Statistics
| Branch: | Revision:

iof-bird-daemon / nest / a-path.c @ 9b0a0ba9

History | View | Annotate | Download (10 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 /* Base (default) size of ASN (autonomous system number) */
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
int
503
as_path_match(struct adata *path, struct f_path_mask *mask)
504
{
505
  struct pm_pos pos[2048 + 1];
506
  int plen = parse_path(path, pos);
507
  int l, h, i, nh, nl;
508
  u32 val = 0;
509
  u32 val2 = 0;
510

    
511
  /* l and h are bound of interval of positions where
512
     are marked states */
513

    
514
  pos[plen].set = 0;
515
  pos[plen].mark = 0;
516

    
517
  l = h = 0;
518
  pos[0].mark = 1;
519
  
520
  while (mask)
521
    {
522
      /* We remove this mark to not step after pos[plen] */
523
      pos[plen].mark = 0;
524

    
525
      switch (mask->kind)
526
        {
527
        case PM_ASTERISK:
528
          for (i = l; i <= plen; i++)
529
            pos[i].mark = 1;
530
          h = plen;
531
          break;
532

    
533
        case PM_ASN:        /* Define single ASN as ASN..ASN - very narrow interval */
534
          val2 = val = mask->val;
535
          goto step;
536
        case PM_ASN_EXPR:
537
          val2 = val = f_eval_asn((struct f_inst *) mask->val);
538
          goto step;
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
}