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/mask_compare.h>
   8 #include <vppinfra/vector/compress.h>
   9
  10 static_always_inline u32
  11 enqueue_one (vlib_main_t *vm, vlib_node_runtime_t *node,
  12              vlib_frame_bitmap_t used_elt_bmp, u16 next_index, u32 *buffers,
  13              u16 *nexts, u32 n_buffers, u32 n_left, u32 *tmp)
  14 {
  15   vlib_frame_bitmap_t match_bmp;
  16   vlib_frame_t *f;
  17   u32 n_extracted, n_free;
  18   u32 *to;
  19
  20   f = vlib_get_next_frame_internal (vm, node, next_index, 0);
  21
  22   n_free = VLIB_FRAME_SIZE - f->n_vectors;
  23
  24   /* if frame contains enough space for worst case scenario, we can avoid
  25    * use of tmp */
  26   if (n_free >= n_left)
  27     to = (u32 *) vlib_frame_vector_args (f) + f->n_vectors;
  28   else
  29     to = tmp;
  30
  31   clib_mask_compare_u16 (next_index, nexts, match_bmp, n_buffers);
  32   n_extracted = clib_compress_u32 (to, buffers, match_bmp, n_buffers);
  33   vlib_frame_bitmap_or (used_elt_bmp, match_bmp);
  34
  35   if (to != tmp)
  36     {
  37       /* indices already written to frame, just close it */
  38       vlib_put_next_frame (vm, node, next_index, n_free - n_extracted);
  39     }
  40   else if (n_free >= n_extracted)
  41     {
  42       /* enough space in the existing frame */
  43       to = (u32 *) vlib_frame_vector_args (f) + f->n_vectors;
  44       vlib_buffer_copy_indices (to, tmp, n_extracted);
  45       vlib_put_next_frame (vm, node, next_index, n_free - n_extracted);
  46     }
  47   else
  48     {
  49       /* full frame */
  50       to = (u32 *) vlib_frame_vector_args (f) + f->n_vectors;
  51       vlib_buffer_copy_indices (to, tmp, n_free);
  52       vlib_put_next_frame (vm, node, next_index, 0);
  53
  54       /* second frame */
  55       u32 n_2nd_frame = n_extracted - n_free;
  56       f = vlib_get_next_frame_internal (vm, node, next_index, 1);
  57       to = vlib_frame_vector_args (f);
  58       vlib_buffer_copy_indices (to, tmp + n_free, n_2nd_frame);
  59       vlib_put_next_frame (vm, node, next_index,
  60                            VLIB_FRAME_SIZE - n_2nd_frame);
  61     }
  62
  63   return n_left - n_extracted;
  64 }
  65
  66 void __clib_section (".vlib_buffer_enqueue_to_next_fn")
  67 CLIB_MULTIARCH_FN (vlib_buffer_enqueue_to_next_fn)
  68 (vlib_main_t *vm, vlib_node_runtime_t *node, u32 *buffers, u16 *nexts,
  69  uword count)
  70 {
  71   u32 tmp[VLIB_FRAME_SIZE];
  72   u32 n_left;
  73   u16 next_index;
  74
  75   while (count >= VLIB_FRAME_SIZE)
  76     {
  77       vlib_frame_bitmap_t used_elt_bmp = {};
  78       n_left = VLIB_FRAME_SIZE;
  79       u32 off = 0;
  80
  81       next_index = nexts[0];
  82       n_left = enqueue_one (vm, node, used_elt_bmp, next_index, buffers, nexts,
  83                             VLIB_FRAME_SIZE, n_left, tmp);
  84
  85       while (n_left)
  86         {
  87           while (PREDICT_FALSE (used_elt_bmp[off] == ~0))
  88             {
  89               off++;
  90               ASSERT (off < ARRAY_LEN (used_elt_bmp));
  91             }
  92
  93           next_index =
  94             nexts[off * 64 + count_trailing_zeros (~used_elt_bmp[off])];
  95           n_left = enqueue_one (vm, node, used_elt_bmp, next_index, buffers,
  96                                 nexts, VLIB_FRAME_SIZE, n_left, tmp);
  97         }
  98
  99       buffers += VLIB_FRAME_SIZE;
 100       nexts += VLIB_FRAME_SIZE;
 101       count -= VLIB_FRAME_SIZE;
 102     }
 103
 104   if (count)
 105     {
 106       vlib_frame_bitmap_t used_elt_bmp = {};
 107       next_index = nexts[0];
 108       n_left = count;
 109       u32 off = 0;
 110
 111       n_left = enqueue_one (vm, node, used_elt_bmp, next_index, buffers, nexts,
 112                             count, n_left, tmp);
 113
 114       while (n_left)
 115         {
 116           while (PREDICT_FALSE (used_elt_bmp[off] == ~0))
 117             {
 118               off++;
 119               ASSERT (off < ARRAY_LEN (used_elt_bmp));
 120             }
 121
 122           next_index =
 123             nexts[off * 64 + count_trailing_zeros (~used_elt_bmp[off])];
 124           n_left = enqueue_one (vm, node, used_elt_bmp, next_index, buffers,
 125                                 nexts, count, n_left, tmp);
 126         }
 127     }
 128 }
 129
 130 CLIB_MARCH_FN_REGISTRATION (vlib_buffer_enqueue_to_next_fn);
 131
 132 void __clib_section (".vlib_buffer_enqueue_to_single_next_fn")
 133 CLIB_MULTIARCH_FN (vlib_buffer_enqueue_to_single_next_fn)
 134 (vlib_main_t *vm, vlib_node_runtime_t *node, u32 *buffers, u16 next_index,
 135  u32 count)
 136 {
 137   u32 *to_next, n_left_to_next, n_enq;
 138
 139   vlib_get_next_frame (vm, node, next_index, to_next, n_left_to_next);
 140
 141   if (PREDICT_TRUE (n_left_to_next >= count))
 142     {
 143       vlib_buffer_copy_indices (to_next, buffers, count);
 144       n_left_to_next -= count;
 145       vlib_put_next_frame (vm, node, next_index, n_left_to_next);
 146       return;
 147     }
 148
 149   n_enq = n_left_to_next;
 150 next:
 151   vlib_buffer_copy_indices (to_next, buffers, n_enq);
 152   n_left_to_next -= n_enq;
 153
 154   if (PREDICT_FALSE (count > n_enq))
 155     {
 156       count -= n_enq;
 157       buffers += n_enq;
 158
 159       vlib_put_next_frame (vm, node, next_index, n_left_to_next);
 160       vlib_get_next_frame (vm, node, next_index, to_next, n_left_to_next);
 161       n_enq = clib_min (n_left_to_next, count);
 162       goto next;
 163     }
 164   vlib_put_next_frame (vm, node, next_index, n_left_to_next);
 165 }
 166 CLIB_MARCH_FN_REGISTRATION (vlib_buffer_enqueue_to_single_next_fn);
 167
 168 static inline vlib_frame_queue_elt_t *
 169 vlib_get_frame_queue_elt (vlib_frame_queue_main_t *fqm, u32 index,
 170                           int dont_wait)
 171 {
 172   vlib_frame_queue_t *fq;
 173   u64 nelts, tail, new_tail;
 174
 175   fq = fqm->vlib_frame_queues[index];
 176   ASSERT (fq);
 177   nelts = fq->nelts;
 178
 179 retry:
 180   tail = __atomic_load_n (&fq->tail, __ATOMIC_ACQUIRE);
 181   new_tail = tail + 1;
 182
 183   if (new_tail >= fq->head + nelts)
 184     {
 185       if (dont_wait)
 186         return 0;
 187
 188       /* Wait until a ring slot is available */
 189       while (new_tail >= fq->head + nelts)
 190         vlib_worker_thread_barrier_check ();
 191     }
 192
 193   if (!__atomic_compare_exchange_n (&fq->tail, &tail, new_tail, 0 /* weak */,
 194                                     __ATOMIC_RELAXED, __ATOMIC_RELAXED))
 195     goto retry;
 196
 197   return fq->elts + (new_tail & (nelts - 1));
 198 }
 199
 200 static_always_inline u32
 201 vlib_buffer_enqueue_to_thread_inline (vlib_main_t *vm,
 202                                       vlib_node_runtime_t *node,
 203                                       vlib_frame_queue_main_t *fqm,
 204                                       u32 *buffer_indices, u16 *thread_indices,
 205                                       u32 n_packets, int drop_on_congestion,
 206                                       int with_aux, u32 *aux_data)
 207 {
 208   u32 drop_list[VLIB_FRAME_SIZE], n_drop = 0;
 209   vlib_frame_bitmap_t mask, used_elts = {};
 210   vlib_frame_queue_elt_t *hf = 0;
 211   u16 thread_index;
 212   u32 n_comp, off = 0, n_left = n_packets;
 213
 214   thread_index = thread_indices[0];
 215
 216 more:
 217   clib_mask_compare_u16 (thread_index, thread_indices, mask, n_packets);
 218   hf = vlib_get_frame_queue_elt (fqm, thread_index, drop_on_congestion);
 219
 220   n_comp = clib_compress_u32 (hf ? hf->buffer_index : drop_list + n_drop,
 221                               buffer_indices, mask, n_packets);
 222   if (with_aux)
 223     clib_compress_u32 (hf ? hf->aux_data : drop_list + n_drop, aux_data, mask,
 224                        n_packets);
 225
 226   if (hf)
 227     {
 228       if (node->flags & VLIB_NODE_FLAG_TRACE)
 229         hf->maybe_trace = 1;
 230       hf->n_vectors = n_comp;
 231       __atomic_store_n (&hf->valid, 1, __ATOMIC_RELEASE);
 232       vlib_get_main_by_index (thread_index)->check_frame_queues = 1;
 233     }
 234   else
 235     n_drop += n_comp;
 236
 237   n_left -= n_comp;
 238
 239   if (n_left)
 240     {
 241       vlib_frame_bitmap_or (used_elts, mask);
 242
 243       while (PREDICT_FALSE (used_elts[off] == ~0))
 244         {
 245           off++;
 246           ASSERT (off < ARRAY_LEN (used_elts));
 247         }
 248
 249       thread_index =
 250         thread_indices[off * 64 + count_trailing_zeros (~used_elts[off])];
 251       goto more;
 252     }
 253
 254   if (drop_on_congestion && n_drop)
 255     vlib_buffer_free (vm, drop_list, n_drop);
 256
 257   return n_packets - n_drop;
 258 }
 259
 260 u32 __clib_section (".vlib_buffer_enqueue_to_thread_fn")
 261 CLIB_MULTIARCH_FN (vlib_buffer_enqueue_to_thread_fn)
 262 (vlib_main_t *vm, vlib_node_runtime_t *node, u32 frame_queue_index,
 263  u32 *buffer_indices, u16 *thread_indices, u32 n_packets,
 264  int drop_on_congestion)
 265 {
 266   vlib_thread_main_t *tm = vlib_get_thread_main ();
 267   vlib_frame_queue_main_t *fqm;
 268   u32 n_enq = 0;
 269
 270   fqm = vec_elt_at_index (tm->frame_queue_mains, frame_queue_index);
 271
 272   while (n_packets >= VLIB_FRAME_SIZE)
 273     {
 274       n_enq += vlib_buffer_enqueue_to_thread_inline (
 275         vm, node, fqm, buffer_indices, thread_indices, VLIB_FRAME_SIZE,
 276         drop_on_congestion, 0 /* with_aux */, NULL);
 277       buffer_indices += VLIB_FRAME_SIZE;
 278       thread_indices += VLIB_FRAME_SIZE;
 279       n_packets -= VLIB_FRAME_SIZE;
 280     }
 281
 282   if (n_packets == 0)
 283     return n_enq;
 284
 285   n_enq += vlib_buffer_enqueue_to_thread_inline (
 286     vm, node, fqm, buffer_indices, thread_indices, n_packets,
 287     drop_on_congestion, 0 /* with_aux */, NULL);
 288
 289   return n_enq;
 290 }
 291
 292 u32 __clib_section (".vlib_buffer_enqueue_to_thread_with_aux_fn")
 293 CLIB_MULTIARCH_FN (vlib_buffer_enqueue_to_thread_with_aux_fn)
 294 (vlib_main_t *vm, vlib_node_runtime_t *node, u32 frame_queue_index,
 295  u32 *buffer_indices, u32 *aux, u16 *thread_indices, u32 n_packets,
 296  int drop_on_congestion)
 297 {
 298   vlib_thread_main_t *tm = vlib_get_thread_main ();
 299   vlib_frame_queue_main_t *fqm;
 300   u32 n_enq = 0;
 301
 302   fqm = vec_elt_at_index (tm->frame_queue_mains, frame_queue_index);
 303
 304   while (n_packets >= VLIB_FRAME_SIZE)
 305     {
 306       n_enq += vlib_buffer_enqueue_to_thread_inline (
 307         vm, node, fqm, buffer_indices, thread_indices, VLIB_FRAME_SIZE,
 308         drop_on_congestion, 1 /* with_aux */, aux);
 309       buffer_indices += VLIB_FRAME_SIZE;
 310       thread_indices += VLIB_FRAME_SIZE;
 311       n_packets -= VLIB_FRAME_SIZE;
 312     }
 313
 314   if (n_packets == 0)
 315     return n_enq;
 316
 317   n_enq += vlib_buffer_enqueue_to_thread_inline (
 318     vm, node, fqm, buffer_indices, thread_indices, n_packets,
 319     drop_on_congestion, 1 /* with_aux */, aux);
 320
 321   return n_enq;
 322 }
 323
 324 CLIB_MARCH_FN_REGISTRATION (vlib_buffer_enqueue_to_thread_fn);
 325 CLIB_MARCH_FN_REGISTRATION (vlib_buffer_enqueue_to_thread_with_aux_fn);
 326
 327 static_always_inline u32
 328 vlib_frame_queue_dequeue_inline (vlib_main_t *vm, vlib_frame_queue_main_t *fqm,
 329                                  u8 with_aux)
 330 {
 331   u32 thread_id = vm->thread_index;
 332   vlib_frame_queue_t *fq = fqm->vlib_frame_queues[thread_id];
 333   u32 mask = fq->nelts - 1;
 334   vlib_frame_queue_elt_t *elt;
 335   u32 n_free, n_copy, *from, *from_aux, *to = 0, *to_aux = 0, processed = 0,
 336                                         vectors = 0;
 337   vlib_frame_t *f = 0;
 338
 339   ASSERT (fq);
 340   ASSERT (vm == vlib_global_main.vlib_mains[thread_id]);
 341
 342   if (PREDICT_FALSE (fqm->node_index == ~0))
 343     return 0;
 344   /*
 345    * Gather trace data for frame queues
 346    */
 347   if (PREDICT_FALSE (fq->trace))
 348     {
 349       frame_queue_trace_t *fqt;
 350       frame_queue_nelt_counter_t *fqh;
 351       u32 elix;
 352
 353       fqt = &fqm->frame_queue_traces[thread_id];
 354
 355       fqt->nelts = fq->nelts;
 356       fqt->head = fq->head;
 357       fqt->tail = fq->tail;
 358       fqt->threshold = fq->vector_threshold;
 359       fqt->n_in_use = fqt->tail - fqt->head;
 360       if (fqt->n_in_use >= fqt->nelts)
 361         {
 362           // if beyond max then use max
 363           fqt->n_in_use = fqt->nelts - 1;
 364         }
 365
 366       /* Record the number of elements in use in the histogram */
 367       fqh = &fqm->frame_queue_histogram[thread_id];
 368       fqh->count[fqt->n_in_use]++;
 369
 370       /* Record a snapshot of the elements in use */
 371       for (elix = 0; elix < fqt->nelts; elix++)
 372         {
 373           elt = fq->elts + ((fq->head + 1 + elix) & (mask));
 374           if (1 || elt->valid)
 375             {
 376               fqt->n_vectors[elix] = elt->n_vectors;
 377             }
 378         }
 379       fqt->written = 1;
 380     }
 381
 382   while (1)
 383     {
 384       if (fq->head == fq->tail)
 385         break;
 386
 387       elt = fq->elts + ((fq->head + 1) & mask);
 388
 389       if (!__atomic_load_n (&elt->valid, __ATOMIC_ACQUIRE))
 390         break;
 391
 392       from = elt->buffer_index + elt->offset;
 393       if (with_aux)
 394         from_aux = elt->aux_data + elt->offset;
 395       ASSERT (elt->offset + elt->n_vectors <= VLIB_FRAME_SIZE);
 396
 397       if (f == 0)
 398         {
 399           f = vlib_get_frame_to_node (vm, fqm->node_index);
 400           to = vlib_frame_vector_args (f);
 401           if (with_aux)
 402             to_aux = vlib_frame_aux_args (f);
 403           n_free = VLIB_FRAME_SIZE;
 404         }
 405
 406       if (elt->maybe_trace)
 407         f->frame_flags |= VLIB_NODE_FLAG_TRACE;
 408
 409       n_copy = clib_min (n_free, elt->n_vectors);
 410
 411       vlib_buffer_copy_indices (to, from, n_copy);
 412       to += n_copy;
 413       if (with_aux)
 414         {
 415           vlib_buffer_copy_indices (to_aux, from_aux, n_copy);
 416           to_aux += n_copy;
 417         }
 418
 419       n_free -= n_copy;
 420       vectors += n_copy;
 421
 422       if (n_free == 0)
 423         {
 424           f->n_vectors = VLIB_FRAME_SIZE;
 425           vlib_put_frame_to_node (vm, fqm->node_index, f);
 426           f = 0;
 427         }
 428
 429       if (n_copy < elt->n_vectors)
 430         {
 431           /* not empty - leave it on the ring */
 432           elt->n_vectors -= n_copy;
 433           elt->offset += n_copy;
 434         }
 435       else
 436         {
 437           /* empty - reset and bump head */
 438           u32 sz = STRUCT_OFFSET_OF (vlib_frame_queue_elt_t, end_of_reset);
 439           clib_memset (elt, 0, sz);
 440           __atomic_store_n (&fq->head, fq->head + 1, __ATOMIC_RELEASE);
 441           processed++;
 442         }
 443
 444       /* Limit the number of packets pushed into the graph */
 445       if (vectors >= fq->vector_threshold)
 446         break;
 447     }
 448
 449   if (f)
 450     {
 451       f->n_vectors = VLIB_FRAME_SIZE - n_free;
 452       vlib_put_frame_to_node (vm, fqm->node_index, f);
 453     }
 454
 455   return processed;
 456 }
 457
 458 u32 __clib_section (".vlib_frame_queue_dequeue_fn")
 459 CLIB_MULTIARCH_FN (vlib_frame_queue_dequeue_fn)
 460 (vlib_main_t *vm, vlib_frame_queue_main_t *fqm)
 461 {
 462   return vlib_frame_queue_dequeue_inline (vm, fqm, 0 /* with_aux */);
 463 }
 464
 465 CLIB_MARCH_FN_REGISTRATION (vlib_frame_queue_dequeue_fn);
 466
 467 u32 __clib_section (".vlib_frame_queue_dequeue_with_aux_fn")
 468 CLIB_MULTIARCH_FN (vlib_frame_queue_dequeue_with_aux_fn)
 469 (vlib_main_t *vm, vlib_frame_queue_main_t *fqm)
 470 {
 471   return vlib_frame_queue_dequeue_inline (vm, fqm, 1 /* with_aux */);
 472 }
 473
 474 CLIB_MARCH_FN_REGISTRATION (vlib_frame_queue_dequeue_with_aux_fn);
 475
 476 #ifndef CLIB_MARCH_VARIANT
 477 vlib_buffer_func_main_t vlib_buffer_func_main;
 478
 479 static clib_error_t *
 480 vlib_buffer_funcs_init (vlib_main_t *vm)
 481 {
 482   vlib_buffer_func_main_t *bfm = &vlib_buffer_func_main;
 483   bfm->buffer_enqueue_to_next_fn =
 484     CLIB_MARCH_FN_POINTER (vlib_buffer_enqueue_to_next_fn);
 485   bfm->buffer_enqueue_to_single_next_fn =
 486     CLIB_MARCH_FN_POINTER (vlib_buffer_enqueue_to_single_next_fn);
 487   bfm->buffer_enqueue_to_thread_fn =
 488     CLIB_MARCH_FN_POINTER (vlib_buffer_enqueue_to_thread_fn);
 489   bfm->buffer_enqueue_to_thread_with_aux_fn =
 490     CLIB_MARCH_FN_POINTER (vlib_buffer_enqueue_to_thread_with_aux_fn);
 491   return 0;
 492 }
 493
 494 VLIB_INIT_FUNCTION (vlib_buffer_funcs_init);
 495 #endif