Help us shape the future of Go! Take the 2026 Go Developer Survey

bart

package module
v0.17.2 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jan 7, 2025 License: MIT Imports: 11 Imported by: 66

README

package bart

GitHub release (latest SemVer) Go Reference Mentioned in Awesome Go CI Coverage Status Go Report Card Stand With Ukraine

Overview

package bart provides a Balanced-Routing-Table (BART).

BART is balanced in terms of memory usage and lookup time for the longest-prefix match.

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.

example 4bit stride
example from artlookup.pdf for a 4bit stride

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

The Table is implemented with popcount compressed sparse arrays together with path compression. This reduces storage consumption by almost two orders of magnitude in comparison to ART with similar lookup times for the longest prefix match.

API

The API has changed in ..., v0.10.1, v0.11.0, v0.12.0, v0.12.6, v0.16.0

  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]) Update(pfx netip.Prefix, cb func(val V, ok bool) V) (newVal 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]) GetAndDelete(pfx netip.Prefix) (val V, ok bool)

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

  func (t *Table[V]) Contains(ip netip.Addr) bool
  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]) OverlapsPrefix(pfx netip.Prefix) bool

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

  func (t *Table[V]) Subnets(pfx netip.Prefix)   func(yield func(netip.Prefix, V) bool)
  func (t *Table[V]) Supernets(pfx netip.Prefix) func(yield func(netip.Prefix, V) bool)

  func (t *Table[V]) All()  func(yield func(pfx netip.Prefix, val V) bool)
  func (t *Table[V]) All4() func(yield func(pfx netip.Prefix, val V) bool)
  func (t *Table[V]) All6() func(yield func(pfx netip.Prefix, val V) bool)

  func (t *Table[V]) AllSorted()  func(yield func(pfx netip.Prefix, val V) bool)
  func (t *Table[V]) AllSorted4() func(yield func(pfx netip.Prefix, val V) bool)
  func (t *Table[V]) AllSorted6() func(yield func(pfx netip.Prefix, val V) bool)

  func (t *Table[V]) Size()  int
  func (t *Table[V]) Size4() int
  func (t *Table[V]) Size6() int

  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]) 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, Contains and Lookups against the full Internet routing table with random IP address probes:

goos: linux
goarch: amd64
pkg: github.com/gaissmai/bart
cpu: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
BenchmarkFullMatchV4/Contains         	38003740	        27.69 ns/op
BenchmarkFullMatchV6/Contains         	49389355	        23.00 ns/op
BenchmarkFullMissV4/Contains          	42902048	        26.57 ns/op
BenchmarkFullMissV6/Contains          	128219610	         9.375 ns/op
PASS
ok  	github.com/gaissmai/bart	12.195s

goos: linux
goarch: amd64
pkg: github.com/gaissmai/bart
cpu: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
BenchmarkFullMatchV4/Lookup         	37453425	        30.55 ns/op
BenchmarkFullMatchV6/Lookup         	36819931	        30.48 ns/op
BenchmarkFullMissV4/Lookup          	37223881	        30.70 ns/op
BenchmarkFullMissV6/Lookup          	94333762	        12.32 ns/op
PASS
ok  	github.com/gaissmai/bart	11.215s

Compatibility Guarantees

The package is currently released as a pre-v1 version, which gives the author the freedom to break backward compatibility to help improve the API as he learns which initial design decisions would need to be revisited to better support the use cases that the library solves for.

These occurrences are expected to be rare in frequency and the API is already quite stable.

CONTRIBUTION

Please open an issue for discussion before sending a pull request.

CREDIT

Standing on the shoulders of giants.

Credits for many inspirations go to

  • the clever guys at tailscale,
  • to Daniel Lemire, 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!

And last but not least to the Go team who do a wonderful job!

LICENSE

MIT

Documentation

Overview

package bart provides a Balanced-Routing-Table (BART).

BART is balanced in terms of memory usage and lookup time for the longest-prefix match.

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 CBT is implemented as a bit-vector, backtracking is just a matter of fast cache friendly bitmask operations.

The routing table is implemented with popcount compressed sparse arrays together with path compression. This reduces storage consumption by almost two orders of magnitude in comparison to ART with similar lookup times for the longest prefix match.

Index

Examples

Constants

View Source 
const (
	UNKNOWN nodeType // logic error
)

Variables

This section is empty.

Functions

This section is empty.

Types

type Cloner added in v0.12.1 

type Cloner[V any] interface {
	Clone() V
}

Cloner, if implemented by payload of type V the values are deeply copied during Table.Clone and Table.Union.

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 

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

All returns an iterator over key-value pairs from Table. The iteration order is not specified and is not guaranteed to be the same from one call to the next.

func (*Table[V]) All4 added in v0.6.0 

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

All4, like Table.All but only for the v4 routing table.

func (*Table[V]) All6 added in v0.6.0 

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

All6, like Table.All but only for the v6 routing table.

func (*Table[V]) AllSorted added in v0.11.0 

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

AllSorted returns an iterator over key-value pairs from Table2 in natural CIDR sort order.

func (*Table[V]) AllSorted4 added in v0.12.6 

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

AllSorted4, like Table.AllSorted but only for the v4 routing table.

Example (Callback) 
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%eth0")},
	{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%lo")},
	{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("2000::")},
	{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.AllSorted4()(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
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
Example (Rangeoverfunc) 
rtbl := new(bart.Table[netip.Addr])
for _, item := range input {
	rtbl.Insert(item.cidr, item.nextHop)
}

for pfx, val := range rtbl.AllSorted4() {
	fmt.Printf("%v\t%v\n", pfx, val)
}

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

func (*Table[V]) AllSorted6 added in v0.12.6 

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

AllSorted6, like Table.AllSorted but only for the v6 routing table.

func (*Table[V]) Clone added in v0.4.0 

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

Clone returns a copy of the routing table. The payload of type V is shallow copied, but if type V implements the Cloner interface, the values are cloned.

func (*Table[V]) Contains added in v0.15.1 

func (t *Table[V]) Contains(ip netip.Addr) bool

Contains does a route lookup for IP and returns true if any route matched.

Contains does not return the value nor the prefix of the matching item, but as a test against a black- or whitelist it's often sufficient and even few nanoseconds faster than Table.Lookup.

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 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 

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

Fprint writes a hierarchical tree diagram of the ordered CIDRs with default formatted payload V 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 (V)
│  ├─ 10.0.0.0/24 (V)
│  └─ 10.0.1.0/24 (V)
├─ 127.0.0.0/8 (V)
│  └─ 127.0.0.1/32 (V)
├─ 169.254.0.0/16 (V)
├─ 172.16.0.0/12 (V)
└─ 192.168.0.0/16 (V)
   └─ 192.168.1.0/24 (V)
▼
└─ ::/0 (V)
   ├─ ::1/128 (V)
   ├─ 2000::/3 (V)
   │  └─ 2001:db8::/32 (V)
   └─ fe80::/10 (V)

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]) GetAndDelete added in v0.13.0 

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

GetAndDelete deletes the prefix and returns the associated payload for prefix and true, or the zero value and 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 given 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%eth0")},
	{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%lo")},
	{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("2000::")},
	{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 next-hop: %11v, ok: %v\n", ip, value, ok)

	ip = a("10.0.1.17")
	value, ok = rtbl.Lookup(ip)
	fmt.Printf("Lookup: %-20v next-hop: %11v, ok: %v\n", ip, value, ok)

	ip = a("2001:7c0:3100:1::111")
	value, ok = rtbl.Lookup(ip)
	fmt.Printf("Lookup: %-20v next-hop: %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%lo)
   ├─ 2000::/3 (2000::)
   │  └─ 2001:db8::/32 (2001:db8::1)
   └─ fe80::/10 (::1%eth0)

Lookup: 42.0.0.0             next-hop:  invalid IP, ok: false
Lookup: 10.0.1.17            next-hop:    10.0.0.0, ok: true
Lookup: 2001:7c0:3100:1::111 next-hop:      2000::, ok: true

func (*Table[V]) LookupPrefix added in v0.5.0 

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 added in v0.5.0 

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 address lookups, they must be converted to /32 or /128 prefixes.

func (*Table[V]) MarshalJSON added in v0.1.6 

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

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 

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

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

func (*Table[V]) Overlaps added in v0.2.0 

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

Overlaps reports whether any IP in the table is matched by a route in the other table or vice versa.

func (*Table[V]) Overlaps4 added in v0.10.1 

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

Overlaps4 reports whether any IPv4 in the table matches a route in the other table or vice versa.

func (*Table[V]) Overlaps6 added in v0.10.1 

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

Overlaps6 reports whether any IPv6 in the table matches a route in the other table or vice versa.

func (*Table[V]) OverlapsPrefix added in v0.1.5 

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

OverlapsPrefix reports whether any IP in pfx is matched by a route in the table or vice versa.

func (*Table[V]) Size added in v0.8.0 

func (t *Table[V]) Size() int

Size returns the prefix count.

func (*Table[V]) Size4 added in v0.8.0 

func (t *Table[V]) Size4() int

Size4 returns the IPv4 prefix count.

func (*Table[V]) Size6 added in v0.8.0 

func (t *Table[V]) Size6() int

Size6 returns the IPv6 prefix count.

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 added in v0.5.0 

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

Subnets returns an iterator over all CIDRs covered by pfx. The iteration is in natural CIDR sort order.

Example (Rangeoverfunc) 
rtbl := new(bart.Table[netip.Addr])
for _, item := range input {
	rtbl.Insert(item.cidr, item.nextHop)
}

cidr := netip.MustParsePrefix("0.0.0.0/1")

for pfx := range rtbl.Subnets(cidr) {
	fmt.Printf("%v\n", pfx)
}

Output:
10.0.0.0/8
10.0.0.0/24
10.0.1.0/24
127.0.0.0/8
127.0.0.1/32

func (*Table[V]) Supernets added in v0.5.0 

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

Supernets returns an iterator over all CIDRs covering pfx. The iteration is in reverse CIDR sort order, from longest-prefix-match to shortest-prefix-match.

Example (Rangeoverfunc) 
rtbl := new(bart.Table[netip.Addr])
for _, item := range input {
	rtbl.Insert(item.cidr, item.nextHop)
}

cidr := netip.MustParsePrefix("2001:db8::/32")

counter := 0
for pfx := range rtbl.Supernets(cidr) {
	fmt.Printf("%v\n", pfx)
	counter++
	if counter >= 2 {
		break
	}
}

Output:
2001:db8::/32
2000::/3

func (*Table[V]) Union added in v0.3.0 

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

Union combines two tables, changing the receiver table. If there are duplicate entries, the payload of type V is shallow copied from the other table. If type V implements the Cloner interface, the values are cloned, see also Table.Clone.

func (*Table[V]) Update added in v0.5.0 

func (t *Table[V]) Update(pfx netip.Prefix, cb func(val V, ok bool) V) (newVal 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.

Source Files

View all Source files

Directories

Path Synopsis
internal
bitset
Package bitset implements bitsets, a mapping between non-negative integers and boolean values.
 Package bitset implements bitsets, a mapping between non-negative integers and boolean values.
sparse
package sparse implements a generic sparse array with popcount compression.
 package sparse implements a generic sparse array with popcount compression.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.