summaryrefslogtreecommitdiffhomepage
path: root/table
diff options
context:
space:
mode:
Diffstat (limited to 'table')
-rw-r--r--table/adj.go2
-rw-r--r--table/destination.go18
-rw-r--r--table/destination_test.go35
-rw-r--r--table/path.go45
-rw-r--r--table/table.go5
-rw-r--r--table/table_test.go10
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)
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-15 11:39:20 +0000