From aa57abfbb57c2dd31eeb26d6988af57cb2e15a6b Mon Sep 17 00:00:00 2001 From: Donald Sharp Date: Tue, 30 Apr 2019 18:04:57 -0400 Subject: [PATCH] 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 --- zebra/rib.h | 43 ++++++++++++++++++++++++++++++++++++++++++- zebra/zebra_rib.c | 7 +++---- zebra/zebra_rnh.c | 6 +++--- zebra/zebra_rnh.h | 34 ---------------------------------- zebra/zebra_vrf.c | 2 +- 5 files changed, 49 insertions(+), 43 deletions(-) diff --git a/zebra/rib.h b/zebra/rib.h index e26831e1a6..fd2aeabf57 100644 --- 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 2994911165..f5ba619afa 100644 --- 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 220a8006d0..2917d0e7a8 100644 --- 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 9cd9116eed..95a3941181 100644 --- 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 2d721ec8a1..f0b99f41fc 100644 --- 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); } } -- 2.39.5