FD.io VPP  v18.04-17-g3a0d853
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  do
301  {
302  l--;
303  f_index = h->free_lists[b][l];
304  f = elt_at (h, f_index);
305  f_size = heap_elt_size (v, f);
306  if ((s = f_size - size) >= 0)
307  break;
308  }
309  while (l >= 0);
310 
311  /* If we fail to find a large enough object, try the next larger size. */
312  if (l < 0)
313  continue;
314 
315  ASSERT (heap_is_free (f));
316 
317  /* Link in used object (u) after free object (f). */
318  if (s == 0)
319  {
320  u = f;
321  fb = HEAP_N_BINS;
322  }
323  else
324  {
325  u = elt_new (h);
326  f = elt_at (h, f_index);
327  elt_insert_after (h, f, u);
328  fb = size_to_bin (s);
329  }
330 
331  u->offset = heap_offset (f) + s;
332 
333  if (fb != b)
334  {
335  if (fb < HEAP_N_BINS)
336  {
337  uword i;
338  vec_validate (h->free_lists, fb);
339  i = vec_len (h->free_lists[fb]);
340  vec_add1 (h->free_lists[fb], f - h->elts);
341  set_free_elt (v, f, i);
342  }
343 
344  remove_free_block (v, b, l);
345  }
346 
347  return u;
348  }
349 
350  return 0;
351 }
352 
353 static void combine_free_blocks (void *v, heap_elt_t * e0, heap_elt_t * e1);
354 
355 static inline void
357 {
358  heap_header_t *h = heap_header (v);
359  uword b, l;
360  heap_elt_t *n, *p;
361 
362  b = size_to_bin (heap_elt_size (v, e));
363  vec_validate (h->free_lists, b);
364  l = vec_len (h->free_lists[b]);
365  vec_add1 (h->free_lists[b], e - h->elts);
366  set_free_elt (v, e, l);
367 
368  /* See if we can combine the block we just freed with neighboring free blocks. */
369  p = heap_prev (e);
370  if (!heap_is_free (p))
371  p = e;
372 
373  n = heap_next (e);
374  if (!heap_is_free (n))
375  n = e;
376 
377  if (p != n)
378  combine_free_blocks (v, p, n);
379 }
380 
381 void *
382 _heap_alloc (void *v,
383  uword size,
384  uword align,
385  uword elt_bytes, uword * offset_return, uword * handle_return)
386 {
387  uword offset = 0, align_size;
388  heap_header_t *h;
389  heap_elt_t *e;
390 
391  if (size == 0)
392  goto error;
393 
394  /* Round up alignment to power of 2. */
395  if (align <= 1)
396  {
397  align = 0;
398  align_size = size;
399  }
400  else
401  {
402  align = max_pow2 (align);
403  align_size = size + align - 1;
404  }
405 
406  e = search_free_list (v, align_size);
407 
408  /* If nothing found on free list, allocate object from end of vector. */
409  if (!e)
410  {
411  uword max_len;
412 
413  offset = vec_len (v);
414  max_len = heap_get_max_len (v);
415 
416  if (max_len && offset + align_size > max_len)
417  goto error;
418 
419  h = heap_header (v);
420  if (!v || !(h->flags & HEAP_IS_STATIC))
421  v = _vec_resize (v,
422  align_size,
423  (offset + align_size) * elt_bytes,
424  sizeof (h[0]), HEAP_DATA_ALIGN);
425  else
426  _vec_len (v) += align_size;
427 
428  if (offset == 0)
429  {
430  h = heap_header (v);
431  h->elt_bytes = elt_bytes;
432  }
433  }
434 
435  h = heap_header (v);
436 
437  /* Add new element to doubly linked chain of elements. */
438  if (!e)
439  {
440  e = elt_new (h);
441  e->offset = offset;
442  elt_insert_after (h, last (h), e);
443  }
444 
445  if (align > 0)
446  {
447  uword e_index;
448  uword new_offset, old_offset;
449 
450  old_offset = e->offset;
451  new_offset = (old_offset + align - 1) & ~(align - 1);
452  e->offset = new_offset;
453  e_index = e - h->elts;
454 
455  /* Free fragments before and after aligned object. */
456  if (new_offset > old_offset)
457  {
458  heap_elt_t *before_e = elt_new (h);
459  before_e->offset = old_offset;
460  elt_insert_before (h, h->elts + e_index, before_e);
461  dealloc_elt (v, before_e);
462  }
463 
464  if (new_offset + size < old_offset + align_size)
465  {
466  heap_elt_t *after_e = elt_new (h);
467  after_e->offset = new_offset + size;
468  elt_insert_after (h, h->elts + e_index, after_e);
469  dealloc_elt (v, after_e);
470  }
471 
472  e = h->elts + e_index;
473  }
474 
475  h->used_count++;
476 
477  /* Keep track of used elements when debugging.
478  This allows deallocation to check that passed objects are valid. */
479  if (CLIB_DEBUG > 0)
480  {
481  uword handle = e - h->elts;
482  ASSERT (!clib_bitmap_get (h->used_elt_bitmap, handle));
483  h->used_elt_bitmap = clib_bitmap_ori (h->used_elt_bitmap, handle);
484  }
485 
486  *offset_return = e->offset;
487  *handle_return = e - h->elts;
488  return v;
489 
490 error:
491  *offset_return = *handle_return = ~0;
492  return v;
493 }
494 
495 void
496 heap_dealloc (void *v, uword handle)
497 {
498  heap_header_t *h = heap_header (v);
499  heap_elt_t *e;
500 
501  ASSERT (handle < vec_len (h->elts));
502 
503  /* For debugging we keep track of indices for valid objects.
504  We make sure user is not trying to free object with an invalid index. */
505  if (CLIB_DEBUG > 0)
506  {
507  ASSERT (clib_bitmap_get (h->used_elt_bitmap, handle));
508  h->used_elt_bitmap = clib_bitmap_andnoti (h->used_elt_bitmap, handle);
509  }
510 
511  h->used_count--;
512 
513  e = h->elts + handle;
514  ASSERT (!heap_is_free (e));
515 
516  dealloc_elt (v, e);
517 }
518 
519 /* While freeing objects at INDEX we noticed free blocks i0 <= index and
520  i1 >= index. We combine these two or three blocks into one big free block. */
521 static void
523 {
524  heap_header_t *h = heap_header (v);
525  uword total_size, i, b, tb, ti, i_last, g_offset;
526  heap_elt_t *e;
527 
528  struct
529  {
530  u32 index;
531  u32 bin;
532  u32 bin_index;
533  } f[3], g;
534 
535  /* Compute total size of free objects i0 through i1. */
536  total_size = 0;
537  for (i = 0, e = e0; 1; e = heap_next (e), i++)
538  {
539  ASSERT (i < ARRAY_LEN (f));
540 
541  ti = get_free_elt (v, e, &tb);
542 
543  ASSERT (tb < vec_len (h->free_lists));
544  ASSERT (ti < vec_len (h->free_lists[tb]));
545 
546  f[i].index = h->free_lists[tb][ti];
547  f[i].bin = tb;
548  f[i].bin_index = ti;
549 
550  total_size += heap_elt_size (v, elt_at (h, f[i].index));
551 
552  if (e == e1)
553  {
554  i_last = i;
555  break;
556  }
557  }
558 
559  /* Compute combined bin. See if all objects can be
560  combined into existing bin. */
561  b = size_to_bin (total_size);
562  g.index = g.bin_index = 0;
563  for (i = 0; i <= i_last; i++)
564  if (b == f[i].bin)
565  {
566  g = f[i];
567  break;
568  }
569 
570  /* Make sure we found a bin. */
571  if (i > i_last)
572  {
573  g.index = elt_new (h) - h->elts;
574  vec_validate (h->free_lists, b);
575  g.bin_index = vec_len (h->free_lists[b]);
576  vec_add1 (h->free_lists[b], g.index);
577  elt_insert_before (h, elt_at (h, f[0].index), elt_at (h, g.index));
578  }
579 
580  g_offset = elt_at (h, f[0].index)->offset;
581 
582  /* Delete unused bins. */
583  for (i = 0; i <= i_last; i++)
584  if (g.index != f[i].index)
585  {
586  ti = get_free_elt (v, elt_at (h, f[i].index), &tb);
587  remove_free_block (v, tb, ti);
588  elt_delete (h, elt_at (h, f[i].index));
589  }
590 
591  /* Initialize new element. */
592  elt_at (h, g.index)->offset = g_offset;
593  set_free_elt (v, elt_at (h, g.index), g.bin_index);
594 }
595 
596 uword
597 heap_len (void *v, word handle)
598 {
599  heap_header_t *h = heap_header (v);
600 
601  if (CLIB_DEBUG > 0)
602  ASSERT (clib_bitmap_get (h->used_elt_bitmap, handle));
603  return heap_elt_size (v, elt_at (h, handle));
604 }
605 
606 void *
607 _heap_free (void *v)
608 {
609  heap_header_t *h = heap_header (v);
610  uword b;
611 
612  if (!v)
613  return v;
614 
616  for (b = 0; b < vec_len (h->free_lists); b++)
617  vec_free (h->free_lists[b]);
618  vec_free (h->free_lists);
619  vec_free (h->elts);
620  vec_free (h->free_elts);
622  if (!(h->flags & HEAP_IS_STATIC))
623  vec_free_h (v, sizeof (h[0]));
624  return v;
625 }
626 
627 uword
628 heap_bytes (void *v)
629 {
630  heap_header_t *h = heap_header (v);
631  uword bytes, b;
632 
633  if (!v)
634  return 0;
635 
636  bytes = sizeof (h[0]);
637  bytes += vec_len (v) * sizeof (h->elt_bytes);
638  for (b = 0; b < vec_len (h->free_lists); b++)
639  bytes += vec_capacity (h->free_lists[b], 0);
640  bytes += vec_bytes (h->free_lists);
641  bytes += vec_capacity (h->elts, 0);
642  bytes += vec_capacity (h->free_elts, 0);
643  bytes += vec_bytes (h->used_elt_bitmap);
644 
645  return bytes;
646 }
647 
648 static u8 *
649 debug_elt (u8 * s, void *v, word i, word n)
650 {
651  heap_elt_t *e, *e0, *e1;
652  heap_header_t *h = heap_header (v);
653  word j;
654 
655  if (vec_len (h->elts) == 0)
656  return s;
657 
658  if (i < 0)
659  e0 = first (h);
660  else
661  {
662  e0 = h->elts + i;
663  for (j = 0; j < n / 2; j++)
664  e0 = heap_prev (e0);
665  }
666 
667  if (n < 0)
668  e1 = h->elts + h->tail;
669  else
670  {
671  e1 = h->elts + i;
672  for (j = 0; j < n / 2; j++)
673  e1 = heap_next (e1);
674  }
675 
676  i = -n / 2;
677  for (e = e0; 1; e = heap_next (e))
678  {
679  if (heap_is_free (e))
680  s = format (s, "index %4d, free\n", e - h->elts);
681  else if (h->format_elt)
682  s = format (s, "%U", h->format_elt, v, elt_data (v, e));
683  else
684  s = format (s, "index %4d, used\n", e - h->elts);
685  i++;
686  if (e == e1)
687  break;
688  }
689 
690  return s;
691 }
692 
693 u8 *
694 format_heap (u8 * s, va_list * va)
695 {
696  void *v = va_arg (*va, void *);
697  uword verbose = va_arg (*va, uword);
698  heap_header_t *h = heap_header (v);
699  heap_header_t zero;
700 
701  memset (&zero, 0, sizeof (zero));
702 
703  if (!v)
704  h = &zero;
705 
706  {
707  f64 elt_bytes = vec_len (v) * h->elt_bytes;
708  f64 overhead_bytes = heap_bytes (v);
709 
710  s = format (s, "heap %p, %6d objects, size %.1fk + overhead %.1fk\n",
711  v, h->used_count, elt_bytes / 1024,
712  (overhead_bytes - elt_bytes) / 1024);
713  }
714 
715  if (v && verbose)
716  s = debug_elt (s, v, -1, -1);
717 
718  return s;
719 }
720 
721 void
723 {
724  heap_header_t *h = heap_header (v);
725  uword i, o, s;
726  u8 *free_map;
727  heap_elt_t *e, *n;
728 
729  uword used_count, total_size;
730  uword free_count, free_size;
731 
733 
734  ASSERT (first (h)->prev == 0);
735  ASSERT (last (h)->next == 0);
736 
737  /* Validate number of elements and size. */
738  free_size = free_count = 0;
739  for (i = 0; i < vec_len (h->free_lists); i++)
740  {
741  free_count += vec_len (h->free_lists[i]);
742  for (o = 0; o < vec_len (h->free_lists[i]); o++)
743  {
744  e = h->elts + h->free_lists[i][o];
745  s = heap_elt_size (v, e);
746  ASSERT (size_to_bin (s) == i);
747  ASSERT (heap_is_free (e));
748  free_size += s;
749  }
750  }
751 
752  {
753  uword elt_free_size, elt_free_count;
754 
755  used_count = total_size = elt_free_size = elt_free_count = 0;
756  for (e = first (h); 1; e = n)
757  {
758  int is_free = heap_is_free (e);
759  used_count++;
760  s = heap_elt_size (v, e);
761  total_size += s;
762  ASSERT (is_free ==
763  !clib_bitmap_get (h->used_elt_bitmap, e - h->elts));
764  if (is_free)
765  {
766  elt_free_count++;
767  elt_free_size += s;
768  }
769  n = heap_next (e);
770  if (e == n)
771  {
772  ASSERT (last (h) == n);
773  break;
774  }
775 
776  /* We should never have two free adjacent elements. */
777  ASSERT (!(heap_is_free (e) && heap_is_free (n)));
778  }
779 
780  ASSERT (free_count == elt_free_count);
781  ASSERT (free_size == elt_free_size);
782  ASSERT (used_count == h->used_count + free_count);
783  ASSERT (total_size == vec_len (v));
784  }
785 
786  free_map = vec_new (u8, used_count);
787 
788  e = first (h);
789  for (i = o = 0; 1; i++)
790  {
791  ASSERT (heap_offset (e) == o);
792  s = heap_elt_size (v, e);
793 
794  if (heap_is_free (e))
795  {
796  uword fb, fi;
797 
798  fi = get_free_elt (v, e, &fb);
799 
800  ASSERT (fb < vec_len (h->free_lists));
801  ASSERT (fi < vec_len (h->free_lists[fb]));
802  ASSERT (h->free_lists[fb][fi] == e - h->elts);
803 
804  ASSERT (!free_map[i]);
805  free_map[i] = 1;
806  }
807 
808  n = heap_next (e);
809 
810  if (e == n)
811  break;
812 
813  ASSERT (heap_prev (n) == e);
814 
815  o += s;
816  e = n;
817  }
818 
819  vec_free (free_map);
820 }
821 
822 /*
823  * fd.io coding-style-patch-verification: ON
824  *
825  * Local Variables:
826  * eval: (c-set-style "gnu")
827  * End:
828  */
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
Definition: vec.h:434
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
u32 tail
Definition: heap.h:144
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
Definition: vec.h:520
static heap_elt_t * last(heap_header_t *h)
Definition: heap.c:53
u8 * format_heap(u8 *s, va_list *va)
Definition: heap.c:694
#define vec_add2(V, P, N)
Add N elements to end of vector V, return pointer to new elements in P.
Definition: vec.h:559
int i
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:419
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.
format_function_t * format_elt
Definition: heap.h:138
u32 * free_elts
Definition: heap.h:133
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 always_inline
Definition: clib.h:92
#define vec_new(T, N)
Create new vector of given type and length (unspecified alignment, no header).
Definition: vec.h:306
static uword heap_is_free(heap_elt_t *e)
Definition: heap.h:85
#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
u32 size
#define HEAP_DATA_ALIGN
Definition: heap.h:158
#define HEAP_IS_STATIC
Definition: heap.h:154
i32 prev
Definition: heap.h:78
#define v
Definition: acl.c:495
heap_elt_t * elts
Definition: heap.h:126
static void dealloc_elt(void *v, heap_elt_t *e)
Definition: heap.c:356
uword heap_bytes(void *v)
Definition: heap.c:628
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:522
u32 elt_bytes
Definition: heap.h:149
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:336
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:271
#define ARRAY_LEN(x)
Definition: clib.h:59
#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:722
unsigned int u32
Definition: types.h:88
void heap_dealloc(void *v, uword handle)
Definition: heap.c:496
#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:649
static heap_elt_t * heap_prev(heap_elt_t *e)
Definition: heap.h:103
uword heap_len(void *v, word handle)
Definition: heap.c:597
u32 flags
Definition: heap.h:151
u64 uword
Definition: types.h:112
#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:441
template key/value backing page structure
Definition: bihash_doc.h:44
i64 word
Definition: types.h:111
#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:323
#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 HEAP_N_BINS
Definition: heap.h:120
static uword max_log2(uword x)
Definition: clib.h:236
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