vppinfra/vppinfra/smp.c

   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, 2002, 2003 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 #include <vppinfra/longjmp.h>
  39 #include <vppinfra/mheap.h>
  40 #include <vppinfra/os.h>
  41
  42 void clib_smp_free (clib_smp_main_t * m)
  43 {
  44   clib_mem_vm_free (m->vm_base, (uword) ((1 + m->n_cpus) << m->log2_n_per_cpu_vm_bytes));
  45 }
  46
  47 static uword allocate_per_cpu_mheap (uword cpu)
  48 {
  49   clib_smp_main_t * m = &clib_smp_main;
  50   void * heap;
  51   uword vm_size, stack_size, mheap_flags;
  52
  53   ASSERT (os_get_cpu_number () == cpu);
  54
  55   vm_size = (uword) 1 << m->log2_n_per_cpu_vm_bytes;
  56   stack_size = (uword) 1 << m->log2_n_per_cpu_stack_bytes;
  57
  58   mheap_flags = MHEAP_FLAG_SMALL_OBJECT_CACHE;
  59
  60   /* Heap extends up to start of stack. */
  61   heap = mheap_alloc_with_flags (clib_smp_vm_base_for_cpu (m, cpu),
  62                                  vm_size - stack_size,
  63                                  mheap_flags);
  64   clib_mem_set_heap (heap);
  65
  66   if (cpu == 0)
  67     {
  68       /* Now that we have a heap, allocate main structure on cpu 0. */
  69       vec_resize (m->per_cpu_mains, m->n_cpus);
  70
  71       /* Allocate shared global heap (thread safe). */
  72       m->global_heap =
  73         mheap_alloc_with_flags (clib_smp_vm_base_for_cpu (m, cpu + m->n_cpus),
  74                                 vm_size,
  75                                 mheap_flags | MHEAP_FLAG_THREAD_SAFE);
  76     }
  77
  78   m->per_cpu_mains[cpu].heap = heap;
  79   return 0;
  80 }
  81
  82 void clib_smp_init (void)
  83 {
  84   clib_smp_main_t * m = &clib_smp_main;
  85   uword cpu;
  86
  87   m->vm_base = clib_mem_vm_alloc ((uword) (m->n_cpus + 1) << m->log2_n_per_cpu_vm_bytes);
  88   if (! m->vm_base)
  89     clib_error ("error allocating virtual memory");
  90
  91   for (cpu = 0; cpu < m->n_cpus; cpu++)
  92     clib_calljmp (allocate_per_cpu_mheap, cpu,
  93                   clib_smp_stack_top_for_cpu (m, cpu));
  94 }
  95
  96 void clib_smp_lock_init (clib_smp_lock_t ** pl)
  97 {
  98   clib_smp_lock_t * l;
  99   uword i, n_bytes, n_fifo_elts;
 100
 101   /* No locking necessary if n_cpus <= 1.
 102      Null means no locking is necessary. */
 103   if (clib_smp_main.n_cpus < 2)
 104     {
 105       *pl = 0;
 106       return;
 107     }
 108
 109   /* Need n_cpus - 1 elts in waiting fifo.  One CPU holds lock
 110      and others could potentially be waiting. */
 111   n_fifo_elts = clib_smp_main.n_cpus - 1;
 112
 113   n_bytes = sizeof (l[0]) + n_fifo_elts * sizeof (l->waiting_fifo[0]);
 114   ASSERT_AND_PANIC (n_bytes % CLIB_CACHE_LINE_BYTES == 0);
 115
 116   l = clib_mem_alloc_aligned (n_bytes, CLIB_CACHE_LINE_BYTES);
 117
 118   memset (l, 0, n_bytes);
 119   l->n_waiting_fifo_elts = n_fifo_elts;
 120
 121   for (i = 0; i < l->n_waiting_fifo_elts; i++)
 122     l->waiting_fifo[i].wait_type = CLIB_SMP_LOCK_WAIT_EMPTY;
 123
 124   *pl = l;
 125 }
 126
 127 void clib_smp_lock_free (clib_smp_lock_t ** pl)
 128 {
 129   if (*pl)
 130     clib_mem_free (*pl);
 131   *pl = 0;
 132 }
 133
 134 void clib_smp_lock_slow_path (clib_smp_lock_t * l,
 135                               uword my_cpu,
 136                               clib_smp_lock_header_t h0,
 137                               clib_smp_lock_type_t type)
 138 {
 139   clib_smp_lock_header_t h1, h2, h3;
 140   uword is_reader = type == CLIB_SMP_LOCK_TYPE_READER;
 141   uword n_fifo_elts = l->n_waiting_fifo_elts;
 142   uword my_tail;
 143
 144   /* Atomically advance waiting FIFO tail pointer; my_tail will point
 145      to entry where we can insert ourselves to wait for lock to be granted. */
 146   while (1)
 147     {
 148       h1 = h0;
 149       my_tail = h1.waiting_fifo.head_index + h1.waiting_fifo.n_elts;
 150       my_tail = my_tail >= n_fifo_elts ? my_tail - n_fifo_elts : my_tail;
 151       h1.waiting_fifo.n_elts += 1;
 152       h1.request_cpu = my_cpu;
 153
 154       ASSERT_AND_PANIC (h1.waiting_fifo.n_elts <= n_fifo_elts);
 155       ASSERT_AND_PANIC (my_tail >= 0 && my_tail < n_fifo_elts);
 156
 157       h2 = clib_smp_lock_set_header (l, h1, h0);
 158
 159       /* Tail successfully advanced? */
 160       if (clib_smp_lock_header_is_equal (h0, h2))
 161         break;
 162
 163       /* It is possible that if head and tail are both zero, CPU with lock would have unlocked lock. */
 164       else if (type == CLIB_SMP_LOCK_TYPE_SPIN)
 165         {
 166           while (! h2.writer_has_lock)
 167             {
 168               ASSERT_AND_PANIC (h2.waiting_fifo.n_elts == 0);
 169               h1 = h2;
 170               h1.request_cpu = my_cpu;
 171               h1.writer_has_lock = 1;
 172
 173               h3 = clib_smp_lock_set_header (l, h1, h2);
 174
 175               /* Got it? */
 176               if (clib_smp_lock_header_is_equal (h2, h3))
 177                 return;
 178
 179               h2 = h3;
 180             }
 181         }
 182
 183       /* Try to advance tail again. */
 184       h0 = h2;
 185     }
 186
 187   {
 188     clib_smp_lock_waiting_fifo_elt_t * w;
 189
 190     w = l->waiting_fifo + my_tail;
 191
 192     while (w->wait_type != CLIB_SMP_LOCK_WAIT_EMPTY)
 193       clib_smp_pause ();
 194
 195     w->wait_type = (is_reader
 196                     ? CLIB_SMP_LOCK_WAIT_READER
 197                     : CLIB_SMP_LOCK_WAIT_WRITER);
 198
 199     /* Wait until CPU holding the lock grants us the lock. */
 200     while (w->wait_type != CLIB_SMP_LOCK_WAIT_DONE)
 201       clib_smp_pause ();
 202
 203     w->wait_type = CLIB_SMP_LOCK_WAIT_EMPTY;
 204   }
 205 }
 206
 207 void clib_smp_unlock_slow_path (clib_smp_lock_t * l,
 208                                 uword my_cpu,
 209                                 clib_smp_lock_header_t h0,
 210                                 clib_smp_lock_type_t type)
 211 {
 212   clib_smp_lock_header_t h1, h2;
 213   clib_smp_lock_waiting_fifo_elt_t * head;
 214   clib_smp_lock_wait_type_t head_wait_type;
 215   uword is_reader = type == CLIB_SMP_LOCK_TYPE_READER;
 216   uword n_fifo_elts = l->n_waiting_fifo_elts;
 217   uword head_index, must_wait_for_readers;
 218
 219   while (1)
 220     {
 221       /* Advance waiting fifo giving lock to first waiter. */
 222       while (1)
 223         {
 224           ASSERT_AND_PANIC (h0.waiting_fifo.n_elts != 0);
 225
 226           h1 = h0;
 227
 228           head_index = h1.waiting_fifo.head_index;
 229           head = l->waiting_fifo + head_index;
 230           if (is_reader)
 231             {
 232               ASSERT_AND_PANIC (h1.n_readers_with_lock > 0);
 233               h1.n_readers_with_lock -= 1;
 234             }
 235           else
 236             {
 237               /* Writer will already have lock. */
 238               ASSERT_AND_PANIC (h1.writer_has_lock);
 239             }
 240
 241           while ((head_wait_type = head->wait_type) == CLIB_SMP_LOCK_WAIT_EMPTY)
 242             clib_smp_pause ();
 243
 244           /* Don't advance FIFO to writer unless all readers have unlocked. */
 245           must_wait_for_readers =
 246             (type != CLIB_SMP_LOCK_TYPE_SPIN
 247              && head_wait_type == CLIB_SMP_LOCK_WAIT_WRITER
 248              && h1.n_readers_with_lock != 0);
 249
 250           if (! must_wait_for_readers)
 251             {
 252               head_index += 1;
 253               h1.waiting_fifo.n_elts -= 1;
 254               if (type != CLIB_SMP_LOCK_TYPE_SPIN)
 255                 {
 256                   if (head_wait_type == CLIB_SMP_LOCK_WAIT_WRITER)
 257                     h1.writer_has_lock = h1.n_readers_with_lock == 0;
 258                   else
 259                     {
 260                       h1.writer_has_lock = 0;
 261                       h1.n_readers_with_lock += 1;
 262                     }
 263                 }
 264             }
 265
 266           h1.waiting_fifo.head_index = head_index == n_fifo_elts ? 0 : head_index;
 267           h1.request_cpu = my_cpu;
 268
 269           ASSERT_AND_PANIC (h1.waiting_fifo.head_index >= 0 && h1.waiting_fifo.head_index < n_fifo_elts);
 270           ASSERT_AND_PANIC (h1.waiting_fifo.n_elts >= 0 && h1.waiting_fifo.n_elts <= n_fifo_elts);
 271
 272           h2 = clib_smp_lock_set_header (l, h1, h0);
 273
 274           if (clib_smp_lock_header_is_equal (h2, h0))
 275             break;
 276
 277           h0 = h2;
 278
 279           if (h0.waiting_fifo.n_elts == 0)
 280             return clib_smp_unlock_inline (l, type);
 281         }
 282
 283       if (must_wait_for_readers)
 284         return;
 285
 286       /* Wake up head of waiting fifo. */
 287       {
 288         uword done_waking;
 289
 290         /* Shift lock to first thread waiting in fifo. */
 291         head->wait_type = CLIB_SMP_LOCK_WAIT_DONE;
 292
 293         /* For read locks we may be able to wake multiple readers. */
 294         done_waking = 1;
 295         if (head_wait_type == CLIB_SMP_LOCK_WAIT_READER)
 296           {
 297             uword hi = h0.waiting_fifo.head_index;
 298             if (h0.waiting_fifo.n_elts != 0
 299                 && l->waiting_fifo[hi].wait_type == CLIB_SMP_LOCK_WAIT_READER)
 300               done_waking = 0;
 301           }
 302
 303         if (done_waking)
 304           break;
 305       }
 306     }
 307 }