From 9306c68db4f95b0e7dc315f3daef6dbbba7a815e Mon Sep 17 00:00:00 2001 From: Michael Tremer Date: Mon, 7 Mar 2022 11:12:17 +0000 Subject: [PATCH] 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 --- src/database.c | 108 ++++++++++++++++++++++++++++++------------- src/libloc/network.h | 15 ++++++ src/libloc/private.h | 40 ++++++++++++++++ 3 files changed, 132 insertions(+), 31 deletions(-) diff --git a/src/database.c b/src/database.c index e5f779d..38dc174 100644 --- 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 3b8b95f..857767f 100644 --- 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 301672d..d6bebdf 100644 --- 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; -- 2.39.5