Line data    Source code

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