Re: [RFC] futex2: add NUMA awareness

Às 13:42 de 22/07/22, Andrey Semashev escreveu:

On 7/14/22 18:00, André Almeida wrote:

quoted

Hi Andrey,

Thanks for the feedback.

Às 08:01 de 14/07/22, Andrey Semashev escreveu:

quoted

On 7/14/22 06:18, André Almeida wrote:

[...]

quoted

quoted

Feedback? Who else should I CC?

Just a few questions:

Do I understand correctly that notifiers won't be able to wake up
waiters unless they know on which node they are waiting?

If userspace is using NUMA_FLAG, yes. Otherwise all futexes would be
located in the default node, and userspace doesn't need to know which
one is the default.

quoted

Is it possible to wait on a futex on different nodes?

Yes, given that you specify `.hint = id` with the proper node id.

So any given futex_wake(FUTEX_NUMA) operates only within its node, right?

quoted

quoted

Is it possible to wake waiters on a futex on all nodes? When a single
(or N, where N is not "all") waiter is woken, which node is selected? Is
there a rotation of nodes, so that nodes are not skewed in terms of
notified waiters?

Regardless of which node the waiter process is running, what matter is
in which node the futex hash table is. So for instance if we have:

	struct futex32_numa f = {.value = 0, hint = 2};

And now we add some waiters for this futex:

Thread 1, running on node 3:

	futex_wait(&f, 0, FUTEX_NUMA | FUTEX_32, NULL);

Thread 2, running on node 0:

	futex_wait(&f, 0, FUTEX_NUMA | FUTEX_32, NULL);

Thread 3, running on node 2:

	futex_wait(&f, 0, FUTEX_NUMA | FUTEX_32, NULL);

And then, Thread 4, running on node 3:

	futex_wake(&f, 2, FUTEX_NUMA | FUTEX_32);

Now, two waiter would wake up (e.g. T1 and T3, node 3 and 2) and they
are from different nodes. futex_wake() doesn't provide guarantees of
which waiter will be selected, so I can't say which node would be
selected.

In this example, T1, T2 and T3 are all blocking on node 2 (since all of
them presumably specify hint == 2), right? In this sense, it doesn't
matter which node they are running on, what matters is what node they
block on.

yes

What I'm asking is can I wake all threads blocked on all nodes on the
same futex? That is, is the following possible?

  // I'm using hint == -1 to indicate the current node
  // of the calling thread for waiters and all nodes for notifiers
  struct futex32_numa f = {.value = 0, .hint = -1};

  Thread 1, running on node 3, blocks on node 3:

  futex_wait(&f, 0, FUTEX_NUMA | FUTEX_32, NULL);

  Thread 2, running on node 0, blocks on node 0:

  futex_wait(&f, 0, FUTEX_NUMA | FUTEX_32, NULL);

  Thread 3, running on node 2, blocks on node 2:

  futex_wait(&f, 0, FUTEX_NUMA | FUTEX_32, NULL);

  And then, Thread 4, running on whatever node:

  futex_wake(&f, -1, FUTEX_NUMA | FUTEX_32);

this futex_wake will wake all futexes waiting on the node that called
futex_wake(), waking only one futex in this example. They are __not__
the same futex. If they have different nodes, they would have different
information inside the kernel.

if you want to wake them all with the same futex_wake(), they need to be
waiting on the same node.

Here, futex_wake would wake T1, T2 and T3. Or:

  futex_wake(&f, 1, FUTEX_NUMA | FUTEX_32);

this would behave exactly as the futex_wake() above.

Here, futex_wake would wake any one of T1, T2 or T3.

quoted

There's no policy for fairness/starvation for futex_wake(). Do
you think this would be important for the NUMA case?

I'm not sure yet. If there isn't a cross-node behavior like in my
example above then, I suppose, it falls to the userspace to ensure fair
rotation of the wakeups on different nodes. If there is functionality
like this, I imagine, some sort of fairness would be desired.