211 lines
8.1 KiB
Markdown
211 lines
8.1 KiB
Markdown
# package bart
|
|
|
|
|
|
[](https://pkg.go.dev/github.com/gaissmai/bart#section-documentation)
|
|
[](https://github.com/avelino/awesome-go)
|
|
[](https://github.com/gaissmai/bart/actions/workflows/go.yml)
|
|
[](https://coveralls.io/github/gaissmai/bart)
|
|
[](https://goreportcard.com/report/github.com/gaissmai/bart)
|
|
[](https://opensource.org/licenses/MIT)
|
|
[](https://stand-with-ukraine.pp.ua)
|
|
|
|
## 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 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
|
|
comparable or even better lookup times for longest prefix match.
|
|
|
|
The algorithm is also excellent for determining whether two tables
|
|
contain overlapping IP addresses.
|
|
|
|
## Example
|
|
|
|
```golang
|
|
func ExampleTable_Contains() {
|
|
// Create a new routing table
|
|
table := new(bart.Table[struct{}])
|
|
|
|
// Insert some prefixes
|
|
prefixes := []string{
|
|
"192.168.0.0/16", // corporate
|
|
"192.168.1.0/24", // department
|
|
"2001:7c0:3100::/40", // corporate
|
|
"2001:7c0:3100:1::/64", // department
|
|
"fc00::/7", // unique local
|
|
}
|
|
|
|
for _, s := range prefixes {
|
|
pfx := netip.MustParsePrefix(s)
|
|
table.Insert(pfx, struct{}{})
|
|
}
|
|
|
|
// Test some IP addresses for black/whitelist containment
|
|
ips := []string{
|
|
"192.168.1.100", // must match, department
|
|
"192.168.2.1", // must match, corporate
|
|
"2001:7c0:3100:1::1", // must match, department
|
|
"2001:7c0:3100:2::1", // must match, corporate
|
|
"fc00::1", // must match, unique local
|
|
//
|
|
"172.16.0.1", // must NOT match
|
|
"2003:dead:beef::1", // must NOT match
|
|
}
|
|
|
|
for _, s := range ips {
|
|
ip := netip.MustParseAddr(s)
|
|
fmt.Printf("%-20s is contained: %t\n", ip, table.Contains(ip))
|
|
}
|
|
|
|
// Output:
|
|
// 192.168.1.100 is contained: true
|
|
// 192.168.2.1 is contained: true
|
|
// 2001:7c0:3100:1::1 is contained: true
|
|
// 2001:7c0:3100:2::1 is contained: true
|
|
// fc00::1 is contained: true
|
|
// 172.16.0.1 is contained: false
|
|
// 2003:dead:beef::1 is contained: false
|
|
}
|
|
```
|
|
## API
|
|
|
|
Release v0.18 requires at least go1.23 and we use the `iter.Seq2[netip.Prefix, V]` types for iterators.
|
|
The lock-free versions of insert, update and delete are added, but still experimentell.
|
|
|
|
```golang
|
|
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. Either the update operations must be protected by an
|
|
external lock mechanism or the various ...Persist functions must be used
|
|
which return a modified routing table by leaving the original unchanged
|
|
|
|
A Table must not be copied by value, see Table.Clone.
|
|
|
|
func (t *Table[V]) Insert(pfx netip.Prefix, val V)
|
|
func (t *Table[V]) Delete(pfx netip.Prefix)
|
|
func (t *Table[V]) Update(pfx netip.Prefix, cb func(val V, ok bool) V) (newVal V)
|
|
|
|
func (t *Table[V]) InsertPersist(pfx netip.Prefix, val V) *Table[V]
|
|
func (t *Table[V]) DeletePersist(pfx netip.Prefix) *Table[V]
|
|
func (t *Table[V]) UpdatePersist(pfx netip.Prefix, cb func(val V, ok bool) V) (pt *Table[V], newVal V)
|
|
|
|
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]) GetAndDeletePersist(pfx netip.Prefix) (pt *Table[V], 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) iter.Seq2[netip.Prefix, V]
|
|
func (t *Table[V]) Supernets(pfx netip.Prefix) iter.Seq2[netip.Prefix, V]
|
|
|
|
func (t *Table[V]) All() iter.Seq2[netip.Prefix, V]
|
|
func (t *Table[V]) All4() iter.Seq2[netip.Prefix, V]
|
|
func (t *Table[V]) All6() iter.Seq2[netip.Prefix, V]
|
|
|
|
func (t *Table[V]) AllSorted() iter.Seq2[netip.Prefix, V]
|
|
func (t *Table[V]) AllSorted4() iter.Seq2[netip.Prefix, V]
|
|
func (t *Table[V]) AllSorted6() iter.Seq2[netip.Prefix, V]
|
|
|
|
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](https://github.com/gaissmai/iprbench) 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 55906228 21.39 ns/op 0 B/op 0 allocs/op
|
|
BenchmarkFullMatchV6/Contains 100000000 11.38 ns/op 0 B/op 0 allocs/op
|
|
BenchmarkFullMissV4/Contains 52927538 22.69 ns/op 0 B/op 0 allocs/op
|
|
BenchmarkFullMissV6/Contains 250386540 4.883 ns/op 0 B/op 0 allocs/op
|
|
PASS
|
|
ok github.com/gaissmai/bart 11.291s
|
|
|
|
goos: linux
|
|
goarch: amd64
|
|
pkg: github.com/gaissmai/bart
|
|
cpu: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
|
|
BenchmarkFullMatchV4/Lookup 53578766 21.77 ns/op 0 B/op 0 allocs/op
|
|
BenchmarkFullMatchV6/Lookup 57054618 21.07 ns/op 0 B/op 0 allocs/op
|
|
BenchmarkFullMissV4/Lookup 48289306 25.60 ns/op 0 B/op 0 allocs/op
|
|
BenchmarkFullMissV6/Lookup 142917571 8.387 ns/op 0 B/op 0 allocs/op
|
|
PASS
|
|
ok github.com/gaissmai/bart 10.455s
|
|
```
|
|
|
|
## 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 for his inspiring blog,
|
|
- to Donald E. Knuth for the **ART** routing algorithm and
|
|
- to Yoichi Hariguchi who deciphered it for us mere mortals
|
|
|
|
And last but not least to the Go team who do a wonderful job!
|
|
|
|
## LICENSE
|
|
|
|
MIT
|