bgpd: Adds support to mark up the BGP rib table entry with multipath

information based on the multipath list (mp_list) generated during
the best path calculation. Display "multipath" for paths that are
multipath and also on bestpath if the route is multipath. Flag a
best path with the BGP_INFO_MULTIPATH_CHG if the multipath
set has changed since the last update. This can be used to trigger
updates to zebra and peers.

The multipath markup is a lazily allocated bgp_info_mpath structure
that is added to the best path and any multipaths. The mpath structures
are linked together with the best path element at the head and the
other elements ordered by nexthop and then by peer address. This
markup scheme is updated by calling bgp_info_mpath_update() and passing
in a new mp_list the the current multipath set. There are additional
API's for walking the multipath set, querying the count of multipaths,
and for cleaning up the multipath markup information when freeing path
information.

* bgpd/bgp_mpath.c
  * bgp_info_mpath_new(): Allocation of new mpath element
  * bgp_info_mpath_free(): Release memory for mpath element
  * bgp_info_mpath_get(): Access mpath element of path. Allocate memory
    on-demand
  * bgp_info_mpath_enqueue(): Enqueue a path onto the multipath list
  * bgp_info_mpath_dequeue(): Remove a path from the multipath list
  * bgp_info_mpath_first(): Return first path on the multipath list
  * bgp_info_mpath_next(): Return next path on the multipath list
  * bgp_info_mpath_count(): Return the number of paths on the multipath list
  * bgp_info_mpath_count_set(): Set the number of paths on the multipath list
  * bgp_info_mpath_update(): Update multipath markup on bgp route table entry
    and flag any changes. Emit 'debug bgp event' output on any multipath
    change.
* bgpd/bgp_mpath.h
  * struct bgp_info_mpath: Information added to a bgp_info path to record
    multipath information
  * External declarations for new functions in bgp_mpath.c
* bgpd/bgp_route.c
  * bgp_info_free(): Free mpath memory when freeing path information
  * bgp_info_reap(): Dequeue path from multipath queue before deleting it
  * bgp_best_selection(): Calls bgp_info_mpath_update() with latest
    mp_list to mark-up rib table entry
  * bgp_vty_out_detail(): Add display of multipath flag for a path. Also
    display 'multipath' for bestpath if it is a multipath route
* bgpd/bgp_route.h
  * struct bgp_info: Add pointer to bgp_info_mpath information
  * Add flags to mark a path as multipath (BGP_INFO_MULTIPATH) and
    to mark bestpath if multipath information has changed
    (BGP_INFO_MULTIPATH_CHG)
* lib/memtypes.c
  * Add MTYPE_BGP_MPATH_INFO for allocating memory for bgp_info_mpath
* tests/bgp_mpath_test.c
  * Add test case for bgp_info_mpath_update() and supporting functions

1 files changed, 32 insertions, 0 deletions

diff --git a/bgpd/bgp_mpath.h b/bgpd/bgp_mpath.h
index de6461fd..1dc2687e 100644
--- a/bgpd/bgp_mpath.h
+++ b/bgpd/bgp_mpath.h
@@ -27,6 +27,24 @@
 /* BGP default maximum-paths */
 #define BGP_DEFAULT_MAXPATHS 1
 
+/* Supplemental information linked to bgp_info for keeping track of
+ * multipath selections, lazily allocated to save memory
+ */
+struct bgp_info_mpath
+{
+  /* Points to the first multipath (on bestpath) or the next multipath */
+  struct bgp_info_mpath *mp_next;
+
+  /* Points to the previous multipath or NULL on bestpath */
+  struct bgp_info_mpath *mp_prev;
+
+  /* Points to bgp_info associated with this multipath info */
+  struct bgp_info *mp_info;
+
+  /* When attached to best path, the number of selected multipaths */
+  u_int32_t mp_count;
+};
+
 /* Functions to support maximum-paths configuration */
 extern int bgp_maximum_paths_set (struct bgp *, afi_t, safi_t, int, u_int16_t);
 extern int bgp_maximum_paths_unset (struct bgp *, afi_t, safi_t, int);
@@ -37,5 +55,19 @@ extern int bgp_maximum_paths_unset (struct bgp *, afi_t, safi_t, int);
 extern void bgp_mp_list_init (struct list *);
 extern void bgp_mp_list_clear (struct list *);
 extern void bgp_mp_list_add (struct list *, struct bgp_info *);
+extern void bgp_info_mpath_update (struct bgp_node *, struct bgp_info *,
+                                   struct bgp_info *, struct list *,
+                                   struct bgp_maxpaths_cfg *);
+
+/* Unlink and free multipath information associated with a bgp_info */
+extern void bgp_info_mpath_dequeue (struct bgp_info *);
+extern void bgp_info_mpath_free (struct bgp_info_mpath **);
+
+/* Walk list of multipaths associated with a best path */
+extern struct bgp_info *bgp_info_mpath_first (struct bgp_info *);
+extern struct bgp_info *bgp_info_mpath_next (struct bgp_info *);
+
+/* Accessors for multipath information */
+extern u_int32_t bgp_info_mpath_count (struct bgp_info *);
 
 #endif /* _QUAGGA_BGP_MPATH_H */