summaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authorEnrico Loparco (eloparco) <eloparco@cisco.com>2022-09-08 12:18:09 +0000
committerEnrico Loparco (eloparco) <eloparco@cisco.com>2022-09-12 13:23:29 +0000
commit6ee6b65ef03f8a479cccb2ae04e6b156f309f045 (patch)
treeea59d0e048c53c40490bc7290eda09ccad954423 /lib
parentcb6f5724b85e51295498a39144ed4ccce114ad53 (diff)
feat(slab): add slab allocator to store hashtables' keys
Ref: HICN-777 Signed-off-by: Enrico Loparco (eloparco) <eloparco@cisco.com> Change-Id: Ibbd5c5e73cfd2f6adf757f7248dff8a933515d21
Diffstat (limited to 'lib')
-rw-r--r--lib/includes/CMakeLists.txt2
-rw-r--r--lib/includes/hicn/util/log.h15
-rw-r--r--lib/includes/hicn/util/slab.h126
-rw-r--r--lib/includes/hicn/util/sstrncpy.h1
-rw-r--r--lib/src/CMakeLists.txt1
-rw-r--r--lib/src/test/CMakeLists.txt1
-rw-r--r--lib/src/test/test_khash.cc4
-rw-r--r--lib/src/test/test_slab.cc148
-rw-r--r--lib/src/util/slab.c203
9 files changed, 492 insertions, 9 deletions
diff --git a/lib/includes/CMakeLists.txt b/lib/includes/CMakeLists.txt
index 61af7eca8..3c79fb891 100644
--- a/lib/includes/CMakeLists.txt
+++ b/lib/includes/CMakeLists.txt
@@ -47,6 +47,7 @@ set(LIBHICN_HEADER_FILES_UTIL
${CMAKE_CURRENT_SOURCE_DIR}/hicn/util/pool.h
${CMAKE_CURRENT_SOURCE_DIR}/hicn/util/ring.h
${CMAKE_CURRENT_SOURCE_DIR}/hicn/util/set.h
+ ${CMAKE_CURRENT_SOURCE_DIR}/hicn/util/slab.h
${CMAKE_CURRENT_SOURCE_DIR}/hicn/util/sstrncpy.h
${CMAKE_CURRENT_SOURCE_DIR}/hicn/util/token.h
${CMAKE_CURRENT_SOURCE_DIR}/hicn/util/types.h
@@ -55,4 +56,3 @@ set(LIBHICN_HEADER_FILES_UTIL
)
set_property(GLOBAL PROPERTY LIBHICN_HEADER_FILES_UTIL_PROPERTY "${LIBHICN_HEADER_FILES_UTIL}")
-
diff --git a/lib/includes/hicn/util/log.h b/lib/includes/hicn/util/log.h
index 6b35d1fef..b9b7725d6 100644
--- a/lib/includes/hicn/util/log.h
+++ b/lib/includes/hicn/util/log.h
@@ -20,12 +20,15 @@
#include <stdio.h> // FILE
#include <time.h> // time, localtime
-#define LOG_FATAL 0
-#define LOG_ERROR 1
-#define LOG_WARN 2
-#define LOG_INFO 3
-#define LOG_DEBUG 4
-#define LOG_TRACE 5
+typedef enum
+{
+ LOG_FATAL,
+ LOG_ERROR,
+ LOG_WARN,
+ LOG_INFO,
+ LOG_DEBUG,
+ LOG_TRACE
+} log_level_t;
typedef struct
{
diff --git a/lib/includes/hicn/util/slab.h b/lib/includes/hicn/util/slab.h
new file mode 100644
index 000000000..2c6546add
--- /dev/null
+++ b/lib/includes/hicn/util/slab.h
@@ -0,0 +1,126 @@
+/*
+ * 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.
+ */
+
+/**
+ * @brief The slab is used to store elements of the same size.
+ *
+ * The slab contains blocks of contiguous memory. Each block contains multiple
+ * chunks. An element is stored inside a chunk and the chunk has a header with
+ * a pointer to the block it belongs to.
+ *
+ * Blocks are stored in two doubly-linked lists: 'full' for blocks that
+ * are already full, 'partial_or_empty' for blocks with available chunks. When
+ * a block becomes full it is moved into the 'full' list and vice versa.
+ *
+ * When allocationg an element, a block is taken from the 'partial_or_empty'
+ * list if such list is not empty. If empty, a new block of contiguous memory
+ * is created and put in the 'partial_or_empty' list. Then, a chunk is taken
+ * from the block. When releasing an element, the block it belongs to is
+ * retrieved from the chunk header and used to release the chunk.
+ *
+ * Blocks are created with increasing capacity (i.e. number of chunks they
+ * contain) such that every new block allocaion doubles the total number of
+ * chunks stored in the slab.
+ */
+
+#ifndef UTIL_SLAB_H
+#define UTIL_SLAB_H
+
+#include <stddef.h>
+
+#define SLAB_INIT_SIZE 32
+
+/* CHUNK */
+
+typedef struct block_s block_t;
+typedef struct
+{
+ block_t *block; // Pointer to the block that contains the chunk
+} chunk_hdr_t;
+
+#define CHUNK_HDRLEN SIZEOF_ALIGNED (chunk_hdr_t)
+#define chunk_hdr(chunk) ((chunk_hdr_t *) ((uint8_t *) (chunk) -CHUNK_HDRLEN))
+
+/* BLOCK */
+
+struct block_s
+{
+ void *pool;
+ block_t *prev;
+ block_t *next;
+};
+
+/* SLAB */
+
+typedef struct
+{
+ size_t num_chunks; // Total number of chunks (from all blocks) currently
+ // stored in the slab
+ size_t chunk_size;
+ block_t *full;
+ block_t *partial_or_empty;
+} slab_t;
+
+/* Internal API */
+
+slab_t *_slab_create (size_t elt_size, size_t num_elts);
+void *_slab_get (slab_t *slab);
+void _slab_put (slab_t *slab, void *elt);
+
+/* Public API */
+
+/**
+ * @brief Create a slab able to store elements of type 'TYPE'.
+ *
+ * @param[in] TYPE Type of the elements to store in the slab.
+ * @param[in] SIZE Initial size of the slab, i.e. size of the initial block.
+ * @return slab_t* The slab created, NULL if error.
+ */
+#define slab_create(TYPE, SIZE) _slab_create (sizeof (TYPE), SIZE)
+
+/**
+ * @brief Free a slab.
+ *
+ * @param[in] slab Slab to free.
+ */
+void slab_free (slab_t *slab);
+
+/**
+ * @brief Get an element from the slab.
+ *
+ * @param[in] TYPE Type of the elements stored in the slab.
+ * @param[in] SLAB Slab to take the element from.
+ * @return TYPE* Element retrieved from the slab
+ */
+#define slab_get(TYPE, SLAB) (TYPE *) _slab_get (SLAB)
+
+/**
+ * @brief Same as 'slab_get' but with a different signature, to avoid passing
+ * the type that is instead inferred from the element.
+ *
+ * @param[in] SLAB Slab to take the element from.
+ * @param[in, out] ELT Element retrieved from the slab.
+ */
+#define slab_get2(SLAB, ELT) ELT = (typeof (*(ELT)) *) _slab_get (SLAB)
+
+/**
+ * @brief Put an element back into the slab.
+ *
+ * @param[in] SLAB Slab to return the element to.
+ * @param[in] ELT Element to put in the slab.
+ */
+#define slab_put(SLAB, ELT) _slab_put (SLAB, (void *) ELT)
+
+#endif /* UTIL_SLAB_H */
diff --git a/lib/includes/hicn/util/sstrncpy.h b/lib/includes/hicn/util/sstrncpy.h
index 81427be6b..0b397c26b 100644
--- a/lib/includes/hicn/util/sstrncpy.h
+++ b/lib/includes/hicn/util/sstrncpy.h
@@ -20,6 +20,7 @@
#define __STDC_WANT_LIB_EXT1__ 1
#endif
+#include <errno.h>
#include <string.h>
#ifdef __STDC_LIB_EXT1__
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 <gtest/gtest.h>
+
+extern "C"
+{
+#include <hicn/util/slab.h>
+}
+
+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 <hicn/util/pool.h>
+#include <hicn/util/slab.h>
+#include <stdlib.h>
+
+/* 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