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

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

4 files changed, 137 insertions, 7 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__