LCOV - code coverage report
Current view: top level - bgp - bgp_update.cc (source / functions) Hit Total Coverage
Test: OpenSDN C/C++ coverage (all TARGET_SET jobs) Lines: 70 213 32.9 %
Date: 2026-11-16 02:06:09 Functions: 12 30 40.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.14