Line data    Source code

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