table: use shorter key for map of ipv4 and ipv6 prefixes

save about 100MB memory.

Signed-off-by: FUJITA Tomonori <fujita.tomonori@lab.ntt.co.jp>

7 files changed, 129 insertions, 67 deletions

diff --git a/gobgp/cmd/neighbor.go b/gobgp/cmd/neighbor.go
index 6bbf6d39..a01dfd4e 100644
--- a/gobgp/cmd/neighbor.go
+++ b/gobgp/cmd/neighbor.go
@@ -781,14 +781,25 @@ func showNeighborRib(r string, name string, args []string) error {
 	}
 
 	if globalOpts.Json {
-		j, _ := json.Marshal(rib.GetDestinations())
+		d := make(map[string]*table.Destination)
+		for _, dst := range rib.GetDestinations() {
+			d[dst.GetNlri().String()] = dst
+		}
+		j, _ := json.Marshal(d)
 		fmt.Println(string(j))
 		return nil
 	}
 
 	if validationTarget != "" {
 		// show RPKI validation info
-		d := rib.GetDestination(validationTarget)
+		addr, _, _ := net.ParseCIDR(validationTarget)
+		var nlri bgp.AddrPrefixInterface
+		if addr.To16() == nil {
+			nlri, _ = bgp.NewPrefixFromRouteFamily(bgp.AFI_IP, bgp.SAFI_UNICAST, validationTarget)
+		} else {
+			nlri, _ = bgp.NewPrefixFromRouteFamily(bgp.AFI_IP6, bgp.SAFI_UNICAST, validationTarget)
+		}
+		d := rib.GetDestination(nlri)
 		if d == nil {
 			fmt.Println("Network not in table")
 			return nil
diff --git a/packet/bgp/bgp.go b/packet/bgp/bgp.go
index ef2e3e20..ea7c6844 100644
--- a/packet/bgp/bgp.go
+++ b/packet/bgp/bgp.go
@@ -4755,12 +4755,32 @@ func GetRouteFamily(name string) (RouteFamily, error) {
 	return RouteFamily(0), fmt.Errorf("%s isn't a valid route family name", name)
 }
 
-func NewPrefixFromRouteFamily(afi uint16, safi uint8) (prefix AddrPrefixInterface, err error) {
-	switch AfiSafiToRouteFamily(afi, safi) {
+func NewPrefixFromRouteFamily(afi uint16, safi uint8, prefixStr ...string) (prefix AddrPrefixInterface, err error) {
+	family := AfiSafiToRouteFamily(afi, safi)
+
+	f := func(s string) AddrPrefixInterface {
+		addr, net, _ := net.ParseCIDR(s)
+		len, _ := net.Mask.Size()
+		switch family {
+		case RF_IPv4_UC, RF_IPv4_MC:
+			return NewIPAddrPrefix(uint8(len), addr.String())
+		}
+		return NewIPv6AddrPrefix(uint8(len), addr.String())
+	}
+
+	switch family {
 	case RF_IPv4_UC, RF_IPv4_MC:
-		prefix = NewIPAddrPrefix(0, "")
+		if len(prefixStr) > 0 {
+			prefix = f(prefixStr[0])
+		} else {
+			prefix = NewIPAddrPrefix(0, "")
+		}
 	case RF_IPv6_UC, RF_IPv6_MC:
-		prefix = NewIPv6AddrPrefix(0, "")
+		if len(prefixStr) > 0 {
+			prefix = f(prefixStr[0])
+		} else {
+			prefix = NewIPv6AddrPrefix(0, "")
+		}
 	case RF_IPv4_VPN:
 		prefix = NewLabeledVPNIPAddrPrefix(0, "", *NewMPLSLabelStack(), nil)
 	case RF_IPv6_VPN:
diff --git a/server/server.go b/server/server.go
index 15b95073..e338fe53 100644
--- a/server/server.go
+++ b/server/server.go
@@ -2265,9 +2265,15 @@ func (s *BgpServer) ValidateRib(prefix string) error {
 			if t, ok := s.globalRib.Tables[rf]; ok {
 				dsts := t.GetDestinations()
 				if prefix != "" {
-					_, p, _ := net.ParseCIDR(prefix)
-					if dst := t.GetDestination(p.String()); dst != nil {
-						dsts = map[string]*table.Destination{p.String(): dst}
+					addr, _, _ := net.ParseCIDR(prefix)
+					var nlri bgp.AddrPrefixInterface
+					if addr.To16() == nil {
+						nlri, _ = bgp.NewPrefixFromRouteFamily(bgp.AFI_IP, bgp.SAFI_UNICAST, prefix)
+					} else {
+						nlri, _ = bgp.NewPrefixFromRouteFamily(bgp.AFI_IP6, bgp.SAFI_UNICAST, prefix)
+					}
+					if dst := t.GetDestination(nlri); dst != nil {
+						dsts = map[string]*table.Destination{nlri.String(): dst}
 					}
 				}
 				for _, dst := range dsts {
diff --git a/table/adj.go b/table/adj.go
index 68e79d17..86e760b7 100644
--- a/table/adj.go
+++ b/table/adj.go
@@ -160,21 +160,21 @@ func (adj *AdjRib) Exists(path *Path) bool {
 }
 
 func (adj *AdjRib) Select(family bgp.RouteFamily, accepted bool, option ...TableSelectOption) (*Table, error) {
-	paths := adj.PathList([]bgp.RouteFamily{family}, accepted)
-	dsts := make(map[string]*Destination, len(paths))
-	for _, path := range paths {
-		if d, y := dsts[path.GetNlri().String()]; y {
-			d.knownPathList = append(d.knownPathList, path)
+	m := make(map[string][]*Path)
+	pl := adj.PathList([]bgp.RouteFamily{family}, accepted)
+	for _, path := range pl {
+		key := path.GetNlri().String()
+		if _, y := m[key]; y {
+			m[key] = append(m[key], path)
 		} else {
-			dst := NewDestination(path.GetNlri(), 0)
-			dsts[path.GetNlri().String()] = dst
-			dst.knownPathList = append(dst.knownPathList, path)
+			m[key] = []*Path{path}
 		}
 	}
-	tbl := &Table{
-		routeFamily:  family,
-		destinations: dsts,
+	d := make([]*Destination, 0, len(pl))
+	for _, l := range m {
+		d = append(d, NewDestination(l[0].GetNlri(), 0, l...))
 	}
+	tbl := NewTable(family, d...)
 	option = append(option, TableSelectOption{adj: true})
 	return tbl.Select(option...)
 }
diff --git a/table/table.go b/table/table.go
index 35403a23..b26095f8 100644
--- a/table/table.go
+++ b/table/table.go
@@ -20,6 +20,7 @@ import (
 	"net"
 	"sort"
 	"strings"
+	"unsafe"
 
 	"github.com/armon/go-radix"
 	"github.com/osrg/gobgp/packet/bgp"
@@ -55,14 +56,14 @@ type Table struct {
 }
 
 func NewTable(rf bgp.RouteFamily, dsts ...*Destination) *Table {
-	destinations := make(map[string]*Destination)
-	for _, dst := range dsts {
-		destinations[dst.GetNlri().String()] = dst
-	}
-	return &Table{
+	t := &Table{
 		routeFamily:  rf,
-		destinations: destinations,
+		destinations: make(map[string]*Destination),
+	}
+	for _, dst := range dsts {
+		t.setDestination(dst)
 	}
+	return t
 }
 
 func (t *Table) GetRoutefamily() bgp.RouteFamily {
@@ -118,15 +119,11 @@ func (t *Table) deleteRTCPathsByVrf(vrf *Vrf, vrfs map[string]*Vrf) []*Path {
 }
 
 func (t *Table) deleteDestByNlri(nlri bgp.AddrPrefixInterface) *Destination {
-	destinations := t.GetDestinations()
-	dest := destinations[t.tableKey(nlri)]
-	if dest != nil {
-		delete(destinations, t.tableKey(nlri))
-		if len(destinations) == 0 {
-			t.destinations = make(map[string]*Destination)
-		}
+	if dst := t.GetDestination(nlri); dst != nil {
+		t.deleteDest(dst)
+		return dst
 	}
-	return dest
+	return nil
 }
 
 func (t *Table) deleteDest(dest *Destination) {
@@ -180,16 +177,15 @@ func (t *Table) validatePath(path *Path) {
 }
 
 func (t *Table) getOrCreateDest(nlri bgp.AddrPrefixInterface) *Destination {
-	tableKey := t.tableKey(nlri)
-	dest := t.GetDestination(tableKey)
+	dest := t.GetDestination(nlri)
 	// If destination for given prefix does not exist we create it.
 	if dest == nil {
 		log.WithFields(log.Fields{
 			"Topic": "Table",
-			"Key":   tableKey,
+			"Nlri":  nlri,
 		}).Debugf("create Destination")
 		dest = NewDestination(nlri, 64)
-		t.setDestination(tableKey, dest)
+		t.setDestination(dest)
 	}
 	return dest
 }
@@ -221,8 +217,8 @@ func (t *Table) GetDestinations() map[string]*Destination {
 func (t *Table) setDestinations(destinations map[string]*Destination) {
 	t.destinations = destinations
 }
-func (t *Table) GetDestination(key string) *Destination {
-	dest, ok := t.destinations[key]
+func (t *Table) GetDestination(nlri bgp.AddrPrefixInterface) *Destination {
+	dest, ok := t.destinations[t.tableKey(nlri)]
 	if ok {
 		return dest
 	} else {
@@ -290,11 +286,25 @@ func (t *Table) GetEvpnDestinationsWithRouteType(typ string) ([]*Destination, er
 	return results, nil
 }
 
-func (t *Table) setDestination(key string, dest *Destination) {
-	t.destinations[key] = dest
+func (t *Table) setDestination(dst *Destination) {
+	t.destinations[t.tableKey(dst.nlri)] = dst
 }
 
 func (t *Table) tableKey(nlri bgp.AddrPrefixInterface) string {
+	switch t.routeFamily {
+	case bgp.RF_IPv4_UC:
+		b := make([]byte, 5)
+		ip := nlri.(*bgp.IPAddrPrefix)
+		copy(b, ip.Prefix.To4())
+		b[4] = ip.Length
+		return *(*string)(unsafe.Pointer(&b))
+	case bgp.RF_IPv6_UC:
+		b := make([]byte, 17)
+		ip := nlri.(*bgp.IPv6AddrPrefix)
+		copy(b, ip.Prefix.To16())
+		b[16] = ip.Length
+		return *(*string)(unsafe.Pointer(&b))
+	}
 	return nlri.String()
 }
 
@@ -350,15 +360,24 @@ func (t *Table) Select(option ...TableSelectOption) (*Table, error) {
 		as = o.AS
 	}
 	dOption := DestinationSelectOption{ID: id, AS: as, VRF: vrf, adj: adj, Best: best, MultiPath: mp}
-	dsts := make(map[string]*Destination)
+	r := &Table{
+		routeFamily:  t.routeFamily,
+		destinations: make(map[string]*Destination),
+	}
 
 	if len(prefixes) != 0 {
 		switch t.routeFamily {
-		case bgp.RF_IPv4_UC, bgp.RF_IPv6_UC, bgp.RF_IPv4_MPLS, bgp.RF_IPv6_MPLS:
-			f := func(key string) bool {
-				if dst := t.GetDestination(key); dst != nil {
+		case bgp.RF_IPv4_UC, bgp.RF_IPv6_UC:
+			f := func(prefixStr string) bool {
+				var nlri bgp.AddrPrefixInterface
+				if t.routeFamily == bgp.RF_IPv4_UC {
+					nlri, _ = bgp.NewPrefixFromRouteFamily(bgp.AFI_IP, bgp.SAFI_UNICAST, prefixStr)
+				} else {
+					nlri, _ = bgp.NewPrefixFromRouteFamily(bgp.AFI_IP6, bgp.SAFI_UNICAST, prefixStr)
+				}
+				if dst := t.GetDestination(nlri); dst != nil {
 					if d := dst.Select(dOption); d != nil {
-						dsts[key] = d
+						r.setDestination(d)
 						return true
 					}
 				}
@@ -375,7 +394,7 @@ func (t *Table) Select(option ...TableSelectOption) (*Table, error) {
 					}
 					for _, dst := range ds {
 						if d := dst.Select(dOption); d != nil {
-							dsts[dst.GetNlri().String()] = d
+							r.setDestination(d)
 						}
 					}
 				case LOOKUP_SHORTER:
@@ -417,7 +436,7 @@ func (t *Table) Select(option ...TableSelectOption) (*Table, error) {
 				}
 				for _, dst := range ds {
 					if d := dst.Select(dOption); d != nil {
-						dsts[dst.GetNlri().String()] = d
+						r.setDestination(d)
 					}
 				}
 			}
@@ -425,16 +444,13 @@ func (t *Table) Select(option ...TableSelectOption) (*Table, error) {
 			return nil, fmt.Errorf("route filtering is not supported for this family")
 		}
 	} else {
-		for k, dst := range t.GetDestinations() {
+		for _, dst := range t.GetDestinations() {
 			if d := dst.Select(dOption); d != nil {
-				dsts[k] = d
+				r.setDestination(d)
 			}
 		}
 	}
-	return &Table{
-		routeFamily:  t.routeFamily,
-		destinations: dsts,
-	}, nil
+	return r, nil
 }
 
 type TableInfo struct {
diff --git a/table/table_manager.go b/table/table_manager.go
index 29f36a23..0bee18c3 100644
--- a/table/table_manager.go
+++ b/table/table_manager.go
@@ -346,7 +346,7 @@ func (manager *TableManager) GetDestination(path *Path) *Destination {
 	if !ok {
 		return nil
 	}
-	return t.GetDestination(path.getPrefix())
+	return t.GetDestination(path.GetNlri())
 }
 
 func (manager *TableManager) TableInfo(id string, as uint32, family bgp.RouteFamily) (*TableInfo, error) {
diff --git a/table/table_test.go b/table/table_test.go
index 6f7c2ab4..6228b995 100644
--- a/table/table_test.go
+++ b/table/table_test.go
@@ -16,10 +16,11 @@
 package table
 
 import (
-	"github.com/osrg/gobgp/packet/bgp"
-	"github.com/stretchr/testify/assert"
 	"testing"
 	"time"
+
+	"github.com/osrg/gobgp/packet/bgp"
+	"github.com/stretchr/testify/assert"
 )
 
 func TestTableDeleteDestByNlri(t *testing.T) {
@@ -27,12 +28,10 @@ func TestTableDeleteDestByNlri(t *testing.T) {
 	pathT := TableCreatePath(peerT)
 	ipv4t := NewTable(bgp.RF_IPv4_UC)
 	for _, path := range pathT {
-		tableKey := ipv4t.tableKey(path.GetNlri())
 		dest := NewDestination(path.GetNlri(), 0)
-		ipv4t.setDestination(tableKey, dest)
+		ipv4t.setDestination(dest)
 	}
-	tableKey := ipv4t.tableKey(pathT[0].GetNlri())
-	gdest := ipv4t.GetDestination(tableKey)
+	gdest := ipv4t.GetDestination(pathT[0].GetNlri())
 	rdest := ipv4t.deleteDestByNlri(pathT[0].GetNlri())
 	assert.Equal(t, rdest, gdest)
 }
@@ -42,15 +41,13 @@ func TestTableDeleteDest(t *testing.T) {
 	pathT := TableCreatePath(peerT)
 	ipv4t := NewTable(bgp.RF_IPv4_UC)
 	for _, path := range pathT {
-		tableKey := ipv4t.tableKey(path.GetNlri())
 		dest := NewDestination(path.GetNlri(), 0)
-		ipv4t.setDestination(tableKey, dest)
+		ipv4t.setDestination(dest)
 	}
-	tableKey := ipv4t.tableKey(pathT[0].GetNlri())
 	dest := NewDestination(pathT[0].GetNlri(), 0)
-	ipv4t.setDestination(tableKey, dest)
+	ipv4t.setDestination(dest)
 	ipv4t.deleteDest(dest)
-	gdest := ipv4t.GetDestination(tableKey)
+	gdest := ipv4t.GetDestination(pathT[0].GetNlri())
 	assert.Nil(t, gdest)
 }
 
@@ -89,6 +86,18 @@ func TestTableGetDestinations(t *testing.T) {
 	assert.Equal(t, ds, destinations)
 }
 
+func TestTableKey(t *testing.T) {
+	tb := NewTable(bgp.RF_IPv4_UC)
+	n1, _ := bgp.NewPrefixFromRouteFamily(bgp.AFI_IP, bgp.SAFI_UNICAST, "0.0.0.0/0")
+	d1 := NewDestination(n1, 0)
+	n2, _ := bgp.NewPrefixFromRouteFamily(bgp.AFI_IP, bgp.SAFI_UNICAST, "0.0.0.0/1")
+	d2 := NewDestination(n2, 0)
+	assert.Equal(t, len(tb.tableKey(d1.GetNlri())), 5)
+	tb.setDestination(d1)
+	tb.setDestination(d2)
+	assert.Equal(t, len(tb.GetDestinations()), 2)
+}
+
 func TableCreatePeer() []*PeerInfo {
 	peerT1 := &PeerInfo{AS: 65000}
 	peerT2 := &PeerInfo{AS: 65001}