Line data    Source code

       1             : /*
       2             :  * Copyright (c) 2013 Juniper Networks, Inc. All rights reserved.
       3             :  */
       4             : 
       5             : #ifndef SRC_BGP_BGP_ASPATH_H_
       6             : #define SRC_BGP_BGP_ASPATH_H_
       7             : 
       8             : #include <boost/intrusive_ptr.hpp>
       9             : 
      10             : #include <atomic>
      11             : #include <algorithm>
      12             : #include <set>
      13             : #include <string>
      14             : #include <vector>
      15             : 
      16             : #include "bgp/bgp_attr_base.h"
      17             : #include "bgp/bgp_common.h"
      18             : #include "base/parse_object.h"
      19             : #include "base/util.h"
      20             : 
      21             : class BgpAttr;
      22             : class AsPathDB;
      23             : class As4PathDB;
      24             : class AsPath4ByteDB;
      25             : class BgpServer;
      26             : 
      27             : struct AsPathSpec : public BgpAttribute {
      28             :     static const int kSize = -1;
      29             :     static const uint8_t kFlags = Transitive;
      30             :     static const as2_t kMinPrivateAs = 64512;
      31             :     static const as2_t kMaxPrivateAs = 65534;
      32             : 
      33       28672 :     AsPathSpec() : BgpAttribute(BgpAttribute::AsPath, kFlags) {}
      34          30 :     explicit AsPathSpec(const BgpAttribute &rhs) : BgpAttribute(rhs) {}
      35        9926 :     explicit AsPathSpec(const AsPathSpec &rhs) :
      36        9926 :             BgpAttribute(BgpAttribute::AsPath, kFlags) {
      37       18232 :         for (size_t i = 0; i < rhs.path_segments.size(); i++) {
      38        8308 :             PathSegment *ps = new PathSegment;
      39        8307 :             *ps = *rhs.path_segments[i];
      40        8305 :             path_segments.push_back(ps);
      41             :         }
      42        9924 :     }
      43       87564 :     ~AsPathSpec() {
      44       52089 :         STLDeleteValues(&path_segments);
      45       87549 :     }
      46             :     struct PathSegment : public ParseObject {
      47       28645 :         int CompareTo(const PathSegment &rhs) const {
      48       28645 :             KEY_COMPARE(path_segment_type, rhs.path_segment_type);
      49       28645 :             KEY_COMPARE(path_segment, rhs.path_segment);
      50       25293 :             return 0;
      51             :         }
      52             : 
      53             :         enum PathSegmentType {
      54             :             AS_SET = 1,
      55             :             AS_SEQUENCE = 2
      56             :         };
      57             :         int path_segment_type;
      58             :         std::vector<as2_t> path_segment;
      59             :     };
      60             : 
      61             :     as2_t AsLeftMost() const;
      62             :     bool AsLeftMostMatch(as2_t as) const;
      63             :     as2_t AsLeftMostPublic() const;
      64             :     bool AsPathLoop(as2_t as, uint8_t max_loop_count = 0) const;
      65         576 :     static bool AsIsPrivate(as2_t as) {
      66         576 :         return as >= kMinPrivateAs && as <= kMaxPrivateAs;
      67             :     }
      68             : 
      69             :     virtual int CompareTo(const BgpAttribute &rhs_attr) const;
      70             :     virtual void ToCanonical(BgpAttr *attr);
      71             :     virtual size_t EncodeLength() const;
      72             :     virtual std::string ToString() const;
      73             :     AsPathSpec *Add(as2_t asn) const;
      74             :     AsPathSpec *Add(const std::vector<as2_t> &asn_list) const;
      75             :     AsPathSpec *Add(const std::vector<as_t> &asn_list) const;
      76             :     AsPathSpec *Replace(as2_t old_asn, as2_t asn) const;
      77             :     AsPathSpec *RemovePrivate(bool all, as2_t asn, as2_t peer_as) const;
      78             : 
      79             :     std::vector<PathSegment *> path_segments;
      80             : };
      81             : 
      82             : class AsPath {
      83             : public:
      84             :     explicit AsPath(AsPathDB *aspath_db) : aspath_db_(aspath_db) {
      85             :         refcount_ = 0;
      86             :     }
      87        1098 :     explicit AsPath(AsPathDB *aspath_db, const AsPathSpec &spec)
      88        1098 :         : aspath_db_(aspath_db), path_(spec) {
      89        1097 :         refcount_ = 0;
      90        1156 :         for (size_t i = 0; i < path_.path_segments.size(); i++) {
      91          58 :             AsPathSpec::PathSegment *ps = path_.path_segments[i];
      92          58 :             if (ps->path_segment_type == AsPathSpec::PathSegment::AS_SET) {
      93           7 :                 std::sort(ps->path_segment.begin(), ps->path_segment.end());
      94             :             }
      95             :         }
      96        1098 :     }
      97      727174 :     virtual ~AsPath() { }
      98             :     virtual void Remove();
      99       44774 :     int AsCount() const {
     100       44774 :         int count = 0;
     101       44774 :         std::vector<AsPathSpec::PathSegment *>::const_iterator i;
     102       89516 :         for (i = path_.path_segments.begin(); i < path_.path_segments.end();
     103       44742 :                 i++) {
     104       44742 :             if ((*i)->path_segment_type == AsPathSpec::PathSegment::AS_SET) {
     105           0 :                 count++;
     106             :             } else {
     107       44742 :                 count += (*i)->path_segment.size();
     108             :             }
     109             :         }
     110       44774 :         return count;
     111             :     }
     112             : 
     113      462218 :     int CompareTo(const AsPath &rhs) const {
     114      462218 :         const std::vector<AsPathSpec::PathSegment *> &lps = path_.path_segments;
     115      462218 :         const std::vector<AsPathSpec::PathSegment *> &rps =
     116             :                 rhs.path_.path_segments;
     117             : 
     118      462218 :         KEY_COMPARE(lps.size(), rps.size());
     119             : 
     120      461247 :         std::vector<AsPathSpec::PathSegment *>::const_iterator i, j;
     121      476530 :         for (i = lps.begin(), j = rps.begin(); i < lps.end(); i++, j++) {
     122       18635 :             int ret = (*i)->CompareTo(**j);
     123       18635 :             if (ret != 0) return ret;
     124             :         }
     125      457895 :         return 0;
     126             :     }
     127       26785 :     const AsPathSpec &path() const { return path_; }
     128           0 :     bool empty() const { return path_.path_segments.empty(); }
     129           8 :     as2_t neighbor_as() const { return path_.AsLeftMost(); }
     130             : 
     131           0 :     friend std::size_t hash_value(const AsPath &as_path) {
     132           0 :         size_t hash = 0;
     133           0 :         boost::hash_combine(hash, as_path.path().ToString());
     134           0 :         return hash;
     135             :     }
     136             : 
     137             : private:
     138             :     friend int intrusive_ptr_add_ref(const AsPath *cpath);
     139             :     friend int intrusive_ptr_del_ref(const AsPath *cpath);
     140             :     friend void intrusive_ptr_release(const AsPath *cpath);
     141             : 
     142             :     mutable std::atomic<int> refcount_;
     143             :     AsPathDB *aspath_db_;
     144             :     AsPathSpec path_;
     145             : };
     146             : 
     147      222070 : inline int intrusive_ptr_add_ref(const AsPath *cpath) {
     148      444140 :     return cpath->refcount_.fetch_add(1);
     149             : }
     150             : 
     151      220872 : inline int intrusive_ptr_del_ref(const AsPath *cpath) {
     152      441744 :     return cpath->refcount_.fetch_sub(1);
     153             : }
     154             : 
     155        1191 : inline void intrusive_ptr_release(const AsPath *cpath) {
     156        1191 :     int prev = cpath->refcount_.fetch_sub(1);
     157        1191 :     if (prev == 1) {
     158          64 :         AsPath *path = const_cast<AsPath *>(cpath);
     159          64 :         path->Remove();
     160          64 :         assert(path->refcount_ == 0);
     161          64 :         delete path;
     162             :     }
     163        1191 : }
     164             : 
     165             : typedef boost::intrusive_ptr<const AsPath> AsPathPtr;
     166             : 
     167             : struct AsPathCompare {
     168      462216 :     bool operator()(const AsPath *lhs, const AsPath *rhs) const {
     169      462216 :         return lhs->CompareTo(*rhs) < 0;
     170             :     }
     171             : };
     172             : 
     173             : class AsPathDB : public BgpPathAttributeDB<AsPath, AsPathPtr, AsPathSpec,
     174             :                                            AsPathCompare, AsPathDB> {
     175             : public:
     176             :     explicit AsPathDB(BgpServer *server);
     177             : 
     178             : private:
     179             : };
     180             : 
     181             : struct AsPath4ByteSpec : public BgpAttribute {
     182             :     static const int kSize = -1;
     183             :     static const uint8_t kFlags = Transitive;
     184             :     static const as_t kMinPrivateAs = 64512;
     185             :     static const as_t kMaxPrivateAs = 65534;
     186             :     static const as_t kMinPrivateAs4 = 4200000000;
     187             :     static const as_t kMaxPrivateAs4 = 4294967294;
     188             : 
     189         791 :     AsPath4ByteSpec() : BgpAttribute(BgpAttribute::AsPath, kFlags) {}
     190           0 :     explicit AsPath4ByteSpec(const BgpAttribute &rhs) : BgpAttribute(rhs) {}
     191         565 :     explicit AsPath4ByteSpec(const AsPath4ByteSpec &rhs) :
     192         565 :             BgpAttribute(BgpAttribute::AsPath, kFlags) {
     193        1043 :         for (size_t i = 0; i < rhs.path_segments.size(); i++) {
     194         478 :             PathSegment *ps = new PathSegment;
     195         478 :             *ps = *rhs.path_segments[i];
     196         478 :             path_segments.push_back(ps);
     197             :         }
     198         565 :     }
     199        1982 :     ~AsPath4ByteSpec() {
     200        1422 :         STLDeleteValues(&path_segments);
     201        1982 :     }
     202             :     struct PathSegment : public ParseObject {
     203        1595 :         int CompareTo(const PathSegment &rhs) const {
     204        1595 :             KEY_COMPARE(path_segment_type, rhs.path_segment_type);
     205        1595 :             KEY_COMPARE(path_segment, rhs.path_segment);
     206         875 :             return 0;
     207             :         }
     208             : 
     209             :         enum PathSegmentType {
     210             :             AS_SET = 1,
     211             :             AS_SEQUENCE = 2
     212             :         };
     213             :         int path_segment_type;
     214             :         std::vector<as_t> path_segment;
     215             :     };
     216             : 
     217             :     as_t AsLeftMost() const;
     218             :     bool AsLeftMostMatch(as_t as) const;
     219             :     as_t AsLeftMostPublic() const;
     220             :     bool AsPathLoop(as_t as, uint8_t max_loop_count = 0) const;
     221          92 :     static bool AsIsPrivate(as_t as) {
     222         140 :         return ((as >= kMinPrivateAs && as <= kMaxPrivateAs) ||
     223         140 :             (as >= kMinPrivateAs4 && as <= kMaxPrivateAs4));
     224             :     }
     225             : 
     226             :     virtual int CompareTo(const BgpAttribute &rhs_attr) const;
     227             :     virtual void ToCanonical(BgpAttr *attr);
     228             :     virtual size_t EncodeLength() const;
     229             :     virtual std::string ToString() const;
     230             :     AsPath4ByteSpec *Add(as_t asn) const;
     231             :     AsPath4ByteSpec *Add(const std::vector<as_t> &asn_list) const;
     232             :     AsPath4ByteSpec *Replace(as_t old_asn, as_t asn) const;
     233             :     AsPath4ByteSpec *RemovePrivate(bool all, as_t asn, as_t peer_as) const;
     234             : 
     235             :     std::vector<PathSegment *> path_segments;
     236             : };
     237             : 
     238             : class AsPath4Byte {
     239             : public:
     240             :     explicit AsPath4Byte(AsPath4ByteDB *aspath_db) : aspath_db_(aspath_db) {
     241             :         refcount_ = 0;
     242             :     }
     243           2 :     explicit AsPath4Byte(AsPath4ByteDB *aspath_db, const AsPath4ByteSpec &spec)
     244           2 :         : aspath_db_(aspath_db), path_(spec) {
     245           2 :         refcount_ = 0;
     246           4 :         for (size_t i = 0; i < path_.path_segments.size(); i++) {
     247           2 :             AsPath4ByteSpec::PathSegment *ps = path_.path_segments[i];
     248           2 :             if (ps->path_segment_type == AsPath4ByteSpec::PathSegment::AS_SET) {
     249           0 :                 std::sort(ps->path_segment.begin(), ps->path_segment.end());
     250             :             }
     251             :         }
     252           2 :     }
     253         982 :     virtual ~AsPath4Byte() { }
     254             :     virtual void Remove();
     255          76 :     int AsCount() const {
     256          76 :         int count = 0;
     257          76 :         std::vector<AsPath4ByteSpec::PathSegment *>::const_iterator i;
     258         152 :         for (i = path_.path_segments.begin(); i < path_.path_segments.end();
     259          76 :                 i++) {
     260          76 :             if ((*i)->path_segment_type ==
     261             :                              AsPath4ByteSpec::PathSegment::AS_SET) {
     262           0 :                 count++;
     263             :             } else {
     264          76 :                 count += (*i)->path_segment.size();
     265             :             }
     266             :         }
     267          76 :         return count;
     268             :     }
     269             : 
     270        1803 :     int CompareTo(const AsPath4Byte &rhs) const {
     271        1803 :         const std::vector<AsPath4ByteSpec::PathSegment *> &lps =
     272             :                 path_.path_segments;
     273        1803 :         const std::vector<AsPath4ByteSpec::PathSegment *> &rps =
     274             :                 rhs.path_.path_segments;
     275             : 
     276        1803 :         KEY_COMPARE(lps.size(), rps.size());
     277             : 
     278        1700 :         std::vector<AsPath4ByteSpec::PathSegment *>::const_iterator i, j;
     279        2572 :         for (i = lps.begin(), j = rps.begin(); i < lps.end(); i++, j++) {
     280        1592 :             int ret = (*i)->CompareTo(**j);
     281        1592 :             if (ret != 0) return ret;
     282             :         }
     283         980 :         return 0;
     284             :     }
     285         934 :     const AsPath4ByteSpec &path() const { return path_; }
     286           0 :     bool empty() const { return path_.path_segments.empty(); }
     287           0 :     as_t neighbor_as() const { return path_.AsLeftMost(); }
     288             : 
     289           0 :     friend std::size_t hash_value(const AsPath4Byte &as_path) {
     290           0 :         size_t hash = 0;
     291           0 :         boost::hash_combine(hash, as_path.path().ToString());
     292           0 :         return hash;
     293             :     }
     294             : 
     295             : private:
     296             :     friend int intrusive_ptr_add_ref(const AsPath4Byte *cpath);
     297             :     friend int intrusive_ptr_del_ref(const AsPath4Byte *cpath);
     298             :     friend void intrusive_ptr_release(const AsPath4Byte *cpath);
     299             : 
     300             :     mutable std::atomic<int> refcount_;
     301             :     AsPath4ByteDB *aspath_db_;
     302             :     AsPath4ByteSpec path_;
     303             : };
     304             : 
     305          20 : inline int intrusive_ptr_add_ref(const AsPath4Byte *cpath) {
     306          40 :     return cpath->refcount_.fetch_add(1);
     307             : }
     308             : 
     309           2 : inline int intrusive_ptr_del_ref(const AsPath4Byte *cpath) {
     310           4 :     return cpath->refcount_.fetch_sub(1);
     311             : }
     312             : 
     313          21 : inline void intrusive_ptr_release(const AsPath4Byte *cpath) {
     314          21 :     int prev = cpath->refcount_.fetch_sub(1);
     315          21 :     if (prev == 1) {
     316           5 :         AsPath4Byte *path = const_cast<AsPath4Byte *>(cpath);
     317           5 :         path->Remove();
     318           5 :         assert(path->refcount_ == 0);
     319           5 :         delete path;
     320             :     }
     321          21 : }
     322             : 
     323             : typedef boost::intrusive_ptr<const AsPath4Byte> AsPath4BytePtr;
     324             : 
     325             : struct AsPath4ByteCompare {
     326        1803 :     bool operator()(const AsPath4Byte *lhs, const AsPath4Byte *rhs) const {
     327        1803 :         return lhs->CompareTo(*rhs) < 0;
     328             :     }
     329             : };
     330             : 
     331             : class AsPath4ByteDB : public BgpPathAttributeDB<AsPath4Byte, AsPath4BytePtr,
     332             :                          AsPath4ByteSpec, AsPath4ByteCompare, AsPath4ByteDB> {
     333             : public:
     334             :     explicit AsPath4ByteDB(BgpServer *server);
     335             : 
     336             : private:
     337             : };
     338             : 
     339             : typedef boost::intrusive_ptr<const AsPath4Byte> AsPath4BytePtr;
     340             : 
     341             : struct As4PathSpec : public BgpAttribute {
     342             :     static const int kSize = -1;
     343             :     static const uint8_t kFlags = Transitive|Optional;
     344             :     static const as_t kMinPrivateAs = 64512;
     345             :     static const as_t kMaxPrivateAs = 65534;
     346             :     static const as_t kMinPrivateAs4 = 4200000000;
     347             :     static const as_t kMaxPrivateAs4 = 4294967294;
     348             : 
     349         457 :     As4PathSpec() : BgpAttribute(BgpAttribute::As4Path, kFlags) {}
     350           0 :     explicit As4PathSpec(const BgpAttribute &rhs) : BgpAttribute(rhs) {}
     351         464 :     explicit As4PathSpec(const As4PathSpec &rhs) :
     352         464 :             BgpAttribute(BgpAttribute::As4Path, kFlags) {
     353         935 :         for (size_t i = 0; i < rhs.path_segments.size(); i++) {
     354         471 :             PathSegment *ps = new PathSegment;
     355         471 :             *ps = *rhs.path_segments[i];
     356         471 :             path_segments.push_back(ps);
     357             :         }
     358         464 :     }
     359        1378 :     ~As4PathSpec() {
     360         924 :         STLDeleteValues(&path_segments);
     361        1378 :     }
     362             :     struct PathSegment : public ParseObject {
     363        1788 :         int CompareTo(const PathSegment &rhs) const {
     364        1788 :             KEY_COMPARE(path_segment_type, rhs.path_segment_type);
     365        1788 :             KEY_COMPARE(path_segment, rhs.path_segment);
     366         915 :             return 0;
     367             :         }
     368             : 
     369             :         enum PathSegmentType {
     370             :             AS_SET = 1,
     371             :             AS_SEQUENCE = 2
     372             :         };
     373             :         int path_segment_type;
     374             :         std::vector<as_t> path_segment;
     375             :     };
     376             : 
     377             :     as_t AsLeftMost() const;
     378             :     bool AsLeftMostMatch(as_t as) const;
     379             :     as_t AsLeftMostPublic() const;
     380             :     bool AsPathLoop(as_t as, uint8_t max_loop_count = 0) const;
     381          92 :     static bool AsIsPrivate(as_t as) {
     382          92 :         return ((as >= kMinPrivateAs && as <= kMaxPrivateAs) ||
     383          92 :             (as >= kMinPrivateAs4 && as <= kMaxPrivateAs4));
     384             :     }
     385             : 
     386             :     virtual int CompareTo(const BgpAttribute &rhs_attr) const;
     387             :     virtual void ToCanonical(BgpAttr *attr);
     388             :     virtual size_t EncodeLength() const;
     389             :     virtual std::string ToString() const;
     390             :     As4PathSpec *Add(as_t asn) const;
     391             :     As4PathSpec *Add(const std::vector<as_t> &asn_list) const;
     392             :     As4PathSpec *Replace(as_t old_asn, as_t asn) const;
     393             :     As4PathSpec *RemovePrivate(bool all, as_t asn, as_t peer_as) const;
     394             : 
     395             :     std::vector<PathSegment *> path_segments;
     396             : };
     397             : 
     398             : class As4Path {
     399             : public:
     400             :     explicit As4Path(As4PathDB *aspath_db) : aspath_db_(aspath_db) {
     401             :         refcount_ = 0;
     402             :     }
     403           0 :     explicit As4Path(As4PathDB *aspath_db, const As4PathSpec &spec)
     404           0 :         : aspath_db_(aspath_db), path_(spec) {
     405           0 :         refcount_ = 0;
     406           0 :         for (size_t i = 0; i < path_.path_segments.size(); i++) {
     407           0 :             As4PathSpec::PathSegment *ps = path_.path_segments[i];
     408           0 :             if (ps->path_segment_type == As4PathSpec::PathSegment::AS_SET) {
     409           0 :                 std::sort(ps->path_segment.begin(), ps->path_segment.end());
     410             :             }
     411             :         }
     412           0 :     }
     413         900 :     virtual ~As4Path() { }
     414             :     virtual void Remove();
     415          66 :     int AsCount() const {
     416          66 :         int count = 0;
     417          66 :         std::vector<As4PathSpec::PathSegment *>::const_iterator i;
     418         132 :         for (i = path_.path_segments.begin(); i < path_.path_segments.end();
     419          66 :                 i++) {
     420          66 :             if ((*i)->path_segment_type == As4PathSpec::PathSegment::AS_SET) {
     421           0 :                 count++;
     422             :             } else {
     423          66 :                 count += (*i)->path_segment.size();
     424             :             }
     425             :         }
     426          66 :         return count;
     427             :     }
     428             : 
     429        1873 :     int CompareTo(const As4Path &rhs) const {
     430        1873 :         const std::vector<As4PathSpec::PathSegment *> &lps = path_.path_segments;
     431        1873 :         const std::vector<As4PathSpec::PathSegment *> &rps =
     432             :                 rhs.path_.path_segments;
     433             : 
     434        1873 :         KEY_COMPARE(lps.size(), rps.size());
     435             : 
     436        1773 :         std::vector<As4PathSpec::PathSegment *>::const_iterator i, j;
     437        2687 :         for (i = lps.begin(), j = rps.begin(); i < lps.end(); i++, j++) {
     438        1787 :             int ret = (*i)->CompareTo(**j);
     439        1787 :             if (ret != 0) return ret;
     440             :         }
     441         900 :         return 0;
     442             :     }
     443         539 :     const As4PathSpec &path() const { return path_; }
     444             :     bool empty() const { return path_.path_segments.empty(); }
     445             :     as_t neighbor_as() const { return path_.AsLeftMost(); }
     446             : 
     447           0 :     friend std::size_t hash_value(As4Path const &as_path) {
     448           0 :         size_t hash = 0;
     449           0 :         boost::hash_combine(hash, as_path.path().ToString());
     450           0 :         return hash;
     451             :     }
     452             : 
     453             : private:
     454             :     friend int intrusive_ptr_add_ref(const As4Path *cpath);
     455             :     friend int intrusive_ptr_del_ref(const As4Path *cpath);
     456             :     friend void intrusive_ptr_release(const As4Path *cpath);
     457             : 
     458             :     mutable std::atomic<int> refcount_;
     459             :     As4PathDB *aspath_db_;
     460             :     As4PathSpec path_;
     461             : };
     462             : 
     463           0 : inline int intrusive_ptr_add_ref(const As4Path *cpath) {
     464           0 :     return cpath->refcount_.fetch_add(1);
     465             : }
     466             : 
     467           0 : inline int intrusive_ptr_del_ref(const As4Path *cpath) {
     468           0 :     return cpath->refcount_.fetch_sub(1);
     469             : }
     470             : 
     471           0 : inline void intrusive_ptr_release(const As4Path *cpath) {
     472           0 :     int prev = cpath->refcount_.fetch_sub(1);
     473           0 :     if (prev == 1) {
     474           0 :         As4Path *path = const_cast<As4Path *>(cpath);
     475           0 :         path->Remove();
     476           0 :         assert(path->refcount_ == 0);
     477           0 :         delete path;
     478             :     }
     479           0 : }
     480             : 
     481             : typedef boost::intrusive_ptr<const As4Path> As4PathPtr;
     482             : 
     483             : struct As4PathCompare {
     484        1873 :     bool operator()(const As4Path *lhs, const As4Path *rhs) const {
     485        1873 :         return lhs->CompareTo(*rhs) < 0;
     486             :     }
     487             : };
     488             : 
     489             : class As4PathDB : public BgpPathAttributeDB<As4Path, As4PathPtr, As4PathSpec,
     490             :                                            As4PathCompare, As4PathDB> {
     491             : public:
     492             :     explicit As4PathDB(BgpServer *server);
     493             : 
     494             : private:
     495             : };
     496             : 
     497             : typedef boost::intrusive_ptr<const As4Path> As4PathPtr;
     498             : #endif  // SRC_BGP_BGP_ASPATH_H_