blob: 0cf84c8664f207c574325b899ef2e57f01295a94 [file] [log] [blame]
Thomas Gleixner1a59d1b82019-05-27 08:55:05 +02001// SPDX-License-Identifier: GPL-2.0-or-later
Linus Torvalds1da177e2005-04-16 15:20:36 -07002/*
3 * Fast Userspace Mutexes (which I call "Futexes!").
4 * (C) Rusty Russell, IBM 2002
5 *
6 * Generalized futexes, futex requeueing, misc fixes by Ingo Molnar
7 * (C) Copyright 2003 Red Hat Inc, All Rights Reserved
8 *
9 * Removed page pinning, fix privately mapped COW pages and other cleanups
10 * (C) Copyright 2003, 2004 Jamie Lokier
11 *
Ingo Molnar0771dfe2006-03-27 01:16:22 -080012 * Robust futex support started by Ingo Molnar
13 * (C) Copyright 2006 Red Hat Inc, All Rights Reserved
14 * Thanks to Thomas Gleixner for suggestions, analysis and fixes.
15 *
Ingo Molnarc87e2832006-06-27 02:54:58 -070016 * PI-futex support started by Ingo Molnar and Thomas Gleixner
17 * Copyright (C) 2006 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
18 * Copyright (C) 2006 Timesys Corp., Thomas Gleixner <tglx@timesys.com>
19 *
Eric Dumazet34f01cc2007-05-09 02:35:04 -070020 * PRIVATE futexes by Eric Dumazet
21 * Copyright (C) 2007 Eric Dumazet <dada1@cosmosbay.com>
22 *
Darren Hart52400ba2009-04-03 13:40:49 -070023 * Requeue-PI support by Darren Hart <dvhltc@us.ibm.com>
24 * Copyright (C) IBM Corporation, 2009
25 * Thanks to Thomas Gleixner for conceptual design and careful reviews.
26 *
Linus Torvalds1da177e2005-04-16 15:20:36 -070027 * Thanks to Ben LaHaise for yelling "hashed waitqueues" loudly
28 * enough at me, Linus for the original (flawed) idea, Matthew
29 * Kirkwood for proof-of-concept implementation.
30 *
31 * "The futexes are also cursed."
32 * "But they come in a choice of three flavours!"
Linus Torvalds1da177e2005-04-16 15:20:36 -070033 */
Arnd Bergmann04e77122018-04-17 16:31:07 +020034#include <linux/compat.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070035#include <linux/slab.h>
36#include <linux/poll.h>
37#include <linux/fs.h>
38#include <linux/file.h>
39#include <linux/jhash.h>
40#include <linux/init.h>
41#include <linux/futex.h>
42#include <linux/mount.h>
43#include <linux/pagemap.h>
44#include <linux/syscalls.h>
Jesper Juhl7ed20e12005-05-01 08:59:14 -070045#include <linux/signal.h>
Paul Gortmaker9984de12011-05-23 14:51:41 -040046#include <linux/export.h>
Andrey Mirkinfd5eea42007-10-16 23:30:13 -070047#include <linux/magic.h>
Pavel Emelyanovb4888932007-10-18 23:40:14 -070048#include <linux/pid.h>
49#include <linux/nsproxy.h>
Kees Cookbdbb7762012-03-19 16:12:53 -070050#include <linux/ptrace.h>
Clark Williams8bd75c72013-02-07 09:47:07 -060051#include <linux/sched/rt.h>
Ingo Molnar84f001e2017-02-01 16:36:40 +010052#include <linux/sched/wake_q.h>
Ingo Molnar6e84f312017-02-08 18:51:29 +010053#include <linux/sched/mm.h>
Zhang Yi13d60f42013-06-25 21:19:31 +080054#include <linux/hugetlb.h>
Colin Cross88c80042013-05-01 18:35:05 -070055#include <linux/freezer.h>
Mike Rapoport57c8a662018-10-30 15:09:49 -070056#include <linux/memblock.h>
Davidlohr Buesoab51fba2015-06-29 23:26:02 -070057#include <linux/fault-inject.h>
Elena Reshetova49262de2019-02-05 14:24:27 +020058#include <linux/refcount.h>
Pavel Emelyanovb4888932007-10-18 23:40:14 -070059
Jakub Jelinek4732efbe2005-09-06 15:16:25 -070060#include <asm/futex.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070061
Peter Zijlstra1696a8b2013-10-31 18:18:19 +010062#include "locking/rtmutex_common.h"
Ingo Molnarc87e2832006-06-27 02:54:58 -070063
Thomas Gleixner99b60ce2014-01-12 15:31:24 -080064/*
Davidlohr Buesod7e8af12014-04-09 11:55:07 -070065 * READ this before attempting to hack on futexes!
66 *
67 * Basic futex operation and ordering guarantees
68 * =============================================
Thomas Gleixner99b60ce2014-01-12 15:31:24 -080069 *
70 * The waiter reads the futex value in user space and calls
71 * futex_wait(). This function computes the hash bucket and acquires
72 * the hash bucket lock. After that it reads the futex user space value
Davidlohr Buesob0c29f72014-01-12 15:31:25 -080073 * again and verifies that the data has not changed. If it has not changed
74 * it enqueues itself into the hash bucket, releases the hash bucket lock
75 * and schedules.
Thomas Gleixner99b60ce2014-01-12 15:31:24 -080076 *
77 * The waker side modifies the user space value of the futex and calls
Davidlohr Buesob0c29f72014-01-12 15:31:25 -080078 * futex_wake(). This function computes the hash bucket and acquires the
79 * hash bucket lock. Then it looks for waiters on that futex in the hash
80 * bucket and wakes them.
Thomas Gleixner99b60ce2014-01-12 15:31:24 -080081 *
Davidlohr Buesob0c29f72014-01-12 15:31:25 -080082 * In futex wake up scenarios where no tasks are blocked on a futex, taking
83 * the hb spinlock can be avoided and simply return. In order for this
84 * optimization to work, ordering guarantees must exist so that the waiter
85 * being added to the list is acknowledged when the list is concurrently being
86 * checked by the waker, avoiding scenarios like the following:
Thomas Gleixner99b60ce2014-01-12 15:31:24 -080087 *
88 * CPU 0 CPU 1
89 * val = *futex;
90 * sys_futex(WAIT, futex, val);
91 * futex_wait(futex, val);
92 * uval = *futex;
93 * *futex = newval;
94 * sys_futex(WAKE, futex);
95 * futex_wake(futex);
96 * if (queue_empty())
97 * return;
98 * if (uval == val)
99 * lock(hash_bucket(futex));
100 * queue();
101 * unlock(hash_bucket(futex));
102 * schedule();
103 *
104 * This would cause the waiter on CPU 0 to wait forever because it
105 * missed the transition of the user space value from val to newval
106 * and the waker did not find the waiter in the hash bucket queue.
Thomas Gleixner99b60ce2014-01-12 15:31:24 -0800107 *
Davidlohr Buesob0c29f72014-01-12 15:31:25 -0800108 * The correct serialization ensures that a waiter either observes
109 * the changed user space value before blocking or is woken by a
110 * concurrent waker:
111 *
112 * CPU 0 CPU 1
Thomas Gleixner99b60ce2014-01-12 15:31:24 -0800113 * val = *futex;
114 * sys_futex(WAIT, futex, val);
115 * futex_wait(futex, val);
Davidlohr Buesob0c29f72014-01-12 15:31:25 -0800116 *
Davidlohr Buesod7e8af12014-04-09 11:55:07 -0700117 * waiters++; (a)
Davidlohr Bueso8ad7b372016-02-09 11:15:13 -0800118 * smp_mb(); (A) <-- paired with -.
119 * |
120 * lock(hash_bucket(futex)); |
121 * |
122 * uval = *futex; |
123 * | *futex = newval;
124 * | sys_futex(WAKE, futex);
125 * | futex_wake(futex);
126 * |
127 * `--------> smp_mb(); (B)
Thomas Gleixner99b60ce2014-01-12 15:31:24 -0800128 * if (uval == val)
Davidlohr Buesob0c29f72014-01-12 15:31:25 -0800129 * queue();
Thomas Gleixner99b60ce2014-01-12 15:31:24 -0800130 * unlock(hash_bucket(futex));
Davidlohr Buesob0c29f72014-01-12 15:31:25 -0800131 * schedule(); if (waiters)
132 * lock(hash_bucket(futex));
Davidlohr Buesod7e8af12014-04-09 11:55:07 -0700133 * else wake_waiters(futex);
134 * waiters--; (b) unlock(hash_bucket(futex));
Davidlohr Buesob0c29f72014-01-12 15:31:25 -0800135 *
Davidlohr Buesod7e8af12014-04-09 11:55:07 -0700136 * Where (A) orders the waiters increment and the futex value read through
137 * atomic operations (see hb_waiters_inc) and where (B) orders the write
Davidlohr Bueso993b2ff2014-10-23 20:27:00 -0700138 * to futex and the waiters read -- this is done by the barriers for both
139 * shared and private futexes in get_futex_key_refs().
Davidlohr Buesob0c29f72014-01-12 15:31:25 -0800140 *
141 * This yields the following case (where X:=waiters, Y:=futex):
142 *
143 * X = Y = 0
144 *
145 * w[X]=1 w[Y]=1
146 * MB MB
147 * r[Y]=y r[X]=x
148 *
149 * Which guarantees that x==0 && y==0 is impossible; which translates back into
150 * the guarantee that we cannot both miss the futex variable change and the
151 * enqueue.
Davidlohr Buesod7e8af12014-04-09 11:55:07 -0700152 *
153 * Note that a new waiter is accounted for in (a) even when it is possible that
154 * the wait call can return error, in which case we backtrack from it in (b).
155 * Refer to the comment in queue_lock().
156 *
157 * Similarly, in order to account for waiters being requeued on another
158 * address we always increment the waiters for the destination bucket before
159 * acquiring the lock. It then decrements them again after releasing it -
160 * the code that actually moves the futex(es) between hash buckets (requeue_futex)
161 * will do the additional required waiter count housekeeping. This is done for
162 * double_lock_hb() and double_unlock_hb(), respectively.
Thomas Gleixner99b60ce2014-01-12 15:31:24 -0800163 */
164
Arnd Bergmann04e77122018-04-17 16:31:07 +0200165#ifdef CONFIG_HAVE_FUTEX_CMPXCHG
166#define futex_cmpxchg_enabled 1
167#else
168static int __read_mostly futex_cmpxchg_enabled;
Heiko Carstens03b8c7b2014-03-02 13:09:47 +0100169#endif
Thomas Gleixnera0c1e902008-02-23 15:23:57 -0800170
Linus Torvalds1da177e2005-04-16 15:20:36 -0700171/*
Darren Hartb41277d2010-11-08 13:10:09 -0800172 * Futex flags used to encode options to functions and preserve them across
173 * restarts.
174 */
Thomas Gleixner784bdf32016-07-29 16:32:30 +0200175#ifdef CONFIG_MMU
176# define FLAGS_SHARED 0x01
177#else
178/*
179 * NOMMU does not have per process address space. Let the compiler optimize
180 * code away.
181 */
182# define FLAGS_SHARED 0x00
183#endif
Darren Hartb41277d2010-11-08 13:10:09 -0800184#define FLAGS_CLOCKRT 0x02
185#define FLAGS_HAS_TIMEOUT 0x04
186
187/*
Ingo Molnarc87e2832006-06-27 02:54:58 -0700188 * Priority Inheritance state:
189 */
190struct futex_pi_state {
191 /*
192 * list of 'owned' pi_state instances - these have to be
193 * cleaned up in do_exit() if the task exits prematurely:
194 */
195 struct list_head list;
196
197 /*
198 * The PI object:
199 */
200 struct rt_mutex pi_mutex;
201
202 struct task_struct *owner;
Elena Reshetova49262de2019-02-05 14:24:27 +0200203 refcount_t refcount;
Ingo Molnarc87e2832006-06-27 02:54:58 -0700204
205 union futex_key key;
Kees Cook3859a272016-10-28 01:22:25 -0700206} __randomize_layout;
Ingo Molnarc87e2832006-06-27 02:54:58 -0700207
Darren Hartd8d88fb2009-09-21 22:30:30 -0700208/**
209 * struct futex_q - The hashed futex queue entry, one per waiting task
Randy Dunlapfb62db22010-10-13 11:02:34 -0700210 * @list: priority-sorted list of tasks waiting on this futex
Darren Hartd8d88fb2009-09-21 22:30:30 -0700211 * @task: the task waiting on the futex
212 * @lock_ptr: the hash bucket lock
213 * @key: the key the futex is hashed on
214 * @pi_state: optional priority inheritance state
215 * @rt_waiter: rt_waiter storage for use with requeue_pi
216 * @requeue_pi_key: the requeue_pi target futex key
217 * @bitset: bitset for the optional bitmasked wakeup
218 *
Ingo Molnarac6424b2017-06-20 12:06:13 +0200219 * We use this hashed waitqueue, instead of a normal wait_queue_entry_t, so
Linus Torvalds1da177e2005-04-16 15:20:36 -0700220 * we can wake only the relevant ones (hashed queues may be shared).
221 *
222 * A futex_q has a woken state, just like tasks have TASK_RUNNING.
Pierre Peifferec92d082007-05-09 02:35:00 -0700223 * It is considered woken when plist_node_empty(&q->list) || q->lock_ptr == 0.
Randy Dunlapfb62db22010-10-13 11:02:34 -0700224 * The order of wakeup is always to make the first condition true, then
Darren Hartd8d88fb2009-09-21 22:30:30 -0700225 * the second.
226 *
227 * PI futexes are typically woken before they are removed from the hash list via
228 * the rt_mutex code. See unqueue_me_pi().
Linus Torvalds1da177e2005-04-16 15:20:36 -0700229 */
230struct futex_q {
Pierre Peifferec92d082007-05-09 02:35:00 -0700231 struct plist_node list;
Darren Hartd8d88fb2009-09-21 22:30:30 -0700232
Thomas Gleixnerf1a11e02009-05-05 19:21:40 +0200233 struct task_struct *task;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700234 spinlock_t *lock_ptr;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700235 union futex_key key;
Ingo Molnarc87e2832006-06-27 02:54:58 -0700236 struct futex_pi_state *pi_state;
Darren Hart52400ba2009-04-03 13:40:49 -0700237 struct rt_mutex_waiter *rt_waiter;
Darren Hart84bc4af2009-08-13 17:36:53 -0700238 union futex_key *requeue_pi_key;
Thomas Gleixnercd6899852008-02-01 17:45:14 +0100239 u32 bitset;
Kees Cook3859a272016-10-28 01:22:25 -0700240} __randomize_layout;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700241
Darren Hart5bdb05f2010-11-08 13:40:28 -0800242static const struct futex_q futex_q_init = {
243 /* list gets initialized in queue_me()*/
244 .key = FUTEX_KEY_INIT,
245 .bitset = FUTEX_BITSET_MATCH_ANY
246};
247
Linus Torvalds1da177e2005-04-16 15:20:36 -0700248/*
Darren Hartb2d09942009-03-12 00:55:37 -0700249 * Hash buckets are shared by all the futex_keys that hash to the same
250 * location. Each key may have multiple futex_q structures, one for each task
251 * waiting on a futex.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700252 */
253struct futex_hash_bucket {
Linus Torvalds11d46162014-03-20 22:11:17 -0700254 atomic_t waiters;
Pierre Peifferec92d082007-05-09 02:35:00 -0700255 spinlock_t lock;
256 struct plist_head chain;
Davidlohr Buesoa52b89e2014-01-12 15:31:23 -0800257} ____cacheline_aligned_in_smp;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700258
Rasmus Villemoesac742d32015-09-09 23:36:40 +0200259/*
260 * The base of the bucket array and its size are always used together
261 * (after initialization only in hash_futex()), so ensure that they
262 * reside in the same cacheline.
263 */
264static struct {
265 struct futex_hash_bucket *queues;
266 unsigned long hashsize;
267} __futex_data __read_mostly __aligned(2*sizeof(long));
268#define futex_queues (__futex_data.queues)
269#define futex_hashsize (__futex_data.hashsize)
Davidlohr Buesoa52b89e2014-01-12 15:31:23 -0800270
Linus Torvalds1da177e2005-04-16 15:20:36 -0700271
Davidlohr Buesoab51fba2015-06-29 23:26:02 -0700272/*
273 * Fault injections for futexes.
274 */
275#ifdef CONFIG_FAIL_FUTEX
276
277static struct {
278 struct fault_attr attr;
279
Viresh Kumar621a5f72015-09-26 15:04:07 -0700280 bool ignore_private;
Davidlohr Buesoab51fba2015-06-29 23:26:02 -0700281} fail_futex = {
282 .attr = FAULT_ATTR_INITIALIZER,
Viresh Kumar621a5f72015-09-26 15:04:07 -0700283 .ignore_private = false,
Davidlohr Buesoab51fba2015-06-29 23:26:02 -0700284};
285
286static int __init setup_fail_futex(char *str)
287{
288 return setup_fault_attr(&fail_futex.attr, str);
289}
290__setup("fail_futex=", setup_fail_futex);
291
kbuild test robot5d285a72015-07-21 01:40:45 +0800292static bool should_fail_futex(bool fshared)
Davidlohr Buesoab51fba2015-06-29 23:26:02 -0700293{
294 if (fail_futex.ignore_private && !fshared)
295 return false;
296
297 return should_fail(&fail_futex.attr, 1);
298}
299
300#ifdef CONFIG_FAULT_INJECTION_DEBUG_FS
301
302static int __init fail_futex_debugfs(void)
303{
304 umode_t mode = S_IFREG | S_IRUSR | S_IWUSR;
305 struct dentry *dir;
306
307 dir = fault_create_debugfs_attr("fail_futex", NULL,
308 &fail_futex.attr);
309 if (IS_ERR(dir))
310 return PTR_ERR(dir);
311
Greg Kroah-Hartman0365aeb2019-01-22 16:21:39 +0100312 debugfs_create_bool("ignore-private", mode, dir,
313 &fail_futex.ignore_private);
Davidlohr Buesoab51fba2015-06-29 23:26:02 -0700314 return 0;
315}
316
317late_initcall(fail_futex_debugfs);
318
319#endif /* CONFIG_FAULT_INJECTION_DEBUG_FS */
320
321#else
322static inline bool should_fail_futex(bool fshared)
323{
324 return false;
325}
326#endif /* CONFIG_FAIL_FUTEX */
327
Thomas Gleixnerba31c1a42019-11-06 22:55:36 +0100328#ifdef CONFIG_COMPAT
329static void compat_exit_robust_list(struct task_struct *curr);
330#else
331static inline void compat_exit_robust_list(struct task_struct *curr) { }
332#endif
333
Davidlohr Buesob0c29f72014-01-12 15:31:25 -0800334static inline void futex_get_mm(union futex_key *key)
335{
Vegard Nossumf1f10072017-02-27 14:30:07 -0800336 mmgrab(key->private.mm);
Davidlohr Buesob0c29f72014-01-12 15:31:25 -0800337 /*
338 * Ensure futex_get_mm() implies a full barrier such that
339 * get_futex_key() implies a full barrier. This is relied upon
Davidlohr Bueso8ad7b372016-02-09 11:15:13 -0800340 * as smp_mb(); (B), see the ordering comment above.
Davidlohr Buesob0c29f72014-01-12 15:31:25 -0800341 */
Peter Zijlstra4e857c52014-03-17 18:06:10 +0100342 smp_mb__after_atomic();
Davidlohr Buesob0c29f72014-01-12 15:31:25 -0800343}
344
Linus Torvalds11d46162014-03-20 22:11:17 -0700345/*
346 * Reflects a new waiter being added to the waitqueue.
347 */
348static inline void hb_waiters_inc(struct futex_hash_bucket *hb)
Davidlohr Buesob0c29f72014-01-12 15:31:25 -0800349{
350#ifdef CONFIG_SMP
Linus Torvalds11d46162014-03-20 22:11:17 -0700351 atomic_inc(&hb->waiters);
Davidlohr Buesob0c29f72014-01-12 15:31:25 -0800352 /*
Linus Torvalds11d46162014-03-20 22:11:17 -0700353 * Full barrier (A), see the ordering comment above.
Davidlohr Buesob0c29f72014-01-12 15:31:25 -0800354 */
Peter Zijlstra4e857c52014-03-17 18:06:10 +0100355 smp_mb__after_atomic();
Linus Torvalds11d46162014-03-20 22:11:17 -0700356#endif
357}
Davidlohr Buesob0c29f72014-01-12 15:31:25 -0800358
Linus Torvalds11d46162014-03-20 22:11:17 -0700359/*
360 * Reflects a waiter being removed from the waitqueue by wakeup
361 * paths.
362 */
363static inline void hb_waiters_dec(struct futex_hash_bucket *hb)
364{
365#ifdef CONFIG_SMP
366 atomic_dec(&hb->waiters);
367#endif
368}
369
370static inline int hb_waiters_pending(struct futex_hash_bucket *hb)
371{
372#ifdef CONFIG_SMP
373 return atomic_read(&hb->waiters);
Davidlohr Buesob0c29f72014-01-12 15:31:25 -0800374#else
Linus Torvalds11d46162014-03-20 22:11:17 -0700375 return 1;
Davidlohr Buesob0c29f72014-01-12 15:31:25 -0800376#endif
377}
378
Thomas Gleixnere8b61b32016-06-01 10:43:29 +0200379/**
380 * hash_futex - Return the hash bucket in the global hash
381 * @key: Pointer to the futex key for which the hash is calculated
382 *
383 * We hash on the keys returned from get_futex_key (see below) and return the
384 * corresponding hash bucket in the global hash.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700385 */
386static struct futex_hash_bucket *hash_futex(union futex_key *key)
387{
388 u32 hash = jhash2((u32*)&key->both.word,
389 (sizeof(key->both.word)+sizeof(key->both.ptr))/4,
390 key->both.offset);
Davidlohr Buesoa52b89e2014-01-12 15:31:23 -0800391 return &futex_queues[hash & (futex_hashsize - 1)];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700392}
393
Thomas Gleixnere8b61b32016-06-01 10:43:29 +0200394
395/**
396 * match_futex - Check whether two futex keys are equal
397 * @key1: Pointer to key1
398 * @key2: Pointer to key2
399 *
Linus Torvalds1da177e2005-04-16 15:20:36 -0700400 * Return 1 if two futex_keys are equal, 0 otherwise.
401 */
402static inline int match_futex(union futex_key *key1, union futex_key *key2)
403{
Darren Hart2bc87202009-10-14 10:12:39 -0700404 return (key1 && key2
405 && key1->both.word == key2->both.word
Linus Torvalds1da177e2005-04-16 15:20:36 -0700406 && key1->both.ptr == key2->both.ptr
407 && key1->both.offset == key2->both.offset);
408}
409
Peter Zijlstra38d47c12008-09-26 19:32:20 +0200410/*
411 * Take a reference to the resource addressed by a key.
412 * Can be called while holding spinlocks.
413 *
414 */
415static void get_futex_key_refs(union futex_key *key)
416{
417 if (!key->both.ptr)
418 return;
419
Thomas Gleixner784bdf32016-07-29 16:32:30 +0200420 /*
421 * On MMU less systems futexes are always "private" as there is no per
422 * process address space. We need the smp wmb nevertheless - yes,
423 * arch/blackfin has MMU less SMP ...
424 */
425 if (!IS_ENABLED(CONFIG_MMU)) {
426 smp_mb(); /* explicit smp_mb(); (B) */
427 return;
428 }
429
Peter Zijlstra38d47c12008-09-26 19:32:20 +0200430 switch (key->both.offset & (FUT_OFF_INODE|FUT_OFF_MMSHARED)) {
431 case FUT_OFF_INODE:
Davidlohr Bueso8ad7b372016-02-09 11:15:13 -0800432 ihold(key->shared.inode); /* implies smp_mb(); (B) */
Peter Zijlstra38d47c12008-09-26 19:32:20 +0200433 break;
434 case FUT_OFF_MMSHARED:
Davidlohr Bueso8ad7b372016-02-09 11:15:13 -0800435 futex_get_mm(key); /* implies smp_mb(); (B) */
Peter Zijlstra38d47c12008-09-26 19:32:20 +0200436 break;
Catalin Marinas76835b0e2014-10-17 17:38:49 +0100437 default:
Davidlohr Bueso993b2ff2014-10-23 20:27:00 -0700438 /*
439 * Private futexes do not hold reference on an inode or
440 * mm, therefore the only purpose of calling get_futex_key_refs
441 * is because we need the barrier for the lockless waiter check.
442 */
Davidlohr Bueso8ad7b372016-02-09 11:15:13 -0800443 smp_mb(); /* explicit smp_mb(); (B) */
Peter Zijlstra38d47c12008-09-26 19:32:20 +0200444 }
445}
446
447/*
448 * Drop a reference to the resource addressed by a key.
Davidlohr Bueso993b2ff2014-10-23 20:27:00 -0700449 * The hash bucket spinlock must not be held. This is
450 * a no-op for private futexes, see comment in the get
451 * counterpart.
Peter Zijlstra38d47c12008-09-26 19:32:20 +0200452 */
453static void drop_futex_key_refs(union futex_key *key)
454{
Darren Hart90621c42008-12-29 19:43:21 -0800455 if (!key->both.ptr) {
456 /* If we're here then we tried to put a key we failed to get */
457 WARN_ON_ONCE(1);
Peter Zijlstra38d47c12008-09-26 19:32:20 +0200458 return;
Darren Hart90621c42008-12-29 19:43:21 -0800459 }
Peter Zijlstra38d47c12008-09-26 19:32:20 +0200460
Thomas Gleixner784bdf32016-07-29 16:32:30 +0200461 if (!IS_ENABLED(CONFIG_MMU))
462 return;
463
Peter Zijlstra38d47c12008-09-26 19:32:20 +0200464 switch (key->both.offset & (FUT_OFF_INODE|FUT_OFF_MMSHARED)) {
465 case FUT_OFF_INODE:
466 iput(key->shared.inode);
467 break;
468 case FUT_OFF_MMSHARED:
469 mmdrop(key->private.mm);
470 break;
471 }
472}
473
Linus Torvalds96d4f262019-01-03 18:57:57 -0800474enum futex_access {
475 FUTEX_READ,
476 FUTEX_WRITE
477};
478
Eric Dumazet34f01cc2007-05-09 02:35:04 -0700479/**
Waiman Long5ca584d2019-05-28 12:03:45 -0400480 * futex_setup_timer - set up the sleeping hrtimer.
481 * @time: ptr to the given timeout value
482 * @timeout: the hrtimer_sleeper structure to be set up
483 * @flags: futex flags
484 * @range_ns: optional range in ns
485 *
486 * Return: Initialized hrtimer_sleeper structure or NULL if no timeout
487 * value given
488 */
489static inline struct hrtimer_sleeper *
490futex_setup_timer(ktime_t *time, struct hrtimer_sleeper *timeout,
491 int flags, u64 range_ns)
492{
493 if (!time)
494 return NULL;
495
Sebastian Andrzej Siewiordbc16252019-07-26 20:30:50 +0200496 hrtimer_init_sleeper_on_stack(timeout, (flags & FLAGS_CLOCKRT) ?
497 CLOCK_REALTIME : CLOCK_MONOTONIC,
498 HRTIMER_MODE_ABS);
Waiman Long5ca584d2019-05-28 12:03:45 -0400499 /*
500 * If range_ns is 0, calling hrtimer_set_expires_range_ns() is
501 * effectively the same as calling hrtimer_set_expires().
502 */
503 hrtimer_set_expires_range_ns(&timeout->timer, *time, range_ns);
504
505 return timeout;
506}
507
508/**
Darren Hartd96ee562009-09-21 22:30:22 -0700509 * get_futex_key() - Get parameters which are the keys for a futex
510 * @uaddr: virtual address of the futex
511 * @fshared: 0 for a PROCESS_PRIVATE futex, 1 for PROCESS_SHARED
512 * @key: address where result is stored.
Linus Torvalds96d4f262019-01-03 18:57:57 -0800513 * @rw: mapping needs to be read/write (values: FUTEX_READ,
514 * FUTEX_WRITE)
Eric Dumazet34f01cc2007-05-09 02:35:04 -0700515 *
Randy Dunlap6c23cbb2013-03-05 10:00:24 -0800516 * Return: a negative error code or 0
517 *
Mauro Carvalho Chehab7b4ff1a2017-05-11 10:17:45 -0300518 * The key words are stored in @key on success.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700519 *
Al Viro6131ffa2013-02-27 16:59:05 -0500520 * For shared mappings, it's (page->index, file_inode(vma->vm_file),
Linus Torvalds1da177e2005-04-16 15:20:36 -0700521 * offset_within_page). For private mappings, it's (uaddr, current->mm).
522 * We can usually work out the index without swapping in the page.
523 *
Darren Hartb2d09942009-03-12 00:55:37 -0700524 * lock_page() might sleep, the caller should not hold a spinlock.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700525 */
Thomas Gleixner64d13042009-05-18 21:20:10 +0200526static int
Linus Torvalds96d4f262019-01-03 18:57:57 -0800527get_futex_key(u32 __user *uaddr, int fshared, union futex_key *key, enum futex_access rw)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700528{
Ingo Molnare2970f22006-06-27 02:54:47 -0700529 unsigned long address = (unsigned long)uaddr;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700530 struct mm_struct *mm = current->mm;
Mel Gorman077fa7a2016-06-08 14:25:22 +0100531 struct page *page, *tail;
Kirill A. Shutemov14d27ab2016-01-15 16:53:00 -0800532 struct address_space *mapping;
Shawn Bohrer9ea71502011-06-30 11:21:32 -0500533 int err, ro = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700534
535 /*
536 * The futex address must be "naturally" aligned.
537 */
Ingo Molnare2970f22006-06-27 02:54:47 -0700538 key->both.offset = address % PAGE_SIZE;
Eric Dumazet34f01cc2007-05-09 02:35:04 -0700539 if (unlikely((address % sizeof(u32)) != 0))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700540 return -EINVAL;
Ingo Molnare2970f22006-06-27 02:54:47 -0700541 address -= key->both.offset;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700542
Linus Torvalds96d4f262019-01-03 18:57:57 -0800543 if (unlikely(!access_ok(uaddr, sizeof(u32))))
Linus Torvalds5cdec2d2013-12-12 09:53:51 -0800544 return -EFAULT;
545
Davidlohr Buesoab51fba2015-06-29 23:26:02 -0700546 if (unlikely(should_fail_futex(fshared)))
547 return -EFAULT;
548
Linus Torvalds1da177e2005-04-16 15:20:36 -0700549 /*
Eric Dumazet34f01cc2007-05-09 02:35:04 -0700550 * PROCESS_PRIVATE futexes are fast.
551 * As the mm cannot disappear under us and the 'key' only needs
552 * virtual address, we dont even have to find the underlying vma.
553 * Note : We do have to check 'uaddr' is a valid user address,
554 * but access_ok() should be faster than find_vma()
555 */
556 if (!fshared) {
Eric Dumazet34f01cc2007-05-09 02:35:04 -0700557 key->private.mm = mm;
558 key->private.address = address;
Davidlohr Bueso8ad7b372016-02-09 11:15:13 -0800559 get_futex_key_refs(key); /* implies smp_mb(); (B) */
Eric Dumazet34f01cc2007-05-09 02:35:04 -0700560 return 0;
561 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700562
Peter Zijlstra38d47c12008-09-26 19:32:20 +0200563again:
Davidlohr Buesoab51fba2015-06-29 23:26:02 -0700564 /* Ignore any VERIFY_READ mapping (futex common case) */
565 if (unlikely(should_fail_futex(fshared)))
566 return -EFAULT;
567
Ira Weiny73b01402019-05-13 17:17:11 -0700568 err = get_user_pages_fast(address, 1, FOLL_WRITE, &page);
Shawn Bohrer9ea71502011-06-30 11:21:32 -0500569 /*
570 * If write access is not required (eg. FUTEX_WAIT), try
571 * and get read-only access.
572 */
Linus Torvalds96d4f262019-01-03 18:57:57 -0800573 if (err == -EFAULT && rw == FUTEX_READ) {
Shawn Bohrer9ea71502011-06-30 11:21:32 -0500574 err = get_user_pages_fast(address, 1, 0, &page);
575 ro = 1;
576 }
Peter Zijlstra38d47c12008-09-26 19:32:20 +0200577 if (err < 0)
578 return err;
Shawn Bohrer9ea71502011-06-30 11:21:32 -0500579 else
580 err = 0;
Peter Zijlstra38d47c12008-09-26 19:32:20 +0200581
Mel Gorman65d8fc72016-02-09 11:15:14 -0800582 /*
583 * The treatment of mapping from this point on is critical. The page
584 * lock protects many things but in this context the page lock
585 * stabilizes mapping, prevents inode freeing in the shared
586 * file-backed region case and guards against movement to swap cache.
587 *
588 * Strictly speaking the page lock is not needed in all cases being
589 * considered here and page lock forces unnecessarily serialization
590 * From this point on, mapping will be re-verified if necessary and
591 * page lock will be acquired only if it is unavoidable
Mel Gorman077fa7a2016-06-08 14:25:22 +0100592 *
593 * Mapping checks require the head page for any compound page so the
594 * head page and mapping is looked up now. For anonymous pages, it
595 * does not matter if the page splits in the future as the key is
596 * based on the address. For filesystem-backed pages, the tail is
597 * required as the index of the page determines the key. For
598 * base pages, there is no tail page and tail == page.
Mel Gorman65d8fc72016-02-09 11:15:14 -0800599 */
Mel Gorman077fa7a2016-06-08 14:25:22 +0100600 tail = page;
Mel Gorman65d8fc72016-02-09 11:15:14 -0800601 page = compound_head(page);
602 mapping = READ_ONCE(page->mapping);
603
Hugh Dickinse6780f72011-12-31 11:44:01 -0800604 /*
Kirill A. Shutemov14d27ab2016-01-15 16:53:00 -0800605 * If page->mapping is NULL, then it cannot be a PageAnon
Hugh Dickinse6780f72011-12-31 11:44:01 -0800606 * page; but it might be the ZERO_PAGE or in the gate area or
607 * in a special mapping (all cases which we are happy to fail);
608 * or it may have been a good file page when get_user_pages_fast
609 * found it, but truncated or holepunched or subjected to
610 * invalidate_complete_page2 before we got the page lock (also
611 * cases which we are happy to fail). And we hold a reference,
612 * so refcount care in invalidate_complete_page's remove_mapping
613 * prevents drop_caches from setting mapping to NULL beneath us.
614 *
615 * The case we do have to guard against is when memory pressure made
616 * shmem_writepage move it from filecache to swapcache beneath us:
Kirill A. Shutemov14d27ab2016-01-15 16:53:00 -0800617 * an unlikely race, but we do need to retry for page->mapping.
Hugh Dickinse6780f72011-12-31 11:44:01 -0800618 */
Mel Gorman65d8fc72016-02-09 11:15:14 -0800619 if (unlikely(!mapping)) {
620 int shmem_swizzled;
621
622 /*
623 * Page lock is required to identify which special case above
624 * applies. If this is really a shmem page then the page lock
625 * will prevent unexpected transitions.
626 */
627 lock_page(page);
628 shmem_swizzled = PageSwapCache(page) || page->mapping;
Kirill A. Shutemov14d27ab2016-01-15 16:53:00 -0800629 unlock_page(page);
630 put_page(page);
Mel Gorman65d8fc72016-02-09 11:15:14 -0800631
Hugh Dickinse6780f72011-12-31 11:44:01 -0800632 if (shmem_swizzled)
633 goto again;
Mel Gorman65d8fc72016-02-09 11:15:14 -0800634
Hugh Dickinse6780f72011-12-31 11:44:01 -0800635 return -EFAULT;
Peter Zijlstra38d47c12008-09-26 19:32:20 +0200636 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700637
638 /*
639 * Private mappings are handled in a simple way.
640 *
Mel Gorman65d8fc72016-02-09 11:15:14 -0800641 * If the futex key is stored on an anonymous page, then the associated
642 * object is the mm which is implicitly pinned by the calling process.
643 *
Linus Torvalds1da177e2005-04-16 15:20:36 -0700644 * NOTE: When userspace waits on a MAP_SHARED mapping, even if
645 * it's a read-only handle, it's expected that futexes attach to
Peter Zijlstra38d47c12008-09-26 19:32:20 +0200646 * the object not the particular process.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700647 */
Kirill A. Shutemov14d27ab2016-01-15 16:53:00 -0800648 if (PageAnon(page)) {
Shawn Bohrer9ea71502011-06-30 11:21:32 -0500649 /*
650 * A RO anonymous page will never change and thus doesn't make
651 * sense for futex operations.
652 */
Davidlohr Buesoab51fba2015-06-29 23:26:02 -0700653 if (unlikely(should_fail_futex(fshared)) || ro) {
Shawn Bohrer9ea71502011-06-30 11:21:32 -0500654 err = -EFAULT;
655 goto out;
656 }
657
Peter Zijlstra38d47c12008-09-26 19:32:20 +0200658 key->both.offset |= FUT_OFF_MMSHARED; /* ref taken on mm */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700659 key->private.mm = mm;
Ingo Molnare2970f22006-06-27 02:54:47 -0700660 key->private.address = address;
Mel Gorman65d8fc72016-02-09 11:15:14 -0800661
662 get_futex_key_refs(key); /* implies smp_mb(); (B) */
663
Peter Zijlstra38d47c12008-09-26 19:32:20 +0200664 } else {
Mel Gorman65d8fc72016-02-09 11:15:14 -0800665 struct inode *inode;
666
667 /*
668 * The associated futex object in this case is the inode and
669 * the page->mapping must be traversed. Ordinarily this should
670 * be stabilised under page lock but it's not strictly
671 * necessary in this case as we just want to pin the inode, not
672 * update the radix tree or anything like that.
673 *
674 * The RCU read lock is taken as the inode is finally freed
675 * under RCU. If the mapping still matches expectations then the
676 * mapping->host can be safely accessed as being a valid inode.
677 */
678 rcu_read_lock();
679
680 if (READ_ONCE(page->mapping) != mapping) {
681 rcu_read_unlock();
682 put_page(page);
683
684 goto again;
685 }
686
687 inode = READ_ONCE(mapping->host);
688 if (!inode) {
689 rcu_read_unlock();
690 put_page(page);
691
692 goto again;
693 }
694
695 /*
696 * Take a reference unless it is about to be freed. Previously
697 * this reference was taken by ihold under the page lock
698 * pinning the inode in place so i_lock was unnecessary. The
699 * only way for this check to fail is if the inode was
Mel Gorman48fb6f42017-08-09 08:27:11 +0100700 * truncated in parallel which is almost certainly an
701 * application bug. In such a case, just retry.
Mel Gorman65d8fc72016-02-09 11:15:14 -0800702 *
703 * We are not calling into get_futex_key_refs() in file-backed
704 * cases, therefore a successful atomic_inc return below will
705 * guarantee that get_futex_key() will still imply smp_mb(); (B).
706 */
Mel Gorman48fb6f42017-08-09 08:27:11 +0100707 if (!atomic_inc_not_zero(&inode->i_count)) {
Mel Gorman65d8fc72016-02-09 11:15:14 -0800708 rcu_read_unlock();
709 put_page(page);
710
711 goto again;
712 }
713
714 /* Should be impossible but lets be paranoid for now */
715 if (WARN_ON_ONCE(inode->i_mapping != mapping)) {
716 err = -EFAULT;
717 rcu_read_unlock();
718 iput(inode);
719
720 goto out;
721 }
722
Peter Zijlstra38d47c12008-09-26 19:32:20 +0200723 key->both.offset |= FUT_OFF_INODE; /* inode-based key */
Mel Gorman65d8fc72016-02-09 11:15:14 -0800724 key->shared.inode = inode;
Mel Gorman077fa7a2016-06-08 14:25:22 +0100725 key->shared.pgoff = basepage_index(tail);
Mel Gorman65d8fc72016-02-09 11:15:14 -0800726 rcu_read_unlock();
Linus Torvalds1da177e2005-04-16 15:20:36 -0700727 }
728
Shawn Bohrer9ea71502011-06-30 11:21:32 -0500729out:
Kirill A. Shutemov14d27ab2016-01-15 16:53:00 -0800730 put_page(page);
Shawn Bohrer9ea71502011-06-30 11:21:32 -0500731 return err;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700732}
733
Thomas Gleixnerae791a22010-11-10 13:30:36 +0100734static inline void put_futex_key(union futex_key *key)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700735{
Peter Zijlstra38d47c12008-09-26 19:32:20 +0200736 drop_futex_key_refs(key);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700737}
738
Darren Hartd96ee562009-09-21 22:30:22 -0700739/**
740 * fault_in_user_writeable() - Fault in user address and verify RW access
Thomas Gleixnerd0725992009-06-11 23:15:43 +0200741 * @uaddr: pointer to faulting user space address
742 *
743 * Slow path to fixup the fault we just took in the atomic write
744 * access to @uaddr.
745 *
Randy Dunlapfb62db22010-10-13 11:02:34 -0700746 * We have no generic implementation of a non-destructive write to the
Thomas Gleixnerd0725992009-06-11 23:15:43 +0200747 * user address. We know that we faulted in the atomic pagefault
748 * disabled section so we can as well avoid the #PF overhead by
749 * calling get_user_pages() right away.
750 */
751static int fault_in_user_writeable(u32 __user *uaddr)
752{
Andi Kleen722d0172009-12-08 13:19:42 +0100753 struct mm_struct *mm = current->mm;
754 int ret;
755
756 down_read(&mm->mmap_sem);
Benjamin Herrenschmidt2efaca92011-07-25 17:12:32 -0700757 ret = fixup_user_fault(current, mm, (unsigned long)uaddr,
Dominik Dingel4a9e1cd2016-01-15 16:57:04 -0800758 FAULT_FLAG_WRITE, NULL);
Andi Kleen722d0172009-12-08 13:19:42 +0100759 up_read(&mm->mmap_sem);
760
Thomas Gleixnerd0725992009-06-11 23:15:43 +0200761 return ret < 0 ? ret : 0;
762}
763
Darren Hart4b1c4862009-04-03 13:39:42 -0700764/**
765 * futex_top_waiter() - Return the highest priority waiter on a futex
Darren Hartd96ee562009-09-21 22:30:22 -0700766 * @hb: the hash bucket the futex_q's reside in
767 * @key: the futex key (to distinguish it from other futex futex_q's)
Darren Hart4b1c4862009-04-03 13:39:42 -0700768 *
769 * Must be called with the hb lock held.
770 */
771static struct futex_q *futex_top_waiter(struct futex_hash_bucket *hb,
772 union futex_key *key)
773{
774 struct futex_q *this;
775
776 plist_for_each_entry(this, &hb->chain, list) {
777 if (match_futex(&this->key, key))
778 return this;
779 }
780 return NULL;
781}
782
Michel Lespinasse37a9d912011-03-10 18:48:51 -0800783static int cmpxchg_futex_value_locked(u32 *curval, u32 __user *uaddr,
784 u32 uval, u32 newval)
Thomas Gleixner36cf3b52007-07-15 23:41:20 -0700785{
Michel Lespinasse37a9d912011-03-10 18:48:51 -0800786 int ret;
Thomas Gleixner36cf3b52007-07-15 23:41:20 -0700787
788 pagefault_disable();
Michel Lespinasse37a9d912011-03-10 18:48:51 -0800789 ret = futex_atomic_cmpxchg_inatomic(curval, uaddr, uval, newval);
Thomas Gleixner36cf3b52007-07-15 23:41:20 -0700790 pagefault_enable();
791
Michel Lespinasse37a9d912011-03-10 18:48:51 -0800792 return ret;
Thomas Gleixner36cf3b52007-07-15 23:41:20 -0700793}
794
795static int get_futex_value_locked(u32 *dest, u32 __user *from)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700796{
797 int ret;
798
Peter Zijlstraa8663742006-12-06 20:32:20 -0800799 pagefault_disable();
Linus Torvaldsbd28b142016-05-22 17:21:27 -0700800 ret = __get_user(*dest, from);
Peter Zijlstraa8663742006-12-06 20:32:20 -0800801 pagefault_enable();
Linus Torvalds1da177e2005-04-16 15:20:36 -0700802
803 return ret ? -EFAULT : 0;
804}
805
Ingo Molnarc87e2832006-06-27 02:54:58 -0700806
807/*
808 * PI code:
809 */
810static int refill_pi_state_cache(void)
811{
812 struct futex_pi_state *pi_state;
813
814 if (likely(current->pi_state_cache))
815 return 0;
816
Burman Yan4668edc2006-12-06 20:38:51 -0800817 pi_state = kzalloc(sizeof(*pi_state), GFP_KERNEL);
Ingo Molnarc87e2832006-06-27 02:54:58 -0700818
819 if (!pi_state)
820 return -ENOMEM;
821
Ingo Molnarc87e2832006-06-27 02:54:58 -0700822 INIT_LIST_HEAD(&pi_state->list);
823 /* pi_mutex gets initialized later */
824 pi_state->owner = NULL;
Elena Reshetova49262de2019-02-05 14:24:27 +0200825 refcount_set(&pi_state->refcount, 1);
Peter Zijlstra38d47c12008-09-26 19:32:20 +0200826 pi_state->key = FUTEX_KEY_INIT;
Ingo Molnarc87e2832006-06-27 02:54:58 -0700827
828 current->pi_state_cache = pi_state;
829
830 return 0;
831}
832
Peter Zijlstrabf92cf32017-03-22 11:35:53 +0100833static struct futex_pi_state *alloc_pi_state(void)
Ingo Molnarc87e2832006-06-27 02:54:58 -0700834{
835 struct futex_pi_state *pi_state = current->pi_state_cache;
836
837 WARN_ON(!pi_state);
838 current->pi_state_cache = NULL;
839
840 return pi_state;
841}
842
Peter Zijlstrabf92cf32017-03-22 11:35:53 +0100843static void get_pi_state(struct futex_pi_state *pi_state)
844{
Elena Reshetova49262de2019-02-05 14:24:27 +0200845 WARN_ON_ONCE(!refcount_inc_not_zero(&pi_state->refcount));
Peter Zijlstrabf92cf32017-03-22 11:35:53 +0100846}
847
Brian Silverman30a6b802014-10-25 20:20:37 -0400848/*
Thomas Gleixner29e9ee52015-12-19 20:07:39 +0000849 * Drops a reference to the pi_state object and frees or caches it
850 * when the last reference is gone.
Brian Silverman30a6b802014-10-25 20:20:37 -0400851 */
Thomas Gleixner29e9ee52015-12-19 20:07:39 +0000852static void put_pi_state(struct futex_pi_state *pi_state)
Ingo Molnarc87e2832006-06-27 02:54:58 -0700853{
Brian Silverman30a6b802014-10-25 20:20:37 -0400854 if (!pi_state)
855 return;
856
Elena Reshetova49262de2019-02-05 14:24:27 +0200857 if (!refcount_dec_and_test(&pi_state->refcount))
Ingo Molnarc87e2832006-06-27 02:54:58 -0700858 return;
859
860 /*
861 * If pi_state->owner is NULL, the owner is most probably dying
862 * and has cleaned up the pi_state already
863 */
864 if (pi_state->owner) {
Peter Zijlstrac74aef22017-09-22 17:48:06 +0200865 struct task_struct *owner;
Ingo Molnarc87e2832006-06-27 02:54:58 -0700866
Peter Zijlstrac74aef22017-09-22 17:48:06 +0200867 raw_spin_lock_irq(&pi_state->pi_mutex.wait_lock);
868 owner = pi_state->owner;
869 if (owner) {
870 raw_spin_lock(&owner->pi_lock);
871 list_del_init(&pi_state->list);
872 raw_spin_unlock(&owner->pi_lock);
873 }
874 rt_mutex_proxy_unlock(&pi_state->pi_mutex, owner);
875 raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
Ingo Molnarc87e2832006-06-27 02:54:58 -0700876 }
877
Peter Zijlstrac74aef22017-09-22 17:48:06 +0200878 if (current->pi_state_cache) {
Ingo Molnarc87e2832006-06-27 02:54:58 -0700879 kfree(pi_state);
Peter Zijlstrac74aef22017-09-22 17:48:06 +0200880 } else {
Ingo Molnarc87e2832006-06-27 02:54:58 -0700881 /*
882 * pi_state->list is already empty.
883 * clear pi_state->owner.
884 * refcount is at 0 - put it back to 1.
885 */
886 pi_state->owner = NULL;
Elena Reshetova49262de2019-02-05 14:24:27 +0200887 refcount_set(&pi_state->refcount, 1);
Ingo Molnarc87e2832006-06-27 02:54:58 -0700888 current->pi_state_cache = pi_state;
889 }
890}
891
Nicolas Pitrebc2eecd2017-08-01 00:31:32 -0400892#ifdef CONFIG_FUTEX_PI
893
Ingo Molnarc87e2832006-06-27 02:54:58 -0700894/*
895 * This task is holding PI mutexes at exit time => bad.
896 * Kernel cleans up PI-state, but userspace is likely hosed.
897 * (Robust-futex cleanup is separate and might save the day for userspace.)
898 */
Thomas Gleixnerba31c1a42019-11-06 22:55:36 +0100899static void exit_pi_state_list(struct task_struct *curr)
Ingo Molnarc87e2832006-06-27 02:54:58 -0700900{
Ingo Molnarc87e2832006-06-27 02:54:58 -0700901 struct list_head *next, *head = &curr->pi_state_list;
902 struct futex_pi_state *pi_state;
Ingo Molnar627371d2006-07-29 05:16:20 +0200903 struct futex_hash_bucket *hb;
Peter Zijlstra38d47c12008-09-26 19:32:20 +0200904 union futex_key key = FUTEX_KEY_INIT;
Ingo Molnarc87e2832006-06-27 02:54:58 -0700905
Thomas Gleixnera0c1e902008-02-23 15:23:57 -0800906 if (!futex_cmpxchg_enabled)
907 return;
Ingo Molnarc87e2832006-06-27 02:54:58 -0700908 /*
909 * We are a ZOMBIE and nobody can enqueue itself on
910 * pi_state_list anymore, but we have to be careful
Ingo Molnar627371d2006-07-29 05:16:20 +0200911 * versus waiters unqueueing themselves:
Ingo Molnarc87e2832006-06-27 02:54:58 -0700912 */
Thomas Gleixner1d615482009-11-17 14:54:03 +0100913 raw_spin_lock_irq(&curr->pi_lock);
Ingo Molnarc87e2832006-06-27 02:54:58 -0700914 while (!list_empty(head)) {
Ingo Molnarc87e2832006-06-27 02:54:58 -0700915 next = head->next;
916 pi_state = list_entry(next, struct futex_pi_state, list);
917 key = pi_state->key;
Ingo Molnar627371d2006-07-29 05:16:20 +0200918 hb = hash_futex(&key);
Peter Zijlstra153fbd12017-10-31 11:18:53 +0100919
920 /*
921 * We can race against put_pi_state() removing itself from the
922 * list (a waiter going away). put_pi_state() will first
923 * decrement the reference count and then modify the list, so
924 * its possible to see the list entry but fail this reference
925 * acquire.
926 *
927 * In that case; drop the locks to let put_pi_state() make
928 * progress and retry the loop.
929 */
Elena Reshetova49262de2019-02-05 14:24:27 +0200930 if (!refcount_inc_not_zero(&pi_state->refcount)) {
Peter Zijlstra153fbd12017-10-31 11:18:53 +0100931 raw_spin_unlock_irq(&curr->pi_lock);
932 cpu_relax();
933 raw_spin_lock_irq(&curr->pi_lock);
934 continue;
935 }
Thomas Gleixner1d615482009-11-17 14:54:03 +0100936 raw_spin_unlock_irq(&curr->pi_lock);
Ingo Molnarc87e2832006-06-27 02:54:58 -0700937
Ingo Molnarc87e2832006-06-27 02:54:58 -0700938 spin_lock(&hb->lock);
Peter Zijlstrac74aef22017-09-22 17:48:06 +0200939 raw_spin_lock_irq(&pi_state->pi_mutex.wait_lock);
940 raw_spin_lock(&curr->pi_lock);
Ingo Molnar627371d2006-07-29 05:16:20 +0200941 /*
942 * We dropped the pi-lock, so re-check whether this
943 * task still owns the PI-state:
944 */
Ingo Molnarc87e2832006-06-27 02:54:58 -0700945 if (head->next != next) {
Peter Zijlstra153fbd12017-10-31 11:18:53 +0100946 /* retain curr->pi_lock for the loop invariant */
Peter Zijlstrac74aef22017-09-22 17:48:06 +0200947 raw_spin_unlock(&pi_state->pi_mutex.wait_lock);
Ingo Molnarc87e2832006-06-27 02:54:58 -0700948 spin_unlock(&hb->lock);
Peter Zijlstra153fbd12017-10-31 11:18:53 +0100949 put_pi_state(pi_state);
Ingo Molnarc87e2832006-06-27 02:54:58 -0700950 continue;
951 }
952
Ingo Molnarc87e2832006-06-27 02:54:58 -0700953 WARN_ON(pi_state->owner != curr);
Ingo Molnar627371d2006-07-29 05:16:20 +0200954 WARN_ON(list_empty(&pi_state->list));
955 list_del_init(&pi_state->list);
Ingo Molnarc87e2832006-06-27 02:54:58 -0700956 pi_state->owner = NULL;
Ingo Molnarc87e2832006-06-27 02:54:58 -0700957
Peter Zijlstra153fbd12017-10-31 11:18:53 +0100958 raw_spin_unlock(&curr->pi_lock);
Peter Zijlstrac74aef22017-09-22 17:48:06 +0200959 raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
Ingo Molnarc87e2832006-06-27 02:54:58 -0700960 spin_unlock(&hb->lock);
961
Peter Zijlstra16ffa122017-03-22 11:35:55 +0100962 rt_mutex_futex_unlock(&pi_state->pi_mutex);
963 put_pi_state(pi_state);
964
Thomas Gleixner1d615482009-11-17 14:54:03 +0100965 raw_spin_lock_irq(&curr->pi_lock);
Ingo Molnarc87e2832006-06-27 02:54:58 -0700966 }
Thomas Gleixner1d615482009-11-17 14:54:03 +0100967 raw_spin_unlock_irq(&curr->pi_lock);
Ingo Molnarc87e2832006-06-27 02:54:58 -0700968}
Thomas Gleixnerba31c1a42019-11-06 22:55:36 +0100969#else
970static inline void exit_pi_state_list(struct task_struct *curr) { }
Nicolas Pitrebc2eecd2017-08-01 00:31:32 -0400971#endif
972
Thomas Gleixner54a217882014-06-03 12:27:08 +0000973/*
974 * We need to check the following states:
975 *
976 * Waiter | pi_state | pi->owner | uTID | uODIED | ?
977 *
978 * [1] NULL | --- | --- | 0 | 0/1 | Valid
979 * [2] NULL | --- | --- | >0 | 0/1 | Valid
980 *
981 * [3] Found | NULL | -- | Any | 0/1 | Invalid
982 *
983 * [4] Found | Found | NULL | 0 | 1 | Valid
984 * [5] Found | Found | NULL | >0 | 1 | Invalid
985 *
986 * [6] Found | Found | task | 0 | 1 | Valid
987 *
988 * [7] Found | Found | NULL | Any | 0 | Invalid
989 *
990 * [8] Found | Found | task | ==taskTID | 0/1 | Valid
991 * [9] Found | Found | task | 0 | 0 | Invalid
992 * [10] Found | Found | task | !=taskTID | 0/1 | Invalid
993 *
994 * [1] Indicates that the kernel can acquire the futex atomically. We
995 * came came here due to a stale FUTEX_WAITERS/FUTEX_OWNER_DIED bit.
996 *
997 * [2] Valid, if TID does not belong to a kernel thread. If no matching
998 * thread is found then it indicates that the owner TID has died.
999 *
1000 * [3] Invalid. The waiter is queued on a non PI futex
1001 *
1002 * [4] Valid state after exit_robust_list(), which sets the user space
1003 * value to FUTEX_WAITERS | FUTEX_OWNER_DIED.
1004 *
1005 * [5] The user space value got manipulated between exit_robust_list()
1006 * and exit_pi_state_list()
1007 *
1008 * [6] Valid state after exit_pi_state_list() which sets the new owner in
1009 * the pi_state but cannot access the user space value.
1010 *
1011 * [7] pi_state->owner can only be NULL when the OWNER_DIED bit is set.
1012 *
1013 * [8] Owner and user space value match
1014 *
1015 * [9] There is no transient state which sets the user space TID to 0
1016 * except exit_robust_list(), but this is indicated by the
1017 * FUTEX_OWNER_DIED bit. See [4]
1018 *
1019 * [10] There is no transient state which leaves owner and user space
1020 * TID out of sync.
Peter Zijlstra734009e2017-03-22 11:35:52 +01001021 *
1022 *
1023 * Serialization and lifetime rules:
1024 *
1025 * hb->lock:
1026 *
1027 * hb -> futex_q, relation
1028 * futex_q -> pi_state, relation
1029 *
1030 * (cannot be raw because hb can contain arbitrary amount
1031 * of futex_q's)
1032 *
1033 * pi_mutex->wait_lock:
1034 *
1035 * {uval, pi_state}
1036 *
1037 * (and pi_mutex 'obviously')
1038 *
1039 * p->pi_lock:
1040 *
1041 * p->pi_state_list -> pi_state->list, relation
1042 *
1043 * pi_state->refcount:
1044 *
1045 * pi_state lifetime
1046 *
1047 *
1048 * Lock order:
1049 *
1050 * hb->lock
1051 * pi_mutex->wait_lock
1052 * p->pi_lock
1053 *
Thomas Gleixner54a217882014-06-03 12:27:08 +00001054 */
Thomas Gleixnere60cbc52014-06-11 20:45:39 +00001055
1056/*
1057 * Validate that the existing waiter has a pi_state and sanity check
1058 * the pi_state against the user space value. If correct, attach to
1059 * it.
1060 */
Peter Zijlstra734009e2017-03-22 11:35:52 +01001061static int attach_to_pi_state(u32 __user *uaddr, u32 uval,
1062 struct futex_pi_state *pi_state,
Thomas Gleixnere60cbc52014-06-11 20:45:39 +00001063 struct futex_pi_state **ps)
1064{
1065 pid_t pid = uval & FUTEX_TID_MASK;
Peter Zijlstra94ffac52017-04-07 09:04:07 +02001066 u32 uval2;
1067 int ret;
Thomas Gleixnere60cbc52014-06-11 20:45:39 +00001068
1069 /*
1070 * Userspace might have messed up non-PI and PI futexes [3]
1071 */
1072 if (unlikely(!pi_state))
1073 return -EINVAL;
1074
Peter Zijlstra734009e2017-03-22 11:35:52 +01001075 /*
1076 * We get here with hb->lock held, and having found a
1077 * futex_top_waiter(). This means that futex_lock_pi() of said futex_q
1078 * has dropped the hb->lock in between queue_me() and unqueue_me_pi(),
1079 * which in turn means that futex_lock_pi() still has a reference on
1080 * our pi_state.
Peter Zijlstra16ffa122017-03-22 11:35:55 +01001081 *
1082 * The waiter holding a reference on @pi_state also protects against
1083 * the unlocked put_pi_state() in futex_unlock_pi(), futex_lock_pi()
1084 * and futex_wait_requeue_pi() as it cannot go to 0 and consequently
1085 * free pi_state before we can take a reference ourselves.
Peter Zijlstra734009e2017-03-22 11:35:52 +01001086 */
Elena Reshetova49262de2019-02-05 14:24:27 +02001087 WARN_ON(!refcount_read(&pi_state->refcount));
Thomas Gleixnere60cbc52014-06-11 20:45:39 +00001088
1089 /*
Peter Zijlstra734009e2017-03-22 11:35:52 +01001090 * Now that we have a pi_state, we can acquire wait_lock
1091 * and do the state validation.
1092 */
1093 raw_spin_lock_irq(&pi_state->pi_mutex.wait_lock);
1094
1095 /*
1096 * Since {uval, pi_state} is serialized by wait_lock, and our current
1097 * uval was read without holding it, it can have changed. Verify it
1098 * still is what we expect it to be, otherwise retry the entire
1099 * operation.
1100 */
1101 if (get_futex_value_locked(&uval2, uaddr))
1102 goto out_efault;
1103
1104 if (uval != uval2)
1105 goto out_eagain;
1106
1107 /*
Thomas Gleixnere60cbc52014-06-11 20:45:39 +00001108 * Handle the owner died case:
1109 */
1110 if (uval & FUTEX_OWNER_DIED) {
1111 /*
1112 * exit_pi_state_list sets owner to NULL and wakes the
1113 * topmost waiter. The task which acquires the
1114 * pi_state->rt_mutex will fixup owner.
1115 */
1116 if (!pi_state->owner) {
1117 /*
1118 * No pi state owner, but the user space TID
1119 * is not 0. Inconsistent state. [5]
1120 */
1121 if (pid)
Peter Zijlstra734009e2017-03-22 11:35:52 +01001122 goto out_einval;
Thomas Gleixnere60cbc52014-06-11 20:45:39 +00001123 /*
1124 * Take a ref on the state and return success. [4]
1125 */
Peter Zijlstra734009e2017-03-22 11:35:52 +01001126 goto out_attach;
Thomas Gleixnere60cbc52014-06-11 20:45:39 +00001127 }
1128
1129 /*
1130 * If TID is 0, then either the dying owner has not
1131 * yet executed exit_pi_state_list() or some waiter
1132 * acquired the rtmutex in the pi state, but did not
1133 * yet fixup the TID in user space.
1134 *
1135 * Take a ref on the state and return success. [6]
1136 */
1137 if (!pid)
Peter Zijlstra734009e2017-03-22 11:35:52 +01001138 goto out_attach;
Thomas Gleixnere60cbc52014-06-11 20:45:39 +00001139 } else {
1140 /*
1141 * If the owner died bit is not set, then the pi_state
1142 * must have an owner. [7]
1143 */
1144 if (!pi_state->owner)
Peter Zijlstra734009e2017-03-22 11:35:52 +01001145 goto out_einval;
Thomas Gleixnere60cbc52014-06-11 20:45:39 +00001146 }
1147
1148 /*
1149 * Bail out if user space manipulated the futex value. If pi
1150 * state exists then the owner TID must be the same as the
1151 * user space TID. [9/10]
1152 */
1153 if (pid != task_pid_vnr(pi_state->owner))
Peter Zijlstra734009e2017-03-22 11:35:52 +01001154 goto out_einval;
1155
1156out_attach:
Peter Zijlstrabf92cf32017-03-22 11:35:53 +01001157 get_pi_state(pi_state);
Peter Zijlstra734009e2017-03-22 11:35:52 +01001158 raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
Thomas Gleixnere60cbc52014-06-11 20:45:39 +00001159 *ps = pi_state;
1160 return 0;
Peter Zijlstra734009e2017-03-22 11:35:52 +01001161
1162out_einval:
1163 ret = -EINVAL;
1164 goto out_error;
1165
1166out_eagain:
1167 ret = -EAGAIN;
1168 goto out_error;
1169
1170out_efault:
1171 ret = -EFAULT;
1172 goto out_error;
1173
1174out_error:
1175 raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
1176 return ret;
Thomas Gleixnere60cbc52014-06-11 20:45:39 +00001177}
1178
Thomas Gleixner3ef240e2019-11-06 22:55:46 +01001179/**
1180 * wait_for_owner_exiting - Block until the owner has exited
Randy Dunlap51bfb1d2019-12-08 20:26:55 -08001181 * @ret: owner's current futex lock status
Thomas Gleixner3ef240e2019-11-06 22:55:46 +01001182 * @exiting: Pointer to the exiting task
1183 *
1184 * Caller must hold a refcount on @exiting.
1185 */
1186static void wait_for_owner_exiting(int ret, struct task_struct *exiting)
1187{
1188 if (ret != -EBUSY) {
1189 WARN_ON_ONCE(exiting);
1190 return;
1191 }
1192
1193 if (WARN_ON_ONCE(ret == -EBUSY && !exiting))
1194 return;
1195
1196 mutex_lock(&exiting->futex_exit_mutex);
1197 /*
1198 * No point in doing state checking here. If the waiter got here
1199 * while the task was in exec()->exec_futex_release() then it can
1200 * have any FUTEX_STATE_* value when the waiter has acquired the
1201 * mutex. OK, if running, EXITING or DEAD if it reached exit()
1202 * already. Highly unlikely and not a problem. Just one more round
1203 * through the futex maze.
1204 */
1205 mutex_unlock(&exiting->futex_exit_mutex);
1206
1207 put_task_struct(exiting);
1208}
1209
Thomas Gleixnerda791a62018-12-10 14:35:14 +01001210static int handle_exit_race(u32 __user *uaddr, u32 uval,
1211 struct task_struct *tsk)
1212{
1213 u32 uval2;
1214
1215 /*
Thomas Gleixnerac31c7f2019-11-06 22:55:45 +01001216 * If the futex exit state is not yet FUTEX_STATE_DEAD, tell the
1217 * caller that the alleged owner is busy.
Thomas Gleixnerda791a62018-12-10 14:35:14 +01001218 */
Thomas Gleixner3d4775d2019-11-06 22:55:37 +01001219 if (tsk && tsk->futex_state != FUTEX_STATE_DEAD)
Thomas Gleixnerac31c7f2019-11-06 22:55:45 +01001220 return -EBUSY;
Thomas Gleixnerda791a62018-12-10 14:35:14 +01001221
1222 /*
1223 * Reread the user space value to handle the following situation:
1224 *
1225 * CPU0 CPU1
1226 *
1227 * sys_exit() sys_futex()
1228 * do_exit() futex_lock_pi()
1229 * futex_lock_pi_atomic()
1230 * exit_signals(tsk) No waiters:
1231 * tsk->flags |= PF_EXITING; *uaddr == 0x00000PID
1232 * mm_release(tsk) Set waiter bit
1233 * exit_robust_list(tsk) { *uaddr = 0x80000PID;
1234 * Set owner died attach_to_pi_owner() {
1235 * *uaddr = 0xC0000000; tsk = get_task(PID);
1236 * } if (!tsk->flags & PF_EXITING) {
1237 * ... attach();
Thomas Gleixner3d4775d2019-11-06 22:55:37 +01001238 * tsk->futex_state = } else {
1239 * FUTEX_STATE_DEAD; if (tsk->futex_state !=
1240 * FUTEX_STATE_DEAD)
Thomas Gleixnerda791a62018-12-10 14:35:14 +01001241 * return -EAGAIN;
1242 * return -ESRCH; <--- FAIL
1243 * }
1244 *
1245 * Returning ESRCH unconditionally is wrong here because the
1246 * user space value has been changed by the exiting task.
1247 *
1248 * The same logic applies to the case where the exiting task is
1249 * already gone.
1250 */
1251 if (get_futex_value_locked(&uval2, uaddr))
1252 return -EFAULT;
1253
1254 /* If the user space value has changed, try again. */
1255 if (uval2 != uval)
1256 return -EAGAIN;
1257
1258 /*
1259 * The exiting task did not have a robust list, the robust list was
1260 * corrupted or the user space value in *uaddr is simply bogus.
1261 * Give up and tell user space.
1262 */
1263 return -ESRCH;
1264}
1265
Thomas Gleixner04e1b2e2014-06-11 20:45:40 +00001266/*
1267 * Lookup the task for the TID provided from user space and attach to
1268 * it after doing proper sanity checks.
1269 */
Thomas Gleixnerda791a62018-12-10 14:35:14 +01001270static int attach_to_pi_owner(u32 __user *uaddr, u32 uval, union futex_key *key,
Thomas Gleixner3ef240e2019-11-06 22:55:46 +01001271 struct futex_pi_state **ps,
1272 struct task_struct **exiting)
Ingo Molnarc87e2832006-06-27 02:54:58 -07001273{
Alexey Kuznetsov778e9a92007-06-08 13:47:00 -07001274 pid_t pid = uval & FUTEX_TID_MASK;
Thomas Gleixner04e1b2e2014-06-11 20:45:40 +00001275 struct futex_pi_state *pi_state;
1276 struct task_struct *p;
Ingo Molnarc87e2832006-06-27 02:54:58 -07001277
1278 /*
Ingo Molnare3f2dde2006-07-29 05:17:57 +02001279 * We are the first waiter - try to look up the real owner and attach
Thomas Gleixner54a217882014-06-03 12:27:08 +00001280 * the new pi_state to it, but bail out when TID = 0 [1]
Thomas Gleixnerda791a62018-12-10 14:35:14 +01001281 *
1282 * The !pid check is paranoid. None of the call sites should end up
1283 * with pid == 0, but better safe than sorry. Let the caller retry
Ingo Molnarc87e2832006-06-27 02:54:58 -07001284 */
Alexey Kuznetsov778e9a92007-06-08 13:47:00 -07001285 if (!pid)
Thomas Gleixnerda791a62018-12-10 14:35:14 +01001286 return -EAGAIN;
Mike Rapoport2ee08262018-02-06 15:40:17 -08001287 p = find_get_task_by_vpid(pid);
Michal Hocko7a0ea092010-06-30 09:51:19 +02001288 if (!p)
Thomas Gleixnerda791a62018-12-10 14:35:14 +01001289 return handle_exit_race(uaddr, uval, NULL);
Alexey Kuznetsov778e9a92007-06-08 13:47:00 -07001290
Oleg Nesterova2129462015-02-02 15:05:36 +01001291 if (unlikely(p->flags & PF_KTHREAD)) {
Thomas Gleixnerf0d71b32014-05-12 20:45:35 +00001292 put_task_struct(p);
1293 return -EPERM;
1294 }
1295
Alexey Kuznetsov778e9a92007-06-08 13:47:00 -07001296 /*
Thomas Gleixner3d4775d2019-11-06 22:55:37 +01001297 * We need to look at the task state to figure out, whether the
1298 * task is exiting. To protect against the change of the task state
1299 * in futex_exit_release(), we do this protected by p->pi_lock:
Alexey Kuznetsov778e9a92007-06-08 13:47:00 -07001300 */
Thomas Gleixner1d615482009-11-17 14:54:03 +01001301 raw_spin_lock_irq(&p->pi_lock);
Thomas Gleixner3d4775d2019-11-06 22:55:37 +01001302 if (unlikely(p->futex_state != FUTEX_STATE_OK)) {
Alexey Kuznetsov778e9a92007-06-08 13:47:00 -07001303 /*
Thomas Gleixner3d4775d2019-11-06 22:55:37 +01001304 * The task is on the way out. When the futex state is
1305 * FUTEX_STATE_DEAD, we know that the task has finished
1306 * the cleanup:
Alexey Kuznetsov778e9a92007-06-08 13:47:00 -07001307 */
Thomas Gleixnerda791a62018-12-10 14:35:14 +01001308 int ret = handle_exit_race(uaddr, uval, p);
Alexey Kuznetsov778e9a92007-06-08 13:47:00 -07001309
Thomas Gleixner1d615482009-11-17 14:54:03 +01001310 raw_spin_unlock_irq(&p->pi_lock);
Thomas Gleixner3ef240e2019-11-06 22:55:46 +01001311 /*
1312 * If the owner task is between FUTEX_STATE_EXITING and
1313 * FUTEX_STATE_DEAD then store the task pointer and keep
1314 * the reference on the task struct. The calling code will
1315 * drop all locks, wait for the task to reach
1316 * FUTEX_STATE_DEAD and then drop the refcount. This is
1317 * required to prevent a live lock when the current task
1318 * preempted the exiting task between the two states.
1319 */
1320 if (ret == -EBUSY)
1321 *exiting = p;
1322 else
1323 put_task_struct(p);
Alexey Kuznetsov778e9a92007-06-08 13:47:00 -07001324 return ret;
1325 }
Ingo Molnarc87e2832006-06-27 02:54:58 -07001326
Thomas Gleixner54a217882014-06-03 12:27:08 +00001327 /*
1328 * No existing pi state. First waiter. [2]
Peter Zijlstra734009e2017-03-22 11:35:52 +01001329 *
1330 * This creates pi_state, we have hb->lock held, this means nothing can
1331 * observe this state, wait_lock is irrelevant.
Thomas Gleixner54a217882014-06-03 12:27:08 +00001332 */
Ingo Molnarc87e2832006-06-27 02:54:58 -07001333 pi_state = alloc_pi_state();
1334
1335 /*
Thomas Gleixner04e1b2e2014-06-11 20:45:40 +00001336 * Initialize the pi_mutex in locked state and make @p
Ingo Molnarc87e2832006-06-27 02:54:58 -07001337 * the owner of it:
1338 */
1339 rt_mutex_init_proxy_locked(&pi_state->pi_mutex, p);
1340
1341 /* Store the key for possible exit cleanups: */
Pierre Peifferd0aa7a72007-05-09 02:35:02 -07001342 pi_state->key = *key;
Ingo Molnarc87e2832006-06-27 02:54:58 -07001343
Ingo Molnar627371d2006-07-29 05:16:20 +02001344 WARN_ON(!list_empty(&pi_state->list));
Ingo Molnarc87e2832006-06-27 02:54:58 -07001345 list_add(&pi_state->list, &p->pi_state_list);
Peter Zijlstrac74aef22017-09-22 17:48:06 +02001346 /*
1347 * Assignment without holding pi_state->pi_mutex.wait_lock is safe
1348 * because there is no concurrency as the object is not published yet.
1349 */
Ingo Molnarc87e2832006-06-27 02:54:58 -07001350 pi_state->owner = p;
Thomas Gleixner1d615482009-11-17 14:54:03 +01001351 raw_spin_unlock_irq(&p->pi_lock);
Ingo Molnarc87e2832006-06-27 02:54:58 -07001352
1353 put_task_struct(p);
1354
Pierre Peifferd0aa7a72007-05-09 02:35:02 -07001355 *ps = pi_state;
Ingo Molnarc87e2832006-06-27 02:54:58 -07001356
1357 return 0;
1358}
1359
Peter Zijlstra734009e2017-03-22 11:35:52 +01001360static int lookup_pi_state(u32 __user *uaddr, u32 uval,
1361 struct futex_hash_bucket *hb,
Thomas Gleixner3ef240e2019-11-06 22:55:46 +01001362 union futex_key *key, struct futex_pi_state **ps,
1363 struct task_struct **exiting)
Thomas Gleixner04e1b2e2014-06-11 20:45:40 +00001364{
Peter Zijlstra499f5ac2017-03-22 11:35:48 +01001365 struct futex_q *top_waiter = futex_top_waiter(hb, key);
Thomas Gleixner04e1b2e2014-06-11 20:45:40 +00001366
1367 /*
1368 * If there is a waiter on that futex, validate it and
1369 * attach to the pi_state when the validation succeeds.
1370 */
Peter Zijlstra499f5ac2017-03-22 11:35:48 +01001371 if (top_waiter)
Peter Zijlstra734009e2017-03-22 11:35:52 +01001372 return attach_to_pi_state(uaddr, uval, top_waiter->pi_state, ps);
Thomas Gleixner04e1b2e2014-06-11 20:45:40 +00001373
1374 /*
1375 * We are the first waiter - try to look up the owner based on
1376 * @uval and attach to it.
1377 */
Thomas Gleixner3ef240e2019-11-06 22:55:46 +01001378 return attach_to_pi_owner(uaddr, uval, key, ps, exiting);
Thomas Gleixner04e1b2e2014-06-11 20:45:40 +00001379}
1380
Thomas Gleixneraf54d6a2014-06-11 20:45:41 +00001381static int lock_pi_update_atomic(u32 __user *uaddr, u32 uval, u32 newval)
1382{
Will Deacon6b4f4bc2019-02-28 11:58:08 +00001383 int err;
Thomas Gleixneraf54d6a2014-06-11 20:45:41 +00001384 u32 uninitialized_var(curval);
1385
Davidlohr Buesoab51fba2015-06-29 23:26:02 -07001386 if (unlikely(should_fail_futex(true)))
1387 return -EFAULT;
1388
Will Deacon6b4f4bc2019-02-28 11:58:08 +00001389 err = cmpxchg_futex_value_locked(&curval, uaddr, uval, newval);
1390 if (unlikely(err))
1391 return err;
Thomas Gleixneraf54d6a2014-06-11 20:45:41 +00001392
Peter Zijlstra734009e2017-03-22 11:35:52 +01001393 /* If user space value changed, let the caller retry */
Thomas Gleixneraf54d6a2014-06-11 20:45:41 +00001394 return curval != uval ? -EAGAIN : 0;
1395}
1396
Darren Hart1a520842009-04-03 13:39:52 -07001397/**
Darren Hartd96ee562009-09-21 22:30:22 -07001398 * futex_lock_pi_atomic() - Atomic work required to acquire a pi aware futex
Darren Hartbab5bc92009-04-07 23:23:50 -07001399 * @uaddr: the pi futex user address
1400 * @hb: the pi futex hash bucket
1401 * @key: the futex key associated with uaddr and hb
1402 * @ps: the pi_state pointer where we store the result of the
1403 * lookup
1404 * @task: the task to perform the atomic lock work for. This will
1405 * be "current" except in the case of requeue pi.
Thomas Gleixner3ef240e2019-11-06 22:55:46 +01001406 * @exiting: Pointer to store the task pointer of the owner task
1407 * which is in the middle of exiting
Darren Hartbab5bc92009-04-07 23:23:50 -07001408 * @set_waiters: force setting the FUTEX_WAITERS bit (1) or not (0)
Darren Hart1a520842009-04-03 13:39:52 -07001409 *
Randy Dunlap6c23cbb2013-03-05 10:00:24 -08001410 * Return:
Mauro Carvalho Chehab7b4ff1a2017-05-11 10:17:45 -03001411 * - 0 - ready to wait;
1412 * - 1 - acquired the lock;
1413 * - <0 - error
Darren Hart1a520842009-04-03 13:39:52 -07001414 *
1415 * The hb->lock and futex_key refs shall be held by the caller.
Thomas Gleixner3ef240e2019-11-06 22:55:46 +01001416 *
1417 * @exiting is only set when the return value is -EBUSY. If so, this holds
1418 * a refcount on the exiting task on return and the caller needs to drop it
1419 * after waiting for the exit to complete.
Darren Hart1a520842009-04-03 13:39:52 -07001420 */
1421static int futex_lock_pi_atomic(u32 __user *uaddr, struct futex_hash_bucket *hb,
1422 union futex_key *key,
1423 struct futex_pi_state **ps,
Thomas Gleixner3ef240e2019-11-06 22:55:46 +01001424 struct task_struct *task,
1425 struct task_struct **exiting,
1426 int set_waiters)
Darren Hart1a520842009-04-03 13:39:52 -07001427{
Thomas Gleixneraf54d6a2014-06-11 20:45:41 +00001428 u32 uval, newval, vpid = task_pid_vnr(task);
Peter Zijlstra499f5ac2017-03-22 11:35:48 +01001429 struct futex_q *top_waiter;
Thomas Gleixneraf54d6a2014-06-11 20:45:41 +00001430 int ret;
Darren Hart1a520842009-04-03 13:39:52 -07001431
1432 /*
Thomas Gleixneraf54d6a2014-06-11 20:45:41 +00001433 * Read the user space value first so we can validate a few
1434 * things before proceeding further.
Darren Hart1a520842009-04-03 13:39:52 -07001435 */
Thomas Gleixneraf54d6a2014-06-11 20:45:41 +00001436 if (get_futex_value_locked(&uval, uaddr))
Darren Hart1a520842009-04-03 13:39:52 -07001437 return -EFAULT;
1438
Davidlohr Buesoab51fba2015-06-29 23:26:02 -07001439 if (unlikely(should_fail_futex(true)))
1440 return -EFAULT;
1441
Darren Hart1a520842009-04-03 13:39:52 -07001442 /*
1443 * Detect deadlocks.
1444 */
Thomas Gleixneraf54d6a2014-06-11 20:45:41 +00001445 if ((unlikely((uval & FUTEX_TID_MASK) == vpid)))
Darren Hart1a520842009-04-03 13:39:52 -07001446 return -EDEADLK;
1447
Davidlohr Buesoab51fba2015-06-29 23:26:02 -07001448 if ((unlikely(should_fail_futex(true))))
1449 return -EDEADLK;
1450
Darren Hart1a520842009-04-03 13:39:52 -07001451 /*
Thomas Gleixneraf54d6a2014-06-11 20:45:41 +00001452 * Lookup existing state first. If it exists, try to attach to
1453 * its pi_state.
Darren Hart1a520842009-04-03 13:39:52 -07001454 */
Peter Zijlstra499f5ac2017-03-22 11:35:48 +01001455 top_waiter = futex_top_waiter(hb, key);
1456 if (top_waiter)
Peter Zijlstra734009e2017-03-22 11:35:52 +01001457 return attach_to_pi_state(uaddr, uval, top_waiter->pi_state, ps);
Thomas Gleixneraf54d6a2014-06-11 20:45:41 +00001458
1459 /*
1460 * No waiter and user TID is 0. We are here because the
1461 * waiters or the owner died bit is set or called from
1462 * requeue_cmp_pi or for whatever reason something took the
1463 * syscall.
1464 */
1465 if (!(uval & FUTEX_TID_MASK)) {
Thomas Gleixnerb3eaa9f2014-06-03 12:27:06 +00001466 /*
Thomas Gleixneraf54d6a2014-06-11 20:45:41 +00001467 * We take over the futex. No other waiters and the user space
1468 * TID is 0. We preserve the owner died bit.
Thomas Gleixnerb3eaa9f2014-06-03 12:27:06 +00001469 */
Thomas Gleixneraf54d6a2014-06-11 20:45:41 +00001470 newval = uval & FUTEX_OWNER_DIED;
1471 newval |= vpid;
1472
1473 /* The futex requeue_pi code can enforce the waiters bit */
1474 if (set_waiters)
1475 newval |= FUTEX_WAITERS;
1476
1477 ret = lock_pi_update_atomic(uaddr, uval, newval);
1478 /* If the take over worked, return 1 */
1479 return ret < 0 ? ret : 1;
Thomas Gleixnerb3eaa9f2014-06-03 12:27:06 +00001480 }
Darren Hart1a520842009-04-03 13:39:52 -07001481
Darren Hart1a520842009-04-03 13:39:52 -07001482 /*
Thomas Gleixneraf54d6a2014-06-11 20:45:41 +00001483 * First waiter. Set the waiters bit before attaching ourself to
1484 * the owner. If owner tries to unlock, it will be forced into
1485 * the kernel and blocked on hb->lock.
Darren Hart1a520842009-04-03 13:39:52 -07001486 */
Thomas Gleixneraf54d6a2014-06-11 20:45:41 +00001487 newval = uval | FUTEX_WAITERS;
1488 ret = lock_pi_update_atomic(uaddr, uval, newval);
1489 if (ret)
1490 return ret;
Darren Hart1a520842009-04-03 13:39:52 -07001491 /*
Thomas Gleixneraf54d6a2014-06-11 20:45:41 +00001492 * If the update of the user space value succeeded, we try to
1493 * attach to the owner. If that fails, no harm done, we only
1494 * set the FUTEX_WAITERS bit in the user space variable.
Darren Hart1a520842009-04-03 13:39:52 -07001495 */
Thomas Gleixner3ef240e2019-11-06 22:55:46 +01001496 return attach_to_pi_owner(uaddr, newval, key, ps, exiting);
Darren Hart1a520842009-04-03 13:39:52 -07001497}
1498
Lai Jiangshan2e129782010-12-22 14:18:50 +08001499/**
1500 * __unqueue_futex() - Remove the futex_q from its futex_hash_bucket
1501 * @q: The futex_q to unqueue
1502 *
1503 * The q->lock_ptr must not be NULL and must be held by the caller.
1504 */
1505static void __unqueue_futex(struct futex_q *q)
1506{
1507 struct futex_hash_bucket *hb;
1508
Lance Roy4de1a292018-10-02 22:38:57 -07001509 if (WARN_ON_SMP(!q->lock_ptr) || WARN_ON(plist_node_empty(&q->list)))
Lai Jiangshan2e129782010-12-22 14:18:50 +08001510 return;
Lance Roy4de1a292018-10-02 22:38:57 -07001511 lockdep_assert_held(q->lock_ptr);
Lai Jiangshan2e129782010-12-22 14:18:50 +08001512
1513 hb = container_of(q->lock_ptr, struct futex_hash_bucket, lock);
1514 plist_del(&q->list, &hb->chain);
Linus Torvalds11d46162014-03-20 22:11:17 -07001515 hb_waiters_dec(hb);
Lai Jiangshan2e129782010-12-22 14:18:50 +08001516}
1517
Ingo Molnarc87e2832006-06-27 02:54:58 -07001518/*
Linus Torvalds1da177e2005-04-16 15:20:36 -07001519 * The hash bucket lock must be held when this is called.
Davidlohr Bueso1d0dcb32015-05-01 08:27:51 -07001520 * Afterwards, the futex_q must not be accessed. Callers
1521 * must ensure to later call wake_up_q() for the actual
1522 * wakeups to occur.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001523 */
Davidlohr Bueso1d0dcb32015-05-01 08:27:51 -07001524static void mark_wake_futex(struct wake_q_head *wake_q, struct futex_q *q)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001525{
Thomas Gleixnerf1a11e02009-05-05 19:21:40 +02001526 struct task_struct *p = q->task;
1527
Darren Hartaa109902012-11-26 16:29:56 -08001528 if (WARN(q->pi_state || q->rt_waiter, "refusing to wake PI futex\n"))
1529 return;
1530
Peter Zijlstrab061c382018-11-29 14:44:49 +01001531 get_task_struct(p);
Lai Jiangshan2e129782010-12-22 14:18:50 +08001532 __unqueue_futex(q);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001533 /*
Darren Hart (VMware)38fcd062017-04-14 15:31:38 -07001534 * The waiting task can free the futex_q as soon as q->lock_ptr = NULL
1535 * is written, without taking any locks. This is possible in the event
1536 * of a spurious wakeup, for example. A memory barrier is required here
1537 * to prevent the following store to lock_ptr from getting ahead of the
1538 * plist_del in __unqueue_futex().
Linus Torvalds1da177e2005-04-16 15:20:36 -07001539 */
Peter Zijlstra1b367ec2017-03-22 11:35:49 +01001540 smp_store_release(&q->lock_ptr, NULL);
Peter Zijlstrab061c382018-11-29 14:44:49 +01001541
1542 /*
1543 * Queue the task for later wakeup for after we've released
Davidlohr Bueso75145902019-10-22 20:34:50 -07001544 * the hb->lock.
Peter Zijlstrab061c382018-11-29 14:44:49 +01001545 */
Davidlohr Bueso07879c62018-12-18 11:53:52 -08001546 wake_q_add_safe(wake_q, p);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001547}
1548
Peter Zijlstra16ffa122017-03-22 11:35:55 +01001549/*
1550 * Caller must hold a reference on @pi_state.
1551 */
1552static int wake_futex_pi(u32 __user *uaddr, u32 uval, struct futex_pi_state *pi_state)
Ingo Molnarc87e2832006-06-27 02:54:58 -07001553{
Vitaliy Ivanov7cfdaf32011-07-07 15:10:31 +03001554 u32 uninitialized_var(curval), newval;
Peter Zijlstra16ffa122017-03-22 11:35:55 +01001555 struct task_struct *new_owner;
Peter Zijlstraaa2bfe52017-03-23 15:56:10 +01001556 bool postunlock = false;
Waiman Long194a6b52016-11-17 11:46:38 -05001557 DEFINE_WAKE_Q(wake_q);
Thomas Gleixner13fbca42014-06-03 12:27:07 +00001558 int ret = 0;
Ingo Molnarc87e2832006-06-27 02:54:58 -07001559
Ingo Molnarc87e2832006-06-27 02:54:58 -07001560 new_owner = rt_mutex_next_owner(&pi_state->pi_mutex);
Peter Zijlstrabebe5b52017-03-22 11:35:59 +01001561 if (WARN_ON_ONCE(!new_owner)) {
Peter Zijlstra16ffa122017-03-22 11:35:55 +01001562 /*
Peter Zijlstrabebe5b52017-03-22 11:35:59 +01001563 * As per the comment in futex_unlock_pi() this should not happen.
Peter Zijlstra16ffa122017-03-22 11:35:55 +01001564 *
1565 * When this happens, give up our locks and try again, giving
1566 * the futex_lock_pi() instance time to complete, either by
1567 * waiting on the rtmutex or removing itself from the futex
1568 * queue.
1569 */
1570 ret = -EAGAIN;
1571 goto out_unlock;
Peter Zijlstra73d786b2017-03-22 11:35:54 +01001572 }
Ingo Molnarc87e2832006-06-27 02:54:58 -07001573
1574 /*
Peter Zijlstra16ffa122017-03-22 11:35:55 +01001575 * We pass it to the next owner. The WAITERS bit is always kept
1576 * enabled while there is PI state around. We cleanup the owner
1577 * died bit, because we are the owner.
Ingo Molnarc87e2832006-06-27 02:54:58 -07001578 */
Thomas Gleixner13fbca42014-06-03 12:27:07 +00001579 newval = FUTEX_WAITERS | task_pid_vnr(new_owner);
Alexey Kuznetsov778e9a92007-06-08 13:47:00 -07001580
Davidlohr Buesoab51fba2015-06-29 23:26:02 -07001581 if (unlikely(should_fail_futex(true)))
1582 ret = -EFAULT;
1583
Will Deacon6b4f4bc2019-02-28 11:58:08 +00001584 ret = cmpxchg_futex_value_locked(&curval, uaddr, uval, newval);
1585 if (!ret && (curval != uval)) {
Sebastian Andrzej Siewior89e9e662016-04-15 14:35:39 +02001586 /*
1587 * If a unconditional UNLOCK_PI operation (user space did not
1588 * try the TID->0 transition) raced with a waiter setting the
1589 * FUTEX_WAITERS flag between get_user() and locking the hash
1590 * bucket lock, retry the operation.
1591 */
1592 if ((FUTEX_TID_MASK & curval) == uval)
1593 ret = -EAGAIN;
1594 else
1595 ret = -EINVAL;
1596 }
Peter Zijlstra734009e2017-03-22 11:35:52 +01001597
Peter Zijlstra16ffa122017-03-22 11:35:55 +01001598 if (ret)
1599 goto out_unlock;
Ingo Molnarc87e2832006-06-27 02:54:58 -07001600
Peter Zijlstra94ffac52017-04-07 09:04:07 +02001601 /*
1602 * This is a point of no return; once we modify the uval there is no
1603 * going back and subsequent operations must not fail.
1604 */
1605
Thomas Gleixnerb4abf912016-01-13 11:25:38 +01001606 raw_spin_lock(&pi_state->owner->pi_lock);
Ingo Molnar627371d2006-07-29 05:16:20 +02001607 WARN_ON(list_empty(&pi_state->list));
1608 list_del_init(&pi_state->list);
Thomas Gleixnerb4abf912016-01-13 11:25:38 +01001609 raw_spin_unlock(&pi_state->owner->pi_lock);
Ingo Molnar627371d2006-07-29 05:16:20 +02001610
Thomas Gleixnerb4abf912016-01-13 11:25:38 +01001611 raw_spin_lock(&new_owner->pi_lock);
Ingo Molnar627371d2006-07-29 05:16:20 +02001612 WARN_ON(!list_empty(&pi_state->list));
Ingo Molnarc87e2832006-06-27 02:54:58 -07001613 list_add(&pi_state->list, &new_owner->pi_state_list);
1614 pi_state->owner = new_owner;
Thomas Gleixnerb4abf912016-01-13 11:25:38 +01001615 raw_spin_unlock(&new_owner->pi_lock);
Ingo Molnar627371d2006-07-29 05:16:20 +02001616
Peter Zijlstraaa2bfe52017-03-23 15:56:10 +01001617 postunlock = __rt_mutex_futex_unlock(&pi_state->pi_mutex, &wake_q);
Peter Zijlstra5293c2e2017-03-22 11:35:51 +01001618
Peter Zijlstra16ffa122017-03-22 11:35:55 +01001619out_unlock:
Peter Zijlstra5293c2e2017-03-22 11:35:51 +01001620 raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
Peter Zijlstra5293c2e2017-03-22 11:35:51 +01001621
Peter Zijlstraaa2bfe52017-03-23 15:56:10 +01001622 if (postunlock)
1623 rt_mutex_postunlock(&wake_q);
Ingo Molnarc87e2832006-06-27 02:54:58 -07001624
Peter Zijlstra16ffa122017-03-22 11:35:55 +01001625 return ret;
Ingo Molnarc87e2832006-06-27 02:54:58 -07001626}
1627
Linus Torvalds1da177e2005-04-16 15:20:36 -07001628/*
Ingo Molnar8b8f3192006-07-03 00:25:05 -07001629 * Express the locking dependencies for lockdep:
1630 */
1631static inline void
1632double_lock_hb(struct futex_hash_bucket *hb1, struct futex_hash_bucket *hb2)
1633{
1634 if (hb1 <= hb2) {
1635 spin_lock(&hb1->lock);
1636 if (hb1 < hb2)
1637 spin_lock_nested(&hb2->lock, SINGLE_DEPTH_NESTING);
1638 } else { /* hb1 > hb2 */
1639 spin_lock(&hb2->lock);
1640 spin_lock_nested(&hb1->lock, SINGLE_DEPTH_NESTING);
1641 }
1642}
1643
Darren Hart5eb3dc62009-03-12 00:55:52 -07001644static inline void
1645double_unlock_hb(struct futex_hash_bucket *hb1, struct futex_hash_bucket *hb2)
1646{
Darren Hartf061d352009-03-12 15:11:18 -07001647 spin_unlock(&hb1->lock);
Ingo Molnar88f502f2009-03-13 10:32:07 +01001648 if (hb1 != hb2)
1649 spin_unlock(&hb2->lock);
Darren Hart5eb3dc62009-03-12 00:55:52 -07001650}
1651
Ingo Molnar8b8f3192006-07-03 00:25:05 -07001652/*
Darren Hartb2d09942009-03-12 00:55:37 -07001653 * Wake up waiters matching bitset queued on this futex (uaddr).
Linus Torvalds1da177e2005-04-16 15:20:36 -07001654 */
Darren Hartb41277d2010-11-08 13:10:09 -08001655static int
1656futex_wake(u32 __user *uaddr, unsigned int flags, int nr_wake, u32 bitset)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001657{
Ingo Molnare2970f22006-06-27 02:54:47 -07001658 struct futex_hash_bucket *hb;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001659 struct futex_q *this, *next;
Peter Zijlstra38d47c12008-09-26 19:32:20 +02001660 union futex_key key = FUTEX_KEY_INIT;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001661 int ret;
Waiman Long194a6b52016-11-17 11:46:38 -05001662 DEFINE_WAKE_Q(wake_q);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001663
Thomas Gleixnercd6899852008-02-01 17:45:14 +01001664 if (!bitset)
1665 return -EINVAL;
1666
Linus Torvalds96d4f262019-01-03 18:57:57 -08001667 ret = get_futex_key(uaddr, flags & FLAGS_SHARED, &key, FUTEX_READ);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001668 if (unlikely(ret != 0))
1669 goto out;
1670
Ingo Molnare2970f22006-06-27 02:54:47 -07001671 hb = hash_futex(&key);
Davidlohr Buesob0c29f72014-01-12 15:31:25 -08001672
1673 /* Make sure we really have tasks to wakeup */
1674 if (!hb_waiters_pending(hb))
1675 goto out_put_key;
1676
Ingo Molnare2970f22006-06-27 02:54:47 -07001677 spin_lock(&hb->lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001678
Jason Low0d00c7b2014-01-12 15:31:22 -08001679 plist_for_each_entry_safe(this, next, &hb->chain, list) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001680 if (match_futex (&this->key, &key)) {
Darren Hart52400ba2009-04-03 13:40:49 -07001681 if (this->pi_state || this->rt_waiter) {
Ingo Molnared6f7b12006-07-01 04:35:46 -07001682 ret = -EINVAL;
1683 break;
1684 }
Thomas Gleixnercd6899852008-02-01 17:45:14 +01001685
1686 /* Check if one of the bits is set in both bitsets */
1687 if (!(this->bitset & bitset))
1688 continue;
1689
Davidlohr Bueso1d0dcb32015-05-01 08:27:51 -07001690 mark_wake_futex(&wake_q, this);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001691 if (++ret >= nr_wake)
1692 break;
1693 }
1694 }
1695
Ingo Molnare2970f22006-06-27 02:54:47 -07001696 spin_unlock(&hb->lock);
Davidlohr Bueso1d0dcb32015-05-01 08:27:51 -07001697 wake_up_q(&wake_q);
Davidlohr Buesob0c29f72014-01-12 15:31:25 -08001698out_put_key:
Thomas Gleixnerae791a22010-11-10 13:30:36 +01001699 put_futex_key(&key);
Darren Hart42d35d42008-12-29 15:49:53 -08001700out:
Linus Torvalds1da177e2005-04-16 15:20:36 -07001701 return ret;
1702}
1703
Jiri Slaby30d6e0a2017-08-24 09:31:05 +02001704static int futex_atomic_op_inuser(unsigned int encoded_op, u32 __user *uaddr)
1705{
1706 unsigned int op = (encoded_op & 0x70000000) >> 28;
1707 unsigned int cmp = (encoded_op & 0x0f000000) >> 24;
Jiri Slabyd70ef222017-11-30 15:35:44 +01001708 int oparg = sign_extend32((encoded_op & 0x00fff000) >> 12, 11);
1709 int cmparg = sign_extend32(encoded_op & 0x00000fff, 11);
Jiri Slaby30d6e0a2017-08-24 09:31:05 +02001710 int oldval, ret;
1711
1712 if (encoded_op & (FUTEX_OP_OPARG_SHIFT << 28)) {
Jiri Slabye78c38f62017-10-23 13:41:51 +02001713 if (oparg < 0 || oparg > 31) {
1714 char comm[sizeof(current->comm)];
1715 /*
1716 * kill this print and return -EINVAL when userspace
1717 * is sane again
1718 */
1719 pr_info_ratelimited("futex_wake_op: %s tries to shift op by %d; fix this program\n",
1720 get_task_comm(comm, current), oparg);
1721 oparg &= 31;
1722 }
Jiri Slaby30d6e0a2017-08-24 09:31:05 +02001723 oparg = 1 << oparg;
1724 }
1725
Linus Torvalds96d4f262019-01-03 18:57:57 -08001726 if (!access_ok(uaddr, sizeof(u32)))
Jiri Slaby30d6e0a2017-08-24 09:31:05 +02001727 return -EFAULT;
1728
1729 ret = arch_futex_atomic_op_inuser(op, oparg, &oldval, uaddr);
1730 if (ret)
1731 return ret;
1732
1733 switch (cmp) {
1734 case FUTEX_OP_CMP_EQ:
1735 return oldval == cmparg;
1736 case FUTEX_OP_CMP_NE:
1737 return oldval != cmparg;
1738 case FUTEX_OP_CMP_LT:
1739 return oldval < cmparg;
1740 case FUTEX_OP_CMP_GE:
1741 return oldval >= cmparg;
1742 case FUTEX_OP_CMP_LE:
1743 return oldval <= cmparg;
1744 case FUTEX_OP_CMP_GT:
1745 return oldval > cmparg;
1746 default:
1747 return -ENOSYS;
1748 }
1749}
1750
Linus Torvalds1da177e2005-04-16 15:20:36 -07001751/*
Jakub Jelinek4732efbe2005-09-06 15:16:25 -07001752 * Wake up all waiters hashed on the physical page that is mapped
1753 * to this virtual address:
1754 */
Ingo Molnare2970f22006-06-27 02:54:47 -07001755static int
Darren Hartb41277d2010-11-08 13:10:09 -08001756futex_wake_op(u32 __user *uaddr1, unsigned int flags, u32 __user *uaddr2,
Ingo Molnare2970f22006-06-27 02:54:47 -07001757 int nr_wake, int nr_wake2, int op)
Jakub Jelinek4732efbe2005-09-06 15:16:25 -07001758{
Peter Zijlstra38d47c12008-09-26 19:32:20 +02001759 union futex_key key1 = FUTEX_KEY_INIT, key2 = FUTEX_KEY_INIT;
Ingo Molnare2970f22006-06-27 02:54:47 -07001760 struct futex_hash_bucket *hb1, *hb2;
Jakub Jelinek4732efbe2005-09-06 15:16:25 -07001761 struct futex_q *this, *next;
Darren Harte4dc5b72009-03-12 00:56:13 -07001762 int ret, op_ret;
Waiman Long194a6b52016-11-17 11:46:38 -05001763 DEFINE_WAKE_Q(wake_q);
Jakub Jelinek4732efbe2005-09-06 15:16:25 -07001764
Darren Harte4dc5b72009-03-12 00:56:13 -07001765retry:
Linus Torvalds96d4f262019-01-03 18:57:57 -08001766 ret = get_futex_key(uaddr1, flags & FLAGS_SHARED, &key1, FUTEX_READ);
Jakub Jelinek4732efbe2005-09-06 15:16:25 -07001767 if (unlikely(ret != 0))
1768 goto out;
Linus Torvalds96d4f262019-01-03 18:57:57 -08001769 ret = get_futex_key(uaddr2, flags & FLAGS_SHARED, &key2, FUTEX_WRITE);
Jakub Jelinek4732efbe2005-09-06 15:16:25 -07001770 if (unlikely(ret != 0))
Darren Hart42d35d42008-12-29 15:49:53 -08001771 goto out_put_key1;
Jakub Jelinek4732efbe2005-09-06 15:16:25 -07001772
Ingo Molnare2970f22006-06-27 02:54:47 -07001773 hb1 = hash_futex(&key1);
1774 hb2 = hash_futex(&key2);
Jakub Jelinek4732efbe2005-09-06 15:16:25 -07001775
Darren Harte4dc5b72009-03-12 00:56:13 -07001776retry_private:
Thomas Gleixnereaaea802009-10-04 09:34:17 +02001777 double_lock_hb(hb1, hb2);
Ingo Molnare2970f22006-06-27 02:54:47 -07001778 op_ret = futex_atomic_op_inuser(op, uaddr2);
Jakub Jelinek4732efbe2005-09-06 15:16:25 -07001779 if (unlikely(op_ret < 0)) {
Darren Hart5eb3dc62009-03-12 00:55:52 -07001780 double_unlock_hb(hb1, hb2);
Jakub Jelinek4732efbe2005-09-06 15:16:25 -07001781
Will Deacon6b4f4bc2019-02-28 11:58:08 +00001782 if (!IS_ENABLED(CONFIG_MMU) ||
1783 unlikely(op_ret != -EFAULT && op_ret != -EAGAIN)) {
1784 /*
1785 * we don't get EFAULT from MMU faults if we don't have
1786 * an MMU, but we might get them from range checking
1787 */
David Gibson796f8d92005-11-07 00:59:33 -08001788 ret = op_ret;
Darren Hart42d35d42008-12-29 15:49:53 -08001789 goto out_put_keys;
David Gibson796f8d92005-11-07 00:59:33 -08001790 }
1791
Will Deacon6b4f4bc2019-02-28 11:58:08 +00001792 if (op_ret == -EFAULT) {
1793 ret = fault_in_user_writeable(uaddr2);
1794 if (ret)
1795 goto out_put_keys;
1796 }
Jakub Jelinek4732efbe2005-09-06 15:16:25 -07001797
Will Deacon6b4f4bc2019-02-28 11:58:08 +00001798 if (!(flags & FLAGS_SHARED)) {
1799 cond_resched();
Darren Harte4dc5b72009-03-12 00:56:13 -07001800 goto retry_private;
Will Deacon6b4f4bc2019-02-28 11:58:08 +00001801 }
Darren Harte4dc5b72009-03-12 00:56:13 -07001802
Thomas Gleixnerae791a22010-11-10 13:30:36 +01001803 put_futex_key(&key2);
1804 put_futex_key(&key1);
Will Deacon6b4f4bc2019-02-28 11:58:08 +00001805 cond_resched();
Darren Harte4dc5b72009-03-12 00:56:13 -07001806 goto retry;
Jakub Jelinek4732efbe2005-09-06 15:16:25 -07001807 }
1808
Jason Low0d00c7b2014-01-12 15:31:22 -08001809 plist_for_each_entry_safe(this, next, &hb1->chain, list) {
Jakub Jelinek4732efbe2005-09-06 15:16:25 -07001810 if (match_futex (&this->key, &key1)) {
Darren Hartaa109902012-11-26 16:29:56 -08001811 if (this->pi_state || this->rt_waiter) {
1812 ret = -EINVAL;
1813 goto out_unlock;
1814 }
Davidlohr Bueso1d0dcb32015-05-01 08:27:51 -07001815 mark_wake_futex(&wake_q, this);
Jakub Jelinek4732efbe2005-09-06 15:16:25 -07001816 if (++ret >= nr_wake)
1817 break;
1818 }
1819 }
1820
1821 if (op_ret > 0) {
Jakub Jelinek4732efbe2005-09-06 15:16:25 -07001822 op_ret = 0;
Jason Low0d00c7b2014-01-12 15:31:22 -08001823 plist_for_each_entry_safe(this, next, &hb2->chain, list) {
Jakub Jelinek4732efbe2005-09-06 15:16:25 -07001824 if (match_futex (&this->key, &key2)) {
Darren Hartaa109902012-11-26 16:29:56 -08001825 if (this->pi_state || this->rt_waiter) {
1826 ret = -EINVAL;
1827 goto out_unlock;
1828 }
Davidlohr Bueso1d0dcb32015-05-01 08:27:51 -07001829 mark_wake_futex(&wake_q, this);
Jakub Jelinek4732efbe2005-09-06 15:16:25 -07001830 if (++op_ret >= nr_wake2)
1831 break;
1832 }
1833 }
1834 ret += op_ret;
1835 }
1836
Darren Hartaa109902012-11-26 16:29:56 -08001837out_unlock:
Darren Hart5eb3dc62009-03-12 00:55:52 -07001838 double_unlock_hb(hb1, hb2);
Davidlohr Bueso1d0dcb32015-05-01 08:27:51 -07001839 wake_up_q(&wake_q);
Darren Hart42d35d42008-12-29 15:49:53 -08001840out_put_keys:
Thomas Gleixnerae791a22010-11-10 13:30:36 +01001841 put_futex_key(&key2);
Darren Hart42d35d42008-12-29 15:49:53 -08001842out_put_key1:
Thomas Gleixnerae791a22010-11-10 13:30:36 +01001843 put_futex_key(&key1);
Darren Hart42d35d42008-12-29 15:49:53 -08001844out:
Jakub Jelinek4732efbe2005-09-06 15:16:25 -07001845 return ret;
1846}
1847
Darren Hart9121e472009-04-03 13:40:31 -07001848/**
1849 * requeue_futex() - Requeue a futex_q from one hb to another
1850 * @q: the futex_q to requeue
1851 * @hb1: the source hash_bucket
1852 * @hb2: the target hash_bucket
1853 * @key2: the new key for the requeued futex_q
1854 */
1855static inline
1856void requeue_futex(struct futex_q *q, struct futex_hash_bucket *hb1,
1857 struct futex_hash_bucket *hb2, union futex_key *key2)
1858{
1859
1860 /*
1861 * If key1 and key2 hash to the same bucket, no need to
1862 * requeue.
1863 */
1864 if (likely(&hb1->chain != &hb2->chain)) {
1865 plist_del(&q->list, &hb1->chain);
Linus Torvalds11d46162014-03-20 22:11:17 -07001866 hb_waiters_dec(hb1);
Linus Torvalds11d46162014-03-20 22:11:17 -07001867 hb_waiters_inc(hb2);
Davidlohr Buesofe1bce92016-04-20 20:09:24 -07001868 plist_add(&q->list, &hb2->chain);
Darren Hart9121e472009-04-03 13:40:31 -07001869 q->lock_ptr = &hb2->lock;
Darren Hart9121e472009-04-03 13:40:31 -07001870 }
1871 get_futex_key_refs(key2);
1872 q->key = *key2;
1873}
1874
Darren Hart52400ba2009-04-03 13:40:49 -07001875/**
1876 * requeue_pi_wake_futex() - Wake a task that acquired the lock during requeue
Darren Hartd96ee562009-09-21 22:30:22 -07001877 * @q: the futex_q
1878 * @key: the key of the requeue target futex
1879 * @hb: the hash_bucket of the requeue target futex
Darren Hart52400ba2009-04-03 13:40:49 -07001880 *
1881 * During futex_requeue, with requeue_pi=1, it is possible to acquire the
1882 * target futex if it is uncontended or via a lock steal. Set the futex_q key
1883 * to the requeue target futex so the waiter can detect the wakeup on the right
1884 * futex, but remove it from the hb and NULL the rt_waiter so it can detect
Darren Hartbeda2c72009-08-09 15:34:39 -07001885 * atomic lock acquisition. Set the q->lock_ptr to the requeue target hb->lock
1886 * to protect access to the pi_state to fixup the owner later. Must be called
1887 * with both q->lock_ptr and hb->lock held.
Darren Hart52400ba2009-04-03 13:40:49 -07001888 */
1889static inline
Darren Hartbeda2c72009-08-09 15:34:39 -07001890void requeue_pi_wake_futex(struct futex_q *q, union futex_key *key,
1891 struct futex_hash_bucket *hb)
Darren Hart52400ba2009-04-03 13:40:49 -07001892{
Darren Hart52400ba2009-04-03 13:40:49 -07001893 get_futex_key_refs(key);
1894 q->key = *key;
1895
Lai Jiangshan2e129782010-12-22 14:18:50 +08001896 __unqueue_futex(q);
Darren Hart52400ba2009-04-03 13:40:49 -07001897
1898 WARN_ON(!q->rt_waiter);
1899 q->rt_waiter = NULL;
1900
Darren Hartbeda2c72009-08-09 15:34:39 -07001901 q->lock_ptr = &hb->lock;
Darren Hartbeda2c72009-08-09 15:34:39 -07001902
Thomas Gleixnerf1a11e02009-05-05 19:21:40 +02001903 wake_up_state(q->task, TASK_NORMAL);
Darren Hart52400ba2009-04-03 13:40:49 -07001904}
1905
1906/**
1907 * futex_proxy_trylock_atomic() - Attempt an atomic lock for the top waiter
Darren Hartbab5bc92009-04-07 23:23:50 -07001908 * @pifutex: the user address of the to futex
1909 * @hb1: the from futex hash bucket, must be locked by the caller
1910 * @hb2: the to futex hash bucket, must be locked by the caller
1911 * @key1: the from futex key
1912 * @key2: the to futex key
1913 * @ps: address to store the pi_state pointer
Thomas Gleixner3ef240e2019-11-06 22:55:46 +01001914 * @exiting: Pointer to store the task pointer of the owner task
1915 * which is in the middle of exiting
Darren Hartbab5bc92009-04-07 23:23:50 -07001916 * @set_waiters: force setting the FUTEX_WAITERS bit (1) or not (0)
Darren Hart52400ba2009-04-03 13:40:49 -07001917 *
1918 * Try and get the lock on behalf of the top waiter if we can do it atomically.
Darren Hartbab5bc92009-04-07 23:23:50 -07001919 * Wake the top waiter if we succeed. If the caller specified set_waiters,
1920 * then direct futex_lock_pi_atomic() to force setting the FUTEX_WAITERS bit.
1921 * hb1 and hb2 must be held by the caller.
Darren Hart52400ba2009-04-03 13:40:49 -07001922 *
Thomas Gleixner3ef240e2019-11-06 22:55:46 +01001923 * @exiting is only set when the return value is -EBUSY. If so, this holds
1924 * a refcount on the exiting task on return and the caller needs to drop it
1925 * after waiting for the exit to complete.
1926 *
Randy Dunlap6c23cbb2013-03-05 10:00:24 -08001927 * Return:
Mauro Carvalho Chehab7b4ff1a2017-05-11 10:17:45 -03001928 * - 0 - failed to acquire the lock atomically;
1929 * - >0 - acquired the lock, return value is vpid of the top_waiter
1930 * - <0 - error
Darren Hart52400ba2009-04-03 13:40:49 -07001931 */
Thomas Gleixner3ef240e2019-11-06 22:55:46 +01001932static int
1933futex_proxy_trylock_atomic(u32 __user *pifutex, struct futex_hash_bucket *hb1,
1934 struct futex_hash_bucket *hb2, union futex_key *key1,
1935 union futex_key *key2, struct futex_pi_state **ps,
1936 struct task_struct **exiting, int set_waiters)
Darren Hart52400ba2009-04-03 13:40:49 -07001937{
Darren Hartbab5bc92009-04-07 23:23:50 -07001938 struct futex_q *top_waiter = NULL;
Darren Hart52400ba2009-04-03 13:40:49 -07001939 u32 curval;
Thomas Gleixner866293e2014-05-12 20:45:34 +00001940 int ret, vpid;
Darren Hart52400ba2009-04-03 13:40:49 -07001941
1942 if (get_futex_value_locked(&curval, pifutex))
1943 return -EFAULT;
1944
Davidlohr Buesoab51fba2015-06-29 23:26:02 -07001945 if (unlikely(should_fail_futex(true)))
1946 return -EFAULT;
1947
Darren Hartbab5bc92009-04-07 23:23:50 -07001948 /*
1949 * Find the top_waiter and determine if there are additional waiters.
1950 * If the caller intends to requeue more than 1 waiter to pifutex,
1951 * force futex_lock_pi_atomic() to set the FUTEX_WAITERS bit now,
1952 * as we have means to handle the possible fault. If not, don't set
1953 * the bit unecessarily as it will force the subsequent unlock to enter
1954 * the kernel.
1955 */
Darren Hart52400ba2009-04-03 13:40:49 -07001956 top_waiter = futex_top_waiter(hb1, key1);
1957
1958 /* There are no waiters, nothing for us to do. */
1959 if (!top_waiter)
1960 return 0;
1961
Darren Hart84bc4af2009-08-13 17:36:53 -07001962 /* Ensure we requeue to the expected futex. */
1963 if (!match_futex(top_waiter->requeue_pi_key, key2))
1964 return -EINVAL;
1965
Darren Hart52400ba2009-04-03 13:40:49 -07001966 /*
Darren Hartbab5bc92009-04-07 23:23:50 -07001967 * Try to take the lock for top_waiter. Set the FUTEX_WAITERS bit in
1968 * the contended case or if set_waiters is 1. The pi_state is returned
1969 * in ps in contended cases.
Darren Hart52400ba2009-04-03 13:40:49 -07001970 */
Thomas Gleixner866293e2014-05-12 20:45:34 +00001971 vpid = task_pid_vnr(top_waiter->task);
Darren Hartbab5bc92009-04-07 23:23:50 -07001972 ret = futex_lock_pi_atomic(pifutex, hb2, key2, ps, top_waiter->task,
Thomas Gleixner3ef240e2019-11-06 22:55:46 +01001973 exiting, set_waiters);
Thomas Gleixner866293e2014-05-12 20:45:34 +00001974 if (ret == 1) {
Darren Hartbeda2c72009-08-09 15:34:39 -07001975 requeue_pi_wake_futex(top_waiter, key2, hb2);
Thomas Gleixner866293e2014-05-12 20:45:34 +00001976 return vpid;
1977 }
Darren Hart52400ba2009-04-03 13:40:49 -07001978 return ret;
1979}
1980
1981/**
1982 * futex_requeue() - Requeue waiters from uaddr1 to uaddr2
Randy Dunlapfb62db22010-10-13 11:02:34 -07001983 * @uaddr1: source futex user address
Darren Hartb41277d2010-11-08 13:10:09 -08001984 * @flags: futex flags (FLAGS_SHARED, etc.)
Randy Dunlapfb62db22010-10-13 11:02:34 -07001985 * @uaddr2: target futex user address
1986 * @nr_wake: number of waiters to wake (must be 1 for requeue_pi)
1987 * @nr_requeue: number of waiters to requeue (0-INT_MAX)
1988 * @cmpval: @uaddr1 expected value (or %NULL)
1989 * @requeue_pi: if we are attempting to requeue from a non-pi futex to a
Darren Hartb41277d2010-11-08 13:10:09 -08001990 * pi futex (pi to pi requeue is not supported)
Darren Hart52400ba2009-04-03 13:40:49 -07001991 *
1992 * Requeue waiters on uaddr1 to uaddr2. In the requeue_pi case, try to acquire
1993 * uaddr2 atomically on behalf of the top waiter.
1994 *
Randy Dunlap6c23cbb2013-03-05 10:00:24 -08001995 * Return:
Mauro Carvalho Chehab7b4ff1a2017-05-11 10:17:45 -03001996 * - >=0 - on success, the number of tasks requeued or woken;
1997 * - <0 - on error
Linus Torvalds1da177e2005-04-16 15:20:36 -07001998 */
Darren Hartb41277d2010-11-08 13:10:09 -08001999static int futex_requeue(u32 __user *uaddr1, unsigned int flags,
2000 u32 __user *uaddr2, int nr_wake, int nr_requeue,
2001 u32 *cmpval, int requeue_pi)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002002{
Peter Zijlstra38d47c12008-09-26 19:32:20 +02002003 union futex_key key1 = FUTEX_KEY_INIT, key2 = FUTEX_KEY_INIT;
Darren Hart52400ba2009-04-03 13:40:49 -07002004 int drop_count = 0, task_count = 0, ret;
2005 struct futex_pi_state *pi_state = NULL;
Ingo Molnare2970f22006-06-27 02:54:47 -07002006 struct futex_hash_bucket *hb1, *hb2;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002007 struct futex_q *this, *next;
Waiman Long194a6b52016-11-17 11:46:38 -05002008 DEFINE_WAKE_Q(wake_q);
Darren Hart52400ba2009-04-03 13:40:49 -07002009
Li Jinyuefbe0e832017-12-14 17:04:54 +08002010 if (nr_wake < 0 || nr_requeue < 0)
2011 return -EINVAL;
2012
Nicolas Pitrebc2eecd2017-08-01 00:31:32 -04002013 /*
2014 * When PI not supported: return -ENOSYS if requeue_pi is true,
2015 * consequently the compiler knows requeue_pi is always false past
2016 * this point which will optimize away all the conditional code
2017 * further down.
2018 */
2019 if (!IS_ENABLED(CONFIG_FUTEX_PI) && requeue_pi)
2020 return -ENOSYS;
2021
Darren Hart52400ba2009-04-03 13:40:49 -07002022 if (requeue_pi) {
2023 /*
Thomas Gleixnere9c243a2014-06-03 12:27:06 +00002024 * Requeue PI only works on two distinct uaddrs. This
2025 * check is only valid for private futexes. See below.
2026 */
2027 if (uaddr1 == uaddr2)
2028 return -EINVAL;
2029
2030 /*
Darren Hart52400ba2009-04-03 13:40:49 -07002031 * requeue_pi requires a pi_state, try to allocate it now
2032 * without any locks in case it fails.
2033 */
2034 if (refill_pi_state_cache())
2035 return -ENOMEM;
2036 /*
2037 * requeue_pi must wake as many tasks as it can, up to nr_wake
2038 * + nr_requeue, since it acquires the rt_mutex prior to
2039 * returning to userspace, so as to not leave the rt_mutex with
2040 * waiters and no owner. However, second and third wake-ups
2041 * cannot be predicted as they involve race conditions with the
2042 * first wake and a fault while looking up the pi_state. Both
2043 * pthread_cond_signal() and pthread_cond_broadcast() should
2044 * use nr_wake=1.
2045 */
2046 if (nr_wake != 1)
2047 return -EINVAL;
2048 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002049
Darren Hart42d35d42008-12-29 15:49:53 -08002050retry:
Linus Torvalds96d4f262019-01-03 18:57:57 -08002051 ret = get_futex_key(uaddr1, flags & FLAGS_SHARED, &key1, FUTEX_READ);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002052 if (unlikely(ret != 0))
2053 goto out;
Shawn Bohrer9ea71502011-06-30 11:21:32 -05002054 ret = get_futex_key(uaddr2, flags & FLAGS_SHARED, &key2,
Linus Torvalds96d4f262019-01-03 18:57:57 -08002055 requeue_pi ? FUTEX_WRITE : FUTEX_READ);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002056 if (unlikely(ret != 0))
Darren Hart42d35d42008-12-29 15:49:53 -08002057 goto out_put_key1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002058
Thomas Gleixnere9c243a2014-06-03 12:27:06 +00002059 /*
2060 * The check above which compares uaddrs is not sufficient for
2061 * shared futexes. We need to compare the keys:
2062 */
2063 if (requeue_pi && match_futex(&key1, &key2)) {
2064 ret = -EINVAL;
2065 goto out_put_keys;
2066 }
2067
Ingo Molnare2970f22006-06-27 02:54:47 -07002068 hb1 = hash_futex(&key1);
2069 hb2 = hash_futex(&key2);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002070
Darren Harte4dc5b72009-03-12 00:56:13 -07002071retry_private:
Linus Torvalds69cd9eb2014-04-08 15:30:07 -07002072 hb_waiters_inc(hb2);
Ingo Molnar8b8f3192006-07-03 00:25:05 -07002073 double_lock_hb(hb1, hb2);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002074
Ingo Molnare2970f22006-06-27 02:54:47 -07002075 if (likely(cmpval != NULL)) {
2076 u32 curval;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002077
Ingo Molnare2970f22006-06-27 02:54:47 -07002078 ret = get_futex_value_locked(&curval, uaddr1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002079
2080 if (unlikely(ret)) {
Darren Hart5eb3dc62009-03-12 00:55:52 -07002081 double_unlock_hb(hb1, hb2);
Linus Torvalds69cd9eb2014-04-08 15:30:07 -07002082 hb_waiters_dec(hb2);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002083
Darren Harte4dc5b72009-03-12 00:56:13 -07002084 ret = get_user(curval, uaddr1);
2085 if (ret)
2086 goto out_put_keys;
2087
Darren Hartb41277d2010-11-08 13:10:09 -08002088 if (!(flags & FLAGS_SHARED))
Darren Harte4dc5b72009-03-12 00:56:13 -07002089 goto retry_private;
2090
Thomas Gleixnerae791a22010-11-10 13:30:36 +01002091 put_futex_key(&key2);
2092 put_futex_key(&key1);
Darren Harte4dc5b72009-03-12 00:56:13 -07002093 goto retry;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002094 }
Ingo Molnare2970f22006-06-27 02:54:47 -07002095 if (curval != *cmpval) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002096 ret = -EAGAIN;
2097 goto out_unlock;
2098 }
2099 }
2100
Darren Hart52400ba2009-04-03 13:40:49 -07002101 if (requeue_pi && (task_count - nr_wake < nr_requeue)) {
Thomas Gleixner3ef240e2019-11-06 22:55:46 +01002102 struct task_struct *exiting = NULL;
2103
Darren Hartbab5bc92009-04-07 23:23:50 -07002104 /*
2105 * Attempt to acquire uaddr2 and wake the top waiter. If we
2106 * intend to requeue waiters, force setting the FUTEX_WAITERS
2107 * bit. We force this here where we are able to easily handle
2108 * faults rather in the requeue loop below.
2109 */
Darren Hart52400ba2009-04-03 13:40:49 -07002110 ret = futex_proxy_trylock_atomic(uaddr2, hb1, hb2, &key1,
Thomas Gleixner3ef240e2019-11-06 22:55:46 +01002111 &key2, &pi_state,
2112 &exiting, nr_requeue);
Darren Hart52400ba2009-04-03 13:40:49 -07002113
2114 /*
2115 * At this point the top_waiter has either taken uaddr2 or is
2116 * waiting on it. If the former, then the pi_state will not
2117 * exist yet, look it up one more time to ensure we have a
Thomas Gleixner866293e2014-05-12 20:45:34 +00002118 * reference to it. If the lock was taken, ret contains the
2119 * vpid of the top waiter task.
Thomas Gleixnerecb38b72015-12-19 20:07:39 +00002120 * If the lock was not taken, we have pi_state and an initial
2121 * refcount on it. In case of an error we have nothing.
Darren Hart52400ba2009-04-03 13:40:49 -07002122 */
Thomas Gleixner866293e2014-05-12 20:45:34 +00002123 if (ret > 0) {
Darren Hart52400ba2009-04-03 13:40:49 -07002124 WARN_ON(pi_state);
Darren Hart89061d32009-10-15 15:30:48 -07002125 drop_count++;
Darren Hart52400ba2009-04-03 13:40:49 -07002126 task_count++;
Thomas Gleixner866293e2014-05-12 20:45:34 +00002127 /*
Thomas Gleixnerecb38b72015-12-19 20:07:39 +00002128 * If we acquired the lock, then the user space value
2129 * of uaddr2 should be vpid. It cannot be changed by
2130 * the top waiter as it is blocked on hb2 lock if it
2131 * tries to do so. If something fiddled with it behind
2132 * our back the pi state lookup might unearth it. So
2133 * we rather use the known value than rereading and
2134 * handing potential crap to lookup_pi_state.
2135 *
2136 * If that call succeeds then we have pi_state and an
2137 * initial refcount on it.
Thomas Gleixner866293e2014-05-12 20:45:34 +00002138 */
Thomas Gleixner3ef240e2019-11-06 22:55:46 +01002139 ret = lookup_pi_state(uaddr2, ret, hb2, &key2,
2140 &pi_state, &exiting);
Darren Hart52400ba2009-04-03 13:40:49 -07002141 }
2142
2143 switch (ret) {
2144 case 0:
Thomas Gleixnerecb38b72015-12-19 20:07:39 +00002145 /* We hold a reference on the pi state. */
Darren Hart52400ba2009-04-03 13:40:49 -07002146 break;
Thomas Gleixner4959f2d2015-12-19 20:07:40 +00002147
2148 /* If the above failed, then pi_state is NULL */
Darren Hart52400ba2009-04-03 13:40:49 -07002149 case -EFAULT:
2150 double_unlock_hb(hb1, hb2);
Linus Torvalds69cd9eb2014-04-08 15:30:07 -07002151 hb_waiters_dec(hb2);
Thomas Gleixnerae791a22010-11-10 13:30:36 +01002152 put_futex_key(&key2);
2153 put_futex_key(&key1);
Thomas Gleixnerd0725992009-06-11 23:15:43 +02002154 ret = fault_in_user_writeable(uaddr2);
Darren Hart52400ba2009-04-03 13:40:49 -07002155 if (!ret)
2156 goto retry;
2157 goto out;
Thomas Gleixnerac31c7f2019-11-06 22:55:45 +01002158 case -EBUSY:
Darren Hart52400ba2009-04-03 13:40:49 -07002159 case -EAGAIN:
Thomas Gleixneraf54d6a2014-06-11 20:45:41 +00002160 /*
2161 * Two reasons for this:
Thomas Gleixnerac31c7f2019-11-06 22:55:45 +01002162 * - EBUSY: Owner is exiting and we just wait for the
Thomas Gleixneraf54d6a2014-06-11 20:45:41 +00002163 * exit to complete.
Thomas Gleixnerac31c7f2019-11-06 22:55:45 +01002164 * - EAGAIN: The user space value changed.
Thomas Gleixneraf54d6a2014-06-11 20:45:41 +00002165 */
Darren Hart52400ba2009-04-03 13:40:49 -07002166 double_unlock_hb(hb1, hb2);
Linus Torvalds69cd9eb2014-04-08 15:30:07 -07002167 hb_waiters_dec(hb2);
Thomas Gleixnerae791a22010-11-10 13:30:36 +01002168 put_futex_key(&key2);
2169 put_futex_key(&key1);
Thomas Gleixner3ef240e2019-11-06 22:55:46 +01002170 /*
2171 * Handle the case where the owner is in the middle of
2172 * exiting. Wait for the exit to complete otherwise
2173 * this task might loop forever, aka. live lock.
2174 */
2175 wait_for_owner_exiting(ret, exiting);
Darren Hart52400ba2009-04-03 13:40:49 -07002176 cond_resched();
2177 goto retry;
2178 default:
2179 goto out_unlock;
2180 }
2181 }
2182
Jason Low0d00c7b2014-01-12 15:31:22 -08002183 plist_for_each_entry_safe(this, next, &hb1->chain, list) {
Darren Hart52400ba2009-04-03 13:40:49 -07002184 if (task_count - nr_wake >= nr_requeue)
2185 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002186
Darren Hart52400ba2009-04-03 13:40:49 -07002187 if (!match_futex(&this->key, &key1))
2188 continue;
2189
Darren Hart392741e2009-08-07 15:20:48 -07002190 /*
2191 * FUTEX_WAIT_REQEUE_PI and FUTEX_CMP_REQUEUE_PI should always
2192 * be paired with each other and no other futex ops.
Darren Hartaa109902012-11-26 16:29:56 -08002193 *
2194 * We should never be requeueing a futex_q with a pi_state,
2195 * which is awaiting a futex_unlock_pi().
Darren Hart392741e2009-08-07 15:20:48 -07002196 */
2197 if ((requeue_pi && !this->rt_waiter) ||
Darren Hartaa109902012-11-26 16:29:56 -08002198 (!requeue_pi && this->rt_waiter) ||
2199 this->pi_state) {
Darren Hart392741e2009-08-07 15:20:48 -07002200 ret = -EINVAL;
2201 break;
2202 }
Darren Hart52400ba2009-04-03 13:40:49 -07002203
2204 /*
2205 * Wake nr_wake waiters. For requeue_pi, if we acquired the
2206 * lock, we already woke the top_waiter. If not, it will be
2207 * woken by futex_unlock_pi().
2208 */
2209 if (++task_count <= nr_wake && !requeue_pi) {
Davidlohr Bueso1d0dcb32015-05-01 08:27:51 -07002210 mark_wake_futex(&wake_q, this);
Darren Hart52400ba2009-04-03 13:40:49 -07002211 continue;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002212 }
Darren Hart52400ba2009-04-03 13:40:49 -07002213
Darren Hart84bc4af2009-08-13 17:36:53 -07002214 /* Ensure we requeue to the expected futex for requeue_pi. */
2215 if (requeue_pi && !match_futex(this->requeue_pi_key, &key2)) {
2216 ret = -EINVAL;
2217 break;
2218 }
2219
Darren Hart52400ba2009-04-03 13:40:49 -07002220 /*
2221 * Requeue nr_requeue waiters and possibly one more in the case
2222 * of requeue_pi if we couldn't acquire the lock atomically.
2223 */
2224 if (requeue_pi) {
Thomas Gleixnerecb38b72015-12-19 20:07:39 +00002225 /*
2226 * Prepare the waiter to take the rt_mutex. Take a
2227 * refcount on the pi_state and store the pointer in
2228 * the futex_q object of the waiter.
2229 */
Peter Zijlstrabf92cf32017-03-22 11:35:53 +01002230 get_pi_state(pi_state);
Darren Hart52400ba2009-04-03 13:40:49 -07002231 this->pi_state = pi_state;
2232 ret = rt_mutex_start_proxy_lock(&pi_state->pi_mutex,
2233 this->rt_waiter,
Thomas Gleixnerc051b212014-05-22 03:25:50 +00002234 this->task);
Darren Hart52400ba2009-04-03 13:40:49 -07002235 if (ret == 1) {
Thomas Gleixnerecb38b72015-12-19 20:07:39 +00002236 /*
2237 * We got the lock. We do neither drop the
2238 * refcount on pi_state nor clear
2239 * this->pi_state because the waiter needs the
2240 * pi_state for cleaning up the user space
2241 * value. It will drop the refcount after
2242 * doing so.
2243 */
Darren Hartbeda2c72009-08-09 15:34:39 -07002244 requeue_pi_wake_futex(this, &key2, hb2);
Darren Hart89061d32009-10-15 15:30:48 -07002245 drop_count++;
Darren Hart52400ba2009-04-03 13:40:49 -07002246 continue;
2247 } else if (ret) {
Thomas Gleixnerecb38b72015-12-19 20:07:39 +00002248 /*
2249 * rt_mutex_start_proxy_lock() detected a
2250 * potential deadlock when we tried to queue
2251 * that waiter. Drop the pi_state reference
2252 * which we took above and remove the pointer
2253 * to the state from the waiters futex_q
2254 * object.
2255 */
Darren Hart52400ba2009-04-03 13:40:49 -07002256 this->pi_state = NULL;
Thomas Gleixner29e9ee52015-12-19 20:07:39 +00002257 put_pi_state(pi_state);
Thomas Gleixner885c2cb2015-12-19 20:07:41 +00002258 /*
2259 * We stop queueing more waiters and let user
2260 * space deal with the mess.
2261 */
2262 break;
Darren Hart52400ba2009-04-03 13:40:49 -07002263 }
2264 }
2265 requeue_futex(this, hb1, hb2, &key2);
2266 drop_count++;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002267 }
2268
Thomas Gleixnerecb38b72015-12-19 20:07:39 +00002269 /*
2270 * We took an extra initial reference to the pi_state either
2271 * in futex_proxy_trylock_atomic() or in lookup_pi_state(). We
2272 * need to drop it here again.
2273 */
Thomas Gleixner29e9ee52015-12-19 20:07:39 +00002274 put_pi_state(pi_state);
Thomas Gleixner885c2cb2015-12-19 20:07:41 +00002275
2276out_unlock:
Darren Hart5eb3dc62009-03-12 00:55:52 -07002277 double_unlock_hb(hb1, hb2);
Davidlohr Bueso1d0dcb32015-05-01 08:27:51 -07002278 wake_up_q(&wake_q);
Linus Torvalds69cd9eb2014-04-08 15:30:07 -07002279 hb_waiters_dec(hb2);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002280
Darren Hartcd84a422009-04-02 14:19:38 -07002281 /*
2282 * drop_futex_key_refs() must be called outside the spinlocks. During
2283 * the requeue we moved futex_q's from the hash bucket at key1 to the
2284 * one at key2 and updated their key pointer. We no longer need to
2285 * hold the references to key1.
2286 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07002287 while (--drop_count >= 0)
Rusty Russell9adef58b2007-05-08 00:26:42 -07002288 drop_futex_key_refs(&key1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002289
Darren Hart42d35d42008-12-29 15:49:53 -08002290out_put_keys:
Thomas Gleixnerae791a22010-11-10 13:30:36 +01002291 put_futex_key(&key2);
Darren Hart42d35d42008-12-29 15:49:53 -08002292out_put_key1:
Thomas Gleixnerae791a22010-11-10 13:30:36 +01002293 put_futex_key(&key1);
Darren Hart42d35d42008-12-29 15:49:53 -08002294out:
Darren Hart52400ba2009-04-03 13:40:49 -07002295 return ret ? ret : task_count;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002296}
2297
2298/* The key must be already stored in q->key. */
Eric Sesterhenn82af7ac2008-01-25 10:40:46 +01002299static inline struct futex_hash_bucket *queue_lock(struct futex_q *q)
Namhyung Kim15e408c2010-09-14 21:43:48 +09002300 __acquires(&hb->lock)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002301{
Ingo Molnare2970f22006-06-27 02:54:47 -07002302 struct futex_hash_bucket *hb;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002303
Ingo Molnare2970f22006-06-27 02:54:47 -07002304 hb = hash_futex(&q->key);
Linus Torvalds11d46162014-03-20 22:11:17 -07002305
2306 /*
2307 * Increment the counter before taking the lock so that
2308 * a potential waker won't miss a to-be-slept task that is
2309 * waiting for the spinlock. This is safe as all queue_lock()
2310 * users end up calling queue_me(). Similarly, for housekeeping,
2311 * decrement the counter at queue_unlock() when some error has
2312 * occurred and we don't end up adding the task to the list.
2313 */
Davidlohr Bueso6f568eb2019-02-06 10:56:02 -08002314 hb_waiters_inc(hb); /* implies smp_mb(); (A) */
Linus Torvalds11d46162014-03-20 22:11:17 -07002315
Ingo Molnare2970f22006-06-27 02:54:47 -07002316 q->lock_ptr = &hb->lock;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002317
Davidlohr Bueso6f568eb2019-02-06 10:56:02 -08002318 spin_lock(&hb->lock);
Ingo Molnare2970f22006-06-27 02:54:47 -07002319 return hb;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002320}
2321
Darren Hartd40d65c2009-09-21 22:30:15 -07002322static inline void
Jason Low0d00c7b2014-01-12 15:31:22 -08002323queue_unlock(struct futex_hash_bucket *hb)
Namhyung Kim15e408c2010-09-14 21:43:48 +09002324 __releases(&hb->lock)
Darren Hartd40d65c2009-09-21 22:30:15 -07002325{
2326 spin_unlock(&hb->lock);
Linus Torvalds11d46162014-03-20 22:11:17 -07002327 hb_waiters_dec(hb);
Darren Hartd40d65c2009-09-21 22:30:15 -07002328}
2329
Peter Zijlstracfafcd12017-03-22 11:35:58 +01002330static inline void __queue_me(struct futex_q *q, struct futex_hash_bucket *hb)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002331{
Pierre Peifferec92d082007-05-09 02:35:00 -07002332 int prio;
2333
2334 /*
2335 * The priority used to register this element is
2336 * - either the real thread-priority for the real-time threads
2337 * (i.e. threads with a priority lower than MAX_RT_PRIO)
2338 * - or MAX_RT_PRIO for non-RT threads.
2339 * Thus, all RT-threads are woken first in priority order, and
2340 * the others are woken last, in FIFO order.
2341 */
2342 prio = min(current->normal_prio, MAX_RT_PRIO);
2343
2344 plist_node_init(&q->list, prio);
Pierre Peifferec92d082007-05-09 02:35:00 -07002345 plist_add(&q->list, &hb->chain);
Ingo Molnarc87e2832006-06-27 02:54:58 -07002346 q->task = current;
Peter Zijlstracfafcd12017-03-22 11:35:58 +01002347}
2348
2349/**
2350 * queue_me() - Enqueue the futex_q on the futex_hash_bucket
2351 * @q: The futex_q to enqueue
2352 * @hb: The destination hash bucket
2353 *
2354 * The hb->lock must be held by the caller, and is released here. A call to
2355 * queue_me() is typically paired with exactly one call to unqueue_me(). The
2356 * exceptions involve the PI related operations, which may use unqueue_me_pi()
2357 * or nothing if the unqueue is done as part of the wake process and the unqueue
2358 * state is implicit in the state of woken task (see futex_wait_requeue_pi() for
2359 * an example).
2360 */
2361static inline void queue_me(struct futex_q *q, struct futex_hash_bucket *hb)
2362 __releases(&hb->lock)
2363{
2364 __queue_me(q, hb);
Ingo Molnare2970f22006-06-27 02:54:47 -07002365 spin_unlock(&hb->lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002366}
2367
Darren Hartd40d65c2009-09-21 22:30:15 -07002368/**
2369 * unqueue_me() - Remove the futex_q from its futex_hash_bucket
2370 * @q: The futex_q to unqueue
2371 *
2372 * The q->lock_ptr must not be held by the caller. A call to unqueue_me() must
2373 * be paired with exactly one earlier call to queue_me().
2374 *
Randy Dunlap6c23cbb2013-03-05 10:00:24 -08002375 * Return:
Mauro Carvalho Chehab7b4ff1a2017-05-11 10:17:45 -03002376 * - 1 - if the futex_q was still queued (and we removed unqueued it);
2377 * - 0 - if the futex_q was already removed by the waking thread
Linus Torvalds1da177e2005-04-16 15:20:36 -07002378 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07002379static int unqueue_me(struct futex_q *q)
2380{
Linus Torvalds1da177e2005-04-16 15:20:36 -07002381 spinlock_t *lock_ptr;
Ingo Molnare2970f22006-06-27 02:54:47 -07002382 int ret = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002383
2384 /* In the common case we don't take the spinlock, which is nice. */
Darren Hart42d35d42008-12-29 15:49:53 -08002385retry:
Jianyu Zhan29b75eb2016-03-07 09:32:24 +08002386 /*
2387 * q->lock_ptr can change between this read and the following spin_lock.
2388 * Use READ_ONCE to forbid the compiler from reloading q->lock_ptr and
2389 * optimizing lock_ptr out of the logic below.
2390 */
2391 lock_ptr = READ_ONCE(q->lock_ptr);
Stephen Hemmingerc80544d2007-10-18 03:07:05 -07002392 if (lock_ptr != NULL) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002393 spin_lock(lock_ptr);
2394 /*
2395 * q->lock_ptr can change between reading it and
2396 * spin_lock(), causing us to take the wrong lock. This
2397 * corrects the race condition.
2398 *
2399 * Reasoning goes like this: if we have the wrong lock,
2400 * q->lock_ptr must have changed (maybe several times)
2401 * between reading it and the spin_lock(). It can
2402 * change again after the spin_lock() but only if it was
2403 * already changed before the spin_lock(). It cannot,
2404 * however, change back to the original value. Therefore
2405 * we can detect whether we acquired the correct lock.
2406 */
2407 if (unlikely(lock_ptr != q->lock_ptr)) {
2408 spin_unlock(lock_ptr);
2409 goto retry;
2410 }
Lai Jiangshan2e129782010-12-22 14:18:50 +08002411 __unqueue_futex(q);
Ingo Molnarc87e2832006-06-27 02:54:58 -07002412
2413 BUG_ON(q->pi_state);
2414
Linus Torvalds1da177e2005-04-16 15:20:36 -07002415 spin_unlock(lock_ptr);
2416 ret = 1;
2417 }
2418
Rusty Russell9adef58b2007-05-08 00:26:42 -07002419 drop_futex_key_refs(&q->key);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002420 return ret;
2421}
2422
Ingo Molnarc87e2832006-06-27 02:54:58 -07002423/*
2424 * PI futexes can not be requeued and must remove themself from the
Pierre Peifferd0aa7a72007-05-09 02:35:02 -07002425 * hash bucket. The hash bucket lock (i.e. lock_ptr) is held on entry
2426 * and dropped here.
Ingo Molnarc87e2832006-06-27 02:54:58 -07002427 */
Pierre Peifferd0aa7a72007-05-09 02:35:02 -07002428static void unqueue_me_pi(struct futex_q *q)
Namhyung Kim15e408c2010-09-14 21:43:48 +09002429 __releases(q->lock_ptr)
Ingo Molnarc87e2832006-06-27 02:54:58 -07002430{
Lai Jiangshan2e129782010-12-22 14:18:50 +08002431 __unqueue_futex(q);
Ingo Molnarc87e2832006-06-27 02:54:58 -07002432
2433 BUG_ON(!q->pi_state);
Thomas Gleixner29e9ee52015-12-19 20:07:39 +00002434 put_pi_state(q->pi_state);
Ingo Molnarc87e2832006-06-27 02:54:58 -07002435 q->pi_state = NULL;
2436
Pierre Peifferd0aa7a72007-05-09 02:35:02 -07002437 spin_unlock(q->lock_ptr);
Ingo Molnarc87e2832006-06-27 02:54:58 -07002438}
2439
Alexey Kuznetsov778e9a92007-06-08 13:47:00 -07002440static int fixup_pi_state_owner(u32 __user *uaddr, struct futex_q *q,
Peter Zijlstrac1e2f0ea2017-12-08 13:49:39 +01002441 struct task_struct *argowner)
Pierre Peifferd0aa7a72007-05-09 02:35:02 -07002442{
Pierre Peifferd0aa7a72007-05-09 02:35:02 -07002443 struct futex_pi_state *pi_state = q->pi_state;
Vitaliy Ivanov7cfdaf32011-07-07 15:10:31 +03002444 u32 uval, uninitialized_var(curval), newval;
Peter Zijlstrac1e2f0ea2017-12-08 13:49:39 +01002445 struct task_struct *oldowner, *newowner;
2446 u32 newtid;
Will Deacon6b4f4bc2019-02-28 11:58:08 +00002447 int ret, err = 0;
Pierre Peifferd0aa7a72007-05-09 02:35:02 -07002448
Peter Zijlstrac1e2f0ea2017-12-08 13:49:39 +01002449 lockdep_assert_held(q->lock_ptr);
2450
Peter Zijlstra734009e2017-03-22 11:35:52 +01002451 raw_spin_lock_irq(&pi_state->pi_mutex.wait_lock);
2452
2453 oldowner = pi_state->owner;
Thomas Gleixner1b7558e2008-06-23 11:21:58 +02002454
2455 /*
Peter Zijlstrac1e2f0ea2017-12-08 13:49:39 +01002456 * We are here because either:
Peter Zijlstra16ffa122017-03-22 11:35:55 +01002457 *
Peter Zijlstrac1e2f0ea2017-12-08 13:49:39 +01002458 * - we stole the lock and pi_state->owner needs updating to reflect
2459 * that (@argowner == current),
2460 *
2461 * or:
2462 *
2463 * - someone stole our lock and we need to fix things to point to the
2464 * new owner (@argowner == NULL).
2465 *
2466 * Either way, we have to replace the TID in the user space variable.
Lai Jiangshan81612392011-01-14 17:09:41 +08002467 * This must be atomic as we have to preserve the owner died bit here.
Thomas Gleixner1b7558e2008-06-23 11:21:58 +02002468 *
Darren Hartb2d09942009-03-12 00:55:37 -07002469 * Note: We write the user space value _before_ changing the pi_state
2470 * because we can fault here. Imagine swapped out pages or a fork
2471 * that marked all the anonymous memory readonly for cow.
Thomas Gleixner1b7558e2008-06-23 11:21:58 +02002472 *
Peter Zijlstra734009e2017-03-22 11:35:52 +01002473 * Modifying pi_state _before_ the user space value would leave the
2474 * pi_state in an inconsistent state when we fault here, because we
2475 * need to drop the locks to handle the fault. This might be observed
2476 * in the PID check in lookup_pi_state.
Thomas Gleixner1b7558e2008-06-23 11:21:58 +02002477 */
2478retry:
Peter Zijlstrac1e2f0ea2017-12-08 13:49:39 +01002479 if (!argowner) {
2480 if (oldowner != current) {
2481 /*
2482 * We raced against a concurrent self; things are
2483 * already fixed up. Nothing to do.
2484 */
2485 ret = 0;
2486 goto out_unlock;
2487 }
2488
2489 if (__rt_mutex_futex_trylock(&pi_state->pi_mutex)) {
2490 /* We got the lock after all, nothing to fix. */
2491 ret = 0;
2492 goto out_unlock;
2493 }
2494
2495 /*
2496 * Since we just failed the trylock; there must be an owner.
2497 */
2498 newowner = rt_mutex_owner(&pi_state->pi_mutex);
2499 BUG_ON(!newowner);
2500 } else {
2501 WARN_ON_ONCE(argowner != current);
2502 if (oldowner == current) {
2503 /*
2504 * We raced against a concurrent self; things are
2505 * already fixed up. Nothing to do.
2506 */
2507 ret = 0;
2508 goto out_unlock;
2509 }
2510 newowner = argowner;
2511 }
2512
2513 newtid = task_pid_vnr(newowner) | FUTEX_WAITERS;
Peter Zijlstraa97cb0e2018-01-22 11:39:47 +01002514 /* Owner died? */
2515 if (!pi_state->owner)
2516 newtid |= FUTEX_OWNER_DIED;
Peter Zijlstrac1e2f0ea2017-12-08 13:49:39 +01002517
Will Deacon6b4f4bc2019-02-28 11:58:08 +00002518 err = get_futex_value_locked(&uval, uaddr);
2519 if (err)
2520 goto handle_err;
Thomas Gleixner1b7558e2008-06-23 11:21:58 +02002521
Peter Zijlstra16ffa122017-03-22 11:35:55 +01002522 for (;;) {
Thomas Gleixner1b7558e2008-06-23 11:21:58 +02002523 newval = (uval & FUTEX_OWNER_DIED) | newtid;
2524
Will Deacon6b4f4bc2019-02-28 11:58:08 +00002525 err = cmpxchg_futex_value_locked(&curval, uaddr, uval, newval);
2526 if (err)
2527 goto handle_err;
2528
Thomas Gleixner1b7558e2008-06-23 11:21:58 +02002529 if (curval == uval)
2530 break;
2531 uval = curval;
2532 }
2533
2534 /*
2535 * We fixed up user space. Now we need to fix the pi_state
2536 * itself.
2537 */
Pierre Peifferd0aa7a72007-05-09 02:35:02 -07002538 if (pi_state->owner != NULL) {
Peter Zijlstra734009e2017-03-22 11:35:52 +01002539 raw_spin_lock(&pi_state->owner->pi_lock);
Pierre Peifferd0aa7a72007-05-09 02:35:02 -07002540 WARN_ON(list_empty(&pi_state->list));
2541 list_del_init(&pi_state->list);
Peter Zijlstra734009e2017-03-22 11:35:52 +01002542 raw_spin_unlock(&pi_state->owner->pi_lock);
Thomas Gleixner1b7558e2008-06-23 11:21:58 +02002543 }
Pierre Peifferd0aa7a72007-05-09 02:35:02 -07002544
Thomas Gleixnercdf71a12008-01-08 19:47:38 +01002545 pi_state->owner = newowner;
Pierre Peifferd0aa7a72007-05-09 02:35:02 -07002546
Peter Zijlstra734009e2017-03-22 11:35:52 +01002547 raw_spin_lock(&newowner->pi_lock);
Pierre Peifferd0aa7a72007-05-09 02:35:02 -07002548 WARN_ON(!list_empty(&pi_state->list));
Thomas Gleixnercdf71a12008-01-08 19:47:38 +01002549 list_add(&pi_state->list, &newowner->pi_state_list);
Peter Zijlstra734009e2017-03-22 11:35:52 +01002550 raw_spin_unlock(&newowner->pi_lock);
2551 raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
2552
Thomas Gleixner1b7558e2008-06-23 11:21:58 +02002553 return 0;
Pierre Peifferd0aa7a72007-05-09 02:35:02 -07002554
Pierre Peifferd0aa7a72007-05-09 02:35:02 -07002555 /*
Will Deacon6b4f4bc2019-02-28 11:58:08 +00002556 * In order to reschedule or handle a page fault, we need to drop the
2557 * locks here. In the case of a fault, this gives the other task
2558 * (either the highest priority waiter itself or the task which stole
2559 * the rtmutex) the chance to try the fixup of the pi_state. So once we
2560 * are back from handling the fault we need to check the pi_state after
2561 * reacquiring the locks and before trying to do another fixup. When
2562 * the fixup has been done already we simply return.
Peter Zijlstra734009e2017-03-22 11:35:52 +01002563 *
2564 * Note: we hold both hb->lock and pi_mutex->wait_lock. We can safely
2565 * drop hb->lock since the caller owns the hb -> futex_q relation.
2566 * Dropping the pi_mutex->wait_lock requires the state revalidate.
Pierre Peifferd0aa7a72007-05-09 02:35:02 -07002567 */
Will Deacon6b4f4bc2019-02-28 11:58:08 +00002568handle_err:
Peter Zijlstra734009e2017-03-22 11:35:52 +01002569 raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
Thomas Gleixner1b7558e2008-06-23 11:21:58 +02002570 spin_unlock(q->lock_ptr);
Alexey Kuznetsov778e9a92007-06-08 13:47:00 -07002571
Will Deacon6b4f4bc2019-02-28 11:58:08 +00002572 switch (err) {
2573 case -EFAULT:
2574 ret = fault_in_user_writeable(uaddr);
2575 break;
2576
2577 case -EAGAIN:
2578 cond_resched();
2579 ret = 0;
2580 break;
2581
2582 default:
2583 WARN_ON_ONCE(1);
2584 ret = err;
2585 break;
2586 }
Alexey Kuznetsov778e9a92007-06-08 13:47:00 -07002587
Thomas Gleixner1b7558e2008-06-23 11:21:58 +02002588 spin_lock(q->lock_ptr);
Peter Zijlstra734009e2017-03-22 11:35:52 +01002589 raw_spin_lock_irq(&pi_state->pi_mutex.wait_lock);
Alexey Kuznetsov778e9a92007-06-08 13:47:00 -07002590
Thomas Gleixner1b7558e2008-06-23 11:21:58 +02002591 /*
2592 * Check if someone else fixed it for us:
2593 */
Peter Zijlstra734009e2017-03-22 11:35:52 +01002594 if (pi_state->owner != oldowner) {
2595 ret = 0;
2596 goto out_unlock;
2597 }
Thomas Gleixner1b7558e2008-06-23 11:21:58 +02002598
2599 if (ret)
Peter Zijlstra734009e2017-03-22 11:35:52 +01002600 goto out_unlock;
Thomas Gleixner1b7558e2008-06-23 11:21:58 +02002601
2602 goto retry;
Peter Zijlstra734009e2017-03-22 11:35:52 +01002603
2604out_unlock:
2605 raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
2606 return ret;
Pierre Peifferd0aa7a72007-05-09 02:35:02 -07002607}
2608
Nick Piggin72c1bbf2007-05-08 00:26:43 -07002609static long futex_wait_restart(struct restart_block *restart);
Thomas Gleixner36cf3b52007-07-15 23:41:20 -07002610
Darren Hartca5f9522009-04-03 13:39:33 -07002611/**
Darren Hartdd973992009-04-03 13:40:02 -07002612 * fixup_owner() - Post lock pi_state and corner case management
2613 * @uaddr: user address of the futex
Darren Hartdd973992009-04-03 13:40:02 -07002614 * @q: futex_q (contains pi_state and access to the rt_mutex)
2615 * @locked: if the attempt to take the rt_mutex succeeded (1) or not (0)
2616 *
2617 * After attempting to lock an rt_mutex, this function is called to cleanup
2618 * the pi_state owner as well as handle race conditions that may allow us to
2619 * acquire the lock. Must be called with the hb lock held.
2620 *
Randy Dunlap6c23cbb2013-03-05 10:00:24 -08002621 * Return:
Mauro Carvalho Chehab7b4ff1a2017-05-11 10:17:45 -03002622 * - 1 - success, lock taken;
2623 * - 0 - success, lock not taken;
2624 * - <0 - on error (-EFAULT)
Darren Hartdd973992009-04-03 13:40:02 -07002625 */
Thomas Gleixnerae791a22010-11-10 13:30:36 +01002626static int fixup_owner(u32 __user *uaddr, struct futex_q *q, int locked)
Darren Hartdd973992009-04-03 13:40:02 -07002627{
Darren Hartdd973992009-04-03 13:40:02 -07002628 int ret = 0;
2629
2630 if (locked) {
2631 /*
2632 * Got the lock. We might not be the anticipated owner if we
2633 * did a lock-steal - fix up the PI-state in that case:
Peter Zijlstra16ffa122017-03-22 11:35:55 +01002634 *
Peter Zijlstrac1e2f0ea2017-12-08 13:49:39 +01002635 * Speculative pi_state->owner read (we don't hold wait_lock);
2636 * since we own the lock pi_state->owner == current is the
2637 * stable state, anything else needs more attention.
Darren Hartdd973992009-04-03 13:40:02 -07002638 */
2639 if (q->pi_state->owner != current)
Thomas Gleixnerae791a22010-11-10 13:30:36 +01002640 ret = fixup_pi_state_owner(uaddr, q, current);
Darren Hartdd973992009-04-03 13:40:02 -07002641 goto out;
2642 }
2643
2644 /*
Peter Zijlstrac1e2f0ea2017-12-08 13:49:39 +01002645 * If we didn't get the lock; check if anybody stole it from us. In
2646 * that case, we need to fix up the uval to point to them instead of
2647 * us, otherwise bad things happen. [10]
2648 *
2649 * Another speculative read; pi_state->owner == current is unstable
2650 * but needs our attention.
2651 */
2652 if (q->pi_state->owner == current) {
2653 ret = fixup_pi_state_owner(uaddr, q, NULL);
2654 goto out;
2655 }
2656
2657 /*
Darren Hartdd973992009-04-03 13:40:02 -07002658 * Paranoia check. If we did not take the lock, then we should not be
Lai Jiangshan81612392011-01-14 17:09:41 +08002659 * the owner of the rt_mutex.
Darren Hartdd973992009-04-03 13:40:02 -07002660 */
Peter Zijlstra73d786b2017-03-22 11:35:54 +01002661 if (rt_mutex_owner(&q->pi_state->pi_mutex) == current) {
Darren Hartdd973992009-04-03 13:40:02 -07002662 printk(KERN_ERR "fixup_owner: ret = %d pi-mutex: %p "
2663 "pi-state %p\n", ret,
2664 q->pi_state->pi_mutex.owner,
2665 q->pi_state->owner);
Peter Zijlstra73d786b2017-03-22 11:35:54 +01002666 }
Darren Hartdd973992009-04-03 13:40:02 -07002667
2668out:
2669 return ret ? ret : locked;
2670}
2671
2672/**
Darren Hartca5f9522009-04-03 13:39:33 -07002673 * futex_wait_queue_me() - queue_me() and wait for wakeup, timeout, or signal
2674 * @hb: the futex hash bucket, must be locked by the caller
2675 * @q: the futex_q to queue up on
2676 * @timeout: the prepared hrtimer_sleeper, or null for no timeout
Darren Hartca5f9522009-04-03 13:39:33 -07002677 */
2678static void futex_wait_queue_me(struct futex_hash_bucket *hb, struct futex_q *q,
Thomas Gleixnerf1a11e02009-05-05 19:21:40 +02002679 struct hrtimer_sleeper *timeout)
Darren Hartca5f9522009-04-03 13:39:33 -07002680{
Darren Hart9beba3c2009-09-24 11:54:47 -07002681 /*
2682 * The task state is guaranteed to be set before another task can
Peter Zijlstrab92b8b32015-05-12 10:51:55 +02002683 * wake it. set_current_state() is implemented using smp_store_mb() and
Darren Hart9beba3c2009-09-24 11:54:47 -07002684 * queue_me() calls spin_unlock() upon completion, both serializing
2685 * access to the hash list and forcing another memory barrier.
2686 */
Thomas Gleixnerf1a11e02009-05-05 19:21:40 +02002687 set_current_state(TASK_INTERRUPTIBLE);
Darren Hart0729e192009-09-21 22:30:38 -07002688 queue_me(q, hb);
Darren Hartca5f9522009-04-03 13:39:33 -07002689
2690 /* Arm the timer */
Thomas Gleixner2e4b0d32015-04-14 21:09:13 +00002691 if (timeout)
Thomas Gleixner9dd88132019-07-30 21:16:55 +02002692 hrtimer_sleeper_start_expires(timeout, HRTIMER_MODE_ABS);
Darren Hartca5f9522009-04-03 13:39:33 -07002693
2694 /*
Darren Hart0729e192009-09-21 22:30:38 -07002695 * If we have been removed from the hash list, then another task
2696 * has tried to wake us, and we can skip the call to schedule().
Darren Hartca5f9522009-04-03 13:39:33 -07002697 */
2698 if (likely(!plist_node_empty(&q->list))) {
2699 /*
2700 * If the timer has already expired, current will already be
2701 * flagged for rescheduling. Only call schedule if there
2702 * is no timeout, or if it has yet to expire.
2703 */
2704 if (!timeout || timeout->task)
Colin Cross88c80042013-05-01 18:35:05 -07002705 freezable_schedule();
Darren Hartca5f9522009-04-03 13:39:33 -07002706 }
2707 __set_current_state(TASK_RUNNING);
2708}
2709
Darren Hartf8010732009-04-03 13:40:40 -07002710/**
2711 * futex_wait_setup() - Prepare to wait on a futex
2712 * @uaddr: the futex userspace address
2713 * @val: the expected value
Darren Hartb41277d2010-11-08 13:10:09 -08002714 * @flags: futex flags (FLAGS_SHARED, etc.)
Darren Hartf8010732009-04-03 13:40:40 -07002715 * @q: the associated futex_q
2716 * @hb: storage for hash_bucket pointer to be returned to caller
2717 *
2718 * Setup the futex_q and locate the hash_bucket. Get the futex value and
2719 * compare it with the expected value. Handle atomic faults internally.
2720 * Return with the hb lock held and a q.key reference on success, and unlocked
2721 * with no q.key reference on failure.
2722 *
Randy Dunlap6c23cbb2013-03-05 10:00:24 -08002723 * Return:
Mauro Carvalho Chehab7b4ff1a2017-05-11 10:17:45 -03002724 * - 0 - uaddr contains val and hb has been locked;
2725 * - <1 - -EFAULT or -EWOULDBLOCK (uaddr does not contain val) and hb is unlocked
Darren Hartf8010732009-04-03 13:40:40 -07002726 */
Darren Hartb41277d2010-11-08 13:10:09 -08002727static int futex_wait_setup(u32 __user *uaddr, u32 val, unsigned int flags,
Darren Hartf8010732009-04-03 13:40:40 -07002728 struct futex_q *q, struct futex_hash_bucket **hb)
2729{
2730 u32 uval;
2731 int ret;
2732
2733 /*
2734 * Access the page AFTER the hash-bucket is locked.
2735 * Order is important:
2736 *
2737 * Userspace waiter: val = var; if (cond(val)) futex_wait(&var, val);
2738 * Userspace waker: if (cond(var)) { var = new; futex_wake(&var); }
2739 *
2740 * The basic logical guarantee of a futex is that it blocks ONLY
2741 * if cond(var) is known to be true at the time of blocking, for
Michel Lespinasse8fe8f542011-03-06 18:07:50 -08002742 * any cond. If we locked the hash-bucket after testing *uaddr, that
2743 * would open a race condition where we could block indefinitely with
Darren Hartf8010732009-04-03 13:40:40 -07002744 * cond(var) false, which would violate the guarantee.
2745 *
Michel Lespinasse8fe8f542011-03-06 18:07:50 -08002746 * On the other hand, we insert q and release the hash-bucket only
2747 * after testing *uaddr. This guarantees that futex_wait() will NOT
2748 * absorb a wakeup if *uaddr does not match the desired values
2749 * while the syscall executes.
Darren Hartf8010732009-04-03 13:40:40 -07002750 */
2751retry:
Linus Torvalds96d4f262019-01-03 18:57:57 -08002752 ret = get_futex_key(uaddr, flags & FLAGS_SHARED, &q->key, FUTEX_READ);
Darren Hartf8010732009-04-03 13:40:40 -07002753 if (unlikely(ret != 0))
Darren Harta5a2a0c2009-04-10 09:50:05 -07002754 return ret;
Darren Hartf8010732009-04-03 13:40:40 -07002755
2756retry_private:
2757 *hb = queue_lock(q);
2758
2759 ret = get_futex_value_locked(&uval, uaddr);
2760
2761 if (ret) {
Jason Low0d00c7b2014-01-12 15:31:22 -08002762 queue_unlock(*hb);
Darren Hartf8010732009-04-03 13:40:40 -07002763
2764 ret = get_user(uval, uaddr);
2765 if (ret)
2766 goto out;
2767
Darren Hartb41277d2010-11-08 13:10:09 -08002768 if (!(flags & FLAGS_SHARED))
Darren Hartf8010732009-04-03 13:40:40 -07002769 goto retry_private;
2770
Thomas Gleixnerae791a22010-11-10 13:30:36 +01002771 put_futex_key(&q->key);
Darren Hartf8010732009-04-03 13:40:40 -07002772 goto retry;
2773 }
2774
2775 if (uval != val) {
Jason Low0d00c7b2014-01-12 15:31:22 -08002776 queue_unlock(*hb);
Darren Hartf8010732009-04-03 13:40:40 -07002777 ret = -EWOULDBLOCK;
2778 }
2779
2780out:
2781 if (ret)
Thomas Gleixnerae791a22010-11-10 13:30:36 +01002782 put_futex_key(&q->key);
Darren Hartf8010732009-04-03 13:40:40 -07002783 return ret;
2784}
2785
Darren Hartb41277d2010-11-08 13:10:09 -08002786static int futex_wait(u32 __user *uaddr, unsigned int flags, u32 val,
2787 ktime_t *abs_time, u32 bitset)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002788{
Waiman Long5ca584d2019-05-28 12:03:45 -04002789 struct hrtimer_sleeper timeout, *to;
Peter Zijlstra2fff78c2009-02-11 18:10:10 +01002790 struct restart_block *restart;
Ingo Molnare2970f22006-06-27 02:54:47 -07002791 struct futex_hash_bucket *hb;
Darren Hart5bdb05f2010-11-08 13:40:28 -08002792 struct futex_q q = futex_q_init;
Ingo Molnare2970f22006-06-27 02:54:47 -07002793 int ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002794
Thomas Gleixnercd6899852008-02-01 17:45:14 +01002795 if (!bitset)
2796 return -EINVAL;
Thomas Gleixnercd6899852008-02-01 17:45:14 +01002797 q.bitset = bitset;
Darren Hartca5f9522009-04-03 13:39:33 -07002798
Waiman Long5ca584d2019-05-28 12:03:45 -04002799 to = futex_setup_timer(abs_time, &timeout, flags,
2800 current->timer_slack_ns);
Thomas Gleixnerd58e6572009-10-13 20:40:43 +02002801retry:
Darren Hart7ada8762010-10-17 08:35:04 -07002802 /*
2803 * Prepare to wait on uaddr. On success, holds hb lock and increments
2804 * q.key refs.
2805 */
Darren Hartb41277d2010-11-08 13:10:09 -08002806 ret = futex_wait_setup(uaddr, val, flags, &q, &hb);
Darren Hartf8010732009-04-03 13:40:40 -07002807 if (ret)
Darren Hart42d35d42008-12-29 15:49:53 -08002808 goto out;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002809
Darren Hartca5f9522009-04-03 13:39:33 -07002810 /* queue_me and wait for wakeup, timeout, or a signal. */
Thomas Gleixnerf1a11e02009-05-05 19:21:40 +02002811 futex_wait_queue_me(hb, &q, to);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002812
2813 /* If we were woken (and unqueued), we succeeded, whatever. */
Peter Zijlstra2fff78c2009-02-11 18:10:10 +01002814 ret = 0;
Darren Hart7ada8762010-10-17 08:35:04 -07002815 /* unqueue_me() drops q.key ref */
Linus Torvalds1da177e2005-04-16 15:20:36 -07002816 if (!unqueue_me(&q))
Darren Hart7ada8762010-10-17 08:35:04 -07002817 goto out;
Peter Zijlstra2fff78c2009-02-11 18:10:10 +01002818 ret = -ETIMEDOUT;
Darren Hartca5f9522009-04-03 13:39:33 -07002819 if (to && !to->task)
Darren Hart7ada8762010-10-17 08:35:04 -07002820 goto out;
Nick Piggin72c1bbf2007-05-08 00:26:43 -07002821
Ingo Molnare2970f22006-06-27 02:54:47 -07002822 /*
Thomas Gleixnerd58e6572009-10-13 20:40:43 +02002823 * We expect signal_pending(current), but we might be the
2824 * victim of a spurious wakeup as well.
Ingo Molnare2970f22006-06-27 02:54:47 -07002825 */
Darren Hart7ada8762010-10-17 08:35:04 -07002826 if (!signal_pending(current))
Thomas Gleixnerd58e6572009-10-13 20:40:43 +02002827 goto retry;
Thomas Gleixnerd58e6572009-10-13 20:40:43 +02002828
Peter Zijlstra2fff78c2009-02-11 18:10:10 +01002829 ret = -ERESTARTSYS;
Pierre Peifferc19384b2007-05-09 02:35:02 -07002830 if (!abs_time)
Darren Hart7ada8762010-10-17 08:35:04 -07002831 goto out;
Steven Rostedtce6bd422007-12-05 15:46:09 +01002832
Andy Lutomirskif56141e2015-02-12 15:01:14 -08002833 restart = &current->restart_block;
Peter Zijlstra2fff78c2009-02-11 18:10:10 +01002834 restart->fn = futex_wait_restart;
Namhyung Kima3c74c52010-09-14 21:43:47 +09002835 restart->futex.uaddr = uaddr;
Peter Zijlstra2fff78c2009-02-11 18:10:10 +01002836 restart->futex.val = val;
Thomas Gleixner2456e852016-12-25 11:38:40 +01002837 restart->futex.time = *abs_time;
Peter Zijlstra2fff78c2009-02-11 18:10:10 +01002838 restart->futex.bitset = bitset;
Darren Hart0cd9c642011-04-14 15:41:57 -07002839 restart->futex.flags = flags | FLAGS_HAS_TIMEOUT;
Peter Zijlstra2fff78c2009-02-11 18:10:10 +01002840
2841 ret = -ERESTART_RESTARTBLOCK;
2842
Darren Hart42d35d42008-12-29 15:49:53 -08002843out:
Darren Hartca5f9522009-04-03 13:39:33 -07002844 if (to) {
2845 hrtimer_cancel(&to->timer);
2846 destroy_hrtimer_on_stack(&to->timer);
2847 }
Ingo Molnarc87e2832006-06-27 02:54:58 -07002848 return ret;
2849}
2850
Nick Piggin72c1bbf2007-05-08 00:26:43 -07002851
2852static long futex_wait_restart(struct restart_block *restart)
2853{
Namhyung Kima3c74c52010-09-14 21:43:47 +09002854 u32 __user *uaddr = restart->futex.uaddr;
Darren Harta72188d2009-04-03 13:40:22 -07002855 ktime_t t, *tp = NULL;
Nick Piggin72c1bbf2007-05-08 00:26:43 -07002856
Darren Harta72188d2009-04-03 13:40:22 -07002857 if (restart->futex.flags & FLAGS_HAS_TIMEOUT) {
Thomas Gleixner2456e852016-12-25 11:38:40 +01002858 t = restart->futex.time;
Darren Harta72188d2009-04-03 13:40:22 -07002859 tp = &t;
2860 }
Nick Piggin72c1bbf2007-05-08 00:26:43 -07002861 restart->fn = do_no_restart_syscall;
Darren Hartb41277d2010-11-08 13:10:09 -08002862
2863 return (long)futex_wait(uaddr, restart->futex.flags,
2864 restart->futex.val, tp, restart->futex.bitset);
Nick Piggin72c1bbf2007-05-08 00:26:43 -07002865}
2866
2867
Ingo Molnarc87e2832006-06-27 02:54:58 -07002868/*
2869 * Userspace tried a 0 -> TID atomic transition of the futex value
2870 * and failed. The kernel side here does the whole locking operation:
Davidlohr Bueso767f5092015-06-29 23:26:01 -07002871 * if there are waiters then it will block as a consequence of relying
2872 * on rt-mutexes, it does PI, etc. (Due to races the kernel might see
2873 * a 0 value of the futex too.).
2874 *
2875 * Also serves as futex trylock_pi()'ing, and due semantics.
Ingo Molnarc87e2832006-06-27 02:54:58 -07002876 */
Michael Kerrisk996636d2015-01-16 20:28:06 +01002877static int futex_lock_pi(u32 __user *uaddr, unsigned int flags,
Darren Hartb41277d2010-11-08 13:10:09 -08002878 ktime_t *time, int trylock)
Ingo Molnarc87e2832006-06-27 02:54:58 -07002879{
Waiman Long5ca584d2019-05-28 12:03:45 -04002880 struct hrtimer_sleeper timeout, *to;
Peter Zijlstra16ffa122017-03-22 11:35:55 +01002881 struct futex_pi_state *pi_state = NULL;
Thomas Gleixner3ef240e2019-11-06 22:55:46 +01002882 struct task_struct *exiting = NULL;
Peter Zijlstracfafcd12017-03-22 11:35:58 +01002883 struct rt_mutex_waiter rt_waiter;
Ingo Molnarc87e2832006-06-27 02:54:58 -07002884 struct futex_hash_bucket *hb;
Darren Hart5bdb05f2010-11-08 13:40:28 -08002885 struct futex_q q = futex_q_init;
Darren Hartdd973992009-04-03 13:40:02 -07002886 int res, ret;
Ingo Molnarc87e2832006-06-27 02:54:58 -07002887
Nicolas Pitrebc2eecd2017-08-01 00:31:32 -04002888 if (!IS_ENABLED(CONFIG_FUTEX_PI))
2889 return -ENOSYS;
2890
Ingo Molnarc87e2832006-06-27 02:54:58 -07002891 if (refill_pi_state_cache())
2892 return -ENOMEM;
2893
Waiman Long5ca584d2019-05-28 12:03:45 -04002894 to = futex_setup_timer(time, &timeout, FLAGS_CLOCKRT, 0);
Thomas Gleixnerc5780e92006-09-08 09:47:15 -07002895
Darren Hart42d35d42008-12-29 15:49:53 -08002896retry:
Linus Torvalds96d4f262019-01-03 18:57:57 -08002897 ret = get_futex_key(uaddr, flags & FLAGS_SHARED, &q.key, FUTEX_WRITE);
Ingo Molnarc87e2832006-06-27 02:54:58 -07002898 if (unlikely(ret != 0))
Darren Hart42d35d42008-12-29 15:49:53 -08002899 goto out;
Ingo Molnarc87e2832006-06-27 02:54:58 -07002900
Darren Harte4dc5b72009-03-12 00:56:13 -07002901retry_private:
Eric Sesterhenn82af7ac2008-01-25 10:40:46 +01002902 hb = queue_lock(&q);
Ingo Molnarc87e2832006-06-27 02:54:58 -07002903
Thomas Gleixner3ef240e2019-11-06 22:55:46 +01002904 ret = futex_lock_pi_atomic(uaddr, hb, &q.key, &q.pi_state, current,
2905 &exiting, 0);
Ingo Molnarc87e2832006-06-27 02:54:58 -07002906 if (unlikely(ret)) {
Davidlohr Bueso767f5092015-06-29 23:26:01 -07002907 /*
2908 * Atomic work succeeded and we got the lock,
2909 * or failed. Either way, we do _not_ block.
2910 */
Alexey Kuznetsov778e9a92007-06-08 13:47:00 -07002911 switch (ret) {
Darren Hart1a520842009-04-03 13:39:52 -07002912 case 1:
2913 /* We got the lock. */
2914 ret = 0;
2915 goto out_unlock_put_key;
2916 case -EFAULT:
2917 goto uaddr_faulted;
Thomas Gleixnerac31c7f2019-11-06 22:55:45 +01002918 case -EBUSY:
Alexey Kuznetsov778e9a92007-06-08 13:47:00 -07002919 case -EAGAIN:
2920 /*
Thomas Gleixneraf54d6a2014-06-11 20:45:41 +00002921 * Two reasons for this:
Thomas Gleixnerac31c7f2019-11-06 22:55:45 +01002922 * - EBUSY: Task is exiting and we just wait for the
Thomas Gleixneraf54d6a2014-06-11 20:45:41 +00002923 * exit to complete.
Thomas Gleixnerac31c7f2019-11-06 22:55:45 +01002924 * - EAGAIN: The user space value changed.
Alexey Kuznetsov778e9a92007-06-08 13:47:00 -07002925 */
Jason Low0d00c7b2014-01-12 15:31:22 -08002926 queue_unlock(hb);
Thomas Gleixnerae791a22010-11-10 13:30:36 +01002927 put_futex_key(&q.key);
Thomas Gleixner3ef240e2019-11-06 22:55:46 +01002928 /*
2929 * Handle the case where the owner is in the middle of
2930 * exiting. Wait for the exit to complete otherwise
2931 * this task might loop forever, aka. live lock.
2932 */
2933 wait_for_owner_exiting(ret, exiting);
Alexey Kuznetsov778e9a92007-06-08 13:47:00 -07002934 cond_resched();
2935 goto retry;
Alexey Kuznetsov778e9a92007-06-08 13:47:00 -07002936 default:
Darren Hart42d35d42008-12-29 15:49:53 -08002937 goto out_unlock_put_key;
Ingo Molnarc87e2832006-06-27 02:54:58 -07002938 }
Ingo Molnarc87e2832006-06-27 02:54:58 -07002939 }
2940
Peter Zijlstracfafcd12017-03-22 11:35:58 +01002941 WARN_ON(!q.pi_state);
2942
Ingo Molnarc87e2832006-06-27 02:54:58 -07002943 /*
2944 * Only actually queue now that the atomic ops are done:
2945 */
Peter Zijlstracfafcd12017-03-22 11:35:58 +01002946 __queue_me(&q, hb);
Ingo Molnarc87e2832006-06-27 02:54:58 -07002947
Peter Zijlstracfafcd12017-03-22 11:35:58 +01002948 if (trylock) {
Peter Zijlstra5293c2e2017-03-22 11:35:51 +01002949 ret = rt_mutex_futex_trylock(&q.pi_state->pi_mutex);
Ingo Molnarc87e2832006-06-27 02:54:58 -07002950 /* Fixup the trylock return value: */
2951 ret = ret ? 0 : -EWOULDBLOCK;
Peter Zijlstracfafcd12017-03-22 11:35:58 +01002952 goto no_block;
Ingo Molnarc87e2832006-06-27 02:54:58 -07002953 }
2954
Peter Zijlstracfafcd12017-03-22 11:35:58 +01002955 rt_mutex_init_waiter(&rt_waiter);
Peter Zijlstra56222b22017-03-22 11:36:00 +01002956
2957 /*
2958 * On PREEMPT_RT_FULL, when hb->lock becomes an rt_mutex, we must not
2959 * hold it while doing rt_mutex_start_proxy(), because then it will
2960 * include hb->lock in the blocking chain, even through we'll not in
2961 * fact hold it while blocking. This will lead it to report -EDEADLK
2962 * and BUG when futex_unlock_pi() interleaves with this.
2963 *
2964 * Therefore acquire wait_lock while holding hb->lock, but drop the
Thomas Gleixner1a1fb982019-01-29 23:15:12 +01002965 * latter before calling __rt_mutex_start_proxy_lock(). This
2966 * interleaves with futex_unlock_pi() -- which does a similar lock
2967 * handoff -- such that the latter can observe the futex_q::pi_state
2968 * before __rt_mutex_start_proxy_lock() is done.
Peter Zijlstra56222b22017-03-22 11:36:00 +01002969 */
2970 raw_spin_lock_irq(&q.pi_state->pi_mutex.wait_lock);
2971 spin_unlock(q.lock_ptr);
Thomas Gleixner1a1fb982019-01-29 23:15:12 +01002972 /*
2973 * __rt_mutex_start_proxy_lock() unconditionally enqueues the @rt_waiter
2974 * such that futex_unlock_pi() is guaranteed to observe the waiter when
2975 * it sees the futex_q::pi_state.
2976 */
Peter Zijlstra56222b22017-03-22 11:36:00 +01002977 ret = __rt_mutex_start_proxy_lock(&q.pi_state->pi_mutex, &rt_waiter, current);
2978 raw_spin_unlock_irq(&q.pi_state->pi_mutex.wait_lock);
2979
Peter Zijlstracfafcd12017-03-22 11:35:58 +01002980 if (ret) {
2981 if (ret == 1)
2982 ret = 0;
Thomas Gleixner1a1fb982019-01-29 23:15:12 +01002983 goto cleanup;
Peter Zijlstracfafcd12017-03-22 11:35:58 +01002984 }
2985
Peter Zijlstracfafcd12017-03-22 11:35:58 +01002986 if (unlikely(to))
Thomas Gleixner9dd88132019-07-30 21:16:55 +02002987 hrtimer_sleeper_start_expires(to, HRTIMER_MODE_ABS);
Peter Zijlstracfafcd12017-03-22 11:35:58 +01002988
2989 ret = rt_mutex_wait_proxy_lock(&q.pi_state->pi_mutex, to, &rt_waiter);
2990
Thomas Gleixner1a1fb982019-01-29 23:15:12 +01002991cleanup:
Vernon Mauerya99e4e42006-07-01 04:35:42 -07002992 spin_lock(q.lock_ptr);
Darren Hartdd973992009-04-03 13:40:02 -07002993 /*
Thomas Gleixner1a1fb982019-01-29 23:15:12 +01002994 * If we failed to acquire the lock (deadlock/signal/timeout), we must
Peter Zijlstracfafcd12017-03-22 11:35:58 +01002995 * first acquire the hb->lock before removing the lock from the
Thomas Gleixner1a1fb982019-01-29 23:15:12 +01002996 * rt_mutex waitqueue, such that we can keep the hb and rt_mutex wait
2997 * lists consistent.
Peter Zijlstra56222b22017-03-22 11:36:00 +01002998 *
2999 * In particular; it is important that futex_unlock_pi() can not
3000 * observe this inconsistency.
Peter Zijlstracfafcd12017-03-22 11:35:58 +01003001 */
3002 if (ret && !rt_mutex_cleanup_proxy_lock(&q.pi_state->pi_mutex, &rt_waiter))
3003 ret = 0;
3004
3005no_block:
3006 /*
Darren Hartdd973992009-04-03 13:40:02 -07003007 * Fixup the pi_state owner and possibly acquire the lock if we
3008 * haven't already.
3009 */
Thomas Gleixnerae791a22010-11-10 13:30:36 +01003010 res = fixup_owner(uaddr, &q, !ret);
Darren Hartdd973992009-04-03 13:40:02 -07003011 /*
3012 * If fixup_owner() returned an error, proprogate that. If it acquired
3013 * the lock, clear our -ETIMEDOUT or -EINTR.
3014 */
3015 if (res)
3016 ret = (res < 0) ? res : 0;
Ingo Molnarc87e2832006-06-27 02:54:58 -07003017
Darren Harte8f63862009-03-12 00:56:06 -07003018 /*
Darren Hartdd973992009-04-03 13:40:02 -07003019 * If fixup_owner() faulted and was unable to handle the fault, unlock
3020 * it and return the fault to userspace.
Darren Harte8f63862009-03-12 00:56:06 -07003021 */
Peter Zijlstra16ffa122017-03-22 11:35:55 +01003022 if (ret && (rt_mutex_owner(&q.pi_state->pi_mutex) == current)) {
3023 pi_state = q.pi_state;
3024 get_pi_state(pi_state);
3025 }
Darren Harte8f63862009-03-12 00:56:06 -07003026
Alexey Kuznetsov778e9a92007-06-08 13:47:00 -07003027 /* Unqueue and drop the lock */
3028 unqueue_me_pi(&q);
Ingo Molnarc87e2832006-06-27 02:54:58 -07003029
Peter Zijlstra16ffa122017-03-22 11:35:55 +01003030 if (pi_state) {
3031 rt_mutex_futex_unlock(&pi_state->pi_mutex);
3032 put_pi_state(pi_state);
3033 }
3034
Mikael Pettersson5ecb01c2010-01-23 22:36:29 +01003035 goto out_put_key;
Ingo Molnarc87e2832006-06-27 02:54:58 -07003036
Darren Hart42d35d42008-12-29 15:49:53 -08003037out_unlock_put_key:
Jason Low0d00c7b2014-01-12 15:31:22 -08003038 queue_unlock(hb);
Ingo Molnarc87e2832006-06-27 02:54:58 -07003039
Darren Hart42d35d42008-12-29 15:49:53 -08003040out_put_key:
Thomas Gleixnerae791a22010-11-10 13:30:36 +01003041 put_futex_key(&q.key);
Darren Hart42d35d42008-12-29 15:49:53 -08003042out:
Thomas Gleixner97181f92017-04-10 18:03:36 +02003043 if (to) {
3044 hrtimer_cancel(&to->timer);
Thomas Gleixner237fc6e2008-04-30 00:55:04 -07003045 destroy_hrtimer_on_stack(&to->timer);
Thomas Gleixner97181f92017-04-10 18:03:36 +02003046 }
Darren Hartdd973992009-04-03 13:40:02 -07003047 return ret != -EINTR ? ret : -ERESTARTNOINTR;
Ingo Molnarc87e2832006-06-27 02:54:58 -07003048
Darren Hart42d35d42008-12-29 15:49:53 -08003049uaddr_faulted:
Jason Low0d00c7b2014-01-12 15:31:22 -08003050 queue_unlock(hb);
Alexey Kuznetsov778e9a92007-06-08 13:47:00 -07003051
Thomas Gleixnerd0725992009-06-11 23:15:43 +02003052 ret = fault_in_user_writeable(uaddr);
Darren Harte4dc5b72009-03-12 00:56:13 -07003053 if (ret)
3054 goto out_put_key;
Ingo Molnarc87e2832006-06-27 02:54:58 -07003055
Darren Hartb41277d2010-11-08 13:10:09 -08003056 if (!(flags & FLAGS_SHARED))
Darren Harte4dc5b72009-03-12 00:56:13 -07003057 goto retry_private;
3058
Thomas Gleixnerae791a22010-11-10 13:30:36 +01003059 put_futex_key(&q.key);
Darren Harte4dc5b72009-03-12 00:56:13 -07003060 goto retry;
Ingo Molnarc87e2832006-06-27 02:54:58 -07003061}
3062
3063/*
Ingo Molnarc87e2832006-06-27 02:54:58 -07003064 * Userspace attempted a TID -> 0 atomic transition, and failed.
3065 * This is the in-kernel slowpath: we look up the PI state (if any),
3066 * and do the rt-mutex unlock.
3067 */
Darren Hartb41277d2010-11-08 13:10:09 -08003068static int futex_unlock_pi(u32 __user *uaddr, unsigned int flags)
Ingo Molnarc87e2832006-06-27 02:54:58 -07003069{
Thomas Gleixnerccf9e6a2014-06-11 20:45:38 +00003070 u32 uninitialized_var(curval), uval, vpid = task_pid_vnr(current);
Peter Zijlstra38d47c12008-09-26 19:32:20 +02003071 union futex_key key = FUTEX_KEY_INIT;
Thomas Gleixnerccf9e6a2014-06-11 20:45:38 +00003072 struct futex_hash_bucket *hb;
Peter Zijlstra499f5ac2017-03-22 11:35:48 +01003073 struct futex_q *top_waiter;
Darren Harte4dc5b72009-03-12 00:56:13 -07003074 int ret;
Ingo Molnarc87e2832006-06-27 02:54:58 -07003075
Nicolas Pitrebc2eecd2017-08-01 00:31:32 -04003076 if (!IS_ENABLED(CONFIG_FUTEX_PI))
3077 return -ENOSYS;
3078
Ingo Molnarc87e2832006-06-27 02:54:58 -07003079retry:
3080 if (get_user(uval, uaddr))
3081 return -EFAULT;
3082 /*
3083 * We release only a lock we actually own:
3084 */
Thomas Gleixnerc0c9ed12011-03-11 11:51:22 +01003085 if ((uval & FUTEX_TID_MASK) != vpid)
Ingo Molnarc87e2832006-06-27 02:54:58 -07003086 return -EPERM;
Ingo Molnarc87e2832006-06-27 02:54:58 -07003087
Linus Torvalds96d4f262019-01-03 18:57:57 -08003088 ret = get_futex_key(uaddr, flags & FLAGS_SHARED, &key, FUTEX_WRITE);
Thomas Gleixnerccf9e6a2014-06-11 20:45:38 +00003089 if (ret)
3090 return ret;
Ingo Molnarc87e2832006-06-27 02:54:58 -07003091
3092 hb = hash_futex(&key);
3093 spin_lock(&hb->lock);
3094
Ingo Molnarc87e2832006-06-27 02:54:58 -07003095 /*
Thomas Gleixnerccf9e6a2014-06-11 20:45:38 +00003096 * Check waiters first. We do not trust user space values at
3097 * all and we at least want to know if user space fiddled
3098 * with the futex value instead of blindly unlocking.
Ingo Molnarc87e2832006-06-27 02:54:58 -07003099 */
Peter Zijlstra499f5ac2017-03-22 11:35:48 +01003100 top_waiter = futex_top_waiter(hb, &key);
3101 if (top_waiter) {
Peter Zijlstra16ffa122017-03-22 11:35:55 +01003102 struct futex_pi_state *pi_state = top_waiter->pi_state;
3103
3104 ret = -EINVAL;
3105 if (!pi_state)
3106 goto out_unlock;
3107
Sebastian Andrzej Siewior802ab582015-06-17 10:33:50 +02003108 /*
Peter Zijlstra16ffa122017-03-22 11:35:55 +01003109 * If current does not own the pi_state then the futex is
3110 * inconsistent and user space fiddled with the futex value.
3111 */
3112 if (pi_state->owner != current)
3113 goto out_unlock;
3114
Peter Zijlstra16ffa122017-03-22 11:35:55 +01003115 get_pi_state(pi_state);
Peter Zijlstrabebe5b52017-03-22 11:35:59 +01003116 /*
Peter Zijlstrabebe5b52017-03-22 11:35:59 +01003117 * By taking wait_lock while still holding hb->lock, we ensure
3118 * there is no point where we hold neither; and therefore
3119 * wake_futex_pi() must observe a state consistent with what we
3120 * observed.
Thomas Gleixner1a1fb982019-01-29 23:15:12 +01003121 *
3122 * In particular; this forces __rt_mutex_start_proxy() to
3123 * complete such that we're guaranteed to observe the
3124 * rt_waiter. Also see the WARN in wake_futex_pi().
Peter Zijlstrabebe5b52017-03-22 11:35:59 +01003125 */
3126 raw_spin_lock_irq(&pi_state->pi_mutex.wait_lock);
Peter Zijlstra16ffa122017-03-22 11:35:55 +01003127 spin_unlock(&hb->lock);
3128
Peter Zijlstrac74aef22017-09-22 17:48:06 +02003129 /* drops pi_state->pi_mutex.wait_lock */
Peter Zijlstra16ffa122017-03-22 11:35:55 +01003130 ret = wake_futex_pi(uaddr, uval, pi_state);
3131
3132 put_pi_state(pi_state);
3133
3134 /*
3135 * Success, we're done! No tricky corner cases.
Sebastian Andrzej Siewior802ab582015-06-17 10:33:50 +02003136 */
3137 if (!ret)
3138 goto out_putkey;
Ingo Molnarc87e2832006-06-27 02:54:58 -07003139 /*
Thomas Gleixnerccf9e6a2014-06-11 20:45:38 +00003140 * The atomic access to the futex value generated a
3141 * pagefault, so retry the user-access and the wakeup:
Ingo Molnarc87e2832006-06-27 02:54:58 -07003142 */
3143 if (ret == -EFAULT)
3144 goto pi_faulted;
Sebastian Andrzej Siewior802ab582015-06-17 10:33:50 +02003145 /*
Sebastian Andrzej Siewior89e9e662016-04-15 14:35:39 +02003146 * A unconditional UNLOCK_PI op raced against a waiter
3147 * setting the FUTEX_WAITERS bit. Try again.
3148 */
Will Deacon6b4f4bc2019-02-28 11:58:08 +00003149 if (ret == -EAGAIN)
3150 goto pi_retry;
Sebastian Andrzej Siewior89e9e662016-04-15 14:35:39 +02003151 /*
Sebastian Andrzej Siewior802ab582015-06-17 10:33:50 +02003152 * wake_futex_pi has detected invalid state. Tell user
3153 * space.
3154 */
Peter Zijlstra16ffa122017-03-22 11:35:55 +01003155 goto out_putkey;
Ingo Molnarc87e2832006-06-27 02:54:58 -07003156 }
Thomas Gleixnerccf9e6a2014-06-11 20:45:38 +00003157
Ingo Molnarc87e2832006-06-27 02:54:58 -07003158 /*
Thomas Gleixnerccf9e6a2014-06-11 20:45:38 +00003159 * We have no kernel internal state, i.e. no waiters in the
3160 * kernel. Waiters which are about to queue themselves are stuck
3161 * on hb->lock. So we can safely ignore them. We do neither
3162 * preserve the WAITERS bit not the OWNER_DIED one. We are the
3163 * owner.
Ingo Molnarc87e2832006-06-27 02:54:58 -07003164 */
Will Deacon6b4f4bc2019-02-28 11:58:08 +00003165 if ((ret = cmpxchg_futex_value_locked(&curval, uaddr, uval, 0))) {
Peter Zijlstra16ffa122017-03-22 11:35:55 +01003166 spin_unlock(&hb->lock);
Will Deacon6b4f4bc2019-02-28 11:58:08 +00003167 switch (ret) {
3168 case -EFAULT:
3169 goto pi_faulted;
3170
3171 case -EAGAIN:
3172 goto pi_retry;
3173
3174 default:
3175 WARN_ON_ONCE(1);
3176 goto out_putkey;
3177 }
Peter Zijlstra16ffa122017-03-22 11:35:55 +01003178 }
Ingo Molnarc87e2832006-06-27 02:54:58 -07003179
Thomas Gleixnerccf9e6a2014-06-11 20:45:38 +00003180 /*
3181 * If uval has changed, let user space handle it.
3182 */
3183 ret = (curval == uval) ? 0 : -EAGAIN;
3184
Ingo Molnarc87e2832006-06-27 02:54:58 -07003185out_unlock:
3186 spin_unlock(&hb->lock);
Sebastian Andrzej Siewior802ab582015-06-17 10:33:50 +02003187out_putkey:
Thomas Gleixnerae791a22010-11-10 13:30:36 +01003188 put_futex_key(&key);
Ingo Molnarc87e2832006-06-27 02:54:58 -07003189 return ret;
3190
Will Deacon6b4f4bc2019-02-28 11:58:08 +00003191pi_retry:
3192 put_futex_key(&key);
3193 cond_resched();
3194 goto retry;
3195
Ingo Molnarc87e2832006-06-27 02:54:58 -07003196pi_faulted:
Thomas Gleixnerae791a22010-11-10 13:30:36 +01003197 put_futex_key(&key);
Ingo Molnarc87e2832006-06-27 02:54:58 -07003198
Thomas Gleixnerd0725992009-06-11 23:15:43 +02003199 ret = fault_in_user_writeable(uaddr);
Darren Hartb5686362008-12-18 15:06:34 -08003200 if (!ret)
Ingo Molnarc87e2832006-06-27 02:54:58 -07003201 goto retry;
3202
Linus Torvalds1da177e2005-04-16 15:20:36 -07003203 return ret;
3204}
3205
Darren Hart52400ba2009-04-03 13:40:49 -07003206/**
3207 * handle_early_requeue_pi_wakeup() - Detect early wakeup on the initial futex
3208 * @hb: the hash_bucket futex_q was original enqueued on
3209 * @q: the futex_q woken while waiting to be requeued
3210 * @key2: the futex_key of the requeue target futex
3211 * @timeout: the timeout associated with the wait (NULL if none)
3212 *
3213 * Detect if the task was woken on the initial futex as opposed to the requeue
3214 * target futex. If so, determine if it was a timeout or a signal that caused
3215 * the wakeup and return the appropriate error code to the caller. Must be
3216 * called with the hb lock held.
3217 *
Randy Dunlap6c23cbb2013-03-05 10:00:24 -08003218 * Return:
Mauro Carvalho Chehab7b4ff1a2017-05-11 10:17:45 -03003219 * - 0 = no early wakeup detected;
3220 * - <0 = -ETIMEDOUT or -ERESTARTNOINTR
Darren Hart52400ba2009-04-03 13:40:49 -07003221 */
3222static inline
3223int handle_early_requeue_pi_wakeup(struct futex_hash_bucket *hb,
3224 struct futex_q *q, union futex_key *key2,
3225 struct hrtimer_sleeper *timeout)
3226{
3227 int ret = 0;
3228
3229 /*
3230 * With the hb lock held, we avoid races while we process the wakeup.
3231 * We only need to hold hb (and not hb2) to ensure atomicity as the
3232 * wakeup code can't change q.key from uaddr to uaddr2 if we hold hb.
3233 * It can't be requeued from uaddr2 to something else since we don't
3234 * support a PI aware source futex for requeue.
3235 */
3236 if (!match_futex(&q->key, key2)) {
3237 WARN_ON(q->lock_ptr && (&hb->lock != q->lock_ptr));
3238 /*
3239 * We were woken prior to requeue by a timeout or a signal.
3240 * Unqueue the futex_q and determine which it was.
3241 */
Lai Jiangshan2e129782010-12-22 14:18:50 +08003242 plist_del(&q->list, &hb->chain);
Linus Torvalds11d46162014-03-20 22:11:17 -07003243 hb_waiters_dec(hb);
Darren Hart52400ba2009-04-03 13:40:49 -07003244
Thomas Gleixnerd58e6572009-10-13 20:40:43 +02003245 /* Handle spurious wakeups gracefully */
Thomas Gleixner11df6dd2009-10-28 20:26:48 +01003246 ret = -EWOULDBLOCK;
Darren Hart52400ba2009-04-03 13:40:49 -07003247 if (timeout && !timeout->task)
3248 ret = -ETIMEDOUT;
Thomas Gleixnerd58e6572009-10-13 20:40:43 +02003249 else if (signal_pending(current))
Thomas Gleixner1c840c12009-05-20 09:22:40 +02003250 ret = -ERESTARTNOINTR;
Darren Hart52400ba2009-04-03 13:40:49 -07003251 }
3252 return ret;
3253}
3254
3255/**
3256 * futex_wait_requeue_pi() - Wait on uaddr and take uaddr2
Darren Hart56ec1602009-09-21 22:29:59 -07003257 * @uaddr: the futex we initially wait on (non-pi)
Darren Hartb41277d2010-11-08 13:10:09 -08003258 * @flags: futex flags (FLAGS_SHARED, FLAGS_CLOCKRT, etc.), they must be
Davidlohr Buesoab51fba2015-06-29 23:26:02 -07003259 * the same type, no requeueing from private to shared, etc.
Darren Hart52400ba2009-04-03 13:40:49 -07003260 * @val: the expected value of uaddr
3261 * @abs_time: absolute timeout
Darren Hart56ec1602009-09-21 22:29:59 -07003262 * @bitset: 32 bit wakeup bitset set by userspace, defaults to all
Darren Hart52400ba2009-04-03 13:40:49 -07003263 * @uaddr2: the pi futex we will take prior to returning to user-space
3264 *
3265 * The caller will wait on uaddr and will be requeued by futex_requeue() to
Darren Hart6f7b0a22012-07-20 11:53:31 -07003266 * uaddr2 which must be PI aware and unique from uaddr. Normal wakeup will wake
3267 * on uaddr2 and complete the acquisition of the rt_mutex prior to returning to
3268 * userspace. This ensures the rt_mutex maintains an owner when it has waiters;
3269 * without one, the pi logic would not know which task to boost/deboost, if
3270 * there was a need to.
Darren Hart52400ba2009-04-03 13:40:49 -07003271 *
3272 * We call schedule in futex_wait_queue_me() when we enqueue and return there
Randy Dunlap6c23cbb2013-03-05 10:00:24 -08003273 * via the following--
Darren Hart52400ba2009-04-03 13:40:49 -07003274 * 1) wakeup on uaddr2 after an atomic lock acquisition by futex_requeue()
Darren Hartcc6db4e2009-07-31 16:20:10 -07003275 * 2) wakeup on uaddr2 after a requeue
3276 * 3) signal
3277 * 4) timeout
Darren Hart52400ba2009-04-03 13:40:49 -07003278 *
Darren Hartcc6db4e2009-07-31 16:20:10 -07003279 * If 3, cleanup and return -ERESTARTNOINTR.
Darren Hart52400ba2009-04-03 13:40:49 -07003280 *
3281 * If 2, we may then block on trying to take the rt_mutex and return via:
3282 * 5) successful lock
3283 * 6) signal
3284 * 7) timeout
3285 * 8) other lock acquisition failure
3286 *
Darren Hartcc6db4e2009-07-31 16:20:10 -07003287 * If 6, return -EWOULDBLOCK (restarting the syscall would do the same).
Darren Hart52400ba2009-04-03 13:40:49 -07003288 *
3289 * If 4 or 7, we cleanup and return with -ETIMEDOUT.
3290 *
Randy Dunlap6c23cbb2013-03-05 10:00:24 -08003291 * Return:
Mauro Carvalho Chehab7b4ff1a2017-05-11 10:17:45 -03003292 * - 0 - On success;
3293 * - <0 - On error
Darren Hart52400ba2009-04-03 13:40:49 -07003294 */
Darren Hartb41277d2010-11-08 13:10:09 -08003295static int futex_wait_requeue_pi(u32 __user *uaddr, unsigned int flags,
Darren Hart52400ba2009-04-03 13:40:49 -07003296 u32 val, ktime_t *abs_time, u32 bitset,
Darren Hartb41277d2010-11-08 13:10:09 -08003297 u32 __user *uaddr2)
Darren Hart52400ba2009-04-03 13:40:49 -07003298{
Waiman Long5ca584d2019-05-28 12:03:45 -04003299 struct hrtimer_sleeper timeout, *to;
Peter Zijlstra16ffa122017-03-22 11:35:55 +01003300 struct futex_pi_state *pi_state = NULL;
Darren Hart52400ba2009-04-03 13:40:49 -07003301 struct rt_mutex_waiter rt_waiter;
Darren Hart52400ba2009-04-03 13:40:49 -07003302 struct futex_hash_bucket *hb;
Darren Hart5bdb05f2010-11-08 13:40:28 -08003303 union futex_key key2 = FUTEX_KEY_INIT;
3304 struct futex_q q = futex_q_init;
Darren Hart52400ba2009-04-03 13:40:49 -07003305 int res, ret;
Darren Hart52400ba2009-04-03 13:40:49 -07003306
Nicolas Pitrebc2eecd2017-08-01 00:31:32 -04003307 if (!IS_ENABLED(CONFIG_FUTEX_PI))
3308 return -ENOSYS;
3309
Darren Hart6f7b0a22012-07-20 11:53:31 -07003310 if (uaddr == uaddr2)
3311 return -EINVAL;
3312
Darren Hart52400ba2009-04-03 13:40:49 -07003313 if (!bitset)
3314 return -EINVAL;
3315
Waiman Long5ca584d2019-05-28 12:03:45 -04003316 to = futex_setup_timer(abs_time, &timeout, flags,
3317 current->timer_slack_ns);
Darren Hart52400ba2009-04-03 13:40:49 -07003318
3319 /*
3320 * The waiter is allocated on our stack, manipulated by the requeue
3321 * code while we sleep on uaddr.
3322 */
Peter Zijlstra50809352017-03-22 11:35:56 +01003323 rt_mutex_init_waiter(&rt_waiter);
Darren Hart52400ba2009-04-03 13:40:49 -07003324
Linus Torvalds96d4f262019-01-03 18:57:57 -08003325 ret = get_futex_key(uaddr2, flags & FLAGS_SHARED, &key2, FUTEX_WRITE);
Darren Hart52400ba2009-04-03 13:40:49 -07003326 if (unlikely(ret != 0))
3327 goto out;
3328
Darren Hart84bc4af2009-08-13 17:36:53 -07003329 q.bitset = bitset;
3330 q.rt_waiter = &rt_waiter;
3331 q.requeue_pi_key = &key2;
3332
Darren Hart7ada8762010-10-17 08:35:04 -07003333 /*
3334 * Prepare to wait on uaddr. On success, increments q.key (key1) ref
3335 * count.
3336 */
Darren Hartb41277d2010-11-08 13:10:09 -08003337 ret = futex_wait_setup(uaddr, val, flags, &q, &hb);
Thomas Gleixnerc8b15a72009-05-20 09:18:50 +02003338 if (ret)
3339 goto out_key2;
Darren Hart52400ba2009-04-03 13:40:49 -07003340
Thomas Gleixnere9c243a2014-06-03 12:27:06 +00003341 /*
3342 * The check above which compares uaddrs is not sufficient for
3343 * shared futexes. We need to compare the keys:
3344 */
3345 if (match_futex(&q.key, &key2)) {
Thomas Gleixner13c42c22014-09-11 23:44:35 +02003346 queue_unlock(hb);
Thomas Gleixnere9c243a2014-06-03 12:27:06 +00003347 ret = -EINVAL;
3348 goto out_put_keys;
3349 }
3350
Darren Hart52400ba2009-04-03 13:40:49 -07003351 /* Queue the futex_q, drop the hb lock, wait for wakeup. */
Thomas Gleixnerf1a11e02009-05-05 19:21:40 +02003352 futex_wait_queue_me(hb, &q, to);
Darren Hart52400ba2009-04-03 13:40:49 -07003353
3354 spin_lock(&hb->lock);
3355 ret = handle_early_requeue_pi_wakeup(hb, &q, &key2, to);
3356 spin_unlock(&hb->lock);
3357 if (ret)
3358 goto out_put_keys;
3359
3360 /*
3361 * In order for us to be here, we know our q.key == key2, and since
3362 * we took the hb->lock above, we also know that futex_requeue() has
3363 * completed and we no longer have to concern ourselves with a wakeup
Darren Hart7ada8762010-10-17 08:35:04 -07003364 * race with the atomic proxy lock acquisition by the requeue code. The
3365 * futex_requeue dropped our key1 reference and incremented our key2
3366 * reference count.
Darren Hart52400ba2009-04-03 13:40:49 -07003367 */
3368
3369 /* Check if the requeue code acquired the second futex for us. */
3370 if (!q.rt_waiter) {
3371 /*
3372 * Got the lock. We might not be the anticipated owner if we
3373 * did a lock-steal - fix up the PI-state in that case.
3374 */
3375 if (q.pi_state && (q.pi_state->owner != current)) {
3376 spin_lock(q.lock_ptr);
Thomas Gleixnerae791a22010-11-10 13:30:36 +01003377 ret = fixup_pi_state_owner(uaddr2, &q, current);
Peter Zijlstra16ffa122017-03-22 11:35:55 +01003378 if (ret && rt_mutex_owner(&q.pi_state->pi_mutex) == current) {
3379 pi_state = q.pi_state;
3380 get_pi_state(pi_state);
3381 }
Thomas Gleixnerfb75a422015-12-19 20:07:38 +00003382 /*
3383 * Drop the reference to the pi state which
3384 * the requeue_pi() code acquired for us.
3385 */
Thomas Gleixner29e9ee52015-12-19 20:07:39 +00003386 put_pi_state(q.pi_state);
Darren Hart52400ba2009-04-03 13:40:49 -07003387 spin_unlock(q.lock_ptr);
3388 }
3389 } else {
Peter Zijlstrac236c8e2017-03-04 10:27:18 +01003390 struct rt_mutex *pi_mutex;
3391
Darren Hart52400ba2009-04-03 13:40:49 -07003392 /*
3393 * We have been woken up by futex_unlock_pi(), a timeout, or a
3394 * signal. futex_unlock_pi() will not destroy the lock_ptr nor
3395 * the pi_state.
3396 */
Darren Hartf27071c2012-07-20 11:53:30 -07003397 WARN_ON(!q.pi_state);
Darren Hart52400ba2009-04-03 13:40:49 -07003398 pi_mutex = &q.pi_state->pi_mutex;
Peter Zijlstra38d589f2017-03-22 11:35:57 +01003399 ret = rt_mutex_wait_proxy_lock(pi_mutex, to, &rt_waiter);
Darren Hart52400ba2009-04-03 13:40:49 -07003400
3401 spin_lock(q.lock_ptr);
Peter Zijlstra38d589f2017-03-22 11:35:57 +01003402 if (ret && !rt_mutex_cleanup_proxy_lock(pi_mutex, &rt_waiter))
3403 ret = 0;
3404
3405 debug_rt_mutex_free_waiter(&rt_waiter);
Darren Hart52400ba2009-04-03 13:40:49 -07003406 /*
3407 * Fixup the pi_state owner and possibly acquire the lock if we
3408 * haven't already.
3409 */
Thomas Gleixnerae791a22010-11-10 13:30:36 +01003410 res = fixup_owner(uaddr2, &q, !ret);
Darren Hart52400ba2009-04-03 13:40:49 -07003411 /*
3412 * If fixup_owner() returned an error, proprogate that. If it
Darren Hart56ec1602009-09-21 22:29:59 -07003413 * acquired the lock, clear -ETIMEDOUT or -EINTR.
Darren Hart52400ba2009-04-03 13:40:49 -07003414 */
3415 if (res)
3416 ret = (res < 0) ? res : 0;
3417
Peter Zijlstrac236c8e2017-03-04 10:27:18 +01003418 /*
3419 * If fixup_pi_state_owner() faulted and was unable to handle
3420 * the fault, unlock the rt_mutex and return the fault to
3421 * userspace.
3422 */
Peter Zijlstra16ffa122017-03-22 11:35:55 +01003423 if (ret && rt_mutex_owner(&q.pi_state->pi_mutex) == current) {
3424 pi_state = q.pi_state;
3425 get_pi_state(pi_state);
3426 }
Peter Zijlstrac236c8e2017-03-04 10:27:18 +01003427
Darren Hart52400ba2009-04-03 13:40:49 -07003428 /* Unqueue and drop the lock. */
3429 unqueue_me_pi(&q);
3430 }
3431
Peter Zijlstra16ffa122017-03-22 11:35:55 +01003432 if (pi_state) {
3433 rt_mutex_futex_unlock(&pi_state->pi_mutex);
3434 put_pi_state(pi_state);
3435 }
3436
Peter Zijlstrac236c8e2017-03-04 10:27:18 +01003437 if (ret == -EINTR) {
Darren Hart52400ba2009-04-03 13:40:49 -07003438 /*
Darren Hartcc6db4e2009-07-31 16:20:10 -07003439 * We've already been requeued, but cannot restart by calling
3440 * futex_lock_pi() directly. We could restart this syscall, but
3441 * it would detect that the user space "val" changed and return
3442 * -EWOULDBLOCK. Save the overhead of the restart and return
3443 * -EWOULDBLOCK directly.
Darren Hart52400ba2009-04-03 13:40:49 -07003444 */
Thomas Gleixner20708872009-05-19 23:04:59 +02003445 ret = -EWOULDBLOCK;
Darren Hart52400ba2009-04-03 13:40:49 -07003446 }
3447
3448out_put_keys:
Thomas Gleixnerae791a22010-11-10 13:30:36 +01003449 put_futex_key(&q.key);
Thomas Gleixnerc8b15a72009-05-20 09:18:50 +02003450out_key2:
Thomas Gleixnerae791a22010-11-10 13:30:36 +01003451 put_futex_key(&key2);
Darren Hart52400ba2009-04-03 13:40:49 -07003452
3453out:
3454 if (to) {
3455 hrtimer_cancel(&to->timer);
3456 destroy_hrtimer_on_stack(&to->timer);
3457 }
3458 return ret;
3459}
3460
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003461/*
3462 * Support for robust futexes: the kernel cleans up held futexes at
3463 * thread exit time.
3464 *
3465 * Implementation: user-space maintains a per-thread list of locks it
3466 * is holding. Upon do_exit(), the kernel carefully walks this list,
3467 * and marks all locks that are owned by this thread with the
Ingo Molnarc87e2832006-06-27 02:54:58 -07003468 * FUTEX_OWNER_DIED bit, and wakes up a waiter (if any). The list is
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003469 * always manipulated with the lock held, so the list is private and
3470 * per-thread. Userspace also maintains a per-thread 'list_op_pending'
3471 * field, to allow the kernel to clean up if the thread dies after
3472 * acquiring the lock, but just before it could have added itself to
3473 * the list. There can only be one such pending lock.
3474 */
3475
3476/**
Darren Hartd96ee562009-09-21 22:30:22 -07003477 * sys_set_robust_list() - Set the robust-futex list head of a task
3478 * @head: pointer to the list-head
3479 * @len: length of the list-head, as userspace expects
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003480 */
Heiko Carstens836f92a2009-01-14 14:14:33 +01003481SYSCALL_DEFINE2(set_robust_list, struct robust_list_head __user *, head,
3482 size_t, len)
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003483{
Thomas Gleixnera0c1e902008-02-23 15:23:57 -08003484 if (!futex_cmpxchg_enabled)
3485 return -ENOSYS;
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003486 /*
3487 * The kernel knows only one size for now:
3488 */
3489 if (unlikely(len != sizeof(*head)))
3490 return -EINVAL;
3491
3492 current->robust_list = head;
3493
3494 return 0;
3495}
3496
3497/**
Darren Hartd96ee562009-09-21 22:30:22 -07003498 * sys_get_robust_list() - Get the robust-futex list head of a task
3499 * @pid: pid of the process [zero for current task]
3500 * @head_ptr: pointer to a list-head pointer, the kernel fills it in
3501 * @len_ptr: pointer to a length field, the kernel fills in the header size
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003502 */
Heiko Carstens836f92a2009-01-14 14:14:33 +01003503SYSCALL_DEFINE3(get_robust_list, int, pid,
3504 struct robust_list_head __user * __user *, head_ptr,
3505 size_t __user *, len_ptr)
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003506{
Al Viroba46df92006-10-10 22:46:07 +01003507 struct robust_list_head __user *head;
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003508 unsigned long ret;
Kees Cookbdbb7762012-03-19 16:12:53 -07003509 struct task_struct *p;
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003510
Thomas Gleixnera0c1e902008-02-23 15:23:57 -08003511 if (!futex_cmpxchg_enabled)
3512 return -ENOSYS;
3513
Kees Cookbdbb7762012-03-19 16:12:53 -07003514 rcu_read_lock();
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003515
Kees Cookbdbb7762012-03-19 16:12:53 -07003516 ret = -ESRCH;
3517 if (!pid)
3518 p = current;
3519 else {
Pavel Emelyanov228ebcb2007-10-18 23:40:16 -07003520 p = find_task_by_vpid(pid);
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003521 if (!p)
3522 goto err_unlock;
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003523 }
3524
Kees Cookbdbb7762012-03-19 16:12:53 -07003525 ret = -EPERM;
Jann Horncaaee622016-01-20 15:00:04 -08003526 if (!ptrace_may_access(p, PTRACE_MODE_READ_REALCREDS))
Kees Cookbdbb7762012-03-19 16:12:53 -07003527 goto err_unlock;
3528
3529 head = p->robust_list;
3530 rcu_read_unlock();
3531
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003532 if (put_user(sizeof(*head), len_ptr))
3533 return -EFAULT;
3534 return put_user(head, head_ptr);
3535
3536err_unlock:
Oleg Nesterovaaa2a972006-09-29 02:00:55 -07003537 rcu_read_unlock();
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003538
3539 return ret;
3540}
3541
Yang Taoca16d5b2019-11-06 22:55:35 +01003542/* Constants for the pending_op argument of handle_futex_death */
3543#define HANDLE_DEATH_PENDING true
3544#define HANDLE_DEATH_LIST false
3545
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003546/*
3547 * Process a futex-list entry, check whether it's owned by the
3548 * dying task, and do notification if so:
3549 */
Yang Taoca16d5b2019-11-06 22:55:35 +01003550static int handle_futex_death(u32 __user *uaddr, struct task_struct *curr,
3551 bool pi, bool pending_op)
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003552{
Vitaliy Ivanov7cfdaf32011-07-07 15:10:31 +03003553 u32 uval, uninitialized_var(nval), mval;
Will Deacon6b4f4bc2019-02-28 11:58:08 +00003554 int err;
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003555
Chen Jie5a071682019-03-15 03:44:38 +00003556 /* Futex address must be 32bit aligned */
3557 if ((((unsigned long)uaddr) % sizeof(*uaddr)) != 0)
3558 return -1;
3559
Ingo Molnar8f17d3a2006-03-27 01:16:27 -08003560retry:
3561 if (get_user(uval, uaddr))
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003562 return -1;
3563
Yang Taoca16d5b2019-11-06 22:55:35 +01003564 /*
3565 * Special case for regular (non PI) futexes. The unlock path in
3566 * user space has two race scenarios:
3567 *
3568 * 1. The unlock path releases the user space futex value and
3569 * before it can execute the futex() syscall to wake up
3570 * waiters it is killed.
3571 *
3572 * 2. A woken up waiter is killed before it can acquire the
3573 * futex in user space.
3574 *
3575 * In both cases the TID validation below prevents a wakeup of
3576 * potential waiters which can cause these waiters to block
3577 * forever.
3578 *
3579 * In both cases the following conditions are met:
3580 *
3581 * 1) task->robust_list->list_op_pending != NULL
3582 * @pending_op == true
3583 * 2) User space futex value == 0
3584 * 3) Regular futex: @pi == false
3585 *
3586 * If these conditions are met, it is safe to attempt waking up a
3587 * potential waiter without touching the user space futex value and
3588 * trying to set the OWNER_DIED bit. The user space futex value is
3589 * uncontended and the rest of the user space mutex state is
3590 * consistent, so a woken waiter will just take over the
3591 * uncontended futex. Setting the OWNER_DIED bit would create
3592 * inconsistent state and malfunction of the user space owner died
3593 * handling.
3594 */
3595 if (pending_op && !pi && !uval) {
3596 futex_wake(uaddr, 1, 1, FUTEX_BITSET_MATCH_ANY);
3597 return 0;
3598 }
3599
Will Deacon6b4f4bc2019-02-28 11:58:08 +00003600 if ((uval & FUTEX_TID_MASK) != task_pid_vnr(curr))
3601 return 0;
3602
3603 /*
3604 * Ok, this dying thread is truly holding a futex
3605 * of interest. Set the OWNER_DIED bit atomically
3606 * via cmpxchg, and if the value had FUTEX_WAITERS
3607 * set, wake up a waiter (if any). (We have to do a
3608 * futex_wake() even if OWNER_DIED is already set -
3609 * to handle the rare but possible case of recursive
3610 * thread-death.) The rest of the cleanup is done in
3611 * userspace.
3612 */
3613 mval = (uval & FUTEX_WAITERS) | FUTEX_OWNER_DIED;
3614
3615 /*
3616 * We are not holding a lock here, but we want to have
3617 * the pagefault_disable/enable() protection because
3618 * we want to handle the fault gracefully. If the
3619 * access fails we try to fault in the futex with R/W
3620 * verification via get_user_pages. get_user() above
3621 * does not guarantee R/W access. If that fails we
3622 * give up and leave the futex locked.
3623 */
3624 if ((err = cmpxchg_futex_value_locked(&nval, uaddr, uval, mval))) {
3625 switch (err) {
3626 case -EFAULT:
Thomas Gleixner6e0aa9f2011-03-14 10:34:35 +01003627 if (fault_in_user_writeable(uaddr))
3628 return -1;
3629 goto retry;
Will Deacon6b4f4bc2019-02-28 11:58:08 +00003630
3631 case -EAGAIN:
3632 cond_resched();
Ingo Molnar8f17d3a2006-03-27 01:16:27 -08003633 goto retry;
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003634
Will Deacon6b4f4bc2019-02-28 11:58:08 +00003635 default:
3636 WARN_ON_ONCE(1);
3637 return err;
3638 }
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003639 }
Will Deacon6b4f4bc2019-02-28 11:58:08 +00003640
3641 if (nval != uval)
3642 goto retry;
3643
3644 /*
3645 * Wake robust non-PI futexes here. The wakeup of
3646 * PI futexes happens in exit_pi_state():
3647 */
3648 if (!pi && (uval & FUTEX_WAITERS))
3649 futex_wake(uaddr, 1, 1, FUTEX_BITSET_MATCH_ANY);
3650
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003651 return 0;
3652}
3653
3654/*
Ingo Molnare3f2dde2006-07-29 05:17:57 +02003655 * Fetch a robust-list pointer. Bit 0 signals PI futexes:
3656 */
3657static inline int fetch_robust_entry(struct robust_list __user **entry,
Al Viroba46df92006-10-10 22:46:07 +01003658 struct robust_list __user * __user *head,
Namhyung Kim1dcc41b2010-09-14 21:43:46 +09003659 unsigned int *pi)
Ingo Molnare3f2dde2006-07-29 05:17:57 +02003660{
3661 unsigned long uentry;
3662
Al Viroba46df92006-10-10 22:46:07 +01003663 if (get_user(uentry, (unsigned long __user *)head))
Ingo Molnare3f2dde2006-07-29 05:17:57 +02003664 return -EFAULT;
3665
Al Viroba46df92006-10-10 22:46:07 +01003666 *entry = (void __user *)(uentry & ~1UL);
Ingo Molnare3f2dde2006-07-29 05:17:57 +02003667 *pi = uentry & 1;
3668
3669 return 0;
3670}
3671
3672/*
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003673 * Walk curr->robust_list (very carefully, it's a userspace list!)
3674 * and mark any locks found there dead, and notify any waiters.
3675 *
3676 * We silently return on any sign of list-walking problem.
3677 */
Thomas Gleixnerba31c1a42019-11-06 22:55:36 +01003678static void exit_robust_list(struct task_struct *curr)
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003679{
3680 struct robust_list_head __user *head = curr->robust_list;
Martin Schwidefsky9f96cb12007-10-01 01:20:13 -07003681 struct robust_list __user *entry, *next_entry, *pending;
Darren Hart4c115e92010-11-04 15:00:00 -04003682 unsigned int limit = ROBUST_LIST_LIMIT, pi, pip;
3683 unsigned int uninitialized_var(next_pi);
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003684 unsigned long futex_offset;
Martin Schwidefsky9f96cb12007-10-01 01:20:13 -07003685 int rc;
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003686
Thomas Gleixnera0c1e902008-02-23 15:23:57 -08003687 if (!futex_cmpxchg_enabled)
3688 return;
3689
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003690 /*
3691 * Fetch the list head (which was registered earlier, via
3692 * sys_set_robust_list()):
3693 */
Ingo Molnare3f2dde2006-07-29 05:17:57 +02003694 if (fetch_robust_entry(&entry, &head->list.next, &pi))
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003695 return;
3696 /*
3697 * Fetch the relative futex offset:
3698 */
3699 if (get_user(futex_offset, &head->futex_offset))
3700 return;
3701 /*
3702 * Fetch any possibly pending lock-add first, and handle it
3703 * if it exists:
3704 */
Ingo Molnare3f2dde2006-07-29 05:17:57 +02003705 if (fetch_robust_entry(&pending, &head->list_op_pending, &pip))
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003706 return;
Ingo Molnare3f2dde2006-07-29 05:17:57 +02003707
Martin Schwidefsky9f96cb12007-10-01 01:20:13 -07003708 next_entry = NULL; /* avoid warning with gcc */
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003709 while (entry != &head->list) {
3710 /*
Martin Schwidefsky9f96cb12007-10-01 01:20:13 -07003711 * Fetch the next entry in the list before calling
3712 * handle_futex_death:
3713 */
3714 rc = fetch_robust_entry(&next_entry, &entry->next, &next_pi);
3715 /*
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003716 * A pending lock might already be on the list, so
Ingo Molnarc87e2832006-06-27 02:54:58 -07003717 * don't process it twice:
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003718 */
Yang Taoca16d5b2019-11-06 22:55:35 +01003719 if (entry != pending) {
Al Viroba46df92006-10-10 22:46:07 +01003720 if (handle_futex_death((void __user *)entry + futex_offset,
Yang Taoca16d5b2019-11-06 22:55:35 +01003721 curr, pi, HANDLE_DEATH_LIST))
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003722 return;
Yang Taoca16d5b2019-11-06 22:55:35 +01003723 }
Martin Schwidefsky9f96cb12007-10-01 01:20:13 -07003724 if (rc)
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003725 return;
Martin Schwidefsky9f96cb12007-10-01 01:20:13 -07003726 entry = next_entry;
3727 pi = next_pi;
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003728 /*
3729 * Avoid excessively long or circular lists:
3730 */
3731 if (!--limit)
3732 break;
3733
3734 cond_resched();
3735 }
Martin Schwidefsky9f96cb12007-10-01 01:20:13 -07003736
Yang Taoca16d5b2019-11-06 22:55:35 +01003737 if (pending) {
Martin Schwidefsky9f96cb12007-10-01 01:20:13 -07003738 handle_futex_death((void __user *)pending + futex_offset,
Yang Taoca16d5b2019-11-06 22:55:35 +01003739 curr, pip, HANDLE_DEATH_PENDING);
3740 }
Ingo Molnar0771dfe2006-03-27 01:16:22 -08003741}
3742
Thomas Gleixneraf8cbda2019-11-06 22:55:43 +01003743static void futex_cleanup(struct task_struct *tsk)
Thomas Gleixnerba31c1a42019-11-06 22:55:36 +01003744{
3745 if (unlikely(tsk->robust_list)) {
3746 exit_robust_list(tsk);
3747 tsk->robust_list = NULL;
3748 }
3749
3750#ifdef CONFIG_COMPAT
3751 if (unlikely(tsk->compat_robust_list)) {
3752 compat_exit_robust_list(tsk);
3753 tsk->compat_robust_list = NULL;
3754 }
3755#endif
3756
3757 if (unlikely(!list_empty(&tsk->pi_state_list)))
3758 exit_pi_state_list(tsk);
3759}
3760
Thomas Gleixner18f69432019-11-06 22:55:41 +01003761/**
3762 * futex_exit_recursive - Set the tasks futex state to FUTEX_STATE_DEAD
3763 * @tsk: task to set the state on
3764 *
3765 * Set the futex exit state of the task lockless. The futex waiter code
3766 * observes that state when a task is exiting and loops until the task has
3767 * actually finished the futex cleanup. The worst case for this is that the
3768 * waiter runs through the wait loop until the state becomes visible.
3769 *
3770 * This is called from the recursive fault handling path in do_exit().
3771 *
3772 * This is best effort. Either the futex exit code has run already or
3773 * not. If the OWNER_DIED bit has been set on the futex then the waiter can
3774 * take it over. If not, the problem is pushed back to user space. If the
3775 * futex exit code did not run yet, then an already queued waiter might
3776 * block forever, but there is nothing which can be done about that.
3777 */
3778void futex_exit_recursive(struct task_struct *tsk)
3779{
Thomas Gleixner3f186d92019-11-06 22:55:44 +01003780 /* If the state is FUTEX_STATE_EXITING then futex_exit_mutex is held */
3781 if (tsk->futex_state == FUTEX_STATE_EXITING)
3782 mutex_unlock(&tsk->futex_exit_mutex);
Thomas Gleixner18f69432019-11-06 22:55:41 +01003783 tsk->futex_state = FUTEX_STATE_DEAD;
3784}
3785
Thomas Gleixneraf8cbda2019-11-06 22:55:43 +01003786static void futex_cleanup_begin(struct task_struct *tsk)
Thomas Gleixner150d7152019-11-06 22:55:39 +01003787{
Thomas Gleixner18f69432019-11-06 22:55:41 +01003788 /*
Thomas Gleixner3f186d92019-11-06 22:55:44 +01003789 * Prevent various race issues against a concurrent incoming waiter
3790 * including live locks by forcing the waiter to block on
3791 * tsk->futex_exit_mutex when it observes FUTEX_STATE_EXITING in
3792 * attach_to_pi_owner().
3793 */
3794 mutex_lock(&tsk->futex_exit_mutex);
3795
3796 /*
Thomas Gleixner4a8e9912019-11-06 22:55:42 +01003797 * Switch the state to FUTEX_STATE_EXITING under tsk->pi_lock.
3798 *
3799 * This ensures that all subsequent checks of tsk->futex_state in
3800 * attach_to_pi_owner() must observe FUTEX_STATE_EXITING with
3801 * tsk->pi_lock held.
3802 *
3803 * It guarantees also that a pi_state which was queued right before
3804 * the state change under tsk->pi_lock by a concurrent waiter must
3805 * be observed in exit_pi_state_list().
Thomas Gleixner18f69432019-11-06 22:55:41 +01003806 */
3807 raw_spin_lock_irq(&tsk->pi_lock);
Thomas Gleixner4a8e9912019-11-06 22:55:42 +01003808 tsk->futex_state = FUTEX_STATE_EXITING;
Thomas Gleixner18f69432019-11-06 22:55:41 +01003809 raw_spin_unlock_irq(&tsk->pi_lock);
Thomas Gleixneraf8cbda2019-11-06 22:55:43 +01003810}
Thomas Gleixner18f69432019-11-06 22:55:41 +01003811
Thomas Gleixneraf8cbda2019-11-06 22:55:43 +01003812static void futex_cleanup_end(struct task_struct *tsk, int state)
3813{
3814 /*
3815 * Lockless store. The only side effect is that an observer might
3816 * take another loop until it becomes visible.
3817 */
3818 tsk->futex_state = state;
Thomas Gleixner3f186d92019-11-06 22:55:44 +01003819 /*
3820 * Drop the exit protection. This unblocks waiters which observed
3821 * FUTEX_STATE_EXITING to reevaluate the state.
3822 */
3823 mutex_unlock(&tsk->futex_exit_mutex);
Thomas Gleixneraf8cbda2019-11-06 22:55:43 +01003824}
Thomas Gleixner18f69432019-11-06 22:55:41 +01003825
Thomas Gleixneraf8cbda2019-11-06 22:55:43 +01003826void futex_exec_release(struct task_struct *tsk)
3827{
3828 /*
3829 * The state handling is done for consistency, but in the case of
3830 * exec() there is no way to prevent futher damage as the PID stays
3831 * the same. But for the unlikely and arguably buggy case that a
3832 * futex is held on exec(), this provides at least as much state
3833 * consistency protection which is possible.
3834 */
3835 futex_cleanup_begin(tsk);
3836 futex_cleanup(tsk);
3837 /*
3838 * Reset the state to FUTEX_STATE_OK. The task is alive and about
3839 * exec a new binary.
3840 */
3841 futex_cleanup_end(tsk, FUTEX_STATE_OK);
3842}
3843
3844void futex_exit_release(struct task_struct *tsk)
3845{
3846 futex_cleanup_begin(tsk);
3847 futex_cleanup(tsk);
3848 futex_cleanup_end(tsk, FUTEX_STATE_DEAD);
Thomas Gleixner150d7152019-11-06 22:55:39 +01003849}
3850
Pierre Peifferc19384b2007-05-09 02:35:02 -07003851long do_futex(u32 __user *uaddr, int op, u32 val, ktime_t *timeout,
Ingo Molnare2970f22006-06-27 02:54:47 -07003852 u32 __user *uaddr2, u32 val2, u32 val3)
Linus Torvalds1da177e2005-04-16 15:20:36 -07003853{
Thomas Gleixner81b40532012-02-15 12:17:09 +01003854 int cmd = op & FUTEX_CMD_MASK;
Darren Hartb41277d2010-11-08 13:10:09 -08003855 unsigned int flags = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003856
Eric Dumazet34f01cc2007-05-09 02:35:04 -07003857 if (!(op & FUTEX_PRIVATE_FLAG))
Darren Hartb41277d2010-11-08 13:10:09 -08003858 flags |= FLAGS_SHARED;
Eric Dumazet34f01cc2007-05-09 02:35:04 -07003859
Darren Hartb41277d2010-11-08 13:10:09 -08003860 if (op & FUTEX_CLOCK_REALTIME) {
3861 flags |= FLAGS_CLOCKRT;
Darren Hart337f1302015-12-18 13:36:37 -08003862 if (cmd != FUTEX_WAIT && cmd != FUTEX_WAIT_BITSET && \
3863 cmd != FUTEX_WAIT_REQUEUE_PI)
Darren Hartb41277d2010-11-08 13:10:09 -08003864 return -ENOSYS;
3865 }
Eric Dumazet34f01cc2007-05-09 02:35:04 -07003866
3867 switch (cmd) {
Thomas Gleixner59263b52012-02-15 12:08:34 +01003868 case FUTEX_LOCK_PI:
3869 case FUTEX_UNLOCK_PI:
3870 case FUTEX_TRYLOCK_PI:
3871 case FUTEX_WAIT_REQUEUE_PI:
3872 case FUTEX_CMP_REQUEUE_PI:
3873 if (!futex_cmpxchg_enabled)
3874 return -ENOSYS;
3875 }
3876
3877 switch (cmd) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07003878 case FUTEX_WAIT:
Thomas Gleixnercd6899852008-02-01 17:45:14 +01003879 val3 = FUTEX_BITSET_MATCH_ANY;
Gustavo A. R. Silvab6391862018-08-16 12:21:24 -05003880 /* fall through */
Thomas Gleixnercd6899852008-02-01 17:45:14 +01003881 case FUTEX_WAIT_BITSET:
Thomas Gleixner81b40532012-02-15 12:17:09 +01003882 return futex_wait(uaddr, flags, val, timeout, val3);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003883 case FUTEX_WAKE:
Thomas Gleixnercd6899852008-02-01 17:45:14 +01003884 val3 = FUTEX_BITSET_MATCH_ANY;
Gustavo A. R. Silvab6391862018-08-16 12:21:24 -05003885 /* fall through */
Thomas Gleixnercd6899852008-02-01 17:45:14 +01003886 case FUTEX_WAKE_BITSET:
Thomas Gleixner81b40532012-02-15 12:17:09 +01003887 return futex_wake(uaddr, flags, val, val3);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003888 case FUTEX_REQUEUE:
Thomas Gleixner81b40532012-02-15 12:17:09 +01003889 return futex_requeue(uaddr, flags, uaddr2, val, val2, NULL, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003890 case FUTEX_CMP_REQUEUE:
Thomas Gleixner81b40532012-02-15 12:17:09 +01003891 return futex_requeue(uaddr, flags, uaddr2, val, val2, &val3, 0);
Jakub Jelinek4732efbe2005-09-06 15:16:25 -07003892 case FUTEX_WAKE_OP:
Thomas Gleixner81b40532012-02-15 12:17:09 +01003893 return futex_wake_op(uaddr, flags, uaddr2, val, val2, val3);
Ingo Molnarc87e2832006-06-27 02:54:58 -07003894 case FUTEX_LOCK_PI:
Michael Kerrisk996636d2015-01-16 20:28:06 +01003895 return futex_lock_pi(uaddr, flags, timeout, 0);
Ingo Molnarc87e2832006-06-27 02:54:58 -07003896 case FUTEX_UNLOCK_PI:
Thomas Gleixner81b40532012-02-15 12:17:09 +01003897 return futex_unlock_pi(uaddr, flags);
Ingo Molnarc87e2832006-06-27 02:54:58 -07003898 case FUTEX_TRYLOCK_PI:
Michael Kerrisk996636d2015-01-16 20:28:06 +01003899 return futex_lock_pi(uaddr, flags, NULL, 1);
Darren Hart52400ba2009-04-03 13:40:49 -07003900 case FUTEX_WAIT_REQUEUE_PI:
3901 val3 = FUTEX_BITSET_MATCH_ANY;
Thomas Gleixner81b40532012-02-15 12:17:09 +01003902 return futex_wait_requeue_pi(uaddr, flags, val, timeout, val3,
3903 uaddr2);
Darren Hart52400ba2009-04-03 13:40:49 -07003904 case FUTEX_CMP_REQUEUE_PI:
Thomas Gleixner81b40532012-02-15 12:17:09 +01003905 return futex_requeue(uaddr, flags, uaddr2, val, val2, &val3, 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003906 }
Thomas Gleixner81b40532012-02-15 12:17:09 +01003907 return -ENOSYS;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003908}
3909
3910
Heiko Carstens17da2bd2009-01-14 14:14:10 +01003911SYSCALL_DEFINE6(futex, u32 __user *, uaddr, int, op, u32, val,
Arnd Bergmannbec2f7c2018-04-17 17:23:35 +02003912 struct __kernel_timespec __user *, utime, u32 __user *, uaddr2,
Heiko Carstens17da2bd2009-01-14 14:14:10 +01003913 u32, val3)
Linus Torvalds1da177e2005-04-16 15:20:36 -07003914{
Arnd Bergmannbec2f7c2018-04-17 17:23:35 +02003915 struct timespec64 ts;
Pierre Peifferc19384b2007-05-09 02:35:02 -07003916 ktime_t t, *tp = NULL;
Ingo Molnare2970f22006-06-27 02:54:47 -07003917 u32 val2 = 0;
Eric Dumazet34f01cc2007-05-09 02:35:04 -07003918 int cmd = op & FUTEX_CMD_MASK;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003919
Thomas Gleixnercd6899852008-02-01 17:45:14 +01003920 if (utime && (cmd == FUTEX_WAIT || cmd == FUTEX_LOCK_PI ||
Darren Hart52400ba2009-04-03 13:40:49 -07003921 cmd == FUTEX_WAIT_BITSET ||
3922 cmd == FUTEX_WAIT_REQUEUE_PI)) {
Davidlohr Buesoab51fba2015-06-29 23:26:02 -07003923 if (unlikely(should_fail_futex(!(op & FUTEX_PRIVATE_FLAG))))
3924 return -EFAULT;
Arnd Bergmannbec2f7c2018-04-17 17:23:35 +02003925 if (get_timespec64(&ts, utime))
Linus Torvalds1da177e2005-04-16 15:20:36 -07003926 return -EFAULT;
Arnd Bergmannbec2f7c2018-04-17 17:23:35 +02003927 if (!timespec64_valid(&ts))
Thomas Gleixner9741ef962006-03-31 02:31:32 -08003928 return -EINVAL;
Pierre Peifferc19384b2007-05-09 02:35:02 -07003929
Arnd Bergmannbec2f7c2018-04-17 17:23:35 +02003930 t = timespec64_to_ktime(ts);
Eric Dumazet34f01cc2007-05-09 02:35:04 -07003931 if (cmd == FUTEX_WAIT)
Thomas Gleixner5a7780e2008-02-13 09:20:43 +01003932 t = ktime_add_safe(ktime_get(), t);
Pierre Peifferc19384b2007-05-09 02:35:02 -07003933 tp = &t;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003934 }
3935 /*
Darren Hart52400ba2009-04-03 13:40:49 -07003936 * requeue parameter in 'utime' if cmd == FUTEX_*_REQUEUE_*.
Andreas Schwabf54f0982007-07-31 00:38:51 -07003937 * number of waiters to wake in 'utime' if cmd == FUTEX_WAKE_OP.
Linus Torvalds1da177e2005-04-16 15:20:36 -07003938 */
Andreas Schwabf54f0982007-07-31 00:38:51 -07003939 if (cmd == FUTEX_REQUEUE || cmd == FUTEX_CMP_REQUEUE ||
Darren Hartba9c22f2009-04-20 22:22:22 -07003940 cmd == FUTEX_CMP_REQUEUE_PI || cmd == FUTEX_WAKE_OP)
Ingo Molnare2970f22006-06-27 02:54:47 -07003941 val2 = (u32) (unsigned long) utime;
Linus Torvalds1da177e2005-04-16 15:20:36 -07003942
Pierre Peifferc19384b2007-05-09 02:35:02 -07003943 return do_futex(uaddr, op, val, tp, uaddr2, val2, val3);
Linus Torvalds1da177e2005-04-16 15:20:36 -07003944}
3945
Arnd Bergmann04e77122018-04-17 16:31:07 +02003946#ifdef CONFIG_COMPAT
3947/*
3948 * Fetch a robust-list pointer. Bit 0 signals PI futexes:
3949 */
3950static inline int
3951compat_fetch_robust_entry(compat_uptr_t *uentry, struct robust_list __user **entry,
3952 compat_uptr_t __user *head, unsigned int *pi)
3953{
3954 if (get_user(*uentry, head))
3955 return -EFAULT;
3956
3957 *entry = compat_ptr((*uentry) & ~1);
3958 *pi = (unsigned int)(*uentry) & 1;
3959
3960 return 0;
3961}
3962
3963static void __user *futex_uaddr(struct robust_list __user *entry,
3964 compat_long_t futex_offset)
3965{
3966 compat_uptr_t base = ptr_to_compat(entry);
3967 void __user *uaddr = compat_ptr(base + futex_offset);
3968
3969 return uaddr;
3970}
3971
3972/*
3973 * Walk curr->robust_list (very carefully, it's a userspace list!)
3974 * and mark any locks found there dead, and notify any waiters.
3975 *
3976 * We silently return on any sign of list-walking problem.
3977 */
Thomas Gleixnerba31c1a42019-11-06 22:55:36 +01003978static void compat_exit_robust_list(struct task_struct *curr)
Arnd Bergmann04e77122018-04-17 16:31:07 +02003979{
3980 struct compat_robust_list_head __user *head = curr->compat_robust_list;
3981 struct robust_list __user *entry, *next_entry, *pending;
3982 unsigned int limit = ROBUST_LIST_LIMIT, pi, pip;
3983 unsigned int uninitialized_var(next_pi);
3984 compat_uptr_t uentry, next_uentry, upending;
3985 compat_long_t futex_offset;
3986 int rc;
3987
3988 if (!futex_cmpxchg_enabled)
3989 return;
3990
3991 /*
3992 * Fetch the list head (which was registered earlier, via
3993 * sys_set_robust_list()):
3994 */
3995 if (compat_fetch_robust_entry(&uentry, &entry, &head->list.next, &pi))
3996 return;
3997 /*
3998 * Fetch the relative futex offset:
3999 */
4000 if (get_user(futex_offset, &head->futex_offset))
4001 return;
4002 /*
4003 * Fetch any possibly pending lock-add first, and handle it
4004 * if it exists:
4005 */
4006 if (compat_fetch_robust_entry(&upending, &pending,
4007 &head->list_op_pending, &pip))
4008 return;
4009
4010 next_entry = NULL; /* avoid warning with gcc */
4011 while (entry != (struct robust_list __user *) &head->list) {
4012 /*
4013 * Fetch the next entry in the list before calling
4014 * handle_futex_death:
4015 */
4016 rc = compat_fetch_robust_entry(&next_uentry, &next_entry,
4017 (compat_uptr_t __user *)&entry->next, &next_pi);
4018 /*
4019 * A pending lock might already be on the list, so
4020 * dont process it twice:
4021 */
4022 if (entry != pending) {
4023 void __user *uaddr = futex_uaddr(entry, futex_offset);
4024
Yang Taoca16d5b2019-11-06 22:55:35 +01004025 if (handle_futex_death(uaddr, curr, pi,
4026 HANDLE_DEATH_LIST))
Arnd Bergmann04e77122018-04-17 16:31:07 +02004027 return;
4028 }
4029 if (rc)
4030 return;
4031 uentry = next_uentry;
4032 entry = next_entry;
4033 pi = next_pi;
4034 /*
4035 * Avoid excessively long or circular lists:
4036 */
4037 if (!--limit)
4038 break;
4039
4040 cond_resched();
4041 }
4042 if (pending) {
4043 void __user *uaddr = futex_uaddr(pending, futex_offset);
4044
Yang Taoca16d5b2019-11-06 22:55:35 +01004045 handle_futex_death(uaddr, curr, pip, HANDLE_DEATH_PENDING);
Arnd Bergmann04e77122018-04-17 16:31:07 +02004046 }
4047}
4048
4049COMPAT_SYSCALL_DEFINE2(set_robust_list,
4050 struct compat_robust_list_head __user *, head,
4051 compat_size_t, len)
4052{
4053 if (!futex_cmpxchg_enabled)
4054 return -ENOSYS;
4055
4056 if (unlikely(len != sizeof(*head)))
4057 return -EINVAL;
4058
4059 current->compat_robust_list = head;
4060
4061 return 0;
4062}
4063
4064COMPAT_SYSCALL_DEFINE3(get_robust_list, int, pid,
4065 compat_uptr_t __user *, head_ptr,
4066 compat_size_t __user *, len_ptr)
4067{
4068 struct compat_robust_list_head __user *head;
4069 unsigned long ret;
4070 struct task_struct *p;
4071
4072 if (!futex_cmpxchg_enabled)
4073 return -ENOSYS;
4074
4075 rcu_read_lock();
4076
4077 ret = -ESRCH;
4078 if (!pid)
4079 p = current;
4080 else {
4081 p = find_task_by_vpid(pid);
4082 if (!p)
4083 goto err_unlock;
4084 }
4085
4086 ret = -EPERM;
4087 if (!ptrace_may_access(p, PTRACE_MODE_READ_REALCREDS))
4088 goto err_unlock;
4089
4090 head = p->compat_robust_list;
4091 rcu_read_unlock();
4092
4093 if (put_user(sizeof(*head), len_ptr))
4094 return -EFAULT;
4095 return put_user(ptr_to_compat(head), head_ptr);
4096
4097err_unlock:
4098 rcu_read_unlock();
4099
4100 return ret;
4101}
Arnd Bergmannbec2f7c2018-04-17 17:23:35 +02004102#endif /* CONFIG_COMPAT */
Arnd Bergmann04e77122018-04-17 16:31:07 +02004103
Arnd Bergmannbec2f7c2018-04-17 17:23:35 +02004104#ifdef CONFIG_COMPAT_32BIT_TIME
Arnd Bergmann8dabe722019-01-07 00:33:08 +01004105SYSCALL_DEFINE6(futex_time32, u32 __user *, uaddr, int, op, u32, val,
Arnd Bergmann04e77122018-04-17 16:31:07 +02004106 struct old_timespec32 __user *, utime, u32 __user *, uaddr2,
4107 u32, val3)
4108{
Arnd Bergmannbec2f7c2018-04-17 17:23:35 +02004109 struct timespec64 ts;
Arnd Bergmann04e77122018-04-17 16:31:07 +02004110 ktime_t t, *tp = NULL;
4111 int val2 = 0;
4112 int cmd = op & FUTEX_CMD_MASK;
4113
4114 if (utime && (cmd == FUTEX_WAIT || cmd == FUTEX_LOCK_PI ||
4115 cmd == FUTEX_WAIT_BITSET ||
4116 cmd == FUTEX_WAIT_REQUEUE_PI)) {
Arnd Bergmannbec2f7c2018-04-17 17:23:35 +02004117 if (get_old_timespec32(&ts, utime))
Arnd Bergmann04e77122018-04-17 16:31:07 +02004118 return -EFAULT;
Arnd Bergmannbec2f7c2018-04-17 17:23:35 +02004119 if (!timespec64_valid(&ts))
Arnd Bergmann04e77122018-04-17 16:31:07 +02004120 return -EINVAL;
4121
Arnd Bergmannbec2f7c2018-04-17 17:23:35 +02004122 t = timespec64_to_ktime(ts);
Arnd Bergmann04e77122018-04-17 16:31:07 +02004123 if (cmd == FUTEX_WAIT)
4124 t = ktime_add_safe(ktime_get(), t);
4125 tp = &t;
4126 }
4127 if (cmd == FUTEX_REQUEUE || cmd == FUTEX_CMP_REQUEUE ||
4128 cmd == FUTEX_CMP_REQUEUE_PI || cmd == FUTEX_WAKE_OP)
4129 val2 = (int) (unsigned long) utime;
4130
4131 return do_futex(uaddr, op, val, tp, uaddr2, val2, val3);
4132}
Arnd Bergmannbec2f7c2018-04-17 17:23:35 +02004133#endif /* CONFIG_COMPAT_32BIT_TIME */
Arnd Bergmann04e77122018-04-17 16:31:07 +02004134
Heiko Carstens03b8c7b2014-03-02 13:09:47 +01004135static void __init futex_detect_cmpxchg(void)
4136{
4137#ifndef CONFIG_HAVE_FUTEX_CMPXCHG
4138 u32 curval;
4139
4140 /*
4141 * This will fail and we want it. Some arch implementations do
4142 * runtime detection of the futex_atomic_cmpxchg_inatomic()
4143 * functionality. We want to know that before we call in any
4144 * of the complex code paths. Also we want to prevent
4145 * registration of robust lists in that case. NULL is
4146 * guaranteed to fault and we get -EFAULT on functional
4147 * implementation, the non-functional ones will return
4148 * -ENOSYS.
4149 */
4150 if (cmpxchg_futex_value_locked(&curval, NULL, 0, 0) == -EFAULT)
4151 futex_cmpxchg_enabled = 1;
4152#endif
4153}
4154
Benjamin Herrenschmidtf6d107f2008-03-27 14:52:15 +11004155static int __init futex_init(void)
Linus Torvalds1da177e2005-04-16 15:20:36 -07004156{
Heiko Carstens63b1a812014-01-16 14:54:50 +01004157 unsigned int futex_shift;
Davidlohr Buesoa52b89e2014-01-12 15:31:23 -08004158 unsigned long i;
4159
4160#if CONFIG_BASE_SMALL
4161 futex_hashsize = 16;
4162#else
4163 futex_hashsize = roundup_pow_of_two(256 * num_possible_cpus());
4164#endif
4165
4166 futex_queues = alloc_large_system_hash("futex", sizeof(*futex_queues),
4167 futex_hashsize, 0,
4168 futex_hashsize < 256 ? HASH_SMALL : 0,
Heiko Carstens63b1a812014-01-16 14:54:50 +01004169 &futex_shift, NULL,
4170 futex_hashsize, futex_hashsize);
4171 futex_hashsize = 1UL << futex_shift;
Heiko Carstens03b8c7b2014-03-02 13:09:47 +01004172
4173 futex_detect_cmpxchg();
Thomas Gleixnera0c1e902008-02-23 15:23:57 -08004174
Davidlohr Buesoa52b89e2014-01-12 15:31:23 -08004175 for (i = 0; i < futex_hashsize; i++) {
Linus Torvalds11d46162014-03-20 22:11:17 -07004176 atomic_set(&futex_queues[i].waiters, 0);
Dima Zavin732375c2011-07-07 17:27:59 -07004177 plist_head_init(&futex_queues[i].chain);
Thomas Gleixner3e4ab742008-02-23 15:23:55 -08004178 spin_lock_init(&futex_queues[i].lock);
4179 }
4180
Linus Torvalds1da177e2005-04-16 15:20:36 -07004181 return 0;
4182}
Yang Yang25f71d12016-12-30 16:17:55 +08004183core_initcall(futex_init);