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>

8 files changed, 52 insertions, 107 deletions

diff --git a/go.mod b/go.mod
index 572027d2..0ff2519e 100644
--- a/go.mod
+++ b/go.mod
@@ -1,8 +1,7 @@
 module github.com/osrg/gobgp
 
 require (
-	github.com/BurntSushi/toml v0.3.0
-	github.com/armon/go-radix v0.0.0-20170727155443-1fca145dffbc
+	github.com/BurntSushi/toml v0.3.1
 	github.com/coreos/go-systemd v0.0.0-20190321100706-95778dfbb74e
 	github.com/davecgh/go-spew v1.1.0 // indirect
 	github.com/dgryski/go-farm v0.0.0-20171119141306-ac7624ea8da3
@@ -15,8 +14,7 @@ require (
 	github.com/inconshreveable/mousetrap v1.0.0 // indirect
 	github.com/jessevdk/go-flags v1.3.0
 	github.com/k-sone/critbitgo v1.3.1-0.20191024122315-48c9e1530131
-	github.com/kr/pretty v0.0.0-20160823170715-cfb55aafdaf3
-	github.com/kr/text v0.0.0-20160504234017-7cafcd837844 // indirect
+	github.com/kr/pretty v0.1.0
 	github.com/magiconair/properties v1.7.3 // indirect
 	github.com/mitchellh/mapstructure v0.0.0-20170523030023-d0303fe80992 // indirect
 	github.com/pelletier/go-buffruneio v0.2.0 // indirect
@@ -32,9 +30,9 @@ require (
 	github.com/stretchr/testify v1.1.4
 	github.com/vishvananda/netlink v0.0.0-20170802012344-a95659537721
 	github.com/vishvananda/netns v0.0.0-20170707011535-86bef332bfc3 // indirect
-	golang.org/x/net v0.0.0-20190404232315-eb5bcb51f2a3
-	golang.org/x/sync v0.0.0-20190227155943-e225da77a7e6 // indirect
-	golang.org/x/sys v0.0.0-20190405154228-4b34438f7a67 // indirect
+	golang.org/x/net v0.0.0-20190620200207-3b0461eec859
+	golang.org/x/sync v0.0.0-20190423024810-112230192c58 // indirect
+	golang.org/x/sys v0.0.0-20190412213103-97732733099d // indirect
 	google.golang.org/genproto v0.0.0-20170731182057-09f6ed296fc6 // indirect
 	google.golang.org/grpc v1.5.1
 	gopkg.in/check.v1 v1.0.0-20180628173108-788fd7840127 // indirect
diff --git a/go.sum b/go.sum
index 96384b72..94da041a 100644
--- a/go.sum
+++ b/go.sum
@@ -1,7 +1,5 @@
-github.com/BurntSushi/toml v0.3.0 h1:e1/Ivsx3Z0FVTV0NSOv/aVgbUWyQuzj7DDnFblkRvsY=
-github.com/BurntSushi/toml v0.3.0/go.mod h1:xHWCNGjB5oqiDr8zfno3MHue2Ht5sIBksp03qcyfWMU=
-github.com/armon/go-radix v0.0.0-20170727155443-1fca145dffbc h1:/WQ8Tr5zbclKWAtvafIcAk/njNpW3gtd22TLLouv+6Q=
-github.com/armon/go-radix v0.0.0-20170727155443-1fca145dffbc/go.mod h1:ufUuZ+zHj4x4TnLV4JWEpy2hxWSpsRywHrMgIH9cCH8=
+github.com/BurntSushi/toml v0.3.1 h1:WXkYYl6Yr3qBf1K79EBnL4mak0OimBfB0XUf9Vl28OQ=
+github.com/BurntSushi/toml v0.3.1/go.mod h1:xHWCNGjB5oqiDr8zfno3MHue2Ht5sIBksp03qcyfWMU=
 github.com/coreos/go-systemd v0.0.0-20190321100706-95778dfbb74e h1:Wf6HqHfScWJN9/ZjdUKyjop4mf3Qdd+1TvvltAvM3m8=
 github.com/coreos/go-systemd v0.0.0-20190321100706-95778dfbb74e/go.mod h1:F5haX7vjVVG0kc13fIWeqUViNPyEJxv/OmvnBo0Yme4=
 github.com/davecgh/go-spew v1.1.0 h1:ZDRjVQ15GmhC3fiQ8ni8+OwkZQO4DARzQgrnXU1Liz8=
@@ -26,10 +24,11 @@ github.com/jessevdk/go-flags v1.3.0 h1:QmKsgik/Z5fJ11ZtlcA8F+XW9dNybBNFQ1rngF3Mm
 github.com/jessevdk/go-flags v1.3.0/go.mod h1:4FA24M0QyGHXBuZZK/XkWh8h0e1EYbRYJSGM75WSRxI=
 github.com/k-sone/critbitgo v1.3.1-0.20191024122315-48c9e1530131 h1:2bjzgZk4GiWAFkj15/SkmxIO30u69RyPiSS+F0d+Kzs=
 github.com/k-sone/critbitgo v1.3.1-0.20191024122315-48c9e1530131/go.mod h1:7E6pyoyADnFxlUBEKcnfS49b7SUAQGMK+OAp/UQvo0s=
-github.com/kr/pretty v0.0.0-20160823170715-cfb55aafdaf3 h1:dhwb1Ev84SKKVBfLuhR4bw/29yYHzwtTyTLUWWnvYxI=
-github.com/kr/pretty v0.0.0-20160823170715-cfb55aafdaf3/go.mod h1:Bvhd+E3laJ0AVkG0c9rmtZcnhV0HQ3+c3YxxqTvc/gA=
-github.com/kr/text v0.0.0-20160504234017-7cafcd837844 h1:kpzneEBeC0dMewP3gr/fADv1OlblH9r1goWVwpOt3TU=
-github.com/kr/text v0.0.0-20160504234017-7cafcd837844/go.mod h1:sjUstKUATFIcff4qlB53Kml0wQPtJVc/3fWrmuUmcfA=
+github.com/kr/pretty v0.1.0 h1:L/CwN0zerZDmRFUapSPitk6f+Q3+0za1rQkzVuMiMFI=
+github.com/kr/pretty v0.1.0/go.mod h1:dAy3ld7l9f0ibDNOQOHHMYYIIbhfbHSm3C4ZsoJORNo=
+github.com/kr/pty v1.1.1/go.mod h1:pFQYn66WHrOpPYNljwOMqo10TkYh1fy3cYio2l3bCsQ=
+github.com/kr/text v0.1.0 h1:45sCR5RtlFHMR4UwH9sdQ5TC8v0qDQCHnXt+kaKSTVE=
+github.com/kr/text v0.1.0/go.mod h1:4Jbv+DJW3UT/LiOwJeYQe1efqtUx/iVham/4vfdArNI=
 github.com/magiconair/properties v1.7.3 h1:6AOjgCKyZFMG/1yfReDPDz3CJZPxnYk7DGmj2HtyF24=
 github.com/magiconair/properties v1.7.3/go.mod h1:PppfXfuXeibc/6YijjN8zIbojt8czPbwD3XqdrwzmxQ=
 github.com/mitchellh/mapstructure v0.0.0-20170523030023-d0303fe80992 h1:W7VHAEVflA5/eTyRvQ53Lz5j8bhRd1myHZlI/IZFvbU=
@@ -61,13 +60,13 @@ github.com/vishvananda/netlink v0.0.0-20170802012344-a95659537721/go.mod h1:+SR5
 github.com/vishvananda/netns v0.0.0-20170707011535-86bef332bfc3 h1:NcYCJC+LbOrfvuf/uHeM/kxh6vOmiuInC4GAWRdc+P0=
 github.com/vishvananda/netns v0.0.0-20170707011535-86bef332bfc3/go.mod h1:ZjcWmFBXmLKZu9Nxj3WKYEafiSqer2rnvPr0en9UNpI=
 golang.org/x/crypto v0.0.0-20190308221718-c2843e01d9a2/go.mod h1:djNgcEr1/C05ACkg1iLfiJU5Ep61QUkGW8qpdssI0+w=
-golang.org/x/net v0.0.0-20190404232315-eb5bcb51f2a3 h1:0GoQqolDA55aaLxZyTzK/Y2ePZzZTUrRacwib7cNsYQ=
-golang.org/x/net v0.0.0-20190404232315-eb5bcb51f2a3/go.mod h1:t9HGtf8HONx5eT2rtn7q6eTqICYqUVnKs3thJo3Qplg=
-golang.org/x/sync v0.0.0-20190227155943-e225da77a7e6 h1:bjcUS9ztw9kFmmIxJInhon/0Is3p+EHBKNgquIzo1OI=
-golang.org/x/sync v0.0.0-20190227155943-e225da77a7e6/go.mod h1:RxMgew5VJxzue5/jJTE5uejpjVlOe/izrB70Jof72aM=
+golang.org/x/net v0.0.0-20190620200207-3b0461eec859 h1:R/3boaszxrf1GEUWTVDzSKVwLmSJpwZ1yqXm8j0v2QI=
+golang.org/x/net v0.0.0-20190620200207-3b0461eec859/go.mod h1:z5CRVTTTmAJ677TzLLGU+0bjPO0LkuOLi4/5GtJWs/s=
+golang.org/x/sync v0.0.0-20190423024810-112230192c58 h1:8gQV6CLnAEikrhgkHFbMAEhagSSnXWGV915qUMm9mrU=
+golang.org/x/sync v0.0.0-20190423024810-112230192c58/go.mod h1:RxMgew5VJxzue5/jJTE5uejpjVlOe/izrB70Jof72aM=
 golang.org/x/sys v0.0.0-20190215142949-d0b11bdaac8a/go.mod h1:STP8DvDyc/dI5b8T5hshtkjS+E42TnysNCUPdjciGhY=
-golang.org/x/sys v0.0.0-20190405154228-4b34438f7a67 h1:1Fzlr8kkDLQwqMP8GxrhptBLqZG/EDpiATneiZHY998=
-golang.org/x/sys v0.0.0-20190405154228-4b34438f7a67/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
+golang.org/x/sys v0.0.0-20190412213103-97732733099d h1:+R4KGOnez64A81RvjARKc4UT5/tI9ujCIVX+P5KiHuI=
+golang.org/x/sys v0.0.0-20190412213103-97732733099d/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
 golang.org/x/text v0.3.0 h1:g61tztE5qeGQ89tm6NTjjM9VPIm088od1l6aSorWRWg=
 golang.org/x/text v0.3.0/go.mod h1:NqM8EUOU14njkJ3fqMW+pc6Ldnwhi/IjpwHt7yyuwOQ=
 google.golang.org/genproto v0.0.0-20170731182057-09f6ed296fc6 h1:72GtwBPfq6av9X0Ru2HtAopsPW+d+vh1K1zaxanTdE8=
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() {