bart

README

package bart

ATTENTION: API change

The API has changed since v0.4.2 !!!

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, using the baseIndex function from the ART algorithm to build the complete binary prefix tree (CBT) for each stride. The stride has a fixed length of 8 bits.

The second key factor is popcount array compression at each stride level and backtracking along the CBT prefix tree in O(k).

The CBT is implemented as a bitvector, backtracking is just a matter of fast cache friendly bitmask operations.

Due to the cache locality of the popcount compressed CBT, the backtracking algorithm is as fast as possible.

API

The API has changed since v0.4.2

  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]) Walk(cb func(pfx netip.Prefix, val V) error) error
  func (t *Table[V]) Walk4(cb func(pfx netip.Prefix, val V) error) error
  func (t *Table[V]) Walk6(cb func(pfx netip.Prefix, val V) error) error

  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             29107173         41.22 ns/op
BenchmarkFullMatchV4/LookupPrefix       24154027         49.73 ns/op
BenchmarkFullMatchV4/LookupPrefixLPM    21278923         56.34 ns/op

BenchmarkFullMatchV6/Lookup             28551670         42.03 ns/op
BenchmarkFullMatchV6/LookupPrefix       23813694         50.38 ns/op
BenchmarkFullMatchV6/LookupPrefixLPM    21109486         56.82 ns/op

BenchmarkFullMissV4/Lookup              21568196         56.01 ns/op
BenchmarkFullMissV4/LookupPrefix        18887606         63.51 ns/op
BenchmarkFullMissV4/LookupPrefixLPM     17191287         69.82 ns/op

BenchmarkFullMissV6/Lookup              18382587         65.18 ns/op
BenchmarkFullMissV6/LookupPrefix        15761524         76.13 ns/op
BenchmarkFullMissV6/LookupPrefixLPM     14565033         82.41 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]) 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
  • func (t *Table[V]) Walk(cb func(pfx netip.Prefix, val V) error) error
  • func (t *Table[V]) Walk4(cb func(pfx netip.Prefix, val V) error) error
  • func (t *Table[V]) Walk6(cb func(pfx netip.Prefix, val V) error) error

Examples

• Table.Lookup
• Table.Walk4

Types

type DumpListNode

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]) Clone

func (t *Table[V]) Clone() *Table[V]

Clone returns a copy of the routing table. The payloads V are copied using assignment, so this is a shallow clone.

func (*Table[V]) Delete

func (t *Table[V]) Delete(pfx netip.Prefix)

Delete removes pfx from the tree, pfx does not have to be present.

func (*Table[V]) DumpList4

func (t *Table[V]) DumpList4() []DumpListNode[V]

DumpList4 dumps ipv4 tree into list of roots and their subnets. It can be used to analyze tree or build custom json representation.

func (*Table[V]) DumpList6

func (t *Table[V]) DumpList6() []DumpListNode[V]

DumpList6 dumps ipv4 tree into list of roots and their subnets. It can be used to analyze tree or build custom json representation.

func (*Table[V]) Fprint

func (t *Table[V]) Fprint(w io.Writer) error

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

func (t *Table[V]) Get(pfx netip.Prefix) (val V, ok bool)

Get returns the associated payload for prefix and true, or false if prefix is not set in the routing table.

func (*Table[V]) Insert

func (t *Table[V]) Insert(pfx netip.Prefix, val V)

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

func (t *Table[V]) Lookup(ip netip.Addr) (val V, ok bool)

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

func (t *Table[V]) LookupPrefix(pfx netip.Prefix) (val V, ok bool)

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

func (t *Table[V]) LookupPrefixLPM(pfx netip.Prefix) (lpm netip.Prefix, val V, ok bool)

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

func (t *Table[V]) MarshalJSON() ([]byte, error)

MarshalJSON dumps table into two sorted lists: for ipv4 and ipv6. Every root and subnet are array, not map, because the order matters.

func (*Table[V]) MarshalText

func (t *Table[V]) MarshalText() ([]byte, error)

MarshalText implements the encoding.TextMarshaler interface, just a wrapper for Table.Fprint.

func (*Table[V]) Overlaps

func (t *Table[V]) Overlaps(o *Table[V]) bool

Overlaps reports whether any IP in the table matches a route in the other table.

func (*Table[V]) OverlapsPrefix

func (t *Table[V]) OverlapsPrefix(pfx netip.Prefix) bool

OverlapsPrefix reports whether any IP in pfx matches a route in the table.

func (*Table[V]) String

func (t *Table[V]) String() 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

func (t *Table[V]) Subnets(pfx netip.Prefix) []netip.Prefix

Subnets, return all prefixes covered by pfx in natural CIDR sort order.

func (*Table[V]) Supernets

func (t *Table[V]) Supernets(pfx netip.Prefix) []netip.Prefix

Supernets, return all matching routes for pfx, in natural CIDR sort order.

func (*Table[V]) Union

func (t *Table[V]) Union(o *Table[V])

Union combines two tables, changing the receiver table. If there are duplicate entries, the value is taken from the other table.

func (*Table[V]) Update

func (t *Table[V]) Update(pfx netip.Prefix, cb func(val V, ok bool) V) V

Update or set the value at pfx with a callback function. The callback function is called with (value, ok) and returns a new value..

If the pfx does not already exist, it is set with the new value.

func (*Table[V]) Walk

func (t *Table[V]) Walk(cb func(pfx netip.Prefix, val V) error) error

Walk runs through the routing table and calls the cb function for each route entry with prefix and value. If the cb function returns an error, the walk ends prematurely and the error is propagated.

Prefixes must not be inserted or deleted by the callback function, otherwise the behavior is undefined. However, value updates are permitted.

The walk order is not specified and is not part of the public interface, you must not rely on it.

func (*Table[V]) Walk4

func (t *Table[V]) Walk4(cb func(pfx netip.Prefix, val V) error) error

Walk4, like Table.Walk 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.Walk4(func(pfx netip.Prefix, val netip.Addr) error {
		fmt.Printf("%v\t%v\n", pfx, val)
		return nil
	})

}

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]) Walk6

func (t *Table[V]) Walk6(cb func(pfx netip.Prefix, val V) error) error

Walk6, like Table.Walk but only for the v6 routing table.