diff options
Diffstat (limited to 'src/vppinfra/vec.h')
| -rw-r--r-- | src/vppinfra/vec.h | 993 |
1 files changed, 558 insertions, 435 deletions
diff --git a/src/vppinfra/vec.h b/src/vppinfra/vec.h index d19ff998137..1a64a69a1e6 100644 --- a/src/vppinfra/vec.h +++ b/src/vppinfra/vec.h @@ -52,11 +52,13 @@ The memory layout looks like this: ~~~~~~~~ - user header (aligned to uword boundary) - vector length: number of elements + user header (start of memory allocation) + padding + heap pointer (optional, only if default_heap == 0) + 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 +72,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,123 +92,130 @@ 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 numa_id numa id (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, - uword numa_id); -/** \brief Low-level vector resize 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 numa_id (may be ~0) - @return v_prime pointer to resized vector, may or may not equal v -*/ +typedef struct +{ + void *heap; + u32 elt_sz; + u16 hdr_sz; + u16 align; +} vec_attr_t; + +void *_vec_alloc_internal (uword n_elts, const vec_attr_t *const attr); +void *_vec_realloc_internal (void *v, uword n_elts, + const vec_attr_t *const attr); +void *_vec_resize_internal (void *v, uword n_elts, + const vec_attr_t *const attr); + +/* 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); +} -#define _vec_resize_numa(V,L,DB,HB,A,S) \ -({ \ - __typeof__ ((V)) _V; \ - _V = _vec_resize_inline((void *)V,L,DB,HB,clib_max((__alignof__((V)[0])),(A)),(S)); \ - _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) \ - _vec_resize_numa(V,L,DB,HB,A,VEC_NUMA_UNSPECIFIED) +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, - uword numa_id) +static_always_inline void * +vec_get_heap (void *v) { - vec_header_t *vh = _vec_find (v); - uword new_data_bytes, aligned_header_bytes; - void *oldheap; + if (v == 0 || _vec_find (v)->default_heap == 1) + return 0; + return _vec_heap (v); +} - aligned_header_bytes = vec_header_bytes (header_bytes); +static_always_inline uword +vec_get_align (void *v) +{ + return 1ULL << _vec_find (v)->log2_align; +} - new_data_bytes = data_bytes + aligned_header_bytes; +static_always_inline void +_vec_prealloc (void **vp, uword n_elts, uword hdr_sz, uword align, void *heap, + uword elt_sz) +{ + const vec_attr_t va = { + .elt_sz = elt_sz, .hdr_sz = hdr_sz, .align = align, .heap = heap + }; + void *v; - if (PREDICT_TRUE (v != 0)) - { - void *p = v - aligned_header_bytes; - - if (PREDICT_FALSE (numa_id != VEC_NUMA_UNSPECIFIED)) - { - oldheap = clib_mem_get_per_cpu_heap (); - clib_mem_set_per_cpu_heap (clib_mem_get_per_numa_heap (numa_id)); - } - - /* Vector header must start heap object. */ - ASSERT (clib_mem_is_heap_object (p)); - - /* Typically we'll not need to resize. */ - if (new_data_bytes <= clib_mem_size (p)) - { - CLIB_MEM_UNPOISON (v, data_bytes); - vh->len += length_increment; - if (PREDICT_FALSE (numa_id != VEC_NUMA_UNSPECIFIED)) - clib_mem_set_per_cpu_heap (oldheap); - return v; - } - if (PREDICT_FALSE (numa_id != VEC_NUMA_UNSPECIFIED)) - clib_mem_set_per_cpu_heap (oldheap); - } + ASSERT (vp[0] == 0); - /* 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), numa_id); + v = _vec_alloc_internal (n_elts, &va); + _vec_set_len (v, 0, elt_sz); + _vec_update_pointer (vp, v); } -/** \brief Determine if vector will resize with next allocation +/** \brief Pre-allocate a vector (generic version) - @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 + @param V pointer to a vector + @param N number of elements to pre-allocate + @param H header size in bytes (may be zero) + @param A alignment (zero means default alignment of the data structure) + @param P heap (zero means default heap) + @return V (value-result macro parameter) */ -always_inline int -_vec_resize_will_expand (void *v, - word length_increment, - uword data_bytes, uword header_bytes, - uword data_align) -{ - uword new_data_bytes, aligned_header_bytes; +#define vec_prealloc_hap(V, N, H, A, P) \ + _vec_prealloc ((void **) &(V), N, H, _vec_align (V, A), P, _vec_elt_sz (V)) - aligned_header_bytes = vec_header_bytes (header_bytes); +/** \brief Pre-allocate a vector (simple version) + + @param V pointer to a vector + @param N number of elements to pre-allocate + @return V (value-result macro parameter) +*/ +#define vec_prealloc(V, N) vec_prealloc_hap (V, N, 0, 0, 0) - new_data_bytes = data_bytes + aligned_header_bytes; +/** \brief Pre-allocate a vector (heap version) - if (PREDICT_TRUE (v != 0)) - { - void *p = v - aligned_header_bytes; + @param V pointer to a vector + @param N number of elements to pre-allocate + @param P heap (zero means default heap) + @return V (value-result macro parameter) +*/ +#define vec_prealloc_heap(V, N, P) vec_prealloc_hap (V, N, 0, 0, P) - /* Vector header must start heap object. */ - ASSERT (clib_mem_is_heap_object (p)); +always_inline int +_vec_resize_will_expand (void *v, uword n_elts, uword elt_sz) +{ + if (v == 0) + return 1; + + /* Vector header must start heap object. */ + ASSERT (clib_mem_heap_is_heap_object (vec_get_heap (v), vec_header (v))); + + n_elts += _vec_len (v); + if ((n_elts * elt_sz) <= vec_max_bytes (v)) + return 0; - /* Typically we'll not need to resize. */ - if (new_data_bytes <= clib_mem_size (p)) - return 0; - } return 1; } @@ -217,34 +227,7 @@ _vec_resize_will_expand (void *v, */ #define vec_resize_will_expand(V, N) \ - ({ \ - word _v (n) = (N); \ - word _v (l) = vec_len (V); \ - _vec_resize_will_expand ((V), _v (n), \ - (_v (l) + _v (n)) * sizeof ((V)[0]), 0, 0); \ - }) - -/** \brief Predicate function, says whether the supplied vector is a clib heap - object (general version). - - @param v pointer to a vector - @param header_bytes vector header size in bytes (may be zero) - @return 0 or 1 -*/ -uword clib_mem_is_vec_h (void *v, uword header_bytes); - - -/** \brief Predicate function, says whether the supplied vector is a clib heap - object - - @param v pointer to a vector - @return 0 or 1 -*/ -always_inline uword -clib_mem_is_vec (void *v) -{ - return clib_mem_is_vec_h (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 @@ -258,31 +241,36 @@ clib_mem_is_vec (void *v) @param N number of elements to add @param H header size in bytes (may be zero) @param A alignment (may be zero) - @param S numa_id (may be zero) @return V (value-result macro parameter) */ -#define vec_resize_has(V,N,H,A,S) \ -do { \ - word _v(n) = (N); \ - word _v(l) = vec_len (V); \ - V = _vec_resize_numa ((V), _v(n), \ - (_v(l) + _v(n)) * sizeof ((V)[0]), \ - (H), (A),(S)); \ -} while (0) +static_always_inline void +_vec_resize (void **vp, uword n_add, uword hdr_sz, uword align, uword elt_sz) +{ + void *v = *vp; + if (PREDICT_FALSE (v == 0)) + { + const vec_attr_t va = { .elt_sz = elt_sz, + .align = align, + .hdr_sz = hdr_sz }; + *vp = _vec_alloc_internal (n_add, &va); + return; + } -/** \brief Resize a vector (less general version). - Add N elements to end of given vector V, return pointer to start of vector. - Vector will have room for H header bytes and will have user's data aligned - at alignment A (rounded to next power of 2). + if (PREDICT_FALSE (_vec_find (v)->grow_elts < n_add)) + { + const vec_attr_t va = { .elt_sz = elt_sz, + .align = align, + .hdr_sz = hdr_sz }; + v = _vec_resize_internal (v, _vec_len (v) + n_add, &va); + _vec_update_pointer (vp, v); + } + else + _vec_set_len (v, _vec_len (v) + n_add, elt_sz); +} - @param V pointer to a vector - @param N number of elements to add - @param H header size in bytes (may be zero) - @param A alignment (may be zero) - @return V (value-result macro parameter) -*/ -#define vec_resize_ha(V,N,H,A) vec_resize_has(V,N,H,A,VEC_NUMA_UNSPECIFIED) +#define vec_resize_ha(V, N, H, A) \ + _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. @@ -317,12 +305,14 @@ do { \ @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) @@ -347,13 +337,14 @@ do { \ @param N number of elements to add @param H header size in bytes (may be zero) @param A alignment (may be zero) + @param P heap (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_generic(T, N, H, A, P) \ + _vec_alloc_internal (N, &((vec_attr_t){ .align = _vec_align ((T *) 0, A), \ + .hdr_sz = (H), \ + .heap = (P), \ + .elt_sz = sizeof (T) })) /** \brief Create new vector of given type and length (unspecified alignment, no header). @@ -362,7 +353,7 @@ do { \ @param N number of elements to add @return V new vector */ -#define vec_new(T,N) vec_new_ha(T,N,0,0) +#define vec_new(T, N) vec_new_generic (T, N, 0, 0, 0) /** \brief Create new vector of given type and length (alignment specified, no header). @@ -371,28 +362,32 @@ do { \ @param A alignment (may be zero) @return V new vector */ -#define vec_new_aligned(T,N,A) vec_new_ha(T,N,0,A) - -/** \brief Free vector's memory (general version) +#define vec_new_aligned(T, N, A) vec_new_generic (T, N, 0, A, 0) +/** \brief Create new vector of given type and length + (heap specified, no header). - @param V pointer to a vector - @param H size of header in bytes - @return V (value-result parameter, V=0) + @param T type of elements in new vector + @param N number of elements to add + @param P heap (may be zero) + @return V new vector */ -#define vec_free_h(V,H) \ -do { \ - if (V) \ - { \ - clib_mem_free (vec_header ((V), (H))); \ - V = 0; \ - } \ -} while (0) +#define vec_new_heap(T, N, P) vec_new_generic (T, N, 0, 0, P) /** \brief Free vector's memory (no header). @param V pointer to a vector @return V (value-result parameter, V=0) */ -#define vec_free(V) vec_free_h(V,0) + +static_always_inline void +_vec_free (void **vp) +{ + if (vp[0] == 0) + return; + clib_mem_heap_free (vec_get_heap (vp[0]), vec_header (vp[0])); + vp[0] = 0; +} + +#define vec_free(V) _vec_free ((void **) &(V)) void vec_free_not_inline (void *v); @@ -407,34 +402,27 @@ void vec_free_not_inline (void *v); @param V pointer to a vector @param H size of header in bytes @param A alignment (may be zero) - @param S numa (may be VEC_NUMA_UNSPECIFIED) @return Vdup copy of vector */ -#define vec_dup_ha_numa(V,H,A,S) \ -({ \ - __typeof__ ((V)[0]) * _v(v) = 0; \ - uword _v(l) = vec_len (V); \ - if (_v(l) > 0) \ - { \ - vec_resize_has (_v(v), _v(l), (H), (A), (S)); \ - clib_memcpy_fast (_v(v), (V), _v(l) * sizeof ((V)[0]));\ - } \ - _v(v); \ -}) - -/** \brief Return copy of vector (VEC_NUMA_UNSPECIFIED). - - @param V pointer to a vector - @param H size of header in bytes - @param A alignment (may be zero) +static_always_inline void * +_vec_dup (void *v, uword hdr_size, uword align, uword elt_sz) +{ + uword len = vec_len (v); + const vec_attr_t va = { .elt_sz = elt_sz, .align = align }; + void *n = 0; - @return Vdup copy of vector -*/ -#define vec_dup_ha(V,H,A) \ - vec_dup_ha_numa(V,H,A,VEC_NUMA_UNSPECIFIED) + if (len) + { + n = _vec_alloc_internal (len, &va); + clib_memcpy_fast (n, v, len * elt_sz); + } + return n; +} +#define vec_dup_ha(V, H, A) \ + _vec_dup ((void *) (V), H, _vec_align (V, A), _vec_elt_sz (V)) /** \brief Return copy of vector (no header, no alignment) @@ -467,12 +455,16 @@ 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) +{ + const vec_attr_t va = { .elt_sz = elt_sz, .align = align }; + v1p[0] = _vec_alloc_internal (vec_len (v2), &va); +} +#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). @@ -480,39 +472,53 @@ do { \ @param I vector index which will be valid upon return @param H header size in bytes (may be zero) @param A alignment (may be zero) - @param N numa_id (may be zero) @return V (value-result macro parameter) */ -#define vec_validate_han(V,I,H,A,N) \ -do { \ - void *oldheap; \ - 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)) \ - { \ - /* switch to the per-numa heap if directed */ \ - if (PREDICT_FALSE(N != VEC_NUMA_UNSPECIFIED)) \ - { \ - oldheap = clib_mem_get_per_cpu_heap(); \ - clib_mem_set_per_cpu_heap (clib_mem_get_per_numa_heap(N)); \ - } \ - \ - 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])); \ - /* Switch back to the global heap */ \ - if (PREDICT_FALSE (N != VEC_NUMA_UNSPECIFIED)) \ - clib_mem_set_per_cpu_heap (oldheap); \ - } \ -} while (0) +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])) -#define vec_validate_ha(V,I,H,A) vec_validate_han(V,I,H,A,VEC_NUMA_UNSPECIFIED) +static_always_inline void +_vec_validate (void **vp, uword index, uword header_size, uword align, + void *heap, uword elt_sz) +{ + void *v = *vp; + uword vl, n_elts = index + 1; + + if (PREDICT_FALSE (v == 0)) + { + const vec_attr_t va = { .elt_sz = elt_sz, + .align = align, + .hdr_sz = header_size }; + *vp = _vec_alloc_internal (n_elts, &va); + return; + } + + vl = _vec_len (v); + + if (PREDICT_FALSE (index < vl)) + return; + + if (PREDICT_FALSE (index >= _vec_find (v)->grow_elts + vl)) + { + const vec_attr_t va = { .elt_sz = elt_sz, + .align = align, + .hdr_sz = header_size }; + v = _vec_resize_internal (v, n_elts, &va); + _vec_update_pointer (vp, v); + } + else + _vec_set_len (v, n_elts, elt_sz); + + _vec_zero_elts (v, vl, n_elts - vl, elt_sz); +} + +#define vec_validate_hap(V, I, H, A, P) \ + _vec_validate ((void **) &(V), I, H, _vec_align (V, A), 0, sizeof ((V)[0])) /** \brief Make sure vector is long enough for given index (no header, unspecified alignment) @@ -521,7 +527,7 @@ do { \ @param I vector index which will be valid upon return @return V (value-result macro parameter) */ -#define vec_validate(V,I) vec_validate_ha(V,I,0,0) +#define vec_validate(V, I) vec_validate_hap (V, I, 0, 0, 0) /** \brief Make sure vector is long enough for given index (no header, specified alignment) @@ -532,7 +538,18 @@ do { \ @return V (value-result macro parameter) */ -#define vec_validate_aligned(V,I,A) vec_validate_ha(V,I,0,A) +#define vec_validate_aligned(V, I, A) vec_validate_hap (V, I, 0, A, 0) + +/** \brief Make sure vector is long enough for given index + (no header, specified heap) + + @param V (possibly NULL) pointer to a vector. + @param I vector index which will be valid upon return + @param H heap (may be zero) + @return V (value-result macro parameter) +*/ + +#define vec_validate_heap(V, I, P) vec_validate_hap (V, I, 0, 0, P) /** \brief Make sure vector is long enough for given index and initialize empty space (general version) @@ -544,20 +561,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) @@ -591,12 +610,40 @@ 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; + + if (PREDICT_FALSE (v == 0)) + { + const vec_attr_t va = { .elt_sz = elt_sz, + .align = align, + .hdr_sz = hdr_sz }; + return *vp = _vec_alloc_internal (1, &va); + } + + len = _vec_len (v); + + if (PREDICT_FALSE (_vec_find (v)->grow_elts == 0)) + { + const vec_attr_t va = { .elt_sz = elt_sz, + .align = align, + .hdr_sz = hdr_sz }; + v = _vec_resize_internal (v, len + 1, &va); + _vec_update_pointer (vp, v); + } + else + _vec_set_len (v, len + 1, elt_sz); + + 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). @@ -625,13 +672,41 @@ 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; + uword len; + + if (PREDICT_FALSE (v == 0)) + { + const vec_attr_t va = { .elt_sz = elt_sz, + .align = align, + .hdr_sz = hdr_sz }; + *vp = *pp = _vec_alloc_internal (n_add, &va); + return; + } + + len = _vec_len (v); + if (PREDICT_FALSE (_vec_find (v)->grow_elts < n_add)) + { + const vec_attr_t va = { .elt_sz = elt_sz, + .align = align, + .hdr_sz = hdr_sz }; + v = _vec_resize_internal (v, len + n_add, &va); + _vec_update_pointer (vp, v); + } + else + _vec_set_len (v, len + n_add, elt_sz); + + *pp = 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) @@ -665,19 +740,47 @@ 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; + uword len; + + ASSERT (n_add >= 0); + + if (n_add < 1) + return; + + if (PREDICT_FALSE (v == 0)) + { + const vec_attr_t va = { .elt_sz = elt_sz, + .align = align, + .hdr_sz = hdr_sz }; + *vp = v = _vec_alloc_internal (n_add, &va); + clib_memcpy_fast (v, e, n_add * elt_sz); + return; + } + + len = _vec_len (v); + + if (PREDICT_FALSE (_vec_find (v)->grow_elts < n_add)) + { + const vec_attr_t va = { .elt_sz = elt_sz, + .align = align, + .hdr_sz = hdr_sz }; + v = _vec_resize_internal (v, len + n_add, &va); + _vec_update_pointer (vp, v); + } + else + _vec_set_len (v, len + n_add, elt_sz); + + clib_memcpy_fast (v + len * elt_sz, e, n_add * elt_sz); +} + #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) @@ -703,14 +806,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 @@ -737,21 +842,27 @@ 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); + const vec_attr_t va = { .elt_sz = elt_sz, .align = align, .hdr_sz = hdr_sz }; + + ASSERT (ins_pt <= len); + + v = _vec_resize_internal (v, len + n_insert, &va); + clib_memmove (v + va.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) @@ -825,23 +936,27 @@ 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); + const vec_attr_t va = { .elt_sz = elt_sz, .align = align, .hdr_sz = hdr_sz }; + + ASSERT (ins_pt <= len); + + v = _vec_resize_internal (v, len + n_insert, &va); + 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) @@ -873,57 +988,66 @@ 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)) + { + const vec_attr_t va = { .elt_sz = v2_elt_sz, .align = align }; + v1 = _vec_resize_internal (v1, len1 + len2, &va); + 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 @@ -932,72 +1056,66 @@ 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 *restrict *v1p, void *restrict v2, uword v1_elt_sz, + uword v2_elt_sz, uword align) +{ + void *restrict v1 = v1p[0]; + uword len1 = vec_len (v1); + uword len2 = vec_len (v2); + + if (PREDICT_TRUE (len2 > 0)) + { + /* prepending vector to itself would result in use-after-free */ + ASSERT (v1 != v2); + const vec_attr_t va = { .elt_sz = v2_elt_sz, .align = align }; + v1 = _vec_resize_internal (v1, len1 + len2, &va); + clib_memmove (v1 + len2 * v2_elt_sz, v1, len1 * v1_elt_sz); + clib_memcpy_fast (v1, v2, len2 * v2_elt_sz); + _vec_update_pointer ((void **) v1p, v1); + } +} /** \brief Prepend v2 before v1. Result in v1. Specified alignment @param V1 target vector - @param V2 vector to prepend + @param V2 vector to prepend, V1 != V2 @param align required alignment */ #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, V1 != V2 +*/ + +#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 @@ -1021,8 +1139,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. @@ -1107,15 +1240,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. @@ -1130,23 +1264,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: - */ |