table: remove withdraw/newPath/oldPath Lists in Destination

Shrink memory usage.

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

5 files changed, 210 insertions, 236 deletions

diff --git a/server/server.go b/server/server.go
index e766d84e..30fb9c22 100644
--- a/server/server.go
+++ b/server/server.go
@@ -701,7 +701,7 @@ func (server *BgpServer) dropPeerAllRoutes(peer *Peer, families []bgp.RouteFamil
 	}
 }
 
-func dstsToPaths(id string, as uint32, dsts []*table.Destination) ([]*table.Path, []*table.Path, [][]*table.Path) {
+func dstsToPaths(id string, as uint32, dsts []*table.Update) ([]*table.Path, []*table.Path, [][]*table.Path) {
 	bestList := make([]*table.Path, 0, len(dsts))
 	oldList := make([]*table.Path, 0, len(dsts))
 	mpathList := make([][]*table.Path, 0, len(dsts))
@@ -717,7 +717,7 @@ func dstsToPaths(id string, as uint32, dsts []*table.Destination) ([]*table.Path
 	return bestList, oldList, mpathList
 }
 
-func (server *BgpServer) propagateUpdateToNeighbors(source *Peer, newPath *table.Path, dsts []*table.Destination, needOld bool) {
+func (server *BgpServer) propagateUpdateToNeighbors(source *Peer, newPath *table.Path, dsts []*table.Update, needOld bool) {
 	if table.SelectionOptions.DisableBestPathSelection {
 		return
 	}
diff --git a/server/server_test.go b/server/server_test.go
index 720202d0..0bbd4070 100644
--- a/server/server_test.go
+++ b/server/server_test.go
@@ -269,7 +269,7 @@ func newPeerandInfo(myAs, as uint32, address string, rib *table.TableManager) (*
 }
 
 func process(rib *table.TableManager, l []*table.Path) (*table.Path, *table.Path) {
-	dsts := make([]*table.Destination, 0)
+	dsts := make([]*table.Update, 0)
 	for _, path := range l {
 		dsts = append(dsts, rib.Update(path)...)
 	}
diff --git a/table/destination.go b/table/destination.go
index 6dac57db..44f65e7f 100644
--- a/table/destination.go
+++ b/table/destination.go
@@ -166,14 +166,11 @@ func NewPeerInfo(g *config.Global, p *config.Neighbor) *PeerInfo {
 }
 
 type Destination struct {
-	routeFamily      bgp.RouteFamily
-	nlri             bgp.AddrPrefixInterface
-	knownPathList    paths
-	withdrawList     paths
-	newPathList      paths
-	oldKnownPathList paths
-	RadixKey         string
-	localIdMap       *Bitmap
+	routeFamily   bgp.RouteFamily
+	nlri          bgp.AddrPrefixInterface
+	knownPathList []*Path
+	RadixKey      string
+	localIdMap    *Bitmap
 }
 
 func NewDestination(nlri bgp.AddrPrefixInterface, mapSize int, known ...*Path) *Destination {
@@ -181,8 +178,6 @@ func NewDestination(nlri bgp.AddrPrefixInterface, mapSize int, known ...*Path) *
 		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.
@@ -243,8 +238,8 @@ func (dd *Destination) GetKnownPathList(id string, as uint32) []*Path {
 	return list
 }
 
-func getBestPath(id string, as uint32, pathList *paths) *Path {
-	for _, p := range *pathList {
+func getBestPath(id string, as uint32, pathList []*Path) *Path {
+	for _, p := range pathList {
 		if rsFilter(id, as, p) {
 			continue
 		}
@@ -257,100 +252,11 @@ func getBestPath(id string, as uint32, pathList *paths) *Path {
 }
 
 func (dd *Destination) GetBestPath(id string, as uint32) *Path {
-	return getBestPath(id, as, &dd.knownPathList)
-}
-
-func getMultiBestPath(id string, pathList *paths) []*Path {
-	list := make([]*Path, 0, len(*pathList))
-	var best *Path
-	for _, p := range *pathList {
-		if !p.IsNexthopInvalid {
-			if best == nil {
-				best = p
-				list = append(list, p)
-			} else if best.Compare(p) == 0 {
-				list = append(list, p)
-			}
-		}
-	}
-	return list
+	return getBestPath(id, as, dd.knownPathList)
 }
 
 func (dd *Destination) GetMultiBestPath(id string) []*Path {
-	return getMultiBestPath(id, &dd.knownPathList)
-}
-
-func (dd *Destination) GetAddPathChanges(id string) []*Path {
-	l := make([]*Path, 0, len(dd.newPathList)+len(dd.withdrawList))
-	for _, p := range dd.newPathList {
-		l = append(l, p)
-	}
-	for _, p := range dd.withdrawList {
-		l = append(l, p.Clone(true))
-	}
-	return l
-}
-
-func (dd *Destination) GetChanges(id string, as uint32, peerDown bool) (*Path, *Path, []*Path) {
-	best, old := func(id string) (*Path, *Path) {
-		old := getBestPath(id, as, &dd.oldKnownPathList)
-		best := dd.GetBestPath(id, as)
-		if best != nil && best.Equal(old) {
-			// RFC4684 3.2. Intra-AS VPN Route Distribution
-			// When processing RT membership NLRIs received from internal iBGP
-			// peers, it is necessary to consider all available iBGP paths for a
-			// given RT prefix, for building the outbound route filter, and not just
-			// the best path.
-			if best.GetRouteFamily() == bgp.RF_RTC_UC {
-				return best, old
-			}
-			// For BGP Nexthop Tracking, checks if the nexthop reachability
-			// was changed or not.
-			if best.IsNexthopInvalid != old.IsNexthopInvalid {
-				return best, old
-			}
-			return nil, old
-		}
-		if best == nil {
-			if old == nil {
-				return nil, nil
-			}
-			if peerDown {
-				// withdraws were generated by peer
-				// down so paths are not in knowpath
-				// or adjin.
-				old.IsWithdraw = true
-				return old, old
-			}
-			return old.Clone(true), old
-		}
-		return best, old
-	}(id)
-
-	var multi []*Path
-
-	if id == GLOBAL_RIB_NAME && UseMultiplePaths.Enabled {
-		diff := func(lhs, rhs []*Path) bool {
-			if len(lhs) != len(rhs) {
-				return true
-			}
-			for idx, l := range lhs {
-				if !l.Equal(rhs[idx]) {
-					return true
-				}
-			}
-			return false
-		}
-		oldM := getMultiBestPath(id, &dd.oldKnownPathList)
-		newM := dd.GetMultiBestPath(id)
-		if diff(oldM, newM) {
-			multi = newM
-			if len(newM) == 0 {
-				multi = []*Path{best}
-			}
-		}
-	}
-	return best, old, multi
+	return getMultiBestPath(id, dd.knownPathList)
 }
 
 func (dd *Destination) validatePath(path *Path) {
@@ -369,11 +275,9 @@ 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(newPath *Path) *Destination {
+func (dest *Destination) Calculate(newPath *Path) *Update {
 	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)
@@ -382,11 +286,9 @@ func (dest *Destination) Calculate(newPath *Path) *Destination {
 				dest.localIdMap.Unflag(uint(id))
 			}
 		}
-		withdrawList = append(withdrawList, newPath)
 	} else {
 		dest.implicitWithdraw(newPath)
 		dest.knownPathList = append(dest.knownPathList, newPath)
-		newPathList = append(newPathList, newPath)
 	}
 
 	for _, path := range dest.knownPathList {
@@ -402,13 +304,11 @@ func (dest *Destination) Calculate(newPath *Path) *Destination {
 	// Compute new best path
 	dest.computeKnownBestPath()
 
-	return &Destination{
-		routeFamily:      dest.routeFamily,
-		nlri:             dest.nlri,
-		knownPathList:    dest.knownPathList,
-		oldKnownPathList: oldKnownPathList,
-		newPathList:      newPathList,
-		withdrawList:     withdrawList,
+	l := make([]*Path, len(dest.knownPathList))
+	copy(l, dest.knownPathList)
+	return &Update{
+		KnownPathList:    l,
+		OldKnownPathList: oldKnownPathList,
 	}
 }
 
@@ -521,7 +421,7 @@ func (dest *Destination) computeKnownBestPath() (*Path, BestPathReason, error) {
 		}
 		return dest.knownPathList[0], BPR_ONLY_PATH, nil
 	}
-	sort.Sort(dest.knownPathList)
+	dest.sort()
 	newBest := dest.knownPathList[0]
 	// If the first path has the invalidated next-hop, which evaluated by IGP,
 	// returns no path with the reason of the next-hop reachability.
@@ -531,123 +431,197 @@ func (dest *Destination) computeKnownBestPath() (*Path, BestPathReason, error) {
 	return newBest, newBest.reason, nil
 }
 
-type paths []*Path
+func (dst *Destination) sort() {
+	sort.SliceStable(dst.knownPathList, func(i, j int) bool {
+		//Compares given paths and returns best path.
+		//
+		//Parameters:
+		//	-`path1`: first path to compare
+		//	-`path2`: second path to compare
+		//
+		//	Best path processing will involve following steps:
+		//	1.  Select a path with a reachable next hop.
+		//	2.  Select the path with the highest weight.
+		//	3.  If path weights are the same, select the path with the highest
+		//	local preference value.
+		//	4.  Prefer locally originated routes (network routes, redistributed
+		//	routes, or aggregated routes) over received routes.
+		//	5.  Select the route with the shortest AS-path length.
+		//	6.  If all paths have the same AS-path length, select the path based
+		//	on origin: IGP is preferred over EGP; EGP is preferred over
+		//	Incomplete.
+		//	7.  If the origins are the same, select the path with lowest MED
+		//	value.
+		//	8.  If the paths have the same MED values, select the path learned
+		//	via EBGP over one learned via IBGP.
+		//	9.  Select the route with the lowest IGP cost to the next hop.
+		//	10. Select the route received from the peer with the lowest BGP
+		//	router ID.
+		//
+		//	Returns None if best-path among given paths cannot be computed else best
+		//	path.
+		//	Assumes paths from NC has source equal to None.
+		//
+
+		path1 := dst.knownPathList[i]
+		path2 := dst.knownPathList[j]
+
+		var better *Path
+		reason := BPR_UNKNOWN
+
+		// draft-uttaro-idr-bgp-persistence-02
+		if better == nil {
+			better = compareByLLGRStaleCommunity(path1, path2)
+			reason = BPR_NON_LLGR_STALE
+		}
+		// Follow best path calculation algorithm steps.
+		// compare by reachability
+		if better == nil {
+			better = compareByReachableNexthop(path1, path2)
+			reason = BPR_REACHABLE_NEXT_HOP
+		}
+		if better == nil {
+			better = compareByHighestWeight(path1, path2)
+			reason = BPR_HIGHEST_WEIGHT
+		}
+		if better == nil {
+			better = compareByLocalPref(path1, path2)
+			reason = BPR_LOCAL_PREF
+		}
+		if better == nil {
+			better = compareByLocalOrigin(path1, path2)
+			reason = BPR_LOCAL_ORIGIN
+		}
+		if better == nil {
+			better = compareByASPath(path1, path2)
+			reason = BPR_ASPATH
+		}
+		if better == nil {
+			better = compareByOrigin(path1, path2)
+			reason = BPR_ORIGIN
+		}
+		if better == nil {
+			better = compareByMED(path1, path2)
+			reason = BPR_MED
+		}
+		if better == nil {
+			better = compareByASNumber(path1, path2)
+			reason = BPR_ASN
+		}
+		if better == nil {
+			better = compareByIGPCost(path1, path2)
+			reason = BPR_IGP_COST
+		}
+		if better == nil {
+			better = compareByAge(path1, path2)
+			reason = BPR_OLDER
+		}
+		if better == nil {
+			var e error = nil
+			better, e = compareByRouterID(path1, path2)
+			if e != nil {
+				log.WithFields(log.Fields{
+					"Topic": "Table",
+					"Error": e,
+				}).Error("Could not get best path by comparing router ID")
+			}
+			reason = BPR_ROUTER_ID
+		}
+		if better == nil {
+			reason = BPR_UNKNOWN
+			better = path1
+		}
 
-func (p paths) Len() int {
-	return len(p)
-}
+		better.reason = reason
 
-func (p paths) Swap(i, j int) {
-	p[i], p[j] = p[j], p[i]
+		if better == path1 {
+			return true
+		}
+		return false
+	})
 }
 
-func (p paths) Less(i, j int) bool {
-
-	//Compares given paths and returns best path.
-	//
-	//Parameters:
-	//	-`path1`: first path to compare
-	//	-`path2`: second path to compare
-	//
-	//	Best path processing will involve following steps:
-	//	1.  Select a path with a reachable next hop.
-	//	2.  Select the path with the highest weight.
-	//	3.  If path weights are the same, select the path with the highest
-	//	local preference value.
-	//	4.  Prefer locally originated routes (network routes, redistributed
-	//	routes, or aggregated routes) over received routes.
-	//	5.  Select the route with the shortest AS-path length.
-	//	6.  If all paths have the same AS-path length, select the path based
-	//	on origin: IGP is preferred over EGP; EGP is preferred over
-	//	Incomplete.
-	//	7.  If the origins are the same, select the path with lowest MED
-	//	value.
-	//	8.  If the paths have the same MED values, select the path learned
-	//	via EBGP over one learned via IBGP.
-	//	9.  Select the route with the lowest IGP cost to the next hop.
-	//	10. Select the route received from the peer with the lowest BGP
-	//	router ID.
-	//
-	//	Returns None if best-path among given paths cannot be computed else best
-	//	path.
-	//	Assumes paths from NC has source equal to None.
-	//
-
-	path1 := p[i]
-	path2 := p[j]
-
-	var better *Path
-	reason := BPR_UNKNOWN
+type Update struct {
+	KnownPathList    []*Path
+	OldKnownPathList []*Path
+}
 
-	// draft-uttaro-idr-bgp-persistence-02
-	if better == nil {
-		better = compareByLLGRStaleCommunity(path1, path2)
-		reason = BPR_NON_LLGR_STALE
-	}
-	// Follow best path calculation algorithm steps.
-	// compare by reachability
-	if better == nil {
-		better = compareByReachableNexthop(path1, path2)
-		reason = BPR_REACHABLE_NEXT_HOP
-	}
-	if better == nil {
-		better = compareByHighestWeight(path1, path2)
-		reason = BPR_HIGHEST_WEIGHT
-	}
-	if better == nil {
-		better = compareByLocalPref(path1, path2)
-		reason = BPR_LOCAL_PREF
-	}
-	if better == nil {
-		better = compareByLocalOrigin(path1, path2)
-		reason = BPR_LOCAL_ORIGIN
-	}
-	if better == nil {
-		better = compareByASPath(path1, path2)
-		reason = BPR_ASPATH
-	}
-	if better == nil {
-		better = compareByOrigin(path1, path2)
-		reason = BPR_ORIGIN
-	}
-	if better == nil {
-		better = compareByMED(path1, path2)
-		reason = BPR_MED
-	}
-	if better == nil {
-		better = compareByASNumber(path1, path2)
-		reason = BPR_ASN
-	}
-	if better == nil {
-		better = compareByIGPCost(path1, path2)
-		reason = BPR_IGP_COST
-	}
-	if better == nil {
-		better = compareByAge(path1, path2)
-		reason = BPR_OLDER
-	}
-	if better == nil {
-		var e error = nil
-		better, e = compareByRouterID(path1, path2)
-		if e != nil {
-			log.WithFields(log.Fields{
-				"Topic": "Table",
-				"Error": e,
-			}).Error("Could not get best path by comparing router ID")
+func getMultiBestPath(id string, pathList []*Path) []*Path {
+	list := make([]*Path, 0, len(pathList))
+	var best *Path
+	for _, p := range pathList {
+		if !p.IsNexthopInvalid {
+			if best == nil {
+				best = p
+				list = append(list, p)
+			} else if best.Compare(p) == 0 {
+				list = append(list, p)
+			}
 		}
-		reason = BPR_ROUTER_ID
-	}
-	if better == nil {
-		reason = BPR_UNKNOWN
-		better = path1
 	}
+	return list
+}
 
-	better.reason = reason
+func (u *Update) GetChanges(id string, as uint32, peerDown bool) (*Path, *Path, []*Path) {
+	best, old := func(id string) (*Path, *Path) {
+		old := getBestPath(id, as, u.OldKnownPathList)
+		best := getBestPath(id, as, u.KnownPathList)
+		if best != nil && best.Equal(old) {
+			// RFC4684 3.2. Intra-AS VPN Route Distribution
+			// When processing RT membership NLRIs received from internal iBGP
+			// peers, it is necessary to consider all available iBGP paths for a
+			// given RT prefix, for building the outbound route filter, and not just
+			// the best path.
+			if best.GetRouteFamily() == bgp.RF_RTC_UC {
+				return best, old
+			}
+			// For BGP Nexthop Tracking, checks if the nexthop reachability
+			// was changed or not.
+			if best.IsNexthopInvalid != old.IsNexthopInvalid {
+				return best, old
+			}
+			return nil, old
+		}
+		if best == nil {
+			if old == nil {
+				return nil, nil
+			}
+			if peerDown {
+				// withdraws were generated by peer
+				// down so paths are not in knowpath
+				// or adjin.
+				old.IsWithdraw = true
+				return old, old
+			}
+			return old.Clone(true), old
+		}
+		return best, old
+	}(id)
 
-	if better == path1 {
-		return true
+	var multi []*Path
+
+	if id == GLOBAL_RIB_NAME && UseMultiplePaths.Enabled {
+		diff := func(lhs, rhs []*Path) bool {
+			if len(lhs) != len(rhs) {
+				return true
+			}
+			for idx, l := range lhs {
+				if !l.Equal(rhs[idx]) {
+					return true
+				}
+			}
+			return false
+		}
+		oldM := getMultiBestPath(id, u.OldKnownPathList)
+		newM := getMultiBestPath(id, u.KnownPathList)
+		if diff(oldM, newM) {
+			multi = newM
+			if len(newM) == 0 {
+				multi = []*Path{best}
+			}
+		}
 	}
-	return false
+	return best, old, multi
 }
 
 func compareByLLGRStaleCommunity(path1, path2 *Path) *Path {
diff --git a/table/table_manager.go b/table/table_manager.go
index e1accda7..29f36a23 100644
--- a/table/table_manager.go
+++ b/table/table_manager.go
@@ -180,15 +180,15 @@ func (manager *TableManager) DeleteVrf(name string) ([]*Path, error) {
 	return msgs, nil
 }
 
-func (tm *TableManager) update(newPath *Path) *Destination {
+func (tm *TableManager) update(newPath *Path) *Update {
 	t := tm.Tables[newPath.GetRouteFamily()]
 	t.validatePath(newPath)
 	dst := t.getOrCreateDest(newPath.GetNlri())
-	d := dst.Calculate(newPath)
+	u := dst.Calculate(newPath)
 	if len(dst.knownPathList) == 0 {
 		t.deleteDest(dst)
 	}
-	return d
+	return u
 }
 
 func (manager *TableManager) GetPathListByPeer(info *PeerInfo, rf bgp.RouteFamily) []*Path {
@@ -206,24 +206,24 @@ func (manager *TableManager) GetPathListByPeer(info *PeerInfo, rf bgp.RouteFamil
 	return nil
 }
 
-func (manager *TableManager) Update(newPath *Path) []*Destination {
+func (manager *TableManager) Update(newPath *Path) []*Update {
 	if newPath == nil || newPath.IsEOR() {
 		return nil
 	}
 
-	// normally, we'll have one destination.
-	dsts := make([]*Destination, 0, 1)
+	// Except for a special case with EVPN, we'll have one destination.
+	updates := make([]*Update, 0, 1)
 	family := newPath.GetRouteFamily()
 	if _, ok := manager.Tables[family]; ok {
-		dsts = append(dsts, manager.update(newPath))
+		updates = append(updates, manager.update(newPath))
 
 		if family == bgp.RF_EVPN {
 			for _, p := range manager.handleMacMobility(newPath) {
-				dsts = append(dsts, manager.update(p))
+				updates = append(updates, manager.update(p))
 			}
 		}
 	}
-	return dsts
+	return updates
 }
 
 // EVPN MAC MOBILITY HANDLING
diff --git a/table/table_manager_test.go b/table/table_manager_test.go
index 3c07dd53..53e226f8 100644
--- a/table/table_manager_test.go
+++ b/table/table_manager_test.go
@@ -31,7 +31,7 @@ import (
 // this function processes only BGPUpdate
 func (manager *TableManager) ProcessUpdate(fromPeer *PeerInfo, message *bgp.BGPMessage) ([]*Path, error) {
 	pathList := make([]*Path, 0)
-	dsts := make([]*Destination, 0)
+	dsts := make([]*Update, 0)
 	for _, path := range ProcessMessage(message, fromPeer, time.Now()) {
 		dsts = append(dsts, manager.Update(path)...)
 	}