]>
Commit | Line | Data |
---|---|---|
c0668f36 MM |
1 | /* |
2 | * BIRD -- Set/Community-list 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 | ||
d15b0b0a OZ |
10 | #include <stdlib.h> |
11 | ||
c0668f36 MM |
12 | #include "nest/bird.h" |
13 | #include "nest/route.h" | |
c6add07f | 14 | #include "nest/attrs.h" |
c0668f36 | 15 | #include "lib/resource.h" |
c6add07f MM |
16 | #include "lib/string.h" |
17 | ||
fdf16eb6 OZ |
18 | /** |
19 | * int_set_format - format an &set for printing | |
20 | * @set: set attribute to be formatted | |
21 | * @way: style of format (0 for router ID list, 1 for community list) | |
22 | * @from: starting position in set | |
23 | * @buf: destination buffer | |
24 | * @size: size of buffer | |
25 | * | |
26 | * This function takes a set attribute and formats it. @way specifies | |
27 | * the style of format (router ID / community). @from argument can be | |
28 | * used to specify the first printed value for the purpose of printing | |
29 | * untruncated sets even with smaller buffers. If the output fits in | |
30 | * the buffer, 0 is returned, otherwise the position of the first not | |
31 | * printed item is returned. This value can be used as @from argument | |
32 | * in subsequent calls. If truncated output suffices, -1 can be | |
33 | * instead used as @from, in that case " ..." is eventually added at | |
34 | * the buffer to indicate truncation. | |
35 | */ | |
36 | int | |
ae80a2de | 37 | int_set_format(struct adata *set, int way, int from, byte *buf, uint size) |
c6add07f MM |
38 | { |
39 | u32 *z = (u32 *) set->data; | |
fdf16eb6 | 40 | byte *end = buf + size - 24; |
42a0c054 | 41 | int from2 = MAX(from, 0); |
fdf16eb6 OZ |
42 | int to = set->length / 4; |
43 | int i; | |
c6add07f | 44 | |
42a0c054 | 45 | for (i = from2; i < to; i++) |
c6add07f | 46 | { |
c6add07f MM |
47 | if (buf > end) |
48 | { | |
fdf16eb6 OZ |
49 | if (from < 0) |
50 | strcpy(buf, " ..."); | |
51 | else | |
52 | *buf = 0; | |
53 | return i; | |
c6add07f | 54 | } |
aebe06b4 | 55 | |
42a0c054 | 56 | if (i > from2) |
fdf16eb6 OZ |
57 | *buf++ = ' '; |
58 | ||
aebe06b4 | 59 | if (way) |
fdf16eb6 | 60 | buf += bsprintf(buf, "(%d,%d)", z[i] >> 16, z[i] & 0xffff); |
aebe06b4 | 61 | else |
fdf16eb6 | 62 | buf += bsprintf(buf, "%R", z[i]); |
c6add07f MM |
63 | } |
64 | *buf = 0; | |
fdf16eb6 | 65 | return 0; |
c6add07f | 66 | } |
9c400ec9 | 67 | |
42a0c054 OZ |
68 | int |
69 | ec_format(byte *buf, u64 ec) | |
70 | { | |
71 | u32 type, key, val; | |
72 | char tbuf[16], *kind; | |
73 | ||
74 | type = ec >> 48; | |
75 | switch (type & 0xf0ff) | |
76 | { | |
77 | case EC_RT: kind = "rt"; break; | |
78 | case EC_RO: kind = "ro"; break; | |
79 | ||
80 | default: | |
81 | kind = tbuf; | |
82 | bsprintf(kind, "unknown 0x%x", type); | |
83 | } | |
84 | ||
85 | switch (ec >> 56) | |
86 | { | |
87 | /* RFC 4360 3.1. Two-Octet AS Specific Extended Community */ | |
88 | case 0x00: | |
89 | case 0x40: | |
90 | key = (ec >> 32) & 0xFFFF; | |
91 | val = ec; | |
92 | return bsprintf(buf, "(%s, %u, %u)", kind, key, val); | |
93 | ||
94 | /* RFC 4360 3.2. IPv4 Address Specific Extended Community */ | |
95 | case 0x01: | |
96 | case 0x41: | |
97 | key = ec >> 16; | |
98 | val = ec & 0xFFFF; | |
99 | return bsprintf(buf, "(%s, %R, %u)", kind, key, val); | |
100 | ||
101 | /* RFC 5668 4-Octet AS Specific BGP Extended Community */ | |
102 | case 0x02: | |
103 | case 0x42: | |
104 | key = ec >> 16; | |
105 | val = ec & 0xFFFF; | |
106 | return bsprintf(buf, "(%s, %u, %u)", kind, key, val); | |
107 | ||
108 | /* Generic format for unknown kinds of extended communities */ | |
109 | default: | |
110 | key = ec >> 32; | |
111 | val = ec; | |
112 | return bsprintf(buf, "(generic, 0x%x, 0x%x)", key, val); | |
113 | } | |
114 | ||
115 | } | |
116 | ||
117 | int | |
ae80a2de | 118 | ec_set_format(struct adata *set, int from, byte *buf, uint size) |
42a0c054 OZ |
119 | { |
120 | u32 *z = int_set_get_data(set); | |
66dbdbd9 | 121 | byte *end = buf + size - 64; |
42a0c054 OZ |
122 | int from2 = MAX(from, 0); |
123 | int to = int_set_get_size(set); | |
124 | int i; | |
125 | ||
126 | for (i = from2; i < to; i += 2) | |
127 | { | |
128 | if (buf > end) | |
129 | { | |
130 | if (from < 0) | |
131 | strcpy(buf, " ..."); | |
132 | else | |
133 | *buf = 0; | |
134 | return i; | |
135 | } | |
136 | ||
137 | if (i > from2) | |
138 | *buf++ = ' '; | |
139 | ||
140 | buf += ec_format(buf, ec_get(z, i)); | |
141 | } | |
142 | *buf = 0; | |
143 | return 0; | |
144 | } | |
145 | ||
66dbdbd9 OZ |
146 | int |
147 | lc_format(byte *buf, lcomm lc) | |
148 | { | |
a46e01ee | 149 | return bsprintf(buf, "(%u, %u, %u)", lc.asn, lc.ldp1, lc.ldp2); |
66dbdbd9 OZ |
150 | } |
151 | ||
152 | int | |
153 | lc_set_format(struct adata *set, int from, byte *buf, uint bufsize) | |
154 | { | |
155 | u32 *d = (u32 *) set->data; | |
156 | byte *end = buf + bufsize - 64; | |
157 | int from2 = MAX(from, 0); | |
158 | int to = set->length / 4; | |
159 | int i; | |
160 | ||
161 | for (i = from2; i < to; i += 3) | |
162 | { | |
163 | if (buf > end) | |
164 | { | |
165 | if (from < 0) | |
166 | strcpy(buf, "..."); | |
167 | else | |
168 | buf[-1] = 0; | |
169 | return i; | |
170 | } | |
171 | ||
a46e01ee | 172 | buf += bsprintf(buf, "(%u, %u, %u)", d[i], d[i+1], d[i+2]); |
66dbdbd9 OZ |
173 | *buf++ = ' '; |
174 | } | |
175 | ||
176 | if (i != from2) | |
177 | buf--; | |
178 | ||
179 | *buf = 0; | |
180 | return 0; | |
181 | } | |
182 | ||
9c400ec9 PM |
183 | int |
184 | int_set_contains(struct adata *list, u32 val) | |
185 | { | |
0267f49f OZ |
186 | if (!list) |
187 | return 0; | |
188 | ||
700bbe60 | 189 | u32 *l = (u32 *) list->data; |
42a0c054 OZ |
190 | int len = int_set_get_size(list); |
191 | int i; | |
192 | ||
193 | for (i = 0; i < len; i++) | |
9c400ec9 PM |
194 | if (*l++ == val) |
195 | return 1; | |
42a0c054 OZ |
196 | |
197 | return 0; | |
198 | } | |
199 | ||
200 | int | |
201 | ec_set_contains(struct adata *list, u64 val) | |
202 | { | |
203 | if (!list) | |
204 | return 0; | |
205 | ||
206 | u32 *l = int_set_get_data(list); | |
207 | int len = int_set_get_size(list); | |
208 | u32 eh = ec_hi(val); | |
209 | u32 el = ec_lo(val); | |
210 | int i; | |
211 | ||
212 | for (i=0; i < len; i += 2) | |
213 | if (l[i] == eh && l[i+1] == el) | |
214 | return 1; | |
215 | ||
9c400ec9 PM |
216 | return 0; |
217 | } | |
218 | ||
66dbdbd9 OZ |
219 | int |
220 | lc_set_contains(struct adata *list, lcomm val) | |
221 | { | |
222 | if (!list) | |
223 | return 0; | |
224 | ||
225 | u32 *l = int_set_get_data(list); | |
226 | int len = int_set_get_size(list); | |
227 | int i; | |
228 | ||
229 | for (i = 0; i < len; i += 3) | |
230 | if (lc_match(l, i, val)) | |
231 | return 1; | |
232 | ||
233 | return 0; | |
234 | } | |
235 | ||
261816b0 OZ |
236 | struct adata * |
237 | int_set_prepend(struct linpool *pool, struct adata *list, u32 val) | |
238 | { | |
239 | struct adata *res; | |
240 | int len; | |
241 | ||
242 | if (int_set_contains(list, val)) | |
243 | return list; | |
244 | ||
245 | len = list ? list->length : 0; | |
246 | res = lp_alloc(pool, sizeof(struct adata) + len + 4); | |
247 | res->length = len + 4; | |
248 | ||
249 | if (list) | |
250 | memcpy(res->data + 4, list->data, list->length); | |
251 | ||
252 | * (u32 *) res->data = val; | |
253 | ||
254 | return res; | |
255 | } | |
66dbdbd9 | 256 | |
0267f49f OZ |
257 | struct adata * |
258 | int_set_add(struct linpool *pool, struct adata *list, u32 val) | |
259 | { | |
260 | struct adata *res; | |
261 | int len; | |
262 | ||
263 | if (int_set_contains(list, val)) | |
264 | return list; | |
265 | ||
266 | len = list ? list->length : 0; | |
42a0c054 | 267 | res = lp_alloc(pool, sizeof(struct adata) + len + 4); |
0267f49f | 268 | res->length = len + 4; |
3c09af41 | 269 | |
0267f49f | 270 | if (list) |
3c09af41 PT |
271 | memcpy(res->data, list->data, list->length); |
272 | ||
261816b0 | 273 | * (u32 *) (res->data + len) = val; |
3c09af41 | 274 | |
0267f49f OZ |
275 | return res; |
276 | } | |
277 | ||
9c400ec9 | 278 | struct adata * |
42a0c054 | 279 | ec_set_add(struct linpool *pool, struct adata *list, u64 val) |
9c400ec9 | 280 | { |
42a0c054 OZ |
281 | if (ec_set_contains(list, val)) |
282 | return list; | |
283 | ||
284 | int olen = list ? list->length : 0; | |
285 | struct adata *res = lp_alloc(pool, sizeof(struct adata) + olen + 8); | |
286 | res->length = olen + 8; | |
287 | ||
288 | if (list) | |
289 | memcpy(res->data, list->data, list->length); | |
290 | ||
66dbdbd9 | 291 | u32 *l = (u32 *) (res->data + olen); |
42a0c054 OZ |
292 | l[0] = ec_hi(val); |
293 | l[1] = ec_lo(val); | |
294 | ||
295 | return res; | |
296 | } | |
297 | ||
66dbdbd9 OZ |
298 | struct adata * |
299 | lc_set_add(struct linpool *pool, struct adata *list, lcomm val) | |
300 | { | |
301 | if (lc_set_contains(list, val)) | |
302 | return list; | |
303 | ||
304 | int olen = list ? list->length : 0; | |
305 | struct adata *res = lp_alloc(pool, sizeof(struct adata) + olen + LCOMM_LENGTH); | |
306 | res->length = olen + LCOMM_LENGTH; | |
307 | ||
308 | if (list) | |
309 | memcpy(res->data, list->data, list->length); | |
310 | ||
311 | lc_put((u32 *) (res->data + olen), val); | |
312 | ||
313 | return res; | |
314 | } | |
9c400ec9 | 315 | |
42a0c054 OZ |
316 | struct adata * |
317 | int_set_del(struct linpool *pool, struct adata *list, u32 val) | |
318 | { | |
9c400ec9 PM |
319 | if (!int_set_contains(list, val)) |
320 | return list; | |
321 | ||
42a0c054 OZ |
322 | struct adata *res; |
323 | res = lp_alloc(pool, sizeof(struct adata) + list->length - 4); | |
324 | res->length = list->length - 4; | |
325 | ||
326 | u32 *l = int_set_get_data(list); | |
327 | u32 *k = int_set_get_data(res); | |
328 | int len = int_set_get_size(list); | |
329 | int i; | |
9c400ec9 | 330 | |
42a0c054 | 331 | for (i = 0; i < len; i++) |
9c400ec9 PM |
332 | if (l[i] != val) |
333 | *k++ = l[i]; | |
334 | ||
335 | return res; | |
336 | } | |
42a0c054 OZ |
337 | |
338 | struct adata * | |
339 | ec_set_del(struct linpool *pool, struct adata *list, u64 val) | |
340 | { | |
341 | if (!ec_set_contains(list, val)) | |
342 | return list; | |
343 | ||
344 | struct adata *res; | |
345 | res = lp_alloc(pool, sizeof(struct adata) + list->length - 8); | |
346 | res->length = list->length - 8; | |
347 | ||
348 | u32 *l = int_set_get_data(list); | |
349 | u32 *k = int_set_get_data(res); | |
350 | int len = int_set_get_size(list); | |
351 | u32 eh = ec_hi(val); | |
352 | u32 el = ec_lo(val); | |
353 | int i; | |
354 | ||
355 | for (i=0; i < len; i += 2) | |
356 | if (! (l[i] == eh && l[i+1] == el)) | |
357 | { | |
358 | *k++ = l[i]; | |
359 | *k++ = l[i+1]; | |
360 | } | |
361 | ||
362 | return res; | |
363 | } | |
0888a737 | 364 | |
66dbdbd9 OZ |
365 | struct adata * |
366 | lc_set_del(struct linpool *pool, struct adata *list, lcomm val) | |
367 | { | |
368 | if (!lc_set_contains(list, val)) | |
369 | return list; | |
370 | ||
371 | struct adata *res; | |
372 | res = lp_alloc(pool, sizeof(struct adata) + list->length - LCOMM_LENGTH); | |
373 | res->length = list->length - LCOMM_LENGTH; | |
374 | ||
375 | u32 *l = int_set_get_data(list); | |
376 | u32 *k = int_set_get_data(res); | |
377 | int len = int_set_get_size(list); | |
378 | int i; | |
379 | ||
380 | for (i=0; i < len; i += 3) | |
381 | if (! lc_match(l, i, val)) | |
382 | k = lc_copy(k, l+i); | |
383 | ||
384 | return res; | |
385 | } | |
0888a737 OZ |
386 | |
387 | struct adata * | |
388 | int_set_union(struct linpool *pool, struct adata *l1, struct adata *l2) | |
389 | { | |
390 | if (!l1) | |
391 | return l2; | |
392 | if (!l2) | |
393 | return l1; | |
394 | ||
395 | struct adata *res; | |
396 | int len = int_set_get_size(l2); | |
397 | u32 *l = int_set_get_data(l2); | |
398 | u32 tmp[len]; | |
399 | u32 *k = tmp; | |
400 | int i; | |
401 | ||
402 | for (i = 0; i < len; i++) | |
403 | if (!int_set_contains(l1, l[i])) | |
404 | *k++ = l[i]; | |
405 | ||
406 | if (k == tmp) | |
407 | return l1; | |
408 | ||
409 | len = (k - tmp) * 4; | |
410 | res = lp_alloc(pool, sizeof(struct adata) + l1->length + len); | |
411 | res->length = l1->length + len; | |
412 | memcpy(res->data, l1->data, l1->length); | |
413 | memcpy(res->data + l1->length, tmp, len); | |
414 | return res; | |
415 | } | |
416 | ||
417 | struct adata * | |
418 | ec_set_union(struct linpool *pool, struct adata *l1, struct adata *l2) | |
419 | { | |
420 | if (!l1) | |
421 | return l2; | |
422 | if (!l2) | |
423 | return l1; | |
424 | ||
425 | struct adata *res; | |
426 | int len = int_set_get_size(l2); | |
427 | u32 *l = int_set_get_data(l2); | |
428 | u32 tmp[len]; | |
429 | u32 *k = tmp; | |
430 | int i; | |
431 | ||
432 | for (i = 0; i < len; i += 2) | |
433 | if (!ec_set_contains(l1, ec_get(l, i))) | |
434 | { | |
435 | *k++ = l[i]; | |
436 | *k++ = l[i+1]; | |
437 | } | |
438 | ||
439 | if (k == tmp) | |
440 | return l1; | |
441 | ||
442 | len = (k - tmp) * 4; | |
443 | res = lp_alloc(pool, sizeof(struct adata) + l1->length + len); | |
444 | res->length = l1->length + len; | |
445 | memcpy(res->data, l1->data, l1->length); | |
446 | memcpy(res->data + l1->length, tmp, len); | |
447 | return res; | |
448 | } | |
66dbdbd9 OZ |
449 | |
450 | struct adata * | |
451 | lc_set_union(struct linpool *pool, struct adata *l1, struct adata *l2) | |
452 | { | |
453 | if (!l1) | |
454 | return l2; | |
455 | if (!l2) | |
456 | return l1; | |
457 | ||
458 | struct adata *res; | |
459 | int len = int_set_get_size(l2); | |
460 | u32 *l = int_set_get_data(l2); | |
461 | u32 tmp[len]; | |
462 | u32 *k = tmp; | |
463 | int i; | |
464 | ||
465 | for (i = 0; i < len; i += 3) | |
466 | if (!lc_set_contains(l1, lc_get(l, i))) | |
467 | k = lc_copy(k, l+i); | |
468 | ||
469 | if (k == tmp) | |
470 | return l1; | |
471 | ||
472 | len = (k - tmp) * 4; | |
473 | res = lp_alloc(pool, sizeof(struct adata) + l1->length + len); | |
474 | res->length = l1->length + len; | |
475 | memcpy(res->data, l1->data, l1->length); | |
476 | memcpy(res->data + l1->length, tmp, len); | |
477 | return res; | |
478 | } | |
d15b0b0a OZ |
479 | |
480 | ||
481 | struct adata * | |
482 | ec_set_del_nontrans(struct linpool *pool, struct adata *set) | |
483 | { | |
484 | adata *res = lp_alloc_adata(pool, set->length); | |
485 | u32 *src = int_set_get_data(set); | |
486 | u32 *dst = int_set_get_data(res); | |
487 | int len = int_set_get_size(set); | |
488 | int i; | |
489 | ||
490 | /* Remove non-transitive communities (EC_TBIT set) */ | |
491 | for (i = 0; i < len; i += 2) | |
492 | { | |
493 | if (src[i] & EC_TBIT) | |
494 | continue; | |
495 | ||
496 | *dst++ = src[i]; | |
497 | *dst++ = src[i+1]; | |
498 | } | |
499 | ||
500 | res->length = ((byte *) dst) - res->data; | |
501 | ||
502 | return res; | |
503 | } | |
504 | ||
505 | static int | |
506 | int_set_cmp(const void *X, const void *Y) | |
507 | { | |
508 | const u32 *x = X, *y = Y; | |
509 | return (*x < *y) ? -1 : (*x > *y) ? 1 : 0; | |
510 | } | |
511 | ||
512 | struct adata * | |
513 | int_set_sort(struct linpool *pool, struct adata *src) | |
514 | { | |
515 | struct adata *dst = lp_alloc_adata(pool, src->length); | |
516 | memcpy(dst->data, src->data, src->length); | |
517 | qsort(dst->data, dst->length / 4, 4, int_set_cmp); | |
518 | return dst; | |
519 | } | |
520 | ||
521 | ||
522 | static int | |
523 | ec_set_cmp(const void *X, const void *Y) | |
524 | { | |
525 | u64 x = ec_get(X, 0); | |
526 | u64 y = ec_get(Y, 0); | |
527 | return (x < y) ? -1 : (x > y) ? 1 : 0; | |
528 | } | |
529 | ||
530 | struct adata * | |
531 | ec_set_sort(struct linpool *pool, struct adata *src) | |
532 | { | |
533 | struct adata *dst = lp_alloc_adata(pool, src->length); | |
534 | memcpy(dst->data, src->data, src->length); | |
535 | qsort(dst->data, dst->length / 8, 8, ec_set_cmp); | |
536 | return dst; | |
537 | } | |
538 | ||
539 | ||
540 | static int | |
541 | lc_set_cmp(const void *X, const void *Y) | |
542 | { | |
543 | const u32 *x = X, *y = Y; | |
544 | if (x[0] != y[0]) | |
545 | return (x[0] > y[0]) ? 1 : -1; | |
546 | if (x[1] != y[1]) | |
547 | return (x[1] > y[1]) ? 1 : -1; | |
548 | if (x[2] != y[2]) | |
549 | return (x[2] > y[2]) ? 1 : -1; | |
550 | return 0; | |
551 | } | |
552 | ||
553 | struct adata * | |
554 | lc_set_sort(struct linpool *pool, struct adata *src) | |
555 | { | |
556 | struct adata *dst = lp_alloc_adata(pool, src->length); | |
557 | memcpy(dst->data, src->data, src->length); | |
558 | qsort(dst->data, dst->length / LCOMM_LENGTH, LCOMM_LENGTH, lc_set_cmp); | |
559 | return dst; | |
560 | } |