Add memory pool.
This is in preparation for replacing the existing allocator.
Change-Id: I3d6b01ee07be248f02336b8d7756883a9eeace85
diff --git a/inc/hf/mpool.h b/inc/hf/mpool.h
new file mode 100644
index 0000000..556fea9
--- /dev/null
+++ b/inc/hf/mpool.h
@@ -0,0 +1,37 @@
+/*
+ * Copyright 2018 Google LLC
+ *
+ * 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
+ *
+ * https://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.
+ */
+
+#pragma once
+
+#include <stdbool.h>
+#include <stddef.h>
+
+#include "hf/spinlock.h"
+
+struct mpool {
+ struct spinlock lock;
+ size_t entry_size;
+ struct mpool_chunk *chunk_list;
+ struct mpool_entry *entry_list;
+};
+
+void mpool_enable_locks(void);
+void mpool_init(struct mpool *p, size_t entry_size);
+void mpool_init_from(struct mpool *p, struct mpool *from);
+bool mpool_add_chunk(struct mpool *p, void *begin, size_t size);
+void *mpool_alloc(struct mpool *p);
+void *mpool_alloc_contiguous(struct mpool *p, size_t count, size_t align);
+void mpool_free(struct mpool *p, void *ptr);
diff --git a/src/BUILD.gn b/src/BUILD.gn
index 83621a5..e768245 100644
--- a/src/BUILD.gn
+++ b/src/BUILD.gn
@@ -51,6 +51,7 @@
"cpu.c",
"fdt_handler.c",
"mm.c",
+ "mpool.c",
"vm.c",
]
@@ -114,6 +115,7 @@
"fdt_handler_test.cc",
"fdt_test.cc",
"mm_test.cc",
+ "mpool_test.cc",
]
sources += [ "layout_fake.c" ]
cflags_cc = [
diff --git a/src/mpool.c b/src/mpool.c
new file mode 100644
index 0000000..21bce22
--- /dev/null
+++ b/src/mpool.c
@@ -0,0 +1,256 @@
+/*
+ * Copyright 2018 Google LLC
+ *
+ * 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
+ *
+ * https://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 "hf/mpool.h"
+
+#include <stdbool.h>
+
+struct mpool_chunk {
+ struct mpool_chunk *next_chunk;
+ struct mpool_chunk *limit;
+};
+
+struct mpool_entry {
+ struct mpool_entry *next;
+};
+
+static bool mpool_locks_enabled = false;
+
+/**
+ * Enables the locks protecting memory pools. Before this function is called,
+ * the locks are disabled, that is, acquiring/releasing them is a no-op.
+ */
+void mpool_enable_locks(void)
+{
+ mpool_locks_enabled = true;
+}
+
+/**
+ * Acquires the lock protecting the given memory pool, if locks are enabled.
+ */
+static void mpool_lock(struct mpool *p)
+{
+ if (mpool_locks_enabled) {
+ sl_lock(&p->lock);
+ }
+}
+
+/**
+ * Releases the lock protecting the given memory pool, if locks are enabled.
+ */
+static void mpool_unlock(struct mpool *p)
+{
+ if (mpool_locks_enabled) {
+ sl_unlock(&p->lock);
+ }
+}
+
+/**
+ * Initialises the given memory pool with the given entry size, which must be
+ * at least the size of two pointers.
+ *
+ * All entries stored in the memory pool will be aligned to at least the entry
+ * size.
+ */
+void mpool_init(struct mpool *p, size_t entry_size)
+{
+ p->entry_size = entry_size;
+ p->chunk_list = NULL;
+ p->entry_list = NULL;
+ sl_init(&p->lock);
+}
+
+/**
+ * Initialises the given memory pool by replicating the properties of `from`. It
+ * also pulls the chunk and free lists from `from`, consuming all its resources
+ * and making them available via the new memory pool.
+ */
+void mpool_init_from(struct mpool *p, struct mpool *from)
+{
+ mpool_init(p, from->entry_size);
+
+ mpool_lock(from);
+ p->chunk_list = from->chunk_list;
+ p->entry_list = from->entry_list;
+
+ from->chunk_list = NULL;
+ from->entry_list = NULL;
+ mpool_unlock(from);
+}
+
+/**
+ * Adds a contiguous chunk of memory to the given memory pool. The chunk will
+ * eventually be broken up into entries of the size held by the memory pool.
+ *
+ * Only the portions aligned to the entry size will be added to the pool.
+ *
+ * Returns true if at least a portion of the chunk was added to pool, or false
+ * if none of the buffer was usable in the pool.
+ */
+bool mpool_add_chunk(struct mpool *p, void *begin, size_t size)
+{
+ struct mpool_chunk *chunk;
+ uintptr_t new_begin;
+ uintptr_t new_end;
+
+ /* Round begin address up, and end address down. */
+ new_begin = ((uintptr_t)begin + p->entry_size - 1) / p->entry_size *
+ p->entry_size;
+ new_end = ((uintptr_t)begin + size) / p->entry_size * p->entry_size;
+
+ /* Nothing to do if there isn't enough room for an entry. */
+ if (new_begin >= new_end || new_end - new_begin < p->entry_size) {
+ return false;
+ }
+
+ chunk = (struct mpool_chunk *)new_begin;
+ chunk->limit = (struct mpool_chunk *)new_end;
+
+ mpool_lock(p);
+ chunk->next_chunk = p->chunk_list;
+ p->chunk_list = chunk;
+ mpool_unlock(p);
+
+ return true;
+}
+
+/**
+ * Allocates an entry from the given memory pool, if one is available.
+ */
+void *mpool_alloc(struct mpool *p)
+{
+ void *ret;
+ struct mpool_chunk *chunk;
+ struct mpool_chunk *new_chunk;
+
+ /* Fetch an entry from the free list if one is available. */
+ mpool_lock(p);
+ if (p->entry_list != NULL) {
+ struct mpool_entry *entry = p->entry_list;
+ p->entry_list = entry->next;
+ ret = entry;
+ goto exit;
+ }
+
+ chunk = p->chunk_list;
+ if (chunk == NULL) {
+ /* The chunk list is also empty, we're out of entries. */
+ ret = NULL;
+ goto exit;
+ }
+
+ new_chunk = (struct mpool_chunk *)((uintptr_t)chunk + p->entry_size);
+ if (new_chunk >= chunk->limit) {
+ p->chunk_list = chunk->next_chunk;
+ } else {
+ *new_chunk = *chunk;
+ p->chunk_list = new_chunk;
+ }
+
+ ret = chunk;
+
+exit:
+ mpool_unlock(p);
+ return ret;
+}
+
+/**
+ * Frees an entry back into the memory pool, making it available for reuse.
+ *
+ * This is meant to be used for freeing single entries. To free multiple
+ * entries, one must call mpool_add_chunk instead.
+ */
+void mpool_free(struct mpool *p, void *ptr)
+{
+ struct mpool_entry *e = ptr;
+
+ /* Store the newly freed entry in the front of the free list. */
+ mpool_lock(p);
+ e->next = p->entry_list;
+ p->entry_list = e;
+ mpool_unlock(p);
+}
+
+/**
+ * Allocates a number of contiguous and aligned entries. This is a best-effort
+ * operation and only succeeds if such entries can be found in chunks (i.e., the
+ * entry list is never used to satisfy these allocations).
+ *
+ * The alignment is specified as the number of entries, that is, if `align` is
+ * 4, the alignment in bytes will be 4 * entry_size.
+ *
+ * The caller can enventually free the returned entries by calling
+ * mpool_add_chunk.
+ */
+void *mpool_alloc_contiguous(struct mpool *p, size_t count, size_t align)
+{
+ struct mpool_chunk **prev;
+ void *ret = NULL;
+
+ align *= p->entry_size;
+
+ mpool_lock(p);
+
+ /*
+ * Go through the chunk list in search of one with enough room for the
+ * requested allocation
+ */
+ prev = &p->chunk_list;
+ while (*prev != NULL) {
+ uintptr_t start;
+ struct mpool_chunk *new_chunk;
+ struct mpool_chunk *chunk = *prev;
+
+ /* Round start address up to the required alignment. */
+ start = ((uintptr_t)chunk + align - 1) / align * align;
+
+ /*
+ * Calculate where the new chunk would be if we consume the
+ * requested number of entries. Then check if this chunk is big
+ * enough to satisfy the request.
+ */
+ new_chunk =
+ (struct mpool_chunk *)(start + count * p->entry_size);
+ if (new_chunk <= chunk->limit) {
+ /* Remove the consumed area. */
+ if (new_chunk == chunk->limit) {
+ *prev = chunk->next_chunk;
+ } else {
+ *new_chunk = *chunk;
+ *prev = new_chunk;
+ }
+
+ /*
+ * Add back the space consumed by the alignment
+ * requirement, if it's big enough to fit an entry.
+ */
+ if (start - (uintptr_t)chunk >= p->entry_size) {
+ chunk->next_chunk = *prev;
+ *prev = chunk;
+ chunk->limit = (struct mpool_chunk *)start;
+ }
+
+ ret = (void *)start;
+ break;
+ }
+
+ prev = &chunk->next_chunk;
+ }
+
+ mpool_unlock(p);
+
+ return ret;
+}
diff --git a/src/mpool_test.cc b/src/mpool_test.cc
new file mode 100644
index 0000000..5cc7fe0
--- /dev/null
+++ b/src/mpool_test.cc
@@ -0,0 +1,292 @@
+/*
+ * Copyright 2018 Google LLC
+ *
+ * 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
+ *
+ * https://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 <stdalign.h>
+
+#include <gmock/gmock.h>
+
+extern "C" {
+#include "hf/mpool.h"
+}
+
+namespace
+{
+using ::testing::IsNull;
+using ::testing::NotNull;
+
+/**
+ * Checks that the given allocations come from the given chunks.
+ */
+bool check_allocs(std::vector<std::unique_ptr<char[]>>& chunks,
+ std::vector<uintptr_t>& allocs, size_t entries_per_chunk,
+ size_t entry_size)
+{
+ size_t i, j;
+
+ if (allocs.size() != chunks.size() * entries_per_chunk) {
+ return false;
+ }
+
+ sort(allocs.begin(), allocs.end());
+ sort(chunks.begin(), chunks.end(),
+ [](const std::unique_ptr<char[]>& a,
+ const std::unique_ptr<char[]>& b) {
+ return a.get() < b.get();
+ });
+
+ for (i = 0; i < chunks.size(); i++) {
+ if ((uintptr_t)chunks[i].get() !=
+ allocs[i * entries_per_chunk]) {
+ return false;
+ }
+
+ for (j = 1; j < entries_per_chunk; j++) {
+ size_t k = i * entries_per_chunk + j;
+ if (allocs[k] != allocs[k - 1] + entry_size) {
+ return false;
+ }
+ }
+ }
+
+ return true;
+}
+
+/**
+ * Add chunks to the given mem pool and chunk vector.
+ */
+static void add_chunks(std::vector<std::unique_ptr<char[]>>& chunks,
+ struct mpool* p, size_t count, size_t size)
+{
+ size_t i;
+
+ for (i = 0; i < count; i++) {
+ chunks.emplace_back(std::make_unique<char[]>(size));
+ mpool_add_chunk(p, chunks.back().get(), size);
+ }
+}
+
+/**
+ * Validates allocations from a memory pool.
+ */
+TEST(mpool, allocation)
+{
+ struct mpool p;
+ constexpr size_t entry_size = 16;
+ constexpr size_t entries_per_chunk = 10;
+ constexpr size_t chunk_count = 10;
+ std::vector<std::unique_ptr<char[]>> chunks;
+ std::vector<uintptr_t> allocs;
+ void* ret;
+
+ mpool_init(&p, entry_size);
+
+ /* Allocate from an empty pool. */
+ EXPECT_THAT(mpool_alloc(&p), IsNull());
+
+ /*
+ * Add a chunk that is too small, it should be ignored, and allocation
+ * should return NULL.
+ */
+ mpool_add_chunk(&p, NULL, entry_size - 1);
+ EXPECT_THAT(mpool_alloc(&p), IsNull());
+
+ /* Allocate a number of chunks and add them to the pool. */
+ add_chunks(chunks, &p, chunk_count, entries_per_chunk * entry_size);
+
+ /* Allocate from the pool until we run out of memory. */
+ while ((ret = mpool_alloc(&p))) {
+ allocs.push_back((uintptr_t)ret);
+ }
+
+ /* Check that returned entries are within chunks that were added. */
+ ASSERT_THAT(check_allocs(chunks, allocs, entries_per_chunk, entry_size),
+ true);
+}
+
+/**
+ * Validates frees into a memory pool.
+ */
+TEST(mpool, freeing)
+{
+ struct mpool p;
+ constexpr size_t entry_size = 16;
+ constexpr size_t entries_per_chunk = 10;
+ constexpr size_t chunk_count = 10;
+ std::vector<std::unique_ptr<char[]>> chunks;
+ std::vector<uintptr_t> allocs;
+ size_t i;
+ alignas(entry_size) char entry[entry_size];
+ void* ret;
+
+ mpool_init(&p, entry_size);
+
+ /* Allocate from an empty pool. */
+ EXPECT_THAT(mpool_alloc(&p), IsNull());
+
+ /* Free an entry into the pool, then allocate it back. */
+ mpool_free(&p, &entry[0]);
+ EXPECT_THAT(mpool_alloc(&p), (void*)&entry[0]);
+ EXPECT_THAT(mpool_alloc(&p), IsNull());
+
+ /* Allocate a number of chunks and add them to the pool. */
+ add_chunks(chunks, &p, chunk_count, entries_per_chunk * entry_size);
+
+ /*
+ * Free again into the pool. Ensure that we get entry back on next
+ * allocation instead of something from the chunks.
+ */
+ mpool_free(&p, &entry[0]);
+ EXPECT_THAT(mpool_alloc(&p), (void*)&entry[0]);
+
+ /* Allocate from the pool until we run out of memory. */
+ while ((ret = mpool_alloc(&p))) {
+ allocs.push_back((uintptr_t)ret);
+ }
+
+ /*
+ * Free again into the pool. Ensure that we get entry back on next
+ * allocation instead of something from the chunks.
+ */
+ mpool_free(&p, &entry[0]);
+ EXPECT_THAT(mpool_alloc(&p), (void*)&entry[0]);
+
+ /* Add entries back to the pool by freeing them. */
+ for (i = 0; i < allocs.size(); i++) {
+ mpool_free(&p, (void*)allocs[i]);
+ }
+ allocs.clear();
+
+ /* Allocate from the pool until we run out of memory. */
+ while ((ret = mpool_alloc(&p))) {
+ allocs.push_back((uintptr_t)ret);
+ }
+
+ /* Check that returned entries are within chunks that were added. */
+ ASSERT_THAT(check_allocs(chunks, allocs, entries_per_chunk, entry_size),
+ true);
+}
+
+/**
+ * Initialises a memory pool from an existing one.
+ */
+TEST(mpool, init_from)
+{
+ struct mpool p, q;
+ constexpr size_t entry_size = 16;
+ constexpr size_t entries_per_chunk = 10;
+ constexpr size_t chunk_count = 10;
+ std::vector<std::unique_ptr<char[]>> chunks;
+ std::vector<uintptr_t> allocs;
+ size_t i;
+ void* ret;
+
+ mpool_init(&p, entry_size);
+
+ /* Allocate a number of chunks and add them to the pool. */
+ add_chunks(chunks, &p, chunk_count, entries_per_chunk * entry_size);
+
+ /* Allocate half of the elements. */
+ for (i = 0; i < entries_per_chunk * chunk_count / 2; i++) {
+ void* ret = mpool_alloc(&p);
+ ASSERT_THAT(ret, NotNull());
+ allocs.push_back((uintptr_t)ret);
+ }
+
+ /* Add entries back to the pool by freeing them. */
+ for (i = 0; i < allocs.size(); i++) {
+ mpool_free(&p, (void*)allocs[i]);
+ }
+ allocs.clear();
+
+ /* Initialise q from p. */
+ mpool_init_from(&q, &p);
+
+ /* Allocation from p must now fail. */
+ EXPECT_THAT(mpool_alloc(&p), IsNull());
+
+ /* Allocate from q until we run out of memory. */
+ while ((ret = mpool_alloc(&q))) {
+ allocs.push_back((uintptr_t)ret);
+ }
+
+ /* Check that returned entries are within chunks that were added. */
+ ASSERT_THAT(check_allocs(chunks, allocs, entries_per_chunk, entry_size),
+ true);
+}
+
+/**
+ * Initialises a memory pool from an existing one.
+ */
+TEST(mpool, alloc_contiguous)
+{
+ struct mpool p;
+ constexpr size_t entry_size = 16;
+ constexpr size_t entries_per_chunk = 10;
+ constexpr size_t chunk_count = 10;
+ std::vector<std::unique_ptr<char[]>> chunks;
+ std::vector<uintptr_t> allocs;
+ size_t i;
+ void* ret;
+ uintptr_t next;
+
+ mpool_init(&p, entry_size);
+
+ /* Allocate a number of chunks and add them to the pool. */
+ add_chunks(chunks, &p, chunk_count, entries_per_chunk * entry_size);
+
+ /*
+ * Allocate entries until the remaining chunk is aligned to 2 entries,
+ * but not aligned to 4 entries.
+ */
+ do {
+ ret = mpool_alloc(&p);
+ ASSERT_THAT(ret, NotNull());
+ allocs.push_back((uintptr_t)ret);
+ next = (uintptr_t)ret / entry_size + 1;
+ } while ((next % 4) != 2);
+
+ /* Allocate 5 entries with an alignment of 4. So two must be skipped. */
+ ret = mpool_alloc_contiguous(&p, 5, 4);
+ ASSERT_THAT(ret, NotNull());
+ ASSERT_THAT((uintptr_t)ret, (next + 2) * entry_size);
+ for (i = 0; i < 5; i++) {
+ allocs.push_back((uintptr_t)ret + i * entry_size);
+ }
+
+ /* Allocate a whole chunk. */
+ ret = mpool_alloc_contiguous(&p, entries_per_chunk, 1);
+ ASSERT_THAT(ret, NotNull());
+ for (i = 0; i < entries_per_chunk; i++) {
+ allocs.push_back((uintptr_t)ret + i * entry_size);
+ }
+
+ /* Allocate 2 entries that are already aligned. */
+ ret = mpool_alloc_contiguous(&p, 2, 1);
+ ASSERT_THAT(ret, NotNull());
+ allocs.push_back((uintptr_t)ret);
+ allocs.push_back((uintptr_t)ret + entry_size);
+
+ /* Allocate from p until we run out of memory. */
+ while ((ret = mpool_alloc(&p))) {
+ allocs.push_back((uintptr_t)ret);
+ }
+
+ /* Check that returned entries are within chunks that were added. */
+ ASSERT_THAT(check_allocs(chunks, allocs, entries_per_chunk, entry_size),
+ true);
+}
+
+} /* namespace */
