diff options
author | Yu Watanabe <watanabe.yu+github@gmail.com> | 2021-10-14 03:10:31 +0900 |
---|---|---|
committer | Yu Watanabe <watanabe.yu+github@gmail.com> | 2021-10-19 00:57:23 +0900 |
commit | cde09c34508947fbb4097facd9185dd385a1dbb5 (patch) | |
tree | dc1f8f2e85ce9b3d5c81add6d5abb4d00f7c389e /src/network/networkd-dhcp6.c | |
parent | 3f3bc1f2e70b7af71b58a551ed0be4438b0d9a9e (diff) | |
download | systemd-cde09c34508947fbb4097facd9185dd385a1dbb5.tar.gz |
network: dhcp6: manage assigned downstream prefixes by using Hashmap
When a system has thousands of downstream interfaces, previously the
total cost of finding free subnet ID was O(n^2), where n is the number
of downstream interfaces.
This makes assigned prefixes are managed by Manager with Hashmap. So,
the cost becomes O(n log n).
Diffstat (limited to 'src/network/networkd-dhcp6.c')
-rw-r--r-- | src/network/networkd-dhcp6.c | 97 |
1 files changed, 52 insertions, 45 deletions
diff --git a/src/network/networkd-dhcp6.c b/src/network/networkd-dhcp6.c index da8a882072..6816c19435 100644 --- a/src/network/networkd-dhcp6.c +++ b/src/network/networkd-dhcp6.c @@ -56,51 +56,53 @@ static bool dhcp6_lease_has_pd_prefix(sd_dhcp6_lease *lease) { return sd_dhcp6_lease_get_pd(lease, &pd_prefix, &pd_prefix_len, &lifetime_preferred, &lifetime_valid) >= 0; } -static int dhcp6_pd_get_link_by_prefix(Manager *manager, const struct in6_addr *prefix, Link **ret) { - union in_addr_union u; - Link *link; +static void link_remove_dhcp6_pd_prefix(Link *link, const struct in6_addr *prefix) { + void *key; - assert(manager); + assert(link); + assert(link->manager); assert(prefix); - u.in6 = *prefix; + if (hashmap_get(link->manager->links_by_dhcp6_pd_prefix, prefix) != link) + return; - HASHMAP_FOREACH(link, manager->links_by_index) { - if (!link_dhcp6_pd_is_enabled(link)) - continue; + hashmap_remove2(link->manager->links_by_dhcp6_pd_prefix, prefix, &key); + free(key); +} - if (link->network->dhcp6_pd_assign) { - Address *address; +static int link_add_dhcp6_pd_prefix(Link *link, const struct in6_addr *prefix) { + _cleanup_free_ struct in6_addr *copy = NULL; + int r; - SET_FOREACH(address, link->addresses) { - if (address->source != NETWORK_CONFIG_SOURCE_DHCP6PD) - continue; - assert(address->family == AF_INET6); + assert(link); + assert(prefix); - if (in_addr_prefix_covers(AF_INET6, &u, 64, &address->in_addr) > 0) { - if (ret) - *ret = link; - return 0; - } - } - } else { - Route *route; - - SET_FOREACH(route, link->routes) { - if (route->source != NETWORK_CONFIG_SOURCE_DHCP6PD) - continue; - assert(route->family == AF_INET6); - - if (in6_addr_equal(&route->dst.in6, prefix)) { - if (ret) - *ret = link; - return 0; - } - } - } - } + copy = newdup(struct in6_addr, prefix, 1); + if (!copy) + return -ENOMEM; - return -ENOENT; + r = hashmap_ensure_put(&link->manager->links_by_dhcp6_pd_prefix, &in6_addr_hash_ops_free, copy, link); + if (r < 0) + return r; + if (r > 0) + TAKE_PTR(copy); + + return 0; +} + +static int link_get_by_dhcp6_pd_prefix(Manager *manager, const struct in6_addr *prefix, Link **ret) { + Link *link; + + assert(manager); + assert(prefix); + + link = hashmap_get(manager->links_by_dhcp6_pd_prefix, prefix); + if (!link) + return -ENODEV; + + if (ret) + *ret = link; + return 0; } static int dhcp6_pd_get_assigned_prefix(Link *link, const struct in6_addr *pd_prefix, uint8_t pd_prefix_len, struct in6_addr *ret) { @@ -175,6 +177,8 @@ int dhcp6_pd_remove(Link *link, bool only_marked) { if (link->radv) (void) sd_radv_remove_prefix(link->radv, &route->dst.in6, 64); + link_remove_dhcp6_pd_prefix(link, &route->dst.in6); + k = route_remove(route); if (k < 0) r = k; @@ -183,17 +187,20 @@ int dhcp6_pd_remove(Link *link, bool only_marked) { } SET_FOREACH(address, link->addresses) { + struct in6_addr prefix; + if (address->source != NETWORK_CONFIG_SOURCE_DHCP6PD) continue; if (only_marked && !address_is_marked(address)) continue; - if (link->radv) { - union in_addr_union prefix = address->in_addr; + prefix = address->in_addr.in6; + in6_addr_mask(&prefix, 64); - in_addr_mask(AF_INET6, &prefix, 64); - (void) sd_radv_remove_prefix(link->radv, &prefix.in6, 64); - } + if (link->radv) + (void) sd_radv_remove_prefix(link->radv, &prefix, 64); + + link_remove_dhcp6_pd_prefix(link, &prefix); k = address_remove(address); if (k < 0) @@ -436,7 +443,7 @@ static int dhcp6_pd_assign_prefix( if (r < 0) return r; - return 0; + return link_add_dhcp6_pd_prefix(link, prefix); } static bool link_has_preferred_subnet_id(Link *link) { @@ -485,7 +492,7 @@ static int dhcp6_get_preferred_delegated_prefix( * This should not fail as we checked the prefix size beforehand */ assert_se(in_addr_prefix_covers(AF_INET6, (const union in_addr_union*) pd_prefix, pd_prefix_len, &prefix) > 0); - if (dhcp6_pd_get_link_by_prefix(link->manager, &prefix.in6, &assigned_link) >= 0 && + if (link_get_by_dhcp6_pd_prefix(link->manager, &prefix.in6, &assigned_link) >= 0 && assigned_link != link) { _cleanup_free_ char *assigned_buf = NULL; @@ -502,7 +509,7 @@ static int dhcp6_get_preferred_delegated_prefix( for (uint64_t n = 0; n < n_prefixes; n++) { /* If we do not have an allocation preference just iterate * through the address space and return the first free prefix. */ - if (dhcp6_pd_get_link_by_prefix(link->manager, &prefix.in6, &assigned_link) < 0 || + if (link_get_by_dhcp6_pd_prefix(link->manager, &prefix.in6, &assigned_link) < 0 || assigned_link == link) { *ret = prefix.in6; return 0; |