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_BGP_RIBOUT_H_
       7             : #define SRC_BGP_BGP_RIBOUT_H_
       8             : 
       9             : #include <boost/scoped_ptr.hpp>
      10             : #include <boost/intrusive/slist.hpp>
      11             : 
      12             : #include <algorithm>
      13             : #include <string>
      14             : #include <vector>
      15             : 
      16             : #include "base/bitset.h"
      17             : #include "base/index_map.h"
      18             : #include "bgp/bgp_attr.h"
      19             : #include "bgp/bgp_proto.h"
      20             : #include "bgp/bgp_rib_policy.h"
      21             : #include "db/db_entry.h"
      22             : #include "net/tunnel_encap_type.h"
      23             : 
      24             : class IPeer;
      25             : class IPeerUpdate;
      26             : class RibOutUpdates;
      27             : class ShowRibOutStatistics;
      28             : class BgpTable;
      29             : class BgpExport;
      30             : class BgpRoute;
      31             : class BgpUpdateSender;
      32             : class RouteUpdate;
      33             : class UpdateInfoSList;
      34             : 
      35             : //
      36             : // This class represents the attributes for a ribout entry, including the
      37             : // label.  It is essentially a combination of a smart pointer to BgpAttr
      38             : // and a label. The label is not included in BgpAttr in order to maximize
      39             : // sharing of the BgpAttr.
      40             : //
      41             : class RibOutAttr {
      42             : public:
      43             :     // This nested class represents an ecmp element for a ribout entry. A
      44             :     // ribout entry keeps a vector of these elements. Each element stores
      45             :     // all per nexthop properties in addition to the nexthop address and
      46             :     // label.
      47             :     //
      48             :     // The origin_vn_index keeps track of the index of the VN from which
      49             :     // the BgpPath originated.  A value of -1 means that the VN is unknown.
      50             :     class NextHop {
      51             :         public:
      52             :             NextHop(const BgpTable *table, IpAddress address,
      53             :                 const MacAddress &mac, uint32_t label, uint32_t l3_label,
      54             :                 const ExtCommunity *ext_community,
      55             :                 const LargeCommunity *large_community, bool vrf_originated);
      56             : 
      57      540315 :             const IpAddress address() const { return address_; }
      58        9091 :             const MacAddress &mac() const { return mac_; }
      59      695851 :             uint32_t label() const { return label_; }
      60       11719 :             uint32_t l3_label() const { return l3_label_; }
      61             :             const Ip4Address &source_address() const { return source_address_; }
      62     1069446 :             int origin_vn_index() const { return origin_vn_index_; }
      63      962356 :             std::vector<std::string> encap() const { return encap_; }
      64      540592 :             std::vector<uint64_t> tag_list() const { return tag_list_; }
      65             : 
      66             :             int CompareTo(const NextHop &rhs) const;
      67             :             bool operator==(const NextHop &rhs) const;
      68             :             bool operator!=(const NextHop &rhs) const;
      69             :             bool operator<(const NextHop &rhs) const;
      70             : 
      71             :         private:
      72             :             IpAddress address_;
      73             :             MacAddress mac_;
      74             :             uint32_t label_;
      75             :             uint32_t l3_label_;
      76             :             Ip4Address source_address_;
      77             :             int origin_vn_index_;
      78             :             std::vector<std::string> encap_;
      79             :             std::vector<uint64_t> tag_list_;
      80             :     };
      81             : 
      82             :     typedef std::vector<NextHop> NextHopList;
      83             : 
      84             :     RibOutAttr();
      85             :     RibOutAttr(const RibOutAttr &rhs);
      86             :     RibOutAttr(const BgpRoute *route, const BgpAttr *attr, bool is_xmpp);
      87             :     RibOutAttr(const BgpTable *table, const BgpAttr *attr, uint32_t label,
      88             :         uint32_t l3_label = 0, bool is_xmpp = false);
      89             :     RibOutAttr(const BgpTable *table, const BgpRoute *route,
      90             :         const BgpAttr *attr, uint32_t label, bool include_nh = true,
      91             :         bool is_xmpp = false);
      92             : 
      93             :     RibOutAttr &operator=(const RibOutAttr &rhs);
      94      647733 :     bool operator==(const RibOutAttr &rhs) const { return CompareTo(rhs) == 0; }
      95      454042 :     bool operator!=(const RibOutAttr &rhs) const { return CompareTo(rhs) != 0; }
      96     6157427 :     bool IsReachable() const { return attr_out_.get() != NULL; }
      97             : 
      98     2166925 :     const NextHopList &nexthop_list() const { return nexthop_list_; }
      99     8239236 :     const BgpAttr *attr() const { return attr_out_.get(); }
     100        8614 :     void set_attr(const BgpTable *table, const BgpAttrPtr &attrp) {
     101        8614 :         set_attr(table, attrp, 0, 0, false, false);
     102        8614 :     }
     103          80 :     void set_attr(const BgpTable *table, const BgpAttrPtr &attrp,
     104             :         uint32_t label) {
     105          80 :         set_attr(table, attrp, label, 0, false, false);
     106          80 :     }
     107             :     void set_attr(const BgpTable *table, const BgpAttrPtr &attrp,
     108             :         uint32_t label, uint32_t l3_label, bool vrf_originated, bool is_xmpp);
     109             :     void set_source_address(Ip4Address source_address) {
     110             :         source_address_ = source_address;
     111             :     }
     112             : 
     113           0 :     void clear() {
     114           0 :         attr_out_.reset();
     115           0 :         nexthop_list_.clear();
     116           0 :     }
     117      571808 :     uint32_t label() const {
     118      571808 :         return nexthop_list_.empty() ? label_ : nexthop_list_[0].label();
     119             :     }
     120      361553 :     uint32_t l3_label() const {
     121      361553 :         return nexthop_list_.empty() ? l3_label_ : nexthop_list_[0].l3_label();
     122             :     }
     123      252492 :     const Ip4Address &source_address() const { return source_address_; }
     124        1263 :     Ip4Address *source_address() { return &source_address_; }
     125     2416093 :     bool is_xmpp() const { return is_xmpp_; }
     126      251602 :     bool vrf_originated() const { return vrf_originated_; }
     127      736028 :     const std::string &repr() const { return repr_; }
     128       30020 :     void set_repr(const std::string &repr, size_t pos = 0) const {
     129       30020 :         repr_.clear();
     130       30021 :         repr_.append(repr, pos, std::string::npos);
     131       30020 :     }
     132             : 
     133             : private:
     134             :     int CompareTo(const RibOutAttr &rhs) const;
     135             : 
     136             :     BgpAttrPtr attr_out_;
     137             :     NextHopList nexthop_list_;
     138             :     uint32_t label_;
     139             :     uint32_t l3_label_;
     140             :     Ip4Address source_address_;
     141             :     bool is_xmpp_;
     142             :     bool vrf_originated_;
     143             :     mutable std::string repr_;
     144             : };
     145             : 
     146             : //
     147             : // This class represents a bitset of peers within a RibOut. This is distinct
     148             : // from the GroupPeerSet in order to allow it to be denser. This is possible
     149             : // because not every peer in the group may be interested in every RibOut.
     150             : //
     151             : class RibPeerSet : public BitSet {
     152             : };
     153             : 
     154             : //
     155             : // This class represents information for a particular prefix that has been
     156             : // advertised to a set of peers.
     157             : //
     158             : // An AdvertiseInfo is part of a intrusive singly linked list container in
     159             : // the RouteState.  The RibPeerSet represents the set of peers to which the
     160             : // prefix has been advertised and the RibOutAttr represents the associated
     161             : // attributes.  This representation allows us to keep track of a different
     162             : // set of attributes for each set of peers.
     163             : //
     164             : struct AdvertiseInfo {
     165        1306 :     AdvertiseInfo() { }
     166      587566 :     explicit AdvertiseInfo(const RibOutAttr *roattr) : roattr(*roattr) { }
     167             :     AdvertiseInfo(const AdvertiseInfo &rhs)
     168             :         : bitset(rhs.bitset), roattr(rhs.roattr) {
     169             :     }
     170             : 
     171             :     // Intrusive slist node for RouteState.
     172             :     boost::intrusive::slist_member_hook<> slist_node;
     173             : 
     174             :     RibPeerSet bitset;
     175             :     RibOutAttr roattr;
     176             : };
     177             : 
     178             : //
     179             : // Disposer for AdvertiseInfo.
     180             : //
     181             : struct AdvertiseInfoDisposer {
     182      588542 :     void operator()(AdvertiseInfo *ainfo) { delete ainfo; }
     183             : };
     184             : 
     185             : //
     186             : // Wrapper for intrusive slist of AdvertiseInfos. Destructor automatically
     187             : // deletes any elements still on the slist.
     188             : //
     189             : // TBD: create a class template.
     190             : //
     191             : class AdvertiseSList {
     192             : public:
     193             :     typedef boost::intrusive::member_hook<
     194             :         AdvertiseInfo,
     195             :         boost::intrusive::slist_member_hook<>,
     196             :         &AdvertiseInfo::slist_node
     197             :     > Node;
     198             :     typedef boost::intrusive::slist<
     199             :         AdvertiseInfo,
     200             :         Node,
     201             :         boost::intrusive::linear<true>
     202             :     > List;
     203             : 
     204     2662933 :     AdvertiseSList() { }
     205     2662590 :     ~AdvertiseSList() { list_.clear_and_dispose(AdvertiseInfoDisposer()); }
     206             : 
     207     5575686 :     List *operator->() { return &list_; }
     208     7413525 :     const List *operator->() const { return &list_; }
     209             :     const List &list() const { return list_; }
     210     2171592 :     void swap(AdvertiseSList &adv_slist) { list_.swap(adv_slist.list_); }
     211             : 
     212             : private:
     213             :     List list_;
     214             : };
     215             : 
     216             : //
     217             : // This class represents per prefix information that been advertised to
     218             : // the peers in a RibOut.
     219             : //
     220             : // A RouteState is derived from a DBState which means that it is part of
     221             : // the state map within a DBEntry.  This allows the RouteState to be
     222             : // associated with a DBEntry using the listener id of the RibOut as the
     223             : // index. In the steady state i.e. when there are no pending updates the
     224             : // DBEntry maps the listener id for the RibOut to a RouteState.
     225             : //
     226             : // A RouteState maintains a singly linked list of AdvertiseInfo entries
     227             : // to keep track of the attributes that have been advertised to each set
     228             : // of peers.
     229             : //
     230             : class RouteState : public DBState {
     231             : public:
     232             :     RouteState();
     233             : 
     234         187 :     void SetHistory(AdvertiseSList &history) {
     235         187 :         assert(advertised_->empty());
     236         187 :         advertised_.swap(history);
     237         187 :     }
     238     1085401 :     void SwapHistory(AdvertiseSList &history) {
     239     1085401 :         advertised_.swap(history);
     240     1085367 :     }
     241             :     void MoveHistory(RouteUpdate *rt_update);
     242             :     const AdvertiseInfo *FindHistory(const RibOutAttr &roattr) const;
     243             :     bool CompareUpdateInfo(const UpdateInfoSList &uinfo_slist) const;
     244             : 
     245      456897 :     const AdvertiseSList &Advertised() const { return advertised_; }
     246      407023 :     AdvertiseSList &Advertised() { return advertised_; }
     247             : 
     248             : private:
     249             :     AdvertiseSList advertised_;
     250             :     DISALLOW_COPY_AND_ASSIGN(RouteState);
     251             : };
     252             : 
     253             : //
     254             : // This class represents per-table state for a collection of peers with the
     255             : // same export policy.  It is effectively a combination of RibExportPolicy
     256             : // and BgpTable. A RibOut has a 1:N association with RibOutUpdates wherein
     257             : // one entry is created per DB partition.
     258             : //
     259             : // A RibOut maintains a PeerStateMap to facilitate allocation and lookup of
     260             : // a bit index per peer in the RibOut.
     261             : //
     262             : class RibOut {
     263             : public:
     264             :     class PeerIterator {
     265             :     public:
     266     1075773 :         PeerIterator(const RibOut *ribout, const RibPeerSet &peer_set)
     267     1075773 :             : ribout_(ribout), peer_set_(peer_set) {
     268     1075773 :             index_ = peer_set_.find_first();
     269     1075764 :         }
     270     3297080 :         bool HasNext() const {
     271     3297080 :             return index_ != RibPeerSet::npos;
     272             :         }
     273     2221229 :         IPeerUpdate *Next() {
     274     2221229 :             IPeerUpdate *ptr = ribout_->GetPeer(index_);
     275     2221101 :             index_ = peer_set_.find_next(index_);
     276     2220533 :             return ptr;
     277             :         }
     278     2221272 :         int index() const { return index_; }
     279             : 
     280             :     private:
     281             :         const RibOut *ribout_;
     282             :         const RibPeerSet &peer_set_;
     283             :         size_t index_;
     284             :     };
     285             : 
     286             :     RibOut(BgpTable *table, BgpUpdateSender *sender,
     287             :            const RibExportPolicy &policy);
     288             :     ~RibOut();
     289             : 
     290             :     void RegisterListener();
     291             :     void Register(IPeerUpdate *peer);
     292             :     void Unregister(IPeerUpdate *peer);
     293             :     bool IsRegistered(IPeerUpdate *peer);
     294             :     void Deactivate(IPeerUpdate *peer);
     295             :     bool IsActive(IPeerUpdate *peer) const;
     296             :     void BuildSendReadyBitSet(const RibPeerSet &peerset,
     297             :         RibPeerSet *mready) const;
     298             : 
     299             :     IPeerUpdate *GetPeer(int index) const;
     300             :     int GetPeerIndex(IPeerUpdate *peer) const;
     301             : 
     302             :     // Returns a bitmask with all the peers that are advertising this RibOut.
     303             :     const RibPeerSet &PeerSet() const;
     304             :     void GetSubsetPeerSet(RibPeerSet *peerset, const IPeerUpdate *cpeer) const;
     305             : 
     306     7079515 :     BgpTable *table() { return table_; }
     307      623693 :     const BgpTable *table() const { return table_; }
     308      611642 :     BgpUpdateSender *sender() { return sender_; }
     309             : 
     310      702016 :     const RibExportPolicy &ExportPolicy() const { return policy_; }
     311             : 
     312             :     int RouteAdvertiseCount(const BgpRoute *rt) const;
     313             :     uint32_t GetQueueSize() const;
     314             : 
     315     6731836 :     DBTableBase::ListenerId listener_id() const { return listener_id_; }
     316       33694 :     const std::string &ToString() const { return name_; }
     317             : 
     318     2993437 :     RibOutUpdates *updates(int idx) { return updates_[idx]; }
     319        7607 :     const RibOutUpdates *updates(int idx) const { return updates_[idx]; }
     320      907242 :     BgpExport *bgp_export() { return bgp_export_.get(); }
     321             : 
     322      919188 :     BgpProto::BgpPeerType peer_type() const { return policy_.type; }
     323      341111 :     as_t peer_as() const { return policy_.as_number; }
     324      204596 :     as_t local_as() const { return policy_.local_as_number; }
     325      545474 :     bool as_override() const { return policy_.as_override; }
     326        5673 :     bool llgr() const { return policy_.llgr; }
     327      311811 :     bool as4_supported() const { return policy_.as4_supported; }
     328           1 :     void set_as4_supported(bool as4) { policy_.as4_supported = as4; }
     329      208656 :     const IpAddress &nexthop() const { return policy_.nexthop; }
     330     2046225 :     bool IsEncodingXmpp() const {
     331     2046225 :         return (policy_.encoding == RibExportPolicy::XMPP);
     332             :     }
     333     1853830 :     bool IsEncodingBgp() const {
     334     1853830 :         return (policy_.encoding == RibExportPolicy::BGP);
     335             :     }
     336           4 :     std::string EncodingString() const {
     337           4 :         return IsEncodingXmpp() ? "XMPP" : "BGP";
     338             :     }
     339      248790 :     bool remove_private_enabled() const {
     340      248790 :         return policy_.remove_private.enabled;
     341             :     }
     342         114 :     bool remove_private_all() const { return policy_.remove_private.all; }
     343         114 :     bool remove_private_replace() const {
     344         114 :         return policy_.remove_private.replace;
     345             :     }
     346         114 :     bool remove_private_peer_loop_check() const {
     347         114 :         return policy_.remove_private.peer_loop_check;
     348             :     }
     349       77786 :     uint32_t cluster_id() const { return policy_.cluster_id; }
     350             : 
     351             :     void FillStatisticsInfo(std::vector<ShowRibOutStatistics> *sros_list) const;
     352             : 
     353             : private:
     354             :     struct PeerState {
     355       93135 :         explicit PeerState(IPeerUpdate *key) : peer(key), index(-1) {
     356       93135 :         }
     357       93135 :         void set_index(int idx) { index = idx; }
     358             :         IPeerUpdate *peer;
     359             :         int index;
     360             :     };
     361             :     typedef IndexMap<IPeerUpdate *, PeerState, RibPeerSet> PeerStateMap;
     362             : 
     363             :     BgpTable *table_;
     364             :     BgpUpdateSender *sender_;
     365             :     RibExportPolicy policy_;
     366             :     std::string name_;
     367             :     PeerStateMap state_map_;
     368             :     RibPeerSet active_peerset_;
     369             :     int listener_id_;
     370             :     std::vector<RibOutUpdates *> updates_;
     371             :     boost::scoped_ptr<BgpExport> bgp_export_;
     372             : 
     373             :     DISALLOW_COPY_AND_ASSIGN(RibOut);
     374             : };
     375             : 
     376             : #endif  // SRC_BGP_BGP_RIBOUT_H_