[RFC,01/13] futex2: Implement wait and wake functions

Create a new set of futex syscalls known as futex2. This new interface
is aimed to implement a more maintainable code, while removing obsolete
features and expanding it with new functionalities.

Implements wait and wake semantics for futexes, along with the base
infrastructure for future operations. The whole wait path is designed to
be used by N waiters, thus making easier to implement vectorized wait.

* Syscalls implemented by this patch:

- futex_wait(void *uaddr, unsigned int val, unsigned int flags,
	     struct timespec *timo)

   The user thread is put to sleep, waiting for a futex_wake() at uaddr,
   if the value at *uaddr is the same as val (otherwise, the syscall
   returns immediately with -EAGAIN). timo is an optional timeout value
   for the operation.

   Return 0 on success, error code otherwise.

 - futex_wake(void *uaddr, unsigned long nr_wake, unsigned int flags)

   Wake `nr_wake` threads waiting at uaddr.

   Return the number of woken threads on success, error code otherwise.

** The `flag` argument

 The flag is used to specify the size of the futex word
 (FUTEX_[8, 16, 32]). It's mandatory to define one, since there's no
 default size.

 By default, the timeout uses a monotonic clock, but can be used as a
 realtime one by using the FUTEX_REALTIME_CLOCK flag.

 By default, futexes are of the private type, that means that this user
 address will be accessed by threads that shares the same memory region.
 This allows for some internal optimizations, so they are faster.
 However, if the address needs to be shared with different processes
 (like using `mmap()` or `shm()`), they need to be defined as shared and
 the flag FUTEX_SHARED_FLAG is used to set that.

 By default, the operation has no NUMA-awareness, meaning that the user
 can't choose the memory node where the kernel side futex data will be
 stored. The user can choose the node where it wants to operate by
 setting the FUTEX_NUMA_FLAG and using the following structure (where X
 can be 8, 16, or 32):

  struct futexX_numa {
          __uX value;
          __sX hint;
  };

 This structure should be passed at the `void *uaddr` of futex
 functions. The address of the structure will be used to be waited/waken
 on, and the `value` will be compared to `val` as usual. The `hint`
 member is used to defined which node the futex will use. When waiting,
 the futex will be registered on a kernel-side table stored on that
 node; when waking, the futex will be searched for on that given table.
 That means that there's no redundancy between tables, and the wrong
 `hint` value will led to undesired behavior.  Userspace is responsible
 for dealing with node migrations issues that may occur. `hint` can
 range from [0, MAX_NUMA_NODES], for specifying a node, or -1, to use
 the same node the current process is using.

 When not using FUTEX_NUMA_FLAG on a NUMA system, the futex will be
 stored on a global table on some node, defined at compilation time.

** The `timo` argument

As per the Y2038 work done in the kernel, new interfaces shouldn't add
timeout options known to be buggy. Given that, `timo` should be a 64bit
timeout at all platforms, using an absolute timeout value.

Signed-off-by: André Almeida <andrealmeid@collabora.com>
---
 MAINTAINERS                                   |   2 +-
 arch/arm/tools/syscall.tbl                    |   2 +
 arch/arm64/include/asm/unistd.h               |   2 +-
 arch/arm64/include/asm/unistd32.h             |   4 +
 arch/x86/entry/syscalls/syscall_32.tbl        |   2 +
 arch/x86/entry/syscalls/syscall_64.tbl        |   2 +
 include/linux/syscalls.h                      |   7 +
 include/uapi/asm-generic/unistd.h             |   8 +-
 include/uapi/linux/futex.h                    |  56 ++
 init/Kconfig                                  |   7 +
 kernel/Makefile                               |   1 +
 kernel/futex2.c                               | 625 ++++++++++++++++++
 kernel/sys_ni.c                               |   4 +
 tools/include/uapi/asm-generic/unistd.h       |   8 +-
 .../arch/x86/entry/syscalls/syscall_64.tbl    |   2 +
 15 files changed, 728 insertions(+), 4 deletions(-)
 create mode 100644 kernel/futex2.c

André Almeida <andrealmeid@collabora.com> writes:

> Create a new set of futex syscalls known as futex2. This new interface
> is aimed to implement a more maintainable code, while removing obsolete
> features and expanding it with new functionalities.

Hi André.  Some comments below

> +/* kernel/futex2.c */
> +asmlinkage long sys_futex_wait(void __user *uaddr, unsigned int val,
> +			       unsigned int flags,
> +			       struct __kernel_timespec __user __user *timo);

Duplicated __user attribute

> +asmlinkage long sys_futex_wake(void __user *uaddr, unsigned int nr_wake,
> +			       unsigned int flags);
> +
>  /* kernel/hrtimer.c */
>  asmlinkage long sys_nanosleep(struct __kernel_timespec __user *rqtp,
>  			      struct __kernel_timespec __user *rmtp);
> diff --git a/include/uapi/asm-generic/unistd.h b/include/uapi/asm-generic/unistd.h
> index 728752917785..57e19200f7e4 100644
> --- a/include/uapi/asm-generic/unistd.h
> +++ b/include/uapi/asm-generic/unistd.h
> @@ -862,8 +862,14 @@ __SYSCALL(__NR_process_madvise, sys_process_madvise)
>  #define __NR_epoll_pwait2 441
>  __SC_COMP(__NR_epoll_pwait2, sys_epoll_pwait2, compat_sys_epoll_pwait2)
>  
> +#define __NR_futex_wait 442
> +__SYSCALL(__NR_futex_wait, sys_futex_wait)
> +
> +#define __NR_futex_wake 443
> +__SYSCALL(__NR_futex_wake, sys_futex_wake)
> +
>  #undef __NR_syscalls
> -#define __NR_syscalls 442
> +#define __NR_syscalls 444
>  
>  /*
>   * 32 bit systems traditionally used different
> diff --git a/include/uapi/linux/futex.h b/include/uapi/linux/futex.h
> index a89eb0accd5e..9fbdaaf4f254 100644
> --- a/include/uapi/linux/futex.h
> +++ b/include/uapi/linux/futex.h
> @@ -41,6 +41,62 @@
>  #define FUTEX_CMP_REQUEUE_PI_PRIVATE	(FUTEX_CMP_REQUEUE_PI | \
>  					 FUTEX_PRIVATE_FLAG)
>  
> +/* Size argument to futex2 syscall */
> +#define FUTEX_8		0
> +#define FUTEX_16	1
> +#define FUTEX_32	2
> +
> +#define FUTEX_SIZE_MASK	0x3
> +
> +#define FUTEX_SHARED_FLAG 8
> +
> +#define FUTEX_NUMA_FLAG 16
> +
> +/**
> + * struct futexXX_numa - struct for NUMA-aware futex operation
> + * @value: futex value
> + * @hint:  node id to operate
> + */
> +
> +struct futex8_numa {
> +	__u8 value;
> +	__s8 hint;
> +};
> +
> +struct futex16_numa {
> +	__u16 value;
> +	__s16 hint;
> +};
> +
> +struct futex32_numa {
> +	__u32 value;
> +	__s32 hint;
> +};

This patchset doesn't use these structures as far as I can see.  Maybe
these should be on a later patchset, when there is actual support for
numa awareness ?

> +
> +#define FUTEX_WAITV_MAX 128
> +
> +/**
> + * struct futex_waitv - A waiter for vectorized wait
> + * @uaddr: User address to wait on
> + * @val:   Expected value at uaddr
> + * @flags: Flags for this waiter
> + */
> +struct futex_waitv {
> +	void *uaddr;
> +	unsigned int val;
> +	unsigned int flags;
> +};

Shouldn't this be in patch 3?
> +
> +/**
> + * struct futex_requeue - Define an address and its flags for requeue operation
> + * @uaddr: User address of one of the requeue arguments
> + * @flags: Flags for this address
> + */
> +struct futex_requeue {
> +	void *uaddr;
> +	unsigned int flags;
> +};

Shouldn't this be in patch 4?

> +/**
> + * struct futexv_head - List of futexes to be waited
> + * @task:    Task to be awaken
> + * @hint:    Was someone on this list awakened?
> + * @objects: List of futexes
> + */
> +struct futexv_head {
> +	struct task_struct *task;
> +	bool hint;
> +	struct futex_waiter objects[0];
> +};

this structure is also used for a single futex.  maybe struct futex_waiter_head?

> +
> +/**
> + * struct futex_bucket - A bucket of futex's hash table
> + * @waiters: Number of waiters in the bucket
> + * @lock:    Bucket lock
> + * @list:    List of waiters on this bucket
> + */
> +struct futex_bucket {
> +	atomic_t waiters;
> +	spinlock_t lock;
> +	struct list_head list;
> +};
> +
> +/**
> + * struct futex_single_waiter - Wrapper for a futexv_head of one element
> + * @futexv: Single futexv element
> + * @waiter: Single waiter element
> + */
> +struct futex_single_waiter {
> +	struct futexv_head futexv;
> +	struct futex_waiter waiter;
> +} __packed;

Is this struct necessary?  can't you just allocate the necessary space,
i.e. a struct futexv_head with 1 futexv_head->object?
> +
> +/* Mask for futex2 flag operations */
> +#define FUTEX2_MASK (FUTEX_SIZE_MASK | FUTEX_SHARED_FLAG | \
> +		     FUTEX_CLOCK_REALTIME)

SHARED_FLAG should be in patch 2

> +
> +/* Mask for sys_futex_waitv flag */
> +#define FUTEXV_MASK (FUTEX_CLOCK_REALTIME)
> +
> +/* Mask for each futex in futex_waitv list */
> +#define FUTEXV_WAITER_MASK (FUTEX_SIZE_MASK | FUTEX_SHARED_FLAG)
> +
> +struct futex_bucket *futex_table;
> +unsigned int futex2_hashsize;
> +
> +/*
> + * Reflects a new waiter being added to the waitqueue.
> + */
> +static inline void bucket_inc_waiters(struct futex_bucket *bucket)
> +{
> +#ifdef CONFIG_SMP
> +	atomic_inc(&bucket->waiters);
> +	/*
> +	 * Issue a barrier after adding so futex_wake() will see that the
> +	 * value had increased
> +	 */
> +	smp_mb__after_atomic();
> +#endif
> +}
> +
> +/*
> + * Reflects a waiter being removed from the waitqueue by wakeup
> + * paths.
> + */
> +static inline void bucket_dec_waiters(struct futex_bucket *bucket)
> +{
> +#ifdef CONFIG_SMP
> +	atomic_dec(&bucket->waiters);
> +#endif
> +}
> +
> +/*
> + * Get the number of waiters in a bucket
> + */
> +static inline int bucket_get_waiters(struct futex_bucket *bucket)
> +{
> +#ifdef CONFIG_SMP
> +	/*
> +	 * Issue a barrier before reading so we get an updated value from
> +	 * futex_wait()
> +	 */
> +	smp_mb();
> +	return atomic_read(&bucket->waiters);
> +#else
> +	return 1;
> +#endif
> +}
> +
> +/**
> + * futex_get_bucket - Check if the user address is valid, prepare internal
> + *                    data and calculate the hash
> + * @uaddr:   futex user address
> + * @key:     data that uniquely identifies a futex
> + *
> + * Return: address of bucket on success, error code otherwise
> + */
> +static struct futex_bucket *futex_get_bucket(void __user *uaddr,
> +					     struct futex_key *key)
> +{
> +	uintptr_t address = (uintptr_t)uaddr;
> +	u32 hash_key;
> +
> +	/* Checking if uaddr is valid and accessible */
> +	if (unlikely(!IS_ALIGNED(address, sizeof(u32))))
> +		return ERR_PTR(-EINVAL);
> +	if (unlikely(!access_ok(address, sizeof(u32))))
> +		return ERR_PTR(-EFAULT);

This says the code only supports 32-bit.  So, maybe drop the other
FUTEX_SIZE defines for now

> +
> +	key->offset = address % PAGE_SIZE;
> +	address -= key->offset;
> +	key->pointer = (u64)address;
> +	key->index = (unsigned long)current->mm;

Why split the key in offset and pointer and waste 1/3 more space to
store each key?

> +
> +	/* Generate hash key for this futex using uaddr and current->mm */
> +	hash_key = jhash2((u32 *)key, sizeof(*key) / sizeof(u32), 0);
> +
> +	/* Since HASH_SIZE is 2^n, subtracting 1 makes a perfect bit mask */
> +	return &futex_table[hash_key & (futex2_hashsize - 1)];

If someone inadvertely changes futex2_hashsize to something not 2^n this
will silently break.  futex2_hashsize should be constant and you need
a BUILD_BUG_ON().

> +static int futex_enqueue(struct futexv_head *futexv, unsigned int nr_futexes,
> +			 int *awakened)
> +{
> +	int i, ret;
> +	u32 uval, *uaddr, val;
> +	struct futex_bucket *bucket;
> +
> +retry:
> +	set_current_state(TASK_INTERRUPTIBLE);
> +
> +	for (i = 0; i < nr_futexes; i++) {
> +		uaddr = (u32 * __user)futexv->objects[i].uaddr;
> +		val = (u32)futexv->objects[i].val;
> +
> +		bucket = futexv->objects[i].bucket;
> +
> +		bucket_inc_waiters(bucket);
> +		spin_lock(&bucket->lock);
> +
> +		ret = futex_get_user(&uval, uaddr);
> +
> +		if (unlikely(ret)) {
> +			spin_unlock(&bucket->lock);
> +
> +			bucket_dec_waiters(bucket);
> +			__set_current_state(TASK_RUNNING);
> +			*awakened = futex_dequeue_multiple(futexv, i);
> +
> +			if (__get_user(uval, uaddr))
> +				return -EFAULT;
> +
> +			if (*awakened >= 0)
> +				return 1;

If you are awakened, you don't need to waste time with trying to get the
next key.


> +/**
> + * futex_wait - Setup the timer (if there's one) and wait on a list of futexes
> + * @futexv:     List of futexes
> + * @nr_futexes: Length of futexv
> + * @timo:	Timeout
> + * @flags:	Timeout flags
> + *
> + * Return:
> + * * 0 >= - Hint of which futex woke us
> + * * 0 <  - Error code
> + */
> +static int futex_set_timer_and_wait(struct futexv_head *futexv,
> +				    unsigned int nr_futexes,
> +				    struct __kernel_timespec __user *timo,
> +				    unsigned int flags)
> +{
> +	struct hrtimer_sleeper timeout;
> +	int ret;
> +
> +	if (timo) {
> +		ret = futex_setup_time(timo, &timeout, flags);
> +		if (ret)
> +			return ret;
> +	}
> +
> +	ret = __futex_wait(futexv, nr_futexes, timo ? &timeout : NULL);
> +
> +	if (timo)
> +		hrtimer_cancel(&timeout.timer);
> +
> +	return ret;
> +}

I'm having a hard time understanding why this function exists.  part of
the futex is set up outside of it, part inside.  Not sure if this isn't
just part of sys_futex_wait.

Thanks,

On Mon, Feb 15, 2021 at 12:23:52PM -0300, André Almeida wrote:
> +static int __futex_wait(struct futexv_head *futexv, unsigned int nr_futexes,
> +			struct hrtimer_sleeper *timeout)
> +{
> +	int ret;
> +
> +	while (1) {
> +		int awakened = -1;
> +

Might be easier to understand if the set_current_state() is here,
instead of squirreled away in futex_enqueue().

> +		ret = futex_enqueue(futexv, nr_futexes, &awakened);
> +
> +		if (ret) {
> +			if (awakened >= 0)
> +				return awakened;
> +			return ret;
> +		}
> +
> +		/* Before sleeping, check if someone was woken */
> +		if (!futexv->hint && (!timeout || timeout->task))
> +			freezable_schedule();
> +
> +		__set_current_state(TASK_RUNNING);

This is typically after the loop.

> +
> +		/*
> +		 * One of those things triggered this wake:
> +		 *
> +		 * * We have been removed from the bucket. futex_wake() woke
> +		 *   us. We just need to dequeue and return 0 to userspace.
> +		 *
> +		 * However, if no futex was dequeued by a futex_wake():
> +		 *
> +		 * * If the there's a timeout and it has expired,
> +		 *   return -ETIMEDOUT.
> +		 *
> +		 * * If there is a signal pending, something wants to kill our
> +		 *   thread, return -ERESTARTSYS.
> +		 *
> +		 * * If there's no signal pending, it was a spurious wake
> +		 *   (scheduler gave us a change to do some work, even if we

chance?

> +		 *   don't want to). We need to remove ourselves from the
> +		 *   bucket and add again, to prevent losing wakeups in the
> +		 *   meantime.
> +		 */

Anyway, doing a dequeue and enqueue for spurious wakes is a bit of an
anti-pattern that can lead to starvation. I've not actually looked at
much detail yet as this is my first read-through, but did figure I'd
mention it.

> +
> +		ret = futex_dequeue_multiple(futexv, nr_futexes);
> +
> +		/* Normal wake */
> +		if (ret >= 0)
> +			return ret;
> +
> +		if (timeout && !timeout->task)
> +			return -ETIMEDOUT;
> +
> +		if (signal_pending(current))
> +			return -ERESTARTSYS;
> +
> +		/* Spurious wake, do everything again */
> +	}
> +}

On Mon, Feb 15, 2021 at 12:23:52PM -0300, André Almeida wrote:

> +static int futex_dequeue_multiple(struct futexv_head *futexv, unsigned int nr)
> +{
> +	int i, ret = -1;
> +
> +	for (i = 0; i < nr; i++) {
> +		spin_lock(&futexv->objects[i].bucket->lock);
> +		if (!list_empty_careful(&futexv->objects[i].list)) {
> +			list_del_init_careful(&futexv->objects[i].list);
> +			bucket_dec_waiters(futexv->objects[i].bucket);

What's with the careful? AFAICT all sites have that bucket->lock.

> +		} else {
> +			ret = i;
> +		}
> +		spin_unlock(&futexv->objects[i].bucket->lock);
> +	}
> +
> +	return ret;
> +}

> +static int futex_enqueue(struct futexv_head *futexv, unsigned int nr_futexes,
> +			 int *awakened)
> +{
> +	int i, ret;
> +	u32 uval, *uaddr, val;
> +	struct futex_bucket *bucket;
> +
> +retry:
> +	set_current_state(TASK_INTERRUPTIBLE);
> +
> +	for (i = 0; i < nr_futexes; i++) {
> +		uaddr = (u32 * __user)futexv->objects[i].uaddr;
> +		val = (u32)futexv->objects[i].val;
> +
> +		bucket = futexv->objects[i].bucket;
> +
> +		bucket_inc_waiters(bucket);
> +		spin_lock(&bucket->lock);
> +
> +		ret = futex_get_user(&uval, uaddr);
> +
> +		if (unlikely(ret)) {
> +			spin_unlock(&bucket->lock);
> +
> +			bucket_dec_waiters(bucket);
> +			__set_current_state(TASK_RUNNING);
> +			*awakened = futex_dequeue_multiple(futexv, i);
> +
> +			if (__get_user(uval, uaddr))
> +				return -EFAULT;
> +
> +			if (*awakened >= 0)
> +				return 1;
> +
> +			goto retry;
> +		}
> +
> +		if (uval != val) {
> +			spin_unlock(&bucket->lock);
> +
> +			bucket_dec_waiters(bucket);
> +			__set_current_state(TASK_RUNNING);
> +			*awakened = futex_dequeue_multiple(futexv, i);
> +
> +			if (*awakened >= 0)
> +				return 1;
> +
> +			return -EAGAIN;
> +		}
> +
> +		list_add_tail(&futexv->objects[i].list, &bucket->list);

and here

> +		spin_unlock(&bucket->lock);
> +	}
> +
> +	return 0;
> +}
> +

> +static void futex_mark_wake(struct futex_waiter *waiter,
> +			    struct futex_bucket *bucket,
> +			    struct wake_q_head *wake_q)
> +{
> +	struct task_struct *task;
> +	struct futexv_head *parent = futex_get_parent((uintptr_t)waiter,
> +						      waiter->index);
> +

	lockdep_assert_held(&bucket->lock);

> +	parent->hint = true;
> +	task = parent->task;
> +	get_task_struct(task);
> +	list_del_init_careful(&waiter->list);

and here

> +	wake_q_add_safe(wake_q, task);
> +	bucket_dec_waiters(bucket);
> +}

On Mon, Feb 15, 2021 at 12:23:52PM -0300, André Almeida wrote:
> Create a new set of futex syscalls known as futex2. This new interface
> is aimed to implement a more maintainable code, while removing obsolete
> features and expanding it with new functionalities.
> 
> Implements wait and wake semantics for futexes, along with the base
> infrastructure for future operations.

> +	futex_table = alloc_large_system_hash("futex2", sizeof(struct futex_bucket),
> +					      futex2_hashsize, 0,
> +					      futex2_hashsize < 256 ? HASH_SMALL : 0,
> +					      &futex_shift, NULL,
> +					      futex2_hashsize, futex2_hashsize);

So why are we implementing a whole second infrastrure and doubling the
memory footprint of all this?

Sure, futex.c is a pain in the ass, but most of that is not because of
the interface, most of it is having to deal with sharing state with
userspace and that being fundamentally unreliable.

Once you want to add {,UN}LOCK{,_PI} and robust futex support, you're
back to it being a giant rats nest of corner cases. Thinking a new
interface can solve any of that is naive.

So while I'm in favour of adding a new interface, I'm not sure I see
benefit of reimplementing the basics, sure it seems simpler now, but
that's because you've not implemented all the 'fun' stuff.

On 2021-02-16 10:56:14 [+0100], Peter Zijlstra wrote:
> So while I'm in favour of adding a new interface, I'm not sure I see
> benefit of reimplementing the basics, sure it seems simpler now, but
> that's because you've not implemented all the 'fun' stuff.

The last attempt tried to hide the updated interface within libc which
did not fly. The global hash state is one of the problems because it
leads to hash collisions of two unrelated locks.
It will get simpler if we go into the kernel for each lock/unlock
operation but this might not very good in terms of performance for locks
which are mostly uncontended. I'm not sure how much we can cheat in
terms of VDSO.

Sebastian

On Tue, Feb 16, 2021 at 11:20:44AM +0100, Sebastian Andrzej Siewior wrote:
> On 2021-02-16 10:56:14 [+0100], Peter Zijlstra wrote:
> > So while I'm in favour of adding a new interface, I'm not sure I see
> > benefit of reimplementing the basics, sure it seems simpler now, but
> > that's because you've not implemented all the 'fun' stuff.
> 
> The last attempt tried to hide the updated interface within libc which
> did not fly. The global hash state is one of the problems because it
> leads to hash collisions of two unrelated locks.
> It will get simpler if we go into the kernel for each lock/unlock
> operation but this might not very good in terms of performance for locks
> which are mostly uncontended. I'm not sure how much we can cheat in
> terms of VDSO.

I'm sorry, but I'm failing to understand any of that.

How is adding a second global hash going to solve anything? Also, the
LOCK/UNLOCK primitives as we have them today very much rely on a
userspace fast path, and I don't see that changing. Only on contention
do we call into the kernel.

The advantage of the new interface is having that NUMA word along with
the Futex word, in which we can store the node_id for the hash we
stuffed the futex in, which is awesome, but that too doesn't need a
re-implementation of all the basics.

And getting rid of the super multiplexer is also nice.

But re-implementing all the basic stuff again, not so nice.

Peter Zijlstra <peterz@infradead.org> writes:

> On Mon, Feb 15, 2021 at 12:23:52PM -0300, André Almeida wrote:
>> Create a new set of futex syscalls known as futex2. This new interface
>> is aimed to implement a more maintainable code, while removing obsolete
>> features and expanding it with new functionalities.
>> 
>> Implements wait and wake semantics for futexes, along with the base
>> infrastructure for future operations.
>
>> +	futex_table = alloc_large_system_hash("futex2", sizeof(struct futex_bucket),
>> +					      futex2_hashsize, 0,
>> +					      futex2_hashsize < 256 ? HASH_SMALL : 0,
>> +					      &futex_shift, NULL,
>> +					      futex2_hashsize, futex2_hashsize);
>
> So why are we implementing a whole second infrastrure and doubling the
> memory footprint of all this?
>
> Sure, futex.c is a pain in the ass, but most of that is not because of
> the interface, most of it is having to deal with sharing state with
> userspace and that being fundamentally unreliable.
>
> Once you want to add {,UN}LOCK{,_PI} and robust futex support, you're
> back to it being a giant rats nest of corner cases. Thinking a new
> interface can solve any of that is naive.
>
> So while I'm in favour of adding a new interface, I'm not sure I see
> benefit of reimplementing the basics, sure it seems simpler now, but
> that's because you've not implemented all the 'fun' stuff.

Peter,

I think there was a question of how we'd introduce this new interface,
since the community is wary of introducing new features in the original
futex code.  The approach we discussed in the last LPC was writing a new
code from scratch that could even sit on the RT tree while it get
stabilized.

The code base duplication, and - perhaps more importantly - the double
memory footprint is bad, for sure.  But considering this implementation
modifies what is enqueued to separate the waiter structure from its
(potentially multiple) keys, we'd be looking at large changes in the
original futex code, which doesn't seem (as it should be) welcome by the
community. At least this feedback was the reason we started working on
futex2.

So, my question is, how else should we present this interface, if not in
a new code base?  If it is just a matter of integrating it into the
original code, I'd go back and ask why this new interface was made a
prerequisite for the futex wait multiple patches André originally wanted
to merge?  For sure, the multiplexing interface is not the sole reason
that stopped that work from being accepted.  The bigger goal was not
increasing the mess and not causing new bugs in the existing overcomplex
futex implementation.

Regarding NUMA support, I wouldn't expect André to implement all other
features before getting something upstreamable in the list.  His
interest in futex is directed at solving the multiple wait problem, but
consider he has already gone way beyond that by re-implementing the
basics of a new interface.  Collabora is willing to do the heavy lifting
necessary (within reason) on this patchset to get something the
community accepts, including NUMA support, provided we also get
semantics to fix the problem we are trying to solve.  But for that, we
gonna need more directioning on what the community is willing to accept
not only regarding the interface, but on internals too.

Hi Gabriel,

Às 16:59 de 15/02/21, Gabriel Krisman Bertazi escreveu:
> André Almeida <andrealmeid@collabora.com> writes:
> 
>> +/**
>> + * struct futexv_head - List of futexes to be waited
>> + * @task:    Task to be awaken
>> + * @hint:    Was someone on this list awakened?
>> + * @objects: List of futexes
>> + */
>> +struct futexv_head {
>> +	struct task_struct *task;
>> +	bool hint;
>> +	struct futex_waiter objects[0];
>> +};
> 
> this structure is also used for a single futex.  maybe struct futex_waiter_head?

One could argue that a single futex is a futexv of one element, but I 
can see that futex_waiter_head makes more sense. Fixed.

>> +/**
>> + * struct futex_single_waiter - Wrapper for a futexv_head of one element
>> + * @futexv: Single futexv element
>> + * @waiter: Single waiter element
>> + */
>> +struct futex_single_waiter {
>> +	struct futexv_head futexv;
>> +	struct futex_waiter waiter;
>> +} __packed;
> 
> Is this struct necessary?  can't you just allocate the necessary space,
> i.e. a struct futexv_head with 1 futexv_head->object?

I don't feel that makes sense to use dynamic allocation for a fixed 
sized memory. Given that, using this struct was the way I found to have 
a futexv_head of a single element in a static allocation fashion.

>> +
>> +	key->offset = address % PAGE_SIZE;
>> +	address -= key->offset;
>> +	key->pointer = (u64)address;
>> +	key->index = (unsigned long)current->mm;
> 
> Why split the key in offset and pointer and waste 1/3 more space to
> store each key?
> 

We need three fields for storing the shared key in the current design, 
and given that the futex key currently lives inside struct futex_waiter, 
private and shared keys need to use the same amount of space. Even if I 
don't use offset for now, the next patch would expand the memory anyway. 
I see that the way I organized the patches made this confusing.

To avoid that we could allocate the key space in futex_wait and make 
futex key point there.

>> +
>> +	/* Generate hash key for this futex using uaddr and current->mm */
>> +	hash_key = jhash2((u32 *)key, sizeof(*key) / sizeof(u32), 0);
>> +
>> +	/* Since HASH_SIZE is 2^n, subtracting 1 makes a perfect bit mask */
>> +	return &futex_table[hash_key & (futex2_hashsize - 1)];
> 
> If someone inadvertely changes futex2_hashsize to something not 2^n this
> will silently break.  futex2_hashsize should be constant and you need
> a BUILD_BUG_ON().

Given that futex2_hashsize is calcutated at boot time, not sure what we 
could to about this, maybe BUG_ON()?

> 
>> +static int futex_enqueue(struct futexv_head *futexv, unsigned int nr_futexes,
>> +			 int *awakened)
>> +{
>> +	int i, ret;
>> +	u32 uval, *uaddr, val;
>> +	struct futex_bucket *bucket;
>> +
>> +retry:
>> +	set_current_state(TASK_INTERRUPTIBLE);
>> +
>> +	for (i = 0; i < nr_futexes; i++) {
>> +		uaddr = (u32 * __user)futexv->objects[i].uaddr;
>> +		val = (u32)futexv->objects[i].val;
>> +
>> +		bucket = futexv->objects[i].bucket;
>> +
>> +		bucket_inc_waiters(bucket);
>> +		spin_lock(&bucket->lock);
>> +
>> +		ret = futex_get_user(&uval, uaddr);
>> +
>> +		if (unlikely(ret)) {
>> +			spin_unlock(&bucket->lock);
>> +
>> +			bucket_dec_waiters(bucket);
>> +			__set_current_state(TASK_RUNNING);
>> +			*awakened = futex_dequeue_multiple(futexv, i);
>> +
>> +			if (__get_user(uval, uaddr))
>> +				return -EFAULT;
>> +
>> +			if (*awakened >= 0)
>> +				return 1;
> 
> If you are awakened, you don't need to waste time with trying to get the
> next key.
> 

Yes, and this is what this return is supposed to do. What I'm missing?

> 
>> +/**
>> + * futex_wait - Setup the timer (if there's one) and wait on a list of futexes
>> + * @futexv:     List of futexes
>> + * @nr_futexes: Length of futexv
>> + * @timo:	Timeout
>> + * @flags:	Timeout flags
>> + *
>> + * Return:
>> + * * 0 >= - Hint of which futex woke us
>> + * * 0 <  - Error code
>> + */
>> +static int futex_set_timer_and_wait(struct futexv_head *futexv,
>> +				    unsigned int nr_futexes,
>> +				    struct __kernel_timespec __user *timo,
>> +				    unsigned int flags)
>> +{
>> +	struct hrtimer_sleeper timeout;
>> +	int ret;
>> +
>> +	if (timo) {
>> +		ret = futex_setup_time(timo, &timeout, flags);
>> +		if (ret)
>> +			return ret;
>> +	}
>> +
>> +	ret = __futex_wait(futexv, nr_futexes, timo ? &timeout : NULL);
>> +
>> +	if (timo)
>> +		hrtimer_cancel(&timeout.timer);
>> +
>> +	return ret;
>> +}
> 
> I'm having a hard time understanding why this function exists.  part of
> the futex is set up outside of it, part inside.  Not sure if this isn't
> just part of sys_futex_wait.
> 

I wrote this function since setting the timer, waiting and canceling the 
timer is common for both wait and waitv, so this would avoid some code 
duplication. But I probably can just do the timer stuff inside __futex_wait.

> Thanks,
>

André Almeida <andrealmeid@collabora.com> writes:

>>> +		if (unlikely(ret)) {
>>> +			spin_unlock(&bucket->lock);
>>> +
>>> +			bucket_dec_waiters(bucket);
>>> +			__set_current_state(TASK_RUNNING);
>>> +			*awakened = futex_dequeue_multiple(futexv, i);
>>> +
>>> +			if (__get_user(uval, uaddr))
>>> +				return -EFAULT;
>>> +
>>> +			if (*awakened >= 0)
>>> +				return 1;
>> If you are awakened, you don't need to waste time with trying to get
>> the
>> next key.
>> 
>
> Yes, and this is what this return is supposed to do. What I'm missing?

you don't need to do that __get_user if some other key was already awoke.

[...]
if (*awakened >= 0)
	return 1;

if (__get_user(uval, uaddr))
	return -EFAULT;
[...]

Hi Peter,

Às 06:02 de 16/02/21, Peter Zijlstra escreveu:
> On Mon, Feb 15, 2021 at 12:23:52PM -0300, André Almeida wrote:
>> +static int __futex_wait(struct futexv_head *futexv, unsigned int nr_futexes,
>> +			struct hrtimer_sleeper *timeout)
>> +{
>> +	int ret;
>> +
>> +	while (1) {
>> +		int awakened = -1;
>> +
> 
> Might be easier to understand if the set_current_state() is here,
> instead of squirreled away in futex_enqueue().
> 

I placed set_current_state() inside futex_enqueue() because we need to 
set RUNNING and then INTERRUPTIBLE again for the retry path.

>> +		ret = futex_enqueue(futexv, nr_futexes, &awakened);
>> +
>> +		if (ret) {
>> +			if (awakened >= 0)
>> +				return awakened;
>> +			return ret;
>> +		}
>> +
>> +		/* Before sleeping, check if someone was woken */
>> +		if (!futexv->hint && (!timeout || timeout->task))
>> +			freezable_schedule();
>> +
>> +		__set_current_state(TASK_RUNNING);
> 
> This is typically after the loop.
> 

Sorry, which loop?

>> +
>> +		/*
>> +		 * One of those things triggered this wake:
>> +		 *
>> +		 * * We have been removed from the bucket. futex_wake() woke
>> +		 *   us. We just need to dequeue and return 0 to userspace.
>> +		 *
>> +		 * However, if no futex was dequeued by a futex_wake():
>> +		 *
>> +		 * * If the there's a timeout and it has expired,
>> +		 *   return -ETIMEDOUT.
>> +		 *
>> +		 * * If there is a signal pending, something wants to kill our
>> +		 *   thread, return -ERESTARTSYS.
>> +		 *
>> +		 * * If there's no signal pending, it was a spurious wake
>> +		 *   (scheduler gave us a change to do some work, even if we
> 
> chance?

Indeed, fixed.

> 
>> +		 *   don't want to). We need to remove ourselves from the
>> +		 *   bucket and add again, to prevent losing wakeups in the
>> +		 *   meantime.
>> +		 */
> 
> Anyway, doing a dequeue and enqueue for spurious wakes is a bit of an
> anti-pattern that can lead to starvation. I've not actually looked at
> much detail yet as this is my first read-through, but did figure I'd
> mention it.
> 

So we could just leave everything enqueued for spurious wake? I was 
expecting that we would need to do all the work again (including 
rechecking *uaddr == val) to see if we didn't miss a futex_wake() 
between the kernel thread waking (spuriously) and going to sleep again.

>> +
>> +		ret = futex_dequeue_multiple(futexv, nr_futexes);
>> +
>> +		/* Normal wake */
>> +		if (ret >= 0)
>> +			return ret;
>> +
>> +		if (timeout && !timeout->task)
>> +			return -ETIMEDOUT;
>> +
>> +		if (signal_pending(current))
>> +			return -ERESTARTSYS;
>> +
>> +		/* Spurious wake, do everything again */
>> +	}
>> +}

Thanks,
	André