Line data Source code
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. */
75 : u32 offset;
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 :
84 : always_inline uword
85 176572 : heap_is_free (heap_elt_t * e)
86 : {
87 176572 : return (e->offset & HEAP_ELT_FREE_BIT) != 0;
88 : }
89 :
90 : always_inline uword
91 284886 : heap_offset (heap_elt_t * e)
92 : {
93 284886 : return e->offset & ~HEAP_ELT_FREE_BIT;
94 : }
95 :
96 : always_inline heap_elt_t *
97 472738 : heap_next (heap_elt_t * e)
98 : {
99 472738 : return e + e->next;
100 : }
101 :
102 : always_inline heap_elt_t *
103 61067 : heap_prev (heap_elt_t * e)
104 : {
105 61067 : return e + e->prev;
106 : }
107 :
108 : always_inline uword
109 118597 : heap_elt_size (void *v, heap_elt_t * e)
110 : {
111 118597 : heap_elt_t *n = heap_next (e);
112 118597 : uword next_offset = n != e ? heap_offset (n) : vec_len (v);
113 118597 : 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. */
126 : heap_elt_t *elts;
127 :
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;
131 :
132 : /* Vector of free indices of elts array. */
133 : u32 *free_elts;
134 :
135 : /* Indices of free elts indexed by size bin. */
136 : u32 **free_lists;
137 :
138 : format_function_t *format_elt;
139 :
140 : /* Used for validation/debugging. */
141 : uword *used_elt_bitmap;
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. */
149 : u32 elt_bytes;
150 :
151 : u32 flags;
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)
155 : } heap_header_t;
156 :
157 : /* Start of heap elements is always cache aligned. */
158 : #define HEAP_DATA_ALIGN (CLIB_CACHE_LINE_BYTES)
159 :
160 : always_inline heap_header_t *
161 1523530 : heap_header (void *v)
162 : {
163 1523530 : return vec_header (v);
164 : }
165 :
166 : always_inline void
167 : heap_dup_header (heap_header_t * old, heap_header_t * new)
168 : {
169 : uword i;
170 :
171 : new[0] = old[0];
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);
179 : }
180 :
181 : /* Make a duplicate copy of a heap. */
182 : #define heap_dup(v) _heap_dup(v, vec_len (v) * sizeof (v[0]))
183 :
184 : always_inline void *
185 : _heap_dup (void *v_old, uword v_bytes)
186 : {
187 : heap_header_t *h_old, *h_new;
188 : vec_attr_t va = { .align = HEAP_DATA_ALIGN,
189 : .hdr_sz = sizeof (heap_header_t),
190 : .elt_sz = 1 };
191 : void *v_new;
192 :
193 : h_old = heap_header (v_old);
194 :
195 : if (!v_old)
196 : return v_old;
197 :
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);
202 : return v_new;
203 : }
204 :
205 : always_inline uword
206 : heap_elts (void *v)
207 : {
208 : heap_header_t *h = heap_header (v);
209 : return h->used_count;
210 : }
211 :
212 : uword heap_bytes (void *v);
213 :
214 : always_inline void *
215 0 : _heap_new (u32 len, u32 n_elt_bytes)
216 : {
217 0 : vec_attr_t va = { .align = HEAP_DATA_ALIGN,
218 : .hdr_sz = sizeof (heap_header_t),
219 : .elt_sz = n_elt_bytes };
220 0 : void *v = _vec_alloc_internal (len, &va);
221 0 : heap_header (v)->elt_bytes = n_elt_bytes;
222 0 : return v;
223 : }
224 :
225 : #define heap_new(v) (v) = _heap_new (0, sizeof ((v)[0]))
226 :
227 : always_inline void
228 : heap_set_format (void *v, format_function_t * format_elt)
229 : {
230 : ASSERT (v);
231 : heap_header (v)->format_elt = format_elt;
232 : }
233 :
234 : always_inline void
235 : heap_set_max_len (void *v, uword max_len)
236 : {
237 : ASSERT (v);
238 : heap_header (v)->max_len = max_len;
239 : }
240 :
241 : always_inline uword
242 285376 : heap_get_max_len (void *v)
243 : {
244 285376 : return v ? heap_header (v)->max_len : 0;
245 : }
246 :
247 : /* Execute BODY for each allocated heap element. */
248 : #define heap_foreach(var,len,heap,body) \
249 : do { \
250 : if (vec_len (heap) > 0) \
251 : { \
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; \
255 : while (1) \
256 : { \
257 : if (! heap_is_free (_e)) \
258 : { \
259 : (var) = (heap) + heap_offset (_e); \
260 : (len) = heap_elt_size ((heap), _e); \
261 : do { body; } while (0); \
262 : } \
263 : if (_e == _end) \
264 : break; \
265 : _e = heap_next (_e); \
266 : } \
267 : } \
268 : } while (0)
269 :
270 : #define heap_elt_at_index(v,index) vec_elt_at_index(v,index)
271 :
272 : always_inline heap_elt_t *
273 : heap_get_elt (void *v, uword handle)
274 : {
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));
278 : return e;
279 : }
280 :
281 : #define heap_elt_with_handle(v,handle) \
282 : ({ \
283 : heap_elt_t * _e = heap_get_elt ((v), (handle)); \
284 : (v) + heap_offset (_e); \
285 : })
286 :
287 : always_inline uword
288 : heap_is_free_handle (void *v, uword heap_handle)
289 : {
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);
293 : }
294 :
295 : extern uword heap_len (void *v, word handle);
296 :
297 : /* Low level allocation call. */
298 : extern void *_heap_alloc (void *v, uword size, uword alignment,
299 : uword elt_bytes, uword * offset, uword * handle);
300 :
301 : #define heap_alloc_aligned(v,size,align,handle) \
302 : ({ \
303 : uword _o, _h; \
304 : uword _a = (align); \
305 : uword _s = (size); \
306 : (v) = _heap_alloc ((v), _s, _a, sizeof ((v)[0]), &_o, &_h); \
307 : (handle) = _h; \
308 : _o; \
309 : })
310 :
311 : #define heap_alloc(v,size,handle) heap_alloc_aligned((v),(size),0,(handle))
312 :
313 : extern void heap_dealloc (void *v, uword handle);
314 : extern void heap_validate (void *v);
315 :
316 : /* Format heap internal data structures as string. */
317 : extern u8 *format_heap (u8 * s, va_list * va);
318 :
319 : void *_heap_free (void *v);
320 :
321 : #define heap_free(v) (v)=_heap_free(v)
322 :
323 : #endif /* included_heap_h */
324 :
325 : /*
326 : * fd.io coding-style-patch-verification: ON
327 : *
328 : * Local Variables:
329 : * eval: (c-set-style "gnu")
330 : * End:
331 : */
|
