diff options
Diffstat (limited to 'proto/ospf/topology.c')
| -rw-r--r-- | proto/ospf/topology.c | 2372 |
1 files changed, 1230 insertions, 1142 deletions
diff --git a/proto/ospf/topology.c b/proto/ospf/topology.c index 4af5afa5..0613d34d 100644 --- a/proto/ospf/topology.c +++ b/proto/ospf/topology.c @@ -3,6 +3,8 @@ * * (c) 1999 Martin Mares <mj@ucw.cz> * (c) 1999--2004 Ondrej Filip <feela@network.cz> + * (c) 2009--2014 Ondrej Zajicek <santiago@crfreenet.org> + * (c) 2009--2014 CZ.NIC z.s.p.o. * * Can be freely distributed and used under the terms of the GNU GPL. */ @@ -12,6 +14,7 @@ #include "ospf.h" + #define HASH_DEF_ORDER 6 #define HASH_HI_MARK *4 #define HASH_HI_STEP 2 @@ -20,166 +23,625 @@ #define HASH_LO_STEP 2 #define HASH_LO_MIN 8 -void originate_prefix_rt_lsa(struct ospf_area *oa); -void originate_prefix_net_lsa(struct ospf_iface *ifa); -void flush_prefix_net_lsa(struct ospf_iface *ifa); +static inline void * lsab_flush(struct ospf_proto *p); +static inline void lsab_reset(struct ospf_proto *p); + -#ifdef OSPFv2 -#define ipa_to_rid(x) _I(x) -#else /* OSPFv3 */ -#define ipa_to_rid(x) _I3(x) -#endif +/** + * ospf_install_lsa - install new LSA into database + * @p: OSPF protocol instance + * @lsa: LSA header + * @type: type of LSA + * @domain: domain of LSA + * @body: pointer to LSA body + * + * This function ensures installing new LSA received in LS update into LSA + * database. Old instance is replaced. Several actions are taken to detect if + * new routing table calculation is necessary. This is described in 13.2 of RFC + * 2328. This function is for received LSA only, locally originated LSAs are + * installed by ospf_originate_lsa(). + * + * The LSA body in @body is expected to be mb_allocated by the caller and its + * ownership is transferred to the LSA entry structure. + */ +struct top_hash_entry * +ospf_install_lsa(struct ospf_proto *p, struct ospf_lsa_header *lsa, u32 type, u32 domain, void *body) +{ + struct top_hash_entry *en; + int change = 0; + en = ospf_hash_get(p->gr, domain, lsa->id, lsa->rt, type); -#ifdef OSPFv2 -static inline u32 -fibnode_to_lsaid(struct proto_ospf *po, struct fib_node *fn) -{ - /* We have to map IP prefixes to u32 in such manner that resulting - u32 interpreted as IP address is a member of given - prefix. Therefore, /32 prefix have to be mapped on itself. - All received prefixes have to be mapped on different u32s. - - We have an assumption that if there is nontrivial (non-/32) - network prefix, then there is not /32 prefix for the first - and the last IP address of the network (these are usually - reserved, therefore it is not an important restriction). - The network prefix is mapped to the first or the last - IP address in the manner that disallow collisions - we - use IP address that cannot be used by parent prefix. - - For example: - 192.168.0.0/24 maps to 192.168.0.255 - 192.168.1.0/24 maps to 192.168.1.0 - because 192.168.0.0 and 192.168.1.255 might be used by - 192.168.0.0/23 . - - This is not compatible with older RFC 1583, so we have an option - to the RFC 1583 compatible assignment (that always uses the first - address) which disallows subnetting. - - Appendig E of RFC 2328 suggests different algorithm, that tries - to maximize both compatibility and subnetting. But as it is not - possible to have both reliably and the suggested algorithm was - unnecessary complicated and it does crazy things like changing - LSA ID for a network because different network appeared, we - choose a different way. */ - - u32 id = _I(fn->prefix); - - if ((po->rfc1583) || (fn->pxlen == 0) || (fn->pxlen == 32)) - return id; + if (!SNODE_VALID(en)) + s_add_tail(&p->lsal, SNODE en); - if (id & (1 << (32 - fn->pxlen))) - return id; + if ((en->lsa_body == NULL) || /* No old LSA */ + (en->lsa.length != lsa->length) || + (en->lsa.type_raw != lsa->type_raw) || /* Check for OSPFv2 options */ + (en->lsa.age == LSA_MAXAGE) || + (lsa->age == LSA_MAXAGE) || + memcmp(en->lsa_body, body, lsa->length - sizeof(struct ospf_lsa_header))) + change = 1; + + if ((en->lsa.age == LSA_MAXAGE) && (lsa->age == LSA_MAXAGE)) + change = 0; + + mb_free(en->lsa_body); + en->lsa_body = body; + en->lsa = *lsa; + en->init_age = en->lsa.age; + en->inst_time = now; + + /* + * We do not set en->mode. It is either default LSA_M_BASIC, or in a special + * case when en is local but flushed, there is postponed LSA, self-originated + * LSA is received and ospf_install_lsa() is called from ospf_advance_lse(), + * then we have en->mode from the postponed LSA origination. + */ + + OSPF_TRACE(D_EVENTS, "Installing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x, Age: %u", + en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn, en->lsa.age); + + if (change) + ospf_schedule_rtcalc(p); + + return en; +} + +/** + * ospf_advance_lsa - handle received unexpected self-originated LSA + * @p: OSPF protocol instance + * @en: current LSA entry or NULL + * @lsa: new LSA header + * @type: type of LSA + * @domain: domain of LSA + * @body: pointer to LSA body + * + * This function handles received unexpected self-originated LSA (@lsa, @body) + * by either advancing sequence number of the local LSA instance (@en) and + * propagating it, or installing the received LSA and immediately flushing it + * (if there is no local LSA; i.e., @en is NULL or MaxAge). + * + * The LSA body in @body is expected to be mb_allocated by the caller and its + * ownership is transferred to the LSA entry structure or it is freed. + */ +void +ospf_advance_lsa(struct ospf_proto *p, struct top_hash_entry *en, struct ospf_lsa_header *lsa, u32 type, u32 domain, void *body) +{ + /* RFC 2328 13.4 */ + + if (en && (en->lsa.age < LSA_MAXAGE)) + { + if (lsa->sn != LSA_MAXSEQNO) + { + /* + * We simply advance current LSA to have higher seqnum than received LSA. + * The received LSA is ignored and the advanced LSA is propagated instead. + * + * Although this is an origination of distinct LSA instance and therefore + * should be limited by MinLSInterval, we do not enforce it here. Fast + * reaction is needed and we are already limited by MinLSArrival. + */ + + mb_free(body); + + en->lsa.sn = lsa->sn + 1; + en->lsa.age = 0; + en->init_age = 0; + en->inst_time = now; + lsasum_calculate(&en->lsa, en->lsa_body); + + OSPF_TRACE(D_EVENTS, "Advancing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x", + en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn); + } + else + { + /* + * Received LSA has maximal sequence number, so we cannot simply override + * it. We have to install it to the database, immediately flush it to + * implement sequence number wrapping, and schedule our current LSA to be + * originated after the received instance is flushed. + */ + + if (en->next_lsa_body == NULL) + { + /* Schedule current LSA */ + en->next_lsa_blen = en->lsa.length - sizeof(struct ospf_lsa_header); + en->next_lsa_body = en->lsa_body; + en->next_lsa_opts = ospf_is_v2(p) ? lsa_get_options(&en->lsa) : 0; + } + else + { + /* There is already scheduled LSA, so we just free current one */ + mb_free(en->lsa_body); + } + + en->lsa_body = body; + en->lsa = *lsa; + en->lsa.age = LSA_MAXAGE; + en->init_age = lsa->age; + en->inst_time = now; + + OSPF_TRACE(D_EVENTS, "Resetting LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x", + en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn); + OSPF_TRACE(D_EVENTS, "Postponing LSA: Type: %04x, Id: %R, Rt: %R", + en->lsa_type, en->lsa.id, en->lsa.rt); + } + } else - return id | ~u32_mkmask(fn->pxlen); + { + /* + * We do not have received LSA in the database. We have to flush the + * received LSA. It has to be installed in the database to secure + * retransmissions. Note that the received LSA may already be MaxAge. + * Also note that en->next_lsa_* may be defined. + */ + + lsa->age = LSA_MAXAGE; + en = ospf_install_lsa(p, lsa, type, domain, body); + } + + /* + * We flood the updated LSA. Although in some cases the to-be-flooded LSA is + * the same as the received LSA, and therefore we should propagate it as + * regular received LSA (send the acknowledgement instead of the update to + * the neighbor we received it from), we cheat a bit here. + */ + + ospf_flood_lsa(p, en, NULL); } -#else /* OSPFv3 */ -static inline u32 -fibnode_to_lsaid(struct proto_ospf *po, struct fib_node *fn) +static int +ospf_do_originate_lsa(struct ospf_proto *p, struct top_hash_entry *en, void *lsa_body, u16 lsa_blen, u16 lsa_opts) { + /* Enforce MinLSInterval */ + if ((en->init_age == 0) && en->inst_time && ((en->inst_time + MINLSINTERVAL) > now)) + return 0; + + /* Handle wrapping sequence number */ + if (en->lsa.sn == LSA_MAXSEQNO) + { + /* Prepare to flush old LSA */ + if (en->lsa.age != LSA_MAXAGE) + { + OSPF_TRACE(D_EVENTS, "Resetting LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x", + en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn); + + en->lsa.age = LSA_MAXAGE; + ospf_flood_lsa(p, en, NULL); + return 0; + } + + /* Already flushing */ + if ((p->padj != 0) || (en->ret_count != 0)) + return 0; + + /* Flush done, just clean up seqnum, lsa_body is freed below */ + en->lsa.sn = LSA_ZEROSEQNO; + } + /* - * In OSPFv3, it is simpler. There is not a requirement for - * membership of the result in the input network, so we just use a - * hash-based unique ID of a routing table entry for a route that - * originated given LSA. For ext-LSA, it is an imported route in the - * nest's routing table (p->table). For summary-LSA, it is a - * 'source' route in the protocol internal routing table (po->rtf). + * lsa.type_raw is initialized by ospf_hash_get() to OSPFv3 LSA type. + * lsa_set_options() implicitly converts it to OSPFv2 LSA type, assuming that + * old type is just new type masked by 0xff. That is not universally true, + * but it holds for all OSPFv2 types currently supported by BIRD. */ - return fn->uid; + + if (ospf_is_v2(p)) + lsa_set_options(&en->lsa, lsa_opts); + + mb_free(en->lsa_body); + en->lsa_body = lsa_body; + en->lsa.length = sizeof(struct ospf_lsa_header) + lsa_blen; + en->lsa.sn++; + en->lsa.age = 0; + en->init_age = 0; + en->inst_time = now; + lsasum_calculate(&en->lsa, en->lsa_body); + + OSPF_TRACE(D_EVENTS, "Originating LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x", + en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn); + + ospf_flood_lsa(p, en, NULL); + + if (en->mode == LSA_M_BASIC) + ospf_schedule_rtcalc(p); + + return 1; } -#endif +/** + * ospf_originate_lsa - originate new LSA + * @p: OSPF protocol instance + * @lsa: New LSA specification + * + * This function prepares a new LSA, installs it into the LSA database and + * floods it. If the new LSA cannot be originated now (because the old instance + * was originated within MinLSInterval, or because the LSA seqnum is currently + * wrapping), the origination is instead scheduled for later. If the new LSA is + * equivalent to the current LSA, the origination is skipped. In all cases, the + * corresponding LSA entry is returned. The new LSA is based on the LSA + * specification (@lsa) and the LSA body from lsab buffer of @p, which is + * emptied after the call. The opposite of this function is ospf_flush_lsa(). + */ +struct top_hash_entry * +ospf_originate_lsa(struct ospf_proto *p, struct ospf_new_lsa *lsa) +{ + struct top_hash_entry *en; + void *lsa_body = p->lsab; + u16 lsa_blen = p->lsab_used; + u16 lsa_length = sizeof(struct ospf_lsa_header) + lsa_blen; + + en = ospf_hash_get(p->gr, lsa->dom, lsa->id, p->router_id, lsa->type); + if (!SNODE_VALID(en)) + s_add_tail(&p->lsal, SNODE en); -static void * -lsab_alloc(struct proto_ospf *po, unsigned size) + if (en->lsa_body == NULL) + en->nf = lsa->nf; + + if (en->nf != lsa->nf) + { + log(L_ERR "%s: LSA ID collision for %I/%d", + p->p.name, lsa->nf->fn.prefix, lsa->nf->fn.pxlen); + + en = NULL; + goto drop; + } + + if (en->mode != lsa->mode) + en->mode = lsa->mode; + + if (en->next_lsa_body) + { + /* Ignore the new LSA if it is the same as the scheduled one */ + if ((lsa_blen == en->next_lsa_blen) && + !memcmp(lsa_body, en->next_lsa_body, lsa_blen) && + (!ospf_is_v2(p) || (lsa->opts == en->next_lsa_opts))) + goto drop; + + /* Free scheduled LSA */ + mb_free(en->next_lsa_body); + en->next_lsa_body = NULL; + en->next_lsa_blen = 0; + en->next_lsa_opts = 0; + } + + /* Ignore the the new LSA if is the same as the current one */ + if ((en->lsa.age < LSA_MAXAGE) && + (lsa_length == en->lsa.length) && + !memcmp(lsa_body, en->lsa_body, lsa_blen) && + (!ospf_is_v2(p) || (lsa->opts == lsa_get_options(&en->lsa)))) + goto drop; + + lsa_body = lsab_flush(p); + + if (! ospf_do_originate_lsa(p, en, lsa_body, lsa_blen, lsa->opts)) + { + OSPF_TRACE(D_EVENTS, "Postponing LSA: Type: %04x, Id: %R, Rt: %R", + en->lsa_type, en->lsa.id, en->lsa.rt); + + en->next_lsa_body = lsa_body; + en->next_lsa_blen = lsa_blen; + en->next_lsa_opts = lsa->opts; + } + + return en; + + drop: + lsab_reset(p); + return en; +} + +static void +ospf_originate_next_lsa(struct ospf_proto *p, struct top_hash_entry *en) +{ + /* Called by ospf_update_lsadb() to handle scheduled origination */ + + if (! ospf_do_originate_lsa(p, en, en->next_lsa_body, en->next_lsa_blen, en->next_lsa_opts)) + return; + + en->next_lsa_body = NULL; + en->next_lsa_blen = 0; + en->next_lsa_opts = 0; +} + +static void +ospf_refresh_lsa(struct ospf_proto *p, struct top_hash_entry *en) +{ + /* + * Called by ospf_update_lsadb() for periodic LSA refresh. + * + * We know that lsa.age < LSA_MAXAGE and lsa.rt is our router ID. We can also + * assume that there is no scheduled LSA, because inst_time is deep in past, + * therefore ospf_originate_next_lsa() called before would either succeed or + * switched lsa.age to LSA_MAXAGE. + */ + + OSPF_TRACE(D_EVENTS, "Refreshing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x", + en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn); + + ASSERT(en->next_lsa_body == NULL); + + /* Handle wrapping sequence number */ + if (en->lsa.sn == LSA_MAXSEQNO) + { + /* Copy LSA body as next LSA to get automatic origination after flush is finished */ + en->next_lsa_blen = en->lsa.length - sizeof(struct ospf_lsa_header); + en->next_lsa_body = mb_alloc(p->p.pool, en->next_lsa_blen); + memcpy(en->next_lsa_body, en->lsa_body, en->next_lsa_blen); + en->next_lsa_opts = ospf_is_v2(p) ? lsa_get_options(&en->lsa) : 0; + + en->lsa.age = LSA_MAXAGE; + ospf_flood_lsa(p, en, NULL); + return; + } + + en->lsa.sn++; + en->lsa.age = 0; + en->init_age = 0; + en->inst_time = now; + lsasum_calculate(&en->lsa, en->lsa_body); + ospf_flood_lsa(p, en, NULL); +} + +/** + * ospf_flush_lsa - flush LSA from OSPF domain + * @p: OSPF protocol instance + * @en: LSA entry to flush + * + * This function flushes @en from the OSPF domain by setting its age to + * %LSA_MAXAGE and flooding it. That also triggers subsequent events in LSA + * lifecycle leading to removal of the LSA from the LSA database (e.g. the LSA + * content is freed when flushing is acknowledged by neighbors). The function + * does nothing if the LSA is already being flushed. LSA entries are not + * immediately removed when being flushed, the caller may assume that @en still + * exists after the call. The function is the opposite of ospf_originate_lsa() + * and is supposed to do the right thing even in cases of postponed + * origination. + */ +void +ospf_flush_lsa(struct ospf_proto *p, struct top_hash_entry *en) { - unsigned offset = po->lsab_used; - po->lsab_used += size; - if (po->lsab_used > po->lsab_size) + if (en->next_lsa_body) + { + mb_free(en->next_lsa_body); + en->next_lsa_body = NULL; + en->next_lsa_blen = 0; + en->next_lsa_opts = 0; + } + + if (en->lsa.age == LSA_MAXAGE) + return; + + OSPF_TRACE(D_EVENTS, "Flushing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x", + en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn); + + en->lsa.age = LSA_MAXAGE; + ospf_flood_lsa(p, en, NULL); + + if (en->mode == LSA_M_BASIC) + ospf_schedule_rtcalc(p); + + en->mode = LSA_M_BASIC; +} + +static void +ospf_clear_lsa(struct ospf_proto *p, struct top_hash_entry *en) +{ + /* + * Called by ospf_update_lsadb() as part of LSA flushing process. + * Flushed LSA was acknowledged by neighbors and we can free its content. + * The log message is for 'remove' - we hide empty LSAs from users. + */ + + OSPF_TRACE(D_EVENTS, "Removing LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x", + en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn); + + if (en->lsa.sn == LSA_MAXSEQNO) + en->lsa.sn = LSA_ZEROSEQNO; + + mb_free(en->lsa_body); + en->lsa_body = NULL; +} + +static void +ospf_remove_lsa(struct ospf_proto *p, struct top_hash_entry *en) +{ + /* + * Called by ospf_update_lsadb() as part of LSA flushing process. + * Both lsa_body and next_lsa_body are NULL. + */ + + s_rem_node(SNODE en); + ospf_hash_delete(p->gr, en); +} + +/** + * ospf_update_lsadb - update LSA database + * @p: OSPF protocol instance + * + * This function is periodicaly invoked from ospf_disp(). It does some periodic + * or postponed processing related to LSA entries. It originates postponed LSAs + * scheduled by ospf_originate_lsa(), It continues in flushing processes started + * by ospf_flush_lsa(). It also periodically refreshs locally originated LSAs -- + * when the current instance is older %LSREFRESHTIME, a new instance is originated. + * Finally, it also ages stored LSAs and flushes ones that reached %LSA_MAXAGE. + * + * The RFC 2328 says that a router should periodically check checksums of all + * stored LSAs to detect hardware problems. This is not implemented. + */ +void +ospf_update_lsadb(struct ospf_proto *p) +{ + struct top_hash_entry *en, *nxt; + bird_clock_t real_age; + + WALK_SLIST_DELSAFE(en, nxt, p->lsal) + { + if (en->next_lsa_body) + ospf_originate_next_lsa(p, en); + + real_age = en->init_age + (now - en->inst_time); + + if (en->lsa.age == LSA_MAXAGE) + { + if (en->lsa_body && (p->padj == 0) && (en->ret_count == 0)) + ospf_clear_lsa(p, en); + + if ((en->lsa_body == NULL) && (en->next_lsa_body == NULL) && + ((en->lsa.rt != p->router_id) || (real_age >= LSA_MAXAGE))) + ospf_remove_lsa(p, en); + + continue; + } + + if ((en->lsa.rt == p->router_id) && (real_age >= LSREFRESHTIME)) + { + ospf_refresh_lsa(p, en); + continue; + } + + if (real_age >= LSA_MAXAGE) { - po->lsab_size = MAX(po->lsab_used, 2 * po->lsab_size); - po->lsab = po->lsab ? mb_realloc(po->lsab, po->lsab_size): - mb_alloc(po->proto.pool, po->lsab_size); + ospf_flush_lsa(p, en); + continue; } - return ((byte *) po->lsab) + offset; + + en->lsa.age = real_age; + } +} + + +static inline u32 +ort_to_lsaid(struct ospf_proto *p, ort *nf) +{ + /* + * In OSPFv2, We have to map IP prefixes to u32 in such manner that resulting + * u32 interpreted as IP address is a member of given prefix. Therefore, /32 + * prefix have to be mapped on itself. All received prefixes have to be + * mapped on different u32s. + * + * We have an assumption that if there is nontrivial (non-/32) network prefix, + * then there is not /32 prefix for the first and the last IP address of the + * network (these are usually reserved, therefore it is not an important + * restriction). The network prefix is mapped to the first or the last IP + * address in the manner that disallow collisions - we use the IP address that + * cannot be used by the parent prefix. + * + * For example: + * 192.168.0.0/24 maps to 192.168.0.255 + * 192.168.1.0/24 maps to 192.168.1.0 + * because 192.168.0.0 and 192.168.1.255 might be used by 192.168.0.0/23 . + * + * Appendig E of RFC 2328 suggests different algorithm, that tries to maximize + * both compatibility and subnetting. But as it is not possible to have both + * reliably and the suggested algorithm was unnecessary complicated and it + * does crazy things like changing LSA ID for a network because different + * network appeared, we choose a different way. + * + * In OSPFv3, it is simpler. There is not a requirement for membership of the + * result in the input network, so we just use a hash-based unique ID of a + * routing table entry for a route that originated given LSA. For ext-LSA, it + * is an imported route in the nest's routing table (p->table). For summary-LSA, + * it is a 'source' route in the protocol internal routing table (p->rtf). + */ + + if (ospf_is_v3(p)) + return nf->fn.uid; + + u32 id = ipa_to_u32(nf->fn.prefix); + int pxlen = nf->fn.pxlen; + + if ((pxlen == 0) || (pxlen == 32)) + return id; + + if (id & (1 << (32 - pxlen))) + return id; + else + return id | ~u32_mkmask(pxlen); +} + + +static void * +lsab_alloc(struct ospf_proto *p, uint size) +{ + uint offset = p->lsab_used; + p->lsab_used += size; + if (p->lsab_used > p->lsab_size) + { + p->lsab_size = MAX(p->lsab_used, 2 * p->lsab_size); + p->lsab = p->lsab ? mb_realloc(p->lsab, p->lsab_size): + mb_alloc(p->p.pool, p->lsab_size); + } + return ((byte *) p->lsab) + offset; } static inline void * -lsab_allocz(struct proto_ospf *po, unsigned size) +lsab_allocz(struct ospf_proto *p, uint size) { - void *r = lsab_alloc(po, size); + void *r = lsab_alloc(p, size); bzero(r, size); return r; } static inline void * -lsab_flush(struct proto_ospf *po) +lsab_flush(struct ospf_proto *p) { - void *r = mb_alloc(po->proto.pool, po->lsab_used); - memcpy(r, po->lsab, po->lsab_used); - po->lsab_used = 0; + void *r = mb_alloc(p->p.pool, p->lsab_used); + memcpy(r, p->lsab, p->lsab_used); + p->lsab_used = 0; return r; } -static inline void * -lsab_offset(struct proto_ospf *po, unsigned offset) +static inline void +lsab_reset(struct ospf_proto *p) { - return ((byte *) po->lsab) + offset; + p->lsab_used = 0; } static inline void * -lsab_end(struct proto_ospf *po) +lsab_offset(struct ospf_proto *p, uint offset) { - return ((byte *) po->lsab) + po->lsab_used; + return ((byte *) p->lsab) + offset; } -static s32 -get_seqnum(struct top_hash_entry *en) +static inline void * +lsab_end(struct ospf_proto *p) { - if (!en) - return LSA_INITSEQNO; - - if (en->lsa.sn == LSA_MAXSEQNO) - { - log(L_WARN "OSPF: Premature origination of LSA (Type: %04x, Id: %R, Rt: %R)", - en->lsa.type, en->lsa.id, en->lsa.rt); - return LSA_INITSEQNO; - } - - return en->lsa.sn + 1; + return ((byte *) p->lsab) + p->lsab_used; } +/* + * Router-LSA handling + * Type = LSA_T_RT + */ + static int configured_stubnet(struct ospf_area *oa, struct ifa *a) { - if (!oa->ac) - return 0; - /* Does not work for IA_PEER addresses, but it is not called on these */ struct ospf_stubnet_config *sn; WALK_LIST(sn, oa->ac->stubnet_list) + { + if (sn->summary) { - if (sn->summary) - { - if (ipa_in_net(a->prefix, sn->px.addr, sn->px.len) && (a->pxlen >= sn->px.len)) - return 1; - } - else - { - if (ipa_equal(a->prefix, sn->px.addr) && (a->pxlen == sn->px.len)) - return 1; - } + if (ipa_in_net(a->prefix, sn->px.addr, sn->px.len) && (a->pxlen >= sn->px.len)) + return 1; } + else + { + if (ipa_equal(a->prefix, sn->px.addr) && (a->pxlen == sn->px.len)) + return 1; + } + } + return 0; } -int +static int bcast_net_active(struct ospf_iface *ifa) { struct ospf_neighbor *neigh; @@ -188,53 +650,66 @@ bcast_net_active(struct ospf_iface *ifa) return 0; WALK_LIST(neigh, ifa->neigh_list) + { + if (neigh->state == NEIGHBOR_FULL) { - if (neigh->state == NEIGHBOR_FULL) - { - if (neigh->rid == ifa->drid) - return 1; + if (neigh->rid == ifa->drid) + return 1; - if (ifa->state == OSPF_IS_DR) - return 1; - } + if (ifa->state == OSPF_IS_DR) + return 1; } + } return 0; } +static inline u32 +get_rt_options(struct ospf_proto *p, struct ospf_area *oa, int bitv) +{ + u32 opts = 0; -#ifdef OSPFv2 + if (p->areano > 1) + opts |= OPT_RT_B; -static void * -originate_rt_lsa_body(struct ospf_area *oa, u16 *length) -{ - struct proto_ospf *po = oa->po; - struct ospf_iface *ifa; - int i = 0, bitv = 0; - struct ospf_lsa_rt *rt; - struct ospf_lsa_rt_link *ln; - struct ospf_neighbor *neigh; + if ((p->areano > 1) && oa_is_nssa(oa) && oa->ac->translator) + opts |= OPT_RT_NT; - ASSERT(po->lsab_used == 0); - rt = lsab_allocz(po, sizeof(struct ospf_lsa_rt)); + if (p->asbr && !oa_is_stub(oa)) + opts |= OPT_RT_E; - rt->options = 0; + if (bitv) + opts |= OPT_RT_V; - if (po->areano > 1) - rt->options |= OPT_RT_B; + return opts; +} - if ((po->areano > 1) && oa_is_nssa(oa) && oa->ac->translator) - rt->options |= OPT_RT_NT; +static inline void +add_rt2_lsa_link(struct ospf_proto *p, u8 type, u32 id, u32 data, u16 metric) +{ + struct ospf_lsa_rt2_link *ln = lsab_alloc(p, sizeof(struct ospf_lsa_rt2_link)); + ln->type = type; + ln->id = id; + ln->data = data; + ln->metric = metric; + ln->no_tos = 0; +} - if (po->ebit && !oa_is_stub(oa)) - rt->options |= OPT_RT_E; +static void +prepare_rt2_lsa_body(struct ospf_proto *p, struct ospf_area *oa) +{ + struct ospf_iface *ifa; + int i = 0, bitv = 0; + struct ospf_neighbor *neigh; - rt = NULL; /* buffer might be reallocated later */ + ASSERT(p->lsab_used == 0); + lsab_allocz(p, sizeof(struct ospf_lsa_rt)); + /* ospf_lsa_rt header will be filled later */ - WALK_LIST(ifa, po->iface_list) + WALK_LIST(ifa, p->iface_list) { int net_lsa = 0; - u32 link_cost = po->stub_router ? 0xffff : ifa->cost; + u32 link_cost = p->stub_router ? 0xffff : ifa->cost; if ((ifa->type == OSPF_IT_VLINK) && (ifa->voa == oa) && (!EMPTY_LIST(ifa->neigh_list))) @@ -249,66 +724,47 @@ originate_rt_lsa_body(struct ospf_area *oa, u16 *length) ifa->rt_pos_beg = i; - /* RFC2328 - 12.4.1.1-4 */ + /* RFC 2328 - 12.4.1.1-4 */ switch (ifa->type) - { - case OSPF_IT_PTP: - case OSPF_IT_PTMP: - WALK_LIST(neigh, ifa->neigh_list) - if (neigh->state == NEIGHBOR_FULL) - { - ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link)); - ln->type = LSART_PTP; - ln->id = neigh->rid; - - /* - * ln->data should be ifa->iface_id in case of no/ptp - * address (ifa->addr->flags & IA_PEER) on PTP link (see - * RFC 2328 12.4.1.1.), but the iface ID value has no use, - * while using IP address even in this case is here for - * compatibility with some broken implementations that use - * this address as a next-hop. - */ - ln->data = ipa_to_u32(ifa->addr->ip); - ln->metric = link_cost; - ln->padding = 0; - i++; - } - break; - - case OSPF_IT_BCAST: - case OSPF_IT_NBMA: - if (bcast_net_active(ifa)) - { - ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link)); - ln->type = LSART_NET; - ln->id = ipa_to_u32(ifa->drip); - ln->data = ipa_to_u32(ifa->addr->ip); - ln->metric = link_cost; - ln->padding = 0; - i++; - net_lsa = 1; - } - break; - - case OSPF_IT_VLINK: - neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list); - if ((!EMPTY_LIST(ifa->neigh_list)) && (neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff)) + { + case OSPF_IT_PTP: + case OSPF_IT_PTMP: + WALK_LIST(neigh, ifa->neigh_list) + if (neigh->state == NEIGHBOR_FULL) { - ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link)); - ln->type = LSART_VLNK; - ln->id = neigh->rid; - ln->data = ipa_to_u32(ifa->addr->ip); - ln->metric = link_cost; - ln->padding = 0; + /* + * ln->data should be ifa->iface_id in case of no/ptp + * address (ifa->addr->flags & IA_PEER) on PTP link (see + * RFC 2328 12.4.1.1.), but the iface ID value has no use, + * while using IP address even in this case is here for + * compatibility with some broken implementations that use + * this address as a next-hop. + */ + add_rt2_lsa_link(p, LSART_PTP, neigh->rid, ipa_to_u32(ifa->addr->ip), link_cost); i++; - } - break; + } + break; - default: - log("Unknown interface type %s", ifa->ifname); - break; + case OSPF_IT_BCAST: + case OSPF_IT_NBMA: + if (bcast_net_active(ifa)) + { + add_rt2_lsa_link(p, LSART_NET, ipa_to_u32(ifa->drip), ipa_to_u32(ifa->addr->ip), link_cost); + i++; + net_lsa = 1; } + break; + + case OSPF_IT_VLINK: + neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list); + if ((!EMPTY_LIST(ifa->neigh_list)) && (neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff)) + add_rt2_lsa_link(p, LSART_VLNK, neigh->rid, ipa_to_u32(ifa->addr->ip), link_cost), i++; + break; + + default: + log(L_BUG "OSPF: Unknown interface type"); + break; + } ifa->rt_pos_end = i; @@ -319,62 +775,32 @@ originate_rt_lsa_body(struct ospf_area *oa, u16 *length) configured_stubnet(oa, ifa->addr)) continue; - ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link)); + /* Host or network stub entry */ if ((ifa->addr->flags & IA_HOST) || (ifa->state == OSPF_IS_LOOP) || (ifa->type == OSPF_IT_PTMP)) - { - /* Host stub entry */ - ln->type = LSART_STUB; - ln->id = ipa_to_u32(ifa->addr->ip); - ln->data = 0xffffffff; - ln->metric = 0; - ln->padding = 0; - } - else - { - /* Network stub entry */ - ln->type = LSART_STUB; - ln->id = ipa_to_u32(ifa->addr->prefix); - ln->data = ipa_to_u32(ipa_mkmask(ifa->addr->pxlen)); - ln->metric = ifa->cost; - ln->padding = 0; - } + add_rt2_lsa_link(p, LSART_STUB, ipa_to_u32(ifa->addr->ip), 0xffffffff, 0); + else + add_rt2_lsa_link(p, LSART_STUB, ipa_to_u32(ifa->addr->prefix), u32_mkmask(ifa->addr->pxlen), ifa->cost); i++; ifa->rt_pos_end = i; } struct ospf_stubnet_config *sn; - if (oa->ac) - WALK_LIST(sn, oa->ac->stubnet_list) - if (!sn->hidden) - { - ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link)); - ln->type = LSART_STUB; - ln->id = ipa_to_u32(sn->px.addr); - ln->data = ipa_to_u32(ipa_mkmask(sn->px.len)); - ln->metric = sn->cost; - ln->padding = 0; - i++; - } - - rt = po->lsab; - rt->links = i; - - if (bitv) - rt->options |= OPT_RT_V; + WALK_LIST(sn, oa->ac->stubnet_list) + if (!sn->hidden) + add_rt2_lsa_link(p, LSART_STUB, ipa_to_u32(sn->px.addr), u32_mkmask(sn->px.len), sn->cost), i++; - *length = po->lsab_used + sizeof(struct ospf_lsa_header); - return lsab_flush(po); + struct ospf_lsa_rt *rt = p->lsab; + /* Store number of links in lower half of options */ + rt->options = get_rt_options(p, oa, bitv) | (u16) i; } -#else /* OSPFv3 */ - -static void -add_lsa_rt_link(struct proto_ospf *po, struct ospf_iface *ifa, u8 type, u32 nif, u32 id) +static inline void +add_rt3_lsa_link(struct ospf_proto *p, u8 type, struct ospf_iface *ifa, u32 nif, u32 id) { - struct ospf_lsa_rt_link *ln = lsab_alloc(po, sizeof(struct ospf_lsa_rt_link)); + struct ospf_lsa_rt3_link *ln = lsab_alloc(p, sizeof(struct ospf_lsa_rt3_link)); ln->type = type; ln->padding = 0; ln->metric = ifa->cost; @@ -383,33 +809,19 @@ add_lsa_rt_link(struct proto_ospf *po, struct ospf_iface *ifa, u8 type, u32 nif, ln->id = id; } -static void * -originate_rt_lsa_body(struct ospf_area *oa, u16 *length) +static void +prepare_rt3_lsa_body(struct ospf_proto *p, struct ospf_area *oa) { - struct proto_ospf *po = oa->po; struct ospf_iface *ifa; + struct ospf_neighbor *neigh; int bitv = 0; int i = 0; - struct ospf_lsa_rt *rt; - struct ospf_neighbor *neigh; - - ASSERT(po->lsab_used == 0); - rt = lsab_allocz(po, sizeof(struct ospf_lsa_rt)); - rt->options = oa->options & OPTIONS_MASK; + ASSERT(p->lsab_used == 0); + lsab_allocz(p, sizeof(struct ospf_lsa_rt)); + /* ospf_lsa_rt header will be filled later */ - if (po->areano > 1) - rt->options |= OPT_RT_B; - - if ((po->areano > 1) && oa_is_nssa(oa) && oa->ac->translator) - rt->options |= OPT_RT_NT; - - if (po->ebit && !oa_is_stub(oa)) - rt->options |= OPT_RT_E; - - rt = NULL; /* buffer might be reallocated later */ - - WALK_LIST(ifa, po->iface_list) + WALK_LIST(ifa, p->iface_list) { if ((ifa->type == OSPF_IT_VLINK) && (ifa->voa == oa) && (!EMPTY_LIST(ifa->neigh_list))) @@ -424,854 +836,556 @@ originate_rt_lsa_body(struct ospf_area *oa, u16 *length) ifa->rt_pos_beg = i; - /* RFC5340 - 4.4.3.2 */ + /* RFC 5340 - 4.4.3.2 */ switch (ifa->type) - { - case OSPF_IT_PTP: - case OSPF_IT_PTMP: - WALK_LIST(neigh, ifa->neigh_list) - if (neigh->state == NEIGHBOR_FULL) - add_lsa_rt_link(po, ifa, LSART_PTP, neigh->iface_id, neigh->rid), i++; - break; - - case OSPF_IT_BCAST: - case OSPF_IT_NBMA: - if (bcast_net_active(ifa)) - add_lsa_rt_link(po, ifa, LSART_NET, ifa->dr_iface_id, ifa->drid), i++; - break; - - case OSPF_IT_VLINK: - neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list); - if ((!EMPTY_LIST(ifa->neigh_list)) && (neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff)) - add_lsa_rt_link(po, ifa, LSART_VLNK, neigh->iface_id, neigh->rid), i++; - break; - - default: - log("Unknown interface type %s", ifa->ifname); - break; - } - - ifa->rt_pos_end = i; - } - - if (bitv) { - rt = po->lsab; - rt->options |= OPT_RT_V; - } - - *length = po->lsab_used + sizeof(struct ospf_lsa_header); - return lsab_flush(po); -} - -#endif + case OSPF_IT_PTP: + case OSPF_IT_PTMP: + WALK_LIST(neigh, ifa->neigh_list) + if (neigh->state == NEIGHBOR_FULL) + add_rt3_lsa_link(p, LSART_PTP, ifa, neigh->iface_id, neigh->rid), i++; + break; -/** - * originate_rt_lsa - build new instance of router LSA - * @oa: ospf_area which is LSA built to - * - * It builds router LSA walking through all OSPF interfaces in - * specified OSPF area. This function is mostly called from - * area_disp(). Builds new LSA, increases sequence number (if old - * instance exists) and sets age of LSA to zero. - */ -void -originate_rt_lsa(struct ospf_area *oa) -{ - struct ospf_lsa_header lsa; - struct proto_ospf *po = oa->po; - struct proto *p = &po->proto; - void *body; + case OSPF_IT_BCAST: + case OSPF_IT_NBMA: + if (bcast_net_active(ifa)) + add_rt3_lsa_link(p, LSART_NET, ifa, ifa->dr_iface_id, ifa->drid), i++; + break; - OSPF_TRACE(D_EVENTS, "Originating router-LSA for area %R", oa->areaid); + case OSPF_IT_VLINK: + neigh = (struct ospf_neighbor *) HEAD(ifa->neigh_list); + if ((!EMPTY_LIST(ifa->neigh_list)) && (neigh->state == NEIGHBOR_FULL) && (ifa->cost <= 0xffff)) + add_rt3_lsa_link(p, LSART_VLNK, ifa, neigh->iface_id, neigh->rid), i++; + break; - lsa.age = 0; - lsa.type = LSA_T_RT; - -#ifdef OSPFv2 - lsa.options = oa->options; - lsa.id = po->router_id; -#else /* OSPFv3 */ - lsa.id = 0; -#endif + default: + log(L_BUG "OSPF: Unknown interface type"); + break; + } - lsa.rt = po->router_id; - lsa.sn = get_seqnum(oa->rt); - u32 dom = oa->areaid; + ifa->rt_pos_end = i; + } - body = originate_rt_lsa_body(oa, &lsa.length); - lsasum_calculate(&lsa, body); - oa->rt = lsa_install_new(po, &lsa, dom, body); - ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1); + struct ospf_lsa_rt *rt = p->lsab; + rt->options = get_rt_options(p, oa, bitv) | (oa->options & LSA_OPTIONS_MASK); } -void -update_rt_lsa(struct ospf_area *oa) +static void +ospf_originate_rt_lsa(struct ospf_proto *p, struct ospf_area *oa) { - struct proto_ospf *po = oa->po; + struct ospf_new_lsa lsa = { + .type = LSA_T_RT, + .dom = oa->areaid, + .id = ospf_is_v2(p) ? p->router_id : 0, + .opts = oa->options + }; - if ((oa->rt) && ((oa->rt->inst_t + MINLSINTERVAL)) > now) - return; - /* - * Tick is probably set to very low value. We cannot - * originate new LSA before MINLSINTERVAL. We will - * try to do it next tick. - */ + OSPF_TRACE(D_EVENTS, "Updating router state for area %R", oa->areaid); - originate_rt_lsa(oa); -#ifdef OSPFv3 - originate_prefix_rt_lsa(oa); -#endif + if (ospf_is_v2(p)) + prepare_rt2_lsa_body(p, oa); + else + prepare_rt3_lsa_body(p, oa); - schedule_rtcalc(po); - oa->origrt = 0; + oa->rt = ospf_originate_lsa(p, &lsa); } -static void * -originate_net_lsa_body(struct ospf_iface *ifa, u16 *length, - struct proto_ospf *po) + +/* + * Net-LSA handling + * Type = LSA_T_NET + */ + +static void +prepare_net2_lsa_body(struct ospf_proto *p, struct ospf_iface *ifa) { - u16 i = 1; - struct ospf_neighbor *n; struct ospf_lsa_net *net; + struct ospf_neighbor *n; int nodes = ifa->fadj + 1; + u16 i = 1; - net = mb_alloc(po->proto.pool, sizeof(struct ospf_lsa_net) - + nodes * sizeof(u32)); - -#ifdef OSPFv2 - net->netmask = ipa_mkmask(ifa->addr->pxlen); -#endif - -#ifdef OSPFv3 - /* In OSPFv3, we would like to merge options from Link LSAs of added neighbors */ - struct top_hash_entry *en; - u32 options = 0; -#endif + ASSERT(p->lsab_used == 0); + net = lsab_alloc(p, sizeof(struct ospf_lsa_net) + 4 * nodes); - net->routers[0] = po->router_id; + net->optx = u32_mkmask(ifa->addr->pxlen); + net->routers[0] = p->router_id; WALK_LIST(n, ifa->neigh_list) { if (n->state == NEIGHBOR_FULL) { -#ifdef OSPFv3 - en = ospf_hash_find(po->gr, ifa->iface_id, n->iface_id, n->rid, LSA_T_LINK); - if (en) - options |= ((struct ospf_lsa_link *) en->lsa_body)->options; -#endif - net->routers[i] = n->rid; i++; } } ASSERT(i == nodes); - -#ifdef OSPFv3 - net->options = options & OPTIONS_MASK; -#endif - - *length = sizeof(struct ospf_lsa_header) + sizeof(struct ospf_lsa_net) - + nodes * sizeof(u32); - return net; } - -/** - * originate_net_lsa - originates of deletes network LSA - * @ifa: interface which is LSA originated for - * - * Interface counts number of adjacent neighbors. If this number is - * lower than one or interface is not in state %OSPF_IS_DR it deletes - * and premature ages instance of network LSA for specified interface. - * In other case, new instance of network LSA is originated. - */ -void -originate_net_lsa(struct ospf_iface *ifa) +static void +prepare_net3_lsa_body(struct ospf_proto *p, struct ospf_iface *ifa) { - struct proto_ospf *po = ifa->oa->po; - struct proto *p = &po->proto; - struct ospf_lsa_header lsa; - u32 dom = ifa->oa->areaid; - - void *body; - - OSPF_TRACE(D_EVENTS, "Originating network-LSA for iface %s", ifa->ifname); - - lsa.age = 0; - lsa.type = LSA_T_NET; - -#ifdef OSPFv2 - lsa.options = ifa->oa->options; - lsa.id = ipa_to_u32(ifa->addr->ip); -#else /* OSPFv3 */ - lsa.id = ifa->iface_id; -#endif + struct ospf_lsa_net *net; + int nodes = ifa->fadj + 1; + u32 options = 0; + u16 i = 1; - lsa.rt = po->router_id; - lsa.sn = get_seqnum(ifa->net_lsa); + ASSERT(p->lsab_used == 0); + net = lsab_alloc(p, sizeof(struct ospf_lsa_net) + 4 * nodes); - body = originate_net_lsa_body(ifa, &lsa.length, po); - lsasum_calculate(&lsa, body); - ifa->net_lsa = lsa_install_new(po, &lsa, dom, body); - ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1); -} + net->routers[0] = p->router_id; -void -flush_net_lsa(struct ospf_iface *ifa) -{ - struct proto_ospf *po = ifa->oa->po; - struct proto *p = &po->proto; - u32 dom = ifa->oa->areaid; - - if (ifa->net_lsa == NULL) - return; + struct ospf_neighbor *n; + WALK_LIST(n, ifa->neigh_list) + { + if (n->state == NEIGHBOR_FULL) + { + /* In OSPFv3, we would like to merge options from Link LSAs of added neighbors */ - OSPF_TRACE(D_EVENTS, "Flushing network-LSA for iface %s", ifa->ifname); - ifa->net_lsa->lsa.sn += 1; - ifa->net_lsa->lsa.age = LSA_MAXAGE; - lsasum_calculate(&ifa->net_lsa->lsa, ifa->net_lsa->lsa_body); - ospf_lsupd_flood(po, NULL, NULL, &ifa->net_lsa->lsa, dom, 0); - flush_lsa(ifa->net_lsa, po); - ifa->net_lsa = NULL; -} + struct top_hash_entry *en = + ospf_hash_find(p->gr, ifa->iface_id, n->iface_id, n->rid, LSA_T_LINK); -void -update_net_lsa(struct ospf_iface *ifa) -{ - struct proto_ospf *po = ifa->oa->po; - - if (ifa->net_lsa && ((ifa->net_lsa->inst_t + MINLSINTERVAL) > now)) - return; - /* - * It's too early to originate new network LSA. We will - * try to do it next tick - */ + if (en) + options |= ((struct ospf_lsa_link *) en->lsa_body)->options; - if ((ifa->state != OSPF_IS_DR) || (ifa->fadj == 0)) - { - flush_net_lsa(ifa); -#ifdef OSPFv3 - flush_prefix_net_lsa(ifa); -#endif - } - else - { - originate_net_lsa(ifa); -#ifdef OSPFv3 - originate_prefix_net_lsa(ifa); -#endif + net->routers[i] = n->rid; + i++; } + } + ASSERT(i == nodes); - schedule_rtcalc(po); - ifa->orignet = 0; + net->optx = options & LSA_OPTIONS_MASK; } -#ifdef OSPFv2 - -static inline void * -originate_sum_lsa_body(struct proto_ospf *po, u16 *length, u32 mlen, u32 metric) +static void +ospf_originate_net_lsa(struct ospf_proto *p, struct ospf_iface *ifa) { - struct ospf_lsa_sum *sum = mb_alloc(po->proto.pool, sizeof(struct ospf_lsa_sum)); - *length = sizeof(struct ospf_lsa_header) + sizeof(struct ospf_lsa_sum); + struct ospf_new_lsa lsa = { + .type = LSA_T_NET, + .dom = ifa->oa->areaid, + .id = ospf_is_v2(p) ? ipa_to_u32(ifa->addr->ip) : ifa->iface_id, + .opts = ifa->oa->options, + .ifa = ifa + }; - sum->netmask = ipa_mkmask(mlen); - sum->metric = metric; + OSPF_TRACE(D_EVENTS, "Updating network state for %s (Id: %R)", ifa->ifname, lsa.id); - return sum; -} - -#define originate_sum_net_lsa_body(po,length,fn,metric) \ - originate_sum_lsa_body(po, length, (fn)->pxlen, metric) - -#define originate_sum_rt_lsa_body(po,length,drid,metric,options) \ - originate_sum_lsa_body(po, length, 0, metric) - -static inline int -check_sum_net_lsaid_collision(struct fib_node *fn, struct top_hash_entry *en) -{ - struct ospf_lsa_sum *sum = en->lsa_body; - return fn->pxlen != ipa_mklen(sum->netmask); -} + if (ospf_is_v2(p)) + prepare_net2_lsa_body(p, ifa); + else + prepare_net3_lsa_body(p, ifa); -static inline int -check_sum_lsa_same(struct top_hash_entry *en, u32 metric) -{ - /* Netmask already checked in check_sum_net_lsaid_collision() */ - struct ospf_lsa_sum *sum = en->lsa_body; - return (en->lsa.sn != LSA_MAXSEQNO) && (sum->metric == metric); + ifa->net_lsa = ospf_originate_lsa(p, &lsa); } -#define check_sum_net_lsa_same(en,metric) \ - check_sum_lsa_same(en, metric) - -#define check_sum_rt_lsa_same(en,drid,metric,options) \ - check_sum_lsa_same(en, metric) +/* + * (Net|Rt)-summary-LSA handling + * (a.k.a. Inter-Area-(Prefix|Router)-LSA) + * Type = LSA_T_SUM_NET, LSA_T_SUM_RT + */ -#else /* OSPFv3 */ - -static inline void * -originate_sum_net_lsa_body(struct proto_ospf *po, u16 *length, struct fib_node *fn, u32 metric) +static inline void +prepare_sum2_lsa_body(struct ospf_proto *p, uint pxlen, u32 metric) { - int size = sizeof(struct ospf_lsa_sum_net) + IPV6_PREFIX_SPACE(fn->pxlen); - struct ospf_lsa_sum_net *sum = mb_alloc(po->proto.pool, size); - *length = sizeof(struct ospf_lsa_header) + size; + struct ospf_lsa_sum2 *sum; + sum = lsab_allocz(p, sizeof(struct ospf_lsa_sum2)); + sum->netmask = u32_mkmask(pxlen); sum->metric = metric; - put_ipv6_prefix(sum->prefix, fn->prefix, fn->pxlen, 0, 0); - - return sum; } -static inline int -check_sum_net_lsaid_collision(struct fib_node *fn, struct top_hash_entry *en) +static inline void +prepare_sum3_net_lsa_body(struct ospf_proto *p, ort *nf, u32 metric) { - struct ospf_lsa_sum_net *sum = en->lsa_body; - ip_addr prefix; - int pxlen; - u8 pxopts; - u16 rest; - - lsa_get_ipv6_prefix(sum->prefix, &prefix, &pxlen, &pxopts, &rest); - return (fn->pxlen != pxlen) || !ipa_equal(fn->prefix, prefix); -} + struct ospf_lsa_sum3_net *sum; -static inline int -check_sum_net_lsa_same(struct top_hash_entry *en, u32 metric) -{ - /* Prefix already checked in check_sum_net_lsaid_collision() */ - struct ospf_lsa_sum_net *sum = en->lsa_body; - return (en->lsa.sn != LSA_MAXSEQNO) && (sum->metric == metric); + sum = lsab_allocz(p, sizeof(struct ospf_lsa_sum3_net) + IPV6_PREFIX_SPACE(nf->fn.pxlen)); + sum->metric = metric; + put_ipv6_prefix(sum->prefix, nf->fn.prefix, nf->fn.pxlen, 0, 0); } -static inline void * -originate_sum_rt_lsa_body(struct proto_ospf *po, u16 *length, u32 drid, u32 metric, u32 options) +static inline void +prepare_sum3_rt_lsa_body(struct ospf_proto *p, u32 drid, u32 metric, u32 options) { - struct ospf_lsa_sum_rt *sum = mb_alloc(po->proto.pool, sizeof(struct ospf_lsa_sum_rt)); - *length = sizeof(struct ospf_lsa_header) + sizeof(struct ospf_lsa_sum_rt); + struct ospf_lsa_sum3_rt *sum; + sum = lsab_allocz(p, sizeof(struct ospf_lsa_sum3_rt)); sum->options = options; sum->metric = metric; sum->drid = drid; - - return sum; } -static inline int -check_sum_rt_lsa_same(struct top_hash_entry *en, u32 drid, u32 metric, u32 options) -{ - struct ospf_lsa_sum_rt *sum = en->lsa_body; - return (en->lsa.sn != LSA_MAXSEQNO) && (sum->options == options) && - (sum->metric == metric) && (sum->drid == drid); -} - -#endif - void -originate_sum_net_lsa(struct ospf_area *oa, struct fib_node *fn, int metric) -{ - struct proto_ospf *po = oa->po; - struct proto *p = &po->proto; - struct top_hash_entry *en; - u32 dom = oa->areaid; - struct ospf_lsa_header lsa; - void *body; - - OSPF_TRACE(D_EVENTS, "Originating net-summary-LSA for %I/%d (metric %d)", - fn->prefix, fn->pxlen, metric); - - /* options argument is used in ORT_NET and OSPFv3 only */ - lsa.age = 0; -#ifdef OSPFv2 - lsa.options = oa->options; -#endif - lsa.type = LSA_T_SUM_NET; - lsa.id = fibnode_to_lsaid(po, fn); - lsa.rt = po->router_id; - - if ((en = ospf_hash_find_header(po->gr, dom, &lsa)) != NULL) - { - if (check_sum_net_lsaid_collision(fn, en)) - { - log(L_ERR "%s: LSAID collision for %I/%d", - p->name, fn->prefix, fn->pxlen); - return; - } - - if (check_sum_net_lsa_same(en, metric)) - return; - } - lsa.sn = get_seqnum(en); - - body = originate_sum_net_lsa_body(po, &lsa.length, fn, metric); - lsasum_calculate(&lsa, body); - lsa_install_new(po, &lsa, dom, body); - ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1); -} - -void -originate_sum_rt_lsa(struct ospf_area *oa, struct fib_node *fn, int metric, u32 options UNUSED) -{ - struct proto_ospf *po = oa->po; - struct proto *p = &po->proto; - struct top_hash_entry *en; - u32 dom = oa->areaid; - u32 rid = ipa_to_rid(fn->prefix); - struct ospf_lsa_header lsa; - void *body; - - OSPF_TRACE(D_EVENTS, "Originating rt-summary-LSA for %R (metric %d)", - rid, metric); - - lsa.age = 0; -#ifdef OSPFv2 - lsa.options = oa->options; -#endif - lsa.type = LSA_T_SUM_RT; - /* In OSPFv3, LSA ID is meaningless, but we still use Router ID of ASBR */ - lsa.id = rid; - lsa.rt = po->router_id; - - options &= OPTIONS_MASK; - if ((en = ospf_hash_find_header(po->gr, dom, &lsa)) != NULL) - { - if (check_sum_rt_lsa_same(en, lsa.id, metric, options)) - return; - } - lsa.sn = get_seqnum(en); +ospf_originate_sum_net_lsa(struct ospf_proto *p, struct ospf_area *oa, ort *nf, int metric) +{ + struct ospf_new_lsa lsa = { + .type = LSA_T_SUM_NET, + .mode = LSA_M_RTCALC, + .dom = oa->areaid, + .id = ort_to_lsaid(p, nf), + .opts = oa->options, + .nf = nf + }; + + if (ospf_is_v2(p)) + prepare_sum2_lsa_body(p, nf->fn.pxlen, metric); + else + prepare_sum3_net_lsa_body(p, nf, metric); - body = originate_sum_rt_lsa_body(po, &lsa.length, lsa.id, metric, options); - lsasum_calculate(&lsa, body); - lsa_install_new(po, &lsa, dom, body); - ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1); + ospf_originate_lsa(p, &lsa); } void -flush_sum_lsa(struct ospf_area *oa, struct fib_node *fn, int type) -{ - struct proto_ospf *po = oa->po; - struct proto *p = &po->proto; - struct top_hash_entry *en; - struct ospf_lsa_header lsa; - - lsa.rt = po->router_id; - if (type == ORT_NET) - { - lsa.id = fibnode_to_lsaid(po, fn); - lsa.type = LSA_T_SUM_NET; - } +ospf_originate_sum_rt_lsa(struct ospf_proto *p, struct ospf_area *oa, ort *nf, int metric, u32 options) +{ + struct ospf_new_lsa lsa = { + .type = LSA_T_SUM_RT, + .mode = LSA_M_RTCALC, + .dom = oa->areaid, + .id = ipa_to_rid(nf->fn.prefix), /* Router ID of ASBR, irrelevant for OSPFv3 */ + .opts = oa->options + }; + + if (ospf_is_v2(p)) + prepare_sum2_lsa_body(p, 0, metric); else - { - /* In OSPFv3, LSA ID is meaningless, but we still use Router ID of ASBR */ - lsa.id = ipa_to_rid(fn->prefix); - lsa.type = LSA_T_SUM_RT; - } - - if ((en = ospf_hash_find_header(po->gr, oa->areaid, &lsa)) != NULL) - { - OSPF_TRACE(D_EVENTS, "Flushing summary-LSA (id=%R, type=%d)", - en->lsa.id, en->lsa.type); - - if ((type == ORT_NET) && check_sum_net_lsaid_collision(fn, en)) - { - log(L_ERR "%s: LSAID collision for %I/%d", - p->name, fn->prefix, fn->pxlen); - return; - } + prepare_sum3_rt_lsa_body(p, lsa.id, metric, options & LSA_OPTIONS_MASK); - struct ospf_lsa_sum *sum = en->lsa_body; - en->lsa.age = LSA_MAXAGE; - en->lsa.sn = LSA_MAXSEQNO; - lsasum_calculate(&en->lsa, sum); - ospf_lsupd_flood(po, NULL, NULL, &en->lsa, oa->areaid, 1); - if (can_flush_lsa(po)) flush_lsa(en, po); - } + ospf_originate_lsa(p, &lsa); } -#ifdef OSPFv2 - -static inline void * -originate_ext_lsa_body(struct proto_ospf *po, u16 *length, struct fib_node *fn, - u32 metric, ip_addr fwaddr, u32 tag, int pbit UNUSED) -{ - struct ospf_lsa_ext *ext = mb_alloc(po->proto.pool, sizeof(struct ospf_lsa_ext)); - *length = sizeof(struct ospf_lsa_header) + sizeof(struct ospf_lsa_ext); - - ext->metric = metric; - ext->netmask = ipa_mkmask(fn->pxlen); - ext->fwaddr = fwaddr; - ext->tag = tag; - - return ext; -} /* - * check_ext_lsa() combines functions of check_*_lsaid_collision() and - * check_*_lsa_same(). 'en' is existing ext LSA, and rest parameters - * are parameters of new ext route. Function returns -1 if there is - * LSAID collision, returns 1 if the existing LSA is the same and - * returns 0 otherwise (in that case, we need to originate a new LSA). - * - * Really, checking for the same parameters is not as important as in - * summary LSA origination, because in most cases the duplicate - * external route propagation would be stopped by the nest. But there - * are still some cases (route reload, the same route propagated through - * different protocol) so it is also done here. + * AS-external-LSA and NSSA-LSA handling + * Type = LSA_T_EXT, LSA_T_NSSA */ -static inline int -check_ext_lsa(struct top_hash_entry *en, struct fib_node *fn, u32 metric, ip_addr fwaddr, u32 tag) +static inline void +prepare_ext2_lsa_body(struct ospf_proto *p, uint pxlen, + u32 metric, u32 ebit, ip_addr fwaddr, u32 tag) { - struct ospf_lsa_ext *ext = en->lsa_body; + struct ospf_lsa_ext2 *ext; - /* LSAID collision */ - if (fn->pxlen != ipa_mklen(ext->netmask)) - return -1; + ext = lsab_allocz(p, sizeof(struct ospf_lsa_ext2)); + ext->metric = metric & LSA_METRIC_MASK; + ext->netmask = u32_mkmask(pxlen); + ext->fwaddr = ipa_to_u32(fwaddr); + ext->tag = tag; - return (en->lsa.sn != LSA_MAXSEQNO) && (ext->metric == metric) && - (ext->tag == tag) && ipa_equal(ext->fwaddr,fwaddr); + if (ebit) + ext->metric |= LSA_EXT2_EBIT; } -#else /* OSPFv3 */ - -static inline void * -originate_ext_lsa_body(struct proto_ospf *po, u16 *length, struct fib_node *fn, - u32 metric, ip_addr fwaddr, u32 tag, int pbit) +static inline void +prepare_ext3_lsa_body(struct ospf_proto *p, ort *nf, + u32 metric, u32 ebit, ip_addr fwaddr, u32 tag, int pbit) { - int size = sizeof(struct ospf_lsa_ext) - + IPV6_PREFIX_SPACE(fn->pxlen) + struct ospf_lsa_ext3 *ext; + int bsize = sizeof(struct ospf_lsa_ext3) + + IPV6_PREFIX_SPACE(nf->fn.pxlen) + (ipa_nonzero(fwaddr) ? 16 : 0) + (tag ? 4 : 0); - struct ospf_lsa_ext *ext = mb_alloc(po->proto.pool, size); - *length = sizeof(struct ospf_lsa_header) + size; + ext = lsab_allocz(p, bsize); + ext->metric = metric & LSA_METRIC_MASK; + u32 *buf = ext->rest; - ext->metric = metric; + buf = put_ipv6_prefix(buf, nf->fn.prefix, nf->fn.pxlen, pbit ? OPT_PX_P : 0, 0); - u32 *buf = ext->rest; - buf = put_ipv6_prefix(buf, fn->prefix, fn->pxlen, pbit ? OPT_PX_P : 0, 0); + if (ebit) + ext->metric |= LSA_EXT3_EBIT; if (ipa_nonzero(fwaddr)) { - ext->metric |= LSA_EXT_FBIT; + ext->metric |= LSA_EXT3_FBIT; buf = put_ipv6_addr(buf, fwaddr); } if (tag) { - ext->metric |= LSA_EXT_TBIT; + ext->metric |= LSA_EXT3_TBIT; *buf++ = tag; } - - return ext; } -static inline int -check_ext_lsa(struct top_hash_entry *en, struct fib_node *fn, u32 metric, ip_addr fwaddr, u32 tag) -{ - struct ospf_lsa_ext *ext = en->lsa_body; - ip_addr prefix; - int pxlen; - u8 pxopts; - u16 rest; +/** + * originate_ext_lsa - new route received from nest and filters + * @p: OSPF protocol instance + * @oa: ospf_area for which LSA is originated + * @nf: network prefix and mask + * @mode: the mode of the LSA (LSA_M_EXPORT or LSA_M_RTCALC) + * @metric: the metric of a route + * @ebit: E-bit for route metric (bool) + * @fwaddr: the forwarding address + * @tag: the route tag + * @pbit: P-bit for NSSA LSAs (bool), ignored for external LSAs + * + * If I receive a message that new route is installed, I try to originate an + * external LSA. If @oa is an NSSA area, NSSA-LSA is originated instead. + * @oa should not be a stub area. @src does not specify whether the LSA + * is external or NSSA, but it specifies the source of origination - + * the export from ospf_rt_notify(), or the NSSA-EXT translation. + */ +void +ospf_originate_ext_lsa(struct ospf_proto *p, struct ospf_area *oa, ort *nf, u8 mode, + u32 metric, u32 ebit, ip_addr fwaddr, u32 tag, int pbit) +{ + struct ospf_new_lsa lsa = { + .type = oa ? LSA_T_NSSA : LSA_T_EXT, + .mode = mode, /* LSA_M_EXPORT or LSA_M_RTCALC */ + .dom = oa ? oa->areaid : 0, + .id = ort_to_lsaid(p, nf), + .opts = oa ? (pbit ? OPT_P : 0) : OPT_E, + .nf = nf + }; + + if (ospf_is_v2(p)) + prepare_ext2_lsa_body(p, nf->fn.pxlen, metric, ebit, fwaddr, tag); + else + prepare_ext3_lsa_body(p, nf, metric, ebit, fwaddr, tag, oa && pbit); - u32 *buf = lsa_get_ipv6_prefix(ext->rest, &prefix, &pxlen, &pxopts, &rest); + ospf_originate_lsa(p, &lsa); +} - /* LSAID collision */ - if ((fn->pxlen != pxlen) || !ipa_equal(fn->prefix, prefix)) - return -1; +static struct top_hash_entry * +ospf_hash_find_(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type); - if (en->lsa.sn == LSA_MAXSEQNO) - return 0; +static void +ospf_flush_ext_lsa(struct ospf_proto *p, struct ospf_area *oa, ort *nf) +{ + struct top_hash_entry *en; - u32 rt_metric = ext->metric & METRIC_MASK; - ip_addr rt_fwaddr = IPA_NONE; - u32 rt_tag = 0; + u32 type = oa ? LSA_T_NSSA : LSA_T_EXT; + u32 dom = oa ? oa->areaid : 0; + u32 id = ort_to_lsaid(p, nf); - if (ext->metric & LSA_EXT_FBIT) - buf = lsa_get_ipv6_addr(buf, &rt_fwaddr); + en = ospf_hash_find_(p->gr, dom, id, p->router_id, type); - if (ext->metric & LSA_EXT_TBIT) - rt_tag = *buf++; + if (!en || (en->nf != nf)) + return; - return (rt_metric == metric) && ipa_equal(rt_fwaddr, fwaddr) && (rt_tag == tag); + ospf_flush_lsa(p, en); } +static inline int +use_gw_for_fwaddr(struct ospf_proto *p, ip_addr gw, struct iface *iface) +{ + struct ospf_iface *ifa; -#endif + if (ipa_zero(gw) || ipa_is_link_local(gw)) + return 0; + + WALK_LIST(ifa, p->iface_list) + if ((ifa->iface == iface) && + (!ospf_is_v2(p) || ipa_in_net(gw, ifa->addr->prefix, ifa->addr->pxlen))) + return 1; + + return 0; +} static inline ip_addr -find_surrogate_fwaddr(struct ospf_area *oa) +find_surrogate_fwaddr(struct ospf_proto *p, struct ospf_area *oa) { - struct proto_ospf *po = oa->po; struct ospf_iface *ifa; struct ifa *a, *cur_addr = NULL; int np, cur_np = 0; - WALK_LIST(ifa, po->iface_list) + /* RFC 3101 2.3 - surrogate forwarding address selection */ + + WALK_LIST(ifa, p->iface_list) { if ((ifa->oa != oa) || (ifa->type == OSPF_IT_VLINK)) continue; -#ifdef OSPFv2 - a = ifa->addr; - if (a->flags & IA_PEER) - continue; - - np = ((a->flags & IA_HOST) || ifa->stub) ? 2 : 1; - if (np > cur_np) + if (ospf_is_v2(p)) { - cur_addr = a; - cur_np = np; - } - -#else /* OSPFv3 */ - WALK_LIST(a, ifa->iface->addrs) - { - if ((a->flags & IA_SECONDARY) || - (a->flags & IA_PEER) || - (a->scope <= SCOPE_LINK)) + a = ifa->addr; + if (a->flags & IA_PEER) continue; - np = ((a->flags & IA_HOST) || ifa->stub) ? 2 : 1; + np = (a->flags & IA_HOST) ? 3 : (ifa->stub ? 2 : 1); if (np > cur_np) { cur_addr = a; cur_np = np; } } -#endif + else /* OSPFv3 */ + { + WALK_LIST(a, ifa->iface->addrs) + { + if ((a->flags & IA_SECONDARY) || + (a->flags & IA_PEER) || + (a->scope <= SCOPE_LINK)) + continue; + + np = (a->flags & IA_HOST) ? 3 : (ifa->stub ? 2 : 1); + if (np > cur_np) + { + cur_addr = a; + cur_np = np; + } + } + } } return cur_addr ? cur_addr->ip : IPA_NONE; } - -/** - * originate_ext_lsa - new route received from nest and filters - * @oa: ospf_area for which LSA is originated - * @fn: network prefix and mask - * @src: the source of origination of the LSA (EXT_EXPORT/EXT_NSSA) - * @metric: the metric of a route - * @fwaddr: the forwarding address - * @tag: the route tag - * @pbit: P-bit for NSSA LSAs, ignored for external LSAs - * - * If I receive a message that new route is installed, I try to originate an - * external LSA. If @oa is an NSSA area, NSSA-LSA is originated instead. - * @oa should not be a stub area. @src does not specify whether the LSA - * is external or NSSA, but it specifies the source of origination - - * the export from ospf_rt_notify(), or the NSSA-EXT translation. - * - * The function also sets flag ebit. If it's the first time, the new router lsa - * origination is necessary. - */ void -originate_ext_lsa(struct ospf_area *oa, struct fib_node *fn, int src, - u32 metric, ip_addr fwaddr, u32 tag, int pbit) -{ - struct proto_ospf *po = oa->po; - struct proto *p = &po->proto; - struct ospf_lsa_header lsa; - struct top_hash_entry *en = NULL; - void *body; - int nssa = oa_is_nssa(oa); - u32 dom = nssa ? oa->areaid : 0; - - OSPF_TRACE(D_EVENTS, "Originating %s-LSA for %I/%d", - nssa ? "NSSA" : "AS-external", fn->prefix, fn->pxlen); - - lsa.age = 0; -#ifdef OSPFv2 - lsa.options = nssa ? (pbit ? OPT_P : 0) : OPT_E; -#endif - lsa.type = nssa ? LSA_T_NSSA : LSA_T_EXT; - lsa.id = fibnode_to_lsaid(po, fn); - lsa.rt = po->router_id; - - if (nssa && pbit && ipa_zero(fwaddr)) - { - /* NSSA-LSA with P-bit set must have non-zero forwarding address */ +ospf_rt_notify(struct proto *P, rtable *tbl UNUSED, net *n, rte *new, rte *old UNUSED, ea_list *ea) +{ + struct ospf_proto *p = (struct ospf_proto *) P; + struct ospf_area *oa = NULL; /* non-NULL for NSSA-LSA */ + ort *nf; - fwaddr = find_surrogate_fwaddr(oa); - if (ipa_zero(fwaddr)) - { - log(L_ERR "%s: Cannot find forwarding address for NSSA-LSA %I/%d", - p->name, fn->prefix, fn->pxlen); - return; - } - } + /* + * There are several posibilities: + * 1) router in regular area - originate external LSA with global scope + * 2) router in NSSA area - originate area-specific NSSA-LSA + * 3) router in stub area - cannot export routes + * 4) area border router - same as (1), it is attached to backbone + */ - if ((en = ospf_hash_find_header(po->gr, dom, &lsa)) != NULL) + if ((p->areano == 1) && oa_is_nssa(HEAD(p->area_list))) + oa = HEAD(p->area_list); + + if (!new) { - int rv = check_ext_lsa(en, fn, metric, fwaddr, tag); - if (rv < 0) - { - log(L_ERR "%s: LSAID collision for %I/%d", - p->name, fn->prefix, fn->pxlen); - return; - } + nf = (ort *) fib_find(&p->rtf, &n->n.prefix, n->n.pxlen); - if (rv > 0) + if (!nf || !nf->external_rte) return; + + ospf_flush_ext_lsa(p, oa, nf); + nf->external_rte = 0; + + /* Old external route might blocked some NSSA translation */ + if ((p->areano > 1) && rt_is_nssa(nf) && nf->n.oa->translate) + ospf_schedule_rtcalc(p); + + return; } - lsa.sn = get_seqnum(en); - body = originate_ext_lsa_body(po, &lsa.length, fn, metric, fwaddr, tag, pbit); - lsasum_calculate(&lsa, body); + ASSERT(p->asbr); + + /* Get route attributes */ + rta *a = new->attrs; + u32 m1 = ea_get_int(ea, EA_OSPF_METRIC1, LSINFINITY); + u32 m2 = ea_get_int(ea, EA_OSPF_METRIC2, 10000); + int ebit = (m1 == LSINFINITY); + u32 metric = ebit ? m2 : m1; + u32 tag = ea_get_int(ea, EA_OSPF_TAG, 0); + ip_addr fwd = IPA_NONE; - if (src) - fn->x1 = src; - lsa_install_new(po, &lsa, dom, body); - ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1); + if ((a->dest == RTD_ROUTER) && use_gw_for_fwaddr(p, a->gw, a->iface)) + fwd = a->gw; - if (po->ebit == 0) + /* NSSA-LSA with P-bit set must have non-zero forwarding address */ + if (oa && ipa_zero(fwd)) { - po->ebit = 1; - WALK_LIST(oa, po->area_list) + fwd = find_surrogate_fwaddr(p, oa); + + if (ipa_zero(fwd)) { - schedule_rt_lsa(oa); + log(L_ERR "%s: Cannot find forwarding address for NSSA-LSA %I/%d", + p->p.name, n->n.prefix, n->n.pxlen); + return; } } -} - -void -flush_ext_lsa(struct ospf_area *oa, struct fib_node *fn, int nssa) -{ - struct proto_ospf *po = oa->po; - struct proto *p = &po->proto; - struct top_hash_entry *en; - u32 dom = nssa ? oa->areaid : 0; - u32 type = nssa ? LSA_T_NSSA : LSA_T_EXT; - u32 lsaid = fibnode_to_lsaid(po, fn); + nf = (ort *) fib_get(&p->rtf, &n->n.prefix, n->n.pxlen); + ospf_originate_ext_lsa(p, oa, nf, LSA_M_EXPORT, metric, ebit, fwd, tag, 1); + nf->external_rte = 1; +} - if (en = ospf_hash_find(po->gr, dom, lsaid, po->router_id, type)) - { - OSPF_TRACE(D_EVENTS, "Flushing %s-LSA for %I/%d", - nssa ? "NSSA" : "AS-external", fn->prefix, fn->pxlen); - if (check_ext_lsa(en, fn, 0, IPA_NONE, 0) < 0) - { - log(L_ERR "%s: LSAID collision for %I/%d", - p->name, fn->prefix, fn->pxlen); - return; - } +/* + * Link-LSA handling (assume OSPFv3) + * Type = LSA_T_LINK + */ - fn->x1 = 0; - ospf_lsupd_flush_nlsa(po, en); - } +static inline void +lsab_put_prefix(struct ospf_proto *p, ip_addr prefix, u32 pxlen, u32 cost) +{ + void *buf = lsab_alloc(p, IPV6_PREFIX_SPACE(pxlen)); + u8 flags = (pxlen < MAX_PREFIX_LENGTH) ? 0 : OPT_PX_LA; + put_ipv6_prefix(buf, prefix, pxlen, flags, cost); } - -#ifdef OSPFv3 - -static void * -originate_link_lsa_body(struct ospf_iface *ifa, u16 *length) +static void +prepare_link_lsa_body(struct ospf_proto *p, struct ospf_iface *ifa) { - struct proto_ospf *po = ifa->oa->po; struct ospf_lsa_link *ll; int i = 0; - u8 flags; - ASSERT(po->lsab_used == 0); - ll = lsab_allocz(po, sizeof(struct ospf_lsa_link)); + ASSERT(p->lsab_used == 0); + ll = lsab_allocz(p, sizeof(struct ospf_lsa_link)); ll->options = ifa->oa->options | (ifa->priority << 24); - ll->lladdr = ifa->addr->ip; + ll->lladdr = ipa_to_ip6(ifa->addr->ip); ll = NULL; /* buffer might be reallocated later */ struct ifa *a; WALK_LIST(a, ifa->iface->addrs) - { - if ((a->flags & IA_SECONDARY) || - (a->scope < SCOPE_SITE)) - continue; + { + if ((a->flags & IA_SECONDARY) || + (a->scope < SCOPE_SITE)) + continue; - flags = (a->pxlen < MAX_PREFIX_LENGTH) ? 0 : OPT_PX_LA; - put_ipv6_prefix(lsab_alloc(po, IPV6_PREFIX_SPACE(a->pxlen)), - a->ip, a->pxlen, flags, 0); - i++; - } + lsab_put_prefix(p, a->prefix, a->pxlen, 0); + i++; + } - ll = po->lsab; + ll = p->lsab; ll->pxcount = i; - *length = po->lsab_used + sizeof(struct ospf_lsa_header); - return lsab_flush(po); } -void -originate_link_lsa(struct ospf_iface *ifa) +static void +ospf_originate_link_lsa(struct ospf_proto *p, struct ospf_iface *ifa) { - struct ospf_lsa_header lsa; - struct proto_ospf *po = ifa->oa->po; - struct proto *p = &po->proto; - void *body; - - /* Vlinks do not have link-LSAs */ - if (ifa->type == OSPF_IT_VLINK) + if (ospf_is_v2(p)) return; - OSPF_TRACE(D_EVENTS, "Originating link-LSA for iface %s", ifa->ifname); + struct ospf_new_lsa lsa = { + .type = LSA_T_LINK, + .dom = ifa->iface_id, + .id = ifa->iface_id, + .ifa = ifa + }; - lsa.age = 0; - lsa.type = LSA_T_LINK; - lsa.id = ifa->iface_id; - lsa.rt = po->router_id; - lsa.sn = get_seqnum(ifa->link_lsa); - u32 dom = ifa->iface_id; + OSPF_TRACE(D_EVENTS, "Updating link state for %s (Id: %R)", ifa->ifname, lsa.id); - body = originate_link_lsa_body(ifa, &lsa.length); - lsasum_calculate(&lsa, body); - ifa->link_lsa = lsa_install_new(po, &lsa, dom, body); - ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1); + prepare_link_lsa_body(p, ifa); - /* Just to be sure to not forget on our link LSA */ - if (ifa->state == OSPF_IS_DR) - schedule_net_lsa(ifa); + ifa->link_lsa = ospf_originate_lsa(p, &lsa); } -void -update_link_lsa(struct ospf_iface *ifa) -{ - if (ifa->link_lsa && ((ifa->link_lsa->inst_t + MINLSINTERVAL) > now)) - return; - /* - * It's too early to originate new link LSA. We will - * try to do it next tick - */ - originate_link_lsa(ifa); - ifa->origlink = 0; -} -static inline void -lsa_put_prefix(struct proto_ospf *po, ip_addr prefix, u32 pxlen, u32 cost) -{ - put_ipv6_prefix(lsab_alloc(po, IPV6_PREFIX_SPACE(pxlen)), prefix, pxlen, - (pxlen < MAX_PREFIX_LENGTH) ? 0 : OPT_PX_LA, cost); -} +/* + * Prefix-Rt-LSA handling (assume OSPFv3) + * Type = LSA_T_PREFIX, referred type = LSA_T_RT + */ -static void * -originate_prefix_rt_lsa_body(struct ospf_area *oa, u16 *length) +static void +prepare_prefix_rt_lsa_body(struct ospf_proto *p, struct ospf_area *oa) { - struct proto_ospf *po = oa->po; - struct ospf_config *cf = (struct ospf_config *) (po->proto.cf); + struct ospf_config *cf = (struct ospf_config *) (p->p.cf); struct ospf_iface *ifa; struct ospf_lsa_prefix *lp; int host_addr = 0; int net_lsa; int i = 0; - ASSERT(po->lsab_used == 0); - lp = lsab_allocz(po, sizeof(struct ospf_lsa_prefix)); + ASSERT(p->lsab_used == 0); + lp = lsab_allocz(p, sizeof(struct ospf_lsa_prefix)); lp->ref_type = LSA_T_RT; lp->ref_id = 0; - lp->ref_rt = po->router_id; + lp->ref_rt = p->router_id; lp = NULL; /* buffer might be reallocated later */ - WALK_LIST(ifa, po->iface_list) + WALK_LIST(ifa, p->iface_list) { if ((ifa->oa != oa) || (ifa->type == OSPF_IT_VLINK) || (ifa->state == OSPF_IS_DOWN)) continue; @@ -1286,47 +1400,46 @@ originate_prefix_rt_lsa_body(struct ospf_area *oa, u16 *length) struct ifa *a; WALK_LIST(a, ifa->iface->addrs) - { - if ((a->flags & IA_SECONDARY) || - (a->flags & IA_PEER) || - (a->scope <= SCOPE_LINK)) - continue; + { + if ((a->flags & IA_SECONDARY) || + (a->flags & IA_PEER) || + (a->scope <= SCOPE_LINK)) + continue; - if (((a->pxlen < MAX_PREFIX_LENGTH) && net_lsa) || - configured_stubnet(oa, a)) - continue; + if (((a->pxlen < MAX_PREFIX_LENGTH) && net_lsa) || + configured_stubnet(oa, a)) + continue; - if ((a->flags & IA_HOST) || - (ifa->state == OSPF_IS_LOOP) || - (ifa->type == OSPF_IT_PTMP)) - { - lsa_put_prefix(po, a->ip, MAX_PREFIX_LENGTH, 0); - host_addr = 1; - } - else - lsa_put_prefix(po, a->prefix, a->pxlen, ifa->cost); - i++; + if ((a->flags & IA_HOST) || + (ifa->state == OSPF_IS_LOOP) || + (ifa->type == OSPF_IT_PTMP)) + { + lsab_put_prefix(p, a->ip, MAX_PREFIX_LENGTH, 0); + host_addr = 1; } + else + lsab_put_prefix(p, a->prefix, a->pxlen, ifa->cost); + i++; + } ifa->px_pos_end = i; } struct ospf_stubnet_config *sn; - if (oa->ac) - WALK_LIST(sn, oa->ac->stubnet_list) - if (!sn->hidden) - { - lsa_put_prefix(po, sn->px.addr, sn->px.len, sn->cost); - if (sn->px.len == MAX_PREFIX_LENGTH) - host_addr = 1; - i++; - } + WALK_LIST(sn, oa->ac->stubnet_list) + if (!sn->hidden) + { + lsab_put_prefix(p, sn->px.addr, sn->px.len, sn->cost); + if (sn->px.len == MAX_PREFIX_LENGTH) + host_addr = 1; + i++; + } /* If there are some configured vlinks, find some global address (even from another area), which will be used as a vlink endpoint. */ if (!EMPTY_LIST(cf->vlink_list) && !host_addr) { - WALK_LIST(ifa, po->iface_list) + WALK_LIST(ifa, p->iface_list) { if ((ifa->type == OSPF_IT_VLINK) || (ifa->state == OSPF_IS_DOWN)) continue; @@ -1338,7 +1451,7 @@ originate_prefix_rt_lsa_body(struct ospf_area *oa, u16 *length) continue; /* Found some IP */ - lsa_put_prefix(po, a->ip, MAX_PREFIX_LENGTH, 0); + lsab_put_prefix(p, a->ip, MAX_PREFIX_LENGTH, 0); i++; goto done; } @@ -1346,36 +1459,33 @@ originate_prefix_rt_lsa_body(struct ospf_area *oa, u16 *length) } done: - lp = po->lsab; + lp = p->lsab; lp->pxcount = i; - *length = po->lsab_used + sizeof(struct ospf_lsa_header); - return lsab_flush(po); } -void -originate_prefix_rt_lsa(struct ospf_area *oa) +static void +ospf_originate_prefix_rt_lsa(struct ospf_proto *p, struct ospf_area *oa) { - struct proto_ospf *po = oa->po; - struct proto *p = &po->proto; - struct ospf_lsa_header lsa; - void *body; + if (ospf_is_v2(p)) + return; - OSPF_TRACE(D_EVENTS, "Originating router prefix-LSA for area %R", oa->areaid); + struct ospf_new_lsa lsa = { + .type = LSA_T_PREFIX, + .dom = oa->areaid, + .id = 0 + }; - lsa.age = 0; - lsa.type = LSA_T_PREFIX; - lsa.id = 0; - lsa.rt = po->router_id; - lsa.sn = get_seqnum(oa->pxr_lsa); - u32 dom = oa->areaid; + prepare_prefix_rt_lsa_body(p, oa); - body = originate_prefix_rt_lsa_body(oa, &lsa.length); - lsasum_calculate(&lsa, body); - oa->pxr_lsa = lsa_install_new(po, &lsa, dom, body); - ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1); + ospf_originate_lsa(p, &lsa); } +/* + * Prefix-Net-LSA handling (assume OSPFv3) + * Type = LSA_T_PREFIX, referred type = LSA_T_NET + */ + static inline int prefix_space(u32 *buf) { @@ -1389,7 +1499,7 @@ prefix_same(u32 *b1, u32 *b2) int pxl1 = *b1 >> 24; int pxl2 = *b2 >> 24; int pxs, i; - + if (pxl1 != pxl2) return 0; @@ -1410,9 +1520,9 @@ prefix_advance(u32 *buf) /* FIXME eliminate items with LA bit set? see 4.4.3.9 */ static void -add_prefix(struct proto_ospf *po, u32 *px, int offset, int *pxc) +add_prefix(struct ospf_proto *p, u32 *px, int offset, int *pxc) { - u32 *pxl = lsab_offset(po, offset); + u32 *pxl = lsab_offset(p, offset); int i; for (i = 0; i < *pxc; pxl = prefix_advance(pxl), i++) if (prefix_same(px, pxl)) @@ -1422,19 +1532,18 @@ add_prefix(struct proto_ospf *po, u32 *px, int offset, int *pxc) return; } - ASSERT(pxl == lsab_end(po)); + ASSERT(pxl == lsab_end(p)); int pxspace = prefix_space(px); - pxl = lsab_alloc(po, pxspace); + pxl = lsab_alloc(p, pxspace); memcpy(pxl, px, pxspace); *pxl &= 0xFFFF0000; /* Set metric to zero */ (*pxc)++; } static void -add_link_lsa(struct proto_ospf *po, struct top_hash_entry *en, int offset, int *pxc) +add_link_lsa(struct ospf_proto *p, struct ospf_lsa_link *ll, int offset, int *pxc) { - struct ospf_lsa_link *ll = en->lsa_body; u32 *pxb = ll->rest; int j; @@ -1451,92 +1560,129 @@ add_link_lsa(struct proto_ospf *po, struct top_hash_entry *en, int offset, int * if ((pxlen >= 10) && ((pxb[1] & 0xffc00000) == 0xfe800000)) continue; - add_prefix(po, pxb, offset, pxc); + add_prefix(p, pxb, offset, pxc); } } - - -static void * -originate_prefix_net_lsa_body(struct ospf_iface *ifa, u16 *length) +static void +prepare_prefix_net_lsa_body(struct ospf_proto *p, struct ospf_iface *ifa) { - struct proto_ospf *po = ifa->oa->po; struct ospf_lsa_prefix *lp; struct ospf_neighbor *n; struct top_hash_entry *en; int pxc, offset; - ASSERT(po->lsab_used == 0); - lp = lsab_allocz(po, sizeof(struct ospf_lsa_prefix)); + ASSERT(p->lsab_used == 0); + lp = lsab_allocz(p, sizeof(struct ospf_lsa_prefix)); lp->ref_type = LSA_T_NET; lp->ref_id = ifa->net_lsa->lsa.id; - lp->ref_rt = po->router_id; + lp->ref_rt = p->router_id; lp = NULL; /* buffer might be reallocated later */ pxc = 0; - offset = po->lsab_used; + offset = p->lsab_used; /* Find all Link LSAs associated with the link and merge their prefixes */ - if (ifa->link_lsa) - add_link_lsa(po, ifa->link_lsa, offset, &pxc); + if (en = ifa->link_lsa) + add_link_lsa(p, en->next_lsa_body ?: en->lsa_body, offset, &pxc); WALK_LIST(n, ifa->neigh_list) if ((n->state == NEIGHBOR_FULL) && - (en = ospf_hash_find(po->gr, ifa->iface_id, n->iface_id, n->rid, LSA_T_LINK))) - add_link_lsa(po, en, offset, &pxc); + (en = ospf_hash_find(p->gr, ifa->iface_id, n->iface_id, n->rid, LSA_T_LINK))) + add_link_lsa(p, en->lsa_body, offset, &pxc); - lp = po->lsab; + lp = p->lsab; lp->pxcount = pxc; - *length = po->lsab_used + sizeof(struct ospf_lsa_header); - return lsab_flush(po); } -void -originate_prefix_net_lsa(struct ospf_iface *ifa) +static void +ospf_originate_prefix_net_lsa(struct ospf_proto *p, struct ospf_iface *ifa) { - struct proto_ospf *po = ifa->oa->po; - struct proto *p = &po->proto; - struct ospf_lsa_header lsa; - void *body; + if (ospf_is_v2(p)) + return; - OSPF_TRACE(D_EVENTS, "Originating network prefix-LSA for iface %s", ifa->ifname); + struct ospf_new_lsa lsa = { + .type = LSA_T_PREFIX, + .dom = ifa->oa->areaid, + .id = ifa->iface_id, + .ifa = ifa + }; - lsa.age = 0; - lsa.type = LSA_T_PREFIX; - lsa.id = ifa->iface_id; - lsa.rt = po->router_id; - lsa.sn = get_seqnum(ifa->pxn_lsa); - u32 dom = ifa->oa->areaid; + prepare_prefix_net_lsa_body(p, ifa); - body = originate_prefix_net_lsa_body(ifa, &lsa.length); - lsasum_calculate(&lsa, body); - ifa->pxn_lsa = lsa_install_new(po, &lsa, dom, body); - ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1); + ifa->pxn_lsa = ospf_originate_lsa(p, &lsa); } +static inline int breaks_minlsinterval(struct top_hash_entry *en) +{ return en && (en->lsa.age < LSA_MAXAGE) && ((en->inst_time + MINLSINTERVAL) > now); } + void -flush_prefix_net_lsa(struct ospf_iface *ifa) +ospf_update_topology(struct ospf_proto *p) { - struct proto_ospf *po = ifa->oa->po; - struct proto *p = &po->proto; - struct top_hash_entry *en = ifa->pxn_lsa; - u32 dom = ifa->oa->areaid; + struct ospf_area *oa; + struct ospf_iface *ifa; - if (en == NULL) - return; + WALK_LIST(oa, p->area_list) + { + if (oa->update_rt_lsa) + { + /* + * Generally, MinLSInterval is enforced in ospf_do_originate_lsa(), but + * origination of (prefix) router LSA is a special case. We do not want to + * prepare a new router LSA body and then postpone it in en->next_lsa_body + * for later origination, because there are side effects (updates of + * rt_pos_* and px_pos_* in ospf_iface structures) during that, which may + * confuse routing table calculation if executed after LSA body + * preparation but before final LSA origination (as rtcalc would use + * current rt_pos_* indexes but the old router LSA body). + * + * Here, we ensure that MinLSInterval is observed and we do not even try + * to originate these LSAs if it is not. Therefore, origination, when + * requested, will succeed unless there is also a seqnum wrapping, which + * is not a problem because in that case rtcalc is blocked by MaxAge. + */ + + if (breaks_minlsinterval(oa->rt) || breaks_minlsinterval(oa->pxr_lsa)) + continue; - OSPF_TRACE(D_EVENTS, "Flushing network prefix-LSA for iface %s", ifa->ifname); + ospf_originate_rt_lsa(p, oa); + ospf_originate_prefix_rt_lsa(p, oa); + oa->update_rt_lsa = 0; + } + } - en->lsa.sn += 1; - en->lsa.age = LSA_MAXAGE; - lsasum_calculate(&en->lsa, en->lsa_body); - ospf_lsupd_flood(po, NULL, NULL, &en->lsa, dom, 0); - flush_lsa(en, po); - ifa->pxn_lsa = NULL; -} + WALK_LIST(ifa, p->iface_list) + { + if (ifa->type == OSPF_IT_VLINK) + continue; + if (ifa->update_link_lsa) + { + if ((ifa->state > OSPF_IS_LOOP) && !ifa->link_lsa_suppression) + ospf_originate_link_lsa(p, ifa); + else + ospf_flush2_lsa(p, &ifa->link_lsa); -#endif + ifa->update_link_lsa = 0; + } + + if (ifa->update_net_lsa) + { + if ((ifa->state == OSPF_IS_DR) && (ifa->fadj > 0)) + { + ospf_originate_net_lsa(p, ifa); + ospf_originate_prefix_net_lsa(p, ifa); + } + else + { + ospf_flush2_lsa(p, &ifa->net_lsa); + ospf_flush2_lsa(p, &ifa->pxn_lsa); + } + + ifa->update_net_lsa = 0; + } + } +} static void @@ -1574,7 +1720,7 @@ ospf_top_hash_u32(u32 a) return a; } -static inline unsigned +static uint ospf_top_hash(struct top_graph *f, u32 domain, u32 lsaid, u32 rtrid, u32 type) { /* In OSPFv2, we don't know Router ID when looking for network LSAs. @@ -1582,14 +1728,8 @@ ospf_top_hash(struct top_graph *f, u32 domain, u32 lsaid, u32 rtrid, u32 type) In both cases, there is (usually) just one (or small number) appropriate LSA, so we just clear unknown part of key. */ - return ( -#ifdef OSPFv2 - ((type == LSA_T_NET) ? 0 : ospf_top_hash_u32(rtrid)) + - ospf_top_hash_u32(lsaid) + -#else /* OSPFv3 */ - ospf_top_hash_u32(rtrid) + - ((type == LSA_T_RT) ? 0 : ospf_top_hash_u32(lsaid)) + -#endif + return (((f->ospf2 && (type == LSA_T_NET)) ? 0 : ospf_top_hash_u32(rtrid)) + + ((!f->ospf2 && (type == LSA_T_RT)) ? 0 : ospf_top_hash_u32(lsaid)) + type + domain) & f->hash_mask; /* @@ -1600,13 +1740,15 @@ ospf_top_hash(struct top_graph *f, u32 domain, u32 lsaid, u32 rtrid, u32 type) /** * ospf_top_new - allocated new topology database - * @p: current instance of ospf + * @p: OSPF protocol instance + * @pool: pool for allocation * - * this dynamically hashed structure is often used for keeping lsas. mainly - * its used in @ospf_area structure. + * This dynamically hashed structure is used for keeping LSAs. Mainly it is used + * for the LSA database of the OSPF protocol, but also for LSA retransmission + * and request lists of OSPF neighbors. */ struct top_graph * -ospf_top_new(pool *pool) +ospf_top_new(struct ospf_proto *p, pool *pool) { struct top_graph *f; @@ -1617,6 +1759,7 @@ ospf_top_new(pool *pool) ospf_top_ht_alloc(f); f->hash_entries = 0; f->hash_entries_min = 0; + f->ospf2 = ospf_is_v2(p); return f; } @@ -1631,8 +1774,8 @@ ospf_top_free(struct top_graph *f) static void ospf_top_rehash(struct top_graph *f, int step) { - unsigned int oldn, oldh; struct top_hash_entry **n, **oldt, **newt, *e, *x; + uint oldn, oldh; oldn = f->hash_size; oldt = f->hash_table; @@ -1648,7 +1791,7 @@ ospf_top_rehash(struct top_graph *f, int step) while (e) { x = e->next; - n = newt + ospf_top_hash(f, e->domain, e->lsa.id, e->lsa.rt, e->lsa.type); + n = newt + ospf_top_hash(f, e->domain, e->lsa.id, e->lsa.rt, e->lsa_type); e->next = *n; *n = e; e = x; @@ -1657,124 +1800,94 @@ ospf_top_rehash(struct top_graph *f, int step) ospf_top_ht_free(oldt); } -#ifdef OSPFv2 - -u32 -ospf_lsa_domain(u32 type, struct ospf_iface *ifa) -{ - return (type == LSA_T_EXT) ? 0 : ifa->oa->areaid; -} - -#else /* OSPFv3 */ - -u32 -ospf_lsa_domain(u32 type, struct ospf_iface *ifa) -{ - switch (type & LSA_SCOPE_MASK) - { - case LSA_SCOPE_LINK: - return ifa->iface_id; - - case LSA_SCOPE_AREA: - return ifa->oa->areaid; - - case LSA_SCOPE_AS: - default: - return 0; - } -} - -#endif - -struct top_hash_entry * -ospf_hash_find_header(struct top_graph *f, u32 domain, struct ospf_lsa_header *h) -{ - return ospf_hash_find(f, domain, h->id, h->rt, h->type); -} - -struct top_hash_entry * -ospf_hash_get_header(struct top_graph *f, u32 domain, struct ospf_lsa_header *h) -{ - return ospf_hash_get(f, domain, h->id, h->rt, h->type); -} - -struct top_hash_entry * -ospf_hash_find(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type) +static struct top_hash_entry * +ospf_hash_find_(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type) { struct top_hash_entry *e; e = f->hash_table[ospf_top_hash(f, domain, lsa, rtr, type)]; - while (e && (e->lsa.id != lsa || e->lsa.type != type || e->lsa.rt != rtr || e->domain != domain)) + while (e && (e->lsa.id != lsa || e->lsa.rt != rtr || + e->lsa_type != type || e->domain != domain)) e = e->next; return e; } - -#ifdef OSPFv2 - -/* In OSPFv2, sometimes we don't know Router ID when looking for network LSAs. - There should be just one, so we find any match. */ struct top_hash_entry * -ospf_hash_find_net(struct top_graph *f, u32 domain, u32 lsa) +ospf_hash_find(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type) { - struct top_hash_entry *e; - e = f->hash_table[ospf_top_hash(f, domain, lsa, 0, LSA_T_NET)]; - - while (e && (e->lsa.id != lsa || e->lsa.type != LSA_T_NET || e->domain != domain)) - e = e->next; + struct top_hash_entry *e = ospf_hash_find_(f, domain, lsa, rtr, type); - return e; + /* Hide hash entry with empty lsa_body */ + return (e && e->lsa_body) ? e : NULL; } -#endif - - -#ifdef OSPFv3 - -/* In OSPFv3, usually we don't know LSA ID when looking for router - LSAs. We return matching LSA with smallest LSA ID. */ +/* In OSPFv2, lsa.id is the same as lsa.rt for router LSA. In OSPFv3, we don't know + lsa.id when looking for router LSAs. We return matching LSA with smallest lsa.id. */ struct top_hash_entry * ospf_hash_find_rt(struct top_graph *f, u32 domain, u32 rtr) { struct top_hash_entry *rv = NULL; struct top_hash_entry *e; - e = f->hash_table[ospf_top_hash(f, domain, 0, rtr, LSA_T_RT)]; - + /* We can put rtr for lsa.id to hash fn, it is ignored in OSPFv3 */ + e = f->hash_table[ospf_top_hash(f, domain, rtr, rtr, LSA_T_RT)]; + while (e) + { + if (e->lsa.rt == rtr && e->lsa_type == LSA_T_RT && e->domain == domain && e->lsa_body) { - if (e->lsa.rt == rtr && e->lsa.type == LSA_T_RT && e->domain == domain) - if (!rv || e->lsa.id < rv->lsa.id) - rv = e; - e = e->next; + if (f->ospf2 && (e->lsa.id == rtr)) + return e; + if (!f->ospf2 && (!rv || e->lsa.id < rv->lsa.id)) + rv = e; } + e = e->next; + } return rv; } +/* + * ospf_hash_find_rt3_first() and ospf_hash_find_rt3_next() are used exclusively + * for lsa_walk_rt_init(), lsa_walk_rt(), therefore they skip MaxAge entries. + */ static inline struct top_hash_entry * -find_matching_rt(struct top_hash_entry *e, u32 domain, u32 rtr) +find_matching_rt3(struct top_hash_entry *e, u32 domain, u32 rtr) { - while (e && (e->lsa.rt != rtr || e->lsa.type != LSA_T_RT || e->domain != domain)) + while (e && (e->lsa.rt != rtr || e->lsa_type != LSA_T_RT || + e->domain != domain || e->lsa.age == LSA_MAXAGE)) e = e->next; return e; } struct top_hash_entry * -ospf_hash_find_rt_first(struct top_graph *f, u32 domain, u32 rtr) +ospf_hash_find_rt3_first(struct top_graph *f, u32 domain, u32 rtr) { struct top_hash_entry *e; e = f->hash_table[ospf_top_hash(f, domain, 0, rtr, LSA_T_RT)]; - return find_matching_rt(e, domain, rtr); + return find_matching_rt3(e, domain, rtr); } struct top_hash_entry * -ospf_hash_find_rt_next(struct top_hash_entry *e) +ospf_hash_find_rt3_next(struct top_hash_entry *e) { - return find_matching_rt(e->next, e->domain, e->lsa.rt); + return find_matching_rt3(e->next, e->domain, e->lsa.rt); } -#endif +/* In OSPFv2, we don't know Router ID when looking for network LSAs. + There should be just one, so we find any match. */ +struct top_hash_entry * +ospf_hash_find_net2(struct top_graph *f, u32 domain, u32 id) +{ + struct top_hash_entry *e; + e = f->hash_table[ospf_top_hash(f, domain, id, 0, LSA_T_NET)]; + + while (e && (e->lsa.id != id || e->lsa_type != LSA_T_NET || + e->domain != domain || e->lsa_body == NULL)) + e = e->next; + + return e; +} struct top_hash_entry * @@ -1786,21 +1899,23 @@ ospf_hash_get(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type) ee = f->hash_table + ospf_top_hash(f, domain, lsa, rtr, type); e = *ee; - while (e && (e->lsa.id != lsa || e->lsa.rt != rtr || e->lsa.type != type || e->domain != domain)) + while (e && (e->lsa.id != lsa || e->lsa.rt != rtr || + e->lsa_type != type || e->domain != domain)) e = e->next; if (e) return e; e = sl_alloc(f->hash_slab); + bzero(e, sizeof(struct top_hash_entry)); + e->color = OUTSPF; e->dist = LSINFINITY; - e->nhs = NULL; - e->lb = IPA_NONE; + e->lsa.type_raw = type; e->lsa.id = lsa; e->lsa.rt = rtr; - e->lsa.type = type; - e->lsa_body = NULL; + e->lsa.sn = LSA_ZEROSEQNO; + e->lsa_type = type; e->domain = domain; e->next = *ee; *ee = e; @@ -1812,8 +1927,8 @@ ospf_hash_get(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type) void ospf_hash_delete(struct top_graph *f, struct top_hash_entry *e) { - struct top_hash_entry **ee = f->hash_table + - ospf_top_hash(f, e->domain, e->lsa.id, e->lsa.rt, e->lsa.type); + struct top_hash_entry **ee = f->hash_table + + ospf_top_hash(f, e->domain, e->lsa.id, e->lsa.rt, e->lsa_type); while (*ee) { @@ -1853,7 +1968,7 @@ ospf_dump_lsa(struct top_hash_entry *he, struct proto *p) rr = (struct ospf_lsa_rt_link *) (rt + 1); for (i = 0; i < lsa_rt_items(&he->lsa); i++) - OSPF_TRACE(D_EVENTS, " - %1x %-1R %-1R %5u", + OSPF_TRACE(D_EVENTS, " - %1x %-1R %-1R %5u", rr[i].type, rr[i].id, rr[i].data, rr[i].metric); break; @@ -1862,7 +1977,7 @@ ospf_dump_lsa(struct top_hash_entry *he, struct proto *p) rts = (u32 *) (ln + 1); for (i = 0; i < lsa_net_items(&he->lsa); i++) - OSPF_TRACE(D_EVENTS, " - %-1R", rts[i]); + OSPF_TRACE(D_EVENTS, " - %-1R", rts[i]); break; default: @@ -1873,7 +1988,7 @@ ospf_dump_lsa(struct top_hash_entry *he, struct proto *p) void ospf_top_dump(struct top_graph *f, struct proto *p) { - unsigned int i; + uint i; OSPF_TRACE(D_EVENTS, "Hash entries: %d", f->hash_entries); for (i = 0; i < f->hash_size; i++) @@ -1884,30 +1999,3 @@ ospf_top_dump(struct top_graph *f, struct proto *p) } } */ - -/* This is very inefficient, please don't call it often */ - -/* I should also test for every LSA if it's in some link state - * retransmission list for every neighbor. I will not test it. - * It could happen that I'll receive some strange ls ack's. - */ - -int -can_flush_lsa(struct proto_ospf *po) -{ - struct ospf_iface *ifa; - struct ospf_neighbor *n; - - WALK_LIST(ifa, po->iface_list) - { - WALK_LIST(n, ifa->neigh_list) - { - if ((n->state == NEIGHBOR_EXCHANGE) || (n->state == NEIGHBOR_LOADING)) - return 0; - - break; - } - } - - return 1; -} |