diff options
Diffstat (limited to 'src/stack-allocator.c')
| -rw-r--r-- | src/stack-allocator.c | 354 |
1 files changed, 0 insertions, 354 deletions
diff --git a/src/stack-allocator.c b/src/stack-allocator.c deleted file mode 100644 index 55aeda9a..00000000 --- a/src/stack-allocator.c +++ /dev/null @@ -1,354 +0,0 @@ -/* - * Copyright 2016 WebAssembly Community Group participants - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include "stack-allocator.h" - -#include <assert.h> -#include <stdint.h> -#include <stdio.h> -#include <string.h> - -#define TRACE_ALLOCATOR 0 - -#if TRACE_ALLOCATOR -#define TRACEF(...) fprintf(stderr, __VA_ARGS__) -#else -#define TRACEF(...) -#endif - -#if WABT_STACK_ALLOCATOR_STATS -#include <stdio.h> -#endif /* WABT_STACK_ALLOCATOR_STATS */ - -#define CHUNK_ALIGN 8 -#define CHUNK_SIZE (1024 * 1024) -#define CHUNK_MAX_AVAIL (CHUNK_SIZE - sizeof(WabtStackAllocatorChunk)) - -typedef struct StackAllocatorMark { - WabtStackAllocatorChunk* chunk; - void* chunk_current; - void* last_allocation; -} StackAllocatorMark; - -#ifndef NDEBUG -static WabtBool is_power_of_two(uint32_t x) { - return x && ((x & (x - 1)) == 0); -} -#endif /* NDEBUG */ - -static void* align_up(void* p, size_t align) { - return (void*)(((intptr_t)p + align - 1) & ~(align - 1)); -} - -static WabtBool allocation_in_chunk(WabtStackAllocatorChunk* chunk, void* p) { - return p >= (void*)chunk && p < chunk->end; -} - -static WabtStackAllocatorChunk* allocate_chunk( - WabtStackAllocator* stack_allocator, - size_t max_avail, - const char* file, - int line) { - assert(max_avail < SIZE_MAX - sizeof(WabtStackAllocatorChunk)); - size_t real_size = max_avail + sizeof(WabtStackAllocatorChunk); - /* common case of allocating a chunk of exactly CHUNK_SIZE */ - if (real_size == CHUNK_SIZE) { - if (stack_allocator->next_free) { - WabtStackAllocatorChunk* chunk = stack_allocator->next_free; - stack_allocator->next_free = stack_allocator->next_free->next_free; - return chunk; - } - } - - WabtStackAllocatorChunk* chunk = - wabt_alloc(stack_allocator->fallback, real_size, CHUNK_ALIGN); - if (!chunk) { - if (stack_allocator->has_jmpbuf) - longjmp(stack_allocator->jmpbuf, 1); - WABT_FATAL("%s:%d: memory allocation failed\n", file, line); - } - /* use the same allocation for the WabtStackAllocatorChunk and its data. + 1 - * skips over the WabtStackAllocatorChunk */ - chunk->start = chunk + 1; - chunk->current = chunk->start; - chunk->end = (void*)((intptr_t)chunk->start + max_avail); - chunk->prev = NULL; -#if WABT_STACK_ALLOCATOR_STATS - stack_allocator->chunk_alloc_count++; - stack_allocator->total_chunk_bytes += CHUNK_SIZE; -#endif /* WABT_STACK_ALLOCATOR_STATS */ - return chunk; -} - -static void* stack_alloc(WabtAllocator* allocator, - size_t size, - size_t align, - const char* file, - int line) { - WabtStackAllocator* stack_allocator = (WabtStackAllocator*)allocator; - assert(is_power_of_two(align)); - WabtStackAllocatorChunk* chunk = stack_allocator->last; - assert(size < SIZE_MAX - align + 1); - size_t alloc_size = size + align - 1; - void* result; - if (alloc_size >= CHUNK_MAX_AVAIL) { - chunk = allocate_chunk(stack_allocator, alloc_size, file, line); - result = align_up(chunk->current, align); - assert((void*)((intptr_t)result + size) <= chunk->end); - chunk->current = chunk->end; - /* thread this chunk before first. There's no available space, so it's not - worth considering. */ - stack_allocator->first->prev = chunk; - stack_allocator->first = chunk; - } else { - assert(chunk); - - chunk->current = align_up(chunk->current, align); - void* new_current = (void*)((intptr_t)chunk->current + size); - if (new_current < chunk->end) { - result = chunk->current; - chunk->current = new_current; - } else { - chunk = allocate_chunk(stack_allocator, CHUNK_MAX_AVAIL, file, line); - chunk->prev = stack_allocator->last; - stack_allocator->last = chunk; - chunk->current = align_up(chunk->current, align); - result = chunk->current; - chunk->current = (void*)((intptr_t)chunk->current + size); - assert(chunk->current <= chunk->end); - } - - stack_allocator->last_allocation = result; - } - -#if TRACE_ALLOCATOR - if (file) { - TRACEF("%s:%d: stack_alloc(%" PRIzd ", align=%" PRIzd ") => %p\n", file, - line, size, align, result); - } -#endif /* TRACE_ALLOCATOR */ - -#if WABT_STACK_ALLOCATOR_STATS - stack_allocator->alloc_count++; - stack_allocator->total_alloc_bytes += size; -#endif /* WABT_STACK_ALLOCATOR_STATS */ - return result; -} - -static void* stack_realloc(WabtAllocator* allocator, - void* p, - size_t size, - size_t align, - const char* file, - int line) { - if (!p) - return stack_alloc(allocator, size, align, file, line); - - WabtStackAllocator* stack_allocator = (WabtStackAllocator*)allocator; - /* TODO(binji): optimize */ - WabtStackAllocatorChunk* chunk = stack_allocator->last; - while (chunk) { - if (allocation_in_chunk(chunk, p)) - break; - chunk = chunk->prev; - } - - assert(chunk); - void* result = stack_alloc(allocator, size, align, NULL, 0); - -#if TRACE_ALLOCATOR - if (file) { - TRACEF("%s:%d: stack_realloc(%p, %" PRIzd ", align=%" PRIzd ") => %p\n", - file, line, p, size, align, result); - } -#endif /* TRACE_ALLOCATOR */ - - /* We know that the previously allocated data was at most extending from |p| - to the end of the chunk. So we can copy at most that many bytes, or the - new size, whichever is less. Use memmove because the regions may be - overlapping. */ - size_t old_max_size = (size_t)chunk->end - (size_t)p; - size_t copy_size = size > old_max_size ? old_max_size : size; - memmove(result, p, copy_size); -#if WABT_STACK_ALLOCATOR_STATS - /* count this is as a realloc, not an alloc */ - stack_allocator->alloc_count--; - stack_allocator->realloc_count++; - stack_allocator->total_alloc_bytes -= size; - stack_allocator->total_realloc_bytes += size; -#endif /* WABT_STACK_ALLOCATOR_STATS */ - return result; -} - -static void stack_free(WabtAllocator* allocator, - void* p, - const char* file, - int line) { - if (!p) - return; - - TRACEF("%s:%d: stack_free(%p)\n", file, line, p); - WabtStackAllocator* stack_allocator = (WabtStackAllocator*)allocator; - -#if WABT_STACK_ALLOCATOR_STATS - stack_allocator->free_count++; -#endif /* WABT_STACK_ALLOCATOR_STATS */ - - if (p != stack_allocator->last_allocation) - return; - - WabtStackAllocatorChunk* chunk = stack_allocator->last; - assert(allocation_in_chunk(chunk, p)); - chunk->current = p; -} - -static void stack_destroy(WabtAllocator* allocator) { - WabtStackAllocator* stack_allocator = (WabtStackAllocator*)allocator; - /* destroy the free chunks */ - WabtStackAllocatorChunk* chunk = stack_allocator->next_free; - while (chunk) { - WabtStackAllocatorChunk* next_free = chunk->next_free; - wabt_free(stack_allocator->fallback, chunk); - chunk = next_free; - } - - /* destroy the used chunks */ - chunk = stack_allocator->last; - while (chunk) { - WabtStackAllocatorChunk* prev = chunk->prev; - wabt_free(stack_allocator->fallback, chunk); - chunk = prev; - } -} - -static WabtAllocatorMark stack_mark(WabtAllocator* allocator) { - WabtStackAllocator* stack_allocator = (WabtStackAllocator*)allocator; - - /* allocate the space for the mark, but copy the current stack state now, so - * when we reset we reset before the mark was allocated */ - StackAllocatorMark mark; - mark.chunk = stack_allocator->last; - mark.chunk_current = mark.chunk->current; - mark.last_allocation = stack_allocator->last_allocation; - - StackAllocatorMark* allocated_mark = stack_alloc( - allocator, sizeof(StackAllocatorMark), WABT_DEFAULT_ALIGN, NULL, 0); -#if WABT_STACK_ALLOCATOR_STATS - /* don't count this allocation */ - stack_allocator->alloc_count--; - stack_allocator->total_alloc_bytes -= sizeof(StackAllocatorMark); -#endif /* WABT_STACK_ALLOCATOR_STATS */ - - *allocated_mark = mark; - return allocated_mark; -} - -static void stack_reset_to_mark(WabtAllocator* allocator, - WabtAllocatorMark mark) { - WabtStackAllocator* stack_allocator = (WabtStackAllocator*)allocator; - StackAllocatorMark* stack_mark = (StackAllocatorMark*)mark; - WabtStackAllocatorChunk* chunk = stack_allocator->last; - while (chunk && chunk != stack_mark->chunk) { - WabtStackAllocatorChunk* prev = chunk->prev; - /* reset this chunk for future use, and thread it into the free list */ - chunk->current = chunk->start; - chunk->next_free = stack_allocator->next_free; - stack_allocator->next_free = chunk; - chunk = prev; - } - - assert(chunk == stack_mark->chunk); - stack_allocator->last = chunk; - chunk->current = stack_mark->chunk_current; - stack_allocator->last_allocation = stack_mark->last_allocation; -} - -#if WABT_STACK_ALLOCATOR_STATS -static const char* human_readable(size_t count) { - /* printing a size_t in decimal requires ceil(sizeof(size_t) * 8 / log2(10)) - * characters. We want to add one comma for each group of three digits, so - * the total number of characters needed is 4/3 multiplied by that value. For - * a 64-bit size_t, this comes out to 27 (including the null-terminator). */ - static char buffer[27]; - int next_comma_in = 3; - memset(buffer, ' ', sizeof(buffer)); - char* p = &buffer[sizeof(buffer) - 1]; - *p-- = '\0'; - if (count) { - while (count) { - if (next_comma_in == 0) { - *p-- = ','; - next_comma_in = 3; - } - assert(p >= buffer); - size_t digit = count % 10; - *p-- = '0' + digit; - count /= 10; - next_comma_in--; - } - } else { - *p-- = '0'; - } - return buffer; -} -#endif /* WABT_STACK_ALLOCATOR_STATS */ - -static void stack_print_stats(WabtAllocator* allocator) { -#if WABT_STACK_ALLOCATOR_STATS -#define VALUE(name) human_readable(stack_allocator->name) - WabtStackAllocator* stack_allocator = (WabtStackAllocator*)allocator; - printf("STACK ALLOCATOR STATS:\n"); - printf("===============================================\n"); - printf("chunk_alloc_count: %s\n", VALUE(chunk_alloc_count)); - printf("alloc_count: %s\n", VALUE(alloc_count)); - printf("realloc_count: %s\n", VALUE(realloc_count)); - printf("free_count: %s\n", VALUE(free_count)); - printf("total_chunk_bytes: %s\n", VALUE(total_chunk_bytes)); - printf("total_alloc_bytes: %s\n", VALUE(total_alloc_bytes)); - printf("total_realloc_bytes: %s\n", VALUE(total_realloc_bytes)); -#undef VALUE -#endif /* WABT_STACK_ALLOCATOR_STATS */ -} - -static int stack_setjmp_handler(WabtAllocator* allocator) { - WabtStackAllocator* stack_allocator = (WabtStackAllocator*)allocator; - stack_allocator->has_jmpbuf = WABT_TRUE; - return setjmp(stack_allocator->jmpbuf); -} - -WabtResult wabt_init_stack_allocator(WabtStackAllocator* stack_allocator, - WabtAllocator* fallback) { - WABT_ZERO_MEMORY(*stack_allocator); - stack_allocator->allocator.alloc = stack_alloc; - stack_allocator->allocator.realloc = stack_realloc; - stack_allocator->allocator.free = stack_free; - stack_allocator->allocator.destroy = stack_destroy; - stack_allocator->allocator.mark = stack_mark; - stack_allocator->allocator.reset_to_mark = stack_reset_to_mark; - stack_allocator->allocator.print_stats = stack_print_stats; - stack_allocator->allocator.setjmp_handler = stack_setjmp_handler; - stack_allocator->fallback = fallback; - - WabtStackAllocatorChunk* chunk = - allocate_chunk(stack_allocator, CHUNK_MAX_AVAIL, __FILE__, __LINE__); - chunk->prev = NULL; - stack_allocator->first = stack_allocator->last = chunk; - return WABT_OK; -} - -void wabt_destroy_stack_allocator(WabtStackAllocator* stack_allocator) { - stack_destroy((WabtAllocator*)stack_allocator); -} |