vppinfra/vppinfra/smp_fifo.h

   1 /*
   2  * Copyright (c) 2015 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   Copyright (c) 2012 Eliot Dresselhaus
  17
  18   Permission is hereby granted, free of charge, to any person obtaining
  19   a copy of this software and associated documentation files (the
  20   "Software"), to deal in the Software without restriction, including
  21   without limitation the rights to use, copy, modify, merge, publish,
  22   distribute, sublicense, and/or sell copies of the Software, and to
  23   permit persons to whom the Software is furnished to do so, subject to
  24   the following conditions:
  25
  26   The above copyright notice and this permission notice shall be
  27   included in all copies or substantial portions of the Software.
  28
  29   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  30   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  31   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  32   NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  33   LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  34   OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  35   WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  36 */
  37
  38 #ifndef included_clib_smp_vec_h
  39 #define included_clib_smp_vec_h
  40
  41 #include <vppinfra/smp.h>
  42
  43 #define foreach_clib_smp_fifo_data_state        \
  44   _ (free)                                      \
  45   _ (write_alloc)                               \
  46   _ (write_done)                                \
  47   _ (read_fetch)
  48
  49 typedef enum
  50 {
  51 #define _(f) CLIB_SMP_FIFO_DATA_STATE_##f,
  52   foreach_clib_smp_fifo_data_state
  53 #undef _
  54     CLIB_SMP_FIFO_N_DATA_STATE,
  55 } clib_smp_fifo_data_state_t;
  56
  57 /* Footer at end of each data element. */
  58 typedef struct
  59 {
  60   /* Magic number marking valid footer plus state encoded in low bits. */
  61   u32 magic_state;
  62 } clib_smp_fifo_data_footer_t;
  63
  64 #define CLIB_SMP_DATA_FOOTER_MAGIC 0xfafbfcf0
  65
  66 always_inline clib_smp_fifo_data_state_t
  67 clib_smp_fifo_data_footer_get_state (clib_smp_fifo_data_footer_t * f)
  68 {
  69   u32 s = f->magic_state - CLIB_SMP_DATA_FOOTER_MAGIC;
  70
  71   /* Check that magic number plus state is still valid. */
  72   if (s >= CLIB_SMP_FIFO_N_DATA_STATE)
  73     os_panic ();
  74
  75   return s;
  76 }
  77
  78 always_inline void
  79 clib_smp_fifo_data_footer_set_state (clib_smp_fifo_data_footer_t * f,
  80                                      clib_smp_fifo_data_state_t s)
  81 {
  82   f->magic_state = CLIB_SMP_DATA_FOOTER_MAGIC + s;
  83 }
  84
  85 typedef struct
  86 {
  87   /* Read/write indices each on their own cache line.
  88      Atomic incremented for each read/write. */
  89   u32 read_index, write_index;
  90
  91   /* Power of 2 number of elements in fifo less one. */
  92   u32 max_n_elts_less_one;
  93
  94   /* Log2 of above. */
  95   u32 log2_max_n_elts;
  96
  97   /* Cache aligned data. */
  98   void *data;
  99 } clib_smp_fifo_t;
 100
 101 /* External functions. */
 102 clib_smp_fifo_t *clib_smp_fifo_init (uword max_n_elts, uword n_bytes_per_elt);
 103
 104 /* Elements are always cache-line sized; this is to avoid smp cache thrashing. */
 105 always_inline uword
 106 clib_smp_fifo_round_elt_bytes (uword n_bytes_per_elt)
 107 {
 108   return round_pow2 (n_bytes_per_elt, CLIB_CACHE_LINE_BYTES);
 109 }
 110
 111 always_inline uword
 112 clib_smp_fifo_n_elts (clib_smp_fifo_t * f)
 113 {
 114   uword n = f->write_index - f->read_index;
 115   ASSERT (n <= f->max_n_elts_less_one + 1);
 116   return n;
 117 }
 118
 119 always_inline clib_smp_fifo_data_footer_t *
 120 clib_smp_fifo_get_data_footer (void *d, uword n_bytes_per_elt)
 121 {
 122   clib_smp_fifo_data_footer_t *f;
 123   f = d + clib_smp_fifo_round_elt_bytes (n_bytes_per_elt) - sizeof (f[0]);
 124   return f;
 125 }
 126
 127 always_inline void *
 128 clib_smp_fifo_elt_at_index (clib_smp_fifo_t * f, uword n_bytes_per_elt,
 129                             uword i)
 130 {
 131   uword n_bytes_per_elt_cache_aligned;
 132
 133   ASSERT (i <= f->max_n_elts_less_one);
 134
 135   n_bytes_per_elt_cache_aligned =
 136     clib_smp_fifo_round_elt_bytes (n_bytes_per_elt);
 137
 138   return f->data + i * n_bytes_per_elt_cache_aligned;
 139 }
 140
 141 always_inline void *
 142 clib_smp_fifo_write_alloc (clib_smp_fifo_t * f, uword n_bytes_per_elt)
 143 {
 144   void *d;
 145   clib_smp_fifo_data_footer_t *t;
 146   clib_smp_fifo_data_state_t s;
 147   u32 wi0, wi1;
 148
 149   wi0 = f->write_index;
 150
 151   /* Fifo full? */
 152   if (wi0 - f->read_index > f->max_n_elts_less_one)
 153     return 0;
 154
 155   while (1)
 156     {
 157       wi1 = wi0 + 1;
 158
 159       d =
 160         clib_smp_fifo_elt_at_index (f, n_bytes_per_elt,
 161                                     wi0 & f->max_n_elts_less_one);
 162       t = clib_smp_fifo_get_data_footer (d, n_bytes_per_elt);
 163
 164       s = clib_smp_fifo_data_footer_get_state (t);
 165       if (s != CLIB_SMP_FIFO_DATA_STATE_free)
 166         {
 167           d = 0;
 168           break;
 169         }
 170
 171       wi1 = clib_smp_compare_and_swap (&f->write_index, wi1, wi0);
 172
 173       if (wi1 == wi0)
 174         {
 175           clib_smp_fifo_data_footer_set_state (t,
 176                                                CLIB_SMP_FIFO_DATA_STATE_write_alloc);
 177           break;
 178         }
 179
 180       /* Other cpu wrote write index first: try again. */
 181       wi0 = wi1;
 182     }
 183
 184   return d;
 185 }
 186
 187 always_inline void
 188 clib_smp_fifo_write_done (clib_smp_fifo_t * f, void *d, uword n_bytes_per_elt)
 189 {
 190   clib_smp_fifo_data_footer_t *t;
 191
 192   /* Flush out pending writes before we change state to write_done.
 193      This will hold off readers until data is flushed. */
 194   CLIB_MEMORY_BARRIER ();
 195
 196   t = clib_smp_fifo_get_data_footer (d, n_bytes_per_elt);
 197
 198   ASSERT (clib_smp_fifo_data_footer_get_state (t) ==
 199           CLIB_SMP_FIFO_DATA_STATE_write_alloc);
 200   clib_smp_fifo_data_footer_set_state (t,
 201                                        CLIB_SMP_FIFO_DATA_STATE_write_done);
 202 }
 203
 204 always_inline void *
 205 clib_smp_fifo_read_fetch (clib_smp_fifo_t * f, uword n_bytes_per_elt)
 206 {
 207   void *d;
 208   clib_smp_fifo_data_footer_t *t;
 209   clib_smp_fifo_data_state_t s;
 210   u32 ri0, ri1;
 211
 212   ri0 = f->read_index;
 213
 214   /* Fifo empty? */
 215   if (f->write_index - ri0 == 0)
 216     return 0;
 217
 218   while (1)
 219     {
 220       ri1 = ri0 + 1;
 221
 222       d =
 223         clib_smp_fifo_elt_at_index (f, n_bytes_per_elt,
 224                                     ri0 & f->max_n_elts_less_one);
 225       t = clib_smp_fifo_get_data_footer (d, n_bytes_per_elt);
 226
 227       s = clib_smp_fifo_data_footer_get_state (t);
 228       if (s != CLIB_SMP_FIFO_DATA_STATE_write_done)
 229         {
 230           d = 0;
 231           break;
 232         }
 233
 234       ri1 = clib_smp_compare_and_swap (&f->read_index, ri1, ri0);
 235       if (ri1 == ri0)
 236         {
 237           clib_smp_fifo_data_footer_set_state (t,
 238                                                CLIB_SMP_FIFO_DATA_STATE_read_fetch);
 239           break;
 240         }
 241
 242       ri0 = ri1;
 243     }
 244
 245   return d;
 246 }
 247
 248 always_inline void
 249 clib_smp_fifo_read_done (clib_smp_fifo_t * f, void *d, uword n_bytes_per_elt)
 250 {
 251   clib_smp_fifo_data_footer_t *t;
 252
 253   t = clib_smp_fifo_get_data_footer (d, n_bytes_per_elt);
 254
 255   ASSERT (clib_smp_fifo_data_footer_get_state (t) ==
 256           CLIB_SMP_FIFO_DATA_STATE_read_fetch);
 257   clib_smp_fifo_data_footer_set_state (t, CLIB_SMP_FIFO_DATA_STATE_free);
 258 }
 259
 260 always_inline void
 261 clib_smp_fifo_memcpy (uword * dst, uword * src, uword n_bytes)
 262 {
 263   word n_bytes_left = n_bytes;
 264
 265   while (n_bytes_left >= 4 * sizeof (uword))
 266     {
 267       dst[0] = src[0];
 268       dst[1] = src[1];
 269       dst[2] = src[2];
 270       dst[3] = src[3];
 271       dst += 4;
 272       src += 4;
 273       n_bytes_left -= 4 * sizeof (dst[0]);
 274     }
 275
 276   while (n_bytes_left > 0)
 277     {
 278       dst[0] = src[0];
 279       dst += 1;
 280       src += 1;
 281       n_bytes_left -= 1 * sizeof (dst[0]);
 282     }
 283 }
 284
 285 always_inline void
 286 clib_smp_fifo_write_inline (clib_smp_fifo_t * f, void *elt_to_write,
 287                             uword n_bytes_per_elt)
 288 {
 289   uword *dst;
 290   dst = clib_smp_fifo_write_alloc (f, n_bytes_per_elt);
 291   clib_smp_fifo_memcpy (dst, elt_to_write, n_bytes_per_elt);
 292   clib_smp_fifo_write_done (f, dst, n_bytes_per_elt);
 293 }
 294
 295 always_inline void
 296 clib_smp_fifo_read_inline (clib_smp_fifo_t * f, void *elt_to_read,
 297                            uword n_bytes_per_elt)
 298 {
 299   uword *src;
 300   src = clib_smp_fifo_read_fetch (f, n_bytes_per_elt);
 301   clib_smp_fifo_memcpy (elt_to_read, src, n_bytes_per_elt);
 302   clib_smp_fifo_read_done (f, src, n_bytes_per_elt);
 303 }
 304
 305 #endif /* included_clib_smp_vec_h */
 306
 307 /*
 308  * fd.io coding-style-patch-verification: ON
 309  *
 310  * Local Variables:
 311  * eval: (c-set-style "gnu")
 312  * End:
 313  */