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:
7 * http://www.apache.org/licenses/LICENSE-2.0
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.
16 Copyright (c) 2001, 2002, 2003 Eliot Dresselhaus
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:
26 The above copyright notice and this permission notice shall be
27 included in all copies or substantial portions of the Software.
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.
38 /* Heaps of objects of type T (e.g. int, struct foo, ...).
40 Usage. To declare a null heap:
46 offset = heap_alloc (heap, size, handle);
48 New object is heap[offset] ... heap[offset + size]
49 Handle is used to free/query object.
53 heap_dealloc (heap, handle);
55 To query the size of an object:
57 heap_size (heap, handle)
61 #ifndef included_heap_h
62 #define included_heap_h
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>
70 /* Doubly linked list of elements. */
73 /* Offset of this element (plus free bit).
74 If element is free, data at offset contains pointer to free list. */
77 /* Index of next and previous elements relative to current element. */
81 /* Use high bit of offset as free bit. */
82 #define HEAP_ELT_FREE_BIT (1 << 31)
85 heap_is_free (heap_elt_t * e)
87 return (e->offset & HEAP_ELT_FREE_BIT) != 0;
91 heap_offset (heap_elt_t * e)
93 return e->offset & ~HEAP_ELT_FREE_BIT;
96 always_inline heap_elt_t *
97 heap_next (heap_elt_t * e)
102 always_inline heap_elt_t *
103 heap_prev (heap_elt_t * e)
109 heap_elt_size (void *v, heap_elt_t * e)
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);
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)
122 /* Header for heaps. */
125 /* Vector of used and free elements. */
128 /* For elt_bytes < sizeof (u32) we need some extra space
129 per elt to store free list index. */
130 u32 *small_free_elt_free_index;
132 /* Vector of free indices of elts array. */
135 /* Indices of free elts indexed by size bin. */
138 format_function_t *format_elt;
140 /* Used for validation/debugging. */
141 uword *used_elt_bitmap;
143 /* First and last element of doubly linked chain of elements. */
146 u32 used_count, max_len;
148 /* Number of bytes in a help element. */
152 /* Static heaps are made from external memory given to
153 us by user and are not re-sizable vectors. */
154 #define HEAP_IS_STATIC (1)
157 /* Start of heap elements is always cache aligned. */
158 #define HEAP_DATA_ALIGN (CLIB_CACHE_LINE_BYTES)
160 always_inline heap_header_t *
161 heap_header (void *v)
163 return vec_header (v);
167 heap_dup_header (heap_header_t * old, heap_header_t * new)
172 new->elts = vec_dup (new->elts);
173 new->free_elts = vec_dup (new->free_elts);
174 new->free_lists = vec_dup (new->free_lists);
175 for (i = 0; i < vec_len (new->free_lists); i++)
176 new->free_lists[i] = vec_dup (new->free_lists[i]);
177 new->used_elt_bitmap = clib_bitmap_dup (new->used_elt_bitmap);
178 new->small_free_elt_free_index = vec_dup (new->small_free_elt_free_index);
181 /* Make a duplicate copy of a heap. */
182 #define heap_dup(v) _heap_dup(v, vec_len (v) * sizeof (v[0]))
185 _heap_dup (void *v_old, uword v_bytes)
187 heap_header_t *h_old, *h_new;
188 vec_attr_t va = { .align = HEAP_DATA_ALIGN,
189 .hdr_sz = sizeof (heap_header_t),
193 h_old = heap_header (v_old);
198 v_new = _vec_alloc_internal (_vec_len (v_old), &va);
199 h_new = heap_header (v_new);
200 heap_dup_header (h_old, h_new);
201 clib_memcpy_fast (v_new, v_old, v_bytes);
208 heap_header_t *h = heap_header (v);
209 return h->used_count;
212 uword heap_bytes (void *v);
215 _heap_new (u32 len, u32 n_elt_bytes)
217 vec_attr_t va = { .align = HEAP_DATA_ALIGN,
218 .hdr_sz = sizeof (heap_header_t),
219 .elt_sz = n_elt_bytes };
220 void *v = _vec_alloc_internal (len, &va);
221 heap_header (v)->elt_bytes = n_elt_bytes;
225 #define heap_new(v) (v) = _heap_new (0, sizeof ((v)[0]))
228 heap_set_format (void *v, format_function_t * format_elt)
231 heap_header (v)->format_elt = format_elt;
235 heap_set_max_len (void *v, uword max_len)
238 heap_header (v)->max_len = max_len;
242 heap_get_max_len (void *v)
244 return v ? heap_header (v)->max_len : 0;
247 /* Execute BODY for each allocated heap element. */
248 #define heap_foreach(var,len,heap,body) \
250 if (vec_len (heap) > 0) \
252 heap_header_t * _h = heap_header (heap); \
253 heap_elt_t * _e = _h->elts + _h->head; \
254 heap_elt_t * _end = _h->elts + _h->tail; \
257 if (! heap_is_free (_e)) \
259 (var) = (heap) + heap_offset (_e); \
260 (len) = heap_elt_size ((heap), _e); \
261 do { body; } while (0); \
265 _e = heap_next (_e); \
270 #define heap_elt_at_index(v,index) vec_elt_at_index(v,index)
272 always_inline heap_elt_t *
273 heap_get_elt (void *v, uword handle)
275 heap_header_t *h = heap_header (v);
276 heap_elt_t *e = vec_elt_at_index (h->elts, handle);
277 ASSERT (!heap_is_free (e));
281 #define heap_elt_with_handle(v,handle) \
283 heap_elt_t * _e = heap_get_elt ((v), (handle)); \
284 (v) + heap_offset (_e); \
288 heap_is_free_handle (void *v, uword heap_handle)
290 heap_header_t *h = heap_header (v);
291 heap_elt_t *e = vec_elt_at_index (h->elts, heap_handle);
292 return heap_is_free (e);
295 extern uword heap_len (void *v, word handle);
297 /* Low level allocation call. */
298 extern void *_heap_alloc (void *v, uword size, uword alignment,
299 uword elt_bytes, uword * offset, uword * handle);
301 #define heap_alloc_aligned(v,size,align,handle) \
304 uword _a = (align); \
306 (v) = _heap_alloc ((v), _s, _a, sizeof ((v)[0]), &_o, &_h); \
311 #define heap_alloc(v,size,handle) heap_alloc_aligned((v),(size),0,(handle))
313 extern void heap_dealloc (void *v, uword handle);
314 extern void heap_validate (void *v);
316 /* Format heap internal data structures as string. */
317 extern u8 *format_heap (u8 * s, va_list * va);
319 void *_heap_free (void *v);
321 #define heap_free(v) (v)=_heap_free(v)
323 #endif /* included_heap_h */
326 * fd.io coding-style-patch-verification: ON
329 * eval: (c-set-style "gnu")