Line data    Source code

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