Annotation of embedaddon/bird/proto/ospf/topology.c, revision 1.1.1.2

1.1       misho       1: /*
                      2:  *     BIRD -- OSPF Topological Database
                      3:  *
                      4:  *     (c) 1999       Martin Mares <mj@ucw.cz>
                      5:  *     (c) 1999--2004 Ondrej Filip <feela@network.cz>
                      6:  *     (c) 2009--2014 Ondrej Zajicek <santiago@crfreenet.org>
                      7:  *     (c) 2009--2014 CZ.NIC z.s.p.o.
                      8:  *
                      9:  *     Can be freely distributed and used under the terms of the GNU GPL.
                     10:  */
                     11: 
                     12: #include "nest/bird.h"
                     13: #include "lib/string.h"
                     14: 
                     15: #include "ospf.h"
                     16: 
                     17: 
                     18: #define HASH_DEF_ORDER 6
                     19: #define HASH_HI_MARK *4
                     20: #define HASH_HI_STEP 2
                     21: #define HASH_HI_MAX 16
                     22: #define HASH_LO_MARK /5
                     23: #define HASH_LO_STEP 2
                     24: #define HASH_LO_MIN 8
                     25: 
                     26: static inline void * lsab_flush(struct ospf_proto *p);
                     27: static inline void lsab_reset(struct ospf_proto *p);
                     28: 
                     29: 
                     30: /**
                     31:  * ospf_install_lsa - install new LSA into database
                     32:  * @p: OSPF protocol instance
                     33:  * @lsa: LSA header
                     34:  * @type: type of LSA
                     35:  * @domain: domain of LSA
                     36:  * @body: pointer to LSA body
                     37:  *
                     38:  * This function ensures installing new LSA received in LS update into LSA
                     39:  * database. Old instance is replaced. Several actions are taken to detect if
                     40:  * new routing table calculation is necessary. This is described in 13.2 of RFC
                     41:  * 2328. This function is for received LSA only, locally originated LSAs are
                     42:  * installed by ospf_originate_lsa().
                     43:  *
                     44:  * The LSA body in @body is expected to be mb_allocated by the caller and its
                     45:  * ownership is transferred to the LSA entry structure.
                     46:  */
                     47: struct top_hash_entry *
                     48: ospf_install_lsa(struct ospf_proto *p, struct ospf_lsa_header *lsa, u32 type, u32 domain, void *body)
                     49: {
                     50:   struct top_hash_entry *en;
                     51:   int change = 0;
                     52: 
                     53:   en = ospf_hash_get(p->gr, domain, lsa->id, lsa->rt, type);
                     54: 
                     55:   if (!SNODE_VALID(en))
                     56:     s_add_tail(&p->lsal, SNODE en);
                     57: 
                     58:   if ((en->lsa_body == NULL) ||                        /* No old LSA */
                     59:       (en->lsa.length != lsa->length) ||
                     60:       (en->lsa.type_raw != lsa->type_raw) ||   /* Check for OSPFv2 options */
                     61:       (en->lsa.age == LSA_MAXAGE) ||
                     62:       (lsa->age == LSA_MAXAGE) ||
                     63:       memcmp(en->lsa_body, body, lsa->length - sizeof(struct ospf_lsa_header)))
                     64:     change = 1;
                     65: 
                     66:   if ((en->lsa.age == LSA_MAXAGE) && (lsa->age == LSA_MAXAGE))
                     67:     change = 0;
                     68: 
                     69:   mb_free(en->lsa_body);
                     70:   en->lsa_body = body;
                     71:   en->lsa = *lsa;
                     72:   en->init_age = en->lsa.age;
                     73:   en->inst_time = now;
                     74: 
                     75:   /*
                     76:    * We do not set en->mode. It is either default LSA_M_BASIC, or in a special
                     77:    * case when en is local but flushed, there is postponed LSA, self-originated
                     78:    * LSA is received and ospf_install_lsa() is called from ospf_advance_lse(),
                     79:    * then we have en->mode from the postponed LSA origination.
                     80:    */
                     81: 
                     82:   OSPF_TRACE(D_EVENTS, "Installing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x, Age: %u",
                     83:             en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn, en->lsa.age);
                     84: 
                     85:   if (change)
                     86:     ospf_schedule_rtcalc(p);
                     87: 
                     88:   return en;
                     89: }
                     90: 
                     91: /**
                     92:  * ospf_advance_lsa - handle received unexpected self-originated LSA
                     93:  * @p: OSPF protocol instance
                     94:  * @en: current LSA entry or NULL
                     95:  * @lsa: new LSA header
                     96:  * @type: type of LSA
                     97:  * @domain: domain of LSA
                     98:  * @body: pointer to LSA body
                     99:  *
                    100:  * This function handles received unexpected self-originated LSA (@lsa, @body)
                    101:  * by either advancing sequence number of the local LSA instance (@en) and
                    102:  * propagating it, or installing the received LSA and immediately flushing it
                    103:  * (if there is no local LSA; i.e., @en is NULL or MaxAge).
                    104:  *
                    105:  * The LSA body in @body is expected to be mb_allocated by the caller and its
                    106:  * ownership is transferred to the LSA entry structure or it is freed.
                    107:  */
                    108: void
                    109: ospf_advance_lsa(struct ospf_proto *p, struct top_hash_entry *en, struct ospf_lsa_header *lsa, u32 type, u32 domain, void *body)
                    110: {
                    111:   /* RFC 2328 13.4 */
                    112: 
                    113:   if (en && (en->lsa.age < LSA_MAXAGE))
                    114:   {
                    115:     if (lsa->sn != LSA_MAXSEQNO)
                    116:     {
                    117:       /*
                    118:        * We simply advance current LSA to have higher seqnum than received LSA.
                    119:        * The received LSA is ignored and the advanced LSA is propagated instead.
                    120:        *
                    121:        * Although this is an origination of distinct LSA instance and therefore
                    122:        * should be limited by MinLSInterval, we do not enforce it here. Fast
                    123:        * reaction is needed and we are already limited by MinLSArrival.
                    124:        */
                    125: 
                    126:       mb_free(body);
                    127: 
                    128:       en->lsa.sn = lsa->sn + 1;
                    129:       en->lsa.age = 0;
                    130:       en->init_age = 0;
                    131:       en->inst_time = now;
                    132:       lsa_generate_checksum(&en->lsa, en->lsa_body);
                    133: 
                    134:       OSPF_TRACE(D_EVENTS, "Advancing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
                    135:                 en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn);
                    136:     }
                    137:     else
                    138:     {
                    139:       /*
                    140:        * Received LSA has maximal sequence number, so we cannot simply override
                    141:        * it. We have to install it to the database, immediately flush it to
                    142:        * implement sequence number wrapping, and schedule our current LSA to be
                    143:        * originated after the received instance is flushed.
                    144:        */
                    145: 
                    146:       if (en->next_lsa_body == NULL)
                    147:       {
                    148:        /* Schedule current LSA */
                    149:        en->next_lsa_blen = en->lsa.length - sizeof(struct ospf_lsa_header);
                    150:        en->next_lsa_body = en->lsa_body;
                    151:        en->next_lsa_opts = ospf_is_v2(p) ? lsa_get_options(&en->lsa) : 0;
                    152:       }
                    153:       else
                    154:       {
                    155:        /* There is already scheduled LSA, so we just free current one */
                    156:        mb_free(en->lsa_body);
                    157:       }
                    158: 
                    159:       en->lsa_body = body;
                    160:       en->lsa = *lsa;
                    161:       en->lsa.age = LSA_MAXAGE;
                    162:       en->init_age = lsa->age;
                    163:       en->inst_time = now;
                    164: 
                    165:       OSPF_TRACE(D_EVENTS, "Resetting LSA:  Type: %04x, Id: %R, Rt: %R, Seq: %08x",
                    166:                 en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn);
                    167:       OSPF_TRACE(D_EVENTS, "Postponing LSA: Type: %04x, Id: %R, Rt: %R",
                    168:                 en->lsa_type, en->lsa.id, en->lsa.rt);
                    169:     }
                    170:   }
                    171:   else
                    172:   {
                    173:     /*
                    174:      * We do not have received LSA in the database. We have to flush the
                    175:      * received LSA. It has to be installed in the database to secure
                    176:      * retransmissions. Note that the received LSA may already be MaxAge.
                    177:      * Also note that en->next_lsa_* may be defined.
                    178:      */
                    179: 
                    180:     lsa->age = LSA_MAXAGE;
                    181:     en = ospf_install_lsa(p, lsa, type, domain, body);
                    182:   }
                    183: 
                    184:   /*
                    185:    * We flood the updated LSA. Although in some cases the to-be-flooded LSA is
                    186:    * the same as the received LSA, and therefore we should propagate it as
                    187:    * regular received LSA (send the acknowledgement instead of the update to
                    188:    * the neighbor we received it from), we cheat a bit here.
                    189:    */
                    190: 
                    191:   ospf_flood_lsa(p, en, NULL);
                    192: }
                    193: 
                    194: 
                    195: static int
                    196: ospf_do_originate_lsa(struct ospf_proto *p, struct top_hash_entry *en, void *lsa_body, u16 lsa_blen, u16 lsa_opts)
                    197: {
                    198:   /* Enforce MinLSInterval */
                    199:   if ((en->init_age == 0) && en->inst_time && ((en->inst_time + MINLSINTERVAL) > now))
                    200:     return 0;
                    201: 
                    202:   /* Handle wrapping sequence number */
                    203:   if (en->lsa.sn == LSA_MAXSEQNO)
                    204:   {
                    205:     /* Prepare to flush old LSA */
                    206:     if (en->lsa.age != LSA_MAXAGE)
                    207:     {
                    208:       OSPF_TRACE(D_EVENTS, "Resetting LSA:  Type: %04x, Id: %R, Rt: %R, Seq: %08x",
                    209:                 en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn);
                    210: 
                    211:       en->lsa.age = LSA_MAXAGE;
                    212:       ospf_flood_lsa(p, en, NULL);
                    213:       return 0;
                    214:     }
                    215: 
                    216:     /* Already flushing */
                    217:     if ((p->padj != 0) || (en->ret_count != 0))
                    218:       return 0;
                    219: 
                    220:     /* Flush done, just clean up seqnum, lsa_body is freed below */
                    221:     en->lsa.sn = LSA_ZEROSEQNO;
                    222:   }
                    223: 
                    224:   /*
                    225:    * lsa.type_raw is initialized by ospf_hash_get() to OSPFv3 LSA type.
                    226:    * lsa_set_options() implicitly converts it to OSPFv2 LSA type, assuming that
                    227:    * old type is just new type masked by 0xff.  That is not universally true,
                    228:    * but it holds for all OSPFv2 types currently supported by BIRD.
                    229:    */
                    230: 
                    231:   if (ospf_is_v2(p))
                    232:     lsa_set_options(&en->lsa, lsa_opts);
                    233: 
                    234:   mb_free(en->lsa_body);
                    235:   en->lsa_body = lsa_body;
                    236:   en->lsa.length = sizeof(struct ospf_lsa_header) + lsa_blen;
                    237:   en->lsa.sn++;
                    238:   en->lsa.age = 0;
                    239:   en->init_age = 0;
                    240:   en->inst_time = now;
                    241:   lsa_generate_checksum(&en->lsa, en->lsa_body);
                    242: 
                    243:   OSPF_TRACE(D_EVENTS, "Originating LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
                    244:             en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn);
                    245: 
                    246:   ospf_flood_lsa(p, en, NULL);
                    247: 
                    248:   if (en->mode == LSA_M_BASIC)
                    249:     ospf_schedule_rtcalc(p);
                    250: 
                    251:   return 1;
                    252: }
                    253: 
                    254: /**
                    255:  * ospf_originate_lsa - originate new LSA
                    256:  * @p: OSPF protocol instance
                    257:  * @lsa: New LSA specification
                    258:  *
                    259:  * This function prepares a new LSA, installs it into the LSA database and
                    260:  * floods it. If the new LSA cannot be originated now (because the old instance
                    261:  * was originated within MinLSInterval, or because the LSA seqnum is currently
                    262:  * wrapping), the origination is instead scheduled for later. If the new LSA is
                    263:  * equivalent to the current LSA, the origination is skipped. In all cases, the
                    264:  * corresponding LSA entry is returned. The new LSA is based on the LSA
                    265:  * specification (@lsa) and the LSA body from lsab buffer of @p, which is
                    266:  * emptied after the call. The opposite of this function is ospf_flush_lsa().
                    267:  */
                    268: struct top_hash_entry *
                    269: ospf_originate_lsa(struct ospf_proto *p, struct ospf_new_lsa *lsa)
                    270: {
                    271:   struct top_hash_entry *en;
                    272:   void *lsa_body = p->lsab;
                    273:   u16 lsa_blen = p->lsab_used;
                    274:   u16 lsa_length = sizeof(struct ospf_lsa_header) + lsa_blen;
                    275: 
                    276:   en = ospf_hash_get(p->gr, lsa->dom, lsa->id, p->router_id, lsa->type);
                    277: 
                    278:   if (!SNODE_VALID(en))
                    279:     s_add_tail(&p->lsal, SNODE en);
                    280: 
                    281:   if (!en->nf || !en->lsa_body)
                    282:     en->nf = lsa->nf;
                    283: 
                    284:   if (en->nf != lsa->nf)
                    285:   {
                    286:     log(L_ERR "%s: LSA ID collision for %I/%d",
                    287:        p->p.name, lsa->nf->fn.prefix, lsa->nf->fn.pxlen);
                    288: 
                    289:     en = NULL;
                    290:     goto drop;
                    291:   }
                    292: 
                    293:   if (en->mode != lsa->mode)
                    294:     en->mode = lsa->mode;
                    295: 
                    296:   if (en->next_lsa_body)
                    297:   {
                    298:     /* Ignore the new LSA if it is the same as the scheduled one */
                    299:     if ((lsa_blen == en->next_lsa_blen) &&
                    300:        !memcmp(lsa_body, en->next_lsa_body, lsa_blen) &&
                    301:        (!ospf_is_v2(p) || (lsa->opts == en->next_lsa_opts)))
                    302:       goto drop;
                    303: 
                    304:     /* Free scheduled LSA */
                    305:     mb_free(en->next_lsa_body);
                    306:     en->next_lsa_body = NULL;
                    307:     en->next_lsa_blen = 0;
                    308:     en->next_lsa_opts = 0;
                    309:   }
                    310: 
                    311:   /* Ignore the the new LSA if is the same as the current one */
                    312:   if ((en->lsa.age < LSA_MAXAGE) &&
                    313:       (lsa_length == en->lsa.length) &&
                    314:       !memcmp(lsa_body, en->lsa_body, lsa_blen) &&
                    315:       (!ospf_is_v2(p) || (lsa->opts == lsa_get_options(&en->lsa))))
                    316:     goto drop;
                    317: 
                    318:   lsa_body = lsab_flush(p);
                    319: 
                    320:   if (! ospf_do_originate_lsa(p, en, lsa_body, lsa_blen, lsa->opts))
                    321:   {
                    322:     OSPF_TRACE(D_EVENTS, "Postponing LSA: Type: %04x, Id: %R, Rt: %R",
                    323:               en->lsa_type, en->lsa.id, en->lsa.rt);
                    324: 
                    325:     en->next_lsa_body = lsa_body;
                    326:     en->next_lsa_blen = lsa_blen;
                    327:     en->next_lsa_opts = lsa->opts;
                    328:   }
                    329: 
                    330:   return en;
                    331: 
                    332:  drop:
                    333:   lsab_reset(p);
                    334:   return en;
                    335: }
                    336: 
                    337: static void
                    338: ospf_originate_next_lsa(struct ospf_proto *p, struct top_hash_entry *en)
                    339: {
                    340:   /* Called by ospf_update_lsadb() to handle scheduled origination */
                    341: 
                    342:   if (! ospf_do_originate_lsa(p, en, en->next_lsa_body, en->next_lsa_blen, en->next_lsa_opts))
                    343:     return;
                    344: 
                    345:   en->next_lsa_body = NULL;
                    346:   en->next_lsa_blen = 0;
                    347:   en->next_lsa_opts = 0;
                    348: }
                    349: 
                    350: static void
                    351: ospf_refresh_lsa(struct ospf_proto *p, struct top_hash_entry *en)
                    352: {
                    353:   /*
                    354:    * Called by ospf_update_lsadb() for periodic LSA refresh.
                    355:    *
                    356:    * We know that lsa.age < LSA_MAXAGE and lsa.rt is our router ID. We can also
                    357:    * assume that there is no scheduled LSA, because inst_time is deep in past,
                    358:    * therefore ospf_originate_next_lsa() called before would either succeed or
                    359:    * switched lsa.age to LSA_MAXAGE.
                    360:    */
                    361: 
                    362:   OSPF_TRACE(D_EVENTS, "Refreshing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
                    363:             en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn);
                    364: 
                    365:   ASSERT(en->next_lsa_body == NULL);
                    366: 
                    367:   /* Handle wrapping sequence number */
                    368:   if (en->lsa.sn == LSA_MAXSEQNO)
                    369:   {
                    370:     /* Copy LSA body as next LSA to get automatic origination after flush is finished */
                    371:     en->next_lsa_blen = en->lsa.length - sizeof(struct ospf_lsa_header);
                    372:     en->next_lsa_body = mb_alloc(p->p.pool, en->next_lsa_blen);
                    373:     memcpy(en->next_lsa_body, en->lsa_body, en->next_lsa_blen);
                    374:     en->next_lsa_opts = ospf_is_v2(p) ? lsa_get_options(&en->lsa) : 0;
                    375: 
                    376:     en->lsa.age = LSA_MAXAGE;
                    377:     ospf_flood_lsa(p, en, NULL);
                    378:     return;
                    379:   }
                    380: 
                    381:   en->lsa.sn++;
                    382:   en->lsa.age = 0;
                    383:   en->init_age = 0;
                    384:   en->inst_time = now;
                    385:   lsa_generate_checksum(&en->lsa, en->lsa_body);
                    386:   ospf_flood_lsa(p, en, NULL);
                    387: }
                    388: 
                    389: /**
                    390:  * ospf_flush_lsa - flush LSA from OSPF domain
                    391:  * @p: OSPF protocol instance
                    392:  * @en: LSA entry to flush
                    393:  *
                    394:  * This function flushes @en from the OSPF domain by setting its age to
                    395:  * %LSA_MAXAGE and flooding it. That also triggers subsequent events in LSA
                    396:  * lifecycle leading to removal of the LSA from the LSA database (e.g. the LSA
                    397:  * content is freed when flushing is acknowledged by neighbors). The function
                    398:  * does nothing if the LSA is already being flushed. LSA entries are not
                    399:  * immediately removed when being flushed, the caller may assume that @en still
                    400:  * exists after the call. The function is the opposite of ospf_originate_lsa()
                    401:  * and is supposed to do the right thing even in cases of postponed
                    402:  * origination.
                    403:  */
                    404: void
                    405: ospf_flush_lsa(struct ospf_proto *p, struct top_hash_entry *en)
                    406: {
1.1.1.2 ! misho     407:   en->nf = NULL;
        !           408: 
1.1       misho     409:   if (en->next_lsa_body)
                    410:   {
                    411:     mb_free(en->next_lsa_body);
                    412:     en->next_lsa_body = NULL;
                    413:     en->next_lsa_blen = 0;
                    414:     en->next_lsa_opts = 0;
                    415:   }
                    416: 
                    417:   if (en->lsa.age == LSA_MAXAGE)
                    418:     return;
                    419: 
                    420:   OSPF_TRACE(D_EVENTS, "Flushing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
                    421:             en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn);
                    422: 
                    423:   en->lsa.age = LSA_MAXAGE;
                    424:   ospf_flood_lsa(p, en, NULL);
                    425: 
                    426:   if (en->mode == LSA_M_BASIC)
                    427:     ospf_schedule_rtcalc(p);
                    428: 
                    429:   en->mode = LSA_M_BASIC;
                    430: }
                    431: 
                    432: static void
                    433: ospf_clear_lsa(struct ospf_proto *p, struct top_hash_entry *en)
                    434: {
                    435:   /*
                    436:    * Called by ospf_update_lsadb() as part of LSA flushing process.
                    437:    * Flushed LSA was acknowledged by neighbors and we can free its content.
                    438:    * The log message is for 'remove' - we hide empty LSAs from users.
                    439:    */
                    440: 
                    441:   OSPF_TRACE(D_EVENTS, "Removing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
                    442:             en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn);
                    443: 
                    444:   if (en->lsa.sn == LSA_MAXSEQNO)
                    445:     en->lsa.sn = LSA_ZEROSEQNO;
                    446: 
                    447:   mb_free(en->lsa_body);
                    448:   en->lsa_body = NULL;
                    449: }
                    450: 
                    451: static void
                    452: ospf_remove_lsa(struct ospf_proto *p, struct top_hash_entry *en)
                    453: {
                    454:   /*
                    455:    * Called by ospf_update_lsadb() as part of LSA flushing process.
                    456:    * Both lsa_body and next_lsa_body are NULL.
                    457:    */
                    458: 
                    459:   s_rem_node(SNODE en);
                    460:   ospf_hash_delete(p->gr, en);
                    461: }
                    462: 
                    463: /**
                    464:  * ospf_update_lsadb - update LSA database
                    465:  * @p: OSPF protocol instance
                    466:  *
                    467:  * This function is periodicaly invoked from ospf_disp(). It does some periodic
                    468:  * or postponed processing related to LSA entries. It originates postponed LSAs
                    469:  * scheduled by ospf_originate_lsa(), It continues in flushing processes started
                    470:  * by ospf_flush_lsa(). It also periodically refreshs locally originated LSAs --
                    471:  * when the current instance is older %LSREFRESHTIME, a new instance is originated.
                    472:  * Finally, it also ages stored LSAs and flushes ones that reached %LSA_MAXAGE.
                    473:  *
                    474:  * The RFC 2328 says that a router should periodically check checksums of all
                    475:  * stored LSAs to detect hardware problems. This is not implemented.
                    476:  */
                    477: void
                    478: ospf_update_lsadb(struct ospf_proto *p)
                    479: {
                    480:   struct top_hash_entry *en, *nxt;
                    481:   bird_clock_t real_age;
                    482: 
                    483:   WALK_SLIST_DELSAFE(en, nxt, p->lsal)
                    484:   {
                    485:     if (en->next_lsa_body)
                    486:       ospf_originate_next_lsa(p, en);
                    487: 
                    488:     real_age = en->init_age + (now - en->inst_time);
                    489: 
                    490:     if (en->lsa.age == LSA_MAXAGE)
                    491:     {
                    492:       if (en->lsa_body && (p->padj == 0) && (en->ret_count == 0))
                    493:        ospf_clear_lsa(p, en);
                    494: 
                    495:       if ((en->lsa_body == NULL) && (en->next_lsa_body == NULL) &&
                    496:          ((en->lsa.rt != p->router_id) || (real_age >= LSA_MAXAGE)))
                    497:        ospf_remove_lsa(p, en);
                    498: 
                    499:       continue;
                    500:     }
                    501: 
                    502:     if ((en->lsa.rt == p->router_id) && (real_age >= LSREFRESHTIME))
                    503:     {
                    504:       ospf_refresh_lsa(p, en);
                    505:       continue;
                    506:     }
                    507: 
                    508:     if (real_age >= LSA_MAXAGE)
                    509:     {
                    510:       ospf_flush_lsa(p, en);
                    511:       continue;
                    512:     }
                    513: 
                    514:     en->lsa.age = real_age;
                    515:   }
                    516: }
                    517: 
                    518: 
                    519: static inline u32
                    520: ort_to_lsaid(struct ospf_proto *p UNUSED4 UNUSED6, ort *nf)
                    521: {
                    522:   /*
                    523:    * In OSPFv2, We have to map IP prefixes to u32 in such manner that resulting
                    524:    * u32 interpreted as IP address is a member of given prefix. Therefore, /32
                    525:    * prefix have to be mapped on itself.  All received prefixes have to be
                    526:    * mapped on different u32s.
                    527:    *
                    528:    * We have an assumption that if there is nontrivial (non-/32) network prefix,
                    529:    * then there is not /32 prefix for the first and the last IP address of the
                    530:    * network (these are usually reserved, therefore it is not an important
                    531:    * restriction).  The network prefix is mapped to the first or the last IP
                    532:    * address in the manner that disallow collisions - we use the IP address that
                    533:    * cannot be used by the parent prefix.
                    534:    *
                    535:    * For example:
                    536:    * 192.168.0.0/24 maps to 192.168.0.255
                    537:    * 192.168.1.0/24 maps to 192.168.1.0
                    538:    * because 192.168.0.0 and 192.168.1.255 might be used by 192.168.0.0/23 .
                    539:    *
                    540:    * Appendig E of RFC 2328 suggests different algorithm, that tries to maximize
                    541:    * both compatibility and subnetting. But as it is not possible to have both
                    542:    * reliably and the suggested algorithm was unnecessary complicated and it
                    543:    * does crazy things like changing LSA ID for a network because different
                    544:    * network appeared, we choose a different way.
                    545:    *
                    546:    * In OSPFv3, it is simpler. There is not a requirement for membership of the
                    547:    * result in the input network, so we just use a hash-based unique ID of a
                    548:    * routing table entry for a route that originated given LSA. For ext-LSA, it
                    549:    * is an imported route in the nest's routing table (p->table). For summary-LSA,
                    550:    * it is a 'source' route in the protocol internal routing table (p->rtf).
                    551:    */
                    552: 
                    553:   if (ospf_is_v3(p))
                    554:     return nf->fn.uid;
                    555: 
                    556:   u32 id = ipa_to_u32(nf->fn.prefix);
                    557:   int pxlen = nf->fn.pxlen;
                    558: 
                    559:   if ((pxlen == 0) || (pxlen == 32))
                    560:     return id;
                    561: 
                    562:   if (id & (1 << (32 - pxlen)))
                    563:     return id;
                    564:   else
                    565:     return id | ~u32_mkmask(pxlen);
                    566: }
                    567: 
                    568: 
                    569: static void *
                    570: lsab_alloc(struct ospf_proto *p, uint size)
                    571: {
                    572:   uint offset = p->lsab_used;
                    573:   p->lsab_used += size;
                    574:   if (p->lsab_used > p->lsab_size)
                    575:   {
                    576:     p->lsab_size = MAX(p->lsab_used, 2 * p->lsab_size);
                    577:     p->lsab = p->lsab ? mb_realloc(p->lsab, p->lsab_size):
                    578:       mb_alloc(p->p.pool, p->lsab_size);
                    579:   }
                    580:   return ((byte *) p->lsab) + offset;
                    581: }
                    582: 
                    583: static inline void *
                    584: lsab_allocz(struct ospf_proto *p, uint size)
                    585: {
                    586:   void *r = lsab_alloc(p, size);
                    587:   bzero(r, size);
                    588:   return r;
                    589: }
                    590: 
                    591: static inline void *
                    592: lsab_flush(struct ospf_proto *p)
                    593: {
                    594:   void *r = mb_alloc(p->p.pool, p->lsab_used);
                    595:   memcpy(r, p->lsab, p->lsab_used);
                    596:   p->lsab_used = 0;
                    597:   return r;
                    598: }
                    599: 
                    600: static inline void
                    601: lsab_reset(struct ospf_proto *p)
                    602: {
                    603:   p->lsab_used = 0;
                    604: }
                    605: 
                    606: static inline void *
                    607: lsab_offset(struct ospf_proto *p, uint offset)
                    608: {
                    609:   return ((byte *) p->lsab) + offset;
                    610: }
                    611: 
                    612: static inline void * UNUSED
                    613: lsab_end(struct ospf_proto *p)
                    614: {
                    615:   return ((byte *) p->lsab) + p->lsab_used;
                    616: }
                    617: 
                    618: 
                    619: /*
                    620:  *     Router-LSA handling
                    621:  *     Type = LSA_T_RT
                    622:  */
                    623: 
                    624: static int
                    625: configured_stubnet(struct ospf_area *oa, struct ifa *a)
                    626: {
                    627:   /* Does not work for IA_PEER addresses, but it is not called on these */
                    628:   struct ospf_stubnet_config *sn;
                    629:   WALK_LIST(sn, oa->ac->stubnet_list)
                    630:   {
                    631:     if (sn->summary)
                    632:     {
                    633:       if (ipa_in_net(a->prefix, sn->px.addr, sn->px.len) && (a->pxlen >= sn->px.len))
                    634:        return 1;
                    635:     }
                    636:     else
                    637:     {
                    638:       if (ipa_equal(a->prefix, sn->px.addr) && (a->pxlen == sn->px.len))
                    639:        return 1;
                    640:     }
                    641:   }
                    642: 
                    643:   return 0;
                    644: }
                    645: 
                    646: static int
                    647: bcast_net_active(struct ospf_iface *ifa)
                    648: {
                    649:   struct ospf_neighbor *neigh;
                    650: 
                    651:   if (ifa->state == OSPF_IS_WAITING)
                    652:     return 0;
                    653: 
                    654:   WALK_LIST(neigh, ifa->neigh_list)
                    655:   {
                    656:     if (neigh->state == NEIGHBOR_FULL)
                    657:     {
                    658:       if (neigh->rid == ifa->drid)
                    659:        return 1;
                    660: 
                    661:       if (ifa->state == OSPF_IS_DR)
                    662:        return 1;
                    663:     }
                    664:   }
                    665: 
                    666:   return 0;
                    667: }
                    668: 
                    669: static inline u32
                    670: get_rt_options(struct ospf_proto *p, struct ospf_area *oa, int bitv)
                    671: {
                    672:   u32 opts = 0;
                    673: 
                    674:   if (p->areano > 1)
                    675:     opts |= OPT_RT_B;
                    676: 
                    677:   if ((p->areano > 1) && oa_is_nssa(oa) && oa->ac->translator)
                    678:     opts |= OPT_RT_NT;
                    679: 
                    680:   if (p->asbr && !oa_is_stub(oa))
                    681:     opts |= OPT_RT_E;
                    682: 
                    683:   if (bitv)
                    684:     opts |= OPT_RT_V;
                    685: 
                    686:   return opts;
                    687: }
                    688: 
                    689: static inline void
                    690: add_rt2_lsa_link(struct ospf_proto *p, u8 type, u32 id, u32 data, u16 metric)
                    691: {
                    692:   struct ospf_lsa_rt2_link *ln = lsab_alloc(p, sizeof(struct ospf_lsa_rt2_link));
                    693:   ln->type = type;
                    694:   ln->id = id;
                    695:   ln->data = data;
                    696:   ln->metric = metric;
                    697:   ln->no_tos = 0;
                    698: }
                    699: 
                    700: static void
                    701: prepare_rt2_lsa_body(struct ospf_proto *p, struct ospf_area *oa)
                    702: {
                    703:   struct ospf_iface *ifa;
                    704:   int i = 0, bitv = 0;
                    705:   struct ospf_neighbor *neigh;
                    706: 
                    707:   ASSERT(p->lsab_used == 0);
                    708:   lsab_allocz(p, sizeof(struct ospf_lsa_rt));
                    709:   /* ospf_lsa_rt header will be filled later */
                    710: 
                    711:   WALK_LIST(ifa, p->iface_list)
                    712:   {
                    713:     int net_lsa = 0;
                    714:     u32 link_cost = p->stub_router ? 0xffff : ifa->cost;
                    715: 
                    716:     if ((ifa->type == OSPF_IT_VLINK) && (ifa->voa == oa) &&
                    717:        (!EMPTY_LIST(ifa->neigh_list)))
                    718:     {
                    719:       neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
                    720:       if ((neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
                    721:        bitv = 1;
                    722:     }
                    723: 
                    724:     if ((ifa->oa != oa) || (ifa->state == OSPF_IS_DOWN))
                    725:       continue;
                    726: 
                    727:     ifa->rt_pos_beg = i;
                    728: 
                    729:     /* RFC 2328 - 12.4.1.1-4 */
                    730:     switch (ifa->type)
                    731:     {
                    732:     case OSPF_IT_PTP:
                    733:     case OSPF_IT_PTMP:
                    734:       WALK_LIST(neigh, ifa->neigh_list)
                    735:        if (neigh->state == NEIGHBOR_FULL)
                    736:        {
                    737:          /*
                    738:           * ln->data should be ifa->iface_id in case of no/ptp
                    739:           * address (ifa->addr->flags & IA_PEER) on PTP link (see
                    740:           * RFC 2328 12.4.1.1.), but the iface ID value has no use,
                    741:           * while using IP address even in this case is here for
                    742:           * compatibility with some broken implementations that use
                    743:           * this address as a next-hop.
                    744:           */
                    745:          add_rt2_lsa_link(p, LSART_PTP, neigh->rid, ipa_to_u32(ifa->addr->ip), link_cost);
                    746:          i++;
                    747:        }
                    748:       break;
                    749: 
                    750:     case OSPF_IT_BCAST:
                    751:     case OSPF_IT_NBMA:
                    752:       if (bcast_net_active(ifa))
                    753:       {
                    754:        add_rt2_lsa_link(p, LSART_NET, ipa_to_u32(ifa->drip), ipa_to_u32(ifa->addr->ip), link_cost);
                    755:        i++;
                    756:        net_lsa = 1;
                    757:       }
                    758:       break;
                    759: 
                    760:     case OSPF_IT_VLINK:
                    761:       neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
                    762:       if ((!EMPTY_LIST(ifa->neigh_list)) && (neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
                    763:        add_rt2_lsa_link(p, LSART_VLNK, neigh->rid, ipa_to_u32(ifa->addr->ip), link_cost), i++;
                    764:       break;
                    765: 
                    766:     default:
                    767:       log(L_BUG "OSPF: Unknown interface type");
                    768:       break;
                    769:     }
                    770: 
                    771:     ifa->rt_pos_end = i;
                    772: 
                    773:     /* Now we will originate stub area if there is no primary */
                    774:     if (net_lsa ||
                    775:        (ifa->type == OSPF_IT_VLINK) ||
                    776:        ((ifa->addr->flags & IA_PEER) && ! ifa->cf->stub) ||
                    777:        configured_stubnet(oa, ifa->addr))
                    778:       continue;
                    779: 
                    780:       /* Host or network stub entry */
                    781:     if ((ifa->addr->flags & IA_HOST) ||
                    782:        (ifa->state == OSPF_IS_LOOP) ||
                    783:        (ifa->type == OSPF_IT_PTMP))
                    784:       add_rt2_lsa_link(p, LSART_STUB, ipa_to_u32(ifa->addr->ip), 0xffffffff, 0);
                    785:     else
                    786:       add_rt2_lsa_link(p, LSART_STUB, ipa_to_u32(ifa->addr->prefix), u32_mkmask(ifa->addr->pxlen), ifa->cost);
                    787:     i++;
                    788: 
                    789:     ifa->rt_pos_end = i;
                    790:   }
                    791: 
                    792:   struct ospf_stubnet_config *sn;
                    793:   WALK_LIST(sn, oa->ac->stubnet_list)
                    794:     if (!sn->hidden)
                    795:       add_rt2_lsa_link(p, LSART_STUB, ipa_to_u32(sn->px.addr), u32_mkmask(sn->px.len), sn->cost), i++;
                    796: 
                    797:   struct ospf_lsa_rt *rt = p->lsab;
                    798:   /* Store number of links in lower half of options */
                    799:   rt->options = get_rt_options(p, oa, bitv) | (u16) i;
                    800: }
                    801: 
                    802: static inline void
                    803: add_rt3_lsa_link(struct ospf_proto *p, u8 type, struct ospf_iface *ifa, u32 nif, u32 id)
                    804: {
                    805:   struct ospf_lsa_rt3_link *ln = lsab_alloc(p, sizeof(struct ospf_lsa_rt3_link));
                    806:   ln->type = type;
                    807:   ln->padding = 0;
                    808:   ln->metric = ifa->cost;
                    809:   ln->lif = ifa->iface_id;
                    810:   ln->nif = nif;
                    811:   ln->id = id;
                    812: }
                    813: 
                    814: static void
                    815: prepare_rt3_lsa_body(struct ospf_proto *p, struct ospf_area *oa)
                    816: {
                    817:   struct ospf_iface *ifa;
                    818:   struct ospf_neighbor *neigh;
                    819:   int bitv = 0;
                    820:   int i = 0;
                    821: 
                    822:   ASSERT(p->lsab_used == 0);
                    823:   lsab_allocz(p, sizeof(struct ospf_lsa_rt));
                    824:   /* ospf_lsa_rt header will be filled later */
                    825: 
                    826:   WALK_LIST(ifa, p->iface_list)
                    827:   {
                    828:     if ((ifa->type == OSPF_IT_VLINK) && (ifa->voa == oa) &&
                    829:        (!EMPTY_LIST(ifa->neigh_list)))
                    830:     {
                    831:       neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
                    832:       if ((neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
                    833:        bitv = 1;
                    834:     }
                    835: 
                    836:     if ((ifa->oa != oa) || (ifa->state == OSPF_IS_DOWN))
                    837:       continue;
                    838: 
                    839:     ifa->rt_pos_beg = i;
                    840: 
                    841:     /* RFC 5340 - 4.4.3.2 */
                    842:     switch (ifa->type)
                    843:     {
                    844:     case OSPF_IT_PTP:
                    845:     case OSPF_IT_PTMP:
                    846:       WALK_LIST(neigh, ifa->neigh_list)
                    847:        if (neigh->state == NEIGHBOR_FULL)
                    848:          add_rt3_lsa_link(p, LSART_PTP, ifa, neigh->iface_id, neigh->rid), i++;
                    849:       break;
                    850: 
                    851:     case OSPF_IT_BCAST:
                    852:     case OSPF_IT_NBMA:
                    853:       if (bcast_net_active(ifa))
                    854:        add_rt3_lsa_link(p, LSART_NET, ifa, ifa->dr_iface_id, ifa->drid), i++;
                    855:       break;
                    856: 
                    857:     case OSPF_IT_VLINK:
                    858:       neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list);
                    859:       if ((!EMPTY_LIST(ifa->neigh_list)) && (neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff))
                    860:        add_rt3_lsa_link(p, LSART_VLNK, ifa, neigh->iface_id, neigh->rid), i++;
                    861:       break;
                    862: 
                    863:     default:
                    864:       log(L_BUG "OSPF: Unknown interface type");
                    865:       break;
                    866:     }
                    867: 
                    868:     ifa->rt_pos_end = i;
                    869:   }
                    870: 
                    871:   struct ospf_lsa_rt *rt = p->lsab;
                    872:   rt->options = get_rt_options(p, oa, bitv) | (oa->options & LSA_OPTIONS_MASK);
                    873: }
                    874: 
                    875: static void
                    876: ospf_originate_rt_lsa(struct ospf_proto *p, struct ospf_area *oa)
                    877: {
                    878:   struct ospf_new_lsa lsa = {
                    879:     .type = LSA_T_RT,
                    880:     .dom  = oa->areaid,
                    881:     .id   = ospf_is_v2(p) ? p->router_id : 0,
                    882:     .opts = oa->options
                    883:   };
                    884: 
                    885:   OSPF_TRACE(D_EVENTS, "Updating router state for area %R", oa->areaid);
                    886: 
                    887:   if (ospf_is_v2(p))
                    888:     prepare_rt2_lsa_body(p, oa);
                    889:   else
                    890:     prepare_rt3_lsa_body(p, oa);
                    891: 
                    892:   oa->rt = ospf_originate_lsa(p, &lsa);
                    893: }
                    894: 
                    895: 
                    896: /*
                    897:  *     Net-LSA handling
                    898:  *     Type = LSA_T_NET
                    899:  */
                    900: 
                    901: static void
                    902: prepare_net2_lsa_body(struct ospf_proto *p, struct ospf_iface *ifa)
                    903: {
                    904:   struct ospf_lsa_net *net;
                    905:   struct ospf_neighbor *n;
                    906:   int nodes = ifa->fadj + 1;
                    907:   u16 i = 1;
                    908: 
                    909:   ASSERT(p->lsab_used == 0);
                    910:   net = lsab_alloc(p, sizeof(struct ospf_lsa_net) + 4 * nodes);
                    911: 
                    912:   net->optx = u32_mkmask(ifa->addr->pxlen);
                    913:   net->routers[0] = p->router_id;
                    914: 
                    915:   WALK_LIST(n, ifa->neigh_list)
                    916:   {
                    917:     if (n->state == NEIGHBOR_FULL)
                    918:     {
                    919:       net->routers[i] = n->rid;
                    920:       i++;
                    921:     }
                    922:   }
                    923:   ASSERT(i == nodes);
                    924: }
                    925: 
                    926: static void
                    927: prepare_net3_lsa_body(struct ospf_proto *p, struct ospf_iface *ifa)
                    928: {
                    929:   struct ospf_lsa_net *net;
                    930:   int nodes = ifa->fadj + 1;
                    931:   u32 options = 0;
                    932:   u16 i = 1;
                    933: 
                    934:   ASSERT(p->lsab_used == 0);
                    935:   net = lsab_alloc(p, sizeof(struct ospf_lsa_net) + 4 * nodes);
                    936: 
                    937:   net->routers[0] = p->router_id;
                    938: 
                    939:   struct ospf_neighbor *n;
                    940:   WALK_LIST(n, ifa->neigh_list)
                    941:   {
                    942:     if (n->state == NEIGHBOR_FULL)
                    943:     {
                    944:       /* In OSPFv3, we would like to merge options from Link LSAs of added neighbors */
                    945: 
                    946:       struct top_hash_entry *en =
                    947:        ospf_hash_find(p->gr, ifa->iface_id, n->iface_id, n->rid, LSA_T_LINK);
                    948: 
                    949:       if (en)
                    950:        options |= ((struct ospf_lsa_link *) en->lsa_body)->options;
                    951: 
                    952:       net->routers[i] = n->rid;
                    953:       i++;
                    954:     }
                    955:   }
                    956:   ASSERT(i == nodes);
                    957: 
                    958:   net->optx = options & LSA_OPTIONS_MASK;
                    959: }
                    960: 
                    961: static void
                    962: ospf_originate_net_lsa(struct ospf_proto *p, struct ospf_iface *ifa)
                    963: {
                    964:   struct ospf_new_lsa lsa = {
                    965:     .type = LSA_T_NET,
                    966:     .dom  = ifa->oa->areaid,
                    967:     .id   = ospf_is_v2(p) ? ipa_to_u32(ifa->addr->ip) : ifa->iface_id,
                    968:     .opts = ifa->oa->options,
                    969:     .ifa  = ifa
                    970:   };
                    971: 
                    972:   OSPF_TRACE(D_EVENTS, "Updating network state for %s (Id: %R)", ifa->ifname, lsa.id);
                    973: 
                    974:   if (ospf_is_v2(p))
                    975:     prepare_net2_lsa_body(p, ifa);
                    976:   else
                    977:     prepare_net3_lsa_body(p, ifa);
                    978: 
                    979:   ifa->net_lsa = ospf_originate_lsa(p, &lsa);
                    980: }
                    981: 
                    982: 
                    983: /*
                    984:  *     (Net|Rt)-summary-LSA handling
                    985:  *     (a.k.a. Inter-Area-(Prefix|Router)-LSA)
                    986:  *     Type = LSA_T_SUM_NET, LSA_T_SUM_RT
                    987:  */
                    988: 
                    989: static inline void
                    990: prepare_sum2_lsa_body(struct ospf_proto *p, uint pxlen, u32 metric)
                    991: {
                    992:   struct ospf_lsa_sum2 *sum;
                    993: 
                    994:   sum = lsab_allocz(p, sizeof(struct ospf_lsa_sum2));
                    995:   sum->netmask = u32_mkmask(pxlen);
                    996:   sum->metric = metric;
                    997: }
                    998: 
                    999: static inline void
                   1000: prepare_sum3_net_lsa_body(struct ospf_proto *p, ort *nf, u32 metric)
                   1001: {
                   1002:   struct ospf_lsa_sum3_net *sum;
                   1003: 
                   1004:   sum = lsab_allocz(p, sizeof(struct ospf_lsa_sum3_net) + IPV6_PREFIX_SPACE(nf->fn.pxlen));
                   1005:   sum->metric = metric;
                   1006:   put_ipv6_prefix(sum->prefix, nf->fn.prefix, nf->fn.pxlen, 0, 0);
                   1007: }
                   1008: 
                   1009: static inline void
                   1010: prepare_sum3_rt_lsa_body(struct ospf_proto *p, u32 drid, u32 metric, u32 options)
                   1011: {
                   1012:   struct ospf_lsa_sum3_rt *sum;
                   1013: 
                   1014:   sum = lsab_allocz(p, sizeof(struct ospf_lsa_sum3_rt));
                   1015:   sum->options = options;
                   1016:   sum->metric = metric;
                   1017:   sum->drid = drid;
                   1018: }
                   1019: 
                   1020: void
                   1021: ospf_originate_sum_net_lsa(struct ospf_proto *p, struct ospf_area *oa, ort *nf, int metric)
                   1022: {
                   1023:   struct ospf_new_lsa lsa = {
                   1024:     .type = LSA_T_SUM_NET,
                   1025:     .mode = LSA_M_RTCALC,
                   1026:     .dom  = oa->areaid,
                   1027:     .id   = ort_to_lsaid(p, nf),
                   1028:     .opts = oa->options,
                   1029:     .nf   = nf
                   1030:   };
                   1031: 
                   1032:   if (ospf_is_v2(p))
                   1033:     prepare_sum2_lsa_body(p, nf->fn.pxlen, metric);
                   1034:   else
                   1035:     prepare_sum3_net_lsa_body(p, nf, metric);
                   1036: 
                   1037:   ospf_originate_lsa(p, &lsa);
                   1038: }
                   1039: 
                   1040: void
                   1041: ospf_originate_sum_rt_lsa(struct ospf_proto *p, struct ospf_area *oa, ort *nf, int metric, u32 options)
                   1042: {
                   1043:   struct ospf_new_lsa lsa = {
                   1044:     .type = LSA_T_SUM_RT,
                   1045:     .mode = LSA_M_RTCALC,
                   1046:     .dom  = oa->areaid,
                   1047:     .id   = ipa_to_rid(nf->fn.prefix), /* Router ID of ASBR, irrelevant for OSPFv3 */
                   1048:     .opts = oa->options
                   1049:   };
                   1050: 
                   1051:   if (ospf_is_v2(p))
                   1052:     prepare_sum2_lsa_body(p, 0, metric);
                   1053:   else
                   1054:     prepare_sum3_rt_lsa_body(p, lsa.id, metric, options & LSA_OPTIONS_MASK);
                   1055: 
                   1056:   ospf_originate_lsa(p, &lsa);
                   1057: }
                   1058: 
                   1059: 
                   1060: /*
                   1061:  *     AS-external-LSA and NSSA-LSA handling
                   1062:  *     Type = LSA_T_EXT, LSA_T_NSSA
                   1063:  */
                   1064: 
                   1065: static inline void
                   1066: prepare_ext2_lsa_body(struct ospf_proto *p, uint pxlen,
                   1067:                      u32 metric, u32 ebit, ip_addr fwaddr, u32 tag)
                   1068: {
                   1069:   struct ospf_lsa_ext2 *ext;
                   1070: 
                   1071:   ext = lsab_allocz(p, sizeof(struct ospf_lsa_ext2));
                   1072:   ext->metric = metric & LSA_METRIC_MASK;
                   1073:   ext->netmask = u32_mkmask(pxlen);
                   1074:   ext->fwaddr = ipa_to_u32(fwaddr);
                   1075:   ext->tag = tag;
                   1076: 
                   1077:   if (ebit)
                   1078:     ext->metric |= LSA_EXT2_EBIT;
                   1079: }
                   1080: 
                   1081: static inline void
                   1082: prepare_ext3_lsa_body(struct ospf_proto *p, ort *nf,
                   1083:                      u32 metric, u32 ebit, ip_addr fwaddr, u32 tag, int pbit)
                   1084: {
                   1085:   struct ospf_lsa_ext3 *ext;
                   1086:   int bsize = sizeof(struct ospf_lsa_ext3)
                   1087:     + IPV6_PREFIX_SPACE(nf->fn.pxlen)
                   1088:     + (ipa_nonzero(fwaddr) ? 16 : 0)
                   1089:     + (tag ? 4 : 0);
                   1090: 
                   1091:   ext = lsab_allocz(p, bsize);
                   1092:   ext->metric = metric & LSA_METRIC_MASK;
                   1093:   u32 *buf = ext->rest;
                   1094: 
                   1095:   buf = put_ipv6_prefix(buf, nf->fn.prefix, nf->fn.pxlen, pbit ? OPT_PX_P : 0, 0);
                   1096: 
                   1097:   if (ebit)
                   1098:     ext->metric |= LSA_EXT3_EBIT;
                   1099: 
                   1100:   if (ipa_nonzero(fwaddr))
                   1101:   {
                   1102:     ext->metric |= LSA_EXT3_FBIT;
                   1103:     buf = put_ipv6_addr(buf, fwaddr);
                   1104:   }
                   1105: 
                   1106:   if (tag)
                   1107:   {
                   1108:     ext->metric |= LSA_EXT3_TBIT;
                   1109:     *buf++ = tag;
                   1110:   }
                   1111: }
                   1112: 
                   1113: /**
                   1114:  * originate_ext_lsa - new route received from nest and filters
                   1115:  * @p: OSPF protocol instance
                   1116:  * @oa: ospf_area for which LSA is originated
                   1117:  * @nf: network prefix and mask
                   1118:  * @mode: the mode of the LSA (LSA_M_EXPORT or LSA_M_RTCALC)
                   1119:  * @metric: the metric of a route
                   1120:  * @ebit: E-bit for route metric (bool)
                   1121:  * @fwaddr: the forwarding address
                   1122:  * @tag: the route tag
                   1123:  * @pbit: P-bit for NSSA LSAs (bool), ignored for external LSAs
                   1124:  *
                   1125:  * If I receive a message that new route is installed, I try to originate an
                   1126:  * external LSA. If @oa is an NSSA area, NSSA-LSA is originated instead.
                   1127:  * @oa should not be a stub area. @src does not specify whether the LSA
                   1128:  * is external or NSSA, but it specifies the source of origination -
                   1129:  * the export from ospf_rt_notify(), or the NSSA-EXT translation.
                   1130:  */
                   1131: void
                   1132: ospf_originate_ext_lsa(struct ospf_proto *p, struct ospf_area *oa, ort *nf, u8 mode,
                   1133:                       u32 metric, u32 ebit, ip_addr fwaddr, u32 tag, int pbit)
                   1134: {
                   1135:   struct ospf_new_lsa lsa = {
                   1136:     .type = oa ? LSA_T_NSSA : LSA_T_EXT,
                   1137:     .mode = mode, /* LSA_M_EXPORT or LSA_M_RTCALC */
                   1138:     .dom  = oa ? oa->areaid : 0,
                   1139:     .id   = ort_to_lsaid(p, nf),
                   1140:     .opts = oa ? (pbit ? OPT_P : 0) : OPT_E,
                   1141:     .nf   = nf
                   1142:   };
                   1143: 
                   1144:   if (ospf_is_v2(p))
                   1145:     prepare_ext2_lsa_body(p, nf->fn.pxlen, metric, ebit, fwaddr, tag);
                   1146:   else
                   1147:     prepare_ext3_lsa_body(p, nf, metric, ebit, fwaddr, tag, oa && pbit);
                   1148: 
                   1149:   ospf_originate_lsa(p, &lsa);
                   1150: }
                   1151: 
                   1152: static struct top_hash_entry *
                   1153: ospf_hash_find_(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type);
                   1154: 
                   1155: static void
                   1156: ospf_flush_ext_lsa(struct ospf_proto *p, struct ospf_area *oa, ort *nf)
                   1157: {
                   1158:   struct top_hash_entry *en;
                   1159: 
                   1160:   u32 type = oa ? LSA_T_NSSA : LSA_T_EXT;
                   1161:   u32 dom = oa ? oa->areaid : 0;
                   1162:   u32 id = ort_to_lsaid(p, nf);
                   1163: 
                   1164:   en = ospf_hash_find_(p->gr, dom, id, p->router_id, type);
                   1165: 
                   1166:   if (!en || (en->nf != nf))
                   1167:     return;
                   1168: 
                   1169:   ospf_flush_lsa(p, en);
                   1170: }
                   1171: 
                   1172: static inline int
                   1173: use_gw_for_fwaddr(struct ospf_proto *p, ip_addr gw, struct iface *iface)
                   1174: {
                   1175:   struct ospf_iface *ifa;
                   1176: 
                   1177:   if (ipa_zero(gw) || ipa_is_link_local(gw))
                   1178:     return 0;
                   1179: 
                   1180:   WALK_LIST(ifa, p->iface_list)
                   1181:     if ((ifa->iface == iface) &&
                   1182:        (!ospf_is_v2(p) || ipa_in_net(gw, ifa->addr->prefix, ifa->addr->pxlen)))
                   1183:       return 1;
                   1184: 
                   1185:   return 0;
                   1186: }
                   1187: 
                   1188: static inline ip_addr
                   1189: find_surrogate_fwaddr(struct ospf_proto *p, struct ospf_area *oa)
                   1190: {
                   1191:   struct ospf_iface *ifa;
                   1192:   struct ifa *a, *cur_addr = NULL;
                   1193:   int np, cur_np = 0;
                   1194: 
                   1195:   /* RFC 3101 2.3 - surrogate forwarding address selection */
                   1196: 
                   1197:   WALK_LIST(ifa, p->iface_list)
                   1198:   {
                   1199:     if ((ifa->oa != oa) ||
                   1200:        (ifa->type == OSPF_IT_VLINK))
                   1201:       continue;
                   1202: 
                   1203:     if (ospf_is_v2(p))
                   1204:     {
                   1205:       a = ifa->addr;
                   1206:       if (a->flags & IA_PEER)
                   1207:        continue;
                   1208: 
                   1209:       np = (a->flags & IA_HOST) ? 3 : (ifa->stub ? 2 : 1);
                   1210:       if (np > cur_np)
                   1211:       {
                   1212:        cur_addr = a;
                   1213:        cur_np = np;
                   1214:       }
                   1215:     }
                   1216:     else /* OSPFv3 */
                   1217:     {
                   1218:       WALK_LIST(a, ifa->iface->addrs)
                   1219:       {
                   1220:        if ((a->flags & IA_SECONDARY) ||
                   1221:            (a->flags & IA_PEER) ||
                   1222:            (a->scope <= SCOPE_LINK))
                   1223:          continue;
                   1224: 
                   1225:        np = (a->flags & IA_HOST) ? 3 : (ifa->stub ? 2 : 1);
                   1226:        if (np > cur_np)
                   1227:        {
                   1228:          cur_addr = a;
                   1229:          cur_np = np;
                   1230:        }
                   1231:       }
                   1232:     }
                   1233:   }
                   1234: 
                   1235:   return cur_addr ? cur_addr->ip : IPA_NONE;
                   1236: }
                   1237: 
                   1238: void
                   1239: ospf_rt_notify(struct proto *P, rtable *tbl UNUSED, net *n, rte *new, rte *old UNUSED, ea_list *ea)
                   1240: {
                   1241:   struct ospf_proto *p = (struct ospf_proto *) P;
                   1242:   struct ospf_area *oa = NULL; /* non-NULL for NSSA-LSA */
                   1243:   ort *nf;
                   1244: 
                   1245:   /*
                   1246:    * There are several posibilities:
                   1247:    * 1) router in regular area - originate external LSA with global scope
                   1248:    * 2) router in NSSA area - originate area-specific NSSA-LSA
                   1249:    * 3) router in stub area - cannot export routes
                   1250:    * 4) area border router - same as (1), it is attached to backbone
                   1251:    */
                   1252: 
                   1253:   if ((p->areano == 1) && oa_is_nssa(HEAD(p->area_list)))
                   1254:     oa = HEAD(p->area_list);
                   1255: 
                   1256:   if (!new)
                   1257:   {
                   1258:     nf = (ort *) fib_find(&p->rtf, &n->n.prefix, n->n.pxlen);
                   1259: 
                   1260:     if (!nf || !nf->external_rte)
                   1261:       return;
                   1262: 
                   1263:     ospf_flush_ext_lsa(p, oa, nf);
                   1264:     nf->external_rte = 0;
                   1265: 
                   1266:     /* Old external route might blocked some NSSA translation */
                   1267:     if ((p->areano > 1) && rt_is_nssa(nf) && nf->n.oa->translate)
                   1268:       ospf_schedule_rtcalc(p);
                   1269: 
                   1270:     return;
                   1271:   }
                   1272: 
                   1273:   ASSERT(p->asbr);
                   1274: 
                   1275:   /* Get route attributes */
                   1276:   rta *a = new->attrs;
                   1277:   u32 m1 = ea_get_int(ea, EA_OSPF_METRIC1, LSINFINITY);
                   1278:   u32 m2 = ea_get_int(ea, EA_OSPF_METRIC2, 10000);
                   1279:   int ebit = (m1 == LSINFINITY);
                   1280:   u32 metric = ebit ? m2 : m1;
                   1281:   u32 tag = ea_get_int(ea, EA_OSPF_TAG, 0);
                   1282:   ip_addr fwd = IPA_NONE;
                   1283: 
                   1284: 
                   1285:   if ((a->dest == RTD_ROUTER) && use_gw_for_fwaddr(p, a->gw, a->iface))
                   1286:     fwd = a->gw;
                   1287: 
                   1288:   /* NSSA-LSA with P-bit set must have non-zero forwarding address */
                   1289:   if (oa && ipa_zero(fwd))
                   1290:   {
                   1291:     fwd = find_surrogate_fwaddr(p, oa);
                   1292: 
                   1293:     if (ipa_zero(fwd))
                   1294:     {
                   1295:       log(L_ERR "%s: Cannot find forwarding address for NSSA-LSA %I/%d",
                   1296:          p->p.name, n->n.prefix, n->n.pxlen);
                   1297:       return;
                   1298:     }
                   1299:   }
                   1300: 
                   1301:   nf = (ort *) fib_get(&p->rtf, &n->n.prefix, n->n.pxlen);
                   1302:   ospf_originate_ext_lsa(p, oa, nf, LSA_M_EXPORT, metric, ebit, fwd, tag, 1);
                   1303:   nf->external_rte = 1;
                   1304: }
                   1305: 
                   1306: 
                   1307: /*
                   1308:  *     Link-LSA handling (assume OSPFv3)
                   1309:  *     Type = LSA_T_LINK
                   1310:  */
                   1311: 
                   1312: static inline void
                   1313: lsab_put_prefix(struct ospf_proto *p, ip_addr prefix, u32 pxlen, u32 cost)
                   1314: {
                   1315:   void *buf = lsab_alloc(p, IPV6_PREFIX_SPACE(pxlen));
                   1316:   u8 flags = (pxlen < MAX_PREFIX_LENGTH) ? 0 : OPT_PX_LA;
                   1317:   put_ipv6_prefix(buf, prefix, pxlen, flags, cost);
                   1318: }
                   1319: 
                   1320: static void
                   1321: prepare_link_lsa_body(struct ospf_proto *p, struct ospf_iface *ifa)
                   1322: {
                   1323:   struct ospf_lsa_link *ll;
                   1324:   int i = 0;
                   1325: 
                   1326:   ASSERT(p->lsab_used == 0);
                   1327:   ll = lsab_allocz(p, sizeof(struct ospf_lsa_link));
                   1328:   ll->options = ifa->oa->options | (ifa->priority << 24);
                   1329:   ll->lladdr = ipa_to_ip6(ifa->addr->ip);
                   1330:   ll = NULL; /* buffer might be reallocated later */
                   1331: 
                   1332:   struct ifa *a;
                   1333:   WALK_LIST(a, ifa->iface->addrs)
                   1334:   {
                   1335:     if ((a->flags & IA_SECONDARY) ||
                   1336:        (a->scope < SCOPE_SITE))
                   1337:       continue;
                   1338: 
                   1339:     lsab_put_prefix(p, a->prefix, a->pxlen, 0);
                   1340:     i++;
                   1341:   }
                   1342: 
                   1343:   ll = p->lsab;
                   1344:   ll->pxcount = i;
                   1345: }
                   1346: 
                   1347: static void
                   1348: ospf_originate_link_lsa(struct ospf_proto *p, struct ospf_iface *ifa)
                   1349: {
                   1350:   if (ospf_is_v2(p))
                   1351:     return;
                   1352: 
                   1353:   struct ospf_new_lsa lsa = {
                   1354:     .type = LSA_T_LINK,
                   1355:     .dom  = ifa->iface_id,
                   1356:     .id   = ifa->iface_id,
                   1357:     .ifa  = ifa
                   1358:   };
                   1359: 
                   1360:   OSPF_TRACE(D_EVENTS, "Updating link state for %s (Id: %R)", ifa->ifname, lsa.id);
                   1361: 
                   1362:   prepare_link_lsa_body(p, ifa);
                   1363: 
                   1364:   ifa->link_lsa = ospf_originate_lsa(p, &lsa);
                   1365: }
                   1366: 
                   1367: 
                   1368: /*
                   1369:  *     Prefix-Rt-LSA handling (assume OSPFv3)
                   1370:  *     Type = LSA_T_PREFIX, referred type = LSA_T_RT
                   1371:  */
                   1372: 
                   1373: static void
                   1374: prepare_prefix_rt_lsa_body(struct ospf_proto *p, struct ospf_area *oa)
                   1375: {
                   1376:   struct ospf_config *cf = (struct ospf_config *) (p->p.cf);
                   1377:   struct ospf_iface *ifa;
                   1378:   struct ospf_lsa_prefix *lp;
                   1379:   int host_addr = 0;
                   1380:   int net_lsa;
                   1381:   int i = 0;
                   1382: 
                   1383:   ASSERT(p->lsab_used == 0);
                   1384:   lp = lsab_allocz(p, sizeof(struct ospf_lsa_prefix));
                   1385:   lp->ref_type = LSA_T_RT;
                   1386:   lp->ref_id = 0;
                   1387:   lp->ref_rt = p->router_id;
                   1388:   lp = NULL; /* buffer might be reallocated later */
                   1389: 
                   1390:   WALK_LIST(ifa, p->iface_list)
                   1391:   {
                   1392:     if ((ifa->oa != oa) || (ifa->type == OSPF_IT_VLINK) || (ifa->state == OSPF_IS_DOWN))
                   1393:       continue;
                   1394: 
                   1395:     ifa->px_pos_beg = i;
                   1396: 
                   1397:     if ((ifa->type == OSPF_IT_BCAST) ||
                   1398:        (ifa->type == OSPF_IT_NBMA))
                   1399:       net_lsa = bcast_net_active(ifa);
                   1400:     else
                   1401:       net_lsa = 0;
                   1402: 
                   1403:     struct ifa *a;
                   1404:     WALK_LIST(a, ifa->iface->addrs)
                   1405:     {
                   1406:       if ((a->flags & IA_SECONDARY) ||
                   1407:          (a->flags & IA_PEER) ||
                   1408:          (a->scope <= SCOPE_LINK))
                   1409:        continue;
                   1410: 
                   1411:       if (((a->pxlen < MAX_PREFIX_LENGTH) && net_lsa) ||
                   1412:          configured_stubnet(oa, a))
                   1413:        continue;
                   1414: 
                   1415:       if ((a->flags & IA_HOST) ||
                   1416:          (ifa->state == OSPF_IS_LOOP) ||
                   1417:          (ifa->type == OSPF_IT_PTMP))
                   1418:       {
                   1419:        lsab_put_prefix(p, a->ip, MAX_PREFIX_LENGTH, 0);
                   1420:        host_addr = 1;
                   1421:       }
                   1422:       else
                   1423:        lsab_put_prefix(p, a->prefix, a->pxlen, ifa->cost);
                   1424:       i++;
                   1425:     }
                   1426: 
                   1427:     ifa->px_pos_end = i;
                   1428:   }
                   1429: 
                   1430:   struct ospf_stubnet_config *sn;
                   1431:   WALK_LIST(sn, oa->ac->stubnet_list)
                   1432:     if (!sn->hidden)
                   1433:     {
                   1434:       lsab_put_prefix(p, sn->px.addr, sn->px.len, sn->cost);
                   1435:       if (sn->px.len == MAX_PREFIX_LENGTH)
                   1436:        host_addr = 1;
                   1437:       i++;
                   1438:     }
                   1439: 
                   1440:   /* If there are some configured vlinks, find some global address
                   1441:      (even from another area), which will be used as a vlink endpoint. */
                   1442:   if (!EMPTY_LIST(cf->vlink_list) && !host_addr)
                   1443:   {
                   1444:     WALK_LIST(ifa, p->iface_list)
                   1445:     {
                   1446:       if ((ifa->type == OSPF_IT_VLINK) || (ifa->state == OSPF_IS_DOWN))
                   1447:        continue;
                   1448: 
                   1449:       struct ifa *a;
                   1450:       WALK_LIST(a, ifa->iface->addrs)
                   1451:       {
                   1452:        if ((a->flags & IA_SECONDARY) || (a->scope <= SCOPE_LINK))
                   1453:          continue;
                   1454: 
                   1455:        /* Found some IP */
                   1456:        lsab_put_prefix(p, a->ip, MAX_PREFIX_LENGTH, 0);
                   1457:        i++;
                   1458:        goto done;
                   1459:       }
                   1460:     }
                   1461:   }
                   1462: 
                   1463:  done:
                   1464:   lp = p->lsab;
                   1465:   lp->pxcount = i;
                   1466: }
                   1467: 
                   1468: static void
                   1469: ospf_originate_prefix_rt_lsa(struct ospf_proto *p, struct ospf_area *oa)
                   1470: {
                   1471:   if (ospf_is_v2(p))
                   1472:     return;
                   1473: 
                   1474:   struct ospf_new_lsa lsa = {
                   1475:     .type = LSA_T_PREFIX,
                   1476:     .dom  = oa->areaid,
                   1477:     .id   = 0
                   1478:   };
                   1479: 
                   1480:   prepare_prefix_rt_lsa_body(p, oa);
                   1481: 
                   1482:   ospf_originate_lsa(p, &lsa);
                   1483: }
                   1484: 
                   1485: 
                   1486: /*
                   1487:  *     Prefix-Net-LSA handling (assume OSPFv3)
                   1488:  *     Type = LSA_T_PREFIX, referred type = LSA_T_NET
                   1489:  */
                   1490: 
                   1491: static inline int
                   1492: prefix_space(u32 *buf)
                   1493: {
                   1494:   int pxl = *buf >> 24;
                   1495:   return IPV6_PREFIX_SPACE(pxl);
                   1496: }
                   1497: 
                   1498: static inline int
                   1499: prefix_same(u32 *b1, u32 *b2)
                   1500: {
                   1501:   int pxl1 = *b1 >> 24;
                   1502:   int pxl2 = *b2 >> 24;
                   1503:   int pxs, i;
                   1504: 
                   1505:   if (pxl1 != pxl2)
                   1506:     return 0;
                   1507: 
                   1508:   pxs = IPV6_PREFIX_WORDS(pxl1);
                   1509:   for (i = 1; i < pxs; i++)
                   1510:     if (b1[i] != b2[i])
                   1511:       return 0;
                   1512: 
                   1513:   return 1;
                   1514: }
                   1515: 
                   1516: static inline u32 *
                   1517: prefix_advance(u32 *buf)
                   1518: {
                   1519:   int pxl = *buf >> 24;
                   1520:   return buf + IPV6_PREFIX_WORDS(pxl);
                   1521: }
                   1522: 
                   1523: /* FIXME eliminate items with LA bit set? see 4.4.3.9 */
                   1524: static void
                   1525: add_prefix(struct ospf_proto *p, u32 *px, int offset, int *pxc)
                   1526: {
                   1527:   u32 *pxl = lsab_offset(p, offset);
                   1528:   int i;
                   1529:   for (i = 0; i < *pxc; pxl = prefix_advance(pxl), i++)
                   1530:     if (prefix_same(px, pxl))
                   1531:     {
                   1532:       /* Options should be logically OR'ed together */
                   1533:       *pxl |= (*px & 0x00FF0000);
                   1534:       return;
                   1535:     }
                   1536: 
                   1537:   ASSERT(pxl == lsab_end(p));
                   1538: 
                   1539:   int pxspace = prefix_space(px);
                   1540:   pxl = lsab_alloc(p, pxspace);
                   1541:   memcpy(pxl, px, pxspace);
                   1542:   *pxl &= 0xFFFF0000;  /* Set metric to zero */
                   1543:   (*pxc)++;
                   1544: }
                   1545: 
                   1546: static void
                   1547: add_link_lsa(struct ospf_proto *p, struct ospf_lsa_link *ll, int offset, int *pxc)
                   1548: {
                   1549:   u32 *pxb = ll->rest;
                   1550:   uint j;
                   1551: 
                   1552:   for (j = 0; j < ll->pxcount; pxb = prefix_advance(pxb), j++)
                   1553:   {
                   1554:     u8 pxlen = (pxb[0] >> 24);
                   1555:     u8 pxopts = (pxb[0] >> 16);
                   1556: 
                   1557:     /* Skip NU or LA prefixes */
                   1558:     if (pxopts & (OPT_PX_NU | OPT_PX_LA))
                   1559:       continue;
                   1560: 
                   1561:     /* Skip link-local prefixes */
                   1562:     if ((pxlen >= 10) && ((pxb[1] & 0xffc00000) == 0xfe800000))
                   1563:       continue;
                   1564: 
                   1565:     add_prefix(p, pxb, offset, pxc);
                   1566:   }
                   1567: }
                   1568: 
                   1569: static void
                   1570: prepare_prefix_net_lsa_body(struct ospf_proto *p, struct ospf_iface *ifa)
                   1571: {
                   1572:   struct ospf_lsa_prefix *lp;
                   1573:   struct ospf_neighbor *n;
                   1574:   struct top_hash_entry *en;
                   1575:   int pxc, offset;
                   1576: 
                   1577:   ASSERT(p->lsab_used == 0);
                   1578:   lp = lsab_allocz(p, sizeof(struct ospf_lsa_prefix));
                   1579:   lp->ref_type = LSA_T_NET;
                   1580:   lp->ref_id = ifa->net_lsa->lsa.id;
                   1581:   lp->ref_rt = p->router_id;
                   1582:   lp = NULL; /* buffer might be reallocated later */
                   1583: 
                   1584:   pxc = 0;
                   1585:   offset = p->lsab_used;
                   1586: 
                   1587:   /* Find all Link LSAs associated with the link and merge their prefixes */
                   1588:   if (en = ifa->link_lsa)
                   1589:     add_link_lsa(p, en->next_lsa_body ?: en->lsa_body, offset, &pxc);
                   1590: 
                   1591:   WALK_LIST(n, ifa->neigh_list)
                   1592:     if ((n->state == NEIGHBOR_FULL) &&
                   1593:        (en = ospf_hash_find(p->gr, ifa->iface_id, n->iface_id, n->rid, LSA_T_LINK)))
                   1594:       add_link_lsa(p, en->lsa_body, offset, &pxc);
                   1595: 
                   1596:   lp = p->lsab;
                   1597:   lp->pxcount = pxc;
                   1598: }
                   1599: 
                   1600: static void
                   1601: ospf_originate_prefix_net_lsa(struct ospf_proto *p, struct ospf_iface *ifa)
                   1602: {
                   1603:   if (ospf_is_v2(p))
                   1604:     return;
                   1605: 
                   1606:   struct ospf_new_lsa lsa = {
                   1607:     .type = LSA_T_PREFIX,
                   1608:     .dom  = ifa->oa->areaid,
                   1609:     .id   = ifa->iface_id,
                   1610:     .ifa  = ifa
                   1611:   };
                   1612: 
                   1613:   prepare_prefix_net_lsa_body(p, ifa);
                   1614: 
                   1615:   ifa->pxn_lsa = ospf_originate_lsa(p, &lsa);
                   1616: }
                   1617: 
                   1618: static inline int breaks_minlsinterval(struct top_hash_entry *en)
                   1619: { return en && (en->lsa.age < LSA_MAXAGE) && ((en->inst_time + MINLSINTERVAL) > now); }
                   1620: 
                   1621: void
                   1622: ospf_update_topology(struct ospf_proto *p)
                   1623: {
                   1624:   struct ospf_area *oa;
                   1625:   struct ospf_iface *ifa;
                   1626: 
                   1627:   WALK_LIST(oa, p->area_list)
                   1628:   {
                   1629:     if (oa->update_rt_lsa)
                   1630:     {
                   1631:       /*
                   1632:        * Generally, MinLSInterval is enforced in ospf_do_originate_lsa(), but
                   1633:        * origination of (prefix) router LSA is a special case. We do not want to
                   1634:        * prepare a new router LSA body and then postpone it in en->next_lsa_body
                   1635:        * for later origination, because there are side effects (updates of
                   1636:        * rt_pos_* and px_pos_* in ospf_iface structures) during that, which may
                   1637:        * confuse routing table calculation if executed after LSA body
                   1638:        * preparation but before final LSA origination (as rtcalc would use
                   1639:        * current rt_pos_* indexes but the old router LSA body).
                   1640:        *
                   1641:        * Here, we ensure that MinLSInterval is observed and we do not even try
                   1642:        * to originate these LSAs if it is not. Therefore, origination, when
                   1643:        * requested, will succeed unless there is also a seqnum wrapping, which
                   1644:        * is not a problem because in that case rtcalc is blocked by MaxAge.
                   1645:        */
                   1646: 
                   1647:       if (breaks_minlsinterval(oa->rt) || breaks_minlsinterval(oa->pxr_lsa))
                   1648:        continue;
                   1649: 
                   1650:       ospf_originate_rt_lsa(p, oa);
                   1651:       ospf_originate_prefix_rt_lsa(p, oa);
                   1652:       oa->update_rt_lsa = 0;
                   1653:     }
                   1654:   }
                   1655: 
                   1656:   WALK_LIST(ifa, p->iface_list)
                   1657:   {
                   1658:     if (ifa->type == OSPF_IT_VLINK)
                   1659:       continue;
                   1660: 
                   1661:     if (ifa->update_link_lsa)
                   1662:     {
                   1663:       if ((ifa->state > OSPF_IS_LOOP) && !ifa->link_lsa_suppression)
                   1664:        ospf_originate_link_lsa(p, ifa);
                   1665:       else
                   1666:        ospf_flush2_lsa(p, &ifa->link_lsa);
                   1667: 
                   1668:       ifa->update_link_lsa = 0;
                   1669:     }
                   1670: 
                   1671:     if (ifa->update_net_lsa)
                   1672:     {
                   1673:       if ((ifa->state == OSPF_IS_DR) && (ifa->fadj > 0))
                   1674:       {
                   1675:        ospf_originate_net_lsa(p, ifa);
                   1676:        ospf_originate_prefix_net_lsa(p, ifa);
                   1677:       }
                   1678:       else
                   1679:       {
                   1680:        ospf_flush2_lsa(p, &ifa->net_lsa);
                   1681:        ospf_flush2_lsa(p, &ifa->pxn_lsa);
                   1682:       }
                   1683: 
                   1684:       ifa->update_net_lsa = 0;
                   1685:     }
                   1686:   }
                   1687: }
                   1688: 
                   1689: 
                   1690: static void
                   1691: ospf_top_ht_alloc(struct top_graph *f)
                   1692: {
                   1693:   f->hash_size = 1 << f->hash_order;
                   1694:   f->hash_mask = f->hash_size - 1;
                   1695:   if (f->hash_order > HASH_HI_MAX - HASH_HI_STEP)
                   1696:     f->hash_entries_max = ~0;
                   1697:   else
                   1698:     f->hash_entries_max = f->hash_size HASH_HI_MARK;
                   1699:   if (f->hash_order < HASH_LO_MIN + HASH_LO_STEP)
                   1700:     f->hash_entries_min = 0;
                   1701:   else
                   1702:     f->hash_entries_min = f->hash_size HASH_LO_MARK;
                   1703:   DBG("Allocating OSPF hash of order %d: %d hash_entries, %d low, %d high\n",
                   1704:       f->hash_order, f->hash_size, f->hash_entries_min, f->hash_entries_max);
                   1705:   f->hash_table =
                   1706:     mb_alloc(f->pool, f->hash_size * sizeof(struct top_hash_entry *));
                   1707:   bzero(f->hash_table, f->hash_size * sizeof(struct top_hash_entry *));
                   1708: }
                   1709: 
                   1710: static inline void
                   1711: ospf_top_ht_free(struct top_hash_entry **h)
                   1712: {
                   1713:   mb_free(h);
                   1714: }
                   1715: 
                   1716: static inline u32
                   1717: ospf_top_hash_u32(u32 a)
                   1718: {
                   1719:   /* Shamelessly stolen from IP address hashing in ipv4.h */
                   1720:   a ^= a >> 16;
                   1721:   a ^= a << 10;
                   1722:   return a;
                   1723: }
                   1724: 
                   1725: static uint
                   1726: ospf_top_hash(struct top_graph *f, u32 domain, u32 lsaid, u32 rtrid, u32 type)
                   1727: {
                   1728:   /* In OSPFv2, we don't know Router ID when looking for network LSAs.
                   1729:      In OSPFv3, we don't know LSA ID when looking for router LSAs.
                   1730:      In both cases, there is (usually) just one (or small number)
                   1731:      appropriate LSA, so we just clear unknown part of key. */
                   1732: 
                   1733:   return (((f->ospf2 && (type == LSA_T_NET)) ? 0 : ospf_top_hash_u32(rtrid)) +
                   1734:          ((!f->ospf2 && (type == LSA_T_RT)) ? 0 : ospf_top_hash_u32(lsaid)) +
                   1735:          type + domain) & f->hash_mask;
                   1736: 
                   1737:   /*
                   1738:   return (ospf_top_hash_u32(lsaid) + ospf_top_hash_u32(rtrid) +
                   1739:          type + areaid) & f->hash_mask;
                   1740:   */
                   1741: }
                   1742: 
                   1743: /**
                   1744:  * ospf_top_new - allocated new topology database
                   1745:  * @p: OSPF protocol instance
                   1746:  * @pool: pool for allocation
                   1747:  *
                   1748:  * This dynamically hashed structure is used for keeping LSAs. Mainly it is used
                   1749:  * for the LSA database of the OSPF protocol, but also for LSA retransmission
                   1750:  * and request lists of OSPF neighbors.
                   1751:  */
                   1752: struct top_graph *
                   1753: ospf_top_new(struct ospf_proto *p UNUSED4 UNUSED6, pool *pool)
                   1754: {
                   1755:   struct top_graph *f;
                   1756: 
                   1757:   f = mb_allocz(pool, sizeof(struct top_graph));
                   1758:   f->pool = pool;
                   1759:   f->hash_slab = sl_new(f->pool, sizeof(struct top_hash_entry));
                   1760:   f->hash_order = HASH_DEF_ORDER;
                   1761:   ospf_top_ht_alloc(f);
                   1762:   f->hash_entries = 0;
                   1763:   f->hash_entries_min = 0;
                   1764:   f->ospf2 = ospf_is_v2(p);
                   1765:   return f;
                   1766: }
                   1767: 
                   1768: void
                   1769: ospf_top_free(struct top_graph *f)
                   1770: {
                   1771:   rfree(f->hash_slab);
                   1772:   ospf_top_ht_free(f->hash_table);
                   1773:   mb_free(f);
                   1774: }
                   1775: 
                   1776: static void
                   1777: ospf_top_rehash(struct top_graph *f, int step)
                   1778: {
                   1779:   struct top_hash_entry **n, **oldt, **newt, *e, *x;
                   1780:   uint oldn, oldh;
                   1781: 
                   1782:   oldn = f->hash_size;
                   1783:   oldt = f->hash_table;
                   1784:   DBG("re-hashing topology hash from order %d to %d\n", f->hash_order,
                   1785:       f->hash_order + step);
                   1786:   f->hash_order += step;
                   1787:   ospf_top_ht_alloc(f);
                   1788:   newt = f->hash_table;
                   1789: 
                   1790:   for (oldh = 0; oldh < oldn; oldh++)
                   1791:   {
                   1792:     e = oldt[oldh];
                   1793:     while (e)
                   1794:     {
                   1795:       x = e->next;
                   1796:       n = newt + ospf_top_hash(f, e->domain, e->lsa.id, e->lsa.rt, e->lsa_type);
                   1797:       e->next = *n;
                   1798:       *n = e;
                   1799:       e = x;
                   1800:     }
                   1801:   }
                   1802:   ospf_top_ht_free(oldt);
                   1803: }
                   1804: 
                   1805: static struct top_hash_entry *
                   1806: ospf_hash_find_(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type)
                   1807: {
                   1808:   struct top_hash_entry *e;
                   1809:   e = f->hash_table[ospf_top_hash(f, domain, lsa, rtr, type)];
                   1810: 
                   1811:   while (e && (e->lsa.id != lsa || e->lsa.rt != rtr ||
                   1812:               e->lsa_type != type || e->domain != domain))
                   1813:     e = e->next;
                   1814: 
                   1815:   return e;
                   1816: }
                   1817: 
                   1818: struct top_hash_entry *
                   1819: ospf_hash_find(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type)
                   1820: {
                   1821:   struct top_hash_entry *e = ospf_hash_find_(f, domain, lsa, rtr, type);
                   1822: 
                   1823:   /* Hide hash entry with empty lsa_body */
                   1824:   return (e && e->lsa_body) ? e : NULL;
                   1825: }
                   1826: 
                   1827: /* In OSPFv2, lsa.id is the same as lsa.rt for router LSA. In OSPFv3, we don't know
                   1828:    lsa.id when looking for router LSAs. We return matching LSA with smallest lsa.id. */
                   1829: struct top_hash_entry *
                   1830: ospf_hash_find_rt(struct top_graph *f, u32 domain, u32 rtr)
                   1831: {
                   1832:   struct top_hash_entry *rv = NULL;
                   1833:   struct top_hash_entry *e;
                   1834:   /* We can put rtr for lsa.id to hash fn, it is ignored in OSPFv3 */
                   1835:   e = f->hash_table[ospf_top_hash(f, domain, rtr, rtr, LSA_T_RT)];
                   1836: 
                   1837:   while (e)
                   1838:   {
                   1839:     if (e->lsa.rt == rtr && e->lsa_type == LSA_T_RT && e->domain == domain && e->lsa_body)
                   1840:     {
                   1841:       if (f->ospf2 && (e->lsa.id == rtr))
                   1842:        return e;
                   1843:       if (!f->ospf2 && (!rv || e->lsa.id < rv->lsa.id))
                   1844:        rv = e;
                   1845:     }
                   1846:     e = e->next;
                   1847:   }
                   1848: 
                   1849:   return rv;
                   1850: }
                   1851: 
                   1852: /*
                   1853:  * ospf_hash_find_rt3_first() and ospf_hash_find_rt3_next() are used exclusively
                   1854:  * for lsa_walk_rt_init(), lsa_walk_rt(), therefore they skip MaxAge entries.
                   1855:  */
                   1856: static inline struct top_hash_entry *
                   1857: find_matching_rt3(struct top_hash_entry *e, u32 domain, u32 rtr)
                   1858: {
                   1859:   while (e && (e->lsa.rt != rtr || e->lsa_type != LSA_T_RT ||
                   1860:               e->domain != domain || e->lsa.age == LSA_MAXAGE))
                   1861:     e = e->next;
                   1862:   return e;
                   1863: }
                   1864: 
                   1865: struct top_hash_entry *
                   1866: ospf_hash_find_rt3_first(struct top_graph *f, u32 domain, u32 rtr)
                   1867: {
                   1868:   struct top_hash_entry *e;
                   1869:   e = f->hash_table[ospf_top_hash(f, domain, 0, rtr, LSA_T_RT)];
                   1870:   return find_matching_rt3(e, domain, rtr);
                   1871: }
                   1872: 
                   1873: struct top_hash_entry *
                   1874: ospf_hash_find_rt3_next(struct top_hash_entry *e)
                   1875: {
                   1876:   return find_matching_rt3(e->next, e->domain, e->lsa.rt);
                   1877: }
                   1878: 
                   1879: /* In OSPFv2, we don't know Router ID when looking for network LSAs.
                   1880:    There should be just one, so we find any match. */
                   1881: struct top_hash_entry *
                   1882: ospf_hash_find_net2(struct top_graph *f, u32 domain, u32 id)
                   1883: {
                   1884:   struct top_hash_entry *e;
                   1885:   e = f->hash_table[ospf_top_hash(f, domain, id, 0, LSA_T_NET)];
                   1886: 
                   1887:   while (e && (e->lsa.id != id || e->lsa_type != LSA_T_NET ||
                   1888:               e->domain != domain || e->lsa_body == NULL))
                   1889:     e = e->next;
                   1890: 
                   1891:   return e;
                   1892: }
                   1893: 
                   1894: 
                   1895: struct top_hash_entry *
                   1896: ospf_hash_get(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type)
                   1897: {
                   1898:   struct top_hash_entry **ee;
                   1899:   struct top_hash_entry *e;
                   1900: 
                   1901:   ee = f->hash_table + ospf_top_hash(f, domain, lsa, rtr, type);
                   1902:   e = *ee;
                   1903: 
                   1904:   while (e && (e->lsa.id != lsa || e->lsa.rt != rtr ||
                   1905:               e->lsa_type != type || e->domain != domain))
                   1906:     e = e->next;
                   1907: 
                   1908:   if (e)
                   1909:     return e;
                   1910: 
                   1911:   e = sl_alloc(f->hash_slab);
                   1912:   bzero(e, sizeof(struct top_hash_entry));
                   1913: 
                   1914:   e->color = OUTSPF;
                   1915:   e->dist = LSINFINITY;
                   1916:   e->lsa.type_raw = type;
                   1917:   e->lsa.id = lsa;
                   1918:   e->lsa.rt = rtr;
                   1919:   e->lsa.sn = LSA_ZEROSEQNO;
                   1920:   e->lsa_type = type;
                   1921:   e->domain = domain;
                   1922:   e->next = *ee;
                   1923:   *ee = e;
                   1924:   if (f->hash_entries++ > f->hash_entries_max)
                   1925:     ospf_top_rehash(f, HASH_HI_STEP);
                   1926:   return e;
                   1927: }
                   1928: 
                   1929: void
                   1930: ospf_hash_delete(struct top_graph *f, struct top_hash_entry *e)
                   1931: {
                   1932:   struct top_hash_entry **ee = f->hash_table +
                   1933:     ospf_top_hash(f, e->domain, e->lsa.id, e->lsa.rt, e->lsa_type);
                   1934: 
                   1935:   while (*ee)
                   1936:   {
                   1937:     if (*ee == e)
                   1938:     {
                   1939:       *ee = e->next;
                   1940:       sl_free(f->hash_slab, e);
                   1941:       if (f->hash_entries-- < f->hash_entries_min)
                   1942:        ospf_top_rehash(f, -HASH_LO_STEP);
                   1943:       return;
                   1944:     }
                   1945:     ee = &((*ee)->next);
                   1946:   }
                   1947:   bug("ospf_hash_delete() called for invalid node");
                   1948: }
                   1949: 
                   1950: /*
                   1951: static void
                   1952: ospf_dump_lsa(struct top_hash_entry *he, struct proto *p)
                   1953: {
                   1954: 
                   1955:   struct ospf_lsa_rt *rt = NULL;
                   1956:   struct ospf_lsa_rt_link *rr = NULL;
                   1957:   struct ospf_lsa_net *ln = NULL;
                   1958:   u32 *rts = NULL;
                   1959:   u32 i, max;
                   1960: 
                   1961:   OSPF_TRACE(D_EVENTS, "- %1x %-1R %-1R %4u 0x%08x 0x%04x %-1R",
                   1962:             he->lsa.type, he->lsa.id, he->lsa.rt, he->lsa.age, he->lsa.sn,
                   1963:             he->lsa.checksum, he->domain);
                   1964: 
                   1965: 
                   1966:   switch (he->lsa.type)
                   1967:     {
                   1968:     case LSA_T_RT:
                   1969:       rt = he->lsa_body;
                   1970:       rr = (struct ospf_lsa_rt_link *) (rt + 1);
                   1971: 
                   1972:       for (i = 0; i < lsa_rt_items(&he->lsa); i++)
                   1973:        OSPF_TRACE(D_EVENTS, "  - %1x %-1R %-1R %5u",
                   1974:                   rr[i].type, rr[i].id, rr[i].data, rr[i].metric);
                   1975:       break;
                   1976: 
                   1977:     case LSA_T_NET:
                   1978:       ln = he->lsa_body;
                   1979:       rts = (u32 *) (ln + 1);
                   1980: 
                   1981:       for (i = 0; i < lsa_net_items(&he->lsa); i++)
                   1982:        OSPF_TRACE(D_EVENTS, "  - %-1R", rts[i]);
                   1983:       break;
                   1984: 
                   1985:     default:
                   1986:       break;
                   1987:     }
                   1988: }
                   1989: 
                   1990: void
                   1991: ospf_top_dump(struct top_graph *f, struct proto *p)
                   1992: {
                   1993:   uint i;
                   1994:   OSPF_TRACE(D_EVENTS, "Hash entries: %d", f->hash_entries);
                   1995: 
                   1996:   for (i = 0; i < f->hash_size; i++)
                   1997:   {
                   1998:     struct top_hash_entry *e;
                   1999:     for (e = f->hash_table[i]; e != NULL; e = e->next)
                   2000:       ospf_dump_lsa(e, p);
                   2001:   }
                   2002: }
                   2003: */

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>