From 6ee6b65ef03f8a479cccb2ae04e6b156f309f045 Mon Sep 17 00:00:00 2001 From: "Enrico Loparco (eloparco)" Date: Thu, 8 Sep 2022 12:18:09 +0000 Subject: feat(slab): add slab allocator to store hashtables' keys Ref: HICN-777 Signed-off-by: Enrico Loparco (eloparco) Change-Id: Ibbd5c5e73cfd2f6adf757f7248dff8a933515d21 --- lib/src/CMakeLists.txt | 1 + lib/src/test/CMakeLists.txt | 1 + lib/src/test/test_khash.cc | 4 +- lib/src/test/test_slab.cc | 148 ++++++++++++++++++++++++++++++++ lib/src/util/slab.c | 203 ++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 355 insertions(+), 2 deletions(-) create mode 100644 lib/src/test/test_slab.cc create mode 100644 lib/src/util/slab.c (limited to 'lib/src') diff --git a/lib/src/CMakeLists.txt b/lib/src/CMakeLists.txt index 10c39fae2..27446a493 100644 --- a/lib/src/CMakeLists.txt +++ b/lib/src/CMakeLists.txt @@ -36,6 +36,7 @@ list(APPEND LIBHICN_SOURCE_FILES util/log.c util/pool.c util/ring.c + util/slab.c util/types.c util/vector.c ) diff --git a/lib/src/test/CMakeLists.txt b/lib/src/test/CMakeLists.txt index 17cf835d2..d828c8dd8 100644 --- a/lib/src/test/CMakeLists.txt +++ b/lib/src/test/CMakeLists.txt @@ -27,6 +27,7 @@ list(APPEND TESTS_SRC test_khash.cc test_pool.cc test_ring.cc + test_slab.cc test_vector.cc ) diff --git a/lib/src/test/test_khash.cc b/lib/src/test/test_khash.cc index b0423ab5d..70b2f2258 100644 --- a/lib/src/test/test_khash.cc +++ b/lib/src/test/test_khash.cc @@ -159,11 +159,11 @@ TEST_F (KHashTest, Collisions) k = kh_put_test_map (map, &key1, &ret); EXPECT_EQ (ret, 1); - kh_val (map, k) = 15; + kh_val (map, k) = 15u; k = kh_put_test_map (map, &key2, &ret); EXPECT_EQ (ret, 1); - kh_val (map, k) = 27; + kh_val (map, k) = 27u; k = kh_get_test_map (map, &key1); ASSERT_NE (k, kh_end (map)); diff --git a/lib/src/test/test_slab.cc b/lib/src/test/test_slab.cc new file mode 100644 index 000000000..15deff3c1 --- /dev/null +++ b/lib/src/test/test_slab.cc @@ -0,0 +1,148 @@ +/* + * Copyright (c) 2022 Cisco and/or its affiliates. + * 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 + +extern "C" +{ +#include +} + +class SlabTest : public ::testing::Test +{ +protected: + SlabTest () {} + virtual ~SlabTest () { slab_free (slab); } + + slab_t *slab; +}; + +typedef struct +{ + int index; + int val; +} element_t; + +TEST_F (SlabTest, SlabCreateAndGetSingleChunk) +{ + slab = slab_create (element_t, 16); + ASSERT_NE (slab, nullptr); + + element_t *e = slab_get (element_t, slab); + ASSERT_NE (e, nullptr); + slab_put (slab, e); +} + +TEST_F (SlabTest, SlabGetChunks) +{ + slab = slab_create (element_t, 2); + + // Force creation of multiple blocks (since initial size is only 2) + for (int i = 0; i < 100; i++) + { + element_t *e = slab_get (element_t, slab); + EXPECT_NE (e, nullptr); + } +} + +TEST_F (SlabTest, SlabGetAndPutChunksNoResize) +{ + constexpr int NUM_ELEMENTS = 64; + element_t *elements[NUM_ELEMENTS]; + for (int i = 0; i < NUM_ELEMENTS; i++) + elements[i] = NULL; + + // Initial size=NUM_ELEMENTS, only one block will be created + slab = slab_create (element_t, NUM_ELEMENTS); + + for (int i = 0; i < NUM_ELEMENTS; i++) + { + elements[i] = slab_get (element_t, slab); + EXPECT_NE (elements[i], nullptr); + } + + // Release all chunks + for (int i = 0; i < NUM_ELEMENTS; i++) + slab_put (slab, elements[i]); +} + +TEST_F (SlabTest, SlabGetAndPutChunks) +{ + constexpr int NUM_ELEMENTS = 100; + element_t *elements[NUM_ELEMENTS]; + for (int i = 0; i < NUM_ELEMENTS; i++) + elements[i] = NULL; + + // Initial size=2 while NUM_ELEMENTS=100, to force creation of multiple + // blocks + slab = slab_create (sizeof (element_t), 2); + + for (int i = 0; i < NUM_ELEMENTS; i++) + { + elements[i] = slab_get (element_t, slab); + EXPECT_NE (elements[i], nullptr); + } + + // Release all chunks + for (int i = 0; i < NUM_ELEMENTS; i++) + slab_put (slab, elements[i]); +} + +TEST_F (SlabTest, SlabGetAndPutSomeChunks) +{ + slab = slab_create (element_t, 2); + + constexpr int NUM_ELEMENTS = 100; + element_t *elements[NUM_ELEMENTS]; + for (int i = 0; i < NUM_ELEMENTS; i++) + elements[i] = NULL; + + // Get chunks... + for (int i = 0; i < NUM_ELEMENTS; i++) + { + elements[i] = slab_get (element_t, slab); + EXPECT_NE (elements[i], nullptr); + + // ...and return only some of them + if (i % 5 == 0) + slab_put (slab, elements[i]); + } +} + +TEST_F (SlabTest, SlabGetSameChunkTwice) +{ + slab = slab_create (element_t, 1); + + // Get chunk and update it before returning it + element_t *e = slab_get (element_t, slab); + ASSERT_NE (e, nullptr); + element_t *prev = e; + e->index = 2; + e->val = 3; + slab_put (slab, e); + + // Get a chunk again: it should return the previous one + // without wiping its memory + e = slab_get (element_t, slab); + ASSERT_NE (e, nullptr); + EXPECT_EQ (e, prev); + EXPECT_EQ (e->index, 2); + EXPECT_EQ (e->val, 3); + + // Try to get an additional chunk: it should return a new chunk + // (different from previous one) + e = slab_get (element_t, slab); + EXPECT_NE (e, prev); +} \ No newline at end of file diff --git a/lib/src/util/slab.c b/lib/src/util/slab.c new file mode 100644 index 000000000..763dcb444 --- /dev/null +++ b/lib/src/util/slab.c @@ -0,0 +1,203 @@ +/* + * Copyright (c) 2022 Cisco and/or its affiliates. + * 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 +#include +#include + +/* BLOCK LINKED LISTS */ + +static void +block_add_to_head (block_t **head_ptr, block_t *block) +{ + if (head_ptr == NULL || block == NULL) + return; + + block->prev = NULL; + if (*head_ptr != NULL) + { + block->next = *head_ptr; + block->next->prev = block; + } + + *head_ptr = block; +} + +static block_t * +block_remove_from_head (block_t **head_ptr) +{ + if (head_ptr == NULL || *head_ptr == NULL) + return NULL; + + block_t *old_head = *head_ptr; + *head_ptr = old_head->next; + + if (*head_ptr != NULL) + (*head_ptr)->prev = NULL; + return old_head; +} + +static void +block_remove (block_t **head_ptr, block_t *block) +{ + if (*head_ptr == NULL || block == NULL) + return; + + if (block == *head_ptr) + *head_ptr = block->next; + if (block->next != NULL) + block->next->prev = block->prev; + if (block->prev != NULL) + block->prev->next = block->next; +} + +static bool +is_block_list_empty (block_t *block) +{ + return block == NULL; +} + +static void +block_list_free (block_t **head) +{ + if (head == NULL || *head == NULL) + return; + + block_t *curr_block = *head; + while (curr_block != NULL) + { + block_t *next = curr_block->next; + pool_free (curr_block->pool); + free (curr_block); + + curr_block = next; + } + + *head = NULL; +} + +/* BLOCK */ + +static bool +is_block_full (block_t *block) +{ + return pool_get_free_indices_size (block->pool) == 0; +} + +static void +block_set_ptr_in_chunks (block_t *block, size_t chunk_size) +{ + void *chunk = block->pool; + + // Cannot use `pool_foreach()` since it requires to know the type + // while here we use a generic (void *) + for (int i = 0; i < pool_get_alloc_size (block->pool); i++) + { + chunk_hdr_t *hdr = (chunk_hdr_t *) chunk; + hdr->block = block; + + chunk = (uint8_t *) (chunk) + chunk_size; // Move to next chunk + } +} + +static block_t * +block_create (size_t chunk_size, size_t num_chunks) +{ + block_t *block = malloc (sizeof (block_t)); + if (block == NULL) + return NULL; + + block->prev = block->next = NULL; + _pool_init (&block->pool, chunk_size, num_chunks, 0); + block_set_ptr_in_chunks (block, chunk_size); + + return block; +} + +/* SLAB */ + +slab_t * +_slab_create (size_t elt_size, size_t num_elts) +{ + // Initialize slab + slab_t *slab = malloc (sizeof (slab_t)); + if (slab == NULL) + return NULL; + + *slab = (slab_t){ .num_chunks = next_pow2 (num_elts), + .chunk_size = CHUNK_HDRLEN + elt_size, + .full = NULL, + .partial_or_empty = NULL }; + + // Add initial empty block to partial or empty list + block_t *block = block_create (slab->chunk_size, slab->num_chunks); + block_add_to_head (&slab->partial_or_empty, block); + + return slab; +} + +void +slab_free (slab_t *slab) +{ + block_list_free (&slab->full); + block_list_free (&slab->partial_or_empty); + free (slab); +} + +void * +_slab_get (slab_t *slab) +{ + // Create new empty block if none with available chunks + if (is_block_list_empty (slab->partial_or_empty)) + { + block_t *block = block_create (slab->chunk_size, slab->num_chunks); + block_add_to_head (&slab->partial_or_empty, block); + + slab->num_chunks *= 2; // Grow size exponentially + } + + // Get chunck from first block in 'partial_or_empty' list + void *chunk; + _pool_get (&slab->partial_or_empty->pool, &chunk, slab->chunk_size); + + // If the current block (i.e. head of 'partial_or_empty' list) if full, + // move it to the 'full' list + if (is_block_full (slab->partial_or_empty)) + { + block_t *block = block_remove_from_head (&slab->partial_or_empty); + block_add_to_head (&slab->full, block); + } + + return (uint8_t *) chunk + CHUNK_HDRLEN; +} + +void +_slab_put (slab_t *slab, void *chunk) +{ + // Get which block the chunk (that we want to release) belong to + chunk_hdr_t *hdr = chunk_hdr (chunk); + block_t *block = hdr->block; + + // Put chunk back into block + bool is_full = is_block_full (block); + _pool_put (&block->pool, (void *) &hdr, slab->chunk_size); + + // If the block was previously full, move it to 'partial_or_empty' list + if (is_full) + { + block_remove (&slab->full, block); + block_add_to_head (&slab->partial_or_empty, block); + } +} \ No newline at end of file -- cgit 1.2.3-korg