aboutsummaryrefslogtreecommitdiffstats
path: root/src/vppinfra
diff options
context:
space:
mode:
authorDamjan Marion <damarion@cisco.com>2022-03-19 00:07:52 +0100
committerFlorin Coras <florin.coras@gmail.com>2022-03-30 18:27:13 +0000
commit299571aca34d36e637e43cfbba6275662d0d7795 (patch)
treea48be21950d082afb7dd93562f76f0ba554e8919 /src/vppinfra
parent9539647b895c456ca53892a9259e3127c6b92d35 (diff)
vppinfra: vector allocator rework
- support of in-place growth of vectors (if there is available space next to existing alloc) - drops the need for alloc_aligned_at_offset from memory allocator, which allows easier swap to different memory allocator and reduces malloc overhead - rework of pool and vec macros to inline functions to improve debuggability - fix alignment - in many cases macros were not using native alignment of the particular datatype. Explicitly setting alignment with XXX_aligned() versions of the macro is not needed anymore in > 99% of cases - fix ASAN usage - avoid use of vector of voids, this was root cause of several bugs found in vec_* and pool_* function where sizeof() was used on voids instead of real vector data type - introduce minimal alignment which is currently 8 bytes, vectors will be always aligned at least to that value (underlay allocator actually always provide 16-byte aligned allocs) Type: improvement Change-Id: I20f4b081bb13bbf7bc0ace85cc4e301787f12fdf Signed-off-by: Damjan Marion <damarion@cisco.com>
Diffstat (limited to 'src/vppinfra')
-rw-r--r--src/vppinfra/dlmalloc.c12
-rw-r--r--src/vppinfra/dlmalloc.h2
-rw-r--r--src/vppinfra/elf.h8
-rw-r--r--src/vppinfra/hash.c13
-rw-r--r--src/vppinfra/heap.c6
-rw-r--r--src/vppinfra/heap.h38
-rw-r--r--src/vppinfra/mem.h144
-rw-r--r--src/vppinfra/mem_dlmalloc.c152
-rw-r--r--src/vppinfra/pool.c6
-rw-r--r--src/vppinfra/pool.h366
-rw-r--r--src/vppinfra/ring.h10
-rw-r--r--src/vppinfra/serialize.c7
-rw-r--r--src/vppinfra/sparse_vec.h8
-rw-r--r--src/vppinfra/string.h19
-rw-r--r--src/vppinfra/test_heap.c13
-rw-r--r--src/vppinfra/test_vec.c3
-rw-r--r--src/vppinfra/types.h8
-rw-r--r--src/vppinfra/vec.c230
-rw-r--r--src/vppinfra/vec.h701
-rw-r--r--src/vppinfra/vec_bootstrap.h52
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