Line data    Source code

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