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       34970 : BgpExport::BgpExport(RibOut *ribout)
      19       34970 :     : ribout_(ribout) {
      20       34970 : }
      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        1615 : static bool IsDuplicate(const RouteUpdate *rt_update,
      29             :         const UpdateInfoSList *uinfo_slist) {
      30        1615 :     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     1429819 : void BgpExport::Export(DBTablePartBase *root, DBEntryBase *db_entry) {
      46             :     RouteUpdate *rt_update;
      47     1429819 :     UpdateInfoSList uinfo_slist;
      48             : 
      49             :     // Calculate attributes by running through export policy.
      50     1429839 :     BgpRoute *route = static_cast<BgpRoute *>(db_entry);
      51     1429839 :     bool reach = false;
      52     1429839 :     if (!db_entry->IsDeleted() && !ribout_->PeerSet().empty()) {
      53      812607 :         reach = ribout_->table()->Export(ribout_, route, ribout_->PeerSet(),
      54             :                 uinfo_slist);
      55             :     }
      56     1430044 :     assert(!reach || !uinfo_slist->empty());
      57             : 
      58             :     // Find and dequeue any existing DBState.
      59     1430041 :     bool duplicate = false;
      60     1430041 :     RibOutUpdates *updates = ribout_->updates(root->index());
      61     1430000 :     RibUpdateMonitor *monitor = updates->monitor();
      62     1429966 :     DBState *dbstate = monitor->GetDBStateAndDequeue(db_entry,
      63             :             boost::bind(IsDuplicate, _1, &uinfo_slist),
      64             :             &duplicate);
      65             : 
      66             :     // Handle the DBState as appropriate.
      67     1430529 :     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      887766 :         if (duplicate)
      74         291 :             return;
      75             : 
      76             :         // If we have no previous state and the route is not reachable we
      77             :         // are done.
      78      887475 :         if (!reach)
      79      431717 :             return;
      80             : 
      81             :         // We have no previous state and the route is reachable.  Need to
      82             :         // schedule a new update.
      83      455758 :         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      542763 :             db_entry->GetState(root->parent(), ribout_->listener_id());
      91      542875 :         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      542875 :         assert(dynamic_cast<UpdateList *>(dbstate) == NULL);
      98             : 
      99      542875 :         rt_update = dynamic_cast<RouteUpdate *>(dbstate);
     100      542875 :         if (rt_update == NULL)  {
     101             :             // Previous state is not a RouteUpdate, must be a RouteState.
     102      541403 :             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      541403 :             if (rstate->CompareUpdateInfo(uinfo_slist))
     110      108708 :                 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      432579 :             rt_update = new RouteUpdate(route, RibOutUpdates::QUPDATE);
     116      432459 :             rstate->MoveHistory(rt_update);
     117      432362 :             delete rstate;
     118      432387 :             dbstate = NULL;
     119      432387 :             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        1472 :             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        1454 :             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        1454 :             if (rt_update->History()->empty() && !reach) {
     133          41 :                 db_entry->ClearState(root->parent(), ribout_->listener_id());
     134          41 :                 delete rt_update;
     135          41 :                 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      433800 :         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      433683 :         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      433658 :         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      889282 :     assert(!uinfo_slist->empty());
     168      889288 :     rt_update->SetUpdateInfo(uinfo_slist);
     169      889211 :     updates->Enqueue(db_entry, rt_update);
     170     1430471 : }
     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      450296 : bool BgpExport::Join(DBTablePartBase *root, const RibPeerSet &mjoin,
     181             :         DBEntryBase *db_entry) {
     182      450296 :     RibOutUpdates *updates = ribout_->updates(root->index());
     183      450281 :     RibUpdateMonitor *monitor = updates->monitor();
     184             : 
     185             :     // Bail if the route is already deleted.
     186      450270 :     if (db_entry->IsDeleted())
     187       44852 :         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      405447 :     RibPeerSet mcurrent, mscheduled;
     195      405464 :     monitor->GetPeerSetCurrentAndScheduled(db_entry, RibOutUpdates::QUPDATE,
     196             :             &mcurrent, &mscheduled);
     197      405619 :     RibPeerSet mjoin_subset = mjoin;
     198      405542 :     mjoin_subset.Reset(mcurrent);
     199      405477 :     mjoin_subset.Reset(mscheduled);
     200      405482 :     if (mjoin_subset.empty()) {
     201      302662 :         return true;
     202             :     }
     203             : 
     204             :     // Run export policy to generate the update infos.
     205      102797 :     BgpRoute *route = static_cast<BgpRoute *>(db_entry);
     206      102797 :     UpdateInfoSList uinfo_slist;
     207      102802 :     bool reach = ribout_->table()->Export(ribout_, route, mjoin_subset,
     208             :             uinfo_slist);
     209      102898 :     assert(!reach || !uinfo_slist->empty());
     210      102897 :     if (!reach) {
     211       23783 :         return true;
     212             :     }
     213             : 
     214             :     // Create a new update.
     215       79114 :     RouteUpdate *rt_update = new RouteUpdate(route, RibOutUpdates::QBULK);
     216       79110 :     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       79108 :     bool need_tail_dequeue = monitor->MergeUpdate(db_entry, rt_update);
     222       79087 :     if (need_tail_dequeue) {
     223       78919 :         BgpUpdateSender *sender = ribout_->sender();
     224       78918 :         sender->RibOutActive(root->index(), ribout_, RibOutUpdates::QBULK);
     225             :     }
     226             : 
     227       79134 :     return true;
     228      405579 : }
     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      450565 : bool BgpExport::Leave(DBTablePartBase *root, const RibPeerSet &mleave,
     237             :         DBEntryBase *db_entry) {
     238      450565 :     RibOutUpdates *updates = ribout_->updates(root->index());
     239      450562 :     RibUpdateMonitor *monitor = updates->monitor();
     240             : 
     241             :     // Nothing to do if there are no current or scheduled updates for any
     242             :     // peers in mleave.
     243      450557 :     RibPeerSet mcurrent, mscheduled;
     244      450568 :     monitor->GetPeerSetCurrentAndScheduled(db_entry, RibOutUpdates::QCOUNT,
     245             :             &mcurrent, &mscheduled);
     246      450587 :     RibPeerSet munion, mleave_subset;
     247      450528 :     munion.Set(mcurrent);
     248      450473 :     munion.Set(mscheduled);
     249      450451 :     mleave_subset.BuildIntersection(mleave, munion);
     250      450460 :     if (mleave_subset.empty()) {
     251      185823 :         return true;
     252             :     }
     253             : 
     254             :     // Cancel scheduled updates for the route and/or remove AdvertiseInfo
     255             :     // for current advertised state.
     256      264625 :     monitor->ClearPeerSetCurrentAndScheduled(db_entry, mleave_subset);
     257             : 
     258      264849 :     return true;
     259      450672 : }