Annotation of embedaddon/bird2/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/data.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 /* Default block size of ASN (autonomous system number) */
! 24:
! 25: #define BAD(DSC, VAL) ({ err_dsc = DSC; err_val = VAL; goto bad; })
! 26:
! 27: int
! 28: as_path_valid(byte *data, uint len, int bs, int confed, char *err, uint elen)
! 29: {
! 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:
! 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:
! 59: BAD("unknown segment", type);
! 60: }
! 61:
! 62: if (pos[1] == 0)
! 63: BAD("zero-length segment", type);
! 64:
! 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, const byte *src, uint len)
! 81: {
! 82: byte *dst0 = dst;
! 83: const 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++)
! 93: {
! 94: put_u32(dst, get_u16(src));
! 95: src += 2;
! 96: dst += 4;
! 97: }
! 98: }
! 99:
! 100: return dst - dst0;
! 101: }
! 102:
! 103: int
! 104: as_path_32to16(byte *dst, const byte *src, uint len)
! 105: {
! 106: byte *dst0 = dst;
! 107: const 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++)
! 117: {
! 118: put_u16(dst, get_u32(src));
! 119: src += 4;
! 120: dst += 2;
! 121: }
! 122: }
! 123:
! 124: return dst - dst0;
! 125: }
! 126:
! 127: int
! 128: as_path_contains_as4(const struct adata *path)
! 129: {
! 130: const byte *pos = path->data;
! 131: const byte *end = pos + path->length;
! 132: uint i, n;
! 133:
! 134: while (pos < end)
! 135: {
! 136: n = pos[1];
! 137: pos += 2;
! 138:
! 139: for (i = 0; i < n; i++)
! 140: {
! 141: if (get_as(pos) > 0xFFFF)
! 142: return 1;
! 143:
! 144: pos += BS;
! 145: }
! 146: }
! 147:
! 148: return 0;
! 149: }
! 150:
! 151: int
! 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:
! 172: struct adata *
! 173: as_path_strip_confed(struct linpool *pool, const struct adata *path)
! 174: {
! 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;
! 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: }
! 194:
! 195: /* Fix the result length */
! 196: res->length = dst - res->data;
! 197:
! 198: return res;
! 199: }
! 200:
! 201: struct adata *
! 202: as_path_prepend2(struct linpool *pool, const struct adata *op, int seq, u32 as)
! 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:
! 233: memcpy(dst, pos, len);
! 234: }
! 235:
! 236: return np;
! 237: }
! 238:
! 239:
! 240: struct adata *
! 241: as_path_to_old(struct linpool *pool, const struct adata *path)
! 242: {
! 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;
! 247: u32 as;
! 248:
! 249: /* Copy the whole path */
! 250: memcpy(res->data, path->data, path->length);
! 251:
! 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++)
! 259: {
! 260: as = get_as(pos);
! 261: if (as > 0xFFFF)
! 262: put_as(pos, AS_TRANS);
! 263:
! 264: pos += BS;
! 265: }
! 266: }
! 267:
! 268: return res;
! 269: }
! 270:
! 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: */
! 275: struct adata *
! 276: as_path_cut(struct linpool *pool, const struct adata *path, uint num)
! 277: {
! 278: const byte *pos = path->data;
! 279: const byte *end = pos + path->length;
! 280:
! 281: while (pos < end)
! 282: {
! 283: uint t = pos[0];
! 284: uint l = pos[1];
! 285: uint n = 0;
! 286:
! 287: switch (t)
! 288: {
! 289: case AS_PATH_SET: n = 1; break;
! 290: case AS_PATH_SEQUENCE: n = l; break;
! 291: case AS_PATH_CONFED_SEQUENCE: n = 0; break;
! 292: case AS_PATH_CONFED_SET: n = 0; break;
! 293: default: bug("as_path_cut: Invalid path segment");
! 294: }
! 295:
! 296: /* Cannot add whole segment, so try partial one and finish */
! 297: if (num < n)
! 298: {
! 299: const byte *nend = pos;
! 300: if (num)
! 301: nend += 2 + BS * num;
! 302:
! 303: struct adata *res = lp_alloc_adata(pool, path->length);
! 304: res->length = nend - (const byte *) path->data;
! 305: memcpy(res->data, path->data, res->length);
! 306:
! 307: if (num)
! 308: {
! 309: byte *dpos = ((byte *) res->data) + (pos - (const byte *) path->data);
! 310: dpos[1] = num;
! 311: }
! 312:
! 313: return res;
! 314: }
! 315:
! 316: num -= n;
! 317: pos += 2 + BS * l;
! 318: }
! 319:
! 320: struct adata *res = lp_alloc_adata(pool, path->length);
! 321: res->length = path->length;
! 322: memcpy(res->data, path->data, res->length);
! 323: return res;
! 324: }
! 325:
! 326: /*
! 327: * Merge (concatenate) paths @p1 and @p2 and return the result.
! 328: * In contrast to other as_path_* functions, @p1 and @p2 may be reused.
! 329: */
! 330: const struct adata *
! 331: as_path_merge(struct linpool *pool, const struct adata *p1, const struct adata *p2)
! 332: {
! 333: if (p1->length == 0)
! 334: return p2;
! 335:
! 336: if (p2->length == 0)
! 337: return p1;
! 338:
! 339: struct adata *res = lp_alloc_adata(pool, p1->length + p2->length);
! 340: memcpy(res->data, p1->data, p1->length);
! 341: memcpy(res->data + p1->length, p2->data, p2->length);
! 342:
! 343: return res;
! 344: }
! 345:
! 346: void
! 347: as_path_format(const struct adata *path, byte *bb, uint size)
! 348: {
! 349: buffer buf = { .start = bb, .pos = bb, .end = bb + size }, *b = &buf;
! 350: const byte *pos = path->data;
! 351: const byte *end = pos + path->length;
! 352: const char *ops, *cls;
! 353:
! 354: b->pos[0] = 0;
! 355:
! 356: while (pos < end)
! 357: {
! 358: uint type = pos[0];
! 359: uint len = pos[1];
! 360: pos += 2;
! 361:
! 362: switch (type)
! 363: {
! 364: case AS_PATH_SET: ops = "{"; cls = "}"; break;
! 365: case AS_PATH_SEQUENCE: ops = NULL; cls = NULL; break;
! 366: case AS_PATH_CONFED_SEQUENCE: ops = "("; cls = ")"; break;
! 367: case AS_PATH_CONFED_SET: ops = "({"; cls = "})"; break;
! 368: default: bug("Invalid path segment");
! 369: }
! 370:
! 371: if (ops)
! 372: buffer_puts(b, ops);
! 373:
! 374: while (len--)
! 375: {
! 376: buffer_print(b, len ? "%u " : "%u", get_as(pos));
! 377: pos += BS;
! 378: }
! 379:
! 380: if (cls)
! 381: buffer_puts(b, cls);
! 382:
! 383: if (pos < end)
! 384: buffer_puts(b, " ");
! 385: }
! 386:
! 387: /* Handle overflow */
! 388: if (b->pos == b->end)
! 389: strcpy(b->end - 12, "...");
! 390: }
! 391:
! 392: int
! 393: as_path_getlen(const struct adata *path)
! 394: {
! 395: const byte *pos = path->data;
! 396: const byte *end = pos + path->length;
! 397: uint res = 0;
! 398:
! 399: while (pos < end)
! 400: {
! 401: uint t = pos[0];
! 402: uint l = pos[1];
! 403: uint n = 0;
! 404:
! 405: switch (t)
! 406: {
! 407: case AS_PATH_SET: n = 1; break;
! 408: case AS_PATH_SEQUENCE: n = l; break;
! 409: case AS_PATH_CONFED_SEQUENCE: n = 0; break;
! 410: case AS_PATH_CONFED_SET: n = 0; break;
! 411: default: bug("as_path_getlen: Invalid path segment");
! 412: }
! 413:
! 414: res += n;
! 415: pos += 2 + BS * l;
! 416: }
! 417:
! 418: return res;
! 419: }
! 420:
! 421: int
! 422: as_path_get_last(const struct adata *path, u32 *orig_as)
! 423: {
! 424: const byte *pos = path->data;
! 425: const byte *end = pos + path->length;
! 426: int found = 0;
! 427: u32 val = 0;
! 428:
! 429: while (pos < end)
! 430: {
! 431: uint type = pos[0];
! 432: uint len = pos[1];
! 433: pos += 2;
! 434:
! 435: if (!len)
! 436: continue;
! 437:
! 438: switch (type)
! 439: {
! 440: case AS_PATH_SET:
! 441: case AS_PATH_CONFED_SET:
! 442: found = 0;
! 443: break;
! 444:
! 445: case AS_PATH_SEQUENCE:
! 446: case AS_PATH_CONFED_SEQUENCE:
! 447: val = get_as(pos + BS * (len - 1));
! 448: found = 1;
! 449: break;
! 450:
! 451: default:
! 452: bug("Invalid path segment");
! 453: }
! 454:
! 455: pos += BS * len;
! 456: }
! 457:
! 458: if (found)
! 459: *orig_as = val;
! 460: return found;
! 461: }
! 462:
! 463: u32
! 464: as_path_get_last_nonaggregated(const struct adata *path)
! 465: {
! 466: const byte *pos = path->data;
! 467: const byte *end = pos + path->length;
! 468: u32 val = 0;
! 469:
! 470: while (pos < end)
! 471: {
! 472: uint type = pos[0];
! 473: uint len = pos[1];
! 474: pos += 2;
! 475:
! 476: if (!len)
! 477: continue;
! 478:
! 479: switch (type)
! 480: {
! 481: case AS_PATH_SET:
! 482: case AS_PATH_CONFED_SET:
! 483: return val;
! 484:
! 485: case AS_PATH_SEQUENCE:
! 486: case AS_PATH_CONFED_SEQUENCE:
! 487: val = get_as(pos + BS * (len - 1));
! 488: break;
! 489:
! 490: default:
! 491: bug("Invalid path segment");
! 492: }
! 493:
! 494: pos += BS * len;
! 495: }
! 496:
! 497: return val;
! 498: }
! 499:
! 500: int
! 501: as_path_get_first(const struct adata *path, u32 *last_as)
! 502: {
! 503: const u8 *p = path->data;
! 504:
! 505: if ((path->length == 0) || (p[0] != AS_PATH_SEQUENCE) || (p[1] == 0))
! 506: return 0;
! 507:
! 508: *last_as = get_as(p+2);
! 509: return 1;
! 510: }
! 511:
! 512: int
! 513: as_path_get_first_regular(const struct adata *path, u32 *last_as)
! 514: {
! 515: const byte *pos = path->data;
! 516: const byte *end = pos + path->length;
! 517:
! 518: while (pos < end)
! 519: {
! 520: uint type = pos[0];
! 521: uint len = pos[1];
! 522: pos += 2;
! 523:
! 524: switch (type)
! 525: {
! 526: case AS_PATH_SET:
! 527: return 0;
! 528:
! 529: case AS_PATH_SEQUENCE:
! 530: if (len == 0)
! 531: return 0;
! 532:
! 533: *last_as = get_as(pos);
! 534: return 1;
! 535:
! 536: case AS_PATH_CONFED_SEQUENCE:
! 537: case AS_PATH_CONFED_SET:
! 538: break;
! 539:
! 540: default:
! 541: bug("Invalid path segment");
! 542: }
! 543:
! 544: pos += BS * len;
! 545: }
! 546:
! 547: return 0;
! 548: }
! 549:
! 550: int
! 551: as_path_contains(const struct adata *path, u32 as, int min)
! 552: {
! 553: const u8 *p = path->data;
! 554: const u8 *q = p+path->length;
! 555: int num = 0;
! 556: int i, n;
! 557:
! 558: while (p<q)
! 559: {
! 560: n = p[1];
! 561: p += 2;
! 562: for(i=0; i<n; i++)
! 563: {
! 564: if (get_as(p) == as)
! 565: if (++num == min)
! 566: return 1;
! 567: p += BS;
! 568: }
! 569: }
! 570: return 0;
! 571: }
! 572:
! 573: int
! 574: as_path_match_set(const struct adata *path, const struct f_tree *set)
! 575: {
! 576: const u8 *p = path->data;
! 577: const u8 *q = p+path->length;
! 578: int i, n;
! 579:
! 580: while (p<q)
! 581: {
! 582: n = p[1];
! 583: p += 2;
! 584: for (i=0; i<n; i++)
! 585: {
! 586: struct f_val v = {T_INT, .val.i = get_as(p)};
! 587: if (find_tree(set, &v))
! 588: return 1;
! 589: p += BS;
! 590: }
! 591: }
! 592:
! 593: return 0;
! 594: }
! 595:
! 596: const struct adata *
! 597: as_path_filter(struct linpool *pool, const struct adata *path, const struct f_tree *set, u32 key, int pos)
! 598: {
! 599: if (!path)
! 600: return NULL;
! 601:
! 602: int len = path->length;
! 603: const u8 *p = path->data;
! 604: const u8 *q = path->data + len;
! 605: u8 *d, *d2;
! 606: int i, bt, sn, dn;
! 607: u8 buf[len];
! 608:
! 609: d = buf;
! 610: while (p<q)
! 611: {
! 612: /* Read block header (type and length) */
! 613: bt = p[0];
! 614: sn = p[1];
! 615: dn = 0;
! 616: p += 2;
! 617: d2 = d + 2;
! 618:
! 619: for (i = 0; i < sn; i++)
! 620: {
! 621: u32 as = get_as(p);
! 622: int match;
! 623:
! 624: if (set)
! 625: {
! 626: struct f_val v = {T_INT, .val.i = as};
! 627: match = !!find_tree(set, &v);
! 628: }
! 629: else
! 630: match = (as == key);
! 631:
! 632: if (match == pos)
! 633: {
! 634: put_as(d2, as);
! 635: d2 += BS;
! 636: dn++;
! 637: }
! 638:
! 639: p += BS;
! 640: }
! 641:
! 642: if (dn > 0)
! 643: {
! 644: /* Nonempty block, set block header and advance */
! 645: d[0] = bt;
! 646: d[1] = dn;
! 647: d = d2;
! 648: }
! 649: }
! 650:
! 651: uint nl = d - buf;
! 652: if (nl == path->length)
! 653: return path;
! 654:
! 655: struct adata *res = lp_alloc(pool, sizeof(struct adata) + nl);
! 656: res->length = nl;
! 657: memcpy(res->data, buf, nl);
! 658:
! 659: return res;
! 660: }
! 661:
! 662:
! 663: struct pm_pos
! 664: {
! 665: u8 set;
! 666: u8 mark;
! 667: union
! 668: {
! 669: const char *sp;
! 670: u32 asn;
! 671: } val;
! 672: };
! 673:
! 674: static int
! 675: parse_path(const struct adata *path, struct pm_pos *pp)
! 676: {
! 677: const byte *pos = path->data;
! 678: const byte *end = pos + path->length;
! 679: struct pm_pos *op = pp;
! 680: uint i;
! 681:
! 682: while (pos < end)
! 683: {
! 684: uint type = pos[0];
! 685: uint len = pos[1];
! 686: pos += 2;
! 687:
! 688: switch (type)
! 689: {
! 690: case AS_PATH_SET:
! 691: case AS_PATH_CONFED_SET:
! 692: pp->set = 1;
! 693: pp->mark = 0;
! 694: pp->val.sp = pos - 1;
! 695: pp++;
! 696:
! 697: pos += BS * len;
! 698: break;
! 699:
! 700: case AS_PATH_SEQUENCE:
! 701: case AS_PATH_CONFED_SEQUENCE:
! 702: for (i = 0; i < len; i++)
! 703: {
! 704: pp->set = 0;
! 705: pp->mark = 0;
! 706: pp->val.asn = get_as(pos);
! 707: pp++;
! 708:
! 709: pos += BS;
! 710: }
! 711: break;
! 712:
! 713: default:
! 714: bug("Invalid path segment");
! 715: }
! 716: }
! 717:
! 718: return pp - op;
! 719: }
! 720:
! 721: static int
! 722: pm_match(struct pm_pos *pos, u32 asn, u32 asn2)
! 723: {
! 724: u32 gas;
! 725: if (! pos->set)
! 726: return ((pos->val.asn >= asn) && (pos->val.asn <= asn2));
! 727:
! 728: const u8 *p = pos->val.sp;
! 729: int len = *p++;
! 730: int i;
! 731:
! 732: for (i = 0; i < len; i++)
! 733: {
! 734: gas = get_as(p + i * BS);
! 735:
! 736: if ((gas >= asn) && (gas <= asn2))
! 737: return 1;
! 738: }
! 739:
! 740: return 0;
! 741: }
! 742:
! 743: static int
! 744: pm_match_set(struct pm_pos *pos, const struct f_tree *set)
! 745: {
! 746: struct f_val asn = { .type = T_INT };
! 747:
! 748: if (! pos->set)
! 749: {
! 750: asn.val.i = pos->val.asn;
! 751: return !!find_tree(set, &asn);
! 752: }
! 753:
! 754: const u8 *p = pos->val.sp;
! 755: int len = *p++;
! 756: int i;
! 757:
! 758: for (i = 0; i < len; i++)
! 759: {
! 760: asn.val.i = get_as(p + i * BS);
! 761: if (find_tree(set, &asn))
! 762: return 1;
! 763: }
! 764:
! 765: return 0;
! 766: }
! 767:
! 768: static void
! 769: pm_mark(struct pm_pos *pos, int i, int plen, int *nl, int *nh)
! 770: {
! 771: int j;
! 772:
! 773: if (pos[i].set)
! 774: pos[i].mark = 1;
! 775:
! 776: for (j = i + 1; (j < plen) && pos[j].set && (! pos[j].mark); j++)
! 777: pos[j].mark = 1;
! 778: pos[j].mark = 1;
! 779:
! 780: /* We are going downwards, therefore every mark is
! 781: new low and just the first mark is new high */
! 782:
! 783: *nl = i + (pos[i].set ? 0 : 1);
! 784:
! 785: if (*nh < 0)
! 786: *nh = j;
! 787: }
! 788:
! 789: /* AS path matching is nontrivial. Because AS path can
! 790: * contain sets, it is not a plain wildcard matching. A set
! 791: * in an AS path is interpreted as it might represent any
! 792: * sequence of AS numbers from that set (possibly with
! 793: * repetitions). So it is also a kind of a pattern,
! 794: * more complicated than a path mask.
! 795: *
! 796: * The algorithm for AS path matching is a variant
! 797: * of nondeterministic finite state machine, where
! 798: * positions in AS path are states, and items in
! 799: * path mask are input for that finite state machine.
! 800: * During execution of the algorithm we maintain a set
! 801: * of marked states - a state is marked if it can be
! 802: * reached by any walk through NFSM with regard to
! 803: * currently processed part of input. When we process
! 804: * next part of mask, we advance each marked state.
! 805: * We start with marked first position, when we
! 806: * run out of marked positions, we reject. When
! 807: * we process the whole mask, we accept if final position
! 808: * (auxiliary position after last real position in AS path)
! 809: * is marked.
! 810: */
! 811: int
! 812: as_path_match(const struct adata *path, const struct f_path_mask *mask)
! 813: {
! 814: struct pm_pos pos[2048 + 1];
! 815: int plen = parse_path(path, pos);
! 816: int l, h, i, nh, nl;
! 817: u32 val = 0;
! 818: u32 val2 = 0;
! 819:
! 820: /* l and h are bound of interval of positions where
! 821: are marked states */
! 822:
! 823: pos[plen].set = 0;
! 824: pos[plen].mark = 0;
! 825:
! 826: l = h = 0;
! 827: pos[0].mark = 1;
! 828:
! 829: for (uint m=0; m < mask->len; m++)
! 830: {
! 831: /* We remove this mark to not step after pos[plen] */
! 832: pos[plen].mark = 0;
! 833:
! 834: switch (mask->item[m].kind)
! 835: {
! 836: case PM_ASTERISK:
! 837: for (i = l; i <= plen; i++)
! 838: pos[i].mark = 1;
! 839: h = plen;
! 840: break;
! 841:
! 842: case PM_ASN: /* Define single ASN as ASN..ASN - very narrow interval */
! 843: val2 = val = mask->item[m].asn;
! 844: goto step;
! 845: case PM_ASN_EXPR:
! 846: bug("Expressions should be evaluated on AS path mask construction.");
! 847: case PM_ASN_RANGE:
! 848: val = mask->item[m].from;
! 849: val2 = mask->item[m].to;
! 850: goto step;
! 851: case PM_QUESTION:
! 852: case PM_ASN_SET:
! 853: step:
! 854: nh = nl = -1;
! 855: for (i = h; i >= l; i--)
! 856: if (pos[i].mark)
! 857: {
! 858: pos[i].mark = 0;
! 859: if ((mask->item[m].kind == PM_QUESTION) ||
! 860: ((mask->item[m].kind != PM_ASN_SET) ?
! 861: pm_match(pos + i, val, val2) :
! 862: pm_match_set(pos + i, mask->item[m].set)))
! 863: pm_mark(pos, i, plen, &nl, &nh);
! 864: }
! 865:
! 866: if (nh < 0)
! 867: return 0;
! 868:
! 869: h = nh;
! 870: l = nl;
! 871: break;
! 872: }
! 873: }
! 874:
! 875: return pos[plen].mark;
! 876: }
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 / bird2 / nest