src/svm/svm_fifo.h

   1 /*
   2  * Copyright (c) 2016-2019 Cisco and/or its affiliates.
   3  * Copyright (c) 2019 Arm Limited
   4  * Copyright (c) 2010-2017 Intel Corporation and/or its affiliates.
   5  * Copyright (c) 2007-2009 Kip Macy kmacy@freebsd.org
   6  * Inspired from DPDK rte_ring.h (SPSC only) (derived from freebsd bufring.h).
   7  * Licensed under the Apache License, Version 2.0 (the "License");
   8  * you may not use this file except in compliance with the License.
   9  * You may obtain a copy of the License at:
  10  *
  11  *     http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  * Unless required by applicable law or agreed to in writing, software
  14  * distributed under the License is distributed on an "AS IS" BASIS,
  15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  * See the License for the specific language governing permissions and
  17  * limitations under the License.
  18  */
  19 #ifndef __included_ssvm_fifo_h__
  20 #define __included_ssvm_fifo_h__
  21
  22 #include <vppinfra/clib.h>
  23 #include <vppinfra/vec.h>
  24 #include <vppinfra/mheap.h>
  25 #include <vppinfra/heap.h>
  26 #include <vppinfra/pool.h>
  27 #include <vppinfra/format.h>
  28 #include <pthread.h>
  29
  30 /** Out-of-order segment */
  31 typedef struct
  32 {
  33   u32 next;     /**< Next linked-list element pool index */
  34   u32 prev;     /**< Previous linked-list element pool index */
  35
  36   u32 start;    /**< Start of segment, normalized*/
  37   u32 length;   /**< Length of segment */
  38 } ooo_segment_t;
  39
  40 format_function_t format_ooo_segment;
  41 format_function_t format_ooo_list;
  42
  43 #define SVM_FIFO_TRACE                  (0)
  44 #define OOO_SEGMENT_INVALID_INDEX       ((u32)~0)
  45 #define SVM_FIFO_INVALID_SESSION_INDEX  ((u32)~0)
  46 #define SVM_FIFO_INVALID_INDEX          ((u32)~0)
  47 #define SVM_FIFO_MAX_EVT_SUBSCRIBERS    8
  48
  49 enum
  50 {
  51   SVM_FIFO_NO_TX_NOTIF = 0,
  52   SVM_FIFO_WANT_TX_NOTIF = 1,
  53   SVM_FIFO_WANT_TX_NOTIF_IF_FULL = 2,
  54 };
  55
  56 typedef struct
  57 {
  58   u32 offset;
  59   u32 len;
  60   u32 action;
  61 } svm_fifo_trace_elem_t;
  62
  63 typedef struct _svm_fifo
  64 {
  65   CLIB_CACHE_LINE_ALIGN_MARK (shared_first);
  66   u32 size;                     /**< size of the fifo(must be power of 2) */
  67   u32 nitems;                   /**< usable size(size-1) */
  68
  69     CLIB_CACHE_LINE_ALIGN_MARK (shared_second);
  70   volatile u32 has_event;       /**< non-zero if deq event exists */
  71
  72   u32 master_session_index;
  73   u32 client_session_index;
  74   u8 master_thread_index;
  75   u8 client_thread_index;
  76   u32 segment_manager;
  77   u32 segment_index;
  78   u32 ct_session_index;         /**< Local session index for vpp */
  79   u32 freelist_index;           /**< aka log2(allocated_size) - const. */
  80   i8 refcnt;                    /**< reference count  */
  81
  82     CLIB_CACHE_LINE_ALIGN_MARK (consumer);
  83   u32 head;
  84   volatile u32 want_tx_ntf;     /**< producer wants nudge */
  85   volatile u32 has_tx_ntf;
  86
  87     CLIB_CACHE_LINE_ALIGN_MARK (producer);
  88   u32 tail;
  89
  90   ooo_segment_t *ooo_segments;  /**< Pool of ooo segments */
  91   u32 ooos_list_head;           /**< Head of out-of-order linked-list */
  92   u32 ooos_newest;              /**< Last segment to have been updated */
  93   struct _svm_fifo *next;       /**< next in freelist/active chain */
  94   struct _svm_fifo *prev;       /**< prev in active chain */
  95   volatile u8 n_subscribers;
  96   u8 subscribers[SVM_FIFO_MAX_EVT_SUBSCRIBERS];
  97
  98 #if SVM_FIFO_TRACE
  99   svm_fifo_trace_elem_t *trace;
 100 #endif
 101
 102     CLIB_CACHE_LINE_ALIGN_MARK (data);
 103 } svm_fifo_t;
 104
 105 typedef enum
 106 {
 107   SVM_FIFO_FULL = -2,
 108 } svm_fifo_err_t;
 109
 110 typedef struct svm_fifo_segment_
 111 {
 112   u8 *data;
 113   u32 len;
 114 } svm_fifo_segment_t;
 115
 116 #if SVM_FIFO_TRACE
 117 #define svm_fifo_trace_add(_f, _s, _l, _t)              \
 118 {                                                       \
 119   svm_fifo_trace_elem_t *trace_elt;                     \
 120   vec_add2(_f->trace, trace_elt, 1);                    \
 121   trace_elt->offset = _s;                               \
 122   trace_elt->len = _l;                                  \
 123   trace_elt->action = _t;                               \
 124 }
 125 #else
 126 #define svm_fifo_trace_add(_f, _s, _l, _t)
 127 #endif
 128
 129 u8 *svm_fifo_dump_trace (u8 * s, svm_fifo_t * f);
 130 u8 *svm_fifo_replay (u8 * s, svm_fifo_t * f, u8 no_read, u8 verbose);
 131
 132 /* internal function */
 133 static inline void
 134 f_load_head_tail_cons (svm_fifo_t * f, u32 * head, u32 * tail)
 135 {
 136   /* load-relaxed: consumer owned index */
 137   *head = f->head;
 138   /* load-acq: consumer foreign index (paired with store-rel in producer) */
 139   *tail = clib_atomic_load_acq_n (&f->tail);
 140 }
 141
 142 /* internal function */
 143 static inline void
 144 f_load_head_tail_prod (svm_fifo_t * f, u32 * head, u32 * tail)
 145 {
 146   /* load relaxed: producer owned index */
 147   *tail = f->tail;
 148   /* load-acq: producer foreign index (paired with store-rel in consumer) */
 149   *head = clib_atomic_load_acq_n (&f->head);
 150 }
 151
 152 /* producer consumer role independent */
 153 /* internal function */
 154 static inline void
 155 f_load_head_tail_all_acq (svm_fifo_t * f, u32 * head, u32 * tail)
 156 {
 157   /* load-acq : consumer foreign index (paired with store-rel) */
 158   *tail = clib_atomic_load_acq_n (&f->tail);
 159   /* load-acq : producer foriegn index (paired with store-rel) */
 160   *head = clib_atomic_load_acq_n (&f->head);
 161 }
 162
 163 /* internal function */
 164 static inline u32
 165 f_free_count (svm_fifo_t * f, u32 head, u32 tail)
 166 {
 167   return (f->nitems + head - tail);
 168 }
 169
 170 /* internal function */
 171 static inline u32
 172 f_cursize (svm_fifo_t * f, u32 head, u32 tail)
 173 {
 174   return (f->nitems - f_free_count (f, head, tail));
 175 }
 176
 177 /* used by consumer */
 178 static inline u32
 179 svm_fifo_max_dequeue_cons (svm_fifo_t * f)
 180 {
 181   u32 tail, head;
 182   f_load_head_tail_cons (f, &head, &tail);
 183   return f_cursize (f, head, tail);
 184 }
 185
 186 /* used by producer*/
 187 static inline u32
 188 svm_fifo_max_dequeue_prod (svm_fifo_t * f)
 189 {
 190   u32 tail, head;
 191   f_load_head_tail_prod (f, &head, &tail);
 192   return f_cursize (f, head, tail);
 193 }
 194
 195 /* use producer or consumer specific functions for perfomance.
 196  * svm_fifo_max_dequeue_cons (svm_fifo_t *f)
 197  * svm_fifo_max_dequeue_prod (svm_fifo_t *f)
 198  */
 199 static inline u32
 200 svm_fifo_max_dequeue (svm_fifo_t * f)
 201 {
 202   u32 tail, head;
 203   f_load_head_tail_all_acq (f, &head, &tail);
 204   return f_cursize (f, head, tail);
 205 }
 206
 207 /* used by producer */
 208 static inline int
 209 svm_fifo_is_full_prod (svm_fifo_t * f)
 210 {
 211   return (svm_fifo_max_dequeue_prod (f) == f->nitems);
 212 }
 213
 214 /* use producer or consumer specific functions for perfomance.
 215  * svm_fifo_is_full_prod (svm_fifo_t * f)
 216  * add cons version if needed
 217  */
 218 static inline int
 219 svm_fifo_is_full (svm_fifo_t * f)
 220 {
 221   return (svm_fifo_max_dequeue (f) == f->nitems);
 222 }
 223
 224 /* used by consumer */
 225 static inline int
 226 svm_fifo_is_empty_cons (svm_fifo_t * f)
 227 {
 228   return (svm_fifo_max_dequeue_cons (f) == 0);
 229 }
 230
 231 /* used by producer */
 232 static inline int
 233 svm_fifo_is_empty_prod (svm_fifo_t * f)
 234 {
 235   return (svm_fifo_max_dequeue_prod (f) == 0);
 236 }
 237
 238 /* use producer or consumer specific functions for perfomance.
 239  * svm_fifo_is_empty_cons (svm_fifo_t * f)
 240  * svm_fifo_is_empty_prod (svm_fifo_t * f)
 241  */
 242 static inline int
 243 svm_fifo_is_empty (svm_fifo_t * f)
 244 {
 245   return (svm_fifo_max_dequeue (f) == 0);
 246 }
 247
 248 /* used by producer*/
 249 static inline u32
 250 svm_fifo_max_enqueue_prod (svm_fifo_t * f)
 251 {
 252   u32 head, tail;
 253   f_load_head_tail_prod (f, &head, &tail);
 254   return f_free_count (f, head, tail);
 255 }
 256
 257 /* use producer or consumer specfic functions for perfomance.
 258  * svm_fifo_max_enqueue_prod (svm_fifo_t *f)
 259  * add consumer specific version if needed.
 260  */
 261 static inline u32
 262 svm_fifo_max_enqueue (svm_fifo_t * f)
 263 {
 264   u32 head, tail;
 265   f_load_head_tail_all_acq (f, &head, &tail);
 266   return f_free_count (f, head, tail);
 267 }
 268
 269 static inline int
 270 svm_fifo_has_event (svm_fifo_t * f)
 271 {
 272   return f->has_event;
 273 }
 274
 275 static inline u8
 276 svm_fifo_has_ooo_data (svm_fifo_t * f)
 277 {
 278   return f->ooos_list_head != OOO_SEGMENT_INVALID_INDEX;
 279 }
 280
 281 /**
 282  * Sets fifo event flag.
 283  *
 284  * Also acts as a release ordering.
 285  *
 286  * @return 1 if flag was not set.
 287  */
 288 always_inline u8
 289 svm_fifo_set_event (svm_fifo_t * f)
 290 {
 291   /* return __sync_lock_test_and_set (&f->has_event, 1) == 0;
 292      return __sync_bool_compare_and_swap (&f->has_event, 0, 1); */
 293   return !clib_atomic_swap_rel_n (&f->has_event, 1);
 294 }
 295
 296 /**
 297  * Unsets fifo event flag.
 298  *
 299  * Also acts as an acquire barrier.
 300  */
 301 always_inline void
 302 svm_fifo_unset_event (svm_fifo_t * f)
 303 {
 304   clib_atomic_swap_acq_n (&f->has_event, 0);
 305 }
 306
 307 svm_fifo_t *svm_fifo_create (u32 data_size_in_bytes);
 308 void svm_fifo_free (svm_fifo_t * f);
 309
 310 int svm_fifo_enqueue_nowait (svm_fifo_t * f, u32 max_bytes,
 311                              const u8 * copy_from_here);
 312 int svm_fifo_enqueue_with_offset (svm_fifo_t * f, u32 offset,
 313                                   u32 required_bytes, u8 * copy_from_here);
 314 int svm_fifo_dequeue_nowait (svm_fifo_t * f, u32 max_bytes, u8 * copy_here);
 315
 316 int svm_fifo_peek (svm_fifo_t * f, u32 offset, u32 max_bytes, u8 * copy_here);
 317 int svm_fifo_dequeue_drop (svm_fifo_t * f, u32 max_bytes);
 318 void svm_fifo_dequeue_drop_all (svm_fifo_t * f);
 319 int svm_fifo_segments (svm_fifo_t * f, svm_fifo_segment_t * fs);
 320 void svm_fifo_segments_free (svm_fifo_t * f, svm_fifo_segment_t * fs);
 321 void svm_fifo_init_pointers (svm_fifo_t * f, u32 pointer);
 322 void svm_fifo_clone (svm_fifo_t * df, svm_fifo_t * sf);
 323 void svm_fifo_overwrite_head (svm_fifo_t * f, u8 * data, u32 len);
 324 void svm_fifo_add_subscriber (svm_fifo_t * f, u8 subscriber);
 325 void svm_fifo_del_subscriber (svm_fifo_t * f, u8 subscriber);
 326 format_function_t format_svm_fifo;
 327
 328 /**
 329  * Max contiguous chunk of data that can be read
 330  */
 331 always_inline u32
 332 svm_fifo_max_read_chunk (svm_fifo_t * f)
 333 {
 334   u32 head, tail;
 335   u32 head_idx, tail_idx;
 336   f_load_head_tail_cons (f, &head, &tail);
 337   head_idx = head % f->size;
 338   tail_idx = tail % f->size;
 339   return tail_idx > head_idx ? (tail_idx - head_idx) : (f->size - head_idx);
 340 }
 341
 342 /**
 343  * Max contiguous chunk of data that can be written
 344  */
 345 always_inline u32
 346 svm_fifo_max_write_chunk (svm_fifo_t * f)
 347 {
 348   u32 head, tail;
 349   u32 head_idx, tail_idx;
 350   f_load_head_tail_prod (f, &head, &tail);
 351   head_idx = head % f->size;
 352   tail_idx = tail % f->size;
 353   return tail_idx >= head_idx ? (f->size - tail_idx) : (head_idx - tail_idx);
 354 }
 355
 356 /**
 357  * Advance tail pointer
 358  *
 359  * Useful for moving tail pointer after external enqueue.
 360  */
 361 always_inline void
 362 svm_fifo_enqueue_nocopy (svm_fifo_t * f, u32 bytes)
 363 {
 364   ASSERT (bytes <= svm_fifo_max_enqueue_prod (f));
 365   /* load-relaxed: producer owned index */
 366   u32 tail = f->tail;
 367   tail += bytes;
 368   /* store-rel: producer owned index (paired with load-acq in consumer) */
 369   clib_atomic_store_rel_n (&f->tail, tail);
 370 }
 371
 372 always_inline u8 *
 373 svm_fifo_head (svm_fifo_t * f)
 374 {
 375   /* load-relaxed: consumer owned index */
 376   return (f->data + (f->head % f->size));
 377 }
 378
 379 always_inline u8 *
 380 svm_fifo_tail (svm_fifo_t * f)
 381 {
 382   /* load-relaxed: producer owned index */
 383   return (f->data + (f->tail % f->size));
 384 }
 385
 386 static inline void
 387 svm_fifo_add_want_tx_ntf (svm_fifo_t * f, u8 ntf_type)
 388 {
 389   f->want_tx_ntf |= ntf_type;
 390 }
 391
 392 static inline void
 393 svm_fifo_del_want_tx_ntf (svm_fifo_t * f, u8 ntf_type)
 394 {
 395   f->want_tx_ntf &= ~ntf_type;
 396 }
 397
 398 static inline void
 399 svm_fifo_clear_tx_ntf (svm_fifo_t * f)
 400 {
 401   /* Set the flag if want_tx_notif_if_full was the only ntf requested */
 402   f->has_tx_ntf = f->want_tx_ntf == SVM_FIFO_WANT_TX_NOTIF_IF_FULL;
 403   svm_fifo_del_want_tx_ntf (f, SVM_FIFO_WANT_TX_NOTIF);
 404 }
 405
 406 static inline void
 407 svm_fifo_reset_tx_ntf (svm_fifo_t * f)
 408 {
 409   f->has_tx_ntf = 0;
 410 }
 411
 412 static inline u8
 413 svm_fifo_needs_tx_ntf (svm_fifo_t * f, u32 n_last_deq)
 414 {
 415   u8 want_ntf = f->want_tx_ntf;
 416
 417   if (PREDICT_TRUE (want_ntf == SVM_FIFO_NO_TX_NOTIF))
 418     return 0;
 419   else if (want_ntf & SVM_FIFO_WANT_TX_NOTIF)
 420     return 1;
 421   else if (want_ntf & SVM_FIFO_WANT_TX_NOTIF_IF_FULL)
 422     {
 423       u32 max_deq = svm_fifo_max_dequeue_cons (f);
 424       u32 nitems = f->nitems;
 425       if (!f->has_tx_ntf && max_deq < nitems
 426           && max_deq + n_last_deq >= nitems)
 427         return 1;
 428
 429       return 0;
 430     }
 431   return 0;
 432 }
 433
 434 always_inline u8
 435 svm_fifo_n_subscribers (svm_fifo_t * f)
 436 {
 437   return f->n_subscribers;
 438 }
 439
 440 u32 svm_fifo_number_ooo_segments (svm_fifo_t * f);
 441 ooo_segment_t *svm_fifo_first_ooo_segment (svm_fifo_t * f);
 442
 443 always_inline ooo_segment_t *
 444 svm_fifo_newest_ooo_segment (svm_fifo_t * f)
 445 {
 446   if (f->ooos_newest == OOO_SEGMENT_INVALID_INDEX)
 447     return 0;
 448   return pool_elt_at_index (f->ooo_segments, f->ooos_newest);
 449 }
 450
 451 always_inline void
 452 svm_fifo_newest_ooo_segment_reset (svm_fifo_t * f)
 453 {
 454   f->ooos_newest = OOO_SEGMENT_INVALID_INDEX;
 455 }
 456
 457 always_inline u32
 458 ooo_segment_distance_from_tail (svm_fifo_t * f, u32 pos, u32 tail)
 459 {
 460   return ((pos - tail) % f->size);
 461 }
 462
 463 always_inline u32
 464 ooo_segment_distance_to_tail (svm_fifo_t * f, u32 pos, u32 tail)
 465 {
 466   return ((tail - pos) % f->size);
 467 }
 468
 469 always_inline u32
 470 ooo_segment_offset_prod (svm_fifo_t * f, ooo_segment_t * s)
 471 {
 472   u32 tail;
 473   /* load-relaxed: producer owned index */
 474   tail = f->tail;
 475
 476   return ooo_segment_distance_from_tail (f, s->start, tail);
 477 }
 478
 479 always_inline u32
 480 ooo_segment_length (svm_fifo_t * f, ooo_segment_t * s)
 481 {
 482   return s->length;
 483 }
 484
 485 always_inline ooo_segment_t *
 486 ooo_segment_get_prev (svm_fifo_t * f, ooo_segment_t * s)
 487 {
 488   if (s->prev == OOO_SEGMENT_INVALID_INDEX)
 489     return 0;
 490   return pool_elt_at_index (f->ooo_segments, s->prev);
 491 }
 492
 493 always_inline ooo_segment_t *
 494 ooo_segment_next (svm_fifo_t * f, ooo_segment_t * s)
 495 {
 496   if (s->next == OOO_SEGMENT_INVALID_INDEX)
 497     return 0;
 498   return pool_elt_at_index (f->ooo_segments, s->next);
 499 }
 500
 501 #endif /* __included_ssvm_fifo_h__ */
 502
 503 /*
 504  * fd.io coding-style-patch-verification: ON
 505  *
 506  * Local Variables:
 507  * eval: (c-set-style "gnu")
 508  * End:
 509  */