diff options
| -rw-r--r-- | nest/locks.c | 10 | ||||
| -rw-r--r-- | nest/locks.h | 5 | ||||
| -rw-r--r-- | proto/ospf/dbdes.c | 19 | ||||
| -rw-r--r-- | proto/ospf/hello.c | 2 | ||||
| -rw-r--r-- | proto/ospf/iface.c | 17 | ||||
| -rw-r--r-- | proto/ospf/lsack.c | 10 | ||||
| -rw-r--r-- | proto/ospf/lsreq.c | 3 | ||||
| -rw-r--r-- | proto/ospf/lsupd.c | 88 | ||||
| -rw-r--r-- | proto/ospf/neighbor.c | 59 | ||||
| -rw-r--r-- | proto/ospf/ospf.c | 170 | ||||
| -rw-r--r-- | proto/ospf/ospf.h | 533 | ||||
| -rw-r--r-- | proto/ospf/rt.c | 43 | ||||
| -rw-r--r-- | proto/ospf/rt.h | 57 | ||||
| -rw-r--r-- | proto/ospf/topology.c | 340 | ||||
| -rw-r--r-- | proto/ospf/topology.h | 118 |
15 files changed, 781 insertions, 693 deletions
diff --git a/nest/locks.c b/nest/locks.c index 7044d6a9..c74f2f45 100644 --- a/nest/locks.c +++ b/nest/locks.c @@ -22,10 +22,11 @@ * or some other non-shareable resource, it asks the core to lock it and it doesn't * use the resource until it's notified that it has acquired the lock. * - * Object locks are represented by &object_lock structures which are in turn a kind of - * resource. Lockable resources are uniquely determined by resource type + * Object locks are represented by &object_lock structures which are in turn a + * kind of resource. Lockable resources are uniquely determined by resource type * (%OBJLOCK_UDP for a UDP port etc.), IP address (usually a broadcast or - * multicast address the port is bound to), port number and interface. + * multicast address the port is bound to), port number, interface and optional + * instance ID. */ #undef LOCAL_DEBUG @@ -45,6 +46,7 @@ olock_same(struct object_lock *x, struct object_lock *y) x->type == y->type && x->iface == y->iface && x->port == y->port && + x->inst == y->inst && ipa_equal(x->addr, y->addr); } @@ -88,7 +90,7 @@ olock_dump(resource *r) struct object_lock *l = (struct object_lock *) r; static char *olock_states[] = { "free", "locked", "waiting", "event" }; - debug("(%d:%s:%I:%d) [%s]\n", l->type, (l->iface ? l->iface->name : "?"), l->addr, l->port, olock_states[l->state]); + debug("(%d:%s:%I:%d:%d) [%s]\n", l->type, (l->iface ? l->iface->name : "?"), l->addr, l->port, l->inst, olock_states[l->state]); if (!EMPTY_LIST(l->waiters)) debug(" [wanted]\n"); } diff --git a/nest/locks.h b/nest/locks.h index 892d3c6b..3d58c8ed 100644 --- a/nest/locks.h +++ b/nest/locks.h @@ -26,9 +26,10 @@ struct object_lock { resource r; ip_addr addr; /* Identification of a object: IP address */ - unsigned int type; /* ... object type (OBJLOCK_xxx) */ + uint type; /* ... object type (OBJLOCK_xxx) */ + uint port; /* ... port number */ + uint inst; /* ... instance ID */ struct iface *iface; /* ... interface */ - unsigned int port; /* ... port number */ void (*hook)(struct object_lock *); /* Called when the lock succeeds */ void *data; /* User data */ /* ... internal to lock manager, don't touch ... */ diff --git a/proto/ospf/dbdes.c b/proto/ospf/dbdes.c index 1f37965c..62b330ed 100644 --- a/proto/ospf/dbdes.c +++ b/proto/ospf/dbdes.c @@ -200,15 +200,11 @@ ospf_do_send_dbdes(struct ospf_proto *p, struct ospf_neighbor *n) * of the buffer. */ void -ospf_send_dbdes(struct ospf_neighbor *n, int next) +ospf_send_dbdes(struct ospf_proto *p, struct ospf_neighbor *n, int next) { - struct ospf_iface *ifa = n->ifa; - struct ospf_area *oa = ifa->oa; - struct ospf_proto *p = oa->po; - /* RFC 2328 10.8 */ - if (oa->rt == NULL) + if (n->ifa->oa->rt == NULL) return; switch (n->state) @@ -312,6 +308,7 @@ ospf_process_dbdes(struct ospf_proto *p, struct ospf_packet *pkt, struct ospf_ne s_add_tail(&n->lsrql, SNODE req); req->lsa = lsa; + req->lsa_body = LSA_BODY_DUMMY; } } @@ -394,7 +391,7 @@ ospf_receive_dbdes(struct ospf_packet *pkt, struct ospf_iface *ifa, n->imms = rcv_imms; OSPF_TRACE(D_PACKETS, "I'm slave to %I", n->ip); ospf_neigh_sm(n, INM_NEGDONE); - ospf_send_dbdes(n, 1); + ospf_send_dbdes(p, n, 1); break; } @@ -426,7 +423,7 @@ ospf_receive_dbdes(struct ospf_packet *pkt, struct ospf_iface *ifa, if (!(n->myimms & DBDES_MS)) { /* Slave should retransmit dbdes packet */ - ospf_send_dbdes(n, 0); + ospf_send_dbdes(p, n, 0); } return; } @@ -472,7 +469,7 @@ ospf_receive_dbdes(struct ospf_packet *pkt, struct ospf_iface *ifa, if (!(n->myimms & DBDES_M) && !(n->imms & DBDES_M)) ospf_neigh_sm(n, INM_EXDONE); else - ospf_send_dbdes(n, 1); + ospf_send_dbdes(p, n, 1); } else { @@ -489,7 +486,7 @@ ospf_receive_dbdes(struct ospf_packet *pkt, struct ospf_iface *ifa, if (ospf_process_dbdes(p, pkt, n) < 0) return; - ospf_send_dbdes(n, 1); + ospf_send_dbdes(p, n, 1); } break; @@ -504,7 +501,7 @@ ospf_receive_dbdes(struct ospf_packet *pkt, struct ospf_iface *ifa, if (!(n->myimms & DBDES_MS)) { /* Slave should retransmit dbdes packet */ - ospf_send_dbdes(n, 0); + ospf_send_dbdes(p, n, 0); } return; } diff --git a/proto/ospf/hello.c b/proto/ospf/hello.c index 376eac3c..50cd8609 100644 --- a/proto/ospf/hello.c +++ b/proto/ospf/hello.c @@ -275,7 +275,7 @@ ospf_receive_hello(struct ospf_packet *pkt, struct ospf_iface *ifa, /* Check consistency of existing neighbor entry */ if (n) { - unsigned t = ifa->type; + uint t = ifa->type; if (ospf_is_v2(p) && ((t == OSPF_IT_BCAST) || (t == OSPF_IT_NBMA) || (t == OSPF_IT_PTMP))) { /* Neighbor identified by IP address; Router ID may change */ diff --git a/proto/ospf/iface.c b/proto/ospf/iface.c index 5e17371d..312e626a 100644 --- a/proto/ospf/iface.c +++ b/proto/ospf/iface.c @@ -620,18 +620,11 @@ ospf_iface_new(struct ospf_area *oa, struct ifa *addr, struct ospf_iface_patt *i add_tail(&oa->po->iface_list, NODE ifa); - /* - * In some cases we allow more ospf_ifaces on one physical iface. - * In OSPFv2, if they use different IP address prefix. - * In OSPFv3, if they use different instance_id. - * Therefore, we store such info to lock->addr field. - */ - - // XXXX review struct object_lock *lock = olock_new(pool); - lock->addr = ospf_is_v2(p) ? ifa->addr->prefix : _MI6(0,0,0,ifa->instance_id); + lock->addr = ospf_is_v2(p) ? ifa->addr->prefix : IPA_NONE; lock->type = OBJLOCK_IP; lock->port = OSPF_PROTO; + lock->inst = ifa->instance_id; lock->iface = iface; lock->data = ifa; lock->hook = ospf_iface_add; @@ -997,7 +990,7 @@ ospf_walk_matching_iface_patts(struct ospf_proto *p, struct ospf_mip_walk *s) BIT32_SET(s->ignore, id); /* If we already found it in previous areas, ignore it and add warning */ - if (!BIT32_TEST(s->active, id)) + if (BIT32_TEST(s->active, id)) { s->warn = 1; continue; } BIT32_SET(s->active, id); @@ -1046,7 +1039,7 @@ ospf_ifa_notify2(struct proto *P, uint flags, struct ifa *a) { struct ospf_mip_walk s = { .iface = a->iface, .a = a }; while (ospf_walk_matching_iface_patts(p, &s)) - ospf_iface_new(s.oa, s.a, s.ip); + ospf_iface_new(s.oa, a, s.ip); } if (flags & IF_CHANGE_DOWN) @@ -1078,7 +1071,7 @@ ospf_ifa_notify3(struct proto *P, uint flags, struct ifa *a) { struct ospf_mip_walk s = { .iface = a->iface }; while (ospf_walk_matching_iface_patts(p, &s)) - ospf_iface_new(s.oa, s.a, s.ip); + ospf_iface_new(s.oa, a, s.ip); } if (flags & IF_CHANGE_DOWN) diff --git a/proto/ospf/lsack.c b/proto/ospf/lsack.c index aefddfb8..5cac3f69 100644 --- a/proto/ospf/lsack.c +++ b/proto/ospf/lsack.c @@ -79,10 +79,9 @@ ospf_reset_lsack_queue(struct ospf_neighbor *n) } static inline void -ospf_send_lsack(struct ospf_neighbor *n, int queue) +ospf_send_lsack_(struct ospf_proto *p, struct ospf_neighbor *n, int queue) { struct ospf_iface *ifa = n->ifa; - struct ospf_proto *p = ifa->oa->po; struct ospf_lsa_header *lsas; struct ospf_packet *pkt; struct lsa_node *no; @@ -121,10 +120,10 @@ ospf_send_lsack(struct ospf_neighbor *n, int queue) } void -ospf_lsack_send(struct ospf_neighbor *n, int queue) +ospf_send_lsack(struct ospf_proto *p, struct ospf_neighbor *n, int queue) { while (!EMPTY_LIST(n->ackl[queue])) - ospf_send_lsack(n, queue); + ospf_send_lsack_(p, n, queue); } void @@ -160,9 +159,6 @@ ospf_receive_lsack(struct ospf_packet *pkt, struct ospf_iface *ifa, if (lsa_comp(&lsa, &ret->lsa) != CMP_SAME) { - if ((lsa.sn == LSA_MAXSEQNO) && (lsa.age == LSA_MAXAGE)) - continue; - OSPF_TRACE(D_PACKETS, "Strange LSACK from %I", n->ip); OSPF_TRACE(D_PACKETS, "Type: %04x, Id: %R, Rt: %R", lsa_type, lsa.id, lsa.rt); diff --git a/proto/ospf/lsreq.c b/proto/ospf/lsreq.c index 8888f88e..1685ef13 100644 --- a/proto/ospf/lsreq.c +++ b/proto/ospf/lsreq.c @@ -71,7 +71,8 @@ ospf_send_lsreq(struct ospf_proto *p, struct ospf_neighbor *n) ospf_pkt_fill_hdr(ifa, pkt, LSREQ_P); ospf_lsreq_body(p, pkt, &lsrs, &lsr_max); - // for (i = 0; i < lsr_max; i++) + /* We send smaller LSREQ to prevent multiple LSACKs as answer */ + lsr_max = lsr_max / 4; i = 0; WALK_SLIST(en, n->lsrql) diff --git a/proto/ospf/lsupd.c b/proto/ospf/lsupd.c index b0bf21cd..37c89a24 100644 --- a/proto/ospf/lsupd.c +++ b/proto/ospf/lsupd.c @@ -115,7 +115,8 @@ ospf_lsa_lsrt_up(struct top_hash_entry *en, struct ospf_neighbor *n) s_add_tail(&n->lsrtl, SNODE ret); } - memcpy(&ret->lsa, &en->lsa, sizeof(struct ospf_lsa_header)); + ret->lsa = en->lsa; + ret->lsa_body = LSA_BODY_DUMMY; } static inline int @@ -134,25 +135,37 @@ ospf_lsa_lsrt_down(struct top_hash_entry *en, struct ospf_neighbor *n) return 0; } +void +ospf_add_flushed_to_lsrt(struct ospf_proto *p, struct ospf_neighbor *n) +{ + struct top_hash_entry *en; + + WALK_SLIST(en, p->lsal) + if ((en->lsa.age == LSA_MAXAGE) && (en->lsa_body != NULL) && + lsa_flooding_allowed(en->lsa_type, en->domain, n->ifa)) + ospf_lsa_lsrt_up(en, n); +} + -static void ospf_lsupd_flood_ifa(struct ospf_proto *p, struct ospf_iface *ifa, struct top_hash_entry *en); +static void ospf_send_lsupd_to_ifa(struct ospf_proto *p, struct top_hash_entry *en, struct ospf_iface *ifa); /** - * ospf_lsupd_flood - send received or generated LSA to the neighbors - * @p: OSPF protocol + * ospf_flood_lsa - send LSA to the neighbors + * @p: OSPF protocol instance * @en: LSA entry * @from: neighbor than sent this LSA (or NULL if LSA is local) * * return value - was the LSA flooded back? */ - int -ospf_lsupd_flood(struct ospf_proto *p, struct top_hash_entry *en, struct ospf_neighbor *from) +ospf_flood_lsa(struct ospf_proto *p, struct top_hash_entry *en, struct ospf_neighbor *from) { struct ospf_iface *ifa; struct ospf_neighbor *n; + /* RFC 2328 13.3 */ + int back = 0; WALK_LIST(ifa, p->iface_list) { @@ -185,6 +198,8 @@ ospf_lsupd_flood(struct ospf_proto *p, struct top_hash_entry *en, struct ospf_ne { s_rem_node(SNODE req); ospf_hash_delete(n->lsrqh, req); + n->want_lsreq = 1; + if ((EMPTY_SLIST(n->lsrql)) && (n->state == NEIGHBOR_LOADING)) ospf_neigh_sm(n, INM_LOADDONE); } @@ -227,7 +242,7 @@ ospf_lsupd_flood(struct ospf_proto *p, struct top_hash_entry *en, struct ospf_ne } /* 13.3 (5) - finally flood the packet */ - ospf_lsupd_flood_ifa(p, ifa, en); + ospf_send_lsupd_to_ifa(p, en, ifa); } return back; @@ -288,7 +303,7 @@ ospf_prepare_lsupd(struct ospf_proto *p, struct ospf_iface *ifa, static void -ospf_lsupd_flood_ifa(struct ospf_proto *p, struct ospf_iface *ifa, struct top_hash_entry *en) +ospf_send_lsupd_to_ifa(struct ospf_proto *p, struct top_hash_entry *en, struct ospf_iface *ifa) { uint c = ospf_prepare_lsupd(p, ifa, &en, 1); @@ -384,7 +399,8 @@ ospf_receive_lsupd(struct ospf_packet *pkt, struct ospf_iface *ifa, /* RFC 2328 13. */ - int sendreq = 1; /* XXXX: review sendreq */ + int skip_lsreq = 0; + n->want_lsreq = 0; uint plen = ntohs(pkt->length); if (plen < (ospf_lsupd_hdrlen(p) + sizeof(struct ospf_lsa_header))) @@ -436,7 +452,7 @@ ospf_receive_lsupd(struct ospf_packet *pkt, struct ospf_iface *ifa, u16 chsum = lsa_n->checksum; if (chsum != lsasum_check(lsa_n, NULL)) { - log(L_WARN "%s: Received LSA from %I with bad checskum: %x %x", + log(L_WARN "%s: Received LSA from %I with bad checksum: %x %x", p->p.name, n->ip, chsum, lsa_n->checksum); continue; } @@ -501,7 +517,7 @@ ospf_receive_lsupd(struct ospf_packet *pkt, struct ospf_iface *ifa, if (en && ((now - en->inst_time) < MINLSARRIVAL)) { OSPF_TRACE(D_EVENTS, "Skipping LSA received in less that MinLSArrival"); - sendreq = 0; + skip_lsreq = 1; continue; } @@ -514,7 +530,6 @@ ospf_receive_lsupd(struct ospf_packet *pkt, struct ospf_iface *ifa, { log(L_WARN "%s: Received invalid LSA from %I", p->p.name, n->ip); mb_free(body); - sendreq = 0; continue; } @@ -528,22 +543,27 @@ ospf_receive_lsupd(struct ospf_packet *pkt, struct ospf_iface *ifa, } /* 13. (5c) - remove old LSA from all retransmission lists */ - /* Must be done before (5b), otherwise it also removes the new entries from (5b) */ - + /* + * We only need to remove it from the retransmission list of the neighbor + * that send us the new LSA. The old LSA is automatically replaced in + * retransmission lists by the new LSA. + */ if (en) ospf_lsa_lsrt_down(en, n); +#if 0 /* - { - struct ospf_iface *ifi; - struct ospf_neighbor *ni; - - WALK_LIST(ifi, p->iface_list) - WALK_LIST(ni, ifi->neigh_list) - if (ni->state > NEIGHBOR_EXSTART) - ospf_lsa_lsrt_down(en, ni); - } - */ + * Old code for removing LSA from all retransmission lists. Must be done + * before (5b), otherwise it also removes the new entries from (5b). + */ + struct ospf_iface *ifi; + struct ospf_neighbor *ni; + + WALK_LIST(ifi, p->iface_list) + WALK_LIST(ni, ifi->neigh_list) + if (ni->state > NEIGHBOR_EXSTART) + ospf_lsa_lsrt_down(en, ni); +#endif /* 13. (5d) - install new LSA into database */ en = ospf_install_lsa(p, &lsa, lsa_type, lsa_domain, body); @@ -553,7 +573,7 @@ ospf_receive_lsupd(struct ospf_packet *pkt, struct ospf_iface *ifa, ospf_notify_net_lsa(ifa); /* 13. (5b) - flood new LSA */ - int flood_back = ospf_lsupd_flood(p, en, n); + int flood_back = ospf_flood_lsa(p, en, n); /* 13.5. - schedule ACKs (tbl 19, cases 1+2) */ if (! flood_back) @@ -582,7 +602,7 @@ ospf_receive_lsupd(struct ospf_packet *pkt, struct ospf_iface *ifa, else ospf_enqueue_lsack(n, lsa_n, ACKL_DIRECT); - sendreq = 0; + skip_lsreq = 1; continue; } @@ -598,11 +618,17 @@ ospf_receive_lsupd(struct ospf_packet *pkt, struct ospf_iface *ifa, } } - /* Send direct LSAs */ - ospf_lsack_send(n, ACKL_DIRECT); - - /* If loading, ask for another part of neighbor's database */ - if (sendreq && (n->state == NEIGHBOR_LOADING)) + /* Send direct LSACKs */ + ospf_send_lsack(p, n, ACKL_DIRECT); + + /* + * In loading state, we should ask for another batch of LSAs. This is only + * vaguely mentioned in RFC 2328. We send a new LSREQ only if the current + * LSUPD actually removed some entries from LSA request list (want_lsreq) and + * did not contain duplicate or early LSAs (skip_lsreq). The first condition + * prevents endless floods, the second condition helps with flow control. + */ + if ((n->state == NEIGHBOR_LOADING) && n->want_lsreq && !skip_lsreq) ospf_send_lsreq(p, n); } diff --git a/proto/ospf/neighbor.c b/proto/ospf/neighbor.c index 392f1d64..c182f0d2 100644 --- a/proto/ospf/neighbor.c +++ b/proto/ospf/neighbor.c @@ -33,13 +33,26 @@ static void rxmt_timer_hook(timer * timer); static void ackd_timer_hook(timer * t); static void -init_lists(struct ospf_neighbor *n) +init_lists(struct ospf_proto *p, struct ospf_neighbor *n) { s_init_list(&(n->lsrql)); - n->lsrqh = ospf_top_new(n->pool); + n->lsrqh = ospf_top_new(p, n->pool); s_init_list(&(n->lsrtl)); - n->lsrth = ospf_top_new(n->pool); + n->lsrth = ospf_top_new(p, n->pool); +} + +static void +release_lsrtl(struct ospf_proto *p, struct ospf_neighbor *n) +{ + struct top_hash_entry *ret, *en; + + WALK_SLIST(ret, n->lsrtl) + { + en = ospf_hash_find_entry(p->gr, ret); + if (en) + en->ret_count--; + } } /* Resets LSA request and retransmit lists. @@ -47,11 +60,12 @@ init_lists(struct ospf_neighbor *n) * it is reset during entering EXCHANGE state. */ static void -reset_lists(struct ospf_neighbor *n) +reset_lists(struct ospf_proto *p, struct ospf_neighbor *n) { + release_lsrtl(p,n); ospf_top_free(n->lsrqh); ospf_top_free(n->lsrth); - init_lists(n); + init_lists(p, n); } struct ospf_neighbor * @@ -68,7 +82,7 @@ ospf_neighbor_new(struct ospf_iface *ifa) n->csn = 0; n->state = NEIGHBOR_DOWN; - init_lists(n); + init_lists(p, n); s_init(&(n->dbsi), &(p->lsal)); n->inactim = tm_new(pool); @@ -360,6 +374,10 @@ ospf_neigh_sm(struct ospf_neighbor *n, int event) s_get(&(n->dbsi)); s_init(&(n->dbsi), &p->lsal); + /* Add MaxAge LSA entries to retransmission list */ + ospf_add_flushed_to_lsrt(p, n); + + /* FIXME: Why is this here ? */ ospf_reset_lsack_queue(n); } else @@ -388,7 +406,7 @@ ospf_neigh_sm(struct ospf_neighbor *n, int event) if (n->state >= NEIGHBOR_EXSTART) if (!can_do_adj(n)) { - reset_lists(n); + reset_lists(p,n); neigh_chstate(n, NEIGHBOR_2WAY); } break; @@ -399,7 +417,7 @@ ospf_neigh_sm(struct ospf_neighbor *n, int event) case INM_BADLSREQ: if (n->state >= NEIGHBOR_EXCHANGE) { - reset_lists(n); + reset_lists(p, n); neigh_chstate(n, NEIGHBOR_EXSTART); } break; @@ -407,12 +425,12 @@ ospf_neigh_sm(struct ospf_neighbor *n, int event) case INM_KILLNBR: case INM_LLDOWN: case INM_INACTTIM: - reset_lists(n); + reset_lists(p, n); neigh_chstate(n, NEIGHBOR_DOWN); break; case INM_1WAYREC: - reset_lists(n); + reset_lists(p, n); neigh_chstate(n, NEIGHBOR_INIT); break; @@ -552,8 +570,10 @@ ospf_neigh_remove(struct ospf_neighbor *n) nn->found = 0; } - s_get(&(n->dbsi)); neigh_chstate(n, NEIGHBOR_DOWN); + + s_get(&(n->dbsi)); + release_lsrtl(p, n); rem_node(NODE n); rfree(n->pool); OSPF_TRACE(D_EVENTS, "Deleting neigbor %R", n->rid); @@ -620,9 +640,9 @@ ospf_sh_neigh_info(struct ospf_neighbor *n) } static void -rxmt_timer_hook(timer * timer) +rxmt_timer_hook(timer *t) { - struct ospf_neighbor *n = (struct ospf_neighbor *) timer->data; + struct ospf_neighbor *n = t->data; struct ospf_proto *p = n->ifa->oa->po; DBG("%s: RXMT timer fired on interface %s for neigh %I\n", @@ -631,12 +651,12 @@ rxmt_timer_hook(timer * timer) switch (n->state) { case NEIGHBOR_EXSTART: - ospf_send_dbdes(n, 1); + ospf_send_dbdes(p, n, 1); return; case NEIGHBOR_EXCHANGE: if (n->myimms & DBDES_MS) - ospf_send_dbdes(n, 0); + ospf_send_dbdes(p, n, 0); case NEIGHBOR_LOADING: ospf_send_lsreq(p, n); return; @@ -653,8 +673,13 @@ rxmt_timer_hook(timer * timer) } static void -ackd_timer_hook(timer * t) +ackd_timer_hook(timer *t) { struct ospf_neighbor *n = t->data; - ospf_lsack_send(n, ACKL_DELAY); + struct ospf_proto *p = n->ifa->oa->po; + + DBG("%s: ACKD timer fired on interface %s for neigh %I\n", + p->p.name, n->ifa->ifname, n->ip); + + ospf_send_lsack(p, n, ACKL_DELAY); } diff --git a/proto/ospf/ospf.c b/proto/ospf/ospf.c index abcd527a..df5fe472 100644 --- a/proto/ospf/ospf.c +++ b/proto/ospf/ospf.c @@ -11,93 +11,81 @@ /** * DOC: Open Shortest Path First (OSPF) * - * The OSPF protocol is quite complicated and its complex implemenation is - * split to many files. In |ospf.c|, you will find mainly the interface - * for communication with the core (e.g., reconfiguration hooks, shutdown - * and initialisation and so on). In |packet.c|, you will find various - * functions for sending and receiving generic OSPF packets. There are - * also routines for authentication and checksumming. File |iface.c| contains - * the interface state machine and functions for allocation and deallocation of OSPF's - * interface data structures. Source |neighbor.c| includes the neighbor state - * machine and functions for election of Designated Router and Backup - * Designated router. In |hello.c|, there are routines for sending - * and receiving of hello packets as well as functions for maintaining - * wait times and the inactivity timer. Files |lsreq.c|, |lsack.c|, |dbdes.c| - * contain functions for sending and receiving of link-state requests, - * link-state acknowledgements and database descriptions respectively. - * In |lsupd.c|, there are functions for sending and receiving - * of link-state updates and also the flooding algorithm. Source |topology.c| is - * a place where routines for searching LSAs in the link-state database, - * adding and deleting them reside, there also are functions for originating - * of various types of LSAs (router LSA, net LSA, external LSA). File |rt.c| - * contains routines for calculating the routing table. |lsalib.c| is a set - * of various functions for working with the LSAs (endianity conversions, - * calculation of checksum etc.). + * The OSPF protocol is quite complicated and its complex implemenation is split + * to many files. In |ospf.c|, you will find mainly the interface for + * communication with the core (e.g., reconfiguration hooks, shutdown and + * initialisation and so on). File |iface.c| contains the interface state + * machine and functions for allocation and deallocation of OSPF's interface + * data structures. Source |neighbor.c| includes the neighbor state machine and + * functions for election of Designated Router and Backup Designated router. In + * |packet.c|, you will find various functions for sending and receiving generic + * OSPF packets. There are also routines for authentication and checksumming. + * In |hello.c|, there are routines for sending and receiving of hello packets + * as well as functions for maintaining wait times and the inactivity timer. + * Files |lsreq.c|, |lsack.c|, |dbdes.c| contain functions for sending and + * receiving of link-state requests, link-state acknowledgements and database + * descriptions respectively. In |lsupd.c|, there are functions for sending and + * receiving of link-state updates and also the flooding algorithm. Source + * |topology.c| is a place where routines for searching LSAs in the link-state + * database, adding and deleting them reside, there also are functions for + * originating of various types of LSAs (router LSA, net LSA, external LSA). + * File |rt.c| contains routines for calculating the routing table. |lsalib.c| + * is a set of various functions for working with the LSAs (endianity + * conversions, calculation of checksum etc.). * - * One instance of the protocol is able to hold LSA databases for - * multiple OSPF areas, to exchange routing information between - * multiple neighbors and to calculate the routing tables. The core - * structure is &ospf_proto to which multiple &ospf_area and - * &ospf_iface structures are connected. &ospf_area is also connected to - * &top_hash_graph which is a dynamic hashing structure that - * describes the link-state database. It allows fast search, addition - * and deletion. Each LSA is kept in two pieces: header and body. Both of them are + * One instance of the protocol is able to hold LSA databases for multiple OSPF + * areas, to exchange routing information between multiple neighbors and to + * calculate the routing tables. The core structure is &ospf_proto to which + * multiple &ospf_area and &ospf_iface structures are connected. &ospf_proto is + * also connected to &top_hash_graph which is a dynamic hashing structure that + * describes the link-state database. It allows fast search, addition and + * deletion. Each LSA is kept in two pieces: header and body. Both of them are * kept in the endianity of the CPU. * - * In OSPFv2 specification, it is implied that there is one IP prefix - * for each physical network/interface (unless it is an ptp link). But - * in modern systems, there might be more independent IP prefixes - * associated with an interface. To handle this situation, we have - * one &ospf_iface for each active IP prefix (instead for each active - * iface); This behaves like virtual interface for the purpose of OSPF. - * If we receive packet, we associate it with a proper virtual interface - * mainly according to its source address. + * In OSPFv2 specification, it is implied that there is one IP prefix for each + * physical network/interface (unless it is an ptp link). But in modern systems, + * there might be more independent IP prefixes associated with an interface. To + * handle this situation, we have one &ospf_iface for each active IP prefix + * (instead for each active iface); This behaves like virtual interface for the + * purpose of OSPF. If we receive packet, we associate it with a proper virtual + * interface mainly according to its source address. * - * OSPF keeps one socket per &ospf_iface. This allows us (compared to - * one socket approach) to evade problems with a limit of multicast - * groups per socket and with sending multicast packets to appropriate - * interface in a portable way. The socket is associated with - * underlying physical iface and should not receive packets received - * on other ifaces (unfortunately, this is not true on - * BSD). Generally, one packet can be received by more sockets (for - * example, if there are more &ospf_iface on one physical iface), - * therefore we explicitly filter received packets according to - * src/dst IP address and received iface. + * OSPF keeps one socket per &ospf_iface. This allows us (compared to one socket + * approach) to evade problems with a limit of multicast groups per socket and + * with sending multicast packets to appropriate interface in a portable way. + * The socket is associated with underlying physical iface and should not + * receive packets received on other ifaces (unfortunately, this is not true on + * BSD). Generally, one packet can be received by more sockets (for example, if + * there are more &ospf_iface on one physical iface), therefore we explicitly + * filter received packets according to src/dst IP address and received iface. * - * Vlinks are implemented using particularly degenerate form of - * &ospf_iface, which has several exceptions: it does not have its - * iface or socket (it copies these from 'parent' &ospf_iface) and it - * is present in iface list even when down (it is not freed in - * ospf_iface_down()). + * Vlinks are implemented using particularly degenerate form of &ospf_iface, + * which has several exceptions: it does not have its iface or socket (it copies + * these from 'parent' &ospf_iface) and it is present in iface list even when + * down (it is not freed in ospf_iface_down()). * * The heart beat of ospf is ospf_disp(). It is called at regular intervals - * (&ospf_proto->tick). It is responsible for aging and flushing of LSAs in - * the database, for routing table calculaction and it call area_disp() of every - * ospf_area. + * (&ospf_proto->tick). It is responsible for aging and flushing of LSAs in the + * database, updating topology information in LSAs and for routing table + * calculation. * - * The function area_disp() is - * responsible for late originating of router LSA and network LSA - * and for cleanup before routing table calculation process in - * the area. - * To every &ospf_iface, we connect one or more - * &ospf_neighbor's -- a structure containing many timers and queues - * for building adjacency and for exchange of routing messages. + * To every &ospf_iface, we connect one or more &ospf_neighbor's -- a structure + * containing many timers and queues for building adjacency and for exchange of + * routing messages. * - * BIRD's OSPF implementation respects RFC2328 in every detail, but - * some of internal algorithms do differ. The RFC recommends making a snapshot - * of the link-state database when a new adjacency is forming and sending - * the database description packets based on the information in this - * snapshot. The database can be quite large in some networks, so - * rather we walk through a &slist structure which allows us to - * continue even if the actual LSA we were working with is deleted. New - * LSAs are added at the tail of this &slist. + * BIRD's OSPF implementation respects RFC2328 in every detail, but some of + * internal algorithms do differ. The RFC recommends making a snapshot of the + * link-state database when a new adjacency is forming and sending the database + * description packets based on the information in this snapshot. The database + * can be quite large in some networks, so rather we walk through a &slist + * structure which allows us to continue even if the actual LSA we were working + * with is deleted. New LSAs are added at the tail of this &slist. * - * We also don't keep a separate OSPF routing table, because the core - * helps us by being able to recognize when a route is updated - * to an identical one and it suppresses the update automatically. - * Due to this, we can flush all the routes we've recalculated and - * also those we've deleted to the core's routing table and the - * core will take care of the rest. This simplifies the process + * We also do not keep a separate OSPF routing table, because the core helps us + * by being able to recognize when a route is updated to an identical one and it + * suppresses the update automatically. Due to this, we can flush all the routes + * we have recalculated and also those we have deleted to the core's routing + * table and the core will take care of the rest. This simplifies the process * and conserves memory. */ @@ -145,7 +133,7 @@ add_area_nets(struct ospf_area *oa, struct ospf_area_config *ac) } static void -ospf_area_add(struct ospf_proto *p, struct ospf_area_config *ac, int reconf) +ospf_area_add(struct ospf_proto *p, struct ospf_area_config *ac) { struct ospf_area *oa; @@ -169,6 +157,8 @@ ospf_area_add(struct ospf_proto *p, struct ospf_area_config *ac, int reconf) oa->options = ac->type; else oa->options = ac->type | OPT_V6 | (p->stub_router ? 0 : OPT_R); + + ospf_notify_rt_lsa(oa); } static void @@ -252,11 +242,11 @@ ospf_start(struct proto *P) init_list(&(p->area_list)); fib_init(&p->rtf, P->pool, sizeof(ort), 0, ospf_rt_initort); p->areano = 0; - p->gr = ospf_top_new(P->pool); + p->gr = ospf_top_new(p, P->pool); s_init_list(&(p->lsal)); WALK_LIST(ac, c->area_list) - ospf_area_add(p, ac, 0); + ospf_area_add(p, ac); if (c->abr) ospf_open_vlink_sk(p); @@ -382,7 +372,7 @@ ospf_build_attrs(ea_list * next, struct linpool *pool, u32 m1, u32 m2, void -schedule_rtcalc(struct ospf_proto *p) +ospf_schedule_rtcalc(struct ospf_proto *p) { if (p->calcrt) return; @@ -418,7 +408,7 @@ ospf_disp(timer * timer) /* Originate or flush local topology LSAs */ ospf_update_topology(p); - /* Age LSA DB */ + /* Process LSA DB */ ospf_update_lsadb(p); /* Calculate routing table */ @@ -429,7 +419,7 @@ ospf_disp(timer * timer) /** * ospf_import_control - accept or reject new route from nest's routing table - * @p: current instance of protocol + * @P: OSPF protocol instance * @new: the new route * @attrs: list of attributes * @pool: pool for allocation of attributes @@ -475,7 +465,7 @@ ospf_store_tmp_attrs(struct rte *rt, struct ea_list *attrs) /** * ospf_shutdown - Finish of OSPF instance - * @p: current instance of protocol + * @P: OSPF protocol instance * * RFC does not define any action that should be taken before router * shutdown. To make my neighbors react as fast as possible, I send @@ -619,7 +609,7 @@ ospf_area_reconfigure(struct ospf_area *oa, struct ospf_area_config *nac) /** * ospf_reconfigure - reconfiguration hook - * @p: current instance of protocol (with old configuration) + * @P: current instance of protocol (with old configuration) * @c: new configuration requested by user * * This hook tries to be a little bit intelligent. Instance of OSPF @@ -669,7 +659,7 @@ ospf_reconfigure(struct proto *P, struct proto_config *c) if (oa) ospf_area_reconfigure(oa, nac); else - ospf_area_add(p, nac, 1); + ospf_area_add(p, nac); } /* Add and update interfaces */ @@ -697,7 +687,7 @@ ospf_reconfigure(struct proto *P, struct proto_config *c) if (oa->marked) ospf_area_remove(oa); - schedule_rtcalc(p); + ospf_schedule_rtcalc(p); return 1; } @@ -1009,7 +999,7 @@ show_lsa_router(struct ospf_proto *p, struct top_hash_entry *he, int verbose) /* In OSPFv2, we try to find network-LSA to get prefix/pxlen */ struct top_hash_entry *net_he = ospf_hash_find_net2(p->gr, he->domain, rtl.id); - if (net_he) + if (net_he && (net_he->lsa.age < LSA_MAXAGE)) { struct ospf_lsa_header *net_lsa = &(net_he->lsa); struct ospf_lsa_net *net_ln = net_he->lsa_body; @@ -1367,8 +1357,8 @@ void ospf_sh_lsadb(struct lsadb_show_data *ld) { struct ospf_proto *p = (struct ospf_proto *) proto_get_named(ld->name, &proto_ospf); - int num = p->gr->hash_entries; - unsigned int i, j; + uint num = p->gr->hash_entries; + uint i, j; int last_dscope = -1; u32 last_domain = 0; u16 type_mask = ospf_is_v2(p) ? 0x00ff : 0xffff; /* see lsa_etype() */ diff --git a/proto/ospf/ospf.h b/proto/ospf/ospf.h index 34c26b47..e5713628 100644 --- a/proto/ospf/ospf.h +++ b/proto/ospf/ospf.h @@ -102,7 +102,7 @@ do { if ((p->p.debug & D_PACKETS) || OSPF_FORCE_DEBUG) \ struct ospf_config { struct proto_config c; - unsigned tick; + uint tick; byte ospf2; byte rfc1583; byte stub_router; @@ -110,16 +110,26 @@ struct ospf_config byte abr; byte asbr; int ecmp; - list area_list; /* list of struct ospf_area_config */ - list vlink_list; /* list of struct ospf_iface_patt */ + list area_list; /* list of area configs (struct ospf_area_config) */ + list vlink_list; /* list of configured vlinks (struct ospf_iface_patt) */ }; -struct nbma_node +struct ospf_area_config { node n; - ip_addr ip; - byte eligible; - byte found; + u32 areaid; + u32 default_cost; /* Cost of default route for stub areas + (With possible LSA_EXT3_EBIT for NSSA areas) */ + u8 type; /* Area type (standard, stub, NSSA), represented + by option flags (OPT_E, OPT_N) */ + u8 summary; /* Import summaries to this stub/NSSA area, valid for ABR */ + u8 default_nssa; /* Generate default NSSA route for NSSA+summary area */ + u8 translator; /* Translator role, for NSSA ABR */ + u32 transint; /* Translator stability interval */ + list patt_list; /* List of iface configs (struct ospf_iface_patt) */ + list net_list; /* List of aggregate networks for that area */ + list enet_list; /* List of aggregate external (NSSA) networks */ + list stubnet_list; /* List of stub networks added to Router LSA */ }; struct area_net_config @@ -148,65 +158,54 @@ struct ospf_stubnet_config u8 summary; }; -struct ospf_area_config +struct nbma_node { node n; - u32 areaid; - u32 default_cost; /* Cost of default route for stub areas - (With possible LSA_EXT3_EBIT for NSSA areas) */ - u8 type; /* Area type (standard, stub, NSSA), represented - by option flags (OPT_E, OPT_N) */ - u8 summary; /* Import summaries to this stub/NSSA area, valid for ABR */ - u8 default_nssa; /* Generate default NSSA route for NSSA+summary area */ - u8 translator; /* Translator role, for NSSA ABR */ - u32 transint; /* Translator stability interval */ - list patt_list; - list net_list; /* List of aggregate networks for that area */ - list enet_list; /* List of aggregate external (NSSA) networks */ - list stubnet_list; /* List of stub networks added to Router LSA */ + ip_addr ip; + byte eligible; + byte found; }; +struct ospf_iface_patt +{ + struct iface_patt i; + u32 type; + u32 stub; + u32 cost; + u32 helloint; + u32 rxmtint; + u32 pollint; + u32 waitint; + u32 deadc; + u32 deadint; + u32 inftransdelay; + list nbma_list; + u32 priority; + u32 voa; + u32 vid; + int tx_tos; + int tx_priority; + u16 tx_length; + u16 rx_buffer; -/* Generic option flags */ -#define OPT_V6 0x01 /* OSPFv3, LSA relevant for IPv6 routing calculation */ -#define OPT_E 0x02 /* Related to AS-external LSAs */ -#define OPT_MC 0x04 /* Related to MOSPF, not used and obsolete */ -#define OPT_N 0x08 /* Related to NSSA */ -#define OPT_P 0x08 /* OSPFv2, flags P and N share position, see NSSA RFC */ -#define OPT_EA 0x10 /* OSPFv2, external attributes, not used and obsolete */ -#define OPT_R 0x10 /* OSPFv3, originator is active router */ -#define OPT_DC 0x20 /* Related to demand circuits, not used */ - -/* Router-LSA VEB flags are are stored together with links (OSPFv2) or options (OSPFv3) */ -#define OPT_RT_B (0x01 << 24) -#define OPT_RT_E (0x02 << 24) -#define OPT_RT_V (0x04 << 24) -#define OPT_RT_NT (0x10 << 24) - -/* Prefix flags, specific for OSPFv3 */ -#define OPT_PX_NU 0x01 -#define OPT_PX_LA 0x02 -#define OPT_PX_P 0x08 -#define OPT_PX_DN 0x10 - - -/* OSPF interface types */ -#define OSPF_IT_BCAST 0 -#define OSPF_IT_NBMA 1 -#define OSPF_IT_PTP 2 -#define OSPF_IT_PTMP 3 -#define OSPF_IT_VLINK 4 -#define OSPF_IT_UNDEF 5 - -/* OSPF interface states */ -#define OSPF_IS_DOWN 0 /* Not active */ -#define OSPF_IS_LOOP 1 /* Iface with no link */ -#define OSPF_IS_WAITING 2 /* Waiting for Wait timer */ -#define OSPF_IS_PTP 3 /* PTP operational */ -#define OSPF_IS_DROTHER 4 /* I'm on BCAST or NBMA and I'm not DR */ -#define OSPF_IS_BACKUP 5 /* I'm BDR */ -#define OSPF_IS_DR 6 /* I'm DR */ - +#define OSPF_RXBUF_MINSIZE 256 /* Minimal allowed size */ + u8 instance_id; + u8 autype; /* Not really used in OSPFv3 */ +#define OSPF_AUTH_NONE 0 +#define OSPF_AUTH_SIMPLE 1 +#define OSPF_AUTH_CRYPT 2 +#define OSPF_AUTH_CRYPT_SIZE 16 + u8 strictnbma; + u8 check_link; + u8 ecmp_weight; + u8 link_lsa_suppression; + u8 real_bcast; /* Not really used in OSPFv3 */ + u8 ptp_netmask; /* bool + 2 for unspecified */ + u8 ttl_security; /* bool + 2 for TX only */ + u8 bfd; + u8 bsd_secondary; + list *passwords; +}; /* Default values for interface parameters */ #define COST_D 10 @@ -220,6 +219,58 @@ struct ospf_area_config /* Value of Wait timer - not found it in RFC * - using 4*HELLO */ + +struct ospf_proto +{ + struct proto p; + timer *disp_timer; /* OSPF proto dispatcher */ + uint tick; + struct top_graph *gr; /* LSA graph */ + slist lsal; /* List of all LSA's */ + int calcrt; /* Routing table calculation scheduled? + 0=no, 1=normal, 2=forced reload */ + list iface_list; /* List of OSPF interfaces (struct ospf_iface) */ + list area_list; /* List of OSPF areas (struct ospf_area) */ + int areano; /* Number of area I belong to */ + int padj; /* Number of neighbors in Exchange or Loading state */ + struct fib rtf; /* Routing table */ + byte ospf2; /* OSPF v2 or v3 */ + byte rfc1583; /* RFC1583 compatibility */ + byte stub_router; /* Do not forward transit traffic */ + byte merge_external; /* Should i merge external routes? */ + byte asbr; /* May i originate any ext/NSSA lsa? */ + byte ecmp; /* Maximal number of nexthops in ECMP route, or 0 */ + struct ospf_area *backbone; /* If exists */ + void *lsab; /* LSA buffer used when originating router LSAs */ + int lsab_size, lsab_used; + linpool *nhpool; /* Linpool used for next hops computed in SPF */ + sock *vlink_sk; /* IP socket used for vlink TX */ + u32 router_id; + u32 last_vlink_id; /* Interface IDs for vlinks (starts at 0x80000000) */ +}; + +struct ospf_area +{ + node n; + u32 areaid; + struct ospf_area_config *ac; /* Related area config */ + struct top_hash_entry *rt; /* My own router LSA */ + struct top_hash_entry *pxr_lsa; /* Originated prefix LSA */ + list cand; /* List of candidates for RT calc. */ + struct fib net_fib; /* Networks to advertise or not */ + struct fib enet_fib; /* External networks for NSSAs */ + u32 options; /* Optional features */ + u8 update_rt_lsa; /* Rt lsa origination scheduled? */ + u8 trcap; /* Transit capability? */ + u8 marked; /* Used in OSPF reconfigure */ + u8 translate; /* Translator state (TRANS_*), for NSSA ABR */ + timer *translator_timer; /* For NSSA translator switch */ + struct ospf_proto *po; + struct fib rtr; /* Routing tables for routers */ +}; + + + struct ospf_iface { node n; @@ -231,7 +282,7 @@ struct ospf_iface pool *pool; sock *sk; /* IP socket */ - list neigh_list; /* List of neigbours */ + list neigh_list; /* List of neigbours (struct ospf_neighbor) */ u32 cost; /* Cost of iface */ u32 waitint; /* number of sec before changing state from wait */ u32 rxmtint; /* number of seconds between LSA retransmissions */ @@ -295,6 +346,153 @@ struct ospf_iface u8 bfd; /* Use BFD on iface */ }; +struct ospf_neighbor +{ + node n; + pool *pool; + struct ospf_iface *ifa; + u8 state; + timer *inactim; /* Inactivity timer */ + u8 imms; /* I, M, Master/slave received */ + u8 myimms; /* I, M Master/slave */ + u32 dds; /* DD Sequence number being sent */ + u32 ddr; /* last Dat Des packet received */ + + u32 rid; /* Router ID */ + ip_addr ip; /* IP of it's interface */ + u8 priority; /* Priority */ + u8 adj; /* built adjacency? */ + u8 want_lsreq; /* Set to 1 when lsrql was shortened during LSUPD */ + u32 options; /* Options received */ + + /* Entries dr and bdr store IP addresses in OSPFv2 and router IDs in + OSPFv3, we use the same type to simplify handling */ + u32 dr; /* Neigbour's idea of DR */ + u32 bdr; /* Neigbour's idea of BDR */ + u32 iface_id; /* ID of Neighbour's iface connected to common network */ + + /* Database summary list iterator, controls initial dbdes exchange. + * Advances in the LSA list as dbdes packets are sent. + */ + siterator dbsi; /* iterator of po->lsal */ + + /* Link state request list, controls initial LSA exchange. + * Entries added when received in dbdes packets, removed as sent in lsreq packets. + */ + slist lsrql; /* slist of struct top_hash_entry from n->lsrqh */ + struct top_graph *lsrqh; + + /* Link state retransmission list, controls LSA retransmission during flood. + * Entries added as sent in lsupd packets, removed when received in lsack packets. + * These entries hold ret_count in appropriate LSA entries. + */ + slist lsrtl; /* slist of struct top_hash_entry from n->lsrth */ + struct top_graph *lsrth; + timer *rxmt_timer; /* RXMT timer */ + list ackl[2]; +#define ACKL_DIRECT 0 +#define ACKL_DELAY 1 + timer *ackd_timer; /* Delayed ack timer */ + struct bfd_request *bfd_req; /* BFD request, if BFD is used */ + void *ldd_buffer; /* Last database description packet */ + u32 ldd_bsize; /* Buffer size for ldd_buffer */ + u32 csn; /* Last received crypt seq number (for MD5) */ +}; + + +/* OSPF interface types */ +#define OSPF_IT_BCAST 0 +#define OSPF_IT_NBMA 1 +#define OSPF_IT_PTP 2 +#define OSPF_IT_PTMP 3 +#define OSPF_IT_VLINK 4 +#define OSPF_IT_UNDEF 5 + +/* OSPF interface states */ +#define OSPF_IS_DOWN 0 /* Not active */ +#define OSPF_IS_LOOP 1 /* Iface with no link */ +#define OSPF_IS_WAITING 2 /* Waiting for Wait timer */ +#define OSPF_IS_PTP 3 /* PTP operational */ +#define OSPF_IS_DROTHER 4 /* I'm on BCAST or NBMA and I'm not DR */ +#define OSPF_IS_BACKUP 5 /* I'm BDR */ +#define OSPF_IS_DR 6 /* I'm DR */ + +/* Definitions for interface state machine */ +#define ISM_UP 0 /* Interface Up */ +#define ISM_WAITF 1 /* Wait timer fired */ +#define ISM_BACKS 2 /* Backup seen */ +#define ISM_NEICH 3 /* Neighbor change */ +#define ISM_LOOP 4 /* Link down */ +#define ISM_UNLOOP 5 /* Link up */ +#define ISM_DOWN 6 /* Interface down */ + + +/* OSPF neighbor states */ +#define NEIGHBOR_DOWN 0 +#define NEIGHBOR_ATTEMPT 1 +#define NEIGHBOR_INIT 2 +#define NEIGHBOR_2WAY 3 +#define NEIGHBOR_EXSTART 4 +#define NEIGHBOR_EXCHANGE 5 +#define NEIGHBOR_LOADING 6 +#define NEIGHBOR_FULL 7 + +/* Definitions for neighbor state machine */ +#define INM_HELLOREC 0 /* Hello Received */ +#define INM_START 1 /* Neighbor start - for NBMA */ +#define INM_2WAYREC 2 /* 2-Way received */ +#define INM_NEGDONE 3 /* Negotiation done */ +#define INM_EXDONE 4 /* Exchange done */ +#define INM_BADLSREQ 5 /* Bad LS Request */ +#define INM_LOADDONE 6 /* Load done */ +#define INM_ADJOK 7 /* AdjOK? */ +#define INM_SEQMIS 8 /* Sequence number mismatch */ +#define INM_1WAYREC 9 /* 1-Way */ +#define INM_KILLNBR 10 /* Kill Neighbor */ +#define INM_INACTTIM 11 /* Inactivity timer */ +#define INM_LLDOWN 12 /* Line down */ + +#define TRANS_OFF 0 +#define TRANS_ON 1 +#define TRANS_WAIT 2 /* Waiting before the end of translation */ + + + +/* Generic option flags */ +#define OPT_V6 0x01 /* OSPFv3, LSA relevant for IPv6 routing calculation */ +#define OPT_E 0x02 /* Related to AS-external LSAs */ +#define OPT_MC 0x04 /* Related to MOSPF, not used and obsolete */ +#define OPT_N 0x08 /* Related to NSSA */ +#define OPT_P 0x08 /* OSPFv2, flags P and N share position, see NSSA RFC */ +#define OPT_EA 0x10 /* OSPFv2, external attributes, not used and obsolete */ +#define OPT_R 0x10 /* OSPFv3, originator is active router */ +#define OPT_DC 0x20 /* Related to demand circuits, not used */ + +/* Router-LSA VEB flags are are stored together with links (OSPFv2) or options (OSPFv3) */ +#define OPT_RT_B (0x01 << 24) +#define OPT_RT_E (0x02 << 24) +#define OPT_RT_V (0x04 << 24) +#define OPT_RT_NT (0x10 << 24) + +/* Prefix flags, specific for OSPFv3 */ +#define OPT_PX_NU 0x01 +#define OPT_PX_LA 0x02 +#define OPT_PX_P 0x08 +#define OPT_PX_DN 0x10 + + +struct ospf_packet +{ + u8 version; + u8 type; + u16 length; + u32 routerid; + u32 areaid; + u16 checksum; + u8 instance_id; /* See RFC 6549 */ + u8 autype; /* Undefined for OSPFv3 */ +}; + struct ospf_md5 { u16 zero; @@ -309,7 +507,6 @@ union ospf_auth struct ospf_md5 md5; }; - /* Packet types */ #define HELLO_P 1 /* Hello */ #define DBDES_P 2 /* Database description */ @@ -317,8 +514,6 @@ union ospf_auth #define LSUPD_P 4 /* Link state update */ #define LSACK_P 5 /* Link state acknowledgement */ -/* Area IDs */ -#define BACKBONE 0 #define DBDES_I 4 /* Init bit */ #define DBDES_M 2 /* More bit */ @@ -326,19 +521,6 @@ union ospf_auth #define DBDES_IMMS (DBDES_I | DBDES_M | DBDES_MS) -struct ospf_packet -{ - u8 version; - u8 type; - u16 length; - u32 routerid; - u32 areaid; - u16 checksum; - u8 instance_id; /* See RFC 6549 */ - u8 autype; /* Undefined for OSPFv3 */ -}; - - #define LSA_T_RT 0x2001 #define LSA_T_NET 0x2002 #define LSA_T_SUM_NET 0x2003 @@ -530,7 +712,7 @@ struct ospf_lsa_prefix }; -static inline unsigned +static inline uint lsa_net_count(struct ospf_lsa_header *lsa) { return (lsa->length - sizeof(struct ospf_lsa_header) - sizeof(struct ospf_lsa_net)) @@ -558,6 +740,7 @@ lsa_get_ipv6_prefix(u32 *buf, ip_addr *addr, int *pxlen, u8 *pxopts, u16 *rest) *addr = IPA_NONE; +#ifdef IPV6 if (pxl > 0) _I0(*addr) = *buf++; if (pxl > 32) @@ -570,6 +753,7 @@ lsa_get_ipv6_prefix(u32 *buf, ip_addr *addr, int *pxlen, u8 *pxopts, u16 *rest) /* Clean up remaining bits */ if (pxl < 128) addr->addr[pxl / 32] &= u32_mkmask(pxl % 32); +#endif return buf; } @@ -613,183 +797,6 @@ struct ospf_lsreq_header }; -struct ospf_neighbor -{ - node n; - pool *pool; - struct ospf_iface *ifa; - u8 state; -#define NEIGHBOR_DOWN 0 -#define NEIGHBOR_ATTEMPT 1 -#define NEIGHBOR_INIT 2 -#define NEIGHBOR_2WAY 3 -#define NEIGHBOR_EXSTART 4 -#define NEIGHBOR_EXCHANGE 5 -#define NEIGHBOR_LOADING 6 -#define NEIGHBOR_FULL 7 - timer *inactim; /* Inactivity timer */ - u8 imms; /* I, M, Master/slave received */ - u8 myimms; /* I, M Master/slave */ - u32 dds; /* DD Sequence number being sent */ - u32 ddr; /* last Dat Des packet received */ - - u32 rid; /* Router ID */ - ip_addr ip; /* IP of it's interface */ - u8 priority; /* Priority */ - u8 adj; /* built adjacency? */ - u32 options; /* Options received */ - - /* Entries dr and bdr store IP addresses in OSPFv2 and router IDs in - OSPFv3, we use the same type to simplify handling */ - u32 dr; /* Neigbour's idea of DR */ - u32 bdr; /* Neigbour's idea of BDR */ - u32 iface_id; /* ID of Neighbour's iface connected to common network */ - - /* Database summary list iterator, controls initial dbdes exchange. - * Advances in the LSA list as dbdes packets are sent. - */ - siterator dbsi; /* iterator of po->lsal */ - - /* Link state request list, controls initial LSA exchange. - * Entries added when received in dbdes packets, removed as sent in lsreq packets. - */ - slist lsrql; /* slist of struct top_hash_entry from n->lsrqh */ - struct top_graph *lsrqh; - - /* Link state retransmission list, controls LSA retransmission during flood. - * Entries added as sent in lsupd packets, removed when received in lsack packets. - */ - slist lsrtl; /* slist of struct top_hash_entry from n->lsrth */ - struct top_graph *lsrth; - timer *rxmt_timer; /* RXMT timer */ - list ackl[2]; -#define ACKL_DIRECT 0 -#define ACKL_DELAY 1 - timer *ackd_timer; /* Delayed ack timer */ - struct bfd_request *bfd_req; /* BFD request, if BFD is used */ - void *ldd_buffer; /* Last database description packet */ - u32 ldd_bsize; /* Buffer size for ldd_buffer */ - u32 csn; /* Last received crypt seq number (for MD5) */ -}; - -/* Definitions for interface state machine */ -#define ISM_UP 0 /* Interface Up */ -#define ISM_WAITF 1 /* Wait timer fired */ -#define ISM_BACKS 2 /* Backup seen */ -#define ISM_NEICH 3 /* Neighbor change */ -#define ISM_LOOP 4 /* Link down */ -#define ISM_UNLOOP 5 /* Link up */ -#define ISM_DOWN 6 /* Interface down */ - -/* Definitions for neighbor state machine */ -#define INM_HELLOREC 0 /* Hello Received */ -#define INM_START 1 /* Neighbor start - for NBMA */ -#define INM_2WAYREC 2 /* 2-Way received */ -#define INM_NEGDONE 3 /* Negotiation done */ -#define INM_EXDONE 4 /* Exchange done */ -#define INM_BADLSREQ 5 /* Bad LS Request */ -#define INM_LOADDONE 6 /* Load done */ -#define INM_ADJOK 7 /* AdjOK? */ -#define INM_SEQMIS 8 /* Sequence number mismatch */ -#define INM_1WAYREC 9 /* 1-Way */ -#define INM_KILLNBR 10 /* Kill Neighbor */ -#define INM_INACTTIM 11 /* Inactivity timer */ -#define INM_LLDOWN 12 /* Line down */ - -struct ospf_area -{ - node n; - u32 areaid; - struct ospf_area_config *ac; /* Related area config */ - struct top_hash_entry *rt; /* My own router LSA */ - struct top_hash_entry *pxr_lsa; /* Originated prefix LSA */ - list cand; /* List of candidates for RT calc. */ - struct fib net_fib; /* Networks to advertise or not */ - struct fib enet_fib; /* External networks for NSSAs */ - u32 options; /* Optional features */ - u8 update_rt_lsa; /* Rt lsa origination scheduled? */ - u8 trcap; /* Transit capability? */ - u8 marked; /* Used in OSPF reconfigure */ - u8 translate; /* Translator state (TRANS_*), for NSSA ABR */ - timer *translator_timer; /* For NSSA translator switch */ - struct ospf_proto *po; - struct fib rtr; /* Routing tables for routers */ -}; - -#define TRANS_OFF 0 -#define TRANS_ON 1 -#define TRANS_WAIT 2 /* Waiting before the end of translation */ - -struct ospf_proto -{ - struct proto p; - timer *disp_timer; /* OSPF proto dispatcher */ - unsigned tick; - struct top_graph *gr; /* LSA graph */ - slist lsal; /* List of all LSA's */ - int calcrt; /* Routing table calculation scheduled? - 0=no, 1=normal, 2=forced reload */ - list iface_list; /* Interfaces we really use */ - list area_list; - int areano; /* Number of area I belong to */ - int padj; /* Number of neighbors in Exchange or Loading state */ - struct fib rtf; /* Routing table */ - byte ospf2; /* OSPF v2 or v3 */ - byte rfc1583; /* RFC1583 compatibility */ - byte stub_router; /* Do not forward transit traffic */ - byte merge_external; /* Should i merge external routes? */ - byte asbr; /* May i originate any ext/NSSA lsa? */ - byte ecmp; /* Maximal number of nexthops in ECMP route, or 0 */ - struct ospf_area *backbone; /* If exists */ - void *lsab; /* LSA buffer used when originating router LSAs */ - int lsab_size, lsab_used; - linpool *nhpool; /* Linpool used for next hops computed in SPF */ - sock *vlink_sk; /* IP socket used for vlink TX */ - u32 router_id; - u32 last_vlink_id; /* Interface IDs for vlinks (starts at 0x80000000) */ -}; - -struct ospf_iface_patt -{ - struct iface_patt i; - u32 type; - u32 stub; - u32 cost; - u32 helloint; - u32 rxmtint; - u32 pollint; - u32 waitint; - u32 deadc; - u32 deadint; - u32 inftransdelay; - list nbma_list; - u32 priority; - u32 voa; - u32 vid; - int tx_tos; - int tx_priority; - u16 tx_length; - u16 rx_buffer; - -#define OSPF_RXBUF_MINSIZE 256 /* Minimal allowed size */ - u8 instance_id; - u8 autype; /* Not really used in OSPFv3 */ -#define OSPF_AUTH_NONE 0 -#define OSPF_AUTH_SIMPLE 1 -#define OSPF_AUTH_CRYPT 2 -#define OSPF_AUTH_CRYPT_SIZE 16 - u8 strictnbma; - u8 check_link; - u8 ecmp_weight; - u8 link_lsa_suppression; - u8 real_bcast; /* Not really used in OSPFv3 */ - u8 ptp_netmask; /* bool + 2 for unspecified */ - u8 ttl_security; /* bool + 2 for TX only */ - u8 bfd; - u8 bsd_secondary; - list *passwords; -}; - #define SH_ROUTER_SELF 0xffffffff @@ -810,7 +817,7 @@ struct lsadb_show_data { /* ospf.c */ -void schedule_rtcalc(struct ospf_proto *p); +void ospf_schedule_rtcalc(struct ospf_proto *p); static inline void ospf_notify_rt_lsa(struct ospf_area *oa) { oa->update_rt_lsa = 1; } @@ -822,12 +829,15 @@ static inline void ospf_notify_link_lsa(struct ospf_iface *ifa) { ifa->update_link_lsa = 1; } +#define ospf_is_v2(X) OSPF_IS_V2 +#define ospf_is_v3(X) (!OSPF_IS_V2) +/* static inline int ospf_is_v2(struct ospf_proto *p) { return p->ospf2; } static inline int ospf_is_v3(struct ospf_proto *p) { return ! p->ospf2; } - +*/ static inline int ospf_get_version(struct ospf_proto *p) { return ospf_is_v2(p) ? 2 : 3; } @@ -920,7 +930,7 @@ void ospf_send_hello(struct ospf_iface *ifa, int kind, struct ospf_neighbor *dir void ospf_receive_hello(struct ospf_packet *pkt, struct ospf_iface *ifa, struct ospf_neighbor *n, ip_addr faddr); /* dbdes.c */ -void ospf_send_dbdes(struct ospf_neighbor *n, int next); +void ospf_send_dbdes(struct ospf_proto *p, struct ospf_neighbor *n, int next); void ospf_receive_dbdes(struct ospf_packet *pkt, struct ospf_iface *ifa, struct ospf_neighbor *n); /* lsreq.c */ @@ -930,7 +940,8 @@ void ospf_receive_lsreq(struct ospf_packet *pkt, struct ospf_iface *ifa, struct /* lsupd.c */ void ospf_dump_lsahdr(struct ospf_proto *p, struct ospf_lsa_header *lsa_n); void ospf_dump_common(struct ospf_proto *p, struct ospf_packet *pkt); -int ospf_lsupd_flood(struct ospf_proto *p, struct top_hash_entry *en, struct ospf_neighbor *from); +void ospf_add_flushed_to_lsrt(struct ospf_proto *p, struct ospf_neighbor *n); +int ospf_flood_lsa(struct ospf_proto *p, struct top_hash_entry *en, struct ospf_neighbor *from); int ospf_send_lsupd(struct ospf_proto *p, struct top_hash_entry **lsa_list, uint lsa_count, struct ospf_neighbor *n); void ospf_rxmt_lsupd(struct ospf_proto *p, struct ospf_neighbor *n); void ospf_receive_lsupd(struct ospf_packet *pkt, struct ospf_iface *ifa, struct ospf_neighbor *n); @@ -938,7 +949,7 @@ void ospf_receive_lsupd(struct ospf_packet *pkt, struct ospf_iface *ifa, struct /* lsack.c */ void ospf_enqueue_lsack(struct ospf_neighbor *n, struct ospf_lsa_header *h_n, int queue); void ospf_reset_lsack_queue(struct ospf_neighbor *n); -void ospf_lsack_send(struct ospf_neighbor *n, int queue); +void ospf_send_lsack(struct ospf_proto *p, struct ospf_neighbor *n, int queue); void ospf_receive_lsack(struct ospf_packet *pkt, struct ospf_iface *ifa, struct ospf_neighbor *n); diff --git a/proto/ospf/rt.c b/proto/ospf/rt.c index c4340ee5..9d146ce2 100644 --- a/proto/ospf/rt.c +++ b/proto/ospf/rt.c @@ -557,7 +557,7 @@ spfa_process_rt(struct ospf_proto *p, struct ospf_area *oa, struct top_hash_entr /* Errata 2078 to RFC 5340 4.8.1 - skip links from non-routing nodes */ if (ospf_is_v3(p) && (act != oa->rt) && !(rt->options & OPT_R)) - break; + return; /* Now process Rt links */ for (lsa_walk_rt_init(p, act, &rtl), i = 0; lsa_walk_rt(&rtl); i++) @@ -688,6 +688,8 @@ ospf_rt_spfa(struct ospf_area *oa) if (oa->rt == NULL) return; + if (oa->rt->lsa.age == LSA_MAXAGE) + return; OSPF_TRACE(D_EVENTS, "Starting routing table calculation for area %R", oa->areaid); @@ -1087,8 +1089,7 @@ check_sum_net_lsa(struct ospf_proto *p, ort *nf) struct area_net *anet = NULL; struct ospf_area *anet_oa = NULL; - /* RT entry marked as area network */ - if (nf->fn.flags & OSPF_RT_PERSISTENT) + if (nf->area_net) { /* It is a default route for stub areas, handled entirely in ospf_rt_abr() */ if (nf->fn.pxlen == 0) @@ -1162,8 +1163,7 @@ check_nssa_lsa(struct ospf_proto *p, ort *nf) if (nf->external_rte) return; - /* RT entry marked as area network */ - if (nf->fn.flags & OSPF_RT_PERSISTENT) + if (nf->area_net) { /* Find that area network */ WALK_LIST(oa, p->area_list) @@ -1176,12 +1176,12 @@ check_nssa_lsa(struct ospf_proto *p, ort *nf) /* RFC 3103 3.2 (3) - originate the aggregated address range */ if (anet && anet->active && !anet->hidden && oa->translate) - ospf_originate_ext_lsa(p, NULL, nf, LSA_RTCALC, anet->metric, + ospf_originate_ext_lsa(p, NULL, nf, LSA_M_RTCALC, anet->metric, (anet->metric & LSA_EXT3_EBIT), IPA_NONE, anet->tag, 0); /* RFC 3103 3.2 (2) - originate the same network */ else if (decide_nssa_lsa(p, nf, &rt)) - ospf_originate_ext_lsa(p, NULL, nf, LSA_RTCALC, rt.metric, rt.ebit, rt.fwaddr, rt.tag, 0); + ospf_originate_ext_lsa(p, NULL, nf, LSA_M_RTCALC, rt.metric, rt.ebit, rt.fwaddr, rt.tag, 0); } /* RFC 2328 16.7. p2 - find new/lost vlink endpoints */ @@ -1273,7 +1273,7 @@ ospf_rt_abr1(struct ospf_proto *p) /* Get a RT entry and mark it to know that it is an area network */ ort *nfi = (ort *) fib_get(&p->rtf, &anet->fn.prefix, anet->fn.pxlen); - nfi->fn.flags |= OSPF_RT_PERSISTENT; /* mark persistent, to have stable UID */ + nfi->area_net = 1; /* 16.2. (3) */ if (nfi->n.type == RTS_OSPF_IA) @@ -1289,7 +1289,7 @@ ospf_rt_abr1(struct ospf_proto *p) ip_addr addr = IPA_NONE; default_nf = (ort *) fib_get(&p->rtf, &addr, 0); - default_nf->fn.flags |= OSPF_RT_PERSISTENT; /* keep persistent */ + default_nf->area_net = 1; struct ospf_area *oa; WALK_LIST(oa, p->area_list) @@ -1309,7 +1309,7 @@ ospf_rt_abr1(struct ospf_proto *p) */ if (oa_is_nssa(oa) && oa->ac->default_nssa) - ospf_originate_ext_lsa(p, oa, default_nf, LSA_RTCALC, oa->ac->default_cost, + ospf_originate_ext_lsa(p, oa, default_nf, LSA_M_RTCALC, oa->ac->default_cost, (oa->ac->default_cost & LSA_EXT3_EBIT), IPA_NONE, 0, 0); /* RFC 2328 16.4. (3) - precompute preferred ASBR entries */ @@ -1348,7 +1348,7 @@ translator_timer_hook(timer *timer) return; oa->translate = TRANS_OFF; - schedule_rtcalc(oa->po); + ospf_schedule_rtcalc(oa->po); } static void @@ -1431,7 +1431,7 @@ ospf_rt_abr2(struct ospf_proto *p) /* Get a RT entry and mark it to know that it is an area network */ nf2 = (ort *) fib_get(&p->rtf, &anet->fn.prefix, anet->fn.pxlen); - nf2->fn.flags |= OSPF_RT_PERSISTENT; /* keep persistent */ + nf2->area_net = 1; } u32 metric = (nf->n.type == RTS_OSPF_EXT1) ? @@ -1634,7 +1634,7 @@ ospf_rt_reset(struct ospf_proto *p) FIB_WALK(&p->rtf, nftmp) { ri = (ort *) nftmp; - ri->fn.flags &= ~OSPF_RT_PERSISTENT; + ri->area_net = 0; reset_ri(ri); } FIB_WALK_END; @@ -1647,8 +1647,8 @@ ospf_rt_reset(struct ospf_proto *p) en->nhs = NULL; en->lb = IPA_NONE; - if (en->rtcalc == LSA_RTCALC) - en->rtcalc = LSA_STALE; + if (en->mode == LSA_M_RTCALC) + en->mode = LSA_M_STALE; } WALK_LIST(oa, p->area_list) @@ -1683,14 +1683,9 @@ ospf_rt_reset(struct ospf_proto *p) } } -static void -ospf_flush_stale(struct ospf_proto *p) -{ -} - /** * ospf_rt_spf - calculate internal routes - * @p: OSPF protocol + * @p: OSPF protocol instance * * Calculation of internal paths in an area is described in 16.1 of RFC 2328. * It's based on Dijkstra's shortest path tree algorithms. @@ -2064,8 +2059,8 @@ again1: rte_update(&p->p, ne, NULL); } - /* Remove unused rt entry. Entries with any flags are persistent. */ - if (!nf->n.type && !nf->external_rte) // XXXX + /* Remove unused rt entry, some special entries are persistent */ + if (!nf->n.type && !nf->external_rte && !nf->area_net) { FIB_ITERATE_PUT(&fit, nftmp); fib_delete(fib, nftmp); @@ -2096,6 +2091,6 @@ again2: /* Cleanup stale LSAs */ WALK_SLIST(en, p->lsal) - if (en->rtcalc == LSA_STALE) + if (en->mode == LSA_M_STALE) ospf_flush_lsa(p, en); } diff --git a/proto/ospf/rt.h b/proto/ospf/rt.h index 77d7080b..61936f3c 100644 --- a/proto/ospf/rt.h +++ b/proto/ospf/rt.h @@ -2,9 +2,10 @@ * BIRD -- OSPF * * (c) 2000--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. - * */ #ifndef _BIRD_OSPF_RT_H_ @@ -28,12 +29,17 @@ typedef struct orta #define ORTA_ASBR OPT_RT_E #define ORTA_ABR OPT_RT_B /* - * For ORT_NET routes, the field is almost unused with one - * exception: ORTA_PREF for external routes means that the route is - * preferred in AS external route selection according to 16.4.1. - - * it is intra-area path using non-backbone area. In other words, - * the forwarding address (or ASBR if forwarding address is zero) is - * intra-area (type == RTS_OSPF) and its area is not a backbone. + * For ORT_NET routes, there are just several flags for external routes: + * + * ORTA_PREF for external routes means that the route is preferred in AS + * external route selection according to 16.4.1. - it is intra-area path using + * non-backbone area. In other words, the forwarding address (or ASBR if + * forwarding address is zero) is intra-area (type == RTS_OSPF) and its area + * is not a backbone. + * + * ORTA_NSSA means that the entry represents an NSSA route, and ORTA_PROP + * means that the NSSA route has propagate-bit set. These flags are used in + * NSSA translation. */ #define ORTA_PREF 0x80000000 #define ORTA_NSSA 0x40000000 @@ -51,41 +57,38 @@ typedef struct orta } orta; - -/* Values for fn.flags in struct ort */ -#define OSPF_RT_PERSISTENT 0x01 - typedef struct ort { /* - * We use OSPF_RT_PERSISTENT to mark persistent rt entries, that are - * needed for summary LSAs that don't have 'proper' rt entry (area - * networks + default to stubs) to keep uid stable (used for LSA ID - * in OSPFv3 - see fibnode_to_lsaid()). - * - * We use ORT_RT_EXPORT and ORT_RT_NSSA to note whether the - * external/NSSA route was originated from the route export (in - * ospf_rt_notify()) or from the NSSA route translation (in - * check_nssa_lsa()). + * Most OSPF routing table entries are for computed OSPF routes, these have + * defined n.type. There are also few other cases: entries for configured area + * networks (these have area_net field set) and entries for external routes + * exported to OSPF (these have external_rte field set). These entries are + * kept even if they do not contain 'proper' rt entry. That is needed to keep + * allocated stable UID numbers (fn.uid), which are used as LSA IDs in OSPFv3 + * (see fibnode_to_lsaid()) for related LSAs (network summary LSAs in the + * first case, external or NSSA LSAs in the second case). Entries for external + * routes also have a second purpose - to prevent NSSA translation of received + * NSSA routes if regular external routes were already originated for the same + * network (see check_nssa_lsa()). * - * old_* values are here to represent the last route update. old_rta - * is cached (we keep reference), mainly for multipath nexthops. - * old_rta == NULL means route was not in the last update, in that - * case other old_* values are not valid. + * old_* values are here to represent the last route update. old_rta is cached + * (we keep reference), mainly for multipath nexthops. old_rta == NULL means + * route was not in the last update, in that case other old_* values are not + * valid. */ struct fib_node fn; orta n; u32 old_metric1, old_metric2, old_tag, old_rid; rta *old_rta; u8 external_rte; + u8 area_net; } ort; static inline int rt_is_nssa(ort *nf) { return nf->n.options & ORTA_NSSA; } -#define EXT_EXPORT 1 -#define EXT_NSSA 2 /* * Invariants for structs top_hash_entry (nodes of LSA db) @@ -97,7 +100,7 @@ static inline int rt_is_nssa(ort *nf) * - beware, nhs is not valid after SPF calculation * * Invariants for structs orta nodes of fib tables po->rtf, oa->rtr: - * - nodes may be invalid (fn.type == 0), in that case other invariants don't hold + * - nodes may be invalid (n.type == 0), in that case other invariants don't hold * - n.metric1 may be at most a small multiple of LSINFINITY, * therefore sums do not overflow * - n.oa is always non-NULL diff --git a/proto/ospf/topology.c b/proto/ospf/topology.c index 5ed3cf7a..bc2de79f 100644 --- a/proto/ospf/topology.c +++ b/proto/ospf/topology.c @@ -40,11 +40,13 @@ static inline void lsab_reset(struct ospf_proto *p); * 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) { - /* LSA can be temporary, but body must be mb_allocated. */ struct top_hash_entry *en; int change = 0; @@ -61,8 +63,8 @@ ospf_install_lsa(struct ospf_proto *p, struct ospf_lsa_header *lsa, u32 type, u3 memcmp(en->lsa_body, body, lsa->length - sizeof(struct ospf_lsa_header))) change = 1; - DBG("Inst lsa: Id: %R, Rt: %R, Type: %u, Age: %u, Sum: %u, Sn: 0x%x\n", - lsa->id, lsa->rt, lsa->type, lsa->age, lsa->checksum, lsa->sn); + if ((en->lsa.age == LSA_MAXAGE) && (lsa->age == LSA_MAXAGE)) + change = 0; mb_free(en->lsa_body); en->lsa_body = body; @@ -70,16 +72,43 @@ ospf_install_lsa(struct ospf_proto *p, struct ospf_lsa_header *lsa, u32 type, u3 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) - schedule_rtcalc(p); + 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) { - // OSPF_TRACE(D_EVENTS, "Reflooding new self-originated LSA with newer sequence number"); + /* RFC 2328 13.4 */ if (en && (en->lsa.age < LSA_MAXAGE)) { @@ -101,6 +130,9 @@ ospf_advance_lsa(struct ospf_proto *p, struct top_hash_entry *en, struct ospf_ls 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 { @@ -129,6 +161,11 @@ ospf_advance_lsa(struct ospf_proto *p, struct top_hash_entry *en, struct ospf_ls 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 @@ -137,6 +174,7 @@ ospf_advance_lsa(struct ospf_proto *p, struct top_hash_entry *en, struct ospf_ls * 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; @@ -150,7 +188,7 @@ ospf_advance_lsa(struct ospf_proto *p, struct top_hash_entry *en, struct ospf_ls * the neighbor we received it from), we cheat a bit here. */ - ospf_lsupd_flood(p, en, NULL); + ospf_flood_lsa(p, en, NULL); } @@ -167,11 +205,11 @@ ospf_do_originate_lsa(struct ospf_proto *p, struct top_hash_entry *en, void *lsa /* Prepare to flush old LSA */ if (en->lsa.age != LSA_MAXAGE) { - OSPF_TRACE(D_EVENTS, "Resetting LSA: Type: %04x, Id: %R, Rt: %R", - en->lsa_type, en->lsa.id, en->lsa.rt); + 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_lsupd_flood(p, en, NULL); + ospf_flood_lsa(p, en, NULL); return 0; } @@ -183,9 +221,6 @@ ospf_do_originate_lsa(struct ospf_proto *p, struct top_hash_entry *en, void *lsa en->lsa.sn = LSA_ZEROSEQNO; } - OSPF_TRACE(D_EVENTS, "Originating LSA: Type: %04x, Id: %R, Rt: %R", - en->lsa_type, en->lsa.id, en->lsa.rt); - /* * 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 @@ -205,7 +240,13 @@ ospf_do_originate_lsa(struct ospf_proto *p, struct top_hash_entry *en, void *lsa en->inst_time = now; lsasum_calculate(&en->lsa, en->lsa_body); - ospf_lsupd_flood(p, en, NULL); + 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; } @@ -244,15 +285,20 @@ ospf_originate_lsa(struct ospf_proto *p, struct ospf_new_lsa *lsa) { 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; } - /* XXXX check for maxage or opts change */ + 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)) + 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 */ @@ -263,13 +309,19 @@ ospf_originate_lsa(struct ospf_proto *p, struct ospf_new_lsa *lsa) } /* Ignore the the new LSA if is the same as the current one */ - if ((lsa_length == en->lsa.length) && !memcmp(lsa_body, en->lsa_body, lsa_blen)) + 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; @@ -293,8 +345,6 @@ ospf_originate_next_lsa(struct ospf_proto *p, struct top_hash_entry *en) en->next_lsa_body = NULL; en->next_lsa_blen = 0; en->next_lsa_opts = 0; - - // XXXX: schedule_rtcalc(p); } static void @@ -309,8 +359,8 @@ ospf_refresh_lsa(struct ospf_proto *p, struct top_hash_entry *en) * switched lsa.age to LSA_MAXAGE. */ - OSPF_TRACE(D_EVENTS, "Refreshing LSA: Type: %04x, Id: %R, Rt: %R", - en->lsa_type, en->lsa.id, en->lsa.rt); + 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); @@ -324,7 +374,7 @@ ospf_refresh_lsa(struct ospf_proto *p, struct top_hash_entry *en) en->next_lsa_opts = ospf_is_v2(p) ? lsa_get_options(&en->lsa) : 0; en->lsa.age = LSA_MAXAGE; - ospf_lsupd_flood(p, en, NULL); + ospf_flood_lsa(p, en, NULL); return; } @@ -333,7 +383,7 @@ ospf_refresh_lsa(struct ospf_proto *p, struct top_hash_entry *en) en->init_age = 0; en->inst_time = now; lsasum_calculate(&en->lsa, en->lsa_body); - ospf_lsupd_flood(p, en, NULL); + ospf_flood_lsa(p, en, NULL); } /** @@ -349,16 +399,13 @@ ospf_refresh_lsa(struct ospf_proto *p, struct top_hash_entry *en) * 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. Note that this function do not schedule routing table - * calculation, the caller is responsible to do it if necessary. + * origination. */ void ospf_flush_lsa(struct ospf_proto *p, struct top_hash_entry *en) { - OSPF_TRACE(D_EVENTS, "Flushing LSA: Type: %04x, Id: %R, Rt: %R", - en->lsa_type, en->lsa.id, en->lsa.rt); - - en->rtcalc = 0; + 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); if (en->next_lsa_body) { @@ -372,7 +419,12 @@ ospf_flush_lsa(struct ospf_proto *p, struct top_hash_entry *en) return; en->lsa.age = LSA_MAXAGE; - ospf_lsupd_flood(p, en, NULL); + ospf_flood_lsa(p, en, NULL); + + if (en->mode == LSA_M_BASIC) + ospf_schedule_rtcalc(p); + + en->mode = LSA_M_BASIC; } static void @@ -450,7 +502,6 @@ ospf_update_lsadb(struct ospf_proto *p) if (real_age >= LSA_MAXAGE) { ospf_flush_lsa(p, en); - schedule_rtcalc(p); continue; } @@ -510,9 +561,9 @@ ort_to_lsaid(struct ospf_proto *p, ort *nf) static void * -lsab_alloc(struct ospf_proto *p, unsigned size) +lsab_alloc(struct ospf_proto *p, uint size) { - unsigned offset = p->lsab_used; + uint offset = p->lsab_used; p->lsab_used += size; if (p->lsab_used > p->lsab_size) { @@ -524,7 +575,7 @@ lsab_alloc(struct ospf_proto *p, unsigned size) } static inline void * -lsab_allocz(struct ospf_proto *p, unsigned size) +lsab_allocz(struct ospf_proto *p, uint size) { void *r = lsab_alloc(p, size); bzero(r, size); @@ -547,7 +598,7 @@ lsab_reset(struct ospf_proto *p) } static inline void * -lsab_offset(struct ospf_proto *p, unsigned offset) +lsab_offset(struct ospf_proto *p, uint offset) { return ((byte *) p->lsab) + offset; } @@ -815,15 +866,6 @@ prepare_rt3_lsa_body(struct ospf_proto *p, struct ospf_area *oa) rt->options = get_rt_options(p, oa, bitv) | (oa->options & LSA_OPTIONS_MASK); } -/** - * ospf_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. - */ static void ospf_originate_rt_lsa(struct ospf_proto *p, struct ospf_area *oa) { @@ -834,6 +876,8 @@ ospf_originate_rt_lsa(struct ospf_proto *p, struct ospf_area *oa) .opts = oa->options }; + OSPF_TRACE(D_EVENTS, "Updating router state for area %R", oa->areaid); + if (ospf_is_v2(p)) prepare_rt2_lsa_body(p, oa); else @@ -908,15 +952,6 @@ prepare_net3_lsa_body(struct ospf_proto *p, struct ospf_iface *ifa) net->optx = options & LSA_OPTIONS_MASK; } -/** - * ospf_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. - */ static void ospf_originate_net_lsa(struct ospf_proto *p, struct ospf_iface *ifa) { @@ -928,6 +963,8 @@ ospf_originate_net_lsa(struct ospf_proto *p, struct ospf_iface *ifa) .ifa = ifa }; + OSPF_TRACE(D_EVENTS, "Updating network state for %s (Id: %R)", ifa->ifname, lsa.id); + if (ospf_is_v2(p)) prepare_net2_lsa_body(p, ifa); else @@ -977,10 +1014,9 @@ prepare_sum3_rt_lsa_body(struct ospf_proto *p, u32 drid, u32 metric, u32 options void ospf_originate_sum_net_lsa(struct ospf_proto *p, struct ospf_area *oa, ort *nf, int metric) { - struct top_hash_entry *en; - 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, @@ -992,32 +1028,26 @@ ospf_originate_sum_net_lsa(struct ospf_proto *p, struct ospf_area *oa, ort *nf, else prepare_sum3_net_lsa_body(p, nf, metric); - en = ospf_originate_lsa(p, &lsa); - en->rtcalc = LSA_RTCALC; + ospf_originate_lsa(p, &lsa); } void ospf_originate_sum_rt_lsa(struct ospf_proto *p, struct ospf_area *oa, ort *nf, int metric, u32 options) { - struct top_hash_entry *en; - u32 rid = ipa_to_rid(nf->fn.prefix); - - /* In OSPFv3, LSA ID is meaningless, but we still use Router ID of ASBR */ - struct ospf_new_lsa lsa = { .type = LSA_T_SUM_RT, + .mode = LSA_M_RTCALC, .dom = oa->areaid, - .id = rid, + .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 - prepare_sum3_rt_lsa_body(p, rid, metric, options & LSA_OPTIONS_MASK); + prepare_sum3_rt_lsa_body(p, lsa.id, metric, options & LSA_OPTIONS_MASK); - en = ospf_originate_lsa(p, &lsa); - en->rtcalc = LSA_RTCALC; + ospf_originate_lsa(p, &lsa); } @@ -1076,13 +1106,15 @@ prepare_ext3_lsa_body(struct ospf_proto *p, ort *nf, /** * 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 - * @src: the source of origination of the LSA (EXT_EXPORT/EXT_NSSA) - * @metric: the metric of a route (possibly with appropriate E-bit) + * @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, ignored for external LSAs + * @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. @@ -1091,13 +1123,12 @@ prepare_ext3_lsa_body(struct ospf_proto *p, ort *nf, * 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 rtcalc, +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 top_hash_entry *en; - 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, @@ -1109,8 +1140,7 @@ ospf_originate_ext_lsa(struct ospf_proto *p, struct ospf_area *oa, ort *nf, u8 r else prepare_ext3_lsa_body(p, nf, metric, ebit, fwaddr, tag, oa && pbit); - en = ospf_originate_lsa(p, &lsa); - en->rtcalc = rtcalc; + ospf_originate_lsa(p, &lsa); } static void @@ -1228,7 +1258,7 @@ ospf_rt_notify(struct proto *P, rtable *tbl UNUSED, net *n, rte *new, rte *old U /* Old external route might blocked some NSSA translation */ if ((p->areano > 1) && rt_is_nssa(nf) && nf->n.oa->translate) - schedule_rtcalc(p); + ospf_schedule_rtcalc(p); return; } @@ -1262,7 +1292,7 @@ ospf_rt_notify(struct proto *P, rtable *tbl UNUSED, net *n, rte *new, rte *old U } nf = (ort *) fib_get(&p->rtf, &n->n.prefix, n->n.pxlen); - ospf_originate_ext_lsa(p, oa, nf, 0, metric, ebit, fwd, tag, 1); + ospf_originate_ext_lsa(p, oa, nf, LSA_M_EXPORT, metric, ebit, fwd, tag, 1); nf->external_rte = 1; } @@ -1320,6 +1350,8 @@ ospf_originate_link_lsa(struct ospf_proto *p, struct ospf_iface *ifa) .ifa = ifa }; + OSPF_TRACE(D_EVENTS, "Updating link state for %s (Id: %R)", ifa->ifname, lsa.id); + prepare_link_lsa_body(p, ifa); ifa->link_lsa = ospf_originate_lsa(p, &lsa); @@ -1576,6 +1608,8 @@ ospf_originate_prefix_net_lsa(struct ospf_proto *p, struct ospf_iface *ifa) 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 ospf_update_topology(struct ospf_proto *p) @@ -1587,6 +1621,25 @@ ospf_update_topology(struct ospf_proto *p) { 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_originate_rt_lsa(p, oa); ospf_originate_prefix_rt_lsa(p, oa); oa->update_rt_lsa = 0; @@ -1624,8 +1677,6 @@ ospf_update_topology(struct ospf_proto *p) ifa->update_net_lsa = 0; } } - - // XXXX schedule_rtcalc(p); } @@ -1664,7 +1715,7 @@ ospf_top_hash_u32(u32 a) return a; } -static 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. @@ -1685,12 +1736,14 @@ ospf_top_hash(struct top_graph *f, u32 domain, u32 lsaid, u32 rtrid, u32 type) /** * ospf_top_new - allocated new topology database * @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; @@ -1701,6 +1754,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; } @@ -1715,8 +1769,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; @@ -1752,7 +1806,7 @@ ospf_hash_find(struct top_graph *f, u32 domain, u32 lsa, u32 rtr, u32 type) e = e->next; /* Hide hash entry with empty lsa_body */ - return e->lsa_body ? e : NULL; + return (e && e->lsa_body) ? e : NULL; } /* In OSPFv2, lsa.id is the same as lsa.rt for router LSA. In OSPFv3, we don't know @@ -1780,11 +1834,15 @@ ospf_hash_find_rt(struct top_graph *f, u32 domain, u32 rtr) 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_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 || e->lsa_body == NULL)) + e->domain != domain || e->lsa.age == LSA_MAXAGE)) e = e->next; return e; } @@ -1917,7 +1975,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++) @@ -1928,115 +1986,3 @@ ospf_top_dump(struct top_graph *f, struct proto *p) } } */ - - - -#if 0 - -void -update_rt_lsa(struct ospf_area *oa) -{ - struct ospf_proto *po = oa->po; - - if ((oa->rt) && ((oa->rt->inst_t + MINLSINTERVAL)) > now) - return; - - originate_rt_lsa(oa); - if (ospf_is_v3(p)) - originate_prefix_rt_lsa(oa); - - schedule_rtcalc(p); - oa->origrt = 0; -} - - - - -static inline int -check_sum2_net_lsa(struct top_hash_entry *en, struct fib_node *fn, u32 metric) -{ - struct ospf_lsa_sum2 *sum = en->lsa_body; - - if (fn->pxlen != ip4_masklen(sum->netmask)) - return -1; - - return (en->lsa.sn != LSA_MAXSEQNO) && (sum->metric == metric); -} - -static inline int -check_sum3_net_lsa(struct top_hash_entry *en, struct fib_node *fn, u32 metric) -{ - struct ospf_lsa_sum3_net *sum = en->lsa_body; - ip6_addr prefix; - int pxlen; - u8 pxopts; - u16 rest; - lsa_get_ipv6_prefix(sum->prefix, &prefix, &pxlen, &pxopts, &rest); - - - if ((fn->pxlen != pxlen) || !ip6_equal(fn->prefix, prefix)) - return -1; - - return (en->lsa.sn != LSA_MAXSEQNO) && (sum->metric == metric); -} - - -static int -check_sum_net_lsa(struct ospf_proto *po, struct top_hash_entry *en, struct fib_node *fn, u32 metric) -{ - int rv = ospf_is_v2(po) ? - check_sum2_net_lsa(en, fn, metric) : - check_sum3_net_lsa(en, fn, metric); - - if (rv < 0) - log(L_ERR "%s: LSAID collision for %I/%d", p->p.name, fn->prefix, fn->pxlen); - - return rv; -} - -static int -check_sum_rt_lsa(struct ospf_proto *po, struct top_hash_entry *en, u32 drid, u32 metric, u32 options) -{ - if (en->lsa.sn == LSA_MAXSEQNO) - return 0; - - if (ospf_is_v2(po)) - { - struct ospf_lsa_sum2 *sum = en->lsa_body; - return (sum->metric == metric); - } - else - { - struct ospf_lsa_sum3_rt *sum = en->lsa_body; - return (sum->options == options) && (sum->metric == metric) && (sum->drid == drid); - } -} - - - - - - - - OSPF_TRACE(D_EVENTS, "Originating router-LSA for area %R", oa->areaid); - OSPF_TRACE(D_EVENTS, "Originating network-LSA for iface %s", ifa->ifname); - OSPF_TRACE(D_EVENTS, "Originating net-summary-LSA for %I/%d (metric %d)", fn->prefix, fn->pxlen, metric); - OSPF_TRACE(D_EVENTS, "Originating rt-summary-LSA for %R (metric %d)", rid, metric); - OSPF_TRACE(D_EVENTS, "Originating %s-LSA for %I/%d", - nssa ? "NSSA" : "AS-external", fn->prefix, fn->pxlen); - OSPF_TRACE(D_EVENTS, "Originating link-LSA for iface %s", ifa->ifname); - OSPF_TRACE(D_EVENTS, "Originating router prefix-LSA for area %R", oa->areaid); - OSPF_TRACE(D_EVENTS, "Originating network prefix-LSA for iface %s", ifa->ifname); - - - en = ospf_hash_find(po->gr, lsa.dom, lsa.id, po->router_id, lsa.type); - if (en && check_ext_lsa(po, en, fn, metric, fwaddr, tag)) - return; - - *length = sizeof(struct ospf_lsa_header) + po->lsab_used; - return lsab_flush(po); - - *length = po->lsab_used + sizeof(struct ospf_lsa_header); - return lsab_flush(po); - -#endif diff --git a/proto/ospf/topology.h b/proto/ospf/topology.h index e4ea79f7..b34689e2 100644 --- a/proto/ospf/topology.h +++ b/proto/ospf/topology.h @@ -18,7 +18,7 @@ struct top_hash_entry in intra-area routing table calculation */ struct top_hash_entry *next; /* Next in hash chain */ struct ospf_lsa_header lsa; - u16 lsa_type; /* lsa.type processed and converted to common values */ + u16 lsa_type; /* lsa.type processed and converted to common values (LSA_T_*) */ u16 init_age; /* Initial value for lsa.age during inst_time */ u32 domain; /* Area ID for area-wide LSAs, Iface ID for link-wide LSAs */ // struct ospf_area *oa; @@ -37,13 +37,115 @@ struct top_hash_entry #define OUTSPF 0 #define CANDIDATE 1 #define INSPF 2 - u8 rtcalc; /* LSA generated during RT calculation (LSA_RTCALC or LSA_STALE)*/ + u8 mode; /* LSA generated during RT calculation (LSA_RTCALC or LSA_STALE)*/ u8 nhs_reuse; /* Whether nhs nodes can be reused during merging. See a note in rt.c:merge_nexthops() */ }; -#define LSA_RTCALC 1 -#define LSA_STALE 2 + +/* Prevents ospf_hash_find() to ignore the entry, for p->lsrqh and p->lsrth */ +#define LSA_BODY_DUMMY ((void *) 1) + +/* + * LSA entry life cycle + * + * LSA entries are created by ospf_originate_lsa() (for locally originated LSAs) + * or ospf_install_lsa() (for LSAs received from neighbors). A regular (like + * newly originated) LSA entry has defined lsa_body nad lsa.age < %LSA_MAXAGE. + * When the LSA is requested to be flushed by ospf_flush_lsa(), the lsa.age is + * set to %LSA_MAXAGE and flooded. Flush process is finished asynchronously, + * when (at least) flooding is acknowledged by neighbors. This is detected in + * ospf_update_lsadb(), then ospf_clear_lsa() is called to free the LSA body but + * the LSA entry is kept. Such LSA does not formally exist, we keep an empty + * entry (until regular timeout) to know inst_time and lsa.sn in the case of + * later reorigination. After the timeout, LSA is removed by ospf_remove_lsa(). + * + * When LSA origination is requested (by ospf_originate_lsa()). but it is not + * possible to do that immediately (because of MinLSInterval or because the + * sequence number is wrapping), The new LSA is scheduled for later origination + * in next_lsa_* fields of the LSA entry. The later origination is handled by + * ospf_originate_next_lsa() called from ospf_update_lsadb(). We can see that + * both real origination and final flush is asynchronous to ospf_originate_lsa() + * and ospf_flush_lsa(). + * + * LSA entry therefore could be in three basic states: + * R - regular (lsa.age < %LSA_MAXAGE, lsa_body != NULL) + * F - flushing (lsa.age == %LSA_MAXAGE, lsa_body != NULL) + * E - empty (lsa.age == %LSA_MAXAGE, lsa_body == NULL) + * + * And these states are doubled based on whether the next LSA is scheduled + * (next_lsa_body != NULL, -n suffix) or not (next_lsa_body == NULL). We also + * use X for a state of non-existentce. We have this basic state graph + * (transitions from any state to R are omitted for clarity): + * + * X --> R ---> F ---> E --> X + * | \ / | | + * | \/ | | + * | /\ | | + * | / \ | | + * Rn --> Fn --> En + * + * The transitions are: + * + * any state -> R - new LSA origination requested and executed + * R -> Rn, F -> Fn, E -> En - new LSA origination requested and postponed + * R -> Fn - new LSA origination requested, seqnum wrapping + * Rn,Fn,En -> R - postponed LSA finally originated + * R -> R - LSA refresh done + * R -> Fn - LSA refresh with seqnum wrapping + * R -> F, Rn -> Fn - LSA age timeout + * R,Rn,Fn -> F, En -> E - LSA flush requested + * F -> E, Fn -> En - LSA flush done (acknowledged) + * E -> X - LSA real age timeout (or immediate for received LSA) + * + * The 'origination requested' and 'flush requested' transitions are triggered + * and done by ospf_originate_lsa() and ospf_flush_lsa(), the rest is handled + * asynchronously by ospf_update_lsadb(). + * + * The situation is significantly simpler for non-local (received) LSAs - there + * is no postponed origination and after flushing is done, LSAs are immediately + * removed, so it is just X -> R -> F -> X, or X -> F -> X (when MaxAge LSA is + * received). + * + * There are also some special cases related to handling of received unknown + * self-originated LSAs in ospf_advance_lsa(): + * X -> F - LSA is received and immediately flushed + * R,Rn -> Fn - LSA with MaxSeqNo received and flushed, current LSA scheduled + */ + + +#define LSA_M_BASIC 0 +#define LSA_M_EXPORT 1 +#define LSA_M_RTCALC 2 +#define LSA_M_STALE 3 + +/* + * LSA entry modes: + * + * LSA_M_BASIC - The LSA is explicitly originated using ospf_originate_lsa() and + * explicitly flushed using ospf_flush_lsa(). When the LSA is changed, the + * routing table calculation is scheduled. This is also the mode used for LSAs + * received from neighbors. Example: Router-LSAs, Network-LSAs. + * + * LSA_M_EXPORT - like LSA_M_BASIC, but the routing table calculation does not + * depend on the LSA. Therefore, the calculation is not scheduled when the LSA + * is changed. Example: AS-external-LSAs for exported routes. + * + * LSA_M_RTCALC - The LSA has to be requested using ospf_originate_lsa() during + * each routing table calculation, otherwise it is flushed automatically at the + * end of the calculation. The LSA is a result of the calculation and not a + * source for it. Therefore, the calculation is not scheduled when the LSA is + * changed. Example: Summary-LSAs. + * + * LSA_M_STALE - Temporary state for LSA_M_RTCALC that is not requested during + * the current routing table calculation. + * + * + * Note that we do not schedule the routing table calculation when the age of + * LSA_M_BASIC LSA is changed to MaxAge because of the sequence number wrapping, + * As it will be switched back to a regular one ASAP. + */ + struct top_graph { @@ -61,6 +163,7 @@ struct top_graph struct ospf_new_lsa { u16 type; + u8 mode; u32 dom; u32 id; u16 opts; @@ -69,9 +172,8 @@ struct ospf_new_lsa struct ort *nf; }; -struct top_graph *ospf_top_new(pool *); -void ospf_top_free(struct top_graph *); -void ospf_top_dump(struct top_graph *, struct proto *); +struct top_graph *ospf_top_new(struct ospf_proto *p, pool *pool); +void ospf_top_free(struct top_graph *f); 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 * ospf_originate_lsa(struct ospf_proto *p, struct ospf_new_lsa *lsa); @@ -84,7 +186,7 @@ static inline void ospf_flush2_lsa(struct ospf_proto *p, struct top_hash_entry * void ospf_originate_sum_net_lsa(struct ospf_proto *p, struct ospf_area *oa, ort *nf, int metric); void ospf_originate_sum_rt_lsa(struct ospf_proto *p, struct ospf_area *oa, ort *nf, int metric, u32 options); -void ospf_originate_ext_lsa(struct ospf_proto *p, struct ospf_area *oa, ort *nf, u8 rtcalc, u32 metric, u32 ebit, ip_addr fwaddr, u32 tag, int pbit); +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); void ospf_rt_notify(struct proto *P, rtable *tbl, net *n, rte *new, rte *old, ea_list *attrs); void ospf_update_topology(struct ospf_proto *p); |