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_ROUTEPATH_REPLICATOR_H_
       7             : #define SRC_BGP_ROUTING_INSTANCE_ROUTEPATH_REPLICATOR_H_
       8             : 
       9             : #include <boost/ptr_container/ptr_map.hpp>
      10             : #include <sandesh/sandesh_trace.h>
      11             : 
      12             : #include <atomic>
      13             : #include <list>
      14             : #include <map>
      15             : #include <set>
      16             : #include <string>
      17             : #include <vector>
      18             : #include <mutex>
      19             : 
      20             : #include "base/lifetime.h"
      21             : #include "base/util.h"
      22             : #include "bgp/bgp_path.h"
      23             : #include "db/db_entry.h"
      24             : #include "db/db_table.h"
      25             : 
      26             : class BgpRoute;
      27             : class BgpServer;
      28             : class BgpTable;
      29             : class RtGroup;
      30             : class RoutePathReplicator;
      31             : class RouteTarget;
      32             : 
      33             : //
      34             : // This keeps track of a RoutePathReplicator's listener state for a BgpTable.
      35             : // An instance is created for each VRF table and for the VPN table.
      36             : //
      37             : // An entry for VPN table is created when RoutePathReplicator is initialized.
      38             : // An entry for a VRF table is created when processing a Join for the first
      39             : // export route target for the VRF.
      40             : // TableState is removed when a Bgp table is deleted.
      41             : // TableState takes a delete reference to the BgpTable and DeleteActor of the
      42             : // TableState manages the unregister of this listener from the BgpTable and
      43             : // delete of TableState object.
      44             : //
      45             : // A TableState entry keeps track of all the export route targets for a VRF
      46             : // by maintaining the GroupList. TableState cannot be deleted if GroupList
      47             : // is non-empty and table has replicated routes. Replicated routes are tracked
      48             : // using the DBStateCount of this listener
      49             : //
      50             : class TableState {
      51             : public:
      52             :     typedef std::set<RtGroup *> GroupList;
      53             : 
      54             :     TableState(RoutePathReplicator *replicator, BgpTable *table);
      55             :     ~TableState();
      56             : 
      57             :     void ManagedDelete();
      58             :     bool MayDelete() const;
      59             :     void RetryDelete();
      60             : 
      61             :     LifetimeActor *deleter();
      62             :     const LifetimeActor *deleter() const;
      63             :     bool deleted() const;
      64             : 
      65             :     void AddGroup(RtGroup *group);
      66             :     void RemoveGroup(RtGroup *group);
      67             :     const RtGroup *FindGroup(RtGroup *group) const;
      68           4 :     bool empty() const { return list_.empty(); }
      69             : 
      70             :     // Generation of the table's export route target list, bumped on every
      71             :     // change to it. Replication compares it against the value recorded in
      72             :     // RtReplicated to tell whether the paths replicated earlier still carry
      73             :     // the current targets. Written from the config tasks, read from
      74             :     // db::DBTable.
      75     4019852 :     uint64_t export_target_gen() const { return export_target_gen_.load(); }
      76      477304 :     void bump_export_target_gen() { ++export_target_gen_; }
      77             : 
      78     4633749 :     DBTableBase::ListenerId listener_id() const { return listener_id_; }
      79      254194 :     void set_listener_id(DBTableBase::ListenerId listener_id) {
      80      254194 :         assert(listener_id_ == DBTableBase::kInvalidId);
      81      254194 :         listener_id_ = listener_id;
      82      254194 :     }
      83             : 
      84             :     uint32_t route_count() const;
      85             : 
      86      508442 :     RoutePathReplicator *replicator() {
      87      508442 :         return replicator_;
      88             :     }
      89             : 
      90             :     const RoutePathReplicator *replicator() const {
      91             :         return replicator_;
      92             :     }
      93             : 
      94           2 :     BgpTable *table() const {
      95           2 :         return table_;
      96             :     }
      97             : 
      98      276828 :     BgpTable *table() {
      99      276828 :         return table_;
     100             :     }
     101             : 
     102      276928 :     const DBTable::DBTableWalkRef &walk_ref() const {
     103      276928 :         return walk_ref_;
     104             :     }
     105             : 
     106      356817 :     DBTable::DBTableWalkRef &walk_ref() {
     107      356817 :         return walk_ref_;
     108             :     }
     109             : 
     110       22603 :     void set_walk_ref(DBTable::DBTableWalkRef walk_ref) {
     111       22603 :         walk_ref_ = walk_ref;
     112       22603 :     }
     113             : 
     114             : private:
     115             :     class DeleteActor;
     116             :     RoutePathReplicator *replicator_;
     117             :     BgpTable *table_;
     118             :     DBTableBase::ListenerId listener_id_;
     119             :     boost::scoped_ptr<DeleteActor> deleter_;
     120             :     LifetimeRef<TableState> table_delete_ref_;
     121             :     GroupList list_;
     122             :     std::atomic<uint64_t> export_target_gen_;
     123             :     DBTable::DBTableWalkRef walk_ref_;
     124             : 
     125             :     DISALLOW_COPY_AND_ASSIGN(TableState);
     126             : };
     127             : 
     128             : //
     129             : // This keeps track of the replication state for a route in the primary table.
     130             : // The ReplicatedRtPathList is a set of SecondaryRouteInfo, where each element
     131             : // represents a secondary path in a secondary table. An entry is added to the
     132             : // set when a path is replicated to a secondary table removed when it's not
     133             : // replicated anymore.
     134             : //
     135             : // Changes to ReplicatedRtPathList may be triggered by changes in the primary
     136             : // route, changes in the export targets of the primary table or changes in the
     137             : // import targets of secondary tables.
     138             : //
     139             : // A RtReplicated is deleted when the route in the primary table is no longer
     140             : // replicated to any secondary tables.
     141             : //
     142             : class RtReplicated : public DBState {
     143             : public:
     144             :     struct SecondaryRouteInfo {
     145             :     public:
     146             :         BgpTable *table_;
     147             :         const IPeer *peer_;
     148             :         uint32_t path_id_;
     149             :         BgpPath::PathSource  src_;
     150             :         BgpRoute *rt_;
     151             : 
     152      956042 :         SecondaryRouteInfo(BgpTable *table, const IPeer *peer,
     153             :             uint32_t path_id, BgpPath::PathSource src, BgpRoute *rt)
     154      956042 :             : table_(table),
     155      956042 :               peer_(peer),
     156      956042 :               path_id_(path_id),
     157      956042 :               src_(src),
     158      956042 :               rt_(rt) {
     159      956042 :         }
     160     4027053 :         int CompareTo(const SecondaryRouteInfo &rhs) const {
     161     4027053 :             KEY_COMPARE(table_, rhs.table_);
     162     1025089 :             KEY_COMPARE(peer_, rhs.peer_);
     163      887273 :             KEY_COMPARE(path_id_, rhs.path_id_);
     164      876225 :             KEY_COMPARE(src_, rhs.src_);
     165      876225 :             KEY_COMPARE(rt_, rhs.rt_);
     166      874954 :             return 0;
     167             :         }
     168     3587633 :         bool operator<(const SecondaryRouteInfo &rhs) const {
     169     3587633 :             return (CompareTo(rhs) < 0);
     170             :         }
     171      440247 :         bool operator>(const SecondaryRouteInfo &rhs) const {
     172      440247 :             return (CompareTo(rhs) > 0);
     173             :         }
     174             : 
     175             :         std::string ToString() const;
     176             :     };
     177             : 
     178             :     typedef std::set<SecondaryRouteInfo> ReplicatedRtPathList;
     179             : 
     180             :     explicit RtReplicated(RoutePathReplicator *replicator);
     181             : 
     182             :     void AddRouteInfo(BgpTable *table, BgpRoute *rt,
     183             :         ReplicatedRtPathList::const_iterator it);
     184             :     void DeleteRouteInfo(BgpTable *table, BgpRoute *rt,
     185             :         ReplicatedRtPathList::const_iterator it);
     186             : 
     187     1447361 :     const ReplicatedRtPathList &GetList() const { return replicate_list_; }
     188     1446794 :     ReplicatedRtPathList *GetMutableList() { return &replicate_list_; }
     189             :     std::vector<std::string> GetTableNameList(const BgpPath *path) const;
     190             : 
     191             :     // TableState::export_target_gen of the primary table as of the last time
     192             :     // the route was replicated.
     193          86 :     uint64_t export_target_gen() const { return export_target_gen_; }
     194     1292334 :     void set_export_target_gen(uint64_t gen) { export_target_gen_ = gen; }
     195             : 
     196             : private:
     197             :     RoutePathReplicator *replicator_;
     198             :     ReplicatedRtPathList replicate_list_;
     199             :     uint64_t export_target_gen_;
     200             : };
     201             : 
     202             : //
     203             : // This class implements functionality to import and export BgpPaths between
     204             : // VRF BgpTables and a VPN BgpTable for a given address family. The exporting
     205             : // table is referred to as the primary table and the importing tables are
     206             : // referred to as secondary tables.
     207             : //
     208             : // The rules for importing and exporting paths are based on route targets of
     209             : // the VRF tables and the route targets in VPN routes. They can be summarized
     210             : // as follows:
     211             : //
     212             : // o The VPN table unconditionally imports routes from all VRF tables.
     213             : // o The VPN table potentially exports routes to all VRF tables.
     214             : // o A path in a VRF table is considered to have export targets of the table.
     215             : // o A path in the VPN table has route targets in it's attributes.
     216             : // o A path in a primary table is imported into a secondary table if one or
     217             : // o more of the targets for the path is in the list of import targets for
     218             : //   the secondary table.
     219             : // o Secondary paths are never exported to other secondary tables.
     220             : //
     221             : // Dependency tracking mechanisms are needed to implement replication in an
     222             : // an efficient manner. RoutePathReplicator does the following:
     223             : //
     224             : // 1. When an export target is added to or removed from a VRF table, walk all
     225             : //    routes in the VRF table to re-evaluate the new set of secondary paths.
     226             : //    The DBTableWalkMgr provides this functionality.
     227             : // 2. When an import target is added to or removed from a VRF table, walk all
     228             : //    VRF tables that have the target in question as an export target.  The
     229             : //    list of tables that export a target is maintained in the RTargetGroupMgr.
     230             : //    This list is updated by the replicator (by calling RTargetGroupMgr APIs)
     231             : //    based on configuration changes in the routing instance.
     232             : // 3. When an import target is added to or removed from a VRF tables, walk all
     233             : //    VPN routes with the target in question.  This dependency is maintained
     234             : //    by RTargetGroupMgr.
     235             : // 4. When a route is updated, calculate new set of secondary paths by going
     236             : //    through all VRF tables that import one of the targets for the route in
     237             : //    question.  The list of VRF tables is obtained from the RTargetGroupMgr.
     238             : // 5. When a route is updated, remove secondary paths that are not required
     239             : //    anymore.  The list of previous secondary paths for a primary route is
     240             : //    maintained using RtReplicated and reconciled/synchronized with the new
     241             : //    list obtained from 4.
     242             : //
     243             : // The TableStateList keeps track of the TableState for each VRF from which
     244             : // routes could be exported. It also has an entry for the TableState for the
     245             : // VPN table. This entry is created when the replicator is initialized and
     246             : // deleted during shutdown.
     247             : //
     248             : // The UnregTableList keeps track of tables for which we need to delete the
     249             : // TableState. Requests are enqueued from the db::DBTable task when a table
     250             : // walk finishes and the TableState is empty.
     251             : //
     252             : // A mutex is used to serialize access from multiple bgp::ConfigHelper tasks.
     253             : //
     254             : class RoutePathReplicator {
     255             : public:
     256             :     RoutePathReplicator(BgpServer *server, Address::Family family);
     257             :     virtual ~RoutePathReplicator();
     258             : 
     259             :     void Initialize();
     260             :     void Join(BgpTable *table, const RouteTarget &rt, bool import);
     261             :     void Leave(BgpTable *table, const RouteTarget &rt, bool import);
     262             : 
     263             :     std::vector<std::string> GetReplicatedTableNameList(const BgpTable *table,
     264             :         const BgpRoute *route, const BgpPath *path) const;
     265             :     const RtReplicated *GetReplicationState(BgpTable *table,
     266             :                                             BgpRoute *rt) const;
     267             : 
     268             : private:
     269             :     friend class ReplicationTest;
     270             :     friend class BGPaaSRDTest;
     271             :     friend class RtReplicated;
     272             :     friend class TableState;
     273             : 
     274             :     typedef std::map<BgpTable *, TableState *> TableStateList;
     275             :     typedef std::set<BgpTable *> UnregTableList;
     276             : 
     277             :     void RequestWalk(BgpTable *table);
     278             :     void BulkReplicationDone(DBTableBase *dbtable);
     279             :     bool UnregisterTables();
     280             : 
     281             :     TableState *AddTableState(BgpTable *table, RtGroup *group = NULL);
     282             :     void RemoveTableState(BgpTable *table, RtGroup *group);
     283             :     void DeleteTableState(BgpTable *table);
     284             :     void UnregisterTableState(BgpTable *table);
     285             :     TableState *FindTableState(BgpTable *table);
     286             :     const TableState *FindTableState(const BgpTable *table) const;
     287             : 
     288             :     void JoinVpnTable(RtGroup *group);
     289             :     void LeaveVpnTable(RtGroup *group);
     290             : 
     291             :     bool RouteListener(TableState *ts, DBTablePartBase *root,
     292             :                        DBEntryBase *entry);
     293             :     void DeleteSecondaryPath(BgpTable  *table, BgpRoute *rt,
     294             :                              const RtReplicated::SecondaryRouteInfo &rtinfo);
     295             :     void DBStateSync(BgpTable *table, TableState *ts, BgpRoute *rt,
     296             :                      RtReplicated *dbstate,
     297             :                      const RtReplicated::ReplicatedRtPathList *future);
     298             : 
     299     9075568 :     BgpServer *server() { return server_; }
     300     8056421 :     Address::Family family() const { return family_; }
     301             :     const BgpServer *server() const { return server_; }
     302             : 
     303             :     BgpServer *server_;
     304             :     std::mutex mutex_;
     305             :     TableStateList table_state_list_;
     306             :     Address::Family family_;
     307             :     BgpTable *vpn_table_;
     308             :     SandeshTraceBufferPtr trace_buf_;
     309             : 
     310             :     DISALLOW_COPY_AND_ASSIGN(RoutePathReplicator);
     311             : };
     312             : 
     313             : #endif  // SRC_BGP_ROUTING_INSTANCE_ROUTEPATH_REPLICATOR_H_