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_QUEUE_H_
       7             : #define SRC_BGP_BGP_UPDATE_QUEUE_H_
       8             : 
       9             : #include <list>
      10             : #include <set>
      11             : #include <vector>
      12             : 
      13             : #include "bgp/bgp_update.h"
      14             : 
      15             : //
      16             : // Comparator used to order UpdateInfos in the UpdateQueue set container.
      17             : // Looks at the BgpAttr, Timestamp and the associated RouteUpdate but not
      18             : // the Label, in order to achieve optimal packing of BGP updates. Ignore
      19             : // the BgpAttr in case of XMPP since each item is self contained - there's
      20             : // no notion of common attributes for all items in an update message.
      21             : //
      22             : // Compare the UpdateInfo pointers themselves as the final tie-breaker to
      23             : // handle the case where there are 2 UpdateInfos with the same BgpAttr in
      24             : // the same RouteUpdate. This can happen if the label (or the set for ecmp
      25             : // nexthops in case of an XMPP ribout) for a route changes between the Join
      26             : // operations for 2 different sets of IPeerUpdates.
      27             : //
      28             : struct UpdateByAttrCmp {
      29     2166206 :     bool operator()(const UpdateInfo &lhs, const UpdateInfo &rhs) const {
      30     2166206 :         if (lhs.roattr.is_xmpp()) {
      31      713396 :             if (lhs.roattr.IsReachable() < rhs.roattr.IsReachable()) {
      32           0 :                 return true;
      33             :             }
      34      713368 :             if (lhs.roattr.IsReachable() > rhs.roattr.IsReachable()) {
      35       13616 :                 return false;
      36             :             }
      37             :         } else {
      38     1452798 :             if (lhs.roattr.attr() < rhs.roattr.attr()) {
      39       41710 :                 return true;
      40             :             }
      41     1410925 :             if (lhs.roattr.attr() > rhs.roattr.attr()) {
      42       56016 :                 return false;
      43             :             }
      44             :         }
      45     2054435 :         if (lhs.update->tstamp() < rhs.update->tstamp())  {
      46      367301 :             return true;
      47             :         }
      48     1687431 :         if (lhs.update->tstamp() > rhs.update->tstamp()) {
      49     1687311 :             return false;
      50             :         }
      51          40 :         if (lhs.update < rhs.update)  {
      52           0 :             return true;
      53             :         }
      54          40 :         if (lhs.update > rhs.update) {
      55           0 :             return false;
      56             :         }
      57          40 :         return (&lhs < &rhs);
      58             :     }
      59             : };
      60             : 
      61             : //
      62             : // This class implements an update queue for a RibOut.  A RibUpdateMonitor
      63             : // contains a vector of pointers to UpdateQueue. The UpdateQueue instances
      64             : // are created and the corresponding pointers added to the vector from the
      65             : // RibOutUpdates constructor.  The following relationships are relevant:
      66             : //
      67             : //     RibOut -> RibOutUpdates (1:N)
      68             : //     RibOutUpdates -> RibUpdateMonitor (1:1)
      69             : //     RibUpdateMonitor -> UpdateQueue (1:N)
      70             : //
      71             : // Each UpdateQueue has an id which indicates whether it's a BULK queue or
      72             : // an UPDATE queue.  A BULK queue is used for route refresh and also when
      73             : // a new peer comes up.
      74             : //
      75             : // An UpdateQueue contains an intrusive doubly linked list of UpdateEntry
      76             : // base elements, which could be either be UpdateMarker or RouteUpdate.
      77             : // This list is maintained in temporal order i.e. it's a FIFO.
      78             : //
      79             : // An UpdateQueue also has a intrusive set of UpdateInfo elements.  These
      80             : // are ordered by attribute, timestamp and the corresponding prefix. This
      81             : // container is used when building updates since it allows us to traverse
      82             : // prefixes grouped by attributes. The relationship between a RouteUpdate
      83             : // and UpdateInfo is described elsewhere.
      84             : //
      85             : // An UpdateQueue also maintains a mapping from a peer's bit position to
      86             : // it's UpdateMarker. Note that it's possible for multiple peers to point
      87             : // to the same marker.
      88             : //
      89             : // A special UpdateMarker called the tail marker is used as an easy way to
      90             : // keep track of whether the list is empty.  The tail marker is always the
      91             : // last marker in the list.  Another way to think about this is that all
      92             : // the RouteUpdates after the tail marker have not been seen by any peer.
      93             : // This property is maintained by making sure that when the update marker
      94             : // for a peer (or set of peers) reaches the tail marker, it's merged into
      95             : // the tail marker.
      96             : //
      97             : class UpdateQueue {
      98             : public:
      99             :     // Typedefs for the intrusive list.
     100             :     typedef boost::intrusive::member_hook<
     101             :         UpdateEntry,
     102             :         boost::intrusive::list_member_hook<>,
     103             :         &UpdateEntry::list_node
     104             :     > UpdateEntryNode;
     105             : 
     106             :     typedef boost::intrusive::list<UpdateEntry, UpdateEntryNode> UpdatesByOrder;
     107             : 
     108             :     // Typedefs for the intrusive set.
     109             :     typedef boost::intrusive::member_hook<UpdateInfo,
     110             :         boost::intrusive::set_member_hook<>,
     111             :         &UpdateInfo::update_node
     112             :     > UpdateSetNode;
     113             : 
     114             :     typedef boost::intrusive::set<UpdateInfo, UpdateSetNode,
     115             :         boost::intrusive::compare<UpdateByAttrCmp>
     116             :     > UpdatesByAttr;
     117             : 
     118             :     typedef std::vector<UpdateMarker *> MarkerList;
     119             : 
     120             :     UpdateQueue(const RibOut *ribout, int queue_id);
     121             :     ~UpdateQueue();
     122             : 
     123             :     bool Enqueue(RouteUpdate *rt_update);
     124             :     void Dequeue(RouteUpdate *rt_update);
     125             : 
     126             :     RouteUpdate *NextUpdate(UpdateEntry *upentry);
     127             :     UpdateEntry *NextEntry(UpdateEntry *upentry);
     128             : 
     129             :     void AttrDequeue(UpdateInfo *current_uinfo);
     130             :     UpdateInfo *AttrNext(UpdateInfo *current_uinfo);
     131             : 
     132             :     void AddMarker(UpdateMarker *marker, RouteUpdate *rt_update);
     133             :     void MoveMarker(UpdateMarker *marker, RouteUpdate *rt_update);
     134             :     void MarkerSplit(UpdateMarker *marker, const RibPeerSet &msplit);
     135             :     void MarkerMerge(UpdateMarker *dst_marker, UpdateMarker *src_marker,
     136             :                      const RibPeerSet &bitset);
     137             :     UpdateMarker *GetMarker(int bit);
     138             : 
     139             :     bool Join(int bit);
     140             :     void Leave(int bit);
     141             : 
     142             :     bool CheckInvariants() const;
     143             : 
     144     1217396 :     UpdateMarker *tail_marker() { return &tail_marker_; }
     145             : 
     146             :     bool empty() const;
     147             :     size_t size() const;
     148             :     size_t marker_count() const;
     149             : 
     150             : private:
     151             :     friend class BgpExportTest;
     152             :     friend class RibOutUpdatesTest;
     153             : 
     154             :     int queue_id_;
     155             :     bool encoding_is_xmpp_;
     156             :     uint64_t tstamp_;
     157             :     size_t marker_count_;
     158             :     UpdatesByOrder queue_;
     159             :     UpdatesByAttr attr_set_;
     160             :     MarkerList markers_;
     161             :     UpdateMarker tail_marker_;
     162             : 
     163             :     DISALLOW_COPY_AND_ASSIGN(UpdateQueue);
     164             : };
     165             : 
     166             : #endif  // SRC_BGP_BGP_UPDATE_QUEUE_H_