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/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, 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 }