Annotation of embedaddon/bird/proto/ospf/topology.c, revision 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>