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