diff options
Diffstat (limited to 'lib/includes/hicn/util/slab.h')
-rw-r--r-- | lib/includes/hicn/util/slab.h | 126 |
1 files changed, 126 insertions, 0 deletions
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 */ |