table: assign local identifier to path

The local identifier for path is sent to remote peers.

To simplify the implementation,

1) the local identifier is unique per prefix not peer.
2) always assign the local identifier even without addpath-rx-capable peer.

In the future, we might need to improve 2) to avoid the unnecessary
overhead.

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

3 files changed, 36 insertions, 1 deletions

diff --git a/table/destination.go b/table/destination.go
index cef2086f..78e0ac6b 100644
--- a/table/destination.go
+++ b/table/destination.go
@@ -147,6 +147,7 @@ type Destination struct {
 	newPathList      paths
 	oldKnownPathList paths
 	RadixKey         string
+	localIdMap       Bitmap
 }
 
 func NewDestination(nlri bgp.AddrPrefixInterface, known ...*Path) *Destination {
@@ -318,11 +319,23 @@ func (dd *Destination) validatePath(path *Path) {
 func (dest *Destination) Calculate() *Destination {
 	oldKnownPathList := dest.knownPathList
 	// First remove the withdrawn paths.
-	dest.explicitWithdraw()
+	withdrawn := dest.explicitWithdraw()
 	// Do implicit withdrawal
 	dest.implicitWithdraw()
+
+	for _, path := range withdrawn {
+		if id := path.GetNlri().PathLocalIdentifier(); id != 0 {
+			dest.localIdMap.Unflag(uint(id))
+		}
+	}
 	// Collect all new paths into known paths.
 	dest.knownPathList = append(dest.knownPathList, dest.newPathList...)
+
+	for _, path := range dest.knownPathList {
+		if path.GetNlri().PathLocalIdentifier() == 0 {
+			path.GetNlri().SetPathLocalIdentifier(uint32(dest.localIdMap.FindandSetZeroBit()))
+		}
+	}
 	// Clear new paths as we copied them.
 	dest.newPathList = make([]*Path, 0)
 	// Compute new best path
@@ -438,6 +451,7 @@ func (dest *Destination) implicitWithdraw() paths {
 				}).Debug("Implicit withdrawal of old path, since we have learned new path from the same peer")
 
 				found = true
+				newPath.GetNlri().SetPathLocalIdentifier(path.GetNlri().PathLocalIdentifier())
 				break
 			}
 		}
diff --git a/table/path.go b/table/path.go
index c911ebf3..6b7146a9 100644
--- a/table/path.go
+++ b/table/path.go
@@ -50,6 +50,24 @@ func (b Bitmap) GetFlag(i uint) bool {
 	return b[i/64]&(1<<uint(i%64)) > 0
 }
 
+func (b Bitmap) FindandSetZeroBit() uint {
+	for i := 0; i < len(b); i++ {
+		if b[i] == math.MaxUint64 {
+			continue
+		}
+		// replace this with TrailingZero64() when gobgp drops go 1.8 support.
+		for j := 0; j < 64; j++ {
+			v := ^b[i]
+			if v&(1<<uint64(j)) > 0 {
+				r := i*64 + j
+				b.Flag(uint(r))
+				return uint(r)
+			}
+		}
+	}
+	return 0
+}
+
 func NewBitmap(size int) Bitmap {
 	return Bitmap(make([]uint64, (size+64-1)/64))
 }
diff --git a/table/table.go b/table/table.go
index c1ed3a29..6e423808 100644
--- a/table/table.go
+++ b/table/table.go
@@ -218,6 +218,9 @@ func (t *Table) getOrCreateDest(nlri bgp.AddrPrefixInterface) *Destination {
 			"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)
 		t.setDestination(tableKey, dest)
 	}
 	return dest