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 : #include <vppinfra/cache.h> /* for CLIB_CACHE_LINE_BYTES */
39 : #include <vppinfra/mem.h>
40 : #include <vppinfra/hash.h>
41 : #include <vppinfra/vec.h>
42 : #include <vppinfra/heap.h>
43 : #include <vppinfra/error.h>
44 :
45 : always_inline heap_elt_t *
46 425362 : elt_at (heap_header_t * h, uword i)
47 : {
48 425362 : ASSERT (i < vec_len (h->elts));
49 425362 : return h->elts + i;
50 : }
51 :
52 : always_inline heap_elt_t *
53 285376 : last (heap_header_t * h)
54 : {
55 285376 : return elt_at (h, h->tail);
56 : }
57 :
58 : always_inline heap_elt_t *
59 0 : first (heap_header_t * h)
60 : {
61 0 : return elt_at (h, h->head);
62 : }
63 :
64 : /* Objects sizes are binned into N_BINS bins.
65 : Objects with size <= SMALL_BINS have their own bins.
66 : Larger objects are grouped together in power or 2 sized
67 : bins.
68 :
69 : Sizes are in units of elt_bytes bytes. */
70 :
71 : /* Convert size to bin. */
72 : always_inline uword
73 396900 : size_to_bin (uword size)
74 : {
75 : uword bin;
76 :
77 396900 : ASSERT (size > 0);
78 :
79 396900 : if (size <= HEAP_SMALL_BINS)
80 : {
81 370461 : bin = size - 1;
82 370461 : if (size == 0)
83 0 : bin = 0;
84 : }
85 : else
86 : {
87 26439 : bin = HEAP_SMALL_BINS + max_log2 (size) - (HEAP_LOG2_SMALL_BINS + 1);
88 26439 : if (bin >= HEAP_N_BINS)
89 0 : bin = HEAP_N_BINS - 1;
90 : }
91 :
92 396900 : return bin;
93 : }
94 :
95 : /* Convert bin to size. */
96 : always_inline __attribute__ ((unused))
97 : uword bin_to_size (uword bin)
98 : {
99 : uword size;
100 :
101 : if (bin <= HEAP_SMALL_BINS - 1)
102 : size = bin + 1;
103 : else
104 : size = (uword) 1 << ((bin - HEAP_SMALL_BINS) + HEAP_LOG2_SMALL_BINS + 1);
105 :
106 : return size;
107 : }
108 :
109 : static void
110 16130 : elt_delete (heap_header_t * h, heap_elt_t * e)
111 : {
112 16130 : heap_elt_t *l = vec_end (h->elts) - 1;
113 :
114 16130 : ASSERT (e >= h->elts && e <= l);
115 :
116 : /* Update doubly linked pointers. */
117 : {
118 16130 : heap_elt_t *p = heap_prev (e);
119 16130 : heap_elt_t *n = heap_next (e);
120 :
121 16130 : if (p == e)
122 : {
123 0 : n->prev = 0;
124 0 : h->head = n - h->elts;
125 : }
126 16130 : else if (n == e)
127 : {
128 5426 : p->next = 0;
129 5426 : h->tail = p - h->elts;
130 : }
131 : else
132 : {
133 10704 : p->next = n - p;
134 10704 : n->prev = p - n;
135 : }
136 : }
137 :
138 : /* Add to index free list or delete from end. */
139 16130 : if (e < l)
140 11107 : vec_add1 (h->free_elts, e - h->elts);
141 : else
142 5023 : vec_dec_len (h->elts, 1);
143 16130 : }
144 :
145 : /*
146 : Before: P ... E
147 : After : P ... NEW ... E
148 : */
149 : always_inline void
150 7880 : elt_insert_before (heap_header_t * h, heap_elt_t * e, heap_elt_t * new)
151 : {
152 7880 : heap_elt_t *p = heap_prev (e);
153 :
154 7880 : if (p == e)
155 : {
156 3561 : new->prev = 0;
157 3561 : new->next = e - new;
158 3561 : p->prev = new - p;
159 3561 : h->head = new - h->elts;
160 : }
161 : else
162 : {
163 4319 : new->prev = p - new;
164 4319 : new->next = e - new;
165 4319 : e->prev = new - e;
166 4319 : p->next = new - p;
167 : }
168 7880 : }
169 :
170 : /*
171 : Before: E ... N
172 : After : E ... NEW ... N
173 : */
174 : always_inline void
175 292704 : elt_insert_after (heap_header_t * h, heap_elt_t * e, heap_elt_t * new)
176 : {
177 292704 : heap_elt_t *n = heap_next (e);
178 :
179 292704 : if (n == e)
180 : {
181 290354 : new->next = 0;
182 290354 : new->prev = e - new;
183 290354 : e->next = new - e;
184 290354 : h->tail = new - h->elts;
185 : }
186 : else
187 : {
188 2350 : new->prev = e - new;
189 2350 : new->next = n - new;
190 2350 : e->next = new - e;
191 2350 : n->prev = new - n;
192 : }
193 292704 : }
194 :
195 : always_inline heap_elt_t *
196 300584 : elt_new (heap_header_t * h)
197 : {
198 : heap_elt_t *e;
199 : uword l;
200 300584 : if ((l = vec_len (h->free_elts)) > 0)
201 : {
202 9441 : e = elt_at (h, h->free_elts[l - 1]);
203 9441 : vec_dec_len (h->free_elts, 1);
204 : }
205 : else
206 291143 : vec_add2 (h->elts, e, 1);
207 300584 : return e;
208 : }
209 :
210 : /* Return pointer to object at given offset.
211 : Used to write free list index of free objects. */
212 : always_inline u32 *
213 85494 : elt_data (void *v, heap_elt_t * e)
214 : {
215 85494 : heap_header_t *h = heap_header (v);
216 85494 : return v + heap_offset (e) * h->elt_bytes;
217 : }
218 :
219 : always_inline void
220 54533 : set_free_elt (void *v, heap_elt_t * e, uword fi)
221 : {
222 54533 : heap_header_t *h = heap_header (v);
223 :
224 54533 : e->offset |= HEAP_ELT_FREE_BIT;
225 54533 : if (h->elt_bytes >= sizeof (u32))
226 : {
227 53817 : *elt_data (v, e) = fi;
228 : }
229 : else
230 : {
231 : /* For elt_bytes < 4 we must store free index in separate
232 : vector. */
233 716 : uword elt_index = e - h->elts;
234 716 : vec_validate (h->small_free_elt_free_index, elt_index);
235 716 : h->small_free_elt_free_index[elt_index] = fi;
236 : }
237 54533 : }
238 :
239 : always_inline uword
240 32269 : get_free_elt (void *v, heap_elt_t * e, uword * bin_result)
241 : {
242 32269 : heap_header_t *h = heap_header (v);
243 : uword fb, fi;
244 :
245 32269 : ASSERT (heap_is_free (e));
246 32269 : fb = size_to_bin (heap_elt_size (v, e));
247 :
248 32269 : if (h->elt_bytes >= sizeof (u32))
249 : {
250 31677 : fi = *elt_data (v, e);
251 : }
252 : else
253 : {
254 592 : uword elt_index = e - h->elts;
255 592 : fi = vec_elt (h->small_free_elt_free_index, elt_index);
256 : }
257 :
258 32269 : *bin_result = fb;
259 32269 : return fi;
260 : }
261 :
262 : always_inline void
263 49262 : remove_free_block (void *v, uword b, uword i)
264 : {
265 49262 : heap_header_t *h = heap_header (v);
266 : uword l;
267 :
268 49262 : ASSERT (b < vec_len (h->free_lists));
269 49262 : ASSERT (i < vec_len (h->free_lists[b]));
270 :
271 49262 : l = vec_len (h->free_lists[b]);
272 :
273 49262 : if (i < l - 1)
274 : {
275 2259 : uword t = h->free_lists[b][l - 1];
276 2259 : h->free_lists[b][i] = t;
277 2259 : set_free_elt (v, elt_at (h, t), i);
278 : }
279 49262 : vec_set_len (h->free_lists[b], l - 1);
280 49262 : }
281 :
282 : static heap_elt_t *
283 318508 : search_free_list (void *v, uword size)
284 : {
285 318508 : heap_header_t *h = heap_header (v);
286 : heap_elt_t *f, *u;
287 : uword b, fb, f_size, f_index;
288 : word s, l;
289 :
290 318508 : if (!v)
291 6151 : return 0;
292 :
293 : /* Search free lists for bins >= given size. */
294 352381 : for (b = size_to_bin (size); b < vec_len (h->free_lists); b++)
295 73156 : if ((l = vec_len (h->free_lists[b])) > 0)
296 : {
297 : /* Find an object that is large enough.
298 : Search list in reverse so that more recently freed objects will be
299 : allocated again sooner. */
300 33132 : u8 found = 0;
301 : do
302 : {
303 33132 : l--;
304 33132 : f_index = h->free_lists[b][l];
305 33132 : f = elt_at (h, f_index);
306 33132 : f_size = heap_elt_size (v, f);
307 33132 : if ((s = f_size - size) >= 0)
308 : {
309 33132 : found = 1;
310 33132 : break;
311 : }
312 : }
313 0 : while (l > 0);
314 :
315 : /* If we fail to find a large enough object, try the next larger size. */
316 33132 : if (found == 0)
317 0 : continue;
318 :
319 33132 : ASSERT (heap_is_free (f));
320 :
321 : /* Link in used object (u) after free object (f). */
322 33132 : if (s == 0)
323 : {
324 25804 : u = f;
325 25804 : fb = HEAP_N_BINS;
326 : }
327 : else
328 : {
329 7328 : u = elt_new (h);
330 7328 : f = elt_at (h, f_index);
331 7328 : elt_insert_after (h, f, u);
332 7328 : fb = size_to_bin (s);
333 : }
334 :
335 33132 : u->offset = heap_offset (f) + s;
336 :
337 33132 : if (fb != b)
338 : {
339 33132 : if (fb < HEAP_N_BINS)
340 : {
341 : uword i;
342 7328 : vec_validate (h->free_lists, fb);
343 7328 : i = vec_len (h->free_lists[fb]);
344 7328 : vec_add1 (h->free_lists[fb], f - h->elts);
345 7328 : set_free_elt (v, f, i);
346 : }
347 :
348 33132 : remove_free_block (v, b, l);
349 : }
350 :
351 33132 : return u;
352 : }
353 :
354 279225 : return 0;
355 : }
356 :
357 : static void combine_free_blocks (void *v, heap_elt_t * e0, heap_elt_t * e1);
358 :
359 : static inline void
360 37057 : dealloc_elt (void *v, heap_elt_t * e)
361 : {
362 37057 : heap_header_t *h = heap_header (v);
363 : uword b, l;
364 : heap_elt_t *n, *p;
365 :
366 37057 : b = size_to_bin (heap_elt_size (v, e));
367 37057 : vec_validate (h->free_lists, b);
368 37057 : l = vec_len (h->free_lists[b]);
369 37057 : vec_add1 (h->free_lists[b], e - h->elts);
370 37057 : set_free_elt (v, e, l);
371 :
372 : /* See if we can combine the block we just freed with neighboring free blocks. */
373 37057 : p = heap_prev (e);
374 37057 : if (!heap_is_free (p))
375 23763 : p = e;
376 :
377 37057 : n = heap_next (e);
378 37057 : if (!heap_is_free (n))
379 7067 : n = e;
380 :
381 37057 : if (p != n)
382 7889 : combine_free_blocks (v, p, n);
383 37057 : }
384 :
385 : __clib_export void *
386 318508 : _heap_alloc (void *v,
387 : uword size,
388 : uword align,
389 : uword elt_bytes, uword * offset_return, uword * handle_return)
390 : {
391 318508 : uword offset = 0, align_size;
392 : heap_header_t *h;
393 : heap_elt_t *e;
394 :
395 318508 : if (size == 0)
396 0 : goto error;
397 :
398 : /* Round up alignment to power of 2. */
399 318508 : if (align <= 1)
400 : {
401 318508 : align = 0;
402 318508 : align_size = size;
403 : }
404 : else
405 : {
406 0 : align = max_pow2 (align);
407 0 : align_size = size + align - 1;
408 : }
409 :
410 318508 : e = search_free_list (v, align_size);
411 :
412 : /* If nothing found on free list, allocate object from end of vector. */
413 318508 : if (!e)
414 : {
415 : uword max_len;
416 285376 : vec_attr_t va = { .elt_sz = elt_bytes,
417 : .hdr_sz = sizeof (h[0]),
418 : .align = HEAP_DATA_ALIGN };
419 :
420 285376 : offset = vec_len (v);
421 285376 : max_len = heap_get_max_len (v);
422 :
423 285376 : if (max_len && offset + align_size > max_len)
424 0 : goto error;
425 :
426 285376 : h = heap_header (v);
427 285376 : if (!v || !(h->flags & HEAP_IS_STATIC))
428 285376 : v = _vec_realloc_internal (v, offset + align_size, &va);
429 : else
430 0 : vec_inc_len (v, align_size);
431 :
432 285376 : if (offset == 0)
433 : {
434 6151 : h = heap_header (v);
435 6151 : h->elt_bytes = elt_bytes;
436 : }
437 : }
438 :
439 318508 : h = heap_header (v);
440 :
441 : /* Add new element to doubly linked chain of elements. */
442 318508 : if (!e)
443 : {
444 285376 : e = elt_new (h);
445 285376 : e->offset = offset;
446 285376 : elt_insert_after (h, last (h), e);
447 : }
448 :
449 318508 : if (align > 0)
450 : {
451 : uword e_index;
452 : uword new_offset, old_offset;
453 :
454 0 : old_offset = e->offset;
455 0 : new_offset = (old_offset + align - 1) & ~(align - 1);
456 0 : e->offset = new_offset;
457 0 : e_index = e - h->elts;
458 :
459 : /* Free fragments before and after aligned object. */
460 0 : if (new_offset > old_offset)
461 : {
462 0 : heap_elt_t *before_e = elt_new (h);
463 0 : before_e->offset = old_offset;
464 0 : elt_insert_before (h, h->elts + e_index, before_e);
465 0 : dealloc_elt (v, before_e);
466 : }
467 :
468 0 : if (new_offset + size < old_offset + align_size)
469 : {
470 0 : heap_elt_t *after_e = elt_new (h);
471 0 : after_e->offset = new_offset + size;
472 0 : elt_insert_after (h, h->elts + e_index, after_e);
473 0 : dealloc_elt (v, after_e);
474 : }
475 :
476 0 : e = h->elts + e_index;
477 : }
478 :
479 318508 : h->used_count++;
480 :
481 : /* Keep track of used elements when debugging.
482 : This allows deallocation to check that passed objects are valid. */
483 : if (CLIB_DEBUG > 0)
484 : {
485 318508 : uword handle = e - h->elts;
486 318508 : ASSERT (!clib_bitmap_get (h->used_elt_bitmap, handle));
487 318508 : h->used_elt_bitmap = clib_bitmap_ori (h->used_elt_bitmap, handle);
488 : }
489 :
490 318508 : *offset_return = e->offset;
491 318508 : *handle_return = e - h->elts;
492 318508 : return v;
493 :
494 0 : error:
495 0 : *offset_return = *handle_return = ~0;
496 0 : return v;
497 : }
498 :
499 : __clib_export void
500 37057 : heap_dealloc (void *v, uword handle)
501 : {
502 37057 : heap_header_t *h = heap_header (v);
503 : heap_elt_t *e;
504 :
505 37057 : ASSERT (handle < vec_len (h->elts));
506 :
507 : /* For debugging we keep track of indices for valid objects.
508 : We make sure user is not trying to free object with an invalid index. */
509 : if (CLIB_DEBUG > 0)
510 : {
511 37057 : ASSERT (clib_bitmap_get (h->used_elt_bitmap, handle));
512 37057 : h->used_elt_bitmap = clib_bitmap_andnoti (h->used_elt_bitmap, handle);
513 : }
514 :
515 37057 : h->used_count--;
516 :
517 37057 : e = h->elts + handle;
518 37057 : ASSERT (!heap_is_free (e));
519 :
520 37057 : dealloc_elt (v, e);
521 37057 : }
522 :
523 : /* While freeing objects at INDEX we noticed free blocks i0 <= index and
524 : i1 >= index. We combine these two or three blocks into one big free block. */
525 : static void
526 7889 : combine_free_blocks (void *v, heap_elt_t * e0, heap_elt_t * e1)
527 : {
528 7889 : heap_header_t *h = heap_header (v);
529 : uword total_size, i, b, tb, ti, i_last, g_offset;
530 : heap_elt_t *e;
531 :
532 : struct
533 : {
534 : u32 index;
535 : u32 bin;
536 : u32 bin_index;
537 : } f[3], g;
538 :
539 : /* Compute total size of free objects i0 through i1. */
540 7889 : total_size = 0;
541 16139 : for (i = 0, e = e0; 1; e = heap_next (e), i++)
542 : {
543 16139 : ASSERT (i < ARRAY_LEN (f));
544 :
545 16139 : ti = get_free_elt (v, e, &tb);
546 :
547 16139 : ASSERT (tb < vec_len (h->free_lists));
548 16139 : ASSERT (ti < vec_len (h->free_lists[tb]));
549 :
550 16139 : f[i].index = h->free_lists[tb][ti];
551 16139 : f[i].bin = tb;
552 16139 : f[i].bin_index = ti;
553 :
554 16139 : total_size += heap_elt_size (v, elt_at (h, f[i].index));
555 :
556 16139 : if (e == e1)
557 : {
558 7889 : i_last = i;
559 7889 : break;
560 : }
561 : }
562 :
563 : /* Compute combined bin. See if all objects can be
564 : combined into existing bin. */
565 7889 : b = size_to_bin (total_size);
566 7889 : g.index = g.bin_index = 0;
567 24010 : for (i = 0; i <= i_last; i++)
568 16130 : if (b == f[i].bin)
569 : {
570 9 : g = f[i];
571 9 : break;
572 : }
573 :
574 : /* Make sure we found a bin. */
575 7889 : if (i > i_last)
576 : {
577 7880 : g.index = elt_new (h) - h->elts;
578 7880 : vec_validate (h->free_lists, b);
579 7880 : g.bin_index = vec_len (h->free_lists[b]);
580 7880 : vec_add1 (h->free_lists[b], g.index);
581 7880 : elt_insert_before (h, elt_at (h, f[0].index), elt_at (h, g.index));
582 : }
583 :
584 7889 : g_offset = elt_at (h, f[0].index)->offset;
585 :
586 : /* Delete unused bins. */
587 24028 : for (i = 0; i <= i_last; i++)
588 16139 : if (g.index != f[i].index)
589 : {
590 16130 : ti = get_free_elt (v, elt_at (h, f[i].index), &tb);
591 16130 : remove_free_block (v, tb, ti);
592 16130 : elt_delete (h, elt_at (h, f[i].index));
593 : }
594 :
595 : /* Initialize new element. */
596 7889 : elt_at (h, g.index)->offset = g_offset;
597 7889 : set_free_elt (v, elt_at (h, g.index), g.bin_index);
598 7889 : }
599 :
600 : __clib_export uword
601 0 : heap_len (void *v, word handle)
602 : {
603 0 : heap_header_t *h = heap_header (v);
604 :
605 : if (CLIB_DEBUG > 0)
606 0 : ASSERT (clib_bitmap_get (h->used_elt_bitmap, handle));
607 0 : return heap_elt_size (v, elt_at (h, handle));
608 : }
609 :
610 : __clib_export void *
611 12201 : _heap_free (void *v)
612 : {
613 12201 : heap_header_t *h = heap_header (v);
614 : uword b;
615 :
616 12201 : if (!v)
617 12201 : return v;
618 :
619 0 : clib_bitmap_free (h->used_elt_bitmap);
620 0 : for (b = 0; b < vec_len (h->free_lists); b++)
621 0 : vec_free (h->free_lists[b]);
622 0 : vec_free (h->free_lists);
623 0 : vec_free (h->elts);
624 0 : vec_free (h->free_elts);
625 0 : vec_free (h->small_free_elt_free_index);
626 0 : if (!(h->flags & HEAP_IS_STATIC))
627 0 : vec_free (v);
628 0 : return v;
629 : }
630 :
631 : uword
632 0 : heap_bytes (void *v)
633 : {
634 0 : heap_header_t *h = heap_header (v);
635 : uword bytes, b;
636 :
637 0 : if (!v)
638 0 : return 0;
639 :
640 0 : bytes = sizeof (h[0]);
641 0 : bytes += vec_len (v) * sizeof (h->elt_bytes);
642 0 : for (b = 0; b < vec_len (h->free_lists); b++)
643 0 : bytes += vec_mem_size (h->free_lists[b]);
644 0 : bytes += vec_bytes (h->free_lists);
645 0 : bytes += vec_mem_size (h->elts);
646 0 : bytes += vec_mem_size (h->free_elts);
647 0 : bytes += vec_bytes (h->used_elt_bitmap);
648 :
649 0 : return bytes;
650 : }
651 :
652 : static u8 *
653 0 : debug_elt (u8 * s, void *v, word i, word n)
654 : {
655 : heap_elt_t *e, *e0, *e1;
656 0 : heap_header_t *h = heap_header (v);
657 : word j;
658 :
659 0 : if (vec_len (h->elts) == 0)
660 0 : return s;
661 :
662 0 : if (i < 0)
663 0 : e0 = first (h);
664 : else
665 : {
666 0 : e0 = h->elts + i;
667 0 : for (j = 0; j < n / 2; j++)
668 0 : e0 = heap_prev (e0);
669 : }
670 :
671 0 : if (n < 0)
672 0 : e1 = h->elts + h->tail;
673 : else
674 : {
675 0 : e1 = h->elts + i;
676 0 : for (j = 0; j < n / 2; j++)
677 0 : e1 = heap_next (e1);
678 : }
679 :
680 0 : i = -n / 2;
681 0 : for (e = e0; 1; e = heap_next (e))
682 : {
683 0 : if (heap_is_free (e))
684 0 : s = format (s, "index %4d, free\n", e - h->elts);
685 0 : else if (h->format_elt)
686 0 : s = format (s, "%U", h->format_elt, v, elt_data (v, e));
687 : else
688 0 : s = format (s, "index %4d, used\n", e - h->elts);
689 0 : i++;
690 0 : if (e == e1)
691 0 : break;
692 : }
693 :
694 0 : return s;
695 : }
696 :
697 : __clib_export u8 *
698 0 : format_heap (u8 *s, va_list *va)
699 : {
700 0 : void *v = va_arg (*va, void *);
701 0 : uword verbose = va_arg (*va, uword);
702 0 : heap_header_t *h = heap_header (v);
703 : heap_header_t zero;
704 :
705 0 : clib_memset (&zero, 0, sizeof (zero));
706 :
707 0 : if (!v)
708 0 : h = &zero;
709 :
710 : {
711 0 : f64 elt_bytes = vec_len (v) * h->elt_bytes;
712 0 : f64 overhead_bytes = heap_bytes (v);
713 :
714 0 : s = format (s, "heap %p, %6d objects, size %.1fk + overhead %.1fk\n",
715 : v, h->used_count, elt_bytes / 1024,
716 0 : (overhead_bytes - elt_bytes) / 1024);
717 : }
718 :
719 0 : if (v && verbose)
720 0 : s = debug_elt (s, v, -1, -1);
721 :
722 0 : return s;
723 : }
724 :
725 : __clib_export void
726 0 : heap_validate (void *v)
727 : {
728 0 : heap_header_t *h = heap_header (v);
729 : uword i, o, s;
730 : u8 *free_map;
731 : heap_elt_t *e, *n;
732 :
733 : uword used_count, total_size;
734 : uword free_count, free_size;
735 :
736 0 : ASSERT (h->used_count == clib_bitmap_count_set_bits (h->used_elt_bitmap));
737 :
738 0 : ASSERT (first (h)->prev == 0);
739 0 : ASSERT (last (h)->next == 0);
740 :
741 : /* Validate number of elements and size. */
742 0 : free_size = free_count = 0;
743 0 : for (i = 0; i < vec_len (h->free_lists); i++)
744 : {
745 0 : free_count += vec_len (h->free_lists[i]);
746 0 : for (o = 0; o < vec_len (h->free_lists[i]); o++)
747 : {
748 0 : e = h->elts + h->free_lists[i][o];
749 0 : s = heap_elt_size (v, e);
750 0 : ASSERT (size_to_bin (s) == i);
751 0 : ASSERT (heap_is_free (e));
752 0 : free_size += s;
753 : }
754 : }
755 :
756 : {
757 : uword elt_free_size, elt_free_count;
758 :
759 0 : used_count = total_size = elt_free_size = elt_free_count = 0;
760 0 : for (e = first (h); 1; e = n)
761 0 : {
762 0 : int is_free = heap_is_free (e);
763 0 : used_count++;
764 0 : s = heap_elt_size (v, e);
765 0 : total_size += s;
766 0 : ASSERT (is_free ==
767 : !clib_bitmap_get (h->used_elt_bitmap, e - h->elts));
768 0 : if (is_free)
769 : {
770 0 : elt_free_count++;
771 0 : elt_free_size += s;
772 : }
773 0 : n = heap_next (e);
774 0 : if (e == n)
775 : {
776 0 : ASSERT (last (h) == n);
777 0 : break;
778 : }
779 :
780 : /* We should never have two free adjacent elements. */
781 0 : ASSERT (!(heap_is_free (e) && heap_is_free (n)));
782 : }
783 :
784 0 : ASSERT (free_count == elt_free_count);
785 0 : ASSERT (free_size == elt_free_size);
786 0 : ASSERT (used_count == h->used_count + free_count);
787 0 : ASSERT (total_size == vec_len (v));
788 : }
789 :
790 0 : free_map = vec_new (u8, used_count);
791 :
792 0 : e = first (h);
793 0 : for (i = o = 0; 1; i++)
794 : {
795 0 : ASSERT (heap_offset (e) == o);
796 0 : s = heap_elt_size (v, e);
797 :
798 0 : if (heap_is_free (e))
799 : {
800 : uword fb, fi;
801 :
802 0 : fi = get_free_elt (v, e, &fb);
803 :
804 0 : ASSERT (fb < vec_len (h->free_lists));
805 0 : ASSERT (fi < vec_len (h->free_lists[fb]));
806 0 : ASSERT (h->free_lists[fb][fi] == e - h->elts);
807 :
808 0 : ASSERT (!free_map[i]);
809 0 : free_map[i] = 1;
810 : }
811 :
812 0 : n = heap_next (e);
813 :
814 0 : if (e == n)
815 0 : break;
816 :
817 0 : ASSERT (heap_prev (n) == e);
818 :
819 0 : o += s;
820 0 : e = n;
821 : }
822 :
823 0 : vec_free (free_map);
824 0 : }
825 :
826 : /*
827 : * fd.io coding-style-patch-verification: ON
828 : *
829 : * Local Variables:
830 : * eval: (c-set-style "gnu")
831 : * End:
832 : */
|
