FD.io VPP  v16.06
Vector Packet Processing
mheap.c
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2015 Cisco and/or its affiliates.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at:
6  *
7  * http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 /*
16  Copyright (c) 2001, 2002, 2003 Eliot Dresselhaus
17 
18  Permission is hereby granted, free of charge, to any person obtaining
19  a copy of this software and associated documentation files (the
20  "Software"), to deal in the Software without restriction, including
21  without limitation the rights to use, copy, modify, merge, publish,
22  distribute, sublicense, and/or sell copies of the Software, and to
23  permit persons to whom the Software is furnished to do so, subject to
24  the following conditions:
25 
26  The above copyright notice and this permission notice shall be
27  included in all copies or substantial portions of the Software.
28 
29  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
30  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
31  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
32  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
33  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
34  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
35  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
36 */
37 
38 #include <vppinfra/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 
49 static void mheap_get_trace (void * v, uword offset, uword size);
50 static void mheap_put_trace (void * v, uword offset, uword size);
51 static int mheap_trace_sort (const void * t1, const void * t2);
52 
54 {
55  mheap_t * h = mheap_header (v);
56  if (v && (h->flags & MHEAP_FLAG_THREAD_SAFE))
57  {
58  u32 my_cpu = os_get_cpu_number();
59  if (h->owner_cpu == my_cpu)
60  {
61  h->recursion_count++;
62  return;
63  }
64 
65  while (__sync_lock_test_and_set (&h->lock, 1))
66  ;
67 
68  h->owner_cpu = my_cpu;
69  h->recursion_count = 1;
70  }
71 }
72 
74 {
75  mheap_t * h = mheap_header (v);
76  if (v && h->flags & MHEAP_FLAG_THREAD_SAFE)
77  {
79  if (--h->recursion_count == 0)
80  {
81  h->owner_cpu = ~0;
83  h->lock = 0;
84  }
85  }
86 }
87 
88 /* Find bin for objects with size at least n_user_data_bytes. */
91 {
92  uword n_user_data_words;
93  word small_bin, large_bin;
94 
95  /* User size must be at least big enough to hold free elt. */
96  n_user_data_bytes = clib_max (n_user_data_bytes, MHEAP_MIN_USER_DATA_BYTES);
97 
98  /* Round to words. */
99  n_user_data_words = (round_pow2 (n_user_data_bytes, MHEAP_USER_DATA_WORD_BYTES)
101 
102  ASSERT (n_user_data_words > 0);
103  small_bin = n_user_data_words - (MHEAP_MIN_USER_DATA_BYTES / MHEAP_USER_DATA_WORD_BYTES);
104  ASSERT (small_bin >= 0);
105 
106  large_bin = MHEAP_N_SMALL_OBJECT_BINS + max_log2 (n_user_data_bytes) - MHEAP_LOG2_N_SMALL_OBJECT_BINS;
107 
108  return small_bin < MHEAP_N_SMALL_OBJECT_BINS ? small_bin : large_bin;
109 }
110 
113 {
114  ASSERT (n_bytes >= sizeof (mheap_elt_t));
115  return (n_bytes - STRUCT_OFFSET_OF (mheap_elt_t, user_data));
116 }
117 
118 always_inline uword __attribute__((unused))
120 {
121  ASSERT (n_bytes % MHEAP_USER_DATA_WORD_BYTES == 0);
123 }
124 
125 always_inline void
127  uword uoffset,
128  uword n_user_data_bytes,
129  uword is_free)
130 {
131  mheap_elt_t * e, * n;
132 
133  e = mheap_elt_at_uoffset (v, uoffset);
134 
135  ASSERT (n_user_data_bytes % MHEAP_USER_DATA_WORD_BYTES == 0);
136  e->n_user_data = n_user_data_bytes / MHEAP_USER_DATA_WORD_BYTES;
137  e->is_free = is_free;
139 
140  n = mheap_next_elt (e);
142  n->prev_is_free = is_free;
143 }
144 
146 {
147  uword i0, i1;
148 
149  h->first_free_elt_uoffset_by_bin[bin] = uoffset;
150 
151  i0 = bin / BITS (h->non_empty_free_elt_heads[0]);
152  i1 = (uword) 1 << (uword) (bin % BITS (h->non_empty_free_elt_heads[0]));
153 
155  if (h->first_free_elt_uoffset_by_bin[bin] == ~0)
156  h->non_empty_free_elt_heads[i0] &= ~i1;
157  else
158  h->non_empty_free_elt_heads[i0] |= i1;
159 }
160 
161 always_inline void
162 set_free_elt (void * v, uword uoffset, uword n_user_data_bytes)
163 {
164  mheap_t * h = mheap_header (v);
165  mheap_elt_t * e = mheap_elt_at_uoffset (v, uoffset);
166  mheap_elt_t * n = mheap_next_elt (e);
167  uword bin = user_data_size_to_bin_index (n_user_data_bytes);
168 
169  ASSERT (n->prev_is_free);
170  ASSERT (e->is_free);
171 
172  e->free_elt.prev_uoffset = ~0;
173  e->free_elt.next_uoffset = h->first_free_elt_uoffset_by_bin[bin];
174 
175  /* Fill in next free elt's previous pointer. */
176  if (e->free_elt.next_uoffset != ~0)
177  {
178  mheap_elt_t * nf = mheap_elt_at_uoffset (v, e->free_elt.next_uoffset);
179  ASSERT (nf->is_free);
180  nf->free_elt.prev_uoffset = uoffset;
181  }
182 
183  set_first_free_elt_offset (h, bin, uoffset);
184 }
185 
186 always_inline void
187 new_free_elt (void * v, uword uoffset, uword n_user_data_bytes)
188 {
189  mheap_elt_set_size (v, uoffset, n_user_data_bytes, /* is_free */ 1);
190  set_free_elt (v, uoffset, n_user_data_bytes);
191 }
192 
193 always_inline void
194 remove_free_elt (void * v, mheap_elt_t * e, uword bin)
195 {
196  mheap_t * h = mheap_header (v);
197  mheap_elt_t * p, * n;
198  u32 no, po;
199 
200  no = e->free_elt.next_uoffset;
201  n = no != ~0 ? mheap_elt_at_uoffset (v, no) : 0;
202  po = e->free_elt.prev_uoffset;
203  p = po != ~0 ? mheap_elt_at_uoffset (v, po) : 0;
204 
205  if (! p)
206  set_first_free_elt_offset (h, bin, no);
207  else
208  p->free_elt.next_uoffset = no;
209 
210  if (n)
211  n->free_elt.prev_uoffset = po;
212 }
213 
214 always_inline void
216 {
217  uword bin;
219  remove_free_elt (v, e, bin);
220 }
221 
222 #define MHEAP_VM_MAP (1 << 0)
223 #define MHEAP_VM_UNMAP (1 << 1)
224 #define MHEAP_VM_NOMAP (0 << 1)
225 #define MHEAP_VM_ROUND (1 << 2)
226 #define MHEAP_VM_ROUND_UP MHEAP_VM_ROUND
227 #define MHEAP_VM_ROUND_DOWN (0 << 2)
228 
230 
232 { return (addr + mheap_page_size - 1) &~ (mheap_page_size - 1); }
233 
235 { return addr &~ (mheap_page_size - 1); }
236 
238 mheap_vm (void * v,
239  uword flags,
240  clib_address_t start_addr,
241  uword size)
242 {
243  mheap_t * h = mheap_header (v);
244  clib_address_t start_page, end_page, end_addr;
245  uword mapped_bytes;
246 
248 
249  end_addr = start_addr + size;
250 
251  /* Round start/end address up to page boundary. */
252  start_page = mheap_page_round (start_addr);
253 
254  if ((flags & MHEAP_VM_ROUND) == MHEAP_VM_ROUND_UP)
255  end_page = mheap_page_round (end_addr);
256  else
257  end_page = mheap_page_truncate (end_addr);
258 
259  mapped_bytes = 0;
260  if (end_page > start_page)
261  {
262  mapped_bytes = end_page - start_page;
263  if (flags & MHEAP_VM_MAP)
264  clib_mem_vm_map ((void *) start_page, end_page - start_page);
265  else if (flags & MHEAP_VM_UNMAP)
266  clib_mem_vm_unmap ((void *) start_page, end_page - start_page);
267  }
268 
269  return mapped_bytes;
270 }
271 
273 mheap_vm_elt (void * v, uword flags, uword offset)
274 {
275  mheap_elt_t * e;
276  clib_address_t start_addr, end_addr;
277 
278  e = mheap_elt_at_uoffset (v, offset);
279  start_addr = (clib_address_t) ((void *) e->user_data);
280  end_addr = (clib_address_t) mheap_next_elt (e);
281  return mheap_vm (v, flags, start_addr, end_addr - start_addr);
282 }
283 
286 {
287  uword mask;
288 
289 /* $$$$ ELIOT FIXME: add Altivec version of this routine */
290 #if !defined (CLIB_HAVE_VEC128) || defined (__ALTIVEC__)
291  mask = 0;
292 #else
293  u8x16 b = u8x16_splat (bin);
294 
295  ASSERT (bin < 256);
296 
297 #define _(i) ((uword) u8x16_compare_byte_mask (u8x16_is_equal (b, c->bins.as_u8x16[i])) << (uword) ((i)*16))
298  mask = _ (0) | _ (1);
299  if (BITS (uword) > 32)
300  mask |= _ (2) | _ (3);
301 #undef _
302 
303 #endif
304  return mask;
305 }
306 
309 {
311  uword mask = mheap_small_object_cache_mask (c, bin + 1);
312  uword offset = ~0;
313 
314  if (mask)
315  {
316  uword i = min_log2 (mask);
317  uword o = c->offsets[i];
318  ASSERT (o != ~0);
319  c->bins.as_u8[i] = 0;
320  offset = o;
321  }
322 
323  return offset;
324 }
325 
328 {
330  uword free_mask = mheap_small_object_cache_mask (c, 0);
331  uword b = bin + 1;
332  uword i;
333 
334  if (free_mask != 0)
335  {
336  i = min_log2 (free_mask);
337  c->bins.as_u8[i] = b;
338  c->offsets[i] = offset;
339  return 0;
340  }
341  else
342  /* Nothing free with right size: cyclic replacement. */
343  {
344  uword old_offset;
345 
346  i = c->replacement_index++;
347  i %= BITS (uword);
348  c->bins.as_u8[i] = b;
349  old_offset = c->offsets[i];
350  c->offsets[i] = offset;
351 
352  /* Return old offset so it can be freed. */
353  return old_offset;
354  }
355 }
356 
357 static uword
359  uword bin,
360  uword * n_user_data_bytes_arg,
361  uword align,
362  uword align_offset)
363 {
364  mheap_t * h = mheap_header (v);
365  mheap_elt_t * e;
366 
367  /* Free object is at offset f0 ... f1;
368  Allocatted object is at offset o0 ... o1. */
369  word o0, o1, f0, f1, search_n_user_data_bytes;
370  word lo_free_usize, hi_free_usize;
371 
372  ASSERT (h->first_free_elt_uoffset_by_bin[bin] != ~0);
374 
375  search_n_user_data_bytes = *n_user_data_bytes_arg;
376 
377  /* Silence compiler warning. */
378  o0 = o1 = f0 = f1 = 0;
379 
381 
382  /* Find an object that is large enough with correct alignment at given alignment offset. */
383  while (1)
384  {
385  uword this_object_n_user_data_bytes = mheap_elt_data_bytes (e);
386 
387  ASSERT (e->is_free);
388  if (bin < MHEAP_N_SMALL_OBJECT_BINS)
389  ASSERT (this_object_n_user_data_bytes >= search_n_user_data_bytes);
390 
392 
393  if (this_object_n_user_data_bytes < search_n_user_data_bytes)
394  goto next;
395 
396  /* Bounds of free object: from f0 to f1. */
397  f0 = ((void *) e->user_data - v);
398  f1 = f0 + this_object_n_user_data_bytes;
399 
400  /* Place candidate object at end of free block and align as requested. */
401  o0 = ((f1 - search_n_user_data_bytes) &~ (align - 1)) - align_offset;
402  while (o0 < f0)
403  o0 += align;
404 
405  /* Make sure that first free fragment is either empty or
406  large enough to be valid. */
407  while (1)
408  {
409  lo_free_usize = o0 != f0 ? o0 - f0 - MHEAP_ELT_OVERHEAD_BYTES : 0;
410  if (o0 <= f0 || lo_free_usize >= (word) MHEAP_MIN_USER_DATA_BYTES)
411  break;
412  o0 -= align;
413  }
414 
415  o1 = o0 + search_n_user_data_bytes;
416 
417  /* Does it fit? */
418  if (o0 >= f0 && o1 <= f1)
419  goto found;
420 
421  next:
422  /* Reached end of free list without finding large enough object. */
423  if (e->free_elt.next_uoffset == ~0)
424  return ~0;
425 
426  /* Otherwise keep searching for large enough object. */
427  e = mheap_elt_at_uoffset (v, e->free_elt.next_uoffset);
428  }
429 
430  found:
431  /* Free fragment at end. */
432  hi_free_usize = f1 != o1 ? f1 - o1 - MHEAP_ELT_OVERHEAD_BYTES : 0;
433 
434  /* If fragment at end is too small to be a new object,
435  give user's object a bit more space than requested. */
436  if (hi_free_usize < (word) MHEAP_MIN_USER_DATA_BYTES)
437  {
438  search_n_user_data_bytes += f1 - o1;
439  o1 = f1;
440  hi_free_usize = 0;
441  }
442 
443  /* Need to make sure that relevant memory areas are mapped. */
444  if (! (h->flags & MHEAP_FLAG_DISABLE_VM))
445  {
446  mheap_elt_t * f0_elt = mheap_elt_at_uoffset (v, f0);
447  mheap_elt_t * f1_elt = mheap_elt_at_uoffset (v, f1);
448  mheap_elt_t * o0_elt = mheap_elt_at_uoffset (v, o0);
449  mheap_elt_t * o1_elt = mheap_elt_at_uoffset (v, o1);
450 
451  uword f0_page_start, f0_page_end;
452  uword o0_page_start, o0_page_end;
453 
454  /* Free elt is mapped. Addresses after that may not be mapped. */
455  f0_page_start = mheap_page_round (pointer_to_uword (f0_elt->user_data));
456  f0_page_end = mheap_page_truncate (pointer_to_uword (f1_elt));
457 
458  o0_page_start = mheap_page_truncate (pointer_to_uword (o0_elt));
459  o0_page_end = mheap_page_round (pointer_to_uword (o1_elt->user_data));
460 
461  if (o0_page_start < f0_page_start)
462  o0_page_start = f0_page_start;
463  if (o0_page_end > f0_page_end)
464  o0_page_end = f0_page_end;
465 
466  if (o0_page_end > o0_page_start)
467  clib_mem_vm_map (uword_to_pointer (o0_page_start, void *),
468  o0_page_end - o0_page_start);
469  }
470 
471  /* Remove free object from free list. */
472  remove_free_elt (v, e, bin);
473 
474  /* Free fragment at begining. */
475  if (lo_free_usize > 0)
476  {
477  ASSERT (lo_free_usize >= (word) MHEAP_MIN_USER_DATA_BYTES);
478  mheap_elt_set_size (v, f0, lo_free_usize, /* is_free */ 1);
479  new_free_elt (v, f0, lo_free_usize);
480  }
481 
482  mheap_elt_set_size (v, o0, search_n_user_data_bytes, /* is_free */ 0);
483 
484  if (hi_free_usize > 0)
485  {
487  mheap_elt_set_size (v, uo, hi_free_usize, /* is_free */ 1);
488  new_free_elt (v, uo, hi_free_usize);
489  }
490 
491  /* Return actual size of block. */
492  *n_user_data_bytes_arg = search_n_user_data_bytes;
493 
495 
496  return o0;
497 }
498 
499 /* Search free lists for object with given size and alignment. */
500 static uword
502  uword * n_user_bytes_arg,
503  uword align,
504  uword align_offset)
505 {
506  mheap_t * h = mheap_header (v);
507  uword bin, n_user_bytes, i, bi;
508 
509  n_user_bytes = *n_user_bytes_arg;
510  bin = user_data_size_to_bin_index (n_user_bytes);
511 
514  && bin < 255
515  && align == STRUCT_SIZE_OF (mheap_elt_t, user_data[0])
516  && align_offset == 0)
517  {
518  uword r = mheap_get_small_object (h, bin);
520  if (r != ~0)
521  {
523  return r;
524  }
525  }
526 
527  for (i = bin / BITS (uword); i < ARRAY_LEN (h->non_empty_free_elt_heads); i++)
528  {
529  uword non_empty_bin_mask = h->non_empty_free_elt_heads[i];
530 
531  /* No need to search smaller bins. */
532  if (i == bin / BITS (uword))
533  non_empty_bin_mask &= ~pow2_mask (bin % BITS (uword));
534 
535  /* Search each occupied free bin which is large enough. */
536  foreach_set_bit (bi, non_empty_bin_mask, ({
537  uword r = mheap_get_search_free_bin (v, bi + i * BITS (uword), n_user_bytes_arg, align, align_offset);
538  if (r != ~0)
539  return r;
540  }));
541  }
542 
543  return ~0;
544 }
545 
546 static never_inline void *
548  uword n_user_data_bytes,
549  uword align,
550  uword align_offset,
551  uword * offset_return)
552 {
553  /* Bounds of free and allocated objects (as above). */
554  uword f0, f1, o0, o1;
555  word free_size;
556  mheap_t * h = mheap_header (v);
557  mheap_elt_t * e;
558 
559  if (_vec_len (v) == 0)
560  {
561  _vec_len (v) = MHEAP_ELT_OVERHEAD_BYTES;
562 
563  /* Create first element of heap. */
564  e = mheap_elt_at_uoffset (v, _vec_len (v));
566  }
567 
568  f0 = _vec_len (v);
569 
570  o0 = round_pow2 (f0, align) - align_offset;
571  while (1)
572  {
573  free_size = o0 - f0 - MHEAP_ELT_OVERHEAD_BYTES;
574  if (o0 == f0 || free_size >= (word) sizeof (mheap_elt_t))
575  break;
576 
577  o0 += align;
578  }
579 
580  o1 = o0 + n_user_data_bytes;
581  f1 = o1 + MHEAP_ELT_OVERHEAD_BYTES;
582 
583  ASSERT (v != 0);
584  h = mheap_header (v);
585 
586  /* Make sure we have space for object plus overhead. */
587  if (f1 > h->max_size)
588  {
589  *offset_return = ~0;
590  return v;
591  }
592 
593  _vec_len (v) = f1;
594 
595  if (! (h->flags & MHEAP_FLAG_DISABLE_VM))
596  {
597  mheap_elt_t * f0_elt = mheap_elt_at_uoffset (v, f0);
598  mheap_elt_t * f1_elt = mheap_elt_at_uoffset (v, f1);
599 
600  uword f0_page = mheap_page_round (pointer_to_uword (f0_elt->user_data));
601  uword f1_page = mheap_page_round (pointer_to_uword (f1_elt->user_data));
602 
603  if (f1_page > f0_page)
604  mheap_vm (v, MHEAP_VM_MAP, f0_page, f1_page - f0_page);
605  }
606 
607  if (free_size > 0)
608  new_free_elt (v, f0, free_size);
609 
610  mheap_elt_set_size (v, o0, n_user_data_bytes, /* is_free */ 0);
611 
612  /* Mark last element. */
613  e = mheap_elt_at_uoffset (v, f1);
615 
616  *offset_return = o0;
617 
618  return v;
619 }
620 
621 void * mheap_get_aligned (void * v,
622  uword n_user_data_bytes,
623  uword align,
624  uword align_offset,
625  uword * offset_return)
626 {
627  mheap_t * h;
628  uword offset;
629  u64 cpu_times[2];
630 
631  cpu_times[0] = clib_cpu_time_now ();
632 
633  align = clib_max (align, STRUCT_SIZE_OF (mheap_elt_t, user_data[0]));
634  align = max_pow2 (align);
635 
636  /* Correct align offset to be smaller than alignment. */
637  align_offset &= (align - 1);
638 
639  /* Align offset must be multiple of minimum object size. */
640  if (align_offset % STRUCT_SIZE_OF (mheap_elt_t, user_data[0]) != 0)
641  {
642  *offset_return = ~0;
643  return v;
644  }
645 
646  /* Round requested size. */
647  n_user_data_bytes = clib_max (n_user_data_bytes, MHEAP_MIN_USER_DATA_BYTES);
648  n_user_data_bytes = round_pow2 (n_user_data_bytes, STRUCT_SIZE_OF (mheap_elt_t, user_data[0]));
649 
650  if (! v)
651  v = mheap_alloc (0, 64 << 20);
652 
653  mheap_maybe_lock (v);
654 
655  h = mheap_header (v);
656 
657  if (h->flags & MHEAP_FLAG_VALIDATE)
658  mheap_validate (v);
659 
660  /* First search free lists for object. */
661  offset = mheap_get_search_free_list (v, &n_user_data_bytes, align, align_offset);
662 
663  h = mheap_header (v);
664 
665  /* If that fails allocate object at end of heap by extending vector. */
666  if (offset == ~0 && _vec_len (v) < h->max_size)
667  {
668  v = mheap_get_extend_vector (v, n_user_data_bytes, align, align_offset, &offset);
669  h = mheap_header (v);
670  h->stats.n_vector_expands += offset != ~0;
671  }
672 
673  *offset_return = offset;
674  if (offset != ~0)
675  {
676  h->n_elts += 1;
677 
678  if (h->flags & MHEAP_FLAG_TRACE)
679  {
680  /* Recursion block for case when we are traceing main clib heap. */
681  h->flags &= ~MHEAP_FLAG_TRACE;
682 
683  mheap_get_trace (v, offset, n_user_data_bytes);
684 
685  h->flags |= MHEAP_FLAG_TRACE;
686  }
687  }
688 
689  if (h->flags & MHEAP_FLAG_VALIDATE)
690  mheap_validate (v);
691 
692  mheap_maybe_unlock (v);
693 
694  cpu_times[1] = clib_cpu_time_now ();
695  h->stats.n_clocks_get += cpu_times[1] - cpu_times[0];
696  h->stats.n_gets += 1;
697 
698  return v;
699 }
700 
701 static void free_last_elt (void * v, mheap_elt_t * e)
702 {
703  mheap_t * h = mheap_header (v);
704 
705  /* Possibly delete preceeding free element also. */
706  if (e->prev_is_free)
707  {
708  e = mheap_prev_elt (e);
709  remove_free_elt2 (v, e);
710  }
711 
713  {
714  if (! (h->flags & MHEAP_FLAG_DISABLE_VM))
716  _vec_len (v) = 0;
717  }
718  else
719  {
720  uword uo = mheap_elt_uoffset (v, e);
721  if (! (h->flags & MHEAP_FLAG_DISABLE_VM))
722  mheap_vm_elt (v, MHEAP_VM_UNMAP, uo);
724  _vec_len (v) = uo;
725  }
726 }
727 
728 void mheap_put (void * v, uword uoffset)
729 {
730  mheap_t * h;
731  uword n_user_data_bytes, bin;
732  mheap_elt_t * e, * n;
733  uword trace_uoffset, trace_n_user_data_bytes;
734  u64 cpu_times[2];
735 
736  cpu_times[0] = clib_cpu_time_now ();
737 
738  h = mheap_header (v);
739 
740  mheap_maybe_lock (v);
741 
742  if (h->flags & MHEAP_FLAG_VALIDATE)
743  mheap_validate (v);
744 
745  ASSERT (h->n_elts > 0);
746  h->n_elts--;
747  h->stats.n_puts += 1;
748 
749  e = mheap_elt_at_uoffset (v, uoffset);
750  n = mheap_next_elt (e);
751  n_user_data_bytes = mheap_elt_data_bytes (e);
752 
753  trace_uoffset = uoffset;
754  trace_n_user_data_bytes = n_user_data_bytes;
755 
756  bin = user_data_size_to_bin_index (n_user_data_bytes);
758  && bin < 255
760  {
761  uoffset = mheap_put_small_object (h, bin, uoffset);
762  if (uoffset == 0)
763  goto done;
764 
765  e = mheap_elt_at_uoffset (v, uoffset);
766  n = mheap_next_elt (e);
767  n_user_data_bytes = mheap_elt_data_bytes (e);
768  }
769 
770  /* Assert that forward and back pointers are equal. */
771  if (e->n_user_data != n->prev_n_user_data)
772  os_panic ();
773 
774  /* Forward and backwards is_free must agree. */
775  if (e->is_free != n->prev_is_free)
776  os_panic ();
777 
778  /* Object was already freed. */
779  if (e->is_free)
780  os_panic ();
781 
782  /* Special case: delete last element in heap. */
784  free_last_elt (v, e);
785 
786  else
787  {
788  uword f0, f1, n_combine;
789 
790  f0 = uoffset;
791  f1 = f0 + n_user_data_bytes;
792  n_combine = 0;
793 
794  if (e->prev_is_free)
795  {
796  mheap_elt_t * p = mheap_prev_elt (e);
797  f0 = mheap_elt_uoffset (v, p);
798  remove_free_elt2 (v, p);
799  n_combine++;
800  }
801 
802  if (n->is_free)
803  {
804  mheap_elt_t * m = mheap_next_elt (n);
805  f1 = (void *) m - v;
806  remove_free_elt2 (v, n);
807  n_combine++;
808  }
809 
810  if (n_combine)
811  mheap_elt_set_size (v, f0, f1 - f0, /* is_free */ 1);
812  else
813  e->is_free = n->prev_is_free = 1;
814  set_free_elt (v, f0, f1 - f0);
815 
816  if (! (h->flags & MHEAP_FLAG_DISABLE_VM))
817  mheap_vm_elt (v, MHEAP_VM_UNMAP, f0);
818  }
819 
820  done:
821  h = mheap_header (v);
822 
823  if (h->flags & MHEAP_FLAG_TRACE)
824  {
825  /* Recursion block for case when we are traceing main clib heap. */
826  h->flags &= ~MHEAP_FLAG_TRACE;
827 
828  mheap_put_trace (v, trace_uoffset, trace_n_user_data_bytes);
829 
830  h->flags |= MHEAP_FLAG_TRACE;
831  }
832 
833  if (h->flags & MHEAP_FLAG_VALIDATE)
834  mheap_validate (v);
835 
836  mheap_maybe_unlock (v);
837 
838  cpu_times[1] = clib_cpu_time_now ();
839  h->stats.n_clocks_put += cpu_times[1] - cpu_times[0];
840 }
841 
842 void * mheap_alloc_with_flags (void * memory, uword memory_size, uword flags)
843 {
844  mheap_t * h;
845  void * v;
846  uword size;
847 
848  if (! mheap_page_size)
849  mheap_page_size = clib_mem_get_page_size ();
850 
851  if (! memory)
852  {
853  /* No memory given, try to VM allocate some. */
854  memory = clib_mem_vm_alloc (memory_size);
855  if (! memory)
856  return 0;
857 
858  /* No memory region implies we have virtual memory. */
859  flags &= ~MHEAP_FLAG_DISABLE_VM;
860  }
861 
862  /* Make sure that given memory is page aligned. */
863  {
864  uword am, av, ah;
865 
866  am = pointer_to_uword (memory);
867  av = mheap_page_round (am);
868  v = uword_to_pointer (av, void *);
869  h = mheap_header (v);
870  ah = pointer_to_uword (h);
871  while (ah < am)
872  ah += mheap_page_size;
873 
874  h = uword_to_pointer (ah, void *);
875  v = mheap_vector (h);
876 
877  size = memory + memory_size - v;
878  }
879 
880  /* VM map header so we can use memory. */
881  if (! (flags & MHEAP_FLAG_DISABLE_VM))
882  clib_mem_vm_map (h, sizeof (h[0]));
883 
884  /* Zero vector header: both heap header and vector length. */
885  memset (h, 0, sizeof (h[0]));
886  _vec_len (v) = 0;
887 
888  h->vm_alloc_offset_from_header = (void *) h - memory;
889  h->vm_alloc_size = memory_size;
890 
891  h->max_size = size;
892  h->owner_cpu = ~0;
893 
894  /* Set flags based on those given less builtin-flags. */
895  h->flags |= (flags &~ MHEAP_FLAG_TRACE);
896 
897  /* Unmap remainder of heap until we will be ready to use it. */
898  if (! (h->flags & MHEAP_FLAG_DISABLE_VM))
900  (clib_address_t) v, h->max_size);
901 
902  /* Initialize free list heads to empty. */
904 
905  return v;
906 }
907 
908 void * mheap_alloc (void * memory, uword size)
909 {
910  uword flags = 0;
911 
912  if (memory != 0)
913  flags |= MHEAP_FLAG_DISABLE_VM;
914 
915 #ifdef CLIB_HAVE_VEC128
917 #endif
918 
919  return mheap_alloc_with_flags (memory, size, flags);
920 }
921 
922 void * _mheap_free (void * v)
923 {
924  mheap_t * h = mheap_header (v);
925 
926  if (v)
928 
929  return 0;
930 }
931 
932 /* Call user's function with each object in heap. */
933 void mheap_foreach (void * v,
934  uword (* func) (void * arg, void * v, void * elt_data, uword elt_size),
935  void * arg)
936 {
937  mheap_elt_t * e;
938  u8 * stack_heap, * clib_mem_mheap_save;
939  u8 tmp_heap_memory[16*1024];
940 
941  mheap_maybe_lock (v);
942 
943  if (vec_len (v) == 0)
944  goto done;
945 
946  clib_mem_mheap_save = 0;
947  stack_heap = 0;
948 
949  /* Allocate a new temporary heap on the stack.
950  This is so that our hash table & user's callback function can
951  themselves allocate memory somewhere without getting in the way
952  of the heap we are looking at. */
953  if (v == clib_mem_get_heap ())
954  {
955  stack_heap = mheap_alloc (tmp_heap_memory, sizeof (tmp_heap_memory));
956  clib_mem_mheap_save = v;
957  clib_mem_set_heap (stack_heap);
958  }
959 
960  for (e = v;
962  e = mheap_next_elt (e))
963  {
964  void * p = mheap_elt_data (v, e);
965  if (e->is_free)
966  continue;
967  if ((* func) (arg, v, p, mheap_elt_data_bytes (e)))
968  break;
969  }
970 
971  /* Restore main CLIB heap. */
972  if (clib_mem_mheap_save)
973  clib_mem_set_heap (clib_mem_mheap_save);
974 
975  done:
976  mheap_maybe_unlock (v);
977 }
978 
979 /* Bytes in mheap header overhead not including data bytes. */
982 {
983  mheap_t * h = mheap_header (v);
984  return v ? sizeof (h[0]) + h->n_elts * sizeof (mheap_elt_t) : 0;
985 }
986 
987 /* Total number of bytes including both data and overhead. */
988 uword mheap_bytes (void * v)
989 { return mheap_bytes_overhead (v) + vec_bytes (v); }
990 
991 static void mheap_usage_no_lock (void * v, clib_mem_usage_t * usage)
992 {
993  mheap_t * h = mheap_header (v);
994  uword used = 0, free = 0, free_vm_unmapped = 0;
995 
996  if (vec_len (v) > 0)
997  {
998  mheap_elt_t * e;
999 
1000  for (e = v;
1002  e = mheap_next_elt (e))
1003  {
1005  if (e->is_free)
1006  {
1007  free += size;
1008  if (! (h->flags & MHEAP_FLAG_DISABLE_VM))
1009  free_vm_unmapped +=
1011  }
1012  else
1013  used += size;
1014  }
1015  }
1016 
1017  usage->object_count = mheap_elts (v);
1018  usage->bytes_total = mheap_bytes (v);
1019  usage->bytes_overhead = mheap_bytes_overhead (v);
1020  usage->bytes_max = mheap_max_size (v);
1021  usage->bytes_used = used;
1022  usage->bytes_free = free;
1023  usage->bytes_free_reclaimed = free_vm_unmapped;
1024 }
1025 
1027 {
1028  mheap_maybe_lock (v);
1029  mheap_usage_no_lock (v, usage);
1030  mheap_maybe_unlock (v);
1031 }
1032 
1033 static u8 * format_mheap_byte_count (u8 * s, va_list * va)
1034 {
1035  uword n_bytes = va_arg (*va, uword);
1036  if (n_bytes < 1024)
1037  return format (s, "%wd", n_bytes);
1038  else
1039  return format (s, "%wdk", n_bytes / 1024);
1040 }
1041 
1042 /* Returns first corrupt heap element. */
1044 {
1045  mheap_elt_t * e, * n;
1046 
1047  if (vec_len (v) == 0)
1048  return 0;
1049 
1050  e = v;
1051  while (1)
1052  {
1054  break;
1055 
1056  n = mheap_next_elt (e);
1057 
1058  if (e->n_user_data != n->prev_n_user_data)
1059  return e;
1060 
1061  if (e->is_free != n->prev_is_free)
1062  return e;
1063 
1064  e = n;
1065  }
1066 
1067  return 0;
1068 }
1069 
1070 static u8 * format_mheap_stats (u8 * s, va_list * va)
1071 {
1072  mheap_t * h = va_arg (*va, mheap_t *);
1073  mheap_stats_t * st = &h->stats;
1074  uword indent = format_get_indent (s);
1075 
1076  s = format (s, "alloc. from small object cache: %Ld hits %Ld attempts (%.2f%%) replacements %d",
1081  : 0.),
1083 
1084  s = format (s, "\n%Ualloc. from free-list: %Ld attempts, %Ld hits (%.2f%%), %Ld considered (per-attempt %.2f)",
1085  format_white_space, indent,
1088  (st->free_list.n_search_attempts != 0
1090  : 0.),
1092  (st->free_list.n_search_attempts != 0
1094  : 0.));
1095 
1096  s = format (s, "\n%Ualloc. from vector-expand: %Ld",
1097  format_white_space, indent,
1098  st->n_vector_expands);
1099 
1100  s = format (s, "\n%Uallocs: %Ld %.2f clocks/call",
1101  format_white_space, indent,
1102  st->n_gets,
1103  (f64) st->n_clocks_get / (f64) st->n_gets);
1104 
1105  s = format (s, "\n%Ufrees: %Ld %.2f clocks/call",
1106  format_white_space, indent,
1107  st->n_puts,
1108  (f64) st->n_clocks_put / (f64) st->n_puts);
1109 
1110  return s;
1111 }
1112 
1113 u8 * format_mheap (u8 * s, va_list * va)
1114 {
1115  void * v = va_arg (*va, u8 *);
1116  int verbose = va_arg (*va, int);
1117 
1118  mheap_t * h;
1119  uword i, size, indent;
1121  mheap_elt_t * first_corrupt;
1122 
1123  mheap_maybe_lock (v);
1124 
1125  h = mheap_header (v);
1126 
1127  mheap_usage_no_lock (v, &usage);
1128 
1129  indent = format_get_indent (s);
1130 
1131  s = format (s, "%d objects, %U of %U used, %U free, %U reclaimed, %U overhead",
1132  usage.object_count,
1138 
1139  if (usage.bytes_max != ~0)
1140  s = format (s, ", %U capacity", format_mheap_byte_count, usage.bytes_max);
1141 
1142  /* Show histogram of sizes. */
1143  if (verbose > 1)
1144  {
1145  uword hist[MHEAP_N_BINS];
1146  mheap_elt_t * e;
1147  uword i, n_hist;
1148 
1149  memset (hist, 0, sizeof (hist));
1150 
1151  n_hist = 0;
1152  for (e = v;
1154  e = mheap_next_elt (e))
1155  {
1156  uword n_user_data_bytes = mheap_elt_data_bytes (e);
1157  uword bin = user_data_size_to_bin_index (n_user_data_bytes);
1158  if (! e->is_free)
1159  {
1160  hist[bin] += 1;
1161  n_hist += 1;
1162  }
1163  }
1164 
1165  s = format (s, "\n%U%=12s%=12s%=16s",
1166  format_white_space, indent + 2,
1167  "Size", "Count", "Fraction");
1168 
1169  for (i = 0; i < ARRAY_LEN (hist); i++)
1170  {
1171  if (hist[i] == 0)
1172  continue;
1173  s = format (s, "\n%U%12d%12wd%16.4f",
1174  format_white_space, indent + 2,
1176  hist[i],
1177  (f64) hist[i] / (f64) n_hist);
1178  }
1179  }
1180 
1181  if (verbose)
1182  s = format (s, "\n%U%U",
1183  format_white_space, indent + 2,
1184  format_mheap_stats, h);
1185 
1186  if ((h->flags & MHEAP_FLAG_TRACE) && vec_len (h->trace_main.traces) > 0)
1187  {
1188  /* Make a copy of traces since we'll be sorting them. */
1189  mheap_trace_t * t, * traces_copy;
1190  uword indent, total_objects_traced;
1191 
1192  traces_copy = vec_dup (h->trace_main.traces);
1193  qsort (traces_copy, vec_len (traces_copy), sizeof (traces_copy[0]),
1195 
1196  total_objects_traced = 0;
1197  s = format (s, "\n");
1198  vec_foreach (t, traces_copy) {
1199  /* Skip over free elements. */
1200  if (t->n_allocations == 0)
1201  continue;
1202 
1203  total_objects_traced += t->n_allocations;
1204 
1205  /* When not verbose only report allocations of more than 1k. */
1206  if (! verbose && t->n_bytes < 1024)
1207  continue;
1208 
1209  if (t == traces_copy)
1210  s = format (s, "%=9s%=9s %=10s Traceback\n", "Bytes", "Count",
1211  "Sample");
1212  s = format (s, "%9d%9d %p", t->n_bytes, t->n_allocations,
1213  t->offset + v);
1214  indent = format_get_indent (s);
1215  for (i = 0; i < ARRAY_LEN (t->callers) && t->callers[i]; i++)
1216  {
1217  if (i > 0)
1218  s = format (s, "%U", format_white_space, indent);
1219 #ifdef CLIB_UNIX
1220  s = format (s, " %U\n", format_clib_elf_symbol_with_address, t->callers[i]);
1221 #else
1222  s = format (s, " %p\n", t->callers[i]);
1223 #endif
1224  }
1225  }
1226 
1227  s = format (s, "%d total traced objects\n", total_objects_traced);
1228 
1229  vec_free (traces_copy);
1230  }
1231 
1232  first_corrupt = mheap_first_corrupt (v);
1233  if (first_corrupt)
1234  {
1235  size = mheap_elt_data_bytes (first_corrupt);
1236  s = format (s, "\n first corrupt object: %p, size %wd\n %U",
1237  first_corrupt,
1238  size,
1239  format_hex_bytes, first_corrupt, size);
1240  }
1241 
1242  /* FIXME. This output could be wrong in the unlikely case that format
1243  uses the same mheap as we are currently inspecting. */
1244  if (verbose > 1)
1245  {
1246  mheap_elt_t * e;
1247  uword i, o;
1248 
1249  s = format (s, "\n");
1250 
1251  e = mheap_elt_at_uoffset (v, 0);
1252  i = 0;
1253  while (1)
1254  {
1255  if ((i % 8) == 0)
1256  s = format (s, "%8d: ", i);
1257 
1258  o = mheap_elt_uoffset (v, e);
1259 
1260  if (e->is_free)
1261  s = format (s, "(%8d) ", o);
1262  else
1263  s = format (s, " %8d ", o);
1264 
1265  if ((i % 8) == 7 || (i + 1) >= h->n_elts)
1266  s = format (s, "\n");
1267  }
1268  }
1269 
1270  mheap_maybe_unlock (v);
1271 
1272  return s;
1273 }
1274 
1275 void dmh (void * v)
1276 { fformat (stderr, "%U", format_mheap, v, 1); }
1277 
1279 { os_panic (); }
1280 
1281 void mheap_validate (void * v)
1282 {
1283  mheap_t * h = mheap_header (v);
1284  uword i, s;
1285 
1286  uword elt_count, elt_size;
1287  uword free_count_from_free_lists, free_size_from_free_lists;
1288  uword small_elt_free_count, small_elt_free_size;
1289 
1290 #define CHECK(x) if (! (x)) { mheap_validate_breakpoint (); os_panic (); }
1291 
1292  if (vec_len (v) == 0)
1293  return;
1294 
1295  mheap_maybe_lock (v);
1296 
1297  /* Validate number of elements and size. */
1298  free_size_from_free_lists = free_count_from_free_lists = 0;
1299  for (i = 0; i < ARRAY_LEN (h->first_free_elt_uoffset_by_bin); i++)
1300  {
1301  mheap_elt_t * e, * n;
1302  uword is_first;
1303 
1304  CHECK ((h->first_free_elt_uoffset_by_bin[i] != ~0)
1305  == ((h->non_empty_free_elt_heads[i / BITS (uword)] & ((uword) 1 << (uword) (i % BITS (uword)))) != 0));
1306 
1307  if (h->first_free_elt_uoffset_by_bin[i] == ~0)
1308  continue;
1309 
1311  is_first = 1;
1312  while (1)
1313  {
1314  uword s;
1315 
1316  n = mheap_next_elt (e);
1317 
1318  /* Object must be marked free. */
1319  CHECK (e->is_free);
1320 
1321  /* Next object's previous free bit must also be set. */
1322  CHECK (n->prev_is_free);
1323 
1324  if (is_first)
1325  CHECK (e->free_elt.prev_uoffset == ~0);
1326  is_first = 0;
1327 
1328  s = mheap_elt_data_bytes (e);
1330 
1331  free_count_from_free_lists += 1;
1332  free_size_from_free_lists += s;
1333 
1334  if (e->free_elt.next_uoffset == ~0)
1335  break;
1336 
1337  n = mheap_elt_at_uoffset (v, e->free_elt.next_uoffset);
1338 
1339  /* Check free element linkages. */
1340  CHECK (n->free_elt.prev_uoffset == mheap_elt_uoffset (v, e));
1341 
1342  e = n;
1343  }
1344  }
1345 
1346  /* Go through small object cache. */
1347  small_elt_free_count = small_elt_free_size = 0;
1348  for (i = 0; i < ARRAY_LEN (h->small_object_cache.bins.as_u8); i++)
1349  {
1350  if (h->small_object_cache.bins.as_u8[i] != 0)
1351  {
1352  mheap_elt_t * e;
1353  uword b = h->small_object_cache.bins.as_u8[i] - 1;
1355  uword s;
1356 
1357  e = mheap_elt_at_uoffset (v, o);
1358 
1359  /* Object must be allocated. */
1360  CHECK (! e->is_free);
1361 
1362  s = mheap_elt_data_bytes (e);
1364 
1365  small_elt_free_count += 1;
1366  small_elt_free_size += s;
1367  }
1368  }
1369 
1370  {
1371  mheap_elt_t * e, * n;
1372  uword elt_free_size, elt_free_count;
1373 
1374  elt_count = elt_size = elt_free_size = elt_free_count = 0;
1375  for (e = v;
1377  e = n)
1378  {
1380  CHECK (e->prev_n_user_data * sizeof (e->user_data[0]) >= MHEAP_MIN_USER_DATA_BYTES);
1381 
1382  CHECK (e->n_user_data * sizeof (e->user_data[0]) >= MHEAP_MIN_USER_DATA_BYTES);
1383 
1384  n = mheap_next_elt (e);
1385 
1386  CHECK (e->is_free == n->prev_is_free);
1387 
1388  elt_count++;
1389  s = mheap_elt_data_bytes (e);
1390  elt_size += s;
1391 
1392  if (e->is_free)
1393  {
1394  elt_free_count++;
1395  elt_free_size += s;
1396  }
1397 
1398  /* Consecutive free objects should have been combined. */
1399  CHECK (! (e->prev_is_free && n->prev_is_free));
1400  }
1401 
1402  CHECK (free_count_from_free_lists == elt_free_count);
1403  CHECK (free_size_from_free_lists == elt_free_size);
1404  CHECK (elt_count == h->n_elts + elt_free_count + small_elt_free_count);
1405  CHECK (elt_size + (elt_count + 1) * MHEAP_ELT_OVERHEAD_BYTES == vec_len (v));
1406  }
1407 
1408  {
1409  mheap_elt_t * e, * n;
1410 
1411  for (e = v;
1413  e = n)
1414  {
1415  n = mheap_next_elt (e);
1416  CHECK (e->n_user_data == n->prev_n_user_data);
1417  }
1418  }
1419 
1420 #undef CHECK
1421 
1422  mheap_maybe_unlock (v);
1423 
1424  h->validate_serial += 1;
1425 }
1426 
1427 static void mheap_get_trace (void * v, uword offset, uword size)
1428 {
1429  mheap_t * h;
1430  mheap_trace_main_t * tm;
1431  mheap_trace_t * t;
1432  uword i, n_callers, trace_index, * p;
1434 
1435  /* Spurious Coverity warnings be gone. */
1436  memset(&trace, 0, sizeof(trace));
1437 
1438  n_callers = clib_backtrace (trace.callers, ARRAY_LEN (trace.callers),
1439  /* Skip mheap_get_aligned's frame */ 1);
1440  if (n_callers == 0)
1441  return;
1442 
1443  for (i = n_callers; i < ARRAY_LEN (trace.callers); i++)
1444  trace.callers[i] = 0;
1445 
1446  h = mheap_header (v);
1447  tm = &h->trace_main;
1448 
1449  if (! tm->trace_by_callers)
1450  tm->trace_by_callers = hash_create_mem (0, sizeof (trace.callers), sizeof (uword));
1451 
1452  p = hash_get_mem (tm->trace_by_callers, &trace.callers);
1453  if (p)
1454  {
1455  trace_index = p[0];
1456  t = tm->traces + trace_index;
1457  }
1458  else
1459  {
1460  i = vec_len (tm->trace_free_list);
1461  if (i > 0)
1462  {
1463  trace_index = tm->trace_free_list[i - 1];
1464  _vec_len (tm->trace_free_list) = i - 1;
1465  }
1466  else
1467  {
1468  mheap_trace_t * old_start = tm->traces;
1469  mheap_trace_t * old_end = vec_end (tm->traces);
1470 
1471  vec_add2 (tm->traces, t, 1);
1472 
1473  if (tm->traces != old_start) {
1474  hash_pair_t * p;
1475  mheap_trace_t * q;
1477  q = uword_to_pointer (p->key, mheap_trace_t *);
1478  ASSERT (q >= old_start && q < old_end);
1479  p->key = pointer_to_uword (tm->traces + (q - old_start));
1480  }));
1481  }
1482  trace_index = t - tm->traces;
1483  }
1484 
1485  t = tm->traces + trace_index;
1486  t[0] = trace;
1487  t->n_allocations = 0;
1488  t->n_bytes = 0;
1489  hash_set_mem (tm->trace_by_callers, t->callers, trace_index);
1490  }
1491 
1492  t->n_allocations += 1;
1493  t->n_bytes += size;
1494  t->offset = offset; /* keep a sample to autopsy */
1495  hash_set (tm->trace_index_by_offset, offset, t - tm->traces);
1496 }
1497 
1498 static void mheap_put_trace (void * v, uword offset, uword size)
1499 {
1500  mheap_t * h;
1501  mheap_trace_main_t * tm;
1502  mheap_trace_t * t;
1503  uword trace_index, * p;
1504 
1505  h = mheap_header (v);
1506  tm = &h->trace_main;
1507  p = hash_get (tm->trace_index_by_offset, offset);
1508  if (! p)
1509  return;
1510 
1511  trace_index = p[0];
1512  hash_unset (tm->trace_index_by_offset, offset);
1513  ASSERT (trace_index < vec_len (tm->traces));
1514 
1515  t = tm->traces + trace_index;
1516  ASSERT (t->n_allocations > 0);
1517  ASSERT (t->n_bytes >= size);
1518  t->n_allocations -= 1;
1519  t->n_bytes -= size;
1520  if (t->n_allocations == 0)
1521  {
1523  vec_add1 (tm->trace_free_list, trace_index);
1524  memset (t, 0, sizeof (t[0]));
1525  }
1526 }
1527 
1528 static int mheap_trace_sort (const void * _t1, const void * _t2)
1529 {
1530  const mheap_trace_t * t1 = _t1;
1531  const mheap_trace_t * t2 = _t2;
1532  word cmp;
1533 
1534  cmp = (word) t2->n_bytes - (word) t1->n_bytes;
1535  if (! cmp)
1536  cmp = (word) t2->n_allocations - (word) t1->n_allocations;
1537  return cmp;
1538 }
1539 
1540 always_inline void
1542 {
1543  vec_free (tm->traces);
1544  vec_free (tm->trace_free_list);
1547 }
1548 
1549 void mheap_trace (void * v, int enable)
1550 {
1551  mheap_t * h;
1552 
1553  h = mheap_header (v);
1554 
1555  if (enable)
1556  {
1557  h->flags |= MHEAP_FLAG_TRACE;
1558  }
1559  else
1560  {
1562  h->flags &= ~MHEAP_FLAG_TRACE;
1563  }
1564 }
#define MHEAP_LOG2_N_SMALL_OBJECT_BINS
static_always_inline uword mheap_page_truncate(uword addr)
Definition: mheap.c:234
struct mheap_stats_t::@19 free_list
uword bytes_overhead
Definition: mem.h:213
always_inline void * clib_mem_vm_map(void *addr, uword size)
struct mheap_elt_t::@16::@18 free_elt
always_inline uword max_pow2(uword x)
Definition: clib.h:245
always_inline uword round_pow2(uword x, uword pow2)
Definition: clib.h:255
uword bytes_total
Definition: mem.h:209
#define hash_set(h, key, value)
Definition: hash.h:237
uword bytes_free
Definition: mem.h:209
sll srl srl sll sra u16x4 i
Definition: vector_sse2.h:267
always_inline uword mheap_elts(void *v)
always_inline uword mheap_elt_uoffset(void *v, mheap_elt_t *e)
always_inline void * mheap_elt_data(void *v, mheap_elt_t *e)
always_inline mheap_elt_t * mheap_prev_elt(mheap_elt_t *e)
always_inline void mheap_elt_set_size(void *v, uword uoffset, uword n_user_data_bytes, uword is_free)
Definition: mheap.c:126
always_inline void mheap_maybe_unlock(void *v)
Definition: mheap.c:73
#define MHEAP_ELT_OVERHEAD_BYTES
#define hash_unset(h, key)
Definition: hash.h:243
static_always_inline uword mheap_vm(void *v, uword flags, clib_address_t start_addr, uword size)
Definition: mheap.c:238
vlib_cli_command_t trace
(constructor) VLIB_CLI_COMMAND (trace)
Definition: memory_vlib.c:1046
static u8 * format_mheap_byte_count(u8 *s, va_list *va)
Definition: mheap.c:1033
always_inline uword mheap_max_size(void *v)
uword offsets[BITS(uword)]
uword vm_alloc_offset_from_header
uword callers[12]
always_inline void set_first_free_elt_offset(mheap_t *h, uword bin, uword uoffset)
Definition: mheap.c:145
uword bytes_free_reclaimed
Definition: mem.h:216
void * mheap_alloc(void *memory, uword size)
Definition: mheap.c:908
uword clib_backtrace(uword *callers, uword max_callers, uword n_frames_to_skip)
Definition: backtrace.c:235
u64 clib_address_t
Definition: types.h:121
void os_panic(void)
Definition: unix-misc.c:165
#define MHEAP_VM_ROUND
Definition: mheap.c:225
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
Definition: vec.h:480
always_inline void * clib_mem_vm_alloc(uword size)
u64 n_small_object_cache_hits
#define vec_add2(V, P, N)
Add N elements to end of vector V, return pointer to new elements in P.
Definition: vec.h:519
u64 n_small_object_cache_attempts
always_inline uword max_log2(uword x)
Definition: clib.h:216
static void usage(void)
Definition: health_check.c:14
#define hash_set_mem(h, key, value)
Definition: hash.h:257
#define STRUCT_OFFSET_OF(t, f)
Definition: clib.h:62
#define MHEAP_N_SMALL_OBJECT_BINS
always_inline void mheap_trace_main_free(mheap_trace_main_t *tm)
Definition: mheap.c:1541
static void mheap_put_trace(void *v, uword offset, uword size)
Definition: mheap.c:1498
#define MHEAP_FLAG_THREAD_SAFE
#define vec_bytes(v)
Number of data bytes in vector.
uword bytes_used
Definition: mem.h:209
u8 * format_mheap(u8 *s, va_list *va)
Definition: mheap.c:1113
#define foreach_set_bit(var, mask, body)
Definition: bitops.h:146
always_inline u8x16 u8x16_splat(u8 a)
Definition: vector_sse2.h:133
vhost_user_memory_t memory
Definition: vhost-user.h:79
uword object_count
Definition: mem.h:205
mheap_trace_main_t trace_main
always_inline uword mheap_elt_size_to_user_n_words(uword n_bytes)
Definition: mheap.c:119
#define static_always_inline
Definition: clib.h:85
#define always_inline
Definition: clib.h:84
#define MHEAP_FLAG_DISABLE_VM
u8 * format_white_space(u8 *s, va_list *va)
Definition: std-formats.c:107
u8 * format_hex_bytes(u8 *s, va_list *va)
Definition: std-formats.c:79
void mheap_usage(void *v, clib_mem_usage_t *usage)
Definition: mheap.c:1026
unsigned long u64
Definition: types.h:89
always_inline void remove_free_elt(void *v, mheap_elt_t *e, uword bin)
Definition: mheap.c:194
#define vec_end(v)
End (last data address) of vector.
volatile u32 lock
always_inline mheap_t * mheap_header(u8 *v)
static uword pointer_to_uword(const void *p)
Definition: types.h:131
uword non_empty_free_elt_heads[(MHEAP_N_BINS+BITS(uword)-1)/BITS(uword)]
mheap_stats_t stats
#define hash_create_mem(elts, key_bytes, value_bytes)
Definition: hash.h:594
#define hash_get(h, key)
Definition: hash.h:231
#define hash_unset_mem(h, key)
Definition: hash.h:263
uword os_get_cpu_number(void)
Definition: unix-misc.c:206
#define hash_free(h)
Definition: hash.h:269
mheap_trace_t * traces
#define vec_dup(V)
Return copy of vector (no header, no alignment)
Definition: vec.h:332
always_inline uword mheap_put_small_object(mheap_t *h, uword bin, uword offset)
Definition: mheap.c:327
static uword mheap_page_size
Definition: mheap.c:229
static_always_inline uword mheap_vm_elt(void *v, uword flags, uword offset)
Definition: mheap.c:273
always_inline void * clib_mem_set_heap(void *heap)
Definition: mem.h:190
u64 validate_serial
always_inline void * clib_mem_get_heap(void)
Definition: mem.h:187
#define MHEAP_N_USER_DATA_INVALID
void dmh(void *v)
Definition: mheap.c:1275
#define uword_to_pointer(u, type)
Definition: types.h:134
always_inline uword mheap_elt_data_bytes(mheap_elt_t *e)
#define MHEAP_VM_MAP
Definition: mheap.c:222
static void mheap_validate_breakpoint()
Definition: mheap.c:1278
#define MHEAP_VM_NOMAP
Definition: mheap.c:224
void * mheap_get_aligned(void *v, uword n_user_data_bytes, uword align, uword align_offset, uword *offset_return)
Definition: mheap.c:621
uword bytes_max
Definition: mem.h:224
static void free_last_elt(void *v, mheap_elt_t *e)
Definition: mheap.c:701
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:298
always_inline void remove_free_elt2(void *v, mheap_elt_t *e)
Definition: mheap.c:215
static never_inline void * mheap_get_extend_vector(void *v, uword n_user_data_bytes, uword align, uword align_offset, uword *offset_return)
Definition: mheap.c:547
mheap_small_object_cache_t small_object_cache
always_inline mheap_elt_t * mheap_next_elt(mheap_elt_t *e)
#define ARRAY_LEN(x)
Definition: clib.h:59
#define CHECK(x)
void * mheap_alloc_with_flags(void *memory, uword memory_size, uword flags)
Definition: mheap.c:842
static uword mheap_get_search_free_list(void *v, uword *n_user_bytes_arg, uword align, uword align_offset)
Definition: mheap.c:501
#define never_inline
Definition: clib.h:81
void mheap_trace(void *v, int enable)
Definition: mheap.c:1549
#define ASSERT(truth)
always_inline uword mheap_small_object_cache_mask(mheap_small_object_cache_t *c, uword bin)
Definition: mheap.c:285
unsigned int u32
Definition: types.h:88
always_inline mheap_elt_t * mheap_elt_at_uoffset(void *v, uword uo)
volatile u32 owner_cpu
u8 * format(u8 *s, char *fmt,...)
Definition: format.c:405
union mheap_small_object_cache_t::@20 bins
uword vm_alloc_size
u32 size
Definition: vhost-user.h:74
always_inline uword mheap_bytes_overhead(void *v)
Definition: mheap.c:981
#define MHEAP_FLAG_VALIDATE
always_inline u8 * mheap_vector(mheap_t *h)
always_inline u32 * elt_data(void *v, heap_elt_t *e)
Definition: heap.c:199
#define clib_max(x, y)
Definition: clib.h:288
static_always_inline uword mheap_page_round(uword addr)
Definition: mheap.c:231
always_inline uword format_get_indent(u8 *s)
Definition: format.h:72
always_inline void clib_mem_vm_free(void *addr, uword size)
u64 uword
Definition: types.h:112
#define MHEAP_FLAG_TRACE
static uword mheap_get_search_free_bin(void *v, uword bin, uword *n_user_data_bytes_arg, uword align, uword align_offset)
Definition: mheap.c:358
static mheap_elt_t * mheap_first_corrupt(void *v)
Definition: mheap.c:1043
#define MHEAP_FLAG_SMALL_OBJECT_CACHE
uword mheap_bytes(void *v)
Definition: mheap.c:988
#define MHEAP_HAVE_SMALL_OBJECT_CACHE
always_inline uword mheap_elt_size_to_user_n_bytes(uword n_bytes)
Definition: mheap.c:112
i64 word
Definition: types.h:111
void qsort(void *base, uword n, uword size, int(*compar)(const void *, const void *))
Definition: qsort.c:55
void mheap_put(void *v, uword uoffset)
Definition: mheap.c:728
static int mheap_trace_sort(const void *t1, const void *t2)
Definition: mheap.c:1528
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
double f64
Definition: types.h:140
unsigned char u8
Definition: types.h:56
#define hash_foreach_pair(p, v, body)
Definition: hash.h:311
u32 user_data[0]
#define MHEAP_VM_ROUND_UP
Definition: mheap.c:226
static void mheap_get_trace(void *v, uword offset, uword size)
Definition: mheap.c:1427
static u8 * format_mheap_stats(u8 *s, va_list *va)
Definition: mheap.c:1070
word fformat(FILE *f, char *fmt,...)
Definition: format.c:437
format_function_t format_clib_elf_symbol_with_address
Definition: elf_clib.h:130
#define hash_get_mem(h, key)
Definition: hash.h:251
always_inline void new_free_elt(void *v, uword uoffset, uword n_user_data_bytes)
Definition: mheap.c:187
#define STRUCT_SIZE_OF(t, f)
Definition: clib.h:64
void mheap_validate(void *v)
Definition: mheap.c:1281
#define vec_foreach(var, vec)
Vector iterator.
void mheap_foreach(void *v, uword(*func)(void *arg, void *v, void *elt_data, uword elt_size), void *arg)
Definition: mheap.c:933
int recursion_count
always_inline uword min_log2(uword x)
Definition: clib.h:181
always_inline uword user_data_size_to_bin_index(uword n_user_data_bytes)
Definition: mheap.c:90
#define CLIB_MEMORY_BARRIER()
Definition: clib.h:101
#define MHEAP_USER_DATA_WORD_BYTES
always_inline void set_free_elt(void *v, uword uoffset, uword n_user_data_bytes)
Definition: mheap.c:162
vhost_vring_addr_t addr
Definition: vhost-user.h:78
always_inline uword pow2_mask(uword x)
Definition: clib.h:242
#define MHEAP_VM_UNMAP
Definition: mheap.c:223
always_inline uword mheap_get_small_object(mheap_t *h, uword bin)
Definition: mheap.c:308
u32 flags
Definition: vhost-user.h:73
always_inline u64 clib_cpu_time_now(void)
Definition: time.h:71
always_inline void * clib_mem_vm_unmap(void *addr, uword size)
always_inline void mheap_maybe_lock(void *v)
Definition: mheap.c:53
uword clib_mem_get_page_size(void)
Definition: mem_mheap.c:111
#define BITS(x)
Definition: clib.h:58
#define MHEAP_N_BINS
static void mheap_usage_no_lock(void *v, clib_mem_usage_t *usage)
Definition: mheap.c:991
#define MHEAP_MIN_USER_DATA_BYTES
u32 first_free_elt_uoffset_by_bin[MHEAP_N_BINS]