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:
11 * http://www.apache.org/licenses/LICENSE-2.0
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.
20 #include <svm/svm_fifo.h>
21 #include <vppinfra/cpu.h>
23 CLIB_MARCH_FN (svm_fifo_copy_to_chunk, void, svm_fifo_t * f,
24 svm_fifo_chunk_t * c, u32 tail_idx, const u8 * src, u32 len,
25 svm_fifo_chunk_t ** last)
29 ASSERT (tail_idx >= c->start_byte && tail_idx < c->start_byte + c->length);
31 tail_idx -= c->start_byte;
32 n_chunk = c->length - tail_idx;
36 clib_memcpy_fast (&c->data[tail_idx], src, n_chunk);
38 while ((to_copy -= n_chunk))
40 n_chunk = clib_min (c->length, to_copy);
41 clib_memcpy_fast (&c->data[0], src + (len - to_copy), n_chunk);
42 c = c->length <= to_copy ? c->next : c;
49 clib_memcpy_fast (&c->data[tail_idx], src, len);
53 CLIB_MARCH_FN (svm_fifo_copy_from_chunk, void, svm_fifo_t * f,
54 svm_fifo_chunk_t * c, u32 head_idx, u8 * dst, u32 len,
55 svm_fifo_chunk_t ** last)
59 ASSERT (head_idx >= c->start_byte && head_idx < c->start_byte + c->length);
61 head_idx -= c->start_byte;
62 n_chunk = c->length - head_idx;
66 clib_memcpy_fast (dst, &c->data[head_idx], n_chunk);
68 while ((to_copy -= n_chunk))
70 n_chunk = clib_min (c->length, to_copy);
71 clib_memcpy_fast (dst + (len - to_copy), &c->data[0], n_chunk);
72 c = c->length <= to_copy ? c->next : c;
79 clib_memcpy_fast (dst, &c->data[head_idx], len);
83 #ifndef CLIB_MARCH_VARIANT
86 svm_fifo_copy_to_chunk (svm_fifo_t * f, svm_fifo_chunk_t * c, u32 tail_idx,
87 const u8 * src, u32 len, svm_fifo_chunk_t ** last)
89 CLIB_MARCH_FN_SELECT (svm_fifo_copy_to_chunk) (f, c, tail_idx, src, len,
94 svm_fifo_copy_from_chunk (svm_fifo_t * f, svm_fifo_chunk_t * c, u32 head_idx,
95 u8 * dst, u32 len, svm_fifo_chunk_t ** last)
97 CLIB_MARCH_FN_SELECT (svm_fifo_copy_from_chunk) (f, c, head_idx, dst, len,
102 position_lt (svm_fifo_t * f, u32 a, u32 b, u32 tail)
104 return (f_distance_to (f, a, tail) < f_distance_to (f, b, tail));
108 position_leq (svm_fifo_t * f, u32 a, u32 b, u32 tail)
110 return (f_distance_to (f, a, tail) <= f_distance_to (f, b, tail));
114 position_gt (svm_fifo_t * f, u32 a, u32 b, u32 tail)
116 return (f_distance_to (f, a, tail) > f_distance_to (f, b, tail));
120 position_diff (svm_fifo_t * f, u32 a, u32 b, u32 tail)
122 return f_distance_to (f, a, tail) - f_distance_to (f, b, tail);
126 ooo_segment_end_pos (svm_fifo_t * f, ooo_segment_t * s)
128 return (s->start + s->length) % f->size;
132 svm_fifo_free_ooo_data (svm_fifo_t * f)
134 pool_free (f->ooo_segments);
137 static inline ooo_segment_t *
138 ooo_segment_prev (svm_fifo_t * f, ooo_segment_t * s)
140 if (s->prev == OOO_SEGMENT_INVALID_INDEX)
142 return pool_elt_at_index (f->ooo_segments, s->prev);
145 static inline ooo_segment_t *
146 ooo_segment_next (svm_fifo_t * f, ooo_segment_t * s)
148 if (s->next == OOO_SEGMENT_INVALID_INDEX)
150 return pool_elt_at_index (f->ooo_segments, s->next);
153 static inline ooo_segment_t *
154 ooo_segment_alloc (svm_fifo_t * f, u32 start, u32 length)
158 pool_get (f->ooo_segments, s);
162 s->prev = s->next = OOO_SEGMENT_INVALID_INDEX;
168 ooo_segment_free (svm_fifo_t * f, u32 index)
170 ooo_segment_t *cur, *prev = 0, *next = 0;
171 cur = pool_elt_at_index (f->ooo_segments, index);
173 if (cur->next != OOO_SEGMENT_INVALID_INDEX)
175 next = pool_elt_at_index (f->ooo_segments, cur->next);
176 next->prev = cur->prev;
179 if (cur->prev != OOO_SEGMENT_INVALID_INDEX)
181 prev = pool_elt_at_index (f->ooo_segments, cur->prev);
182 prev->next = cur->next;
186 f->ooos_list_head = cur->next;
189 pool_put (f->ooo_segments, cur);
193 * Add segment to fifo's out-of-order segment list. Takes care of merging
194 * adjacent segments and removing overlapping ones.
197 ooo_segment_add (svm_fifo_t * f, u32 offset, u32 head, u32 tail, u32 length)
199 ooo_segment_t *s, *new_s, *prev, *next, *it;
200 u32 new_index, s_end_pos, s_index;
201 u32 offset_pos, offset_end_pos;
203 ASSERT (offset + length <= f_distance_to (f, head, tail) || head == tail);
205 offset_pos = (tail + offset) % f->size;
206 offset_end_pos = (tail + offset + length) % f->size;
208 f->ooos_newest = OOO_SEGMENT_INVALID_INDEX;
210 if (f->ooos_list_head == OOO_SEGMENT_INVALID_INDEX)
212 s = ooo_segment_alloc (f, offset_pos, length);
213 f->ooos_list_head = s - f->ooo_segments;
214 f->ooos_newest = f->ooos_list_head;
218 /* Find first segment that starts after new segment */
219 s = pool_elt_at_index (f->ooo_segments, f->ooos_list_head);
220 while (s->next != OOO_SEGMENT_INVALID_INDEX
221 && position_lt (f, s->start, offset_pos, tail))
222 s = pool_elt_at_index (f->ooo_segments, s->next);
224 /* If we have a previous and we overlap it, use it as starting point */
225 prev = ooo_segment_prev (f, s);
227 && position_leq (f, offset_pos, ooo_segment_end_pos (f, prev), tail))
230 s_end_pos = ooo_segment_end_pos (f, s);
232 /* Since we have previous, offset start position cannot be smaller
233 * than prev->start. Check tail */
234 ASSERT (position_lt (f, s->start, offset_pos, tail));
238 s_index = s - f->ooo_segments;
239 s_end_pos = ooo_segment_end_pos (f, s);
241 /* No overlap, add before current segment */
242 if (position_lt (f, offset_end_pos, s->start, tail))
244 new_s = ooo_segment_alloc (f, offset_pos, length);
245 new_index = new_s - f->ooo_segments;
247 /* Pool might've moved, get segment again */
248 s = pool_elt_at_index (f->ooo_segments, s_index);
249 if (s->prev != OOO_SEGMENT_INVALID_INDEX)
251 new_s->prev = s->prev;
252 prev = pool_elt_at_index (f->ooo_segments, new_s->prev);
253 prev->next = new_index;
258 f->ooos_list_head = new_index;
261 new_s->next = s_index;
263 f->ooos_newest = new_index;
266 /* No overlap, add after current segment */
267 else if (position_gt (f, offset_pos, s_end_pos, tail))
269 new_s = ooo_segment_alloc (f, offset_pos, length);
270 new_index = new_s - f->ooo_segments;
272 /* Pool might've moved, get segment again */
273 s = pool_elt_at_index (f->ooo_segments, s_index);
275 /* Needs to be last */
276 ASSERT (s->next == OOO_SEGMENT_INVALID_INDEX);
278 new_s->prev = s_index;
280 f->ooos_newest = new_index;
290 if (position_lt (f, offset_pos, s->start, tail))
292 s->start = offset_pos;
293 s->length = position_diff (f, s_end_pos, s->start, tail);
294 f->ooos_newest = s - f->ooo_segments;
299 /* Overlapping tail */
300 if (position_gt (f, offset_end_pos, s_end_pos, tail))
302 s->length = position_diff (f, offset_end_pos, s->start, tail);
304 /* Remove the completely overlapped segments in the tail */
305 it = ooo_segment_next (f, s);
306 while (it && position_leq (f, ooo_segment_end_pos (f, it),
307 offset_end_pos, tail))
309 next = ooo_segment_next (f, it);
310 ooo_segment_free (f, it - f->ooo_segments);
314 /* If partial overlap with last, merge */
315 if (it && position_leq (f, it->start, offset_end_pos, tail))
317 s->length = position_diff (f, ooo_segment_end_pos (f, it),
319 ooo_segment_free (f, it - f->ooo_segments);
321 f->ooos_newest = s - f->ooo_segments;
326 * Removes segments that can now be enqueued because the fifo's tail has
327 * advanced. Returns the number of bytes added to tail.
330 ooo_segment_try_collect (svm_fifo_t * f, u32 n_bytes_enqueued, u32 * tail)
332 u32 s_index, bytes = 0;
336 s = pool_elt_at_index (f->ooo_segments, f->ooos_list_head);
337 diff = f_distance_from (f, s->start, *tail);
339 ASSERT (diff != n_bytes_enqueued);
341 if (diff > n_bytes_enqueued)
344 /* If last tail update overlaps one/multiple ooo segments, remove them */
345 while (0 <= diff && diff < n_bytes_enqueued)
347 s_index = s - f->ooo_segments;
349 /* Segment end is beyond the tail. Advance tail and remove segment */
350 if (s->length > diff)
352 bytes = s->length - diff;
353 *tail = (*tail + bytes) % f->size;
354 ooo_segment_free (f, s_index);
358 /* If we have next go on */
359 if (s->next != OOO_SEGMENT_INVALID_INDEX)
361 s = pool_elt_at_index (f->ooo_segments, s->next);
362 diff = f_distance_from (f, s->start, *tail);
363 ooo_segment_free (f, s_index);
368 ooo_segment_free (f, s_index);
373 ASSERT (bytes <= f->nitems);
377 static ooo_segment_t *
378 ooo_segment_last (svm_fifo_t * f)
382 if (f->ooos_list_head == OOO_SEGMENT_INVALID_INDEX)
385 s = svm_fifo_first_ooo_segment (f);
386 while (s->next != OOO_SEGMENT_INVALID_INDEX)
387 s = pool_elt_at_index (f->ooo_segments, s->next);
392 svm_fifo_init (svm_fifo_t * f, u32 size)
396 * usable size of the fifo set to rounded_data_size - 1
397 * to differentiate between free fifo and empty fifo.
399 f->nitems = f->size - 1;
400 f->ooos_list_head = OOO_SEGMENT_INVALID_INDEX;
401 f->segment_index = SVM_FIFO_INVALID_INDEX;
403 f->head = f->tail = f->flags = 0;
404 f->head_chunk = f->tail_chunk = f->ooo_enq = f->ooo_deq = f->start_chunk;
408 svm_fifo_init_chunks (svm_fifo_t * f)
410 svm_fifo_chunk_t *c, *prev;
412 if (f->start_chunk->next == f->start_chunk)
415 f->flags |= SVM_FIFO_F_MULTI_CHUNK;
416 rb_tree_init (&f->ooo_enq_lookup);
417 rb_tree_init (&f->ooo_deq_lookup);
419 f->start_chunk->start_byte = 0;
420 prev = f->start_chunk;
423 while (c != f->start_chunk)
425 c->start_byte = prev->start_byte + prev->length;
432 * Creates a fifo in the current heap. Fails vs blow up the process
435 svm_fifo_create (u32 data_size_in_bytes)
437 u32 rounded_data_size;
441 f = clib_mem_alloc_aligned_or_null (sizeof (*f), CLIB_CACHE_LINE_BYTES);
445 clib_memset (f, 0, sizeof (*f));
447 /* always round fifo data size to the next highest power-of-two */
448 rounded_data_size = (1 << (max_log2 (data_size_in_bytes)));
449 c = clib_mem_alloc_aligned_or_null (sizeof (*c) + rounded_data_size,
450 CLIB_CACHE_LINE_BYTES);
459 c->length = data_size_in_bytes;
460 c->rb_index = RBTREE_TNIL_INDEX;
461 f->start_chunk = f->end_chunk = c;
463 svm_fifo_init (f, data_size_in_bytes);
468 * Creates a fifo chunk in the current heap
471 svm_fifo_chunk_alloc (u32 size)
476 /* round chunk size to the next highest power-of-two */
477 rounded_size = (1 << (max_log2 (size)));
478 c = clib_mem_alloc_aligned_or_null (sizeof (*c) + rounded_size,
479 CLIB_CACHE_LINE_BYTES);
483 clib_memset (c, 0, sizeof (*c));
484 c->length = rounded_size;
489 svm_fifo_chunk_includes_pos (svm_fifo_chunk_t * c, u32 pos)
491 return (pos >= c->start_byte && pos < c->start_byte + c->length);
495 svm_fifo_find_node_rbtree (rb_tree_t * rt, u32 pos)
497 rb_node_t *cur, *prev;
499 cur = rb_node (rt, rt->root);
500 if (PREDICT_FALSE (rb_node_is_tnil (rt, cur)))
503 while (pos != cur->key)
508 cur = rb_node_left (rt, cur);
509 if (rb_node_is_tnil (rt, cur))
511 cur = rb_tree_predecessor (rt, prev);
517 cur = rb_node_right (rt, cur);
518 if (rb_node_is_tnil (rt, cur))
526 if (rb_node_is_tnil (rt, cur))
532 static svm_fifo_chunk_t *
533 svm_fifo_find_chunk_rbtree (rb_tree_t * rt, u32 pos)
538 n = svm_fifo_find_node_rbtree (rt, pos);
541 c = uword_to_pointer (n->opaque, svm_fifo_chunk_t *);
542 if (svm_fifo_chunk_includes_pos (c, pos))
549 * Find chunk for given byte position
552 * @param pos normalized position in fifo
554 * @return chunk that includes given position or 0
556 static svm_fifo_chunk_t *
557 svm_fifo_find_chunk (svm_fifo_t * f, u32 pos)
564 if (svm_fifo_chunk_includes_pos (c, pos))
568 while (c != f->start_chunk);
574 svm_fifo_update_ooo_enq (svm_fifo_t * f, u32 ref_pos, u32 start_pos,
577 rb_tree_t *rt = &f->ooo_enq_lookup;
581 if (svm_fifo_chunk_includes_pos (f->ooo_enq, start_pos)
582 && svm_fifo_chunk_includes_pos (f->ooo_enq, end_pos)
583 && ref_pos < start_pos)
586 if (rt->root == RBTREE_TNIL_INDEX)
589 c->rb_index = rb_tree_add2 (rt, c->start_byte, pointer_to_uword (c));
593 cur = svm_fifo_find_node_rbtree (rt, start_pos);
594 c = uword_to_pointer (cur->opaque, svm_fifo_chunk_t *);
595 if (ref_pos > start_pos && c->start_byte > start_pos)
598 ASSERT (c->rb_index != RBTREE_TNIL_INDEX);
602 if (svm_fifo_chunk_includes_pos (c, start_pos))
605 if (svm_fifo_chunk_includes_pos (c, end_pos) && ref_pos < end_pos)
611 if (c->rb_index != RBTREE_TNIL_INDEX)
614 c->rb_index = rb_tree_add2 (rt, c->start_byte, pointer_to_uword (c));
616 if (svm_fifo_chunk_includes_pos (c, start_pos))
620 while (!svm_fifo_chunk_includes_pos (c, end_pos));
624 svm_fifo_update_ooo_deq (svm_fifo_t * f, u32 ref_pos, u32 start_pos,
627 rb_tree_t *rt = &f->ooo_deq_lookup;
631 if (svm_fifo_chunk_includes_pos (f->ooo_deq, start_pos)
632 && svm_fifo_chunk_includes_pos (f->ooo_deq, end_pos)
633 && ref_pos < start_pos)
636 if (rt->root == RBTREE_TNIL_INDEX)
639 c->rb_index = rb_tree_add2 (rt, c->start_byte, pointer_to_uword (c));
643 cur = svm_fifo_find_node_rbtree (rt, start_pos);
644 c = uword_to_pointer (cur->opaque, svm_fifo_chunk_t *);
645 if (ref_pos > start_pos && c->start_byte > start_pos)
648 ASSERT (c->rb_index != RBTREE_TNIL_INDEX);
652 if (svm_fifo_chunk_includes_pos (c, start_pos))
655 if (svm_fifo_chunk_includes_pos (c, end_pos) && ref_pos < end_pos)
661 if (c->rb_index != RBTREE_TNIL_INDEX)
664 c->rb_index = rb_tree_add2 (rt, c->start_byte, pointer_to_uword (c));
666 if (svm_fifo_chunk_includes_pos (c, start_pos))
670 while (!svm_fifo_chunk_includes_pos (c, end_pos));
674 svm_fifo_ooo_deq_track (svm_fifo_t * f, u32 start_pos, u32 end_pos)
676 rb_tree_t *rt = &f->ooo_deq_lookup;
679 if (svm_fifo_chunk_includes_pos (f->ooo_deq, end_pos)
680 && start_pos < end_pos)
683 c = f->ooo_deq->next;
686 ASSERT (c->rb_index == RBTREE_TNIL_INDEX);
687 rb_tree_add2 (rt, c->start_byte, pointer_to_uword (c));
691 while (!svm_fifo_chunk_includes_pos (c, end_pos));
694 static svm_fifo_chunk_t *
695 svm_fifo_lookup_clear_chunks (svm_fifo_t * f, rb_tree_t * rt,
696 svm_fifo_chunk_t * start, u32 start_pos,
702 /* Nothing to do if still in the same chunk and not wrapped */
703 if (svm_fifo_chunk_includes_pos (start, end_pos) && start_pos < end_pos)
709 if (c->rb_index == RBTREE_TNIL_INDEX)
715 n = rb_node (rt, c->rb_index);
716 rb_tree_del_node (rt, n);
717 c->rb_index = RBTREE_TNIL_INDEX;
720 while (!svm_fifo_chunk_includes_pos (c, end_pos));
726 svm_fifo_grow (svm_fifo_t * f, svm_fifo_chunk_t * c)
728 svm_fifo_chunk_t *prev;
734 f->end_chunk->next = c;
737 add_bytes += c->length;
742 prev->next = f->start_chunk;
743 f->size += add_bytes;
744 f->nitems = f->size - 1;
749 svm_fifo_try_grow (svm_fifo_t * f, u32 new_head)
751 if (new_head > f->tail)
754 svm_fifo_grow (f, f->new_chunks);
755 f->flags &= ~SVM_FIFO_F_GROW;
759 svm_fifo_add_chunk (svm_fifo_t * f, svm_fifo_chunk_t * c)
761 svm_fifo_chunk_t *cur, *prev;
763 /* Initialize rbtree if needed and add default chunk to it. Expectation is
764 * that this is called with the heap where the rbtree's pool is pushed. */
765 if (!(f->flags & SVM_FIFO_F_MULTI_CHUNK))
767 ASSERT (f->start_chunk->next == f->start_chunk);
768 rb_tree_init (&f->ooo_enq_lookup);
769 rb_tree_init (&f->ooo_deq_lookup);
770 f->flags |= SVM_FIFO_F_MULTI_CHUNK;
773 /* If fifo is not wrapped, update the size now */
774 if (!svm_fifo_is_wrapped (f))
776 /* Initialize chunks and add to lookup rbtree */
780 prev = f->new_chunks;
790 cur->start_byte = prev->start_byte + prev->length;
791 cur->rb_index = RBTREE_TNIL_INDEX;
796 ASSERT (!f->new_chunks);
797 svm_fifo_grow (f, c);
802 if (f->flags & SVM_FIFO_F_SINGLE_THREAD_OWNED)
804 ASSERT (f->master_thread_index == os_get_thread_index ());
806 if (!f->new_chunks && f->head_chunk != f->tail_chunk)
808 u32 head = 0, tail = 0;
809 f_load_head_tail_cons (f, &head, &tail);
811 svm_fifo_chunk_t *tmp = f->tail_chunk->next;
813 prev = f->tail_chunk;
816 while (cur != f->start_chunk)
818 /* remove any existing rb_tree entry */
819 if (cur->rb_index != RBTREE_TNIL_INDEX)
821 rb_tree_del (&f->ooo_enq_lookup, cur->start_byte);
822 rb_tree_del (&f->ooo_deq_lookup, cur->start_byte);
824 cur->rb_index = RBTREE_TNIL_INDEX;
828 /* insert new chunk after the tail_chunk */
829 f->tail_chunk->next = c;
832 add_bytes += c->length;
833 c->start_byte = prev->start_byte + prev->length;
834 cur->rb_index = RBTREE_TNIL_INDEX;
841 /* shift existing chunks along */
843 while (cur != f->start_chunk)
845 cur->start_byte = prev->start_byte + prev->length;
850 f->size += add_bytes;
851 f->nitems = f->size - 1;
855 clib_atomic_store_rel_n (&f->head, head);
856 ASSERT (svm_fifo_is_sane (f));
862 /* Wrapped, and optimization of single-thread-owned fifo cannot be applied */
863 /* Initialize chunks and add to lookup rbtree */
867 prev = f->new_chunks;
877 cur->start_byte = prev->start_byte + prev->length;
878 cur->rb_index = RBTREE_TNIL_INDEX;
883 /* Postpone size update */
887 f->flags |= SVM_FIFO_F_GROW;
892 * Removes chunks that are after fifo end byte
895 svm_fifo_collect_chunks (svm_fifo_t * f)
897 svm_fifo_chunk_t *list, *cur;
899 f->flags &= ~SVM_FIFO_F_COLLECT_CHUNKS;
901 list = f->new_chunks;
906 if (cur->rb_index != RBTREE_TNIL_INDEX)
908 rb_tree_del (&f->ooo_enq_lookup, cur->start_byte);
909 rb_tree_del (&f->ooo_deq_lookup, cur->start_byte);
918 svm_fifo_try_shrink (svm_fifo_t * f, u32 head, u32 tail)
920 u32 len_to_shrink = 0, tail_pos, len, last_pos;
921 svm_fifo_chunk_t *cur, *prev, *next, *start;
924 if (f->ooos_list_head != OOO_SEGMENT_INVALID_INDEX)
926 ooo_segment_t *last = ooo_segment_last (f);
927 tail_pos = ooo_segment_end_pos (f, last);
930 if (f->size_decrement)
932 /* Figure out available free space considering that there may be
934 len = clib_min (f->size_decrement, f_free_count (f, head, tail_pos));
936 f->size_decrement -= len;
939 /* Remove tail chunks if the following hold:
941 * - last used byte less than start of last chunk
943 if (tail_pos >= head && tail_pos < f->end_chunk->start_byte)
945 /* Lookup the last position not to be removed. Since size still needs
946 * to be nitems + 1, nitems must fall within the usable space. Also,
947 * first segment is not removable, so tail_pos can be 0. */
948 last_pos = tail_pos > 0 ? tail_pos - 1 : tail_pos;
949 prev = svm_fifo_find_chunk (f, clib_max (f->nitems, last_pos));
951 /* If tail_pos is first position in next, skip the chunk, otherwise,
952 * we must update the tail and, if fifo size is 0, even the head.
953 * We should not invalidate the tail for the caller and must not change
954 * consumer owned variables from code that's typically called by the
956 if (next->start_byte == tail_pos)
961 while (next != f->start_chunk)
965 len_to_shrink += cur->length;
969 f->size -= len_to_shrink;
971 prev->next = f->start_chunk;
973 cur->next = f->new_chunks;
974 f->new_chunks = start;
978 if (!f->size_decrement && f->size == f->nitems + 1)
980 f->flags &= ~SVM_FIFO_F_SHRINK;
981 f->flags |= SVM_FIFO_F_COLLECT_CHUNKS;
982 if (f->start_chunk == f->start_chunk->next)
983 f->flags &= ~SVM_FIFO_F_MULTI_CHUNK;
988 * Request to reduce fifo size by amount of bytes
991 svm_fifo_reduce_size (svm_fifo_t * f, u32 len, u8 try_shrink)
993 svm_fifo_chunk_t *cur;
996 /* Abort if trying to reduce by more than fifo size or if
997 * fifo is undergoing resizing already */
998 if (len >= f->size || f->size > f->nitems + 1
999 || (f->flags & SVM_FIFO_F_SHRINK) || (f->flags & SVM_FIFO_F_GROW))
1002 /* last chunk that will not be removed */
1003 cur = svm_fifo_find_chunk (f, f->nitems - len);
1005 /* sum length of chunks that will be removed */
1007 while (cur != f->start_chunk)
1009 actual_len += cur->length;
1013 ASSERT (actual_len <= len);
1017 f->size_decrement = actual_len;
1018 f->flags |= SVM_FIFO_F_SHRINK;
1023 f_load_head_tail_prod (f, &head, &tail);
1024 svm_fifo_try_shrink (f, head, tail);
1031 svm_fifo_free_chunk_lookup (svm_fifo_t * f)
1033 rb_tree_free_nodes (&f->ooo_enq_lookup);
1034 rb_tree_free_nodes (&f->ooo_deq_lookup);
1038 svm_fifo_free (svm_fifo_t * f)
1040 ASSERT (f->refcnt > 0);
1042 if (--f->refcnt == 0)
1044 /* ooo data is not allocated on segment heap */
1045 svm_fifo_free_chunk_lookup (f);
1051 svm_fifo_overwrite_head (svm_fifo_t * f, u8 * src, u32 len)
1054 u32 head, tail, head_idx;
1055 svm_fifo_chunk_t *c;
1057 ASSERT (len <= f->nitems);
1059 f_load_head_tail_cons (f, &head, &tail);
1061 head_idx = head - c->start_byte;
1062 n_chunk = c->length - head_idx;
1064 clib_memcpy_fast (&c->data[head_idx], src, len);
1067 clib_memcpy_fast (&c->data[head_idx], src, n_chunk);
1068 clib_memcpy_fast (&c->next->data[0], src + n_chunk, len - n_chunk);
1073 svm_fifo_enqueue (svm_fifo_t * f, u32 len, const u8 * src)
1075 u32 tail, head, free_count;
1077 f_load_head_tail_prod (f, &head, &tail);
1079 /* free space in fifo can only increase during enqueue: SPSC */
1080 free_count = f_free_count (f, head, tail);
1082 f->ooos_newest = OOO_SEGMENT_INVALID_INDEX;
1084 if (PREDICT_FALSE (free_count == 0))
1085 return SVM_FIFO_EFULL;
1087 /* number of bytes we're going to copy */
1088 len = clib_min (free_count, len);
1089 svm_fifo_copy_to_chunk (f, f->tail_chunk, tail, src, len, &f->tail_chunk);
1090 tail = (tail + len) % f->size;
1092 svm_fifo_trace_add (f, head, len, 2);
1094 /* collect out-of-order segments */
1095 if (PREDICT_FALSE (f->ooos_list_head != OOO_SEGMENT_INVALID_INDEX))
1097 len += ooo_segment_try_collect (f, len, &tail);
1098 if (f->flags & SVM_FIFO_F_MULTI_CHUNK)
1099 f->tail_chunk = svm_fifo_lookup_clear_chunks (f, &f->ooo_enq_lookup,
1100 f->tail_chunk, f->tail,
1104 /* store-rel: producer owned index (paired with load-acq in consumer) */
1105 clib_atomic_store_rel_n (&f->tail, tail);
1111 * Enqueue a future segment.
1113 * Two choices: either copies the entire segment, or copies nothing
1114 * Returns 0 of the entire segment was copied
1115 * Returns -1 if none of the segment was copied due to lack of space
1118 svm_fifo_enqueue_with_offset (svm_fifo_t * f, u32 offset, u32 len, u8 * src)
1120 u32 tail, head, free_count, tail_idx;
1122 f_load_head_tail_prod (f, &head, &tail);
1124 if (PREDICT_FALSE (f->flags & SVM_FIFO_F_SHRINK))
1125 svm_fifo_try_shrink (f, head, tail);
1127 /* free space in fifo can only increase during enqueue: SPSC */
1128 free_count = f_free_count (f, head, tail);
1130 /* will this request fit? */
1131 if ((len + offset) > free_count)
1132 return SVM_FIFO_EFULL;
1134 f->ooos_newest = OOO_SEGMENT_INVALID_INDEX;
1135 svm_fifo_trace_add (f, offset, len, 1);
1136 ooo_segment_add (f, offset, head, tail, len);
1137 tail_idx = (tail + offset) % f->size;
1139 if (f->flags & SVM_FIFO_F_MULTI_CHUNK)
1140 svm_fifo_update_ooo_enq (f, f->tail, tail_idx,
1141 (tail_idx + len) % f->size);
1143 svm_fifo_copy_to_chunk (f, f->ooo_enq, tail_idx, src, len, &f->ooo_enq);
1152 svm_fifo_enqueue_nocopy (svm_fifo_t * f, u32 len)
1156 ASSERT (len <= svm_fifo_max_enqueue_prod (f));
1157 /* load-relaxed: producer owned index */
1159 tail = (tail + len) % f->size;
1161 if (f->flags & SVM_FIFO_F_MULTI_CHUNK)
1162 f->tail_chunk = svm_fifo_lookup_clear_chunks (f, &f->ooo_enq_lookup,
1163 f->tail_chunk, f->tail,
1166 /* store-rel: producer owned index (paired with load-acq in consumer) */
1167 clib_atomic_store_rel_n (&f->tail, tail);
1171 svm_fifo_dequeue (svm_fifo_t * f, u32 len, u8 * dst)
1173 u32 tail, head, cursize;
1175 f_load_head_tail_cons (f, &head, &tail);
1177 /* current size of fifo can only increase during dequeue: SPSC */
1178 cursize = f_cursize (f, head, tail);
1180 if (PREDICT_FALSE (cursize == 0))
1181 return SVM_FIFO_EEMPTY;
1183 len = clib_min (cursize, len);
1184 svm_fifo_copy_from_chunk (f, f->head_chunk, head, dst, len, &f->head_chunk);
1185 head = (head + len) % f->size;
1187 if (PREDICT_FALSE (f->flags & SVM_FIFO_F_GROW))
1188 svm_fifo_try_grow (f, head);
1190 /* store-rel: consumer owned index (paired with load-acq in producer) */
1191 clib_atomic_store_rel_n (&f->head, head);
1197 svm_fifo_peek (svm_fifo_t * f, u32 offset, u32 len, u8 * dst)
1199 u32 tail, head, cursize, head_idx;
1201 f_load_head_tail_cons (f, &head, &tail);
1203 /* current size of fifo can only increase during peek: SPSC */
1204 cursize = f_cursize (f, head, tail);
1206 if (PREDICT_FALSE (cursize < offset))
1207 return SVM_FIFO_EEMPTY;
1209 len = clib_min (cursize - offset, len);
1210 head_idx = (head + offset) % f->size;
1212 if (f->flags & SVM_FIFO_F_MULTI_CHUNK)
1213 svm_fifo_update_ooo_deq (f, head, head_idx, (head_idx + len) % f->size);
1215 svm_fifo_copy_from_chunk (f, f->ooo_deq, head_idx, dst, len, &f->ooo_deq);
1220 svm_fifo_dequeue_drop (svm_fifo_t * f, u32 len)
1222 u32 total_drop_bytes, tail, head, cursize;
1224 f_load_head_tail_cons (f, &head, &tail);
1226 /* number of bytes available */
1227 cursize = f_cursize (f, head, tail);
1228 if (PREDICT_FALSE (cursize == 0))
1229 return SVM_FIFO_EEMPTY;
1231 /* number of bytes we're going to drop */
1232 total_drop_bytes = clib_min (cursize, len);
1234 svm_fifo_trace_add (f, tail, total_drop_bytes, 3);
1237 head = (head + total_drop_bytes) % f->size;
1239 if (f->flags & SVM_FIFO_F_MULTI_CHUNK)
1240 f->head_chunk = svm_fifo_lookup_clear_chunks (f, &f->ooo_deq_lookup,
1241 f->head_chunk, f->head,
1244 if (PREDICT_FALSE (f->flags & SVM_FIFO_F_GROW))
1245 svm_fifo_try_grow (f, head);
1247 /* store-rel: consumer owned index (paired with load-acq in producer) */
1248 clib_atomic_store_rel_n (&f->head, head);
1250 return total_drop_bytes;
1254 svm_fifo_dequeue_drop_all (svm_fifo_t * f)
1256 /* consumer foreign index */
1257 u32 tail = clib_atomic_load_acq_n (&f->tail);
1259 if (f->flags & SVM_FIFO_F_MULTI_CHUNK)
1260 f->head_chunk = svm_fifo_lookup_clear_chunks (f, &f->ooo_deq_lookup,
1261 f->head_chunk, tail,
1264 if (PREDICT_FALSE (f->flags & SVM_FIFO_F_GROW))
1265 svm_fifo_try_grow (f, tail);
1267 /* store-rel: consumer owned index (paired with load-acq in producer) */
1268 clib_atomic_store_rel_n (&f->head, tail);
1272 svm_fifo_segments (svm_fifo_t * f, svm_fifo_seg_t * fs)
1274 u32 cursize, head, tail, head_idx;
1276 f_load_head_tail_cons (f, &head, &tail);
1278 /* consumer function, cursize can only increase while we're working */
1279 cursize = f_cursize (f, head, tail);
1281 if (PREDICT_FALSE (cursize == 0))
1282 return SVM_FIFO_EEMPTY;
1288 fs[0].len = f->size - head_idx;
1289 fs[0].data = f->head_chunk->data + head_idx;
1290 fs[1].len = cursize - fs[0].len;
1291 fs[1].data = f->head_chunk->data;
1295 fs[0].len = cursize;
1296 fs[0].data = f->head_chunk->data + head_idx;
1304 svm_fifo_segments_free (svm_fifo_t * f, svm_fifo_seg_t * fs)
1308 /* consumer owned index */
1311 ASSERT (fs[0].data == f->head_chunk->data + head);
1312 head = (head + fs[0].len + fs[1].len) % f->size;
1313 /* store-rel: consumer owned index (paired with load-acq in producer) */
1314 clib_atomic_store_rel_n (&f->head, head);
1321 * - no prod and cons are accessing either dest or src fifo
1322 * - fifo is not multi chunk
1325 svm_fifo_clone (svm_fifo_t * df, svm_fifo_t * sf)
1328 clib_memcpy_fast (df->head_chunk->data, sf->head_chunk->data, sf->size);
1330 f_load_head_tail_all_acq (sf, &head, &tail);
1331 clib_atomic_store_rel_n (&df->head, head);
1332 clib_atomic_store_rel_n (&df->tail, tail);
1336 svm_fifo_n_ooo_segments (svm_fifo_t * f)
1338 return pool_elts (f->ooo_segments);
1342 svm_fifo_first_ooo_segment (svm_fifo_t * f)
1344 return pool_elt_at_index (f->ooo_segments, f->ooos_list_head);
1348 * Set fifo pointers to requested offset
1351 svm_fifo_init_pointers (svm_fifo_t * f, u32 head, u32 tail)
1353 head = head % f->size;
1354 tail = tail % f->size;
1355 clib_atomic_store_rel_n (&f->head, head);
1356 clib_atomic_store_rel_n (&f->tail, tail);
1357 if (f->flags & SVM_FIFO_F_MULTI_CHUNK)
1359 svm_fifo_chunk_t *c;
1360 c = svm_fifo_find_chunk (f, head);
1362 f->head_chunk = f->ooo_deq = c;
1363 c = svm_fifo_find_chunk (f, tail);
1365 f->tail_chunk = f->ooo_enq = c;
1370 svm_fifo_add_subscriber (svm_fifo_t * f, u8 subscriber)
1372 if (f->n_subscribers >= SVM_FIFO_MAX_EVT_SUBSCRIBERS)
1374 f->subscribers[f->n_subscribers++] = subscriber;
1378 svm_fifo_del_subscriber (svm_fifo_t * f, u8 subscriber)
1382 for (i = 0; i < f->n_subscribers; i++)
1384 if (f->subscribers[i] != subscriber)
1386 f->subscribers[i] = f->subscribers[f->n_subscribers - 1];
1393 svm_fifo_is_sane (svm_fifo_t * f)
1395 if (f->size - 1 != f->nitems && !(f->flags & SVM_FIFO_F_SHRINK))
1397 if (!svm_fifo_chunk_includes_pos (f->head_chunk, f->head))
1399 if (!svm_fifo_chunk_includes_pos (f->tail_chunk, f->tail))
1402 if (f->start_chunk->next != f->start_chunk)
1404 svm_fifo_chunk_t *c, *prev = 0, *tmp;
1407 if (!(f->flags & SVM_FIFO_F_MULTI_CHUNK))
1413 tmp = svm_fifo_find_chunk (f, c->start_byte);
1416 if (prev && (prev->start_byte + prev->length != c->start_byte))
1419 if (c->rb_index != RBTREE_TNIL_INDEX)
1423 tmp = svm_fifo_find_chunk_rbtree (&f->ooo_enq_lookup,
1432 tmp = svm_fifo_find_chunk_rbtree (&f->ooo_deq_lookup,
1451 while (c != f->start_chunk);
1453 if (size != f->size)
1461 svm_fifo_set_single_thread_owned (svm_fifo_t * f)
1463 if (f->flags & SVM_FIFO_F_SINGLE_THREAD_OWNED)
1465 if (f->master_thread_index == os_get_thread_index ())
1467 /* just a duplicate call */
1471 /* already owned by another thread */
1475 f->flags |= SVM_FIFO_F_SINGLE_THREAD_OWNED;
1480 format_ooo_segment (u8 * s, va_list * args)
1482 svm_fifo_t *f = va_arg (*args, svm_fifo_t *);
1483 ooo_segment_t *seg = va_arg (*args, ooo_segment_t *);
1484 u32 normalized_start = (seg->start + f->nitems - f->tail) % f->size;
1485 s = format (s, "[%u, %u], len %u, next %d, prev %d", normalized_start,
1486 (normalized_start + seg->length) % f->size, seg->length,
1487 seg->next, seg->prev);
1492 svm_fifo_dump_trace (u8 * s, svm_fifo_t * f)
1495 svm_fifo_trace_elem_t *seg = 0;
1500 vec_foreach (seg, f->trace)
1502 s = format (s, "{%u, %u, %u}, ", seg->offset, seg->len, seg->action);
1505 s = format (s, "\n");
1507 s = format (s, "\n");
1516 svm_fifo_replay (u8 * s, svm_fifo_t * f, u8 no_read, u8 verbose)
1520 svm_fifo_trace_elem_t *trace;
1522 svm_fifo_t *dummy_fifo;
1529 trace_len = vec_len (trace);
1535 dummy_fifo = svm_fifo_create (f->size);
1536 clib_memset (f->head_chunk->data, 0xFF, f->nitems);
1537 vec_validate (data, f->nitems);
1538 for (i = 0; i < vec_len (data); i++)
1541 for (i = 0; i < trace_len; i++)
1543 offset = trace[i].offset;
1544 if (trace[i].action == 1)
1547 s = format (s, "adding [%u, %u]:", trace[i].offset,
1548 (trace[i].offset + trace[i].len) % dummy_fifo->size);
1549 svm_fifo_enqueue_with_offset (dummy_fifo, trace[i].offset,
1550 trace[i].len, &data[offset]);
1552 else if (trace[i].action == 2)
1555 s = format (s, "adding [%u, %u]:", 0, trace[i].len);
1556 svm_fifo_enqueue (dummy_fifo, trace[i].len, &data[offset]);
1561 s = format (s, "read: %u", trace[i].len);
1562 svm_fifo_dequeue_drop (dummy_fifo, trace[i].len);
1565 s = format (s, "%U", format_svm_fifo, dummy_fifo, 1);
1568 s = format (s, "result: %U", format_svm_fifo, dummy_fifo, 1);
1574 format_ooo_list (u8 * s, va_list * args)
1576 svm_fifo_t *f = va_arg (*args, svm_fifo_t *);
1577 u32 indent = va_arg (*args, u32);
1578 u32 ooo_segment_index = f->ooos_list_head;
1581 while (ooo_segment_index != OOO_SEGMENT_INVALID_INDEX)
1583 seg = pool_elt_at_index (f->ooo_segments, ooo_segment_index);
1584 s = format (s, "%U%U\n", format_white_space, indent, format_ooo_segment,
1586 ooo_segment_index = seg->next;
1593 format_svm_fifo (u8 * s, va_list * args)
1595 svm_fifo_t *f = va_arg (*args, svm_fifo_t *);
1596 int verbose = va_arg (*args, int);
1602 indent = format_get_indent (s);
1603 s = format (s, "cursize %u nitems %u has_event %d\n",
1604 svm_fifo_max_dequeue (f), f->nitems, f->has_event);
1605 s = format (s, "%Uhead %u tail %u segment manager %u\n", format_white_space,
1606 indent, (f->head % f->size), (f->tail % f->size),
1607 f->segment_manager);
1610 s = format (s, "%Uvpp session %d thread %d app session %d thread %d\n",
1611 format_white_space, indent, f->master_session_index,
1612 f->master_thread_index, f->client_session_index,
1613 f->client_thread_index);
1617 s = format (s, "%Uooo pool %d active elts newest %u\n",
1618 format_white_space, indent, pool_elts (f->ooo_segments),
1620 if (svm_fifo_has_ooo_data (f))
1621 s = format (s, " %U", format_ooo_list, f, indent, verbose);
1628 * fd.io coding-style-patch-verification: ON
1631 * eval: (c-set-style "gnu")