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>

8 files changed, 764 insertions, 7 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 */
diff --git a/include/config.h b/include/config.h
index ff23a7ec4e..2362103856 100644
--- a/include/config.h
+++ b/include/config.h
@@ -1540,6 +1540,9 @@
 /* Use Link-Time Optimizations to try to reduce the firmware code size */
 #undef CONFIG_LTO
 
+/* Provide rudimentary malloc/free like services for shared memory. */
+#undef CONFIG_MALLOC
+
 /* Need for a math library */
 #undef CONFIG_MATH_UTIL
 
diff --git a/include/shared_mem.h b/include/shared_mem.h
index f7b8bcbccb..b99cdb1341 100644
--- a/include/shared_mem.h
+++ b/include/shared_mem.h
@@ -18,11 +18,7 @@
 #define __CROS_EC_SHARED_MEM_H
 
 #include "common.h"
-
-/**
- * Initializes the module.
- */
-int shared_mem_init(void);
+#include <stddef.h>
 
 /**
  * Returns the maximum amount of shared memory which can be acquired, in
@@ -30,9 +26,14 @@ int shared_mem_init(void);
  */
 int shared_mem_size(void);
 
-/**
+/*
  * Acquires a shared memory area of the requested size in bytes.
  *
+ * Doing a sysjump between images will corrupt and/or erase shared memory as
+ * jump tags are added and .bss is reinitialized. Due to the way jump tags are
+ * added to the end of RAM, shared memory must not be allocated, accessed, or
+ * freed after the start of a sysjump (for example, in HOOK_SYSJUMP).
+ *
  * @param size		Number of bytes requested
  * @param dest_ptr	If successful, set on return to the start of the
  *			granted memory buffer.
@@ -47,4 +48,32 @@ int shared_mem_acquire(int size, char **dest_ptr);
  */
 void shared_mem_release(void *ptr);
 
+/*
+ * This structure is allocated at the base of the free memory chunk and every
+ * allocated buffer.
+ */
+struct shm_buffer {
+	struct shm_buffer *next_buffer;
+	struct shm_buffer *prev_buffer;
+	size_t buffer_size;
+};
+
+#ifdef TEST_BUILD
+
+/*
+ * When in test mode, all possible paths in the allocation/free functions set
+ * unique bits in an integer bitmap.
+ *
+ * The test function generates random allocation and free requests and
+ * monitors the bitmap until all bits have been set, which indicates that all
+ * possible paths have been executed.
+ */
+
+#define MAX_MASK_BIT 24
+#define ALL_PATHS_MASK ((1 << (MAX_MASK_BIT + 1)) - 1)
+void set_map_bit(uint32_t mask);
+extern struct shm_buffer *free_buf_chain;
+extern struct shm_buffer *allocced_buf_chain;
+#endif
+
 #endif  /* __CROS_EC_SHARED_MEM_H */
diff --git a/test/build.mk b/test/build.mk
index f1083628fe..19fa51f5b0 100644
--- a/test/build.mk
+++ b/test/build.mk
@@ -66,6 +66,7 @@ test-list-host += rsa
 test-list-host += rsa3
 test-list-host += sbs_charging
 test-list-host += sbs_charging_v2
+test-list-host += shmalloc
 test-list-host += system
 test-list-host += thermal
 test-list-host += timer_dos
@@ -107,6 +108,7 @@ rsa-y=rsa.o
 rsa3-y=rsa.o
 sbs_charging-y=sbs_charging.o
 sbs_charging_v2-y=sbs_charging_v2.o
+shmalloc-y=shmalloc.o
 stress-y=stress.o
 system-y=system.o
 thermal-y=thermal.o
diff --git a/test/shmalloc.c b/test/shmalloc.c
new file mode 100644
index 0000000000..d96579c275
--- /dev/null
+++ b/test/shmalloc.c
@@ -0,0 +1,305 @@
+/*
+ * 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.
+ */
+
+#include <stddef.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "common.h"
+#include "compile_time_macros.h"
+#include "console.h"
+#include "link_defs.h"
+#include "shared_mem.h"
+#include "test_util.h"
+
+/*
+ * Total size of memory in the malloc pool (shared between free and allocated
+ * buffers.
+ */
+static int total_size;
+
+/*
+ * Number of randomized allocation/free attempts, large enough to execute all
+ * branches in the malloc/free module.
+ */
+static int counter = 500000;
+
+/*
+ * A good random number generator approximation. Guaranteed to generate the
+ * same sequence on all test runs.
+ */
+static uint32_t next = 127;
+static uint32_t myrand(void)
+{
+	next = next * 1103515245 + 12345;
+	return ((uint32_t)(next/65536) % 32768);
+}
+
+/* Keep track of buffers allocated by the test function. */
+static struct {
+	void *buf;
+	size_t buffer_size;
+} allocations[12];  /* Up to 12 buffers could be allocated concurrently. */
+
+/*
+ * Verify that allocated and free buffers do not overlap, and that our and
+ * malloc's ideas of the number of allocated buffers match.
+ */
+
+static int check_for_overlaps(void)
+{
+	int i;
+	int allocation_match;
+	int allocations_count, allocated_count;
+
+	allocations_count = allocated_count = 0;
+	for (i = 0; i < ARRAY_SIZE(allocations); i++) {
+		struct shm_buffer *allocced_buf;
+
+		if (!allocations[i].buf)
+			continue;
+
+		/*
+		 * Indication of finding the allocated buffer in internal
+		 * malloc structures.
+		 */
+		allocation_match = 0;
+
+		/* number of buffers allocated by the test program. */
+		allocations_count++;
+
+		/*
+		 * Number of allocated buffers malloc knows about, calculated
+		 * multiple times to keep things simple.
+		 */
+		allocated_count = 0;
+		for (allocced_buf = allocced_buf_chain;
+		     allocced_buf;
+		     allocced_buf = allocced_buf->next_buffer) {
+			int allocated_size, allocation_size;
+
+			allocated_count++;
+			if (allocations[i].buf != (allocced_buf + 1))
+				continue;
+
+			allocated_size = allocced_buf->buffer_size;
+			allocation_size = allocations[i].buffer_size;
+
+			/*
+			 * Verify that size requested by the allocator matches
+			 * the value used by malloc, i.e. does not exceed the
+			 * allocated size and is no less than two buffer
+			 * structures lower (which can happen when the
+			 * requested size was rounded up to cover gaps smaller
+			 * than the buffer header structure size).
+			 */
+			if ((allocation_size > allocated_size) ||
+			    ((allocated_size - allocation_size) >=
+			     (2 * sizeof(struct shm_buffer) + sizeof(int)))) {
+				ccprintf("inconsistency: allocated (size %d)"
+					 " allocation %d(size %d)\n",
+					 allocated_size, i, allocation_size);
+				return 0;
+			}
+
+			if (allocation_match++) {
+				ccprintf("inconsistency: duplicated match\n");
+				return 0;
+			}
+		}
+		if (!allocation_match) {
+			ccprintf("missing match %p!\n", allocations[i].buf);
+			return 0;
+		}
+	}
+	if (allocations_count != allocated_count) {
+		ccprintf("count mismatch (%d != %d)!\n",
+			 allocations_count, allocated_count);
+		return 0;
+	}
+	return 1;
+}
+
+/*
+ * Verify that shared memory is in a consistent state, i.e. that there is no
+ * overlaps between allocated and free buffers, and that all memory is
+ * accounted for (is either allocated or available).
+ */
+
+static int shmem_is_ok(int line)
+{
+	int count = 0;
+	int running_size = 0;
+	struct shm_buffer *pbuf = free_buf_chain;
+
+	if (pbuf && pbuf->prev_buffer) {
+		ccprintf("Bad free buffer list start %p\n", pbuf);
+		goto bailout;
+	}
+
+	while (pbuf) {
+		struct shm_buffer *top;
+
+		running_size += pbuf->buffer_size;
+		if (count++ > 100)
+			goto bailout;  /* Is there a loop? */
+
+		top = (struct shm_buffer *)((uintptr_t)pbuf +
+					     pbuf->buffer_size);
+		if (pbuf->next_buffer) {
+			if (top >= pbuf->next_buffer) {
+				ccprintf("%s:%d"
+					 " - inconsistent buffer size at %p\n",
+					 __func__, __LINE__, pbuf);
+				goto bailout;
+			}
+			if (pbuf->next_buffer->prev_buffer != pbuf) {
+				ccprintf("%s:%d"
+					 " - inconsistent next buffer at %p\n",
+					 __func__, __LINE__, pbuf);
+				goto bailout;
+			}
+		}
+		pbuf = pbuf->next_buffer;
+	}
+
+	if (pbuf) { /* Must be a loop. */
+		ccprintf("Too many buffers in the chain\n");
+		goto bailout;
+	}
+
+	/* Make sure there were at least 5 buffers allocated at one point. */
+	if (count > 5)
+		set_map_bit(1 << 24);
+
+	/* Add allocated sizes. */
+	for (pbuf = allocced_buf_chain; pbuf; pbuf = pbuf->next_buffer)
+		running_size += pbuf->buffer_size;
+
+	if (total_size) {
+		if (total_size != running_size)
+			goto bailout;
+	} else {
+		/* Remember total size for future reference. */
+		total_size = running_size;
+	}
+
+	if (!check_for_overlaps())
+		goto bailout;
+
+	return 1;
+
+ bailout:
+	ccprintf("Line %d, counter %d. The list has been corrupted, "
+		 "total size %d, running size %d\n",
+		 line, counter, total_size, running_size);
+	return 0;
+}
+
+/*
+ * Bitmap used to keep track of branches taken by malloc/free routines. Once
+ * all bits in the 0..(MAX_MASK_BIT - 1) range are set, consider the test
+ * completed.
+ */
+static uint32_t test_map;
+
+void run_test(void)
+{
+	int index;
+	const int shmem_size = shared_mem_size();
+
+	while (counter--) {
+		char *shptr;
+		uint32_t r_data;
+
+		r_data = myrand();
+
+		if (!(counter % 50000))
+			ccprintf("%d\n", counter);
+
+		/*
+		 * If all bits we care about are set in the map - the test is
+		 * over.
+		 */
+		if ((test_map & ALL_PATHS_MASK) == ALL_PATHS_MASK) {
+			if (test_map & ~ALL_PATHS_MASK) {
+				ccprintf("Unexpected mask bits set: %x"
+					 ", counter %d\n",
+					 test_map & ~ALL_PATHS_MASK,
+					 counter);
+				test_fail();
+				return;
+			}
+			ccprintf("Done testing, counter at %d\n", counter);
+			test_pass();
+			return;
+		}
+
+		/* Pick a random allocation entry. */
+		index = r_data % ARRAY_SIZE(allocations);
+		if (allocations[index].buf) {
+			/*
+			 * If there is a buffer associated with the entry -
+			 * release it.
+			 */
+			shared_mem_release(allocations[index].buf);
+			allocations[index].buf = 0;
+			if (!shmem_is_ok(__LINE__)) {
+				test_fail();
+				return;
+			}
+		} else {
+			size_t alloc_size = r_data % (shmem_size);
+
+			/*
+			 * If the allocation entry is empty - allocate a
+			 * buffer of a random size up to max shared memory.
+			 */
+			if (shared_mem_acquire(alloc_size, &shptr) ==
+			    EC_SUCCESS) {
+				allocations[index].buf = (void *) shptr;
+				allocations[index].buffer_size = alloc_size;
+
+				/*
+				 * Make sure every allocated byte is
+				 * modified.
+				 */
+				while (alloc_size--)
+					shptr[alloc_size] =
+					shptr[alloc_size] ^ 0xff;
+
+				if (!shmem_is_ok(__LINE__)) {
+					test_fail();
+					return;
+				}
+			}
+		}
+	}
+
+	/*
+	 * The test is over, free all still allcated buffers, if any. Keep
+	 * verifying memory consistency after each free() invocation.
+	 */
+	for (index = 0; index < ARRAY_SIZE(allocations); index++)
+		if (allocations[index].buf) {
+			shared_mem_release(allocations[index].buf);
+			allocations[index].buf = NULL;
+			if (!shmem_is_ok(__LINE__)) {
+				test_fail();
+				return;
+			}
+		}
+
+	ccprintf("Did not pass all paths, map %x != %x\n",
+		 test_map, ALL_PATHS_MASK);
+	test_fail();
+}
+
+void set_map_bit(uint32_t mask)
+{
+	test_map |= mask;
+}
diff --git a/test/shmalloc.tasklist b/test/shmalloc.tasklist
new file mode 100644
index 0000000000..ab483e513f
--- /dev/null
+++ b/test/shmalloc.tasklist
@@ -0,0 +1,19 @@
+/*
+ * 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.
+ */
+
+/**
+ * List of enabled tasks in the priority order
+ *
+ * The first one has the lowest priority.
+ *
+ * For each task, use the macro TASK_TEST(n, r, d, s) where :
+ * 'n' in the name of the task
+ * 'r' in the main routine of the task
+ * 'd' in an opaque parameter passed to the routine at startup
+ * 's' is the stack size in bytes; must be a multiple of 8
+ */
+#define CONFIG_TEST_TASK_LIST
+
diff --git a/test/test_config.h b/test/test_config.h
index 8eddcb9714..61ba6b6db5 100644
--- a/test/test_config.h
+++ b/test/test_config.h
@@ -78,6 +78,10 @@ int board_discharge_on_ac(int enabled);
 #define I2C_PORT_CHARGER 0
 #endif
 
+#ifdef TEST_SHMALLOC
+#define CONFIG_MALLOC
+#endif
+
 #ifdef TEST_SBS_CHARGING_V2
 #define CONFIG_BATTERY_MOCK
 #define CONFIG_BATTERY_SMART