aboutsummaryrefslogtreecommitdiffstats
path: root/src/svm
diff options
context:
space:
mode:
authorFlorin Coras <fcoras@cisco.com>2019-12-19 16:10:58 -0800
committerDave Barach <openvpp@barachs.net>2020-02-25 19:18:49 +0000
commitf22f4e562e1b922cff036ef628b77fd2d479d015 (patch)
tree4cbc3091a5ce89a73c94685dcee198dd583ca375 /src/svm
parentb020806806c0e6c54886cdb4347a5fd1f19504b0 (diff)
svm: refactor fifo
Type: refactor Switch from a wrapped byte space to a "continuous" one wherein fifo chunks are appended to the fifo as more data is enqueued and chunks are removed as data is dequeued. The fifo is still subject to a maximum size, i.e., maximum number of bytes that can be enqueued, so the max number of chunks associated to the fifo is also constrained. When enqueueing data, which must fit within the available free space, if not enough "supporting" chunk memory is available, the fifo asks the fifo segment for enough chunk memory to ensure that the write can succeed. To avoid allocating large amounts of small chunks due to small writes, if possible, the size of the chunks requested is lower capped by min_alloc. When dequeuing data, all the chunks that have been completely drained, i.e., head moved beyond the chunks’ end bytes, are unlinked from the fifo and returned to the fifo segment. The one exception to this is the last chunk which is never unlinked. Change-Id: I98c1dbd9135fb79650365c7e40c29238b96cd4ee Signed-off-by: Florin Coras <fcoras@cisco.com>
Diffstat (limited to 'src/svm')
-rw-r--r--src/svm/CMakeLists.txt1
-rw-r--r--src/svm/fifo_segment.c189
-rw-r--r--src/svm/fifo_segment.h44
-rw-r--r--src/svm/fifo_types.h130
-rw-r--r--src/svm/svm_fifo.c1044
-rw-r--r--src/svm/svm_fifo.h255
6 files changed, 782 insertions, 881 deletions
diff --git a/src/svm/CMakeLists.txt b/src/svm/CMakeLists.txt
index 7664014153a..2cb76948591 100644
--- a/src/svm/CMakeLists.txt
+++ b/src/svm/CMakeLists.txt
@@ -28,6 +28,7 @@ add_vpp_library(svm
INSTALL_HEADERS
fifo_segment.h
+ fifo_types.h
message_queue.h
queue.h
ssvm.h
diff --git a/src/svm/fifo_segment.c b/src/svm/fifo_segment.c
index bc46aba7bf6..49cd1161a4b 100644
--- a/src/svm/fifo_segment.c
+++ b/src/svm/fifo_segment.c
@@ -127,6 +127,7 @@ fifo_segment_init (fifo_segment_t * fs)
{
fss = fsh_slice_get (fsh, i);
vec_validate_init_empty (fss->free_chunks, max_chunk_sz, 0);
+ clib_spinlock_init (&fss->chunk_lock);
}
ssvm_pop_heap (oldheap);
@@ -243,6 +244,8 @@ fifo_segment_main_init (fifo_segment_main_t * sm, u64 baseva,
static inline u32
fs_freelist_for_size (u32 size)
{
+ if (PREDICT_FALSE (size < FIFO_SEGMENT_MIN_FIFO_SIZE))
+ return 0;
return max_log2 (size) - FIFO_SEGMENT_MIN_LOG2_FIFO_SIZE;
}
@@ -278,9 +281,8 @@ fs_try_alloc_fifo_freelist (fifo_segment_slice_t * fss,
fss->free_fifos = f->next;
fss->free_chunks[fl_index] = c->next;
- c->next = c;
+ c->next = 0;
c->start_byte = 0;
- c->length = data_bytes;
memset (f, 0, sizeof (*f));
f->start_chunk = c;
f->end_chunk = c;
@@ -331,7 +333,6 @@ fs_try_alloc_fifo_freelist_multi_chunk (fifo_segment_header_t * fsh,
c->next = first;
first = c;
n_alloc += fl_size;
- c->length = clib_min (fl_size, data_bytes);
data_bytes -= c->length;
}
else
@@ -370,7 +371,6 @@ fs_try_alloc_fifo_freelist_multi_chunk (fifo_segment_header_t * fsh,
f->start_chunk = first;
f->end_chunk = last;
- last->next = first;
fss->n_fl_chunk_bytes -= n_alloc;
return f;
}
@@ -412,7 +412,8 @@ fs_try_alloc_fifo_batch (fifo_segment_header_t * fsh,
c = (svm_fifo_chunk_t *) (fmem + sizeof (*f));
c->start_byte = 0;
c->length = rounded_data_size;
- c->rb_index = RBTREE_TNIL_INDEX;
+ c->enq_rb_index = RBTREE_TNIL_INDEX;
+ c->deq_rb_index = RBTREE_TNIL_INDEX;
c->next = fss->free_chunks[fl_index];
fss->free_chunks[fl_index] = c;
fmem += hdrs + rounded_data_size;
@@ -466,7 +467,7 @@ fs_try_alloc_fifo (fifo_segment_header_t * fsh, fifo_segment_slice_t * fss,
if (fifo_sz <= n_free_bytes)
{
void *oldheap = ssvm_push_heap (fsh->ssvm_sh);
- f = svm_fifo_create (data_bytes);
+ f = svm_fifo_alloc (data_bytes);
ssvm_pop_heap (oldheap);
if (f)
{
@@ -479,9 +480,87 @@ fs_try_alloc_fifo (fifo_segment_header_t * fsh, fifo_segment_slice_t * fss,
done:
+ if (f)
+ f->fs_hdr = fsh;
return f;
}
+svm_fifo_chunk_t *
+fsh_alloc_chunk (fifo_segment_header_t * fsh, u32 slice_index, u32 chunk_size)
+{
+ fifo_segment_slice_t *fss;
+ svm_fifo_chunk_t *c;
+ void *oldheap;
+ int fl_index;
+
+ fl_index = fs_freelist_for_size (chunk_size);
+ fss = fsh_slice_get (fsh, slice_index);
+
+ clib_spinlock_lock (&fss->chunk_lock);
+ c = fss->free_chunks[fl_index];
+
+ if (!c)
+ {
+ fsh_check_mem (fsh);
+ chunk_size = fs_freelist_index_to_size (fl_index);
+ if (fsh_n_free_bytes (fsh) < chunk_size)
+ goto done;
+
+ oldheap = ssvm_push_heap (fsh->ssvm_sh);
+ c = svm_fifo_chunk_alloc (chunk_size);
+ ssvm_pop_heap (oldheap);
+
+ if (!c)
+ goto done;
+
+ fsh_free_bytes_sub (fsh, chunk_size + sizeof (*c));
+ }
+ else
+ {
+ fss->free_chunks[fl_index] = c->next;
+ c->next = 0;
+ fss->n_fl_chunk_bytes -= fs_freelist_index_to_size (fl_index);
+ }
+
+done:
+
+ clib_spinlock_unlock (&fss->chunk_lock);
+
+ return c;
+}
+
+static void
+fsh_slice_collect_chunks (fifo_segment_slice_t * fss, svm_fifo_chunk_t * cur)
+{
+ svm_fifo_chunk_t *next;
+ int fl_index;
+
+ clib_spinlock_lock (&fss->chunk_lock);
+
+ while (cur)
+ {
+ next = cur->next;
+ fl_index = fs_freelist_for_size (cur->length);
+ cur->next = fss->free_chunks[fl_index];
+ cur->enq_rb_index = RBTREE_TNIL_INDEX;
+ cur->deq_rb_index = RBTREE_TNIL_INDEX;
+ fss->free_chunks[fl_index] = cur;
+ fss->n_fl_chunk_bytes += fs_freelist_index_to_size (fl_index);
+ cur = next;
+ }
+
+ clib_spinlock_unlock (&fss->chunk_lock);
+}
+
+void
+fsh_collect_chunks (fifo_segment_header_t * fsh, u32 slice_index,
+ svm_fifo_chunk_t * cur)
+{
+ fifo_segment_slice_t *fss;
+ fss = fsh_slice_get (fsh, slice_index);
+ fsh_slice_collect_chunks (fss, cur);
+}
+
/**
* Allocate fifo in fifo segment
*/
@@ -502,13 +581,8 @@ fifo_segment_alloc_fifo_w_slice (fifo_segment_t * fs, u32 slice_index,
f->slice_index = slice_index;
- /* (re)initialize the fifo, as in svm_fifo_create */
svm_fifo_init (f, data_bytes);
- /* Initialize chunks and rbtree for multi-chunk fifos */
- if (f->start_chunk->next != f->start_chunk)
- svm_fifo_init_chunks (f);
-
/* If rx fifo type add to active fifos list. When cleaning up segment,
* we need a list of active sessions that should be disconnected. Since
* both rx and tx fifos keep pointers to the session, it's enough to track
@@ -522,7 +596,14 @@ fifo_segment_alloc_fifo_w_slice (fifo_segment_t * fs, u32 slice_index,
}
fss->fifos = f;
f->flags |= SVM_FIFO_F_LL_TRACKED;
+
+ svm_fifo_init_ooo_lookup (f, 0 /* ooo enq */ );
+ }
+ else
+ {
+ svm_fifo_init_ooo_lookup (f, 1 /* ooo deq */ );
}
+
fsh_active_fifos_update (fsh, 1);
done:
@@ -536,9 +617,7 @@ void
fifo_segment_free_fifo (fifo_segment_t * fs, svm_fifo_t * f)
{
fifo_segment_header_t *fsh = fs->h;
- svm_fifo_chunk_t *cur, *next;
fifo_segment_slice_t *fss;
- int fl_index;
ASSERT (f->refcnt > 0);
@@ -565,26 +644,13 @@ fifo_segment_free_fifo (fifo_segment_t * fs, svm_fifo_t * f)
fss->free_fifos = f;
/* Free fifo chunks */
- cur = f->start_chunk;
- do
- {
- next = cur->next;
- fl_index = fs_freelist_for_size (cur->length);
- ASSERT (fl_index < vec_len (fss->free_chunks));
- cur->next = fss->free_chunks[fl_index];
- cur->rb_index = RBTREE_TNIL_INDEX;
- fss->free_chunks[fl_index] = cur;
- fss->n_fl_chunk_bytes += fs_freelist_index_to_size (fl_index);
- cur = next;
- }
- while (cur != f->start_chunk);
+ fsh_slice_collect_chunks (fss, f->start_chunk);
- f->start_chunk = f->end_chunk = f->new_chunks = 0;
+ f->start_chunk = f->end_chunk = 0;
f->head_chunk = f->tail_chunk = f->ooo_enq = f->ooo_deq = 0;
- svm_fifo_free_chunk_lookup (f);
-
/* not allocated on segment heap */
+ svm_fifo_free_chunk_lookup (f);
svm_fifo_free_ooo_data (f);
if (CLIB_DEBUG)
@@ -751,71 +817,6 @@ fifo_segment_preallocate_fifo_pairs (fifo_segment_t * fs,
}
}
-int
-fifo_segment_grow_fifo (fifo_segment_t * fs, svm_fifo_t * f, u32 chunk_size)
-{
- fifo_segment_header_t *fsh = fs->h;
- fifo_segment_slice_t *fss;
- svm_fifo_chunk_t *c;
- void *oldheap;
- int fl_index;
-
- fl_index = fs_freelist_for_size (chunk_size);
- fss = fsh_slice_get (fsh, f->slice_index);
-
- c = fss->free_chunks[fl_index];
-
- if (!c)
- {
- fsh_check_mem (fsh);
- if (fsh_n_free_bytes (fsh) < chunk_size)
- return -1;
-
- oldheap = ssvm_push_heap (fsh->ssvm_sh);
- c = svm_fifo_chunk_alloc (chunk_size);
- ssvm_pop_heap (oldheap);
-
- if (!c)
- return -1;
-
- fsh_free_bytes_sub (fsh, chunk_size + sizeof (*c));
- }
- else
- {
- fss->free_chunks[fl_index] = c->next;
- c->next = 0;
- fss->n_fl_chunk_bytes -= fs_freelist_index_to_size (fl_index);
- }
-
- svm_fifo_add_chunk (f, c);
-
- return 0;
-}
-
-int
-fifo_segment_collect_fifo_chunks (fifo_segment_t * fs, svm_fifo_t * f)
-{
- fifo_segment_header_t *fsh = fs->h;
- svm_fifo_chunk_t *cur, *next;
- fifo_segment_slice_t *fss;
- int fl_index;
-
- cur = svm_fifo_collect_chunks (f);
-
- fss = fsh_slice_get (fsh, f->slice_index);
-
- while (cur)
- {
- next = cur->next;
- fl_index = fs_freelist_for_size (cur->length);
- cur->next = fss->free_chunks[fl_index];
- fss->free_chunks[fl_index] = cur;
- cur = next;
- }
-
- return 0;
-}
-
/**
* Get number of active fifos
*/
diff --git a/src/svm/fifo_segment.h b/src/svm/fifo_segment.h
index 02d45d3244d..85548063972 100644
--- a/src/svm/fifo_segment.h
+++ b/src/svm/fifo_segment.h
@@ -16,6 +16,7 @@
#define __included_fifo_segment_h__
#include <svm/ssvm.h>
+#include <svm/fifo_types.h>
#include <svm/svm_fifo.h>
typedef enum
@@ -38,26 +39,6 @@ typedef enum fifo_segment_flags_
FIFO_SEGMENT_F_MEM_LIMIT = 1 << 2,
} fifo_segment_flags_t;
-typedef struct fifo_segment_slice_
-{
- svm_fifo_t *fifos; /**< Linked list of active RX fifos */
- svm_fifo_t *free_fifos; /**< Freelists by fifo size */
- svm_fifo_chunk_t **free_chunks; /**< Freelists by chunk size */
- uword n_fl_chunk_bytes; /**< Chunk bytes on freelist */
-} fifo_segment_slice_t;
-
-typedef struct
-{
- fifo_segment_slice_t *slices; /** Fixed array of slices */
- ssvm_shared_header_t *ssvm_sh; /**< Pointer to fs ssvm shared hdr */
- uword n_free_bytes; /**< Segment free bytes */
- u32 n_active_fifos; /**< Number of active fifos */
- u32 n_reserved_bytes; /**< Bytes not to be allocated */
- u32 max_log2_chunk_size; /**< Max log2(chunk size) for fs */
- u8 flags; /**< Segment flags */
- u8 n_slices; /**< Number of slices */
-} fifo_segment_header_t;
-
typedef struct
{
ssvm_private_t ssvm; /**< ssvm segment data */
@@ -158,25 +139,12 @@ void fifo_segment_preallocate_fifo_pairs (fifo_segment_t * fs,
u32 rx_fifo_size,
u32 tx_fifo_size,
u32 * n_fifo_pairs);
-/**
- * Grow fifo size by adding an additional chunk of memory
- *
- * @param fs fifo segment for fifo
- * @param f fifo to be grown
- * @param chunk_size number of bytes to be added to fifo
- * @return 0 on success or a negative number otherwise
- */
-int fifo_segment_grow_fifo (fifo_segment_t * fs, svm_fifo_t * f,
- u32 chunk_size);
-/**
- * Collect unused chunks for fifo
- *
- * @param fs fifo segment for fifo
- * @param f fifo whose chunks are to be collected
- * @return 0 on success, error otherwise
- */
-int fifo_segment_collect_fifo_chunks (fifo_segment_t * fs, svm_fifo_t * f);
+svm_fifo_chunk_t *fsh_alloc_chunk (fifo_segment_header_t * fsh,
+ u32 slice_index, u32 chunk_size);
+
+void fsh_collect_chunks (fifo_segment_header_t * fsh, u32 slice_index,
+ svm_fifo_chunk_t * cur);
/**
* Fifo segment estimate of number of free bytes
diff --git a/src/svm/fifo_types.h b/src/svm/fifo_types.h
new file mode 100644
index 00000000000..3e6a14eea7d
--- /dev/null
+++ b/src/svm/fifo_types.h
@@ -0,0 +1,130 @@
+/*
+ * Copyright (c) 2020 Cisco and/or its affiliates.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef SRC_SVM_FIFO_TYPES_H_
+#define SRC_SVM_FIFO_TYPES_H_
+
+#include <svm/ssvm.h>
+#include <vppinfra/clib.h>
+#include <vppinfra/rbtree.h>
+
+#define SVM_FIFO_TRACE (0)
+#define SVM_FIFO_MAX_EVT_SUBSCRIBERS 7
+
+typedef struct fifo_segment_header_ fifo_segment_header_t;
+
+typedef struct svm_fifo_chunk_
+{
+ u32 start_byte; /**< chunk start byte */
+ u32 length; /**< length of chunk in bytes */
+ struct svm_fifo_chunk_ *next; /**< pointer to next chunk in linked-lists */
+ rb_node_index_t enq_rb_index; /**< enq node index if chunk in rbtree */
+ rb_node_index_t deq_rb_index; /**< deq node index if chunk in rbtree */
+ u8 data[0]; /**< start of chunk data */
+} svm_fifo_chunk_t;
+
+typedef struct
+{
+ u32 next; /**< Next linked-list element pool index */
+ u32 prev; /**< Previous linked-list element pool index */
+ u32 start; /**< Start of segment, normalized*/
+ u32 length; /**< Length of segment */
+} ooo_segment_t;
+
+typedef struct
+{
+ u32 offset;
+ u32 len;
+ u32 action;
+} svm_fifo_trace_elem_t;
+
+typedef struct _svm_fifo
+{
+ CLIB_CACHE_LINE_ALIGN_MARK (shared_first);
+ fifo_segment_header_t *fs_hdr;/**< fifo segment header for fifo */
+ svm_fifo_chunk_t *start_chunk;/**< first chunk in fifo chunk list */
+ svm_fifo_chunk_t *end_chunk; /**< end chunk in fifo chunk list */
+ u32 min_alloc; /**< min chunk alloc if space available */
+ u32 size; /**< size of the fifo in bytes */
+ u8 flags; /**< fifo flags */
+ u8 slice_index; /**< segment slice for fifo */
+
+ CLIB_CACHE_LINE_ALIGN_MARK (shared_second);
+ volatile u32 has_event; /**< non-zero if deq event exists */
+ u32 master_session_index; /**< session layer session index */
+ u32 client_session_index; /**< app session index */
+ u8 master_thread_index; /**< session layer thread index */
+ u8 client_thread_index; /**< app worker index */
+ i8 refcnt; /**< reference count */
+ u32 segment_manager; /**< session layer segment manager index */
+ u32 segment_index; /**< segment index in segment manager */
+ struct _svm_fifo *next; /**< next in freelist/active chain */
+ struct _svm_fifo *prev; /**< prev in active chain */
+
+ CLIB_CACHE_LINE_ALIGN_MARK (consumer);
+ rb_tree_t ooo_deq_lookup; /**< rbtree for ooo deq chunk lookup */
+ svm_fifo_chunk_t *head_chunk; /**< tracks chunk where head lands */
+ svm_fifo_chunk_t *ooo_deq; /**< last chunk used for ooo dequeue */
+ u32 head; /**< fifo head position/byte */
+ volatile u32 want_deq_ntf; /**< producer wants nudge */
+ volatile u32 has_deq_ntf;
+
+ CLIB_CACHE_LINE_ALIGN_MARK (producer);
+ rb_tree_t ooo_enq_lookup; /**< rbtree for ooo enq chunk lookup */
+ u32 tail; /**< fifo tail position/byte */
+ u32 ooos_list_head; /**< Head of out-of-order linked-list */
+ svm_fifo_chunk_t *tail_chunk; /**< tracks chunk where tail lands */
+ svm_fifo_chunk_t *ooo_enq; /**< last chunk used for ooo enqueue */
+ ooo_segment_t *ooo_segments; /**< Pool of ooo segments */
+ u32 ooos_newest; /**< Last segment to have been updated */
+ volatile u8 n_subscribers; /**< Number of subscribers for io events */
+ u8 subscribers[SVM_FIFO_MAX_EVT_SUBSCRIBERS];
+
+#if SVM_FIFO_TRACE
+ svm_fifo_trace_elem_t *trace;
+#endif
+
+} svm_fifo_t;
+
+typedef struct fifo_segment_slice_
+{
+ svm_fifo_t *fifos; /**< Linked list of active RX fifos */
+ svm_fifo_t *free_fifos; /**< Freelists by fifo size */
+ svm_fifo_chunk_t **free_chunks; /**< Freelists by chunk size */
+ uword n_fl_chunk_bytes; /**< Chunk bytes on freelist */
+ clib_spinlock_t chunk_lock;
+} fifo_segment_slice_t;
+
+struct fifo_segment_header_
+{
+ fifo_segment_slice_t *slices; /** Fixed array of slices */
+ ssvm_shared_header_t *ssvm_sh; /**< Pointer to fs ssvm shared hdr */
+ uword n_free_bytes; /**< Segment free bytes */
+ u32 n_active_fifos; /**< Number of active fifos */
+ u32 n_reserved_bytes; /**< Bytes not to be allocated */
+ u32 max_log2_chunk_size; /**< Max log2(chunk size) for fs */
+ u8 flags; /**< Segment flags */
+ u8 n_slices; /**< Number of slices */
+};
+
+#endif /* SRC_SVM_FIFO_TYPES_H_ */
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */
diff --git a/src/svm/svm_fifo.c b/src/svm/svm_fifo.c
index 3df67135cfd..0168c08e49c 100644
--- a/src/svm/svm_fifo.c
+++ b/src/svm/svm_fifo.c
@@ -18,6 +18,7 @@
*/
#include <svm/svm_fifo.h>
+#include <svm/fifo_segment.h>
#include <vppinfra/cpu.h>
CLIB_MARCH_FN (svm_fifo_copy_to_chunk, void, svm_fifo_t * f,
@@ -26,7 +27,8 @@ CLIB_MARCH_FN (svm_fifo_copy_to_chunk, void, svm_fifo_t * f,
{
u32 n_chunk;
- ASSERT (tail_idx >= c->start_byte && tail_idx < c->start_byte + c->length);
+ ASSERT (f_pos_geq (tail_idx, c->start_byte)
+ && f_pos_lt (tail_idx, c->start_byte + c->length));
tail_idx -= c->start_byte;
n_chunk = c->length - tail_idx;
@@ -56,7 +58,8 @@ CLIB_MARCH_FN (svm_fifo_copy_from_chunk, void, svm_fifo_t * f,
{
u32 n_chunk;
- ASSERT (head_idx >= c->start_byte && head_idx < c->start_byte + c->length);
+ ASSERT (f_pos_geq (head_idx, c->start_byte)
+ && f_pos_lt (head_idx, c->start_byte + c->length));
head_idx -= c->start_byte;
n_chunk = c->length - head_idx;
@@ -98,34 +101,10 @@ svm_fifo_copy_from_chunk (svm_fifo_t * f, svm_fifo_chunk_t * c, u32 head_idx,
last);
}
-static inline u8
-position_lt (svm_fifo_t * f, u32 a, u32 b, u32 tail)
-{
- return (f_distance_to (f, a, tail) < f_distance_to (f, b, tail));
-}
-
-static inline u8
-position_leq (svm_fifo_t * f, u32 a, u32 b, u32 tail)
-{
- return (f_distance_to (f, a, tail) <= f_distance_to (f, b, tail));
-}
-
-static inline u8
-position_gt (svm_fifo_t * f, u32 a, u32 b, u32 tail)
-{
- return (f_distance_to (f, a, tail) > f_distance_to (f, b, tail));
-}
-
-static inline u32
-position_diff (svm_fifo_t * f, u32 a, u32 b, u32 tail)
-{
- return f_distance_to (f, a, tail) - f_distance_to (f, b, tail);
-}
-
static inline u32
-ooo_segment_end_pos (svm_fifo_t * f, ooo_segment_t * s)
+ooo_segment_end_pos (ooo_segment_t * s)
{
- return (s->start + s->length) % f->size;
+ return (s->start + s->length);
}
void
@@ -200,10 +179,10 @@ ooo_segment_add (svm_fifo_t * f, u32 offset, u32 head, u32 tail, u32 length)
u32 new_index, s_end_pos, s_index;
u32 offset_pos, offset_end_pos;
- ASSERT (offset + length <= f_distance_to (f, head, tail) || head == tail);
+ ASSERT (offset + length <= f_free_count (f, head, tail));
- offset_pos = (tail + offset) % f->size;
- offset_end_pos = (tail + offset + length) % f->size;
+ offset_pos = tail + offset;
+ offset_end_pos = tail + offset + length;
f->ooos_newest = OOO_SEGMENT_INVALID_INDEX;
@@ -218,28 +197,27 @@ ooo_segment_add (svm_fifo_t * f, u32 offset, u32 head, u32 tail, u32 length)
/* Find first segment that starts after new segment */
s = pool_elt_at_index (f->ooo_segments, f->ooos_list_head);
while (s->next != OOO_SEGMENT_INVALID_INDEX
- && position_lt (f, s->start, offset_pos, tail))
+ && f_pos_lt (s->start, offset_pos))
s = pool_elt_at_index (f->ooo_segments, s->next);
/* If we have a previous and we overlap it, use it as starting point */
prev = ooo_segment_prev (f, s);
- if (prev
- && position_leq (f, offset_pos, ooo_segment_end_pos (f, prev), tail))
+ if (prev && f_pos_leq (offset_pos, ooo_segment_end_pos (prev)))
{
s = prev;
- s_end_pos = ooo_segment_end_pos (f, s);
+ s_end_pos = ooo_segment_end_pos (s);
/* Since we have previous, offset start position cannot be smaller
* than prev->start. Check tail */
- ASSERT (position_lt (f, s->start, offset_pos, tail));
+ ASSERT (f_pos_lt (s->start, offset_pos));
goto check_tail;
}
s_index = s - f->ooo_segments;
- s_end_pos = ooo_segment_end_pos (f, s);
+ s_end_pos = ooo_segment_end_pos (s);
/* No overlap, add before current segment */
- if (position_lt (f, offset_end_pos, s->start, tail))
+ if (f_pos_lt (offset_end_pos, s->start))
{
new_s = ooo_segment_alloc (f, offset_pos, length);
new_index = new_s - f->ooo_segments;
@@ -264,7 +242,7 @@ ooo_segment_add (svm_fifo_t * f, u32 offset, u32 head, u32 tail, u32 length)
return;
}
/* No overlap, add after current segment */
- else if (position_gt (f, offset_pos, s_end_pos, tail))
+ else if (f_pos_gt (offset_pos, s_end_pos))
{
new_s = ooo_segment_alloc (f, offset_pos, length);
new_index = new_s - f->ooo_segments;
@@ -287,24 +265,23 @@ ooo_segment_add (svm_fifo_t * f, u32 offset, u32 head, u32 tail, u32 length)
*/
/* Merge at head */
- if (position_lt (f, offset_pos, s->start, tail))
+ if (f_pos_lt (offset_pos, s->start))
{
s->start = offset_pos;
- s->length = position_diff (f, s_end_pos, s->start, tail);
+ s->length = s_end_pos - s->start;
f->ooos_newest = s - f->ooo_segments;
}
check_tail:
/* Overlapping tail */
- if (position_gt (f, offset_end_pos, s_end_pos, tail))
+ if (f_pos_gt (offset_end_pos, s_end_pos))
{
- s->length = position_diff (f, offset_end_pos, s->start, tail);
+ s->length = offset_end_pos - s->start;
/* Remove the completely overlapped segments in the tail */
it = ooo_segment_next (f, s);
- while (it && position_leq (f, ooo_segment_end_pos (f, it),
- offset_end_pos, tail))
+ while (it && f_pos_leq (ooo_segment_end_pos (it), offset_end_pos))
{
next = ooo_segment_next (f, it);
ooo_segment_free (f, it - f->ooo_segments);
@@ -312,10 +289,9 @@ check_tail:
}
/* If partial overlap with last, merge */
- if (it && position_leq (f, it->start, offset_end_pos, tail))
+ if (it && f_pos_leq (it->start, offset_end_pos))
{
- s->length = position_diff (f, ooo_segment_end_pos (f, it),
- s->start, tail);
+ s->length = ooo_segment_end_pos (it) - s->start;
ooo_segment_free (f, it - f->ooo_segments);
}
f->ooos_newest = s - f->ooo_segments;
@@ -334,7 +310,7 @@ ooo_segment_try_collect (svm_fifo_t * f, u32 n_bytes_enqueued, u32 * tail)
i32 diff;
s = pool_elt_at_index (f->ooo_segments, f->ooos_list_head);
- diff = f_distance_from (f, s->start, *tail);
+ diff = *tail - s->start;
ASSERT (diff != n_bytes_enqueued);
@@ -350,7 +326,7 @@ ooo_segment_try_collect (svm_fifo_t * f, u32 n_bytes_enqueued, u32 * tail)
if (s->length > diff)
{
bytes = s->length - diff;
- *tail = (*tail + bytes) % f->size;
+ *tail = *tail + bytes;
ooo_segment_free (f, s_index);
break;
}
@@ -359,7 +335,7 @@ ooo_segment_try_collect (svm_fifo_t * f, u32 n_bytes_enqueued, u32 * tail)
if (s->next != OOO_SEGMENT_INVALID_INDEX)
{
s = pool_elt_at_index (f->ooo_segments, s->next);
- diff = f_distance_from (f, s->start, *tail);
+ diff = *tail - s->start;
ooo_segment_free (f, s_index);
}
/* End of search */
@@ -370,11 +346,11 @@ ooo_segment_try_collect (svm_fifo_t * f, u32 n_bytes_enqueued, u32 * tail)
}
}
- ASSERT (bytes <= f->nitems);
+ ASSERT (bytes <= f->size);
return bytes;
}
-static ooo_segment_t *
+__clib_unused static ooo_segment_t *
ooo_segment_last (svm_fifo_t * f)
{
ooo_segment_t *s;
@@ -391,36 +367,30 @@ ooo_segment_last (svm_fifo_t * f)
void
svm_fifo_init (svm_fifo_t * f, u32 size)
{
+ svm_fifo_chunk_t *c, *prev;
+ u32 first_chunk, min_alloc;
+
f->size = size;
- /*
- * usable size of the fifo set to rounded_data_size - 1
- * to differentiate between free fifo and empty fifo.
- */
- f->nitems = f->size - 1;
f->ooos_list_head = OOO_SEGMENT_INVALID_INDEX;
f->segment_index = SVM_FIFO_INVALID_INDEX;
f->refcnt = 1;
f->head = f->tail = f->flags = 0;
- f->head_chunk = f->tail_chunk = f->ooo_enq = f->ooo_deq = f->start_chunk;
-}
-
-void
-svm_fifo_init_chunks (svm_fifo_t * f)
-{
- svm_fifo_chunk_t *c, *prev;
+ f->head_chunk = f->tail_chunk = f->start_chunk;
+ f->ooo_deq = f->ooo_enq = 0;
- if (f->start_chunk->next == f->start_chunk)
- return;
-
- f->flags |= SVM_FIFO_F_MULTI_CHUNK;
- rb_tree_init (&f->ooo_enq_lookup);
- rb_tree_init (&f->ooo_deq_lookup);
+ first_chunk = f->start_chunk->length;
+ min_alloc = first_chunk > 16 << 10 ? first_chunk >> 2 : 4096;
+ min_alloc = clib_min (first_chunk, 64 << 10);
+ f->min_alloc = min_alloc;
+ /*
+ * Initialize chunks
+ */
f->start_chunk->start_byte = 0;
prev = f->start_chunk;
c = prev->next;
- while (c != f->start_chunk)
+ while (c)
{
c->start_byte = prev->start_byte + prev->length;
prev = c;
@@ -428,11 +398,26 @@ svm_fifo_init_chunks (svm_fifo_t * f)
}
}
+void
+svm_fifo_init_ooo_lookup (svm_fifo_t * f, u8 ooo_type)
+{
+ if (ooo_type == 0)
+ {
+ ASSERT (!rb_tree_is_init (&f->ooo_enq_lookup));
+ rb_tree_init (&f->ooo_enq_lookup);
+ }
+ else
+ {
+ ASSERT (!rb_tree_is_init (&f->ooo_deq_lookup));
+ rb_tree_init (&f->ooo_deq_lookup);
+ }
+}
+
/**
* Creates a fifo in the current heap. Fails vs blow up the process
*/
svm_fifo_t *
-svm_fifo_create (u32 data_size_in_bytes)
+svm_fifo_alloc (u32 data_size_in_bytes)
{
u32 rounded_data_size;
svm_fifo_chunk_t *c;
@@ -454,13 +439,13 @@ svm_fifo_create (u32 data_size_in_bytes)
return 0;
}
- c->next = c;
+ clib_memset (c, 0, sizeof (*c));
c->start_byte = 0;
c->length = data_size_in_bytes;
- c->rb_index = RBTREE_TNIL_INDEX;
+ c->enq_rb_index = RBTREE_TNIL_INDEX;
+ c->deq_rb_index = RBTREE_TNIL_INDEX;
f->start_chunk = f->end_chunk = c;
- svm_fifo_init (f, data_size_in_bytes);
return f;
}
@@ -485,14 +470,73 @@ svm_fifo_chunk_alloc (u32 size)
return c;
}
-static inline u8
-svm_fifo_chunk_includes_pos (svm_fifo_chunk_t * c, u32 pos)
+/**
+ * Find chunk for given byte position
+ *
+ * @param f fifo
+ * @param pos normalized position in fifo
+ *
+ * @return chunk that includes given position or 0
+ */
+static svm_fifo_chunk_t *
+svm_fifo_find_chunk (svm_fifo_t * f, u32 pos)
+{
+ svm_fifo_chunk_t *c;
+
+ c = f->start_chunk;
+ while (c && !f_chunk_includes_pos (c, pos))
+ c = c->next;
+
+ return c;
+}
+
+static svm_fifo_chunk_t *
+svm_fifo_find_next_chunk (svm_fifo_t * f, svm_fifo_chunk_t * start, u32 pos)
+{
+ svm_fifo_chunk_t *c;
+
+ ASSERT (start != 0);
+
+ c = start;
+ while (c && !f_chunk_includes_pos (c, pos))
+ c = c->next;
+
+ return c;
+}
+
+u32
+svm_fifo_max_read_chunk (svm_fifo_t * f)
+{
+ u32 head, tail, end_chunk;
+
+ f_load_head_tail_cons (f, &head, &tail);
+ ASSERT (!f->head_chunk || f_chunk_includes_pos (f->head_chunk, head));
+
+ if (!f->head_chunk)
+ {
+ f->head_chunk = svm_fifo_find_chunk (f, head);
+ if (PREDICT_FALSE (!f->head_chunk))
+ return 0;
+ }
+
+ end_chunk = f_chunk_end (f->head_chunk);
+
+ return f_pos_lt (end_chunk, tail) ? end_chunk - head : tail - head;
+}
+
+u32
+svm_fifo_max_write_chunk (svm_fifo_t * f)
{
- return (pos >= c->start_byte && pos < c->start_byte + c->length);
+ u32 head, tail;
+
+ f_load_head_tail_prod (f, &head, &tail);
+ ASSERT (!f->tail_chunk || f_chunk_includes_pos (f->tail_chunk, tail));
+
+ return f->tail_chunk ? f_chunk_end (f->tail_chunk) - tail : 0;
}
static rb_node_t *
-svm_fifo_find_node_rbtree (rb_tree_t * rt, u32 pos)
+f_find_node_rbtree (rb_tree_t * rt, u32 pos)
{
rb_node_t *cur, *prev;
@@ -503,7 +547,7 @@ svm_fifo_find_node_rbtree (rb_tree_t * rt, u32 pos)
while (pos != cur->key)
{
prev = cur;
- if (pos < cur->key)
+ if (f_pos_lt (pos, cur->key))
{
cur = rb_node_left (rt, cur);
if (rb_node_is_tnil (rt, cur))
@@ -530,501 +574,206 @@ svm_fifo_find_node_rbtree (rb_tree_t * rt, u32 pos)
}
static svm_fifo_chunk_t *
-svm_fifo_find_chunk_rbtree (rb_tree_t * rt, u32 pos)
+f_find_chunk_rbtree (rb_tree_t * rt, u32 pos)
{
svm_fifo_chunk_t *c;
rb_node_t *n;
- n = svm_fifo_find_node_rbtree (rt, pos);
+ if (!rb_tree_is_init (rt))
+ return 0;
+
+ n = f_find_node_rbtree (rt, pos);
if (!n)
return 0;
c = uword_to_pointer (n->opaque, svm_fifo_chunk_t *);
- if (svm_fifo_chunk_includes_pos (c, pos))
+ if (f_chunk_includes_pos (c, pos))
return c;
return 0;
}
-/**
- * Find chunk for given byte position
- *
- * @param f fifo
- * @param pos normalized position in fifo
- *
- * @return chunk that includes given position or 0
- */
-static svm_fifo_chunk_t *
-svm_fifo_find_chunk (svm_fifo_t * f, u32 pos)
-{
- svm_fifo_chunk_t *c;
-
- c = f->start_chunk;
- do
- {
- if (svm_fifo_chunk_includes_pos (c, pos))
- return c;
- c = c->next;
- }
- while (c != f->start_chunk);
-
- return 0;
-}
-
static void
-svm_fifo_update_ooo_enq (svm_fifo_t * f, u32 ref_pos, u32 start_pos,
- u32 end_pos)
+f_update_ooo_enq (svm_fifo_t * f, u32 start_pos, u32 end_pos)
{
rb_tree_t *rt = &f->ooo_enq_lookup;
svm_fifo_chunk_t *c;
rb_node_t *cur;
- if (svm_fifo_chunk_includes_pos (f->ooo_enq, start_pos)
- && svm_fifo_chunk_includes_pos (f->ooo_enq, end_pos)
- && ref_pos < start_pos)
- return;
+ /* Use linear search if rbtree is not initialized */
+ if (PREDICT_FALSE (!rb_tree_is_init (rt)))
+ {
+ f->ooo_enq = svm_fifo_find_next_chunk (f, f->tail_chunk, start_pos);
+ return;
+ }
if (rt->root == RBTREE_TNIL_INDEX)
{
c = f->tail_chunk;
- c->rb_index = rb_tree_add2 (rt, c->start_byte, pointer_to_uword (c));
+ ASSERT (c->enq_rb_index == RBTREE_TNIL_INDEX);
+ c->enq_rb_index = rb_tree_add_custom (rt, c->start_byte,
+ pointer_to_uword (c), f_pos_lt);
}
else
{
- cur = svm_fifo_find_node_rbtree (rt, start_pos);
+ cur = f_find_node_rbtree (rt, start_pos);
c = uword_to_pointer (cur->opaque, svm_fifo_chunk_t *);
- if (ref_pos > start_pos && c->start_byte > start_pos)
- {
- c = f->end_chunk;
- ASSERT (c->rb_index != RBTREE_TNIL_INDEX);
- }
+ ASSERT (f_pos_leq (c->start_byte, start_pos));
}
- if (svm_fifo_chunk_includes_pos (c, start_pos))
+ if (f_chunk_includes_pos (c, start_pos))
f->ooo_enq = c;
- if (svm_fifo_chunk_includes_pos (c, end_pos) && ref_pos < end_pos)
+ if (f_chunk_includes_pos (c, end_pos))
return;
do
{
c = c->next;
- if (c->rb_index != RBTREE_TNIL_INDEX)
+ if (!c || c->enq_rb_index != RBTREE_TNIL_INDEX)
break;
- c->rb_index = rb_tree_add2 (rt, c->start_byte, pointer_to_uword (c));
+ c->enq_rb_index = rb_tree_add_custom (rt, c->start_byte,
+ pointer_to_uword (c), f_pos_lt);
- if (svm_fifo_chunk_includes_pos (c, start_pos))
+ if (f_chunk_includes_pos (c, start_pos))
f->ooo_enq = c;
-
}
- while (!svm_fifo_chunk_includes_pos (c, end_pos));
+ while (!f_chunk_includes_pos (c, end_pos));
}
static void
-svm_fifo_update_ooo_deq (svm_fifo_t * f, u32 ref_pos, u32 start_pos,
- u32 end_pos)
+f_update_ooo_deq (svm_fifo_t * f, u32 start_pos, u32 end_pos)
{
rb_tree_t *rt = &f->ooo_deq_lookup;
rb_node_t *cur;
svm_fifo_chunk_t *c;
- if (svm_fifo_chunk_includes_pos (f->ooo_deq, start_pos)
- && svm_fifo_chunk_includes_pos (f->ooo_deq, end_pos)
- && ref_pos < start_pos)
- return;
+ /* Use linear search if rbtree is not initialized */
+ if (PREDICT_FALSE (!rb_tree_is_init (rt)))
+ {
+ f->ooo_deq = svm_fifo_find_chunk (f, start_pos);
+ return;
+ }
if (rt->root == RBTREE_TNIL_INDEX)
{
- c = f->head_chunk;
- c->rb_index = rb_tree_add2 (rt, c->start_byte, pointer_to_uword (c));
+ c = f->start_chunk;
+ ASSERT (c->deq_rb_index == RBTREE_TNIL_INDEX);
+ c->deq_rb_index = rb_tree_add_custom (rt, c->start_byte,
+ pointer_to_uword (c), f_pos_lt);
}
else
{
- cur = svm_fifo_find_node_rbtree (rt, start_pos);
+ cur = f_find_node_rbtree (rt, start_pos);
c = uword_to_pointer (cur->opaque, svm_fifo_chunk_t *);
- if (ref_pos > start_pos && c->start_byte > start_pos)
- {
- c = f->end_chunk;
- ASSERT (c->rb_index != RBTREE_TNIL_INDEX);
- }
+ ASSERT (f_pos_leq (c->start_byte, start_pos));
}
- if (svm_fifo_chunk_includes_pos (c, start_pos))
+ if (f_chunk_includes_pos (c, start_pos))
f->ooo_deq = c;
- if (svm_fifo_chunk_includes_pos (c, end_pos) && ref_pos < end_pos)
+ if (f_chunk_includes_pos (c, end_pos))
return;
do
{
c = c->next;
- if (c->rb_index != RBTREE_TNIL_INDEX)
+ if (!c || c->deq_rb_index != RBTREE_TNIL_INDEX)
break;
- c->rb_index = rb_tree_add2 (rt, c->start_byte, pointer_to_uword (c));
+ c->deq_rb_index = rb_tree_add_custom (rt, c->start_byte,
+ pointer_to_uword (c), f_pos_lt);
- if (svm_fifo_chunk_includes_pos (c, start_pos))
+ if (f_chunk_includes_pos (c, start_pos))
f->ooo_deq = c;
-
}
- while (!svm_fifo_chunk_includes_pos (c, end_pos));
+ while (!f_chunk_includes_pos (c, end_pos));
}
-void
-svm_fifo_ooo_deq_track (svm_fifo_t * f, u32 start_pos, u32 end_pos)
+static svm_fifo_chunk_t *
+f_lookup_clear_enq_chunks (svm_fifo_t * f, svm_fifo_chunk_t * start,
+ u32 end_pos)
{
- rb_tree_t *rt = &f->ooo_deq_lookup;
+ rb_tree_t *rt = &f->ooo_enq_lookup;
svm_fifo_chunk_t *c;
+ rb_node_t *n;
- if (svm_fifo_chunk_includes_pos (f->ooo_deq, end_pos)
- && start_pos < end_pos)
- return;
-
- c = f->ooo_deq->next;
- do
+ c = start;
+ while (c && !f_chunk_includes_pos (c, end_pos))
{
- ASSERT (c->rb_index == RBTREE_TNIL_INDEX);
- rb_tree_add2 (rt, c->start_byte, pointer_to_uword (c));
+ if (c->enq_rb_index != RBTREE_TNIL_INDEX)
+ {
+ n = rb_node (rt, c->enq_rb_index);
+ rb_tree_del_node (rt, n);
+ c->enq_rb_index = RBTREE_TNIL_INDEX;
+ }
c = c->next;
}
- while (!svm_fifo_chunk_includes_pos (c, end_pos));
+
+ /* No ooo segments left, so make sure the current chunk
+ * is not tracked in the enq rbtree */
+ if (f->ooos_list_head == OOO_SEGMENT_INVALID_INDEX
+ && c && c->enq_rb_index != RBTREE_TNIL_INDEX)
+ {
+ n = rb_node (rt, c->enq_rb_index);
+ rb_tree_del_node (rt, n);
+ c->enq_rb_index = RBTREE_TNIL_INDEX;
+ }
+
+ return c;
}
static svm_fifo_chunk_t *
-svm_fifo_lookup_clear_chunks (svm_fifo_t * f, rb_tree_t * rt,
- svm_fifo_chunk_t * start, u32 start_pos,
- u32 end_pos)
+f_lookup_clear_deq_chunks (svm_fifo_t * f, svm_fifo_chunk_t * start,
+ u32 end_pos)
{
+ rb_tree_t *rt = &f->ooo_deq_lookup;
svm_fifo_chunk_t *c;
rb_node_t *n;
- /* Nothing to do if still in the same chunk and not wrapped */
- if (svm_fifo_chunk_includes_pos (start, end_pos) && start_pos < end_pos)
- return start;
-
c = start;
- do
+ while (c && !f_chunk_includes_pos (c, end_pos))
{
- if (c->rb_index == RBTREE_TNIL_INDEX)
+ if (c->deq_rb_index != RBTREE_TNIL_INDEX)
{
- c = c->next;
- continue;
+ n = rb_node (rt, c->deq_rb_index);
+ rb_tree_del_node (rt, n);
+ c->deq_rb_index = RBTREE_TNIL_INDEX;
}
- n = rb_node (rt, c->rb_index);
- rb_tree_del_node (rt, n);
- c->rb_index = RBTREE_TNIL_INDEX;
c = c->next;
}
- while (!svm_fifo_chunk_includes_pos (c, end_pos));
return c;
}
-static inline void
-svm_fifo_grow (svm_fifo_t * f, svm_fifo_chunk_t * c)
-{
- svm_fifo_chunk_t *prev;
- u32 add_bytes = 0;
-
- if (!c)
- return;
-
- f->end_chunk->next = c;
- while (c)
- {
- add_bytes += c->length;
- prev = c;
- c = c->next;
- }
- f->end_chunk = prev;
- prev->next = f->start_chunk;
- f->size += add_bytes;
- f->nitems = f->size - 1;
- f->new_chunks = 0;
-}
-
-static void
-svm_fifo_try_grow (svm_fifo_t * f, u32 new_head)
-{
- if (new_head > f->tail)
- return;
-
- svm_fifo_grow (f, f->new_chunks);
- f->flags &= ~SVM_FIFO_F_GROW;
-}
-
void
svm_fifo_add_chunk (svm_fifo_t * f, svm_fifo_chunk_t * c)
{
svm_fifo_chunk_t *cur, *prev;
- /* Initialize rbtree if needed and add default chunk to it. Expectation is
- * that this is called with the heap where the rbtree's pool is pushed. */
- if (!(f->flags & SVM_FIFO_F_MULTI_CHUNK))
- {
- ASSERT (f->start_chunk->next == f->start_chunk);
- rb_tree_init (&f->ooo_enq_lookup);
- rb_tree_init (&f->ooo_deq_lookup);
- f->flags |= SVM_FIFO_F_MULTI_CHUNK;
- }
-
- /* If fifo is not wrapped, update the size now */
- if (!svm_fifo_is_wrapped (f))
- {
- /* Initialize chunks and add to lookup rbtree */
- cur = c;
- if (f->new_chunks)
- {
- prev = f->new_chunks;
- while (prev->next)
- prev = prev->next;
- prev->next = c;
- }
- else
- prev = f->end_chunk;
-
- while (cur)
- {
- cur->start_byte = prev->start_byte + prev->length;
- cur->rb_index = RBTREE_TNIL_INDEX;
- prev = cur;
- cur = cur->next;
- }
-
- ASSERT (!f->new_chunks);
- svm_fifo_grow (f, c);
- return;
- }
-
- /* Wrapped */
- if (f->flags & SVM_FIFO_F_SINGLE_THREAD_OWNED)
- {
- ASSERT (f->master_thread_index == os_get_thread_index ());
-
- if (!f->new_chunks && f->head_chunk != f->tail_chunk)
- {
- u32 head = 0, tail = 0;
- f_load_head_tail_cons (f, &head, &tail);
-
- svm_fifo_chunk_t *tmp = f->tail_chunk->next;
-
- prev = f->tail_chunk;
- u32 add_bytes = 0;
- cur = prev->next;
- while (cur != f->start_chunk)
- {
- /* remove any existing rb_tree entry */
- if (cur->rb_index != RBTREE_TNIL_INDEX)
- {
- rb_tree_del (&f->ooo_enq_lookup, cur->start_byte);
- rb_tree_del (&f->ooo_deq_lookup, cur->start_byte);
- }
- cur->rb_index = RBTREE_TNIL_INDEX;
- cur = cur->next;
- }
-
- /* insert new chunk after the tail_chunk */
- f->tail_chunk->next = c;
- while (c)
- {
- add_bytes += c->length;
- c->start_byte = prev->start_byte + prev->length;
- cur->rb_index = RBTREE_TNIL_INDEX;
-
- prev = c;
- c = c->next;
- }
- prev->next = tmp;
-
- /* shift existing chunks along */
- cur = tmp;
- while (cur != f->start_chunk)
- {
- cur->start_byte = prev->start_byte + prev->length;
- prev = cur;
- cur = cur->next;
- }
-
- f->size += add_bytes;
- f->nitems = f->size - 1;
- f->new_chunks = 0;
- head += add_bytes;
-
- clib_atomic_store_rel_n (&f->head, head);
- ASSERT (svm_fifo_is_sane (f));
-
- return;
- }
- }
-
- /* Wrapped, and optimization of single-thread-owned fifo cannot be applied */
- /* Initialize chunks and add to lookup rbtree */
cur = c;
- if (f->new_chunks)
- {
- prev = f->new_chunks;
- while (prev->next)
- prev = prev->next;
- prev->next = c;
- }
- else
- prev = f->end_chunk;
+ prev = f->end_chunk;
while (cur)
{
cur->start_byte = prev->start_byte + prev->length;
- cur->rb_index = RBTREE_TNIL_INDEX;
- prev = cur;
- cur = cur->next;
- }
-
- /* Postpone size update */
- if (!f->new_chunks)
- {
- f->new_chunks = c;
- f->flags |= SVM_FIFO_F_GROW;
- }
-}
-
-/**
- * Removes chunks that are after fifo end byte
- */
-svm_fifo_chunk_t *
-svm_fifo_collect_chunks (svm_fifo_t * f)
-{
- svm_fifo_chunk_t *list, *cur;
-
- f->flags &= ~SVM_FIFO_F_COLLECT_CHUNKS;
-
- list = f->new_chunks;
- f->new_chunks = 0;
- cur = list;
- while (cur)
- {
- if (cur->rb_index != RBTREE_TNIL_INDEX)
- {
- rb_tree_del (&f->ooo_enq_lookup, cur->start_byte);
- rb_tree_del (&f->ooo_deq_lookup, cur->start_byte);
- }
- cur = cur->next;
- }
-
- return list;
-}
-
-void
-svm_fifo_try_shrink (svm_fifo_t * f, u32 head, u32 tail)
-{
- u32 len_to_shrink = 0, tail_pos, len, last_pos;
- svm_fifo_chunk_t *cur, *prev, *next, *start;
-
- tail_pos = tail;
- if (f->ooos_list_head != OOO_SEGMENT_INVALID_INDEX)
- {
- ooo_segment_t *last = ooo_segment_last (f);
- tail_pos = ooo_segment_end_pos (f, last);
- }
-
- if (f->size_decrement)
- {
- /* Figure out available free space considering that there may be
- * ooo segments */
- len = clib_min (f->size_decrement, f_free_count (f, head, tail_pos));
- f->nitems -= len;
- f->size_decrement -= len;
- }
-
- /* Remove tail chunks if the following hold:
- * - not wrapped
- * - last used byte less than start of last chunk
- */
- if (tail_pos >= head && tail_pos < f->end_chunk->start_byte)
- {
- /* Lookup the last position not to be removed. Since size still needs
- * to be nitems + 1, nitems must fall within the usable space. Also,
- * first segment is not removable, so tail_pos can be 0. */
- last_pos = tail_pos > 0 ? tail_pos - 1 : tail_pos;
- prev = svm_fifo_find_chunk (f, clib_max (f->nitems, last_pos));
- next = prev->next;
- /* If tail_pos is first position in next, skip the chunk, otherwise,
- * we must update the tail and, if fifo size is 0, even the head.
- * We should not invalidate the tail for the caller and must not change
- * consumer owned variables from code that's typically called by the
- * producer */
- if (next->start_byte == tail_pos)
- {
- prev = next;
- next = next->next;
- }
- while (next != f->start_chunk)
- {
- cur = next;
- next = cur->next;
- len_to_shrink += cur->length;
- }
- if (len_to_shrink)
- {
- f->size -= len_to_shrink;
- start = prev->next;
- prev->next = f->start_chunk;
- f->end_chunk = prev;
- cur->next = f->new_chunks;
- f->new_chunks = start;
- }
- }
-
- if (!f->size_decrement && f->size == f->nitems + 1)
- {
- f->flags &= ~SVM_FIFO_F_SHRINK;
- f->flags |= SVM_FIFO_F_COLLECT_CHUNKS;
- if (f->start_chunk == f->start_chunk->next)
- f->flags &= ~SVM_FIFO_F_MULTI_CHUNK;
- }
-}
+ cur->enq_rb_index = RBTREE_TNIL_INDEX;
+ cur->deq_rb_index = RBTREE_TNIL_INDEX;
-/**
- * Request to reduce fifo size by amount of bytes
- */
-int
-svm_fifo_reduce_size (svm_fifo_t * f, u32 len, u8 try_shrink)
-{
- svm_fifo_chunk_t *cur;
- u32 actual_len = 0;
-
- /* Abort if trying to reduce by more than fifo size or if
- * fifo is undergoing resizing already */
- if (len >= f->size || f->size > f->nitems + 1
- || (f->flags & SVM_FIFO_F_SHRINK) || (f->flags & SVM_FIFO_F_GROW))
- return 0;
-
- /* last chunk that will not be removed */
- cur = svm_fifo_find_chunk (f, f->nitems - len);
-
- /* sum length of chunks that will be removed */
- cur = cur->next;
- while (cur != f->start_chunk)
- {
- actual_len += cur->length;
+ prev = cur;
cur = cur->next;
}
- ASSERT (actual_len <= len);
- if (!actual_len)
- return 0;
-
- f->size_decrement = actual_len;
- f->flags |= SVM_FIFO_F_SHRINK;
+ prev->next = 0;
+ f->end_chunk->next = c;
+ f->end_chunk = prev;
- if (try_shrink)
- {
- u32 head, tail;
- f_load_head_tail_prod (f, &head, &tail);
- svm_fifo_try_shrink (f, head, tail);
- }
+ if (!f->tail_chunk)
+ f->tail_chunk = c;
- return actual_len;
+ return;
}
void
@@ -1054,9 +803,13 @@ svm_fifo_overwrite_head (svm_fifo_t * f, u8 * src, u32 len)
u32 head, tail, head_idx;
svm_fifo_chunk_t *c;
- ASSERT (len <= f->nitems);
+ ASSERT (len <= f->size);
f_load_head_tail_cons (f, &head, &tail);
+
+ if (!f->head_chunk)
+ f->head_chunk = svm_fifo_find_chunk (f, head);
+
c = f->head_chunk;
head_idx = head - c->start_byte;
n_chunk = c->length - head_idx;
@@ -1064,30 +817,65 @@ svm_fifo_overwrite_head (svm_fifo_t * f, u8 * src, u32 len)
clib_memcpy_fast (&c->data[head_idx], src, len);
else
{
+ ASSERT (len - n_chunk <= c->next->length);
clib_memcpy_fast (&c->data[head_idx], src, n_chunk);
clib_memcpy_fast (&c->next->data[0], src + n_chunk, len - n_chunk);
}
}
+static int
+f_try_grow (svm_fifo_t * f, u32 head, u32 tail, u32 len)
+{
+ svm_fifo_chunk_t *c;
+ u32 alloc_size, free_alloced;
+
+ free_alloced = f_chunk_end (f->end_chunk) - tail;
+ ASSERT (free_alloced < len);
+
+ alloc_size = clib_min (f->min_alloc, f->size - (tail - head));
+ alloc_size = clib_max (alloc_size, len - free_alloced);
+
+ c = fsh_alloc_chunk (f->fs_hdr, f->slice_index, alloc_size);
+ if (PREDICT_FALSE (!c))
+ return -1;
+
+ svm_fifo_add_chunk (f, c);
+ return 0;
+}
+
int
svm_fifo_enqueue (svm_fifo_t * f, u32 len, const u8 * src)
{
u32 tail, head, free_count;
+ svm_fifo_chunk_t *old_tail_c;
+
+ f->ooos_newest = OOO_SEGMENT_INVALID_INDEX;
f_load_head_tail_prod (f, &head, &tail);
/* free space in fifo can only increase during enqueue: SPSC */
free_count = f_free_count (f, head, tail);
- f->ooos_newest = OOO_SEGMENT_INVALID_INDEX;
-
if (PREDICT_FALSE (free_count == 0))
return SVM_FIFO_EFULL;
/* number of bytes we're going to copy */
len = clib_min (free_count, len);
+
+ if (f_pos_gt (tail + len, f_chunk_end (f->end_chunk)))
+ {
+ if (PREDICT_FALSE (f_try_grow (f, head, tail, len)))
+ {
+ len = f_chunk_end (f->end_chunk) - tail;
+ if (!len)
+ return SVM_FIFO_EGROW;
+ }
+ }
+
+ old_tail_c = f->tail_chunk;
+
svm_fifo_copy_to_chunk (f, f->tail_chunk, tail, src, len, &f->tail_chunk);
- tail = (tail + len) % f->size;
+ tail = tail + len;
svm_fifo_trace_add (f, head, len, 2);
@@ -1095,10 +883,9 @@ svm_fifo_enqueue (svm_fifo_t * f, u32 len, const u8 * src)
if (PREDICT_FALSE (f->ooos_list_head != OOO_SEGMENT_INVALID_INDEX))
{
len += ooo_segment_try_collect (f, len, &tail);
- if (f->flags & SVM_FIFO_F_MULTI_CHUNK)
- f->tail_chunk = svm_fifo_lookup_clear_chunks (f, &f->ooo_enq_lookup,
- f->tail_chunk, f->tail,
- tail);
+ /* Tail chunk might've changed even if nothing was collected */
+ f->tail_chunk = f_lookup_clear_enq_chunks (f, old_tail_c, tail);
+ f->ooo_enq = 0;
}
/* store-rel: producer owned index (paired with load-acq in consumer) */
@@ -1117,30 +904,33 @@ svm_fifo_enqueue (svm_fifo_t * f, u32 len, const u8 * src)
int
svm_fifo_enqueue_with_offset (svm_fifo_t * f, u32 offset, u32 len, u8 * src)
{
- u32 tail, head, free_count, tail_idx;
+ u32 tail, head, free_count, enq_pos;
f_load_head_tail_prod (f, &head, &tail);
- if (PREDICT_FALSE (f->flags & SVM_FIFO_F_SHRINK))
- svm_fifo_try_shrink (f, head, tail);
-
/* free space in fifo can only increase during enqueue: SPSC */
free_count = f_free_count (f, head, tail);
+ f->ooos_newest = OOO_SEGMENT_INVALID_INDEX;
/* will this request fit? */
if ((len + offset) > free_count)
return SVM_FIFO_EFULL;
- f->ooos_newest = OOO_SEGMENT_INVALID_INDEX;
+ enq_pos = tail + offset;
+
+ if (f_pos_gt (enq_pos + len, f_chunk_end (f->end_chunk)))
+ {
+ if (PREDICT_FALSE (f_try_grow (f, head, tail, offset + len)))
+ return SVM_FIFO_EGROW;
+ }
+
svm_fifo_trace_add (f, offset, len, 1);
ooo_segment_add (f, offset, head, tail, len);
- tail_idx = (tail + offset) % f->size;
- if (f->flags & SVM_FIFO_F_MULTI_CHUNK)
- svm_fifo_update_ooo_enq (f, f->tail, tail_idx,
- (tail_idx + len) % f->size);
+ if (!f->ooo_enq || !f_chunk_includes_pos (f->ooo_enq, enq_pos))
+ f_update_ooo_enq (f, enq_pos, enq_pos + len);
- svm_fifo_copy_to_chunk (f, f->ooo_enq, tail_idx, src, len, &f->ooo_enq);
+ svm_fifo_copy_to_chunk (f, f->ooo_enq, enq_pos, src, len, &f->ooo_enq);
return 0;
}
@@ -1156,17 +946,74 @@ svm_fifo_enqueue_nocopy (svm_fifo_t * f, u32 len)
ASSERT (len <= svm_fifo_max_enqueue_prod (f));
/* load-relaxed: producer owned index */
tail = f->tail;
- tail = (tail + len) % f->size;
+ tail = tail + len;
- if (f->flags & SVM_FIFO_F_MULTI_CHUNK)
- f->tail_chunk = svm_fifo_lookup_clear_chunks (f, &f->ooo_enq_lookup,
- f->tail_chunk, f->tail,
- tail);
+ if (rb_tree_is_init (&f->ooo_enq_lookup))
+ {
+ f->tail_chunk = f_lookup_clear_enq_chunks (f, f->tail_chunk, tail);
+ f->ooo_enq = 0;
+ }
+ else
+ {
+ f->tail_chunk = svm_fifo_find_next_chunk (f, f->tail_chunk, tail);
+ }
/* store-rel: producer owned index (paired with load-acq in consumer) */
clib_atomic_store_rel_n (&f->tail, tail);
}
+always_inline svm_fifo_chunk_t *
+f_unlink_chunks (svm_fifo_t * f, u32 end_pos, u8 maybe_ooo)
+{
+ svm_fifo_chunk_t *start, *prev = 0, *c;
+ rb_tree_t *rt;
+ rb_node_t *n;
+
+ ASSERT (!f_chunk_includes_pos (f->start_chunk, end_pos));
+
+ if (maybe_ooo)
+ rt = &f->ooo_deq_lookup;
+
+ c = f->start_chunk;
+
+ do
+ {
+ if (maybe_ooo && c->deq_rb_index != RBTREE_TNIL_INDEX)
+ {
+ n = rb_node (rt, c->deq_rb_index);
+ ASSERT (n == f_find_node_rbtree (rt, c->start_byte));
+ rb_tree_del_node (rt, n);
+ c->deq_rb_index = RBTREE_TNIL_INDEX;
+ }
+ if (!c->next)
+ break;
+ prev = c;
+ c = c->next;
+ }
+ while (!f_chunk_includes_pos (c, end_pos));
+
+ if (maybe_ooo)
+ {
+ if (f->ooo_deq && f_pos_lt (f->ooo_deq->start_byte, f_chunk_end (c)))
+ f->ooo_deq = 0;
+ }
+ else
+ {
+ if (PREDICT_FALSE (f->ooo_deq != 0))
+ f->ooo_deq = 0;
+ }
+
+ /* Avoid unlinking the last chunk */
+ if (!prev)
+ return 0;
+
+ prev->next = 0;
+ start = f->start_chunk;
+ f->start_chunk = c;
+
+ return start;
+}
+
int
svm_fifo_dequeue (svm_fifo_t * f, u32 len, u8 * dst)
{
@@ -1181,11 +1028,16 @@ svm_fifo_dequeue (svm_fifo_t * f, u32 len, u8 * dst)
return SVM_FIFO_EEMPTY;
len = clib_min (cursize, len);
+
+ if (!f->head_chunk)
+ f->head_chunk = svm_fifo_find_chunk (f, head);
+
svm_fifo_copy_from_chunk (f, f->head_chunk, head, dst, len, &f->head_chunk);
- head = (head + len) % f->size;
+ head = head + len;
- if (PREDICT_FALSE (f->flags & SVM_FIFO_F_GROW))
- svm_fifo_try_grow (f, head);
+ if (f_pos_geq (head, f_chunk_end (f->start_chunk)))
+ fsh_collect_chunks (f->fs_hdr, f->slice_index,
+ f_unlink_chunks (f, head, 0));
/* store-rel: consumer owned index (paired with load-acq in producer) */
clib_atomic_store_rel_n (&f->head, head);
@@ -1207,10 +1059,10 @@ svm_fifo_peek (svm_fifo_t * f, u32 offset, u32 len, u8 * dst)
return SVM_FIFO_EEMPTY;
len = clib_min (cursize - offset, len);
- head_idx = (head + offset) % f->size;
+ head_idx = head + offset;
- if (f->flags & SVM_FIFO_F_MULTI_CHUNK)
- svm_fifo_update_ooo_deq (f, head, head_idx, (head_idx + len) % f->size);
+ if (!f->ooo_deq || !f_chunk_includes_pos (f->ooo_deq, head_idx))
+ f_update_ooo_deq (f, head_idx, head_idx + len);
svm_fifo_copy_from_chunk (f, f->ooo_deq, head_idx, dst, len, &f->ooo_deq);
return len;
@@ -1234,15 +1086,15 @@ svm_fifo_dequeue_drop (svm_fifo_t * f, u32 len)
svm_fifo_trace_add (f, tail, total_drop_bytes, 3);
/* move head */
- head = (head + total_drop_bytes) % f->size;
-
- if (f->flags & SVM_FIFO_F_MULTI_CHUNK)
- f->head_chunk = svm_fifo_lookup_clear_chunks (f, &f->ooo_deq_lookup,
- f->head_chunk, f->head,
- head);
+ head = head + total_drop_bytes;
- if (PREDICT_FALSE (f->flags & SVM_FIFO_F_GROW))
- svm_fifo_try_grow (f, head);
+ if (f_pos_geq (head, f_chunk_end (f->start_chunk)))
+ {
+ fsh_collect_chunks (f->fs_hdr, f->slice_index,
+ f_unlink_chunks (f, head, 1));
+ f->head_chunk =
+ f_chunk_includes_pos (f->start_chunk, head) ? f->start_chunk : 0;
+ }
/* store-rel: consumer owned index (paired with load-acq in producer) */
clib_atomic_store_rel_n (&f->head, head);
@@ -1250,25 +1102,48 @@ svm_fifo_dequeue_drop (svm_fifo_t * f, u32 len)
return total_drop_bytes;
}
+/**
+ * Drop all data from fifo
+ *
+ * Should be called only from vpp side because of lookup cleanup
+ */
void
svm_fifo_dequeue_drop_all (svm_fifo_t * f)
{
- /* consumer foreign index */
- u32 tail = clib_atomic_load_acq_n (&f->tail);
+ u32 head, tail;
+
+ f_load_head_tail_all_acq (f, &head, &tail);
- if (f->flags & SVM_FIFO_F_MULTI_CHUNK)
- f->head_chunk = svm_fifo_lookup_clear_chunks (f, &f->ooo_deq_lookup,
- f->head_chunk, tail,
- tail - 1);
+ if (!f->head_chunk || !f_chunk_includes_pos (f->head_chunk, head))
+ f->head_chunk = svm_fifo_find_chunk (f, head);
- if (PREDICT_FALSE (f->flags & SVM_FIFO_F_GROW))
- svm_fifo_try_grow (f, tail);
+ f->head_chunk = f_lookup_clear_deq_chunks (f, f->head_chunk, tail);
+
+ if (f_pos_geq (tail, f_chunk_end (f->start_chunk)))
+ fsh_collect_chunks (f->fs_hdr, f->slice_index,
+ f_unlink_chunks (f, tail, 0));
/* store-rel: consumer owned index (paired with load-acq in producer) */
clib_atomic_store_rel_n (&f->head, tail);
}
int
+svm_fifo_fill_chunk_list (svm_fifo_t * f)
+{
+ u32 head, tail;
+
+ f_load_head_tail_prod (f, &head, &tail);
+
+ if (f_chunk_end (f->end_chunk) - head >= f->size)
+ return 0;
+
+ if (f_try_grow (f, head, tail, f->size - (tail - head)))
+ return SVM_FIFO_EGROW;
+
+ return 0;
+}
+
+int
svm_fifo_segments (svm_fifo_t * f, svm_fifo_seg_t * fs)
{
u32 cursize, head, tail, head_idx;
@@ -1309,7 +1184,7 @@ svm_fifo_segments_free (svm_fifo_t * f, svm_fifo_seg_t * fs)
head = f->head;
ASSERT (fs[0].data == f->head_chunk->data + head);
- head = (head + fs[0].len + fs[1].len) % f->size;
+ head = (head + fs[0].len + fs[1].len);
/* store-rel: consumer owned index (paired with load-acq in producer) */
clib_atomic_store_rel_n (&f->head, head);
}
@@ -1325,6 +1200,10 @@ void
svm_fifo_clone (svm_fifo_t * df, svm_fifo_t * sf)
{
u32 head, tail;
+
+ /* Support only single chunk clones for now */
+ ASSERT (svm_fifo_n_chunks (sf) == 1);
+
clib_memcpy_fast (df->head_chunk->data, sf->head_chunk->data, sf->size);
f_load_head_tail_all_acq (sf, &head, &tail);
@@ -1350,20 +1229,17 @@ svm_fifo_first_ooo_segment (svm_fifo_t * f)
void
svm_fifo_init_pointers (svm_fifo_t * f, u32 head, u32 tail)
{
- head = head % f->size;
- tail = tail % f->size;
+ svm_fifo_chunk_t *c;
+
clib_atomic_store_rel_n (&f->head, head);
clib_atomic_store_rel_n (&f->tail, tail);
- if (f->flags & SVM_FIFO_F_MULTI_CHUNK)
- {
- svm_fifo_chunk_t *c;
- c = svm_fifo_find_chunk (f, head);
- ASSERT (c != 0);
- f->head_chunk = f->ooo_deq = c;
- c = svm_fifo_find_chunk (f, tail);
- ASSERT (c != 0);
- f->tail_chunk = f->ooo_enq = c;
- }
+
+ c = svm_fifo_find_chunk (f, head);
+ ASSERT (c != 0);
+ f->head_chunk = f->ooo_deq = c;
+ c = svm_fifo_find_chunk (f, tail);
+ ASSERT (c != 0);
+ f->tail_chunk = f->ooo_enq = c;
}
void
@@ -1392,20 +1268,54 @@ svm_fifo_del_subscriber (svm_fifo_t * f, u8 subscriber)
u8
svm_fifo_is_sane (svm_fifo_t * f)
{
- if (f->size - 1 != f->nitems && !(f->flags & SVM_FIFO_F_SHRINK))
- return 0;
- if (!svm_fifo_chunk_includes_pos (f->head_chunk, f->head))
+ svm_fifo_chunk_t *tmp;
+
+ if (f->head_chunk && !f_chunk_includes_pos (f->head_chunk, f->head))
return 0;
- if (!svm_fifo_chunk_includes_pos (f->tail_chunk, f->tail))
+ if (f->tail_chunk && !f_chunk_includes_pos (f->tail_chunk, f->tail))
return 0;
+ if (f->ooo_deq)
+ {
+ if (rb_tree_is_init (&f->ooo_deq_lookup))
+ {
+ if (f_pos_lt (f->ooo_deq->start_byte, f->start_chunk->start_byte)
+ || f_pos_gt (f->ooo_deq->start_byte,
+ f_chunk_end (f->end_chunk)))
+ return 0;
- if (f->start_chunk->next != f->start_chunk)
+ tmp = f_find_chunk_rbtree (&f->ooo_deq_lookup,
+ f->ooo_deq->start_byte);
+ }
+ else
+ tmp = svm_fifo_find_chunk (f, f->ooo_deq->start_byte);
+ if (tmp != f->ooo_deq)
+ return 0;
+ }
+ if (f->ooo_enq)
{
- svm_fifo_chunk_t *c, *prev = 0, *tmp;
- u32 size = 0;
+ if (rb_tree_is_init (&f->ooo_enq_lookup))
+ {
+ if (f_pos_lt (f->ooo_enq->start_byte, f->start_chunk->start_byte)
+ || f_pos_gt (f->ooo_enq->start_byte,
+ f_chunk_end (f->end_chunk)))
+ return 0;
- if (!(f->flags & SVM_FIFO_F_MULTI_CHUNK))
+ tmp = f_find_chunk_rbtree (&f->ooo_enq_lookup,
+ f->ooo_enq->start_byte);
+ }
+ else
+ {
+ tmp = svm_fifo_find_next_chunk (f, f->tail_chunk,
+ f->ooo_enq->start_byte);
+ }
+ if (tmp != f->ooo_enq)
return 0;
+ }
+
+ if (f->start_chunk->next)
+ {
+ svm_fifo_chunk_t *c, *prev = 0, *tmp;
+ u32 chunks_bytes = 0;
c = f->start_chunk;
do
@@ -1416,75 +1326,61 @@ svm_fifo_is_sane (svm_fifo_t * f)
if (prev && (prev->start_byte + prev->length != c->start_byte))
return 0;
- if (c->rb_index != RBTREE_TNIL_INDEX)
+ if (c->enq_rb_index != RBTREE_TNIL_INDEX)
{
- u8 found = 0;
-
- tmp = svm_fifo_find_chunk_rbtree (&f->ooo_enq_lookup,
- c->start_byte);
+ tmp = f_find_chunk_rbtree (&f->ooo_enq_lookup, c->start_byte);
if (tmp)
{
- found = 1;
if (tmp != c)
return 0;
}
-
- tmp = svm_fifo_find_chunk_rbtree (&f->ooo_deq_lookup,
- c->start_byte);
+ }
+ if (c->deq_rb_index != RBTREE_TNIL_INDEX)
+ {
+ tmp = f_find_chunk_rbtree (&f->ooo_deq_lookup, c->start_byte);
if (tmp)
{
- if (found)
- return 0;
-
- found = 1;
if (tmp != c)
return 0;
}
- if (!found)
- return 0;
}
- size += c->length;
+ chunks_bytes += c->length;
prev = c;
c = c->next;
}
- while (c != f->start_chunk);
+ while (c);
- if (size != f->size)
+ if (chunks_bytes < f->tail - f->head)
return 0;
}
return 1;
}
-u8
-svm_fifo_set_single_thread_owned (svm_fifo_t * f)
+u32
+svm_fifo_n_chunks (svm_fifo_t * f)
{
- if (f->flags & SVM_FIFO_F_SINGLE_THREAD_OWNED)
- {
- if (f->master_thread_index == os_get_thread_index ())
- {
- /* just a duplicate call */
- return 0;
- }
+ svm_fifo_chunk_t *c;
+ int n_chunks = 0;
- /* already owned by another thread */
- return 1;
+ c = f->start_chunk;
+ while (c)
+ {
+ n_chunks++;
+ c = c->next;
}
- f->flags |= SVM_FIFO_F_SINGLE_THREAD_OWNED;
- return 0;
+ return n_chunks;
}
u8 *
format_ooo_segment (u8 * s, va_list * args)
{
- svm_fifo_t *f = va_arg (*args, svm_fifo_t *);
+ svm_fifo_t __clib_unused *f = va_arg (*args, svm_fifo_t *);
ooo_segment_t *seg = va_arg (*args, ooo_segment_t *);
- u32 normalized_start = (seg->start + f->nitems - f->tail) % f->size;
- s = format (s, "[%u, %u], len %u, next %d, prev %d", normalized_start,
- (normalized_start + seg->length) % f->size, seg->length,
- seg->next, seg->prev);
+ s = format (s, "[%u, %u], len %u, next %d, prev %d", seg->start,
+ seg->start + seg->length, seg->length, seg->next, seg->prev);
return s;
}
@@ -1532,9 +1428,10 @@ svm_fifo_replay (u8 * s, svm_fifo_t * f, u8 no_read, u8 verbose)
trace_len = 0;
#endif
- dummy_fifo = svm_fifo_create (f->size);
- clib_memset (f->head_chunk->data, 0xFF, f->nitems);
- vec_validate (data, f->nitems);
+ dummy_fifo = svm_fifo_alloc (f->size);
+ svm_fifo_init (f, f->size);
+ clib_memset (f->head_chunk->data, 0xFF, f->size);
+ vec_validate (data, f->size);
for (i = 0; i < vec_len (data); i++)
data[i] = i;
@@ -1545,7 +1442,7 @@ svm_fifo_replay (u8 * s, svm_fifo_t * f, u8 no_read, u8 verbose)
{
if (verbose)
s = format (s, "adding [%u, %u]:", trace[i].offset,
- (trace[i].offset + trace[i].len) % dummy_fifo->size);
+ (trace[i].offset + trace[i].len));
svm_fifo_enqueue_with_offset (dummy_fifo, trace[i].offset,
trace[i].len, &data[offset]);
}
@@ -1600,11 +1497,10 @@ format_svm_fifo (u8 * s, va_list * args)
return s;
indent = format_get_indent (s);
- s = format (s, "cursize %u nitems %u has_event %d\n",
- svm_fifo_max_dequeue (f), f->nitems, f->has_event);
+ s = format (s, "cursize %u nitems %u has_event %d min_alloc %u\n",
+ svm_fifo_max_dequeue (f), f->size, f->has_event, f->min_alloc);
s = format (s, "%Uhead %u tail %u segment manager %u\n", format_white_space,
- indent, (f->head % f->size), (f->tail % f->size),
- f->segment_manager);
+ indent, f->head, f->tail, f->segment_manager);
if (verbose > 1)
s = format (s, "%Uvpp session %d thread %d app session %d thread %d\n",
diff --git a/src/svm/svm_fifo.h b/src/svm/svm_fifo.h
index 2b6e8542cdf..8d5e4803360 100644
--- a/src/svm/svm_fifo.h
+++ b/src/svm/svm_fifo.h
@@ -23,22 +23,11 @@
#include <vppinfra/vec.h>
#include <vppinfra/pool.h>
#include <vppinfra/format.h>
-#include <vppinfra/rbtree.h>
+#include <svm/fifo_types.h>
-/** Out-of-order segment */
-typedef struct
-{
- u32 next; /**< Next linked-list element pool index */
- u32 prev; /**< Previous linked-list element pool index */
- u32 start; /**< Start of segment, normalized*/
- u32 length; /**< Length of segment */
-} ooo_segment_t;
-
-#define SVM_FIFO_TRACE (0)
#define OOO_SEGMENT_INVALID_INDEX ((u32)~0)
#define SVM_FIFO_INVALID_SESSION_INDEX ((u32)~0)
#define SVM_FIFO_INVALID_INDEX ((u32)~0)
-#define SVM_FIFO_MAX_EVT_SUBSCRIBERS 7
typedef enum svm_fifo_deq_ntf_
{
@@ -48,85 +37,16 @@ typedef enum svm_fifo_deq_ntf_
SVM_FIFO_WANT_DEQ_NOTIF_IF_EMPTY = 4, /**< Notify on transition to empty */
} svm_fifo_deq_ntf_t;
-typedef struct
-{
- u32 offset;
- u32 len;
- u32 action;
-} svm_fifo_trace_elem_t;
-
-typedef struct svm_fifo_chunk_
-{
- u32 start_byte; /**< chunk start byte */
- u32 length; /**< length of chunk in bytes */
- struct svm_fifo_chunk_ *next; /**< pointer to next chunk in linked-lists */
- rb_node_index_t rb_index; /**< node index if chunk in rbtree */
- u8 data[0]; /**< start of chunk data */
-} svm_fifo_chunk_t;
-
typedef enum svm_fifo_flag_
{
- SVM_FIFO_F_MULTI_CHUNK = 1 << 0,
- SVM_FIFO_F_GROW = 1 << 1,
- SVM_FIFO_F_SHRINK = 1 << 2,
- SVM_FIFO_F_COLLECT_CHUNKS = 1 << 3,
- SVM_FIFO_F_LL_TRACKED = 1 << 4,
- SVM_FIFO_F_SINGLE_THREAD_OWNED = 1 << 5,
+ SVM_FIFO_F_LL_TRACKED = 1 << 0,
} svm_fifo_flag_t;
-typedef struct _svm_fifo
-{
- CLIB_CACHE_LINE_ALIGN_MARK (shared_first);
- u32 size; /**< size of the fifo in bytes */
- u32 nitems; /**< usable size (size-1) */
- svm_fifo_chunk_t *start_chunk;/**< first chunk in fifo chunk list */
- svm_fifo_chunk_t *end_chunk; /**< end chunk in fifo chunk list */
- rb_tree_t ooo_enq_lookup; /**< rbtree for ooo enq chunk lookup */
- rb_tree_t ooo_deq_lookup; /**< rbtree for ooo deq chunk lookup */
- u8 flags; /**< fifo flags */
- u8 slice_index; /**< segment slice for fifo */
-
- CLIB_CACHE_LINE_ALIGN_MARK (shared_second);
- volatile u32 has_event; /**< non-zero if deq event exists */
- u32 master_session_index; /**< session layer session index */
- u32 client_session_index; /**< app session index */
- u8 master_thread_index; /**< session layer thread index */
- u8 client_thread_index; /**< app worker index */
- i8 refcnt; /**< reference count */
- u32 segment_manager; /**< session layer segment manager index */
- u32 segment_index; /**< segment index in segment manager */
- struct _svm_fifo *next; /**< next in freelist/active chain */
- struct _svm_fifo *prev; /**< prev in active chain */
- svm_fifo_chunk_t *new_chunks; /**< chunks yet to be added to list */
- u32 size_decrement; /**< bytes to remove from fifo */
-
- CLIB_CACHE_LINE_ALIGN_MARK (consumer);
- u32 head; /**< fifo head position/byte */
- svm_fifo_chunk_t *head_chunk; /**< tracks chunk where head lands */
- svm_fifo_chunk_t *ooo_deq; /**< last chunk used for ooo dequeue */
- volatile u32 want_deq_ntf; /**< producer wants nudge */
- volatile u32 has_deq_ntf;
-
- CLIB_CACHE_LINE_ALIGN_MARK (producer);
- u32 tail; /**< fifo tail position/byte */
- u32 ooos_list_head; /**< Head of out-of-order linked-list */
- svm_fifo_chunk_t *tail_chunk; /**< tracks chunk where tail lands */
- svm_fifo_chunk_t *ooo_enq; /**< last chunk used for ooo enqueue */
- ooo_segment_t *ooo_segments; /**< Pool of ooo segments */
- u32 ooos_newest; /**< Last segment to have been updated */
- volatile u8 n_subscribers; /**< Number of subscribers for io events */
- u8 subscribers[SVM_FIFO_MAX_EVT_SUBSCRIBERS];
-
-#if SVM_FIFO_TRACE
- svm_fifo_trace_elem_t *trace;
-#endif
-
-} svm_fifo_t;
-
typedef enum
{
SVM_FIFO_EFULL = -2,
SVM_FIFO_EEMPTY = -3,
+ SVM_FIFO_EGROW = -4,
} svm_fifo_err_t;
typedef struct svm_fifo_seg_
@@ -193,55 +113,63 @@ f_load_head_tail_all_acq (svm_fifo_t * f, u32 * head, u32 * tail)
}
/**
- * Distance to a from b, i.e., a - b in the fifo
+ * Fifo current size, i.e., number of bytes enqueued
*
* Internal function.
*/
static inline u32
-f_distance_to (svm_fifo_t * f, u32 a, u32 b)
+f_cursize (svm_fifo_t * f, u32 head, u32 tail)
{
- return ((f->size + a - b) % f->size);
+ return tail - head;
}
/**
- * Distance from a to b, i.e., b - a in the fifo
+ * Fifo free bytes, i.e., number of free bytes
*
- * Internal function.
+ * Internal function
*/
static inline u32
-f_distance_from (svm_fifo_t * f, u32 a, u32 b)
+f_free_count (svm_fifo_t * f, u32 head, u32 tail)
{
- return ((f->size + b - a) % f->size);
+ return (f->size - f_cursize (f, head, tail));
}
-/**
- * Fifo current size, i.e., number of bytes enqueued
- *
- * Internal function.
- */
-static inline u32
-f_cursize (svm_fifo_t * f, u32 head, u32 tail)
+always_inline u32
+f_chunk_end (svm_fifo_chunk_t * c)
{
- return (head <= tail ? tail - head : f->size + tail - head);
+ return c->start_byte + c->length;
}
-/**
- * Fifo free bytes, i.e., number of free bytes
- *
- * Internal function
- */
-static inline u32
-f_free_count (svm_fifo_t * f, u32 head, u32 tail)
+always_inline int
+f_pos_lt (u32 a, u32 b)
{
- return (f->nitems - f_cursize (f, head, tail));
+ return ((i32) (a - b) < 0);
}
-/**
- * Try to shrink fifo size.
- *
- * Internal function.
- */
-void svm_fifo_try_shrink (svm_fifo_t * f, u32 head, u32 tail);
+always_inline int
+f_pos_leq (u32 a, u32 b)
+{
+ return ((i32) (a - b) <= 0);
+}
+
+always_inline int
+f_pos_gt (u32 a, u32 b)
+{
+ return ((i32) (a - b) > 0);
+}
+
+always_inline int
+f_pos_geq (u32 a, u32 b)
+{
+ return ((i32) (a - b) >= 0);
+}
+
+always_inline u8
+f_chunk_includes_pos (svm_fifo_chunk_t * c, u32 pos)
+{
+ return (f_pos_geq (pos, c->start_byte)
+ && f_pos_lt (pos, c->start_byte + c->length));
+}
/**
* Create fifo of requested size
@@ -252,7 +180,7 @@ void svm_fifo_try_shrink (svm_fifo_t * f, u32 head, u32 tail);
* rounded to the next highest power-of-two value.
* @return pointer to new fifo
*/
-svm_fifo_t *svm_fifo_create (u32 size);
+svm_fifo_t *svm_fifo_alloc (u32 size);
/**
* Initialize fifo
*
@@ -261,12 +189,6 @@ svm_fifo_t *svm_fifo_create (u32 size);
*/
void svm_fifo_init (svm_fifo_t * f, u32 size);
/**
- * Initialize fifo chunks and rbtree
- *
- * @param f fifo
- */
-void svm_fifo_init_chunks (svm_fifo_t * f);
-/**
* Allocate a fifo chunk on heap
*
* If the chunk is allocated on a fifo segment, this should be called
@@ -287,31 +209,8 @@ svm_fifo_chunk_t *svm_fifo_chunk_alloc (u32 size);
* @param c chunk or linked list of chunks to be added
*/
void svm_fifo_add_chunk (svm_fifo_t * f, svm_fifo_chunk_t * c);
-/**
- * Request to reduce fifo size by amount of bytes
- *
- * Because the producer might be enqueuing data when this is called, the
- * actual size update is only applied when producer tries to enqueue new
- * data, unless @param try_shrink is set.
- *
- * @param f fifo
- * @param len number of bytes to remove from fifo. The actual number
- * of bytes to be removed will be less or equal to this
- * value.
- * @param try_shrink flg to indicate if it's safe to try to shrink fifo
- * size. It should be set only if this is called by the
- * producer of if the producer is not using the fifo
- * @return actual length fifo size will be reduced by
- */
-int svm_fifo_reduce_size (svm_fifo_t * f, u32 len, u8 try_shrink);
-/**
- * Removes chunks that are after fifo end byte
- *
- * Needs to be called with segment heap pushed.
- *
- * @param f fifo
- */
-svm_fifo_chunk_t *svm_fifo_collect_chunks (svm_fifo_t * f);
+int svm_fifo_fill_chunk_list (svm_fifo_t * f);
+void svm_fifo_init_ooo_lookup (svm_fifo_t * f, u8 ooo_type);
/**
* Free fifo and associated state
*
@@ -481,14 +380,7 @@ ooo_segment_t *svm_fifo_first_ooo_segment (svm_fifo_t * f);
* @return 1 if sane, 0 otherwise
*/
u8 svm_fifo_is_sane (svm_fifo_t * f);
-/**
- * Declare this fifo is used by only a single thread.
- * In this special case, fifo-growth can be done in an efficient way without delay.
- *
- * @param f fifo
- * @return 1 if the fifo is already owned by another thread, 0 otherwise
- */
-u8 svm_fifo_set_single_thread_owned (svm_fifo_t * f);
+u32 svm_fifo_n_chunks (svm_fifo_t * f);
format_function_t format_svm_fifo;
/**
@@ -543,7 +435,7 @@ svm_fifo_max_dequeue (svm_fifo_t * f)
static inline int
svm_fifo_is_full_prod (svm_fifo_t * f)
{
- return (svm_fifo_max_dequeue_prod (f) == f->nitems);
+ return (svm_fifo_max_dequeue_prod (f) == f->size);
}
/* Check if fifo is full.
@@ -555,7 +447,7 @@ svm_fifo_is_full_prod (svm_fifo_t * f)
static inline int
svm_fifo_is_full (svm_fifo_t * f)
{
- return (svm_fifo_max_dequeue (f) == f->nitems);
+ return (svm_fifo_max_dequeue (f) == f->size);
}
/**
@@ -622,8 +514,6 @@ svm_fifo_max_enqueue_prod (svm_fifo_t * f)
{
u32 head, tail;
f_load_head_tail_prod (f, &head, &tail);
- if (PREDICT_FALSE (f->flags & SVM_FIFO_F_SHRINK))
- svm_fifo_try_shrink (f, head, tail);
return f_free_count (f, head, tail);
}
@@ -638,40 +528,44 @@ svm_fifo_max_enqueue (svm_fifo_t * f)
{
u32 head, tail;
f_load_head_tail_all_acq (f, &head, &tail);
- if (PREDICT_FALSE (f->flags & SVM_FIFO_F_SHRINK))
- svm_fifo_try_shrink (f, head, tail);
return f_free_count (f, head, tail);
}
/**
- * Max contiguous chunk of data that can be read
+ * Max contiguous chunk of data that can be read.
+ *
+ * Should only be called by consumers.
*/
-static inline u32
-svm_fifo_max_read_chunk (svm_fifo_t * f)
-{
- u32 head, tail;
- f_load_head_tail_cons (f, &head, &tail);
- return tail >= head ? (tail - head) : (f->size - head);
-}
+u32 svm_fifo_max_read_chunk (svm_fifo_t * f);
/**
* Max contiguous chunk of data that can be written
+ *
+ * Should only be called by producers
*/
-static inline u32
-svm_fifo_max_write_chunk (svm_fifo_t * f)
+u32 svm_fifo_max_write_chunk (svm_fifo_t * f);
+
+static inline svm_fifo_chunk_t *
+svm_fifo_head_chunk (svm_fifo_t * f)
{
- u32 head, tail;
- f_load_head_tail_prod (f, &head, &tail);
- return tail >= head ? f->size - tail : f_free_count (f, head, tail);
+ return f->head_chunk;
}
static inline u8 *
svm_fifo_head (svm_fifo_t * f)
{
+ if (!f->head_chunk)
+ return 0;
/* load-relaxed: consumer owned index */
return (f->head_chunk->data + (f->head - f->head_chunk->start_byte));
}
+static inline svm_fifo_chunk_t *
+svm_fifo_tail_chunk (svm_fifo_t * f)
+{
+ return f->tail_chunk;
+}
+
static inline u8 *
svm_fifo_tail (svm_fifo_t * f)
{
@@ -718,7 +612,7 @@ ooo_segment_offset_prod (svm_fifo_t * f, ooo_segment_t * s)
/* load-relaxed: producer owned index */
tail = f->tail;
- return f_distance_to (f, s->start, tail);
+ return (s->start - tail);
}
static inline u32
@@ -727,6 +621,18 @@ ooo_segment_length (svm_fifo_t * f, ooo_segment_t * s)
return s->length;
}
+static inline u32
+svm_fifo_size (svm_fifo_t * f)
+{
+ return f->size;
+}
+
+static inline void
+svm_fifo_set_size (svm_fifo_t * f, u32 size)
+{
+ f->size = size;
+}
+
/**
* Check if fifo has io event
*
@@ -850,9 +756,8 @@ svm_fifo_needs_deq_ntf (svm_fifo_t * f, u32 n_last_deq)
if (want_ntf & SVM_FIFO_WANT_DEQ_NOTIF_IF_FULL)
{
u32 max_deq = svm_fifo_max_dequeue_cons (f);
- u32 nitems = f->nitems;
- if (!f->has_deq_ntf && max_deq < nitems
- && max_deq + n_last_deq >= nitems)
+ u32 size = f->size;
+ if (!f->has_deq_ntf && max_deq < size && max_deq + n_last_deq >= size)
return 1;
}
if (want_ntf & SVM_FIFO_WANT_DEQ_NOTIF_IF_EMPTY)