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