From 806f87607e6b41f67cd1550bc8a9b579522fb15c Mon Sep 17 00:00:00 2001 From: Renato Westphal Date: Sat, 29 Oct 2016 20:30:57 -0200 Subject: [PATCH] lib/zebra: convert vrf_list to a red-black tree Since we're already using a red-black tree to store VRFs sorted by their vrf_id's, create a new tree to store VRFs sorted by their names. The biggest advantage of doing this is that we reduce the time complexity of vrf_list_lookup_by_name() from O(n) to O(log n). Signed-off-by: Renato Westphal --- lib/vrf.c | 50 +++++++++++++++-------------------------------- lib/vrf.h | 6 ++++-- zebra/zebra_vrf.c | 3 +-- zebra/zebra_vty.c | 9 +++------ 4 files changed, 24 insertions(+), 44 deletions(-) diff --git a/lib/vrf.c b/lib/vrf.c index 2d2c55f7a..3def16151 100644 --- a/lib/vrf.c +++ b/lib/vrf.c @@ -36,10 +36,13 @@ DEFINE_MTYPE_STATIC(LIB, VRF_BITMAP, "VRF bit-map") DEFINE_QOBJ_TYPE(vrf) static __inline int vrf_id_compare (struct vrf *, struct vrf *); +static __inline int vrf_name_compare (struct vrf *, struct vrf *); RB_GENERATE (vrf_id_head, vrf, id_entry, vrf_id_compare) +RB_GENERATE (vrf_name_head, vrf, name_entry, vrf_name_compare) struct vrf_id_head vrfs_by_id = RB_INITIALIZER (&vrfs_by_id); +struct vrf_name_head vrfs_by_name = RB_INITIALIZER (&vrfs_by_name); /* * Turn on/off debug code @@ -56,9 +59,6 @@ struct vrf_master int (*vrf_disable_hook) (vrf_id_t, const char *, void **); } vrf_master = {0,}; -/* VRF is part of a list too to store it before its actually active */ -struct list *vrf_list; - static int vrf_is_enabled (struct vrf *vrf); static void vrf_disable (struct vrf *vrf); @@ -66,16 +66,9 @@ static void vrf_disable (struct vrf *vrf); struct vrf * vrf_list_lookup_by_name (const char *name) { - struct listnode *node; - struct vrf *vrfp; - - if (name) - for (ALL_LIST_ELEMENTS_RO (vrf_list, node, vrfp)) - { - if (strcmp(name, vrfp->name) == 0) - return vrfp; - } - return NULL; + struct vrf vrf; + strlcpy (vrf.name, name, sizeof (vrf.name)); + return (RB_FIND (vrf_name_head, &vrfs_by_name, &vrf)); } static __inline int @@ -84,6 +77,12 @@ vrf_id_compare (struct vrf *a, struct vrf *b) return (a->vrf_id - b->vrf_id); } +static int +vrf_name_compare (struct vrf *a, struct vrf *b) +{ + return strcmp (a->name, b->name); +} + /* Get a VRF. If not found, create one. * Arg: * name - The name of the vrf. May be NULL if unknown. @@ -123,7 +122,7 @@ vrf_get (vrf_id_t vrf_id, const char *name) vrf_id, (name) ? name : "(NULL)"); strcpy (vrf->name, name); vrf->vrf_id = VRF_UNKNOWN; - listnode_add_sort (vrf_list, vrf); + RB_INSERT (vrf_name_head, &vrfs_by_name, vrf); if_init (&vrf->iflist); QOBJ_REG (vrf, vrf); if (vrf_master.vrf_new_hook) @@ -180,7 +179,7 @@ vrf_get (vrf_id_t vrf_id, const char *name) * so let's set it. */ strcpy (vrf->name, name); - listnode_add_sort (vrf_list, vrf); + RB_INSERT (vrf_name_head, &vrfs_by_name, vrf); if (vrf_master.vrf_new_hook) { (*vrf_master.vrf_new_hook) (vrf_id, name, &vrf->info); @@ -197,7 +196,7 @@ vrf_get (vrf_id_t vrf_id, const char *name) vrf = XCALLOC (MTYPE_VRF, sizeof (struct vrf)); vrf->vrf_id = vrf_id; strcpy (vrf->name, name); - listnode_add_sort (vrf_list, vrf); + RB_INSERT (vrf_name_head, &vrfs_by_name, vrf); RB_INSERT (vrf_id_head, &vrfs_by_id, vrf); if_init (&vrf->iflist); QOBJ_REG (vrf, vrf); @@ -265,7 +264,7 @@ vrf_delete (struct vrf *vrf) if (vrf->vrf_id != VRF_UNKNOWN) RB_REMOVE (vrf_id_head, &vrfs_by_id, vrf); - listnode_delete (vrf_list, vrf); + RB_REMOVE (vrf_name_head, &vrfs_by_name, vrf); XFREE (MTYPE_VRF, vrf); } @@ -536,20 +535,6 @@ vrf_bitmap_check (vrf_bitmap_t bmap, vrf_id_t vrf_id) VRF_BITMAP_FLAG (offset)) ? 1 : 0; } -/* Compare interface names, returning an integer greater than, equal to, or - * less than 0, (following the strcmp convention), according to the - * relationship between vrfp1 and vrfp2. Interface names consist of an - * alphabetic prefix and a numeric suffix. The primary sort key is - * lexicographic by name, and then numeric by number. No number sorts - * before all numbers. Examples: de0 < de1, de100 < fxp0 < xl0, devpty < - * devpty0, de0 < del0 - */ -static int -vrf_cmp_func (struct vrf *vrfp1, struct vrf *vrfp2) -{ - return if_cmp_name_func (vrfp1->name, vrfp2->name); -} - /* Initialize VRF module. */ void vrf_init (void) @@ -559,9 +544,6 @@ vrf_init (void) if (debug_vrf) zlog_debug ("%s: Initializing VRF subsystem", __PRETTY_FUNCTION__); - vrf_list = list_new (); - vrf_list->cmp = (int (*)(void *, void *))vrf_cmp_func; - /* The default VRF always exists. */ default_vrf = vrf_get (VRF_DEFAULT, VRF_DEFAULT_NAME); if (!default_vrf) diff --git a/lib/vrf.h b/lib/vrf.h index 4ee871b33..9dfaae21f 100644 --- a/lib/vrf.h +++ b/lib/vrf.h @@ -70,7 +70,7 @@ enum { struct vrf { - RB_ENTRY(vrf) id_entry; + RB_ENTRY(vrf) id_entry, name_entry; /* Identifier, same as the vector index */ vrf_id_t vrf_id; @@ -92,11 +92,13 @@ struct vrf }; RB_HEAD (vrf_id_head, vrf); RB_PROTOTYPE (vrf_id_head, vrf, id_entry, vrf_id_compare) +RB_HEAD (vrf_name_head, vrf); +RB_PROTOTYPE (vrf_name_head, vrf, name_entry, vrf_name_compare) DECLARE_QOBJ_TYPE(vrf) extern struct vrf_id_head vrfs_by_id; -extern struct list *vrf_list; +extern struct vrf_name_head vrfs_by_name; /* * Add a specific hook to VRF module. diff --git a/zebra/zebra_vrf.c b/zebra/zebra_vrf.c index fbb41eb5a..e28f97d76 100644 --- a/zebra/zebra_vrf.c +++ b/zebra/zebra_vrf.c @@ -446,11 +446,10 @@ DEFUN_NOSH (zebra_vrf, static int vrf_config_write (struct vty *vty) { - struct listnode *node; struct vrf *vrf; struct zebra_vrf *zvrf; - for (ALL_LIST_ELEMENTS_RO (vrf_list, node, vrf)) + RB_FOREACH (vrf, vrf_name_head, &vrfs_by_name) { zvrf = vrf->info; if (! zvrf || strcmp (zvrf->name, VRF_DEFAULT_NAME)) diff --git a/zebra/zebra_vty.c b/zebra/zebra_vty.c index 444d25135..3aa7ada91 100644 --- a/zebra/zebra_vty.c +++ b/zebra/zebra_vty.c @@ -3677,9 +3677,8 @@ static_config_ipv4 (struct vty *vty, safi_t safi, const char *cmd) struct zebra_vrf *zvrf; char buf[BUFSIZ]; int write =0; - struct listnode *node; - for (ALL_LIST_ELEMENTS_RO (vrf_list, node, vrf)) + RB_FOREACH (vrf, vrf_name_head, &vrfs_by_name) { zvrf = vrf->info; if (! zvrf) @@ -5789,9 +5788,8 @@ static_config_ipv6 (struct vty *vty) struct route_table *stable; struct vrf *vrf; struct zebra_vrf *zvrf; - struct listnode *node; - for (ALL_LIST_ELEMENTS_RO (vrf_list, node, vrf)) + RB_FOREACH (vrf, vrf_name_head, &vrfs_by_name) { zvrf = vrf->info; if (! zvrf) @@ -5886,9 +5884,8 @@ DEFUN (show_vrf, { struct vrf *vrf; struct zebra_vrf *zvrf; - struct listnode *node; - for (ALL_LIST_ELEMENTS_RO (vrf_list, node, vrf)) + RB_FOREACH (vrf, vrf_name_head, &vrfs_by_name) { zvrf = vrf->info; if (! zvrf || ! zvrf->vrf_id) -- 2.39.5