FD.io VPP  v16.09
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 
53 always_inline void
55 {
56  mheap_t *h = mheap_header (v);
57  if (v && (h->flags & MHEAP_FLAG_THREAD_SAFE))
58  {
59  u32 my_cpu = os_get_cpu_number ();
60  if (h->owner_cpu == my_cpu)
61  {
62  h->recursion_count++;
63  return;
64  }
65 
66  while (__sync_lock_test_and_set (&h->lock, 1))
67  ;
68 
69  h->owner_cpu = my_cpu;
70  h->recursion_count = 1;
71  }
72 }
73 
74 always_inline void
76 {
77  mheap_t *h = mheap_header (v);
78  if (v && h->flags & MHEAP_FLAG_THREAD_SAFE)
79  {
81  if (--h->recursion_count == 0)
82  {
83  h->owner_cpu = ~0;
85  h->lock = 0;
86  }
87  }
88 }
89 
90 /* Find bin for objects with size at least 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. */
101  n_user_data_words =
102  (round_pow2 (n_user_data_bytes, MHEAP_USER_DATA_WORD_BYTES) /
104 
105  ASSERT (n_user_data_words > 0);
106  small_bin =
107  n_user_data_words -
109  ASSERT (small_bin >= 0);
110 
111  large_bin =
112  MHEAP_N_SMALL_OBJECT_BINS + max_log2 (n_user_data_bytes) -
114 
115  return small_bin < MHEAP_N_SMALL_OBJECT_BINS ? small_bin : large_bin;
116 }
117 
120 {
121  ASSERT (n_bytes >= sizeof (mheap_elt_t));
122  return (n_bytes - STRUCT_OFFSET_OF (mheap_elt_t, user_data));
123 }
124 
125 always_inline uword __attribute__ ((unused))
127 {
128  ASSERT (n_bytes % MHEAP_USER_DATA_WORD_BYTES == 0);
129  return mheap_elt_size_to_user_n_bytes (n_bytes) /
131 }
132 
133 always_inline void
135  uword uoffset, uword n_user_data_bytes, uword is_free)
136 {
137  mheap_elt_t *e, *n;
138 
139  e = mheap_elt_at_uoffset (v, uoffset);
140 
141  ASSERT (n_user_data_bytes % MHEAP_USER_DATA_WORD_BYTES == 0);
142 
143  e->n_user_data = n_user_data_bytes / MHEAP_USER_DATA_WORD_BYTES;
144  e->is_free = is_free;
145  ASSERT (e->prev_n_user_data * sizeof (e->user_data[0]) >=
147 
148  n = mheap_next_elt (e);
150  n->prev_is_free = is_free;
151 }
152 
153 always_inline void
155 {
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 
165  h->non_empty_free_elt_heads[i0] &= ~i1;
166  else
167  h->non_empty_free_elt_heads[i0] |= i1;
168 }
169 
170 always_inline void
171 set_free_elt (void *v, uword uoffset, uword n_user_data_bytes)
172 {
173  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);
176  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 
181  e->free_elt.prev_uoffset = MHEAP_GROUNDED;
182  e->free_elt.next_uoffset = h->first_free_elt_uoffset_by_bin[bin];
183 
184  /* Fill in next free elt's previous pointer. */
185  if (e->free_elt.next_uoffset != MHEAP_GROUNDED)
186  {
187  mheap_elt_t *nf = mheap_elt_at_uoffset (v, e->free_elt.next_uoffset);
188  ASSERT (nf->is_free);
189  nf->free_elt.prev_uoffset = uoffset;
190  }
191 
192  set_first_free_elt_offset (h, bin, uoffset);
193 }
194 
195 always_inline void
196 new_free_elt (void *v, uword uoffset, uword n_user_data_bytes)
197 {
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 
202 always_inline void
203 remove_free_elt (void *v, mheap_elt_t * e, uword bin)
204 {
205  mheap_t *h = mheap_header (v);
206  mheap_elt_t *p, *n;
207 #if CLIB_VEC64 > 0
208  u64 no, po;
209 #else
210  u32 no, po;
211 #endif
212 
213  no = e->free_elt.next_uoffset;
214 
215  n = no != MHEAP_GROUNDED ? mheap_elt_at_uoffset (v, no) : 0;
216  po = e->free_elt.prev_uoffset;
217  p = po != MHEAP_GROUNDED ? mheap_elt_at_uoffset (v, po) : 0;
218 
219  if (!p)
220  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 
228 always_inline void
230 {
231  uword bin;
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 
244 
247 {
248  return (addr + mheap_page_size - 1) & ~(mheap_page_size - 1);
249 }
250 
253 {
254  return addr & ~(mheap_page_size - 1);
255 }
256 
258 mheap_vm (void *v, uword flags, clib_address_t start_addr, uword size)
259 {
260  mheap_t *h = mheap_header (v);
261  clib_address_t start_page, end_page, end_addr;
262  uword mapped_bytes;
263 
265 
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 
291 {
292  mheap_elt_t *e;
293  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 
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))
315  mask = _(0) | _(1);
316  if (BITS (uword) > 32)
317  mask |= _(2) | _(3);
318 #undef _
319 
320 #endif
321  return mask;
322 }
323 
326 {
328  uword mask = mheap_small_object_cache_mask (c, bin + 1);
330 
331  if (mask)
332  {
333  uword i = min_log2 (mask);
334  uword o = c->offsets[i];
335  ASSERT (o != MHEAP_GROUNDED);
336  c->bins.as_u8[i] = 0;
337  offset = o;
338  }
339 
340  return offset;
341 }
342 
345 {
347  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 
374 static uword
376  uword bin,
377  uword * n_user_data_bytes_arg,
378  uword align, uword align_offset)
379 {
380  mheap_t *h = mheap_header (v);
381  mheap_elt_t *e;
382 
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 
390 
391  search_n_user_data_bytes = *n_user_data_bytes_arg;
392 
393  /* Silence compiler warning. */
394  o0 = o1 = f0 = f1 = 0;
395 
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 
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. */
417  o0 = ((f1 - search_n_user_data_bytes) & ~(align - 1)) - align_offset;
418  while (o0 < f0)
419  o0 += align;
420 
421  /* Make sure that first free fragment is either empty or
422  large enough to be valid. */
423  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. */
439  if (e->free_elt.next_uoffset == MHEAP_GROUNDED)
440  return MHEAP_GROUNDED;
441 
442  /* Otherwise keep searching for large enough object. */
443  e = mheap_elt_at_uoffset (v, e->free_elt.next_uoffset);
444  }
445 
446 found:
447  /* 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. */
460  if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
461  {
462  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);
466 
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));
472  f0_page_end = mheap_page_truncate (pointer_to_uword (f1_elt));
473 
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  {
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 
511 
512  return o0;
513 }
514 
515 /* Search free lists for object with given size and alignment. */
516 static uword
518  uword * n_user_bytes_arg,
519  uword align, uword align_offset)
520 {
521  mheap_t *h = mheap_header (v);
522  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 
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);
535  if (r != MHEAP_GROUNDED)
536  {
538  return r;
539  }
540  }
541 
542  for (i = bin / BITS (uword); i < ARRAY_LEN (h->non_empty_free_elt_heads);
543  i++)
544  {
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. */
552  foreach_set_bit (bi, non_empty_bin_mask, (
553  {
554  uword r =
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  ));
569  }
570 
571  return MHEAP_GROUNDED;
572 }
573 
574 static never_inline void *
576  uword n_user_data_bytes,
577  uword align,
578  uword align_offset, uword * offset_return)
579 {
580  /* Bounds of free and allocated objects (as above). */
581  uword f0, f1, o0, o1;
582  word free_size;
583  mheap_t *h = mheap_header (v);
584  mheap_elt_t *e;
585 
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));
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;
609 
610  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  {
616  *offset_return = MHEAP_GROUNDED;
617  return v;
618  }
619 
620  _vec_len (v) = f1;
621 
622  if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
623  {
624  mheap_elt_t *f0_elt = mheap_elt_at_uoffset (v, f0);
625  mheap_elt_t *f1_elt = mheap_elt_at_uoffset (v, f1);
626 
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);
642 
643  *offset_return = o0;
644 
645  return v;
646 }
647 
648 void *
650  uword n_user_data_bytes,
651  uword align, uword align_offset, uword * offset_return)
652 {
653  mheap_t *h;
654  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  {
668  *offset_return = MHEAP_GROUNDED;
669  return v;
670  }
671 
672  /* Round requested size. */
673  n_user_data_bytes = clib_max (n_user_data_bytes, MHEAP_MIN_USER_DATA_BYTES);
674  n_user_data_bytes =
675  round_pow2 (n_user_data_bytes,
676  STRUCT_SIZE_OF (mheap_elt_t, user_data[0]));
677 
678  if (!v)
679  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. */
689  offset =
690  mheap_get_search_free_list (v, &n_user_data_bytes, align, align_offset);
691 
692  h = mheap_header (v);
693 
694  /* If that fails allocate object at end of heap by extending vector. */
695  if (offset == MHEAP_GROUNDED && _vec_len (v) < h->max_size)
696  {
697  v =
698  mheap_get_extend_vector (v, n_user_data_bytes, align, align_offset,
699  &offset);
700  h = mheap_header (v);
701  h->stats.n_vector_expands += offset != MHEAP_GROUNDED;
702  }
703 
704  *offset_return = offset;
705  if (offset != MHEAP_GROUNDED)
706  {
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 
732 static void
734 {
735  mheap_t *h = mheap_header (v);
736 
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 
745  {
746  if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
748  _vec_len (v) = 0;
749  }
750  else
751  {
752  uword uo = mheap_elt_uoffset (v, e);
753  if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
754  mheap_vm_elt (v, MHEAP_VM_UNMAP, uo);
756  _vec_len (v) = uo;
757  }
758 }
759 
760 void
761 mheap_put (void *v, uword uoffset)
762 {
763  mheap_t *h;
764  uword n_user_data_bytes, bin;
765  mheap_elt_t *e, *n;
766  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);
791  && bin < 255 && (h->flags & MHEAP_FLAG_SMALL_OBJECT_CACHE))
792  {
793  uoffset = mheap_put_small_object (h, bin, uoffset);
794  if (uoffset == 0)
795  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. */
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  {
828  mheap_elt_t *p = mheap_prev_elt (e);
829  f0 = mheap_elt_uoffset (v, p);
830  remove_free_elt2 (v, p);
831  n_combine++;
832  }
833 
834  if (n->is_free)
835  {
836  mheap_elt_t *m = mheap_next_elt (n);
837  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 
848  if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
849  mheap_vm_elt (v, MHEAP_VM_UNMAP, f0);
850  }
851 
852 done:
853  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 
874 void *
876 {
877  mheap_t *h;
878  void *v;
879  uword size;
880 
881  if (!mheap_page_size)
882  mheap_page_size = clib_mem_get_page_size ();
883 
884  if (!memory)
885  {
886  /* No memory given, try to VM allocate some. */
887  memory = clib_mem_vm_alloc (memory_size);
888  if (!memory)
889  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 
910  if (PREDICT_FALSE (memory + memory_size < v))
911  {
912  /*
913  * This will happen when the requested memory_size is too
914  * small to cope with the heap header and/or memory alignment.
915  */
916  clib_mem_vm_free (memory, memory_size);
917  return 0;
918  }
919 
920  size = memory + memory_size - v;
921  }
922 
923  /* VM map header so we can use memory. */
924  if (!(flags & MHEAP_FLAG_DISABLE_VM))
925  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. */
938  h->flags |= (flags & ~MHEAP_FLAG_TRACE);
939 
940  /* Unmap remainder of heap until we will be ready to use it. */
941  if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
943  (clib_address_t) v, h->max_size);
944 
945  /* Initialize free list heads to empty. */
946  memset (h->first_free_elt_uoffset_by_bin, 0xFF,
947  sizeof (h->first_free_elt_uoffset_by_bin));
948 
949  return v;
950 }
951 
952 void *
954 {
955  uword flags = 0;
956 
957  if (memory != 0)
958  flags |= MHEAP_FLAG_DISABLE_VM;
959 
960 #ifdef CLIB_HAVE_VEC128
962 #endif
963 
964  return mheap_alloc_with_flags (memory, size, flags);
965 }
966 
967 void *
968 _mheap_free (void *v)
969 {
970  mheap_t *h = mheap_header (v);
971 
972  if (v)
974  h->vm_alloc_size);
975 
976  return 0;
977 }
978 
979 /* Call user's function with each object in heap. */
980 void
981 mheap_foreach (void *v,
982  uword (*func) (void *arg, void *v, void *elt_data,
983  uword elt_size), void *arg)
984 {
985  mheap_elt_t *e;
986  u8 *stack_heap, *clib_mem_mheap_save;
987  u8 tmp_heap_memory[16 * 1024];
988 
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;
1010  {
1011  void *p = mheap_elt_data (v, e);
1012  if (e->is_free)
1013  continue;
1014  if ((*func) (arg, v, p, mheap_elt_data_bytes (e)))
1015  break;
1016  }
1017 
1018  /* Restore main CLIB heap. */
1019  if (clib_mem_mheap_save)
1020  clib_mem_set_heap (clib_mem_mheap_save);
1021 
1022 done:
1023  mheap_maybe_unlock (v);
1024 }
1025 
1026 /* Bytes in mheap header overhead not including data bytes. */
1029 {
1030  mheap_t *h = mheap_header (v);
1031  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. */
1035 uword
1036 mheap_bytes (void *v)
1037 {
1038  return mheap_bytes_overhead (v) + vec_bytes (v);
1039 }
1040 
1041 static void
1043 {
1044  mheap_t *h = mheap_header (v);
1045  uword used = 0, free = 0, free_vm_unmapped = 0;
1046 
1047  if (vec_len (v) > 0)
1048  {
1049  mheap_elt_t *e;
1050 
1051  for (e = v;
1053  e = mheap_next_elt (e))
1054  {
1056  if (e->is_free)
1057  {
1058  free += size;
1059  if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
1060  free_vm_unmapped +=
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 
1077 void
1079 {
1080  mheap_maybe_lock (v);
1081  mheap_usage_no_lock (v, usage);
1082  mheap_maybe_unlock (v);
1083 }
1084 
1085 static u8 *
1086 format_mheap_byte_count (u8 * s, va_list * va)
1087 {
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. */
1096 static mheap_elt_t *
1098 {
1099  mheap_elt_t *e, *n;
1100 
1101  if (vec_len (v) == 0)
1102  return 0;
1103 
1104  e = v;
1105  while (1)
1106  {
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 
1124 static u8 *
1125 format_mheap_stats (u8 * s, va_list * va)
1126 {
1127  mheap_t *h = va_arg (*va, mheap_t *);
1128  mheap_stats_t *st = &h->stats;
1129  uword indent = format_get_indent (s);
1130 
1131  s =
1132  format (s,
1133  "alloc. from small object cache: %Ld hits %Ld attempts (%.2f%%) replacements %d",
1136  0 ? 100. * (f64) st->n_small_object_cache_hits /
1137  (f64) st->n_small_object_cache_attempts : 0.),
1139 
1140  s =
1141  format (s,
1142  "\n%Ualloc. from free-list: %Ld attempts, %Ld hits (%.2f%%), %Ld considered (per-attempt %.2f)",
1146  0 ? 100. * (f64) st->free_list.n_objects_found /
1147  (f64) st->free_list.n_search_attempts : 0.),
1150  0 ? (f64) st->free_list.n_objects_searched /
1151  (f64) st->free_list.n_search_attempts : 0.));
1152 
1153  s = format (s, "\n%Ualloc. from vector-expand: %Ld",
1154  format_white_space, indent, st->n_vector_expands);
1155 
1156  s = format (s, "\n%Uallocs: %Ld %.2f clocks/call",
1157  format_white_space, indent,
1158  st->n_gets, (f64) st->n_clocks_get / (f64) st->n_gets);
1159 
1160  s = format (s, "\n%Ufrees: %Ld %.2f clocks/call",
1161  format_white_space, indent,
1162  st->n_puts, (f64) st->n_clocks_put / (f64) st->n_puts);
1163 
1164  return s;
1165 }
1166 
1167 u8 *
1168 format_mheap (u8 * s, va_list * va)
1169 {
1170  void *v = va_arg (*va, u8 *);
1171  int verbose = va_arg (*va, int);
1172 
1173  mheap_t *h;
1174  uword i, size, indent;
1176  mheap_elt_t *first_corrupt;
1177 
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 
1186  s =
1187  format (s,
1188  "%d objects, %U of %U used, %U free, %U reclaimed, %U overhead",
1194 
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];
1202  mheap_elt_t *e;
1203  uword i, n_hist;
1204 
1205  memset (hist, 0, sizeof (hist));
1206 
1207  n_hist = 0;
1208  for (e = v;
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);
1214  if (!e->is_free)
1215  {
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,
1232  i * MHEAP_USER_DATA_WORD_BYTES, hist[i],
1233  (f64) hist[i] / (f64) n_hist);
1234  }
1235  }
1236 
1237  if (verbose)
1238  s = format (s, "\n%U%U",
1239  format_white_space, indent + 2, format_mheap_stats, h);
1240 
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. */
1244  mheap_trace_t *t, *traces_copy;
1245  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]),
1250 
1251  total_objects_traced = 0;
1252  s = format (s, "\n");
1253  vec_foreach (t, traces_copy)
1254  {
1255  /* 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. */
1262  if (!verbose && t->n_bytes < 1024)
1263  continue;
1264 
1265  if (t == traces_copy)
1266  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);
1270  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
1276  s =
1278  t->callers[i]);
1279 #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);
1288  }
1289 
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",
1295  first_corrupt, size, format_hex_bytes, first_corrupt, size);
1296  }
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  {
1302  mheap_elt_t *e;
1303  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 
1331 void
1332 dmh (void *v)
1333 {
1334  fformat (stderr, "%U", format_mheap, v, 1);
1335 }
1336 
1337 static void
1339 {
1340  os_panic ();
1341 }
1342 
1343 void
1345 {
1346  mheap_t *h = mheap_header (v);
1347  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  {
1364  mheap_elt_t *e, *n;
1365  uword is_first;
1366 
1368  ==
1369  ((h->non_empty_free_elt_heads[i /
1370  BITS (uword)] & ((uword) 1 <<
1371  (uword) (i %
1372  BITS
1373  (uword))))
1374  != 0));
1375 
1377  continue;
1378 
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)
1394  CHECK (e->free_elt.prev_uoffset == MHEAP_GROUNDED);
1395  is_first = 0;
1396 
1397  s = mheap_elt_data_bytes (e);
1399 
1400  free_count_from_free_lists += 1;
1401  free_size_from_free_lists += s;
1402 
1403  if (e->free_elt.next_uoffset == MHEAP_GROUNDED)
1404  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  {
1421  mheap_elt_t *e;
1422  uword b = h->small_object_cache.bins.as_u8[i] - 1;
1424  uword s;
1425 
1426  e = mheap_elt_at_uoffset (v, o);
1427 
1428  /* Object must be allocated. */
1429  CHECK (!e->is_free);
1430 
1431  s = mheap_elt_data_bytes (e);
1433 
1434  small_elt_free_count += 1;
1435  small_elt_free_size += s;
1436  }
1437  }
1438 
1439  {
1440  mheap_elt_t *e, *n;
1441  uword elt_free_size, elt_free_count;
1442 
1443  elt_count = elt_size = elt_free_size = elt_free_count = 0;
1444  for (e = v; e->n_user_data != MHEAP_N_USER_DATA_INVALID; e = n)
1445  {
1447  CHECK (e->prev_n_user_data * sizeof (e->user_data[0]) >=
1449 
1450  CHECK (e->n_user_data * sizeof (e->user_data[0]) >=
1452 
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. */
1468  CHECK (!(e->prev_is_free && n->prev_is_free));
1469  }
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);
1474  CHECK (elt_size + (elt_count + 1) * MHEAP_ELT_OVERHEAD_BYTES ==
1475  vec_len (v));
1476  }
1477 
1478  {
1479  mheap_elt_t *e, *n;
1480 
1481  for (e = v; e->n_user_data == MHEAP_N_USER_DATA_INVALID; e = n)
1482  {
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 
1495 static void
1497 {
1498  mheap_t *h;
1499  mheap_trace_main_t *tm;
1500  mheap_trace_t *t;
1501  uword i, n_callers, trace_index, *p;
1503 
1504  /* Spurious Coverity warnings be gone. */
1505  memset (&trace, 0, sizeof (trace));
1506 
1507  n_callers = clib_backtrace (trace.callers, ARRAY_LEN (trace.callers),
1508  /* Skip mheap_get_aligned's frame */ 1);
1509  if (n_callers == 0)
1510  return;
1511 
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 
1518  if (!tm->trace_by_callers)
1519  tm->trace_by_callers =
1520  hash_create_mem (0, sizeof (trace.callers), sizeof (uword));
1521 
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  {
1538  mheap_trace_t *old_start = tm->traces;
1539  mheap_trace_t *old_end = vec_end (tm->traces);
1540 
1541  vec_add2 (tm->traces, t, 1);
1542 
1543  if (tm->traces != old_start)
1544  {
1545  hash_pair_t *p;
1546  mheap_trace_t *q;
1547  /* *INDENT-OFF* */
1549  ({
1550  q = uword_to_pointer (p->key, mheap_trace_t *);
1551  ASSERT (q >= old_start && q < old_end);
1552  p->key = pointer_to_uword (tm->traces + (q - old_start));
1553  }));
1554  /* *INDENT-ON* */
1555  }
1556  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;
1568  t->offset = offset; /* keep a sample to autopsy */
1569  hash_set (tm->trace_index_by_offset, offset, t - tm->traces);
1570 }
1571 
1572 static void
1574 {
1575  mheap_t *h;
1576  mheap_trace_main_t *tm;
1577  mheap_trace_t *t;
1578  uword trace_index, *p;
1579 
1580  h = mheap_header (v);
1581  tm = &h->trace_main;
1582  p = hash_get (tm->trace_index_by_offset, offset);
1583  if (!p)
1584  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  {
1598  vec_add1 (tm->trace_free_list, trace_index);
1599  memset (t, 0, sizeof (t[0]));
1600  }
1601 }
1602 
1603 static int
1604 mheap_trace_sort (const void *_t1, const void *_t2)
1605 {
1606  const mheap_trace_t *t1 = _t1;
1607  const mheap_trace_t *t2 = _t2;
1608  word cmp;
1609 
1610  cmp = (word) t2->n_bytes - (word) t1->n_bytes;
1611  if (!cmp)
1612  cmp = (word) t2->n_allocations - (word) t1->n_allocations;
1613  return cmp;
1614 }
1615 
1616 always_inline void
1618 {
1619  vec_free (tm->traces);
1620  vec_free (tm->trace_free_list);
1623 }
1624 
1625 void
1626 mheap_trace (void *v, int enable)
1627 {
1628  mheap_t *h;
1629 
1630  h = mheap_header (v);
1631 
1632  if (enable)
1633  {
1634  h->flags |= MHEAP_FLAG_TRACE;
1635  }
1636  else
1637  {
1639  h->flags &= ~MHEAP_FLAG_TRACE;
1640  }
1641 }
1642 
1643 /*
1644  * fd.io coding-style-patch-verification: ON
1645  *
1646  * Local Variables:
1647  * eval: (c-set-style "gnu")
1648  * End:
1649  */
#define MHEAP_LOG2_N_SMALL_OBJECT_BINS
static_always_inline uword mheap_page_truncate(uword addr)
Definition: mheap.c:252
uword bytes_overhead
Definition: mem.h:227
struct mheap_elt_t::@14::@16 free_elt
uword bytes_total
Definition: mem.h:223
#define hash_set(h, key, value)
Definition: hash.h:254
uword bytes_free
Definition: mem.h:223
sll srl srl sll sra u16x4 i
Definition: vector_sse2.h:343
static void remove_free_elt2(void *v, mheap_elt_t *e)
Definition: mheap.c:229
#define MHEAP_ELT_OVERHEAD_BYTES
#define hash_unset(h, key)
Definition: hash.h:260
union mheap_small_object_cache_t::@18 bins
static_always_inline uword mheap_vm(void *v, uword flags, clib_address_t start_addr, uword size)
Definition: mheap.c:258
static vlib_cli_command_t trace
(constructor) VLIB_CLI_COMMAND (trace)
Definition: memory_vlib.c:1168
static u8 * format_mheap_byte_count(u8 *s, va_list *va)
Definition: mheap.c:1086
uword offsets[BITS(uword)]
uword vm_alloc_offset_from_header
uword callers[12]
uword bytes_free_reclaimed
Definition: mem.h:230
static uword mheap_elt_size_to_user_n_words(uword n_bytes)
Definition: mheap.c:126
void * mheap_alloc(void *memory, uword size)
Definition: mheap.c:953
uword clib_backtrace(uword *callers, uword max_callers, uword n_frames_to_skip)
Definition: backtrace.c:232
u64 clib_address_t
Definition: types.h:121
void os_panic(void)
Definition: unix-misc.c:172
struct mheap_stats_t::@17 free_list
#define MHEAP_VM_ROUND
Definition: mheap.c:239
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
Definition: vec.h:482
static u64 clib_cpu_time_now(void)
Definition: time.h:73
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:521
u64 n_small_object_cache_attempts
static mheap_t * mheap_header(u8 *v)
static void usage(void)
Definition: health_check.c:14
#define hash_set_mem(h, key, value)
Definition: hash.h:274
#define STRUCT_OFFSET_OF(t, f)
Definition: clib.h:62
static void clib_mem_vm_free(void *addr, uword size)
#define MHEAP_N_SMALL_OBJECT_BINS
static void mheap_put_trace(void *v, uword offset, uword size)
Definition: mheap.c:1573
#define MHEAP_FLAG_THREAD_SAFE
static void new_free_elt(void *v, uword uoffset, uword n_user_data_bytes)
Definition: mheap.c:196
#define vec_bytes(v)
Number of data bytes in vector.
static uword mheap_max_size(void *v)
static void mheap_maybe_unlock(void *v)
Definition: mheap.c:75
static uword mheap_small_object_cache_mask(mheap_small_object_cache_t *c, uword bin)
Definition: mheap.c:302
uword bytes_used
Definition: mem.h:223
u8 * format_mheap(u8 *s, va_list *va)
Definition: mheap.c:1168
static uword min_log2(uword x)
Definition: clib.h:183
#define foreach_set_bit(var, mask, body)
Definition: bitops.h:158
vhost_user_memory_t memory
Definition: vhost-user.h:83
uword object_count
Definition: mem.h:219
static uword mheap_get_small_object(mheap_t *h, uword bin)
Definition: mheap.c:325
mheap_trace_main_t trace_main
#define static_always_inline
Definition: clib.h:85
#define always_inline
Definition: clib.h:84
static uword pow2_mask(uword x)
Definition: clib.h:251
#define MHEAP_FLAG_DISABLE_VM
u8 * format_white_space(u8 *s, va_list *va)
Definition: std-formats.c:113
u8 * format_hex_bytes(u8 *s, va_list *va)
Definition: std-formats.c:84
void mheap_usage(void *v, clib_mem_usage_t *usage)
Definition: mheap.c:1078
static uword mheap_elt_data_bytes(mheap_elt_t *e)
unsigned long u64
Definition: types.h:89
static mheap_elt_t * mheap_prev_elt(mheap_elt_t *e)
#define vec_end(v)
End (last data address) of vector.
volatile u32 lock
static uword mheap_bytes_overhead(void *v)
Definition: mheap.c:1028
static uword pointer_to_uword(const void *p)
Definition: types.h:131
static void mheap_trace_main_free(mheap_trace_main_t *tm)
Definition: mheap.c:1617
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:626
#define hash_get(h, key)
Definition: hash.h:248
#define hash_unset_mem(h, key)
Definition: hash.h:280
static uword format_get_indent(u8 *s)
Definition: format.h:72
static void mheap_maybe_lock(void *v)
Definition: mheap.c:54
uword os_get_cpu_number(void)
Definition: unix-misc.c:224
static uword mheap_elts(void *v)
#define hash_free(h)
Definition: hash.h:286
mheap_trace_t * traces
#define vec_dup(V)
Return copy of vector (no header, no alignment)
Definition: vec.h:334
static uword mheap_page_size
Definition: mheap.c:243
#define PREDICT_FALSE(x)
Definition: clib.h:97
static_always_inline uword mheap_vm_elt(void *v, uword flags, uword offset)
Definition: mheap.c:290
u64 validate_serial
static u32 * elt_data(void *v, heap_elt_t *e)
Definition: heap.c:213
#define MHEAP_N_USER_DATA_INVALID
void dmh(void *v)
Definition: mheap.c:1332
#define uword_to_pointer(u, type)
Definition: types.h:136
#define MHEAP_VM_MAP
Definition: mheap.c:236
static uword mheap_put_small_object(mheap_t *h, uword bin, uword offset)
Definition: mheap.c:344
static void mheap_validate_breakpoint()
Definition: mheap.c:1338
#define MHEAP_VM_NOMAP
Definition: mheap.c:238
svmdb_client_t * c
void * mheap_get_aligned(void *v, uword n_user_data_bytes, uword align, uword align_offset, uword *offset_return)
Definition: mheap.c:649
uword bytes_max
Definition: mem.h:238
static void free_last_elt(void *v, mheap_elt_t *e)
Definition: mheap.c:733
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:300
static uword mheap_elt_uoffset(void *v, mheap_elt_t *e)
static void * clib_mem_set_heap(void *heap)
Definition: mem.h:201
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:575
mheap_small_object_cache_t small_object_cache
static uword max_pow2(uword x)
Definition: clib.h:257
#define ARRAY_LEN(x)
Definition: clib.h:59
static uword round_pow2(uword x, uword pow2)
Definition: clib.h:272
#define CHECK(x)
static void set_free_elt(void *v, uword uoffset, uword n_user_data_bytes)
Definition: mheap.c:171
static void * clib_mem_vm_unmap(void *addr, uword size)
static void * clib_mem_get_heap(void)
Definition: mem.h:195
void * mheap_alloc_with_flags(void *memory, uword memory_size, uword flags)
Definition: mheap.c:875
static uword mheap_get_search_free_list(void *v, uword *n_user_bytes_arg, uword align, uword align_offset)
Definition: mheap.c:517
#define never_inline
Definition: clib.h:81
void mheap_trace(void *v, int enable)
Definition: mheap.c:1626
#define ASSERT(truth)
unsigned int u32
Definition: types.h:88
volatile u32 owner_cpu
u8 * format(u8 *s, char *fmt,...)
Definition: format.c:418
#define MHEAP_GROUNDED
uword vm_alloc_size
u32 size
Definition: vhost-user.h:77
static void * mheap_elt_data(void *v, mheap_elt_t *e)
#define MHEAP_FLAG_VALIDATE
#define clib_max(x, y)
Definition: clib.h:319
static u8x16 u8x16_splat(u8 a)
Definition: vector_sse2.h:200
static_always_inline uword mheap_page_round(uword addr)
Definition: mheap.c:246
static void * clib_mem_vm_alloc(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:375
static mheap_elt_t * mheap_first_corrupt(void *v)
Definition: mheap.c:1097
#define MHEAP_FLAG_SMALL_OBJECT_CACHE
static mheap_elt_t * mheap_elt_at_uoffset(void *v, uword uo)
uword mheap_bytes(void *v)
Definition: mheap.c:1036
template key/value backing page structure
Definition: bihash_doc.h:44
#define MHEAP_HAVE_SMALL_OBJECT_CACHE
i64 word
Definition: types.h:111
void qsort(void *base, uword n, uword size, int(*compar)(const void *, const void *))
Definition: qsort.c:56
void mheap_put(void *v, uword uoffset)
Definition: mheap.c:761
static int mheap_trace_sort(const void *t1, const void *t2)
Definition: mheap.c:1604
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
double f64
Definition: types.h:142
unsigned char u8
Definition: types.h:56
#define hash_foreach_pair(p, v, body)
Definition: hash.h:338
static uword max_log2(uword x)
Definition: clib.h:222
#define MHEAP_VM_ROUND_UP
Definition: mheap.c:240
static uword mheap_elt_size_to_user_n_bytes(uword n_bytes)
Definition: mheap.c:119
static void mheap_get_trace(void *v, uword offset, uword size)
Definition: mheap.c:1496
static void * clib_mem_vm_map(void *addr, uword size)
static u8 * format_mheap_stats(u8 *s, va_list *va)
Definition: mheap.c:1125
static mheap_elt_t * mheap_next_elt(mheap_elt_t *e)
word fformat(FILE *f, char *fmt,...)
Definition: format.c:452
format_function_t format_clib_elf_symbol_with_address
Definition: elf_clib.h:134
#define hash_get_mem(h, key)
Definition: hash.h:268
struct clib_bihash_value offset
template key/value backing page structure
#define STRUCT_SIZE_OF(t, f)
Definition: clib.h:64
void mheap_validate(void *v)
Definition: mheap.c:1344
static void remove_free_elt(void *v, mheap_elt_t *e, uword bin)
Definition: mheap.c:203
#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:981
int recursion_count
static void set_first_free_elt_offset(mheap_t *h, uword bin, uword uoffset)
Definition: mheap.c:154
#define CLIB_MEMORY_BARRIER()
Definition: clib.h:101
#define MHEAP_USER_DATA_WORD_BYTES
vhost_vring_addr_t addr
Definition: vhost-user.h:82
static uword user_data_size_to_bin_index(uword n_user_data_bytes)
Definition: mheap.c:92
#define MHEAP_VM_UNMAP
Definition: mheap.c:237
u32 flags
Definition: vhost-user.h:76
static u8 * mheap_vector(mheap_t *h)
uword clib_mem_get_page_size(void)
Definition: mem_mheap.c:110
#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:1042
#define MHEAP_MIN_USER_DATA_BYTES
static void mheap_elt_set_size(void *v, uword uoffset, uword n_user_data_bytes, uword is_free)
Definition: mheap.c:134
u32 first_free_elt_uoffset_by_bin[MHEAP_N_BINS]