3 ms·

If you want to get fun with it you can actually fit the entire IP range in a single 32 bit value. On the internet networks larger than /24s aren't considered va

If you want to get fun with it you can actually fit the entire IP range in a single 32 bit value. On the internet networks larger than /24s aren't considered valid advertisements so you only need to store 3 bytes (the first 24 bits) of the address to hold the start. If you store than in a uint32 you can use the remaining 8 bits to hold the netmask (you don't actually need all of them but it keeps things byte aligned), which lets you dynamically calculate the end address in just a few CPU cycles. The search still occurs on the base address portion so you don't ever have to calculate the end address until you've already found the right base address.

teddyh 2y ago
> On the internet networks larger than /24s aren't considered valid advertisements The number 24 is larger, but the network is smaller.
- zamadatix 2y ago
  Good catch, thanks! This should have been "netmasks" instead of "networks" but it's too late for me to edit now.
  - AStonesThrow 2y ago
    A netmask is different and deprecated terminology. The "/24" you refer to is a "prefix length", i.e. a network prefix being advertised by BGP.
riobard 2y ago
> fit the entire IP range in a single 32 bit value … only if you pretend IPv6 does not exist, which isn't the case in the original blogpost. But the idea can be extended to fit entire IP (both v4 and v6) subnets in an uint64, given that the minimal IPv6 prefix size to be globally routed is /48, you could use the first byte of the uint64 to mark the address type (e.g. 0x4 for IPv4 and 0x6 for IPv6), the remaining 3 (for IPv4) or 6 (for IPv6) bytes for actual prefix, and the last byte for prefix length.
blibble 2y ago
for ipv4 you can do with with just a single lookup, so real O(1) store the entire thing in one big array, indexed by the uint24 value of the /24 so ASN for 0.0.0.0 stored in position 0, ASN for 0.0.1.0 stored in position 1, etc and you can drop 0.0.0.0/8, 10.0.0.0/8, 127.0.0.0/8, 224.0.0.0/4, 240.0.0.0/24 to save 35 /8s (256-16-16-3)256256*4 bytes needed -> 55mb mmap it if necessary
- zamadatix 2y ago
  If you do it this way I think you lose all of the prefix size info I.e. every match will claim to be part of a /24 match. Depends if you care showing that portion or not if that matters though.

teddyh 2y ago

> On the internet networks larger than /24s aren't considered valid advertisements The number 24 is larger, but the network is smaller.

zamadatix 2y ago
Good catch, thanks! This should have been "netmasks" instead of "networks" but it's too late for me to edit now.
- AStonesThrow 2y ago
  A netmask is different and deprecated terminology. The "/24" you refer to is a "prefix length", i.e. a network prefix being advertised by BGP.

riobard 2y ago

> fit the entire IP range in a single 32 bit value … only if you pretend IPv6 does not exist, which isn't the case in the original blogpost. But the idea can be extended to fit entire IP (both v4 and v6) subnets in an uint64, given that the minimal IPv6 prefix size to be globally routed is /48, you could use the first byte of the uint64 to mark the address type (e.g. 0x4 for IPv4 and 0x6 for IPv6), the remaining 3 (for IPv4) or 6 (for IPv6) bytes for actual prefix, and the last byte for prefix length.

blibble 2y ago

for ipv4 you can do with with just a single lookup, so real O(1) store the entire thing in one big array, indexed by the uint24 value of the /24 so ASN for 0.0.0.0 stored in position 0, ASN for 0.0.1.0 stored in position 1, etc and you can drop 0.0.0.0/8, 10.0.0.0/8, 127.0.0.0/8, 224.0.0.0/4, 240.0.0.0/24 to save 35 /8s (256-16-16-3)256256*4 bytes needed -> 55mb mmap it if necessary

zamadatix 2y ago
If you do it this way I think you lose all of the prefix size info I.e. every match will claim to be part of a /24 match. Depends if you care showing that portion or not if that matters though.