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