zebra: Remove linked list and replace with new LIST

The `struct rib_dest_t` was being used to store the linked
list of rnh's associated with the node.  This was taking up
a bunch of memory.  Replace with new data structure supplied
by David and see the memory reductions associated with 1 million
routes in the zebra rib:

Old:
Memory statistics for zebra:
System allocator statistics:
  Total heap allocated:  675 MiB
  Holding block headers: 0 bytes
  Used small blocks:     0 bytes
  Used ordinary blocks:  567 MiB
  Free small blocks:     39 MiB
  Free ordinary blocks:  69 MiB
  Ordinary blocks:       0
  Small blocks:          0
  Holding blocks:        0

New:
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

`struct rnh` was moved to rib.h because of the tangled web
of structure dependancies.  This data structure is used
in numerous places so it should be ok for the moment.
Future work might be needed to do a better job of splitting
up data structures and function definitions.

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

diff --git a/zebra/rib.h b/zebra/rib.h
index e26831e1a6427b7d4e2dda7f625aff06aa735d37..fd2aeabf57d7c4109bf3ee9fc997ac70a0fc1ef4 100644 (file)
--- a/zebra/rib.h
+++ b/zebra/rib.h
@@ -24,6 +24,7 @@
 
 #include "zebra.h"
 #include "hook.h"
+#include "typesafe.h"
 #include "linklist.h"
 #include "prefix.h"
 #include "table.h"
@@ -39,6 +40,44 @@
 extern "C" {
 #endif
 
+typedef enum { RNH_NEXTHOP_TYPE, RNH_IMPORT_CHECK_TYPE } rnh_type_t;
+
+PREDECL_LIST(rnh_list)
+
+/* Nexthop structure. */
+struct rnh {
+       uint8_t flags;
+
+#define ZEBRA_NHT_CONNECTED     0x1
+#define ZEBRA_NHT_DELETED       0x2
+#define ZEBRA_NHT_EXACT_MATCH   0x4
+
+       /* VRF identifier. */
+       vrf_id_t vrf_id;
+
+       afi_t afi;
+
+       rnh_type_t type;
+
+       uint32_t seqno;
+
+       struct route_entry *state;
+       struct prefix resolved_route;
+       struct list *client_list;
+
+       /* pseudowires dependent on this nh */
+       struct list *zebra_pseudowire_list;
+
+       struct route_node *node;
+
+       /*
+        * if this has been filtered for the client
+        */
+       int filtered[ZEBRA_ROUTE_MAX];
+
+       struct rnh_list_item rnh_list_item;
+};
+
 #define DISTANCE_INFINITY  255
 #define ZEBRA_KERNEL_TABLE_MAX 252 /* support for no more than this rt tables */
 
@@ -151,7 +190,7 @@ typedef struct rib_dest_t_ {
         * the data plane we will run evaluate_rnh
         * on these prefixes.
         */
-       struct list *nht;
+       struct rnh_list_head nht;
 
        /*
         * Linkage to put dest on the FPM processing queue.
@@ -160,6 +199,8 @@ typedef struct rib_dest_t_ {
 
 } rib_dest_t;
 
+DECLARE_LIST(rnh_list, struct rnh, rnh_list_item);
+
 #define RIB_ROUTE_QUEUED(x)    (1 << (x))
 // If MQ_SIZE is modified this value needs to be updated.
 #define RIB_ROUTE_ANY_QUEUED    0x1F

diff --git a/zebra/zebra_rib.c b/zebra/zebra_rib.c
index 2994911165f6bd35ced95d0946896f960006e881..f5ba619afa9b1384d8940e0b12d09a30de4d7846 100644 (file)
--- a/zebra/zebra_rib.c
+++ b/zebra/zebra_rib.c
@@ -1204,7 +1204,6 @@ static int rib_can_delete_dest(rib_dest_t *dest)
 void zebra_rib_evaluate_rn_nexthops(struct route_node *rn, uint32_t seq)
 {
        rib_dest_t *dest = rib_dest_from_rnode(rn);
-       struct listnode *node, *nnode;
        struct rnh *rnh;
 
        /*
@@ -1236,7 +1235,7 @@ void zebra_rib_evaluate_rn_nexthops(struct route_node *rn, uint32_t seq)
                 * nht resolution and as such we need to call the
                 * nexthop tracking evaluation code
                 */
-               for (ALL_LIST_ELEMENTS(dest->nht, node, nnode, rnh)) {
+               for_each (rnh_list, &dest->nht, rnh) {
                        struct zebra_vrf *zvrf =
                                zebra_vrf_lookup_by_id(rnh->vrf_id);
                        struct prefix *p = &rnh->node->p;
@@ -1312,7 +1311,7 @@ int rib_gc_dest(struct route_node *rn)
        zebra_rib_evaluate_rn_nexthops(rn, zebra_router_get_next_sequence());
 
        dest->rnode = NULL;
-       list_delete(&dest->nht);
+       rnh_list_fini(&dest->nht);
        XFREE(MTYPE_RIB_DEST, dest);
        rn->info = NULL;
 
@@ -2357,7 +2356,7 @@ rib_dest_t *zebra_rib_create_dest(struct route_node *rn)
        rib_dest_t *dest;
 
        dest = XCALLOC(MTYPE_RIB_DEST, sizeof(rib_dest_t));
-       dest->nht = list_new();
+       rnh_list_init(&dest->nht);
        route_lock_node(rn); /* rn route table reference */
        rn->info = dest;
        dest->rnode = rn;

diff --git a/zebra/zebra_rnh.c b/zebra/zebra_rnh.c
index 220a8006d011c8cd08d1c5dafbe778a4e9adf37b..2917d0e7a8ff19c8604df1a70609d137db79ecc0 100644 (file)
--- a/zebra/zebra_rnh.c
+++ b/zebra/zebra_rnh.c
@@ -119,7 +119,7 @@ static void zebra_rnh_remove_from_routing_table(struct rnh *rnh)
        }
 
        dest = rib_dest_from_rnode(rn);
-       listnode_delete(dest->nht, rnh);
+       rnh_list_del(&dest->nht, rnh);
        route_unlock_node(rn);
 }
 
@@ -145,7 +145,7 @@ static void zebra_rnh_store_in_routing_table(struct rnh *rnh)
        }
 
        dest = rib_dest_from_rnode(rn);
-       listnode_add(dest->nht, rnh);
+       rnh_list_add_tail(&dest->nht, rnh);
        route_unlock_node(rn);
 }
 
@@ -251,7 +251,7 @@ void zebra_free_rnh(struct rnh *rnh)
                        route_unlock_node(rern);
 
                        dest = rib_dest_from_rnode(rern);
-                       listnode_delete(dest->nht, rnh);
+                       rnh_list_del(&dest->nht, rnh);
                }
        }
        free_state(rnh->vrf_id, rnh->state, rnh->node);

diff --git a/zebra/zebra_rnh.h b/zebra/zebra_rnh.h
index 9cd9116eed01c9673ad1ecb4593c9dde5d26bf02..95a39411816ff4be7920f95c5934cd548deb2205 100644 (file)
--- a/zebra/zebra_rnh.h
+++ b/zebra/zebra_rnh.h
@@ -29,40 +29,6 @@
 extern "C" {
 #endif
 
-typedef enum { RNH_NEXTHOP_TYPE, RNH_IMPORT_CHECK_TYPE } rnh_type_t;
-
-/* Nexthop structure. */
-struct rnh {
-       uint8_t flags;
-
-#define ZEBRA_NHT_CONNECTED    0x1
-#define ZEBRA_NHT_DELETED       0x2
-#define ZEBRA_NHT_EXACT_MATCH   0x4
-
-       /* VRF identifier. */
-       vrf_id_t vrf_id;
-
-       afi_t afi;
-
-       rnh_type_t type;
-
-       uint32_t seqno;
-
-       struct route_entry *state;
-       struct prefix resolved_route;
-       struct list *client_list;
-
-       /* pseudowires dependent on this nh */
-       struct list *zebra_pseudowire_list;
-
-       struct route_node *node;
-
-       /*
-        * if this has been filtered for the client
-        */
-       int filtered[ZEBRA_ROUTE_MAX];
-};
-
 extern int zebra_rnh_ip_default_route;
 extern int zebra_rnh_ipv6_default_route;
 

diff --git a/zebra/zebra_vrf.c b/zebra/zebra_vrf.c
index 2d721ec8a1a53ca6e8a396e438b0184ace37ceb8..f0b99f41fccc95c00915468ccf46be4b4c920670 100644 (file)
--- a/zebra/zebra_vrf.c
+++ b/zebra/zebra_vrf.c
@@ -357,7 +357,7 @@ void zebra_rtable_node_cleanup(struct route_table *table,
        if (node->info) {
                rib_dest_t *dest = node->info;
 
-               list_delete(&dest->nht);
+               rnh_list_fini(&dest->nht);
                XFREE(MTYPE_RIB_DEST, node->info);
        }
 }