From f284f8355cb2d9213884120c4f615acbb512d7eb Mon Sep 17 00:00:00 2001 From: Michael Tremer Date: Thu, 26 Sep 2024 19:48:03 +0000 Subject: [PATCH] libloc: Refactor summarizing IP address ranges The algorithm seems to have had some bugs where it generated too many unnecessary subnets which caused the system to run out of memory very quickly when determining bogons. This version of the algorithm is now a little bit smarter and should be significantly faster as well. Signed-off-by: Michael Tremer --- src/database.c | 1 - src/libloc/address.h | 42 +++++++++++++++++++++++++++--------------- src/network-list.c | 43 +++++++++++++++---------------------------- 3 files changed, 42 insertions(+), 44 deletions(-) diff --git a/src/database.c b/src/database.c index f6a7c8a..8bbbe79 100644 --- a/src/database.c +++ b/src/database.c @@ -1626,7 +1626,6 @@ static int __loc_database_enumerator_next_bogon( return 0; FINISH: - if (!loc_address_all_zeroes(&enumerator->gap6_start)) { r = loc_address_reset_last(&gap_end, AF_INET6); if (r) diff --git a/src/libloc/address.h b/src/libloc/address.h index 1c14696..082c33f 100644 --- a/src/libloc/address.h +++ b/src/libloc/address.h @@ -160,6 +160,33 @@ static inline unsigned int loc_address_bit_length(const struct in6_addr* address return 0; } +static inline int loc_address_common_bits(const struct in6_addr* a1, const struct in6_addr* a2) { + int bits = 0; + + // Both must be of the same family + if (IN6_IS_ADDR_V4MAPPED(a1) && !IN6_IS_ADDR_V4MAPPED(a2)) + return -EINVAL; + + else if (!IN6_IS_ADDR_V4MAPPED(a1) && IN6_IS_ADDR_V4MAPPED(a2)) + return -EINVAL; + + // Walk through both addresses octet by octet + for (unsigned int i = (IN6_IS_ADDR_V4MAPPED(a1) ? 12 : 0); i <= 15; i++) { + // Fast path if the entire octet matches + if (a1->s6_addr[i] == a2->s6_addr[i]) { + bits += 8; + + // Otherwise we XOR the octets and count the leading zeroes + // (where both octets have been identical). + } else { + bits += __builtin_clz(a1->s6_addr[i] ^ a2->s6_addr[i]) - 24; + break; + } + } + + return bits; +} + static inline int loc_address_reset(struct in6_addr* address, int family) { switch (family) { case AF_INET6: @@ -285,21 +312,6 @@ static inline void loc_address_decrement(struct in6_addr* address) { } } -static inline int loc_address_count_trailing_zero_bits(const struct in6_addr* address) { - int zeroes = 0; - - int octet = 0; - foreach_octet_in_address_reverse(octet, address) { - if (address->s6_addr[octet]) { - zeroes += __builtin_ctz(address->s6_addr[octet]); - break; - } else - zeroes += 8; - } - - return zeroes; -} - static inline int loc_address_get_octet(const struct in6_addr* address, const unsigned int i) { if (IN6_IS_ADDR_V4MAPPED(address)) { if (i >= 4) diff --git a/src/network-list.c b/src/network-list.c index bca4422..d35bf56 100644 --- a/src/network-list.c +++ b/src/network-list.c @@ -322,6 +322,7 @@ LOC_EXPORT int loc_network_list_merge( int loc_network_list_summarize(struct loc_ctx* ctx, const struct in6_addr* first, const struct in6_addr* last, struct loc_network_list** list) { + int bits; int r; if (!list) { @@ -351,41 +352,27 @@ int loc_network_list_summarize(struct loc_ctx* ctx, struct loc_network* network = NULL; struct in6_addr start = *first; - const int family_bit_length = loc_address_family_bit_length(family1); - while (loc_address_cmp(&start, last) <= 0) { - struct in6_addr num; - int bits1; - - // Find the number of trailing zeroes of the start address - if (loc_address_all_zeroes(&start)) - bits1 = family_bit_length; - else { - bits1 = loc_address_count_trailing_zero_bits(&start); - if (bits1 > family_bit_length) - bits1 = family_bit_length; - } - - // Subtract the start address from the last address and add one - // (i.e. how many addresses are in this network?) - r = loc_address_sub(&num, last, &start); - if (r) - return r; - - loc_address_increment(&num); - - // How many bits do we need to represent this address? - int bits2 = loc_address_bit_length(&num) - 1; + // Count how many leading bits the IP addresses have in common + bits = loc_address_common_bits(&start, last); + if (bits < 0) + return bits; - // Select the smaller one - int bits = (bits1 > bits2) ? bits2 : bits1; + // If the start and end address don't have any bits in common, we try + // to cut the subnet into halves and try again... + else if (bits == 0) + bits = 1; // Create a network - r = loc_network_new(ctx, &network, &start, family_bit_length - bits); + r = loc_network_new(ctx, &network, &start, bits); if (r) return r; - DEBUG(ctx, "Found network %s\n", loc_network_str(network)); + DEBUG(ctx, "Found network %s, %s -> %s\n", + loc_network_str(network), + loc_address_str(loc_network_get_first_address(network)), + loc_address_str(loc_network_get_last_address(network)) + ); // Push network on the list r = loc_network_list_push(*list, network); -- 2.47.2