From efeea5b111db9075ffdab73191f6343f6872bfb2 Mon Sep 17 00:00:00 2001 From: Damjan Marion Date: Thu, 10 Feb 2022 15:01:03 +0100 Subject: [PATCH] vlib: vlib frame bitmaps Special bitmaps with VLIB_FRAME_SIZE bits. Type: improvement Change-Id: I48747e422e519e7b5e930fa720397459d3adbb8e Signed-off-by: Damjan Marion --- src/vlib/buffer_funcs.c | 23 +++++------- src/vlib/node_funcs.h | 85 +++++++++++++++++++++++++++++++++++++++++++++ src/vnet/interface_output.c | 8 ++--- 3 files changed, 97 insertions(+), 19 deletions(-) diff --git a/src/vlib/buffer_funcs.c b/src/vlib/buffer_funcs.c index a661370a141..32c2d1b8a2f 100644 --- a/src/vlib/buffer_funcs.c +++ b/src/vlib/buffer_funcs.c @@ -8,11 +8,11 @@ #include static_always_inline u32 -enqueue_one (vlib_main_t *vm, vlib_node_runtime_t *node, u64 *used_elt_bmp, - u16 next_index, u32 *buffers, u16 *nexts, u32 n_buffers, - u32 n_left, u32 *tmp) +enqueue_one (vlib_main_t *vm, vlib_node_runtime_t *node, + vlib_frame_bitmap_t used_elt_bmp, u16 next_index, u32 *buffers, + u16 *nexts, u32 n_buffers, u32 n_left, u32 *tmp) { - u64 match_bmp[VLIB_FRAME_SIZE / 64]; + vlib_frame_bitmap_t match_bmp; vlib_frame_t *f; u32 n_extracted, n_free; u32 *to; @@ -29,11 +29,8 @@ enqueue_one (vlib_main_t *vm, vlib_node_runtime_t *node, u64 *used_elt_bmp, to = tmp; clib_mask_compare_u16 (next_index, nexts, match_bmp, n_buffers); - n_extracted = clib_compress_u32 (to, buffers, match_bmp, n_buffers); - - for (int i = 0; i < ARRAY_LEN (match_bmp); i++) - used_elt_bmp[i] |= match_bmp[i]; + vlib_frame_bitmap_or (used_elt_bmp, match_bmp); if (to != tmp) { @@ -77,7 +74,7 @@ CLIB_MULTIARCH_FN (vlib_buffer_enqueue_to_next_fn) while (count >= VLIB_FRAME_SIZE) { - u64 used_elt_bmp[VLIB_FRAME_SIZE / 64] = {}; + vlib_frame_bitmap_t used_elt_bmp = {}; n_left = VLIB_FRAME_SIZE; u32 off = 0; @@ -106,7 +103,7 @@ CLIB_MULTIARCH_FN (vlib_buffer_enqueue_to_next_fn) if (count) { - u64 used_elt_bmp[VLIB_FRAME_SIZE / 64] = {}; + vlib_frame_bitmap_t used_elt_bmp = {}; next_index = nexts[0]; n_left = count; u32 off = 0; @@ -208,8 +205,7 @@ vlib_buffer_enqueue_to_thread_inline (vlib_main_t *vm, u32 n_packets, int drop_on_congestion) { u32 drop_list[VLIB_FRAME_SIZE], n_drop = 0; - u64 used_elts[VLIB_FRAME_SIZE / 64] = {}; - u64 mask[VLIB_FRAME_SIZE / 64]; + vlib_frame_bitmap_t mask, used_elts = {}; vlib_frame_queue_elt_t *hf = 0; u16 thread_index; u32 n_comp, off = 0, n_left = n_packets; @@ -238,8 +234,7 @@ more: if (n_left) { - for (int i = 0; i < ARRAY_LEN (used_elts); i++) - used_elts[i] |= mask[i]; + vlib_frame_bitmap_or (used_elts, mask); while (PREDICT_FALSE (used_elts[off] == ~0)) { diff --git a/src/vlib/node_funcs.h b/src/vlib/node_funcs.h index 46db46dd1e0..a9101f5d16a 100644 --- a/src/vlib/node_funcs.h +++ b/src/vlib/node_funcs.h @@ -1279,6 +1279,91 @@ vlib_node_function_t * vlib_node_get_preferred_node_fn_variant (vlib_main_t *vm, vlib_node_fn_registration_t *regs); +/* + * vlib_frame_bitmap functions + */ + +#define VLIB_FRAME_BITMAP_N_UWORDS \ + (((VLIB_FRAME_SIZE + uword_bits - 1) & ~(uword_bits - 1)) / uword_bits) + +typedef uword vlib_frame_bitmap_t[VLIB_FRAME_BITMAP_N_UWORDS]; + +static_always_inline void +vlib_frame_bitmap_init (uword *bmp, u32 n_first_bits_set) +{ + u32 n_left = VLIB_FRAME_BITMAP_N_UWORDS; + while (n_first_bits_set >= (sizeof (uword) * 8) && n_left) + { + bmp++[0] = ~0; + n_first_bits_set -= sizeof (uword) * 8; + n_left--; + } + + if (n_first_bits_set && n_left) + { + bmp++[0] = pow2_mask (n_first_bits_set); + n_left--; + } + + while (n_left--) + bmp++[0] = 0; +} + +static_always_inline void +vlib_frame_bitmap_clear (uword *bmp) +{ + u32 n_left = VLIB_FRAME_BITMAP_N_UWORDS; + while (n_left--) + bmp++[0] = 0; +} + +static_always_inline void +vlib_frame_bitmap_xor (uword *bmp, uword *bmp2) +{ + u32 n_left = VLIB_FRAME_BITMAP_N_UWORDS; + while (n_left--) + bmp++[0] ^= bmp2++[0]; +} + +static_always_inline void +vlib_frame_bitmap_or (uword *bmp, uword *bmp2) +{ + u32 n_left = VLIB_FRAME_BITMAP_N_UWORDS; + while (n_left--) + bmp++[0] |= bmp2++[0]; +} + +static_always_inline u32 +vlib_frame_bitmap_count_set_bits (uword *bmp) +{ + u32 n_left = VLIB_FRAME_BITMAP_N_UWORDS; + u32 count = 0; + while (n_left--) + count += count_set_bits (bmp++[0]); + return count; +} + +static_always_inline int +vlib_frame_bitmap_find_first_set (uword *bmp) +{ + uword *b = bmp; + while (b[0] == 0) + { + ASSERT (b - bmp < VLIB_FRAME_BITMAP_N_UWORDS); + b++; + } + + return (b - bmp) * uword_bits + get_lowest_set_bit_index (b[0]); +} + +#define foreach_vlib_frame_bitmap_set_bit_index(i, v) \ + for (uword _off = 0; _off < ARRAY_LEN (v); _off++) \ + for (uword _tmp = \ + (v[_off]) + 0 * (uword) (i = _off * uword_bits + \ + get_lowest_set_bit_index (v[_off])); \ + _tmp; i = _off * uword_bits + get_lowest_set_bit_index ( \ + _tmp = clear_lowest_set_bit (_tmp))) + #endif /* included_vlib_node_funcs_h */ /* diff --git a/src/vnet/interface_output.c b/src/vnet/interface_output.c index cf64eeed093..6d5697deac4 100644 --- a/src/vnet/interface_output.c +++ b/src/vnet/interface_output.c @@ -405,7 +405,7 @@ enqueue_one_to_tx_node (vlib_main_t *vm, vlib_node_runtime_t *node, u32 *ppqi, u32 n_vectors, u32 n_left, u32 next_index) { u32 tmp[VLIB_FRAME_SIZE]; - u64 mask[VLIB_FRAME_SIZE / 64] = {}; + vlib_frame_bitmap_t mask = {}; vlib_frame_t *f; vnet_hw_if_tx_frame_t *tf; u32 *to; @@ -1259,8 +1259,7 @@ VLIB_NODE_FN (vnet_interface_output_arc_end_node) vnet_hw_interface_t *hi; vlib_buffer_t *bufs[VLIB_FRAME_SIZE], **b = bufs; u32 sw_if_indices[VLIB_FRAME_SIZE], *sw_if_index = sw_if_indices; - u64 used_elts[VLIB_FRAME_SIZE / 64] = {}; - u64 mask[VLIB_FRAME_SIZE / 64] = {}; + vlib_frame_bitmap_t used_elts = {}, mask = {}; u32 *tmp, *from, n_left, n_comp, n_p_comp, swif, off; u16 next_index; void *ptr[VLIB_FRAME_SIZE], **p = ptr; @@ -1350,8 +1349,7 @@ drop: if (n_left) { /* store comparison mask so we can find next unused element */ - for (int i = 0; i < ARRAY_LEN (used_elts); i++) - used_elts[i] |= mask[i]; + vlib_frame_bitmap_or (used_elts, mask); /* fine first unused sw_if_index by scanning trough used_elts bitmap */ while (PREDICT_FALSE (used_elts[off] == ~0)) -- 2.16.6