FD.io VPP  v21.10.1-2-g0a485f517
Vector Packet Processing
vec.c
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2015 Cisco and/or its affiliates.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at:
6  *
7  * http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 /*
16  Copyright (c) 2001, 2002, 2003 Eliot Dresselhaus
17 
18  Permission is hereby granted, free of charge, to any person obtaining
19  a copy of this software and associated documentation files (the
20  "Software"), to deal in the Software without restriction, including
21  without limitation the rights to use, copy, modify, merge, publish,
22  distribute, sublicense, and/or sell copies of the Software, and to
23  permit persons to whom the Software is furnished to do so, subject to
24  the following conditions:
25 
26  The above copyright notice and this permission notice shall be
27  included in all copies or substantial portions of the Software.
28 
29  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
30  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
31  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
32  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
33  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
34  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
35  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
36 */
37 
38 #include <vppinfra/vec.h>
39 #include <vppinfra/mem.h>
40 
41 #ifndef CLIB_VECTOR_GROW_BY_ONE
42 #define CLIB_VECTOR_GROW_BY_ONE 0
43 #endif
44 
45 /* Vector resize operator. Called as needed by various macros such as
46  vec_add1() when we need to allocate memory. */
47 __clib_export void *
49  word length_increment,
50  uword data_bytes,
51  uword header_bytes, uword data_align,
52  uword numa_id)
53 {
54  vec_header_t *vh = _vec_find (v);
55  uword old_alloc_bytes, new_alloc_bytes;
56  void *old, *new;
57  void *oldheap;
58 
59  header_bytes = vec_header_bytes (header_bytes);
60 
61  data_bytes += header_bytes;
62 
63  if (PREDICT_FALSE (numa_id != VEC_NUMA_UNSPECIFIED))
64  {
65  oldheap = clib_mem_get_per_cpu_heap ();
67  }
68 
69  if (!v)
70  {
71  new = clib_mem_alloc_aligned_at_offset (data_bytes, data_align, header_bytes, 1 /* yes, call os_out_of_memory */
72  );
73  new_alloc_bytes = clib_mem_size (new);
74  CLIB_MEM_UNPOISON (new + data_bytes, new_alloc_bytes - data_bytes);
75  clib_memset (new, 0, new_alloc_bytes);
76  CLIB_MEM_POISON (new + data_bytes, new_alloc_bytes - data_bytes);
77  v = new + header_bytes;
78  _vec_len (v) = length_increment;
79  _vec_numa (v) = numa_id;
80  if (PREDICT_FALSE (numa_id != VEC_NUMA_UNSPECIFIED))
81  clib_mem_set_per_cpu_heap (oldheap);
82  return v;
83  }
84 
85  vh->len += length_increment;
86  old = v - header_bytes;
87 
88  /* Vector header must start heap object. */
90 
91  old_alloc_bytes = clib_mem_size (old);
92 
93  /* Need to resize? */
94  if (data_bytes <= old_alloc_bytes)
95  {
96  CLIB_MEM_UNPOISON (v, data_bytes);
97  if (PREDICT_FALSE (numa_id != VEC_NUMA_UNSPECIFIED))
98  clib_mem_set_per_cpu_heap (oldheap);
99  return v;
100  }
101 
102 #if CLIB_VECTOR_GROW_BY_ONE > 0
103  new_alloc_bytes = data_bytes;
104 #else
105  new_alloc_bytes = (old_alloc_bytes * 3) / 2;
106  if (new_alloc_bytes < data_bytes)
107  new_alloc_bytes = data_bytes;
108 #endif
109 
110  new =
111  clib_mem_alloc_aligned_at_offset (new_alloc_bytes, data_align,
112  header_bytes,
113  1 /* yes, call os_out_of_memory */ );
114 
115  /* FIXME fail gracefully. */
116  if (!new)
117  clib_panic
118  ("vec_resize fails, length increment %d, data bytes %d, alignment %d",
119  length_increment, data_bytes, data_align);
120 
121  CLIB_MEM_UNPOISON (old, old_alloc_bytes);
122  clib_memcpy_fast (new, old, old_alloc_bytes);
123  clib_mem_free (old);
124 
125  /* Allocator may give a bit of extra room. */
126  new_alloc_bytes = clib_mem_size (new);
127  v = new;
128 
129  /* Zero new memory. */
130  CLIB_MEM_UNPOISON (new + data_bytes, new_alloc_bytes - data_bytes);
131  memset (v + old_alloc_bytes, 0, new_alloc_bytes - old_alloc_bytes);
132  CLIB_MEM_POISON (new + data_bytes, new_alloc_bytes - data_bytes);
133 
134  _vec_numa ((v + header_bytes)) = numa_id;
135  if (PREDICT_FALSE (numa_id != VEC_NUMA_UNSPECIFIED))
136  clib_mem_set_per_cpu_heap (oldheap);
137 
138  return v + header_bytes;
139 }
140 
141 __clib_export uword
142 clib_mem_is_vec_h (void *v, uword header_bytes)
143 {
144  return clib_mem_is_heap_object (vec_header (v, header_bytes));
145 }
146 
147 __clib_export u32
149 {
150  return vec_len (v);
151 }
152 
153 __clib_export void
155 {
156  vec_free (v);
157 }
158 
159 /** \cond */
160 
161 #ifdef TEST
162 
163 #include <stdio.h>
164 
165 void
166 main (int argc, char *argv[])
167 {
168  word n = atoi (argv[1]);
169  word i, *x = 0;
170 
171  typedef struct
172  {
173  word x, y, z;
174  } FOO;
175 
176  FOO *foos = vec_init (FOO, 10), *f;
177 
178  vec_validate (foos, 100);
179  foos[100].x = 99;
180 
181  _vec_len (foos) = 0;
182  for (i = 0; i < n; i++)
183  {
184  vec_add1 (x, i);
185  vec_add2 (foos, f, 1);
186  f->x = 2 * i;
187  f->y = 3 * i;
188  f->z = 4 * i;
189  }
190 
191  {
192  word n = 2;
193  word m = 42;
194  vec_delete (foos, n, m);
195  }
196 
197  {
198  word n = 2;
199  word m = 42;
200  vec_insert (foos, n, m);
201  }
202 
203  vec_free (x);
204  vec_free (foos);
205  exit (0);
206 }
207 #endif
208 /** \endcond */
209 
210 /*
211  * fd.io coding-style-patch-verification: ON
212  *
213  * Local Variables:
214  * eval: (c-set-style "gnu")
215  * End:
216  */
VEC_NUMA_UNSPECIFIED
#define VEC_NUMA_UNSPECIFIED
Definition: mem.h:161
vec_resize_allocate_memory
__clib_export void * vec_resize_allocate_memory(void *v, word length_increment, uword data_bytes, uword header_bytes, uword data_align, uword numa_id)
Low-level resize allocation function, usually not called directly.
Definition: vec.c:48
CLIB_MEM_POISON
#define CLIB_MEM_POISON(a, s)
Definition: sanitizer.h:113
f
vlib_frame_t * f
Definition: interface_output.c:1098
clib_mem_free
static void clib_mem_free(void *p)
Definition: mem.h:314
vec_delete
#define vec_delete(V, N, M)
Delete N elements starting at element M.
Definition: vec.h:875
clib_memcpy_fast
static_always_inline void * clib_memcpy_fast(void *restrict dst, const void *restrict src, size_t n)
Definition: string.h:92
clib_mem_get_per_numa_heap
static void * clib_mem_get_per_numa_heap(u32 numa_id)
Definition: mem.h:180
clib_mem_get_per_cpu_heap
static clib_mem_heap_t * clib_mem_get_per_cpu_heap(void)
Definition: mem.h:164
vec_len
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
Definition: vec_bootstrap.h:142
vec_add2
#define vec_add2(V, P, N)
Add N elements to end of vector V, return pointer to new elements in P.
Definition: vec.h:644
vec_add1
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
Definition: vec.h:606
clib_mem_size
static uword clib_mem_size(void *p)
Definition: mem.h:346
PREDICT_FALSE
#define PREDICT_FALSE(x)
Definition: clib.h:124
uword
u64 uword
Definition: types.h:112
vec_header
static void * vec_header(void *v, uword header_bytes)
Find a user vector header.
Definition: vec_bootstrap.h:92
vec_free_not_inline
__clib_export void vec_free_not_inline(void *v)
Definition: vec.c:154
vec_validate
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment)
Definition: vec.h:523
vec_free
#define vec_free(V)
Free vector's memory (no header).
Definition: vec.h:395
vec_len_not_inline
__clib_export u32 vec_len_not_inline(void *v)
Definition: vec.c:148
main
int main(int argc, char **argv)
Definition: health_check.c:24
ASSERT
#define ASSERT(truth)
Definition: error_bootstrap.h:69
clib_mem_is_vec_h
__clib_export uword clib_mem_is_vec_h(void *v, uword header_bytes)
Predicate function, says whether the supplied vector is a clib heap object (general version).
Definition: vec.c:142
u32
unsigned int u32
Definition: types.h:88
CLIB_MEM_UNPOISON
#define CLIB_MEM_UNPOISON(a, s)
Definition: sanitizer.h:114
clib_mem_set_per_cpu_heap
static void * clib_mem_set_per_cpu_heap(void *new_heap)
Definition: mem.h:171
vec.h
vec_header_t
vector header structure
Definition: vec_bootstrap.h:55
clib_memset
clib_memset(h->entries, 0, sizeof(h->entries[0]) *entries)
i
int i
Definition: flowhash_template.h:376
clib_mem_alloc_aligned_at_offset
static void * clib_mem_alloc_aligned_at_offset(uword size, uword align, uword align_offset, int os_out_of_memory_on_failure)
Definition: mem.h:225
word
i64 word
Definition: types.h:111
mem.h
clib_panic
#define clib_panic(format, args...)
Definition: error.h:72
vec_header_bytes
static uword vec_header_bytes(uword header_bytes)
Definition: vec_bootstrap.h:79
vec_header_t::len
u32 len
Number of elements in vector (NOT its allocated length).
Definition: vec_bootstrap.h:57
vec_insert
#define vec_insert(V, N, M)
Insert N vector elements starting at element M, initialize new elements to zero (no header,...
Definition: vec.h:775
clib_mem_is_heap_object
static uword clib_mem_is_heap_object(void *p)
Definition: mem.h:306