From 13225f1dbff54619476f2d8f6bc779dbb4983e3e Mon Sep 17 00:00:00 2001 From: "Ondrej Zajicek (work)" Date: Sun, 5 Apr 2020 03:24:46 +0200 Subject: Filter: Faster prefix sets Use 16-way (4bit) branching in prefix trie instead of basic binary branching. The change makes IPv4 prefix sets almost 3x faster, but with more memory consumption and much more complicated algorithm. Together with a previous filter change, it makes IPv4 prefix sets about ~4.3x faster and slightly smaller (on my test data). --- lib/birdlib.h | 3 +++ 1 file changed, 3 insertions(+) (limited to 'lib/birdlib.h') diff --git a/lib/birdlib.h b/lib/birdlib.h index 431b7c0d..81d4908a 100644 --- a/lib/birdlib.h +++ b/lib/birdlib.h @@ -32,6 +32,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)) -- cgit v1.2.3 From de86040b2cf4ec9bfbb64f0e208a19d4d7e51adc Mon Sep 17 00:00:00 2001 From: Maria Matejka Date: Sun, 10 Apr 2022 14:11:46 +0200 Subject: Attribute list normalization cleanup --- filter/f-inst.c | 8 ++----- lib/attrs.h | 10 +++++++++ lib/birdlib.h | 1 + lib/route.h | 18 +++++----------- nest/rt-attr.c | 64 +++++++++++++++++++++++++++++++++++++------------------ nest/rt-show.c | 2 +- proto/bgp/attrs.c | 47 +++++++++------------------------------- proto/mrt/mrt.c | 2 +- 8 files changed, 73 insertions(+), 79 deletions(-) (limited to 'lib/birdlib.h') diff --git a/filter/f-inst.c b/filter/f-inst.c index e0bad833..7b3db1c7 100644 --- a/filter/f-inst.c +++ b/filter/f-inst.c @@ -717,12 +717,8 @@ runtime( "Setting opaque attribute is not allowed" ); break; - case T_IP:; - int len = sizeof(ip_addr); - struct adata *ad = lp_alloc(fs->pool, sizeof(struct adata) + len); - ad->length = len; - (* (ip_addr *) ad->data) = v1.val.ip; - l->attrs[0].u.ptr = ad; + case T_IP: + l->attrs[0].u.ptr = lp_store_adata(fs->pool, &v1.val.ip, sizeof(ip_addr)); break; default: diff --git a/lib/attrs.h b/lib/attrs.h index 97a9630f..fcb70230 100644 --- a/lib/attrs.h +++ b/lib/attrs.h @@ -17,6 +17,8 @@ typedef struct adata { 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 * @@ -27,6 +29,14 @@ lp_alloc_adata(struct linpool *pool, uint 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; +} + 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)); } diff --git a/lib/birdlib.h b/lib/birdlib.h index 81d4908a..6f0bab96 100644 --- a/lib/birdlib.h +++ b/lib/birdlib.h @@ -19,6 +19,7 @@ struct align_probe { char x; long int y; }; #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 BIRD_CPU_ALIGN(s) BIRD_ALIGN((s), CPU_STRUCT_ALIGN) /* Utility macros */ diff --git a/lib/route.h b/lib/route.h index 8e60f749..eda5b9ad 100644 --- a/lib/route.h +++ b/lib/route.h @@ -204,24 +204,16 @@ ea_get_int(ea_list *e, unsigned id, u32 def) } void ea_dump(ea_list *); -void ea_sort(ea_list *); /* Sort entries in all sub-lists */ -unsigned ea_scan(ea_list *); /* How many bytes do we need for merged ea_list */ -void ea_merge(ea_list *from, ea_list *to); /* Merge sub-lists to allocated buffer */ 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); -#define ea_normalize(ea) do { \ - if (ea->next) { \ - ea_list *t = alloca(ea_scan(ea)); \ - ea_merge(ea, t); \ - ea = t; \ - } \ - ea_sort(ea); \ - if (ea->count == 0) \ - ea = NULL; \ -} while(0) \ +/* 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); struct ea_one_attr_list { ea_list l; diff --git a/nest/rt-attr.c b/nest/rt-attr.c index 2fa9b673..afa95eec 100644 --- a/nest/rt-attr.c +++ b/nest/rt-attr.c @@ -626,7 +626,7 @@ ea_do_prune(ea_list *e) * If an attribute occurs multiple times in a single &ea_list, * ea_sort() leaves only the first (the only significant) occurrence. */ -void +static void ea_sort(ea_list *e) { while (e) @@ -650,8 +650,8 @@ ea_sort(ea_list *e) * This function calculates an upper bound of the size of * a given &ea_list after merging with ea_merge(). */ -unsigned -ea_scan(ea_list *e) +static unsigned +ea_scan(const ea_list *e) { unsigned cnt = 0; @@ -677,8 +677,8 @@ ea_scan(ea_list *e) * segments with ea_merge() and finally sort and prune the result * by calling ea_sort(). */ -void -ea_merge(ea_list *e, ea_list *t) +static void +ea_merge(const ea_list *e, ea_list *t) { eattr *d = t->attrs; @@ -694,6 +694,16 @@ ea_merge(ea_list *e, ea_list *t) } } +ea_list * +ea_normalize(const ea_list *e) +{ + ea_list *t = tmp_alloc(ea_scan(e)); + ea_merge(e, t); + ea_sort(t); + + return t->count ? t : NULL; +} + /** * ea_same - compare two &ea_list's * @x: attribute list @@ -729,33 +739,38 @@ ea_same(ea_list *x, ea_list *y) return 1; } -static inline ea_list * -ea_list_copy(ea_list *o) +uint +ea_list_size(ea_list *o) { - ea_list *n; - unsigned i, adpos, elen; + unsigned i, elen; - if (!o) - return NULL; - ASSERT(!o->next); - elen = adpos = sizeof(ea_list) + sizeof(eattr) * o->count; + ASSERT_DIE(o); + ASSERT_DIE(!o->next); + elen = BIRD_CPU_ALIGN(sizeof(ea_list) + sizeof(eattr) * o->count); for(i=0; icount; i++) { eattr *a = &o->attrs[i]; if (!(a->type & EAF_EMBEDDED)) - elen += sizeof(struct adata) + a->u.ptr->length; + elen += ADATA_SIZE(a->u.ptr->length); } - n = mb_alloc(rta_pool, elen); + return elen; +} + +void +ea_list_copy(ea_list *n, ea_list *o, uint elen) +{ + uint adpos = sizeof(ea_list) + sizeof(eattr) * o->count; memcpy(n, o, adpos); - n->flags |= EALF_CACHED; - for(i=0; icount; i++) + adpos = BIRD_CPU_ALIGN(adpos); + + for(uint i=0; icount; i++) { eattr *a = &n->attrs[i]; if (!(a->type & EAF_EMBEDDED)) { - unsigned size = sizeof(struct adata) + a->u.ptr->length; + unsigned size = ADATA_SIZE(a->u.ptr->length); ASSERT_DIE(adpos + size <= elen); struct adata *d = ((void *) n) + adpos; @@ -765,8 +780,8 @@ ea_list_copy(ea_list *o) adpos += size; } } + ASSERT_DIE(adpos == elen); - return n; } static inline void @@ -1029,6 +1044,7 @@ ea_hash(ea_list *e) if (e) /* Assuming chain of length 1 */ { + ASSERT_DIE(!e->next); for(i=0; icount; i++) { struct eattr *a = &e->attrs[i]; @@ -1135,7 +1151,13 @@ rta_copy(rta *o) memcpy(r, o, rta_size(o)); r->uc = 1; r->nh.next = nexthop_copy(o->nh.next); - r->eattrs = ea_list_copy(o->eattrs); + if (!r->eattrs) + return r; + + uint elen = ea_list_size(o->eattrs); + r->eattrs = mb_alloc(rta_pool, elen); + ea_list_copy(r->eattrs, o->eattrs, elen); + r->eattrs->flags |= EALF_CACHED; return r; } @@ -1191,7 +1213,7 @@ rta_lookup(rta *o) ASSERT(!o->cached); if (o->eattrs) - ea_normalize(o->eattrs); + o->eattrs = ea_normalize(o->eattrs); h = rta_hash(o); for(r=rta_hash_table[h & rta_cache_mask]; r; r=r->next) diff --git a/nest/rt-show.c b/nest/rt-show.c index 464e5f1b..4e0c5602 100644 --- a/nest/rt-show.c +++ b/nest/rt-show.c @@ -55,7 +55,7 @@ rt_show_rte(struct cli *c, byte *ia, rte *e, struct rt_show_data *d, int primary /* Need to normalize the extended attributes */ if (d->verbose && !rta_is_cached(a) && a->eattrs) - ea_normalize(a->eattrs); + a->eattrs = ea_normalize(a->eattrs); get_route_info = e->src->proto->proto->get_route_info; if (get_route_info) diff --git a/proto/bgp/attrs.c b/proto/bgp/attrs.c index 2c0d011f..1c49e76a 100644 --- a/proto/bgp/attrs.c +++ b/proto/bgp/attrs.c @@ -1191,12 +1191,11 @@ bgp_export_attr(struct bgp_export_state *s, eattr *a, ea_list *to) * Result: one sorted attribute list segment, or NULL if attributes are unsuitable. */ static inline ea_list * -bgp_export_attrs(struct bgp_export_state *s, ea_list *attrs) +bgp_export_attrs(struct bgp_export_state *s, const ea_list *a) { /* Merge the attribute list */ - ea_list *new = lp_alloc(s->pool, ea_scan(attrs)); - ea_merge(attrs, new); - ea_sort(new); + ea_list *new = ea_normalize(a); + ASSERT_DIE(new); uint i, count; count = new->count; @@ -1498,6 +1497,7 @@ bgp_free_bucket_table(struct bgp_channel *c) static struct bgp_bucket * bgp_get_bucket(struct bgp_channel *c, ea_list *new) { + /* Hash and lookup */ u32 hash = ea_hash(new); struct bgp_bucket *b = HASH_FIND(c->bucket_hash, RBH, new, hash); @@ -1505,45 +1505,18 @@ bgp_get_bucket(struct bgp_channel *c, ea_list *new) if (b) return b; - uint ea_size = sizeof(ea_list) + new->count * sizeof(eattr); - uint ea_size_aligned = BIRD_ALIGN(ea_size, CPU_STRUCT_ALIGN); - uint size = sizeof(struct bgp_bucket) + ea_size_aligned; - uint i; - byte *dest; - - /* Gather total size of non-inline attributes */ - for (i = 0; i < new->count; i++) - { - eattr *a = &new->attrs[i]; - - if (!(a->type & EAF_EMBEDDED)) - size += BIRD_ALIGN(sizeof(struct adata) + a->u.ptr->length, CPU_STRUCT_ALIGN); - } + /* Scan the list for total size */ + uint ea_size = BIRD_CPU_ALIGN(ea_list_size(new)); + uint size = sizeof(struct bgp_bucket) + ea_size; - /* Create the bucket */ + /* Allocate the bucket */ b = mb_alloc(c->pool, size); *b = (struct bgp_bucket) { }; init_list(&b->prefixes); b->hash = hash; - /* Copy list of extended attributes */ - memcpy(b->eattrs, new, ea_size); - dest = ((byte *) b->eattrs) + ea_size_aligned; - - /* Copy values of non-inline attributes */ - for (i = 0; i < new->count; i++) - { - eattr *a = &b->eattrs->attrs[i]; - - if (!(a->type & EAF_EMBEDDED)) - { - const struct adata *oa = a->u.ptr; - struct adata *na = (struct adata *) dest; - memcpy(na, oa, sizeof(struct adata) + oa->length); - a->u.ptr = na; - dest += BIRD_ALIGN(sizeof(struct adata) + na->length, CPU_STRUCT_ALIGN); - } - } + /* Copy the ea_list */ + ea_list_copy(b->eattrs, new, ea_size); /* Insert the bucket to send queue and bucket hash */ add_tail(&c->bucket_queue, &b->send_node); diff --git a/proto/mrt/mrt.c b/proto/mrt/mrt.c index 321c6395..760cfa73 100644 --- a/proto/mrt/mrt.c +++ b/proto/mrt/mrt.c @@ -431,7 +431,7 @@ mrt_rib_table_entry_bgp_attrs(struct mrt_table_dump_state *s, rte *r) /* Attribute list must be normalized for bgp_encode_attrs() */ if (!rta_is_cached(r->attrs)) - ea_normalize(eattrs); + eattrs = ea_normalize(eattrs); mrt_buffer_need(b, MRT_ATTR_BUFFER_SIZE); byte *pos = b->pos; -- cgit v1.2.3 From 1d309c4ce6e95b68c64a8f007f6dd2f1830a5707 Mon Sep 17 00:00:00 2001 From: Maria Matejka Date: Thu, 14 Apr 2022 16:51:18 +0200 Subject: Enforcing certain data structure explicit paddings. Implicit paddings have undefined values in C. We want the eattr blocks to be comparable by memcmp and eattrs settable directly by structrure literals. This check ensures that all paddings in eattr and bval are explicit and therefore zeroed in all literals. --- aclocal.m4 | 26 +++++++++++++++++++ configure.ac | 7 ++++++ lib/Makefile | 2 +- lib/birdlib.h | 18 ++++++++++--- lib/route.h | 2 ++ lib/type.h | 12 ++++++--- lib/type_test.c | 78 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ nest/Makefile | 2 +- nest/bird.h | 1 - 9 files changed, 139 insertions(+), 9 deletions(-) create mode 100644 lib/type_test.c (limited to 'lib/birdlib.h') diff --git a/aclocal.m4 b/aclocal.m4 index 1613d680..58c48791 100644 --- a/aclocal.m4 +++ b/aclocal.m4 @@ -1,6 +1,32 @@ dnl ** Additional Autoconf tests for BIRD configure script dnl ** (c) 1999 Martin Mares +AC_DEFUN([BIRD_CHECK_POINTER_ALIGNMENT], +[ + AC_CACHE_CHECK( + [how pointers are aligned], + [bird_cv_pointer_alignment], + AC_COMPILE_IFELSE([ + AC_LANG_PROGRAM( + [ + _Static_assert(_Alignof(void *) == 8, "bad"); + ], [] + ) + ], + [bird_cv_pointer_alignment=8], + AC_COMPILE_IFELSE([ + AC_LANG_PROGRAM( + [ + _Static_assert(_Alignof(void *) == 4, "bad"); + ], [] + ) + ], + [bird_cv_pointer_alignment=4], + [bird_cv_pointer_alignment=unknown] + )) + ) +]) + AC_DEFUN([BIRD_CHECK_THREAD_LOCAL], [ AC_CACHE_CHECK( diff --git a/configure.ac b/configure.ac index 64181d29..321bed95 100644 --- a/configure.ac +++ b/configure.ac @@ -360,6 +360,13 @@ AC_C_BIGENDIAN( [AC_MSG_ERROR([Cannot determine CPU endianity.])] ) +BIRD_CHECK_POINTER_ALIGNMENT +if test "$bird_cv_pointer_alignment" = "unknown" ; then + AC_MSG_ERROR([Couldn't determine pointer alignment]) +else + AC_DEFINE_UNQUOTED([CPU_POINTER_ALIGNMENT], [$bird_cv_pointer_alignment], [Pointer alignment for macro usage]) +fi + BIRD_CHECK_ANDROID_GLOB if test "$bird_cv_lib_glob" = no ; then AC_MSG_ERROR([glob.h not found.]) diff --git a/lib/Makefile b/lib/Makefile index 853e0a22..15f757d9 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -2,6 +2,6 @@ src := a-path.c a-set.c bitmap.c bitops.c blake2s.c blake2b.c checksum.c event.c obj := $(src-o-files) $(all-daemon) -tests_src := a-set_test.c a-path_test.c bitmap_test.c heap_test.c buffer_test.c event_test.c flowspec_test.c bitops_test.c patmatch_test.c fletcher16_test.c slist_test.c checksum_test.c lists_test.c mac_test.c ip_test.c hash_test.c printf_test.c slab_test.c +tests_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/birdlib.h b/lib/birdlib.h index 6f0bab96..9b6e4a16 100644 --- a/lib/birdlib.h +++ b/lib/birdlib.h @@ -9,18 +9,30 @@ #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 */ #define MIN_(a,b) (((a)<(b))?(a):(b)) diff --git a/lib/route.h b/lib/route.h index 431da4d8..ba7bab61 100644 --- a/lib/route.h +++ b/lib/route.h @@ -144,6 +144,8 @@ typedef struct eattr { byte fresh:1; /* An uncached attribute (e.g. modified in export filter) */ byte undef:1; /* Explicitly undefined */ + PADDING(unused, 0, 4); + union bval u; } eattr; diff --git a/lib/type.h b/lib/type.h index 6d19a250..e43389f3 100644 --- a/lib/type.h +++ b/lib/type.h @@ -13,9 +13,15 @@ #include "lib/attrs.h" union bval { -#define BVAL_ITEMS \ - u32 data; /* Integer type inherited from eattrs */ \ - u32 i; /* Integer type inherited from filters */ \ +#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 */ \ diff --git a/lib/type_test.c b/lib/type_test.c new file mode 100644 index 00000000..20e7630b --- /dev/null +++ b/lib/type_test.c @@ -0,0 +1,78 @@ +/* + * BIRD Library -- Data Type Alignment Tests + * + * (c) 2022 Maria Matejka + * + * 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 $@ + $(Q)echo "#include \"lib/birdlib.h\"\n$(patsubst %,void %(void);\n,$(PROTO_BUILD)) void protos_build_gen(void) { $(patsubst %, %();\n,$(PROTO_BUILD))}" > $@ tests_src := tests_targets := $(tests_targets) $(tests-target-files) diff --git a/nest/bird.h b/nest/bird.h index 55712abe..931974a0 100644 --- a/nest/bird.h +++ b/nest/bird.h @@ -9,7 +9,6 @@ #ifndef _BIRD_BIRD_H_ #define _BIRD_BIRD_H_ -#include "sysdep/config.h" #include "lib/birdlib.h" #include "lib/ip.h" #include "lib/net.h" -- cgit v1.2.3