From 4814c4c79cc00ba61f865075af9ca8f919f6f370 Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Mon, 17 Dec 2012 13:53:25 +1030 Subject: [PATCH] tal: append the length property to the initial allocation. Since we never post-add a length property, we can save some cycles by allocating it together with the object itself: Before: $ ./samba-allocs talloc.dump --tal Tal time: 6058997-6215211(6102645)ns Tal_free time: 4791112-4968964(4824814)ns Single tal_free time: 3173647-3331584(3200183)ns $ ./samba-allocs talloc.dump --tal-size Virtual size = 9809920, RSS = 3952640 After: $ ./samba-allocs talloc.dump --tal Tal time: 5911994-6043808(5956914)ns Tal_free time: 4676026-4834598(4719908)ns Single tal_free time: 2888195-3067365(2922298)ns $ ./samba-allocs talloc.dump --tal-size Virtual size = 9809920, RSS = 3948544 Signed-off-by: Rusty Russell --- ccan/tal/_info | 1 + ccan/tal/tal.c | 98 ++++++++++++++++++++++++++------------- ccan/tal/test/run-count.c | 97 +++++++++++++++++++++++++++++--------- 3 files changed, 141 insertions(+), 55 deletions(-) diff --git a/ccan/tal/_info b/ccan/tal/_info index 853c6985..0d75f56e 100644 --- a/ccan/tal/_info +++ b/ccan/tal/_info @@ -94,6 +94,7 @@ int main(int argc, char *argv[]) return 1; if (strcmp(argv[1], "depends") == 0) { + printf("ccan/alignof\n"); printf("ccan/compiler\n"); printf("ccan/likely\n"); printf("ccan/list\n"); diff --git a/ccan/tal/tal.c b/ccan/tal/tal.c index 5c0aec07..ce122070 100644 --- a/ccan/tal/tal.c +++ b/ccan/tal/tal.c @@ -3,6 +3,7 @@ #include #include #include +#include #include #include #include @@ -326,18 +327,6 @@ static struct name *add_name_property(struct tal_hdr *t, const char *name) return prop; } -static struct length *add_length_property(struct tal_hdr *t, size_t count) -{ - struct length *prop; - - prop = allocate(sizeof(*prop)); - if (prop) { - init_property(&prop->hdr, t, LENGTH); - prop->count = count; - } - return prop; -} - static struct children *add_child_property(struct tal_hdr *parent, struct tal_hdr *child) { @@ -397,7 +386,9 @@ static void del_tree(struct tal_hdr *t, const tal_t *orig) /* Finally free our properties. */ for (p = t->prop; p && !is_literal(p); p = next) { next = p->next; - freefn(p); + /* LENGTH is appended, so don't free separately! */ + if (p->type != LENGTH) + freefn(p); } freefn(t); } @@ -424,14 +415,16 @@ void *tal_alloc_(const tal_t *ctx, size_t size, bool clear, const char *label) static bool adjust_size(size_t *size, size_t count) { + const size_t extra = sizeof(struct tal_hdr) + sizeof(struct length)*2; + /* Multiplication wrap */ if (count && unlikely(*size * count / *size != count)) goto overflow; *size *= count; - /* Make sure we don't wrap adding header. */ - if (*size + sizeof(struct tal_hdr) < sizeof(struct tal_hdr)) + /* Make sure we don't wrap adding header/tailer. */ + if (*size + extra < extra) goto overflow; return true; overflow: @@ -439,6 +432,17 @@ overflow: return false; } +static size_t extra_for_length(size_t size) +{ + size_t extra; + const size_t align = ALIGNOF(struct length); + + /* Round up size, and add tailer. */ + extra = ((size + align-1) & ~(align-1)) - size; + extra += sizeof(struct length); + return extra; +} + void *tal_alloc_arr_(const tal_t *ctx, size_t size, size_t count, bool clear, bool add_count, const char *label) { @@ -447,10 +451,18 @@ void *tal_alloc_arr_(const tal_t *ctx, size_t size, size_t count, bool clear, if (!adjust_size(&size, count)) return NULL; + if (add_count) + size += extra_for_length(size); + ret = tal_alloc_(ctx, size, clear, label); - if (likely(ret) && add_count) { - if (unlikely(!add_length_property(to_tal_hdr(ret), count))) - ret = tal_free(ret); + if (unlikely(!ret)) + return ret; + + if (add_count) { + struct length *lprop; + lprop = (struct length *)((char *)ret + size) - 1; + init_property(&lprop->hdr, to_tal_hdr(ret), LENGTH); + lprop->count = count; } return ret; } @@ -672,26 +684,49 @@ bool tal_resize_(tal_t **ctxp, size_t size, size_t count) { struct tal_hdr *old_t, *t; struct children *child; - struct length *len; + struct prop_hdr **lenp; + struct length len; + size_t extra = 0; old_t = debug_tal(to_tal_hdr(*ctxp)); if (!adjust_size(&size, count)) return false; - t = resizefn(old_t, size + sizeof(struct tal_hdr)); + lenp = find_property_ptr(old_t, LENGTH); + if (lenp) { + /* Copy here, in case we're shrinking! */ + len = *(struct length *)*lenp; + extra = extra_for_length(size); + } + + t = resizefn(old_t, sizeof(struct tal_hdr) + size + extra); if (!t) { call_error("Reallocation failure"); return false; } + /* Copy length to end. */ + if (lenp) { + struct length *new_len; + + new_len = (struct length *)((char *)(t + 1) + size); + len.count = count; + *new_len = len; + + /* Be careful replacing next ptr; could be old hdr. */ + if (lenp == &old_t->prop) + t->prop = &new_len->hdr; + else + *lenp = &new_len->hdr; + } + + update_bounds(t, sizeof(struct tal_hdr) + size + extra); + /* If it didn't move, we're done! */ if (t != old_t) { - update_bounds(t, size + sizeof(struct tal_hdr)); - /* Fix up linked list pointers. */ - if (list_entry(t->list.next, struct tal_hdr, list) != old_t) - t->list.next->prev = t->list.prev->next = &t->list; + t->list.next->prev = t->list.prev->next = &t->list; /* Fix up child property's parent pointer. */ child = find_property(t, CHILDREN); @@ -703,9 +738,6 @@ bool tal_resize_(tal_t **ctxp, size_t size, size_t count) if (notifiers) notify(t, TAL_NOTIFY_MOVE, from_tal_hdr(old_t)); } - len = find_property(t, LENGTH); - if (len) - len->count = count; if (notifiers) notify(t, TAL_NOTIFY_RESIZE, (void *)size); @@ -715,26 +747,26 @@ bool tal_resize_(tal_t **ctxp, size_t size, size_t count) bool tal_expand_(tal_t **ctxp, const void *src, size_t size, size_t count) { struct length *l; + size_t old_count; bool ret = false; l = find_property(debug_tal(to_tal_hdr(*ctxp)), LENGTH); + old_count = l->count; /* Check for additive overflow */ - if (l->count + count < count) { + if (old_count + count < count) { call_error("dup size overflow"); goto out; } /* Don't point src inside thing we're expanding! */ assert(src < *ctxp - || (char *)src >= (char *)(*ctxp) + (size * l->count)); + || (char *)src >= (char *)(*ctxp) + (size * old_count)); - /* Note: updates l->count. */ - if (!tal_resize_(ctxp, size, l->count + count)) + if (!tal_resize_(ctxp, size, old_count + count)) goto out; - memcpy((char *)*ctxp + size * (l->count - count), - src, count * size); + memcpy((char *)*ctxp + size * old_count, src, count * size); ret = true; out: diff --git a/ccan/tal/test/run-count.c b/ccan/tal/test/run-count.c index 0b64b887..91b020dc 100644 --- a/ccan/tal/test/run-count.c +++ b/ccan/tal/test/run-count.c @@ -2,32 +2,85 @@ #include #include +static bool move; +#define ALIGN (sizeof(void *)*2) + +static void *my_alloc(size_t len) +{ + char *ret = malloc(len + ALIGN); + memcpy(ret, &len, sizeof(len)); + return ret + ALIGN; +} + +static void my_free(void *p) +{ + if (p) + free((char *)p - ALIGN); +} + +static void *my_realloc(void *old, size_t new_size) +{ + char *ret; + + /* Test what happens if we always move */ + if (move) { + size_t old_size = *(size_t *)((char *)old - ALIGN); + ret = my_alloc(new_size); + memcpy(ret, old, old_size > new_size ? new_size : old_size); + my_free(old); + } else { + ret = realloc((char *)old - ALIGN, new_size + ALIGN); + memcpy(ret, &new_size, sizeof(new_size)); + ret += ALIGN; + } + return ret; +} + int main(void) { char *p1, *p2; + unsigned int i; + + tal_set_backend(my_alloc, my_realloc, my_free, NULL); + + plan_tests(19 * 3); + + for (i = 0; i < 3; i++) { + move = i; + + p1 = tal(NULL, char); + ok1(p1); + ok1(tal_count(p1) == 0); - plan_tests(12); - - p1 = tal(NULL, char); - ok1(p1); - ok1(tal_count(p1) == 0); - - p2 = tal_arr(p1, char, 1); - ok1(p2); - ok1(tal_count(p2) == 1); - ok1(tal_resize(&p2, 2)); - ok1(tal_count(p2) == 2); - ok1(tal_check(NULL, NULL)); - tal_free(p2); - - p2 = tal_arrz(p1, char, 7); - ok1(p2); - ok1(tal_count(p2) == 7); - ok1(tal_resize(&p2, 0)); - ok1(tal_count(p2) == 0); - ok1(tal_check(NULL, NULL)); - tal_free(p2); - tal_free(p1); + p2 = tal_arr(p1, char, 1); + ok1(p2); + ok1(tal_count(p2) == 1); + ok1(tal_resize(&p2, 2)); + ok1(tal_count(p2) == 2); + ok1(tal_check(NULL, NULL)); + tal_free(p2); + /* Resize twice. */ + p2 = tal_arrz(p1, char, 7); + ok1(p2); + ok1(tal_count(p2) == 7); + ok1(tal_check(NULL, NULL)); + tal_resize(&p2, 20); + ok1(p2); + ok1(tal_check(NULL, NULL)); + ok1(tal_count(p2) == 20); + /* Tickles non-moving logic, as we do not update bounds. */ + if (i == 2) + move = false; + tal_resize(&p2, 300); + ok1(p2); + ok1(tal_check(NULL, NULL)); + ok1(tal_count(p2) == 300); + ok1(tal_resize(&p2, 0)); + ok1(tal_count(p2) == 0); + ok1(tal_check(NULL, NULL)); + tal_free(p2); + tal_free(p1); + } return exit_status(); } -- 2.39.2