]>
Commit | Line | Data |
---|---|---|
1 | // SPDX-License-Identifier: GPL-2.0-or-later | |
2 | /* AS path management routines. | |
3 | * Copyright (C) 1996, 97, 98, 99 Kunihiro Ishiguro | |
4 | * Copyright (C) 2005 Sun Microsystems, Inc. | |
5 | */ | |
6 | ||
7 | #include <zebra.h> | |
8 | ||
9 | #include "hash.h" | |
10 | #include "memory.h" | |
11 | #include "vector.h" | |
12 | #include "log.h" | |
13 | #include "stream.h" | |
14 | #include "command.h" | |
15 | #include "jhash.h" | |
16 | #include "queue.h" | |
17 | #include "filter.h" | |
18 | ||
19 | #include "bgpd/bgpd.h" | |
20 | #include "bgpd/bgp_aspath.h" | |
21 | #include "bgpd/bgp_debug.h" | |
22 | #include "bgpd/bgp_attr.h" | |
23 | #include "bgpd/bgp_errors.h" | |
24 | ||
25 | /* Attr. Flags and Attr. Type Code. */ | |
26 | #define AS_HEADER_SIZE 2 | |
27 | ||
28 | /* Now FOUR octets are used for AS value. */ | |
29 | #define AS_VALUE_SIZE sizeof(as_t) | |
30 | /* This is the old one */ | |
31 | #define AS16_VALUE_SIZE sizeof(as16_t) | |
32 | ||
33 | /* Maximum protocol segment length value */ | |
34 | #define AS_SEGMENT_MAX 255 | |
35 | ||
36 | /* The following length and size macros relate specifically to Quagga's | |
37 | * internal representation of AS-Segments, not per se to the on-wire | |
38 | * sizes and lengths. At present (200508) they sort of match, however | |
39 | * the ONLY functions which should now about the on-wire syntax are | |
40 | * aspath_put, assegment_put and assegment_parse. | |
41 | * | |
42 | * aspath_put returns bytes written, the only definitive record of | |
43 | * size of wire-format attribute.. | |
44 | */ | |
45 | ||
46 | /* Calculated size in bytes of ASN segment data to hold N ASN's */ | |
47 | #define ASSEGMENT_DATA_SIZE(N, S) \ | |
48 | ((N) * ((S) ? AS_VALUE_SIZE : AS16_VALUE_SIZE)) | |
49 | ||
50 | /* Calculated size of segment struct to hold N ASN's */ | |
51 | #define ASSEGMENT_SIZE(N,S) (AS_HEADER_SIZE + ASSEGMENT_DATA_SIZE (N,S)) | |
52 | ||
53 | /* AS segment octet length. */ | |
54 | #define ASSEGMENT_LEN(X,S) ASSEGMENT_SIZE((X)->length,S) | |
55 | ||
56 | /* AS_SEQUENCE segments can be packed together */ | |
57 | /* Can the types of X and Y be considered for packing? */ | |
58 | #define ASSEGMENT_TYPES_PACKABLE(X, Y) \ | |
59 | (((X)->type == (Y)->type) && ((X)->type == AS_SEQUENCE)) | |
60 | /* Types and length of X,Y suitable for packing? */ | |
61 | #define ASSEGMENTS_PACKABLE(X, Y) \ | |
62 | (ASSEGMENT_TYPES_PACKABLE((X), (Y)) \ | |
63 | && (((X)->length + (Y)->length) <= AS_SEGMENT_MAX)) | |
64 | ||
65 | /* As segment header - the on-wire representation | |
66 | * NOT the internal representation! | |
67 | */ | |
68 | struct assegment_header { | |
69 | uint8_t type; | |
70 | uint8_t length; | |
71 | }; | |
72 | ||
73 | /* Hash for aspath. This is the top level structure of AS path. */ | |
74 | static struct hash *ashash; | |
75 | ||
76 | /* Stream for SNMP. See aspath_snmp_pathseg */ | |
77 | static struct stream *snmp_stream; | |
78 | ||
79 | /* Callers are required to initialize the memory */ | |
80 | static as_t *assegment_data_new(int num) | |
81 | { | |
82 | return (XMALLOC(MTYPE_AS_SEG_DATA, ASSEGMENT_DATA_SIZE(num, 1))); | |
83 | } | |
84 | ||
85 | static void assegment_data_free(as_t *asdata) | |
86 | { | |
87 | XFREE(MTYPE_AS_SEG_DATA, asdata); | |
88 | } | |
89 | ||
90 | const char *const aspath_segment_type_str[] = { | |
91 | "as-invalid", "as-set", "as-sequence", "as-confed-sequence", | |
92 | "as-confed-set" | |
93 | }; | |
94 | ||
95 | /* Get a new segment. Note that 0 is an allowed length, | |
96 | * and will result in a segment with no allocated data segment. | |
97 | * the caller should immediately assign data to the segment, as the segment | |
98 | * otherwise is not generally valid | |
99 | */ | |
100 | static struct assegment *assegment_new(uint8_t type, unsigned short length) | |
101 | { | |
102 | struct assegment *new; | |
103 | ||
104 | new = XCALLOC(MTYPE_AS_SEG, sizeof(struct assegment)); | |
105 | ||
106 | if (length) | |
107 | new->as = assegment_data_new(length); | |
108 | ||
109 | new->length = length; | |
110 | new->type = type; | |
111 | ||
112 | return new; | |
113 | } | |
114 | ||
115 | static void assegment_free(struct assegment *seg) | |
116 | { | |
117 | if (!seg) | |
118 | return; | |
119 | ||
120 | assegment_data_free(seg->as); | |
121 | memset(seg, 0xfe, sizeof(struct assegment)); | |
122 | XFREE(MTYPE_AS_SEG, seg); | |
123 | ||
124 | return; | |
125 | } | |
126 | ||
127 | /* free entire chain of segments */ | |
128 | static void assegment_free_all(struct assegment *seg) | |
129 | { | |
130 | struct assegment *prev; | |
131 | ||
132 | while (seg) { | |
133 | prev = seg; | |
134 | seg = seg->next; | |
135 | assegment_free(prev); | |
136 | } | |
137 | } | |
138 | ||
139 | /* Duplicate just the given assegment and its data */ | |
140 | static struct assegment *assegment_dup(struct assegment *seg) | |
141 | { | |
142 | struct assegment *new; | |
143 | ||
144 | new = assegment_new(seg->type, seg->length); | |
145 | memcpy(new->as, seg->as, ASSEGMENT_DATA_SIZE(new->length, 1)); | |
146 | ||
147 | return new; | |
148 | } | |
149 | ||
150 | /* Duplicate entire chain of assegments, return the head */ | |
151 | static struct assegment *assegment_dup_all(struct assegment *seg) | |
152 | { | |
153 | struct assegment *new = NULL; | |
154 | struct assegment *head = NULL; | |
155 | ||
156 | while (seg) { | |
157 | if (head) { | |
158 | new->next = assegment_dup(seg); | |
159 | new = new->next; | |
160 | } else | |
161 | head = new = assegment_dup(seg); | |
162 | ||
163 | seg = seg->next; | |
164 | } | |
165 | return head; | |
166 | } | |
167 | ||
168 | /* prepend the as number to given segment, given num of times */ | |
169 | static struct assegment *assegment_prepend_asns(struct assegment *seg, | |
170 | as_t asnum, int num) | |
171 | { | |
172 | as_t *newas; | |
173 | int i; | |
174 | ||
175 | if (!num) | |
176 | return seg; | |
177 | ||
178 | if (num >= AS_SEGMENT_MAX) | |
179 | return seg; /* we don't do huge prepends */ | |
180 | ||
181 | newas = assegment_data_new(seg->length + num); | |
182 | if (newas == NULL) | |
183 | return seg; | |
184 | ||
185 | for (i = 0; i < num; i++) | |
186 | newas[i] = asnum; | |
187 | ||
188 | memcpy(newas + num, seg->as, ASSEGMENT_DATA_SIZE(seg->length, 1)); | |
189 | assegment_data_free(seg->as); | |
190 | seg->as = newas; | |
191 | seg->length += num; | |
192 | ||
193 | return seg; | |
194 | } | |
195 | ||
196 | /* append given array of as numbers to the segment */ | |
197 | static struct assegment *assegment_append_asns(struct assegment *seg, | |
198 | as_t *asnos, int num) | |
199 | { | |
200 | as_t *newas; | |
201 | ||
202 | if (!seg) | |
203 | return seg; | |
204 | ||
205 | newas = XREALLOC(MTYPE_AS_SEG_DATA, seg->as, | |
206 | ASSEGMENT_DATA_SIZE(seg->length + num, 1)); | |
207 | ||
208 | seg->as = newas; | |
209 | memcpy(seg->as + seg->length, asnos, | |
210 | ASSEGMENT_DATA_SIZE(num, 1)); | |
211 | seg->length += num; | |
212 | return seg; | |
213 | } | |
214 | ||
215 | static int int_cmp(const void *p1, const void *p2) | |
216 | { | |
217 | const as_t *as1 = p1; | |
218 | const as_t *as2 = p2; | |
219 | ||
220 | return (*as1 == *as2) ? 0 : ((*as1 > *as2) ? 1 : -1); | |
221 | } | |
222 | ||
223 | /* normalise the segment. | |
224 | * In particular, merge runs of AS_SEQUENCEs into one segment | |
225 | * Internally, we do not care about the wire segment length limit, and | |
226 | * we want each distinct AS_PATHs to have the exact same internal | |
227 | * representation - eg, so that our hashing actually works.. | |
228 | */ | |
229 | static struct assegment *assegment_normalise(struct assegment *head) | |
230 | { | |
231 | struct assegment *seg = head, *pin; | |
232 | struct assegment *tmp; | |
233 | ||
234 | if (!head) | |
235 | return head; | |
236 | ||
237 | while (seg) { | |
238 | pin = seg; | |
239 | ||
240 | /* Sort values SET segments, for determinism in paths to aid | |
241 | * creation of hash values / path comparisons | |
242 | * and because it helps other lesser implementations ;) | |
243 | */ | |
244 | if (seg->type == AS_SET || seg->type == AS_CONFED_SET) { | |
245 | int tail = 0; | |
246 | int i; | |
247 | ||
248 | qsort(seg->as, seg->length, sizeof(as_t), int_cmp); | |
249 | ||
250 | /* weed out dupes */ | |
251 | for (i = 1; i < seg->length; i++) { | |
252 | if (seg->as[tail] == seg->as[i]) | |
253 | continue; | |
254 | ||
255 | tail++; | |
256 | if (tail < i) | |
257 | seg->as[tail] = seg->as[i]; | |
258 | } | |
259 | /* seg->length can be 0.. */ | |
260 | if (seg->length) | |
261 | seg->length = tail + 1; | |
262 | } | |
263 | ||
264 | /* read ahead from the current, pinned segment while the | |
265 | * segments | |
266 | * are packable/mergeable. Append all following packable | |
267 | * segments | |
268 | * to the segment we have pinned and remove these appended | |
269 | * segments. | |
270 | */ | |
271 | while (pin->next && ASSEGMENT_TYPES_PACKABLE(pin, pin->next)) { | |
272 | tmp = pin->next; | |
273 | seg = pin->next; | |
274 | ||
275 | /* append the next sequence to the pinned sequence */ | |
276 | pin = assegment_append_asns(pin, seg->as, seg->length); | |
277 | ||
278 | /* bypass the next sequence */ | |
279 | pin->next = seg->next; | |
280 | ||
281 | /* get rid of the now referenceless segment */ | |
282 | assegment_free(tmp); | |
283 | } | |
284 | ||
285 | seg = pin->next; | |
286 | } | |
287 | return head; | |
288 | } | |
289 | ||
290 | static struct aspath *aspath_new(enum asnotation_mode asnotation) | |
291 | { | |
292 | struct aspath *as; | |
293 | ||
294 | as = XCALLOC(MTYPE_AS_PATH, sizeof(struct aspath)); | |
295 | as->asnotation = asnotation; | |
296 | return as; | |
297 | } | |
298 | ||
299 | /* Free AS path structure. */ | |
300 | void aspath_free(struct aspath *aspath) | |
301 | { | |
302 | if (!aspath) | |
303 | return; | |
304 | if (aspath->segments) | |
305 | assegment_free_all(aspath->segments); | |
306 | XFREE(MTYPE_AS_STR, aspath->str); | |
307 | ||
308 | if (aspath->json) { | |
309 | json_object_free(aspath->json); | |
310 | aspath->json = NULL; | |
311 | } | |
312 | ||
313 | XFREE(MTYPE_AS_PATH, aspath); | |
314 | } | |
315 | ||
316 | /* Unintern aspath from AS path bucket. */ | |
317 | void aspath_unintern(struct aspath **aspath) | |
318 | { | |
319 | struct aspath *ret; | |
320 | struct aspath *asp; | |
321 | ||
322 | if (!*aspath) | |
323 | return; | |
324 | ||
325 | asp = *aspath; | |
326 | ||
327 | if (asp->refcnt) | |
328 | asp->refcnt--; | |
329 | ||
330 | if (asp->refcnt == 0) { | |
331 | /* This aspath must exist in aspath hash table. */ | |
332 | ret = hash_release(ashash, asp); | |
333 | assert(ret != NULL); | |
334 | aspath_free(asp); | |
335 | *aspath = NULL; | |
336 | } | |
337 | } | |
338 | ||
339 | /* Return the start or end delimiters for a particular Segment type */ | |
340 | #define AS_SEG_START 0 | |
341 | #define AS_SEG_END 1 | |
342 | static char aspath_delimiter_char(uint8_t type, uint8_t which) | |
343 | { | |
344 | int i; | |
345 | struct { | |
346 | int type; | |
347 | char start; | |
348 | char end; | |
349 | } aspath_delim_char[] = {{AS_SET, '{', '}'}, | |
350 | {AS_CONFED_SET, '[', ']'}, | |
351 | {AS_CONFED_SEQUENCE, '(', ')'}, | |
352 | {0}}; | |
353 | ||
354 | for (i = 0; aspath_delim_char[i].type != 0; i++) { | |
355 | if (aspath_delim_char[i].type == type) { | |
356 | if (which == AS_SEG_START) | |
357 | return aspath_delim_char[i].start; | |
358 | else if (which == AS_SEG_END) | |
359 | return aspath_delim_char[i].end; | |
360 | } | |
361 | } | |
362 | return ' '; | |
363 | } | |
364 | ||
365 | /* countup asns from this segment and index onward */ | |
366 | static int assegment_count_asns(struct assegment *seg, int from) | |
367 | { | |
368 | int count = 0; | |
369 | while (seg) { | |
370 | if (!from) | |
371 | count += seg->length; | |
372 | else { | |
373 | count += (seg->length - from); | |
374 | from = 0; | |
375 | } | |
376 | seg = seg->next; | |
377 | } | |
378 | return count; | |
379 | } | |
380 | ||
381 | unsigned int aspath_count_confeds(struct aspath *aspath) | |
382 | { | |
383 | int count = 0; | |
384 | struct assegment *seg = aspath->segments; | |
385 | ||
386 | while (seg) { | |
387 | if (seg->type == AS_CONFED_SEQUENCE) | |
388 | count += seg->length; | |
389 | else if (seg->type == AS_CONFED_SET) | |
390 | count++; | |
391 | ||
392 | seg = seg->next; | |
393 | } | |
394 | return count; | |
395 | } | |
396 | ||
397 | unsigned int aspath_count_hops(const struct aspath *aspath) | |
398 | { | |
399 | int count = 0; | |
400 | struct assegment *seg = aspath->segments; | |
401 | ||
402 | while (seg) { | |
403 | if (seg->type == AS_SEQUENCE) | |
404 | count += seg->length; | |
405 | else if (seg->type == AS_SET) | |
406 | count++; | |
407 | ||
408 | seg = seg->next; | |
409 | } | |
410 | return count; | |
411 | } | |
412 | ||
413 | /* Check if aspath has AS_SET or AS_CONFED_SET */ | |
414 | bool aspath_check_as_sets(struct aspath *aspath) | |
415 | { | |
416 | struct assegment *seg = aspath->segments; | |
417 | ||
418 | while (seg) { | |
419 | if (seg->type == AS_SET || seg->type == AS_CONFED_SET) | |
420 | return true; | |
421 | seg = seg->next; | |
422 | } | |
423 | return false; | |
424 | } | |
425 | ||
426 | /* Check if aspath has BGP_AS_ZERO */ | |
427 | bool aspath_check_as_zero(struct aspath *aspath) | |
428 | { | |
429 | struct assegment *seg = aspath->segments; | |
430 | unsigned int i; | |
431 | ||
432 | while (seg) { | |
433 | for (i = 0; i < seg->length; i++) | |
434 | if (seg->as[i] == BGP_AS_ZERO) | |
435 | return true; | |
436 | seg = seg->next; | |
437 | } | |
438 | ||
439 | return false; | |
440 | } | |
441 | ||
442 | /* Estimate size aspath /might/ take if encoded into an | |
443 | * ASPATH attribute. | |
444 | * | |
445 | * This is a quick estimate, not definitive! aspath_put() | |
446 | * may return a different number!! | |
447 | */ | |
448 | unsigned int aspath_size(struct aspath *aspath) | |
449 | { | |
450 | int size = 0; | |
451 | struct assegment *seg = aspath->segments; | |
452 | ||
453 | while (seg) { | |
454 | size += ASSEGMENT_SIZE(seg->length, 1); | |
455 | seg = seg->next; | |
456 | } | |
457 | return size; | |
458 | } | |
459 | ||
460 | /* Return highest public ASN in path */ | |
461 | as_t aspath_highest(struct aspath *aspath) | |
462 | { | |
463 | struct assegment *seg = aspath->segments; | |
464 | as_t highest = 0; | |
465 | unsigned int i; | |
466 | ||
467 | while (seg) { | |
468 | for (i = 0; i < seg->length; i++) | |
469 | if (seg->as[i] > highest | |
470 | && !BGP_AS_IS_PRIVATE(seg->as[i])) | |
471 | highest = seg->as[i]; | |
472 | seg = seg->next; | |
473 | } | |
474 | return highest; | |
475 | } | |
476 | ||
477 | /* Return the left-most ASN in path */ | |
478 | as_t aspath_leftmost(struct aspath *aspath) | |
479 | { | |
480 | struct assegment *seg = aspath->segments; | |
481 | as_t leftmost = 0; | |
482 | ||
483 | if (seg && seg->length && seg->type == AS_SEQUENCE) | |
484 | leftmost = seg->as[0]; | |
485 | ||
486 | return leftmost; | |
487 | } | |
488 | ||
489 | /* Return 1 if there are any 4-byte ASes in the path */ | |
490 | bool aspath_has_as4(struct aspath *aspath) | |
491 | { | |
492 | struct assegment *seg = aspath->segments; | |
493 | unsigned int i; | |
494 | ||
495 | while (seg) { | |
496 | for (i = 0; i < seg->length; i++) | |
497 | if (seg->as[i] > BGP_AS_MAX) | |
498 | return true; | |
499 | seg = seg->next; | |
500 | } | |
501 | return false; | |
502 | } | |
503 | ||
504 | /* Convert aspath structure to string expression. */ | |
505 | static void aspath_make_str_count(struct aspath *as, bool make_json) | |
506 | { | |
507 | struct assegment *seg; | |
508 | int str_size; | |
509 | int len = 0; | |
510 | char *str_buf; | |
511 | json_object *jaspath_segments = NULL; | |
512 | json_object *jseg = NULL; | |
513 | json_object *jseg_list = NULL; | |
514 | ||
515 | if (make_json) { | |
516 | as->json = json_object_new_object(); | |
517 | jaspath_segments = json_object_new_array(); | |
518 | } | |
519 | ||
520 | /* Empty aspath. */ | |
521 | if (!as->segments) { | |
522 | if (make_json) { | |
523 | json_object_string_add(as->json, "string", "Local"); | |
524 | json_object_object_add(as->json, "segments", | |
525 | jaspath_segments); | |
526 | json_object_int_add(as->json, "length", 0); | |
527 | } | |
528 | as->str = XMALLOC(MTYPE_AS_STR, 1); | |
529 | as->str[0] = '\0'; | |
530 | as->str_len = 0; | |
531 | return; | |
532 | } | |
533 | ||
534 | seg = as->segments; | |
535 | ||
536 | /* ASN takes 5 to 10 chars plus separator, see below. | |
537 | * If there is one differing segment type, we need an additional | |
538 | * 2 chars for segment delimiters, and the final '\0'. | |
539 | * Hopefully this is large enough to avoid hitting the realloc | |
540 | * code below for most common sequences. | |
541 | * | |
542 | * This was changed to 10 after the well-known BGP assertion, which | |
543 | * had hit some parts of the Internet in May of 2009. | |
544 | * plain format : '4294967295 ' : 10 + 1 | |
545 | * astod format : '65535.65535 ': 11 + 1 | |
546 | */ | |
547 | #define ASN_STR_LEN (11 + 1) | |
548 | str_size = MAX(assegment_count_asns(seg, 0) * ASN_STR_LEN + 2 + 1, | |
549 | ASPATH_STR_DEFAULT_LEN); | |
550 | str_buf = XMALLOC(MTYPE_AS_STR, str_size); | |
551 | ||
552 | while (seg) { | |
553 | int i; | |
554 | char separator; | |
555 | ||
556 | /* Check AS type validity. Set separator for segment */ | |
557 | switch (seg->type) { | |
558 | case AS_SET: | |
559 | case AS_CONFED_SET: | |
560 | separator = ','; | |
561 | break; | |
562 | case AS_SEQUENCE: | |
563 | case AS_CONFED_SEQUENCE: | |
564 | separator = ' '; | |
565 | break; | |
566 | default: | |
567 | XFREE(MTYPE_AS_STR, str_buf); | |
568 | as->str = NULL; | |
569 | as->str_len = 0; | |
570 | json_object_free(as->json); | |
571 | as->json = NULL; | |
572 | ||
573 | return; | |
574 | } | |
575 | ||
576 | /* We might need to increase str_buf, particularly if path has | |
577 | * differing segments types, our initial guesstimate above will | |
578 | * have been wrong. Need 11 chars for ASN, a separator each and | |
579 | * potentially two segment delimiters, plus a space between each | |
580 | * segment and trailing zero. | |
581 | * | |
582 | * This definitely didn't work with the value of 5 bytes and | |
583 | * 32-bit ASNs. | |
584 | */ | |
585 | #define SEGMENT_STR_LEN(X) (((X)->length * ASN_STR_LEN) + 2 + 1 + 1) | |
586 | if ((len + SEGMENT_STR_LEN(seg)) > str_size) { | |
587 | str_size = len + SEGMENT_STR_LEN(seg); | |
588 | str_buf = XREALLOC(MTYPE_AS_STR, str_buf, str_size); | |
589 | } | |
590 | #undef ASN_STR_LEN | |
591 | #undef SEGMENT_STR_LEN | |
592 | ||
593 | if (seg->type != AS_SEQUENCE) | |
594 | len += snprintf( | |
595 | str_buf + len, str_size - len, "%c", | |
596 | aspath_delimiter_char(seg->type, AS_SEG_START)); | |
597 | ||
598 | if (make_json) | |
599 | jseg_list = json_object_new_array(); | |
600 | ||
601 | /* write out the ASNs, with their separators, bar the last one*/ | |
602 | for (i = 0; i < seg->length; i++) { | |
603 | if (make_json) | |
604 | asn_asn2json_array(jseg_list, seg->as[i], | |
605 | as->asnotation); | |
606 | len += snprintfrr(str_buf + len, str_size - len, | |
607 | ASN_FORMAT(as->asnotation), | |
608 | &seg->as[i]); | |
609 | ||
610 | if (i < (seg->length - 1)) | |
611 | len += snprintf(str_buf + len, str_size - len, | |
612 | "%c", separator); | |
613 | } | |
614 | ||
615 | if (make_json) { | |
616 | jseg = json_object_new_object(); | |
617 | json_object_string_add( | |
618 | jseg, "type", | |
619 | aspath_segment_type_str[seg->type]); | |
620 | json_object_object_add(jseg, "list", jseg_list); | |
621 | json_object_array_add(jaspath_segments, jseg); | |
622 | } | |
623 | ||
624 | if (seg->type != AS_SEQUENCE) | |
625 | len += snprintf( | |
626 | str_buf + len, str_size - len, "%c", | |
627 | aspath_delimiter_char(seg->type, AS_SEG_END)); | |
628 | if (seg->next) | |
629 | len += snprintf(str_buf + len, str_size - len, " "); | |
630 | ||
631 | seg = seg->next; | |
632 | } | |
633 | ||
634 | assert(len < str_size); | |
635 | ||
636 | str_buf[len] = '\0'; | |
637 | as->str = str_buf; | |
638 | as->str_len = len; | |
639 | ||
640 | if (make_json) { | |
641 | json_object_string_add(as->json, "string", str_buf); | |
642 | json_object_object_add(as->json, "segments", jaspath_segments); | |
643 | json_object_int_add(as->json, "length", aspath_count_hops(as)); | |
644 | } | |
645 | ||
646 | return; | |
647 | } | |
648 | ||
649 | void aspath_str_update(struct aspath *as, bool make_json) | |
650 | { | |
651 | XFREE(MTYPE_AS_STR, as->str); | |
652 | ||
653 | if (as->json) { | |
654 | json_object_free(as->json); | |
655 | as->json = NULL; | |
656 | } | |
657 | ||
658 | aspath_make_str_count(as, make_json); | |
659 | } | |
660 | ||
661 | /* Intern allocated AS path. */ | |
662 | struct aspath *aspath_intern(struct aspath *aspath) | |
663 | { | |
664 | struct aspath *find; | |
665 | ||
666 | /* Assert this AS path structure is not interned and has the string | |
667 | representation built. */ | |
668 | assert(aspath->refcnt == 0); | |
669 | assert(aspath->str); | |
670 | ||
671 | /* Check AS path hash. */ | |
672 | find = hash_get(ashash, aspath, hash_alloc_intern); | |
673 | if (find != aspath) | |
674 | aspath_free(aspath); | |
675 | ||
676 | find->refcnt++; | |
677 | ||
678 | return find; | |
679 | } | |
680 | ||
681 | /* Duplicate aspath structure. Created same aspath structure but | |
682 | reference count and AS path string is cleared. */ | |
683 | struct aspath *aspath_dup(struct aspath *aspath) | |
684 | { | |
685 | unsigned short buflen = aspath->str_len + 1; | |
686 | struct aspath *new; | |
687 | ||
688 | new = XCALLOC(MTYPE_AS_PATH, sizeof(struct aspath)); | |
689 | new->json = NULL; | |
690 | ||
691 | if (aspath->segments) | |
692 | new->segments = assegment_dup_all(aspath->segments); | |
693 | ||
694 | if (!aspath->str) | |
695 | return new; | |
696 | ||
697 | new->str = XMALLOC(MTYPE_AS_STR, buflen); | |
698 | new->str_len = aspath->str_len; | |
699 | new->asnotation = aspath->asnotation; | |
700 | ||
701 | /* copy the string data */ | |
702 | if (aspath->str_len > 0) | |
703 | memcpy(new->str, aspath->str, buflen); | |
704 | else | |
705 | new->str[0] = '\0'; | |
706 | ||
707 | return new; | |
708 | } | |
709 | ||
710 | static void *aspath_hash_alloc(void *arg) | |
711 | { | |
712 | const struct aspath *aspath = arg; | |
713 | struct aspath *new; | |
714 | ||
715 | /* Malformed AS path value. */ | |
716 | assert(aspath->str); | |
717 | ||
718 | /* New aspath structure is needed. */ | |
719 | new = XMALLOC(MTYPE_AS_PATH, sizeof(struct aspath)); | |
720 | ||
721 | /* Reuse segments and string representation */ | |
722 | new->refcnt = 0; | |
723 | new->segments = aspath->segments; | |
724 | new->str = aspath->str; | |
725 | new->str_len = aspath->str_len; | |
726 | new->json = aspath->json; | |
727 | new->asnotation = aspath->asnotation; | |
728 | ||
729 | return new; | |
730 | } | |
731 | ||
732 | /* parse as-segment byte stream in struct assegment */ | |
733 | static int assegments_parse(struct stream *s, size_t length, | |
734 | struct assegment **result, int use32bit) | |
735 | { | |
736 | struct assegment_header segh; | |
737 | struct assegment *seg, *prev = NULL, *head = NULL; | |
738 | size_t bytes = 0; | |
739 | ||
740 | /* empty aspath (ie iBGP or somesuch) */ | |
741 | if (length == 0) | |
742 | return 0; | |
743 | ||
744 | if (BGP_DEBUG(as4, AS4_SEGMENT)) | |
745 | zlog_debug( | |
746 | "[AS4SEG] Parse aspath segment: got total byte length %lu", | |
747 | (unsigned long)length); | |
748 | /* basic checks */ | |
749 | if ((STREAM_READABLE(s) < length) | |
750 | || (STREAM_READABLE(s) < AS_HEADER_SIZE) | |
751 | || (length % AS16_VALUE_SIZE)) | |
752 | return -1; | |
753 | ||
754 | while (bytes < length) { | |
755 | int i; | |
756 | size_t seg_size; | |
757 | ||
758 | if ((length - bytes) <= AS_HEADER_SIZE) { | |
759 | if (head) | |
760 | assegment_free_all(head); | |
761 | return -1; | |
762 | } | |
763 | ||
764 | /* softly softly, get the header first on its own */ | |
765 | segh.type = stream_getc(s); | |
766 | segh.length = stream_getc(s); | |
767 | ||
768 | seg_size = ASSEGMENT_SIZE(segh.length, use32bit); | |
769 | ||
770 | if (BGP_DEBUG(as4, AS4_SEGMENT)) | |
771 | zlog_debug( | |
772 | "[AS4SEG] Parse aspath segment: got type %d, length %d", | |
773 | segh.type, segh.length); | |
774 | ||
775 | /* check it.. */ | |
776 | if (((bytes + seg_size) > length) | |
777 | /* 1771bis 4.3b: seg length contains one or more */ | |
778 | || (segh.length == 0) | |
779 | /* Paranoia in case someone changes type of segment length. | |
780 | * Shift both values by 0x10 to make the comparison operate | |
781 | * on more, than 8 bits (otherwise it's a warning, bug | |
782 | * #564). | |
783 | */ | |
784 | || ((sizeof(segh.length) > 1) | |
785 | && (0x10 + segh.length > 0x10 + AS_SEGMENT_MAX))) { | |
786 | if (head) | |
787 | assegment_free_all(head); | |
788 | return -1; | |
789 | } | |
790 | ||
791 | switch (segh.type) { | |
792 | case AS_SEQUENCE: | |
793 | case AS_SET: | |
794 | case AS_CONFED_SEQUENCE: | |
795 | case AS_CONFED_SET: | |
796 | break; | |
797 | default: | |
798 | if (head) | |
799 | assegment_free_all(head); | |
800 | return -1; | |
801 | } | |
802 | ||
803 | /* now its safe to trust lengths */ | |
804 | seg = assegment_new(segh.type, segh.length); | |
805 | ||
806 | if (head) | |
807 | prev->next = seg; | |
808 | else /* it's the first segment */ | |
809 | head = seg; | |
810 | ||
811 | for (i = 0; i < segh.length; i++) | |
812 | seg->as[i] = | |
813 | (use32bit) ? stream_getl(s) : stream_getw(s); | |
814 | ||
815 | bytes += seg_size; | |
816 | ||
817 | if (BGP_DEBUG(as4, AS4_SEGMENT)) | |
818 | zlog_debug( | |
819 | "[AS4SEG] Parse aspath segment: Bytes now: %lu", | |
820 | (unsigned long)bytes); | |
821 | ||
822 | prev = seg; | |
823 | } | |
824 | ||
825 | *result = assegment_normalise(head); | |
826 | return 0; | |
827 | } | |
828 | ||
829 | /* AS path parse function. pnt is a pointer to byte stream and length | |
830 | is length of byte stream. If there is same AS path in the the AS | |
831 | path hash then return it else make new AS path structure. | |
832 | ||
833 | On error NULL is returned. | |
834 | */ | |
835 | struct aspath *aspath_parse(struct stream *s, size_t length, int use32bit, | |
836 | enum asnotation_mode asnotation) | |
837 | { | |
838 | struct aspath as; | |
839 | struct aspath *find; | |
840 | ||
841 | /* If length is odd it's malformed AS path. */ | |
842 | /* Nit-picking: if (use32bit == 0) it is malformed if odd, | |
843 | * otherwise its malformed when length is larger than 2 and (length-2) | |
844 | * is not dividable by 4. | |
845 | * But... this time we're lazy | |
846 | */ | |
847 | if (length % AS16_VALUE_SIZE) | |
848 | return NULL; | |
849 | ||
850 | memset(&as, 0, sizeof(as)); | |
851 | as.asnotation = asnotation; | |
852 | if (assegments_parse(s, length, &as.segments, use32bit) < 0) | |
853 | return NULL; | |
854 | ||
855 | /* If already same aspath exist then return it. */ | |
856 | find = hash_get(ashash, &as, aspath_hash_alloc); | |
857 | ||
858 | /* if the aspath was already hashed free temporary memory. */ | |
859 | if (find->refcnt) { | |
860 | assegment_free_all(as.segments); | |
861 | /* aspath_key_make() always updates the string */ | |
862 | XFREE(MTYPE_AS_STR, as.str); | |
863 | if (as.json) { | |
864 | json_object_free(as.json); | |
865 | as.json = NULL; | |
866 | } | |
867 | } | |
868 | ||
869 | find->refcnt++; | |
870 | ||
871 | return find; | |
872 | } | |
873 | ||
874 | static void assegment_data_put(struct stream *s, as_t *as, int num, | |
875 | int use32bit) | |
876 | { | |
877 | int i; | |
878 | assert(num <= AS_SEGMENT_MAX); | |
879 | ||
880 | for (i = 0; i < num; i++) | |
881 | if (use32bit) | |
882 | stream_putl(s, as[i]); | |
883 | else { | |
884 | if (as[i] <= BGP_AS_MAX) | |
885 | stream_putw(s, as[i]); | |
886 | else | |
887 | stream_putw(s, BGP_AS_TRANS); | |
888 | } | |
889 | } | |
890 | ||
891 | static size_t assegment_header_put(struct stream *s, uint8_t type, int length) | |
892 | { | |
893 | size_t lenp; | |
894 | assert(length <= AS_SEGMENT_MAX); | |
895 | stream_putc(s, type); | |
896 | lenp = stream_get_endp(s); | |
897 | stream_putc(s, length); | |
898 | return lenp; | |
899 | } | |
900 | ||
901 | /* write aspath data to stream */ | |
902 | size_t aspath_put(struct stream *s, struct aspath *as, int use32bit) | |
903 | { | |
904 | struct assegment *seg = as->segments; | |
905 | size_t bytes = 0; | |
906 | ||
907 | if (!seg || seg->length == 0) | |
908 | return 0; | |
909 | ||
910 | /* | |
911 | * Hey, what do we do when we have > STREAM_WRITABLE(s) here? | |
912 | * At the moment, we would write out a partial aspath, and our | |
913 | * peer | |
914 | * will complain and drop the session :-/ | |
915 | * | |
916 | * The general assumption here is that many things tested will | |
917 | * never happen. And, in real live, up to now, they have not. | |
918 | */ | |
919 | while (seg && (ASSEGMENT_LEN(seg, use32bit) <= STREAM_WRITEABLE(s))) { | |
920 | struct assegment *next = seg->next; | |
921 | int written = 0; | |
922 | int asns_packed = 0; | |
923 | size_t lenp; | |
924 | ||
925 | /* Overlength segments have to be split up */ | |
926 | while ((seg->length - written) > AS_SEGMENT_MAX) { | |
927 | assegment_header_put(s, seg->type, AS_SEGMENT_MAX); | |
928 | assegment_data_put(s, (seg->as + written), | |
929 | AS_SEGMENT_MAX, use32bit); | |
930 | written += AS_SEGMENT_MAX; | |
931 | bytes += ASSEGMENT_SIZE(AS_SEGMENT_MAX, use32bit); | |
932 | } | |
933 | ||
934 | /* write the final segment, probably is also the first | |
935 | */ | |
936 | lenp = assegment_header_put(s, seg->type, | |
937 | seg->length - written); | |
938 | assegment_data_put(s, (seg->as + written), | |
939 | seg->length - written, use32bit); | |
940 | ||
941 | /* Sequence-type segments can be 'packed' together | |
942 | * Case of a segment which was overlength and split up | |
943 | * will be missed here, but that doesn't matter. | |
944 | */ | |
945 | while (next && ASSEGMENTS_PACKABLE(seg, next)) { | |
946 | /* NB: We should never normally get here given | |
947 | * we | |
948 | * normalise aspath data when parse them. | |
949 | * However, better | |
950 | * safe than sorry. We potentially could call | |
951 | * assegment_normalise here instead, but it's | |
952 | * cheaper and | |
953 | * easier to do it on the fly here rather than | |
954 | * go through | |
955 | * the segment list twice every time we write | |
956 | * out | |
957 | * aspath's. | |
958 | */ | |
959 | ||
960 | /* Next segment's data can fit in this one */ | |
961 | assegment_data_put(s, next->as, next->length, use32bit); | |
962 | ||
963 | /* update the length of the segment header */ | |
964 | stream_putc_at(s, lenp, | |
965 | seg->length - written + next->length); | |
966 | asns_packed += next->length; | |
967 | ||
968 | next = next->next; | |
969 | } | |
970 | ||
971 | bytes += ASSEGMENT_SIZE(seg->length - written + asns_packed, | |
972 | use32bit); | |
973 | seg = next; | |
974 | } | |
975 | return bytes; | |
976 | } | |
977 | ||
978 | /* This is for SNMP BGP4PATHATTRASPATHSEGMENT | |
979 | * We have no way to manage the storage, so we use a static stream | |
980 | * wrapper around aspath_put. | |
981 | */ | |
982 | uint8_t *aspath_snmp_pathseg(struct aspath *as, size_t *varlen) | |
983 | { | |
984 | #define SNMP_PATHSEG_MAX 1024 | |
985 | ||
986 | if (!snmp_stream) | |
987 | snmp_stream = stream_new(SNMP_PATHSEG_MAX); | |
988 | else | |
989 | stream_reset(snmp_stream); | |
990 | ||
991 | if (!as) { | |
992 | *varlen = 0; | |
993 | return NULL; | |
994 | } | |
995 | aspath_put(snmp_stream, as, 0); /* use 16 bit for now here */ | |
996 | ||
997 | *varlen = stream_get_endp(snmp_stream); | |
998 | return stream_pnt(snmp_stream); | |
999 | } | |
1000 | ||
1001 | static struct assegment *aspath_aggregate_as_set_add(struct aspath *aspath, | |
1002 | struct assegment *asset, | |
1003 | as_t as) | |
1004 | { | |
1005 | int i; | |
1006 | ||
1007 | /* If this is first AS set member, create new as-set segment. */ | |
1008 | if (asset == NULL) { | |
1009 | asset = assegment_new(AS_SET, 1); | |
1010 | if (!aspath->segments) | |
1011 | aspath->segments = asset; | |
1012 | else { | |
1013 | struct assegment *seg = aspath->segments; | |
1014 | while (seg->next) | |
1015 | seg = seg->next; | |
1016 | seg->next = asset; | |
1017 | } | |
1018 | asset->type = AS_SET; | |
1019 | asset->length = 1; | |
1020 | asset->as[0] = as; | |
1021 | } else { | |
1022 | /* Check this AS value already exists or not. */ | |
1023 | for (i = 0; i < asset->length; i++) | |
1024 | if (asset->as[i] == as) | |
1025 | return asset; | |
1026 | ||
1027 | asset->length++; | |
1028 | asset->as = XREALLOC(MTYPE_AS_SEG_DATA, asset->as, | |
1029 | asset->length * AS_VALUE_SIZE); | |
1030 | asset->as[asset->length - 1] = as; | |
1031 | } | |
1032 | ||
1033 | ||
1034 | return asset; | |
1035 | } | |
1036 | ||
1037 | /* Modify as1 using as2 for aggregation. */ | |
1038 | struct aspath *aspath_aggregate(struct aspath *as1, struct aspath *as2) | |
1039 | { | |
1040 | int i; | |
1041 | int minlen = 0; | |
1042 | int match = 0; | |
1043 | int from; | |
1044 | struct assegment *seg1 = as1->segments; | |
1045 | struct assegment *seg2 = as2->segments; | |
1046 | struct aspath *aspath = NULL; | |
1047 | struct assegment *asset = NULL; | |
1048 | struct assegment *prevseg = NULL; | |
1049 | ||
1050 | /* First of all check common leading sequence. */ | |
1051 | while (seg1 && seg2) { | |
1052 | /* Check segment type. */ | |
1053 | if (seg1->type != seg2->type) | |
1054 | break; | |
1055 | ||
1056 | /* Minimum segment length. */ | |
1057 | minlen = MIN(seg1->length, seg2->length); | |
1058 | ||
1059 | for (match = 0; match < minlen; match++) | |
1060 | if (seg1->as[match] != seg2->as[match]) | |
1061 | break; | |
1062 | ||
1063 | if (match) { | |
1064 | struct assegment *seg = assegment_new(seg1->type, 0); | |
1065 | ||
1066 | seg = assegment_append_asns(seg, seg1->as, match); | |
1067 | ||
1068 | if (!aspath) { | |
1069 | aspath = aspath_new(as1->asnotation); | |
1070 | aspath->segments = seg; | |
1071 | } else | |
1072 | prevseg->next = seg; | |
1073 | ||
1074 | prevseg = seg; | |
1075 | } | |
1076 | ||
1077 | if (match != minlen || match != seg1->length | |
1078 | || seg1->length != seg2->length) | |
1079 | break; | |
1080 | /* We are moving on to the next segment to reset match */ | |
1081 | else | |
1082 | match = 0; | |
1083 | ||
1084 | seg1 = seg1->next; | |
1085 | seg2 = seg2->next; | |
1086 | } | |
1087 | ||
1088 | if (!aspath) | |
1089 | aspath = aspath_new(as1->asnotation); | |
1090 | ||
1091 | /* Make as-set using rest of all information. */ | |
1092 | from = match; | |
1093 | while (seg1) { | |
1094 | for (i = from; i < seg1->length; i++) | |
1095 | asset = aspath_aggregate_as_set_add(aspath, asset, | |
1096 | seg1->as[i]); | |
1097 | ||
1098 | from = 0; | |
1099 | seg1 = seg1->next; | |
1100 | } | |
1101 | ||
1102 | from = match; | |
1103 | while (seg2) { | |
1104 | for (i = from; i < seg2->length; i++) | |
1105 | asset = aspath_aggregate_as_set_add(aspath, asset, | |
1106 | seg2->as[i]); | |
1107 | ||
1108 | from = 0; | |
1109 | seg2 = seg2->next; | |
1110 | } | |
1111 | ||
1112 | assegment_normalise(aspath->segments); | |
1113 | aspath_str_update(aspath, false); | |
1114 | return aspath; | |
1115 | } | |
1116 | ||
1117 | /* When a BGP router receives an UPDATE with an MP_REACH_NLRI | |
1118 | attribute, check the leftmost AS number in the AS_PATH attribute is | |
1119 | or not the peer's AS number. */ | |
1120 | bool aspath_firstas_check(struct aspath *aspath, as_t asno) | |
1121 | { | |
1122 | if ((aspath == NULL) || (aspath->segments == NULL)) | |
1123 | return false; | |
1124 | ||
1125 | if (aspath->segments && (aspath->segments->type == AS_SEQUENCE) | |
1126 | && (aspath->segments->as[0] == asno)) | |
1127 | return true; | |
1128 | ||
1129 | return false; | |
1130 | } | |
1131 | ||
1132 | unsigned int aspath_get_first_as(struct aspath *aspath) | |
1133 | { | |
1134 | if (aspath == NULL || aspath->segments == NULL) | |
1135 | return 0; | |
1136 | ||
1137 | return aspath->segments->as[0]; | |
1138 | } | |
1139 | ||
1140 | unsigned int aspath_get_last_as(struct aspath *aspath) | |
1141 | { | |
1142 | int i; | |
1143 | unsigned int last_as = 0; | |
1144 | const struct assegment *seg; | |
1145 | ||
1146 | if (aspath == NULL || aspath->segments == NULL) | |
1147 | return last_as; | |
1148 | ||
1149 | seg = aspath->segments; | |
1150 | ||
1151 | while (seg) { | |
1152 | if (seg->type == AS_SEQUENCE || seg->type == AS_CONFED_SEQUENCE) | |
1153 | for (i = 0; i < seg->length; i++) | |
1154 | last_as = seg->as[i]; | |
1155 | seg = seg->next; | |
1156 | } | |
1157 | ||
1158 | return last_as; | |
1159 | } | |
1160 | ||
1161 | /* AS path loop check. If aspath contains asno then return >= 1. */ | |
1162 | int aspath_loop_check(struct aspath *aspath, as_t asno) | |
1163 | { | |
1164 | struct assegment *seg; | |
1165 | int count = 0; | |
1166 | ||
1167 | if ((aspath == NULL) || (aspath->segments == NULL)) | |
1168 | return 0; | |
1169 | ||
1170 | seg = aspath->segments; | |
1171 | ||
1172 | while (seg) { | |
1173 | int i; | |
1174 | ||
1175 | for (i = 0; i < seg->length; i++) | |
1176 | if (seg->as[i] == asno) | |
1177 | count++; | |
1178 | ||
1179 | seg = seg->next; | |
1180 | } | |
1181 | return count; | |
1182 | } | |
1183 | ||
1184 | /* AS path loop check. If aspath contains asno | |
1185 | * that is a confed id then return >= 1. | |
1186 | */ | |
1187 | int aspath_loop_check_confed(struct aspath *aspath, as_t asno) | |
1188 | { | |
1189 | struct assegment *seg; | |
1190 | int count = 0; | |
1191 | ||
1192 | if (aspath == NULL || aspath->segments == NULL) | |
1193 | return 0; | |
1194 | ||
1195 | seg = aspath->segments; | |
1196 | ||
1197 | while (seg) { | |
1198 | unsigned int i; | |
1199 | ||
1200 | for (i = 0; i < seg->length; i++) | |
1201 | if (seg->type != AS_CONFED_SEQUENCE && | |
1202 | seg->type != AS_CONFED_SET && seg->as[i] == asno) | |
1203 | count++; | |
1204 | ||
1205 | seg = seg->next; | |
1206 | } | |
1207 | return count; | |
1208 | } | |
1209 | ||
1210 | ||
1211 | /* When all of AS path is private AS return 1. */ | |
1212 | bool aspath_private_as_check(struct aspath *aspath) | |
1213 | { | |
1214 | struct assegment *seg; | |
1215 | ||
1216 | if (!(aspath && aspath->segments)) | |
1217 | return false; | |
1218 | ||
1219 | seg = aspath->segments; | |
1220 | ||
1221 | while (seg) { | |
1222 | int i; | |
1223 | ||
1224 | for (i = 0; i < seg->length; i++) { | |
1225 | if (!BGP_AS_IS_PRIVATE(seg->as[i])) | |
1226 | return false; | |
1227 | } | |
1228 | seg = seg->next; | |
1229 | } | |
1230 | return true; | |
1231 | } | |
1232 | ||
1233 | /* Replace all instances of the target ASN with our own ASN */ | |
1234 | struct aspath *aspath_replace_specific_asn(struct aspath *aspath, | |
1235 | as_t target_asn, as_t our_asn) | |
1236 | { | |
1237 | struct aspath *new; | |
1238 | struct assegment *seg; | |
1239 | ||
1240 | new = aspath_dup(aspath); | |
1241 | seg = new->segments; | |
1242 | ||
1243 | while (seg) { | |
1244 | int i; | |
1245 | ||
1246 | for (i = 0; i < seg->length; i++) { | |
1247 | if (seg->as[i] == target_asn) | |
1248 | seg->as[i] = our_asn; | |
1249 | } | |
1250 | seg = seg->next; | |
1251 | } | |
1252 | ||
1253 | aspath_str_update(new, false); | |
1254 | return new; | |
1255 | } | |
1256 | ||
1257 | /* Replace all ASNs with our own ASN */ | |
1258 | struct aspath *aspath_replace_all_asn(struct aspath *aspath, as_t our_asn) | |
1259 | { | |
1260 | struct aspath *new; | |
1261 | struct assegment *seg; | |
1262 | ||
1263 | new = aspath_dup(aspath); | |
1264 | seg = new->segments; | |
1265 | ||
1266 | while (seg) { | |
1267 | int i; | |
1268 | ||
1269 | for (i = 0; i < seg->length; i++) | |
1270 | seg->as[i] = our_asn; | |
1271 | ||
1272 | seg = seg->next; | |
1273 | } | |
1274 | ||
1275 | aspath_str_update(new, false); | |
1276 | return new; | |
1277 | } | |
1278 | ||
1279 | /* Replace all private ASNs with our own ASN */ | |
1280 | struct aspath *aspath_replace_private_asns(struct aspath *aspath, as_t asn, | |
1281 | as_t peer_asn) | |
1282 | { | |
1283 | struct aspath *new; | |
1284 | struct assegment *seg; | |
1285 | ||
1286 | new = aspath_dup(aspath); | |
1287 | seg = new->segments; | |
1288 | ||
1289 | while (seg) { | |
1290 | int i; | |
1291 | ||
1292 | for (i = 0; i < seg->length; i++) { | |
1293 | /* Don't replace if public ASN or peer's ASN */ | |
1294 | if (BGP_AS_IS_PRIVATE(seg->as[i]) | |
1295 | && (seg->as[i] != peer_asn)) | |
1296 | seg->as[i] = asn; | |
1297 | } | |
1298 | seg = seg->next; | |
1299 | } | |
1300 | ||
1301 | aspath_str_update(new, false); | |
1302 | return new; | |
1303 | } | |
1304 | ||
1305 | /* Remove all private ASNs */ | |
1306 | struct aspath *aspath_remove_private_asns(struct aspath *aspath, as_t peer_asn) | |
1307 | { | |
1308 | struct aspath *new; | |
1309 | struct assegment *seg; | |
1310 | struct assegment *new_seg; | |
1311 | struct assegment *last_new_seg; | |
1312 | int i; | |
1313 | int j; | |
1314 | int public = 0; | |
1315 | int peer = 0; | |
1316 | ||
1317 | new = XCALLOC(MTYPE_AS_PATH, sizeof(struct aspath)); | |
1318 | ||
1319 | new->json = NULL; | |
1320 | new_seg = NULL; | |
1321 | last_new_seg = NULL; | |
1322 | seg = aspath->segments; | |
1323 | while (seg) { | |
1324 | public = 0; | |
1325 | peer = 0; | |
1326 | for (i = 0; i < seg->length; i++) { | |
1327 | // ASN is public | |
1328 | if (!BGP_AS_IS_PRIVATE(seg->as[i])) | |
1329 | public++; | |
1330 | /* ASN matches peer's. | |
1331 | * Don't double-count if peer_asn is public. | |
1332 | */ | |
1333 | else if (seg->as[i] == peer_asn) | |
1334 | peer++; | |
1335 | } | |
1336 | ||
1337 | // The entire segment is public so copy it | |
1338 | if (public == seg->length) | |
1339 | new_seg = assegment_dup(seg); | |
1340 | ||
1341 | // The segment is a mix of public and private ASNs. Copy as many | |
1342 | // spots as | |
1343 | // there are public ASNs then come back and fill in only the | |
1344 | // public ASNs. | |
1345 | else { | |
1346 | /* length needs to account for all retained ASNs | |
1347 | * (public or peer_asn), not just public | |
1348 | */ | |
1349 | new_seg = assegment_new(seg->type, (public + peer)); | |
1350 | j = 0; | |
1351 | for (i = 0; i < seg->length; i++) { | |
1352 | // keep ASN if public or matches peer's ASN | |
1353 | if (!BGP_AS_IS_PRIVATE(seg->as[i]) | |
1354 | || (seg->as[i] == peer_asn)) { | |
1355 | new_seg->as[j] = seg->as[i]; | |
1356 | j++; | |
1357 | } | |
1358 | } | |
1359 | } | |
1360 | ||
1361 | // This is the first segment so set the aspath segments pointer | |
1362 | // to this one | |
1363 | if (!last_new_seg) | |
1364 | new->segments = new_seg; | |
1365 | else | |
1366 | last_new_seg->next = new_seg; | |
1367 | ||
1368 | last_new_seg = new_seg; | |
1369 | seg = seg->next; | |
1370 | } | |
1371 | ||
1372 | aspath_str_update(new, false); | |
1373 | return new; | |
1374 | } | |
1375 | ||
1376 | /* AS path confed check. If aspath contains confed set or sequence then return | |
1377 | * 1. */ | |
1378 | bool aspath_confed_check(struct aspath *aspath) | |
1379 | { | |
1380 | struct assegment *seg; | |
1381 | ||
1382 | if (!(aspath && aspath->segments)) | |
1383 | return false; | |
1384 | ||
1385 | seg = aspath->segments; | |
1386 | ||
1387 | while (seg) { | |
1388 | if (seg->type == AS_CONFED_SET | |
1389 | || seg->type == AS_CONFED_SEQUENCE) | |
1390 | return true; | |
1391 | seg = seg->next; | |
1392 | } | |
1393 | return false; | |
1394 | } | |
1395 | ||
1396 | /* Leftmost AS path segment confed check. If leftmost AS segment is of type | |
1397 | AS_CONFED_SEQUENCE or AS_CONFED_SET then return 1. */ | |
1398 | bool aspath_left_confed_check(struct aspath *aspath) | |
1399 | { | |
1400 | ||
1401 | if (!(aspath && aspath->segments)) | |
1402 | return false; | |
1403 | ||
1404 | if ((aspath->segments->type == AS_CONFED_SEQUENCE) | |
1405 | || (aspath->segments->type == AS_CONFED_SET)) | |
1406 | return true; | |
1407 | ||
1408 | return false; | |
1409 | } | |
1410 | ||
1411 | /* Merge as1 to as2. as2 should be uninterned aspath. */ | |
1412 | static struct aspath *aspath_merge(struct aspath *as1, struct aspath *as2) | |
1413 | { | |
1414 | struct assegment *last, *new; | |
1415 | ||
1416 | if (!as1 || !as2) | |
1417 | return NULL; | |
1418 | ||
1419 | last = new = assegment_dup_all(as1->segments); | |
1420 | ||
1421 | /* find the last valid segment */ | |
1422 | while (last && last->next) | |
1423 | last = last->next; | |
1424 | ||
1425 | if (last) | |
1426 | last->next = as2->segments; | |
1427 | as2->segments = new; | |
1428 | aspath_str_update(as2, false); | |
1429 | return as2; | |
1430 | } | |
1431 | ||
1432 | /* Prepend as1 to as2. as2 should be uninterned aspath. */ | |
1433 | struct aspath *aspath_prepend(struct aspath *as1, struct aspath *as2) | |
1434 | { | |
1435 | struct assegment *as1segtail; | |
1436 | struct assegment *as2segtail; | |
1437 | struct assegment *as2seghead; | |
1438 | ||
1439 | if (!as1 || !as2) | |
1440 | return NULL; | |
1441 | ||
1442 | /* If as2 is empty, only need to dupe as1's chain onto as2 */ | |
1443 | if (as2->segments == NULL) { | |
1444 | as2->segments = assegment_dup_all(as1->segments); | |
1445 | aspath_str_update(as2, false); | |
1446 | return as2; | |
1447 | } | |
1448 | ||
1449 | /* If as1 is empty AS, no prepending to do. */ | |
1450 | if (as1->segments == NULL) | |
1451 | return as2; | |
1452 | ||
1453 | /* find the tail as1's segment chain. */ | |
1454 | as1segtail = as1->segments; | |
1455 | while (as1segtail && as1segtail->next) | |
1456 | as1segtail = as1segtail->next; | |
1457 | ||
1458 | /* Delete any AS_CONFED_SEQUENCE segment from as2. */ | |
1459 | if (as1segtail->type == AS_SEQUENCE | |
1460 | && as2->segments->type == AS_CONFED_SEQUENCE) | |
1461 | as2 = aspath_delete_confed_seq(as2); | |
1462 | ||
1463 | if (!as2->segments) { | |
1464 | as2->segments = assegment_dup_all(as1->segments); | |
1465 | aspath_str_update(as2, false); | |
1466 | return as2; | |
1467 | } | |
1468 | ||
1469 | /* Compare last segment type of as1 and first segment type of as2. */ | |
1470 | if (as1segtail->type != as2->segments->type) | |
1471 | return aspath_merge(as1, as2); | |
1472 | ||
1473 | if (as1segtail->type == AS_SEQUENCE) { | |
1474 | /* We have two chains of segments, as1->segments and seg2, | |
1475 | * and we have to attach them together, merging the attaching | |
1476 | * segments together into one. | |
1477 | * | |
1478 | * 1. dupe as1->segments onto head of as2 | |
1479 | * 2. merge seg2's asns onto last segment of this new chain | |
1480 | * 3. attach chain after seg2 | |
1481 | */ | |
1482 | ||
1483 | /* save as2 head */ | |
1484 | as2seghead = as2->segments; | |
1485 | ||
1486 | /* dupe as1 onto as2's head */ | |
1487 | as2segtail = as2->segments = assegment_dup_all(as1->segments); | |
1488 | ||
1489 | /* refind the tail of as2 */ | |
1490 | while (as2segtail && as2segtail->next) | |
1491 | as2segtail = as2segtail->next; | |
1492 | ||
1493 | /* merge the old head, seg2, into tail, seg1 */ | |
1494 | assegment_append_asns(as2segtail, as2seghead->as, | |
1495 | as2seghead->length); | |
1496 | ||
1497 | /* | |
1498 | * bypass the merged seg2, and attach any chain after it | |
1499 | * to chain descending from as2's head | |
1500 | */ | |
1501 | if (as2segtail) | |
1502 | as2segtail->next = as2seghead->next; | |
1503 | ||
1504 | /* as2->segments is now referenceless and useless */ | |
1505 | assegment_free(as2seghead); | |
1506 | ||
1507 | /* we've now prepended as1's segment chain to as2, merging | |
1508 | * the inbetween AS_SEQUENCE of seg2 in the process | |
1509 | */ | |
1510 | aspath_str_update(as2, false); | |
1511 | return as2; | |
1512 | } else { | |
1513 | /* AS_SET merge code is needed at here. */ | |
1514 | return aspath_merge(as1, as2); | |
1515 | } | |
1516 | /* XXX: Ermmm, what if as1 has multiple segments?? */ | |
1517 | ||
1518 | /* Not reached */ | |
1519 | } | |
1520 | ||
1521 | /* Iterate over AS_PATH segments and wipe all occurrences of the | |
1522 | * listed AS numbers. Hence some segments may lose some or even | |
1523 | * all data on the way, the operation is implemented as a smarter | |
1524 | * version of aspath_dup(), which allocates memory to hold the new | |
1525 | * data, not the original. The new AS path is returned. | |
1526 | */ | |
1527 | struct aspath *aspath_filter_exclude(struct aspath *source, | |
1528 | struct aspath *exclude_list) | |
1529 | { | |
1530 | struct assegment *srcseg, *exclseg, *lastseg; | |
1531 | struct aspath *newpath; | |
1532 | ||
1533 | newpath = aspath_new(source->asnotation); | |
1534 | lastseg = NULL; | |
1535 | ||
1536 | for (srcseg = source->segments; srcseg; srcseg = srcseg->next) { | |
1537 | unsigned i, y, newlen = 0, done = 0, skip_as; | |
1538 | struct assegment *newseg; | |
1539 | ||
1540 | /* Find out, how much ASns are we going to pick from this | |
1541 | * segment. | |
1542 | * We can't perform filtering right inline, because the size of | |
1543 | * the new segment isn't known at the moment yet. | |
1544 | */ | |
1545 | for (i = 0; i < srcseg->length; i++) { | |
1546 | skip_as = 0; | |
1547 | for (exclseg = exclude_list->segments; | |
1548 | exclseg && !skip_as; exclseg = exclseg->next) | |
1549 | for (y = 0; y < exclseg->length; y++) | |
1550 | if (srcseg->as[i] == exclseg->as[y]) { | |
1551 | skip_as = 1; | |
1552 | // There's no sense in testing | |
1553 | // the rest of exclusion list, | |
1554 | // bail out. | |
1555 | break; | |
1556 | } | |
1557 | if (!skip_as) | |
1558 | newlen++; | |
1559 | } | |
1560 | /* newlen is now the number of ASns to copy */ | |
1561 | if (!newlen) | |
1562 | continue; | |
1563 | ||
1564 | /* Actual copying. Allocate memory and iterate once more, | |
1565 | * performing filtering. */ | |
1566 | newseg = assegment_new(srcseg->type, newlen); | |
1567 | for (i = 0; i < srcseg->length; i++) { | |
1568 | skip_as = 0; | |
1569 | for (exclseg = exclude_list->segments; | |
1570 | exclseg && !skip_as; exclseg = exclseg->next) | |
1571 | for (y = 0; y < exclseg->length; y++) | |
1572 | if (srcseg->as[i] == exclseg->as[y]) { | |
1573 | skip_as = 1; | |
1574 | break; | |
1575 | } | |
1576 | if (skip_as) | |
1577 | continue; | |
1578 | newseg->as[done++] = srcseg->as[i]; | |
1579 | } | |
1580 | /* At his point newlen must be equal to done, and both must be | |
1581 | * positive. Append | |
1582 | * the filtered segment to the gross result. */ | |
1583 | if (!lastseg) | |
1584 | newpath->segments = newseg; | |
1585 | else | |
1586 | lastseg->next = newseg; | |
1587 | lastseg = newseg; | |
1588 | } | |
1589 | aspath_str_update(newpath, false); | |
1590 | /* We are happy returning even an empty AS_PATH, because the | |
1591 | * administrator | |
1592 | * might expect this very behaviour. There's a mean to avoid this, if | |
1593 | * necessary, | |
1594 | * by having a match rule against certain AS_PATH regexps in the | |
1595 | * route-map index. | |
1596 | */ | |
1597 | aspath_free(source); | |
1598 | return newpath; | |
1599 | } | |
1600 | ||
1601 | /* Add specified AS to the leftmost of aspath. */ | |
1602 | static struct aspath *aspath_add_asns(struct aspath *aspath, as_t asno, | |
1603 | uint8_t type, unsigned num) | |
1604 | { | |
1605 | struct assegment *assegment = aspath->segments; | |
1606 | unsigned i; | |
1607 | ||
1608 | if (assegment && assegment->type == type) { | |
1609 | /* extend existing segment */ | |
1610 | aspath->segments = | |
1611 | assegment_prepend_asns(aspath->segments, asno, num); | |
1612 | } else { | |
1613 | /* prepend with new segment */ | |
1614 | struct assegment *newsegment = assegment_new(type, num); | |
1615 | for (i = 0; i < num; i++) | |
1616 | newsegment->as[i] = asno; | |
1617 | ||
1618 | /* insert potentially replacing empty segment */ | |
1619 | if (assegment && assegment->length == 0) { | |
1620 | newsegment->next = assegment->next; | |
1621 | assegment_free(assegment); | |
1622 | } else | |
1623 | newsegment->next = assegment; | |
1624 | aspath->segments = newsegment; | |
1625 | } | |
1626 | ||
1627 | aspath_str_update(aspath, false); | |
1628 | return aspath; | |
1629 | } | |
1630 | ||
1631 | /* Add specified AS to the leftmost of aspath num times. */ | |
1632 | struct aspath *aspath_add_seq_n(struct aspath *aspath, as_t asno, unsigned num) | |
1633 | { | |
1634 | return aspath_add_asns(aspath, asno, AS_SEQUENCE, num); | |
1635 | } | |
1636 | ||
1637 | /* Add specified AS to the leftmost of aspath. */ | |
1638 | struct aspath *aspath_add_seq(struct aspath *aspath, as_t asno) | |
1639 | { | |
1640 | return aspath_add_asns(aspath, asno, AS_SEQUENCE, 1); | |
1641 | } | |
1642 | ||
1643 | /* Compare leftmost AS value for MED check. If as1's leftmost AS and | |
1644 | as2's leftmost AS is same return 1. */ | |
1645 | bool aspath_cmp_left(const struct aspath *aspath1, const struct aspath *aspath2) | |
1646 | { | |
1647 | const struct assegment *seg1; | |
1648 | const struct assegment *seg2; | |
1649 | ||
1650 | if (!(aspath1 && aspath2)) | |
1651 | return false; | |
1652 | ||
1653 | seg1 = aspath1->segments; | |
1654 | seg2 = aspath2->segments; | |
1655 | ||
1656 | /* If both paths are originated in this AS then we do want to compare | |
1657 | * MED */ | |
1658 | if (!seg1 && !seg2) | |
1659 | return true; | |
1660 | ||
1661 | /* find first non-confed segments for each */ | |
1662 | while (seg1 && ((seg1->type == AS_CONFED_SEQUENCE) | |
1663 | || (seg1->type == AS_CONFED_SET))) | |
1664 | seg1 = seg1->next; | |
1665 | ||
1666 | while (seg2 && ((seg2->type == AS_CONFED_SEQUENCE) | |
1667 | || (seg2->type == AS_CONFED_SET))) | |
1668 | seg2 = seg2->next; | |
1669 | ||
1670 | /* Check as1's */ | |
1671 | if (!(seg1 && seg2 && (seg1->type == AS_SEQUENCE) | |
1672 | && (seg2->type == AS_SEQUENCE))) | |
1673 | return false; | |
1674 | ||
1675 | if (seg1->as[0] == seg2->as[0]) | |
1676 | return true; | |
1677 | ||
1678 | return false; | |
1679 | } | |
1680 | ||
1681 | /* Truncate an aspath after a number of hops, and put the hops remaining | |
1682 | * at the front of another aspath. Needed for AS4 compat. | |
1683 | * | |
1684 | * Returned aspath is a /new/ aspath, which should either by free'd or | |
1685 | * interned by the caller, as desired. | |
1686 | */ | |
1687 | struct aspath *aspath_reconcile_as4(struct aspath *aspath, | |
1688 | struct aspath *as4path) | |
1689 | { | |
1690 | struct assegment *seg, *newseg, *prevseg = NULL; | |
1691 | struct aspath *newpath = NULL, *mergedpath; | |
1692 | int hops, cpasns = 0; | |
1693 | ||
1694 | if (!aspath || !as4path) | |
1695 | return NULL; | |
1696 | ||
1697 | seg = aspath->segments; | |
1698 | ||
1699 | /* CONFEDs should get reconciled too.. */ | |
1700 | hops = (aspath_count_hops(aspath) + aspath_count_confeds(aspath)) | |
1701 | - aspath_count_hops(as4path); | |
1702 | ||
1703 | if (hops < 0) { | |
1704 | if (BGP_DEBUG(as4, AS4)) | |
1705 | flog_warn( | |
1706 | EC_BGP_ASPATH_FEWER_HOPS, | |
1707 | "[AS4] Fewer hops in AS_PATH than NEW_AS_PATH"); | |
1708 | /* Something's gone wrong. The RFC says we should now ignore | |
1709 | * AS4_PATH, | |
1710 | * which is daft behaviour - it contains vital loop-detection | |
1711 | * information which must have been removed from AS_PATH. | |
1712 | */ | |
1713 | hops = aspath_count_hops(aspath); | |
1714 | } | |
1715 | ||
1716 | if (!hops) { | |
1717 | newpath = aspath_dup(as4path); | |
1718 | aspath_str_update(newpath, false); | |
1719 | return newpath; | |
1720 | } | |
1721 | ||
1722 | if (BGP_DEBUG(as4, AS4)) | |
1723 | zlog_debug( | |
1724 | "[AS4] got AS_PATH %s and AS4_PATH %s synthesizing now", | |
1725 | aspath->str, as4path->str); | |
1726 | ||
1727 | while (seg && hops > 0) { | |
1728 | switch (seg->type) { | |
1729 | case AS_SET: | |
1730 | case AS_CONFED_SET: | |
1731 | hops--; | |
1732 | cpasns = seg->length; | |
1733 | break; | |
1734 | case AS_CONFED_SEQUENCE: | |
1735 | /* Should never split a confed-sequence, if hop-count | |
1736 | * suggests we must then something's gone wrong | |
1737 | * somewhere. | |
1738 | * | |
1739 | * Most important goal is to preserve AS_PATHs prime | |
1740 | * function | |
1741 | * as loop-detector, so we fudge the numbers so that the | |
1742 | * entire | |
1743 | * confed-sequence is merged in. | |
1744 | */ | |
1745 | if (hops < seg->length) { | |
1746 | if (BGP_DEBUG(as4, AS4)) | |
1747 | zlog_debug( | |
1748 | "[AS4] AS4PATHmangle: AS_CONFED_SEQUENCE falls across 2/4 ASN boundary somewhere, broken.."); | |
1749 | hops = seg->length; | |
1750 | } | |
1751 | /* fallthru */ | |
1752 | case AS_SEQUENCE: | |
1753 | cpasns = MIN(seg->length, hops); | |
1754 | hops -= seg->length; | |
1755 | } | |
1756 | ||
1757 | assert(cpasns <= seg->length); | |
1758 | ||
1759 | newseg = assegment_new(seg->type, 0); | |
1760 | newseg = assegment_append_asns(newseg, seg->as, cpasns); | |
1761 | ||
1762 | if (!newpath) { | |
1763 | newpath = aspath_new(aspath->asnotation); | |
1764 | newpath->segments = newseg; | |
1765 | } else | |
1766 | prevseg->next = newseg; | |
1767 | ||
1768 | prevseg = newseg; | |
1769 | seg = seg->next; | |
1770 | } | |
1771 | ||
1772 | /* We may be able to join some segments here, and we must | |
1773 | * do this because... we want normalised aspaths in out hash | |
1774 | * and we do not want to stumble in aspath_put. | |
1775 | */ | |
1776 | mergedpath = aspath_merge(newpath, aspath_dup(as4path)); | |
1777 | aspath_free(newpath); | |
1778 | mergedpath->segments = assegment_normalise(mergedpath->segments); | |
1779 | aspath_str_update(mergedpath, false); | |
1780 | ||
1781 | if (BGP_DEBUG(as4, AS4)) | |
1782 | zlog_debug("[AS4] result of synthesizing is %s", | |
1783 | mergedpath->str); | |
1784 | ||
1785 | return mergedpath; | |
1786 | } | |
1787 | ||
1788 | /* Compare leftmost AS value for MED check. If as1's leftmost AS and | |
1789 | as2's leftmost AS is same return 1. (confederation as-path | |
1790 | only). */ | |
1791 | bool aspath_cmp_left_confed(const struct aspath *aspath1, | |
1792 | const struct aspath *aspath2) | |
1793 | { | |
1794 | if (!(aspath1 && aspath2)) | |
1795 | return false; | |
1796 | ||
1797 | if (!(aspath1->segments && aspath2->segments)) | |
1798 | return false; | |
1799 | ||
1800 | if ((aspath1->segments->type != AS_CONFED_SEQUENCE) | |
1801 | || (aspath2->segments->type != AS_CONFED_SEQUENCE)) | |
1802 | return false; | |
1803 | ||
1804 | if (aspath1->segments->as[0] == aspath2->segments->as[0]) | |
1805 | return true; | |
1806 | ||
1807 | return false; | |
1808 | } | |
1809 | ||
1810 | /* Delete all AS_CONFED_SEQUENCE/SET segments from aspath. | |
1811 | * RFC 5065 section 4.1.c.1 | |
1812 | * | |
1813 | * 1) if any path segments of the AS_PATH are of the type | |
1814 | * AS_CONFED_SEQUENCE or AS_CONFED_SET, those segments MUST be | |
1815 | * removed from the AS_PATH attribute, leaving the sanitized | |
1816 | * AS_PATH attribute to be operated on by steps 2, 3 or 4. | |
1817 | */ | |
1818 | struct aspath *aspath_delete_confed_seq(struct aspath *aspath) | |
1819 | { | |
1820 | struct assegment *seg, *prev, *next; | |
1821 | char removed_confed_segment; | |
1822 | ||
1823 | if (!(aspath && aspath->segments)) | |
1824 | return aspath; | |
1825 | ||
1826 | seg = aspath->segments; | |
1827 | removed_confed_segment = 0; | |
1828 | next = NULL; | |
1829 | prev = NULL; | |
1830 | ||
1831 | while (seg) { | |
1832 | next = seg->next; | |
1833 | ||
1834 | if (seg->type == AS_CONFED_SEQUENCE | |
1835 | || seg->type == AS_CONFED_SET) { | |
1836 | /* This is the first segment in the aspath */ | |
1837 | if (aspath->segments == seg) | |
1838 | aspath->segments = seg->next; | |
1839 | else | |
1840 | prev->next = seg->next; | |
1841 | ||
1842 | assegment_free(seg); | |
1843 | removed_confed_segment = 1; | |
1844 | } else | |
1845 | prev = seg; | |
1846 | ||
1847 | seg = next; | |
1848 | } | |
1849 | ||
1850 | if (removed_confed_segment) | |
1851 | aspath_str_update(aspath, false); | |
1852 | ||
1853 | return aspath; | |
1854 | } | |
1855 | ||
1856 | /* Add new AS number to the leftmost part of the aspath as | |
1857 | AS_CONFED_SEQUENCE. */ | |
1858 | struct aspath *aspath_add_confed_seq(struct aspath *aspath, as_t asno) | |
1859 | { | |
1860 | return aspath_add_asns(aspath, asno, AS_CONFED_SEQUENCE, 1); | |
1861 | } | |
1862 | ||
1863 | /* Add new as value to as path structure. */ | |
1864 | static void aspath_as_add(struct aspath *as, as_t asno) | |
1865 | { | |
1866 | struct assegment *seg = as->segments; | |
1867 | ||
1868 | if (!seg) | |
1869 | return; | |
1870 | ||
1871 | /* Last segment search procedure. */ | |
1872 | while (seg->next) | |
1873 | seg = seg->next; | |
1874 | ||
1875 | assegment_append_asns(seg, &asno, 1); | |
1876 | } | |
1877 | ||
1878 | /* Add new as segment to the as path. */ | |
1879 | static void aspath_segment_add(struct aspath *as, int type) | |
1880 | { | |
1881 | struct assegment *seg = as->segments; | |
1882 | struct assegment *new = assegment_new(type, 0); | |
1883 | ||
1884 | if (seg) { | |
1885 | while (seg->next) | |
1886 | seg = seg->next; | |
1887 | seg->next = new; | |
1888 | } else | |
1889 | as->segments = new; | |
1890 | } | |
1891 | ||
1892 | struct aspath *aspath_empty(enum asnotation_mode asnotation) | |
1893 | { | |
1894 | return aspath_parse(NULL, 0, 1, asnotation); /* 32Bit ;-) */ | |
1895 | } | |
1896 | ||
1897 | struct aspath *aspath_empty_get(void) | |
1898 | { | |
1899 | struct aspath *aspath; | |
1900 | ||
1901 | aspath = aspath_new(bgp_get_asnotation(NULL)); | |
1902 | aspath_make_str_count(aspath, false); | |
1903 | return aspath; | |
1904 | } | |
1905 | ||
1906 | unsigned long aspath_count(void) | |
1907 | { | |
1908 | return ashash->count; | |
1909 | } | |
1910 | ||
1911 | /* | |
1912 | Theoretically, one as path can have: | |
1913 | ||
1914 | One BGP packet size should be less than 4096. | |
1915 | One BGP attribute size should be less than 4096 - BGP header size. | |
1916 | One BGP aspath size should be less than 4096 - BGP header size - | |
1917 | BGP mandantry attribute size. | |
1918 | */ | |
1919 | ||
1920 | /* AS path string lexical token enum. */ | |
1921 | enum as_token { | |
1922 | as_token_asval, | |
1923 | as_token_set_start, | |
1924 | as_token_set_end, | |
1925 | as_token_confed_seq_start, | |
1926 | as_token_confed_seq_end, | |
1927 | as_token_confed_set_start, | |
1928 | as_token_confed_set_end, | |
1929 | as_token_unknown | |
1930 | }; | |
1931 | ||
1932 | /* Return next token and point for string parse. */ | |
1933 | static const char *aspath_gettoken(const char *buf, enum as_token *token, | |
1934 | unsigned long *asno) | |
1935 | { | |
1936 | const char *p = buf; | |
1937 | as_t asval; | |
1938 | bool found = false; | |
1939 | ||
1940 | /* Skip separators (space for sequences, ',' for sets). */ | |
1941 | while (isspace((unsigned char)*p) || *p == ',') | |
1942 | p++; | |
1943 | ||
1944 | /* Check the end of the string and type specify characters | |
1945 | (e.g. {}()). */ | |
1946 | switch (*p) { | |
1947 | case '\0': | |
1948 | return NULL; | |
1949 | case '{': | |
1950 | *token = as_token_set_start; | |
1951 | p++; | |
1952 | return p; | |
1953 | case '}': | |
1954 | *token = as_token_set_end; | |
1955 | p++; | |
1956 | return p; | |
1957 | case '(': | |
1958 | *token = as_token_confed_seq_start; | |
1959 | p++; | |
1960 | return p; | |
1961 | case ')': | |
1962 | *token = as_token_confed_seq_end; | |
1963 | p++; | |
1964 | return p; | |
1965 | case '[': | |
1966 | *token = as_token_confed_set_start; | |
1967 | p++; | |
1968 | return p; | |
1969 | case ']': | |
1970 | *token = as_token_confed_set_end; | |
1971 | p++; | |
1972 | return p; | |
1973 | } | |
1974 | ||
1975 | asval = 0; | |
1976 | p = asn_str2asn_parse(p, &asval, &found); | |
1977 | if (found) { | |
1978 | *asno = asval; | |
1979 | *token = as_token_asval; | |
1980 | } else | |
1981 | *token = as_token_unknown; | |
1982 | return p; | |
1983 | } | |
1984 | ||
1985 | struct aspath *aspath_str2aspath(const char *str, | |
1986 | enum asnotation_mode asnotation) | |
1987 | { | |
1988 | enum as_token token = as_token_unknown; | |
1989 | unsigned short as_type; | |
1990 | unsigned long asno = 0; | |
1991 | struct aspath *aspath; | |
1992 | int needtype; | |
1993 | ||
1994 | aspath = aspath_new(asnotation); | |
1995 | ||
1996 | /* We start default type as AS_SEQUENCE. */ | |
1997 | as_type = AS_SEQUENCE; | |
1998 | needtype = 1; | |
1999 | ||
2000 | while ((str = aspath_gettoken(str, &token, &asno)) != NULL) { | |
2001 | switch (token) { | |
2002 | case as_token_asval: | |
2003 | if (needtype) { | |
2004 | aspath_segment_add(aspath, as_type); | |
2005 | needtype = 0; | |
2006 | } | |
2007 | aspath_as_add(aspath, asno); | |
2008 | break; | |
2009 | case as_token_set_start: | |
2010 | as_type = AS_SET; | |
2011 | aspath_segment_add(aspath, as_type); | |
2012 | needtype = 0; | |
2013 | break; | |
2014 | case as_token_set_end: | |
2015 | as_type = AS_SEQUENCE; | |
2016 | needtype = 1; | |
2017 | break; | |
2018 | case as_token_confed_seq_start: | |
2019 | as_type = AS_CONFED_SEQUENCE; | |
2020 | aspath_segment_add(aspath, as_type); | |
2021 | needtype = 0; | |
2022 | break; | |
2023 | case as_token_confed_seq_end: | |
2024 | as_type = AS_SEQUENCE; | |
2025 | needtype = 1; | |
2026 | break; | |
2027 | case as_token_confed_set_start: | |
2028 | as_type = AS_CONFED_SET; | |
2029 | aspath_segment_add(aspath, as_type); | |
2030 | needtype = 0; | |
2031 | break; | |
2032 | case as_token_confed_set_end: | |
2033 | as_type = AS_SEQUENCE; | |
2034 | needtype = 1; | |
2035 | break; | |
2036 | case as_token_unknown: | |
2037 | default: | |
2038 | aspath_free(aspath); | |
2039 | return NULL; | |
2040 | } | |
2041 | } | |
2042 | ||
2043 | aspath_make_str_count(aspath, false); | |
2044 | ||
2045 | return aspath; | |
2046 | } | |
2047 | ||
2048 | /* Make hash value by raw aspath data. */ | |
2049 | unsigned int aspath_key_make(const void *p) | |
2050 | { | |
2051 | const struct aspath *aspath = p; | |
2052 | unsigned int key = 0; | |
2053 | ||
2054 | if (!aspath->str) | |
2055 | aspath_str_update((struct aspath *)aspath, false); | |
2056 | ||
2057 | key = jhash(aspath->str, aspath->str_len, 2334325); | |
2058 | ||
2059 | return key; | |
2060 | } | |
2061 | ||
2062 | /* If two aspath have same value then return 1 else return 0 */ | |
2063 | bool aspath_cmp(const void *arg1, const void *arg2) | |
2064 | { | |
2065 | const struct assegment *seg1 = ((const struct aspath *)arg1)->segments; | |
2066 | const struct assegment *seg2 = ((const struct aspath *)arg2)->segments; | |
2067 | ||
2068 | if (((const struct aspath *)arg1)->asnotation != | |
2069 | ((const struct aspath *)arg2)->asnotation) | |
2070 | return false; | |
2071 | ||
2072 | while (seg1 || seg2) { | |
2073 | int i; | |
2074 | if ((!seg1 && seg2) || (seg1 && !seg2)) | |
2075 | return false; | |
2076 | if (seg1->type != seg2->type) | |
2077 | return false; | |
2078 | if (seg1->length != seg2->length) | |
2079 | return false; | |
2080 | for (i = 0; i < seg1->length; i++) | |
2081 | if (seg1->as[i] != seg2->as[i]) | |
2082 | return false; | |
2083 | seg1 = seg1->next; | |
2084 | seg2 = seg2->next; | |
2085 | } | |
2086 | return true; | |
2087 | } | |
2088 | ||
2089 | /* AS path hash initialize. */ | |
2090 | void aspath_init(void) | |
2091 | { | |
2092 | ashash = hash_create_size(32768, aspath_key_make, aspath_cmp, | |
2093 | "BGP AS Path"); | |
2094 | } | |
2095 | ||
2096 | void aspath_finish(void) | |
2097 | { | |
2098 | hash_clean_and_free(&ashash, (void (*)(void *))aspath_free); | |
2099 | ||
2100 | if (snmp_stream) | |
2101 | stream_free(snmp_stream); | |
2102 | } | |
2103 | ||
2104 | /* return and as path value */ | |
2105 | const char *aspath_print(struct aspath *as) | |
2106 | { | |
2107 | return (as ? as->str : NULL); | |
2108 | } | |
2109 | ||
2110 | /* Printing functions */ | |
2111 | /* Feed the AS_PATH to the vty; the space suffix follows it only in case | |
2112 | * AS_PATH wasn't empty. | |
2113 | */ | |
2114 | void aspath_print_vty(struct vty *vty, struct aspath *as) | |
2115 | { | |
2116 | vty_out(vty, "%s%s", as->str, as->str_len ? " " : ""); | |
2117 | } | |
2118 | ||
2119 | static void aspath_show_all_iterator(struct hash_bucket *bucket, | |
2120 | struct vty *vty) | |
2121 | { | |
2122 | struct aspath *as; | |
2123 | ||
2124 | as = (struct aspath *)bucket->data; | |
2125 | ||
2126 | vty_out(vty, "[%p:%u] (%ld) ", (void *)bucket, bucket->key, as->refcnt); | |
2127 | vty_out(vty, "%s\n", as->str); | |
2128 | } | |
2129 | ||
2130 | /* Print all aspath and hash information. This function is used from | |
2131 | `show [ip] bgp paths' command. */ | |
2132 | void aspath_print_all_vty(struct vty *vty) | |
2133 | { | |
2134 | hash_iterate(ashash, (void (*)(struct hash_bucket *, | |
2135 | void *))aspath_show_all_iterator, | |
2136 | vty); | |
2137 | } | |
2138 | ||
2139 | static struct aspath *bgp_aggr_aspath_lookup(struct bgp_aggregate *aggregate, | |
2140 | struct aspath *aspath) | |
2141 | { | |
2142 | return hash_lookup(aggregate->aspath_hash, aspath); | |
2143 | } | |
2144 | ||
2145 | static void *bgp_aggr_aspath_hash_alloc(void *p) | |
2146 | { | |
2147 | struct aspath *ref = (struct aspath *)p; | |
2148 | struct aspath *aspath = NULL; | |
2149 | ||
2150 | aspath = aspath_dup(ref); | |
2151 | return aspath; | |
2152 | } | |
2153 | ||
2154 | static void bgp_aggr_aspath_prepare(struct hash_bucket *hb, void *arg) | |
2155 | { | |
2156 | struct aspath *hb_aspath = hb->data; | |
2157 | struct aspath **aggr_aspath = arg; | |
2158 | struct aspath *aspath = NULL; | |
2159 | ||
2160 | if (*aggr_aspath) { | |
2161 | aspath = aspath_aggregate(*aggr_aspath, hb_aspath); | |
2162 | aspath_free(*aggr_aspath); | |
2163 | *aggr_aspath = aspath; | |
2164 | } else { | |
2165 | *aggr_aspath = aspath_dup(hb_aspath); | |
2166 | } | |
2167 | } | |
2168 | ||
2169 | void bgp_aggr_aspath_remove(void *arg) | |
2170 | { | |
2171 | struct aspath *aspath = arg; | |
2172 | ||
2173 | aspath_free(aspath); | |
2174 | } | |
2175 | ||
2176 | void bgp_compute_aggregate_aspath(struct bgp_aggregate *aggregate, | |
2177 | struct aspath *aspath) | |
2178 | { | |
2179 | bgp_compute_aggregate_aspath_hash(aggregate, aspath); | |
2180 | ||
2181 | bgp_compute_aggregate_aspath_val(aggregate); | |
2182 | ||
2183 | } | |
2184 | ||
2185 | void bgp_compute_aggregate_aspath_hash(struct bgp_aggregate *aggregate, | |
2186 | struct aspath *aspath) | |
2187 | { | |
2188 | struct aspath *aggr_aspath = NULL; | |
2189 | ||
2190 | if ((aggregate == NULL) || (aspath == NULL)) | |
2191 | return; | |
2192 | ||
2193 | /* Create hash if not already created. | |
2194 | */ | |
2195 | if (aggregate->aspath_hash == NULL) | |
2196 | aggregate->aspath_hash = hash_create( | |
2197 | aspath_key_make, aspath_cmp, | |
2198 | "BGP Aggregator as-path hash"); | |
2199 | ||
2200 | aggr_aspath = bgp_aggr_aspath_lookup(aggregate, aspath); | |
2201 | if (aggr_aspath == NULL) { | |
2202 | /* Insert as-path into hash. | |
2203 | */ | |
2204 | aggr_aspath = hash_get(aggregate->aspath_hash, aspath, | |
2205 | bgp_aggr_aspath_hash_alloc); | |
2206 | } | |
2207 | ||
2208 | /* Increment reference counter. | |
2209 | */ | |
2210 | aggr_aspath->refcnt++; | |
2211 | } | |
2212 | ||
2213 | void bgp_compute_aggregate_aspath_val(struct bgp_aggregate *aggregate) | |
2214 | { | |
2215 | if (aggregate == NULL) | |
2216 | return; | |
2217 | /* Re-compute aggregate's as-path. | |
2218 | */ | |
2219 | if (aggregate->aspath) { | |
2220 | aspath_free(aggregate->aspath); | |
2221 | aggregate->aspath = NULL; | |
2222 | } | |
2223 | if (aggregate->aspath_hash | |
2224 | && aggregate->aspath_hash->count) { | |
2225 | hash_iterate(aggregate->aspath_hash, | |
2226 | bgp_aggr_aspath_prepare, | |
2227 | &aggregate->aspath); | |
2228 | } | |
2229 | } | |
2230 | ||
2231 | void bgp_remove_aspath_from_aggregate(struct bgp_aggregate *aggregate, | |
2232 | struct aspath *aspath) | |
2233 | { | |
2234 | struct aspath *aggr_aspath = NULL; | |
2235 | struct aspath *ret_aspath = NULL; | |
2236 | ||
2237 | if ((!aggregate) | |
2238 | || (!aggregate->aspath_hash) | |
2239 | || (!aspath)) | |
2240 | return; | |
2241 | ||
2242 | /* Look-up the aspath in the hash. | |
2243 | */ | |
2244 | aggr_aspath = bgp_aggr_aspath_lookup(aggregate, aspath); | |
2245 | if (aggr_aspath) { | |
2246 | aggr_aspath->refcnt--; | |
2247 | ||
2248 | if (aggr_aspath->refcnt == 0) { | |
2249 | ret_aspath = hash_release(aggregate->aspath_hash, | |
2250 | aggr_aspath); | |
2251 | aspath_free(ret_aspath); | |
2252 | ret_aspath = NULL; | |
2253 | ||
2254 | /* Remove aggregate's old as-path. | |
2255 | */ | |
2256 | aspath_free(aggregate->aspath); | |
2257 | aggregate->aspath = NULL; | |
2258 | ||
2259 | bgp_compute_aggregate_aspath_val(aggregate); | |
2260 | } | |
2261 | } | |
2262 | } | |
2263 | ||
2264 | void bgp_remove_aspath_from_aggregate_hash(struct bgp_aggregate *aggregate, | |
2265 | struct aspath *aspath) | |
2266 | { | |
2267 | struct aspath *aggr_aspath = NULL; | |
2268 | struct aspath *ret_aspath = NULL; | |
2269 | ||
2270 | if ((!aggregate) | |
2271 | || (!aggregate->aspath_hash) | |
2272 | || (!aspath)) | |
2273 | return; | |
2274 | ||
2275 | /* Look-up the aspath in the hash. | |
2276 | */ | |
2277 | aggr_aspath = bgp_aggr_aspath_lookup(aggregate, aspath); | |
2278 | if (aggr_aspath) { | |
2279 | aggr_aspath->refcnt--; | |
2280 | ||
2281 | if (aggr_aspath->refcnt == 0) { | |
2282 | ret_aspath = hash_release(aggregate->aspath_hash, | |
2283 | aggr_aspath); | |
2284 | aspath_free(ret_aspath); | |
2285 | ret_aspath = NULL; | |
2286 | } | |
2287 | } | |
2288 | } | |
2289 |