From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp10.mail.ru (smtp10.mail.ru [94.100.181.92]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dev.tarantool.org (Postfix) with ESMTPS id 462B9469710 for ; Sat, 16 May 2020 02:22:02 +0300 (MSK) From: Vladislav Shpilevoy Date: Sat, 16 May 2020 01:21:57 +0200 Message-Id: <194d73cbb844795fbe2a9a6599bb684f4e6a0cf2.1589584903.git.v.shpilevoy@tarantool.org> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Subject: [Tarantool-patches] [PATCH v2 small 1/1] lsregion: introduce aligned alloc List-Id: Tarantool development patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: tarantool-patches@dev.tarantool.org, tsafin@tarantool.org, alyapunov@tarantool.org, gorcunov@gmail.com lsregion_alloc() can return a not aligned address, even odd. This is not good when the allocation is going to be used for a type, which requires alignment, such as a number, or a struct having numbers in it. Unaligned access to objects saved into the returned memory is either slower than aligned access, or can even lead to a crash on certain architectures. Also it makes 'alignment' clang sanitizer crazy. The patch provides a function to make aligned allocations on lsregion. Part of https://github.com/tarantool/tarantool/issues/4609 --- Branch: http://github.com/tarantool/small/tree/gerold103/aligned-lsregion Issue: https://github.com/tarantool/tarantool/issues/4609 Changes in v2: - Made lsregion do not reserve extra bytes, when aligned allocation is requested, and the first available address is already aligned. small/lsregion.c | 93 +++++++++++++++++----------------- small/lsregion.h | 116 +++++++++++++++++++++++++++++++++++++------ test/lsregion.c | 95 ++++++++++++++++++++++++++++++++++- test/lsregion.result | 32 +++++++++++- 4 files changed, 274 insertions(+), 62 deletions(-) diff --git a/small/lsregion.c b/small/lsregion.c index 6bcc043..e6e347c 100644 --- a/small/lsregion.c +++ b/small/lsregion.c @@ -32,59 +32,62 @@ #include "lsregion.h" void * -lsregion_alloc_slow(struct lsregion *lsregion, size_t size, int64_t id) +lsregion_aligned_reserve_slow(struct lsregion *lsregion, size_t size, + size_t alignment, void **unaligned) { - struct lslab *slab = NULL; - size_t slab_size = lsregion->arena->slab_size; + void *pos; + struct lslab *slab; + struct slab_arena *arena = lsregion->arena; + size_t slab_size = arena->slab_size; /* If there is an existing slab then try to use it. */ if (! rlist_empty(&lsregion->slabs.slabs)) { slab = rlist_last_entry(&lsregion->slabs.slabs, struct lslab, next_in_list); assert(slab != NULL); + *unaligned = lslab_pos(slab); + pos = (void *)small_align((size_t)*unaligned, alignment); + if (pos + size <= lslab_end(slab)) + return pos; } - if ((slab != NULL && size > lslab_unused(slab)) || - slab == NULL) { - if (size + lslab_sizeof() > slab_size) { - /* Large allocation, use malloc() */ - slab_size = size + lslab_sizeof(); - struct quota *quota = lsregion->arena->quota; - if (quota_use(quota, slab_size) < 0) - return NULL; - slab = malloc(slab_size); - if (slab == NULL) { - quota_release(quota, slab_size); - return NULL; - } - lslab_create(slab, slab_size); - rlist_add_tail_entry(&lsregion->slabs.slabs, slab, - next_in_list); - lsregion->slabs.stats.total += slab_size; - } else if (lsregion->cached != NULL) { - /* If there is the cached slab then use it. */ - slab = lsregion->cached; - lsregion->cached = NULL; - rlist_add_tail_entry(&lsregion->slabs.slabs, slab, - next_in_list); - } else { - slab = (struct lslab *) slab_map(lsregion->arena); - if (slab == NULL) - return NULL; - lslab_create(slab, slab_size); - rlist_add_tail_entry(&lsregion->slabs.slabs, slab, - next_in_list); - lsregion->slabs.stats.total += slab_size; + /* + * Need to allocate more, since it can happen, that the + * new slab won't be aligned by the needed alignment, and + * after alignment its size won't be enough. + */ + size_t aligned_size = size + alignment - 1; + if (aligned_size + lslab_sizeof() > slab_size) { + /* Large allocation, use malloc() */ + slab_size = aligned_size + lslab_sizeof(); + struct quota *quota = arena->quota; + if (quota_use(quota, slab_size) < 0) + return NULL; + slab = malloc(slab_size); + if (slab == NULL) { + quota_release(quota, slab_size); + return NULL; } + lslab_create(slab, slab_size); + rlist_add_tail_entry(&lsregion->slabs.slabs, slab, + next_in_list); + lsregion->slabs.stats.total += slab_size; + } else if (lsregion->cached != NULL) { + /* If there is the cached slab then use it. */ + slab = lsregion->cached; + lsregion->cached = NULL; + rlist_add_tail_entry(&lsregion->slabs.slabs, slab, + next_in_list); + } else { + slab = (struct lslab *) slab_map(arena); + if (slab == NULL) + return NULL; + lslab_create(slab, slab_size); + rlist_add_tail_entry(&lsregion->slabs.slabs, slab, + next_in_list); + lsregion->slabs.stats.total += slab_size; } - assert(slab != NULL); - assert(slab->max_id <= id); - assert(size <= lslab_unused(slab)); - void *res = lslab_pos(slab); - slab->slab_used += size; - - /* Update the memory block meta info. */ - assert(slab->max_id <= id); - slab->max_id = id; - lsregion->slabs.stats.used += size; - return res; + *unaligned = lslab_pos(slab); + pos = (void *)small_align((size_t)*unaligned, alignment); + assert(pos + size <= lslab_end(slab)); + return pos; } diff --git a/small/lsregion.h b/small/lsregion.h index 73d68dc..2fc0888 100644 --- a/small/lsregion.h +++ b/small/lsregion.h @@ -127,6 +127,18 @@ lslab_unused(const struct lslab *slab) return slab->slab_size - slab->slab_used; } +/** + * Update slab statistics and meta according to new allocation. + */ +static inline void +lslab_use(struct lslab *slab, size_t size, int64_t id) +{ + assert(size <= lslab_unused(slab)); + assert(slab->max_id <= id); + slab->slab_used += size; + slab->max_id = id; +} + /** * Pointer to the end of the used part of the slab. * @param slab Slab container. @@ -138,6 +150,13 @@ lslab_pos(struct lslab *slab) return (char *) slab + slab->slab_used; } +/** Pointer to the end of the slab memory. */ +static inline void * +lslab_end(struct lslab *slab) +{ + return (char *)slab + slab->slab_size; +} + /** * Initialize log structured allocator. * @param lsregion Allocator object. @@ -153,22 +172,30 @@ lsregion_create(struct lsregion *lsregion, struct slab_arena *arena) lsregion->cached = NULL; } -/** @sa lsregion_alloc(). */ +/** @sa lsregion_aligned_reserve(). */ void * -lsregion_alloc_slow(struct lsregion *lsregion, size_t size, int64_t id); +lsregion_aligned_reserve_slow(struct lsregion *lsregion, size_t size, + size_t alignment, void **unaligned); /** - * Allocate \p size bytes and assicoate the allocated block - * with \p id. + * Make sure a next allocation of at least @a size bytes will not + * fail, and will return the same result as this call, aligned by + * @a alignment. * @param lsregion Allocator object. * @param size Size to allocate. - * @param id Memory chunk identifier. + * @param alignment Byte alignment required for the result + * address. + * @param[out] unaligned When the function succeeds, it returns + * aligned address, and stores base unaligned address to + * this variable. That helps to find how many bytes were + * wasted to make the alignment. * * @retval not NULL Success. * @retval NULL Memory error. */ static inline void * -lsregion_alloc(struct lsregion *lsregion, size_t size, int64_t id) +lsregion_aligned_reserve(struct lsregion *lsregion, size_t size, + size_t alignment, void **unaligned) { /* If there is an existing slab then try to use it. */ if (! rlist_empty(&lsregion->slabs.slabs)) { @@ -176,16 +203,75 @@ lsregion_alloc(struct lsregion *lsregion, size_t size, int64_t id) slab = rlist_last_entry(&lsregion->slabs.slabs, struct lslab, next_in_list); assert(slab != NULL); - assert(slab->max_id <= id); - if (size <= lslab_unused(slab)) { - void *res = lslab_pos(slab); - slab->slab_used += size; - slab->max_id = id; - lsregion->slabs.stats.used += size; - return res; - } + *unaligned = lslab_pos(slab); + void *pos = (void *)small_align((size_t)*unaligned, alignment); + if (pos + size <= lslab_end(slab)) + return pos; } - return lsregion_alloc_slow(lsregion, size, id); + return lsregion_aligned_reserve_slow(lsregion, size, alignment, + unaligned); +} + +/** + * Make sure a next allocation of at least @a size bytes will not + * fail, and will return the same result as this call. + * @param lsregion Allocator object. + * @param size Size to allocate. + * + * @retval not-NULL Success. + * @retval NULL Memory error. + */ +static inline void * +lsregion_reserve(struct lsregion *lsregion, size_t size) +{ + void *unaligned = NULL; + void *res = lsregion_aligned_reserve(lsregion, size, 1, &unaligned); + assert(res == NULL || res == unaligned); + return res; +} + +/** + * Allocate @a size bytes and associate the allocated block + * with @a id. + * @param lsregion Allocator object. + * @param size Size to allocate. + * @param id Memory chunk identifier. + * + * @retval not-NULL Success. + * @retval NULL Memory error. + */ +static inline void * +lsregion_alloc(struct lsregion *lsregion, size_t size, int64_t id) +{ + void *res = lsregion_reserve(lsregion, size); + if (res == NULL) + return NULL; + struct lslab *slab = rlist_last_entry(&lsregion->slabs.slabs, + struct lslab, next_in_list); + lslab_use(slab, size, id); + lsregion->slabs.stats.used += size; + return res; +} + +/** + * The same as normal alloc, but the resulting pointer is aligned + * by @a alignment. + */ +static inline void * +lsregion_aligned_alloc(struct lsregion *lsregion, size_t size, size_t alignment, + int64_t id) +{ + void *unaligned; + void *res = lsregion_aligned_reserve(lsregion, size, alignment, + &unaligned); + if (res == NULL) + return NULL; + struct lslab *slab = rlist_last_entry(&lsregion->slabs.slabs, + struct lslab, next_in_list); + size += res - unaligned; + lslab_use(slab, size, id); + lsregion->slabs.stats.used += size; + return res; } /** diff --git a/test/lsregion.c b/test/lsregion.c index 90ad060..416c6fe 100644 --- a/test/lsregion.c +++ b/test/lsregion.c @@ -358,15 +358,108 @@ test_big_data_small_slabs() check_plan(); } +static void +test_reserve(void) +{ + plan(10); + header(); + + struct quota quota; + struct slab_arena arena; + struct lsregion allocator; + quota_init("a, 16 * SLAB_MIN_SIZE); + is(slab_arena_create(&arena, "a, 0, 0, MAP_PRIVATE), 0, "init"); + lsregion_create(&allocator, &arena); + + void *p1 = lsregion_reserve(&allocator, 100); + is(lsregion_used(&allocator), 0, "reserve does not occupy memory"); + is(lsregion_total(&allocator), arena.slab_size, "reserve creates slabs"); + void *p2 = lsregion_alloc(&allocator, 80, 1); + is(p1, p2, "alloc returns the same as reserve, even if size is less"); + is(lsregion_used(&allocator), 80, "alloc updated 'used'"); + + p1 = lsregion_reserve(&allocator, arena.slab_size - lslab_sizeof()); + is(lsregion_used(&allocator), 80, "next reserve didn't touch 'used'"); + is(lsregion_total(&allocator), arena.slab_size * 2, "but changed " + "'total' because second slab is allocated"); + is(lsregion_slab_count(&allocator), 2, "slab count is 2 now"); + lsregion_gc(&allocator, 1); + + is(lsregion_used(&allocator), 0, "gc works fine with empty reserved " + "slabs"); + is(lsregion_slab_count(&allocator), 0, "all slabs are removed"); + + lsregion_destroy(&allocator); + slab_arena_destroy(&arena); + + footer(); + check_plan(); +} + +static void +test_aligned(void) +{ + plan(12); + header(); + + struct quota quota; + struct slab_arena arena; + struct lsregion allocator; + quota_init("a, 16 * SLAB_MIN_SIZE); + is(slab_arena_create(&arena, "a, 0, 0, MAP_PRIVATE), 0, "init"); + lsregion_create(&allocator, &arena); + int id = 0; + + ++id; + void *p1 = lsregion_aligned_alloc(&allocator, 8, 8, id); + ok((unsigned long)p1 % 8 == 0, "trivial aligned"); + is(lsregion_used(&allocator), 8, "'used'"); + + ++id; + void *p2 = lsregion_aligned_alloc(&allocator, 1, 16, id); + ok((unsigned long)p2 % 16 == 0, "16 byte alignment for 1 byte"); + void *p3 = lsregion_aligned_alloc(&allocator, 1, 16, id); + ok(p3 == (char *)p2 + 16, "second 16 aligned alloc of 1 byte is far " + "from first"); + ok((unsigned long)p3 % 16 == 0, "aligned by 16 too"); + + is(lsregion_used(&allocator), (size_t)(p3 + 1 - p1), "'used'"); + + ++id; + void *p4 = lsregion_aligned_alloc(&allocator, 3, 4, id); + ok(p4 == (char *)p3 + 4, "align next by 4 bytes, should be closer to " + "previous"); + ok((unsigned long)p4 % 4 == 0, "aligned by 4"); + is(lsregion_used(&allocator), (size_t)(p4 + 3 - p1), "'used'"); + + lsregion_gc(&allocator, id); + + ++id; + p1 = lsregion_aligned_alloc(&allocator, + arena.slab_size - lslab_sizeof(), 32, id); + ok((unsigned long)p1 % 32 == 0, "32 byte aligned alloc of slab size"); + + lsregion_gc(&allocator, id); + is(lsregion_used(&allocator), 0, "gc deleted all"); + + lsregion_destroy(&allocator); + slab_arena_destroy(&arena); + + footer(); + check_plan(); +} + int main() { - plan(4); + plan(6); test_basic(); test_many_allocs_one_slab(); test_many_allocs_many_slabs(); test_big_data_small_slabs(); + test_reserve(); + test_aligned(); return check_plan(); } diff --git a/test/lsregion.result b/test/lsregion.result index 3157283..399c2a6 100644 --- a/test/lsregion.result +++ b/test/lsregion.result @@ -1,4 +1,4 @@ -1..4 +1..6 # basic 1..42 ok 1 - init @@ -76,3 +76,33 @@ ok 3 - subtests ok 6 - slab count after gc (id / 2) ok 7 - arena used after gc(id / 2) ok 4 - subtests + 1..10 + *** test_reserve *** + ok 1 - init + ok 2 - reserve does not occupy memory + ok 3 - reserve creates slabs + ok 4 - alloc returns the same as reserve, even if size is less + ok 5 - alloc updated 'used' + ok 6 - next reserve didn't touch 'used' + ok 7 - but changed 'total' because second slab is allocated + ok 8 - slab count is 2 now + ok 9 - gc works fine with empty reserved slabs + ok 10 - all slabs are removed + *** test_reserve: done *** +ok 5 - subtests + 1..12 + *** test_aligned *** + ok 1 - init + ok 2 - trivial aligned + ok 3 - 'used' + ok 4 - 16 byte alignment for 1 byte + ok 5 - second 16 aligned alloc of 1 byte is far from first + ok 6 - aligned by 16 too + ok 7 - 'used' + ok 8 - align next by 4 bytes, should be closer to previous + ok 9 - aligned by 4 + ok 10 - 'used' + ok 11 - 32 byte aligned alloc of slab size + ok 12 - gc deleted all + *** test_aligned: done *** +ok 6 - subtests -- 2.21.1 (Apple Git-122.3)