bogons: Refactor algorithms

This changes that we won't compare one network with the previous one,
but instead we will look for gaps starting from the first possible to
the last possible IP address.

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

diff --git a/src/database.c b/src/database.c
index e5f779d72c2fb1982fe0a4d76cba345379e5d3a4..38dc174c2b480b91113cb2624b1ec8bd66f2fa98 100644 (file)
--- a/src/database.c
+++ b/src/database.c
@@ -124,7 +124,10 @@ struct loc_database_enumerator {
 
        // For subnet search and bogons
        struct loc_network_list* stack;
-       struct loc_network* last_network;
+
+       // For bogons
+       struct in6_addr gap6_start;
+       struct in6_addr gap4_start;
 };
 
 static int loc_database_read_magic(struct loc_database* db) {
@@ -985,9 +988,6 @@ static void loc_database_enumerator_free(struct loc_database_enumerator* enumera
        if (enumerator->stack)
                loc_network_list_unref(enumerator->stack);
 
-       if (enumerator->last_network)
-               loc_network_unref(enumerator->last_network);
-
        free(enumerator);
 }
 
@@ -1017,6 +1017,10 @@ LOC_EXPORT int loc_database_enumerator_new(struct loc_database_enumerator** enum
                return r;
        }
 
+       // Initialize bogon search
+       loc_address_reset(&e->gap6_start, AF_INET6);
+       loc_address_reset(&e->gap4_start, AF_INET);
+
        DEBUG(e->ctx, "Database enumerator object allocated at %p\n", e);
 
        *enumerator = e;
@@ -1397,23 +1401,6 @@ static int __loc_database_enumerator_next_network_flattened(
 /*
        This function finds all bogons (i.e. gaps) between the input networks
 */
-static int __loc_database_enumerator_find_bogons(struct loc_ctx* ctx,
-               struct loc_network* first, struct loc_network* second, struct loc_network_list* bogons) {
-       // We do not need to check if first < second because the graph is always ordered
-
-       // The last address of the first network + 1 is the start of the gap
-       struct in6_addr first_address = address_increment(loc_network_get_last_address(first));
-
-       // The first address of the second network - 1 is the end of the gap
-       struct in6_addr last_address = address_decrement(loc_network_get_first_address(second));
-
-       // If first address is now greater than last address, there is no gap
-       if (in6_addr_cmp(&first_address, &last_address) >= 0)
-               return 0;
-
-       return loc_network_list_summarize(ctx, &first_address, &last_address, &bogons);
-}
-
 static int __loc_database_enumerator_next_bogon(
                struct loc_database_enumerator* enumerator, struct loc_network** bogon) {
        int r;
@@ -1431,26 +1418,53 @@ static int __loc_database_enumerator_next_bogon(
        }
 
        struct loc_network* network = NULL;
+       struct in6_addr* gap_start = NULL;
+       struct in6_addr gap_end = IN6ADDR_ANY_INIT;
 
        while (1) {
                r = __loc_database_enumerator_next_network(enumerator, &network, 1);
                if (r)
-                       goto ERROR;
+                       return r;
 
+               // We have read the last network
                if (!network)
-                       break;
+                       goto FINISH;
+
+               // Determine the network family
+               int family = loc_network_address_family(network);
+
+               switch (family) {
+                       case AF_INET6:
+                               gap_start = &enumerator->gap6_start;
+                               break;
+
+                       case AF_INET:
+                               gap_start = &enumerator->gap4_start;
+                               break;
+
+                       default:
+                               ERROR(enumerator->ctx, "Unsupported network family %d\n", family);
+                               errno = ENOTSUP;
+                               return 1;
+               }
+
+               // Search where the gap could end
+               gap_end = address_decrement(loc_network_get_first_address(network));
 
-               if (enumerator->last_network && loc_network_address_family(enumerator->last_network) == loc_network_address_family(network)) {
-                       r = __loc_database_enumerator_find_bogons(enumerator->ctx,
-                               enumerator->last_network, network, enumerator->stack);
+               // There is a gap
+               if (in6_addr_cmp(gap_start, &gap_end) < 0) {
+                       r = loc_network_list_summarize(enumerator->ctx,
+                               gap_start, &gap_end, &enumerator->stack);
                        if (r) {
                                loc_network_unref(network);
-                               goto ERROR;
+                               return r;
                        }
                }
 
-               // Remember network for next iteration
-               enumerator->last_network = loc_network_ref(network);
+               // The gap now starts after this network
+               const struct in6_addr* network_end = loc_network_get_last_address(network);
+               (*gap_start) = address_increment(network_end);
+
                loc_network_unref(network);
 
                // Try to return something
@@ -1459,8 +1473,40 @@ static int __loc_database_enumerator_next_bogon(
                        break;
        }
 
-ERROR:
-       return r;
+       return 0;
+
+FINISH:
+
+       if (!loc_address_all_zeroes(&enumerator->gap6_start)) {
+               r = loc_address_reset_last(&gap_end, AF_INET6);
+               if (r)
+                       return r;
+
+               if (in6_addr_cmp(&enumerator->gap6_start, &gap_end) < 0) {
+                       r = loc_network_list_summarize(enumerator->ctx,
+                               &enumerator->gap6_start, &gap_end, &enumerator->stack);
+                       if (r)
+                               return r;
+               }
+       }
+
+       if (!loc_address_all_zeroes(&enumerator->gap4_start)) {
+               r = loc_address_reset_last(&gap_end, AF_INET);
+               if (r)
+                       return r;
+
+               if (in6_addr_cmp(&enumerator->gap4_start, &gap_end) < 0) {
+                       r = loc_network_list_summarize(enumerator->ctx,
+                               &enumerator->gap4_start, &gap_end, &enumerator->stack);
+                       if (r)
+                               return r;
+               }
+       }
+
+       // Try to return something
+       *bogon = loc_network_list_pop_first(enumerator->stack);
+
+       return 0;
 }
 
 LOC_EXPORT int loc_database_enumerator_next_network(

diff --git a/src/libloc/network.h b/src/libloc/network.h
index 3b8b95f672613a6241a077d50b1a5b7f70916819..857767f88cdff3005e4ea0c543f3e76163c6d421 100644 (file)
--- a/src/libloc/network.h
+++ b/src/libloc/network.h
@@ -103,6 +103,21 @@ static inline int loc_address_family(const struct in6_addr* address) {
                return AF_INET6;
 }
 
+static inline int loc_address_all_zeroes(const struct in6_addr* address) {
+       struct in6_addr all_zeroes = IN6ADDR_ANY_INIT;
+
+       const int family = loc_address_family(address);
+
+       int r = loc_address_reset(&all_zeroes, family);
+       if (r)
+               return r;
+
+       if (in6_addr_cmp(address, &all_zeroes) == 0)
+               return 1;
+
+       return 0;
+}
+
 static inline int loc_address_count_trailing_zero_bits(const struct in6_addr* address) {
        int zeroes = 0;
 

diff --git a/src/libloc/private.h b/src/libloc/private.h
index 301672d87c826c0c8505a399a173d50ab6016f02..d6bebdf9e59ad69fe1f351cd72c0e06fc129ea87 100644 (file)
--- a/src/libloc/private.h
+++ b/src/libloc/private.h
@@ -130,6 +130,46 @@ static inline unsigned int loc_address_bit_length(const struct in6_addr* address
                return __loc_address6_bit_length(address);
 }
 
+static inline int loc_address_reset(struct in6_addr* address, int family) {
+       switch (family) {
+               case AF_INET6:
+                       address->s6_addr32[0] = 0x0000;
+                       address->s6_addr32[1] = 0x0000;
+                       address->s6_addr32[2] = 0x0000;
+                       address->s6_addr32[3] = 0x0000;
+                       return 0;
+
+               case AF_INET:
+                       address->s6_addr32[0] = 0x0000;
+                       address->s6_addr32[1] = 0x0000;
+                       address->s6_addr32[2] = htonl(0xffff);
+                       address->s6_addr32[3] = 0x0000;
+                       return 0;
+       }
+
+       return -1;
+}
+
+static inline int loc_address_reset_last(struct in6_addr* address, int family) {
+       switch (family) {
+               case AF_INET6:
+                       address->s6_addr32[0] = 0xffff;
+                       address->s6_addr32[1] = 0xffff;
+                       address->s6_addr32[2] = 0xffff;
+                       address->s6_addr32[3] = 0xffff;
+                       return 0;
+
+               case AF_INET:
+                       address->s6_addr32[0] = 0x0000;
+                       address->s6_addr32[1] = 0x0000;
+                       address->s6_addr32[2] = htonl(0xffff);
+                       address->s6_addr32[3] = 0xffff;
+                       return 0;
+       }
+
+       return -1;
+}
+
 static inline struct in6_addr loc_address_and(
                const struct in6_addr* address, const struct in6_addr* bitmask) {
        struct in6_addr a;