From aa6870be6be4e1696243b19655216b7799a5e092 Mon Sep 17 00:00:00 2001 From: =?utf8?q?David=20H=C3=A4rdeman?= Date: Sat, 11 Oct 2025 08:29:07 +0200 Subject: [PATCH] dhcpv4: use an AVL to store leases MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit An AVL has O(log n) complexity vs O(n) for a linked list in all the operations we care about (insertion and search). Also, it makes the code simpler by not having to care about details like how to sort the leases. Signed-off-by: David Härdeman Link: https://github.com/openwrt/odhcpd/pull/306 Signed-off-by: Álvaro Fernández Rojas --- src/config.c | 7 ++++++- src/dhcpv4.c | 53 ++++++++++++++++++++---------------------------- src/odhcpd.h | 4 ++-- src/statefiles.c | 4 ++-- src/ubus.c | 4 ++-- 5 files changed, 34 insertions(+), 38 deletions(-) diff --git a/src/config.c b/src/config.c index 055cd5d..056dd47 100644 --- a/src/config.c +++ b/src/config.c @@ -1069,6 +1069,11 @@ err: return -1; } +static int avl_ipv4_cmp(const void *k1, const void *k2, _unused void *ptr) +{ + return memcmp(k1, k2, sizeof(struct in_addr)); +} + int config_parse_interface(void *data, size_t len, const char *name, bool overwrite) { struct odhcpd_ipaddr *addrs = NULL; @@ -1103,7 +1108,7 @@ int config_parse_interface(void *data, size_t len, const char *name, bool overwr iface->ndp_ping_fd = -1; iface->dhcpv4_event.uloop.fd = -1; INIT_LIST_HEAD(&iface->ia_assignments); - INIT_LIST_HEAD(&iface->dhcpv4_leases); + avl_init(&iface->dhcpv4_leases, avl_ipv4_cmp, false, iface); INIT_LIST_HEAD(&iface->dhcpv4_fr_ips); set_interface_defaults(iface); diff --git a/src/dhcpv4.c b/src/dhcpv4.c index 4c574af..f5db428 100644 --- a/src/dhcpv4.c +++ b/src/dhcpv4.c @@ -84,7 +84,7 @@ static bool leases_require_fr(struct interface *iface, struct odhcpd_ipaddr *add struct dhcpv4_lease *lease = NULL; struct odhcpd_ref_ip *fr_ip = NULL; - list_for_each_entry(lease, &iface->dhcpv4_leases, head) { + avl_for_each_element(&iface->dhcpv4_leases, lease, iface_avl) { if ((lease->accept_fr_nonce || iface->dhcpv4_forcereconf) && !lease->fr_ip && ((lease->addr & mask) == (addr->addr.in.s_addr & mask))) { @@ -333,13 +333,17 @@ static void dhcpv4_fr_rand_delay(struct dhcpv4_lease *lease) void dhcpv4_free_lease(struct dhcpv4_lease *lease) { + if (!lease) + return; + if (lease->fr_ip) dhcpv4_fr_stop(lease); - if (lease->iface) + if (lease->iface) { lease->iface->update_statefile = true; + avl_delete(&lease->iface->dhcpv4_leases, &lease->iface_avl); + } - list_del(&lease->head); if (lease->lease_cfg) lease->lease_cfg->dhcpv4_lease = NULL; @@ -361,8 +365,7 @@ dhcpv4_alloc_lease(struct interface *iface, const uint8_t *hwaddr, if (!lease) return NULL; - INIT_LIST_HEAD(&lease->head); - + lease->iface_avl.key = &lease->addr; lease->hwaddr_len = hwaddr_len; memcpy(lease->hwaddr, hwaddr, hwaddr_len); if (duid_len > 0) { @@ -375,27 +378,14 @@ dhcpv4_alloc_lease(struct interface *iface, const uint8_t *hwaddr, return lease; } -static bool dhcpv4_insert_lease(struct list_head *list, struct dhcpv4_lease *lease, +static bool dhcpv4_insert_lease(struct avl_tree *avl, struct dhcpv4_lease *lease, uint32_t addr) { - uint32_t h_addr = ntohl(addr); - struct dhcpv4_lease *c; - - list_for_each_entry(c, list, head) { - uint32_t c_addr = ntohl(c->addr); - - if (c_addr == h_addr) - return false; - - if (c_addr > h_addr) - break; - } - - /* Insert new node before c (might match list head) */ lease->addr = addr; - list_add_tail(&lease->head, &c->head); - - return true; + if (!avl_insert(avl, &lease->iface_avl)) + return true; + else + return false; } static bool dhcpv4_assign(struct interface *iface, struct dhcpv4_lease *lease, @@ -476,7 +466,7 @@ static struct dhcpv4_lease *find_lease_by_hwaddr(struct interface *iface, const { struct dhcpv4_lease *lease; - list_for_each_entry(lease, &iface->dhcpv4_leases, head) + avl_for_each_element(&iface->dhcpv4_leases, lease, iface_avl) if (!memcmp(lease->hwaddr, hwaddr, 6)) return lease; @@ -489,7 +479,7 @@ find_lease_by_duid_iaid(struct interface *iface, const uint8_t *duid, { struct dhcpv4_lease *lease; - list_for_each_entry(lease, &iface->dhcpv4_leases, head) { + avl_for_each_element(&iface->dhcpv4_leases, lease, iface_avl) { if (lease->duid_len != duid_len || lease->iaid != iaid) continue; if (!memcmp(lease->duid, duid, duid_len)) @@ -594,7 +584,7 @@ dhcpv4_lease(struct interface *iface, enum dhcpv4_msg req_msg, const uint8_t *re (iface->dhcpv4_start_ip.s_addr & iface->dhcpv4_mask.s_addr)) && !(lease->flags & OAF_STATIC)) { /* Try to reassign to an address that is in-scope */ - list_del_init(&lease->head); + avl_delete(&iface->dhcpv4_leases, &lease->iface_avl); lease->addr = INADDR_ANY; if (!dhcpv4_assign(iface, lease, req_addr)) { dhcpv4_free_lease(lease); @@ -1428,9 +1418,10 @@ int dhcpv4_setup_interface(struct interface *iface, bool enable) } if (!enable || iface->dhcpv4 == MODE_DISABLED) { - while (!list_empty(&iface->dhcpv4_leases)) - dhcpv4_free_lease(list_first_entry(&iface->dhcpv4_leases, - struct dhcpv4_lease, head)); + struct dhcpv4_lease *lease, *tmp; + + avl_remove_all_elements(&iface->dhcpv4_leases, lease, iface_avl, tmp) + dhcpv4_free_lease(lease); return 0; } @@ -1541,7 +1532,7 @@ static void dhcpv4_addrlist_change(struct interface *iface) return; } - list_for_each_entry(lease, &iface->dhcpv4_leases, head) { + avl_for_each_element(&iface->dhcpv4_leases, lease, iface_avl) { if ((lease->flags & OAF_BOUND) && lease->fr_ip && !lease->fr_cnt) { if (lease->accept_fr_nonce || iface->dhcpv4_forcereconf) dhcpv4_fr_rand_delay(lease); @@ -1582,7 +1573,7 @@ static void dhcpv4_valid_until_cb(struct uloop_timeout *event) if (iface->dhcpv4 != MODE_SERVER) continue; - list_for_each_entry_safe(lease, tmp, &iface->dhcpv4_leases, head) { + avl_for_each_element_safe(&iface->dhcpv4_leases, lease, iface_avl, tmp) { if (!INFINITE_VALID(lease->valid_until) && lease->valid_until < now) { ubus_bcast_dhcp_event("dhcp.expire", lease->hwaddr, (struct in_addr *)&lease->addr, diff --git a/src/odhcpd.h b/src/odhcpd.h index 520c27f..924fbe2 100644 --- a/src/odhcpd.h +++ b/src/odhcpd.h @@ -232,7 +232,7 @@ struct duid { struct odhcpd_ref_ip; struct dhcpv4_lease { - struct list_head head; // struct interface->dhcpv4_assignments + struct avl_node iface_avl; // struct interface->dhcpv4_leases struct interface *iface; // assignment interface, non-null struct lease_cfg *lease_cfg; // host lease cfg, nullable @@ -367,7 +367,7 @@ struct interface { // DHCPv4 runtime data struct odhcpd_event dhcpv4_event; - struct list_head dhcpv4_leases; + struct avl_tree dhcpv4_leases; struct list_head dhcpv4_fr_ips; // Services diff --git a/src/statefiles.c b/src/statefiles.c index c5f2b57..e27a92c 100644 --- a/src/statefiles.c +++ b/src/statefiles.c @@ -139,7 +139,7 @@ static void statefiles_write_hosts(time_t now) if (ctxt.iface->dhcpv4 == MODE_SERVER) { struct dhcpv4_lease *lease; - list_for_each_entry(lease, &ctxt.iface->dhcpv4_leases, head) { + avl_for_each_element(&ctxt.iface->dhcpv4_leases, lease, iface_avl) { if (!(lease->flags & OAF_BOUND)) continue; @@ -297,7 +297,7 @@ static bool statefiles_write_state(time_t now) if (ctxt.iface->dhcpv4 == MODE_SERVER) { struct dhcpv4_lease *lease; - list_for_each_entry(lease, &ctxt.iface->dhcpv4_leases, head) { + avl_for_each_element(&ctxt.iface->dhcpv4_leases, lease, iface_avl) { if (!(lease->flags & OAF_BOUND)) continue; diff --git a/src/ubus.c b/src/ubus.c index 7378f0a..1301291 100644 --- a/src/ubus.c +++ b/src/ubus.c @@ -36,9 +36,9 @@ static int handle_dhcpv4_leases(struct ubus_context *ctx, _unused struct ubus_ob void *i = blobmsg_open_table(&b, iface->ifname); void *j = blobmsg_open_array(&b, "leases"); - struct dhcpv4_lease *c; - list_for_each_entry(c, &iface->dhcpv4_leases, head) { + + avl_for_each_element(&iface->dhcpv4_leases, c, iface_avl) { if (!INFINITE_VALID(c->valid_until) && c->valid_until < now) continue; -- 2.30.2