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      271160 : UpdateQueue::UpdateQueue(const RibOut *ribout, int queue_id)
      15      271160 :     : queue_id_(queue_id),
      16      271160 :       encoding_is_xmpp_(ribout->IsEncodingXmpp()),
      17      271160 :       tstamp_(0),
      18      813480 :       marker_count_(0) {
      19      271160 :     queue_.push_back(tail_marker_);
      20      271160 : }
      21             : 
      22             : //
      23             : // Destroy the UpdateQueue after removing the tail marker from the FIFO.
      24             : //
      25      271160 : UpdateQueue::~UpdateQueue() {
      26      542320 :     queue_.erase(queue_.iterator_to(tail_marker_));
      27      271160 :     assert(queue_.empty());
      28      271160 :     assert(attr_set_.empty());
      29      271160 : }
      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      976390 : bool UpdateQueue::Enqueue(RouteUpdate *rt_update) {
      38      976390 :     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      976436 :     UpdateEntry *tail_upentry = &(queue_.back());
      43      976348 :     bool need_tail_dequeue = (tail_upentry == &tail_marker_);
      44      976348 :     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      976300 :     UpdateInfoSList &uinfo_slist = rt_update->Updates();
      50      976282 :     for (UpdateInfoSList::List::iterator iter = uinfo_slist->begin();
      51     3915902 :          iter != uinfo_slist->end(); ++iter) {
      52     1963624 :         iter->update = rt_update;
      53             :         UpdatesByAttr::iterator set_iter;
      54             :         bool result;
      55     1963624 :         tie(set_iter, result) = attr_set_.insert(*iter);
      56      981930 :         assert(result);
      57             :     }
      58      975939 :     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      976128 : void UpdateQueue::Dequeue(RouteUpdate *rt_update) {
      66     1952275 :     queue_.erase(queue_.iterator_to(*rt_update));
      67      976482 :     UpdateInfoSList &uinfo_slist = rt_update->Updates();
      68      976470 :     for (UpdateInfoSList::List::iterator iter = uinfo_slist->begin();
      69     1956670 :          iter != uinfo_slist->end(); ++iter) {
      70        5766 :         attr_set_.erase(attr_set_.iterator_to(*iter));
      71             :     }
      72      976392 : }
      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     1241464 : RouteUpdate *UpdateQueue::NextUpdate(UpdateEntry *current_upentry) {
      82     1241464 :     UpdatesByOrder::iterator iter = queue_.iterator_to(*current_upentry);
      83     3726837 :     while (++iter != queue_.end()) {
      84      632802 :         UpdateEntry *upentry = iter.operator->();
      85      632802 :         if (upentry->IsUpdate()) {
      86      632126 :             return static_cast<RouteUpdate *>(upentry);
      87             :         }
      88             :     }
      89      609501 :     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      979901 : void UpdateQueue::AttrDequeue(UpdateInfo *current_uinfo) {
     111     1959826 :     attr_set_.erase(attr_set_.iterator_to(*current_uinfo));
     112      980132 : }
     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      925655 : UpdateInfo *UpdateQueue::AttrNext(UpdateInfo *current_uinfo) {
     131      925655 :     UpdatesByAttr::iterator iter = attr_set_.iterator_to(*current_uinfo);
     132             :     ++iter;
     133     1851562 :     if (iter == attr_set_.end()) {
     134      604372 :         return NULL;
     135             :     }
     136      321501 :     UpdateInfo *next_uinfo = iter.operator->();
     137      321501 :     if (next_uinfo->update == current_uinfo->update) {
     138         713 :         return NULL;
     139             :     }
     140      320788 :     if (encoding_is_xmpp_) {
     141      241236 :         const RibOutAttr &next_roattr = next_uinfo->roattr;
     142      241236 :         const RibOutAttr &current_roattr = current_uinfo->roattr;
     143      241236 :         if (next_roattr.IsReachable() == current_roattr.IsReachable()) {
     144      240963 :             return next_uinfo;
     145             :         } else {
     146         262 :             return NULL;
     147             :         }
     148             :     }
     149       79552 :     if (next_uinfo->roattr.attr() == current_uinfo->roattr.attr()) {
     150       68998 :         return next_uinfo;
     151             :     }
     152       10612 :     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         686 : void UpdateQueue::AddMarker(UpdateMarker *marker, RouteUpdate *rt_update) {
     161         686 :     assert(!marker->members.empty());
     162         686 :     marker_count_++;
     163        2058 :     queue_.insert(++queue_.iterator_to(*rt_update), *marker);
     164             : 
     165         686 :     for (size_t i = marker->members.find_first();
     166        1482 :          i != BitSet::npos; i = marker->members.find_next(i)) {
     167         796 :         assert(markers_[i]);
     168         796 :         markers_[i] = marker;
     169             :     }
     170         686 : }
     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      609290 : void UpdateQueue::MoveMarker(UpdateMarker *marker, RouteUpdate *rt_update) {
     185     1218593 :     queue_.erase(queue_.iterator_to(*marker));
     186             : 
     187      609343 :     UpdatesByOrder::iterator iter = queue_.iterator_to(*rt_update);
     188      609319 :     if (marker == &tail_marker_) {
     189     1220454 :         for (iter++; iter != queue_.end() && iter->IsMarker(); iter++) {
     190             :         }
     191     1218576 :         queue_.insert(iter, *marker);
     192             :     } else {
     193          45 :         queue_.insert(++iter, *marker);
     194             :     }
     195      609298 : }
     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        2704 : void UpdateQueue::MarkerSplit(UpdateMarker *marker, const RibPeerSet &msplit) {
     207        2704 :     assert(!msplit.empty());
     208        2704 :     UpdateMarker *split_marker = new UpdateMarker();
     209        2705 :     split_marker->members = msplit;
     210             : 
     211        2705 :     marker->members.Reset(msplit);
     212        2704 :     assert(!marker->members.empty());
     213        2704 :     UpdatesByOrder::iterator mpos = queue_.iterator_to(*marker);
     214        5410 :     queue_.insert(mpos, *split_marker);
     215        2706 :     marker_count_++;
     216             : 
     217        2706 :     for (size_t i = msplit.find_first();
     218        5774 :          i != BitSet::npos; i = msplit.find_next(i)) {
     219        3069 :         assert(markers_[i]);
     220        3069 :         markers_[i] = split_marker;
     221             :     }
     222        2705 : }
     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         299 : UpdateMarker *UpdateQueue::GetMarker(int bit) {
     257         299 :     assert(markers_[bit]);
     258         299 :     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      734810 : bool UpdateQueue::Join(int bit) {
     274      734810 :     UpdateMarker *marker = &tail_marker_;
     275      734810 :     marker->members.set(bit);
     276      734810 :     if (markers_.size() < (size_t)(bit + 1))
     277      724406 :         markers_.resize(bit + 1, NULL);
     278      734810 :     assert(!markers_[bit]);
     279      734810 :     markers_[bit] = marker;
     280      734810 :     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      734810 : void UpdateQueue::Leave(int bit) {
     292      734810 :     UpdateMarker *marker = markers_[bit];
     293      734810 :     markers_[bit] = NULL;
     294      734810 :     assert(marker);
     295      734810 :     marker->members.reset(bit);
     296      734810 :     if (marker != &tail_marker_  && marker->members.empty()) {
     297        6618 :         queue_.erase(queue_.iterator_to(*marker));
     298        3309 :         delete marker;
     299             :     }
     300      734810 : }
     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       12302 : size_t UpdateQueue::size() const {
     322       12302 :     return attr_set_.size();
     323             : }
     324             : 
     325      639875 : size_t UpdateQueue::marker_count() const {
     326      639875 :     return marker_count_;
     327             : }