/* * 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. */ /* 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. */ #ifndef included_vec_h #define included_vec_h #include /* word, etc */ #include /* clib_mem_free */ #include /* memcpy, memmove */ #include /** \file CLIB vectors are ubiquitous dynamically resized arrays with by user defined "headers". Many CLIB data structures (e.g. hash, heap, pool) are vectors with various different headers. The memory layout looks like this: ~~~~~~~~ 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 ... ~~~~~~~~ The user pointer contains the address of vector element # 0. Null pointer vectors are valid and mean a zero length vector. You can reset the length of an allocated vector to zero via the vec_reset_length(v) macro, or by setting the vector length field to zero (e.g. _vec_len (v) = 0). Vec_reset_length(v) preferred: it understands Null pointers. Typically, the header is not present. Headers allow for other data structures to be built atop CLIB vectors. 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, pool, etc.). Many macros have \_a variants supporting alignment of vector elements and \_h variants supporting non-zero-length vector headers. The \_ha variants support both. Additionally cacheline alignment within a vector element structure can be specified using the CLIB_CACHE_LINE_ALIGN_MARK() macro. Standard programming error: memorize a pointer to the ith element of a vector then expand it. Vectors expand by 3/2, so such code may appear to work for a period of time. Memorize vector indices which are invariant. */ /** \brief Low-level (re)allocation function, usually not called directly @param v pointer to a vector @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 */ 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); } /* 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; } static_always_inline void _vec_update_pointer (void **vp, void *v) { /* avoid store if not needed */ if (v != vp[0]) vp[0] = v; } static_always_inline void * vec_get_heap (void *v) { if (v == 0 || _vec_find (v)->default_heap == 1) return 0; return _vec_heap (v); } static_always_inline uword vec_get_align (void *v) { return 1ULL << _vec_find (v)->log2_align; } 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; ASSERT (vp[0] == 0); v = _vec_alloc_internal (n_elts, &va); _vec_set_len (v, 0, elt_sz); _vec_update_pointer (vp, v); } /** \brief Pre-allocate a vector (generic version) @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) */ #define vec_prealloc_hap(V, N, H, A, P) \ _vec_prealloc ((void **) &(V), N, H, _vec_align (V, A), P, _vec_elt_sz (V)) /** \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) /** \brief Pre-allocate a vector (heap version) @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) 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; return 1; } /** \brief Determine if vector will resize with next allocation @param V pointer to a vector @param N number of elements to add @return 1 if vector will resize 0 otherwise */ #define vec_resize_will_expand(V, N) \ _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 /** \brief Resize a vector (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). @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) */ 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; } 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); } #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. Vector will have room for H header bytes and will have user's data aligned at alignment A (rounded to next power of 2). @param V pointer to a vector @param N number of elements to add @return V (value-result macro parameter) */ #define vec_resize(V,N) vec_resize_ha(V,N,0,0) /** \brief Resize a vector (no header, alignment specified). 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). @param V pointer to a vector @param N number of elements to add @param A alignment (may be zero) @return V (value-result macro parameter) */ #define vec_resize_aligned(V,N,A) vec_resize_ha(V,N,0,A) /** \brief Allocate space for N more elements @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_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) @param V pointer to a vector @param N number of elements to add @return V (value-result macro parameter) */ #define vec_alloc(V,N) vec_alloc_ha(V,N,0,0) /** \brief Allocate space for N more elements (no header, given alignment) @param V pointer to a vector @param N number of elements to add @param A alignment (may be zero) @return V (value-result macro parameter) */ #define vec_alloc_aligned(V,N,A) vec_alloc_ha(V,N,0,A) /** \brief Create new vector of given type and length (general version). @param T type of elements in new vector @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_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). @param T type of elements in new vector @param N number of elements to add @return V new vector */ #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). @param T type of elements in new vector @param N number of elements to add @param A alignment (may be zero) @return V new vector */ #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 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_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) */ 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); /**\brief Free vector user header (syntactic sugar) @param h vector header @void */ #define vec_free_header(h) clib_mem_free (h) /** \brief Return copy of vector (general version). @param V pointer to a vector @param H size of header in bytes @param A alignment (may be zero) @return Vdup copy of vector */ static_always_inline void * _vec_dup (void *v, uword hdr_size, uword align, uword elt_sz) { uword len = vec_len (v); const vec_attr_t va = { .elt_sz = elt_sz, .align = align }; void *n = 0; 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) @param V pointer to a vector @return Vdup copy of vector */ #define vec_dup(V) vec_dup_ha(V,0,0) /** \brief Return copy of vector (no header, alignment specified). @param V pointer to a vector @param A alignment (may be zero) @return Vdup copy of vector */ #define vec_dup_aligned(V,A) vec_dup_ha(V,0,A) /** \brief Copy a vector, memcpy wrapper. Assumes sizeof(SRC[0]) == sizeof(DST[0]) @param DST destination @param SRC source 
/*
 * 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.
 */
/*
  Copyright (c) 2005 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.
*/

#ifndef included_fifo_h
#define included_fifo_h

#include <vppinfra/cache.h>
#include <vppinfra/error.h>	/* for ASSERT */
#include <vppinfra/vec.h>

typedef struct
{
  /* First index of valid data in fifo. */
  u32 head_index;

  /* One beyond last index in fifo. */
  u32 tail_index;
} clib_fifo_header_t;

always_inline clib_fifo_header_t *
clib_fifo_header (void *f)
{
  return vec_header (f, sizeof (clib_fifo_header_t));
}

/* Aliases. */
#define clib_fifo_len(v) vec_len(v)
#define _clib_fifo_len(v) _vec_len(v)
#define clib_fifo_end(v) vec_end(v)

always_inline uword
clib_fifo_elts (void *v)
{
  word l, r;
  clib_fifo_header_t *f = clib_fifo_header (v);

  if (!v)
    return 0;

  l = _clib_fifo_len (v);
  r = (word) f->tail_index - (word) f->head_index;
  r = r < 0 ? r + l : r;
  ASSERT (r >= 0 && r <= l);
  return r;
}

always_inline uword
clib_fifo_free_elts (void *v)
{
  return clib_fifo_len (v) - clib_fifo_elts (v);
}

always_inline void
clib_fifo_reset (void *v)
{
  clib_fifo_header_t *f = clib_fifo_header (v);
  if (v)
    {
      f->head_index = f->tail_index = 0;
      _vec_len (v) = 0;
    }
}

/* External resize function. */
void *_clib_fifo_resize (void *v, uword n_elts, uword elt_bytes);

#define clib_fifo_resize(f,n_elts) \
  f = _clib_fifo_resize ((f), (n_elts), sizeof ((f)[0]))

always_inline void *
_clib_fifo_validate (void *v, uword n_elts, uword elt_bytes)
{
  if (clib_fifo_free_elts (v) < n_elts)
    v = _clib_fifo_resize (v, n_elts, elt_bytes);
  return v;
}

#define clib_fifo_validate(f,n_elts) \
  f = _clib_fifo_validate ((f), (n_elts), sizeof (f[0]))

/* Advance tail pointer by N_ELTS which can be either positive or negative. */
always_inline void *
_clib_fifo_advance_tail (void *v, word n_elts, uword elt_bytes,
			 uword * tail_return)
{
  word i, l, n_free;
  clib_fifo_header_t *f;

  n_free = clib_fifo_free_elts (v);
  if (n_free < n_elts)
    {
      v = _clib_fifo_resize (v, n_elts, elt_bytes);
      n_free = clib_fifo_free_elts (v);
    }

  ASSERT (n_free >= n_elts);
  n_free -= n_elts;

  f = clib_fifo_header (v);
  l = _clib_fifo_len (v);
  i = f->tail_index;

  if (n_free == 0)
    {
      /* Mark fifo full. */
      f->tail_index = f->head_index + l;
    }
  else
    {
      word n = f->tail_index + n_elts;
      if (n >= l)
	n -= l;
      else if (n < 0)
	n += l;
      ASSERT (n >= 0 && n < l);
      f->tail_index = n;
    }

  ASSERT (clib_fifo_free_elts (v) == n_free);

  if (tail_return)
    *tail_return = n_elts > 0 ? i : f->tail_index;

  return v;
}

#define clib_fifo_advance_tail(f,n_elts)				\
({									\
  uword _i;								\
  (f) = _clib_fifo_advance_tail ((f), (n_elts), sizeof ((f)[0]), &_i);	\
  (f) + _i;								\
})

always_inline uword
clib_fifo_advance_head (void *v, uword n_elts)
{
  clib_fifo_header_t *f;
  uword l, i, n;

  ASSERT (clib_fifo_elts (v) >= n_elts);
  f = clib_fifo_header (v);
  l = _clib_fifo_len (v);

  /* If fifo was full, restore tail pointer. */
  if (f->tail_index == f->head_index + l)
    f->tail_index = f->head_index;

  n = i = f->head_index;
  n += n_elts;
  n = n >= l ? n - l : n;
  ASSERT (n < l);
  f->head_index = n;

  return i;
}

/* Add given element to fifo. */
#define clib_fifo_add1(f,e)					\
do {								\
  uword _i;							\
  (f) = _clib_fifo_advance_tail ((f), 1, sizeof ((f)[0]), &_i);	\
  (f)[_i] = (e);						\
} while (0)

/* Add element to fifo; return pointer to new element. */
#define clib_fifo_add2(f,p)					\
do {								\
  uword _i;							\
  (f) = _clib_fifo_advance_tail ((f), 1, sizeof ((f)[0]), &_i);	\
  (p) = (f) + _i;						\
} while (0)

/* Add several elements to fifo. */
#define clib_fifo_add(f,e,n)						\
do {									\
  uword _i, _l; word _n0, _n1;						\
									\
  _n0 = (n);								\
  (f) = _clib_fifo_advance_tail ((f), _n0, sizeof ((f)[0]), &_i);	\
  _l = clib_fifo_len (f);						\
  _n1 = _i + _n0 - _l;							\
  _n1 = _n1 < 0 ? 0 : _n1;						\
  _n0 -= _n1;								\
  clib_memcpy_fast ((f) + _i, (e), _n0 * sizeof ((f)[0]));		\
  if (_n1)								\
    clib_memcpy_fast ((f) + 0, (e) + _n0, _n1 * sizeof ((f)[0]));	\
} while (0)

/* Subtract element from fifo. */
#define clib_fifo_sub1(f,e)			\
do {						\
  uword _i;					\
  ASSERT (clib_fifo_elts (f) >= 1);		\
  _i = clib_fifo_advance_head ((f), 1);		\
  (e) = (f)[_i];				\
} while (0)

#define clib_fifo_sub2(f,p)			\
do {						\
  uword _i;					\
  ASSERT (clib_fifo_elts (f) >= 1);		\
  _i = clib_fifo_advance_head ((f), 1);		\
  (p) = (f) + _i;				\
} while (0)

always_inline uword
clib_fifo_head_index (void *v)
{
  clib_fifo_header_t *f = clib_fifo_header (v);
  return v ? f->head_index : 0;
}

always_inline uword
clib_fifo_tail_index (void *v)
{
  clib_fifo_header_t *f = clib_fifo_header (v);
  return v