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