From de146e5d5f7e919b423feeff3159c4ecd564c353 Mon Sep 17 00:00:00 2001 From: Florin Coras Date: Fri, 26 Apr 2019 20:34:49 -0700 Subject: [PATCH 1/1] svm: fix fifo tail/head/ooo logic for u32 wrap These were introduced with the switch to unbound tail/head size, so they only affect master. Added unit tests to avoid future surprises. Change-Id: I83b6c9efbe31d8092ba59b8e2ed46f4da97f35db Signed-off-by: Florin Coras --- src/plugins/unittest/svm_fifo_test.c | 291 +++++++++++++++++++++++++++++++++-- src/svm/svm_fifo.c | 4 +- src/svm/svm_fifo.h | 4 +- 3 files changed, 283 insertions(+), 16 deletions(-) diff --git a/src/plugins/unittest/svm_fifo_test.c b/src/plugins/unittest/svm_fifo_test.c index 4e44441ebdc..9e834a1a056 100644 --- a/src/plugins/unittest/svm_fifo_test.c +++ b/src/plugins/unittest/svm_fifo_test.c @@ -174,7 +174,7 @@ compare_data (u8 * data1, u8 * data2, u32 start, u32 len, u32 * index) { int i; - for (i = start; i < len; i++) + for (i = start; i < start + len; i++) { if (data1[i] != data2[i]) { @@ -359,12 +359,19 @@ sfifo_test_fifo1 (vlib_main_t * vm, unformat_input_t * input) SFIFO_TEST ((svm_fifo_number_ooo_segments (f) == 1), "number of ooo segments %u", svm_fifo_number_ooo_segments (f)); - vec_validate (data_buf, vec_len (data)); - svm_fifo_peek (f, 0, vec_len (data), data_buf); - if (compare_data (data_buf, data, 8, vec_len (data), &j)) - { - SFIFO_TEST (0, "[%d] peeked %u expected %u", j, data_buf[j], data[j]); - } + /* add missing data to be able to dequeue something */ + rv = svm_fifo_enqueue_nowait (f, 4, data); + SFIFO_TEST ((rv == 32), "enqueued %u", rv); + SFIFO_TEST ((svm_fifo_number_ooo_segments (f) == 0), + "number of ooo segments %u", svm_fifo_number_ooo_segments (f)); + + vec_validate (data_buf, vec_len (test_data)); + svm_fifo_peek (f, 0, 4, data_buf); + if (compare_data (data_buf, data, 0, 4, &j)) + SFIFO_TEST (0, "[%d] peeked %u expected %u", j, data_buf[j], data[j]); + svm_fifo_peek (f, 8, 21, data_buf); + if (compare_data (data_buf, data, 0, 21, &j)) + SFIFO_TEST (0, "[%d] peeked %u expected %u", j, data_buf[j], data[j]); vec_reset_length (data_buf); /* @@ -426,7 +433,7 @@ static int sfifo_test_fifo2 (vlib_main_t * vm) { svm_fifo_t *f; - u32 fifo_size = 1 << 20; + u32 fifo_size = (1 << 20) + 1; int i, rv, test_data_len; u64 data64; test_pattern_t *tp, *vp, *test_data; @@ -508,7 +515,7 @@ static int sfifo_test_fifo3 (vlib_main_t * vm, unformat_input_t * input) { svm_fifo_t *f; - u32 fifo_size = 4 << 10; + u32 fifo_size = (4 << 10) + 1; u32 fifo_initial_offset = 0; u32 total_size = 2 << 10; int overlap = 0, verbose = 0, randomize = 1, drop = 0, in_seq_all = 0; @@ -802,6 +809,15 @@ fifo_pos (svm_fifo_t * f, u32 pos) return pos; } +/* Avoids exposing svm_fifo.c internal function */ +static ooo_segment_t * +ooo_seg_next (svm_fifo_t * f, ooo_segment_t * s) +{ + if (pool_is_free_index (f->ooo_segments, s->next)) + return 0; + return pool_elt_at_index (f->ooo_segments, s->next); +} + static int sfifo_test_fifo5 (vlib_main_t * vm, unformat_input_t * input) { @@ -848,7 +864,7 @@ sfifo_test_fifo5 (vlib_main_t * vm, unformat_input_t * input) * Add [225, 275] */ - rv = svm_fifo_enqueue_with_offset (f, 225, 50, &test_data[200]); + rv = svm_fifo_enqueue_with_offset (f, 225, 50, &test_data[225]); if (verbose) vlib_cli_output (vm, "fifo after [225, 275] : %U", format_svm_fifo, f, 2 /* verbose */ ); @@ -860,13 +876,13 @@ sfifo_test_fifo5 (vlib_main_t * vm, unformat_input_t * input) fifo_pos (f, 100 + offset)); SFIFO_TEST ((ooo_seg->length == 100), "first seg length %u expected %u", ooo_seg->length, 100); - ooo_seg = ooo_segment_next (f, ooo_seg); + ooo_seg = ooo_seg_next (f, ooo_seg); SFIFO_TEST ((ooo_seg->start == fifo_pos (f, 225 + offset)), "second seg start %u expected %u", ooo_seg->start, fifo_pos (f, 225 + offset)); SFIFO_TEST ((ooo_seg->length == 50), "second seg length %u expected %u", ooo_seg->length, 50); - ooo_seg = ooo_segment_next (f, ooo_seg); + ooo_seg = ooo_seg_next (f, ooo_seg); SFIFO_TEST ((ooo_seg->start == fifo_pos (f, 300 + offset)), "third seg start %u expected %u", ooo_seg->start, fifo_pos (f, 300 + offset)); @@ -931,6 +947,245 @@ sfifo_test_fifo5 (vlib_main_t * vm, unformat_input_t * input) return 0; } +/* + * Test ooo head/tail u32 wrapping + */ +static int +sfifo_test_fifo6 (vlib_main_t * vm, unformat_input_t * input) +{ + u32 fifo_size = 101, n_test_bytes = 100; + int i, j, rv, __clib_unused verbose = 0; + u8 *test_data = 0, *data_buf = 0; + ooo_segment_t *ooo_seg; + svm_fifo_t *f; + + while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) + { + if (unformat (input, "verbose")) + verbose = 1; + else + { + vlib_cli_output (vm, "parse error: '%U'", format_unformat_error, + input); + return -1; + } + } + + f = fifo_prepare (fifo_size); + vec_validate (test_data, n_test_bytes - 1); + vec_validate (data_buf, n_test_bytes - 1); + for (i = 0; i < vec_len (test_data); i++) + test_data[i] = i % 0xff; + + /* + * Test ooo segment distance to/from tail with u32 wrap + */ + + /* + * |0|---[start]--(len5)-->|0|--(len6)-->[end]---|0| + */ + rv = ooo_segment_distance_to_tail (f, ~0 - 5, 5); + SFIFO_TEST (rv == 11, "distance to tail should be %u is %u", 11, rv); + + rv = ooo_segment_distance_from_tail (f, ~0 - 5, 5); + SFIFO_TEST (rv == f->size - 11, "distance from tail should be %u is %u", + f->size - 11, rv); + + /* + * |0|---[end]--(len5)-->|0|--(len6)-->[start]---|0| + */ + rv = ooo_segment_distance_from_tail (f, 5, ~0 - 5); + SFIFO_TEST (rv == 11, "distance from tail should be %u is %u", 11, rv); + + rv = ooo_segment_distance_to_tail (f, 5, ~0 - 5); + SFIFO_TEST (rv == f->size - 11, "distance to tail should be %u is %u", + f->size - 11, rv); + + /* + * Add ooo with tail and ooo segment start u32 wrap + */ + svm_fifo_init_pointers (f, ~0, ~0); + svm_fifo_enqueue_with_offset (f, 10, 10, &test_data[10]); + SFIFO_TEST ((svm_fifo_number_ooo_segments (f) == 1), + "number of ooo segments %u", svm_fifo_number_ooo_segments (f)); + ooo_seg = svm_fifo_first_ooo_segment (f); + rv = ooo_segment_offset_prod (f, ooo_seg); + SFIFO_TEST (rv == 10, "offset should be %u is %u", 10, rv); + + svm_fifo_enqueue_nowait (f, 10, test_data); + SFIFO_TEST ((svm_fifo_number_ooo_segments (f) == 0), + "number of ooo segments %u", svm_fifo_number_ooo_segments (f)); + SFIFO_TEST (f->ooos_list_head == OOO_SEGMENT_INVALID_INDEX, + "there should be no ooo seg"); + + svm_fifo_peek (f, 5, 10, &data_buf[5]); + if (compare_data (data_buf, test_data, 5, 10, (u32 *) & j)) + SFIFO_TEST (0, "[%d] dequeued %u expected %u", j, data_buf[j], + test_data[j]); + + svm_fifo_dequeue_nowait (f, 20, data_buf); + if (compare_data (data_buf, test_data, 0, 20, (u32 *) & j)) + SFIFO_TEST (0, "[%d] dequeued %u expected %u", j, data_buf[j], + test_data[j]); + + /* + * Force collect with tail u32 wrap and without ooo segment start u32 wrap + */ + svm_fifo_init_pointers (f, ~0 - 10, ~0 - 10); + svm_fifo_enqueue_with_offset (f, 5, 15, &test_data[5]); + svm_fifo_enqueue_nowait (f, 12, test_data); + + SFIFO_TEST ((svm_fifo_number_ooo_segments (f) == 0), + "number of ooo segments %u", svm_fifo_number_ooo_segments (f)); + SFIFO_TEST (f->ooos_list_head == OOO_SEGMENT_INVALID_INDEX, + "there should be no ooo seg"); + + svm_fifo_dequeue_nowait (f, 20, data_buf); + if (compare_data (data_buf, test_data, 0, 20, (u32 *) & j)) + SFIFO_TEST (0, "[%d] dequeued %u expected %u", j, data_buf[j], + test_data[j]); + + /* + * Cleanup + */ + vec_free (test_data); + vec_free (data_buf); + svm_fifo_free (f); + return 0; +} + +/* + * Multiple ooo enqueues and dequeues that force fifo tail/head wrap + */ +static int +sfifo_test_fifo7 (vlib_main_t * vm, unformat_input_t * input) +{ + u32 fifo_size = 101, n_iterations = 100; + int i, j, rv, __clib_unused verbose = 0; + u8 *test_data = 0, *data_buf = 0; + u64 n_test_bytes = 100; + svm_fifo_t *f; + + while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) + { + if (unformat (input, "verbose")) + verbose = 1; + else + { + vlib_cli_output (vm, "parse error: '%U'", format_unformat_error, + input); + return -1; + } + } + + /* + * Prepare data structures + */ + f = fifo_prepare (fifo_size); + svm_fifo_init_pointers (f, ~0, ~0); + + vec_validate (test_data, n_test_bytes - 1); + vec_validate (data_buf, n_test_bytes - 1); + for (i = 0; i < vec_len (test_data); i++) + test_data[i] = i % 0xff; + + /* + * Run n iterations of test + */ + for (i = 0; i < n_iterations; i++) + { + for (j = n_test_bytes - 1; j > 0; j -= 2) + { + svm_fifo_enqueue_with_offset (f, j, 1, &test_data[j]); + rv = svm_fifo_number_ooo_segments (f); + if (rv != (n_test_bytes - j) / 2 + 1) + SFIFO_TEST (0, "number of ooo segments expected %u is %u", + (n_test_bytes - j) / 2 + 1, rv); + } + + svm_fifo_enqueue_with_offset (f, 1, n_test_bytes - 1, &test_data[1]); + rv = svm_fifo_number_ooo_segments (f); + if (rv != 1) + SFIFO_TEST (0, "number of ooo segments %u", rv); + + svm_fifo_enqueue_nowait (f, 1, test_data); + rv = svm_fifo_number_ooo_segments (f); + if (rv != 0) + SFIFO_TEST (0, "number of ooo segments %u", rv); + + svm_fifo_dequeue_nowait (f, n_test_bytes, data_buf); + if (compare_data (data_buf, test_data, 0, n_test_bytes, (u32 *) & j)) + SFIFO_TEST (0, "[%d] dequeued %u expected %u", j, data_buf[j], + test_data[j]); + svm_fifo_init_pointers (f, ~0 - i, ~0 - i); + } + SFIFO_TEST (1, "passed multiple ooo enqueue/dequeue"); + + /* + * Cleanup + */ + vec_free (test_data); + vec_free (data_buf); + svm_fifo_free (f); + return 0; +} + +/* + * Enqueue more than 4GB + */ +static int +sfifo_test_fifo_large (vlib_main_t * vm, unformat_input_t * input) +{ + u32 n_iterations = 100, n_bytes_per_iter, half; + int i, j, rv, __clib_unused verbose = 0; + u8 *test_data = 0, *data_buf = 0; + u64 n_test_bytes = 100; + svm_fifo_t *f; + + while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) + { + if (unformat (input, "verbose")) + verbose = 1; + else + { + vlib_cli_output (vm, "parse error: '%U'", format_unformat_error, + input); + return -1; + } + } + + + n_test_bytes = 5ULL << 30; + n_iterations = 1 << 10; + n_bytes_per_iter = n_test_bytes / n_iterations; + + f = fifo_prepare (n_bytes_per_iter + 1); + svm_fifo_init_pointers (f, ~0, ~0); + + vec_validate (test_data, n_bytes_per_iter - 1); + vec_validate (data_buf, n_bytes_per_iter - 1); + for (i = 0; i < vec_len (test_data); i++) + test_data[i] = i % 0xff; + + half = n_bytes_per_iter / 2; + for (i = 0; i < n_iterations; i++) + { + svm_fifo_enqueue_with_offset (f, half, half, &test_data[half]); + svm_fifo_enqueue_nowait (f, half, test_data); + rv = svm_fifo_number_ooo_segments (f); + if (rv != 0) + SFIFO_TEST (0, "number of ooo segments %u", rv); + svm_fifo_dequeue_nowait (f, n_bytes_per_iter, data_buf); + if (compare_data (data_buf, test_data, 0, n_bytes_per_iter, + (u32 *) & j)) + SFIFO_TEST (0, "[%d][%d] dequeued %u expected %u", i, j, data_buf[j], + test_data[j]); + } + SFIFO_TEST (1, "passed large transfer"); + + return 0; +} + static int sfifo_test_fifo_grow (vlib_main_t * vm, unformat_input_t * input) { @@ -1606,6 +1861,12 @@ svm_fifo_test (vlib_main_t * vm, unformat_input_t * input, res = sfifo_test_fifo4 (vm, input); else if (unformat (input, "fifo5")) res = sfifo_test_fifo5 (vm, input); + else if (unformat (input, "fifo6")) + res = sfifo_test_fifo6 (vm, input); + else if (unformat (input, "fifo7")) + res = sfifo_test_fifo7 (vm, input); + else if (unformat (input, "large")) + res = sfifo_test_fifo_large (vm, input); else if (unformat (input, "replay")) res = sfifo_test_fifo_replay (vm, input); else if (unformat (input, "grow")) @@ -1659,6 +1920,12 @@ svm_fifo_test (vlib_main_t * vm, unformat_input_t * input, if ((res = sfifo_test_fifo5 (vm, input))) goto done; + if ((res = sfifo_test_fifo6 (vm, input))) + goto done; + + if ((res = sfifo_test_fifo7 (vm, input))) + goto done; + if ((res = sfifo_test_fifo_grow (vm, input))) goto done; diff --git a/src/svm/svm_fifo.c b/src/svm/svm_fifo.c index c8fd263c094..4c84fce4c01 100644 --- a/src/svm/svm_fifo.c +++ b/src/svm/svm_fifo.c @@ -819,7 +819,7 @@ svm_fifo_enqueue_with_offset (svm_fifo_t * f, u32 offset, u32 len, u8 * src) ooo_segment_add (f, offset, head, tail, len); - tail_idx = (tail + offset) % f->size; + tail_idx = (tail % f->size + offset) % f->size; if (!svm_fifo_chunk_includes_pos (f->ooo_enq, tail_idx)) f->ooo_enq = svm_fifo_find_chunk (f, tail_idx); @@ -871,7 +871,7 @@ svm_fifo_peek (svm_fifo_t * f, u32 offset, u32 len, u8 * dst) return -2; /* nothing in the fifo */ len = clib_min (cursize - offset, len); - head_idx = (head + offset) % f->size; + head_idx = (head % f->size + offset) % f->size; if (!svm_fifo_chunk_includes_pos (f->ooo_deq, head_idx)) f->ooo_deq = svm_fifo_find_chunk (f, head_idx); diff --git a/src/svm/svm_fifo.h b/src/svm/svm_fifo.h index 7c84fc82198..c9370955dfb 100644 --- a/src/svm/svm_fifo.h +++ b/src/svm/svm_fifo.h @@ -527,13 +527,13 @@ svm_fifo_newest_ooo_segment_reset (svm_fifo_t * f) always_inline u32 ooo_segment_distance_from_tail (svm_fifo_t * f, u32 pos, u32 tail) { - return ((pos - tail) % f->size); + return ((f->size + pos - tail) % f->size); } always_inline u32 ooo_segment_distance_to_tail (svm_fifo_t * f, u32 pos, u32 tail) { - return ((tail - pos) % f->size); + return ((f->size + tail - pos) % f->size); } always_inline u32 -- 2.16.6