Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (7.94 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

    
19
// 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

    
22
#define put_as put_u32
23
#define get_as get_u32
24
#define BS  4
25

    
26
struct adata *
27
as_path_prepend(struct linpool *pool, struct adata *olda, u32 as)
28
{
29
  struct adata *newa;
30

    
31
  if (olda->length && olda->data[0] == AS_PATH_SEQUENCE && olda->data[1] < 255)
32
    /* Starting with sequence => just prepend the AS number */
33
    {
34
      int nl = olda->length + BS;
35
      newa = lp_alloc(pool, sizeof(struct adata) + nl);
36
      newa->length = nl;
37
      newa->data[0] = AS_PATH_SEQUENCE;
38
      newa->data[1] = olda->data[1] + 1;
39
      memcpy(newa->data + BS + 2, olda->data + 2, olda->length - 2);
40
    }
41
  else /* Create new path segment */
42
    {
43
      int nl = olda->length + BS + 2;
44
      newa = lp_alloc(pool, sizeof(struct adata) + nl);
45
      newa->length = nl;
46
      newa->data[0] = AS_PATH_SEQUENCE;
47
      newa->data[1] = 1;
48
      memcpy(newa->data + BS + 2, olda->data, olda->length);
49
    }
50
  put_as(newa->data + 2, as);
51
  return newa;
52
}
53

    
54
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
void
128
as_path_format(struct adata *path, byte *buf, unsigned int size)
129
{
130
  byte *p = path->data;
131
  byte *e = p + path->length;
132
  byte *end = buf + size - 16;
133
  int sp = 1;
134
  int l, isset;
135

    
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
          buf += bsprintf(buf, "%u", get_as(p));
157
          p += BS;
158
          sp = 0;
159
        }
160
      if (isset)
161
        {
162
          *buf++ = ' ';
163
          *buf++ = '}';
164
          sp = 0;
165
        }
166
    }
167
  *buf = 0;
168
}
169

    
170
int
171
as_path_getlen(struct adata *path)
172
{
173
  return as_path_getlen_int(path, BS);
174
}
175

    
176
int
177
as_path_getlen_int(struct adata *path, int bs)
178
{
179
  int res = 0;
180
  u8 *p = path->data;
181
  u8 *q = p+path->length;
182
  int len;
183

    
184
  while (p<q)
185
    {
186
      switch (*p++)
187
        {
188
        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
        default: bug("as_path_getlen: Invalid path segment");
191
        }
192
    }
193
  return res;
194
}
195

    
196
int
197
as_path_get_last(struct adata *path, u32 *orig_as)
198
{
199
  int found = 0;
200
  u32 res = 0;
201
  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
            {
212
              found = 0;
213
              p += BS * len;
214
            }
215
          break;
216
        case AS_PATH_SEQUENCE:
217
          if (len = *p++)
218
            {
219
              found = 1;
220
              res = get_as(p + BS * (len - 1));
221
              p += BS * len;
222
            }
223
          break;
224
        default: bug("as_path_get_first: Invalid path segment");
225
        }
226
    }
227

    
228
  if (found)
229
    *orig_as = res;
230
  return found;
231
}
232

    
233
int
234
as_path_get_first(struct adata *path, u32 *last_as)
235
{
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
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
          p += BS;
263
        }
264
    }
265
  return 0;
266
}
267

    
268

    
269
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
{
283
  u8 *p = path->data;
284
  u8 *q = p + path->length;
285
  struct pm_pos *opos = pos;
286
  int i, len;
287

    
288

    
289
  while (p < q)
290
    switch (*p++)
291
      {
292
      case AS_PATH_SET:
293
        pos->set = 1;
294
        pos->mark = 0;
295
        pos->val.sp = p;
296
        len = *p;
297
        p += 1 + BS * len;
298
        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
            p += BS;
309
            pos++;
310
          }
311
        break;
312

    
313
      default:
314
        bug("as_path_match: Invalid path component");
315
      }
316
  
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
    if (get_as(p + i * BS) == asn)
333
      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
  u32 val = 0;
389

    
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
          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
          nh = nl = -1;
421
          for (i = h; i >= l; i--)
422
            if (pos[i].mark)
423
              {
424
                pos[i].mark = 0;
425
                if ((mask->kind == PM_QUESTION) || pm_match(pos + i, val))
426
                  pm_mark(pos, i, plen, &nl, &nh);
427
              }
428

    
429
          if (nh < 0)
430
            return 0;
431

    
432
          h = nh;
433
          l = nl;
434
          break;
435
        }
436

    
437
      mask = mask->next;
438
    }
439

    
440
  return pos[plen].mark;
441
}