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