]>
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 | |
23 | #define BS 4 | |
11cb6202 | 24 | |
c0668f36 | 25 | struct adata * |
11cb6202 | 26 | as_path_prepend(struct linpool *pool, struct adata *olda, u32 as) |
c0668f36 MM |
27 | { |
28 | struct adata *newa; | |
29 | ||
11cb6202 OZ |
30 | if (olda->length && olda->data[0] == AS_PATH_SEQUENCE && olda->data[1] < 255) |
31 | /* Starting with sequence => just prepend the AS number */ | |
c0668f36 | 32 | { |
43c1cecc | 33 | int nl = olda->length + BS; |
11cb6202 OZ |
34 | newa = lp_alloc(pool, sizeof(struct adata) + nl); |
35 | newa->length = nl; | |
36 | newa->data[0] = AS_PATH_SEQUENCE; | |
c0668f36 | 37 | newa->data[1] = olda->data[1] + 1; |
43c1cecc | 38 | memcpy(newa->data + BS + 2, olda->data + 2, olda->length - 2); |
c0668f36 | 39 | } |
11cb6202 | 40 | else /* Create new path segment */ |
c0668f36 | 41 | { |
43c1cecc | 42 | int nl = olda->length + BS + 2; |
11cb6202 OZ |
43 | newa = lp_alloc(pool, sizeof(struct adata) + nl); |
44 | newa->length = nl; | |
45 | newa->data[0] = AS_PATH_SEQUENCE; | |
c0668f36 | 46 | newa->data[1] = 1; |
43c1cecc | 47 | memcpy(newa->data + BS + 2, olda->data, olda->length); |
c0668f36 | 48 | } |
11cb6202 | 49 | put_as(newa->data + 2, as); |
c0668f36 MM |
50 | return newa; |
51 | } | |
c6add07f | 52 | |
11cb6202 OZ |
53 | int |
54 | as_path_convert_to_old(struct adata *path, byte *dst, int *new_used) | |
55 | { | |
56 | byte *src = path->data; | |
57 | byte *src_end = src + path->length; | |
58 | byte *dst_start = dst; | |
59 | u32 as; | |
60 | int i, n; | |
61 | *new_used = 0; | |
62 | ||
63 | while (src < src_end) | |
64 | { | |
65 | n = src[1]; | |
66 | *dst++ = *src++; | |
67 | *dst++ = *src++; | |
68 | ||
69 | for(i=0; i<n; i++) | |
70 | { | |
71 | as = get_u32(src); | |
72 | if (as > 0xFFFF) | |
73 | { | |
74 | as = AS_TRANS; | |
75 | *new_used = 1; | |
76 | } | |
77 | put_u16(dst, as); | |
78 | src += 4; | |
79 | dst += 2; | |
80 | } | |
81 | } | |
82 | ||
83 | return dst - dst_start; | |
84 | } | |
85 | ||
86 | int | |
87 | as_path_convert_to_new(struct adata *path, byte *dst, int req_as) | |
88 | { | |
89 | byte *src = path->data; | |
90 | byte *src_end = src + path->length; | |
91 | byte *dst_start = dst; | |
92 | u32 as; | |
93 | int i, t, n; | |
94 | ||
95 | ||
96 | while ((src < src_end) && (req_as > 0)) | |
97 | { | |
98 | t = *src++; | |
99 | n = *src++; | |
100 | ||
101 | if (t == AS_PATH_SEQUENCE) | |
102 | { | |
103 | if (n > req_as) | |
104 | n = req_as; | |
105 | ||
106 | req_as -= n; | |
107 | } | |
108 | else // t == AS_PATH_SET | |
109 | req_as--; | |
110 | ||
111 | *dst++ = t; | |
112 | *dst++ = n; | |
113 | ||
114 | for(i=0; i<n; i++) | |
115 | { | |
116 | as = get_u16(src); | |
117 | put_u32(dst, as); | |
118 | src += 2; | |
119 | dst += 4; | |
120 | } | |
121 | } | |
122 | ||
123 | return dst - dst_start; | |
124 | } | |
125 | ||
c6add07f | 126 | void |
ae80a2de | 127 | as_path_format(struct adata *path, byte *buf, uint size) |
c6add07f MM |
128 | { |
129 | byte *p = path->data; | |
987de545 | 130 | byte *e = p + path->length; |
11cb6202 | 131 | byte *end = buf + size - 16; |
c6add07f | 132 | int sp = 1; |
93a786cb | 133 | int l, isset; |
c6add07f MM |
134 | |
135 | while (p < e) | |
136 | { | |
137 | if (buf > end) | |
138 | { | |
139 | strcpy(buf, " ..."); | |
140 | return; | |
141 | } | |
142 | isset = (*p++ == AS_PATH_SET); | |
143 | l = *p++; | |
144 | if (isset) | |
145 | { | |
146 | if (!sp) | |
147 | *buf++ = ' '; | |
148 | *buf++ = '{'; | |
149 | sp = 0; | |
150 | } | |
151 | while (l-- && buf <= end) | |
152 | { | |
153 | if (!sp) | |
154 | *buf++ = ' '; | |
11cb6202 | 155 | buf += bsprintf(buf, "%u", get_as(p)); |
43c1cecc | 156 | p += BS; |
c6add07f MM |
157 | sp = 0; |
158 | } | |
159 | if (isset) | |
160 | { | |
161 | *buf++ = ' '; | |
162 | *buf++ = '}'; | |
163 | sp = 0; | |
164 | } | |
165 | } | |
166 | *buf = 0; | |
167 | } | |
684c6f5a PM |
168 | |
169 | int | |
170 | as_path_getlen(struct adata *path) | |
171 | { | |
43c1cecc | 172 | return as_path_getlen_int(path, BS); |
949bd34e OZ |
173 | } |
174 | ||
175 | int | |
176 | as_path_getlen_int(struct adata *path, int bs) | |
177 | { | |
684c6f5a PM |
178 | int res = 0; |
179 | u8 *p = path->data; | |
180 | u8 *q = p+path->length; | |
181 | int len; | |
182 | ||
4b03f64b MM |
183 | while (p<q) |
184 | { | |
185 | switch (*p++) | |
186 | { | |
11cb6202 OZ |
187 | case AS_PATH_SET: len = *p++; res++; p += bs * len; break; |
188 | case AS_PATH_SEQUENCE: len = *p++; res += len; p += bs * len; break; | |
4b03f64b MM |
189 | default: bug("as_path_getlen: Invalid path segment"); |
190 | } | |
684c6f5a | 191 | } |
684c6f5a PM |
192 | return res; |
193 | } | |
2a40efa5 | 194 | |
f49528a3 | 195 | int |
52b9b2a1 | 196 | as_path_get_last(struct adata *path, u32 *orig_as) |
f49528a3 | 197 | { |
11cb6202 OZ |
198 | int found = 0; |
199 | u32 res = 0; | |
f49528a3 MM |
200 | u8 *p = path->data; |
201 | u8 *q = p+path->length; | |
202 | int len; | |
203 | ||
204 | while (p<q) | |
205 | { | |
206 | switch (*p++) | |
207 | { | |
208 | case AS_PATH_SET: | |
209 | if (len = *p++) | |
11cb6202 | 210 | { |
52b9b2a1 | 211 | found = 0; |
43c1cecc | 212 | p += BS * len; |
11cb6202 | 213 | } |
f49528a3 MM |
214 | break; |
215 | case AS_PATH_SEQUENCE: | |
216 | if (len = *p++) | |
11cb6202 OZ |
217 | { |
218 | found = 1; | |
43c1cecc OZ |
219 | res = get_as(p + BS * (len - 1)); |
220 | p += BS * len; | |
11cb6202 | 221 | } |
f49528a3 MM |
222 | break; |
223 | default: bug("as_path_get_first: Invalid path segment"); | |
224 | } | |
225 | } | |
11cb6202 | 226 | |
52b9b2a1 OZ |
227 | if (found) |
228 | *orig_as = res; | |
11cb6202 | 229 | return found; |
f49528a3 MM |
230 | } |
231 | ||
b6bf284a | 232 | int |
52b9b2a1 | 233 | as_path_get_first(struct adata *path, u32 *last_as) |
b6bf284a OZ |
234 | { |
235 | u8 *p = path->data; | |
236 | ||
237 | if ((path->length == 0) || (p[0] != AS_PATH_SEQUENCE) || (p[1] == 0)) | |
238 | return 0; | |
239 | else | |
240 | { | |
241 | *last_as = get_as(p+2); | |
242 | return 1; | |
243 | } | |
244 | } | |
245 | ||
11cb6202 | 246 | int |
a15dab76 | 247 | as_path_contains(struct adata *path, u32 as, int min) |
11cb6202 | 248 | { |
11cb6202 OZ |
249 | u8 *p = path->data; |
250 | u8 *q = p+path->length; | |
a15dab76 | 251 | int num = 0; |
11cb6202 OZ |
252 | int i, n; |
253 | ||
254 | while (p<q) | |
255 | { | |
256 | n = p[1]; | |
257 | p += 2; | |
258 | for(i=0; i<n; i++) | |
259 | { | |
260 | if (get_as(p) == as) | |
a15dab76 OZ |
261 | if (++num == min) |
262 | return 1; | |
43c1cecc | 263 | p += BS; |
11cb6202 OZ |
264 | } |
265 | } | |
266 | return 0; | |
267 | } | |
268 | ||
cc31b75a OZ |
269 | int |
270 | as_path_match_set(struct adata *path, struct f_tree *set) | |
271 | { | |
272 | u8 *p = path->data; | |
273 | u8 *q = p+path->length; | |
274 | int i, n; | |
275 | ||
276 | while (p<q) | |
277 | { | |
278 | n = p[1]; | |
279 | p += 2; | |
280 | for (i=0; i<n; i++) | |
281 | { | |
282 | struct f_val v = {T_INT, .val.i = get_as(p)}; | |
283 | if (find_tree(set, v)) | |
284 | return 1; | |
285 | p += BS; | |
286 | } | |
287 | } | |
288 | ||
289 | return 0; | |
290 | } | |
291 | ||
bff9ce51 OZ |
292 | struct adata * |
293 | as_path_filter(struct linpool *pool, struct adata *path, struct f_tree *set, u32 key, int pos) | |
294 | { | |
295 | if (!path) | |
296 | return NULL; | |
297 | ||
298 | int len = path->length; | |
299 | u8 *p = path->data; | |
300 | u8 *q = path->data + len; | |
301 | u8 *d, *d2; | |
302 | int i, bt, sn, dn; | |
303 | u8 buf[len]; | |
304 | ||
305 | d = buf; | |
306 | while (p<q) | |
307 | { | |
308 | /* Read block header (type and length) */ | |
309 | bt = p[0]; | |
310 | sn = p[1]; | |
311 | dn = 0; | |
312 | p += 2; | |
313 | d2 = d + 2; | |
314 | ||
315 | for (i = 0; i < sn; i++) | |
316 | { | |
317 | u32 as = get_as(p); | |
318 | int match; | |
319 | ||
320 | if (set) | |
321 | match = !!find_tree(set, (struct f_val){T_INT, .val.i = as}); | |
322 | else | |
323 | match = (as == key); | |
324 | ||
325 | if (match == pos) | |
326 | { | |
327 | put_as(d2, as); | |
328 | d2 += BS; | |
329 | dn++; | |
330 | } | |
331 | ||
332 | p += BS; | |
333 | } | |
334 | ||
335 | if (dn > 0) | |
336 | { | |
337 | /* Nonempty block, set block header and advance */ | |
338 | d[0] = bt; | |
339 | d[1] = dn; | |
340 | d = d2; | |
341 | } | |
342 | } | |
343 | ||
344 | int nl = d - buf; | |
345 | if (nl == path->length) | |
346 | return path; | |
347 | ||
348 | struct adata *res = lp_alloc(pool, sizeof(struct adata) + nl); | |
349 | res->length = nl; | |
350 | memcpy(res->data, buf, nl); | |
351 | ||
352 | return res; | |
353 | } | |
354 | ||
11cb6202 | 355 | |
c8a6b9a3 OZ |
356 | struct pm_pos |
357 | { | |
358 | u8 set; | |
359 | u8 mark; | |
360 | union | |
361 | { | |
362 | char *sp; | |
363 | u32 asn; | |
364 | } val; | |
365 | }; | |
366 | ||
367 | static int | |
368 | parse_path(struct adata *path, struct pm_pos *pos) | |
2a40efa5 | 369 | { |
2a40efa5 | 370 | u8 *p = path->data; |
c8a6b9a3 OZ |
371 | u8 *q = p + path->length; |
372 | struct pm_pos *opos = pos; | |
05198c12 | 373 | int i, len; |
2a40efa5 | 374 | |
25cb9f1d | 375 | |
c8a6b9a3 OZ |
376 | while (p < q) |
377 | switch (*p++) | |
2a40efa5 | 378 | { |
c8a6b9a3 OZ |
379 | case AS_PATH_SET: |
380 | pos->set = 1; | |
381 | pos->mark = 0; | |
382 | pos->val.sp = p; | |
383 | len = *p; | |
43c1cecc | 384 | p += 1 + BS * len; |
c8a6b9a3 OZ |
385 | pos++; |
386 | break; | |
387 | ||
388 | case AS_PATH_SEQUENCE: | |
389 | len = *p++; | |
390 | for (i = 0; i < len; i++) | |
391 | { | |
392 | pos->set = 0; | |
393 | pos->mark = 0; | |
394 | pos->val.asn = get_as(p); | |
43c1cecc | 395 | p += BS; |
c8a6b9a3 | 396 | pos++; |
2a40efa5 | 397 | } |
c8a6b9a3 OZ |
398 | break; |
399 | ||
400 | default: | |
401 | bug("as_path_match: Invalid path component"); | |
2a40efa5 | 402 | } |
c8a6b9a3 OZ |
403 | |
404 | return pos - opos; | |
405 | } | |
406 | ||
407 | ||
408 | static int | |
409 | pm_match(struct pm_pos *pos, u32 asn) | |
410 | { | |
411 | if (! pos->set) | |
412 | return pos->val.asn == asn; | |
413 | ||
c8a6b9a3 OZ |
414 | u8 *p = pos->val.sp; |
415 | int len = *p++; | |
416 | int i; | |
417 | ||
418 | for (i = 0; i < len; i++) | |
43c1cecc | 419 | if (get_as(p + i * BS) == asn) |
c8a6b9a3 OZ |
420 | return 1; |
421 | ||
422 | return 0; | |
423 | } | |
424 | ||
425 | static void | |
426 | pm_mark(struct pm_pos *pos, int i, int plen, int *nl, int *nh) | |
427 | { | |
428 | int j; | |
429 | ||
430 | if (pos[i].set) | |
431 | pos[i].mark = 1; | |
432 | ||
433 | for (j = i + 1; (j < plen) && pos[j].set && (! pos[j].mark); j++) | |
434 | pos[j].mark = 1; | |
435 | pos[j].mark = 1; | |
436 | ||
437 | /* We are going downwards, therefore every mark is | |
438 | new low and just the first mark is new high */ | |
439 | ||
440 | *nl = i + (pos[i].set ? 0 : 1); | |
441 | ||
442 | if (*nh < 0) | |
443 | *nh = j; | |
444 | } | |
445 | ||
446 | /* AS path matching is nontrivial. Because AS path can | |
447 | * contain sets, it is not a plain wildcard matching. A set | |
448 | * in an AS path is interpreted as it might represent any | |
449 | * sequence of AS numbers from that set (possibly with | |
450 | * repetitions). So it is also a kind of a pattern, | |
451 | * more complicated than a path mask. | |
452 | * | |
453 | * The algorithm for AS path matching is a variant | |
454 | * of nondeterministic finite state machine, where | |
455 | * positions in AS path are states, and items in | |
456 | * path mask are input for that finite state machine. | |
457 | * During execution of the algorithm we maintain a set | |
458 | * of marked states - a state is marked if it can be | |
459 | * reached by any walk through NFSM with regard to | |
460 | * currently processed part of input. When we process | |
461 | * next part of mask, we advance each marked state. | |
462 | * We start with marked first position, when we | |
463 | * run out of marked positions, we reject. When | |
464 | * we process the whole mask, we accept iff final position | |
465 | * (auxiliary position after last real position in AS path) | |
466 | * is marked. | |
467 | */ | |
468 | ||
469 | int | |
470 | as_path_match(struct adata *path, struct f_path_mask *mask) | |
471 | { | |
472 | struct pm_pos pos[2048 + 1]; | |
473 | int plen = parse_path(path, pos); | |
474 | int l, h, i, nh, nl; | |
e81b440f | 475 | u32 val = 0; |
c8a6b9a3 OZ |
476 | |
477 | /* l and h are bound of interval of positions where | |
478 | are marked states */ | |
479 | ||
480 | pos[plen].set = 0; | |
481 | pos[plen].mark = 0; | |
482 | ||
483 | l = h = 0; | |
484 | pos[0].mark = 1; | |
485 | ||
486 | while (mask) | |
487 | { | |
488 | /* We remove this mark to not step after pos[plen] */ | |
489 | pos[plen].mark = 0; | |
490 | ||
491 | switch (mask->kind) | |
492 | { | |
493 | case PM_ASTERISK: | |
494 | for (i = l; i <= plen; i++) | |
495 | pos[i].mark = 1; | |
496 | h = plen; | |
497 | break; | |
498 | ||
c8a6b9a3 | 499 | case PM_ASN: |
92a72a4c OZ |
500 | val = mask->val; |
501 | goto step; | |
502 | case PM_ASN_EXPR: | |
503 | val = f_eval_asn((struct f_inst *) mask->val); | |
504 | goto step; | |
505 | case PM_QUESTION: | |
506 | step: | |
e81b440f | 507 | nh = nl = -1; |
c8a6b9a3 OZ |
508 | for (i = h; i >= l; i--) |
509 | if (pos[i].mark) | |
510 | { | |
511 | pos[i].mark = 0; | |
92a72a4c | 512 | if ((mask->kind == PM_QUESTION) || pm_match(pos + i, val)) |
c8a6b9a3 OZ |
513 | pm_mark(pos, i, plen, &nl, &nh); |
514 | } | |
515 | ||
516 | if (nh < 0) | |
2a40efa5 | 517 | return 0; |
c8a6b9a3 OZ |
518 | |
519 | h = nh; | |
520 | l = nl; | |
521 | break; | |
2a40efa5 | 522 | } |
2a40efa5 | 523 | |
c8a6b9a3 | 524 | mask = mask->next; |
2a40efa5 | 525 | } |
98347659 | 526 | |
c8a6b9a3 OZ |
527 | return pos[plen].mark; |
528 | } |