diff options
Diffstat (limited to 'lib')
-rw-r--r-- | lib/birdlib.h | 3 | ||||
-rw-r--r-- | lib/event.c | 2 | ||||
-rw-r--r-- | lib/flowspec_test.c | 8 | ||||
-rw-r--r-- | lib/ip.h | 35 | ||||
-rw-r--r-- | lib/ip_test.c | 66 | ||||
-rw-r--r-- | lib/lists.h | 1 | ||||
-rw-r--r-- | lib/mempool.c | 14 | ||||
-rw-r--r-- | lib/net.h | 1 | ||||
-rw-r--r-- | lib/resource.c | 35 | ||||
-rw-r--r-- | lib/resource.h | 25 | ||||
-rw-r--r-- | lib/slab.c | 44 | ||||
-rw-r--r-- | lib/socket.h | 1 | ||||
-rw-r--r-- | lib/timer.c | 1 |
13 files changed, 196 insertions, 40 deletions
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)) 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/flowspec_test.c b/lib/flowspec_test.c index ed4afe51..115084a3 100644 --- a/lib/flowspec_test.c +++ b/lib/flowspec_test.c @@ -449,7 +449,6 @@ t_builder4(void) resource_init(); struct flow_builder *fb = flow_builder_init(&root_pool); - linpool *lp = lp_new_default(&root_pool); /* Expectation */ @@ -492,7 +491,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); @@ -530,7 +529,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 +572,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 +599,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; @@ -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); } 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..f9a9aaca 100644 --- a/lib/mempool.c +++ b/lib/mempool.c @@ -43,10 +43,12 @@ struct linpool { uint chunk_size, threshold, total:31, use_pages:1, total_large; }; +_Thread_local linpool *tmp_linpool; + 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", @@ -302,7 +304,7 @@ lp_dump(resource *r) m->total_large); } -static size_t +static struct resmem lp_memsize(resource *r) { linpool *m = (linpool *) r; @@ -314,9 +316,11 @@ lp_memsize(resource *r) for(c=m->first_large; c; c=c->next) cnt++; - return ALLOC_OVERHEAD + sizeof(struct linpool) + - cnt * (ALLOC_OVERHEAD + sizeof(struct lp_chunk)) + - m->total + m->total_large; + return (struct resmem) { + .effective = m->total + m->total_large, + .overhead = ALLOC_OVERHEAD + sizeof(struct linpool) + + cnt * (ALLOC_OVERHEAD + sizeof(struct lp_chunk)), + }; } @@ -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/resource.c b/lib/resource.c index 4c4b92ec..a179afe3 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. */ @@ -37,7 +38,7 @@ struct pool { 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", @@ -97,15 +98,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); + { + struct resmem add = rmemsize(r); + sum.effective += add.effective; + sum.overhead += add.overhead; + } return sum; } @@ -193,14 +201,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); } @@ -259,9 +270,12 @@ 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); } /** @@ -305,11 +319,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 = { diff --git a/lib/resource.h b/lib/resource.h index 1b9fed33..313b01dc 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 */ @@ -40,7 +46,7 @@ void resource_init(void); pool *rp_new(pool *, const char *); /* Create new pool */ 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 */ @@ -73,6 +79,15 @@ 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 _Thread_local linpool *tmp_linpool; /* Temporary linpool autoflushed regularily */ + +#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) + +#define tmp_init(p) tmp_linpool = lp_new_default(p) +#define tmp_flush() lp_flush(tmp_linpool) + 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) @@ -95,10 +110,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. */ -u64 get_page_size(void); +extern long page_size; void *alloc_page(void); void free_page(void *); +void resource_sys_init(void); + #ifdef HAVE_LIBDMALLOC /* * The standard dmalloc macros tend to produce lots of namespace @@ -42,7 +42,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 @@ -128,7 +128,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 +138,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, + }; } @@ -177,7 +180,7 @@ struct sl_alignment { /* Magic structure for testing of alignment */ int x[0]; }; -#define SL_GET_HEAD(x) ((struct sl_head *) (((uintptr_t) (x)) & ~(get_page_size()-1))) +#define SL_GET_HEAD(x) ((struct sl_head *) (((uintptr_t) (x)) & ~(page_size-1))) /** * sl_new - create a new Slab @@ -192,14 +195,13 @@ sl_new(pool *p, uint size) { slab *s = ralloc(p, &sl_class); 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; s->head_size = sizeof(struct sl_head); - u64 page_size = get_page_size(); do { s->objs_per_slab = (page_size - s->head_size) / size; @@ -270,7 +272,7 @@ no_partial: } h = alloc_page(); #ifdef POISON - memset(h, 0xba, get_page_size()); + memset(h, 0xba, page_size); #endif ASSERT_DIE(SL_GET_HEAD(h) == h); memset(h, 0, s->head_size); @@ -329,7 +331,7 @@ sl_free(slab *s, void *oo) if (s->num_empty_heads >= MAX_EMPTY_HEADS) { #ifdef POISON - memset(h, 0xde, get_page_size()); + memset(h, 0xde, page_size); #endif free_page(h); } @@ -371,21 +373,33 @@ slab_dump(resource *r) 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_LIST(h, s->full_heads) heads++; + + size_t items = heads * s->objs_per_slab; + WALK_LIST(h, s->partial_heads) + { heads++; - WALK_LIST(h, s->full_heads) + items += h->num_full; + } + + WALK_LIST(h, s->empty_heads) heads++; - return ALLOC_OVERHEAD + sizeof(struct slab) + heads * (ALLOC_OVERHEAD + get_page_size()); + size_t eff = items * s->obj_size; + + return (struct resmem) { + .effective = eff, + .overhead = ALLOC_OVERHEAD + sizeof(struct slab) + heads * page_size - eff, + }; } static resource * @@ -395,10 +409,10 @@ slab_lookup(resource *r, unsigned long a) struct sl_head *h; WALK_LIST(h, s->partial_heads) - if ((unsigned long) h < a && (unsigned long) h + get_page_size() < a) + if ((unsigned long) h < a && (unsigned long) h + page_size < a) return r; WALK_LIST(h, s->full_heads) - if ((unsigned long) h < a && (unsigned long) h + get_page_size() < a) + if ((unsigned long) h < a && (unsigned long) h + page_size < a) return r; return NULL; } 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/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(); } } |