Statistics
| Branch: | Revision:

iof-bird / bird-2.0.1 / nest / a-path.c @ 6b3f1a54

History | View | Annotate | Download (15.6 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, 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, byte *src, uint len)
81
{
82
  byte *dst0 = dst;
83
  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, byte *src, uint len)
105
{
106
  byte *dst0 = dst;
107
  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
  //log(L_INFO "hello 10.1.confed.1");
155
  const byte *pos = path->data;
156
  const byte *end = pos + path->length;
157

    
158
  //log(L_INFO "hello 10.1.confed.2");
159
  while (pos < end)
160
  {
161
    //log(L_INFO "hello 10.1.confed.3");
162
    uint type = pos[0];
163
    uint slen = 2 + BS * pos[1];
164
    //log(L_INFO "hello 10.1.confed.4");
165
    if ((type == AS_PATH_CONFED_SEQUENCE) ||
166
        (type == AS_PATH_CONFED_SET))
167
      return 1;
168
    //log(L_INFO "hello 10.1.confed.5");
169
    pos += slen;
170
  }
171
  //log(L_INFO "hello 10.1.confed.6");
172
  return 0;
173
}
174

    
175
struct adata *
176
as_path_strip_confed(struct linpool *pool, const struct adata *path)
177
{
178
  //log(L_INFO "hello 10.1.1.confed.1");
179
  struct adata *res = lp_alloc_adata(pool, path->length);
180
  const byte *src = path->data;
181
  const byte *end = src + path->length;
182
  byte *dst = res->data;
183

    
184
  //log(L_INFO "hello 10.1.1.confed.2");
185
  while (src < end)
186
  {
187
    //log(L_INFO "hello 10.1.1.confed.3");
188
    uint type = src[0];
189
    uint slen = 2 + BS * src[1];
190
    //log(L_INFO "hello 10.1.1.confed.4");
191
    /* Copy regular segments */
192
    if ((type == AS_PATH_SET) || (type == AS_PATH_SEQUENCE))
193
    {
194
      //log(L_INFO "hello 10.1.1.confed.5");
195
      memcpy(dst, src, slen);
196
      dst += slen;
197
    }
198
    //log(L_INFO "hello 10.1.1.confed.6");
199
    src += slen;
200
  }
201
  //log(L_INFO "hello 10.1.1.confed.7");
202
  /* Fix the result length */
203
  res->length = dst - res->data;
204

    
205
  return res;
206
}
207

    
208
struct adata *
209
as_path_prepend2(struct linpool *pool, const struct adata *op, int seq, u32 as)
210
{
211
  struct adata *np;
212
  const byte *pos = op->data;
213
  uint len = op->length;
214

    
215
  if (len && (pos[0] == seq) && (pos[1] < 255))
216
  {
217
    /* Starting with matching segment => just prepend the AS number */
218
    np = lp_alloc_adata(pool, len + BS);
219
    np->data[0] = seq;
220
    np->data[1] = pos[1] + 1;
221
    put_as(np->data + 2, as);
222

    
223
    uint dlen = BS * pos[1];
224
    memcpy(np->data + 2 + BS, pos + 2, dlen);
225
    ADVANCE(pos, len, 2 + dlen);
226
  }
227
  else
228
  {
229
    /* Create a new path segment */
230
    np = lp_alloc_adata(pool, len + 2 + BS);
231
    np->data[0] = seq;
232
    np->data[1] = 1;
233
    put_as(np->data + 2, as);
234
  }
235

    
236
  if (len)
237
  {
238
    byte *dst = np->data + 2 + BS * np->data[1];
239

    
240
    memcpy(dst, pos, len);
241
  }
242

    
243
  return np;
244
}
245

    
246

    
247
struct adata *
248
as_path_to_old(struct linpool *pool, const struct adata *path)
249
{
250
  struct adata *res = lp_alloc_adata(pool, path->length);
251
  byte *pos = res->data;
252
  byte *end = pos + res->length;
253
  uint i, n;
254
  u32 as;
255

    
256
  /* Copy the whole path */
257
  memcpy(res->data, path->data, path->length);
258

    
259
  /* Replace 32-bit AS numbers with AS_TRANS */
260
  while (pos < end)
261
  {
262
    n = pos[1];
263
    pos += 2;
264

    
265
    for (i = 0; i < n; i++)
266
    {
267
      as = get_as(pos);
268
      if (as > 0xFFFF)
269
        put_as(pos, AS_TRANS);
270

    
271
      pos += BS;
272
    }
273
  }
274

    
275
  return res;
276
}
277

    
278
/*
279
 * Cut the path to the length @num, measured to the usual path metric. Note that
280
 * AS_CONFED_* segments have zero length and must be added if they are on edge.
281
 * In contrast to other as_path_* functions, @path is modified in place.
282
 */
283
void
284
as_path_cut(struct adata *path, uint num)
285
{
286
  byte *pos = path->data;
287
  byte *end = pos + path->length;
288

    
289
  while (pos < end)
290
  {
291
    uint t = pos[0];
292
    uint l = pos[1];
293
    uint n = 0;
294

    
295
    switch (t)
296
    {
297
    case AS_PATH_SET:                        n = 1; break;
298
    case AS_PATH_SEQUENCE:                n = l; break;
299
    case AS_PATH_CONFED_SEQUENCE:        n = 0; break;
300
    case AS_PATH_CONFED_SET:                n = 0; break;
301
    default: bug("as_path_cut: Invalid path segment");
302
    }
303

    
304
    /* Cannot add whole segment, so try partial one and finish */
305
    if (num < n)
306
    {
307
      if (num)
308
      {
309
        pos[1] = num;
310
        pos += 2 + BS * num;
311
      }
312

    
313
      break;
314
    }
315

    
316
    num -= n;
317
    pos += 2 + BS * l;
318
  }
319

    
320
  path->length = pos - path->data;
321
}
322

    
323
/*
324
 * Merge (concatenate) paths @p1 and @p2 and return the result.
325
 * In contrast to other as_path_* functions, @p1 and @p2 may be reused.
326
 */
327
struct adata *
328
as_path_merge(struct linpool *pool, struct adata *p1, struct adata *p2)
329
{
330
  if (p1->length == 0)
331
    return p2;
332

    
333
  if (p2->length == 0)
334
    return p1;
335

    
336
  struct adata *res = lp_alloc_adata(pool, p1->length + p2->length);
337
  memcpy(res->data, p1->data, p1->length);
338
  memcpy(res->data + p1->length, p2->data, p2->length);
339

    
340
  return res;
341
}
342

    
343
void
344
as_path_format(const struct adata *path, byte *bb, uint size)
345
{
346
  buffer buf = { .start = bb, .pos = bb, .end = bb + size }, *b = &buf;
347
  const byte *pos = path->data;
348
  const byte *end = pos + path->length;
349
  const char *ops, *cls;
350

    
351
  b->pos[0] = 0;
352

    
353
  while (pos < end)
354
  {
355
    uint type = pos[0];
356
    uint len  = pos[1];
357
    pos += 2;
358

    
359
    switch (type)
360
    {
361
    case AS_PATH_SET:                        ops = "{";        cls = "}";        break;
362
    case AS_PATH_SEQUENCE:                ops = NULL;        cls = NULL;        break;
363
    case AS_PATH_CONFED_SEQUENCE:        ops = "(";        cls = ")";        break;
364
    case AS_PATH_CONFED_SET:                ops = "({";        cls = "})";        break;
365
    default: bug("Invalid path segment");
366
    }
367

    
368
    if (ops)
369
      buffer_puts(b, ops);
370

    
371
    while (len--)
372
    {
373
      buffer_print(b, len ? "%u " : "%u", get_as(pos));
374
      pos += BS;
375
    }
376

    
377
    if (cls)
378
      buffer_puts(b, cls);
379

    
380
    if (pos < end)
381
      buffer_puts(b, " ");
382
  }
383

    
384
  /* Handle overflow */
385
  if (b->pos == b->end)
386
    strcpy(b->end - 12, "...");
387
}
388

    
389
int
390
as_path_getlen(const struct adata *path)
391
{
392
  const byte *pos = path->data;
393
  const byte *end = pos + path->length;
394
  uint res = 0;
395

    
396
  while (pos < end)
397
  {
398
    uint t = pos[0];
399
    uint l = pos[1];
400
    uint n = 0;
401

    
402
    switch (t)
403
    {
404
    case AS_PATH_SET:                        n = 1; break;
405
    case AS_PATH_SEQUENCE:                n = l; break;
406
    case AS_PATH_CONFED_SEQUENCE:        n = 0; break;
407
    case AS_PATH_CONFED_SET:                n = 0; break;
408
    default: bug("as_path_getlen: Invalid path segment");
409
    }
410

    
411
    res += n;
412
    pos += 2 + BS * l;
413
  }
414

    
415
  return res;
416
}
417

    
418
int
419
as_path_get_last(const struct adata *path, u32 *orig_as)
420
{
421
  const byte *pos = path->data;
422
  const byte *end = pos + path->length;
423
  int found = 0;
424
  u32 val = 0;
425

    
426
  while (pos < end)
427
  {
428
    uint type = pos[0];
429
    uint len  = pos[1];
430
    pos += 2;
431

    
432
    if (!len)
433
      continue;
434

    
435
    switch (type)
436
    {
437
    case AS_PATH_SET:
438
    case AS_PATH_CONFED_SET:
439
      found = 0;
440
      break;
441

    
442
    case AS_PATH_SEQUENCE:
443
    case AS_PATH_CONFED_SEQUENCE:
444
      val = get_as(pos + BS * (len - 1));
445
      found = 1;
446
      break;
447

    
448
    default:
449
      bug("Invalid path segment");
450
    }
451

    
452
    pos += BS * len;
453
  }
454

    
455
  if (found)
456
    *orig_as = val;
457
  return found;
458
}
459

    
460
u32
461
as_path_get_last_nonaggregated(const struct adata *path)
462
{
463
  const byte *pos = path->data;
464
  const byte *end = pos + path->length;
465
  u32 val = 0;
466

    
467
  while (pos < end)
468
  {
469
    uint type = pos[0];
470
    uint len  = pos[1];
471
    pos += 2;
472

    
473
    if (!len)
474
      continue;
475

    
476
    switch (type)
477
    {
478
    case AS_PATH_SET:
479
    case AS_PATH_CONFED_SET:
480
      return val;
481

    
482
    case AS_PATH_SEQUENCE:
483
    case AS_PATH_CONFED_SEQUENCE:
484
      val = get_as(pos + BS * (len - 1));
485
      break;
486

    
487
    default:
488
      bug("Invalid path segment");
489
    }
490

    
491
    pos += BS * len;
492
  }
493

    
494
  return val;
495
}
496

    
497
int
498
as_path_get_first(const struct adata *path, u32 *last_as)
499
{
500
  const u8 *p = path->data;
501

    
502
  if ((path->length == 0) || (p[0] != AS_PATH_SEQUENCE) || (p[1] == 0))
503
    return 0;
504

    
505
  *last_as = get_as(p+2);
506
  return 1;
507
}
508

    
509
int
510
as_path_get_first_regular(const struct adata *path, u32 *last_as)
511
{
512
  const byte *pos = path->data;
513
  const byte *end = pos + path->length;
514

    
515
  while (pos < end)
516
  {
517
    uint type = pos[0];
518
    uint len  = pos[1];
519
    pos += 2;
520

    
521
    switch (type)
522
    {
523
    case AS_PATH_SET:
524
      return 0;
525

    
526
    case AS_PATH_SEQUENCE:
527
      if (len == 0)
528
        return 0;
529

    
530
      *last_as = get_as(pos);
531
      return 1;
532

    
533
    case AS_PATH_CONFED_SEQUENCE:
534
    case AS_PATH_CONFED_SET:
535
      break;
536

    
537
    default:
538
      bug("Invalid path segment");
539
    }
540

    
541
    pos += BS * len;
542
  }
543

    
544
  return 0;
545
}
546

    
547
int
548
as_path_contains(const struct adata *path, u32 as, int min)
549
{
550
  const u8 *p = path->data;
551
  const u8 *q = p+path->length;
552
  int num = 0;
553
  int i, n;
554

    
555
  while (p<q)
556
    {
557
      n = p[1];
558
      p += 2;
559
      for(i=0; i<n; i++)
560
        {
561
          if (get_as(p) == as)
562
            if (++num == min)
563
              return 1;
564
          p += BS;
565
        }
566
    }
567
  return 0;
568
}
569

    
570
int
571
as_path_match_set(const struct adata *path, struct f_tree *set)
572
{
573
  const u8 *p = path->data;
574
  const u8 *q = p+path->length;
575
  int i, n;
576

    
577
  while (p<q)
578
    {
579
      n = p[1];
580
      p += 2;
581
      for (i=0; i<n; i++)
582
        {
583
          struct f_val v = {T_INT, .val.i = get_as(p)};
584
          if (find_tree(set, v))
585
            return 1;
586
          p += BS;
587
        }
588
    }
589

    
590
  return 0;
591
}
592

    
593
struct adata *
594
as_path_filter(struct linpool *pool, struct adata *path, struct f_tree *set, u32 key, int pos)
595
{
596
  if (!path)
597
    return NULL;
598

    
599
  int len = path->length;
600
  const u8 *p = path->data;
601
  const u8 *q = path->data + len;
602
  u8 *d, *d2;
603
  int i, bt, sn, dn;
604
  u8 buf[len];
605

    
606
  d = buf;
607
  while (p<q)
608
    {
609
      /* Read block header (type and length) */
610
      bt = p[0];
611
      sn = p[1];
612
      dn = 0;
613
      p += 2;
614
      d2 = d + 2;
615

    
616
      for (i = 0; i < sn; i++)
617
        {
618
          u32 as = get_as(p);
619
          int match;
620

    
621
          if (set)
622
            match = !!find_tree(set, (struct f_val){T_INT, .val.i = as});
623
          else
624
            match = (as == key);
625

    
626
          if (match == pos)
627
            {
628
              put_as(d2, as);
629
              d2 += BS;
630
              dn++;
631
            }
632

    
633
          p += BS;
634
        }
635

    
636
      if (dn > 0)
637
        {
638
          /* Nonempty block, set block header and advance */
639
          d[0] = bt;
640
          d[1] = dn;
641
          d = d2;
642
        }
643
  }
644

    
645
  uint nl = d - buf;
646
  if (nl == path->length)
647
    return path;
648

    
649
  struct adata *res = lp_alloc(pool, sizeof(struct adata) + nl);
650
  res->length = nl;
651
  memcpy(res->data, buf, nl);
652

    
653
  return res;
654
}
655

    
656

    
657
struct pm_pos
658
{
659
  u8 set;
660
  u8 mark;
661
  union
662
  {
663
    const char *sp;
664
    u32 asn;
665
  } val;
666
};
667

    
668
static int
669
parse_path(const struct adata *path, struct pm_pos *pp)
670
{
671
  const byte *pos = path->data;
672
  const byte *end = pos + path->length;
673
  struct pm_pos *op = pp;
674
  uint i;
675

    
676
  while (pos < end)
677
  {
678
    uint type = pos[0];
679
    uint len  = pos[1];
680
    pos += 2;
681

    
682
    switch (type)
683
    {
684
    case AS_PATH_SET:
685
    case AS_PATH_CONFED_SET:
686
      pp->set = 1;
687
      pp->mark = 0;
688
      pp->val.sp = pos - 1;
689
      pp++;
690

    
691
      pos += BS * len;
692
      break;
693

    
694
    case AS_PATH_SEQUENCE:
695
    case AS_PATH_CONFED_SEQUENCE:
696
      for (i = 0; i < len; i++)
697
      {
698
        pp->set = 0;
699
        pp->mark = 0;
700
        pp->val.asn = get_as(pos);
701
        pp++;
702

    
703
        pos += BS;
704
      }
705
      break;
706

    
707
    default:
708
      bug("Invalid path segment");
709
    }
710
  }
711

    
712
  return pp - op;
713
}
714

    
715
static int
716
pm_match(struct pm_pos *pos, u32 asn, u32 asn2)
717
{
718
  u32 gas;
719
  if (! pos->set)
720
    return ((pos->val.asn >= asn) && (pos->val.asn <= asn2));
721

    
722
  const u8 *p = pos->val.sp;
723
  int len = *p++;
724
  int i;
725

    
726
  for (i = 0; i < len; i++)
727
  {
728
    gas = get_as(p + i * BS);
729

    
730
    if ((gas >= asn) && (gas <= asn2))
731
      return 1;
732
  }
733

    
734
  return 0;
735
}
736

    
737
static void
738
pm_mark(struct pm_pos *pos, int i, int plen, int *nl, int *nh)
739
{
740
  int j;
741

    
742
  if (pos[i].set)
743
    pos[i].mark = 1;
744

    
745
  for (j = i + 1; (j < plen) && pos[j].set && (! pos[j].mark); j++)
746
    pos[j].mark = 1;
747
  pos[j].mark = 1;
748

    
749
  /* We are going downwards, therefore every mark is
750
     new low and just the first mark is new high */
751

    
752
  *nl = i + (pos[i].set ? 0 : 1);
753

    
754
  if (*nh < 0)
755
    *nh = j;
756
}
757

    
758
/* AS path matching is nontrivial. Because AS path can
759
 * contain sets, it is not a plain wildcard matching. A set
760
 * in an AS path is interpreted as it might represent any
761
 * sequence of AS numbers from that set (possibly with
762
 * repetitions). So it is also a kind of a pattern,
763
 * more complicated than a path mask.
764
 *
765
 * The algorithm for AS path matching is a variant
766
 * of nondeterministic finite state machine, where
767
 * positions in AS path are states, and items in
768
 * path mask are input for that finite state machine.
769
 * During execution of the algorithm we maintain a set
770
 * of marked states - a state is marked if it can be
771
 * reached by any walk through NFSM with regard to
772
 * currently processed part of input. When we process
773
 * next part of mask, we advance each marked state.
774
 * We start with marked first position, when we
775
 * run out of marked positions, we reject. When
776
 * we process the whole mask, we accept if final position
777
 * (auxiliary position after last real position in AS path)
778
 * is marked.
779
 */
780
int
781
as_path_match(const struct adata *path, struct f_path_mask *mask)
782
{
783
  struct pm_pos pos[2048 + 1];
784
  int plen = parse_path(path, pos);
785
  int l, h, i, nh, nl;
786
  u32 val = 0;
787
  u32 val2 = 0;
788

    
789
  /* l and h are bound of interval of positions where
790
     are marked states */
791

    
792
  pos[plen].set = 0;
793
  pos[plen].mark = 0;
794

    
795
  l = h = 0;
796
  pos[0].mark = 1;
797

    
798
  while (mask)
799
    {
800
      /* We remove this mark to not step after pos[plen] */
801
      pos[plen].mark = 0;
802

    
803
      switch (mask->kind)
804
        {
805
        case PM_ASTERISK:
806
          for (i = l; i <= plen; i++)
807
            pos[i].mark = 1;
808
          h = plen;
809
          break;
810

    
811
        case PM_ASN:        /* Define single ASN as ASN..ASN - very narrow interval */
812
          val2 = val = mask->val;
813
          goto step;
814
        case PM_ASN_EXPR:
815
          val2 = val = f_eval_asn((struct f_inst *) mask->val);
816
          goto step;
817
        case PM_ASN_RANGE:
818
          val = mask->val;
819
          val2 = mask->val2;
820
          goto step;
821
        case PM_QUESTION:
822
        step:
823
          nh = nl = -1;
824
          for (i = h; i >= l; i--)
825
            if (pos[i].mark)
826
              {
827
                pos[i].mark = 0;
828
                if ((mask->kind == PM_QUESTION) || pm_match(pos + i, val, val2))
829
                  pm_mark(pos, i, plen, &nl, &nh);
830
              }
831

    
832
          if (nh < 0)
833
            return 0;
834

    
835
          h = nh;
836
          l = nl;
837
          break;
838
        }
839

    
840
      mask = mask->next;
841
    }
842

    
843
  return pos[plen].mark;
844
}