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 #define _(f) CLIB_SMP_FIFO_DATA_STATE_##f,
  51   foreach_clib_smp_fifo_data_state
  52 #undef _
  53   CLIB_SMP_FIFO_N_DATA_STATE,
  54 } clib_smp_fifo_data_state_t;
  55
  56 /* Footer at end of each data element. */
  57 typedef struct {
  58   /* Magic number marking valid footer plus state encoded in low bits. */
  59   u32 magic_state;
  60 } clib_smp_fifo_data_footer_t;
  61
  62 #define CLIB_SMP_DATA_FOOTER_MAGIC 0xfafbfcf0
  63
  64 always_inline clib_smp_fifo_data_state_t
  65 clib_smp_fifo_data_footer_get_state (clib_smp_fifo_data_footer_t * f)
  66 {
  67   u32 s = f->magic_state - CLIB_SMP_DATA_FOOTER_MAGIC;
  68
  69   /* Check that magic number plus state is still valid. */
  70   if (s >= CLIB_SMP_FIFO_N_DATA_STATE)
  71     os_panic ();
  72
  73   return s;
  74 }
  75
  76 always_inline void
  77 clib_smp_fifo_data_footer_set_state (clib_smp_fifo_data_footer_t * f,
  78                                      clib_smp_fifo_data_state_t s)
  79 { f->magic_state = CLIB_SMP_DATA_FOOTER_MAGIC + s; }
  80
  81 typedef struct {
  82   /* Read/write indices each on their own cache line.
  83      Atomic incremented for each read/write. */
  84   u32 read_index, write_index;
  85
  86   /* Power of 2 number of elements in fifo less one. */
  87   u32 max_n_elts_less_one;
  88
  89   /* Log2 of above. */
  90   u32 log2_max_n_elts;
  91
  92   /* Cache aligned data. */
  93   void * data;
  94 } clib_smp_fifo_t;
  95
  96 /* External functions. */
  97 clib_smp_fifo_t * clib_smp_fifo_init (uword max_n_elts, uword n_bytes_per_elt);
  98
  99 /* Elements are always cache-line sized; this is to avoid smp cache thrashing. */
 100 always_inline uword
 101 clib_smp_fifo_round_elt_bytes (uword n_bytes_per_elt)
 102 { return round_pow2 (n_bytes_per_elt, CLIB_CACHE_LINE_BYTES); }
 103
 104 always_inline uword
 105 clib_smp_fifo_n_elts (clib_smp_fifo_t * f)
 106 {
 107   uword n = f->write_index - f->read_index;
 108   ASSERT (n <= f->max_n_elts_less_one + 1);
 109   return n;
 110 }
 111
 112 always_inline clib_smp_fifo_data_footer_t *
 113 clib_smp_fifo_get_data_footer (void * d, uword n_bytes_per_elt)
 114 {
 115   clib_smp_fifo_data_footer_t * f;
 116   f = d + clib_smp_fifo_round_elt_bytes (n_bytes_per_elt) - sizeof (f[0]);
 117   return f;
 118 }
 119
 120 always_inline void *
 121 clib_smp_fifo_elt_at_index (clib_smp_fifo_t * f, uword n_bytes_per_elt, uword i)
 122 {
 123   uword n_bytes_per_elt_cache_aligned;
 124
 125   ASSERT (i <= f->max_n_elts_less_one);
 126
 127   n_bytes_per_elt_cache_aligned = clib_smp_fifo_round_elt_bytes (n_bytes_per_elt);
 128
 129   return f->data + i * n_bytes_per_elt_cache_aligned;
 130 }
 131
 132 always_inline void *
 133 clib_smp_fifo_write_alloc (clib_smp_fifo_t * f, uword n_bytes_per_elt)
 134 {
 135   void * d;
 136   clib_smp_fifo_data_footer_t * t;
 137   clib_smp_fifo_data_state_t s;
 138   u32 wi0, wi1;
 139
 140   wi0 = f->write_index;
 141
 142   /* Fifo full? */
 143   if (wi0 - f->read_index > f->max_n_elts_less_one)
 144     return 0;
 145
 146   while (1)
 147     {
 148       wi1 = wi0 + 1;
 149
 150       d = clib_smp_fifo_elt_at_index (f, n_bytes_per_elt, wi0 & f->max_n_elts_less_one);
 151       t = clib_smp_fifo_get_data_footer (d, n_bytes_per_elt);
 152
 153       s = clib_smp_fifo_data_footer_get_state (t);
 154       if (s != CLIB_SMP_FIFO_DATA_STATE_free)
 155         {
 156           d = 0;
 157           break;
 158         }
 159
 160       wi1 = clib_smp_compare_and_swap (&f->write_index, wi1, wi0);
 161
 162       if (wi1 == wi0)
 163         {
 164           clib_smp_fifo_data_footer_set_state (t, CLIB_SMP_FIFO_DATA_STATE_write_alloc);
 165           break;
 166         }
 167
 168       /* Other cpu wrote write index first: try again. */
 169       wi0 = wi1;
 170     }
 171
 172   return d;
 173 }
 174
 175 always_inline void
 176 clib_smp_fifo_write_done (clib_smp_fifo_t * f, void * d, uword n_bytes_per_elt)
 177 {
 178   clib_smp_fifo_data_footer_t * t;
 179
 180   /* Flush out pending writes before we change state to write_done.
 181      This will hold off readers until data is flushed. */
 182   CLIB_MEMORY_BARRIER ();
 183
 184   t = clib_smp_fifo_get_data_footer (d, n_bytes_per_elt);
 185
 186   ASSERT (clib_smp_fifo_data_footer_get_state (t) == CLIB_SMP_FIFO_DATA_STATE_write_alloc);
 187   clib_smp_fifo_data_footer_set_state (t, CLIB_SMP_FIFO_DATA_STATE_write_done);
 188 }
 189
 190 always_inline void *
 191 clib_smp_fifo_read_fetch (clib_smp_fifo_t * f, uword n_bytes_per_elt)
 192 {
 193   void * d;
 194   clib_smp_fifo_data_footer_t * t;
 195   clib_smp_fifo_data_state_t s;
 196   u32 ri0, ri1;
 197
 198   ri0 = f->read_index;
 199
 200   /* Fifo empty? */
 201   if (f->write_index - ri0 == 0)
 202     return 0;
 203
 204   while (1)
 205     {
 206       ri1 = ri0 + 1;
 207
 208       d = clib_smp_fifo_elt_at_index (f, n_bytes_per_elt, ri0 & f->max_n_elts_less_one);
 209       t = clib_smp_fifo_get_data_footer (d, n_bytes_per_elt);
 210
 211       s = clib_smp_fifo_data_footer_get_state (t);
 212       if (s != CLIB_SMP_FIFO_DATA_STATE_write_done)
 213         {
 214           d = 0;
 215           break;
 216         }
 217
 218       ri1 = clib_smp_compare_and_swap (&f->read_index, ri1, ri0);
 219       if (ri1 == ri0)
 220         {
 221           clib_smp_fifo_data_footer_set_state (t, CLIB_SMP_FIFO_DATA_STATE_read_fetch);
 222           break;
 223         }
 224
 225       ri0 = ri1;
 226     }
 227
 228   return d;
 229 }
 230
 231 always_inline void
 232 clib_smp_fifo_read_done (clib_smp_fifo_t * f, void * d, uword n_bytes_per_elt)
 233 {
 234   clib_smp_fifo_data_footer_t * t;
 235
 236   t = clib_smp_fifo_get_data_footer (d, n_bytes_per_elt);
 237
 238   ASSERT (clib_smp_fifo_data_footer_get_state (t) == CLIB_SMP_FIFO_DATA_STATE_read_fetch);
 239   clib_smp_fifo_data_footer_set_state (t, CLIB_SMP_FIFO_DATA_STATE_free);
 240 }
 241
 242 always_inline void
 243 clib_smp_fifo_memcpy (uword * dst, uword * src, uword n_bytes)
 244 {
 245   word n_bytes_left = n_bytes;
 246
 247   while (n_bytes_left >= 4 * sizeof (uword))
 248     {
 249       dst[0] = src[0];
 250       dst[1] = src[1];
 251       dst[2] = src[2];
 252       dst[3] = src[3];
 253       dst += 4;
 254       src += 4;
 255       n_bytes_left -= 4 * sizeof (dst[0]);
 256     }
 257
 258   while (n_bytes_left > 0)
 259     {
 260       dst[0] = src[0];
 261       dst += 1;
 262       src += 1;
 263       n_bytes_left -= 1 * sizeof (dst[0]);
 264     }
 265 }
 266
 267 always_inline void
 268 clib_smp_fifo_write_inline (clib_smp_fifo_t * f, void * elt_to_write, uword n_bytes_per_elt)
 269 {
 270   uword * dst;
 271   dst = clib_smp_fifo_write_alloc (f, n_bytes_per_elt);
 272   clib_smp_fifo_memcpy (dst, elt_to_write, n_bytes_per_elt);
 273   clib_smp_fifo_write_done (f, dst, n_bytes_per_elt);
 274 }
 275
 276 always_inline void
 277 clib_smp_fifo_read_inline (clib_smp_fifo_t * f, void * elt_to_read, uword n_bytes_per_elt)
 278 {
 279   uword * src;
 280   src = clib_smp_fifo_read_fetch (f, n_bytes_per_elt);
 281   clib_smp_fifo_memcpy (elt_to_read, src, n_bytes_per_elt);
 282   clib_smp_fifo_read_done (f, src, n_bytes_per_elt);
 283 }
 284
 285 #endif /* included_clib_smp_vec_h */