FD.io VPP  v18.07-34-g55fbdb9
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_thread_index ();
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__) || defined (__i386__)
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 ((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  /* *INDENT-OFF* */
553  foreach_set_bit (bi, non_empty_bin_mask,
554  ({
555  uword r =
556  mheap_get_search_free_bin (v, bi + i * BITS (uword),
557  n_user_bytes_arg,
558  align,
559  align_offset);
560  if (r != MHEAP_GROUNDED) return r;
561  }));
562  /* *INDENT-ON* */
563  }
564 
565  return MHEAP_GROUNDED;
566 }
567 
568 static never_inline void *
570  uword n_user_data_bytes,
571  uword align,
572  uword align_offset, uword * offset_return)
573 {
574  /* Bounds of free and allocated objects (as above). */
575  uword f0, f1, o0, o1;
576  word free_size;
577  mheap_t *h = mheap_header (v);
578  mheap_elt_t *e;
579 
580  if (_vec_len (v) == 0)
581  {
582  _vec_len (v) = MHEAP_ELT_OVERHEAD_BYTES;
583 
584  /* Create first element of heap. */
585  e = mheap_elt_at_uoffset (v, _vec_len (v));
587  }
588 
589  f0 = _vec_len (v);
590 
591  o0 = round_pow2 (f0, align) - align_offset;
592  while (1)
593  {
594  free_size = o0 - f0 - MHEAP_ELT_OVERHEAD_BYTES;
595  if (o0 == f0 || free_size >= (word) sizeof (mheap_elt_t))
596  break;
597 
598  o0 += align;
599  }
600 
601  o1 = o0 + n_user_data_bytes;
602  f1 = o1 + MHEAP_ELT_OVERHEAD_BYTES;
603 
604  ASSERT (v != 0);
605  h = mheap_header (v);
606 
607  /* Make sure we have space for object plus overhead. */
608  if (f1 > h->max_size)
609  {
610  *offset_return = MHEAP_GROUNDED;
611  return v;
612  }
613 
614  _vec_len (v) = f1;
615 
616  if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
617  {
618  mheap_elt_t *f0_elt = mheap_elt_at_uoffset (v, f0);
619  mheap_elt_t *f1_elt = mheap_elt_at_uoffset (v, f1);
620 
621  uword f0_page = mheap_page_round (pointer_to_uword (f0_elt->user_data));
622  uword f1_page = mheap_page_round (pointer_to_uword (f1_elt->user_data));
623 
624  if (f1_page > f0_page)
625  mheap_vm (v, MHEAP_VM_MAP, f0_page, f1_page - f0_page);
626  }
627 
628  if (free_size > 0)
629  new_free_elt (v, f0, free_size);
630 
631  mheap_elt_set_size (v, o0, n_user_data_bytes, /* is_free */ 0);
632 
633  /* Mark last element. */
634  e = mheap_elt_at_uoffset (v, f1);
636 
637  *offset_return = o0;
638 
639  return v;
640 }
641 
642 void *
644  uword n_user_data_bytes,
645  uword align, uword align_offset, uword * offset_return)
646 {
647  mheap_t *h;
648  uword offset;
649  u64 cpu_times[2];
650 
651  cpu_times[0] = clib_cpu_time_now ();
652 
653  align = clib_max (align, STRUCT_SIZE_OF (mheap_elt_t, user_data[0]));
654  align = max_pow2 (align);
655 
656  /* Correct align offset to be smaller than alignment. */
657  align_offset &= (align - 1);
658 
659  /* Align offset must be multiple of minimum object size. */
660  if (align_offset % STRUCT_SIZE_OF (mheap_elt_t, user_data[0]) != 0)
661  {
662  *offset_return = MHEAP_GROUNDED;
663  return v;
664  }
665 
666  /*
667  * Round requested size.
668  *
669  * Step 1: round up to the minimum object size.
670  * Step 2: round up to a multiple of the user data size (e.g. 4)
671  * Step 3: if non-trivial alignment requested, round up
672  * so that the object precisely fills a chunk
673  * as big as the alignment request.
674  *
675  * Step 3 prevents the code from going into "bin search hyperspace":
676  * looking at a huge number of fractional remainder chunks, none of which
677  * will satisfy the alignment constraint. This fixes an allocator
678  * performance issue when one requests a large number of 16 byte objects
679  * aligned to 64 bytes, to name one variation on the theme.
680  */
681  n_user_data_bytes = clib_max (n_user_data_bytes, MHEAP_MIN_USER_DATA_BYTES);
682  n_user_data_bytes =
683  round_pow2 (n_user_data_bytes,
684  STRUCT_SIZE_OF (mheap_elt_t, user_data[0]));
685  if (align > MHEAP_ELT_OVERHEAD_BYTES)
686  n_user_data_bytes = clib_max (n_user_data_bytes,
687  align - MHEAP_ELT_OVERHEAD_BYTES);
688  if (!v)
689  v = mheap_alloc (0, 64 << 20);
690 
691  mheap_maybe_lock (v);
692 
693  h = mheap_header (v);
694 
695  if (h->flags & MHEAP_FLAG_VALIDATE)
696  mheap_validate (v);
697 
698  /* First search free lists for object. */
699  offset =
700  mheap_get_search_free_list (v, &n_user_data_bytes, align, align_offset);
701 
702  h = mheap_header (v);
703 
704  /* If that fails allocate object at end of heap by extending vector. */
705  if (offset == MHEAP_GROUNDED && _vec_len (v) < h->max_size)
706  {
707  v =
708  mheap_get_extend_vector (v, n_user_data_bytes, align, align_offset,
709  &offset);
710  h = mheap_header (v);
711  h->stats.n_vector_expands += offset != MHEAP_GROUNDED;
712  }
713 
714  *offset_return = offset;
715  if (offset != MHEAP_GROUNDED)
716  {
717  h->n_elts += 1;
718 
719  if (h->flags & MHEAP_FLAG_TRACE)
720  {
721  /* Recursion block for case when we are traceing main clib heap. */
722  h->flags &= ~MHEAP_FLAG_TRACE;
723 
724  mheap_get_trace (v, offset, n_user_data_bytes);
725 
726  h->flags |= MHEAP_FLAG_TRACE;
727  }
728  }
729 
730  if (h->flags & MHEAP_FLAG_VALIDATE)
731  mheap_validate (v);
732 
733  mheap_maybe_unlock (v);
734 
735  cpu_times[1] = clib_cpu_time_now ();
736  h->stats.n_clocks_get += cpu_times[1] - cpu_times[0];
737  h->stats.n_gets += 1;
738 
739  return v;
740 }
741 
742 static void
744 {
745  mheap_t *h = mheap_header (v);
746 
747  /* Possibly delete preceeding free element also. */
748  if (e->prev_is_free)
749  {
750  e = mheap_prev_elt (e);
751  remove_free_elt2 (v, e);
752  }
753 
755  {
756  if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
758  _vec_len (v) = 0;
759  }
760  else
761  {
762  uword uo = mheap_elt_uoffset (v, e);
763  if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
764  mheap_vm_elt (v, MHEAP_VM_UNMAP, uo);
766  _vec_len (v) = uo;
767  }
768 }
769 
770 void
771 mheap_put (void *v, uword uoffset)
772 {
773  mheap_t *h;
774  uword n_user_data_bytes, bin;
775  mheap_elt_t *e, *n;
776  uword trace_uoffset, trace_n_user_data_bytes;
777  u64 cpu_times[2];
778 
779  cpu_times[0] = clib_cpu_time_now ();
780 
781  h = mheap_header (v);
782 
783  mheap_maybe_lock (v);
784 
785  if (h->flags & MHEAP_FLAG_VALIDATE)
786  mheap_validate (v);
787 
788  ASSERT (h->n_elts > 0);
789  h->n_elts--;
790  h->stats.n_puts += 1;
791 
792  e = mheap_elt_at_uoffset (v, uoffset);
793  n = mheap_next_elt (e);
794  n_user_data_bytes = mheap_elt_data_bytes (e);
795 
796  trace_uoffset = uoffset;
797  trace_n_user_data_bytes = n_user_data_bytes;
798 
799  bin = user_data_size_to_bin_index (n_user_data_bytes);
801  && bin < 255 && (h->flags & MHEAP_FLAG_SMALL_OBJECT_CACHE))
802  {
803  uoffset = mheap_put_small_object (h, bin, uoffset);
804  if (uoffset == 0)
805  goto done;
806 
807  e = mheap_elt_at_uoffset (v, uoffset);
808  n = mheap_next_elt (e);
809  n_user_data_bytes = mheap_elt_data_bytes (e);
810  }
811 
812  /* Assert that forward and back pointers are equal. */
813  if (e->n_user_data != n->prev_n_user_data)
814  os_panic ();
815 
816  /* Forward and backwards is_free must agree. */
817  if (e->is_free != n->prev_is_free)
818  os_panic ();
819 
820  /* Object was already freed. */
821  if (e->is_free)
822  os_panic ();
823 
824  /* Special case: delete last element in heap. */
826  free_last_elt (v, e);
827 
828  else
829  {
830  uword f0, f1, n_combine;
831 
832  f0 = uoffset;
833  f1 = f0 + n_user_data_bytes;
834  n_combine = 0;
835 
836  if (e->prev_is_free)
837  {
838  mheap_elt_t *p = mheap_prev_elt (e);
839  f0 = mheap_elt_uoffset (v, p);
840  remove_free_elt2 (v, p);
841  n_combine++;
842  }
843 
844  if (n->is_free)
845  {
846  mheap_elt_t *m = mheap_next_elt (n);
847  f1 = (void *) m - v;
848  remove_free_elt2 (v, n);
849  n_combine++;
850  }
851 
852  if (n_combine)
853  mheap_elt_set_size (v, f0, f1 - f0, /* is_free */ 1);
854  else
855  e->is_free = n->prev_is_free = 1;
856  set_free_elt (v, f0, f1 - f0);
857 
858  if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
859  mheap_vm_elt (v, MHEAP_VM_UNMAP, f0);
860  }
861 
862 done:
863  h = mheap_header (v);
864 
865  if (h->flags & MHEAP_FLAG_TRACE)
866  {
867  /* Recursion block for case when we are traceing main clib heap. */
868  h->flags &= ~MHEAP_FLAG_TRACE;
869 
870  mheap_put_trace (v, trace_uoffset, trace_n_user_data_bytes);
871 
872  h->flags |= MHEAP_FLAG_TRACE;
873  }
874 
875  if (h->flags & MHEAP_FLAG_VALIDATE)
876  mheap_validate (v);
877 
878  mheap_maybe_unlock (v);
879 
880  cpu_times[1] = clib_cpu_time_now ();
881  h->stats.n_clocks_put += cpu_times[1] - cpu_times[0];
882 }
883 
884 void *
886 {
887  mheap_t *h;
888  void *v;
889  uword size;
890 
891  if (!mheap_page_size)
892  mheap_page_size = clib_mem_get_page_size ();
893 
894  if (!memory)
895  {
896  /* No memory given, try to VM allocate some. */
897  memory = clib_mem_vm_alloc (memory_size);
898  if (!memory)
899  return 0;
900 
901  /* No memory region implies we have virtual memory. */
902  flags &= ~MHEAP_FLAG_DISABLE_VM;
903  }
904 
905  /* Make sure that given memory is page aligned. */
906  {
907  uword am, av, ah;
908 
909  am = pointer_to_uword (memory);
910  av = mheap_page_round (am);
911  v = uword_to_pointer (av, void *);
912  h = mheap_header (v);
913  ah = pointer_to_uword (h);
914  while (ah < am)
915  ah += mheap_page_size;
916 
917  h = uword_to_pointer (ah, void *);
918  v = mheap_vector (h);
919 
920  if (PREDICT_FALSE (memory + memory_size < v))
921  {
922  /*
923  * This will happen when the requested memory_size is too
924  * small to cope with the heap header and/or memory alignment.
925  */
926  clib_mem_vm_free (memory, memory_size);
927  return 0;
928  }
929 
930  size = memory + memory_size - v;
931  }
932 
933  /* VM map header so we can use memory. */
934  if (!(flags & MHEAP_FLAG_DISABLE_VM))
935  clib_mem_vm_map (h, sizeof (h[0]));
936 
937  /* Zero vector header: both heap header and vector length. */
938  memset (h, 0, sizeof (h[0]));
939  _vec_len (v) = 0;
940 
941  h->vm_alloc_offset_from_header = (void *) h - memory;
943 
944  h->max_size = size;
945  h->owner_cpu = ~0;
946 
947  /* Set flags based on those given less builtin-flags. */
948  h->flags |= (flags & ~MHEAP_FLAG_TRACE);
949 
950  /* Unmap remainder of heap until we will be ready to use it. */
951  if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
953  (clib_address_t) v, h->max_size);
954 
955  /* Initialize free list heads to empty. */
956  memset (h->first_free_elt_uoffset_by_bin, 0xFF,
957  sizeof (h->first_free_elt_uoffset_by_bin));
958 
959  return v;
960 }
961 
962 void *
964 {
965  uword flags = 0;
966 
967  if (memory != 0)
968  flags |= MHEAP_FLAG_DISABLE_VM;
969 
970 #ifdef CLIB_HAVE_VEC128
972 #endif
973 
974  return mheap_alloc_with_flags (memory, size, flags);
975 }
976 
977 void *
978 _mheap_free (void *v)
979 {
980  mheap_t *h = mheap_header (v);
981 
982  if (v)
984  h->vm_alloc_size);
985 
986  return 0;
987 }
988 
989 /* Call user's function with each object in heap. */
990 void
991 mheap_foreach (void *v,
992  uword (*func) (void *arg, void *v, void *elt_data,
993  uword elt_size), void *arg)
994 {
995  mheap_elt_t *e;
996  u8 *stack_heap, *clib_mem_mheap_save;
997  u8 tmp_heap_memory[16 * 1024];
998 
999  mheap_maybe_lock (v);
1000 
1001  if (vec_len (v) == 0)
1002  goto done;
1003 
1004  clib_mem_mheap_save = 0;
1005  stack_heap = 0;
1006 
1007  /* Allocate a new temporary heap on the stack.
1008  This is so that our hash table & user's callback function can
1009  themselves allocate memory somewhere without getting in the way
1010  of the heap we are looking at. */
1011  if (v == clib_mem_get_heap ())
1012  {
1013  stack_heap = mheap_alloc (tmp_heap_memory, sizeof (tmp_heap_memory));
1014  clib_mem_mheap_save = v;
1015  clib_mem_set_heap (stack_heap);
1016  }
1017 
1018  for (e = v;
1020  {
1021  void *p = mheap_elt_data (v, e);
1022  if (e->is_free)
1023  continue;
1024  if ((*func) (arg, v, p, mheap_elt_data_bytes (e)))
1025  break;
1026  }
1027 
1028  /* Restore main CLIB heap. */
1029  if (clib_mem_mheap_save)
1030  clib_mem_set_heap (clib_mem_mheap_save);
1031 
1032 done:
1033  mheap_maybe_unlock (v);
1034 }
1035 
1036 /* Bytes in mheap header overhead not including data bytes. */
1039 {
1040  mheap_t *h = mheap_header (v);
1041  return v ? sizeof (h[0]) + h->n_elts * sizeof (mheap_elt_t) : 0;
1042 }
1043 
1044 /* Total number of bytes including both data and overhead. */
1045 uword
1046 mheap_bytes (void *v)
1047 {
1048  return mheap_bytes_overhead (v) + vec_bytes (v);
1049 }
1050 
1051 static void
1053 {
1054  mheap_t *h = mheap_header (v);
1055  uword used = 0, free = 0, free_vm_unmapped = 0;
1056 
1057  if (vec_len (v) > 0)
1058  {
1059  mheap_elt_t *e;
1060 
1061  for (e = v;
1063  e = mheap_next_elt (e))
1064  {
1066  if (e->is_free)
1067  {
1068  free += size;
1069  if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
1070  free_vm_unmapped +=
1072  }
1073  else
1074  used += size;
1075  }
1076  }
1077 
1078  usage->object_count = mheap_elts (v);
1079  usage->bytes_total = mheap_bytes (v);
1080  usage->bytes_overhead = mheap_bytes_overhead (v);
1081  usage->bytes_max = mheap_max_size (v);
1082  usage->bytes_used = used;
1083  usage->bytes_free = free;
1084  usage->bytes_free_reclaimed = free_vm_unmapped;
1085 }
1086 
1087 void
1089 {
1090  mheap_maybe_lock (v);
1091  mheap_usage_no_lock (v, usage);
1092  mheap_maybe_unlock (v);
1093 }
1094 
1095 static u8 *
1096 format_mheap_byte_count (u8 * s, va_list * va)
1097 {
1098  uword n_bytes = va_arg (*va, uword);
1099  if (n_bytes < 1024)
1100  return format (s, "%wd", n_bytes);
1101  else
1102  return format (s, "%wdk", n_bytes / 1024);
1103 }
1104 
1105 /* Returns first corrupt heap element. */
1106 static mheap_elt_t *
1108 {
1109  mheap_elt_t *e, *n;
1110 
1111  if (vec_len (v) == 0)
1112  return 0;
1113 
1114  e = v;
1115  while (1)
1116  {
1118  break;
1119 
1120  n = mheap_next_elt (e);
1121 
1122  if (e->n_user_data != n->prev_n_user_data)
1123  return e;
1124 
1125  if (e->is_free != n->prev_is_free)
1126  return e;
1127 
1128  e = n;
1129  }
1130 
1131  return 0;
1132 }
1133 
1134 static u8 *
1135 format_mheap_stats (u8 * s, va_list * va)
1136 {
1137  mheap_t *h = va_arg (*va, mheap_t *);
1138  mheap_stats_t *st = &h->stats;
1139  u32 indent = format_get_indent (s);
1140 
1141  s =
1142  format (s,
1143  "alloc. from small object cache: %Ld hits %Ld attempts (%.2f%%) replacements %d",
1146  0 ? 100. * (f64) st->n_small_object_cache_hits /
1147  (f64) st->n_small_object_cache_attempts : 0.),
1149 
1150  s =
1151  format (s,
1152  "\n%Ualloc. from free-list: %Ld attempts, %Ld hits (%.2f%%), %Ld considered (per-attempt %.2f)",
1156  0 ? 100. * (f64) st->free_list.n_objects_found /
1157  (f64) st->free_list.n_search_attempts : 0.),
1160  0 ? (f64) st->free_list.n_objects_searched /
1161  (f64) st->free_list.n_search_attempts : 0.));
1162 
1163  s = format (s, "\n%Ualloc. from vector-expand: %Ld",
1164  format_white_space, indent, st->n_vector_expands);
1165 
1166  s = format (s, "\n%Uallocs: %Ld %.2f clocks/call",
1167  format_white_space, indent,
1168  st->n_gets, (f64) st->n_clocks_get / (f64) st->n_gets);
1169 
1170  s = format (s, "\n%Ufrees: %Ld %.2f clocks/call",
1171  format_white_space, indent,
1172  st->n_puts, (f64) st->n_clocks_put / (f64) st->n_puts);
1173 
1174  return s;
1175 }
1176 
1177 u8 *
1178 format_mheap (u8 * s, va_list * va)
1179 {
1180  void *v = va_arg (*va, u8 *);
1181  int verbose = va_arg (*va, int);
1182 
1183  mheap_t *h;
1184  uword i, size;
1185  u32 indent;
1187  mheap_elt_t *first_corrupt;
1188 
1189  mheap_maybe_lock (v);
1190 
1191  h = mheap_header (v);
1192 
1193  mheap_usage_no_lock (v, &usage);
1194 
1195  indent = format_get_indent (s);
1196 
1197  s =
1198  format (s,
1199  "%d objects, %U of %U used, %U free, %U reclaimed, %U overhead",
1205 
1206  if (usage.bytes_max != ~0)
1207  s = format (s, ", %U capacity", format_mheap_byte_count, usage.bytes_max);
1208 
1209  /* Show histogram of sizes. */
1210  if (verbose > 1)
1211  {
1212  uword hist[MHEAP_N_BINS];
1213  mheap_elt_t *e;
1214  uword i, n_hist;
1215 
1216  memset (hist, 0, sizeof (hist));
1217 
1218  n_hist = 0;
1219  for (e = v;
1221  e = mheap_next_elt (e))
1222  {
1223  uword n_user_data_bytes = mheap_elt_data_bytes (e);
1224  uword bin = user_data_size_to_bin_index (n_user_data_bytes);
1225  if (!e->is_free)
1226  {
1227  hist[bin] += 1;
1228  n_hist += 1;
1229  }
1230  }
1231 
1232  s = format (s, "\n%U%=12s%=12s%=16s",
1233  format_white_space, indent + 2,
1234  "Size", "Count", "Fraction");
1235 
1236  for (i = 0; i < ARRAY_LEN (hist); i++)
1237  {
1238  if (hist[i] == 0)
1239  continue;
1240  s = format (s, "\n%U%12d%12wd%16.4f",
1241  format_white_space, indent + 2,
1243  i * MHEAP_USER_DATA_WORD_BYTES, hist[i],
1244  (f64) hist[i] / (f64) n_hist);
1245  }
1246  }
1247 
1248  if (verbose)
1249  s = format (s, "\n%U%U",
1250  format_white_space, indent + 2, format_mheap_stats, h);
1251 
1252  if ((h->flags & MHEAP_FLAG_TRACE) && vec_len (h->trace_main.traces) > 0)
1253  {
1254  /* Make a copy of traces since we'll be sorting them. */
1255  mheap_trace_t *t, *traces_copy;
1256  u32 indent, total_objects_traced;
1257 
1258  traces_copy = vec_dup (h->trace_main.traces);
1259  qsort (traces_copy, vec_len (traces_copy), sizeof (traces_copy[0]),
1261 
1262  total_objects_traced = 0;
1263  s = format (s, "\n");
1264  vec_foreach (t, traces_copy)
1265  {
1266  /* Skip over free elements. */
1267  if (t->n_allocations == 0)
1268  continue;
1269 
1270  total_objects_traced += t->n_allocations;
1271 
1272  /* When not verbose only report allocations of more than 1k. */
1273  if (!verbose && t->n_bytes < 1024)
1274  continue;
1275 
1276  if (t == traces_copy)
1277  s = format (s, "%=9s%=9s %=10s Traceback\n", "Bytes", "Count",
1278  "Sample");
1279  s = format (s, "%9d%9d %p", t->n_bytes, t->n_allocations,
1280  t->offset + v);
1281  indent = format_get_indent (s);
1282  for (i = 0; i < ARRAY_LEN (t->callers) && t->callers[i]; i++)
1283  {
1284  if (i > 0)
1285  s = format (s, "%U", format_white_space, indent);
1286 #ifdef CLIB_UNIX
1287  s =
1289  t->callers[i]);
1290 #else
1291  s = format (s, " %p\n", t->callers[i]);
1292 #endif
1293  }
1294  }
1295 
1296  s = format (s, "%d total traced objects\n", total_objects_traced);
1297 
1298  vec_free (traces_copy);
1299  }
1300 
1301  first_corrupt = mheap_first_corrupt (v);
1302  if (first_corrupt)
1303  {
1304  size = mheap_elt_data_bytes (first_corrupt);
1305  s = format (s, "\n first corrupt object: %p, size %wd\n %U",
1306  first_corrupt, size, format_hex_bytes, first_corrupt, size);
1307  }
1308 
1309  /* FIXME. This output could be wrong in the unlikely case that format
1310  uses the same mheap as we are currently inspecting. */
1311  if (verbose > 1)
1312  {
1313  mheap_elt_t *e;
1314  uword i, o;
1315 
1316  s = format (s, "\n");
1317 
1318  e = mheap_elt_at_uoffset (v, 0);
1319  i = 0;
1320  while (1)
1321  {
1322  if ((i % 8) == 0)
1323  s = format (s, "%8d: ", i);
1324 
1325  o = mheap_elt_uoffset (v, e);
1326 
1327  if (e->is_free)
1328  s = format (s, "(%8d) ", o);
1329  else
1330  s = format (s, " %8d ", o);
1331 
1332  if ((i % 8) == 7 || (i + 1) >= h->n_elts)
1333  s = format (s, "\n");
1334  }
1335  }
1336 
1337  mheap_maybe_unlock (v);
1338 
1339  return s;
1340 }
1341 
1342 void
1343 dmh (void *v)
1344 {
1345  fformat (stderr, "%U", format_mheap, v, 1);
1346 }
1347 
1348 static void
1350 {
1351  os_panic ();
1352 }
1353 
1354 void
1356 {
1357  mheap_t *h = mheap_header (v);
1358  uword i, s;
1359 
1360  uword elt_count, elt_size;
1361  uword free_count_from_free_lists, free_size_from_free_lists;
1362  uword small_elt_free_count, small_elt_free_size;
1363 
1364 #define CHECK(x) if (! (x)) { mheap_validate_breakpoint (); os_panic (); }
1365 
1366  if (vec_len (v) == 0)
1367  return;
1368 
1369  mheap_maybe_lock (v);
1370 
1371  /* Validate number of elements and size. */
1372  free_size_from_free_lists = free_count_from_free_lists = 0;
1373  for (i = 0; i < ARRAY_LEN (h->first_free_elt_uoffset_by_bin); i++)
1374  {
1375  mheap_elt_t *e, *n;
1376  uword is_first;
1377 
1379  ==
1380  ((h->non_empty_free_elt_heads[i /
1381  BITS (uword)] & ((uword) 1 <<
1382  (uword) (i %
1383  BITS
1384  (uword))))
1385  != 0));
1386 
1388  continue;
1389 
1391  is_first = 1;
1392  while (1)
1393  {
1394  uword s;
1395 
1396  n = mheap_next_elt (e);
1397 
1398  /* Object must be marked free. */
1399  CHECK (e->is_free);
1400 
1401  /* Next object's previous free bit must also be set. */
1402  CHECK (n->prev_is_free);
1403 
1404  if (is_first)
1405  CHECK (e->free_elt.prev_uoffset == MHEAP_GROUNDED);
1406  is_first = 0;
1407 
1408  s = mheap_elt_data_bytes (e);
1410 
1411  free_count_from_free_lists += 1;
1412  free_size_from_free_lists += s;
1413 
1414  if (e->free_elt.next_uoffset == MHEAP_GROUNDED)
1415  break;
1416 
1417  n = mheap_elt_at_uoffset (v, e->free_elt.next_uoffset);
1418 
1419  /* Check free element linkages. */
1420  CHECK (n->free_elt.prev_uoffset == mheap_elt_uoffset (v, e));
1421 
1422  e = n;
1423  }
1424  }
1425 
1426  /* Go through small object cache. */
1427  small_elt_free_count = small_elt_free_size = 0;
1428  for (i = 0; i < ARRAY_LEN (h->small_object_cache.bins.as_u8); i++)
1429  {
1430  if (h->small_object_cache.bins.as_u8[i] != 0)
1431  {
1432  mheap_elt_t *e;
1433  uword b = h->small_object_cache.bins.as_u8[i] - 1;
1435  uword s;
1436 
1437  e = mheap_elt_at_uoffset (v, o);
1438 
1439  /* Object must be allocated. */
1440  CHECK (!e->is_free);
1441 
1442  s = mheap_elt_data_bytes (e);
1444 
1445  small_elt_free_count += 1;
1446  small_elt_free_size += s;
1447  }
1448  }
1449 
1450  {
1451  mheap_elt_t *e, *n;
1452  uword elt_free_size, elt_free_count;
1453 
1454  elt_count = elt_size = elt_free_size = elt_free_count = 0;
1455  for (e = v; e->n_user_data != MHEAP_N_USER_DATA_INVALID; e = n)
1456  {
1458  CHECK (e->prev_n_user_data * sizeof (e->user_data[0]) >=
1460 
1461  CHECK (e->n_user_data * sizeof (e->user_data[0]) >=
1463 
1464  n = mheap_next_elt (e);
1465 
1466  CHECK (e->is_free == n->prev_is_free);
1467 
1468  elt_count++;
1469  s = mheap_elt_data_bytes (e);
1470  elt_size += s;
1471 
1472  if (e->is_free)
1473  {
1474  elt_free_count++;
1475  elt_free_size += s;
1476  }
1477 
1478  /* Consecutive free objects should have been combined. */
1479  CHECK (!(e->prev_is_free && n->prev_is_free));
1480  }
1481 
1482  CHECK (free_count_from_free_lists == elt_free_count);
1483  CHECK (free_size_from_free_lists == elt_free_size);
1484  CHECK (elt_count == h->n_elts + elt_free_count + small_elt_free_count);
1485  CHECK (elt_size + (elt_count + 1) * MHEAP_ELT_OVERHEAD_BYTES ==
1486  vec_len (v));
1487  }
1488 
1489  {
1490  mheap_elt_t *e, *n;
1491 
1492  for (e = v; e->n_user_data == MHEAP_N_USER_DATA_INVALID; e = n)
1493  {
1494  n = mheap_next_elt (e);
1495  CHECK (e->n_user_data == n->prev_n_user_data);
1496  }
1497  }
1498 
1499 #undef CHECK
1500 
1501  mheap_maybe_unlock (v);
1502 
1503  h->validate_serial += 1;
1504 }
1505 
1506 static void
1508 {
1509  mheap_t *h;
1510  mheap_trace_main_t *tm;
1511  mheap_trace_t *t;
1512  uword i, n_callers, trace_index, *p;
1514 
1515  /* Spurious Coverity warnings be gone. */
1516  memset (&trace, 0, sizeof (trace));
1517 
1518  n_callers = clib_backtrace (trace.callers, ARRAY_LEN (trace.callers),
1519  /* Skip mheap_get_aligned's frame */ 1);
1520  if (n_callers == 0)
1521  return;
1522 
1523  for (i = n_callers; i < ARRAY_LEN (trace.callers); i++)
1524  trace.callers[i] = 0;
1525 
1526  h = mheap_header (v);
1527  tm = &h->trace_main;
1528 
1529  if (!tm->trace_by_callers)
1530  tm->trace_by_callers =
1531  hash_create_shmem (0, sizeof (trace.callers), sizeof (uword));
1532 
1533  p = hash_get_mem (tm->trace_by_callers, &trace.callers);
1534  if (p)
1535  {
1536  trace_index = p[0];
1537  t = tm->traces + trace_index;
1538  }
1539  else
1540  {
1541  i = vec_len (tm->trace_free_list);
1542  if (i > 0)
1543  {
1544  trace_index = tm->trace_free_list[i - 1];
1545  _vec_len (tm->trace_free_list) = i - 1;
1546  }
1547  else
1548  {
1549  mheap_trace_t *old_start = tm->traces;
1550  mheap_trace_t *old_end = vec_end (tm->traces);
1551 
1552  vec_add2 (tm->traces, t, 1);
1553 
1554  if (tm->traces != old_start)
1555  {
1556  hash_pair_t *p;
1557  mheap_trace_t *q;
1558  /* *INDENT-OFF* */
1560  ({
1561  q = uword_to_pointer (p->key, mheap_trace_t *);
1562  ASSERT (q >= old_start && q < old_end);
1563  p->key = pointer_to_uword (tm->traces + (q - old_start));
1564  }));
1565  /* *INDENT-ON* */
1566  }
1567  trace_index = t - tm->traces;
1568  }
1569 
1570  t = tm->traces + trace_index;
1571  t[0] = trace;
1572  t->n_allocations = 0;
1573  t->n_bytes = 0;
1574  hash_set_mem (tm->trace_by_callers, t->callers, trace_index);
1575  }
1576 
1577  t->n_allocations += 1;
1578  t->n_bytes += size;
1579  t->offset = offset; /* keep a sample to autopsy */
1580  hash_set (tm->trace_index_by_offset, offset, t - tm->traces);
1581 }
1582 
1583 static void
1585 {
1586  mheap_t *h;
1587  mheap_trace_main_t *tm;
1588  mheap_trace_t *t;
1589  uword trace_index, *p;
1590 
1591  h = mheap_header (v);
1592  tm = &h->trace_main;
1593  p = hash_get (tm->trace_index_by_offset, offset);
1594  if (!p)
1595  return;
1596 
1597  trace_index = p[0];
1598  hash_unset (tm->trace_index_by_offset, offset);
1599  ASSERT (trace_index < vec_len (tm->traces));
1600 
1601  t = tm->traces + trace_index;
1602  ASSERT (t->n_allocations > 0);
1603  ASSERT (t->n_bytes >= size);
1604  t->n_allocations -= 1;
1605  t->n_bytes -= size;
1606  if (t->n_allocations == 0)
1607  {
1609  vec_add1 (tm->trace_free_list, trace_index);
1610  memset (t, 0, sizeof (t[0]));
1611  }
1612 }
1613 
1614 static int
1615 mheap_trace_sort (const void *_t1, const void *_t2)
1616 {
1617  const mheap_trace_t *t1 = _t1;
1618  const mheap_trace_t *t2 = _t2;
1619  word cmp;
1620 
1621  cmp = (word) t2->n_bytes - (word) t1->n_bytes;
1622  if (!cmp)
1623  cmp = (word) t2->n_allocations - (word) t1->n_allocations;
1624  return cmp;
1625 }
1626 
1627 always_inline void
1629 {
1630  vec_free (tm->traces);
1631  vec_free (tm->trace_free_list);
1634 }
1635 
1636 void
1637 mheap_trace (void *v, int enable)
1638 {
1639  mheap_t *h;
1640 
1641  h = mheap_header (v);
1642 
1643  if (enable)
1644  {
1645  h->flags |= MHEAP_FLAG_TRACE;
1646  }
1647  else
1648  {
1650  h->flags &= ~MHEAP_FLAG_TRACE;
1651  }
1652 }
1653 
1654 /*
1655  * fd.io coding-style-patch-verification: ON
1656  *
1657  * Local Variables:
1658  * eval: (c-set-style "gnu")
1659  * End:
1660  */
#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:252
uword bytes_total
Definition: mem.h:248
static vlib_cli_command_t trace
(constructor) VLIB_CLI_COMMAND (trace)
Definition: vlib_api_cli.c:862
#define hash_set(h, key, value)
Definition: hash.h:255
uword bytes_free
Definition: mem.h:248
vhost_user_memory_t memory
Definition: vhost_user.h:117
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:261
static_always_inline uword mheap_vm(void *v, uword flags, clib_address_t start_addr, uword size)
Definition: mheap.c:258
static u8 * format_mheap_byte_count(u8 *s, va_list *va)
Definition: mheap.c:1096
uword offsets[BITS(uword)]
union mheap_small_object_cache_t::@17 bins
uword vm_alloc_offset_from_header
uword callers[12]
uword bytes_free_reclaimed
Definition: mem.h:255
static uword mheap_elt_size_to_user_n_words(uword n_bytes)
Definition: mheap.c:126
unsigned long u64
Definition: types.h:89
void * mheap_alloc(void *memory, uword size)
Definition: mheap.c:963
u64 clib_address_t
Definition: types.h:121
uword clib_backtrace(uword *callers, uword max_callers, uword n_frames_to_skip)
Definition: backtrace.c:226
void os_panic(void)
Definition: unix-misc.c:174
struct mheap_elt_t::@13::@15 free_elt
#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:523
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:562
int i
u64 n_small_object_cache_attempts
static mheap_t * mheap_header(u8 *v)
static void usage(void)
Definition: health_check.c:14
static u32 format_get_indent(u8 *s)
Definition: format.h:72
#define hash_set_mem(h, key, value)
Definition: hash.h:275
#define STRUCT_OFFSET_OF(t, f)
Definition: clib.h:62
#define MHEAP_N_SMALL_OBJECT_BINS
struct mheap_stats_t::@16 free_list
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:419
static void mheap_put_trace(void *v, uword offset, uword size)
Definition: mheap.c:1584
#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)
vhost_vring_addr_t addr
Definition: vhost_user.h:116
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:248
unsigned char u8
Definition: types.h:56
u8 * format_mheap(u8 *s, va_list *va)
Definition: mheap.c:1178
static uword min_log2(uword x)
Definition: clib.h:138
#define foreach_set_bit(var, mask, body)
Definition: bitops.h:166
double f64
Definition: types.h:142
uword object_count
Definition: mem.h:244
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:93
i64 word
Definition: types.h:111
#define always_inline
Definition: clib.h:92
static uword pow2_mask(uword x)
Definition: clib.h:214
#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:1088
static uword mheap_elt_data_bytes(mheap_elt_t *e)
static mheap_elt_t * mheap_prev_elt(mheap_elt_t *e)
unsigned int u32
Definition: types.h:88
#define vec_end(v)
End (last data address) of vector.
volatile u32 lock
static uword mheap_bytes_overhead(void *v)
Definition: mheap.c:1038
static void mheap_trace_main_free(mheap_trace_main_t *tm)
Definition: mheap.c:1628
uword non_empty_free_elt_heads[(MHEAP_N_BINS+BITS(uword)-1)/BITS(uword)]
mheap_stats_t stats
#define hash_get(h, key)
Definition: hash.h:249
uword size
#define hash_unset_mem(h, key)
Definition: hash.h:291
static void mheap_maybe_lock(void *v)
Definition: mheap.c:54
#define v
Definition: acl.c:491
u64 memory_size
Definition: vhost_user.h:110
static uword mheap_elts(void *v)
#define hash_free(h)
Definition: hash.h:310
mheap_trace_t * traces
#define vec_dup(V)
Return copy of vector (no header, no alignment)
Definition: vec.h:373
static uword mheap_page_size
Definition: mheap.c:243
#define PREDICT_FALSE(x)
Definition: clib.h:105
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
word fformat(FILE *f, char *fmt,...)
Definition: format.c:453
void dmh(void *v)
Definition: mheap.c:1343
u32 flags
Definition: vhost_user.h:110
#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:1349
#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:643
uword bytes_max
Definition: mem.h:263
static void free_last_elt(void *v, mheap_elt_t *e)
Definition: mheap.c:743
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:339
static uword mheap_elt_uoffset(void *v, mheap_elt_t *e)
static void * clib_mem_set_heap(void *heap)
Definition: mem.h:226
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:569
mheap_small_object_cache_t small_object_cache
static uword max_pow2(uword x)
Definition: clib.h:220
#define ARRAY_LEN(x)
Definition: clib.h:59
static uword round_pow2(uword x, uword pow2)
Definition: clib.h:235
#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_get_heap(void)
Definition: mem.h:220
void * mheap_alloc_with_flags(void *memory, uword memory_size, uword flags)
Definition: mheap.c:885
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:89
void mheap_trace(void *v, int enable)
Definition: mheap.c:1637
#define uword_to_pointer(u, type)
Definition: types.h:136
#define hash_create_shmem(elts, key_bytes, value_bytes)
Definition: hash.h:684
#define ASSERT(truth)
volatile u32 owner_cpu
#define MHEAP_GROUNDED
uword vm_alloc_size
static void * mheap_elt_data(void *v, mheap_elt_t *e)
#define MHEAP_FLAG_VALIDATE
static uword pointer_to_uword(const void *p)
Definition: types.h:131
#define clib_max(x, y)
Definition: clib.h:282
static_always_inline uword mheap_page_round(uword addr)
Definition: mheap.c:246
#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:1107
#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:1046
template key/value backing page structure
Definition: bihash_doc.h:44
#define MHEAP_HAVE_SMALL_OBJECT_CACHE
static void clib_mem_vm_free(void *addr, uword size)
Definition: mem.h:289
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:771
static int mheap_trace_sort(const void *t1, const void *t2)
Definition: mheap.c:1615
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
#define hash_foreach_pair(p, v, body)
Iterate over hash pairs.
Definition: hash.h:373
static uword max_log2(uword x)
Definition: clib.h:185
#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
u64 uword
Definition: types.h:112
static void mheap_get_trace(void *v, uword offset, uword size)
Definition: mheap.c:1507
static_always_inline uword os_get_thread_index(void)
Definition: os.h:62
static u8 * format_mheap_stats(u8 *s, va_list *va)
Definition: mheap.c:1135
static mheap_elt_t * mheap_next_elt(mheap_elt_t *e)
format_function_t format_clib_elf_symbol_with_address
Definition: elf_clib.h:134
#define hash_get_mem(h, key)
Definition: hash.h:269
struct clib_bihash_value offset
template key/value backing page structure
static void * clib_mem_vm_unmap(void *addr, uword size)
Definition: mem.h:295
#define STRUCT_SIZE_OF(t, f)
Definition: clib.h:64
void mheap_validate(void *v)
Definition: mheap.c:1355
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:991
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:109
#define MHEAP_USER_DATA_WORD_BYTES
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
static u8 * mheap_vector(mheap_t *h)
uword clib_mem_get_page_size(void)
Definition: mem_mheap.c:110
static void * clib_mem_vm_alloc(uword size)
Definition: mem.h:272
#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:1052
#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]
static void * clib_mem_vm_map(void *addr, uword size)
Definition: mem.h:312