From d82fc18d75e4ebf615657cb5d98f000c728b13e4 Mon Sep 17 00:00:00 2001 From: Ondrej Zajicek Date: Wed, 7 Oct 2009 21:10:29 +0100 Subject: Implement proper LSA ID generation. --- nest/route.h | 1 + nest/rt-fib.c | 41 +++++++++++++++++++++++++++-- proto/ospf/ospf.c | 4 ++- proto/ospf/rt.c | 2 +- proto/ospf/topology.c | 71 ++++++++++++++++++++++++++++++++++++++++++++------- 5 files changed, 106 insertions(+), 13 deletions(-) diff --git a/nest/route.h b/nest/route.h index 1bd23a6..e45a8c6 100644 --- a/nest/route.h +++ b/nest/route.h @@ -37,6 +37,7 @@ struct fib_node { byte pxlen; byte flags; /* User-defined */ byte x0, x1; /* User-defined */ + u32 uid; /* Unique ID based on hash */ ip_addr prefix; /* In host order */ }; diff --git a/nest/rt-fib.c b/nest/rt-fib.c index 8d76f26..510aa76 100644 --- a/nest/rt-fib.c +++ b/nest/rt-fib.c @@ -172,6 +172,28 @@ fib_find(struct fib *f, ip_addr *a, int len) return e; } +/* +int +fib_histogram(struct fib *f) +{ + log(L_WARN "Histogram dump start %d %d", f->hash_size, f->entries); + + int i, j; + struct fib_node *e; + + for (i = 0; i < f->hash_size; i++) + { + j = 0; + for (e = f->hash_table[i]; e != NULL; e = e->next) + j++; + if (j > 0) + log(L_WARN "Histogram line %d: %d", i, j); + } + + log(L_WARN "Histogram dump end"); +} +*/ + /** * fib_get - find or create a FIB node * @f: FIB to work with @@ -187,6 +209,7 @@ fib_get(struct fib *f, ip_addr *a, int len) unsigned int h = ipa_hash(*a); struct fib_node **ee = f->hash_table + (h >> f->hash_shift); struct fib_node *g, *e = *ee; + u32 uid = h << 16; while (e && (e->pxlen != len || !ipa_equal(*a, e->prefix))) e = e->next; @@ -196,17 +219,31 @@ fib_get(struct fib *f, ip_addr *a, int len) if (len < 0 || len > BITS_PER_IP_ADDRESS || !ip_is_prefix(*a,len)) bug("fib_get() called for invalid address"); #endif + + while ((g = *ee) && g->uid < uid) + ee = &g->next; + while ((g = *ee) && g->uid == uid) + { + ee = &g->next; + uid++; + } + + if ((uid >> 16) != h) + log(L_ERR "FIB hash table chains are too long"); + + // log (L_WARN "FIB_GET %I %x %x", *a, h, uid); + e = sl_alloc(f->fib_slab); e->prefix = *a; e->pxlen = len; - while ((g = *ee) && ipa_hash(g->prefix) < h) - ee = &g->next; e->next = *ee; + e->uid = uid; *ee = e; e->readers = NULL; f->init(e); if (f->entries++ > f->entries_max) fib_rehash(f, HASH_HI_STEP); + return e; } diff --git a/proto/ospf/ospf.c b/proto/ospf/ospf.c index dafb607..0c4d673 100644 --- a/proto/ospf/ospf.c +++ b/proto/ospf/ospf.c @@ -605,7 +605,9 @@ ospf_reconfigure(struct proto *p, struct proto_config *c) struct area_net_config *anc; struct area_net *an; - po->rfc1583 = new->rfc1583; + if (po->rfc1583 != new->rfc1583) + return 0; + schedule_rtcalc(po); po->tick = new->tick; diff --git a/proto/ospf/rt.c b/proto/ospf/rt.c index 416223f..68b6c82 100644 --- a/proto/ospf/rt.c +++ b/proto/ospf/rt.c @@ -18,7 +18,7 @@ static void ospf_ext_spf(struct proto_ospf *po); static void rt_sync(struct proto_ospf *po); /* In ospf_area->rtr we store paths to routers, but we use RID (and not IP address) - as index, so we need to encapsulate RID to IP addresss */ + as index, so we need to encapsulate RID to IP address */ #ifdef OSPFv2 #define ipa_from_rid(x) _MI(x) #else /* OSPFv3 */ diff --git a/proto/ospf/topology.c b/proto/ospf/topology.c index 182f644..6f7905b 100644 --- a/proto/ospf/topology.c +++ b/proto/ospf/topology.c @@ -30,11 +30,64 @@ void flush_prefix_net_lsa(struct ospf_iface *ifa); #define ipa_to_rid(x) _I3(x) #endif -/* FIXME very ugly hack */ + #ifdef OSPFv2 -#define ipa_to_lsaid(x) _I(x) +static inline u32 +fibnode_to_lsaid(struct proto_ospf *po, struct fib_node *fn) +{ + /* We have to map IP prefixes to u32 in such manner that resulting + u32 interpreted as IP address is a member of given + prefix. Therefore, /32 prefix have to be mapped on itself. + All received prefixes have to be mapped on different u32s. + + We have an assumption that if there is nontrivial (non-/32) + network prefix, then there is not /32 prefix for the first + and the last IP address of the network (these are usually + reserved, therefore it is not an important restriction). + The network prefix is mapped to the first or the last + IP address in the manner that disallow collisions - we + use IP address that cannot be used by parent prefix. + + For example: + 192.168.0.0/24 maps to 192.168.0.255 + 192.168.1.0/24 maps to 192.168.1.0 + because 192.168.0.0 and 192.168.1.255 might be used by + 192.168.0.0/23 . + + This is not compatible with older RFC 1583, so we have an option + to the RFC 1583 compatible assignment (that always uses the first + address) which disallows subnetting. + + Appendig E of RFC 2328 suggests different algorithm, that tries + to maximize both compatibility and subnetting. But as it is not + possible to have both reliably and the suggested algorithm was + unnecessary complicated and it does crazy things like changing + LSA ID for a network because different network appeared, we + choose a different way. */ + + u32 id = _I(fn->prefix); + + if ((po->rfc1583) || (fn->pxlen == 0) || (fn->pxlen == 32)) + return id; + + if (id & (1 << (32 - fn->pxlen))) + return id; + else + return id | ~u32_mkmask(fn->pxlen); +} + #else /* OSPFv3 */ -#define ipa_to_lsaid(x) _I0(x) ^ _I1(x) ^ _I2(x) ^ _I3(x) + +static inline u32 +fibnode_to_lsaid(struct proto_ospf *po, struct fib_node *fn) +{ + /* In OSPFv3, it is simpler. There is not a requirement + for membership of the result in input network, so we + just use hash-based unique ID. */ + + return fn->uid; +} + #endif @@ -660,8 +713,7 @@ originate_sum_lsa(struct ospf_area *oa, struct fib_node *fn, int type, int metri if (type == ORT_NET) { - /* FIXME proper handling of LSA IDs and check for the same network */ - lsa.id = ipa_to_lsaid(fn->prefix); + lsa.id = fibnode_to_lsaid(po, fn); lsa.type = LSA_T_SUM_NET; } else @@ -710,8 +762,7 @@ flush_sum_lsa(struct ospf_area *oa, struct fib_node *fn, int type) lsa.rt = rid; if (type == ORT_NET) { - /* FIXME proper handling of LSA IDs and check for the same network */ - lsa.id = ipa_to_lsaid(fn->prefix); + lsa.id = fibnode_to_lsaid(po, fn); lsa.type = LSA_T_SUM_NET; } else @@ -721,6 +772,8 @@ flush_sum_lsa(struct ospf_area *oa, struct fib_node *fn, int type) lsa.type = LSA_T_SUM_RT; } + /* FIXME check for the same network */ + if ((en = ospf_hash_find_header(po->gr, oa->areaid, &lsa)) != NULL) { struct ospf_lsa_sum *sum = en->lsa_body; @@ -892,7 +945,7 @@ originate_ext_lsa(net * n, rte * e, struct proto_ospf *po, #endif /* FIXME proper handling of LSA IDs and check for the same network */ - lsa.id = ipa_to_lsaid(n->n.prefix); + lsa.id = fibnode_to_lsaid(po, &n->n); if ((en = ospf_hash_find_header(po->gr, 0, &lsa)) != NULL) { @@ -927,7 +980,7 @@ flush_ext_lsa(net *n, struct proto_ospf *po) 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); + u32 lsaid = fibnode_to_lsaid(po, &n->n); if (en = ospf_hash_find(po->gr, 0, lsaid, rid, LSA_T_EXT)) { -- cgit v1.2.3