1
1
// -*- c-basic-offset: 4; tab-width: 8; indent-tabs-mode: t -*-
3
// Copyright (c) 2001-2007 International Computer Science Institute
3
// Copyright (c) 2001-2008 International Computer Science Institute
5
5
// Permission is hereby granted, free of charge, to any person obtaining a
6
6
// copy of this software and associated documentation files (the "Software")
12
12
// notice is a summary of the XORP LICENSE file; the license in that file is
13
13
// legally binding.
15
#ident "$XORP: xorp/bgp/aspath.cc,v 1.40 2007/04/05 02:02:48 zec Exp $"
15
#ident "$XORP: xorp/bgp/aspath.cc,v 1.42 2008/01/04 03:15:17 pavlin Exp $"
17
// #define DEBUG_LOGGING
18
// #define DEBUG_PRINT_FUNCTION_NAME
17
//#define DEBUG_LOGGING
18
//#define DEBUG_PRINT_FUNCTION_NAME
20
20
#include "bgp_module.h"
43
43
extern void dump_bytes(const uint8_t *d, uint8_t l);
45
/* *************** AsSegment ********************** */
45
/* *************** ASSegment ********************** */
48
48
* Convert the external representation into the internal one.
49
49
* _type is d[0], _entries is d[1], entries follow.
52
AsSegment::decode(const uint8_t *d) throw(CorruptMessage)
52
ASSegment::decode(const uint8_t *d) throw(CorruptMessage)
76
76
* Convert from internal to external representation.
79
AsSegment::encode(size_t &len, uint8_t *data) const
79
ASSegment::encode(size_t &len, uint8_t *data) const
81
81
debug_msg("AsSegment encode\n");
82
82
XLOG_ASSERT(_aslist.size() <= 255);
243
243
* Compares internal representations for <.
246
AsSegment::operator<(const AsSegment& him) const
246
ASSegment::operator<(const ASSegment& him) const
248
248
int mysize = _aslist.size();
249
249
int hissize = him._aslist.size();
257
257
// XXX isn't this the same format as on the wire ???
260
AsSegment::encode_for_mib(uint8_t* buf, size_t buf_size) const
260
ASSegment::encode_for_mib(uint8_t* buf, size_t buf_size) const
262
262
//See RFC 1657, Page 15 for the encoding
263
263
XLOG_ASSERT(buf_size >= (2 + _aslist.size() * 2));
326
326
* Convert from internal to external AS4_PATH representation.
329
As4Segment::encode(size_t &len, uint8_t *data) const
329
AS4Segment::encode(size_t &len, uint8_t *data) const
331
debug_msg("AsSegment encode\n");
331
debug_msg("AS4Segment encode\n");
332
332
XLOG_ASSERT(_aslist.size() <= 255);
334
334
size_t i = wire_size();
356
/* *************** AsPath *********************** */
356
/* *************** ASPath *********************** */
359
* AsPath constructor by parsing strings. Input strings
359
* ASPath constructor by parsing strings. Input strings
360
360
* should have the form
362
362
* "segment, segment, segment, ... ,segment"
371
371
* blank spaces " " can appear at any point in the string.
374
AsPath::AsPath(const char *as_path) throw(InvalidString)
374
ASPath::ASPath(const char *as_path) throw(InvalidString)
376
debug_msg("AsPath(%s) constructor called\n", as_path);
376
debug_msg("ASPath(%s) constructor called\n", as_path);
377
377
_num_segments = 0;
396
396
if (seg.type() == AS_NONE) // possibly start new segment
397
397
seg.set_type(AS_SEQUENCE);
399
while (i < path.length() && xorp_isdigit(path[i]))
399
while (i < path.length() && (xorp_isdigit(path[i]) || path[i]=='.')) {
402
uint16_t num = atoi(path.substr(start, i).c_str());
403
string asnum = path.substr(start, i-start);
403
404
i--; // back to last valid character
404
debug_msg("asnum = %d\n", num);
405
seg.add_as(AsNum(num));
405
debug_msg("asnum = %s\n", asnum.c_str());
406
seg.add_as(AsNum(asnum));
406
407
} else if (c == '[') {
407
408
if (seg.type() == AS_SEQUENCE) {
408
409
// push previous thing and start a new one
490
491
add_segment(seg);
491
492
else if (seg.type() == AS_SET)
492
493
xorp_throw(InvalidString,
493
c_format("Unterminated AsSet: %s", path.c_str()));
494
debug_msg("end of AsPath()\n");
494
c_format("Unterminated ASSet: %s", path.c_str()));
495
debug_msg("end of ASPath()\n");
498
* populate an AsPath from the received data representation
499
* populate an ASPath from the received data representation
501
AsPath::decode(const uint8_t *d, size_t l) throw(CorruptMessage)
502
ASPath::decode(const uint8_t *d, size_t l) throw(CorruptMessage)
503
504
_num_segments = 0;
521
* construct a new aggregate AsPath from two AsPaths
522
* construct a new aggregate ASPath from two ASPaths
523
AsPath::AsPath(const AsPath &asp1, const AsPath &asp2)
524
ASPath::ASPath(const ASPath &asp1, const ASPath &asp2)
525
526
_num_segments = 0;
547
AsSegment newseg(asp1.segment(curseg).type());
548
ASSegment newseg(asp1.segment(curseg).type());
548
549
for (size_t elem = 0; elem < matchelem; elem++)
549
550
newseg.add_as(asp1.segment(curseg).as_num(elem));
550
551
this->add_segment(newseg);
676
AsPath::prepend_as(const AsNum &asn)
677
ASPath::prepend_as(const AsNum &asn)
678
679
if (_segments.empty() || _segments.front().type() == AS_SET) {
679
AsSegment seg = AsSegment(AS_SEQUENCE);
680
ASSegment seg = ASSegment(AS_SEQUENCE);
682
683
_segments.push_front(seg);
692
AsPath::prepend_confed_as(const AsNum &asn)
693
ASPath::prepend_confed_as(const AsNum &asn)
694
695
if (_segments.empty() || _segments.front().type() == AS_SET
695
696
|| _segments.front().type() == AS_SEQUENCE) {
696
AsSegment seg = AsSegment(AS_CONFED_SEQUENCE);
697
ASSegment seg = ASSegment(AS_CONFED_SEQUENCE);
699
700
_segments.push_front(seg);
741
ASPath::operator=(const ASPath& him)
744
while (!_segments.empty()) {
745
_segments.pop_front();
750
for (i = him._segments.begin() ;i != him._segments.end(); i++) {
751
_segments.push_back(*i);
740
AsPath::operator==(const AsPath& him) const
757
ASPath::operator==(const ASPath& him) const
742
759
if (_num_segments != him._num_segments)
771
AsPath::encode_for_mib(vector<uint8_t>& encode_buf) const
788
ASPath::encode_for_mib(vector<uint8_t>& encode_buf) const
773
790
//See RFC 1657, Page 15 for the encoding.
774
791
size_t buf_size = wire_size();
824
ASPath::merge_as4_path(AS4Path& as4_path)
826
as4_path.cross_validate(*this);
807
As4Path::As4Path(const uint8_t* d, size_t len, const AsPath& as_path)
831
AS4Path::AS4Path(const uint8_t* d, size_t len, const ASPath& as_path)
808
832
throw(CorruptMessage)
811
835
cross_validate(as_path);
840
AS4Path::AS4Path(const uint8_t* d, size_t len)
841
throw(CorruptMessage)
815
* populate a AsPath from the received data representation from a
847
* populate a ASPath from the received data representation from a
816
848
* AS4_PATH attribute.
819
As4Path::decode(const uint8_t *d, size_t l) throw(CorruptMessage)
851
AS4Path::decode(const uint8_t *d, size_t l) throw(CorruptMessage)
821
853
_num_segments = 0;
840
void As4Path::cross_validate(const AsPath& as_path)
872
void AS4Path::cross_validate(const ASPath& as_path)
874
debug_msg("cross validate\n%s\n%s\n", str().c_str(), as_path.str().c_str());
842
876
if (as_path.path_length() < path_length() ) {
877
debug_msg("as_path.path_length() < path_length()\n");
843
878
// This is illegal. The spec says to ignore the AS4_PATH
844
879
// attribute and use the data from the AS_PATH attribute throw
845
880
// away the data we had.
847
882
_segments.pop_front();
849
884
// copy in from the AS_PATH version
850
for (uint32_t i = 0; i < as_path.path_length(); i++) {
885
for (uint32_t i = 0; i < as_path.num_segments(); i++) {
886
debug_msg("adding %u %s\n", i, as_path.segment(i).str().c_str());
851
887
add_segment(as_path.segment(i));
867
903
// The AS_PATH has at least as many segments as the
868
904
// AS4_PATH find where they differ, and copy across.
869
905
for (uint32_t i = 1; i <= num_segments(); i++) {
870
const AsSegment *old_seg;
906
const ASSegment *old_seg;
872
908
old_seg = &(as_path.segment(as_path.num_segments() - i));
873
new_seg = const_cast<AsSegment*>(&(segment(num_segments() - i)));
909
new_seg = const_cast<ASSegment*>(&(segment(num_segments() - i)));
910
printf("old seg: %s\n", old_seg->str().c_str());
911
printf("new seg: %s\n", new_seg->str().c_str());
874
912
if (old_seg->path_length() == new_seg->path_length())
876
914
if (old_seg->path_length() < new_seg->path_length()) {
877
915
// ooops - WTF happened here
916
debug_msg("do patchup\n");
878
917
do_patchup(as_path);
880
919
if (old_seg->path_length() > new_seg->path_length()) {
881
920
// found a segment that needs data copying over
921
debug_msg("pad segment\n");
922
printf("new_seg type: %u\n", new_seg->type());
882
923
pad_segment(*old_seg, *new_seg);
927
debug_msg("after patching: \n");
928
debug_msg("old as_path (len %u): %s\n", (uint32_t)as_path.path_length(), as_path.str().c_str());
929
debug_msg("new as_path (len %u): %s\n", (uint32_t)path_length(), str().c_str());
886
930
if (as_path.path_length() == path_length()) {
902
void As4Path::pad_segment(const AsSegment& old_seg, AsSegment& new_seg)
946
void AS4Path::pad_segment(const ASSegment& old_seg, ASSegment& new_seg)
948
debug_msg("pad: new type: %u\n", new_seg.type());
904
949
if (new_seg.type() == AS_SET) {
950
debug_msg("new == AS_SET\n");
905
951
// find everything in the old seg that's not in the new seg,
907
953
for (int i = old_seg.as_size()-1; i >= 0; i--) {
922
968
if (old_seg.type() == AS_SET) {
969
debug_msg("old == AS_SET\n");
923
970
// The old segment was an AS_SET, but the new isn't. Looks
924
971
// like some old BGP speaker did some form of aggregation.
925
972
// Convert the new one to an AS_SET too.
978
debug_msg("both are sequences\n");
931
979
// They're both AS_SEQUENCES, so we need to preserve sequence.
932
980
// First validate that new_seg is a sub-sequence of old_seg
933
981
for (uint32_t i = 1; i <= new_seg.as_size(); i++) {
934
982
const AsNum *old_asn = &(old_seg.as_num(old_seg.as_size()-i));
935
983
const AsNum *new_asn = &(new_seg.as_num(new_seg.as_size()-i));
936
if (*old_asn != *new_asn) {
984
debug_msg("old_asn: %s, new_asn: %s\n", old_asn->str().c_str(), new_asn->str().c_str());
985
// do a compare on the 16-bit compat versions of the numbers
986
if (old_asn->as() != new_asn->as()) {
987
debug_msg("Mismatch\n");
937
988
// We've got a mismatch - make it into an AS_SET. This is
938
989
// a pretty arbitrary decision, but this shouldn't happen
939
990
// in reality. At least it should be safe.
946
997
// now we can simply copy across the missing AS numbers
947
998
for (int i = old_seg.as_size() - new_seg.as_size() - 1; i >= 0; i--) {
948
999
new_seg.prepend_as(old_seg.as_num(i));
953
void As4Path::do_patchup(const AsPath& as_path)
1005
void AS4Path::do_patchup(const ASPath& as_path)
955
1007
// we get here when the cross validation fails, and we need to do
956
1008
// something that isn't actually illegal.
960
1012
// previously in the AS4_PATH. This at least should prevent
961
1013
// loops forming, but it's really ugly.
963
AsSegment new_set(AS_SET);
1015
ASSegment new_set(AS_SET);
964
1016
for (uint32_t i = 0; i < as_path.path_length(); i++) {
965
const AsSegment *s = &(as_path.segment(i));
1017
const ASSegment *s = &(as_path.segment(i));
966
1018
for (uint32_t j = 0; j < s->path_length(); j++) {
967
1019
const AsNum *asn = &(s->as_num(j));
968
1020
if (asn->as() == AsNum::AS_TRAN)
999
As4Path::encode(size_t &len, uint8_t *buf) const
1051
AS4Path::encode(size_t &len, uint8_t *buf) const
1053
debug_msg("AS4Path::encode\n");
1001
1054
XLOG_ASSERT(_num_segments == _segments.size()); // XXX expensive
1002
1055
const_iterator i;
1003
1056
size_t pos, l = wire_size();
1012
1065
// encode into the buffer
1013
1066
for (pos = 0, i = _segments.begin(); i != _segments.end(); ++i) {
1014
const As4Segment *new_seg = (const As4Segment*)(&(*i));
1067
const AS4Segment *new_seg = (const AS4Segment*)(&(*i));
1015
1068
l = new_seg->wire_size();
1016
1069
new_seg->encode(l, buf + pos);
1024
As4Path::wire_size() const
1077
AS4Path::wire_size() const
1027
1080
const_iterator i;
1029
1082
for (i = _segments.begin(); i != _segments.end(); ++i) {
1030
const As4Segment *new_seg = (const As4Segment*)(&(*i));
1083
const AS4Segment *new_seg = (const AS4Segment*)(&(*i));
1031
1084
l += new_seg->wire_size();
added
removed
bgp/aspath.cc
