Statistics
| Branch: | Revision:

iof-bird-daemon / nest / a-path.c @ 7e95c05d

History | View | Annotate | Download (7.94 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 11cb6202 Ondrej Zajicek
19 43c1cecc Ondrej Zajicek
// static inline void put_as(byte *data, u32 as) { put_u32(data, as); }
20
// static inline u32 get_as(byte *data) { return get_u32(data); }
21 11cb6202 Ondrej Zajicek
22 43c1cecc Ondrej Zajicek
#define put_as put_u32
23
#define get_as get_u32
24
#define BS  4
25 11cb6202 Ondrej Zajicek
26 c0668f36 Martin Mares
struct adata *
27 11cb6202 Ondrej Zajicek
as_path_prepend(struct linpool *pool, struct adata *olda, u32 as)
28 c0668f36 Martin Mares
{
29
  struct adata *newa;
30
31 11cb6202 Ondrej Zajicek
  if (olda->length && olda->data[0] == AS_PATH_SEQUENCE && olda->data[1] < 255)
32
    /* Starting with sequence => just prepend the AS number */
33 c0668f36 Martin Mares
    {
34 43c1cecc Ondrej Zajicek
      int nl = olda->length + BS;
35 11cb6202 Ondrej Zajicek
      newa = lp_alloc(pool, sizeof(struct adata) + nl);
36
      newa->length = nl;
37
      newa->data[0] = AS_PATH_SEQUENCE;
38 c0668f36 Martin Mares
      newa->data[1] = olda->data[1] + 1;
39 43c1cecc Ondrej Zajicek
      memcpy(newa->data + BS + 2, olda->data + 2, olda->length - 2);
40 c0668f36 Martin Mares
    }
41 11cb6202 Ondrej Zajicek
  else /* Create new path segment */
42 c0668f36 Martin Mares
    {
43 43c1cecc Ondrej Zajicek
      int nl = olda->length + BS + 2;
44 11cb6202 Ondrej Zajicek
      newa = lp_alloc(pool, sizeof(struct adata) + nl);
45
      newa->length = nl;
46
      newa->data[0] = AS_PATH_SEQUENCE;
47 c0668f36 Martin Mares
      newa->data[1] = 1;
48 43c1cecc Ondrej Zajicek
      memcpy(newa->data + BS + 2, olda->data, olda->length);
49 c0668f36 Martin Mares
    }
50 11cb6202 Ondrej Zajicek
  put_as(newa->data + 2, as);
51 c0668f36 Martin Mares
  return newa;
52
}
53 c6add07f Martin Mares
54 11cb6202 Ondrej Zajicek
int
55
as_path_convert_to_old(struct adata *path, byte *dst, int *new_used)
56
{
57
  byte *src = path->data;
58
  byte *src_end = src + path->length;
59
  byte *dst_start = dst;
60
  u32 as;
61
  int i, n;
62
  *new_used = 0;
63
64
  while (src < src_end)
65
    {
66
      n = src[1];
67
      *dst++ = *src++;
68
      *dst++ = *src++;
69
70
      for(i=0; i<n; i++)
71
        {
72
          as = get_u32(src);
73
          if (as > 0xFFFF) 
74
            {
75
              as = AS_TRANS;
76
              *new_used = 1;
77
            }
78
          put_u16(dst, as);
79
          src += 4;
80
          dst += 2;
81
        }
82
    }
83
84
  return dst - dst_start;
85
}
86
87
int
88
as_path_convert_to_new(struct adata *path, byte *dst, int req_as)
89
{
90
  byte *src = path->data;
91
  byte *src_end = src + path->length;
92
  byte *dst_start = dst;
93
  u32 as;
94
  int i, t, n;
95
96
97
  while ((src < src_end) && (req_as > 0))
98
    {
99
      t = *src++;
100
      n = *src++;
101
102
      if (t == AS_PATH_SEQUENCE)
103
        {
104
          if (n > req_as)
105
            n = req_as;
106
107
          req_as -= n;
108
        }
109
      else // t == AS_PATH_SET
110
        req_as--;
111
112
      *dst++ = t;
113
      *dst++ = n;
114
115
      for(i=0; i<n; i++)
116
        {
117
          as = get_u16(src);
118
          put_u32(dst, as);
119
          src += 2;
120
          dst += 4;
121
        }
122
    }
123
124
  return dst - dst_start;
125
}
126
127 c6add07f Martin Mares
void
128
as_path_format(struct adata *path, byte *buf, unsigned int size)
129
{
130
  byte *p = path->data;
131 987de545 Martin Mares
  byte *e = p + path->length;
132 11cb6202 Ondrej Zajicek
  byte *end = buf + size - 16;
133 c6add07f Martin Mares
  int sp = 1;
134 93a786cb Martin Mares
  int l, isset;
135 c6add07f Martin Mares
136
  while (p < e)
137
    {
138
      if (buf > end)
139
        {
140
          strcpy(buf, " ...");
141
          return;
142
        }
143
      isset = (*p++ == AS_PATH_SET);
144
      l = *p++;
145
      if (isset)
146
        {
147
          if (!sp)
148
            *buf++ = ' ';
149
          *buf++ = '{';
150
          sp = 0;
151
        }
152
      while (l-- && buf <= end)
153
        {
154
          if (!sp)
155
            *buf++ = ' ';
156 11cb6202 Ondrej Zajicek
          buf += bsprintf(buf, "%u", get_as(p));
157 43c1cecc Ondrej Zajicek
          p += BS;
158 c6add07f Martin Mares
          sp = 0;
159
        }
160
      if (isset)
161
        {
162
          *buf++ = ' ';
163
          *buf++ = '}';
164
          sp = 0;
165
        }
166
    }
167
  *buf = 0;
168
}
169 684c6f5a Pavel Machek
170
int
171
as_path_getlen(struct adata *path)
172
{
173 43c1cecc Ondrej Zajicek
  return as_path_getlen_int(path, BS);
174 949bd34e Ondrej Zajicek
}
175
176
int
177
as_path_getlen_int(struct adata *path, int bs)
178
{
179 684c6f5a Pavel Machek
  int res = 0;
180
  u8 *p = path->data;
181
  u8 *q = p+path->length;
182
  int len;
183
184 4b03f64b Martin Mares
  while (p<q)
185
    {
186
      switch (*p++)
187
        {
188 11cb6202 Ondrej Zajicek
        case AS_PATH_SET:      len = *p++; res++;      p += bs * len; break;
189
        case AS_PATH_SEQUENCE: len = *p++; res += len; p += bs * len; break;
190 4b03f64b Martin Mares
        default: bug("as_path_getlen: Invalid path segment");
191
        }
192 684c6f5a Pavel Machek
    }
193
  return res;
194
}
195 2a40efa5 Pavel Machek
196 f49528a3 Martin Mares
int
197 52b9b2a1 Ondrej Zajicek
as_path_get_last(struct adata *path, u32 *orig_as)
198 f49528a3 Martin Mares
{
199 11cb6202 Ondrej Zajicek
  int found = 0;
200
  u32 res = 0;
201 f49528a3 Martin Mares
  u8 *p = path->data;
202
  u8 *q = p+path->length;
203
  int len;
204
205
  while (p<q)
206
    {
207
      switch (*p++)
208
        {
209
        case AS_PATH_SET:
210
          if (len = *p++)
211 11cb6202 Ondrej Zajicek
            {
212 52b9b2a1 Ondrej Zajicek
              found = 0;
213 43c1cecc Ondrej Zajicek
              p += BS * len;
214 11cb6202 Ondrej Zajicek
            }
215 f49528a3 Martin Mares
          break;
216
        case AS_PATH_SEQUENCE:
217
          if (len = *p++)
218 11cb6202 Ondrej Zajicek
            {
219
              found = 1;
220 43c1cecc Ondrej Zajicek
              res = get_as(p + BS * (len - 1));
221
              p += BS * len;
222 11cb6202 Ondrej Zajicek
            }
223 f49528a3 Martin Mares
          break;
224
        default: bug("as_path_get_first: Invalid path segment");
225
        }
226
    }
227 11cb6202 Ondrej Zajicek
228 52b9b2a1 Ondrej Zajicek
  if (found)
229
    *orig_as = res;
230 11cb6202 Ondrej Zajicek
  return found;
231 f49528a3 Martin Mares
}
232
233 11cb6202 Ondrej Zajicek
int
234 52b9b2a1 Ondrej Zajicek
as_path_get_first(struct adata *path, u32 *last_as)
235 b6bf284a Ondrej Zajicek
{
236
  u8 *p = path->data;
237
238
  if ((path->length == 0) || (p[0] != AS_PATH_SEQUENCE) || (p[1] == 0))
239
    return 0;
240
  else
241
    {
242
      *last_as = get_as(p+2);
243
      return 1;
244
    }
245
}
246
247
int
248 11cb6202 Ondrej Zajicek
as_path_is_member(struct adata *path, u32 as)
249
{
250
  u8 *p = path->data;
251
  u8 *q = p+path->length;
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
            return 1;
262 43c1cecc Ondrej Zajicek
          p += BS;
263 11cb6202 Ondrej Zajicek
        }
264
    }
265
  return 0;
266
}
267
268
269 c8a6b9a3 Ondrej Zajicek
struct pm_pos
270
{
271
  u8 set;
272
  u8 mark;
273
  union
274
  {
275
    char *sp;
276
    u32 asn;
277
  } val;
278
};
279
280
static int
281
parse_path(struct adata *path, struct pm_pos *pos)
282 2a40efa5 Pavel Machek
{
283
  u8 *p = path->data;
284 c8a6b9a3 Ondrej Zajicek
  u8 *q = p + path->length;
285
  struct pm_pos *opos = pos;
286 05198c12 Ondrej Zajicek
  int i, len;
287 2a40efa5 Pavel Machek
288 25cb9f1d Ondrej Zajicek
289 c8a6b9a3 Ondrej Zajicek
  while (p < q)
290
    switch (*p++)
291 2a40efa5 Pavel Machek
      {
292 c8a6b9a3 Ondrej Zajicek
      case AS_PATH_SET:
293
        pos->set = 1;
294
        pos->mark = 0;
295
        pos->val.sp = p;
296
        len = *p;
297 43c1cecc Ondrej Zajicek
        p += 1 + BS * len;
298 c8a6b9a3 Ondrej Zajicek
        pos++;
299
        break;
300
      
301
      case AS_PATH_SEQUENCE:
302
        len = *p++;
303
        for (i = 0; i < len; i++)
304
          {
305
            pos->set = 0;
306
            pos->mark = 0;
307
            pos->val.asn = get_as(p);
308 43c1cecc Ondrej Zajicek
            p += BS;
309 c8a6b9a3 Ondrej Zajicek
            pos++;
310 2a40efa5 Pavel Machek
          }
311 c8a6b9a3 Ondrej Zajicek
        break;
312
313
      default:
314
        bug("as_path_match: Invalid path component");
315 2a40efa5 Pavel Machek
      }
316 c8a6b9a3 Ondrej Zajicek
  
317
  return pos - opos;
318
}
319
320
321
static int
322
pm_match(struct pm_pos *pos, u32 asn)
323
{
324
  if (! pos->set)
325
    return pos->val.asn == asn;
326
327
  u8 *p = pos->val.sp;
328
  int len = *p++;
329
  int i;
330
331
  for (i = 0; i < len; i++)
332 43c1cecc Ondrej Zajicek
    if (get_as(p + i * BS) == asn)
333 c8a6b9a3 Ondrej Zajicek
      return 1;
334
335
  return 0;
336
}
337
338
static void
339
pm_mark(struct pm_pos *pos, int i, int plen, int *nl, int *nh)
340
{
341
  int j;
342
343
  if (pos[i].set)
344
    pos[i].mark = 1;
345
  
346
  for (j = i + 1; (j < plen) && pos[j].set && (! pos[j].mark); j++)
347
    pos[j].mark = 1;
348
  pos[j].mark = 1;
349
350
  /* We are going downwards, therefore every mark is
351
     new low and just the first mark is new high */
352
353
  *nl = i + (pos[i].set ? 0 : 1);
354
355
  if (*nh < 0)
356
    *nh = j;
357
}
358
359
/* AS path matching is nontrivial. Because AS path can
360
 * contain sets, it is not a plain wildcard matching. A set 
361
 * in an AS path is interpreted as it might represent any
362
 * sequence of AS numbers from that set (possibly with
363
 * repetitions). So it is also a kind of a pattern,
364
 * more complicated than a path mask.
365
 *
366
 * The algorithm for AS path matching is a variant
367
 * of nondeterministic finite state machine, where
368
 * positions in AS path are states, and items in
369
 * path mask are input for that finite state machine.
370
 * During execution of the algorithm we maintain a set
371
 * of marked states - a state is marked if it can be
372
 * reached by any walk through NFSM with regard to
373
 * currently processed part of input. When we process
374
 * next part of mask, we advance each marked state.
375
 * We start with marked first position, when we
376
 * run out of marked positions, we reject. When
377
 * we process the whole mask, we accept iff final position
378
 * (auxiliary position after last real position in AS path)
379
 * is marked.
380
 */
381
382
int
383
as_path_match(struct adata *path, struct f_path_mask *mask)
384
{
385
  struct pm_pos pos[2048 + 1];
386
  int plen = parse_path(path, pos);
387
  int l, h, i, nh, nl;
388 e81b440f Ondrej Zajicek
  u32 val = 0;
389 c8a6b9a3 Ondrej Zajicek
390
  /* l and h are bound of interval of positions where
391
     are marked states */
392
393
  pos[plen].set = 0;
394
  pos[plen].mark = 0;
395
396
  l = h = 0;
397
  pos[0].mark = 1;
398
  
399
  while (mask)
400
    {
401
      /* We remove this mark to not step after pos[plen] */
402
      pos[plen].mark = 0;
403
404
      switch (mask->kind)
405
        {
406
        case PM_ASTERISK:
407
          for (i = l; i <= plen; i++)
408
            pos[i].mark = 1;
409
          h = plen;
410
          break;
411
412
        case PM_ASN:
413 92a72a4c Ondrej Zajicek
          val = mask->val;
414
          goto step;
415
        case PM_ASN_EXPR:
416
          val = f_eval_asn((struct f_inst *) mask->val);
417
          goto step;
418
        case PM_QUESTION:
419
        step:
420 e81b440f Ondrej Zajicek
          nh = nl = -1;
421 c8a6b9a3 Ondrej Zajicek
          for (i = h; i >= l; i--)
422
            if (pos[i].mark)
423
              {
424
                pos[i].mark = 0;
425 92a72a4c Ondrej Zajicek
                if ((mask->kind == PM_QUESTION) || pm_match(pos + i, val))
426 c8a6b9a3 Ondrej Zajicek
                  pm_mark(pos, i, plen, &nl, &nh);
427
              }
428
429
          if (nh < 0)
430 2a40efa5 Pavel Machek
            return 0;
431 c8a6b9a3 Ondrej Zajicek
432
          h = nh;
433
          l = nl;
434
          break;
435 2a40efa5 Pavel Machek
        }
436
437 c8a6b9a3 Ondrej Zajicek
      mask = mask->next;
438 2a40efa5 Pavel Machek
    }
439 98347659 Pavel Machek
440 c8a6b9a3 Ondrej Zajicek
  return pos[plen].mark;
441
}