1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
|
/*--------------------------------------------------------------------*/
/*--- 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-2017 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, see <http://www.gnu.org/licenses/>.
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_core_libcproc.h"
#include "pub_core_mallocfree.h"
#include "pub_core_threadstate.h"
#include "pub_core_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 HChar *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));
// The futex syscall requires that a futex takes four bytes.
vg_assert(sizeof(p->futex[0]) == 4);
VG_(memset)(p, 0, sizeof(*p));
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 %u\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 %u - waiting until"
" futex[%ld] != %u\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) && sr_Err(sres) != VKI_EAGAIN) {
VG_(printf)("futex_wait() returned error code %lu\n", sr_Err(sres));
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 %u (futex[%ld] = %u)"
"\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 %u\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,
};
|
