]>
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" |
718e3744 | 31 | |
32 | #include "bgpd/bgpd.h" | |
33 | #include "bgpd/bgp_aspath.h" | |
34 | \f | |
35 | /* Attr. Flags and Attr. Type Code. */ | |
36 | #define AS_HEADER_SIZE 2 | |
37 | ||
38 | /* Two octet is used for AS value. */ | |
39 | #define AS_VALUE_SIZE sizeof (as_t) | |
40 | ||
fe69a505 | 41 | /* Maximum protocol segment length value */ |
42 | #define AS_SEGMENT_MAX 255 | |
43 | ||
44 | /* The following length and size macros relate specifically to Quagga's | |
45 | * internal representation of AS-Segments, not per se to the on-wire | |
46 | * sizes and lengths. At present (200508) they sort of match, however | |
47 | * the ONLY functions which should now about the on-wire syntax are | |
48 | * aspath_put, assegment_put and assegment_parse. | |
49 | */ | |
50 | ||
51 | /* Calculated size in bytes of ASN segment data to hold N ASN's */ | |
52 | #define ASSEGMENT_DATA_SIZE(N) ((N) * AS_VALUE_SIZE) | |
718e3744 | 53 | |
fe69a505 | 54 | /* Calculated size of segment struct to hold N ASN's */ |
55 | #define ASSEGMENT_SIZE(N) (AS_HEADER_SIZE + ASSEGMENT_DATA_SIZE (N)) | |
56 | ||
57 | /* AS segment octet length. */ | |
58 | #define ASSEGMENT_LEN(X) ASSEGMENT_SIZE((X)->length) | |
59 | ||
60 | /* AS_SEQUENCE segments can be packed together */ | |
61 | /* Can the types of X and Y be considered for packing? */ | |
62 | #define ASSEGMENT_TYPES_PACKABLE(X,Y) \ | |
63 | ( ((X)->type == (Y)->type) \ | |
64 | && ((X)->type == AS_SEQUENCE)) | |
65 | /* Types and length of X,Y suitable for packing? */ | |
66 | #define ASSEGMENTS_PACKABLE(X,Y) \ | |
67 | ( ASSEGMENT_TYPES_PACKABLE( (X), (Y)) \ | |
68 | && ( ((X)->length + (Y)->length) <= AS_SEGMENT_MAX ) ) | |
69 | ||
70 | /* As segment header - the on-wire representation | |
71 | * NOT the internal representation! | |
72 | */ | |
73 | struct assegment_header | |
718e3744 | 74 | { |
75 | u_char type; | |
76 | u_char length; | |
718e3744 | 77 | }; |
78 | ||
79 | /* Hash for aspath. This is the top level structure of AS path. */ | |
80 | struct hash *ashash; | |
8fdc32ab | 81 | |
82 | /* Stream for SNMP. See aspath_snmp_pathseg */ | |
83 | static struct stream *snmp_stream; | |
718e3744 | 84 | \f |
fe69a505 | 85 | static inline as_t * |
86 | assegment_data_new (int num) | |
87 | { | |
88 | return (XCALLOC (MTYPE_AS_SEG_DATA, ASSEGMENT_DATA_SIZE (num))); | |
89 | } | |
90 | ||
91 | static inline void | |
92 | assegment_data_free (as_t *asdata) | |
93 | { | |
94 | XFREE (MTYPE_AS_SEG_DATA,asdata); | |
95 | } | |
96 | ||
97 | /* Get a new segment. Note that 0 is an allowed length, | |
98 | * and will result in a segment with no allocated data segment. | |
99 | * the caller should immediately assign data to the segment, as the segment | |
100 | * otherwise is not generally valid | |
101 | */ | |
102 | static struct assegment * | |
103 | assegment_new (u_char type, u_short length) | |
104 | { | |
105 | struct assegment *new; | |
106 | ||
107 | new = XCALLOC (MTYPE_AS_SEG, sizeof (struct assegment)); | |
108 | ||
109 | if (length) | |
110 | new->as = assegment_data_new (length); | |
111 | ||
112 | new->length = length; | |
113 | new->type = type; | |
114 | ||
115 | return new; | |
116 | } | |
117 | ||
118 | static void | |
119 | assegment_free (struct assegment *seg) | |
120 | { | |
121 | if (!seg) | |
122 | return; | |
123 | ||
124 | if (seg->as) | |
125 | XFREE (MTYPE_AS_SEG_DATA, seg->as); | |
126 | memset (seg, 0xfe, sizeof(struct assegment)); | |
127 | XFREE (MTYPE_AS_SEG, seg); | |
128 | ||
129 | return; | |
130 | } | |
131 | ||
132 | /* free entire chain of segments */ | |
133 | static void | |
134 | assegment_free_all (struct assegment *seg) | |
135 | { | |
136 | struct assegment *prev; | |
137 | ||
138 | while (seg) | |
139 | { | |
140 | prev = seg; | |
141 | seg = seg->next; | |
142 | assegment_free (prev); | |
143 | } | |
144 | } | |
145 | ||
146 | /* Duplicate just the given assegment and its data */ | |
147 | static struct assegment * | |
148 | assegment_dup (struct assegment *seg) | |
149 | { | |
150 | struct assegment *new; | |
151 | ||
152 | new = assegment_new (seg->type, seg->length); | |
153 | memcpy (new->as, seg->as, ASSEGMENT_DATA_SIZE (new->length) ); | |
154 | ||
155 | return new; | |
156 | } | |
157 | ||
158 | /* Duplicate entire chain of assegments, return the head */ | |
159 | static struct assegment * | |
160 | assegment_dup_all (struct assegment *seg) | |
161 | { | |
162 | struct assegment *new = NULL; | |
163 | struct assegment *head = NULL; | |
164 | ||
165 | while (seg) | |
166 | { | |
167 | if (head) | |
168 | { | |
169 | new->next = assegment_dup (seg); | |
170 | new = new->next; | |
171 | } | |
172 | else | |
173 | head = new = assegment_dup (seg); | |
174 | ||
175 | seg = seg->next; | |
176 | } | |
177 | return head; | |
178 | } | |
179 | ||
180 | /* prepend the as number to given segment, given num of times */ | |
181 | static struct assegment * | |
182 | assegment_prepend_asns (struct assegment *seg, as_t asnum, int num) | |
183 | { | |
184 | as_t *newas; | |
185 | ||
186 | if (!num) | |
187 | return seg; | |
188 | ||
189 | if (num >= AS_SEGMENT_MAX) | |
190 | return seg; /* we don't do huge prepends */ | |
191 | ||
192 | newas = assegment_data_new (seg->length + num); | |
193 | ||
194 | if (newas) | |
195 | { | |
196 | int i; | |
197 | for (i = 0; i < num; i++) | |
198 | newas[i] = asnum; | |
199 | ||
200 | memcpy (newas + num, seg->as, ASSEGMENT_DATA_SIZE (seg->length)); | |
201 | XFREE (MTYPE_AS_SEG_DATA, seg->as); | |
202 | seg->as = newas; | |
203 | seg->length += num; | |
204 | return seg; | |
205 | } | |
206 | ||
207 | assegment_free_all (seg); | |
208 | return NULL; | |
209 | } | |
210 | ||
211 | /* append given array of as numbers to the segment */ | |
212 | static struct assegment * | |
213 | assegment_append_asns (struct assegment *seg, as_t *asnos, int num) | |
214 | { | |
02335429 | 215 | as_t *newas; |
216 | ||
217 | newas = XREALLOC (MTYPE_AS_SEG_DATA, seg->as, | |
fe69a505 | 218 | ASSEGMENT_DATA_SIZE (seg->length + num)); |
219 | ||
02335429 | 220 | if (newas) |
fe69a505 | 221 | { |
02335429 | 222 | seg->as = newas; |
fe69a505 | 223 | memcpy (seg->as + seg->length, asnos, ASSEGMENT_DATA_SIZE(num)); |
224 | seg->length += num; | |
225 | return seg; | |
226 | } | |
227 | ||
228 | assegment_free_all (seg); | |
229 | return NULL; | |
230 | } | |
231 | ||
232 | static int | |
233 | int_cmp (const void *p1, const void *p2) | |
234 | { | |
235 | const as_t *as1 = p1; | |
236 | const as_t *as2 = p2; | |
237 | ||
238 | return (*as1 == *as2) | |
239 | ? 0 : ( (*as1 > *as2) ? 1 : -1); | |
240 | } | |
241 | ||
242 | /* normalise the segment. | |
243 | * In particular, merge runs of AS_SEQUENCEs into one segment | |
244 | * Internally, we do not care about the wire segment length limit, and | |
245 | * we want each distinct AS_PATHs to have the exact same internal | |
246 | * representation - eg, so that our hashing actually works.. | |
247 | */ | |
248 | static struct assegment * | |
249 | assegment_normalise (struct assegment *head) | |
250 | { | |
251 | struct assegment *seg = head, *pin; | |
252 | struct assegment *tmp; | |
253 | ||
254 | if (!head) | |
255 | return head; | |
256 | ||
257 | while (seg) | |
258 | { | |
259 | pin = seg; | |
260 | ||
261 | /* Sort values SET segments, for determinism in paths to aid | |
262 | * creation of hash values / path comparisons | |
263 | * and because it helps other lesser implementations ;) | |
264 | */ | |
265 | if (seg->type == AS_SET || seg->type == AS_CONFED_SET) | |
266 | qsort (seg->as, seg->length, sizeof(as_t), int_cmp); | |
267 | ||
268 | /* read ahead from the current, pinned segment while the segments | |
269 | * are packable/mergeable. Append all following packable segments | |
270 | * to the segment we have pinned and remove these appended | |
271 | * segments. | |
272 | */ | |
273 | while (pin->next && ASSEGMENT_TYPES_PACKABLE(pin, pin->next)) | |
274 | { | |
275 | tmp = pin->next; | |
276 | seg = pin->next; | |
277 | ||
278 | /* append the next sequence to the pinned sequence */ | |
279 | pin = assegment_append_asns (pin, seg->as, seg->length); | |
280 | ||
281 | /* bypass the next sequence */ | |
282 | pin->next = seg->next; | |
283 | ||
284 | /* get rid of the now referenceless segment */ | |
285 | assegment_free (tmp); | |
286 | ||
287 | } | |
288 | ||
289 | seg = pin->next; | |
290 | } | |
291 | return head; | |
292 | } | |
293 | \f | |
718e3744 | 294 | static struct aspath * |
fe69a505 | 295 | aspath_new (void) |
718e3744 | 296 | { |
297 | struct aspath *aspath; | |
298 | ||
299 | aspath = XMALLOC (MTYPE_AS_PATH, sizeof (struct aspath)); | |
300 | memset (aspath, 0, sizeof (struct aspath)); | |
301 | return aspath; | |
302 | } | |
303 | ||
304 | /* Free AS path structure. */ | |
305 | void | |
306 | aspath_free (struct aspath *aspath) | |
307 | { | |
308 | if (!aspath) | |
309 | return; | |
fe69a505 | 310 | if (aspath->segments) |
311 | assegment_free_all (aspath->segments); | |
718e3744 | 312 | if (aspath->str) |
313 | XFREE (MTYPE_AS_STR, aspath->str); | |
314 | XFREE (MTYPE_AS_PATH, aspath); | |
315 | } | |
316 | ||
317 | /* Unintern aspath from AS path bucket. */ | |
318 | void | |
319 | aspath_unintern (struct aspath *aspath) | |
320 | { | |
321 | struct aspath *ret; | |
322 | ||
323 | if (aspath->refcnt) | |
324 | aspath->refcnt--; | |
325 | ||
326 | if (aspath->refcnt == 0) | |
327 | { | |
328 | /* This aspath must exist in aspath hash table. */ | |
329 | ret = hash_release (ashash, aspath); | |
330 | assert (ret != NULL); | |
331 | aspath_free (aspath); | |
332 | } | |
333 | } | |
334 | ||
335 | /* Return the start or end delimiters for a particular Segment type */ | |
336 | #define AS_SEG_START 0 | |
337 | #define AS_SEG_END 1 | |
338 | static char | |
339 | aspath_delimiter_char (u_char type, u_char which) | |
340 | { | |
341 | int i; | |
342 | struct | |
343 | { | |
344 | int type; | |
345 | char start; | |
346 | char end; | |
347 | } aspath_delim_char [] = | |
348 | { | |
349 | { AS_SET, '{', '}' }, | |
718e3744 | 350 | { AS_CONFED_SET, '[', ']' }, |
351 | { AS_CONFED_SEQUENCE, '(', ')' }, | |
352 | { 0 } | |
353 | }; | |
354 | ||
355 | for (i = 0; aspath_delim_char[i].type != 0; i++) | |
356 | { | |
357 | if (aspath_delim_char[i].type == type) | |
358 | { | |
359 | if (which == AS_SEG_START) | |
360 | return aspath_delim_char[i].start; | |
361 | else if (which == AS_SEG_END) | |
362 | return aspath_delim_char[i].end; | |
363 | } | |
364 | } | |
365 | return ' '; | |
366 | } | |
367 | ||
fe69a505 | 368 | /* countup asns from this segment and index onward */ |
369 | static int | |
370 | assegment_count_asns (struct assegment *seg, int from) | |
371 | { | |
372 | int count = 0; | |
373 | while (seg) | |
374 | { | |
375 | if (!from) | |
376 | count += seg->length; | |
377 | else | |
378 | { | |
379 | count += (seg->length - from); | |
380 | from = 0; | |
381 | } | |
382 | seg = seg->next; | |
383 | } | |
384 | return count; | |
385 | } | |
386 | ||
387 | unsigned int | |
388 | aspath_count_confeds (struct aspath *aspath) | |
389 | { | |
390 | int count = 0; | |
391 | struct assegment *seg = aspath->segments; | |
392 | ||
393 | while (seg) | |
394 | { | |
395 | if (seg->type == AS_CONFED_SEQUENCE) | |
396 | count += seg->length; | |
397 | else if (seg->type == AS_CONFED_SET) | |
398 | count++; | |
399 | ||
400 | seg = seg->next; | |
401 | } | |
402 | return count; | |
403 | } | |
404 | ||
405 | unsigned int | |
406 | aspath_count_hops (struct aspath *aspath) | |
407 | { | |
408 | int count = 0; | |
409 | struct assegment *seg = aspath->segments; | |
410 | ||
411 | while (seg) | |
412 | { | |
413 | if (seg->type == AS_SEQUENCE) | |
414 | count += seg->length; | |
415 | else if (seg->type == AS_SET) | |
416 | count++; | |
417 | ||
418 | seg = seg->next; | |
419 | } | |
420 | return count; | |
421 | } | |
422 | ||
423 | unsigned int | |
424 | aspath_size (struct aspath *aspath) | |
425 | { | |
426 | int size = 0; | |
427 | struct assegment *seg = aspath->segments; | |
428 | ||
429 | while (seg) | |
430 | { | |
431 | size += ASSEGMENT_SIZE(seg->length); | |
432 | seg = seg->next; | |
433 | } | |
434 | return size; | |
435 | } | |
436 | ||
2815e61f PJ |
437 | /* Return highest public ASN in path */ |
438 | as_t | |
439 | aspath_highest (struct aspath *aspath) | |
440 | { | |
441 | struct assegment *seg = aspath->segments; | |
442 | as_t highest = 0; | |
443 | unsigned int i; | |
444 | ||
445 | while (seg) | |
446 | { | |
447 | for (i = 0; i < seg->length; i++) | |
448 | if (seg->as[i] > highest | |
449 | && (seg->as[i] < BGP_PRIVATE_AS_MIN | |
450 | || seg->as[i] > BGP_PRIVATE_AS_MAX)) | |
451 | highest = seg->as[i]; | |
452 | seg = seg->next; | |
453 | } | |
454 | return highest; | |
455 | } | |
456 | ||
718e3744 | 457 | /* Convert aspath structure to string expression. */ |
94f2b392 | 458 | static char * |
718e3744 | 459 | aspath_make_str_count (struct aspath *as) |
460 | { | |
fe69a505 | 461 | struct assegment *seg; |
462 | int str_size; | |
463 | int len = 0; | |
c9e52be3 | 464 | char *str_buf; |
718e3744 | 465 | |
466 | /* Empty aspath. */ | |
fe69a505 | 467 | if (!as->segments) |
718e3744 | 468 | { |
469 | str_buf = XMALLOC (MTYPE_AS_STR, 1); | |
470 | str_buf[0] = '\0'; | |
718e3744 | 471 | return str_buf; |
472 | } | |
fe69a505 | 473 | |
474 | seg = as->segments; | |
475 | ||
476 | /* ASN takes 5 chars at least, plus seperator, see below. | |
477 | * If there is one differing segment type, we need an additional | |
478 | * 2 chars for segment delimiters, and the final '\0'. | |
479 | * Hopefully this is large enough to avoid hitting the realloc | |
480 | * code below for most common sequences. | |
481 | */ | |
482 | #define ASN_STR_LEN (5 + 1) | |
483 | str_size = MAX (assegment_count_asns (seg, 0) * ASN_STR_LEN + 2 + 1, | |
484 | ASPATH_STR_DEFAULT_LEN); | |
718e3744 | 485 | str_buf = XMALLOC (MTYPE_AS_STR, str_size); |
718e3744 | 486 | |
fe69a505 | 487 | while (seg) |
718e3744 | 488 | { |
489 | int i; | |
fe69a505 | 490 | char seperator; |
718e3744 | 491 | |
fe69a505 | 492 | /* Check AS type validity. Set seperator for segment */ |
493 | switch (seg->type) | |
494 | { | |
495 | case AS_SET: | |
496 | case AS_CONFED_SET: | |
497 | seperator = ','; | |
498 | break; | |
499 | case AS_SEQUENCE: | |
500 | case AS_CONFED_SEQUENCE: | |
501 | seperator = ' '; | |
502 | break; | |
503 | default: | |
504 | XFREE (MTYPE_AS_STR, str_buf); | |
505 | return NULL; | |
506 | } | |
507 | ||
508 | /* We might need to increase str_buf, particularly if path has | |
509 | * differing segments types, our initial guesstimate above will | |
510 | * have been wrong. need 5 chars for ASN, a seperator each and | |
511 | * potentially two segment delimiters, plus a space between each | |
512 | * segment and trailing zero. | |
513 | */ | |
514 | #define SEGMENT_STR_LEN(X) (((X)->length * ASN_STR_LEN) + 2 + 1 + 1) | |
515 | if ( (len + SEGMENT_STR_LEN(seg)) > str_size) | |
516 | { | |
517 | str_size = len + SEGMENT_STR_LEN(seg); | |
518 | str_buf = XREALLOC (MTYPE_AS_STR, str_buf, str_size); | |
519 | } | |
520 | #undef ASN_STR_LEN | |
521 | #undef SEGMENT_STR_LEN | |
522 | ||
523 | if (seg->type != AS_SEQUENCE) | |
524 | len += snprintf (str_buf + len, str_size - len, | |
525 | "%c", | |
526 | aspath_delimiter_char (seg->type, AS_SEG_START)); | |
527 | ||
528 | /* write out the ASNs, with their seperators, bar the last one*/ | |
529 | for (i = 0; i < seg->length; i++) | |
530 | { | |
531 | len += snprintf (str_buf + len, str_size - len, "%u", seg->as[i]); | |
532 | ||
533 | if (i < (seg->length - 1)) | |
534 | len += snprintf (str_buf + len, str_size - len, "%c", seperator); | |
535 | } | |
536 | ||
537 | if (seg->type != AS_SEQUENCE) | |
538 | len += snprintf (str_buf + len, str_size - len, "%c", | |
539 | aspath_delimiter_char (seg->type, AS_SEG_END)); | |
540 | if (seg->next) | |
541 | len += snprintf (str_buf + len, str_size - len, " "); | |
542 | ||
543 | seg = seg->next; | |
718e3744 | 544 | } |
fe69a505 | 545 | |
546 | assert (len < str_size); | |
547 | ||
548 | str_buf[len] = '\0'; | |
718e3744 | 549 | |
550 | return str_buf; | |
551 | } | |
552 | ||
fe69a505 | 553 | static void |
554 | aspath_str_update (struct aspath *as) | |
555 | { | |
556 | if (as->str) | |
557 | XFREE (MTYPE_AS_STR, as->str); | |
558 | as->str = aspath_make_str_count (as); | |
559 | } | |
560 | ||
718e3744 | 561 | /* Intern allocated AS path. */ |
562 | struct aspath * | |
563 | aspath_intern (struct aspath *aspath) | |
564 | { | |
565 | struct aspath *find; | |
566 | ||
567 | /* Assert this AS path structure is not interned. */ | |
568 | assert (aspath->refcnt == 0); | |
569 | ||
570 | /* Check AS path hash. */ | |
571 | find = hash_get (ashash, aspath, hash_alloc_intern); | |
572 | ||
573 | if (find != aspath) | |
fe69a505 | 574 | aspath_free (aspath); |
718e3744 | 575 | |
576 | find->refcnt++; | |
577 | ||
578 | if (! find->str) | |
579 | find->str = aspath_make_str_count (find); | |
580 | ||
581 | return find; | |
582 | } | |
583 | ||
584 | /* Duplicate aspath structure. Created same aspath structure but | |
585 | reference count and AS path string is cleared. */ | |
586 | struct aspath * | |
587 | aspath_dup (struct aspath *aspath) | |
588 | { | |
589 | struct aspath *new; | |
590 | ||
fe69a505 | 591 | new = XCALLOC (MTYPE_AS_PATH, sizeof (struct aspath)); |
718e3744 | 592 | |
fe69a505 | 593 | if (aspath->segments) |
594 | new->segments = assegment_dup_all (aspath->segments); | |
718e3744 | 595 | else |
fe69a505 | 596 | new->segments = NULL; |
718e3744 | 597 | |
fe69a505 | 598 | new->str = aspath_make_str_count (aspath); |
718e3744 | 599 | |
600 | return new; | |
601 | } | |
602 | ||
94f2b392 | 603 | static void * |
fe69a505 | 604 | aspath_hash_alloc (void *arg) |
718e3744 | 605 | { |
606 | struct aspath *aspath; | |
607 | ||
608 | /* New aspath strucutre is needed. */ | |
fe69a505 | 609 | aspath = aspath_dup (arg); |
610 | ||
718e3744 | 611 | /* Malformed AS path value. */ |
612 | if (! aspath->str) | |
613 | { | |
614 | aspath_free (aspath); | |
615 | return NULL; | |
616 | } | |
617 | ||
618 | return aspath; | |
619 | } | |
620 | ||
fe69a505 | 621 | /* parse as-segment byte stream in struct assegment */ |
ad72740e | 622 | static struct assegment * |
fe69a505 | 623 | assegments_parse (struct stream *s, size_t length) |
624 | { | |
625 | struct assegment_header segh; | |
626 | struct assegment *seg, *prev = NULL, *head = NULL; | |
627 | size_t bytes = 0; | |
628 | ||
629 | /* empty aspath (ie iBGP or somesuch) */ | |
630 | if (length == 0) | |
631 | return NULL; | |
632 | ||
633 | /* basic checks */ | |
634 | if ( (STREAM_READABLE(s) < length) | |
635 | || (STREAM_READABLE(s) < AS_HEADER_SIZE) | |
636 | || (length % AS_VALUE_SIZE)) | |
637 | return NULL; | |
638 | ||
639 | while ( (STREAM_READABLE(s) > AS_HEADER_SIZE) | |
640 | && (bytes < length)) | |
641 | { | |
642 | int i; | |
643 | ||
644 | /* softly softly, get the header first on its own */ | |
645 | segh.type = stream_getc (s); | |
646 | segh.length = stream_getc (s); | |
647 | ||
648 | /* check it.. */ | |
649 | if ( ((bytes + ASSEGMENT_SIZE(segh.length)) > length) | |
650 | /* 1771bis 4.3b: seg length contains one or more */ | |
651 | || (segh.length == 0) | |
652 | /* Paranoia in case someone changes type of segment length */ | |
653 | || ((sizeof segh.length > 1) && segh.length > AS_SEGMENT_MAX)) | |
654 | { | |
655 | if (head) | |
656 | assegment_free_all (head); | |
657 | return NULL; | |
658 | } | |
659 | ||
660 | /* now its safe to trust lengths */ | |
661 | seg = assegment_new (segh.type, segh.length); | |
662 | ||
663 | if (head) | |
664 | prev->next = seg; | |
665 | else /* it's the first segment */ | |
666 | head = prev = seg; | |
667 | ||
668 | for (i = 0; i < segh.length; i++) | |
669 | seg->as[i] = stream_getw (s); | |
670 | ||
671 | bytes += ASSEGMENT_SIZE(segh.length); | |
672 | ||
673 | prev = seg; | |
674 | } | |
675 | ||
676 | return assegment_normalise (head); | |
677 | } | |
678 | ||
718e3744 | 679 | /* AS path parse function. pnt is a pointer to byte stream and length |
680 | is length of byte stream. If there is same AS path in the the AS | |
681 | path hash then return it else make new AS path structure. */ | |
682 | struct aspath * | |
fe69a505 | 683 | aspath_parse (struct stream *s, size_t length) |
718e3744 | 684 | { |
685 | struct aspath as; | |
686 | struct aspath *find; | |
687 | ||
688 | /* If length is odd it's malformed AS path. */ | |
fe69a505 | 689 | if (length % AS_VALUE_SIZE) |
718e3744 | 690 | return NULL; |
691 | ||
fe69a505 | 692 | as.segments = assegments_parse (s, length); |
693 | ||
718e3744 | 694 | /* If already same aspath exist then return it. */ |
695 | find = hash_get (ashash, &as, aspath_hash_alloc); | |
02335429 | 696 | |
697 | /* aspath_hash_alloc dupes segments too. that probably could be | |
698 | * optimised out. | |
699 | */ | |
700 | assegment_free_all (as.segments); | |
701 | ||
718e3744 | 702 | if (! find) |
703 | return NULL; | |
704 | find->refcnt++; | |
705 | ||
706 | return find; | |
707 | } | |
708 | ||
fe69a505 | 709 | static inline void |
710 | assegment_data_put (struct stream *s, as_t *as, int num) | |
711 | { | |
712 | int i; | |
713 | assert (num <= AS_SEGMENT_MAX); | |
714 | ||
715 | for (i = 0; i < num; i++) | |
716 | stream_putw (s, as[i]); | |
717 | } | |
718e3744 | 718 | |
fe69a505 | 719 | static inline size_t |
720 | assegment_header_put (struct stream *s, u_char type, int length) | |
718e3744 | 721 | { |
fe69a505 | 722 | size_t lenp; |
723 | assert (length <= AS_SEGMENT_MAX); | |
724 | stream_putc (s, type); | |
725 | lenp = stream_get_endp (s); | |
726 | stream_putc (s, length); | |
727 | return lenp; | |
728 | } | |
718e3744 | 729 | |
fe69a505 | 730 | /* write aspath data to stream */ |
731 | void | |
732 | aspath_put (struct stream *s, struct aspath *as) | |
733 | { | |
734 | struct assegment *seg = as->segments; | |
735 | ||
736 | if (!seg || seg->length == 0) | |
737 | return; | |
738 | ||
739 | if (seg) | |
718e3744 | 740 | { |
fe69a505 | 741 | while (seg && (ASSEGMENT_LEN (seg) <= STREAM_WRITEABLE(s))) |
742 | { | |
743 | int written = 0; | |
744 | size_t lenp; | |
745 | ||
746 | /* Overlength segments have to be split up */ | |
747 | while ( (seg->length - written) > AS_SEGMENT_MAX) | |
748 | { | |
749 | assegment_header_put (s, seg->type, AS_SEGMENT_MAX); | |
750 | assegment_data_put (s, seg->as, AS_SEGMENT_MAX); | |
751 | written += AS_SEGMENT_MAX; | |
752 | } | |
753 | ||
754 | /* write the final segment, probably is also the first */ | |
755 | lenp = assegment_header_put (s, seg->type, seg->length - written); | |
756 | assegment_data_put (s, (seg->as + written), seg->length - written); | |
757 | ||
758 | /* Sequence-type segments can be 'packed' together | |
759 | * Case of a segment which was overlength and split up | |
760 | * will be missed here, but that doesn't matter. | |
761 | */ | |
762 | if (seg->next && ASSEGMENTS_PACKABLE (seg, seg->next)) | |
763 | { | |
764 | /* NB: We should never normally get here given we | |
765 | * normalise aspath data when parse them. However, better | |
766 | * safe than sorry. We potentially could call | |
767 | * assegment_normalise here instead, but it's cheaper and | |
768 | * easier to do it on the fly here rather than go through | |
769 | * the segment list twice every time we write out | |
770 | * aspath's. | |
771 | */ | |
772 | ||
773 | /* Next segment's data can fit in this one */ | |
774 | assegment_data_put (s, seg->next->as, seg->next->length); | |
775 | ||
776 | /* update the length of the segment header */ | |
777 | stream_putc_at (s, lenp, | |
778 | seg->length - written + seg->next->length); | |
779 | seg = seg->next->next; /* skip to past next */ | |
780 | } | |
781 | else | |
782 | seg = seg->next; | |
783 | } | |
718e3744 | 784 | } |
fe69a505 | 785 | } |
786 | ||
787 | /* This is for SNMP BGP4PATHATTRASPATHSEGMENT | |
788 | * We have no way to manage the storage, so we use a static stream | |
789 | * wrapper around aspath_put. | |
790 | */ | |
791 | u_char * | |
792 | aspath_snmp_pathseg (struct aspath *as, size_t *varlen) | |
793 | { | |
794 | #define SNMP_PATHSEG_MAX 1024 | |
8fdc32ab | 795 | |
796 | if (!snmp_stream) | |
797 | snmp_stream = stream_new (SNMP_PATHSEG_MAX); | |
718e3744 | 798 | else |
8fdc32ab | 799 | stream_reset (snmp_stream); |
fe69a505 | 800 | |
801 | if (!as) | |
718e3744 | 802 | { |
fe69a505 | 803 | *varlen = 0; |
804 | return NULL; | |
718e3744 | 805 | } |
8fdc32ab | 806 | aspath_put (snmp_stream, as); |
fe69a505 | 807 | |
8fdc32ab | 808 | *varlen = stream_get_endp (snmp_stream); |
809 | return stream_pnt(snmp_stream); | |
718e3744 | 810 | } |
fe69a505 | 811 | |
812 | #define min(A,B) ((A) < (B) ? (A) : (B)) | |
718e3744 | 813 | |
94f2b392 | 814 | static struct assegment * |
718e3744 | 815 | aspath_aggregate_as_set_add (struct aspath *aspath, struct assegment *asset, |
816 | as_t as) | |
817 | { | |
818 | int i; | |
819 | ||
820 | /* If this is first AS set member, create new as-set segment. */ | |
821 | if (asset == NULL) | |
822 | { | |
fe69a505 | 823 | asset = assegment_new (AS_SET, 1); |
824 | if (! aspath->segments) | |
825 | aspath->segments = asset; | |
718e3744 | 826 | else |
fe69a505 | 827 | { |
828 | struct assegment *seg = aspath->segments; | |
829 | while (seg->next) | |
830 | seg = seg->next; | |
831 | seg->next = asset; | |
832 | } | |
718e3744 | 833 | asset->type = AS_SET; |
834 | asset->length = 1; | |
fe69a505 | 835 | asset->as[0] = as; |
718e3744 | 836 | } |
837 | else | |
838 | { | |
718e3744 | 839 | /* Check this AS value already exists or not. */ |
840 | for (i = 0; i < asset->length; i++) | |
fe69a505 | 841 | if (asset->as[i] == as) |
718e3744 | 842 | return asset; |
fe69a505 | 843 | |
718e3744 | 844 | asset->length++; |
fe69a505 | 845 | asset->as = XREALLOC (MTYPE_AS_SEG_DATA, asset->as, |
846 | asset->length * AS_VALUE_SIZE); | |
847 | asset->as[asset->length - 1] = as; | |
718e3744 | 848 | } |
fe69a505 | 849 | |
718e3744 | 850 | |
851 | return asset; | |
852 | } | |
853 | ||
854 | /* Modify as1 using as2 for aggregation. */ | |
855 | struct aspath * | |
856 | aspath_aggregate (struct aspath *as1, struct aspath *as2) | |
857 | { | |
858 | int i; | |
859 | int minlen; | |
860 | int match; | |
fe69a505 | 861 | int from; |
862 | struct assegment *seg1 = as1->segments; | |
863 | struct assegment *seg2 = as2->segments; | |
718e3744 | 864 | struct aspath *aspath; |
865 | struct assegment *asset; | |
866 | ||
867 | match = 0; | |
868 | minlen = 0; | |
869 | aspath = NULL; | |
870 | asset = NULL; | |
718e3744 | 871 | |
872 | /* First of all check common leading sequence. */ | |
fe69a505 | 873 | while (seg1 && seg2) |
718e3744 | 874 | { |
875 | /* Check segment type. */ | |
876 | if (seg1->type != seg2->type) | |
877 | break; | |
878 | ||
879 | /* Minimum segment length. */ | |
880 | minlen = min (seg1->length, seg2->length); | |
881 | ||
882 | for (match = 0; match < minlen; match++) | |
fe69a505 | 883 | if (seg1->as[match] != seg2->as[match]) |
718e3744 | 884 | break; |
885 | ||
886 | if (match) | |
887 | { | |
888 | if (! aspath) | |
fe69a505 | 889 | aspath = aspath_new (); |
890 | aspath->segments = assegment_new (seg1->type, 0); | |
891 | aspath->segments = assegment_append_asns (aspath->segments, | |
892 | seg1->as, match); | |
718e3744 | 893 | } |
894 | ||
895 | if (match != minlen || match != seg1->length | |
896 | || seg1->length != seg2->length) | |
897 | break; | |
fe69a505 | 898 | |
899 | seg1 = seg1->next; | |
900 | seg2 = seg2->next; | |
718e3744 | 901 | } |
902 | ||
903 | if (! aspath) | |
904 | aspath = aspath_new(); | |
905 | ||
906 | /* Make as-set using rest of all information. */ | |
fe69a505 | 907 | from = match; |
908 | while (seg1) | |
718e3744 | 909 | { |
fe69a505 | 910 | for (i = from; i < seg1->length; i++) |
911 | asset = aspath_aggregate_as_set_add (aspath, asset, seg1->as[i]); | |
912 | ||
913 | from = 0; | |
914 | seg1 = seg1->next; | |
718e3744 | 915 | } |
916 | ||
fe69a505 | 917 | from = match; |
918 | while (seg2) | |
718e3744 | 919 | { |
fe69a505 | 920 | for (i = from; i < seg2->length; i++) |
921 | asset = aspath_aggregate_as_set_add (aspath, asset, seg2->as[i]); | |
718e3744 | 922 | |
fe69a505 | 923 | from = 0; |
924 | seg2 = seg2->next; | |
718e3744 | 925 | } |
fe69a505 | 926 | |
927 | assegment_normalise (aspath->segments); | |
928 | aspath_str_update (aspath); | |
718e3744 | 929 | return aspath; |
930 | } | |
931 | ||
932 | /* When a BGP router receives an UPDATE with an MP_REACH_NLRI | |
933 | attribute, check the leftmost AS number in the AS_PATH attribute is | |
934 | or not the peer's AS number. */ | |
935 | int | |
936 | aspath_firstas_check (struct aspath *aspath, as_t asno) | |
937 | { | |
fe69a505 | 938 | if ( (aspath == NULL) || (aspath->segments == NULL) ) |
718e3744 | 939 | return 0; |
fe69a505 | 940 | |
941 | if (aspath->segments | |
942 | && (aspath->segments->type == AS_SEQUENCE) | |
943 | && (aspath->segments->as[0] == asno )) | |
718e3744 | 944 | return 1; |
945 | ||
946 | return 0; | |
947 | } | |
948 | ||
1f742f21 | 949 | /* AS path loop check. If aspath contains asno then return >= 1. */ |
718e3744 | 950 | int |
951 | aspath_loop_check (struct aspath *aspath, as_t asno) | |
952 | { | |
fe69a505 | 953 | struct assegment *seg; |
718e3744 | 954 | int count = 0; |
955 | ||
1f742f21 | 956 | if ( (aspath == NULL) || (aspath->segments == NULL) ) |
718e3744 | 957 | return 0; |
fe69a505 | 958 | |
959 | seg = aspath->segments; | |
960 | ||
961 | while (seg) | |
718e3744 | 962 | { |
963 | int i; | |
718e3744 | 964 | |
fe69a505 | 965 | for (i = 0; i < seg->length; i++) |
966 | if (seg->as[i] == asno) | |
718e3744 | 967 | count++; |
fe69a505 | 968 | |
969 | seg = seg->next; | |
718e3744 | 970 | } |
971 | return count; | |
972 | } | |
973 | ||
974 | /* When all of AS path is private AS return 1. */ | |
975 | int | |
976 | aspath_private_as_check (struct aspath *aspath) | |
977 | { | |
fe69a505 | 978 | struct assegment *seg; |
979 | ||
980 | if ( !(aspath && aspath->segments) ) | |
718e3744 | 981 | return 0; |
fe69a505 | 982 | |
983 | seg = aspath->segments; | |
718e3744 | 984 | |
fe69a505 | 985 | while (seg) |
718e3744 | 986 | { |
987 | int i; | |
718e3744 | 988 | |
fe69a505 | 989 | for (i = 0; i < seg->length; i++) |
718e3744 | 990 | { |
fe69a505 | 991 | if ( (seg->as[i] < BGP_PRIVATE_AS_MIN) |
992 | || (seg->as[i] > BGP_PRIVATE_AS_MAX) ) | |
718e3744 | 993 | return 0; |
994 | } | |
fe69a505 | 995 | seg = seg->next; |
718e3744 | 996 | } |
997 | return 1; | |
998 | } | |
999 | ||
1000 | /* Merge as1 to as2. as2 should be uninterned aspath. */ | |
94f2b392 | 1001 | static struct aspath * |
718e3744 | 1002 | aspath_merge (struct aspath *as1, struct aspath *as2) |
1003 | { | |
fe69a505 | 1004 | struct assegment *last, *new; |
718e3744 | 1005 | |
1006 | if (! as1 || ! as2) | |
1007 | return NULL; | |
1008 | ||
fe69a505 | 1009 | last = new = assegment_dup_all (as1->segments); |
1010 | ||
1011 | /* find the last valid segment */ | |
1012 | while (last && last->next) | |
1013 | last = last->next; | |
1014 | ||
1015 | last->next = as2->segments; | |
1016 | as2->segments = new; | |
1017 | aspath_str_update (as2); | |
718e3744 | 1018 | return as2; |
1019 | } | |
1020 | ||
1021 | /* Prepend as1 to as2. as2 should be uninterned aspath. */ | |
1022 | struct aspath * | |
1023 | aspath_prepend (struct aspath *as1, struct aspath *as2) | |
1024 | { | |
fe69a505 | 1025 | struct assegment *seg1; |
1026 | struct assegment *seg2; | |
718e3744 | 1027 | |
1028 | if (! as1 || ! as2) | |
1029 | return NULL; | |
fe69a505 | 1030 | |
1031 | seg1 = as1->segments; | |
1032 | seg2 = as2->segments; | |
1033 | ||
1034 | /* If as2 is empty, only need to dupe as1's chain onto as2 */ | |
718e3744 | 1035 | if (seg2 == NULL) |
1036 | { | |
fe69a505 | 1037 | as2->segments = assegment_dup_all (as1->segments); |
1038 | aspath_str_update (as2); | |
718e3744 | 1039 | return as2; |
1040 | } | |
fe69a505 | 1041 | |
1042 | /* If as1 is empty AS, no prepending to do. */ | |
718e3744 | 1043 | if (seg1 == NULL) |
1044 | return as2; | |
fe69a505 | 1045 | |
1046 | /* find the tail as1's segment chain. */ | |
1047 | while (seg1 && seg1->next) | |
1048 | seg1 = seg1->next; | |
718e3744 | 1049 | |
1050 | /* Compare last segment type of as1 and first segment type of as2. */ | |
1051 | if (seg1->type != seg2->type) | |
1052 | return aspath_merge (as1, as2); | |
1053 | ||
1054 | if (seg1->type == AS_SEQUENCE) | |
1055 | { | |
fe69a505 | 1056 | /* We have two chains of segments, as1->segments and seg2, |
1057 | * and we have to attach them together, merging the attaching | |
1058 | * segments together into one. | |
1059 | * | |
1060 | * 1. dupe as1->segments onto head of as2 | |
1061 | * 2. merge seg2's asns onto last segment of this new chain | |
1062 | * 3. attach chain after seg2 | |
1063 | */ | |
718e3744 | 1064 | |
fe69a505 | 1065 | /* dupe as1 onto as2's head */ |
1066 | seg1 = as2->segments = assegment_dup_all (as1->segments); | |
1067 | ||
1068 | /* refind the tail of as2, reusing seg1 */ | |
1069 | while (seg1 && seg1->next) | |
1070 | seg1 = seg1->next; | |
1071 | ||
1072 | /* merge the old head, seg2, into tail, seg1 */ | |
1073 | seg1 = assegment_append_asns (seg1, seg2->as, seg2->length); | |
1074 | ||
1075 | /* bypass the merged seg2, and attach any chain after it to | |
1076 | * chain descending from as2's head | |
1077 | */ | |
1078 | seg1->next = seg2->next; | |
1079 | ||
1080 | /* seg2 is now referenceless and useless*/ | |
1081 | assegment_free (seg2); | |
1082 | ||
1083 | /* we've now prepended as1's segment chain to as2, merging | |
1084 | * the inbetween AS_SEQUENCE of seg2 in the process | |
1085 | */ | |
1086 | aspath_str_update (as2); | |
718e3744 | 1087 | return as2; |
1088 | } | |
1089 | else | |
1090 | { | |
1091 | /* AS_SET merge code is needed at here. */ | |
1092 | return aspath_merge (as1, as2); | |
1093 | } | |
fe69a505 | 1094 | /* XXX: Ermmm, what if as1 has multiple segments?? */ |
1095 | ||
718e3744 | 1096 | /* Not reached */ |
1097 | } | |
1098 | ||
1099 | /* Add specified AS to the leftmost of aspath. */ | |
1100 | static struct aspath * | |
1101 | aspath_add_one_as (struct aspath *aspath, as_t asno, u_char type) | |
1102 | { | |
fe69a505 | 1103 | struct assegment *assegment = aspath->segments; |
718e3744 | 1104 | |
1105 | /* In case of empty aspath. */ | |
1106 | if (assegment == NULL || assegment->length == 0) | |
1107 | { | |
fe69a505 | 1108 | aspath->segments = assegment_new (type, 1); |
1109 | aspath->segments->as[0] = asno; | |
1110 | ||
718e3744 | 1111 | if (assegment) |
fe69a505 | 1112 | assegment_free (assegment); |
718e3744 | 1113 | |
1114 | return aspath; | |
1115 | } | |
1116 | ||
1117 | if (assegment->type == type) | |
fe69a505 | 1118 | aspath->segments = assegment_prepend_asns (aspath->segments, asno, 1); |
1119 | else | |
718e3744 | 1120 | { |
fe69a505 | 1121 | /* create new segment |
1122 | * push it onto head of aspath's segment chain | |
1123 | */ | |
718e3744 | 1124 | struct assegment *newsegment; |
fe69a505 | 1125 | |
1126 | newsegment = assegment_new (type, 1); | |
1127 | newsegment->as[0] = asno; | |
1128 | ||
1129 | newsegment->next = assegment; | |
1130 | aspath->segments = newsegment; | |
718e3744 | 1131 | } |
1132 | ||
1133 | return aspath; | |
1134 | } | |
1135 | ||
1136 | /* Add specified AS to the leftmost of aspath. */ | |
1137 | struct aspath * | |
1138 | aspath_add_seq (struct aspath *aspath, as_t asno) | |
1139 | { | |
1140 | return aspath_add_one_as (aspath, asno, AS_SEQUENCE); | |
1141 | } | |
1142 | ||
1143 | /* Compare leftmost AS value for MED check. If as1's leftmost AS and | |
1144 | as2's leftmost AS is same return 1. */ | |
1145 | int | |
1146 | aspath_cmp_left (struct aspath *aspath1, struct aspath *aspath2) | |
1147 | { | |
fe69a505 | 1148 | struct assegment *seg1 = NULL; |
1149 | struct assegment *seg2 = NULL; | |
718e3744 | 1150 | |
fe69a505 | 1151 | if (!(aspath1 && aspath2)) |
1152 | return 0; | |
718e3744 | 1153 | |
fe69a505 | 1154 | seg1 = aspath1->segments; |
1155 | seg2 = aspath2->segments; | |
718e3744 | 1156 | |
fe69a505 | 1157 | /* find first non-confed segments for each */ |
1158 | while (seg1 && ((seg1->type == AS_CONFED_SEQUENCE) | |
1159 | || (seg1->type == AS_CONFED_SET))) | |
1160 | seg1 = seg1->next; | |
718e3744 | 1161 | |
fe69a505 | 1162 | while (seg2 && ((seg2->type == AS_CONFED_SEQUENCE) |
1163 | || (seg2->type == AS_CONFED_SET))) | |
1164 | seg2 = seg2->next; | |
718e3744 | 1165 | |
fe69a505 | 1166 | /* Check as1's */ |
1167 | if (!(seg1 && seg2 | |
1168 | && (seg1->type == AS_SEQUENCE) && (seg2->type == AS_SEQUENCE))) | |
1169 | return 0; | |
1170 | ||
1171 | if (seg1->as[0] == seg2->as[0]) | |
718e3744 | 1172 | return 1; |
1173 | ||
1174 | return 0; | |
1175 | } | |
1176 | ||
1177 | /* Compare leftmost AS value for MED check. If as1's leftmost AS and | |
1178 | as2's leftmost AS is same return 1. (confederation as-path | |
1179 | only). */ | |
1180 | int | |
1181 | aspath_cmp_left_confed (struct aspath *aspath1, struct aspath *aspath2) | |
1182 | { | |
fe69a505 | 1183 | if (! (aspath1 && aspath2) ) |
718e3744 | 1184 | return 0; |
fe69a505 | 1185 | |
ad72740e | 1186 | if ( !(aspath1->segments && aspath2->segments) ) |
1187 | return 0; | |
1188 | ||
fe69a505 | 1189 | if ( (aspath1->segments->type != AS_CONFED_SEQUENCE) |
1190 | || (aspath2->segments->type != AS_CONFED_SEQUENCE) ) | |
718e3744 | 1191 | return 0; |
fe69a505 | 1192 | |
1193 | if (aspath1->segments->as[0] == aspath2->segments->as[0]) | |
718e3744 | 1194 | return 1; |
1195 | ||
1196 | return 0; | |
1197 | } | |
1198 | ||
fe69a505 | 1199 | /* Delete all leading AS_CONFED_SEQUENCE/SET segments from aspath. |
1200 | * See RFC3065, 6.1 c1 */ | |
718e3744 | 1201 | struct aspath * |
1202 | aspath_delete_confed_seq (struct aspath *aspath) | |
1203 | { | |
fe69a505 | 1204 | struct assegment *seg; |
718e3744 | 1205 | |
fe69a505 | 1206 | if (!(aspath && aspath->segments)) |
718e3744 | 1207 | return aspath; |
1208 | ||
fe69a505 | 1209 | seg = aspath->segments; |
1210 | ||
1211 | /* "if the first path segment of the AS_PATH is | |
1212 | * of type AS_CONFED_SEQUENCE," | |
1213 | */ | |
1214 | if (aspath->segments->type != AS_CONFED_SEQUENCE) | |
1215 | return aspath; | |
718e3744 | 1216 | |
fe69a505 | 1217 | /* "... that segment and any immediately following segments |
1218 | * of the type AS_CONFED_SET or AS_CONFED_SEQUENCE are removed | |
1219 | * from the AS_PATH attribute," | |
1220 | */ | |
1221 | while (seg && | |
1222 | (seg->type == AS_CONFED_SEQUENCE || seg->type == AS_CONFED_SET)) | |
718e3744 | 1223 | { |
fe69a505 | 1224 | aspath->segments = seg->next; |
1225 | assegment_free (seg); | |
1226 | seg = aspath->segments; | |
718e3744 | 1227 | } |
fe69a505 | 1228 | aspath_str_update (aspath); |
718e3744 | 1229 | return aspath; |
1230 | } | |
1231 | ||
1232 | /* Add new AS number to the leftmost part of the aspath as | |
1233 | AS_CONFED_SEQUENCE. */ | |
1234 | struct aspath* | |
1235 | aspath_add_confed_seq (struct aspath *aspath, as_t asno) | |
1236 | { | |
1237 | return aspath_add_one_as (aspath, asno, AS_CONFED_SEQUENCE); | |
1238 | } | |
1239 | ||
1240 | /* Add new as value to as path structure. */ | |
94f2b392 | 1241 | static void |
718e3744 | 1242 | aspath_as_add (struct aspath *as, as_t asno) |
1243 | { | |
fe69a505 | 1244 | struct assegment *seg = as->segments; |
718e3744 | 1245 | |
1246 | /* Last segment search procedure. */ | |
fe69a505 | 1247 | while (seg && seg->next) |
1248 | seg = seg->next; | |
1249 | ||
1250 | if (!seg) | |
1251 | return; | |
1252 | ||
1253 | assegment_append_asns (seg, &asno, 1); | |
718e3744 | 1254 | } |
1255 | ||
1256 | /* Add new as segment to the as path. */ | |
94f2b392 | 1257 | static void |
718e3744 | 1258 | aspath_segment_add (struct aspath *as, int type) |
1259 | { | |
fe69a505 | 1260 | struct assegment *seg = as->segments; |
1261 | struct assegment *new = assegment_new (type, 0); | |
718e3744 | 1262 | |
fe69a505 | 1263 | while (seg && seg->next) |
1264 | seg = seg->next; | |
1265 | ||
1266 | if (seg == NULL) | |
1267 | as->segments = new; | |
718e3744 | 1268 | else |
fe69a505 | 1269 | seg->next = new; |
718e3744 | 1270 | } |
1271 | ||
1272 | struct aspath * | |
94f2b392 | 1273 | aspath_empty (void) |
718e3744 | 1274 | { |
1275 | return aspath_parse (NULL, 0); | |
1276 | } | |
1277 | ||
1278 | struct aspath * | |
94f2b392 | 1279 | aspath_empty_get (void) |
718e3744 | 1280 | { |
1281 | struct aspath *aspath; | |
1282 | ||
1283 | aspath = aspath_new (); | |
1284 | aspath->str = aspath_make_str_count (aspath); | |
1285 | return aspath; | |
1286 | } | |
1287 | ||
1288 | unsigned long | |
fe69a505 | 1289 | aspath_count (void) |
718e3744 | 1290 | { |
1291 | return ashash->count; | |
1292 | } | |
1293 | \f | |
1294 | /* | |
1295 | Theoretically, one as path can have: | |
1296 | ||
1297 | One BGP packet size should be less than 4096. | |
1298 | One BGP attribute size should be less than 4096 - BGP header size. | |
1299 | One BGP aspath size should be less than 4096 - BGP header size - | |
1300 | BGP mandantry attribute size. | |
1301 | */ | |
1302 | ||
1303 | /* AS path string lexical token enum. */ | |
1304 | enum as_token | |
1305 | { | |
1306 | as_token_asval, | |
1307 | as_token_set_start, | |
1308 | as_token_set_end, | |
fe69a505 | 1309 | as_token_confed_seq_start, |
1310 | as_token_confed_seq_end, | |
1311 | as_token_confed_set_start, | |
1312 | as_token_confed_set_end, | |
718e3744 | 1313 | as_token_unknown |
1314 | }; | |
1315 | ||
1316 | /* Return next token and point for string parse. */ | |
94f2b392 | 1317 | static const char * |
fd79ac91 | 1318 | aspath_gettoken (const char *buf, enum as_token *token, u_short *asno) |
718e3744 | 1319 | { |
fd79ac91 | 1320 | const char *p = buf; |
718e3744 | 1321 | |
fe69a505 | 1322 | /* Skip seperators (space for sequences, ',' for sets). */ |
1323 | while (isspace ((int) *p) || *p == ',') | |
718e3744 | 1324 | p++; |
1325 | ||
1326 | /* Check the end of the string and type specify characters | |
1327 | (e.g. {}()). */ | |
1328 | switch (*p) | |
1329 | { | |
1330 | case '\0': | |
1331 | return NULL; | |
718e3744 | 1332 | case '{': |
1333 | *token = as_token_set_start; | |
1334 | p++; | |
1335 | return p; | |
718e3744 | 1336 | case '}': |
1337 | *token = as_token_set_end; | |
1338 | p++; | |
1339 | return p; | |
718e3744 | 1340 | case '(': |
fe69a505 | 1341 | *token = as_token_confed_seq_start; |
718e3744 | 1342 | p++; |
1343 | return p; | |
718e3744 | 1344 | case ')': |
fe69a505 | 1345 | *token = as_token_confed_seq_end; |
1346 | p++; | |
1347 | return p; | |
fe69a505 | 1348 | case '[': |
1349 | *token = as_token_confed_set_start; | |
1350 | p++; | |
1351 | return p; | |
fe69a505 | 1352 | case ']': |
1353 | *token = as_token_confed_set_end; | |
718e3744 | 1354 | p++; |
1355 | return p; | |
718e3744 | 1356 | } |
1357 | ||
1358 | /* Check actual AS value. */ | |
1359 | if (isdigit ((int) *p)) | |
1360 | { | |
1361 | u_short asval; | |
1362 | ||
1363 | *token = as_token_asval; | |
1364 | asval = (*p - '0'); | |
1365 | p++; | |
1366 | while (isdigit ((int) *p)) | |
1367 | { | |
1368 | asval *= 10; | |
1369 | asval += (*p - '0'); | |
1370 | p++; | |
1371 | } | |
1372 | *asno = asval; | |
1373 | return p; | |
1374 | } | |
1375 | ||
1376 | /* There is no match then return unknown token. */ | |
1377 | *token = as_token_unknown; | |
1378 | return p++; | |
1379 | } | |
1380 | ||
1381 | struct aspath * | |
fd79ac91 | 1382 | aspath_str2aspath (const char *str) |
718e3744 | 1383 | { |
3fff6ffc | 1384 | enum as_token token = as_token_unknown; |
718e3744 | 1385 | u_short as_type; |
1f742f21 | 1386 | u_short asno = 0; |
718e3744 | 1387 | struct aspath *aspath; |
1388 | int needtype; | |
1389 | ||
1390 | aspath = aspath_new (); | |
1391 | ||
1392 | /* We start default type as AS_SEQUENCE. */ | |
1393 | as_type = AS_SEQUENCE; | |
1394 | needtype = 1; | |
1395 | ||
1396 | while ((str = aspath_gettoken (str, &token, &asno)) != NULL) | |
1397 | { | |
1398 | switch (token) | |
1399 | { | |
1400 | case as_token_asval: | |
1401 | if (needtype) | |
1402 | { | |
1403 | aspath_segment_add (aspath, as_type); | |
1404 | needtype = 0; | |
1405 | } | |
1406 | aspath_as_add (aspath, asno); | |
1407 | break; | |
1408 | case as_token_set_start: | |
1409 | as_type = AS_SET; | |
1410 | aspath_segment_add (aspath, as_type); | |
1411 | needtype = 0; | |
1412 | break; | |
1413 | case as_token_set_end: | |
1414 | as_type = AS_SEQUENCE; | |
1415 | needtype = 1; | |
1416 | break; | |
fe69a505 | 1417 | case as_token_confed_seq_start: |
718e3744 | 1418 | as_type = AS_CONFED_SEQUENCE; |
1419 | aspath_segment_add (aspath, as_type); | |
1420 | needtype = 0; | |
1421 | break; | |
fe69a505 | 1422 | case as_token_confed_seq_end: |
1423 | as_type = AS_SEQUENCE; | |
1424 | needtype = 1; | |
1425 | break; | |
1426 | case as_token_confed_set_start: | |
1427 | as_type = AS_CONFED_SET; | |
1428 | aspath_segment_add (aspath, as_type); | |
1429 | needtype = 0; | |
1430 | break; | |
1431 | case as_token_confed_set_end: | |
718e3744 | 1432 | as_type = AS_SEQUENCE; |
1433 | needtype = 1; | |
1434 | break; | |
1435 | case as_token_unknown: | |
1436 | default: | |
fe69a505 | 1437 | aspath_free (aspath); |
718e3744 | 1438 | return NULL; |
718e3744 | 1439 | } |
1440 | } | |
1441 | ||
1442 | aspath->str = aspath_make_str_count (aspath); | |
1443 | ||
1444 | return aspath; | |
1445 | } | |
1446 | \f | |
1447 | /* Make hash value by raw aspath data. */ | |
1448 | unsigned int | |
1449 | aspath_key_make (struct aspath *aspath) | |
1450 | { | |
1451 | unsigned int key = 0; | |
fe69a505 | 1452 | unsigned int i; |
1453 | struct assegment *seg = aspath->segments; | |
1454 | struct assegment *prev = NULL; | |
718e3744 | 1455 | |
fe69a505 | 1456 | while (seg) |
718e3744 | 1457 | { |
fe69a505 | 1458 | /* segment types should be part of the hash |
1459 | * otherwise seq(1) and set(1) will hash to same value | |
1460 | */ | |
1461 | if (!(prev && seg->type == AS_SEQUENCE && seg->type == prev->type)) | |
1462 | key += seg->type; | |
1463 | ||
1464 | for (i = 0; i < seg->length; i++) | |
1465 | key += seg->as[i]; | |
1466 | ||
1467 | prev = seg; | |
1468 | seg = seg->next; | |
718e3744 | 1469 | } |
1470 | ||
1471 | return key; | |
1472 | } | |
1473 | ||
1474 | /* If two aspath have same value then return 1 else return 0 */ | |
94f2b392 | 1475 | static int |
fe69a505 | 1476 | aspath_cmp (void *arg1, void *arg2) |
718e3744 | 1477 | { |
fe69a505 | 1478 | struct assegment *seg1 = ((struct aspath *)arg1)->segments; |
1479 | struct assegment *seg2 = ((struct aspath *)arg2)->segments; | |
1480 | ||
1481 | while (seg1 || seg2) | |
1482 | { | |
1483 | int i; | |
1484 | if ((!seg1 && seg2) || (seg1 && !seg2)) | |
1485 | return 0; | |
1486 | if (seg1->type != seg2->type) | |
1487 | return 0; | |
1488 | if (seg1->length != seg2->length) | |
1489 | return 0; | |
1490 | for (i = 0; i < seg1->length; i++) | |
1491 | if (seg1->as[i] != seg2->as[i]) | |
1492 | return 0; | |
1493 | seg1 = seg1->next; | |
1494 | seg2 = seg2->next; | |
1495 | } | |
1496 | return 1; | |
718e3744 | 1497 | } |
1498 | ||
1499 | /* AS path hash initialize. */ | |
1500 | void | |
94f2b392 | 1501 | aspath_init (void) |
718e3744 | 1502 | { |
1503 | ashash = hash_create_size (32767, aspath_key_make, aspath_cmp); | |
1504 | } | |
8fdc32ab | 1505 | |
1506 | void | |
1507 | aspath_finish (void) | |
1508 | { | |
1509 | hash_free (ashash); | |
1510 | ||
1511 | if (snmp_stream) | |
1512 | stream_free (snmp_stream); | |
1513 | } | |
718e3744 | 1514 | \f |
1515 | /* return and as path value */ | |
1516 | const char * | |
1517 | aspath_print (struct aspath *as) | |
1518 | { | |
fe69a505 | 1519 | return (as ? as->str : NULL); |
718e3744 | 1520 | } |
1521 | ||
1522 | /* Printing functions */ | |
1523 | void | |
b2518c1e | 1524 | aspath_print_vty (struct vty *vty, const char *format, struct aspath *as) |
718e3744 | 1525 | { |
b2518c1e PJ |
1526 | assert (format); |
1527 | vty_out (vty, format, as->str); | |
718e3744 | 1528 | } |
1529 | ||
94f2b392 | 1530 | static void |
718e3744 | 1531 | aspath_show_all_iterator (struct hash_backet *backet, struct vty *vty) |
1532 | { | |
1533 | struct aspath *as; | |
1534 | ||
1535 | as = (struct aspath *) backet->data; | |
1536 | ||
efa9f830 | 1537 | vty_out (vty, "[%p:%u] (%ld) ", backet, backet->key, as->refcnt); |
718e3744 | 1538 | vty_out (vty, "%s%s", as->str, VTY_NEWLINE); |
1539 | } | |
1540 | ||
1541 | /* Print all aspath and hash information. This function is used from | |
1542 | `show ip bgp paths' command. */ | |
1543 | void | |
1544 | aspath_print_all_vty (struct vty *vty) | |
1545 | { | |
1546 | hash_iterate (ashash, | |
1547 | (void (*) (struct hash_backet *, void *)) | |
1548 | aspath_show_all_iterator, | |
1549 | vty); | |
1550 | } |