coregrind/m_scheduler/ticket-lock-linux.c

   1
   2 /*--------------------------------------------------------------------*/
   3 /*--- Linux ticket lock implementation         ticket-lock-linux.c ---*/
   4 /*---                                                              ---*/
   5 /*--- Guarantees fair scheduling even if multiple threads are      ---*/
   6 /*--- runnable at the same time on a multicore system. Has been    ---*/
   7 /*--- observed to cause a slow-down compared to the generic        ---*/
   8 /*--- scheduler lock with CPU frequency scaling enabled. Makes     ---*/
   9 /*--- Valgrind slightly faster if CPU frequency scaling has been   ---*/
  10 /*--- disabled. See also http://bugs.kde.org/show_bug.cgi?id=270006---*/
  11 /*--------------------------------------------------------------------*/
  12
  13 /*
  14    This file is part of Valgrind, a dynamic binary instrumentation
  15    framework.
  16
  17    Copyright (C) 2011-2017 Bart Van Assche <bvanassche@acm.org>.
  18
  19    This program is free software; you can redistribute it and/or
  20    modify it under the terms of the GNU General Public License as
  21    published by the Free Software Foundation; either version 2 of the
  22    License, or (at your option) any later version.
  23
  24    This program is distributed in the hope that it will be useful, but
  25    WITHOUT ANY WARRANTY; without even the implied warranty of
  26    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  27    General Public License for more details.
  28
  29    You should have received a copy of the GNU General Public License
  30    along with this program; if not, see <http://www.gnu.org/licenses/>.
  31
  32    The GNU General Public License is contained in the file COPYING.
  33 */
  34
  35 #include "pub_core_basics.h"
  36 #include "pub_core_libcassert.h"
  37 #include "pub_core_libcbase.h"     // VG_(memset)()
  38 #include "pub_core_libcprint.h"
  39 #include "pub_core_syscall.h"
  40 #include "pub_core_vki.h"
  41 #include "pub_core_vkiscnums.h"    // __NR_futex
  42 #include "pub_core_libcproc.h"
  43 #include "pub_core_mallocfree.h"
  44 #include "pub_core_threadstate.h"
  45 #include "pub_core_inner.h"
  46 #if defined(ENABLE_INNER_CLIENT_REQUEST)
  47 #include "helgrind/helgrind.h"
  48 #endif
  49 #include "priv_sched-lock.h"
  50 #include "priv_sched-lock-impl.h"
  51
  52 #define TL_FUTEX_COUNT_LOG2 4
  53 #define TL_FUTEX_COUNT (1U << TL_FUTEX_COUNT_LOG2)
  54 #define TL_FUTEX_MASK (TL_FUTEX_COUNT - 1)
  55
  56 struct sched_lock {
  57    volatile unsigned head;
  58    volatile unsigned tail;
  59    volatile unsigned futex[TL_FUTEX_COUNT];
  60    int owner;
  61 };
  62
  63 #if 1
  64 static Bool s_debug;
  65 #else
  66 static Bool s_debug = True;
  67 #endif
  68
  69 static const HChar *get_sched_lock_name(void)
  70 {
  71    return "ticket lock";
  72 }
  73
  74 static struct sched_lock *create_sched_lock(void)
  75 {
  76    struct sched_lock *p;
  77
  78    p = VG_(malloc)("sched_lock", sizeof(*p));
  79
  80    // The futex syscall requires that a futex takes four bytes.
  81    vg_assert(sizeof(p->futex[0]) == 4);
  82
  83    VG_(memset)(p, 0, sizeof(*p));
  84
  85    INNER_REQUEST(ANNOTATE_RWLOCK_CREATE(p));
  86    INNER_REQUEST(ANNOTATE_BENIGN_RACE_SIZED(&p->futex, sizeof(p->futex), ""));
  87    return p;
  88 }
  89
  90 static void destroy_sched_lock(struct sched_lock *p)
  91 {
  92    INNER_REQUEST(ANNOTATE_RWLOCK_DESTROY(p));
  93    VG_(free)(p);
  94 }
  95
  96 static int get_sched_lock_owner(struct sched_lock *p)
  97 {
  98    return p->owner;
  99 }
 100
 101 /*
 102  * Acquire ticket lock. Increment the tail of the queue and use the original
 103  * value as the ticket value. Wait until the head of the queue equals the
 104  * ticket value. The futex used to wait depends on the ticket value in order
 105  * to avoid that all threads get woken up every time a ticket lock is
 106  * released. That last effect is sometimes called the "thundering herd"
 107  * effect.
 108  *
 109  * See also Nick Piggin, x86: FIFO ticket spinlocks, Linux kernel mailing list
 110  * (http://lkml.org/lkml/2007/11/1/125) for more info.
 111  */
 112 static void acquire_sched_lock(struct sched_lock *p)
 113 {
 114    unsigned ticket, futex_value;
 115    volatile unsigned *futex;
 116    SysRes sres;
 117
 118    ticket = __sync_fetch_and_add(&p->tail, 1);
 119    futex = &p->futex[ticket & TL_FUTEX_MASK];
 120    if (s_debug)
 121       VG_(printf)("[%d/%d] acquire: ticket %u\n", VG_(getpid)(),
 122                   VG_(gettid)(), ticket);
 123    for (;;) {
 124       futex_value = *futex;
 125       __sync_synchronize();
 126       if (ticket == p->head)
 127          break;
 128       if (s_debug)
 129          VG_(printf)("[%d/%d] acquire: ticket %u - waiting until"
 130                      " futex[%ld] != %u\n", VG_(getpid)(),
 131                      VG_(gettid)(), ticket, (long)(futex - p->futex),
 132                      futex_value);
 133       sres = VG_(do_syscall3)(__NR_futex, (UWord)futex,
 134                               VKI_FUTEX_WAIT | VKI_FUTEX_PRIVATE_FLAG,
 135                               futex_value);
 136       if (sr_isError(sres) && sr_Err(sres) != VKI_EAGAIN) {
 137          VG_(printf)("futex_wait() returned error code %lu\n", sr_Err(sres));
 138          vg_assert(False);
 139       }
 140    }
 141    __sync_synchronize();
 142    INNER_REQUEST(ANNOTATE_RWLOCK_ACQUIRED(p, /*is_w*/1));
 143    vg_assert(p->owner == 0);
 144    p->owner = VG_(gettid)();
 145 }
 146
 147 /*
 148  * Release a ticket lock by incrementing the head of the queue. Only generate
 149  * a thread wakeup signal if at least one thread is waiting. If the queue tail
 150  * matches the wakeup_ticket value, no threads have to be woken up.
 151  *
 152  * Note: tail will only be read after head has been incremented since both are
 153  * declared as volatile and since the __sync...() functions imply a memory
 154  * barrier.
 155  */
 156 static void release_sched_lock(struct sched_lock *p)
 157 {
 158    unsigned wakeup_ticket, futex_value;
 159    volatile unsigned *futex;
 160    SysRes sres;
 161
 162    vg_assert(p->owner != 0);
 163    p->owner = 0;
 164    INNER_REQUEST(ANNOTATE_RWLOCK_RELEASED(p, /*is_w*/1));
 165    wakeup_ticket = __sync_fetch_and_add(&p->head, 1) + 1;
 166    if (p->tail != wakeup_ticket) {
 167       futex = &p->futex[wakeup_ticket & TL_FUTEX_MASK];
 168       futex_value = __sync_fetch_and_add(futex, 1);
 169       if (s_debug)
 170          VG_(printf)("[%d/%d] release: waking up ticket %u (futex[%ld] = %u)"
 171                      "\n", VG_(getpid)(), VG_(gettid)(), wakeup_ticket,
 172                      (long)(futex - p->futex), futex_value);
 173       sres = VG_(do_syscall3)(__NR_futex, (UWord)futex,
 174                               VKI_FUTEX_WAKE | VKI_FUTEX_PRIVATE_FLAG,
 175                               0x7fffffff);
 176       vg_assert(!sr_isError(sres));
 177    } else {
 178       if (s_debug)
 179          VG_(printf)("[%d/%d] release: no thread is waiting for ticket %u\n",
 180                      VG_(getpid)(), VG_(gettid)(), wakeup_ticket);
 181    }
 182 }
 183
 184 const struct sched_lock_ops ML_(linux_ticket_lock_ops) = {
 185    .get_sched_lock_name  = get_sched_lock_name,
 186    .create_sched_lock    = create_sched_lock,
 187    .destroy_sched_lock   = destroy_sched_lock,
 188    .get_sched_lock_owner = get_sched_lock_owner,
 189    .acquire_sched_lock   = acquire_sched_lock,
 190    .release_sched_lock   = release_sched_lock,
 191 };