1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
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 */
|
