diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/Makefile | 4 | ||||
| -rw-r--r-- | lib/a-path.c | 905 | ||||
| -rw-r--r-- | lib/a-path_test.c | 206 | ||||
| -rw-r--r-- | lib/a-set.c | 695 | ||||
| -rw-r--r-- | lib/a-set_test.c | 240 | ||||
| -rw-r--r-- | lib/attrs.h | 262 | ||||
| -rw-r--r-- | lib/birdlib.h | 22 | ||||
| -rw-r--r-- | lib/bitmap_test.c | 3 | ||||
| -rw-r--r-- | lib/buffer_test.c | 1 | ||||
| -rw-r--r-- | lib/event.c | 2 | ||||
| -rw-r--r-- | lib/event_test.c | 5 | ||||
| -rw-r--r-- | lib/fib.h | 119 | ||||
| -rw-r--r-- | lib/flowspec_test.c | 11 | ||||
| -rw-r--r-- | lib/hash_test.c | 1 | ||||
| -rw-r--r-- | lib/ip.c | 24 | ||||
| -rw-r--r-- | lib/ip.h | 41 | ||||
| -rw-r--r-- | lib/ip_test.c | 66 | ||||
| -rw-r--r-- | lib/lists.h | 1 | ||||
| -rw-r--r-- | lib/mempool.c | 85 | ||||
| -rw-r--r-- | lib/net.h | 1 | ||||
| -rw-r--r-- | lib/printf.c | 48 | ||||
| -rw-r--r-- | lib/resource.c | 139 | ||||
| -rw-r--r-- | lib/resource.h | 48 | ||||
| -rw-r--r-- | lib/route.h | 433 | ||||
| -rw-r--r-- | lib/slab.c | 157 | ||||
| -rw-r--r-- | lib/slab_test.c | 171 | ||||
| -rw-r--r-- | lib/socket.h | 1 | ||||
| -rw-r--r-- | lib/string.h | 5 | ||||
| -rw-r--r-- | lib/timer.c | 1 | ||||
| -rw-r--r-- | lib/tlists.h | 172 | ||||
| -rw-r--r-- | lib/type.h | 112 | ||||
| -rw-r--r-- | lib/type_test.c | 79 |
32 files changed, 3811 insertions, 249 deletions
diff --git a/lib/Makefile b/lib/Makefile index 4378a7bd..15f757d9 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 +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 type_test.c tests_targets := $(tests_targets) $(tests-target-files) tests_objs := $(tests_objs) $(src-o-files) diff --git a/lib/a-path.c b/lib/a-path.c new file mode 100644 index 00000000..0eca8475 --- /dev/null +++ b/lib/a-path.c @@ -0,0 +1,905 @@ +/* + * BIRD -- Path Operations + * + * (c) 2000 Martin Mares <mj@ucw.cz> + * (c) 2000 Pavel Machek <pavel@ucw.cz> + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#include "nest/bird.h" +#include "nest/rt.h" +#include "lib/attrs.h" +#include "lib/resource.h" +#include "lib/unaligned.h" +#include "lib/string.h" +#include "filter/data.h" + +// static inline void put_as(byte *data, u32 as) { put_u32(data, as); } +// static inline u32 get_as(byte *data) { return get_u32(data); } + +#define put_as put_u32 +#define get_as get_u32 +#define BS 4 /* Default block size of ASN (autonomous system number) */ + +#define BAD(DSC, VAL) ({ err_dsc = DSC; err_val = VAL; goto bad; }) + +int +as_path_valid(byte *data, uint len, int bs, int sets, int confed, char *err, uint elen) +{ + byte *pos = data; + char *err_dsc = NULL; + uint err_val = 0; + + while (len) + { + if (len < 2) + BAD("segment framing error", 0); + + /* Process one AS path segment */ + uint type = pos[0]; + uint slen = 2 + bs * pos[1]; + + if (len < slen) + BAD("segment framing error", len); + + switch (type) + { + case AS_PATH_SET: + if (!sets) + BAD("AS_SET segment", type); + break; + + case AS_PATH_SEQUENCE: + break; + + case AS_PATH_CONFED_SEQUENCE: + if (!confed) + BAD("AS_CONFED_SEQUENCE segment", type); + break; + + case AS_PATH_CONFED_SET: + if (!sets || !confed) + BAD("AS_CONFED_SET segment", type); + break; + + default: + BAD("unknown segment", type); + } + + if (pos[1] == 0) + BAD("zero-length segment", type); + + pos += slen; + len -= slen; + } + + return 1; + +bad: + if (err) + if (bsnprintf(err, elen, "%s (%u) at %d", err_dsc, err_val, (int) (pos - data)) < 0) + err[0] = 0; + + return 0; +} + +int +as_path_16to32(byte *dst, const byte *src, uint len) +{ + byte *dst0 = dst; + const byte *end = src + len; + uint i, n; + + while (src < end) + { + n = src[1]; + *dst++ = *src++; + *dst++ = *src++; + + for (i = 0; i < n; i++) + { + put_u32(dst, get_u16(src)); + src += 2; + dst += 4; + } + } + + return dst - dst0; +} + +int +as_path_32to16(byte *dst, const byte *src, uint len) +{ + byte *dst0 = dst; + const byte *end = src + len; + uint i, n; + + while (src < end) + { + n = src[1]; + *dst++ = *src++; + *dst++ = *src++; + + for (i = 0; i < n; i++) + { + put_u16(dst, get_u32(src)); + src += 4; + dst += 2; + } + } + + return dst - dst0; +} + +int +as_path_contains_as4(const struct adata *path) +{ + const byte *pos = path->data; + const byte *end = pos + path->length; + uint i, n; + + while (pos < end) + { + n = pos[1]; + pos += 2; + + for (i = 0; i < n; i++) + { + if (get_as(pos) > 0xFFFF) + return 1; + + pos += BS; + } + } + + return 0; +} + +int +as_path_contains_confed(const struct adata *path) +{ + const byte *pos = path->data; + const byte *end = pos + path->length; + + while (pos < end) + { + uint type = pos[0]; + uint slen = 2 + BS * pos[1]; + + if ((type == AS_PATH_CONFED_SEQUENCE) || + (type == AS_PATH_CONFED_SET)) + return 1; + + pos += slen; + } + + return 0; +} + +struct adata * +as_path_strip_confed(struct linpool *pool, const struct adata *path) +{ + struct adata *res = lp_alloc_adata(pool, path->length); + const byte *src = path->data; + const byte *end = src + path->length; + byte *dst = res->data; + + while (src < end) + { + uint type = src[0]; + uint slen = 2 + BS * src[1]; + + /* Copy regular segments */ + if ((type == AS_PATH_SET) || (type == AS_PATH_SEQUENCE)) + { + memcpy(dst, src, slen); + dst += slen; + } + + src += slen; + } + + /* Fix the result length */ + res->length = dst - res->data; + + return res; +} + +struct adata * +as_path_prepend2(struct linpool *pool, const struct adata *op, int seq, u32 as) +{ + struct adata *np; + const byte *pos = op->data; + uint len = op->length; + + if (len && (pos[0] == seq) && (pos[1] < 255)) + { + /* Starting with matching segment => just prepend the AS number */ + np = lp_alloc_adata(pool, len + BS); + np->data[0] = seq; + np->data[1] = pos[1] + 1; + put_as(np->data + 2, as); + + uint dlen = BS * pos[1]; + memcpy(np->data + 2 + BS, pos + 2, dlen); + ADVANCE(pos, len, 2 + dlen); + } + else + { + /* Create a new path segment */ + np = lp_alloc_adata(pool, len + 2 + BS); + np->data[0] = seq; + np->data[1] = 1; + put_as(np->data + 2, as); + } + + if (len) + { + byte *dst = np->data + 2 + BS * np->data[1]; + + memcpy(dst, pos, len); + } + + return np; +} + + +struct adata * +as_path_to_old(struct linpool *pool, const struct adata *path) +{ + struct adata *res = lp_alloc_adata(pool, path->length); + byte *pos = res->data; + byte *end = pos + res->length; + uint i, n; + u32 as; + + /* Copy the whole path */ + memcpy(res->data, path->data, path->length); + + /* Replace 32-bit AS numbers with AS_TRANS */ + while (pos < end) + { + n = pos[1]; + pos += 2; + + for (i = 0; i < n; i++) + { + as = get_as(pos); + if (as > 0xFFFF) + put_as(pos, AS_TRANS); + + pos += BS; + } + } + + return res; +} + +/* + * Cut the path to the length @num, measured to the usual path metric. Note that + * AS_CONFED_* segments have zero length and must be added if they are on edge. + */ +struct adata * +as_path_cut(struct linpool *pool, const struct adata *path, uint num) +{ + const byte *pos = path->data; + const byte *end = pos + path->length; + + while (pos < end) + { + uint t = pos[0]; + uint l = pos[1]; + uint n = 0; + + switch (t) + { + case AS_PATH_SET: n = 1; break; + case AS_PATH_SEQUENCE: n = l; break; + case AS_PATH_CONFED_SEQUENCE: n = 0; break; + case AS_PATH_CONFED_SET: n = 0; break; + default: bug("as_path_cut: Invalid path segment"); + } + + /* Cannot add whole segment, so try partial one and finish */ + if (num < n) + { + const byte *nend = pos; + if (num) + nend += 2 + BS * num; + + struct adata *res = lp_alloc_adata(pool, path->length); + res->length = nend - (const byte *) path->data; + memcpy(res->data, path->data, res->length); + + if (num) + { + byte *dpos = ((byte *) res->data) + (pos - (const byte *) path->data); + dpos[1] = num; + } + + return res; + } + + num -= n; + pos += 2 + BS * l; + } + + struct adata *res = lp_alloc_adata(pool, path->length); + res->length = path->length; + memcpy(res->data, path->data, res->length); + return res; +} + +/* + * Merge (concatenate) paths @p1 and @p2 and return the result. + * In contrast to other as_path_* functions, @p1 and @p2 may be reused. + */ +const struct adata * +as_path_merge(struct linpool *pool, const struct adata *p1, const struct adata *p2) +{ + if (p1->length == 0) + return p2; + + if (p2->length == 0) + return p1; + + struct adata *res = lp_alloc_adata(pool, p1->length + p2->length); + memcpy(res->data, p1->data, p1->length); + memcpy(res->data + p1->length, p2->data, p2->length); + + return res; +} + +void +as_path_format(const struct adata *path, byte *bb, uint size) +{ + buffer buf = { .start = bb, .pos = bb, .end = bb + size }, *b = &buf; + const byte *pos = path->data; + const byte *end = pos + path->length; + const char *ops, *cls; + + b->pos[0] = 0; + + while (pos < end) + { + uint type = pos[0]; + uint len = pos[1]; + pos += 2; + + switch (type) + { + case AS_PATH_SET: ops = "{"; cls = "}"; break; + case AS_PATH_SEQUENCE: ops = NULL; cls = NULL; break; + case AS_PATH_CONFED_SEQUENCE: ops = "("; cls = ")"; break; + case AS_PATH_CONFED_SET: ops = "({"; cls = "})"; break; + default: bug("Invalid path segment"); + } + + if (ops) + buffer_puts(b, ops); + + while (len--) + { + buffer_print(b, len ? "%u " : "%u", get_as(pos)); + pos += BS; + } + + if (cls) + buffer_puts(b, cls); + + if (pos < end) + buffer_puts(b, " "); + } + + /* Handle overflow */ + if (b->pos == b->end) + strcpy(b->end - 12, "..."); +} + +int +as_path_getlen(const struct adata *path) +{ + const byte *pos = path->data; + const byte *end = pos + path->length; + uint res = 0; + + while (pos < end) + { + uint t = pos[0]; + uint l = pos[1]; + uint n = 0; + + switch (t) + { + case AS_PATH_SET: n = 1; break; + case AS_PATH_SEQUENCE: n = l; break; + case AS_PATH_CONFED_SEQUENCE: n = 0; break; + case AS_PATH_CONFED_SET: n = 0; break; + default: bug("as_path_getlen: Invalid path segment"); + } + + res += n; + pos += 2 + BS * l; + } + + return res; +} + +int +as_path_get_last(const struct adata *path, u32 *orig_as) +{ + const byte *pos = path->data; + const byte *end = pos + path->length; + int found = 0; + u32 val = 0; + + while (pos < end) + { + uint type = pos[0]; + uint len = pos[1]; + pos += 2; + + if (!len) + continue; + + switch (type) + { + case AS_PATH_SET: + case AS_PATH_CONFED_SET: + found = 0; + break; + + case AS_PATH_SEQUENCE: + case AS_PATH_CONFED_SEQUENCE: + val = get_as(pos + BS * (len - 1)); + found = 1; + break; + + default: + bug("Invalid path segment"); + } + + pos += BS * len; + } + + if (found) + *orig_as = val; + return found; +} + +u32 +as_path_get_last_nonaggregated(const struct adata *path) +{ + const byte *pos = path->data; + const byte *end = pos + path->length; + u32 val = 0; + + while (pos < end) + { + uint type = pos[0]; + uint len = pos[1]; + pos += 2; + + if (!len) + continue; + + switch (type) + { + case AS_PATH_SET: + case AS_PATH_CONFED_SET: + return val; + + case AS_PATH_SEQUENCE: + case AS_PATH_CONFED_SEQUENCE: + val = get_as(pos + BS * (len - 1)); + break; + + default: + bug("Invalid path segment"); + } + + pos += BS * len; + } + + return val; +} + +int +as_path_get_first(const struct adata *path, u32 *last_as) +{ + const u8 *p = path->data; + + if ((path->length == 0) || (p[0] != AS_PATH_SEQUENCE) || (p[1] == 0)) + return 0; + + *last_as = get_as(p+2); + return 1; +} + +int +as_path_get_first_regular(const struct adata *path, u32 *last_as) +{ + const byte *pos = path->data; + const byte *end = pos + path->length; + + while (pos < end) + { + uint type = pos[0]; + uint len = pos[1]; + pos += 2; + + switch (type) + { + case AS_PATH_SET: + return 0; + + case AS_PATH_SEQUENCE: + if (len == 0) + return 0; + + *last_as = get_as(pos); + return 1; + + case AS_PATH_CONFED_SEQUENCE: + case AS_PATH_CONFED_SET: + break; + + default: + bug("Invalid path segment"); + } + + pos += BS * len; + } + + return 0; +} + +int +as_path_contains(const struct adata *path, u32 as, int min) +{ + const u8 *p = path->data; + const u8 *q = p+path->length; + int num = 0; + int i, n; + + while (p<q) + { + n = p[1]; + p += 2; + for(i=0; i<n; i++) + { + if (get_as(p) == as) + if (++num == min) + return 1; + p += BS; + } + } + return 0; +} + +int +as_path_match_set(const struct adata *path, const struct f_tree *set) +{ + const u8 *p = path->data; + const u8 *q = p+path->length; + int i, n; + + while (p<q) + { + n = p[1]; + p += 2; + for (i=0; i<n; i++) + { + struct f_val v = { .type = T_INT, .val.i = get_as(p)}; + if (find_tree(set, &v)) + return 1; + p += BS; + } + } + + return 0; +} + +const struct adata * +as_path_filter(struct linpool *pool, const struct adata *path, const struct f_tree *set, u32 key, int pos) +{ + if (!path) + return NULL; + + int len = path->length; + const u8 *p = path->data; + const u8 *q = path->data + len; + u8 *d, *d2; + int i, bt, sn, dn; + u8 buf[len]; + + d = buf; + while (p<q) + { + /* Read block header (type and length) */ + bt = p[0]; + sn = p[1]; + dn = 0; + p += 2; + d2 = d + 2; + + for (i = 0; i < sn; i++) + { + u32 as = get_as(p); + int match; + + if (set) + { + struct f_val v = { .type = T_INT, .val.i = as}; + match = !!find_tree(set, &v); + } + else + match = (as == key); + + if (match == pos) + { + put_as(d2, as); + d2 += BS; + dn++; + } + + p += BS; + } + + if (dn > 0) + { + /* Nonempty block, set block header and advance */ + d[0] = bt; + d[1] = dn; + d = d2; + } + } + + uint nl = d - buf; + if (nl == path->length) + return path; + + struct adata *res = lp_alloc(pool, sizeof(struct adata) + nl); + res->length = nl; + memcpy(res->data, buf, nl); + + return res; +} + + +struct pm_pos +{ + u8 set; + u8 mark; + union + { + const char *sp; + u32 asn; + } val; +}; + +static int +parse_path(const struct adata *path, struct pm_pos *pp) +{ + const byte *pos = path->data; + const byte *end = pos + path->length; + struct pm_pos *op = pp; + uint i; + + while (pos < end) + { + uint type = pos[0]; + uint len = pos[1]; + pos += 2; + + switch (type) + { + case AS_PATH_SET: + case AS_PATH_CONFED_SET: + pp->set = 1; + pp->mark = 0; + pp->val.sp = pos - 1; + pp++; + + pos += BS * len; + break; + + case AS_PATH_SEQUENCE: + case AS_PATH_CONFED_SEQUENCE: + for (i = 0; i < len; i++) + { + pp->set = 0; + pp->mark = 0; + pp->val.asn = get_as(pos); + pp++; + + pos += BS; + } + break; + + default: + bug("Invalid path segment"); + } + } + + return pp - op; +} + +static int +pm_match_val(const struct pm_pos *pos, u32 asn, u32 asn2) +{ + u32 gas; + if (! pos->set) + return ((pos->val.asn >= asn) && (pos->val.asn <= asn2)); + + const u8 *p = pos->val.sp; + int len = *p++; + int i; + + for (i = 0; i < len; i++) + { + gas = get_as(p + i * BS); + + if ((gas >= asn) && (gas <= asn2)) + return 1; + } + + return 0; +} + +static int +pm_match_set(const struct pm_pos *pos, const struct f_tree *set) +{ + struct f_val asn = { .type = T_INT }; + + if (! pos->set) + { + asn.val.i = pos->val.asn; + return !!find_tree(set, &asn); + } + + const u8 *p = pos->val.sp; + int len = *p++; + int i; + + for (i = 0; i < len; i++) + { + asn.val.i = get_as(p + i * BS); + if (find_tree(set, &asn)) + return 1; + } + + return 0; +} + +static inline int +pm_match(const struct pm_pos *pos, const struct f_path_mask_item *mask, u32 asn, u32 asn2) +{ + return ((mask->kind == PM_QUESTION) || + ((mask->kind != PM_ASN_SET) ? + pm_match_val(pos, asn, asn2) : + pm_match_set(pos, mask->set))); +} + +static void +pm_mark(struct pm_pos *pos, int *i, int plen, int *nl, int *nh) +{ + int j = *i; + + if (pos[j].set) + do { pos[j].mark = 1; j++; } + while ((j < plen) && pos[j].set); + else + j++; + + pos[j].mark = 1; + + /* Update low, high based on first and last marked pos */ + int l = pos[*i].set ? *i : j; + + *nl = (*nl < 0) ? l : MIN(*nl, l); + *nh = MAX(*nh, j); + *i = j; +} + +/* AS path matching is nontrivial. Because AS path can + * contain sets, it is not a plain wildcard matching. A set + * in an AS path is interpreted as it might represent any + * sequence of AS numbers from that set (possibly with + * repetitions). So it is also a kind of a pattern, + * more complicated than a path mask. + * + * The algorithm for AS path matching is a variant + * of nondeterministic finite state machine, where + * positions in AS path are states, and items in + * path mask are input for that finite state machine. + * During execution of the algorithm we maintain a set + * of marked states - a state is marked if it can be + * reached by any walk through NFSM with regard to + * currently processed part of input. When we process + * next part of mask, we advance each marked state. + * We start with marked first position, when we + * run out of marked positions, we reject. When + * we process the whole mask, we accept if final position + * (auxiliary position after last real position in AS path) + * is marked. + */ +int +as_path_match(const struct adata *path, const struct f_path_mask *mask) +{ + struct pm_pos pos[2048 + 1]; + int plen = parse_path(path, pos); + int l, h, i, nh, nl, last, loop; + u32 val = 0; + u32 val2 = 0; + + /* l and h are bound of interval of positions where + are marked states */ + + pos[plen].set = 0; + pos[plen].mark = 0; + + l = h = loop = 0; + pos[0].mark = 1; + + for (uint m=0; m < mask->len; m++) + { + /* We remove this mark to not step after pos[plen] */ + pos[plen].mark = 0; + + switch (mask->item[m].kind) + { + case PM_ASTERISK: + for (i = l; i <= plen; i++) + pos[i].mark = 1; + h = plen; + break; + + case PM_LOOP: + loop = 1; + break; + + case PM_ASN: /* Define single ASN as ASN..ASN - very narrow interval */ + val2 = val = mask->item[m].asn; + goto step; + case PM_ASN_EXPR: + bug("Expressions should be evaluated on AS path mask construction."); + case PM_ASN_RANGE: + val = mask->item[m].from; + val2 = mask->item[m].to; + goto step; + case PM_QUESTION: + case PM_ASN_SET: + step: + nh = nl = -1; + last = plen; + for (i = h; i >= l; i--) + if (pos[i].mark) + { + pos[i].mark = 0; + int j = i; + + match: + if (pm_match(pos + j, &mask->item[m], val, val2)) + { + pm_mark(pos, &j, plen, &nl, &nh); + if (loop && (j < last)) + goto match; + } + + last = i; + } + + if (nh < 0) + return 0; + + h = nh; + l = nl; + loop = 0; + break; + } + } + + return pos[plen].mark; +} diff --git a/lib/a-path_test.c b/lib/a-path_test.c new file mode 100644 index 00000000..38f77642 --- /dev/null +++ b/lib/a-path_test.c @@ -0,0 +1,206 @@ +/* + * BIRD -- Path Operations Tests + * + * (c) 2015 CZ.NIC z.s.p.o. + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#include "test/birdtest.h" +#include "test/bt-utils.h" + +#include "nest/rt.h" +#include "lib/attrs.h" +#include "lib/resource.h" + +#define TESTS_NUM 30 +#define AS_PATH_LENGTH 1000 + +#if AS_PATH_LENGTH > AS_PATH_MAXLEN +#warning "AS_PATH_LENGTH should be <= AS_PATH_MAXLEN" +#endif + +static int +t_as_path_match(void) +{ + int round; + for (round = 0; round < TESTS_NUM; round++) + { + struct adata empty_as_path = {}; + struct adata *as_path = &empty_as_path; + u32 first_prepended, last_prepended; + first_prepended = last_prepended = 0; + + struct f_path_mask *mask = alloca(sizeof(struct f_path_mask) + AS_PATH_LENGTH * sizeof(struct f_path_mask_item)); + mask->len = AS_PATH_LENGTH; + for (int i = AS_PATH_LENGTH - 1; i >= 0; i--) + { + u32 val = bt_random(); + as_path = as_path_prepend(tmp_linpool, as_path, val); + bt_debug("Prepending ASN: %10u \n", val); + + if (i == 0) + last_prepended = val; + if (i == AS_PATH_LENGTH-1) + first_prepended = val; + + mask->item[i].kind = PM_ASN; + mask->item[i].asn = val; + } + + bt_assert_msg(as_path_match(as_path, mask), "Mask should match with AS path"); + + u32 asn; + + bt_assert(as_path_get_first(as_path, &asn)); + bt_assert_msg(asn == last_prepended, "as_path_get_first() should return the last prepended ASN"); + + bt_assert(as_path_get_last(as_path, &asn)); + bt_assert_msg(asn == first_prepended, "as_path_get_last() should return the first prepended ASN"); + + tmp_flush(); + } + + return 1; +} + +static int +t_path_format(void) +{ + struct adata empty_as_path = {}; + struct adata *as_path = &empty_as_path; + + uint i; + for (i = 4294967285; i <= 4294967294; i++) + { + as_path = as_path_prepend(tmp_linpool, as_path, i); + bt_debug("Prepending ASN: %10u \n", i); + } + +#define BUFFER_SIZE 120 + byte buf[BUFFER_SIZE] = {}; + + as_path_format(&empty_as_path, buf, BUFFER_SIZE); + bt_assert_msg(strcmp(buf, "") == 0, "Buffer(%zu): '%s'", strlen(buf), buf); + + as_path_format(as_path, buf, BUFFER_SIZE); + bt_assert_msg(strcmp(buf, "4294967294 4294967293 4294967292 4294967291 4294967290 4294967289 4294967288 4294967287 4294967286 4294967285") == 0, "Buffer(%zu): '%s'", strlen(buf), buf); + +#define SMALL_BUFFER_SIZE 25 + byte buf2[SMALL_BUFFER_SIZE] = {}; + as_path_format(as_path, buf2, SMALL_BUFFER_SIZE); + bt_assert_msg(strcmp(buf2, "4294967294 42...") == 0, "Small Buffer(%zu): '%s'", strlen(buf2), buf2); + + tmp_flush(); + + return 1; +} + +static int +count_asn_in_array(const u32 *array, u32 asn) +{ + int counts_of_contains = 0; + int u; + for (u = 0; u < AS_PATH_LENGTH; u++) + if (array[u] == asn) + counts_of_contains++; + return counts_of_contains; +} + +static int +t_path_include(void) +{ + struct adata empty_as_path = {}; + struct adata *as_path = &empty_as_path; + + u32 as_nums[AS_PATH_LENGTH] = {}; + int i; + for (i = 0; i < AS_PATH_LENGTH; i++) + { + u32 val = bt_random(); + as_nums[i] = val; + as_path = as_path_prepend(tmp_linpool, as_path, val); + } + + for (i = 0; i < AS_PATH_LENGTH; i++) + { + int counts_of_contains = count_asn_in_array(as_nums, as_nums[i]); + bt_assert_msg(as_path_contains(as_path, as_nums[i], counts_of_contains), "AS Path should contains %d-times number %d", counts_of_contains, as_nums[i]); + + bt_assert(as_path_filter(tmp_linpool, as_path, NULL, as_nums[i], 0) != NULL); + bt_assert(as_path_filter(tmp_linpool, as_path, NULL, as_nums[i], 1) != NULL); + } + + for (i = 0; i < 10000; i++) + { + u32 test_val = bt_random(); + int counts_of_contains = count_asn_in_array(as_nums, test_val); + int result = as_path_contains(as_path, test_val, (counts_of_contains == 0 ? 1 : counts_of_contains)); + + if (counts_of_contains) + bt_assert_msg(result, "As path should contain %d-times the number %u", counts_of_contains, test_val); + else + bt_assert_msg(result == 0, "As path should not contain the number %u", test_val); + } + + tmp_flush(); + + return 1; +} + +#if 0 +static int +t_as_path_converting(void) +{ + struct adata empty_as_path = {}; + struct adata *as_path = &empty_as_path; +#define AS_PATH_LENGTH_FOR_CONVERTING_TEST 10 + + int i; + for (i = 0; i < AS_PATH_LENGTH_FOR_CONVERTING_TEST; i++) + as_path = as_path_prepend(tmp_linpool, as_path, i); + + bt_debug("data length: %u \n", as_path->length); + + byte buffer[100] = {}; + int used_size = as_path_convert_to_new(as_path, buffer, AS_PATH_LENGTH_FOR_CONVERTING_TEST-1); + bt_debug("as_path_convert_to_new: len %d \n%s\n", used_size, buffer); + for (i = 0; i < used_size; i++) + { + bt_debug("\\03%d", buffer[i]); + } + bt_debug("\n"); + bt_assert(memcmp(buffer, + "\032\039\030\030\030\030\030\030\030\039\030\030\030\030\030\030\030\038\030\030\030\030\030\030" + "\030\037\030\030\030\030\030\030\030\036\030\030\030\030", + 38)); + + bzero(buffer, sizeof(buffer)); + int new_used; + used_size = as_path_convert_to_old(as_path, buffer, &new_used); + bt_debug("as_path_convert_to_old: len %d, new_used: %d \n", used_size, new_used); + for (i = 0; i < used_size; i++) + { + bt_debug("\\03%d", buffer[i]); + } + bt_debug("\n"); + bt_assert(memcmp(buffer, + "\032\0310\030\039\030\038\030\037\030\036\030\035\030\034\030\033\030\032\030\031\030\030", + 22)); + + return 1; +} +#endif + +int +main(int argc, char *argv[]) +{ + bt_init(argc, argv); + + bt_test_suite(t_as_path_match, "Testing AS path matching and some a-path utilities."); + bt_test_suite(t_path_format, "Testing formating as path into byte buffer"); + bt_test_suite(t_path_include, "Testing including a AS number in AS path"); + // bt_test_suite(t_as_path_converting, "Testing as_path_convert_to_*() output constancy"); + + return bt_exit_value(); +} diff --git a/lib/a-set.c b/lib/a-set.c new file mode 100644 index 00000000..8ede9b83 --- /dev/null +++ b/lib/a-set.c @@ -0,0 +1,695 @@ +/* + * BIRD -- Set/Community-list Operations + * + * (c) 2000 Martin Mares <mj@ucw.cz> + * (c) 2000 Pavel Machek <pavel@ucw.cz> + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#include <stdlib.h> + +#include "nest/bird.h" +#include "nest/rt.h" +#include "lib/attrs.h" +#include "lib/resource.h" +#include "lib/string.h" + +/** + * int_set_format - format an &set for printing + * @set: set attribute to be formatted + * @way: style of format (0 for router ID list, 1 for community list) + * @from: starting position in set + * @buf: destination buffer + * @size: size of buffer + * + * This function takes a set attribute and formats it. @way specifies + * the style of format (router ID / community). @from argument can be + * used to specify the first printed value for the purpose of printing + * untruncated sets even with smaller buffers. If the output fits in + * the buffer, 0 is returned, otherwise the position of the first not + * printed item is returned. This value can be used as @from argument + * in subsequent calls. If truncated output suffices, -1 can be + * instead used as @from, in that case " ..." is eventually added at + * the buffer to indicate truncation. + */ +int +int_set_format(const struct adata *set, int way, int from, byte *buf, uint size) +{ + u32 *z = (u32 *) set->data; + byte *end = buf + size - 24; + int from2 = MAX(from, 0); + int to = set->length / 4; + int i; + + for (i = from2; i < to; i++) + { + if (buf > end) + { + if (from < 0) + strcpy(buf, " ..."); + else + *buf = 0; + return i; + } + + if (i > from2) + *buf++ = ' '; + + if (way) + buf += bsprintf(buf, "(%d,%d)", z[i] >> 16, z[i] & 0xffff); + else + buf += bsprintf(buf, "%R", z[i]); + } + *buf = 0; + return 0; +} + +int +ec_format(byte *buf, u64 ec) +{ + u32 type, key, val; + char tbuf[16]; + const char *kind; + + type = ec >> 48; + kind = ec_subtype_str(type & 0xf0ff); + + if (!kind) { + bsprintf(tbuf, "unknown 0x%x", type); + kind = tbuf; + } + + switch (ec >> 56) + { + /* RFC 4360 3.1. Two-Octet AS Specific Extended Community */ + case 0x00: + case 0x40: + key = (ec >> 32) & 0xFFFF; + val = ec; + return bsprintf(buf, "(%s, %u, %u)", kind, key, val); + + /* RFC 4360 3.2. IPv4 Address Specific Extended Community */ + case 0x01: + case 0x41: + key = ec >> 16; + val = ec & 0xFFFF; + return bsprintf(buf, "(%s, %R, %u)", kind, key, val); + + /* RFC 5668 4-Octet AS Specific BGP Extended Community */ + case 0x02: + case 0x42: + key = ec >> 16; + val = ec & 0xFFFF; + return bsprintf(buf, "(%s, %u, %u)", kind, key, val); + + /* Generic format for unknown kinds of extended communities */ + default: + key = ec >> 32; + val = ec; + return bsprintf(buf, "(generic, 0x%x, 0x%x)", key, val); + } + +} + +int +ec_set_format(const struct adata *set, int from, byte *buf, uint size) +{ + u32 *z = int_set_get_data(set); + byte *end = buf + size - 64; + int from2 = MAX(from, 0); + int to = int_set_get_size(set); + int i; + + for (i = from2; i < to; i += 2) + { + if (buf > end) + { + if (from < 0) + strcpy(buf, " ..."); + else + *buf = 0; + return i; + } + + if (i > from2) + *buf++ = ' '; + + buf += ec_format(buf, ec_get(z, i)); + } + *buf = 0; + return 0; +} + +int +lc_format(byte *buf, lcomm lc) +{ + return bsprintf(buf, "(%u, %u, %u)", lc.asn, lc.ldp1, lc.ldp2); +} + +int +lc_set_format(const struct adata *set, int from, byte *buf, uint bufsize) +{ + u32 *d = (u32 *) set->data; + byte *end = buf + bufsize - 64; + int from2 = MAX(from, 0); + int to = set->length / 4; + int i; + + for (i = from2; i < to; i += 3) + { + if (buf > end) + { + if (from < 0) + strcpy(buf, "..."); + else + buf[-1] = 0; + return i; + } + + buf += bsprintf(buf, "(%u, %u, %u)", d[i], d[i+1], d[i+2]); + *buf++ = ' '; + } + + if (i != from2) + buf--; + + *buf = 0; + return 0; +} + +int +int_set_contains(const struct adata *list, u32 val) +{ + if (!list) + return 0; + + u32 *l = (u32 *) list->data; + int len = int_set_get_size(list); + int i; + + for (i = 0; i < len; i++) + if (*l++ == val) + return 1; + + return 0; +} + +int +ec_set_contains(const struct adata *list, u64 val) +{ + if (!list) + return 0; + + u32 *l = int_set_get_data(list); + int len = int_set_get_size(list); + u32 eh = ec_hi(val); + u32 el = ec_lo(val); + int i; + + for (i=0; i < len; i += 2) + if (l[i] == eh && l[i+1] == el) + return 1; + + return 0; +} + +int +lc_set_contains(const struct adata *list, lcomm val) +{ + if (!list) + return 0; + + u32 *l = int_set_get_data(list); + int len = int_set_get_size(list); + int i; + + for (i = 0; i < len; i += 3) + if (lc_match(l, i, val)) + return 1; + + return 0; +} + +const struct adata * +int_set_prepend(struct linpool *pool, const struct adata *list, u32 val) +{ + struct adata *res; + int len; + + if (int_set_contains(list, val)) + return list; + + len = list ? list->length : 0; + res = lp_alloc(pool, sizeof(struct adata) + len + 4); + res->length = len + 4; + + if (list) + memcpy(res->data + 4, list->data, list->length); + + * (u32 *) res->data = val; + + return res; +} + +const struct adata * +int_set_add(struct linpool *pool, const struct adata *list, u32 val) +{ + struct adata *res; + int len; + + if (int_set_contains(list, val)) + return list; + + len = list ? list->length : 0; + res = lp_alloc(pool, sizeof(struct adata) + len + 4); + res->length = len + 4; + + if (list) + memcpy(res->data, list->data, list->length); + + * (u32 *) (res->data + len) = val; + + return res; +} + +const struct adata * +ec_set_add(struct linpool *pool, const struct adata *list, u64 val) +{ + if (ec_set_contains(list, val)) + return list; + + int olen = list ? list->length : 0; + struct adata *res = lp_alloc(pool, sizeof(struct adata) + olen + 8); + res->length = olen + 8; + + if (list) + memcpy(res->data, list->data, list->length); + + u32 *l = (u32 *) (res->data + olen); + l[0] = ec_hi(val); + l[1] = ec_lo(val); + + return res; +} + +const struct adata * +lc_set_add(struct linpool *pool, const struct adata *list, lcomm val) +{ + if (lc_set_contains(list, val)) + return list; + + int olen = list ? list->length : 0; + struct adata *res = lp_alloc(pool, sizeof(struct adata) + olen + LCOMM_LENGTH); + res->length = olen + LCOMM_LENGTH; + + if (list) + memcpy(res->data, list->data, list->length); + + lc_put((u32 *) (res->data + olen), val); + + return res; +} + +const struct adata * +int_set_del(struct linpool *pool, const struct adata *list, u32 val) +{ + if (!int_set_contains(list, val)) + return list; + + struct adata *res; + res = lp_alloc(pool, sizeof(struct adata) + list->length - 4); + res->length = list->length - 4; + + u32 *l = int_set_get_data(list); + u32 *k = int_set_get_data(res); + int len = int_set_get_size(list); + int i; + + for (i = 0; i < len; i++) + if (l[i] != val) + *k++ = l[i]; + + return res; +} + +const struct adata * +ec_set_del(struct linpool *pool, const struct adata *list, u64 val) +{ + if (!ec_set_contains(list, val)) + return list; + + struct adata *res; + res = lp_alloc(pool, sizeof(struct adata) + list->length - 8); + res->length = list->length - 8; + + u32 *l = int_set_get_data(list); + u32 *k = int_set_get_data(res); + int len = int_set_get_size(list); + u32 eh = ec_hi(val); + u32 el = ec_lo(val); + int i; + + for (i=0; i < len; i += 2) + if (! (l[i] == eh && l[i+1] == el)) + { + *k++ = l[i]; + *k++ = l[i+1]; + } + + return res; +} + +const struct adata * +lc_set_del(struct linpool *pool, const struct adata *list, lcomm val) +{ + if (!lc_set_contains(list, val)) + return list; + + struct adata *res; + res = lp_alloc(pool, sizeof(struct adata) + list->length - LCOMM_LENGTH); + res->length = list->length - LCOMM_LENGTH; + + u32 *l = int_set_get_data(list); + u32 *k = int_set_get_data(res); + int len = int_set_get_size(list); + int i; + + for (i=0; i < len; i += 3) + if (! lc_match(l, i, val)) + k = lc_copy(k, l+i); + + return res; +} + +const struct adata * +int_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2) +{ + if (!l1) + return l2; + if (!l2) + return l1; + + struct adata *res; + int len = int_set_get_size(l2); + u32 *l = int_set_get_data(l2); + u32 tmp[len]; + u32 *k = tmp; + int i; + + for (i = 0; i < len; i++) + if (!int_set_contains(l1, l[i])) + *k++ = l[i]; + + if (k == tmp) + return l1; + + len = (k - tmp) * 4; + res = lp_alloc(pool, sizeof(struct adata) + l1->length + len); + res->length = l1->length + len; + memcpy(res->data, l1->data, l1->length); + memcpy(res->data + l1->length, tmp, len); + return res; +} + +const struct adata * +ec_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2) +{ + if (!l1) + return l2; + if (!l2) + return l1; + + struct adata *res; + int len = int_set_get_size(l2); + u32 *l = int_set_get_data(l2); + u32 tmp[len]; + u32 *k = tmp; + int i; + + for (i = 0; i < len; i += 2) + if (!ec_set_contains(l1, ec_get(l, i))) + { + *k++ = l[i]; + *k++ = l[i+1]; + } + + if (k == tmp) + return l1; + + len = (k - tmp) * 4; + res = lp_alloc(pool, sizeof(struct adata) + l1->length + len); + res->length = l1->length + len; + memcpy(res->data, l1->data, l1->length); + memcpy(res->data + l1->length, tmp, len); + return res; +} + +const struct adata * +lc_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2) +{ + if (!l1) + return l2; + if (!l2) + return l1; + + struct adata *res; + int len = int_set_get_size(l2); + u32 *l = int_set_get_data(l2); + u32 tmp[len]; + u32 *k = tmp; + int i; + + for (i = 0; i < len; i += 3) + if (!lc_set_contains(l1, lc_get(l, i))) + k = lc_copy(k, l+i); + + if (k == tmp) + return l1; + + len = (k - tmp) * 4; + res = lp_alloc(pool, sizeof(struct adata) + l1->length + len); + res->length = l1->length + len; + memcpy(res->data, l1->data, l1->length); + memcpy(res->data + l1->length, tmp, len); + return res; +} + + +struct adata * +ec_set_del_nontrans(struct linpool *pool, const struct adata *set) +{ + adata *res = lp_alloc_adata(pool, set->length); + u32 *src = int_set_get_data(set); + u32 *dst = int_set_get_data(res); + int len = int_set_get_size(set); + int i; + + /* Remove non-transitive communities (EC_TBIT set) */ + for (i = 0; i < len; i += 2) + { + if (src[i] & EC_TBIT) + continue; + + *dst++ = src[i]; + *dst++ = src[i+1]; + } + + res->length = ((byte *) dst) - res->data; + + return res; +} + +static int +int_set_cmp(const void *X, const void *Y) +{ + const u32 *x = X, *y = Y; + return (*x < *y) ? -1 : (*x > *y) ? 1 : 0; +} + +struct adata * +int_set_sort(struct linpool *pool, const struct adata *src) +{ + struct adata *dst = lp_alloc_adata(pool, src->length); + memcpy(dst->data, src->data, src->length); + qsort(dst->data, dst->length / 4, 4, int_set_cmp); + return dst; +} + +int +int_set_min(const struct adata *list, u32 *val) +{ + if (!list) + return 0; + + u32 *l = (u32 *) list->data; + int len = int_set_get_size(list); + int i; + + if (len < 1) + return 0; + + *val = *l++; + for (i = 1; i < len; i++, l++) + if (int_set_cmp(val, l) > 0) + *val = *l; + + return 1; +} + +int +int_set_max(const struct adata *list, u32 *val) +{ + if (!list) + return 0; + + u32 *l = (u32 *) list->data; + int len = int_set_get_size(list); + int i; + + if (len < 1) + return 0; + + *val = *l++; + for (i = 1; i < len; i++, l++) + if (int_set_cmp(val, l) < 0) + *val = *l; + + return 1; +} + + +static int +ec_set_cmp(const void *X, const void *Y) +{ + u64 x = ec_get(X, 0); + u64 y = ec_get(Y, 0); + return (x < y) ? -1 : (x > y) ? 1 : 0; +} + +struct adata * +ec_set_sort(struct linpool *pool, const struct adata *src) +{ + struct adata *dst = lp_alloc_adata(pool, src->length); + memcpy(dst->data, src->data, src->length); + qsort(dst->data, dst->length / 8, 8, ec_set_cmp); + return dst; +} + +void +ec_set_sort_x(struct adata *set) +{ + /* Sort in place */ + qsort(set->data, set->length / 8, 8, ec_set_cmp); +} + +int +ec_set_min(const struct adata *list, u64 *val) +{ + if (!list) + return 0; + + u32 *l = int_set_get_data(list); + int len = int_set_get_size(list); + int i; + + if (len < 1) + return 0; + + u32 *res = l; l += 2; + for (i = 2; i < len; i += 2, l += 2) + if (ec_set_cmp(res, l) > 0) + res = l; + + *val = ec_generic(res[0], res[1]); + return 1; +} + +int +ec_set_max(const struct adata *list, u64 *val) +{ + if (!list) + return 0; + + u32 *l = int_set_get_data(list); + int len = int_set_get_size(list); + int i; + + if (len < 1) + return 0; + + u32 *res = l; l += 2; + for (i = 2; i < len; i += 2, l += 2) + if (ec_set_cmp(res, l) < 0) + res = l; + + *val = ec_generic(res[0], res[1]); + return 1; +} + + +static int +lc_set_cmp(const void *X, const void *Y) +{ + const u32 *x = X, *y = Y; + if (x[0] != y[0]) + return (x[0] > y[0]) ? 1 : -1; + if (x[1] != y[1]) + return (x[1] > y[1]) ? 1 : -1; + if (x[2] != y[2]) + return (x[2] > y[2]) ? 1 : -1; + return 0; +} + +struct adata * +lc_set_sort(struct linpool *pool, const struct adata *src) +{ + struct adata *dst = lp_alloc_adata(pool, src->length); + memcpy(dst->data, src->data, src->length); + qsort(dst->data, dst->length / LCOMM_LENGTH, LCOMM_LENGTH, lc_set_cmp); + return dst; +} + +int +lc_set_min(const struct adata *list, lcomm *val) +{ + if (!list) + return 0; + + u32 *l = int_set_get_data(list); + int len = int_set_get_size(list); + int i; + + if (len < 1) + return 0; + + u32 *res = l; l += 3; + for (i = 3; i < len; i += 3, l += 3) + if (lc_set_cmp(res, l) > 0) + res = l; + + *val = (lcomm) { res[0], res[1], res[2] }; + return 1; +} + +int +lc_set_max(const struct adata *list, lcomm *val) +{ + if (!list) + return 0; + + u32 *l = int_set_get_data(list); + int len = int_set_get_size(list); + int i; + + if (len < 1) + return 0; + + u32 *res = l; l += 3; + for (i = 3; i < len; i += 3, l += 3) + if (lc_set_cmp(res, l) < 0) + res = l; + + *val = (lcomm) { res[0], res[1], res[2] }; + return 1; +} diff --git a/lib/a-set_test.c b/lib/a-set_test.c new file mode 100644 index 00000000..3280031f --- /dev/null +++ b/lib/a-set_test.c @@ -0,0 +1,240 @@ +/* + * BIRD -- Set/Community-list Operations Tests + * + * (c) 2015 CZ.NIC z.s.p.o. + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#include "test/birdtest.h" +#include "test/bt-utils.h" + +#include "lib/net.h" +#include "nest/rt.h" +#include "lib/attrs.h" +#include "lib/resource.h" + +#define SET_SIZE 10 +static const struct adata *set_sequence; /* <0; SET_SIZE) */ +static const struct adata *set_sequence_same; /* <0; SET_SIZE) */ +static const struct adata *set_sequence_higher; /* <SET_SIZE; 2*SET_SIZE) */ +static const struct adata *set_random; + +#define BUFFER_SIZE 1000 +static byte buf[BUFFER_SIZE] = {}; + +#define SET_SIZE_FOR_FORMAT_OUTPUT 10 + +enum set_type +{ + SET_TYPE_INT, + SET_TYPE_EC +}; + +static void +generate_set_sequence(enum set_type type, int len) +{ + struct adata empty_as_path = {}; + set_sequence = set_sequence_same = set_sequence_higher = set_random = &empty_as_path; + + int i; + for (i = 0; i < len; i++) + { + if (type == SET_TYPE_INT) + { + set_sequence = int_set_add(tmp_linpool, set_sequence, i); + set_sequence_same = int_set_add(tmp_linpool, set_sequence_same, i); + set_sequence_higher = int_set_add(tmp_linpool, set_sequence_higher, i + SET_SIZE); + set_random = int_set_add(tmp_linpool, set_random, bt_random()); + } + else if (type == SET_TYPE_EC) + { + set_sequence = ec_set_add(tmp_linpool, set_sequence, i); + set_sequence_same = ec_set_add(tmp_linpool, set_sequence_same, i); + set_sequence_higher = ec_set_add(tmp_linpool, set_sequence_higher, i + SET_SIZE); + set_random = ec_set_add(tmp_linpool, set_random, (bt_random() << 32 | bt_random())); + } + else + bt_abort_msg("This should be unreachable"); + } +} + +/* + * SET INT TESTS + */ + +static int +t_set_int_contains(void) +{ + int i; + + generate_set_sequence(SET_TYPE_INT, SET_SIZE); + + bt_assert(int_set_get_size(set_sequence) == SET_SIZE); + + for (i = 0; i < SET_SIZE; i++) + bt_assert(int_set_contains(set_sequence, i)); + bt_assert(int_set_contains(set_sequence, -1) == 0); + bt_assert(int_set_contains(set_sequence, SET_SIZE) == 0); + + int *data = int_set_get_data(set_sequence); + for (i = 0; i < SET_SIZE; i++) + bt_assert_msg(data[i] == i, "(data[i] = %d) == i = %d)", data[i], i); + + return 1; +} + +static int +t_set_int_union(void) +{ + generate_set_sequence(SET_TYPE_INT, SET_SIZE); + + const struct adata *set_union; + set_union = int_set_union(tmp_linpool, set_sequence, set_sequence_same); + bt_assert(int_set_get_size(set_union) == SET_SIZE); + bt_assert(int_set_format(set_union, 0, 2, buf, BUFFER_SIZE) == 0); + + set_union = int_set_union(tmp_linpool, set_sequence, set_sequence_higher); + bt_assert_msg(int_set_get_size(set_union) == SET_SIZE*2, "int_set_get_size(set_union) %d, SET_SIZE*2 %d", int_set_get_size(set_union), SET_SIZE*2); + bt_assert(int_set_format(set_union, 0, 2, buf, BUFFER_SIZE) == 0); + + return 1; +} + +static int +t_set_int_format(void) +{ + generate_set_sequence(SET_TYPE_INT, SET_SIZE_FOR_FORMAT_OUTPUT); + + bt_assert(int_set_format(set_sequence, 0, 0, buf, BUFFER_SIZE) == 0); + bt_assert(strcmp(buf, "0.0.0.0 0.0.0.1 0.0.0.2 0.0.0.3 0.0.0.4 0.0.0.5 0.0.0.6 0.0.0.7 0.0.0.8 0.0.0.9") == 0); + + bzero(buf, BUFFER_SIZE); + bt_assert(int_set_format(set_sequence, 0, 2, buf, BUFFER_SIZE) == 0); + bt_assert(strcmp(buf, "0.0.0.2 0.0.0.3 0.0.0.4 0.0.0.5 0.0.0.6 0.0.0.7 0.0.0.8 0.0.0.9") == 0); + + bzero(buf, BUFFER_SIZE); + bt_assert(int_set_format(set_sequence, 1, 0, buf, BUFFER_SIZE) == 0); + bt_assert(strcmp(buf, "(0,0) (0,1) (0,2) (0,3) (0,4) (0,5) (0,6) (0,7) (0,8) (0,9)") == 0); + + return 1; +} + +static int +t_set_int_delete(void) +{ + generate_set_sequence(SET_TYPE_INT, SET_SIZE); + + const struct adata *deleting_sequence = set_sequence; + u32 i; + for (i = 0; i < SET_SIZE; i++) + { + deleting_sequence = int_set_del(tmp_linpool, deleting_sequence, i); + bt_assert_msg(int_set_get_size(deleting_sequence) == (int) (SET_SIZE-1-i), + "int_set_get_size(deleting_sequence) %d == SET_SIZE-1-i %d", + int_set_get_size(deleting_sequence), + SET_SIZE-1-i); + } + + bt_assert(int_set_get_size(set_sequence) == SET_SIZE); + + return 1; +} + +/* + * SET EC TESTS + */ + +static int +t_set_ec_contains(void) +{ + u32 i; + + generate_set_sequence(SET_TYPE_EC, SET_SIZE); + + bt_assert(ec_set_get_size(set_sequence) == SET_SIZE); + + for (i = 0; i < SET_SIZE; i++) + bt_assert(ec_set_contains(set_sequence, i)); + bt_assert(ec_set_contains(set_sequence, -1) == 0); + bt_assert(ec_set_contains(set_sequence, SET_SIZE) == 0); + +// int *data = ec_set_get_data(set_sequence); +// for (i = 0; i < SET_SIZE; i++) +// bt_assert_msg(data[i] == (SET_SIZE-1-i), "(data[i] = %d) == ((SET_SIZE-1-i) = %d)", data[i], SET_SIZE-1-i); + + return 1; +} + +static int +t_set_ec_union(void) +{ + generate_set_sequence(SET_TYPE_EC, SET_SIZE); + + const struct adata *set_union; + set_union = ec_set_union(tmp_linpool, set_sequence, set_sequence_same); + bt_assert(ec_set_get_size(set_union) == SET_SIZE); + bt_assert(ec_set_format(set_union, 0, buf, BUFFER_SIZE) == 0); + + set_union = ec_set_union(tmp_linpool, set_sequence, set_sequence_higher); + bt_assert_msg(ec_set_get_size(set_union) == SET_SIZE*2, "ec_set_get_size(set_union) %d, SET_SIZE*2 %d", ec_set_get_size(set_union), SET_SIZE*2); + bt_assert(ec_set_format(set_union, 0, buf, BUFFER_SIZE) == 0); + + return 1; +} + +static int +t_set_ec_format(void) +{ + const struct adata empty_as_path = {}; + set_sequence = set_sequence_same = set_sequence_higher = set_random = &empty_as_path; + + u64 i = 0; + set_sequence = ec_set_add(tmp_linpool, set_sequence, i); + for (i = 1; i < SET_SIZE_FOR_FORMAT_OUTPUT; i++) + set_sequence = ec_set_add(tmp_linpool, set_sequence, i + ((i%2) ? ((u64)EC_RO << 48) : ((u64)EC_RT << 48))); + + bt_assert(ec_set_format(set_sequence, 0, buf, BUFFER_SIZE) == 0); + bt_assert_msg(strcmp(buf, "(unknown 0x0, 0, 0) (ro, 0, 1) (rt, 0, 2) (ro, 0, 3) (rt, 0, 4) (ro, 0, 5) (rt, 0, 6) (ro, 0, 7) (rt, 0, 8) (ro, 0, 9)") == 0, + "ec_set_format() returns '%s'", buf); + + return 1; +} + +static int +t_set_ec_delete(void) +{ + generate_set_sequence(SET_TYPE_EC, SET_SIZE); + + const struct adata *deleting_sequence = set_sequence; + u32 i; + for (i = 0; i < SET_SIZE; i++) + { + deleting_sequence = ec_set_del(tmp_linpool, deleting_sequence, i); + bt_assert_msg(ec_set_get_size(deleting_sequence) == (int) (SET_SIZE-1-i), + "ec_set_get_size(deleting_sequence) %d == SET_SIZE-1-i %d", + ec_set_get_size(deleting_sequence), SET_SIZE-1-i); + } + + bt_assert(ec_set_get_size(set_sequence) == SET_SIZE); + + return 1; +} + +int +main(int argc, char *argv[]) +{ + bt_init(argc, argv); + + bt_test_suite(t_set_int_contains, "Testing sets of integers: contains, get_data"); + bt_test_suite(t_set_int_format, "Testing sets of integers: format"); + bt_test_suite(t_set_int_union, "Testing sets of integers: union"); + bt_test_suite(t_set_int_delete, "Testing sets of integers: delete"); + + bt_test_suite(t_set_ec_contains, "Testing sets of Extended Community values: contains, get_data"); + bt_test_suite(t_set_ec_format, "Testing sets of Extended Community values: format"); + bt_test_suite(t_set_ec_union, "Testing sets of Extended Community values: union"); + bt_test_suite(t_set_ec_delete, "Testing sets of Extended Community values: delete"); + + return bt_exit_value(); +} diff --git a/lib/attrs.h b/lib/attrs.h new file mode 100644 index 00000000..79b7b14a --- /dev/null +++ b/lib/attrs.h @@ -0,0 +1,262 @@ +/* + * BIRD Internet Routing Daemon -- Attribute Operations + * + * (c) 2000 Martin Mares <mj@ucw.cz> + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#ifndef _BIRD_ATTRS_H_ +#define _BIRD_ATTRS_H_ + +#include <stdint.h> +#include "lib/unaligned.h" + +typedef struct adata { + uint length; /* Length of data */ + byte data[0]; +} adata; + +#define ADATA_SIZE(s) BIRD_CPU_ALIGN(sizeof(struct adata) + s) + +extern const adata null_adata; /* adata of length 0 */ + +static inline struct adata * +lp_alloc_adata(struct linpool *pool, uint len) +{ + struct adata *ad = lp_alloc(pool, sizeof(struct adata) + len); + ad->length = len; + return ad; +} + +static inline struct adata * +lp_store_adata(struct linpool *pool, const void *buf, uint len) +{ + struct adata *ad = lp_alloc_adata(pool, len); + memcpy(ad->data, buf, len); + return ad; +} + +#define tmp_alloc_adata(len) lp_alloc_adata(tmp_linpool, len) +#define tmp_store_adata(buf, len) lp_store_adata(tmp_linpool, buf, len) +#define tmp_copy_adata(ad) tmp_store_adata((ad)->data, (ad)->length) + +static inline int adata_same(const struct adata *a, const struct adata *b) +{ return (a->length == b->length && !memcmp(a->data, b->data, a->length)); } + + + +/* 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/lib/birdlib.h b/lib/birdlib.h index 431b7c0d..9b6e4a16 100644 --- a/lib/birdlib.h +++ b/lib/birdlib.h @@ -9,16 +9,29 @@ #ifndef _BIRD_BIRDLIB_H_ #define _BIRD_BIRDLIB_H_ +#include "sysdep/config.h" #include "lib/alloca.h" /* Ugly structure offset handling macros */ -struct align_probe { char x; long int y; }; - #define OFFSETOF(s, i) ((size_t) &((s *)0)->i) #define SKIP_BACK(s, i, p) ((s *)((char *)p - OFFSETOF(s, i))) #define BIRD_ALIGN(s, a) (((s)+a-1)&~(a-1)) -#define CPU_STRUCT_ALIGN (sizeof(struct align_probe)) +#define CPU_STRUCT_ALIGN (MAX_(_Alignof(void*), _Alignof(u64))) +#define BIRD_CPU_ALIGN(s) BIRD_ALIGN((s), CPU_STRUCT_ALIGN) + +/* Structure item alignment macros */ + +#define PADDING_NAME(id) _padding_##id +#define PADDING_(id, sz) u8 PADDING_NAME(id)[sz] + +#if CPU_POINTER_ALIGNMENT == 4 +#define PADDING(id, n32, n64) PADDING_(id, n32) +#elif CPU_POINTER_ALIGNMENT == 8 +#define PADDING(id, n32, n64) PADDING_(id, n64) +#else +#error "Strange CPU pointer alignment: " CPU_POINTER_ALIGNMENT +#endif /* Utility macros */ @@ -32,6 +45,9 @@ struct align_probe { char x; long int y; }; #define MAX(a,b) MAX_(a,b) #endif +#define ROUND_DOWN_POW2(a,b) ((a) & ~((b)-1)) +#define ROUND_UP_POW2(a,b) (((a)+((b)-1)) & ~((b)-1)) + #define U64(c) UINT64_C(c) #define ABS(a) ((a)>=0 ? (a) : -(a)) #define DELTA(a,b) (((a)>=(b))?(a)-(b):(b)-(a)) diff --git a/lib/bitmap_test.c b/lib/bitmap_test.c index 0595a4d0..07860c94 100644 --- a/lib/bitmap_test.c +++ b/lib/bitmap_test.c @@ -24,7 +24,6 @@ t_bmap_set_clear_random(void) { struct bmap b; - resource_init(); bmap_init(&b, &root_pool, 1024); char expected[MAX_NUM] = {}; @@ -60,7 +59,6 @@ t_hmap_set_clear_random(void) { struct hmap b; - resource_init(); hmap_init(&b, &root_pool, 1024); char expected[MAX_NUM] = {}; @@ -119,7 +117,6 @@ t_hmap_set_clear_fill(void) { struct hmap b; - resource_init(); hmap_init(&b, &root_pool, 1024); char expected[MAX_NUM] = {}; diff --git a/lib/buffer_test.c b/lib/buffer_test.c index 5b7de330..0629e901 100644 --- a/lib/buffer_test.c +++ b/lib/buffer_test.c @@ -41,7 +41,6 @@ fill_expected_array(void) static void init_buffer(void) { - resource_init(); buffer_pool = &root_pool; BUFFER_INIT(buf, buffer_pool, MAX_NUM); } diff --git a/lib/event.c b/lib/event.c index 273447e0..33dc00b0 100644 --- a/lib/event.c +++ b/lib/event.c @@ -157,6 +157,7 @@ ev_run_list(event_list *l) io_log_event(e->hook, e->data); ev_run(e); + tmp_flush(); } return !EMPTY_LIST(*l); @@ -184,6 +185,7 @@ ev_run_list_limited(event_list *l, uint limit) io_log_event(e->hook, e->data); ev_run(e); + tmp_flush(); limit--; } diff --git a/lib/event_test.c b/lib/event_test.c index e1215bba..3070327d 100644 --- a/lib/event_test.c +++ b/lib/event_test.c @@ -15,7 +15,7 @@ #include "nest/locks.h" #include "sysdep/unix/unix.h" #include "nest/iface.h" -#include "nest/route.h" +#include "nest/rt.h" #define MAX_NUM 4 @@ -53,11 +53,10 @@ t_ev_run_list(void) { int i; - resource_init(); olock_init(); timer_init(); - io_init(); rt_init(); + io_init(); if_init(); // roa_init(); config_init(); diff --git a/lib/fib.h b/lib/fib.h new file mode 100644 index 00000000..bec2a8d4 --- /dev/null +++ b/lib/fib.h @@ -0,0 +1,119 @@ +/* + * BIRD Internet Routing Daemon -- Network prefix storage + * + * (c) 1998--2000 Martin Mares <mj@ucw.cz> + * (c) 2022 Maria Matejka <mq@jmq.cz> + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#ifndef _BIRD_LIB_FIB_H_ +#define _BIRD_LIB_FIB_H_ + +/* + * BIRD FIBs are generic data structure for storing network prefixes. + * Also used for the master routing table. Currently implemented as + * a hash table. + * + * Available operations: + * - insertion of new entry + * - deletion of entry + * - searching for entry by network prefix + * - asynchronous retrieval of fib contents + */ + +struct fib; + +struct fib_node { + struct fib_node *next; /* Next in hash chain */ + struct fib_iterator *readers; /* List of readers of this node */ + net_addr addr[0]; +}; + +struct fib_iterator { /* See lib/slists.h for an explanation */ + struct fib_iterator *prev, *next; /* Must be synced with struct fib_node! */ + byte efef; /* 0xff to distinguish between iterator and node */ + byte pad[3]; + struct fib_node *node; /* Or NULL if freshly merged */ + uint hash; +}; + +typedef void (*fib_init_fn)(struct fib *, void *); + +struct fib { + pool *fib_pool; /* Pool holding all our data */ + slab *fib_slab; /* Slab holding all fib nodes */ + struct fib_node **hash_table; /* Node hash table */ + uint hash_size; /* Number of hash table entries (a power of two) */ + uint hash_order; /* Binary logarithm of hash_size */ + uint hash_shift; /* 32 - hash_order */ + uint addr_type; /* Type of address data stored in fib (NET_*) */ + uint node_size; /* FIB node size, 0 for nonuniform */ + uint node_offset; /* Offset of fib_node struct inside of user data */ + uint entries; /* Number of entries */ + uint entries_min, entries_max; /* Entry count limits (else start rehashing) */ + fib_init_fn init; /* Constructor */ +}; + +static inline void * fib_node_to_user(struct fib *f, struct fib_node *e) +{ return e ? (void *) ((char *) e - f->node_offset) : NULL; } + +static inline struct fib_node * fib_user_to_node(struct fib *f, void *e) +{ return e ? (void *) ((char *) e + f->node_offset) : NULL; } + +void fib_init(struct fib *f, pool *p, uint addr_type, uint node_size, uint node_offset, uint hash_order, fib_init_fn init); +void *fib_find(struct fib *, const net_addr *); /* Find or return NULL if doesn't exist */ +void *fib_get_chain(struct fib *f, const net_addr *a); /* Find first node in linked list from hash table */ +void *fib_get(struct fib *, const net_addr *); /* Find or create new if nonexistent */ +void *fib_route(struct fib *, const net_addr *); /* Longest-match routing lookup */ +void fib_delete(struct fib *, void *); /* Remove fib entry */ +void fib_free(struct fib *); /* Destroy the fib */ +void fib_check(struct fib *); /* Consistency check for debugging */ + +void fit_init(struct fib_iterator *, struct fib *); /* Internal functions, don't call */ +struct fib_node *fit_get(struct fib *, struct fib_iterator *); +void fit_put(struct fib_iterator *, struct fib_node *); +void fit_put_next(struct fib *f, struct fib_iterator *i, struct fib_node *n, uint hpos); +void fit_put_end(struct fib_iterator *i); +void fit_copy(struct fib *f, struct fib_iterator *dst, struct fib_iterator *src); + + +#define FIB_WALK(fib, type, z) do { \ + struct fib_node *fn_, **ff_ = (fib)->hash_table; \ + uint count_ = (fib)->hash_size; \ + type *z; \ + while (count_--) \ + for (fn_ = *ff_++; z = fib_node_to_user(fib, fn_); fn_=fn_->next) + +#define FIB_WALK_END } while (0) + +#define FIB_ITERATE_INIT(it, fib) fit_init(it, fib) + +#define FIB_ITERATE_START(fib, it, type, z) do { \ + struct fib_node *fn_ = fit_get(fib, it); \ + uint count_ = (fib)->hash_size; \ + uint hpos_ = (it)->hash; \ + type *z; \ + for(;;) { \ + if (!fn_) \ + { \ + if (++hpos_ >= count_) \ + break; \ + fn_ = (fib)->hash_table[hpos_]; \ + continue; \ + } \ + z = fib_node_to_user(fib, fn_); + +#define FIB_ITERATE_END fn_ = fn_->next; } } while(0) + +#define FIB_ITERATE_PUT(it) fit_put(it, fn_) + +#define FIB_ITERATE_PUT_NEXT(it, fib) fit_put_next(fib, it, fn_, hpos_) + +#define FIB_ITERATE_PUT_END(it) fit_put_end(it) + +#define FIB_ITERATE_UNLINK(it, fib) fit_get(fib, it) + +#define FIB_ITERATE_COPY(dst, src, fib) fit_copy(fib, dst, src) + +#endif diff --git a/lib/flowspec_test.c b/lib/flowspec_test.c index ed4afe51..03649b99 100644 --- a/lib/flowspec_test.c +++ b/lib/flowspec_test.c @@ -446,10 +446,7 @@ t_validation6(void) static int t_builder4(void) { - resource_init(); - struct flow_builder *fb = flow_builder_init(&root_pool); - linpool *lp = lp_new_default(&root_pool); /* Expectation */ @@ -492,7 +489,7 @@ t_builder4(void) flow_builder_set_type(fb, FLOW_TYPE_TCP_FLAGS); flow_builder_add_op_val(fb, 0, 0x55); - net_addr_flow4 *res = flow_builder4_finalize(fb, lp); + net_addr_flow4 *res = flow_builder4_finalize(fb, tmp_linpool); bt_assert(memcmp(res, expect, expect->length) == 0); @@ -529,8 +526,6 @@ t_builder6(void) { net_addr_ip6 ip; - resource_init(); - linpool *lp = lp_new_default(&root_pool); struct flow_builder *fb = flow_builder_init(&root_pool); fb->ipv6 = 1; @@ -574,7 +569,7 @@ t_builder6(void) flow_builder_set_type(fb, FLOW_TYPE_LABEL); flow_builder_add_op_val(fb, 0, 0x55); - net_addr_flow6 *res = flow_builder6_finalize(fb, lp); + net_addr_flow6 *res = flow_builder6_finalize(fb, tmp_linpool); bt_assert(memcmp(res, expect, expect->length) == 0); /* Reverse order */ @@ -601,7 +596,7 @@ t_builder6(void) flow_builder_set_type(fb, FLOW_TYPE_DST_PREFIX); flow_builder6_add_pfx(fb, &ip, 61); - res = flow_builder6_finalize(fb, lp); + res = flow_builder6_finalize(fb, tmp_linpool); bt_assert(memcmp(res, expect, expect->length) == 0); return 1; diff --git a/lib/hash_test.c b/lib/hash_test.c index 59beb7c0..4bce7017 100644 --- a/lib/hash_test.c +++ b/lib/hash_test.c @@ -61,7 +61,6 @@ dump_nodes(void) static void init_hash_(uint order) { - resource_init(); my_pool = rp_new(&root_pool, "Test pool"); HASH_INIT(hash, my_pool, order); @@ -85,25 +85,29 @@ ip4_classify(ip4_addr ad) u32 a = _I(ad); u32 b = a >> 24U; - if (b && b <= 0xdf) + if (b < 0xe0) { - if (b == 0x7f) + if (b == 0x00) /* 0.0.0.0/8 This network */ + return IADDR_INVALID; + + if (b == 0x7f) /* 127.0.0.0/8 Loopback address */ return IADDR_HOST | SCOPE_HOST; - else if ((b == 0x0a) || - ((a & 0xffff0000) == 0xc0a80000) || - ((a & 0xfff00000) == 0xac100000)) + + if ((b == 0x0a) || /* 10.0.0.0/8 Private range */ + ((a & 0xffff0000) == 0xc0a80000) || /* 192.168.0.0/16 Private range */ + ((a & 0xfff00000) == 0xac100000)) /* 172.16.0.0/12 Private range */ return IADDR_HOST | SCOPE_SITE; - else - return IADDR_HOST | SCOPE_UNIVERSE; + + return IADDR_HOST | SCOPE_UNIVERSE; } - if (b >= 0xe0 && b <= 0xef) + if (b < 0xf0) /* 224.0.0.0/4 Multicast address */ return IADDR_MULTICAST | SCOPE_UNIVERSE; - if (a == 0xffffffff) + if (a == 0xffffffff) /* 255.255.255.255 Broadcast address */ return IADDR_BROADCAST | SCOPE_LINK; - return IADDR_INVALID; + return IADDR_HOST | SCOPE_SITE; /* 240.0.0.0/4 Reserved / private */ } int @@ -279,11 +279,35 @@ static inline uint ip6_pxlen(ip6_addr a, ip6_addr b) return 32 * i + 31 - u32_log2(a.addr[i] ^ b.addr[i]); } +static inline int ip4_prefix_equal(ip4_addr a, ip4_addr b, uint n) +{ + return (_I(a) ^ _I(b)) < ((u64) 1 << (32 - n)); +} + +static inline int ip6_prefix_equal(ip6_addr a, ip6_addr b, uint n) +{ + uint n0 = n / 32; + uint n1 = n % 32; + + return + ((n0 <= 0) || (_I0(a) == _I0(b))) && + ((n0 <= 1) || (_I1(a) == _I1(b))) && + ((n0 <= 2) || (_I2(a) == _I2(b))) && + ((n0 <= 3) || (_I3(a) == _I3(b))) && + (!n1 || ((a.addr[n0] ^ b.addr[n0]) < (1u << (32 - n1)))); +} + static inline u32 ip4_getbit(ip4_addr a, uint pos) -{ return _I(a) & (0x80000000 >> pos); } +{ return (_I(a) >> (31 - pos)) & 1; } + +static inline u32 ip4_getbits(ip4_addr a, uint pos, uint n) +{ return (_I(a) >> ((32 - n) - pos)) & ((1u << n) - 1); } static inline u32 ip6_getbit(ip6_addr a, uint pos) -{ return a.addr[pos / 32] & (0x80000000 >> (pos % 32)); } +{ return (a.addr[pos / 32] >> (31 - (pos % 32))) & 0x1; } + +static inline u32 ip6_getbits(ip6_addr a, uint pos, uint n) +{ return (a.addr[pos / 32] >> ((32 - n) - (pos % 32))) & ((1u << n) - 1); } static inline u32 ip4_setbit(ip4_addr *a, uint pos) { return _I(*a) |= (0x80000000 >> pos); } @@ -297,6 +321,13 @@ static inline u32 ip4_clrbit(ip4_addr *a, uint pos) static inline u32 ip6_clrbit(ip6_addr *a, uint pos) { return a->addr[pos / 32] &= ~(0x80000000 >> (pos % 32)); } +static inline ip4_addr ip4_setbits(ip4_addr a, uint pos, uint val) +{ _I(a) |= val << (31 - pos); return a; } + +static inline ip6_addr ip6_setbits(ip6_addr a, uint pos, uint val) +{ a.addr[pos / 32] |= val << (31 - pos % 32); return a; } + + static inline ip4_addr ip4_opposite_m1(ip4_addr a) { return _MI4(_I(a) ^ 1); } @@ -331,11 +362,7 @@ static inline ip6_addr ip6_hton(ip6_addr a) static inline ip6_addr ip6_ntoh(ip6_addr a) { return _MI6(ntohl(_I0(a)), ntohl(_I1(a)), ntohl(_I2(a)), ntohl(_I3(a))); } -#define MPLS_MAX_LABEL_STACK 8 -typedef struct mpls_label_stack { - uint len; - u32 stack[MPLS_MAX_LABEL_STACK]; -} mpls_label_stack; +#define MPLS_MAX_LABEL_STACK 16 static inline int mpls_get(const char *buf, int buflen, u32 *stack) diff --git a/lib/ip_test.c b/lib/ip_test.c index 36d10d68..eee0a427 100644 --- a/lib/ip_test.c +++ b/lib/ip_test.c @@ -167,6 +167,70 @@ t_ip6_ntop(void) return bt_assert_batch(test_vectors, test_ipa_ntop, bt_fmt_ipa, bt_fmt_str); } +static int +t_ip4_prefix_equal(void) +{ + bt_assert( ip4_prefix_equal(ip4_from_u32(0x12345678), ip4_from_u32(0x1234ffff), 16)); + bt_assert(!ip4_prefix_equal(ip4_from_u32(0x12345678), ip4_from_u32(0x1234ffff), 17)); + bt_assert( ip4_prefix_equal(ip4_from_u32(0x12345678), ip4_from_u32(0x12345000), 21)); + bt_assert(!ip4_prefix_equal(ip4_from_u32(0x12345678), ip4_from_u32(0x12345000), 22)); + + bt_assert( ip4_prefix_equal(ip4_from_u32(0x00000000), ip4_from_u32(0xffffffff), 0)); + bt_assert( ip4_prefix_equal(ip4_from_u32(0x12345678), ip4_from_u32(0x12345678), 0)); + + bt_assert( ip4_prefix_equal(ip4_from_u32(0x12345678), ip4_from_u32(0x12345678), 32)); + bt_assert(!ip4_prefix_equal(ip4_from_u32(0x12345678), ip4_from_u32(0x12345679), 32)); + bt_assert(!ip4_prefix_equal(ip4_from_u32(0x12345678), ip4_from_u32(0x92345678), 32)); + + return 1; +} + +static int +t_ip6_prefix_equal(void) +{ + bt_assert( ip6_prefix_equal(ip6_build(0x20010db8, 0x12345678, 0x10101010, 0x20202020), + ip6_build(0x20010db8, 0x1234ffff, 0xfefefefe, 0xdcdcdcdc), + 48)); + + bt_assert(!ip6_prefix_equal(ip6_build(0x20010db8, 0x12345678, 0x10101010, 0x20202020), + ip6_build(0x20010db8, 0x1234ffff, 0xfefefefe, 0xdcdcdcdc), + 49)); + + bt_assert(!ip6_prefix_equal(ip6_build(0x20010db8, 0x12345678, 0x10101010, 0x20202020), + ip6_build(0x20020db8, 0x12345678, 0xfefefefe, 0xdcdcdcdc), + 48)); + + bt_assert( ip6_prefix_equal(ip6_build(0x20010db8, 0x12345678, 0x10101010, 0x20202020), + ip6_build(0x20010db8, 0x12345678, 0xfefefefe, 0xdcdcdcdc), + 64)); + + bt_assert(!ip6_prefix_equal(ip6_build(0x20010db8, 0x12345678, 0x10101010, 0x20202020), + ip6_build(0x20010db8, 0x1234567e, 0xfefefefe, 0xdcdcdcdc), + 64)); + + bt_assert( ip6_prefix_equal(ip6_build(0x20010db8, 0x12345678, 0x10101010, 0x20002020), + ip6_build(0x20010db8, 0x12345678, 0x10101010, 0x20202020), + 106)); + + bt_assert(!ip6_prefix_equal(ip6_build(0x20010db8, 0x12345678, 0x10101010, 0x20002020), + ip6_build(0x20010db8, 0x12345678, 0x10101010, 0x20202020), + 107)); + + bt_assert( ip6_prefix_equal(ip6_build(0xfeef0db8, 0x87654321, 0x10101010, 0x20202020), + ip6_build(0x20010db8, 0x12345678, 0xfefefefe, 0xdcdcdcdc), + 0)); + + bt_assert( ip6_prefix_equal(ip6_build(0x20010db8, 0x12345678, 0x10101010, 0x20202020), + ip6_build(0x20010db8, 0x12345678, 0x10101010, 0x20202020), + 128)); + + bt_assert(!ip6_prefix_equal(ip6_build(0x20010db8, 0x12345678, 0x10101010, 0x20202020), + ip6_build(0x20010db8, 0x12345678, 0x10101010, 0x20202021), + 128)); + + return 1; +} + int main(int argc, char *argv[]) { @@ -176,6 +240,8 @@ main(int argc, char *argv[]) bt_test_suite(t_ip6_pton, "Converting IPv6 string to ip6_addr struct"); bt_test_suite(t_ip4_ntop, "Converting ip4_addr struct to IPv4 string"); bt_test_suite(t_ip6_ntop, "Converting ip6_addr struct to IPv6 string"); + bt_test_suite(t_ip4_prefix_equal, "Testing ip4_prefix_equal()"); + bt_test_suite(t_ip6_prefix_equal, "Testing ip6_prefix_equal()"); return bt_exit_value(); } diff --git a/lib/lists.h b/lib/lists.h index 479f4ed1..7e6d5467 100644 --- a/lib/lists.h +++ b/lib/lists.h @@ -42,6 +42,7 @@ typedef union list { /* In fact two overlayed nodes */ }; } list; +#define STATIC_LIST_INIT(name) name = { .head = &name.tail_node, .tail = &name.head_node, .null = NULL } #define NODE (node *) #define HEAD(list) ((void *)((list).head)) diff --git a/lib/mempool.c b/lib/mempool.c index 8f300b81..33eaec86 100644 --- a/lib/mempool.c +++ b/lib/mempool.c @@ -27,26 +27,24 @@ struct lp_chunk { struct lp_chunk *next; - uint size; uintptr_t data_align[0]; byte data[0]; }; -const int lp_chunk_size = sizeof(struct lp_chunk); +#define LP_DATA_SIZE (page_size - OFFSETOF(struct lp_chunk, data)) struct linpool { resource r; byte *ptr, *end; - pool *p; struct lp_chunk *first, *current; /* Normal (reusable) chunks */ struct lp_chunk *first_large; /* Large chunks */ - uint chunk_size, threshold, total:31, use_pages:1, total_large; + uint total, total_large; }; static void lp_free(resource *); static void lp_dump(resource *); static resource *lp_lookup(resource *, unsigned long); -static size_t lp_memsize(resource *r); +static struct resmem lp_memsize(resource *r); static struct resclass lp_class = { "LinPool", @@ -60,26 +58,14 @@ static struct resclass lp_class = { /** * lp_new - create a new linear memory pool * @p: pool - * @blk: block size * * lp_new() creates a new linear memory pool resource inside the pool @p. - * The linear pool consists of a list of memory chunks of size at least - * @blk. + * The linear pool consists of a list of memory chunks of page size. */ linpool -*lp_new(pool *p, uint blk) +*lp_new(pool *p) { - linpool *m = ralloc(p, &lp_class); - m->p = p; - if (!blk) - { - m->use_pages = 1; - blk = page_size - lp_chunk_size; - } - - m->chunk_size = blk; - m->threshold = 3*blk/4; - return m; + return ralloc(p, &lp_class); } /** @@ -110,14 +96,13 @@ lp_alloc(linpool *m, uint size) else { struct lp_chunk *c; - if (size >= m->threshold) + if (size > LP_DATA_SIZE) { /* Too large => allocate large chunk */ c = xmalloc(sizeof(struct lp_chunk) + size); m->total_large += size; c->next = m->first_large; m->first_large = c; - c->size = size; } else { @@ -129,14 +114,10 @@ lp_alloc(linpool *m, uint size) else { /* Need to allocate a new chunk */ - if (m->use_pages) - c = alloc_page(m->p); - else - c = xmalloc(sizeof(struct lp_chunk) + m->chunk_size); + c = alloc_page(); - m->total += m->chunk_size; + m->total += LP_DATA_SIZE; c->next = NULL; - c->size = m->chunk_size; if (m->current) m->current->next = c; @@ -145,7 +126,7 @@ lp_alloc(linpool *m, uint size) } m->current = c; m->ptr = c->data + size; - m->end = c->data + m->chunk_size; + m->end = c->data + LP_DATA_SIZE; } return c->data; } @@ -207,7 +188,7 @@ lp_flush(linpool *m) /* Move ptr to the first chunk and free all large chunks */ m->current = c = m->first; m->ptr = c ? c->data : NULL; - m->end = c ? c->data + m->chunk_size : NULL; + m->end = c ? c->data + LP_DATA_SIZE : NULL; while (c = m->first_large) { @@ -230,6 +211,7 @@ lp_save(linpool *m, lp_state *p) { p->current = m->current; p->large = m->first_large; + p->total_large = m->total_large; p->ptr = m->ptr; } @@ -251,12 +233,12 @@ lp_restore(linpool *m, lp_state *p) /* Move ptr to the saved pos and free all newer large chunks */ m->current = c = p->current; m->ptr = p->ptr; - m->end = c ? c->data + m->chunk_size : NULL; + m->end = c ? c->data + LP_DATA_SIZE : NULL; + m->total_large = p->total_large; while ((c = m->first_large) && (c != p->large)) { m->first_large = c->next; - m->total_large -= c->size; xfree(c); } } @@ -270,10 +252,7 @@ lp_free(resource *r) for(d=m->first; d; d = c) { c = d->next; - if (m->use_pages) - free_page(m->p, d); - else - xfree(d); + free_page(d); } for(d=m->first_large; d; d = c) { @@ -293,30 +272,33 @@ lp_dump(resource *r) ; for(cntl=0, c=m->first_large; c; c=c->next, cntl++) ; - debug("(chunk=%d threshold=%d count=%d+%d total=%d+%d)\n", - m->chunk_size, - m->threshold, + debug("(count=%d+%d total=%d+%d)\n", cnt, cntl, m->total, m->total_large); } -static size_t +static struct resmem lp_memsize(resource *r) { linpool *m = (linpool *) r; - struct lp_chunk *c; - int cnt = 0; + struct resmem sz = { + .overhead = sizeof(struct linpool) + ALLOC_OVERHEAD, + .effective = m->total_large, + }; - for(c=m->first; c; c=c->next) - cnt++; - for(c=m->first_large; c; c=c->next) - cnt++; + for (struct lp_chunk *c = m->first_large; c; c = c->next) + sz.overhead += sizeof(struct lp_chunk) + ALLOC_OVERHEAD; - return ALLOC_OVERHEAD + sizeof(struct linpool) + - cnt * (ALLOC_OVERHEAD + sizeof(struct lp_chunk)) + - m->total + m->total_large; + uint regular = 0; + for (struct lp_chunk *c = m->first; c; c = c->next) + regular++; + + sz.effective += LP_DATA_SIZE * regular; + sz.overhead += (sizeof(struct lp_chunk) + ALLOC_OVERHEAD) * regular; + + return sz; } @@ -327,10 +309,7 @@ lp_lookup(resource *r, unsigned long a) struct lp_chunk *c; for(c=m->first; c; c=c->next) - if ((unsigned long) c->data <= a && (unsigned long) c->data + c->size > a) - return r; - for(c=m->first_large; c; c=c->next) - if ((unsigned long) c->data <= a && (unsigned long) c->data + c->size > a) + if ((unsigned long) c->data <= a && (unsigned long) c->data + LP_DATA_SIZE > a) return r; return NULL; } @@ -38,6 +38,7 @@ #define NB_IP (NB_IP4 | NB_IP6) #define NB_VPN (NB_VPN4 | NB_VPN6) +#define NB_ROA (NB_ROA4 | NB_ROA6) #define NB_FLOW (NB_FLOW4 | NB_FLOW6) #define NB_DEST (NB_IP | NB_IP6_SADR | NB_VPN | NB_MPLS) #define NB_ANY 0xffffffff diff --git a/lib/printf.c b/lib/printf.c index 236df427..424d545f 100644 --- a/lib/printf.c +++ b/lib/printf.c @@ -568,3 +568,51 @@ buffer_puts(buffer *buf, const char *str) buf->pos = (bp < be) ? bp : buf->end; } + +#define POOL_PRINTF_MAXBUF 1024 + +char *mb_vsprintf(pool *p, const char *fmt, va_list args) +{ + char buf[POOL_PRINTF_MAXBUF]; + int count = bvsnprintf(buf, POOL_PRINTF_MAXBUF, fmt, args); + + if (count < 0) + bug("Attempted to mb_vsprintf() a too long string"); + + char *out = mb_alloc(p, count + 1); + memcpy(out, buf, count + 1); + return out; +} + +char *mb_sprintf(pool *p, const char *fmt, ...) +{ + va_list args; + char *out; + va_start(args, fmt); + out = mb_vsprintf(p, fmt, args); + va_end(args); + return out; +} + +char *lp_vsprintf(linpool *p, const char *fmt, va_list args) +{ + char buf[POOL_PRINTF_MAXBUF]; + int count = bvsnprintf(buf, POOL_PRINTF_MAXBUF, fmt, args); + + if (count < 0) + bug("Attempted to mb_vsprintf() a too long string"); + + char *out = lp_alloc(p, count + 1); + memcpy(out, buf, count + 1); + return out; +} + +char *lp_sprintf(linpool *p, const char *fmt, ...) +{ + va_list args; + char *out; + va_start(args, fmt); + out = lp_vsprintf(p, fmt, args); + va_end(args); + return out; +} diff --git a/lib/resource.c b/lib/resource.c index e80b315b..c31d9889 100644 --- a/lib/resource.c +++ b/lib/resource.c @@ -2,6 +2,7 @@ * BIRD Resource Manager * * (c) 1998--2000 Martin Mares <mj@ucw.cz> + * (c) 2021 Maria Matejka <mq@jmq.cz> * * Can be freely distributed and used under the terms of the GNU GPL. */ @@ -31,22 +32,13 @@ struct pool { resource r; list inside; - struct pool_pages *pages; const char *name; }; -struct pool_pages { - uint free; - uint used; - void *ptr[0]; -}; - -#define POOL_PAGES_MAX ((page_size - sizeof(struct pool_pages)) / sizeof (void *)) - static void pool_dump(resource *); static void pool_free(resource *); static resource *pool_lookup(resource *, unsigned long); -static size_t pool_memsize(resource *P); +static struct resmem pool_memsize(resource *P); static struct resclass pool_class = { "Pool", @@ -59,9 +51,6 @@ static struct resclass pool_class = { pool root_pool; -void *alloc_sys_page(void); -void free_sys_page(void *); - static int indent; /** @@ -81,6 +70,20 @@ rp_new(pool *p, const char *name) return z; } +pool * +rp_newf(pool *p, const char *fmt, ...) +{ + pool *z = rp_new(p, NULL); + + va_list args; + va_start(args, fmt); + z->name = mb_vsprintf(p, fmt, args); + va_end(args); + + return z; +} + + static void pool_free(resource *P) { @@ -94,14 +97,6 @@ pool_free(resource *P) xfree(r); r = rr; } - - if (p->pages) - { - ASSERT_DIE(!p->pages->used); - for (uint i=0; i<p->pages->free; i++) - free_sys_page(p->pages->ptr[i]); - free_sys_page(p->pages); - } } static void @@ -117,18 +112,22 @@ pool_dump(resource *P) indent -= 3; } -static size_t +static struct resmem pool_memsize(resource *P) { pool *p = (pool *) P; resource *r; - size_t sum = sizeof(pool) + ALLOC_OVERHEAD; + struct resmem sum = { + .effective = 0, + .overhead = sizeof(pool) + ALLOC_OVERHEAD, + }; WALK_LIST(r, p->inside) - sum += rmemsize(r); - - if (p->pages) - sum += page_size * (p->pages->used + p->pages->free + 1); + { + struct resmem add = rmemsize(r); + sum.effective += add.effective; + sum.overhead += add.overhead; + } return sum; } @@ -216,14 +215,17 @@ rdump(void *res) debug("NULL\n"); } -size_t +struct resmem rmemsize(void *res) { resource *r = res; if (!r) - return 0; + return (struct resmem) {}; if (!r->class->memsize) - return r->class->size + ALLOC_OVERHEAD; + return (struct resmem) { + .effective = r->class->size - sizeof(resource), + .overhead = ALLOC_OVERHEAD + sizeof(resource), + }; return r->class->memsize(r); } @@ -282,11 +284,33 @@ rlookup(unsigned long a) void resource_init(void) { + resource_sys_init(); + root_pool.r.class = &pool_class; root_pool.name = "Root"; init_list(&root_pool.inside); + tmp_init(&root_pool); +} + +_Thread_local struct tmp_resources tmp_res; + +void +tmp_init(pool *p) +{ + tmp_res.lp = lp_new_default(p); + tmp_res.parent = p; + tmp_res.pool = rp_new(p, "TMP"); +} + +void +tmp_flush(void) +{ + lp_flush(tmp_linpool); + rfree(tmp_res.pool); + tmp_res.pool = rp_new(tmp_res.parent, "TMP"); } + /** * DOC: Memory blocks * @@ -328,11 +352,14 @@ mbl_lookup(resource *r, unsigned long a) return NULL; } -static size_t +static struct resmem mbl_memsize(resource *r) { struct mblock *m = (struct mblock *) r; - return ALLOC_OVERHEAD + sizeof(struct mblock) + m->size; + return (struct resmem) { + .effective = m->size, + .overhead = ALLOC_OVERHEAD + sizeof(struct mblock), + }; } static struct resclass mb_class = { @@ -416,21 +443,6 @@ mb_realloc(void *m, unsigned size) return b->data; } -/** - * mb_move - move a memory block - * @m: memory block - * @p: target pool - * - * mb_move() moves the given memory block to another pool in the same way - * as rmove() moves a plain resource. - */ -void -mb_move(void *m, pool *p) -{ - struct mblock *b = SKIP_BACK(struct mblock, data, m); - rmove(b, p); -} - /** * mb_free - free a memory block @@ -448,39 +460,6 @@ mb_free(void *m) rfree(b); } -void * -alloc_page(pool *p) -{ - if (!p->pages) - { - p->pages = alloc_sys_page(); - p->pages->free = 0; - p->pages->used = 1; - } - else - p->pages->used++; - - if (p->pages->free) - { - void *ptr = p->pages->ptr[--p->pages->free]; - bzero(ptr, page_size); - return ptr; - } - else - return alloc_sys_page(); -} - -void -free_page(pool *p, void *ptr) -{ - ASSERT_DIE(p->pages); - p->pages->used--; - - if (p->pages->free >= POOL_PAGES_MAX) - return free_sys_page(ptr); - else - p->pages->ptr[p->pages->free++] = ptr; -} #define STEP_UP(x) ((x) + (x)/2 + 4) diff --git a/lib/resource.h b/lib/resource.h index 26030aea..4cedbf00 100644 --- a/lib/resource.h +++ b/lib/resource.h @@ -2,6 +2,7 @@ * BIRD Resource Manager * * (c) 1998--1999 Martin Mares <mj@ucw.cz> + * (c) 2021 Maria Matejka <mq@jmq.cz> * * Can be freely distributed and used under the terms of the GNU GPL. */ @@ -11,6 +12,11 @@ #include "lib/lists.h" +struct resmem { + size_t effective; /* Memory actually used for data storage */ + size_t overhead; /* Overhead memory imposed by allocator strategies */ +}; + /* Resource */ typedef struct resource { @@ -26,11 +32,11 @@ struct resclass { void (*free)(resource *); /* Freeing function */ void (*dump)(resource *); /* Dump to debug output */ resource *(*lookup)(resource *, unsigned long); /* Look up address (only for debugging) */ - size_t (*memsize)(resource *); /* Return size of memory used by the resource, may be NULL */ + struct resmem (*memsize)(resource *); /* Return size of memory used by the resource, may be NULL */ }; /* Estimate of system allocator overhead per item, for memory consumtion stats */ -#define ALLOC_OVERHEAD 8 +#define ALLOC_OVERHEAD 16 /* Generic resource manipulation */ @@ -38,9 +44,10 @@ typedef struct pool pool; void resource_init(void); pool *rp_new(pool *, const char *); /* Create new pool */ +pool *rp_newf(pool *, const char *, ...); /* Create a new pool with a formatted string as its name */ void rfree(void *); /* Free single resource */ void rdump(void *); /* Dump to debug output */ -size_t rmemsize(void *res); /* Return size of memory used by the resource */ +struct resmem rmemsize(void *res); /* Return size of memory used by the resource */ void rlookup(unsigned long); /* Look up address (only for debugging) */ void rmove(void *, pool *); /* Move to a different pool */ @@ -53,7 +60,6 @@ extern pool root_pool; void *mb_alloc(pool *, unsigned size); void *mb_allocz(pool *, unsigned size); void *mb_realloc(void *m, unsigned size); -void mb_move(void *, pool *); void mb_free(void *); /* Memory pools with linear allocation */ @@ -63,9 +69,10 @@ typedef struct linpool linpool; typedef struct lp_state { void *current, *large; byte *ptr; + uint total_large; } lp_state; -linpool *lp_new(pool *, unsigned blk); +linpool *lp_new(pool *); void *lp_alloc(linpool *, unsigned size); /* Aligned */ void *lp_allocu(linpool *, unsigned size); /* Unaligned */ void *lp_allocz(linpool *, unsigned size); /* With clear */ @@ -73,10 +80,23 @@ void lp_flush(linpool *); /* Free everything, but leave linpool */ void lp_save(linpool *m, lp_state *p); /* Save state */ void lp_restore(linpool *m, lp_state *p); /* Restore state */ -extern const int lp_chunk_size; -#define LP_GAS 1024 -#define LP_GOOD_SIZE(x) (((x + LP_GAS - 1) & (~(LP_GAS - 1))) - lp_chunk_size) -#define lp_new_default(p) lp_new(p, 0) +struct tmp_resources { + pool *pool, *parent; + linpool *lp; +}; + +extern _Thread_local struct tmp_resources tmp_res; + +#define tmp_linpool tmp_res.lp +#define tmp_alloc(sz) lp_alloc(tmp_linpool, sz) +#define tmp_allocu(sz) lp_allocu(tmp_linpool, sz) +#define tmp_allocz(sz) lp_allocz(tmp_linpool, sz) + +void tmp_init(pool *p); +void tmp_flush(void); + + +#define lp_new_default lp_new /* Slabs */ @@ -85,7 +105,7 @@ typedef struct slab slab; slab *sl_new(pool *, unsigned size); void *sl_alloc(slab *); void *sl_allocz(slab *); -void sl_free(slab *, void *); +void sl_free(void *); /* * Low-level memory allocation functions, please don't use @@ -94,12 +114,12 @@ void sl_free(slab *, void *); void buffer_realloc(void **buf, unsigned *size, unsigned need, unsigned item_size); +/* Allocator of whole pages; for use in slabs and other high-level allocators. */ extern long page_size; +void *alloc_page(void); +void free_page(void *); -/* Allocator of whole pages; for use in slabs and other high-level allocators. */ -void *alloc_page(pool *); -void free_page(pool *, void *); -#define PAGE_HEAD(x) ((void *) (((intptr_t) (x)) & ~(page_size-1))) +void resource_sys_init(void); #ifdef HAVE_LIBDMALLOC /* diff --git a/lib/route.h b/lib/route.h new file mode 100644 index 00000000..283a3760 --- /dev/null +++ b/lib/route.h @@ -0,0 +1,433 @@ +/* + * BIRD Internet Routing Daemon -- Routing data structures + * + * (c) 1998--2000 Martin Mares <mj@ucw.cz> + * (c) 2022 Maria Matejka <mq@jmq.cz> + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#ifndef _BIRD_LIB_ROUTE_H_ +#define _BIRD_LIB_ROUTE_H_ + +#include "lib/type.h" + +struct network; +struct proto; +struct cli; + + +typedef struct rte { + struct rta *attrs; /* Attributes of this route */ + const net_addr *net; /* Network this RTE belongs to */ + struct rte_src *src; /* Route source that created the route */ + struct rt_import_hook *sender; /* Import hook used to send the route to the routing table */ + btime lastmod; /* Last modified (set by table) */ + u32 id; /* Table specific route id */ + byte flags; /* Table-specific flags */ + byte pflags; /* Protocol-specific flags */ + u8 generation; /* If this route import is based on other previously exported route, + this value should be 1 + MAX(generation of the parent routes). + Otherwise the route is independent and this value is zero. */ +} rte; + +#define REF_FILTERED 2 /* Route is rejected by import filter */ +#define REF_STALE 4 /* Route is stale in a refresh cycle */ +#define REF_DISCARD 8 /* Route is scheduled for discard */ +#define REF_MODIFY 16 /* Route is scheduled for modify */ + +/* Route is valid for propagation (may depend on other flags in the future), accepts NULL */ +static inline int rte_is_valid(rte *r) { return r && !(r->flags & REF_FILTERED); } + +/* Route just has REF_FILTERED flag */ +static inline int rte_is_filtered(rte *r) { return !!(r->flags & REF_FILTERED); } + +struct rte_src { + struct rte_src *next; /* Hash chain */ + struct proto *proto; /* Protocol the source is based on */ + u32 private_id; /* Private ID, assigned by the protocol */ + u32 global_id; /* Globally unique ID of the source */ + unsigned uc; /* Use count */ +}; + + +struct rte_src *rt_find_source(struct proto *p, u32 id); +struct rte_src *rt_get_source(struct proto *p, u32 id); +static inline void rt_lock_source(struct rte_src *src) { src->uc++; } +static inline void rt_unlock_source(struct rte_src *src) { src->uc--; } +void rt_prune_sources(void); + +/* + * Route Attributes + * + * Beware: All standard BGP attributes must be represented here instead + * of making them local to the route. This is needed to ensure proper + * construction of BGP route attribute lists. + */ + +/* Nexthop structure */ +struct nexthop { + ip_addr gw; /* Next hop */ + struct iface *iface; /* Outgoing interface */ + byte flags; + byte weight; + byte labels; /* Number of all labels */ + u32 label[0]; +}; + +/* For packing one into eattrs */ +struct nexthop_adata { + struct adata ad; + /* There is either a set of nexthops or a special destination (RTD_*) */ + union { + struct nexthop nh; + uint dest; + }; +}; + +#define NEXTHOP_DEST_SIZE (OFFSETOF(struct nexthop_adata, dest) + sizeof(uint) - OFFSETOF(struct adata, data)) +#define NEXTHOP_DEST_LITERAL(x) ((struct nexthop_adata) { \ + .ad.length = NEXTHOP_DEST_SIZE, .dest = (x), }) + +#define RNF_ONLINK 0x1 /* Gateway is onlink regardless of IP ranges */ + + +typedef struct rta { + struct rta *next, **pprev; /* Hash chain */ + u32 uc; /* Use count */ + u32 hash_key; /* Hash over important fields */ + struct ea_list *eattrs; /* Extended Attribute chain */ + u16 cached:1; /* Are attributes cached? */ +} rta; + +#define RTS_STATIC 1 /* Normal static route */ +#define RTS_INHERIT 2 /* Route inherited from kernel */ +#define RTS_DEVICE 3 /* Device route */ +#define RTS_STATIC_DEVICE 4 /* Static device route */ +#define RTS_REDIRECT 5 /* Learned via redirect */ +#define RTS_RIP 6 /* RIP route */ +#define RTS_OSPF 7 /* OSPF route */ +#define RTS_OSPF_IA 8 /* OSPF inter-area route */ +#define RTS_OSPF_EXT1 9 /* OSPF external route type 1 */ +#define RTS_OSPF_EXT2 10 /* OSPF external route type 2 */ +#define RTS_BGP 11 /* BGP route */ +#define RTS_PIPE 12 /* Inter-table wormhole */ +#define RTS_BABEL 13 /* Babel route */ +#define RTS_RPKI 14 /* Route Origin Authorization */ +#define RTS_PERF 15 /* Perf checker */ +#define RTS_MAX 16 + +#define RTD_NONE 0 /* Undefined next hop */ +#define RTD_UNICAST 1 /* A standard next hop */ +#define RTD_BLACKHOLE 2 /* Silently drop packets */ +#define RTD_UNREACHABLE 3 /* Reject as unreachable */ +#define RTD_PROHIBIT 4 /* Administratively prohibited */ +#define RTD_MAX 5 + +extern const char * rta_dest_names[RTD_MAX]; + +static inline const char *rta_dest_name(uint n) +{ return (n < RTD_MAX) ? rta_dest_names[n] : "???"; } + + +/* + * Extended Route Attributes + */ + +typedef struct eattr { + word id; /* EA_CODE(PROTOCOL_..., protocol-dependent ID) */ + byte flags; /* Protocol-dependent flags */ + byte type; /* Attribute type */ + byte rfu:5; + byte originated:1; /* The attribute has originated locally */ + byte fresh:1; /* An uncached attribute (e.g. modified in export filter) */ + byte undef:1; /* Explicitly undefined */ + + PADDING(unused, 3, 3); + + union bval u; +} eattr; + + +#define EA_CODE_MASK 0xffff +#define EA_ALLOW_UNDEF 0x10000 /* ea_find: allow EAF_TYPE_UNDEF */ +#define EA_BIT(n) ((n) << 24) /* Used in bitfield accessors */ +#define EA_BIT_GET(ea) ((ea) >> 24) + +typedef struct ea_list { + struct ea_list *next; /* In case we have an override list */ + byte flags; /* Flags: EALF_... */ + byte rfu; + word count; /* Number of attributes */ + eattr attrs[0]; /* Attribute definitions themselves */ +} ea_list; + +#define EALF_SORTED 1 /* Attributes are sorted by code */ +#define EALF_BISECT 2 /* Use interval bisection for searching */ +#define EALF_CACHED 4 /* Attributes belonging to cached rta */ + +struct ea_class { +#define EA_CLASS_INSIDE \ + const char *name; /* Name (both print and filter) */ \ + struct symbol *sym; /* Symbol to export to configs */ \ + uint id; /* Autoassigned attribute ID */ \ + uint uc; /* Reference count */ \ + btype type; /* Data type ID */ \ + uint readonly:1; /* This attribute can't be changed by filters */ \ + uint conf:1; /* Requested by config */ \ + void (*format)(const eattr *ea, byte *buf, uint size); \ + void (*stored)(const eattr *ea); /* When stored into global hash */ \ + void (*freed)(const eattr *ea); /* When released from global hash */ \ + + EA_CLASS_INSIDE; +}; + +struct ea_class_ref { + resource r; + struct ea_class *class; +}; + +void ea_register_init(struct ea_class *); +struct ea_class_ref *ea_register_alloc(pool *, struct ea_class); + +#define EA_REGISTER_ALL_HELPER(x) ea_register_init(x); +#define EA_REGISTER_ALL(...) MACRO_FOREACH(EA_REGISTER_ALL_HELPER, __VA_ARGS__) + +struct ea_class *ea_class_find_by_id(uint id); +struct ea_class *ea_class_find_by_name(const char *name); +static inline struct ea_class *ea_class_self(struct ea_class *self) { return self; } +#define ea_class_find(_arg) _Generic((_arg), \ + uint: ea_class_find_by_id, \ + word: ea_class_find_by_id, \ + char *: ea_class_find_by_name, \ + const char *: ea_class_find_by_name, \ + struct ea_class *: ea_class_self)(_arg) + +struct ea_walk_state { + ea_list *eattrs; /* Ccurrent ea_list, initially set by caller */ + eattr *ea; /* Current eattr, initially NULL */ + u32 visited[4]; /* Bitfield, limiting max to 128 */ +}; + +#define ea_find(_l, _arg) _Generic((_arg), uint: ea_find_by_id, struct ea_class *: ea_find_by_class, char *: ea_find_by_name)(_l, _arg) +eattr *ea_find_by_id(ea_list *, unsigned ea); +static inline eattr *ea_find_by_class(ea_list *l, const struct ea_class *def) +{ return ea_find_by_id(l, def->id); } +static inline eattr *ea_find_by_name(ea_list *l, const char *name) +{ + const struct ea_class *def = ea_class_find_by_name(name); + return def ? ea_find_by_class(l, def) : NULL; +} + +#define ea_get_int(_l, _ident, _def) ({ \ + struct ea_class *cls = ea_class_find((_ident)); \ + ASSERT_DIE(cls->type & EAF_EMBEDDED); \ + const eattr *ea = ea_find((_l), cls->id); \ + (ea ? ea->u.data : (_def)); \ + }) + +#define ea_get_ip(_l, _ident, _def) ({ \ + struct ea_class *cls = ea_class_find((_ident)); \ + ASSERT_DIE(cls->type == T_IP); \ + const eattr *ea = ea_find((_l), cls->id); \ + (ea ? *((const ip_addr *) ea->u.ptr->data) : (_def)); \ + }) + +eattr *ea_walk(struct ea_walk_state *s, uint id, uint max); +void ea_dump(ea_list *); +int ea_same(ea_list *x, ea_list *y); /* Test whether two ea_lists are identical */ +uint ea_hash(ea_list *e); /* Calculate 16-bit hash value */ +ea_list *ea_append(ea_list *to, ea_list *what); +void ea_format_bitfield(const struct eattr *a, byte *buf, int bufsize, const char **names, int min, int max); + +/* Normalize ea_list; allocates the result from tmp_linpool */ +ea_list *ea_normalize(const ea_list *e); + +uint ea_list_size(ea_list *); +void ea_list_copy(ea_list *dest, ea_list *src, uint size); + +#define EA_LOCAL_LIST(N) struct { ea_list l; eattr a[N]; } + +#define EA_LITERAL_EMBEDDED(_class, _flags, _val) ({ \ + btype _type = (_class)->type; \ + ASSERT_DIE(_type & EAF_EMBEDDED); \ + EA_LITERAL_GENERIC((_class)->id, _type, _flags, .u.i = _val); \ + }) + +#define EA_LITERAL_STORE_ADATA(_class, _flags, _buf, _len) ({ \ + btype _type = (_class)->type; \ + ASSERT_DIE(!(_type & EAF_EMBEDDED)); \ + EA_LITERAL_GENERIC((_class)->id, _type, _flags, .u.ad = tmp_store_adata((_buf), (_len))); \ + }) + +#define EA_LITERAL_DIRECT_ADATA(_class, _flags, _adata) ({ \ + btype _type = (_class)->type; \ + ASSERT_DIE(!(_type & EAF_EMBEDDED)); \ + EA_LITERAL_GENERIC((_class)->id, _type, _flags, .u.ad = _adata); \ + }) + +#define EA_LITERAL_GENERIC(_id, _type, _flags, ...) \ + ((eattr) { .id = _id, .type = _type, .flags = _flags, __VA_ARGS__ }) + +static inline eattr * +ea_set_attr(ea_list **to, eattr a) +{ + EA_LOCAL_LIST(1) *ea = tmp_alloc(sizeof(*ea)); + *ea = (typeof(*ea)) { + .l.flags = EALF_SORTED, + .l.count = 1, + .l.next = *to, + .a[0] = a, + }; + + *to = &ea->l; + return &ea->a[0]; +} + +static inline void +ea_unset_attr(ea_list **to, _Bool local, const struct ea_class *def) +{ + ea_set_attr(to, EA_LITERAL_GENERIC(def->id, 0, 0, + .fresh = local, .originated = local, .undef = 1)); +} + +static inline void +ea_set_attr_u32(ea_list **to, const struct ea_class *def, uint flags, u64 data) +{ ea_set_attr(to, EA_LITERAL_EMBEDDED(def, flags, data)); } + +static inline void +ea_set_attr_data(ea_list **to, const struct ea_class *def, uint flags, const void *data, uint len) +{ ea_set_attr(to, EA_LITERAL_STORE_ADATA(def, flags, data, len)); } + +static inline void +ea_copy_attr(ea_list **to, ea_list *from, const struct ea_class *def) +{ + eattr *e = ea_find_by_class(from, def); + if (e) + if (e->type & EAF_EMBEDDED) + ea_set_attr_u32(to, def, e->flags, e->u.data); + else + ea_set_attr_data(to, def, e->flags, e->u.ptr->data, e->u.ptr->length); + else + ea_unset_attr(to, 0, def); +} + +/* + * Common route attributes + */ + +/* Preference: first-order comparison */ +extern struct ea_class ea_gen_preference; +static inline u32 rt_get_preference(rte *rt) +{ return ea_get_int(rt->attrs->eattrs, &ea_gen_preference, 0); } + +/* IGP metric: second-order comparison */ +extern struct ea_class ea_gen_igp_metric; +u32 rt_get_igp_metric(const rte *rt); +#define IGP_METRIC_UNKNOWN 0x80000000 /* Default igp_metric used when no other + protocol-specific metric is availabe */ + +/* From: Advertising router */ +extern struct ea_class ea_gen_from; + +/* Source: An old method to devise the route source protocol and kind. + * To be superseded in a near future by something more informative. */ +extern struct ea_class ea_gen_source; +static inline u32 rt_get_source_attr(const rte *rt) +{ return ea_get_int(rt->attrs->eattrs, &ea_gen_source, 0); } + +/* Flowspec validation result */ +enum flowspec_valid { + FLOWSPEC_UNKNOWN = 0, + FLOWSPEC_VALID = 1, + FLOWSPEC_INVALID = 2, + FLOWSPEC__MAX, +}; + +extern const char * flowspec_valid_names[FLOWSPEC__MAX]; +static inline const char *flowspec_valid_name(enum flowspec_valid v) +{ return (v < FLOWSPEC__MAX) ? flowspec_valid_names[v] : "???"; } + +extern struct ea_class ea_gen_flowspec_valid; +static inline enum flowspec_valid rt_get_flowspec_valid(rte *rt) +{ return ea_get_int(rt->attrs->eattrs, &ea_gen_flowspec_valid, FLOWSPEC_UNKNOWN); } + +/* Next hop: For now, stored as adata */ +extern struct ea_class ea_gen_nexthop; + +static inline void ea_set_dest(struct ea_list **to, uint flags, uint dest) +{ + struct nexthop_adata nhad = NEXTHOP_DEST_LITERAL(dest); + ea_set_attr_data(to, &ea_gen_nexthop, flags, &nhad.ad.data, nhad.ad.length); +} + +/* Next hop structures */ + +#define NEXTHOP_ALIGNMENT (_Alignof(struct nexthop)) +#define NEXTHOP_MAX_SIZE (sizeof(struct nexthop) + sizeof(u32)*MPLS_MAX_LABEL_STACK) +#define NEXTHOP_SIZE(_nh) NEXTHOP_SIZE_CNT(((_nh)->labels)) +#define NEXTHOP_SIZE_CNT(cnt) BIRD_ALIGN((sizeof(struct nexthop) + sizeof(u32) * (cnt)), NEXTHOP_ALIGNMENT) +#define nexthop_size(nh) NEXTHOP_SIZE((nh)) + +#define NEXTHOP_NEXT(_nh) ((void *) (_nh) + NEXTHOP_SIZE(_nh)) +#define NEXTHOP_END(_nhad) ((_nhad)->ad.data + (_nhad)->ad.length) +#define NEXTHOP_VALID(_nh, _nhad) ((void *) (_nh) < (void *) NEXTHOP_END(_nhad)) +#define NEXTHOP_ONE(_nhad) (NEXTHOP_NEXT(&(_nhad)->nh) == NEXTHOP_END(_nhad)) + +#define NEXTHOP_WALK(_iter, _nhad) for ( \ + struct nexthop *_iter = &(_nhad)->nh; \ + (void *) _iter < (void *) NEXTHOP_END(_nhad); \ + _iter = NEXTHOP_NEXT(_iter)) + + +static inline int nexthop_same(struct nexthop_adata *x, struct nexthop_adata *y) +{ return adata_same(&x->ad, &y->ad); } +struct nexthop_adata *nexthop_merge(struct nexthop_adata *x, struct nexthop_adata *y, int max, linpool *lp); +struct nexthop_adata *nexthop_sort(struct nexthop_adata *x, linpool *lp); +int nexthop_is_sorted(struct nexthop_adata *x); + +#define NEXTHOP_IS_REACHABLE(nhad) ((nhad)->ad.length > NEXTHOP_DEST_SIZE) + +/* Route has regular, reachable nexthop (i.e. not RTD_UNREACHABLE and like) */ +static inline int rte_is_reachable(rte *r) +{ + eattr *nhea = ea_find(r->attrs->eattrs, &ea_gen_nexthop); + if (!nhea) + return 0; + + struct nexthop_adata *nhad = (void *) nhea->u.ptr; + return NEXTHOP_IS_REACHABLE(nhad); +} + +static inline int nhea_dest(eattr *nhea) +{ + if (!nhea) + return RTD_NONE; + + struct nexthop_adata *nhad = nhea ? (struct nexthop_adata *) nhea->u.ptr : NULL; + if (NEXTHOP_IS_REACHABLE(nhad)) + return RTD_UNICAST; + else + return nhad->dest; +} + +static inline int rte_dest(const rte *r) +{ + return nhea_dest(ea_find(r->attrs->eattrs, &ea_gen_nexthop)); +} + +void rta_init(void); +#define rta_size(...) (sizeof(rta)) +#define RTA_MAX_SIZE (sizeof(rta)) +rta *rta_lookup(rta *); /* Get rta equivalent to this one, uc++ */ +static inline int rta_is_cached(rta *r) { return r->cached; } +static inline rta *rta_clone(rta *r) { r->uc++; return r; } +void rta__free(rta *r); +static inline void rta_free(rta *r) { if (r && !--r->uc) rta__free(r); } +rta *rta_do_cow(rta *o, linpool *lp); +static inline rta * rta_cow(rta *r, linpool *lp) { return rta_is_cached(r) ? rta_do_cow(r, lp) : r; } +void rta_dump(rta *); +void rta_dump_all(void); +void rta_show(struct cli *, rta *); + +#endif @@ -32,6 +32,7 @@ #include "nest/bird.h" #include "lib/resource.h" #include "lib/string.h" +#include "lib/tlists.h" #undef FAKE_SLAB /* Turn on if you want to debug memory allocations */ @@ -42,7 +43,7 @@ static void slab_free(resource *r); static void slab_dump(resource *r); static resource *slab_lookup(resource *r, unsigned long addr); -static size_t slab_memsize(resource *r); +static struct resmem slab_memsize(resource *r); #ifdef FAKE_SLAB @@ -98,7 +99,7 @@ sl_allocz(slab *s) } void -sl_free(slab *s, void *oo) +sl_free(void *oo) { struct sl_obj *o = SKIP_BACK(struct sl_obj, data, oo); @@ -128,7 +129,7 @@ slab_dump(resource *r) debug("(%d objects per %d bytes)\n", cnt, s->size); } -static size_t +static struct resmem slab_memsize(resource *r) { slab *s = (slab *) r; @@ -138,7 +139,10 @@ slab_memsize(resource *r) WALK_LIST(o, s->objs) cnt++; - return ALLOC_OVERHEAD + sizeof(struct slab) + cnt * (ALLOC_OVERHEAD + s->size); + return (struct resmem) { + .effective = cnt * s->size, + .overhead = ALLOC_OVERHEAD + sizeof(struct slab) + cnt * ALLOC_OVERHEAD, + }; } @@ -150,12 +154,38 @@ slab_memsize(resource *r) #define MAX_EMPTY_HEADS 1 +enum sl_head_state { + slh_empty = 2, + slh_partial = 0, + slh_full = 1, +} PACKED; + +struct sl_head { + struct slab *slab; + TLIST_NODE(sl_head, struct sl_head) n; + u16 num_full; + enum sl_head_state state; + u32 used_bits[0]; +}; + +struct sl_alignment { /* Magic structure for testing of alignment */ + byte data; + int x[0]; +}; + +#define TLIST_PREFIX sl_head +#define TLIST_TYPE struct sl_head +#define TLIST_ITEM n +#define TLIST_WANT_WALK +#define TLIST_WANT_ADD_HEAD + +#include "lib/tlists.h" + struct slab { resource r; - pool *p; uint obj_size, head_size, head_bitfield_len; uint objs_per_slab, num_empty_heads, data_size; - list empty_heads, partial_heads, full_heads; + struct sl_head_list empty_heads, partial_heads, full_heads; }; static struct resclass sl_class = { @@ -167,18 +197,15 @@ static struct resclass sl_class = { slab_memsize }; -struct sl_head { - node n; - u32 num_full; - u32 used_bits[0]; -}; +#define SL_GET_HEAD(x) ((struct sl_head *) (((uintptr_t) (x)) & ~(page_size-1))) -struct sl_alignment { /* Magic structure for testing of alignment */ - byte data; - int x[0]; -}; +#define SL_HEAD_CHANGE_STATE(_s, _h, _from, _to) ({ \ + ASSERT_DIE(_h->state == slh_##_from); \ + sl_head_rem_node(&_s->_from##_heads, _h); \ + sl_head_add_head(&_s->_to##_heads, _h); \ + _h->state = slh_##_to; \ + }) -#define SL_GET_HEAD(x) ((struct sl_head *) PAGE_HEAD(x)) /** * sl_new - create a new Slab @@ -192,10 +219,9 @@ slab * sl_new(pool *p, uint size) { slab *s = ralloc(p, &sl_class); - s->p = p; uint align = sizeof(struct sl_alignment); - if (align < sizeof(int)) - align = sizeof(int); + if (align < sizeof(void *)) + align = sizeof(void *); s->data_size = size; size = (size + align - 1) / align * align; s->obj_size = size; @@ -216,9 +242,6 @@ sl_new(pool *p, uint size) bug("Slab: object too large"); s->num_empty_heads = 0; - init_list(&s->empty_heads); - init_list(&s->partial_heads); - init_list(&s->full_heads); return s; } @@ -235,8 +258,7 @@ sl_alloc(slab *s) struct sl_head *h; redo: - h = HEAD(s->partial_heads); - if (!h->n.next) + if (!(h = s->partial_heads.first)) goto no_partial; okay: for (uint i=0; i<s->head_bitfield_len; i++) @@ -256,26 +278,27 @@ okay: return out; } - rem_node(&h->n); - add_tail(&s->full_heads, &h->n); + SL_HEAD_CHANGE_STATE(s, h, partial, full); goto redo; no_partial: - h = HEAD(s->empty_heads); - if (h->n.next) + if (h = s->empty_heads.first) { - rem_node(&h->n); - add_head(&s->partial_heads, &h->n); + SL_HEAD_CHANGE_STATE(s, h, empty, partial); s->num_empty_heads--; goto okay; } - h = alloc_page(s->p); + + h = alloc_page(); + ASSERT_DIE(SL_GET_HEAD(h) == h); + #ifdef POISON memset(h, 0xba, page_size); #endif - ASSERT_DIE(SL_GET_HEAD(h) == h); + memset(h, 0, s->head_size); - add_head(&s->partial_heads, &h->n); + h->slab = s; + sl_head_add_head(&s->partial_heads, h); goto okay; } @@ -304,9 +327,10 @@ sl_allocz(slab *s) * and returns it back to the Slab @s. */ void -sl_free(slab *s, void *oo) +sl_free(void *oo) { struct sl_head *h = SL_GET_HEAD(oo); + struct slab *s = h->slab; #ifdef POISON memset(oo, 0xdb, s->data_size); @@ -319,24 +343,22 @@ sl_free(slab *s, void *oo) h->used_bits[pos / 32] &= ~(1 << (pos % 32)); - if (h->num_full-- == s->objs_per_slab) - { - rem_node(&h->n); - add_head(&s->partial_heads, &h->n); - } + if ((h->num_full-- == s->objs_per_slab) && (h->state == slh_full)) + SL_HEAD_CHANGE_STATE(s, h, full, partial); else if (!h->num_full) { - rem_node(&h->n); + sl_head_rem_node(&s->partial_heads, h); if (s->num_empty_heads >= MAX_EMPTY_HEADS) { #ifdef POISON memset(h, 0xde, page_size); #endif - free_page(s->p, h); + free_page(h); } else { - add_head(&s->empty_heads, &h->n); + sl_head_add_head(&s->empty_heads, h); + h->state = slh_empty; s->num_empty_heads++; } } @@ -346,14 +368,13 @@ static void slab_free(resource *r) { slab *s = (slab *) r; - struct sl_head *h, *g; - - WALK_LIST_DELSAFE(h, g, s->empty_heads) - free_page(s->p, h); - WALK_LIST_DELSAFE(h, g, s->partial_heads) - free_page(s->p, h); - WALK_LIST_DELSAFE(h, g, s->full_heads) - free_page(s->p, h); + + WALK_TLIST_DELSAFE(sl_head, h, &s->empty_heads) + free_page(h); + WALK_TLIST_DELSAFE(sl_head, h, &s->partial_heads) + free_page(h); + WALK_TLIST_DELSAFE(sl_head, h, &s->full_heads) + free_page(h); } static void @@ -361,45 +382,53 @@ slab_dump(resource *r) { slab *s = (slab *) r; int ec=0, pc=0, fc=0; - struct sl_head *h; - WALK_LIST(h, s->empty_heads) + WALK_TLIST(sl_head, h, &s->empty_heads) ec++; - WALK_LIST(h, s->partial_heads) + WALK_TLIST(sl_head, h, &s->partial_heads) pc++; - WALK_LIST(h, s->full_heads) + WALK_TLIST(sl_head, h, &s->full_heads) fc++; debug("(%de+%dp+%df blocks per %d objs per %d bytes)\n", ec, pc, fc, s->objs_per_slab, s->obj_size); } -static size_t +static struct resmem slab_memsize(resource *r) { slab *s = (slab *) r; size_t heads = 0; - struct sl_head *h; - WALK_LIST(h, s->empty_heads) + WALK_TLIST(sl_head, h, &s->full_heads) heads++; - WALK_LIST(h, s->partial_heads) + + size_t items = heads * s->objs_per_slab; + + WALK_TLIST(sl_head, h, &s->partial_heads) + { heads++; - WALK_LIST(h, s->full_heads) + items += h->num_full; + } + + WALK_TLIST(sl_head, h, &s->empty_heads) heads++; -// return ALLOC_OVERHEAD + sizeof(struct slab) + heads * (ALLOC_OVERHEAD + page_size); - return ALLOC_OVERHEAD + sizeof(struct slab); /* The page sizes are accounted for in the pool */ + size_t eff = items * s->data_size; + + return (struct resmem) { + .effective = eff, + .overhead = ALLOC_OVERHEAD + sizeof(struct slab) + heads * page_size - eff, + }; } static resource * slab_lookup(resource *r, unsigned long a) { slab *s = (slab *) r; - struct sl_head *h; - WALK_LIST(h, s->partial_heads) + WALK_TLIST(sl_head, h, &s->partial_heads) if ((unsigned long) h < a && (unsigned long) h + page_size < a) return r; - WALK_LIST(h, s->full_heads) + WALK_TLIST(sl_head, h, &s->full_heads) if ((unsigned long) h < a && (unsigned long) h + page_size < a) return r; return NULL; diff --git a/lib/slab_test.c b/lib/slab_test.c new file mode 100644 index 00000000..803d0215 --- /dev/null +++ b/lib/slab_test.c @@ -0,0 +1,171 @@ +/* + * BIRD Library -- Slab Alloc / Dealloc Tests + * + * (c) 2022 Maria Matejka <mq@jmq.cz> + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#include "test/birdtest.h" +#include "lib/resource.h" +#include "lib/bitops.h" + +static const int sizes[] = { + 8, 12, 18, 27, 41, 75, 131, 269, +}; + +#define TEST_SIZE 1024 * 128 +#define ITEMS(sz) TEST_SIZE / ( (sz) >> u32_log2((sz))/2 ) + +struct test_request { + int size; + enum strategy { + TEST_NONE, + TEST_FORWARDS, + TEST_BACKWARDS, + TEST_RANDOM, + TEST_MIXED, + TEST__MAX, + } strategy; +}; + +const char * const strategy_name[TEST__MAX] = { + [TEST_FORWARDS] = "forwards", + [TEST_BACKWARDS] = "backwards", + [TEST_RANDOM] = "random", + [TEST_MIXED] = "mixed", +}; + +static inline byte *test_alloc(slab *s, int sz, struct resmem *sliz) +{ + byte *out = sl_alloc(s); + + for (int p=0; p < sz; p++) + out[p] = p & 0xff; + + struct resmem ns = rmemsize((resource *) s); + + bt_assert(sliz->effective + sz == ns.effective); + bt_assert((sliz->overhead - sz - ns.overhead) % page_size == 0); + + *sliz = ns; + + return out; +} + +static inline void test_free(slab *s, byte *block, int sz, struct resmem *sliz) +{ + for (int p=0; p < sz; p++) + { + bt_assert(block[p] == (p & 0xff)); + block[p]++; + } + + sl_free(block); + + struct resmem ns = rmemsize((resource *) s); + + bt_assert(sliz->effective - sz == ns.effective); + bt_assert((sliz->overhead + sz - ns.overhead) % page_size == 0); + + *sliz = ns; +} + +static inline struct resmem get_memsize(slab *s) +{ + struct resmem sz = rmemsize((resource *) s); + bt_assert(sz.effective == 0); + return sz; +} + +static int +t_slab(const void *data) +{ + const struct test_request *tr = data; + int sz = tr->size; + + slab *s = sl_new(&root_pool, sz); + struct resmem sliz = get_memsize(s); + + int n = ITEMS(sz); + byte **block = mb_alloc(&root_pool, n * sizeof(*block)); + + switch (tr->strategy) { + case TEST_FORWARDS: + for (int i = 0; i < n; i++) + block[i] = test_alloc(s, sz, &sliz); + + for (int i = 0; i < n; i++) + test_free(s, block[i], sz, &sliz); + + break; + + case TEST_BACKWARDS: + for (int i = 0; i < n; i++) + block[i] = test_alloc(s, sz, &sliz); + + for (int i = n - 1; i >= 0; i--) + test_free(s, block[i], sz, &sliz); + + break; + + case TEST_RANDOM: + for (int i = 0; i < n; i++) + block[i] = test_alloc(s, sz, &sliz); + + for (int i = 0; i < n; i++) + { + int pos = bt_random() % (n - i); + test_free(s, block[pos], sz, &sliz); + if (pos != n - i - 1) + block[pos] = block[n - i - 1]; + } + + break; + + case TEST_MIXED: + { + int cur = 0; + int pending = n; + + while (cur + pending > 0) { + int action = bt_random() % (cur + pending); + + if (action < cur) { + test_free(s, block[action], sz, &sliz); + if (action != --cur) + block[action] = block[cur]; + } else { + block[cur++] = test_alloc(s, sz, &sliz); + pending--; + } + } + + break; + } + + default: bug("This shouldn't happen"); + } + + mb_free(block); + return 1; +} +int main(int argc, char *argv[]) +{ + bt_init(argc, argv); + + struct test_request tr; + + for (uint i = 0; i < sizeof(sizes) / sizeof(*sizes); i++) + for (uint strategy = TEST_FORWARDS; strategy < TEST__MAX; strategy++) + { + tr = (struct test_request) { + .size = sizes[i], + .strategy = strategy, + }; + bt_test_suite_arg(t_slab, &tr, "Slab allocator test, size=%d, strategy=%s", + tr.size, strategy_name[strategy]); + } + + return bt_exit_value(); +} diff --git a/lib/socket.h b/lib/socket.h index 96fedeeb..0b6ac589 100644 --- a/lib/socket.h +++ b/lib/socket.h @@ -123,6 +123,7 @@ extern int sk_priority_control; /* Suggested priority for control traffic, shou #define SKF_TTL_RX 0x08 /* Report TTL / Hop Limit for RX packets */ #define SKF_BIND 0x10 /* Bind datagram socket to given source address */ #define SKF_HIGH_PORT 0x20 /* Choose port from high range if possible */ +#define SKF_FREEBIND 0x40 /* Allow socket to bind to a nonlocal address */ #define SKF_THREAD 0x100 /* Socked used in thread, Do not add to main loop */ #define SKF_TRUNCATED 0x200 /* Received packet was truncated, set by IO layer */ diff --git a/lib/string.h b/lib/string.h index 976b1c24..2829943d 100644 --- a/lib/string.h +++ b/lib/string.h @@ -20,6 +20,11 @@ int bvsprintf(char *str, const char *fmt, va_list args); int bsnprintf(char *str, int size, const char *fmt, ...); int bvsnprintf(char *str, int size, const char *fmt, va_list args); +char *mb_sprintf(pool *p, const char *fmt, ...); +char *mb_vsprintf(pool *p, const char *fmt, va_list args); +char *lp_sprintf(linpool *p, const char *fmt, ...); +char *lp_vsprintf(linpool *p, const char *fmt, va_list args); + int buffer_vprint(buffer *buf, const char *fmt, va_list args); int buffer_print(buffer *buf, const char *fmt, ...); void buffer_puts(buffer *buf, const char *str); diff --git a/lib/timer.c b/lib/timer.c index 381163d0..c47e0bbc 100644 --- a/lib/timer.c +++ b/lib/timer.c @@ -233,6 +233,7 @@ timers_fire(struct timeloop *loop) io_log_event(t->hook, t->data); t->hook(t); + tmp_flush(); } } diff --git a/lib/tlists.h b/lib/tlists.h new file mode 100644 index 00000000..e1ed79ea --- /dev/null +++ b/lib/tlists.h @@ -0,0 +1,172 @@ +/* + * BIRD Library -- Typed Linked Lists + * + * (c) 2022 Maria Matejka <mq@jmq.cz> + * + * Can be freely distributed and used under the terms of the GNU GPL. + * + * + * This implementation of linked lists forces its members to be + * typed. On the other hand, it needs to be implemented as ugly macros to + * keep the needed genericity. + * + * Usage: + * 1. Include this file + * 2. Define the node structure + * 3. For every list type you need to define: + * A. #define TLIST_PREFIX and other macros + * B. Include this file once again + * + * Macros to define: + * TLIST_PREFIX: prefix to prepend to everything generated + * TLIST_TYPE: the actual node type + * TLIST_ITEM: where the tlist structure is + * TLIST_WANT_WALK: if defined, generates a helper functions for list walking macros + * TLIST_WANT_ADD_HEAD: if defined, TLIST_PREFIX_add_head() is generated to + * add an item to the beginning of the list + * TLIST_WANT_ADD_TAIL: if defined, TLIST_PREFIX_add_tail() is generated to + * add an item to the end of the list + * + * TLIST_PREFIX_rem_node() is generated always. + * + * All these macros are #undef-ed by including this file. + * + * Example: + * + * #include "lib/tlists.h" + * + * struct foo { + * ... + * TLIST_NODE(bar, struct foo) baz; + * ... + * }; + * + * #define TLIST_PREFIX bar + * #define TLIST_TYPE struct foo + * #define TLIST_ITEM baz + * + * #define TLIST_WANT_WALK + * #define TLIST_WANT_ADD_HEAD + * + * #include "lib/tlists.h" + * + * ... + * (end of example) + * + */ + +#ifdef _BIRD_LIB_TLISTS_H_ +# ifdef TLIST_PREFIX + +/* Check for mandatory arguments */ +#ifndef TLIST_TYPE +#error "TLIST_TYPE must be defined" +#endif +#ifndef TLIST_ITEM +#error "TLIST_ITEM must be defined" +#endif +#ifndef TLIST_PREFIX +#error "TLIST_PREFIX must be defined" +#endif + +#define TLIST_NAME(x) MACRO_CONCAT_AFTER(TLIST_PREFIX,_##x) +#ifndef TLIST_LIST_STRUCT +#define TLIST_LIST_STRUCT TLIST_NAME(list) +#endif + +typedef struct TLIST_LIST_STRUCT { + TLIST_TYPE *first; + TLIST_TYPE *last; +} TLIST_LIST_STRUCT; + +#ifdef TLIST_WANT_WALK +static inline struct TLIST_NAME(node) * TLIST_NAME(node_get)(TLIST_TYPE *node) +{ return &(node->TLIST_ITEM); } +#endif + +#ifdef TLIST_WANT_ADD_HEAD +static inline void TLIST_NAME(add_head)(TLIST_LIST_STRUCT *list, TLIST_TYPE *node) +{ + ASSERT_DIE(!node->TLIST_ITEM.prev && !node->TLIST_ITEM.next); + if (node->TLIST_ITEM.next = list->first) + list->first->TLIST_ITEM.prev = node; + else + list->last = node; + list->first = node; +} +#endif + +#ifdef TLIST_WANT_ADD_TAIL +static inline void TLIST_NAME(add_tail)(TLIST_LIST_STRUCT *list, TLIST_TYPE *node) +{ + ASSERT_DIE(!node->TLIST_ITEM.prev && !node->TLIST_ITEM.next); + if (node->TLIST_ITEM.prev = list->last) + list->last->TLIST_ITEM.next = node; + else + list->first = node; + list->last = node; +} +#endif + +static inline void TLIST_NAME(rem_node)(TLIST_LIST_STRUCT *list, TLIST_TYPE *node) +{ + if (node->TLIST_ITEM.prev) + node->TLIST_ITEM.prev->TLIST_ITEM.next = node->TLIST_ITEM.next; + else + { + ASSERT_DIE(list->first == node); + list->first = node->TLIST_ITEM.next; + } + + if (node->TLIST_ITEM.next) + node->TLIST_ITEM.next->TLIST_ITEM.prev = node->TLIST_ITEM.prev; + else + { + ASSERT_DIE(list->last == node); + list->last = node->TLIST_ITEM.prev; + } + + node->TLIST_ITEM.next = node->TLIST_ITEM.prev = NULL; +} + +#undef TLIST_PREFIX +#undef TLIST_NAME +#undef TLIST_LIST_STRUCT +#undef TLIST_TYPE +#undef TLIST_ITEM +#undef TLIST_WANT_ADD_HEAD +#undef TLIST_WANT_ADD_TAIL + +# endif +#else +#define _BIRD_LIB_TLISTS_H_ + +#include "lib/macro.h" + +#if defined(TLIST_NAME) || defined(TLIST_PREFIX) +#error "You should first include lib/tlists.h without requesting a TLIST" +#endif + +#define TLIST_NODE(_name, _type) struct _name##_node { _type *next; _type *prev; } +#define TLIST_LIST(_name) struct _name##_list + +/* Use ->first and ->last to access HEAD and TAIL */ +#define THEAD(_name, _list) (_list)->first +#define TTAIL(_name, _list) (_list)->last + +/* Walkaround macros: simple and resilient to node removal */ +#define WALK_TLIST(_name, _node, _list) \ + for (typeof((_list)->first) _node = (_list)->first; \ + _node; _node = _name##_node_get((_node))->next) + +#define WALK_TLIST_DELSAFE(_name, _node, _list) \ + for (typeof((_list)->first) _node = (_list)->first, \ + _helper = _node ? _name##_node_get((_list)->first)->next : NULL; \ + _node; \ + (_node = _helper) ? (_helper = _name##_node_get(_helper)->next) : 0) + +/* Empty check */ +#define EMPTY_TLIST(_name, _list) (!(_list)->first) + +#endif + diff --git a/lib/type.h b/lib/type.h new file mode 100644 index 00000000..b54744c1 --- /dev/null +++ b/lib/type.h @@ -0,0 +1,112 @@ +/* + * BIRD Internet Routing Daemon -- Internal Data Types + * + * (c) 2022 Maria Matejka <mq@jmq.cz> + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#ifndef _BIRD_TYPE_H_ +#define _BIRD_TYPE_H_ + +#include "lib/birdlib.h" +#include "lib/attrs.h" + +union bval { +#define BVAL_ITEMS \ + struct { \ + u32 data; /* Integer type inherited from eattrs */ \ + PADDING(data, 0, 4); /* Must be padded on 64-bits */ \ + }; \ + struct { \ + u32 i; /* Integer type inherited from filters */ \ + PADDING(i, 0, 4); /* Must be padded on 64-bits */ \ + }; \ + const struct adata *ptr; /* Generic attribute data inherited from eattrs */ \ + const struct adata *ad; /* Generic attribute data inherited from filters */ \ + + BVAL_ITEMS; +}; + +union bval_long { + union bval bval; /* For direct assignments */ + BVAL_ITEMS; /* For item-wise access */ + + u64 ec; + lcomm lc; + ip_addr ip; + const net_addr *net; + const char *s; + const struct f_tree *t; + const struct f_trie *ti; + const struct f_path_mask *path_mask; + struct f_path_mask_item pmi; +}; + + +/* Internal types */ +enum btype { +/* Nothing. Simply nothing. */ + T_VOID = 0, + +/* Something but inaccessible. */ + T_OPAQUE = 0x02, /* Opaque byte string (not filterable) */ + T_IFACE = 0x0c, /* Pointer to an interface (inside adata) */ + T_NEXTHOP_LIST = 0x2c, /* The whole nexthop block */ + T_HOSTENTRY = 0x2e, /* Hostentry with possible MPLS labels */ + +/* Types shared with eattrs */ + T_INT = 0x01, /* 32-bit unsigned integer number */ + T_IP = 0x04, /* IP address */ + T_QUAD = 0x05, /* Router ID (IPv4 address) */ + T_PATH = 0x06, /* BGP AS path (encoding per RFC 1771:4.3) */ + T_CLIST = 0x0a, /* Set of u32's (e.g., a community list) */ + T_ECLIST = 0x0e, /* Set of pairs of u32's - ext. community list */ + T_LCLIST = 0x08, /* Set of triplets of u32's - large community list */ + + T_ENUM_BGP_ORIGIN = 0x11, /* BGP Origin enum */ + T_ENUM_RA_PREFERENCE = 0x13, /* RA Preference enum */ + T_ENUM_FLOWSPEC_VALID = 0x15, /* Flowspec validation result */ + +#define EAF_TYPE__MAX 0x1f +#define EAF_EMBEDDED 0x01 /* Data stored in eattr.u.data (part of type spec) */ + /* Otherwise, attribute data is adata */ + +/* Other user visible types which fit in int */ + T_BOOL = 0xa0, + T_PAIR = 0xa4, /* Notice that pair is stored as integer: first << 16 | second */ + +/* Put enumerational types in 0x20..0x3f range */ + T_ENUM_LO = 0x10, + T_ENUM_HI = 0x3f, + + T_ENUM_RTS = 0x31, + T_ENUM_SCOPE = 0x33, + T_ENUM_RTD = 0x37, + T_ENUM_ROA = 0x39, + T_ENUM_NETTYPE = 0x3b, + T_ENUM_AF = 0x3d, + +/* new enums go here */ + +#define T_ENUM T_ENUM_LO ... T_ENUM_HI + +/* Bigger ones */ + T_NET = 0xb0, + T_STRING = 0xb4, + T_PATH_MASK = 0xb8, /* mask for BGP path */ + T_EC = 0xbc, /* Extended community value, u64 */ + T_LC = 0xc0, /* Large community value, lcomm */ + T_RD = 0xc4, /* Route distinguisher for VPN addresses */ + T_PATH_MASK_ITEM = 0xc8, /* Path mask item for path mask constructors */ + + T_SET = 0x80, + T_PREFIX_SET = 0x84, +} PACKED; + +typedef enum btype btype; + +STATIC_ASSERT(sizeof(btype) == sizeof(byte)); + + +#endif diff --git a/lib/type_test.c b/lib/type_test.c new file mode 100644 index 00000000..b526db69 --- /dev/null +++ b/lib/type_test.c @@ -0,0 +1,79 @@ +/* + * BIRD Library -- Data Type Alignment Tests + * + * (c) 2022 Maria Matejka <mq@jmq.cz> + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#include "test/birdtest.h" +#include "lib/type.h" +#include "lib/route.h" + +#define CHECK_ONE(val) \ + for (uint i=0; i<sizeof(val); i++) \ + bt_assert(((const u8 *) &val)[i] == (u8) ~0); + +#define SET_PADDING(val, name) \ + for (uint i=0; i<sizeof(val.PADDING_NAME(name)); i++) \ + val.PADDING_NAME(name)[i] = ~0; + + +static int +t_bval(void) +{ + union bval v; + + memset(&v, 0, sizeof(v)); + v.data = ~0; + SET_PADDING(v, data); + CHECK_ONE(v); + + memset(&v, 0, sizeof(v)); + v.i = ~0; + SET_PADDING(v, i); + CHECK_ONE(v); + + memset(&v, 0, sizeof(v)); + v.ptr = (void *) ~0; + CHECK_ONE(v); + + memset(&v, 0, sizeof(v)); + v.ad = (void *) ~0; + CHECK_ONE(v); + + return 1; +} + +static int +t_eattr(void) +{ + struct eattr e; + memset(&e, 0, sizeof(e)); + + e.id = ~0; + e.flags = ~0; + e.type = ~0; + e.rfu = ~0; + e.originated = ~0; + e.fresh = ~0; + e.undef = ~0; + memset(&e.u, ~0, sizeof(e.u)); /* Assumes t_bval passed */ + + SET_PADDING(e, unused); + + CHECK_ONE(e); + + return 1; +} + + +int main(int argc, char *argv[]) +{ + bt_init(argc, argv); + + bt_test_suite(t_bval, "Structure alignment test: bval"); + bt_test_suite(t_eattr, "Structure alignment test: eattr"); + + return bt_exit_value(); +} |