Line data    Source code

       1             : /*
       2             :  * Copyright (c) 2013 Juniper Networks, Inc. All rights reserved.
       3             :  * Copyright Contributors to the OpenSDN project
       4             :  */
       5             : 
       6             : #ifndef SRC_BGP_BGP_UPDATE_H_
       7             : #define SRC_BGP_BGP_UPDATE_H_
       8             : 
       9             : #include <boost/intrusive/list.hpp>
      10             : #include <boost/intrusive/slist.hpp>
      11             : #include <boost/intrusive/set.hpp>
      12             : 
      13             : #include <algorithm>
      14             : #include <list>
      15             : 
      16             : #include "bgp/bgp_ribout.h"
      17             : 
      18             : class BgpRoute;
      19             : class RibUpdateMonitor;
      20             : class RouteUpdate;
      21             : class UpdateList;
      22             : 
      23             : //
      24             : // This is the base class for elements in the UpdatesByOrder list container
      25             : // in an UpdateQueue. Each element can either be an RouteUpdate (UPDATE) or
      26             : // an UpdateMarker (MARKER).
      27             : //
      28             : class UpdateEntry {
      29             : public:
      30             :     enum EntryType {
      31             :         UPDATE  = 1,
      32             :         MARKER
      33             :     };
      34             : 
      35     1253742 :     explicit UpdateEntry(EntryType type) : type_(type) { }
      36             : 
      37        1550 :     bool IsMarker() { return (type_ == MARKER); }
      38     1235337 :     bool IsUpdate() { return (type_ == UPDATE); }
      39             : 
      40             :     // Intrusive DLL
      41             :     boost::intrusive::list_member_hook<> list_node;
      42             : 
      43             : private:
      44             :     EntryType type_;
      45             :     DISALLOW_COPY_AND_ASSIGN(UpdateEntry);
      46             : };
      47             : 
      48             : //
      49             : // This class represents an update marker in the UpdatesByOrder container
      50             : // in an UpdateQueue. It contains a set of bits corresponding to the peers
      51             : // that have not seen any updates after the marker.
      52             : //
      53             : struct UpdateMarker : public UpdateEntry {
      54      275321 :     UpdateMarker() : UpdateEntry(MARKER) {
      55      275320 :     }
      56             :     RibPeerSet members;
      57             : };
      58             : 
      59             : //
      60             : // This class represents a unique collection of attributes for a particular
      61             : // prefix that needs to be sent to a subset of peers.  It is essentially a
      62             : // combination of a RouteUpdate and a RibOutAttr that keeps track of the
      63             : // subset of peers by using a RibPeerSet.
      64             : //
      65             : // Since an UpdateInfo is relevant only in the context of a RouteUpdate, it
      66             : // is on a singly linked list container in the RouteUpdate and maintains a
      67             : // back pointer to the RouteUpdate.
      68             : //
      69             : // An UpdateInfo is also part of the set container in an UpdateQueue that
      70             : // is sorted by attribute, timestamp and prefix.
      71             : //
      72             : struct UpdateInfo {
      73      712490 :     UpdateInfo() : update(NULL) { }
      74      381171 :     explicit UpdateInfo(const RibPeerSet &target)
      75      381048 :         : target(target),
      76      381171 :           update(NULL) {
      77      380949 :     }
      78        8900 :     UpdateInfo(const RibPeerSet &target, RibOutAttr &roattr)
      79        8900 :         : roattr(roattr),
      80        8900 :           target(target),
      81        8900 :           update(NULL) {
      82        8900 :     }
      83             : 
      84             :     void clear() {
      85             :         roattr.clear();
      86             :         target.clear();
      87             :     }
      88             : 
      89             :     void swap(UpdateInfo &rhs) {
      90             :         std::swap(roattr, rhs.roattr);
      91             :         std::swap(target, rhs.target);
      92             :     }
      93             : 
      94             :     // Intrusive slist node for RouteUpdate.
      95             :     boost::intrusive::slist_member_hook<> slist_node;
      96             : 
      97             :     // Node in UpdateQueue tree. Sorted by attribute, timestamp, rt prefix.
      98             :     boost::intrusive::set_member_hook<> update_node;
      99             : 
     100             :     // Update attributes.
     101             :     RibOutAttr roattr;
     102             : 
     103             :     // Update mask
     104             :     RibPeerSet target;
     105             : 
     106             :     // Backpointer to the RouteUpdate.
     107             :     RouteUpdate *update;
     108             : 
     109             : private:
     110             :     DISALLOW_COPY_AND_ASSIGN(UpdateInfo);
     111             : };
     112             : 
     113             : //
     114             : // Disposer for UpdateInfo.
     115             : //
     116             : struct UpdateInfoDisposer {
     117     1098785 :     void operator()(UpdateInfo *uinfo) { delete uinfo; }
     118             : };
     119             : 
     120             : #ifndef _LIBCPP_VERSION
     121             : namespace std {
     122             : template <>
     123             : inline void swap<UpdateInfo>(UpdateInfo &lhs, UpdateInfo &rhs) {
     124             :     swap(lhs.roattr, rhs.roattr);
     125             :     swap(lhs.target, rhs.target);
     126             : }
     127             : }
     128             : #endif
     129             : 
     130             : //
     131             : // Wrapper for intrusive slist of UpdateInfos. Destructor automatically
     132             : // deletes any elements still on the slist.
     133             : //
     134             : // TBD: create a class template.
     135             : //
     136             : class UpdateInfoSList {
     137             : public:
     138             :     typedef boost::intrusive::member_hook<
     139             :         UpdateInfo,
     140             :         boost::intrusive::slist_member_hook<>,
     141             :         &UpdateInfo::slist_node
     142             :     > Node;
     143             :     typedef boost::intrusive::slist<
     144             :         UpdateInfo,
     145             :         Node,
     146             :         boost::intrusive::linear<true>
     147             :     > List;
     148             : 
     149     2565161 :     UpdateInfoSList() { }
     150     2565994 :     ~UpdateInfoSList() { list_.clear_and_dispose(UpdateInfoDisposer()); }
     151             :     const UpdateInfo *FindUpdateInfo(const RibOutAttr &roattr) const;
     152             : 
     153    17249901 :     List *operator->() { return &list_; }
     154     2062264 :     const List *operator->() const { return &list_; }
     155      980351 :     void swap(UpdateInfoSList &uinfo_slist) { list_.swap(uinfo_slist.list_); }
     156             : 
     157             : private:
     158             :     List list_;
     159             :     DISALLOW_COPY_AND_ASSIGN(UpdateInfoSList);
     160             : };
     161             : 
     162             : //
     163             : // This class represents an UPDATE element in the FIFO of UpdateEntry that
     164             : // is maintained within an UpdateQueue.
     165             : //
     166             : // A RouteUpdate contains a back pointer to a Route (which corresponds to
     167             : // the prefix) and a list of UpdateInfo elements. Each element contains a
     168             : // unique set of attributes that need to be advertised to a subset of the
     169             : // peers.  In the typical case, the list of UpdateInfo elements contains
     170             : // only a single entry.  However, separating the prefix information from
     171             : // the attributes in this manner allows the implementation to be extended
     172             : // to support add-path or route reflection.
     173             : //
     174             : // A RouteUpdate is also derived from a DBState which means that it is
     175             : // part of the state map within a DBEntry. This allows a RouteUpdate to
     176             : // be associated with a DBEntry using the listener id of the RibOut as
     177             : // the index. In the steady state, the DBEntry maps the listener id for
     178             : // the RibOut to a RouteState which contains the history of what has
     179             : // already been advertised.  When a RouteUpdate is created this history
     180             : // gets transferred from the RouteState to the RouteUpdate. This allows
     181             : // the DbEntry to map a listener id to either a RouteState or RouteUpdate
     182             : // instead of maintaining references to both.
     183             : //
     184             : class RouteUpdate : public DBState, public UpdateEntry {
     185             : public:
     186             :     enum Flag {
     187             :         F_LIST = 0,     // Entry is part of a list.
     188             :     };
     189             : 
     190             :     RouteUpdate(BgpRoute *route, int queue_id);
     191             :     ~RouteUpdate();
     192             : 
     193             :     void SetUpdateInfo(UpdateInfoSList &uinfo_slist);
     194             :     void BuildNegativeUpdateInfo(UpdateInfoSList &uinfo_slist) const;
     195             :     void ClearUpdateInfo();
     196             :     bool CompareUpdateInfo(const UpdateInfoSList &uinfo_slist) const;
     197             :     UpdateInfo *FindUpdateInfo(const RibOutAttr &roattr);
     198             :     const UpdateInfo *FindUpdateInfo(const RibOutAttr &roattr) const;
     199             :     void MergeUpdateInfo(UpdateInfoSList &uinfo_slist);
     200             :     bool RemoveUpdateInfo(UpdateInfo *uinfo);
     201             :     void ResetUpdateInfo(const RibPeerSet &peerset);
     202             :     void TrimRedundantUpdateInfo(UpdateInfoSList &uinfo_slist) const;
     203             : 
     204             :     void SetHistory(AdvertiseSList &history);
     205             :     void ClearHistory();
     206     1085453 :     void SwapHistory(AdvertiseSList &history) { history_.swap(history); }
     207             :     void MoveHistory(RouteState *rstate);
     208             :     void UpdateHistory(RibOut *ribout, const RibOutAttr *roattr,
     209             :                        const RibPeerSet &bits);
     210             :     const AdvertiseInfo *FindHistory(const RibOutAttr &roattr) const;
     211             : 
     212      123433 :     AdvertiseSList &History() { return history_; }
     213      157840 :     const AdvertiseSList &History() const { return history_; }
     214             : 
     215     3958188 :     UpdateInfoSList &Updates() { return updates_; }
     216      144409 :     const UpdateInfoSList &Updates() const { return updates_; }
     217             : 
     218             : 
     219             :     // Return true if there is an history entry with a non-null attribute.
     220             :     bool IsAdvertised() const;
     221     1842311 :     bool OnUpdateList () { return FlagIsSet(RouteUpdate::F_LIST); }
     222             : 
     223             :     UpdateList *MakeUpdateList();
     224             :     UpdateList *GetUpdateList(RibOut *ribout);
     225         410 :     void set_update_list() { FlagSet(RouteUpdate::F_LIST); }
     226         350 :     void clear_update_list() { FlagReset(RouteUpdate::F_LIST); }
     227             : 
     228     1842293 :     BgpRoute *route() { return route_; }
     229             : 
     230     4121446 :     int queue_id() const { return queue_id_; }
     231        1565 :     void set_queue_id(int queue_id) { queue_id_ = queue_id; }
     232             : 
     233     7482053 :     uint64_t tstamp() const { return tstamp_; }
     234      979884 :     void set_tstamp(uint64_t tstamp) { tstamp_ = tstamp; }
     235             : 
     236      623517 :     bool empty() const { return updates_->empty(); }
     237             : 
     238             : private:
     239             :     friend class RibUpdateMonitor;
     240             : 
     241     1842570 :     bool FlagIsSet(Flag flag) const { return flags_ & (1 << flag); }
     242         410 :     void FlagSet(Flag flag) { flags_ |= (1 << flag); }
     243         350 :     void FlagReset(Flag flag) { flags_ &= ~(1 << flag); }
     244             : 
     245             :     BgpRoute *route_;
     246             :     int8_t queue_id_;
     247             :     int8_t flags_;
     248             :     AdvertiseSList history_;  // Update history
     249             :     UpdateInfoSList updates_;       // The state we want to advertise
     250             :     uint64_t tstamp_;
     251             :     DISALLOW_COPY_AND_ASSIGN(RouteUpdate);
     252             : };
     253             : 
     254             : //
     255             : // If multiple RouteUpdates are active across different queues they are
     256             : // stored as an UpdateList.  An UpdateList is created when there's more
     257             : // than 1 RouteUpdate and is deleted when the number goes back to 1. An
     258             : // UpdateList keeps a list of pointers to RouteUpdates.
     259             : //
     260             : // The main motivation for creating an UpdateList is to avoid impacting
     261             : // the order in which updates from the QUPDATE queue are sent out when
     262             : // new peer(s) join or existing peer(s) request a refresh.  Without the
     263             : // notion of an UpdateList, we would have to dequeue a RouteUpdate and
     264             : // enqueue it again at the end when handling a join/refresh.
     265             : //
     266             : // The scheduled UpdateInfos are maintained in individual RouteUpdates in
     267             : // each queue, while the history is maintained in the UpdateList.
     268             : //
     269             : class UpdateList : public DBState {
     270             : public:
     271             :     typedef std::list<RouteUpdate *> List;
     272             : 
     273         220 :     UpdateList() { }
     274             : 
     275         400 :     AdvertiseSList &History() { return history_; }
     276         805 :     const AdvertiseSList &History() const { return history_; }
     277             : 
     278             :     void SetHistory(AdvertiseSList &history);
     279         210 :     void SwapHistory(AdvertiseSList &history) { history_.swap(history); }
     280             :     void MoveHistory(RouteState *rstate);
     281             :     void MoveHistory(RouteUpdate *rt_update);
     282             :     const AdvertiseInfo *FindHistory(const RibOutAttr &roattr) const;
     283             : 
     284         240 :     List *GetList() { return &list_; }
     285         140 :     const List *GetList() const { return &list_; }
     286             : 
     287             :     void AddUpdate(RouteUpdate *rt_update);
     288             :     void RemoveUpdate(RouteUpdate *rt_update);
     289             :     RouteUpdate *FindUpdate(int queue_id);
     290             :     RouteUpdate *MakeRouteUpdate();
     291             : 
     292             : private:
     293             :     friend class RibUpdateMonitor;
     294             : 
     295             :     AdvertiseSList history_;  // Update history
     296             :     List list_;
     297             :     DISALLOW_COPY_AND_ASSIGN(UpdateList);
     298             : };
     299             : 
     300             : #endif  // SRC_BGP_BGP_UPDATE_H_