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