preparation for shrinking Destination structure

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

5 files changed, 119 insertions, 221 deletions

diff --git a/table/destination.go b/table/destination.go
index 32169f59..6dac57db 100644
--- a/table/destination.go
+++ b/table/destination.go
@@ -353,16 +353,6 @@ func (dd *Destination) GetChanges(id string, as uint32, peerDown bool) (*Path, *
 	return best, old, multi
 }
 
-func (dd *Destination) AddWithdraw(withdraw *Path) {
-	dd.validatePath(withdraw)
-	dd.withdrawList = append(dd.withdrawList, withdraw)
-}
-
-func (dd *Destination) AddNewPath(newPath *Path) {
-	dd.validatePath(newPath)
-	dd.newPathList = append(dd.newPathList, newPath)
-}
-
 func (dd *Destination) validatePath(path *Path) {
 	if path == nil || path.GetRouteFamily() != dd.routeFamily {
 
@@ -379,21 +369,25 @@ func (dd *Destination) validatePath(path *Path) {
 //
 // Modifies destination's state related to stored paths. Removes withdrawn
 // paths from known paths. Also, adds new paths to known paths.
-func (dest *Destination) Calculate() *Destination {
-	oldKnownPathList := dest.knownPathList
-	newPathList := dest.newPathList
-	// First remove the withdrawn paths.
-	withdrawn := dest.explicitWithdraw()
-	// Do implicit withdrawal
-	dest.implicitWithdraw()
-
-	for _, path := range withdrawn {
-		if id := path.GetNlri().PathLocalIdentifier(); id != 0 {
-			dest.localIdMap.Unflag(uint(id))
+func (dest *Destination) Calculate(newPath *Path) *Destination {
+	oldKnownPathList := make([]*Path, len(dest.knownPathList))
+	copy(oldKnownPathList, dest.knownPathList)
+	newPathList := make([]*Path, 0)
+	withdrawList := make([]*Path, 0)
+
+	if newPath.IsWithdraw {
+		p := dest.explicitWithdraw(newPath)
+		if p != nil {
+			if id := p.GetNlri().PathLocalIdentifier(); id != 0 {
+				dest.localIdMap.Unflag(uint(id))
+			}
 		}
+		withdrawList = append(withdrawList, newPath)
+	} else {
+		dest.implicitWithdraw(newPath)
+		dest.knownPathList = append(dest.knownPathList, newPath)
+		newPathList = append(newPathList, newPath)
 	}
-	// Collect all new paths into known paths.
-	dest.knownPathList = append(dest.knownPathList, dest.newPathList...)
 
 	for _, path := range dest.knownPathList {
 		if path.GetNlri().PathLocalIdentifier() == 0 {
@@ -405,8 +399,6 @@ func (dest *Destination) Calculate() *Destination {
 			path.GetNlri().SetPathLocalIdentifier(uint32(id))
 		}
 	}
-	// Clear new paths as we copied them.
-	dest.newPathList = make([]*Path, 0)
 	// Compute new best path
 	dest.computeKnownBestPath()
 
@@ -416,7 +408,7 @@ func (dest *Destination) Calculate() *Destination {
 		knownPathList:    dest.knownPathList,
 		oldKnownPathList: oldKnownPathList,
 		newPathList:      newPathList,
-		withdrawList:     withdrawn,
+		withdrawList:     withdrawList,
 	}
 }
 
@@ -428,113 +420,76 @@ func (dest *Destination) Calculate() *Destination {
 // we can receive withdraws for such paths and withdrawals may not be
 // stopped by the same policies.
 //
-func (dest *Destination) explicitWithdraw() paths {
-
-	// If we have no withdrawals, we have nothing to do.
-	if len(dest.withdrawList) == 0 {
-		return nil
-	}
-
+func (dest *Destination) explicitWithdraw(withdraw *Path) *Path {
 	log.WithFields(log.Fields{
-		"Topic":  "Table",
-		"Key":    dest.GetNlri().String(),
-		"Length": len(dest.withdrawList),
+		"Topic": "Table",
+		"Key":   dest.GetNlri().String(),
 	}).Debug("Removing withdrawals")
 
 	// If we have some withdrawals and no know-paths, it means it is safe to
 	// delete these withdraws.
 	if len(dest.knownPathList) == 0 {
 		log.WithFields(log.Fields{
-			"Topic":  "Table",
-			"Key":    dest.GetNlri().String(),
-			"Length": len(dest.withdrawList),
+			"Topic": "Table",
+			"Key":   dest.GetNlri().String(),
 		}).Debug("Found withdrawals for path(s) that did not get installed")
-		dest.withdrawList = []*Path{}
 		return nil
 	}
 
-	// If we have some known paths and some withdrawals, we find matches and
-	// delete them first.
-	matches := make([]*Path, 0, len(dest.withdrawList)/2)
-	newKnownPaths := make([]*Path, 0, len(dest.knownPathList)/2)
-
 	// Match all withdrawals from destination paths.
-	for _, withdraw := range dest.withdrawList {
-		isFound := false
-		for _, path := range dest.knownPathList {
-			// We have a match if the source and path-id are same.
-			if path.GetSource().Equal(withdraw.GetSource()) && path.GetNlri().PathIdentifier() == withdraw.GetNlri().PathIdentifier() {
-				isFound = true
-				// this path is referenced in peer's adj-rib-in
-				// when there was no policy modification applied.
-				// we could flag IsWithdraw down after use to avoid
-				// a path with IsWithdraw flag exists in adj-rib-in
-				path.IsWithdraw = true
-				withdraw.GetNlri().SetPathLocalIdentifier(path.GetNlri().PathLocalIdentifier())
-				matches = append(matches, withdraw)
-			}
-		}
-
-		// We do no have any match for this withdraw.
-		if !isFound {
-			log.WithFields(log.Fields{
-				"Topic": "Table",
-				"Key":   dest.GetNlri().String(),
-				"Path":  withdraw,
-			}).Warn("No matching path for withdraw found, may be path was not installed into table")
+	isFound := -1
+	for i, path := range dest.knownPathList {
+		// We have a match if the source and path-id are same.
+		if path.GetSource().Equal(withdraw.GetSource()) && path.GetNlri().PathIdentifier() == withdraw.GetNlri().PathIdentifier() {
+			isFound = i
+			withdraw.GetNlri().SetPathLocalIdentifier(path.GetNlri().PathLocalIdentifier())
 		}
 	}
 
-	for _, path := range dest.knownPathList {
-		if !path.IsWithdraw {
-			newKnownPaths = append(newKnownPaths, path)
-		}
-		// here we flag IsWithdraw down
-		path.IsWithdraw = false
+	// We do no have any match for this withdraw.
+	if isFound == -1 {
+		log.WithFields(log.Fields{
+			"Topic": "Table",
+			"Key":   dest.GetNlri().String(),
+			"Path":  withdraw,
+		}).Warn("No matching path for withdraw found, may be path was not installed into table")
+		return nil
+	} else {
+		p := dest.knownPathList[isFound]
+		dest.knownPathList = append(dest.knownPathList[:isFound], dest.knownPathList[isFound+1:]...)
+		return p
 	}
-
-	dest.knownPathList = newKnownPaths
-	dest.withdrawList = make([]*Path, 0)
-	return matches
 }
 
 // Identifies which of known paths are old and removes them.
 //
 // Known paths will no longer have paths whose new version is present in
 // new paths.
-func (dest *Destination) implicitWithdraw() paths {
-	newKnownPaths := make([]*Path, 0, len(dest.knownPathList))
-	implicitWithdrawn := make([]*Path, 0, len(dest.knownPathList))
-	for _, path := range dest.knownPathList {
-		found := false
-		for _, newPath := range dest.newPathList {
-			if newPath.NoImplicitWithdraw() {
-				continue
-			}
-			// Here we just check if source is same and not check if path
-			// version num. as newPaths are implicit withdrawal of old
-			// paths and when doing RouteRefresh (not EnhancedRouteRefresh)
-			// we get same paths again.
-			if newPath.GetSource().Equal(path.GetSource()) && newPath.GetNlri().PathIdentifier() == path.GetNlri().PathIdentifier() {
-				log.WithFields(log.Fields{
-					"Topic": "Table",
-					"Key":   dest.GetNlri().String(),
-					"Path":  path,
-				}).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
-			}
+func (dest *Destination) implicitWithdraw(newPath *Path) {
+	found := -1
+	for i, path := range dest.knownPathList {
+		if newPath.NoImplicitWithdraw() {
+			continue
 		}
-		if found {
-			implicitWithdrawn = append(implicitWithdrawn, path)
-		} else {
-			newKnownPaths = append(newKnownPaths, path)
+		// Here we just check if source is same and not check if path
+		// version num. as newPaths are implicit withdrawal of old
+		// paths and when doing RouteRefresh (not EnhancedRouteRefresh)
+		// we get same paths again.
+		if newPath.GetSource().Equal(path.GetSource()) && newPath.GetNlri().PathIdentifier() == path.GetNlri().PathIdentifier() {
+			log.WithFields(log.Fields{
+				"Topic": "Table",
+				"Key":   dest.GetNlri().String(),
+				"Path":  path,
+			}).Debug("Implicit withdrawal of old path, since we have learned new path from the same peer")
+
+			found = i
+			newPath.GetNlri().SetPathLocalIdentifier(path.GetNlri().PathLocalIdentifier())
+			break
 		}
 	}
-	dest.knownPathList = newKnownPaths
-	return implicitWithdrawn
+	if found != -1 {
+		dest.knownPathList = append(dest.knownPathList[:found], dest.knownPathList[found+1:]...)
+	}
 }
 
 func (dest *Destination) computeKnownBestPath() (*Path, BestPathReason, error) {
diff --git a/table/destination_test.go b/table/destination_test.go
index f488d4ac..0934057a 100644
--- a/table/destination_test.go
+++ b/table/destination_test.go
@@ -82,8 +82,7 @@ func TestCalculate2(t *testing.T) {
 	path1 := ProcessMessage(update1, peer1, time.Now())[0]
 
 	d := NewDestination(nlri, 0)
-	d.AddNewPath(path1)
-	d.Calculate()
+	d.Calculate(path1)
 
 	// suppose peer2 sends grammaatically correct but semantically flawed update message
 	// which has a withdrawal nlri not advertised before
@@ -92,8 +91,7 @@ func TestCalculate2(t *testing.T) {
 	path2 := ProcessMessage(update2, peer2, time.Now())[0]
 	assert.Equal(t, path2.IsWithdraw, true)
 
-	d.AddWithdraw(path2)
-	d.Calculate()
+	d.Calculate(path2)
 
 	// we have a path from peer1 here
 	assert.Equal(t, len(d.knownPathList), 1)
@@ -103,8 +101,7 @@ func TestCalculate2(t *testing.T) {
 	path3 := ProcessMessage(update3, peer2, time.Now())[0]
 	assert.Equal(t, path3.IsWithdraw, false)
 
-	d.AddNewPath(path3)
-	d.Calculate()
+	d.Calculate(path3)
 
 	// this time, we have paths from peer1 and peer2
 	assert.Equal(t, len(d.knownPathList), 2)
@@ -114,8 +111,7 @@ func TestCalculate2(t *testing.T) {
 	update4 := bgp.NewBGPUpdateMessage(nil, pathAttributes, []*bgp.IPAddrPrefix{nlri})
 	path4 := ProcessMessage(update4, peer3, time.Now())[0]
 
-	d.AddNewPath(path4)
-	d.Calculate()
+	d.Calculate(path4)
 
 	// we must have paths from peer1, peer2 and peer3
 	assert.Equal(t, len(d.knownPathList), 3)
@@ -193,10 +189,8 @@ func TestTimeTieBreaker(t *testing.T) {
 	path2 := ProcessMessage(updateMsg, peer2, time.Now().Add(-1*time.Hour))[0]                 // older than path1
 
 	d := NewDestination(nlri, 0)
-	d.AddNewPath(path1)
-	d.AddNewPath(path2)
-
-	d.Calculate()
+	d.Calculate(path1)
+	d.Calculate(path2)
 
 	assert.Equal(t, len(d.knownPathList), 2)
 	assert.Equal(t, true, d.GetBestPath("", 0).GetSource().ID.Equal(net.IP{2, 2, 2, 2})) // path from peer2 win
@@ -204,10 +198,8 @@ func TestTimeTieBreaker(t *testing.T) {
 	// this option disables tie breaking by age
 	SelectionOptions.ExternalCompareRouterId = true
 	d = NewDestination(nlri, 0)
-	d.AddNewPath(path1)
-	d.AddNewPath(path2)
-
-	d.Calculate()
+	d.Calculate(path1)
+	d.Calculate(path2)
 
 	assert.Equal(t, len(d.knownPathList), 2)
 	assert.Equal(t, true, d.GetBestPath("", 0).GetSource().ID.Equal(net.IP{1, 1, 1, 1})) // path from peer1 win
@@ -361,18 +353,16 @@ func TestMultipath(t *testing.T) {
 	path2 := ProcessMessage(updateMsg, peer2, time.Now())[0]
 
 	d := NewDestination(nlri[0], 0)
-	d.AddNewPath(path1)
-	d.AddNewPath(path2)
+	d.Calculate(path2)
 
-	best, old, multi := d.Calculate().GetChanges(GLOBAL_RIB_NAME, 0, false)
+	best, old, multi := d.Calculate(path1).GetChanges(GLOBAL_RIB_NAME, 0, false)
 	assert.NotNil(t, best)
-	assert.Equal(t, old, (*Path)(nil))
+	assert.Equal(t, old, path2)
 	assert.Equal(t, len(multi), 2)
 	assert.Equal(t, len(d.GetKnownPathList(GLOBAL_RIB_NAME, 0)), 2)
 
 	path3 := path2.Clone(true)
-	d.AddWithdraw(path3)
-	dd := d.Calculate()
+	dd := d.Calculate(path3)
 	best, old, multi = dd.GetChanges(GLOBAL_RIB_NAME, 0, false)
 	assert.Nil(t, best)
 	assert.Equal(t, old, path1)
@@ -390,9 +380,8 @@ func TestMultipath(t *testing.T) {
 	}
 	updateMsg = bgp.NewBGPUpdateMessage(nil, pathAttributes, nlri)
 	path4 := ProcessMessage(updateMsg, peer3, time.Now())[0]
-	d.AddNewPath(path4)
-
-	best, _, multi = d.Calculate().GetChanges(GLOBAL_RIB_NAME, 0, false)
+	dd = d.Calculate(path4)
+	best, _, multi = dd.GetChanges(GLOBAL_RIB_NAME, 0, false)
 	assert.NotNil(t, best)
 	assert.Equal(t, len(multi), 1)
 	assert.Equal(t, len(d.GetKnownPathList(GLOBAL_RIB_NAME, 0)), 2)
@@ -406,9 +395,7 @@ func TestMultipath(t *testing.T) {
 	}
 	updateMsg = bgp.NewBGPUpdateMessage(nil, pathAttributes, nlri)
 	path5 := ProcessMessage(updateMsg, peer2, time.Now())[0]
-	d.AddNewPath(path5)
-
-	best, _, multi = d.Calculate().GetChanges(GLOBAL_RIB_NAME, 0, false)
+	best, _, multi = d.Calculate(path5).GetChanges(GLOBAL_RIB_NAME, 0, false)
 	assert.NotNil(t, best)
 	assert.Equal(t, len(multi), 2)
 	assert.Equal(t, len(d.GetKnownPathList(GLOBAL_RIB_NAME, 0)), 3)
diff --git a/table/table.go b/table/table.go
index 6662376e..6bc88149 100644
--- a/table/table.go
+++ b/table/table.go
@@ -69,37 +69,6 @@ func (t *Table) GetRoutefamily() bgp.RouteFamily {
 	return t.routeFamily
 }
 
-func (t *Table) insert(path *Path) *Destination {
-	t.validatePath(path)
-	dest := t.getOrCreateDest(path.GetNlri())
-
-	if path.IsWithdraw {
-		// withdraw insert
-		dest.AddWithdraw(path)
-	} else {
-		// path insert
-		dest.AddNewPath(path)
-	}
-	return dest
-}
-
-func (t *Table) DeleteDestByPeer(peerInfo *PeerInfo) []*Destination {
-	dsts := []*Destination{}
-	for _, dst := range t.destinations {
-		match := false
-		for _, p := range dst.knownPathList {
-			if p.GetSource().Equal(peerInfo) {
-				dst.AddWithdraw(p)
-				match = true
-			}
-		}
-		if match {
-			dsts = append(dsts, dst)
-		}
-	}
-	return dsts
-}
-
 func (t *Table) deletePathsByVrf(vrf *Vrf) []*Path {
 	pathList := make([]*Path, 0)
 	for _, dest := range t.destinations {
diff --git a/table/table_manager.go b/table/table_manager.go
index 0e980404..e1accda7 100644
--- a/table/table_manager.go
+++ b/table/table_manager.go
@@ -180,65 +180,50 @@ func (manager *TableManager) DeleteVrf(name string) ([]*Path, error) {
 	return msgs, nil
 }
 
-func (manager *TableManager) calculate(dsts []*Destination) []*Destination {
-	emptyDsts := make([]*Destination, 0, len(dsts))
-	clonedDsts := make([]*Destination, 0, len(dsts))
-
-	for _, dst := range dsts {
-		log.WithFields(log.Fields{
-			"Topic": "table",
-			"Key":   dst.GetNlri().String(),
-		}).Debug("Processing destination")
-
-		clonedDsts = append(clonedDsts, dst.Calculate())
-
-		if len(dst.knownPathList) == 0 {
-			emptyDsts = append(emptyDsts, dst)
-		}
-	}
-
-	for _, dst := range emptyDsts {
-		t := manager.Tables[dst.Family()]
+func (tm *TableManager) update(newPath *Path) *Destination {
+	t := tm.Tables[newPath.GetRouteFamily()]
+	t.validatePath(newPath)
+	dst := t.getOrCreateDest(newPath.GetNlri())
+	d := dst.Calculate(newPath)
+	if len(dst.knownPathList) == 0 {
 		t.deleteDest(dst)
 	}
-	return clonedDsts
+	return d
 }
 
-func (manager *TableManager) DeletePathsByPeer(info *PeerInfo, rf bgp.RouteFamily) []*Destination {
+func (manager *TableManager) GetPathListByPeer(info *PeerInfo, rf bgp.RouteFamily) []*Path {
 	if t, ok := manager.Tables[rf]; ok {
-		dsts := t.DeleteDestByPeer(info)
-		return manager.calculate(dsts)
+		pathList := make([]*Path, 0, len(t.destinations))
+		for _, dst := range t.destinations {
+			for _, p := range dst.knownPathList {
+				if p.GetSource().Equal(info) {
+					pathList = append(pathList, p)
+				}
+			}
+		}
+		return pathList
 	}
 	return nil
 }
 
-func (manager *TableManager) ProcessPaths(pathList []*Path) []*Destination {
-	m := make(map[string]bool, len(pathList))
-	dsts := make([]*Destination, 0, len(pathList))
-	for _, path := range pathList {
-		if path == nil || path.IsEOR() {
-			continue
-		}
-		rf := path.GetRouteFamily()
-		if t, ok := manager.Tables[rf]; ok {
-			dst := t.insert(path)
-			key := dst.GetNlri().String()
-			if !m[key] {
-				m[key] = true
-				dsts = append(dsts, dst)
-			}
-			if rf == bgp.RF_EVPN {
-				for _, dst := range manager.handleMacMobility(path) {
-					key := dst.GetNlri().String()
-					if !m[key] {
-						m[key] = true
-						dsts = append(dsts, dst)
-					}
-				}
+func (manager *TableManager) Update(newPath *Path) []*Destination {
+	if newPath == nil || newPath.IsEOR() {
+		return nil
+	}
+
+	// normally, we'll have one destination.
+	dsts := make([]*Destination, 0, 1)
+	family := newPath.GetRouteFamily()
+	if _, ok := manager.Tables[family]; ok {
+		dsts = append(dsts, manager.update(newPath))
+
+		if family == bgp.RF_EVPN {
+			for _, p := range manager.handleMacMobility(newPath) {
+				dsts = append(dsts, manager.update(p))
 			}
 		}
 	}
-	return manager.calculate(dsts)
+	return dsts
 }
 
 // EVPN MAC MOBILITY HANDLING
@@ -249,8 +234,8 @@ func (manager *TableManager) ProcessPaths(pathList []*Path) []*Destination {
 // different Ethernet segment identifier and a higher sequence number
 // than that which it had previously advertised withdraws its MAC/IP
 // Advertisement route.
-func (manager *TableManager) handleMacMobility(path *Path) []*Destination {
-	dsts := make([]*Destination, 0)
+func (manager *TableManager) handleMacMobility(path *Path) []*Path {
+	pathList := make([]*Path, 0)
 	nlri := path.GetNlri().(*bgp.EVPNNLRI)
 	if path.IsWithdraw || path.IsLocal() || nlri.RouteType != bgp.EVPN_ROUTE_TYPE_MAC_IP_ADVERTISEMENT {
 		return nil
@@ -275,12 +260,10 @@ func (manager *TableManager) handleMacMobility(path *Path) []*Destination {
 		e1, m1, s1 := f(path)
 		e2, m2, s2 := f(path2)
 		if bytes.Equal(m1, m2) && !bytes.Equal(e1.Value, e2.Value) && s1 > s2 {
-			path2.IsWithdraw = true
-			dsts = append(dsts, manager.Tables[bgp.RF_EVPN].insert(path2))
-			break
+			pathList = append(pathList, path2.Clone(true))
 		}
 	}
-	return dsts
+	return pathList
 }
 
 func (manager *TableManager) tables(list ...bgp.RouteFamily) []*Table {
diff --git a/table/table_manager_test.go b/table/table_manager_test.go
index 3e2d1e74..3c07dd53 100644
--- a/table/table_manager_test.go
+++ b/table/table_manager_test.go
@@ -31,7 +31,11 @@ import (
 // this function processes only BGPUpdate
 func (manager *TableManager) ProcessUpdate(fromPeer *PeerInfo, message *bgp.BGPMessage) ([]*Path, error) {
 	pathList := make([]*Path, 0)
-	for _, d := range manager.ProcessPaths(ProcessMessage(message, fromPeer, time.Now())) {
+	dsts := make([]*Destination, 0)
+	for _, path := range ProcessMessage(message, fromPeer, time.Now()) {
+		dsts = append(dsts, manager.Update(path)...)
+	}
+	for _, d := range dsts {
 		b, _, _ := d.GetChanges(GLOBAL_RIB_NAME, 0, false)
 		pathList = append(pathList, b)
 	}