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      403243 :     AsPathSpec() : BgpAttribute(BgpAttribute::AsPath, kFlags) {}
      34      123997 :     explicit AsPathSpec(const BgpAttribute &rhs) : BgpAttribute(rhs) {}
      35      472995 :     explicit AsPathSpec(const AsPathSpec &rhs) :
      36      472995 :             BgpAttribute(BgpAttribute::AsPath, kFlags) {
      37      860051 :         for (size_t i = 0; i < rhs.path_segments.size(); i++) {
      38      387100 :             PathSegment *ps = new PathSegment;
      39      387089 :             *ps = *rhs.path_segments[i];
      40      387046 :             path_segments.push_back(ps);
      41             :         }
      42      472872 :     }
      43     1458285 :     ~AsPathSpec() {
      44     1000311 :         STLDeleteValues(&path_segments);
      45     1458209 :     }
      46             :     struct PathSegment : public ParseObject {
      47     1272477 :         int CompareTo(const PathSegment &rhs) const {
      48     1272477 :             KEY_COMPARE(path_segment_type, rhs.path_segment_type);
      49     1272477 :             KEY_COMPARE(path_segment, rhs.path_segment);
      50      606049 :             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      363155 :     explicit AsPath(AsPathDB *aspath_db, const AsPathSpec &spec)
      88      363155 :         : aspath_db_(aspath_db), path_(spec) {
      89      363146 :         refcount_ = 0;
      90      661274 :         for (size_t i = 0; i < path_.path_segments.size(); i++) {
      91      298048 :             AsPathSpec::PathSegment *ps = path_.path_segments[i];
      92      298048 :             if (ps->path_segment_type == AsPathSpec::PathSegment::AS_SET) {
      93          45 :                 std::sort(ps->path_segment.begin(), ps->path_segment.end());
      94             :             }
      95             :         }
      96      363181 :     }
      97      725411 :     virtual ~AsPath() { }
      98             :     virtual void Remove();
      99      767898 :     int AsCount() const {
     100      767898 :         int count = 0;
     101      767898 :         std::vector<AsPathSpec::PathSegment *>::const_iterator i;
     102     1388423 :         for (i = path_.path_segments.begin(); i < path_.path_segments.end();
     103      620514 :                 i++) {
     104      620516 :             if ((*i)->path_segment_type == AsPathSpec::PathSegment::AS_SET) {
     105          20 :                 count++;
     106             :             } else {
     107      620504 :                 count += (*i)->path_segment.size();
     108             :             }
     109             :         }
     110      767902 :         return count;
     111             :     }
     112             : 
     113     2065148 :     int CompareTo(const AsPath &rhs) const {
     114     2065148 :         const std::vector<AsPathSpec::PathSegment *> &lps = path_.path_segments;
     115     2065148 :         const std::vector<AsPathSpec::PathSegment *> &rps =
     116             :                 rhs.path_.path_segments;
     117             : 
     118     2065148 :         KEY_COMPARE(lps.size(), rps.size());
     119             : 
     120     2062871 :         std::vector<AsPathSpec::PathSegment *>::const_iterator i, j;
     121     2658925 :         for (i = lps.begin(), j = rps.begin(); i < lps.end(); i++, j++) {
     122     1262471 :             int ret = (*i)->CompareTo(**j);
     123     1262518 :             if (ret != 0) return ret;
     124             :         }
     125     1396439 :         return 0;
     126             :     }
     127      598297 :     const AsPathSpec &path() const { return path_; }
     128         450 :     bool empty() const { return path_.path_segments.empty(); }
     129      496045 :     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     2699957 : inline int intrusive_ptr_add_ref(const AsPath *cpath) {
     148     5399914 :     return cpath->refcount_.fetch_add(1);
     149             : }
     150             : 
     151      698237 : inline int intrusive_ptr_del_ref(const AsPath *cpath) {
     152     1396474 :     return cpath->refcount_.fetch_sub(1);
     153             : }
     154             : 
     155     2002397 : inline void intrusive_ptr_release(const AsPath *cpath) {
     156     2002397 :     int prev = cpath->refcount_.fetch_sub(1);
     157     2002397 :     if (prev == 1) {
     158        8219 :         AsPath *path = const_cast<AsPath *>(cpath);
     159        8219 :         path->Remove();
     160        8219 :         assert(path->refcount_ == 0);
     161        8219 :         delete path;
     162             :     }
     163     2002397 : }
     164             : 
     165             : typedef boost::intrusive_ptr<const AsPath> AsPathPtr;
     166             : 
     167             : struct AsPathCompare {
     168     2065146 :     bool operator()(const AsPath *lhs, const AsPath *rhs) const {
     169     2065146 :         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         781 :     AsPath4ByteSpec() : BgpAttribute(BgpAttribute::AsPath, kFlags) {}
     190          69 :     explicit AsPath4ByteSpec(const BgpAttribute &rhs) : BgpAttribute(rhs) {}
     191         554 :     explicit AsPath4ByteSpec(const AsPath4ByteSpec &rhs) :
     192         554 :             BgpAttribute(BgpAttribute::AsPath, kFlags) {
     193        1021 :         for (size_t i = 0; i < rhs.path_segments.size(); i++) {
     194         467 :             PathSegment *ps = new PathSegment;
     195         467 :             *ps = *rhs.path_segments[i];
     196         467 :             path_segments.push_back(ps);
     197             :         }
     198         554 :     }
     199        1962 :     ~AsPath4ByteSpec() {
     200        1401 :         STLDeleteValues(&path_segments);
     201        1962 :     }
     202             :     struct PathSegment : public ParseObject {
     203        1572 :         int CompareTo(const PathSegment &rhs) const {
     204        1572 :             KEY_COMPARE(path_segment_type, rhs.path_segment_type);
     205        1572 :             KEY_COMPARE(path_segment, rhs.path_segment);
     206         853 :             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         479 :     explicit AsPath4Byte(AsPath4ByteDB *aspath_db, const AsPath4ByteSpec &spec)
     244         479 :         : aspath_db_(aspath_db), path_(spec) {
     245         479 :         refcount_ = 0;
     246         904 :         for (size_t i = 0; i < path_.path_segments.size(); i++) {
     247         425 :             AsPath4ByteSpec::PathSegment *ps = path_.path_segments[i];
     248         425 :             if (ps->path_segment_type == AsPath4ByteSpec::PathSegment::AS_SET) {
     249          49 :                 std::sort(ps->path_segment.begin(), ps->path_segment.end());
     250             :             }
     251             :         }
     252         479 :     }
     253         958 :     virtual ~AsPath4Byte() { }
     254             :     virtual void Remove();
     255         488 :     int AsCount() const {
     256         488 :         int count = 0;
     257         488 :         std::vector<AsPath4ByteSpec::PathSegment *>::const_iterator i;
     258         796 :         for (i = path_.path_segments.begin(); i < path_.path_segments.end();
     259         308 :                 i++) {
     260         308 :             if ((*i)->path_segment_type ==
     261             :                              AsPath4ByteSpec::PathSegment::AS_SET) {
     262           0 :                 count++;
     263             :             } else {
     264         308 :                 count += (*i)->path_segment.size();
     265             :             }
     266             :         }
     267         488 :         return count;
     268             :     }
     269             : 
     270        1780 :     int CompareTo(const AsPath4Byte &rhs) const {
     271        1780 :         const std::vector<AsPath4ByteSpec::PathSegment *> &lps =
     272             :                 path_.path_segments;
     273        1780 :         const std::vector<AsPath4ByteSpec::PathSegment *> &rps =
     274             :                 rhs.path_.path_segments;
     275             : 
     276        1780 :         KEY_COMPARE(lps.size(), rps.size());
     277             : 
     278        1677 :         std::vector<AsPath4ByteSpec::PathSegment *>::const_iterator i, j;
     279        2527 :         for (i = lps.begin(), j = rps.begin(); i < lps.end(); i++, j++) {
     280        1569 :             int ret = (*i)->CompareTo(**j);
     281        1569 :             if (ret != 0) return ret;
     282             :         }
     283         958 :         return 0;
     284             :     }
     285         929 :     const AsPath4ByteSpec &path() const { return path_; }
     286          86 :     bool empty() const { return path_.path_segments.empty(); }
     287         219 :     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        1533 : inline int intrusive_ptr_add_ref(const AsPath4Byte *cpath) {
     306        3066 :     return cpath->refcount_.fetch_add(1);
     307             : }
     308             : 
     309         479 : inline int intrusive_ptr_del_ref(const AsPath4Byte *cpath) {
     310         958 :     return cpath->refcount_.fetch_sub(1);
     311             : }
     312             : 
     313        1054 : inline void intrusive_ptr_release(const AsPath4Byte *cpath) {
     314        1054 :     int prev = cpath->refcount_.fetch_sub(1);
     315        1054 :     if (prev == 1) {
     316         329 :         AsPath4Byte *path = const_cast<AsPath4Byte *>(cpath);
     317         329 :         path->Remove();
     318         329 :         assert(path->refcount_ == 0);
     319         329 :         delete path;
     320             :     }
     321        1054 : }
     322             : 
     323             : typedef boost::intrusive_ptr<const AsPath4Byte> AsPath4BytePtr;
     324             : 
     325             : struct AsPath4ByteCompare {
     326        1780 :     bool operator()(const AsPath4Byte *lhs, const AsPath4Byte *rhs) const {
     327        1780 :         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         445 :     As4PathSpec() : BgpAttribute(BgpAttribute::As4Path, kFlags) {}
     350           3 :     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        1366 :     ~As4PathSpec() {
     360         912 :         STLDeleteValues(&path_segments);
     361        1366 :     }
     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         450 :     explicit As4Path(As4PathDB *aspath_db, const As4PathSpec &spec)
     404         450 :         : aspath_db_(aspath_db), path_(spec) {
     405         450 :         refcount_ = 0;
     406         907 :         for (size_t i = 0; i < path_.path_segments.size(); i++) {
     407         457 :             As4PathSpec::PathSegment *ps = path_.path_segments[i];
     408         457 :             if (ps->path_segment_type == As4PathSpec::PathSegment::AS_SET) {
     409          32 :                 std::sort(ps->path_segment.begin(), ps->path_segment.end());
     410             :             }
     411             :         }
     412         450 :     }
     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         535 :     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        1159 : inline int intrusive_ptr_add_ref(const As4Path *cpath) {
     464        2318 :     return cpath->refcount_.fetch_add(1);
     465             : }
     466             : 
     467         450 : inline int intrusive_ptr_del_ref(const As4Path *cpath) {
     468         900 :     return cpath->refcount_.fetch_sub(1);
     469             : }
     470             : 
     471         709 : inline void intrusive_ptr_release(const As4Path *cpath) {
     472         709 :     int prev = cpath->refcount_.fetch_sub(1);
     473         709 :     if (prev == 1) {
     474         433 :         As4Path *path = const_cast<As4Path *>(cpath);
     475         433 :         path->Remove();
     476         433 :         assert(path->refcount_ == 0);
     477         433 :         delete path;
     478             :     }
     479         709 : }
     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_