From be862406627da3bd1facea9309b3f32e67422eab Mon Sep 17 00:00:00 2001 From: Ondrej Zajicek Date: Tue, 8 Sep 2009 13:45:02 +0200 Subject: Temporary OSPFv3 development commit. Finally, it is working. --- lib/ipv4.h | 6 +++ lib/ipv6.h | 6 +++ nest/iface.h | 1 + nest/neighbor.c | 36 ++++++++------- proto/ospf/iface.c | 1 + proto/ospf/lsalib.c | 2 - proto/ospf/lsupd.c | 7 +++ proto/ospf/ospf.c | 20 ++++++++- proto/ospf/ospf.h | 9 +++- proto/ospf/rt.c | 3 +- proto/ospf/topology.c | 99 +++++++++++++++++++++++++----------------- sysdep/linux/netlink/netlink.c | 8 ++++ 12 files changed, 135 insertions(+), 63 deletions(-) diff --git a/lib/ipv4.h b/lib/ipv4.h index b64d9b2..5c8c390 100644 --- a/lib/ipv4.h +++ b/lib/ipv4.h @@ -54,6 +54,7 @@ typedef u32 ip_addr; #define ipa_hton(x) x = _MI(htonl(_I(x))) #define ipa_ntoh(x) x = _MI(ntohl(_I(x))) #define ipa_classify(x) ipv4_classify(_I(x)) +#define ipa_has_link_scope(x) ipv4_has_link_scope(_I(x)) #define ipa_opposite(x,len) _MI(_I(x) ^ (len == 30 ? 3 : 1)) #define ipa_class_mask(x) _MI(ipv4_class_mask(_I(x))) #define ipa_from_u32(x) _MI(x) @@ -69,6 +70,11 @@ int ipv4_classify(u32); u32 ipv4_class_mask(u32); byte *ipv4_skip_header(byte *, int *); +static inline int ipv4_has_link_scope(u32 a) +{ + return 0; +} + static inline unsigned ipv4_hash(u32 a) { /* Returns a 16-bit value */ diff --git a/lib/ipv6.h b/lib/ipv6.h index 592e57c..53888ff 100644 --- a/lib/ipv6.h +++ b/lib/ipv6.h @@ -60,6 +60,7 @@ typedef struct ipv6_addr { #define ipa_hton(x) ipv6_hton(&(x)) #define ipa_ntoh(x) ipv6_ntoh(&(x)) #define ipa_classify(x) ipv6_classify(&(x)) +#define ipa_has_link_scope(x) ipv6_has_link_scope(&(x)) /* ipa_opposite and ipa_class_mask don't make sense with IPv6 */ /* ipa_from_u32 and ipa_to_u32 replaced by ipa_build */ #define ipa_build(a,b,c,d) _MI(a,b,c,d) @@ -81,6 +82,11 @@ int ipv6_compare(ip_addr, ip_addr); int ipv4_pton_u32(char *, u32 *); void ipv6_absolutize(ip_addr *, ip_addr *); +static inline int ipv6_has_link_scope(ip_addr *a) +{ + return ((a->addr[0] & 0xffc00000) == 0xfe800000); +} + /* * This hash function looks well, but once IPv6 enters * mainstream use, we need to check that it has good diff --git a/nest/iface.h b/nest/iface.h index af98a76..a982c17 100644 --- a/nest/iface.h +++ b/nest/iface.h @@ -99,6 +99,7 @@ typedef struct neighbor { #define NEF_STICKY 1 neighbor *neigh_find(struct proto *, ip_addr *, unsigned flags); +neighbor *neigh_find2(struct proto *p, ip_addr *a, struct iface *ifa, unsigned flags); static inline int neigh_connected_to(struct proto *p, ip_addr *a, struct iface *i) { diff --git a/nest/neighbor.c b/nest/neighbor.c index 7aaf8d7..a44667f 100644 --- a/nest/neighbor.c +++ b/nest/neighbor.c @@ -100,21 +100,21 @@ if_connected(ip_addr *a, struct iface *i) /* -1=error, 1=match, 0=no match */ * IP address, neigh_find() returns %NULL. */ -/* + neighbor * neigh_find(struct proto *p, ip_addr *a, unsigned flags) { return neigh_find2(p, a, NULL, flags); } -*/ + neighbor * -neigh_find(struct proto *p, ip_addr *a, unsigned flags) +neigh_find2(struct proto *p, ip_addr *a, struct iface *ifa, unsigned flags) { neighbor *n; int class, scope = SCOPE_HOST; unsigned int h = neigh_hash(p, a); - struct iface *i, *j; + struct iface *i; WALK_LIST(n, neigh_hash_table[h]) /* Search the cache */ if (n->proto == p && ipa_equal(*a, n->addr)) @@ -123,27 +123,31 @@ neigh_find(struct proto *p, ip_addr *a, unsigned flags) class = ipa_classify(*a); if (class < 0) /* Invalid address */ return NULL; - if ((class & IADDR_SCOPE_MASK) < SCOPE_SITE || + if (((class & IADDR_SCOPE_MASK) == SCOPE_HOST) || + (((class & IADDR_SCOPE_MASK) == SCOPE_LINK) && (ifa == NULL)) || !(class & IADDR_HOST)) return NULL; /* Bad scope or a somecast */ - j = NULL; - WALK_LIST(i, iface_list) - if ((scope = if_connected(a, i)) >= 0) - { - j = i; - break; - } - if (!j && !(flags & NEF_STICKY)) + if (ifa) + scope = if_connected(a, ifa); + else + WALK_LIST(i, iface_list) + if ((scope = if_connected(a, i)) >= 0) + { + ifa = i; + break; + } + + if (!ifa && !(flags & NEF_STICKY)) return NULL; n = sl_alloc(neigh_slab); n->addr = *a; - n->iface = j; - if (j) + n->iface = ifa; + if (ifa) { add_tail(&neigh_hash_table[h], &n->n); - add_tail(&j->neighbors, &n->if_n); + add_tail(&ifa->neighbors, &n->if_n); } else { diff --git a/proto/ospf/iface.c b/proto/ospf/iface.c index fc1cf2a..9b65961 100644 --- a/proto/ospf/iface.c +++ b/proto/ospf/iface.c @@ -381,6 +381,7 @@ ospf_iface_add(struct object_lock *lock) ifa->state = OSPF_IS_DOWN; ospf_iface_sm(ifa, ISM_UP); + schedule_link_lsa(ifa); } void diff --git a/proto/ospf/lsalib.c b/proto/ospf/lsalib.c index 8442882..31b5118 100644 --- a/proto/ospf/lsalib.c +++ b/proto/ospf/lsalib.c @@ -462,9 +462,7 @@ lsa_install_new(struct proto_ospf *po, struct ospf_lsa_header *lsa, u32 domain, en->ini_age = en->lsa.age; if (change) - { schedule_rtcalc(po); - } return en; } diff --git a/proto/ospf/lsupd.c b/proto/ospf/lsupd.c index bccdba8..cb79461 100644 --- a/proto/ospf/lsupd.c +++ b/proto/ospf/lsupd.c @@ -627,6 +627,13 @@ ospf_lsupd_receive(struct ospf_packet *ps_i, struct ospf_iface *ifa, lsadb = lsa_install_new(po, &lsatmp, domain, body); DBG("New LSA installed in DB\n"); +#ifdef OSPFv3 + /* Events 6,7 from 4.4.3. */ + if ((lsatmp.type == LSA_T_LINK) && + (ifa->state == OSPF_IS_DR)) + schedule_net_lsa(ifa); +#endif + continue; } diff --git a/proto/ospf/ospf.c b/proto/ospf/ospf.c index 438e9a5..dafb607 100644 --- a/proto/ospf/ospf.c +++ b/proto/ospf/ospf.c @@ -307,15 +307,29 @@ ospf_build_attrs(ea_list * next, struct linpool *pool, u32 m1, u32 m2, void schedule_net_lsa(struct ospf_iface *ifa) { + struct proto *p = &ifa->oa->po->proto; + + OSPF_TRACE(D_EVENTS, "Scheduling network-LSA origination for iface %s", ifa->iface->name); ifa->orignet = 1; } +#ifdef OSPFv3 +void +schedule_link_lsa(struct ospf_iface *ifa) +{ + struct proto *p = &ifa->oa->po->proto; + + OSPF_TRACE(D_EVENTS, "Scheduling link-LSA origination for iface %s", ifa->iface->name); + ifa->origlink = 1; +} +#endif + void schedule_rt_lsa(struct ospf_area *oa) { struct proto *p = &oa->po->proto; - OSPF_TRACE(D_EVENTS, "Scheduling RT lsa origination for area %R.", oa->areaid); + OSPF_TRACE(D_EVENTS, "Scheduling router-LSA origination for area %R", oa->areaid); oa->origrt = 1; } @@ -327,7 +341,7 @@ schedule_rtcalc(struct proto_ospf *po) if (po->calcrt) return; - OSPF_TRACE(D_EVENTS, "Scheduling RT calculation."); + OSPF_TRACE(D_EVENTS, "Scheduling routing table calculation"); po->calcrt = 1; } @@ -353,6 +367,7 @@ area_disp(struct ospf_area *oa) WALK_LIST(ifa, po->iface_list) { #ifdef OSPFv3 + /* Link LSA should be originated before Network LSA */ if (ifa->origlink && (ifa->oa == oa)) update_link_lsa(ifa); #endif @@ -478,6 +493,7 @@ ospf_ifa_notify(struct proto *p, unsigned flags, struct ifa *a) if (ifa->iface == a->iface) { schedule_rt_lsa(ifa->oa); + schedule_link_lsa(ifa); return; } } diff --git a/proto/ospf/ospf.h b/proto/ospf/ospf.h index ae073dd..4bcb7a0 100644 --- a/proto/ospf/ospf.h +++ b/proto/ospf/ospf.h @@ -232,8 +232,8 @@ struct ospf_iface struct top_hash_entry *net_lsa; /* Originated network LSA */ int orignet; /* Schedule network LSA origination */ #ifdef OSPFv3 - struct top_hash_entry *link_lsa; /* Originated link LSA */ int origlink; /* Schedule link LSA origination */ + struct top_hash_entry *link_lsa; /* Originated link LSA */ struct top_hash_entry *pxn_lsa; /* Originated prefix LSA */ #endif int fadj; /* Number of full adjacent neigh */ @@ -734,6 +734,13 @@ void ospf_store_tmp_attrs(struct rte *rt, struct ea_list *attrs); void schedule_rt_lsa(struct ospf_area *oa); void schedule_rtcalc(struct proto_ospf *po); void schedule_net_lsa(struct ospf_iface *ifa); + +#ifdef OSPFv3 +void schedule_link_lsa(struct ospf_iface *ifa); +#else +static inline void schedule_link_lsa(struct ospf_iface *ifa) {} +#endif + void ospf_sh_neigh(struct proto *p, char *iff); void ospf_sh(struct proto *p); void ospf_sh_iface(struct proto *p, char *iff); diff --git a/proto/ospf/rt.c b/proto/ospf/rt.c index 0f6efd7..9d3aea0 100644 --- a/proto/ospf/rt.c +++ b/proto/ospf/rt.c @@ -321,7 +321,6 @@ ospf_rt_spfa(struct ospf_area *oa) } rr = (struct ospf_lsa_rt_link *) (rt + 1); - DBG(" Number of links: %u\n", rt->links); for (i = 0; i < lsa_rt_count(&act->lsa); i++) { tmp = NULL; @@ -1178,7 +1177,7 @@ again1: if (nf->n.ifa) a0.iface = nf->n.ifa->iface; a0.gw = nf->n.nh; - if ((!ipa_equal(nf->n.nh, IPA_NONE)) && (!neigh_find(p, &nf->n.nh, 0))) + if (ipa_nonzero(nf->n.nh) && (!neigh_find2(p, &nf->n.nh, nf->n.ifa->iface, 0))) { int found = 0; struct ospf_iface *ifa; diff --git a/proto/ospf/topology.c b/proto/ospf/topology.c index 8f64c4c..cadf4ea 100644 --- a/proto/ospf/topology.c +++ b/proto/ospf/topology.c @@ -168,9 +168,6 @@ originate_rt_lsa_body(struct ospf_area *oa, u16 *length) struct ospf_lsa_rt_link *ln; struct ospf_neighbor *neigh; - DBG("%s: Originating RT_lsa body for area %R.\n", po->proto.name, - oa->areaid); - ASSERT(po->lsab_used == 0); rt = lsab_allocz(po, sizeof(struct ospf_lsa_rt)); @@ -322,9 +319,6 @@ originate_rt_lsa_body(struct ospf_area *oa, u16 *length) struct ospf_lsa_rt *rt; struct ospf_neighbor *neigh; - DBG("%s: Originating RT_lsa body for area %R.\n", po->proto.name, - oa->areaid); - ASSERT(po->lsab_used == 0); rt = lsab_allocz(po, sizeof(struct ospf_lsa_rt)); @@ -411,7 +405,7 @@ originate_rt_lsa(struct ospf_area *oa) u32 rid = po->proto.cf->global->router_id; void *body; - OSPF_TRACE(D_EVENTS, "Originating RT_lsa for area %R.", oa->areaid); + OSPF_TRACE(D_EVENTS, "Originating router-LSA for area %R", oa->areaid); lsa.age = 0; lsa.type = LSA_T_RT; @@ -522,7 +516,7 @@ originate_net_lsa(struct ospf_iface *ifa) struct proto *p = &po->proto; void *body; - OSPF_TRACE(D_EVENTS, "Originating Net lsa for iface \"%s\".", + OSPF_TRACE(D_EVENTS, "Originating network-LSA for iface %s", ifa->iface->name); lsa.age = 0; @@ -554,7 +548,7 @@ flush_net_lsa(struct ospf_iface *ifa) if (ifa->net_lsa == NULL) return; - OSPF_TRACE(D_EVENTS, "Deleting Net lsa for iface \"%s\".", + OSPF_TRACE(D_EVENTS, "Flushing network-LSA for iface %s", ifa->iface->name); ifa->net_lsa->lsa.sn += 1; ifa->net_lsa->lsa.age = LSA_MAXAGE; @@ -685,14 +679,14 @@ originate_sum_lsa(struct ospf_area *oa, struct fib_node *fn, int type, int metri if (type == ORT_NET) { - OSPF_TRACE(D_EVENTS, "Originating Net-Summary-LSA for %I/%d (metric %d).", + OSPF_TRACE(D_EVENTS, "Originating summary-LSA for %I/%d (metric %d)", fn->prefix, fn->pxlen, metric); body = originate_sum_net_lsa_body(po, &lsa.length, fn, metric); } else { - OSPF_TRACE(D_EVENTS, "Originating RT-Summary-LSA for %R (metric %d).", + OSPF_TRACE(D_EVENTS, "Originating summary-LSA for %R (metric %d)", lsa.id, metric); body = originate_sum_rt_lsa_body(po, &lsa.length, lsa.id, metric, options); @@ -734,7 +728,7 @@ flush_sum_lsa(struct ospf_area *oa, struct fib_node *fn, int type) en->lsa.sn = LSA_MAXSEQNO; lsasum_calculate(&en->lsa, sum); - OSPF_TRACE(D_EVENTS, "Flushing summary lsa. (id=%R, type=%d)", + OSPF_TRACE(D_EVENTS, "Flushing summary-LSA (id=%R, type=%d)", en->lsa.id, en->lsa.type); ospf_lsupd_flood(po, NULL, NULL, &en->lsa, oa->areaid, 1); if (can_flush_lsa(po)) flush_lsa(en, po); @@ -879,15 +873,15 @@ void originate_ext_lsa(net * n, rte * e, struct proto_ospf *po, struct ea_list *attrs) { + struct proto *p = &po->proto; struct ospf_lsa_header lsa; u32 rid = po->proto.cf->global->router_id; struct top_hash_entry *en = NULL; void *body; - struct proto *p = &po->proto; struct ospf_area *oa; - OSPF_TRACE(D_EVENTS, "Originating Ext lsa for %I/%d.", n->n.prefix, - n->n.pxlen); + OSPF_TRACE(D_EVENTS, "Originating AS-external-LSA for %I/%d", + n->n.prefix, n->n.pxlen); lsa.age = 0; lsa.type = LSA_T_EXT; @@ -924,10 +918,14 @@ originate_ext_lsa(net * n, rte * e, struct proto_ospf *po, void flush_ext_lsa(net *n, struct proto_ospf *po) { + struct proto *p = &po->proto; u32 rid = po->proto.cf->global->router_id; struct ospf_area *oa; struct top_hash_entry *en; + OSPF_TRACE(D_EVENTS, "Flushing AS-external-LSA for %I/%d", + n->n.prefix, n->n.pxlen); + /* FIXME proper handling of LSA IDs and check for the same network */ u32 lsaid = ipa_to_lsaid(n->n.prefix); @@ -987,7 +985,7 @@ originate_link_lsa(struct ospf_iface *ifa) void *body; /* FIXME check for vlink and skip that? */ - OSPF_TRACE(D_EVENTS, "Originating Link_lsa for iface %s.", ifa->iface->name); + OSPF_TRACE(D_EVENTS, "Originating link-LSA for iface %s", ifa->iface->name); lsa.age = 0; lsa.type = LSA_T_LINK; @@ -1000,6 +998,10 @@ originate_link_lsa(struct ospf_iface *ifa) lsasum_calculate(&lsa, body); ifa->link_lsa = lsa_install_new(po, &lsa, dom, body); ospf_lsupd_flood(po, NULL, NULL, &lsa, dom, 1); + + /* Just to be sure to not forget on our link LSA */ + if (ifa->state == OSPF_IS_DR) + schedule_net_lsa(ifa); } void @@ -1050,6 +1052,7 @@ originate_prefix_rt_lsa_body(struct ospf_area *oa, u16 *length) if (((a->pxlen < MAX_PREFIX_LENGTH) && net_lsa) || (a->flags & IA_SECONDARY) || (a->flags & IA_UNNUMBERED) || + (a->scope <= SCOPE_LINK) || configured_stubnet(oa, a)) continue; @@ -1081,14 +1084,17 @@ originate_prefix_rt_lsa_body(struct ospf_area *oa, u16 *length) void originate_prefix_rt_lsa(struct ospf_area *oa) { - struct ospf_lsa_header lsa; struct proto_ospf *po = oa->po; + struct proto *p = &po->proto; u32 rid = po->proto.cf->global->router_id; + struct ospf_lsa_header lsa; void *body; + OSPF_TRACE(D_EVENTS, "Originating router prefix-LSA for area %R", oa->areaid); + lsa.age = 0; lsa.type = LSA_T_PREFIX; - lsa.id = 1 << 31; + lsa.id = 0; lsa.rt = rid; lsa.sn = oa->pxr_lsa ? (oa->pxr_lsa->lsa.sn + 1) : LSA_INITSEQNO; u32 dom = oa->areaid; @@ -1128,12 +1134,14 @@ prefix_same(u32 *b1, u32 *b2) static inline u32 * prefix_advance(u32 *buf) { - return buf + prefix_space(buf); + int pxl = *buf >> 24; + return buf + IPV6_PREFIX_WORDS(pxl); } static void -add_prefix(struct proto_ospf *po, u32 *px, u32 *pxl, int *pxc) +add_prefix(struct proto_ospf *po, u32 *px, int offset, int *pxc) { + u32 *pxl = lsab_offset(po, offset); int i; for (i = 0; i < *pxc; i++) { @@ -1154,19 +1162,31 @@ add_prefix(struct proto_ospf *po, u32 *px, u32 *pxl, int *pxc) (*pxc)++; } +static void +add_link_lsa(struct proto_ospf *po, struct top_hash_entry *en, int offset, int *pxc) +{ + struct ospf_lsa_link *ll = en->lsa_body; + u32 *pxb = ll->rest; + int j; + + for (j = 0; j < ll->pxcount; j++) + { + add_prefix(po, pxb, offset, pxc); + pxb = prefix_advance(pxb); + } +} + + static void * originate_prefix_net_lsa_body(struct ospf_iface *ifa, u16 *length) { struct proto_ospf *po = ifa->oa->po; struct ospf_lsa_prefix *lp; - struct ospf_lsa_link *ll; struct ospf_neighbor *n; struct top_hash_entry *en; u32 rid = po->proto.cf->global->router_id; - u32 *pxb; - int i, j, offset; - + int pxc, offset; ASSERT(po->lsab_used == 0); lp = lsab_allocz(po, sizeof(struct ospf_lsa_prefix)); @@ -1175,26 +1195,20 @@ originate_prefix_net_lsa_body(struct ospf_iface *ifa, u16 *length) lp->ref_rt = rid; lp = NULL; /* buffer might be reallocated later */ - i = 0; + pxc = 0; offset = po->lsab_used; - /* Find all Link LSA associated with the link and merge their prefixes */ + /* Find all Link LSAs associated with the link and merge their prefixes */ + if (ifa->link_lsa) + add_link_lsa(po, ifa->link_lsa, offset, &pxc); + WALK_LIST(n, ifa->neigh_list) if ((n->state == NEIGHBOR_FULL) && (en = ospf_hash_find(po->gr, ifa->iface->index, n->iface_id, n->rid, LSA_T_LINK))) - { - ll = en->lsa_body; - pxb = ll->rest; - - for (j = 0; j < ll->pxcount; j++) - { - add_prefix(po, pxb, lsab_offset(po, offset), &i); - pxb = prefix_advance(pxb); - } - } + add_link_lsa(po, en, offset, &pxc); lp = po->lsab; - lp->pxcount = i; + lp->pxcount = pxc; *length = po->lsab_used + sizeof(struct ospf_lsa_header); return lsab_flush(po); } @@ -1202,11 +1216,15 @@ originate_prefix_net_lsa_body(struct ospf_iface *ifa, u16 *length) void originate_prefix_net_lsa(struct ospf_iface *ifa) { - struct ospf_lsa_header lsa; struct proto_ospf *po = ifa->oa->po; + struct proto *p = &po->proto; u32 rid = po->proto.cf->global->router_id; + struct ospf_lsa_header lsa; void *body; + OSPF_TRACE(D_EVENTS, "Originating network prefix-LSA for iface %s", + ifa->iface->name); + lsa.age = 0; lsa.type = LSA_T_PREFIX; lsa.id = ifa->iface->index; @@ -1231,8 +1249,9 @@ flush_prefix_net_lsa(struct ospf_iface *ifa) if (en == NULL) return; - OSPF_TRACE(D_EVENTS, "Flushing Net Prefix lsa for iface \"%s\".", + OSPF_TRACE(D_EVENTS, "Flushing network prefix-LSA for iface %s", ifa->iface->name); + en->lsa.sn += 1; en->lsa.age = LSA_MAXAGE; lsasum_calculate(&en->lsa, en->lsa_body); @@ -1283,7 +1302,7 @@ ospf_top_hash_u32(u32 a) static inline unsigned 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. + /* In OSPFv2, we don't know Router ID when looking for network LSAs. dirty patch to make rt table calculation work. */ return (ospf_top_hash_u32(lsaid) + type + diff --git a/sysdep/linux/netlink/netlink.c b/sysdep/linux/netlink/netlink.c index b7fd479..0f7b707 100644 --- a/sysdep/linux/netlink/netlink.c +++ b/sysdep/linux/netlink/netlink.c @@ -472,6 +472,9 @@ krt_capable(rte *e) switch (a->dest) { case RTD_ROUTER: + if (ipa_has_link_scope(a->gw) && (a->iface == NULL)) + return 0; + case RTD_DEVICE: case RTD_BLACKHOLE: case RTD_UNREACHABLE: @@ -514,6 +517,11 @@ nl_send_route(struct krt_proto *p, rte *e, int new) case RTD_ROUTER: r.r.rtm_type = RTN_UNICAST; nl_add_attr_ipa(&r.h, sizeof(r), RTA_GATEWAY, a->gw); + + /* a->iface != NULL checked in krt_capable() */ + if (ipa_has_link_scope(a->gw)) + nl_add_attr_u32(&r.h, sizeof(r), RTA_OIF, a->iface->index); + break; case RTD_DEVICE: if (!a->iface) -- cgit v1.2.3