FD.io VPP  v20.01-48-g3e0dafb74
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  * Copyright (c) 2019 Arm Limited
4  * Copyright (c) 2010-2017 Intel Corporation and/or its affiliates.
5  * Copyright (c) 2007-2009 Kip Macy kmacy@freebsd.org
6  * Inspired from DPDK rte_ring.h (SPSC only) (derived from freebsd bufring.h).
7  * Licensed under the Apache License, Version 2.0 (the "License");
8  * you may not use this file except in compliance with the License.
9  * You may obtain a copy of the License at:
10  *
11  * http://www.apache.org/licenses/LICENSE-2.0
12  *
13  * Unless required by applicable law or agreed to in writing, software
14  * distributed under the License is distributed on an "AS IS" BASIS,
15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16  * See the License for the specific language governing permissions and
17  * limitations under the License.
18  */
19 #ifndef __included_ssvm_fifo_h__
20 #define __included_ssvm_fifo_h__
21 
22 #include <vppinfra/clib.h>
23 #include <vppinfra/vec.h>
24 #include <vppinfra/pool.h>
25 #include <vppinfra/format.h>
26 #include <vppinfra/rbtree.h>
27 
28 /** Out-of-order segment */
29 typedef struct
30 {
31  u32 next; /**< Next linked-list element pool index */
32  u32 prev; /**< Previous linked-list element pool index */
33  u32 start; /**< Start of segment, normalized*/
34  u32 length; /**< Length of segment */
36 
37 #define SVM_FIFO_TRACE (0)
38 #define OOO_SEGMENT_INVALID_INDEX ((u32)~0)
39 #define SVM_FIFO_INVALID_SESSION_INDEX ((u32)~0)
40 #define SVM_FIFO_INVALID_INDEX ((u32)~0)
41 #define SVM_FIFO_MAX_EVT_SUBSCRIBERS 7
42 
43 typedef enum svm_fifo_deq_ntf_
44 {
45  SVM_FIFO_NO_DEQ_NOTIF = 0, /**< No notification requested */
46  SVM_FIFO_WANT_DEQ_NOTIF = 1, /**< Notify on dequeue */
47  SVM_FIFO_WANT_DEQ_NOTIF_IF_FULL = 2, /**< Notify on transition from full */
48  SVM_FIFO_WANT_DEQ_NOTIF_IF_EMPTY = 4, /**< Notify on transition to empty */
50 
51 typedef struct
52 {
57 
58 typedef struct svm_fifo_chunk_
59 {
60  u32 start_byte; /**< chunk start byte */
61  u32 length; /**< length of chunk in bytes */
62  struct svm_fifo_chunk_ *next; /**< pointer to next chunk in linked-lists */
63  u8 data[0]; /**< start of chunk data */
65 
66 typedef enum svm_fifo_flag_
67 {
69  SVM_FIFO_F_GROW = 1 << 1,
75 
76 typedef struct _svm_fifo
77 {
78  CLIB_CACHE_LINE_ALIGN_MARK (shared_first);
79  u32 size; /**< size of the fifo in bytes */
80  u32 nitems; /**< usable size (size-1) */
81  svm_fifo_chunk_t *start_chunk;/**< first chunk in fifo chunk list */
82  svm_fifo_chunk_t *end_chunk; /**< end chunk in fifo chunk list */
83  svm_fifo_chunk_t *new_chunks; /**< chunks yet to be added to list */
84  rb_tree_t chunk_lookup; /**< rbtree for chunk lookup */
85  u8 flags; /**< fifo flags */
86  u8 slice_index; /**< segment slice for fifo */
87 
88  CLIB_CACHE_LINE_ALIGN_MARK (shared_second);
89  volatile u32 has_event; /**< non-zero if deq event exists */
90  u32 master_session_index; /**< session layer session index */
91  u32 client_session_index; /**< app session index */
92  u8 master_thread_index; /**< session layer thread index */
93  u8 client_thread_index; /**< app worker index */
94  i8 refcnt; /**< reference count */
95  u32 segment_manager; /**< session layer segment manager index */
96  u32 segment_index; /**< segment index in segment manager */
97  struct _svm_fifo *next; /**< next in freelist/active chain */
98  struct _svm_fifo *prev; /**< prev in active chain */
99  u32 size_decrement; /**< bytes to remove from fifo */
100 
101  CLIB_CACHE_LINE_ALIGN_MARK (consumer);
102  u32 head; /**< fifo head position/byte */
103  svm_fifo_chunk_t *head_chunk; /**< tracks chunk where head lands */
104  svm_fifo_chunk_t *ooo_deq; /**< last chunk used for ooo dequeue */
105  volatile u32 want_deq_ntf; /**< producer wants nudge */
106  volatile u32 has_deq_ntf;
107 
108  CLIB_CACHE_LINE_ALIGN_MARK (producer);
109  u32 tail; /**< fifo tail position/byte */
110  u32 ooos_list_head; /**< Head of out-of-order linked-list */
111  svm_fifo_chunk_t *tail_chunk; /**< tracks chunk where tail lands */
112  svm_fifo_chunk_t *ooo_enq; /**< last chunk used for ooo enqueue */
113  ooo_segment_t *ooo_segments; /**< Pool of ooo segments */
114  u32 ooos_newest; /**< Last segment to have been updated */
115  volatile u8 n_subscribers; /**< Number of subscribers for io events */
116  u8 subscribers[SVM_FIFO_MAX_EVT_SUBSCRIBERS];
117 
118 #if SVM_FIFO_TRACE
120 #endif
121 
122 } svm_fifo_t;
123 
124 typedef enum
125 {
129 
130 typedef struct svm_fifo_seg_
131 {
135 
136 #if SVM_FIFO_TRACE
137 #define svm_fifo_trace_add(_f, _s, _l, _t) \
138 { \
139  svm_fifo_trace_elem_t *trace_elt; \
140  vec_add2(_f->trace, trace_elt, 1); \
141  trace_elt->offset = _s; \
142  trace_elt->len = _l; \
143  trace_elt->action = _t; \
144 }
145 #else
146 #define svm_fifo_trace_add(_f, _s, _l, _t)
147 #endif
148 
149 u8 *svm_fifo_dump_trace (u8 * s, svm_fifo_t * f);
150 u8 *svm_fifo_replay (u8 * s, svm_fifo_t * f, u8 no_read, u8 verbose);
151 
152 /**
153  * Load head and tail optimized for consumer
154  *
155  * Internal function.
156  */
157 static inline void
159 {
160  /* load-relaxed: consumer owned index */
161  *head = f->head;
162  /* load-acq: consumer foreign index (paired with store-rel in producer) */
163  *tail = clib_atomic_load_acq_n (&f->tail);
164 }
165 
166 /** Load head and tail optimized for producer
167  *
168  * Internal function
169  */
170 static inline void
172 {
173  /* load relaxed: producer owned index */
174  *tail = f->tail;
175  /* load-acq: producer foreign index (paired with store-rel in consumer) */
176  *head = clib_atomic_load_acq_n (&f->head);
177 }
178 
179 /**
180  * Load head and tail independent of producer/consumer role
181  *
182  * Internal function.
183  */
184 static inline void
186 {
187  /* load-acq : consumer foreign index (paired with store-rel) */
188  *tail = clib_atomic_load_acq_n (&f->tail);
189  /* load-acq : producer foriegn index (paired with store-rel) */
190  *head = clib_atomic_load_acq_n (&f->head);
191 }
192 
193 /**
194  * Distance to a from b, i.e., a - b in the fifo
195  *
196  * Internal function.
197  */
198 static inline u32
200 {
201  return ((f->size + a - b) % f->size);
202 }
203 
204 /**
205  * Distance from a to b, i.e., b - a in the fifo
206  *
207  * Internal function.
208  */
209 static inline u32
211 {
212  return ((f->size + b - a) % f->size);
213 }
214 
215 /**
216  * Fifo current size, i.e., number of bytes enqueued
217  *
218  * Internal function.
219  */
220 static inline u32
221 f_cursize (svm_fifo_t * f, u32 head, u32 tail)
222 {
223  return (head <= tail ? tail - head : f->size + tail - head);
224 }
225 
226 /**
227  * Fifo free bytes, i.e., number of free bytes
228  *
229  * Internal function
230  */
231 static inline u32
232 f_free_count (svm_fifo_t * f, u32 head, u32 tail)
233 {
234  return (f->nitems - f_cursize (f, head, tail));
235 }
236 
237 /**
238  * Try to shrink fifo size.
239  *
240  * Internal function.
241  */
242 void svm_fifo_try_shrink (svm_fifo_t * f, u32 head, u32 tail);
243 
244 /**
245  * Create fifo of requested size
246  *
247  * Allocates fifo on current heap.
248  *
249  * @param size data size in bytes for fifo to be allocated. Will be
250  * rounded to the next highest power-of-two value.
251  * @return pointer to new fifo
252  */
254 /**
255  * Initialize fifo
256  *
257  * @param f fifo
258  * @param size size for fifo
259  */
260 void svm_fifo_init (svm_fifo_t * f, u32 size);
261 /**
262  * Initialize fifo chunks and rbtree
263  *
264  * @param f fifo
265  */
267 /**
268  * Allocate a fifo chunk on heap
269  *
270  * If the chunk is allocated on a fifo segment, this should be called
271  * with the segment's heap pushed.
272  *
273  * @param size chunk size in bytes. Will be rounded to the next highest
274  * power-of-two
275  * @return new chunk or 0 if alloc failed
276  */
278 /**
279  * Grow fifo size by adding chunk to chunk list
280  *
281  * If fifos are allocated on a segment, this should be called with
282  * the segment's heap pushed.
283  *
284  * @param f fifo to be extended
285  * @param c chunk or linked list of chunks to be added
286  */
288 /**
289  * Request to reduce fifo size by amount of bytes
290  *
291  * Because the producer might be enqueuing data when this is called, the
292  * actual size update is only applied when producer tries to enqueue new
293  * data, unless @param try_shrink is set.
294  *
295  * @param f fifo
296  * @param len number of bytes to remove from fifo. The actual number
297  * of bytes to be removed will be less or equal to this
298  * value.
299  * @param try_shrink flg to indicate if it's safe to try to shrink fifo
300  * size. It should be set only if this is called by the
301  * producer of if the producer is not using the fifo
302  * @return actual length fifo size will be reduced by
303  */
304 int svm_fifo_reduce_size (svm_fifo_t * f, u32 len, u8 try_shrink);
305 /**
306  * Removes chunks that are after fifo end byte
307  *
308  * Needs to be called with segment heap pushed.
309  *
310  * @param f fifo
311  */
313 /**
314  * Free fifo and associated state
315  *
316  * @param f fifo
317  */
318 void svm_fifo_free (svm_fifo_t * f);
319 /**
320  * Cleanup fifo chunk lookup rb tree
321  *
322  * The rb tree is allocated in segment heap so this should be called
323  * with it pushed.
324  *
325  * @param f fifo to cleanup
326  */
328 /**
329  * Cleanup fifo ooo data
330  *
331  * The ooo data is allocated in producer process memory. The fifo
332  * segment heap should not be pushed.
333  *
334  * @param f fifo to cleanup
335  */
337 /**
338  * Init fifo head and tail
339  *
340  * @param f fifo
341  * @param head head value that will be matched to a chunk
342  * @param tail tail value that will be matched to a chunk
343  */
344 void svm_fifo_init_pointers (svm_fifo_t * f, u32 head, u32 tail);
345 /**
346  * Clone fifo
347  *
348  * Clones single/default chunk fifo. It does not work for fifos with
349  * multiple chunks.
350  */
351 void svm_fifo_clone (svm_fifo_t * df, svm_fifo_t * sf);
352 /**
353  * Enqueue data to fifo
354  *
355  * Data is enqueued and tail pointer is updated atomically. If the new data
356  * enqueued partly overlaps or "touches" an out-of-order segment, said segment
357  * is "consumed" and the number of bytes returned is appropriately updated.
358  *
359  * @param f fifo
360  * @param len length of data to copy
361  * @param src buffer from where to copy the data
362  * @return number of contiguous bytes that can be consumed or error
363  */
364 int svm_fifo_enqueue (svm_fifo_t * f, u32 len, const u8 * src);
365 /**
366  * Enqueue data to fifo with offset
367  *
368  * Data is enqueued without updating tail pointer. Instead, an out-of-order
369  * list of segments is generated and maintained. Fifo takes care of coalescing
370  * contiguous or overlapping segments.
371  *
372  * @param f fifo
373  * @param offset offset at which to copy the data
374  * @param len len of data to copy
375  * @param src buffer from where to copy the data
376  * @return 0 if enqueue was successful, error otherwise
377  */
379  u8 * src);
380 
381 /**
382  * Advance tail pointer
383  *
384  * Useful for moving tail pointer after external enqueue.
385  *
386  * @param f fifo
387  * @param len number of bytes to add to tail
388  */
390 /**
391  * Overwrite fifo head with new data
392  *
393  * This should be typically used by dgram transport protocols that need
394  * to update the dgram header after dequeueing a chunk of data. It assumes
395  * that the dgram header is at most spread over two chunks.
396  *
397  * @param f fifo
398  * @param src src of new data
399  * @param len length of new data
400  */
402 /**
403  * Dequeue data from fifo
404  *
405  * Data is dequeued to consumer provided buffer and head is atomically
406  * updated.
407  *
408  * @param f fifo
409  * @param len length of data to dequeue
410  * @param dst buffer to where to dequeue the data
411  * @return number of bytes dequeued or error
412  */
413 int svm_fifo_dequeue (svm_fifo_t * f, u32 len, u8 * dst);
414 /**
415  * Peek data from fifo
416  *
417  * Data is copied from requested offset into provided dst buffer. Head is
418  * not updated.
419  *
420  * @param f fifo
421  * @param offset offset from which to copy the data
422  * @param len length of data to copy
423  * @param dst buffer to where to dequeue the data
424  * @return number of bytes peeked
425  */
426 int svm_fifo_peek (svm_fifo_t * f, u32 offset, u32 len, u8 * dst);
427 /**
428  * Dequeue and drop bytes from fifo
429  *
430  * Advances fifo head by requested amount of bytes.
431  *
432  * @param f fifo
433  * @param len number of bytes to drop
434  * @return number of bytes dropped
435  */
437 /**
438  * Dequeue and drop all bytes from fifo
439  *
440  * Advances head to tail position.
441  *
442  * @param f fifo
443  */
447 /**
448  * Add io events subscriber to list
449  *
450  * @param f fifo
451  * @param sub subscriber opaque index (typically app worker index)
452  */
453 void svm_fifo_add_subscriber (svm_fifo_t * f, u8 sub);
454 /**
455  * Remove io events subscriber form list
456  *
457  * @param f fifo
458  * @param sub subscriber index to be removed
459  */
460 void svm_fifo_del_subscriber (svm_fifo_t * f, u8 subscriber);
461 /**
462  * Number of out-of-order segments for fifo
463  *
464  * @param f fifo
465  * @return number of out of order segments
466  */
468 /**
469  * First out-of-order segment for fifo
470  *
471  * @param f fifo
472  * @return first out-of-order segment for fifo
473  */
475 /**
476  * Check if fifo is sane. Debug only.
477  *
478  * @param f fifo
479  * @return 1 if sane, 0 otherwise
480  */
482 /**
483  * Declare this fifo is used by only a single thread.
484  * In this special case, fifo-growth can be done in an efficient way without delay.
485  *
486  * @param f fifo
487  * @return 1 if the fifo is already owned by another thread, 0 otherwise
488  */
491 
492 /**
493  * Fifo max bytes to dequeue optimized for consumer
494  *
495  * @param f fifo
496  * @return max number of bytes that can be dequeued
497  */
498 static inline u32
500 {
501  u32 tail, head;
502  f_load_head_tail_cons (f, &head, &tail);
503  return f_cursize (f, head, tail);
504 }
505 
506 /**
507  * Fifo max bytes to dequeue optimized for producer
508  *
509  * @param f fifo
510  * @return max number of bytes that can be dequeued
511  */
512 static inline u32
514 {
515  u32 tail, head;
516  f_load_head_tail_prod (f, &head, &tail);
517  return f_cursize (f, head, tail);
518 }
519 
520 /**
521  * Fifo max bytes to dequeue
522  *
523  * Note: use producer or consumer specific functions for performance:
524  * @ref svm_fifo_max_dequeue_cons (svm_fifo_t *f)
525  * @ref svm_fifo_max_dequeue_prod (svm_fifo_t *f)
526  */
527 static inline u32
529 {
530  u32 tail, head;
531  f_load_head_tail_all_acq (f, &head, &tail);
532  return f_cursize (f, head, tail);
533 }
534 
535 /**
536  * Check if fifo is full optimized for producer
537  *
538  * @param f fifo
539  * @return 1 if fifo is full 0 otherwise
540  */
541 static inline int
543 {
544  return (svm_fifo_max_dequeue_prod (f) == f->nitems);
545 }
546 
547 /* Check if fifo is full.
548  *
549  * Note: use producer or consumer specific functions for performance.
550  * @ref svm_fifo_is_full_prod (svm_fifo_t * f)
551  * add cons version if needed
552  */
553 static inline int
555 {
556  return (svm_fifo_max_dequeue (f) == f->nitems);
557 }
558 
559 /**
560  * Check if fifo is empty optimized for consumer
561  *
562  * @param f fifo
563  * @return 1 if fifo is empty 0 otherwise
564  */
565 static inline int
567 {
568  return (svm_fifo_max_dequeue_cons (f) == 0);
569 }
570 
571 /**
572  * Check if fifo is empty optimized for producer
573  *
574  * @param f fifo
575  * @return 1 if fifo is empty 0 otherwise
576  */
577 static inline int
579 {
580  return (svm_fifo_max_dequeue_prod (f) == 0);
581 }
582 
583 /**
584  * Check if fifo is empty
585  *
586  * Note: use producer or consumer specific functions for perfomance.
587  * @ref svm_fifo_is_empty_cons (svm_fifo_t * f)
588  * @ref svm_fifo_is_empty_prod (svm_fifo_t * f)
589  */
590 static inline int
592 {
593  return (svm_fifo_max_dequeue (f) == 0);
594 }
595 
596 /**
597  * Check if fifo is wrapped
598  *
599  * @param f fifo
600  * @return 1 if 'normalized' head is ahead of tail
601  */
602 static inline u8
604 {
605  u32 head, tail;
606  f_load_head_tail_all_acq (f, &head, &tail);
607  return head > tail;
608 }
609 
610 /**
611  * Maximum number of bytes that can be enqueued into fifo
612  *
613  * Optimized for producer
614  *
615  * @param f fifo
616  * @return max number of bytes that can be enqueued into fifo
617  */
618 static inline u32
620 {
621  u32 head, tail;
622  f_load_head_tail_prod (f, &head, &tail);
623  if (PREDICT_FALSE (f->flags & SVM_FIFO_F_SHRINK))
624  svm_fifo_try_shrink (f, head, tail);
625  return f_free_count (f, head, tail);
626 }
627 
628 /* Maximum number of bytes that can be enqueued into fifo
629  *
630  * Note: use producer or consumer specific functions for performance.
631  * @ref svm_fifo_max_enqueue_prod (svm_fifo_t *f)
632  * add consumer specific version if needed.
633  */
634 static inline u32
636 {
637  u32 head, tail;
638  f_load_head_tail_all_acq (f, &head, &tail);
639  if (PREDICT_FALSE (f->flags & SVM_FIFO_F_SHRINK))
640  svm_fifo_try_shrink (f, head, tail);
641  return f_free_count (f, head, tail);
642 }
643 
644 /**
645  * Max contiguous chunk of data that can be read
646  */
647 static inline u32
649 {
650  u32 head, tail;
651  f_load_head_tail_cons (f, &head, &tail);
652  return tail >= head ? (tail - head) : (f->size - head);
653 }
654 
655 /**
656  * Max contiguous chunk of data that can be written
657  */
658 static inline u32
660 {
661  u32 head, tail;
662  f_load_head_tail_prod (f, &head, &tail);
663  return tail >= head ? f->size - tail : f_free_count (f, head, tail);
664 }
665 
666 static inline u8 *
668 {
669  /* load-relaxed: consumer owned index */
670  return (f->head_chunk->data + (f->head - f->head_chunk->start_byte));
671 }
672 
673 static inline u8 *
675 {
676  /* load-relaxed: producer owned index */
677  return (f->tail_chunk->data + (f->tail - f->tail_chunk->start_byte));
678 }
679 
680 static inline u8
682 {
683  return f->n_subscribers;
684 }
685 
686 /**
687  * Check if fifo has out-of-order data
688  *
689  * @param f fifo
690  * @return 1 if fifo has ooo data, 0 otherwise
691  */
692 static inline u8
694 {
695  return f->ooos_list_head != OOO_SEGMENT_INVALID_INDEX;
696 }
697 
698 static inline ooo_segment_t *
700 {
701  if (f->ooos_newest == OOO_SEGMENT_INVALID_INDEX)
702  return 0;
703  return pool_elt_at_index (f->ooo_segments, f->ooos_newest);
704 }
705 
706 static inline void
708 {
709  f->ooos_newest = OOO_SEGMENT_INVALID_INDEX;
710 }
711 
712 static inline u32
714 {
715  u32 tail;
716  /* load-relaxed: producer owned index */
717  tail = f->tail;
718 
719  return f_distance_to (f, s->start, tail);
720 }
721 
722 static inline u32
724 {
725  return s->length;
726 }
727 
728 /**
729  * Check if fifo has io event
730  *
731  * @param f fifo
732  * @return 1 if fifo has event, 0 otherwise
733  */
734 static inline int
736 {
737  return f->has_event;
738 }
739 
740 /**
741  * Set fifo event flag.
742  *
743  * Forces release semantics.
744  *
745  * @param f fifo
746  * @return 1 if flag was not set, 0 otherwise
747  */
750 {
751  return !clib_atomic_swap_rel_n (&f->has_event, 1);
752 }
753 
754 /**
755  * Unset fifo event flag.
756  *
757  * Forces acquire semantics
758  *
759  * @param f fifo
760  */
761 always_inline void
763 {
764  clib_atomic_swap_acq_n (&f->has_event, 0);
765 }
766 
767 /**
768  * Set specific want notification flag
769  *
770  * For list of flags see @ref svm_fifo_deq_ntf_t
771  *
772  * @param f fifo
773  * @param ntf_type type of notification requested
774  */
775 static inline void
777 {
778  f->want_deq_ntf |= ntf_type;
779 }
780 
781 /**
782  * Clear specific want notification flag
783  *
784  * For list of flags see @ref svm_fifo_ntf_t
785  *
786  * @param f fifo
787  * @param ntf_type type of notification to be cleared
788  */
789 static inline void
791 {
792  f->want_deq_ntf &= ~ntf_type;
793 }
794 
795 /**
796  * Clear the want notification flag and set has notification
797  *
798  * Should be used after enqueuing an event. This clears the
799  * SVM_FIFO_WANT_NOTIF flag but it does not clear
800  * SVM_FIFO_WANT_NOTIF_IF_FULL. If the latter was set, has_ntf is
801  * set to avoid enqueueing events for for all dequeue operations until
802  * it is manually cleared.
803  *
804  * @param f fifo
805  */
806 static inline void
808 {
809  /* Set the flag if want_notif_if_full was the only ntf requested */
810  f->has_deq_ntf = f->want_deq_ntf == SVM_FIFO_WANT_DEQ_NOTIF_IF_FULL;
812 }
813 
814 /**
815  * Clear has notification flag
816  *
817  * The fifo generates only one event per SVM_FIFO_WANT_NOTIF_IF_FULL
818  * request and sets has_ntf. To received new events the flag must be
819  * cleared using this function.
820  *
821  * @param f fifo
822  */
823 static inline void
825 {
826  f->has_deq_ntf = 0;
827 }
828 
829 /**
830  * Check if fifo needs dequeue notification
831  *
832  * Determines based on notification request flags and state of the fifo if
833  * an event should be generated.
834  *
835  * @param f fifo
836  * @param n_last_deq number of bytes last dequeued
837  * @return 1 if event should be generated, 0 otherwise
838  */
839 static inline u8
841 {
842  u8 want_ntf = f->want_deq_ntf;
843 
844  if (PREDICT_TRUE (want_ntf == SVM_FIFO_NO_DEQ_NOTIF))
845  return 0;
846  else if (want_ntf & SVM_FIFO_WANT_DEQ_NOTIF)
847  return 1;
848  if (want_ntf & SVM_FIFO_WANT_DEQ_NOTIF_IF_FULL)
849  {
850  u32 max_deq = svm_fifo_max_dequeue_cons (f);
851  u32 nitems = f->nitems;
852  if (!f->has_deq_ntf && max_deq < nitems
853  && max_deq + n_last_deq >= nitems)
854  return 1;
855  }
856  if (want_ntf & SVM_FIFO_WANT_DEQ_NOTIF_IF_EMPTY)
857  {
858  if (!f->has_deq_ntf && svm_fifo_is_empty (f))
859  return 1;
860  }
861  return 0;
862 }
863 
864 #endif /* __included_ssvm_fifo_h__ */
865 
866 /*
867  * fd.io coding-style-patch-verification: ON
868  *
869  * Local Variables:
870  * eval: (c-set-style "gnu")
871  * End:
872  */
void svm_fifo_add_subscriber(svm_fifo_t *f, u8 sub)
Add io events subscriber to list.
Definition: svm_fifo.c:1175
u32 length
length of chunk in bytes
Definition: svm_fifo.h:61
static void f_load_head_tail_all_acq(svm_fifo_t *f, u32 *head, u32 *tail)
Load head and tail independent of producer/consumer role.
Definition: svm_fifo.h:185
static vlib_cli_command_t trace
(constructor) VLIB_CLI_COMMAND (trace)
Definition: vlib_api_cli.c:898
#define CLIB_CACHE_LINE_ALIGN_MARK(mark)
Definition: cache.h:60
struct svm_fifo_chunk_ svm_fifo_chunk_t
int svm_fifo_enqueue(svm_fifo_t *f, u32 len, const u8 *src)
Enqueue data to fifo.
Definition: svm_fifo.c:888
static u32 svm_fifo_max_enqueue_prod(svm_fifo_t *f)
Maximum number of bytes that can be enqueued into fifo.
Definition: svm_fifo.h:619
a
Definition: bitmap.h:538
void svm_fifo_clone(svm_fifo_t *df, svm_fifo_t *sf)
Clone fifo.
Definition: svm_fifo.c:1130
void svm_fifo_try_shrink(svm_fifo_t *f, u32 head, u32 tail)
Try to shrink fifo size.
Definition: svm_fifo.c:734
static int svm_fifo_is_full(svm_fifo_t *f)
Definition: svm_fifo.h:554
Notify on dequeue.
Definition: svm_fifo.h:46
u8 * svm_fifo_replay(u8 *s, svm_fifo_t *f, u8 no_read, u8 verbose)
Definition: svm_fifo.c:1292
static u8 svm_fifo_has_ooo_data(svm_fifo_t *f)
Check if fifo has out-of-order data.
Definition: svm_fifo.h:693
format_function_t format_svm_fifo
Definition: svm_fifo.h:490
void svm_fifo_free_ooo_data(svm_fifo_t *f)
Cleanup fifo ooo data.
Definition: svm_fifo.c:132
#define PREDICT_TRUE(x)
Definition: clib.h:112
svm_fifo_flag_
Definition: svm_fifo.h:66
static u32 f_free_count(svm_fifo_t *f, u32 head, u32 tail)
Fifo free bytes, i.e., number of free bytes.
Definition: svm_fifo.h:232
Fixed length block allocator.
static int svm_fifo_is_empty_prod(svm_fifo_t *f)
Check if fifo is empty optimized for producer.
Definition: svm_fifo.h:578
u32 prev
Previous linked-list element pool index.
Definition: svm_fifo.h:32
static void f_load_head_tail_cons(svm_fifo_t *f, u32 *head, u32 *tail)
Load head and tail optimized for consumer.
Definition: svm_fifo.h:158
vl_api_address_t src
Definition: gre.api:60
static int svm_fifo_is_empty_cons(svm_fifo_t *f)
Check if fifo is empty optimized for consumer.
Definition: svm_fifo.h:566
static void svm_fifo_reset_has_deq_ntf(svm_fifo_t *f)
Clear has notification flag.
Definition: svm_fifo.h:824
static u32 svm_fifo_max_enqueue(svm_fifo_t *f)
Definition: svm_fifo.h:635
int svm_fifo_reduce_size(svm_fifo_t *f, u32 len, u8 try_shrink)
Request to reduce fifo size by amount of bytes.
Definition: svm_fifo.c:807
void svm_fifo_add_chunk(svm_fifo_t *f, svm_fifo_chunk_t *c)
Grow fifo size by adding chunk to chunk list.
Definition: svm_fifo.c:579
static u8 * svm_fifo_tail(svm_fifo_t *f)
Definition: svm_fifo.h:674
unsigned char u8
Definition: types.h:56
struct _svm_fifo svm_fifo_t
u8 *() format_function_t(u8 *s, va_list *args)
Definition: format.h:48
static int svm_fifo_is_empty(svm_fifo_t *f)
Check if fifo is empty.
Definition: svm_fifo.h:591
int svm_fifo_segments(svm_fifo_t *f, svm_fifo_seg_t *fs)
Definition: svm_fifo.c:1077
static u32 svm_fifo_max_dequeue(svm_fifo_t *f)
Fifo max bytes to dequeue.
Definition: svm_fifo.h:528
static u32 svm_fifo_max_dequeue_cons(svm_fifo_t *f)
Fifo max bytes to dequeue optimized for consumer.
Definition: svm_fifo.h:499
static u32 svm_fifo_max_write_chunk(svm_fifo_t *f)
Max contiguous chunk of data that can be written.
Definition: svm_fifo.h:659
static u32 ooo_segment_length(svm_fifo_t *f, ooo_segment_t *s)
Definition: svm_fifo.h:723
u8 * svm_fifo_dump_trace(u8 *s, svm_fifo_t *f)
Definition: svm_fifo.c:1268
unsigned int u32
Definition: types.h:88
struct svm_fifo_seg_ svm_fifo_seg_t
svm_fifo_deq_ntf_
Definition: svm_fifo.h:43
static u8 * svm_fifo_head(svm_fifo_t *f)
Definition: svm_fifo.h:667
static u32 svm_fifo_max_read_chunk(svm_fifo_t *f)
Max contiguous chunk of data that can be read.
Definition: svm_fifo.h:648
static int svm_fifo_is_full_prod(svm_fifo_t *f)
Check if fifo is full optimized for producer.
Definition: svm_fifo.h:542
static void svm_fifo_newest_ooo_segment_reset(svm_fifo_t *f)
Definition: svm_fifo.h:707
int svm_fifo_peek(svm_fifo_t *f, u32 offset, u32 len, u8 *dst)
Peek data from fifo.
Definition: svm_fifo.c:1007
u8 svm_fifo_is_sane(svm_fifo_t *f)
Check if fifo is sane.
Definition: svm_fifo.c:1198
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
Definition: pool.h:519
void svm_fifo_dequeue_drop_all(svm_fifo_t *f)
Dequeue and drop all bytes from fifo.
Definition: svm_fifo.c:1061
u32 svm_fifo_n_ooo_segments(svm_fifo_t *f)
Number of out-of-order segments for fifo.
Definition: svm_fifo.c:1141
struct svm_fifo_chunk_ * next
pointer to next chunk in linked-lists
Definition: svm_fifo.h:62
u64 size
Definition: vhost_user.h:140
#define PREDICT_FALSE(x)
Definition: clib.h:111
#define always_inline
Definition: ipsec.h:28
u8 svm_fifo_set_single_thread_owned(svm_fifo_t *f)
Declare this fifo is used by only a single thread.
Definition: svm_fifo.c:1237
static void svm_fifo_unset_event(svm_fifo_t *f)
Unset fifo event flag.
Definition: svm_fifo.h:762
void svm_fifo_init_chunks(svm_fifo_t *f)
Initialize fifo chunks and rbtree.
Definition: svm_fifo.c:408
signed char i8
Definition: types.h:45
svm_fifo_t * svm_fifo_create(u32 size)
Create fifo of requested size.
Definition: svm_fifo.c:436
static u32 svm_fifo_max_dequeue_prod(svm_fifo_t *f)
Fifo max bytes to dequeue optimized for producer.
Definition: svm_fifo.h:513
vl_api_address_t dst
Definition: gre.api:61
static ooo_segment_t * svm_fifo_newest_ooo_segment(svm_fifo_t *f)
Definition: svm_fifo.h:699
u8 len
Definition: ip_types.api:91
static u8 svm_fifo_set_event(svm_fifo_t *f)
Set fifo event flag.
Definition: svm_fifo.h:749
svm_fifo_chunk_t * svm_fifo_chunk_alloc(u32 size)
Allocate a fifo chunk on heap.
Definition: svm_fifo.c:471
#define SVM_FIFO_MAX_EVT_SUBSCRIBERS
Definition: svm_fifo.h:41
static u8 svm_fifo_needs_deq_ntf(svm_fifo_t *f, u32 n_last_deq)
Check if fifo needs dequeue notification.
Definition: svm_fifo.h:840
u32 flags
Definition: vhost_user.h:141
static u32 f_cursize(svm_fifo_t *f, u32 head, u32 tail)
Fifo current size, i.e., number of bytes enqueued.
Definition: svm_fifo.h:221
int svm_fifo_dequeue(svm_fifo_t *f, u32 len, u8 *dst)
Dequeue data from fifo.
Definition: svm_fifo.c:981
void svm_fifo_overwrite_head(svm_fifo_t *f, u8 *src, u32 len)
Overwrite fifo head with new data.
Definition: svm_fifo.c:866
static void f_load_head_tail_prod(svm_fifo_t *f, u32 *head, u32 *tail)
Load head and tail optimized for producer.
Definition: svm_fifo.h:171
u32 start_byte
chunk start byte
Definition: svm_fifo.h:60
svm_fifo_chunk_t * svm_fifo_collect_chunks(svm_fifo_t *f)
Removes chunks that are after fifo end byte.
Definition: svm_fifo.c:715
#define OOO_SEGMENT_INVALID_INDEX
Definition: svm_fifo.h:38
void svm_fifo_free_chunk_lookup(svm_fifo_t *f)
Cleanup fifo chunk lookup rb tree.
Definition: svm_fifo.c:847
#define clib_atomic_swap_acq_n(a, b)
Definition: atomics.h:51
int svm_fifo_dequeue_drop(svm_fifo_t *f, u32 len)
Dequeue and drop bytes from fifo.
Definition: svm_fifo.c:1029
Notify on transition to empty.
Definition: svm_fifo.h:48
u8 data[0]
start of chunk data
Definition: svm_fifo.h:63
void svm_fifo_free(svm_fifo_t *f)
Free fifo and associated state.
Definition: svm_fifo.c:853
static void svm_fifo_clear_deq_ntf(svm_fifo_t *f)
Clear the want notification flag and set has notification.
Definition: svm_fifo.h:807
static void svm_fifo_add_want_deq_ntf(svm_fifo_t *f, u8 ntf_type)
Set specific want notification flag.
Definition: svm_fifo.h:776
static u8 svm_fifo_is_wrapped(svm_fifo_t *f)
Check if fifo is wrapped.
Definition: svm_fifo.h:603
Out-of-order segment.
Definition: svm_fifo.h:29
Notify on transition from full.
Definition: svm_fifo.h:47
static u32 f_distance_to(svm_fifo_t *f, u32 a, u32 b)
Distance to a from b, i.e., a - b in the fifo.
Definition: svm_fifo.h:199
u32 length
Length of segment.
Definition: svm_fifo.h:34
void svm_fifo_enqueue_nocopy(svm_fifo_t *f, u32 len)
Advance tail pointer.
Definition: svm_fifo.c:964
void svm_fifo_init(svm_fifo_t *f, u32 size)
Initialize fifo.
Definition: svm_fifo.c:392
u32 next
Next linked-list element pool index.
Definition: svm_fifo.h:31
template key/value backing page structure
Definition: bihash_doc.h:44
#define clib_atomic_swap_rel_n(a, b)
Definition: atomics.h:52
enum svm_fifo_deq_ntf_ svm_fifo_deq_ntf_t
No notification requested.
Definition: svm_fifo.h:45
enum svm_fifo_flag_ svm_fifo_flag_t
static void svm_fifo_del_want_deq_ntf(svm_fifo_t *f, u8 ntf_type)
Clear specific want notification flag.
Definition: svm_fifo.h:790
static u32 f_distance_from(svm_fifo_t *f, u32 a, u32 b)
Distance from a to b, i.e., b - a in the fifo.
Definition: svm_fifo.h:210
static u32 ooo_segment_offset_prod(svm_fifo_t *f, ooo_segment_t *s)
Definition: svm_fifo.h:713
static u8 svm_fifo_n_subscribers(svm_fifo_t *f)
Definition: svm_fifo.h:681
void svm_fifo_init_pointers(svm_fifo_t *f, u32 head, u32 tail)
Init fifo head and tail.
Definition: svm_fifo.c:1156
void svm_fifo_segments_free(svm_fifo_t *f, svm_fifo_seg_t *fs)
Definition: svm_fifo.c:1109
svm_fifo_err_t
Definition: svm_fifo.h:124
static int svm_fifo_has_event(svm_fifo_t *f)
Check if fifo has io event.
Definition: svm_fifo.h:735
#define clib_atomic_load_acq_n(a)
Definition: atomics.h:48
void svm_fifo_del_subscriber(svm_fifo_t *f, u8 subscriber)
Remove io events subscriber form list.
Definition: svm_fifo.c:1183
int svm_fifo_enqueue_with_offset(svm_fifo_t *f, u32 offset, u32 len, u8 *src)
Enqueue data to fifo with offset.
Definition: svm_fifo.c:931
u32 start
Start of segment, normalized.
Definition: svm_fifo.h:33
ooo_segment_t * svm_fifo_first_ooo_segment(svm_fifo_t *f)
First out-of-order segment for fifo.
Definition: svm_fifo.c:1147
CLIB vectors are ubiquitous dynamically resized arrays with by user defined "headers".