From 9f25dd8af76dc30e54ddcbb4a284058e598951d5 Mon Sep 17 00:00:00 2001 From: Hans Dedecker Date: Tue, 5 Feb 2019 12:09:44 +0100 Subject: [PATCH] treewide: use avl tree to store interfaces Store the interfaces in an avl tree iso a linear linked list Signed-off-by: Hans Dedecker --- CMakeLists.txt | 2 +- src/config.c | 43 ++++++++++++++++--------------------------- src/dhcpv4.c | 5 +++-- src/dhcpv6-ia.c | 10 ++++++---- src/ndp.c | 7 ++++--- src/odhcpd.c | 15 +++++++++++---- src/odhcpd.h | 5 +++-- src/router.c | 12 +++++------- src/ubus.c | 33 ++++++++++++++++----------------- 9 files changed, 65 insertions(+), 67 deletions(-) diff --git a/CMakeLists.txt b/CMakeLists.txt index 380d633..46cf4c4 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -5,7 +5,7 @@ cmake_policy(SET CMP0015 NEW) project(odhcpd C) set(CMAKE_SHARED_LIBRARY_LINK_C_FLAGS "") -set(CMAKE_C_FLAGS "${CMAKE_C_FLAGS} -g -std=c99") +set(CMAKE_C_FLAGS "${CMAKE_C_FLAGS} -g -std=gnu99") FIND_PATH(ubox_include_dir libubox/uloop.h) FIND_PATH(libnl-tiny_include_dir netlink-generic.h PATH_SUFFIXES libnl-tiny) diff --git a/src/config.c b/src/config.c index 68aacd8..f4a0dcf 100644 --- a/src/config.c +++ b/src/config.c @@ -12,13 +12,15 @@ #include #include #include +#include +#include #include "odhcpd.h" static struct blob_buf b; static int reload_pipe[2]; struct list_head leases = LIST_HEAD_INIT(leases); -struct list_head interfaces = LIST_HEAD_INIT(interfaces); +AVL_TREE(interfaces, avl_strcmp, false, NULL); struct config config = {.legacy = false, .main_dhcpv4 = false, .dhcp_cb = NULL, .dhcp_statefile = NULL, .log_level = LOG_INFO}; @@ -206,15 +208,6 @@ static void free_lease(struct lease *l) free(l); } -static struct interface* get_interface(const char *name) -{ - struct interface *c; - list_for_each_entry(c, &interfaces, head) - if (!strcmp(c->name, name)) - return c; - return NULL; -} - static void set_interface_defaults(struct interface *iface) { iface->learn_routes = 1; @@ -244,8 +237,7 @@ static void clean_interface(struct interface *iface) static void close_interface(struct interface *iface) { - if (iface->head.next) - list_del(&iface->head); + avl_delete(&interfaces, &iface->avl); router_setup_interface(iface, false); dhcpv6_setup_interface(iface, false); @@ -409,6 +401,7 @@ err: int config_parse_interface(void *data, size_t len, const char *name, bool overwrite) { + struct interface *iface; struct blob_attr *tb[IFACE_ATTR_MAX], *c; bool get_addrs = false; @@ -420,19 +413,19 @@ int config_parse_interface(void *data, size_t len, const char *name, bool overwr if (!name) return -1; - struct interface *iface = get_interface(name); + iface = avl_find_element(&interfaces, name, iface, avl); if (!iface) { - char *iface_name; + char *new_name; - iface = calloc_a(sizeof(*iface), &iface_name, strlen(name) + 1); + iface = calloc_a(sizeof(*iface), &new_name, strlen(name) + 1); if (!iface) return -1; - iface->name = strcpy(iface_name, name); - + iface->name = strcpy(new_name, name); + iface->avl.key = iface->name; set_interface_defaults(iface); - list_add(&iface->head, &interfaces); + avl_insert(&interfaces, &iface->avl); get_addrs = overwrite = true; } @@ -785,16 +778,15 @@ static int set_interface(struct uci_section *s) void odhcpd_reload(void) { struct uci_context *uci = uci_alloc_context(); + struct interface *master = NULL, *i, *tmp; while (!list_empty(&leases)) free_lease(list_first_entry(&leases, struct lease, head)); - struct interface *master = NULL, *i, *n; - if (!uci) return; - list_for_each_entry(i, &interfaces, head) + avl_for_each_element(&interfaces, i, avl) clean_interface(i); struct uci_package *dhcp = NULL; @@ -829,7 +821,7 @@ void odhcpd_reload(void) bool any_dhcpv6_slave = false, any_ra_slave = false, any_ndp_slave = false; /* Test for */ - list_for_each_entry(i, &interfaces, head) { + avl_for_each_element(&interfaces, i, avl) { if (i->master) continue; @@ -844,7 +836,7 @@ void odhcpd_reload(void) } /* Evaluate hybrid mode for master */ - list_for_each_entry(i, &interfaces, head) { + avl_for_each_element(&interfaces, i, avl) { if (!i->master) continue; @@ -877,7 +869,7 @@ void odhcpd_reload(void) } - list_for_each_entry_safe(i, n, &interfaces, head) { + avl_for_each_element_safe(&interfaces, i, avl, tmp) { if (i->inuse) { /* Resolve hybrid mode */ if (i->dhcpv6 == MODE_HYBRID) @@ -944,8 +936,5 @@ void odhcpd_run(void) odhcpd_reload(); uloop_run(); - - while (!list_empty(&interfaces)) - close_interface(list_first_entry(&interfaces, struct interface, head)); } diff --git a/src/dhcpv4.c b/src/dhcpv4.c index 4a74b8a..e29f490 100644 --- a/src/dhcpv4.c +++ b/src/dhcpv4.c @@ -412,9 +412,10 @@ static bool leases_require_fr(struct interface *iface, struct odhcpd_ipaddr *add static void valid_until_cb(struct uloop_timeout *event) { - time_t now = odhcpd_time(); struct interface *iface; - list_for_each_entry(iface, &interfaces, head) { + time_t now = odhcpd_time(); + + avl_for_each_element(&interfaces, iface, avl) { if (iface->dhcpv4 != MODE_SERVER || iface->dhcpv4_assignments.next == NULL) continue; diff --git a/src/dhcpv6-ia.c b/src/dhcpv6-ia.c index 06e418a..af3b720 100644 --- a/src/dhcpv6-ia.c +++ b/src/dhcpv6-ia.c @@ -379,7 +379,7 @@ void dhcpv6_write_statefile(void) ctxt.buf = leasebuf; ctxt.buf_len = sizeof(leasebuf); - list_for_each_entry(ctxt.iface, &interfaces, head) { + avl_for_each_element(&interfaces, ctxt.iface, avl) { if (ctxt.iface->dhcpv6 != MODE_SERVER && ctxt.iface->dhcpv4 != MODE_SERVER) continue; @@ -805,13 +805,15 @@ static void stop_reconf(struct dhcpv6_assignment *a) static void valid_until_cb(struct uloop_timeout *event) { - time_t now = odhcpd_time(); struct interface *iface; - list_for_each_entry(iface, &interfaces, head) { + time_t now = odhcpd_time(); + + avl_for_each_element(&interfaces, iface, avl) { + struct dhcpv6_assignment *a, *n; + if (iface->dhcpv6 != MODE_SERVER || iface->ia_assignments.next == NULL) continue; - struct dhcpv6_assignment *a, *n; list_for_each_entry_safe(a, n, &iface->ia_assignments, head) { if (!INFINITE_VALID(a->valid_until) && a->valid_until < now) { if ((a->length < 128 && a->clid_len > 0) || diff --git a/src/ndp.c b/src/ndp.c index 8cae97f..c819062 100644 --- a/src/ndp.c +++ b/src/ndp.c @@ -284,6 +284,7 @@ static void handle_solicit(void *addr, void *data, size_t len, struct ip6_hdr *ip6 = data; struct nd_neighbor_solicit *req = (struct nd_neighbor_solicit*)&ip6[1]; struct sockaddr_ll *ll = addr; + struct interface *c; char ipbuf[INET6_ADDRSTRLEN]; uint8_t mac[6]; @@ -311,11 +312,11 @@ static void handle_solicit(void *addr, void *data, size_t len, if (!memcmp(ll->sll_addr, mac, sizeof(mac))) return; /* Looped back */ - struct interface *c; - list_for_each_entry(c, &interfaces, head) + avl_for_each_element(&interfaces, c, avl) { if (iface != c && c->ndp == MODE_RELAY && (ns_is_dad || !c->external)) ping6(&req->nd_ns_target, c); + } } /* Use rtnetlink to modify kernel routes */ @@ -340,7 +341,7 @@ static void setup_addr_for_relaying(struct in6_addr *addr, struct interface *ifa inet_ntop(AF_INET6, addr, ipbuf, sizeof(ipbuf)); - list_for_each_entry(c, &interfaces, head) { + avl_for_each_element(&interfaces, c, avl) { if (iface == c || (c->ndp != MODE_RELAY && !add)) continue; diff --git a/src/odhcpd.c b/src/odhcpd.c index 8a61148..46878f7 100644 --- a/src/odhcpd.c +++ b/src/odhcpd.c @@ -291,9 +291,11 @@ int odhcpd_get_interface_dns_addr(const struct interface *iface, struct in6_addr struct interface* odhcpd_get_interface_by_index(int ifindex) { struct interface *iface; - list_for_each_entry(iface, &interfaces, head) + + avl_for_each_element(&interfaces, iface, avl) { if (iface->ifindex == ifindex) return iface; + } return NULL; } @@ -302,9 +304,11 @@ struct interface* odhcpd_get_interface_by_index(int ifindex) struct interface* odhcpd_get_interface_by_name(const char *name) { struct interface *iface; - list_for_each_entry(iface, &interfaces, head) + + avl_for_each_element(&interfaces, iface, avl) { if (!strcmp(iface->ifname, name)) return iface; + } return NULL; } @@ -313,9 +317,11 @@ struct interface* odhcpd_get_interface_by_name(const char *name) struct interface* odhcpd_get_master_interface(void) { struct interface *iface; - list_for_each_entry(iface, &interfaces, head) + + avl_for_each_element(&interfaces, iface, avl) { if (iface->master) return iface; + } return NULL; } @@ -417,7 +423,8 @@ static void odhcpd_receive_packets(struct uloop_fd *u, _unused unsigned int even return; } else if (destiface != 0) { struct interface *iface; - list_for_each_entry(iface, &interfaces, head) { + + avl_for_each_element(&interfaces, iface, avl) { if (iface->ifindex != destiface) continue; diff --git a/src/odhcpd.h b/src/odhcpd.h index 5157f1f..a1d89e8 100644 --- a/src/odhcpd.h +++ b/src/odhcpd.h @@ -22,6 +22,7 @@ #include #include #include +#include // RFC 6106 defines this router advertisement option #define ND_OPT_ROUTE_INFO 24 @@ -145,7 +146,7 @@ struct lease { struct interface { - struct list_head head; + struct avl_node avl; int ifindex; char *ifname; @@ -245,7 +246,7 @@ struct interface { char *filter_class; }; -extern struct list_head interfaces; +extern struct avl_tree interfaces; #define RA_MANAGED_NO_MFLAG 0 #define RA_MANAGED_MFLAG 1 diff --git a/src/router.c b/src/router.c index a79f09c..a3456a8 100644 --- a/src/router.c +++ b/src/router.c @@ -209,7 +209,7 @@ static void router_netevent_cb(unsigned long event, struct netevent_handler_info if (info->rt.dst_len) break; - list_for_each_entry(iface, &interfaces, head) { + avl_for_each_element(&interfaces, iface, avl) { if (iface->ra == MODE_SERVER && !iface->master) uloop_timeout_set(&iface->timer_rs, 1000); } @@ -736,14 +736,15 @@ static void forward_router_advertisement(const struct interface *iface, uint8_t { struct nd_router_advert *adv = (struct nd_router_advert *)data; struct sockaddr_in6 all_nodes; - + struct icmpv6_opt *opt; + struct interface *c; + struct iovec iov = { .iov_base = data, .iov_len = len }; /* Rewrite options */ uint8_t *end = data + len; uint8_t *mac_ptr = NULL; struct in6_addr *dns_ptr = NULL; size_t dns_count = 0; - struct icmpv6_opt *opt; icmpv6_for_each_option(opt, &adv[1], end) { if (opt->type == ND_OPT_SOURCE_LINKADDR) { /* Store address of source MAC-address */ @@ -765,10 +766,7 @@ static void forward_router_advertisement(const struct interface *iface, uint8_t all_nodes.sin6_family = AF_INET6; inet_pton(AF_INET6, ALL_IPV6_NODES, &all_nodes.sin6_addr); - struct iovec iov = {data, len}; - - struct interface *c; - list_for_each_entry(c, &interfaces, head) { + avl_for_each_element(&interfaces, c, avl) { if (c->ra != MODE_RELAY || c->master) continue; diff --git a/src/ubus.c b/src/ubus.c index 816ca2a..eb6e845 100644 --- a/src/ubus.c +++ b/src/ubus.c @@ -28,7 +28,7 @@ static int handle_dhcpv4_leases(struct ubus_context *ctx, _unused struct ubus_ob blob_buf_init(&b, 0); a = blobmsg_open_table(&b, "device"); - list_for_each_entry(iface, &interfaces, head) { + avl_for_each_element(&interfaces, iface, avl) { if (iface->dhcpv4 != MODE_SERVER || iface->dhcpv4_assignments.next == NULL) continue; @@ -111,7 +111,7 @@ static int handle_dhcpv6_leases(_unused struct ubus_context *ctx, _unused struct blob_buf_init(&b, 0); a = blobmsg_open_table(&b, "device"); - list_for_each_entry(iface, &interfaces, head) { + avl_for_each_element(&interfaces, iface, avl) { if (iface->dhcpv6 != MODE_SERVER || iface->ia_assignments.next == NULL) continue; @@ -244,22 +244,23 @@ static int handle_update(_unused struct ubus_context *ctx, _unused struct ubus_o struct blob_attr *msg) { struct blob_attr *tb[IFACE_ATTR_MAX]; - blobmsg_parse(iface_attrs, IFACE_ATTR_MAX, tb, blob_data(msg), blob_len(msg)); + struct interface *c; + bool update = false; + blobmsg_parse(iface_attrs, IFACE_ATTR_MAX, tb, blob_data(msg), blob_len(msg)); const char *interface = (tb[IFACE_ATTR_INTERFACE]) ? blobmsg_get_string(tb[IFACE_ATTR_INTERFACE]) : ""; - const char *ifname = (tb[IFACE_ATTR_IFNAME]) ? - blobmsg_get_string(tb[IFACE_ATTR_IFNAME]) : ""; - struct interface *c, *iface = NULL; - list_for_each_entry(c, &interfaces, head) - if (!strcmp(interface, c->name) || !strcmp(ifname, c->ifname)) - iface = c; + avl_for_each_element(&interfaces, c, avl) { + if (!strcmp(interface, c->name) && !c->ignore) { + update = true; + break; + } + } - if (iface && iface->ignore) - return 0; + if (update) + update_netifd(false); - update_netifd(false); return 0; } @@ -281,15 +282,13 @@ void ubus_apply_network(void) const char *interface = (tb[IFACE_ATTR_INTERFACE]) ? blobmsg_get_string(tb[IFACE_ATTR_INTERFACE]) : ""; - const char *ifname = (tb[IFACE_ATTR_IFNAME]) ? - blobmsg_get_string(tb[IFACE_ATTR_IFNAME]) : ""; bool matched = false; - struct interface *c, *n; - list_for_each_entry_safe(c, n, &interfaces, head) { + struct interface *c, *tmp; + avl_for_each_element_safe(&interfaces, c, avl, tmp) { char *f = memmem(c->upstream, c->upstream_len, interface, strlen(interface) + 1); - bool cmatched = !strcmp(interface, c->name) || !strcmp(ifname, c->ifname); + bool cmatched = !strcmp(interface, c->name); matched |= cmatched; if (!cmatched && (!c->upstream_len || !f || (f != c->upstream && f[-1] != 0))) -- 2.25.1