README
¶
package bart
ATTENTION: API change!!!
API change, Walk() got a signature change and renamed to All(), ready for range-over-func iterations.
Overview
package bart provides a Balanced-Routing-Table (BART).
BART is balanced in terms of memory consumption versus lookup time.
The lookup time is by a factor of ~2 slower on average as the routing algorithms ART, SMART, CPE, ... but reduces the memory consumption by an order of magnitude in comparison.
BART is a multibit-trie with fixed stride length of 8 bits, using the baseIndex function from the ART algorithm to build the complete-binary-tree (CBT) of prefixes for each stride.
The second key factor is popcount array compression at each stride level of the CBT prefix tree and backtracking along the CBT in O(k).
The CBT is implemented as a bitvector, backtracking is just a matter of fast cache friendly bitmask operations.
The child array at each stride level is also popcount compressed.
API
The API has changed since v0.4.2 and 0.5.3.
import "github.com/gaissmai/bart"
type Table[V any] struct {
// Has unexported fields.
}
Table is an IPv4 and IPv6 routing table with payload V. The zero value is
ready to use.
The Table is safe for concurrent readers but not for concurrent readers
and/or writers.
func (t *Table[V]) Insert(pfx netip.Prefix, val V)
func (t *Table[V]) Delete(pfx netip.Prefix)
func (t *Table[V]) Get(pfx netip.Prefix) (val V, ok bool)
func (t *Table[V]) Update(pfx netip.Prefix, cb func(val V, ok bool) V) V
func (t *Table[V]) Union(o *Table[V])
func (t *Table[V]) Clone() *Table[V]
func (t *Table[V]) Lookup(ip netip.Addr) (val V, ok bool)
func (t *Table[V]) LookupPrefix(pfx netip.Prefix) (val V, ok bool)
func (t *Table[V]) LookupPrefixLPM(pfx netip.Prefix) (lpm netip.Prefix, val V, ok bool)
func (t *Table[V]) Subnets(pfx netip.Prefix) []netip.Prefix
func (t *Table[V]) Supernets(pfx netip.Prefix) []netip.Prefix
func (t *Table[V]) Overlaps(o *Table[V]) bool
func (t *Table[V]) OverlapsPrefix(pfx netip.Prefix) bool
func (t *Table[V]) String() string
func (t *Table[V]) Fprint(w io.Writer) error
func (t *Table[V]) MarshalText() ([]byte, error)
func (t *Table[V]) MarshalJSON() ([]byte, error)
func (t *Table[V]) All(yield func(pfx netip.Prefix, val V) bool) bool
func (t *Table[V]) All4(yield func(pfx netip.Prefix, val V) bool) bool
func (t *Table[V]) All6(yield func(pfx netip.Prefix, val V) bool) bool
func (t *Table[V]) DumpList4() []DumpListNode[V]
func (t *Table[V]) DumpList6() []DumpListNode[V]
benchmarks
Please see the extensive benchmarks comparing bart with other IP routing table implementations.
Just a teaser, LPM lookups against the full Internet routing table with random probes:
cpu: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
BenchmarkFullMatchV4/Lookup 28140715 41.95 ns/op
BenchmarkFullMatchV4/LookupPrefix 24648212 48.73 ns/op
BenchmarkFullMatchV4/LookupPrefixLPM 21412228 56.06 ns/op
BenchmarkFullMatchV6/Lookup 29225397 41.06 ns/op
BenchmarkFullMatchV6/LookupPrefix 24992281 48.01 ns/op
BenchmarkFullMatchV6/LookupPrefixLPM 21743133 55.25 ns/op
BenchmarkFullMissV4/Lookup 15246050 78.84 ns/op
BenchmarkFullMissV4/LookupPrefix 13382380 89.76 ns/op
BenchmarkFullMissV4/LookupPrefixLPM 12887918 93.09 ns/op
BenchmarkFullMissV6/Lookup 69248640 17.31 ns/op
BenchmarkFullMissV6/LookupPrefix 51542642 23.29 ns/op
BenchmarkFullMissV6/LookupPrefixLPM 48444040 24.79 ns/op
CONTRIBUTION
Please open an issue for discussion before sending a pull request.
CREDIT
Credits for many inspirations go to the clever guys at tailscale, to Daniel Lemire for the super-fast bitset package and to Donald E. Knuth for the ART routing algorithm and all the rest of his Art and for keeping important algorithms in the public domain!
LICENSE
MIT
Documentation
¶
Index ¶
- type DumpListNode
- type Table
- func (t *Table[V]) All(yield func(pfx netip.Prefix, val V) bool)
- func (t *Table[V]) All4(yield func(pfx netip.Prefix, val V) bool)
- func (t *Table[V]) All6(yield func(pfx netip.Prefix, val V) bool)
- func (t *Table[V]) Clone() *Table[V]
- func (t *Table[V]) Delete(pfx netip.Prefix)
- func (t *Table[V]) DumpList4() []DumpListNode[V]
- func (t *Table[V]) DumpList6() []DumpListNode[V]
- func (t *Table[V]) Fprint(w io.Writer) error
- func (t *Table[V]) Get(pfx netip.Prefix) (val V, ok bool)
- func (t *Table[V]) Insert(pfx netip.Prefix, val V)
- func (t *Table[V]) Lookup(ip netip.Addr) (val V, ok bool)
- func (t *Table[V]) LookupPrefix(pfx netip.Prefix) (val V, ok bool)
- func (t *Table[V]) LookupPrefixLPM(pfx netip.Prefix) (lpm netip.Prefix, val V, ok bool)
- func (t *Table[V]) MarshalJSON() ([]byte, error)
- func (t *Table[V]) MarshalText() ([]byte, error)
- func (t *Table[V]) Overlaps(o *Table[V]) bool
- func (t *Table[V]) OverlapsPrefix(pfx netip.Prefix) bool
- func (t *Table[V]) String() string
- func (t *Table[V]) Subnets(pfx netip.Prefix) []netip.Prefix
- func (t *Table[V]) Supernets(pfx netip.Prefix) []netip.Prefix
- func (t *Table[V]) Union(o *Table[V])
- func (t *Table[V]) Update(pfx netip.Prefix, cb func(val V, ok bool) V) V
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type DumpListNode ¶ added in v0.1.6
type DumpListNode[V any] struct { CIDR netip.Prefix `json:"cidr"` Value V `json:"value"` Subnets []DumpListNode[V] `json:"subnets,omitempty"` }
DumpListNode contains CIDR, value and list of subnets (tree childrens).
type Table ¶
type Table[V any] struct { // contains filtered or unexported fields }
Table is an IPv4 and IPv6 routing table with payload V. The zero value is ready to use.
The Table is safe for concurrent readers but not for concurrent readers and/or writers.
func (*Table[V]) All ¶ added in v0.6.0
All may be used in a for/range loop to iterate through all the prefixes.
Prefixes must not be inserted or deleted during iteration, otherwise the behavior is undefined. However, value updates are permitted.
The iteration order is not specified and is not part of the public interface, you must not rely on it.
func (*Table[V]) All4 ¶ added in v0.6.0
All4, like Table.All but only for the v4 routing table.
Example ¶
package main
import (
"fmt"
"net/netip"
"github.com/gaissmai/bart"
)
var (
a = netip.MustParseAddr
p = netip.MustParsePrefix
)
var input = []struct {
cidr netip.Prefix
nextHop netip.Addr
}{
{p("fe80::/10"), a("::1%lo")},
{p("172.16.0.0/12"), a("8.8.8.8")},
{p("10.0.0.0/24"), a("8.8.8.8")},
{p("::1/128"), a("::1%eth0")},
{p("192.168.0.0/16"), a("9.9.9.9")},
{p("10.0.0.0/8"), a("9.9.9.9")},
{p("::/0"), a("2001:db8::1")},
{p("10.0.1.0/24"), a("10.0.0.0")},
{p("169.254.0.0/16"), a("10.0.0.0")},
{p("2000::/3"), a("2001:db8::1")},
{p("2001:db8::/32"), a("2001:db8::1")},
{p("127.0.0.0/8"), a("127.0.0.1")},
{p("127.0.0.1/32"), a("127.0.0.1")},
{p("192.168.1.0/24"), a("127.0.0.1")},
}
func main() {
rtbl := new(bart.Table[netip.Addr])
for _, item := range input {
rtbl.Insert(item.cidr, item.nextHop)
}
rtbl.All4(func(pfx netip.Prefix, val netip.Addr) bool {
fmt.Printf("%v\t%v\n", pfx, val)
return true
})
}
Output: 10.0.0.0/8 9.9.9.9 127.0.0.0/8 127.0.0.1 10.0.0.0/24 8.8.8.8 10.0.1.0/24 10.0.0.0 127.0.0.1/32 127.0.0.1 169.254.0.0/16 10.0.0.0 172.16.0.0/12 8.8.8.8 192.168.0.0/16 9.9.9.9 192.168.1.0/24 127.0.0.1
func (*Table[V]) Clone ¶ added in v0.4.0
Clone returns a copy of the routing table. The payloads V are copied using assignment, so this is a shallow clone.
func (*Table[V]) DumpList4 ¶ added in v0.5.0
func (t *Table[V]) DumpList4() []DumpListNode[V]
DumpList4 dumps the ipv4 tree into a list of roots and their subnets. It can be used to analyze the tree or build custom json representation.
func (*Table[V]) DumpList6 ¶ added in v0.5.0
func (t *Table[V]) DumpList6() []DumpListNode[V]
DumpList6 dumps the ipv6 tree into a list of roots and their subnets. It can be used to analyze the tree or build custom json representation.
func (*Table[V]) Fprint ¶
Fprint writes a hierarchical tree diagram of the ordered CIDRs to w. If w is nil, Fprint panics.
The order from top to bottom is in ascending order of the prefix address and the subtree structure is determined by the CIDRs coverage.
▼ ├─ 10.0.0.0/8 (9.9.9.9) │ ├─ 10.0.0.0/24 (8.8.8.8) │ └─ 10.0.1.0/24 (10.0.0.0) ├─ 127.0.0.0/8 (127.0.0.1) │ └─ 127.0.0.1/32 (127.0.0.1) ├─ 169.254.0.0/16 (10.0.0.0) ├─ 172.16.0.0/12 (8.8.8.8) └─ 192.168.0.0/16 (9.9.9.9) └─ 192.168.1.0/24 (127.0.0.1) ▼ └─ ::/0 (2001:db8::1) ├─ ::1/128 (::1%eth0) ├─ 2000::/3 (2001:db8::1) │ └─ 2001:db8::/32 (2001:db8::1) └─ fe80::/10 (::1%lo)
func (*Table[V]) Get ¶
Get returns the associated payload for prefix and true, or false if prefix is not set in the routing table.
func (*Table[V]) Insert ¶
Insert adds pfx to the tree, with value val. If pfx is already present in the tree, its value is set to val.
func (*Table[V]) Lookup ¶
Lookup does a route lookup (longest prefix match) for IP and returns the associated value and true, or false if no route matched.
Example ¶
package main
import (
"fmt"
"net/netip"
"os"
"github.com/gaissmai/bart"
)
var (
a = netip.MustParseAddr
p = netip.MustParsePrefix
)
var input = []struct {
cidr netip.Prefix
nextHop netip.Addr
}{
{p("fe80::/10"), a("::1%lo")},
{p("172.16.0.0/12"), a("8.8.8.8")},
{p("10.0.0.0/24"), a("8.8.8.8")},
{p("::1/128"), a("::1%eth0")},
{p("192.168.0.0/16"), a("9.9.9.9")},
{p("10.0.0.0/8"), a("9.9.9.9")},
{p("::/0"), a("2001:db8::1")},
{p("10.0.1.0/24"), a("10.0.0.0")},
{p("169.254.0.0/16"), a("10.0.0.0")},
{p("2000::/3"), a("2001:db8::1")},
{p("2001:db8::/32"), a("2001:db8::1")},
{p("127.0.0.0/8"), a("127.0.0.1")},
{p("127.0.0.1/32"), a("127.0.0.1")},
{p("192.168.1.0/24"), a("127.0.0.1")},
}
func main() {
rtbl := new(bart.Table[netip.Addr])
for _, item := range input {
rtbl.Insert(item.cidr, item.nextHop)
}
rtbl.Fprint(os.Stdout)
fmt.Println()
ip := a("42.0.0.0")
value, ok := rtbl.Lookup(ip)
fmt.Printf("Lookup: %-20v value: %11v, ok: %v\n", ip, value, ok)
ip = a("10.0.1.17")
value, ok = rtbl.Lookup(ip)
fmt.Printf("Lookup: %-20v value: %11v, ok: %v\n", ip, value, ok)
ip = a("2001:7c0:3100:1::111")
value, ok = rtbl.Lookup(ip)
fmt.Printf("Lookup: %-20v value: %11v, ok: %v\n", ip, value, ok)
}
Output: ▼ ├─ 10.0.0.0/8 (9.9.9.9) │ ├─ 10.0.0.0/24 (8.8.8.8) │ └─ 10.0.1.0/24 (10.0.0.0) ├─ 127.0.0.0/8 (127.0.0.1) │ └─ 127.0.0.1/32 (127.0.0.1) ├─ 169.254.0.0/16 (10.0.0.0) ├─ 172.16.0.0/12 (8.8.8.8) └─ 192.168.0.0/16 (9.9.9.9) └─ 192.168.1.0/24 (127.0.0.1) ▼ └─ ::/0 (2001:db8::1) ├─ ::1/128 (::1%eth0) ├─ 2000::/3 (2001:db8::1) │ └─ 2001:db8::/32 (2001:db8::1) └─ fe80::/10 (::1%lo) Lookup: 42.0.0.0 value: invalid IP, ok: false Lookup: 10.0.1.17 value: 10.0.0.0, ok: true Lookup: 2001:7c0:3100:1::111 value: 2001:db8::1, ok: true
func (*Table[V]) LookupPrefix ¶ added in v0.5.0
LookupPrefix does a route lookup (longest prefix match) for pfx and returns the associated value and true, or false if no route matched.
func (*Table[V]) LookupPrefixLPM ¶ added in v0.5.0
LookupPrefixLPM is similar to Table.LookupPrefix, but it returns the lpm prefix in addition to value,ok.
This method is about 20-30% slower than LookupPrefix and should only be used if the matching lpm entry is also required for other reasons.
If LookupPrefixLPM is to be used for IP addresses, they must be converted to /32 or /128 prefixes.
func (*Table[V]) MarshalJSON ¶ added in v0.1.6
MarshalJSON dumps the table into two sorted lists: for ipv4 and ipv6. Every root and subnet is an array, not a map, because the order matters.
func (*Table[V]) MarshalText ¶ added in v0.1.5
MarshalText implements the encoding.TextMarshaler interface, just a wrapper for Table.Fprint.
func (*Table[V]) Overlaps ¶ added in v0.2.0
Overlaps reports whether any IP in the table matches a route in the other table.
func (*Table[V]) OverlapsPrefix ¶ added in v0.1.5
OverlapsPrefix reports whether any IP in pfx matches a route in the table.
func (*Table[V]) String ¶
String returns a hierarchical tree diagram of the ordered CIDRs as string, just a wrapper for Table.Fprint. If Fprint returns an error, String panics.
func (*Table[V]) Subnets ¶ added in v0.5.0
Subnets, return all prefixes covered by pfx in natural CIDR sort order.
func (*Table[V]) Supernets ¶ added in v0.5.0
Supernets, return all matching routes for pfx, in natural CIDR sort order.
func (*Table[V]) Union ¶ added in v0.3.0
Union combines two tables, changing the receiver table. If there are duplicate entries, the value is taken from the other table.
Source Files