Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (13.8 KB)

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

    
53
    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
    {
82
      put_u32(dst, get_u16(src));
83
      src += 2;
84
      dst += 4;
85
    }
86
  }
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
    {
106
      put_u16(dst, get_u32(src));
107
      src += 4;
108
      dst += 2;
109
    }
110
  }
111

    
112
  return dst - dst0;
113
}
114

    
115
int
116
as_path_contains_as4(const struct adata *path)
117
{
118
  const byte *pos = path->data;
119
  const byte *end = pos + path->length;
120
  uint i, n;
121

    
122
  while (pos < end)
123
  {
124
    n = pos[1];
125
    pos += 2;
126

    
127
    for (i = 0; i < n; i++)
128
    {
129
      if (get_as(pos) > 0xFFFF)
130
        return 1;
131

    
132
      pos += BS;
133
    }
134
  }
135

    
136
  return 0;
137
}
138

    
139
int
140
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
{
234
  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
  u32 as;
239

    
240
  /* Copy the whole path */
241
  memcpy(res->data, path->data, path->length);
242

    
243
  /* 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
    {
251
      as = get_as(pos);
252
      if (as > 0xFFFF)
253
        put_as(pos, AS_TRANS);
254

    
255
      pos += BS;
256
    }
257
  }
258

    
259
  return res;
260
}
261

    
262
/*
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

    
273
  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
    }
287

    
288
    /* 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
}
326

    
327
void
328
as_path_format(const struct adata *path, byte *buf, uint size)
329
{
330
  const byte *p = path->data;
331
  const byte *e = p + path->length;
332
  byte *end = buf + size - 16;
333
  int sp = 1;
334
  int l, isset;
335

    
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
          buf += bsprintf(buf, "%u", get_as(p));
357
          p += BS;
358
          sp = 0;
359
        }
360
      if (isset)
361
        {
362
          *buf++ = ' ';
363
          *buf++ = '}';
364
          sp = 0;
365
        }
366
    }
367
  *buf = 0;
368
}
369

    
370
int
371
as_path_getlen(const struct adata *path)
372
{
373
  const byte *pos = path->data;
374
  const byte *end = pos + path->length;
375
  uint res = 0;
376

    
377
  while (pos < end)
378
  {
379
    uint t = pos[0];
380
    uint l = pos[1];
381
    uint n = 0;
382

    
383
    switch (t)
384
    {
385
    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
    }
391

    
392
    res += n;
393
    pos += 2 + BS * l;
394
  }
395

    
396
  return res;
397
}
398

    
399
int
400
as_path_get_last(const struct adata *path, u32 *orig_as)
401
{
402
  int found = 0;
403
  u32 res = 0;
404
  const u8 *p = path->data;
405
  const u8 *q = p+path->length;
406
  int len;
407

    
408
  while (p<q)
409
    {
410
      switch (*p++)
411
        {
412
        case AS_PATH_SET:
413
          if (len = *p++)
414
            {
415
              found = 0;
416
              p += BS * len;
417
            }
418
          break;
419
        case AS_PATH_SEQUENCE:
420
          if (len = *p++)
421
            {
422
              found = 1;
423
              res = get_as(p + BS * (len - 1));
424
              p += BS * len;
425
            }
426
          break;
427
        default: bug("Invalid path segment");
428
        }
429
    }
430

    
431
  if (found)
432
    *orig_as = res;
433
  return found;
434
}
435

    
436
u32
437
as_path_get_last_nonaggregated(const struct adata *path)
438
{
439
  const u8 *p = path->data;
440
  const u8 *q = p+path->length;
441
  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
int
465
as_path_get_first(const struct adata *path, u32 *last_as)
466
{
467
  const u8 *p = path->data;
468

    
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
as_path_contains(const struct adata *path, u32 as, int min)
480
{
481
  const u8 *p = path->data;
482
  const u8 *q = p+path->length;
483
  int num = 0;
484
  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
            if (++num == min)
494
              return 1;
495
          p += BS;
496
        }
497
    }
498
  return 0;
499
}
500

    
501
int
502
as_path_match_set(const struct adata *path, struct f_tree *set)
503
{
504
  const u8 *p = path->data;
505
  const u8 *q = p+path->length;
506
  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
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
  const u8 *p = path->data;
532
  const u8 *q = path->data + len;
533
  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
  uint nl = d - buf;
577
  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

    
588
struct pm_pos
589
{
590
  u8 set;
591
  u8 mark;
592
  union
593
  {
594
    const char *sp;
595
    u32 asn;
596
  } val;
597
};
598

    
599
static int
600
parse_path(const struct adata *path, struct pm_pos *pos)
601
{
602
  const u8 *p = path->data;
603
  const u8 *q = p + path->length;
604
  struct pm_pos *opos = pos;
605
  int i, len;
606

    
607

    
608
  while (p < q)
609
    switch (*p++)
610
      {
611
      case AS_PATH_SET:
612
        pos->set = 1;
613
        pos->mark = 0;
614
        pos->val.sp = p;
615
        len = *p;
616
        p += 1 + BS * len;
617
        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
            p += BS;
628
            pos++;
629
          }
630
        break;
631

    
632
      default:
633
        bug("as_path_match: Invalid path component");
634
      }
635

    
636
  return pos - opos;
637
}
638

    
639
static int
640
pm_match(struct pm_pos *pos, u32 asn, u32 asn2)
641
{
642
  u32 gas;
643
  if (! pos->set)
644
    return ((pos->val.asn >= asn) && (pos->val.asn <= asn2));
645

    
646
  const u8 *p = pos->val.sp;
647
  int len = *p++;
648
  int i;
649

    
650
  for (i = 0; i < len; i++)
651
  {
652
    gas = get_as(p + i * BS);
653

    
654
    if ((gas >= asn) && (gas <= asn2))
655
      return 1;
656
  }
657

    
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

    
669
  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
 * we process the whole mask, we accept if final position
701
 * (auxiliary position after last real position in AS path)
702
 * is marked.
703
 */
704
int
705
as_path_match(const struct adata *path, struct f_path_mask *mask)
706
{
707
  struct pm_pos pos[2048 + 1];
708
  int plen = parse_path(path, pos);
709
  int l, h, i, nh, nl;
710
  u32 val = 0;
711
  u32 val2 = 0;
712

    
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
        case PM_ASN:        /* Define single ASN as ASN..ASN - very narrow interval */
736
          val2 = val = mask->val;
737
          goto step;
738
        case PM_ASN_EXPR:
739
          val2 = val = f_eval_asn((struct f_inst *) mask->val);
740
          goto step;
741
        case PM_ASN_RANGE:
742
          val = mask->val;
743
          val2 = mask->val2;
744
          goto step;
745
        case PM_QUESTION:
746
        step:
747
          nh = nl = -1;
748
          for (i = h; i >= l; i--)
749
            if (pos[i].mark)
750
              {
751
                pos[i].mark = 0;
752
                if ((mask->kind == PM_QUESTION) || pm_match(pos + i, val, val2))
753
                  pm_mark(pos, i, plen, &nl, &nh);
754
              }
755

    
756
          if (nh < 0)
757
            return 0;
758

    
759
          h = nh;
760
          l = nl;
761
          break;
762
        }
763

    
764
      mask = mask->next;
765
    }
766

    
767
  return pos[plen].mark;
768
}