Line data    Source code

       1             : /*
       2             :  * Copyright (c) 2013 Juniper Networks, Inc. All rights reserved.
       3             :  */
       4             : 
       5             : #ifndef SRC_BGP_ROUTING_INSTANCE_PATH_RESOLVER_H_
       6             : #define SRC_BGP_ROUTING_INSTANCE_PATH_RESOLVER_H_
       7             : 
       8             : #include <boost/scoped_ptr.hpp>
       9             : #include <tbb/spin_rw_mutex.h>
      10             : 
      11             : #include <map>
      12             : #include <set>
      13             : #include <string>
      14             : #include <vector>
      15             : #include <utility>
      16             : #include <mutex>
      17             : 
      18             : #include "base/lifetime.h"
      19             : #include "base/util.h"
      20             : #include "base/address.h"
      21             : #include "bgp/bgp_condition_listener.h"
      22             : #include "db/db_entry.h"
      23             : #include "db/db_table.h"
      24             : 
      25             : class BgpAttr;
      26             : class BgpPath;
      27             : class BgpRoute;
      28             : class BgpServer;
      29             : class BgpTable;
      30             : class DBEntryBase;
      31             : class DBTablePartBase;
      32             : class DeleteActor;
      33             : class IPeer;
      34             : class PathResolverPartition;
      35             : class ResolverNexthop;
      36             : class ResolverPath;
      37             : class ResolverRouteState;
      38             : class RoutingInstance;
      39             : class ShowPathResolver;
      40             : class TaskTrigger;
      41             : 
      42             : //
      43             : // This represents an instance of the resolver per BgpTable. A BgpTable that
      44             : // with BgpPaths that need resolution will have an instance of PathResolver.
      45             : //
      46             : // The [Start|Update|Stop]PathResolution APIs are invoked by PathResolution
      47             : // clients explicitly as required. They have to be invoked in context of the
      48             : // db::DBTable Task.
      49             : //
      50             : // The listener_id is used by ResolverPath to set ResolverRouteState on the
      51             : // BgpRoute for the BgpPaths in question. The PathResolver doesn't actually
      52             : // listen to notifications for routes in the BgpTable.
      53             : //
      54             : // The nexthop map keeps track of all ResolverNexthop for this instance. In
      55             : // addition, a given ResolverNexthop may be on the register/unregister list
      56             : // and the update list. Entries are added to the map and the lists from the
      57             : // db::DBTable Task. A mutex is used to serialize updates to the map and the
      58             : // lists. Note that there's no no concurrent access when entries are removed
      59             : // from the map and the lists, since the remove operations happen from Tasks
      60             : // that are mutually exclusive.
      61             : //
      62             : // The register/unregister list is processed in the context of bgp::Config
      63             : // Task. ResolverNexthops are added to this list when we need to add/remove
      64             : // or unregister them to/from the BgpConditionListener. This is done since
      65             : // the BgpConditionListener expects these operations to be made in context
      66             : // of bgp::Config Task.
      67             : //
      68             : // When a ResolverNexthop is removed the BgpConditionListener, it is added
      69             : // to the delete list. This is required because remove call is asynchronous.
      70             : // When BgpConditionListener invokes the remove request done callback, the
      71             : // ResolverNexthop is added to the register/unregister list again. It gets
      72             : // erased from the delete list and unregistered from BgpConditionListener
      73             : // after the list is processed again.
      74             : //
      75             : // The update list is processed in the context of bgp::ResolverNexthop Task.
      76             : // When an entry on this list is processed all it's dependent ResolverPaths
      77             : // are queued for re-evaluation in the PathResolverPartition.
      78             : //
      79             : // Concurrency Notes:
      80             : //
      81             : // Resolution APIs are invoked from db::DBTable Task.
      82             : // Updates to ResolverNexthop (via Match method) happen from db::DBTable Task.
      83             : // ResolverNexthop register/unregister list is processed in bgp::Config Task.
      84             : // ResolverNexthop update is processed in bgp::ResolverNexthop Task.
      85             : // ResolverPath update is processed in bgp::ResolverPath Task.
      86             : //
      87             : // bgp::Config is mutually exclusive with bgp::ResolverPath
      88             : // bgp::Config is mutually exclusive with bgp::ResolverNexthop
      89             : // db::DBTable is mutually exclusive with bgp::ResolverPath
      90             : // db::DBTable is mutually exclusive with bgp::ResolverNexthop
      91             : // bgp::ResolverPath is mutually exclusive with bgp::ResolverNexthop
      92             : //
      93             : class PathResolver {
      94             : public:
      95             :     explicit PathResolver(BgpTable *table);
      96             :     ~PathResolver();
      97             : 
      98             :     void StartPathResolution(BgpRoute *route, const BgpPath *path,
      99             :         BgpTable *nh_table = NULL);
     100             :     void StopPathResolution(int part_id, const BgpPath *path);
     101             : 
     102             :     ResolverRouteState *FindResolverRouteState(BgpRoute *route);
     103             :     ResolverRouteState *LocateResolverRouteState(BgpRoute *route);
     104             : 
     105      380348 :     BgpTable *table() { return table_; }
     106             :     Address::Family family() const;
     107        2714 :     DBTableBase::ListenerId listener_id() const { return listener_id_; }
     108             :     BgpConditionListener *get_condition_listener(Address::Family family);
     109             :     bool IsDeleted() const;
     110             :     void ManagedDelete();
     111             :     bool MayDelete() const;
     112             :     void RetryDelete();
     113       51449 :     bool nexthop_longest_match() const { return nexthop_longest_match_; }
     114       42922 :     void set_nexthop_longest_match(bool flag) { nexthop_longest_match_ = flag; }
     115             : 
     116             :     void FillShowInfo(ShowPathResolver *spr, bool summary) const;
     117             :     static bool RoutePrefixMatch(const BgpRoute *route,
     118             :                                  const IpAddress &address);
     119             : 
     120             : private:
     121             :     friend class PathResolverPartition;
     122             :     friend class ResolverNexthop;
     123             :     template <typename U> friend class PathResolverTest;
     124             : 
     125             :     class DeleteActor;
     126             :     typedef std::pair<IpAddress, BgpTable *> ResolverNexthopKey;
     127             :     typedef std::map<ResolverNexthopKey, ResolverNexthop *> ResolverNexthopMap;
     128             :     typedef std::set<ResolverNexthop *> ResolverNexthopList;
     129             : 
     130             :     PathResolverPartition *GetPartition(int part_id);
     131             :     PathResolverPartition *GetPartition(int part_id) const;
     132             : 
     133             :     ResolverNexthop *LocateResolverNexthop(IpAddress address, BgpTable *table);
     134             :     void RemoveResolverNexthop(ResolverNexthop *rnexthop);
     135             :     void UpdateResolverNexthop(ResolverNexthop *rnexthop);
     136             :     void RegisterUnregisterResolverNexthop(ResolverNexthop *rnexthop);
     137             : 
     138             :     void UnregisterResolverNexthopDone(BgpTable *table, ConditionMatch *match);
     139             :     bool ProcessResolverNexthopRegUnreg(ResolverNexthop *rnexthop);
     140             :     bool ProcessResolverNexthopRegUnregList();
     141             :     bool ProcessResolverNexthopUpdateList();
     142             : 
     143             :     bool RouteListener(DBTablePartBase *root, DBEntryBase *entry);
     144             : 
     145             :     size_t GetResolverNexthopMapSize() const;
     146             :     size_t GetResolverNexthopDeleteListSize() const;
     147             : 
     148             :     void DisableResolverNexthopRegUnregProcessing();
     149             :     void EnableResolverNexthopRegUnregProcessing();
     150             :     size_t GetResolverNexthopRegUnregListSize() const;
     151             : 
     152             :     void DisableResolverNexthopUpdateProcessing();
     153             :     void EnableResolverNexthopUpdateProcessing();
     154             :     size_t GetResolverNexthopUpdateListSize() const;
     155             : 
     156             :     void DisableResolverPathUpdateProcessing();
     157             :     void EnableResolverPathUpdateProcessing();
     158             :     void PauseResolverPathUpdateProcessing();
     159             :     void ResumeResolverPathUpdateProcessing();
     160             :     size_t GetResolverPathUpdateListSize() const;
     161             : 
     162             :     BgpTable *table_;
     163             :     DBTableBase::ListenerId listener_id_;
     164             :     bool nexthop_longest_match_;
     165             :     mutable std::mutex mutex_;
     166             :     ResolverNexthopMap nexthop_map_;
     167             :     ResolverNexthopList nexthop_reg_unreg_list_;
     168             :     boost::scoped_ptr<TaskTrigger> nexthop_reg_unreg_trigger_;
     169             :     ResolverNexthopList nexthop_update_list_;
     170             :     boost::scoped_ptr<TaskTrigger> nexthop_update_trigger_;
     171             :     ResolverNexthopList nexthop_delete_list_;
     172             :     std::vector<PathResolverPartition *> partitions_;
     173             : 
     174             :     boost::scoped_ptr<DeleteActor> deleter_;
     175             :     LifetimeRef<PathResolver> table_delete_ref_;
     176             : 
     177             :     DISALLOW_COPY_AND_ASSIGN(PathResolver);
     178             : };
     179             : 
     180             : //
     181             : // This represents one partition in the PathResolver. It keeps tracks of all
     182             : // the ResolverPaths for BgpRoutes in the partition. It has a map of BgpPath
     183             : // to ResolverPath.
     184             : //
     185             : // The update list contains ResolverPaths whose resolved BgpPath list need to
     186             : // be updated. Entries are added to the list as described in the comments for
     187             : // ResolverPath class. The list is processed in context of bgp::ResolverPath
     188             : // Task with the partition index as the Task instance id. This allows all the
     189             : // PathResolverPartitions to work concurrently.
     190             : 
     191             : // Mutual exclusion of db::DBTable and bgp::ResolverPath Tasks ensures that
     192             : // it's safe to add/delete/update resolved BgpPaths from the bgp::ResolverPath
     193             : // Task. It also ensures that it's safe to access the BgpPaths of the nexthop
     194             : // BgpRoute from the bgp::ResolverPath Task. The only exception is where the
     195             : // BgpRoute itself is being modified by another bgp::ResolverPath Task. This
     196             : // is handled by using a read-write mutex in the ResolverRouteState.
     197             : //
     198             : class PathResolverPartition {
     199             : public:
     200             :     PathResolverPartition(int part_id, PathResolver *resolver);
     201             :     ~PathResolverPartition();
     202             : 
     203             :     void StartPathResolution(BgpRoute *route, const BgpPath *path,
     204             :         BgpTable *nh_table);
     205             :     void StopPathResolution(const BgpPath *path);
     206             : 
     207             :     void TriggerPathResolution(ResolverPath *rpath);
     208             :     void DeferPathResolution(ResolverPath *rpath);
     209             : 
     210        6086 :     int part_id() const { return part_id_; }
     211             :     DBTableBase::ListenerId listener_id() const {
     212             :         return resolver_->listener_id();
     213             :     }
     214        3043 :     PathResolver *resolver() const { return resolver_; }
     215       34430 :     BgpTable *table() const { return resolver_->table(); }
     216             :     DBTablePartBase *table_partition();
     217             : 
     218             : private:
     219             :     friend class PathResolver;
     220             : 
     221             :     typedef std::map<const BgpPath *, ResolverPath *> PathToResolverPathMap;
     222             :     typedef std::set<ResolverPath *> ResolverPathList;
     223             : 
     224             :     ResolverPath *CreateResolverPath(const BgpPath *path, BgpRoute *route,
     225             :         ResolverNexthop *rnexthop);
     226             :     ResolverPath *FindResolverPath(const BgpPath *path);
     227             :     ResolverPath *RemoveResolverPath(const BgpPath *path);
     228             :     bool ProcessResolverPathUpdateList();
     229             : 
     230             :     void DisableResolverPathUpdateProcessing();
     231             :     void EnableResolverPathUpdateProcessing();
     232             :     void PauseResolverPathUpdateProcessing();
     233             :     void ResumeResolverPathUpdateProcessing();
     234             :     size_t GetResolverPathUpdateListSize() const;
     235             : 
     236             :     int part_id_;
     237             :     PathResolver *resolver_;
     238             :     PathToResolverPathMap rpath_map_;
     239             :     ResolverPathList rpath_update_list_;
     240             :     boost::scoped_ptr<TaskTrigger> rpath_update_trigger_;
     241             : 
     242             :     DISALLOW_COPY_AND_ASSIGN(PathResolverPartition);
     243             : };
     244             : 
     245             : //
     246             : // This is used to take a reference on a BgpRoute with at least one BgpPath
     247             : // that is being resolved by the PathResolver. Each ResolverPath for the
     248             : // BgpRoute in question has an intrusive pointer to the ResolverRouteState.
     249             : //
     250             : // The refcount doesn't need to be atomic because it's updated/accessed from
     251             : // exactly one DBPartition or PathResolverPartition.
     252             : //
     253             : // The rw_mutex is used to prevent a PathResolverPartition from modifying the
     254             : // associated BgpRoute while another PathResolverPartition is accessing the
     255             : // BgpRoute. This can happen when there's more than 1 levels of resolution in
     256             : // use i.e. a BgpRoute with resolved paths is itself being used to resolve a
     257             : // nexthop. Note that the two PathResolverPartitions could be in the same or
     258             : // different PathResolvers.
     259             : //
     260             : class ResolverRouteState : public DBState {
     261             : public:
     262             :     ResolverRouteState(PathResolver *resolver, BgpRoute *route);
     263             :     virtual ~ResolverRouteState();
     264       11817 :     tbb::spin_rw_mutex &rw_mutex() { return rw_mutex_; }
     265             : 
     266             : private:
     267             :     friend void intrusive_ptr_add_ref(ResolverRouteState *state);
     268             :     friend void intrusive_ptr_release(ResolverRouteState *state);
     269             : 
     270             :     PathResolver *resolver_;
     271             :     BgpRoute *route_;
     272             :     tbb::spin_rw_mutex rw_mutex_;
     273             :     uint32_t refcount_;
     274             : };
     275             : 
     276        3043 : inline void intrusive_ptr_add_ref(ResolverRouteState *state) {
     277        3043 :     state->refcount_++;
     278        3043 : }
     279             : 
     280        3043 : inline void intrusive_ptr_release(ResolverRouteState *state) {
     281        3043 :     assert(state->refcount_ != 0);
     282        3043 :     if (--state->refcount_ == 0)
     283        1357 :         delete state;
     284        3043 : }
     285             : 
     286             : typedef boost::intrusive_ptr<ResolverRouteState> ResolverRouteStatePtr;
     287             : 
     288             : //
     289             : // This represents a BgpPath for which resolution has been requested. It's
     290             : // inserted into a map keyed by BgpPath pointer in a PathResolverPartition.
     291             : //
     292             : // If the client requests an update the ResolverPath is inserted into an
     293             : // update list in the PathResolverPartition. Similarly, if there's a change
     294             : // in the underlying BgpRoute for the ResolverNexthop, all of the impacted
     295             : // ResolverPaths are added to the update list in the PathResolverPartition.
     296             : // The latter happens when the ResolverNexthop update list in PathResolver
     297             : // is processed.
     298             : //
     299             : // A ResolverPath keeps a list of resolved BgpPaths it has added. A resolved
     300             : // path is added for each ecmp eligible BgpPath of the BgpRoute that tracks
     301             : // the nexthop of ResolverPath. The nexthop is represented by ResolverNexthop.
     302             : //
     303             : // The resolved paths of the ResolverPath are reconciled when the update list
     304             : // in the PathResolverPartition is processed. New resolved paths may get added,
     305             : // existing resolved paths may get updated and stale resolved paths could get
     306             : // deleted.
     307             : //
     308             : // The attributes of a resolved BgpPath are a combination of the attributes
     309             : // of the original BgpPath and the BgpPath of the nexthop being tracked. As a
     310             : // general rule, forwarding information (e.g. nexthop address, label, tunnel
     311             : // encapsulation) is obtained from tracking BgpPath while routing information
     312             : // (e.g. communities, as path, local pref) is obtained from original BgpPath.
     313             : //
     314             : class ResolverPath {
     315             : public:
     316             :     ResolverPath(PathResolverPartition *partition, const BgpPath *path,
     317             :         BgpRoute *route, ResolverNexthop *rnexthop);
     318             :     ~ResolverPath();
     319             : 
     320             :     bool UpdateResolvedPaths();
     321             : 
     322             :     PathResolverPartition *partition() const { return partition_; }
     323          96 :     BgpRoute *route() const { return route_; }
     324          96 :     const ResolverNexthop *rnexthop() const { return rnexthop_; }
     325        3042 :     void clear_path() { path_ = NULL; }
     326          96 :     size_t resolved_path_count() const { return resolved_path_list_.size(); }
     327             : 
     328             : private:
     329             :     typedef std::set<BgpPath *> ResolvedPathList;
     330             : 
     331             :     void AddResolvedPath(ResolvedPathList::const_iterator it);
     332             :     void DeleteResolvedPath(ResolvedPathList::const_iterator it);
     333             :     BgpPath *LocateResolvedPath(const IPeer *peer, uint32_t path_id,
     334             :         const BgpAttr *attr, uint32_t label, bool is_replicated = false);
     335             : 
     336             :     PathResolverPartition *partition_;
     337             :     const BgpPath *path_;
     338             :     BgpRoute *route_;
     339             :     ResolverNexthop *rnexthop_;
     340             :     ResolverRouteStatePtr state_;
     341             :     ResolvedPathList resolved_path_list_;
     342             : 
     343             :     DISALLOW_COPY_AND_ASSIGN(ResolverPath);
     344             : };
     345             : 
     346             : //
     347             : // This represents a nexthop IP address to be resolved using the specified
     348             : // BgpTable. This need not be the BgpTable associated with the PathResolver.
     349             : // Each ResolverNexthop is inserted into a map keyed by ResolverNexthopKey
     350             : // in the PathResolver.
     351             : //
     352             : // A ResolverNexthop is created when resolution is requested for the first
     353             : // BgpPath with the associated IP address. At creation, the ResolverNexthop
     354             : // is added to the PathResolver's registration/unregistration list so that
     355             : // the ConditionMatch can be added to the BgpConditionListener. This list
     356             : // gets processed in the context of the bgp::Config Task.
     357             : //
     358             : // A ResolverNexthop maintains a vector of ResolverPathList, one entry per
     359             : // partition. Each ResolverPathList is a set of ResolverPaths that use the
     360             : // ResolverNexthop in question. When there's a change to the BgpRoute for
     361             : // the IP address being tracked, the ResolverNexthop is added to the update
     362             : // list in the PathResolver. The PathResolver processes the entries in this
     363             : // list in the context of the bgp::ResolverNexthop Task. The action is to
     364             : // trigger re-evaluation of all ResolverPaths that use the ResolverNexthop.
     365             : //
     366             : // When the last ResolverPath in a partition using a ResolverNexthop gets
     367             : // removed, the ResolverNexthop is added to the registration/unregistration
     368             : // in the PathResolver. The list is processed in the bgp::Config Task. If
     369             : // the ResolverNexthop is empty i.e. not being used by any ResolverPaths,
     370             : // the ConditionMatch is removed from the BgpConditionListener and is also
     371             : // erased from the map in the PathResolver. When the remove done callback
     372             : // gets invoked from BgpConditionListener, the ResolverNexthop is added to
     373             : // the register/unregistration list again. It's finally unregistered when
     374             : // the list is processed again.
     375             : //
     376             : // The registered flag keeps track of whether the ResolverNexthop has been
     377             : // registered with the BgpConditionListener.  It's needed to handle corner
     378             : // cases where a ResolverNexthop gets added to registration/unregistration
     379             : // list but all ResolverPaths using it get removed before the ResolverNexthop
     380             : // has been registered.
     381             : //
     382             : // A set of pointers to all BgpRoutes that match IpAddress is maintained in a
     383             : // set so that the PathResolverPartition can access their BgpPaths. A reference
     384             : // to each BgpRoute in the set is kept by setting ConditionMatchState for the
     385             : // route. This set is sorted in descending order based on the prefix length so
     386             : // that longest matching route is always positioned at the beginning of the set.
     387             : // All operations to the set are protected by a mutex.
     388             : //
     389             : // A delete reference to BgpTable is maintained to ensure that the BgpTable
     390             : // does not get destroyed while there are ResolverNexthops tracking it.
     391             : //
     392             : class ResolverNexthop : public ConditionMatch {
     393             : public:
     394             :     ResolverNexthop(PathResolver *resolver, IpAddress address, BgpTable *table);
     395             :     virtual ~ResolverNexthop();
     396             : 
     397             :     virtual std::string ToString() const;
     398             :     virtual bool Match(BgpServer *server, BgpTable *table, BgpRoute *route,
     399             :         bool deleted);
     400             :     void AddResolverPath(int part_id, ResolverPath *rpath);
     401             :     void RemoveResolverPath(int part_id, ResolverPath *rpath);
     402             :     ResolverRouteState *GetResolverRouteState();
     403             : 
     404             :     void TriggerAllResolverPaths() const;
     405             : 
     406         104 :     void ManagedDelete() { }
     407             : 
     408        1299 :     IpAddress address() const { return address_; }
     409       17155 :     BgpTable *table() const { return table_; }
     410             :     bool InsertRoute(BgpRoute *route);
     411             :     bool RemoveRoute(BgpRoute *route);
     412             :     const BgpRoute *GetRoute() const;
     413             :     BgpRoute *GetRoute();
     414             :     bool empty() const;
     415        5334 :     bool registered() const { return registered_; }
     416        1175 :     void set_registered() { registered_ = true; }
     417             : 
     418             : protected:
     419             :     struct ResolverRouteCompare {
     420             :         bool operator()(const BgpRoute *lhs, const BgpRoute *rhs) const;
     421             :     };
     422             :     typedef std::set<BgpRoute *, ResolverRouteCompare> ResolverRouteSet;
     423             : 
     424             :     ResolverRouteSet routes_;
     425             : 
     426             : private:
     427             :     typedef std::set<ResolverPath *> ResolverPathList;
     428             : 
     429             :     PathResolver *resolver_;
     430             :     IpAddress address_;
     431             :     BgpTable *table_;
     432             :     bool registered_;
     433             :     mutable std::mutex routes_mutex_;
     434             :     std::vector<ResolverPathList> rpath_lists_;
     435             :     LifetimeRef<ResolverNexthop> table_delete_ref_;
     436             : 
     437             :     DISALLOW_COPY_AND_ASSIGN(ResolverNexthop);
     438             : };
     439             : 
     440             : #endif  // SRC_BGP_ROUTING_INSTANCE_PATH_RESOLVER_H_