Annotation of embedaddon/bird/nest/a-path.c, revision 1.1
1.1 ! misho 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: val2 = val = f_eval_asn((struct f_inst *) mask->val);
! 539: goto step;
! 540: case PM_ASN_RANGE:
! 541: val = mask->val;
! 542: val2 = mask->val2;
! 543: goto step;
! 544: case PM_QUESTION:
! 545: step:
! 546: nh = nl = -1;
! 547: for (i = h; i >= l; i--)
! 548: if (pos[i].mark)
! 549: {
! 550: pos[i].mark = 0;
! 551: if ((mask->kind == PM_QUESTION) || pm_match(pos + i, val, val2))
! 552: pm_mark(pos, i, plen, &nl, &nh);
! 553: }
! 554:
! 555: if (nh < 0)
! 556: return 0;
! 557:
! 558: h = nh;
! 559: l = nl;
! 560: break;
! 561: }
! 562:
! 563: mask = mask->next;
! 564: }
! 565:
! 566: return pos[plen].mark;
! 567: }
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