summaryrefslogtreecommitdiffstats
path: root/src/vppinfra/mheap.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/vppinfra/mheap.c')
-rw-r--r--src/vppinfra/mheap.c1683
1 files changed, 0 insertions, 1683 deletions
diff --git a/src/vppinfra/mheap.c b/src/vppinfra/mheap.c
deleted file mode 100644
index b5566bd6389..00000000000
--- a/src/vppinfra/mheap.c
+++ /dev/null
@@ -1,1683 +0,0 @@
-/*
- * Copyright (c) 2015 Cisco and/or its affiliates.
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at:
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-/*
- Copyright (c) 2001, 2002, 2003 Eliot Dresselhaus
-
- Permission is hereby granted, free of charge, to any person obtaining
- a copy of this software and associated documentation files (the
- "Software"), to deal in the Software without restriction, including
- without limitation the rights to use, copy, modify, merge, publish,
- distribute, sublicense, and/or sell copies of the Software, and to
- permit persons to whom the Software is furnished to do so, subject to
- the following conditions:
-
- The above copyright notice and this permission notice shall be
- included in all copies or substantial portions of the Software.
-
- THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
- EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
- MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
- NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
- LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
- OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
- WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
-*/
-
-#include <vppinfra/bitops.h>
-#include <vppinfra/hash.h>
-#include <vppinfra/format.h>
-#include <vppinfra/mheap.h>
-#include <vppinfra/os.h>
-#include <vppinfra/time.h>
-#include <vppinfra/lock.h>
-
-#ifdef CLIB_UNIX
-#include <vppinfra/elf_clib.h>
-#endif
-
-static void mheap_get_trace (void *v, uword offset, uword size);
-static void mheap_put_trace (void *v, uword offset, uword size);
-static int mheap_trace_sort (const void *t1, const void *t2);
-
-always_inline void
-mheap_maybe_lock (void *v)
-{
- mheap_t *h = mheap_header (v);
- if (v && (h->flags & MHEAP_FLAG_THREAD_SAFE))
- {
- u32 my_cpu = os_get_thread_index ();
- if (h->owner_cpu == my_cpu)
- {
- h->recursion_count++;
- return;
- }
-
- while (clib_atomic_test_and_set (&h->lock))
- CLIB_PAUSE ();
-
- h->owner_cpu = my_cpu;
- h->recursion_count = 1;
- }
-}
-
-always_inline void
-mheap_maybe_unlock (void *v)
-{
- mheap_t *h = mheap_header (v);
- if (v && h->flags & MHEAP_FLAG_THREAD_SAFE)
- {
- ASSERT (os_get_thread_index () == h->owner_cpu);
- if (--h->recursion_count == 0)
- {
- h->owner_cpu = ~0;
- clib_atomic_release (&h->lock);
- }
- }
-}
-
-/* Find bin for objects with size at least n_user_data_bytes. */
-always_inline uword
-user_data_size_to_bin_index (uword n_user_data_bytes)
-{
- uword n_user_data_words;
- word small_bin, large_bin;
-
- /* User size must be at least big enough to hold free elt. */
- n_user_data_bytes = clib_max (n_user_data_bytes, MHEAP_MIN_USER_DATA_BYTES);
-
- /* Round to words. */
- n_user_data_words =
- (round_pow2 (n_user_data_bytes, MHEAP_USER_DATA_WORD_BYTES) /
- MHEAP_USER_DATA_WORD_BYTES);
-
- ASSERT (n_user_data_words > 0);
- small_bin =
- n_user_data_words -
- (MHEAP_MIN_USER_DATA_BYTES / MHEAP_USER_DATA_WORD_BYTES);
- ASSERT (small_bin >= 0);
-
- large_bin =
- MHEAP_N_SMALL_OBJECT_BINS + max_log2 (n_user_data_bytes) -
- MHEAP_LOG2_N_SMALL_OBJECT_BINS;
-
- return small_bin < MHEAP_N_SMALL_OBJECT_BINS ? small_bin : large_bin;
-}
-
-always_inline uword
-mheap_elt_size_to_user_n_bytes (uword n_bytes)
-{
- ASSERT (n_bytes >= sizeof (mheap_elt_t));
- return (n_bytes - STRUCT_OFFSET_OF (mheap_elt_t, user_data));
-}
-
-always_inline uword __attribute__ ((unused))
-mheap_elt_size_to_user_n_words (uword n_bytes)
-{
- ASSERT (n_bytes % MHEAP_USER_DATA_WORD_BYTES == 0);
- return mheap_elt_size_to_user_n_bytes (n_bytes) /
- MHEAP_USER_DATA_WORD_BYTES;
-}
-
-always_inline void
-mheap_elt_set_size (void *v,
- uword uoffset, uword n_user_data_bytes, uword is_free)
-{
- mheap_elt_t *e, *n;
-
- e = mheap_elt_at_uoffset (v, uoffset);
-
- ASSERT (n_user_data_bytes % MHEAP_USER_DATA_WORD_BYTES == 0);
-
- e->n_user_data = n_user_data_bytes / MHEAP_USER_DATA_WORD_BYTES;
- e->is_free = is_free;
- ASSERT (e->prev_n_user_data * sizeof (e->user_data[0]) >=
- MHEAP_MIN_USER_DATA_BYTES);
-
- n = mheap_next_elt (e);
- n->prev_n_user_data = e->n_user_data;
- n->prev_is_free = is_free;
-}
-
-always_inline void
-set_first_free_elt_offset (mheap_t * h, uword bin, uword uoffset)
-{
- uword i0, i1;
-
- h->first_free_elt_uoffset_by_bin[bin] = uoffset;
-
- i0 = bin / BITS (h->non_empty_free_elt_heads[0]);
- i1 = (uword) 1 << (uword) (bin % BITS (h->non_empty_free_elt_heads[0]));
-
- ASSERT (i0 < ARRAY_LEN (h->non_empty_free_elt_heads));
- if (h->first_free_elt_uoffset_by_bin[bin] == MHEAP_GROUNDED)
- h->non_empty_free_elt_heads[i0] &= ~i1;
- else
- h->non_empty_free_elt_heads[i0] |= i1;
-}
-
-always_inline void
-set_free_elt (void *v, uword uoffset, uword n_user_data_bytes)
-{
- mheap_t *h = mheap_header (v);
- mheap_elt_t *e = mheap_elt_at_uoffset (v, uoffset);
- mheap_elt_t *n = mheap_next_elt (e);
- uword bin = user_data_size_to_bin_index (n_user_data_bytes);
-
- ASSERT (n->prev_is_free);
- ASSERT (e->is_free);
-
- e->free_elt.prev_uoffset = MHEAP_GROUNDED;
- e->free_elt.next_uoffset = h->first_free_elt_uoffset_by_bin[bin];
-
- /* Fill in next free elt's previous pointer. */
- if (e->free_elt.next_uoffset != MHEAP_GROUNDED)
- {
- mheap_elt_t *nf = mheap_elt_at_uoffset (v, e->free_elt.next_uoffset);
- ASSERT (nf->is_free);
- nf->free_elt.prev_uoffset = uoffset;
- }
-
- set_first_free_elt_offset (h, bin, uoffset);
-}
-
-always_inline void
-new_free_elt (void *v, uword uoffset, uword n_user_data_bytes)
-{
- mheap_elt_set_size (v, uoffset, n_user_data_bytes, /* is_free */ 1);
- set_free_elt (v, uoffset, n_user_data_bytes);
-}
-
-always_inline void
-remove_free_elt (void *v, mheap_elt_t * e, uword bin)
-{
- mheap_t *h = mheap_header (v);
- mheap_elt_t *p, *n;
-#if CLIB_VEC64 > 0
- u64 no, po;
-#else
- u32 no, po;
-#endif
-
- no = e->free_elt.next_uoffset;
-
- n = no != MHEAP_GROUNDED ? mheap_elt_at_uoffset (v, no) : 0;
- po = e->free_elt.prev_uoffset;
- p = po != MHEAP_GROUNDED ? mheap_elt_at_uoffset (v, po) : 0;
-
- if (!p)
- set_first_free_elt_offset (h, bin, no);
- else
- p->free_elt.next_uoffset = no;
-
- if (n)
- n->free_elt.prev_uoffset = po;
-}
-
-always_inline void
-remove_free_elt2 (void *v, mheap_elt_t * e)
-{
- uword bin;
- bin = user_data_size_to_bin_index (mheap_elt_data_bytes (e));
- remove_free_elt (v, e, bin);
-}
-
-#define MHEAP_VM_MAP (1 << 0)
-#define MHEAP_VM_UNMAP (1 << 1)
-#define MHEAP_VM_NOMAP (0 << 1)
-#define MHEAP_VM_ROUND (1 << 2)
-#define MHEAP_VM_ROUND_UP MHEAP_VM_ROUND
-#define MHEAP_VM_ROUND_DOWN (0 << 2)
-
-static uword mheap_page_size;
-
-static_always_inline uword
-mheap_page_round (uword addr)
-{
- return (addr + mheap_page_size - 1) & ~(mheap_page_size - 1);
-}
-
-static_always_inline uword
-mheap_page_truncate (uword addr)
-{
- return addr & ~(mheap_page_size - 1);
-}
-
-static_always_inline uword
-mheap_vm (void *v, uword flags, clib_address_t start_addr, uword size)
-{
- mheap_t *h = mheap_header (v);
- clib_address_t start_page, end_page, end_addr;
- uword mapped_bytes;
-
- ASSERT (!(h->flags & MHEAP_FLAG_DISABLE_VM));
-
- end_addr = start_addr + size;
-
- /* Round start/end address up to page boundary. */
- start_page = mheap_page_round (start_addr);
-
- if ((flags & MHEAP_VM_ROUND) == MHEAP_VM_ROUND_UP)
- end_page = mheap_page_round (end_addr);
- else
- end_page = mheap_page_truncate (end_addr);
-
- mapped_bytes = 0;
- if (end_page > start_page)
- {
- mapped_bytes = end_page - start_page;
- if (flags & MHEAP_VM_MAP)
- clib_mem_vm_map ((void *) start_page, end_page - start_page);
- else if (flags & MHEAP_VM_UNMAP)
- clib_mem_vm_unmap ((void *) start_page, end_page - start_page);
- }
-
- return mapped_bytes;
-}
-
-static_always_inline uword
-mheap_vm_elt (void *v, uword flags, uword offset)
-{
- mheap_elt_t *e;
- clib_address_t start_addr, end_addr;
-
- e = mheap_elt_at_uoffset (v, offset);
- start_addr = (clib_address_t) ((void *) e->user_data);
- end_addr = (clib_address_t) mheap_next_elt (e);
- return mheap_vm (v, flags, start_addr, end_addr - start_addr);
-}
-
-always_inline uword
-mheap_small_object_cache_mask (mheap_small_object_cache_t * c, uword bin)
-{
- uword mask;
-
-/* $$$$ ELIOT FIXME: add Altivec version of this routine */
-#if !defined (CLIB_HAVE_VEC128) || defined (__ALTIVEC__) || defined (__i386__)
- mask = 0;
-#else
- u8x16 b = u8x16_splat (bin);
-
- ASSERT (bin < 256);
-
-#define _(i) ((uword) u8x16_compare_byte_mask ((b == c->bins.as_u8x16[i])) << (uword) ((i)*16))
- mask = _(0) | _(1);
- if (BITS (uword) > 32)
- mask |= _(2) | _(3);
-#undef _
-
-#endif
- return mask;
-}
-
-always_inline uword
-mheap_get_small_object (mheap_t * h, uword bin)
-{
- mheap_small_object_cache_t *c = &h->small_object_cache;
- uword mask = mheap_small_object_cache_mask (c, bin + 1);
- uword offset = MHEAP_GROUNDED;
-
- if (mask)
- {
- uword i = min_log2 (mask);
- uword o = c->offsets[i];
- ASSERT (o != MHEAP_GROUNDED);
- c->bins.as_u8[i] = 0;
- offset = o;
- }
-
- return offset;
-}
-
-always_inline uword
-mheap_put_small_object (mheap_t * h, uword bin, uword offset)
-{
- mheap_small_object_cache_t *c = &h->small_object_cache;
- uword free_mask = mheap_small_object_cache_mask (c, 0);
- uword b = bin + 1;
- uword i;
-
- if (free_mask != 0)
- {
- i = min_log2 (free_mask);
- c->bins.as_u8[i] = b;
- c->offsets[i] = offset;
- return 0;
- }
- else
- /* Nothing free with right size: cyclic replacement. */
- {
- uword old_offset;
-
- i = c->replacement_index++;
- i %= BITS (uword);
- c->bins.as_u8[i] = b;
- old_offset = c->offsets[i];
- c->offsets[i] = offset;
-
- /* Return old offset so it can be freed. */
- return old_offset;
- }
-}
-
-static uword
-mheap_get_search_free_bin (void *v,
- uword bin,
- uword * n_user_data_bytes_arg,
- uword align, uword align_offset)
-{
- mheap_t *h = mheap_header (v);
- mheap_elt_t *e;
-
- /* Free object is at offset f0 ... f1;
- Allocatted object is at offset o0 ... o1. */
- word o0, o1, f0, f1, search_n_user_data_bytes;
- word lo_free_usize, hi_free_usize;
-
- ASSERT (h->first_free_elt_uoffset_by_bin[bin] != MHEAP_GROUNDED);
- e = mheap_elt_at_uoffset (v, h->first_free_elt_uoffset_by_bin[bin]);
-
- search_n_user_data_bytes = *n_user_data_bytes_arg;
-
- /* Silence compiler warning. */
- o0 = o1 = f0 = f1 = 0;
-
- h->stats.free_list.n_search_attempts += 1;
-
- /* Find an object that is large enough with correct alignment at given alignment offset. */
- while (1)
- {
- uword this_object_n_user_data_bytes = mheap_elt_data_bytes (e);
-
- ASSERT (e->is_free);
- if (bin < MHEAP_N_SMALL_OBJECT_BINS)
- ASSERT (this_object_n_user_data_bytes >= search_n_user_data_bytes);
-
- h->stats.free_list.n_objects_searched += 1;
-
- if (this_object_n_user_data_bytes < search_n_user_data_bytes)
- goto next;
-
- /* Bounds of free object: from f0 to f1. */
- f0 = ((void *) e->user_data - v);
- f1 = f0 + this_object_n_user_data_bytes;
-
- /* Place candidate object at end of free block and align as requested. */
- o0 = ((f1 - search_n_user_data_bytes) & ~(align - 1)) - align_offset;
- while (o0 < f0)
- o0 += align;
-
- /* Make sure that first free fragment is either empty or
- large enough to be valid. */
- while (1)
- {
- lo_free_usize = o0 != f0 ? o0 - f0 - MHEAP_ELT_OVERHEAD_BYTES : 0;
- if (o0 <= f0 || lo_free_usize >= (word) MHEAP_MIN_USER_DATA_BYTES)
- break;
- o0 -= align;
- }
-
- o1 = o0 + search_n_user_data_bytes;
-
- /* Does it fit? */
- if (o0 >= f0 && o1 <= f1)
- goto found;
-
- next:
- /* Reached end of free list without finding large enough object. */
- if (e->free_elt.next_uoffset == MHEAP_GROUNDED)
- return MHEAP_GROUNDED;
-
- /* Otherwise keep searching for large enough object. */
- e = mheap_elt_at_uoffset (v, e->free_elt.next_uoffset);
- }
-
-found:
- /* Free fragment at end. */
- hi_free_usize = f1 != o1 ? f1 - o1 - MHEAP_ELT_OVERHEAD_BYTES : 0;
-
- /* If fragment at end is too small to be a new object,
- give user's object a bit more space than requested. */
- if (hi_free_usize < (word) MHEAP_MIN_USER_DATA_BYTES)
- {
- search_n_user_data_bytes += f1 - o1;
- o1 = f1;
- hi_free_usize = 0;
- }
-
- /* Need to make sure that relevant memory areas are mapped. */
- if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
- {
- mheap_elt_t *f0_elt = mheap_elt_at_uoffset (v, f0);
- mheap_elt_t *f1_elt = mheap_elt_at_uoffset (v, f1);
- mheap_elt_t *o0_elt = mheap_elt_at_uoffset (v, o0);
- mheap_elt_t *o1_elt = mheap_elt_at_uoffset (v, o1);
-
- uword f0_page_start, f0_page_end;
- uword o0_page_start, o0_page_end;
-
- /* Free elt is mapped. Addresses after that may not be mapped. */
- f0_page_start = mheap_page_round (pointer_to_uword (f0_elt->user_data));
- f0_page_end = mheap_page_truncate (pointer_to_uword (f1_elt));
-
- o0_page_start = mheap_page_truncate (pointer_to_uword (o0_elt));
- o0_page_end = mheap_page_round (pointer_to_uword (o1_elt->user_data));
-
- if (o0_page_start < f0_page_start)
- o0_page_start = f0_page_start;
- if (o0_page_end > f0_page_end)
- o0_page_end = f0_page_end;
-
- if (o0_page_end > o0_page_start)
- clib_mem_vm_map (uword_to_pointer (o0_page_start, void *),
- o0_page_end - o0_page_start);
- }
-
- /* Remove free object from free list. */
- remove_free_elt (v, e, bin);
-
- /* Free fragment at begining. */
- if (lo_free_usize > 0)
- {
- ASSERT (lo_free_usize >= (word) MHEAP_MIN_USER_DATA_BYTES);
- mheap_elt_set_size (v, f0, lo_free_usize, /* is_free */ 1);
- new_free_elt (v, f0, lo_free_usize);
- }
-
- mheap_elt_set_size (v, o0, search_n_user_data_bytes, /* is_free */ 0);
-
- if (hi_free_usize > 0)
- {
- uword uo = o1 + MHEAP_ELT_OVERHEAD_BYTES;
- mheap_elt_set_size (v, uo, hi_free_usize, /* is_free */ 1);
- new_free_elt (v, uo, hi_free_usize);
- }
-
- /* Return actual size of block. */
- *n_user_data_bytes_arg = search_n_user_data_bytes;
-
- h->stats.free_list.n_objects_found += 1;
-
- return o0;
-}
-
-/* Search free lists for object with given size and alignment. */
-static uword
-mheap_get_search_free_list (void *v,
- uword * n_user_bytes_arg,
- uword align, uword align_offset)
-{
- mheap_t *h = mheap_header (v);
- uword bin, n_user_bytes, i, bi;
-
- n_user_bytes = *n_user_bytes_arg;
- bin = user_data_size_to_bin_index (n_user_bytes);
-
- if (MHEAP_HAVE_SMALL_OBJECT_CACHE
- && (h->flags & MHEAP_FLAG_SMALL_OBJECT_CACHE)
- && bin < 255
- && align == STRUCT_SIZE_OF (mheap_elt_t, user_data[0])
- && align_offset == 0)
- {
- uword r = mheap_get_small_object (h, bin);
- h->stats.n_small_object_cache_attempts += 1;
- if (r != MHEAP_GROUNDED)
- {
- h->stats.n_small_object_cache_hits += 1;
- return r;
- }
- }
-
- for (i = bin / BITS (uword); i < ARRAY_LEN (h->non_empty_free_elt_heads);
- i++)
- {
- uword non_empty_bin_mask = h->non_empty_free_elt_heads[i];
-
- /* No need to search smaller bins. */
- if (i == bin / BITS (uword))
- non_empty_bin_mask &= ~pow2_mask (bin % BITS (uword));
-
- /* Search each occupied free bin which is large enough. */
- /* *INDENT-OFF* */
- foreach_set_bit (bi, non_empty_bin_mask,
- ({
- uword r =
- mheap_get_search_free_bin (v, bi + i * BITS (uword),
- n_user_bytes_arg,
- align,
- align_offset);
- if (r != MHEAP_GROUNDED) return r;
- }));
- /* *INDENT-ON* */
- }
-
- return MHEAP_GROUNDED;
-}
-
-static never_inline void *
-mheap_get_extend_vector (void *v,
- uword n_user_data_bytes,
- uword align,
- uword align_offset, uword * offset_return)
-{
- /* Bounds of free and allocated objects (as above). */
- uword f0, f1, o0, o1;
- word free_size;
- mheap_t *h = mheap_header (v);
- mheap_elt_t *e;
-
- if (_vec_len (v) == 0)
- {
- _vec_len (v) = MHEAP_ELT_OVERHEAD_BYTES;
-
- /* Create first element of heap. */
- e = mheap_elt_at_uoffset (v, _vec_len (v));
- e->prev_n_user_data = MHEAP_N_USER_DATA_INVALID;
- }
-
- f0 = _vec_len (v);
-
- o0 = round_pow2 (f0, align) - align_offset;
- while (1)
- {
- free_size = o0 - f0 - MHEAP_ELT_OVERHEAD_BYTES;
- if (o0 == f0 || free_size >= (word) sizeof (mheap_elt_t))
- break;
-
- o0 += align;
- }
-
- o1 = o0 + n_user_data_bytes;
- f1 = o1 + MHEAP_ELT_OVERHEAD_BYTES;
-
- ASSERT (v != 0);
- h = mheap_header (v);
-
- /* Make sure we have space for object plus overhead. */
- if (f1 > h->max_size)
- {
- *offset_return = MHEAP_GROUNDED;
- return v;
- }
-
- _vec_len (v) = f1;
-
- if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
- {
- mheap_elt_t *f0_elt = mheap_elt_at_uoffset (v, f0);
- mheap_elt_t *f1_elt = mheap_elt_at_uoffset (v, f1);
-
- uword f0_page = mheap_page_round (pointer_to_uword (f0_elt->user_data));
- uword f1_page = mheap_page_round (pointer_to_uword (f1_elt->user_data));
-
- if (f1_page > f0_page)
- mheap_vm (v, MHEAP_VM_MAP, f0_page, f1_page - f0_page);
- }
-
- if (free_size > 0)
- new_free_elt (v, f0, free_size);
-
- mheap_elt_set_size (v, o0, n_user_data_bytes, /* is_free */ 0);
-
- /* Mark last element. */
- e = mheap_elt_at_uoffset (v, f1);
- e->n_user_data = MHEAP_N_USER_DATA_INVALID;
-
- *offset_return = o0;
-
- return v;
-}
-
-void *
-mheap_get_aligned (void *v,
- uword n_user_data_bytes,
- uword align, uword align_offset, uword * offset_return)
-{
- mheap_t *h;
- uword offset;
- u64 cpu_times[2];
-
- cpu_times[0] = clib_cpu_time_now ();
-
- align = clib_max (align, STRUCT_SIZE_OF (mheap_elt_t, user_data[0]));
- align = max_pow2 (align);
-
- /* Correct align offset to be smaller than alignment. */
- align_offset &= (align - 1);
-
- /* Align offset must be multiple of minimum object size. */
- if (align_offset % STRUCT_SIZE_OF (mheap_elt_t, user_data[0]) != 0)
- {
- *offset_return = MHEAP_GROUNDED;
- return v;
- }
-
- /*
- * Round requested size.
- *
- * Step 1: round up to the minimum object size.
- * Step 2: round up to a multiple of the user data size (e.g. 4)
- * Step 3: if non-trivial alignment requested, round up
- * so that the object precisely fills a chunk
- * as big as the alignment request.
- *
- * Step 3 prevents the code from going into "bin search hyperspace":
- * looking at a huge number of fractional remainder chunks, none of which
- * will satisfy the alignment constraint. This fixes an allocator
- * performance issue when one requests a large number of 16 byte objects
- * aligned to 64 bytes, to name one variation on the theme.
- */
- n_user_data_bytes = clib_max (n_user_data_bytes, MHEAP_MIN_USER_DATA_BYTES);
- n_user_data_bytes =
- round_pow2 (n_user_data_bytes,
- STRUCT_SIZE_OF (mheap_elt_t, user_data[0]));
- if (align > MHEAP_ELT_OVERHEAD_BYTES)
- n_user_data_bytes = clib_max (n_user_data_bytes,
- align - MHEAP_ELT_OVERHEAD_BYTES);
- if (!v)
- v = mheap_alloc (0, 64 << 20);
-
- mheap_maybe_lock (v);
-
- h = mheap_header (v);
-
- if (h->flags & MHEAP_FLAG_VALIDATE)
- mheap_validate (v);
-
- /* First search free lists for object. */
- offset =
- mheap_get_search_free_list (v, &n_user_data_bytes, align, align_offset);
-
- h = mheap_header (v);
-
- /* If that fails allocate object at end of heap by extending vector. */
- if (offset == MHEAP_GROUNDED && _vec_len (v) < h->max_size)
- {
- v =
- mheap_get_extend_vector (v, n_user_data_bytes, align, align_offset,
- &offset);
- h = mheap_header (v);
- h->stats.n_vector_expands += offset != MHEAP_GROUNDED;
- }
-
- *offset_return = offset;
- if (offset != MHEAP_GROUNDED)
- {
- h->n_elts += 1;
-
- if (h->flags & MHEAP_FLAG_TRACE)
- {
- /* Recursion block for case when we are traceing main clib heap. */
- h->flags &= ~MHEAP_FLAG_TRACE;
-
- mheap_get_trace (v, offset, n_user_data_bytes);
-
- h->flags |= MHEAP_FLAG_TRACE;
- }
- }
-
- if (h->flags & MHEAP_FLAG_VALIDATE)
- mheap_validate (v);
-
- mheap_maybe_unlock (v);
-
- cpu_times[1] = clib_cpu_time_now ();
- h->stats.n_clocks_get += cpu_times[1] - cpu_times[0];
- h->stats.n_gets += 1;
-
- return v;
-}
-
-static void
-free_last_elt (void *v, mheap_elt_t * e)
-{
- mheap_t *h = mheap_header (v);
-
- /* Possibly delete preceeding free element also. */
- if (e->prev_is_free)
- {
- e = mheap_prev_elt (e);
- remove_free_elt2 (v, e);
- }
-
- if (e->prev_n_user_data == MHEAP_N_USER_DATA_INVALID)
- {
- if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
- mheap_vm_elt (v, MHEAP_VM_UNMAP, mheap_elt_uoffset (v, e));
- _vec_len (v) = 0;
- }
- else
- {
- uword uo = mheap_elt_uoffset (v, e);
- if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
- mheap_vm_elt (v, MHEAP_VM_UNMAP, uo);
- e->n_user_data = MHEAP_N_USER_DATA_INVALID;
- _vec_len (v) = uo;
- }
-}
-
-void
-mheap_put (void *v, uword uoffset)
-{
- mheap_t *h;
- uword n_user_data_bytes, bin;
- mheap_elt_t *e, *n;
- uword trace_uoffset, trace_n_user_data_bytes;
- u64 cpu_times[2];
-
- cpu_times[0] = clib_cpu_time_now ();
-
- h = mheap_header (v);
-
- mheap_maybe_lock (v);
-
- if (h->flags & MHEAP_FLAG_VALIDATE)
- mheap_validate (v);
-
- ASSERT (h->n_elts > 0);
- h->n_elts--;
- h->stats.n_puts += 1;
-
- e = mheap_elt_at_uoffset (v, uoffset);
- n = mheap_next_elt (e);
- n_user_data_bytes = mheap_elt_data_bytes (e);
-
- trace_uoffset = uoffset;
- trace_n_user_data_bytes = n_user_data_bytes;
-
- bin = user_data_size_to_bin_index (n_user_data_bytes);
- if (MHEAP_HAVE_SMALL_OBJECT_CACHE
- && bin < 255 && (h->flags & MHEAP_FLAG_SMALL_OBJECT_CACHE))
- {
- uoffset = mheap_put_small_object (h, bin, uoffset);
- if (uoffset == 0)
- goto done;
-
- e = mheap_elt_at_uoffset (v, uoffset);
- n = mheap_next_elt (e);
- n_user_data_bytes = mheap_elt_data_bytes (e);
- }
-
- /* Assert that forward and back pointers are equal. */
- if (e->n_user_data != n->prev_n_user_data)
- os_panic ();
-
- /* Forward and backwards is_free must agree. */
- if (e->is_free != n->prev_is_free)
- os_panic ();
-
- /* Object was already freed. */
- if (e->is_free)
- os_panic ();
-
- /* Special case: delete last element in heap. */
- if (n->n_user_data == MHEAP_N_USER_DATA_INVALID)
- free_last_elt (v, e);
-
- else
- {
- uword f0, f1, n_combine;
-
- f0 = uoffset;
- f1 = f0 + n_user_data_bytes;
- n_combine = 0;
-
- if (e->prev_is_free)
- {
- mheap_elt_t *p = mheap_prev_elt (e);
- f0 = mheap_elt_uoffset (v, p);
- remove_free_elt2 (v, p);
- n_combine++;
- }
-
- if (n->is_free)
- {
- mheap_elt_t *m = mheap_next_elt (n);
- f1 = (void *) m - v;
- remove_free_elt2 (v, n);
- n_combine++;
- }
-
- if (n_combine)
- mheap_elt_set_size (v, f0, f1 - f0, /* is_free */ 1);
- else
- e->is_free = n->prev_is_free = 1;
- set_free_elt (v, f0, f1 - f0);
-
- if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
- mheap_vm_elt (v, MHEAP_VM_UNMAP, f0);
- }
-
-done:
- h = mheap_header (v);
-
- if (h->flags & MHEAP_FLAG_TRACE)
- {
- /* Recursion block for case when we are traceing main clib heap. */
- h->flags &= ~MHEAP_FLAG_TRACE;
-
- mheap_put_trace (v, trace_uoffset, trace_n_user_data_bytes);
-
- h->flags |= MHEAP_FLAG_TRACE;
- }
-
- if (h->flags & MHEAP_FLAG_VALIDATE)
- mheap_validate (v);
-
- mheap_maybe_unlock (v);
-
- cpu_times[1] = clib_cpu_time_now ();
- h->stats.n_clocks_put += cpu_times[1] - cpu_times[0];
-}
-
-void *
-mheap_alloc_with_flags (void *memory, uword memory_size, uword flags)
-{
- mheap_t *h;
- void *v;
- uword size;
-
- if (!mheap_page_size)
- mheap_page_size = clib_mem_get_page_size ();
-
- if (!memory)
- {
- /* No memory given, try to VM allocate some. */
- memory = clib_mem_vm_alloc (memory_size);
- if (!memory)
- return 0;
-
- /* No memory region implies we have virtual memory. */
- flags &= ~MHEAP_FLAG_DISABLE_VM;
- }
-
- /* Make sure that given memory is page aligned. */
- {
- uword am, av, ah;
-
- am = pointer_to_uword (memory);
- av = mheap_page_round (am);
- v = uword_to_pointer (av, void *);
- h = mheap_header (v);
- ah = pointer_to_uword (h);
- while (ah < am)
- ah += mheap_page_size;
-
- h = uword_to_pointer (ah, void *);
- v = mheap_vector (h);
-
- if (PREDICT_FALSE (memory + memory_size < v))
- {
- /*
- * This will happen when the requested memory_size is too
- * small to cope with the heap header and/or memory alignment.
- */
- clib_mem_vm_free (memory, memory_size);
- return 0;
- }
-
- size = memory + memory_size - v;
- }
-
- /* VM map header so we can use memory. */
- if (!(flags & MHEAP_FLAG_DISABLE_VM))
- clib_mem_vm_map (h, sizeof (h[0]));
-
- /* Zero vector header: both heap header and vector length. */
- clib_memset (h, 0, sizeof (h[0]));
- _vec_len (v) = 0;
-
- h->vm_alloc_offset_from_header = (void *) h - memory;
- h->vm_alloc_size = memory_size;
-
- h->max_size = size;
- h->owner_cpu = ~0;
-
- /* Set flags based on those given less builtin-flags. */
- h->flags |= (flags & ~MHEAP_FLAG_TRACE);
-
- /* Unmap remainder of heap until we will be ready to use it. */
- if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
- mheap_vm (v, MHEAP_VM_UNMAP | MHEAP_VM_ROUND_UP,
- (clib_address_t) v, h->max_size);
-
- /* Initialize free list heads to empty. */
- clib_memset (h->first_free_elt_uoffset_by_bin, 0xFF,
- sizeof (h->first_free_elt_uoffset_by_bin));
-
- return v;
-}
-
-void *
-mheap_alloc (void *memory, uword size)
-{
- uword flags = 0;
-
- if (memory != 0)
- flags |= MHEAP_FLAG_DISABLE_VM;
-
-#ifdef CLIB_HAVE_VEC128
- flags |= MHEAP_FLAG_SMALL_OBJECT_CACHE;
-#endif
-
- return mheap_alloc_with_flags (memory, size, flags);
-}
-
-void *
-mheap_alloc_with_lock (void *memory, uword size, int locked)
-{
- uword flags = 0;
- void *rv;
-
- if (memory != 0)
- flags |= MHEAP_FLAG_DISABLE_VM;
-
-#ifdef CLIB_HAVE_VEC128
- flags |= MHEAP_FLAG_SMALL_OBJECT_CACHE;
-#endif
-
- rv = mheap_alloc_with_flags (memory, size, flags);
-
- if (rv && locked)
- {
- mheap_t *h = mheap_header (rv);
- h->flags |= MHEAP_FLAG_THREAD_SAFE;
- }
- return rv;
-}
-
-void *
-_mheap_free (void *v)
-{
- mheap_t *h = mheap_header (v);
-
- if (v)
- clib_mem_vm_free ((void *) h - h->vm_alloc_offset_from_header,
- h->vm_alloc_size);
-
- return 0;
-}
-
-/* Call user's function with each object in heap. */
-void
-mheap_foreach (void *v,
- uword (*func) (void *arg, void *v, void *elt_data,
- uword elt_size), void *arg)
-{
- mheap_elt_t *e;
- u8 *stack_heap, *clib_mem_mheap_save;
- u8 tmp_heap_memory[16 * 1024];
-
- mheap_maybe_lock (v);
-
- if (vec_len (v) == 0)
- goto done;
-
- clib_mem_mheap_save = 0;
- stack_heap = 0;
-
- /* Allocate a new temporary heap on the stack.
- This is so that our hash table & user's callback function can
- themselves allocate memory somewhere without getting in the way
- of the heap we are looking at. */
- if (v == clib_mem_get_heap ())
- {
- stack_heap = mheap_alloc (tmp_heap_memory, sizeof (tmp_heap_memory));
- clib_mem_mheap_save = v;
- clib_mem_set_heap (stack_heap);
- }
-
- for (e = v;
- e->n_user_data != MHEAP_N_USER_DATA_INVALID; e = mheap_next_elt (e))
- {
- void *p = mheap_elt_data (v, e);
- if (e->is_free)
- continue;
- if ((*func) (arg, v, p, mheap_elt_data_bytes (e)))
- break;
- }
-
- /* Restore main CLIB heap. */
- if (clib_mem_mheap_save)
- clib_mem_set_heap (clib_mem_mheap_save);
-
-done:
- mheap_maybe_unlock (v);
-}
-
-/* Bytes in mheap header overhead not including data bytes. */
-always_inline uword
-mheap_bytes_overhead (void *v)
-{
- mheap_t *h = mheap_header (v);
- return v ? sizeof (h[0]) + h->n_elts * sizeof (mheap_elt_t) : 0;
-}
-
-/* Total number of bytes including both data and overhead. */
-uword
-mheap_bytes (void *v)
-{
- return mheap_bytes_overhead (v) + vec_bytes (v);
-}
-
-static void
-mheap_usage_no_lock (void *v, clib_mem_usage_t * usage)
-{
- mheap_t *h = mheap_header (v);
- uword used = 0, free = 0, free_vm_unmapped = 0;
-
- if (vec_len (v) > 0)
- {
- mheap_elt_t *e;
-
- for (e = v;
- e->n_user_data != MHEAP_N_USER_DATA_INVALID;
- e = mheap_next_elt (e))
- {
- uword size = mheap_elt_data_bytes (e);
- if (e->is_free)
- {
- free += size;
- if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
- free_vm_unmapped +=
- mheap_vm_elt (v, MHEAP_VM_NOMAP, mheap_elt_uoffset (v, e));
- }
- else
- used += size;
- }
- }
-
- usage->object_count = mheap_elts (v);
- usage->bytes_total = mheap_bytes (v);
- usage->bytes_overhead = mheap_bytes_overhead (v);
- usage->bytes_max = mheap_max_size (v);
- usage->bytes_used = used;
- usage->bytes_free = free;
- usage->bytes_free_reclaimed = free_vm_unmapped;
-}
-
-void
-mheap_usage (void *v, clib_mem_usage_t * usage)
-{
- mheap_maybe_lock (v);
- mheap_usage_no_lock (v, usage);
- mheap_maybe_unlock (v);
-}
-
-static u8 *
-format_mheap_byte_count (u8 * s, va_list * va)
-{
- uword n_bytes = va_arg (*va, uword);
- if (n_bytes < 1024)
- return format (s, "%wd", n_bytes);
- else
- return format (s, "%wdk", n_bytes / 1024);
-}
-
-/* Returns first corrupt heap element. */
-static mheap_elt_t *
-mheap_first_corrupt (void *v)
-{
- mheap_elt_t *e, *n;
-
- if (vec_len (v) == 0)
- return 0;
-
- e = v;
- while (1)
- {
- if (e->n_user_data == MHEAP_N_USER_DATA_INVALID)
- break;
-
- n = mheap_next_elt (e);
-
- if (e->n_user_data != n->prev_n_user_data)
- return e;
-
- if (e->is_free != n->prev_is_free)
- return e;
-
- e = n;
- }
-
- return 0;
-}
-
-static u8 *
-format_mheap_stats (u8 * s, va_list * va)
-{
- mheap_t *h = va_arg (*va, mheap_t *);
- mheap_stats_t *st = &h->stats;
- u32 indent = format_get_indent (s);
-
- s =
- format (s,
- "alloc. from small object cache: %Ld hits %Ld attempts (%.2f%%) replacements %d",
- st->n_small_object_cache_hits, st->n_small_object_cache_attempts,
- (st->n_small_object_cache_attempts !=
- 0 ? 100. * (f64) st->n_small_object_cache_hits /
- (f64) st->n_small_object_cache_attempts : 0.),
- h->small_object_cache.replacement_index);
-
- s =
- format (s,
- "\n%Ualloc. from free-list: %Ld attempts, %Ld hits (%.2f%%), %Ld considered (per-attempt %.2f)",
- format_white_space, indent, st->free_list.n_search_attempts,
- st->free_list.n_objects_found,
- (st->free_list.n_search_attempts !=
- 0 ? 100. * (f64) st->free_list.n_objects_found /
- (f64) st->free_list.n_search_attempts : 0.),
- st->free_list.n_objects_searched,
- (st->free_list.n_search_attempts !=
- 0 ? (f64) st->free_list.n_objects_searched /
- (f64) st->free_list.n_search_attempts : 0.));
-
- s = format (s, "\n%Ualloc. from vector-expand: %Ld",
- format_white_space, indent, st->n_vector_expands);
-
- s = format (s, "\n%Uallocs: %Ld %.2f clocks/call",
- format_white_space, indent,
- st->n_gets, (f64) st->n_clocks_get / (f64) st->n_gets);
-
- s = format (s, "\n%Ufrees: %Ld %.2f clocks/call",
- format_white_space, indent,
- st->n_puts, (f64) st->n_clocks_put / (f64) st->n_puts);
-
- return s;
-}
-
-u8 *
-format_mheap (u8 * s, va_list * va)
-{
- void *v = va_arg (*va, u8 *);
- int verbose = va_arg (*va, int);
-
- mheap_t *h;
- uword i, size;
- u32 indent;
- clib_mem_usage_t usage;
- mheap_elt_t *first_corrupt;
-
- mheap_maybe_lock (v);
-
- h = mheap_header (v);
-
- mheap_usage_no_lock (v, &usage);
-
- indent = format_get_indent (s);
-
- s =
- format (s,
- "%d objects, %U of %U used, %U free, %U reclaimed, %U overhead",
- usage.object_count, format_mheap_byte_count, usage.bytes_used,
- format_mheap_byte_count, usage.bytes_total,
- format_mheap_byte_count, usage.bytes_free,
- format_mheap_byte_count, usage.bytes_free_reclaimed,
- format_mheap_byte_count, usage.bytes_overhead);
-
- if (usage.bytes_max != ~0)
- s = format (s, ", %U capacity", format_mheap_byte_count, usage.bytes_max);
-
- /* Show histogram of sizes. */
- if (verbose > 1)
- {
- uword hist[MHEAP_N_BINS];
- mheap_elt_t *e;
- uword i, n_hist;
-
- clib_memset (hist, 0, sizeof (hist));
-
- n_hist = 0;
- for (e = v;
- e->n_user_data != MHEAP_N_USER_DATA_INVALID;
- e = mheap_next_elt (e))
- {
- uword n_user_data_bytes = mheap_elt_data_bytes (e);
- uword bin = user_data_size_to_bin_index (n_user_data_bytes);
- if (!e->is_free)
- {
- hist[bin] += 1;
- n_hist += 1;
- }
- }
-
- s = format (s, "\n%U%=12s%=12s%=16s",
- format_white_space, indent + 2,
- "Size", "Count", "Fraction");
-
- for (i = 0; i < ARRAY_LEN (hist); i++)
- {
- if (hist[i] == 0)
- continue;
- s = format (s, "\n%U%12d%12wd%16.4f",
- format_white_space, indent + 2,
- MHEAP_MIN_USER_DATA_BYTES +
- i * MHEAP_USER_DATA_WORD_BYTES, hist[i],
- (f64) hist[i] / (f64) n_hist);
- }
- }
-
- if (verbose)
- s = format (s, "\n%U%U",
- format_white_space, indent + 2, format_mheap_stats, h);
-
- if ((h->flags & MHEAP_FLAG_TRACE) && vec_len (h->trace_main.traces) > 0)
- {
- /* Make a copy of traces since we'll be sorting them. */
- mheap_trace_t *t, *traces_copy;
- u32 indent, total_objects_traced;
-
- traces_copy = vec_dup (h->trace_main.traces);
- qsort (traces_copy, vec_len (traces_copy), sizeof (traces_copy[0]),
- mheap_trace_sort);
-
- total_objects_traced = 0;
- s = format (s, "\n");
- vec_foreach (t, traces_copy)
- {
- /* Skip over free elements. */
- if (t->n_allocations == 0)
- continue;
-
- total_objects_traced += t->n_allocations;
-
- /* When not verbose only report allocations of more than 1k. */
- if (!verbose && t->n_bytes < 1024)
- continue;
-
- if (t == traces_copy)
- s = format (s, "%=9s%=9s %=10s Traceback\n", "Bytes", "Count",
- "Sample");
- s = format (s, "%9d%9d %p", t->n_bytes, t->n_allocations,
- t->offset + v);
- indent = format_get_indent (s);
- for (i = 0; i < ARRAY_LEN (t->callers) && t->callers[i]; i++)
- {
- if (i > 0)
- s = format (s, "%U", format_white_space, indent);
-#ifdef CLIB_UNIX
- s =
- format (s, " %U\n", format_clib_elf_symbol_with_address,
- t->callers[i]);
-#else
- s = format (s, " %p\n", t->callers[i]);
-#endif
- }
- }
-
- s = format (s, "%d total traced objects\n", total_objects_traced);
-
- vec_free (traces_copy);
- }
-
- first_corrupt = mheap_first_corrupt (v);
- if (first_corrupt)
- {
- size = mheap_elt_data_bytes (first_corrupt);
- s = format (s, "\n first corrupt object: %p, size %wd\n %U",
- first_corrupt, size, format_hex_bytes, first_corrupt, size);
- }
-
- /* FIXME. This output could be wrong in the unlikely case that format
- uses the same mheap as we are currently inspecting. */
- if (verbose > 1)
- {
- mheap_elt_t *e;
- uword i, o;
-
- s = format (s, "\n");
-
- e = mheap_elt_at_uoffset (v, 0);
- i = 0;
- while (1)
- {
- if ((i % 8) == 0)
- s = format (s, "%8d: ", i);
-
- o = mheap_elt_uoffset (v, e);
-
- if (e->is_free)
- s = format (s, "(%8d) ", o);
- else
- s = format (s, " %8d ", o);
-
- if ((i % 8) == 7 || (i + 1) >= h->n_elts)
- s = format (s, "\n");
- }
- }
-
- mheap_maybe_unlock (v);
-
- return s;
-}
-
-void
-dmh (void *v)
-{
- fformat (stderr, "%U", format_mheap, v, 1);
-}
-
-static void
-mheap_validate_breakpoint ()
-{
- os_panic ();
-}
-
-void
-mheap_validate (void *v)
-{
- mheap_t *h = mheap_header (v);
- uword i, s;
-
- uword elt_count, elt_size;
- uword free_count_from_free_lists, free_size_from_free_lists;
- uword small_elt_free_count, small_elt_free_size;
-
-#define CHECK(x) if (! (x)) { mheap_validate_breakpoint (); os_panic (); }
-
- if (vec_len (v) == 0)
- return;
-
- mheap_maybe_lock (v);
-
- /* Validate number of elements and size. */
- free_size_from_free_lists = free_count_from_free_lists = 0;
- for (i = 0; i < ARRAY_LEN (h->first_free_elt_uoffset_by_bin); i++)
- {
- mheap_elt_t *e, *n;
- uword is_first;
-
- CHECK ((h->first_free_elt_uoffset_by_bin[i] != MHEAP_GROUNDED)
- ==
- ((h->non_empty_free_elt_heads[i /
- BITS (uword)] & ((uword) 1 <<
- (uword) (i %
- BITS
- (uword))))
- != 0));
-
- if (h->first_free_elt_uoffset_by_bin[i] == MHEAP_GROUNDED)
- continue;
-
- e = mheap_elt_at_uoffset (v, h->first_free_elt_uoffset_by_bin[i]);
- is_first = 1;
- while (1)
- {
- uword s;
-
- n = mheap_next_elt (e);
-
- /* Object must be marked free. */
- CHECK (e->is_free);
-
- /* Next object's previous free bit must also be set. */
- CHECK (n->prev_is_free);
-
- if (is_first)
- CHECK (e->free_elt.prev_uoffset == MHEAP_GROUNDED);
- is_first = 0;
-
- s = mheap_elt_data_bytes (e);
- CHECK (user_data_size_to_bin_index (s) == i);
-
- free_count_from_free_lists += 1;
- free_size_from_free_lists += s;
-
- if (e->free_elt.next_uoffset == MHEAP_GROUNDED)
- break;
-
- n = mheap_elt_at_uoffset (v, e->free_elt.next_uoffset);
-
- /* Check free element linkages. */
- CHECK (n->free_elt.prev_uoffset == mheap_elt_uoffset (v, e));
-
- e = n;
- }
- }
-
- /* Go through small object cache. */
- small_elt_free_count = small_elt_free_size = 0;
- for (i = 0; i < ARRAY_LEN (h->small_object_cache.bins.as_u8); i++)
- {
- if (h->small_object_cache.bins.as_u8[i] != 0)
- {
- mheap_elt_t *e;
- uword b = h->small_object_cache.bins.as_u8[i] - 1;
- uword o = h->small_object_cache.offsets[i];
- uword s;
-
- e = mheap_elt_at_uoffset (v, o);
-
- /* Object must be allocated. */
- CHECK (!e->is_free);
-
- s = mheap_elt_data_bytes (e);
- CHECK (user_data_size_to_bin_index (s) == b);
-
- small_elt_free_count += 1;
- small_elt_free_size += s;
- }
- }
-
- {
- mheap_elt_t *e, *n;
- uword elt_free_size, elt_free_count;
-
- elt_count = elt_size = elt_free_size = elt_free_count = 0;
- for (e = v; e->n_user_data != MHEAP_N_USER_DATA_INVALID; e = n)
- {
- if (e->prev_n_user_data != MHEAP_N_USER_DATA_INVALID)
- CHECK (e->prev_n_user_data * sizeof (e->user_data[0]) >=
- MHEAP_MIN_USER_DATA_BYTES);
-
- CHECK (e->n_user_data * sizeof (e->user_data[0]) >=
- MHEAP_MIN_USER_DATA_BYTES);
-
- n = mheap_next_elt (e);
-
- CHECK (e->is_free == n->prev_is_free);
-
- elt_count++;
- s = mheap_elt_data_bytes (e);
- elt_size += s;
-
- if (e->is_free)
- {
- elt_free_count++;
- elt_free_size += s;
- }
-
- /* Consecutive free objects should have been combined. */
- CHECK (!(e->prev_is_free && n->prev_is_free));
- }
-
- CHECK (free_count_from_free_lists == elt_free_count);
- CHECK (free_size_from_free_lists == elt_free_size);
- CHECK (elt_count == h->n_elts + elt_free_count + small_elt_free_count);
- CHECK (elt_size + (elt_count + 1) * MHEAP_ELT_OVERHEAD_BYTES ==
- vec_len (v));
- }
-
- {
- mheap_elt_t *e, *n;
-
- for (e = v; e->n_user_data == MHEAP_N_USER_DATA_INVALID; e = n)
- {
- n = mheap_next_elt (e);
- CHECK (e->n_user_data == n->prev_n_user_data);
- }
- }
-
-#undef CHECK
-
- mheap_maybe_unlock (v);
-
- h->validate_serial += 1;
-}
-
-static void
-mheap_get_trace (void *v, uword offset, uword size)
-{
- mheap_t *h;
- mheap_trace_main_t *tm;
- mheap_trace_t *t;
- uword i, n_callers, trace_index, *p;
- mheap_trace_t trace;
-
- /* Spurious Coverity warnings be gone. */
- clib_memset (&trace, 0, sizeof (trace));
-
- n_callers = clib_backtrace (trace.callers, ARRAY_LEN (trace.callers),
- /* Skip mheap_get_aligned's frame */ 1);
- if (n_callers == 0)
- return;
-
- for (i = n_callers; i < ARRAY_LEN (trace.callers); i++)
- trace.callers[i] = 0;
-
- h = mheap_header (v);
- tm = &h->trace_main;
-
- if (!tm->trace_by_callers)
- tm->trace_by_callers =
- hash_create_shmem (0, sizeof (trace.callers), sizeof (uword));
-
- p = hash_get_mem (tm->trace_by_callers, &trace.callers);
- if (p)
- {
- trace_index = p[0];
- t = tm->traces + trace_index;
- }
- else
- {
- i = vec_len (tm->trace_free_list);
- if (i > 0)
- {
- trace_index = tm->trace_free_list[i - 1];
- _vec_len (tm->trace_free_list) = i - 1;
- }
- else
- {
- mheap_trace_t *old_start = tm->traces;
- mheap_trace_t *old_end = vec_end (tm->traces);
-
- vec_add2 (tm->traces, t, 1);
-
- if (tm->traces != old_start)
- {
- hash_pair_t *p;
- mheap_trace_t *q;
- /* *INDENT-OFF* */
- hash_foreach_pair (p, tm->trace_by_callers,
- ({
- q = uword_to_pointer (p->key, mheap_trace_t *);
- ASSERT (q >= old_start && q < old_end);
- p->key = pointer_to_uword (tm->traces + (q - old_start));
- }));
- /* *INDENT-ON* */
- }
- trace_index = t - tm->traces;
- }
-
- t = tm->traces + trace_index;
- t[0] = trace;
- t->n_allocations = 0;
- t->n_bytes = 0;
- hash_set_mem (tm->trace_by_callers, t->callers, trace_index);
- }
-
- t->n_allocations += 1;
- t->n_bytes += size;
- t->offset = offset; /* keep a sample to autopsy */
- hash_set (tm->trace_index_by_offset, offset, t - tm->traces);
-}
-
-static void
-mheap_put_trace (void *v, uword offset, uword size)
-{
- mheap_t *h;
- mheap_trace_main_t *tm;
- mheap_trace_t *t;
- uword trace_index, *p;
-
- h = mheap_header (v);
- tm = &h->trace_main;
- p = hash_get (tm->trace_index_by_offset, offset);
- if (!p)
- return;
-
- trace_index = p[0];
- hash_unset (tm->trace_index_by_offset, offset);
- ASSERT (trace_index < vec_len (tm->traces));
-
- t = tm->traces + trace_index;
- ASSERT (t->n_allocations > 0);
- ASSERT (t->n_bytes >= size);
- t->n_allocations -= 1;
- t->n_bytes -= size;
- if (t->n_allocations == 0)
- {
- hash_unset_mem (tm->trace_by_callers, t->callers);
- vec_add1 (tm->trace_free_list, trace_index);
- clib_memset (t, 0, sizeof (t[0]));
- }
-}
-
-static int
-mheap_trace_sort (const void *_t1, const void *_t2)
-{
- const mheap_trace_t *t1 = _t1;
- const mheap_trace_t *t2 = _t2;
- word cmp;
-
- cmp = (word) t2->n_bytes - (word) t1->n_bytes;
- if (!cmp)
- cmp = (word) t2->n_allocations - (word) t1->n_allocations;
- return cmp;
-}
-
-always_inline void
-mheap_trace_main_free (mheap_trace_main_t * tm)
-{
- vec_free (tm->traces);
- vec_free (tm->trace_free_list);
- hash_free (tm->trace_by_callers);
- hash_free (tm->trace_index_by_offset);
-}
-
-void
-mheap_trace (void *v, int enable)
-{
- mheap_t *h;
-
- h = mheap_header (v);
-
- if (enable)
- {
- h->flags |= MHEAP_FLAG_TRACE;
- }
- else
- {
- mheap_trace_main_free (&h->trace_main);
- h->flags &= ~MHEAP_FLAG_TRACE;
- }
-}
-
-/*
- * fd.io coding-style-patch-verification: ON
- *
- * Local Variables:
- * eval: (c-set-style "gnu")
- * End:
- */