src/vlib/buffer_funcs.c

   1 /* SPDX-License-Identifier: Apache-2.0
   2  * Copyright(c) 2021 Cisco Systems, Inc.
   3  */
   4
   5 #include <vppinfra/clib.h>
   6 #include <vlib/vlib.h>
   7 #include <vppinfra/vector_funcs.h>
   8
   9 typedef struct
  10 {
  11   uword used_elts[VLIB_FRAME_SIZE / 64];
  12   u32 uword_offset;
  13 } extract_data_t;
  14
  15 static_always_inline u32 *
  16 extract_unused_elts_x64 (u32 *elts, u16 *indices, u16 index, int n_left,
  17                          u64 *bmp, u32 *dst)
  18 {
  19   u64 mask = 0;
  20 #if defined(CLIB_HAVE_VEC128)
  21   mask = clib_compare_u16_x64 (index, indices);
  22   if (n_left == 64)
  23     {
  24       if (mask == ~0ULL)
  25         {
  26           clib_memcpy_u32 (dst, elts, 64);
  27           *bmp = ~0ULL;
  28           return dst + 64;
  29         }
  30     }
  31   else
  32     mask &= pow2_mask (n_left);
  33
  34   *bmp |= mask;
  35
  36 #if defined(CLIB_HAVE_VEC512_COMPRESS)
  37   u32x16u *ev = (u32x16u *) elts;
  38   for (int i = 0; i < 4; i++)
  39     {
  40       int cnt = _popcnt32 ((u16) mask);
  41       u32x16_compress_store (ev[i], mask, dst);
  42       dst += cnt;
  43       mask >>= 16;
  44     }
  45
  46 #elif defined(CLIB_HAVE_VEC256_COMPRESS)
  47   u32x8u *ev = (u32x8u *) elts;
  48   for (int i = 0; i < 8; i++)
  49     {
  50       int cnt = _popcnt32 ((u8) mask);
  51       u32x8_compress_store (ev[i], mask, dst);
  52       dst += cnt;
  53       mask >>= 8;
  54     }
  55 #elif defined(CLIB_HAVE_VEC256)
  56   while (mask)
  57     {
  58       u16 bit = count_trailing_zeros (mask);
  59       mask = clear_lowest_set_bit (mask);
  60       dst++[0] = elts[bit];
  61     }
  62 #else
  63   while (mask)
  64     {
  65       u16 bit = count_trailing_zeros (mask);
  66       mask ^= 1ULL << bit;
  67       dst++[0] = elts[bit];
  68     }
  69 #endif
  70 #else
  71   for (int i = 0; i < n_left; i++)
  72     {
  73       if (indices[i] == index)
  74         {
  75           dst++[0] = elts[i];
  76           mask |= 1ULL << i;
  77         }
  78     }
  79   *bmp |= mask;
  80 #endif
  81   return dst;
  82 }
  83
  84 static_always_inline u32
  85 extract_unused_elts_by_index (extract_data_t *d, u32 *elts, u16 *indices,
  86                               u16 index, int n_left, u32 *dst)
  87 {
  88   u32 *dst0 = dst;
  89   u64 *bmp = d->used_elts;
  90   while (n_left >= 64)
  91     {
  92       dst = extract_unused_elts_x64 (elts, indices, index, 64, bmp, dst);
  93
  94       /* next */
  95       indices += 64;
  96       elts += 64;
  97       bmp++;
  98       n_left -= 64;
  99     }
 100
 101   if (n_left)
 102     dst = extract_unused_elts_x64 (elts, indices, index, n_left, bmp, dst);
 103
 104   return dst - dst0;
 105 }
 106
 107 static_always_inline u32
 108 find_first_unused_elt (extract_data_t *d)
 109 {
 110   u64 *ue = d->used_elts + d->uword_offset;
 111
 112   while (PREDICT_FALSE (ue[0] == ~0))
 113     {
 114       ue++;
 115       d->uword_offset++;
 116     }
 117
 118   return d->uword_offset * 64 + count_trailing_zeros (~ue[0]);
 119 }
 120
 121 static_always_inline u32
 122 enqueue_one (vlib_main_t *vm, vlib_node_runtime_t *node, extract_data_t *d,
 123              u16 next_index, u32 *buffers, u16 *nexts, u32 n_buffers,
 124              u32 n_left, u32 *tmp)
 125 {
 126   vlib_frame_t *f;
 127   u32 n_extracted, n_free;
 128   u32 *to;
 129
 130   f = vlib_get_next_frame_internal (vm, node, next_index, 0);
 131
 132   n_free = VLIB_FRAME_SIZE - f->n_vectors;
 133
 134   /* if frame contains enough space for worst case scenario, we can avoid
 135    * use of tmp */
 136   if (n_free >= n_left)
 137     to = (u32 *) vlib_frame_vector_args (f) + f->n_vectors;
 138   else
 139     to = tmp;
 140
 141   n_extracted = extract_unused_elts_by_index (d, buffers, nexts, next_index,
 142                                               n_buffers, to);
 143
 144   if (to != tmp)
 145     {
 146       /* indices already written to frame, just close it */
 147       vlib_put_next_frame (vm, node, next_index, n_free - n_extracted);
 148     }
 149   else if (n_free >= n_extracted)
 150     {
 151       /* enough space in the existing frame */
 152       to = (u32 *) vlib_frame_vector_args (f) + f->n_vectors;
 153       vlib_buffer_copy_indices (to, tmp, n_extracted);
 154       vlib_put_next_frame (vm, node, next_index, n_free - n_extracted);
 155     }
 156   else
 157     {
 158       /* full frame */
 159       to = (u32 *) vlib_frame_vector_args (f) + f->n_vectors;
 160       vlib_buffer_copy_indices (to, tmp, n_free);
 161       vlib_put_next_frame (vm, node, next_index, 0);
 162
 163       /* second frame */
 164       u32 n_2nd_frame = n_extracted - n_free;
 165       f = vlib_get_next_frame_internal (vm, node, next_index, 1);
 166       to = vlib_frame_vector_args (f);
 167       vlib_buffer_copy_indices (to, tmp + n_free, n_2nd_frame);
 168       vlib_put_next_frame (vm, node, next_index,
 169                            VLIB_FRAME_SIZE - n_2nd_frame);
 170     }
 171
 172   return n_left - n_extracted;
 173 }
 174
 175 void __clib_section (".vlib_buffer_enqueue_to_next_fn")
 176 CLIB_MULTIARCH_FN (vlib_buffer_enqueue_to_next_fn)
 177 (vlib_main_t *vm, vlib_node_runtime_t *node, u32 *buffers, u16 *nexts,
 178  uword count)
 179 {
 180   u32 tmp[VLIB_FRAME_SIZE];
 181   u32 n_left;
 182   u16 next_index;
 183
 184   while (count >= VLIB_FRAME_SIZE)
 185     {
 186       extract_data_t d = {};
 187       n_left = VLIB_FRAME_SIZE;
 188
 189       next_index = nexts[0];
 190       n_left = enqueue_one (vm, node, &d, next_index, buffers, nexts,
 191                             VLIB_FRAME_SIZE, n_left, tmp);
 192
 193       while (n_left)
 194         {
 195           next_index = nexts[find_first_unused_elt (&d)];
 196           n_left = enqueue_one (vm, node, &d, next_index, buffers, nexts,
 197                                 VLIB_FRAME_SIZE, n_left, tmp);
 198         }
 199
 200       buffers += VLIB_FRAME_SIZE;
 201       nexts += VLIB_FRAME_SIZE;
 202       count -= VLIB_FRAME_SIZE;
 203     }
 204
 205   if (count)
 206     {
 207       extract_data_t d = {};
 208       next_index = nexts[0];
 209       n_left = count;
 210
 211       n_left = enqueue_one (vm, node, &d, next_index, buffers, nexts, count,
 212                             n_left, tmp);
 213
 214       while (n_left)
 215         {
 216           next_index = nexts[find_first_unused_elt (&d)];
 217           n_left = enqueue_one (vm, node, &d, next_index, buffers, nexts,
 218                                 count, n_left, tmp);
 219         }
 220     }
 221 }
 222
 223 CLIB_MARCH_FN_REGISTRATION (vlib_buffer_enqueue_to_next_fn);
 224
 225 void __clib_section (".vlib_buffer_enqueue_to_single_next_fn")
 226 CLIB_MULTIARCH_FN (vlib_buffer_enqueue_to_single_next_fn)
 227 (vlib_main_t *vm, vlib_node_runtime_t *node, u32 *buffers, u16 next_index,
 228  u32 count)
 229 {
 230   u32 *to_next, n_left_to_next, n_enq;
 231
 232   vlib_get_next_frame (vm, node, next_index, to_next, n_left_to_next);
 233
 234   if (PREDICT_TRUE (n_left_to_next >= count))
 235     {
 236       vlib_buffer_copy_indices (to_next, buffers, count);
 237       n_left_to_next -= count;
 238       vlib_put_next_frame (vm, node, next_index, n_left_to_next);
 239       return;
 240     }
 241
 242   n_enq = n_left_to_next;
 243 next:
 244   vlib_buffer_copy_indices (to_next, buffers, n_enq);
 245   n_left_to_next -= n_enq;
 246
 247   if (PREDICT_FALSE (count > n_enq))
 248     {
 249       count -= n_enq;
 250       buffers += n_enq;
 251
 252       vlib_put_next_frame (vm, node, next_index, n_left_to_next);
 253       vlib_get_next_frame (vm, node, next_index, to_next, n_left_to_next);
 254       n_enq = clib_min (n_left_to_next, count);
 255       goto next;
 256     }
 257   vlib_put_next_frame (vm, node, next_index, n_left_to_next);
 258 }
 259 CLIB_MARCH_FN_REGISTRATION (vlib_buffer_enqueue_to_single_next_fn);
 260
 261 u32 __clib_section (".vlib_buffer_enqueue_to_thread_fn")
 262 CLIB_MULTIARCH_FN (vlib_buffer_enqueue_to_thread_fn)
 263 (vlib_main_t *vm, u32 frame_queue_index, u32 *buffer_indices,
 264  u16 *thread_indices, u32 n_packets, int drop_on_congestion)
 265 {
 266   vlib_thread_main_t *tm = vlib_get_thread_main ();
 267   vlib_frame_queue_main_t *fqm;
 268   vlib_frame_queue_per_thread_data_t *ptd;
 269   u32 n_left = n_packets;
 270   u32 drop_list[VLIB_FRAME_SIZE], *dbi = drop_list, n_drop = 0;
 271   vlib_frame_queue_elt_t *hf = 0;
 272   u32 n_left_to_next_thread = 0, *to_next_thread = 0;
 273   u32 next_thread_index, current_thread_index = ~0;
 274   int i;
 275
 276   fqm = vec_elt_at_index (tm->frame_queue_mains, frame_queue_index);
 277   ptd = vec_elt_at_index (fqm->per_thread_data, vm->thread_index);
 278
 279   while (n_left)
 280     {
 281       next_thread_index = thread_indices[0];
 282
 283       if (next_thread_index != current_thread_index)
 284         {
 285           if (drop_on_congestion &&
 286               is_vlib_frame_queue_congested (
 287                 frame_queue_index, next_thread_index, fqm->queue_hi_thresh,
 288                 ptd->congested_handoff_queue_by_thread_index))
 289             {
 290               dbi[0] = buffer_indices[0];
 291               dbi++;
 292               n_drop++;
 293               goto next;
 294             }
 295
 296           if (hf)
 297             hf->n_vectors = VLIB_FRAME_SIZE - n_left_to_next_thread;
 298
 299           hf = vlib_get_worker_handoff_queue_elt (
 300             frame_queue_index, next_thread_index,
 301             ptd->handoff_queue_elt_by_thread_index);
 302
 303           n_left_to_next_thread = VLIB_FRAME_SIZE - hf->n_vectors;
 304           to_next_thread = &hf->buffer_index[hf->n_vectors];
 305           current_thread_index = next_thread_index;
 306         }
 307
 308       to_next_thread[0] = buffer_indices[0];
 309       to_next_thread++;
 310       n_left_to_next_thread--;
 311
 312       if (n_left_to_next_thread == 0)
 313         {
 314           hf->n_vectors = VLIB_FRAME_SIZE;
 315           vlib_put_frame_queue_elt (hf);
 316           vlib_get_main_by_index (current_thread_index)->check_frame_queues =
 317             1;
 318           current_thread_index = ~0;
 319           ptd->handoff_queue_elt_by_thread_index[next_thread_index] = 0;
 320           hf = 0;
 321         }
 322
 323       /* next */
 324     next:
 325       thread_indices += 1;
 326       buffer_indices += 1;
 327       n_left -= 1;
 328     }
 329
 330   if (hf)
 331     hf->n_vectors = VLIB_FRAME_SIZE - n_left_to_next_thread;
 332
 333   /* Ship frames to the thread nodes */
 334   for (i = 0; i < vec_len (ptd->handoff_queue_elt_by_thread_index); i++)
 335     {
 336       if (ptd->handoff_queue_elt_by_thread_index[i])
 337         {
 338           hf = ptd->handoff_queue_elt_by_thread_index[i];
 339           /*
 340            * It works better to let the handoff node
 341            * rate-adapt, always ship the handoff queue element.
 342            */
 343           if (1 || hf->n_vectors == hf->last_n_vectors)
 344             {
 345               vlib_put_frame_queue_elt (hf);
 346               vlib_get_main_by_index (i)->check_frame_queues = 1;
 347               ptd->handoff_queue_elt_by_thread_index[i] = 0;
 348             }
 349           else
 350             hf->last_n_vectors = hf->n_vectors;
 351         }
 352       ptd->congested_handoff_queue_by_thread_index[i] =
 353         (vlib_frame_queue_t *) (~0);
 354     }
 355
 356   if (drop_on_congestion && n_drop)
 357     vlib_buffer_free (vm, drop_list, n_drop);
 358
 359   return n_packets - n_drop;
 360 }
 361
 362 CLIB_MARCH_FN_REGISTRATION (vlib_buffer_enqueue_to_thread_fn);
 363
 364 #ifndef CLIB_MARCH_VARIANT
 365 vlib_buffer_func_main_t vlib_buffer_func_main;
 366
 367 static clib_error_t *
 368 vlib_buffer_funcs_init (vlib_main_t *vm)
 369 {
 370   vlib_buffer_func_main_t *bfm = &vlib_buffer_func_main;
 371   bfm->buffer_enqueue_to_next_fn =
 372     CLIB_MARCH_FN_POINTER (vlib_buffer_enqueue_to_next_fn);
 373   bfm->buffer_enqueue_to_single_next_fn =
 374     CLIB_MARCH_FN_POINTER (vlib_buffer_enqueue_to_single_next_fn);
 375   bfm->buffer_enqueue_to_thread_fn =
 376     CLIB_MARCH_FN_POINTER (vlib_buffer_enqueue_to_thread_fn);
 377   return 0;
 378 }
 379
 380 VLIB_INIT_FUNCTION (vlib_buffer_funcs_init);
 381 #endif