packet/mrt: BGP Additional Path Extensions (RFC8050)

This patch enables to decode/encode MRT format with BGP Additional Path
Extensions which described in RFC8050.

Signed-off-by: IWASE Yusuke <iwase.yusuke0@gmail.com>

3 files changed, 188 insertions, 30 deletions

diff --git a/packet/mrt/mrt.go b/packet/mrt/mrt.go
index 8947648a..38be0e95 100644
--- a/packet/mrt/mrt.go
+++ b/packet/mrt/mrt.go
@@ -61,12 +61,17 @@ type MRTSubTyper interface {
 type MRTSubTypeTableDumpv2 uint16
 
 const (
-	PEER_INDEX_TABLE   MRTSubTypeTableDumpv2 = 1
-	RIB_IPV4_UNICAST   MRTSubTypeTableDumpv2 = 2
-	RIB_IPV4_MULTICAST MRTSubTypeTableDumpv2 = 3
-	RIB_IPV6_UNICAST   MRTSubTypeTableDumpv2 = 4
-	RIB_IPV6_MULTICAST MRTSubTypeTableDumpv2 = 5
-	RIB_GENERIC        MRTSubTypeTableDumpv2 = 6
+	PEER_INDEX_TABLE           MRTSubTypeTableDumpv2 = 1
+	RIB_IPV4_UNICAST           MRTSubTypeTableDumpv2 = 2
+	RIB_IPV4_MULTICAST         MRTSubTypeTableDumpv2 = 3
+	RIB_IPV6_UNICAST           MRTSubTypeTableDumpv2 = 4
+	RIB_IPV6_MULTICAST         MRTSubTypeTableDumpv2 = 5
+	RIB_GENERIC                MRTSubTypeTableDumpv2 = 6
+	RIB_IPV4_UNICAST_ADDPATH   MRTSubTypeTableDumpv2 = 8  // RFC8050
+	RIB_IPV4_MULTICAST_ADDPATH MRTSubTypeTableDumpv2 = 9  // RFC8050
+	RIB_IPV6_UNICAST_ADDPATH   MRTSubTypeTableDumpv2 = 10 // RFC8050
+	RIB_IPV6_MULTICAST_ADDPATH MRTSubTypeTableDumpv2 = 11 // RFC8050
+	RIB_GENERIC_ADDPATH        MRTSubTypeTableDumpv2 = 12 // RFC8050
 )
 
 func (t MRTSubTypeTableDumpv2) ToUint16() uint16 {
@@ -76,12 +81,16 @@ func (t MRTSubTypeTableDumpv2) ToUint16() uint16 {
 type MRTSubTypeBGP4MP uint16
 
 const (
-	STATE_CHANGE      MRTSubTypeBGP4MP = 0
-	MESSAGE           MRTSubTypeBGP4MP = 1
-	MESSAGE_AS4       MRTSubTypeBGP4MP = 4
-	STATE_CHANGE_AS4  MRTSubTypeBGP4MP = 5
-	MESSAGE_LOCAL     MRTSubTypeBGP4MP = 6
-	MESSAGE_AS4_LOCAL MRTSubTypeBGP4MP = 7
+	STATE_CHANGE              MRTSubTypeBGP4MP = 0
+	MESSAGE                   MRTSubTypeBGP4MP = 1
+	MESSAGE_AS4               MRTSubTypeBGP4MP = 4
+	STATE_CHANGE_AS4          MRTSubTypeBGP4MP = 5
+	MESSAGE_LOCAL             MRTSubTypeBGP4MP = 6
+	MESSAGE_AS4_LOCAL         MRTSubTypeBGP4MP = 7
+	MESSAGE_ADDPATH           MRTSubTypeBGP4MP = 8  // RFC8050
+	MESSAGE_AS4_ADDPATH       MRTSubTypeBGP4MP = 9  // RFC8050
+	MESSAGE_LOCAL_ADDPATH     MRTSubTypeBGP4MP = 10 // RFC8050
+	MESSAGE_AS4_LOCAL_ADDPATH MRTSubTypeBGP4MP = 11 // RFC8050
 )
 
 func (t MRTSubTypeBGP4MP) ToUint16() uint16 {
@@ -344,7 +353,9 @@ func (t *PeerIndexTable) String() string {
 type RibEntry struct {
 	PeerIndex      uint16
 	OriginatedTime uint32
+	PathIdentifier uint32
 	PathAttributes []bgp.PathAttributeInterface
+	isAddPath      bool
 }
 
 func (e *RibEntry) DecodeFromBytes(data []byte) ([]byte, error) {
@@ -354,8 +365,14 @@ func (e *RibEntry) DecodeFromBytes(data []byte) ([]byte, error) {
 	}
 	e.PeerIndex = binary.BigEndian.Uint16(data[:2])
 	e.OriginatedTime = binary.BigEndian.Uint32(data[2:6])
-	totalLen := binary.BigEndian.Uint16(data[6:8])
-	data = data[8:]
+	if e.isAddPath {
+		e.PathIdentifier = binary.BigEndian.Uint32(data[6:10])
+		data = data[10:]
+	} else {
+		data = data[6:]
+	}
+	totalLen := binary.BigEndian.Uint16(data[:2])
+	data = data[2:]
 	for attrLen := totalLen; attrLen > 0; {
 		p, err := bgp.GetPathAttribute(data)
 		if err != nil {
@@ -376,11 +393,8 @@ func (e *RibEntry) DecodeFromBytes(data []byte) ([]byte, error) {
 }
 
 func (e *RibEntry) Serialize() ([]byte, error) {
-	buf := make([]byte, 8)
-	binary.BigEndian.PutUint16(buf, e.PeerIndex)
-	binary.BigEndian.PutUint32(buf[2:], e.OriginatedTime)
+	pbuf := make([]byte, 0)
 	totalLen := 0
-	binary.BigEndian.PutUint16(buf[6:], uint16(totalLen))
 	for _, pattr := range e.PathAttributes {
 		// TODO special modification is needed for MP_REACH_NLRI
 		// but also Quagga doesn't implement this.
@@ -392,27 +406,47 @@ func (e *RibEntry) Serialize() ([]byte, error) {
 		// in the RIB Entry Header or RIB_GENERIC Entry Header,
 		// only the Next Hop Address Length and Next Hop Address fields are included.
 
-		bbuf, err := pattr.Serialize()
+		pb, err := pattr.Serialize()
 		if err != nil {
 			return nil, err
 		}
-		buf = append(buf, bbuf...)
-		totalLen += len(bbuf)
+		pbuf = append(pbuf, pb...)
+		totalLen += len(pb)
+	}
+	var buf []byte
+	if e.isAddPath {
+		buf = make([]byte, 12)
+		binary.BigEndian.PutUint16(buf, e.PeerIndex)
+		binary.BigEndian.PutUint32(buf[2:], e.OriginatedTime)
+		binary.BigEndian.PutUint32(buf[6:], e.PathIdentifier)
+		binary.BigEndian.PutUint16(buf[10:], uint16(totalLen))
+	} else {
+		buf = make([]byte, 8)
+		binary.BigEndian.PutUint16(buf, e.PeerIndex)
+		binary.BigEndian.PutUint32(buf[2:], e.OriginatedTime)
+		binary.BigEndian.PutUint16(buf[6:], uint16(totalLen))
 	}
-	binary.BigEndian.PutUint16(buf[6:], uint16(totalLen))
+	buf = append(buf, pbuf...)
 	return buf, nil
 }
 
-func NewRibEntry(index uint16, time uint32, pathattrs []bgp.PathAttributeInterface) *RibEntry {
+func NewRibEntry(index uint16, time uint32, pathid uint32, pathattrs []bgp.PathAttributeInterface) *RibEntry {
 	return &RibEntry{
 		PeerIndex:      index,
 		OriginatedTime: time,
+		PathIdentifier: pathid,
 		PathAttributes: pathattrs,
+		isAddPath:      pathid != 0,
 	}
 }
 
 func (e *RibEntry) String() string {
-	return fmt.Sprintf("RIB_ENTRY: PeerIndex [%d] OriginatedTime [%d] PathAttrs [%v]", e.PeerIndex, e.OriginatedTime, e.PathAttributes)
+	if e.isAddPath {
+		return fmt.Sprintf("RIB_ENTRY: PeerIndex [%d] OriginatedTime [%d] PathIdentifier[%d] PathAttrs [%v]", e.PeerIndex, e.OriginatedTime, e.PathIdentifier, e.PathAttributes)
+	} else {
+		return fmt.Sprintf("RIB_ENTRY: PeerIndex [%d] OriginatedTime [%d] PathAttrs [%v]", e.PeerIndex, e.OriginatedTime, e.PathAttributes)
+	}
+
 }
 
 type Rib struct {
@@ -420,6 +454,7 @@ type Rib struct {
 	Prefix         bgp.AddrPrefixInterface
 	Entries        []*RibEntry
 	RouteFamily    bgp.RouteFamily
+	isAddPath      bool
 }
 
 func (u *Rib) DecodeFromBytes(data []byte) error {
@@ -448,7 +483,9 @@ func (u *Rib) DecodeFromBytes(data []byte) error {
 	data = data[2:]
 	u.Entries = make([]*RibEntry, 0, entryNum)
 	for i := 0; i < int(entryNum); i++ {
-		e := &RibEntry{}
+		e := &RibEntry{
+			isAddPath: u.isAddPath,
+		}
 		data, err = e.DecodeFromBytes(data)
 		if err != nil {
 			return err
@@ -497,6 +534,7 @@ func NewRib(seq uint32, prefix bgp.AddrPrefixInterface, entries []*RibEntry) *Ri
 		Prefix:         prefix,
 		Entries:        entries,
 		RouteFamily:    rf,
+		isAddPath:      entries[0].isAddPath,
 	}
 }
 
@@ -645,6 +683,7 @@ type BGP4MPMessage struct {
 	BGPMessage        *bgp.BGPMessage
 	BGPMessagePayload []byte
 	isLocal           bool
+	isAddPath         bool
 }
 
 func (m *BGP4MPMessage) DecodeFromBytes(data []byte) error {
@@ -697,6 +736,25 @@ func NewBGP4MPMessageLocal(peeras, localas uint32, intfindex uint16, peerip, loc
 	}
 }
 
+func NewBGP4MPMessageAddPath(peeras, localas uint32, intfindex uint16, peerip, localip string, isAS4 bool, msg *bgp.BGPMessage) *BGP4MPMessage {
+	header, _ := newBGP4MPHeader(peeras, localas, intfindex, peerip, localip, isAS4)
+	return &BGP4MPMessage{
+		BGP4MPHeader: header,
+		BGPMessage:   msg,
+		isAddPath:    true,
+	}
+}
+
+func NewBGP4MPMessageLocalAddPath(peeras, localas uint32, intfindex uint16, peerip, localip string, isAS4 bool, msg *bgp.BGPMessage) *BGP4MPMessage {
+	header, _ := newBGP4MPHeader(peeras, localas, intfindex, peerip, localip, isAS4)
+	return &BGP4MPMessage{
+		BGP4MPHeader: header,
+		BGPMessage:   msg,
+		isLocal:      true,
+		isAddPath:    true,
+	}
+}
+
 func (m *BGP4MPMessage) String() string {
 	title := "BGP4MP_MSG"
 	if m.isAS4 {
@@ -705,6 +763,9 @@ func (m *BGP4MPMessage) String() string {
 	if m.isLocal {
 		title += "_LOCAL"
 	}
+	if m.isAddPath {
+		title += "_ADDPATH"
+	}
 	return fmt.Sprintf("%s: PeerAS [%d] LocalAS [%d] InterfaceIndex [%d] PeerIP [%s] LocalIP [%s] BGPMessage [%v]", title, m.PeerAS, m.LocalAS, m.InterfaceIndex, m.PeerIpAddress, m.LocalIpAddress, m.BGPMessage)
 }
 
@@ -738,6 +799,7 @@ func ParseMRTBody(h *MRTHeader, data []byte) (*MRTMessage, error) {
 	case TABLE_DUMPv2:
 		subType := MRTSubTypeTableDumpv2(h.SubType)
 		rf := bgp.RouteFamily(0)
+		isAddPath := false
 		switch subType {
 		case PEER_INDEX_TABLE:
 			msg.Body = &PeerIndexTable{}
@@ -750,6 +812,20 @@ func ParseMRTBody(h *MRTHeader, data []byte) (*MRTMessage, error) {
 		case RIB_IPV6_MULTICAST:
 			rf = bgp.RF_IPv6_MC
 		case RIB_GENERIC:
+		case RIB_IPV4_UNICAST_ADDPATH:
+			rf = bgp.RF_IPv4_UC
+			isAddPath = true
+		case RIB_IPV4_MULTICAST_ADDPATH:
+			rf = bgp.RF_IPv4_MC
+			isAddPath = true
+		case RIB_IPV6_UNICAST_ADDPATH:
+			rf = bgp.RF_IPv6_UC
+			isAddPath = true
+		case RIB_IPV6_MULTICAST_ADDPATH:
+			rf = bgp.RF_IPv6_MC
+			isAddPath = true
+		case RIB_GENERIC_ADDPATH:
+			isAddPath = true
 		default:
 			return nil, fmt.Errorf("unsupported table dumpv2 subtype: %v\n", subType)
 		}
@@ -757,6 +833,7 @@ func ParseMRTBody(h *MRTHeader, data []byte) (*MRTMessage, error) {
 		if subType != PEER_INDEX_TABLE {
 			msg.Body = &Rib{
 				RouteFamily: rf,
+				isAddPath:   isAddPath,
 			}
 		}
 	case BGP4MP:
@@ -785,6 +862,23 @@ func ParseMRTBody(h *MRTHeader, data []byte) (*MRTMessage, error) {
 				BGP4MPHeader: &BGP4MPHeader{isAS4: isAS4},
 				isLocal:      true,
 			}
+		case MESSAGE_ADDPATH:
+			isAS4 = false
+			fallthrough
+		case MESSAGE_AS4_ADDPATH:
+			msg.Body = &BGP4MPMessage{
+				BGP4MPHeader: &BGP4MPHeader{isAS4: isAS4},
+				isAddPath:    true,
+			}
+		case MESSAGE_LOCAL_ADDPATH:
+			isAS4 = false
+			fallthrough
+		case MESSAGE_AS4_LOCAL_ADDPATH:
+			msg.Body = &BGP4MPMessage{
+				BGP4MPHeader: &BGP4MPHeader{isAS4: isAS4},
+				isLocal:      true,
+				isAddPath:    true,
+			}
 		default:
 			return nil, fmt.Errorf("unsupported bgp4mp subtype: %v\n", subType)
 		}
diff --git a/packet/mrt/mrt_test.go b/packet/mrt/mrt_test.go
index 634d69ae..1b5978b0 100644
--- a/packet/mrt/mrt_test.go
+++ b/packet/mrt/mrt_test.go
@@ -114,7 +114,7 @@ func TestMrtRibEntry(t *testing.T) {
 		bgp.NewPathAttributeLocalPref(1 << 22),
 	}
 
-	e1 := NewRibEntry(1, uint32(time.Now().Unix()), p)
+	e1 := NewRibEntry(1, uint32(time.Now().Unix()), 0, p)
 	b1, err := e1.Serialize()
 	if err != nil {
 		t.Fatal(err)
@@ -129,6 +129,35 @@ func TestMrtRibEntry(t *testing.T) {
 	assert.Equal(t, reflect.DeepEqual(e1, e2), true)
 }
 
+func TestMrtRibEntryWithAddPath(t *testing.T) {
+	aspath1 := []bgp.AsPathParamInterface{
+		bgp.NewAsPathParam(2, []uint16{1000}),
+		bgp.NewAsPathParam(1, []uint16{1001, 1002}),
+		bgp.NewAsPathParam(2, []uint16{1003, 1004}),
+	}
+
+	p := []bgp.PathAttributeInterface{
+		bgp.NewPathAttributeOrigin(3),
+		bgp.NewPathAttributeAsPath(aspath1),
+		bgp.NewPathAttributeNextHop("129.1.1.2"),
+		bgp.NewPathAttributeMultiExitDisc(1 << 20),
+		bgp.NewPathAttributeLocalPref(1 << 22),
+	}
+	e1 := NewRibEntry(1, uint32(time.Now().Unix()), 200, p)
+	b1, err := e1.Serialize()
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	e2 := &RibEntry{isAddPath: true}
+	rest, err := e2.DecodeFromBytes(b1)
+	if err != nil {
+		t.Fatal(err)
+	}
+	assert.Equal(t, len(rest), 0)
+	assert.Equal(t, reflect.DeepEqual(e1, e2), true)
+}
+
 func TestMrtRib(t *testing.T) {
 	aspath1 := []bgp.AsPathParamInterface{
 		bgp.NewAsPathParam(2, []uint16{1000}),
@@ -144,9 +173,43 @@ func TestMrtRib(t *testing.T) {
 		bgp.NewPathAttributeLocalPref(1 << 22),
 	}
 
-	e1 := NewRibEntry(1, uint32(time.Now().Unix()), p)
-	e2 := NewRibEntry(2, uint32(time.Now().Unix()), p)
-	e3 := NewRibEntry(3, uint32(time.Now().Unix()), p)
+	e1 := NewRibEntry(1, uint32(time.Now().Unix()), 0, p)
+	e2 := NewRibEntry(2, uint32(time.Now().Unix()), 0, p)
+	e3 := NewRibEntry(3, uint32(time.Now().Unix()), 0, p)
+
+	r1 := NewRib(1, bgp.NewIPAddrPrefix(24, "192.168.0.0"), []*RibEntry{e1, e2, e3})
+	b1, err := r1.Serialize()
+	if err != nil {
+		t.Fatal(err)
+	}
+	r2 := &Rib{
+		RouteFamily: bgp.RF_IPv4_UC,
+	}
+	err = r2.DecodeFromBytes(b1)
+	if err != nil {
+		t.Fatal(err)
+	}
+	assert.Equal(t, reflect.DeepEqual(r1, r2), true)
+}
+
+func TestMrtRibWithAddPath(t *testing.T) {
+	aspath1 := []bgp.AsPathParamInterface{
+		bgp.NewAsPathParam(2, []uint16{1000}),
+		bgp.NewAsPathParam(1, []uint16{1001, 1002}),
+		bgp.NewAsPathParam(2, []uint16{1003, 1004}),
+	}
+
+	p := []bgp.PathAttributeInterface{
+		bgp.NewPathAttributeOrigin(3),
+		bgp.NewPathAttributeAsPath(aspath1),
+		bgp.NewPathAttributeNextHop("129.1.1.2"),
+		bgp.NewPathAttributeMultiExitDisc(1 << 20),
+		bgp.NewPathAttributeLocalPref(1 << 22),
+	}
+
+	e1 := NewRibEntry(1, uint32(time.Now().Unix()), 100, p)
+	e2 := NewRibEntry(2, uint32(time.Now().Unix()), 200, p)
+	e3 := NewRibEntry(3, uint32(time.Now().Unix()), 300, p)
 
 	r1 := NewRib(1, bgp.NewIPAddrPrefix(24, "192.168.0.0"), []*RibEntry{e1, e2, e3})
 	b1, err := r1.Serialize()
@@ -155,6 +218,7 @@ func TestMrtRib(t *testing.T) {
 	}
 	r2 := &Rib{
 		RouteFamily: bgp.RF_IPv4_UC,
+		isAddPath:   true,
 	}
 	err = r2.DecodeFromBytes(b1)
 	if err != nil {
diff --git a/server/mrt.go b/server/mrt.go
index 884f21ea..6c66745d 100644
--- a/server/mrt.go
+++ b/server/mrt.go
@@ -147,7 +147,7 @@ func (m *mrtWriter) loop() error {
 						if path.IsLocal() {
 							continue
 						}
-						entries = append(entries, mrt.NewRibEntry(idx(path), uint32(path.GetTimestamp().Unix()), path.GetPathAttrs()))
+						entries = append(entries, mrt.NewRibEntry(idx(path), uint32(path.GetTimestamp().Unix()), 0, path.GetPathAttrs()))
 					}
 					if len(entries) > 0 {
 						bm, _ := mrt.NewMRTMessage(t, mrt.TABLE_DUMPv2, subtype(pathList[0]), mrt.NewRib(seq, pathList[0].GetNlri(), entries))