FD.io VPP  v19.04.2-12-g66b1689
Vector Packet Processing
svm_fifo.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2016-2019 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 #ifndef __included_ssvm_fifo_h__
16 #define __included_ssvm_fifo_h__
17 
18 #include <vppinfra/clib.h>
19 #include <vppinfra/vec.h>
20 #include <vppinfra/mheap.h>
21 #include <vppinfra/heap.h>
22 #include <vppinfra/pool.h>
23 #include <vppinfra/format.h>
24 #include <pthread.h>
25 
26 /** Out-of-order segment */
27 typedef struct
28 {
29  u32 next; /**< Next linked-list element pool index */
30  u32 prev; /**< Previous linked-list element pool index */
31 
32  u32 start; /**< Start of segment, normalized*/
33  u32 length; /**< Length of segment */
35 
38 
39 #define SVM_FIFO_TRACE (0)
40 #define OOO_SEGMENT_INVALID_INDEX ((u32)~0)
41 #define SVM_FIFO_INVALID_SESSION_INDEX ((u32)~0)
42 #define SVM_FIFO_INVALID_INDEX ((u32)~0)
43 #define SVM_FIFO_MAX_EVT_SUBSCRIBERS 8
44 
45 enum
46 {
50 };
51 
52 typedef struct
53 {
58 
59 typedef struct _svm_fifo
60 {
61  CLIB_CACHE_LINE_ALIGN_MARK (shared_first);
62  volatile u32 cursize; /**< current fifo size */
63  u32 nitems;
64 
65  CLIB_CACHE_LINE_ALIGN_MARK (shared_second);
66  volatile u32 has_event; /**< non-zero if deq event exists */
67 
68  u32 master_session_index;
69  u32 client_session_index;
70  u8 master_thread_index;
71  u8 client_thread_index;
72  u32 segment_manager;
73  u32 segment_index;
74  u32 ct_session_index; /**< Local session index for vpp */
75  u32 freelist_index; /**< aka log2(allocated_size) - const. */
76  i8 refcnt; /**< reference count */
77 
78  CLIB_CACHE_LINE_ALIGN_MARK (consumer);
79  u32 head;
80  volatile u32 want_tx_ntf; /**< producer wants nudge */
81  volatile u32 has_tx_ntf;
82 
83  CLIB_CACHE_LINE_ALIGN_MARK (producer);
84  u32 tail;
85 
86  ooo_segment_t *ooo_segments; /**< Pool of ooo segments */
87  u32 ooos_list_head; /**< Head of out-of-order linked-list */
88  u32 ooos_newest; /**< Last segment to have been updated */
89  struct _svm_fifo *next; /**< next in freelist/active chain */
90  struct _svm_fifo *prev; /**< prev in active chain */
91  volatile u8 n_subscribers;
92  u8 subscribers[SVM_FIFO_MAX_EVT_SUBSCRIBERS];
93 
94 #if SVM_FIFO_TRACE
96 #endif
97 
99 } svm_fifo_t;
100 
101 typedef enum
102 {
105 
106 typedef struct svm_fifo_segment_
107 {
111 
112 #if SVM_FIFO_TRACE
113 #define svm_fifo_trace_add(_f, _s, _l, _t) \
114 { \
115  svm_fifo_trace_elem_t *trace_elt; \
116  vec_add2(_f->trace, trace_elt, 1); \
117  trace_elt->offset = _s; \
118  trace_elt->len = _l; \
119  trace_elt->action = _t; \
120 }
121 #else
122 #define svm_fifo_trace_add(_f, _s, _l, _t)
123 #endif
124 
125 u8 *svm_fifo_dump_trace (u8 * s, svm_fifo_t * f);
126 u8 *svm_fifo_replay (u8 * s, svm_fifo_t * f, u8 no_read, u8 verbose);
127 
128 static inline u32
130 {
131  return clib_atomic_load_acq_n (&f->cursize);
132 }
133 
134 static inline int
136 {
137  return (clib_atomic_load_acq_n (&f->cursize) == f->nitems);
138 }
139 
140 static inline int
142 {
143  return (clib_atomic_load_acq_n (&f->cursize) == 0);
144 }
145 
146 static inline u32
148 {
149  return f->nitems - svm_fifo_max_dequeue (f);
150 }
151 
152 static inline int
154 {
155  return f->has_event;
156 }
157 
158 static inline u8
160 {
161  return f->ooos_list_head != OOO_SEGMENT_INVALID_INDEX;
162 }
163 
164 /**
165  * Sets fifo event flag.
166  *
167  * Also acts as a release barrier.
168  *
169  * @return 1 if flag was not set.
170  */
173 {
174  /* return __sync_lock_test_and_set (&f->has_event, 1) == 0;
175  return __sync_bool_compare_and_swap (&f->has_event, 0, 1); */
176  return !clib_atomic_swap_rel_n (&f->has_event, 1);
177 }
178 
179 /**
180  * Unsets fifo event flag.
181  *
182  * Also acts as an acquire barrier.
183  */
184 always_inline void
186 {
187  clib_atomic_swap_acq_n (&f->has_event, 0);
188 }
189 
190 svm_fifo_t *svm_fifo_create (u32 data_size_in_bytes);
191 void svm_fifo_free (svm_fifo_t * f);
192 
193 int svm_fifo_enqueue_nowait (svm_fifo_t * f, u32 max_bytes,
194  const u8 * copy_from_here);
196  u32 required_bytes, u8 * copy_from_here);
197 int svm_fifo_dequeue_nowait (svm_fifo_t * f, u32 max_bytes, u8 * copy_here);
198 
199 int svm_fifo_peek (svm_fifo_t * f, u32 offset, u32 max_bytes, u8 * copy_here);
200 int svm_fifo_dequeue_drop (svm_fifo_t * f, u32 max_bytes);
204 void svm_fifo_init_pointers (svm_fifo_t * f, u32 pointer);
206 void svm_fifo_add_subscriber (svm_fifo_t * f, u8 subscriber);
207 void svm_fifo_del_subscriber (svm_fifo_t * f, u8 subscriber);
209 
210 /**
211  * Max contiguous chunk of data that can be read
212  */
215 {
216  return ((f->tail > f->head) ? (f->tail - f->head) : (f->nitems - f->head));
217 }
218 
219 /**
220  * Max contiguous chunk of data that can be written
221  */
224 {
225  return ((f->tail >= f->head) ? (f->nitems - f->tail) : (f->head - f->tail));
226 }
227 
228 /**
229  * Advance tail pointer
230  *
231  * Useful for moving tail pointer after external enqueue.
232  */
233 always_inline void
235 {
236  ASSERT (bytes <= svm_fifo_max_enqueue (f));
237  f->tail = (f->tail + bytes) % f->nitems;
238  clib_atomic_fetch_add_rel (&f->cursize, bytes);
239 }
240 
243 {
244  return (f->data + f->head);
245 }
246 
249 {
250  return (f->data + f->tail);
251 }
252 
255 {
256  return f->nitems;
257 }
258 
259 static inline void
261 {
262  f->want_tx_ntf |= ntf_type;
263 }
264 
265 static inline void
267 {
268  f->want_tx_ntf &= ~ntf_type;
269 }
270 
271 static inline void
273 {
274  /* Set the flag if want_tx_notif_if_full was the only ntf requested */
275  f->has_tx_ntf = f->want_tx_ntf == SVM_FIFO_WANT_TX_NOTIF_IF_FULL;
277 }
278 
279 static inline void
281 {
282  f->has_tx_ntf = 0;
283 }
284 
285 static inline u8
287 {
288  u8 want_ntf = f->want_tx_ntf;
289 
290  if (PREDICT_TRUE (want_ntf == SVM_FIFO_NO_TX_NOTIF))
291  return 0;
292  else if (want_ntf & SVM_FIFO_WANT_TX_NOTIF)
293  return 1;
294  else if (want_ntf & SVM_FIFO_WANT_TX_NOTIF_IF_FULL)
295  {
296  u32 max_deq = svm_fifo_max_dequeue (f);
297  u32 nitems = svm_fifo_nitems (f);
298  if (!f->has_tx_ntf && max_deq < nitems
299  && max_deq + n_last_deq >= nitems)
300  return 1;
301 
302  return 0;
303  }
304  return 0;
305 }
306 
309 {
310  return f->n_subscribers;
311 }
312 
315 
318 {
319  if (f->ooos_newest == OOO_SEGMENT_INVALID_INDEX)
320  return 0;
321  return pool_elt_at_index (f->ooo_segments, f->ooos_newest);
322 }
323 
324 always_inline void
326 {
327  f->ooos_newest = OOO_SEGMENT_INVALID_INDEX;
328 }
329 
332 {
333  /* Ambiguous. Assumption is that ooo segments don't touch tail */
334  if (PREDICT_FALSE (pos == f->tail && f->tail == f->head))
335  return f->nitems;
336 
337  return (((f->nitems + pos) - f->tail) % f->nitems);
338 }
339 
342 {
343  return (((f->nitems + f->tail) - pos) % f->nitems);
344 }
345 
348 {
349  return ooo_segment_distance_from_tail (f, s->start);
350 }
351 
354 {
355  return ooo_segment_distance_from_tail (f, s->start) + s->length;
356 }
357 
360 {
361  return s->length;
362 }
363 
366 {
368  return 0;
369  return pool_elt_at_index (f->ooo_segments, s->prev);
370 }
371 
374 {
376  return 0;
377  return pool_elt_at_index (f->ooo_segments, s->next);
378 }
379 
380 #endif /* __included_ssvm_fifo_h__ */
381 
382 /*
383  * fd.io coding-style-patch-verification: ON
384  *
385  * Local Variables:
386  * eval: (c-set-style "gnu")
387  * End:
388  */
int svm_fifo_dequeue_drop(svm_fifo_t *f, u32 max_bytes)
Definition: svm_fifo.c:734
static vlib_cli_command_t trace
(constructor) VLIB_CLI_COMMAND (trace)
Definition: vlib_api_cli.c:862
#define CLIB_CACHE_LINE_ALIGN_MARK(mark)
Definition: cache.h:60
format_function_t format_ooo_segment
Definition: svm_fifo.h:36
static int svm_fifo_is_full(svm_fifo_t *f)
Definition: svm_fifo.h:135
u8 * svm_fifo_replay(u8 *s, svm_fifo_t *f, u8 no_read, u8 verbose)
Definition: svm_fifo.c:92
static u8 svm_fifo_has_ooo_data(svm_fifo_t *f)
Definition: svm_fifo.h:159
format_function_t format_svm_fifo
Definition: svm_fifo.h:208
#define PREDICT_TRUE(x)
Definition: clib.h:112
Fixed length block allocator.
u32 prev
Previous linked-list element pool index.
Definition: svm_fifo.h:30
void svm_fifo_segments_free(svm_fifo_t *f, svm_fifo_segment_t *fs)
Definition: svm_fifo.c:809
static u32 svm_fifo_max_enqueue(svm_fifo_t *f)
Definition: svm_fifo.h:147
u8 data[128]
Definition: ipsec.api:248
u8 *( format_function_t)(u8 *s, va_list *args)
Definition: format.h:48
svm_fifo_t * svm_fifo_create(u32 data_size_in_bytes)
create an svm fifo, in the current heap.
Definition: svm_fifo.c:205
static void svm_fifo_add_want_tx_ntf(svm_fifo_t *f, u8 ntf_type)
Definition: svm_fifo.h:260
static u8 * svm_fifo_tail(svm_fifo_t *f)
Definition: svm_fifo.h:248
unsigned char u8
Definition: types.h:56
static u32 ooo_segment_distance_from_tail(svm_fifo_t *f, u32 pos)
Definition: svm_fifo.h:331
struct _svm_fifo svm_fifo_t
static void svm_fifo_enqueue_nocopy(svm_fifo_t *f, u32 bytes)
Advance tail pointer.
Definition: svm_fifo.h:234
static int svm_fifo_is_empty(svm_fifo_t *f)
Definition: svm_fifo.h:141
static u32 ooo_segment_end_offset(svm_fifo_t *f, ooo_segment_t *s)
Definition: svm_fifo.h:353
#define always_inline
Definition: clib.h:98
void svm_fifo_add_subscriber(svm_fifo_t *f, u8 subscriber)
Definition: svm_fifo.c:849
static u32 svm_fifo_max_dequeue(svm_fifo_t *f)
Definition: svm_fifo.h:129
static u32 svm_fifo_max_write_chunk(svm_fifo_t *f)
Max contiguous chunk of data that can be written.
Definition: svm_fifo.h:223
static u32 ooo_segment_length(svm_fifo_t *f, ooo_segment_t *s)
Definition: svm_fifo.h:359
u8 * svm_fifo_dump_trace(u8 *s, svm_fifo_t *f)
Definition: svm_fifo.c:68
int svm_fifo_dequeue_nowait(svm_fifo_t *f, u32 max_bytes, u8 *copy_here)
Definition: svm_fifo.c:678
unsigned int u32
Definition: types.h:88
static u8 * svm_fifo_head(svm_fifo_t *f)
Definition: svm_fifo.h:242
static u32 svm_fifo_nitems(svm_fifo_t *f)
Definition: svm_fifo.h:254
static u32 svm_fifo_max_read_chunk(svm_fifo_t *f)
Max contiguous chunk of data that can be read.
Definition: svm_fifo.h:214
static void svm_fifo_newest_ooo_segment_reset(svm_fifo_t *f)
Definition: svm_fifo.h:325
static u8 svm_fifo_needs_tx_ntf(svm_fifo_t *f, u32 n_last_deq)
Definition: svm_fifo.h:286
void svm_fifo_overwrite_head(svm_fifo_t *f, u8 *data, u32 len)
Definition: svm_fifo.c:607
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
Definition: pool.h:514
void svm_fifo_dequeue_drop_all(svm_fifo_t *f)
Definition: svm_fifo.c:774
static void svm_fifo_clear_tx_ntf(svm_fifo_t *f)
Definition: svm_fifo.h:272
static u32 ooo_segment_offset(svm_fifo_t *f, ooo_segment_t *s)
Definition: svm_fifo.h:347
#define PREDICT_FALSE(x)
Definition: clib.h:111
static ooo_segment_t * ooo_segment_next(svm_fifo_t *f, ooo_segment_t *s)
Definition: svm_fifo.h:373
static void svm_fifo_unset_event(svm_fifo_t *f)
Unsets fifo event flag.
Definition: svm_fifo.h:185
signed char i8
Definition: types.h:45
#define clib_atomic_fetch_add_rel(a, b)
Definition: atomics.h:48
static ooo_segment_t * svm_fifo_newest_ooo_segment(svm_fifo_t *f)
Definition: svm_fifo.h:317
u8 len
Definition: ip_types.api:49
static void svm_fifo_del_want_tx_ntf(svm_fifo_t *f, u8 ntf_type)
Definition: svm_fifo.h:266
static u8 svm_fifo_set_event(svm_fifo_t *f)
Sets fifo event flag.
Definition: svm_fifo.h:172
struct svm_fifo_segment_ svm_fifo_segment_t
#define SVM_FIFO_MAX_EVT_SUBSCRIBERS
Definition: svm_fifo.h:43
format_function_t format_ooo_list
Definition: svm_fifo.h:37
int svm_fifo_enqueue_nowait(svm_fifo_t *f, u32 max_bytes, const u8 *copy_from_here)
Definition: svm_fifo.c:530
static ooo_segment_t * ooo_segment_get_prev(svm_fifo_t *f, ooo_segment_t *s)
Definition: svm_fifo.h:365
#define OOO_SEGMENT_INVALID_INDEX
Definition: svm_fifo.h:40
void svm_fifo_init_pointers(svm_fifo_t *f, u32 pointer)
Set fifo pointers to requested offset.
Definition: svm_fifo.c:843
#define ASSERT(truth)
int svm_fifo_segments(svm_fifo_t *f, svm_fifo_segment_t *fs)
Definition: svm_fifo.c:781
#define clib_atomic_swap_acq_n(a, b)
Definition: atomics.h:45
void svm_fifo_free(svm_fifo_t *f)
Definition: svm_fifo.c:227
Out-of-order segment.
Definition: svm_fifo.h:27
u32 length
Length of segment.
Definition: svm_fifo.h:33
u32 next
Next linked-list element pool index.
Definition: svm_fifo.h:29
template key/value backing page structure
Definition: bihash_doc.h:44
#define clib_atomic_swap_rel_n(a, b)
Definition: atomics.h:46
int svm_fifo_peek(svm_fifo_t *f, u32 offset, u32 max_bytes, u8 *copy_here)
Definition: svm_fifo.c:726
static void svm_fifo_reset_tx_ntf(svm_fifo_t *f)
Definition: svm_fifo.h:280
static u8 svm_fifo_n_subscribers(svm_fifo_t *f)
Definition: svm_fifo.h:308
u32 svm_fifo_number_ooo_segments(svm_fifo_t *f)
Definition: svm_fifo.c:828
svm_fifo_err_t
Definition: svm_fifo.h:101
static int svm_fifo_has_event(svm_fifo_t *f)
Definition: svm_fifo.h:153
#define clib_atomic_load_acq_n(a)
Definition: atomics.h:43
void svm_fifo_del_subscriber(svm_fifo_t *f, u8 subscriber)
Definition: svm_fifo.c:857
u32 start
Start of segment, normalized.
Definition: svm_fifo.h:32
ooo_segment_t * svm_fifo_first_ooo_segment(svm_fifo_t *f)
Definition: svm_fifo.c:834
int svm_fifo_enqueue_with_offset(svm_fifo_t *f, u32 offset, u32 required_bytes, u8 *copy_from_here)
Definition: svm_fifo.c:598
CLIB vectors are ubiquitous dynamically resized arrays with by user defined "headers".
static u32 ooo_segment_distance_to_tail(svm_fifo_t *f, u32 pos)
Definition: svm_fifo.h:341