Line data    Source code

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