policy: make AS Path match regular expression work as quagga and cisco

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

3 files changed, 129 insertions, 142 deletions

diff --git a/policy/policy.go b/policy/policy.go
index 5d0dc631..21bae110 100644
--- a/policy/policy.go
+++ b/policy/policy.go
@@ -383,8 +383,8 @@ func (c *AsPathLengthCondition) evaluate(path *table.Path) bool {
 
 type AsPathCondition struct {
 	DefaultCondition
-	AsPathList  []*AsPathElement
-	MatchOption config.MatchSetOptionsType
+	AsRegExpList []*regexp.Regexp
+	MatchOption  config.MatchSetOptionsType
 }
 
 type AsnPos int
@@ -396,89 +396,43 @@ const (
 	AS_ONLY
 )
 
-type AsPathElement struct {
-	postiion  AsnPos
-	asStr     string
-	asRegExps []*regexp.Regexp
-}
+const (
+	ASPATH_REGEXP_MAGIC = "(^|[,{}() ]|$)"
+)
 
-// create AsPathCondition object
-// AsPathCondition supports only following regexp:
-// - ^100  (from as100)
-// - ^100$ (from as100 and originated by as100)
-// - 100$  (originated by as100)
-// - 100   (from or through or originated by as100)
 func NewAsPathCondition(matchSet config.MatchAsPathSet, defAsPathSetList []config.AsPathSet) *AsPathCondition {
-
 	asPathSetName := matchSet.AsPathSet
 	options := matchSet.MatchSetOptions
 
-	asPathList := make([]*AsPathElement, 0)
+	asRegExpList := make([]*regexp.Regexp, 0)
 	for _, asPathSet := range defAsPathSetList {
 		if asPathSet.AsPathSetName == asPathSetName {
 			for _, aspath := range asPathSet.AsPathList {
 				a := aspath.AsPath
 				if len(a) != 0 {
-					isTop := a[:1] == "^"
-					if isTop {
-						a = a[1:]
-					}
-					isEnd := a[len(a)-1:] == "$"
-					if isEnd {
-						a = a[:len(a)-1]
-					}
-					elems := strings.Split(a, "_")
-					asRegExps := make([]*regexp.Regexp, 0)
-					for _, el := range elems {
-						if len(el) == 0 {
-							log.WithFields(log.Fields{
-								"Topic": "Policy",
-								"Type":  "AsPath Condition",
-								"Value": aspath.AsPath,
-								"Elem":  el,
-							}).Error("invalid element. do not enter a blank.")
-							return nil
-						}
-						regElem, err := regexp.Compile(el)
-						if err != nil {
-							log.WithFields(log.Fields{
-								"Topic": "Policy",
-								"Type":  "AsPath Condition",
-								"Value": aspath.AsPath,
-								"Elem":  el,
-								"Error": err,
-							}).Error("can not comple AS_PATH values to Regular expressions.")
-							return nil
-						}
-						asRegExps = append(asRegExps, regElem)
-					}
-
-					e := &AsPathElement{}
-					e.asRegExps = asRegExps
-					e.asStr = a
-					if isTop && isEnd {
-						e.postiion = AS_ONLY
-					} else if isTop && !isEnd {
-						e.postiion = AS_FROM
-					} else if !isTop && isEnd {
-						e.postiion = AS_ORIGIN
-					} else {
-						e.postiion = AS_ANY
+					r, err := regexp.Compile(strings.Replace(a, "_", ASPATH_REGEXP_MAGIC, -1))
+					if err != nil {
+						log.WithFields(log.Fields{
+							"Topic": "Policy",
+							"Type":  "AsPath Condition",
+							"Value": aspath.AsPath,
+							"Error": err,
+						}).Error("can not comple AS_PATH values to Regular expressions.")
+						return nil
 					}
-					asPathList = append(asPathList, e)
 
+					asRegExpList = append(asRegExpList, r)
 				} else {
 					log.WithFields(log.Fields{
 						"Topic": "Policy",
 						"Type":  "AsPath Condition",
 					}).Error("does not parse AS_PATH condition value.")
-
 					return nil
 				}
 			}
 			c := &AsPathCondition{
-				AsPathList:  asPathList,
-				MatchOption: options,
+				AsRegExpList: asRegExpList,
+				MatchOption:  options,
 			}
 			return c
 		}
@@ -486,101 +440,41 @@ func NewAsPathCondition(matchSet config.MatchAsPathSet, defAsPathSetList []confi
 	return nil
 }
 
-func (c *AsPathCondition) checkMembers(aspath []uint32, checkAll bool) bool {
-
-	checkElem := func(checkType AsnPos, regElems []*regexp.Regexp) bool {
-		aslen := len(aspath)
-		reglen := len(regElems)
-
-		if aslen < reglen {
-			return false
-		}
-
-		switch checkType {
-		case AS_ONLY:
-			if aslen != reglen {
-				return false
-			}
-			fallthrough
-		case AS_FROM:
-			for i := 0; i < reglen; i++ {
-				if !regElems[i].MatchString(fmt.Sprintf("%d", aspath[i])) {
-					return false
-				}
-			}
-		case AS_ORIGIN:
-			for i := 0; i < reglen; i++ {
-				if !regElems[reglen-i-1].MatchString(fmt.Sprintf("%d", aspath[aslen-i-1])) {
-					return false
-				}
-			}
-		case AS_ANY:
-			for i := 0; i < aslen; i++ {
-				eMatched := true
-				if aslen < i+reglen {
-					break
-				}
-				for j := 0; j < reglen; j++ {
-					if !regElems[j].MatchString(fmt.Sprintf("%d", aspath[i+j])) {
-						eMatched = false
-						break
-					}
-				}
-				if eMatched {
-					return true
-				}
-			}
-			return false
-		}
-		return true
-	}
-
-	result := false
-	if checkAll {
-		result = true
-	}
-	for _, member := range c.AsPathList {
-		if checkElem(member.postiion, member.asRegExps) {
+func (c *AsPathCondition) checkMembers(aspathStr string, checkAll bool) bool {
+	for _, r := range c.AsRegExpList {
+		if r.MatchString(aspathStr) {
 			log.WithFields(log.Fields{
 				"Topic":     "Policy",
 				"Condition": "aspath length",
-				"ASN":       member.asStr,
-				"Position":  member.postiion,
+				"AS":        aspathStr,
+				"ASN":       r,
 			}).Debug("aspath condition matched")
 
 			if !checkAll {
-				result = true
-				break
+				return true
 			}
-
 		} else {
 			if checkAll {
-				result = false
-				break
+				return false
 			}
 		}
 	}
-
-	return result
+	return checkAll
 }
 
 // compare AS_PATH in the message's AS_PATH attribute with
 // the one in condition.
 func (c *AsPathCondition) evaluate(path *table.Path) bool {
 
-	aspath := path.GetAsSeqList()
-
-	if c == nil || len(aspath) == 0 {
-		return false
-	}
+	aspathStr := path.GetAsString()
 
 	result := false
 	if c.MatchOption == config.MATCH_SET_OPTIONS_TYPE_ALL {
-		result = c.checkMembers(aspath, true)
+		result = c.checkMembers(aspathStr, true)
 	} else if c.MatchOption == config.MATCH_SET_OPTIONS_TYPE_ANY {
-		result = c.checkMembers(aspath, false)
+		result = c.checkMembers(aspathStr, false)
 	} else if c.MatchOption == config.MATCH_SET_OPTIONS_TYPE_INVERT {
-		result = !c.checkMembers(aspath, false)
+		result = !c.checkMembers(aspathStr, false)
 	}
 
 	log.WithFields(log.Fields{
diff --git a/policy/policy_test.go b/policy/policy_test.go
index 72bf5c6c..069f2dad 100644
--- a/policy/policy_test.go
+++ b/policy/policy_test.go
@@ -24,9 +24,11 @@ import (
 	"github.com/stretchr/testify/assert"
 	"math"
 	"net"
+	"regexp"
 	"strconv"
 	"strings"
 	"testing"
+	"time"
 )
 
 func init() {
@@ -600,7 +602,6 @@ func TestAsPathConditionEvaluate(t *testing.T) {
 	path1 := table.ProcessMessage(updateMsg1, peer)[0]
 
 	aspathParam2 := []bgp.AsPathParamInterface{
-		bgp.NewAsPathParam(2, []uint16{65010}),
 		bgp.NewAsPathParam(1, []uint16{65010}),
 	}
 	aspath2 := bgp.NewPathAttributeAsPath(aspathParam2)
@@ -653,7 +654,6 @@ func TestAsPathConditionEvaluate(t *testing.T) {
 		},
 	}
 
-
 	asPathSetList := []config.AsPathSet{asPathSet1, asPathSet2, asPathSet3,
 		asPathSet4, asPathSet5, asPathSet6}
 
@@ -681,7 +681,7 @@ func TestAsPathConditionEvaluate(t *testing.T) {
 	assert.Equal(t, true, p2.evaluate(path1))
 	assert.Equal(t, true, p3.evaluate(path1))
 	assert.Equal(t, false, p4.evaluate(path1))
-	assert.Equal(t, false, p5.evaluate(path1))
+	assert.Equal(t, true, p5.evaluate(path1))
 	assert.Equal(t, false, p6.evaluate(path1))
 	assert.Equal(t, true, p6.evaluate(path2))
 
@@ -709,7 +709,6 @@ func TestMultipleAsPathConditionEvaluate(t *testing.T) {
 	table.UpdatePathAttrs4ByteAs(updateMsg1.Body.(*bgp.BGPUpdate))
 	path1 := table.ProcessMessage(updateMsg1, peer)[0]
 
-
 	// create match condition
 	asPathSet1 := config.AsPathSet{
 		AsPathSetName: "asset1",
@@ -742,7 +741,7 @@ func TestMultipleAsPathConditionEvaluate(t *testing.T) {
 	asPathSet5 := config.AsPathSet{
 		AsPathSetName: "asset5",
 		AsPathList: []config.AsPath{
-			config.AsPath{AsPath: "^65001_65000_54000_65004_65005$"},
+			config.AsPath{AsPath: "^65001 65000 54000 65004 65005 65001,65010,54000,65004,65005$"},
 		},
 	}
 
@@ -803,10 +802,76 @@ func TestMultipleAsPathConditionEvaluate(t *testing.T) {
 	assert.Equal(t, true, p5.evaluate(path1))
 	assert.Equal(t, true, p6.evaluate(path1))
 	assert.Equal(t, true, p7.evaluate(path1))
-	assert.Equal(t, false, p8.evaluate(path1))
+	assert.Equal(t, true, p8.evaluate(path1))
 	assert.Equal(t, false, p9.evaluate(path1))
 }
 
+func TestAsPathCondition(t *testing.T) {
+	type astest struct {
+		path   *table.Path
+		result bool
+	}
+
+	makeTest := func(asPathAttrType uint8, ases []uint32, result bool) astest {
+		aspathParam := []bgp.AsPathParamInterface{
+			bgp.NewAs4PathParam(asPathAttrType, ases),
+		}
+		pathAttributes := []bgp.PathAttributeInterface{bgp.NewPathAttributeAsPath(aspathParam)}
+		p := table.NewPath(nil, nil, false, pathAttributes, false, time.Time{}, false)
+		return astest{
+			path:   p,
+			result: result,
+		}
+	}
+
+	tests := make(map[string][]astest)
+
+	tests["^(100_)+(200_)+$"] = []astest{
+		makeTest(bgp.BGP_ASPATH_ATTR_TYPE_SEQ, []uint32{100, 200}, true),
+		makeTest(bgp.BGP_ASPATH_ATTR_TYPE_SEQ, []uint32{100, 100, 200}, true),
+		makeTest(bgp.BGP_ASPATH_ATTR_TYPE_SEQ, []uint32{100, 100, 200, 200}, true),
+		makeTest(bgp.BGP_ASPATH_ATTR_TYPE_SEQ, []uint32{100, 100, 200, 200, 300}, false),
+	}
+
+	aslen255 := func() []uint32 {
+		r := make([]uint32, 255)
+		for i := 0; i < 255; i++ {
+			r[i] = 1
+		}
+		return r
+	}()
+	tests["^([0-9]+_){0,255}$"] = []astest{
+		makeTest(bgp.BGP_ASPATH_ATTR_TYPE_SEQ, aslen255, true),
+		makeTest(bgp.BGP_ASPATH_ATTR_TYPE_SEQ, append(aslen255, 1), false),
+	}
+
+	tests["(_7521)$"] = []astest{
+		makeTest(bgp.BGP_ASPATH_ATTR_TYPE_SEQ, []uint32{7521}, true),
+		makeTest(bgp.BGP_ASPATH_ATTR_TYPE_SEQ, []uint32{1000, 7521}, true),
+		makeTest(bgp.BGP_ASPATH_ATTR_TYPE_SEQ, []uint32{7521, 1000}, false),
+		makeTest(bgp.BGP_ASPATH_ATTR_TYPE_SEQ, []uint32{1000, 7521, 100}, false),
+	}
+
+	for k, v := range tests {
+		r, _ := regexp.Compile(strings.Replace(k, "_", ASPATH_REGEXP_MAGIC, -1))
+		c := &AsPathCondition{
+			AsRegExpList: []*regexp.Regexp{r},
+			MatchOption:  config.MATCH_SET_OPTIONS_TYPE_ANY,
+		}
+		for _, a := range v {
+			result := c.evaluate(a.path)
+			if a.result != result {
+				log.WithFields(log.Fields{
+					"EXP":      k,
+					"ASN":      r,
+					"ASSTR":    a.path.GetAsString(),
+					"Expected": a.result,
+					"Result":   result,
+				}).Fatal("failed")
+			}
+		}
+	}
+}
 
 func TestAsPathConditionWithOtherCondition(t *testing.T) {
 
diff --git a/table/path.go b/table/path.go
index 224cda9d..b3a84d9d 100644
--- a/table/path.go
+++ b/table/path.go
@@ -297,6 +297,34 @@ func (path *Path) GetAsPathLen() int {
 	return length
 }
 
+func (path *Path) GetAsString() string {
+	r := ""
+	if _, attr := path.getPathAttr(bgp.BGP_ATTR_TYPE_AS_PATH); attr != nil {
+		aspath := attr.(*bgp.PathAttributeAsPath)
+		for i, paramIf := range aspath.Value {
+			segment := paramIf.(*bgp.As4PathParam)
+			if i != 0 {
+				r += " "
+			}
+
+			sep := " "
+			switch segment.Type {
+			case bgp.BGP_ASPATH_ATTR_TYPE_SET, bgp.BGP_ASPATH_ATTR_TYPE_CONFED_SET:
+				sep = ","
+			case bgp.BGP_ASPATH_ATTR_TYPE_SEQ, bgp.BGP_ASPATH_ATTR_TYPE_CONFED_SEQ:
+				sep = " "
+			}
+			for j, as := range segment.AS {
+				r += fmt.Sprintf("%d", as)
+				if j != len(segment.AS)-1 {
+					r += sep
+				}
+			}
+		}
+	}
+	return r
+}
+
 func (path *Path) GetAsList() []uint32 {
 	return path.getAsListofSpecificType(true, true)