FD.io VPP  v21.06-3-gbb25fbf28
Vector Packet Processing
vec.h
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 #ifndef included_vec_h
39 #define included_vec_h
40 
41 #include <vppinfra/clib.h> /* word, etc */
42 #include <vppinfra/mem.h> /* clib_mem_free */
43 #include <vppinfra/string.h> /* memcpy, memmove */
44 #include <vppinfra/vec_bootstrap.h>
45 
46 /** \file
47 
48  CLIB vectors are ubiquitous dynamically resized arrays with by user
49  defined "headers". Many CLIB data structures (e.g. hash, heap,
50  pool) are vectors with various different headers.
51 
52  The memory layout looks like this:
53 
54 ~~~~~~~~
55  user header (aligned to uword boundary)
56  vector length: number of elements
57  user's pointer-> vector element #0
58  vector element #1
59  ...
60 ~~~~~~~~
61 
62  The user pointer contains the address of vector element # 0. Null
63  pointer vectors are valid and mean a zero length vector.
64 
65  You can reset the length of an allocated vector to zero via the
66  vec_reset_length(v) macro, or by setting the vector length field to
67  zero (e.g. _vec_len (v) = 0). Vec_reset_length(v) preferred: it
68  understands Null pointers.
69 
70  Typically, the header is not present. Headers allow for other
71  data structures to be built atop CLIB vectors.
72 
73  Users may specify the alignment for first data element of a vector
74  via the vec_*_aligned macros.
75 
76  Vector elements can be any C type e.g. (int, double, struct bar).
77  This is also true for data types built atop vectors (e.g. heap,
78  pool, etc.).
79 
80  Many macros have \_a variants supporting alignment of vector elements
81  and \_h variants supporting non-zero-length vector headers. The \_ha
82  variants support both. Additionally cacheline alignment within a
83  vector element structure can be specified using the
84  CLIB_CACHE_LINE_ALIGN_MARK() macro.
85 
86  Standard programming error: memorize a pointer to the ith element
87  of a vector then expand it. Vectors expand by 3/2, so such code
88  may appear to work for a period of time. Memorize vector indices
89  which are invariant.
90  */
91 
92 /** \brief Low-level resize allocation function, usually not called directly
93 
94  @param v pointer to a vector
95  @param length_increment length increment in elements
96  @param data_bytes requested size in bytes
97  @param header_bytes header size in bytes (may be zero)
98  @param data_align alignment (may be zero)
99  @param numa_id numa id (may be zero)
100  @return v_prime pointer to resized vector, may or may not equal v
101 */
102 void *vec_resize_allocate_memory (void *v,
103  word length_increment,
104  uword data_bytes,
105  uword header_bytes, uword data_align,
106  uword numa_id);
107 
108 /** \brief Low-level vector resize function, usually not called directly
109 
110  @param v pointer to a vector
111  @param length_increment length increment in elements
112  @param data_bytes requested size in bytes
113  @param header_bytes header size in bytes (may be zero)
114  @param data_align alignment (may be zero)
115  @param numa_id (may be ~0)
116  @return v_prime pointer to resized vector, may or may not equal v
117 */
118 
119 #define _vec_resize_numa(V,L,DB,HB,A,S) \
120 ({ \
121  __typeof__ ((V)) _V; \
122  _V = _vec_resize_inline((void *)V,L,DB,HB,clib_max((__alignof__((V)[0])),(A)),(S)); \
123  _V; \
124 })
125 
126 #define _vec_resize(V,L,DB,HB,A) \
127  _vec_resize_numa(V,L,DB,HB,A,VEC_NUMA_UNSPECIFIED)
128 
129 always_inline void *
130 _vec_resize_inline (void *v,
131  word length_increment,
132  uword data_bytes, uword header_bytes, uword data_align,
133  uword numa_id)
134 {
135  vec_header_t *vh = _vec_find (v);
136  uword new_data_bytes, aligned_header_bytes;
137  void *oldheap;
138 
139  aligned_header_bytes = vec_header_bytes (header_bytes);
140 
141  new_data_bytes = data_bytes + aligned_header_bytes;
142 
143  if (PREDICT_TRUE (v != 0))
144  {
145  void *p = v - aligned_header_bytes;
146 
147  if (PREDICT_FALSE (numa_id != VEC_NUMA_UNSPECIFIED))
148  {
149  oldheap = clib_mem_get_per_cpu_heap ();
150  clib_mem_set_per_cpu_heap (clib_mem_get_per_numa_heap (numa_id));
151  }
152 
153  /* Vector header must start heap object. */
154  ASSERT (clib_mem_is_heap_object (p));
155 
156  /* Typically we'll not need to resize. */
157  if (new_data_bytes <= clib_mem_size (p))
158  {
159  CLIB_MEM_UNPOISON (v, data_bytes);
160  vh->len += length_increment;
161  if (PREDICT_FALSE (numa_id != VEC_NUMA_UNSPECIFIED))
162  clib_mem_set_per_cpu_heap (oldheap);
163  return v;
164  }
165  if (PREDICT_FALSE (numa_id != VEC_NUMA_UNSPECIFIED))
166  clib_mem_set_per_cpu_heap (oldheap);
167  }
168 
169  /* Slow path: call helper function. */
170  return vec_resize_allocate_memory (v, length_increment, data_bytes,
171  header_bytes,
172  clib_max (sizeof (vec_header_t),
173  data_align), numa_id);
174 }
175 
176 /** \brief Determine if vector will resize with next allocation
177 
178  @param v pointer to a vector
179  @param length_increment length increment in elements
180  @param data_bytes requested size in bytes
181  @param header_bytes header size in bytes (may be zero)
182  @param data_align alignment (may be zero)
183  @return 1 if vector will resize 0 otherwise
184 */
185 
186 always_inline int
187 _vec_resize_will_expand (void *v,
188  word length_increment,
189  uword data_bytes, uword header_bytes,
190  uword data_align)
191 {
192  uword new_data_bytes, aligned_header_bytes;
193 
194  aligned_header_bytes = vec_header_bytes (header_bytes);
195 
196  new_data_bytes = data_bytes + aligned_header_bytes;
197 
198  if (PREDICT_TRUE (v != 0))
199  {
200  void *p = v - aligned_header_bytes;
201 
202  /* Vector header must start heap object. */
203  ASSERT (clib_mem_is_heap_object (p));
204 
205  /* Typically we'll not need to resize. */
206  if (new_data_bytes <= clib_mem_size (p))
207  return 0;
208  }
209  return 1;
210 }
211 
212 /** \brief Determine if vector will resize with next allocation
213 
214  @param V pointer to a vector
215  @param N number of elements to add
216  @return 1 if vector will resize 0 otherwise
217 */
218 
219 #define vec_resize_will_expand(V, N) \
220  ({ \
221  word _v (n) = (N); \
222  word _v (l) = vec_len (V); \
223  _vec_resize_will_expand ((V), _v (n), \
224  (_v (l) + _v (n)) * sizeof ((V)[0]), 0, 0); \
225  })
226 
227 /** \brief Predicate function, says whether the supplied vector is a clib heap
228  object (general version).
229 
230  @param v pointer to a vector
231  @param header_bytes vector header size in bytes (may be zero)
232  @return 0 or 1
233 */
234 uword clib_mem_is_vec_h (void *v, uword header_bytes);
235 
236 
237 /** \brief Predicate function, says whether the supplied vector is a clib heap
238  object
239 
240  @param v pointer to a vector
241  @return 0 or 1
242 */
243 always_inline uword
244 clib_mem_is_vec (void *v)
245 {
246  return clib_mem_is_vec_h (v, 0);
247 }
248 
249 /* Local variable naming macro (prevents collisions with other macro naming). */
250 #define _v(var) _vec_##var
251 
252 /** \brief Resize a vector (general version).
253  Add N elements to end of given vector V, return pointer to start of vector.
254  Vector will have room for H header bytes and will have user's data aligned
255  at alignment A (rounded to next power of 2).
256 
257  @param V pointer to a vector
258  @param N number of elements to add
259  @param H header size in bytes (may be zero)
260  @param A alignment (may be zero)
261  @param S numa_id (may be zero)
262  @return V (value-result macro parameter)
263 */
264 
265 #define vec_resize_has(V,N,H,A,S) \
266 do { \
267  word _v(n) = (N); \
268  word _v(l) = vec_len (V); \
269  V = _vec_resize_numa ((V), _v(n), \
270  (_v(l) + _v(n)) * sizeof ((V)[0]), \
271  (H), (A),(S)); \
272 } while (0)
273 
274 /** \brief Resize a vector (less general version).
275  Add N elements to end of given vector V, return pointer to start of vector.
276  Vector will have room for H header bytes and will have user's data aligned
277  at alignment A (rounded to next power of 2).
278 
279  @param V pointer to a vector
280  @param N number of elements to add
281  @param H header size in bytes (may be zero)
282  @param A alignment (may be zero)
283  @return V (value-result macro parameter)
284 */
285 #define vec_resize_ha(V,N,H,A) vec_resize_has(V,N,H,A,VEC_NUMA_UNSPECIFIED)
286 
287 /** \brief Resize a vector (no header, unspecified alignment)
288  Add N elements to end of given vector V, return pointer to start of vector.
289  Vector will have room for H header bytes and will have user's data aligned
290  at alignment A (rounded to next power of 2).
291 
292  @param V pointer to a vector
293  @param N number of elements to add
294  @return V (value-result macro parameter)
295 */
296 #define vec_resize(V,N) vec_resize_ha(V,N,0,0)
297 
298 /** \brief Resize a vector (no header, alignment specified).
299  Add N elements to end of given vector V, return pointer to start of vector.
300  Vector will have room for H header bytes and will have user's data aligned
301  at alignment A (rounded to next power of 2).
302 
303  @param V pointer to a vector
304  @param N number of elements to add
305  @param A alignment (may be zero)
306  @return V (value-result macro parameter)
307 */
308 
309 #define vec_resize_aligned(V,N,A) vec_resize_ha(V,N,0,A)
310 
311 /** \brief Allocate space for N more elements
312 
313  @param V pointer to a vector
314  @param N number of elements to add
315  @param H header size in bytes (may be zero)
316  @param A alignment (may be zero)
317  @return V (value-result macro parameter)
318 */
319 
320 #define vec_alloc_ha(V,N,H,A) \
321 do { \
322  uword _v(l) = vec_len (V); \
323  vec_resize_ha (V, N, H, A); \
324  _vec_len (V) = _v(l); \
325 } while (0)
326 
327 /** \brief Allocate space for N more elements
328  (no header, unspecified alignment)
329 
330  @param V pointer to a vector
331  @param N number of elements to add
332  @return V (value-result macro parameter)
333 */
334 #define vec_alloc(V,N) vec_alloc_ha(V,N,0,0)
335 
336 /** \brief Allocate space for N more elements (no header, given alignment)
337  @param V pointer to a vector
338  @param N number of elements to add
339  @param A alignment (may be zero)
340  @return V (value-result macro parameter)
341 */
342 
343 #define vec_alloc_aligned(V,N,A) vec_alloc_ha(V,N,0,A)
344 
345 /** \brief Create new vector of given type and length (general version).
346  @param T type of elements in new vector
347  @param N number of elements to add
348  @param H header size in bytes (may be zero)
349  @param A alignment (may be zero)
350  @return V new vector
351 */
352 #define vec_new_ha(T,N,H,A) \
353 ({ \
354  word _v(n) = (N); \
355  (T *)_vec_resize ((T *) 0, _v(n), _v(n) * sizeof (T), (H), (A)); \
356 })
357 
358 /** \brief Create new vector of given type and length
359  (unspecified alignment, no header).
360 
361  @param T type of elements in new vector
362  @param N number of elements to add
363  @return V new vector
364 */
365 #define vec_new(T,N) vec_new_ha(T,N,0,0)
366 /** \brief Create new vector of given type and length
367  (alignment specified, no header).
368 
369  @param T type of elements in new vector
370  @param N number of elements to add
371  @param A alignment (may be zero)
372  @return V new vector
373 */
374 #define vec_new_aligned(T,N,A) vec_new_ha(T,N,0,A)
375 
376 /** \brief Free vector's memory (general version)
377 
378  @param V pointer to a vector
379  @param H size of header in bytes
380  @return V (value-result parameter, V=0)
381 */
382 #define vec_free_h(V,H) \
383 do { \
384  if (V) \
385  { \
386  clib_mem_free (vec_header ((V), (H))); \
387  V = 0; \
388  } \
389 } while (0)
390 
391 /** \brief Free vector's memory (no header).
392  @param V pointer to a vector
393  @return V (value-result parameter, V=0)
394 */
395 #define vec_free(V) vec_free_h(V,0)
396 
397 void vec_free_not_inline (void *v);
398 
399 /**\brief Free vector user header (syntactic sugar)
400  @param h vector header
401  @void
402 */
403 #define vec_free_header(h) clib_mem_free (h)
404 
405 /** \brief Return copy of vector (general version).
406 
407  @param V pointer to a vector
408  @param H size of header in bytes
409  @param A alignment (may be zero)
410  @param S numa (may be VEC_NUMA_UNSPECIFIED)
411 
412  @return Vdup copy of vector
413 */
414 
415 #define vec_dup_ha_numa(V,H,A,S) \
416 ({ \
417  __typeof__ ((V)[0]) * _v(v) = 0; \
418  uword _v(l) = vec_len (V); \
419  if (_v(l) > 0) \
420  { \
421  vec_resize_has (_v(v), _v(l), (H), (A), (S)); \
422  clib_memcpy_fast (_v(v), (V), _v(l) * sizeof ((V)[0]));\
423  } \
424  _v(v); \
425 })
426 
427 /** \brief Return copy of vector (VEC_NUMA_UNSPECIFIED).
428 
429  @param V pointer to a vector
430  @param H size of header in bytes
431  @param A alignment (may be zero)
432 
433  @return Vdup copy of vector
434 */
435 #define vec_dup_ha(V,H,A) \
436  vec_dup_ha_numa(V,H,A,VEC_NUMA_UNSPECIFIED)
437 
438 
439 /** \brief Return copy of vector (no header, no alignment)
440 
441  @param V pointer to a vector
442  @return Vdup copy of vector
443 */
444 #define vec_dup(V) vec_dup_ha(V,0,0)
445 
446 /** \brief Return copy of vector (no header, alignment specified).
447 
448  @param V pointer to a vector
449  @param A alignment (may be zero)
450 
451  @return Vdup copy of vector
452 */
453 #define vec_dup_aligned(V,A) vec_dup_ha(V,0,A)
454 
455 /** \brief Copy a vector, memcpy wrapper. Assumes sizeof(SRC[0]) ==
456  sizeof(DST[0])
457 
458  @param DST destination
459  @param SRC source
460 */
461 #define vec_copy(DST,SRC) clib_memcpy_fast (DST, SRC, vec_len (DST) * \
462  sizeof ((DST)[0]))
463 
464 /** \brief Clone a vector. Make a new vector with the
465  same size as a given vector but possibly with a different type.
466 
467  @param NEW_V pointer to new vector
468  @param OLD_V pointer to old vector
469 */
470 #define vec_clone(NEW_V,OLD_V) \
471 do { \
472  (NEW_V) = 0; \
473  (NEW_V) = _vec_resize ((NEW_V), vec_len (OLD_V), \
474  vec_len (OLD_V) * sizeof ((NEW_V)[0]), (0), (0)); \
475 } while (0)
476 
477 /** \brief Make sure vector is long enough for given index (general version).
478 
479  @param V (possibly NULL) pointer to a vector.
480  @param I vector index which will be valid upon return
481  @param H header size in bytes (may be zero)
482  @param A alignment (may be zero)
483  @param N numa_id (may be zero)
484  @return V (value-result macro parameter)
485 */
486 
487 #define vec_validate_han(V,I,H,A,N) \
488 do { \
489  void *oldheap; \
490  STATIC_ASSERT(A==0 || ((A % sizeof(V[0]))==0) \
491  || ((sizeof(V[0]) % A) == 0), \
492  "vector validate aligned on incorrectly sized object"); \
493  word _v(i) = (I); \
494  word _v(l) = vec_len (V); \
495  if (_v(i) >= _v(l)) \
496  { \
497  /* switch to the per-numa heap if directed */ \
498  if (PREDICT_FALSE(N != VEC_NUMA_UNSPECIFIED)) \
499  { \
500  oldheap = clib_mem_get_per_cpu_heap(); \
501  clib_mem_set_per_cpu_heap (clib_mem_get_per_numa_heap(N)); \
502  } \
503  \
504  vec_resize_ha ((V), 1 + (_v(i) - _v(l)), (H), (A)); \
505  /* Must zero new space since user may have previously \
506  used e.g. _vec_len (v) -= 10 */ \
507  clib_memset ((V) + _v(l), 0, \
508  (1 + (_v(i) - _v(l))) * sizeof ((V)[0])); \
509  /* Switch back to the global heap */ \
510  if (PREDICT_FALSE (N != VEC_NUMA_UNSPECIFIED)) \
511  clib_mem_set_per_cpu_heap (oldheap); \
512  } \
513 } while (0)
514 
515 #define vec_validate_ha(V,I,H,A) vec_validate_han(V,I,H,A,VEC_NUMA_UNSPECIFIED)
516 
517 /** \brief Make sure vector is long enough for given index
518  (no header, unspecified alignment)
519 
520  @param V (possibly NULL) pointer to a vector.
521  @param I vector index which will be valid upon return
522  @return V (value-result macro parameter)
523 */
524 #define vec_validate(V,I) vec_validate_ha(V,I,0,0)
525 
526 /** \brief Make sure vector is long enough for given index
527  (no header, specified alignment)
528 
529  @param V (possibly NULL) pointer to a vector.
530  @param I vector index which will be valid upon return
531  @param A alignment (may be zero)
532  @return V (value-result macro parameter)
533 */
534 
535 #define vec_validate_aligned(V,I,A) vec_validate_ha(V,I,0,A)
536 
537 /** \brief Make sure vector is long enough for given index
538  and initialize empty space (general version)
539 
540  @param V (possibly NULL) pointer to a vector.
541  @param I vector index which will be valid upon return
542  @param INIT initial value (can be a complex expression!)
543  @param H header size in bytes (may be zero)
544  @param A alignment (may be zero)
545  @return V (value-result macro parameter)
546 */
547 #define vec_validate_init_empty_ha(V,I,INIT,H,A) \
548 do { \
549  word _v(i) = (I); \
550  word _v(l) = vec_len (V); \
551  if (_v(i) >= _v(l)) \
552  { \
553  vec_resize_ha ((V), 1 + (_v(i) - _v(l)), (H), (A)); \
554  while (_v(l) <= _v(i)) \
555  { \
556  (V)[_v(l)] = (INIT); \
557  _v(l)++; \
558  } \
559  } \
560 } while (0)
561 
562 /** \brief Make sure vector is long enough for given index
563  and initialize empty space (no header, unspecified alignment)
564 
565  @param V (possibly NULL) pointer to a vector.
566  @param I vector index which will be valid upon return
567  @param INIT initial value (can be a complex expression!)
568  @return V (value-result macro parameter)
569 */
570 
571 #define vec_validate_init_empty(V,I,INIT) \
572  vec_validate_init_empty_ha(V,I,INIT,0,0)
573 
574 /** \brief Make sure vector is long enough for given index
575  and initialize empty space (no header, alignment alignment)
576 
577  @param V (possibly NULL) pointer to a vector.
578  @param I vector index which will be valid upon return
579  @param INIT initial value (can be a complex expression!)
580  @param A alignment (may be zero)
581  @return V (value-result macro parameter)
582 */
583 #define vec_validate_init_empty_aligned(V,I,INIT,A) \
584  vec_validate_init_empty_ha(V,I,INIT,0,A)
585 
586 /** \brief Add 1 element to end of vector (general version).
587 
588  @param V pointer to a vector
589  @param E element to add
590  @param H header size in bytes (may be zero)
591  @param A alignment (may be zero)
592  @return V (value-result macro parameter)
593 */
594 #define vec_add1_ha(V,E,H,A) \
595 do { \
596  word _v(l) = vec_len (V); \
597  V = _vec_resize ((V), 1, (_v(l) + 1) * sizeof ((V)[0]), (H), (A)); \
598  (V)[_v(l)] = (E); \
599 } while (0)
600 
601 /** \brief Add 1 element to end of vector (unspecified alignment).
602 
603  @param V pointer to a vector
604  @param E element to add
605  @return V (value-result macro parameter)
606 */
607 #define vec_add1(V,E) vec_add1_ha(V,E,0,0)
608 
609 /** \brief Add 1 element to end of vector (alignment specified).
610 
611  @param V pointer to a vector
612  @param E element to add
613  @param A alignment (may be zero)
614  @return V (value-result macro parameter)
615 */
616 #define vec_add1_aligned(V,E,A) vec_add1_ha(V,E,0,A)
617 
618 /** \brief Add N elements to end of vector V,
619  return pointer to new elements in P. (general version)
620 
621  @param V pointer to a vector
622  @param P pointer to new vector element(s)
623  @param N number of elements to add
624  @param H header size in bytes (may be zero)
625  @param A alignment (may be zero)
626  @return V and P (value-result macro parameters)
627 */
628 #define vec_add2_ha(V,P,N,H,A) \
629 do { \
630  word _v(n) = (N); \
631  word _v(l) = vec_len (V); \
632  V = _vec_resize ((V), _v(n), (_v(l) + _v(n)) * sizeof ((V)[0]), (H), (A)); \
633  P = (V) + _v(l); \
634 } while (0)
635 
636 /** \brief Add N elements to end of vector V,
637  return pointer to new elements in P. (no header, unspecified alignment)
638 
639  @param V pointer to a vector
640  @param P pointer to new vector element(s)
641  @param N number of elements to add
642  @return V and P (value-result macro parameters)
643 */
644 
645 #define vec_add2(V,P,N) vec_add2_ha(V,P,N,0,0)
646 
647 /** \brief Add N elements to end of vector V,
648  return pointer to new elements in P. (no header, alignment specified)
649 
650  @param V pointer to a vector
651  @param P pointer to new vector element(s)
652  @param N number of elements to add
653  @param A alignment (may be zero)
654  @return V and P (value-result macro parameters)
655 */
656 
657 #define vec_add2_aligned(V,P,N,A) vec_add2_ha(V,P,N,0,A)
658 
659 /** \brief Add N elements to end of vector V (general version)
660 
661  @param V pointer to a vector
662  @param E pointer to element(s) to add
663  @param N number of elements to add
664  @param H header size in bytes (may be zero)
665  @param A alignment (may be zero)
666  @return V (value-result macro parameter)
667 */
668 #define vec_add_ha(V, E, N, H, A) \
669  do \
670  { \
671  word _v (n) = (N); \
672  if (PREDICT_TRUE (_v (n) > 0)) \
673  { \
674  word _v (l) = vec_len (V); \
675  V = _vec_resize ((V), _v (n), (_v (l) + _v (n)) * sizeof ((V)[0]), \
676  (H), (A)); \
677  clib_memcpy_fast ((V) + _v (l), (E), _v (n) * sizeof ((V)[0])); \
678  } \
679  } \
680  while (0)
681 
682 /** \brief Add N elements to end of vector V (no header, unspecified alignment)
683 
684  @param V pointer to a vector
685  @param E pointer to element(s) to add
686  @param N number of elements to add
687  @return V (value-result macro parameter)
688 */
689 #define vec_add(V,E,N) vec_add_ha(V,E,N,0,0)
690 
691 /** \brief Add N elements to end of vector V (no header, specified alignment)
692 
693  @param V pointer to a vector
694  @param E pointer to element(s) to add
695  @param N number of elements to add
696  @param A alignment (may be zero)
697  @return V (value-result macro parameter)
698 */
699 #define vec_add_aligned(V,E,N,A) vec_add_ha(V,E,N,0,A)
700 
701 /** \brief Returns last element of a vector and decrements its length
702 
703  @param V pointer to a vector
704  @return E element removed from the end of the vector
705 */
706 #define vec_pop(V) \
707 ({ \
708  uword _v(l) = vec_len (V); \
709  ASSERT (_v(l) > 0); \
710  _v(l) -= 1; \
711  _vec_len (V) = _v (l); \
712  (V)[_v(l)]; \
713 })
714 
715 /** \brief Set E to the last element of a vector, decrement vector length
716  @param V pointer to a vector
717  @param E pointer to the last vector element
718  @return E element removed from the end of the vector
719  (value-result macro parameter
720 */
721 
722 #define vec_pop2(V,E) \
723 ({ \
724  uword _v(l) = vec_len (V); \
725  if (_v(l) > 0) (E) = vec_pop (V); \
726  _v(l) > 0; \
727 })
728 
729 /** \brief Insert N vector elements starting at element M,
730  initialize new elements (general version).
731 
732  @param V (possibly NULL) pointer to a vector.
733  @param N number of elements to insert
734  @param M insertion point
735  @param INIT initial value (can be a complex expression!)
736  @param H header size in bytes (may be zero)
737  @param A alignment (may be zero)
738  @return V (value-result macro parameter)
739 */
740 #define vec_insert_init_empty_ha(V,N,M,INIT,H,A) \
741 do { \
742  word _v(l) = vec_len (V); \
743  word _v(n) = (N); \
744  word _v(m) = (M); \
745  V = _vec_resize ((V), \
746  _v(n), \
747  (_v(l) + _v(n))*sizeof((V)[0]), \
748  (H), (A)); \
749  ASSERT (_v(m) <= _v(l)); \
750  memmove ((V) + _v(m) + _v(n), \
751  (V) + _v(m), \
752  (_v(l) - _v(m)) * sizeof ((V)[0])); \
753  clib_memset ((V) + _v(m), INIT, _v(n) * sizeof ((V)[0])); \
754 } while (0)
755 
756 /** \brief Insert N vector elements starting at element M,
757  initialize new elements to zero (general version)
758 
759  @param V (possibly NULL) pointer to a vector.
760  @param N number of elements to insert
761  @param M insertion point
762  @param H header size in bytes (may be zero)
763  @param A alignment (may be zero)
764  @return V (value-result macro parameter)
765 */
766 #define vec_insert_ha(V,N,M,H,A) vec_insert_init_empty_ha(V,N,M,0,H,A)
767 
768 /** \brief Insert N vector elements starting at element M,
769  initialize new elements to zero (no header, unspecified alignment)
770 
771  @param V (possibly NULL) pointer to a vector.
772  @param N number of elements to insert
773  @param M insertion point
774  @return V (value-result macro parameter)
775 */
776 #define vec_insert(V,N,M) vec_insert_ha(V,N,M,0,0)
777 
778 /** \brief Insert N vector elements starting at element M,
779  initialize new elements to zero (no header, alignment specified)
780 
781  @param V (possibly NULL) pointer to a vector.
782  @param N number of elements to insert
783  @param M insertion point
784  @param A alignment (may be zero)
785  @return V (value-result macro parameter)
786 */
787 #define vec_insert_aligned(V,N,M,A) vec_insert_ha(V,N,M,0,A)
788 
789 /** \brief Insert N vector elements starting at element M,
790  initialize new elements (no header, unspecified alignment)
791 
792  @param V (possibly NULL) pointer to a vector.
793  @param N number of elements to insert
794  @param M insertion point
795  @param INIT initial value (can be a complex expression!)
796  @return V (value-result macro parameter)
797 */
798 
799 #define vec_insert_init_empty(V,N,M,INIT) \
800  vec_insert_init_empty_ha(V,N,M,INIT,0,0)
801 /* Resize vector by N elements starting from element M, initialize new elements to INIT (alignment specified, no header). */
802 
803 /** \brief Insert N vector elements starting at element M,
804  initialize new elements (no header, specified alignment)
805 
806  @param V (possibly NULL) pointer to a vector.
807  @param N number of elements to insert
808  @param M insertion point
809  @param INIT initial value (can be a complex expression!)
810  @param A alignment (may be zero)
811  @return V (value-result macro parameter)
812 */
813 #define vec_insert_init_empty_aligned(V,N,M,INIT,A) \
814  vec_insert_init_empty_ha(V,N,M,INIT,0,A)
815 
816 /** \brief Insert N vector elements starting at element M,
817  insert given elements (general version)
818 
819  @param V (possibly NULL) pointer to a vector.
820  @param E element(s) to insert
821  @param N number of elements to insert
822  @param M insertion point
823  @param H header size in bytes (may be zero)
824  @param A alignment (may be zero)
825  @return V (value-result macro parameter)
826 */
827 
828 #define vec_insert_elts_ha(V, E, N, M, H, A) \
829  do \
830  { \
831  word _v (n) = (N); \
832  if (PREDICT_TRUE (_v (n) > 0)) \
833  { \
834  word _v (l) = vec_len (V); \
835  word _v (m) = (M); \
836  V = _vec_resize ((V), _v (n), (_v (l) + _v (n)) * sizeof ((V)[0]), \
837  (H), (A)); \
838  ASSERT (_v (m) <= _v (l)); \
839  memmove ((V) + _v (m) + _v (n), (V) + _v (m), \
840  (_v (l) - _v (m)) * sizeof ((V)[0])); \
841  clib_memcpy_fast ((V) + _v (m), (E), _v (n) * sizeof ((V)[0])); \
842  } \
843  } \
844  while (0)
845 
846 /** \brief Insert N vector elements starting at element M,
847  insert given elements (no header, unspecified alignment)
848 
849  @param V (possibly NULL) pointer to a vector.
850  @param E element(s) to insert
851  @param N number of elements to insert
852  @param M insertion point
853  @return V (value-result macro parameter)
854 */
855 #define vec_insert_elts(V,E,N,M) vec_insert_elts_ha(V,E,N,M,0,0)
856 
857 /** \brief Insert N vector elements starting at element M,
858  insert given elements (no header, specified alignment)
859 
860  @param V (possibly NULL) pointer to a vector.
861  @param E element(s) to insert
862  @param N number of elements to insert
863  @param M insertion point
864  @param A alignment (may be zero)
865  @return V (value-result macro parameter)
866 */
867 #define vec_insert_elts_aligned(V,E,N,M,A) vec_insert_elts_ha(V,E,N,M,0,A)
868 
869 /** \brief Delete N elements starting at element M
870 
871  @param V pointer to a vector
872  @param N number of elements to delete
873  @param M first element to delete
874  @return V (value-result macro parameter)
875 */
876 #define vec_delete(V,N,M) \
877 do { \
878  word _v(l) = vec_len (V); \
879  word _v(n) = (N); \
880  word _v(m) = (M); \
881  /* Copy over deleted elements. */ \
882  if (_v(l) - _v(n) - _v(m) > 0) \
883  memmove ((V) + _v(m), (V) + _v(m) + _v(n), \
884  (_v(l) - _v(n) - _v(m)) * sizeof ((V)[0])); \
885  /* Zero empty space at end (for future re-allocation). */ \
886  if (_v(n) > 0) \
887  clib_memset ((V) + _v(l) - _v(n), 0, _v(n) * sizeof ((V)[0])); \
888  _vec_len (V) -= _v(n); \
889  CLIB_MEM_POISON(vec_end(V), _v(n) * sizeof ((V)[0])); \
890 } while (0)
891 
892 /** \brief Delete the element at index I
893 
894  @param V pointer to a vector
895  @param I index to delete
896 */
897 #define vec_del1(v,i) \
898 do { \
899  uword _vec_del_l = _vec_len (v) - 1; \
900  uword _vec_del_i = (i); \
901  if (_vec_del_i < _vec_del_l) \
902  (v)[_vec_del_i] = (v)[_vec_del_l]; \
903  _vec_len (v) = _vec_del_l; \
904  CLIB_MEM_POISON(vec_end(v), sizeof ((v)[0])); \
905 } while (0)
906 
907 /** \brief Append v2 after v1. Result in v1.
908  @param V1 target vector
909  @param V2 vector to append
910 */
911 
912 #define vec_append(v1, v2) \
913  do \
914  { \
915  uword _v (l1) = vec_len (v1); \
916  uword _v (l2) = vec_len (v2); \
917  \
918  if (PREDICT_TRUE (_v (l2) > 0)) \
919  { \
920  v1 = _vec_resize ((v1), _v (l2), \
921  (_v (l1) + _v (l2)) * sizeof ((v1)[0]), 0, 0); \
922  clib_memcpy_fast ((v1) + _v (l1), (v2), \
923  _v (l2) * sizeof ((v2)[0])); \
924  } \
925  } \
926  while (0)
927 
928 /** \brief Append v2 after v1. Result in v1. Specified alignment.
929  @param V1 target vector
930  @param V2 vector to append
931  @param align required alignment
932 */
933 
934 #define vec_append_aligned(v1, v2, align) \
935  do \
936  { \
937  uword _v (l1) = vec_len (v1); \
938  uword _v (l2) = vec_len (v2); \
939  \
940  if (PREDICT_TRUE (_v (l2) > 0)) \
941  { \
942  v1 = _vec_resize ( \
943  (v1), _v (l2), (_v (l1) + _v (l2)) * sizeof ((v1)[0]), 0, align); \
944  clib_memcpy_fast ((v1) + _v (l1), (v2), \
945  _v (l2) * sizeof ((v2)[0])); \
946  } \
947  } \
948  while (0)
949 
950 /** \brief Prepend v2 before v1. Result in v1.
951  @param V1 target vector
952  @param V2 vector to prepend
953 */
954 
955 #define vec_prepend(v1, v2) \
956  do \
957  { \
958  uword _v (l1) = vec_len (v1); \
959  uword _v (l2) = vec_len (v2); \
960  \
961  if (PREDICT_TRUE (_v (l2) > 0)) \
962  { \
963  v1 = _vec_resize ((v1), _v (l2), \
964  (_v (l1) + _v (l2)) * sizeof ((v1)[0]), 0, 0); \
965  memmove ((v1) + _v (l2), (v1), _v (l1) * sizeof ((v1)[0])); \
966  clib_memcpy_fast ((v1), (v2), _v (l2) * sizeof ((v2)[0])); \
967  } \
968  } \
969  while (0)
970 
971 /** \brief Prepend v2 before v1. Result in v1. Specified alignment
972  @param V1 target vector
973  @param V2 vector to prepend
974  @param align required alignment
975 */
976 
977 #define vec_prepend_aligned(v1, v2, align) \
978  do \
979  { \
980  uword _v (l1) = vec_len (v1); \
981  uword _v (l2) = vec_len (v2); \
982  \
983  if (PREDICT_TRUE (_v (l2) > 0)) \
984  { \
985  v1 = _vec_resize ( \
986  (v1), _v (l2), (_v (l1) + _v (l2)) * sizeof ((v1)[0]), 0, align); \
987  memmove ((v1) + _v (l2), (v1), _v (l1) * sizeof ((v1)[0])); \
988  clib_memcpy_fast ((v1), (v2), _v (l2) * sizeof ((v2)[0])); \
989  } \
990  } \
991  while (0)
992 
993 /** \brief Zero all vector elements. Null-pointer tolerant.
994  @param var Vector to zero
995 */
996 #define vec_zero(var) \
997 do { \
998  if (var) \
999  clib_memset ((var), 0, vec_len (var) * sizeof ((var)[0])); \
1000 } while (0)
1001 
1002 /** \brief Set all vector elements to given value. Null-pointer tolerant.
1003  @param v vector to set
1004  @param val value for each vector element
1005 */
1006 #define vec_set(v,val) \
1007 do { \
1008  word _v(i); \
1009  __typeof__ ((v)[0]) _val = (val); \
1010  for (_v(i) = 0; _v(i) < vec_len (v); _v(i)++) \
1011  (v)[_v(i)] = _val; \
1012 } while (0)
1013 
1014 #ifdef CLIB_UNIX
1015 #include <stdlib.h> /* for qsort */
1016 #endif
1017 
1018 /** \brief Compare two vectors, not NULL-pointer tolerant
1019 
1020  @param v1 Pointer to a vector
1021  @param v2 Pointer to a vector
1022  @return 1 if equal, 0 if unequal
1023 */
1024 #define vec_is_equal(v1,v2) \
1025  (vec_len (v1) == vec_len (v2) && ! memcmp ((v1), (v2), vec_len (v1) * sizeof ((v1)[0])))
1026 
1027 /** \brief Compare two vectors (only applicable to vectors of signed numbers).
1028  Used in qsort compare functions.
1029 
1030  @param v1 Pointer to a vector
1031  @param v2 Pointer to a vector
1032  @return -1, 0, +1
1033 */
1034 #define vec_cmp(v1,v2) \
1035 ({ \
1036  word _v(i), _v(cmp), _v(l); \
1037  _v(l) = clib_min (vec_len (v1), vec_len (v2)); \
1038  _v(cmp) = 0; \
1039  for (_v(i) = 0; _v(i) < _v(l); _v(i)++) { \
1040  _v(cmp) = (v1)[_v(i)] - (v2)[_v(i)]; \
1041  if (_v(cmp)) \
1042  break; \
1043  } \
1044  if (_v(cmp) == 0 && _v(l) > 0) \
1045  _v(cmp) = vec_len(v1) - vec_len(v2); \
1046  (_v(cmp) < 0 ? -1 : (_v(cmp) > 0 ? +1 : 0)); \
1047 })
1048 
1049 /** \brief Search a vector for the index of the entry that matches.
1050 
1051  @param v Pointer to a vector
1052  @param E Entry to match
1053  @return index of match or ~0
1054 */
1055 #define vec_search(v,E) \
1056 ({ \
1057  word _v(i) = 0; \
1058  while (_v(i) < vec_len(v)) \
1059  { \
1060  if ((v)[_v(i)] == E) \
1061  break; \
1062  _v(i)++; \
1063  } \
1064  if (_v(i) == vec_len(v)) \
1065  _v(i) = ~0; \
1066  _v(i); \
1067 })
1068 
1069 /** \brief Search a vector for the index of the entry that matches.
1070 
1071  @param v Pointer to a vector
1072  @param E Pointer to entry to match
1073  @param fn Comparison function !0 => match
1074  @return index of match or ~0
1075 */
1076 #define vec_search_with_function(v,E,fn) \
1077 ({ \
1078  word _v(i) = 0; \
1079  while (_v(i) < vec_len(v)) \
1080  { \
1081  if (0 != fn(&(v)[_v(i)], (E))) \
1082  break; \
1083  _v(i)++; \
1084  } \
1085  if (_v(i) == vec_len(v)) \
1086  _v(i) = ~0; \
1087  _v(i); \
1088 })
1089 
1090 /** \brief Sort a vector using the supplied element comparison function
1091 
1092  Does not depend on the underlying implementation to deal correctly
1093  with null, zero-long, or 1-long vectors
1094 
1095  @param vec vector to sort
1096  @param f comparison function
1097 */
1098 #define vec_sort_with_function(vec,f) \
1099 do { \
1100  if (vec_len (vec) > 1) \
1101  qsort (vec, vec_len (vec), sizeof (vec[0]), (void *) (f)); \
1102 } while (0)
1103 
1104 /** \brief Make a vector containing a NULL terminated c-string.
1105 
1106  @param V (possibly NULL) pointer to a vector.
1107  @param S pointer to string buffer.
1108  @param L string length (NOT including the terminating NULL; a la strlen())
1109 */
1110 #define vec_validate_init_c_string(V, S, L) \
1111  do { \
1112  vec_reset_length (V); \
1113  vec_validate ((V), (L)); \
1114  if ((S) && (L)) \
1115  clib_memcpy_fast ((V), (S), (L)); \
1116  (V)[(L)] = 0; \
1117  } while (0)
1118 
1119 
1120 /** \brief Test whether a vector is a NULL terminated c-string.
1121 
1122  @param V (possibly NULL) pointer to a vector.
1123  @return BOOLEAN indicating if the vector c-string is null terminated.
1124 */
1125 #define vec_c_string_is_terminated(V) \
1126  (((V) != 0) && (vec_len (V) != 0) && ((V)[vec_len ((V)) - 1] == 0))
1127 
1128 /** \brief (If necessary) NULL terminate a vector containing a c-string.
1129 
1130  @param V (possibly NULL) pointer to a vector.
1131  @return V (value-result macro parameter)
1132 */
1133 #define vec_terminate_c_string(V) \
1134  do { \
1135  u32 vl = vec_len ((V)); \
1136  if (!vec_c_string_is_terminated(V)) \
1137  { \
1138  vec_validate ((V), vl); \
1139  (V)[vl] = 0; \
1140  } \
1141  } while (0)
1142 
1143 #endif /* included_vec_h */
1144 
1145 
1146 /*
1147  * fd.io coding-style-patch-verification: ON
1148  *
1149  * Local Variables:
1150  * eval: (c-set-style "gnu")
1151  * End:
1152  */
clib_mem_is_vec
static uword clib_mem_is_vec(void *v)
Predicate function, says whether the supplied vector is a clib heap object.
Definition: vec.h:244
VEC_NUMA_UNSPECIFIED
#define VEC_NUMA_UNSPECIFIED
Definition: mem.h:158
clib_max
#define clib_max(x, y)
Definition: clib.h:335
clib.h
clib_mem_is_vec_h
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
string.h
vec_bootstrap.h
clib_mem_get_per_numa_heap
static void * clib_mem_get_per_numa_heap(u32 numa_id)
Definition: mem.h:177
clib_mem_get_per_cpu_heap
static clib_mem_heap_t * clib_mem_get_per_cpu_heap(void)
Definition: mem.h:161
clib_mem_size
static uword clib_mem_size(void *p)
Definition: mem.h:343
PREDICT_FALSE
#define PREDICT_FALSE(x)
Definition: clib.h:124
uword
u64 uword
Definition: types.h:112
vec_free_not_inline
void vec_free_not_inline(void *v)
Definition: vec.c:154
always_inline
#define always_inline
Definition: rdma_mlx5dv.h:23
ASSERT
#define ASSERT(truth)
Definition: error_bootstrap.h:69
CLIB_MEM_UNPOISON
#define CLIB_MEM_UNPOISON(a, s)
Definition: sanitizer.h:47
clib_mem_set_per_cpu_heap
static void * clib_mem_set_per_cpu_heap(void *new_heap)
Definition: mem.h:168
vec_header_t
vector header structure
Definition: vec_bootstrap.h:55
word
i64 word
Definition: types.h:111
mem.h
vec_resize_allocate_memory
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
PREDICT_TRUE
#define PREDICT_TRUE(x)
Definition: clib.h:125
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
clib_mem_is_heap_object
static uword clib_mem_is_heap_object(void *p)
Definition: mem.h:303