FD.io VPP  v16.09
Vector Packet Processing
fifo.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) 2005 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_fifo_h
39 #define included_fifo_h
40 
41 #include <vppinfra/cache.h>
42 #include <vppinfra/error.h> /* for ASSERT */
43 #include <vppinfra/vec.h>
44 
45 typedef struct
46 {
47  /* First index of valid data in fifo. */
49 
50  /* One beyond last index in fifo. */
53 
56 {
57  return vec_header (f, sizeof (clib_fifo_header_t));
58 }
59 
60 /* Aliases. */
61 #define clib_fifo_len(v) vec_len(v)
62 #define _clib_fifo_len(v) _vec_len(v)
63 #define clib_fifo_end(v) vec_end(v)
64 
66 clib_fifo_elts (void *v)
67 {
68  word l, r;
70 
71  if (!v)
72  return 0;
73 
74  l = _clib_fifo_len (v);
75  r = (word) f->tail_index - (word) f->head_index;
76  r = r < 0 ? r + l : r;
77  ASSERT (r >= 0 && r <= l);
78  return r;
79 }
80 
83 {
84  return clib_fifo_len (v) - clib_fifo_elts (v);
85 }
86 
87 always_inline void
88 clib_fifo_reset (void *v)
89 {
91  if (v)
92  {
93  f->head_index = f->tail_index = 0;
94  _vec_len (v) = 0;
95  }
96 }
97 
98 /* External resize function. */
99 void *_clib_fifo_resize (void *v, uword n_elts, uword elt_bytes);
100 
101 #define clib_fifo_resize(f,n_elts) \
102  f = _clib_fifo_resize ((f), (n_elts), sizeof ((f)[0]))
103 
104 always_inline void *
105 _clib_fifo_validate (void *v, uword n_elts, uword elt_bytes)
106 {
107  if (clib_fifo_free_elts (v) < n_elts)
108  v = _clib_fifo_resize (v, n_elts, elt_bytes);
109  return v;
110 }
111 
112 #define clib_fifo_validate(f,n_elts) \
113  f = _clib_fifo_validate ((f), (n_elts), sizeof (f[0]))
114 
115 /* Advance tail pointer by N_ELTS which can be either positive or negative. */
116 always_inline void *
117 _clib_fifo_advance_tail (void *v, word n_elts, uword elt_bytes,
118  uword * tail_return)
119 {
120  word i, l, n_free;
122 
123  n_free = clib_fifo_free_elts (v);
124  if (n_free < n_elts)
125  {
126  v = _clib_fifo_resize (v, n_elts, elt_bytes);
127  n_free = clib_fifo_free_elts (v);
128  }
129 
130  ASSERT (n_free >= n_elts);
131  n_free -= n_elts;
132 
133  f = clib_fifo_header (v);
134  l = _clib_fifo_len (v);
135  i = f->tail_index;
136 
137  if (n_free == 0)
138  {
139  /* Mark fifo full. */
140  f->tail_index = f->head_index + l;
141  }
142  else
143  {
144  word n = f->tail_index + n_elts;
145  if (n >= l)
146  n -= l;
147  else if (n < 0)
148  n += l;
149  ASSERT (n >= 0 && n < l);
150  f->tail_index = n;
151  }
152 
153  ASSERT (clib_fifo_free_elts (v) == n_free);
154 
155  if (tail_return)
156  *tail_return = n_elts > 0 ? i : f->tail_index;
157 
158  return v;
159 }
160 
161 #define clib_fifo_advance_tail(f,n_elts) \
162 ({ \
163  uword _i; \
164  (f) = _clib_fifo_advance_tail ((f), (n_elts), sizeof ((f)[0]), &_i); \
165  (f) + _i; \
166 })
167 
169 clib_fifo_advance_head (void *v, uword n_elts)
170 {
172  uword l, i, n;
173 
174  ASSERT (clib_fifo_elts (v) >= n_elts);
175  f = clib_fifo_header (v);
176  l = _clib_fifo_len (v);
177 
178  /* If fifo was full, restore tail pointer. */
179  if (f->tail_index == f->head_index + l)
180  f->tail_index = f->head_index;
181 
182  n = i = f->head_index;
183  n += n_elts;
184  n = n >= l ? n - l : n;
185  ASSERT (n < l);
186  f->head_index = n;
187 
188  return i;
189 }
190 
191 /* Add given element to fifo. */
192 #define clib_fifo_add1(f,e) \
193 do { \
194  uword _i; \
195  (f) = _clib_fifo_advance_tail ((f), 1, sizeof ((f)[0]), &_i); \
196  (f)[_i] = (e); \
197 } while (0)
198 
199 /* Add element to fifo; return pointer to new element. */
200 #define clib_fifo_add2(f,p) \
201 do { \
202  uword _i; \
203  (f) = _clib_fifo_advance_tail ((f), 1, sizeof ((f)[0]), &_i); \
204  (p) = (f) + _i; \
205 } while (0)
206 
207 /* Add several elements to fifo. */
208 #define clib_fifo_add(f,e,n) \
209 do { \
210  uword _i, _l; word _n0, _n1; \
211  \
212  _n0 = (n); \
213  (f) = _clib_fifo_advance_tail ((f), _n0, sizeof ((f)[0]), &_i); \
214  _l = clib_fifo_len (f); \
215  _n1 = _i + _n0 - _l; \
216  _n1 = _n1 < 0 ? 0 : _n1; \
217  _n0 -= _n1; \
218  clib_memcpy ((f) + _i, (e), _n0 * sizeof ((f)[0])); \
219  if (_n1) \
220  clib_memcpy ((f) + 0, (e) + _n0, _n1 * sizeof ((f)[0])); \
221 } while (0)
222 
223 /* Subtract element from fifo. */
224 #define clib_fifo_sub1(f,e) \
225 do { \
226  uword _i; \
227  ASSERT (clib_fifo_elts (f) >= 1); \
228  _i = clib_fifo_advance_head ((f), 1); \
229  (e) = (f)[_i]; \
230 } while (0)
231 
232 #define clib_fifo_sub2(f,p) \
233 do { \
234  uword _i; \
235  ASSERT (clib_fifo_elts (f) >= 1); \
236  _i = clib_fifo_advance_head ((f), 1); \
237  (p) = (f) + _i; \
238 } while (0)
239 
242 {
244  return v ? f->head_index : 0;
245 }
246 
249 {
251  return v ? f->tail_index : 0;
252 }
253 
254 #define clib_fifo_head(v) ((v) + clib_fifo_head_index (v))
255 #define clib_fifo_tail(v) ((v) + clib_fifo_tail_index (v))
256 
257 #define clib_fifo_free(f) vec_free_h((f),sizeof(clib_fifo_header_t))
258 
261 {
263  uword result = 0;
264 
265  ASSERT (i < clib_fifo_elts (v));
266 
267  if (v)
268  {
269  result = f->head_index + i;
270  if (result >= _vec_len (v))
271  result -= _vec_len (v);
272  }
273 
274  return result;
275 }
276 
277 #define clib_fifo_elt_at_index(v,i) ((v) + clib_fifo_elt_index (v, (i)))
278 
279 #define clib_fifo_foreach(v,f,body) \
280 do { \
281  uword _i, _l, _n; \
282  \
283  _i = clib_fifo_head_index (f); \
284  _l = clib_fifo_len (f); \
285  _n = clib_fifo_elts (f); \
286  while (_n > 0) \
287  { \
288  (v) = (f) + _i; \
289  do { body; } while (0); \
290  _n--; \
291  _i++; \
292  _i = _i >= _l ? 0 : _i; \
293  } \
294 } while (0)
295 
296 #endif /* included_fifo_h */
297 
298 /*
299  * fd.io coding-style-patch-verification: ON
300  *
301  * Local Variables:
302  * eval: (c-set-style "gnu")
303  * End:
304  */
sll srl srl sll sra u16x4 i
Definition: vector_sse2.h:343
static uword clib_fifo_elts(void *v)
Definition: fifo.h:66
static uword clib_fifo_elt_index(void *v, uword i)
Definition: fifo.h:260
#define always_inline
Definition: clib.h:84
static uword clib_fifo_head_index(void *v)
Definition: fifo.h:241
static uword clib_fifo_free_elts(void *v)
Definition: fifo.h:82
static void clib_fifo_reset(void *v)
Definition: fifo.h:88
static uword clib_fifo_tail_index(void *v)
Definition: fifo.h:248
static uword clib_fifo_advance_head(void *v, uword n_elts)
Definition: fifo.h:169
#define ASSERT(truth)
unsigned int u32
Definition: types.h:88
u32 head_index
Definition: fifo.h:48
u64 uword
Definition: types.h:112
u32 tail_index
Definition: fifo.h:51
static clib_fifo_header_t * clib_fifo_header(void *f)
Definition: fifo.h:55
i64 word
Definition: types.h:111
static void * vec_header(void *v, uword header_bytes)
Find a user vector header.
Definition: vec_bootstrap.h:92
#define clib_fifo_len(v)
Definition: fifo.h:61
CLIB vectors are ubiquitous dynamically resized arrays with by user defined "headers".