Statistics
| Branch: | Revision:

iof-bird-daemon / nest / a-path.c @ ae80a2de

History | View | Annotate | Download (9.32 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
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("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
}