Line data    Source code

       1             : /*
       2             :  * Copyright (c) 2013 Juniper Networks, Inc. All rights reserved.
       3             :  */
       4             : 
       5             : #include "bgp/bgp_update.h"
       6             : 
       7             : #include "bgp/bgp_route.h"
       8             : #include "bgp/bgp_table.h"
       9             : 
      10             : //
      11             : // Find the UpdateInfo element with matching RibOutAttr.
      12             : //
      13         257 : const UpdateInfo *UpdateInfoSList::FindUpdateInfo(
      14             :     const RibOutAttr &roattr) const {
      15         257 :     for (List::const_iterator iter = list_.begin();
      16         982 :          iter != list_.end(); ++iter) {
      17         616 :         if (iter->roattr == roattr) return iter.operator->();
      18             :     }
      19          66 :     return NULL;
      20             : }
      21             : 
      22      974973 : RouteUpdate::RouteUpdate(BgpRoute *route, int queue_id)
      23             :     : UpdateEntry(UpdateEntry::UPDATE),
      24      974952 :     route_(route),
      25      974952 :     queue_id_(queue_id),
      26      974973 :     flags_(0) {
      27      974837 : }
      28             : 
      29     1949860 : RouteUpdate::~RouteUpdate() {
      30      974941 :     ClearUpdateInfo();
      31      974932 :     ClearHistory();
      32     1949791 : }
      33             : 
      34             : //
      35             : // Set the given UpdateInfoSList in the RouteUpdate to the given value.
      36             : //
      37             : // Note that the back pointers from the individual UpdateInfo elements
      38             : // to the RouteUpdate will be set up when the RouteUpdate gets enqueued
      39             : // to an UpdateQueue.
      40             : //
      41      976100 : void RouteUpdate::SetUpdateInfo(UpdateInfoSList &uinfo_slist) {
      42      976100 :     assert(updates_->empty());
      43      976107 :     updates_.swap(uinfo_slist);
      44      976098 : }
      45             : 
      46             : //
      47             : // Get rid of all the UpdateInfo elements in the RouteUpdate. Each element
      48             : // is also deleted.
      49             : //
      50      976531 : void RouteUpdate::ClearUpdateInfo() {
      51      976531 :     updates_->clear_and_dispose(UpdateInfoDisposer());
      52      976507 : }
      53             : 
      54             : //
      55             : // Remove the UpdateInfo element from the UpdateInfoSList and delete the
      56             : // element.
      57             : //
      58             : // Return true if the UpdateInfoSList is now empty.
      59             : //
      60      920832 : bool RouteUpdate::RemoveUpdateInfo(UpdateInfo *uinfo) {
      61      920832 :     updates_->erase_and_dispose(updates_->iterator_to(*uinfo),
      62             :             UpdateInfoDisposer());
      63      921013 :     return updates_->empty();
      64             : }
      65             : 
      66             : //
      67             : // Find the UpdateInfo element with matching RibOutAttr.
      68             : //
      69        2072 : UpdateInfo *RouteUpdate::FindUpdateInfo(const RibOutAttr &roattr) {
      70        2072 :     for (UpdateInfoSList::List::iterator iter = updates_->begin();
      71        7300 :          iter != updates_->end(); ++iter) {
      72        5568 :         if (iter->roattr == roattr) return iter.operator->();
      73             :     }
      74          77 :     return NULL;
      75             : }
      76             : 
      77             : //
      78             : // Find the UpdateInfo element with matching RibOutAttr, full of const
      79             : // goodness so it can be used by CompareUpdateInfo.
      80             : //
      81        1024 : const UpdateInfo *RouteUpdate::FindUpdateInfo(const RibOutAttr &roattr) const {
      82        1024 :     for (UpdateInfoSList::List::const_iterator iter = updates_->begin();
      83        4066 :          iter != updates_->end(); ++iter) {
      84        1463 :         if (iter->roattr == roattr) return iter.operator->();
      85             :     }
      86         797 :     return NULL;
      87             : }
      88             : 
      89             : //
      90             : // Reset the given RibPeerSet from the target of all UpdateInfo elements. Get
      91             : // rid of any elements whose target becomes empty.
      92             : //
      93          77 : void RouteUpdate::ResetUpdateInfo(const RibPeerSet &peerset) {
      94          77 :     for (UpdateInfoSList::List::iterator iter = updates_->begin();
      95         588 :          iter != updates_->end(); ) {
      96         217 :         iter->target.Reset(peerset);
      97         217 :         if (iter->target.empty()) {
      98          81 :             iter = updates_->erase_and_dispose(iter, UpdateInfoDisposer());
      99             :         } else {
     100             :             ++iter;
     101             :         }
     102             :     }
     103          77 : }
     104             : 
     105             : //
     106             : // Compare this RouteUpdate with the UpdateInfo elements in the given list.
     107             : // The UpdateInfos and AdvertiseInfos in the RouteUpdate represent the old
     108             : // state and the UpdateInfoSList represents the new state.
     109             : //
     110             : // Uses brute force since the UpdateInfo and AdvertiseInfo lists typically
     111             : // contain just a single element.
     112             : //
     113             : // Return true if the information in the RouteUpdate is logically the same
     114             : // as that in the UpdateInfoSList.
     115             : //
     116        1691 : bool RouteUpdate::CompareUpdateInfo(const UpdateInfoSList &uinfo_slist) const {
     117             :     // Handle the special case where the given UpdateInfoSList is empty.
     118             :     //
     119             :     // If we already have withdraws scheduled to all peers to which the
     120             :     // route was sent earlier, and there are no other scheduled updates,
     121             :     // we can safely consider the RouteUpdate to have the same state as
     122             :     // an empty UpdateInfoSList.
     123        1691 :     RibOutAttr roattr_null;
     124        1691 :     if (uinfo_slist->empty() &&
     125        2308 :         updates_->size() == 1 && updates_->begin()->roattr == roattr_null) {
     126         266 :         RibPeerSet withdraw_peerset = updates_->begin()->target;
     127         133 :         for (AdvertiseSList::List::const_iterator iter = history_->begin();
     128         582 :              iter != history_->end(); ++iter) {
     129         168 :             if (!withdraw_peerset.Contains(iter->bitset))
     130          10 :                 return false;
     131             :         }
     132         123 :         return true;
     133         133 :     }
     134             : 
     135             :     // All the peers that we sent the route to previously must be covered
     136             :     // by the UpdateInfos in the given UpdateInfoSList. If this is not the
     137             :     // case, we would need to schedule withdraws to the peers that are not
     138             :     // covered.
     139        1558 :     RibPeerSet old_peerset, new_peerset;
     140        1558 :     for (AdvertiseSList::List::const_iterator iter = history_->begin();
     141        6014 :          iter != history_->end(); ++iter) {
     142        1449 :         old_peerset.Set(iter->bitset);
     143             :     }
     144        1558 :     for (UpdateInfoSList::List::const_iterator iter = uinfo_slist->begin();
     145        5570 :          iter != uinfo_slist->end(); ++iter) {
     146        1227 :         new_peerset.Set(iter->target);
     147             :     }
     148        1558 :     if (!new_peerset.Contains(old_peerset))
     149         612 :         return false;
     150             : 
     151             :     // Compare the peerset for each UpdateInfo in the UpdateInfoSList to
     152             :     // the peerset for the corresponding UpdateInfo and AdvertiseInfo in
     153             :     // in the RouteUpdate i.e. the ones for the same RibOutAttr.  Each
     154             :     // peer in the new UpdateInfo must either be in the old UpdateInfo or
     155             :     // AdvertiseInfo.
     156         946 :     for (UpdateInfoSList::List::const_iterator iter = uinfo_slist->begin();
     157        2452 :          iter != uinfo_slist->end(); ++iter) {
     158        1024 :         RibPeerSet attr_peerset;
     159        1024 :         const UpdateInfo *uinfo = FindUpdateInfo(iter->roattr);
     160        1024 :         if (uinfo)
     161         227 :             attr_peerset.Set(uinfo->target);
     162        1024 :         const AdvertiseInfo *ainfo = FindHistory(iter->roattr);
     163        1024 :         if (ainfo)
     164          79 :             attr_peerset.Set(ainfo->bitset);
     165        1024 :         if (iter->target != attr_peerset)
     166         744 :             return false;
     167        1024 :     }
     168             : 
     169             :     // Compare the peerset for each UpdateInfo in the RouteUpdate to the
     170             :     // corresponding UpdateInfo in the given UpdateInfoSList. The peerset
     171             :     // from the old UpdateInfo needs to be a subset of the peerset from
     172             :     // the new UpdateInfo. It need not be equal since we may already have
     173             :     // sent the old state to some peers and moved them to the history.
     174         202 :     for (UpdateInfoSList::List::const_iterator iter = updates_->begin();
     175         786 :          iter != updates_->end(); ++iter) {
     176         257 :         const UpdateInfo *uinfo = uinfo_slist.FindUpdateInfo(iter->roattr);
     177         448 :         if (!uinfo || !uinfo->target.Contains(iter->target))
     178          66 :             return false;
     179             :     }
     180             : 
     181         136 :     return true;
     182        1691 : }
     183             : 
     184             : //
     185             : // Merge the list of UpdateInfo elements into the RouteUpdate. If we find
     186             : // an UpdateInfo with the same RibOutAttr, we modify it's target in place.
     187             : // Otherwise, we reset the target bits in any existing UpdateInfos in the
     188             : // RouteUpdate and move the UpdateInfo from the list into the RouteUpdate.
     189             : //
     190          57 : void RouteUpdate::MergeUpdateInfo(UpdateInfoSList &uinfo_slist) {
     191          57 :     for (UpdateInfoSList::List::iterator iter = uinfo_slist->begin();
     192         298 :          iter != uinfo_slist->end(); ) {
     193          92 :         UpdateInfo *uinfo = FindUpdateInfo(iter->roattr);
     194          92 :         if (uinfo) {
     195          15 :             uinfo->target |= iter->target;
     196          45 :             iter = uinfo_slist->erase_and_dispose(iter, UpdateInfoDisposer());
     197             :         } else {
     198          77 :             UpdateInfo &temp_uinfo = *iter;
     199          77 :             ResetUpdateInfo(temp_uinfo.target);
     200         154 :             iter = uinfo_slist->erase(iter);
     201          77 :             updates_->push_front(temp_uinfo);
     202             :         }
     203             :     }
     204          57 : }
     205             : 
     206             : //
     207             : // The AdvertiseSList in the history contains state that has been sent to
     208             : // a set of peers, and the given UpdateInfoSList represents state that we
     209             : // intend to send to a possibly different set of peers.
     210             : //
     211             : // If there are peers in any AdvertiseInfo in the history for which there
     212             : // is no state in the UpdateInfoSList, create an UpdateInfo with negative
     213             : // state to withdraw what we sent out previously. This UpdateInfo has null
     214             : // RibOutAttr and a RibPeerSet of all peers from which we need to withdraw
     215             : // the route.
     216             : //
     217      432020 : void RouteUpdate::BuildNegativeUpdateInfo(UpdateInfoSList &uinfo_slist) const {
     218      432020 :     RibPeerSet peerset;
     219             : 
     220             :     // Build the bitset of peers to which we previously advertised something.
     221      432016 :     for (AdvertiseSList::List::const_iterator iter = history_->begin();
     222     1755976 :          iter != history_->end(); ++iter) {
     223      446153 :         peerset.Set(iter->bitset);
     224             :     }
     225             : 
     226             :     // Remove the peers to which we are going to send updated state.
     227      863689 :     for (UpdateInfoSList::List::const_iterator iter = uinfo_slist->begin();
     228      980990 :          iter != uinfo_slist->end(); ++iter) {
     229       58534 :         peerset.Reset(iter->target);
     230             :     }
     231             : 
     232             :     // Push an UpdateInfo for a withdraw if the bitset is non-empty.
     233      431952 :     if (!peerset.empty()) {
     234      377694 :         UpdateInfo *uinfo = new UpdateInfo(peerset);
     235      377638 :         uinfo_slist->push_front(*uinfo);
     236             :     }
     237      431923 : }
     238             : 
     239             : //
     240             : // If any UpdateInfo element in the UpdateInfoSList describes state that's
     241             : // already in one of the AdvertiseInfos in the history, trim that state to
     242             : // avoid sending duplicate information.
     243             : //
     244             : // The RibPeerSet in the UpdateInfo need not be exactly the same as that in
     245             : // the AdevrtiseInfo.  If the RibOutAttrs match, we can trim the RibPeerSet
     246             : // in the UpdateInfo.
     247             : //
     248      431922 : void RouteUpdate::TrimRedundantUpdateInfo(UpdateInfoSList &uinfo_slist) const {
     249      431922 :     for (AdvertiseSList::List::const_iterator iter = history_->begin();
     250     1755840 :          iter != history_->end(); ++iter) {
     251      446112 :         const AdvertiseInfo *ainfo = iter.operator->();
     252             : 
     253      446112 :         for (UpdateInfoSList::List::iterator iter = uinfo_slist->begin();
     254     1792483 :              iter != uinfo_slist->end(); ++iter) {
     255             :             // Keep going if the attributes are different.
     256      900842 :             if (iter->roattr != ainfo->roattr)
     257      450160 :                 continue;
     258             : 
     259             :             // Found one with matching attributes.  Reset the target bits in
     260             :             // the UpdateInfo. Get rid of the UpdateInfo if the target is now
     261             :             // empty.
     262         254 :             iter->target.Reset(ainfo->bitset);
     263         257 :             if (iter->target.empty()) {
     264         326 :                 uinfo_slist->erase_and_dispose(iter, UpdateInfoDisposer());
     265             :             }
     266             : 
     267             :             // Since a given UpdateInfoSList can have at most one UpdateInfo
     268             :             // with any given attributes, there's no point in looking at any
     269             :             // more UpdateInfos.
     270         257 :             break;
     271             :         }
     272             :     }
     273      431777 : }
     274             : 
     275             : //
     276             : // Set the given AdvertiseSList in the RouteUpdate to the given value.
     277             : //
     278             : // Should be used only for testing.
     279             : //
     280         327 : void RouteUpdate::SetHistory(AdvertiseSList &history) {
     281         327 :     assert(history_->empty());
     282         327 :     history_.swap(history);
     283         327 : }
     284             : 
     285             : //
     286             : // Get rid of all the AdvertiseInfo elements in the RouteUpdate. Each element
     287             : // is also deleted.
     288             : //
     289      974915 : void RouteUpdate::ClearHistory() {
     290      974915 :     history_->clear_and_dispose(AdvertiseInfoDisposer());
     291      974872 : }
     292             : 
     293             : //
     294             : // Move history from RouteUpdate to RouteState.
     295             : //
     296      598760 : void RouteUpdate::MoveHistory(RouteState *rstate) {
     297      598760 :     AdvertiseSList adv_slist;
     298      598747 :     SwapHistory(adv_slist);
     299      598736 :     rstate->SwapHistory(adv_slist);
     300      598730 : }
     301             : 
     302             : //
     303             : // Find the history element with matching RibOutAttr.
     304             : //
     305        1878 : const AdvertiseInfo *RouteUpdate::FindHistory(const RibOutAttr &roattr) const {
     306        1878 :     for (AdvertiseSList::List::const_iterator iter = history_->begin();
     307        6564 :          iter != history_->end(); ++iter) {
     308        3270 :         if (iter->roattr == roattr) return iter.operator->();
     309             :     }
     310         945 :     return NULL;
     311             : }
     312             : 
     313             : //
     314             : // Update the history information for the RouteUpdate to include the given
     315             : // RibOutAttr and the RibPeerSet. This may entail an update to an existing
     316             : // AdvertiseInfo or the creation of a new one, as well as possible deletion
     317             : // of an existing one.
     318             : //
     319      921907 : void RouteUpdate::UpdateHistory(RibOut *ribout, const RibOutAttr *roattr,
     320             :         const RibPeerSet &bits) {
     321             :     // The history information may reside in the RouteUpdate itself or in
     322             :     // the associated UpdateList if the RouteUpdate in on an UpdateList.
     323             :     AdvertiseSList &adv_slist =
     324      921907 :         (OnUpdateList() ? GetUpdateList(ribout)->History() : history_);
     325             : 
     326             :     // Traipse through all the AdvertiseInfo elements in the history.  We
     327             :     // obviously need to find one with a matching RibOutAttr if it exists
     328             :     // and update it's RibPeerSet.   Additionally, we also want to reset
     329             :     // the RibPeerSet in all other elements since we may have previously
     330             :     // advertised different attributes to some of the peers in the set.
     331      921931 :     AdvertiseInfo *ainfo = NULL;
     332      921931 :     for (AdvertiseSList::List::iterator iter = adv_slist->begin();
     333     2765645 :          iter != adv_slist->end(); ) {
     334             :         // Remember if we find the matching element, and move on to the
     335             :         // next one.
     336      460870 :         if (iter->roattr == *roattr) {
     337        2002 :             assert(ainfo == NULL);
     338        2002 :             ainfo = iter.operator->();
     339             :             ++iter;
     340        2002 :             continue;
     341             :         }
     342             : 
     343             :         // TBD: optimize to reuse an element with the same RibPeerSet but
     344             :         // different attributes.
     345             : 
     346             :         // Reset the bits in the current element.  If the RibPeerSet in the
     347             :         // element becomes empty, get rid of it.
     348      458862 :         iter->bitset.Reset(bits);
     349      458835 :         if (iter->bitset.empty()) {
     350             :             AdvertiseSList::List::iterator prev_iter = iter++;
     351      790083 :             adv_slist->erase_and_dispose(prev_iter, AdvertiseInfoDisposer());
     352             :         } else {
     353             :             ++iter;
     354             :         }
     355             :     }
     356             : 
     357             :     // Update an existing element if we found one or create a new one with
     358             :     // the appropriate state.
     359      921907 :     if (roattr->IsReachable()) {
     360      588948 :         if (ainfo == NULL) {
     361      586946 :             ainfo = new AdvertiseInfo(roattr);
     362      586924 :             adv_slist->push_front(*ainfo);
     363             :         }
     364      588934 :         ainfo->bitset |= bits;
     365             :     } else {
     366      333013 :         assert(ainfo == NULL);
     367             :     }
     368      921922 : }
     369             : 
     370             : //
     371             : // Return true if this RouteUpdate has been advertised to anyone. We simply
     372             : // go through all the AdvertiseInfo elements in the history and check if we
     373             : // have at least one that's reachable.
     374             : //
     375      915940 : bool RouteUpdate::IsAdvertised() const {
     376      915940 :     for (AdvertiseSList::List::const_iterator iter = history_->begin();
     377     1831835 :          iter != history_->end(); ++iter) {
     378      583407 :         if (iter->roattr.IsReachable()) {
     379      583407 :             return true;
     380             :         }
     381             :     }
     382      332492 :     return false;
     383             : }
     384             : 
     385             : //
     386             : // Upgrade this RouteUpdate to an UpdateList.  Creates a new UpdateList and
     387             : // adds the RouteUpdate to it.  Also moves the history from the RouteUpdate
     388             : // to the UpdateList.
     389             : //
     390             : // Returns the new UpdateList.
     391             : //
     392          10 : UpdateList *RouteUpdate::MakeUpdateList() {
     393          10 :     UpdateList *uplist = new UpdateList;
     394          10 :     AdvertiseSList history;
     395          10 :     SwapHistory(history);
     396          10 :     uplist->SwapHistory(history);
     397          10 :     uplist->AddUpdate(this);
     398          10 :     return uplist;
     399          10 : }
     400             : 
     401             : //
     402             : // Return the UpdateList that contains this RouteUpdate.  Assumes that the
     403             : // RouteUpdate is on an UpdateList.
     404             : //
     405         270 : UpdateList *RouteUpdate::GetUpdateList(RibOut *ribout) {
     406         270 :     assert(FlagIsSet(RouteUpdate::F_LIST));
     407         270 :     DBState *dbstate = route_->GetState(ribout->table(), ribout->listener_id());
     408         270 :     UpdateList *uplist = dynamic_cast<UpdateList *>(dbstate);
     409         270 :     assert(uplist);
     410         270 :     return uplist;
     411             : }
     412             : 
     413             : //
     414             : // Set the given AdvertiseSList in the UpdateList to the given value.
     415             : //
     416             : // Should be used only for testing.
     417             : //
     418         210 : void UpdateList::SetHistory(AdvertiseSList &history) {
     419         210 :     assert(history_->empty());
     420         210 :     history_.swap(history);
     421         210 : }
     422             : 
     423             : //
     424             : // Move history from UpdateList to RouteState.
     425             : //
     426          40 : void UpdateList::MoveHistory(RouteState *rstate) {
     427          40 :     AdvertiseSList adv_slist;
     428          40 :     SwapHistory(adv_slist);
     429          40 :     rstate->SwapHistory(adv_slist);
     430          40 : }
     431             : 
     432             : //
     433             : // Move history from UpdateList to RouteUpdate.
     434             : //
     435         160 : void UpdateList::MoveHistory(RouteUpdate *rt_update) {
     436         160 :     AdvertiseSList adv_slist;
     437         160 :     SwapHistory(adv_slist);
     438         160 :     rt_update->SwapHistory(adv_slist);
     439         160 : }
     440             : 
     441             : //
     442             : // Find the history element with matching RibOutAttr.
     443             : //
     444          75 : const AdvertiseInfo *UpdateList::FindHistory(const RibOutAttr &roattr) const {
     445          75 :     for (AdvertiseSList::List::const_iterator iter = history_->begin();
     446         150 :          iter != history_->end(); ++iter) {
     447         150 :         if (iter->roattr == roattr) return iter.operator->();
     448             :     }
     449           0 :     return NULL;
     450             : }
     451             : 
     452             : //
     453             : // Add a RouteUpdate to this UpdateList.  Sets up the association between
     454             : // the RouteUpdate and the UpdateList.
     455             : //
     456             : // Assumes that RouteUpdate has no history i.e. AdvertiseSList is empty.
     457             : //
     458         410 : void UpdateList::AddUpdate(RouteUpdate *rt_update) {
     459         410 :     list_.push_back(rt_update);
     460         410 :     rt_update->set_update_list();
     461         410 : }
     462             : 
     463             : //
     464             : // Remove a RouteUpdate from this UpdateList.  Takes care of removing the
     465             : // linkage between the UpdateList and the RouteUpdate.
     466             : //
     467         220 : void UpdateList::RemoveUpdate(RouteUpdate *rt_update) {
     468         220 :     rt_update->clear_update_list();
     469         220 :     list_.remove(rt_update);
     470         220 : }
     471             : 
     472             : //
     473             : // Find the RouteUpdate for the given queue.
     474             : //
     475         285 : RouteUpdate *UpdateList::FindUpdate(int queue_id) {
     476         450 :     for (List::iterator iter = list_.begin(); iter != list_.end(); ++iter) {
     477         415 :         if ((*iter)->queue_id() == queue_id)
     478         250 :             return *iter;
     479             :     }
     480          35 :     return NULL;
     481             : }
     482             : 
     483             : //
     484             : // Downgrade this UpdateList to a RouteUpdate if there's only 1 RouteUpdate
     485             : // on it. Takes care of removing the linkage between the UpdateList and the
     486             : // last RouteUpdate and moves history from the UpdateList to the RouteUpdate.
     487             : //
     488             : // Note that the caller is responsible for deleting the UpdateList.
     489             : //
     490             : // Returns the last/only RouteUpdate if successful, NULL otherwise.
     491             : //
     492         130 : RouteUpdate *UpdateList::MakeRouteUpdate() {
     493         130 :     assert(list_.size() != 0);
     494             : 
     495         130 :     if (list_.size() > 1)
     496           0 :         return NULL;
     497             : 
     498         130 :     RouteUpdate *rt_update = list_.front();
     499         130 :     rt_update->clear_update_list();
     500         130 :     MoveHistory(rt_update);
     501         130 :     return rt_update;
     502             : }