FD.io VPP  v17.07.01-10-g3be13f0
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 (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  /* *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  /* Round requested size. */
667  n_user_data_bytes = clib_max (n_user_data_bytes, MHEAP_MIN_USER_DATA_BYTES);
668  n_user_data_bytes =
669  round_pow2 (n_user_data_bytes,
670  STRUCT_SIZE_OF (mheap_elt_t, user_data[0]));
671 
672  if (!v)
673  v = mheap_alloc (0, 64 << 20);
674 
675  mheap_maybe_lock (v);
676 
677  h = mheap_header (v);
678 
679  if (h->flags & MHEAP_FLAG_VALIDATE)
680  mheap_validate (v);
681 
682  /* First search free lists for object. */
683  offset =
684  mheap_get_search_free_list (v, &n_user_data_bytes, align, align_offset);
685 
686  h = mheap_header (v);
687 
688  /* If that fails allocate object at end of heap by extending vector. */
689  if (offset == MHEAP_GROUNDED && _vec_len (v) < h->max_size)
690  {
691  v =
692  mheap_get_extend_vector (v, n_user_data_bytes, align, align_offset,
693  &offset);
694  h = mheap_header (v);
695  h->stats.n_vector_expands += offset != MHEAP_GROUNDED;
696  }
697 
698  *offset_return = offset;
699  if (offset != MHEAP_GROUNDED)
700  {
701  h->n_elts += 1;
702 
703  if (h->flags & MHEAP_FLAG_TRACE)
704  {
705  /* Recursion block for case when we are traceing main clib heap. */
706  h->flags &= ~MHEAP_FLAG_TRACE;
707 
708  mheap_get_trace (v, offset, n_user_data_bytes);
709 
710  h->flags |= MHEAP_FLAG_TRACE;
711  }
712  }
713 
714  if (h->flags & MHEAP_FLAG_VALIDATE)
715  mheap_validate (v);
716 
717  mheap_maybe_unlock (v);
718 
719  cpu_times[1] = clib_cpu_time_now ();
720  h->stats.n_clocks_get += cpu_times[1] - cpu_times[0];
721  h->stats.n_gets += 1;
722 
723  return v;
724 }
725 
726 static void
728 {
729  mheap_t *h = mheap_header (v);
730 
731  /* Possibly delete preceeding free element also. */
732  if (e->prev_is_free)
733  {
734  e = mheap_prev_elt (e);
735  remove_free_elt2 (v, e);
736  }
737 
739  {
740  if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
742  _vec_len (v) = 0;
743  }
744  else
745  {
746  uword uo = mheap_elt_uoffset (v, e);
747  if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
748  mheap_vm_elt (v, MHEAP_VM_UNMAP, uo);
750  _vec_len (v) = uo;
751  }
752 }
753 
754 void
755 mheap_put (void *v, uword uoffset)
756 {
757  mheap_t *h;
758  uword n_user_data_bytes, bin;
759  mheap_elt_t *e, *n;
760  uword trace_uoffset, trace_n_user_data_bytes;
761  u64 cpu_times[2];
762 
763  cpu_times[0] = clib_cpu_time_now ();
764 
765  h = mheap_header (v);
766 
767  mheap_maybe_lock (v);
768 
769  if (h->flags & MHEAP_FLAG_VALIDATE)
770  mheap_validate (v);
771 
772  ASSERT (h->n_elts > 0);
773  h->n_elts--;
774  h->stats.n_puts += 1;
775 
776  e = mheap_elt_at_uoffset (v, uoffset);
777  n = mheap_next_elt (e);
778  n_user_data_bytes = mheap_elt_data_bytes (e);
779 
780  trace_uoffset = uoffset;
781  trace_n_user_data_bytes = n_user_data_bytes;
782 
783  bin = user_data_size_to_bin_index (n_user_data_bytes);
785  && bin < 255 && (h->flags & MHEAP_FLAG_SMALL_OBJECT_CACHE))
786  {
787  uoffset = mheap_put_small_object (h, bin, uoffset);
788  if (uoffset == 0)
789  goto done;
790 
791  e = mheap_elt_at_uoffset (v, uoffset);
792  n = mheap_next_elt (e);
793  n_user_data_bytes = mheap_elt_data_bytes (e);
794  }
795 
796  /* Assert that forward and back pointers are equal. */
797  if (e->n_user_data != n->prev_n_user_data)
798  os_panic ();
799 
800  /* Forward and backwards is_free must agree. */
801  if (e->is_free != n->prev_is_free)
802  os_panic ();
803 
804  /* Object was already freed. */
805  if (e->is_free)
806  os_panic ();
807 
808  /* Special case: delete last element in heap. */
810  free_last_elt (v, e);
811 
812  else
813  {
814  uword f0, f1, n_combine;
815 
816  f0 = uoffset;
817  f1 = f0 + n_user_data_bytes;
818  n_combine = 0;
819 
820  if (e->prev_is_free)
821  {
822  mheap_elt_t *p = mheap_prev_elt (e);
823  f0 = mheap_elt_uoffset (v, p);
824  remove_free_elt2 (v, p);
825  n_combine++;
826  }
827 
828  if (n->is_free)
829  {
830  mheap_elt_t *m = mheap_next_elt (n);
831  f1 = (void *) m - v;
832  remove_free_elt2 (v, n);
833  n_combine++;
834  }
835 
836  if (n_combine)
837  mheap_elt_set_size (v, f0, f1 - f0, /* is_free */ 1);
838  else
839  e->is_free = n->prev_is_free = 1;
840  set_free_elt (v, f0, f1 - f0);
841 
842  if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
843  mheap_vm_elt (v, MHEAP_VM_UNMAP, f0);
844  }
845 
846 done:
847  h = mheap_header (v);
848 
849  if (h->flags & MHEAP_FLAG_TRACE)
850  {
851  /* Recursion block for case when we are traceing main clib heap. */
852  h->flags &= ~MHEAP_FLAG_TRACE;
853 
854  mheap_put_trace (v, trace_uoffset, trace_n_user_data_bytes);
855 
856  h->flags |= MHEAP_FLAG_TRACE;
857  }
858 
859  if (h->flags & MHEAP_FLAG_VALIDATE)
860  mheap_validate (v);
861 
862  mheap_maybe_unlock (v);
863 
864  cpu_times[1] = clib_cpu_time_now ();
865  h->stats.n_clocks_put += cpu_times[1] - cpu_times[0];
866 }
867 
868 void *
870 {
871  mheap_t *h;
872  void *v;
873  uword size;
874 
875  if (!mheap_page_size)
876  mheap_page_size = clib_mem_get_page_size ();
877 
878  if (!memory)
879  {
880  /* No memory given, try to VM allocate some. */
881  memory = clib_mem_vm_alloc (memory_size);
882  if (!memory)
883  return 0;
884 
885  /* No memory region implies we have virtual memory. */
886  flags &= ~MHEAP_FLAG_DISABLE_VM;
887  }
888 
889  /* Make sure that given memory is page aligned. */
890  {
891  uword am, av, ah;
892 
893  am = pointer_to_uword (memory);
894  av = mheap_page_round (am);
895  v = uword_to_pointer (av, void *);
896  h = mheap_header (v);
897  ah = pointer_to_uword (h);
898  while (ah < am)
899  ah += mheap_page_size;
900 
901  h = uword_to_pointer (ah, void *);
902  v = mheap_vector (h);
903 
904  if (PREDICT_FALSE (memory + memory_size < v))
905  {
906  /*
907  * This will happen when the requested memory_size is too
908  * small to cope with the heap header and/or memory alignment.
909  */
910  clib_mem_vm_free (memory, memory_size);
911  return 0;
912  }
913 
914  size = memory + memory_size - v;
915  }
916 
917  /* VM map header so we can use memory. */
918  if (!(flags & MHEAP_FLAG_DISABLE_VM))
919  clib_mem_vm_map (h, sizeof (h[0]));
920 
921  /* Zero vector header: both heap header and vector length. */
922  memset (h, 0, sizeof (h[0]));
923  _vec_len (v) = 0;
924 
925  h->vm_alloc_offset_from_header = (void *) h - memory;
927 
928  h->max_size = size;
929  h->owner_cpu = ~0;
930 
931  /* Set flags based on those given less builtin-flags. */
932  h->flags |= (flags & ~MHEAP_FLAG_TRACE);
933 
934  /* Unmap remainder of heap until we will be ready to use it. */
935  if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
937  (clib_address_t) v, h->max_size);
938 
939  /* Initialize free list heads to empty. */
940  memset (h->first_free_elt_uoffset_by_bin, 0xFF,
941  sizeof (h->first_free_elt_uoffset_by_bin));
942 
943  return v;
944 }
945 
946 void *
948 {
949  uword flags = 0;
950 
951  if (memory != 0)
952  flags |= MHEAP_FLAG_DISABLE_VM;
953 
954 #ifdef CLIB_HAVE_VEC128
956 #endif
957 
958  return mheap_alloc_with_flags (memory, size, flags);
959 }
960 
961 void *
962 _mheap_free (void *v)
963 {
964  mheap_t *h = mheap_header (v);
965 
966  if (v)
968  h->vm_alloc_size);
969 
970  return 0;
971 }
972 
973 /* Call user's function with each object in heap. */
974 void
975 mheap_foreach (void *v,
976  uword (*func) (void *arg, void *v, void *elt_data,
977  uword elt_size), void *arg)
978 {
979  mheap_elt_t *e;
980  u8 *stack_heap, *clib_mem_mheap_save;
981  u8 tmp_heap_memory[16 * 1024];
982 
983  mheap_maybe_lock (v);
984 
985  if (vec_len (v) == 0)
986  goto done;
987 
988  clib_mem_mheap_save = 0;
989  stack_heap = 0;
990 
991  /* Allocate a new temporary heap on the stack.
992  This is so that our hash table & user's callback function can
993  themselves allocate memory somewhere without getting in the way
994  of the heap we are looking at. */
995  if (v == clib_mem_get_heap ())
996  {
997  stack_heap = mheap_alloc (tmp_heap_memory, sizeof (tmp_heap_memory));
998  clib_mem_mheap_save = v;
999  clib_mem_set_heap (stack_heap);
1000  }
1001 
1002  for (e = v;
1004  {
1005  void *p = mheap_elt_data (v, e);
1006  if (e->is_free)
1007  continue;
1008  if ((*func) (arg, v, p, mheap_elt_data_bytes (e)))
1009  break;
1010  }
1011 
1012  /* Restore main CLIB heap. */
1013  if (clib_mem_mheap_save)
1014  clib_mem_set_heap (clib_mem_mheap_save);
1015 
1016 done:
1017  mheap_maybe_unlock (v);
1018 }
1019 
1020 /* Bytes in mheap header overhead not including data bytes. */
1023 {
1024  mheap_t *h = mheap_header (v);
1025  return v ? sizeof (h[0]) + h->n_elts * sizeof (mheap_elt_t) : 0;
1026 }
1027 
1028 /* Total number of bytes including both data and overhead. */
1029 uword
1030 mheap_bytes (void *v)
1031 {
1032  return mheap_bytes_overhead (v) + vec_bytes (v);
1033 }
1034 
1035 static void
1037 {
1038  mheap_t *h = mheap_header (v);
1039  uword used = 0, free = 0, free_vm_unmapped = 0;
1040 
1041  if (vec_len (v) > 0)
1042  {
1043  mheap_elt_t *e;
1044 
1045  for (e = v;
1047  e = mheap_next_elt (e))
1048  {
1050  if (e->is_free)
1051  {
1052  free += size;
1053  if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
1054  free_vm_unmapped +=
1056  }
1057  else
1058  used += size;
1059  }
1060  }
1061 
1062  usage->object_count = mheap_elts (v);
1063  usage->bytes_total = mheap_bytes (v);
1064  usage->bytes_overhead = mheap_bytes_overhead (v);
1065  usage->bytes_max = mheap_max_size (v);
1066  usage->bytes_used = used;
1067  usage->bytes_free = free;
1068  usage->bytes_free_reclaimed = free_vm_unmapped;
1069 }
1070 
1071 void
1073 {
1074  mheap_maybe_lock (v);
1075  mheap_usage_no_lock (v, usage);
1076  mheap_maybe_unlock (v);
1077 }
1078 
1079 static u8 *
1080 format_mheap_byte_count (u8 * s, va_list * va)
1081 {
1082  uword n_bytes = va_arg (*va, uword);
1083  if (n_bytes < 1024)
1084  return format (s, "%wd", n_bytes);
1085  else
1086  return format (s, "%wdk", n_bytes / 1024);
1087 }
1088 
1089 /* Returns first corrupt heap element. */
1090 static mheap_elt_t *
1092 {
1093  mheap_elt_t *e, *n;
1094 
1095  if (vec_len (v) == 0)
1096  return 0;
1097 
1098  e = v;
1099  while (1)
1100  {
1102  break;
1103 
1104  n = mheap_next_elt (e);
1105 
1106  if (e->n_user_data != n->prev_n_user_data)
1107  return e;
1108 
1109  if (e->is_free != n->prev_is_free)
1110  return e;
1111 
1112  e = n;
1113  }
1114 
1115  return 0;
1116 }
1117 
1118 static u8 *
1119 format_mheap_stats (u8 * s, va_list * va)
1120 {
1121  mheap_t *h = va_arg (*va, mheap_t *);
1122  mheap_stats_t *st = &h->stats;
1123  uword indent = format_get_indent (s);
1124 
1125  s =
1126  format (s,
1127  "alloc. from small object cache: %Ld hits %Ld attempts (%.2f%%) replacements %d",
1130  0 ? 100. * (f64) st->n_small_object_cache_hits /
1131  (f64) st->n_small_object_cache_attempts : 0.),
1133 
1134  s =
1135  format (s,
1136  "\n%Ualloc. from free-list: %Ld attempts, %Ld hits (%.2f%%), %Ld considered (per-attempt %.2f)",
1140  0 ? 100. * (f64) st->free_list.n_objects_found /
1141  (f64) st->free_list.n_search_attempts : 0.),
1144  0 ? (f64) st->free_list.n_objects_searched /
1145  (f64) st->free_list.n_search_attempts : 0.));
1146 
1147  s = format (s, "\n%Ualloc. from vector-expand: %Ld",
1148  format_white_space, indent, st->n_vector_expands);
1149 
1150  s = format (s, "\n%Uallocs: %Ld %.2f clocks/call",
1151  format_white_space, indent,
1152  st->n_gets, (f64) st->n_clocks_get / (f64) st->n_gets);
1153 
1154  s = format (s, "\n%Ufrees: %Ld %.2f clocks/call",
1155  format_white_space, indent,
1156  st->n_puts, (f64) st->n_clocks_put / (f64) st->n_puts);
1157 
1158  return s;
1159 }
1160 
1161 u8 *
1162 format_mheap (u8 * s, va_list * va)
1163 {
1164  void *v = va_arg (*va, u8 *);
1165  int verbose = va_arg (*va, int);
1166 
1167  mheap_t *h;
1168  uword i, size, indent;
1170  mheap_elt_t *first_corrupt;
1171 
1172  mheap_maybe_lock (v);
1173 
1174  h = mheap_header (v);
1175 
1176  mheap_usage_no_lock (v, &usage);
1177 
1178  indent = format_get_indent (s);
1179 
1180  s =
1181  format (s,
1182  "%d objects, %U of %U used, %U free, %U reclaimed, %U overhead",
1188 
1189  if (usage.bytes_max != ~0)
1190  s = format (s, ", %U capacity", format_mheap_byte_count, usage.bytes_max);
1191 
1192  /* Show histogram of sizes. */
1193  if (verbose > 1)
1194  {
1195  uword hist[MHEAP_N_BINS];
1196  mheap_elt_t *e;
1197  uword i, n_hist;
1198 
1199  memset (hist, 0, sizeof (hist));
1200 
1201  n_hist = 0;
1202  for (e = v;
1204  e = mheap_next_elt (e))
1205  {
1206  uword n_user_data_bytes = mheap_elt_data_bytes (e);
1207  uword bin = user_data_size_to_bin_index (n_user_data_bytes);
1208  if (!e->is_free)
1209  {
1210  hist[bin] += 1;
1211  n_hist += 1;
1212  }
1213  }
1214 
1215  s = format (s, "\n%U%=12s%=12s%=16s",
1216  format_white_space, indent + 2,
1217  "Size", "Count", "Fraction");
1218 
1219  for (i = 0; i < ARRAY_LEN (hist); i++)
1220  {
1221  if (hist[i] == 0)
1222  continue;
1223  s = format (s, "\n%U%12d%12wd%16.4f",
1224  format_white_space, indent + 2,
1226  i * MHEAP_USER_DATA_WORD_BYTES, hist[i],
1227  (f64) hist[i] / (f64) n_hist);
1228  }
1229  }
1230 
1231  if (verbose)
1232  s = format (s, "\n%U%U",
1233  format_white_space, indent + 2, format_mheap_stats, h);
1234 
1235  if ((h->flags & MHEAP_FLAG_TRACE) && vec_len (h->trace_main.traces) > 0)
1236  {
1237  /* Make a copy of traces since we'll be sorting them. */
1238  mheap_trace_t *t, *traces_copy;
1239  uword indent, total_objects_traced;
1240 
1241  traces_copy = vec_dup (h->trace_main.traces);
1242  qsort (traces_copy, vec_len (traces_copy), sizeof (traces_copy[0]),
1244 
1245  total_objects_traced = 0;
1246  s = format (s, "\n");
1247  vec_foreach (t, traces_copy)
1248  {
1249  /* Skip over free elements. */
1250  if (t->n_allocations == 0)
1251  continue;
1252 
1253  total_objects_traced += t->n_allocations;
1254 
1255  /* When not verbose only report allocations of more than 1k. */
1256  if (!verbose && t->n_bytes < 1024)
1257  continue;
1258 
1259  if (t == traces_copy)
1260  s = format (s, "%=9s%=9s %=10s Traceback\n", "Bytes", "Count",
1261  "Sample");
1262  s = format (s, "%9d%9d %p", t->n_bytes, t->n_allocations,
1263  t->offset + v);
1264  indent = format_get_indent (s);
1265  for (i = 0; i < ARRAY_LEN (t->callers) && t->callers[i]; i++)
1266  {
1267  if (i > 0)
1268  s = format (s, "%U", format_white_space, indent);
1269 #ifdef CLIB_UNIX
1270  s =
1272  t->callers[i]);
1273 #else
1274  s = format (s, " %p\n", t->callers[i]);
1275 #endif
1276  }
1277  }
1278 
1279  s = format (s, "%d total traced objects\n", total_objects_traced);
1280 
1281  vec_free (traces_copy);
1282  }
1283 
1284  first_corrupt = mheap_first_corrupt (v);
1285  if (first_corrupt)
1286  {
1287  size = mheap_elt_data_bytes (first_corrupt);
1288  s = format (s, "\n first corrupt object: %p, size %wd\n %U",
1289  first_corrupt, size, format_hex_bytes, first_corrupt, size);
1290  }
1291 
1292  /* FIXME. This output could be wrong in the unlikely case that format
1293  uses the same mheap as we are currently inspecting. */
1294  if (verbose > 1)
1295  {
1296  mheap_elt_t *e;
1297  uword i, o;
1298 
1299  s = format (s, "\n");
1300 
1301  e = mheap_elt_at_uoffset (v, 0);
1302  i = 0;
1303  while (1)
1304  {
1305  if ((i % 8) == 0)
1306  s = format (s, "%8d: ", i);
1307 
1308  o = mheap_elt_uoffset (v, e);
1309 
1310  if (e->is_free)
1311  s = format (s, "(%8d) ", o);
1312  else
1313  s = format (s, " %8d ", o);
1314 
1315  if ((i % 8) == 7 || (i + 1) >= h->n_elts)
1316  s = format (s, "\n");
1317  }
1318  }
1319 
1320  mheap_maybe_unlock (v);
1321 
1322  return s;
1323 }
1324 
1325 void
1326 dmh (void *v)
1327 {
1328  fformat (stderr, "%U", format_mheap, v, 1);
1329 }
1330 
1331 static void
1333 {
1334  os_panic ();
1335 }
1336 
1337 void
1339 {
1340  mheap_t *h = mheap_header (v);
1341  uword i, s;
1342 
1343  uword elt_count, elt_size;
1344  uword free_count_from_free_lists, free_size_from_free_lists;
1345  uword small_elt_free_count, small_elt_free_size;
1346 
1347 #define CHECK(x) if (! (x)) { mheap_validate_breakpoint (); os_panic (); }
1348 
1349  if (vec_len (v) == 0)
1350  return;
1351 
1352  mheap_maybe_lock (v);
1353 
1354  /* Validate number of elements and size. */
1355  free_size_from_free_lists = free_count_from_free_lists = 0;
1356  for (i = 0; i < ARRAY_LEN (h->first_free_elt_uoffset_by_bin); i++)
1357  {
1358  mheap_elt_t *e, *n;
1359  uword is_first;
1360 
1362  ==
1363  ((h->non_empty_free_elt_heads[i /
1364  BITS (uword)] & ((uword) 1 <<
1365  (uword) (i %
1366  BITS
1367  (uword))))
1368  != 0));
1369 
1371  continue;
1372 
1374  is_first = 1;
1375  while (1)
1376  {
1377  uword s;
1378 
1379  n = mheap_next_elt (e);
1380 
1381  /* Object must be marked free. */
1382  CHECK (e->is_free);
1383 
1384  /* Next object's previous free bit must also be set. */
1385  CHECK (n->prev_is_free);
1386 
1387  if (is_first)
1388  CHECK (e->free_elt.prev_uoffset == MHEAP_GROUNDED);
1389  is_first = 0;
1390 
1391  s = mheap_elt_data_bytes (e);
1393 
1394  free_count_from_free_lists += 1;
1395  free_size_from_free_lists += s;
1396 
1397  if (e->free_elt.next_uoffset == MHEAP_GROUNDED)
1398  break;
1399 
1400  n = mheap_elt_at_uoffset (v, e->free_elt.next_uoffset);
1401 
1402  /* Check free element linkages. */
1403  CHECK (n->free_elt.prev_uoffset == mheap_elt_uoffset (v, e));
1404 
1405  e = n;
1406  }
1407  }
1408 
1409  /* Go through small object cache. */
1410  small_elt_free_count = small_elt_free_size = 0;
1411  for (i = 0; i < ARRAY_LEN (h->small_object_cache.bins.as_u8); i++)
1412  {
1413  if (h->small_object_cache.bins.as_u8[i] != 0)
1414  {
1415  mheap_elt_t *e;
1416  uword b = h->small_object_cache.bins.as_u8[i] - 1;
1418  uword s;
1419 
1420  e = mheap_elt_at_uoffset (v, o);
1421 
1422  /* Object must be allocated. */
1423  CHECK (!e->is_free);
1424 
1425  s = mheap_elt_data_bytes (e);
1427 
1428  small_elt_free_count += 1;
1429  small_elt_free_size += s;
1430  }
1431  }
1432 
1433  {
1434  mheap_elt_t *e, *n;
1435  uword elt_free_size, elt_free_count;
1436 
1437  elt_count = elt_size = elt_free_size = elt_free_count = 0;
1438  for (e = v; e->n_user_data != MHEAP_N_USER_DATA_INVALID; e = n)
1439  {
1441  CHECK (e->prev_n_user_data * sizeof (e->user_data[0]) >=
1443 
1444  CHECK (e->n_user_data * sizeof (e->user_data[0]) >=
1446 
1447  n = mheap_next_elt (e);
1448 
1449  CHECK (e->is_free == n->prev_is_free);
1450 
1451  elt_count++;
1452  s = mheap_elt_data_bytes (e);
1453  elt_size += s;
1454 
1455  if (e->is_free)
1456  {
1457  elt_free_count++;
1458  elt_free_size += s;
1459  }
1460 
1461  /* Consecutive free objects should have been combined. */
1462  CHECK (!(e->prev_is_free && n->prev_is_free));
1463  }
1464 
1465  CHECK (free_count_from_free_lists == elt_free_count);
1466  CHECK (free_size_from_free_lists == elt_free_size);
1467  CHECK (elt_count == h->n_elts + elt_free_count + small_elt_free_count);
1468  CHECK (elt_size + (elt_count + 1) * MHEAP_ELT_OVERHEAD_BYTES ==
1469  vec_len (v));
1470  }
1471 
1472  {
1473  mheap_elt_t *e, *n;
1474 
1475  for (e = v; e->n_user_data == MHEAP_N_USER_DATA_INVALID; e = n)
1476  {
1477  n = mheap_next_elt (e);
1478  CHECK (e->n_user_data == n->prev_n_user_data);
1479  }
1480  }
1481 
1482 #undef CHECK
1483 
1484  mheap_maybe_unlock (v);
1485 
1486  h->validate_serial += 1;
1487 }
1488 
1489 static void
1491 {
1492  mheap_t *h;
1493  mheap_trace_main_t *tm;
1494  mheap_trace_t *t;
1495  uword i, n_callers, trace_index, *p;
1497 
1498  /* Spurious Coverity warnings be gone. */
1499  memset (&trace, 0, sizeof (trace));
1500 
1501  n_callers = clib_backtrace (trace.callers, ARRAY_LEN (trace.callers),
1502  /* Skip mheap_get_aligned's frame */ 1);
1503  if (n_callers == 0)
1504  return;
1505 
1506  for (i = n_callers; i < ARRAY_LEN (trace.callers); i++)
1507  trace.callers[i] = 0;
1508 
1509  h = mheap_header (v);
1510  tm = &h->trace_main;
1511 
1512  if (!tm->trace_by_callers)
1513  tm->trace_by_callers =
1514  hash_create_mem (0, sizeof (trace.callers), sizeof (uword));
1515 
1516  p = hash_get_mem (tm->trace_by_callers, &trace.callers);
1517  if (p)
1518  {
1519  trace_index = p[0];
1520  t = tm->traces + trace_index;
1521  }
1522  else
1523  {
1524  i = vec_len (tm->trace_free_list);
1525  if (i > 0)
1526  {
1527  trace_index = tm->trace_free_list[i - 1];
1528  _vec_len (tm->trace_free_list) = i - 1;
1529  }
1530  else
1531  {
1532  mheap_trace_t *old_start = tm->traces;
1533  mheap_trace_t *old_end = vec_end (tm->traces);
1534 
1535  vec_add2 (tm->traces, t, 1);
1536 
1537  if (tm->traces != old_start)
1538  {
1539  hash_pair_t *p;
1540  mheap_trace_t *q;
1541  /* *INDENT-OFF* */
1543  ({
1544  q = uword_to_pointer (p->key, mheap_trace_t *);
1545  ASSERT (q >= old_start && q < old_end);
1546  p->key = pointer_to_uword (tm->traces + (q - old_start));
1547  }));
1548  /* *INDENT-ON* */
1549  }
1550  trace_index = t - tm->traces;
1551  }
1552 
1553  t = tm->traces + trace_index;
1554  t[0] = trace;
1555  t->n_allocations = 0;
1556  t->n_bytes = 0;
1557  hash_set_mem (tm->trace_by_callers, t->callers, trace_index);
1558  }
1559 
1560  t->n_allocations += 1;
1561  t->n_bytes += size;
1562  t->offset = offset; /* keep a sample to autopsy */
1563  hash_set (tm->trace_index_by_offset, offset, t - tm->traces);
1564 }
1565 
1566 static void
1568 {
1569  mheap_t *h;
1570  mheap_trace_main_t *tm;
1571  mheap_trace_t *t;
1572  uword trace_index, *p;
1573 
1574  h = mheap_header (v);
1575  tm = &h->trace_main;
1576  p = hash_get (tm->trace_index_by_offset, offset);
1577  if (!p)
1578  return;
1579 
1580  trace_index = p[0];
1581  hash_unset (tm->trace_index_by_offset, offset);
1582  ASSERT (trace_index < vec_len (tm->traces));
1583 
1584  t = tm->traces + trace_index;
1585  ASSERT (t->n_allocations > 0);
1586  ASSERT (t->n_bytes >= size);
1587  t->n_allocations -= 1;
1588  t->n_bytes -= size;
1589  if (t->n_allocations == 0)
1590  {
1592  vec_add1 (tm->trace_free_list, trace_index);
1593  memset (t, 0, sizeof (t[0]));
1594  }
1595 }
1596 
1597 static int
1598 mheap_trace_sort (const void *_t1, const void *_t2)
1599 {
1600  const mheap_trace_t *t1 = _t1;
1601  const mheap_trace_t *t2 = _t2;
1602  word cmp;
1603 
1604  cmp = (word) t2->n_bytes - (word) t1->n_bytes;
1605  if (!cmp)
1606  cmp = (word) t2->n_allocations - (word) t1->n_allocations;
1607  return cmp;
1608 }
1609 
1610 always_inline void
1612 {
1613  vec_free (tm->traces);
1614  vec_free (tm->trace_free_list);
1617 }
1618 
1619 void
1620 mheap_trace (void *v, int enable)
1621 {
1622  mheap_t *h;
1623 
1624  h = mheap_header (v);
1625 
1626  if (enable)
1627  {
1628  h->flags |= MHEAP_FLAG_TRACE;
1629  }
1630  else
1631  {
1633  h->flags &= ~MHEAP_FLAG_TRACE;
1634  }
1635 }
1636 
1637 /*
1638  * fd.io coding-style-patch-verification: ON
1639  *
1640  * Local Variables:
1641  * eval: (c-set-style "gnu")
1642  * End:
1643  */
#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:249
struct mheap_elt_t::@14::@16 free_elt
uword bytes_total
Definition: mem.h:245
#define hash_set(h, key, value)
Definition: hash.h:254
uword bytes_free
Definition: mem.h:245
sll srl srl sll sra u16x4 i
Definition: vector_sse2.h:337
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:1173
static u8 * format_mheap_byte_count(u8 *s, va_list *va)
Definition: mheap.c:1080
uword offsets[BITS(uword)]
uword vm_alloc_offset_from_header
uword callers[12]
uword bytes_free_reclaimed
Definition: mem.h:252
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:947
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:174
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:522
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:561
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
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:1567
#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:245
u8 * format_mheap(u8 *s, va_list *va)
Definition: mheap.c:1162
static uword min_log2(uword x)
Definition: clib.h:189
#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:241
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:257
static uword format_get_indent(u8 *s)
Definition: format.h:72
#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:1072
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:1022
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:1611
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:637
#define hash_get(h, key)
Definition: hash.h:248
#define hash_unset_mem(h, key)
Definition: hash.h:280
static void mheap_maybe_lock(void *v)
Definition: mheap.c:54
#define v
Definition: acl.c:320
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:374
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
word fformat(FILE *f, char *fmt,...)
Definition: format.c:453
void dmh(void *v)
Definition: mheap.c:1326
#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:1332
#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:260
static void free_last_elt(void *v, mheap_elt_t *e)
Definition: mheap.c:727
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:340
static uword mheap_elt_uoffset(void *v, mheap_elt_t *e)
static void * clib_mem_set_heap(void *heap)
Definition: mem.h:223
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
u64 memory_size
Definition: vhost-user.h:76
mheap_small_object_cache_t small_object_cache
static uword max_pow2(uword x)
Definition: clib.h:263
#define ARRAY_LEN(x)
Definition: clib.h:59
static uword round_pow2(uword x, uword pow2)
Definition: clib.h:278
#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:217
void * mheap_alloc_with_flags(void *memory, uword memory_size, uword flags)
Definition: mheap.c:869
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:1620
#define ASSERT(truth)
unsigned int u32
Definition: types.h:88
volatile u32 owner_cpu
#define MHEAP_GROUNDED
uword vm_alloc_size
u64 size
Definition: vhost-user.h:75
static void * mheap_elt_data(void *v, mheap_elt_t *e)
#define MHEAP_FLAG_VALIDATE
#define clib_max(x, y)
Definition: clib.h:325
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:1091
#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:1030
template key/value backing page structure
Definition: bihash_doc.h:44
#define MHEAP_HAVE_SMALL_OBJECT_CACHE
#define u8x16_splat(i)
Definition: vector_neon.h:22
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:755
static int mheap_trace_sort(const void *t1, const void *t2)
Definition: mheap.c:1598
#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)
Iterate over hash pairs.
Definition: hash.h:349
static uword max_log2(uword x)
Definition: clib.h:228
#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:1490
static void * clib_mem_vm_map(void *addr, uword size)
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:1119
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: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:1338
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:975
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:1036
#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]