use sorted single master table for route server setup

https://github.com/osrg/gobgp/issues/1249

The IN policy was removed. The modification by the IMPORT policy are
visible to all route server peers.

This saves some dozens bytes memory per a path.

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

4 files changed, 50 insertions, 116 deletions

diff --git a/server/fsm.go b/server/fsm.go
index b38cc9a1..db3efe1f 100644
--- a/server/fsm.go
+++ b/server/fsm.go
@@ -897,25 +897,7 @@ func (h *FSMHandler) recvMessageWithError() (*FsmMsg, error) {
 					return fmsg, err
 				}
 
-				// RFC4271 9.1.2 Phase 2: Route Selection
-				//
-				// If the AS_PATH attribute of a BGP route contains an AS loop, the BGP
-				// route should be excluded from the Phase 2 decision function.
-				var asLoop bool
-				if attr := getPathAttrFromBGPUpdate(body, bgp.BGP_ATTR_TYPE_AS_PATH); attr != nil {
-					asLoop = hasOwnASLoop(h.fsm.peerInfo.LocalAS, int(h.fsm.pConf.AsPathOptions.Config.AllowOwnAs), attr.(*bgp.PathAttributeAsPath))
-				}
-
 				fmsg.PathList = table.ProcessMessage(m, h.fsm.peerInfo, fmsg.timestamp)
-				id := h.fsm.pConf.State.NeighborAddress
-				for _, path := range fmsg.PathList {
-					if path.IsEOR() {
-						continue
-					}
-					if asLoop || (h.fsm.policy.ApplyPolicy(id, table.POLICY_DIRECTION_IN, path, nil) == nil) {
-						path.Filter(id, table.POLICY_DIRECTION_IN)
-					}
-				}
 				fallthrough
 			case bgp.BGP_MSG_KEEPALIVE:
 				// if the length of h.holdTimerResetCh
diff --git a/server/peer.go b/server/peer.go
index 96cb4170..4be180a5 100644
--- a/server/peer.go
+++ b/server/peer.go
@@ -340,7 +340,7 @@ func (peer *Peer) filterpath(path, old *table.Path) *table.Path {
 			// (*Destination) GetChanges().
 			dst := peer.localRib.GetDestination(path)
 			path = nil
-			for _, p := range dst.GetKnownPathList(peer.TableID()) {
+			for _, p := range dst.GetKnownPathList(peer.TableID(), peer.AS()) {
 				// Just take care not to send back.
 				if peer.ID() != p.GetSource().Address.String() {
 					path = p
@@ -453,9 +453,9 @@ func (peer *Peer) getBestFromLocal(rfList []bgp.RouteFamily) ([]*table.Path, []*
 	for _, family := range peer.toGlobalFamilies(rfList) {
 		pl := func() []*table.Path {
 			if peer.isAddPathSendEnabled(family) {
-				return peer.localRib.GetPathList(peer.TableID(), []bgp.RouteFamily{family})
+				return peer.localRib.GetPathList(peer.TableID(), peer.AS(), []bgp.RouteFamily{family})
 			}
-			return peer.localRib.GetBestPathList(peer.TableID(), []bgp.RouteFamily{family})
+			return peer.localRib.GetBestPathList(peer.TableID(), peer.AS(), []bgp.RouteFamily{family})
 		}()
 		for _, path := range pl {
 			if p := peer.filterpath(path, nil); p != nil {
@@ -616,11 +616,16 @@ func (peer *Peer) handleUpdate(e *FsmMsg) ([]*table.Path, []bgp.RouteFamily, *bg
 				eor = append(eor, family)
 				continue
 			}
-			if path.Filtered(peer.ID()) != table.POLICY_DIRECTION_IN {
-				paths = append(paths, path)
-			} else {
-				paths = append(paths, path.Clone(true))
+			// RFC4271 9.1.2 Phase 2: Route Selection
+			//
+			// If the AS_PATH attribute of a BGP route contains an AS loop, the BGP
+			// route should be excluded from the Phase 2 decision function.
+			if aspath := path.GetAsPath(); aspath != nil {
+				if hasOwnASLoop(peer.fsm.peerInfo.LocalAS, int(peer.fsm.pConf.AsPathOptions.Config.AllowOwnAs), aspath) {
+					continue
+				}
 			}
+			paths = append(paths, path)
 		}
 		return paths, eor, nil
 	}
diff --git a/server/server.go b/server/server.go
index abd32dfa..47bebd7b 100644
--- a/server/server.go
+++ b/server/server.go
@@ -545,7 +545,7 @@ func (server *BgpServer) notifyPostPolicyUpdateWatcher(peer *Peer, pathList []*t
 	server.notifyWatcher(WATCH_EVENT_TYPE_POST_UPDATE, ev)
 }
 
-func dstsToPaths(id string, dsts []*table.Destination, addpath bool) ([]*table.Path, []*table.Path, [][]*table.Path) {
+func dstsToPaths(id string, as uint32, dsts []*table.Destination, addpath bool) ([]*table.Path, []*table.Path, [][]*table.Path) {
 	if table.SelectionOptions.DisableBestPathSelection {
 		// Note: If best path selection disabled, there is no best path.
 		return nil, nil, nil
@@ -558,7 +558,7 @@ func dstsToPaths(id string, dsts []*table.Destination, addpath bool) ([]*table.P
 		if addpath {
 			bestList = append(bestList, dst.GetAddPathChanges(id)...)
 		} else {
-			best, old, mpath := dst.GetChanges(id, false)
+			best, old, mpath := dst.GetChanges(id, as, false)
 			bestList = append(bestList, best)
 			oldList = append(oldList, old)
 			if mpath != nil {
@@ -583,7 +583,7 @@ func (server *BgpServer) dropPeerAllRoutes(peer *Peer, families []bgp.RouteFamil
 	for _, rf := range families {
 		dsts := rib.DeletePathsByPeer(peer.fsm.peerInfo, rf)
 		if !peer.isRouteServerClient() {
-			gBestList, _, mpathList = dstsToPaths(table.GLOBAL_RIB_NAME, dsts, false)
+			gBestList, _, mpathList = dstsToPaths(table.GLOBAL_RIB_NAME, 0, dsts, false)
 			server.notifyBestWatcher(gBestList, mpathList)
 		}
 
@@ -592,9 +592,9 @@ func (server *BgpServer) dropPeerAllRoutes(peer *Peer, families []bgp.RouteFamil
 				continue
 			}
 			if targetPeer.isAddPathSendEnabled(rf) {
-				bestList, _, _ = dstsToPaths(targetPeer.TableID(), dsts, true)
+				bestList, _, _ = dstsToPaths(targetPeer.TableID(), targetPeer.AS(), dsts, true)
 			} else if targetPeer.isRouteServerClient() {
-				bestList, _, _ = dstsToPaths(targetPeer.TableID(), dsts, false)
+				bestList, _, _ = dstsToPaths(targetPeer.TableID(), targetPeer.AS(), dsts, false)
 			} else {
 				bestList = gBestList
 			}
@@ -661,30 +661,6 @@ func (server *BgpServer) notifyRecvMessageWatcher(peer *Peer, timestamp time.Tim
 	server.notifyMessageWatcher(peer, timestamp, msg, false)
 }
 
-func (server *BgpServer) RSimportPaths(peer *Peer, pathList []*table.Path) []*table.Path {
-	moded := make([]*table.Path, 0, len(pathList)/2)
-	for _, before := range pathList {
-		if isASLoop(peer, before) {
-			before.Filter(peer.ID(), table.POLICY_DIRECTION_IMPORT)
-			continue
-		}
-		after := server.policy.ApplyPolicy(peer.TableID(), table.POLICY_DIRECTION_IMPORT, before, nil)
-		if after == nil {
-			before.Filter(peer.ID(), table.POLICY_DIRECTION_IMPORT)
-		} else if after != before {
-			before.Filter(peer.ID(), table.POLICY_DIRECTION_IMPORT)
-			for _, n := range server.neighborMap {
-				if n == peer {
-					continue
-				}
-				after.Filter(n.ID(), table.POLICY_DIRECTION_IMPORT)
-			}
-			moded = append(moded, after)
-		}
-	}
-	return moded
-}
-
 func (server *BgpServer) propagateUpdate(peer *Peer, pathList []*table.Path) {
 	var dsts []*table.Destination
 
@@ -702,17 +678,15 @@ func (server *BgpServer) propagateUpdate(peer *Peer, pathList []*table.Path) {
 
 	if peer != nil && peer.isRouteServerClient() {
 		rib = server.rsRib
-		for _, path := range pathList {
-			path.Filter(peer.ID(), table.POLICY_DIRECTION_IMPORT)
-		}
-		moded := make([]*table.Path, 0)
-		for _, targetPeer := range server.neighborMap {
-			if !targetPeer.isRouteServerClient() || peer == targetPeer {
-				continue
+		for idx, path := range pathList {
+			if p := server.policy.ApplyPolicy(peer.TableID(), table.POLICY_DIRECTION_IMPORT, path, nil); p != nil {
+				path = p
+			} else {
+				path = path.Clone(true)
 			}
-			moded = append(moded, server.RSimportPaths(targetPeer, pathList)...)
+			pathList[idx] = path
 		}
-		dsts = rib.ProcessPaths(append(pathList, moded...))
+		dsts = rib.ProcessPaths(pathList)
 	} else {
 		for idx, path := range pathList {
 			var options *table.PolicyOptions
@@ -752,7 +726,7 @@ func (server *BgpServer) propagateUpdate(peer *Peer, pathList []*table.Path) {
 				if path.IsWithdraw {
 					candidates, _ = peer.getBestFromLocal(peer.configuredRFlist())
 				} else {
-					candidates = rib.GetBestPathList(peer.TableID(), fs)
+					candidates = rib.GetBestPathList(peer.TableID(), 0, fs)
 				}
 				paths := make([]*table.Path, 0, len(candidates))
 				for _, p := range candidates {
@@ -777,7 +751,7 @@ func (server *BgpServer) propagateUpdate(peer *Peer, pathList []*table.Path) {
 		server.notifyPostPolicyUpdateWatcher(peer, pathList)
 		dsts = rib.ProcessPaths(pathList)
 
-		gBestList, gOldList, mpathList = dstsToPaths(table.GLOBAL_RIB_NAME, dsts, false)
+		gBestList, gOldList, mpathList = dstsToPaths(table.GLOBAL_RIB_NAME, 0, dsts, false)
 		server.notifyBestWatcher(gBestList, mpathList)
 	}
 
@@ -805,9 +779,9 @@ func (server *BgpServer) propagateUpdateToNeighbors(peer *Peer, dsts []*table.De
 				continue
 			}
 			if targetPeer.isAddPathSendEnabled(family) {
-				bestList, oldList, _ = dstsToPaths(targetPeer.TableID(), l, true)
+				bestList, oldList, _ = dstsToPaths(targetPeer.TableID(), targetPeer.AS(), l, true)
 			} else if targetPeer.isRouteServerClient() {
-				bestList, oldList, _ = dstsToPaths(targetPeer.TableID(), l, false)
+				bestList, oldList, _ = dstsToPaths(targetPeer.TableID(), targetPeer.AS(), l, false)
 			} else {
 				bestList = gBestList
 				oldList = gOldList
@@ -1293,7 +1267,7 @@ func (server *BgpServer) fixupApiPath(vrfId string, pathList []*table.Path) erro
 			switch r := nlri.RouteTypeData.(type) {
 			case *bgp.EVPNMacIPAdvertisementRoute:
 				// MAC Mobility Extended Community
-				paths := server.globalRib.GetBestPathList(table.GLOBAL_RIB_NAME, []bgp.RouteFamily{bgp.RF_EVPN})
+				paths := server.globalRib.GetBestPathList(table.GLOBAL_RIB_NAME, 0, []bgp.RouteFamily{bgp.RF_EVPN})
 				if m := getMacMobilityExtendedCommunity(r.ETag, r.MacAddress, paths); m != nil {
 					path.SetExtCommunities([]bgp.ExtendedCommunityInterface{m}, false)
 				}
@@ -1347,7 +1321,7 @@ func (s *BgpServer) DeletePath(uuid []byte, f bgp.RouteFamily, vrfId string, pat
 		if len(uuid) > 0 {
 			// Delete locally generated path which has the given UUID
 			path := func() *table.Path {
-				for _, path := range s.globalRib.GetPathList(table.GLOBAL_RIB_NAME, s.globalRib.GetRFlist()) {
+				for _, path := range s.globalRib.GetPathList(table.GLOBAL_RIB_NAME, 0, s.globalRib.GetRFlist()) {
 					if path.IsLocal() && len(path.UUID()) > 0 && bytes.Equal(path.UUID().Bytes(), uuid) {
 						return path
 					}
@@ -1364,7 +1338,7 @@ func (s *BgpServer) DeletePath(uuid []byte, f bgp.RouteFamily, vrfId string, pat
 			if f != 0 {
 				families = []bgp.RouteFamily{f}
 			}
-			for _, path := range s.globalRib.GetPathList(table.GLOBAL_RIB_NAME, families) {
+			for _, path := range s.globalRib.GetPathList(table.GLOBAL_RIB_NAME, 0, families) {
 				if path.IsLocal() {
 					deletePathList = append(deletePathList, path.Clone(true))
 				}
@@ -1386,7 +1360,7 @@ func (s *BgpServer) UpdatePath(vrfId string, pathList []*table.Path) error {
 			return err
 		}
 		dsts := s.globalRib.ProcessPaths(pathList)
-		gBestList, gOldList, gMPathList := dstsToPaths(table.GLOBAL_RIB_NAME, dsts, false)
+		gBestList, gOldList, gMPathList := dstsToPaths(table.GLOBAL_RIB_NAME, 0, dsts, false)
 		s.notifyBestWatcher(gBestList, gMPathList)
 		s.propagateUpdateToNeighbors(nil, dsts, gBestList, gOldList)
 		return nil
@@ -1501,36 +1475,16 @@ func (s *BgpServer) softResetIn(addr string, family bgp.RouteFamily) error {
 			families = peer.configuredRFlist()
 		}
 		for _, path := range peer.adjRibIn.PathList(families, false) {
-			exResult := path.Filtered(peer.ID())
-			path.Filter(peer.ID(), table.POLICY_DIRECTION_NONE)
-
 			// RFC4271 9.1.2 Phase 2: Route Selection
 			//
 			// If the AS_PATH attribute of a BGP route contains an AS loop, the BGP
 			// route should be excluded from the Phase 2 decision function.
-			var asLoop bool
 			if aspath := path.GetAsPath(); aspath != nil {
-				asLoop = hasOwnASLoop(peer.fsm.peerInfo.LocalAS, int(peer.fsm.pConf.AsPathOptions.Config.AllowOwnAs), aspath)
-			}
-
-			if !asLoop && s.policy.ApplyPolicy(peer.ID(), table.POLICY_DIRECTION_IN, path, nil) != nil {
-				pathList = append(pathList, path.Clone(false))
-				// this path still in rib's
-				// knownPathList. We can't
-				// drop
-				// table.POLICY_DIRECTION_IMPORT
-				// flag here. Otherwise, this
-				// path could be the old best
-				// path.
-				if peer.isRouteServerClient() {
-					path.Filter(peer.ID(), table.POLICY_DIRECTION_IMPORT)
-				}
-			} else {
-				path.Filter(peer.ID(), table.POLICY_DIRECTION_IN)
-				if exResult != table.POLICY_DIRECTION_IN {
-					pathList = append(pathList, path.Clone(true))
+				if hasOwnASLoop(peer.fsm.peerInfo.LocalAS, int(peer.fsm.pConf.AsPathOptions.Config.AllowOwnAs), aspath) {
+					continue
 				}
 			}
+			pathList = append(pathList, path.Clone(false))
 		}
 		peer.adjRibIn.RefreshAcceptedNumber(families)
 		s.propagateUpdate(peer, pathList)
@@ -1626,6 +1580,7 @@ func (s *BgpServer) GetRib(addr string, family bgp.RouteFamily, prefixes []*tabl
 	err = s.mgmtOperation(func() error {
 		m := s.globalRib
 		id := table.GLOBAL_RIB_NAME
+		as := uint32(0)
 		if len(addr) > 0 {
 			peer, ok := s.neighborMap[addr]
 			if !ok {
@@ -1635,6 +1590,7 @@ func (s *BgpServer) GetRib(addr string, family bgp.RouteFamily, prefixes []*tabl
 				return fmt.Errorf("Neighbor %v doesn't have local rib", addr)
 			}
 			id = peer.ID()
+			as = peer.AS()
 			m = s.rsRib
 		}
 		af := bgp.RouteFamily(family)
@@ -1642,7 +1598,7 @@ func (s *BgpServer) GetRib(addr string, family bgp.RouteFamily, prefixes []*tabl
 		if !ok {
 			return fmt.Errorf("address family: %s not supported", af)
 		}
-		rib, err = tbl.Select(table.TableSelectOption{ID: id, LookupPrefixes: prefixes})
+		rib, err = tbl.Select(table.TableSelectOption{ID: id, AS: as, LookupPrefixes: prefixes})
 		return err
 	}, true)
 	return
@@ -1681,6 +1637,7 @@ func (s *BgpServer) GetAdjRib(addr string, family bgp.RouteFamily, in bool, pref
 			return fmt.Errorf("Neighbor that has %v doesn't exist.", addr)
 		}
 		id := peer.ID()
+		as := peer.AS()
 
 		var adjRib *table.AdjRib
 		if in {
@@ -1690,7 +1647,7 @@ func (s *BgpServer) GetAdjRib(addr string, family bgp.RouteFamily, in bool, pref
 			accepted, _ := peer.getBestFromLocal(peer.configuredRFlist())
 			adjRib.Update(accepted)
 		}
-		rib, err = adjRib.Select(family, false, table.TableSelectOption{ID: id, LookupPrefixes: prefixes})
+		rib, err = adjRib.Select(family, false, table.TableSelectOption{ID: id, AS: as, LookupPrefixes: prefixes})
 		return err
 	}, true)
 	return
@@ -1700,6 +1657,7 @@ func (s *BgpServer) GetRibInfo(addr string, family bgp.RouteFamily) (info *table
 	err = s.mgmtOperation(func() error {
 		m := s.globalRib
 		id := table.GLOBAL_RIB_NAME
+		as := uint32(0)
 		if len(addr) > 0 {
 			peer, ok := s.neighborMap[addr]
 			if !ok {
@@ -1709,9 +1667,10 @@ func (s *BgpServer) GetRibInfo(addr string, family bgp.RouteFamily) (info *table
 				return fmt.Errorf("Neighbor %v doesn't have local rib", addr)
 			}
 			id = peer.ID()
+			as = peer.AS()
 			m = s.rsRib
 		}
-		info, err = m.TableInfo(id, family)
+		info, err = m.TableInfo(id, as, family)
 		return err
 	}, true)
 	return
@@ -1842,20 +1801,6 @@ func (server *BgpServer) addNeighbor(c *config.Neighbor) error {
 	}
 	peer := NewPeer(&server.bgpConfig.Global, c, rib, server.policy)
 	server.policy.Reset(nil, map[string]config.ApplyPolicy{peer.ID(): c.ApplyPolicy})
-	if peer.isRouteServerClient() {
-		pathList := make([]*table.Path, 0)
-		rfList := peer.configuredRFlist()
-		for _, p := range server.neighborMap {
-			if !p.isRouteServerClient() {
-				continue
-			}
-			pathList = append(pathList, p.getAccepted(rfList)...)
-		}
-		moded := server.RSimportPaths(peer, pathList)
-		if len(moded) > 0 {
-			server.rsRib.ProcessPaths(moded)
-		}
-	}
 	server.neighborMap[addr] = peer
 	if name := c.Config.PeerGroup; name != "" {
 		server.peerGroupMap[name].AddMember(*c)
@@ -2577,6 +2522,7 @@ func (w *Watcher) Generate(t WatchEventType) error {
 			w.notify(&WatchEventAdjIn{PathList: clonePathList(pathList)})
 		case WATCH_EVENT_TYPE_TABLE:
 			rib := w.s.globalRib
+			as := uint32(0)
 			id := table.GLOBAL_RIB_NAME
 			if len(w.opts.tableName) > 0 {
 				peer, ok := w.s.neighborMap[w.opts.tableName]
@@ -2587,6 +2533,7 @@ func (w *Watcher) Generate(t WatchEventType) error {
 					return fmt.Errorf("Neighbor %v doesn't have local rib", w.opts.tableName)
 				}
 				id = peer.ID()
+				as = peer.AS()
 				rib = w.s.rsRib
 			}
 
@@ -2594,7 +2541,7 @@ func (w *Watcher) Generate(t WatchEventType) error {
 				pathList := make(map[string][]*table.Path)
 				for _, t := range rib.Tables {
 					for _, dst := range t.GetSortedDestinations() {
-						if paths := dst.GetKnownPathList(id); len(paths) > 0 {
+						if paths := dst.GetKnownPathList(id, as); len(paths) > 0 {
 							pathList[dst.GetNlri().String()] = clonePathList(paths)
 						}
 					}
@@ -2698,7 +2645,7 @@ func (s *BgpServer) Watch(opts ...WatchOption) (w *Watcher) {
 		}
 		if w.opts.initBest && s.active() == nil {
 			w.notify(&WatchEventBestPath{
-				PathList:      s.globalRib.GetBestPathList(table.GLOBAL_RIB_NAME, nil),
+				PathList:      s.globalRib.GetBestPathList(table.GLOBAL_RIB_NAME, 0, nil),
 				MultiPathList: s.globalRib.GetBestMultiPathList(table.GLOBAL_RIB_NAME, nil),
 			})
 		}
@@ -2753,7 +2700,7 @@ func (s *BgpServer) Watch(opts ...WatchOption) (w *Watcher) {
 					continue
 				}
 				pathsByPeer := make(map[*table.PeerInfo][]*table.Path)
-				for _, path := range s.globalRib.GetPathList(table.GLOBAL_RIB_NAME, []bgp.RouteFamily{rf}) {
+				for _, path := range s.globalRib.GetPathList(table.GLOBAL_RIB_NAME, 0, []bgp.RouteFamily{rf}) {
 					pathsByPeer[path.GetSource()] = append(pathsByPeer[path.GetSource()], path)
 				}
 				for peerInfo, paths := range pathsByPeer {
diff --git a/server/server_test.go b/server/server_test.go
index 82a926ae..7eaea7b7 100644
--- a/server/server_test.go
+++ b/server/server_test.go
@@ -166,7 +166,7 @@ func TestMonitor(test *testing.T) {
 		if err != nil {
 			log.Fatal(err)
 		}
-		if len(rib.GetKnownPathList("")) > 0 {
+		if len(rib.GetKnownPathList("", 0)) > 0 {
 			break
 		}
 		time.Sleep(1)
@@ -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) {
-	news, olds, _ := dstsToPaths(table.GLOBAL_RIB_NAME, rib.ProcessPaths(l), false)
+	news, olds, _ := dstsToPaths(table.GLOBAL_RIB_NAME, 0, rib.ProcessPaths(l), false)
 	if len(news) != 1 {
 		panic("can't handle multiple paths")
 	}