table: use slice instead of homegrown orderedmap

- 4-bytes AS code needs add/delete a new path attribute at the exact
place.
- we would support actions to modify path attributes

Unliley operations on path attributes would perfomance bottle neck so
this commit changes the code to simply use slice to store path
attributes in a path structure.

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

1 files changed, 71 insertions, 132 deletions

diff --git a/table/path.go b/table/path.go
index a5c08e8f..e7536f22 100644
--- a/table/path.go
+++ b/table/path.go
@@ -18,15 +18,16 @@ package table
 import (
 	"fmt"
 	"github.com/osrg/gobgp/packet"
-	"github.com/osrg/gobgp/utils"
+	//"github.com/osrg/gobgp/utils"
 	"net"
+	"reflect"
 )
 
 type Path interface {
 	String() string
-	getPathAttributeMap() *utils.OrderedMap
-	getPathAttribute(int) bgp.PathAttributeInterface
-	clone(forWithdrawal bool) Path
+	GetPathAttrs() []bgp.PathAttributeInterface
+	GetPathAttr(int) (int, bgp.PathAttributeInterface)
+	//	clone(forWithdrawal bool) Path
 	getRouteFamily() RouteFamily
 	setSource(source *PeerInfo)
 	getSource() *PeerInfo
@@ -49,32 +50,20 @@ type PathDefault struct {
 	sourceVerNum           int
 	withdraw               bool
 	nlri                   bgp.AddrPrefixInterface
-	pattrMap               *utils.OrderedMap
+	pathAttrs              []bgp.PathAttributeInterface
 	medSetByTargetNeighbor bool
 }
 
-func NewPathDefault(rf RouteFamily, source *PeerInfo, nlri bgp.AddrPrefixInterface, sourceVerNum int, nexthop net.IP,
-	isWithdraw bool, pattr *utils.OrderedMap, medSetByTargetNeighbor bool) *PathDefault {
+func NewPathDefault(rf RouteFamily, source *PeerInfo, nlri bgp.AddrPrefixInterface, sourceVerNum int, nexthop net.IP, isWithdraw bool, pattrs []bgp.PathAttributeInterface, medSetByTargetNeighbor bool) *PathDefault {
 
-	if !isWithdraw && (pattr == nil || nexthop == nil) {
+	if !isWithdraw && pattrs == nil {
 		logger.Error("Need to provide nexthop and patattrs for path that is not a withdraw.")
 		return nil
 	}
 
 	path := &PathDefault{}
 	path.routeFamily = rf
-	path.pattrMap = utils.NewOrderedMap()
-	if pattr != nil {
-		keyList := pattr.KeyLists()
-		for key := keyList.Front(); key != nil; key = key.Next() {
-			key := key.Value
-			val := pattr.Get(key)
-			e := path.pattrMap.Append(key, val)
-			if e != nil {
-				logger.Error(e)
-			}
-		}
-	}
+	path.pathAttrs = pattrs
 	path.nlri = nlri
 	path.source = source
 	path.nexthop = nexthop
@@ -132,46 +121,53 @@ func (pd *PathDefault) getMedSetByTargetNeighbor() bool {
 	return pd.medSetByTargetNeighbor
 }
 
-//Copy the entity
-func (pd *PathDefault) getPathAttributeMap() *utils.OrderedMap {
-	cpPattr := utils.NewOrderedMap()
-	keyList := pd.pattrMap.KeyLists()
-	for key := keyList.Front(); key != nil; key = key.Next() {
-		key := key.Value
-		val := pd.pattrMap.Get(key)
-		e := cpPattr.Append(key, val)
-		if e != nil {
-			logger.Error(e)
+func (pd *PathDefault) GetPathAttrs() []bgp.PathAttributeInterface {
+	return pd.pathAttrs
+}
+
+func (pd *PathDefault) GetPathAttr(pattrType int) (int, bgp.PathAttributeInterface) {
+	attrMap := [bgp.BGP_ATTR_TYPE_AS4_AGGREGATOR + 1]reflect.Type{}
+	attrMap[bgp.BGP_ATTR_TYPE_ORIGIN] = reflect.TypeOf(&bgp.PathAttributeOrigin{})
+	attrMap[bgp.BGP_ATTR_TYPE_AS_PATH] = reflect.TypeOf(&bgp.PathAttributeAsPath{})
+	attrMap[bgp.BGP_ATTR_TYPE_NEXT_HOP] = reflect.TypeOf(&bgp.PathAttributeNextHop{})
+	attrMap[bgp.BGP_ATTR_TYPE_MULTI_EXIT_DISC] = reflect.TypeOf(&bgp.PathAttributeMultiExitDisc{})
+	attrMap[bgp.BGP_ATTR_TYPE_LOCAL_PREF] = reflect.TypeOf(&bgp.PathAttributeLocalPref{})
+	attrMap[bgp.BGP_ATTR_TYPE_ATOMIC_AGGREGATE] = reflect.TypeOf(&bgp.PathAttributeAtomicAggregate{})
+	attrMap[bgp.BGP_ATTR_TYPE_AGGREGATOR] = reflect.TypeOf(&bgp.PathAttributeAggregator{})
+	attrMap[bgp.BGP_ATTR_TYPE_COMMUNITIES] = reflect.TypeOf(&bgp.PathAttributeCommunities{})
+	attrMap[bgp.BGP_ATTR_TYPE_ORIGINATOR_ID] = reflect.TypeOf(&bgp.PathAttributeOriginatorId{})
+	attrMap[bgp.BGP_ATTR_TYPE_CLUSTER_LIST] = reflect.TypeOf(&bgp.PathAttributeClusterList{})
+	attrMap[bgp.BGP_ATTR_TYPE_MP_REACH_NLRI] = reflect.TypeOf(&bgp.PathAttributeMpReachNLRI{})
+	attrMap[bgp.BGP_ATTR_TYPE_MP_UNREACH_NLRI] = reflect.TypeOf(&bgp.PathAttributeMpUnreachNLRI{})
+	attrMap[bgp.BGP_ATTR_TYPE_EXTENDED_COMMUNITIES] = reflect.TypeOf(&bgp.PathAttributeExtendedCommunities{})
+	attrMap[bgp.BGP_ATTR_TYPE_AS4_PATH] = reflect.TypeOf(&bgp.PathAttributeAs4Path{})
+	attrMap[bgp.BGP_ATTR_TYPE_AS4_AGGREGATOR] = reflect.TypeOf(&bgp.PathAttributeAs4Aggregator{})
+
+	t := attrMap[pattrType]
+	for i, p := range pd.pathAttrs {
+		if t == reflect.TypeOf(p) {
+			return i, p
 		}
 	}
-	return cpPattr
-}
-
-func (pd *PathDefault) getPathAttribute(pattrType int) bgp.PathAttributeInterface {
-	attr := pd.pattrMap.Get(pattrType)
-	if attr == nil {
-		logger.Debugf("Attribute Type %s is not found", AttributeType(pattrType))
-		return nil
-	}
-	return attr.(bgp.PathAttributeInterface)
-}
-
-func (pi *PathDefault) clone(forWithdrawal bool) Path {
-	pathAttrs := utils.NewOrderedMap()
-	if !forWithdrawal {
-		pathAttrs = pi.getPathAttributeMap()
-	}
-	def := NewPathDefault(pi.getRouteFamily(), pi.getSource(), pi.GetNlri(), pi.getSourceVerNum(),
-		pi.getNexthop(), forWithdrawal, pathAttrs, pi.getMedSetByTargetNeighbor())
-	switch pi.getRouteFamily() {
-	case RF_IPv4_UC:
-		return &IPv4Path{PathDefault: def}
-	case RF_IPv6_UC:
-		return &IPv6Path{PathDefault: def}
-	default:
-		return def
-	}
-}
+	return -1, nil
+}
+
+// func (pi *PathDefault) clone(forWithdrawal bool) Path {
+// 	pathAttrs := utils.NewOrderedMap()
+// 	if !forWithdrawal {
+// 		pathAttrs = pi.getPathAttributeMap()
+// 	}
+// 	def := NewPathDefault(pi.getRouteFamily(), pi.getSource(), pi.GetNlri(), pi.getSourceVerNum(),
+// 		pi.getNexthop(), forWithdrawal, pathAttrs, pi.getMedSetByTargetNeighbor())
+// 	switch pi.getRouteFamily() {
+// 	case RF_IPv4_UC:
+// 		return &IPv4Path{PathDefault: def}
+// 	case RF_IPv6_UC:
+// 		return &IPv6Path{PathDefault: def}
+// 	default:
+// 		return def
+// 	}
+//}
 
 // return Path's string representation
 func (pi *PathDefault) String() string {
@@ -179,7 +175,7 @@ func (pi *PathDefault) String() string {
 	str = str + fmt.Sprintf(" NLRI: %s, ", pi.getPrefix().String())
 	str = str + fmt.Sprintf(" nexthop: %s, ", pi.getNexthop().String())
 	str = str + fmt.Sprintf(" withdraw: %s, ", pi.isWithdraw())
-	str = str + fmt.Sprintf(" path attributes: %s, ", pi.getPathAttributeMap())
+	//str = str + fmt.Sprintf(" path attributes: %s, ", pi.getPathAttributeMap())
 	return str
 }
 
@@ -194,57 +190,11 @@ func (pi *PathDefault) getPrefix() net.IP {
 	return nil
 }
 
-func createPathAttributeMap(pathAttributes []bgp.PathAttributeInterface) *utils.OrderedMap {
-
-	pathAttrMap := utils.NewOrderedMap()
-	for _, attr := range pathAttributes {
-		var err error
-		switch a := attr.(type) {
-		case *bgp.PathAttributeOrigin:
-			err = pathAttrMap.Append(bgp.BGP_ATTR_TYPE_ORIGIN, a)
-		case *bgp.PathAttributeAsPath:
-			err = pathAttrMap.Append(bgp.BGP_ATTR_TYPE_AS_PATH, a)
-		case *bgp.PathAttributeNextHop:
-			err = pathAttrMap.Append(bgp.BGP_ATTR_TYPE_NEXT_HOP, a)
-		case *bgp.PathAttributeMultiExitDisc:
-			err = pathAttrMap.Append(bgp.BGP_ATTR_TYPE_MULTI_EXIT_DISC, a)
-		case *bgp.PathAttributeLocalPref:
-			err = pathAttrMap.Append(bgp.BGP_ATTR_TYPE_LOCAL_PREF, a)
-		case *bgp.PathAttributeAtomicAggregate:
-			err = pathAttrMap.Append(bgp.BGP_ATTR_TYPE_ATOMIC_AGGREGATE, a)
-		case *bgp.PathAttributeAggregator:
-			err = pathAttrMap.Append(bgp.BGP_ATTR_TYPE_AGGREGATOR, a)
-		case *bgp.PathAttributeCommunities:
-			err = pathAttrMap.Append(bgp.BGP_ATTR_TYPE_COMMUNITIES, a)
-		case *bgp.PathAttributeOriginatorId:
-			err = pathAttrMap.Append(bgp.BGP_ATTR_TYPE_ORIGINATOR_ID, a)
-		case *bgp.PathAttributeClusterList:
-			err = pathAttrMap.Append(bgp.BGP_ATTR_TYPE_CLUSTER_LIST, a)
-		case *bgp.PathAttributeMpReachNLRI:
-			err = pathAttrMap.Append(bgp.BGP_ATTR_TYPE_MP_REACH_NLRI, a)
-		case *bgp.PathAttributeMpUnreachNLRI:
-			err = pathAttrMap.Append(bgp.BGP_ATTR_TYPE_MP_UNREACH_NLRI, a)
-		case *bgp.PathAttributeExtendedCommunities:
-			err = pathAttrMap.Append(bgp.BGP_ATTR_TYPE_EXTENDED_COMMUNITIES, a)
-		case *bgp.PathAttributeAs4Path:
-			err = pathAttrMap.Append(bgp.BGP_ATTR_TYPE_AS4_PATH, a)
-		case *bgp.PathAttributeAs4Aggregator:
-			err = pathAttrMap.Append(bgp.BGP_ATTR_TYPE_AS4_AGGREGATOR, a)
-		}
-		if err != nil {
-			return nil
-		}
-	}
-	return pathAttrMap
-}
-
 // create Path object based on route family
-func CreatePath(source *PeerInfo, nlri bgp.AddrPrefixInterface,
-	pathAttributes []bgp.PathAttributeInterface, isWithdraw bool) Path {
+func CreatePath(source *PeerInfo, nlri bgp.AddrPrefixInterface, attrs []bgp.PathAttributeInterface, isWithdraw bool) Path {
 
 	rf := RouteFamily(int(nlri.AFI())<<16 | int(nlri.SAFI()))
 	logger.Debugf("afi: %d, safi: %d ", int(nlri.AFI()), nlri.SAFI())
-	pathAttrMap := createPathAttributeMap(pathAttributes)
 	var path Path
 	var sourceVerNum int = 1
 
@@ -255,27 +205,10 @@ func CreatePath(source *PeerInfo, nlri bgp.AddrPrefixInterface,
 	switch rf {
 	case RF_IPv4_UC:
 		logger.Debugf("RouteFamily : %s", RF_IPv4_UC.String())
-		var nexthop net.IP
-
-		if !isWithdraw {
-			nexthop_attr := pathAttrMap.Get(bgp.BGP_ATTR_TYPE_NEXT_HOP).(*bgp.PathAttributeNextHop)
-			nexthop = nexthop_attr.Value
-		} else {
-			nexthop = nil
-		}
-
-		path = NewIPv4Path(source, nlri, sourceVerNum, nexthop, isWithdraw, pathAttrMap, false)
+		path = NewIPv4Path(source, nlri, sourceVerNum, isWithdraw, attrs, false)
 	case RF_IPv6_UC:
 		logger.Debugf("RouteFamily : %s", RF_IPv6_UC.String())
-		var nexthop net.IP
-
-		if !isWithdraw {
-			mpattr := pathAttrMap.Get(bgp.BGP_ATTR_TYPE_MP_REACH_NLRI).(*bgp.PathAttributeMpReachNLRI)
-			nexthop = mpattr.Nexthop
-		} else {
-			nexthop = nil
-		}
-		path = NewIPv6Path(source, nlri, sourceVerNum, nexthop, isWithdraw, pathAttrMap, false)
+		path = NewIPv6Path(source, nlri, sourceVerNum, isWithdraw, attrs, false)
 	}
 	return path
 }
@@ -287,10 +220,13 @@ type IPv4Path struct {
 	*PathDefault
 }
 
-func NewIPv4Path(source *PeerInfo, nlri bgp.AddrPrefixInterface, sourceVerNum int, nexthop net.IP,
-	isWithdraw bool, pattr *utils.OrderedMap, medSetByTargetNeighbor bool) *IPv4Path {
+func NewIPv4Path(source *PeerInfo, nlri bgp.AddrPrefixInterface, sourceVerNum int, isWithdraw bool, attrs []bgp.PathAttributeInterface, medSetByTargetNeighbor bool) *IPv4Path {
 	ipv4Path := &IPv4Path{}
-	ipv4Path.PathDefault = NewPathDefault(RF_IPv4_UC, source, nlri, sourceVerNum, nexthop, isWithdraw, pattr, medSetByTargetNeighbor)
+	ipv4Path.PathDefault = NewPathDefault(RF_IPv4_UC, source, nlri, sourceVerNum, nil, isWithdraw, attrs, medSetByTargetNeighbor)
+	if !isWithdraw {
+		_, nexthop_attr := ipv4Path.GetPathAttr(bgp.BGP_ATTR_TYPE_NEXT_HOP)
+		ipv4Path.nexthop = nexthop_attr.(*bgp.PathAttributeNextHop).Value
+	}
 	return ipv4Path
 }
 
@@ -305,10 +241,13 @@ type IPv6Path struct {
 	*PathDefault
 }
 
-func NewIPv6Path(source *PeerInfo, nlri bgp.AddrPrefixInterface, sourceVerNum int, nexthop net.IP,
-	isWithdraw bool, pattr *utils.OrderedMap, medSetByTargetNeighbor bool) *IPv6Path {
+func NewIPv6Path(source *PeerInfo, nlri bgp.AddrPrefixInterface, sourceVerNum int, isWithdraw bool, attrs []bgp.PathAttributeInterface, medSetByTargetNeighbor bool) *IPv6Path {
 	ipv6Path := &IPv6Path{}
-	ipv6Path.PathDefault = NewPathDefault(RF_IPv6_UC, source, nlri, sourceVerNum, nexthop, isWithdraw, pattr, medSetByTargetNeighbor)
+	ipv6Path.PathDefault = NewPathDefault(RF_IPv6_UC, source, nlri, sourceVerNum, nil, isWithdraw, attrs, medSetByTargetNeighbor)
+	if !isWithdraw {
+		_, mpattr := ipv6Path.GetPathAttr(bgp.BGP_ATTR_TYPE_MP_REACH_NLRI)
+		ipv6Path.nexthop = mpattr.(*bgp.PathAttributeMpReachNLRI).Nexthop
+	}
 	return ipv6Path
 }
 
@@ -331,6 +270,6 @@ func (ipv6p *IPv6Path) String() string {
 	str = str + fmt.Sprintf(" NLRI: %s, ", ipv6p.getPrefix().String())
 	str = str + fmt.Sprintf(" nexthop: %s, ", ipv6p.getNexthop().String())
 	str = str + fmt.Sprintf(" withdraw: %s, ", ipv6p.isWithdraw())
-	str = str + fmt.Sprintf(" path attributes: %s, ", ipv6p.getPathAttributeMap())
+	//str = str + fmt.Sprintf(" path attributes: %s, ", ipv6p.getPathAttributeMap())
 	return str
 }