FD.io VPP  v16.12-rc0-308-g931be3a
Vector Packet Processing
heap.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2015 Cisco and/or its affiliates.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at:
6  *
7  * http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 /*
16  Copyright (c) 2001, 2002, 2003 Eliot Dresselhaus
17 
18  Permission is hereby granted, free of charge, to any person obtaining
19  a copy of this software and associated documentation files (the
20  "Software"), to deal in the Software without restriction, including
21  without limitation the rights to use, copy, modify, merge, publish,
22  distribute, sublicense, and/or sell copies of the Software, and to
23  permit persons to whom the Software is furnished to do so, subject to
24  the following conditions:
25 
26  The above copyright notice and this permission notice shall be
27  included in all copies or substantial portions of the Software.
28 
29  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
30  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
31  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
32  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
33  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
34  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
35  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
36 */
37 
38 /* Heaps of objects of type T (e.g. int, struct foo, ...).
39 
40  Usage. To declare a null heap:
41 
42  T * heap = 0;
43 
44  To allocate:
45 
46  offset = heap_alloc (heap, size, handle);
47 
48  New object is heap[offset] ... heap[offset + size]
49  Handle is used to free/query object.
50 
51  To free object:
52 
53  heap_dealloc (heap, handle);
54 
55  To query the size of an object:
56 
57  heap_size (heap, handle)
58 
59 */
60 
61 #ifndef included_heap_h
62 #define included_heap_h
63 
64 #include <vppinfra/clib.h>
65 #include <vppinfra/cache.h>
66 #include <vppinfra/hash.h>
67 #include <vppinfra/format.h>
68 #include <vppinfra/bitmap.h>
69 
70 /* Doubly linked list of elements. */
71 typedef struct
72 {
73  /* Offset of this element (plus free bit).
74  If element is free, data at offset contains pointer to free list. */
76 
77  /* Index of next and previous elements relative to current element. */
78  i32 next, prev;
79 } heap_elt_t;
80 
81 /* Use high bit of offset as free bit. */
82 #define HEAP_ELT_FREE_BIT (1 << 31)
83 
86 {
87  return (e->offset & HEAP_ELT_FREE_BIT) != 0;
88 }
89 
92 {
93  return e->offset & ~HEAP_ELT_FREE_BIT;
94 }
95 
98 {
99  return e + e->next;
100 }
101 
104 {
105  return e + e->prev;
106 }
107 
109 heap_elt_size (void *v, heap_elt_t * e)
110 {
111  heap_elt_t *n = heap_next (e);
112  uword next_offset = n != e ? heap_offset (n) : vec_len (v);
113  return next_offset - heap_offset (e);
114 }
115 
116 /* Sizes are binned. Sizes 1 to 2^log2_small_bins have their
117  own free lists. Larger sizes are grouped in powers of two. */
118 #define HEAP_LOG2_SMALL_BINS (5)
119 #define HEAP_SMALL_BINS (1 << HEAP_LOG2_SMALL_BINS)
120 #define HEAP_N_BINS (2 * HEAP_SMALL_BINS)
121 
122 /* Header for heaps. */
123 typedef struct
124 {
125  /* Vector of used and free elements. */
127 
128  /* For elt_bytes < sizeof (u32) we need some extra space
129  per elt to store free list index. */
131 
132  /* Vector of free indices of elts array. */
134 
135  /* Indices of free elts indexed by size bin. */
137 
139 
140  /* Used for validattion/debugging. */
142 
143  /* First and last element of doubly linked chain of elements. */
144  u32 head, tail;
145 
146  u32 used_count, max_len;
147 
148  /* Number of bytes in a help element. */
150 
152  /* Static heaps are made from external memory given to
153  us by user and are not re-sizeable vectors. */
154 #define HEAP_IS_STATIC (1)
155 } heap_header_t;
156 
157 /* Start of heap elements is always cache aligned. */
158 #define HEAP_DATA_ALIGN (CLIB_CACHE_LINE_BYTES)
159 
161 heap_header (void *v)
162 {
163  return vec_header (v, sizeof (heap_header_t));
164 }
165 
168 {
169  return vec_header_bytes (sizeof (heap_header_t));
170 }
171 
172 always_inline void
174 {
175  uword i;
176 
177  new[0] = old[0];
178  new->elts = vec_dup (new->elts);
179  new->free_elts = vec_dup (new->free_elts);
180  new->free_lists = vec_dup (new->free_lists);
181  for (i = 0; i < vec_len (new->free_lists); i++)
182  new->free_lists[i] = vec_dup (new->free_lists[i]);
183  new->used_elt_bitmap = clib_bitmap_dup (new->used_elt_bitmap);
184  new->small_free_elt_free_index = vec_dup (new->small_free_elt_free_index);
185 }
186 
187 /* Make a duplicate copy of a heap. */
188 #define heap_dup(v) _heap_dup(v, vec_len (v) * sizeof (v[0]))
189 
190 always_inline void *
191 _heap_dup (void *v_old, uword v_bytes)
192 {
193  heap_header_t *h_old, *h_new;
194  void *v_new;
195 
196  h_old = heap_header (v_old);
197 
198  if (!v_old)
199  return v_old;
200 
201  v_new = 0;
202  v_new =
203  _vec_resize (v_new, _vec_len (v_old), v_bytes, sizeof (heap_header_t),
205  h_new = heap_header (v_new);
206  heap_dup_header (h_old, h_new);
207  clib_memcpy (v_new, v_old, v_bytes);
208  return v_new;
209 }
210 
212 heap_elts (void *v)
213 {
214  heap_header_t *h = heap_header (v);
215  return h->used_count;
216 }
217 
218 uword heap_bytes (void *v);
219 
220 always_inline void *
221 _heap_new (u32 len, u32 n_elt_bytes)
222 {
223  void *v = _vec_resize (0, len, (uword) len * n_elt_bytes,
224  sizeof (heap_header_t),
226  heap_header (v)->elt_bytes = n_elt_bytes;
227  return v;
228 }
229 
230 #define heap_new(v) (v) = _heap_new (0, sizeof ((v)[0]))
231 
232 always_inline void
233 heap_set_format (void *v, format_function_t * format_elt)
234 {
235  ASSERT (v);
236  heap_header (v)->format_elt = format_elt;
237 }
238 
239 always_inline void
240 heap_set_max_len (void *v, uword max_len)
241 {
242  ASSERT (v);
243  heap_header (v)->max_len = max_len;
244 }
245 
248 {
249  return v ? heap_header (v)->max_len : 0;
250 }
251 
252 /* Create fixed size heap with given block of memory. */
253 always_inline void *
254 heap_create_from_memory (void *memory, uword max_len, uword elt_bytes)
255 {
256  heap_header_t *h;
257  void *v;
258 
259  if (max_len * elt_bytes < sizeof (h[0]))
260  return 0;
261 
262  h = memory;
263  memset (h, 0, sizeof (h[0]));
264  h->max_len = max_len;
265  h->elt_bytes = elt_bytes;
266  h->flags = HEAP_IS_STATIC;
267 
268  v = (void *) (memory + heap_header_bytes ());
269  _vec_len (v) = 0;
270  return v;
271 }
272 
273 /* Execute BODY for each allocated heap element. */
274 #define heap_foreach(var,len,heap,body) \
275 do { \
276  if (vec_len (heap) > 0) \
277  { \
278  heap_header_t * _h = heap_header (heap); \
279  heap_elt_t * _e = _h->elts + _h->head; \
280  heap_elt_t * _end = _h->elts + _h->tail; \
281  while (1) \
282  { \
283  if (! heap_is_free (_e)) \
284  { \
285  (var) = (heap) + heap_offset (_e); \
286  (len) = heap_elt_size ((heap), _e); \
287  do { body; } while (0); \
288  } \
289  if (_e == _end) \
290  break; \
291  _e = heap_next (_e); \
292  } \
293  } \
294 } while (0)
295 
296 #define heap_elt_at_index(v,index) vec_elt_at_index(v,index)
297 
299 heap_get_elt (void *v, uword handle)
300 {
301  heap_header_t *h = heap_header (v);
302  heap_elt_t *e = vec_elt_at_index (h->elts, handle);
303  ASSERT (!heap_is_free (e));
304  return e;
305 }
306 
307 #define heap_elt_with_handle(v,handle) \
308 ({ \
309  heap_elt_t * _e = heap_get_elt ((v), (handle)); \
310  (v) + heap_offset (_e); \
311 })
312 
314 heap_is_free_handle (void *v, uword heap_handle)
315 {
316  heap_header_t *h = heap_header (v);
317  heap_elt_t *e = vec_elt_at_index (h->elts, heap_handle);
318  return heap_is_free (e);
319 }
320 
321 extern uword heap_len (void *v, word handle);
322 
323 /* Low level allocation call. */
324 extern void *_heap_alloc (void *v, uword size, uword alignment,
325  uword elt_bytes, uword * offset, uword * handle);
326 
327 #define heap_alloc_aligned(v,size,align,handle) \
328 ({ \
329  uword _o, _h; \
330  uword _a = (align); \
331  uword _s = (size); \
332  (v) = _heap_alloc ((v), _s, _a, sizeof ((v)[0]), &_o, &_h); \
333  (handle) = _h; \
334  _o; \
335 })
336 
337 #define heap_alloc(v,size,handle) heap_alloc_aligned((v),(size),0,(handle))
338 
339 extern void heap_dealloc (void *v, uword handle);
340 extern void heap_validate (void *v);
341 
342 /* Format heap internal data structures as string. */
343 extern u8 *format_heap (u8 * s, va_list * va);
344 
345 void *_heap_free (void *v);
346 
347 #define heap_free(v) (v)=_heap_free(v)
348 
349 #endif /* included_heap_h */
350 
351 /*
352  * fd.io coding-style-patch-verification: ON
353  *
354  * Local Variables:
355  * eval: (c-set-style "gnu")
356  * End:
357  */
sll srl srl sll sra u16x4 i
Definition: vector_sse2.h:343
i32 next
Definition: heap.h:78
static uword heap_get_max_len(void *v)
Definition: heap.h:247
u32 tail
Definition: heap.h:144
u32 offset
Definition: heap.h:75
static heap_elt_t * heap_get_elt(void *v, uword handle)
Definition: heap.h:299
#define clib_bitmap_dup(v)
Duplicate a bitmap.
Definition: bitmap.h:87
vhost_user_memory_t memory
Definition: vhost-user.h:82
format_function_t * format_elt
Definition: heap.h:138
u32 * free_elts
Definition: heap.h:133
uword heap_bytes(void *v)
Definition: heap.c:628
static uword vec_header_bytes(uword header_bytes)
Definition: vec_bootstrap.h:79
#define always_inline
Definition: clib.h:84
int i32
Definition: types.h:81
static void heap_set_max_len(void *v, uword max_len)
Definition: heap.h:240
#define vec_elt_at_index(v, i)
Get vector value at index i checking that i is in bounds.
static uword heap_is_free(heap_elt_t *e)
Definition: heap.h:85
static void * heap_create_from_memory(void *memory, uword max_len, uword elt_bytes)
Definition: heap.h:254
uword * used_elt_bitmap
Definition: heap.h:141
static heap_elt_t * heap_next(heap_elt_t *e)
Definition: heap.h:97
u8 * format_heap(u8 *s, va_list *va)
Definition: heap.c:694
#define HEAP_DATA_ALIGN
Definition: heap.h:158
#define HEAP_IS_STATIC
Definition: heap.h:154
i32 prev
Definition: heap.h:78
void heap_validate(void *v)
Definition: heap.c:722
heap_elt_t * elts
Definition: heap.h:126
#define vec_dup(V)
Return copy of vector (no header, no alignment)
Definition: vec.h:334
u32 max_len
Definition: heap.h:146
uword heap_len(void *v, word handle)
Definition: heap.c:597
static uword heap_header_bytes()
Definition: heap.h:167
static void heap_dup_header(heap_header_t *old, heap_header_t *new)
Definition: heap.h:173
u32 elt_bytes
Definition: heap.h:149
u32 used_count
Definition: heap.h:146
#define clib_memcpy(a, b, c)
Definition: string.h:64
static uword heap_offset(heap_elt_t *e)
Definition: heap.h:91
u32 * small_free_elt_free_index
Definition: heap.h:130
#define ASSERT(truth)
unsigned int u32
Definition: types.h:88
u32 size
Definition: vhost-user.h:76
Bitmaps built as vectors of machine words.
static uword heap_elt_size(void *v, heap_elt_t *e)
Definition: heap.h:109
static heap_header_t * heap_header(void *v)
Definition: heap.h:161
u8 *( format_function_t)(u8 *s, va_list *args)
Definition: format.h:48
static heap_elt_t * heap_prev(heap_elt_t *e)
Definition: heap.h:103
u32 flags
Definition: heap.h:151
static void heap_set_format(void *v, format_function_t *format_elt)
Definition: heap.h:233
u64 uword
Definition: types.h:112
template key/value backing page structure
Definition: bihash_doc.h:44
static uword heap_is_free_handle(void *v, uword heap_handle)
Definition: heap.h:314
i64 word
Definition: types.h:111
#define HEAP_ELT_FREE_BIT
Definition: heap.h:82
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
unsigned char u8
Definition: types.h:56
static uword heap_elts(void *v)
Definition: heap.h:212
static void * vec_header(void *v, uword header_bytes)
Find a user vector header.
Definition: vec_bootstrap.h:92
void heap_dealloc(void *v, uword handle)
Definition: heap.c:496
u32 ** free_lists
Definition: heap.h:136