diff options
author | Vadim Bendebury <vbendeb@chromium.org> | 2016-12-14 21:31:25 -0800 |
---|---|---|
committer | chrome-bot <chrome-bot@chromium.org> | 2017-01-05 21:13:09 -0800 |
commit | 32b064108a94fa163b5e9f9aef2b85615c68ee1d (patch) | |
tree | e5cd6fe1bf84f555d5aa32f7ab970eb9001f827e /common | |
parent | 02d9c311ec93b3dc87f8c600b9f3653e3b13009a (diff) | |
download | chrome-ec-32b064108a94fa163b5e9f9aef2b85615c68ee1d.tar.gz |
common: introduce malloc/free implementation
The new code allows to replace the existing one buffer at a time
shared memory facility with a malloc/free implementation. A new
configuration option is being provided (CONFIG_MALLOC).
The names of functions allocating and freeing memory are not being
changed to allow to switch between the two implementations seamlessly.
A double linked list of buffers is used to keep track of free and
allocated memory. During initialization the entire free memory block
is considered a single free buffer. No allocations/frees are allowed
from within interrupts. The control structures are protected by a
semaphore, so allocate and free invocation could be blocking.
A test is added which randomly allocates and frees memory, continuing
until all branches in the allocate and free functions are taken.
BUG=chrome-os-partner:
TEST=make buildall -j succeeds, which includes testing the new
malloc/free implementation.
Change-Id: I5e71c0190c6c247ec73bb459f66a6d7a06e3d248
Signed-off-by: Vadim Bendebury <vbendeb@chromium.org>
Reviewed-on: https://chromium-review.googlesource.com/420466
Reviewed-by: Randall Spangler <rspangler@chromium.org>
Diffstat (limited to 'common')
-rw-r--r-- | common/build.mk | 8 | ||||
-rw-r--r-- | common/shmalloc.c | 389 |
2 files changed, 396 insertions, 1 deletions
diff --git a/common/build.mk b/common/build.mk index df17dd0f22..02541536c7 100644 --- a/common/build.mk +++ b/common/build.mk @@ -40,7 +40,7 @@ common-$(CONFIG_CHARGER_V2)+=charge_state_v2.o common-$(CONFIG_CMD_I2CWEDGE)+=i2c_wedge.o common-$(CONFIG_COMMON_GPIO)+=gpio.o gpio_commands.o common-$(CONFIG_COMMON_PANIC_OUTPUT)+=panic_output.o -common-$(CONFIG_COMMON_RUNTIME)+=hooks.o main.o system.o shared_mem.o +common-$(CONFIG_COMMON_RUNTIME)+=hooks.o main.o system.o common-$(CONFIG_COMMON_TIMER)+=timer.o common-$(CONFIG_CRC8)+= crc8.o common-$(CONFIG_DEVICE_STATE)+=device_state.o @@ -114,6 +114,12 @@ common-$(HAS_TASK_LIGHTBAR)+=lb_common.o lightbar.o common-$(HAS_TASK_MOTIONSENSE)+=motion_sense.o common-$(HAS_TASK_TPM)+=tpm_registers.o +ifeq ($(CONFIG_MALLOC),y) +common-$(CONFIG_COMMON_RUNTIME)+=shmalloc.o +else +common-$(CONFIG_COMMON_RUNTIME)+=shared_mem.o +endif + ifeq ($(CTS_MODULE),) common-$(TEST_BUILD)+=test_util.o else diff --git a/common/shmalloc.c b/common/shmalloc.c new file mode 100644 index 0000000000..6d3d4c728f --- /dev/null +++ b/common/shmalloc.c @@ -0,0 +1,389 @@ +/* + * Copyright 2016 The Chromium OS Authors. All rights reserved. + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ + +/* Malloc/free memory module for Chrome EC */ +#include <stdint.h> + +#include "common.h" +#include "hooks.h" +#include "link_defs.h" +#include "shared_mem.h" +#include "system.h" +#include "task.h" +#include "util.h" + +static struct mutex shmem_lock; + +#ifndef TEST_BUILD +#define set_map_bit(x) +#define TEST_GLOBAL static +#else +#define TEST_GLOBAL +#endif + +/* + * At the beginning there is a single free memory chunk which includes all + * memory available in the system. It then gets fragmented/defragmented based + * on actual allocations/releases. + */ +TEST_GLOBAL struct shm_buffer *free_buf_chain; + +/* At the beginning there is no allocated buffers */ +TEST_GLOBAL struct shm_buffer *allocced_buf_chain; + +/* The size of the biggest ever allocated buffer. */ +static int max_allocated_size; + +static void shared_mem_init(void) +{ + /* + * Use all the RAM we can. The shared memory buffer is the last thing + * allocated from the start of RAM, so we can use everything up to the + * jump data at the end of RAM. + */ + free_buf_chain = (struct shm_buffer *)__shared_mem_buf; + free_buf_chain->next_buffer = NULL; + free_buf_chain->prev_buffer = NULL; + free_buf_chain->buffer_size = system_usable_ram_end() - + (uintptr_t)__shared_mem_buf; +} +DECLARE_HOOK(HOOK_INIT, shared_mem_init, HOOK_PRIO_FIRST); + +/* Called with the mutex lock acquired. */ +static void do_release(struct shm_buffer *ptr) +{ + struct shm_buffer *pfb; + struct shm_buffer *top; + size_t released_size; + + /* Take the buffer out of the allocated buffers chain. */ + if (ptr == allocced_buf_chain) { + if (ptr->next_buffer) { + set_map_bit(1 << 20); + ptr->next_buffer->prev_buffer = NULL; + } else { + set_map_bit(1 << 21); + } + allocced_buf_chain = ptr->next_buffer; + } else { + /* + * Saninty check: verify that the buffer is in the allocated + * buffers chain. + */ + for (pfb = allocced_buf_chain->next_buffer; + pfb; + pfb = pfb->next_buffer) + if (pfb == ptr) + break; + if (!pfb) + return; + + ptr->prev_buffer->next_buffer = ptr->next_buffer; + if (ptr->next_buffer) { + set_map_bit(1 << 22); + ptr->next_buffer->prev_buffer = ptr->prev_buffer; + } else { + set_map_bit(1 << 23); + } + } + + /* + * Let's bring the released buffer back into the fold. Cache its size + * for quick reference. + */ + released_size = ptr->buffer_size; + if (!free_buf_chain) { + /* + * All memory had been allocated - this buffer is going to be + * the only available free space. + */ + set_map_bit(1 << 0); + free_buf_chain = ptr; + free_buf_chain->buffer_size = released_size; + free_buf_chain->next_buffer = NULL; + free_buf_chain->prev_buffer = NULL; + return; + } + + if (ptr < free_buf_chain) { + /* + * Insert this buffer in the beginning of the chain, possibly + * merging it with the first buffer of the chain. + */ + pfb = (struct shm_buffer *)((uintptr_t)ptr + released_size); + if (pfb == free_buf_chain) { + set_map_bit(1 << 1); + /* Merge the two buffers. */ + ptr->buffer_size = free_buf_chain->buffer_size + + released_size; + ptr->next_buffer = + free_buf_chain->next_buffer; + } else { + set_map_bit(1 << 2); + ptr->buffer_size = released_size; + ptr->next_buffer = free_buf_chain; + free_buf_chain->prev_buffer = ptr; + } + if (ptr->next_buffer) { + set_map_bit(1 << 3); + ptr->next_buffer->prev_buffer = ptr; + } else { + set_map_bit(1 << 4); + } + ptr->prev_buffer = NULL; + free_buf_chain = ptr; + return; + } + + /* + * Need to merge the new free buffer into the existing chain. Find a + * spot for it, it should be above the highest address buffer which is + * still below the new one. + */ + pfb = free_buf_chain; + while (pfb->next_buffer && (pfb->next_buffer < ptr)) + pfb = pfb->next_buffer; + + top = (struct shm_buffer *)((uintptr_t)pfb + pfb->buffer_size); + if (top == ptr) { + /* + * The returned buffer is adjacent to an existing free buffer, + * below it, merge the two buffers. + */ + pfb->buffer_size += released_size; + + /* + * Is the returned buffer the exact gap between two free + * buffers? + */ + top = (struct shm_buffer *)((uintptr_t)ptr + released_size); + if (top == pfb->next_buffer) { + /* Yes, it is. */ + pfb->buffer_size += pfb->next_buffer->buffer_size; + pfb->next_buffer = + pfb->next_buffer->next_buffer; + if (pfb->next_buffer) { + set_map_bit(1 << 5); + pfb->next_buffer->prev_buffer = pfb; + } else { + set_map_bit(1 << 6); + } + } + return; + } + + top = (struct shm_buffer *)((uintptr_t)ptr + released_size); + if (top == pfb->next_buffer) { + /* The new buffer is adjacent with the one right above it. */ + set_map_bit(1 << 7); + ptr->buffer_size = released_size + + pfb->next_buffer->buffer_size; + ptr->next_buffer = pfb->next_buffer->next_buffer; + } else { + /* Just include the new free buffer into the chain. */ + set_map_bit(1 << 8); + ptr->next_buffer = pfb->next_buffer; + ptr->buffer_size = released_size; + } + ptr->prev_buffer = pfb; + pfb->next_buffer = ptr; + if (ptr->next_buffer) { + set_map_bit(1 << 9); + ptr->next_buffer->prev_buffer = ptr; + } else { + set_map_bit(1 << 10); + } +} + +/* Called with the mutex lock acquired. */ +static int do_acquire(int size, struct shm_buffer **dest_ptr) +{ + int headroom = 0x10000000; /* we'll never have this much. */ + struct shm_buffer *pfb; + struct shm_buffer *candidate = 0; + + /* To keep things simple let's align the size. */ + size = (size + sizeof(int) - 1) & ~(sizeof(int) - 1); + + /* And let's allocate room to fit the buffer header. */ + size += sizeof(struct shm_buffer); + + pfb = free_buf_chain; + while (pfb) { + if ((pfb->buffer_size > size) && + ((pfb->buffer_size - size) < headroom)) { + /* this is a new candidate. */ + headroom = pfb->buffer_size - size; + candidate = pfb; + } + pfb = pfb->next_buffer; + } + + if (!candidate) { + set_map_bit(1 << 11); + return EC_ERROR_BUSY; + } + + *dest_ptr = candidate; + + /* Now let's take the candidate out of the free buffer chain. */ + if (headroom <= sizeof(struct shm_buffer)) { + /* + * The entire buffer should be allocated, there is no need to + * re-define its tail as a new free buffer. + */ + if (candidate == free_buf_chain) { + /* + * The next buffer becomes the head of the free buffer + * chain. + */ + free_buf_chain = candidate->next_buffer; + if (free_buf_chain) { + set_map_bit(1 << 12); + free_buf_chain->prev_buffer = 0; + } else { + set_map_bit(1 << 13); + } + } else { + candidate->prev_buffer->next_buffer = + candidate->next_buffer; + if (candidate->next_buffer) { + set_map_bit(1 << 14); + candidate->next_buffer->prev_buffer = + candidate->prev_buffer; + } else { + set_map_bit(1 << 15); + } + } + return EC_SUCCESS; + } + + candidate->buffer_size = size; + + /* Candidate's tail becomes a new free buffer. */ + pfb = (struct shm_buffer *)((uintptr_t)candidate + size); + pfb->buffer_size = headroom; + pfb->next_buffer = candidate->next_buffer; + pfb->prev_buffer = candidate->prev_buffer; + + if (pfb->next_buffer) { + set_map_bit(1 << 16); + pfb->next_buffer->prev_buffer = pfb; + } else { + set_map_bit(1 << 17); + } + + if (candidate == free_buf_chain) { + set_map_bit(1 << 18); + free_buf_chain = pfb; + } else { + set_map_bit(1 << 19); + pfb->prev_buffer->next_buffer = pfb; + } + return EC_SUCCESS; +} + +int shared_mem_size(void) +{ + struct shm_buffer *pfb; + size_t max_available = 0; + + mutex_lock(&shmem_lock); + + /* Find the maximum available buffer size. */ + pfb = free_buf_chain; + while (pfb) { + if (pfb->buffer_size > max_available) + max_available = pfb->buffer_size; + pfb = pfb->next_buffer; + } + + mutex_unlock(&shmem_lock); + return max_available; +} + +int shared_mem_acquire(int size, char **dest_ptr) +{ + int rv; + struct shm_buffer *new_buf; + + if (in_interrupt_context()) + return EC_ERROR_INVAL; + + if (!free_buf_chain) + return EC_ERROR_BUSY; + + mutex_lock(&shmem_lock); + rv = do_acquire(size, &new_buf); + if (rv == EC_SUCCESS) { + new_buf->next_buffer = allocced_buf_chain; + new_buf->prev_buffer = NULL; + if (allocced_buf_chain) + allocced_buf_chain->prev_buffer = new_buf; + + allocced_buf_chain = new_buf; + + *dest_ptr = (void *)(new_buf + 1); + + if (size > max_allocated_size) + max_allocated_size = size; + } + mutex_unlock(&shmem_lock); + + return rv; +} + +void shared_mem_release(void *ptr) +{ + if (in_interrupt_context()) + return; + + mutex_lock(&shmem_lock); + do_release((struct shm_buffer *)ptr - 1); + mutex_unlock(&shmem_lock); +} + +#ifdef CONFIG_CMD_SHMEM + +static int command_shmem(int argc, char **argv) +{ + size_t allocated_size; + size_t free_size; + size_t max_free; + struct shm_buffer *buf; + + allocated_size = free_size = max_free = 0; + + mutex_lock(&shmem_lock); + + for (buf = free_buf_chain; buf; buf = free_buf_chain->next_buffer) { + size_t buf_room; + + buf_room = buf->buffer_size; + + free_size += buf_room; + if (buf_room > max_free) + max_free = buf_room; + } + + for (buf = allocced_buf_chain; buf; + buf = allocced_buf_chain->next_buffer) + allocated_size += buf->buffer_size; + + mutex_unlock(&shmem_lock); + + ccprintf("Total: %6d\n", allocated_size + free_size); + ccprintf("Allocated: %6d\n", allocated_size); + ccprintf("Free: %6d\n", free_size); + ccprintf("Max free buf: %6d\n", max_free); + ccprintf("Max allocated: %6d\n", max_allocated_size); + return EC_SUCCESS; +} +DECLARE_SAFE_CONSOLE_COMMAND(shmem, command_shmem, + NULL, + "Print shared memory stats"); + +#endif /* CONFIG_CMD_SHMEM ^^^^^^^ defined */ |