diff options
Diffstat (limited to 'kernel/futex/core.c')
| -rw-r--r-- | kernel/futex/core.c | 131 |
1 files changed, 84 insertions, 47 deletions
diff --git a/kernel/futex/core.c b/kernel/futex/core.c index 233b926f5624..f74ede3df161 100644 --- a/kernel/futex/core.c +++ b/kernel/futex/core.c @@ -48,23 +48,19 @@ #include <vdso/futex.h> +#include <asm/runtime-const.h> + #include "futex.h" #include "../locking/rtmutex_common.h" -/* - * The base of the bucket array and its size are always used together - * (after initialization only in futex_hash()), so ensure that they - * reside in the same cacheline. - */ -static struct { - unsigned long hashmask; - unsigned int hashshift; - struct futex_hash_bucket *queues[MAX_NUMNODES]; -} __futex_data __read_mostly __aligned(2*sizeof(long)); +static u32 __futex_mask __ro_after_init; +static u32 __futex_shift __ro_after_init; +static struct futex_hash_bucket **__futex_queues __ro_after_init; -#define futex_hashmask (__futex_data.hashmask) -#define futex_hashshift (__futex_data.hashshift) -#define futex_queues (__futex_data.queues) +static __always_inline struct futex_hash_bucket **futex_queues(void) +{ + return runtime_const_ptr(__futex_queues); +} struct futex_private_hash { int state; @@ -395,13 +391,13 @@ __futex_hash(union futex_key *key, struct futex_private_hash *fph, struct futex_ * NOTE: this isn't perfectly uniform, but it is fast and * handles sparse node masks. */ - node = (hash >> futex_hashshift) % nr_node_ids; + node = runtime_const_shift_right_32(hash, __futex_shift) % nr_node_ids; if (!node_possible(node)) { node = find_next_bit_wrap(node_possible_map.bits, nr_node_ids, node); } } - return &futex_queues[node][hash & futex_hashmask]; + return &futex_queues()[node][runtime_const_mask_32(hash, __futex_mask)]; } /** @@ -520,7 +516,7 @@ int get_futex_key(u32 __user *uaddr, unsigned int flags, union futex_key *key, * The futex address must be "naturally" aligned. */ key->both.offset = address % PAGE_SIZE; - if (unlikely((address % size) != 0)) + if (unlikely((address & (size-1)) != 0)) return -EINVAL; address -= key->both.offset; @@ -982,8 +978,11 @@ retry: return -1; /* - * Special case for regular (non PI) futexes. The unlock path in - * user space has two race scenarios: + * Special case for regular (non PI) futexes. Ordinarily, we do + * not perform any processing here unless the current thread was + * the owner of the futex (by the TID check below). + * + * However, the unlock path has three race scenarios: * * 1. The unlock path releases the user space futex value and * before it can execute the futex() syscall to wake up @@ -992,42 +991,70 @@ retry: * 2. A woken up waiter is killed before it can acquire the * futex in user space. * - * In the second case, the wake up notification could be generated - * by the unlock path in user space after setting the futex value - * to zero or by the kernel after setting the OWNER_DIED bit below. + * 3. A woken up waiter is killed in user space after another + * thread has acquired the futex, but before it can set + * FUTEX_WAITERS. + * + * Note that, if userspace uses the FUTEX_ROBUST_UNLOCK flag, we + * will not see case 1 here. + * + * In the second and third case, the wake up notification could + * be generated from any of: + * + * i. An ordinary futex wakeup after unlock (with or + * without FUTEX_ROBUST_UNLOCK) + * ii. A robust wakeup from another thread's death + * iii. A previous round through this special case + * + * As a result, the futex world will be in one of four states: * - * In both cases the TID validation below prevents a wakeup of - * potential waiters which can cause these waiters to block - * forever. + * A. The futex word is 0 (unlocked) + * B. The futex word is owned by another thread + * (FUTEX_WAITERS is not set) + * C. The futex word is owned by another thread + * (FUTEX_WAITERS set) + * D. The futex's owner died and OWNER_DIED is set + * (the owner part of the word is 0) * - * In both cases the following conditions are met: + * The key issue is that the kernel usually (at least from + * sources ii. and iii. or when so requested by userspace from + * source i.) only ever wakes *one* waiter at a time. If this + * waiter dies before acquiring the futex (or setting the + * FUTEX_WAITERS bit), the kernel *must* still wake the next + * waiter down the line to uphold the futex invariants and + * avoid lost wakeups. Note we do not need to handle state C, + * as it does not matter to us whether *we* successfully set + * the bit or a third thread did so in the meantime. * - * 1) task->futex.robust_list->list_op_pending != NULL - * @pending_op == true - * 2) The owner part of user space futex value == 0 + * Therefore, in these cases we must issue an additional + * futex_wake(). Note however that we *must not* set OWNER_DIED + * here. Our thread is *not* the owner of the futex. + * + * Thus to summarize, the conditions for needing the additional + * futex_wake() are: + * + * 1) @pending_op == true (the thread has not finished the + * mutex operation) + * 2) The futex word is in one of the states A, B or D * 3) Regular futex: @pi == false * - * If these conditions are met, it is safe to attempt waking up a - * potential waiter without touching the user space futex value and - * trying to set the OWNER_DIED bit. If the futex value is zero, - * the rest of the user space mutex state is consistent, so a woken - * waiter will just take over the uncontended futex. Setting the - * OWNER_DIED bit would create inconsistent state and malfunction - * of the user space owner died handling. Otherwise, the OWNER_DIED - * bit is already set, and the woken waiter is expected to deal with - * this. + * Note in particular that in all of the states A-D the owner + * portion of the futex word differs from our thread's TID + * (unless the actual owner has the same TID in another PID + * namespace, but we cannot currently distinguish that + * scenario), so this can be a special-case wakeup in the bail + * path of the ordinary TID check. */ owner = uval & FUTEX_TID_MASK; - if (pending_op && !pi && !owner) { - futex_wake(uaddr, FLAGS_SIZE_32 | FLAGS_SHARED, NULL, 1, - FUTEX_BITSET_MATCH_ANY); + if (owner != task_pid_vnr(curr)) { + if (pending_op && !pi && (!owner || !(uval & FUTEX_WAITERS))) { + futex_wake(uaddr, FLAGS_SIZE_32 | FLAGS_SHARED, NULL, 1, + FUTEX_BITSET_MATCH_ANY); + } return 0; } - if (owner != task_pid_vnr(curr)) - return 0; - /* * Ok, this dying thread is truly holding a futex * of interest. Set the OWNER_DIED bit atomically @@ -1921,7 +1948,7 @@ int futex_hash_allocate_default(void) * 16 <= threads * 4 <= global hash size */ buckets = roundup_pow_of_two(4 * threads); - buckets = clamp(buckets, 16, futex_hashmask + 1); + buckets = clamp(buckets, 16, __futex_mask + 1); if (current_buckets >= buckets) return 0; @@ -2019,10 +2046,21 @@ static int __init futex_init(void) hashsize = max(4, hashsize); hashsize = roundup_pow_of_two(hashsize); #endif - futex_hashshift = ilog2(hashsize); + __futex_mask = hashsize - 1; + __futex_shift = ilog2(hashsize); size = sizeof(struct futex_hash_bucket) * hashsize; order = get_order(size); + __futex_queues = kcalloc(nr_node_ids, sizeof(*__futex_queues), GFP_KERNEL); + + runtime_const_init(shift, __futex_shift); + runtime_const_init(mask, __futex_mask); + runtime_const_init(ptr, __futex_queues); + + barrier(); + + BUG_ON(!futex_queues()); + for_each_node(n) { struct futex_hash_bucket *table; @@ -2036,10 +2074,9 @@ static int __init futex_init(void) for (i = 0; i < hashsize; i++) futex_hash_bucket_init(&table[i]); - futex_queues[n] = table; + futex_queues()[n] = table; } - futex_hashmask = hashsize - 1; pr_info("futex hash table entries: %lu (%lu bytes on %d NUMA nodes, total %lu KiB, %s).\n", hashsize, size, num_possible_nodes(), size * num_possible_nodes() / 1024, order > MAX_PAGE_ORDER ? "vmalloc" : "linear"); |