Statistics
| Branch: | Revision:

iof-bird-daemon / nest / a-path.c @ 25cb9f1d

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

    
17

    
18
/* Global AS4 support, shared by all BGP instances.
19
 * This specifies whether BA_AS_PATH attributes contain 2 or 4 B per ASN
20
 */
21

    
22
int bgp_as4_support = 1;
23

    
24
static void
25
put_as(byte *data, u32 as)
26
{
27
  if (bgp_as4_support)
28
    put_u32(data, as);
29
  else if (as <= 0xFFFF)
30
    put_u16(data, as);
31
  else
32
    bug("put_as: Try to put 32bit AS to 16bit AS Path");
33
}
34

    
35
static inline u32
36
get_as(byte *data)
37
{
38
  return bgp_as4_support ? get_u32(data) : get_u16(data);
39
}
40

    
41
struct adata *
42
as_path_prepend(struct linpool *pool, struct adata *olda, u32 as)
43
{
44
  int bs = bgp_as4_support ? 4 : 2;
45
  struct adata *newa;
46

    
47
  if (olda->length && olda->data[0] == AS_PATH_SEQUENCE && olda->data[1] < 255)
48
    /* Starting with sequence => just prepend the AS number */
49
    {
50
      int nl = olda->length + bs;
51
      newa = lp_alloc(pool, sizeof(struct adata) + nl);
52
      newa->length = nl;
53
      newa->data[0] = AS_PATH_SEQUENCE;
54
      newa->data[1] = olda->data[1] + 1;
55
      memcpy(newa->data + bs + 2, olda->data + 2, olda->length - 2);
56
    }
57
  else /* Create new path segment */
58
    {
59
      int nl = olda->length + bs + 2;
60
      newa = lp_alloc(pool, sizeof(struct adata) + nl);
61
      newa->length = nl;
62
      newa->data[0] = AS_PATH_SEQUENCE;
63
      newa->data[1] = 1;
64
      memcpy(newa->data + bs + 2, olda->data, olda->length);
65
    }
66
  put_as(newa->data + 2, as);
67
  return newa;
68
}
69

    
70
int
71
as_path_convert_to_old(struct adata *path, byte *dst, int *new_used)
72
{
73
  byte *src = path->data;
74
  byte *src_end = src + path->length;
75
  byte *dst_start = dst;
76
  u32 as;
77
  int i, n;
78
  *new_used = 0;
79

    
80
  while (src < src_end)
81
    {
82
      n = src[1];
83
      *dst++ = *src++;
84
      *dst++ = *src++;
85

    
86
      for(i=0; i<n; i++)
87
        {
88
          as = get_u32(src);
89
          if (as > 0xFFFF) 
90
            {
91
              as = AS_TRANS;
92
              *new_used = 1;
93
            }
94
          put_u16(dst, as);
95
          src += 4;
96
          dst += 2;
97
        }
98
    }
99

    
100
  return dst - dst_start;
101
}
102

    
103
int
104
as_path_convert_to_new(struct adata *path, byte *dst, int req_as)
105
{
106
  byte *src = path->data;
107
  byte *src_end = src + path->length;
108
  byte *dst_start = dst;
109
  u32 as;
110
  int i, t, n;
111

    
112

    
113
  while ((src < src_end) && (req_as > 0))
114
    {
115
      t = *src++;
116
      n = *src++;
117

    
118
      if (t == AS_PATH_SEQUENCE)
119
        {
120
          if (n > req_as)
121
            n = req_as;
122

    
123
          req_as -= n;
124
        }
125
      else // t == AS_PATH_SET
126
        req_as--;
127

    
128
      *dst++ = t;
129
      *dst++ = n;
130

    
131
      for(i=0; i<n; i++)
132
        {
133
          as = get_u16(src);
134
          put_u32(dst, as);
135
          src += 2;
136
          dst += 4;
137
        }
138
    }
139

    
140
  return dst - dst_start;
141
}
142

    
143
void
144
as_path_format(struct adata *path, byte *buf, unsigned int size)
145
{
146
  int bs = bgp_as4_support ? 4 : 2;
147
  byte *p = path->data;
148
  byte *e = p + path->length;
149
  byte *end = buf + size - 16;
150
  int sp = 1;
151
  int l, isset;
152

    
153
  while (p < e)
154
    {
155
      if (buf > end)
156
        {
157
          strcpy(buf, " ...");
158
          return;
159
        }
160
      isset = (*p++ == AS_PATH_SET);
161
      l = *p++;
162
      if (isset)
163
        {
164
          if (!sp)
165
            *buf++ = ' ';
166
          *buf++ = '{';
167
          sp = 0;
168
        }
169
      while (l-- && buf <= end)
170
        {
171
          if (!sp)
172
            *buf++ = ' ';
173
          buf += bsprintf(buf, "%u", get_as(p));
174
          p += bs;
175
          sp = 0;
176
        }
177
      if (isset)
178
        {
179
          *buf++ = ' ';
180
          *buf++ = '}';
181
          sp = 0;
182
        }
183
    }
184
  *buf = 0;
185
}
186

    
187
int
188
as_path_getlen(struct adata *path)
189
{
190
  int bs = bgp_as4_support ? 4 : 2;
191
  int res = 0;
192
  u8 *p = path->data;
193
  u8 *q = p+path->length;
194
  int len;
195

    
196
  while (p<q)
197
    {
198
      switch (*p++)
199
        {
200
        case AS_PATH_SET:      len = *p++; res++;      p += bs * len; break;
201
        case AS_PATH_SEQUENCE: len = *p++; res += len; p += bs * len; break;
202
        default: bug("as_path_getlen: Invalid path segment");
203
        }
204
    }
205
  return res;
206
}
207

    
208
int
209
as_path_get_first(struct adata *path, u32 *orig_as)
210
{
211
  int bs = bgp_as4_support ? 4 : 2;
212
  int found = 0;
213
  u32 res = 0;
214
  u8 *p = path->data;
215
  u8 *q = p+path->length;
216
  int len;
217

    
218
  while (p<q)
219
    {
220
      switch (*p++)
221
        {
222
        case AS_PATH_SET:
223
          if (len = *p++)
224
            {
225
              found = 1;
226
              res = get_as(p);
227
              p += bs * len;
228
            }
229
          break;
230
        case AS_PATH_SEQUENCE:
231
          if (len = *p++)
232
            {
233
              found = 1;
234
              res = get_as(p + bs * (len - 1));
235
              p += bs * len;
236
            }
237
          break;
238
        default: bug("as_path_get_first: Invalid path segment");
239
        }
240
    }
241

    
242
  *orig_as = res;
243
  return found;
244
}
245

    
246
int
247
as_path_get_last(struct adata *path, u32 *last_as)
248
{
249
  u8 *p = path->data;
250

    
251
  if ((path->length == 0) || (p[0] != AS_PATH_SEQUENCE) || (p[1] == 0))
252
    return 0;
253
  else
254
    {
255
      *last_as = get_as(p+2);
256
      return 1;
257
    }
258
}
259

    
260
int
261
as_path_is_member(struct adata *path, u32 as)
262
{
263
  int bs = bgp_as4_support ? 4 : 2;
264
  u8 *p = path->data;
265
  u8 *q = p+path->length;
266
  int i, n;
267

    
268
  while (p<q)
269
    {
270
      n = p[1];
271
      p += 2;
272
      for(i=0; i<n; i++)
273
        {
274
          if (get_as(p) == as)
275
            return 1;
276
          p += bs;
277
        }
278
    }
279
  return 0;
280
}
281

    
282

    
283

    
284
#define MASK_PLUS do { mask = mask->next; if (!mask) return next == q; \
285
                       asterisk = mask->any; \
286
                       if (asterisk) { mask = mask->next; if (!mask) { return 1; } } \
287
                       } while(0)
288

    
289
int
290
as_path_match(struct adata *path, struct f_path_mask *mask)
291
{
292
  int bs = bgp_as4_support ? 4 : 2;
293
  int i;
294
  int asterisk = 0;
295
  u8 *p = path->data;
296
  u8 *q = p+path->length;
297
  int len;
298
  u8 *next;
299
  u32 as;
300

    
301
  if (!mask)
302
    return ! path->length;
303

    
304
  asterisk = mask->any;
305
  if (asterisk)
306
    { mask = mask->next; if (!mask) return 1; }
307

    
308
  while (p<q) {
309
    switch (*p++) {
310
    case AS_PATH_SET:
311
      len = *p++;
312
      {
313
        u8 *p_save = p;
314
        next = p_save + bs * len;
315
      retry:
316
        p = p_save;
317
        for (i=0; i<len; i++) {
318
          as = get_as(p);
319
          if (asterisk && (as == mask->val)) {
320
            MASK_PLUS;
321
            goto retry;
322
          }
323
          if (!asterisk && (as == mask->val)) {
324
            p = next;
325
            MASK_PLUS;
326
            goto okay;
327
          }
328
          p += bs;
329
        }
330
        if (!asterisk)
331
          return 0;
332
      okay: ;
333
      }
334
      break;
335

    
336
    case AS_PATH_SEQUENCE:
337
      len = *p++;
338
      for (i=0; i<len; i++) {
339
        next = p + bs;
340
        as = get_as(p);
341
        if (asterisk && (as == mask->val))
342
          MASK_PLUS;
343
        else if (!asterisk) {
344
          if (as != mask->val)
345
            return 0;
346
          MASK_PLUS;
347
        }
348
        p += bs;
349
      }
350
      break;
351

    
352
    default:
353
      bug("as_path_match: Invalid path component");
354
    }
355
  }
356
  return 0;
357
}
358