From ff880b78ef2d480b381d29487812279d57c0bbac Mon Sep 17 00:00:00 2001 From: Renato Westphal Date: Mon, 2 Oct 2017 22:06:04 -0300 Subject: *: introduce new rb-tree to optimize interface lookup by ifindex Performance tests showed that, when running on a system with a large number of interfaces, some daemons would spend a considerable amount of time in the if_lookup_by_index() function. Introduce a new rb-tree to solve this problem. With this change, we need to use the if_set_index() function whenever we want to change the ifindex of an interface. This is necessary to ensure that the 'ifaces_by_index' rb-tree is updated accordingly. The return value of all insert/remove operations in the interface rb-trees is checked to ensure that an error is logged if a corruption is detected. Signed-off-by: Renato Westphal --- babeld/babel_interface.c | 2 +- bgpd/bgp_zebra.c | 2 +- eigrpd/eigrp_zebra.c | 1 + isisd/isis_zebra.c | 2 +- ldpd/ldp_zebra.c | 2 +- lib/if.c | 60 +++++++++++++++++++++++++++++++++--------------- lib/if.h | 40 ++++++++++++++++++++++++++++++-- lib/vrf.c | 1 + lib/vrf.h | 1 + lib/zclient.c | 2 +- nhrpd/nhrp_interface.c | 2 +- ospf6d/ospf6_zebra.c | 2 +- ospfd/ospf_zebra.c | 2 +- ripd/rip_interface.c | 2 +- ripngd/ripng_interface.c | 2 +- zebra/if_ioctl.c | 2 +- zebra/if_ioctl_solaris.c | 4 ++-- zebra/if_netlink.c | 2 +- zebra/interface.c | 2 +- zebra/kernel_socket.c | 4 ++-- 20 files changed, 99 insertions(+), 38 deletions(-) diff --git a/babeld/babel_interface.c b/babeld/babel_interface.c index 49c848d49..5bc48e8a2 100644 --- a/babeld/babel_interface.c +++ b/babeld/babel_interface.c @@ -138,7 +138,7 @@ babel_interface_delete (int cmd, struct zclient *client, zebra_size_t length, vr /* To support pseudo interface do not free interface structure. */ /* if_delete(ifp); */ - ifp->ifindex = IFINDEX_INTERNAL; + if_set_index(ifp, IFINDEX_INTERNAL); return 0; } diff --git a/bgpd/bgp_zebra.c b/bgpd/bgp_zebra.c index ae8f2f26d..aff88694e 100644 --- a/bgpd/bgp_zebra.c +++ b/bgpd/bgp_zebra.c @@ -238,7 +238,7 @@ static int bgp_interface_delete(int command, struct zclient *zclient, bgp_update_interface_nbrs(bgp, ifp, NULL); - ifp->ifindex = IFINDEX_INTERNAL; + if_set_index(ifp, IFINDEX_INTERNAL); return 0; } diff --git a/eigrpd/eigrp_zebra.c b/eigrpd/eigrp_zebra.c index b70c55104..28d2f2981 100644 --- a/eigrpd/eigrp_zebra.c +++ b/eigrpd/eigrp_zebra.c @@ -192,6 +192,7 @@ static int eigrp_interface_delete(int command, struct zclient *zclient, eigrp_if_free(ifp->info, INTERFACE_DOWN_BY_ZEBRA); + if_set_index(ifp, IFINDEX_INTERNAL); return 0; } diff --git a/isisd/isis_zebra.c b/isisd/isis_zebra.c index 7109bfb11..387f99938 100644 --- a/isisd/isis_zebra.c +++ b/isisd/isis_zebra.c @@ -128,7 +128,7 @@ static int isis_zebra_if_del(int command, struct zclient *zclient, in case there is configuration info attached to it. */ if_delete_retain(ifp); - ifp->ifindex = IFINDEX_INTERNAL; + if_set_index(ifp, IFINDEX_INTERNAL); return 0; } diff --git a/ldpd/ldp_zebra.c b/ldpd/ldp_zebra.c index 4b3f5b0f9..f6dfe96dc 100644 --- a/ldpd/ldp_zebra.c +++ b/ldpd/ldp_zebra.c @@ -288,7 +288,7 @@ ldp_interface_delete(int command, struct zclient *zclient, zebra_size_t length, /* To support pseudo interface do not free interface structure. */ /* if_delete(ifp); */ - ifp->ifindex = IFINDEX_INTERNAL; + if_set_index(ifp, IFINDEX_INTERNAL); ifp2kif(ifp, &kif); main_imsg_compose_both(IMSG_IFSTATUS, &kif, sizeof(kif)); diff --git a/lib/if.c b/lib/if.c index c40daf7ef..612cc2081 100644 --- a/lib/if.c +++ b/lib/if.c @@ -41,7 +41,10 @@ DEFINE_MTYPE(LIB, CONNECTED_LABEL, "Connected interface label") DEFINE_MTYPE_STATIC(LIB, IF_LINK_PARAMS, "Informational Link Parameters") static int if_cmp_func(const struct interface *, const struct interface *); +static int if_cmp_index_func(const struct interface *ifp1, + const struct interface *ifp2); RB_GENERATE(if_name_head, interface, name_entry, if_cmp_func); +RB_GENERATE(if_index_head, interface, index_entry, if_cmp_index_func); DEFINE_QOBJ_TYPE(interface) @@ -118,6 +121,12 @@ static int if_cmp_func(const struct interface *ifp1, return if_cmp_name_func((char *)ifp1->name, (char *)ifp2->name); } +static int if_cmp_index_func(const struct interface *ifp1, + const struct interface *ifp2) +{ + return ifp1->ifindex - ifp2->ifindex; +} + /* Create new interface structure. */ struct interface *if_create(const char *name, vrf_id_t vrf_id) { @@ -130,11 +139,7 @@ struct interface *if_create(const char *name, vrf_id_t vrf_id) assert(name); strlcpy(ifp->name, name, sizeof(ifp->name)); ifp->vrf_id = vrf_id; - if (RB_INSERT(if_name_head, &vrf->ifaces_by_name, ifp)) - zlog_err( - "if_create(%s): corruption detected -- interface with this " - "name exists already in VRF %u!", - ifp->name, vrf_id); + IFNAME_RB_INSERT(vrf, ifp); ifp->connected = list_new(); ifp->connected->del = (void (*)(void *))connected_free; @@ -156,16 +161,18 @@ void if_update_to_new_vrf(struct interface *ifp, vrf_id_t vrf_id) /* remove interface from old master vrf list */ vrf = vrf_lookup_by_id(ifp->vrf_id); - if (vrf) - RB_REMOVE(if_name_head, &vrf->ifaces_by_name, ifp); + if (vrf) { + IFNAME_RB_REMOVE(vrf, ifp); + if (ifp->ifindex != IFINDEX_INTERNAL) + IFINDEX_RB_REMOVE(vrf, ifp); + } ifp->vrf_id = vrf_id; vrf = vrf_get(ifp->vrf_id, NULL); - if (RB_INSERT(if_name_head, &vrf->ifaces_by_name, ifp)) - zlog_err( - "%s(%s): corruption detected -- interface with this " - "name exists already in VRF %u!", - __func__, ifp->name, vrf_id); + + IFNAME_RB_INSERT(vrf, ifp); + if (ifp->ifindex != IFINDEX_INTERNAL) + IFINDEX_RB_INSERT(vrf, ifp); } @@ -187,7 +194,9 @@ void if_delete(struct interface *ifp) { struct vrf *vrf = vrf_lookup_by_id(ifp->vrf_id); - RB_REMOVE(if_name_head, &vrf->ifaces_by_name, ifp); + IFNAME_RB_REMOVE(vrf, ifp); + if (ifp->ifindex != IFINDEX_INTERNAL) + IFINDEX_RB_REMOVE(vrf, ifp); if_delete_retain(ifp); @@ -203,13 +212,10 @@ void if_delete(struct interface *ifp) struct interface *if_lookup_by_index(ifindex_t ifindex, vrf_id_t vrf_id) { struct vrf *vrf = vrf_lookup_by_id(vrf_id); - struct interface *ifp; - - RB_FOREACH (ifp, if_name_head, &vrf->ifaces_by_name) - if (ifp->ifindex == ifindex) - return ifp; + struct interface if_tmp; - return NULL; + if_tmp.ifindex = ifindex; + return RB_FIND(if_index_head, &vrf->ifaces_by_index, &if_tmp); } const char *ifindex2ifname(ifindex_t ifindex, vrf_id_t vrf_id) @@ -378,6 +384,22 @@ struct interface *if_get_by_name(const char *name, vrf_id_t vrf_id, int vty) return if_create(name, vrf_id); } +void if_set_index(struct interface *ifp, ifindex_t ifindex) +{ + struct vrf *vrf = vrf_lookup_by_id(ifp->vrf_id); + + if (ifp->ifindex == ifindex) + return; + + if (ifp->ifindex != IFINDEX_INTERNAL) + IFINDEX_RB_REMOVE(vrf, ifp) + + ifp->ifindex = ifindex; + + if (ifp->ifindex != IFINDEX_INTERNAL) + IFINDEX_RB_INSERT(vrf, ifp) +} + /* Does interface up ? */ int if_is_up(struct interface *ifp) { diff --git a/lib/if.h b/lib/if.h index d4ae8fc42..3e2824b6c 100644 --- a/lib/if.h +++ b/lib/if.h @@ -201,7 +201,7 @@ struct if_link_params { /* Interface structure */ struct interface { - RB_ENTRY(interface) name_entry; + RB_ENTRY(interface) name_entry, index_entry; /* Interface name. This should probably never be changed after the interface is created, because the configuration info for this @@ -214,7 +214,12 @@ struct interface { char name[INTERFACE_NAMSIZ]; /* Interface index (should be IFINDEX_INTERNAL for non-kernel or - deleted interfaces). */ + deleted interfaces). + WARNING: the ifindex needs to be changed using the if_set_index() + function. Failure to respect this will cause corruption in the data + structure used to store the interfaces and if_lookup_by_index() will + not work as expected. + */ ifindex_t ifindex; #define IFINDEX_INTERNAL 0 @@ -285,8 +290,38 @@ struct interface { }; RB_HEAD(if_name_head, interface); RB_PROTOTYPE(if_name_head, interface, name_entry, if_cmp_func); +RB_HEAD(if_index_head, interface); +RB_PROTOTYPE(if_index_head, interface, index_entry, if_cmp_func); DECLARE_QOBJ_TYPE(interface) +#define IFNAME_RB_INSERT(vrf, ifp) \ + if (RB_INSERT(if_name_head, &vrf->ifaces_by_name, (ifp))) \ + zlog_err( \ + "%s(%s): corruption detected -- interface with this " \ + "name exists already in VRF %u!", \ + __func__, (ifp)->name, (ifp)->vrf_id); + +#define IFNAME_RB_REMOVE(vrf, ifp) \ + if (RB_REMOVE(if_name_head, &vrf->ifaces_by_name, (ifp)) == NULL) \ + zlog_err( \ + "%s(%s): corruption detected -- interface with this " \ + "name doesn't exist in VRF %u!", \ + __func__, (ifp)->name, (ifp)->vrf_id); + +#define IFINDEX_RB_INSERT(vrf, ifp) \ + if (RB_INSERT(if_index_head, &vrf->ifaces_by_index, (ifp))) \ + zlog_err( \ + "%s(%u): corruption detected -- interface with this " \ + "ifindex exists already in VRF %u!", \ + __func__, (ifp)->ifindex, (ifp)->vrf_id); + +#define IFINDEX_RB_REMOVE(vrf, ifp) \ + if (RB_REMOVE(if_index_head, &vrf->ifaces_by_index, (ifp)) == NULL) \ + zlog_err( \ + "%s(%u): corruption detected -- interface with this " \ + "ifindex doesn't exist in VRF %u!", \ + __func__, (ifp)->ifindex, (ifp)->vrf_id); + /* called from the library code whenever interfaces are created/deleted * note: interfaces may not be fully realized at that point; also they * may not exist in the system (ifindex = IFINDEX_INTERNAL) @@ -426,6 +461,7 @@ extern struct interface *if_lookup_by_name_all_vrf(const char *ifname); extern struct interface *if_lookup_by_name(const char *ifname, vrf_id_t vrf_id); extern struct interface *if_get_by_name(const char *ifname, vrf_id_t vrf_id, int vty); +extern void if_set_index(struct interface *ifp, ifindex_t ifindex); /* Delete the interface, but do not free the structure, and leave it in the interface list. It is often advisable to leave the pseudo interface diff --git a/lib/vrf.c b/lib/vrf.c index e303e0e1c..056f778a3 100644 --- a/lib/vrf.c +++ b/lib/vrf.c @@ -110,6 +110,7 @@ struct vrf *vrf_get(vrf_id_t vrf_id, const char *name) vrf = XCALLOC(MTYPE_VRF, sizeof(struct vrf)); vrf->vrf_id = VRF_UNKNOWN; RB_INIT(if_name_head, &vrf->ifaces_by_name); + RB_INIT(if_index_head, &vrf->ifaces_by_index); QOBJ_REG(vrf, vrf); new = 1; diff --git a/lib/vrf.h b/lib/vrf.h index 5309100bd..8bfdc8768 100644 --- a/lib/vrf.h +++ b/lib/vrf.h @@ -79,6 +79,7 @@ struct vrf { /* Interfaces belonging to this VRF */ struct if_name_head ifaces_by_name; + struct if_index_head ifaces_by_index; /* User data */ void *info; diff --git a/lib/zclient.c b/lib/zclient.c index 1fc88ee6a..ad5c30584 100644 --- a/lib/zclient.c +++ b/lib/zclient.c @@ -1331,7 +1331,7 @@ void zebra_interface_if_set_value(struct stream *s, struct interface *ifp) u_char link_params_status = 0; /* Read interface's index. */ - ifp->ifindex = stream_getl(s); + if_set_index(ifp, stream_getl(s)); ifp->status = stream_getc(s); /* Read interface's value. */ diff --git a/nhrpd/nhrp_interface.c b/nhrpd/nhrp_interface.c index a46962c91..67e3f41b3 100644 --- a/nhrpd/nhrp_interface.c +++ b/nhrpd/nhrp_interface.c @@ -299,7 +299,7 @@ int nhrp_interface_delete(int cmd, struct zclient *client, return 0; debugf(NHRP_DEBUG_IF, "if-delete: %s", ifp->name); - ifp->ifindex = IFINDEX_INTERNAL; + if_set_index(ifp, ifp->ifindex); nhrp_interface_update(ifp); /* if_delete(ifp); */ return 0; diff --git a/ospf6d/ospf6_zebra.c b/ospf6d/ospf6_zebra.c index 14dc6aa30..b032bd7a7 100644 --- a/ospf6d/ospf6_zebra.c +++ b/ospf6d/ospf6_zebra.c @@ -126,7 +126,7 @@ static int ospf6_zebra_if_del(int command, struct zclient *zclient, ospf6_interface_if_del (ifp); #endif /*0*/ - ifp->ifindex = IFINDEX_INTERNAL; + if_set_index(ifp, IFINDEX_INTERNAL); return 0; } diff --git a/ospfd/ospf_zebra.c b/ospfd/ospf_zebra.c index a171e5f04..3f94e6b4e 100644 --- a/ospfd/ospf_zebra.c +++ b/ospfd/ospf_zebra.c @@ -166,7 +166,7 @@ static int ospf_interface_delete(int command, struct zclient *zclient, if (rn->info) ospf_if_free((struct ospf_interface *)rn->info); - ifp->ifindex = IFINDEX_INTERNAL; + if_set_index(ifp, IFINDEX_INTERNAL); return 0; } diff --git a/ripd/rip_interface.c b/ripd/rip_interface.c index 6fba0512e..21950c9f2 100644 --- a/ripd/rip_interface.c +++ b/ripd/rip_interface.c @@ -471,7 +471,7 @@ int rip_interface_delete(int command, struct zclient *zclient, /* To support pseudo interface do not free interface structure. */ /* if_delete(ifp); */ - ifp->ifindex = IFINDEX_INTERNAL; + if_set_index(ifp, IFINDEX_INTERNAL); return 0; } diff --git a/ripngd/ripng_interface.c b/ripngd/ripng_interface.c index dbee3ce69..7203c906e 100644 --- a/ripngd/ripng_interface.c +++ b/ripngd/ripng_interface.c @@ -299,7 +299,7 @@ int ripng_interface_delete(int command, struct zclient *zclient, /* To support pseudo interface do not free interface structure. */ /* if_delete(ifp); */ - ifp->ifindex = IFINDEX_INTERNAL; + if_set_index(ifp, IFINDEX_INTERNAL); return 0; } diff --git a/zebra/if_ioctl.c b/zebra/if_ioctl.c index 54dbb555d..33e53551b 100644 --- a/zebra/if_ioctl.c +++ b/zebra/if_ioctl.c @@ -131,7 +131,7 @@ end: /* Get interface's index by ioctl. */ static int if_get_index(struct interface *ifp) { - ifp->ifindex = if_nametoindex(ifp->name); + if_set_index(ifp, if_nametoindex(ifp->name)); return ifp->ifindex; } diff --git a/zebra/if_ioctl_solaris.c b/zebra/if_ioctl_solaris.c index 145dc0ac5..94738664b 100644 --- a/zebra/if_ioctl_solaris.c +++ b/zebra/if_ioctl_solaris.c @@ -227,9 +227,9 @@ static int if_get_index(struct interface *ifp) /* OK we got interface index. */ #ifdef ifr_ifindex - ifp->ifindex = lifreq.lifr_ifindex; + if_set_index(ifp, lifreq.lifr_ifindex); #else - ifp->ifindex = lifreq.lifr_index; + if_set_index(ifp, lifreq.lifr_index); #endif return ifp->ifindex; } diff --git a/zebra/if_netlink.c b/zebra/if_netlink.c index 0b97903ce..a2235904c 100644 --- a/zebra/if_netlink.c +++ b/zebra/if_netlink.c @@ -93,7 +93,7 @@ static void set_ifindex(struct interface *ifp, ifindex_t ifi_index, if_delete_update(oifp); } } - ifp->ifindex = ifi_index; + if_set_index(ifp, ifi_index); } /* Utility function to parse hardware link-layer address and update ifp */ diff --git a/zebra/interface.c b/zebra/interface.c index 1b11357a8..fe7241964 100644 --- a/zebra/interface.c +++ b/zebra/interface.c @@ -685,7 +685,7 @@ void if_delete_update(struct interface *ifp) while processing the deletion. Each client daemon is responsible for setting ifindex to IFINDEX_INTERNAL after processing the interface deletion message. */ - ifp->ifindex = IFINDEX_INTERNAL; + if_set_index(ifp, IFINDEX_INTERNAL); ifp->node = NULL; /* if the ifp is in a vrf, move it to default so vrf can be deleted if diff --git a/zebra/kernel_socket.c b/zebra/kernel_socket.c index cbfc37119..89c933f90 100644 --- a/zebra/kernel_socket.c +++ b/zebra/kernel_socket.c @@ -324,7 +324,7 @@ static int ifan_read(struct if_announcemsghdr *ifan) /* Create Interface */ ifp = if_get_by_name(ifan->ifan_name, VRF_DEFAULT, 0); - ifp->ifindex = ifan->ifan_index; + if_set_index(ifp, ifan->ifan_index); if_get_metric(ifp); if_add_update(ifp); @@ -528,7 +528,7 @@ int ifm_read(struct if_msghdr *ifm) * Fill in newly created interface structure, or larval * structure with ifindex IFINDEX_INTERNAL. */ - ifp->ifindex = ifm->ifm_index; + if_set_index(ifp, ifm->ifm_index); #ifdef HAVE_BSD_IFI_LINK_STATE /* translate BSD kernel msg for link-state */ bsd_linkdetect_translate(ifm); -- cgit v1.2.3