summaryrefslogtreecommitdiffstats
path: root/src/vppinfra/vec.c
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/vec.c
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/vec.c')
-rw-r--r--src/vppinfra/vec.c230
1 files changed, 59 insertions, 171 deletions
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:
- */