diff options
Diffstat (limited to 'nest')
| -rw-r--r-- | nest/iface.h | 1 | ||||
| -rw-r--r-- | nest/neighbor.c | 38 | ||||
| -rw-r--r-- | nest/route.h | 1 | ||||
| -rw-r--r-- | nest/rt-fib.c | 41 |
4 files changed, 66 insertions, 15 deletions
diff --git a/nest/iface.h b/nest/iface.h index af98a761..a982c17f 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 2c5af6a6..a44667f5 100644 --- a/nest/neighbor.c +++ b/nest/neighbor.c @@ -100,13 +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_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)) @@ -115,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/nest/route.h b/nest/route.h index 1bd23a6b..e45a8c62 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 8d76f26f..510aa76b 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; } |