OpenSDN source code
bgp_update_sender.cc
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 
7 
8 #include <boost/bind/bind.hpp>
9 #include <boost/foreach.hpp>
10 
11 #include <map>
12 #include <string>
13 #include <atomic>
14 
15 #include "base/task_annotations.h"
16 #include "bgp/ipeer.h"
17 #include "bgp/bgp_ribout.h"
18 #include "bgp/bgp_ribout_updates.h"
19 #include "db/db.h"
20 
21 using std::unique_ptr;
22 using std::make_pair;
23 using std::map;
24 using std::string;
25 using std::vector;
26 using namespace boost::placeholders;
27 
28 //
29 // This struct represents RibOut specific state for a PeerState. There's one
30 // instance of this for each RibOut that an IPeerUpdate has joined.
31 //
32 // The PeerRibState contains a bit mask to keep track of the QueueIds that are
33 // currently active for the RibOut for the IPeerUpdate.
34 //
36  PeerRibState() : qactive(0) { }
37  uint8_t qactive;
38 };
39 
40 //
41 // This nested class represents IPeerUpdate related state that's specific to
42 // the BgpSenderPartition.
43 //
44 // A PeerState contains a Map of the index for a RibState to a PeerRibState.
45 // Each entry in the map logically represents the state of the peer for the
46 // ribout.
47 //
48 // The Map is used in conjunction with the RibStateMap in BgpSenderPartition
49 // to implement regular and circular iterator classes that are used to walk
50 // through all the RibState entries for a peer.
51 //
52 // A PeerState maintains the in_sync and send_ready state for the IPeerUpdate.
53 //
54 // The PeerState is considered to be send_ready when the underlying socket is
55 // is writable. Note that the send_ready state in the PeerState may be out of
56 // date with the actual socket state because the socket could have got blocked
57 // when writing from another partition. Hence IPeerUpdate::send_ready() is the
58 // more authoritative source.
59 //
60 // The PeerState is considered to be in_sync if it's send_ready and the marker
61 // IPeerUpdate the peer has merged with the tail marker for all QueueIds in
62 // all RiBOuts for which the IPeerUpdate is subscribed.
63 //
64 // The PeerState keeps count of the number of active RibOuts for each QueueId.
65 // A (RibOut, QueueId) pair is considered to be active if the PeerState isn't
66 // send_ready and there's RouteUpdates for the pair.
67 //
69 public:
70  typedef map<size_t, PeerRibState> Map;
71 
72  class iterator : public boost::iterator_facade<
73  iterator, RibOut, boost::forward_traversal_tag> {
74  public:
75  explicit iterator(const RibStateMap &indexmap, Map *map, size_t index)
76  : indexmap_(indexmap), map_(map), index_(index) {
77  }
78  size_t index() const { return index_; }
79  RibState *rib_state() { return indexmap_.At(index_); }
80  const PeerRibState &peer_rib_state() const { return (*map_)[index_]; }
81 
82  private:
83  friend class boost::iterator_core_access;
84  void increment() {
85  Map::const_iterator loc = map_->upper_bound(index_);
86  if (loc == map_->end()) {
87  index_ = -1;
88  } else {
89  index_ = loc->first;
90  }
91  }
92  bool equal(const iterator &rhs) const {
93  return index_ == rhs.index_;
94  }
95  RibOut &dereference() const;
96 
99  size_t index_;
100  };
101 
102  class circular_iterator : public boost::iterator_facade<
103  circular_iterator, RibOut, boost::forward_traversal_tag> {
104  public:
105  explicit circular_iterator(const RibStateMap &indexmap, Map *map,
106  int start, bool is_valid)
107  : indexmap_(indexmap), map_(map), index_(-1), match_(true) {
108  if (map_->empty()) {
109  return;
110  }
111  Map::const_iterator loc = map_->lower_bound(start);
112  if (loc == map_->end()) {
113  loc = map_->begin();
114  }
115  index_ = loc->first;
116  if (is_valid) match_ = false;
117  }
118  int index() const { return index_; }
119  RibState *rib_state() { return indexmap_.At(index_); }
120  const PeerRibState &peer_rib_state() const { return (*map_)[index_]; }
121 
122  private:
123  friend class boost::iterator_core_access;
124  void increment() {
125  match_ = true;
126  assert(!map_->empty());
127  Map::const_iterator loc = map_->upper_bound(index_);
128  if (loc == map_->end()) {
129  loc = map_->begin();
130  }
131  index_ = loc->first;
132  }
133  bool equal(const circular_iterator &rhs) const {
134  return ((match_ == rhs.match_) && (index_ == rhs.index_));
135  }
136  RibOut &dereference() const;
137 
140  int index_;
141  bool match_;
142  };
143 
144  explicit PeerState(IPeerUpdate *peer)
145  : key_(peer), index_(-1),
146  qactive_cnt_(RibOutUpdates::QCOUNT),
147  in_sync_(true), rib_iterator_(BitSet::npos) {
148  send_ready_ = true;
149  for (int i = 0; i < RibOutUpdates::QCOUNT; i++) {
150  qactive_cnt_[i] = 0;
151  }
152  }
153 
154  void Add(RibState *rs);
155 
156  void Remove(RibState *rs);
157 
158  bool IsMember(size_t index) const {
159  return rib_bitset_.test(index);
160  }
161 
162  iterator begin(const RibStateMap &indexmap) {
163  Map::const_iterator it = rib_set_.begin();
164  size_t index = (it != rib_set_.end() ? it->first : -1);
165  return iterator(indexmap, &rib_set_, index);
166  }
167  iterator end(const RibStateMap &indexmap) {
168  return iterator(indexmap, &rib_set_, -1);
169  }
170 
172  return circular_iterator(indexmap, &rib_set_, rib_iterator_, true);
173  }
175  return circular_iterator(indexmap, &rib_set_, rib_iterator_, false);
176  }
177 
178  void SetIteratorStart(size_t start) { rib_iterator_ = start; }
179 
180  void SetQueueActive(size_t rib_index, int queue_id) {
181  CHECK_CONCURRENCY("bgp::SendUpdate");
182  Map::iterator loc = rib_set_.find(rib_index);
183  assert(loc != rib_set_.end());
184  if (!BitIsSet(loc->second.qactive, queue_id)) {
185  SetBit(loc->second.qactive, queue_id);
186  qactive_cnt_[queue_id]++;
187  }
188  }
189 
190  void SetQueueInactive(size_t rib_index, int queue_id) {
191  CHECK_CONCURRENCY("bgp::SendUpdate", "bgp::PeerMembership");
192  Map::iterator loc = rib_set_.find(rib_index);
193  assert(loc != rib_set_.end());
194  if (BitIsSet(loc->second.qactive, queue_id)) {
195  ClearBit(loc->second.qactive, queue_id);
196  qactive_cnt_[queue_id]--;
197  }
198  }
199 
200  bool IsQueueActive(size_t rib_index, int queue_id) {
201  CHECK_CONCURRENCY("bgp::SendUpdate");
202  Map::iterator loc = rib_set_.find(rib_index);
203  assert(loc != rib_set_.end());
204  return BitIsSet(loc->second.qactive, queue_id);
205  }
206 
207  int QueueCount(int queue_id) { return qactive_cnt_[queue_id]; }
208 
209  IPeerUpdate *peer() const { return key_; }
210  void set_index(size_t index) { index_ = index; }
211  size_t index() const { return index_; }
212 
213  bool in_sync() const { return in_sync_; }
214  void clear_sync() { in_sync_ = false; }
215  void SetSync();
216 
217  bool send_ready() const { return send_ready_; }
218  void set_send_ready(bool toggle) { send_ready_ = toggle; }
219 
220  bool empty() const { return rib_set_.empty(); }
221 
222  bool CheckInvariants() const {
223  for (int i = 0; i < RibOutUpdates::QCOUNT; i++) {
224  CHECK_INVARIANT(qactive_cnt_[i] <= (int) rib_set_.size());
225  }
226  return true;
227  }
228 
229 private:
231  size_t index_; // assigned from PeerStateMap
232  Map rib_set_; // list of RibOuts advertised by the peer.
233  BitSet rib_bitset_; // bitset of RibOuts advertised by the peer
234  vector<int> qactive_cnt_;
235  bool in_sync_; // whether the peer may dequeue tail markers.
236  std::atomic<bool> send_ready_; // whether the peer may send updates.
237  size_t rib_iterator_; // index of last processed rib.
238 
240 };
241 
242 //
243 // This nested class represents RibOut related state that's specific to the
244 // BgpSenderPartition.
245 //
246 // A RibState contains a BitSet of all the peers that are advertising the
247 // RibOut associated with the RibState.
248 //
249 // The BitSet is used in conjunction with PeerStateMap in BgpSenderPartition
250 // to implement an iterator that is used to walk through all the PeerState
251 // entries for the ribout.
252 //
254 public:
255  class iterator : public boost::iterator_facade<
256  iterator, PeerState, boost::forward_traversal_tag> {
257  public:
258  explicit iterator(const PeerStateMap &indexmap,
259  const BitSet &set, size_t index)
260  : indexmap_(indexmap), set_(set), index_(index) {
261  }
262  size_t index() const { return index_; }
263 
264  private:
265  friend class boost::iterator_core_access;
266  void increment() {
267  index_ = set_.find_next(index_);
268  }
269  bool equal(const iterator &rhs) const {
270  return index_ == rhs.index_;
271  }
273  return *indexmap_.At(index_);
274  }
276  const BitSet &set_;
277  size_t index_;
278  };
279 
280  explicit RibState(RibOut *ribout)
281  : key_(ribout), index_(-1), in_sync_(RibOutUpdates::QCOUNT, true) {
282  }
283 
284  void Add(PeerState *ps);
285  void Remove(PeerState *ps);
286 
287  bool QueueSync(int queue_id);
288  void SetQueueSync(int queue_id);
289  void SetQueueUnsync(int queue_id);
290 
291  RibOut *ribout() { return key_; }
292 
293  iterator begin(const PeerStateMap &indexmap) {
294  return iterator(indexmap, peer_set_, peer_set_.find_first());
295  }
296 
297  iterator end(const PeerStateMap &indexmap) {
298  return iterator(indexmap, peer_set_, BitSet::npos);
299  }
300 
301  void set_index(size_t index) { index_ = index; }
302  size_t index() const { return index_; }
303 
304  bool empty() const { return peer_set_.none(); }
305 
306  const BitSet &peer_set() const { return peer_set_; }
307 
308 private:
310  size_t index_;
312  vector<bool> in_sync_;
313 
315 };
316 
317 
319  CHECK_CONCURRENCY("bgp::PeerMembership");
320  peer_set_.set(ps->index());
321 }
322 
324  CHECK_CONCURRENCY("bgp::PeerMembership");
325  peer_set_.reset(ps->index());
326 }
327 
329  CHECK_CONCURRENCY("bgp::SendUpdate");
330  return (in_sync_[queue_id]);
331 }
332 
334  CHECK_CONCURRENCY("bgp::SendUpdate");
335  in_sync_[queue_id] = true;
336 }
337 
339  CHECK_CONCURRENCY("bgp::SendUpdate");
340  in_sync_[queue_id] = false;
341 }
342 
344  CHECK_CONCURRENCY("bgp::PeerMembership");
346  rib_set_.insert(make_pair(rs->index(), init));
347  rib_bitset_.set(rs->index());
348 }
349 
351  CHECK_CONCURRENCY("bgp::PeerMembership");
352  for (int queue_id = 0; queue_id < RibOutUpdates::QCOUNT; queue_id++) {
353  SetQueueInactive(rs->index(), queue_id);
354  }
355  rib_set_.erase(rs->index());
356  rib_bitset_.reset(rs->index());
357 }
358 
360  CHECK_CONCURRENCY("bgp::SendUpdate");
361  for (Map::iterator it = rib_set_.begin(); it != rib_set_.end(); ++it) {
362  assert(it->second.qactive == 0);
363  }
364  for (int i = 0; i < RibOutUpdates::QCOUNT; i++) {
365  assert(qactive_cnt_[i] == 0);
366  }
367  in_sync_ = true;
368 }
369 
371  return *indexmap_.At(index_)->ribout();
372 }
373 
375  return *indexmap_.At(index_)->ribout();
376 }
377 
379 public:
380  explicit Worker(BgpSenderPartition *partition)
381  : Task(partition->task_id(), partition->index()),
382  partition_(partition) {
383  }
384 
385  virtual bool Run() {
386  CHECK_CONCURRENCY("bgp::SendUpdate");
387 
388  while (true) {
389  unique_ptr<WorkBase> wentry = partition_->WorkDequeue();
390  if (!wentry.get())
391  break;
392  if (!wentry->valid)
393  continue;
394  switch (wentry->type) {
395  case WorkBase::WRibOut: {
396  WorkRibOut *workrib = static_cast<WorkRibOut *>(wentry.get());
397  partition_->UpdateRibOut(workrib->ribout, workrib->queue_id);
398  break;
399  }
400  case WorkBase::WPeer: {
401  WorkPeer *workpeer = static_cast<WorkPeer *>(wentry.get());
402  partition_->UpdatePeer(workpeer->peer);
403  break;
404  }
405  }
406  }
407 
408  return true;
409  }
410  string Description() const { return "BgpSenderPartition::Worker"; }
411 
412 private:
414 };
415 
417  : sender_(sender),
418  index_(index),
419  running_(false),
420  disabled_(false),
421  worker_task_(NULL) {
422 }
423 
425  if (worker_task_) {
427  scheduler->Cancel(worker_task_);
428  }
429  assert(peer_state_imap_.empty());
430  assert(rib_state_imap_.empty());
431 }
432 
434  return sender_->task_id();
435 }
436 
437 //
438 // Add the (RibOut, IPeerUpdate) combo to the BgpSenderPartition.
439 // Find or create the corresponding RibState and PeerState and sets up the
440 // cross-linkage.
441 //
443  CHECK_CONCURRENCY("bgp::PeerMembership");
444 
445  RibState *rs = rib_state_imap_.Locate(ribout);
446  PeerState *ps = peer_state_imap_.Locate(peer);
447  rs->Add(ps);
448  ps->Add(rs);
449 }
450 
451 //
452 // Remove the (RibOut, IPeerUpdate) combo from the BgpSenderPartition.
453 // Decouple cross linkage between the corresponding RibState and PeerState and
454 // get rid of the RibState and/or PeerState if they are no longer needed.
455 //
457  CHECK_CONCURRENCY("bgp::PeerMembership");
458 
459  RibState *rs = rib_state_imap_.Find(ribout);
460  PeerState *ps = peer_state_imap_.Find(peer);
461  assert(rs != NULL);
462  assert(ps != NULL);
463  rs->Remove(ps);
464  ps->Remove(rs);
465  if (rs->empty()) {
466  WorkRibOutInvalidate(ribout);
467  rib_state_imap_.Remove(ribout, rs->index());
468  }
469  if (ps->empty()) {
470  WorkPeerInvalidate(peer);
471  peer_state_imap_.Remove(peer, ps->index());
472  }
473 }
474 
475 //
476 // Create and enqueue new WorkRibOut entry since the RibOut is now
477 // active.
478 //
479 void BgpSenderPartition::RibOutActive(RibOut *ribout, int queue_id) {
480  CHECK_CONCURRENCY("db::DBTable", "bgp::SendUpdate", "bgp::PeerMembership");
481 
482  WorkRibOutEnqueue(ribout, queue_id);
483 }
484 
485 //
486 // Mark an IPeerUpdate to be send ready.
487 //
489  CHECK_CONCURRENCY("bgp::SendReadyTask");
490 
491  // The IPeerUpdate may not be registered if it has not reached Established
492  // state or it may already have been unregistered by the time we get around
493  // to processing the notification.
494  PeerState *ps = peer_state_imap_.Find(peer);
495  if (!ps)
496  return;
497 
498  // Nothing to do if the IPeerUpdate's already in that state.
499  if (ps->send_ready())
500  return;
501 
502  // Create and enqueue new WorkPeer entry.
503  ps->set_send_ready(true);
504  WorkPeerEnqueue(peer);
505 }
506 
507 //
508 // Return true if the IPeer is send ready.
509 //
511  CHECK_CONCURRENCY("bgp::PeerMembership", "bgp::ShowCommand");
512 
513  PeerState *ps = peer_state_imap_.Find(peer);
514  return ps->send_ready();
515 }
516 
517 //
518 // Return true if the IPeer is registered.
519 //
521  CHECK_CONCURRENCY("bgp::PeerMembership", "bgp::ShowCommand");
522 
523  return (peer_state_imap_.Find(peer) != NULL);
524 }
525 
526 //
527 // Return true if the IPeer is in sync.
528 //
530  CHECK_CONCURRENCY("bgp::PeerMembership", "bgp::ShowCommand");
531 
532  PeerState *ps = peer_state_imap_.Find(peer);
533  return (ps ? ps->in_sync() : false);
534 }
535 
536 //
537 // Create a Worker if warranted and enqueue it to the TaskScheduler.
538 // Assumes that the caller holds the BgpSenderPartition mutex.
539 //
541  if (!running_ && !disabled_) {
542  worker_task_ = new Worker(this);
544  scheduler->Enqueue(worker_task_);
545  running_ = true;
546  }
547 }
548 
549 //
550 // Dequeue the first WorkBase item from the work queue and return an
551 // unique_ptr to it. Clear out Worker related state if the work queue
552 // is empty.
553 //
554 unique_ptr<BgpSenderPartition::WorkBase> BgpSenderPartition::WorkDequeue() {
555  CHECK_CONCURRENCY("bgp::SendUpdate");
556 
557  unique_ptr<WorkBase> wentry;
558  if (work_queue_.empty()) {
559  worker_task_ = NULL;
560  running_ = false;
561  } else {
562  wentry.reset(work_queue_.pop_front().release());
563  }
564  return wentry;
565 }
566 
567 //
568 // Enqueue a WorkBase entry into the the work queue and start a new Worker
569 // task if required.
570 //
572  CHECK_CONCURRENCY("db::DBTable", "bgp::SendUpdate", "bgp::SendReadyTask",
573  "bgp::PeerMembership");
574 
575  work_queue_.push_back(wentry);
577 }
578 
579 //
580 // Disable or enable the worker.
581 // For unit testing.
582 //
583 void BgpSenderPartition::set_disabled(bool disabled) {
584  disabled_ = disabled;
586 }
587 
588 //
589 // Enqueue a WorkPeer to the work queue.
590 //
592  CHECK_CONCURRENCY("bgp::SendReadyTask");
593 
594  WorkBase *wentry = new WorkPeer(peer);
595  WorkEnqueue(wentry);
596 }
597 
598 //
599 // Invalidate all WorkBases for the given IPeerUpdate.
600 // Used when a IPeerUpdate is removed.
601 //
603  CHECK_CONCURRENCY("bgp::PeerMembership");
604 
605  for (WorkQueue::iterator it = work_queue_.begin();
606  it != work_queue_.end(); ++it) {
607  WorkBase *wentry = it.operator->();
608  if (wentry->type != WorkBase::WPeer)
609  continue;
610  WorkPeer *wpeer = static_cast<WorkPeer *>(wentry);
611  if (wpeer->peer != peer)
612  continue;
613  wpeer->valid = false;
614  }
615 }
616 
617 //
618 // Enqueue a WorkRibOut to the work queue.
619 //
620 void BgpSenderPartition::WorkRibOutEnqueue(RibOut *ribout, int queue_id) {
621  CHECK_CONCURRENCY("db::DBTable", "bgp::SendUpdate", "bgp::PeerMembership");
622 
623  WorkBase *wentry = new WorkRibOut(ribout, queue_id);
624  WorkEnqueue(wentry);
625 }
626 
627 //
628 // Invalidate all WorkBases for the given RibOut.
629 // Used when a RibOut is removed.
630 //
632  CHECK_CONCURRENCY("bgp::PeerMembership");
633 
634  for (WorkQueue::iterator it = work_queue_.begin();
635  it != work_queue_.end(); ++it) {
636  WorkBase *wentry = it.operator->();
637  if (wentry->type != WorkBase::WRibOut)
638  continue;
639  WorkRibOut *wribout = static_cast<WorkRibOut *>(wentry);
640  if (wribout->ribout != ribout)
641  continue;
642  wribout->valid = false;
643  }
644 }
645 
646 //
647 // Build the RibPeerSet of IPeers for the RibOut that are in sync. Note that
648 // we need to use bit indices that are specific to the RibOut, not the ones
649 // from the BgpSenderPartition.
650 //
652  RibPeerSet *msync) {
653  CHECK_CONCURRENCY("bgp::SendUpdate");
654 
656  it != rs->end(peer_state_imap_); ++it) {
657  PeerState *ps = it.operator->();
658 
659  // If the PeerState is in sync but the IPeerUpdate is not send ready
660  // then update the sync and send ready state in the PeerState. Note
661  // that the RibOut queue for the PeerState will get marked active via
662  // the call the SetQueueActive from UpdateRibOut.
663  if (ps->in_sync()) {
664  if (ps->peer()->send_ready()) {
665  int rix = ribout->GetPeerIndex(ps->peer());
666  msync->set(rix);
667  } else {
668  ps->clear_sync();
669  ps->set_send_ready(false);
670  }
671  }
672  }
673 }
674 
675 //
676 // Take the RibPeerSet of blocked IPeers and update the relevant PeerStates.
677 // Note that bit indices in the RibPeerSet and are specific to the RibOut.
678 //
680  int queue_id, const RibPeerSet &blocked) {
681  CHECK_CONCURRENCY("bgp::SendUpdate");
682 
683  for (size_t bit = blocked.find_first(); bit != RibPeerSet::npos;
684  bit = blocked.find_next(bit)) {
685  IPeerUpdate *peer = ribout->GetPeer(bit);
686  PeerState *ps = peer_state_imap_.Find(peer);
687  ps->SetQueueActive(rs->index(), queue_id);
688  ps->clear_sync();
689  ps->set_send_ready(false);
690  }
691 }
692 
693 //
694 // For unit testing only.
695 // Take the RibPeerSet of blocked IPeers and update the relevant PeerStates.
696 //
698  int queue_id, const RibPeerSet &blocked) {
699  CHECK_CONCURRENCY("bgp::SendUpdate");
700 
701  RibState *rs = rib_state_imap_.Find(ribout);
702  assert(rs);
703  SetSendBlocked(ribout, rs, queue_id, blocked);
704 }
705 
706 //
707 // Concurrency: called from bgp send task.
708 //
709 // Take the RibPeerSet of unsync IPeers and update the relevant PeerStates.
710 // Note that bit indices in the RibPeerSet and are specific to the RibOut.
711 //
713  int queue_id, const RibPeerSet &munsync) {
714  CHECK_CONCURRENCY("bgp::SendUpdate");
715 
716  for (size_t bit = munsync.find_first(); bit != RibPeerSet::npos;
717  bit = munsync.find_next(bit)) {
718  IPeerUpdate *peer = ribout->GetPeer(bit);
719  PeerState *ps = peer_state_imap_.Find(peer);
720  ps->SetQueueActive(rs->index(), queue_id);
721  }
722 }
723 
724 //
725 // Concurrency: called from bgp send task.
726 //
727 // Mark the PeerRibState corresponding to the given IPeerUpdate and RibOut
728 // as active.
729 //
730 // Used by unit test code.
731 //
732 void BgpSenderPartition::SetQueueActive(RibOut *ribout, int queue_id,
733  IPeerUpdate *peer) {
734  CHECK_CONCURRENCY("bgp::SendUpdate");
735 
736  PeerState *ps = peer_state_imap_.Find(peer);
737  RibState *rs = rib_state_imap_.Find(ribout);
738  ps->SetQueueActive(rs->index(), queue_id);
739 }
740 
741 //
742 // Concurrency: called from bgp send task.
743 //
744 // Check if the queue corresponding to IPeerUpdate, Ribout and queue id is
745 // active.
746 //
747 // Used by unit test code.
748 //
749 bool BgpSenderPartition::IsQueueActive(RibOut *ribout, int queue_id,
750  IPeerUpdate *peer) {
751  CHECK_CONCURRENCY("bgp::SendUpdate");
752 
753  PeerState *ps = peer_state_imap_.Find(peer);
754  RibState *rs = rib_state_imap_.Find(ribout);
755  return ps->IsQueueActive(rs->index(), queue_id);
756 }
757 
758 //
759 // Concurrency: called from bgp send task.
760 //
761 // Mark all the RibStates for the given peer and queue id as being in sync
762 // and trigger a tail dequeue.
763 //
765  CHECK_CONCURRENCY("bgp::SendUpdate");
766 
768  it != ps->end(rib_state_imap_); ++it) {
769  RibState *rs = it.rib_state();
770  if (!rs->QueueSync(queue_id)) {
771  RibOut *ribout = it.operator->();
772  RibOutActive(ribout, queue_id);
773  rs->SetQueueSync(queue_id);
774  }
775  }
776 }
777 
778 //
779 // Drain the queue until there are no more updates or all the members become
780 // blocked.
781 //
782 void BgpSenderPartition::UpdateRibOut(RibOut *ribout, int queue_id) {
783  CHECK_CONCURRENCY("bgp::SendUpdate");
784 
785  RibOutUpdates *updates = ribout->updates(index_);
786  RibState *rs = rib_state_imap_.Find(ribout);
787  RibPeerSet msync;
788 
789  // Convert group in-sync list to rib specific bitset.
790  BuildSyncBitSet(ribout, rs, &msync);
791 
792  // Drain the queue till we can do no more.
793  RibPeerSet blocked, munsync;
794  bool done = updates->TailDequeue(queue_id, msync, &blocked, &munsync);
795  assert(msync.Contains(blocked));
796 
797  // Mark peers as send blocked.
798  SetSendBlocked(ribout, rs, queue_id, blocked);
799 
800  // Set the queue to be active for any unsync peers. If we don't do this,
801  // we will forget to mark the (RibOut,QueueId) as active for these peers
802  // since the blocked RibPeerSet does not contain peers that are already
803  // out of sync. Note that the unsync peers would have been split from
804  // the tail marker in TailDequeue.
805  SetQueueActive(ribout, rs, queue_id, munsync);
806 
807  // If all peers are blocked, mark the queue as unsync in the RibState. We
808  // will trigger tail dequeue for the (RibOut,QueueId) when any peer that
809  // is interested in the RibOut becomes in sync.
810  if (!done)
811  rs->SetQueueUnsync(queue_id);
812 }
813 
814 //
815 // Go through all RibOuts for the IPeerUpdate and drain the given queue till it
816 // is up-to date or it becomes blocked. If it's blocked, select the next RibOut
817 // to be processed when the IPeerUpdate becomes send ready.
818 //
819 // Return false if the IPeerUpdate got blocked.
820 //
822  int queue_id) {
823  CHECK_CONCURRENCY("bgp::SendUpdate");
824 
826  it != ps->circular_end(rib_state_imap_); ++it) {
827  // Skip if this queue is not active in the PeerRibState.
828  if (!BitIsSet(it.peer_rib_state().qactive, queue_id))
829  continue;
830 
831  // Drain the queue till we can do no more.
832  RibOut *ribout = it.operator->();
833  RibOutUpdates *updates = ribout->updates(index_);
834  RibPeerSet blocked;
835  bool done = updates->PeerDequeue(queue_id, peer, &blocked);
836 
837  // Process blocked mask.
838  RibState *rs = it.rib_state();
839  SetSendBlocked(ribout, rs, queue_id, blocked);
840 
841  // If the peer is still send_ready, mark the queue as inactive for
842  // the peer. Need to check send_ready because the return value of
843  // PeerDequeue only tells that *some* peer was merged with the tail
844  // marker.
845  // If the peer got blocked, remember where to start next time and
846  // stop processing. We don't want to continue processing for other
847  // merged peers if the lead peer is blocked. Processing for other
848  // peers will continue when their own WorkPeer items are processed.
849  if (ps->send_ready()) {
850  assert(done);
851  ps->SetQueueInactive(rs->index(), queue_id);
852  } else {
853  ps->SetIteratorStart(it.index());
854  return false;
855  }
856  }
857 
858  return true;
859 }
860 
861 //
862 // Drain the queue of all updates for this IPeerUpdate, until it is up-to date
863 // or it becomes blocked.
864 //
866  CHECK_CONCURRENCY("bgp::SendUpdate");
867 
868  // Bail if the PeerState is not send ready.
869  PeerState *ps = peer_state_imap_.Find(peer);
870  if (!ps->send_ready()) {
871  return;
872  }
873 
874  // Update the PeerState and bail if the IPeerUpdate is not send ready.
875  // This happens if the IPeerUpdate gets blocked while processing some
876  // other partition.
877  if (!peer->send_ready()) {
878  ps->set_send_ready(false);
879  return;
880  }
881 
882  // Go through all queues and drain them if there's anything on them.
883  for (int queue_id = RibOutUpdates::QCOUNT - 1; queue_id >= 0; --queue_id) {
884  if (ps->QueueCount(queue_id) == 0) {
885  continue;
886  }
887  if (!UpdatePeerQueue(peer, ps, queue_id)) {
888  assert(!ps->send_ready());
889  return;
890  }
891  }
892 
893  // Checking the return value of UpdatePeerQueue above is not sufficient as
894  // that only tells us that *some* peer(s) got merged with the tail marker.
895  // Need to make sure that the IPeerUpdate that we are processing is still
896  // send ready.
897  if (!ps->send_ready()) {
898  return;
899  }
900 
901  // Mark the peer as being in sync across all tables.
902  ps->SetSync();
903 
904  // Mark all RibStates for the peer as being in sync. This triggers a tail
905  // dequeue for the corresponding (RibOut, QueueId) if necessary. This in
906  // turn ensures that we do not get stuck in the case where all peers get
907  // blocked and then get back in sync.
908  for (int queue_id = RibOutUpdates::QCOUNT - 1; queue_id >= 0; --queue_id) {
909  SetQueueSync(ps, queue_id);
910  }
911 }
912 
913 //
914 // Check invariants for the BgpSenderPartition.
915 //
917  int grp_peer_count = 0;
918  int peer_grp_count = 0;
919  for (size_t i = 0; i < rib_state_imap_.size(); i++) {
920  if (!rib_state_imap_.bits().test(i)) {
921  continue;
922  }
923  RibState *rs = rib_state_imap_.At(i);
924  assert(rs != NULL);
925  CHECK_INVARIANT(rs->index() == i);
927  it != rs->end(peer_state_imap_); ++it) {
928  PeerState *ps = it.operator->();
929  CHECK_INVARIANT(ps->IsMember(i));
930  grp_peer_count++;
931  }
932  }
933  for (size_t i = 0; i < peer_state_imap_.size(); i++) {
934  if (!peer_state_imap_.bits().test(i)) {
935  continue;
936  }
937  PeerState *ps = peer_state_imap_.At(i);
938  assert(ps != NULL);
939  CHECK_INVARIANT(ps->index() == i);
940  if (!ps->CheckInvariants()) {
941  return false;
942  }
944  it != ps->end(rib_state_imap_); ++it) {
945  RibState *rs = it.rib_state();
946  CHECK_INVARIANT(rs->peer_set().test(i));
947  peer_grp_count++;
948  }
949  }
950 
951  CHECK_INVARIANT(grp_peer_count == peer_grp_count);
952  return true;
953 }
954 
955 //
956 // Constructor for BgpUpdateSender.
957 // Initialize send ready WorkQueue and allocate BgpSenderPartitions.
958 //
960  : server_(server),
961  task_id_(TaskScheduler::GetInstance()->GetTaskId("bgp::SendUpdate")),
962  send_ready_queue_(
963  TaskScheduler::GetInstance()->GetTaskId("bgp::SendReadyTask"), 0,
964  boost::bind(&BgpUpdateSender::SendReadyCallback, this, _1)) {
965  for (int idx = 0; idx < DB::PartitionCount(); ++idx) {
966  partitions_.push_back(new BgpSenderPartition(this, idx));
967  }
968 }
969 
970 //
971 // Destructor for BgpUpdateSender.
972 // Shutdown the WorkQueue and delete all BgpSenderPartitions.
973 //
977 }
978 
979 //
980 // Handle the join of an IPeerUpdate to a RibOut.
981 //
983  CHECK_CONCURRENCY("bgp::PeerMembership");
984 
985  BOOST_FOREACH(BgpSenderPartition *partition, partitions_) {
986  partition->Add(ribout, peer);
987  }
988 }
989 
990 //
991 // Handle the leave of an IPeerUpdate from a RibOut.
992 //
994  CHECK_CONCURRENCY("bgp::PeerMembership");
995 
996  BOOST_FOREACH(BgpSenderPartition *partition, partitions_) {
997  partition->Remove(ribout, peer);
998  }
999 }
1000 
1001 //
1002 // Inform the specified BgpSenderPartition that it needs to schedule a tail
1003 // dequeue for the given RibOut queue.
1004 //
1005 void BgpUpdateSender::RibOutActive(int index, RibOut *ribout, int queue_id) {
1006  CHECK_CONCURRENCY("db::DBTable", "bgp::PeerMembership");
1007 
1008  partitions_[index]->RibOutActive(ribout, queue_id);
1009 }
1010 
1011 //
1012 // Concurrency: called from arbitrary task.
1013 //
1014 // Enqueue the IPeerUpdate to the send ready processing work queue.
1015 // The callback is invoked in the context of bgp::SendReadyTask.
1016 //
1018  send_ready_queue_.Enqueue(peer);
1019 }
1020 
1021 //
1022 // Return true if the IPeer is registered.
1023 //
1025  BOOST_FOREACH(BgpSenderPartition *partition, partitions_) {
1026  if (partition->PeerIsRegistered(peer))
1027  return true;
1028  }
1029  return false;
1030 }
1031 
1032 //
1033 // Return true if the IPeer is in sync.
1034 //
1036  BOOST_FOREACH(BgpSenderPartition *partition, partitions_) {
1037  if (!partition->PeerInSync(peer))
1038  return false;
1039  }
1040  return true;
1041 }
1042 
1043 //
1044 // Callback to handle send ready notification for IPeerUpdate. Processing it
1045 // in the context of bgp::SendeReadyTask ensures that there are no concurrency
1046 // issues w.r.t. the BgpSenderPartition working on the IPeerUpdate while we are
1047 // processing the notification.
1048 //
1050  CHECK_CONCURRENCY("bgp::SendReadyTask");
1051 
1052  BOOST_FOREACH(BgpSenderPartition *partition, partitions_) {
1053  partition->PeerSendReady(peer);
1054  }
1055  return true;
1056 }
1057 
1058 //
1059 // Check invariants for the BgpUpdateSender.
1060 //
1062  BOOST_FOREACH(BgpSenderPartition *partition, partitions_) {
1063  if (!partition->CheckInvariants())
1064  return false;
1065  }
1066  return true;
1067 }
1068 
1069 //
1070 // Disable all BgpSenderPartitions.
1071 //
1073  BOOST_FOREACH(BgpSenderPartition *partition, partitions_) {
1074  partition->set_disabled(true);
1075  }
1076 }
1077 
1078 //
1079 // Enable all BgpSenderPartitions.
1080 //
1082  BOOST_FOREACH(BgpSenderPartition *partition, partitions_) {
1083  partition->set_disabled(false);
1084  }
1085 }
bool equal(const circular_iterator &rhs) const
circular_iterator(const RibStateMap &indexmap, Map *map, int start, bool is_valid)
bool equal(const iterator &rhs) const
iterator(const RibStateMap &indexmap, Map *map, size_t index)
const PeerRibState & peer_rib_state() const
iterator end(const RibStateMap &indexmap)
void SetQueueInactive(size_t rib_index, int queue_id)
bool IsQueueActive(size_t rib_index, int queue_id)
iterator begin(const RibStateMap &indexmap)
void SetQueueActive(size_t rib_index, int queue_id)
circular_iterator circular_begin(const RibStateMap &indexmap)
map< size_t, PeerRibState > Map
circular_iterator circular_end(const RibStateMap &indexmap)
bool IsMember(size_t index) const
bool equal(const iterator &rhs) const
iterator(const PeerStateMap &indexmap, const BitSet &set, size_t index)
iterator begin(const PeerStateMap &indexmap)
iterator end(const PeerStateMap &indexmap)
const BitSet & peer_set() const
Worker(BgpSenderPartition *partition)
virtual bool Run()
Code to execute in a task. Returns true if task is completed. Return false to reschedule the task.
BgpSenderPartition * partition_
string Description() const
Gives a description of the task.
bool CheckInvariants() const
std::unique_ptr< WorkBase > WorkDequeue()
void RibOutActive(RibOut *ribout, int queue_id)
void SetSendBlocked(RibOut *ribout, int queue_id, const RibPeerSet &blocked)
void Remove(RibOut *ribout, IPeerUpdate *peer)
void Add(RibOut *ribout, IPeerUpdate *peer)
void WorkRibOutInvalidate(RibOut *ribout)
bool PeerIsSendReady(IPeerUpdate *peer) const
void BuildSyncBitSet(const RibOut *ribout, RibState *rs, RibPeerSet *msync)
void WorkRibOutEnqueue(RibOut *ribout, int queue_id)
void SetQueueSync(PeerState *ps, int queue_id)
void set_disabled(bool disabled)
bool IsQueueActive(RibOut *ribout, int queue_id, IPeerUpdate *peer)
bool PeerIsRegistered(IPeerUpdate *peer) const
RibStateMap rib_state_imap_
void WorkPeerEnqueue(IPeerUpdate *peer)
BgpUpdateSender * sender_
void UpdatePeer(IPeerUpdate *peer)
void PeerSendReady(IPeerUpdate *peer)
void SetQueueActive(const RibOut *ribout, RibState *rs, int queue_id, const RibPeerSet &munsync)
bool PeerInSync(IPeerUpdate *peer) const
bool UpdatePeerQueue(IPeerUpdate *peer, PeerState *ps, int queue_id)
PeerStateMap peer_state_imap_
BgpSenderPartition(BgpUpdateSender *sender, int index)
void WorkEnqueue(WorkBase *wentry)
void UpdateRibOut(RibOut *ribout, int queue_id)
void WorkPeerInvalidate(IPeerUpdate *peer)
bool PeerInSync(IPeerUpdate *peer) const
void Leave(RibOut *ribout, IPeerUpdate *peer)
bool PeerIsRegistered(IPeerUpdate *peer) const
BgpSenderPartition * partition(int index)
bool CheckInvariants() const
void Join(RibOut *ribout, IPeerUpdate *peer)
bool SendReadyCallback(IPeerUpdate *peer)
void RibOutActive(int index, RibOut *ribout, int queue_id)
BgpUpdateSender(BgpServer *server)
WorkQueue< IPeerUpdate * > send_ready_queue_
std::vector< BgpSenderPartition * > partitions_
void PeerSendReady(IPeerUpdate *peer)
Definition: bitset.h:18
static const size_t npos
Definition: bitset.h:20
size_t find_first() const
Definition: bitset.cc:243
size_t find_next(size_t pos) const
Definition: bitset.cc:256
bool Contains(const BitSet &rhs) const
Definition: bitset.cc:537
BitSet & set(size_t pos)
Definition: bitset.cc:126
bool test(size_t pos) const
Definition: bitset.cc:147
static int PartitionCount()
Definition: db.cc:32
virtual bool send_ready() const
Definition: ipeer.h:24
ValueType * At(int index) const
Definition: index_map.h:32
bool empty() const
Definition: index_map.h:103
const BitsetType & bits() const
Definition: index_map.h:111
size_t size() const
Definition: index_map.h:101
ValueType * Locate(const KeyType &key)
Definition: index_map.h:92
void Remove(const KeyType &key, int index, bool clear_bit=true)
Definition: index_map.h:70
ValueType * Find(const KeyType &key) const
Definition: index_map.h:35
virtual bool PeerDequeue(int queue_id, IPeerUpdate *peer, RibPeerSet *blocked)
virtual bool TailDequeue(int queue_id, const RibPeerSet &msync, RibPeerSet *blocked, RibPeerSet *unsync)
RibOutUpdates * updates(int idx)
Definition: bgp_ribout.h:318
IPeerUpdate * GetPeer(int index) const
Definition: bgp_ribout.cc:534
int GetPeerIndex(IPeerUpdate *peer) const
Definition: bgp_ribout.cc:545
The TaskScheduler keeps track of what tasks are currently schedulable. When a task is enqueued it is ...
Definition: task.h:307
void Enqueue(Task *task)
Enqueues a task for running. Starts task if all policy rules are met else puts task in waitq....
Definition: task.cc:662
static TaskScheduler * GetInstance()
Definition: task.cc:574
CancelReturnCode Cancel(Task *task)
Cancels a Task that can be in RUN/WAIT state. The caller needs to ensure that the task exists when Ca...
Definition: task.cc:727
Task is a class to describe a computational task within OpenSDN control plane applications....
Definition: task.h:82
bool Enqueue(QueueEntryT entry)
Definition: queue_task.h:249
void Shutdown(bool delete_entries=true)
Definition: queue_task.h:153
static bool disabled_
Definition: logging.cc:20
void init()
Definition: bgp_log.cc:38
#define CHECK_CONCURRENCY(...)
void SetBit(IntType &value, size_t bit)
Definition: util.h:42
void ClearBit(IntType &value, size_t bit)
Definition: util.h:47
void STLDeleteValues(Container *container)
Definition: util.h:102
bool BitIsSet(IntType value, size_t bit)
Definition: util.h:37
#define CHECK_INVARIANT(Cond)
Definition: util.h:30