Line data    Source code

       1             : /*
       2             :  * Copyright (c) 2013 Juniper Networks, Inc. All rights reserved.
       3             :  */
       4             : 
       5             : #include "bgp/bgp_update_queue.h"
       6             : 
       7             : #include <boost/tuple/tuple.hpp>
       8             : 
       9             : using boost::tie;
      10             : 
      11             : //
      12             : // Initialize the UpdateQueue and add the tail marker to the FIFO.
      13             : //
      14      272032 : UpdateQueue::UpdateQueue(const RibOut *ribout, int queue_id)
      15      272032 :     : queue_id_(queue_id),
      16      272032 :       encoding_is_xmpp_(ribout->IsEncodingXmpp()),
      17      272032 :       tstamp_(0),
      18      816096 :       marker_count_(0) {
      19      272032 :     queue_.push_back(tail_marker_);
      20      272032 : }
      21             : 
      22             : //
      23             : // Destroy the UpdateQueue after removing the tail marker from the FIFO.
      24             : //
      25      272032 : UpdateQueue::~UpdateQueue() {
      26      544064 :     queue_.erase(queue_.iterator_to(tail_marker_));
      27      272032 :     assert(queue_.empty());
      28      272032 :     assert(attr_set_.empty());
      29      272032 : }
      30             : 
      31             : //
      32             : // Enqueue the specified RouteUpdate to the UpdateQueue.  Updates both the
      33             : // FIFO and the set container.
      34             : //
      35             : // Return true if the UpdateQueue had no RouteUpdates after the tail marker.
      36             : //
      37      977860 : bool UpdateQueue::Enqueue(RouteUpdate *rt_update) {
      38      977860 :     rt_update->set_tstamp(++tstamp_);
      39             : 
      40             :     // Insert at the end of the FIFO. Remember if the FIFO previously had
      41             :     // no RouteUpdates after the tail marker.
      42      977791 :     UpdateEntry *tail_upentry = &(queue_.back());
      43      977662 :     bool need_tail_dequeue = (tail_upentry == &tail_marker_);
      44      977662 :     queue_.push_back(*rt_update);
      45             : 
      46             :     // Go through the UpdateInfo list and insert each element into the set
      47             :     // container for the UpdateQueue.  Also set up the back pointer to the
      48             :     // RouteUpdate.
      49      977614 :     UpdateInfoSList &uinfo_slist = rt_update->Updates();
      50      977585 :     for (UpdateInfoSList::List::iterator iter = uinfo_slist->begin();
      51     3920866 :          iter != uinfo_slist->end(); ++iter) {
      52     1965898 :         iter->update = rt_update;
      53             :         UpdatesByAttr::iterator set_iter;
      54             :         bool result;
      55     1965898 :         tie(set_iter, result) = attr_set_.insert(*iter);
      56      983142 :         assert(result);
      57             :     }
      58      977263 :     return need_tail_dequeue;
      59             : }
      60             : 
      61             : //
      62             : // Dequeue the specified RouteUpdate from the UpdateQueue.  All UpdateInfo
      63             : // elements for the RouteUpdate are removed from the set container.
      64             : //
      65      977423 : void UpdateQueue::Dequeue(RouteUpdate *rt_update) {
      66     1954886 :     queue_.erase(queue_.iterator_to(*rt_update));
      67      977840 :     UpdateInfoSList &uinfo_slist = rt_update->Updates();
      68      977807 :     for (UpdateInfoSList::List::iterator iter = uinfo_slist->begin();
      69     1959041 :          iter != uinfo_slist->end(); ++iter) {
      70        5397 :         attr_set_.erase(attr_set_.iterator_to(*iter));
      71             :     }
      72      977686 : }
      73             : 
      74             : //
      75             : // Return the next RouteUpdate after the given UpdateEntry on the UpdateQueue.
      76             : // Traverses the FIFO and skips over MARKERs and other element types to find
      77             : // the next RouteUpdate.
      78             : //
      79             : // Return NULL if there's no such RouteUpdate on the FIFO.
      80             : //
      81     1247634 : RouteUpdate *UpdateQueue::NextUpdate(UpdateEntry *current_upentry) {
      82     1247634 :     UpdatesByOrder::iterator iter = queue_.iterator_to(*current_upentry);
      83     3745415 :     while (++iter != queue_.end()) {
      84      636141 :         UpdateEntry *upentry = iter.operator->();
      85      636141 :         if (upentry->IsUpdate()) {
      86      635443 :             return static_cast<RouteUpdate *>(upentry);
      87             :         }
      88             :     }
      89      612347 :     return NULL;
      90             : }
      91             : 
      92             : //
      93             : // Return the next UpdateEntry on the UpdateQueue after the one specified.
      94             : // Traverses the FIFO and returns the next UpdateEntry, irrespective of the
      95             : // type.
      96             : //
      97             : // Return NULL if there's no such UpdateEntry on the FIFO.
      98             : //
      99         507 : UpdateEntry *UpdateQueue::NextEntry(UpdateEntry *current_upentry) {
     100         507 :     UpdatesByOrder::iterator iter = queue_.iterator_to(*current_upentry);
     101        1521 :     if (++iter == queue_.end()) {
     102           0 :         return NULL;
     103             :     }
     104         507 :     return iter.operator->();
     105             : }
     106             : 
     107             : //
     108             : // Dequeue the specified UpdateInfo from the set container.
     109             : //
     110      981186 : void UpdateQueue::AttrDequeue(UpdateInfo *current_uinfo) {
     111     1962412 :     attr_set_.erase(attr_set_.iterator_to(*current_uinfo));
     112      981407 : }
     113             : 
     114             : //
     115             : // Return the next UpdateInfo after the one provided. This traverses the set
     116             : // container and returns the next one if it has the same BgpAttr.  Note that
     117             : // we must not consider the label in order to ensure optimal packing.
     118             : //
     119             : // Returns NULL if there are no more updates with the same BgpAttr. This is
     120             : // relaxed if the RibOut encoding is XMPP since it's possible to pack items
     121             : // with different BgpAttrs in the same message given that each item is self
     122             : // contained.
     123             : //
     124             : // Also return NULL if the next UpdateInfo is for the same RouteUpdate. This
     125             : // can happen in corner cases where the label (or the set for ecmp nexthops
     126             : // in case of an XMPP ribout) for a route changes between Join operations for
     127             : // 2 different sets of IPeerUpdates. Returning such an UpdateInfo results in
     128             : // data corruption.
     129             : //
     130      924235 : UpdateInfo *UpdateQueue::AttrNext(UpdateInfo *current_uinfo) {
     131      924235 :     UpdatesByAttr::iterator iter = attr_set_.iterator_to(*current_uinfo);
     132             :     ++iter;
     133     1848818 :     if (iter == attr_set_.end()) {
     134      607454 :         return NULL;
     135             :     }
     136      317037 :     UpdateInfo *next_uinfo = iter.operator->();
     137      317037 :     if (next_uinfo->update == current_uinfo->update) {
     138         683 :         return NULL;
     139             :     }
     140      316354 :     if (encoding_is_xmpp_) {
     141      239133 :         const RibOutAttr &next_roattr = next_uinfo->roattr;
     142      239133 :         const RibOutAttr &current_roattr = current_uinfo->roattr;
     143      239133 :         if (next_roattr.IsReachable() == current_roattr.IsReachable()) {
     144      238849 :             return next_uinfo;
     145             :         } else {
     146         263 :             return NULL;
     147             :         }
     148             :     }
     149       77221 :     if (next_uinfo->roattr.attr() == current_uinfo->roattr.attr()) {
     150       66458 :         return next_uinfo;
     151             :     }
     152       10843 :     return NULL;
     153             : }
     154             : 
     155             : //
     156             : // Add the provided UpdateMarker after a specific RouteUpdate. Also update
     157             : // the MarkerList so that all peers in the provided UpdateMarker now point
     158             : // to it.
     159             : //
     160         719 : void UpdateQueue::AddMarker(UpdateMarker *marker, RouteUpdate *rt_update) {
     161         719 :     assert(!marker->members.empty());
     162         719 :     marker_count_++;
     163        2157 :     queue_.insert(++queue_.iterator_to(*rt_update), *marker);
     164             : 
     165         719 :     for (size_t i = marker->members.find_first();
     166        1574 :          i != BitSet::npos; i = marker->members.find_next(i)) {
     167         855 :         assert(markers_[i]);
     168         855 :         markers_[i] = marker;
     169             :     }
     170         719 : }
     171             : 
     172             : //
     173             : // Move the provided UpdateMarker so that it's after the RouteUpdate. Since
     174             : // the entire UpdateMarker itself is being moved, there's no need to update
     175             : // the MarkerList.
     176             : //
     177             : // If the UpdateMarker is the tail marker, skip over all markers after the
     178             : // RouteUpdate till we hit the next RouteUpdate or the end of the queue.
     179             : // This is needed for the case where some peers get blocked after sending
     180             : // the last RouteUpdate in the queue. In that scenario, the marker for the
     181             : // blocked peers is inserted after the RouteUpdate and we then try to move
     182             : // the tail marker after the RouteUpdate.
     183             : //
     184      612137 : void UpdateQueue::MoveMarker(UpdateMarker *marker, RouteUpdate *rt_update) {
     185     1224319 :     queue_.erase(queue_.iterator_to(*marker));
     186             : 
     187      612240 :     UpdatesByOrder::iterator iter = queue_.iterator_to(*rt_update);
     188      612209 :     if (marker == &tail_marker_) {
     189     1226325 :         for (iter++; iter != queue_.end() && iter->IsMarker(); iter++) {
     190             :         }
     191     1224364 :         queue_.insert(iter, *marker);
     192             :     } else {
     193          45 :         queue_.insert(++iter, *marker);
     194             :     }
     195      612201 : }
     196             : 
     197             : //
     198             : // Split the specified UpdateMarker based on the RibPeerSet. A new marker is
     199             : // created for the peers in the RibPeerSet and is inserted immediately before
     200             : // the existing marker.  The bits corresponding to the RibPeerSet being split
     201             : // are reset in the existing marker.
     202             : //
     203             : // The MarkerList is updated so that all the peers in in the RibPeerSet point
     204             : // to the new marker.
     205             : //
     206        2635 : void UpdateQueue::MarkerSplit(UpdateMarker *marker, const RibPeerSet &msplit) {
     207        2635 :     assert(!msplit.empty());
     208        2635 :     UpdateMarker *split_marker = new UpdateMarker();
     209        2636 :     split_marker->members = msplit;
     210             : 
     211        2637 :     marker->members.Reset(msplit);
     212        2637 :     assert(!marker->members.empty());
     213        2637 :     UpdatesByOrder::iterator mpos = queue_.iterator_to(*marker);
     214        5274 :     queue_.insert(mpos, *split_marker);
     215        2637 :     marker_count_++;
     216             : 
     217        2637 :     for (size_t i = msplit.find_first();
     218        5717 :          i != BitSet::npos; i = msplit.find_next(i)) {
     219        3080 :         assert(markers_[i]);
     220        3079 :         markers_[i] = split_marker;
     221             :     }
     222        2637 : }
     223             : 
     224             : //
     225             : // Merge the peers corresponding to the RibPeerSet from the src UpdateMarker
     226             : // to the dst. The bits corresponding to the RibPeerSet being merged into the
     227             : // dst are reset in the src marker. If the src UpdateMarker has no more peers,
     228             : // as a result, it is removed from the FIFO and destroyed.
     229             : //
     230          84 : void UpdateQueue::MarkerMerge(UpdateMarker *dst_marker,
     231             :         UpdateMarker *src_marker, const RibPeerSet &bitset) {
     232          84 :     assert(!bitset.empty());
     233             : 
     234             :     // Set the bits in dst and update the MarkerList.  Be sure to set the dst
     235             :     // before we reset the src since bitset maybe a reference to src->members.
     236          84 :     dst_marker->members.Set(bitset);
     237          84 :     for (size_t i = bitset.find_first();
     238         261 :          i != BitSet::npos; i = bitset.find_next(i)) {
     239         177 :         assert(markers_[i]);
     240         177 :         markers_[i] = dst_marker;
     241             :     }
     242             : 
     243             :     // Reset the bits in the src and get rid of it in case it's now empty.
     244          84 :     src_marker->members.Reset(bitset);
     245          84 :     if (src_marker->members.empty()) {
     246         168 :         queue_.erase(queue_.iterator_to(*src_marker));
     247          84 :         assert(src_marker != &tail_marker_);
     248          84 :         delete src_marker;
     249          84 :         marker_count_--;
     250             :     }
     251          84 : }
     252             : 
     253             : //
     254             : // Return the UpdateMarker for the peer specified by the bit position.
     255             : //
     256         300 : UpdateMarker *UpdateQueue::GetMarker(int bit) {
     257         300 :     assert(markers_[bit]);
     258         300 :     return markers_[bit];
     259             : }
     260             : 
     261             : //
     262             : // Join a new peer, as represented by it's bit index, to the UpdateQueue.
     263             : // Since it's a new peer, it starts out at the tail marker.  Also add the
     264             : // peer's bit index and the tail marker pair to the MarkerList, growing
     265             : // the MarkerList if necessary.
     266             : //
     267             : // Return true if the tail marker is not the last entry in the queue. The
     268             : // caller should trigger a tail dequeue for the RibOut if so to take care
     269             : // of the possibility that all peers in the tail marker are blocked. Note
     270             : // that a tail dequeue may already be pending in the BgpUpdateSender, but
     271             : // an extra one is harmless.
     272             : //
     273      735602 : bool UpdateQueue::Join(int bit) {
     274      735602 :     UpdateMarker *marker = &tail_marker_;
     275      735602 :     marker->members.set(bit);
     276      735602 :     if (markers_.size() < (size_t)(bit + 1))
     277      725282 :         markers_.resize(bit + 1, NULL);
     278      735602 :     assert(!markers_[bit]);
     279      735602 :     markers_[bit] = marker;
     280      735602 :     return (&tail_marker_ != &queue_.back());
     281             : }
     282             : 
     283             : //
     284             : // Leave a peer, as represented by it's bit index, from the UpdateQueue.
     285             : // Find the current marker for the peer and clear the peer bit's entry in
     286             : // the MarkerList. Don't bother shrinking the MarkerList - the entry can
     287             : // be reused by a subsequent Join.
     288             : // Reset the peer's bit in the marker and get rid of the marker itself if
     289             : // it's now empty.
     290             : //
     291      735602 : void UpdateQueue::Leave(int bit) {
     292      735602 :     UpdateMarker *marker = markers_[bit];
     293      735602 :     markers_[bit] = NULL;
     294      735602 :     assert(marker);
     295      735602 :     marker->members.reset(bit);
     296      735602 :     if (marker != &tail_marker_  && marker->members.empty()) {
     297        6544 :         queue_.erase(queue_.iterator_to(*marker));
     298        3272 :         delete marker;
     299             :     }
     300      735602 : }
     301             : 
     302         856 : bool UpdateQueue::CheckInvariants() const {
     303       20632 :     for (size_t idx = 0; idx < markers_.size(); ++idx) {
     304       19776 :         UpdateMarker *marker = markers_[idx];
     305       19776 :         if (!marker)
     306           0 :             continue;
     307       19776 :         CHECK_INVARIANT(marker->members.test(idx));
     308             :     }
     309         856 :     return true;
     310             : }
     311             : 
     312             : //
     313             : // Return true if the UpdateQueue is empty.  It's considered empty if there
     314             : // are as no UpdateInfo elements in the set container. We don't look at the
     315             : // FIFO since that may still have the tail marker on it.
     316             : //
     317          16 : bool UpdateQueue::empty() const {
     318          16 :     return attr_set_.empty();
     319             : }
     320             : 
     321       18142 : size_t UpdateQueue::size() const {
     322       18142 :     return attr_set_.size();
     323             : }
     324             : 
     325      648972 : size_t UpdateQueue::marker_count() const {
     326      648972 :     return marker_count_;
     327             : }