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"
12: #include "nest/attrs.h"
13: #include "lib/resource.h"
14: #include "lib/unaligned.h"
15: #include "lib/string.h"
16: #include "filter/filter.h"
17:
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); }
20:
21: #define put_as put_u32
22: #define get_as get_u32
23: #define BS 4
24:
25: struct adata *
26: as_path_prepend(struct linpool *pool, struct adata *olda, u32 as)
27: {
28: struct adata *newa;
29:
30: if (olda->length && olda->data[0] == AS_PATH_SEQUENCE && olda->data[1] < 255)
31: /* Starting with sequence => just prepend the AS number */
32: {
33: int nl = olda->length + BS;
34: newa = lp_alloc(pool, sizeof(struct adata) + nl);
35: newa->length = nl;
36: newa->data[0] = AS_PATH_SEQUENCE;
37: newa->data[1] = olda->data[1] + 1;
38: memcpy(newa->data + BS + 2, olda->data + 2, olda->length - 2);
39: }
40: else /* Create new path segment */
41: {
42: int nl = olda->length + BS + 2;
43: newa = lp_alloc(pool, sizeof(struct adata) + nl);
44: newa->length = nl;
45: newa->data[0] = AS_PATH_SEQUENCE;
46: newa->data[1] = 1;
47: memcpy(newa->data + BS + 2, olda->data, olda->length);
48: }
49: put_as(newa->data + 2, as);
50: return newa;
51: }
52:
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:
126: void
127: as_path_format(struct adata *path, byte *buf, uint size)
128: {
129: byte *p = path->data;
130: byte *e = p + path->length;
131: byte *end = buf + size - 16;
132: int sp = 1;
133: int l, isset;
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++ = ' ';
155: buf += bsprintf(buf, "%u", get_as(p));
156: p += BS;
157: sp = 0;
158: }
159: if (isset)
160: {
161: *buf++ = ' ';
162: *buf++ = '}';
163: sp = 0;
164: }
165: }
166: *buf = 0;
167: }
168:
169: int
170: as_path_getlen(struct adata *path)
171: {
172: return as_path_getlen_int(path, BS);
173: }
174:
175: int
176: as_path_getlen_int(struct adata *path, int bs)
177: {
178: int res = 0;
179: u8 *p = path->data;
180: u8 *q = p+path->length;
181: int len;
182:
183: while (p<q)
184: {
185: switch (*p++)
186: {
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;
189: default: bug("as_path_getlen: Invalid path segment");
190: }
191: }
192: return res;
193: }
194:
195: int
196: as_path_get_last(struct adata *path, u32 *orig_as)
197: {
198: int found = 0;
199: u32 res = 0;
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++)
210: {
211: found = 0;
212: p += BS * len;
213: }
214: break;
215: case AS_PATH_SEQUENCE:
216: if (len = *p++)
217: {
218: found = 1;
219: res = get_as(p + BS * (len - 1));
220: p += BS * len;
221: }
222: break;
223: default: bug("Invalid path segment");
224: }
225: }
226:
227: if (found)
228: *orig_as = res;
229: return found;
230: }
231:
232: u32
233: as_path_get_last_nonaggregated(struct adata *path)
234: {
235: u8 *p = path->data;
236: u8 *q = p+path->length;
237: u32 res = 0;
238: int len;
239:
240: while (p<q)
241: {
242: switch (*p++)
243: {
244: case AS_PATH_SET:
245: return res;
246:
247: case AS_PATH_SEQUENCE:
248: if (len = *p++)
249: res = get_as(p + BS * (len - 1));
250: p += BS * len;
251: break;
252:
253: default: bug("Invalid path segment");
254: }
255: }
256:
257: return res;
258: }
259:
260:
261: int
262: as_path_get_first(struct adata *path, u32 *last_as)
263: {
264: u8 *p = path->data;
265:
266: if ((path->length == 0) || (p[0] != AS_PATH_SEQUENCE) || (p[1] == 0))
267: return 0;
268: else
269: {
270: *last_as = get_as(p+2);
271: return 1;
272: }
273: }
274:
275: int
276: as_path_contains(struct adata *path, u32 as, int min)
277: {
278: u8 *p = path->data;
279: u8 *q = p+path->length;
280: int num = 0;
281: int i, n;
282:
283: while (p<q)
284: {
285: n = p[1];
286: p += 2;
287: for(i=0; i<n; i++)
288: {
289: if (get_as(p) == as)
290: if (++num == min)
291: return 1;
292: p += BS;
293: }
294: }
295: return 0;
296: }
297:
298: int
299: as_path_match_set(struct adata *path, struct f_tree *set)
300: {
301: u8 *p = path->data;
302: u8 *q = p+path->length;
303: int i, n;
304:
305: while (p<q)
306: {
307: n = p[1];
308: p += 2;
309: for (i=0; i<n; i++)
310: {
311: struct f_val v = {T_INT, .val.i = get_as(p)};
312: if (find_tree(set, v))
313: return 1;
314: p += BS;
315: }
316: }
317:
318: return 0;
319: }
320:
321: struct adata *
322: as_path_filter(struct linpool *pool, struct adata *path, struct f_tree *set, u32 key, int pos)
323: {
324: if (!path)
325: return NULL;
326:
327: int len = path->length;
328: u8 *p = path->data;
329: u8 *q = path->data + len;
330: u8 *d, *d2;
331: int i, bt, sn, dn;
332: u8 buf[len];
333:
334: d = buf;
335: while (p<q)
336: {
337: /* Read block header (type and length) */
338: bt = p[0];
339: sn = p[1];
340: dn = 0;
341: p += 2;
342: d2 = d + 2;
343:
344: for (i = 0; i < sn; i++)
345: {
346: u32 as = get_as(p);
347: int match;
348:
349: if (set)
350: match = !!find_tree(set, (struct f_val){T_INT, .val.i = as});
351: else
352: match = (as == key);
353:
354: if (match == pos)
355: {
356: put_as(d2, as);
357: d2 += BS;
358: dn++;
359: }
360:
361: p += BS;
362: }
363:
364: if (dn > 0)
365: {
366: /* Nonempty block, set block header and advance */
367: d[0] = bt;
368: d[1] = dn;
369: d = d2;
370: }
371: }
372:
373: uint nl = d - buf;
374: if (nl == path->length)
375: return path;
376:
377: struct adata *res = lp_alloc(pool, sizeof(struct adata) + nl);
378: res->length = nl;
379: memcpy(res->data, buf, nl);
380:
381: return res;
382: }
383:
384:
385: struct pm_pos
386: {
387: u8 set;
388: u8 mark;
389: union
390: {
391: char *sp;
392: u32 asn;
393: } val;
394: };
395:
396: static int
397: parse_path(struct adata *path, struct pm_pos *pos)
398: {
399: u8 *p = path->data;
400: u8 *q = p + path->length;
401: struct pm_pos *opos = pos;
402: int i, len;
403:
404:
405: while (p < q)
406: switch (*p++)
407: {
408: case AS_PATH_SET:
409: pos->set = 1;
410: pos->mark = 0;
411: pos->val.sp = p;
412: len = *p;
413: p += 1 + BS * len;
414: pos++;
415: break;
416:
417: case AS_PATH_SEQUENCE:
418: len = *p++;
419: for (i = 0; i < len; i++)
420: {
421: pos->set = 0;
422: pos->mark = 0;
423: pos->val.asn = get_as(p);
424: p += BS;
425: pos++;
426: }
427: break;
428:
429: default:
430: bug("as_path_match: Invalid path component");
431: }
432:
433: return pos - opos;
434: }
435:
436:
437: static int
438: pm_match(struct pm_pos *pos, u32 asn, u32 asn2)
439: {
440: u32 gas;
441: if (! pos->set)
442: return ((pos->val.asn >= asn) && (pos->val.asn <= asn2));
443:
444: u8 *p = pos->val.sp;
445: int len = *p++;
446: int i;
447:
448: for (i = 0; i < len; i++)
449: {
450: gas = get_as(p + i * BS);
451:
452: if ((gas >= asn) && (gas <= asn2))
453: return 1;
454: }
455:
456: return 0;
457: }
458:
459: static void
460: pm_mark(struct pm_pos *pos, int i, int plen, int *nl, int *nh)
461: {
462: int j;
463:
464: if (pos[i].set)
465: pos[i].mark = 1;
466:
467: for (j = i + 1; (j < plen) && pos[j].set && (! pos[j].mark); j++)
468: pos[j].mark = 1;
469: pos[j].mark = 1;
470:
471: /* We are going downwards, therefore every mark is
472: new low and just the first mark is new high */
473:
474: *nl = i + (pos[i].set ? 0 : 1);
475:
476: if (*nh < 0)
477: *nh = j;
478: }
479:
480: /* AS path matching is nontrivial. Because AS path can
481: * contain sets, it is not a plain wildcard matching. A set
482: * in an AS path is interpreted as it might represent any
483: * sequence of AS numbers from that set (possibly with
484: * repetitions). So it is also a kind of a pattern,
485: * more complicated than a path mask.
486: *
487: * The algorithm for AS path matching is a variant
488: * of nondeterministic finite state machine, where
489: * positions in AS path are states, and items in
490: * path mask are input for that finite state machine.
491: * During execution of the algorithm we maintain a set
492: * of marked states - a state is marked if it can be
493: * reached by any walk through NFSM with regard to
494: * currently processed part of input. When we process
495: * next part of mask, we advance each marked state.
496: * We start with marked first position, when we
497: * run out of marked positions, we reject. When
498: * we process the whole mask, we accept if final position
499: * (auxiliary position after last real position in AS path)
500: * is marked.
501: */
502:
503: int
504: as_path_match(struct adata *path, struct f_path_mask *mask)
505: {
506: struct pm_pos pos[2048 + 1];
507: int plen = parse_path(path, pos);
508: int l, h, i, nh, nl;
509: u32 val = 0;
510: u32 val2 = 0;
511:
512: /* l and h are bound of interval of positions where
513: are marked states */
514:
515: pos[plen].set = 0;
516: pos[plen].mark = 0;
517:
518: l = h = 0;
519: pos[0].mark = 1;
520:
521: while (mask)
522: {
523: /* We remove this mark to not step after pos[plen] */
524: pos[plen].mark = 0;
525:
526: switch (mask->kind)
527: {
528: case PM_ASTERISK:
529: for (i = l; i <= plen; i++)
530: pos[i].mark = 1;
531: h = plen;
532: break;
533:
534: case PM_ASN: /* Define single ASN as ASN..ASN - very narrow interval */
535: val2 = val = mask->val;
536: goto step;
537: case PM_ASN_EXPR:
538: ASSERT(0);
539: case PM_ASN_RANGE:
540: val = mask->val;
541: val2 = mask->val2;
542: goto step;
543: case PM_QUESTION:
544: step:
545: nh = nl = -1;
546: for (i = h; i >= l; i--)
547: if (pos[i].mark)
548: {
549: pos[i].mark = 0;
550: if ((mask->kind == PM_QUESTION) || pm_match(pos + i, val, val2))
551: pm_mark(pos, i, plen, &nl, &nh);
552: }
553:
554: if (nh < 0)
555: return 0;
556:
557: h = nh;
558: l = nl;
559: break;
560: }
561:
562: mask = mask->next;
563: }
564:
565: return pos[plen].mark;
566: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to a-path.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird / nest