FD.io VPP  v18.10-34-gcce845e
Vector Packet Processing
svm_fifo.c
Go to the documentation of this file.
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 #include <vppinfra/cpu.h>
18 
19 static inline u8
21 {
22  return (ooo_segment_distance_from_tail (f, a)
24 }
25 
26 static inline u8
28 {
29  return (ooo_segment_distance_from_tail (f, a)
31 }
32 
33 static inline u8
35 {
36  return (ooo_segment_distance_from_tail (f, a)
38 }
39 
40 static inline u32
41 position_diff (svm_fifo_t * f, u32 posa, u32 posb)
42 {
43  return ooo_segment_distance_from_tail (f, posa)
45 }
46 
47 static inline u32
49 {
50  return (s->start + s->length) % f->nitems;
51 }
52 
53 #ifndef CLIB_MARCH_VARIANT
54 
55 u8 *
56 format_ooo_segment (u8 * s, va_list * args)
57 {
58  svm_fifo_t *f = va_arg (*args, svm_fifo_t *);
59  ooo_segment_t *seg = va_arg (*args, ooo_segment_t *);
60  u32 normalized_start = (seg->start + f->nitems - f->tail) % f->nitems;
61  s = format (s, "[%u, %u], len %u, next %d, prev %d", normalized_start,
62  (normalized_start + seg->length) % f->nitems, seg->length,
63  seg->next, seg->prev);
64  return s;
65 }
66 
67 u8 *
69 {
70 #if SVM_FIFO_TRACE
71  svm_fifo_trace_elem_t *seg = 0;
72  int i = 0;
73 
74  if (f->trace)
75  {
76  vec_foreach (seg, f->trace)
77  {
78  s = format (s, "{%u, %u, %u}, ", seg->offset, seg->len, seg->action);
79  i++;
80  if (i % 5 == 0)
81  s = format (s, "\n");
82  }
83  s = format (s, "\n");
84  }
85  return s;
86 #else
87  return 0;
88 #endif
89 }
90 
91 u8 *
92 svm_fifo_replay (u8 * s, svm_fifo_t * f, u8 no_read, u8 verbose)
93 {
94  int i, trace_len;
95  u8 *data = 0;
97  u32 offset;
98  svm_fifo_t *dummy_fifo;
99 
100  if (!f)
101  return s;
102 
103 #if SVM_FIFO_TRACE
104  trace = f->trace;
105  trace_len = vec_len (trace);
106 #else
107  trace = 0;
108  trace_len = 0;
109 #endif
110 
111  dummy_fifo = svm_fifo_create (f->nitems);
112  memset (f->data, 0xFF, f->nitems);
113 
114  vec_validate (data, f->nitems);
115  for (i = 0; i < vec_len (data); i++)
116  data[i] = i;
117 
118  for (i = 0; i < trace_len; i++)
119  {
120  offset = trace[i].offset;
121  if (trace[i].action == 1)
122  {
123  if (verbose)
124  s = format (s, "adding [%u, %u]:", trace[i].offset,
125  (trace[i].offset +
126  trace[i].len) % dummy_fifo->nitems);
127  svm_fifo_enqueue_with_offset (dummy_fifo, trace[i].offset,
128  trace[i].len, &data[offset]);
129  }
130  else if (trace[i].action == 2)
131  {
132  if (verbose)
133  s = format (s, "adding [%u, %u]:", 0, trace[i].len);
134  svm_fifo_enqueue_nowait (dummy_fifo, trace[i].len, &data[offset]);
135  }
136  else if (!no_read)
137  {
138  if (verbose)
139  s = format (s, "read: %u", trace[i].len);
140  svm_fifo_dequeue_drop (dummy_fifo, trace[i].len);
141  }
142  if (verbose)
143  s = format (s, "%U", format_svm_fifo, dummy_fifo, 1);
144  }
145 
146  s = format (s, "result: %U", format_svm_fifo, dummy_fifo, 1);
147 
148  return s;
149 }
150 
151 u8 *
152 format_ooo_list (u8 * s, va_list * args)
153 {
154  svm_fifo_t *f = va_arg (*args, svm_fifo_t *);
155  u32 ooo_segment_index = f->ooos_list_head;
156  ooo_segment_t *seg;
157 
158  while (ooo_segment_index != OOO_SEGMENT_INVALID_INDEX)
159  {
160  seg = pool_elt_at_index (f->ooo_segments, ooo_segment_index);
161  s = format (s, " %U\n", format_ooo_segment, f, seg);
162  ooo_segment_index = seg->next;
163  }
164 
165  return s;
166 }
167 
168 u8 *
169 format_svm_fifo (u8 * s, va_list * args)
170 {
171  svm_fifo_t *f = va_arg (*args, svm_fifo_t *);
172  int verbose = va_arg (*args, int);
173 
174  if (!s)
175  return s;
176 
177  s = format (s, "cursize %u nitems %u has_event %d\n",
178  f->cursize, f->nitems, f->has_event);
179  s = format (s, " head %d tail %d segment manager %u\n", f->head, f->tail,
180  f->segment_manager);
181 
182  if (verbose > 1)
183  s = format
184  (s, " vpp session %d thread %d app session %d thread %d\n",
185  f->master_session_index, f->master_thread_index,
186  f->client_session_index, f->client_thread_index);
187 
188  if (verbose)
189  {
190  s = format (s, " ooo pool %d active elts newest %u\n",
191  pool_elts (f->ooo_segments), f->ooos_newest);
192  if (svm_fifo_has_ooo_data (f))
193  s = format (s, " %U", format_ooo_list, f, verbose);
194  }
195  return s;
196 }
197 
198 /** create an svm fifo, in the current heap. Fails vs blow up the process */
199 svm_fifo_t *
200 svm_fifo_create (u32 data_size_in_bytes)
201 {
202  svm_fifo_t *f;
203  u32 rounded_data_size;
204 
205  /* always round fifo data size to the next highest power-of-two */
206  rounded_data_size = (1 << (max_log2 (data_size_in_bytes)));
207  f = clib_mem_alloc_aligned_or_null (sizeof (*f) + rounded_data_size,
209  if (f == 0)
210  return 0;
211 
212  memset (f, 0, sizeof (*f));
213  f->nitems = data_size_in_bytes;
214  f->ooos_list_head = OOO_SEGMENT_INVALID_INDEX;
215  f->ct_session_index = SVM_FIFO_INVALID_SESSION_INDEX;
216  f->refcnt = 1;
217  return (f);
218 }
219 
220 void
222 {
223  ASSERT (f->refcnt > 0);
224 
225  if (--f->refcnt == 0)
226  {
227  pool_free (f->ooo_segments);
228  clib_mem_free (f);
229  }
230 }
231 #endif
232 
234 ooo_segment_new (svm_fifo_t * f, u32 start, u32 length)
235 {
236  ooo_segment_t *s;
237 
238  pool_get (f->ooo_segments, s);
239 
240  s->start = start;
241  s->length = length;
242 
244 
245  return s;
246 }
247 
248 always_inline void
250 {
251  ooo_segment_t *cur, *prev = 0, *next = 0;
252  cur = pool_elt_at_index (f->ooo_segments, index);
253 
254  if (cur->next != OOO_SEGMENT_INVALID_INDEX)
255  {
256  next = pool_elt_at_index (f->ooo_segments, cur->next);
257  next->prev = cur->prev;
258  }
259 
260  if (cur->prev != OOO_SEGMENT_INVALID_INDEX)
261  {
262  prev = pool_elt_at_index (f->ooo_segments, cur->prev);
263  prev->next = cur->next;
264  }
265  else
266  {
267  f->ooos_list_head = cur->next;
268  }
269 
270  pool_put (f->ooo_segments, cur);
271 }
272 
273 /**
274  * Add segment to fifo's out-of-order segment list. Takes care of merging
275  * adjacent segments and removing overlapping ones.
276  */
277 static void
279 {
280  ooo_segment_t *s, *new_s, *prev, *next, *it;
281  u32 new_index, s_end_pos, s_index;
282  u32 normalized_position, normalized_end_position;
283 
284  ASSERT (offset + length <= ooo_segment_distance_from_tail (f, f->head));
285  normalized_position = (f->tail + offset) % f->nitems;
286  normalized_end_position = (f->tail + offset + length) % f->nitems;
287 
288  f->ooos_newest = OOO_SEGMENT_INVALID_INDEX;
289 
290  if (f->ooos_list_head == OOO_SEGMENT_INVALID_INDEX)
291  {
292  s = ooo_segment_new (f, normalized_position, length);
293  f->ooos_list_head = s - f->ooo_segments;
294  f->ooos_newest = f->ooos_list_head;
295  return;
296  }
297 
298  /* Find first segment that starts after new segment */
299  s = pool_elt_at_index (f->ooo_segments, f->ooos_list_head);
300  while (s->next != OOO_SEGMENT_INVALID_INDEX
301  && position_lt (f, s->start, normalized_position))
302  s = pool_elt_at_index (f->ooo_segments, s->next);
303 
304  /* If we have a previous and we overlap it, use it as starting point */
305  prev = ooo_segment_get_prev (f, s);
306  if (prev
307  && position_leq (f, normalized_position, ooo_segment_end_pos (f, prev)))
308  {
309  s = prev;
310  s_end_pos = ooo_segment_end_pos (f, s);
311 
312  /* Since we have previous, normalized start position cannot be smaller
313  * than prev->start. Check tail */
314  ASSERT (position_lt (f, s->start, normalized_position));
315  goto check_tail;
316  }
317 
318  s_index = s - f->ooo_segments;
319  s_end_pos = ooo_segment_end_pos (f, s);
320 
321  /* No overlap, add before current segment */
322  if (position_lt (f, normalized_end_position, s->start))
323  {
324  new_s = ooo_segment_new (f, normalized_position, length);
325  new_index = new_s - f->ooo_segments;
326 
327  /* Pool might've moved, get segment again */
328  s = pool_elt_at_index (f->ooo_segments, s_index);
330  {
331  new_s->prev = s->prev;
332  prev = pool_elt_at_index (f->ooo_segments, new_s->prev);
333  prev->next = new_index;
334  }
335  else
336  {
337  /* New head */
338  f->ooos_list_head = new_index;
339  }
340 
341  new_s->next = s_index;
342  s->prev = new_index;
343  f->ooos_newest = new_index;
344  return;
345  }
346  /* No overlap, add after current segment */
347  else if (position_gt (f, normalized_position, s_end_pos))
348  {
349  new_s = ooo_segment_new (f, normalized_position, length);
350  new_index = new_s - f->ooo_segments;
351 
352  /* Pool might've moved, get segment again */
353  s = pool_elt_at_index (f->ooo_segments, s_index);
354 
355  /* Needs to be last */
357 
358  new_s->prev = s_index;
359  s->next = new_index;
360  f->ooos_newest = new_index;
361 
362  return;
363  }
364 
365  /*
366  * Merge needed
367  */
368 
369  /* Merge at head */
370  if (position_lt (f, normalized_position, s->start))
371  {
372  s->start = normalized_position;
373  s->length = position_diff (f, s_end_pos, s->start);
374  f->ooos_newest = s - f->ooo_segments;
375  }
376 
377 check_tail:
378 
379  /* Overlapping tail */
380  if (position_gt (f, normalized_end_position, s_end_pos))
381  {
382  s->length = position_diff (f, normalized_end_position, s->start);
383 
384  /* Remove the completely overlapped segments in the tail */
385  it = ooo_segment_next (f, s);
386  while (it && position_leq (f, ooo_segment_end_pos (f, it),
387  normalized_end_position))
388  {
389  next = ooo_segment_next (f, it);
390  ooo_segment_del (f, it - f->ooo_segments);
391  it = next;
392  }
393 
394  /* If partial overlap with last, merge */
395  if (it && position_leq (f, it->start, normalized_end_position))
396  {
397  s->length = position_diff (f, ooo_segment_end_pos (f, it),
398  s->start);
399  ooo_segment_del (f, it - f->ooo_segments);
400  }
401  f->ooos_newest = s - f->ooo_segments;
402  }
403 }
404 
405 /**
406  * Removes segments that can now be enqueued because the fifo's tail has
407  * advanced. Returns the number of bytes added to tail.
408  */
409 static int
410 ooo_segment_try_collect (svm_fifo_t * f, u32 n_bytes_enqueued)
411 {
412  ooo_segment_t *s;
413  u32 index, bytes = 0;
414  i32 diff;
415 
416  s = pool_elt_at_index (f->ooo_segments, f->ooos_list_head);
417  diff = ooo_segment_distance_to_tail (f, s->start);
418 
419  ASSERT (diff != n_bytes_enqueued);
420 
421  if (diff > n_bytes_enqueued)
422  return 0;
423 
424  /* If last tail update overlaps one/multiple ooo segments, remove them */
425  while (0 <= diff && diff < n_bytes_enqueued)
426  {
427  index = s - f->ooo_segments;
428 
429  /* Segment end is beyond the tail. Advance tail and remove segment */
430  if (s->length > diff)
431  {
432  bytes = s->length - diff;
433  f->tail += bytes;
434  f->tail %= f->nitems;
435  ooo_segment_del (f, index);
436  break;
437  }
438 
439  /* If we have next go on */
441  {
442  s = pool_elt_at_index (f->ooo_segments, s->next);
443  diff = ooo_segment_distance_to_tail (f, s->start);
444  ooo_segment_del (f, index);
445  }
446  /* End of search */
447  else
448  {
449  ooo_segment_del (f, index);
450  break;
451  }
452  }
453 
454  ASSERT (bytes <= f->nitems);
455  return bytes;
456 }
457 
459  const u8 * copy_from_here)
460 {
461  u32 total_copy_bytes, first_copy_bytes, second_copy_bytes;
462  u32 cursize, nitems;
463 
464  /* read cursize, which can only increase while we're working */
465  cursize = svm_fifo_max_dequeue (f);
466  f->ooos_newest = OOO_SEGMENT_INVALID_INDEX;
467 
468  if (PREDICT_FALSE (cursize == f->nitems))
469  return SVM_FIFO_FULL;
470 
471  nitems = f->nitems;
472 
473  /* Number of bytes we're going to copy */
474  total_copy_bytes = (nitems - cursize) < max_bytes ?
475  (nitems - cursize) : max_bytes;
476 
477  if (PREDICT_TRUE (copy_from_here != 0))
478  {
479  /* Number of bytes in first copy segment */
480  first_copy_bytes = ((nitems - f->tail) < total_copy_bytes)
481  ? (nitems - f->tail) : total_copy_bytes;
482 
483  clib_memcpy (&f->data[f->tail], copy_from_here, first_copy_bytes);
484  f->tail += first_copy_bytes;
485  f->tail = (f->tail == nitems) ? 0 : f->tail;
486 
487  /* Number of bytes in second copy segment, if any */
488  second_copy_bytes = total_copy_bytes - first_copy_bytes;
489  if (second_copy_bytes)
490  {
491  clib_memcpy (&f->data[f->tail], copy_from_here + first_copy_bytes,
492  second_copy_bytes);
493  f->tail += second_copy_bytes;
494  f->tail = (f->tail == nitems) ? 0 : f->tail;
495  }
496  }
497  else
498  {
499  ASSERT (0);
500 
501  /* Account for a zero-copy enqueue done elsewhere */
502  ASSERT (max_bytes <= (nitems - cursize));
503  f->tail += max_bytes;
504  f->tail = f->tail % nitems;
505  total_copy_bytes = max_bytes;
506  }
507 
508  svm_fifo_trace_add (f, f->head, total_copy_bytes, 2);
509 
510  /* Any out-of-order segments to collect? */
511  if (PREDICT_FALSE (f->ooos_list_head != OOO_SEGMENT_INVALID_INDEX))
512  total_copy_bytes += ooo_segment_try_collect (f, total_copy_bytes);
513 
514  /* Atomically increase the queue length */
515  ASSERT (cursize + total_copy_bytes <= nitems);
516  __sync_fetch_and_add (&f->cursize, total_copy_bytes);
517 
518  return (total_copy_bytes);
519 }
520 
521 #ifndef CLIB_MARCH_VARIANT
522 int
524  const u8 * copy_from_here)
525 {
526  return CLIB_MARCH_FN_SELECT (svm_fifo_enqueue_nowait) (f, max_bytes,
527  copy_from_here);
528 }
529 #endif
530 
531 /**
532  * Enqueue a future segment.
533  *
534  * Two choices: either copies the entire segment, or copies nothing
535  * Returns 0 of the entire segment was copied
536  * Returns -1 if none of the segment was copied due to lack of space
537  */
539  u32 offset, u32 required_bytes, u8 * copy_from_here)
540 {
541  u32 total_copy_bytes, first_copy_bytes, second_copy_bytes;
542  u32 cursize, nitems, normalized_offset;
543 
544  f->ooos_newest = OOO_SEGMENT_INVALID_INDEX;
545 
546  /* read cursize, which can only increase while we're working */
547  cursize = svm_fifo_max_dequeue (f);
548  nitems = f->nitems;
549 
550  ASSERT (required_bytes < nitems);
551 
552  normalized_offset = (f->tail + offset) % nitems;
553 
554  /* Will this request fit? */
555  if ((required_bytes + offset) > (nitems - cursize))
556  return -1;
557 
558  svm_fifo_trace_add (f, offset, required_bytes, 1);
559 
560  ooo_segment_add (f, offset, required_bytes);
561 
562  /* Number of bytes we're going to copy */
563  total_copy_bytes = required_bytes;
564 
565  /* Number of bytes in first copy segment */
566  first_copy_bytes = ((nitems - normalized_offset) < total_copy_bytes)
567  ? (nitems - normalized_offset) : total_copy_bytes;
568 
569  clib_memcpy (&f->data[normalized_offset], copy_from_here, first_copy_bytes);
570 
571  /* Number of bytes in second copy segment, if any */
572  second_copy_bytes = total_copy_bytes - first_copy_bytes;
573  if (second_copy_bytes)
574  {
575  normalized_offset += first_copy_bytes;
576  normalized_offset %= nitems;
577 
578  ASSERT (normalized_offset == 0);
579 
580  clib_memcpy (&f->data[normalized_offset],
581  copy_from_here + first_copy_bytes, second_copy_bytes);
582  }
583 
584  return (0);
585 }
586 
587 #ifndef CLIB_MARCH_VARIANT
588 
589 int
591  u8 * copy_from_here)
592 {
594  required_bytes,
595  copy_from_here);
596 }
597 
598 void
600 {
601  u32 first_chunk;
602  first_chunk = f->nitems - f->head;
603  ASSERT (len <= f->nitems);
604  if (len <= first_chunk)
605  clib_memcpy (&f->data[f->head], data, len);
606  else
607  {
608  clib_memcpy (&f->data[f->head], data, first_chunk);
609  clib_memcpy (&f->data[0], data + first_chunk, len - first_chunk);
610  }
611 }
612 #endif
613 
615  u8 * copy_here)
616 {
617  u32 total_copy_bytes, first_copy_bytes, second_copy_bytes;
618  u32 cursize, nitems;
619 
620  /* read cursize, which can only increase while we're working */
621  cursize = svm_fifo_max_dequeue (f);
622  if (PREDICT_FALSE (cursize == 0))
623  return -2; /* nothing in the fifo */
624 
625  nitems = f->nitems;
626 
627  /* Number of bytes we're going to copy */
628  total_copy_bytes = (cursize < max_bytes) ? cursize : max_bytes;
629 
630  if (PREDICT_TRUE (copy_here != 0))
631  {
632  /* Number of bytes in first copy segment */
633  first_copy_bytes = ((nitems - f->head) < total_copy_bytes)
634  ? (nitems - f->head) : total_copy_bytes;
635  clib_memcpy (copy_here, &f->data[f->head], first_copy_bytes);
636  f->head += first_copy_bytes;
637  f->head = (f->head == nitems) ? 0 : f->head;
638 
639  /* Number of bytes in second copy segment, if any */
640  second_copy_bytes = total_copy_bytes - first_copy_bytes;
641  if (second_copy_bytes)
642  {
643  clib_memcpy (copy_here + first_copy_bytes,
644  &f->data[f->head], second_copy_bytes);
645  f->head += second_copy_bytes;
646  f->head = (f->head == nitems) ? 0 : f->head;
647  }
648  }
649  else
650  {
651  ASSERT (0);
652  /* Account for a zero-copy dequeue done elsewhere */
653  ASSERT (max_bytes <= cursize);
654  f->head += max_bytes;
655  f->head = f->head % nitems;
656  cursize -= max_bytes;
657  total_copy_bytes = max_bytes;
658  }
659 
660  ASSERT (f->head <= nitems);
661  ASSERT (cursize >= total_copy_bytes);
662  __sync_fetch_and_sub (&f->cursize, total_copy_bytes);
663 
664  return (total_copy_bytes);
665 }
666 
667 #ifndef CLIB_MARCH_VARIANT
668 
669 int
670 svm_fifo_dequeue_nowait (svm_fifo_t * f, u32 max_bytes, u8 * copy_here)
671 {
672  return CLIB_MARCH_FN_SELECT (svm_fifo_dequeue_nowait) (f, max_bytes,
673  copy_here);
674 }
675 #endif
676 
677 CLIB_MARCH_FN (svm_fifo_peek, int, svm_fifo_t * f, u32 relative_offset,
678  u32 max_bytes, u8 * copy_here)
679 {
680  u32 total_copy_bytes, first_copy_bytes, second_copy_bytes;
681  u32 cursize, nitems, real_head;
682 
683  /* read cursize, which can only increase while we're working */
684  cursize = svm_fifo_max_dequeue (f);
685  if (PREDICT_FALSE (cursize < relative_offset))
686  return -2; /* nothing in the fifo */
687 
688  nitems = f->nitems;
689  real_head = f->head + relative_offset;
690  real_head = real_head >= nitems ? real_head - nitems : real_head;
691 
692  /* Number of bytes we're going to copy */
693  total_copy_bytes = (cursize - relative_offset < max_bytes) ?
694  cursize - relative_offset : max_bytes;
695 
696  if (PREDICT_TRUE (copy_here != 0))
697  {
698  /* Number of bytes in first copy segment */
699  first_copy_bytes =
700  ((nitems - real_head) < total_copy_bytes) ?
701  (nitems - real_head) : total_copy_bytes;
702  clib_memcpy (copy_here, &f->data[real_head], first_copy_bytes);
703 
704  /* Number of bytes in second copy segment, if any */
705  second_copy_bytes = total_copy_bytes - first_copy_bytes;
706  if (second_copy_bytes)
707  {
708  clib_memcpy (copy_here + first_copy_bytes, &f->data[0],
709  second_copy_bytes);
710  }
711  }
712  return total_copy_bytes;
713 }
714 
715 #ifndef CLIB_MARCH_VARIANT
716 
717 int
718 svm_fifo_peek (svm_fifo_t * f, u32 relative_offset, u32 max_bytes,
719  u8 * copy_here)
720 {
721  return CLIB_MARCH_FN_SELECT (svm_fifo_peek) (f, relative_offset, max_bytes,
722  copy_here);
723 }
724 
725 int
727 {
728  u32 total_drop_bytes, first_drop_bytes, second_drop_bytes;
729  u32 cursize, nitems;
730 
731  /* read cursize, which can only increase while we're working */
732  cursize = svm_fifo_max_dequeue (f);
733  if (PREDICT_FALSE (cursize == 0))
734  return -2; /* nothing in the fifo */
735 
736  nitems = f->nitems;
737 
738  /* Number of bytes we're going to drop */
739  total_drop_bytes = (cursize < max_bytes) ? cursize : max_bytes;
740 
741  svm_fifo_trace_add (f, f->tail, total_drop_bytes, 3);
742 
743  /* Number of bytes in first copy segment */
744  first_drop_bytes =
745  ((nitems - f->head) < total_drop_bytes) ?
746  (nitems - f->head) : total_drop_bytes;
747  f->head += first_drop_bytes;
748  f->head = (f->head == nitems) ? 0 : f->head;
749 
750  /* Number of bytes in second drop segment, if any */
751  second_drop_bytes = total_drop_bytes - first_drop_bytes;
752  if (second_drop_bytes)
753  {
754  f->head += second_drop_bytes;
755  f->head = (f->head == nitems) ? 0 : f->head;
756  }
757 
758  ASSERT (f->head <= nitems);
759  ASSERT (cursize >= total_drop_bytes);
760  __sync_fetch_and_sub (&f->cursize, total_drop_bytes);
761 
762  return total_drop_bytes;
763 }
764 
765 void
767 {
768  f->head = f->tail;
769  __sync_fetch_and_sub (&f->cursize, f->cursize);
770 }
771 
772 int
774 {
775  u32 cursize, nitems;
776 
777  /* read cursize, which can only increase while we're working */
778  cursize = svm_fifo_max_dequeue (f);
779  if (PREDICT_FALSE (cursize == 0))
780  return -2;
781 
782  nitems = f->nitems;
783 
784  fs[0].len = ((nitems - f->head) < cursize) ? (nitems - f->head) : cursize;
785  fs[0].data = f->data + f->head;
786 
787  if (fs[0].len < cursize)
788  {
789  fs[1].len = cursize - fs[0].len;
790  fs[1].data = f->data;
791  }
792  else
793  {
794  fs[1].len = 0;
795  fs[1].data = 0;
796  }
797  return cursize;
798 }
799 
800 void
802 {
803  u32 total_drop_bytes;
804 
805  ASSERT (fs[0].data == f->data + f->head);
806  if (fs[1].len)
807  {
808  f->head = fs[1].len;
809  total_drop_bytes = fs[0].len + fs[1].len;
810  }
811  else
812  {
813  f->head = (f->head + fs[0].len) % f->nitems;
814  total_drop_bytes = fs[0].len;
815  }
816  __sync_fetch_and_sub (&f->cursize, total_drop_bytes);
817 }
818 
819 u32
821 {
822  return pool_elts (f->ooo_segments);
823 }
824 
827 {
828  return pool_elt_at_index (f->ooo_segments, f->ooos_list_head);
829 }
830 
831 /**
832  * Set fifo pointers to requested offset
833  */
834 void
836 {
837  f->head = f->tail = pointer % f->nitems;
838 }
839 
840 #endif
841 /*
842  * fd.io coding-style-patch-verification: ON
843  *
844  * Local Variables:
845  * eval: (c-set-style "gnu")
846  * End:
847  */
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
Definition: vec.h:437
static vlib_cli_command_t trace
(constructor) VLIB_CLI_COMMAND (trace)
Definition: vlib_api_cli.c:862
void svm_fifo_init_pointers(svm_fifo_t *f, u32 pointer)
Set fifo pointers to requested offset.
Definition: svm_fifo.c:835
static u32 position_diff(svm_fifo_t *f, u32 posa, u32 posb)
Definition: svm_fifo.c:41
a
Definition: bitmap.h:538
int svm_fifo_segments(svm_fifo_t *f, svm_fifo_segment_t *fs)
Definition: svm_fifo.c:773
static u8 svm_fifo_has_ooo_data(svm_fifo_t *f)
Definition: svm_fifo.h:144
#define PREDICT_TRUE(x)
Definition: clib.h:108
void svm_fifo_free(svm_fifo_t *f)
Definition: svm_fifo.c:221
u32 prev
Previous linked-list element pool index.
Definition: svm_fifo.h:30
#define CLIB_MARCH_FN_SELECT(fn)
Definition: cpu.h:310
void svm_fifo_overwrite_head(svm_fifo_t *f, u8 *data, u32 len)
Definition: svm_fifo.c:599
int i
static int ooo_segment_try_collect(svm_fifo_t *f, u32 n_bytes_enqueued)
Removes segments that can now be enqueued because the fifo&#39;s tail has advanced.
Definition: svm_fifo.c:410
ooo_segment_t * svm_fifo_first_ooo_segment(svm_fifo_t *f)
Definition: svm_fifo.c:826
void svm_fifo_dequeue_drop_all(svm_fifo_t *f)
Definition: svm_fifo.c:766
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:419
#define pool_get(P, E)
Allocate an object E from a pool P (unspecified alignment).
Definition: pool.h:228
unsigned char u8
Definition: types.h:56
static u32 ooo_segment_distance_from_tail(svm_fifo_t *f, u32 pos)
Definition: svm_fifo.h:266
struct _svm_fifo svm_fifo_t
memset(h->entries, 0, sizeof(h->entries[0])*entries)
static void ooo_segment_add(svm_fifo_t *f, u32 offset, u32 length)
Add segment to fifo&#39;s out-of-order segment list.
Definition: svm_fifo.c:278
#define always_inline
Definition: clib.h:94
static u32 svm_fifo_max_dequeue(svm_fifo_t *f)
Definition: svm_fifo.h:114
u8 * format_ooo_list(u8 *s, va_list *args)
Definition: svm_fifo.c:152
int svm_fifo_enqueue_nowait(svm_fifo_t *f, u32 max_bytes, const u8 *copy_from_here)
Definition: svm_fifo.c:523
unsigned int u32
Definition: types.h:88
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
Definition: pool.h:464
static u8 position_gt(svm_fifo_t *f, u32 a, u32 b)
Definition: svm_fifo.c:34
u32 svm_fifo_number_ooo_segments(svm_fifo_t *f)
Definition: svm_fifo.c:820
#define pool_put(P, E)
Free an object E in pool P.
Definition: pool.h:274
#define PREDICT_FALSE(x)
Definition: clib.h:107
static ooo_segment_t * ooo_segment_next(svm_fifo_t *f, ooo_segment_t *s)
Definition: svm_fifo.h:308
#define svm_fifo_trace_add(_f, _s, _l, _t)
Definition: svm_fifo.h:107
u8 * svm_fifo_replay(u8 *s, svm_fifo_t *f, u8 no_read, u8 verbose)
Definition: svm_fifo.c:92
#define pool_free(p)
Free a pool.
Definition: pool.h:357
static u8 position_leq(svm_fifo_t *f, u32 a, u32 b)
Definition: svm_fifo.c:27
#define clib_memcpy(a, b, c)
Definition: string.h:75
static ooo_segment_t * ooo_segment_get_prev(svm_fifo_t *f, ooo_segment_t *s)
Definition: svm_fifo.h:300
static void ooo_segment_del(svm_fifo_t *f, u32 index)
Definition: svm_fifo.c:249
CLIB_MARCH_FN(svm_fifo_enqueue_nowait, int, svm_fifo_t *f, u32 max_bytes, const u8 *copy_from_here)
Definition: svm_fifo.c:458
#define OOO_SEGMENT_INVALID_INDEX
Definition: svm_fifo.h:40
u8 * format_ooo_segment(u8 *s, va_list *args)
Definition: svm_fifo.c:56
static void * clib_mem_alloc_aligned_or_null(uword size, uword align)
Definition: mem.h:156
signed int i32
Definition: types.h:77
u8 * format_svm_fifo(u8 *s, va_list *args)
Definition: svm_fifo.c:169
#define ASSERT(truth)
static u8 position_lt(svm_fifo_t *f, u32 a, u32 b)
Definition: svm_fifo.c:20
static void clib_mem_free(void *p)
Definition: mem.h:205
int svm_fifo_enqueue_with_offset(svm_fifo_t *f, u32 offset, u32 required_bytes, u8 *copy_from_here)
Definition: svm_fifo.c:590
Out-of-order segment.
Definition: svm_fifo.h:27
u32 length
Length of segment.
Definition: svm_fifo.h:33
u8 * svm_fifo_dump_trace(u8 *s, svm_fifo_t *f)
Definition: svm_fifo.c:68
u32 next
Next linked-list element pool index.
Definition: svm_fifo.h:29
template key/value backing page structure
Definition: bihash_doc.h:44
void svm_fifo_segments_free(svm_fifo_t *f, svm_fifo_segment_t *fs)
Definition: svm_fifo.c:801
int svm_fifo_dequeue_drop(svm_fifo_t *f, u32 max_bytes)
Definition: svm_fifo.c:726
static u32 ooo_segment_end_pos(svm_fifo_t *f, ooo_segment_t *s)
Definition: svm_fifo.c:48
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
static ooo_segment_t * ooo_segment_new(svm_fifo_t *f, u32 start, u32 length)
Definition: svm_fifo.c:234
static uword max_log2(uword x)
Definition: clib.h:187
struct clib_bihash_value offset
template key/value backing page structure
#define vec_foreach(var, vec)
Vector iterator.
#define SVM_FIFO_INVALID_SESSION_INDEX
Definition: svm_fifo.h:41
#define CLIB_CACHE_LINE_BYTES
Definition: cache.h:59
int svm_fifo_peek(svm_fifo_t *f, u32 relative_offset, u32 max_bytes, u8 *copy_here)
Definition: svm_fifo.c:718
int svm_fifo_dequeue_nowait(svm_fifo_t *f, u32 max_bytes, u8 *copy_here)
Definition: svm_fifo.c:670
u32 start
Start of segment, normalized.
Definition: svm_fifo.h:32
static u32 ooo_segment_distance_to_tail(svm_fifo_t *f, u32 pos)
Definition: svm_fifo.h:276
svm_fifo_t * svm_fifo_create(u32 data_size_in_bytes)
create an svm fifo, in the current heap.
Definition: svm_fifo.c:200
static uword pool_elts(void *v)
Number of active elements in a pool.
Definition: pool.h:128