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