From 7cd468a3d7dee7d6c92f69a0bb7061ae208ec727 Mon Sep 17 00:00:00 2001 From: Damjan Marion Date: Mon, 19 Dec 2016 23:05:39 +0100 Subject: Reorganize source tree to use single autotools instance Change-Id: I7b51f88292e057c6443b12224486f2d0c9f8ae23 Signed-off-by: Damjan Marion --- src/vppinfra/heap.c | 828 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 828 insertions(+) create mode 100644 src/vppinfra/heap.c (limited to 'src/vppinfra/heap.c') diff --git a/src/vppinfra/heap.c b/src/vppinfra/heap.c new file mode 100644 index 00000000..2a5fb5c8 --- /dev/null +++ b/src/vppinfra/heap.c @@ -0,0 +1,828 @@ +/* + * Copyright (c) 2015 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +/* + Copyright (c) 2001, 2002, 2003 Eliot Dresselhaus + + Permission is hereby granted, free of charge, to any person obtaining + a copy of this software and associated documentation files (the + "Software"), to deal in the Software without restriction, including + without limitation the rights to use, copy, modify, merge, publish, + distribute, sublicense, and/or sell copies of the Software, and to + permit persons to whom the Software is furnished to do so, subject to + the following conditions: + + The above copyright notice and this permission notice shall be + included in all copies or substantial portions of the Software. + + THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE + LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION + OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION + WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. +*/ + +#include /* for CLIB_CACHE_LINE_BYTES */ +#include +#include +#include +#include +#include + +always_inline heap_elt_t * +elt_at (heap_header_t * h, uword i) +{ + ASSERT (i < vec_len (h->elts)); + return h->elts + i; +} + +always_inline heap_elt_t * +last (heap_header_t * h) +{ + return elt_at (h, h->tail); +} + +always_inline heap_elt_t * +first (heap_header_t * h) +{ + return elt_at (h, h->head); +} + +/* Objects sizes are binned into N_BINS bins. + Objects with size <= SMALL_BINS have their own bins. + Larger objects are grouped together in power or 2 sized + bins. + + Sizes are in units of elt_bytes bytes. */ + +/* Convert size to bin. */ +always_inline uword +size_to_bin (uword size) +{ + uword bin; + + ASSERT (size > 0); + + if (size <= HEAP_SMALL_BINS) + { + bin = size - 1; + if (size == 0) + bin = 0; + } + else + { + bin = HEAP_SMALL_BINS + max_log2 (size) - (HEAP_LOG2_SMALL_BINS + 1); + if (bin >= HEAP_N_BINS) + bin = HEAP_N_BINS - 1; + } + + return bin; +} + +/* Convert bin to size. */ +always_inline __attribute__ ((unused)) + uword bin_to_size (uword bin) +{ + uword size; + + if (bin <= HEAP_SMALL_BINS - 1) + size = bin + 1; + else + size = (uword) 1 << ((bin - HEAP_SMALL_BINS) + HEAP_LOG2_SMALL_BINS + 1); + + return size; +} + +static void +elt_delete (heap_header_t * h, heap_elt_t * e) +{ + heap_elt_t *l = vec_end (h->elts) - 1; + + ASSERT (e >= h->elts && e <= l); + + /* Update doubly linked pointers. */ + { + heap_elt_t *p = heap_prev (e); + heap_elt_t *n = heap_next (e); + + if (p == e) + { + n->prev = 0; + h->head = n - h->elts; + } + else if (n == e) + { + p->next = 0; + h->tail = p - h->elts; + } + else + { + p->next = n - p; + n->prev = p - n; + } + } + + /* Add to index free list or delete from end. */ + if (e < l) + vec_add1 (h->free_elts, e - h->elts); + else + _vec_len (h->elts)--; +} + +/* + Before: P ... E + After : P ... NEW ... E +*/ +always_inline void +elt_insert_before (heap_header_t * h, heap_elt_t * e, heap_elt_t * new) +{ + heap_elt_t *p = heap_prev (e); + + if (p == e) + { + new->prev = 0; + new->next = e - new; + p->prev = new - p; + h->head = new - h->elts; + } + else + { + new->prev = p - new; + new->next = e - new; + e->prev = new - e; + p->next = new - p; + } +} + +/* + Before: E ... N + After : E ... NEW ... N +*/ +always_inline void +elt_insert_after (heap_header_t * h, heap_elt_t * e, heap_elt_t * new) +{ + heap_elt_t *n = heap_next (e); + + if (n == e) + { + new->next = 0; + new->prev = e - new; + e->next = new - e; + h->tail = new - h->elts; + } + else + { + new->prev = e - new; + new->next = n - new; + e->next = new - e; + n->prev = new - n; + } +} + +always_inline heap_elt_t * +elt_new (heap_header_t * h) +{ + heap_elt_t *e; + uword l; + if ((l = vec_len (h->free_elts)) > 0) + { + e = elt_at (h, h->free_elts[l - 1]); + _vec_len (h->free_elts) -= 1; + } + else + vec_add2 (h->elts, e, 1); + return e; +} + +/* Return pointer to object at given offset. + Used to write free list index of free objects. */ +always_inline u32 * +elt_data (void *v, heap_elt_t * e) +{ + heap_header_t *h = heap_header (v); + return v + heap_offset (e) * h->elt_bytes; +} + +always_inline void +set_free_elt (void *v, heap_elt_t * e, uword fi) +{ + heap_header_t *h = heap_header (v); + + e->offset |= HEAP_ELT_FREE_BIT; + if (h->elt_bytes >= sizeof (u32)) + { + *elt_data (v, e) = fi; + } + else + { + /* For elt_bytes < 4 we must store free index in separate + vector. */ + uword elt_index = e - h->elts; + vec_validate (h->small_free_elt_free_index, elt_index); + h->small_free_elt_free_index[elt_index] = fi; + } +} + +always_inline uword +get_free_elt (void *v, heap_elt_t * e, uword * bin_result) +{ + heap_header_t *h = heap_header (v); + uword fb, fi; + + ASSERT (heap_is_free (e)); + fb = size_to_bin (heap_elt_size (v, e)); + + if (h->elt_bytes >= sizeof (u32)) + { + fi = *elt_data (v, e); + } + else + { + uword elt_index = e - h->elts; + fi = vec_elt (h->small_free_elt_free_index, elt_index); + } + + *bin_result = fb; + return fi; +} + +always_inline void +remove_free_block (void *v, uword b, uword i) +{ + heap_header_t *h = heap_header (v); + uword l; + + ASSERT (b < vec_len (h->free_lists)); + ASSERT (i < vec_len (h->free_lists[b])); + + l = vec_len (h->free_lists[b]); + + if (i < l - 1) + { + uword t = h->free_lists[b][l - 1]; + h->free_lists[b][i] = t; + set_free_elt (v, elt_at (h, t), i); + } + _vec_len (h->free_lists[b]) = l - 1; +} + +static heap_elt_t * +search_free_list (void *v, uword size) +{ + heap_header_t *h = heap_header (v); + heap_elt_t *f, *u; + uword b, fb, f_size, f_index; + word s, l; + + if (!v) + return 0; + + /* Search free lists for bins >= given size. */ + for (b = size_to_bin (size); b < vec_len (h->free_lists); b++) + if ((l = vec_len (h->free_lists[b])) > 0) + { + /* Find an object that is large enough. + Search list in reverse so that more recently freed objects will be + allocated again sooner. */ + do + { + l--; + f_index = h->free_lists[b][l]; + f = elt_at (h, f_index); + f_size = heap_elt_size (v, f); + if ((s = f_size - size) >= 0) + break; + } + while (l >= 0); + + /* If we fail to find a large enough object, try the next larger size. */ + if (l < 0) + continue; + + ASSERT (heap_is_free (f)); + + /* Link in used object (u) after free object (f). */ + if (s == 0) + { + u = f; + fb = HEAP_N_BINS; + } + else + { + u = elt_new (h); + f = elt_at (h, f_index); + elt_insert_after (h, f, u); + fb = size_to_bin (s); + } + + u->offset = heap_offset (f) + s; + + if (fb != b) + { + if (fb < HEAP_N_BINS) + { + uword i; + vec_validate (h->free_lists, fb); + i = vec_len (h->free_lists[fb]); + vec_add1 (h->free_lists[fb], f - h->elts); + set_free_elt (v, f, i); + } + + remove_free_block (v, b, l); + } + + return u; + } + + return 0; +} + +static void combine_free_blocks (void *v, heap_elt_t * e0, heap_elt_t * e1); + +static inline void +dealloc_elt (void *v, heap_elt_t * e) +{ + heap_header_t *h = heap_header (v); + uword b, l; + heap_elt_t *n, *p; + + b = size_to_bin (heap_elt_size (v, e)); + vec_validate (h->free_lists, b); + l = vec_len (h->free_lists[b]); + vec_add1 (h->free_lists[b], e - h->elts); + set_free_elt (v, e, l); + + /* See if we can combine the block we just freed with neighboring free blocks. */ + p = heap_prev (e); + if (!heap_is_free (p)) + p = e; + + n = heap_next (e); + if (!heap_is_free (n)) + n = e; + + if (p != n) + combine_free_blocks (v, p, n); +} + +void * +_heap_alloc (void *v, + uword size, + uword align, + uword elt_bytes, uword * offset_return, uword * handle_return) +{ + uword offset = 0, align_size; + heap_header_t *h; + heap_elt_t *e; + + if (size == 0) + goto error; + + /* Round up alignment to power of 2. */ + if (align <= 1) + { + align = 0; + align_size = size; + } + else + { + align = max_pow2 (align); + align_size = size + align - 1; + } + + e = search_free_list (v, align_size); + + /* If nothing found on free list, allocate object from end of vector. */ + if (!e) + { + uword max_len; + + offset = vec_len (v); + max_len = heap_get_max_len (v); + + if (max_len && offset + align_size > max_len) + goto error; + + h = heap_header (v); + if (!v || !(h->flags & HEAP_IS_STATIC)) + v = _vec_resize (v, + align_size, + (offset + align_size) * elt_bytes, + sizeof (h[0]), HEAP_DATA_ALIGN); + else + _vec_len (v) += align_size; + + if (offset == 0) + { + h = heap_header (v); + h->elt_bytes = elt_bytes; + } + } + + h = heap_header (v); + + /* Add new element to doubly linked chain of elements. */ + if (!e) + { + e = elt_new (h); + e->offset = offset; + elt_insert_after (h, last (h), e); + } + + if (align > 0) + { + uword e_index; + uword new_offset, old_offset; + + old_offset = e->offset; + new_offset = (old_offset + align - 1) & ~(align - 1); + e->offset = new_offset; + e_index = e - h->elts; + + /* Free fragments before and after aligned object. */ + if (new_offset > old_offset) + { + heap_elt_t *before_e = elt_new (h); + before_e->offset = old_offset; + elt_insert_before (h, h->elts + e_index, before_e); + dealloc_elt (v, before_e); + } + + if (new_offset + size < old_offset + align_size) + { + heap_elt_t *after_e = elt_new (h); + after_e->offset = new_offset + size; + elt_insert_after (h, h->elts + e_index, after_e); + dealloc_elt (v, after_e); + } + + e = h->elts + e_index; + } + + h->used_count++; + + /* Keep track of used elements when debugging. + This allows deallocation to check that passed objects are valid. */ + if (CLIB_DEBUG > 0) + { + uword handle = e - h->elts; + ASSERT (!clib_bitmap_get (h->used_elt_bitmap, handle)); + h->used_elt_bitmap = clib_bitmap_ori (h->used_elt_bitmap, handle); + } + + *offset_return = e->offset; + *handle_return = e - h->elts; + return v; + +error: + *offset_return = *handle_return = ~0; + return v; +} + +void +heap_dealloc (void *v, uword handle) +{ + heap_header_t *h = heap_header (v); + heap_elt_t *e; + + ASSERT (handle < vec_len (h->elts)); + + /* For debugging we keep track of indices for valid objects. + We make sure user is not trying to free object with an invalid index. */ + if (CLIB_DEBUG > 0) + { + ASSERT (clib_bitmap_get (h->used_elt_bitmap, handle)); + h->used_elt_bitmap = clib_bitmap_andnoti (h->used_elt_bitmap, handle); + } + + h->used_count--; + + e = h->elts + handle; + ASSERT (!heap_is_free (e)); + + dealloc_elt (v, e); +} + +/* While freeing objects at INDEX we noticed free blocks i0 <= index and + i1 >= index. We combine these two or three blocks into one big free block. */ +static void +combine_free_blocks (void *v, heap_elt_t * e0, heap_elt_t * e1) +{ + heap_header_t *h = heap_header (v); + uword total_size, i, b, tb, ti, i_last, g_offset; + heap_elt_t *e; + + struct + { + u32 index; + u32 bin; + u32 bin_index; + } f[3], g; + + /* Compute total size of free objects i0 through i1. */ + total_size = 0; + for (i = 0, e = e0; 1; e = heap_next (e), i++) + { + ASSERT (i < ARRAY_LEN (f)); + + ti = get_free_elt (v, e, &tb); + + ASSERT (tb < vec_len (h->free_lists)); + ASSERT (ti < vec_len (h->free_lists[tb])); + + f[i].index = h->free_lists[tb][ti]; + f[i].bin = tb; + f[i].bin_index = ti; + + total_size += heap_elt_size (v, elt_at (h, f[i].index)); + + if (e == e1) + { + i_last = i; + break; + } + } + + /* Compute combined bin. See if all objects can be + combined into existing bin. */ + b = size_to_bin (total_size); + g.index = g.bin_index = 0; + for (i = 0; i <= i_last; i++) + if (b == f[i].bin) + { + g = f[i]; + break; + } + + /* Make sure we found a bin. */ + if (i > i_last) + { + g.index = elt_new (h) - h->elts; + vec_validate (h->free_lists, b); + g.bin_index = vec_len (h->free_lists[b]); + vec_add1 (h->free_lists[b], g.index); + elt_insert_before (h, elt_at (h, f[0].index), elt_at (h, g.index)); + } + + g_offset = elt_at (h, f[0].index)->offset; + + /* Delete unused bins. */ + for (i = 0; i <= i_last; i++) + if (g.index != f[i].index) + { + ti = get_free_elt (v, elt_at (h, f[i].index), &tb); + remove_free_block (v, tb, ti); + elt_delete (h, elt_at (h, f[i].index)); + } + + /* Initialize new element. */ + elt_at (h, g.index)->offset = g_offset; + set_free_elt (v, elt_at (h, g.index), g.bin_index); +} + +uword +heap_len (void *v, word handle) +{ + heap_header_t *h = heap_header (v); + + if (CLIB_DEBUG > 0) + ASSERT (clib_bitmap_get (h->used_elt_bitmap, handle)); + return heap_elt_size (v, elt_at (h, handle)); +} + +void * +_heap_free (void *v) +{ + heap_header_t *h = heap_header (v); + uword b; + + if (!v) + return v; + + clib_bitmap_free (h->used_elt_bitmap); + for (b = 0; b < vec_len (h->free_lists); b++) + vec_free (h->free_lists[b]); + vec_free (h->free_lists); + vec_free (h->elts); + vec_free (h->free_elts); + vec_free (h->small_free_elt_free_index); + if (!(h->flags & HEAP_IS_STATIC)) + vec_free_h (v, sizeof (h[0])); + return v; +} + +uword +heap_bytes (void *v) +{ + heap_header_t *h = heap_header (v); + uword bytes, b; + + if (!v) + return 0; + + bytes = sizeof (h[0]); + bytes += vec_len (v) * sizeof (h->elt_bytes); + for (b = 0; b < vec_len (h->free_lists); b++) + bytes += vec_capacity (h->free_lists[b], 0); + bytes += vec_bytes (h->free_lists); + bytes += vec_capacity (h->elts, 0); + bytes += vec_capacity (h->free_elts, 0); + bytes += vec_bytes (h->used_elt_bitmap); + + return bytes; +} + +static u8 * +debug_elt (u8 * s, void *v, word i, word n) +{ + heap_elt_t *e, *e0, *e1; + heap_header_t *h = heap_header (v); + word j; + + if (vec_len (h->elts) == 0) + return s; + + if (i < 0) + e0 = first (h); + else + { + e0 = h->elts + i; + for (j = 0; j < n / 2; j++) + e0 = heap_prev (e0); + } + + if (n < 0) + e1 = h->elts + h->tail; + else + { + e1 = h->elts + i; + for (j = 0; j < n / 2; j++) + e1 = heap_next (e1); + } + + i = -n / 2; + for (e = e0; 1; e = heap_next (e)) + { + if (heap_is_free (e)) + s = format (s, "index %4d, free\n", e - h->elts); + else if (h->format_elt) + s = format (s, "%U", h->format_elt, v, elt_data (v, e)); + else + s = format (s, "index %4d, used\n", e - h->elts); + i++; + if (e == e1) + break; + } + + return s; +} + +u8 * +format_heap (u8 * s, va_list * va) +{ + void *v = va_arg (*va, void *); + uword verbose = va_arg (*va, uword); + heap_header_t *h = heap_header (v); + heap_header_t zero; + + memset (&zero, 0, sizeof (zero)); + + if (!v) + h = &zero; + + { + f64 elt_bytes = vec_len (v) * h->elt_bytes; + f64 overhead_bytes = heap_bytes (v); + + s = format (s, "heap %p, %6d objects, size %.1fk + overhead %.1fk\n", + v, h->used_count, elt_bytes / 1024, + (overhead_bytes - elt_bytes) / 1024); + } + + if (v && verbose) + s = debug_elt (s, v, -1, -1); + + return s; +} + +void +heap_validate (void *v) +{ + heap_header_t *h = heap_header (v); + uword i, o, s; + u8 *free_map; + heap_elt_t *e, *n; + + uword used_count, total_size; + uword free_count, free_size; + + ASSERT (h->used_count == clib_bitmap_count_set_bits (h->used_elt_bitmap)); + + ASSERT (first (h)->prev == 0); + ASSERT (last (h)->next == 0); + + /* Validate number of elements and size. */ + free_size = free_count = 0; + for (i = 0; i < vec_len (h->free_lists); i++) + { + free_count += vec_len (h->free_lists[i]); + for (o = 0; o < vec_len (h->free_lists[i]); o++) + { + e = h->elts + h->free_lists[i][o]; + s = heap_elt_size (v, e); + ASSERT (size_to_bin (s) == i); + ASSERT (heap_is_free (e)); + free_size += s; + } + } + + { + uword elt_free_size, elt_free_count; + + used_count = total_size = elt_free_size = elt_free_count = 0; + for (e = first (h); 1; e = n) + { + int is_free = heap_is_free (e); + used_count++; + s = heap_elt_size (v, e); + total_size += s; + ASSERT (is_free == + !clib_bitmap_get (h->used_elt_bitmap, e - h->elts)); + if (is_free) + { + elt_free_count++; + elt_free_size += s; + } + n = heap_next (e); + if (e == n) + { + ASSERT (last (h) == n); + break; + } + + /* We should never have two free adjacent elements. */ + ASSERT (!(heap_is_free (e) && heap_is_free (n))); + } + + ASSERT (free_count == elt_free_count); + ASSERT (free_size == elt_free_size); + ASSERT (used_count == h->used_count + free_count); + ASSERT (total_size == vec_len (v)); + } + + free_map = vec_new (u8, used_count); + + e = first (h); + for (i = o = 0; 1; i++) + { + ASSERT (heap_offset (e) == o); + s = heap_elt_size (v, e); + + if (heap_is_free (e)) + { + uword fb, fi; + + fi = get_free_elt (v, e, &fb); + + ASSERT (fb < vec_len (h->free_lists)); + ASSERT (fi < vec_len (h->free_lists[fb])); + ASSERT (h->free_lists[fb][fi] == e - h->elts); + + ASSERT (!free_map[i]); + free_map[i] = 1; + } + + n = heap_next (e); + + if (e == n) + break; + + ASSERT (heap_prev (n) == e); + + o += s; + e = n; + } + + vec_free (free_map); +} + +/* + * fd.io coding-style-patch-verification: ON + * + * Local Variables: + * eval: (c-set-style "gnu") + * End: + */ -- cgit 1.2.3-korg