feat(slab): add slab allocator to store hashtables' keys

Ref: HICN-777
Signed-off-by: Enrico Loparco (eloparco) <eloparco@cisco.com>
Change-Id: Ibbd5c5e73cfd2f6adf757f7248dff8a933515d21

5 files changed, 355 insertions, 2 deletions

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