diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/includes/CMakeLists.txt | 2 | ||||
| -rw-r--r-- | lib/includes/hicn/util/log.h | 15 | ||||
| -rw-r--r-- | lib/includes/hicn/util/slab.h | 126 | ||||
| -rw-r--r-- | lib/includes/hicn/util/sstrncpy.h | 1 | ||||
| -rw-r--r-- | lib/src/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | lib/src/test/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | lib/src/test/test_khash.cc | 4 | ||||
| -rw-r--r-- | lib/src/test/test_slab.cc | 148 | ||||
| -rw-r--r-- | lib/src/util/slab.c | 203 |
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 |