server: return flowspec routes in rfc compliant manner

The order of the flowspec routes matters because they will be used
as ACL rules and what rule will be applied depends on the order.
RFC5575 specifies how flowspec routes should be sorted.
This commit implements what it says.

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

5 files changed, 262 insertions, 61 deletions

diff --git a/gobgp/cmd/neighbor.go b/gobgp/cmd/neighbor.go
index c31e6f9a..a9362313 100644
--- a/gobgp/cmd/neighbor.go
+++ b/gobgp/cmd/neighbor.go
@@ -510,7 +510,7 @@ func showNeighborRib(r string, name string, args []string) error {
 
 	isResultSorted := func(rf bgp.RouteFamily) bool {
 		switch rf {
-		case bgp.RF_IPv4_UC, bgp.RF_IPv6_UC:
+		case bgp.RF_IPv4_UC, bgp.RF_IPv6_UC, bgp.RF_FS_IPv4_UC, bgp.RF_FS_IPv6_UC, bgp.RF_FS_IPv4_VPN, bgp.RF_FS_IPv6_VPN, bgp.RF_FS_L2_VPN:
 			return true
 		}
 		return false
diff --git a/packet/bgp/bgp.go b/packet/bgp/bgp.go
index 4fd0898e..97df0b27 100644
--- a/packet/bgp/bgp.go
+++ b/packet/bgp/bgp.go
@@ -3115,6 +3115,161 @@ func (n *FlowSpecNLRI) MarshalJSON() ([]byte, error) {
 	})
 }
 
+//
+// CompareFlowSpecNLRI(n, m) returns
+// -1 when m has precedence
+//  0 when n and m have same precedence
+//  1 when n has precedence
+//
+func CompareFlowSpecNLRI(n, m *FlowSpecNLRI) (int, error) {
+	family := AfiSafiToRouteFamily(n.AFI(), n.SAFI())
+	if family != AfiSafiToRouteFamily(m.AFI(), m.SAFI()) {
+		return 0, fmt.Errorf("address family mismatch")
+	}
+	longer := n.Value
+	shorter := m.Value
+	invert := 1
+	if len(n.Value) < len(m.Value) {
+		longer = m.Value
+		shorter = n.Value
+		invert = -1
+	}
+	for idx, v := range longer {
+		if len(shorter) < idx+1 {
+			return invert, nil
+		}
+		w := shorter[idx]
+		if v.Type() < w.Type() {
+			return invert, nil
+		} else if w.Type() > v.Type() {
+			return invert * -1, nil
+		}
+		if v.Type() == FLOW_SPEC_TYPE_DST_PREFIX || v.Type() == FLOW_SPEC_TYPE_SRC_PREFIX {
+			// RFC5575 5.1
+			//
+			// For IP prefix values (IP destination and source prefix) precedence is
+			// given to the lowest IP value of the common prefix length; if the
+			// common prefix is equal, then the most specific prefix has precedence.
+			var p, q *IPAddrPrefixDefault
+			var pCommon, qCommon uint64
+			if family == RF_FS_IPv4_UC || family == RF_FS_IPv4_VPN {
+				if family == RF_FS_IPv4_VPN {
+					var s, t *LabeledVPNIPAddrPrefix
+					if v.Type() == FLOW_SPEC_TYPE_DST_PREFIX {
+						s = v.(*FlowSpecDestinationPrefix).Prefix.(*LabeledVPNIPAddrPrefix)
+						t = w.(*FlowSpecDestinationPrefix).Prefix.(*LabeledVPNIPAddrPrefix)
+					} else {
+						s = v.(*FlowSpecSourcePrefix).Prefix.(*LabeledVPNIPAddrPrefix)
+						t = w.(*FlowSpecSourcePrefix).Prefix.(*LabeledVPNIPAddrPrefix)
+					}
+					k, _ := s.RD.Serialize()
+					l, _ := t.RD.Serialize()
+					if result := bytes.Compare(k, l); result < 0 {
+						return invert, nil
+					} else if result > 0 {
+						return invert * -1, nil
+					}
+					p = &s.IPAddrPrefixDefault
+					q = &t.IPAddrPrefixDefault
+				} else {
+					if v.Type() == FLOW_SPEC_TYPE_DST_PREFIX {
+						p = &v.(*FlowSpecDestinationPrefix).Prefix.(*IPAddrPrefix).IPAddrPrefixDefault
+						q = &w.(*FlowSpecDestinationPrefix).Prefix.(*IPAddrPrefix).IPAddrPrefixDefault
+					} else {
+						p = &v.(*FlowSpecSourcePrefix).Prefix.(*IPAddrPrefix).IPAddrPrefixDefault
+						q = &w.(*FlowSpecSourcePrefix).Prefix.(*IPAddrPrefix).IPAddrPrefixDefault
+					}
+				}
+				min := p.Length
+				if q.Length < p.Length {
+					min = q.Length
+				}
+				pCommon = uint64(binary.BigEndian.Uint32([]byte(p.Prefix.To4())) >> (32 - min))
+				qCommon = uint64(binary.BigEndian.Uint32([]byte(q.Prefix.To4())) >> (32 - min))
+			} else if family == RF_FS_IPv6_UC || family == RF_FS_IPv6_VPN {
+				if family == RF_FS_IPv6_VPN {
+					var s, t *LabeledVPNIPv6AddrPrefix
+					if v.Type() == FLOW_SPEC_TYPE_DST_PREFIX {
+						s = v.(*FlowSpecDestinationPrefix6).Prefix.(*LabeledVPNIPv6AddrPrefix)
+						t = w.(*FlowSpecDestinationPrefix6).Prefix.(*LabeledVPNIPv6AddrPrefix)
+					} else {
+						s = v.(*FlowSpecSourcePrefix6).Prefix.(*LabeledVPNIPv6AddrPrefix)
+						t = w.(*FlowSpecSourcePrefix6).Prefix.(*LabeledVPNIPv6AddrPrefix)
+					}
+					k, _ := s.RD.Serialize()
+					l, _ := t.RD.Serialize()
+					if result := bytes.Compare(k, l); result < 0 {
+						return invert, nil
+					} else if result > 0 {
+						return invert * -1, nil
+					}
+					p = &s.IPAddrPrefixDefault
+					q = &t.IPAddrPrefixDefault
+				} else {
+					if v.Type() == FLOW_SPEC_TYPE_DST_PREFIX {
+						p = &v.(*FlowSpecDestinationPrefix6).Prefix.(*IPv6AddrPrefix).IPAddrPrefixDefault
+						q = &w.(*FlowSpecDestinationPrefix6).Prefix.(*IPv6AddrPrefix).IPAddrPrefixDefault
+					} else {
+						p = &v.(*FlowSpecSourcePrefix6).Prefix.(*IPv6AddrPrefix).IPAddrPrefixDefault
+						q = &w.(*FlowSpecSourcePrefix6).Prefix.(*IPv6AddrPrefix).IPAddrPrefixDefault
+					}
+				}
+				min := uint(p.Length)
+				if q.Length < p.Length {
+					min = uint(q.Length)
+				}
+				var mask uint
+				if min-64 > 0 {
+					mask = min - 64
+				}
+				pCommon = binary.BigEndian.Uint64([]byte(p.Prefix.To16()[:8])) >> mask
+				qCommon = binary.BigEndian.Uint64([]byte(q.Prefix.To16()[:8])) >> mask
+				if pCommon == qCommon && mask == 0 {
+					mask = 64 - min
+					pCommon = binary.BigEndian.Uint64([]byte(p.Prefix.To16()[8:])) >> mask
+					qCommon = binary.BigEndian.Uint64([]byte(q.Prefix.To16()[8:])) >> mask
+				}
+			}
+
+			if pCommon < qCommon {
+				return invert, nil
+			} else if pCommon > qCommon {
+				return invert * -1, nil
+			} else if p.Length > q.Length {
+				return invert, nil
+			} else if p.Length < q.Length {
+				return invert * -1, nil
+			}
+
+		} else {
+			// RFC5575 5.1
+			//
+			// For all other component types, unless otherwise specified, the
+			// comparison is performed by comparing the component data as a binary
+			// string using the memcmp() function as defined by the ISO C standard.
+			// For strings of different lengths, the common prefix is compared.  If
+			// equal, the longest string is considered to have higher precedence
+			// than the shorter one.
+			p, _ := v.Serialize()
+			q, _ := w.Serialize()
+			min := len(p)
+			if len(q) < len(p) {
+				min = len(q)
+			}
+			if result := bytes.Compare(p[:min], q[:min]); result < 0 {
+				return invert, nil
+			} else if result > 0 {
+				return invert * -1, nil
+			} else if len(p) > len(q) {
+				return invert, nil
+			} else if len(q) > len(p) {
+				return invert * -1, nil
+			}
+		}
+	}
+	return 0, nil
+}
+
 type FlowSpecIPv4Unicast struct {
 	FlowSpecNLRI
 }
diff --git a/server/server.go b/server/server.go
index 81d678b9..df25e91b 100644
--- a/server/server.go
+++ b/server/server.go
@@ -1704,23 +1704,6 @@ func (server *BgpServer) handleGrpc(grpcReq *GrpcRequest) []*SenderMsg {
 		return []*Peer{peer}, err
 	}
 
-	sortedDsts := func(id string, t *table.Table) []*api.Destination {
-		results := make([]*api.Destination, 0, len(t.GetDestinations()))
-
-		r := radix.New()
-		for _, dst := range t.GetDestinations() {
-			if d := dst.ToApiStruct(id); d != nil {
-				r.Insert(dst.RadixKey, d)
-			}
-		}
-		r.Walk(func(s string, v interface{}) bool {
-			results = append(results, v.(*api.Destination))
-			return false
-		})
-
-		return results
-	}
-
 	if server.bgpConfig.Global.Config.As == 0 && grpcReq.RequestType != REQ_START_SERVER {
 		grpcReq.ResponseCh <- &GrpcResponse{
 			ResponseErr: fmt.Errorf("bgpd main loop is not started yet"),
@@ -1788,59 +1771,53 @@ func (server *BgpServer) handleGrpc(grpcReq *GrpcRequest) []*SenderMsg {
 			goto ERROR
 		}
 
-		switch af {
-		case bgp.RF_IPv4_UC, bgp.RF_IPv6_UC:
-			if len(arg.Table.Destinations) > 0 {
-				dsts := []*api.Destination{}
-				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 d := dst.ToApiStruct(id); d != nil {
-							dsts = append(dsts, d)
-						}
-						return true, nil
-					} else {
-						return false, nil
+		dsts := make([]*api.Destination, 0, len(rib.Tables[af].GetDestinations()))
+		if (af == bgp.RF_IPv4_UC || af == bgp.RF_IPv6_UC) && len(arg.Table.Destinations) > 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 d := dst.ToApiStruct(id); d != nil {
+						dsts = append(dsts, d)
 					}
+					return true, nil
+				} else {
+					return false, nil
 				}
-				for _, dst := range arg.Table.Destinations {
-					key := dst.Prefix
-					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
-								}
-							}
+			}
+			for _, dst := range arg.Table.Destinations {
+				key := dst.Prefix
+				if _, err := f(id, key); err != nil {
+					if host := net.ParseIP(key); host != nil {
+						masklen := 32
+						if af == bgp.RF_IPv6_UC {
+							masklen = 128
 						}
-					} else if dst.LongerPrefixes {
-						_, prefix, _ := net.ParseCIDR(key)
-						ones, bits := prefix.Mask.Size()
-						for i := ones + 1; i <= bits; i++ {
-							prefix.Mask = net.CIDRMask(i, bits)
-							f(id, prefix.String())
+						for i := masklen; i > 0; i-- {
+							if y, _ := f(id, fmt.Sprintf("%s/%d", key, i)); y {
+								break
+							}
 						}
 					}
+				} else if dst.LongerPrefixes {
+					_, prefix, _ := net.ParseCIDR(key)
+					ones, bits := prefix.Mask.Size()
+					for i := ones + 1; i <= bits; i++ {
+						prefix.Mask = net.CIDRMask(i, bits)
+						f(id, prefix.String())
+					}
 				}
-				d.Destinations = dsts
-			} else {
-				d.Destinations = sortedDsts(id, rib.Tables[af])
 			}
-		default:
-			d.Destinations = make([]*api.Destination, 0, len(rib.Tables[af].GetDestinations()))
-			for _, dst := range rib.Tables[af].GetDestinations() {
-				if s := dst.ToApiStruct(id); s != nil {
-					d.Destinations = append(d.Destinations, s)
+		} else {
+			for _, dst := range rib.Tables[af].GetSortedDestinations() {
+				if d := dst.ToApiStruct(id); d != nil {
+					dsts = append(dsts, d)
 				}
 			}
 		}
+		d.Destinations = dsts
 		grpcReq.ResponseCh <- &GrpcResponse{
 			Data: &api.GetRibResponse{Table: d},
 		}
diff --git a/table/destination.go b/table/destination.go
index 3642cf7e..91d2d89b 100644
--- a/table/destination.go
+++ b/table/destination.go
@@ -801,3 +801,45 @@ func compareByAge(path1, path2 *Path) *Path {
 func (dest *Destination) String() string {
 	return fmt.Sprintf("Destination NLRI: %s", dest.nlri.String())
 }
+
+type destinations []*Destination
+
+func (d destinations) Len() int {
+	return len(d)
+}
+
+func (d destinations) Swap(i, j int) {
+	d[i], d[j] = d[j], d[i]
+}
+
+func (d destinations) Less(i, j int) bool {
+	switch d[i].routeFamily {
+	case bgp.RF_FS_IPv4_UC, bgp.RF_FS_IPv6_UC, bgp.RF_FS_IPv4_VPN, bgp.RF_FS_IPv6_VPN, bgp.RF_FS_L2_VPN:
+		var s, t *bgp.FlowSpecNLRI
+		switch d[i].routeFamily {
+		case bgp.RF_FS_IPv4_UC:
+			s = &d[i].nlri.(*bgp.FlowSpecIPv4Unicast).FlowSpecNLRI
+			t = &d[j].nlri.(*bgp.FlowSpecIPv4Unicast).FlowSpecNLRI
+		case bgp.RF_FS_IPv6_UC:
+			s = &d[i].nlri.(*bgp.FlowSpecIPv6Unicast).FlowSpecNLRI
+			t = &d[j].nlri.(*bgp.FlowSpecIPv6Unicast).FlowSpecNLRI
+		case bgp.RF_FS_IPv4_VPN:
+			s = &d[i].nlri.(*bgp.FlowSpecIPv4VPN).FlowSpecNLRI
+			t = &d[j].nlri.(*bgp.FlowSpecIPv4VPN).FlowSpecNLRI
+		case bgp.RF_FS_IPv6_VPN:
+			s = &d[i].nlri.(*bgp.FlowSpecIPv6VPN).FlowSpecNLRI
+			t = &d[j].nlri.(*bgp.FlowSpecIPv6VPN).FlowSpecNLRI
+		case bgp.RF_FS_L2_VPN:
+			s = &d[i].nlri.(*bgp.FlowSpecL2VPN).FlowSpecNLRI
+			t = &d[j].nlri.(*bgp.FlowSpecL2VPN).FlowSpecNLRI
+		}
+		if r, _ := bgp.CompareFlowSpecNLRI(s, t); r >= 0 {
+			return true
+		} else {
+			return false
+		}
+	default:
+		strings := sort.StringSlice{d[i].nlri.String(), d[j].nlri.String()}
+		return strings.Less(0, 1)
+	}
+}
diff --git a/table/table.go b/table/table.go
index 9246c6ff..50cecc58 100644
--- a/table/table.go
+++ b/table/table.go
@@ -17,7 +17,9 @@ package table
 
 import (
 	log "github.com/Sirupsen/logrus"
+	"github.com/armon/go-radix"
 	"github.com/osrg/gobgp/packet/bgp"
+	"sort"
 )
 
 type Table struct {
@@ -194,6 +196,31 @@ func (t *Table) getOrCreateDest(nlri bgp.AddrPrefixInterface) *Destination {
 	return dest
 }
 
+func (t *Table) GetSortedDestinations() []*Destination {
+	results := make([]*Destination, 0, len(t.GetDestinations()))
+	switch t.routeFamily {
+	case bgp.RF_IPv4_UC, bgp.RF_IPv6_UC:
+		r := radix.New()
+		for _, dst := range t.GetDestinations() {
+			r.Insert(dst.RadixKey, dst)
+		}
+		r.Walk(func(s string, v interface{}) bool {
+			results = append(results, v.(*Destination))
+			return false
+		})
+	case bgp.RF_FS_IPv4_UC, bgp.RF_FS_IPv6_UC, bgp.RF_FS_IPv4_VPN, bgp.RF_FS_IPv6_VPN, bgp.RF_FS_L2_VPN:
+		for _, dst := range t.GetDestinations() {
+			results = append(results, dst)
+		}
+		sort.Sort(destinations(results))
+	default:
+		for _, dst := range t.GetDestinations() {
+			results = append(results, dst)
+		}
+	}
+	return results
+}
+
 func (t *Table) GetDestinations() map[string]*Destination {
 	return t.destinations
 }