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