diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/Makefile | 4 | ||||
| -rw-r--r-- | lib/a-path.c | 905 | ||||
| -rw-r--r-- | lib/a-path_test.c | 206 | ||||
| -rw-r--r-- | lib/a-set.c | 695 | ||||
| -rw-r--r-- | lib/a-set_test.c | 240 | ||||
| -rw-r--r-- | lib/attrs.h | 230 |
6 files changed, 2278 insertions, 2 deletions
diff --git a/lib/Makefile b/lib/Makefile index 812f721c..853e0a22 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -1,7 +1,7 @@ -src := bitmap.c bitops.c blake2s.c blake2b.c checksum.c event.c flowspec.c idm.c ip.c lists.c mac.c md5.c mempool.c net.c patmatch.c printf.c resource.c sha1.c sha256.c sha512.c slab.c slists.c strtoul.c tbf.c timer.c xmalloc.c +src := a-path.c a-set.c bitmap.c bitops.c blake2s.c blake2b.c checksum.c event.c flowspec.c idm.c ip.c lists.c mac.c md5.c mempool.c net.c patmatch.c printf.c resource.c sha1.c sha256.c sha512.c slab.c slists.c strtoul.c tbf.c timer.c xmalloc.c obj := $(src-o-files) $(all-daemon) -tests_src := bitmap_test.c heap_test.c buffer_test.c event_test.c flowspec_test.c bitops_test.c patmatch_test.c fletcher16_test.c slist_test.c checksum_test.c lists_test.c mac_test.c ip_test.c hash_test.c printf_test.c slab_test.c +tests_src := a-set_test.c a-path_test.c bitmap_test.c heap_test.c buffer_test.c event_test.c flowspec_test.c bitops_test.c patmatch_test.c fletcher16_test.c slist_test.c checksum_test.c lists_test.c mac_test.c ip_test.c hash_test.c printf_test.c slab_test.c tests_targets := $(tests_targets) $(tests-target-files) tests_objs := $(tests_objs) $(src-o-files) diff --git a/lib/a-path.c b/lib/a-path.c new file mode 100644 index 00000000..0eca8475 --- /dev/null +++ b/lib/a-path.c @@ -0,0 +1,905 @@ +/* + * BIRD -- Path Operations + * + * (c) 2000 Martin Mares <mj@ucw.cz> + * (c) 2000 Pavel Machek <pavel@ucw.cz> + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#include "nest/bird.h" +#include "nest/rt.h" +#include "lib/attrs.h" +#include "lib/resource.h" +#include "lib/unaligned.h" +#include "lib/string.h" +#include "filter/data.h" + +// static inline void put_as(byte *data, u32 as) { put_u32(data, as); } +// static inline u32 get_as(byte *data) { return get_u32(data); } + +#define put_as put_u32 +#define get_as get_u32 +#define BS 4 /* Default block size of ASN (autonomous system number) */ + +#define BAD(DSC, VAL) ({ err_dsc = DSC; err_val = VAL; goto bad; }) + +int +as_path_valid(byte *data, uint len, int bs, int sets, int confed, char *err, uint elen) +{ + byte *pos = data; + char *err_dsc = NULL; + uint err_val = 0; + + while (len) + { + if (len < 2) + BAD("segment framing error", 0); + + /* Process one AS path segment */ + uint type = pos[0]; + uint slen = 2 + bs * pos[1]; + + if (len < slen) + BAD("segment framing error", len); + + switch (type) + { + case AS_PATH_SET: + if (!sets) + BAD("AS_SET segment", type); + break; + + case AS_PATH_SEQUENCE: + break; + + case AS_PATH_CONFED_SEQUENCE: + if (!confed) + BAD("AS_CONFED_SEQUENCE segment", type); + break; + + case AS_PATH_CONFED_SET: + if (!sets || !confed) + BAD("AS_CONFED_SET segment", type); + break; + + default: + BAD("unknown segment", type); + } + + if (pos[1] == 0) + BAD("zero-length segment", type); + + pos += slen; + len -= slen; + } + + return 1; + +bad: + if (err) + if (bsnprintf(err, elen, "%s (%u) at %d", err_dsc, err_val, (int) (pos - data)) < 0) + err[0] = 0; + + return 0; +} + +int +as_path_16to32(byte *dst, const byte *src, uint len) +{ + byte *dst0 = dst; + const byte *end = src + len; + uint i, n; + + while (src < end) + { + n = src[1]; + *dst++ = *src++; + *dst++ = *src++; + + for (i = 0; i < n; i++) + { + put_u32(dst, get_u16(src)); + src += 2; + dst += 4; + } + } + + return dst - dst0; +} + +int +as_path_32to16(byte *dst, const byte *src, uint len) +{ + byte *dst0 = dst; + const byte *end = src + len; + uint i, n; + + while (src < end) + { + n = src[1]; + *dst++ = *src++; + *dst++ = *src++; + + for (i = 0; i < n; i++) + { + put_u16(dst, get_u32(src)); + src += 4; + dst += 2; + } + } + + return dst - dst0; +} + +int +as_path_contains_as4(const struct adata *path) +{ + const byte *pos = path->data; + const byte *end = pos + path->length; + uint i, n; + + while (pos < end) + { + n = pos[1]; + pos += 2; + + for (i = 0; i < n; i++) + { + if (get_as(pos) > 0xFFFF) + return 1; + + pos += BS; + } + } + + return 0; +} + +int +as_path_contains_confed(const struct adata *path) +{ + const byte *pos = path->data; + const byte *end = pos + path->length; + + while (pos < end) + { + uint type = pos[0]; + uint slen = 2 + BS * pos[1]; + + if ((type == AS_PATH_CONFED_SEQUENCE) || + (type == AS_PATH_CONFED_SET)) + return 1; + + pos += slen; + } + + return 0; +} + +struct adata * +as_path_strip_confed(struct linpool *pool, const struct adata *path) +{ + struct adata *res = lp_alloc_adata(pool, path->length); + const byte *src = path->data; + const byte *end = src + path->length; + byte *dst = res->data; + + while (src < end) + { + uint type = src[0]; + uint slen = 2 + BS * src[1]; + + /* Copy regular segments */ + if ((type == AS_PATH_SET) || (type == AS_PATH_SEQUENCE)) + { + memcpy(dst, src, slen); + dst += slen; + } + + src += slen; + } + + /* Fix the result length */ + res->length = dst - res->data; + + return res; +} + +struct adata * +as_path_prepend2(struct linpool *pool, const struct adata *op, int seq, u32 as) +{ + struct adata *np; + const byte *pos = op->data; + uint len = op->length; + + if (len && (pos[0] == seq) && (pos[1] < 255)) + { + /* Starting with matching segment => just prepend the AS number */ + np = lp_alloc_adata(pool, len + BS); + np->data[0] = seq; + np->data[1] = pos[1] + 1; + put_as(np->data + 2, as); + + uint dlen = BS * pos[1]; + memcpy(np->data + 2 + BS, pos + 2, dlen); + ADVANCE(pos, len, 2 + dlen); + } + else + { + /* Create a new path segment */ + np = lp_alloc_adata(pool, len + 2 + BS); + np->data[0] = seq; + np->data[1] = 1; + put_as(np->data + 2, as); + } + + if (len) + { + byte *dst = np->data + 2 + BS * np->data[1]; + + memcpy(dst, pos, len); + } + + return np; +} + + +struct adata * +as_path_to_old(struct linpool *pool, const struct adata *path) +{ + struct adata *res = lp_alloc_adata(pool, path->length); + byte *pos = res->data; + byte *end = pos + res->length; + uint i, n; + u32 as; + + /* Copy the whole path */ + memcpy(res->data, path->data, path->length); + + /* Replace 32-bit AS numbers with AS_TRANS */ + while (pos < end) + { + n = pos[1]; + pos += 2; + + for (i = 0; i < n; i++) + { + as = get_as(pos); + if (as > 0xFFFF) + put_as(pos, AS_TRANS); + + pos += BS; + } + } + + return res; +} + +/* + * Cut the path to the length @num, measured to the usual path metric. Note that + * AS_CONFED_* segments have zero length and must be added if they are on edge. + */ +struct adata * +as_path_cut(struct linpool *pool, const struct adata *path, uint num) +{ + const byte *pos = path->data; + const byte *end = pos + path->length; + + while (pos < end) + { + uint t = pos[0]; + uint l = pos[1]; + uint n = 0; + + switch (t) + { + case AS_PATH_SET: n = 1; break; + case AS_PATH_SEQUENCE: n = l; break; + case AS_PATH_CONFED_SEQUENCE: n = 0; break; + case AS_PATH_CONFED_SET: n = 0; break; + default: bug("as_path_cut: Invalid path segment"); + } + + /* Cannot add whole segment, so try partial one and finish */ + if (num < n) + { + const byte *nend = pos; + if (num) + nend += 2 + BS * num; + + struct adata *res = lp_alloc_adata(pool, path->length); + res->length = nend - (const byte *) path->data; + memcpy(res->data, path->data, res->length); + + if (num) + { + byte *dpos = ((byte *) res->data) + (pos - (const byte *) path->data); + dpos[1] = num; + } + + return res; + } + + num -= n; + pos += 2 + BS * l; + } + + struct adata *res = lp_alloc_adata(pool, path->length); + res->length = path->length; + memcpy(res->data, path->data, res->length); + return res; +} + +/* + * Merge (concatenate) paths @p1 and @p2 and return the result. + * In contrast to other as_path_* functions, @p1 and @p2 may be reused. + */ +const struct adata * +as_path_merge(struct linpool *pool, const struct adata *p1, const struct adata *p2) +{ + if (p1->length == 0) + return p2; + + if (p2->length == 0) + return p1; + + struct adata *res = lp_alloc_adata(pool, p1->length + p2->length); + memcpy(res->data, p1->data, p1->length); + memcpy(res->data + p1->length, p2->data, p2->length); + + return res; +} + +void +as_path_format(const struct adata *path, byte *bb, uint size) +{ + buffer buf = { .start = bb, .pos = bb, .end = bb + size }, *b = &buf; + const byte *pos = path->data; + const byte *end = pos + path->length; + const char *ops, *cls; + + b->pos[0] = 0; + + while (pos < end) + { + uint type = pos[0]; + uint len = pos[1]; + pos += 2; + + switch (type) + { + case AS_PATH_SET: ops = "{"; cls = "}"; break; + case AS_PATH_SEQUENCE: ops = NULL; cls = NULL; break; + case AS_PATH_CONFED_SEQUENCE: ops = "("; cls = ")"; break; + case AS_PATH_CONFED_SET: ops = "({"; cls = "})"; break; + default: bug("Invalid path segment"); + } + + if (ops) + buffer_puts(b, ops); + + while (len--) + { + buffer_print(b, len ? "%u " : "%u", get_as(pos)); + pos += BS; + } + + if (cls) + buffer_puts(b, cls); + + if (pos < end) + buffer_puts(b, " "); + } + + /* Handle overflow */ + if (b->pos == b->end) + strcpy(b->end - 12, "..."); +} + +int +as_path_getlen(const struct adata *path) +{ + const byte *pos = path->data; + const byte *end = pos + path->length; + uint res = 0; + + while (pos < end) + { + uint t = pos[0]; + uint l = pos[1]; + uint n = 0; + + switch (t) + { + case AS_PATH_SET: n = 1; break; + case AS_PATH_SEQUENCE: n = l; break; + case AS_PATH_CONFED_SEQUENCE: n = 0; break; + case AS_PATH_CONFED_SET: n = 0; break; + default: bug("as_path_getlen: Invalid path segment"); + } + + res += n; + pos += 2 + BS * l; + } + + return res; +} + +int +as_path_get_last(const struct adata *path, u32 *orig_as) +{ + const byte *pos = path->data; + const byte *end = pos + path->length; + int found = 0; + u32 val = 0; + + while (pos < end) + { + uint type = pos[0]; + uint len = pos[1]; + pos += 2; + + if (!len) + continue; + + switch (type) + { + case AS_PATH_SET: + case AS_PATH_CONFED_SET: + found = 0; + break; + + case AS_PATH_SEQUENCE: + case AS_PATH_CONFED_SEQUENCE: + val = get_as(pos + BS * (len - 1)); + found = 1; + break; + + default: + bug("Invalid path segment"); + } + + pos += BS * len; + } + + if (found) + *orig_as = val; + return found; +} + +u32 +as_path_get_last_nonaggregated(const struct adata *path) +{ + const byte *pos = path->data; + const byte *end = pos + path->length; + u32 val = 0; + + while (pos < end) + { + uint type = pos[0]; + uint len = pos[1]; + pos += 2; + + if (!len) + continue; + + switch (type) + { + case AS_PATH_SET: + case AS_PATH_CONFED_SET: + return val; + + case AS_PATH_SEQUENCE: + case AS_PATH_CONFED_SEQUENCE: + val = get_as(pos + BS * (len - 1)); + break; + + default: + bug("Invalid path segment"); + } + + pos += BS * len; + } + + return val; +} + +int +as_path_get_first(const struct adata *path, u32 *last_as) +{ + const u8 *p = path->data; + + if ((path->length == 0) || (p[0] != AS_PATH_SEQUENCE) || (p[1] == 0)) + return 0; + + *last_as = get_as(p+2); + return 1; +} + +int +as_path_get_first_regular(const struct adata *path, u32 *last_as) +{ + const byte *pos = path->data; + const byte *end = pos + path->length; + + while (pos < end) + { + uint type = pos[0]; + uint len = pos[1]; + pos += 2; + + switch (type) + { + case AS_PATH_SET: + return 0; + + case AS_PATH_SEQUENCE: + if (len == 0) + return 0; + + *last_as = get_as(pos); + return 1; + + case AS_PATH_CONFED_SEQUENCE: + case AS_PATH_CONFED_SET: + break; + + default: + bug("Invalid path segment"); + } + + pos += BS * len; + } + + return 0; +} + +int +as_path_contains(const struct adata *path, u32 as, int min) +{ + const u8 *p = path->data; + const u8 *q = p+path->length; + int num = 0; + int i, n; + + while (p<q) + { + n = p[1]; + p += 2; + for(i=0; i<n; i++) + { + if (get_as(p) == as) + if (++num == min) + return 1; + p += BS; + } + } + return 0; +} + +int +as_path_match_set(const struct adata *path, const struct f_tree *set) +{ + const u8 *p = path->data; + const u8 *q = p+path->length; + int i, n; + + while (p<q) + { + n = p[1]; + p += 2; + for (i=0; i<n; i++) + { + struct f_val v = { .type = T_INT, .val.i = get_as(p)}; + if (find_tree(set, &v)) + return 1; + p += BS; + } + } + + return 0; +} + +const struct adata * +as_path_filter(struct linpool *pool, const struct adata *path, const struct f_tree *set, u32 key, int pos) +{ + if (!path) + return NULL; + + int len = path->length; + const u8 *p = path->data; + const u8 *q = path->data + len; + u8 *d, *d2; + int i, bt, sn, dn; + u8 buf[len]; + + d = buf; + while (p<q) + { + /* Read block header (type and length) */ + bt = p[0]; + sn = p[1]; + dn = 0; + p += 2; + d2 = d + 2; + + for (i = 0; i < sn; i++) + { + u32 as = get_as(p); + int match; + + if (set) + { + struct f_val v = { .type = T_INT, .val.i = as}; + match = !!find_tree(set, &v); + } + else + match = (as == key); + + if (match == pos) + { + put_as(d2, as); + d2 += BS; + dn++; + } + + p += BS; + } + + if (dn > 0) + { + /* Nonempty block, set block header and advance */ + d[0] = bt; + d[1] = dn; + d = d2; + } + } + + uint nl = d - buf; + if (nl == path->length) + return path; + + struct adata *res = lp_alloc(pool, sizeof(struct adata) + nl); + res->length = nl; + memcpy(res->data, buf, nl); + + return res; +} + + +struct pm_pos +{ + u8 set; + u8 mark; + union + { + const char *sp; + u32 asn; + } val; +}; + +static int +parse_path(const struct adata *path, struct pm_pos *pp) +{ + const byte *pos = path->data; + const byte *end = pos + path->length; + struct pm_pos *op = pp; + uint i; + + while (pos < end) + { + uint type = pos[0]; + uint len = pos[1]; + pos += 2; + + switch (type) + { + case AS_PATH_SET: + case AS_PATH_CONFED_SET: + pp->set = 1; + pp->mark = 0; + pp->val.sp = pos - 1; + pp++; + + pos += BS * len; + break; + + case AS_PATH_SEQUENCE: + case AS_PATH_CONFED_SEQUENCE: + for (i = 0; i < len; i++) + { + pp->set = 0; + pp->mark = 0; + pp->val.asn = get_as(pos); + pp++; + + pos += BS; + } + break; + + default: + bug("Invalid path segment"); + } + } + + return pp - op; +} + +static int +pm_match_val(const struct pm_pos *pos, u32 asn, u32 asn2) +{ + u32 gas; + if (! pos->set) + return ((pos->val.asn >= asn) && (pos->val.asn <= asn2)); + + const u8 *p = pos->val.sp; + int len = *p++; + int i; + + for (i = 0; i < len; i++) + { + gas = get_as(p + i * BS); + + if ((gas >= asn) && (gas <= asn2)) + return 1; + } + + return 0; +} + +static int +pm_match_set(const struct pm_pos *pos, const struct f_tree *set) +{ + struct f_val asn = { .type = T_INT }; + + if (! pos->set) + { + asn.val.i = pos->val.asn; + return !!find_tree(set, &asn); + } + + const u8 *p = pos->val.sp; + int len = *p++; + int i; + + for (i = 0; i < len; i++) + { + asn.val.i = get_as(p + i * BS); + if (find_tree(set, &asn)) + return 1; + } + + return 0; +} + +static inline int +pm_match(const struct pm_pos *pos, const struct f_path_mask_item *mask, u32 asn, u32 asn2) +{ + return ((mask->kind == PM_QUESTION) || + ((mask->kind != PM_ASN_SET) ? + pm_match_val(pos, asn, asn2) : + pm_match_set(pos, mask->set))); +} + +static void +pm_mark(struct pm_pos *pos, int *i, int plen, int *nl, int *nh) +{ + int j = *i; + + if (pos[j].set) + do { pos[j].mark = 1; j++; } + while ((j < plen) && pos[j].set); + else + j++; + + pos[j].mark = 1; + + /* Update low, high based on first and last marked pos */ + int l = pos[*i].set ? *i : j; + + *nl = (*nl < 0) ? l : MIN(*nl, l); + *nh = MAX(*nh, j); + *i = j; +} + +/* AS path matching is nontrivial. Because AS path can + * contain sets, it is not a plain wildcard matching. A set + * in an AS path is interpreted as it might represent any + * sequence of AS numbers from that set (possibly with + * repetitions). So it is also a kind of a pattern, + * more complicated than a path mask. + * + * The algorithm for AS path matching is a variant + * of nondeterministic finite state machine, where + * positions in AS path are states, and items in + * path mask are input for that finite state machine. + * During execution of the algorithm we maintain a set + * of marked states - a state is marked if it can be + * reached by any walk through NFSM with regard to + * currently processed part of input. When we process + * next part of mask, we advance each marked state. + * We start with marked first position, when we + * run out of marked positions, we reject. When + * we process the whole mask, we accept if final position + * (auxiliary position after last real position in AS path) + * is marked. + */ +int +as_path_match(const struct adata *path, const struct f_path_mask *mask) +{ + struct pm_pos pos[2048 + 1]; + int plen = parse_path(path, pos); + int l, h, i, nh, nl, last, loop; + u32 val = 0; + u32 val2 = 0; + + /* l and h are bound of interval of positions where + are marked states */ + + pos[plen].set = 0; + pos[plen].mark = 0; + + l = h = loop = 0; + pos[0].mark = 1; + + for (uint m=0; m < mask->len; m++) + { + /* We remove this mark to not step after pos[plen] */ + pos[plen].mark = 0; + + switch (mask->item[m].kind) + { + case PM_ASTERISK: + for (i = l; i <= plen; i++) + pos[i].mark = 1; + h = plen; + break; + + case PM_LOOP: + loop = 1; + break; + + case PM_ASN: /* Define single ASN as ASN..ASN - very narrow interval */ + val2 = val = mask->item[m].asn; + goto step; + case PM_ASN_EXPR: + bug("Expressions should be evaluated on AS path mask construction."); + case PM_ASN_RANGE: + val = mask->item[m].from; + val2 = mask->item[m].to; + goto step; + case PM_QUESTION: + case PM_ASN_SET: + step: + nh = nl = -1; + last = plen; + for (i = h; i >= l; i--) + if (pos[i].mark) + { + pos[i].mark = 0; + int j = i; + + match: + if (pm_match(pos + j, &mask->item[m], val, val2)) + { + pm_mark(pos, &j, plen, &nl, &nh); + if (loop && (j < last)) + goto match; + } + + last = i; + } + + if (nh < 0) + return 0; + + h = nh; + l = nl; + loop = 0; + break; + } + } + + return pos[plen].mark; +} diff --git a/lib/a-path_test.c b/lib/a-path_test.c new file mode 100644 index 00000000..38f77642 --- /dev/null +++ b/lib/a-path_test.c @@ -0,0 +1,206 @@ +/* + * BIRD -- Path Operations Tests + * + * (c) 2015 CZ.NIC z.s.p.o. + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#include "test/birdtest.h" +#include "test/bt-utils.h" + +#include "nest/rt.h" +#include "lib/attrs.h" +#include "lib/resource.h" + +#define TESTS_NUM 30 +#define AS_PATH_LENGTH 1000 + +#if AS_PATH_LENGTH > AS_PATH_MAXLEN +#warning "AS_PATH_LENGTH should be <= AS_PATH_MAXLEN" +#endif + +static int +t_as_path_match(void) +{ + int round; + for (round = 0; round < TESTS_NUM; round++) + { + struct adata empty_as_path = {}; + struct adata *as_path = &empty_as_path; + u32 first_prepended, last_prepended; + first_prepended = last_prepended = 0; + + struct f_path_mask *mask = alloca(sizeof(struct f_path_mask) + AS_PATH_LENGTH * sizeof(struct f_path_mask_item)); + mask->len = AS_PATH_LENGTH; + for (int i = AS_PATH_LENGTH - 1; i >= 0; i--) + { + u32 val = bt_random(); + as_path = as_path_prepend(tmp_linpool, as_path, val); + bt_debug("Prepending ASN: %10u \n", val); + + if (i == 0) + last_prepended = val; + if (i == AS_PATH_LENGTH-1) + first_prepended = val; + + mask->item[i].kind = PM_ASN; + mask->item[i].asn = val; + } + + bt_assert_msg(as_path_match(as_path, mask), "Mask should match with AS path"); + + u32 asn; + + bt_assert(as_path_get_first(as_path, &asn)); + bt_assert_msg(asn == last_prepended, "as_path_get_first() should return the last prepended ASN"); + + bt_assert(as_path_get_last(as_path, &asn)); + bt_assert_msg(asn == first_prepended, "as_path_get_last() should return the first prepended ASN"); + + tmp_flush(); + } + + return 1; +} + +static int +t_path_format(void) +{ + struct adata empty_as_path = {}; + struct adata *as_path = &empty_as_path; + + uint i; + for (i = 4294967285; i <= 4294967294; i++) + { + as_path = as_path_prepend(tmp_linpool, as_path, i); + bt_debug("Prepending ASN: %10u \n", i); + } + +#define BUFFER_SIZE 120 + byte buf[BUFFER_SIZE] = {}; + + as_path_format(&empty_as_path, buf, BUFFER_SIZE); + bt_assert_msg(strcmp(buf, "") == 0, "Buffer(%zu): '%s'", strlen(buf), buf); + + as_path_format(as_path, buf, BUFFER_SIZE); + bt_assert_msg(strcmp(buf, "4294967294 4294967293 4294967292 4294967291 4294967290 4294967289 4294967288 4294967287 4294967286 4294967285") == 0, "Buffer(%zu): '%s'", strlen(buf), buf); + +#define SMALL_BUFFER_SIZE 25 + byte buf2[SMALL_BUFFER_SIZE] = {}; + as_path_format(as_path, buf2, SMALL_BUFFER_SIZE); + bt_assert_msg(strcmp(buf2, "4294967294 42...") == 0, "Small Buffer(%zu): '%s'", strlen(buf2), buf2); + + tmp_flush(); + + return 1; +} + +static int +count_asn_in_array(const u32 *array, u32 asn) +{ + int counts_of_contains = 0; + int u; + for (u = 0; u < AS_PATH_LENGTH; u++) + if (array[u] == asn) + counts_of_contains++; + return counts_of_contains; +} + +static int +t_path_include(void) +{ + struct adata empty_as_path = {}; + struct adata *as_path = &empty_as_path; + + u32 as_nums[AS_PATH_LENGTH] = {}; + int i; + for (i = 0; i < AS_PATH_LENGTH; i++) + { + u32 val = bt_random(); + as_nums[i] = val; + as_path = as_path_prepend(tmp_linpool, as_path, val); + } + + for (i = 0; i < AS_PATH_LENGTH; i++) + { + int counts_of_contains = count_asn_in_array(as_nums, as_nums[i]); + bt_assert_msg(as_path_contains(as_path, as_nums[i], counts_of_contains), "AS Path should contains %d-times number %d", counts_of_contains, as_nums[i]); + + bt_assert(as_path_filter(tmp_linpool, as_path, NULL, as_nums[i], 0) != NULL); + bt_assert(as_path_filter(tmp_linpool, as_path, NULL, as_nums[i], 1) != NULL); + } + + for (i = 0; i < 10000; i++) + { + u32 test_val = bt_random(); + int counts_of_contains = count_asn_in_array(as_nums, test_val); + int result = as_path_contains(as_path, test_val, (counts_of_contains == 0 ? 1 : counts_of_contains)); + + if (counts_of_contains) + bt_assert_msg(result, "As path should contain %d-times the number %u", counts_of_contains, test_val); + else + bt_assert_msg(result == 0, "As path should not contain the number %u", test_val); + } + + tmp_flush(); + + return 1; +} + +#if 0 +static int +t_as_path_converting(void) +{ + struct adata empty_as_path = {}; + struct adata *as_path = &empty_as_path; +#define AS_PATH_LENGTH_FOR_CONVERTING_TEST 10 + + int i; + for (i = 0; i < AS_PATH_LENGTH_FOR_CONVERTING_TEST; i++) + as_path = as_path_prepend(tmp_linpool, as_path, i); + + bt_debug("data length: %u \n", as_path->length); + + byte buffer[100] = {}; + int used_size = as_path_convert_to_new(as_path, buffer, AS_PATH_LENGTH_FOR_CONVERTING_TEST-1); + bt_debug("as_path_convert_to_new: len %d \n%s\n", used_size, buffer); + for (i = 0; i < used_size; i++) + { + bt_debug("\\03%d", buffer[i]); + } + bt_debug("\n"); + bt_assert(memcmp(buffer, + "\032\039\030\030\030\030\030\030\030\039\030\030\030\030\030\030\030\038\030\030\030\030\030\030" + "\030\037\030\030\030\030\030\030\030\036\030\030\030\030", + 38)); + + bzero(buffer, sizeof(buffer)); + int new_used; + used_size = as_path_convert_to_old(as_path, buffer, &new_used); + bt_debug("as_path_convert_to_old: len %d, new_used: %d \n", used_size, new_used); + for (i = 0; i < used_size; i++) + { + bt_debug("\\03%d", buffer[i]); + } + bt_debug("\n"); + bt_assert(memcmp(buffer, + "\032\0310\030\039\030\038\030\037\030\036\030\035\030\034\030\033\030\032\030\031\030\030", + 22)); + + return 1; +} +#endif + +int +main(int argc, char *argv[]) +{ + bt_init(argc, argv); + + bt_test_suite(t_as_path_match, "Testing AS path matching and some a-path utilities."); + bt_test_suite(t_path_format, "Testing formating as path into byte buffer"); + bt_test_suite(t_path_include, "Testing including a AS number in AS path"); + // bt_test_suite(t_as_path_converting, "Testing as_path_convert_to_*() output constancy"); + + return bt_exit_value(); +} diff --git a/lib/a-set.c b/lib/a-set.c new file mode 100644 index 00000000..8ede9b83 --- /dev/null +++ b/lib/a-set.c @@ -0,0 +1,695 @@ +/* + * BIRD -- Set/Community-list Operations + * + * (c) 2000 Martin Mares <mj@ucw.cz> + * (c) 2000 Pavel Machek <pavel@ucw.cz> + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#include <stdlib.h> + +#include "nest/bird.h" +#include "nest/rt.h" +#include "lib/attrs.h" +#include "lib/resource.h" +#include "lib/string.h" + +/** + * int_set_format - format an &set for printing + * @set: set attribute to be formatted + * @way: style of format (0 for router ID list, 1 for community list) + * @from: starting position in set + * @buf: destination buffer + * @size: size of buffer + * + * This function takes a set attribute and formats it. @way specifies + * the style of format (router ID / community). @from argument can be + * used to specify the first printed value for the purpose of printing + * untruncated sets even with smaller buffers. If the output fits in + * the buffer, 0 is returned, otherwise the position of the first not + * printed item is returned. This value can be used as @from argument + * in subsequent calls. If truncated output suffices, -1 can be + * instead used as @from, in that case " ..." is eventually added at + * the buffer to indicate truncation. + */ +int +int_set_format(const struct adata *set, int way, int from, byte *buf, uint size) +{ + u32 *z = (u32 *) set->data; + byte *end = buf + size - 24; + int from2 = MAX(from, 0); + int to = set->length / 4; + int i; + + for (i = from2; i < to; i++) + { + if (buf > end) + { + if (from < 0) + strcpy(buf, " ..."); + else + *buf = 0; + return i; + } + + if (i > from2) + *buf++ = ' '; + + if (way) + buf += bsprintf(buf, "(%d,%d)", z[i] >> 16, z[i] & 0xffff); + else + buf += bsprintf(buf, "%R", z[i]); + } + *buf = 0; + return 0; +} + +int +ec_format(byte *buf, u64 ec) +{ + u32 type, key, val; + char tbuf[16]; + const char *kind; + + type = ec >> 48; + kind = ec_subtype_str(type & 0xf0ff); + + if (!kind) { + bsprintf(tbuf, "unknown 0x%x", type); + kind = tbuf; + } + + switch (ec >> 56) + { + /* RFC 4360 3.1. Two-Octet AS Specific Extended Community */ + case 0x00: + case 0x40: + key = (ec >> 32) & 0xFFFF; + val = ec; + return bsprintf(buf, "(%s, %u, %u)", kind, key, val); + + /* RFC 4360 3.2. IPv4 Address Specific Extended Community */ + case 0x01: + case 0x41: + key = ec >> 16; + val = ec & 0xFFFF; + return bsprintf(buf, "(%s, %R, %u)", kind, key, val); + + /* RFC 5668 4-Octet AS Specific BGP Extended Community */ + case 0x02: + case 0x42: + key = ec >> 16; + val = ec & 0xFFFF; + return bsprintf(buf, "(%s, %u, %u)", kind, key, val); + + /* Generic format for unknown kinds of extended communities */ + default: + key = ec >> 32; + val = ec; + return bsprintf(buf, "(generic, 0x%x, 0x%x)", key, val); + } + +} + +int +ec_set_format(const struct adata *set, int from, byte *buf, uint size) +{ + u32 *z = int_set_get_data(set); + byte *end = buf + size - 64; + int from2 = MAX(from, 0); + int to = int_set_get_size(set); + int i; + + for (i = from2; i < to; i += 2) + { + if (buf > end) + { + if (from < 0) + strcpy(buf, " ..."); + else + *buf = 0; + return i; + } + + if (i > from2) + *buf++ = ' '; + + buf += ec_format(buf, ec_get(z, i)); + } + *buf = 0; + return 0; +} + +int +lc_format(byte *buf, lcomm lc) +{ + return bsprintf(buf, "(%u, %u, %u)", lc.asn, lc.ldp1, lc.ldp2); +} + +int +lc_set_format(const struct adata *set, int from, byte *buf, uint bufsize) +{ + u32 *d = (u32 *) set->data; + byte *end = buf + bufsize - 64; + int from2 = MAX(from, 0); + int to = set->length / 4; + int i; + + for (i = from2; i < to; i += 3) + { + if (buf > end) + { + if (from < 0) + strcpy(buf, "..."); + else + buf[-1] = 0; + return i; + } + + buf += bsprintf(buf, "(%u, %u, %u)", d[i], d[i+1], d[i+2]); + *buf++ = ' '; + } + + if (i != from2) + buf--; + + *buf = 0; + return 0; +} + +int +int_set_contains(const struct adata *list, u32 val) +{ + if (!list) + return 0; + + u32 *l = (u32 *) list->data; + int len = int_set_get_size(list); + int i; + + for (i = 0; i < len; i++) + if (*l++ == val) + return 1; + + return 0; +} + +int +ec_set_contains(const struct adata *list, u64 val) +{ + if (!list) + return 0; + + u32 *l = int_set_get_data(list); + int len = int_set_get_size(list); + u32 eh = ec_hi(val); + u32 el = ec_lo(val); + int i; + + for (i=0; i < len; i += 2) + if (l[i] == eh && l[i+1] == el) + return 1; + + return 0; +} + +int +lc_set_contains(const struct adata *list, lcomm val) +{ + if (!list) + return 0; + + u32 *l = int_set_get_data(list); + int len = int_set_get_size(list); + int i; + + for (i = 0; i < len; i += 3) + if (lc_match(l, i, val)) + return 1; + + return 0; +} + +const struct adata * +int_set_prepend(struct linpool *pool, const struct adata *list, u32 val) +{ + struct adata *res; + int len; + + if (int_set_contains(list, val)) + return list; + + len = list ? list->length : 0; + res = lp_alloc(pool, sizeof(struct adata) + len + 4); + res->length = len + 4; + + if (list) + memcpy(res->data + 4, list->data, list->length); + + * (u32 *) res->data = val; + + return res; +} + +const struct adata * +int_set_add(struct linpool *pool, const struct adata *list, u32 val) +{ + struct adata *res; + int len; + + if (int_set_contains(list, val)) + return list; + + len = list ? list->length : 0; + res = lp_alloc(pool, sizeof(struct adata) + len + 4); + res->length = len + 4; + + if (list) + memcpy(res->data, list->data, list->length); + + * (u32 *) (res->data + len) = val; + + return res; +} + +const struct adata * +ec_set_add(struct linpool *pool, const struct adata *list, u64 val) +{ + if (ec_set_contains(list, val)) + return list; + + int olen = list ? list->length : 0; + struct adata *res = lp_alloc(pool, sizeof(struct adata) + olen + 8); + res->length = olen + 8; + + if (list) + memcpy(res->data, list->data, list->length); + + u32 *l = (u32 *) (res->data + olen); + l[0] = ec_hi(val); + l[1] = ec_lo(val); + + return res; +} + +const struct adata * +lc_set_add(struct linpool *pool, const struct adata *list, lcomm val) +{ + if (lc_set_contains(list, val)) + return list; + + int olen = list ? list->length : 0; + struct adata *res = lp_alloc(pool, sizeof(struct adata) + olen + LCOMM_LENGTH); + res->length = olen + LCOMM_LENGTH; + + if (list) + memcpy(res->data, list->data, list->length); + + lc_put((u32 *) (res->data + olen), val); + + return res; +} + +const struct adata * +int_set_del(struct linpool *pool, const struct adata *list, u32 val) +{ + if (!int_set_contains(list, val)) + return list; + + struct adata *res; + res = lp_alloc(pool, sizeof(struct adata) + list->length - 4); + res->length = list->length - 4; + + u32 *l = int_set_get_data(list); + u32 *k = int_set_get_data(res); + int len = int_set_get_size(list); + int i; + + for (i = 0; i < len; i++) + if (l[i] != val) + *k++ = l[i]; + + return res; +} + +const struct adata * +ec_set_del(struct linpool *pool, const struct adata *list, u64 val) +{ + if (!ec_set_contains(list, val)) + return list; + + struct adata *res; + res = lp_alloc(pool, sizeof(struct adata) + list->length - 8); + res->length = list->length - 8; + + u32 *l = int_set_get_data(list); + u32 *k = int_set_get_data(res); + int len = int_set_get_size(list); + u32 eh = ec_hi(val); + u32 el = ec_lo(val); + int i; + + for (i=0; i < len; i += 2) + if (! (l[i] == eh && l[i+1] == el)) + { + *k++ = l[i]; + *k++ = l[i+1]; + } + + return res; +} + +const struct adata * +lc_set_del(struct linpool *pool, const struct adata *list, lcomm val) +{ + if (!lc_set_contains(list, val)) + return list; + + struct adata *res; + res = lp_alloc(pool, sizeof(struct adata) + list->length - LCOMM_LENGTH); + res->length = list->length - LCOMM_LENGTH; + + u32 *l = int_set_get_data(list); + u32 *k = int_set_get_data(res); + int len = int_set_get_size(list); + int i; + + for (i=0; i < len; i += 3) + if (! lc_match(l, i, val)) + k = lc_copy(k, l+i); + + return res; +} + +const struct adata * +int_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2) +{ + if (!l1) + return l2; + if (!l2) + return l1; + + struct adata *res; + int len = int_set_get_size(l2); + u32 *l = int_set_get_data(l2); + u32 tmp[len]; + u32 *k = tmp; + int i; + + for (i = 0; i < len; i++) + if (!int_set_contains(l1, l[i])) + *k++ = l[i]; + + if (k == tmp) + return l1; + + len = (k - tmp) * 4; + res = lp_alloc(pool, sizeof(struct adata) + l1->length + len); + res->length = l1->length + len; + memcpy(res->data, l1->data, l1->length); + memcpy(res->data + l1->length, tmp, len); + return res; +} + +const struct adata * +ec_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2) +{ + if (!l1) + return l2; + if (!l2) + return l1; + + struct adata *res; + int len = int_set_get_size(l2); + u32 *l = int_set_get_data(l2); + u32 tmp[len]; + u32 *k = tmp; + int i; + + for (i = 0; i < len; i += 2) + if (!ec_set_contains(l1, ec_get(l, i))) + { + *k++ = l[i]; + *k++ = l[i+1]; + } + + if (k == tmp) + return l1; + + len = (k - tmp) * 4; + res = lp_alloc(pool, sizeof(struct adata) + l1->length + len); + res->length = l1->length + len; + memcpy(res->data, l1->data, l1->length); + memcpy(res->data + l1->length, tmp, len); + return res; +} + +const struct adata * +lc_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2) +{ + if (!l1) + return l2; + if (!l2) + return l1; + + struct adata *res; + int len = int_set_get_size(l2); + u32 *l = int_set_get_data(l2); + u32 tmp[len]; + u32 *k = tmp; + int i; + + for (i = 0; i < len; i += 3) + if (!lc_set_contains(l1, lc_get(l, i))) + k = lc_copy(k, l+i); + + if (k == tmp) + return l1; + + len = (k - tmp) * 4; + res = lp_alloc(pool, sizeof(struct adata) + l1->length + len); + res->length = l1->length + len; + memcpy(res->data, l1->data, l1->length); + memcpy(res->data + l1->length, tmp, len); + return res; +} + + +struct adata * +ec_set_del_nontrans(struct linpool *pool, const struct adata *set) +{ + adata *res = lp_alloc_adata(pool, set->length); + u32 *src = int_set_get_data(set); + u32 *dst = int_set_get_data(res); + int len = int_set_get_size(set); + int i; + + /* Remove non-transitive communities (EC_TBIT set) */ + for (i = 0; i < len; i += 2) + { + if (src[i] & EC_TBIT) + continue; + + *dst++ = src[i]; + *dst++ = src[i+1]; + } + + res->length = ((byte *) dst) - res->data; + + return res; +} + +static int +int_set_cmp(const void *X, const void *Y) +{ + const u32 *x = X, *y = Y; + return (*x < *y) ? -1 : (*x > *y) ? 1 : 0; +} + +struct adata * +int_set_sort(struct linpool *pool, const struct adata *src) +{ + struct adata *dst = lp_alloc_adata(pool, src->length); + memcpy(dst->data, src->data, src->length); + qsort(dst->data, dst->length / 4, 4, int_set_cmp); + return dst; +} + +int +int_set_min(const struct adata *list, u32 *val) +{ + if (!list) + return 0; + + u32 *l = (u32 *) list->data; + int len = int_set_get_size(list); + int i; + + if (len < 1) + return 0; + + *val = *l++; + for (i = 1; i < len; i++, l++) + if (int_set_cmp(val, l) > 0) + *val = *l; + + return 1; +} + +int +int_set_max(const struct adata *list, u32 *val) +{ + if (!list) + return 0; + + u32 *l = (u32 *) list->data; + int len = int_set_get_size(list); + int i; + + if (len < 1) + return 0; + + *val = *l++; + for (i = 1; i < len; i++, l++) + if (int_set_cmp(val, l) < 0) + *val = *l; + + return 1; +} + + +static int +ec_set_cmp(const void *X, const void *Y) +{ + u64 x = ec_get(X, 0); + u64 y = ec_get(Y, 0); + return (x < y) ? -1 : (x > y) ? 1 : 0; +} + +struct adata * +ec_set_sort(struct linpool *pool, const struct adata *src) +{ + struct adata *dst = lp_alloc_adata(pool, src->length); + memcpy(dst->data, src->data, src->length); + qsort(dst->data, dst->length / 8, 8, ec_set_cmp); + return dst; +} + +void +ec_set_sort_x(struct adata *set) +{ + /* Sort in place */ + qsort(set->data, set->length / 8, 8, ec_set_cmp); +} + +int +ec_set_min(const struct adata *list, u64 *val) +{ + if (!list) + return 0; + + u32 *l = int_set_get_data(list); + int len = int_set_get_size(list); + int i; + + if (len < 1) + return 0; + + u32 *res = l; l += 2; + for (i = 2; i < len; i += 2, l += 2) + if (ec_set_cmp(res, l) > 0) + res = l; + + *val = ec_generic(res[0], res[1]); + return 1; +} + +int +ec_set_max(const struct adata *list, u64 *val) +{ + if (!list) + return 0; + + u32 *l = int_set_get_data(list); + int len = int_set_get_size(list); + int i; + + if (len < 1) + return 0; + + u32 *res = l; l += 2; + for (i = 2; i < len; i += 2, l += 2) + if (ec_set_cmp(res, l) < 0) + res = l; + + *val = ec_generic(res[0], res[1]); + return 1; +} + + +static int +lc_set_cmp(const void *X, const void *Y) +{ + const u32 *x = X, *y = Y; + if (x[0] != y[0]) + return (x[0] > y[0]) ? 1 : -1; + if (x[1] != y[1]) + return (x[1] > y[1]) ? 1 : -1; + if (x[2] != y[2]) + return (x[2] > y[2]) ? 1 : -1; + return 0; +} + +struct adata * +lc_set_sort(struct linpool *pool, const struct adata *src) +{ + struct adata *dst = lp_alloc_adata(pool, src->length); + memcpy(dst->data, src->data, src->length); + qsort(dst->data, dst->length / LCOMM_LENGTH, LCOMM_LENGTH, lc_set_cmp); + return dst; +} + +int +lc_set_min(const struct adata *list, lcomm *val) +{ + if (!list) + return 0; + + u32 *l = int_set_get_data(list); + int len = int_set_get_size(list); + int i; + + if (len < 1) + return 0; + + u32 *res = l; l += 3; + for (i = 3; i < len; i += 3, l += 3) + if (lc_set_cmp(res, l) > 0) + res = l; + + *val = (lcomm) { res[0], res[1], res[2] }; + return 1; +} + +int +lc_set_max(const struct adata *list, lcomm *val) +{ + if (!list) + return 0; + + u32 *l = int_set_get_data(list); + int len = int_set_get_size(list); + int i; + + if (len < 1) + return 0; + + u32 *res = l; l += 3; + for (i = 3; i < len; i += 3, l += 3) + if (lc_set_cmp(res, l) < 0) + res = l; + + *val = (lcomm) { res[0], res[1], res[2] }; + return 1; +} diff --git a/lib/a-set_test.c b/lib/a-set_test.c new file mode 100644 index 00000000..3280031f --- /dev/null +++ b/lib/a-set_test.c @@ -0,0 +1,240 @@ +/* + * BIRD -- Set/Community-list Operations Tests + * + * (c) 2015 CZ.NIC z.s.p.o. + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#include "test/birdtest.h" +#include "test/bt-utils.h" + +#include "lib/net.h" +#include "nest/rt.h" +#include "lib/attrs.h" +#include "lib/resource.h" + +#define SET_SIZE 10 +static const struct adata *set_sequence; /* <0; SET_SIZE) */ +static const struct adata *set_sequence_same; /* <0; SET_SIZE) */ +static const struct adata *set_sequence_higher; /* <SET_SIZE; 2*SET_SIZE) */ +static const struct adata *set_random; + +#define BUFFER_SIZE 1000 +static byte buf[BUFFER_SIZE] = {}; + +#define SET_SIZE_FOR_FORMAT_OUTPUT 10 + +enum set_type +{ + SET_TYPE_INT, + SET_TYPE_EC +}; + +static void +generate_set_sequence(enum set_type type, int len) +{ + struct adata empty_as_path = {}; + set_sequence = set_sequence_same = set_sequence_higher = set_random = &empty_as_path; + + int i; + for (i = 0; i < len; i++) + { + if (type == SET_TYPE_INT) + { + set_sequence = int_set_add(tmp_linpool, set_sequence, i); + set_sequence_same = int_set_add(tmp_linpool, set_sequence_same, i); + set_sequence_higher = int_set_add(tmp_linpool, set_sequence_higher, i + SET_SIZE); + set_random = int_set_add(tmp_linpool, set_random, bt_random()); + } + else if (type == SET_TYPE_EC) + { + set_sequence = ec_set_add(tmp_linpool, set_sequence, i); + set_sequence_same = ec_set_add(tmp_linpool, set_sequence_same, i); + set_sequence_higher = ec_set_add(tmp_linpool, set_sequence_higher, i + SET_SIZE); + set_random = ec_set_add(tmp_linpool, set_random, (bt_random() << 32 | bt_random())); + } + else + bt_abort_msg("This should be unreachable"); + } +} + +/* + * SET INT TESTS + */ + +static int +t_set_int_contains(void) +{ + int i; + + generate_set_sequence(SET_TYPE_INT, SET_SIZE); + + bt_assert(int_set_get_size(set_sequence) == SET_SIZE); + + for (i = 0; i < SET_SIZE; i++) + bt_assert(int_set_contains(set_sequence, i)); + bt_assert(int_set_contains(set_sequence, -1) == 0); + bt_assert(int_set_contains(set_sequence, SET_SIZE) == 0); + + int *data = int_set_get_data(set_sequence); + for (i = 0; i < SET_SIZE; i++) + bt_assert_msg(data[i] == i, "(data[i] = %d) == i = %d)", data[i], i); + + return 1; +} + +static int +t_set_int_union(void) +{ + generate_set_sequence(SET_TYPE_INT, SET_SIZE); + + const struct adata *set_union; + set_union = int_set_union(tmp_linpool, set_sequence, set_sequence_same); + bt_assert(int_set_get_size(set_union) == SET_SIZE); + bt_assert(int_set_format(set_union, 0, 2, buf, BUFFER_SIZE) == 0); + + set_union = int_set_union(tmp_linpool, set_sequence, set_sequence_higher); + bt_assert_msg(int_set_get_size(set_union) == SET_SIZE*2, "int_set_get_size(set_union) %d, SET_SIZE*2 %d", int_set_get_size(set_union), SET_SIZE*2); + bt_assert(int_set_format(set_union, 0, 2, buf, BUFFER_SIZE) == 0); + + return 1; +} + +static int +t_set_int_format(void) +{ + generate_set_sequence(SET_TYPE_INT, SET_SIZE_FOR_FORMAT_OUTPUT); + + bt_assert(int_set_format(set_sequence, 0, 0, buf, BUFFER_SIZE) == 0); + bt_assert(strcmp(buf, "0.0.0.0 0.0.0.1 0.0.0.2 0.0.0.3 0.0.0.4 0.0.0.5 0.0.0.6 0.0.0.7 0.0.0.8 0.0.0.9") == 0); + + bzero(buf, BUFFER_SIZE); + bt_assert(int_set_format(set_sequence, 0, 2, buf, BUFFER_SIZE) == 0); + bt_assert(strcmp(buf, "0.0.0.2 0.0.0.3 0.0.0.4 0.0.0.5 0.0.0.6 0.0.0.7 0.0.0.8 0.0.0.9") == 0); + + bzero(buf, BUFFER_SIZE); + bt_assert(int_set_format(set_sequence, 1, 0, buf, BUFFER_SIZE) == 0); + bt_assert(strcmp(buf, "(0,0) (0,1) (0,2) (0,3) (0,4) (0,5) (0,6) (0,7) (0,8) (0,9)") == 0); + + return 1; +} + +static int +t_set_int_delete(void) +{ + generate_set_sequence(SET_TYPE_INT, SET_SIZE); + + const struct adata *deleting_sequence = set_sequence; + u32 i; + for (i = 0; i < SET_SIZE; i++) + { + deleting_sequence = int_set_del(tmp_linpool, deleting_sequence, i); + bt_assert_msg(int_set_get_size(deleting_sequence) == (int) (SET_SIZE-1-i), + "int_set_get_size(deleting_sequence) %d == SET_SIZE-1-i %d", + int_set_get_size(deleting_sequence), + SET_SIZE-1-i); + } + + bt_assert(int_set_get_size(set_sequence) == SET_SIZE); + + return 1; +} + +/* + * SET EC TESTS + */ + +static int +t_set_ec_contains(void) +{ + u32 i; + + generate_set_sequence(SET_TYPE_EC, SET_SIZE); + + bt_assert(ec_set_get_size(set_sequence) == SET_SIZE); + + for (i = 0; i < SET_SIZE; i++) + bt_assert(ec_set_contains(set_sequence, i)); + bt_assert(ec_set_contains(set_sequence, -1) == 0); + bt_assert(ec_set_contains(set_sequence, SET_SIZE) == 0); + +// int *data = ec_set_get_data(set_sequence); +// for (i = 0; i < SET_SIZE; i++) +// bt_assert_msg(data[i] == (SET_SIZE-1-i), "(data[i] = %d) == ((SET_SIZE-1-i) = %d)", data[i], SET_SIZE-1-i); + + return 1; +} + +static int +t_set_ec_union(void) +{ + generate_set_sequence(SET_TYPE_EC, SET_SIZE); + + const struct adata *set_union; + set_union = ec_set_union(tmp_linpool, set_sequence, set_sequence_same); + bt_assert(ec_set_get_size(set_union) == SET_SIZE); + bt_assert(ec_set_format(set_union, 0, buf, BUFFER_SIZE) == 0); + + set_union = ec_set_union(tmp_linpool, set_sequence, set_sequence_higher); + bt_assert_msg(ec_set_get_size(set_union) == SET_SIZE*2, "ec_set_get_size(set_union) %d, SET_SIZE*2 %d", ec_set_get_size(set_union), SET_SIZE*2); + bt_assert(ec_set_format(set_union, 0, buf, BUFFER_SIZE) == 0); + + return 1; +} + +static int +t_set_ec_format(void) +{ + const struct adata empty_as_path = {}; + set_sequence = set_sequence_same = set_sequence_higher = set_random = &empty_as_path; + + u64 i = 0; + set_sequence = ec_set_add(tmp_linpool, set_sequence, i); + for (i = 1; i < SET_SIZE_FOR_FORMAT_OUTPUT; i++) + set_sequence = ec_set_add(tmp_linpool, set_sequence, i + ((i%2) ? ((u64)EC_RO << 48) : ((u64)EC_RT << 48))); + + bt_assert(ec_set_format(set_sequence, 0, buf, BUFFER_SIZE) == 0); + bt_assert_msg(strcmp(buf, "(unknown 0x0, 0, 0) (ro, 0, 1) (rt, 0, 2) (ro, 0, 3) (rt, 0, 4) (ro, 0, 5) (rt, 0, 6) (ro, 0, 7) (rt, 0, 8) (ro, 0, 9)") == 0, + "ec_set_format() returns '%s'", buf); + + return 1; +} + +static int +t_set_ec_delete(void) +{ + generate_set_sequence(SET_TYPE_EC, SET_SIZE); + + const struct adata *deleting_sequence = set_sequence; + u32 i; + for (i = 0; i < SET_SIZE; i++) + { + deleting_sequence = ec_set_del(tmp_linpool, deleting_sequence, i); + bt_assert_msg(ec_set_get_size(deleting_sequence) == (int) (SET_SIZE-1-i), + "ec_set_get_size(deleting_sequence) %d == SET_SIZE-1-i %d", + ec_set_get_size(deleting_sequence), SET_SIZE-1-i); + } + + bt_assert(ec_set_get_size(set_sequence) == SET_SIZE); + + return 1; +} + +int +main(int argc, char *argv[]) +{ + bt_init(argc, argv); + + bt_test_suite(t_set_int_contains, "Testing sets of integers: contains, get_data"); + bt_test_suite(t_set_int_format, "Testing sets of integers: format"); + bt_test_suite(t_set_int_union, "Testing sets of integers: union"); + bt_test_suite(t_set_int_delete, "Testing sets of integers: delete"); + + bt_test_suite(t_set_ec_contains, "Testing sets of Extended Community values: contains, get_data"); + bt_test_suite(t_set_ec_format, "Testing sets of Extended Community values: format"); + bt_test_suite(t_set_ec_union, "Testing sets of Extended Community values: union"); + bt_test_suite(t_set_ec_delete, "Testing sets of Extended Community values: delete"); + + return bt_exit_value(); +} diff --git a/lib/attrs.h b/lib/attrs.h new file mode 100644 index 00000000..e0595846 --- /dev/null +++ b/lib/attrs.h @@ -0,0 +1,230 @@ +/* + * BIRD Internet Routing Daemon -- Attribute Operations + * + * (c) 2000 Martin Mares <mj@ucw.cz> + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#ifndef _BIRD_ATTRS_H_ +#define _BIRD_ATTRS_H_ + +#include <stdint.h> +#include "lib/unaligned.h" +#include "lib/route.h" + + +/* a-path.c */ + +#define AS_PATH_SET 1 /* Types of path segments */ +#define AS_PATH_SEQUENCE 2 +#define AS_PATH_CONFED_SEQUENCE 3 +#define AS_PATH_CONFED_SET 4 + +#define AS_PATH_MAXLEN 10000 + +#define AS_TRANS 23456 +/* AS_TRANS is used when we need to store 32bit ASN larger than 0xFFFF + * to 16bit slot (like in 16bit AS_PATH). See RFC 4893 for details + */ + +struct f_tree; + +int as_path_valid(byte *data, uint len, int bs, int sets, int confed, char *err, uint elen); +int as_path_16to32(byte *dst, const byte *src, uint len); +int as_path_32to16(byte *dst, const byte *src, uint len); +int as_path_contains_as4(const struct adata *path); +int as_path_contains_confed(const struct adata *path); +struct adata *as_path_strip_confed(struct linpool *pool, const struct adata *op); +struct adata *as_path_prepend2(struct linpool *pool, const struct adata *op, int seq, u32 as); +struct adata *as_path_to_old(struct linpool *pool, const struct adata *path); +struct adata *as_path_cut(struct linpool *pool, const struct adata *path, uint num); +const struct adata *as_path_merge(struct linpool *pool, const struct adata *p1, const struct adata *p2); +void as_path_format(const struct adata *path, byte *buf, uint size); +int as_path_getlen(const struct adata *path); +int as_path_getlen_int(const struct adata *path, int bs); +int as_path_get_first(const struct adata *path, u32 *orig_as); +int as_path_get_first_regular(const struct adata *path, u32 *last_as); +int as_path_get_last(const struct adata *path, u32 *last_as); +u32 as_path_get_last_nonaggregated(const struct adata *path); +int as_path_contains(const struct adata *path, u32 as, int min); +int as_path_match_set(const struct adata *path, const struct f_tree *set); +const struct adata *as_path_filter(struct linpool *pool, const struct adata *path, const struct f_tree *set, u32 key, int pos); + +static inline struct adata *as_path_prepend(struct linpool *pool, const struct adata *path, u32 as) +{ return as_path_prepend2(pool, path, AS_PATH_SEQUENCE, as); } + + +#define PM_ASN 0 +#define PM_QUESTION 1 +#define PM_ASTERISK 2 +#define PM_ASN_EXPR 3 +#define PM_ASN_RANGE 4 +#define PM_ASN_SET 5 +#define PM_LOOP 6 + +struct f_path_mask_item { + union { + u32 asn; /* PM_ASN */ + const struct f_line *expr; /* PM_ASN_EXPR */ + const struct f_tree *set; /* PM_ASN_SET */ + struct { /* PM_ASN_RANGE */ + u32 from; + u32 to; + }; + }; + int kind; +}; + +struct f_path_mask { + uint len; + struct f_path_mask_item item[0]; +}; + +int as_path_match(const struct adata *path, const struct f_path_mask *mask); + + +/* Counterparts to appropriate as_path_* functions */ + +static inline int +aggregator_16to32(byte *dst, const byte *src) +{ + put_u32(dst, get_u16(src)); + memcpy(dst+4, src+2, 4); + return 8; +} + +static inline int +aggregator_32to16(byte *dst, const byte *src) +{ + put_u16(dst, get_u32(src)); + memcpy(dst+2, src+4, 4); + return 6; +} + +static inline int +aggregator_contains_as4(const struct adata *a) +{ + return get_u32(a->data) > 0xFFFF; +} + +static inline struct adata * +aggregator_to_old(struct linpool *pool, const struct adata *a) +{ + struct adata *d = lp_alloc_adata(pool, 8); + put_u32(d->data, AS_TRANS); + memcpy(d->data + 4, a->data + 4, 4); + return d; +} + + +/* a-set.c */ + + +/* Extended Community subtypes (kinds) */ +enum ec_subtype { + EC_RT = 0x0002, + EC_RO = 0x0003, + EC_GENERIC = 0xFFFF, +}; + +static inline const char *ec_subtype_str(const enum ec_subtype ecs) { + switch (ecs) { + case EC_RT: return "rt"; + case EC_RO: return "ro"; + default: return NULL; + } +} + +/* Transitive bit (for first u32 half of EC) */ +#define EC_TBIT 0x40000000 + +#define ECOMM_LENGTH 8 + +static inline int int_set_get_size(const struct adata *list) +{ return list->length / 4; } + +static inline int ec_set_get_size(const struct adata *list) +{ return list->length / 8; } + +static inline int lc_set_get_size(const struct adata *list) +{ return list->length / 12; } + +static inline u32 *int_set_get_data(const struct adata *list) +{ return (u32 *) list->data; } + +static inline u32 ec_hi(u64 ec) { return ec >> 32; } +static inline u32 ec_lo(u64 ec) { return ec; } +static inline u64 ec_get(const u32 *l, int i) +{ return (((u64) l[i]) << 32) | l[i+1]; } + +/* RFC 4360 3.1. Two-Octet AS Specific Extended Community */ +static inline u64 ec_as2(enum ec_subtype kind, u64 key, u64 val) +{ return (((u64) kind | 0x0000) << 48) | (key << 32) | val; } + +/* RFC 5668 4-Octet AS Specific BGP Extended Community */ +static inline u64 ec_as4(enum ec_subtype kind, u64 key, u64 val) +{ return (((u64) kind | 0x0200) << 48) | (key << 16) | val; } + +/* RFC 4360 3.2. IPv4 Address Specific Extended Community */ +static inline u64 ec_ip4(enum ec_subtype kind, u64 key, u64 val) +{ return (((u64) kind | 0x0100) << 48) | (key << 16) | val; } + +static inline u64 ec_generic(u64 key, u64 val) +{ return (key << 32) | val; } + +/* Large community value */ +typedef struct lcomm { + u32 asn; + u32 ldp1; + u32 ldp2; +} lcomm; + +#define LCOMM_LENGTH 12 + +static inline lcomm lc_get(const u32 *l, int i) +{ return (lcomm) { l[i], l[i+1], l[i+2] }; } + +static inline void lc_put(u32 *l, lcomm v) +{ l[0] = v.asn; l[1] = v.ldp1; l[2] = v.ldp2; } + +static inline int lc_match(const u32 *l, int i, lcomm v) +{ return (l[i] == v.asn && l[i+1] == v.ldp1 && l[i+2] == v.ldp2); } + +static inline u32 *lc_copy(u32 *dst, const u32 *src) +{ memcpy(dst, src, LCOMM_LENGTH); return dst + 3; } + + +int int_set_format(const struct adata *set, int way, int from, byte *buf, uint size); +int ec_format(byte *buf, u64 ec); +int ec_set_format(const struct adata *set, int from, byte *buf, uint size); +int lc_format(byte *buf, lcomm lc); +int lc_set_format(const struct adata *set, int from, byte *buf, uint size); +int int_set_contains(const struct adata *list, u32 val); +int ec_set_contains(const struct adata *list, u64 val); +int lc_set_contains(const struct adata *list, lcomm val); +const struct adata *int_set_prepend(struct linpool *pool, const struct adata *list, u32 val); +const struct adata *int_set_add(struct linpool *pool, const struct adata *list, u32 val); +const struct adata *ec_set_add(struct linpool *pool, const struct adata *list, u64 val); +const struct adata *lc_set_add(struct linpool *pool, const struct adata *list, lcomm val); +const struct adata *int_set_del(struct linpool *pool, const struct adata *list, u32 val); +const struct adata *ec_set_del(struct linpool *pool, const struct adata *list, u64 val); +const struct adata *lc_set_del(struct linpool *pool, const struct adata *list, lcomm val); +const struct adata *int_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2); +const struct adata *ec_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2); +const struct adata *lc_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2); + +struct adata *ec_set_del_nontrans(struct linpool *pool, const struct adata *set); +struct adata *int_set_sort(struct linpool *pool, const struct adata *src); +struct adata *ec_set_sort(struct linpool *pool, const struct adata *src); +struct adata *lc_set_sort(struct linpool *pool, const struct adata *src); +int int_set_min(const struct adata *list, u32 *val); +int ec_set_min(const struct adata *list, u64 *val); +int lc_set_min(const struct adata *list, lcomm *val); +int int_set_max(const struct adata *list, u32 *val); +int ec_set_max(const struct adata *list, u64 *val); +int lc_set_max(const struct adata *list, lcomm *val); + +void ec_set_sort_x(struct adata *set); /* Sort in place */ + +#endif |