Line data    Source code

       1             : /*
       2             :  * Copyright (c) 2013 Juniper Networks, Inc. All rights reserved.
       3             :  */
       4             : 
       5             : #include "bgp/bgp_aspath.h"
       6             : 
       7             : #include <boost/assign/list_of.hpp>
       8             : #include <sstream>
       9             : 
      10             : #include "bgp/bgp_proto.h"
      11             : 
      12             : using boost::assign::list_of;
      13             : using std::copy;
      14             : using std::ostringstream;
      15             : using std::string;
      16             : using std::vector;
      17             : 
      18             : //
      19             : // Return the left most AS.
      20             : //
      21      485305 : as2_t AsPathSpec::AsLeftMost() const {
      22      485305 :     if (path_segments.empty())
      23       41129 :         return 0;
      24      444180 :     if (path_segments[0]->path_segment_type == PathSegment::AS_SET)
      25           7 :         return 0;
      26      444171 :     if (path_segments[0]->path_segment.empty())
      27        2171 :         return 0;
      28      441986 :     return (path_segments[0]->path_segment[0]);
      29             : }
      30             : 
      31             : //
      32             : // Return true if left most AS matches the input.
      33             : //
      34       87899 : bool AsPathSpec::AsLeftMostMatch(as2_t as) const {
      35       87899 :     if (path_segments.empty())
      36           0 :         return false;
      37       87899 :     if (path_segments[0]->path_segment.empty())
      38           0 :         return false;
      39       87899 :     return (path_segments[0]->path_segment[0] == as);
      40             : }
      41             : 
      42             : //
      43             : // Return the left most public AS.
      44             : //
      45          24 : as2_t AsPathSpec::AsLeftMostPublic() const {
      46          24 :     for (size_t i = 0; i < path_segments.size(); ++i) {
      47          24 :         PathSegment *ps = path_segments[i];
      48          80 :         for (size_t j = 0; j < path_segments[i]->path_segment.size(); ++j) {
      49          80 :             if (!AsIsPrivate(ps->path_segment[j]))
      50          24 :                 return ps->path_segment[j];
      51             :         }
      52             :     }
      53           0 :     return 0;
      54             : }
      55             : 
      56       10003 : int AsPathSpec::CompareTo(const BgpAttribute &rhs_attr) const {
      57       10003 :     int ret = BgpAttribute::CompareTo(rhs_attr);
      58       10003 :     if (ret != 0) return ret;
      59       10003 :     const AsPathSpec &rhs = static_cast<const AsPathSpec &>(rhs_attr);
      60       10003 :     KEY_COMPARE(path_segments.size(), rhs.path_segments.size());
      61             : 
      62       20013 :     for (size_t i = 0; i < path_segments.size(); i++) {
      63       10010 :         int ret = path_segments[i]->CompareTo(*rhs.path_segments[i]);
      64       10010 :         if (ret != 0) return ret;
      65             :     }
      66       10003 :     return 0;
      67             : }
      68             : 
      69      117225 : void AsPathSpec::ToCanonical(BgpAttr *attr) {
      70      117225 :     attr->set_as_path(this);
      71      117225 : }
      72             : 
      73      116772 : string AsPathSpec::ToString() const {
      74      116772 :     ostringstream oss;
      75             : 
      76      210933 :     for (size_t i = 0; i < path_segments.size(); i++) {
      77       94128 :         if (i != 0) oss << " ";
      78       94128 :         switch (path_segments[i]->path_segment_type) {
      79           3 :         case AsPathSpec::PathSegment::AS_SET:
      80           3 :             oss << "{";
      81           3 :             for (size_t j = 0; j < path_segments[i]->path_segment.size(); j++) {
      82           2 :                 if (j != 0) oss << " ";
      83           2 :                 oss << path_segments[i]->path_segment[j];
      84             :             }
      85           1 :             oss << "}";
      86           1 :             break;
      87       94124 :         case AsPathSpec::PathSegment::AS_SEQUENCE:
      88      221594 :             for (size_t j = 0; j < path_segments[i]->path_segment.size(); j++) {
      89      127465 :                 if (j != 0) oss << " ";
      90      127465 :                 oss << path_segments[i]->path_segment[j];
      91             :             }
      92       94127 :             break;
      93           0 :         default:
      94           0 :             break;
      95             :         }
      96             :     }
      97             : 
      98      233604 :     return oss.str();
      99      116800 : }
     100             : 
     101      383374 : size_t AsPathSpec::EncodeLength() const {
     102      383374 :     size_t sz = 0;
     103      602846 :     for (size_t i = 0; i < path_segments.size(); i++) {
     104      219441 :         sz += 2;
     105      219441 :         sz += path_segments[i]->path_segment.size() * 2;
     106             :     }
     107      383362 :     return sz;
     108             : }
     109             : 
     110             : //
     111             : // Check AsPathSpec for loops for the given as.
     112             : // Return true if the number of occurrences of as exceeds given max loop count.
     113             : //
     114      317804 : bool AsPathSpec::AsPathLoop(as2_t as, uint8_t max_loop_count) const {
     115      317804 :     uint8_t loop_count = 0;
     116      477450 :     for (size_t i = 0; i < path_segments.size(); ++i) {
     117      489753 :         for (size_t j = 0; j < path_segments[i]->path_segment.size(); ++j) {
     118      330103 :             if (path_segments[i]->path_segment[j] == as &&
     119             :                 ++loop_count > max_loop_count) {
     120      135407 :                 return true;
     121             :             }
     122             :         }
     123             :     }
     124      182421 :     return false;
     125             : }
     126             : 
     127             : //
     128             : // Create a new AsPathSpec by prepending the given asn at the beginning.
     129             : //
     130      202500 : AsPathSpec *AsPathSpec::Add(as2_t asn) const {
     131      202500 :     vector<as2_t> asn_list = list_of(asn);
     132      404903 :     return Add(asn_list);
     133      202457 : }
     134             : 
     135             : //
     136             : // Create a new AsPathSpec by prepending the given vector of asns at the
     137             : // beginning.
     138             : //
     139           3 : AsPathSpec *AsPathSpec::Add(const vector<as_t> &asn_list) const {
     140           3 :     AsPathSpec *new_spec = new AsPathSpec;
     141           3 :     PathSegment *ps = new PathSegment;
     142           3 :     ps->path_segment_type = PathSegment::AS_SEQUENCE;
     143          12 :     for (vector<as_t>::const_iterator it = asn_list.begin(); it !=
     144          18 :                       asn_list.end(); it++) {
     145           6 :         if ((*it) <= AS2_MAX)
     146           6 :             ps->path_segment.push_back((as2_t)(*it));
     147             :     }
     148           3 :     size_t first = 0;
     149           3 :     size_t last = path_segments.size();
     150           4 :     if (last &&
     151           4 :         path_segments[0]->path_segment_type == PathSegment::AS_SEQUENCE &&
     152           1 :         path_segments[0]->path_segment.size() + asn_list.size() <= 255) {
     153           1 :         copy(path_segments[0]->path_segment.begin(),
     154           1 :              path_segments[0]->path_segment.end(),
     155           1 :              back_inserter(ps->path_segment));
     156           1 :         new_spec->path_segments.push_back(ps);
     157           1 :         first++;
     158             :     } else {
     159           2 :         new_spec->path_segments.push_back(ps);
     160             :     }
     161           3 :     if (first == last)
     162           3 :         return new_spec;
     163           0 :     for (size_t idx = first; idx < last; ++idx) {
     164           0 :         PathSegment *ps = new PathSegment;
     165           0 :         *ps = *path_segments[idx];
     166           0 :         new_spec->path_segments.push_back(ps);
     167             :     }
     168           0 :     return new_spec;
     169             : }
     170             : 
     171             : //
     172             : // Create a new AsPathSpec by prepending the given vector of asns at the
     173             : // beginning.
     174             : //
     175      202461 : AsPathSpec *AsPathSpec::Add(const vector<as2_t> &asn_list) const {
     176      202461 :     AsPathSpec *new_spec = new AsPathSpec;
     177      202458 :     PathSegment *ps = new PathSegment;
     178      202447 :     ps->path_segment_type = PathSegment::AS_SEQUENCE;
     179      202447 :     ps->path_segment = asn_list;
     180      202419 :     size_t first = 0;
     181      202419 :     size_t last = path_segments.size();
     182      273925 :     if (last &&
     183      273924 :         path_segments[0]->path_segment_type == PathSegment::AS_SEQUENCE &&
     184       71472 :         path_segments[0]->path_segment.size() + asn_list.size() <= 255) {
     185       71466 :         copy(path_segments[0]->path_segment.begin(),
     186       71468 :              path_segments[0]->path_segment.end(),
     187       71468 :              back_inserter(ps->path_segment));
     188       71466 :         new_spec->path_segments.push_back(ps);
     189       71464 :         first++;
     190             :     } else {
     191      130984 :         new_spec->path_segments.push_back(ps);
     192             :     }
     193      202461 :     if (first == last)
     194      202439 :         return new_spec;
     195          96 :     for (size_t idx = first; idx < last; ++idx) {
     196          74 :         PathSegment *ps = new PathSegment;
     197          74 :         *ps = *path_segments[idx];
     198          74 :         new_spec->path_segments.push_back(ps);
     199             :     }
     200          22 :     return new_spec;
     201             : }
     202             : 
     203             : //
     204             : // Create a new AsPathSpec by replacing the old asn with given asn.
     205             : //
     206          46 : AsPathSpec *AsPathSpec::Replace(as2_t old_asn, as2_t asn) const {
     207          46 :     AsPathSpec *new_spec = new AsPathSpec(*this);
     208          94 :     for (size_t i = 0; i < new_spec->path_segments.size(); ++i) {
     209          48 :         PathSegment *ps = new_spec->path_segments[i];
     210         128 :         for (size_t j = 0; j < ps->path_segment.size(); ++j) {
     211          80 :             if (ps->path_segment[j] == old_asn)
     212          24 :                 ps->path_segment[j] = asn;
     213             :         }
     214             :     }
     215          46 :     return new_spec;
     216             : }
     217             : 
     218             : //
     219             : // Create a new AsPathSpec by removing private asns.  Stop looking for private
     220             : // asns when we encounter the first public asn or the peer asn.
     221             : // If all is true, remove all private asns i.e. do not stop when we encounter
     222             : // the first public asn or the peer asn.
     223             : // If asn is non-zero, replace private asns instead of removing them. Use the
     224             : // nearest public asn as the replacement value.  If we haven't found a public
     225             : // asn, then use the given asn.
     226             : // If peer asn is non-zero, do not remove/replace it.
     227             : //
     228         102 : AsPathSpec *AsPathSpec::RemovePrivate(bool all, as2_t asn, as2_t peer_asn) const {
     229         102 :     bool remove_replace_done = false;
     230         102 :     AsPathSpec *new_spec = new AsPathSpec;
     231         210 :     for (size_t i = 0; i < path_segments.size(); ++i) {
     232         108 :         PathSegment *ps = path_segments[i];
     233         108 :         PathSegment *new_ps = new PathSegment;
     234             : 
     235             :         // We've already removed/replaced all private asns that we can.
     236             :         // Copy the entire segment instead of copying one as2_t at a time.
     237         108 :         if (remove_replace_done) {
     238           4 :             *new_ps = *ps;
     239           4 :             new_spec->path_segments.push_back(new_ps);
     240           4 :             continue;
     241             :         }
     242             : 
     243             :         // Examine each as2_t in the path segment to build a modified version.
     244             :         // Note down that we're done removing/replacing when we see a public
     245             :         // asn or the peer asn.
     246         104 :         new_ps->path_segment_type = ps->path_segment_type;
     247         523 :         for (size_t j = 0; j < ps->path_segment.size(); ++j) {
     248         819 :             if (remove_replace_done ||
     249         694 :                 !AsIsPrivate(ps->path_segment[j]) ||
     250         275 :                 ps->path_segment[j] == peer_asn) {
     251         150 :                 new_ps->path_segment.push_back(ps->path_segment[j]);
     252         150 :                 remove_replace_done = !all;
     253         150 :                 if (asn && !AsIsPrivate(ps->path_segment[j])) {
     254          93 :                     asn = ps->path_segment[j];
     255             :                 }
     256         269 :             } else if (asn) {
     257         190 :                 new_ps->path_segment.push_back(asn);
     258             :             }
     259             :         }
     260             : 
     261             :         // Get rid of the new path segment if it's empty.
     262             :         // Otherwise add it to the new spec.
     263         104 :         if (new_ps->path_segment.empty()) {
     264          10 :             delete new_ps;
     265             :         } else {
     266          94 :             new_spec->path_segments.push_back(new_ps);
     267             :         }
     268             :     }
     269             : 
     270         102 :     return new_spec;
     271             : }
     272             : 
     273        8261 : void AsPath::Remove() {
     274        8261 :     aspath_db_->Delete(this);
     275        8261 : }
     276             : 
     277        9742 : AsPathDB::AsPathDB(BgpServer *server) {
     278        9742 : }
     279             : 
     280             : //
     281             : // Return the left most AS.
     282             : //
     283         225 : as_t AsPath4ByteSpec::AsLeftMost() const {
     284         225 :     if (path_segments.empty())
     285          45 :         return 0;
     286         180 :     if (path_segments[0]->path_segment_type == PathSegment::AS_SET)
     287           0 :         return 0;
     288         180 :     if (path_segments[0]->path_segment.empty())
     289           0 :         return 0;
     290         180 :     return (path_segments[0]->path_segment[0]);
     291             : }
     292             : 
     293             : //
     294             : // Return true if left most AS matches the input.
     295             : //
     296         153 : bool AsPath4ByteSpec::AsLeftMostMatch(as_t as) const {
     297         153 :     if (path_segments.empty())
     298           0 :         return false;
     299         153 :     if (path_segments[0]->path_segment.empty())
     300           0 :         return false;
     301         153 :     return (path_segments[0]->path_segment[0] == as);
     302             : }
     303             : 
     304             : //
     305             : // Return the left most public AS.
     306             : //
     307           0 : as_t AsPath4ByteSpec::AsLeftMostPublic() const {
     308           0 :     for (size_t i = 0; i < path_segments.size(); ++i) {
     309           0 :         PathSegment *ps = path_segments[i];
     310           0 :         for (size_t j = 0; j < path_segments[i]->path_segment.size(); ++j) {
     311           0 :             if (!AsIsPrivate(ps->path_segment[j]))
     312           0 :                 return ps->path_segment[j];
     313             :         }
     314             :     }
     315           0 :     return 0;
     316             : }
     317             : 
     318           3 : int AsPath4ByteSpec::CompareTo(const BgpAttribute &rhs_attr) const {
     319           3 :     int ret = BgpAttribute::CompareTo(rhs_attr);
     320           3 :     if (ret != 0) return ret;
     321           3 :     const AsPath4ByteSpec &rhs = static_cast<const AsPath4ByteSpec &>(rhs_attr);
     322           3 :     KEY_COMPARE(path_segments.size(), rhs.path_segments.size());
     323             : 
     324           6 :     for (size_t i = 0; i < path_segments.size(); i++) {
     325           3 :         int ret = path_segments[i]->CompareTo(*rhs.path_segments[i]);
     326           3 :         if (ret != 0) return ret;
     327             :     }
     328           3 :     return 0;
     329             : }
     330             : 
     331          94 : void AsPath4ByteSpec::ToCanonical(BgpAttr *attr) {
     332          94 :     attr->set_aspath_4byte(this);
     333          94 : }
     334             : 
     335          66 : string AsPath4ByteSpec::ToString() const {
     336          66 :     ostringstream oss;
     337             : 
     338          99 :     for (size_t i = 0; i < path_segments.size(); i++) {
     339          33 :         if (i != 0) oss << " ";
     340          33 :         switch (path_segments[i]->path_segment_type) {
     341           0 :         case AsPath4ByteSpec::PathSegment::AS_SET:
     342           0 :             oss << "{";
     343           0 :             for (size_t j = 0; j < path_segments[i]->path_segment.size(); j++) {
     344           0 :                 if (j != 0) oss << " ";
     345           0 :                 oss << path_segments[i]->path_segment[j];
     346             :             }
     347           0 :             oss << "}";
     348           0 :             break;
     349          33 :         case AsPath4ByteSpec::PathSegment::AS_SEQUENCE:
     350          66 :             for (size_t j = 0; j < path_segments[i]->path_segment.size(); j++) {
     351          33 :                 if (j != 0) oss << " ";
     352          33 :                 oss << path_segments[i]->path_segment[j];
     353             :             }
     354          33 :             break;
     355           0 :         default:
     356           0 :             break;
     357             :         }
     358             :     }
     359             : 
     360         132 :     return oss.str();
     361          66 : }
     362             : 
     363         205 : size_t AsPath4ByteSpec::EncodeLength() const {
     364         205 :     size_t sz = 0;
     365         275 :     for (size_t i = 0; i < path_segments.size(); i++) {
     366          70 :         sz += 2;
     367          70 :         sz += path_segments[i]->path_segment.size() * 4;
     368             :     }
     369         205 :     return sz;
     370             : }
     371             : 
     372             : //
     373             : // Check AsPath4ByteSpec for loops for the given as.
     374             : // Return true if the number of occurrences of as exceeds given max loop count.
     375             : //
     376         340 : bool AsPath4ByteSpec::AsPathLoop(as_t as, uint8_t max_loop_count) const {
     377         340 :     uint8_t loop_count = 0;
     378         540 :     for (size_t i = 0; i < path_segments.size(); ++i) {
     379         965 :         for (size_t j = 0; j < path_segments[i]->path_segment.size(); ++j) {
     380         765 :             if (path_segments[i]->path_segment[j] == as &&
     381             :                 ++loop_count > max_loop_count) {
     382         123 :                 return true;
     383             :             }
     384             :         }
     385             :     }
     386         217 :     return false;
     387             : }
     388             : 
     389             : //
     390             : // Create a new AsPath4ByteSpec by prepending the given asn at the beginning.
     391             : //
     392         233 : AsPath4ByteSpec *AsPath4ByteSpec::Add(as_t asn) const {
     393         233 :     vector<as_t> asn_list = list_of(asn);
     394         466 :     return Add(asn_list);
     395         233 : }
     396             : 
     397             : //
     398             : // Create a new AsPath4ByteSpec by prepending the given vector of asns at the
     399             : // beginning.
     400             : //
     401         236 : AsPath4ByteSpec *AsPath4ByteSpec::Add(const vector<as_t> &asn_list) const {
     402         236 :     AsPath4ByteSpec *new_spec = new AsPath4ByteSpec;
     403         236 :     PathSegment *ps = new PathSegment;
     404         236 :     ps->path_segment_type = PathSegment::AS_SEQUENCE;
     405         236 :     ps->path_segment = asn_list;
     406         236 :     size_t first = 0;
     407         236 :     size_t last = path_segments.size();
     408         421 :     if (last &&
     409         405 :         path_segments[0]->path_segment_type == PathSegment::AS_SEQUENCE &&
     410         169 :         path_segments[0]->path_segment.size() + asn_list.size() <= 255) {
     411         169 :         copy(path_segments[0]->path_segment.begin(),
     412         169 :              path_segments[0]->path_segment.end(),
     413         169 :              back_inserter(ps->path_segment));
     414         169 :         new_spec->path_segments.push_back(ps);
     415         169 :         first++;
     416             :     } else {
     417          67 :         new_spec->path_segments.push_back(ps);
     418             :     }
     419         236 :     if (first == last)
     420         204 :         return new_spec;
     421          64 :     for (size_t idx = first; idx < last; ++idx) {
     422          32 :         PathSegment *ps = new PathSegment;
     423          32 :         *ps = *path_segments[idx];
     424          32 :         new_spec->path_segments.push_back(ps);
     425             :     }
     426          32 :     return new_spec;
     427             : }
     428             : 
     429             : //
     430             : // Create a new AsPath4ByteSpec by replacing the old asn with given asn.
     431             : //
     432           8 : AsPath4ByteSpec *AsPath4ByteSpec::Replace(as_t old_asn, as_t asn) const {
     433           8 :     AsPath4ByteSpec *new_spec = new AsPath4ByteSpec(*this);
     434          16 :     for (size_t i = 0; i < new_spec->path_segments.size(); ++i) {
     435           8 :         PathSegment *ps = new_spec->path_segments[i];
     436          28 :         for (size_t j = 0; j < ps->path_segment.size(); ++j) {
     437          20 :             if (ps->path_segment[j] == old_asn)
     438           0 :                 ps->path_segment[j] = asn;
     439             :         }
     440             :     }
     441           8 :     return new_spec;
     442             : }
     443             : 
     444             : //
     445             : // Create a new AsPath4ByteSpec by removing private asns.  Stop looking for private
     446             : // asns when we encounter the first public asn or the peer asn.
     447             : // If all is true, remove all private asns i.e. do not stop when we encounter
     448             : // the first public asn or the peer asn.
     449             : // If asn is non-zero, replace private asns instead of removing them. Use the
     450             : // nearest public asn as the replacement value.  If we haven't found a public
     451             : // asn, then use the given asn.
     452             : // If peer asn is non-zero, do not remove/replace it.
     453             : //
     454          24 : AsPath4ByteSpec *AsPath4ByteSpec::RemovePrivate(bool all, as_t asn, as_t peer_asn) const {
     455          24 :     bool remove_replace_done = false;
     456          24 :     AsPath4ByteSpec *new_spec = new AsPath4ByteSpec;
     457          48 :     for (size_t i = 0; i < path_segments.size(); ++i) {
     458          24 :         PathSegment *ps = path_segments[i];
     459          24 :         PathSegment *new_ps = new PathSegment;
     460             : 
     461             :         // We've already removed/replaced all private asns that we can.
     462             :         // Copy the entire segment instead of copying one as_t at a time.
     463          24 :         if (remove_replace_done) {
     464           0 :             *new_ps = *ps;
     465           0 :             new_spec->path_segments.push_back(new_ps);
     466           0 :             continue;
     467             :         }
     468             : 
     469             :         // Examine each as_t in the path segment to build a modified version.
     470             :         // Note down that we're done removing/replacing when we see a public
     471             :         // asn or the peer asn.
     472          24 :         new_ps->path_segment_type = ps->path_segment_type;
     473         100 :         for (size_t j = 0; j < ps->path_segment.size(); ++j) {
     474         152 :             if (remove_replace_done ||
     475         132 :                 !AsIsPrivate(ps->path_segment[j]) ||
     476          56 :                 ps->path_segment[j] == peer_asn) {
     477          20 :                 new_ps->path_segment.push_back(ps->path_segment[j]);
     478          20 :                 remove_replace_done = !all;
     479          20 :                 if (asn && !AsIsPrivate(ps->path_segment[j])) {
     480          16 :                     asn = ps->path_segment[j];
     481             :                 }
     482          56 :             } else if (asn) {
     483          40 :                 new_ps->path_segment.push_back(asn);
     484             :             }
     485             :         }
     486             : 
     487             :         // Get rid of the new path segment if it's empty.
     488             :         // Otherwise add it to the new spec.
     489          24 :         if (new_ps->path_segment.empty()) {
     490           4 :             delete new_ps;
     491             :         } else {
     492          20 :             new_spec->path_segments.push_back(new_ps);
     493             :         }
     494             :     }
     495             : 
     496          24 :     return new_spec;
     497             : }
     498             : 
     499         330 : void AsPath4Byte::Remove() {
     500         330 :     aspath_db_->Delete(this);
     501         330 : }
     502             : 
     503        9742 : AsPath4ByteDB::AsPath4ByteDB(BgpServer *server) {
     504        9742 : }
     505             : 
     506             : //
     507             : // Return the left most AS.
     508             : //
     509           0 : as_t As4PathSpec::AsLeftMost() const {
     510           0 :     if (path_segments.empty())
     511           0 :         return 0;
     512           0 :     if (path_segments[0]->path_segment_type == PathSegment::AS_SET)
     513           0 :         return 0;
     514           0 :     if (path_segments[0]->path_segment.empty())
     515           0 :         return 0;
     516           0 :     return (path_segments[0]->path_segment[0]);
     517             : }
     518             : 
     519             : //
     520             : // Return true if left most AS matches the input.
     521             : //
     522          60 : bool As4PathSpec::AsLeftMostMatch(as_t as) const {
     523          60 :     if (path_segments.empty())
     524           0 :         return false;
     525          60 :     if (path_segments[0]->path_segment.empty())
     526           0 :         return false;
     527          60 :     return (path_segments[0]->path_segment[0] == as);
     528             : }
     529             : 
     530             : //
     531             : // Return the left most public AS.
     532             : //
     533           0 : as_t As4PathSpec::AsLeftMostPublic() const {
     534           0 :     for (size_t i = 0; i < path_segments.size(); ++i) {
     535           0 :         PathSegment *ps = path_segments[i];
     536           0 :         for (size_t j = 0; j < path_segments[i]->path_segment.size(); ++j) {
     537           0 :             if (!AsIsPrivate(ps->path_segment[j]))
     538           0 :                 return ps->path_segment[j];
     539             :         }
     540             :     }
     541           0 :     return 0;
     542             : }
     543             : 
     544           1 : int As4PathSpec::CompareTo(const BgpAttribute &rhs_attr) const {
     545           1 :     int ret = BgpAttribute::CompareTo(rhs_attr);
     546           1 :     if (ret != 0) return ret;
     547           1 :     const As4PathSpec &rhs = static_cast<const As4PathSpec &>(rhs_attr);
     548           1 :     KEY_COMPARE(path_segments.size(), rhs.path_segments.size());
     549             : 
     550           2 :     for (size_t i = 0; i < path_segments.size(); i++) {
     551           1 :         int ret = path_segments[i]->CompareTo(*rhs.path_segments[i]);
     552           1 :         if (ret != 0) return ret;
     553             :     }
     554           1 :     return 0;
     555             : }
     556             : 
     557           4 : void As4PathSpec::ToCanonical(BgpAttr *attr) {
     558           4 :     attr->set_as4_path(this);
     559           4 : }
     560             : 
     561           9 : string As4PathSpec::ToString() const {
     562           9 :     ostringstream oss;
     563             : 
     564          18 :     for (size_t i = 0; i < path_segments.size(); i++) {
     565           9 :         if (i != 0) oss << " ";
     566           9 :         switch (path_segments[i]->path_segment_type) {
     567           0 :         case As4PathSpec::PathSegment::AS_SET:
     568           0 :             oss << "{";
     569           0 :             for (size_t j = 0; j < path_segments[i]->path_segment.size(); j++) {
     570           0 :                 if (j != 0) oss << " ";
     571           0 :                 oss << path_segments[i]->path_segment[j];
     572             :             }
     573           0 :             oss << "}";
     574           0 :             break;
     575           9 :         case As4PathSpec::PathSegment::AS_SEQUENCE:
     576          45 :             for (size_t j = 0; j < path_segments[i]->path_segment.size(); j++) {
     577          36 :                 if (j != 0) oss << " ";
     578          36 :                 oss << path_segments[i]->path_segment[j];
     579             :             }
     580           9 :             break;
     581           0 :         default:
     582           0 :             break;
     583             :         }
     584             :     }
     585             : 
     586          18 :     return oss.str();
     587           9 : }
     588             : 
     589          15 : size_t As4PathSpec::EncodeLength() const {
     590          15 :     size_t sz = 0;
     591          25 :     for (size_t i = 0; i < path_segments.size(); i++) {
     592          10 :         sz += 2;
     593          10 :         sz += path_segments[i]->path_segment.size() * 4;
     594             :     }
     595          15 :     return sz;
     596             : }
     597             : 
     598             : //
     599             : // Check As4PathSpec for loops for the given as.
     600             : // Return true if the number of occurrences of as exceeds given max loop count.
     601             : //
     602          20 : bool As4PathSpec::AsPathLoop(as_t as, uint8_t max_loop_count) const {
     603          20 :     uint8_t loop_count = 0;
     604          36 :     for (size_t i = 0; i < path_segments.size(); ++i) {
     605          64 :         for (size_t j = 0; j < path_segments[i]->path_segment.size(); ++j) {
     606          48 :             if (path_segments[i]->path_segment[j] == as &&
     607             :                 ++loop_count > max_loop_count) {
     608           4 :                 return true;
     609             :             }
     610             :         }
     611             :     }
     612          16 :     return false;
     613             : }
     614             : 
     615             : //
     616             : // Create a new As4PathSpec by prepending the given asn at the beginning.
     617             : //
     618         247 : As4PathSpec *As4PathSpec::Add(as_t asn) const {
     619         247 :     vector<as_t> asn_list = list_of(asn);
     620         494 :     return Add(asn_list);
     621         247 : }
     622             : 
     623             : //
     624             : // Create a new As4PathSpec by prepending the given vector of asns at the
     625             : // beginning.
     626             : //
     627         247 : As4PathSpec *As4PathSpec::Add(const vector<as_t> &asn_list) const {
     628         247 :     As4PathSpec *new_spec = new As4PathSpec;
     629         247 :     PathSegment *ps = new PathSegment;
     630         247 :     ps->path_segment_type = PathSegment::AS_SEQUENCE;
     631         247 :     ps->path_segment = asn_list;
     632         247 :     size_t first = 0;
     633         247 :     size_t last = path_segments.size();
     634         469 :     if (last &&
     635         469 :         path_segments[0]->path_segment_type == PathSegment::AS_SEQUENCE &&
     636         222 :         path_segments[0]->path_segment.size() + asn_list.size() <= 255) {
     637         222 :         copy(path_segments[0]->path_segment.begin(),
     638         222 :              path_segments[0]->path_segment.end(),
     639         222 :              back_inserter(ps->path_segment));
     640         222 :         new_spec->path_segments.push_back(ps);
     641         222 :         first++;
     642             :     } else {
     643          25 :         new_spec->path_segments.push_back(ps);
     644             :     }
     645         247 :     if (first == last)
     646         231 :         return new_spec;
     647          32 :     for (size_t idx = first; idx < last; ++idx) {
     648          16 :         PathSegment *ps = new PathSegment;
     649          16 :         *ps = *path_segments[idx];
     650          16 :         new_spec->path_segments.push_back(ps);
     651             :     }
     652          16 :     return new_spec;
     653             : }
     654             : 
     655             : //
     656             : // Create a new As4PathSpec by replacing the old asn with given asn.
     657             : //
     658          12 : As4PathSpec *As4PathSpec::Replace(as_t old_asn, as_t asn) const {
     659          12 :     As4PathSpec *new_spec = new As4PathSpec(*this);
     660          24 :     for (size_t i = 0; i < new_spec->path_segments.size(); ++i) {
     661          12 :         PathSegment *ps = new_spec->path_segments[i];
     662          30 :         for (size_t j = 0; j < ps->path_segment.size(); ++j) {
     663          18 :             if (ps->path_segment[j] == old_asn)
     664           6 :                 ps->path_segment[j] = asn;
     665             :         }
     666             :     }
     667          12 :     return new_spec;
     668             : }
     669             : 
     670             : //
     671             : // Create a new As4PathSpec by removing private asns.  Stop looking for private
     672             : // asns when we encounter the first public asn or the peer asn.
     673             : // If all is true, remove all private asns i.e. do not stop when we encounter
     674             : // the first public asn or the peer asn.
     675             : // If asn is non-zero, replace private asns instead of removing them. Use the
     676             : // nearest public asn as the replacement value.  If we haven't found a public
     677             : // asn, then use the given asn.
     678             : // If peer asn is non-zero, do not remove/replace it.
     679             : //
     680          16 : As4PathSpec *As4PathSpec::RemovePrivate(bool all, as_t asn, as_t peer_asn) const {
     681          16 :     bool remove_replace_done = false;
     682          16 :     As4PathSpec *new_spec = new As4PathSpec;
     683          32 :     for (size_t i = 0; i < path_segments.size(); ++i) {
     684          16 :         PathSegment *ps = path_segments[i];
     685          16 :         PathSegment *new_ps = new PathSegment;
     686             : 
     687             :         // We've already removed/replaced all private asns that we can.
     688             :         // Copy the entire segment instead of copying one as_t at a time.
     689          16 :         if (remove_replace_done) {
     690           0 :             *new_ps = *ps;
     691           0 :             new_spec->path_segments.push_back(new_ps);
     692           0 :             continue;
     693             :         }
     694             : 
     695             :         // Examine each as_t in the path segment to build a modified version.
     696             :         // Note down that we're done removing/replacing when we see a public
     697             :         // asn or the peer asn.
     698          16 :         new_ps->path_segment_type = ps->path_segment_type;
     699          72 :         for (size_t j = 0; j < ps->path_segment.size(); ++j) {
     700         112 :             if (remove_replace_done ||
     701          76 :                 !AsIsPrivate(ps->path_segment[j]) ||
     702          20 :                 ps->path_segment[j] == peer_asn) {
     703          36 :                 new_ps->path_segment.push_back(ps->path_segment[j]);
     704          36 :                 remove_replace_done = !all;
     705          36 :                 if (asn && !AsIsPrivate(ps->path_segment[j])) {
     706          36 :                     asn = ps->path_segment[j];
     707             :                 }
     708          20 :             } else if (asn) {
     709          20 :                 new_ps->path_segment.push_back(asn);
     710             :             }
     711             :         }
     712             : 
     713             :         // Get rid of the new path segment if it's empty.
     714             :         // Otherwise add it to the new spec.
     715          16 :         if (new_ps->path_segment.empty()) {
     716           0 :             delete new_ps;
     717             :         } else {
     718          16 :             new_spec->path_segments.push_back(new_ps);
     719             :         }
     720             :     }
     721             : 
     722          16 :     return new_spec;
     723             : }
     724             : 
     725         441 : void As4Path::Remove() {
     726         441 :     aspath_db_->Delete(this);
     727         441 : }
     728             : 
     729        9742 : As4PathDB::As4PathDB(BgpServer *server) {
     730        9742 : }