treewide: use avl tree to store interfaces

Store the interfaces in an avl tree iso a linear linked list

Signed-off-by: Hans Dedecker <dedeckeh@gmail.com>

diff --git a/CMakeLists.txt b/CMakeLists.txt
index 380d633967715666d5ac2c66f61960aa25c5fcff..46cf4c4579397319dc501d6ed3325d17ef4f65e6 100644 (file)
--- 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 68aacd8557554db26a1557c38cb79bbec0b811bd..f4a0dcfc920d45f853bdc1f780cf0156d99376a3 100644 (file)
--- a/src/config.c
+++ b/src/config.c
@@ -12,13 +12,15 @@
 #include <uci.h>
 #include <uci_blob.h>
 #include <libubox/utils.h>
+#include <libubox/avl.h>
+#include <libubox/avl-cmp.h>
 
 #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 4a74b8a983b300894b179f2cea1b37e4fddeb60e..e29f49063f4c4409e0e9406781d8c3f3530532b3 100644 (file)
--- 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 06e418a5350768f8656918de82fac10c85bf53f4..af3b72031a1eed5c67ea58fbd9ea8a35e09d9789 100644 (file)
--- 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 8cae97ffd56b7c91455bb53b3ebb8fa9ecfa7c71..c819062947f40b33918444671b37813ef73c92f9 100644 (file)
--- 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 8a6114892d5e38018ef3c90c6d736a86a440c291..46878f739132ba179131c602834a2b7f08f1f3e8 100644 (file)
--- 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 5157f1fd3dfacac9578bd217e46b5fc4428a9b55..a1d89e88b12279b4933ecfbd3218872c4f828a29 100644 (file)
--- a/src/odhcpd.h
+++ b/src/odhcpd.h
@@ -22,6 +22,7 @@
 #include <libubox/blobmsg.h>
 #include <libubox/list.h>
 #include <libubox/uloop.h>
+#include <libubox/avl.h>
 
 // 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 a79f09c28bf61e595b8802c0fd3f2bfce4768ec3..a3456a8e1f18406afc291bb87554e4d8e4acf397 100644 (file)
--- 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 816ca2a538c902291b84b044f6eabdd9039d2671..eb6e84513595884304c4d603f372a35cb66be921 100644 (file)
--- 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)))