From f2a503f0cece16dd66e7c258a3bccd967533d074 Mon Sep 17 00:00:00 2001 From: Donald Sharp Date: Thu, 17 May 2018 08:18:23 -0400 Subject: [PATCH] zebra: The neigh host_list is expensive too The neighbor host_list is expensive as well. Modify the code to take advantage of a rb_tree as well. Signed-off-by: Donald Sharp --- zebra/zebra_vxlan.c | 75 ++++++++++--------------------------- zebra/zebra_vxlan_private.h | 2 +- 2 files changed, 21 insertions(+), 56 deletions(-) diff --git a/zebra/zebra_vxlan.c b/zebra/zebra_vxlan.c index 30811e4252..6b8f915f67 100644 --- a/zebra/zebra_vxlan.c +++ b/zebra/zebra_vxlan.c @@ -476,20 +476,20 @@ static void zl3vni_print_nh(zebra_neigh_t *n, struct vty *vty, { char buf1[ETHER_ADDR_STRLEN]; char buf2[INET6_ADDRSTRLEN]; - struct listnode *node = NULL; - struct prefix *p = NULL; json_object *json_hosts = NULL; + struct host_rb_entry *hle; if (!json) { vty_out(vty, "Ip: %s\n", ipaddr2str(&n->ip, buf2, sizeof(buf2))); vty_out(vty, " RMAC: %s\n", prefix_mac2str(&n->emac, buf1, sizeof(buf1))); - vty_out(vty, " Refcount: %d\n", listcount(n->host_list)); + vty_out(vty, " Refcount: %d\n", + rb_host_count(&n->host_rb)); vty_out(vty, " Prefixes:\n"); - for (ALL_LIST_ELEMENTS_RO(n->host_list, node, p)) + RB_FOREACH (hle, host_rb_entry_rb, &n->host_rb) vty_out(vty, " %s\n", - prefix2str(p, buf2, sizeof(buf2))); + prefix2str(&hle->p, buf2, sizeof(buf2))); } else { json_hosts = json_object_new_array(); json_object_string_add( @@ -497,11 +497,12 @@ static void zl3vni_print_nh(zebra_neigh_t *n, struct vty *vty, json_object_string_add( json, "routerMac", prefix_mac2str(&n->emac, buf2, sizeof(buf2))); - json_object_int_add(json, "refCount", listcount(n->host_list)); - for (ALL_LIST_ELEMENTS_RO(n->host_list, node, p)) + json_object_int_add(json, "refCount", + rb_host_count(&n->host_rb)); + RB_FOREACH (hle, host_rb_entry_rb, &n->host_rb) json_object_array_add(json_hosts, json_object_new_string(prefix2str( - p, buf2, sizeof(buf2)))); + &hle->p, buf2, sizeof(buf2)))); json_object_object_add(json, "prefixList", json_hosts); } } @@ -3117,44 +3118,6 @@ static void rb_delete_host(struct host_rb_entry_rb *hrbe, struct prefix *host) return; } -static int is_host_present_in_host_list(struct list *list, struct prefix *host) -{ - struct listnode *node = NULL; - struct prefix *p = NULL; - - for (ALL_LIST_ELEMENTS_RO(list, node, p)) { - if (prefix_same(p, host)) - return 1; - } - return 0; -} - -static void host_list_add_host(struct list *list, struct prefix *host) -{ - struct prefix *p = NULL; - - p = XCALLOC(MTYPE_HOST_PREFIX, sizeof(struct prefix)); - memcpy(p, host, sizeof(struct prefix)); - - listnode_add_sort(list, p); -} - -static void host_list_delete_host(struct list *list, struct prefix *host) -{ - struct listnode *node = NULL, *nnode = NULL, *node_to_del = NULL; - struct prefix *p = NULL; - - for (ALL_LIST_ELEMENTS(list, node, nnode, p)) { - if (prefix_same(p, host)) { - XFREE(MTYPE_HOST_PREFIX, p); - node_to_del = node; - } - } - - if (node_to_del) - list_delete_node(list, node_to_del); -} - /* * Look up MAC hash entry. */ @@ -3374,8 +3337,7 @@ static zebra_neigh_t *zl3vni_nh_add(zebra_l3vni_t *zl3vni, struct ipaddr *ip, n = hash_get(zl3vni->nh_table, &tmp_n, zl3vni_nh_alloc); assert(n); - n->host_list = list_new(); - n->host_list->cmp = (int (*)(void *, void *))prefix_cmp; + RB_INIT(host_rb_entry_rb, &n->host_rb); memcpy(&n->emac, mac, ETH_ALEN); SET_FLAG(n->flags, ZEBRA_NEIGH_REMOTE); @@ -3390,10 +3352,14 @@ static zebra_neigh_t *zl3vni_nh_add(zebra_l3vni_t *zl3vni, struct ipaddr *ip, static int zl3vni_nh_del(zebra_l3vni_t *zl3vni, zebra_neigh_t *n) { zebra_neigh_t *tmp_n; + struct host_rb_entry *hle; - if (n->host_list) - list_delete_and_null(&n->host_list); - n->host_list = NULL; + while (!RB_EMPTY(host_rb_entry_rb, &n->host_rb)) { + hle = RB_ROOT(host_rb_entry_rb, &n->host_rb); + + RB_REMOVE(host_rb_entry_rb, &n->host_rb, hle); + XFREE(MTYPE_HOST_PREFIX, hle); + } tmp_n = hash_release(zl3vni->nh_table, n); if (tmp_n) @@ -3458,8 +3424,7 @@ static int zl3vni_remote_nh_add(zebra_l3vni_t *zl3vni, struct ipaddr *vtep_ip, zl3vni_nh_install(zl3vni, nh); } - if (!is_host_present_in_host_list(nh->host_list, host_prefix)) - host_list_add_host(nh->host_list, host_prefix); + rb_find_or_add_host(&nh->host_rb, host_prefix); return 0; } @@ -3468,9 +3433,9 @@ static int zl3vni_remote_nh_add(zebra_l3vni_t *zl3vni, struct ipaddr *vtep_ip, static void zl3vni_remote_nh_del(zebra_l3vni_t *zl3vni, zebra_neigh_t *nh, struct prefix *host_prefix) { - host_list_delete_host(nh->host_list, host_prefix); - if (list_isempty(nh->host_list)) { + rb_delete_host(&nh->host_rb, host_prefix); + if (RB_EMPTY(host_rb_entry_rb, &nh->host_rb)) { /* uninstall from kernel */ zl3vni_nh_uninstall(zl3vni, nh); diff --git a/zebra/zebra_vxlan_private.h b/zebra/zebra_vxlan_private.h index c5f6b783aa..b2bfcecfc5 100644 --- a/zebra/zebra_vxlan_private.h +++ b/zebra/zebra_vxlan_private.h @@ -336,7 +336,7 @@ struct zebra_neigh_t_ { struct in_addr r_vtep_ip; /* list of hosts pointing to this remote NH entry */ - struct list *host_list; + struct host_rb_entry_rb host_rb; }; /* -- 2.39.5