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