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 #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>
45 always_inline heap_elt_t * elt_at (heap_header_t * h, uword i)
47 ASSERT (i < vec_len (h->elts));
51 always_inline heap_elt_t * last (heap_header_t * h)
52 { return elt_at (h, h->tail); }
54 always_inline heap_elt_t * first (heap_header_t * h)
55 { return elt_at (h, h->head); }
57 /* Objects sizes are binned into N_BINS bins.
58 Objects with size <= SMALL_BINS have their own bins.
59 Larger objects are grouped together in power or 2 sized
62 Sizes are in units of elt_bytes bytes. */
64 /* Convert size to bin. */
65 always_inline uword size_to_bin (uword size)
71 if (size <= HEAP_SMALL_BINS)
79 bin = HEAP_SMALL_BINS + max_log2 (size) - (HEAP_LOG2_SMALL_BINS + 1);
80 if (bin >= HEAP_N_BINS)
81 bin = HEAP_N_BINS - 1;
87 /* Convert bin to size. */
88 always_inline __attribute__((unused)) uword bin_to_size (uword bin)
92 if (bin <= HEAP_SMALL_BINS - 1)
95 size = (uword) 1 << ((bin - HEAP_SMALL_BINS) + HEAP_LOG2_SMALL_BINS + 1);
100 static void elt_delete (heap_header_t * h, heap_elt_t * e)
102 heap_elt_t * l = vec_end (h->elts) - 1;
104 ASSERT (e >= h->elts && e <= l);
106 /* Update doubly linked pointers. */
108 heap_elt_t * p = heap_prev (e);
109 heap_elt_t * n = heap_next (e);
114 h->head = n - h->elts;
119 h->tail = p - h->elts;
128 /* Add to index free list or delete from end. */
130 vec_add1 (h->free_elts, e - h->elts);
132 _vec_len (h->elts)--;
137 After : P ... NEW ... E
139 always_inline void elt_insert_before (heap_header_t * h, heap_elt_t * e, heap_elt_t * new)
141 heap_elt_t * p = heap_prev (e);
148 h->head = new - h->elts;
161 After : E ... NEW ... N
163 always_inline void elt_insert_after (heap_header_t * h, heap_elt_t * e, heap_elt_t * new)
165 heap_elt_t * n = heap_next (e);
172 h->tail = new - h->elts;
183 always_inline heap_elt_t * elt_new (heap_header_t * h)
187 if ((l = vec_len (h->free_elts)) > 0)
189 e = elt_at (h, h->free_elts[l-1]);
190 _vec_len (h->free_elts) -= 1;
193 vec_add2 (h->elts, e, 1);
197 /* Return pointer to object at given offset.
198 Used to write free list index of free objects. */
199 always_inline u32 * elt_data (void * v, heap_elt_t * e)
201 heap_header_t * h = heap_header (v);
202 return v + heap_offset (e) * h->elt_bytes;
206 set_free_elt (void * v, heap_elt_t * e, uword fi)
208 heap_header_t * h = heap_header (v);
210 e->offset |= HEAP_ELT_FREE_BIT;
211 if (h->elt_bytes >= sizeof (u32))
213 *elt_data (v, e) = fi;
217 /* For elt_bytes < 4 we must store free index in separate
219 uword elt_index = e - h->elts;
220 vec_validate (h->small_free_elt_free_index, elt_index);
221 h->small_free_elt_free_index[elt_index] = fi;
226 get_free_elt (void * v, heap_elt_t * e, uword * bin_result)
228 heap_header_t * h = heap_header (v);
231 ASSERT (heap_is_free (e));
232 fb = size_to_bin (heap_elt_size (v, e));
234 if (h->elt_bytes >= sizeof (u32))
236 fi = *elt_data (v, e);
240 uword elt_index = e - h->elts;
241 fi = vec_elt (h->small_free_elt_free_index, elt_index);
248 always_inline void remove_free_block (void * v, uword b, uword i)
250 heap_header_t * h = heap_header (v);
253 ASSERT (b < vec_len (h->free_lists));
254 ASSERT (i < vec_len (h->free_lists[b]));
256 l = vec_len (h->free_lists[b]);
260 uword t = h->free_lists[b][l - 1];
261 h->free_lists[b][i] = t;
262 set_free_elt (v, elt_at (h, t), i);
264 _vec_len (h->free_lists[b]) = l - 1;
267 static heap_elt_t * search_free_list (void * v, uword size)
269 heap_header_t * h = heap_header (v);
271 uword b, fb, f_size, f_index;
277 /* Search free lists for bins >= given size. */
278 for (b = size_to_bin (size); b < vec_len (h->free_lists); b++)
279 if ((l = vec_len (h->free_lists[b])) > 0)
281 /* Find an object that is large enough.
282 Search list in reverse so that more recently freed objects will be
283 allocated again sooner. */
286 f_index = h->free_lists[b][l];
287 f = elt_at (h, f_index);
288 f_size = heap_elt_size (v, f);
289 if ((s = f_size - size) >= 0)
293 /* If we fail to find a large enough object, try the next larger size. */
297 ASSERT (heap_is_free (f));
299 /* Link in used object (u) after free object (f). */
308 f = elt_at (h, f_index);
309 elt_insert_after (h, f, u);
310 fb = size_to_bin (s);
313 u->offset = heap_offset (f) + s;
317 if (fb < HEAP_N_BINS)
320 vec_validate (h->free_lists, fb);
321 i = vec_len (h->free_lists[fb]);
322 vec_add1 (h->free_lists[fb], f - h->elts);
323 set_free_elt (v, f, i);
326 remove_free_block (v, b, l);
335 static void combine_free_blocks (void * v, heap_elt_t * e0, heap_elt_t * e1);
337 static inline void dealloc_elt (void * v, heap_elt_t * e)
339 heap_header_t * h = heap_header (v);
343 b = size_to_bin (heap_elt_size (v, e));
344 vec_validate (h->free_lists, b);
345 l = vec_len (h->free_lists[b]);
346 vec_add1 (h->free_lists[b], e - h->elts);
347 set_free_elt (v, e, l);
349 /* See if we can combine the block we just freed with neighboring free blocks. */
351 if (! heap_is_free (p))
355 if (! heap_is_free (n))
359 combine_free_blocks (v, p, n);
362 void * _heap_alloc (void * v,
366 uword * offset_return,
367 uword * handle_return)
369 uword offset = 0, align_size;
376 /* Round up alignment to power of 2. */
384 align = max_pow2 (align);
385 align_size = size + align - 1;
388 e = search_free_list (v, align_size);
390 /* If nothing found on free list, allocate object from end of vector. */
395 offset = vec_len (v);
396 max_len = heap_get_max_len (v);
398 if (max_len && offset + align_size > max_len)
402 if (! v || ! (h->flags & HEAP_IS_STATIC))
405 (offset + align_size) * elt_bytes,
409 _vec_len (v) += align_size;
414 h->elt_bytes = elt_bytes;
420 /* Add new element to doubly linked chain of elements. */
425 elt_insert_after (h, last (h), e);
431 uword new_offset, old_offset;
433 old_offset = e->offset;
434 new_offset = (old_offset + align - 1) &~ (align - 1);
435 e->offset = new_offset;
436 e_index = e - h->elts;
438 /* Free fragments before and after aligned object. */
439 if (new_offset > old_offset)
441 heap_elt_t * before_e = elt_new (h);
442 before_e->offset = old_offset;
443 elt_insert_before (h, h->elts + e_index, before_e);
444 dealloc_elt (v, before_e);
447 if (new_offset + size < old_offset + align_size)
449 heap_elt_t * after_e = elt_new (h);
450 after_e->offset = new_offset + size;
451 elt_insert_after (h, h->elts + e_index, after_e);
452 dealloc_elt (v, after_e);
455 e = h->elts + e_index;
460 /* Keep track of used elements when debugging.
461 This allows deallocation to check that passed objects are valid. */
464 uword handle = e - h->elts;
465 ASSERT (! clib_bitmap_get (h->used_elt_bitmap, handle));
466 h->used_elt_bitmap = clib_bitmap_ori (h->used_elt_bitmap, handle);
469 *offset_return = e->offset;
470 *handle_return = e - h->elts;
474 *offset_return = *handle_return = ~0;
478 void heap_dealloc (void * v, uword handle)
480 heap_header_t * h = heap_header (v);
483 ASSERT (handle < vec_len (h->elts));
485 /* For debugging we keep track of indices for valid objects.
486 We make sure user is not trying to free object with an invalid index. */
489 ASSERT (clib_bitmap_get (h->used_elt_bitmap, handle));
490 h->used_elt_bitmap = clib_bitmap_andnoti (h->used_elt_bitmap, handle);
495 e = h->elts + handle;
496 ASSERT (! heap_is_free (e));
501 /* While freeing objects at INDEX we noticed free blocks i0 <= index and
502 i1 >= index. We combine these two or three blocks into one big free block. */
503 static void combine_free_blocks (void * v, heap_elt_t * e0, heap_elt_t * e1)
505 heap_header_t * h = heap_header (v);
506 uword total_size, i, b, tb, ti, i_last, g_offset;
515 /* Compute total size of free objects i0 through i1. */
517 for (i = 0, e = e0; 1; e = heap_next (e), i++)
519 ASSERT (i < ARRAY_LEN (f));
521 ti = get_free_elt (v, e, &tb);
523 ASSERT (tb < vec_len (h->free_lists));
524 ASSERT (ti < vec_len (h->free_lists[tb]));
526 f[i].index = h->free_lists[tb][ti];
530 total_size += heap_elt_size (v, elt_at (h, f[i].index));
539 /* Compute combined bin. See if all objects can be
540 combined into existing bin. */
541 b = size_to_bin (total_size);
542 g.index = g.bin_index = 0;
543 for (i = 0; i <= i_last; i++)
550 /* Make sure we found a bin. */
553 g.index = elt_new (h) - h->elts;
554 vec_validate (h->free_lists, b);
555 g.bin_index = vec_len (h->free_lists[b]);
556 vec_add1 (h->free_lists[b], g.index);
557 elt_insert_before (h, elt_at (h, f[0].index), elt_at (h, g.index));
560 g_offset = elt_at (h, f[0].index)->offset;
562 /* Delete unused bins. */
563 for (i = 0; i <= i_last; i++)
564 if (g.index != f[i].index)
566 ti = get_free_elt (v, elt_at (h, f[i].index), &tb);
567 remove_free_block (v, tb, ti);
568 elt_delete (h, elt_at (h, f[i].index));
571 /* Initialize new element. */
572 elt_at (h, g.index)->offset = g_offset;
573 set_free_elt (v, elt_at (h, g.index), g.bin_index);
576 uword heap_len (void * v, word handle)
578 heap_header_t * h = heap_header (v);
581 ASSERT (clib_bitmap_get (h->used_elt_bitmap, handle));
582 return heap_elt_size (v, elt_at (h, handle));
585 void * _heap_free (void * v)
587 heap_header_t * h = heap_header (v);
593 clib_bitmap_free (h->used_elt_bitmap);
594 for (b = 0; b < vec_len (h->free_lists); b++)
595 vec_free (h->free_lists[b]);
596 vec_free (h->free_lists);
598 vec_free (h->free_elts);
599 vec_free (h->small_free_elt_free_index);
600 if (! (h->flags & HEAP_IS_STATIC))
601 vec_free_h (v, sizeof (h[0]));
605 uword heap_bytes (void * v)
607 heap_header_t * h = heap_header (v);
613 bytes = sizeof (h[0]);
614 bytes += vec_len (v) * sizeof (h->elt_bytes);
615 for (b = 0; b < vec_len (h->free_lists); b++)
616 bytes += vec_capacity (h->free_lists[b], 0);
617 bytes += vec_bytes (h->free_lists);
618 bytes += vec_capacity (h->elts, 0);
619 bytes += vec_capacity (h->free_elts, 0);
620 bytes += vec_bytes (h->used_elt_bitmap);
625 static u8 * debug_elt (u8 * s, void * v, word i, word n)
627 heap_elt_t * e, * e0, * e1;
628 heap_header_t * h = heap_header (v);
631 if (vec_len (h->elts) == 0)
639 for (j = 0; j < n/2; j++)
644 e1 = h->elts + h->tail;
648 for (j = 0; j < n/2; j++)
653 for (e = e0; 1; e = heap_next (e))
655 if (heap_is_free (e))
656 s = format (s, "index %4d, free\n", e - h->elts);
657 else if (h->format_elt)
658 s = format (s, "%U", h->format_elt, v, elt_data (v, e));
660 s = format (s, "index %4d, used\n", e - h->elts);
669 u8 * format_heap (u8 * s, va_list * va)
671 void * v = va_arg (*va, void *);
672 uword verbose = va_arg (*va, uword);
673 heap_header_t * h = heap_header (v);
676 memset (&zero, 0, sizeof (zero));
682 f64 elt_bytes = vec_len (v) * h->elt_bytes;
683 f64 overhead_bytes = heap_bytes (v);
685 s = format (s, "heap %p, %6d objects, size %.1fk + overhead %.1fk\n",
686 v, h->used_count, elt_bytes / 1024, (overhead_bytes - elt_bytes) / 1024);
690 s = debug_elt (s, v, -1, -1);
695 void heap_validate (void * v)
697 heap_header_t * h = heap_header (v);
702 uword used_count, total_size;
703 uword free_count, free_size;
705 ASSERT (h->used_count == clib_bitmap_count_set_bits (h->used_elt_bitmap));
707 ASSERT (first(h)->prev == 0);
708 ASSERT (last(h)->next == 0);
710 /* Validate number of elements and size. */
711 free_size = free_count = 0;
712 for (i = 0; i < vec_len (h->free_lists); i++)
714 free_count += vec_len (h->free_lists[i]);
715 for (o = 0; o < vec_len (h->free_lists[i]); o++)
717 e = h->elts + h->free_lists[i][o];
718 s = heap_elt_size (v, e);
719 ASSERT (size_to_bin (s) == i);
720 ASSERT (heap_is_free (e));
726 uword elt_free_size, elt_free_count;
728 used_count = total_size = elt_free_size = elt_free_count = 0;
729 for (e = first (h); 1; e = n)
731 int is_free = heap_is_free (e);
733 s = heap_elt_size (v, e);
735 ASSERT (is_free == ! clib_bitmap_get (h->used_elt_bitmap, e - h->elts));
744 ASSERT (last (h) == n);
748 /* We should never have two free adjacent elements. */
749 ASSERT (! (heap_is_free (e) && heap_is_free (n)));
752 ASSERT (free_count == elt_free_count);
753 ASSERT (free_size == elt_free_size);
754 ASSERT (used_count == h->used_count + free_count);
755 ASSERT (total_size == vec_len (v));
758 free_map = vec_new (u8, used_count);
761 for (i = o = 0; 1; i++)
763 ASSERT (heap_offset (e) == o);
764 s = heap_elt_size (v, e);
766 if (heap_is_free (e))
770 fi = get_free_elt (v, e, &fb);
772 ASSERT (fb < vec_len (h->free_lists));
773 ASSERT (fi < vec_len (h->free_lists[fb]));
774 ASSERT (h->free_lists[fb][fi] == e - h->elts);
776 ASSERT (! free_map[i]);
785 ASSERT (heap_prev (n) == e);