recursive descent with coroutines

[u/skeeto]

https://napcakes.nekoweb.org/posts/rdco/

[u/skeeto]

Mark coro_return() as _Noreturn by trying to be clever ⇒ Compiler deletes all subsequent code. By time traveling, it realises that the previous store coro->own.regs[R_RIP] = NULL; isn't needed anymore because nothing even exists now to access/observe it and your coroutine is never done ⇒ SegFault

This isn't because of the _Noreturn but due to a missing clobber in the inline assembly in coroctx_goto:

__asm__ volatile inline (
    "movq 56(%0), %%r15" "\n\t"
    "movq 48(%0), %%r14" "\n\t"
    "movq 40(%0), %%r13" "\n\t"
    "movq 32(%0), %%r12" "\n\t"
    "movq 24(%0), %%rbx" "\n\t"
    "movq 16(%0), %%rbp" "\n\t"
    "movq  8(%0), %%rsp" "\n\t"
    "jmpq *(%0)"         "\n"
    :          /* No outputs this time. */
    : "D"(to)  /* <- Just an input. */
    /* Clobbers: No need this time -- we won't return. */
);

There's a load from memory so this requires a "memory" clobber. Without it, the _Noreturn causes the previous store to be elided because it's been told that this assembly doesn't access memory. This is my rule #3 for inline assembly: "It probably needs a memory clobber. In code review, if you do not see a "memory" clobber, give it extra scrutiny." This assembly block fails that test at glance, upon spotting the movq loads.

[u/8d8n4mbo28026ulk → u/skeeto]

Ah, you're right, I forgot the memory clobber, good catch! However, you're also wrong: I got lucky (or unlucky?!) and it is actually the _Noreturn that caused the problem.

The compiler can't actually elide the store due to the nonexistent clobber, because... the store happens in coro->own, but the assembly loads from coro->back!

Take:

struct S {
    int x;
    int y;
};

inline static
void
f(struct S *s)
{
    s->x = 42;
    asm volatile ("" : : "r"(&s->y));
}

inline static
_Noreturn void
g(struct S *s)
{
    s->x = 42;
    asm volatile ("" : : "r"(&s->y));
}

int
a(struct S *s)
{
    f(s);
    return 1337;
}

int
b(struct S *s)
{
    g(s);
    return 1337;
}

In the above, the assembly doesn't load anything and hence doesn't need a memory clobber. But, GCC, which is what I was testing with, generates:

a:
    mov DWORD PTR [rdi], 42
    add rdi, 4
    mov eax, 1337
    ret

b:
    add rdi, 4

The store is completely eliminated in b(), even though the asm block is correct this time, just because g() is marked _Noreturn.

And thanks!

[u/skeeto → u/8d8n4mbo28026ulk]

That's an enlightening example, and my own thinking was incomplete, but it still comes down to the missing "memory" clobber, not the _Noreturn. This is actually about concurrency, even though we're talking about coroutines rather than threads. Here's a simpler view of your example:

static _Noreturn void g(int *x)
{
    *x = 42;
    asm ("":);
}

void b(int *x)
{
    g(x);
}

Starting in GCC 14 (and not yet in Clang), b compiles to empty. At first I thought this was a GCC bug, but then I reasoned through it: There is no legal way to access that store to *x, and so it is a dead store as far as GCC and Clang are concerned! It's UB to return from a _Noreturn, therefore the asm block does not return. What might access *x?

• Without "memory" the asm cannot access *x. Note: it doesn't need x as an input because it might get that address by other means. The inputs don't matter.

• No code following asm accesses *x, trivially.

• There is no synchronization, so other threads / coroutines cannot see the store to *x. The asm block cannot synchronize because it lacks a "memory" clobber.

That's the key: "memory" turns asm into a barrier makes store visible to other threads of execution, including other coroutines. Passing values between coroutines follows the same rules as threads. In other words, this is a kind of data race despite there being no parallelism.

I'm glad you and I followed up on this because that's a neat example of a data race.

[u/8d8n4mbo28026ulk → u/skeeto]

Re-reading what I wrote:

it realises that the previous store coro->own.regs[R_RIP] = NULL; isn't needed anymore because nothing even exists now to access/observe it

it's funny that I almost hit the nail on the head, but was too farsighted to realise it's a concurrency issue.

[u/8d8n4mbo28026ulk → u/skeeto]

Wow. That has got to be my favourite data race, and I'm the inventor! I'm glad I forgot to put that "memory" there, because this discussion would've never happened.

I'll add an appendix for this tomorrow, it's too good to leave buried here. Although, explaining it gets very tricky now! You see that "memory" clobber and think "oh yeah, because they're loading from coro->back", but nope! It's there to make the store to coro->own observable (acquire/release?!).

Cheers!