From 90b0bd64e0777f0023976f92d427920f9a6b5b21 Mon Sep 17 00:00:00 2001 From: FUJITA Tomonori Date: Sat, 20 Dec 2014 06:09:33 -0800 Subject: 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 --- table/path.go | 203 ++++++++++++++++++++-------------------------------------- 1 file changed, 71 insertions(+), 132 deletions(-) (limited to 'table/path.go') 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 } -- cgit v1.2.3