Merge networks before writing the database

This should help us keeping the database more compact where we summarize
two smaller networks to one larger one if they share the same
properties.

Signed-off-by: Michael Tremer <michael.tremer@ipfire.org>

diff --git a/src/libloc/network-list.h b/src/libloc/network-list.h
index 988a8a0d692638b1705fe96bdbc9f6b6876e775a..7d3c791bdee67e767a1dda3bc92b6d5b6c94310c 100644 (file)
--- a/src/libloc/network-list.h
+++ b/src/libloc/network-list.h
@@ -31,9 +31,13 @@ struct loc_network* loc_network_list_get(struct loc_network_list* list, size_t i
 int loc_network_list_push(struct loc_network_list* list, struct loc_network* network);
 struct loc_network* loc_network_list_pop(struct loc_network_list* list);
 struct loc_network* loc_network_list_pop_first(struct loc_network_list* list);
+int loc_network_list_remove(struct loc_network_list* list, struct loc_network* network);
 int loc_network_list_contains(struct loc_network_list* list, struct loc_network* network);
 int loc_network_list_merge(struct loc_network_list* self, struct loc_network_list* other);
 
+void loc_network_list_remove_with_prefix_smaller_than(
+       struct loc_network_list* list, const unsigned int prefix);
+
 #ifdef LIBLOC_PRIVATE
 
 #include <netinet/in.h>

diff --git a/src/network-list.c b/src/network-list.c
index 1b64a7ef8aa7c7690729630b1fad3e9b87472a59..bca44221c011ec881bc9c95d242057add83f2fa8 100644 (file)
--- a/src/network-list.c
+++ b/src/network-list.c
@@ -276,6 +276,29 @@ LOC_EXPORT struct loc_network* loc_network_list_pop_first(struct loc_network_lis
        return network;
 }
 
+int loc_network_list_remove(struct loc_network_list* list, struct loc_network* network) {
+       int found = 0;
+
+       // Find the network on the list
+       off_t index = loc_network_list_find(list, network, &found);
+
+       // Nothing to do if the network wasn't found
+       if (!found)
+               return 0;
+
+       // Dereference the network at the position
+       loc_network_unref(list->elements[index]);
+
+       // Move all other elements back
+       for (unsigned int i = index; i < list->size - 1; i++)
+               list->elements[i] = list->elements[i+1];
+
+       // The list is shorter now
+       --list->size;
+
+       return 0;
+}
+
 LOC_EXPORT int loc_network_list_contains(struct loc_network_list* list, struct loc_network* network) {
        int found = 0;
 
@@ -383,3 +406,34 @@ int loc_network_list_summarize(struct loc_ctx* ctx,
 
        return 0;
 }
+
+void loc_network_list_remove_with_prefix_smaller_than(
+               struct loc_network_list* list, const unsigned int prefix) {
+       unsigned int p = 0;
+
+       // Count how many networks were removed
+       unsigned int removed = 0;
+
+       for (unsigned int i = 0; i < list->size; i++) {
+               // Fetch the prefix
+               p = loc_network_prefix(list->elements[i]);
+
+               if (p > prefix) {
+                       // Drop this network
+                       loc_network_unref(list->elements[i]);
+
+                       // Increment counter
+                       removed++;
+
+                       continue;
+               }
+
+               // Move pointers backwards to keep the list filled
+               list->elements[i - removed] = list->elements[i];
+       }
+
+       // Adjust size
+       list->size -= removed;
+
+       return;
+}

diff --git a/src/network.c b/src/network.c
index d8aa10ef9e718aedaf6827ecbfd491b023e30c0c..2c1d8b7906be748cb9b1c048aaf92e8365ad0fdf 100644 (file)
--- a/src/network.c
+++ b/src/network.c
@@ -575,6 +575,64 @@ LOC_EXPORT struct loc_network_list* loc_network_exclude_list(
        return subnets;
 }
 
+static int loc_network_merge(struct loc_network** n,
+               struct loc_network* n1, struct loc_network* n2) {
+       struct loc_network* network = NULL;
+       struct in6_addr address;
+       int r;
+
+       // Reset pointer
+       *n = NULL;
+
+       // Family must match
+       if (n1->family != n2->family)
+               return 0;
+
+       // The prefix must match, too
+       if (n1->prefix != n2->prefix)
+               return 0;
+
+       // Cannot merge ::/0 or 0.0.0.0/0
+       if (!n1->prefix || !n2->prefix)
+               return 0;
+
+       const unsigned int prefix = loc_network_prefix(n1);
+
+       // How many bits do we need to represent this address?
+       const size_t bitlength = loc_address_bit_length(&n1->first_address) - 1;
+
+       // We cannot shorten this any more
+       if (bitlength == prefix)
+               return 0;
+
+       // Increment the last address of the first network
+       address = n1->last_address;
+       loc_address_increment(&address);
+
+       // If they don't match they are not neighbours
+       if (loc_address_cmp(&address, &n2->first_address) != 0)
+               return 0;
+
+       // All properties must match, too
+       if (loc_network_properties_cmp(n1, n2) != 0)
+               return 0;
+
+       // Create a new network object
+       r = loc_network_new(n1->ctx, &network, &n1->first_address, prefix - 1);
+       if (r)
+               return r;
+
+       // Copy everything else
+       loc_country_code_copy(network->country_code, n1->country_code);
+       network->asn = n1->asn;
+       network->flags = n1->flags;
+
+       // Return pointer
+       *n = network;
+
+       return 0;
+}
+
 int loc_network_to_database_v1(struct loc_network* network, struct loc_database_network_v1* dbobj) {
        // Add country code
        loc_country_code_copy(dbobj->country_code, network->country_code);
@@ -813,7 +871,8 @@ int loc_network_tree_add_network(struct loc_network_tree* tree, struct loc_netwo
 
        // Check if node has not been set before
        if (node->network) {
-               DEBUG(tree->ctx, "There is already a network at this path\n");
+               DEBUG(tree->ctx, "There is already a network at this path: %s\n",
+                       loc_network_str(node->network));
                return -EBUSY;
        }
 
@@ -932,6 +991,139 @@ struct loc_network* loc_network_tree_node_get_network(struct loc_network_tree_no
        return loc_network_ref(node->network);
 }
 
+/*
+       Merge the tree!
+*/
+
+struct loc_network_tree_merge_ctx {
+       struct loc_network_tree* tree;
+       struct loc_network_list* networks;
+       unsigned int merged;
+};
+
+static int loc_network_tree_merge_step(struct loc_network* network, void* data) {
+       struct loc_network_tree_merge_ctx* ctx = (struct loc_network_tree_merge_ctx*)data;
+       struct loc_network* n = NULL;
+       struct loc_network* m = NULL;
+       int r;
+
+       // How many networks do we have?
+       size_t i = loc_network_list_size(ctx->networks);
+
+       // If the list is empty, just add the network
+       if (i == 0)
+               return loc_network_list_push(ctx->networks, network);
+
+       while (i--) {
+               // Fetch the last network of the list
+               n = loc_network_list_get(ctx->networks, i);
+
+               // Try to merge the two networks
+               r = loc_network_merge(&m, n, network);
+               if (r)
+                       goto ERROR;
+
+               // Did we get a result?
+               if (m) {
+                       DEBUG(ctx->tree->ctx, "Merged networks %s + %s -> %s\n",
+                               loc_network_str(n), loc_network_str(network), loc_network_str(m));
+
+                       // Add the new network
+                       r = loc_network_tree_add_network(ctx->tree, m);
+                       switch (r) {
+                               case 0:
+                                       break;
+
+                               // There might already be a network
+                               case -EBUSY:
+                                       r = 0;
+                                       goto ERROR;
+
+                               default:
+                                       goto ERROR;
+                       }
+
+                       // It would be nice if we could remove the networks that we just merged,
+                       // but removing objects from the tree while walking through it is something
+                       // we currently don't support. The deduplication check will however find
+                       // and remove these networks.
+
+                       // Add the new network to the stack
+                       r = loc_network_list_push(ctx->networks, m);
+                       if (r)
+                               goto ERROR;
+
+                       // Remove the previous network from the stack
+                       r = loc_network_list_remove(ctx->networks, n);
+                       if (r)
+                               goto ERROR;
+
+                       // Count merges
+                       ctx->merged++;
+
+                       // Try merging the new network with others
+                       r = loc_network_tree_merge_step(m, data);
+                       if (r)
+                               goto ERROR;
+
+                       loc_network_unref(m);
+                       m = NULL;
+
+                       // Once we have found a merge, we are done
+                       break;
+
+               // If we could not merge the two networks, we add the current one
+               } else {
+                       r = loc_network_list_push(ctx->networks, network);
+                       if (r)
+                               goto ERROR;
+               }
+
+               loc_network_unref(n);
+               n = NULL;
+       }
+
+       const unsigned int prefix = loc_network_prefix(network);
+
+       // Remove any networks that we cannot merge
+       loc_network_list_remove_with_prefix_smaller_than(ctx->networks, prefix);
+
+ERROR:
+       if (m)
+               loc_network_unref(m);
+       if (n)
+               loc_network_unref(n);
+
+       return r;
+}
+
+static int loc_network_tree_merge(struct loc_network_tree* tree) {
+       struct loc_network_tree_merge_ctx ctx = {
+               .tree     = tree,
+               .networks = NULL,
+               .merged   = 0,
+       };
+       int r;
+
+       // Create a new list
+       r = loc_network_list_new(tree->ctx, &ctx.networks);
+       if (r)
+               goto ERROR;
+
+       // Walk through the entire tree
+       r = loc_network_tree_walk(tree, NULL, loc_network_tree_merge_step, &ctx);
+       if (r)
+               goto ERROR;
+
+       DEBUG(tree->ctx, "%u network(s) have been merged\n", ctx.merged);
+
+ERROR:
+       if (ctx.networks)
+               loc_network_list_unref(ctx.networks);
+
+       return r;
+}
+
 /*
        Deduplicate the tree
 */
@@ -1050,7 +1242,19 @@ static int loc_network_tree_delete_nodes(struct loc_network_tree* tree) {
 int loc_network_tree_cleanup(struct loc_network_tree* tree) {
        int r;
 
-       // Deduplicate the tree
+       // Deduplicate the tree so finding merges is quicker
+       r = loc_network_tree_dedup(tree);
+       if (r)
+               return r;
+
+       // Merge networks
+       r = loc_network_tree_merge(tree);
+       if (r) {
+               ERROR(tree->ctx, "Could not merge networks: %m\n");
+               return r;
+       }
+
+       // Remove duplicates once again
        r = loc_network_tree_dedup(tree);
        if (r)
                return r;