src/vlib/buffer_funcs.h

   1 /*
   2  * Copyright (c) 2015 Cisco and/or its affiliates.
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15 /*
  16  * buffer_funcs.h: VLIB buffer related functions/inlines
  17  *
  18  * Copyright (c) 2008 Eliot Dresselhaus
  19  *
  20  * Permission is hereby granted, free of charge, to any person obtaining
  21  * a copy of this software and associated documentation files (the
  22  * "Software"), to deal in the Software without restriction, including
  23  * without limitation the rights to use, copy, modify, merge, publish,
  24  * distribute, sublicense, and/or sell copies of the Software, and to
  25  * permit persons to whom the Software is furnished to do so, subject to
  26  * the following conditions:
  27  *
  28  * The above copyright notice and this permission notice shall be
  29  * included in all copies or substantial portions of the Software.
  30  *
  31  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  32  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  33  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  34  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  35  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  36  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  37  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  38  */
  39
  40 #ifndef included_vlib_buffer_funcs_h
  41 #define included_vlib_buffer_funcs_h
  42
  43 #include <vppinfra/hash.h>
  44 #include <vppinfra/fifo.h>
  45 #include <vppinfra/vector/index_to_ptr.h>
  46 #include <vlib/buffer.h>
  47 #include <vlib/physmem_funcs.h>
  48 #include <vlib/main.h>
  49 #include <vlib/node.h>
  50
  51 /** \file
  52     vlib buffer access methods.
  53 */
  54
  55 typedef void (vlib_buffer_enqueue_to_next_fn_t) (vlib_main_t *vm,
  56                                                  vlib_node_runtime_t *node,
  57                                                  u32 *buffers, u16 *nexts,
  58                                                  uword count);
  59 typedef void (vlib_buffer_enqueue_to_single_next_fn_t) (
  60   vlib_main_t *vm, vlib_node_runtime_t *node, u32 *ers, u16 next_index,
  61   u32 count);
  62
  63 typedef u32 (vlib_buffer_enqueue_to_thread_fn_t) (
  64   vlib_main_t *vm, vlib_node_runtime_t *node, u32 frame_queue_index,
  65   u32 *buffer_indices, u16 *thread_indices, u32 n_packets,
  66   int drop_on_congestion);
  67
  68 typedef u32 (vlib_frame_queue_dequeue_fn_t) (vlib_main_t *vm,
  69                                              vlib_frame_queue_main_t *fqm);
  70
  71 typedef struct
  72 {
  73   vlib_buffer_enqueue_to_next_fn_t *buffer_enqueue_to_next_fn;
  74   vlib_buffer_enqueue_to_single_next_fn_t *buffer_enqueue_to_single_next_fn;
  75   vlib_buffer_enqueue_to_thread_fn_t *buffer_enqueue_to_thread_fn;
  76   vlib_frame_queue_dequeue_fn_t *frame_queue_dequeue_fn;
  77 } vlib_buffer_func_main_t;
  78
  79 extern vlib_buffer_func_main_t vlib_buffer_func_main;
  80
  81 always_inline void
  82 vlib_buffer_validate (vlib_main_t * vm, vlib_buffer_t * b)
  83 {
  84   vlib_buffer_main_t *bm = vm->buffer_main;
  85   vlib_buffer_pool_t *bp;
  86
  87   /* reference count in allocated buffer always must be 1 or higher */
  88   ASSERT (b->ref_count > 0);
  89
  90   /* verify that buffer pool index is valid */
  91   bp = vec_elt_at_index (bm->buffer_pools, b->buffer_pool_index);
  92   ASSERT (pointer_to_uword (b) >= bp->start);
  93   ASSERT (pointer_to_uword (b) < bp->start + bp->size -
  94           (bp->data_size + sizeof (vlib_buffer_t)));
  95 }
  96
  97 always_inline void *
  98 vlib_buffer_ptr_from_index (uword buffer_mem_start, u32 buffer_index,
  99                             uword offset)
 100 {
 101   offset += ((uword) buffer_index) << CLIB_LOG2_CACHE_LINE_BYTES;
 102   return uword_to_pointer (buffer_mem_start + offset, vlib_buffer_t *);
 103 }
 104
 105 /** \brief Translate buffer index into buffer pointer
 106
 107     @param vm - (vlib_main_t *) vlib main data structure pointer
 108     @param buffer_index - (u32) buffer index
 109     @return - (vlib_buffer_t *) buffer pointer
 110 */
 111 always_inline vlib_buffer_t *
 112 vlib_get_buffer (vlib_main_t * vm, u32 buffer_index)
 113 {
 114   vlib_buffer_main_t *bm = vm->buffer_main;
 115   vlib_buffer_t *b;
 116
 117   b = vlib_buffer_ptr_from_index (bm->buffer_mem_start, buffer_index, 0);
 118   vlib_buffer_validate (vm, b);
 119   return b;
 120 }
 121
 122 static_always_inline u32
 123 vlib_buffer_get_default_data_size (vlib_main_t * vm)
 124 {
 125   return vm->buffer_main->default_data_size;
 126 }
 127
 128 static_always_inline void
 129 vlib_buffer_copy_indices (u32 * dst, u32 * src, u32 n_indices)
 130 {
 131   clib_memcpy_u32 (dst, src, n_indices);
 132 }
 133
 134 always_inline void
 135 vlib_buffer_copy_indices_from_ring (u32 * dst, u32 * ring, u32 start,
 136                                     u32 ring_size, u32 n_buffers)
 137 {
 138   ASSERT (n_buffers <= ring_size);
 139
 140   if (PREDICT_TRUE (start + n_buffers <= ring_size))
 141     {
 142       vlib_buffer_copy_indices (dst, ring + start, n_buffers);
 143     }
 144   else
 145     {
 146       u32 n = ring_size - start;
 147       vlib_buffer_copy_indices (dst, ring + start, n);
 148       vlib_buffer_copy_indices (dst + n, ring, n_buffers - n);
 149     }
 150 }
 151
 152 always_inline void
 153 vlib_buffer_copy_indices_to_ring (u32 * ring, u32 * src, u32 start,
 154                                   u32 ring_size, u32 n_buffers)
 155 {
 156   ASSERT (n_buffers <= ring_size);
 157
 158   if (PREDICT_TRUE (start + n_buffers <= ring_size))
 159     {
 160       vlib_buffer_copy_indices (ring + start, src, n_buffers);
 161     }
 162   else
 163     {
 164       u32 n = ring_size - start;
 165       vlib_buffer_copy_indices (ring + start, src, n);
 166       vlib_buffer_copy_indices (ring, src + n, n_buffers - n);
 167     }
 168 }
 169
 170 STATIC_ASSERT_OFFSET_OF (vlib_buffer_t, template_end, 64);
 171 static_always_inline void
 172 vlib_buffer_copy_template (vlib_buffer_t * b, vlib_buffer_t * bt)
 173 {
 174 #if defined CLIB_HAVE_VEC512
 175   b->as_u8x64[0] = bt->as_u8x64[0];
 176 #elif defined (CLIB_HAVE_VEC256)
 177   b->as_u8x32[0] = bt->as_u8x32[0];
 178   b->as_u8x32[1] = bt->as_u8x32[1];
 179 #elif defined (CLIB_HAVE_VEC128)
 180   b->as_u8x16[0] = bt->as_u8x16[0];
 181   b->as_u8x16[1] = bt->as_u8x16[1];
 182   b->as_u8x16[2] = bt->as_u8x16[2];
 183   b->as_u8x16[3] = bt->as_u8x16[3];
 184 #else
 185   clib_memcpy_fast (b, bt, 64);
 186 #endif
 187 }
 188
 189 always_inline u8
 190 vlib_buffer_pool_get_default_for_numa (vlib_main_t * vm, u32 numa_node)
 191 {
 192   ASSERT (numa_node < VLIB_BUFFER_MAX_NUMA_NODES);
 193   return vm->buffer_main->default_buffer_pool_index_for_numa[numa_node];
 194 }
 195
 196 /** \brief Translate array of buffer indices into buffer pointers with offset
 197
 198     @param vm - (vlib_main_t *) vlib main data structure pointer
 199     @param bi - (u32 *) array of buffer indices
 200     @param b - (void **) array to store buffer pointers
 201     @param count - (uword) number of elements
 202     @param offset - (i32) offset applied to each pointer
 203 */
 204 static_always_inline void
 205 vlib_get_buffers_with_offset (vlib_main_t *vm, u32 *bi, void **b, u32 count,
 206                               i32 offset)
 207 {
 208   uword buffer_mem_start = vm->buffer_main->buffer_mem_start;
 209   void *base = (void *) (buffer_mem_start + offset);
 210   int objsize = __builtin_object_size (b, 0);
 211   const int sh = CLIB_LOG2_CACHE_LINE_BYTES;
 212
 213   if (COMPILE_TIME_CONST (count) == 0 && objsize >= 64 * sizeof (b[0]) &&
 214       (objsize & ((8 * sizeof (b[0])) - 1)) == 0)
 215     {
 216       u32 n = round_pow2 (count, 8);
 217       ASSERT (objsize >= count);
 218       CLIB_ASSUME (objsize >= count);
 219       while (n >= 64)
 220         {
 221           clib_index_to_ptr_u32 (bi, base, sh, b, 64);
 222           b += 64;
 223           bi += 64;
 224           n -= 64;
 225         }
 226
 227       while (n)
 228         {
 229           clib_index_to_ptr_u32 (bi, base, sh, b, 8);
 230           b += 8;
 231           bi += 8;
 232           n -= 8;
 233         }
 234     }
 235   else
 236     clib_index_to_ptr_u32 (bi, base, sh, b, count);
 237 }
 238
 239 /** \brief Translate array of buffer indices into buffer pointers
 240
 241     @param vm - (vlib_main_t *) vlib main data structure pointer
 242     @param bi - (u32 *) array of buffer indices
 243     @param b - (vlib_buffer_t **) array to store buffer pointers
 244     @param count - (uword) number of elements
 245 */
 246
 247 static_always_inline void
 248 vlib_get_buffers (vlib_main_t *vm, u32 *bi, vlib_buffer_t **b, u32 count)
 249 {
 250   vlib_get_buffers_with_offset (vm, bi, (void **) b, count, 0);
 251 }
 252
 253 /** \brief Translate buffer pointer into buffer index
 254
 255     @param vm - (vlib_main_t *) vlib main data structure pointer
 256     @param p - (void *) buffer pointer
 257     @return - (u32) buffer index
 258 */
 259
 260 always_inline u32
 261 vlib_get_buffer_index (vlib_main_t * vm, void *p)
 262 {
 263   vlib_buffer_main_t *bm = vm->buffer_main;
 264   uword offset = pointer_to_uword (p) - bm->buffer_mem_start;
 265   ASSERT (pointer_to_uword (p) >= bm->buffer_mem_start);
 266   ASSERT (offset < bm->buffer_mem_size);
 267   ASSERT ((offset % (1 << CLIB_LOG2_CACHE_LINE_BYTES)) == 0);
 268   return offset >> CLIB_LOG2_CACHE_LINE_BYTES;
 269 }
 270
 271 /** \brief Translate array of buffer pointers into buffer indices with offset
 272
 273     @param vm - (vlib_main_t *) vlib main data structure pointer
 274     @param b - (void **) array of buffer pointers
 275     @param bi - (u32 *) array to store buffer indices
 276     @param count - (uword) number of elements
 277     @param offset - (i32) offset applied to each pointer
 278 */
 279 static_always_inline void
 280 vlib_get_buffer_indices_with_offset (vlib_main_t * vm, void **b, u32 * bi,
 281                                      uword count, i32 offset)
 282 {
 283 #ifdef CLIB_HAVE_VEC256
 284   u32x8 mask = { 0, 2, 4, 6, 1, 3, 5, 7 };
 285   u64x4 off4 = u64x4_splat (vm->buffer_main->buffer_mem_start - offset);
 286
 287   while (count >= 8)
 288     {
 289       /* load 4 pointers into 256-bit register */
 290       u64x4 v0 = u64x4_load_unaligned (b);
 291       u64x4 v1 = u64x4_load_unaligned (b + 4);
 292       u32x8 v2, v3;
 293
 294       v0 -= off4;
 295       v1 -= off4;
 296
 297       v0 >>= CLIB_LOG2_CACHE_LINE_BYTES;
 298       v1 >>= CLIB_LOG2_CACHE_LINE_BYTES;
 299
 300       /* permute 256-bit register so lower u32s of each buffer index are
 301        * placed into lower 128-bits */
 302       v2 = u32x8_permute ((u32x8) v0, mask);
 303       v3 = u32x8_permute ((u32x8) v1, mask);
 304
 305       /* extract lower 128-bits and save them to the array of buffer indices */
 306       u32x4_store_unaligned (u32x8_extract_lo (v2), bi);
 307       u32x4_store_unaligned (u32x8_extract_lo (v3), bi + 4);
 308       bi += 8;
 309       b += 8;
 310       count -= 8;
 311     }
 312 #endif
 313   while (count >= 4)
 314     {
 315       /* equivalent non-nector implementation */
 316       bi[0] = vlib_get_buffer_index (vm, ((u8 *) b[0]) + offset);
 317       bi[1] = vlib_get_buffer_index (vm, ((u8 *) b[1]) + offset);
 318       bi[2] = vlib_get_buffer_index (vm, ((u8 *) b[2]) + offset);
 319       bi[3] = vlib_get_buffer_index (vm, ((u8 *) b[3]) + offset);
 320       bi += 4;
 321       b += 4;
 322       count -= 4;
 323     }
 324   while (count)
 325     {
 326       bi[0] = vlib_get_buffer_index (vm, ((u8 *) b[0]) + offset);
 327       bi += 1;
 328       b += 1;
 329       count -= 1;
 330     }
 331 }
 332
 333 /** \brief Translate array of buffer pointers into buffer indices
 334
 335     @param vm - (vlib_main_t *) vlib main data structure pointer
 336     @param b - (vlib_buffer_t **) array of buffer pointers
 337     @param bi - (u32 *) array to store buffer indices
 338     @param count - (uword) number of elements
 339 */
 340 static_always_inline void
 341 vlib_get_buffer_indices (vlib_main_t * vm, vlib_buffer_t ** b, u32 * bi,
 342                          uword count)
 343 {
 344   vlib_get_buffer_indices_with_offset (vm, (void **) b, bi, count, 0);
 345 }
 346
 347 /** \brief Get next buffer in buffer linklist, or zero for end of list.
 348
 349     @param vm - (vlib_main_t *) vlib main data structure pointer
 350     @param b - (void *) buffer pointer
 351     @return - (vlib_buffer_t *) next buffer, or NULL
 352 */
 353 always_inline vlib_buffer_t *
 354 vlib_get_next_buffer (vlib_main_t * vm, vlib_buffer_t * b)
 355 {
 356   return (b->flags & VLIB_BUFFER_NEXT_PRESENT
 357           ? vlib_get_buffer (vm, b->next_buffer) : 0);
 358 }
 359
 360 uword vlib_buffer_length_in_chain_slow_path (vlib_main_t * vm,
 361                                              vlib_buffer_t * b_first);
 362
 363 /** \brief Get length in bytes of the buffer chain
 364
 365     @param vm - (vlib_main_t *) vlib main data structure pointer
 366     @param b - (void *) buffer pointer
 367     @return - (uword) length of buffer chain
 368 */
 369 always_inline uword
 370 vlib_buffer_length_in_chain (vlib_main_t * vm, vlib_buffer_t * b)
 371 {
 372   uword len = b->current_length;
 373
 374   if (PREDICT_TRUE ((b->flags & VLIB_BUFFER_NEXT_PRESENT) == 0))
 375     return len;
 376
 377   if (PREDICT_TRUE (b->flags & VLIB_BUFFER_TOTAL_LENGTH_VALID))
 378     return len + b->total_length_not_including_first_buffer;
 379
 380   return vlib_buffer_length_in_chain_slow_path (vm, b);
 381 }
 382
 383 /** \brief Get length in bytes of the buffer index buffer chain
 384
 385     @param vm - (vlib_main_t *) vlib main data structure pointer
 386     @param bi - (u32) buffer index
 387     @return - (uword) length of buffer chain
 388 */
 389 always_inline uword
 390 vlib_buffer_index_length_in_chain (vlib_main_t * vm, u32 bi)
 391 {
 392   vlib_buffer_t *b = vlib_get_buffer (vm, bi);
 393   return vlib_buffer_length_in_chain (vm, b);
 394 }
 395
 396 /** \brief Copy buffer contents to memory
 397
 398     @param vm - (vlib_main_t *) vlib main data structure pointer
 399     @param buffer_index - (u32) buffer index
 400     @param contents - (u8 *) memory, <strong>must be large enough</strong>
 401     @return - (uword) length of buffer chain
 402 */
 403 always_inline uword
 404 vlib_buffer_contents (vlib_main_t * vm, u32 buffer_index, u8 * contents)
 405 {
 406   uword content_len = 0;
 407   uword l;
 408   vlib_buffer_t *b;
 409
 410   while (1)
 411     {
 412       b = vlib_get_buffer (vm, buffer_index);
 413       l = b->current_length;
 414       clib_memcpy_fast (contents + content_len, b->data + b->current_data, l);
 415       content_len += l;
 416       if (!(b->flags & VLIB_BUFFER_NEXT_PRESENT))
 417         break;
 418       buffer_index = b->next_buffer;
 419     }
 420
 421   return content_len;
 422 }
 423
 424 always_inline uword
 425 vlib_buffer_get_pa (vlib_main_t * vm, vlib_buffer_t * b)
 426 {
 427   return vlib_physmem_get_pa (vm, b->data);
 428 }
 429
 430 always_inline uword
 431 vlib_buffer_get_current_pa (vlib_main_t * vm, vlib_buffer_t * b)
 432 {
 433   return vlib_buffer_get_pa (vm, b) + b->current_data;
 434 }
 435
 436 /** \brief Prefetch buffer metadata by buffer index
 437     The first 64 bytes of buffer contains most header information
 438
 439     @param vm - (vlib_main_t *) vlib main data structure pointer
 440     @param bi - (u32) buffer index
 441     @param type - LOAD, STORE. In most cases, STORE is the right answer
 442 */
 443 /* Prefetch buffer header given index. */
 444 #define vlib_prefetch_buffer_with_index(vm,bi,type)     \
 445   do {                                                  \
 446     vlib_buffer_t * _b = vlib_get_buffer (vm, bi);      \
 447     vlib_prefetch_buffer_header (_b, type);             \
 448   } while (0)
 449
 450 typedef enum
 451 {
 452   /* Index is unknown. */
 453   VLIB_BUFFER_UNKNOWN,
 454
 455   /* Index is known and free/allocated. */
 456   VLIB_BUFFER_KNOWN_FREE,
 457   VLIB_BUFFER_KNOWN_ALLOCATED,
 458 } vlib_buffer_known_state_t;
 459
 460 void vlib_buffer_validate_alloc_free (vlib_main_t * vm, u32 * buffers,
 461                                       uword n_buffers,
 462                                       vlib_buffer_known_state_t
 463                                       expected_state);
 464
 465 always_inline vlib_buffer_known_state_t
 466 vlib_buffer_is_known (vlib_main_t * vm, u32 buffer_index)
 467 {
 468   vlib_buffer_main_t *bm = vm->buffer_main;
 469
 470   clib_spinlock_lock (&bm->buffer_known_hash_lockp);
 471   uword *p = hash_get (bm->buffer_known_hash, buffer_index);
 472   clib_spinlock_unlock (&bm->buffer_known_hash_lockp);
 473   return p ? p[0] : VLIB_BUFFER_UNKNOWN;
 474 }
 475
 476 /* Validates sanity of a single buffer.
 477    Returns format'ed vector with error message if any. */
 478 u8 *vlib_validate_buffer (vlib_main_t * vm, u32 buffer_index,
 479                           uword follow_chain);
 480
 481 u8 *vlib_validate_buffers (vlib_main_t * vm,
 482                            u32 * buffers,
 483                            uword next_buffer_stride,
 484                            uword n_buffers,
 485                            vlib_buffer_known_state_t known_state,
 486                            uword follow_buffer_next);
 487
 488 static_always_inline vlib_buffer_pool_t *
 489 vlib_get_buffer_pool (vlib_main_t * vm, u8 buffer_pool_index)
 490 {
 491   vlib_buffer_main_t *bm = vm->buffer_main;
 492   return vec_elt_at_index (bm->buffer_pools, buffer_pool_index);
 493 }
 494
 495 static_always_inline __clib_warn_unused_result uword
 496 vlib_buffer_pool_get (vlib_main_t * vm, u8 buffer_pool_index, u32 * buffers,
 497                       u32 n_buffers)
 498 {
 499   vlib_buffer_pool_t *bp = vlib_get_buffer_pool (vm, buffer_pool_index);
 500   u32 len;
 501
 502   ASSERT (bp->buffers);
 503
 504   clib_spinlock_lock (&bp->lock);
 505   len = bp->n_avail;
 506   if (PREDICT_TRUE (n_buffers < len))
 507     {
 508       len -= n_buffers;
 509       vlib_buffer_copy_indices (buffers, bp->buffers + len, n_buffers);
 510       bp->n_avail = len;
 511       clib_spinlock_unlock (&bp->lock);
 512       return n_buffers;
 513     }
 514   else
 515     {
 516       vlib_buffer_copy_indices (buffers, bp->buffers, len);
 517       bp->n_avail = 0;
 518       clib_spinlock_unlock (&bp->lock);
 519       return len;
 520     }
 521 }
 522
 523
 524 /** \brief Allocate buffers from specific pool into supplied array
 525
 526     @param vm - (vlib_main_t *) vlib main data structure pointer
 527     @param buffers - (u32 * ) buffer index array
 528     @param n_buffers - (u32) number of buffers requested
 529     @return - (u32) number of buffers actually allocated, may be
 530     less than the number requested or zero
 531 */
 532
 533 always_inline __clib_warn_unused_result u32
 534 vlib_buffer_alloc_from_pool (vlib_main_t * vm, u32 * buffers, u32 n_buffers,
 535                              u8 buffer_pool_index)
 536 {
 537   vlib_buffer_main_t *bm = vm->buffer_main;
 538   vlib_buffer_pool_t *bp;
 539   vlib_buffer_pool_thread_t *bpt;
 540   u32 *src, *dst, len, n_left;
 541
 542   /* If buffer allocation fault injection is configured */
 543   if (VLIB_BUFFER_ALLOC_FAULT_INJECTOR > 0)
 544     {
 545       u32 vlib_buffer_alloc_may_fail (vlib_main_t *, u32);
 546
 547       /* See how many buffers we're willing to allocate */
 548       n_buffers = vlib_buffer_alloc_may_fail (vm, n_buffers);
 549       if (n_buffers == 0)
 550         return (n_buffers);
 551     }
 552
 553   bp = vec_elt_at_index (bm->buffer_pools, buffer_pool_index);
 554   bpt = vec_elt_at_index (bp->threads, vm->thread_index);
 555
 556   dst = buffers;
 557   n_left = n_buffers;
 558   len = bpt->n_cached;
 559
 560   /* per-thread cache contains enough buffers */
 561   if (len >= n_buffers)
 562     {
 563       src = bpt->cached_buffers + len - n_buffers;
 564       vlib_buffer_copy_indices (dst, src, n_buffers);
 565       bpt->n_cached -= n_buffers;
 566       goto done;
 567     }
 568
 569   /* alloc bigger than cache - take buffers directly from main pool */
 570   if (n_buffers >= VLIB_BUFFER_POOL_PER_THREAD_CACHE_SZ)
 571     {
 572       n_buffers = vlib_buffer_pool_get (vm, buffer_pool_index, buffers,
 573                                         n_buffers);
 574       goto done;
 575     }
 576
 577   /* take everything available in the cache */
 578   if (len)
 579     {
 580       vlib_buffer_copy_indices (dst, bpt->cached_buffers, len);
 581       bpt->n_cached = 0;
 582       dst += len;
 583       n_left -= len;
 584     }
 585
 586   len = round_pow2 (n_left, 32);
 587   len = vlib_buffer_pool_get (vm, buffer_pool_index, bpt->cached_buffers,
 588                               len);
 589   bpt->n_cached = len;
 590
 591   if (len)
 592     {
 593       u32 n_copy = clib_min (len, n_left);
 594       src = bpt->cached_buffers + len - n_copy;
 595       vlib_buffer_copy_indices (dst, src, n_copy);
 596       bpt->n_cached -= n_copy;
 597       n_left -= n_copy;
 598     }
 599
 600   n_buffers -= n_left;
 601
 602 done:
 603   /* Verify that buffers are known free. */
 604   if (CLIB_DEBUG > 0)
 605     vlib_buffer_validate_alloc_free (vm, buffers, n_buffers,
 606                                      VLIB_BUFFER_KNOWN_FREE);
 607   if (PREDICT_FALSE (bm->alloc_callback_fn != 0))
 608     bm->alloc_callback_fn (vm, buffer_pool_index, buffers, n_buffers);
 609   return n_buffers;
 610 }
 611
 612 /** \brief Allocate buffers from specific numa node into supplied array
 613
 614     @param vm - (vlib_main_t *) vlib main data structure pointer
 615     @param buffers - (u32 * ) buffer index array
 616     @param n_buffers - (u32) number of buffers requested
 617     @param numa_node - (u32) numa node
 618     @return - (u32) number of buffers actually allocated, may be
 619     less than the number requested or zero
 620 */
 621 always_inline __clib_warn_unused_result u32
 622 vlib_buffer_alloc_on_numa (vlib_main_t * vm, u32 * buffers, u32 n_buffers,
 623                            u32 numa_node)
 624 {
 625   u8 index = vlib_buffer_pool_get_default_for_numa (vm, numa_node);
 626   return vlib_buffer_alloc_from_pool (vm, buffers, n_buffers, index);
 627 }
 628
 629 /** \brief Allocate buffers into supplied array
 630
 631     @param vm - (vlib_main_t *) vlib main data structure pointer
 632     @param buffers - (u32 * ) buffer index array
 633     @param n_buffers - (u32) number of buffers requested
 634     @return - (u32) number of buffers actually allocated, may be
 635     less than the number requested or zero
 636 */
 637
 638 always_inline __clib_warn_unused_result u32
 639 vlib_buffer_alloc (vlib_main_t * vm, u32 * buffers, u32 n_buffers)
 640 {
 641   return vlib_buffer_alloc_on_numa (vm, buffers, n_buffers, vm->numa_node);
 642 }
 643
 644 /** \brief Allocate buffers into ring
 645
 646     @param vm - (vlib_main_t *) vlib main data structure pointer
 647     @param buffers - (u32 * ) buffer index ring
 648     @param start - (u32) first slot in the ring
 649     @param ring_size - (u32) ring size
 650     @param n_buffers - (u32) number of buffers requested
 651     @return - (u32) number of buffers actually allocated, may be
 652     less than the number requested or zero
 653 */
 654 always_inline __clib_warn_unused_result u32
 655 vlib_buffer_alloc_to_ring (vlib_main_t * vm, u32 * ring, u32 start,
 656                            u32 ring_size, u32 n_buffers)
 657 {
 658   u32 n_alloc;
 659
 660   ASSERT (n_buffers <= ring_size);
 661
 662   if (PREDICT_TRUE (start + n_buffers <= ring_size))
 663     return vlib_buffer_alloc (vm, ring + start, n_buffers);
 664
 665   n_alloc = vlib_buffer_alloc (vm, ring + start, ring_size - start);
 666
 667   if (PREDICT_TRUE (n_alloc == ring_size - start))
 668     n_alloc += vlib_buffer_alloc (vm, ring, n_buffers - n_alloc);
 669
 670   return n_alloc;
 671 }
 672
 673 /** \brief Allocate buffers into ring from specific buffer pool
 674
 675     @param vm - (vlib_main_t *) vlib main data structure pointer
 676     @param buffers - (u32 * ) buffer index ring
 677     @param start - (u32) first slot in the ring
 678     @param ring_size - (u32) ring size
 679     @param n_buffers - (u32) number of buffers requested
 680     @return - (u32) number of buffers actually allocated, may be
 681     less than the number requested or zero
 682 */
 683 always_inline __clib_warn_unused_result u32
 684 vlib_buffer_alloc_to_ring_from_pool (vlib_main_t * vm, u32 * ring, u32 start,
 685                                      u32 ring_size, u32 n_buffers,
 686                                      u8 buffer_pool_index)
 687 {
 688   u32 n_alloc;
 689
 690   ASSERT (n_buffers <= ring_size);
 691
 692   if (PREDICT_TRUE (start + n_buffers <= ring_size))
 693     return vlib_buffer_alloc_from_pool (vm, ring + start, n_buffers,
 694                                         buffer_pool_index);
 695
 696   n_alloc = vlib_buffer_alloc_from_pool (vm, ring + start, ring_size - start,
 697                                          buffer_pool_index);
 698
 699   if (PREDICT_TRUE (n_alloc == ring_size - start))
 700     n_alloc += vlib_buffer_alloc_from_pool (vm, ring, n_buffers - n_alloc,
 701                                             buffer_pool_index);
 702
 703   return n_alloc;
 704 }
 705
 706 static_always_inline void
 707 vlib_buffer_pool_put (vlib_main_t * vm, u8 buffer_pool_index,
 708                       u32 * buffers, u32 n_buffers)
 709 {
 710   vlib_buffer_main_t *bm = vm->buffer_main;
 711   vlib_buffer_pool_t *bp = vlib_get_buffer_pool (vm, buffer_pool_index);
 712   vlib_buffer_pool_thread_t *bpt = vec_elt_at_index (bp->threads,
 713                                                      vm->thread_index);
 714   u32 n_cached, n_empty;
 715
 716   if (CLIB_DEBUG > 0)
 717     vlib_buffer_validate_alloc_free (vm, buffers, n_buffers,
 718                                      VLIB_BUFFER_KNOWN_ALLOCATED);
 719   if (PREDICT_FALSE (bm->free_callback_fn != 0))
 720     bm->free_callback_fn (vm, buffer_pool_index, buffers, n_buffers);
 721
 722   n_cached = bpt->n_cached;
 723   n_empty = VLIB_BUFFER_POOL_PER_THREAD_CACHE_SZ - n_cached;
 724   if (n_buffers <= n_empty)
 725     {
 726       vlib_buffer_copy_indices (bpt->cached_buffers + n_cached,
 727                                 buffers, n_buffers);
 728       bpt->n_cached = n_cached + n_buffers;
 729       return;
 730     }
 731
 732   vlib_buffer_copy_indices (bpt->cached_buffers + n_cached,
 733                             buffers + n_buffers - n_empty, n_empty);
 734   bpt->n_cached = VLIB_BUFFER_POOL_PER_THREAD_CACHE_SZ;
 735
 736   clib_spinlock_lock (&bp->lock);
 737   vlib_buffer_copy_indices (bp->buffers + bp->n_avail, buffers,
 738                             n_buffers - n_empty);
 739   bp->n_avail += n_buffers - n_empty;
 740   clib_spinlock_unlock (&bp->lock);
 741 }
 742
 743 static_always_inline void
 744 vlib_buffer_free_inline (vlib_main_t * vm, u32 * buffers, u32 n_buffers,
 745                          int maybe_next)
 746 {
 747   const int queue_size = 128;
 748   vlib_buffer_pool_t *bp = 0;
 749   u8 buffer_pool_index = ~0;
 750   u32 n_queue = 0, queue[queue_size + 4];
 751   vlib_buffer_t bt = { };
 752 #if defined(CLIB_HAVE_VEC128)
 753   vlib_buffer_t bpi_mask = {.buffer_pool_index = ~0 };
 754   vlib_buffer_t bpi_vec = {};
 755   vlib_buffer_t flags_refs_mask = {
 756     .flags = VLIB_BUFFER_NEXT_PRESENT,
 757     .ref_count = ~1
 758   };
 759 #endif
 760
 761   if (PREDICT_FALSE (n_buffers == 0))
 762     return;
 763
 764   vlib_buffer_t *b = vlib_get_buffer (vm, buffers[0]);
 765   buffer_pool_index = b->buffer_pool_index;
 766   bp = vlib_get_buffer_pool (vm, buffer_pool_index);
 767   vlib_buffer_copy_template (&bt, &bp->buffer_template);
 768 #if defined(CLIB_HAVE_VEC128)
 769   bpi_vec.buffer_pool_index = buffer_pool_index;
 770 #endif
 771
 772   while (n_buffers)
 773     {
 774       vlib_buffer_t *b[8];
 775       u32 bi, sum = 0, flags, next;
 776
 777       if (n_buffers < 4)
 778         goto one_by_one;
 779
 780       vlib_get_buffers (vm, buffers, b, 4);
 781
 782       if (n_buffers >= 12)
 783         {
 784           vlib_get_buffers (vm, buffers + 8, b + 4, 4);
 785           vlib_prefetch_buffer_header (b[4], LOAD);
 786           vlib_prefetch_buffer_header (b[5], LOAD);
 787           vlib_prefetch_buffer_header (b[6], LOAD);
 788           vlib_prefetch_buffer_header (b[7], LOAD);
 789         }
 790
 791 #if defined(CLIB_HAVE_VEC128)
 792       u8x16 p0, p1, p2, p3, r;
 793       p0 = u8x16_load_unaligned (b[0]);
 794       p1 = u8x16_load_unaligned (b[1]);
 795       p2 = u8x16_load_unaligned (b[2]);
 796       p3 = u8x16_load_unaligned (b[3]);
 797
 798       r = p0 ^ bpi_vec.as_u8x16[0];
 799       r |= p1 ^ bpi_vec.as_u8x16[0];
 800       r |= p2 ^ bpi_vec.as_u8x16[0];
 801       r |= p3 ^ bpi_vec.as_u8x16[0];
 802       r &= bpi_mask.as_u8x16[0];
 803       r |= (p0 | p1 | p2 | p3) & flags_refs_mask.as_u8x16[0];
 804
 805       sum = !u8x16_is_all_zero (r);
 806 #else
 807       sum |= b[0]->flags;
 808       sum |= b[1]->flags;
 809       sum |= b[2]->flags;
 810       sum |= b[3]->flags;
 811       sum &= VLIB_BUFFER_NEXT_PRESENT;
 812       sum += b[0]->ref_count - 1;
 813       sum += b[1]->ref_count - 1;
 814       sum += b[2]->ref_count - 1;
 815       sum += b[3]->ref_count - 1;
 816       sum |= b[0]->buffer_pool_index ^ buffer_pool_index;
 817       sum |= b[1]->buffer_pool_index ^ buffer_pool_index;
 818       sum |= b[2]->buffer_pool_index ^ buffer_pool_index;
 819       sum |= b[3]->buffer_pool_index ^ buffer_pool_index;
 820 #endif
 821
 822       if (sum)
 823         goto one_by_one;
 824
 825       vlib_buffer_copy_indices (queue + n_queue, buffers, 4);
 826       vlib_buffer_copy_template (b[0], &bt);
 827       vlib_buffer_copy_template (b[1], &bt);
 828       vlib_buffer_copy_template (b[2], &bt);
 829       vlib_buffer_copy_template (b[3], &bt);
 830       n_queue += 4;
 831
 832       vlib_buffer_validate (vm, b[0]);
 833       vlib_buffer_validate (vm, b[1]);
 834       vlib_buffer_validate (vm, b[2]);
 835       vlib_buffer_validate (vm, b[3]);
 836
 837       VLIB_BUFFER_TRACE_TRAJECTORY_INIT (b[0]);
 838       VLIB_BUFFER_TRACE_TRAJECTORY_INIT (b[1]);
 839       VLIB_BUFFER_TRACE_TRAJECTORY_INIT (b[2]);
 840       VLIB_BUFFER_TRACE_TRAJECTORY_INIT (b[3]);
 841
 842       if (n_queue >= queue_size)
 843         {
 844           vlib_buffer_pool_put (vm, buffer_pool_index, queue, n_queue);
 845           n_queue = 0;
 846         }
 847       buffers += 4;
 848       n_buffers -= 4;
 849       continue;
 850
 851     one_by_one:
 852       bi = buffers[0];
 853
 854     next_in_chain:
 855       b[0] = vlib_get_buffer (vm, bi);
 856       flags = b[0]->flags;
 857       next = b[0]->next_buffer;
 858
 859       if (PREDICT_FALSE (buffer_pool_index != b[0]->buffer_pool_index))
 860         {
 861
 862           if (n_queue)
 863             {
 864               vlib_buffer_pool_put (vm, buffer_pool_index, queue, n_queue);
 865               n_queue = 0;
 866             }
 867
 868           buffer_pool_index = b[0]->buffer_pool_index;
 869 #if defined(CLIB_HAVE_VEC128)
 870           bpi_vec.buffer_pool_index = buffer_pool_index;
 871 #endif
 872           bp = vlib_get_buffer_pool (vm, buffer_pool_index);
 873           vlib_buffer_copy_template (&bt, &bp->buffer_template);
 874         }
 875
 876       vlib_buffer_validate (vm, b[0]);
 877
 878       VLIB_BUFFER_TRACE_TRAJECTORY_INIT (b[0]);
 879
 880       if (clib_atomic_sub_fetch (&b[0]->ref_count, 1) == 0)
 881         {
 882           vlib_buffer_copy_template (b[0], &bt);
 883           queue[n_queue++] = bi;
 884         }
 885
 886       if (n_queue == queue_size)
 887         {
 888           vlib_buffer_pool_put (vm, buffer_pool_index, queue, queue_size);
 889           n_queue = 0;
 890         }
 891
 892       if (maybe_next && (flags & VLIB_BUFFER_NEXT_PRESENT))
 893         {
 894           bi = next;
 895           goto next_in_chain;
 896         }
 897
 898       buffers++;
 899       n_buffers--;
 900     }
 901
 902   if (n_queue)
 903     vlib_buffer_pool_put (vm, buffer_pool_index, queue, n_queue);
 904 }
 905
 906
 907 /** \brief Free buffers
 908     Frees the entire buffer chain for each buffer
 909
 910     @param vm - (vlib_main_t *) vlib main data structure pointer
 911     @param buffers - (u32 * ) buffer index array
 912     @param n_buffers - (u32) number of buffers to free
 913
 914 */
 915 always_inline void
 916 vlib_buffer_free (vlib_main_t * vm,
 917                   /* pointer to first buffer */
 918                   u32 * buffers,
 919                   /* number of buffers to free */
 920                   u32 n_buffers)
 921 {
 922   vlib_buffer_free_inline (vm, buffers, n_buffers, /* maybe next */ 1);
 923 }
 924
 925 /** \brief Free buffers, does not free the buffer chain for each buffer
 926
 927     @param vm - (vlib_main_t *) vlib main data structure pointer
 928     @param buffers - (u32 * ) buffer index array
 929     @param n_buffers - (u32) number of buffers to free
 930
 931 */
 932 always_inline void
 933 vlib_buffer_free_no_next (vlib_main_t * vm,
 934                           /* pointer to first buffer */
 935                           u32 * buffers,
 936                           /* number of buffers to free */
 937                           u32 n_buffers)
 938 {
 939   vlib_buffer_free_inline (vm, buffers, n_buffers, /* maybe next */ 0);
 940 }
 941
 942 /** \brief Free one buffer
 943     Shorthand to free a single buffer chain.
 944
 945     @param vm - (vlib_main_t *) vlib main data structure pointer
 946     @param buffer_index - (u32) buffer index to free
 947 */
 948 always_inline void
 949 vlib_buffer_free_one (vlib_main_t * vm, u32 buffer_index)
 950 {
 951   vlib_buffer_free_inline (vm, &buffer_index, 1, /* maybe next */ 1);
 952 }
 953
 954 /** \brief Free buffers from ring
 955
 956     @param vm - (vlib_main_t *) vlib main data structure pointer
 957     @param buffers - (u32 * ) buffer index ring
 958     @param start - (u32) first slot in the ring
 959     @param ring_size - (u32) ring size
 960     @param n_buffers - (u32) number of buffers
 961 */
 962 always_inline void
 963 vlib_buffer_free_from_ring (vlib_main_t * vm, u32 * ring, u32 start,
 964                             u32 ring_size, u32 n_buffers)
 965 {
 966   ASSERT (n_buffers <= ring_size);
 967
 968   if (PREDICT_TRUE (start + n_buffers <= ring_size))
 969     {
 970       vlib_buffer_free (vm, ring + start, n_buffers);
 971     }
 972   else
 973     {
 974       vlib_buffer_free (vm, ring + start, ring_size - start);
 975       vlib_buffer_free (vm, ring, n_buffers - (ring_size - start));
 976     }
 977 }
 978
 979 /** \brief Free buffers from ring without freeing tail buffers
 980
 981     @param vm - (vlib_main_t *) vlib main data structure pointer
 982     @param buffers - (u32 * ) buffer index ring
 983     @param start - (u32) first slot in the ring
 984     @param ring_size - (u32) ring size
 985     @param n_buffers - (u32) number of buffers
 986 */
 987 always_inline void
 988 vlib_buffer_free_from_ring_no_next (vlib_main_t * vm, u32 * ring, u32 start,
 989                                     u32 ring_size, u32 n_buffers)
 990 {
 991   ASSERT (n_buffers <= ring_size);
 992
 993   if (PREDICT_TRUE (start + n_buffers <= ring_size))
 994     {
 995       vlib_buffer_free_no_next (vm, ring + start, n_buffers);
 996     }
 997   else
 998     {
 999       vlib_buffer_free_no_next (vm, ring + start, ring_size - start);
1000       vlib_buffer_free_no_next (vm, ring, n_buffers - (ring_size - start));
1001     }
1002 }
1003
1004 /* Append given data to end of buffer, possibly allocating new buffers. */
1005 int vlib_buffer_add_data (vlib_main_t * vm, u32 * buffer_index, void *data,
1006                           u32 n_data_bytes);
1007
1008 /* Define vlib_buffer and vnet_buffer flags bits preserved for copy/clone */
1009 #define VLIB_BUFFER_COPY_CLONE_FLAGS_MASK                       \
1010   (VLIB_BUFFER_NEXT_PRESENT | VLIB_BUFFER_TOTAL_LENGTH_VALID |  \
1011    VLIB_BUFFER_IS_TRACED | ~VLIB_BUFFER_FLAGS_ALL)
1012
1013 /* duplicate all buffers in chain */
1014 always_inline vlib_buffer_t *
1015 vlib_buffer_copy (vlib_main_t * vm, vlib_buffer_t * b)
1016 {
1017   vlib_buffer_t *s, *d, *fd;
1018   uword n_alloc, n_buffers = 1;
1019   u32 flag_mask = VLIB_BUFFER_COPY_CLONE_FLAGS_MASK;
1020   int i;
1021
1022   s = b;
1023   while (s->flags & VLIB_BUFFER_NEXT_PRESENT)
1024     {
1025       n_buffers++;
1026       s = vlib_get_buffer (vm, s->next_buffer);
1027     }
1028   u32 new_buffers[n_buffers];
1029
1030   n_alloc = vlib_buffer_alloc (vm, new_buffers, n_buffers);
1031
1032   /* No guarantee that we'll get all the buffers we asked for */
1033   if (PREDICT_FALSE (n_alloc < n_buffers))
1034     {
1035       if (n_alloc > 0)
1036         vlib_buffer_free (vm, new_buffers, n_alloc);
1037       return 0;
1038     }
1039
1040   /* 1st segment */
1041   s = b;
1042   fd = d = vlib_get_buffer (vm, new_buffers[0]);
1043   d->current_data = s->current_data;
1044   d->current_length = s->current_length;
1045   d->flags = s->flags & flag_mask;
1046   d->trace_handle = s->trace_handle;
1047   d->total_length_not_including_first_buffer =
1048     s->total_length_not_including_first_buffer;
1049   clib_memcpy_fast (d->opaque, s->opaque, sizeof (s->opaque));
1050   clib_memcpy_fast (d->opaque2, s->opaque2, sizeof (s->opaque2));
1051   clib_memcpy_fast (vlib_buffer_get_current (d),
1052                     vlib_buffer_get_current (s), s->current_length);
1053
1054   /* next segments */
1055   for (i = 1; i < n_buffers; i++)
1056     {
1057       /* previous */
1058       d->next_buffer = new_buffers[i];
1059       /* current */
1060       s = vlib_get_buffer (vm, s->next_buffer);
1061       d = vlib_get_buffer (vm, new_buffers[i]);
1062       d->current_data = s->current_data;
1063       d->current_length = s->current_length;
1064       clib_memcpy_fast (vlib_buffer_get_current (d),
1065                         vlib_buffer_get_current (s), s->current_length);
1066       d->flags = s->flags & flag_mask;
1067     }
1068
1069   return fd;
1070 }
1071
1072 /* duplicate first buffer in chain */
1073 always_inline vlib_buffer_t *
1074 vlib_buffer_copy_no_chain (vlib_main_t * vm, vlib_buffer_t * b, u32 * di)
1075 {
1076   vlib_buffer_t *d;
1077
1078   if ((vlib_buffer_alloc (vm, di, 1)) != 1)
1079     return 0;
1080
1081   d = vlib_get_buffer (vm, *di);
1082   /* 1st segment */
1083   d->current_data = b->current_data;
1084   d->current_length = b->current_length;
1085   clib_memcpy_fast (d->opaque, b->opaque, sizeof (b->opaque));
1086   clib_memcpy_fast (d->opaque2, b->opaque2, sizeof (b->opaque2));
1087   clib_memcpy_fast (vlib_buffer_get_current (d),
1088                     vlib_buffer_get_current (b), b->current_length);
1089
1090   return d;
1091 }
1092
1093 /*  \brief Move packet from current position to offset position in buffer.
1094     Only work for small packet using one buffer with room to fit the move
1095     @param vm - (vlib_main_t *) vlib main data structure pointer
1096     @param b -  (vlib_buffer_t *) pointer to buffer
1097     @param offset - (i16) position to move the packet in buffer
1098  */
1099 always_inline void
1100 vlib_buffer_move (vlib_main_t * vm, vlib_buffer_t * b, i16 offset)
1101 {
1102   ASSERT ((b->flags & VLIB_BUFFER_NEXT_PRESENT) == 0);
1103   ASSERT (offset + VLIB_BUFFER_PRE_DATA_SIZE >= 0);
1104   ASSERT (offset + b->current_length <
1105           vlib_buffer_get_default_data_size (vm));
1106
1107   u8 *source = vlib_buffer_get_current (b);
1108   b->current_data = offset;
1109   u8 *destination = vlib_buffer_get_current (b);
1110   u16 length = b->current_length;
1111
1112   if (source + length <= destination)   /* no overlap */
1113     clib_memcpy_fast (destination, source, length);
1114   else
1115     memmove (destination, source, length);
1116 }
1117
1118 /** \brief Create a maximum of 256 clones of buffer and store them
1119     in the supplied array
1120
1121     @param vm - (vlib_main_t *) vlib main data structure pointer
1122     @param src_buffer - (u32) source buffer index
1123     @param buffers - (u32 * ) buffer index array
1124     @param n_buffers - (u16) number of buffer clones requested (<=256)
1125     @param head_end_offset - (u16) offset relative to current position
1126            where packet head ends
1127     @param offset - (i16) copy packet head at current position if 0,
1128            else at offset position to change headroom space as specified
1129     @return - (u16) number of buffers actually cloned, may be
1130     less than the number requested or zero
1131 */
1132 always_inline u16
1133 vlib_buffer_clone_256 (vlib_main_t * vm, u32 src_buffer, u32 * buffers,
1134                        u16 n_buffers, u16 head_end_offset, i16 offset)
1135 {
1136   u16 i;
1137   vlib_buffer_t *s = vlib_get_buffer (vm, src_buffer);
1138
1139   ASSERT (s->ref_count == 1);
1140   ASSERT (n_buffers);
1141   ASSERT (n_buffers <= 256);
1142   ASSERT (offset + VLIB_BUFFER_PRE_DATA_SIZE >= 0);
1143   ASSERT ((offset + head_end_offset) <
1144           vlib_buffer_get_default_data_size (vm));
1145
1146   if (s->current_length <= head_end_offset + CLIB_CACHE_LINE_BYTES * 2)
1147     {
1148       buffers[0] = src_buffer;
1149       if (offset)
1150         vlib_buffer_move (vm, s, offset);
1151
1152       for (i = 1; i < n_buffers; i++)
1153         {
1154           vlib_buffer_t *d;
1155           d = vlib_buffer_copy (vm, s);
1156           if (d == 0)
1157             return i;
1158           buffers[i] = vlib_get_buffer_index (vm, d);
1159
1160         }
1161       return n_buffers;
1162     }
1163
1164   if (PREDICT_FALSE ((n_buffers == 1) && (offset == 0)))
1165     {
1166       buffers[0] = src_buffer;
1167       return 1;
1168     }
1169
1170   n_buffers = vlib_buffer_alloc_from_pool (vm, buffers, n_buffers,
1171                                            s->buffer_pool_index);
1172
1173   for (i = 0; i < n_buffers; i++)
1174     {
1175       vlib_buffer_t *d = vlib_get_buffer (vm, buffers[i]);
1176       if (offset)
1177         d->current_data = offset;
1178       else
1179         d->current_data = s->current_data;
1180
1181       d->current_length = head_end_offset;
1182       ASSERT (d->buffer_pool_index == s->buffer_pool_index);
1183
1184       d->total_length_not_including_first_buffer = s->current_length -
1185         head_end_offset;
1186       if (PREDICT_FALSE (s->flags & VLIB_BUFFER_NEXT_PRESENT))
1187         {
1188           d->total_length_not_including_first_buffer +=
1189             s->total_length_not_including_first_buffer;
1190         }
1191       d->flags = (s->flags & VLIB_BUFFER_COPY_CLONE_FLAGS_MASK) |
1192         VLIB_BUFFER_NEXT_PRESENT;
1193       d->trace_handle = s->trace_handle;
1194       clib_memcpy_fast (d->opaque, s->opaque, sizeof (s->opaque));
1195       clib_memcpy_fast (d->opaque2, s->opaque2, sizeof (s->opaque2));
1196       clib_memcpy_fast (vlib_buffer_get_current (d),
1197                         vlib_buffer_get_current (s), head_end_offset);
1198       d->next_buffer = src_buffer;
1199     }
1200   vlib_buffer_advance (s, head_end_offset);
1201   s->ref_count = n_buffers ? n_buffers : s->ref_count;
1202   while (s->flags & VLIB_BUFFER_NEXT_PRESENT)
1203     {
1204       s = vlib_get_buffer (vm, s->next_buffer);
1205       s->ref_count = n_buffers ? n_buffers : s->ref_count;
1206     }
1207
1208   return n_buffers;
1209 }
1210
1211 /** \brief Create multiple clones of buffer and store them
1212     in the supplied array
1213
1214     @param vm - (vlib_main_t *) vlib main data structure pointer
1215     @param src_buffer - (u32) source buffer index
1216     @param buffers - (u32 * ) buffer index array
1217     @param n_buffers - (u16) number of buffer clones requested (<=256)
1218     @param head_end_offset - (u16) offset relative to current position
1219            where packet head ends
1220     @param offset - (i16) copy packet head at current position if 0,
1221            else at offset position to change headroom space as specified
1222     @return - (u16) number of buffers actually cloned, may be
1223     less than the number requested or zero
1224 */
1225 always_inline u16
1226 vlib_buffer_clone_at_offset (vlib_main_t * vm, u32 src_buffer, u32 * buffers,
1227                              u16 n_buffers, u16 head_end_offset, i16 offset)
1228 {
1229   vlib_buffer_t *s = vlib_get_buffer (vm, src_buffer);
1230   u16 n_cloned = 0;
1231
1232   while (n_buffers > 256)
1233     {
1234       vlib_buffer_t *copy;
1235       copy = vlib_buffer_copy (vm, s);
1236       n_cloned += vlib_buffer_clone_256 (vm,
1237                                          vlib_get_buffer_index (vm, copy),
1238                                          (buffers + n_cloned),
1239                                          256, head_end_offset, offset);
1240       n_buffers -= 256;
1241     }
1242   n_cloned += vlib_buffer_clone_256 (vm, src_buffer,
1243                                      buffers + n_cloned,
1244                                      n_buffers, head_end_offset, offset);
1245
1246   return n_cloned;
1247 }
1248
1249 /** \brief Create multiple clones of buffer and store them
1250     in the supplied array
1251
1252     @param vm - (vlib_main_t *) vlib main data structure pointer
1253     @param src_buffer - (u32) source buffer index
1254     @param buffers - (u32 * ) buffer index array
1255     @param n_buffers - (u16) number of buffer clones requested (<=256)
1256     @param head_end_offset - (u16) offset relative to current position
1257            where packet head ends
1258     @return - (u16) number of buffers actually cloned, may be
1259     less than the number requested or zero
1260 */
1261 always_inline u16
1262 vlib_buffer_clone (vlib_main_t * vm, u32 src_buffer, u32 * buffers,
1263                    u16 n_buffers, u16 head_end_offset)
1264 {
1265   return vlib_buffer_clone_at_offset (vm, src_buffer, buffers, n_buffers,
1266                                       head_end_offset, 0);
1267 }
1268
1269 /** \brief Attach cloned tail to the buffer
1270
1271     @param vm - (vlib_main_t *) vlib main data structure pointer
1272     @param head - (vlib_buffer_t *) head buffer
1273     @param tail - (Vlib buffer_t *) tail buffer to clone and attach to head
1274 */
1275
1276 always_inline void
1277 vlib_buffer_attach_clone (vlib_main_t * vm, vlib_buffer_t * head,
1278                           vlib_buffer_t * tail)
1279 {
1280   ASSERT ((head->flags & VLIB_BUFFER_NEXT_PRESENT) == 0);
1281   ASSERT (head->buffer_pool_index == tail->buffer_pool_index);
1282
1283   head->flags |= VLIB_BUFFER_NEXT_PRESENT;
1284   head->flags &= ~VLIB_BUFFER_TOTAL_LENGTH_VALID;
1285   head->flags &= ~VLIB_BUFFER_EXT_HDR_VALID;
1286   head->flags |= (tail->flags & VLIB_BUFFER_TOTAL_LENGTH_VALID);
1287   head->next_buffer = vlib_get_buffer_index (vm, tail);
1288   head->total_length_not_including_first_buffer = tail->current_length +
1289     tail->total_length_not_including_first_buffer;
1290
1291 next_segment:
1292   clib_atomic_add_fetch (&tail->ref_count, 1);
1293
1294   if (tail->flags & VLIB_BUFFER_NEXT_PRESENT)
1295     {
1296       tail = vlib_get_buffer (vm, tail->next_buffer);
1297       goto next_segment;
1298     }
1299 }
1300
1301 /* Initializes the buffer as an empty packet with no chained buffers. */
1302 always_inline void
1303 vlib_buffer_chain_init (vlib_buffer_t * first)
1304 {
1305   first->total_length_not_including_first_buffer = 0;
1306   first->current_length = 0;
1307   first->flags &= ~VLIB_BUFFER_NEXT_PRESENT;
1308   first->flags |= VLIB_BUFFER_TOTAL_LENGTH_VALID;
1309 }
1310
1311 /* The provided next_bi buffer index is appended to the end of the packet. */
1312 always_inline vlib_buffer_t *
1313 vlib_buffer_chain_buffer (vlib_main_t * vm, vlib_buffer_t * last, u32 next_bi)
1314 {
1315   vlib_buffer_t *next_buffer = vlib_get_buffer (vm, next_bi);
1316   last->next_buffer = next_bi;
1317   last->flags |= VLIB_BUFFER_NEXT_PRESENT;
1318   next_buffer->current_length = 0;
1319   next_buffer->flags &= ~VLIB_BUFFER_NEXT_PRESENT;
1320   return next_buffer;
1321 }
1322
1323 /* Increases or decreases the packet length.
1324  * It does not allocate or deallocate new buffers.
1325  * Therefore, the added length must be compatible
1326  * with the last buffer. */
1327 always_inline void
1328 vlib_buffer_chain_increase_length (vlib_buffer_t * first,
1329                                    vlib_buffer_t * last, i32 len)
1330 {
1331   last->current_length += len;
1332   if (first != last)
1333     first->total_length_not_including_first_buffer += len;
1334 }
1335
1336 /* Copy data to the end of the packet and increases its length.
1337  * It does not allocate new buffers.
1338  * Returns the number of copied bytes. */
1339 always_inline u16
1340 vlib_buffer_chain_append_data (vlib_main_t * vm,
1341                                vlib_buffer_t * first,
1342                                vlib_buffer_t * last, void *data, u16 data_len)
1343 {
1344   u32 n_buffer_bytes = vlib_buffer_get_default_data_size (vm);
1345   ASSERT (n_buffer_bytes >= last->current_length + last->current_data);
1346   u16 len = clib_min (data_len,
1347                       n_buffer_bytes - last->current_length -
1348                       last->current_data);
1349   clib_memcpy_fast (vlib_buffer_get_current (last) + last->current_length,
1350                     data, len);
1351   vlib_buffer_chain_increase_length (first, last, len);
1352   return len;
1353 }
1354
1355 /* Copy data to the end of the packet and increases its length.
1356  * Allocates additional buffers from the free list if necessary.
1357  * Returns the number of copied bytes.
1358  * 'last' value is modified whenever new buffers are allocated and
1359  * chained and points to the last buffer in the chain. */
1360 u16
1361 vlib_buffer_chain_append_data_with_alloc (vlib_main_t * vm,
1362                                           vlib_buffer_t * first,
1363                                           vlib_buffer_t ** last, void *data,
1364                                           u16 data_len);
1365 void vlib_buffer_chain_validate (vlib_main_t * vm, vlib_buffer_t * first);
1366
1367 format_function_t format_vlib_buffer, format_vlib_buffer_and_data,
1368   format_vlib_buffer_contents, format_vlib_buffer_no_chain;
1369
1370 typedef struct
1371 {
1372   /* Vector of packet data. */
1373   u8 *packet_data;
1374
1375   /* Number of buffers to allocate in each call to allocator. */
1376   u32 min_n_buffers_each_alloc;
1377
1378   u8 *name;
1379 } vlib_packet_template_t;
1380
1381 void vlib_packet_template_init (vlib_main_t * vm,
1382                                 vlib_packet_template_t * t,
1383                                 void *packet_data,
1384                                 uword n_packet_data_bytes,
1385                                 uword min_n_buffers_each_alloc,
1386                                 char *fmt, ...);
1387
1388 void *vlib_packet_template_get_packet (vlib_main_t * vm,
1389                                        vlib_packet_template_t * t,
1390                                        u32 * bi_result);
1391
1392 always_inline void
1393 vlib_packet_template_free (vlib_main_t * vm, vlib_packet_template_t * t)
1394 {
1395   vec_free (t->packet_data);
1396 }
1397
1398 always_inline u32
1399 vlib_buffer_space_left_at_end (vlib_main_t * vm, vlib_buffer_t * b)
1400 {
1401   return b->data + vlib_buffer_get_default_data_size (vm) -
1402     ((u8 *) vlib_buffer_get_current (b) + b->current_length);
1403 }
1404
1405 #define VLIB_BUFFER_LINEARIZE_MAX 64
1406
1407 always_inline u32
1408 vlib_buffer_chain_linearize (vlib_main_t * vm, vlib_buffer_t * b)
1409 {
1410   vlib_buffer_t *dst_b;
1411   u32 n_buffers = 1, to_free = 0;
1412   u16 rem_len, dst_len, data_size, src_len = 0;
1413   u8 *dst, *src = 0;
1414
1415   if (PREDICT_TRUE ((b->flags & VLIB_BUFFER_NEXT_PRESENT) == 0))
1416     return 1;
1417
1418   ASSERT (1 == b->ref_count);
1419   if (PREDICT_FALSE (1 != b->ref_count))
1420     return 0;
1421
1422   data_size = vlib_buffer_get_default_data_size (vm);
1423   rem_len = vlib_buffer_length_in_chain (vm, b) - b->current_length;
1424
1425   dst_b = b;
1426   dst = vlib_buffer_get_tail (dst_b);
1427   dst_len = vlib_buffer_space_left_at_end (vm, dst_b);
1428
1429   b->total_length_not_including_first_buffer -= dst_len;
1430
1431   while (rem_len > 0)
1432     {
1433       u16 copy_len;
1434
1435       while (0 == src_len)
1436         {
1437           ASSERT (b->flags & VLIB_BUFFER_NEXT_PRESENT);
1438           if (PREDICT_FALSE (!(b->flags & VLIB_BUFFER_NEXT_PRESENT)))
1439             break; /* malformed chained buffer */
1440
1441           b = vlib_get_buffer (vm, b->next_buffer);
1442           src = vlib_buffer_get_current (b);
1443           src_len = b->current_length;
1444         }
1445
1446       if (0 == dst_len)
1447         {
1448           ASSERT (dst_b->flags & VLIB_BUFFER_NEXT_PRESENT);
1449           if (PREDICT_FALSE (!(dst_b->flags & VLIB_BUFFER_NEXT_PRESENT)))
1450             break; /* malformed chained buffer */
1451
1452           vlib_buffer_t *next_dst_b = vlib_get_buffer (vm, dst_b->next_buffer);
1453
1454           if (PREDICT_TRUE (1 == next_dst_b->ref_count))
1455             {
1456               /* normal case: buffer is not cloned, just use it */
1457               dst_b = next_dst_b;
1458             }
1459           else
1460             {
1461               /* cloned buffer, build a new dest chain from there */
1462               vlib_buffer_t *bufs[VLIB_BUFFER_LINEARIZE_MAX];
1463               u32 bis[VLIB_BUFFER_LINEARIZE_MAX + 1];
1464               const int n = (rem_len + data_size - 1) / data_size;
1465               int n_alloc;
1466               int i;
1467
1468               ASSERT (n <= VLIB_BUFFER_LINEARIZE_MAX);
1469               if (PREDICT_FALSE (n > VLIB_BUFFER_LINEARIZE_MAX))
1470                 return 0;
1471
1472               n_alloc = vlib_buffer_alloc (vm, bis, n);
1473               if (PREDICT_FALSE (n_alloc != n))
1474                 {
1475                   vlib_buffer_free (vm, bis, n_alloc);
1476                   return 0;
1477                 }
1478
1479               vlib_get_buffers (vm, bis, bufs, n);
1480
1481               for (i = 0; i < n - 1; i++)
1482                 {
1483                   bufs[i]->flags |= VLIB_BUFFER_NEXT_PRESENT;
1484                   bufs[i]->next_buffer = bis[i + 1];
1485                 }
1486
1487               to_free = dst_b->next_buffer;
1488               dst_b->next_buffer = bis[0];
1489               dst_b = bufs[0];
1490             }
1491
1492           n_buffers++;
1493
1494           dst_b->current_data = clib_min (0, dst_b->current_data);
1495           dst_b->current_length = 0;
1496
1497           dst = dst_b->data + dst_b->current_data;
1498           dst_len = data_size - dst_b->current_data;
1499         }
1500
1501       copy_len = clib_min (src_len, dst_len);
1502
1503       if (PREDICT_TRUE (src == dst))
1504         {
1505           /* nothing to do */
1506         }
1507       else if (src + copy_len > dst && dst + copy_len > src)
1508         {
1509           /* src and dst overlap */
1510           ASSERT (b == dst_b);
1511           memmove (dst, src, copy_len);
1512         }
1513       else
1514         {
1515           clib_memcpy_fast (dst, src, copy_len);
1516         }
1517
1518       dst_b->current_length += copy_len;
1519
1520       dst += copy_len;
1521       src += copy_len;
1522       dst_len -= copy_len;
1523       src_len -= copy_len;
1524       rem_len -= copy_len;
1525     }
1526
1527   /* in case of a malformed chain buffer, we'll exit early from the loop. */
1528   ASSERT (0 == rem_len);
1529   b->total_length_not_including_first_buffer -= rem_len;
1530
1531   if (to_free)
1532     vlib_buffer_free_one (vm, to_free);
1533
1534   if (dst_b->flags & VLIB_BUFFER_NEXT_PRESENT)
1535     {
1536       /* the resulting chain is smaller than the original, cut it there */
1537       dst_b->flags &= ~VLIB_BUFFER_NEXT_PRESENT;
1538       vlib_buffer_free_one (vm, dst_b->next_buffer);
1539       if (1 == n_buffers)
1540         {
1541           /* no longer a chained buffer */
1542           dst_b->flags &= ~VLIB_BUFFER_TOTAL_LENGTH_VALID;
1543           dst_b->total_length_not_including_first_buffer = 0;
1544         }
1545     }
1546
1547   return n_buffers;
1548 }
1549
1550 #endif /* included_vlib_buffer_funcs_h */
1551
1552 /*
1553  * fd.io coding-style-patch-verification: ON
1554  *
1555  * Local Variables:
1556  * eval: (c-set-style "gnu")
1557  * End:
1558  */