FD.io VPP  v20.09-64-g4f7b92f0a
Vector Packet Processing
heap.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/cache.h> /* for CLIB_CACHE_LINE_BYTES */
39 #include <vppinfra/mem.h>
40 #include <vppinfra/hash.h>
41 #include <vppinfra/vec.h>
42 #include <vppinfra/heap.h>
43 #include <vppinfra/error.h>
44 
47 {
48  ASSERT (i < vec_len (h->elts));
49  return h->elts + i;
50 }
51 
54 {
55  return elt_at (h, h->tail);
56 }
57 
60 {
61  return elt_at (h, h->head);
62 }
63 
64 /* Objects sizes are binned into N_BINS bins.
65  Objects with size <= SMALL_BINS have their own bins.
66  Larger objects are grouped together in power or 2 sized
67  bins.
68 
69  Sizes are in units of elt_bytes bytes. */
70 
71 /* Convert size to bin. */
74 {
75  uword bin;
76 
77  ASSERT (size > 0);
78 
79  if (size <= HEAP_SMALL_BINS)
80  {
81  bin = size - 1;
82  if (size == 0)
83  bin = 0;
84  }
85  else
86  {
87  bin = HEAP_SMALL_BINS + max_log2 (size) - (HEAP_LOG2_SMALL_BINS + 1);
88  if (bin >= HEAP_N_BINS)
89  bin = HEAP_N_BINS - 1;
90  }
91 
92  return bin;
93 }
94 
95 /* Convert bin to size. */
96 always_inline __attribute__ ((unused))
98 {
99  uword size;
100 
101  if (bin <= HEAP_SMALL_BINS - 1)
102  size = bin + 1;
103  else
104  size = (uword) 1 << ((bin - HEAP_SMALL_BINS) + HEAP_LOG2_SMALL_BINS + 1);
105 
106  return size;
107 }
108 
109 static void
111 {
112  heap_elt_t *l = vec_end (h->elts) - 1;
113 
114  ASSERT (e >= h->elts && e <= l);
115 
116  /* Update doubly linked pointers. */
117  {
118  heap_elt_t *p = heap_prev (e);
119  heap_elt_t *n = heap_next (e);
120 
121  if (p == e)
122  {
123  n->prev = 0;
124  h->head = n - h->elts;
125  }
126  else if (n == e)
127  {
128  p->next = 0;
129  h->tail = p - h->elts;
130  }
131  else
132  {
133  p->next = n - p;
134  n->prev = p - n;
135  }
136  }
137 
138  /* Add to index free list or delete from end. */
139  if (e < l)
140  vec_add1 (h->free_elts, e - h->elts);
141  else
142  _vec_len (h->elts)--;
143 }
144 
145 /*
146  Before: P ... E
147  After : P ... NEW ... E
148 */
149 always_inline void
151 {
152  heap_elt_t *p = heap_prev (e);
153 
154  if (p == e)
155  {
156  new->prev = 0;
157  new->next = e - new;
158  p->prev = new - p;
159  h->head = new - h->elts;
160  }
161  else
162  {
163  new->prev = p - new;
164  new->next = e - new;
165  e->prev = new - e;
166  p->next = new - p;
167  }
168 }
169 
170 /*
171  Before: E ... N
172  After : E ... NEW ... N
173 */
174 always_inline void
176 {
177  heap_elt_t *n = heap_next (e);
178 
179  if (n == e)
180  {
181  new->next = 0;
182  new->prev = e - new;
183  e->next = new - e;
184  h->tail = new - h->elts;
185  }
186  else
187  {
188  new->prev = e - new;
189  new->next = n - new;
190  e->next = new - e;
191  n->prev = new - n;
192  }
193 }
194 
197 {
198  heap_elt_t *e;
199  uword l;
200  if ((l = vec_len (h->free_elts)) > 0)
201  {
202  e = elt_at (h, h->free_elts[l - 1]);
203  _vec_len (h->free_elts) -= 1;
204  }
205  else
206  vec_add2 (h->elts, e, 1);
207  return e;
208 }
209 
210 /* Return pointer to object at given offset.
211  Used to write free list index of free objects. */
213 elt_data (void *v, heap_elt_t * e)
214 {
215  heap_header_t *h = heap_header (v);
216  return v + heap_offset (e) * h->elt_bytes;
217 }
218 
219 always_inline void
220 set_free_elt (void *v, heap_elt_t * e, uword fi)
221 {
222  heap_header_t *h = heap_header (v);
223 
225  if (h->elt_bytes >= sizeof (u32))
226  {
227  *elt_data (v, e) = fi;
228  }
229  else
230  {
231  /* For elt_bytes < 4 we must store free index in separate
232  vector. */
233  uword elt_index = e - h->elts;
234  vec_validate (h->small_free_elt_free_index, elt_index);
235  h->small_free_elt_free_index[elt_index] = fi;
236  }
237 }
238 
240 get_free_elt (void *v, heap_elt_t * e, uword * bin_result)
241 {
242  heap_header_t *h = heap_header (v);
243  uword fb, fi;
244 
245  ASSERT (heap_is_free (e));
246  fb = size_to_bin (heap_elt_size (v, e));
247 
248  if (h->elt_bytes >= sizeof (u32))
249  {
250  fi = *elt_data (v, e);
251  }
252  else
253  {
254  uword elt_index = e - h->elts;
255  fi = vec_elt (h->small_free_elt_free_index, elt_index);
256  }
257 
258  *bin_result = fb;
259  return fi;
260 }
261 
262 always_inline void
264 {
265  heap_header_t *h = heap_header (v);
266  uword l;
267 
268  ASSERT (b < vec_len (h->free_lists));
269  ASSERT (i < vec_len (h->free_lists[b]));
270 
271  l = vec_len (h->free_lists[b]);
272 
273  if (i < l - 1)
274  {
275  uword t = h->free_lists[b][l - 1];
276  h->free_lists[b][i] = t;
277  set_free_elt (v, elt_at (h, t), i);
278  }
279  _vec_len (h->free_lists[b]) = l - 1;
280 }
281 
282 static heap_elt_t *
284 {
285  heap_header_t *h = heap_header (v);
286  heap_elt_t *f, *u;
287  uword b, fb, f_size, f_index;
288  word s, l;
289 
290  if (!v)
291  return 0;
292 
293  /* Search free lists for bins >= given size. */
294  for (b = size_to_bin (size); b < vec_len (h->free_lists); b++)
295  if ((l = vec_len (h->free_lists[b])) > 0)
296  {
297  /* Find an object that is large enough.
298  Search list in reverse so that more recently freed objects will be
299  allocated again sooner. */
300  u8 found = 0;
301  do
302  {
303  l--;
304  f_index = h->free_lists[b][l];
305  f = elt_at (h, f_index);
306  f_size = heap_elt_size (v, f);
307  if ((s = f_size - size) >= 0)
308  {
309  found = 1;
310  break;
311  }
312  }
313  while (l > 0);
314 
315  /* If we fail to find a large enough object, try the next larger size. */
316  if (found == 0)
317  continue;
318 
319  ASSERT (heap_is_free (f));
320 
321  /* Link in used object (u) after free object (f). */
322  if (s == 0)
323  {
324  u = f;
325  fb = HEAP_N_BINS;
326  }
327  else
328  {
329  u = elt_new (h);
330  f = elt_at (h, f_index);
331  elt_insert_after (h, f, u);
332  fb = size_to_bin (s);
333  }
334 
335  u->offset = heap_offset (f) + s;
336 
337  if (fb != b)
338  {
339  if (fb < HEAP_N_BINS)
340  {
341  uword i;
342  vec_validate (h->free_lists, fb);
343  i = vec_len (h->free_lists[fb]);
344  vec_add1 (h->free_lists[fb], f - h->elts);
345  set_free_elt (v, f, i);
346  }
347 
348  remove_free_block (v, b, l);
349  }
350 
351  return u;
352  }
353 
354  return 0;
355 }
356 
357 static void combine_free_blocks (void *v, heap_elt_t * e0, heap_elt_t * e1);
358 
359 static inline void
360 dealloc_elt (void *v, heap_elt_t * e)
361 {
362  heap_header_t *h = heap_header (v);
363  uword b, l;
364  heap_elt_t *n, *p;
365 
366  b = size_to_bin (heap_elt_size (v, e));
367  vec_validate (h->free_lists, b);
368  l = vec_len (h->free_lists[b]);
369  vec_add1 (h->free_lists[b], e - h->elts);
370  set_free_elt (v, e, l);
371 
372  /* See if we can combine the block we just freed with neighboring free blocks. */
373  p = heap_prev (e);
374  if (!heap_is_free (p))
375  p = e;
376 
377  n = heap_next (e);
378  if (!heap_is_free (n))
379  n = e;
380 
381  if (p != n)
382  combine_free_blocks (v, p, n);
383 }
384 
385 void *
386 _heap_alloc (void *v,
387  uword size,
388  uword align,
389  uword elt_bytes, uword * offset_return, uword * handle_return)
390 {
391  uword offset = 0, align_size;
392  heap_header_t *h;
393  heap_elt_t *e;
394 
395  if (size == 0)
396  goto error;
397 
398  /* Round up alignment to power of 2. */
399  if (align <= 1)
400  {
401  align = 0;
402  align_size = size;
403  }
404  else
405  {
406  align = max_pow2 (align);
407  align_size = size + align - 1;
408  }
409 
410  e = search_free_list (v, align_size);
411 
412  /* If nothing found on free list, allocate object from end of vector. */
413  if (!e)
414  {
415  uword max_len;
416 
417  offset = vec_len (v);
418  max_len = heap_get_max_len (v);
419 
420  if (max_len && offset + align_size > max_len)
421  goto error;
422 
423  h = heap_header (v);
424  if (!v || !(h->flags & HEAP_IS_STATIC))
425  v = _vec_resize (v,
426  align_size,
427  (offset + align_size) * elt_bytes,
428  sizeof (h[0]), HEAP_DATA_ALIGN);
429  else
430  _vec_len (v) += align_size;
431 
432  if (offset == 0)
433  {
434  h = heap_header (v);
435  h->elt_bytes = elt_bytes;
436  }
437  }
438 
439  h = heap_header (v);
440 
441  /* Add new element to doubly linked chain of elements. */
442  if (!e)
443  {
444  e = elt_new (h);
445  e->offset = offset;
446  elt_insert_after (h, last (h), e);
447  }
448 
449  if (align > 0)
450  {
451  uword e_index;
452  uword new_offset, old_offset;
453 
454  old_offset = e->offset;
455  new_offset = (old_offset + align - 1) & ~(align - 1);
456  e->offset = new_offset;
457  e_index = e - h->elts;
458 
459  /* Free fragments before and after aligned object. */
460  if (new_offset > old_offset)
461  {
462  heap_elt_t *before_e = elt_new (h);
463  before_e->offset = old_offset;
464  elt_insert_before (h, h->elts + e_index, before_e);
465  dealloc_elt (v, before_e);
466  }
467 
468  if (new_offset + size < old_offset + align_size)
469  {
470  heap_elt_t *after_e = elt_new (h);
471  after_e->offset = new_offset + size;
472  elt_insert_after (h, h->elts + e_index, after_e);
473  dealloc_elt (v, after_e);
474  }
475 
476  e = h->elts + e_index;
477  }
478 
479  h->used_count++;
480 
481  /* Keep track of used elements when debugging.
482  This allows deallocation to check that passed objects are valid. */
483  if (CLIB_DEBUG > 0)
484  {
485  uword handle = e - h->elts;
486  ASSERT (!clib_bitmap_get (h->used_elt_bitmap, handle));
487  h->used_elt_bitmap = clib_bitmap_ori (h->used_elt_bitmap, handle);
488  }
489 
490  *offset_return = e->offset;
491  *handle_return = e - h->elts;
492  return v;
493 
494 error:
495  *offset_return = *handle_return = ~0;
496  return v;
497 }
498 
499 void
500 heap_dealloc (void *v, uword handle)
501 {
502  heap_header_t *h = heap_header (v);
503  heap_elt_t *e;
504 
505  ASSERT (handle < vec_len (h->elts));
506 
507  /* For debugging we keep track of indices for valid objects.
508  We make sure user is not trying to free object with an invalid index. */
509  if (CLIB_DEBUG > 0)
510  {
511  ASSERT (clib_bitmap_get (h->used_elt_bitmap, handle));
512  h->used_elt_bitmap = clib_bitmap_andnoti (h->used_elt_bitmap, handle);
513  }
514 
515  h->used_count--;
516 
517  e = h->elts + handle;
518  ASSERT (!heap_is_free (e));
519 
520  dealloc_elt (v, e);
521 }
522 
523 /* While freeing objects at INDEX we noticed free blocks i0 <= index and
524  i1 >= index. We combine these two or three blocks into one big free block. */
525 static void
527 {
528  heap_header_t *h = heap_header (v);
529  uword total_size, i, b, tb, ti, i_last, g_offset;
530  heap_elt_t *e;
531 
532  struct
533  {
534  u32 index;
535  u32 bin;
536  u32 bin_index;
537  } f[3], g;
538 
539  /* Compute total size of free objects i0 through i1. */
540  total_size = 0;
541  for (i = 0, e = e0; 1; e = heap_next (e), i++)
542  {
543  ASSERT (i < ARRAY_LEN (f));
544 
545  ti = get_free_elt (v, e, &tb);
546 
547  ASSERT (tb < vec_len (h->free_lists));
548  ASSERT (ti < vec_len (h->free_lists[tb]));
549 
550  f[i].index = h->free_lists[tb][ti];
551  f[i].bin = tb;
552  f[i].bin_index = ti;
553 
554  total_size += heap_elt_size (v, elt_at (h, f[i].index));
555 
556  if (e == e1)
557  {
558  i_last = i;
559  break;
560  }
561  }
562 
563  /* Compute combined bin. See if all objects can be
564  combined into existing bin. */
565  b = size_to_bin (total_size);
566  g.index = g.bin_index = 0;
567  for (i = 0; i <= i_last; i++)
568  if (b == f[i].bin)
569  {
570  g = f[i];
571  break;
572  }
573 
574  /* Make sure we found a bin. */
575  if (i > i_last)
576  {
577  g.index = elt_new (h) - h->elts;
578  vec_validate (h->free_lists, b);
579  g.bin_index = vec_len (h->free_lists[b]);
580  vec_add1 (h->free_lists[b], g.index);
581  elt_insert_before (h, elt_at (h, f[0].index), elt_at (h, g.index));
582  }
583 
584  g_offset = elt_at (h, f[0].index)->offset;
585 
586  /* Delete unused bins. */
587  for (i = 0; i <= i_last; i++)
588  if (g.index != f[i].index)
589  {
590  ti = get_free_elt (v, elt_at (h, f[i].index), &tb);
591  remove_free_block (v, tb, ti);
592  elt_delete (h, elt_at (h, f[i].index));
593  }
594 
595  /* Initialize new element. */
596  elt_at (h, g.index)->offset = g_offset;
597  set_free_elt (v, elt_at (h, g.index), g.bin_index);
598 }
599 
600 uword
601 heap_len (void *v, word handle)
602 {
603  heap_header_t *h = heap_header (v);
604 
605  if (CLIB_DEBUG > 0)
606  ASSERT (clib_bitmap_get (h->used_elt_bitmap, handle));
607  return heap_elt_size (v, elt_at (h, handle));
608 }
609 
610 void *
611 _heap_free (void *v)
612 {
613  heap_header_t *h = heap_header (v);
614  uword b;
615 
616  if (!v)
617  return v;
618 
620  for (b = 0; b < vec_len (h->free_lists); b++)
621  vec_free (h->free_lists[b]);
622  vec_free (h->free_lists);
623  vec_free (h->elts);
624  vec_free (h->free_elts);
626  if (!(h->flags & HEAP_IS_STATIC))
627  vec_free_h (v, sizeof (h[0]));
628  return v;
629 }
630 
631 uword
632 heap_bytes (void *v)
633 {
634  heap_header_t *h = heap_header (v);
635  uword bytes, b;
636 
637  if (!v)
638  return 0;
639 
640  bytes = sizeof (h[0]);
641  bytes += vec_len (v) * sizeof (h->elt_bytes);
642  for (b = 0; b < vec_len (h->free_lists); b++)
643  bytes += vec_capacity (h->free_lists[b], 0);
644  bytes += vec_bytes (h->free_lists);
645  bytes += vec_capacity (h->elts, 0);
646  bytes += vec_capacity (h->free_elts, 0);
647  bytes += vec_bytes (h->used_elt_bitmap);
648 
649  return bytes;
650 }
651 
652 static u8 *
653 debug_elt (u8 * s, void *v, word i, word n)
654 {
655  heap_elt_t *e, *e0, *e1;
656  heap_header_t *h = heap_header (v);
657  word j;
658 
659  if (vec_len (h->elts) == 0)
660  return s;
661 
662  if (i < 0)
663  e0 = first (h);
664  else
665  {
666  e0 = h->elts + i;
667  for (j = 0; j < n / 2; j++)
668  e0 = heap_prev (e0);
669  }
670 
671  if (n < 0)
672  e1 = h->elts + h->tail;
673  else
674  {
675  e1 = h->elts + i;
676  for (j = 0; j < n / 2; j++)
677  e1 = heap_next (e1);
678  }
679 
680  i = -n / 2;
681  for (e = e0; 1; e = heap_next (e))
682  {
683  if (heap_is_free (e))
684  s = format (s, "index %4d, free\n", e - h->elts);
685  else if (h->format_elt)
686  s = format (s, "%U", h->format_elt, v, elt_data (v, e));
687  else
688  s = format (s, "index %4d, used\n", e - h->elts);
689  i++;
690  if (e == e1)
691  break;
692  }
693 
694  return s;
695 }
696 
697 u8 *
698 format_heap (u8 * s, va_list * va)
699 {
700  void *v = va_arg (*va, void *);
701  uword verbose = va_arg (*va, uword);
702  heap_header_t *h = heap_header (v);
703  heap_header_t zero;
704 
705  clib_memset (&zero, 0, sizeof (zero));
706 
707  if (!v)
708  h = &zero;
709 
710  {
711  f64 elt_bytes = vec_len (v) * h->elt_bytes;
712  f64 overhead_bytes = heap_bytes (v);
713 
714  s = format (s, "heap %p, %6d objects, size %.1fk + overhead %.1fk\n",
715  v, h->used_count, elt_bytes / 1024,
716  (overhead_bytes - elt_bytes) / 1024);
717  }
718 
719  if (v && verbose)
720  s = debug_elt (s, v, -1, -1);
721 
722  return s;
723 }
724 
725 void
726 heap_validate (void *v)
727 {
728  heap_header_t *h = heap_header (v);
729  uword i, o, s;
730  u8 *free_map;
731  heap_elt_t *e, *n;
732 
733  uword used_count, total_size;
734  uword free_count, free_size;
735 
737 
738  ASSERT (first (h)->prev == 0);
739  ASSERT (last (h)->next == 0);
740 
741  /* Validate number of elements and size. */
742  free_size = free_count = 0;
743  for (i = 0; i < vec_len (h->free_lists); i++)
744  {
745  free_count += vec_len (h->free_lists[i]);
746  for (o = 0; o < vec_len (h->free_lists[i]); o++)
747  {
748  e = h->elts + h->free_lists[i][o];
749  s = heap_elt_size (v, e);
750  ASSERT (size_to_bin (s) == i);
751  ASSERT (heap_is_free (e));
752  free_size += s;
753  }
754  }
755 
756  {
757  uword elt_free_size, elt_free_count;
758 
759  used_count = total_size = elt_free_size = elt_free_count = 0;
760  for (e = first (h); 1; e = n)
761  {
762  int is_free = heap_is_free (e);
763  used_count++;
764  s = heap_elt_size (v, e);
765  total_size += s;
766  ASSERT (is_free ==
767  !clib_bitmap_get (h->used_elt_bitmap, e - h->elts));
768  if (is_free)
769  {
770  elt_free_count++;
771  elt_free_size += s;
772  }
773  n = heap_next (e);
774  if (e == n)
775  {
776  ASSERT (last (h) == n);
777  break;
778  }
779 
780  /* We should never have two free adjacent elements. */
781  ASSERT (!(heap_is_free (e) && heap_is_free (n)));
782  }
783 
784  ASSERT (free_count == elt_free_count);
785  ASSERT (free_size == elt_free_size);
786  ASSERT (used_count == h->used_count + free_count);
787  ASSERT (total_size == vec_len (v));
788  }
789 
790  free_map = vec_new (u8, used_count);
791 
792  e = first (h);
793  for (i = o = 0; 1; i++)
794  {
795  ASSERT (heap_offset (e) == o);
796  s = heap_elt_size (v, e);
797 
798  if (heap_is_free (e))
799  {
800  uword fb, fi;
801 
802  fi = get_free_elt (v, e, &fb);
803 
804  ASSERT (fb < vec_len (h->free_lists));
805  ASSERT (fi < vec_len (h->free_lists[fb]));
806  ASSERT (h->free_lists[fb][fi] == e - h->elts);
807 
808  ASSERT (!free_map[i]);
809  free_map[i] = 1;
810  }
811 
812  n = heap_next (e);
813 
814  if (e == n)
815  break;
816 
817  ASSERT (heap_prev (n) == e);
818 
819  o += s;
820  e = n;
821  }
822 
823  vec_free (free_map);
824 }
825 
826 /*
827  * fd.io coding-style-patch-verification: ON
828  *
829  * Local Variables:
830  * eval: (c-set-style "gnu")
831  * End:
832  */
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
Definition: vec.h:509
static heap_elt_t * elt_at(heap_header_t *h, uword i)
Definition: heap.c:46
static heap_elt_t * search_free_list(void *v, uword size)
Definition: heap.c:283
static uword bin_to_size(uword bin)
Definition: heap.c:97
i32 next
Definition: heap.h:78
static uword heap_get_max_len(void *v)
Definition: heap.h:247
static void elt_delete(heap_header_t *h, heap_elt_t *e)
Definition: heap.c:110
#define HEAP_LOG2_SMALL_BINS
Definition: heap.h:118
static uword get_free_elt(void *v, heap_elt_t *e, uword *bin_result)
Definition: heap.c:240
clib_memset(h->entries, 0, sizeof(h->entries[0]) *entries)
u32 tail
Definition: heap.h:144
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
Definition: vec.h:592
static heap_elt_t * last(heap_header_t *h)
Definition: heap.c:53
u8 * format_heap(u8 *s, va_list *va)
Definition: heap.c:698
#define vec_add2(V, P, N)
Add N elements to end of vector V, return pointer to new elements in P.
Definition: vec.h:630
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:424
u32 head
Definition: heap.h:144
static void elt_insert_before(heap_header_t *h, heap_elt_t *e, heap_elt_t *new)
Definition: heap.c:150
u32 offset
Definition: heap.h:75
#define vec_bytes(v)
Number of data bytes in vector.
unsigned char u8
Definition: types.h:56
double f64
Definition: types.h:142
format_function_t * format_elt
Definition: heap.h:138
u32 * free_elts
Definition: heap.h:133
i64 word
Definition: types.h:111
static heap_elt_t * elt_new(heap_header_t *h)
Definition: heap.c:196
static void set_free_elt(void *v, heap_elt_t *e, uword fi)
Definition: heap.c:220
#define vec_new(T, N)
Create new vector of given type and length (unspecified alignment, no header).
Definition: vec.h:350
static uword heap_is_free(heap_elt_t *e)
Definition: heap.h:85
unsigned int u32
Definition: types.h:88
#define vec_end(v)
End (last data address) of vector.
static void remove_free_block(void *v, uword b, uword i)
Definition: heap.c:263
uword * used_elt_bitmap
Definition: heap.h:141
static heap_elt_t * heap_next(heap_elt_t *e)
Definition: heap.h:97
static heap_elt_t * first(heap_header_t *h)
Definition: heap.c:59
#define HEAP_DATA_ALIGN
Definition: heap.h:158
#define HEAP_IS_STATIC
Definition: heap.h:154
i32 prev
Definition: heap.h:78
u32 size
Definition: vhost_user.h:106
vec_header_t h
Definition: buffer.c:322
heap_elt_t * elts
Definition: heap.h:126
#define always_inline
Definition: ipsec.h:28
static void dealloc_elt(void *v, heap_elt_t *e)
Definition: heap.c:360
uword heap_bytes(void *v)
Definition: heap.c:632
static u32 * elt_data(void *v, heap_elt_t *e)
Definition: heap.c:213
static void combine_free_blocks(void *v, heap_elt_t *e0, heap_elt_t *e1)
Definition: heap.c:526
u32 elt_bytes
Definition: heap.h:149
sll srl srl sll sra u16x4 i
Definition: vector_sse42.h:317
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:380
u32 used_count
Definition: heap.h:146
#define HEAP_SMALL_BINS
Definition: heap.h:119
static uword heap_offset(heap_elt_t *e)
Definition: heap.h:91
static uword max_pow2(uword x)
Definition: clib.h:243
#define ARRAY_LEN(x)
Definition: clib.h:67
#define vec_capacity(v, b)
Total number of bytes that can fit in vector with current allocation.
static uword clib_bitmap_get(uword *ai, uword i)
Gets the ith bit value from a bitmap.
Definition: bitmap.h:197
u32 * small_free_elt_free_index
Definition: heap.h:130
#define ASSERT(truth)
static void elt_insert_after(heap_header_t *h, heap_elt_t *e, heap_elt_t *new)
Definition: heap.c:175
void heap_validate(void *v)
Definition: heap.c:726
void heap_dealloc(void *v, uword handle)
Definition: heap.c:500
#define clib_bitmap_free(v)
Free a bitmap.
Definition: bitmap.h:92
static uword heap_elt_size(void *v, heap_elt_t *e)
Definition: heap.h:109
static heap_header_t * heap_header(void *v)
Definition: heap.h:161
static u8 * debug_elt(u8 *s, void *v, word i, word n)
Definition: heap.c:653
static heap_elt_t * heap_prev(heap_elt_t *e)
Definition: heap.h:103
uword heap_len(void *v, word handle)
Definition: heap.c:601
u32 flags
Definition: heap.h:151
#define vec_elt(v, i)
Get vector value at index i.
static uword clib_bitmap_count_set_bits(uword *ai)
Return the number of set bits in a bitmap.
Definition: bitmap.h:462
template key/value backing page structure
Definition: bihash_doc.h:44
#define HEAP_ELT_FREE_BIT
Definition: heap.h:82
#define vec_free_h(V, H)
Free vector&#39;s memory (general version)
Definition: vec.h:367
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
#define HEAP_N_BINS
Definition: heap.h:120
static uword max_log2(uword x)
Definition: clib.h:208
u64 uword
Definition: types.h:112
u32 index
Definition: flow_types.api:221
struct clib_bihash_value offset
template key/value backing page structure
static uword size_to_bin(uword size)
Definition: heap.c:73
CLIB vectors are ubiquitous dynamically resized arrays with by user defined "headers".
u32 ** free_lists
Definition: heap.h:136