nest/a-path.c

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