OpenSDN source code
bgp_update_queue.h
Go to the documentation of this file.
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 //
29  bool operator()(const UpdateInfo &lhs, const UpdateInfo &rhs) const {
30  if (lhs.roattr.is_xmpp()) {
31  if (lhs.roattr.IsReachable() < rhs.roattr.IsReachable()) {
32  return true;
33  }
34  if (lhs.roattr.IsReachable() > rhs.roattr.IsReachable()) {
35  return false;
36  }
37  } else {
38  if (lhs.roattr.attr() < rhs.roattr.attr()) {
39  return true;
40  }
41  if (lhs.roattr.attr() > rhs.roattr.attr()) {
42  return false;
43  }
44  }
45  if (lhs.update->tstamp() < rhs.update->tstamp()) {
46  return true;
47  }
48  if (lhs.update->tstamp() > rhs.update->tstamp()) {
49  return false;
50  }
51  if (lhs.update < rhs.update) {
52  return true;
53  }
54  if (lhs.update > rhs.update) {
55  return false;
56  }
57  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<>,
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<>,
113 
114  typedef boost::intrusive::set<UpdateInfo, UpdateSetNode,
115  boost::intrusive::compare<UpdateByAttrCmp>
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 
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 
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 
156  uint64_t tstamp_;
162 
164 };
165 
166 #endif // SRC_BGP_BGP_UPDATE_QUEUE_H_
const BgpAttr * attr() const
Definition: bgp_ribout.h:99
bool IsReachable() const
Definition: bgp_ribout.h:96
bool is_xmpp() const
Definition: bgp_ribout.h:125
uint64_t tstamp() const
Definition: bgp_update.h:233
boost::intrusive::list_member_hook list_node
Definition: bgp_update.h:41
bool Enqueue(RouteUpdate *rt_update)
UpdateEntry * NextEntry(UpdateEntry *upentry)
boost::intrusive::set< UpdateInfo, UpdateSetNode, boost::intrusive::compare< UpdateByAttrCmp > > UpdatesByAttr
boost::intrusive::member_hook< UpdateEntry, boost::intrusive::list_member_hook<>, &UpdateEntry::list_node > UpdateEntryNode
void MarkerSplit(UpdateMarker *marker, const RibPeerSet &msplit)
uint64_t tstamp_
DISALLOW_COPY_AND_ASSIGN(UpdateQueue)
UpdateInfo * AttrNext(UpdateInfo *current_uinfo)
bool CheckInvariants() const
MarkerList markers_
UpdateMarker * tail_marker()
friend class BgpExportTest
friend class RibOutUpdatesTest
void AddMarker(UpdateMarker *marker, RouteUpdate *rt_update)
bool Join(int bit)
UpdateQueue(const RibOut *ribout, int queue_id)
void MarkerMerge(UpdateMarker *dst_marker, UpdateMarker *src_marker, const RibPeerSet &bitset)
std::vector< UpdateMarker * > MarkerList
boost::intrusive::list< UpdateEntry, UpdateEntryNode > UpdatesByOrder
boost::intrusive::member_hook< UpdateInfo, boost::intrusive::set_member_hook<>, &UpdateInfo::update_node > UpdateSetNode
void Dequeue(RouteUpdate *rt_update)
void MoveMarker(UpdateMarker *marker, RouteUpdate *rt_update)
RouteUpdate * NextUpdate(UpdateEntry *upentry)
bool empty() const
UpdatesByAttr attr_set_
UpdateMarker * GetMarker(int bit)
size_t marker_count() const
size_t marker_count_
void Leave(int bit)
size_t size() const
UpdatesByOrder queue_
void AttrDequeue(UpdateInfo *current_uinfo)
UpdateMarker tail_marker_
bool operator()(const UpdateInfo &lhs, const UpdateInfo &rhs) const
RibOutAttr roattr
Definition: bgp_update.h:101
boost::intrusive::set_member_hook update_node
Definition: bgp_update.h:98
RouteUpdate * update
Definition: bgp_update.h:107