gaissmai / bart Goto Github PK

The Balanced Routing Table is an adaptation of D. Knuth's ART algorithm combined with popcount level compression and backtracking. It is somewhat slower than ART, but requires considerably less memory.

License: MIT License

Go 100.00%

ip ipv6 cidr ip-routing longest-prefix-match art

bart's Introduction

package bart

ATTENTION: API change!!!

All prefixes as input parameters must be normalized!

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, 0.5.3. and v0.6.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.

    ATTENTION: The standard library net/netip doesn't enforce normalized
    prefixes, where the non-prefix bits are all zero.

    Since the conversion of a prefix into the normalized form is quite
    time-consuming relative to the other functions of the library, all prefixes
    must already be provided in normalized form as input parameters.

    If this is not the case, the behavior is undefined.
  
  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]) Size() int
  func (t *Table[V]) Size4() int
  func (t *Table[V]) Size6() int

  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]) 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, LPM lookups against the full Internet routing table with random probes:

goos: linux
goarch: amd64
pkg: github.com/gaissmai/bart
cpu: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz

BenchmarkFullMatchV4/Lookup                     24484828            49.03 ns/op
BenchmarkFullMatchV6/Lookup                     17098262            70.15 ns/op
BenchmarkFullMissV4/Lookup                      24480925            49.15 ns/op
BenchmarkFullMissV6/Lookup                      54955310            21.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

bart's People

Contributors

Stargazers

Watchers

Forkers

mieczkowski maisem tobez

bart's Issues

bart: memory aliasing issue in Union

(*Table).Union seems to result in shared memory between the receiving and other (*Table).

This results in unexpected side effects especially incases where some tables are computed once and then reused for the lifetime of the process. These tables end up getting mutated when unioned with other shorter lived tables.

I would have expected to not have any memory aliasing between the (*Table) apart from the values being shallow copied as described in the docs which doesn't matter for my use case as I am using Table[struct{}]

bart: remove sync.Once from Table?

The Table struct has a sync.Once, which when tested under sufficient load shows up in CPU profiles.

As the implementation isn't really thread safe anyways, can this be changed to a bool instead?

 // Table is an IPv4 and IPv6 routing table with payload V.
@@ -15,16 +14,18 @@ type Table[V any] struct {
 	rootV6 *node[V]
 
 	// simple API, no constructor needed
-	initOnce sync.Once
+	initOnce bool // set to true after first init
 }
 
 // init once, so no constructor is needed.
 func (t *Table[V]) init() {
-	t.initOnce.Do(func() {
-		// BitSets have to be initialized.
-		t.rootV4 = newNode[V]()
-		t.rootV6 = newNode[V]()
-	})
+	if t.initOnce {
+		return
+	}
+	// BitSets have to be initialized.
+	t.rootV4 = newNode[V]()
+	t.rootV6 = newNode[V]()
+	t.initOnce = true
 }
 
 // rootNodeByVersion, select root node for ip version.

bart: extend functionality to make it more useful for implementing a RIB

I am thinking about these new functions:

// Find exact match to pfx, or insert pfx.
// Returns pointer to value, and whether pfx was inserted.
func (t *Table[V]) FetchOrInsert(pfx netip.Prefix) (*V, bool) {...}

This will allow to perform modifications to existing values. Insert() can then be implemented like

func (t *Table[V]) Insert(pfx netip.Prefix, val V) {
	vp, _ := t.FetchOrInsert(pfx)
	*vp = val
}

// Find  like Lookup but by prefix
// Find does a route lookup for prefix and returns the longest prefix,
// pointer to the associated value and true for success, or false otherwise if
// no route matched.
func (t *Table[V]) Find(pfx netip.Prefix) (lpm netip.Prefix, pv *V, ok bool) {...}

// FindAll  Slice of all matching prefixes and pointers to their values, longest first
func (t *Table[V]) FindAll(pfx netip.Prefix) []struct { pfx netip.Prefix, pv *V }  {...}

I have a ready implementation for fetchOrInsert() but not for the others.

Suggest signature change to WalkXXX() to be compatible with rangefunc iterators

If one changes the WalkXXX() signatures to

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

they will become compatible with rangefunc experiment, and if the experiment is enabled (but likely a default one day), syntactic niceties like this become possible:

for pfx, val := range t.Walk {
    ...
}

What do you think?

When subnetwork is deleted from table lookup/get still reports individual IPs as present

When subnetwork is deleted from table lookup/get still reports individual IPs as present.

Maybe I misunderstand how to use this module correctly, below is an example test:

package main

import (
	"net/netip"
	"testing"

	"github.com/gaissmai/bart"
	"github.com/stretchr/testify/assert"
)

func mustParsePrefix(s string) netip.Prefix {
	pfx, err := netip.ParsePrefix(s)
	if err != nil {
		panic(err)
	}

	return pfx
}

func mustParseAddr(s string) netip.Addr {
	addr, err := netip.ParseAddr(s)
	if err != nil {
		panic(err)
	}

	return addr
}

func TestBART(t *testing.T) {
	var ok bool

	tbl := new(bart.Table[struct{}])

	{
		// 192.168.40.1 - 192.168.43.254
		tbl.Insert(mustParsePrefix("192.168.42.1/22"), struct{}{})

		_, _, ok = tbl.Lookup(mustParseAddr("192.168.40.1"))
		assert.True(t, ok)

		_, _, ok = tbl.Lookup(mustParseAddr("192.168.43.254"))
		assert.True(t, ok)

		_, _, ok = tbl.Lookup(mustParseAddr("192.168.42.242"))
		assert.True(t, ok)

		_, _, ok = tbl.Lookup(mustParseAddr("10.0.42.42"))
		assert.False(t, ok)
	}

	{
		tbl.Delete(mustParsePrefix("192.168.42.42/32"))

		_, _, ok = tbl.Lookup(mustParseAddr("192.168.40.1"))
		assert.True(t, ok)

		_, _, ok = tbl.Lookup(mustParseAddr("192.168.43.254"))
		assert.True(t, ok)

		_, _, ok = tbl.Lookup(mustParseAddr("192.168.42.42"))
		assert.False(t, ok)

		_, _, ok = tbl.Lookup(mustParseAddr("10.0.42.42"))
		assert.False(t, ok)
	}

	{
		// 192.168.42.1 - 192.168.42.254
		tbl.Delete(mustParsePrefix("192.168.42.1/24"))

		_, _, ok = tbl.Lookup(mustParseAddr("192.168.40.1"))
		assert.True(t, ok)

		_, _, ok = tbl.Lookup(mustParseAddr("192.168.43.254"))
		assert.True(t, ok)

		_, _, ok = tbl.Lookup(mustParseAddr("192.168.42.242"))
		assert.False(t, ok)

		_, _, ok = tbl.Lookup(mustParseAddr("10.0.42.42"))
		assert.False(t, ok)
	}
}