From 1a19552eee24e447e6087de43a2eeb9250b8cae7 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Beno=C3=AEt=20Ganne?= Date: Thu, 27 May 2021 17:43:34 +0200 Subject: [PATCH] buffers: fix buffer linearization MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit vlib_buffer_chain_linearize() truncates partial data in chained buffers in corner cases when current_data is negative. Strengthen test cases to reproduce the errors and fix it. Type: fix Change-Id: Ida621923711c5755508224bdc3842b31003c6c0b Signed-off-by: Benoît Ganne --- src/plugins/unittest/test_buffer.c | 308 ++++++++++++++++++++++++++++++++----- src/vlib/buffer_funcs.h | 199 ++++++++++++------------ 2 files changed, 376 insertions(+), 131 deletions(-) diff --git a/src/plugins/unittest/test_buffer.c b/src/plugins/unittest/test_buffer.c index 18938d888bb..584ce589012 100644 --- a/src/plugins/unittest/test_buffer.c +++ b/src/plugins/unittest/test_buffer.c @@ -16,48 +16,237 @@ #include #include -#define TEST_I(_cond, _comment, _args...) \ -({ \ - int _evald = (_cond); \ - if (!(_evald)) { \ - fformat(stderr, "FAIL:%d: " _comment "\n", \ - __LINE__, ##_args); \ - } else { \ - fformat(stderr, "PASS:%d: " _comment "\n", \ - __LINE__, ##_args); \ - } \ - _evald; \ -}) - -#define TEST(_cond, _comment, _args...) \ -{ \ - if (!TEST_I(_cond, _comment, ##_args)) { \ - return 1; \ - } \ +#define TEST_I(_cond, _comment, _args...) \ + ({ \ + int _evald = (0 == (_cond)); \ + if (_evald) \ + { \ + fformat (stderr, "FAIL:%d: " _comment "\n", __LINE__, ##_args); \ + } \ + else \ + { \ + fformat (stderr, "PASS:%d: " _comment "\n", __LINE__, ##_args); \ + } \ + _evald; \ + }) + +#define TEST(_cond, _comment, _args...) \ + { \ + if (TEST_I (_cond, _comment, ##_args)) \ + { \ + goto err; \ + } \ + } + +typedef struct +{ + i16 current_data; + u16 current_length; + u8 ref_count; +} chained_buffer_template_t; + +static int +build_chain (vlib_main_t *vm, const chained_buffer_template_t *tmpl, u32 n, + clib_random_buffer_t *randbuf, u8 **rand, vlib_buffer_t **b_, + u32 *bi_) +{ + vlib_buffer_t *bufs[2 * VLIB_BUFFER_LINEARIZE_MAX], **b = bufs; + u32 bis[2 * VLIB_BUFFER_LINEARIZE_MAX + 1], *bi = bis; + u32 n_alloc; + + if (rand) + vec_reset_length (*rand); + + ASSERT (n <= ARRAY_LEN (bufs)); + n_alloc = vlib_buffer_alloc (vm, bi, n); + if (n_alloc != n) + { + vlib_buffer_free (vm, bi, n_alloc); + return 0; + } + + vlib_get_buffers (vm, bis, bufs, n); + + while (n > 0) + { + b[0]->next_buffer = bi[1]; + b[0]->flags |= VLIB_BUFFER_NEXT_PRESENT; + b[0]->current_data = tmpl->current_data; + b[0]->current_length = tmpl->current_length; + b[0]->ref_count = 0xff == tmpl->ref_count ? 1 : tmpl->ref_count; + + if (rand) + { + const u16 len = b[0]->current_length; + if (len) + { + vec_add (*rand, clib_random_buffer_get_data (randbuf, len), len); + void *dst = vlib_buffer_get_current (b[0]); + const void *src = + vec_elt_at_index (*rand, vec_len (*rand) - len); + clib_memcpy_fast (dst, src, len); + } + } + + b++; + bi++; + tmpl++; + n--; + } + + b[-1]->flags &= ~VLIB_BUFFER_NEXT_PRESENT; + + *b_ = bufs[0]; + *bi_ = bis[0]; + return 1; +} + +static int +check_chain (vlib_main_t *vm, vlib_buffer_t *b, const u8 *rand) +{ + int len_chain = vlib_buffer_length_in_chain (vm, b); + int len; + + /* check for data corruption */ + if (clib_memcmp (vlib_buffer_get_current (b), vec_elt_at_index (rand, 0), + b->current_length)) + return 0; + len = b->current_length; + while (b->flags & VLIB_BUFFER_NEXT_PRESENT) + { + b = vlib_get_buffer (vm, b->next_buffer); + if (clib_memcmp (vlib_buffer_get_current (b), + vec_elt_at_index (rand, len), b->current_length)) + return 0; + len += b->current_length; + } + + /* check for data truncation */ + if (len != vec_len (rand)) + return 0; + + /* check total length update is correct */ + if (len != len_chain) + return 0; + + return 1; +} + +static int +test_chain (vlib_main_t *vm, const chained_buffer_template_t *tmpl, + const u32 n, const int clone_off, clib_random_buffer_t *randbuf, + u8 **rand) +{ + vlib_buffer_t *b; + u32 bi[2]; + int ret = 0; + + if (!build_chain (vm, tmpl, n, randbuf, rand, &b, bi)) + goto err0; + + if (clone_off) + { + if (2 != vlib_buffer_clone (vm, bi[0], bi, 2, clone_off)) + goto err1; + b = vlib_get_buffer (vm, bi[0]); + } + + if (!(ret = vlib_buffer_chain_linearize (vm, b))) + goto err2; + + if (!check_chain (vm, b, *rand)) + { + ret = 0; + goto err2; + } + +err2: + if (clone_off) + vlib_buffer_free_one (vm, bi[1]); +err1: + vlib_buffer_free_one (vm, bi[0]); +err0: + return ret; } -/* test function for a specific case where current_data is negative, verify - * that there is no crash */ static int -linearize_negative_current_data (vlib_main_t * vm) +linearize_test (vlib_main_t *vm) { - u32 bi[32]; - TEST (ARRAY_LEN (bi) == vlib_buffer_alloc (vm, bi, ARRAY_LEN (bi)), - "buff alloc"); + chained_buffer_template_t tmpl[VLIB_BUFFER_LINEARIZE_MAX]; + clib_random_buffer_t randbuf; u32 data_size = vlib_buffer_get_default_data_size (vm); - u32 i; - for (i = 0; i < ARRAY_LEN (bi) - 1; ++i) + u8 *rand = 0; + int ret = 0; + int i; + + clib_random_buffer_init (&randbuf, 0); + + clib_memset (tmpl, 0xff, sizeof (tmpl)); + for (i = 0; i < 2; i++) { - vlib_buffer_t *b = vlib_get_buffer (vm, bi[i]); - b->next_buffer = bi[i + 1]; - b->flags |= VLIB_BUFFER_NEXT_PRESENT; - b->current_data = -14; - b->current_length = 14 + data_size; + tmpl[i].current_data = -14; + tmpl[i].current_length = 14 + data_size; } + TEST (2 == test_chain (vm, tmpl, 2, 0, &randbuf, &rand), + "linearize chain with negative current data"); - (void) vlib_buffer_chain_linearize (vm, vlib_get_buffer (vm, bi[0])); + clib_memset (tmpl, 0xff, sizeof (tmpl)); + tmpl[0].current_data = 12; + tmpl[0].current_length = data_size - 12; + tmpl[1].current_data = 0; + tmpl[1].current_length = 0; + TEST (1 == test_chain (vm, tmpl, 2, 0, &randbuf, &rand), + "linearize chain with empty next"); - return 0; + clib_memset (tmpl, 0xff, sizeof (tmpl)); + tmpl[0].current_data = 0; + tmpl[0].current_length = data_size - 17; + tmpl[1].current_data = -5; + tmpl[1].current_length = 3; + tmpl[2].current_data = 17; + tmpl[2].current_length = 9; + tmpl[3].current_data = 3; + tmpl[3].current_length = 5; + TEST (1 == test_chain (vm, tmpl, 4, 0, &randbuf, &rand), + "linearize chain into a single buffer"); + + clib_memset (tmpl, 0xff, sizeof (tmpl)); + tmpl[0].current_data = 0; + tmpl[0].current_length = data_size - 2; + tmpl[1].current_data = -VLIB_BUFFER_PRE_DATA_SIZE; + tmpl[1].current_length = 20; + tmpl[2].current_data = data_size - 10; + tmpl[2].current_length = 10; + tmpl[3].current_data = 0; + tmpl[3].current_length = data_size; + TEST (2 == test_chain (vm, tmpl, 4, data_size - 1, &randbuf, &rand), + "linearize cloned chain"); + + clib_memset (tmpl, 0xff, sizeof (tmpl)); + for (i = 0; i < 100; i++) + { + u8 *r = clib_random_buffer_get_data (&randbuf, 1); + int n = clib_max (r[0] % ARRAY_LEN (tmpl), 1); + int j; + for (j = 0; j < n; j++) + { + r = clib_random_buffer_get_data (&randbuf, 3); + i16 current_data = (i16) r[0] - VLIB_BUFFER_PRE_DATA_SIZE; + u16 current_length = *(u16 *) (r + 1) % (data_size - current_data); + tmpl[j].current_data = current_data; + tmpl[j].current_length = current_length; + } + r = clib_random_buffer_get_data (&randbuf, 1); + TEST ( + test_chain (vm, tmpl, n, r[0] > 250 ? r[0] % 128 : 0, &randbuf, &rand), + "linearize random chain %d", i); + } + + ret = 1; +err: + clib_random_buffer_free (&randbuf); + vec_free (rand); + return ret; } static clib_error_t * @@ -65,12 +254,12 @@ test_linearize_fn (vlib_main_t * vm, unformat_input_t * input, vlib_cli_command_t * cmd) { - if (linearize_negative_current_data (vm)) + if (!linearize_test (vm)) { - return clib_error_return (0, "linearize_negative_current_data failed"); + return clib_error_return (0, "linearize test failed"); } - return (NULL); + return 0; } /* *INDENT-OFF* */ @@ -82,6 +271,53 @@ VLIB_CLI_COMMAND (test_linearize_command, static) = }; /* *INDENT-ON* */ +static clib_error_t * +test_linearize_speed_fn (vlib_main_t *vm, unformat_input_t *input, + vlib_cli_command_t *cmd) +{ + /* typical 9000-bytes TCP jumbo frames */ + const chained_buffer_template_t tmpl[5] = { { 14, 2034, 1 }, + { 0, 2048, 1 }, + { 0, 2048, 1 }, + { 0, 2048, 1 }, + { 0, 808, 1 } }; + int i, j; + + for (i = 0; i < 10; i++) + { + u64 tot = 0; + for (j = 0; j < 100000; j++) + { + vlib_buffer_t *b; + u32 bi; + + if (!build_chain (vm, tmpl, 5, 0, 0, &b, &bi)) + return clib_error_create ("build_chain() failed"); + + CLIB_COMPILER_BARRIER (); + u64 start = clib_cpu_time_now (); + CLIB_COMPILER_BARRIER (); + + vlib_buffer_chain_linearize (vm, b); + + CLIB_COMPILER_BARRIER (); + tot += clib_cpu_time_now () - start; + CLIB_COMPILER_BARRIER (); + + vlib_buffer_free_one (vm, bi); + } + vlib_cli_output (vm, "%.03f ticks/call", (f64) tot / j); + } + + return 0; +} + +VLIB_CLI_COMMAND (test_linearize_speed_command, static) = { + .path = "test chained-buffer-linearization speed", + .short_help = "test chained-buffer-linearization speed", + .function = test_linearize_speed_fn, +}; + /* * fd.io coding-style-patch-verification: ON * diff --git a/src/vlib/buffer_funcs.h b/src/vlib/buffer_funcs.h index 8b8a3911776..89a765ee0d3 100644 --- a/src/vlib/buffer_funcs.h +++ b/src/vlib/buffer_funcs.h @@ -1468,139 +1468,148 @@ vlib_buffer_space_left_at_end (vlib_main_t * vm, vlib_buffer_t * b) ((u8 *) vlib_buffer_get_current (b) + b->current_length); } +#define VLIB_BUFFER_LINEARIZE_MAX 64 + always_inline u32 vlib_buffer_chain_linearize (vlib_main_t * vm, vlib_buffer_t * b) { - vlib_buffer_t *db = b, *sb, *first = b; - int is_cloned = 0; - u32 bytes_left = 0, data_size; - u16 src_left, dst_left, n_buffers = 1; - u8 *dp, *sp; - u32 to_free = 0; + vlib_buffer_t *dst_b; + u32 n_buffers = 1, to_free = 0; + u16 rem_len, dst_len, data_size, src_len = 0; + u8 *dst, *src = 0; if (PREDICT_TRUE ((b->flags & VLIB_BUFFER_NEXT_PRESENT) == 0)) return 1; + ASSERT (1 == b->ref_count); + if (PREDICT_FALSE (1 != b->ref_count)) + return 0; + data_size = vlib_buffer_get_default_data_size (vm); + rem_len = vlib_buffer_length_in_chain (vm, b) - b->current_length; - dst_left = vlib_buffer_space_left_at_end (vm, b); + dst_b = b; + dst = vlib_buffer_get_tail (dst_b); + dst_len = vlib_buffer_space_left_at_end (vm, dst_b); - while (b->flags & VLIB_BUFFER_NEXT_PRESENT) - { - b = vlib_get_buffer (vm, b->next_buffer); - if (b->ref_count > 1) - is_cloned = 1; - bytes_left += b->current_length; - n_buffers++; - } + b->total_length_not_including_first_buffer -= dst_len; - /* if buffer is cloned, create completely new chain - unless everything fits - * into one buffer */ - if (is_cloned && bytes_left >= dst_left) + while (rem_len > 0) { - u32 len = 0; - u32 space_needed = bytes_left - dst_left; - u32 tail; - - if (vlib_buffer_alloc (vm, &tail, 1) == 0) - return 0; + u16 copy_len; - ++n_buffers; - len += data_size; - b = vlib_get_buffer (vm, tail); - - while (len < space_needed) + while (0 == src_len) { - u32 bi; - if (vlib_buffer_alloc (vm, &bi, 1) == 0) - { - vlib_buffer_free_one (vm, tail); - return 0; - } - b->flags = VLIB_BUFFER_NEXT_PRESENT; - b->next_buffer = bi; - b = vlib_get_buffer (vm, bi); - len += data_size; - n_buffers++; + ASSERT (b->flags & VLIB_BUFFER_NEXT_PRESENT); + if (PREDICT_FALSE (!(b->flags & VLIB_BUFFER_NEXT_PRESENT))) + break; /* malformed chained buffer */ + + b = vlib_get_buffer (vm, b->next_buffer); + src = vlib_buffer_get_current (b); + src_len = b->current_length; } - sb = vlib_get_buffer (vm, first->next_buffer); - to_free = first->next_buffer; - first->next_buffer = tail; - } - else - sb = vlib_get_buffer (vm, first->next_buffer); - src_left = sb->current_length; - sp = vlib_buffer_get_current (sb); - dp = vlib_buffer_get_tail (db); + if (0 == dst_len) + { + ASSERT (dst_b->flags & VLIB_BUFFER_NEXT_PRESENT); + if (PREDICT_FALSE (!(dst_b->flags & VLIB_BUFFER_NEXT_PRESENT))) + break; /* malformed chained buffer */ - while (bytes_left) - { - u16 bytes_to_copy; + vlib_buffer_t *next_dst_b = vlib_get_buffer (vm, dst_b->next_buffer); - if (dst_left == 0) - { - db->current_length = dp - (u8 *) vlib_buffer_get_current (db); - ASSERT (db->flags & VLIB_BUFFER_NEXT_PRESENT); - db = vlib_get_buffer (vm, db->next_buffer); - dst_left = data_size; - if (db->current_data > 0) + if (PREDICT_TRUE (1 == next_dst_b->ref_count)) { - db->current_data = 0; + /* normal case: buffer is not cloned, just use it */ + dst_b = next_dst_b; } else { - dst_left += -db->current_data; + /* cloned buffer, build a new dest chain from there */ + vlib_buffer_t *bufs[VLIB_BUFFER_LINEARIZE_MAX]; + u32 bis[VLIB_BUFFER_LINEARIZE_MAX + 1]; + const int n = (rem_len + data_size - 1) / data_size; + int n_alloc; + int i; + + ASSERT (n <= VLIB_BUFFER_LINEARIZE_MAX); + if (PREDICT_FALSE (n > VLIB_BUFFER_LINEARIZE_MAX)) + return 0; + + n_alloc = vlib_buffer_alloc (vm, bis, n); + if (PREDICT_FALSE (n_alloc != n)) + { + vlib_buffer_free (vm, bis, n_alloc); + return 0; + } + + vlib_get_buffers (vm, bis, bufs, n); + + for (i = 0; i < n - 1; i++) + { + bufs[i]->flags |= VLIB_BUFFER_NEXT_PRESENT; + bufs[i]->next_buffer = bis[i + 1]; + } + + to_free = dst_b->next_buffer; + dst_b->next_buffer = bis[0]; + dst_b = bufs[0]; } - dp = vlib_buffer_get_current (db); - } - while (src_left == 0) - { - ASSERT (sb->flags & VLIB_BUFFER_NEXT_PRESENT); - sb = vlib_get_buffer (vm, sb->next_buffer); - src_left = sb->current_length; - sp = vlib_buffer_get_current (sb); + n_buffers++; + + dst_b->current_data = clib_min (0, dst_b->current_data); + dst_b->current_length = 0; + + dst = dst_b->data + dst_b->current_data; + dst_len = data_size - dst_b->current_data; } - bytes_to_copy = clib_min (dst_left, src_left); + copy_len = clib_min (src_len, dst_len); - if (dp != sp) + if (PREDICT_TRUE (src == dst)) { - if (sb == db) - bytes_to_copy = clib_min (bytes_to_copy, sp - dp); - - clib_memcpy_fast (dp, sp, bytes_to_copy); + /* nothing to do */ + } + else if (src + copy_len > dst && dst + copy_len > src) + { + /* src and dst overlap */ + ASSERT (b == dst_b); + memmove (dst, src, copy_len); + } + else + { + clib_memcpy_fast (dst, src, copy_len); } - src_left -= bytes_to_copy; - dst_left -= bytes_to_copy; - dp += bytes_to_copy; - sp += bytes_to_copy; - bytes_left -= bytes_to_copy; + dst_b->current_length += copy_len; + + dst += copy_len; + src += copy_len; + dst_len -= copy_len; + src_len -= copy_len; + rem_len -= copy_len; } - if (db != first) - db->current_data = 0; - db->current_length = dp - (u8 *) vlib_buffer_get_current (db); - if (is_cloned && to_free) + /* in case of a malformed chain buffer, we'll exit early from the loop. */ + ASSERT (0 == rem_len); + b->total_length_not_including_first_buffer -= rem_len; + + if (to_free) vlib_buffer_free_one (vm, to_free); - else + + if (dst_b->flags & VLIB_BUFFER_NEXT_PRESENT) { - if (db->flags & VLIB_BUFFER_NEXT_PRESENT) - vlib_buffer_free_one (vm, db->next_buffer); - db->flags &= ~VLIB_BUFFER_NEXT_PRESENT; - b = first; - n_buffers = 1; - while (b->flags & VLIB_BUFFER_NEXT_PRESENT) + /* the resulting chain is smaller than the original, cut it there */ + dst_b->flags &= ~VLIB_BUFFER_NEXT_PRESENT; + vlib_buffer_free_one (vm, dst_b->next_buffer); + if (1 == n_buffers) { - b = vlib_get_buffer (vm, b->next_buffer); - ++n_buffers; + /* no longer a chained buffer */ + dst_b->flags &= ~VLIB_BUFFER_TOTAL_LENGTH_VALID; + dst_b->total_length_not_including_first_buffer = 0; } } - first->flags &= ~VLIB_BUFFER_TOTAL_LENGTH_VALID; - return n_buffers; } -- 2.16.6