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_export.h"
       7             : 
       8             : #include <boost/bind/bind.hpp>
       9             : 
      10             : #include "bgp/bgp_ribout_updates.h"
      11             : #include "bgp/bgp_route.h"
      12             : #include "bgp/bgp_table.h"
      13             : #include "bgp/bgp_update.h"
      14             : #include "bgp/bgp_update_monitor.h"
      15             : #include "bgp/bgp_update_sender.h"
      16             : 
      17             : using namespace boost::placeholders;
      18             : 
      19       34970 : BgpExport::BgpExport(RibOut *ribout)
      20       34970 :     : ribout_(ribout) {
      21       34970 : }
      22             : 
      23             : //
      24             : // Check if the desired state as expressed by the UpdateInfoSList is exactly
      25             : // the same as the state already stored in the RouteUpdate.
      26             : //
      27             : // Return true if we have a duplicate, false otherwise.
      28             : //
      29        1760 : static bool IsDuplicate(const RouteUpdate *rt_update,
      30             :         const UpdateInfoSList *uinfo_slist) {
      31        1760 :     return rt_update->CompareUpdateInfo(*uinfo_slist);
      32             : }
      33             : 
      34             : //
      35             : // Export Processing.
      36             : // 1. Calculate the desired attributes (UpdateInfo list) via BgpTable::Export.
      37             : // 2. Dequeue the existing update if present.
      38             : //    a) If the current update is the same as desired update then the operation
      39             : //    is a NOP.
      40             : //    b) If there is a current update, then the code must obtain a lock on it
      41             : //    in order to make sure that the output process is not currently reading
      42             : //    and modifying its state.
      43             : // 3. Calculate the delta between previous state and new state.
      44             : // 4. Enqueue a new update at tail.
      45             : //
      46     1472758 : void BgpExport::Export(DBTablePartBase *root, DBEntryBase *db_entry) {
      47             :     RouteUpdate *rt_update;
      48     1472758 :     UpdateInfoSList uinfo_slist;
      49             : 
      50             :     // Calculate attributes by running through export policy.
      51     1472799 :     BgpRoute *route = static_cast<BgpRoute *>(db_entry);
      52     1472799 :     bool reach = false;
      53     1472799 :     if (!db_entry->IsDeleted() && !ribout_->PeerSet().empty()) {
      54      817255 :         reach = ribout_->table()->Export(ribout_, route, ribout_->PeerSet(),
      55             :                 uinfo_slist);
      56             :     }
      57     1473001 :     assert(!reach || !uinfo_slist->empty());
      58             : 
      59             :     // Find and dequeue any existing DBState.
      60     1473009 :     bool duplicate = false;
      61     1473009 :     RibOutUpdates *updates = ribout_->updates(root->index());
      62     1472946 :     RibUpdateMonitor *monitor = updates->monitor();
      63     1472939 :     DBState *dbstate = monitor->GetDBStateAndDequeue(db_entry,
      64             :             boost::bind(IsDuplicate, _1, &uinfo_slist),
      65             :             &duplicate);
      66             : 
      67             :     // Handle the DBState as appropriate.
      68     1473762 :     if (dbstate == NULL) {
      69             :         // A NULL DBState implies that we either have no previous state or
      70             :         // that the previously scheduled updates are duplicates of what we
      71             :         // want to send now.
      72             : 
      73             :         // Nothing to do if we are looking at duplicates.
      74      926352 :         if (duplicate)
      75         290 :             return;
      76             : 
      77             :         // If we have no previous state and the route is not reachable we
      78             :         // are done.
      79      926062 :         if (!reach)
      80      469717 :             return;
      81             : 
      82             :         // We have no previous state and the route is reachable.  Need to
      83             :         // schedule a new update.
      84      456345 :         rt_update = new RouteUpdate(route, RibOutUpdates::QUPDATE);
      85             :     } else {
      86             :         // The DBState in the DBEntryBase must be the same as what we found.
      87             :         // This is a paranoid check to make sure that GetDBStateAndDequeue
      88             :         // did not forget to update the DBState when handing a RouteUpdate
      89             :         // from the QBULK queue or when handling an UpdateList.
      90             :         const DBState *entry_db_state =
      91      547410 :             db_entry->GetState(root->parent(), ribout_->listener_id());
      92      547518 :         assert(entry_db_state == dbstate);
      93             : 
      94             :         // We got here because we have previous state, either a RouteState
      95             :         // or a RouteUpdate. Note that it cannot be an UpdateList since we
      96             :         // get rid of UpdateLists in GetDBStateAndDequeue and return either
      97             :         // the RouteUpdate for QUPDATE or a new RouteState with the history.
      98      547518 :         assert(dynamic_cast<UpdateList *>(dbstate) == NULL);
      99             : 
     100      547518 :         rt_update = dynamic_cast<RouteUpdate *>(dbstate);
     101      547518 :         if (rt_update == NULL)  {
     102             :             // Previous state is not a RouteUpdate, must be a RouteState.
     103      545911 :             RouteState *rstate = static_cast<RouteState *>(dbstate);
     104             : 
     105             :             // Bail if the new state that we want to schedule is identical
     106             :             // to what we have previously advertised. This can happen when
     107             :             // there are back to back changes to a route such that it goes
     108             :             // from state A to B and then back to A but the Export routine
     109             :             // never saw state B.
     110      545911 :             if (rstate->CompareUpdateInfo(uinfo_slist))
     111      112040 :                 return;
     112             : 
     113             :             // We need a new RouteUpdate to advertise the new state and/or
     114             :             // withdraw part or all of the previous state. Move history to
     115             :             // a new RouteUpdate and get rid of the RouteState.
     116      433710 :             rt_update = new RouteUpdate(route, RibOutUpdates::QUPDATE);
     117      433524 :             rstate->MoveHistory(rt_update);
     118      433456 :             delete rstate;
     119      433486 :             dbstate = NULL;
     120      433486 :             rstate = NULL;
     121             :         } else {
     122             :             // The RouteUpdate must be for QUPDATE. Any RouteUpdate that got
     123             :             // dequeued from QBULK is also converted to be for QUPDATE.
     124        1607 :             assert(rt_update->queue_id() == RibOutUpdates::QUPDATE);
     125             : 
     126             :             // The previous state is a RouteUpdate. Get rid of any scheduled
     127             :             // UpdateInfos since we have fresh new UpdateInfos to schedule.
     128             :             // Note that the history information is still in the RouteUpdate.
     129        1595 :             rt_update->ClearUpdateInfo();
     130             : 
     131             :             // If the history is empty and the route is not reachable, there
     132             :             // is nothing to withdraw. Get rid of the RouteUpdate and return.
     133        1595 :             if (rt_update->History()->empty() && !reach) {
     134          44 :                 db_entry->ClearState(root->parent(), ribout_->listener_id());
     135          44 :                 delete rt_update;
     136          44 :                 return;
     137             :             }
     138             :         }
     139             : 
     140             :         // The new UpdateInfos that we want to schedule may not cover all the
     141             :         // peers that we advertised state to previously. May need to generate
     142             :         // negative state for such peers based on the history in RouteUpdate.
     143      435037 :         rt_update->BuildNegativeUpdateInfo(uinfo_slist);
     144             : 
     145             :         // At this point we have a RouteUpdate with history information and
     146             :         // an UpdateInfoSList that contains the state that we are going to
     147             :         // schedule. There may be some commonality between them. We want to
     148             :         // trim redundant state in the UpdateInfoSList i.e. if some of it's
     149             :         // the same as what's already in the history.
     150      434917 :         rt_update->TrimRedundantUpdateInfo(uinfo_slist);
     151             : 
     152             :         // If there are no more UpdateInfos in the list, move the history to
     153             :         // a new RouteState and get rid of the RouteUpdate.  This can happen
     154             :         // if the route goes from state A to B, the Export routine sees B and
     155             :         // schedules updates but the state goes back to A before the updates
     156             :         // can be sent to anyone.
     157      434935 :         if (uinfo_slist->empty()) {
     158          36 :             RouteState *rstate = new RouteState();
     159          36 :             rt_update->MoveHistory(rstate);
     160          36 :             db_entry->SetState(root->parent(), ribout_->listener_id(), rstate);
     161          36 :             delete rt_update;
     162          36 :             return;
     163             :         }
     164             :     }
     165             : 
     166             :     // Associate the new UpdateInfos we want to send with the RouteUpdate
     167             :     // and enqueue the RouteUpdate.
     168      891119 :     assert(!uinfo_slist->empty());
     169      891098 :     rt_update->SetUpdateInfo(uinfo_slist);
     170      891064 :     updates->Enqueue(db_entry, rt_update);
     171     1473528 : }
     172             : 
     173             : //
     174             : // Join Processing.
     175             : // 1. Detect if we have've already sent or scheduled updates to the bitset of
     176             : //    peers for the QUPDATE queue.
     177             : // 2. Calculate the desired attributes (UpdateInfo list) via BgpTable::Export.
     178             : // 3. Create a new RouteUpdate for the QBULK queue and merge it with existing
     179             : //    state.
     180             : //
     181      453700 : bool BgpExport::Join(DBTablePartBase *root, const RibPeerSet &mjoin,
     182             :         DBEntryBase *db_entry) {
     183      453700 :     RibOutUpdates *updates = ribout_->updates(root->index());
     184      453689 :     RibUpdateMonitor *monitor = updates->monitor();
     185             : 
     186             :     // Bail if the route is already deleted.
     187      453678 :     if (db_entry->IsDeleted())
     188       43604 :         return true;
     189             : 
     190             :     // There may have been a route change before the walk gets to this route.
     191             :     // Trim mjoin by resetting mcurrent and mscheduled to prevent enqueueing
     192             :     // duplicate updates.
     193             :     //
     194             :     // TBD:: tweak this further to handle route refresh.
     195      410096 :     RibPeerSet mcurrent, mscheduled;
     196      410128 :     monitor->GetPeerSetCurrentAndScheduled(db_entry, RibOutUpdates::QUPDATE,
     197             :             &mcurrent, &mscheduled);
     198      410176 :     RibPeerSet mjoin_subset = mjoin;
     199      410125 :     mjoin_subset.Reset(mcurrent);
     200      410075 :     mjoin_subset.Reset(mscheduled);
     201      410096 :     if (mjoin_subset.empty()) {
     202      305607 :         return true;
     203             :     }
     204             : 
     205             :     // Run export policy to generate the update infos.
     206      104462 :     BgpRoute *route = static_cast<BgpRoute *>(db_entry);
     207      104462 :     UpdateInfoSList uinfo_slist;
     208      104471 :     bool reach = ribout_->table()->Export(ribout_, route, mjoin_subset,
     209             :             uinfo_slist);
     210      104538 :     assert(!reach || !uinfo_slist->empty());
     211      104549 :     if (!reach) {
     212       25142 :         return true;
     213             :     }
     214             : 
     215             :     // Create a new update.
     216       79407 :     RouteUpdate *rt_update = new RouteUpdate(route, RibOutUpdates::QBULK);
     217       79397 :     rt_update->SetUpdateInfo(uinfo_slist);
     218             : 
     219             :     // Merge the update into the BULK queue. If there is an entry present
     220             :     // already then the update info is merged.  Kick the BgpUpdateSender
     221             :     // machinery if needed.
     222       79402 :     bool need_tail_dequeue = monitor->MergeUpdate(db_entry, rt_update);
     223       79346 :     if (need_tail_dequeue) {
     224       79318 :         BgpUpdateSender *sender = ribout_->sender();
     225       79317 :         sender->RibOutActive(root->index(), ribout_, RibOutUpdates::QBULK);
     226             :     }
     227             : 
     228       79427 :     return true;
     229      410176 : }
     230             : 
     231             : //
     232             : // Leave Processing.
     233             : // 1. Detect if there's no history or scheduled updates for the bitset of
     234             : //    peers.
     235             : // 2. Remove any history or scheduled updates.
     236             : //
     237      453910 : bool BgpExport::Leave(DBTablePartBase *root, const RibPeerSet &mleave,
     238             :         DBEntryBase *db_entry) {
     239      453910 :     RibOutUpdates *updates = ribout_->updates(root->index());
     240      453900 :     RibUpdateMonitor *monitor = updates->monitor();
     241             : 
     242             :     // Nothing to do if there are no current or scheduled updates for any
     243             :     // peers in mleave.
     244      453900 :     RibPeerSet mcurrent, mscheduled;
     245      453963 :     monitor->GetPeerSetCurrentAndScheduled(db_entry, RibOutUpdates::QCOUNT,
     246             :             &mcurrent, &mscheduled);
     247      453960 :     RibPeerSet munion, mleave_subset;
     248      453966 :     munion.Set(mcurrent);
     249      453889 :     munion.Set(mscheduled);
     250      453827 :     mleave_subset.BuildIntersection(mleave, munion);
     251      453824 :     if (mleave_subset.empty()) {
     252      192716 :         return true;
     253             :     }
     254             : 
     255             :     // Cancel scheduled updates for the route and/or remove AdvertiseInfo
     256             :     // for current advertised state.
     257      261099 :     monitor->ClearPeerSetCurrentAndScheduled(db_entry, mleave_subset);
     258             : 
     259      261326 :     return true;
     260      454042 : }