From ee91af5b638755a19c6954579b77a28916fb9bff Mon Sep 17 00:00:00 2001 From: FUJITA Tomonori Date: Tue, 10 Apr 2018 22:39:08 +0900 Subject: preparation for shrinking Destination structure Signed-off-by: FUJITA Tomonori --- table/destination.go | 171 ++++++++++++++++---------------------------- table/destination_test.go | 43 ++++------- table/table.go | 31 -------- table/table_manager.go | 89 ++++++++++------------- table/table_manager_test.go | 6 +- 5 files changed, 119 insertions(+), 221 deletions(-) (limited to 'table') 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) } -- cgit v1.2.3