FD.io VPP  v19.01.3-6-g70449b9b9
Vector Packet Processing
svm_fifo.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2016 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 
44 enum
45 {
49 };
50 
51 typedef struct
52 {
57 
58 typedef struct _svm_fifo
59 {
60  volatile u32 cursize; /**< current fifo size */
61  u32 nitems;
62  CLIB_CACHE_LINE_ALIGN_MARK (end_cursize);
63 
64  volatile u32 has_event; /**< non-zero if deq event exists */
65 
66  /* Backpointers */
67  u32 master_session_index;
68  u32 client_session_index;
69  u8 master_thread_index;
70  u8 client_thread_index;
71  u32 segment_manager;
72  u32 segment_index;
73  u32 ct_session_index; /**< Local session index for vpp */
74  CLIB_CACHE_LINE_ALIGN_MARK (end_shared);
75  u32 head;
76  volatile u32 want_tx_ntf; /**< producer wants nudge */
77  volatile u32 has_tx_ntf;
78  CLIB_CACHE_LINE_ALIGN_MARK (end_consumer);
79 
80  /* producer */
81  u32 tail;
82 
83  ooo_segment_t *ooo_segments; /**< Pool of ooo segments */
84  u32 ooos_list_head; /**< Head of out-of-order linked-list */
85  u32 ooos_newest; /**< Last segment to have been updated */
86  struct _svm_fifo *next; /**< next in freelist/active chain */
87  struct _svm_fifo *prev; /**< prev in active chain */
88 #if SVM_FIFO_TRACE
90 #endif
91  u32 freelist_index; /**< aka log2(allocated_size) - const. */
92  i8 refcnt; /**< reference count */
94 } svm_fifo_t;
95 
96 typedef enum
97 {
100 
101 typedef struct svm_fifo_segment_
102 {
106 
107 #if SVM_FIFO_TRACE
108 #define svm_fifo_trace_add(_f, _s, _l, _t) \
109 { \
110  svm_fifo_trace_elem_t *trace_elt; \
111  vec_add2(_f->trace, trace_elt, 1); \
112  trace_elt->offset = _s; \
113  trace_elt->len = _l; \
114  trace_elt->action = _t; \
115 }
116 #else
117 #define svm_fifo_trace_add(_f, _s, _l, _t)
118 #endif
119 
120 u8 *svm_fifo_dump_trace (u8 * s, svm_fifo_t * f);
121 u8 *svm_fifo_replay (u8 * s, svm_fifo_t * f, u8 no_read, u8 verbose);
122 
123 static inline u32
125 {
126  return clib_atomic_load_acq_n (&f->cursize);
127 }
128 
129 static inline int
131 {
132  return (clib_atomic_load_acq_n (&f->cursize) == f->nitems);
133 }
134 
135 static inline int
137 {
138  return (clib_atomic_load_acq_n (&f->cursize) == 0);
139 }
140 
141 static inline u32
143 {
144  return f->nitems - svm_fifo_max_dequeue (f);
145 }
146 
147 static inline int
149 {
150  return f->has_event;
151 }
152 
153 static inline u8
155 {
156  return f->ooos_list_head != OOO_SEGMENT_INVALID_INDEX;
157 }
158 
159 /**
160  * Sets fifo event flag.
161  *
162  * Also acts as a release barrier.
163  *
164  * @return 1 if flag was not set.
165  */
168 {
169  /* return __sync_lock_test_and_set (&f->has_event, 1) == 0;
170  return __sync_bool_compare_and_swap (&f->has_event, 0, 1); */
171  return !__atomic_exchange_n (&f->has_event, 1, __ATOMIC_RELEASE);
172 }
173 
174 /**
175  * Unsets fifo event flag.
176  *
177  * Also acts as a release barrier.
178  */
179 always_inline void
181 {
182  clib_atomic_release (&f->has_event);
183 }
184 
185 svm_fifo_t *svm_fifo_create (u32 data_size_in_bytes);
186 void svm_fifo_free (svm_fifo_t * f);
187 
188 int svm_fifo_enqueue_nowait (svm_fifo_t * f, u32 max_bytes,
189  const u8 * copy_from_here);
191  u32 required_bytes, u8 * copy_from_here);
192 int svm_fifo_dequeue_nowait (svm_fifo_t * f, u32 max_bytes, u8 * copy_here);
193 
194 int svm_fifo_peek (svm_fifo_t * f, u32 offset, u32 max_bytes, u8 * copy_here);
195 int svm_fifo_dequeue_drop (svm_fifo_t * f, u32 max_bytes);
199 void svm_fifo_init_pointers (svm_fifo_t * f, u32 pointer);
200 void svm_fifo_overwrite_head (svm_fifo_t * f, u8 * data, u32 len);
202 
203 /**
204  * Max contiguous chunk of data that can be read
205  */
208 {
209  return ((f->tail > f->head) ? (f->tail - f->head) : (f->nitems - f->head));
210 }
211 
212 /**
213  * Max contiguous chunk of data that can be written
214  */
217 {
218  return ((f->tail >= f->head) ? (f->nitems - f->tail) : (f->head - f->tail));
219 }
220 
221 /**
222  * Advance tail pointer
223  *
224  * Useful for moving tail pointer after external enqueue.
225  */
226 always_inline void
228 {
229  ASSERT (bytes <= svm_fifo_max_enqueue (f));
230  f->tail = (f->tail + bytes) % f->nitems;
231  f->cursize += bytes;
232 }
233 
236 {
237  return (f->data + f->head);
238 }
239 
242 {
243  return (f->data + f->tail);
244 }
245 
248 {
249  return f->nitems;
250 }
251 
252 static inline void
254 {
255  f->want_tx_ntf |= ntf_type;
256 }
257 
258 static inline void
260 {
261  f->want_tx_ntf &= ~ntf_type;
262 }
263 
264 static inline void
266 {
267  /* Set the flag if want_tx_notif_if_full was the only ntf requested */
268  f->has_tx_ntf = f->want_tx_ntf == SVM_FIFO_WANT_TX_NOTIF_IF_FULL;
270 }
271 
272 static inline void
274 {
275  f->has_tx_ntf = 0;
276 }
277 
278 static inline u8
280 {
281  u8 want_ntf = f->want_tx_ntf;
282 
283  if (PREDICT_TRUE (want_ntf == SVM_FIFO_NO_TX_NOTIF))
284  return 0;
285  else if (want_ntf & SVM_FIFO_WANT_TX_NOTIF)
286  return 1;
287  else if (want_ntf & SVM_FIFO_WANT_TX_NOTIF_IF_FULL)
288  {
289  u32 max_deq = svm_fifo_max_dequeue (f);
290  u32 nitems = svm_fifo_nitems (f);
291  if (!f->has_tx_ntf && max_deq < nitems
292  && max_deq + n_last_deq >= nitems)
293  return 1;
294 
295  return 0;
296  }
297  return 0;
298 }
299 
302 
305 {
306  if (f->ooos_newest == OOO_SEGMENT_INVALID_INDEX)
307  return 0;
308  return pool_elt_at_index (f->ooo_segments, f->ooos_newest);
309 }
310 
311 always_inline void
313 {
314  f->ooos_newest = OOO_SEGMENT_INVALID_INDEX;
315 }
316 
319 {
320  /* Ambiguous. Assumption is that ooo segments don't touch tail */
321  if (PREDICT_FALSE (pos == f->tail && f->tail == f->head))
322  return f->nitems;
323 
324  return (((f->nitems + pos) - f->tail) % f->nitems);
325 }
326 
329 {
330  return (((f->nitems + f->tail) - pos) % f->nitems);
331 }
332 
335 {
336  return ooo_segment_distance_from_tail (f, s->start);
337 }
338 
341 {
342  return ooo_segment_distance_from_tail (f, s->start) + s->length;
343 }
344 
347 {
348  return s->length;
349 }
350 
353 {
355  return 0;
356  return pool_elt_at_index (f->ooo_segments, s->prev);
357 }
358 
361 {
363  return 0;
364  return pool_elt_at_index (f->ooo_segments, s->next);
365 }
366 
367 #endif /* __included_ssvm_fifo_h__ */
368 
369 /*
370  * fd.io coding-style-patch-verification: ON
371  *
372  * Local Variables:
373  * eval: (c-set-style "gnu")
374  * End:
375  */
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:130
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:154
format_function_t format_svm_fifo
Definition: svm_fifo.h:201
#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:142
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:253
static u8 * svm_fifo_tail(svm_fifo_t *f)
Definition: svm_fifo.h:241
unsigned char u8
Definition: types.h:56
static u32 ooo_segment_distance_from_tail(svm_fifo_t *f, u32 pos)
Definition: svm_fifo.h:318
struct _svm_fifo svm_fifo_t
u8 *() format_function_t(u8 *s, va_list *args)
Definition: format.h:48
static void svm_fifo_enqueue_nocopy(svm_fifo_t *f, u32 bytes)
Advance tail pointer.
Definition: svm_fifo.h:227
static int svm_fifo_is_empty(svm_fifo_t *f)
Definition: svm_fifo.h:136
static u32 ooo_segment_end_offset(svm_fifo_t *f, ooo_segment_t *s)
Definition: svm_fifo.h:340
#define always_inline
Definition: clib.h:98
static u32 svm_fifo_max_dequeue(svm_fifo_t *f)
Definition: svm_fifo.h:124
static u32 svm_fifo_max_write_chunk(svm_fifo_t *f)
Max contiguous chunk of data that can be written.
Definition: svm_fifo.h:216
static u32 ooo_segment_length(svm_fifo_t *f, ooo_segment_t *s)
Definition: svm_fifo.h:346
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:235
static u32 svm_fifo_nitems(svm_fifo_t *f)
Definition: svm_fifo.h:247
static u32 svm_fifo_max_read_chunk(svm_fifo_t *f)
Max contiguous chunk of data that can be read.
Definition: svm_fifo.h:207
static void svm_fifo_newest_ooo_segment_reset(svm_fifo_t *f)
Definition: svm_fifo.h:312
static u8 svm_fifo_needs_tx_ntf(svm_fifo_t *f, u32 n_last_deq)
Definition: svm_fifo.h:279
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:511
void svm_fifo_dequeue_drop_all(svm_fifo_t *f)
Definition: svm_fifo.c:774
#define clib_atomic_release(a)
Definition: atomics.h:41
static void svm_fifo_clear_tx_ntf(svm_fifo_t *f)
Definition: svm_fifo.h:265
static u32 ooo_segment_offset(svm_fifo_t *f, ooo_segment_t *s)
Definition: svm_fifo.h:334
#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:360
static void svm_fifo_unset_event(svm_fifo_t *f)
Unsets fifo event flag.
Definition: svm_fifo.h:180
signed char i8
Definition: types.h:45
static ooo_segment_t * svm_fifo_newest_ooo_segment(svm_fifo_t *f)
Definition: svm_fifo.h:304
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:259
static u8 svm_fifo_set_event(svm_fifo_t *f)
Sets fifo event flag.
Definition: svm_fifo.h:167
struct svm_fifo_segment_ svm_fifo_segment_t
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:352
#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
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
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:273
u32 svm_fifo_number_ooo_segments(svm_fifo_t *f)
Definition: svm_fifo.c:828
svm_fifo_err_t
Definition: svm_fifo.h:96
static int svm_fifo_has_event(svm_fifo_t *f)
Definition: svm_fifo.h:148
#define clib_atomic_load_acq_n(a)
Definition: atomics.h:43
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:328