table: merge NLRIs in one message in hard way

Actually comapring all the attributes to see if packing NLRIs. It
takes long but gobgpd sends minimum messages.

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

1 files changed, 84 insertions, 43 deletions

diff --git a/table/message.go b/table/message.go
index 2597749a..c5dfb4d4 100644
--- a/table/message.go
+++ b/table/message.go
@@ -16,8 +16,9 @@
 package table
 
 import (
+	"bytes"
 	"github.com/osrg/gobgp/packet"
-	"reflect"
+	"hash/fnv"
 )
 
 func UpdatePathAttrs2ByteAs(msg *bgp.BGPUpdate) error {
@@ -183,58 +184,98 @@ func createUpdateMsgFromPath(path *Path, msg *bgp.BGPMessage) *bgp.BGPMessage {
 	return nil
 }
 
-func isMergeable(p1, p2 *Path, msg *bgp.BGPMessage) bool {
-	if p1 == nil {
-		return false
-	}
-	if p1.GetRouteFamily() != bgp.RF_IPv4_UC || p2.GetRouteFamily() != bgp.RF_IPv4_UC {
-		return false
-	}
-	if p1.IsWithdraw || p2.IsWithdraw {
-		return false
-	}
-	if p1.GetSource().Address.Equal(p2.GetSource().Address) == false {
-		return false
-	}
-	if reflect.DeepEqual(p1.GetPathAttrs(), p2.GetPathAttrs()) == false {
-		return false
-	}
-
-	u := msg.Body.(*bgp.BGPUpdate)
-
-	msgLen := func(u *bgp.BGPUpdate) int {
-		attrsLen := 0
-		for _, a := range u.PathAttributes {
-			attrsLen += a.Len()
-		}
-		// Header + Update (WithdrawnRoutesLen +
-		// TotalPathAttributeLen + attributes + maxlen of
-		// NLRI). Note that we try to add one NLRI.
-		return 19 + 2 + 2 + attrsLen + (len(u.NLRI)+1)*5
-	}(u)
-
-	// 128 is arbitrary number. just avoid too tight.
-	if msgLen+128 > bgp.BGP_MAX_MESSAGE_LENGTH {
-		return false
-	}
-	return true
+type bucket struct {
+	attrs []byte
+	paths []*Path
 }
 
 func CreateUpdateMsgFromPaths(pathList []*Path) []*bgp.BGPMessage {
-	var pre *Path
 	var msgs []*bgp.BGPMessage
+
+	pathByAttrs := make(map[uint32][]*bucket)
+
 	for _, path := range pathList {
-		y := false
-		if pre != nil {
-			y = isMergeable(pre, path, msgs[len(msgs)-1])
-		}
+		y := func(p *Path) bool {
+			if p.GetRouteFamily() != bgp.RF_IPv4_UC {
+				return false
+			}
+			if p.IsWithdraw {
+				return false
+			}
+			return true
+		}(path)
+
 		if y {
-			createUpdateMsgFromPath(path, msgs[len(msgs)-1])
+			key, attrs := func(p *Path) (uint32, []byte) {
+				h := fnv.New32()
+				total := bytes.NewBuffer(make([]byte, 0))
+				for _, v := range p.GetPathAttrs() {
+					b, _ := v.Serialize()
+					total.Write(b)
+				}
+				h.Write(total.Bytes())
+				return h.Sum32(), total.Bytes()
+			}(path)
+
+			if bl, y := pathByAttrs[key]; y {
+				found := false
+				for _, b := range bl {
+					if bytes.Compare(b.attrs, attrs) == 0 {
+						b.paths = append(b.paths, path)
+						found = true
+						break
+					}
+				}
+				if found == false {
+					nb := &bucket{
+						attrs: attrs,
+						paths: []*Path{path},
+					}
+					pathByAttrs[key] = append(pathByAttrs[key], nb)
+				}
+			} else {
+				nb := &bucket{
+					attrs: attrs,
+					paths: []*Path{path},
+				}
+				pathByAttrs[key] = []*bucket{nb}
+			}
 		} else {
 			msg := createUpdateMsgFromPath(path, nil)
-			pre = path
 			msgs = append(msgs, msg)
 		}
 	}
+
+	for _, bList := range pathByAttrs {
+		for _, b := range bList {
+			var msg *bgp.BGPMessage
+			for i, path := range b.paths {
+				if i == 0 {
+					msg = createUpdateMsgFromPath(path, nil)
+					msgs = append(msgs, msg)
+				} else {
+					msgLen := func(u *bgp.BGPUpdate) int {
+						attrsLen := 0
+						for _, a := range u.PathAttributes {
+							attrsLen += a.Len()
+						}
+						// Header + Update (WithdrawnRoutesLen +
+						// TotalPathAttributeLen + attributes + maxlen of
+						// NLRI). Note that we try to add one NLRI.
+						return 19 + 2 + 2 + attrsLen + (len(u.NLRI)+1)*5
+					}(msg.Body.(*bgp.BGPUpdate))
+
+					if msgLen+32 > bgp.BGP_MAX_MESSAGE_LENGTH {
+						// don't marge
+						msg = createUpdateMsgFromPath(path, nil)
+						msgs = append(msgs, msg)
+					} else {
+						createUpdateMsgFromPath(path, msg)
+					}
+				}
+			}
+		}
+	}
+
 	return msgs
 }