Line data    Source code

       1             : /*
       2             :  * Copyright (c) 2013 Juniper Networks, Inc. All rights reserved.
       3             :  */
       4             : 
       5             : #include "bgp/bgp_export.h"
       6             : 
       7             : #include <boost/bind/bind.hpp>
       8             : 
       9             : #include "bgp/bgp_ribout_updates.h"
      10             : #include "bgp/bgp_route.h"
      11             : #include "bgp/bgp_table.h"
      12             : #include "bgp/bgp_update.h"
      13             : #include "bgp/bgp_update_monitor.h"
      14             : #include "bgp/bgp_update_sender.h"
      15             : 
      16             : using namespace boost::placeholders;
      17             : 
      18       34927 : BgpExport::BgpExport(RibOut *ribout)
      19       34927 :     : ribout_(ribout) {
      20       34927 : }
      21             : 
      22             : //
      23             : // Check if the desired state as expressed by the UpdateInfoSList is exactly
      24             : // the same as the state already stored in the RouteUpdate.
      25             : //
      26             : // Return true if we have a duplicate, false otherwise.
      27             : //
      28        1808 : static bool IsDuplicate(const RouteUpdate *rt_update,
      29             :         const UpdateInfoSList *uinfo_slist) {
      30        1808 :     return rt_update->CompareUpdateInfo(*uinfo_slist);
      31             : }
      32             : 
      33             : //
      34             : // Export Processing.
      35             : // 1. Calculate the desired attributes (UpdateInfo list) via BgpTable::Export.
      36             : // 2. Dequeue the existing update if present.
      37             : //    a) If the current update is the same as desired update then the operation
      38             : //    is a NOP.
      39             : //    b) If there is a current update, then the code must obtain a lock on it
      40             : //    in order to make sure that the output process is not currently reading
      41             : //    and modifying its state.
      42             : // 3. Calculate the delta between previous state and new state.
      43             : // 4. Enqueue a new update at tail.
      44             : //
      45     1461960 : void BgpExport::Export(DBTablePartBase *root, DBEntryBase *db_entry) {
      46             :     RouteUpdate *rt_update;
      47     1461960 :     UpdateInfoSList uinfo_slist;
      48             : 
      49             :     // Calculate attributes by running through export policy.
      50     1461858 :     BgpRoute *route = static_cast<BgpRoute *>(db_entry);
      51     1461858 :     bool reach = false;
      52     1461858 :     if (!db_entry->IsDeleted() && !ribout_->PeerSet().empty()) {
      53      819044 :         reach = ribout_->table()->Export(ribout_, route, ribout_->PeerSet(),
      54             :                 uinfo_slist);
      55             :     }
      56     1462071 :     assert(!reach || !uinfo_slist->empty());
      57             : 
      58             :     // Find and dequeue any existing DBState.
      59     1462065 :     bool duplicate = false;
      60     1462065 :     RibOutUpdates *updates = ribout_->updates(root->index());
      61     1461959 :     RibUpdateMonitor *monitor = updates->monitor();
      62     1461939 :     DBState *dbstate = monitor->GetDBStateAndDequeue(db_entry,
      63             :             boost::bind(IsDuplicate, _1, &uinfo_slist),
      64             :             &duplicate);
      65             : 
      66             :     // Handle the DBState as appropriate.
      67     1462675 :     if (dbstate == NULL) {
      68             :         // A NULL DBState implies that we either have no previous state or
      69             :         // that the previously scheduled updates are duplicates of what we
      70             :         // want to send now.
      71             : 
      72             :         // Nothing to do if we are looking at duplicates.
      73      911349 :         if (duplicate)
      74         293 :             return;
      75             : 
      76             :         // If we have no previous state and the route is not reachable we
      77             :         // are done.
      78      911056 :         if (!reach)
      79      454944 :             return;
      80             : 
      81             :         // We have no previous state and the route is reachable.  Need to
      82             :         // schedule a new update.
      83      456112 :         rt_update = new RouteUpdate(route, RibOutUpdates::QUPDATE);
      84             :     } else {
      85             :         // The DBState in the DBEntryBase must be the same as what we found.
      86             :         // This is a paranoid check to make sure that GetDBStateAndDequeue
      87             :         // did not forget to update the DBState when handing a RouteUpdate
      88             :         // from the QBULK queue or when handling an UpdateList.
      89             :         const DBState *entry_db_state =
      90      551326 :             db_entry->GetState(root->parent(), ribout_->listener_id());
      91      551525 :         assert(entry_db_state == dbstate);
      92             : 
      93             :         // We got here because we have previous state, either a RouteState
      94             :         // or a RouteUpdate. Note that it cannot be an UpdateList since we
      95             :         // get rid of UpdateLists in GetDBStateAndDequeue and return either
      96             :         // the RouteUpdate for QUPDATE or a new RouteState with the history.
      97      551525 :         assert(dynamic_cast<UpdateList *>(dbstate) == NULL);
      98             : 
      99      551525 :         rt_update = dynamic_cast<RouteUpdate *>(dbstate);
     100      551525 :         if (rt_update == NULL)  {
     101             :             // Previous state is not a RouteUpdate, must be a RouteState.
     102      549854 :             RouteState *rstate = static_cast<RouteState *>(dbstate);
     103             : 
     104             :             // Bail if the new state that we want to schedule is identical
     105             :             // to what we have previously advertised. This can happen when
     106             :             // there are back to back changes to a route such that it goes
     107             :             // from state A to B and then back to A but the Export routine
     108             :             // never saw state B.
     109      549854 :             if (rstate->CompareUpdateInfo(uinfo_slist))
     110      112709 :                 return;
     111             : 
     112             :             // We need a new RouteUpdate to advertise the new state and/or
     113             :             // withdraw part or all of the previous state. Move history to
     114             :             // a new RouteUpdate and get rid of the RouteState.
     115      436991 :             rt_update = new RouteUpdate(route, RibOutUpdates::QUPDATE);
     116      436771 :             rstate->MoveHistory(rt_update);
     117      436678 :             delete rstate;
     118      436731 :             dbstate = NULL;
     119      436731 :             rstate = NULL;
     120             :         } else {
     121             :             // The RouteUpdate must be for QUPDATE. Any RouteUpdate that got
     122             :             // dequeued from QBULK is also converted to be for QUPDATE.
     123        1671 :             assert(rt_update->queue_id() == RibOutUpdates::QUPDATE);
     124             : 
     125             :             // The previous state is a RouteUpdate. Get rid of any scheduled
     126             :             // UpdateInfos since we have fresh new UpdateInfos to schedule.
     127             :             // Note that the history information is still in the RouteUpdate.
     128        1658 :             rt_update->ClearUpdateInfo();
     129             : 
     130             :             // If the history is empty and the route is not reachable, there
     131             :             // is nothing to withdraw. Get rid of the RouteUpdate and return.
     132        1659 :             if (rt_update->History()->empty() && !reach) {
     133          43 :                 db_entry->ClearState(root->parent(), ribout_->listener_id());
     134          43 :                 delete rt_update;
     135          43 :                 return;
     136             :             }
     137             :         }
     138             : 
     139             :         // The new UpdateInfos that we want to schedule may not cover all the
     140             :         // peers that we advertised state to previously. May need to generate
     141             :         // negative state for such peers based on the history in RouteUpdate.
     142      438347 :         rt_update->BuildNegativeUpdateInfo(uinfo_slist);
     143             : 
     144             :         // At this point we have a RouteUpdate with history information and
     145             :         // an UpdateInfoSList that contains the state that we are going to
     146             :         // schedule. There may be some commonality between them. We want to
     147             :         // trim redundant state in the UpdateInfoSList i.e. if some of it's
     148             :         // the same as what's already in the history.
     149      438178 :         rt_update->TrimRedundantUpdateInfo(uinfo_slist);
     150             : 
     151             :         // If there are no more UpdateInfos in the list, move the history to
     152             :         // a new RouteState and get rid of the RouteUpdate.  This can happen
     153             :         // if the route goes from state A to B, the Export routine sees B and
     154             :         // schedules updates but the state goes back to A before the updates
     155             :         // can be sent to anyone.
     156      438171 :         if (uinfo_slist->empty()) {
     157          36 :             RouteState *rstate = new RouteState();
     158          36 :             rt_update->MoveHistory(rstate);
     159          36 :             db_entry->SetState(root->parent(), ribout_->listener_id(), rstate);
     160          36 :             delete rt_update;
     161          36 :             return;
     162             :         }
     163             :     }
     164             : 
     165             :     // Associate the new UpdateInfos we want to send with the RouteUpdate
     166             :     // and enqueue the RouteUpdate.
     167      894053 :     assert(!uinfo_slist->empty());
     168      894020 :     rt_update->SetUpdateInfo(uinfo_slist);
     169      893977 :     updates->Enqueue(db_entry, rt_update);
     170     1462644 : }
     171             : 
     172             : //
     173             : // Join Processing.
     174             : // 1. Detect if we have've already sent or scheduled updates to the bitset of
     175             : //    peers for the QUPDATE queue.
     176             : // 2. Calculate the desired attributes (UpdateInfo list) via BgpTable::Export.
     177             : // 3. Create a new RouteUpdate for the QBULK queue and merge it with existing
     178             : //    state.
     179             : //
     180      448314 : bool BgpExport::Join(DBTablePartBase *root, const RibPeerSet &mjoin,
     181             :         DBEntryBase *db_entry) {
     182      448314 :     RibOutUpdates *updates = ribout_->updates(root->index());
     183      448297 :     RibUpdateMonitor *monitor = updates->monitor();
     184             : 
     185             :     // Bail if the route is already deleted.
     186      448277 :     if (db_entry->IsDeleted())
     187       48711 :         return true;
     188             : 
     189             :     // There may have been a route change before the walk gets to this route.
     190             :     // Trim mjoin by resetting mcurrent and mscheduled to prevent enqueueing
     191             :     // duplicate updates.
     192             :     //
     193             :     // TBD:: tweak this further to handle route refresh.
     194      399606 :     RibPeerSet mcurrent, mscheduled;
     195      399593 :     monitor->GetPeerSetCurrentAndScheduled(db_entry, RibOutUpdates::QUPDATE,
     196             :             &mcurrent, &mscheduled);
     197      399698 :     RibPeerSet mjoin_subset = mjoin;
     198      399594 :     mjoin_subset.Reset(mcurrent);
     199      399574 :     mjoin_subset.Reset(mscheduled);
     200      399587 :     if (mjoin_subset.empty()) {
     201      296676 :         return true;
     202             :     }
     203             : 
     204             :     // Run export policy to generate the update infos.
     205      102879 :     BgpRoute *route = static_cast<BgpRoute *>(db_entry);
     206      102879 :     UpdateInfoSList uinfo_slist;
     207      102880 :     bool reach = ribout_->table()->Export(ribout_, route, mjoin_subset,
     208             :             uinfo_slist);
     209      102945 :     assert(!reach || !uinfo_slist->empty());
     210      102944 :     if (!reach) {
     211       23909 :         return true;
     212             :     }
     213             : 
     214             :     // Create a new update.
     215       79035 :     RouteUpdate *rt_update = new RouteUpdate(route, RibOutUpdates::QBULK);
     216       79036 :     rt_update->SetUpdateInfo(uinfo_slist);
     217             : 
     218             :     // Merge the update into the BULK queue. If there is an entry present
     219             :     // already then the update info is merged.  Kick the BgpUpdateSender
     220             :     // machinery if needed.
     221       79038 :     bool need_tail_dequeue = monitor->MergeUpdate(db_entry, rt_update);
     222       79007 :     if (need_tail_dequeue) {
     223       78945 :         BgpUpdateSender *sender = ribout_->sender();
     224       78944 :         sender->RibOutActive(root->index(), ribout_, RibOutUpdates::QBULK);
     225             :     }
     226             : 
     227       79095 :     return true;
     228      399680 : }
     229             : 
     230             : //
     231             : // Leave Processing.
     232             : // 1. Detect if there's no history or scheduled updates for the bitset of
     233             : //    peers.
     234             : // 2. Remove any history or scheduled updates.
     235             : //
     236      448552 : bool BgpExport::Leave(DBTablePartBase *root, const RibPeerSet &mleave,
     237             :         DBEntryBase *db_entry) {
     238      448552 :     RibOutUpdates *updates = ribout_->updates(root->index());
     239      448558 :     RibUpdateMonitor *monitor = updates->monitor();
     240             : 
     241             :     // Nothing to do if there are no current or scheduled updates for any
     242             :     // peers in mleave.
     243      448546 :     RibPeerSet mcurrent, mscheduled;
     244      448565 :     monitor->GetPeerSetCurrentAndScheduled(db_entry, RibOutUpdates::QCOUNT,
     245             :             &mcurrent, &mscheduled);
     246      448563 :     RibPeerSet munion, mleave_subset;
     247      448518 :     munion.Set(mcurrent);
     248      448470 :     munion.Set(mscheduled);
     249      448437 :     mleave_subset.BuildIntersection(mleave, munion);
     250      448495 :     if (mleave_subset.empty()) {
     251      189127 :         return true;
     252             :     }
     253             : 
     254             :     // Cancel scheduled updates for the route and/or remove AdvertiseInfo
     255             :     // for current advertised state.
     256      259316 :     monitor->ClearPeerSetCurrentAndScheduled(db_entry, mleave_subset);
     257             : 
     258      259478 :     return true;
     259      448605 : }