vppinfra/vppinfra/smp.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) 2001-2005 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_h
  39 #define included_clib_smp_h
  40
  41 #include <vppinfra/cache.h>
  42 #include <vppinfra/os.h>                /* for os_panic */
  43
  44 /* Per-CPU state. */
  45 typedef struct {
  46   /* Per-cpu local heap. */
  47   void * heap;
  48
  49   u32 thread_id;
  50 } clib_smp_per_cpu_main_t;
  51
  52 typedef struct {
  53   /* Number of CPUs used to model current computer. */
  54   u32 n_cpus;
  55
  56   /* Number of cpus that are done and have exited. */
  57   u32 n_cpus_exited;
  58
  59   /* Log2 stack and vm (heap) size. */
  60   u8 log2_n_per_cpu_stack_bytes, log2_n_per_cpu_vm_bytes;
  61
  62   /* Thread local store (TLS) is stored at stack top.
  63      Number of 4k pages to allocate for TLS. */
  64   u16 n_tls_4k_pages;
  65
  66   /* Per cpus stacks/heaps start at these addresses. */
  67   void * vm_base;
  68
  69   /* Thread-safe global heap.  Objects here can be allocated/freed by any cpu. */
  70   void * global_heap;
  71
  72   clib_smp_per_cpu_main_t * per_cpu_mains;
  73 } clib_smp_main_t;
  74
  75 extern clib_smp_main_t clib_smp_main;
  76
  77 always_inline void *
  78 clib_smp_vm_base_for_cpu (clib_smp_main_t * m, uword cpu)
  79 {
  80   return m->vm_base + (cpu << m->log2_n_per_cpu_vm_bytes);
  81 }
  82
  83 always_inline void *
  84 clib_smp_stack_top_for_cpu (clib_smp_main_t * m, uword cpu)
  85 {
  86   /* Stack is at top of per cpu VM area. */
  87   return clib_smp_vm_base_for_cpu (m, cpu + 1) - ((uword) 1 << m->log2_n_per_cpu_stack_bytes);
  88 }
  89
  90 always_inline uword
  91 os_get_cpu_number_inline (void)
  92 {
  93   clib_smp_main_t * m = &clib_smp_main;
  94   void * sp;
  95   uword n;
  96
  97   /* Get any old stack address. */
  98   sp = &sp;
  99
 100   n = ((uword)sp - (uword)m->vm_base) >> m->log2_n_per_cpu_vm_bytes;
 101
 102   if (CLIB_DEBUG && m->n_cpus > 0 && n >= m->n_cpus)
 103     os_panic ();
 104
 105   return n < m->n_cpus ? n : 0;
 106 }
 107
 108 #define clib_smp_compare_and_swap(addr,new,old) __sync_val_compare_and_swap(addr,old,new)
 109 #define clib_smp_swap(addr,new) __sync_lock_test_and_set(addr,new)
 110 #define clib_smp_atomic_add(addr,increment) __sync_fetch_and_add(addr,increment)
 111
 112 #if defined (i386) || defined (__x86_64__)
 113 #define clib_smp_pause() do { asm volatile ("pause"); } while (0)
 114 #endif
 115
 116 #ifndef clib_smp_pause
 117 #define clib_smp_pause() do { } while (0)
 118 #endif
 119
 120 #ifdef CLIB_UNIX
 121 #include <sched.h>
 122
 123 always_inline void
 124 os_sched_yield (void)
 125 { sched_yield (); }
 126 #else
 127 always_inline void
 128 os_sched_yield (void)
 129 { clib_smp_pause (); }
 130 #endif
 131
 132 typedef enum {
 133   CLIB_SMP_LOCK_TYPE_READER,
 134   CLIB_SMP_LOCK_TYPE_WRITER,
 135   CLIB_SMP_LOCK_TYPE_SPIN,
 136 } clib_smp_lock_type_t;
 137
 138 typedef enum {
 139   CLIB_SMP_LOCK_WAIT_EMPTY,
 140   CLIB_SMP_LOCK_WAIT_DONE,
 141   CLIB_SMP_LOCK_WAIT_READER,
 142   CLIB_SMP_LOCK_WAIT_WRITER,
 143 } clib_smp_lock_wait_type_t;
 144
 145 #if uword_bits == 64
 146 typedef u16 clib_smp_quarter_word_t;
 147 typedef u32 clib_smp_half_word_t;
 148 #else
 149 typedef u8 clib_smp_quarter_word_t;
 150 typedef u16 clib_smp_half_word_t;
 151 #endif
 152
 153 typedef union {
 154   struct {
 155     /* FIFO of CPUs (threads) waiting for lock. */
 156     struct {
 157       clib_smp_quarter_word_t head_index, n_elts;
 158     } waiting_fifo;
 159
 160     /* Requesting CPU for atomic compare_and_swap instructions.
 161        This makes CPUs requesting same header change unique. */
 162     clib_smp_quarter_word_t request_cpu;
 163
 164     /* Count of readers who have been given read lock.
 165        Not applicable for spin locks. */
 166     clib_smp_quarter_word_t n_readers_with_lock : BITS (clib_smp_quarter_word_t) - 1;
 167
 168     /* Set when writer has been given write lock.  Only one of
 169        these can happen at a time. */
 170     clib_smp_quarter_word_t writer_has_lock : 1;
 171   };
 172
 173   uword as_uword;
 174 } clib_smp_lock_header_t;
 175
 176 always_inline uword
 177 clib_smp_lock_header_is_equal (clib_smp_lock_header_t h0, clib_smp_lock_header_t h1)
 178 { return h0.as_uword == h1.as_uword; }
 179
 180 typedef struct {
 181   volatile clib_smp_lock_wait_type_t wait_type;
 182   u8 pad[CLIB_CACHE_LINE_BYTES - 1 * sizeof (clib_smp_lock_wait_type_t)];
 183 } clib_smp_lock_waiting_fifo_elt_t;
 184
 185 /* Cache aligned. */
 186 typedef struct {
 187   clib_smp_lock_header_t header;
 188
 189   /* Size of waiting FIFO; equal to max number of threads less one. */
 190   u32 n_waiting_fifo_elts;
 191
 192   u8 pad[CLIB_CACHE_LINE_BYTES - sizeof (clib_smp_lock_header_t) - sizeof (u32)];
 193
 194   clib_smp_lock_waiting_fifo_elt_t waiting_fifo[0];
 195 } clib_smp_lock_t;
 196
 197 always_inline clib_smp_lock_header_t
 198 clib_smp_lock_set_header (clib_smp_lock_t * l, clib_smp_lock_header_t new_hdr, clib_smp_lock_header_t old)
 199 {
 200   clib_smp_lock_header_t cmp;
 201   cmp.as_uword = clib_smp_compare_and_swap (&l->header.as_uword, new_hdr.as_uword, old.as_uword);
 202   return cmp;
 203 }
 204
 205 void clib_smp_lock_init (clib_smp_lock_t ** l);
 206 void clib_smp_lock_free (clib_smp_lock_t ** l);
 207 void clib_smp_lock_slow_path (clib_smp_lock_t * l, uword my_cpu, clib_smp_lock_header_t h, clib_smp_lock_type_t type);
 208 void clib_smp_unlock_slow_path (clib_smp_lock_t * l, uword my_cpu, clib_smp_lock_header_t h, clib_smp_lock_type_t type);
 209
 210 always_inline void
 211 clib_smp_lock_inline (clib_smp_lock_t * l, clib_smp_lock_type_t type)
 212 {
 213   clib_smp_lock_header_t h0, h1, h2;
 214   uword is_reader = type == CLIB_SMP_LOCK_TYPE_READER;
 215   uword my_cpu;
 216
 217   /* Null lock means n_cpus <= 1: nothing to lock. */
 218   if (! l)
 219     return;
 220
 221   my_cpu = os_get_cpu_number_inline ();
 222   h0 = l->header;
 223   while (! h0.writer_has_lock)
 224     {
 225       /* Want to write but there are still readers with lock? */
 226       if (type == CLIB_SMP_LOCK_TYPE_WRITER && h0.n_readers_with_lock != 0)
 227         break;
 228
 229       if (type == CLIB_SMP_LOCK_TYPE_SPIN)
 230         ASSERT_AND_PANIC (h0.waiting_fifo.n_elts == 0);
 231
 232       /* Read/write can't proceed when waiting fifo is non-empty. */
 233       else if (h0.waiting_fifo.n_elts != 0)
 234         break;
 235
 236       h1 = h0;
 237       h1.request_cpu = my_cpu;
 238       h1.writer_has_lock = ! is_reader;
 239       h1.n_readers_with_lock += is_reader;
 240
 241       /* Try to set head and tail to zero and thereby get the lock. */
 242       h2 = clib_smp_lock_set_header (l, h1, h0);
 243
 244       /* Compare and swap succeeded?  If so, we got the lock. */
 245       if (clib_smp_lock_header_is_equal (h2, h0))
 246         return;
 247
 248       /* Header for slow path. */
 249       h0 = h2;
 250     }
 251
 252   clib_smp_lock_slow_path (l, my_cpu, h0, type);
 253 }
 254
 255 always_inline void
 256 clib_smp_unlock_inline (clib_smp_lock_t * l, clib_smp_lock_type_t type)
 257 {
 258   clib_smp_lock_header_t h0, h1;
 259   uword is_reader = type == CLIB_SMP_LOCK_TYPE_READER;
 260   uword my_cpu;
 261
 262   /* Null means no locking is necessary. */
 263   if (! l)
 264     return;
 265
 266   my_cpu = os_get_cpu_number_inline ();
 267   h0 = l->header;
 268
 269   /* Should be locked. */
 270   if (is_reader)
 271     {
 272       ASSERT_AND_PANIC (h0.n_readers_with_lock != 0);
 273       ASSERT_AND_PANIC (h0.writer_has_lock == 0);
 274     }
 275   else
 276     {
 277       ASSERT_AND_PANIC (h0.n_readers_with_lock == 0);
 278       ASSERT_AND_PANIC (h0.writer_has_lock);
 279     }
 280
 281   /* Locked but empty waiting fifo? */
 282   while (h0.waiting_fifo.n_elts == 0)
 283     {
 284       /* Try to mark it unlocked. */
 285       h1 = h0;
 286       if (is_reader)
 287         h1.n_readers_with_lock -= 1;
 288       else
 289         h1.writer_has_lock = 0;
 290       h1.request_cpu = my_cpu;
 291       h1 = clib_smp_lock_set_header (l, h1, h0);
 292       if (clib_smp_lock_header_is_equal (h1, h0))
 293         return;
 294       h0 = h1;
 295     }
 296
 297   /* Other cpus are waiting. */
 298   clib_smp_unlock_slow_path (l, my_cpu, h0, type);
 299 }
 300
 301 always_inline void
 302 clib_smp_lock (clib_smp_lock_t * l)
 303 { clib_smp_lock_inline (l, CLIB_SMP_LOCK_TYPE_SPIN); }
 304
 305 always_inline void
 306 clib_smp_lock_for_writer (clib_smp_lock_t * l)
 307 { clib_smp_lock_inline (l, CLIB_SMP_LOCK_TYPE_WRITER); }
 308
 309 always_inline void
 310 clib_smp_lock_for_reader (clib_smp_lock_t * l)
 311 { clib_smp_lock_inline (l, CLIB_SMP_LOCK_TYPE_READER); }
 312
 313 always_inline void
 314 clib_smp_unlock (clib_smp_lock_t * l)
 315 { clib_smp_unlock_inline (l, CLIB_SMP_LOCK_TYPE_SPIN); }
 316
 317 always_inline void
 318 clib_smp_unlock_for_writer (clib_smp_lock_t * l)
 319 { clib_smp_unlock_inline (l, CLIB_SMP_LOCK_TYPE_WRITER); }
 320
 321 always_inline void
 322 clib_smp_unlock_for_reader (clib_smp_lock_t * l)
 323 { clib_smp_unlock_inline (l, CLIB_SMP_LOCK_TYPE_READER); }
 324
 325 #define clib_exec_on_global_heap(body)                                  \
 326 do {                                                                    \
 327   void * __clib_exec_on_global_heap_saved_heap;                         \
 328                                                                         \
 329   /* Switch to global (thread-safe) heap. */                            \
 330   __clib_exec_on_global_heap_saved_heap = clib_mem_set_heap (clib_smp_main.global_heap); \
 331                                                                         \
 332   /* Execute body. */                                                   \
 333   body;                                                                 \
 334                                                                         \
 335   /* Switch back to previous heap. */                                   \
 336   clib_mem_set_heap (__clib_exec_on_global_heap_saved_heap);            \
 337 } while (0)
 338
 339 uword os_smp_bootstrap (uword n_cpus,
 340                         void * bootstrap_function,
 341                         uword bootstrap_function_arg);
 342
 343 void clib_smp_init (void);
 344
 345 #endif /* included_clib_smp_h */