ipradix

package module
v0.0.0-...-b85a7ab Latest Latest
Warning

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

 Go to latest Published: Jun 16, 2026 License: MIT Imports: 4 Imported by: 0

README

ipradix

CI

ipradix is a generic, concurrency-safe IPv4 and IPv6 routing table for Go. It uses separate compressed Patricia radix trees for efficient longest-prefix lookups.

Features

  • IPv4 and IPv6 support
  • Longest-prefix matching with Find
  • All matching prefixes with FindAll
  • Multiple BGP routes per prefix
  • Atomic prefix replacement and route-level updates
  • Generic route metadata
  • Safe concurrent reads and writes
  • Automatic prefix and IPv4-mapped IPv6 normalization

Installation

go get github.com/kmatsoukas/ipradix

Longest-Prefix Match

The zero value of Table is ready to use:

package main

import (
	"fmt"
	"net/netip"

	"github.com/kmatsoukas/ipradix"
)

func main() {
	type WhoisInfo struct {
		NetName      string
		Organization string
		Registry     string
	}

	type Metadata struct {
		Country string
		Whois   WhoisInfo
	}

	var table ipradix.Table[Metadata]

	_ = table.Insert(ipradix.Prefix[Metadata]{
		Prefix: netip.MustParsePrefix("10.0.0.0/8"),
		Routes: []ipradix.Route[Metadata]{
			{
				ID:      1,
				NextHop: netip.MustParseAddr("192.0.2.1"),
				Metadata: Metadata{
					Country: "US",
					Whois: WhoisInfo{
						NetName:      "PRIVATE-ADDRESS-ABLK-RFC1918-IANA-RESERVED",
						Organization: "Internet Assigned Numbers Authority",
						Registry:     "ARIN",
					},
				},
			},
		},
	})

	_ = table.Insert(ipradix.Prefix[Metadata]{
		Prefix: netip.MustParsePrefix("10.20.0.0/16"),
		Routes: []ipradix.Route[Metadata]{
			{
				ID:      2,
				NextHop: netip.MustParseAddr("192.0.2.2"),
				Metadata: Metadata{
					Country: "US",
					Whois: WhoisInfo{
						NetName:      "EXAMPLE-CUSTOMER-NET",
						Organization: "Example Customer, Inc.",
						Registry:     "ARIN",
					},
				},
			},
		},
	})

	match, ok := table.Find(netip.MustParseAddr("10.20.30.40"))
	if ok {
		fmt.Println(match.Prefix)             // 10.20.0.0/16
		fmt.Println(match.Routes[0].NextHop) // 192.0.2.2
		fmt.Println(match.Routes[0].Metadata.Country) // US
	}
}

Find All Matches

FindAll returns matches from most specific to least specific:

matches := table.FindAll(netip.MustParseAddr("10.20.30.40"))
for _, match := range matches {
	fmt.Println(match.Prefix)
}

// 10.20.0.0/16
// 10.0.0.0/8

IPv4 and IPv6 entries can coexist in the same table:

var table ipradix.Table[Metadata]

_ = table.UpsertRoute(
	netip.MustParsePrefix("2001:db8::/32"),
	ipradix.Route[Metadata]{
		ID:      1,
		NextHop: netip.MustParseAddr("2001:db8::1"),
		Metadata: Metadata{
			Country: "US",
			Whois: WhoisInfo{
				NetName:      "DOCUMENTATION",
				Organization: "Internet Assigned Numbers Authority",
				Registry:     "ARIN",
			},
		},
	},
)

match, ok := table.Find(netip.MustParseAddr("2001:db8:42::10"))

BGP Route Attributes

Routes include common BGP attributes and caller-defined metadata:

type WhoisInfo struct {
	NetName      string
	Organization string
	Registry     string
}

type Metadata struct {
	Country string
	Whois   WhoisInfo
}

var table ipradix.Table[Metadata]

err := table.UpsertRoute(
	netip.MustParsePrefix("203.0.113.0/24"),
	ipradix.Route[Metadata]{
		ID:              1 << 32,
		RouterID:        netip.MustParseAddr("192.0.2.1"),
		NextHop:         netip.MustParseAddr("192.0.2.254"),
		PeerAS:          64512,
		OriginAS:        64496,
		ASPath:          []uint32{64512, 64496},
		Communities:     []uint32{100},
		LocalPreference: 100,
		MED:             50,
		Origin:          ipradix.OriginIGP,
		Metadata: Metadata{
			Country: "US",
			Whois: WhoisInfo{
				NetName:      "TEST-NET-3",
				Organization: "Internet Assigned Numbers Authority",
				Registry:     "ARIN",
			},
		},
	},
)
if err != nil {
	panic(err)
}

Route.ID is an opaque uint64 supplied by the caller. It must be nonzero, unique within a prefix, and stable across updates and withdrawals. The library does not interpret the ID or derive it from route attributes.

Applications that track routes from multiple observation sources can pack a 32-bit source ID and a 32-bit path ID into one route ID:

type SourceID uint32

func routeID(source SourceID, pathID uint32) uint64 {
	return uint64(source)<<32 | uint64(pathID)
}

The application owns source allocation and any registry that maps a source ID back to router or peer details. When BGP ADD-PATH is not in use, pathID can be zero as long as source is nonzero. Do not derive route IDs from mutable attributes such as the next hop, AS path, or communities.

Updating and Deleting Routes

UpsertRoute creates the prefix when necessary. For an existing prefix, it replaces a route with the same ID or appends a route with a new ID:

prefix := netip.MustParsePrefix("203.0.113.0/24")
id := routeID(1, 0)

_ = table.UpsertRoute(prefix, ipradix.Route[Metadata]{
	ID:      id,
	NextHop: netip.MustParseAddr("192.0.2.10"),
	Metadata: Metadata{
		Country: "US",
		Whois: WhoisInfo{
			NetName:      "TEST-NET-3",
			Organization: "Internet Assigned Numbers Authority",
			Registry:     "ARIN",
		},
	},
})

table.DeleteRoute(prefix, id) // Removes one route.
table.Delete(prefix)          // Removes the entire prefix.

Deleting the final route also removes its prefix.

Data Ownership

The table copies route and BGP attribute slices during insertion and lookup. Generic metadata is copied by assignment. Metadata containing maps, slices, pointers, or other reference types must therefore be treated as immutable while stored in the table and after lookup.

Testing

Task can run the complete test suite verbosely without using cached results:

task test

Run the test suite with race detection and print a per-function coverage report:

task coverage

Run the IPv4 and IPv6 lookup benchmarks with allocation statistics:

task bench

Alternatively:

go test -race -covermode=atomic ./...

License

This project is available under the MIT License. It permits private, commercial, and open-source use, modification, and redistribution while retaining the copyright and license notice.

Documentation

Overview

Package ipradix provides a concurrent IPv4 and IPv6 routing table backed by compressed Patricia radix trees.

Index

Examples

Constants

This section is empty.

Variables

View Source 
var (
	ErrInvalidPrefix    = errors.New("invalid prefix")
	ErrEmptyRoutes      = errors.New("prefix has no routes")
	ErrEmptyRouteID     = errors.New("route ID is empty")
	ErrDuplicateRouteID = errors.New("duplicate route ID")
)

Functions

This section is empty.

Types

type LargeCommunity 

type LargeCommunity struct {
	GlobalAdministrator uint32 `json:"globalAdministrator"`
	LocalData1          uint32 `json:"localData1"`
	LocalData2          uint32 `json:"localData2"`
}

LargeCommunity is a BGP large community.

type Origin 

type Origin uint8

Origin is a BGP ORIGIN path attribute. 

const (
	OriginIGP Origin = iota
	OriginEGP
	OriginIncomplete
)

type Prefix 

type Prefix[M any] struct {
	Prefix netip.Prefix `json:"prefix"`
	Routes []Route[M]   `json:"routes"`
}

Prefix associates a network prefix with all known routes to it.

type Route 

type Route[M any] struct {
	ID                  uint64           `json:"id"`
	RouterID            netip.Addr       `json:"routerId"`
	NextHop             netip.Addr       `json:"nextHop"`
	PeerAS              uint32           `json:"peerAs"`
	OriginAS            uint32           `json:"originAs"`
	ASPath              []uint32         `json:"asPath"`
	Communities         []uint32         `json:"communities"`
	ExtendedCommunities []uint64         `json:"extendedCommunities"`
	LargeCommunities    []LargeCommunity `json:"largeCommunities"`
	LocalPreference     uint32           `json:"localPreference"`
	MED                 uint32           `json:"med"`
	Origin              Origin           `json:"origin"`
	Metadata            M                `json:"metadata"`
}

Route describes a path to a prefix. ID is a nonzero value supplied by the caller and must remain stable for the lifetime of the path.

Metadata is copied by assignment. Callers must treat metadata containing pointers, maps, slices, or other reference types as immutable while stored in a Table and after it is returned by a lookup.

type Table 

type Table[M any] struct {
	// contains filtered or unexported fields
}

Table is a concurrent IPv4 and IPv6 routing table. Its zero value is ready for use. A Table must not be copied after first use.

func (*Table[M]) Delete 

func (t *Table[M]) Delete(prefix netip.Prefix) bool

Delete removes an exact prefix and all routes associated with it.

func (*Table[M]) DeleteRoute 

func (t *Table[M]) DeleteRoute(prefix netip.Prefix, routeID uint64) bool

DeleteRoute removes a route by ID from an exact prefix. Removing the final route also removes the prefix.

func (*Table[M]) Find 

func (t *Table[M]) Find(addr netip.Addr) (Prefix[M], bool)

Find returns the longest-prefix match for addr.

Example 
package main

import (
	"fmt"
	"hash/fnv"
	"net/netip"

	"github.com/kmatsoukas/ipradix"
)

type exampleWhoisInfo struct {
	NetName      string
	Organization string
	Registry     string
}

type exampleMetadata struct {
	Country string
	Whois   exampleWhoisInfo
}

func main() {
	var table ipradix.Table[exampleMetadata]
	prefix := netip.MustParsePrefix("203.0.113.0/24")
	nextHop := netip.MustParseAddr("192.0.2.254")
	routerID := netip.MustParseAddr("192.0.2.1")

	err := table.Insert(ipradix.Prefix[exampleMetadata]{
		Prefix: prefix,
		Routes: []ipradix.Route[exampleMetadata]{
			{
				ID:       routeID(prefix, nextHop),
				NextHop:  nextHop,
				PeerAS:   64512,
				OriginAS: 64496,
				ASPath:   []uint32{64512, 64496},
				Metadata: exampleMetadata{
					Country: "US",
					Whois: exampleWhoisInfo{
						NetName:      "TEST-NET-3",
						Organization: "Internet Assigned Numbers Authority",
						Registry:     "ARIN",
					},
				},
			},
			{
				ID:       routeIDWithRouter(routerID, prefix, nextHop),
				RouterID: routerID,
				NextHop:  nextHop,
				PeerAS:   64513,
				OriginAS: 64496,
				ASPath:   []uint32{64513, 64496},
				Metadata: exampleMetadata{
					Country: "US",
					Whois: exampleWhoisInfo{
						NetName:      "TEST-NET-3",
						Organization: "Internet Assigned Numbers Authority",
						Registry:     "ARIN",
					},
				},
			},
		},
	})
	if err != nil {
		panic(err)
	}

	match, ok := table.Find(netip.MustParseAddr("203.0.113.42"))
	fmt.Println(match.Prefix, len(match.Routes), match.Routes[0].Metadata.Country, match.Routes[0].Metadata.Whois.NetName, ok)

}

func routeID(prefix netip.Prefix, nextHop netip.Addr) uint64 {
	return hashRouteID(prefix.Masked().String(), nextHop.String())
}

func routeIDWithRouter(routerID netip.Addr, prefix netip.Prefix, nextHop netip.Addr) uint64 {
	return hashRouteID(routerID.String(), prefix.Masked().String(), nextHop.String())
}

func hashRouteID(parts ...string) uint64 {
	h := fnv.New64a()
	for _, part := range parts {
		_, _ = h.Write([]byte(part))
		_, _ = h.Write([]byte{0})
	}

	id := h.Sum64()
	if id == 0 {
		return 1
	}
	return id
}

Output:
203.0.113.0/24 2 US TEST-NET-3 true

func (*Table[M]) FindAll 

func (t *Table[M]) FindAll(addr netip.Addr) []Prefix[M]

FindAll returns every prefix containing addr, ordered from most specific to least specific.

func (*Table[M]) Insert 

func (t *Table[M]) Insert(prefix Prefix[M]) error

Insert atomically inserts or replaces a prefix and all of its routes.

func (*Table[M]) UpsertRoute 

func (t *Table[M]) UpsertRoute(prefix netip.Prefix, route Route[M]) error

UpsertRoute inserts a route or replaces the route with the same ID at an exact prefix. New routes are appended, while replacements retain their existing position.

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.