server/api: fix GetRib API to return sorted destination

the feature has been broken.

Signed-off-by: Wataru Ishida <ishida.wataru@lab.ntt.co.jp>

6 files changed, 247 insertions, 197 deletions

diff --git a/api/grpc_server.go b/api/grpc_server.go
index b4bfd1e3..225c3971 100644
--- a/api/grpc_server.go
+++ b/api/grpc_server.go
@@ -180,7 +180,7 @@ func (s *Server) GetNeighbor(ctx context.Context, arg *GetNeighborRequest) (*Get
 	return &GetNeighborResponse{Peers: p}, nil
 }
 
-func toPathApi(id string, path *table.Path) *Path {
+func toPathApi(path *table.Path) *Path {
 	nlri := path.GetNlri()
 	n, _ := nlri.Serialize()
 	family := uint32(bgp.AfiSafiToRouteFamily(nlri.AFI(), nlri.SAFI()))
@@ -198,7 +198,7 @@ func toPathApi(id string, path *table.Path) *Path {
 		Age:            path.GetTimestamp().Unix(),
 		IsWithdraw:     path.IsWithdraw,
 		Validation:     int32(path.Validation().ToInt()),
-		Filtered:       path.Filtered(id) == table.POLICY_DIRECTION_IN,
+		Filtered:       path.Filtered("") == table.POLICY_DIRECTION_IN,
 		Family:         family,
 		SourceAsn:      path.GetSource().AS,
 		SourceId:       path.GetSource().ID.String(),
@@ -209,18 +209,18 @@ func toPathApi(id string, path *table.Path) *Path {
 }
 
 func (s *Server) GetRib(ctx context.Context, arg *GetRibRequest) (*GetRibResponse, error) {
-	f := func() []*server.LookupPrefix {
-		l := make([]*server.LookupPrefix, 0, len(arg.Table.Destinations))
+	f := func() []*table.LookupPrefix {
+		l := make([]*table.LookupPrefix, 0, len(arg.Table.Destinations))
 		for _, p := range arg.Table.Destinations {
-			l = append(l, &server.LookupPrefix{
+			l = append(l, &table.LookupPrefix{
 				Prefix: p.Prefix,
-				LookupOption: func() server.LookupOption {
+				LookupOption: func() table.LookupOption {
 					if p.LongerPrefixes {
-						return server.LOOKUP_LONGER
+						return table.LOOKUP_LONGER
 					} else if p.ShorterPrefixes {
-						return server.LOOKUP_SHORTER
+						return table.LOOKUP_SHORTER
 					}
-					return server.LOOKUP_EXACT
+					return table.LOOKUP_EXACT
 				}(),
 			})
 		}
@@ -229,46 +229,48 @@ func (s *Server) GetRib(ctx context.Context, arg *GetRibRequest) (*GetRibRespons
 
 	var in bool
 	var err error
-	var id string
-	var r map[string][]*table.Path
+	var tbl *table.Table
 
 	family := bgp.RouteFamily(arg.Table.Family)
 	switch arg.Table.Type {
 	case Resource_LOCAL, Resource_GLOBAL:
-		id, r, err = s.bgpServer.GetRib(arg.Table.Name, family, f())
+		tbl, err = s.bgpServer.GetRib(arg.Table.Name, family, f())
 	case Resource_ADJ_IN:
 		in = true
 		fallthrough
 	case Resource_ADJ_OUT:
-		id, r, err = s.bgpServer.GetAdjRib(arg.Table.Name, family, in, f())
+		tbl, err = s.bgpServer.GetAdjRib(arg.Table.Name, family, in, f())
 	case Resource_VRF:
-		id, r, err = s.bgpServer.GetVrfRib(arg.Table.Name, family, []*server.LookupPrefix{})
+		tbl, err = s.bgpServer.GetVrfRib(arg.Table.Name, family, []*table.LookupPrefix{})
 	default:
 		return nil, fmt.Errorf("unsupported resource type: %v", arg.Table.Type)
 	}
 
-	dsts := make([]*Destination, 0, len(r))
-	if err == nil {
-		for k, v := range r {
-			dsts = append(dsts, &Destination{
-				Prefix: k,
-				Paths: func(paths []*table.Path) []*Path {
-					l := make([]*Path, 0, len(v))
-					for i, p := range paths {
-						pp := toPathApi(id, p)
-						switch arg.Table.Type {
-						case Resource_LOCAL, Resource_GLOBAL:
-							if i == 0 {
-								pp.Best = true
-							}
+	if err != nil {
+		return nil, err
+	}
+
+	dsts := []*Destination{}
+	for _, dst := range tbl.GetSortedDestinations() {
+		dsts = append(dsts, &Destination{
+			Prefix: dst.GetNlri().String(),
+			Paths: func(paths []*table.Path) []*Path {
+				l := make([]*Path, 0, len(paths))
+				for i, p := range paths {
+					pp := toPathApi(p)
+					switch arg.Table.Type {
+					case Resource_LOCAL, Resource_GLOBAL:
+						if i == 0 {
+							pp.Best = true
 						}
-						l = append(l, pp)
 					}
-					return l
-				}(v),
-			})
-		}
+					l = append(l, pp)
+				}
+				return l
+			}(dst.GetAllKnownPathList()),
+		})
 	}
+
 	return &GetRibResponse{Table: &Table{
 		Type:         arg.Table.Type,
 		Family:       arg.Table.Family,
@@ -304,11 +306,11 @@ func (s *Server) MonitorRib(arg *Table, stream GobgpApi_MonitorRibServer) error
 					continue
 				}
 				if dst, y := dsts[path.GetNlri().String()]; y {
-					dst.Paths = append(dst.Paths, toPathApi(table.GLOBAL_RIB_NAME, path))
+					dst.Paths = append(dst.Paths, toPathApi(path))
 				} else {
 					dsts[path.GetNlri().String()] = &Destination{
 						Prefix: path.GetNlri().String(),
-						Paths:  []*Path{toPathApi(table.GLOBAL_RIB_NAME, path)},
+						Paths:  []*Path{toPathApi(path)},
 					}
 				}
 			}
diff --git a/server/server.go b/server/server.go
index 049f3e46..d051aac3 100644
--- a/server/server.go
+++ b/server/server.go
@@ -24,7 +24,6 @@ import (
 	"time"
 
 	log "github.com/Sirupsen/logrus"
-	"github.com/armon/go-radix"
 	"github.com/eapache/channels"
 	"github.com/osrg/gobgp/config"
 	"github.com/osrg/gobgp/packet/bgp"
@@ -1423,28 +1422,15 @@ func (s *BgpServer) SoftReset(addr string, family bgp.RouteFamily) (err error) {
 	return err
 }
 
-type LookupOption uint8
-
-const (
-	LOOKUP_EXACT LookupOption = iota
-	LOOKUP_LONGER
-	LOOKUP_SHORTER
-)
-
-type LookupPrefix struct {
-	Prefix string
-	LookupOption
-}
-
-func (s *BgpServer) GetRib(addr string, family bgp.RouteFamily, prefixes []*LookupPrefix) (id string, dsts map[string][]*table.Path, err error) {
+func (s *BgpServer) GetRib(addr string, family bgp.RouteFamily, prefixes []*table.LookupPrefix) (rib *table.Table, err error) {
 	ch := make(chan struct{})
 	defer func() { <-ch }()
 
 	s.mgmtCh <- func() {
 		defer close(ch)
 
-		rib := s.globalRib
-		id = table.GLOBAL_RIB_NAME
+		m := s.globalRib
+		id := table.GLOBAL_RIB_NAME
 		if len(addr) > 0 {
 			peer, ok := s.neighborMap[addr]
 			if !ok {
@@ -1458,121 +1444,49 @@ func (s *BgpServer) GetRib(addr string, family bgp.RouteFamily, prefixes []*Look
 			id = peer.ID()
 		}
 		af := bgp.RouteFamily(family)
-		if _, ok := rib.Tables[af]; !ok {
+		tbl, ok := m.Tables[af]
+		if !ok {
 			err = fmt.Errorf("address family: %s not supported", af)
 			return
 		}
-
-		dsts = make(map[string][]*table.Path)
-		if (af == bgp.RF_IPv4_UC || af == bgp.RF_IPv6_UC) && len(prefixes) > 0 {
-			f := func(id, cidr string) (bool, error) {
-				_, prefix, err := net.ParseCIDR(cidr)
-				if err != nil {
-					return false, err
-				}
-				if dst := rib.Tables[af].GetDestination(prefix.String()); dst != nil {
-					if paths := dst.GetKnownPathList(id); len(paths) > 0 {
-						dsts[dst.GetNlri().String()] = clonePathList(paths)
-					}
-					return true, nil
-				} else {
-					return false, nil
-				}
-			}
-			for _, p := range prefixes {
-				key := p.Prefix
-				switch p.LookupOption {
-				case LOOKUP_LONGER:
-					ds, e := rib.Tables[af].GetLongerPrefixDestinations(key)
-					if err != nil {
-						err = e
-						return
-					}
-					for _, dst := range ds {
-						if paths := dst.GetKnownPathList(id); len(paths) > 0 {
-							dsts[dst.GetNlri().String()] = clonePathList(paths)
-						}
-					}
-
-				case LOOKUP_SHORTER:
-					_, prefix, e := net.ParseCIDR(key)
-					if e != nil {
-						err = e
-						return
-					}
-					ones, bits := prefix.Mask.Size()
-					for i := ones; i > 0; i-- {
-						prefix.Mask = net.CIDRMask(i, bits)
-						f(id, prefix.String())
-					}
-				default:
-					if _, err := f(id, key); err != nil {
-						if host := net.ParseIP(key); host != nil {
-							masklen := 32
-							if af == bgp.RF_IPv6_UC {
-								masklen = 128
-							}
-							for i := masklen; i > 0; i-- {
-								if y, _ := f(id, fmt.Sprintf("%s/%d", key, i)); y {
-									break
-								}
-							}
-						}
-					}
-				}
-			}
-		} else {
-			for _, dst := range rib.Tables[af].GetSortedDestinations() {
-				if paths := dst.GetKnownPathList(id); len(paths) > 0 {
-					dsts[dst.GetNlri().String()] = clonePathList(paths)
-				}
-			}
-		}
+		rib, err = tbl.Select(table.TableSelectOption{ID: id, LookupPrefixes: prefixes})
 	}
-	return id, dsts, err
+	return
 }
 
-func (s *BgpServer) GetVrfRib(name string, family bgp.RouteFamily, prefixes []*LookupPrefix) (id string, dsts map[string][]*table.Path, err error) {
+func (s *BgpServer) GetVrfRib(name string, family bgp.RouteFamily, prefixes []*table.LookupPrefix) (rib *table.Table, err error) {
 	ch := make(chan struct{})
 	defer func() { <-ch }()
 
 	s.mgmtCh <- func() {
 		defer close(ch)
 
-		rib := s.globalRib
-		vrfs := rib.Vrfs
+		m := s.globalRib
+		vrfs := m.Vrfs
 		if _, ok := vrfs[name]; !ok {
 			err = fmt.Errorf("vrf %s not found", name)
 			return
 		}
-		var rf bgp.RouteFamily
+		var af bgp.RouteFamily
 		switch family {
 		case bgp.RF_IPv4_UC:
-			rf = bgp.RF_IPv4_VPN
+			af = bgp.RF_IPv4_VPN
 		case bgp.RF_IPv6_UC:
-			rf = bgp.RF_IPv6_VPN
+			af = bgp.RF_IPv6_VPN
 		case bgp.RF_EVPN:
-			rf = bgp.RF_EVPN
-		default:
-			err = fmt.Errorf("unsupported route family: %s", family)
-			return
+			af = bgp.RF_EVPN
 		}
-
-		dsts = make(map[string][]*table.Path)
-		for _, path := range rib.GetPathList(table.GLOBAL_RIB_NAME, []bgp.RouteFamily{rf}) {
-			if ok := table.CanImportToVrf(vrfs[name], path); ok {
-				if d, y := dsts[path.GetNlri().String()]; y {
-					d = append(d, path.Clone(false))
-				} else {
-					dsts[path.GetNlri().String()] = []*table.Path{path.Clone(false)}
-				}
-			}
+		tbl, ok := m.Tables[af]
+		if !ok {
+			err = fmt.Errorf("address family: %s not supported", af)
+			return
 		}
+		rib, err = tbl.Select(table.TableSelectOption{VRF: vrfs[name], LookupPrefixes: prefixes})
 	}
-	return table.GLOBAL_RIB_NAME, dsts, err
+	return
 }
 
-func (s *BgpServer) GetAdjRib(addr string, family bgp.RouteFamily, in bool, prefixes []*LookupPrefix) (id string, dsts map[string][]*table.Path, err error) {
+func (s *BgpServer) GetAdjRib(addr string, family bgp.RouteFamily, in bool, prefixes []*table.LookupPrefix) (rib *table.Table, err error) {
 	ch := make(chan struct{})
 	defer func() { <-ch }()
 
@@ -1584,66 +1498,17 @@ func (s *BgpServer) GetAdjRib(addr string, family bgp.RouteFamily, in bool, pref
 			err = fmt.Errorf("Neighbor that has %v doesn't exist.", addr)
 			return
 		}
-		id = peer.TableID()
+		id := peer.TableID()
 
-		var paths []*table.Path
+		var adjRib *table.AdjRib
 		if in {
-			paths = peer.adjRibIn.PathList([]bgp.RouteFamily{family}, false)
-			log.WithFields(log.Fields{
-				"Topic": "Peer",
-			}).Debugf("RouteFamily=%v adj-rib-in found : %d", family.String(), len(paths))
+			adjRib = peer.adjRibIn
 		} else {
-			paths = peer.adjRibOut.PathList([]bgp.RouteFamily{family}, false)
-			log.WithFields(log.Fields{
-				"Topic": "Peer",
-			}).Debugf("RouteFamily=%v adj-rib-out found : %d", family.String(), len(paths))
-		}
-
-		for i, p := range paths {
-			paths[i] = p.Clone(false)
-			paths[i].Filter(id, p.Filtered(id))
-		}
-
-		dsts = make(map[string][]*table.Path)
-		switch family {
-		case bgp.RF_IPv4_UC, bgp.RF_IPv6_UC:
-			r := radix.New()
-			for _, p := range paths {
-				key := p.GetNlri().String()
-				found := true
-				for _, p := range prefixes {
-					found = false
-					if p.Prefix == key {
-						found = true
-						break
-					}
-				}
-
-				if found {
-					b, _ := r.Get(table.CidrToRadixkey(key))
-					if b == nil {
-						r.Insert(table.CidrToRadixkey(key), []*table.Path{p})
-					} else {
-						l := b.([]*table.Path)
-						l = append(l, p)
-					}
-				}
-			}
-			r.Walk(func(s string, v interface{}) bool {
-				dsts[s] = v.([]*table.Path)
-				return false
-			})
-		default:
-			for _, p := range paths {
-				if d, y := dsts[p.GetNlri().String()]; y {
-					d = append(d, p)
-				} else {
-					dsts[p.GetNlri().String()] = []*table.Path{p}
-				}
-			}
+			adjRib = peer.adjRibOut
 		}
+		rib, err = adjRib.Select(family, false, table.TableSelectOption{ID: id, LookupPrefixes: prefixes})
 	}
-	return id, dsts, err
+	return
 }
 
 func (s *BgpServer) GetServer() (c *config.Global) {
diff --git a/table/adj.go b/table/adj.go
index 2fb46b4a..b38e02b8 100644
--- a/table/adj.go
+++ b/table/adj.go
@@ -168,3 +168,23 @@ func (adj *AdjRib) Exists(path *Path) bool {
 	_, ok = table[path.getPrefix()]
 	return ok
 }
+
+func (adj *AdjRib) Select(family bgp.RouteFamily, accepted bool, option ...TableSelectOption) (*Table, error) {
+	paths := adj.PathList([]bgp.RouteFamily{family}, accepted)
+	dsts := make(map[string]*Destination, len(paths))
+	for _, path := range paths {
+		if d, y := dsts[path.GetNlri().String()]; y {
+			d.knownPathList = append(d.knownPathList, path)
+		} else {
+			dst := NewDestination(path.GetNlri())
+			dsts[path.GetNlri().String()] = dst
+			dst.knownPathList = append(dst.knownPathList, path)
+		}
+	}
+	tbl := &Table{
+		routeFamily:  family,
+		destinations: dsts,
+	}
+	option = append(option, TableSelectOption{adj: true})
+	return tbl.Select(option...)
+}
diff --git a/table/destination.go b/table/destination.go
index f6b3f7f9..7e0deb2b 100644
--- a/table/destination.go
+++ b/table/destination.go
@@ -850,6 +850,48 @@ func (dest *Destination) String() string {
 	return fmt.Sprintf("Destination NLRI: %s", dest.nlri.String())
 }
 
+type DestinationSelectOption struct {
+	ID  string
+	VRF *Vrf
+	adj bool
+}
+
+func (old *Destination) Select(option ...DestinationSelectOption) *Destination {
+	id := GLOBAL_RIB_NAME
+	var vrf *Vrf
+	adj := false
+	for _, o := range option {
+		if o.ID != "" {
+			id = o.ID
+		}
+		if o.VRF != nil {
+			vrf = o.VRF
+		}
+		adj = o.adj
+	}
+	var paths []*Path
+	if adj {
+		paths = old.knownPathList
+	} else {
+		paths = old.GetKnownPathList(id)
+	}
+	new := NewDestination(old.nlri)
+	list := make([]*Path, 0, len(old.knownPathList))
+	for _, path := range paths {
+		if vrf != nil && !CanImportToVrf(vrf, path) {
+			continue
+		}
+		p := path.Clone(path.IsWithdraw)
+		p.Filter("", path.Filtered(id))
+		list = append(list, p)
+	}
+	if len(list) == 0 {
+		return nil
+	}
+	new.knownPathList = list
+	return new
+}
+
 type destinations []*Destination
 
 func (d destinations) Len() int {
diff --git a/table/table.go b/table/table.go
index b1ec94a1..bad0e824 100644
--- a/table/table.go
+++ b/table/table.go
@@ -16,6 +16,7 @@
 package table
 
 import (
+	"fmt"
 	"net"
 	"sort"
 
@@ -24,6 +25,26 @@ import (
 	"github.com/osrg/gobgp/packet/bgp"
 )
 
+type LookupOption uint8
+
+const (
+	LOOKUP_EXACT LookupOption = iota
+	LOOKUP_LONGER
+	LOOKUP_SHORTER
+)
+
+type LookupPrefix struct {
+	Prefix string
+	LookupOption
+}
+
+type TableSelectOption struct {
+	ID             string
+	LookupPrefixes []*LookupPrefix
+	VRF            *Vrf
+	adj            bool
+}
+
 type Table struct {
 	routeFamily  bgp.RouteFamily
 	destinations map[string]*Destination
@@ -287,3 +308,79 @@ func (t *Table) GetKnownPathList(id string) []*Path {
 	}
 	return paths
 }
+
+func (t *Table) Select(option ...TableSelectOption) (*Table, error) {
+	id := GLOBAL_RIB_NAME
+	var vrf *Vrf
+	adj := false
+	prefixes := make([]*LookupPrefix, 0, len(option))
+	for _, o := range option {
+		if o.ID != "" {
+			id = o.ID
+		}
+		if o.VRF != nil {
+			vrf = o.VRF
+		}
+		adj = o.adj
+		prefixes = append(prefixes, o.LookupPrefixes...)
+	}
+	dsts := make(map[string]*Destination)
+	if (t.routeFamily == bgp.RF_IPv4_UC || t.routeFamily == bgp.RF_IPv6_UC) && len(prefixes) > 0 {
+		f := func(id, key string) (bool, error) {
+			if dst := t.GetDestination(key); dst != nil {
+				if d := dst.Select(DestinationSelectOption{ID: id, adj: adj}); d != nil {
+					dsts[key] = d
+					return true, nil
+				}
+			}
+			return false, nil
+		}
+		for _, p := range prefixes {
+			key := p.Prefix
+			switch p.LookupOption {
+			case LOOKUP_LONGER:
+				ds, err := t.GetLongerPrefixDestinations(key)
+				if err != nil {
+					return nil, err
+				}
+				for _, dst := range ds {
+					dsts[dst.GetNlri().String()] = dst.Select(DestinationSelectOption{ID: id, adj: adj})
+				}
+			case LOOKUP_SHORTER:
+				_, prefix, err := net.ParseCIDR(key)
+				if err != nil {
+					return nil, err
+				}
+				ones, bits := prefix.Mask.Size()
+				for i := ones; i > 0; i-- {
+					prefix.Mask = net.CIDRMask(i, bits)
+					f(id, prefix.String())
+				}
+			default:
+				if _, err := f(id, key); err != nil {
+					if host := net.ParseIP(key); host != nil {
+						masklen := 32
+						if t.routeFamily == bgp.RF_IPv6_UC {
+							masklen = 128
+						}
+						for i := masklen; i > 0; i-- {
+							if y, _ := f(id, fmt.Sprintf("%s/%d", key, i)); y {
+								break
+							}
+						}
+					}
+				}
+			}
+		}
+	} else {
+		for k, dst := range t.GetDestinations() {
+			if d := dst.Select(DestinationSelectOption{ID: id, VRF: vrf, adj: adj}); d != nil {
+				dsts[k] = d
+			}
+		}
+	}
+	return &Table{
+		routeFamily:  t.routeFamily,
+		destinations: dsts,
+	}, nil
+}
diff --git a/test/scenario_test/bgp_router_test.py b/test/scenario_test/bgp_router_test.py
index 10821137..f6831f79 100644
--- a/test/scenario_test/bgp_router_test.py
+++ b/test/scenario_test/bgp_router_test.py
@@ -390,6 +390,30 @@ class GoBGPTestBase(unittest.TestCase):
 
         self.assertTrue(cnt == 1)
 
+    def test_21_check_cli_sorted(self):
+        g1 = self.gobgp
+        cnt = 0
+        def next_prefix():
+            for i in range(100, 105):
+                for j in range(100, 105):
+                    yield '{0}.{1}.0.0/24'.format(i, j)
+
+        for p in next_prefix():
+            g1.local('gobgp global rib add {0}'.format(p))
+            cnt += 1
+
+        cnt2 = 0
+        g = next_prefix()
+        n = g.next()
+        for path in g1.get_global_rib():
+            if path['prefix'] == n:
+                try:
+                    cnt2 += 1
+                    n = g.next()
+                except StopIteration:
+                    break
+
+        self.assertTrue(cnt == cnt2)
 
 if __name__ == '__main__':
     if os.geteuid() is not 0: