]>
Commit | Line | Data |
---|---|---|
c0668f36 MM |
1 | /* |
2 | * BIRD -- Path Operations | |
3 | * | |
4 | * (c) 2000 Martin Mares <mj@ucw.cz> | |
5 | * (c) 2000 Pavel Machek <pavel@ucw.cz> | |
6 | * | |
7 | * Can be freely distributed and used under the terms of the GNU GPL. | |
8 | */ | |
9 | ||
10 | #include "nest/bird.h" | |
11 | #include "nest/route.h" | |
c6add07f | 12 | #include "nest/attrs.h" |
c0668f36 MM |
13 | #include "lib/resource.h" |
14 | #include "lib/unaligned.h" | |
c6add07f | 15 | #include "lib/string.h" |
05198c12 | 16 | #include "filter/filter.h" |
c0668f36 | 17 | |
43c1cecc OZ |
18 | // static inline void put_as(byte *data, u32 as) { put_u32(data, as); } |
19 | // static inline u32 get_as(byte *data) { return get_u32(data); } | |
11cb6202 | 20 | |
43c1cecc OZ |
21 | #define put_as put_u32 |
22 | #define get_as get_u32 | |
0eb7f17d | 23 | #define BS 4 /* Default block size of ASN (autonomous system number) */ |
11cb6202 | 24 | |
d15b0b0a OZ |
25 | #define BAD(DSC, VAL) ({ err_dsc = DSC; err_val = VAL; goto bad; }) |
26 | ||
27 | int | |
5509e17d | 28 | as_path_valid(byte *data, uint len, int bs, int confed, char *err, uint elen) |
c0668f36 | 29 | { |
d15b0b0a OZ |
30 | byte *pos = data; |
31 | char *err_dsc = NULL; | |
32 | uint err_val = 0; | |
33 | ||
34 | while (len) | |
35 | { | |
36 | if (len < 2) | |
37 | BAD("segment framing error", 0); | |
38 | ||
39 | /* Process one AS path segment */ | |
40 | uint type = pos[0]; | |
41 | uint slen = 2 + bs * pos[1]; | |
42 | ||
43 | if (len < slen) | |
44 | BAD("segment framing error", len); | |
45 | ||
5509e17d OZ |
46 | switch (type) |
47 | { | |
48 | case AS_PATH_SET: | |
49 | case AS_PATH_SEQUENCE: | |
50 | break; | |
51 | ||
52 | case AS_PATH_CONFED_SEQUENCE: | |
53 | case AS_PATH_CONFED_SET: | |
54 | if (!confed) | |
55 | BAD("AS_CONFED* segment", type); | |
56 | break; | |
57 | ||
58 | default: | |
d15b0b0a | 59 | BAD("unknown segment", type); |
5509e17d | 60 | } |
d15b0b0a OZ |
61 | |
62 | if (pos[1] == 0) | |
63 | BAD("zero-length segment", type); | |
c0668f36 | 64 | |
d15b0b0a OZ |
65 | pos += slen; |
66 | len -= slen; | |
67 | } | |
68 | ||
69 | return 1; | |
70 | ||
71 | bad: | |
72 | if (err) | |
73 | if (bsnprintf(err, elen, "%s (%u) at %d", err_dsc, err_val, (int) (pos - data)) < 0) | |
74 | err[0] = 0; | |
75 | ||
76 | return 0; | |
77 | } | |
78 | ||
79 | int | |
80 | as_path_16to32(byte *dst, byte *src, uint len) | |
81 | { | |
82 | byte *dst0 = dst; | |
83 | byte *end = src + len; | |
84 | uint i, n; | |
85 | ||
86 | while (src < end) | |
87 | { | |
88 | n = src[1]; | |
89 | *dst++ = *src++; | |
90 | *dst++ = *src++; | |
91 | ||
92 | for (i = 0; i < n; i++) | |
c0668f36 | 93 | { |
d15b0b0a OZ |
94 | put_u32(dst, get_u16(src)); |
95 | src += 2; | |
96 | dst += 4; | |
c0668f36 | 97 | } |
d15b0b0a OZ |
98 | } |
99 | ||
100 | return dst - dst0; | |
101 | } | |
102 | ||
103 | int | |
104 | as_path_32to16(byte *dst, byte *src, uint len) | |
105 | { | |
106 | byte *dst0 = dst; | |
107 | byte *end = src + len; | |
108 | uint i, n; | |
109 | ||
110 | while (src < end) | |
111 | { | |
112 | n = src[1]; | |
113 | *dst++ = *src++; | |
114 | *dst++ = *src++; | |
115 | ||
116 | for (i = 0; i < n; i++) | |
c0668f36 | 117 | { |
d15b0b0a OZ |
118 | put_u16(dst, get_u32(src)); |
119 | src += 4; | |
120 | dst += 2; | |
c0668f36 | 121 | } |
d15b0b0a OZ |
122 | } |
123 | ||
124 | return dst - dst0; | |
c0668f36 | 125 | } |
c6add07f | 126 | |
11cb6202 | 127 | int |
d15b0b0a | 128 | as_path_contains_as4(const struct adata *path) |
11cb6202 | 129 | { |
d15b0b0a OZ |
130 | const byte *pos = path->data; |
131 | const byte *end = pos + path->length; | |
132 | uint i, n; | |
11cb6202 | 133 | |
d15b0b0a OZ |
134 | while (pos < end) |
135 | { | |
136 | n = pos[1]; | |
137 | pos += 2; | |
138 | ||
139 | for (i = 0; i < n; i++) | |
11cb6202 | 140 | { |
d15b0b0a OZ |
141 | if (get_as(pos) > 0xFFFF) |
142 | return 1; | |
11cb6202 | 143 | |
d15b0b0a | 144 | pos += BS; |
11cb6202 | 145 | } |
d15b0b0a | 146 | } |
11cb6202 | 147 | |
d15b0b0a | 148 | return 0; |
11cb6202 OZ |
149 | } |
150 | ||
151 | int | |
d15b0b0a OZ |
152 | as_path_contains_confed(const struct adata *path) |
153 | { | |
154 | const byte *pos = path->data; | |
155 | const byte *end = pos + path->length; | |
156 | ||
157 | while (pos < end) | |
158 | { | |
159 | uint type = pos[0]; | |
160 | uint slen = 2 + BS * pos[1]; | |
161 | ||
162 | if ((type == AS_PATH_CONFED_SEQUENCE) || | |
163 | (type == AS_PATH_CONFED_SET)) | |
164 | return 1; | |
165 | ||
166 | pos += slen; | |
167 | } | |
168 | ||
169 | return 0; | |
170 | } | |
171 | ||
5509e17d OZ |
172 | struct adata * |
173 | as_path_strip_confed(struct linpool *pool, const struct adata *path) | |
d15b0b0a | 174 | { |
5509e17d OZ |
175 | struct adata *res = lp_alloc_adata(pool, path->length); |
176 | const byte *src = path->data; | |
177 | const byte *end = src + path->length; | |
178 | byte *dst = res->data; | |
d15b0b0a OZ |
179 | |
180 | while (src < end) | |
181 | { | |
182 | uint type = src[0]; | |
183 | uint slen = 2 + BS * src[1]; | |
184 | ||
185 | /* Copy regular segments */ | |
186 | if ((type == AS_PATH_SET) || (type == AS_PATH_SEQUENCE)) | |
187 | { | |
188 | memcpy(dst, src, slen); | |
189 | dst += slen; | |
190 | } | |
191 | ||
192 | src += slen; | |
193 | } | |
d15b0b0a | 194 | |
5509e17d OZ |
195 | /* Fix the result length */ |
196 | res->length = dst - res->data; | |
197 | ||
198 | return res; | |
d15b0b0a OZ |
199 | } |
200 | ||
201 | struct adata * | |
5509e17d | 202 | as_path_prepend2(struct linpool *pool, const struct adata *op, int seq, u32 as) |
d15b0b0a OZ |
203 | { |
204 | struct adata *np; | |
205 | const byte *pos = op->data; | |
206 | uint len = op->length; | |
207 | ||
208 | if (len && (pos[0] == seq) && (pos[1] < 255)) | |
209 | { | |
210 | /* Starting with matching segment => just prepend the AS number */ | |
211 | np = lp_alloc_adata(pool, len + BS); | |
212 | np->data[0] = seq; | |
213 | np->data[1] = pos[1] + 1; | |
214 | put_as(np->data + 2, as); | |
215 | ||
216 | uint dlen = BS * pos[1]; | |
217 | memcpy(np->data + 2 + BS, pos + 2, dlen); | |
218 | ADVANCE(pos, len, 2 + dlen); | |
219 | } | |
220 | else | |
221 | { | |
222 | /* Create a new path segment */ | |
223 | np = lp_alloc_adata(pool, len + 2 + BS); | |
224 | np->data[0] = seq; | |
225 | np->data[1] = 1; | |
226 | put_as(np->data + 2, as); | |
227 | } | |
228 | ||
229 | if (len) | |
230 | { | |
231 | byte *dst = np->data + 2 + BS * np->data[1]; | |
232 | ||
5509e17d | 233 | memcpy(dst, pos, len); |
d15b0b0a OZ |
234 | } |
235 | ||
236 | return np; | |
237 | } | |
238 | ||
239 | ||
240 | struct adata * | |
241 | as_path_to_old(struct linpool *pool, const struct adata *path) | |
11cb6202 | 242 | { |
d15b0b0a OZ |
243 | struct adata *res = lp_alloc_adata(pool, path->length); |
244 | byte *pos = res->data; | |
245 | byte *end = pos + res->length; | |
246 | uint i, n; | |
11cb6202 | 247 | u32 as; |
11cb6202 | 248 | |
d15b0b0a OZ |
249 | /* Copy the whole path */ |
250 | memcpy(res->data, path->data, path->length); | |
11cb6202 | 251 | |
d15b0b0a OZ |
252 | /* Replace 32-bit AS numbers with AS_TRANS */ |
253 | while (pos < end) | |
254 | { | |
255 | n = pos[1]; | |
256 | pos += 2; | |
257 | ||
258 | for (i = 0; i < n; i++) | |
11cb6202 | 259 | { |
d15b0b0a OZ |
260 | as = get_as(pos); |
261 | if (as > 0xFFFF) | |
262 | put_as(pos, AS_TRANS); | |
11cb6202 | 263 | |
d15b0b0a OZ |
264 | pos += BS; |
265 | } | |
266 | } | |
11cb6202 | 267 | |
d15b0b0a OZ |
268 | return res; |
269 | } | |
11cb6202 | 270 | |
d15b0b0a OZ |
271 | /* |
272 | * Cut the path to the length @num, measured to the usual path metric. Note that | |
273 | * AS_CONFED_* segments have zero length and must be added if they are on edge. | |
274 | * In contrast to other as_path_* functions, @path is modified in place. | |
275 | */ | |
276 | void | |
277 | as_path_cut(struct adata *path, uint num) | |
278 | { | |
279 | byte *pos = path->data; | |
280 | byte *end = pos + path->length; | |
11cb6202 | 281 | |
d15b0b0a OZ |
282 | while (pos < end) |
283 | { | |
284 | uint t = pos[0]; | |
285 | uint l = pos[1]; | |
286 | uint n = 0; | |
287 | ||
288 | switch (t) | |
289 | { | |
290 | case AS_PATH_SET: n = 1; break; | |
291 | case AS_PATH_SEQUENCE: n = l; break; | |
292 | case AS_PATH_CONFED_SEQUENCE: n = 0; break; | |
293 | case AS_PATH_CONFED_SET: n = 0; break; | |
294 | default: bug("as_path_cut: Invalid path segment"); | |
11cb6202 OZ |
295 | } |
296 | ||
d15b0b0a OZ |
297 | /* Cannot add whole segment, so try partial one and finish */ |
298 | if (num < n) | |
299 | { | |
300 | if (num) | |
301 | { | |
302 | pos[1] = num; | |
303 | pos += 2 + BS * num; | |
304 | } | |
305 | ||
306 | break; | |
307 | } | |
308 | ||
309 | num -= n; | |
310 | pos += 2 + BS * l; | |
311 | } | |
312 | ||
313 | path->length = pos - path->data; | |
314 | } | |
315 | ||
316 | /* | |
317 | * Merge (concatenate) paths @p1 and @p2 and return the result. | |
318 | * In contrast to other as_path_* functions, @p1 and @p2 may be reused. | |
319 | */ | |
320 | struct adata * | |
321 | as_path_merge(struct linpool *pool, struct adata *p1, struct adata *p2) | |
322 | { | |
323 | if (p1->length == 0) | |
324 | return p2; | |
325 | ||
326 | if (p2->length == 0) | |
327 | return p1; | |
328 | ||
329 | struct adata *res = lp_alloc_adata(pool, p1->length + p2->length); | |
330 | memcpy(res->data, p1->data, p1->length); | |
331 | memcpy(res->data + p1->length, p2->data, p2->length); | |
332 | ||
333 | return res; | |
11cb6202 OZ |
334 | } |
335 | ||
c6add07f | 336 | void |
5509e17d | 337 | as_path_format(const struct adata *path, byte *bb, uint size) |
c6add07f | 338 | { |
5509e17d OZ |
339 | buffer buf = { .start = bb, .pos = bb, .end = bb + size }, *b = &buf; |
340 | const byte *pos = path->data; | |
341 | const byte *end = pos + path->length; | |
342 | const char *ops, *cls; | |
343 | ||
344 | b->pos[0] = 0; | |
345 | ||
346 | while (pos < end) | |
347 | { | |
348 | uint type = pos[0]; | |
349 | uint len = pos[1]; | |
350 | pos += 2; | |
c6add07f | 351 | |
5509e17d | 352 | switch (type) |
c6add07f | 353 | { |
5509e17d OZ |
354 | case AS_PATH_SET: ops = "{"; cls = "}"; break; |
355 | case AS_PATH_SEQUENCE: ops = NULL; cls = NULL; break; | |
356 | case AS_PATH_CONFED_SEQUENCE: ops = "("; cls = ")"; break; | |
357 | case AS_PATH_CONFED_SET: ops = "({"; cls = "})"; break; | |
358 | default: bug("Invalid path segment"); | |
c6add07f | 359 | } |
5509e17d OZ |
360 | |
361 | if (ops) | |
362 | buffer_puts(b, ops); | |
363 | ||
364 | while (len--) | |
365 | { | |
366 | buffer_print(b, len ? "%u " : "%u", get_as(pos)); | |
367 | pos += BS; | |
368 | } | |
369 | ||
370 | if (cls) | |
371 | buffer_puts(b, cls); | |
372 | ||
373 | if (pos < end) | |
374 | buffer_puts(b, " "); | |
375 | } | |
376 | ||
377 | /* Handle overflow */ | |
378 | if (b->pos == b->end) | |
379 | strcpy(b->end - 12, "..."); | |
c6add07f | 380 | } |
684c6f5a PM |
381 | |
382 | int | |
d15b0b0a | 383 | as_path_getlen(const struct adata *path) |
684c6f5a | 384 | { |
d15b0b0a OZ |
385 | const byte *pos = path->data; |
386 | const byte *end = pos + path->length; | |
387 | uint res = 0; | |
949bd34e | 388 | |
d15b0b0a OZ |
389 | while (pos < end) |
390 | { | |
391 | uint t = pos[0]; | |
392 | uint l = pos[1]; | |
393 | uint n = 0; | |
684c6f5a | 394 | |
d15b0b0a | 395 | switch (t) |
4b03f64b | 396 | { |
d15b0b0a OZ |
397 | case AS_PATH_SET: n = 1; break; |
398 | case AS_PATH_SEQUENCE: n = l; break; | |
399 | case AS_PATH_CONFED_SEQUENCE: n = 0; break; | |
400 | case AS_PATH_CONFED_SET: n = 0; break; | |
401 | default: bug("as_path_getlen: Invalid path segment"); | |
684c6f5a | 402 | } |
d15b0b0a OZ |
403 | |
404 | res += n; | |
405 | pos += 2 + BS * l; | |
406 | } | |
407 | ||
684c6f5a PM |
408 | return res; |
409 | } | |
2a40efa5 | 410 | |
f49528a3 | 411 | int |
d15b0b0a | 412 | as_path_get_last(const struct adata *path, u32 *orig_as) |
f49528a3 | 413 | { |
5509e17d OZ |
414 | const byte *pos = path->data; |
415 | const byte *end = pos + path->length; | |
11cb6202 | 416 | int found = 0; |
5509e17d | 417 | u32 val = 0; |
f49528a3 | 418 | |
5509e17d OZ |
419 | while (pos < end) |
420 | { | |
421 | uint type = pos[0]; | |
422 | uint len = pos[1]; | |
423 | pos += 2; | |
424 | ||
425 | if (!len) | |
426 | continue; | |
427 | ||
428 | switch (type) | |
f49528a3 | 429 | { |
5509e17d OZ |
430 | case AS_PATH_SET: |
431 | case AS_PATH_CONFED_SET: | |
432 | found = 0; | |
433 | break; | |
434 | ||
435 | case AS_PATH_SEQUENCE: | |
436 | case AS_PATH_CONFED_SEQUENCE: | |
437 | val = get_as(pos + BS * (len - 1)); | |
438 | found = 1; | |
439 | break; | |
440 | ||
441 | default: | |
442 | bug("Invalid path segment"); | |
f49528a3 | 443 | } |
11cb6202 | 444 | |
5509e17d OZ |
445 | pos += BS * len; |
446 | } | |
447 | ||
52b9b2a1 | 448 | if (found) |
5509e17d | 449 | *orig_as = val; |
11cb6202 | 450 | return found; |
f49528a3 MM |
451 | } |
452 | ||
9c9cc35c | 453 | u32 |
d15b0b0a | 454 | as_path_get_last_nonaggregated(const struct adata *path) |
9c9cc35c | 455 | { |
5509e17d OZ |
456 | const byte *pos = path->data; |
457 | const byte *end = pos + path->length; | |
458 | u32 val = 0; | |
9c9cc35c | 459 | |
5509e17d OZ |
460 | while (pos < end) |
461 | { | |
462 | uint type = pos[0]; | |
463 | uint len = pos[1]; | |
464 | pos += 2; | |
465 | ||
466 | if (!len) | |
467 | continue; | |
468 | ||
469 | switch (type) | |
9c9cc35c | 470 | { |
5509e17d OZ |
471 | case AS_PATH_SET: |
472 | case AS_PATH_CONFED_SET: | |
473 | return val; | |
9c9cc35c | 474 | |
5509e17d OZ |
475 | case AS_PATH_SEQUENCE: |
476 | case AS_PATH_CONFED_SEQUENCE: | |
477 | val = get_as(pos + BS * (len - 1)); | |
478 | break; | |
9c9cc35c | 479 | |
5509e17d OZ |
480 | default: |
481 | bug("Invalid path segment"); | |
9c9cc35c OZ |
482 | } |
483 | ||
5509e17d OZ |
484 | pos += BS * len; |
485 | } | |
486 | ||
487 | return val; | |
9c9cc35c OZ |
488 | } |
489 | ||
b6bf284a | 490 | int |
d15b0b0a | 491 | as_path_get_first(const struct adata *path, u32 *last_as) |
b6bf284a | 492 | { |
d15b0b0a | 493 | const u8 *p = path->data; |
b6bf284a OZ |
494 | |
495 | if ((path->length == 0) || (p[0] != AS_PATH_SEQUENCE) || (p[1] == 0)) | |
496 | return 0; | |
5509e17d OZ |
497 | |
498 | *last_as = get_as(p+2); | |
499 | return 1; | |
500 | } | |
501 | ||
502 | int | |
503 | as_path_get_first_regular(const struct adata *path, u32 *last_as) | |
504 | { | |
505 | const byte *pos = path->data; | |
506 | const byte *end = pos + path->length; | |
507 | ||
508 | while (pos < end) | |
509 | { | |
510 | uint type = pos[0]; | |
511 | uint len = pos[1]; | |
512 | pos += 2; | |
513 | ||
514 | switch (type) | |
b6bf284a | 515 | { |
5509e17d OZ |
516 | case AS_PATH_SET: |
517 | return 0; | |
518 | ||
519 | case AS_PATH_SEQUENCE: | |
520 | if (len == 0) | |
521 | return 0; | |
522 | ||
523 | *last_as = get_as(pos); | |
b6bf284a | 524 | return 1; |
5509e17d OZ |
525 | |
526 | case AS_PATH_CONFED_SEQUENCE: | |
527 | case AS_PATH_CONFED_SET: | |
528 | break; | |
529 | ||
530 | default: | |
531 | bug("Invalid path segment"); | |
b6bf284a | 532 | } |
5509e17d OZ |
533 | |
534 | pos += BS * len; | |
535 | } | |
536 | ||
537 | return 0; | |
b6bf284a OZ |
538 | } |
539 | ||
11cb6202 | 540 | int |
d15b0b0a | 541 | as_path_contains(const struct adata *path, u32 as, int min) |
11cb6202 | 542 | { |
d15b0b0a OZ |
543 | const u8 *p = path->data; |
544 | const u8 *q = p+path->length; | |
a15dab76 | 545 | int num = 0; |
11cb6202 OZ |
546 | int i, n; |
547 | ||
548 | while (p<q) | |
549 | { | |
550 | n = p[1]; | |
551 | p += 2; | |
552 | for(i=0; i<n; i++) | |
553 | { | |
554 | if (get_as(p) == as) | |
a15dab76 OZ |
555 | if (++num == min) |
556 | return 1; | |
43c1cecc | 557 | p += BS; |
11cb6202 OZ |
558 | } |
559 | } | |
560 | return 0; | |
561 | } | |
562 | ||
cc31b75a | 563 | int |
d15b0b0a | 564 | as_path_match_set(const struct adata *path, struct f_tree *set) |
cc31b75a | 565 | { |
d15b0b0a OZ |
566 | const u8 *p = path->data; |
567 | const u8 *q = p+path->length; | |
cc31b75a OZ |
568 | int i, n; |
569 | ||
570 | while (p<q) | |
571 | { | |
572 | n = p[1]; | |
573 | p += 2; | |
574 | for (i=0; i<n; i++) | |
575 | { | |
576 | struct f_val v = {T_INT, .val.i = get_as(p)}; | |
577 | if (find_tree(set, v)) | |
578 | return 1; | |
579 | p += BS; | |
580 | } | |
581 | } | |
582 | ||
583 | return 0; | |
584 | } | |
585 | ||
bff9ce51 OZ |
586 | struct adata * |
587 | as_path_filter(struct linpool *pool, struct adata *path, struct f_tree *set, u32 key, int pos) | |
588 | { | |
589 | if (!path) | |
590 | return NULL; | |
591 | ||
592 | int len = path->length; | |
d15b0b0a OZ |
593 | const u8 *p = path->data; |
594 | const u8 *q = path->data + len; | |
bff9ce51 OZ |
595 | u8 *d, *d2; |
596 | int i, bt, sn, dn; | |
597 | u8 buf[len]; | |
598 | ||
599 | d = buf; | |
600 | while (p<q) | |
601 | { | |
602 | /* Read block header (type and length) */ | |
603 | bt = p[0]; | |
604 | sn = p[1]; | |
605 | dn = 0; | |
606 | p += 2; | |
607 | d2 = d + 2; | |
608 | ||
609 | for (i = 0; i < sn; i++) | |
610 | { | |
611 | u32 as = get_as(p); | |
612 | int match; | |
613 | ||
614 | if (set) | |
615 | match = !!find_tree(set, (struct f_val){T_INT, .val.i = as}); | |
616 | else | |
617 | match = (as == key); | |
618 | ||
619 | if (match == pos) | |
620 | { | |
621 | put_as(d2, as); | |
622 | d2 += BS; | |
623 | dn++; | |
624 | } | |
625 | ||
626 | p += BS; | |
627 | } | |
628 | ||
629 | if (dn > 0) | |
630 | { | |
631 | /* Nonempty block, set block header and advance */ | |
632 | d[0] = bt; | |
633 | d[1] = dn; | |
634 | d = d2; | |
635 | } | |
636 | } | |
637 | ||
3e236955 | 638 | uint nl = d - buf; |
bff9ce51 OZ |
639 | if (nl == path->length) |
640 | return path; | |
641 | ||
642 | struct adata *res = lp_alloc(pool, sizeof(struct adata) + nl); | |
643 | res->length = nl; | |
644 | memcpy(res->data, buf, nl); | |
645 | ||
646 | return res; | |
647 | } | |
648 | ||
11cb6202 | 649 | |
c8a6b9a3 OZ |
650 | struct pm_pos |
651 | { | |
652 | u8 set; | |
653 | u8 mark; | |
654 | union | |
655 | { | |
d15b0b0a | 656 | const char *sp; |
c8a6b9a3 OZ |
657 | u32 asn; |
658 | } val; | |
659 | }; | |
660 | ||
661 | static int | |
5509e17d | 662 | parse_path(const struct adata *path, struct pm_pos *pp) |
2a40efa5 | 663 | { |
5509e17d OZ |
664 | const byte *pos = path->data; |
665 | const byte *end = pos + path->length; | |
666 | struct pm_pos *op = pp; | |
667 | uint i; | |
2a40efa5 | 668 | |
5509e17d OZ |
669 | while (pos < end) |
670 | { | |
671 | uint type = pos[0]; | |
672 | uint len = pos[1]; | |
673 | pos += 2; | |
25cb9f1d | 674 | |
5509e17d OZ |
675 | switch (type) |
676 | { | |
677 | case AS_PATH_SET: | |
678 | case AS_PATH_CONFED_SET: | |
679 | pp->set = 1; | |
680 | pp->mark = 0; | |
681 | pp->val.sp = pos - 1; | |
682 | pp++; | |
683 | ||
684 | pos += BS * len; | |
685 | break; | |
686 | ||
687 | case AS_PATH_SEQUENCE: | |
688 | case AS_PATH_CONFED_SEQUENCE: | |
689 | for (i = 0; i < len; i++) | |
2a40efa5 | 690 | { |
5509e17d OZ |
691 | pp->set = 0; |
692 | pp->mark = 0; | |
693 | pp->val.asn = get_as(pos); | |
694 | pp++; | |
695 | ||
696 | pos += BS; | |
2a40efa5 | 697 | } |
5509e17d | 698 | break; |
d15b0b0a | 699 | |
5509e17d OZ |
700 | default: |
701 | bug("Invalid path segment"); | |
702 | } | |
703 | } | |
704 | ||
705 | return pp - op; | |
c8a6b9a3 OZ |
706 | } |
707 | ||
c8a6b9a3 | 708 | static int |
a0fe1944 | 709 | pm_match(struct pm_pos *pos, u32 asn, u32 asn2) |
c8a6b9a3 | 710 | { |
a0fe1944 | 711 | u32 gas; |
c8a6b9a3 | 712 | if (! pos->set) |
a0fe1944 | 713 | return ((pos->val.asn >= asn) && (pos->val.asn <= asn2)); |
c8a6b9a3 | 714 | |
d15b0b0a | 715 | const u8 *p = pos->val.sp; |
c8a6b9a3 OZ |
716 | int len = *p++; |
717 | int i; | |
718 | ||
719 | for (i = 0; i < len; i++) | |
a0fe1944 OF |
720 | { |
721 | gas = get_as(p + i * BS); | |
722 | ||
723 | if ((gas >= asn) && (gas <= asn2)) | |
c8a6b9a3 | 724 | return 1; |
a0fe1944 | 725 | } |
c8a6b9a3 OZ |
726 | |
727 | return 0; | |
728 | } | |
729 | ||
730 | static void | |
731 | pm_mark(struct pm_pos *pos, int i, int plen, int *nl, int *nh) | |
732 | { | |
733 | int j; | |
734 | ||
735 | if (pos[i].set) | |
736 | pos[i].mark = 1; | |
d15b0b0a | 737 | |
c8a6b9a3 OZ |
738 | for (j = i + 1; (j < plen) && pos[j].set && (! pos[j].mark); j++) |
739 | pos[j].mark = 1; | |
740 | pos[j].mark = 1; | |
741 | ||
742 | /* We are going downwards, therefore every mark is | |
743 | new low and just the first mark is new high */ | |
744 | ||
745 | *nl = i + (pos[i].set ? 0 : 1); | |
746 | ||
747 | if (*nh < 0) | |
748 | *nh = j; | |
749 | } | |
750 | ||
751 | /* AS path matching is nontrivial. Because AS path can | |
5509e17d | 752 | * contain sets, it is not a plain wildcard matching. A set |
c8a6b9a3 OZ |
753 | * in an AS path is interpreted as it might represent any |
754 | * sequence of AS numbers from that set (possibly with | |
755 | * repetitions). So it is also a kind of a pattern, | |
756 | * more complicated than a path mask. | |
757 | * | |
758 | * The algorithm for AS path matching is a variant | |
759 | * of nondeterministic finite state machine, where | |
760 | * positions in AS path are states, and items in | |
761 | * path mask are input for that finite state machine. | |
762 | * During execution of the algorithm we maintain a set | |
763 | * of marked states - a state is marked if it can be | |
764 | * reached by any walk through NFSM with regard to | |
765 | * currently processed part of input. When we process | |
766 | * next part of mask, we advance each marked state. | |
767 | * We start with marked first position, when we | |
768 | * run out of marked positions, we reject. When | |
a0fe1944 | 769 | * we process the whole mask, we accept if final position |
c8a6b9a3 OZ |
770 | * (auxiliary position after last real position in AS path) |
771 | * is marked. | |
772 | */ | |
c8a6b9a3 | 773 | int |
d15b0b0a | 774 | as_path_match(const struct adata *path, struct f_path_mask *mask) |
c8a6b9a3 OZ |
775 | { |
776 | struct pm_pos pos[2048 + 1]; | |
777 | int plen = parse_path(path, pos); | |
778 | int l, h, i, nh, nl; | |
e81b440f | 779 | u32 val = 0; |
a0fe1944 | 780 | u32 val2 = 0; |
c8a6b9a3 OZ |
781 | |
782 | /* l and h are bound of interval of positions where | |
783 | are marked states */ | |
784 | ||
785 | pos[plen].set = 0; | |
786 | pos[plen].mark = 0; | |
787 | ||
788 | l = h = 0; | |
789 | pos[0].mark = 1; | |
5509e17d | 790 | |
c8a6b9a3 OZ |
791 | while (mask) |
792 | { | |
793 | /* We remove this mark to not step after pos[plen] */ | |
794 | pos[plen].mark = 0; | |
795 | ||
796 | switch (mask->kind) | |
797 | { | |
798 | case PM_ASTERISK: | |
799 | for (i = l; i <= plen; i++) | |
800 | pos[i].mark = 1; | |
801 | h = plen; | |
802 | break; | |
803 | ||
a0fe1944 OF |
804 | case PM_ASN: /* Define single ASN as ASN..ASN - very narrow interval */ |
805 | val2 = val = mask->val; | |
92a72a4c OZ |
806 | goto step; |
807 | case PM_ASN_EXPR: | |
d4cebc6b | 808 | bug("Expressions should be evaluated on AS path mask construction."); |
a0fe1944 OF |
809 | case PM_ASN_RANGE: |
810 | val = mask->val; | |
811 | val2 = mask->val2; | |
a82f692e | 812 | goto step; |
92a72a4c OZ |
813 | case PM_QUESTION: |
814 | step: | |
e81b440f | 815 | nh = nl = -1; |
c8a6b9a3 OZ |
816 | for (i = h; i >= l; i--) |
817 | if (pos[i].mark) | |
818 | { | |
819 | pos[i].mark = 0; | |
a0fe1944 | 820 | if ((mask->kind == PM_QUESTION) || pm_match(pos + i, val, val2)) |
c8a6b9a3 OZ |
821 | pm_mark(pos, i, plen, &nl, &nh); |
822 | } | |
823 | ||
824 | if (nh < 0) | |
2a40efa5 | 825 | return 0; |
c8a6b9a3 OZ |
826 | |
827 | h = nh; | |
828 | l = nl; | |
829 | break; | |
2a40efa5 | 830 | } |
2a40efa5 | 831 | |
c8a6b9a3 | 832 | mask = mask->next; |
2a40efa5 | 833 | } |
98347659 | 834 | |
c8a6b9a3 OZ |
835 | return pos[plen].mark; |
836 | } |