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         243 : const UpdateInfo *UpdateInfoSList::FindUpdateInfo(
      15             :     const RibOutAttr &roattr) const {
      16         243 :     for (List::const_iterator iter = list_.begin();
      17         954 :          iter != list_.end(); ++iter) {
      18         612 :         if (iter->roattr == roattr) return iter.operator->();
      19             :     }
      20          54 :     return NULL;
      21             : }
      22             : 
      23      978469 : RouteUpdate::RouteUpdate(BgpRoute *route, int queue_id)
      24             :     : UpdateEntry(UpdateEntry::UPDATE),
      25      978396 :     route_(route),
      26      978396 :     queue_id_(queue_id),
      27      978469 :     flags_(0) {
      28      978182 : }
      29             : 
      30     1956844 : RouteUpdate::~RouteUpdate() {
      31      978420 :     ClearUpdateInfo();
      32      978386 :     ClearHistory();
      33     1956740 : }
      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      979459 : void RouteUpdate::SetUpdateInfo(UpdateInfoSList &uinfo_slist) {
      43      979459 :     assert(updates_->empty());
      44      979457 :     updates_.swap(uinfo_slist);
      45      979453 : }
      46             : 
      47             : //
      48             : // Get rid of all the UpdateInfo elements in the RouteUpdate. Each element
      49             : // is also deleted.
      50             : //
      51      980014 : void RouteUpdate::ClearUpdateInfo() {
      52      980014 :     updates_->clear_and_dispose(UpdateInfoDisposer());
      53      979978 : }
      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      923027 : bool RouteUpdate::RemoveUpdateInfo(UpdateInfo *uinfo) {
      62      923027 :     updates_->erase_and_dispose(updates_->iterator_to(*uinfo),
      63             :             UpdateInfoDisposer());
      64      923178 :     return updates_->empty();
      65             : }
      66             : 
      67             : //
      68             : // Find the UpdateInfo element with matching RibOutAttr.
      69             : //
      70        2072 : UpdateInfo *RouteUpdate::FindUpdateInfo(const RibOutAttr &roattr) {
      71        2072 :     for (UpdateInfoSList::List::iterator iter = updates_->begin();
      72        7300 :          iter != updates_->end(); ++iter) {
      73        5568 :         if (iter->roattr == roattr) return iter.operator->();
      74             :     }
      75          77 :     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        1000 : const UpdateInfo *RouteUpdate::FindUpdateInfo(const RibOutAttr &roattr) const {
      83        1000 :     for (UpdateInfoSList::List::const_iterator iter = updates_->begin();
      84        3974 :          iter != updates_->end(); ++iter) {
      85        1437 :         if (iter->roattr == roattr) return iter.operator->();
      86             :     }
      87         775 :     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          77 : void RouteUpdate::ResetUpdateInfo(const RibPeerSet &peerset) {
      95          77 :     for (UpdateInfoSList::List::iterator iter = updates_->begin();
      96         588 :          iter != updates_->end(); ) {
      97         217 :         iter->target.Reset(peerset);
      98         217 :         if (iter->target.empty()) {
      99          81 :             iter = updates_->erase_and_dispose(iter, UpdateInfoDisposer());
     100             :         } else {
     101             :             ++iter;
     102             :         }
     103             :     }
     104          77 : }
     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        1760 : 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        1760 :     RibOutAttr roattr_null;
     125        1760 :     if (uinfo_slist->empty() &&
     126        2414 :         updates_->size() == 1 && updates_->begin()->roattr == roattr_null) {
     127         332 :         RibPeerSet withdraw_peerset = updates_->begin()->target;
     128         166 :         for (AdvertiseSList::List::const_iterator iter = history_->begin();
     129         718 :              iter != history_->end(); ++iter) {
     130         203 :             if (!withdraw_peerset.Contains(iter->bitset))
     131          10 :                 return false;
     132             :         }
     133         156 :         return true;
     134         166 :     }
     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        1594 :     RibPeerSet old_peerset, new_peerset;
     141        1594 :     for (AdvertiseSList::List::const_iterator iter = history_->begin();
     142        6234 :          iter != history_->end(); ++iter) {
     143        1524 :         old_peerset.Set(iter->bitset);
     144             :     }
     145        1593 :     for (UpdateInfoSList::List::const_iterator iter = uinfo_slist->begin();
     146        5658 :          iter != uinfo_slist->end(); ++iter) {
     147        1236 :         new_peerset.Set(iter->target);
     148             :     }
     149        1593 :     if (!new_peerset.Contains(old_peerset))
     150         683 :         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         910 :     for (UpdateInfoSList::List::const_iterator iter = uinfo_slist->begin();
     158        2376 :          iter != uinfo_slist->end(); ++iter) {
     159        1000 :         RibPeerSet attr_peerset;
     160        1000 :         const UpdateInfo *uinfo = FindUpdateInfo(iter->roattr);
     161        1000 :         if (uinfo)
     162         225 :             attr_peerset.Set(uinfo->target);
     163        1000 :         const AdvertiseInfo *ainfo = FindHistory(iter->roattr);
     164        1000 :         if (ainfo)
     165          79 :             attr_peerset.Set(ainfo->bitset);
     166        1000 :         if (iter->target != attr_peerset)
     167         722 :             return false;
     168        1000 :     }
     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         188 :     for (UpdateInfoSList::List::const_iterator iter = updates_->begin();
     176         754 :          iter != updates_->end(); ++iter) {
     177         243 :         const UpdateInfo *uinfo = uinfo_slist.FindUpdateInfo(iter->roattr);
     178         432 :         if (!uinfo || !uinfo->target.Contains(iter->target))
     179          54 :             return false;
     180             :     }
     181             : 
     182         134 :     return true;
     183        1759 : }
     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          57 : void RouteUpdate::MergeUpdateInfo(UpdateInfoSList &uinfo_slist) {
     192          57 :     for (UpdateInfoSList::List::iterator iter = uinfo_slist->begin();
     193         298 :          iter != uinfo_slist->end(); ) {
     194          92 :         UpdateInfo *uinfo = FindUpdateInfo(iter->roattr);
     195          92 :         if (uinfo) {
     196          15 :             uinfo->target |= iter->target;
     197          45 :             iter = uinfo_slist->erase_and_dispose(iter, UpdateInfoDisposer());
     198             :         } else {
     199          77 :             UpdateInfo &temp_uinfo = *iter;
     200          77 :             ResetUpdateInfo(temp_uinfo.target);
     201         154 :             iter = uinfo_slist->erase(iter);
     202          77 :             updates_->push_front(temp_uinfo);
     203             :         }
     204             :     }
     205          57 : }
     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      434985 : void RouteUpdate::BuildNegativeUpdateInfo(UpdateInfoSList &uinfo_slist) const {
     219      434985 :     RibPeerSet peerset;
     220             : 
     221             :     // Build the bitset of peers to which we previously advertised something.
     222      435006 :     for (AdvertiseSList::List::const_iterator iter = history_->begin();
     223     1768851 :          iter != history_->end(); ++iter) {
     224      449678 :         peerset.Set(iter->bitset);
     225             :     }
     226             : 
     227             :     // Remove the peers to which we are going to send updated state.
     228      869502 :     for (UpdateInfoSList::List::const_iterator iter = uinfo_slist->begin();
     229      986144 :          iter != uinfo_slist->end(); ++iter) {
     230       58176 :         peerset.Reset(iter->target);
     231             :     }
     232             : 
     233             :     // Push an UpdateInfo for a withdraw if the bitset is non-empty.
     234      434874 :     if (!peerset.empty()) {
     235      381002 :         UpdateInfo *uinfo = new UpdateInfo(peerset);
     236      380939 :         uinfo_slist->push_front(*uinfo);
     237             :     }
     238      434874 : }
     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      434921 : void RouteUpdate::TrimRedundantUpdateInfo(UpdateInfoSList &uinfo_slist) const {
     250      434921 :     for (AdvertiseSList::List::const_iterator iter = history_->begin();
     251     1768901 :          iter != history_->end(); ++iter) {
     252      449643 :         const AdvertiseInfo *ainfo = iter.operator->();
     253             : 
     254      449643 :         for (UpdateInfoSList::List::iterator iter = uinfo_slist->begin();
     255     1806838 :              iter != uinfo_slist->end(); ++iter) {
     256             :             // Keep going if the attributes are different.
     257      908104 :             if (iter->roattr != ainfo->roattr)
     258      453803 :                 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         256 :             iter->target.Reset(ainfo->bitset);
     264         258 :             if (iter->target.empty()) {
     265         334 :                 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         258 :             break;
     272             :         }
     273             :     }
     274      434777 : }
     275             : 
     276             : //
     277             : // Set the given AdvertiseSList in the RouteUpdate to the given value.
     278             : //
     279             : // Should be used only for testing.
     280             : //
     281         327 : void RouteUpdate::SetHistory(AdvertiseSList &history) {
     282         327 :     assert(history_->empty());
     283         327 :     history_.swap(history);
     284         327 : }
     285             : 
     286             : //
     287             : // Get rid of all the AdvertiseInfo elements in the RouteUpdate. Each element
     288             : // is also deleted.
     289             : //
     290      978318 : void RouteUpdate::ClearHistory() {
     291      978318 :     history_->clear_and_dispose(AdvertiseInfoDisposer());
     292      978317 : }
     293             : 
     294             : //
     295             : // Move history from RouteUpdate to RouteState.
     296             : //
     297      598753 : void RouteUpdate::MoveHistory(RouteState *rstate) {
     298      598753 :     AdvertiseSList adv_slist;
     299      598744 :     SwapHistory(adv_slist);
     300      598764 :     rstate->SwapHistory(adv_slist);
     301      598763 : }
     302             : 
     303             : //
     304             : // Find the history element with matching RibOutAttr.
     305             : //
     306        1854 : const AdvertiseInfo *RouteUpdate::FindHistory(const RibOutAttr &roattr) const {
     307        1854 :     for (AdvertiseSList::List::const_iterator iter = history_->begin();
     308        6554 :          iter != history_->end(); ++iter) {
     309        3289 :         if (iter->roattr == roattr) return iter.operator->();
     310             :     }
     311         921 :     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      924005 : 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      924005 :         (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      924065 :     AdvertiseInfo *ainfo = NULL;
     333      924065 :     for (AdvertiseSList::List::iterator iter = adv_slist->begin();
     334     2777316 :          iter != adv_slist->end(); ) {
     335             :         // Remember if we find the matching element, and move on to the
     336             :         // next one.
     337      464569 :         if (iter->roattr == *roattr) {
     338        2073 :             assert(ainfo == NULL);
     339        2073 :             ainfo = iter.operator->();
     340             :             ++iter;
     341        2073 :             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      462508 :         iter->bitset.Reset(bits);
     350      462442 :         if (iter->bitset.empty()) {
     351             :             AdvertiseSList::List::iterator prev_iter = iter++;
     352      792870 :             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      924020 :     if (roattr->IsReachable()) {
     361      589534 :         if (ainfo == NULL) {
     362      587462 :             ainfo = new AdvertiseInfo(roattr);
     363      587404 :             adv_slist->push_front(*ainfo);
     364             :         }
     365      589508 :         ainfo->bitset |= bits;
     366             :     } else {
     367      334539 :         assert(ainfo == NULL);
     368             :     }
     369      924042 : }
     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      918132 : bool RouteUpdate::IsAdvertised() const {
     377      918132 :     for (AdvertiseSList::List::const_iterator iter = history_->begin();
     378     1836212 :          iter != history_->end(); ++iter) {
     379      584079 :         if (iter->roattr.IsReachable()) {
     380      584083 :             return true;
     381             :         }
     382             :     }
     383      334018 :     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          10 : UpdateList *RouteUpdate::MakeUpdateList() {
     394          10 :     UpdateList *uplist = new UpdateList;
     395          10 :     AdvertiseSList history;
     396          10 :     SwapHistory(history);
     397          10 :     uplist->SwapHistory(history);
     398          10 :     uplist->AddUpdate(this);
     399          10 :     return uplist;
     400          10 : }
     401             : 
     402             : //
     403             : // Return the UpdateList that contains this RouteUpdate.  Assumes that the
     404             : // RouteUpdate is on an UpdateList.
     405             : //
     406         270 : UpdateList *RouteUpdate::GetUpdateList(RibOut *ribout) {
     407         270 :     assert(FlagIsSet(RouteUpdate::F_LIST));
     408         270 :     DBState *dbstate = route_->GetState(ribout->table(), ribout->listener_id());
     409         270 :     UpdateList *uplist = dynamic_cast<UpdateList *>(dbstate);
     410         270 :     assert(uplist);
     411         270 :     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         210 : void UpdateList::SetHistory(AdvertiseSList &history) {
     420         210 :     assert(history_->empty());
     421         210 :     history_.swap(history);
     422         210 : }
     423             : 
     424             : //
     425             : // Move history from UpdateList to RouteState.
     426             : //
     427          40 : void UpdateList::MoveHistory(RouteState *rstate) {
     428          40 :     AdvertiseSList adv_slist;
     429          40 :     SwapHistory(adv_slist);
     430          40 :     rstate->SwapHistory(adv_slist);
     431          40 : }
     432             : 
     433             : //
     434             : // Move history from UpdateList to RouteUpdate.
     435             : //
     436         160 : void UpdateList::MoveHistory(RouteUpdate *rt_update) {
     437         160 :     AdvertiseSList adv_slist;
     438         160 :     SwapHistory(adv_slist);
     439         160 :     rt_update->SwapHistory(adv_slist);
     440         160 : }
     441             : 
     442             : //
     443             : // Find the history element with matching RibOutAttr.
     444             : //
     445          75 : const AdvertiseInfo *UpdateList::FindHistory(const RibOutAttr &roattr) const {
     446          75 :     for (AdvertiseSList::List::const_iterator iter = history_->begin();
     447         150 :          iter != history_->end(); ++iter) {
     448         150 :         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         410 : void UpdateList::AddUpdate(RouteUpdate *rt_update) {
     460         410 :     list_.push_back(rt_update);
     461         410 :     rt_update->set_update_list();
     462         410 : }
     463             : 
     464             : //
     465             : // Remove a RouteUpdate from this UpdateList.  Takes care of removing the
     466             : // linkage between the UpdateList and the RouteUpdate.
     467             : //
     468         220 : void UpdateList::RemoveUpdate(RouteUpdate *rt_update) {
     469         220 :     rt_update->clear_update_list();
     470         220 :     list_.remove(rt_update);
     471         220 : }
     472             : 
     473             : //
     474             : // Find the RouteUpdate for the given queue.
     475             : //
     476         285 : RouteUpdate *UpdateList::FindUpdate(int queue_id) {
     477         450 :     for (List::iterator iter = list_.begin(); iter != list_.end(); ++iter) {
     478         415 :         if ((*iter)->queue_id() == queue_id)
     479         250 :             return *iter;
     480             :     }
     481          35 :     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         130 : RouteUpdate *UpdateList::MakeRouteUpdate() {
     494         130 :     assert(list_.size() != 0);
     495             : 
     496         130 :     if (list_.size() > 1)
     497           0 :         return NULL;
     498             : 
     499         130 :     RouteUpdate *rt_update = list_.front();
     500         130 :     rt_update->clear_update_list();
     501         130 :     MoveHistory(rt_update);
     502         130 :     return rt_update;
     503             : }