diff options
author | Ed Warnicke <eaw@cisco.com> | 2015-12-08 15:45:58 -0700 |
---|---|---|
committer | Ed Warnicke <eaw@cisco.com> | 2015-12-08 15:47:27 -0700 |
commit | cb9cadad578297ffd78fa8a33670bdf1ab669e7e (patch) | |
tree | 6ac2be912482cc7849a26f0ab845561c3d7f4e26 /vppinfra/vppinfra/heap.h | |
parent | fb0815d4ae4bb0fe27bd9313f34b45c8593b907e (diff) |
Initial commit of vpp code.v1.0.0
Change-Id: Ib246f1fbfce93274020ee93ce461e3d8bd8b9f17
Signed-off-by: Ed Warnicke <eaw@cisco.com>
Diffstat (limited to 'vppinfra/vppinfra/heap.h')
-rw-r--r-- | vppinfra/vppinfra/heap.h | 321 |
1 files changed, 321 insertions, 0 deletions
diff --git a/vppinfra/vppinfra/heap.h b/vppinfra/vppinfra/heap.h new file mode 100644 index 00000000000..912e865e75b --- /dev/null +++ b/vppinfra/vppinfra/heap.h @@ -0,0 +1,321 @@ +/* + * 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. +*/ + +/* Heaps of objects of type T (e.g. int, struct foo, ...). + + Usage. To declare a null heap: + + T * heap = 0; + + To allocate: + + offset = heap_alloc (heap, size, handle); + + New object is heap[offset] ... heap[offset + size] + Handle is used to free/query object. + + To free object: + + heap_dealloc (heap, handle); + + To query the size of an object: + + heap_size (heap, handle) + +*/ + +#ifndef included_heap_h +#define included_heap_h + +#include <vppinfra/clib.h> +#include <vppinfra/cache.h> +#include <vppinfra/hash.h> +#include <vppinfra/format.h> +#include <vppinfra/bitmap.h> + +/* Doubly linked list of elements. */ +typedef struct { + /* Offset of this element (plus free bit). + If element is free, data at offset contains pointer to free list. */ + u32 offset; + + /* Index of next and previous elements relative to current element. */ + i32 next, prev; +} heap_elt_t; + +/* Use high bit of offset as free bit. */ +#define HEAP_ELT_FREE_BIT (1 << 31) + +always_inline uword heap_is_free (heap_elt_t * e) +{ return (e->offset & HEAP_ELT_FREE_BIT) != 0; } + +always_inline uword heap_offset (heap_elt_t * e) +{ return e->offset &~ HEAP_ELT_FREE_BIT; } + +always_inline heap_elt_t * heap_next (heap_elt_t * e) +{ return e + e->next; } + +always_inline heap_elt_t * heap_prev (heap_elt_t * e) +{ return e + e->prev; } + +always_inline uword heap_elt_size (void * v, heap_elt_t * e) +{ + heap_elt_t * n = heap_next (e); + uword next_offset = n != e ? heap_offset (n) : vec_len (v); + return next_offset - heap_offset (e); +} + +/* Sizes are binned. Sizes 1 to 2^log2_small_bins have their + own free lists. Larger sizes are grouped in powers of two. */ +#define HEAP_LOG2_SMALL_BINS (5) +#define HEAP_SMALL_BINS (1 << HEAP_LOG2_SMALL_BINS) +#define HEAP_N_BINS (2 * HEAP_SMALL_BINS) + +/* Header for heaps. */ +typedef struct { + /* Vector of used and free elements. */ + heap_elt_t * elts; + + /* For elt_bytes < sizeof (u32) we need some extra space + per elt to store free list index. */ + u32 * small_free_elt_free_index; + + /* Vector of free indices of elts array. */ + u32 * free_elts; + + /* Indices of free elts indexed by size bin. */ + u32 ** free_lists; + + format_function_t * format_elt; + + /* Used for validattion/debugging. */ + uword * used_elt_bitmap; + + /* First and last element of doubly linked chain of elements. */ + u32 head, tail; + + u32 used_count, max_len; + + /* Number of bytes in a help element. */ + u32 elt_bytes; + + u32 flags; + /* Static heaps are made from external memory given to + us by user and are not re-sizeable vectors. */ +#define HEAP_IS_STATIC (1) +} heap_header_t; + +/* Start of heap elements is always cache aligned. */ +#define HEAP_DATA_ALIGN (CLIB_CACHE_LINE_BYTES) + +always_inline heap_header_t * heap_header (void * v) +{ return vec_header (v, sizeof (heap_header_t)); } + +always_inline uword heap_header_bytes () +{ return vec_header_bytes (sizeof (heap_header_t)); } + +always_inline void heap_dup_header (heap_header_t * old, heap_header_t * new) +{ + uword i; + + new[0] = old[0]; + new->elts = vec_dup (new->elts); + new->free_elts = vec_dup (new->free_elts); + new->free_lists = vec_dup (new->free_lists); + for (i = 0; i < vec_len (new->free_lists); i++) + new->free_lists[i] = vec_dup (new->free_lists[i]); + new->used_elt_bitmap = clib_bitmap_dup (new->used_elt_bitmap); + new->small_free_elt_free_index = vec_dup (new->small_free_elt_free_index); +} + +/* Make a duplicate copy of a heap. */ +#define heap_dup(v) _heap_dup(v, vec_len (v) * sizeof (v[0])) + +always_inline void * _heap_dup (void * v_old, uword v_bytes) +{ + heap_header_t * h_old, * h_new; + void * v_new; + + h_old = heap_header (v_old); + + if (! v_old) + return v_old; + + v_new = 0; + v_new = _vec_resize (v_new, _vec_len (v_old), v_bytes, sizeof (heap_header_t), + HEAP_DATA_ALIGN); + h_new = heap_header (v_new); + heap_dup_header (h_old, h_new); + memcpy (v_new, v_old, v_bytes); + return v_new; +} + +always_inline uword heap_elts (void * v) +{ + heap_header_t * h = heap_header (v); + return h->used_count; +} + +uword heap_bytes (void * v); + +always_inline void * _heap_new (u32 len, u32 n_elt_bytes) +{ + void * v = _vec_resize (0, len, len*n_elt_bytes, + sizeof (heap_header_t), + HEAP_DATA_ALIGN); + heap_header (v)->elt_bytes = n_elt_bytes; + return v; +} + +#define heap_new(v) (v) = _heap_new (0, sizeof ((v)[0])) + +always_inline void +heap_set_format (void * v, format_function_t * format_elt) +{ + ASSERT (v); + heap_header (v)->format_elt = format_elt; +} + +always_inline void +heap_set_max_len (void * v, uword max_len) +{ + ASSERT (v); + heap_header (v)->max_len = max_len; +} + +always_inline uword heap_get_max_len (void * v) +{ return v ? heap_header (v)->max_len : 0; } + +/* Create fixed size heap with given block of memory. */ +always_inline void * +heap_create_from_memory (void * memory, uword max_len, uword elt_bytes) +{ + heap_header_t * h; + void * v; + + if (max_len * elt_bytes < sizeof (h[0])) + return 0; + + h = memory; + memset (h, 0, sizeof (h[0])); + h->max_len = max_len; + h->elt_bytes = elt_bytes; + h->flags = HEAP_IS_STATIC; + + v = (void *) (memory + heap_header_bytes ()); + _vec_len (v) = 0; + return v; +} + +/* Execute BODY for each allocated heap element. */ +#define heap_foreach(var,len,heap,body) \ +do { \ + if (vec_len (heap) > 0) \ + { \ + heap_header_t * _h = heap_header (heap); \ + heap_elt_t * _e = _h->elts + _h->head; \ + heap_elt_t * _end = _h->elts + _h->tail; \ + while (1) \ + { \ + if (! heap_is_free (_e)) \ + { \ + (var) = (heap) + heap_offset (_e); \ + (len) = heap_elt_size ((heap), _e); \ + do { body; } while (0); \ + } \ + if (_e == _end) \ + break; \ + _e = heap_next (_e); \ + } \ + } \ +} while (0) + +#define heap_elt_at_index(v,index) vec_elt_at_index(v,index) + +always_inline heap_elt_t * +heap_get_elt (void * v, uword handle) +{ + heap_header_t * h = heap_header (v); + heap_elt_t * e = vec_elt_at_index (h->elts, handle); + ASSERT (! heap_is_free (e)); + return e; +} + +#define heap_elt_with_handle(v,handle) \ +({ \ + heap_elt_t * _e = heap_get_elt ((v), (handle)); \ + (v) + heap_offset (_e); \ +}) + +always_inline uword +heap_is_free_handle (void * v, uword heap_handle) +{ + heap_header_t * h = heap_header (v); + heap_elt_t * e = vec_elt_at_index (h->elts, heap_handle); + return heap_is_free (e); +} + +extern uword heap_len (void * v, word handle); + +/* Low level allocation call. */ +extern void * _heap_alloc (void * v, uword size, uword alignment, + uword elt_bytes, + uword * offset, uword * handle); + +#define heap_alloc_aligned(v,size,align,handle) \ +({ \ + uword _o, _h; \ + uword _a = (align); \ + uword _s = (size); \ + (v) = _heap_alloc ((v), _s, _a, sizeof ((v)[0]), &_o, &_h); \ + (handle) = _h; \ + _o; \ +}) + +#define heap_alloc(v,size,handle) heap_alloc_aligned((v),(size),0,(handle)) + +extern void heap_dealloc (void * v, uword handle); +extern void heap_validate (void * v); + +/* Format heap internal data structures as string. */ +extern u8 * format_heap (u8 * s, va_list * va); + +void * _heap_free (void * v); + +#define heap_free(v) (v)=_heap_free(v) + +#endif /* included_heap_h */ |