path: root/table/path.go

// Copyright (C) 2014 Nippon Telegraph and Telephone Corporation.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//    http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
// implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package table

import (
	"encoding/json"
	"fmt"
	log "github.com/Sirupsen/logrus"
	"github.com/osrg/gobgp/config"
	"github.com/osrg/gobgp/packet"
	"net"
	"reflect"
	"time"
)

type Path interface {
	String() string
	getPathAttrs() []bgp.PathAttributeInterface
	getPathAttr(bgp.BGPAttrType) (int, bgp.PathAttributeInterface)
	updatePathAttrs(global *config.Global, peer *config.Neighbor)
	GetRouteFamily() bgp.RouteFamily
	setSource(source *PeerInfo)
	getSource() *PeerInfo
	setNexthop(nexthop net.IP)
	GetNexthop() net.IP
	setWithdraw(withdraw bool)
	IsWithdraw() bool
	getNlri() bgp.AddrPrefixInterface
	getPrefix() string
	setMedSetByTargetNeighbor(medSetByTargetNeighbor bool)
	getMedSetByTargetNeighbor() bool
	clone(IsWithdraw bool) Path
	getTimestamp() time.Time
	setTimestamp(t time.Time)
	MarshalJSON() ([]byte, error)
}

type PathDefault struct {
	routeFamily            bgp.RouteFamily
	source                 *PeerInfo
	nexthop                net.IP
	withdraw               bool
	nlri                   bgp.AddrPrefixInterface
	pathAttrs              []bgp.PathAttributeInterface
	medSetByTargetNeighbor bool
	timestamp              time.Time
}

func NewPathDefault(rf bgp.RouteFamily, source *PeerInfo, nlri bgp.AddrPrefixInterface, nexthop net.IP, isWithdraw bool, pattrs []bgp.PathAttributeInterface, medSetByTargetNeighbor bool, now time.Time) *PathDefault {
	if !isWithdraw && pattrs == nil {
		log.WithFields(log.Fields{
			"Topic":   "Table",
			"Key":     nlri.String(),
			"Peer":    source.Address.String(),
			"Nexthop": nexthop.String(),
		}).Error("Need to provide nexthop and patattrs for the path that is not withdraw.")
		return nil
	}

	path := &PathDefault{}
	path.routeFamily = rf
	path.pathAttrs = pattrs
	path.nlri = nlri
	path.source = source
	path.nexthop = nexthop
	path.withdraw = isWithdraw
	path.medSetByTargetNeighbor = medSetByTargetNeighbor
	path.timestamp = now
	return path
}

func cloneAsPath(asAttr *bgp.PathAttributeAsPath) *bgp.PathAttributeAsPath {
	newASparams := make([]bgp.AsPathParamInterface, len(asAttr.Value))
	for i, param := range asAttr.Value {
		asParam := param.(*bgp.As4PathParam)
		as := make([]uint32, len(asParam.AS))
		copy(as, asParam.AS)
		newASparams[i] = bgp.NewAs4PathParam(asParam.Type, as)
	}
	return bgp.NewPathAttributeAsPath(newASparams)
}

func (pd *PathDefault) updatePathAttrs(global *config.Global, peer *config.Neighbor) {
	newPathAttrs := make([]bgp.PathAttributeInterface, len(pd.pathAttrs))
	for i, v := range pd.pathAttrs {
		newPathAttrs[i] = v
	}
	pd.pathAttrs = newPathAttrs

	if peer.RouteServer.RouteServerClient {
		return
	}

	if peer.PeerType == config.PEER_TYPE_EXTERNAL {
		// NEXTHOP handling
		idx, _ := pd.getPathAttr(bgp.BGP_ATTR_TYPE_NEXT_HOP)
		if idx < 0 {
			log.Fatal("missing NEXTHOP mandatory attribute")
		}
		newNexthop := bgp.NewPathAttributeNextHop(peer.LocalAddress.String())
		newPathAttrs[idx] = newNexthop

		// AS_PATH handling
		//
		//  When a given BGP speaker advertises the route to an external
		//  peer, the advertising speaker updates the AS_PATH attribute
		//  as follows:
		//  1) if the first path segment of the AS_PATH is of type
		//     AS_SEQUENCE, the local system prepends its own AS num as
		//     the last element of the sequence (put it in the left-most
		//     position with respect to the position of  octets in the
		//     protocol message).  If the act of prepending will cause an
		//     overflow in the AS_PATH segment (i.e.,  more than 255
		//     ASes), it SHOULD prepend a new segment of type AS_SEQUENCE
		//     and prepend its own AS number to this new segment.
		//
		//  2) if the first path segment of the AS_PATH is of type AS_SET
		//     , the local system prepends a new path segment of type
		//     AS_SEQUENCE to the AS_PATH, including its own AS number in
		//     that segment.
		//
		//  3) if the AS_PATH is empty, the local system creates a path
		//     segment of type AS_SEQUENCE, places its own AS into that
		//     segment, and places that segment into the AS_PATH.
		idx, originalAsPath := pd.getPathAttr(bgp.BGP_ATTR_TYPE_AS_PATH)
		if idx < 0 {
			log.Fatal("missing AS_PATH mandatory attribute")
		}
		asPath := cloneAsPath(originalAsPath.(*bgp.PathAttributeAsPath))
		newPathAttrs[idx] = asPath
		fst := asPath.Value[0].(*bgp.As4PathParam)
		if len(asPath.Value) > 0 && fst.Type == bgp.BGP_ASPATH_ATTR_TYPE_SEQ &&
			fst.ASLen() < 255 {
			fst.AS = append([]uint32{global.As}, fst.AS...)
			fst.Num += 1
		} else {
			p := bgp.NewAs4PathParam(bgp.BGP_ASPATH_ATTR_TYPE_SEQ, []uint32{global.As})
			asPath.Value = append([]bgp.AsPathParamInterface{p}, asPath.Value...)
		}

		// MED Handling
		idx, _ = pd.getPathAttr(bgp.BGP_ATTR_TYPE_MULTI_EXIT_DISC)
		if idx >= 0 {
			newPathAttrs = append(newPathAttrs[:idx], newPathAttrs[idx+1:]...)
		}
	} else if peer.PeerType == config.PEER_TYPE_INTERNAL {
		// For iBGP peers we are required to send local-pref attribute
		// for connected or local prefixes.
		// We set default local-pref 100.
		p := bgp.NewPathAttributeLocalPref(100)
		idx, _ := pd.getPathAttr(bgp.BGP_ATTR_TYPE_LOCAL_PREF)
		if idx < 0 {
			newPathAttrs = append(newPathAttrs, p)
		} else {
			newPathAttrs[idx] = p
		}
	} else {
		log.WithFields(log.Fields{
			"Topic": "Peer",
			"Key":   peer.NeighborAddress,
		}).Warnf("invalid peer type: %d", peer.PeerType)
	}
}

func (pd *PathDefault) getTimestamp() time.Time {
	return pd.timestamp
}

func (pd *PathDefault) setTimestamp(t time.Time) {
	pd.timestamp = t
}

func (pd *PathDefault) MarshalJSON() ([]byte, error) {
	return json.Marshal(struct {
		Network string
		Nexthop string
		Attrs   []bgp.PathAttributeInterface
		Age     float64
	}{
		Network: pd.getPrefix(),
		Nexthop: pd.nexthop.String(),
		Attrs:   pd.getPathAttrs(),
		Age:     time.Now().Sub(pd.timestamp).Seconds(),
	})
}

// create new PathAttributes
func (pd *PathDefault) clone(isWithdraw bool) Path {
	nlri := pd.nlri
	if isWithdraw {
		if pd.IsWithdraw() {
			nlri = pd.nlri
		} else {
			nlri = &bgp.WithdrawnRoute{pd.nlri.(*bgp.NLRInfo).IPAddrPrefix}
		}
	}
	return CreatePath(pd.source, nlri, pd.pathAttrs, isWithdraw, pd.timestamp)
}

func (pd *PathDefault) GetRouteFamily() bgp.RouteFamily {
	return pd.routeFamily
}

func (pd *PathDefault) setSource(source *PeerInfo) {
	pd.source = source
}
func (pd *PathDefault) getSource() *PeerInfo {
	return pd.source
}

func (pd *PathDefault) setNexthop(nexthop net.IP) {
	pd.nexthop = nexthop
}

func (pd *PathDefault) GetNexthop() net.IP {
	return pd.nexthop
}

func (pd *PathDefault) setWithdraw(withdraw bool) {
	pd.withdraw = withdraw
}

func (pd *PathDefault) IsWithdraw() bool {
	return pd.withdraw
}

func (pd *PathDefault) getNlri() bgp.AddrPrefixInterface {
	return pd.nlri
}

func (pd *PathDefault) setMedSetByTargetNeighbor(medSetByTargetNeighbor bool) {
	pd.medSetByTargetNeighbor = medSetByTargetNeighbor
}

func (pd *PathDefault) getMedSetByTargetNeighbor() bool {
	return pd.medSetByTargetNeighbor
}

func (pd *PathDefault) getPathAttrs() []bgp.PathAttributeInterface {
	return pd.pathAttrs
}

func (pd *PathDefault) getPathAttr(pattrType bgp.BGPAttrType) (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 -1, nil
}

// return Path's string representation
func (pi *PathDefault) String() string {
	str := fmt.Sprintf("IPv4Path Source: %v, ", pi.getSource())
	str = str + fmt.Sprintf(" NLRI: %s, ", pi.getPrefix())
	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())
	return str
}

func (pi *PathDefault) getPrefix() string {
	switch nlri := pi.nlri.(type) {
	case *bgp.NLRInfo:
		return nlri.IPAddrPrefix.IPAddrPrefixDefault.String()
	case *bgp.WithdrawnRoute:
		return nlri.IPAddrPrefix.IPAddrPrefixDefault.String()
	}
	log.Fatal()
	return ""
}

// create Path object based on route family
func CreatePath(source *PeerInfo, nlri bgp.AddrPrefixInterface, attrs []bgp.PathAttributeInterface, isWithdraw bool, now time.Time) Path {

	rf := bgp.RouteFamily(int(nlri.AFI())<<16 | int(nlri.SAFI()))
	log.Debugf("CreatePath afi: %d, safi: %d ", int(nlri.AFI()), nlri.SAFI())
	var path Path

	switch rf {
	case bgp.RF_IPv4_UC:
		log.Debugf("CreatePath RouteFamily : %s", bgp.RF_IPv4_UC.String())
		path = NewIPv4Path(source, nlri, isWithdraw, attrs, false, now)
	case bgp.RF_IPv6_UC:
		log.Debugf("CreatePath RouteFamily : %s", bgp.RF_IPv6_UC.String())
		path = NewIPv6Path(source, nlri, isWithdraw, attrs, false, now)
	case bgp.RF_IPv4_VPN:
		log.Debugf("CreatePath RouteFamily : %s", bgp.RF_IPv4_VPN.String())
		path = NewIPv4VPNPath(source, nlri, isWithdraw, attrs, false, now)
	}
	return path
}

/*
* 	Definition of inherited Path  interface
 */
type IPv4Path struct {
	*PathDefault
}

func NewIPv4Path(source *PeerInfo, nlri bgp.AddrPrefixInterface, isWithdraw bool, attrs []bgp.PathAttributeInterface, medSetByTargetNeighbor bool, now time.Time) *IPv4Path {
	ipv4Path := &IPv4Path{}
	ipv4Path.PathDefault = NewPathDefault(bgp.RF_IPv4_UC, source, nlri, nil, isWithdraw, attrs, medSetByTargetNeighbor, now)
	if !isWithdraw {
		_, nexthop_attr := ipv4Path.getPathAttr(bgp.BGP_ATTR_TYPE_NEXT_HOP)
		ipv4Path.nexthop = nexthop_attr.(*bgp.PathAttributeNextHop).Value
	}
	return ipv4Path
}

func (ipv4p *IPv4Path) setPathDefault(pd *PathDefault) {
	ipv4p.PathDefault = pd
}
func (ipv4p *IPv4Path) getPathDefault() *PathDefault {
	return ipv4p.PathDefault
}

type IPv6Path struct {
	*PathDefault
}

func NewIPv6Path(source *PeerInfo, nlri bgp.AddrPrefixInterface, isWithdraw bool, attrs []bgp.PathAttributeInterface, medSetByTargetNeighbor bool, now time.Time) *IPv6Path {
	ipv6Path := &IPv6Path{}
	ipv6Path.PathDefault = NewPathDefault(bgp.RF_IPv6_UC, source, nlri, nil, isWithdraw, attrs, medSetByTargetNeighbor, now)
	if !isWithdraw {
		_, mpattr := ipv6Path.getPathAttr(bgp.BGP_ATTR_TYPE_MP_REACH_NLRI)
		ipv6Path.nexthop = mpattr.(*bgp.PathAttributeMpReachNLRI).Nexthop
	}
	return ipv6Path
}

func (ipv6p *IPv6Path) clone(isWithdraw bool) Path {
	nlri := ipv6p.nlri
	return CreatePath(ipv6p.source, nlri, ipv6p.pathAttrs, isWithdraw, ipv6p.PathDefault.timestamp)
}

func (ipv6p *IPv6Path) setPathDefault(pd *PathDefault) {
	ipv6p.PathDefault = pd
}

func (ipv6p *IPv6Path) getPathDefault() *PathDefault {
	return ipv6p.PathDefault
}

func (ipv6p *IPv6Path) getPrefix() string {
	addrPrefix := ipv6p.nlri.(*bgp.IPv6AddrPrefix)
	return addrPrefix.IPAddrPrefixDefault.String()
}

// return IPv6Path's string representation
func (ipv6p *IPv6Path) String() string {
	str := fmt.Sprintf("IPv6Path Source: %v, ", ipv6p.getSource())
	str = str + fmt.Sprintf(" NLRI: %s, ", ipv6p.getPrefix())
	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())
	return str
}

func (ipv6p *IPv6Path) MarshalJSON() ([]byte, error) {
	return json.Marshal(struct {
		Network string
		Nexthop string
		Attrs   []bgp.PathAttributeInterface
		Age     float64
	}{
		Network: ipv6p.getPrefix(),
		Nexthop: ipv6p.PathDefault.nexthop.String(),
		Attrs:   ipv6p.PathDefault.getPathAttrs(),
		Age:     time.Now().Sub(ipv6p.PathDefault.timestamp).Seconds(),
	})
}

type IPv4VPNPath struct {
	*PathDefault
}

func NewIPv4VPNPath(source *PeerInfo, nlri bgp.AddrPrefixInterface, isWithdraw bool, attrs []bgp.PathAttributeInterface, medSetByTargetNeighbor bool, now time.Time) *IPv4VPNPath {
	ipv4VPNPath := &IPv4VPNPath{}
	ipv4VPNPath.PathDefault = NewPathDefault(bgp.RF_IPv4_VPN, source, nlri, nil, isWithdraw, attrs, medSetByTargetNeighbor, now)
	if !isWithdraw {
		_, mpattr := ipv4VPNPath.getPathAttr(bgp.BGP_ATTR_TYPE_MP_REACH_NLRI)
		ipv4VPNPath.nexthop = mpattr.(*bgp.PathAttributeMpReachNLRI).Nexthop
	}
	return ipv4VPNPath
}

func (ipv4vpnp *IPv4VPNPath) clone(isWithdraw bool) Path {
	nlri := ipv4vpnp.nlri
	if isWithdraw {
		if ipv4vpnp.IsWithdraw() {
			log.WithFields(log.Fields{
				"Topic": "Table",
				"Key":   ipv4vpnp.getNlri().String(),
				"Peer":  ipv4vpnp.getSource().Address.String(),
			}).Fatal("Withdraw path is not supposed to be cloned")
		}
	}
	return CreatePath(ipv4vpnp.source, nlri, ipv4vpnp.pathAttrs, isWithdraw, ipv4vpnp.PathDefault.timestamp)
}

func (ipv4vpnp *IPv4VPNPath) setPathDefault(pd *PathDefault) {
	ipv4vpnp.PathDefault = pd
}

func (ipv4vpnp *IPv4VPNPath) getPathDefault() *PathDefault {
	return ipv4vpnp.PathDefault
}

func (ipv4vpnp *IPv4VPNPath) getPrefix() string {
	addrPrefix := ipv4vpnp.nlri.(*bgp.LabelledVPNIPAddrPrefix)
	return addrPrefix.IPAddrPrefixDefault.String()
}

// return IPv4VPNPath's string representation
func (ipv4vpnp *IPv4VPNPath) String() string {
	str := fmt.Sprintf("IPv4VPNPath Source: %v, ", ipv4vpnp.getSource())
	str = str + fmt.Sprintf(" NLRI: %s, ", ipv4vpnp.getPrefix())
	str = str + fmt.Sprintf(" nexthop: %s, ", ipv4vpnp.GetNexthop().String())
	str = str + fmt.Sprintf(" withdraw: %s, ", ipv4vpnp.IsWithdraw())
	//str = str + fmt.Sprintf(" path attributes: %s, ", ipv4vpnp.getPathAttributeMap())
	return str
}

func (ipv4vpnp *IPv4VPNPath) MarshalJSON() ([]byte, error) {
	return json.Marshal(struct {
		Network string
		Nexthop string
		Attrs   []bgp.PathAttributeInterface
		Age     float64
	}{
		Network: ipv4vpnp.getPrefix(),
		Nexthop: ipv4vpnp.PathDefault.nexthop.String(),
		Attrs:   ipv4vpnp.PathDefault.getPathAttrs(),
		Age:     time.Now().Sub(ipv4vpnp.PathDefault.timestamp).Seconds(),
	})
}