Line data Source code
1 : /*
2 : * Copyright (c) 2016 Juniper Networks, Inc. All rights reserved.
3 : * Copyright Contributors to the OpenSDN project
4 : */
5 :
6 : #ifndef SRC_BGP_BGP_MEMBERSHIP_H_
7 : #define SRC_BGP_BGP_MEMBERSHIP_H_
8 :
9 : #include <boost/dynamic_bitset.hpp>
10 : #include <boost/scoped_ptr.hpp>
11 : #include <tbb/spin_rw_mutex.h>
12 :
13 : #include <list>
14 : #include <map>
15 : #include <set>
16 : #include <string>
17 : #include <vector>
18 : #include <atomic>
19 :
20 : #include "base/lifetime.h"
21 : #include "base/queue_task.h"
22 : #include "db/db_table.h"
23 : #include "bgp/bgp_ribout.h"
24 :
25 : class BgpNeighborResp;
26 : class BgpServer;
27 : class BgpTable;
28 : class IPeer;
29 : class RibOut;
30 : class ShowMembershipPeerInfo;
31 : class ShowRoutingInstanceTable;
32 : class TaskTrigger;
33 :
34 : //
35 : // This class implements membership management for a BgpServer.
36 :
37 : // It provides methods for an IPeer to manage it's membership in BgpTables.
38 : // There are two kinds of memberships for a (IPeer, BgpTable) pair - RibIn
39 : // and RibOut. RibIn membership is needed for an IPeer to add BgpPaths to a
40 : // BgpTable. RibOut membership is needed to advertise routes from a BgpTable
41 : // to an IPeer.
42 : //
43 : // APIs are provided to manage these 2 types of memberships together as well
44 : // as separately. An API to walk all BgpPaths added by an IPeer to a BgpTable
45 : // is also provided. This is used by clients to delete BgpPaths when a peer
46 : // is going down, to mark BgpPaths as stale when handling graceful restart of
47 : // a peer etc. The actual logic of deleting or modifying a BgpPath has to be
48 : // in the client code.
49 : //
50 : // Many APIs require traversal of the entire BgpTable and so are asynchronous.
51 : // An IPeer gets notified on completion of API via virtual function callback.
52 : // Along similar lines, when using a walk API, an IPeer gets notified for each
53 : // BgpPath added by it via a virtual function. A client is allowed to have 1
54 : // outstanding request for a given (IPeer, BgpTable) pair.
55 : //
56 : // There are scenarios where multiple IPeers subscribe to a given BgpTable at
57 : // roughly the same time. Further, this can happen for many BgpTables at about
58 : // the same time as well. The implementation handles this quite efficiently by
59 : // accumulating multiple (IPeer, BgpTable) requests to reduce/minimize the
60 : // number of table walks. The table walk functionality is delegated to the
61 : // Walker class.
62 : //
63 : // Membership information corresponding to (IPeer, BgpTable) pairs is organized
64 : // with the above goal in mind. An IPeer is represented using a PeerState and a
65 : // BgpTable is represented using a RibState. A PeerStateMap and RibStateMap are
66 : // used for efficient lookup and insertion. A (IPeer, BgpTable) is represented
67 : // using a PeerRibState. Linkage between PeerState, RibState, and PeerRibState
68 : // is described in more detail later.
69 : //
70 : // Updates to the PeerStateMap, RibStateMap and other maps/sets maintained in
71 : // a PeerState and RibState can happen synchronously from from the API calls.
72 : // This allows for easy detection of violations in API assumptions e.g. only a
73 : // single outstanding request for a (IPeer, BgpTable) pair. Since multiple API
74 : // calls can happen in parallel, access to internal state has to be serialized
75 : // using a read-write mutex. A read-write mutex is used to allow parallel calls
76 : // to GetRegistrationInfo from multiple db::DBTable tasks. All other API calls
77 : // are relatively infrequent.
78 : //
79 : // The read-write mutex ensures consistency of BgpMembershipManager's internal
80 : // state. However, the BgpMembershipManager also needs to call external APIs
81 : // which have their own concurrency requirements. A WorkQueue of Events is
82 : // used to satisfy these requirements. The WorkQueue is processed in context
83 : // of bgp::PeerMembership task and appropriate exclusion polices are specified
84 : // at system initialization. Client callbacks for API complete notifications
85 : // are also made from the bgp:PeerMembership task.
86 : //
87 : class BgpMembershipManager {
88 : public:
89 : typedef boost::function<void(IPeer *, BgpTable *, bool)>
90 : PeerRegistrationCallback;
91 :
92 : explicit BgpMembershipManager(BgpServer *server);
93 : virtual ~BgpMembershipManager();
94 :
95 : int RegisterPeerRegistrationCallback(PeerRegistrationCallback callback);
96 : void UnregisterPeerRegistrationCallback(int id);
97 :
98 : virtual void Register(IPeer *peer, BgpTable *table,
99 : const RibExportPolicy &policy, int instance_id = -1);
100 : void RegisterRibIn(IPeer *peer, BgpTable *table);
101 : virtual void Unregister(IPeer *peer, BgpTable *table);
102 : void UnregisterRibIn(IPeer *peer, BgpTable *table);
103 : virtual void UnregisterRibOut(IPeer *peer, BgpTable *table);
104 : void WalkRibIn(IPeer *peer, BgpTable *table);
105 :
106 : bool GetRegistrationInfo(const IPeer *peer, const BgpTable *table,
107 : int *instance_id = NULL, uint64_t *subscription_gen_id = NULL) const;
108 : void SetRegistrationInfo(const IPeer *peer, const BgpTable *table,
109 : int instance_id, uint64_t subscription_gen_id);
110 :
111 : bool IsRegistered(const IPeer *peer, const BgpTable *table) const;
112 : bool IsRibInRegistered(const IPeer *peer, const BgpTable *table) const;
113 : bool IsRibOutRegistered(const IPeer *peer, const BgpTable *table) const;
114 : uint32_t GetRibOutQueueDepth(const IPeer *peer,
115 : const BgpTable *table) const;
116 :
117 : void GetRegisteredRibs(const IPeer *peer,
118 : std::list<BgpTable *> *table_list) const;
119 :
120 : void FillRoutingInstanceTableInfo(ShowRoutingInstanceTable *srit,
121 : const BgpTable *table) const;
122 : void FillPeerMembershipInfo(const IPeer *peer, BgpNeighborResp *resp) const;
123 :
124 81679 : BgpServer *server() { return server_; }
125 : bool IsQueueEmpty() const;
126 : size_t GetMembershipCount() const;
127 : uint64_t current_jobs_count() const { return current_jobs_count_; }
128 : uint64_t total_jobs_count() const { return total_jobs_count_; }
129 :
130 : protected:
131 : class PeerRibState;
132 : struct Event;
133 :
134 : virtual bool EventCallbackInternal(Event *event);
135 : virtual bool AssertRegister(PeerRibState *prs, bool do_assert = true);
136 : virtual bool AssertUnregister(PeerRibState *prs, bool do_assert = true);
137 : virtual bool AssertRegisterRibIn(PeerRibState *prs, IPeer *peer,
138 : bool do_assert = true);
139 : virtual bool AssertWalkRibIn(PeerRibState *prs, bool do_assert = true);
140 :
141 : mutable tbb::spin_rw_mutex rw_mutex_;
142 :
143 : private:
144 : class PeerState;
145 : class RibState;
146 : class Walker;
147 :
148 : friend class BgpMembershipManager::PeerState;
149 : friend class BgpMembershipManager::RibState;
150 : friend class BgpMembershipManager::PeerRibState;
151 : friend class BgpMembershipManager::Walker;
152 : friend class BgpMembershipTest;
153 : friend class BgpServerUnitTest;
154 : friend class BgpXmppUnitTest;
155 :
156 : enum Action {
157 : NONE,
158 : RIBOUT_ADD,
159 : RIBIN_DELETE,
160 : RIBIN_WALK,
161 : RIBIN_WALK_RIBOUT_DELETE,
162 : RIBIN_DELETE_RIBOUT_DELETE
163 : };
164 :
165 : enum EventType {
166 : REGISTER_RIB,
167 : REGISTER_RIB_COMPLETE,
168 : UNREGISTER_RIB,
169 : UNREGISTER_RIB_COMPLETE,
170 : WALK_RIB_COMPLETE
171 : };
172 :
173 : typedef std::vector<PeerRegistrationCallback> PeerRegistrationListenerList;
174 : typedef std::map<const IPeer *, PeerState *> PeerStateMap;
175 : typedef std::map<const BgpTable *, RibState *> RibStateMap;
176 : typedef std::set<PeerRibState *> PeerRibList;
177 :
178 : void UnregisterRibInUnlocked(PeerRibState *prs);
179 :
180 : PeerState *LocatePeerState(IPeer *peer);
181 : PeerState *FindPeerState(const IPeer *peer);
182 : const PeerState *FindPeerState(const IPeer *peer) const;
183 : void DestroyPeerState(PeerState *ps);
184 :
185 : RibState *LocateRibState(BgpTable *table);
186 : RibState *FindRibState(const BgpTable *table);
187 : const RibState *FindRibState(const BgpTable *table) const;
188 : void DestroyRibState(RibState *ps);
189 : void EnqueueRibState(RibState *rs);
190 :
191 : PeerRibState *LocatePeerRibState(IPeer *peer, BgpTable *table);
192 : PeerRibState *FindPeerRibState(const IPeer *peer, const BgpTable *table);
193 : const PeerRibState *FindPeerRibState(const IPeer *peer,
194 : const BgpTable *table) const;
195 : void DestroyPeerRibState(PeerRibState *prs);
196 :
197 : void TriggerRegisterRibCompleteEvent(IPeer *peer, BgpTable *table);
198 : void TriggerUnregisterRibCompleteEvent(IPeer *peer, BgpTable *table);
199 : void TriggerWalkRibCompleteEvent(IPeer *peer, BgpTable *table);
200 :
201 : void ProcessRegisterRibEvent(Event *event);
202 : void ProcessRegisterRibCompleteEvent(Event *event);
203 : void ProcessUnregisterRibEvent(Event *event);
204 : void ProcessUnregisterRibCompleteEvent(Event *event);
205 : void ProcessWalkRibCompleteEvent(Event *event);
206 :
207 332803 : void EnqueueEvent(Event *event) { event_queue_->Enqueue(event); }
208 : bool EventCallback(Event *event);
209 :
210 : void NotifyPeerRegistration(IPeer *peer, BgpTable *table, bool unregister);
211 :
212 : // Testing only.
213 84 : void SetQueueDisable(bool value) { event_queue_->set_disable(value); }
214 30 : Walker *walker() { return walker_.get(); }
215 :
216 : BgpServer *server_;
217 : std::atomic<uint64_t> current_jobs_count_;
218 : std::atomic<uint64_t> total_jobs_count_;
219 : RibStateMap rib_state_map_;
220 : PeerStateMap peer_state_map_;
221 : boost::scoped_ptr<Walker> walker_;
222 : boost::scoped_ptr<WorkQueue<Event *> > event_queue_;
223 :
224 : boost::dynamic_bitset<> registration_bmap_;
225 : PeerRegistrationListenerList registration_callbacks_;
226 :
227 : DISALLOW_COPY_AND_ASSIGN(BgpMembershipManager);
228 : };
229 :
230 : struct BgpMembershipManager::Event {
231 : friend class BgpMembershipManager;
232 :
233 : typedef BgpMembershipManager::EventType EventType;
234 :
235 : Event(EventType event_type, IPeer *peer, BgpTable *table);
236 : Event(EventType event_type, IPeer *peer, BgpTable *table,
237 : const RibExportPolicy &policy, int instance_id);
238 :
239 : EventType event_type;
240 : IPeer *peer;
241 : BgpTable *table;
242 : RibExportPolicy policy;
243 : int instance_id;
244 : };
245 :
246 : //
247 : // This represents an IPeer within the BgpMembershipManager, which maintains a
248 : // map of PeerStates keyed an IPeer pointer.
249 : //
250 : // The PeerRibStateMap allows efficient creation and lookup of PeerRibState.
251 : // It can be accessed synchronously from the API calls to BgpMembershipManager
252 : // or from the bgp::PeerMembership task. In the former case, the read-write
253 : // mutex in the BgpMembershipManager is sufficient to serialize access to the
254 : // PeerRibStateMap. In the latter case, task exclusion policies prevent any
255 : // parallel access.
256 : //
257 : class BgpMembershipManager::PeerState {
258 : public:
259 : typedef BgpMembershipManager::RibState RibState;
260 : typedef BgpMembershipManager::PeerRibState PeerRibState;
261 : typedef std::map<const RibState *, PeerRibState *> PeerRibStateMap;
262 :
263 : PeerState(BgpMembershipManager *manager, IPeer *peer);
264 : ~PeerState();
265 :
266 : PeerRibState *LocatePeerRibState(RibState *rs);
267 : PeerRibState *FindPeerRibState(const RibState *rs);
268 : const PeerRibState *FindPeerRibState(const RibState *rs) const;
269 : bool RemovePeerRibState(PeerRibState *prs);
270 :
271 : void GetRegisteredRibs(std::list<BgpTable *> *table_list) const;
272 937 : size_t GetMembershipCount() const { return rib_map_.size(); }
273 : void FillPeerMembershipInfo(BgpNeighborResp *resp) const;
274 :
275 604836 : IPeer *peer() { return peer_; }
276 : const IPeer *peer() const { return peer_; }
277 :
278 : private:
279 : BgpMembershipManager *manager_;
280 : IPeer *peer_;
281 : PeerRibStateMap rib_map_;
282 :
283 : DISALLOW_COPY_AND_ASSIGN(PeerState);
284 : };
285 :
286 : //
287 : // This represents a BgpTable within the BgpMembershipManager, which maintains
288 : // a map of RibStates keyed a BgpTable pointer.
289 : //
290 : // A RibState maintains two PeerRibLists.
291 : // The pending list contains all the PeerRibStates for which some action needs
292 : // to performed during the next walk of the associated BgpTable. This is used
293 : // by the Walker when it's starting a walk of the BgpTable.
294 : // The regular PeerRibList contains all the PeerRibStates for this RibState.
295 : // It is used only for introspect.
296 : //
297 : class BgpMembershipManager::RibState {
298 : public:
299 : typedef BgpMembershipManager::PeerRibState PeerRibState;
300 : typedef BgpMembershipManager::PeerRibList PeerRibList;
301 : typedef PeerRibList::iterator iterator;
302 :
303 : explicit RibState(BgpMembershipManager *manager, BgpTable *table);
304 : ~RibState();
305 1775 : void ManagedDelete() {}
306 :
307 130103 : iterator begin() { return pending_peer_rib_list_.begin(); }
308 299434 : iterator end() { return pending_peer_rib_list_.end(); }
309 :
310 : void EnqueuePeerRibState(PeerRibState *prs);
311 : void ClearPeerRibStateList();
312 :
313 : void InsertPeerRibState(PeerRibState *prs);
314 : bool RemovePeerRibState(PeerRibState *prs);
315 :
316 : void FillRoutingInstanceTableInfo(ShowRoutingInstanceTable *srit) const;
317 :
318 1095441 : BgpTable *table() const { return table_; }
319 130103 : void increment_walk_count() { walk_count_++; }
320 :
321 : private:
322 : BgpMembershipManager *manager_;
323 : BgpTable *table_;
324 : uint32_t request_count_;
325 : uint32_t walk_count_;
326 : PeerRibList peer_rib_list_;
327 : PeerRibList pending_peer_rib_list_;
328 : LifetimeRef<RibState> table_delete_ref_;
329 :
330 : DISALLOW_COPY_AND_ASSIGN(RibState);
331 : };
332 :
333 : //
334 : // This class represents the membership of an IPeer in a BgpTable. The result
335 : // of this membership is a RibOut instance. An instance of a PeerRibState is
336 : // created when an IPeer registers with a BgpTable and gets deleted when the
337 : // IPeer unregisters from the BgpTable.
338 : //
339 : // A PeerState has a map of PeerRibStates keyed by RibState pointer.
340 : // A PeerRibState is on a list of PeerRibStates in it's RibState.
341 : // If a PeerRibState has a pending action, it's also on the pending list in
342 : // the RibState.
343 : // The action is NONE in steady state.
344 : //
345 : class BgpMembershipManager::PeerRibState {
346 : public:
347 : PeerRibState(BgpMembershipManager *manager, PeerState *ps, RibState *rs);
348 : ~PeerRibState();
349 :
350 : void RegisterRibOut(const RibExportPolicy &policy);
351 : void UnregisterRibOut();
352 : void DeactivateRibOut();
353 : void UnregisterRibIn();
354 : void WalkRibIn();
355 :
356 : void FillMembershipInfo(ShowMembershipPeerInfo *smpi) const;
357 :
358 10472 : const IPeer *peer() const { return ps_->peer(); }
359 336465 : PeerState *peer_state() { return ps_; }
360 : const PeerState *peer_state() const { return ps_; }
361 158964 : RibState *rib_state() { return rs_; }
362 163358 : RibOut *ribout() const { return ribout_; }
363 163358 : int ribout_index() const { return ribout_index_; }
364 12336 : const BgpTable *table() const { return rs_->table(); }
365 :
366 1283953 : BgpMembershipManager::Action action() const { return action_; }
367 169410 : void set_action(BgpMembershipManager::Action action) { action_ = action; }
368 169411 : void clear_action() { action_ = BgpMembershipManager::NONE; }
369 602800 : bool ribin_registered() const { return ribin_registered_; }
370 168178 : void set_ribin_registered(bool value) { ribin_registered_ = value; }
371 567290 : bool ribout_registered() const { return ribout_registered_; }
372 40 : void set_ribout_registered(bool value) { ribout_registered_ = value; }
373 68351 : int instance_id() const { return instance_id_; }
374 233836 : void set_instance_id(int instance_id) { instance_id_ = instance_id; }
375 66850 : uint64_t subscription_gen_id() const { return subscription_gen_id_; }
376 152117 : void set_subscription_gen_id(uint64_t subscription_gen_id) {
377 152117 : subscription_gen_id_ = subscription_gen_id;
378 152117 : }
379 :
380 : private:
381 : BgpMembershipManager *manager_;
382 : PeerState *ps_;
383 : RibState *rs_;
384 : RibOut *ribout_;
385 : int ribout_index_;
386 : BgpMembershipManager::Action action_;
387 : bool ribin_registered_;
388 : bool ribout_registered_;
389 : int instance_id_;
390 : uint64_t subscription_gen_id_;
391 :
392 : DISALLOW_COPY_AND_ASSIGN(PeerRibState);
393 : };
394 :
395 : //
396 : // This class is responsible for efficient implementation of BgpTable walks
397 : // for the BgpMembershipManager. It accepts walk requests for any number of
398 : // RibStates and triggers table walks one at a time. It has a maximum of one
399 : // ongoing table walk at any given time.
400 : //
401 : // The RibStateList contains all RibStates for which walks have not yet been
402 : // started. The Walker removes the first RibState from the list and starts a
403 : // table walk for it.
404 : //
405 : // The RibStateSet is used to prevent duplicates in the RibStateList. Using
406 : // just the RibStateSet to maintain the pending RibStates would have caused
407 : // problems if the same RibState is enqueued repeatedly. In that case, the
408 : // Walker would walk the same BgpTable repeatedly and starve out all other
409 : // RibStates. Using the RibStateSet and RibStateList together prevents this
410 : // problem.
411 : //
412 : // Items are inserted into RibStateList either from the bgp::PeerMembership
413 : // task or from other tasks that invoke the BgpMembershipManager public APIs.
414 : // There's no issues with concurrent access in the former case. In the latter
415 : // case, access is serialized because of the mutex in BgpMembershipManager.
416 : //
417 : // The Walker creates temporary internal state when it starts a table walk so
418 : // that walk callbacks for each DBEntry can be handled with minimal processing
419 : // overhead. Details on this temporary state are as follows:
420 : //
421 : // - walk_ref_ is the walker for the current walk
422 : // - rs_ is the RibState for which the walk was started
423 : // - peer_rib_list_ is the list of PeerRibStates for the current RibState
424 : // that have a pending action. The pending list in RibState is logically
425 : // moved to this field. This allows the RibState to accumulate a new set
426 : // of pending PeerRibStates that can be serviced in a subsequent walk.
427 : // The peer_rib_list_ is used to create and enqueue events when the table
428 : // walk finishes.
429 : // - peer_list_ is the list of IPeers to be notified about BgpPaths added
430 : // by them for RibIn processing.
431 : // - ribout_state_map_ is a map of RibOutStates that need to be processed
432 : // for each route.
433 : // - ribout_state_list_ is a list of same RibOutStates as ribout_state_map_.
434 : // It allows simpler traversal compared to the ribout_state_map_ when each
435 : // DBEntry is processed.
436 : //
437 : // A RibOutState is created for each unique RibOut in the PeerRibStates in
438 : // peer_rib_list_. It's join and leave bitsets are based on the action in
439 : // the PeerRibStates.
440 : //
441 : // A TaskTrigger that runs in context of bgp::PeerMembership task is used to
442 : // handle start and finish of table walks. This avoids concurrency issues in
443 : // accessing/clearing the pending list in the RibState. Note that TaskTrigger
444 : // in this class and the WorkQueue in BgpMembershipManager both use instance
445 : // id of 0, so they can't run concurrently.
446 : //
447 : class BgpMembershipManager::Walker {
448 : public:
449 : explicit Walker(BgpMembershipManager *manager);
450 : ~Walker();
451 :
452 : void Enqueue(RibState *rs);
453 : bool IsQueueEmpty() const;
454 :
455 : private:
456 : friend class BgpMembershipTest;
457 :
458 : class RibOutState {
459 : public:
460 126280 : explicit RibOutState(RibOut *ribout) : ribout_(ribout) { }
461 126280 : ~RibOutState() { }
462 :
463 453539 : RibOut *ribout() { return ribout_; }
464 81679 : void JoinPeer(int index) { join_bitset_.set(index); }
465 81679 : void LeavePeer(int index) { leave_bitset_.set(index); }
466 453492 : const RibPeerSet &join_bitset() { return join_bitset_; }
467 453616 : const RibPeerSet &leave_bitset() { return leave_bitset_; }
468 :
469 : private:
470 : RibOut *ribout_;
471 : RibPeerSet join_bitset_;
472 : RibPeerSet leave_bitset_;
473 :
474 : DISALLOW_COPY_AND_ASSIGN(RibOutState);
475 : };
476 :
477 : typedef BgpMembershipManager::Event Event;
478 : typedef BgpMembershipManager::RibState RibState;
479 : typedef BgpMembershipManager::PeerRibState PeerRibState;
480 : typedef BgpMembershipManager::PeerRibList PeerRibList;
481 : typedef std::set<RibState *> RibStateSet;
482 : typedef std::list<RibState *> RibStateList;
483 : typedef std::map<RibOut *, RibOutState *> RibOutStateMap;
484 : typedef std::list<RibOutState *> RibOutStateList;
485 : typedef std::set<const IPeer *> PeerList;
486 :
487 : RibOutState *LocateRibOutState(RibOut *ribout);
488 : bool WalkCallback(DBTablePartBase *tpart, DBEntryBase *db_entry);
489 : void WalkDoneCallback(DBTableBase *table);
490 : void WalkStart();
491 : void WalkFinish();
492 : bool WalkTrigger();
493 :
494 : // Testing only.
495 : void SetQueueDisable(bool value);
496 29 : size_t GetQueueSize() const { return rib_state_list_size_; }
497 4 : size_t GetPeerListSize() const { return peer_list_.size(); }
498 2 : size_t GetPeerRibListSize() const { return peer_rib_list_.size(); }
499 4 : size_t GetRibOutStateListSize() const { return ribout_state_list_size_; }
500 : void PostponeWalk();
501 : void ResumeWalk();
502 :
503 : BgpMembershipManager *manager_;
504 : RibStateSet rib_state_set_;
505 : RibStateList rib_state_list_;
506 : boost::scoped_ptr<TaskTrigger> trigger_;
507 :
508 : bool postpone_walk_;
509 : bool walk_started_;
510 : bool walk_completed_;
511 : DBTable::DBTableWalkRef walk_ref_;
512 : RibState *rs_;
513 : PeerRibList peer_rib_list_;
514 : PeerList peer_list_;
515 : RibOutStateMap ribout_state_map_;
516 : RibOutStateList ribout_state_list_;
517 : size_t rib_state_list_size_;
518 : size_t ribout_state_list_size_;
519 :
520 : DISALLOW_COPY_AND_ASSIGN(Walker);
521 : };
522 :
523 : #endif // SRC_BGP_BGP_MEMBERSHIP_H_
|
