From 3fb70b26faca6788aa0bdf1d558414f9f777c6cd Mon Sep 17 00:00:00 2001 From: Maria Matejka Date: Thu, 31 Mar 2022 19:22:07 +0200 Subject: Complex route attributes are data structures, shall be in lib also --- filter/data.c | 2 +- filter/filter.c | 2 +- filter/filter.h | 2 +- lib/Makefile | 4 +- lib/a-path.c | 905 ++++++++++++++++++++++++++++++++++++++++++++++++++++ lib/a-path_test.c | 206 ++++++++++++ lib/a-set.c | 695 ++++++++++++++++++++++++++++++++++++++++ lib/a-set_test.c | 240 ++++++++++++++ lib/attrs.h | 230 +++++++++++++ nest/Makefile | 4 +- nest/a-path.c | 905 ---------------------------------------------------- nest/a-path_test.c | 206 ------------ nest/a-set.c | 695 ---------------------------------------- nest/a-set_test.c | 240 -------------- nest/attrs.h | 230 ------------- nest/rt-attr.c | 2 +- proto/bgp/attrs.c | 2 +- proto/bgp/packets.c | 2 +- 18 files changed, 2286 insertions(+), 2286 deletions(-) create mode 100644 lib/a-path.c create mode 100644 lib/a-path_test.c create mode 100644 lib/a-set.c create mode 100644 lib/a-set_test.c create mode 100644 lib/attrs.h delete mode 100644 nest/a-path.c delete mode 100644 nest/a-path_test.c delete mode 100644 nest/a-set.c delete mode 100644 nest/a-set_test.c delete mode 100644 nest/attrs.h diff --git a/filter/data.c b/filter/data.c index 87ef4ff1..381448fa 100644 --- a/filter/data.c +++ b/filter/data.c @@ -19,7 +19,7 @@ #include "nest/rt.h" #include "nest/protocol.h" #include "nest/iface.h" -#include "nest/attrs.h" +#include "lib/attrs.h" #include "conf/conf.h" #include "filter/filter.h" #include "filter/f-inst.h" diff --git a/filter/filter.c b/filter/filter.c index 31ae79fe..8f946f5b 100644 --- a/filter/filter.c +++ b/filter/filter.c @@ -38,7 +38,7 @@ #include "nest/rt.h" #include "nest/protocol.h" #include "nest/iface.h" -#include "nest/attrs.h" +#include "lib/attrs.h" #include "conf/conf.h" #include "filter/filter.h" #include "filter/f-inst.h" diff --git a/filter/filter.h b/filter/filter.h index 8ce6c1e0..385f1179 100644 --- a/filter/filter.h +++ b/filter/filter.h @@ -14,7 +14,7 @@ #include "lib/ip.h" #include "lib/macro.h" #include "nest/rt.h" -#include "nest/attrs.h" +#include "lib/attrs.h" /* Possible return values of filter execution */ enum filter_return { 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 + * (c) 2000 Pavel Machek + * + * 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 (pdata; + const u8 *q = p+path->length; + int i, n; + + while (plength; + 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 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 + * (c) 2000 Pavel Machek + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#include + +#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; /* + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#ifndef _BIRD_ATTRS_H_ +#define _BIRD_ATTRS_H_ + +#include +#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 diff --git a/nest/Makefile b/nest/Makefile index 7d451ba4..c0765530 100644 --- a/nest/Makefile +++ b/nest/Makefile @@ -1,4 +1,4 @@ -src := a-path.c a-set.c cli.c cmds.c iface.c locks.c neighbor.c password.c proto.c proto-build.c rt-attr.c rt-dev.c rt-fib.c rt-show.c rt-table.c +src := cli.c cmds.c iface.c locks.c neighbor.c password.c proto.c proto-build.c rt-attr.c rt-dev.c rt-fib.c rt-show.c rt-table.c obj := $(src-o-files) $(all-daemon) $(cf-local) @@ -8,6 +8,6 @@ $(proto-build-c): $(lastword $(MAKEFILE_LIST)) $(E)echo GEN $@ $(Q)echo "$(patsubst %,void %(void); ,$(PROTO_BUILD)) void protos_build_gen(void) { $(patsubst %, %(); ,$(PROTO_BUILD))}" > $@ -tests_src := a-set_test.c a-path_test.c +tests_src := tests_targets := $(tests_targets) $(tests-target-files) tests_objs := $(tests_objs) $(src-o-files) diff --git a/nest/a-path.c b/nest/a-path.c deleted file mode 100644 index 64504c93..00000000 --- a/nest/a-path.c +++ /dev/null @@ -1,905 +0,0 @@ -/* - * BIRD -- Path Operations - * - * (c) 2000 Martin Mares - * (c) 2000 Pavel Machek - * - * Can be freely distributed and used under the terms of the GNU GPL. - */ - -#include "nest/bird.h" -#include "nest/rt.h" -#include "nest/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 (pdata; - const u8 *q = p+path->length; - int i, n; - - while (plength; - 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 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/nest/a-path_test.c b/nest/a-path_test.c deleted file mode 100644 index a6b4d3d8..00000000 --- a/nest/a-path_test.c +++ /dev/null @@ -1,206 +0,0 @@ -/* - * 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 "nest/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/nest/a-set.c b/nest/a-set.c deleted file mode 100644 index 93f6431e..00000000 --- a/nest/a-set.c +++ /dev/null @@ -1,695 +0,0 @@ -/* - * BIRD -- Set/Community-list Operations - * - * (c) 2000 Martin Mares - * (c) 2000 Pavel Machek - * - * Can be freely distributed and used under the terms of the GNU GPL. - */ - -#include - -#include "nest/bird.h" -#include "nest/rt.h" -#include "nest/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/nest/a-set_test.c b/nest/a-set_test.c deleted file mode 100644 index daa6ab74..00000000 --- a/nest/a-set_test.c +++ /dev/null @@ -1,240 +0,0 @@ -/* - * 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 "nest/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; /* - * - * Can be freely distributed and used under the terms of the GNU GPL. - */ - -#ifndef _BIRD_ATTRS_H_ -#define _BIRD_ATTRS_H_ - -#include -#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 diff --git a/nest/rt-attr.c b/nest/rt-attr.c index 8f4319c5..2fa9b673 100644 --- a/nest/rt-attr.c +++ b/nest/rt-attr.c @@ -49,7 +49,7 @@ #include "nest/protocol.h" #include "nest/iface.h" #include "nest/cli.h" -#include "nest/attrs.h" +#include "lib/attrs.h" #include "lib/alloca.h" #include "lib/hash.h" #include "lib/idm.h" diff --git a/proto/bgp/attrs.c b/proto/bgp/attrs.c index 3265cb5e..2c0d011f 100644 --- a/proto/bgp/attrs.c +++ b/proto/bgp/attrs.c @@ -16,7 +16,7 @@ #include "nest/iface.h" #include "nest/protocol.h" #include "nest/rt.h" -#include "nest/attrs.h" +#include "lib/attrs.h" #include "conf/conf.h" #include "lib/resource.h" #include "lib/string.h" diff --git a/proto/bgp/packets.c b/proto/bgp/packets.c index 5def0f27..8eeae490 100644 --- a/proto/bgp/packets.c +++ b/proto/bgp/packets.c @@ -16,7 +16,7 @@ #include "nest/iface.h" #include "nest/protocol.h" #include "nest/rt.h" -#include "nest/attrs.h" +#include "lib/attrs.h" #include "proto/mrt/mrt.h" #include "conf/conf.h" #include "lib/unaligned.h" -- cgit v1.2.3