table: replace radix with crit-bit algo for longer-prefixes search

faster and less memory usage.

Now go-radix has gone.

Signed-off-by: FUJITA Tomonori <fujita.tomonori@gmail.com>

6 files changed, 34 insertions, 86 deletions

diff --git a/internal/pkg/table/destination.go b/internal/pkg/table/destination.go
index 4adc6290..2880f662 100644
--- a/internal/pkg/table/destination.go
+++ b/internal/pkg/table/destination.go
@@ -74,38 +74,6 @@ func (r *BestPathReason) String() string {
 	return BestPathReasonStringMap[*r]
 }
 
-func IpToRadixkey(b []byte, max uint8) string {
-	var buffer bytes.Buffer
-	for i := 0; i < len(b) && i < int(max); i++ {
-		fmt.Fprintf(&buffer, "%08b", b[i])
-	}
-	return buffer.String()[:max]
-}
-
-func CidrToRadixkey(cidr string) string {
-	_, n, _ := net.ParseCIDR(cidr)
-	ones, _ := n.Mask.Size()
-	return IpToRadixkey(n.IP, uint8(ones))
-}
-
-func AddrToRadixkey(addr bgp.AddrPrefixInterface) string {
-	var (
-		ip   net.IP
-		size uint8
-	)
-	switch T := addr.(type) {
-	case *bgp.IPAddrPrefix:
-		mask := net.CIDRMask(int(T.Length), net.IPv4len*8)
-		ip, size = T.Prefix.Mask(mask).To4(), uint8(T.Length)
-	case *bgp.IPv6AddrPrefix:
-		mask := net.CIDRMask(int(T.Length), net.IPv6len*8)
-		ip, size = T.Prefix.Mask(mask).To16(), uint8(T.Length)
-	default:
-		return CidrToRadixkey(addr.String())
-	}
-	return IpToRadixkey(ip, size)
-}
-
 type PeerInfo struct {
 	AS                      uint32
 	ID                      net.IP
diff --git a/internal/pkg/table/destination_test.go b/internal/pkg/table/destination_test.go
index 110278fb..b1c1b2e8 100644
--- a/internal/pkg/table/destination_test.go
+++ b/internal/pkg/table/destination_test.go
@@ -17,7 +17,7 @@ package table
 
 import (
 	//"fmt"
-	"fmt"
+
 	"net"
 	"testing"
 	"time"
@@ -292,35 +292,6 @@ func updateMsgD3() *bgp.BGPMessage {
 	return updateMsg
 }
 
-func TestRadixkey(t *testing.T) {
-	assert.Equal(t, "000010100000001100100000", CidrToRadixkey("10.3.32.0/24"))
-	assert.Equal(t, "000010100000001100100000", IpToRadixkey(net.ParseIP("10.3.32.0").To4(), 24))
-	assert.Equal(t, "000010100000001100100000", IpToRadixkey(net.ParseIP("10.3.32.0").To4(), 24))
-	assert.Equal(t, CidrToRadixkey("::ffff:0.0.0.0/96")+"000010100000001100100000", CidrToRadixkey("::ffff:10.3.32.0/120"))
-}
-
-func TestIpToRadixkey(t *testing.T) {
-	for i := byte(0); i < 255; i += 3 {
-		for y := byte(1); y < 128; y *= 2 {
-			ip := net.IPv4(i, i+2, i+3, i-y)
-			for n := uint8(16); n <= 32; n += 2 {
-				exp := CidrToRadixkey(fmt.Sprintf("%v/%d", ip.To4(), n))
-				got := IpToRadixkey(ip.To4(), n)
-				if exp != got {
-					t.Fatalf(`exp %v; got %v`, exp, got)
-				}
-			}
-			for n := uint8(116); n <= 128; n += 2 {
-				exp := CidrToRadixkey(fmt.Sprintf("::ffff:%v/%d", ip.To16(), n))
-				got := IpToRadixkey(ip.To16(), n)
-				if exp != got {
-					t.Fatalf(`exp %v; got %v`, exp, got)
-				}
-			}
-		}
-	}
-}
-
 func TestMultipath(t *testing.T) {
 	UseMultiplePaths.Enabled = true
 	origin := bgp.NewPathAttributeOrigin(0)
diff --git a/internal/pkg/table/path.go b/internal/pkg/table/path.go
index 9f68fde3..0a6debca 100644
--- a/internal/pkg/table/path.go
+++ b/internal/pkg/table/path.go
@@ -1217,3 +1217,29 @@ func (p *Path) SetHash(v uint32) {
 func (p *Path) GetHash() uint32 {
 	return p.attrsHash
 }
+
+func nlriToIPNet(nlri bgp.AddrPrefixInterface) *net.IPNet {
+	switch T := nlri.(type) {
+	case *bgp.IPAddrPrefix:
+		return &net.IPNet{
+			IP:   net.IP(T.Prefix.To4()),
+			Mask: net.CIDRMask(int(T.Length), 32),
+		}
+	case *bgp.IPv6AddrPrefix:
+		return &net.IPNet{
+			IP:   net.IP(T.Prefix.To16()),
+			Mask: net.CIDRMask(int(T.Length), 128),
+		}
+	case *bgp.LabeledIPAddrPrefix:
+		return &net.IPNet{
+			IP:   net.IP(T.Prefix.To4()),
+			Mask: net.CIDRMask(int(T.Length), 32),
+		}
+	case *bgp.LabeledIPv6AddrPrefix:
+		return &net.IPNet{
+			IP:   net.IP(T.Prefix.To4()),
+			Mask: net.CIDRMask(int(T.Length), 128),
+		}
+	}
+	return nil
+}
diff --git a/internal/pkg/table/policy.go b/internal/pkg/table/policy.go
index 32626c6d..08636991 100644
--- a/internal/pkg/table/policy.go
+++ b/internal/pkg/table/policy.go
@@ -1443,7 +1443,7 @@ func (c *PrefixCondition) Evaluate(path *Path, _ *PolicyOptions) bool {
 		return false
 	}
 
-	r := pathToIPNet(path)
+	r := nlriToIPNet(path.GetNlri())
 	ones, _ := r.Mask.Size()
 	masklen := uint8(ones)
 	result := false
diff --git a/internal/pkg/table/roa.go b/internal/pkg/table/roa.go
index 4d8aeb04..f4ff0aa2 100644
--- a/internal/pkg/table/roa.go
+++ b/internal/pkg/table/roa.go
@@ -172,22 +172,6 @@ func (rt *ROATable) DeleteAll(network string) {
 	}
 }
 
-func pathToIPNet(path *Path) *net.IPNet {
-	switch T := path.GetNlri().(type) {
-	case *bgp.IPAddrPrefix:
-		return &net.IPNet{
-			IP:   net.IP(T.Prefix.To4()),
-			Mask: net.CIDRMask(int(T.Length), 32),
-		}
-	case *bgp.IPv6AddrPrefix:
-		return &net.IPNet{
-			IP:   net.IP(T.Prefix.To16()),
-			Mask: net.CIDRMask(int(T.Length), 128),
-		}
-	}
-	return nil
-}
-
 func (rt *ROATable) Validate(path *Path) *Validation {
 	if path.IsWithdraw || path.IsEOR() {
 		// RPKI isn't enabled or invalid path
@@ -229,7 +213,7 @@ func (rt *ROATable) Validate(path *Path) *Validation {
 		}
 	}
 
-	r := pathToIPNet(path)
+	r := nlriToIPNet(path.GetNlri())
 	prefixLen, _ := r.Mask.Size()
 	var bucket *roaBucket
 	tree.WalkMatch(r, func(r *net.IPNet, v interface{}) bool {
diff --git a/internal/pkg/table/table.go b/internal/pkg/table/table.go
index 40eab0f7..bfcf2059 100644
--- a/internal/pkg/table/table.go
+++ b/internal/pkg/table/table.go
@@ -22,7 +22,7 @@ import (
 	"strings"
 	"unsafe"
 
-	"github.com/armon/go-radix"
+	"github.com/k-sone/critbitgo"
 	"github.com/osrg/gobgp/pkg/packet/bgp"
 	log "github.com/sirupsen/logrus"
 )
@@ -212,14 +212,13 @@ func (t *Table) GetLongerPrefixDestinations(key string) ([]*Destination, error)
 		if err != nil {
 			return nil, err
 		}
-		k := CidrToRadixkey(prefix.String())
-		r := radix.New()
+		r := critbitgo.NewNet()
 		for _, dst := range t.GetDestinations() {
-			r.Insert(AddrToRadixkey(dst.nlri), dst)
+			r.Add(nlriToIPNet(dst.nlri), dst)
 		}
-		r.WalkPrefix(k, func(s string, v interface{}) bool {
+		r.WalkPrefix(prefix, func(_ *net.IPNet, v interface{}) bool {
 			results = append(results, v.(*Destination))
-			return false
+			return true
 		})
 	default:
 		for _, dst := range t.GetDestinations() {