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 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, write to the Free Software
31 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
32 02111-1307, USA.
33
34 The GNU General Public License is contained in the file COPYING.
35 */
36
37 #include "pub_core_basics.h"
38 #include "pub_core_libcassert.h"
39 #include "pub_core_libcbase.h" // VG_(memset)()
40 #include "pub_core_libcprint.h"
41 #include "pub_core_syscall.h"
42 #include "pub_core_vki.h"
43 #include "pub_core_vkiscnums.h" // __NR_futex
44 #include "pub_tool_libcproc.h"
45 #include "pub_tool_mallocfree.h"
46 #include "pub_tool_threadstate.h"
47 #include "pub_tool_inner.h"
48 #if defined(ENABLE_INNER_CLIENT_REQUEST)
49 #include "helgrind/helgrind.h"
50 #endif
51 #include "priv_sched-lock.h"
52 #include "priv_sched-lock-impl.h"
53
54 #define TL_FUTEX_COUNT_LOG2 4
55 #define TL_FUTEX_COUNT (1U << TL_FUTEX_COUNT_LOG2)
56 #define TL_FUTEX_MASK (TL_FUTEX_COUNT - 1)
57
58 struct sched_lock {
59 volatile unsigned head;
60 volatile unsigned tail;
61 volatile unsigned futex[TL_FUTEX_COUNT];
62 int owner;
63 };
64
65 #if 1
66 static Bool s_debug;
67 #else
68 static Bool s_debug = True;
69 #endif
70
get_sched_lock_name(void)71 static const Char *get_sched_lock_name(void)
72 {
73 return "ticket lock";
74 }
75
create_sched_lock(void)76 static struct sched_lock *create_sched_lock(void)
77 {
78 struct sched_lock *p;
79
80 p = VG_(malloc)("sched_lock", sizeof(*p));
81 if (p) {
82 // The futex syscall requires that a futex takes four bytes.
83 vg_assert(sizeof(p->futex[0]) == 4);
84
85 p->head = 0;
86 p->tail = 0;
87 VG_(memset)((void*)p->futex, 0, sizeof(p->futex));
88 p->owner = 0;
89 }
90 INNER_REQUEST(ANNOTATE_RWLOCK_CREATE(p));
91 INNER_REQUEST(ANNOTATE_BENIGN_RACE_SIZED(&p->futex, sizeof(p->futex), ""));
92 return p;
93 }
94
destroy_sched_lock(struct sched_lock * p)95 static void destroy_sched_lock(struct sched_lock *p)
96 {
97 INNER_REQUEST(ANNOTATE_RWLOCK_DESTROY(p));
98 VG_(free)(p);
99 }
100
get_sched_lock_owner(struct sched_lock * p)101 static int get_sched_lock_owner(struct sched_lock *p)
102 {
103 return p->owner;
104 }
105
106 /*
107 * Acquire ticket lock. Increment the tail of the queue and use the original
108 * value as the ticket value. Wait until the head of the queue equals the
109 * ticket value. The futex used to wait depends on the ticket value in order
110 * to avoid that all threads get woken up every time a ticket lock is
111 * released. That last effect is sometimes called the "thundering herd"
112 * effect.
113 *
114 * See also Nick Piggin, x86: FIFO ticket spinlocks, Linux kernel mailing list
115 * (http://lkml.org/lkml/2007/11/1/125) for more info.
116 */
acquire_sched_lock(struct sched_lock * p)117 static void acquire_sched_lock(struct sched_lock *p)
118 {
119 unsigned ticket, futex_value;
120 volatile unsigned *futex;
121 SysRes sres;
122
123 ticket = __sync_fetch_and_add(&p->tail, 1);
124 futex = &p->futex[ticket & TL_FUTEX_MASK];
125 if (s_debug)
126 VG_(printf)("[%d/%d] acquire: ticket %d\n", VG_(getpid)(),
127 VG_(gettid)(), ticket);
128 for (;;) {
129 futex_value = *futex;
130 __sync_synchronize();
131 if (ticket == p->head)
132 break;
133 if (s_debug)
134 VG_(printf)("[%d/%d] acquire: ticket %d - waiting until"
135 " futex[%ld] != %d\n", VG_(getpid)(),
136 VG_(gettid)(), ticket, (long)(futex - p->futex),
137 futex_value);
138 sres = VG_(do_syscall3)(__NR_futex, (UWord)futex,
139 VKI_FUTEX_WAIT | VKI_FUTEX_PRIVATE_FLAG,
140 futex_value);
141 if (sr_isError(sres) && sres._val != VKI_EAGAIN) {
142 VG_(printf)("futex_wait() returned error code %ld\n", sres._val);
143 vg_assert(False);
144 }
145 }
146 __sync_synchronize();
147 INNER_REQUEST(ANNOTATE_RWLOCK_ACQUIRED(p, /*is_w*/1));
148 vg_assert(p->owner == 0);
149 p->owner = VG_(gettid)();
150 }
151
152 /*
153 * Release a ticket lock by incrementing the head of the queue. Only generate
154 * a thread wakeup signal if at least one thread is waiting. If the queue tail
155 * matches the wakeup_ticket value, no threads have to be woken up.
156 *
157 * Note: tail will only be read after head has been incremented since both are
158 * declared as volatile and since the __sync...() functions imply a memory
159 * barrier.
160 */
release_sched_lock(struct sched_lock * p)161 static void release_sched_lock(struct sched_lock *p)
162 {
163 unsigned wakeup_ticket, futex_value;
164 volatile unsigned *futex;
165 SysRes sres;
166
167 vg_assert(p->owner != 0);
168 p->owner = 0;
169 INNER_REQUEST(ANNOTATE_RWLOCK_RELEASED(p, /*is_w*/1));
170 wakeup_ticket = __sync_fetch_and_add(&p->head, 1) + 1;
171 if (p->tail != wakeup_ticket) {
172 futex = &p->futex[wakeup_ticket & TL_FUTEX_MASK];
173 futex_value = __sync_fetch_and_add(futex, 1);
174 if (s_debug)
175 VG_(printf)("[%d/%d] release: waking up ticket %d (futex[%ld] = %d)"
176 "\n", VG_(getpid)(), VG_(gettid)(), wakeup_ticket,
177 (long)(futex - p->futex), futex_value);
178 sres = VG_(do_syscall3)(__NR_futex, (UWord)futex,
179 VKI_FUTEX_WAKE | VKI_FUTEX_PRIVATE_FLAG,
180 0x7fffffff);
181 vg_assert(!sr_isError(sres));
182 } else {
183 if (s_debug)
184 VG_(printf)("[%d/%d] release: no thread is waiting for ticket %d\n",
185 VG_(getpid)(), VG_(gettid)(), wakeup_ticket);
186 }
187 }
188
189 const struct sched_lock_ops ML_(linux_ticket_lock_ops) = {
190 .get_sched_lock_name = get_sched_lock_name,
191 .create_sched_lock = create_sched_lock,
192 .destroy_sched_lock = destroy_sched_lock,
193 .get_sched_lock_owner = get_sched_lock_owner,
194 .acquire_sched_lock = acquire_sched_lock,
195 .release_sched_lock = release_sched_lock,
196 };
197