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