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