Line data    Source code

       1             : /*
       2             :  * Copyright (c) 2015 Juniper Networks, Inc. All rights reserved.
       3             :  */
       4             : 
       5             : #ifndef SRC_BGP_ROUTING_POLICY_ROUTING_POLICY_H_
       6             : #define SRC_BGP_ROUTING_POLICY_ROUTING_POLICY_H_
       7             : 
       8             : #include <boost/scoped_ptr.hpp>
       9             : #include <boost/intrusive_ptr.hpp>
      10             : #include <boost/shared_ptr.hpp>
      11             : #include <sandesh/sandesh_trace.h>
      12             : 
      13             : #include <list>
      14             : #include <map>
      15             : #include <string>
      16             : #include <utility>
      17             : #include <vector>
      18             : #include <mutex>
      19             : #include <atomic>
      20             : 
      21             : #include "base/lifetime.h"
      22             : #include "base/util.h"
      23             : #include "bgp/bgp_common.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 RoutingPolicyMgr;
      32             : class BgpRoutingPolicyConfig;
      33             : class RoutingInstance;
      34             : class RoutingPolicyMatch;
      35             : class RoutingPolicyAction;
      36             : class RoutingPolicyTermConfig;
      37             : class TaskTrigger;
      38             : 
      39             : // Routing Policy Manager
      40             : // This class implements the routing policy for control node.
      41             : // It maintains the list of routing policies configured on the system
      42             : // It provides API to lookup the routing policy by name.
      43             : //
      44             : // A mutex is used to serialize access from multiple bgp::ConfigHelper tasks.
      45             : //
      46             : // It provides two APIs to apply routing policy on the routes belonging to given
      47             : // routing instance.
      48             : // 1. ApplyRoutingPolicy
      49             : //    Apply routing policy on the routing instance passed as input.
      50             : //    To achieve this Routing policy manager walks all the routing tables of
      51             : //    the routing instance. On each route encountered during the walk, policy
      52             : //    is evaluated using EvaluateRoutingPolicy. EvaluateRoutingPolicy visits
      53             : //    all the BgpPath and apply all routing policies of that routing instance
      54             : //    on that BgpPath.
      55             : //
      56             : // 2. ExecuteRoutingPolicy
      57             : //     This function is called on the given route + path from two code path.
      58             : //     First one is from InsertPath. i.e. when new path is being added to a
      59             : //     route.
      60             : //     Second path is from DBTable walk context while applying the routing
      61             : //     policy on routing instance.  This function calls the operator() of the
      62             : //     policy in input to match and apply the action on successful match.
      63             : //
      64             : //
      65             : // RoutingPolicyManager takes a delete reference of BgpServer.
      66             : //
      67             : // RoutingPolicy
      68             : //
      69             : // This represents one Routing Policy in operational data.
      70             : // Each routing policy has multiple policy terms (represented using PolicyTerm
      71             : // class) represented as ordered list using std::list.
      72             : //
      73             : // Routing Policy object takes lifetime reference of RoutingPolicyMgr.
      74             : //
      75             : // Reference to RoutingPolicy object is done using intrusive pointer which
      76             : // keeps track of ref_count.
      77             : // The DeleteActor of the RoutingPolicy uses this ref_count to allow/disallow
      78             : // delete of the RoutingPolicy object. On last dereference of the RoutingPolicy
      79             : // object, RetryDelete on the DeleteActor is triggered.
      80             : //
      81             : // RoutingPolicy is removed from the name-map in RoutingPolicyMgr  only in
      82             : // Destroy method of DeleteActor. It is possible that config might have revived
      83             : // the RoutingPolicy object with same name(with same or different config).
      84             : // In such case, RoutingPolicyMgr recreate the routing policy based on the
      85             : // new config object.
      86             : //
      87             : // RoutingPolicy object provided operator() to apply the policy on a
      88             : // BgpRoute+BgpPath. In this operator overload function, route is processed
      89             : // against each policy term till a terminal rule is encountered.
      90             : // A terminal rule is a term where action on successful match is to Reject or
      91             : // Accept the route. Return value gives the hint of result of policy apply.
      92             : // Result is represented as a pair with first element representing whether the
      93             : // match was for terminal rule and second element indicating whether there
      94             : // was a policy match.
      95             : //
      96             : // RoutingPolicy object is updated on config update function in UpdateConfig
      97             : // method. This method walks newly configured policy term list and existing
      98             : // policy term list and compares the PolicyTerm to see whether
      99             : //    a. Policy term matches (Done using operator==() function on PolicyTerm).
     100             : //       If no match is found, new PolicyTerm as per new config is created and
     101             : //       inserted in to ordered list of PolicyTerm.
     102             : //    b. New policy Term is inserted
     103             : //    c. Existing policy term is deleted
     104             : // At the end of the update, generation number of the policy term is updated to
     105             : // indicate config change to Routing Policy. Routing Instances referring to
     106             : // this policy is not triggered from this path. It is expected that
     107             : // BgpConfigListener infra would put the RoutingInstance to the change_list when
     108             : // the routing policy it is referring undergoes a change.
     109             : //
     110             : // Routing Instance
     111             : // Routing instance maintains ordered list of routing policies that it refers.
     112             : // This is represented as std::list of pair<RoutingPolicyPtr, gen-id of policy>.
     113             : // Please note RoutingPolicyPtr is an intrusive pointer to RoutingPolicy object.
     114             : //
     115             : // While processing the routing policies on each routes belonging to this
     116             : // instance, each of routing policies are applied till terminal rule is hit.
     117             : // BgpRoute is update with all policy actions from the matching policy term.
     118             : // Policy action is stored in BgpPath (in flag ond/or in BgpAttr)
     119             : //
     120             : // Update of the routing instance checks whether the routing policy list on the
     121             : // instance has changed. This process checks for following
     122             : //   a. If a routing policy order is update
     123             : //   b. If new routing policy(ies) are added to the routing policy list
     124             : //   c. If existing routing policy(ies) are removed from the routing policy list
     125             : //   d. If the routing policies that it is referring has undergone config change
     126             : //      This is done by checking the generation number of routing policy that
     127             : //      is applied on the routing instance.
     128             : // In case the routing policy is updated on the routing instance
     129             : // (if either of (a) to (d) above is true), all the BgpTables belonging to the
     130             : // routing instance is walked to reapply the routing policy.
     131             : //
     132             : // BgpRoute/BgpPath
     133             : // BgpPath maintains original BgpAttribute that it received in a new field
     134             : // called as original_attr_. The path attribute attr_ represents the
     135             : // BgpAttribute after applying the policy.
     136             : // New flag is introduced to indicate if the path is rejected by routing policy.
     137             : //
     138             : // PolicyTerm
     139             : // Policy Term has two ordered lists
     140             : //      1. Match conditions
     141             : //      2. Actions
     142             : //
     143             : // PolicyTerm class provides accessor method to get list of matches and actions.
     144             : // It also provides compare function (operator==()) to check whether two policy
     145             : // terms matches/same. It would return true if each policy term has same match
     146             : // set(ordered list) and same action list(ordered).
     147             : //
     148             : // Policy action is represented as ordered list of action to be taken on
     149             : // successful match. The top of the action list indicates what should be done
     150             : // with route on successful match. e.g. Accept/Reject/NextTerm.
     151             : // Subsequent entry in this list are the update action to be taken on policy
     152             : // match.
     153             : //
     154             : // Match Condition
     155             : // RoutingPolicyMatch is the abstract base class to implement a match condition.
     156             : // This abstract class provides Match() function to compare the route + Path
     157             : // attribute with match condition. The derived class provides implementation
     158             : // to compare the route + attribute with match condition. Another method of this
     159             : // class is comparator function operator==(). This method compares whether two
     160             : // match conditions are same. This is done by comparing the typeid() (RTTI) and
     161             : // calling IsEqual pure virtual method if type ids are same.
     162             : //
     163             : // All match conditions inherit this RoutingPolicyMatch and provide
     164             : // implementation of pure virtual methods.
     165             : // In the current release, match is supported on Community and prefix.
     166             : //
     167             : // MatchCommunity implements match for community value
     168             : // MatchPrefix provides templetized implementation for matching prefix.
     169             : // Currently PrefixMatchInet and PrefixMatchInet6 implementation is supported
     170             : // to match inet and inet6 routes.
     171             : //
     172             : // Policy Action
     173             : // RoutingPolicyAction is the abstract base class for implementing the policy
     174             : // action.
     175             : // Action is represented as
     176             : //      RoutingPolicyNexTermAction,
     177             : //      RoutingPolicyRejectAction,
     178             : //      RoutingPolicyAcceptAction or
     179             : //      RoutingPolicyUpdateAction
     180             : // This represents NextTerm, Reject, accept and route update action respectively
     181             : // RoutingPolicyRejectAction & RoutingPolicyAcceptAction as Terminal actions.
     182             : // RoutingPolicyNexTermAction and RoutingPolicyAcceptAction may/may not have
     183             : // RoutingPolicyUpdateAction associated with it.
     184             : // RoutingPolicyUpdateAction represents the modification done to path attribute
     185             : // on successful match.
     186             : // RoutingPolicyAction provides comparator function to check whether two actions
     187             : // are same. This is done by comparing the typeid() of the object and invoking
     188             : // IsEqual when typeid() is same.
     189             : // RoutingPolicyUpdateAction which inherits the RoutingPolicyAction provides the
     190             : // pure virtual method operator() to apply update action on BgpAttr.
     191             : // Currently support for updating the local-pref and community list is supported
     192             : // for update action.
     193             : // UpdateCommunity supports add/remove/set list of
     194             : // community to incoming BgpAttr.
     195             : //
     196             : class PolicyTerm {
     197             : public:
     198             :     typedef std::vector<RoutingPolicyAction *> ActionList;
     199             :     typedef std::vector<RoutingPolicyMatch *> MatchList;
     200             :     PolicyTerm();
     201             :     ~PolicyTerm();
     202             :     bool terminal() const;
     203             :     bool ApplyTerm(const BgpRoute *route,
     204             :                    const BgpPath *path, BgpAttr *attr) const;
     205         479 :     void set_actions(const ActionList &actions) {
     206         479 :         actions_ = actions;
     207         479 :     }
     208         479 :     void set_matches(const MatchList &matches) {
     209         479 :         matches_ = matches;
     210         479 :     }
     211        2685 :     const MatchList &matches() const {
     212        2685 :         return matches_;
     213             :     }
     214        4230 :     const ActionList &actions() const {
     215        4230 :         return actions_;
     216             :     }
     217             :     bool operator==(const PolicyTerm &term) const;
     218             : 
     219             : private:
     220             :     MatchList matches_;
     221             :     ActionList actions_;
     222             : };
     223             : 
     224             : class RoutingPolicy {
     225             : public:
     226             :     typedef boost::shared_ptr<PolicyTerm>  PolicyTermPtr;
     227             :     typedef std::list<PolicyTermPtr> RoutingPolicyTermList;
     228             :     typedef std::pair<bool, bool> PolicyResult;
     229             :     RoutingPolicy(std::string name, BgpServer *server,
     230             :                     RoutingPolicyMgr *mgr,
     231             :                     const BgpRoutingPolicyConfig *config);
     232             :     virtual ~RoutingPolicy();
     233             :     void ProcessConfig();
     234             :     void UpdateConfig(const BgpRoutingPolicyConfig *config);
     235             :     void ClearConfig();
     236             :     void Shutdown();
     237             : 
     238             :     bool MayDelete() const;
     239             :     void RetryDelete();
     240             :     void ManagedDelete();
     241             :     LifetimeActor *deleter();
     242             :     const LifetimeActor *deleter() const;
     243             :     bool deleted() const;
     244             : 
     245         285 :     const std::string &name() const { return name_; }
     246             :     const BgpRoutingPolicyConfig *config() const { return config_; }
     247             :     const RoutingPolicyMgr *manager() const { return mgr_; }
     248             : 
     249             :     BgpServer *server() { return server_; }
     250             :     const BgpServer *server() const { return server_; }
     251             : 
     252        1277 :     RoutingPolicyTermList *terms() { return &terms_; }
     253         777 :     const RoutingPolicyTermList &terms() const { return terms_; }
     254         198 :     void add_term(PolicyTermPtr term) {
     255         198 :         terms_.push_back(term);
     256         198 :     }
     257             : 
     258             :     PolicyResult operator()(const BgpRoute *route,
     259             :                             const BgpPath *path, BgpAttr *attr) const;
     260         286 :     uint32_t generation() const { return generation_; }
     261          13 :     uint32_t refcount() const { return refcount_; }
     262             : 
     263             : private:
     264             :     friend class RoutingPolicyMgr;
     265             :     class DeleteActor;
     266             :     friend void intrusive_ptr_add_ref(RoutingPolicy *policy);
     267             :     friend void intrusive_ptr_release(RoutingPolicy *policy);
     268             : 
     269             :     PolicyTermPtr BuildTerm(const RoutingPolicyTermConfig &term);
     270             :     std::string name_;
     271             :     BgpServer *server_;
     272             :     RoutingPolicyMgr *mgr_;
     273             :     const BgpRoutingPolicyConfig *config_;
     274             :     boost::scoped_ptr<DeleteActor> deleter_;
     275             :     LifetimeRef<RoutingPolicy> manager_delete_ref_;
     276             : 
     277             :     // Updated when routing policy undergoes a change
     278             :     std::atomic<uint32_t> refcount_;
     279             :     uint32_t generation_;
     280             :     RoutingPolicyTermList terms_;
     281             : };
     282             : 
     283        1731 : inline void intrusive_ptr_add_ref(RoutingPolicy *policy) {
     284        1731 :     policy->refcount_++;
     285        1731 :     return;
     286             : }
     287             : 
     288        1731 : inline void intrusive_ptr_release(RoutingPolicy *policy) {
     289        1731 :     int prev = policy->refcount_.fetch_sub(1);
     290        1731 :     if (prev == 1) {
     291         163 :         if (policy->MayDelete())
     292         163 :             policy->RetryDelete();
     293             :     }
     294        1731 : }
     295             : 
     296             : class RoutingPolicyMgr {
     297             : public:
     298             :     typedef std::map<std::string, RoutingPolicy*> RoutingPolicyList;
     299             :     typedef RoutingPolicyList::iterator name_iterator;
     300             :     typedef RoutingPolicyList::const_iterator const_name_iterator;
     301             :     typedef std::map<BgpTable *,
     302             :             DBTable::DBTableWalkRef> RoutingPolicyWalkRequests;
     303             : 
     304             :     explicit RoutingPolicyMgr(BgpServer *server);
     305             :     virtual ~RoutingPolicyMgr();
     306             :     SandeshTraceBufferPtr trace_buffer() const { return trace_buf_; }
     307             : 
     308             :     name_iterator name_begin() { return routing_policies_.begin(); }
     309           0 :     name_iterator name_end() { return routing_policies_.end(); }
     310             :     name_iterator name_lower_bound(const std::string &name) {
     311             :         return routing_policies_.lower_bound(name);
     312             :     }
     313             :     const_name_iterator name_cbegin() { return routing_policies_.begin(); }
     314          22 :     const_name_iterator name_cend() { return routing_policies_.end(); }
     315           6 :     const_name_iterator name_clower_bound(const std::string &name) {
     316           6 :         return routing_policies_.lower_bound(name);
     317             :     }
     318             : 
     319         647 :     RoutingPolicy *GetRoutingPolicy(const std::string &name) {
     320         647 :         name_iterator it;
     321         647 :         if ((it = routing_policies_.find(name)) != routing_policies_.end()) {
     322         486 :             return it->second;
     323             :         }
     324         161 :         return NULL;
     325             :     }
     326             :     const RoutingPolicy *GetRoutingPolicy(const std::string &name) const {
     327             :         const_name_iterator it;
     328             :         if ((it = routing_policies_.find(name)) != routing_policies_.end()) {
     329             :             return it->second;
     330             :         }
     331             :         return NULL;
     332             :     }
     333             : 
     334             :     virtual RoutingPolicy *CreateRoutingPolicy(
     335             :                              const BgpRoutingPolicyConfig *config);
     336             :     void UpdateRoutingPolicy(const BgpRoutingPolicyConfig *config);
     337             :     virtual void DeleteRoutingPolicy(const std::string &name);
     338             : 
     339             : 
     340             :     bool deleted();
     341             :     void ManagedDelete();
     342             : 
     343             :     void DestroyRoutingPolicy(RoutingPolicy *policy);
     344             : 
     345             :     size_t count() const { return routing_policies_.size(); }
     346          43 :     BgpServer *server() { return server_; }
     347             :     const BgpServer *server() const { return server_; }
     348             :     LifetimeActor *deleter();
     349             : 
     350             :     RoutingPolicy::PolicyResult ExecuteRoutingPolicy(
     351             :         const RoutingPolicy *policy, const BgpRoute *route,
     352             :         const BgpPath *path, BgpAttr *attr) const;
     353             : 
     354             :     // Update the routing policy list on attach point
     355             :     bool UpdateRoutingPolicyList(const RoutingPolicyConfigList &cfg_list,
     356             :                                        RoutingPolicyAttachList *oper_list);
     357             : 
     358             :     // RoutingInstance is updated with new set of policies. This function
     359             :     // applies that policy on each route of this routing instance
     360             :     void ApplyRoutingPolicy(RoutingInstance *instance);
     361             : 
     362             :     void RequestWalk(BgpTable *table);
     363             :     void WalkDone(DBTableBase *dbtable);
     364             :     bool EvaluateRoutingPolicy(DBTablePartBase *root, DBEntryBase *entry);
     365             : 
     366             : private:
     367             :     class DeleteActor;
     368             : 
     369             :     BgpServer *server_;
     370             :     std::mutex mutex_;
     371             :     RoutingPolicyList routing_policies_;
     372             :     boost::scoped_ptr<DeleteActor> deleter_;
     373             :     LifetimeRef<RoutingPolicyMgr> server_delete_ref_;
     374             :     RoutingPolicyWalkRequests routing_policy_sync_;
     375             :     SandeshTraceBufferPtr trace_buf_;
     376             : };
     377             : 
     378             : #endif  // SRC_BGP_ROUTING_POLICY_ROUTING_POLICY_H_