Statistics
| Branch: | Revision:

iof-bird-daemon / nest / a-path.c @ 62e64905

History | View | Annotate | Download (13.8 KB)

1 c0668f36 Martin Mares
/*
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 c6add07f Martin Mares
#include "nest/attrs.h"
13 c0668f36 Martin Mares
#include "lib/resource.h"
14
#include "lib/unaligned.h"
15 c6add07f Martin Mares
#include "lib/string.h"
16 05198c12 Ondrej Zajicek
#include "filter/filter.h"
17 c0668f36 Martin Mares
18 43c1cecc Ondrej Zajicek
// 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 11cb6202 Ondrej Zajicek
21 43c1cecc Ondrej Zajicek
#define put_as put_u32
22
#define get_as get_u32
23 0eb7f17d Pavel Tvrdik
#define BS  4        /* Default block size of ASN (autonomous system number) */
24 11cb6202 Ondrej Zajicek
25 d15b0b0a Ondrej Zajicek (work)
#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, char *err, uint elen)
29 c0668f36 Martin Mares
{
30 d15b0b0a Ondrej Zajicek (work)
  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
    /* XXXX handle CONFED segments */
47
    if ((type != AS_PATH_SET) && (type != AS_PATH_SEQUENCE))
48
      BAD("unknown segment", type);
49
50
    if (pos[1] == 0)
51
      BAD("zero-length segment", type);
52 c0668f36 Martin Mares
53 d15b0b0a Ondrej Zajicek (work)
    pos += slen;
54
    len -= slen;
55
  }
56
57
  return 1;
58
59
bad:
60
  if (err)
61
    if (bsnprintf(err, elen, "%s (%u) at %d", err_dsc, err_val, (int) (pos - data)) < 0)
62
      err[0] = 0;
63
64
  return 0;
65
}
66
67
int
68
as_path_16to32(byte *dst, byte *src, uint len)
69
{
70
  byte *dst0 = dst;
71
  byte *end = src + len;
72
  uint i, n;
73
74
  while (src < end)
75
  {
76
    n = src[1];
77
    *dst++ = *src++;
78
    *dst++ = *src++;
79
80
    for (i = 0; i < n; i++)
81 c0668f36 Martin Mares
    {
82 d15b0b0a Ondrej Zajicek (work)
      put_u32(dst, get_u16(src));
83
      src += 2;
84
      dst += 4;
85 c0668f36 Martin Mares
    }
86 d15b0b0a Ondrej Zajicek (work)
  }
87
88
  return dst - dst0;
89
}
90
91
int
92
as_path_32to16(byte *dst, byte *src, uint len)
93
{
94
  byte *dst0 = dst;
95
  byte *end = src + len;
96
  uint i, n;
97
98
  while (src < end)
99
  {
100
    n = src[1];
101
    *dst++ = *src++;
102
    *dst++ = *src++;
103
104
    for (i = 0; i < n; i++)
105 c0668f36 Martin Mares
    {
106 d15b0b0a Ondrej Zajicek (work)
      put_u16(dst, get_u32(src));
107
      src += 4;
108
      dst += 2;
109 c0668f36 Martin Mares
    }
110 d15b0b0a Ondrej Zajicek (work)
  }
111
112
  return dst - dst0;
113 c0668f36 Martin Mares
}
114 c6add07f Martin Mares
115 11cb6202 Ondrej Zajicek
int
116 d15b0b0a Ondrej Zajicek (work)
as_path_contains_as4(const struct adata *path)
117 11cb6202 Ondrej Zajicek
{
118 d15b0b0a Ondrej Zajicek (work)
  const byte *pos = path->data;
119
  const byte *end = pos + path->length;
120
  uint i, n;
121 11cb6202 Ondrej Zajicek
122 d15b0b0a Ondrej Zajicek (work)
  while (pos < end)
123
  {
124
    n = pos[1];
125
    pos += 2;
126
127
    for (i = 0; i < n; i++)
128 11cb6202 Ondrej Zajicek
    {
129 d15b0b0a Ondrej Zajicek (work)
      if (get_as(pos) > 0xFFFF)
130
        return 1;
131 11cb6202 Ondrej Zajicek
132 d15b0b0a Ondrej Zajicek (work)
      pos += BS;
133 11cb6202 Ondrej Zajicek
    }
134 d15b0b0a Ondrej Zajicek (work)
  }
135 11cb6202 Ondrej Zajicek
136 d15b0b0a Ondrej Zajicek (work)
  return 0;
137 11cb6202 Ondrej Zajicek
}
138
139
int
140 d15b0b0a Ondrej Zajicek (work)
as_path_contains_confed(const struct adata *path)
141
{
142
  const byte *pos = path->data;
143
  const byte *end = pos + path->length;
144
145
  while (pos < end)
146
  {
147
    uint type = pos[0];
148
    uint slen = 2 + BS * pos[1];
149
150
    if ((type == AS_PATH_CONFED_SEQUENCE) ||
151
        (type == AS_PATH_CONFED_SET))
152
      return 1;
153
154
    pos += slen;
155
  }
156
157
  return 0;
158
}
159
160
static void
161
as_path_strip_confed_(byte *dst, const byte *src, uint len)
162
{
163
  const byte *end = src + len;
164
165
  while (src < end)
166
  {
167
    uint type = src[0];
168
    uint slen = 2 + BS * src[1];
169
170
    /* Copy regular segments */
171
    if ((type == AS_PATH_SET) || (type == AS_PATH_SEQUENCE))
172
    {
173
      memcpy(dst, src, slen);
174
      dst += slen;
175
    }
176
177
    src += slen;
178
  }
179
}
180
181
struct adata *
182
as_path_strip_confed(struct linpool *pool, const struct adata *op)
183
{
184
  struct adata *np = lp_alloc_adata(pool, op->length);
185
  as_path_strip_confed_(np->data, op->data, op->length);
186
  return np;
187
}
188
189
struct adata *
190
as_path_prepend2(struct linpool *pool, const struct adata *op, int seq, u32 as, int strip)
191
{
192
  struct adata *np;
193
  const byte *pos = op->data;
194
  uint len = op->length;
195
196
  if (len && (pos[0] == seq) && (pos[1] < 255))
197
  {
198
    /* Starting with matching segment => just prepend the AS number */
199
    np = lp_alloc_adata(pool, len + BS);
200
    np->data[0] = seq;
201
    np->data[1] = pos[1] + 1;
202
    put_as(np->data + 2, as);
203
204
    uint dlen = BS * pos[1];
205
    memcpy(np->data + 2 + BS, pos + 2, dlen);
206
    ADVANCE(pos, len, 2 + dlen);
207
  }
208
  else
209
  {
210
    /* Create a new path segment */
211
    np = lp_alloc_adata(pool, len + 2 + BS);
212
    np->data[0] = seq;
213
    np->data[1] = 1;
214
    put_as(np->data + 2, as);
215
  }
216
217
  if (len)
218
  {
219
    byte *dst = np->data + 2 + BS * np->data[1];
220
221
    if (strip)
222
      as_path_strip_confed_(dst, pos, len);
223
    else
224
      memcpy(dst, pos, len);
225
  }
226
227
  return np;
228
}
229
230
231
struct adata *
232
as_path_to_old(struct linpool *pool, const struct adata *path)
233 11cb6202 Ondrej Zajicek
{
234 d15b0b0a Ondrej Zajicek (work)
  struct adata *res = lp_alloc_adata(pool, path->length);
235
  byte *pos = res->data;
236
  byte *end = pos + res->length;
237
  uint i, n;
238 11cb6202 Ondrej Zajicek
  u32 as;
239
240 d15b0b0a Ondrej Zajicek (work)
  /* Copy the whole path */
241
  memcpy(res->data, path->data, path->length);
242 11cb6202 Ondrej Zajicek
243 d15b0b0a Ondrej Zajicek (work)
  /* Replace 32-bit AS numbers with AS_TRANS */
244
  while (pos < end)
245
  {
246
    n = pos[1];
247
    pos += 2;
248
249
    for (i = 0; i < n; i++)
250 11cb6202 Ondrej Zajicek
    {
251 d15b0b0a Ondrej Zajicek (work)
      as = get_as(pos);
252
      if (as > 0xFFFF)
253
        put_as(pos, AS_TRANS);
254 11cb6202 Ondrej Zajicek
255 d15b0b0a Ondrej Zajicek (work)
      pos += BS;
256
    }
257
  }
258 11cb6202 Ondrej Zajicek
259 d15b0b0a Ondrej Zajicek (work)
  return res;
260
}
261 11cb6202 Ondrej Zajicek
262 d15b0b0a Ondrej Zajicek (work)
/*
263
 * Cut the path to the length @num, measured to the usual path metric. Note that
264
 * AS_CONFED_* segments have zero length and must be added if they are on edge.
265
 * In contrast to other as_path_* functions, @path is modified in place.
266
 */
267
void
268
as_path_cut(struct adata *path, uint num)
269
{
270
  byte *pos = path->data;
271
  byte *end = pos + path->length;
272 11cb6202 Ondrej Zajicek
273 d15b0b0a Ondrej Zajicek (work)
  while (pos < end)
274
  {
275
    uint t = pos[0];
276
    uint l = pos[1];
277
    uint n = 0;
278
279
    switch (t)
280
    {
281
    case AS_PATH_SET:                        n = 1; break;
282
    case AS_PATH_SEQUENCE:                n = l; break;
283
    case AS_PATH_CONFED_SEQUENCE:        n = 0; break;
284
    case AS_PATH_CONFED_SET:                n = 0; break;
285
    default: bug("as_path_cut: Invalid path segment");
286 11cb6202 Ondrej Zajicek
    }
287
288 d15b0b0a Ondrej Zajicek (work)
    /* Cannot add whole segment, so try partial one and finish */
289
    if (num < n)
290
    {
291
      if (num)
292
      {
293
        pos[1] = num;
294
        pos += 2 + BS * num;
295
      }
296
297
      break;
298
    }
299
300
    num -= n;
301
    pos += 2 + BS * l;
302
  }
303
304
  path->length = pos - path->data;
305
}
306
307
/*
308
 * Merge (concatenate) paths @p1 and @p2 and return the result.
309
 * In contrast to other as_path_* functions, @p1 and @p2 may be reused.
310
 */
311
struct adata *
312
as_path_merge(struct linpool *pool, struct adata *p1, struct adata *p2)
313
{
314
  if (p1->length == 0)
315
    return p2;
316
317
  if (p2->length == 0)
318
    return p1;
319
320
  struct adata *res = lp_alloc_adata(pool, p1->length + p2->length);
321
  memcpy(res->data, p1->data, p1->length);
322
  memcpy(res->data + p1->length, p2->data, p2->length);
323
324
  return res;
325 11cb6202 Ondrej Zajicek
}
326
327 c6add07f Martin Mares
void
328 d15b0b0a Ondrej Zajicek (work)
as_path_format(const struct adata *path, byte *buf, uint size)
329 c6add07f Martin Mares
{
330 d15b0b0a Ondrej Zajicek (work)
  const byte *p = path->data;
331
  const byte *e = p + path->length;
332 11cb6202 Ondrej Zajicek
  byte *end = buf + size - 16;
333 c6add07f Martin Mares
  int sp = 1;
334 93a786cb Martin Mares
  int l, isset;
335 c6add07f Martin Mares
336
  while (p < e)
337
    {
338
      if (buf > end)
339
        {
340
          strcpy(buf, " ...");
341
          return;
342
        }
343
      isset = (*p++ == AS_PATH_SET);
344
      l = *p++;
345
      if (isset)
346
        {
347
          if (!sp)
348
            *buf++ = ' ';
349
          *buf++ = '{';
350
          sp = 0;
351
        }
352
      while (l-- && buf <= end)
353
        {
354
          if (!sp)
355
            *buf++ = ' ';
356 11cb6202 Ondrej Zajicek
          buf += bsprintf(buf, "%u", get_as(p));
357 43c1cecc Ondrej Zajicek
          p += BS;
358 c6add07f Martin Mares
          sp = 0;
359
        }
360
      if (isset)
361
        {
362
          *buf++ = ' ';
363
          *buf++ = '}';
364
          sp = 0;
365
        }
366
    }
367
  *buf = 0;
368
}
369 684c6f5a Pavel Machek
370
int
371 d15b0b0a Ondrej Zajicek (work)
as_path_getlen(const struct adata *path)
372 684c6f5a Pavel Machek
{
373 d15b0b0a Ondrej Zajicek (work)
  const byte *pos = path->data;
374
  const byte *end = pos + path->length;
375
  uint res = 0;
376 949bd34e Ondrej Zajicek
377 d15b0b0a Ondrej Zajicek (work)
  while (pos < end)
378
  {
379
    uint t = pos[0];
380
    uint l = pos[1];
381
    uint n = 0;
382 684c6f5a Pavel Machek
383 d15b0b0a Ondrej Zajicek (work)
    switch (t)
384 4b03f64b Martin Mares
    {
385 d15b0b0a Ondrej Zajicek (work)
    case AS_PATH_SET:                        n = 1; break;
386
    case AS_PATH_SEQUENCE:                n = l; break;
387
    case AS_PATH_CONFED_SEQUENCE:        n = 0; break;
388
    case AS_PATH_CONFED_SET:                n = 0; break;
389
    default: bug("as_path_getlen: Invalid path segment");
390 684c6f5a Pavel Machek
    }
391 d15b0b0a Ondrej Zajicek (work)
392
    res += n;
393
    pos += 2 + BS * l;
394
  }
395
396 684c6f5a Pavel Machek
  return res;
397
}
398 2a40efa5 Pavel Machek
399 f49528a3 Martin Mares
int
400 d15b0b0a Ondrej Zajicek (work)
as_path_get_last(const struct adata *path, u32 *orig_as)
401 f49528a3 Martin Mares
{
402 11cb6202 Ondrej Zajicek
  int found = 0;
403
  u32 res = 0;
404 d15b0b0a Ondrej Zajicek (work)
  const u8 *p = path->data;
405
  const u8 *q = p+path->length;
406 f49528a3 Martin Mares
  int len;
407
408
  while (p<q)
409
    {
410
      switch (*p++)
411
        {
412
        case AS_PATH_SET:
413
          if (len = *p++)
414 11cb6202 Ondrej Zajicek
            {
415 52b9b2a1 Ondrej Zajicek
              found = 0;
416 43c1cecc Ondrej Zajicek
              p += BS * len;
417 11cb6202 Ondrej Zajicek
            }
418 f49528a3 Martin Mares
          break;
419
        case AS_PATH_SEQUENCE:
420
          if (len = *p++)
421 11cb6202 Ondrej Zajicek
            {
422
              found = 1;
423 43c1cecc Ondrej Zajicek
              res = get_as(p + BS * (len - 1));
424
              p += BS * len;
425 11cb6202 Ondrej Zajicek
            }
426 f49528a3 Martin Mares
          break;
427 9c9cc35c Ondrej Zajicek (work)
        default: bug("Invalid path segment");
428 f49528a3 Martin Mares
        }
429
    }
430 11cb6202 Ondrej Zajicek
431 52b9b2a1 Ondrej Zajicek
  if (found)
432
    *orig_as = res;
433 11cb6202 Ondrej Zajicek
  return found;
434 f49528a3 Martin Mares
}
435
436 9c9cc35c Ondrej Zajicek (work)
u32
437 d15b0b0a Ondrej Zajicek (work)
as_path_get_last_nonaggregated(const struct adata *path)
438 9c9cc35c Ondrej Zajicek (work)
{
439 d15b0b0a Ondrej Zajicek (work)
  const u8 *p = path->data;
440
  const u8 *q = p+path->length;
441 9c9cc35c Ondrej Zajicek (work)
  u32 res = 0;
442
  int len;
443
444
  while (p<q)
445
    {
446
      switch (*p++)
447
        {
448
        case AS_PATH_SET:
449
          return res;
450
451
        case AS_PATH_SEQUENCE:
452
          if (len = *p++)
453
            res = get_as(p + BS * (len - 1));
454
          p += BS * len;
455
          break;
456
457
        default: bug("Invalid path segment");
458
        }
459
    }
460
461
  return res;
462
}
463
464 11cb6202 Ondrej Zajicek
int
465 d15b0b0a Ondrej Zajicek (work)
as_path_get_first(const struct adata *path, u32 *last_as)
466 b6bf284a Ondrej Zajicek
{
467 d15b0b0a Ondrej Zajicek (work)
  const u8 *p = path->data;
468 b6bf284a Ondrej Zajicek
469
  if ((path->length == 0) || (p[0] != AS_PATH_SEQUENCE) || (p[1] == 0))
470
    return 0;
471
  else
472
    {
473
      *last_as = get_as(p+2);
474
      return 1;
475
    }
476
}
477
478
int
479 d15b0b0a Ondrej Zajicek (work)
as_path_contains(const struct adata *path, u32 as, int min)
480 11cb6202 Ondrej Zajicek
{
481 d15b0b0a Ondrej Zajicek (work)
  const u8 *p = path->data;
482
  const u8 *q = p+path->length;
483 a15dab76 Ondrej Zajicek
  int num = 0;
484 11cb6202 Ondrej Zajicek
  int i, n;
485
486
  while (p<q)
487
    {
488
      n = p[1];
489
      p += 2;
490
      for(i=0; i<n; i++)
491
        {
492
          if (get_as(p) == as)
493 a15dab76 Ondrej Zajicek
            if (++num == min)
494
              return 1;
495 43c1cecc Ondrej Zajicek
          p += BS;
496 11cb6202 Ondrej Zajicek
        }
497
    }
498
  return 0;
499
}
500
501 cc31b75a Ondrej Zajicek
int
502 d15b0b0a Ondrej Zajicek (work)
as_path_match_set(const struct adata *path, struct f_tree *set)
503 cc31b75a Ondrej Zajicek
{
504 d15b0b0a Ondrej Zajicek (work)
  const u8 *p = path->data;
505
  const u8 *q = p+path->length;
506 cc31b75a Ondrej Zajicek
  int i, n;
507
508
  while (p<q)
509
    {
510
      n = p[1];
511
      p += 2;
512
      for (i=0; i<n; i++)
513
        {
514
          struct f_val v = {T_INT, .val.i = get_as(p)};
515
          if (find_tree(set, v))
516
            return 1;
517
          p += BS;
518
        }
519
    }
520
521
  return 0;
522
}
523
524 bff9ce51 Ondrej Zajicek
struct adata *
525
as_path_filter(struct linpool *pool, struct adata *path, struct f_tree *set, u32 key, int pos)
526
{
527
  if (!path)
528
    return NULL;
529
530
  int len = path->length;
531 d15b0b0a Ondrej Zajicek (work)
  const u8 *p = path->data;
532
  const u8 *q = path->data + len;
533 bff9ce51 Ondrej Zajicek
  u8 *d, *d2;
534
  int i, bt, sn, dn;
535
  u8 buf[len];
536
537
  d = buf;
538
  while (p<q)
539
    {
540
      /* Read block header (type and length) */
541
      bt = p[0];
542
      sn = p[1];
543
      dn = 0;
544
      p += 2;
545
      d2 = d + 2;
546
547
      for (i = 0; i < sn; i++)
548
        {
549
          u32 as = get_as(p);
550
          int match;
551
552
          if (set)
553
            match = !!find_tree(set, (struct f_val){T_INT, .val.i = as});
554
          else
555
            match = (as == key);
556
557
          if (match == pos)
558
            {
559
              put_as(d2, as);
560
              d2 += BS;
561
              dn++;
562
            }
563
564
          p += BS;
565
        }
566
567
      if (dn > 0)
568
        {
569
          /* Nonempty block, set block header and advance */
570
          d[0] = bt;
571
          d[1] = dn;
572
          d = d2;
573
        }
574
  }
575
576 3e236955 Jan Moskyto Matejka
  uint nl = d - buf;
577 bff9ce51 Ondrej Zajicek
  if (nl == path->length)
578
    return path;
579
580
  struct adata *res = lp_alloc(pool, sizeof(struct adata) + nl);
581
  res->length = nl;
582
  memcpy(res->data, buf, nl);
583
584
  return res;
585
}
586
587 11cb6202 Ondrej Zajicek
588 c8a6b9a3 Ondrej Zajicek
struct pm_pos
589
{
590
  u8 set;
591
  u8 mark;
592
  union
593
  {
594 d15b0b0a Ondrej Zajicek (work)
    const char *sp;
595 c8a6b9a3 Ondrej Zajicek
    u32 asn;
596
  } val;
597
};
598
599
static int
600 d15b0b0a Ondrej Zajicek (work)
parse_path(const struct adata *path, struct pm_pos *pos)
601 2a40efa5 Pavel Machek
{
602 d15b0b0a Ondrej Zajicek (work)
  const u8 *p = path->data;
603
  const u8 *q = p + path->length;
604 c8a6b9a3 Ondrej Zajicek
  struct pm_pos *opos = pos;
605 05198c12 Ondrej Zajicek
  int i, len;
606 2a40efa5 Pavel Machek
607 25cb9f1d Ondrej Zajicek
608 c8a6b9a3 Ondrej Zajicek
  while (p < q)
609
    switch (*p++)
610 2a40efa5 Pavel Machek
      {
611 c8a6b9a3 Ondrej Zajicek
      case AS_PATH_SET:
612
        pos->set = 1;
613
        pos->mark = 0;
614
        pos->val.sp = p;
615
        len = *p;
616 43c1cecc Ondrej Zajicek
        p += 1 + BS * len;
617 c8a6b9a3 Ondrej Zajicek
        pos++;
618
        break;
619
      
620
      case AS_PATH_SEQUENCE:
621
        len = *p++;
622
        for (i = 0; i < len; i++)
623
          {
624
            pos->set = 0;
625
            pos->mark = 0;
626
            pos->val.asn = get_as(p);
627 43c1cecc Ondrej Zajicek
            p += BS;
628 c8a6b9a3 Ondrej Zajicek
            pos++;
629 2a40efa5 Pavel Machek
          }
630 c8a6b9a3 Ondrej Zajicek
        break;
631
632
      default:
633
        bug("as_path_match: Invalid path component");
634 2a40efa5 Pavel Machek
      }
635 d15b0b0a Ondrej Zajicek (work)
636 c8a6b9a3 Ondrej Zajicek
  return pos - opos;
637
}
638
639
static int
640 a0fe1944 Ondrej Filip
pm_match(struct pm_pos *pos, u32 asn, u32 asn2)
641 c8a6b9a3 Ondrej Zajicek
{
642 a0fe1944 Ondrej Filip
  u32 gas;
643 c8a6b9a3 Ondrej Zajicek
  if (! pos->set)
644 a0fe1944 Ondrej Filip
    return ((pos->val.asn >= asn) && (pos->val.asn <= asn2));
645 c8a6b9a3 Ondrej Zajicek
646 d15b0b0a Ondrej Zajicek (work)
  const u8 *p = pos->val.sp;
647 c8a6b9a3 Ondrej Zajicek
  int len = *p++;
648
  int i;
649
650
  for (i = 0; i < len; i++)
651 a0fe1944 Ondrej Filip
  {
652
    gas = get_as(p + i * BS);
653
654
    if ((gas >= asn) && (gas <= asn2))
655 c8a6b9a3 Ondrej Zajicek
      return 1;
656 a0fe1944 Ondrej Filip
  }
657 c8a6b9a3 Ondrej Zajicek
658
  return 0;
659
}
660
661
static void
662
pm_mark(struct pm_pos *pos, int i, int plen, int *nl, int *nh)
663
{
664
  int j;
665
666
  if (pos[i].set)
667
    pos[i].mark = 1;
668 d15b0b0a Ondrej Zajicek (work)
669 c8a6b9a3 Ondrej Zajicek
  for (j = i + 1; (j < plen) && pos[j].set && (! pos[j].mark); j++)
670
    pos[j].mark = 1;
671
  pos[j].mark = 1;
672
673
  /* We are going downwards, therefore every mark is
674
     new low and just the first mark is new high */
675
676
  *nl = i + (pos[i].set ? 0 : 1);
677
678
  if (*nh < 0)
679
    *nh = j;
680
}
681
682
/* AS path matching is nontrivial. Because AS path can
683
 * contain sets, it is not a plain wildcard matching. A set 
684
 * in an AS path is interpreted as it might represent any
685
 * sequence of AS numbers from that set (possibly with
686
 * repetitions). So it is also a kind of a pattern,
687
 * more complicated than a path mask.
688
 *
689
 * The algorithm for AS path matching is a variant
690
 * of nondeterministic finite state machine, where
691
 * positions in AS path are states, and items in
692
 * path mask are input for that finite state machine.
693
 * During execution of the algorithm we maintain a set
694
 * of marked states - a state is marked if it can be
695
 * reached by any walk through NFSM with regard to
696
 * currently processed part of input. When we process
697
 * next part of mask, we advance each marked state.
698
 * We start with marked first position, when we
699
 * run out of marked positions, we reject. When
700 a0fe1944 Ondrej Filip
 * we process the whole mask, we accept if final position
701 c8a6b9a3 Ondrej Zajicek
 * (auxiliary position after last real position in AS path)
702
 * is marked.
703
 */
704
int
705 d15b0b0a Ondrej Zajicek (work)
as_path_match(const struct adata *path, struct f_path_mask *mask)
706 c8a6b9a3 Ondrej Zajicek
{
707
  struct pm_pos pos[2048 + 1];
708
  int plen = parse_path(path, pos);
709
  int l, h, i, nh, nl;
710 e81b440f Ondrej Zajicek
  u32 val = 0;
711 a0fe1944 Ondrej Filip
  u32 val2 = 0;
712 c8a6b9a3 Ondrej Zajicek
713
  /* l and h are bound of interval of positions where
714
     are marked states */
715
716
  pos[plen].set = 0;
717
  pos[plen].mark = 0;
718
719
  l = h = 0;
720
  pos[0].mark = 1;
721
  
722
  while (mask)
723
    {
724
      /* We remove this mark to not step after pos[plen] */
725
      pos[plen].mark = 0;
726
727
      switch (mask->kind)
728
        {
729
        case PM_ASTERISK:
730
          for (i = l; i <= plen; i++)
731
            pos[i].mark = 1;
732
          h = plen;
733
          break;
734
735 a0fe1944 Ondrej Filip
        case PM_ASN:        /* Define single ASN as ASN..ASN - very narrow interval */
736
          val2 = val = mask->val;
737 92a72a4c Ondrej Zajicek
          goto step;
738
        case PM_ASN_EXPR:
739 a0fe1944 Ondrej Filip
          val2 = val = f_eval_asn((struct f_inst *) mask->val);
740 92a72a4c Ondrej Zajicek
          goto step;
741 a0fe1944 Ondrej Filip
        case PM_ASN_RANGE:
742
          val = mask->val;
743
          val2 = mask->val2;
744
          goto step;
745 92a72a4c Ondrej Zajicek
        case PM_QUESTION:
746
        step:
747 e81b440f Ondrej Zajicek
          nh = nl = -1;
748 c8a6b9a3 Ondrej Zajicek
          for (i = h; i >= l; i--)
749
            if (pos[i].mark)
750
              {
751
                pos[i].mark = 0;
752 a0fe1944 Ondrej Filip
                if ((mask->kind == PM_QUESTION) || pm_match(pos + i, val, val2))
753 c8a6b9a3 Ondrej Zajicek
                  pm_mark(pos, i, plen, &nl, &nh);
754
              }
755
756
          if (nh < 0)
757 2a40efa5 Pavel Machek
            return 0;
758 c8a6b9a3 Ondrej Zajicek
759
          h = nh;
760
          l = nl;
761
          break;
762 2a40efa5 Pavel Machek
        }
763
764 c8a6b9a3 Ondrej Zajicek
      mask = mask->next;
765 2a40efa5 Pavel Machek
    }
766 98347659 Pavel Machek
767 c8a6b9a3 Ondrej Zajicek
  return pos[plen].mark;
768
}