src/svm/svm_fifo.c

   1 /*
   2  * Copyright (c) 2016 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 #include <svm/svm_fifo.h>
  17
  18 static inline u8
  19 position_lt (svm_fifo_t * f, u32 a, u32 b)
  20 {
  21   return (ooo_segment_distance_to_tail (f, a)
  22           < ooo_segment_distance_to_tail (f, b));
  23 }
  24
  25 static inline u8
  26 position_leq (svm_fifo_t * f, u32 a, u32 b)
  27 {
  28   return (ooo_segment_distance_to_tail (f, a)
  29           <= ooo_segment_distance_to_tail (f, b));
  30 }
  31
  32 static inline u8
  33 position_gt (svm_fifo_t * f, u32 a, u32 b)
  34 {
  35   return (ooo_segment_distance_to_tail (f, a)
  36           > ooo_segment_distance_to_tail (f, b));
  37 }
  38
  39 static inline u32
  40 position_diff (svm_fifo_t * f, u32 posa, u32 posb)
  41 {
  42   return ooo_segment_distance_to_tail (f, posa)
  43     - ooo_segment_distance_to_tail (f, posb);
  44 }
  45
  46 static inline u32
  47 ooo_segment_end_pos (svm_fifo_t * f, ooo_segment_t * s)
  48 {
  49   return (s->start + s->length) % f->nitems;
  50 }
  51
  52 u8 *
  53 format_ooo_segment (u8 * s, va_list * args)
  54 {
  55   ooo_segment_t *seg = va_arg (*args, ooo_segment_t *);
  56
  57   s = format (s, "pos %u, len %u, next %d, prev %d",
  58               seg->start, seg->length, seg->next, seg->prev);
  59   return s;
  60 }
  61
  62 u8 *
  63 format_ooo_list (u8 * s, va_list * args)
  64 {
  65   svm_fifo_t *f = va_arg (*args, svm_fifo_t *);
  66   u32 ooo_segment_index = f->ooos_list_head;
  67   ooo_segment_t *seg;
  68
  69   while (ooo_segment_index != OOO_SEGMENT_INVALID_INDEX)
  70     {
  71       seg = pool_elt_at_index (f->ooo_segments, ooo_segment_index);
  72       s = format (s, "  %U\n", format_ooo_segment, seg);
  73       ooo_segment_index = seg->next;
  74     }
  75   return s;
  76 }
  77
  78 u8 *
  79 format_svm_fifo (u8 * s, va_list * args)
  80 {
  81   svm_fifo_t *f = va_arg (*args, svm_fifo_t *);
  82   int verbose = va_arg (*args, int);
  83
  84   s = format (s, "cursize %u nitems %u has_event %d\n",
  85               f->cursize, f->nitems, f->has_event);
  86   s = format (s, " head %d tail %d\n", f->head, f->tail);
  87
  88   if (verbose > 1)
  89     s = format
  90       (s, " server session %d thread %d client session %d thread %d\n",
  91        f->master_session_index, f->master_thread_index,
  92        f->client_session_index, f->client_thread_index);
  93
  94   if (verbose)
  95     {
  96       s = format (s, " ooo pool %d active elts\n",
  97                   pool_elts (f->ooo_segments));
  98       if (svm_fifo_has_ooo_data (f))
  99         s = format (s, " %U", format_ooo_list, f);
 100     }
 101   return s;
 102 }
 103
 104 /** create an svm fifo, in the current heap. Fails vs blow up the process */
 105 svm_fifo_t *
 106 svm_fifo_create (u32 data_size_in_bytes)
 107 {
 108   svm_fifo_t *f;
 109
 110   f = clib_mem_alloc_aligned_or_null (sizeof (*f) + data_size_in_bytes,
 111                                       CLIB_CACHE_LINE_BYTES);
 112   if (f == 0)
 113     return 0;
 114
 115   memset (f, 0, sizeof (*f) + data_size_in_bytes);
 116   f->nitems = data_size_in_bytes;
 117   f->ooos_list_head = OOO_SEGMENT_INVALID_INDEX;
 118
 119   return (f);
 120 }
 121
 122 void
 123 svm_fifo_free (svm_fifo_t * f)
 124 {
 125   pool_free (f->ooo_segments);
 126   clib_mem_free (f);
 127 }
 128
 129 always_inline ooo_segment_t *
 130 ooo_segment_new (svm_fifo_t * f, u32 start, u32 length)
 131 {
 132   ooo_segment_t *s;
 133
 134   pool_get (f->ooo_segments, s);
 135
 136   s->start = start;
 137   s->length = length;
 138
 139   s->prev = s->next = OOO_SEGMENT_INVALID_INDEX;
 140
 141   return s;
 142 }
 143
 144 always_inline void
 145 ooo_segment_del (svm_fifo_t * f, u32 index)
 146 {
 147   ooo_segment_t *cur, *prev = 0, *next = 0;
 148   cur = pool_elt_at_index (f->ooo_segments, index);
 149
 150   if (cur->next != OOO_SEGMENT_INVALID_INDEX)
 151     {
 152       next = pool_elt_at_index (f->ooo_segments, cur->next);
 153       next->prev = cur->prev;
 154     }
 155
 156   if (cur->prev != OOO_SEGMENT_INVALID_INDEX)
 157     {
 158       prev = pool_elt_at_index (f->ooo_segments, cur->prev);
 159       prev->next = cur->next;
 160     }
 161   else
 162     {
 163       f->ooos_list_head = cur->next;
 164     }
 165
 166   pool_put (f->ooo_segments, cur);
 167 }
 168
 169 /**
 170  * Add segment to fifo's out-of-order segment list. Takes care of merging
 171  * adjacent segments and removing overlapping ones.
 172  */
 173 static void
 174 ooo_segment_add (svm_fifo_t * f, u32 offset, u32 length)
 175 {
 176   ooo_segment_t *s, *new_s, *prev, *next, *it;
 177   u32 new_index, s_end_pos, s_index;
 178   u32 normalized_position, normalized_end_position;
 179
 180   normalized_position = (f->tail + offset) % f->nitems;
 181   normalized_end_position = (f->tail + offset + length) % f->nitems;
 182
 183   f->ooos_newest = OOO_SEGMENT_INVALID_INDEX;
 184
 185   if (f->ooos_list_head == OOO_SEGMENT_INVALID_INDEX)
 186     {
 187       s = ooo_segment_new (f, normalized_position, length);
 188       f->ooos_list_head = s - f->ooo_segments;
 189       f->ooos_newest = f->ooos_list_head;
 190       return;
 191     }
 192
 193   /* Find first segment that starts after new segment */
 194   s = pool_elt_at_index (f->ooo_segments, f->ooos_list_head);
 195   while (s->next != OOO_SEGMENT_INVALID_INDEX
 196          && position_lt (f, s->start, normalized_position))
 197     s = pool_elt_at_index (f->ooo_segments, s->next);
 198
 199   /* If we have a previous and we overlap it, use it as starting point */
 200   prev = ooo_segment_get_prev (f, s);
 201   if (prev
 202       && position_leq (f, normalized_position, ooo_segment_end_pos (f, prev)))
 203     {
 204       s = prev;
 205       s_end_pos = ooo_segment_end_pos (f, s);
 206       goto merge;
 207     }
 208
 209   s_index = s - f->ooo_segments;
 210   s_end_pos = ooo_segment_end_pos (f, s);
 211
 212   /* No overlap, add before current segment */
 213   if (position_lt (f, normalized_end_position, s->start))
 214     {
 215       new_s = ooo_segment_new (f, normalized_position, length);
 216       new_index = new_s - f->ooo_segments;
 217
 218       /* Pool might've moved, get segment again */
 219       s = pool_elt_at_index (f->ooo_segments, s_index);
 220       if (s->prev != OOO_SEGMENT_INVALID_INDEX)
 221         {
 222           new_s->prev = s->prev;
 223           prev = pool_elt_at_index (f->ooo_segments, new_s->prev);
 224           prev->next = new_index;
 225         }
 226       else
 227         {
 228           /* New head */
 229           f->ooos_list_head = new_index;
 230         }
 231
 232       new_s->next = s_index;
 233       s->prev = new_index;
 234       f->ooos_newest = new_index;
 235       return;
 236     }
 237   /* No overlap, add after current segment */
 238   else if (position_gt (f, normalized_position, s_end_pos))
 239     {
 240       new_s = ooo_segment_new (f, normalized_position, length);
 241       new_index = new_s - f->ooo_segments;
 242
 243       /* Pool might've moved, get segment again */
 244       s = pool_elt_at_index (f->ooo_segments, s_index);
 245
 246       ASSERT (s->next == OOO_SEGMENT_INVALID_INDEX);
 247
 248       new_s->prev = s_index;
 249       s->next = new_index;
 250       f->ooos_newest = new_index;
 251
 252       return;
 253     }
 254
 255   /*
 256    * Merge needed
 257    */
 258
 259 merge:
 260
 261   /* Merge at head */
 262   if (position_lt (f, normalized_position, s->start))
 263     {
 264       s->start = normalized_position;
 265       s->length = position_diff (f, s_end_pos, s->start);
 266     }
 267   /* Overlapping tail */
 268   else if (position_gt (f, normalized_end_position, s_end_pos))
 269     {
 270       s->length = position_diff (f, normalized_end_position, s->start);
 271     }
 272   /* New segment completely covered by current one */
 273   else
 274     {
 275       /* Do Nothing */
 276       s = 0;
 277       goto done;
 278     }
 279
 280   /* The new segment's tail may cover multiple smaller ones */
 281   if (position_gt (f, normalized_end_position, s_end_pos))
 282     {
 283       /* Remove the completely overlapped segments */
 284       it = (s->next != OOO_SEGMENT_INVALID_INDEX) ?
 285         pool_elt_at_index (f->ooo_segments, s->next) : 0;
 286       while (it && position_leq (f, ooo_segment_end_pos (f, it),
 287                                  normalized_end_position))
 288         {
 289           next = (it->next != OOO_SEGMENT_INVALID_INDEX) ?
 290             pool_elt_at_index (f->ooo_segments, it->next) : 0;
 291           ooo_segment_del (f, it - f->ooo_segments);
 292           it = next;
 293         }
 294
 295       /* If partial overlap with last, merge */
 296       if (it && position_leq (f, it->start, normalized_end_position))
 297         {
 298           s->length = ooo_segment_end_pos (f, it) - s->start;
 299           ooo_segment_del (f, it - f->ooo_segments);
 300         }
 301     }
 302
 303 done:
 304   /* Most recently updated segment */
 305   if (s)
 306     f->ooos_newest = s - f->ooo_segments;
 307 }
 308
 309 /**
 310  * Removes segments that can now be enqueued because the fifo's tail has
 311  * advanced. Returns the number of bytes added to tail.
 312  */
 313 static int
 314 ooo_segment_try_collect (svm_fifo_t * f, u32 n_bytes_enqueued)
 315 {
 316   ooo_segment_t *s;
 317   u32 index, bytes = 0;
 318   i32 diff;
 319
 320   s = pool_elt_at_index (f->ooo_segments, f->ooos_list_head);
 321
 322   diff = (f->tail >= s->start) ?
 323     f->tail - s->start : f->nitems + f->tail - s->start;
 324
 325   if (diff > n_bytes_enqueued)
 326     return 0;
 327
 328   /* If last tail update overlaps one/multiple ooo segments, remove them */
 329   while (0 <= diff && diff < n_bytes_enqueued)
 330     {
 331       index = s - f->ooo_segments;
 332
 333       /* Segment end is beyond the tail. Advance tail and remove segment */
 334       if (s->length > diff)
 335         {
 336           bytes = s->length - diff;
 337           f->tail += bytes;
 338           f->tail %= f->nitems;
 339           ooo_segment_del (f, index);
 340           break;
 341         }
 342
 343       /* If we have next go on */
 344       if (s->next != OOO_SEGMENT_INVALID_INDEX)
 345         {
 346           s = pool_elt_at_index (f->ooo_segments, s->next);
 347           diff = (f->tail >= s->start) ?
 348             f->tail - s->start : f->nitems + f->tail - s->start;
 349           ooo_segment_del (f, index);
 350         }
 351       /* End of search */
 352       else
 353         {
 354           ooo_segment_del (f, index);
 355           break;
 356         }
 357     }
 358
 359   return bytes;
 360 }
 361
 362 static int
 363 svm_fifo_enqueue_internal (svm_fifo_t * f, u32 max_bytes, u8 * copy_from_here)
 364 {
 365   u32 total_copy_bytes, first_copy_bytes, second_copy_bytes;
 366   u32 cursize, nitems;
 367
 368   /* read cursize, which can only increase while we're working */
 369   cursize = svm_fifo_max_dequeue (f);
 370   f->ooos_newest = OOO_SEGMENT_INVALID_INDEX;
 371
 372   if (PREDICT_FALSE (cursize == f->nitems))
 373     return -2;                  /* fifo stuffed */
 374
 375   nitems = f->nitems;
 376
 377   /* Number of bytes we're going to copy */
 378   total_copy_bytes = (nitems - cursize) < max_bytes ?
 379     (nitems - cursize) : max_bytes;
 380
 381   if (PREDICT_TRUE (copy_from_here != 0))
 382     {
 383       /* Number of bytes in first copy segment */
 384       first_copy_bytes = ((nitems - f->tail) < total_copy_bytes)
 385         ? (nitems - f->tail) : total_copy_bytes;
 386
 387       clib_memcpy (&f->data[f->tail], copy_from_here, first_copy_bytes);
 388       f->tail += first_copy_bytes;
 389       f->tail = (f->tail == nitems) ? 0 : f->tail;
 390
 391       /* Number of bytes in second copy segment, if any */
 392       second_copy_bytes = total_copy_bytes - first_copy_bytes;
 393       if (second_copy_bytes)
 394         {
 395           clib_memcpy (&f->data[f->tail], copy_from_here + first_copy_bytes,
 396                        second_copy_bytes);
 397           f->tail += second_copy_bytes;
 398           f->tail = (f->tail == nitems) ? 0 : f->tail;
 399         }
 400     }
 401   else
 402     {
 403       /* Account for a zero-copy enqueue done elsewhere */
 404       ASSERT (max_bytes <= (nitems - cursize));
 405       f->tail += max_bytes;
 406       f->tail = f->tail % nitems;
 407       total_copy_bytes = max_bytes;
 408     }
 409
 410   /* Any out-of-order segments to collect? */
 411   if (PREDICT_FALSE (f->ooos_list_head != OOO_SEGMENT_INVALID_INDEX))
 412     total_copy_bytes += ooo_segment_try_collect (f, total_copy_bytes);
 413
 414   /* Atomically increase the queue length */
 415   __sync_fetch_and_add (&f->cursize, total_copy_bytes);
 416
 417   return (total_copy_bytes);
 418 }
 419
 420 int
 421 svm_fifo_enqueue_nowait (svm_fifo_t * f, u32 max_bytes, u8 * copy_from_here)
 422 {
 423   return svm_fifo_enqueue_internal (f, max_bytes, copy_from_here);
 424 }
 425
 426 /**
 427  * Enqueue a future segment.
 428  *
 429  * Two choices: either copies the entire segment, or copies nothing
 430  * Returns 0 of the entire segment was copied
 431  * Returns -1 if none of the segment was copied due to lack of space
 432  */
 433 static int
 434 svm_fifo_enqueue_with_offset_internal (svm_fifo_t * f,
 435                                        u32 offset,
 436                                        u32 required_bytes,
 437                                        u8 * copy_from_here)
 438 {
 439   u32 total_copy_bytes, first_copy_bytes, second_copy_bytes;
 440   u32 cursize, nitems, normalized_offset;
 441   u32 offset_from_tail;
 442
 443   f->ooos_newest = OOO_SEGMENT_INVALID_INDEX;
 444
 445   /* read cursize, which can only increase while we're working */
 446   cursize = svm_fifo_max_dequeue (f);
 447   nitems = f->nitems;
 448
 449   normalized_offset = (f->tail + offset) % nitems;
 450
 451   /* Will this request fit? */
 452   offset_from_tail = (nitems + normalized_offset - f->tail) % nitems;
 453   if ((required_bytes + offset_from_tail) > (nitems - cursize))
 454     return -1;
 455
 456   ooo_segment_add (f, offset, required_bytes);
 457
 458   /* Number of bytes we're going to copy */
 459   total_copy_bytes = required_bytes;
 460
 461   /* Number of bytes in first copy segment */
 462   first_copy_bytes = ((nitems - normalized_offset) < total_copy_bytes)
 463     ? (nitems - normalized_offset) : total_copy_bytes;
 464
 465   clib_memcpy (&f->data[normalized_offset], copy_from_here, first_copy_bytes);
 466
 467   /* Number of bytes in second copy segment, if any */
 468   second_copy_bytes = total_copy_bytes - first_copy_bytes;
 469   if (second_copy_bytes)
 470     {
 471       normalized_offset += first_copy_bytes;
 472       normalized_offset %= nitems;
 473
 474       ASSERT (normalized_offset == 0);
 475
 476       clib_memcpy (&f->data[normalized_offset],
 477                    copy_from_here + first_copy_bytes, second_copy_bytes);
 478     }
 479
 480   return (0);
 481 }
 482
 483
 484 int
 485 svm_fifo_enqueue_with_offset (svm_fifo_t * f,
 486                               u32 offset,
 487                               u32 required_bytes, u8 * copy_from_here)
 488 {
 489   return svm_fifo_enqueue_with_offset_internal (f, offset, required_bytes,
 490                                                 copy_from_here);
 491 }
 492
 493
 494 static int
 495 svm_fifo_dequeue_internal (svm_fifo_t * f, u32 max_bytes, u8 * copy_here)
 496 {
 497   u32 total_copy_bytes, first_copy_bytes, second_copy_bytes;
 498   u32 cursize, nitems;
 499
 500   /* read cursize, which can only increase while we're working */
 501   cursize = svm_fifo_max_dequeue (f);
 502   if (PREDICT_FALSE (cursize == 0))
 503     return -2;                  /* nothing in the fifo */
 504
 505   nitems = f->nitems;
 506
 507   /* Number of bytes we're going to copy */
 508   total_copy_bytes = (cursize < max_bytes) ? cursize : max_bytes;
 509
 510   if (PREDICT_TRUE (copy_here != 0))
 511     {
 512       /* Number of bytes in first copy segment */
 513       first_copy_bytes = ((nitems - f->head) < total_copy_bytes)
 514         ? (nitems - f->head) : total_copy_bytes;
 515       clib_memcpy (copy_here, &f->data[f->head], first_copy_bytes);
 516       f->head += first_copy_bytes;
 517       f->head = (f->head == nitems) ? 0 : f->head;
 518
 519       /* Number of bytes in second copy segment, if any */
 520       second_copy_bytes = total_copy_bytes - first_copy_bytes;
 521       if (second_copy_bytes)
 522         {
 523           clib_memcpy (copy_here + first_copy_bytes,
 524                        &f->data[f->head], second_copy_bytes);
 525           f->head += second_copy_bytes;
 526           f->head = (f->head == nitems) ? 0 : f->head;
 527         }
 528     }
 529   else
 530     {
 531       /* Account for a zero-copy dequeue done elsewhere */
 532       ASSERT (max_bytes <= cursize);
 533       f->head += max_bytes;
 534       f->head = f->head % nitems;
 535       cursize -= max_bytes;
 536       total_copy_bytes = max_bytes;
 537     }
 538
 539   __sync_fetch_and_sub (&f->cursize, total_copy_bytes);
 540
 541   return (total_copy_bytes);
 542 }
 543
 544 int
 545 svm_fifo_dequeue_nowait (svm_fifo_t * f, u32 max_bytes, u8 * copy_here)
 546 {
 547   return svm_fifo_dequeue_internal (f, max_bytes, copy_here);
 548 }
 549
 550 int
 551 svm_fifo_peek (svm_fifo_t * f, u32 relative_offset, u32 max_bytes,
 552                u8 * copy_here)
 553 {
 554   u32 total_copy_bytes, first_copy_bytes, second_copy_bytes;
 555   u32 cursize, nitems, real_head;
 556
 557   /* read cursize, which can only increase while we're working */
 558   cursize = svm_fifo_max_dequeue (f);
 559   if (PREDICT_FALSE (cursize < relative_offset))
 560     return -2;                  /* nothing in the fifo */
 561
 562   nitems = f->nitems;
 563   real_head = f->head + relative_offset;
 564   real_head = real_head >= nitems ? real_head - nitems : real_head;
 565
 566   /* Number of bytes we're going to copy */
 567   total_copy_bytes = (cursize - relative_offset < max_bytes) ?
 568     cursize - relative_offset : max_bytes;
 569
 570   if (PREDICT_TRUE (copy_here != 0))
 571     {
 572       /* Number of bytes in first copy segment */
 573       first_copy_bytes =
 574         ((nitems - real_head) < total_copy_bytes) ?
 575         (nitems - real_head) : total_copy_bytes;
 576       clib_memcpy (copy_here, &f->data[real_head], first_copy_bytes);
 577
 578       /* Number of bytes in second copy segment, if any */
 579       second_copy_bytes = total_copy_bytes - first_copy_bytes;
 580       if (second_copy_bytes)
 581         {
 582           clib_memcpy (copy_here + first_copy_bytes, &f->data[0],
 583                        second_copy_bytes);
 584         }
 585     }
 586   return total_copy_bytes;
 587 }
 588
 589 int
 590 svm_fifo_dequeue_drop (svm_fifo_t * f, u32 max_bytes)
 591 {
 592   u32 total_drop_bytes, first_drop_bytes, second_drop_bytes;
 593   u32 cursize, nitems;
 594
 595   /* read cursize, which can only increase while we're working */
 596   cursize = svm_fifo_max_dequeue (f);
 597   if (PREDICT_FALSE (cursize == 0))
 598     return -2;                  /* nothing in the fifo */
 599
 600   nitems = f->nitems;
 601
 602   /* Number of bytes we're going to drop */
 603   total_drop_bytes = (cursize < max_bytes) ? cursize : max_bytes;
 604
 605   /* Number of bytes in first copy segment */
 606   first_drop_bytes =
 607     ((nitems - f->head) < total_drop_bytes) ?
 608     (nitems - f->head) : total_drop_bytes;
 609   f->head += first_drop_bytes;
 610   f->head = (f->head == nitems) ? 0 : f->head;
 611
 612   /* Number of bytes in second drop segment, if any */
 613   second_drop_bytes = total_drop_bytes - first_drop_bytes;
 614   if (second_drop_bytes)
 615     {
 616       f->head += second_drop_bytes;
 617       f->head = (f->head == nitems) ? 0 : f->head;
 618     }
 619
 620   __sync_fetch_and_sub (&f->cursize, total_drop_bytes);
 621
 622   return total_drop_bytes;
 623 }
 624
 625 u32
 626 svm_fifo_number_ooo_segments (svm_fifo_t * f)
 627 {
 628   return pool_elts (f->ooo_segments);
 629 }
 630
 631 ooo_segment_t *
 632 svm_fifo_first_ooo_segment (svm_fifo_t * f)
 633 {
 634   return pool_elt_at_index (f->ooo_segments, f->ooos_list_head);
 635 }
 636
 637 /**
 638  * Set fifo pointers to requested offset
 639  */
 640 void
 641 svm_fifo_init_pointers (svm_fifo_t * f, u32 pointer)
 642 {
 643   f->head = f->tail = pointer % f->nitems;
 644 }
 645
 646 /*
 647  * fd.io coding-style-patch-verification: ON
 648  *
 649  * Local Variables:
 650  * eval: (c-set-style "gnu")
 651  * End:
 652  */