README
¶
cidranger
Fast IP to CIDR block(s) lookup using trie in Golang, inspired by IPv4 route lookup linux. Possible use cases include detecting if a IP address is from published cloud provider CIDR blocks (e.g. 52.95.110.1 is contained in published AWS Route53 CIDR 52.95.110.0/24), IP routing rules, etc.
This is visualization of a trie storing CIDR blocks 128.0.0.0/2 192.0.0.0/2 200.0.0.0/5 without path compression, the 0/1 number on the path indicates the bit value of the IP address at specified bit position, hence the path from root node to a child node represents a CIDR block that contains all IP ranges of its children, and children's children.
Visualization of trie storing same CIDR blocks with path compression, improving both lookup speed and memory footprint.
Getting Started
Configure imports.
import (
"net"
"github.com/yl2chen/cidranger"
)
Create a new ranger implemented using Path-Compressed prefix trie.
ranger := NewPCTrieRanger()
Inserts CIDR blocks.
_, network1, _ := net.ParseCIDR("192.168.1.0/24")
_, network2, _ := net.ParseCIDR("128.168.1.0/24")
ranger.Insert(NewBasicRangerEntry(*network1))
ranger.Insert(NewBasicRangerEntry(*network2))
To attach any additional value(s) to the entry, simply create custom struct storing the desired value(s) that implements the RangerEntry interface:
type RangerEntry interface {
Network() net.IPNet
}
The prefix trie can be visualized as:
0.0.0.0/0 (target_pos:31:has_entry:false)
| 1--> 128.0.0.0/1 (target_pos:30:has_entry:false)
| | 0--> 128.168.1.0/24 (target_pos:7:has_entry:true)
| | 1--> 192.168.1.0/24 (target_pos:7:has_entry:true)
To test if given IP is contained in constructed ranger,
contains, err = ranger.Contains(net.ParseIP("128.168.1.0")) // returns true, nil
contains, err = ranger.Contains(net.ParseIP("192.168.2.0")) // returns false, nil
To get all the networks given is contained in,
containingNetworks, err = ranger.ContainingNetworks(net.ParseIP("128.168.1.0"))
To get all networks in ranger,
entries, err := ranger.CoveredNetworks(*AllIPv4) // for IPv4
entries, err := ranger.CoveredNetworks(*AllIPv6) // for IPv6
Benchmark
Compare hit/miss case for IPv4/IPv6 using PC trie vs brute force implementation, Ranger is initialized with published AWS ip ranges (889 IPv4 CIDR blocks and 360 IPv6)
// Ipv4 lookup hit scenario
BenchmarkPCTrieHitIPv4UsingAWSRanges-4 5000000 353 ns/op
BenchmarkBruteRangerHitIPv4UsingAWSRanges-4 100000 13719 ns/op
// Ipv6 lookup hit scenario, counter-intuitively faster then IPv4 due to less IPv6 CIDR
// blocks in the AWS dataset, hence the constructed trie has less path splits and depth.
BenchmarkPCTrieHitIPv6UsingAWSRanges-4 10000000 143 ns/op
BenchmarkBruteRangerHitIPv6UsingAWSRanges-4 300000 5178 ns/op
// Ipv4 lookup miss scenario
BenchmarkPCTrieMissIPv4UsingAWSRanges-4 20000000 96.5 ns/op
BenchmarkBruteRangerMissIPv4UsingAWSRanges-4 50000 24781 ns/op
// Ipv6 lookup miss scenario
BenchmarkPCTrieHMissIPv6UsingAWSRanges-4 10000000 115 ns/op
BenchmarkBruteRangerMissIPv6UsingAWSRanges-4 100000 10824 ns/op
Example of IPv6 trie:
::/0 (target_pos:127:has_entry:false)
| 0--> 2400::/14 (target_pos:113:has_entry:false)
| | 0--> 2400:6400::/22 (target_pos:105:has_entry:false)
| | | 0--> 2400:6500::/32 (target_pos:95:has_entry:false)
| | | | 0--> 2400:6500::/39 (target_pos:88:has_entry:false)
| | | | | 0--> 2400:6500:0:7000::/53 (target_pos:74:has_entry:false)
| | | | | | 0--> 2400:6500:0:7000::/54 (target_pos:73:has_entry:false)
| | | | | | | 0--> 2400:6500:0:7000::/55 (target_pos:72:has_entry:false)
| | | | | | | | 0--> 2400:6500:0:7000::/56 (target_pos:71:has_entry:true)
| | | | | | | | 1--> 2400:6500:0:7100::/56 (target_pos:71:has_entry:true)
| | | | | | | 1--> 2400:6500:0:7200::/56 (target_pos:71:has_entry:true)
| | | | | | 1--> 2400:6500:0:7400::/55 (target_pos:72:has_entry:false)
| | | | | | | 0--> 2400:6500:0:7400::/56 (target_pos:71:has_entry:true)
| | | | | | | 1--> 2400:6500:0:7500::/56 (target_pos:71:has_entry:true)
| | | | | 1--> 2400:6500:100:7000::/54 (target_pos:73:has_entry:false)
| | | | | | 0--> 2400:6500:100:7100::/56 (target_pos:71:has_entry:true)
| | | | | | 1--> 2400:6500:100:7200::/56 (target_pos:71:has_entry:true)
| | | | 1--> 2400:6500:ff00::/64 (target_pos:63:has_entry:true)
| | | 1--> 2400:6700:ff00::/64 (target_pos:63:has_entry:true)
| | 1--> 2403:b300:ff00::/64 (target_pos:63:has_entry:true)
Documentation
¶
Overview ¶
Package cidranger provides utility to store CIDR blocks and perform ip inclusion tests against it.
To create a new instance of the path-compressed trie:
ranger := NewPCTrieRanger()
To insert or remove an entry (any object that satisfies the RangerEntry interface):
_, network, _ := net.ParseCIDR("192.168.0.0/24")
ranger.Insert(NewBasicRangerEntry(*network))
ranger.Remove(network)
If you desire for any value to be attached to the entry, simply create custom struct that satisfies the RangerEntry interface:
type RangerEntry interface {
Network() net.IPNet
}
To test whether an IP is contained in the constructed networks ranger:
// returns bool, error
containsBool, err := ranger.Contains(net.ParseIP("192.168.0.1"))
To get a list of CIDR blocks in constructed ranger that contains IP:
// returns []RangerEntry, error
entries, err := ranger.ContainingNetworks(net.ParseIP("192.168.0.1"))
To get a list of all IPv4/IPv6 rangers respectively:
// returns []RangerEntry, error entries, err := ranger.CoveredNetworks(*AllIPv4) entries, err := ranger.CoveredNetworks(*AllIPv6)
Index ¶
Constants ¶
This section is empty.
Variables ¶
var AllIPv4 = parseCIDRUnsafe("0.0.0.0/0")
AllIPv4 is a IPv4 CIDR that contains all networks
var AllIPv6 = parseCIDRUnsafe("0::0/0")
AllIPv6 is a IPv6 CIDR that contains all networks
var ErrInvalidNetworkInput = fmt.Errorf("Invalid network input")
ErrInvalidNetworkInput is returned upon invalid network input.
var ErrInvalidNetworkNumberInput = fmt.Errorf("Invalid network number input")
ErrInvalidNetworkNumberInput is returned upon invalid network input.
Functions ¶
func NewBredthIter ¶ added in v1.1.0
func NewBredthIter(r Ranger) bredthRangerIter
A bredth-first iterator that returns all netblocks with a RangerEntry
func NewShallowBredthIter ¶ added in v1.1.0
func NewShallowBredthIter(r Ranger) bredthRangerIter
A bredth-first iterator that will return only the largest netblocks with an entry
Types ¶
type Ranger ¶
type Ranger interface {
// Insert a RangerEntry
Insert(entry RangerEntry) error
// Remove a network from the Ranger, returning its RangerEntry
Remove(network net.IPNet) (RangerEntry, error)
// ContainsNetwork returns true if the ip is covered in the Ranger
Contains(ip net.IP) (bool, error)
// ContainsNetwork returns true if the exact network is in the Ranger
ContainsNetwork(network net.IPNet) (bool, error)
// ContainingNetworks returns all RangerEntry that contain ip
ContainingNetworks(ip net.IP) ([]RangerEntry, error)
// CoveredNetworks returns all networks that are subnets of network
CoveredNetworks(network net.IPNet) ([]RangerEntry, error)
// Len returns number of entries in the Ranger
Len() int
// String returns a representation for visualization and debugging
String() string
// MissingNetworks determines the list of CIDR blocks out of the
// address space which are not contained in the Ranger
MissingNetworks() ([]net.IPNet, error)
}
Ranger is an interface for cidr block containment lookups.
func DoRollupApply ¶ added in v1.1.0
func DoRollupApply(r Ranger, f RollupApply) (Ranger, error)
Use a provided RollupApply and return the Ranger after modification
func NewIPv4PCTrieRanger ¶
func NewIPv4PCTrieRanger() Ranger
NewIPv4PCTrieRanger returns an IPv4-only Ranger for use-cases where the additional version checking and second Trie overhead is not desired.
func NewPCTrieRanger ¶
func NewPCTrieRanger() Ranger
NewPCTrieRanger returns a versionedRanger that supports both IPv4 and IPv6 using the path compressed trie implemention.
type RangerEntry ¶
RangerEntry is an interface for insertable entry into a Ranger.
func NewBasicRangerEntry ¶
func NewBasicRangerEntry(ipNet net.IPNet) RangerEntry
NewBasicRangerEntry returns a basic RangerEntry that only stores the network itself.
type RangerIter ¶ added in v1.1.0
type RangerIter interface {
Next() bool
Get() RangerEntry
Error() error
}
RangerIter is an interface to use with an iterator-like pattern ri := NewBredthIter(ptrie)
for ri.Next() {
entry := ri.Get()
...
}
if err := ri.Error(); err != nil {
...
}
While it's not really an iterator, this is exactly what bufio.Scanner does. Basically the idea is to have an Error() method which you call after iteration is complete to see whether iteration terminated because it was done or because an error was encountered midway through.
type RollupApply ¶ added in v1.1.0
type RollupApply interface {
// Decides if siblings should be rolled up
CanRollup(child0 RangerEntry, child1 RangerEntry) bool
// Rolls up siblings into a parent entry
GetParentEntry(child0 RangerEntry, child1 RangerEntry, parentNet net.IPNet) RangerEntry
}
Rollup apply Insert an entry at the parent of one or two children with entries, where the RangerEntry objects at those children meet the criteria of a rollup function
Source Files
Directories