diff options
Diffstat (limited to 'nest')
| -rw-r--r-- | nest/route.h | 5 | ||||
| -rw-r--r-- | nest/rt-attr.c | 139 |
2 files changed, 119 insertions, 25 deletions
diff --git a/nest/route.h b/nest/route.h index 8b14c85..74fbf9c 100644 --- a/nest/route.h +++ b/nest/route.h @@ -215,8 +215,7 @@ void rt_show(struct rt_show_data *); */ typedef struct rta { - struct rta *next, *prev; /* Hash chain */ - struct rta *garbage; /* Garbage collector chain */ + struct rta *next, **pprev; /* Hash chain */ struct proto *proto; /* Protocol instance */ unsigned uc; /* Use count */ byte source; /* Route source (RTS_...) */ @@ -225,7 +224,7 @@ typedef struct rta { byte dest; /* Route destination type (RTD_...) */ byte flags; /* Route flags (RTF_...), now unused */ byte aflags; /* Attribute cache flags (RTAF_...) */ - byte rfu, rfu2; /* Padding */ + u16 hash_key; /* Hash over important fields */ ip_addr gw; /* Next hop */ ip_addr from; /* Advertising router */ struct iface *iface; /* Outgoing interface */ diff --git a/nest/rt-attr.c b/nest/rt-attr.c index 99d063e..43bf5fe 100644 --- a/nest/rt-attr.c +++ b/nest/rt-attr.c @@ -1,7 +1,7 @@ /* * BIRD -- Route Attribute Cache * - * (c) 1998--1999 Martin Mares <mj@ucw.cz> + * (c) 1998--2000 Martin Mares <mj@ucw.cz> * * Can be freely distributed and used under the terms of the GNU GPL. */ @@ -16,11 +16,6 @@ #include "nest/cli.h" #include "lib/resource.h" -/* - * FIXME: Implement hash tables and garbage collection! - */ - -static rta *first_rta; static slab *rta_slab; static pool *rta_pool; @@ -150,9 +145,7 @@ ea_sort(ea_list *e) ea_do_prune(e); e->flags |= EALF_SORTED; } -#if 0 /* FIXME: Remove this after some testing */ if (e->count > 5) -#endif e->flags |= EALF_BISECT; e = e->next; } @@ -278,10 +271,70 @@ ea_dump(ea_list *e) } } +static inline unsigned int +ea_hash(ea_list *e) +{ + u32 h = 0; + int i; + + if (e) /* Assuming chain of length 1 */ + { + for(i=0; i<e->count; i++) + { + struct eattr *a = &e->attrs[i]; + h ^= a->id; + if (a->type & EAF_EMBEDDED) + h ^= a->u.data; + else + { + struct adata *d = a->u.ptr; + int size = d->length; + byte *z = d->data; + while (size >= 4) + { + h ^= *(u32 *)z; + z += 4; + size -= 4; + } + while (size--) + h = (h >> 24) ^ (h << 8) ^ *z++; + } + } + h ^= h >> 16; + h ^= h >> 6; + h &= 0xffff; + } + return h; +} + /* * rta's */ +static unsigned int rta_cache_count; +static unsigned int rta_cache_size = 32; +static unsigned int rta_cache_limit; +static unsigned int rta_cache_mask; +static rta **rta_hash_table; + +static void +rta_alloc_hash(void) +{ + rta_hash_table = mb_alloc(rta_pool, sizeof(rta *) * rta_cache_size); + bzero(rta_hash_table, sizeof(rta *) * rta_cache_size); + if (rta_cache_size < 32768) + rta_cache_limit = rta_cache_size * 2; + else + rta_cache_limit = ~0; + rta_cache_mask = rta_cache_size - 1; +} + +static inline unsigned int +rta_hash(rta *a) +{ + return a->proto->hash_key ^ ipa_hash(a->gw) ^ ea_hash(a->eattrs); +} + static inline int rta_same(rta *x, rta *y) { @@ -308,10 +361,42 @@ rta_copy(rta *o) return r; } +static inline void +rta_insert(rta *r) +{ + unsigned int h = r->hash_key & rta_cache_mask; + r->next = rta_hash_table[h]; + if (r->next) + r->next->pprev = &r->next; + r->pprev = &rta_hash_table[h]; + rta_hash_table[h] = r; +} + +static void +rta_rehash(void) +{ + unsigned int ohs = rta_cache_size; + unsigned int h; + rta *r, *n; + rta **oht = rta_hash_table; + + rta_cache_size = 2*rta_cache_size; + DBG("Rehashing rta cache from %d to %d entries.\n", ohs, rta_cache_size); + rta_alloc_hash(); + for(h=0; h<ohs; h++) + for(r=oht[h]; r; r=n) + { + n = r->next; + rta_insert(r); + } + mb_free(oht); +} + rta * rta_lookup(rta *o) { rta *r; + unsigned int h; ASSERT(!(o->aflags & RTAF_CACHED)); if (o->eattrs) @@ -325,20 +410,27 @@ rta_lookup(rta *o) ea_sort(o->eattrs); } - for(r=first_rta; r; r=r->next) - if (rta_same(r, o)) + h = rta_hash(o); + for(r=rta_hash_table[h & rta_cache_mask]; r; r=r->next) + if (r->hash_key == h && rta_same(r, o)) return rta_clone(r); r = rta_copy(o); + r->hash_key = h; r->aflags = RTAF_CACHED; - r->next = first_rta; - first_rta = r; + rta_insert(r); + + if (++rta_cache_count > rta_cache_limit) + rta_rehash(); + return r; } void rta__free(rta *a) { + ASSERT(rta_cache_count && (a->aflags & RTAF_CACHED)); + rta_cache_count--; } void @@ -351,9 +443,9 @@ rta_dump(rta *a) static char *rtc[] = { "", " BC", " MC", " AC" }; static char *rtd[] = { "", " DEV", " HOLE", " UNREACH", " PROHIBIT" }; - debug("p=%s uc=%d %s %s%s%s", + debug("p=%s uc=%d %s %s%s%s h=%04x", a->proto->name, a->uc, rts[a->source], ip_scope_text(a->scope), rtc[a->cast], - rtd[a->dest]); + rtd[a->dest], a->hash_key); if (!(a->aflags & RTAF_CACHED)) debug(" !CACHED"); debug(" <-%I", a->from); @@ -372,14 +464,16 @@ void rta_dump_all(void) { rta *a; - - debug("Route attribute cache:\n"); - for(a=first_rta; a; a=a->next) - { - debug("%p ", a); - rta_dump(a); - debug("\n"); - } + unsigned int h; + + debug("Route attribute cache (%d entries, rehash at %d):\n", rta_cache_count, rta_cache_limit); + for(h=0; h<rta_cache_size; h++) + for(a=rta_hash_table[h]; a; a=a->next) + { + debug("%p ", a); + rta_dump(a); + debug("\n"); + } debug("\n"); } @@ -400,4 +494,5 @@ rta_init(void) { rta_pool = rp_new(&root_pool, "Attributes"); rta_slab = sl_new(rta_pool, sizeof(rta)); + rta_alloc_hash(); } |