table: allocate bitmap for path id dynamically

allocating 256 bytes per prefix isn't a good idea. Let's allocate 8
bytes by default and expand dynamically if necessary.

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

6 files changed, 78 insertions, 37 deletions

diff --git a/table/adj.go b/table/adj.go
index 05a795be..98c714e6 100644
--- a/table/adj.go
+++ b/table/adj.go
@@ -178,7 +178,7 @@ func (adj *AdjRib) Select(family bgp.RouteFamily, accepted bool, option ...Table
 		if d, y := dsts[path.GetNlri().String()]; y {
 			d.knownPathList = append(d.knownPathList, path)
 		} else {
-			dst := NewDestination(path.GetNlri())
+			dst := NewDestination(path.GetNlri(), 0)
 			dsts[path.GetNlri().String()] = dst
 			dst.knownPathList = append(dst.knownPathList, path)
 		}
diff --git a/table/destination.go b/table/destination.go
index 15d80e1d..9a26b4d3 100644
--- a/table/destination.go
+++ b/table/destination.go
@@ -147,16 +147,21 @@ type Destination struct {
 	newPathList      paths
 	oldKnownPathList paths
 	RadixKey         string
-	localIdMap       Bitmap
+	localIdMap       *Bitmap
 }
 
-func NewDestination(nlri bgp.AddrPrefixInterface, known ...*Path) *Destination {
+func NewDestination(nlri bgp.AddrPrefixInterface, mapSize int, known ...*Path) *Destination {
 	d := &Destination{
 		routeFamily:   bgp.AfiSafiToRouteFamily(nlri.AFI(), nlri.SAFI()),
 		nlri:          nlri,
 		knownPathList: known,
 		withdrawList:  make([]*Path, 0),
 		newPathList:   make([]*Path, 0),
+		localIdMap:    NewBitmap(mapSize),
+	}
+	// the id zero means id is not allocated yet.
+	if mapSize != 0 {
+		d.localIdMap.Flag(0)
 	}
 	switch d.routeFamily {
 	case bgp.RF_IPv4_UC, bgp.RF_IPv6_UC, bgp.RF_IPv4_MPLS, bgp.RF_IPv6_MPLS:
@@ -345,7 +350,12 @@ func (dest *Destination) Calculate() *Destination {
 
 	for _, path := range dest.knownPathList {
 		if path.GetNlri().PathLocalIdentifier() == 0 {
-			path.GetNlri().SetPathLocalIdentifier(uint32(dest.localIdMap.FindandSetZeroBit()))
+			id, err := dest.localIdMap.FindandSetZeroBit()
+			if err != nil {
+				dest.localIdMap.Expand()
+				id, _ = dest.localIdMap.FindandSetZeroBit()
+			}
+			path.GetNlri().SetPathLocalIdentifier(uint32(id))
 		}
 	}
 	// Clear new paths as we copied them.
@@ -1022,7 +1032,7 @@ func (old *Destination) Select(option ...DestinationSelectOption) *Destination {
 			}
 		}
 	}
-	new := NewDestination(old.nlri)
+	new := NewDestination(old.nlri, 0)
 	for _, path := range paths {
 		p := path.Clone(path.IsWithdraw)
 		p.Filter("", path.Filtered(id))
diff --git a/table/destination_test.go b/table/destination_test.go
index d1124b4b..48430bd6 100644
--- a/table/destination_test.go
+++ b/table/destination_test.go
@@ -29,13 +29,13 @@ import (
 func TestDestinationNewIPv4(t *testing.T) {
 	peerD := DestCreatePeer()
 	pathD := DestCreatePath(peerD)
-	ipv4d := NewDestination(pathD[0].GetNlri())
+	ipv4d := NewDestination(pathD[0].GetNlri(), 0)
 	assert.NotNil(t, ipv4d)
 }
 func TestDestinationNewIPv6(t *testing.T) {
 	peerD := DestCreatePeer()
 	pathD := DestCreatePath(peerD)
-	ipv6d := NewDestination(pathD[0].GetNlri())
+	ipv6d := NewDestination(pathD[0].GetNlri(), 0)
 	assert.NotNil(t, ipv6d)
 }
 
@@ -88,7 +88,7 @@ func TestCalculate(t *testing.T) {
 	path1.Filter("2", POLICY_DIRECTION_IMPORT)
 	path2.Filter("1", POLICY_DIRECTION_IMPORT)
 
-	d := NewDestination(nlri)
+	d := NewDestination(nlri, 0)
 	d.AddNewPath(path1)
 	d.AddNewPath(path2)
 
@@ -122,7 +122,7 @@ func TestCalculate2(t *testing.T) {
 	peer1 := &PeerInfo{AS: 1, Address: net.IP{1, 1, 1, 1}}
 	path1 := ProcessMessage(update1, peer1, time.Now())[0]
 
-	d := NewDestination(nlri)
+	d := NewDestination(nlri, 0)
 	d.AddNewPath(path1)
 	d.Calculate()
 
@@ -186,7 +186,7 @@ func TestImplicitWithdrawCalculate(t *testing.T) {
 	path2.Filter("1", POLICY_DIRECTION_IMPORT)
 	path2.Filter("3", POLICY_DIRECTION_IMPORT)
 
-	d := NewDestination(nlri)
+	d := NewDestination(nlri, 0)
 	d.AddNewPath(path1)
 	d.AddNewPath(path2)
 
@@ -290,7 +290,7 @@ func TestTimeTieBreaker(t *testing.T) {
 	peer2 := &PeerInfo{AS: 2, LocalAS: 1, Address: net.IP{2, 2, 2, 2}, ID: net.IP{2, 2, 2, 2}} // weaker router-id
 	path2 := ProcessMessage(updateMsg, peer2, time.Now().Add(-1*time.Hour))[0]                 // older than path1
 
-	d := NewDestination(nlri)
+	d := NewDestination(nlri, 0)
 	d.AddNewPath(path1)
 	d.AddNewPath(path2)
 
@@ -301,7 +301,7 @@ func TestTimeTieBreaker(t *testing.T) {
 
 	// this option disables tie breaking by age
 	SelectionOptions.ExternalCompareRouterId = true
-	d = NewDestination(nlri)
+	d = NewDestination(nlri, 0)
 	d.AddNewPath(path1)
 	d.AddNewPath(path2)
 
@@ -458,7 +458,7 @@ func TestMultipath(t *testing.T) {
 	updateMsg = bgp.NewBGPUpdateMessage(nil, pathAttributes, nlri)
 	path2 := ProcessMessage(updateMsg, peer2, time.Now())[0]
 
-	d := NewDestination(nlri[0])
+	d := NewDestination(nlri[0], 0)
 	d.AddNewPath(path1)
 	d.AddNewPath(path2)
 
@@ -513,3 +513,22 @@ func TestMultipath(t *testing.T) {
 
 	UseMultiplePaths.Enabled = false
 }
+
+func TestIdMap(t *testing.T) {
+	d := NewDestination(bgp.NewIPAddrPrefix(24, "10.10.0.101"), 64)
+	for i := 0; ; i++ {
+		if id, err := d.localIdMap.FindandSetZeroBit(); err == nil {
+			assert.Equal(t, uint(i+1), id)
+		} else {
+			assert.Equal(t, i, 63)
+			break
+		}
+	}
+	d.localIdMap.Expand()
+	for i := 0; i < 64; i++ {
+		id, _ := d.localIdMap.FindandSetZeroBit()
+		assert.Equal(t, id, uint(64+i))
+	}
+	_, err := d.localIdMap.FindandSetZeroBit()
+	assert.NotNil(t, err)
+}
diff --git a/table/path.go b/table/path.go
index 07702fc4..fbe426c5 100644
--- a/table/path.go
+++ b/table/path.go
@@ -36,40 +36,55 @@ const (
 	DEFAULT_LOCAL_PREF = 100
 )
 
-type Bitmap []uint64
+type Bitmap struct {
+	bitmap []uint64
+}
 
-func (b Bitmap) Flag(i uint) {
-	b[i/64] |= 1 << uint(i%64)
+func (b *Bitmap) Flag(i uint) {
+	b.bitmap[i/64] |= 1 << uint(i%64)
 }
 
-func (b Bitmap) Unflag(i uint) {
-	b[i/64] &^= 1 << uint(i%64)
+func (b *Bitmap) Unflag(i uint) {
+	b.bitmap[i/64] &^= 1 << uint(i%64)
 }
 
-func (b Bitmap) GetFlag(i uint) bool {
-	return b[i/64]&(1<<uint(i%64)) > 0
+func (b *Bitmap) GetFlag(i uint) bool {
+	return b.bitmap[i/64]&(1<<uint(i%64)) > 0
 }
 
-func (b Bitmap) FindandSetZeroBit() uint {
-	for i := 0; i < len(b); i++ {
-		if b[i] == math.MaxUint64 {
+func (b *Bitmap) FindandSetZeroBit() (uint, error) {
+	for i := 0; i < len(b.bitmap); i++ {
+		if b.bitmap[i] == math.MaxUint64 {
 			continue
 		}
 		// replace this with TrailingZero64() when gobgp drops go 1.8 support.
 		for j := 0; j < 64; j++ {
-			v := ^b[i]
+			v := ^b.bitmap[i]
 			if v&(1<<uint64(j)) > 0 {
 				r := i*64 + j
 				b.Flag(uint(r))
-				return uint(r)
+				return uint(r), nil
 			}
 		}
 	}
-	return 0
+	return 0, fmt.Errorf("no space")
+}
+
+func (b *Bitmap) Expand() {
+	old := b.bitmap
+	new := make([]uint64, len(old)+1)
+	for i := 0; i < len(old); i++ {
+		new[i] = old[i]
+	}
+	b.bitmap = new
 }
 
-func NewBitmap(size int) Bitmap {
-	return Bitmap(make([]uint64, (size+64-1)/64))
+func NewBitmap(size int) *Bitmap {
+	b := &Bitmap{}
+	if size != 0 {
+		b.bitmap = make([]uint64, (size+64-1)/64)
+	}
+	return b
 }
 
 type originInfo struct {
diff --git a/table/table.go b/table/table.go
index 6e423808..01bf6349 100644
--- a/table/table.go
+++ b/table/table.go
@@ -217,10 +217,7 @@ func (t *Table) getOrCreateDest(nlri bgp.AddrPrefixInterface) *Destination {
 			"Topic": "Table",
 			"Key":   tableKey,
 		}).Debugf("create Destination")
-		dest = NewDestination(nlri)
-		dest.localIdMap = NewBitmap(2048)
-		// the id zero means id is not allocated yet.
-		dest.localIdMap.Flag(0)
+		dest = NewDestination(nlri, 64)
 		t.setDestination(tableKey, dest)
 	}
 	return dest
diff --git a/table/table_test.go b/table/table_test.go
index bb51a4de..6f7c2ab4 100644
--- a/table/table_test.go
+++ b/table/table_test.go
@@ -28,7 +28,7 @@ func TestTableDeleteDestByNlri(t *testing.T) {
 	ipv4t := NewTable(bgp.RF_IPv4_UC)
 	for _, path := range pathT {
 		tableKey := ipv4t.tableKey(path.GetNlri())
-		dest := NewDestination(path.GetNlri())
+		dest := NewDestination(path.GetNlri(), 0)
 		ipv4t.setDestination(tableKey, dest)
 	}
 	tableKey := ipv4t.tableKey(pathT[0].GetNlri())
@@ -43,11 +43,11 @@ func TestTableDeleteDest(t *testing.T) {
 	ipv4t := NewTable(bgp.RF_IPv4_UC)
 	for _, path := range pathT {
 		tableKey := ipv4t.tableKey(path.GetNlri())
-		dest := NewDestination(path.GetNlri())
+		dest := NewDestination(path.GetNlri(), 0)
 		ipv4t.setDestination(tableKey, dest)
 	}
 	tableKey := ipv4t.tableKey(pathT[0].GetNlri())
-	dest := NewDestination(pathT[0].GetNlri())
+	dest := NewDestination(pathT[0].GetNlri(), 0)
 	ipv4t.setDestination(tableKey, dest)
 	ipv4t.deleteDest(dest)
 	gdest := ipv4t.GetDestination(tableKey)
@@ -67,7 +67,7 @@ func TestTableSetDestinations(t *testing.T) {
 	destinations := make(map[string]*Destination)
 	for _, path := range pathT {
 		tableKey := ipv4t.tableKey(path.GetNlri())
-		dest := NewDestination(path.GetNlri())
+		dest := NewDestination(path.GetNlri(), 0)
 		destinations[tableKey] = dest
 	}
 	ipv4t.setDestinations(destinations)
@@ -81,7 +81,7 @@ func TestTableGetDestinations(t *testing.T) {
 	destinations := make(map[string]*Destination)
 	for _, path := range pathT {
 		tableKey := ipv4t.tableKey(path.GetNlri())
-		dest := NewDestination(path.GetNlri())
+		dest := NewDestination(path.GetNlri(), 0)
 		destinations[tableKey] = dest
 	}
 	ipv4t.setDestinations(destinations)