blob: b8828f9e3e7ca5379565b202c53a710dc3019be4 [file] [log] [blame]
Ed Warnickecb9cada2015-12-08 15:45:58 -07001/*
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/bitops.h>
39#include <vppinfra/hash.h>
40#include <vppinfra/format.h>
41#include <vppinfra/mheap.h>
42#include <vppinfra/os.h>
43#include <vppinfra/time.h>
44
45#ifdef CLIB_UNIX
46#include <vppinfra/elf_clib.h>
47#endif
48
Dave Barachc3799992016-08-15 11:12:27 -040049static void mheap_get_trace (void *v, uword offset, uword size);
50static void mheap_put_trace (void *v, uword offset, uword size);
51static int mheap_trace_sort (const void *t1, const void *t2);
Ed Warnickecb9cada2015-12-08 15:45:58 -070052
Dave Barachc3799992016-08-15 11:12:27 -040053always_inline void
54mheap_maybe_lock (void *v)
Ed Warnickecb9cada2015-12-08 15:45:58 -070055{
Dave Barachc3799992016-08-15 11:12:27 -040056 mheap_t *h = mheap_header (v);
Ed Warnickecb9cada2015-12-08 15:45:58 -070057 if (v && (h->flags & MHEAP_FLAG_THREAD_SAFE))
58 {
Dave Barachc3799992016-08-15 11:12:27 -040059 u32 my_cpu = os_get_cpu_number ();
Ed Warnickecb9cada2015-12-08 15:45:58 -070060 if (h->owner_cpu == my_cpu)
Dave Barachc3799992016-08-15 11:12:27 -040061 {
62 h->recursion_count++;
63 return;
64 }
65
Ed Warnickecb9cada2015-12-08 15:45:58 -070066 while (__sync_lock_test_and_set (&h->lock, 1))
Dave Barachc3799992016-08-15 11:12:27 -040067 ;
Ed Warnickecb9cada2015-12-08 15:45:58 -070068
69 h->owner_cpu = my_cpu;
70 h->recursion_count = 1;
71 }
72}
73
Dave Barachc3799992016-08-15 11:12:27 -040074always_inline void
75mheap_maybe_unlock (void *v)
Ed Warnickecb9cada2015-12-08 15:45:58 -070076{
Dave Barachc3799992016-08-15 11:12:27 -040077 mheap_t *h = mheap_header (v);
Ed Warnickecb9cada2015-12-08 15:45:58 -070078 if (v && h->flags & MHEAP_FLAG_THREAD_SAFE)
79 {
Dave Barachc3799992016-08-15 11:12:27 -040080 ASSERT (os_get_cpu_number () == h->owner_cpu);
Ed Warnickecb9cada2015-12-08 15:45:58 -070081 if (--h->recursion_count == 0)
Dave Barachc3799992016-08-15 11:12:27 -040082 {
83 h->owner_cpu = ~0;
84 CLIB_MEMORY_BARRIER ();
85 h->lock = 0;
86 }
Ed Warnickecb9cada2015-12-08 15:45:58 -070087 }
88}
89
90/* Find bin for objects with size at least n_user_data_bytes. */
91always_inline uword
92user_data_size_to_bin_index (uword n_user_data_bytes)
93{
94 uword n_user_data_words;
95 word small_bin, large_bin;
96
97 /* User size must be at least big enough to hold free elt. */
98 n_user_data_bytes = clib_max (n_user_data_bytes, MHEAP_MIN_USER_DATA_BYTES);
99
100 /* Round to words. */
Dave Barachc3799992016-08-15 11:12:27 -0400101 n_user_data_words =
102 (round_pow2 (n_user_data_bytes, MHEAP_USER_DATA_WORD_BYTES) /
103 MHEAP_USER_DATA_WORD_BYTES);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700104
105 ASSERT (n_user_data_words > 0);
Dave Barachc3799992016-08-15 11:12:27 -0400106 small_bin =
107 n_user_data_words -
108 (MHEAP_MIN_USER_DATA_BYTES / MHEAP_USER_DATA_WORD_BYTES);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700109 ASSERT (small_bin >= 0);
110
Dave Barachc3799992016-08-15 11:12:27 -0400111 large_bin =
112 MHEAP_N_SMALL_OBJECT_BINS + max_log2 (n_user_data_bytes) -
113 MHEAP_LOG2_N_SMALL_OBJECT_BINS;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700114
115 return small_bin < MHEAP_N_SMALL_OBJECT_BINS ? small_bin : large_bin;
116}
117
118always_inline uword
119mheap_elt_size_to_user_n_bytes (uword n_bytes)
120{
121 ASSERT (n_bytes >= sizeof (mheap_elt_t));
122 return (n_bytes - STRUCT_OFFSET_OF (mheap_elt_t, user_data));
123}
124
Dave Barachc3799992016-08-15 11:12:27 -0400125always_inline uword __attribute__ ((unused))
Ed Warnickecb9cada2015-12-08 15:45:58 -0700126mheap_elt_size_to_user_n_words (uword n_bytes)
127{
128 ASSERT (n_bytes % MHEAP_USER_DATA_WORD_BYTES == 0);
Dave Barachc3799992016-08-15 11:12:27 -0400129 return mheap_elt_size_to_user_n_bytes (n_bytes) /
130 MHEAP_USER_DATA_WORD_BYTES;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700131}
132
133always_inline void
Dave Barachc3799992016-08-15 11:12:27 -0400134mheap_elt_set_size (void *v,
135 uword uoffset, uword n_user_data_bytes, uword is_free)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700136{
Dave Barachc3799992016-08-15 11:12:27 -0400137 mheap_elt_t *e, *n;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700138
139 e = mheap_elt_at_uoffset (v, uoffset);
140
141 ASSERT (n_user_data_bytes % MHEAP_USER_DATA_WORD_BYTES == 0);
Dave Barachb3d93da2016-08-03 14:34:38 -0400142
Ed Warnickecb9cada2015-12-08 15:45:58 -0700143 e->n_user_data = n_user_data_bytes / MHEAP_USER_DATA_WORD_BYTES;
144 e->is_free = is_free;
Dave Barachc3799992016-08-15 11:12:27 -0400145 ASSERT (e->prev_n_user_data * sizeof (e->user_data[0]) >=
146 MHEAP_MIN_USER_DATA_BYTES);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700147
148 n = mheap_next_elt (e);
149 n->prev_n_user_data = e->n_user_data;
150 n->prev_is_free = is_free;
151}
152
Dave Barachc3799992016-08-15 11:12:27 -0400153always_inline void
154set_first_free_elt_offset (mheap_t * h, uword bin, uword uoffset)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700155{
156 uword i0, i1;
157
158 h->first_free_elt_uoffset_by_bin[bin] = uoffset;
159
160 i0 = bin / BITS (h->non_empty_free_elt_heads[0]);
161 i1 = (uword) 1 << (uword) (bin % BITS (h->non_empty_free_elt_heads[0]));
162
163 ASSERT (i0 < ARRAY_LEN (h->non_empty_free_elt_heads));
Dave Barachb3d93da2016-08-03 14:34:38 -0400164 if (h->first_free_elt_uoffset_by_bin[bin] == MHEAP_GROUNDED)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700165 h->non_empty_free_elt_heads[i0] &= ~i1;
166 else
167 h->non_empty_free_elt_heads[i0] |= i1;
168}
169
170always_inline void
Dave Barachc3799992016-08-15 11:12:27 -0400171set_free_elt (void *v, uword uoffset, uword n_user_data_bytes)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700172{
Dave Barachc3799992016-08-15 11:12:27 -0400173 mheap_t *h = mheap_header (v);
174 mheap_elt_t *e = mheap_elt_at_uoffset (v, uoffset);
175 mheap_elt_t *n = mheap_next_elt (e);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700176 uword bin = user_data_size_to_bin_index (n_user_data_bytes);
177
178 ASSERT (n->prev_is_free);
179 ASSERT (e->is_free);
180
Dave Barachb3d93da2016-08-03 14:34:38 -0400181 e->free_elt.prev_uoffset = MHEAP_GROUNDED;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700182 e->free_elt.next_uoffset = h->first_free_elt_uoffset_by_bin[bin];
183
184 /* Fill in next free elt's previous pointer. */
Dave Barachb3d93da2016-08-03 14:34:38 -0400185 if (e->free_elt.next_uoffset != MHEAP_GROUNDED)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700186 {
Dave Barachc3799992016-08-15 11:12:27 -0400187 mheap_elt_t *nf = mheap_elt_at_uoffset (v, e->free_elt.next_uoffset);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700188 ASSERT (nf->is_free);
189 nf->free_elt.prev_uoffset = uoffset;
190 }
191
192 set_first_free_elt_offset (h, bin, uoffset);
193}
194
195always_inline void
Dave Barachc3799992016-08-15 11:12:27 -0400196new_free_elt (void *v, uword uoffset, uword n_user_data_bytes)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700197{
198 mheap_elt_set_size (v, uoffset, n_user_data_bytes, /* is_free */ 1);
199 set_free_elt (v, uoffset, n_user_data_bytes);
200}
201
202always_inline void
Dave Barachc3799992016-08-15 11:12:27 -0400203remove_free_elt (void *v, mheap_elt_t * e, uword bin)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700204{
Dave Barachc3799992016-08-15 11:12:27 -0400205 mheap_t *h = mheap_header (v);
206 mheap_elt_t *p, *n;
Dave Barachb3d93da2016-08-03 14:34:38 -0400207#if CLIB_VEC64 > 0
208 u64 no, po;
209#else
Ed Warnickecb9cada2015-12-08 15:45:58 -0700210 u32 no, po;
Dave Barachb3d93da2016-08-03 14:34:38 -0400211#endif
Ed Warnickecb9cada2015-12-08 15:45:58 -0700212
213 no = e->free_elt.next_uoffset;
Dave Barachb3d93da2016-08-03 14:34:38 -0400214
215 n = no != MHEAP_GROUNDED ? mheap_elt_at_uoffset (v, no) : 0;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700216 po = e->free_elt.prev_uoffset;
Dave Barachb3d93da2016-08-03 14:34:38 -0400217 p = po != MHEAP_GROUNDED ? mheap_elt_at_uoffset (v, po) : 0;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700218
Dave Barachc3799992016-08-15 11:12:27 -0400219 if (!p)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700220 set_first_free_elt_offset (h, bin, no);
221 else
222 p->free_elt.next_uoffset = no;
223
224 if (n)
225 n->free_elt.prev_uoffset = po;
226}
227
228always_inline void
Dave Barachc3799992016-08-15 11:12:27 -0400229remove_free_elt2 (void *v, mheap_elt_t * e)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700230{
231 uword bin;
232 bin = user_data_size_to_bin_index (mheap_elt_data_bytes (e));
233 remove_free_elt (v, e, bin);
234}
235
236#define MHEAP_VM_MAP (1 << 0)
237#define MHEAP_VM_UNMAP (1 << 1)
238#define MHEAP_VM_NOMAP (0 << 1)
239#define MHEAP_VM_ROUND (1 << 2)
240#define MHEAP_VM_ROUND_UP MHEAP_VM_ROUND
241#define MHEAP_VM_ROUND_DOWN (0 << 2)
242
243static uword mheap_page_size;
244
Dave Barachc3799992016-08-15 11:12:27 -0400245static_always_inline uword
246mheap_page_round (uword addr)
247{
248 return (addr + mheap_page_size - 1) & ~(mheap_page_size - 1);
249}
Ed Warnickecb9cada2015-12-08 15:45:58 -0700250
251static_always_inline uword
Dave Barachc3799992016-08-15 11:12:27 -0400252mheap_page_truncate (uword addr)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700253{
Dave Barachc3799992016-08-15 11:12:27 -0400254 return addr & ~(mheap_page_size - 1);
255}
256
257static_always_inline uword
258mheap_vm (void *v, uword flags, clib_address_t start_addr, uword size)
259{
260 mheap_t *h = mheap_header (v);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700261 clib_address_t start_page, end_page, end_addr;
262 uword mapped_bytes;
263
Dave Barachc3799992016-08-15 11:12:27 -0400264 ASSERT (!(h->flags & MHEAP_FLAG_DISABLE_VM));
Ed Warnickecb9cada2015-12-08 15:45:58 -0700265
266 end_addr = start_addr + size;
267
268 /* Round start/end address up to page boundary. */
269 start_page = mheap_page_round (start_addr);
270
271 if ((flags & MHEAP_VM_ROUND) == MHEAP_VM_ROUND_UP)
272 end_page = mheap_page_round (end_addr);
273 else
274 end_page = mheap_page_truncate (end_addr);
275
276 mapped_bytes = 0;
277 if (end_page > start_page)
278 {
279 mapped_bytes = end_page - start_page;
280 if (flags & MHEAP_VM_MAP)
281 clib_mem_vm_map ((void *) start_page, end_page - start_page);
282 else if (flags & MHEAP_VM_UNMAP)
283 clib_mem_vm_unmap ((void *) start_page, end_page - start_page);
284 }
285
286 return mapped_bytes;
287}
288
289static_always_inline uword
Dave Barachc3799992016-08-15 11:12:27 -0400290mheap_vm_elt (void *v, uword flags, uword offset)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700291{
Dave Barachc3799992016-08-15 11:12:27 -0400292 mheap_elt_t *e;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700293 clib_address_t start_addr, end_addr;
294
295 e = mheap_elt_at_uoffset (v, offset);
296 start_addr = (clib_address_t) ((void *) e->user_data);
297 end_addr = (clib_address_t) mheap_next_elt (e);
298 return mheap_vm (v, flags, start_addr, end_addr - start_addr);
299}
300
301always_inline uword
302mheap_small_object_cache_mask (mheap_small_object_cache_t * c, uword bin)
303{
304 uword mask;
305
306/* $$$$ ELIOT FIXME: add Altivec version of this routine */
307#if !defined (CLIB_HAVE_VEC128) || defined (__ALTIVEC__)
308 mask = 0;
309#else
310 u8x16 b = u8x16_splat (bin);
311
312 ASSERT (bin < 256);
313
314#define _(i) ((uword) u8x16_compare_byte_mask (u8x16_is_equal (b, c->bins.as_u8x16[i])) << (uword) ((i)*16))
Dave Barachc3799992016-08-15 11:12:27 -0400315 mask = _(0) | _(1);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700316 if (BITS (uword) > 32)
Dave Barachc3799992016-08-15 11:12:27 -0400317 mask |= _(2) | _(3);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700318#undef _
319
320#endif
321 return mask;
322}
323
324always_inline uword
325mheap_get_small_object (mheap_t * h, uword bin)
326{
Dave Barachc3799992016-08-15 11:12:27 -0400327 mheap_small_object_cache_t *c = &h->small_object_cache;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700328 uword mask = mheap_small_object_cache_mask (c, bin + 1);
Dave Barachb3d93da2016-08-03 14:34:38 -0400329 uword offset = MHEAP_GROUNDED;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700330
331 if (mask)
332 {
333 uword i = min_log2 (mask);
334 uword o = c->offsets[i];
Dave Barachb3d93da2016-08-03 14:34:38 -0400335 ASSERT (o != MHEAP_GROUNDED);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700336 c->bins.as_u8[i] = 0;
337 offset = o;
338 }
339
340 return offset;
341}
342
343always_inline uword
344mheap_put_small_object (mheap_t * h, uword bin, uword offset)
345{
Dave Barachc3799992016-08-15 11:12:27 -0400346 mheap_small_object_cache_t *c = &h->small_object_cache;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700347 uword free_mask = mheap_small_object_cache_mask (c, 0);
348 uword b = bin + 1;
349 uword i;
350
351 if (free_mask != 0)
352 {
353 i = min_log2 (free_mask);
354 c->bins.as_u8[i] = b;
355 c->offsets[i] = offset;
356 return 0;
357 }
358 else
359 /* Nothing free with right size: cyclic replacement. */
360 {
361 uword old_offset;
362
363 i = c->replacement_index++;
364 i %= BITS (uword);
365 c->bins.as_u8[i] = b;
366 old_offset = c->offsets[i];
367 c->offsets[i] = offset;
368
369 /* Return old offset so it can be freed. */
370 return old_offset;
371 }
372}
373
374static uword
Dave Barachc3799992016-08-15 11:12:27 -0400375mheap_get_search_free_bin (void *v,
Ed Warnickecb9cada2015-12-08 15:45:58 -0700376 uword bin,
377 uword * n_user_data_bytes_arg,
Dave Barachc3799992016-08-15 11:12:27 -0400378 uword align, uword align_offset)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700379{
Dave Barachc3799992016-08-15 11:12:27 -0400380 mheap_t *h = mheap_header (v);
381 mheap_elt_t *e;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700382
383 /* Free object is at offset f0 ... f1;
384 Allocatted object is at offset o0 ... o1. */
385 word o0, o1, f0, f1, search_n_user_data_bytes;
386 word lo_free_usize, hi_free_usize;
387
Dave Barachb3d93da2016-08-03 14:34:38 -0400388 ASSERT (h->first_free_elt_uoffset_by_bin[bin] != MHEAP_GROUNDED);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700389 e = mheap_elt_at_uoffset (v, h->first_free_elt_uoffset_by_bin[bin]);
390
391 search_n_user_data_bytes = *n_user_data_bytes_arg;
392
393 /* Silence compiler warning. */
394 o0 = o1 = f0 = f1 = 0;
395
396 h->stats.free_list.n_search_attempts += 1;
397
398 /* Find an object that is large enough with correct alignment at given alignment offset. */
399 while (1)
400 {
401 uword this_object_n_user_data_bytes = mheap_elt_data_bytes (e);
402
403 ASSERT (e->is_free);
404 if (bin < MHEAP_N_SMALL_OBJECT_BINS)
405 ASSERT (this_object_n_user_data_bytes >= search_n_user_data_bytes);
406
407 h->stats.free_list.n_objects_searched += 1;
408
409 if (this_object_n_user_data_bytes < search_n_user_data_bytes)
410 goto next;
411
412 /* Bounds of free object: from f0 to f1. */
413 f0 = ((void *) e->user_data - v);
414 f1 = f0 + this_object_n_user_data_bytes;
415
416 /* Place candidate object at end of free block and align as requested. */
Dave Barachc3799992016-08-15 11:12:27 -0400417 o0 = ((f1 - search_n_user_data_bytes) & ~(align - 1)) - align_offset;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700418 while (o0 < f0)
419 o0 += align;
420
421 /* Make sure that first free fragment is either empty or
Dave Barachc3799992016-08-15 11:12:27 -0400422 large enough to be valid. */
Ed Warnickecb9cada2015-12-08 15:45:58 -0700423 while (1)
424 {
425 lo_free_usize = o0 != f0 ? o0 - f0 - MHEAP_ELT_OVERHEAD_BYTES : 0;
426 if (o0 <= f0 || lo_free_usize >= (word) MHEAP_MIN_USER_DATA_BYTES)
427 break;
428 o0 -= align;
429 }
430
431 o1 = o0 + search_n_user_data_bytes;
432
433 /* Does it fit? */
434 if (o0 >= f0 && o1 <= f1)
435 goto found;
436
437 next:
438 /* Reached end of free list without finding large enough object. */
Dave Barachb3d93da2016-08-03 14:34:38 -0400439 if (e->free_elt.next_uoffset == MHEAP_GROUNDED)
440 return MHEAP_GROUNDED;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700441
442 /* Otherwise keep searching for large enough object. */
443 e = mheap_elt_at_uoffset (v, e->free_elt.next_uoffset);
444 }
445
Dave Barachc3799992016-08-15 11:12:27 -0400446found:
Ed Warnickecb9cada2015-12-08 15:45:58 -0700447 /* Free fragment at end. */
448 hi_free_usize = f1 != o1 ? f1 - o1 - MHEAP_ELT_OVERHEAD_BYTES : 0;
449
450 /* If fragment at end is too small to be a new object,
451 give user's object a bit more space than requested. */
452 if (hi_free_usize < (word) MHEAP_MIN_USER_DATA_BYTES)
453 {
454 search_n_user_data_bytes += f1 - o1;
455 o1 = f1;
456 hi_free_usize = 0;
457 }
458
459 /* Need to make sure that relevant memory areas are mapped. */
Dave Barachc3799992016-08-15 11:12:27 -0400460 if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
Ed Warnickecb9cada2015-12-08 15:45:58 -0700461 {
Dave Barachc3799992016-08-15 11:12:27 -0400462 mheap_elt_t *f0_elt = mheap_elt_at_uoffset (v, f0);
463 mheap_elt_t *f1_elt = mheap_elt_at_uoffset (v, f1);
464 mheap_elt_t *o0_elt = mheap_elt_at_uoffset (v, o0);
465 mheap_elt_t *o1_elt = mheap_elt_at_uoffset (v, o1);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700466
467 uword f0_page_start, f0_page_end;
468 uword o0_page_start, o0_page_end;
469
470 /* Free elt is mapped. Addresses after that may not be mapped. */
471 f0_page_start = mheap_page_round (pointer_to_uword (f0_elt->user_data));
Dave Barachc3799992016-08-15 11:12:27 -0400472 f0_page_end = mheap_page_truncate (pointer_to_uword (f1_elt));
Ed Warnickecb9cada2015-12-08 15:45:58 -0700473
474 o0_page_start = mheap_page_truncate (pointer_to_uword (o0_elt));
475 o0_page_end = mheap_page_round (pointer_to_uword (o1_elt->user_data));
476
477 if (o0_page_start < f0_page_start)
478 o0_page_start = f0_page_start;
479 if (o0_page_end > f0_page_end)
480 o0_page_end = f0_page_end;
481
482 if (o0_page_end > o0_page_start)
483 clib_mem_vm_map (uword_to_pointer (o0_page_start, void *),
484 o0_page_end - o0_page_start);
485 }
486
487 /* Remove free object from free list. */
488 remove_free_elt (v, e, bin);
489
490 /* Free fragment at begining. */
491 if (lo_free_usize > 0)
492 {
493 ASSERT (lo_free_usize >= (word) MHEAP_MIN_USER_DATA_BYTES);
494 mheap_elt_set_size (v, f0, lo_free_usize, /* is_free */ 1);
495 new_free_elt (v, f0, lo_free_usize);
496 }
497
498 mheap_elt_set_size (v, o0, search_n_user_data_bytes, /* is_free */ 0);
499
500 if (hi_free_usize > 0)
501 {
502 uword uo = o1 + MHEAP_ELT_OVERHEAD_BYTES;
503 mheap_elt_set_size (v, uo, hi_free_usize, /* is_free */ 1);
504 new_free_elt (v, uo, hi_free_usize);
505 }
506
507 /* Return actual size of block. */
508 *n_user_data_bytes_arg = search_n_user_data_bytes;
509
510 h->stats.free_list.n_objects_found += 1;
511
512 return o0;
513}
514
515/* Search free lists for object with given size and alignment. */
516static uword
Dave Barachc3799992016-08-15 11:12:27 -0400517mheap_get_search_free_list (void *v,
Ed Warnickecb9cada2015-12-08 15:45:58 -0700518 uword * n_user_bytes_arg,
Dave Barachc3799992016-08-15 11:12:27 -0400519 uword align, uword align_offset)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700520{
Dave Barachc3799992016-08-15 11:12:27 -0400521 mheap_t *h = mheap_header (v);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700522 uword bin, n_user_bytes, i, bi;
523
524 n_user_bytes = *n_user_bytes_arg;
525 bin = user_data_size_to_bin_index (n_user_bytes);
526
527 if (MHEAP_HAVE_SMALL_OBJECT_CACHE
528 && (h->flags & MHEAP_FLAG_SMALL_OBJECT_CACHE)
529 && bin < 255
530 && align == STRUCT_SIZE_OF (mheap_elt_t, user_data[0])
531 && align_offset == 0)
532 {
533 uword r = mheap_get_small_object (h, bin);
534 h->stats.n_small_object_cache_attempts += 1;
Dave Barachb3d93da2016-08-03 14:34:38 -0400535 if (r != MHEAP_GROUNDED)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700536 {
537 h->stats.n_small_object_cache_hits += 1;
538 return r;
539 }
540 }
541
Dave Barachc3799992016-08-15 11:12:27 -0400542 for (i = bin / BITS (uword); i < ARRAY_LEN (h->non_empty_free_elt_heads);
543 i++)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700544 {
545 uword non_empty_bin_mask = h->non_empty_free_elt_heads[i];
546
547 /* No need to search smaller bins. */
548 if (i == bin / BITS (uword))
549 non_empty_bin_mask &= ~pow2_mask (bin % BITS (uword));
550
551 /* Search each occupied free bin which is large enough. */
Dave Barachc3799992016-08-15 11:12:27 -0400552 foreach_set_bit (bi, non_empty_bin_mask, (
553 {
554 uword r =
555 mheap_get_search_free_bin (v,
556 bi
557 +
558 i
559 *
560 BITS
561 (uword),
562 n_user_bytes_arg,
563 align,
564 align_offset);
565 if (r !=
566 MHEAP_GROUNDED) return
567 r;}
568 ));
Ed Warnickecb9cada2015-12-08 15:45:58 -0700569 }
570
Dave Barachb3d93da2016-08-03 14:34:38 -0400571 return MHEAP_GROUNDED;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700572}
573
574static never_inline void *
Dave Barachc3799992016-08-15 11:12:27 -0400575mheap_get_extend_vector (void *v,
Ed Warnickecb9cada2015-12-08 15:45:58 -0700576 uword n_user_data_bytes,
577 uword align,
Dave Barachc3799992016-08-15 11:12:27 -0400578 uword align_offset, uword * offset_return)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700579{
580 /* Bounds of free and allocated objects (as above). */
581 uword f0, f1, o0, o1;
582 word free_size;
Dave Barachc3799992016-08-15 11:12:27 -0400583 mheap_t *h = mheap_header (v);
584 mheap_elt_t *e;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700585
586 if (_vec_len (v) == 0)
587 {
588 _vec_len (v) = MHEAP_ELT_OVERHEAD_BYTES;
589
590 /* Create first element of heap. */
591 e = mheap_elt_at_uoffset (v, _vec_len (v));
592 e->prev_n_user_data = MHEAP_N_USER_DATA_INVALID;
593 }
594
595 f0 = _vec_len (v);
596
597 o0 = round_pow2 (f0, align) - align_offset;
598 while (1)
599 {
600 free_size = o0 - f0 - MHEAP_ELT_OVERHEAD_BYTES;
601 if (o0 == f0 || free_size >= (word) sizeof (mheap_elt_t))
602 break;
603
604 o0 += align;
605 }
606
607 o1 = o0 + n_user_data_bytes;
608 f1 = o1 + MHEAP_ELT_OVERHEAD_BYTES;
Dave Barachc3799992016-08-15 11:12:27 -0400609
Ed Warnickecb9cada2015-12-08 15:45:58 -0700610 ASSERT (v != 0);
611 h = mheap_header (v);
612
613 /* Make sure we have space for object plus overhead. */
614 if (f1 > h->max_size)
615 {
Dave Barachb3d93da2016-08-03 14:34:38 -0400616 *offset_return = MHEAP_GROUNDED;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700617 return v;
618 }
619
620 _vec_len (v) = f1;
621
Dave Barachc3799992016-08-15 11:12:27 -0400622 if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
Ed Warnickecb9cada2015-12-08 15:45:58 -0700623 {
Dave Barachc3799992016-08-15 11:12:27 -0400624 mheap_elt_t *f0_elt = mheap_elt_at_uoffset (v, f0);
625 mheap_elt_t *f1_elt = mheap_elt_at_uoffset (v, f1);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700626
627 uword f0_page = mheap_page_round (pointer_to_uword (f0_elt->user_data));
628 uword f1_page = mheap_page_round (pointer_to_uword (f1_elt->user_data));
629
630 if (f1_page > f0_page)
631 mheap_vm (v, MHEAP_VM_MAP, f0_page, f1_page - f0_page);
632 }
633
634 if (free_size > 0)
635 new_free_elt (v, f0, free_size);
636
637 mheap_elt_set_size (v, o0, n_user_data_bytes, /* is_free */ 0);
638
639 /* Mark last element. */
640 e = mheap_elt_at_uoffset (v, f1);
641 e->n_user_data = MHEAP_N_USER_DATA_INVALID;
642
643 *offset_return = o0;
644
645 return v;
646}
647
Dave Barachc3799992016-08-15 11:12:27 -0400648void *
649mheap_get_aligned (void *v,
650 uword n_user_data_bytes,
651 uword align, uword align_offset, uword * offset_return)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700652{
Dave Barachc3799992016-08-15 11:12:27 -0400653 mheap_t *h;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700654 uword offset;
655 u64 cpu_times[2];
656
657 cpu_times[0] = clib_cpu_time_now ();
658
659 align = clib_max (align, STRUCT_SIZE_OF (mheap_elt_t, user_data[0]));
660 align = max_pow2 (align);
661
662 /* Correct align offset to be smaller than alignment. */
663 align_offset &= (align - 1);
664
665 /* Align offset must be multiple of minimum object size. */
666 if (align_offset % STRUCT_SIZE_OF (mheap_elt_t, user_data[0]) != 0)
667 {
Dave Barachb3d93da2016-08-03 14:34:38 -0400668 *offset_return = MHEAP_GROUNDED;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700669 return v;
670 }
671
672 /* Round requested size. */
673 n_user_data_bytes = clib_max (n_user_data_bytes, MHEAP_MIN_USER_DATA_BYTES);
Dave Barachc3799992016-08-15 11:12:27 -0400674 n_user_data_bytes =
675 round_pow2 (n_user_data_bytes,
676 STRUCT_SIZE_OF (mheap_elt_t, user_data[0]));
Ed Warnickecb9cada2015-12-08 15:45:58 -0700677
Dave Barachc3799992016-08-15 11:12:27 -0400678 if (!v)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700679 v = mheap_alloc (0, 64 << 20);
680
681 mheap_maybe_lock (v);
682
683 h = mheap_header (v);
684
685 if (h->flags & MHEAP_FLAG_VALIDATE)
686 mheap_validate (v);
687
688 /* First search free lists for object. */
Dave Barachc3799992016-08-15 11:12:27 -0400689 offset =
690 mheap_get_search_free_list (v, &n_user_data_bytes, align, align_offset);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700691
692 h = mheap_header (v);
693
694 /* If that fails allocate object at end of heap by extending vector. */
Dave Barachb3d93da2016-08-03 14:34:38 -0400695 if (offset == MHEAP_GROUNDED && _vec_len (v) < h->max_size)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700696 {
Dave Barachc3799992016-08-15 11:12:27 -0400697 v =
698 mheap_get_extend_vector (v, n_user_data_bytes, align, align_offset,
699 &offset);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700700 h = mheap_header (v);
Dave Barachb3d93da2016-08-03 14:34:38 -0400701 h->stats.n_vector_expands += offset != MHEAP_GROUNDED;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700702 }
703
704 *offset_return = offset;
Dave Barachb3d93da2016-08-03 14:34:38 -0400705 if (offset != MHEAP_GROUNDED)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700706 {
707 h->n_elts += 1;
708
709 if (h->flags & MHEAP_FLAG_TRACE)
710 {
711 /* Recursion block for case when we are traceing main clib heap. */
712 h->flags &= ~MHEAP_FLAG_TRACE;
713
714 mheap_get_trace (v, offset, n_user_data_bytes);
715
716 h->flags |= MHEAP_FLAG_TRACE;
717 }
718 }
719
720 if (h->flags & MHEAP_FLAG_VALIDATE)
721 mheap_validate (v);
722
723 mheap_maybe_unlock (v);
724
725 cpu_times[1] = clib_cpu_time_now ();
726 h->stats.n_clocks_get += cpu_times[1] - cpu_times[0];
727 h->stats.n_gets += 1;
728
729 return v;
730}
731
Dave Barachc3799992016-08-15 11:12:27 -0400732static void
733free_last_elt (void *v, mheap_elt_t * e)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700734{
Dave Barachc3799992016-08-15 11:12:27 -0400735 mheap_t *h = mheap_header (v);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700736
737 /* Possibly delete preceeding free element also. */
738 if (e->prev_is_free)
739 {
740 e = mheap_prev_elt (e);
741 remove_free_elt2 (v, e);
742 }
743
744 if (e->prev_n_user_data == MHEAP_N_USER_DATA_INVALID)
745 {
Dave Barachc3799992016-08-15 11:12:27 -0400746 if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
Ed Warnickecb9cada2015-12-08 15:45:58 -0700747 mheap_vm_elt (v, MHEAP_VM_UNMAP, mheap_elt_uoffset (v, e));
748 _vec_len (v) = 0;
749 }
750 else
751 {
752 uword uo = mheap_elt_uoffset (v, e);
Dave Barachc3799992016-08-15 11:12:27 -0400753 if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
Ed Warnickecb9cada2015-12-08 15:45:58 -0700754 mheap_vm_elt (v, MHEAP_VM_UNMAP, uo);
755 e->n_user_data = MHEAP_N_USER_DATA_INVALID;
756 _vec_len (v) = uo;
757 }
758}
759
Dave Barachc3799992016-08-15 11:12:27 -0400760void
761mheap_put (void *v, uword uoffset)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700762{
Dave Barachc3799992016-08-15 11:12:27 -0400763 mheap_t *h;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700764 uword n_user_data_bytes, bin;
Dave Barachc3799992016-08-15 11:12:27 -0400765 mheap_elt_t *e, *n;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700766 uword trace_uoffset, trace_n_user_data_bytes;
767 u64 cpu_times[2];
768
769 cpu_times[0] = clib_cpu_time_now ();
770
771 h = mheap_header (v);
772
773 mheap_maybe_lock (v);
774
775 if (h->flags & MHEAP_FLAG_VALIDATE)
776 mheap_validate (v);
777
778 ASSERT (h->n_elts > 0);
779 h->n_elts--;
780 h->stats.n_puts += 1;
781
782 e = mheap_elt_at_uoffset (v, uoffset);
783 n = mheap_next_elt (e);
784 n_user_data_bytes = mheap_elt_data_bytes (e);
785
786 trace_uoffset = uoffset;
787 trace_n_user_data_bytes = n_user_data_bytes;
788
789 bin = user_data_size_to_bin_index (n_user_data_bytes);
790 if (MHEAP_HAVE_SMALL_OBJECT_CACHE
Dave Barachc3799992016-08-15 11:12:27 -0400791 && bin < 255 && (h->flags & MHEAP_FLAG_SMALL_OBJECT_CACHE))
Ed Warnickecb9cada2015-12-08 15:45:58 -0700792 {
793 uoffset = mheap_put_small_object (h, bin, uoffset);
Dave Barachc3799992016-08-15 11:12:27 -0400794 if (uoffset == 0)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700795 goto done;
796
797 e = mheap_elt_at_uoffset (v, uoffset);
798 n = mheap_next_elt (e);
799 n_user_data_bytes = mheap_elt_data_bytes (e);
800 }
801
802 /* Assert that forward and back pointers are equal. */
803 if (e->n_user_data != n->prev_n_user_data)
804 os_panic ();
805
806 /* Forward and backwards is_free must agree. */
807 if (e->is_free != n->prev_is_free)
808 os_panic ();
809
810 /* Object was already freed. */
811 if (e->is_free)
812 os_panic ();
813
814 /* Special case: delete last element in heap. */
815 if (n->n_user_data == MHEAP_N_USER_DATA_INVALID)
816 free_last_elt (v, e);
817
818 else
819 {
820 uword f0, f1, n_combine;
821
822 f0 = uoffset;
823 f1 = f0 + n_user_data_bytes;
824 n_combine = 0;
825
826 if (e->prev_is_free)
827 {
Dave Barachc3799992016-08-15 11:12:27 -0400828 mheap_elt_t *p = mheap_prev_elt (e);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700829 f0 = mheap_elt_uoffset (v, p);
830 remove_free_elt2 (v, p);
831 n_combine++;
832 }
833
834 if (n->is_free)
835 {
Dave Barachc3799992016-08-15 11:12:27 -0400836 mheap_elt_t *m = mheap_next_elt (n);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700837 f1 = (void *) m - v;
838 remove_free_elt2 (v, n);
839 n_combine++;
840 }
841
842 if (n_combine)
843 mheap_elt_set_size (v, f0, f1 - f0, /* is_free */ 1);
844 else
845 e->is_free = n->prev_is_free = 1;
846 set_free_elt (v, f0, f1 - f0);
847
Dave Barachc3799992016-08-15 11:12:27 -0400848 if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
Ed Warnickecb9cada2015-12-08 15:45:58 -0700849 mheap_vm_elt (v, MHEAP_VM_UNMAP, f0);
850 }
851
Dave Barachc3799992016-08-15 11:12:27 -0400852done:
Ed Warnickecb9cada2015-12-08 15:45:58 -0700853 h = mheap_header (v);
854
855 if (h->flags & MHEAP_FLAG_TRACE)
856 {
857 /* Recursion block for case when we are traceing main clib heap. */
858 h->flags &= ~MHEAP_FLAG_TRACE;
859
860 mheap_put_trace (v, trace_uoffset, trace_n_user_data_bytes);
861
862 h->flags |= MHEAP_FLAG_TRACE;
863 }
864
865 if (h->flags & MHEAP_FLAG_VALIDATE)
866 mheap_validate (v);
867
868 mheap_maybe_unlock (v);
869
870 cpu_times[1] = clib_cpu_time_now ();
871 h->stats.n_clocks_put += cpu_times[1] - cpu_times[0];
872}
873
Dave Barachc3799992016-08-15 11:12:27 -0400874void *
875mheap_alloc_with_flags (void *memory, uword memory_size, uword flags)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700876{
Dave Barachc3799992016-08-15 11:12:27 -0400877 mheap_t *h;
878 void *v;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700879 uword size;
880
Dave Barachc3799992016-08-15 11:12:27 -0400881 if (!mheap_page_size)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700882 mheap_page_size = clib_mem_get_page_size ();
883
Dave Barachc3799992016-08-15 11:12:27 -0400884 if (!memory)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700885 {
886 /* No memory given, try to VM allocate some. */
887 memory = clib_mem_vm_alloc (memory_size);
Dave Barachc3799992016-08-15 11:12:27 -0400888 if (!memory)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700889 return 0;
890
891 /* No memory region implies we have virtual memory. */
892 flags &= ~MHEAP_FLAG_DISABLE_VM;
893 }
894
895 /* Make sure that given memory is page aligned. */
896 {
897 uword am, av, ah;
898
899 am = pointer_to_uword (memory);
900 av = mheap_page_round (am);
901 v = uword_to_pointer (av, void *);
902 h = mheap_header (v);
903 ah = pointer_to_uword (h);
904 while (ah < am)
905 ah += mheap_page_size;
906
907 h = uword_to_pointer (ah, void *);
908 v = mheap_vector (h);
909
Dave Barachc3799992016-08-15 11:12:27 -0400910 if (PREDICT_FALSE (memory + memory_size < v))
911 {
Pierre Pfister889178c2016-06-17 13:30:02 +0100912 /*
913 * This will happen when the requested memory_size is too
914 * small to cope with the heap header and/or memory alignment.
915 */
Dave Barachc3799992016-08-15 11:12:27 -0400916 clib_mem_vm_free (memory, memory_size);
Pierre Pfister889178c2016-06-17 13:30:02 +0100917 return 0;
Dave Barachc3799992016-08-15 11:12:27 -0400918 }
Pierre Pfister889178c2016-06-17 13:30:02 +0100919
Ed Warnickecb9cada2015-12-08 15:45:58 -0700920 size = memory + memory_size - v;
921 }
922
923 /* VM map header so we can use memory. */
Dave Barachc3799992016-08-15 11:12:27 -0400924 if (!(flags & MHEAP_FLAG_DISABLE_VM))
Ed Warnickecb9cada2015-12-08 15:45:58 -0700925 clib_mem_vm_map (h, sizeof (h[0]));
926
927 /* Zero vector header: both heap header and vector length. */
928 memset (h, 0, sizeof (h[0]));
929 _vec_len (v) = 0;
930
931 h->vm_alloc_offset_from_header = (void *) h - memory;
932 h->vm_alloc_size = memory_size;
933
934 h->max_size = size;
935 h->owner_cpu = ~0;
936
937 /* Set flags based on those given less builtin-flags. */
Dave Barachc3799992016-08-15 11:12:27 -0400938 h->flags |= (flags & ~MHEAP_FLAG_TRACE);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700939
940 /* Unmap remainder of heap until we will be ready to use it. */
Dave Barachc3799992016-08-15 11:12:27 -0400941 if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
Ed Warnickecb9cada2015-12-08 15:45:58 -0700942 mheap_vm (v, MHEAP_VM_UNMAP | MHEAP_VM_ROUND_UP,
943 (clib_address_t) v, h->max_size);
944
945 /* Initialize free list heads to empty. */
Dave Barachc3799992016-08-15 11:12:27 -0400946 memset (h->first_free_elt_uoffset_by_bin, 0xFF,
947 sizeof (h->first_free_elt_uoffset_by_bin));
Ed Warnickecb9cada2015-12-08 15:45:58 -0700948
949 return v;
950}
951
Dave Barachc3799992016-08-15 11:12:27 -0400952void *
953mheap_alloc (void *memory, uword size)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700954{
955 uword flags = 0;
956
957 if (memory != 0)
958 flags |= MHEAP_FLAG_DISABLE_VM;
959
960#ifdef CLIB_HAVE_VEC128
961 flags |= MHEAP_FLAG_SMALL_OBJECT_CACHE;
962#endif
963
964 return mheap_alloc_with_flags (memory, size, flags);
965}
966
Dave Barachc3799992016-08-15 11:12:27 -0400967void *
968_mheap_free (void *v)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700969{
Dave Barachc3799992016-08-15 11:12:27 -0400970 mheap_t *h = mheap_header (v);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700971
972 if (v)
Dave Barachc3799992016-08-15 11:12:27 -0400973 clib_mem_vm_free ((void *) h - h->vm_alloc_offset_from_header,
974 h->vm_alloc_size);
975
Ed Warnickecb9cada2015-12-08 15:45:58 -0700976 return 0;
977}
978
979/* Call user's function with each object in heap. */
Dave Barachc3799992016-08-15 11:12:27 -0400980void
981mheap_foreach (void *v,
982 uword (*func) (void *arg, void *v, void *elt_data,
983 uword elt_size), void *arg)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700984{
Dave Barachc3799992016-08-15 11:12:27 -0400985 mheap_elt_t *e;
986 u8 *stack_heap, *clib_mem_mheap_save;
987 u8 tmp_heap_memory[16 * 1024];
Ed Warnickecb9cada2015-12-08 15:45:58 -0700988
989 mheap_maybe_lock (v);
990
991 if (vec_len (v) == 0)
992 goto done;
993
994 clib_mem_mheap_save = 0;
995 stack_heap = 0;
996
997 /* Allocate a new temporary heap on the stack.
998 This is so that our hash table & user's callback function can
999 themselves allocate memory somewhere without getting in the way
1000 of the heap we are looking at. */
1001 if (v == clib_mem_get_heap ())
1002 {
1003 stack_heap = mheap_alloc (tmp_heap_memory, sizeof (tmp_heap_memory));
1004 clib_mem_mheap_save = v;
1005 clib_mem_set_heap (stack_heap);
1006 }
1007
1008 for (e = v;
Dave Barachc3799992016-08-15 11:12:27 -04001009 e->n_user_data != MHEAP_N_USER_DATA_INVALID; e = mheap_next_elt (e))
Ed Warnickecb9cada2015-12-08 15:45:58 -07001010 {
Dave Barachc3799992016-08-15 11:12:27 -04001011 void *p = mheap_elt_data (v, e);
Ed Warnickecb9cada2015-12-08 15:45:58 -07001012 if (e->is_free)
1013 continue;
Dave Barachc3799992016-08-15 11:12:27 -04001014 if ((*func) (arg, v, p, mheap_elt_data_bytes (e)))
Ed Warnickecb9cada2015-12-08 15:45:58 -07001015 break;
1016 }
1017
1018 /* Restore main CLIB heap. */
1019 if (clib_mem_mheap_save)
1020 clib_mem_set_heap (clib_mem_mheap_save);
1021
Dave Barachc3799992016-08-15 11:12:27 -04001022done:
Ed Warnickecb9cada2015-12-08 15:45:58 -07001023 mheap_maybe_unlock (v);
1024}
1025
1026/* Bytes in mheap header overhead not including data bytes. */
1027always_inline uword
Dave Barachc3799992016-08-15 11:12:27 -04001028mheap_bytes_overhead (void *v)
Ed Warnickecb9cada2015-12-08 15:45:58 -07001029{
Dave Barachc3799992016-08-15 11:12:27 -04001030 mheap_t *h = mheap_header (v);
Ed Warnickecb9cada2015-12-08 15:45:58 -07001031 return v ? sizeof (h[0]) + h->n_elts * sizeof (mheap_elt_t) : 0;
1032}
1033
1034/* Total number of bytes including both data and overhead. */
Dave Barachc3799992016-08-15 11:12:27 -04001035uword
1036mheap_bytes (void *v)
Ed Warnickecb9cada2015-12-08 15:45:58 -07001037{
Dave Barachc3799992016-08-15 11:12:27 -04001038 return mheap_bytes_overhead (v) + vec_bytes (v);
1039}
1040
1041static void
1042mheap_usage_no_lock (void *v, clib_mem_usage_t * usage)
1043{
1044 mheap_t *h = mheap_header (v);
Ed Warnickecb9cada2015-12-08 15:45:58 -07001045 uword used = 0, free = 0, free_vm_unmapped = 0;
1046
1047 if (vec_len (v) > 0)
1048 {
Dave Barachc3799992016-08-15 11:12:27 -04001049 mheap_elt_t *e;
Ed Warnickecb9cada2015-12-08 15:45:58 -07001050
1051 for (e = v;
1052 e->n_user_data != MHEAP_N_USER_DATA_INVALID;
1053 e = mheap_next_elt (e))
1054 {
1055 uword size = mheap_elt_data_bytes (e);
1056 if (e->is_free)
1057 {
1058 free += size;
Dave Barachc3799992016-08-15 11:12:27 -04001059 if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
Ed Warnickecb9cada2015-12-08 15:45:58 -07001060 free_vm_unmapped +=
1061 mheap_vm_elt (v, MHEAP_VM_NOMAP, mheap_elt_uoffset (v, e));
1062 }
1063 else
1064 used += size;
1065 }
1066 }
1067
1068 usage->object_count = mheap_elts (v);
1069 usage->bytes_total = mheap_bytes (v);
1070 usage->bytes_overhead = mheap_bytes_overhead (v);
1071 usage->bytes_max = mheap_max_size (v);
1072 usage->bytes_used = used;
1073 usage->bytes_free = free;
1074 usage->bytes_free_reclaimed = free_vm_unmapped;
1075}
1076
Dave Barachc3799992016-08-15 11:12:27 -04001077void
1078mheap_usage (void *v, clib_mem_usage_t * usage)
Ed Warnickecb9cada2015-12-08 15:45:58 -07001079{
1080 mheap_maybe_lock (v);
1081 mheap_usage_no_lock (v, usage);
1082 mheap_maybe_unlock (v);
1083}
1084
Dave Barachc3799992016-08-15 11:12:27 -04001085static u8 *
1086format_mheap_byte_count (u8 * s, va_list * va)
Ed Warnickecb9cada2015-12-08 15:45:58 -07001087{
1088 uword n_bytes = va_arg (*va, uword);
1089 if (n_bytes < 1024)
1090 return format (s, "%wd", n_bytes);
1091 else
1092 return format (s, "%wdk", n_bytes / 1024);
1093}
1094
1095/* Returns first corrupt heap element. */
Dave Barachc3799992016-08-15 11:12:27 -04001096static mheap_elt_t *
1097mheap_first_corrupt (void *v)
Ed Warnickecb9cada2015-12-08 15:45:58 -07001098{
Dave Barachc3799992016-08-15 11:12:27 -04001099 mheap_elt_t *e, *n;
Ed Warnickecb9cada2015-12-08 15:45:58 -07001100
1101 if (vec_len (v) == 0)
1102 return 0;
1103
1104 e = v;
1105 while (1)
1106 {
1107 if (e->n_user_data == MHEAP_N_USER_DATA_INVALID)
1108 break;
1109
1110 n = mheap_next_elt (e);
1111
1112 if (e->n_user_data != n->prev_n_user_data)
1113 return e;
1114
1115 if (e->is_free != n->prev_is_free)
1116 return e;
1117
1118 e = n;
1119 }
1120
1121 return 0;
1122}
1123
Dave Barachc3799992016-08-15 11:12:27 -04001124static u8 *
1125format_mheap_stats (u8 * s, va_list * va)
Ed Warnickecb9cada2015-12-08 15:45:58 -07001126{
Dave Barachc3799992016-08-15 11:12:27 -04001127 mheap_t *h = va_arg (*va, mheap_t *);
1128 mheap_stats_t *st = &h->stats;
Ed Warnickecb9cada2015-12-08 15:45:58 -07001129 uword indent = format_get_indent (s);
1130
Dave Barachc3799992016-08-15 11:12:27 -04001131 s =
1132 format (s,
1133 "alloc. from small object cache: %Ld hits %Ld attempts (%.2f%%) replacements %d",
1134 st->n_small_object_cache_hits, st->n_small_object_cache_attempts,
1135 (st->n_small_object_cache_attempts !=
1136 0 ? 100. * (f64) st->n_small_object_cache_hits /
1137 (f64) st->n_small_object_cache_attempts : 0.),
1138 h->small_object_cache.replacement_index);
Ed Warnickecb9cada2015-12-08 15:45:58 -07001139
Dave Barachc3799992016-08-15 11:12:27 -04001140 s =
1141 format (s,
1142 "\n%Ualloc. from free-list: %Ld attempts, %Ld hits (%.2f%%), %Ld considered (per-attempt %.2f)",
1143 format_white_space, indent, st->free_list.n_search_attempts,
1144 st->free_list.n_objects_found,
1145 (st->free_list.n_search_attempts !=
1146 0 ? 100. * (f64) st->free_list.n_objects_found /
1147 (f64) st->free_list.n_search_attempts : 0.),
1148 st->free_list.n_objects_searched,
1149 (st->free_list.n_search_attempts !=
1150 0 ? (f64) st->free_list.n_objects_searched /
1151 (f64) st->free_list.n_search_attempts : 0.));
Ed Warnickecb9cada2015-12-08 15:45:58 -07001152
1153 s = format (s, "\n%Ualloc. from vector-expand: %Ld",
Dave Barachc3799992016-08-15 11:12:27 -04001154 format_white_space, indent, st->n_vector_expands);
Ed Warnickecb9cada2015-12-08 15:45:58 -07001155
1156 s = format (s, "\n%Uallocs: %Ld %.2f clocks/call",
1157 format_white_space, indent,
Dave Barachc3799992016-08-15 11:12:27 -04001158 st->n_gets, (f64) st->n_clocks_get / (f64) st->n_gets);
Ed Warnickecb9cada2015-12-08 15:45:58 -07001159
1160 s = format (s, "\n%Ufrees: %Ld %.2f clocks/call",
1161 format_white_space, indent,
Dave Barachc3799992016-08-15 11:12:27 -04001162 st->n_puts, (f64) st->n_clocks_put / (f64) st->n_puts);
1163
Ed Warnickecb9cada2015-12-08 15:45:58 -07001164 return s;
1165}
1166
Dave Barachc3799992016-08-15 11:12:27 -04001167u8 *
1168format_mheap (u8 * s, va_list * va)
Ed Warnickecb9cada2015-12-08 15:45:58 -07001169{
Dave Barachc3799992016-08-15 11:12:27 -04001170 void *v = va_arg (*va, u8 *);
Ed Warnickecb9cada2015-12-08 15:45:58 -07001171 int verbose = va_arg (*va, int);
1172
Dave Barachc3799992016-08-15 11:12:27 -04001173 mheap_t *h;
Ed Warnickecb9cada2015-12-08 15:45:58 -07001174 uword i, size, indent;
1175 clib_mem_usage_t usage;
Dave Barachc3799992016-08-15 11:12:27 -04001176 mheap_elt_t *first_corrupt;
Ed Warnickecb9cada2015-12-08 15:45:58 -07001177
1178 mheap_maybe_lock (v);
1179
1180 h = mheap_header (v);
1181
1182 mheap_usage_no_lock (v, &usage);
1183
1184 indent = format_get_indent (s);
1185
Dave Barachc3799992016-08-15 11:12:27 -04001186 s =
1187 format (s,
1188 "%d objects, %U of %U used, %U free, %U reclaimed, %U overhead",
1189 usage.object_count, format_mheap_byte_count, usage.bytes_used,
1190 format_mheap_byte_count, usage.bytes_total,
1191 format_mheap_byte_count, usage.bytes_free,
1192 format_mheap_byte_count, usage.bytes_free_reclaimed,
1193 format_mheap_byte_count, usage.bytes_overhead);
Ed Warnickecb9cada2015-12-08 15:45:58 -07001194
1195 if (usage.bytes_max != ~0)
1196 s = format (s, ", %U capacity", format_mheap_byte_count, usage.bytes_max);
1197
1198 /* Show histogram of sizes. */
1199 if (verbose > 1)
1200 {
1201 uword hist[MHEAP_N_BINS];
Dave Barachc3799992016-08-15 11:12:27 -04001202 mheap_elt_t *e;
Ed Warnickecb9cada2015-12-08 15:45:58 -07001203 uword i, n_hist;
1204
1205 memset (hist, 0, sizeof (hist));
1206
1207 n_hist = 0;
1208 for (e = v;
1209 e->n_user_data != MHEAP_N_USER_DATA_INVALID;
1210 e = mheap_next_elt (e))
1211 {
1212 uword n_user_data_bytes = mheap_elt_data_bytes (e);
1213 uword bin = user_data_size_to_bin_index (n_user_data_bytes);
Dave Barachc3799992016-08-15 11:12:27 -04001214 if (!e->is_free)
Ed Warnickecb9cada2015-12-08 15:45:58 -07001215 {
1216 hist[bin] += 1;
1217 n_hist += 1;
1218 }
1219 }
1220
1221 s = format (s, "\n%U%=12s%=12s%=16s",
1222 format_white_space, indent + 2,
1223 "Size", "Count", "Fraction");
1224
1225 for (i = 0; i < ARRAY_LEN (hist); i++)
1226 {
1227 if (hist[i] == 0)
1228 continue;
1229 s = format (s, "\n%U%12d%12wd%16.4f",
1230 format_white_space, indent + 2,
Dave Barachc3799992016-08-15 11:12:27 -04001231 MHEAP_MIN_USER_DATA_BYTES +
1232 i * MHEAP_USER_DATA_WORD_BYTES, hist[i],
Ed Warnickecb9cada2015-12-08 15:45:58 -07001233 (f64) hist[i] / (f64) n_hist);
1234 }
1235 }
1236
1237 if (verbose)
1238 s = format (s, "\n%U%U",
Dave Barachc3799992016-08-15 11:12:27 -04001239 format_white_space, indent + 2, format_mheap_stats, h);
Ed Warnickecb9cada2015-12-08 15:45:58 -07001240
1241 if ((h->flags & MHEAP_FLAG_TRACE) && vec_len (h->trace_main.traces) > 0)
1242 {
1243 /* Make a copy of traces since we'll be sorting them. */
Dave Barachc3799992016-08-15 11:12:27 -04001244 mheap_trace_t *t, *traces_copy;
Ed Warnickecb9cada2015-12-08 15:45:58 -07001245 uword indent, total_objects_traced;
1246
1247 traces_copy = vec_dup (h->trace_main.traces);
1248 qsort (traces_copy, vec_len (traces_copy), sizeof (traces_copy[0]),
1249 mheap_trace_sort);
1250
1251 total_objects_traced = 0;
1252 s = format (s, "\n");
Dave Barachc3799992016-08-15 11:12:27 -04001253 vec_foreach (t, traces_copy)
1254 {
Ed Warnickecb9cada2015-12-08 15:45:58 -07001255 /* Skip over free elements. */
1256 if (t->n_allocations == 0)
1257 continue;
1258
1259 total_objects_traced += t->n_allocations;
1260
1261 /* When not verbose only report allocations of more than 1k. */
Dave Barachc3799992016-08-15 11:12:27 -04001262 if (!verbose && t->n_bytes < 1024)
1263 continue;
Ed Warnickecb9cada2015-12-08 15:45:58 -07001264
1265 if (t == traces_copy)
Dave Barachc3799992016-08-15 11:12:27 -04001266 s = format (s, "%=9s%=9s %=10s Traceback\n", "Bytes", "Count",
1267 "Sample");
1268 s = format (s, "%9d%9d %p", t->n_bytes, t->n_allocations,
1269 t->offset + v);
Ed Warnickecb9cada2015-12-08 15:45:58 -07001270 indent = format_get_indent (s);
1271 for (i = 0; i < ARRAY_LEN (t->callers) && t->callers[i]; i++)
1272 {
1273 if (i > 0)
1274 s = format (s, "%U", format_white_space, indent);
1275#ifdef CLIB_UNIX
Dave Barachc3799992016-08-15 11:12:27 -04001276 s =
1277 format (s, " %U\n", format_clib_elf_symbol_with_address,
1278 t->callers[i]);
Ed Warnickecb9cada2015-12-08 15:45:58 -07001279#else
1280 s = format (s, " %p\n", t->callers[i]);
1281#endif
1282 }
1283 }
1284
1285 s = format (s, "%d total traced objects\n", total_objects_traced);
1286
1287 vec_free (traces_copy);
Dave Barachc3799992016-08-15 11:12:27 -04001288 }
Ed Warnickecb9cada2015-12-08 15:45:58 -07001289
1290 first_corrupt = mheap_first_corrupt (v);
1291 if (first_corrupt)
1292 {
1293 size = mheap_elt_data_bytes (first_corrupt);
1294 s = format (s, "\n first corrupt object: %p, size %wd\n %U",
Dave Barachc3799992016-08-15 11:12:27 -04001295 first_corrupt, size, format_hex_bytes, first_corrupt, size);
Ed Warnickecb9cada2015-12-08 15:45:58 -07001296 }
1297
1298 /* FIXME. This output could be wrong in the unlikely case that format
1299 uses the same mheap as we are currently inspecting. */
1300 if (verbose > 1)
1301 {
Dave Barachc3799992016-08-15 11:12:27 -04001302 mheap_elt_t *e;
Ed Warnickecb9cada2015-12-08 15:45:58 -07001303 uword i, o;
1304
1305 s = format (s, "\n");
1306
1307 e = mheap_elt_at_uoffset (v, 0);
1308 i = 0;
1309 while (1)
1310 {
1311 if ((i % 8) == 0)
1312 s = format (s, "%8d: ", i);
1313
1314 o = mheap_elt_uoffset (v, e);
1315
1316 if (e->is_free)
1317 s = format (s, "(%8d) ", o);
1318 else
1319 s = format (s, " %8d ", o);
1320
1321 if ((i % 8) == 7 || (i + 1) >= h->n_elts)
1322 s = format (s, "\n");
1323 }
1324 }
1325
1326 mheap_maybe_unlock (v);
1327
1328 return s;
1329}
1330
Dave Barachc3799992016-08-15 11:12:27 -04001331void
1332dmh (void *v)
Ed Warnickecb9cada2015-12-08 15:45:58 -07001333{
Dave Barachc3799992016-08-15 11:12:27 -04001334 fformat (stderr, "%U", format_mheap, v, 1);
1335}
1336
1337static void
1338mheap_validate_breakpoint ()
1339{
1340 os_panic ();
1341}
1342
1343void
1344mheap_validate (void *v)
1345{
1346 mheap_t *h = mheap_header (v);
Ed Warnickecb9cada2015-12-08 15:45:58 -07001347 uword i, s;
1348
1349 uword elt_count, elt_size;
1350 uword free_count_from_free_lists, free_size_from_free_lists;
1351 uword small_elt_free_count, small_elt_free_size;
1352
1353#define CHECK(x) if (! (x)) { mheap_validate_breakpoint (); os_panic (); }
1354
1355 if (vec_len (v) == 0)
1356 return;
1357
1358 mheap_maybe_lock (v);
1359
1360 /* Validate number of elements and size. */
1361 free_size_from_free_lists = free_count_from_free_lists = 0;
1362 for (i = 0; i < ARRAY_LEN (h->first_free_elt_uoffset_by_bin); i++)
1363 {
Dave Barachc3799992016-08-15 11:12:27 -04001364 mheap_elt_t *e, *n;
Ed Warnickecb9cada2015-12-08 15:45:58 -07001365 uword is_first;
1366
Dave Barachb3d93da2016-08-03 14:34:38 -04001367 CHECK ((h->first_free_elt_uoffset_by_bin[i] != MHEAP_GROUNDED)
Dave Barachc3799992016-08-15 11:12:27 -04001368 ==
1369 ((h->non_empty_free_elt_heads[i /
1370 BITS (uword)] & ((uword) 1 <<
1371 (uword) (i %
1372 BITS
1373 (uword))))
1374 != 0));
Ed Warnickecb9cada2015-12-08 15:45:58 -07001375
Dave Barachb3d93da2016-08-03 14:34:38 -04001376 if (h->first_free_elt_uoffset_by_bin[i] == MHEAP_GROUNDED)
Ed Warnickecb9cada2015-12-08 15:45:58 -07001377 continue;
1378
1379 e = mheap_elt_at_uoffset (v, h->first_free_elt_uoffset_by_bin[i]);
1380 is_first = 1;
1381 while (1)
1382 {
1383 uword s;
1384
1385 n = mheap_next_elt (e);
1386
1387 /* Object must be marked free. */
1388 CHECK (e->is_free);
1389
1390 /* Next object's previous free bit must also be set. */
1391 CHECK (n->prev_is_free);
1392
1393 if (is_first)
Dave Barachb3d93da2016-08-03 14:34:38 -04001394 CHECK (e->free_elt.prev_uoffset == MHEAP_GROUNDED);
Ed Warnickecb9cada2015-12-08 15:45:58 -07001395 is_first = 0;
1396
1397 s = mheap_elt_data_bytes (e);
1398 CHECK (user_data_size_to_bin_index (s) == i);
1399
1400 free_count_from_free_lists += 1;
1401 free_size_from_free_lists += s;
1402
Dave Barachb3d93da2016-08-03 14:34:38 -04001403 if (e->free_elt.next_uoffset == MHEAP_GROUNDED)
Ed Warnickecb9cada2015-12-08 15:45:58 -07001404 break;
1405
1406 n = mheap_elt_at_uoffset (v, e->free_elt.next_uoffset);
1407
1408 /* Check free element linkages. */
1409 CHECK (n->free_elt.prev_uoffset == mheap_elt_uoffset (v, e));
1410
1411 e = n;
1412 }
1413 }
1414
1415 /* Go through small object cache. */
1416 small_elt_free_count = small_elt_free_size = 0;
1417 for (i = 0; i < ARRAY_LEN (h->small_object_cache.bins.as_u8); i++)
1418 {
1419 if (h->small_object_cache.bins.as_u8[i] != 0)
1420 {
Dave Barachc3799992016-08-15 11:12:27 -04001421 mheap_elt_t *e;
Ed Warnickecb9cada2015-12-08 15:45:58 -07001422 uword b = h->small_object_cache.bins.as_u8[i] - 1;
1423 uword o = h->small_object_cache.offsets[i];
1424 uword s;
1425
1426 e = mheap_elt_at_uoffset (v, o);
1427
1428 /* Object must be allocated. */
Dave Barachc3799992016-08-15 11:12:27 -04001429 CHECK (!e->is_free);
Ed Warnickecb9cada2015-12-08 15:45:58 -07001430
1431 s = mheap_elt_data_bytes (e);
1432 CHECK (user_data_size_to_bin_index (s) == b);
1433
1434 small_elt_free_count += 1;
1435 small_elt_free_size += s;
1436 }
1437 }
1438
1439 {
Dave Barachc3799992016-08-15 11:12:27 -04001440 mheap_elt_t *e, *n;
Ed Warnickecb9cada2015-12-08 15:45:58 -07001441 uword elt_free_size, elt_free_count;
1442
1443 elt_count = elt_size = elt_free_size = elt_free_count = 0;
Dave Barachc3799992016-08-15 11:12:27 -04001444 for (e = v; e->n_user_data != MHEAP_N_USER_DATA_INVALID; e = n)
Ed Warnickecb9cada2015-12-08 15:45:58 -07001445 {
1446 if (e->prev_n_user_data != MHEAP_N_USER_DATA_INVALID)
Dave Barachc3799992016-08-15 11:12:27 -04001447 CHECK (e->prev_n_user_data * sizeof (e->user_data[0]) >=
1448 MHEAP_MIN_USER_DATA_BYTES);
Ed Warnickecb9cada2015-12-08 15:45:58 -07001449
Dave Barachc3799992016-08-15 11:12:27 -04001450 CHECK (e->n_user_data * sizeof (e->user_data[0]) >=
1451 MHEAP_MIN_USER_DATA_BYTES);
Ed Warnickecb9cada2015-12-08 15:45:58 -07001452
1453 n = mheap_next_elt (e);
1454
1455 CHECK (e->is_free == n->prev_is_free);
1456
1457 elt_count++;
1458 s = mheap_elt_data_bytes (e);
1459 elt_size += s;
1460
1461 if (e->is_free)
1462 {
1463 elt_free_count++;
1464 elt_free_size += s;
1465 }
1466
1467 /* Consecutive free objects should have been combined. */
Dave Barachc3799992016-08-15 11:12:27 -04001468 CHECK (!(e->prev_is_free && n->prev_is_free));
Ed Warnickecb9cada2015-12-08 15:45:58 -07001469 }
1470
1471 CHECK (free_count_from_free_lists == elt_free_count);
1472 CHECK (free_size_from_free_lists == elt_free_size);
1473 CHECK (elt_count == h->n_elts + elt_free_count + small_elt_free_count);
Dave Barachc3799992016-08-15 11:12:27 -04001474 CHECK (elt_size + (elt_count + 1) * MHEAP_ELT_OVERHEAD_BYTES ==
1475 vec_len (v));
Ed Warnickecb9cada2015-12-08 15:45:58 -07001476 }
1477
1478 {
Dave Barachc3799992016-08-15 11:12:27 -04001479 mheap_elt_t *e, *n;
Ed Warnickecb9cada2015-12-08 15:45:58 -07001480
Dave Barachc3799992016-08-15 11:12:27 -04001481 for (e = v; e->n_user_data == MHEAP_N_USER_DATA_INVALID; e = n)
Ed Warnickecb9cada2015-12-08 15:45:58 -07001482 {
1483 n = mheap_next_elt (e);
1484 CHECK (e->n_user_data == n->prev_n_user_data);
1485 }
1486 }
1487
1488#undef CHECK
1489
1490 mheap_maybe_unlock (v);
1491
1492 h->validate_serial += 1;
1493}
1494
Dave Barachc3799992016-08-15 11:12:27 -04001495static void
1496mheap_get_trace (void *v, uword offset, uword size)
Ed Warnickecb9cada2015-12-08 15:45:58 -07001497{
Dave Barachc3799992016-08-15 11:12:27 -04001498 mheap_t *h;
1499 mheap_trace_main_t *tm;
1500 mheap_trace_t *t;
1501 uword i, n_callers, trace_index, *p;
Ed Warnickecb9cada2015-12-08 15:45:58 -07001502 mheap_trace_t trace;
1503
1504 /* Spurious Coverity warnings be gone. */
Dave Barachc3799992016-08-15 11:12:27 -04001505 memset (&trace, 0, sizeof (trace));
Ed Warnickecb9cada2015-12-08 15:45:58 -07001506
1507 n_callers = clib_backtrace (trace.callers, ARRAY_LEN (trace.callers),
1508 /* Skip mheap_get_aligned's frame */ 1);
1509 if (n_callers == 0)
Dave Barachc3799992016-08-15 11:12:27 -04001510 return;
Ed Warnickecb9cada2015-12-08 15:45:58 -07001511
1512 for (i = n_callers; i < ARRAY_LEN (trace.callers); i++)
1513 trace.callers[i] = 0;
1514
1515 h = mheap_header (v);
1516 tm = &h->trace_main;
1517
Dave Barachc3799992016-08-15 11:12:27 -04001518 if (!tm->trace_by_callers)
1519 tm->trace_by_callers =
1520 hash_create_mem (0, sizeof (trace.callers), sizeof (uword));
Ed Warnickecb9cada2015-12-08 15:45:58 -07001521
1522 p = hash_get_mem (tm->trace_by_callers, &trace.callers);
1523 if (p)
1524 {
1525 trace_index = p[0];
1526 t = tm->traces + trace_index;
1527 }
1528 else
1529 {
1530 i = vec_len (tm->trace_free_list);
1531 if (i > 0)
1532 {
1533 trace_index = tm->trace_free_list[i - 1];
1534 _vec_len (tm->trace_free_list) = i - 1;
1535 }
1536 else
1537 {
Dave Barachc3799992016-08-15 11:12:27 -04001538 mheap_trace_t *old_start = tm->traces;
1539 mheap_trace_t *old_end = vec_end (tm->traces);
Ed Warnickecb9cada2015-12-08 15:45:58 -07001540
1541 vec_add2 (tm->traces, t, 1);
1542
Dave Barachc3799992016-08-15 11:12:27 -04001543 if (tm->traces != old_start)
1544 {
1545 hash_pair_t *p;
1546 mheap_trace_t *q;
1547 /* *INDENT-OFF* */
Damjan Marion607de1a2016-08-16 22:53:54 +02001548 hash_foreach_pair (p, tm->trace_by_callers,
Dave Barachc3799992016-08-15 11:12:27 -04001549 ({
1550 q = uword_to_pointer (p->key, mheap_trace_t *);
1551 ASSERT (q >= old_start && q < old_end);
Ed Warnickecb9cada2015-12-08 15:45:58 -07001552 p->key = pointer_to_uword (tm->traces + (q - old_start));
1553 }));
Dave Barachc3799992016-08-15 11:12:27 -04001554 /* *INDENT-ON* */
1555 }
Ed Warnickecb9cada2015-12-08 15:45:58 -07001556 trace_index = t - tm->traces;
1557 }
1558
1559 t = tm->traces + trace_index;
1560 t[0] = trace;
1561 t->n_allocations = 0;
1562 t->n_bytes = 0;
1563 hash_set_mem (tm->trace_by_callers, t->callers, trace_index);
1564 }
1565
1566 t->n_allocations += 1;
1567 t->n_bytes += size;
Dave Barachc3799992016-08-15 11:12:27 -04001568 t->offset = offset; /* keep a sample to autopsy */
Ed Warnickecb9cada2015-12-08 15:45:58 -07001569 hash_set (tm->trace_index_by_offset, offset, t - tm->traces);
1570}
1571
Dave Barachc3799992016-08-15 11:12:27 -04001572static void
1573mheap_put_trace (void *v, uword offset, uword size)
Ed Warnickecb9cada2015-12-08 15:45:58 -07001574{
Dave Barachc3799992016-08-15 11:12:27 -04001575 mheap_t *h;
1576 mheap_trace_main_t *tm;
1577 mheap_trace_t *t;
1578 uword trace_index, *p;
Ed Warnickecb9cada2015-12-08 15:45:58 -07001579
1580 h = mheap_header (v);
1581 tm = &h->trace_main;
1582 p = hash_get (tm->trace_index_by_offset, offset);
Dave Barachc3799992016-08-15 11:12:27 -04001583 if (!p)
Ed Warnickecb9cada2015-12-08 15:45:58 -07001584 return;
1585
1586 trace_index = p[0];
1587 hash_unset (tm->trace_index_by_offset, offset);
1588 ASSERT (trace_index < vec_len (tm->traces));
1589
1590 t = tm->traces + trace_index;
1591 ASSERT (t->n_allocations > 0);
1592 ASSERT (t->n_bytes >= size);
1593 t->n_allocations -= 1;
1594 t->n_bytes -= size;
1595 if (t->n_allocations == 0)
1596 {
1597 hash_unset_mem (tm->trace_by_callers, t->callers);
1598 vec_add1 (tm->trace_free_list, trace_index);
1599 memset (t, 0, sizeof (t[0]));
1600 }
1601}
1602
Dave Barachc3799992016-08-15 11:12:27 -04001603static int
1604mheap_trace_sort (const void *_t1, const void *_t2)
Ed Warnickecb9cada2015-12-08 15:45:58 -07001605{
Dave Barachc3799992016-08-15 11:12:27 -04001606 const mheap_trace_t *t1 = _t1;
1607 const mheap_trace_t *t2 = _t2;
Ed Warnickecb9cada2015-12-08 15:45:58 -07001608 word cmp;
1609
1610 cmp = (word) t2->n_bytes - (word) t1->n_bytes;
Dave Barachc3799992016-08-15 11:12:27 -04001611 if (!cmp)
Ed Warnickecb9cada2015-12-08 15:45:58 -07001612 cmp = (word) t2->n_allocations - (word) t1->n_allocations;
1613 return cmp;
1614}
1615
1616always_inline void
1617mheap_trace_main_free (mheap_trace_main_t * tm)
1618{
1619 vec_free (tm->traces);
1620 vec_free (tm->trace_free_list);
1621 hash_free (tm->trace_by_callers);
1622 hash_free (tm->trace_index_by_offset);
1623}
1624
Dave Barachc3799992016-08-15 11:12:27 -04001625void
1626mheap_trace (void *v, int enable)
Ed Warnickecb9cada2015-12-08 15:45:58 -07001627{
Dave Barachc3799992016-08-15 11:12:27 -04001628 mheap_t *h;
Ed Warnickecb9cada2015-12-08 15:45:58 -07001629
1630 h = mheap_header (v);
1631
1632 if (enable)
1633 {
1634 h->flags |= MHEAP_FLAG_TRACE;
1635 }
1636 else
1637 {
1638 mheap_trace_main_free (&h->trace_main);
1639 h->flags &= ~MHEAP_FLAG_TRACE;
1640 }
1641}
Dave Barachc3799992016-08-15 11:12:27 -04001642
1643/*
1644 * fd.io coding-style-patch-verification: ON
1645 *
1646 * Local Variables:
1647 * eval: (c-set-style "gnu")
1648 * End:
1649 */