diff options
Diffstat (limited to 'src/vppinfra')
| -rw-r--r-- | src/vppinfra/dlmalloc.c | 12 | ||||
| -rw-r--r-- | src/vppinfra/dlmalloc.h | 2 | ||||
| -rw-r--r-- | src/vppinfra/elf.h | 8 | ||||
| -rw-r--r-- | src/vppinfra/hash.c | 13 | ||||
| -rw-r--r-- | src/vppinfra/heap.c | 6 | ||||
| -rw-r--r-- | src/vppinfra/heap.h | 38 | ||||
| -rw-r--r-- | src/vppinfra/mem.h | 144 | ||||
| -rw-r--r-- | src/vppinfra/mem_dlmalloc.c | 152 | ||||
| -rw-r--r-- | src/vppinfra/pool.c | 6 | ||||
| -rw-r--r-- | src/vppinfra/pool.h | 366 | ||||
| -rw-r--r-- | src/vppinfra/ring.h | 10 | ||||
| -rw-r--r-- | src/vppinfra/serialize.c | 7 | ||||
| -rw-r--r-- | src/vppinfra/sparse_vec.h | 8 | ||||
| -rw-r--r-- | src/vppinfra/string.h | 19 | ||||
| -rw-r--r-- | src/vppinfra/test_heap.c | 13 | ||||
| -rw-r--r-- | src/vppinfra/test_vec.c | 3 | ||||
| -rw-r--r-- | src/vppinfra/types.h | 8 | ||||
| -rw-r--r-- | src/vppinfra/vec.c | 230 | ||||
| -rw-r--r-- | src/vppinfra/vec.h | 701 | ||||
| -rw-r--r-- | src/vppinfra/vec_bootstrap.h | 52 |
20 files changed, 866 insertions, 932 deletions
diff --git a/src/vppinfra/dlmalloc.c b/src/vppinfra/dlmalloc.c index 36c80b09b87..03e7d874032 100644 --- a/src/vppinfra/dlmalloc.c +++ b/src/vppinfra/dlmalloc.c @@ -3420,7 +3420,7 @@ void* dlcalloc(size_t n_elements, size_t elem_size) { /* ------------ Internal support for realloc, memalign, etc -------------- */ /* Try to realloc; only in-place unless can_move true */ -static mchunkptr try_realloc_chunk(mstate m, mchunkptr p, size_t nb, +static CLIB_NOSANITIZE_ADDR mchunkptr try_realloc_chunk(mstate m, mchunkptr p, size_t nb, int can_move) { mchunkptr newp = 0; size_t oldsize = chunksize(p); @@ -4118,7 +4118,7 @@ void mspace_get_address_and_size (mspace msp, char **addrp, size_t *sizep) *sizep = this_seg->size; } -CLIB_NOSANITIZE_ADDR __clib_export +CLIB_NOSANITIZE_ADDR int mspace_is_heap_object (mspace msp, void *p) { msegment *this_seg; @@ -4185,7 +4185,7 @@ int mspace_is_traced (mspace msp) return 0; } -CLIB_NOSANITIZE_ADDR __clib_export +CLIB_NOSANITIZE_ADDR void* mspace_get_aligned (mspace msp, unsigned long n_user_data_bytes, unsigned long align, @@ -4265,7 +4265,7 @@ void* mspace_get_aligned (mspace msp, return (void *) searchp; } -CLIB_NOSANITIZE_ADDR __clib_export +CLIB_NOSANITIZE_ADDR void mspace_put (mspace msp, void *p_arg) { char *object_header; @@ -4315,7 +4315,7 @@ void mspace_put_no_offset (mspace msp, void *p_arg) mspace_free (msp, p_arg); } -CLIB_NOSANITIZE_ADDR __clib_export +CLIB_NOSANITIZE_ADDR size_t mspace_usable_size_with_delta (const void *p) { size_t usable_size; @@ -4623,6 +4623,7 @@ void* mspace_realloc(mspace msp, void* oldmem, size_t bytes) { return mem; } +CLIB_NOSANITIZE_ADDR void* mspace_realloc_in_place(mspace msp, void* oldmem, size_t bytes) { void* mem = 0; if (oldmem != 0) { @@ -4655,6 +4656,7 @@ void* mspace_realloc_in_place(mspace msp, void* oldmem, size_t bytes) { return mem; } +CLIB_NOSANITIZE_ADDR void* mspace_memalign(mspace msp, size_t alignment, size_t bytes) { mstate ms = (mstate)msp; if (!ok_magic(ms)) { diff --git a/src/vppinfra/dlmalloc.h b/src/vppinfra/dlmalloc.h index b8adf74831d..5fcaf7c30ca 100644 --- a/src/vppinfra/dlmalloc.h +++ b/src/vppinfra/dlmalloc.h @@ -1447,6 +1447,8 @@ DLMALLOC_EXPORT int mspace_trim(mspace msp, size_t pad); */ DLMALLOC_EXPORT int mspace_mallopt(int, int); +DLMALLOC_EXPORT void* mspace_realloc_in_place (mspace msp, void *oldmem, size_t bytes); + DLMALLOC_EXPORT void* mspace_get_aligned (mspace msp, unsigned long n_user_data_bytes, unsigned long align, diff --git a/src/vppinfra/elf.h b/src/vppinfra/elf.h index cceb13e256b..8d9893120f5 100644 --- a/src/vppinfra/elf.h +++ b/src/vppinfra/elf.h @@ -967,11 +967,9 @@ elf_get_section_contents (elf_main_t * em, if (vec_len (s->contents) > 0) { /* Make vector copy of contents with given element size. */ - result = _vec_resize (result, - vec_len (s->contents) / elt_size, - vec_len (s->contents), - /* header_bytes */ 0, - /* align */ 0); + result = + _vec_realloc (result, vec_len (s->contents) / elt_size, elt_size, + /* header_bytes */ 0, /* align */ 0, 0); clib_memcpy (result, s->contents, vec_len (s->contents)); } diff --git a/src/vppinfra/hash.c b/src/vppinfra/hash.c index 7c1dcd4c57b..df740c5f659 100644 --- a/src/vppinfra/hash.c +++ b/src/vppinfra/hash.c @@ -285,9 +285,7 @@ set_indirect (void *v, hash_pair_indirect_t * pi, uword key, new_len = len + 1; if (new_len * hash_pair_bytes (h) > (1ULL << log2_bytes)) { - pi->pairs = clib_mem_realloc (pi->pairs, - 1ULL << (log2_bytes + 1), - 1ULL << log2_bytes); + pi->pairs = clib_mem_realloc (pi->pairs, 1ULL << (log2_bytes + 1)); log2_bytes++; } @@ -560,13 +558,8 @@ _hash_create (uword elts, hash_t * h_user) if (h_user) log2_pair_size = h_user->log2_pair_size; - v = _vec_resize ((void *) 0, - /* vec len: */ elts, - /* data bytes: */ - (elts << log2_pair_size) * sizeof (hash_pair_t), - /* header bytes: */ - sizeof (h[0]), - /* alignment */ sizeof (hash_pair_t)); + v = _vec_realloc (0, elts, (1 << log2_pair_size) * sizeof (hash_pair_t), + sizeof (h[0]), sizeof (hash_pair_t), 0); h = hash_header (v); if (h_user) diff --git a/src/vppinfra/heap.c b/src/vppinfra/heap.c index bc3e8cb79c9..47b6cf53214 100644 --- a/src/vppinfra/heap.c +++ b/src/vppinfra/heap.c @@ -422,10 +422,8 @@ _heap_alloc (void *v, 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); + v = _vec_realloc (v, offset + align_size, elt_bytes, sizeof (h[0]), + HEAP_DATA_ALIGN, 0); else _vec_len (v) += align_size; diff --git a/src/vppinfra/heap.h b/src/vppinfra/heap.h index 8b430644dbd..f496fe07b2e 100644 --- a/src/vppinfra/heap.h +++ b/src/vppinfra/heap.h @@ -163,12 +163,6 @@ heap_header (void *v) return vec_header (v); } -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) { @@ -198,10 +192,8 @@ _heap_dup (void *v_old, uword v_bytes) 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); + v_new = _vec_realloc (0, _vec_len (v_old), 1, sizeof (heap_header_t), + HEAP_DATA_ALIGN, 0); h_new = heap_header (v_new); heap_dup_header (h_old, h_new); clib_memcpy_fast (v_new, v_old, v_bytes); @@ -220,9 +212,8 @@ uword heap_bytes (void *v); always_inline void * _heap_new (u32 len, u32 n_elt_bytes) { - void *v = _vec_resize ((void *) 0, len, (uword) len * n_elt_bytes, - sizeof (heap_header_t), - HEAP_DATA_ALIGN); + void *v = _vec_realloc ((void *) 0, len, n_elt_bytes, sizeof (heap_header_t), + HEAP_DATA_ALIGN, 0); heap_header (v)->elt_bytes = n_elt_bytes; return v; } @@ -249,27 +240,6 @@ 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; - clib_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 { \ diff --git a/src/vppinfra/mem.h b/src/vppinfra/mem.h index dfe8de93626..1a813be68b6 100644 --- a/src/vppinfra/mem.h +++ b/src/vppinfra/mem.h @@ -53,6 +53,8 @@ #define CLIB_MAX_NUMAS 16 #define CLIB_MEM_VM_MAP_FAILED ((void *) ~0) #define CLIB_MEM_ERROR (-1) +#define CLIB_MEM_LOG2_MIN_ALIGN (3) +#define CLIB_MEM_MIN_ALIGN (1 << CLIB_MEM_LOG2_MIN_ALIGN) typedef enum { @@ -93,9 +95,10 @@ typedef struct _clib_mem_vm_map_hdr struct _clib_mem_vm_map_hdr *prev, *next; } clib_mem_vm_map_hdr_t; -#define foreach_clib_mem_heap_flag \ - _(0, LOCKED, "locked") \ - _(1, UNMAP_ON_DESTROY, "unmap-on-destroy") +#define foreach_clib_mem_heap_flag \ + _ (0, LOCKED, "locked") \ + _ (1, UNMAP_ON_DESTROY, "unmap-on-destroy") \ + _ (2, TRACED, "traced") typedef enum { @@ -213,77 +216,13 @@ clib_mem_set_thread_index (void) ASSERT (__os_thread_index > 0); } -always_inline uword -clib_mem_size_nocheck (void *p) -{ - size_t mspace_usable_size_with_delta (const void *p); - return mspace_usable_size_with_delta (p); -} - -/* Memory allocator which may call os_out_of_memory() if it fails */ -always_inline void * -clib_mem_alloc_aligned_at_offset (uword size, uword align, uword align_offset, - int os_out_of_memory_on_failure) -{ - void *mspace_get_aligned (void *msp, unsigned long n_user_data_bytes, - unsigned long align, unsigned long align_offset); - clib_mem_heap_t *h = clib_mem_get_per_cpu_heap (); - void *p; - - if (align_offset > align) - { - if (align > 0) - align_offset %= align; - else - align_offset = align; - } - - p = mspace_get_aligned (h->mspace, size, align, align_offset); - - if (PREDICT_FALSE (0 == p)) - { - if (os_out_of_memory_on_failure) - os_out_of_memory (); - return 0; - } - - CLIB_MEM_UNPOISON (p, size); - return p; -} - -/* Memory allocator which calls os_out_of_memory() when it fails */ -always_inline void * -clib_mem_alloc (uword size) -{ - return clib_mem_alloc_aligned_at_offset (size, /* align */ 1, - /* align_offset */ 0, - /* os_out_of_memory */ 1); -} - -always_inline void * -clib_mem_alloc_aligned (uword size, uword align) -{ - return clib_mem_alloc_aligned_at_offset (size, align, /* align_offset */ 0, - /* os_out_of_memory */ 1); -} - /* Memory allocator which calls os_out_of_memory() when it fails */ -always_inline void * -clib_mem_alloc_or_null (uword size) -{ - return clib_mem_alloc_aligned_at_offset (size, /* align */ 1, - /* align_offset */ 0, - /* os_out_of_memory */ 0); -} - -always_inline void * -clib_mem_alloc_aligned_or_null (uword size, uword align) -{ - return clib_mem_alloc_aligned_at_offset (size, align, /* align_offset */ 0, - /* os_out_of_memory */ 0); -} - - +void *clib_mem_alloc (uword size); +void *clib_mem_alloc_aligned (uword size, uword align); +void *clib_mem_alloc_or_null (uword size); +void *clib_mem_alloc_aligned_or_null (uword size, uword align); +void *clib_mem_realloc (void *p, uword new_size); +void *clib_mem_realloc_aligned (void *p, uword new_size, uword align); /* Memory allocator which panics when it fails. Use macro so that clib_panic macro can expand __FUNCTION__ and __LINE__. */ @@ -302,61 +241,10 @@ clib_mem_alloc_aligned_or_null (uword size, uword align) /* Alias to stack allocator for naming consistency. */ #define clib_mem_alloc_stack(bytes) __builtin_alloca(bytes) -always_inline uword -clib_mem_is_heap_object (void *p) -{ - int mspace_is_heap_object (void *msp, void *p); - clib_mem_heap_t *h = clib_mem_get_per_cpu_heap (); - return mspace_is_heap_object (h->mspace, p); -} - -always_inline void -clib_mem_free (void *p) -{ - void mspace_put (void *msp, void *p_arg); - clib_mem_heap_t *h = clib_mem_get_per_cpu_heap (); - - /* Make sure object is in the correct heap. */ - ASSERT (clib_mem_is_heap_object (p)); - - CLIB_MEM_POISON (p, clib_mem_size_nocheck (p)); - - mspace_put (h->mspace, p); -} - -always_inline void * -clib_mem_realloc (void *p, uword new_size, uword old_size) -{ - /* By default use alloc, copy and free to emulate realloc. */ - void *q = clib_mem_alloc (new_size); - if (q) - { - uword copy_size; - if (old_size < new_size) - copy_size = old_size; - else - copy_size = new_size; - clib_memcpy_fast (q, p, copy_size); - clib_mem_free (p); - } - return q; -} - -always_inline uword -clib_mem_size (void *p) -{ - ASSERT (clib_mem_is_heap_object (p)); - return clib_mem_size_nocheck (p); -} - -always_inline void -clib_mem_free_s (void *p) -{ - uword size = clib_mem_size (p); - CLIB_MEM_UNPOISON (p, size); - memset_s_inline (p, size, 0, size); - clib_mem_free (p); -} +uword clib_mem_is_heap_object (void *p); +void clib_mem_free (void *p); +uword clib_mem_size (void *p); +void clib_mem_free_s (void *p); always_inline clib_mem_heap_t * clib_mem_get_heap (void) diff --git a/src/vppinfra/mem_dlmalloc.c b/src/vppinfra/mem_dlmalloc.c index e2a0f71e084..4d6d11f3489 100644 --- a/src/vppinfra/mem_dlmalloc.c +++ b/src/vppinfra/mem_dlmalloc.c @@ -464,7 +464,7 @@ format_clib_mem_heap (u8 * s, va_list * va) format_white_space, indent + 2, format_msize, mi.usmblks); } - if (mspace_is_traced (heap->mspace)) + if (heap->flags & CLIB_MEM_HEAP_F_TRACED) s = format (s, "\n%U", format_mheap_trace, tm, verbose); return s; } @@ -493,7 +493,10 @@ uword clib_mem_validate_serial = 0; __clib_export void mheap_trace (clib_mem_heap_t * h, int enable) { - (void) mspace_enable_disable_trace (h->mspace, enable); + if (enable) + h->flags |= CLIB_MEM_HEAP_F_TRACED; + else + h->flags &= ~CLIB_MEM_HEAP_F_TRACED; if (enable == 0) mheap_trace_main_free (&mheap_trace_main); @@ -518,7 +521,7 @@ int clib_mem_is_traced (void) { clib_mem_heap_t *h = clib_mem_get_heap (); - return mspace_is_traced (h->mspace); + return (h->flags &= CLIB_MEM_HEAP_F_TRACED) != 0; } __clib_export uword @@ -594,10 +597,139 @@ clib_mem_get_heap_size (clib_mem_heap_t * heap) return heap->size; } -/* - * fd.io coding-style-patch-verification: ON - * - * Local Variables: - * eval: (c-set-style "gnu") - * End: - */ +/* Memory allocator which may call os_out_of_memory() if it fails */ +static void * +clib_mem_alloc_inline (uword size, uword align, + int os_out_of_memory_on_failure) +{ + clib_mem_heap_t *h = clib_mem_get_per_cpu_heap (); + void *p; + + align = clib_max (CLIB_MEM_MIN_ALIGN, align); + + p = mspace_memalign (h->mspace, align, size); + + if (PREDICT_FALSE (0 == p)) + { + if (os_out_of_memory_on_failure) + os_out_of_memory (); + return 0; + } + + if (PREDICT_FALSE (h->flags & CLIB_MEM_HEAP_F_TRACED)) + mheap_get_trace (pointer_to_uword (p), clib_mem_size (p)); + + CLIB_MEM_UNPOISON (p, size); + return p; +} + +/* Memory allocator which calls os_out_of_memory() when it fails */ +__clib_export void * +clib_mem_alloc (uword size) +{ + return clib_mem_alloc_inline (size, CLIB_MEM_MIN_ALIGN, + /* os_out_of_memory */ 1); +} + +__clib_export void * +clib_mem_alloc_aligned (uword size, uword align) +{ + return clib_mem_alloc_inline (size, align, + /* os_out_of_memory */ 1); +} + +/* Memory allocator which calls os_out_of_memory() when it fails */ +__clib_export void * +clib_mem_alloc_or_null (uword size) +{ + return clib_mem_alloc_inline (size, CLIB_MEM_MIN_ALIGN, + /* os_out_of_memory */ 0); +} + +__clib_export void * +clib_mem_alloc_aligned_or_null (uword size, uword align) +{ + return clib_mem_alloc_inline (size, align, + /* os_out_of_memory */ 0); +} + +__clib_export void * +clib_mem_realloc_aligned (void *p, uword new_size, uword align) +{ + uword old_alloc_size; + clib_mem_heap_t *h = clib_mem_get_per_cpu_heap (); + void *new; + + ASSERT (count_set_bits (align) == 1); + + old_alloc_size = p ? mspace_usable_size (p) : 0; + + if (new_size == old_alloc_size) + return p; + + if (p && pointer_is_aligned (p, align) && + mspace_realloc_in_place (h->mspace, p, new_size)) + { + CLIB_MEM_UNPOISON (p, new_size); + } + else + { + new = clib_mem_alloc_inline (new_size, align, 1); + + CLIB_MEM_UNPOISON (new, new_size); + if (old_alloc_size) + { + CLIB_MEM_UNPOISON (p, old_alloc_size); + clib_memcpy_fast (new, p, clib_min (new_size, old_alloc_size)); + clib_mem_free (p); + } + p = new; + } + + return p; +} + +__clib_export void * +clib_mem_realloc (void *p, uword new_size) +{ + return clib_mem_realloc_aligned (p, new_size, CLIB_MEM_MIN_ALIGN); +} + +__clib_export uword +clib_mem_is_heap_object (void *p) +{ + int mspace_is_heap_object (void *msp, void *p); + clib_mem_heap_t *h = clib_mem_get_per_cpu_heap (); + return mspace_is_heap_object (h->mspace, p); +} + +__clib_export void +clib_mem_free (void *p) +{ + clib_mem_heap_t *h = clib_mem_get_per_cpu_heap (); + uword size = clib_mem_size (p); + + /* Make sure object is in the correct heap. */ + ASSERT (clib_mem_is_heap_object (p)); + + if (PREDICT_FALSE (h->flags & CLIB_MEM_HEAP_F_TRACED)) + mheap_put_trace (pointer_to_uword (p), size); + CLIB_MEM_POISON (p, clib_mem_size (p)); + + mspace_free (h->mspace, p); +} + +__clib_export uword +clib_mem_size (void *p) +{ + return mspace_usable_size (p); +} + +__clib_export void +clib_mem_free_s (void *p) +{ + uword size = clib_mem_size (p); + CLIB_MEM_UNPOISON (p, size); + memset_s_inline (p, size, 0, size); + clib_mem_free (p); +} diff --git a/src/vppinfra/pool.c b/src/vppinfra/pool.c index ff7278b1dcd..2bbfe60d320 100644 --- a/src/vppinfra/pool.c +++ b/src/vppinfra/pool.c @@ -38,7 +38,7 @@ #include <vppinfra/pool.h> __clib_export void -_pool_init_fixed (void **pool_ptr, u32 elt_size, u32 max_elts) +_pool_init_fixed (void **pool_ptr, uword elt_size, uword max_elts, uword align) { uword *b; pool_header_t *ph; @@ -48,9 +48,7 @@ _pool_init_fixed (void **pool_ptr, u32 elt_size, u32 max_elts) ASSERT (elt_size); ASSERT (max_elts); - v = - vec_resize_allocate_memory (0, max_elts, elt_size * max_elts, - sizeof (pool_header_t), CLIB_CACHE_LINE_BYTES); + v = _vec_realloc (0, max_elts, elt_size, sizeof (pool_header_t), align, 0); ph = pool_header (v); ph->max_elts = max_elts; diff --git a/src/vppinfra/pool.h b/src/vppinfra/pool.h index 45265b31cbc..32360daeffc 100644 --- a/src/vppinfra/pool.h +++ b/src/vppinfra/pool.h @@ -63,10 +63,6 @@ typedef struct } pool_header_t; -/** Align pool header so that pointers are naturally aligned. */ -#define pool_aligned_header_bytes \ - round_pow2 (sizeof (pool_header_t), sizeof (void *)) - /** Get pool header from user pool pointer */ always_inline pool_header_t * pool_header (void *v) @@ -74,14 +70,12 @@ pool_header (void *v) return vec_header (v); } -extern void _pool_init_fixed (void **, u32, u32); -extern void fpool_free (void *); +void _pool_init_fixed (void **pool_ptr, uword elt_sz, uword max_elts, + uword align); /** initialize a fixed-size, preallocated pool */ -#define pool_init_fixed(pool,max_elts) \ -{ \ - _pool_init_fixed((void **)&(pool),sizeof(pool[0]),max_elts); \ -} +#define pool_init_fixed(P, E) \ + _pool_init_fixed ((void **) &(P), _vec_elt_sz (P), E, _vec_align (P, 0)); /** Validate a pool */ always_inline void @@ -99,23 +93,6 @@ pool_validate (void *v) ASSERT (clib_bitmap_get (p->free_bitmap, p->free_indices[i]) == 1); } -always_inline void -pool_header_validate_index (void *v, uword index) -{ - pool_header_t *p = pool_header (v); - - if (v) - vec_validate (p->free_bitmap, index / BITS (uword)); -} - -#define pool_validate_index(v,i) \ -do { \ - uword __pool_validate_index = (i); \ - vec_validate_ha ((v), __pool_validate_index, \ - pool_aligned_header_bytes, /* align */ 0); \ - pool_header_validate_index ((v), __pool_validate_index); \ -} while (0) - /** Number of active elements in a pool. * @return Number of active elements in a pool */ @@ -162,66 +139,81 @@ pool_header_bytes (void *v) #define pool_max_len(P) vec_max_len (P) /** Number of free elements in pool */ -#define pool_free_elts(P) \ - ({ \ - pool_header_t *_pool_var (p) = pool_header (P); \ - uword n_free = 0; \ - if (P) \ - { \ - n_free += vec_len (_pool_var (p)->free_indices); \ - /* Fixed-size pools have max_elts set non-zero */ \ - if (_pool_var (p)->max_elts == 0) \ - n_free += pool_max_len (P) - vec_len (P); \ - } \ - n_free; \ - }) +static_always_inline uword +_pool_free_elts (void *p, uword elt_sz) +{ + pool_header_t *ph; + uword n_free; + + if (p == 0) + return 0; + + ph = pool_header (p); + + n_free = vec_len (ph->free_indices); + + /* Fixed-size pools have max_elts set non-zero */ + if (ph->max_elts == 0) + n_free += _vec_max_len (p, elt_sz) - vec_len (p); + + return n_free; +} + +#define pool_free_elts(P) _pool_free_elts ((void *) (P), _vec_elt_sz (P)) /** Allocate an object E from a pool P (general version). First search free list. If nothing is free extend vector of objects. */ + +static_always_inline void +_pool_get (void **pp, void **ep, uword align, int zero, uword elt_sz) +{ + uword len = 0; + void *p = pp[0]; + void *e; + + if (p) + { + pool_header_t *ph = pool_header (p); + uword n_free = vec_len (ph->free_indices); + + if (n_free) + { + uword index = ph->free_indices[n_free - 1]; + e = p + index * elt_sz; + ph->free_bitmap = + clib_bitmap_andnoti_notrim (ph->free_bitmap, index); + _vec_len (ph->free_indices) = n_free - 1; + CLIB_MEM_UNPOISON (e, elt_sz); + goto done; + } + + if (ph->max_elts) + { + clib_warning ("can't expand fixed-size pool"); + os_out_of_memory (); + } + } + + len = vec_len (p); + + /* Nothing on free list, make a new element and return it. */ + p = + _vec_realloc_inline (p, len + 1, elt_sz, sizeof (pool_header_t), align, 0); + e = p + len * elt_sz; + + _vec_update_pointer (pp, p); + +done: + ep[0] = e; + if (zero) + clib_memset_u8 (e, 0, elt_sz); +} + #define _pool_get_aligned_internal(P, E, A, Z) \ - do \ - { \ - pool_header_t *_pool_var (p) = pool_header (P); \ - uword _pool_var (l); \ - \ - STATIC_ASSERT (A == 0 || ((A % sizeof (P[0])) == 0) || \ - ((sizeof (P[0]) % A) == 0), \ - "Pool aligned alloc of incorrectly sized object"); \ - _pool_var (l) = 0; \ - if (P) \ - _pool_var (l) = vec_len (_pool_var (p)->free_indices); \ - \ - if (_pool_var (l) > 0) \ - { \ - /* Return free element from free list. */ \ - uword _pool_var (i) = \ - _pool_var (p)->free_indices[_pool_var (l) - 1]; \ - (E) = (P) + _pool_var (i); \ - _pool_var (p)->free_bitmap = clib_bitmap_andnoti_notrim ( \ - _pool_var (p)->free_bitmap, _pool_var (i)); \ - _vec_len (_pool_var (p)->free_indices) = _pool_var (l) - 1; \ - CLIB_MEM_UNPOISON ((E), sizeof ((E)[0])); \ - } \ - else \ - { \ - /* fixed-size, preallocated pools cannot expand */ \ - if ((P) && _pool_var (p)->max_elts) \ - { \ - clib_warning ("can't expand fixed-size pool"); \ - os_out_of_memory (); \ - } \ - /* Nothing on free list, make a new element and return it. */ \ - P = _vec_resize (P, /* length_increment */ 1, \ - /* new size */ (vec_len (P) + 1) * sizeof (P[0]), \ - pool_aligned_header_bytes, /* align */ (A)); \ - E = vec_end (P) - 1; \ - } \ - if (Z) \ - memset (E, 0, sizeof (*E)); \ - } \ - while (0) + _pool_get ((void **) &(P), (void **) &(E), _vec_align (P, A), Z, \ + _vec_elt_sz (P)) /** Allocate an object E from a pool P with alignment A */ #define pool_get_aligned(P,E,A) _pool_get_aligned_internal(P,E,A,0) @@ -236,7 +228,7 @@ pool_header_bytes (void *v) #define pool_get_zero(P,E) pool_get_aligned_zero(P,E,0) always_inline int -_pool_get_will_expand (void *p, uword elt_size) +_pool_get_will_expand (void *p, uword elt_sz) { pool_header_t *ph; uword len; @@ -255,13 +247,13 @@ _pool_get_will_expand (void *p, uword elt_size) if (len > 0) return 0; - return _vec_resize_will_expand (p, 1, elt_size); + return _vec_resize_will_expand (p, 1, elt_sz); } #define pool_get_will_expand(P) _pool_get_will_expand (P, sizeof ((P)[0])) always_inline int -_pool_put_will_expand (void *p, uword index, uword elt_size) +_pool_put_will_expand (void *p, uword index, uword elt_sz) { pool_header_t *ph = pool_header (p); @@ -277,81 +269,112 @@ _pool_put_will_expand (void *p, uword index, uword elt_size) #define pool_put_will_expand(P, E) _pool_put_will_expand (P, (E) - (P), sizeof ((P)[0]) /** Use free bitmap to query whether given element is free. */ -#define pool_is_free(P,E) \ -({ \ - pool_header_t * _pool_var (p) = pool_header (P); \ - uword _pool_var (i) = (E) - (P); \ - (_pool_var (i) < vec_len (P)) ? clib_bitmap_get (_pool_var (p)->free_bitmap, _pool_i) : 1; \ -}) +static_always_inline int +pool_is_free_index (void *p, uword index) +{ + pool_header_t *ph = pool_header (p); + return index < vec_len (p) ? clib_bitmap_get (ph->free_bitmap, index) : 1; +} -/** Use free bitmap to query whether given index is free */ -#define pool_is_free_index(P,I) pool_is_free((P),(P)+(I)) +#define pool_is_free(P, E) pool_is_free_index ((void *) (P), (E) - (P)) /** Free an object E in pool P. */ -#define pool_put(P, E) \ - do \ - { \ - typeof (P) _pool_var (p__) = (P); \ - typeof (E) _pool_var (e__) = (E); \ - pool_header_t *_pool_var (p) = pool_header (_pool_var (p__)); \ - uword _pool_var (l) = _pool_var (e__) - _pool_var (p__); \ - if (_pool_var (p)->max_elts == 0) \ - ASSERT (vec_is_member (_pool_var (p__), _pool_var (e__))); \ - ASSERT (!pool_is_free (_pool_var (p__), _pool_var (e__))); \ - \ - /* Add element to free bitmap and to free list. */ \ - _pool_var (p)->free_bitmap = \ - clib_bitmap_ori_notrim (_pool_var (p)->free_bitmap, _pool_var (l)); \ - \ - /* Preallocated pool? */ \ - if (_pool_var (p)->max_elts) \ - { \ - ASSERT (_pool_var (l) < _pool_var (p)->max_elts); \ - _pool_var (p) \ - ->free_indices[_vec_len (_pool_var (p)->free_indices)] = \ - _pool_var (l); \ - _vec_len (_pool_var (p)->free_indices) += 1; \ - } \ - else \ - vec_add1 (_pool_var (p)->free_indices, _pool_var (l)); \ - \ - CLIB_MEM_POISON (_pool_var (e__), sizeof (_pool_var (e__)[0])); \ - } \ - while (0) - -/** Free pool element with given index. */ -#define pool_put_index(p,i) \ -do { \ - typeof (p) _e = (p) + (i); \ - pool_put (p, _e); \ -} while (0) +static_always_inline void +_pool_put_index (void *p, uword index, uword elt_sz) +{ + pool_header_t *ph = pool_header (p); + + ASSERT (index < ph->max_elts ? ph->max_elts : vec_len (p)); + ASSERT (!pool_is_free_index (p, index)); + + /* Add element to free bitmap and to free list. */ + ph->free_bitmap = clib_bitmap_ori_notrim (ph->free_bitmap, index); + + /* Preallocated pool? */ + if (ph->max_elts) + { + ph->free_indices[_vec_len (ph->free_indices)] = index; + _vec_len (ph->free_indices) += 1; + } + else + vec_add1 (ph->free_indices, index); + + CLIB_MEM_POISON (p + index * elt_sz, elt_sz); +} + +#define pool_put_index(P, I) _pool_put_index ((void *) (P), I, _vec_elt_sz (P)) +#define pool_put(P, E) pool_put_index (P, (E) - (P)) /** Allocate N more free elements to pool (general version). */ -#define pool_alloc_aligned(P,N,A) \ -do { \ - pool_header_t * _p; \ - \ - if ((P)) \ - { \ - _p = pool_header (P); \ - if (_p->max_elts) \ - { \ - clib_warning ("Can't expand fixed-size pool"); \ - os_out_of_memory(); \ - } \ - } \ - \ - (P) = _vec_resize ((P), 0, (vec_len (P) + (N)) * sizeof (P[0]), \ - pool_aligned_header_bytes, \ - (A)); \ - _p = pool_header (P); \ - vec_resize (_p->free_indices, (N)); \ - _vec_len (_p->free_indices) -= (N); \ -} while (0) + +static_always_inline void +_pool_alloc (void **pp, uword n_elts, uword align, uword elt_sz) +{ + pool_header_t *ph = pool_header (pp[0]); + uword len = vec_len (pp[0]); + + if (ph && ph->max_elts) + { + clib_warning ("Can't expand fixed-size pool"); + os_out_of_memory (); + } + + pp[0] = _vec_realloc_inline (pp[0], len + n_elts, elt_sz, + sizeof (pool_header_t), align, 0); + _vec_len (pp[0]) = len; + CLIB_MEM_POISON (pp[0] + len * elt_sz, n_elts * elt_sz); + + ph = pool_header (pp[0]); + vec_resize (ph->free_indices, n_elts); + _vec_len (ph->free_indices) -= n_elts; + clib_bitmap_vec_validate (ph->free_bitmap, len + n_elts - 1); +} + +#define pool_alloc_aligned(P, N, A) \ + _pool_alloc ((void **) &(P), N, _vec_align (P, A), _vec_elt_sz (P)) /** Allocate N more free elements to pool (unspecified alignment). */ #define pool_alloc(P,N) pool_alloc_aligned(P,N,0) +static_always_inline void * +_pool_dup (void *p, uword align, uword elt_sz) +{ + pool_header_t *nph, *ph = pool_header (p); + uword len = vec_len (p); + void *n; + + if (ph && ph->max_elts) + { + clib_warning ("Can't expand fixed-size pool"); + os_out_of_memory (); + } + + n = _vec_realloc_inline (0, len, elt_sz, sizeof (pool_header_t), align, 0); + nph = pool_header (n); + clib_memset_u8 (nph, 0, sizeof (vec_header_t)); + + if (len) + { + u32 *fi; + vec_foreach (fi, ph->free_indices) + CLIB_MEM_UNPOISON (p + elt_sz * fi[0], elt_sz); + + clib_memcpy_fast (n, p, len * elt_sz); + + nph->free_bitmap = clib_bitmap_dup (ph->free_bitmap); + nph->free_indices = vec_dup (ph->free_indices); + + vec_foreach (fi, ph->free_indices) + { + uword offset = elt_sz * fi[0]; + CLIB_MEM_POISON (p + offset, elt_sz); + CLIB_MEM_POISON (n + offset, elt_sz); + } + } + + return n; +} + /** * Return copy of pool with alignment * @@ -359,30 +382,9 @@ do { \ * @param A alignment (may be zero) * @return copy of pool */ + #define pool_dup_aligned(P, A) \ - ({ \ - typeof (P) _pool_var (new) = 0; \ - pool_header_t *_pool_var (ph), *_pool_var (new_ph); \ - u32 _pool_var (n) = pool_len (P); \ - if ((P)) \ - { \ - _pool_var (new) = _vec_resize (_pool_var (new), _pool_var (n), \ - _pool_var (n) * sizeof ((P)[0]), \ - pool_aligned_header_bytes, (A)); \ - CLIB_MEM_OVERFLOW_PUSH ((P), _pool_var (n) * sizeof ((P)[0])); \ - clib_memcpy_fast (_pool_var (new), (P), \ - _pool_var (n) * sizeof ((P)[0])); \ - CLIB_MEM_OVERFLOW_POP (); \ - _pool_var (ph) = pool_header (P); \ - _pool_var (new_ph) = pool_header (_pool_var (new)); \ - _pool_var (new_ph)->free_bitmap = \ - clib_bitmap_dup (_pool_var (ph)->free_bitmap); \ - _pool_var (new_ph)->free_indices = \ - vec_dup (_pool_var (ph)->free_indices); \ - _pool_var (new_ph)->max_elts = _pool_var (ph)->max_elts; \ - } \ - _pool_var (new); \ - }) + _pool_dup (P, _vec_align (P, A), _vec_elt_sz (P)) /** * Return copy of pool without alignment @@ -393,18 +395,19 @@ do { \ #define pool_dup(P) pool_dup_aligned(P,0) /** Low-level free pool operator (do not call directly). */ -always_inline void * -_pool_free (void *v) +always_inline void +_pool_free (void **v) { - pool_header_t *p = pool_header (v); - if (!v) - return v; + pool_header_t *p = pool_header (v[0]); + if (!p) + return; + clib_bitmap_free (p->free_bitmap); vec_free (p->free_indices); - vec_free (v); - return 0; + _vec_free (v); } +#define pool_free(p) _pool_free ((void **) &(p)) static_always_inline uword pool_get_first_index (void *pool) @@ -420,9 +423,6 @@ pool_get_next_index (void *pool, uword last) return clib_bitmap_next_clear (h->free_bitmap, last + 1); } -/** Free a pool. */ -#define pool_free(p) (p) = _pool_free(p) - /** Optimized iteration through pool. @param LO pointer to first element in chunk diff --git a/src/vppinfra/ring.h b/src/vppinfra/ring.h index 52b4261e4e6..d7e19156482 100644 --- a/src/vppinfra/ring.h +++ b/src/vppinfra/ring.h @@ -38,11 +38,11 @@ clib_ring_new_inline (void **p, u32 elt_bytes, u32 size, u32 align) void *v; clib_ring_header_t *h; - v = _vec_resize ((void *) 0, - /* length increment */ size, - /* data bytes */ elt_bytes * size, - /* header bytes */ sizeof (h[0]), - /* data align */ align); + v = _vec_realloc (0, + /* length increment */ size, + /* data bytes */ elt_bytes, + /* header bytes */ sizeof (h[0]), + /* data align */ align, 0); h = clib_ring_header (v); h->next = 0; diff --git a/src/vppinfra/serialize.c b/src/vppinfra/serialize.c index 64509254b5d..95eca96758a 100644 --- a/src/vppinfra/serialize.c +++ b/src/vppinfra/serialize.c @@ -313,8 +313,8 @@ unserialize_vector_ha (serialize_main_t * m, if (l > max_length) serialize_error (&m->header, clib_error_create ("bad vector length %d", l)); - p = v = _vec_resize ((void *) 0, l, (uword) l * elt_bytes, header_bytes, - /* align */ align); + p = v = _vec_realloc ((void *) 0, l, elt_bytes, header_bytes, + /* align */ align, 0); while (l != 0) { @@ -444,8 +444,7 @@ unserialize_pool_helper (serialize_main_t * m, return 0; } - v = _vec_resize ((void *) 0, l, (uword) l * elt_bytes, sizeof (p[0]), - align); + v = _vec_realloc ((void *) 0, l, elt_bytes, sizeof (p[0]), align, 0); p = pool_header (v); vec_unserialize (m, &p->free_indices, unserialize_vec_32); diff --git a/src/vppinfra/sparse_vec.h b/src/vppinfra/sparse_vec.h index 4bc2cbdeaea..6cab868a8b2 100644 --- a/src/vppinfra/sparse_vec.h +++ b/src/vppinfra/sparse_vec.h @@ -76,11 +76,9 @@ sparse_vec_new (uword elt_bytes, uword sparse_index_bits) ASSERT (sparse_index_bits <= 16); - v = _vec_resize ((void *) 0, - /* length increment */ 8, - /* data bytes */ 8 * elt_bytes, - /* header bytes */ sizeof (h[0]), - /* data align */ 0); + v = _vec_realloc (0, /* data bytes */ 8, elt_bytes, + /* header bytes */ sizeof (h[0]), /* data align */ 0, + /* heap */ 0); /* Make space for invalid entry (entry 0). */ _vec_len (v) = 1; diff --git a/src/vppinfra/string.h b/src/vppinfra/string.h index 0b187672816..0d8b1e6cb25 100644 --- a/src/vppinfra/string.h +++ b/src/vppinfra/string.h @@ -85,6 +85,25 @@ clib_memcpy_fast (void *restrict dst, const void *restrict src, size_t n) #endif } +static_always_inline void * +clib_memmove (void *dst, const void *src, size_t n) +{ + u8 *d = (u8 *) dst; + u8 *s = (u8 *) src; + + if (s == d) + return d; + + if (d > s) + for (uword i = n - 1; (i + 1) > 0; i--) + d[i] = s[i]; + else + for (uword i = 0; i < n; i++) + d[i] = s[i]; + + return d; +} + #include <vppinfra/memcpy.h> /* c-11 string manipulation variants */ diff --git a/src/vppinfra/test_heap.c b/src/vppinfra/test_heap.c index 00c896e5c9a..da3ad24a820 100644 --- a/src/vppinfra/test_heap.c +++ b/src/vppinfra/test_heap.c @@ -61,14 +61,13 @@ main (int argc, char *argv[]) uword *objects = 0; uword *handles = 0; uword objects_used; - uword align, fixed_size; + uword align; clib_mem_init (0, 10 << 20); n = 10; seed = (u32) getpid (); check_mask = 0; - fixed_size = 0; if (argc > 1) { @@ -100,13 +99,6 @@ main (int argc, char *argv[]) objects_used = 0; - if (fixed_size) - { - uword max_len = 1024 * 1024; - void *memory = clib_mem_alloc (max_len * sizeof (h[0])); - h = heap_create_from_memory (memory, max_len, sizeof (h[0])); - } - for (i = 0; i < n; i++) { while (1) @@ -188,9 +180,6 @@ main (int argc, char *argv[]) vec_free (objects); vec_free (handles); - if (fixed_size) - vec_free (h); - if (verbose) fformat (stderr, "%U\n", format_clib_mem_usage, /* verbose */ 0); diff --git a/src/vppinfra/test_vec.c b/src/vppinfra/test_vec.c index cd461375893..4bfffd121a2 100644 --- a/src/vppinfra/test_vec.c +++ b/src/vppinfra/test_vec.c @@ -221,8 +221,7 @@ dump_call_stats (uword * stats) if (_v (l) == ~0) \ _v (l) = bounded_random_u32 (&(seed), 0, MAX_VEC_LEN); \ \ - _v (v) = \ - _vec_resize (NULL, _v (l), _v (l) * sizeof (elt_type), _v (h), 0); \ + _v (v) = _vec_realloc (NULL, _v (l), sizeof (elt_type), _v (h), 0, 0); \ fill_with_random_data (_v (v), vec_bytes (_v (v)), (seed)); \ \ /* Fill header with random data as well. */ \ diff --git a/src/vppinfra/types.h b/src/vppinfra/types.h index 24dd5b30e02..e098db5fbaf 100644 --- a/src/vppinfra/types.h +++ b/src/vppinfra/types.h @@ -135,6 +135,14 @@ pointer_to_uword (const void *p) return (uword) (clib_address_t) p; } +static inline __attribute__ ((always_inline)) uword +pointer_is_aligned (void *p, uword align) +{ + if ((pointer_to_uword (p) & (align - 1)) == 0) + return 1; + return 0; +} + #define uword_to_pointer(u,type) ((type) (clib_address_t) (u)) /* Any type: can be either word or pointer. */ diff --git a/src/vppinfra/vec.c b/src/vppinfra/vec.c index 300ef8520ed..2fbab2f7e45 100644 --- a/src/vppinfra/vec.c +++ b/src/vppinfra/vec.c @@ -1,39 +1,6 @@ -/* - * 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. +/* SPDX-License-Identifier: Apache-2.0 + * Copyright(c) 2022 Cisco Systems, Inc. */ -/* - 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 <vppinfra/vec.h> #include <vppinfra/mem.h> @@ -42,94 +9,74 @@ #define CLIB_VECTOR_GROW_BY_ONE 0 #endif -/* Vector resize operator. Called as needed by various macros such as - vec_add1() when we need to allocate memory. */ -__clib_export void * -vec_resize_allocate_memory (void *v, word length_increment, uword data_bytes, - uword header_bytes, uword data_align) +__clib_export uword +vec_mem_size (void *v) { - vec_header_t *vh = _vec_find (v); - uword old_alloc_bytes, new_alloc_bytes; - void *old, *new; - - header_bytes = vec_header_bytes (header_bytes); - data_align = data_align == 0 ? 1 : data_align; + return v ? clib_mem_size (v - vec_get_header_size (v)) : 0; +} - data_bytes += header_bytes; +__clib_export void * +_vec_realloc (void *v, uword n_elts, uword elt_sz, uword hdr_sz, uword align, + void *heap) +{ + uword n_data_bytes, data_offset, new_data_size, alloc_size; + void *p; /* alignment must be power of 2 */ - ASSERT (count_set_bits (data_align) == 1); - - if (!v) - { - new = clib_mem_alloc_aligned_at_offset (data_bytes, data_align, header_bytes, 1 /* yes, call os_out_of_memory */ - ); - new_alloc_bytes = clib_mem_size (new); - CLIB_MEM_UNPOISON (new + data_bytes, new_alloc_bytes - data_bytes); - clib_memset (new, 0, new_alloc_bytes); - CLIB_MEM_POISON (new + data_bytes, new_alloc_bytes - data_bytes); - v = new + header_bytes; - _vec_len (v) = length_increment; - ASSERT (header_bytes / VEC_HEADER_ROUND <= 255); - _vec_find (v)->hdr_size = header_bytes / VEC_HEADER_ROUND; - _vec_find (v)->log2_align = min_log2 (data_align); - return v; - } - - ASSERT (_vec_find (v)->hdr_size * VEC_HEADER_ROUND == header_bytes); - header_bytes = _vec_find (v)->hdr_size * VEC_HEADER_ROUND; + align = clib_max (align, VEC_MIN_ALIGN); + ASSERT (count_set_bits (align) == 1); - ASSERT (data_align == (1 << _vec_find (v)->log2_align)); - data_align = 1 << _vec_find (v)->log2_align; + /* number of bytes needed to store both vector header and optional user + * header */ + data_offset = round_pow2 (hdr_sz + sizeof (vec_header_t), align); - vh->len += length_increment; - old = v - header_bytes; + /* mumber of bytes needed to store vector data */ + n_data_bytes = n_elts * elt_sz; - /* Vector header must start heap object. */ - ASSERT (clib_mem_is_heap_object (old)); + /* minimal allocation needed to store data and headers */ + new_data_size = data_offset + n_data_bytes; - old_alloc_bytes = clib_mem_size (old); - - /* Need to resize? */ - if (data_bytes <= old_alloc_bytes) + if (v) { - CLIB_MEM_UNPOISON (v, data_bytes); - return v; + uword old_data_size = data_offset + _vec_len (v) * elt_sz; + p = vec_header (v); + alloc_size = clib_mem_size (p); + + /* check that we are still dealing with the same vector type */ + ASSERT (_vec_find (v)->hdr_size * VEC_MIN_ALIGN == data_offset); + ASSERT (_vec_find (v)->log2_align == min_log2 (align)); + + /* realloc if new size cannot fit into existing allocation */ + if (alloc_size < new_data_size) + { + if (CLIB_VECTOR_GROW_BY_ONE) + alloc_size = n_data_bytes + data_offset; + else + alloc_size = (n_data_bytes * 3) / 2 + data_offset; + + p = clib_mem_realloc_aligned (p, alloc_size, align); + alloc_size = clib_mem_size (p); + v = p + data_offset; + } + + CLIB_MEM_UNPOISON (p, alloc_size); + clib_memset_u8 (p + old_data_size, 0, alloc_size - old_data_size); + } + else + { + /* new allocation */ + p = clib_mem_alloc_aligned (new_data_size, align); + alloc_size = clib_mem_size (p); + CLIB_MEM_UNPOISON (p, alloc_size); + clib_memset_u8 (p, 0, alloc_size); + v = p + data_offset; + _vec_find (v)->hdr_size = data_offset / VEC_MIN_ALIGN; + _vec_find (v)->log2_align = min_log2 (align); } -#if CLIB_VECTOR_GROW_BY_ONE > 0 - new_alloc_bytes = data_bytes; -#else - new_alloc_bytes = (old_alloc_bytes * 3) / 2; - if (new_alloc_bytes < data_bytes) - new_alloc_bytes = data_bytes; -#endif - - new = - clib_mem_alloc_aligned_at_offset (new_alloc_bytes, data_align, - header_bytes, - 1 /* yes, call os_out_of_memory */ ); - - /* FIXME fail gracefully. */ - if (!new) - clib_panic - ("vec_resize fails, length increment %d, data bytes %d, alignment %d", - length_increment, data_bytes, data_align); - - CLIB_MEM_UNPOISON (old, old_alloc_bytes); - clib_memcpy_fast (new, old, old_alloc_bytes); - clib_mem_free (old); - - /* Allocator may give a bit of extra room. */ - new_alloc_bytes = clib_mem_size (new); - v = new; - - /* Zero new memory. */ - CLIB_MEM_UNPOISON (new + data_bytes, new_alloc_bytes - data_bytes); - memset (v + old_alloc_bytes, 0, new_alloc_bytes - old_alloc_bytes); - CLIB_MEM_POISON (new + data_bytes, new_alloc_bytes - data_bytes); - - return v + header_bytes; + CLIB_MEM_POISON (p + new_data_size, alloc_size - new_data_size); + _vec_len (v) = n_elts; + return v; } __clib_export u32 @@ -143,62 +90,3 @@ vec_free_not_inline (void *v) { vec_free (v); } - -/** \cond */ - -#ifdef TEST - -#include <stdio.h> - -void -main (int argc, char *argv[]) -{ - word n = atoi (argv[1]); - word i, *x = 0; - - typedef struct - { - word x, y, z; - } FOO; - - FOO *foos = vec_init (FOO, 10), *f; - - vec_validate (foos, 100); - foos[100].x = 99; - - _vec_len (foos) = 0; - for (i = 0; i < n; i++) - { - vec_add1 (x, i); - vec_add2 (foos, f, 1); - f->x = 2 * i; - f->y = 3 * i; - f->z = 4 * i; - } - - { - word n = 2; - word m = 42; - vec_delete (foos, n, m); - } - - { - word n = 2; - word m = 42; - vec_insert (foos, n, m); - } - - vec_free (x); - vec_free (foos); - exit (0); -} -#endif -/** \endcond */ - -/* - * fd.io coding-style-patch-verification: ON - * - * Local Variables: - * eval: (c-set-style "gnu") - * End: - */ diff --git a/src/vppinfra/vec.h b/src/vppinfra/vec.h index 8f42149021a..e90c27c1bc1 100644 --- a/src/vppinfra/vec.h +++ b/src/vppinfra/vec.h @@ -52,11 +52,12 @@ The memory layout looks like this: ~~~~~~~~ - user header (aligned to uword boundary) - vector length: number of elements + user header (start of memory allocation) + padding + vector header: number of elements, header size user's pointer-> vector element #0 - vector element #1 - ... + vector element #1 + ... ~~~~~~~~ The user pointer contains the address of vector element # 0. Null @@ -70,8 +71,9 @@ Typically, the header is not present. Headers allow for other data structures to be built atop CLIB vectors. - Users may specify the alignment for first data element of a vector - via the vec_*_aligned macros. + While users may specify the alignment for first data element of a vector + via the vec_*_aligned macros that is typically not needed as alignment + is set based on native alignment of the data structure used. Vector elements can be any C type e.g. (int, double, struct bar). This is also true for data types built atop vectors (e.g. heap, @@ -89,91 +91,79 @@ which are invariant. */ -/** \brief Low-level resize allocation function, usually not called directly +/** \brief Low-level (re)allocation function, usually not called directly @param v pointer to a vector - @param length_increment length increment in elements - @param data_bytes requested size in bytes - @param header_bytes header size in bytes (may be zero) - @param data_align alignment (may be zero) + @param n_elts requested number of elements + @param elt_sz requested size of one element + @param hdr_sz header size in bytes (may be zero) + @param align alignment (may be zero) @return v_prime pointer to resized vector, may or may not equal v */ -void *vec_resize_allocate_memory (void *v, word length_increment, - uword data_bytes, uword header_bytes, - uword data_align); +void *_vec_realloc (void *v, uword n_elts, uword elt_sz, uword hdr_sz, + uword align, void *heap); -/** \brief Low-level vector resize function, usually not called directly +/* calculate minimum alignment out of data natural alignment and provided + * value, should not be < VEC_MIN_ALIGN */ +static_always_inline uword +__vec_align (uword data_align, uword configuered_align) +{ + data_align = clib_max (data_align, configuered_align); + ASSERT (count_set_bits (data_align) == 1); + return clib_max (VEC_MIN_ALIGN, data_align); +} - @param v pointer to a vector - @param length_increment length increment in elements - @param data_bytes requested size in bytes - @param header_bytes header size in bytes (may be zero) - @param data_align alignment (may be zero) - @return v_prime pointer to resized vector, may or may not equal v -*/ +/* function used t o catch cases where vec_* macros on used on void * */ +static_always_inline uword +__vec_elt_sz (uword elt_sz, int is_void) +{ + /* vector macro operations on void * are not allowed */ + ASSERT (is_void == 0); + return elt_sz; +} -#define _vec_resize(V, L, DB, HB, A) \ - ({ \ - __typeof__ ((V)) _V; \ - _V = _vec_resize_inline ((void *) V, L, DB, HB, \ - clib_max ((__alignof__((V)[0])), (A))); \ - _V; \ - }) +static_always_inline void +_vec_update_pointer (void **vp, void *v) +{ + /* avoid store if not needed */ + if (v != vp[0]) + vp[0] = v; +} always_inline void * -_vec_resize_inline (void *v, word length_increment, uword data_bytes, - uword header_bytes, uword data_align) +_vec_realloc_inline (void *v, uword n_elts, uword elt_sz, uword hdr_sz, + uword align, void *heap) { - vec_header_t *vh = _vec_find (v); - uword new_data_bytes, aligned_header_bytes; - - aligned_header_bytes = vec_header_bytes (header_bytes); - - new_data_bytes = data_bytes + aligned_header_bytes; - if (PREDICT_TRUE (v != 0)) { - void *p = v - aligned_header_bytes; - /* Vector header must start heap object. */ - ASSERT (clib_mem_is_heap_object (p)); + ASSERT (clib_mem_is_heap_object (vec_header (v))); /* Typically we'll not need to resize. */ - if (new_data_bytes <= clib_mem_size (p)) + if ((n_elts * elt_sz) <= vec_max_bytes (v)) { - CLIB_MEM_UNPOISON (v, data_bytes); - vh->len += length_increment; + _vec_set_len (v, n_elts, elt_sz); return v; } } /* Slow path: call helper function. */ - return vec_resize_allocate_memory ( - v, length_increment, data_bytes, header_bytes, - clib_max (sizeof (vec_header_t), data_align)); + return _vec_realloc (v, n_elts, elt_sz, hdr_sz, align, heap); } -/** \brief Determine if vector will resize with next allocation - - @param v pointer to a vector - @param length_increment length increment in elements - @param data_bytes requested size in bytes - @param header_bytes header size in bytes (may be zero) - @param data_align alignment (may be zero) - @return 1 if vector will resize 0 otherwise -*/ - always_inline int -_vec_resize_will_expand (void *v, uword n_elts, uword elt_size) +_vec_resize_will_expand (void *v, uword n_elts, uword elt_sz) { - if (PREDICT_TRUE (v != 0)) - { - /* Vector header must start heap object. */ - ASSERT (clib_mem_is_heap_object (vec_header (v))); + if (v == 0) + return 1; + + /* Vector header must start heap object. */ + ASSERT (clib_mem_is_heap_object (vec_header (v))); + + n_elts += _vec_len (v); + if ((n_elts * elt_sz) <= vec_max_bytes (v)) + return 0; - if (vec_mem_size (v) >= ((_vec_len (v) + n_elts)) * elt_size) - return 0; - } return 1; } @@ -185,7 +175,7 @@ _vec_resize_will_expand (void *v, uword n_elts, uword elt_size) */ #define vec_resize_will_expand(V, N) \ - _vec_resize_will_expand (V, N, sizeof ((V)[0])) + _vec_resize_will_expand (V, N, _vec_elt_sz (V)) /* Local variable naming macro (prevents collisions with other macro naming). */ #define _v(var) _vec_##var @@ -202,15 +192,16 @@ _vec_resize_will_expand (void *v, uword n_elts, uword elt_size) @return V (value-result macro parameter) */ +static_always_inline void +_vec_resize (void **vp, uword n_add, uword hdr_sz, uword align, uword elt_sz) +{ + void *v = vp[0]; + v = _vec_realloc_inline (v, vec_len (v) + n_add, elt_sz, hdr_sz, align, 0); + _vec_update_pointer (vp, v); +} + #define vec_resize_ha(V, N, H, A) \ - do \ - { \ - word _v (n) = (N); \ - word _v (l) = vec_len (V); \ - V = _vec_resize ((V), _v (n), (_v (l) + _v (n)) * sizeof ((V)[0]), (H), \ - (A)); \ - } \ - while (0) + _vec_resize ((void **) &(V), N, H, _vec_align (V, A), _vec_elt_sz (V)) /** \brief Resize a vector (no header, unspecified alignment) Add N elements to end of given vector V, return pointer to start of vector. @@ -245,12 +236,14 @@ _vec_resize_will_expand (void *v, uword n_elts, uword elt_size) @return V (value-result macro parameter) */ -#define vec_alloc_ha(V,N,H,A) \ -do { \ - uword _v(l) = vec_len (V); \ - vec_resize_ha (V, N, H, A); \ - _vec_len (V) = _v(l); \ -} while (0) +#define vec_alloc_ha(V, N, H, A) \ + do \ + { \ + uword _v (l) = vec_len (V); \ + vec_resize_ha (V, N, H, A); \ + vec_set_len (V, _v (l)); \ + } \ + while (0) /** \brief Allocate space for N more elements (no header, unspecified alignment) @@ -277,11 +270,8 @@ do { \ @param A alignment (may be zero) @return V new vector */ -#define vec_new_ha(T,N,H,A) \ -({ \ - word _v(n) = (N); \ - (T *)_vec_resize ((T *) 0, _v(n), _v(n) * sizeof (T), (H), (A)); \ -}) +#define vec_new_ha(T, N, H, A) \ + _vec_realloc (0, N, sizeof (T), H, _vec_align ((T *) 0, A), 0) /** \brief Create new vector of given type and length (unspecified alignment, no header). @@ -305,16 +295,17 @@ do { \ @param V pointer to a vector @return V (value-result parameter, V=0) */ -#define vec_free(V) \ - do \ - { \ - if (V) \ - { \ - clib_mem_free (vec_header ((V))); \ - V = 0; \ - } \ - } \ - while (0) + +static_always_inline void +_vec_free (void **vp) +{ + if (vp[0] == 0) + return; + clib_mem_free (vec_header (vp[0])); + vp[0] = 0; +} + +#define vec_free(V) _vec_free ((void **) &(V)) void vec_free_not_inline (void *v); @@ -333,17 +324,22 @@ void vec_free_not_inline (void *v); @return Vdup copy of vector */ +static_always_inline void * +_vec_dup (void *v, uword hdr_size, uword align, uword elt_sz) +{ + uword len = vec_len (v); + void *n = 0; + + if (len) + { + n = _vec_realloc (0, len, elt_sz, hdr_size, align, 0); + clib_memcpy_fast (n, v, len * elt_sz); + } + return n; +} + #define vec_dup_ha(V, H, A) \ - ({ \ - __typeof__ ((V)[0]) *_v (v) = 0; \ - uword _v (l) = vec_len (V); \ - if (_v (l) > 0) \ - { \ - vec_resize_ha (_v (v), _v (l), (H), (A)); \ - clib_memcpy_fast (_v (v), (V), _v (l) * sizeof ((V)[0])); \ - } \ - _v (v); \ - }) + _vec_dup ((void *) (V), H, _vec_align (V, A), _vec_elt_sz (V)) /** \brief Return copy of vector (no header, no alignment) @@ -376,12 +372,15 @@ void vec_free_not_inline (void *v); @param NEW_V pointer to new vector @param OLD_V pointer to old vector */ -#define vec_clone(NEW_V,OLD_V) \ -do { \ - (NEW_V) = 0; \ - (NEW_V) = _vec_resize ((NEW_V), vec_len (OLD_V), \ - vec_len (OLD_V) * sizeof ((NEW_V)[0]), (0), (0)); \ -} while (0) + +static_always_inline void +_vec_clone (void **v1p, void *v2, uword align, uword elt_sz) +{ + v1p[0] = _vec_realloc (0, vec_len (v2), elt_sz, 0, align, 0); +} +#define vec_clone(NEW_V, OLD_V) \ + _vec_clone ((void **) &(NEW_V), OLD_V, _vec_align (NEW_V, 0), \ + _vec_elt_sz (NEW_V)) /** \brief Make sure vector is long enough for given index (general version). @@ -392,24 +391,29 @@ do { \ @return V (value-result macro parameter) */ +always_inline void +_vec_zero_elts (void *v, uword first, uword count, uword elt_sz) +{ + clib_memset_u8 (v + (first * elt_sz), 0, count * elt_sz); +} +#define vec_zero_elts(V, F, C) _vec_zero_elts (V, F, C, sizeof ((V)[0])) + +static_always_inline void * +_vec_validate_ha (void *v, uword index, uword header_size, uword align, + uword elt_sz) +{ + uword vl = vec_len (v); + if (index >= vl) + { + v = _vec_realloc_inline (v, index + 1, elt_sz, header_size, align, 0); + _vec_zero_elts (v, vl, index - vl + 1, elt_sz); + } + return v; +} + #define vec_validate_ha(V, I, H, A) \ - do \ - { \ - STATIC_ASSERT (A == 0 || ((A % sizeof (V[0])) == 0) || \ - ((sizeof (V[0]) % A) == 0), \ - "vector validate aligned on incorrectly sized object"); \ - word _v (i) = (I); \ - word _v (l) = vec_len (V); \ - if (_v (i) >= _v (l)) \ - { \ - vec_resize_ha ((V), 1 + (_v (i) - _v (l)), (H), (A)); \ - /* Must zero new space since user may have previously \ - used e.g. _vec_len (v) -= 10 */ \ - clib_memset ((V) + _v (l), 0, \ - (1 + (_v (i) - _v (l))) * sizeof ((V)[0])); \ - } \ - } \ - while (0) + (V) = \ + _vec_validate_ha ((void *) (V), I, H, _vec_align (V, A), sizeof ((V)[0])) /** \brief Make sure vector is long enough for given index (no header, unspecified alignment) @@ -441,20 +445,22 @@ do { \ @param A alignment (may be zero) @return V (value-result macro parameter) */ -#define vec_validate_init_empty_ha(V,I,INIT,H,A) \ -do { \ - word _v(i) = (I); \ - word _v(l) = vec_len (V); \ - if (_v(i) >= _v(l)) \ - { \ - vec_resize_ha ((V), 1 + (_v(i) - _v(l)), (H), (A)); \ - while (_v(l) <= _v(i)) \ - { \ - (V)[_v(l)] = (INIT); \ - _v(l)++; \ - } \ - } \ -} while (0) +#define vec_validate_init_empty_ha(V, I, INIT, H, A) \ + do \ + { \ + word _v (i) = (I); \ + word _v (l) = vec_len (V); \ + if (_v (i) >= _v (l)) \ + { \ + vec_resize_ha (V, 1 + (_v (i) - _v (l)), H, A); \ + while (_v (l) <= _v (i)) \ + { \ + (V)[_v (l)] = (INIT); \ + _v (l)++; \ + } \ + } \ + } \ + while (0) /** \brief Make sure vector is long enough for given index and initialize empty space (no header, unspecified alignment) @@ -488,12 +494,22 @@ do { \ @param A alignment (may be zero) @return V (value-result macro parameter) */ -#define vec_add1_ha(V,E,H,A) \ -do { \ - word _v(l) = vec_len (V); \ - V = _vec_resize ((V), 1, (_v(l) + 1) * sizeof ((V)[0]), (H), (A)); \ - (V)[_v(l)] = (E); \ -} while (0) + +static_always_inline void * +_vec_add1 (void **vp, uword hdr_sz, uword align, uword elt_sz) +{ + void *v = vp[0]; + uword len = vec_len (v); + v = _vec_realloc_inline (v, len + 1, elt_sz, hdr_sz, align, 0); + + _vec_update_pointer (vp, v); + + return v + len * elt_sz; +} + +#define vec_add1_ha(V, E, H, A) \ + ((__typeof__ ((V)[0]) *) _vec_add1 ((void **) &(V), H, _vec_align (V, A), \ + _vec_elt_sz (V)))[0] = (E) /** \brief Add 1 element to end of vector (unspecified alignment). @@ -522,13 +538,21 @@ do { \ @param A alignment (may be zero) @return V and P (value-result macro parameters) */ -#define vec_add2_ha(V,P,N,H,A) \ -do { \ - word _v(n) = (N); \ - word _v(l) = vec_len (V); \ - V = _vec_resize ((V), _v(n), (_v(l) + _v(n)) * sizeof ((V)[0]), (H), (A)); \ - P = (V) + _v(l); \ -} while (0) + +static_always_inline void +_vec_add2 (void **vp, void **pp, uword n_add, uword hdr_sz, uword align, + uword elt_sz) +{ + void *v = vp[0]; + uword len = vec_len (vp[0]); + v = _vec_realloc_inline (v, len + n_add, elt_sz, hdr_sz, align, 0); + _vec_update_pointer (vp, v); + pp[0] = v + len * elt_sz; +} + +#define vec_add2_ha(V, P, N, H, A) \ + _vec_add2 ((void **) &(V), (void **) &(P), N, H, _vec_align (V, A), \ + _vec_elt_sz (V)) /** \brief Add N elements to end of vector V, return pointer to new elements in P. (no header, unspecified alignment) @@ -562,19 +586,26 @@ do { \ @param A alignment (may be zero) @return V (value-result macro parameter) */ +static_always_inline void +_vec_add (void **vp, void *e, word n_add, uword hdr_sz, uword align, + uword elt_sz) +{ + void *v = vp[0]; + uword len = vec_len (v); + + ASSERT (n_add >= 0); + + if (n_add < 1) + return; + + v = _vec_realloc_inline (v, len + n_add, elt_sz, hdr_sz, align, 0); + clib_memcpy_fast (v + len * elt_sz, e, n_add * elt_sz); + _vec_update_pointer (vp, v); +} + #define vec_add_ha(V, E, N, H, A) \ - do \ - { \ - word _v (n) = (N); \ - if (PREDICT_TRUE (_v (n) > 0)) \ - { \ - word _v (l) = vec_len (V); \ - V = _vec_resize ((V), _v (n), (_v (l) + _v (n)) * sizeof ((V)[0]), \ - (H), (A)); \ - clib_memcpy_fast ((V) + _v (l), (E), _v (n) * sizeof ((V)[0])); \ - } \ - } \ - while (0) + _vec_add ((void **) &(V), (void *) (E), N, H, _vec_align (V, A), \ + _vec_elt_sz (V)) /** \brief Add N elements to end of vector V (no header, unspecified alignment) @@ -600,14 +631,16 @@ do { \ @param V pointer to a vector @return E element removed from the end of the vector */ -#define vec_pop(V) \ -({ \ - uword _v(l) = vec_len (V); \ - ASSERT (_v(l) > 0); \ - _v(l) -= 1; \ - _vec_len (V) = _v (l); \ - (V)[_v(l)]; \ -}) +#define vec_pop(V) \ + ({ \ + uword _v (l) = vec_len (V); \ + __typeof__ ((V)[0]) _v (rv); \ + ASSERT (_v (l) > 0); \ + _v (l) -= 1; \ + _v (rv) = (V)[_v (l)]; \ + vec_set_len (V, _v (l)); \ + (_v (rv)); \ + }) /** \brief Set E to the last element of a vector, decrement vector length @param V pointer to a vector @@ -634,21 +667,26 @@ do { \ @param A alignment (may be zero) @return V (value-result macro parameter) */ -#define vec_insert_init_empty_ha(V,N,M,INIT,H,A) \ -do { \ - word _v(l) = vec_len (V); \ - word _v(n) = (N); \ - word _v(m) = (M); \ - V = _vec_resize ((V), \ - _v(n), \ - (_v(l) + _v(n))*sizeof((V)[0]), \ - (H), (A)); \ - ASSERT (_v(m) <= _v(l)); \ - memmove ((V) + _v(m) + _v(n), \ - (V) + _v(m), \ - (_v(l) - _v(m)) * sizeof ((V)[0])); \ - clib_memset ((V) + _v(m), INIT, _v(n) * sizeof ((V)[0])); \ -} while (0) + +static_always_inline void +_vec_insert (void **vp, uword n_insert, uword ins_pt, u8 init, uword hdr_sz, + uword align, uword elt_sz) +{ + void *v = vp[0]; + uword len = vec_len (v); + + ASSERT (ins_pt <= len); + + v = _vec_realloc_inline (v, len + n_insert, elt_sz, hdr_sz, align, 0); + clib_memmove (v + elt_sz * (ins_pt + n_insert), v + ins_pt * elt_sz, + (len - ins_pt) * elt_sz); + _vec_zero_elts (v, ins_pt, n_insert, elt_sz); + _vec_update_pointer (vp, v); +} + +#define vec_insert_init_empty_ha(V, N, M, INIT, H, A) \ + _vec_insert ((void **) &(V), N, M, INIT, H, _vec_align (V, A), \ + _vec_elt_sz (V)) /** \brief Insert N vector elements starting at element M, initialize new elements to zero (general version) @@ -722,23 +760,26 @@ do { \ @return V (value-result macro parameter) */ +static_always_inline void +_vec_insert_elts (void **vp, void *e, uword n_insert, uword ins_pt, + uword hdr_sz, uword align, uword elt_sz) +{ + void *v = vp[0]; + uword len = vec_len (v); + + ASSERT (ins_pt <= len); + + v = _vec_realloc_inline (v, len + n_insert, elt_sz, hdr_sz, align, 0); + clib_memmove (v + elt_sz * (ins_pt + n_insert), v + ins_pt * elt_sz, + (len - ins_pt) * elt_sz); + _vec_zero_elts (v, ins_pt, n_insert, elt_sz); + clib_memcpy_fast (v + ins_pt * elt_sz, e, n_insert * elt_sz); + _vec_update_pointer (vp, v); +} + #define vec_insert_elts_ha(V, E, N, M, H, A) \ - do \ - { \ - word _v (n) = (N); \ - if (PREDICT_TRUE (_v (n) > 0)) \ - { \ - word _v (l) = vec_len (V); \ - word _v (m) = (M); \ - V = _vec_resize ((V), _v (n), (_v (l) + _v (n)) * sizeof ((V)[0]), \ - (H), (A)); \ - ASSERT (_v (m) <= _v (l)); \ - memmove ((V) + _v (m) + _v (n), (V) + _v (m), \ - (_v (l) - _v (m)) * sizeof ((V)[0])); \ - clib_memcpy_fast ((V) + _v (m), (E), _v (n) * sizeof ((V)[0])); \ - } \ - } \ - while (0) + _vec_insert_elts ((void **) &(V), E, N, M, H, _vec_align (V, A), \ + _vec_elt_sz (V)) /** \brief Insert N vector elements starting at element M, insert given elements (no header, unspecified alignment) @@ -770,57 +811,65 @@ do { \ @param M first element to delete @return V (value-result macro parameter) */ -#define vec_delete(V,N,M) \ -do { \ - word _v(l) = vec_len (V); \ - word _v(n) = (N); \ - word _v(m) = (M); \ - /* Copy over deleted elements. */ \ - if (_v(l) - _v(n) - _v(m) > 0) \ - memmove ((V) + _v(m), (V) + _v(m) + _v(n), \ - (_v(l) - _v(n) - _v(m)) * sizeof ((V)[0])); \ - /* Zero empty space at end (for future re-allocation). */ \ - if (_v(n) > 0) \ - clib_memset ((V) + _v(l) - _v(n), 0, _v(n) * sizeof ((V)[0])); \ - _vec_len (V) -= _v(n); \ - CLIB_MEM_POISON(vec_end(V), _v(n) * sizeof ((V)[0])); \ -} while (0) + +static_always_inline void +_vec_delete (void *v, uword n_del, uword first, uword elt_sz) +{ + word n_bytes_del, n_bytes_to_move, len = vec_len (v); + u8 *dst; + + if (n_del == 0) + return; + + ASSERT (first + n_del <= len); + + n_bytes_del = n_del * elt_sz; + n_bytes_to_move = (len - first - n_del) * elt_sz; + dst = v + first * elt_sz; + + if (n_bytes_to_move > 0) + clib_memmove (dst, dst + n_bytes_del, n_bytes_to_move); + clib_memset (dst + n_bytes_to_move, 0, n_bytes_del); + + _vec_set_len (v, _vec_len (v) - n_del, elt_sz); +} + +#define vec_delete(V, N, M) _vec_delete ((void *) (V), N, M, _vec_elt_sz (V)) /** \brief Delete the element at index I @param V pointer to a vector @param I index to delete */ -#define vec_del1(v,i) \ -do { \ - uword _vec_del_l = _vec_len (v) - 1; \ - uword _vec_del_i = (i); \ - if (_vec_del_i < _vec_del_l) \ - (v)[_vec_del_i] = (v)[_vec_del_l]; \ - _vec_len (v) = _vec_del_l; \ - CLIB_MEM_POISON(vec_end(v), sizeof ((v)[0])); \ -} while (0) -/** \brief Append v2 after v1. Result in v1. - @param V1 target vector - @param V2 vector to append -*/ +static_always_inline void +_vec_del1 (void *v, uword index, uword elt_sz) +{ + uword len = _vec_len (v) - 1; -#define vec_append(v1, v2) \ - do \ - { \ - uword _v (l1) = vec_len (v1); \ - uword _v (l2) = vec_len (v2); \ - \ - if (PREDICT_TRUE (_v (l2) > 0)) \ - { \ - v1 = _vec_resize ((v1), _v (l2), \ - (_v (l1) + _v (l2)) * sizeof ((v1)[0]), 0, 0); \ - clib_memcpy_fast ((v1) + _v (l1), (v2), \ - _v (l2) * sizeof ((v2)[0])); \ - } \ - } \ - while (0) + if (index < len) + clib_memcpy_fast (v + index * elt_sz, v + len * elt_sz, elt_sz); + + _vec_set_len (v, len, elt_sz); +} + +#define vec_del1(v, i) _vec_del1 ((void *) (v), i, _vec_elt_sz (v)) + +static_always_inline void +_vec_append (void **v1p, void *v2, uword v1_elt_sz, uword v2_elt_sz, + uword align) +{ + void *v1 = v1p[0]; + uword len1 = vec_len (v1); + uword len2 = vec_len (v2); + + if (PREDICT_TRUE (len2 > 0)) + { + v1 = _vec_realloc_inline (v1, len1 + len2, v2_elt_sz, 0, align, 0); + clib_memcpy_fast (v1 + len1 * v1_elt_sz, v2, len2 * v2_elt_sz); + _vec_update_pointer (v1p, v1); + } +} /** \brief Append v2 after v1. Result in v1. Specified alignment. @param V1 target vector @@ -829,41 +878,32 @@ do { \ */ #define vec_append_aligned(v1, v2, align) \ - do \ - { \ - uword _v (l1) = vec_len (v1); \ - uword _v (l2) = vec_len (v2); \ - \ - if (PREDICT_TRUE (_v (l2) > 0)) \ - { \ - v1 = _vec_resize ( \ - (v1), _v (l2), (_v (l1) + _v (l2)) * sizeof ((v1)[0]), 0, align); \ - clib_memcpy_fast ((v1) + _v (l1), (v2), \ - _v (l2) * sizeof ((v2)[0])); \ - } \ - } \ - while (0) + _vec_append ((void **) &(v1), (void *) (v2), _vec_elt_sz (v1), \ + _vec_elt_sz (v2), _vec_align (v1, align)) -/** \brief Prepend v2 before v1. Result in v1. +/** \brief Append v2 after v1. Result in v1. @param V1 target vector - @param V2 vector to prepend + @param V2 vector to append */ -#define vec_prepend(v1, v2) \ - do \ - { \ - uword _v (l1) = vec_len (v1); \ - uword _v (l2) = vec_len (v2); \ - \ - if (PREDICT_TRUE (_v (l2) > 0)) \ - { \ - v1 = _vec_resize ((v1), _v (l2), \ - (_v (l1) + _v (l2)) * sizeof ((v1)[0]), 0, 0); \ - memmove ((v1) + _v (l2), (v1), _v (l1) * sizeof ((v1)[0])); \ - clib_memcpy_fast ((v1), (v2), _v (l2) * sizeof ((v2)[0])); \ - } \ - } \ - while (0) +#define vec_append(v1, v2) vec_append_aligned (v1, v2, 0) + +static_always_inline void +_vec_prepend (void **v1p, void *v2, uword v1_elt_sz, uword v2_elt_sz, + uword align) +{ + void *v1 = v1p[0]; + uword len1 = vec_len (v1); + uword len2 = vec_len (v2); + + if (PREDICT_TRUE (len2 > 0)) + { + v1 = _vec_realloc_inline (v1, len1 + len2, v2_elt_sz, 0, align, 0); + clib_memmove (v1 + len2 * v2_elt_sz, v1p[0], len1 * v1_elt_sz); + clib_memcpy_fast (v1, v2, len2 * v2_elt_sz); + _vec_update_pointer (v1p, v1); + } +} /** \brief Prepend v2 before v1. Result in v1. Specified alignment @param V1 target vector @@ -872,29 +912,29 @@ do { \ */ #define vec_prepend_aligned(v1, v2, align) \ - do \ - { \ - uword _v (l1) = vec_len (v1); \ - uword _v (l2) = vec_len (v2); \ - \ - if (PREDICT_TRUE (_v (l2) > 0)) \ - { \ - v1 = _vec_resize ( \ - (v1), _v (l2), (_v (l1) + _v (l2)) * sizeof ((v1)[0]), 0, align); \ - memmove ((v1) + _v (l2), (v1), _v (l1) * sizeof ((v1)[0])); \ - clib_memcpy_fast ((v1), (v2), _v (l2) * sizeof ((v2)[0])); \ - } \ - } \ - while (0) + _vec_prepend ((void **) &(v1), (void *) (v2), _vec_elt_sz (v1), \ + _vec_elt_sz (v2), _vec_align (v1, align)) + +/** \brief Prepend v2 before v1. Result in v1. + @param V1 target vector + @param V2 vector to prepend +*/ + +#define vec_prepend(v1, v2) vec_prepend_aligned (v1, v2, 0) /** \brief Zero all vector elements. Null-pointer tolerant. @param var Vector to zero */ -#define vec_zero(var) \ -do { \ - if (var) \ - clib_memset ((var), 0, vec_len (var) * sizeof ((var)[0])); \ -} while (0) +static_always_inline void +_vec_zero (void *v, uword elt_sz) +{ + uword len = vec_len (v); + + if (len) + clib_memset_u8 (v, 0, len * elt_sz); +} + +#define vec_zero(var) _vec_zero ((void *) (var), _vec_elt_sz (var)) /** \brief Set all vector elements to given value. Null-pointer tolerant. @param v vector to set @@ -918,8 +958,23 @@ do { \ @param v2 Pointer to a vector @return 1 if equal, 0 if unequal */ -#define vec_is_equal(v1,v2) \ - (vec_len (v1) == vec_len (v2) && ! memcmp ((v1), (v2), vec_len (v1) * sizeof ((v1)[0]))) +static_always_inline int +_vec_is_equal (void *v1, void *v2, uword v1_elt_sz, uword v2_elt_sz) +{ + uword vec_len_v1 = vec_len (v1); + + if ((vec_len_v1 != vec_len (v2)) || (v1_elt_sz != v2_elt_sz)) + return 0; + + if ((vec_len_v1 == 0) || (memcmp (v1, v2, vec_len_v1 * v1_elt_sz) == 0)) + return 1; + + return 0; +} + +#define vec_is_equal(v1, v2) \ + _vec_is_equal ((void *) (v1), (void *) (v2), _vec_elt_sz (v1), \ + _vec_elt_sz (v2)) /** \brief Compare two vectors (only applicable to vectors of signed numbers). Used in qsort compare functions. @@ -1004,15 +1059,16 @@ do { \ @param S pointer to string buffer. @param L string length (NOT including the terminating NULL; a la strlen()) */ -#define vec_validate_init_c_string(V, S, L) \ - do { \ - vec_reset_length (V); \ - vec_validate ((V), (L)); \ - if ((S) && (L)) \ - clib_memcpy_fast ((V), (S), (L)); \ - (V)[(L)] = 0; \ - } while (0) - +#define vec_validate_init_c_string(V, S, L) \ + do \ + { \ + vec_reset_length (V); \ + vec_validate (V, (L)); \ + if ((S) && (L)) \ + clib_memcpy_fast (V, (S), (L)); \ + (V)[(L)] = 0; \ + } \ + while (0) /** \brief Test whether a vector is a NULL terminated c-string. @@ -1027,23 +1083,12 @@ do { \ @param V (possibly NULL) pointer to a vector. @return V (value-result macro parameter) */ -#define vec_terminate_c_string(V) \ - do { \ - u32 vl = vec_len ((V)); \ - if (!vec_c_string_is_terminated(V)) \ - { \ - vec_validate ((V), vl); \ - (V)[vl] = 0; \ - } \ - } while (0) +#define vec_terminate_c_string(V) \ + do \ + { \ + if (!vec_c_string_is_terminated (V)) \ + vec_add1 (V, 0); \ + } \ + while (0) #endif /* included_vec_h */ - - -/* - * fd.io coding-style-patch-verification: ON - * - * Local Variables: - * eval: (c-set-style "gnu") - * End: - */ diff --git a/src/vppinfra/vec_bootstrap.h b/src/vppinfra/vec_bootstrap.h index bb6ac84e734..304ea2dee1a 100644 --- a/src/vppinfra/vec_bootstrap.h +++ b/src/vppinfra/vec_bootstrap.h @@ -55,13 +55,13 @@ typedef struct { u32 len; /**< Number of elements in vector (NOT its allocated length). */ - u8 hdr_size; /**< header size divided by VEC_HEADER_ROUND */ + u8 hdr_size; /**< header size divided by VEC_MIN_ALIGN */ u8 log2_align; /**< data alignment */ u8 vpad[2]; /**< pad to 8 bytes */ u8 vector_data[0]; /**< Vector data . */ } vec_header_t; -#define VEC_HEADER_ROUND 8 +#define VEC_MIN_ALIGN 8 /** \brief Find the vector header @@ -73,19 +73,20 @@ typedef struct */ #define _vec_find(v) ((vec_header_t *) (v) - 1) +always_inline uword __vec_align (uword data_align, uword configuered_align); +always_inline uword __vec_elt_sz (uword elt_sz, int is_void); + #define _vec_round_size(s) \ (((s) + sizeof (uword) - 1) &~ (sizeof (uword) - 1)) +#define _vec_is_void(P) \ + __builtin_types_compatible_p (__typeof__ ((P)[0]), void) +#define _vec_elt_sz(V) __vec_elt_sz (sizeof ((V)[0]), _vec_is_void (V)) +#define _vec_align(V, A) __vec_align (__alignof__((V)[0]), A) -always_inline uword -vec_header_bytes (uword header_bytes) -{ - return round_pow2 (header_bytes + sizeof (vec_header_t), VEC_HEADER_ROUND); -} - -always_inline uword +always_inline CLIB_NOSANITIZE_ADDR uword vec_get_header_size (void *v) { - uword header_size = _vec_find (v)->hdr_size * VEC_HEADER_ROUND; + uword header_size = _vec_find (v)->hdr_size * VEC_MIN_ALIGN; return header_size; } @@ -141,11 +142,7 @@ u32 vec_len_not_inline (void *v); * @return memory size allocated for the vector */ -always_inline uword -vec_mem_size (void *v) -{ - return v ? clib_mem_size (v - vec_get_header_size (v)) : 0; -} +uword vec_mem_size (void *v); /** * Number of elements that can fit into generic vector @@ -156,24 +153,35 @@ vec_mem_size (void *v) */ always_inline uword -_vec_max_len (void *v, uword elt_size) +vec_max_bytes (void *v) { - return v ? vec_mem_size (v) / elt_size : 0; + return v ? vec_mem_size (v) - vec_get_header_size (v) : 0; } -#define vec_max_len(v) _vec_max_len (v, sizeof ((v)[0])) +always_inline uword +_vec_max_len (void *v, uword elt_sz) +{ + return vec_max_bytes (v) / elt_sz; +} + +#define vec_max_len(v) _vec_max_len (v, _vec_elt_sz (v)) always_inline void -_vec_set_len (void *v, uword len, uword elt_size) +_vec_set_len (void *v, uword len, uword elt_sz) { ASSERT (v); - ASSERT (len <= vec_max_len (v)); + ASSERT (len <= _vec_max_len (v, elt_sz)); + uword old_len = _vec_len (v); + + if (len > old_len) + CLIB_MEM_UNPOISON (v + old_len * elt_sz, (len - old_len) * elt_sz); + else if (len > old_len) + CLIB_MEM_POISON (v + len * elt_sz, (old_len - len) * elt_sz); - CLIB_MEM_POISON_LEN (v, _vec_len (v) * elt_size, len * elt_size); _vec_len (v) = len; } -#define vec_set_len(v, l) _vec_set_len ((void *) v, l, sizeof ((v)[0])) +#define vec_set_len(v, l) _vec_set_len ((void *) v, l, _vec_elt_sz (v)) /** \brief Reset vector length to zero NULL-pointer tolerant |