lib: Convert table code to use new hash type

This converts the new table code to use the new hash
type provided by David.

The following test is 1 million routes installed and how
much memory we are using:

Old mem usage:
Memory statistics for zebra:
System allocator statistics:
  Total heap allocated:  574 MiB
  Holding block headers: 0 bytes
  Used small blocks:     0 bytes
  Used ordinary blocks:  536 MiB
  Free small blocks:     33 MiB
  Free ordinary blocks:  4600 KiB
  Ordinary blocks:       0
  Small blocks:          0
  Holding blocks:        0

New Memory usage:
Memory statistics for zebra:
System allocator statistics:
  Total heap allocated:  542 MiB
  Holding block headers: 0 bytes
  Used small blocks:     0 bytes
  Used ordinary blocks:  506 MiB
  Free small blocks:     3374 KiB
  Free ordinary blocks:  33 MiB
  Ordinary blocks:       0
  Small blocks:          0
  Holding blocks:        0

Signed-off-by: Donald Sharp <sharpd@cumulusnetworks.com>

diff --git a/lib/table.c b/lib/table.c
index edba7f1932455181bf85657c238a40bab5c21a2d..2d42e2d55c904fe8942f497df267cd979c610df9 100644 (file)
--- a/lib/table.c
+++ b/lib/table.c
@@ -33,12 +33,14 @@ DEFINE_MTYPE(LIB, ROUTE_NODE, "Route node")
 
 static void route_table_free(struct route_table *);
 
-static bool route_table_hash_cmp(const void *a, const void *b)
+static int route_table_hash_cmp(const void *a, const void *b)
 {
        const struct prefix *pa = a, *pb = b;
-       return prefix_cmp(pa, pb) == 0;
+       return prefix_cmp(pa, pb);
 }
 
+DECLARE_HASH(rn_hash_node, struct route_node, nodehash, route_table_hash_cmp,
+            prefix_hash_key)
 /*
  * route_table_init_with_delegate
  */
@@ -49,8 +51,7 @@ route_table_init_with_delegate(route_table_delegate_t *delegate)
 
        rt = XCALLOC(MTYPE_ROUTE_TABLE, sizeof(struct route_table));
        rt->delegate = delegate;
-       rt->hash = hash_create(prefix_hash_key, route_table_hash_cmp,
-                              "route table hash");
+       rn_hash_node_init(&rt->hash);
        return rt;
 }
 
@@ -69,15 +70,14 @@ static struct route_node *route_node_new(struct route_table *table)
 static struct route_node *route_node_set(struct route_table *table,
                                         const struct prefix *prefix)
 {
-       struct route_node *node, *inserted;
+       struct route_node *node;
 
        node = route_node_new(table);
 
        prefix_copy(&node->p, prefix);
        node->table = table;
 
-       inserted = hash_get(node->table->hash, node, hash_alloc_intern);
-       assert(inserted == node);
+       rn_hash_node_add(&node->table->hash, node);
 
        return node;
 }
@@ -99,9 +99,6 @@ static void route_table_free(struct route_table *rt)
        if (rt == NULL)
                return;
 
-       hash_clean(rt->hash, NULL);
-       hash_free(rt->hash);
-
        node = rt->top;
 
        /* Bulk deletion of nodes remaining in this table.  This function is not
@@ -123,6 +120,7 @@ static void route_table_free(struct route_table *rt)
 
                tmp_node->table->count--;
                tmp_node->lock = 0; /* to cause assert if unlocked after this */
+               rn_hash_node_del(&rt->hash, tmp_node);
                route_node_free(rt, tmp_node);
 
                if (node != NULL) {
@@ -137,6 +135,7 @@ static void route_table_free(struct route_table *rt)
 
        assert(rt->count == 0);
 
+       rn_hash_node_fini(&rt->hash);
        XFREE(MTYPE_ROUTE_TABLE, rt);
        return;
 }
@@ -257,7 +256,7 @@ struct route_node *route_node_lookup(const struct route_table *table,
        prefix_copy(&p, pu.p);
        apply_mask(&p);
 
-       node = hash_get(table->hash, (void *)&p, NULL);
+       node = rn_hash_node_find(&table->hash, (void *)&p);
        return (node && node->info) ? route_lock_node(node) : NULL;
 }
 
@@ -270,7 +269,7 @@ struct route_node *route_node_lookup_maynull(const struct route_table *table,
        prefix_copy(&p, pu.p);
        apply_mask(&p);
 
-       node = hash_get(table->hash, (void *)&p, NULL);
+       node = rn_hash_node_find(&table->hash, (void *)&p);
        return node ? route_lock_node(node) : NULL;
 }
 
@@ -282,12 +281,11 @@ struct route_node *route_node_get(struct route_table *const table,
        struct route_node *new;
        struct route_node *node;
        struct route_node *match;
-       struct route_node *inserted;
        uint16_t prefixlen = p->prefixlen;
        const uint8_t *prefix = &p->u.prefix;
 
        apply_mask((struct prefix *)p);
-       node = hash_get(table->hash, (void *)p, NULL);
+       node = rn_hash_node_find(&table->hash, (void *)p);
        if (node && node->info)
                return route_lock_node(node);
 
@@ -314,8 +312,7 @@ struct route_node *route_node_get(struct route_table *const table,
                new->p.family = p->family;
                new->table = table;
                set_link(new, node);
-               inserted = hash_get(node->table->hash, new, hash_alloc_intern);
-               assert(inserted == new);
+               rn_hash_node_add(&table->hash, new);
 
                if (match)
                        set_link(match, new);
@@ -367,7 +364,7 @@ void route_node_delete(struct route_node *node)
 
        node->table->count--;
 
-       hash_release(node->table->hash, node);
+       rn_hash_node_del(&node->table->hash, node);
 
        /* WARNING: FRAGILE CODE!
         * route_node_free may have the side effect of free'ing the entire

diff --git a/lib/table.h b/lib/table.h
index ce578e795c648f782fbffc8c64aead792fb8d5bf..3e3fb658aebe011df1ded9fde4bab856489b1b7c 100644 (file)
--- a/lib/table.h
+++ b/lib/table.h
@@ -25,6 +25,7 @@
 #include "memory.h"
 #include "hash.h"
 #include "prefix.h"
+#include "typesafe.h"
 
 #ifdef __cplusplus
 extern "C" {
@@ -59,10 +60,12 @@ struct route_table_delegate_t_ {
        route_table_destroy_node_func_t destroy_node;
 };
 
+PREDECL_HASH(rn_hash_node)
+
 /* Routing table top structure. */
 struct route_table {
        struct route_node *top;
-       struct hash *hash;
+       struct rn_hash_node_head hash;
 
        /*
         * Delegate that performs certain functions for this table.
@@ -129,6 +132,7 @@ struct route_table {
        /* Lock of this radix */                                               \
        unsigned int table_rdonly(lock);                                       \
                                                                                \
+       struct rn_hash_node_item nodehash;                                     \
        /* Each node of route. */                                              \
        void *info;                                                            \