From 9202b3fdfdaf890752d7472692296490ec55c750 Mon Sep 17 00:00:00 2001 From: Craig Tiller Date: Sun, 12 Mar 2017 22:30:38 -0700 Subject: Arena allocator for grpc --- src/core/lib/support/arena.c | 90 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 90 insertions(+) create mode 100644 src/core/lib/support/arena.c (limited to 'src/core/lib/support/arena.c') diff --git a/src/core/lib/support/arena.c b/src/core/lib/support/arena.c new file mode 100644 index 0000000000..a5b0be4d48 --- /dev/null +++ b/src/core/lib/support/arena.c @@ -0,0 +1,90 @@ +/* + * + * Copyright 2017, Google Inc. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + */ + +#include "src/core/lib/support/arena.h" +#include +#include +#include + +typedef struct zone { + size_t size_begin; + size_t size_end; + gpr_atm next_atm; +} zone; + +struct gpr_arena { + gpr_atm size_so_far; + zone initial_zone; +}; + +gpr_arena *gpr_arena_create(size_t initial_size) { + gpr_arena *a = gpr_zalloc(sizeof(gpr_arena) + initial_size); + a->initial_zone.size_end = initial_size; + return a; +} + +size_t gpr_arena_destroy(gpr_arena *arena) { + gpr_atm size = gpr_atm_no_barrier_load(&arena->size_so_far); + zone *z = (zone *)gpr_atm_no_barrier_load(&arena->initial_zone.next_atm); + gpr_free(arena); + while (z) { + zone *next_z = (zone *)gpr_atm_no_barrier_load(&z->next_atm); + gpr_free(z); + z = next_z; + } + return (size_t)size; +} + +void *gpr_arena_alloc(gpr_arena *arena, size_t size) { + size_t start = + (size_t)gpr_atm_no_barrier_fetch_add(&arena->size_so_far, size); + zone *z = &arena->initial_zone; + while (start > z->size_begin) { + zone *next_z = (zone *)gpr_atm_acq_load(&z->next_atm); + while (next_z == NULL) { + size_t next_z_size = GPR_MAX(2 * start, size); + next_z = gpr_zalloc(sizeof(zone) + next_z_size); + next_z->size_begin = z->size_end; + next_z->size_end = z->size_end + next_z_size; + if (!gpr_atm_rel_cas(&z->next_atm, (gpr_atm)NULL, (gpr_atm)next_z)) { + gpr_free(next_z); + next_z = NULL; + } + } + z = next_z; + } + if (start + size > z->size_end) { + return gpr_arena_alloc(arena, size); + } + return ((char *)(z + 1)) + start - z->size_begin; +} -- cgit v1.2.3 From 0dd81003b5a9601d4bc79afdd269a7e93b53c5a9 Mon Sep 17 00:00:00 2001 From: Craig Tiller Date: Mon, 13 Mar 2017 06:57:29 -0700 Subject: Concurrent test --- src/core/lib/support/arena.c | 5 +++++ test/core/support/arena_test.c | 43 ++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 48 insertions(+) (limited to 'src/core/lib/support/arena.c') diff --git a/src/core/lib/support/arena.c b/src/core/lib/support/arena.c index a5b0be4d48..faceb1a1eb 100644 --- a/src/core/lib/support/arena.c +++ b/src/core/lib/support/arena.c @@ -36,6 +36,9 @@ #include #include +#define ROUND_UP_TO_ALIGNMENT_SIZE(x) \ + (((x) + GPR_MAX_ALIGNMENT - 1u) & ~(GPR_MAX_ALIGNMENT - 1u)) + typedef struct zone { size_t size_begin; size_t size_end; @@ -48,6 +51,7 @@ struct gpr_arena { }; gpr_arena *gpr_arena_create(size_t initial_size) { + initial_size = ROUND_UP_TO_ALIGNMENT_SIZE(initial_size); gpr_arena *a = gpr_zalloc(sizeof(gpr_arena) + initial_size); a->initial_zone.size_end = initial_size; return a; @@ -66,6 +70,7 @@ size_t gpr_arena_destroy(gpr_arena *arena) { } void *gpr_arena_alloc(gpr_arena *arena, size_t size) { + size = ROUND_UP_TO_ALIGNMENT_SIZE(size); size_t start = (size_t)gpr_atm_no_barrier_fetch_add(&arena->size_so_far, size); zone *z = &arena->initial_zone; diff --git a/test/core/support/arena_test.c b/test/core/support/arena_test.c index bbf6d48db3..3e21867bcf 100644 --- a/test/core/support/arena_test.c +++ b/test/core/support/arena_test.c @@ -36,8 +36,11 @@ #include #include #include +#include +#include #include #include +#include #include "src/core/lib/support/string.h" #include "test/core/util/test_config.h" @@ -65,9 +68,12 @@ static void test(const char *name, size_t init_size, const size_t *allocs, void **ps = gpr_zalloc(sizeof(*ps) * nallocs); for (size_t i = 0; i < nallocs; i++) { ps[i] = gpr_arena_alloc(a, allocs[i]); + // ensure no duplicate results for (size_t j = 0; j < i; j++) { GPR_ASSERT(ps[i] != ps[j]); } + // ensure writable + memset(ps[i], 1, allocs[i]); } gpr_arena_destroy(a); } @@ -76,6 +82,42 @@ static void test(const char *name, size_t init_size, const size_t *allocs, static const size_t allocs_##name[] = {__VA_ARGS__}; \ test(#name, init_size, allocs_##name, GPR_ARRAY_SIZE(allocs_##name)) +#define CONCURRENT_TEST_ITERATIONS 100000 +#define CONCURRENT_TEST_THREADS 100 + +typedef struct { + gpr_event ev_start; + gpr_arena *arena; +} concurrent_test_args; + +static void concurrent_test_body(void *arg) { + concurrent_test_args *a = arg; + gpr_event_wait(&a->ev_start, gpr_inf_future(GPR_CLOCK_REALTIME)); + for (size_t i = 0; i < CONCURRENT_TEST_ITERATIONS; i++) { + *(char *)gpr_arena_alloc(a->arena, 1) = (char)i; + } +} + +static void concurrent_test(void) { + concurrent_test_args args; + gpr_event_init(&args.ev_start); + args.arena = gpr_arena_create(1024); + + gpr_thd_id thds[CONCURRENT_TEST_THREADS]; + + for (int i = 0; i < CONCURRENT_TEST_THREADS; i++) { + gpr_thd_options opt = gpr_thd_options_default(); + gpr_thd_options_is_joinable(&opt); + gpr_thd_new(&thds[i], concurrent_test_body, &args, &opt); + } + + gpr_event_set(&args.ev_start, (void *)1); + + for (int i = 0; i < CONCURRENT_TEST_THREADS; i++) { + gpr_thd_join(thds[i]); + } +} + int main(int argc, char *argv[]) { grpc_test_init(argc, argv); @@ -86,6 +128,7 @@ int main(int argc, char *argv[]) { TEST(1_3, 1, 3); TEST(1_inc, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11); TEST(6_123, 6, 1, 2, 3); + concurrent_test(); return 0; } -- cgit v1.2.3 From 37723c9ee07c05633b763cfd5cfe0935a20a9258 Mon Sep 17 00:00:00 2001 From: Craig Tiller Date: Mon, 13 Mar 2017 07:45:44 -0700 Subject: Fix race condition --- src/core/lib/support/arena.c | 11 +++++++---- test/core/support/arena_test.c | 7 ++++++- 2 files changed, 13 insertions(+), 5 deletions(-) (limited to 'src/core/lib/support/arena.c') diff --git a/src/core/lib/support/arena.c b/src/core/lib/support/arena.c index faceb1a1eb..b5c32b2041 100644 --- a/src/core/lib/support/arena.c +++ b/src/core/lib/support/arena.c @@ -34,6 +34,7 @@ #include "src/core/lib/support/arena.h" #include #include +#include #include #define ROUND_UP_TO_ALIGNMENT_SIZE(x) \ @@ -74,16 +75,16 @@ void *gpr_arena_alloc(gpr_arena *arena, size_t size) { size_t start = (size_t)gpr_atm_no_barrier_fetch_add(&arena->size_so_far, size); zone *z = &arena->initial_zone; - while (start > z->size_begin) { + while (start > z->size_end) { zone *next_z = (zone *)gpr_atm_acq_load(&z->next_atm); - while (next_z == NULL) { - size_t next_z_size = GPR_MAX(2 * start, size); + if (next_z == NULL) { + size_t next_z_size = GPR_MAX((size_t)gpr_atm_no_barrier_load(&arena->size_so_far), size); next_z = gpr_zalloc(sizeof(zone) + next_z_size); next_z->size_begin = z->size_end; next_z->size_end = z->size_end + next_z_size; if (!gpr_atm_rel_cas(&z->next_atm, (gpr_atm)NULL, (gpr_atm)next_z)) { gpr_free(next_z); - next_z = NULL; + next_z = (zone*)gpr_atm_acq_load(&z->next_atm); } } z = next_z; @@ -91,5 +92,7 @@ void *gpr_arena_alloc(gpr_arena *arena, size_t size) { if (start + size > z->size_end) { return gpr_arena_alloc(arena, size); } + GPR_ASSERT(start >= z->size_begin); + GPR_ASSERT(start + size <= z->size_end); return ((char *)(z + 1)) + start - z->size_begin; } diff --git a/test/core/support/arena_test.c b/test/core/support/arena_test.c index 3e21867bcf..35b2bbd1b1 100644 --- a/test/core/support/arena_test.c +++ b/test/core/support/arena_test.c @@ -76,6 +76,7 @@ static void test(const char *name, size_t init_size, const size_t *allocs, memset(ps[i], 1, allocs[i]); } gpr_arena_destroy(a); + gpr_free(ps); } #define TEST(name, init_size, ...) \ @@ -99,6 +100,8 @@ static void concurrent_test_body(void *arg) { } static void concurrent_test(void) { + gpr_log(GPR_DEBUG, "concurrent_test"); + concurrent_test_args args; gpr_event_init(&args.ev_start); args.arena = gpr_arena_create(1024); @@ -107,7 +110,7 @@ static void concurrent_test(void) { for (int i = 0; i < CONCURRENT_TEST_THREADS; i++) { gpr_thd_options opt = gpr_thd_options_default(); - gpr_thd_options_is_joinable(&opt); + gpr_thd_options_set_joinable(&opt); gpr_thd_new(&thds[i], concurrent_test_body, &args, &opt); } @@ -116,6 +119,8 @@ static void concurrent_test(void) { for (int i = 0; i < CONCURRENT_TEST_THREADS; i++) { gpr_thd_join(thds[i]); } + + gpr_arena_destroy(args.arena); } int main(int argc, char *argv[]) { -- cgit v1.2.3 From 09acb108b7620eff840fb0428f7eb159a4f27cf4 Mon Sep 17 00:00:00 2001 From: Craig Tiller Date: Mon, 13 Mar 2017 07:45:59 -0700 Subject: clang-format --- src/core/lib/support/arena.c | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) (limited to 'src/core/lib/support/arena.c') diff --git a/src/core/lib/support/arena.c b/src/core/lib/support/arena.c index b5c32b2041..6610acd3a0 100644 --- a/src/core/lib/support/arena.c +++ b/src/core/lib/support/arena.c @@ -78,13 +78,14 @@ void *gpr_arena_alloc(gpr_arena *arena, size_t size) { while (start > z->size_end) { zone *next_z = (zone *)gpr_atm_acq_load(&z->next_atm); if (next_z == NULL) { - size_t next_z_size = GPR_MAX((size_t)gpr_atm_no_barrier_load(&arena->size_so_far), size); + size_t next_z_size = + GPR_MAX((size_t)gpr_atm_no_barrier_load(&arena->size_so_far), size); next_z = gpr_zalloc(sizeof(zone) + next_z_size); next_z->size_begin = z->size_end; next_z->size_end = z->size_end + next_z_size; if (!gpr_atm_rel_cas(&z->next_atm, (gpr_atm)NULL, (gpr_atm)next_z)) { gpr_free(next_z); - next_z = (zone*)gpr_atm_acq_load(&z->next_atm); + next_z = (zone *)gpr_atm_acq_load(&z->next_atm); } } z = next_z; -- cgit v1.2.3 From d26250be35a0e0921cb97f43b13ce14343ee4c7d Mon Sep 17 00:00:00 2001 From: Craig Tiller Date: Tue, 14 Mar 2017 11:01:52 -0700 Subject: Get growth right --- src/core/lib/support/arena.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'src/core/lib/support/arena.c') diff --git a/src/core/lib/support/arena.c b/src/core/lib/support/arena.c index 6610acd3a0..7bcb983f24 100644 --- a/src/core/lib/support/arena.c +++ b/src/core/lib/support/arena.c @@ -78,8 +78,7 @@ void *gpr_arena_alloc(gpr_arena *arena, size_t size) { while (start > z->size_end) { zone *next_z = (zone *)gpr_atm_acq_load(&z->next_atm); if (next_z == NULL) { - size_t next_z_size = - GPR_MAX((size_t)gpr_atm_no_barrier_load(&arena->size_so_far), size); + size_t next_z_size = (size_t)gpr_atm_no_barrier_load(&arena->size_so_far); next_z = gpr_zalloc(sizeof(zone) + next_z_size); next_z->size_begin = z->size_end; next_z->size_end = z->size_end + next_z_size; -- cgit v1.2.3