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