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).

3 files changed, 54 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;
diff --git a/src/network/networkd-manager.c b/src/network/networkd-manager.c
index b4494d5182..c5ccfb4b58 100644
--- a/src/network/networkd-manager.c
+++ b/src/network/networkd-manager.c
@@ -485,6 +485,7 @@ Manager* manager_free(Manager *m) {
         m->dirty_links = set_free_with_destructor(m->dirty_links, link_unref);
         m->links_by_name = hashmap_free(m->links_by_name);
         m->links_by_hw_addr = hashmap_free(m->links_by_hw_addr);
+        m->links_by_dhcp6_pd_prefix = hashmap_free(m->links_by_dhcp6_pd_prefix);
         m->links_by_index = hashmap_free_with_destructor(m->links_by_index, link_unref);
 
         m->networks = ordered_hashmap_free_with_destructor(m->networks, network_unref);
diff --git a/src/network/networkd-manager.h b/src/network/networkd-manager.h
index 5f3f81ad9d..42b77ee0f5 100644
--- a/src/network/networkd-manager.h
+++ b/src/network/networkd-manager.h
@@ -48,6 +48,7 @@ struct Manager {
         Hashmap *links_by_index;
         Hashmap *links_by_name;
         Hashmap *links_by_hw_addr;
+        Hashmap *links_by_dhcp6_pd_prefix;
         Hashmap *netdevs;
         OrderedHashmap *networks;
         OrderedSet *address_pools;