bart

package module
v0.8.2 Latest Latest
Warning

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

 Go to latest Published: May 14, 2024 License: MIT Imports: 11 Imported by: 2

README

package bart

Go Reference GitHub release (latest SemVer) CI Coverage Status Stand With Ukraine

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

Documentation

Index

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.

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 (*Table[V]) All added in v0.6.0 

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

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 

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

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]) All6 added in v0.6.0 

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

All6, like Table.All 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 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.

The prefix must already be normalized!

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

The prefix must already be normalized!

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.

The prefix must already be normalized!

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

The prefix must already be normalized!

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.

The prefix must already be normalized!

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 

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 matches a route in the other table.

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 matches a route in the table.

The prefix must be normalized!

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

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

Size, calculates the IPv4 and IPv6 prefixes and returns the sum. You could also calculate it using All(), but this would be slower in any case and therefore qualifies Size() as an independent method.

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

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

Size4 calculates the number of IPv4 prefixes. You could also calculate it using All4(), but this would be slower in any case and therefore qualifies Size4() as an independent method.

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

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

Size6 calculates the number of IPv6 prefixes. You could also calculate it using All6(), but this would be slower in any case and therefore qualifies Size6() as an independent method.

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) []netip.Prefix

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

The prefix must already be normalized!

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

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

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

The prefix must already be normalized!

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 value is taken from the other table.

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

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.

The prefix must already be normalized!

Source Files

View all Source files

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.