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

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

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