/*--------------------------------------------------------------------*/
/*--- Linux ticket lock implementation ticket-lock-linux.c ---*/
/*--- ---*/
/*--- Guarantees fair scheduling even if multiple threads are ---*/
/*--- runnable at the same time on a multicore system. Has been ---*/
/*--- observed to cause a slow-down compared to the generic ---*/
/*--- scheduler lock with CPU frequency scaling enabled. Makes ---*/
/*--- Valgrind slightly faster if CPU frequency scaling has been ---*/
/*--- disabled. See also http://bugs.kde.org/show_bug.cgi?id=270006---*/
/*--------------------------------------------------------------------*/
/*
This file is part of Valgrind, a dynamic binary instrumentation
framework.
Copyright (C) 2011 Bart Van Assche <bvanassche@acm.org>.
This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License as
published by the Free Software Foundation; either version 2 of the
License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
02111-1307, USA.
The GNU General Public License is contained in the file COPYING.
*/
#include "pub_core_basics.h"
#include "pub_core_libcassert.h"
#include "pub_core_libcbase.h" // VG_(memset)()
#include "pub_core_libcprint.h"
#include "pub_core_syscall.h"
#include "pub_core_vki.h"
#include "pub_core_vkiscnums.h" // __NR_futex
#include "pub_tool_libcproc.h"
#include "pub_tool_mallocfree.h"
#include "pub_tool_threadstate.h"
#include "pub_tool_inner.h"
#if defined(ENABLE_INNER_CLIENT_REQUEST)
#include "helgrind/helgrind.h"
#endif
#include "priv_sched-lock.h"
#include "priv_sched-lock-impl.h"
#define TL_FUTEX_COUNT_LOG2 4
#define TL_FUTEX_COUNT (1U << TL_FUTEX_COUNT_LOG2)
#define TL_FUTEX_MASK (TL_FUTEX_COUNT - 1)
struct sched_lock {
volatile unsigned head;
volatile unsigned tail;
volatile unsigned futex[TL_FUTEX_COUNT];
int owner;
};
#if 1
static Bool s_debug;
#else
static Bool s_debug = True;
#endif
static const Char *get_sched_lock_name(void)
{
return "ticket lock";
}
static struct sched_lock *create_sched_lock(void)
{
struct sched_lock *p;
p = VG_(malloc)("sched_lock", sizeof(*p));
if (p) {
// The futex syscall requires that a futex takes four bytes.
vg_assert(sizeof(p->futex[0]) == 4);
p->head = 0;
p->tail = 0;
VG_(memset)((void*)p->futex, 0, sizeof(p->futex));
p->owner = 0;
}
INNER_REQUEST(ANNOTATE_RWLOCK_CREATE(p));
INNER_REQUEST(ANNOTATE_BENIGN_RACE_SIZED(&p->futex, sizeof(p->futex), ""));
return p;
}
static void destroy_sched_lock(struct sched_lock *p)
{
INNER_REQUEST(ANNOTATE_RWLOCK_DESTROY(p));
VG_(free)(p);
}
static int get_sched_lock_owner(struct sched_lock *p)
{
return p->owner;
}
/*
* Acquire ticket lock. Increment the tail of the queue and use the original
* value as the ticket value. Wait until the head of the queue equals the
* ticket value. The futex used to wait depends on the ticket value in order
* to avoid that all threads get woken up every time a ticket lock is
* released. That last effect is sometimes called the "thundering herd"
* effect.
*
* See also Nick Piggin, x86: FIFO ticket spinlocks, Linux kernel mailing list
* (http://lkml.org/lkml/2007/11/1/125) for more info.
*/
static void acquire_sched_lock(struct sched_lock *p)
{
unsigned ticket, futex_value;
volatile unsigned *futex;
SysRes sres;
ticket = __sync_fetch_and_add(&p->tail, 1);
futex = &p->futex[ticket & TL_FUTEX_MASK];
if (s_debug)
VG_(printf)("[%d/%d] acquire: ticket %d\n", VG_(getpid)(),
VG_(gettid)(), ticket);
for (;;) {
futex_value = *futex;
__sync_synchronize();
if (ticket == p->head)
break;
if (s_debug)
VG_(printf)("[%d/%d] acquire: ticket %d - waiting until"
" futex[%ld] != %d\n", VG_(getpid)(),
VG_(gettid)(), ticket, (long)(futex - p->futex),
futex_value);
sres = VG_(do_syscall3)(__NR_futex, (UWord)futex,
VKI_FUTEX_WAIT | VKI_FUTEX_PRIVATE_FLAG,
futex_value);
if (sr_isError(sres) && sres._val != VKI_EAGAIN) {
VG_(printf)("futex_wait() returned error code %ld\n", sres._val);
vg_assert(False);
}
}
__sync_synchronize();
INNER_REQUEST(ANNOTATE_RWLOCK_ACQUIRED(p, /*is_w*/1));
vg_assert(p->owner == 0);
p->owner = VG_(gettid)();
}
/*
* Release a ticket lock by incrementing the head of the queue. Only generate
* a thread wakeup signal if at least one thread is waiting. If the queue tail
* matches the wakeup_ticket value, no threads have to be woken up.
*
* Note: tail will only be read after head has been incremented since both are
* declared as volatile and since the __sync...() functions imply a memory
* barrier.
*/
static void release_sched_lock(struct sched_lock *p)
{
unsigned wakeup_ticket, futex_value;
volatile unsigned *futex;
SysRes sres;
vg_assert(p->owner != 0);
p->owner = 0;
INNER_REQUEST(ANNOTATE_RWLOCK_RELEASED(p, /*is_w*/1));
wakeup_ticket = __sync_fetch_and_add(&p->head, 1) + 1;
if (p->tail != wakeup_ticket) {
futex = &p->futex[wakeup_ticket & TL_FUTEX_MASK];
futex_value = __sync_fetch_and_add(futex, 1);
if (s_debug)
VG_(printf)("[%d/%d] release: waking up ticket %d (futex[%ld] = %d)"
"\n", VG_(getpid)(), VG_(gettid)(), wakeup_ticket,
(long)(futex - p->futex), futex_value);
sres = VG_(do_syscall3)(__NR_futex, (UWord)futex,
VKI_FUTEX_WAKE | VKI_FUTEX_PRIVATE_FLAG,
0x7fffffff);
vg_assert(!sr_isError(sres));
} else {
if (s_debug)
VG_(printf)("[%d/%d] release: no thread is waiting for ticket %d\n",
VG_(getpid)(), VG_(gettid)(), wakeup_ticket);
}
}
const struct sched_lock_ops ML_(linux_ticket_lock_ops) = {
.get_sched_lock_name = get_sched_lock_name,
.create_sched_lock = create_sched_lock,
.destroy_sched_lock = destroy_sched_lock,
.get_sched_lock_owner = get_sched_lock_owner,
.acquire_sched_lock = acquire_sched_lock,
.release_sched_lock = release_sched_lock,
};