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      402234 :     AsPathSpec() : BgpAttribute(BgpAttribute::AsPath, kFlags) {}
      34      124019 :     explicit AsPathSpec(const BgpAttribute &rhs) : BgpAttribute(rhs) {}
      35      472108 :     explicit AsPathSpec(const AsPathSpec &rhs) :
      36      472108 :             BgpAttribute(BgpAttribute::AsPath, kFlags) {
      37      857984 :         for (size_t i = 0; i < rhs.path_segments.size(); i++) {
      38      385910 :             PathSegment *ps = new PathSegment;
      39      385899 :             *ps = *rhs.path_segments[i];
      40      385861 :             path_segments.push_back(ps);
      41             :         }
      42      472024 :     }
      43     1455463 :     ~AsPathSpec() {
      44      998403 :         STLDeleteValues(&path_segments);
      45     1455371 :     }
      46             :     struct PathSegment : public ParseObject {
      47     1286765 :         int CompareTo(const PathSegment &rhs) const {
      48     1286765 :             KEY_COMPARE(path_segment_type, rhs.path_segment_type);
      49     1286765 :             KEY_COMPARE(path_segment, rhs.path_segment);
      50      604405 :             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      362512 :     explicit AsPath(AsPathDB *aspath_db, const AsPathSpec &spec)
      88      362512 :         : aspath_db_(aspath_db), path_(spec) {
      89      362504 :         refcount_ = 0;
      90      659797 :         for (size_t i = 0; i < path_.path_segments.size(); i++) {
      91      297233 :             AsPathSpec::PathSegment *ps = path_.path_segments[i];
      92      297232 :             if (ps->path_segment_type == AsPathSpec::PathSegment::AS_SET) {
      93          45 :                 std::sort(ps->path_segment.begin(), ps->path_segment.end());
      94             :             }
      95             :         }
      96      362521 :     }
      97      724094 :     virtual ~AsPath() { }
      98             :     virtual void Remove();
      99      762430 :     int AsCount() const {
     100      762430 :         int count = 0;
     101      762430 :         std::vector<AsPathSpec::PathSegment *>::const_iterator i;
     102     1377259 :         for (i = path_.path_segments.begin(); i < path_.path_segments.end();
     103      614824 :                 i++) {
     104      614832 :             if ((*i)->path_segment_type == AsPathSpec::PathSegment::AS_SET) {
     105          20 :                 count++;
     106             :             } else {
     107      614810 :                 count += (*i)->path_segment.size();
     108             :             }
     109             :         }
     110      762652 :         return count;
     111             :     }
     112             : 
     113     2933300 :     int CompareTo(const AsPath &rhs) const {
     114     2933300 :         const std::vector<AsPathSpec::PathSegment *> &lps = path_.path_segments;
     115     2933300 :         const std::vector<AsPathSpec::PathSegment *> &rps =
     116             :                 rhs.path_.path_segments;
     117             : 
     118     2933300 :         KEY_COMPARE(lps.size(), rps.size());
     119             : 
     120     2930936 :         std::vector<AsPathSpec::PathSegment *>::const_iterator i, j;
     121     3525349 :         for (i = lps.begin(), j = rps.begin(); i < lps.end(); i++, j++) {
     122     1276760 :             int ret = (*i)->CompareTo(**j);
     123     1276803 :             if (ret != 0) return ret;
     124             :         }
     125     2248576 :         return 0;
     126             :     }
     127      597577 :     const AsPathSpec &path() const { return path_; }
     128         450 :     bool empty() const { return path_.path_segments.empty(); }
     129      492094 :     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     3117489 : inline int intrusive_ptr_add_ref(const AsPath *cpath) {
     148     6234978 :     return cpath->refcount_.fetch_add(1);
     149             : }
     150             : 
     151     1124317 : inline int intrusive_ptr_del_ref(const AsPath *cpath) {
     152     2248634 :     return cpath->refcount_.fetch_sub(1);
     153             : }
     154             : 
     155     1993784 : inline void intrusive_ptr_release(const AsPath *cpath) {
     156     1993784 :     int prev = cpath->refcount_.fetch_sub(1);
     157     1993784 :     if (prev == 1) {
     158        8200 :         AsPath *path = const_cast<AsPath *>(cpath);
     159        8200 :         path->Remove();
     160        8200 :         assert(path->refcount_ == 0);
     161        8200 :         delete path;
     162             :     }
     163     1993784 : }
     164             : 
     165             : typedef boost::intrusive_ptr<const AsPath> AsPathPtr;
     166             : 
     167             : struct AsPathCompare {
     168     2933298 :     bool operator()(const AsPath *lhs, const AsPath *rhs) const {
     169     2933298 :         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         787 :     AsPath4ByteSpec() : BgpAttribute(BgpAttribute::AsPath, kFlags) {}
     190          69 :     explicit AsPath4ByteSpec(const BgpAttribute &rhs) : BgpAttribute(rhs) {}
     191         560 :     explicit AsPath4ByteSpec(const AsPath4ByteSpec &rhs) :
     192         560 :             BgpAttribute(BgpAttribute::AsPath, kFlags) {
     193        1033 :         for (size_t i = 0; i < rhs.path_segments.size(); i++) {
     194         473 :             PathSegment *ps = new PathSegment;
     195         473 :             *ps = *rhs.path_segments[i];
     196         473 :             path_segments.push_back(ps);
     197             :         }
     198         560 :     }
     199        1974 :     ~AsPath4ByteSpec() {
     200        1413 :         STLDeleteValues(&path_segments);
     201        1974 :     }
     202             :     struct PathSegment : public ParseObject {
     203        1581 :         int CompareTo(const PathSegment &rhs) const {
     204        1581 :             KEY_COMPARE(path_segment_type, rhs.path_segment_type);
     205        1581 :             KEY_COMPARE(path_segment, rhs.path_segment);
     206         865 :             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         485 :     explicit AsPath4Byte(AsPath4ByteDB *aspath_db, const AsPath4ByteSpec &spec)
     244         485 :         : aspath_db_(aspath_db), path_(spec) {
     245         485 :         refcount_ = 0;
     246         916 :         for (size_t i = 0; i < path_.path_segments.size(); i++) {
     247         431 :             AsPath4ByteSpec::PathSegment *ps = path_.path_segments[i];
     248         431 :             if (ps->path_segment_type == AsPath4ByteSpec::PathSegment::AS_SET) {
     249          49 :                 std::sort(ps->path_segment.begin(), ps->path_segment.end());
     250             :             }
     251             :         }
     252         485 :     }
     253         970 :     virtual ~AsPath4Byte() { }
     254             :     virtual void Remove();
     255         496 :     int AsCount() const {
     256         496 :         int count = 0;
     257         496 :         std::vector<AsPath4ByteSpec::PathSegment *>::const_iterator i;
     258         812 :         for (i = path_.path_segments.begin(); i < path_.path_segments.end();
     259         316 :                 i++) {
     260         316 :             if ((*i)->path_segment_type ==
     261             :                              AsPath4ByteSpec::PathSegment::AS_SET) {
     262           0 :                 count++;
     263             :             } else {
     264         316 :                 count += (*i)->path_segment.size();
     265             :             }
     266             :         }
     267         496 :         return count;
     268             :     }
     269             : 
     270        1789 :     int CompareTo(const AsPath4Byte &rhs) const {
     271        1789 :         const std::vector<AsPath4ByteSpec::PathSegment *> &lps =
     272             :                 path_.path_segments;
     273        1789 :         const std::vector<AsPath4ByteSpec::PathSegment *> &rps =
     274             :                 rhs.path_.path_segments;
     275             : 
     276        1789 :         KEY_COMPARE(lps.size(), rps.size());
     277             : 
     278        1686 :         std::vector<AsPath4ByteSpec::PathSegment *>::const_iterator i, j;
     279        2548 :         for (i = lps.begin(), j = rps.begin(); i < lps.end(); i++, j++) {
     280        1578 :             int ret = (*i)->CompareTo(**j);
     281        1578 :             if (ret != 0) return ret;
     282             :         }
     283         970 :         return 0;
     284             :     }
     285         933 :     const AsPath4ByteSpec &path() const { return path_; }
     286          86 :     bool empty() const { return path_.path_segments.empty(); }
     287         225 :     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        1551 : inline int intrusive_ptr_add_ref(const AsPath4Byte *cpath) {
     306        3102 :     return cpath->refcount_.fetch_add(1);
     307             : }
     308             : 
     309         485 : inline int intrusive_ptr_del_ref(const AsPath4Byte *cpath) {
     310         970 :     return cpath->refcount_.fetch_sub(1);
     311             : }
     312             : 
     313        1066 : inline void intrusive_ptr_release(const AsPath4Byte *cpath) {
     314        1066 :     int prev = cpath->refcount_.fetch_sub(1);
     315        1066 :     if (prev == 1) {
     316         330 :         AsPath4Byte *path = const_cast<AsPath4Byte *>(cpath);
     317         330 :         path->Remove();
     318         330 :         assert(path->refcount_ == 0);
     319         330 :         delete path;
     320             :     }
     321        1066 : }
     322             : 
     323             : typedef boost::intrusive_ptr<const AsPath4Byte> AsPath4BytePtr;
     324             : 
     325             : struct AsPath4ByteCompare {
     326        1789 :     bool operator()(const AsPath4Byte *lhs, const AsPath4Byte *rhs) const {
     327        1789 :         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         455 :     As4PathSpec() : BgpAttribute(BgpAttribute::As4Path, kFlags) {}
     350           5 :     explicit As4PathSpec(const BgpAttribute &rhs) : BgpAttribute(rhs) {}
     351         472 :     explicit As4PathSpec(const As4PathSpec &rhs) :
     352         472 :             BgpAttribute(BgpAttribute::As4Path, kFlags) {
     353         951 :         for (size_t i = 0; i < rhs.path_segments.size(); i++) {
     354         479 :             PathSegment *ps = new PathSegment;
     355         479 :             *ps = *rhs.path_segments[i];
     356         479 :             path_segments.push_back(ps);
     357             :         }
     358         472 :     }
     359        1394 :     ~As4PathSpec() {
     360         932 :         STLDeleteValues(&path_segments);
     361        1394 :     }
     362             :     struct PathSegment : public ParseObject {
     363        1806 :         int CompareTo(const PathSegment &rhs) const {
     364        1806 :             KEY_COMPARE(path_segment_type, rhs.path_segment_type);
     365        1806 :             KEY_COMPARE(path_segment, rhs.path_segment);
     366         927 :             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         456 :     explicit As4Path(As4PathDB *aspath_db, const As4PathSpec &spec)
     404         456 :         : aspath_db_(aspath_db), path_(spec) {
     405         456 :         refcount_ = 0;
     406         919 :         for (size_t i = 0; i < path_.path_segments.size(); i++) {
     407         463 :             As4PathSpec::PathSegment *ps = path_.path_segments[i];
     408         463 :             if (ps->path_segment_type == As4PathSpec::PathSegment::AS_SET) {
     409          32 :                 std::sort(ps->path_segment.begin(), ps->path_segment.end());
     410             :             }
     411             :         }
     412         456 :     }
     413         912 :     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        1891 :     int CompareTo(const As4Path &rhs) const {
     430        1891 :         const std::vector<As4PathSpec::PathSegment *> &lps = path_.path_segments;
     431        1891 :         const std::vector<As4PathSpec::PathSegment *> &rps =
     432             :                 rhs.path_.path_segments;
     433             : 
     434        1891 :         KEY_COMPARE(lps.size(), rps.size());
     435             : 
     436        1791 :         std::vector<As4PathSpec::PathSegment *>::const_iterator i, j;
     437        2717 :         for (i = lps.begin(), j = rps.begin(); i < lps.end(); i++, j++) {
     438        1805 :             int ret = (*i)->CompareTo(**j);
     439        1805 :             if (ret != 0) return ret;
     440             :         }
     441         912 :         return 0;
     442             :     }
     443         538 :     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        1177 : inline int intrusive_ptr_add_ref(const As4Path *cpath) {
     464        2354 :     return cpath->refcount_.fetch_add(1);
     465             : }
     466             : 
     467         456 : inline int intrusive_ptr_del_ref(const As4Path *cpath) {
     468         912 :     return cpath->refcount_.fetch_sub(1);
     469             : }
     470             : 
     471         721 : inline void intrusive_ptr_release(const As4Path *cpath) {
     472         721 :     int prev = cpath->refcount_.fetch_sub(1);
     473         721 :     if (prev == 1) {
     474         439 :         As4Path *path = const_cast<As4Path *>(cpath);
     475         439 :         path->Remove();
     476         439 :         assert(path->refcount_ == 0);
     477         439 :         delete path;
     478             :     }
     479         721 : }
     480             : 
     481             : typedef boost::intrusive_ptr<const As4Path> As4PathPtr;
     482             : 
     483             : struct As4PathCompare {
     484        1891 :     bool operator()(const As4Path *lhs, const As4Path *rhs) const {
     485        1891 :         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_