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, unsigned int 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("as_path_get_first: Invalid path segment");
 224         }
 225     }
 226
 227   if (found)
 228     *orig_as = res;
 229   return found;
 230 }
 231
 232 int
 233 as_path_get_first(struct adata *path, u32 *last_as)
 234 {
 235   u8 *p = path->data;
 236
 237   if ((path->length == 0) || (p[0] != AS_PATH_SEQUENCE) || (p[1] == 0))
 238     return 0;
 239   else
 240     {
 241       *last_as = get_as(p+2);
 242       return 1;
 243     }
 244 }
 245
 246 int
 247 as_path_contains(struct adata *path, u32 as, int min)
 248 {
 249   u8 *p = path->data;
 250   u8 *q = p+path->length;
 251   int num = 0;
 252   int i, n;
 253
 254   while (p<q)
 255     {
 256       n = p[1];
 257       p += 2;
 258       for(i=0; i<n; i++)
 259         {
 260           if (get_as(p) == as)
 261             if (++num == min)
 262               return 1;
 263           p += BS;
 264         }
 265     }
 266   return 0;
 267 }
 268
 269 int
 270 as_path_match_set(struct adata *path, struct f_tree *set)
 271 {
 272   u8 *p = path->data;
 273   u8 *q = p+path->length;
 274   int i, n;
 275
 276   while (p<q)
 277     {
 278       n = p[1];
 279       p += 2;
 280       for (i=0; i<n; i++)
 281         {
 282           struct f_val v = {T_INT, .val.i = get_as(p)};
 283           if (find_tree(set, v))
 284             return 1;
 285           p += BS;
 286         }
 287     }
 288
 289   return 0;
 290 }
 291
 292 struct adata *
 293 as_path_filter(struct linpool *pool, struct adata *path, struct f_tree *set, u32 key, int pos)
 294 {
 295   if (!path)
 296     return NULL;
 297
 298   int len = path->length;
 299   u8 *p = path->data;
 300   u8 *q = path->data + len;
 301   u8 *d, *d2;
 302   int i, bt, sn, dn;
 303   u8 buf[len];
 304
 305   d = buf;
 306   while (p<q)
 307     {
 308       /* Read block header (type and length) */
 309       bt = p[0];
 310       sn = p[1];
 311       dn = 0;
 312       p += 2;
 313       d2 = d + 2;
 314
 315       for (i = 0; i < sn; i++)
 316         {
 317           u32 as = get_as(p);
 318           int match;
 319
 320           if (set)
 321             match = !!find_tree(set, (struct f_val){T_INT, .val.i = as});
 322           else
 323             match = (as == key);
 324
 325           if (match == pos)
 326             {
 327               put_as(d2, as);
 328               d2 += BS;
 329               dn++;
 330             }
 331
 332           p += BS;
 333         }
 334
 335       if (dn > 0)
 336         {
 337           /* Nonempty block, set block header and advance */
 338           d[0] = bt;
 339           d[1] = dn;
 340           d = d2;
 341         }
 342   }
 343
 344   int nl = d - buf;
 345   if (nl == path->length)
 346     return path;
 347
 348   struct adata *res = lp_alloc(pool, sizeof(struct adata) + nl);
 349   res->length = nl;
 350   memcpy(res->data, buf, nl);
 351
 352   return res;
 353 }
 354
 355
 356 struct pm_pos
 357 {
 358   u8 set;
 359   u8 mark;
 360   union
 361   {
 362     char *sp;
 363     u32 asn;
 364   } val;
 365 };
 366
 367 static int
 368 parse_path(struct adata *path, struct pm_pos *pos)
 369 {
 370   u8 *p = path->data;
 371   u8 *q = p + path->length;
 372   struct pm_pos *opos = pos;
 373   int i, len;
 374
 375
 376   while (p < q)
 377     switch (*p++)
 378       {
 379       case AS_PATH_SET:
 380         pos->set = 1;
 381         pos->mark = 0;
 382         pos->val.sp = p;
 383         len = *p;
 384         p += 1 + BS * len;
 385         pos++;
 386         break;
 387
 388       case AS_PATH_SEQUENCE:
 389         len = *p++;
 390         for (i = 0; i < len; i++)
 391           {
 392             pos->set = 0;
 393             pos->mark = 0;
 394             pos->val.asn = get_as(p);
 395             p += BS;
 396             pos++;
 397           }
 398         break;
 399
 400       default:
 401         bug("as_path_match: Invalid path component");
 402       }
 403
 404   return pos - opos;
 405 }
 406
 407
 408 static int
 409 pm_match(struct pm_pos *pos, u32 asn)
 410 {
 411   if (! pos->set)
 412     return pos->val.asn == asn;
 413
 414   u8 *p = pos->val.sp;
 415   int len = *p++;
 416   int i;
 417
 418   for (i = 0; i < len; i++)
 419     if (get_as(p + i * BS) == asn)
 420       return 1;
 421
 422   return 0;
 423 }
 424
 425 static void
 426 pm_mark(struct pm_pos *pos, int i, int plen, int *nl, int *nh)
 427 {
 428   int j;
 429
 430   if (pos[i].set)
 431     pos[i].mark = 1;
 432
 433   for (j = i + 1; (j < plen) && pos[j].set && (! pos[j].mark); j++)
 434     pos[j].mark = 1;
 435   pos[j].mark = 1;
 436
 437   /* We are going downwards, therefore every mark is
 438      new low and just the first mark is new high */
 439
 440   *nl = i + (pos[i].set ? 0 : 1);
 441
 442   if (*nh < 0)
 443     *nh = j;
 444 }
 445
 446 /* AS path matching is nontrivial. Because AS path can
 447  * contain sets, it is not a plain wildcard matching. A set
 448  * in an AS path is interpreted as it might represent any
 449  * sequence of AS numbers from that set (possibly with
 450  * repetitions). So it is also a kind of a pattern,
 451  * more complicated than a path mask.
 452  *
 453  * The algorithm for AS path matching is a variant
 454  * of nondeterministic finite state machine, where
 455  * positions in AS path are states, and items in
 456  * path mask are input for that finite state machine.
 457  * During execution of the algorithm we maintain a set
 458  * of marked states - a state is marked if it can be
 459  * reached by any walk through NFSM with regard to
 460  * currently processed part of input. When we process
 461  * next part of mask, we advance each marked state.
 462  * We start with marked first position, when we
 463  * run out of marked positions, we reject. When
 464  * we process the whole mask, we accept iff final position
 465  * (auxiliary position after last real position in AS path)
 466  * is marked.
 467  */
 468
 469 int
 470 as_path_match(struct adata *path, struct f_path_mask *mask)
 471 {
 472   struct pm_pos pos[2048 + 1];
 473   int plen = parse_path(path, pos);
 474   int l, h, i, nh, nl;
 475   u32 val = 0;
 476
 477   /* l and h are bound of interval of positions where
 478      are marked states */
 479
 480   pos[plen].set = 0;
 481   pos[plen].mark = 0;
 482
 483   l = h = 0;
 484   pos[0].mark = 1;
 485
 486   while (mask)
 487     {
 488       /* We remove this mark to not step after pos[plen] */
 489       pos[plen].mark = 0;
 490
 491       switch (mask->kind)
 492         {
 493         case PM_ASTERISK:
 494           for (i = l; i <= plen; i++)
 495             pos[i].mark = 1;
 496           h = plen;
 497           break;
 498
 499         case PM_ASN:
 500           val = mask->val;
 501           goto step;
 502         case PM_ASN_EXPR:
 503           val = f_eval_asn((struct f_inst *) mask->val);
 504           goto step;
 505         case PM_QUESTION:
 506         step:
 507           nh = nl = -1;
 508           for (i = h; i >= l; i--)
 509             if (pos[i].mark)
 510               {
 511                 pos[i].mark = 0;
 512                 if ((mask->kind == PM_QUESTION) || pm_match(pos + i, val))
 513                   pm_mark(pos, i, plen, &nl, &nh);
 514               }
 515
 516           if (nh < 0)
 517             return 0;
 518
 519           h = nh;
 520           l = nl;
 521           break;
 522         }
 523
 524       mask = mask->next;
 525     }
 526
 527   return pos[plen].mark;
 528 }