Solve the thread completion/destruction problem without cost on every context switch

[nyh]

In commit 96ee424 I solved a long-standing bug we had, where a terminating thread, in complete(), would wake the thread join()ing it (_joiner), but in rare cases, this joiner thread would delete the completing thread's stack quickly, before complete() returned, causing a crash.

My solution in this commit included an extra variable we need to check after every context switch - to see if the thread we just left terminated, and we need to wake its joiner (on the new thread's stack). This new if() on every context switch - even when no thread ever terminates - is a waste - not a big one, but still a waste. It would be nice if we had a solution without such an extra if().

In a long email brainstorming with Guy we came up with two alternative solutions. Both are more complex and require more coding, but we should consider one of them in the future:

Solution 1 - migration (my favorite, but Avi and Guy are not enthusiastic about it)

The idea behind this solution is that join() can only run in parallel to complete() if they are running on two different CPUs. If we know that both are on the same CPU, and we disable preemption, then join() will not run (and destroy the terminating thread) until the next schedule() switches the threads. To get them both on the same CPU, all we need to do is to migrate the current thread to the joiner's CPU.

So with this solution, complete() will call unref() directly (no need to set a flag instead), and unref will look like this:

void thread::unref()
{
    if (_ref_counter.fetch_add(-1) == 1) {
        if (_joiner) {
            if (thread::current() == this) {
                // Waking the _joiner thread might cause it to quickly delete
                // this thread, including the stack we're running on, so we
                // need to make sure that _joiner can't run while doing this.
                // We ensure this by migrating to the same CPU as _joiner, and
                // then preempt_disable is enough to ensure _joiner is not
                // running (note we assume here migration of a thread out of
                // this CPU only happens in load_balancer() and this doesn't
                // run when preemption is disabled).
                preempt_disable(); // already disabled in complete(), but doesn't hurt
                while (_joiner->tcpu() != tcpu()) {
                    migrate(_joiner->tcpu());
                }
                _joiner->wake_with([&] { _status.store(status::terminated); });
                // at this point, _joiner cannot have run yet (it's on the
                // same CPU as us and preemption is disabled), so our thread
                // and its stack still exists.
                schedule();
            }

            _joiner->wake_with([&] { _status.store(status::terminated); });
        } else {
            _status.store(status::terminated);
        }
    }
}

The remaining challenge is, of course, to implement migrate(). We can't trivially migrate the running thread from itself, because we'll have the potential migrate() running on the original CPU in parallel with itself on the target CPU. Instead, we need to add to load_balancer() support to send the load_balancer on the current CPU the command to move this thread to a different CPU. The current CPU can then yield() hoping load_balancer gets to run, but perhaps it will be more efficient to set a new status ("migrating") so that the thread being migrated doesn't run again until actually migrated ("waiting" may not good enough because a spurious wake can cause it to stop waiting).

While adding migrate() is a complication, I think it will be a generally somewhat-useful feature. Avi also needed it once, to allow a thread to pin itself to a specific CPU.

Solution 2 - temporary stack (Guy's favorite)

This solution also has complete() calling unref() directly, but when unref wants to set the thread's status and wake the joiner, it can't do it on the thread's stack, as we know, so the idea of this solution is to switch to a temporary stack. Each CPU will have a small stack (even one page may be enough) used just in unref() when it decides to delete the thread, it switches to this stack (via an asm() instruction).

There's a complication here, that it's not enough to call wake() on the new stack. wake() also checks the current thread's state, checks preempt_counter (a thread-local variable) and even needs the current thread just to get the current CPU. All of this cannot work when the thread structure, its stack and its TLS, are all deleted in parallel with this code.
So we need a new version of wake() which can take all this information (current CPU, etc.) as parameters. unref() will need to save these things in registers (and force the compiler to leave them in registers), change the stack, and then call wake with these parameters.

[nyh]

One downside with solution 2 proposed above is that it adds more assembly code, which we'll need to port in the future to different architectures.

To avoid this, we can use actual threads instead of bare stacks - have a per-cpu thread with a small stack, terminator_thread(), similar to how we have a per-cpu load-balancer and idle thread.

So this proposal becomes:

Solution 2a:

complete() will:

1. preempt_disable() - so the terminator_thread doesn't run in the middle of this part
2. set thread's state to "terminating" (as we do now)
3. add to this thread to a PERCPU variable termination_list (can also use a struct cpu field). No locking is needed. [but note: don't use an STL list, an malloc can cause context switch so we need to control where happens]
4. wake this CPU's terminator_thread
5. call schedule()

Each terminator thread will:

1. wait_until there's something in this cpu's termination_list
2. preempt_disable(), to prevent competition with more complete()s
3. for each thread in termination_list, assert() its status is "terminating", and unref() it.
4. preempt_enable()

[loudinthecloud]

Solution 2a is better than unrefing from within schedule() but it adds X more threads, they don't consume much (do they?) but we'll have X idle threads X load balancer and X terminators. If 2a is also an option, maybe we can unify all those threads to a single scheduler_helper thread or something.

Besides that, adding a set_stack() function for each arch is not a big problem in my opinion, we are doing it anyway in switch_to so we can reuse it.

[nyh]

On Mon, Jun 24, 2013 at 4:48 PM, loudinthecloud notifications@github.comwrote:

Solution 2a is better than unrefing from within schedule() but it adds X
more threads, they don't consume much (do they?) but we'll have X idle
threads X load balancer and X terminators.

Waiting threads do not consume any resources beyond their memory use -
mostly the stack.
The scheduler doesn't even consider them, because they're not on the
runqueue of any CPU.

One thing that is "ugly" about all these extra threads is that they
"consume" a thread number, and visible on "osv info threads". To make it
less ugly, perhaps we should consider giving these "internal" threads
negative numbers, and have "osv info threads" not show them.

If 2a is also an option, maybe we can unify all those threads to a single

scheduler_helper thread or something.

A good idea. Since idle_thread, load_balancer, and terminator_thread, are
not meant to run concurrently (they run on the same CPU, and do no
waiting), there is no reason why they need to be different threads, with
different stacks. We can save a bit of memory if we use the same stack for
all three, and just have one helper thread that checks all three conditions.

Besides that, adding a set_stack() function for each arch is not a big
problem in my opinion, we are doing it anyway in switch_to so we can reuse
it.

I'm not sure that all it takes to change the stack in the middle of C code
without a disaster is a set_stack() function (I'm not even sure what it
means to change the stack in a function, maybe it needs to be a macro...).
I'm not saying it can't work, but since we already have the same mechanism
for normal context-switching, maybe it's better to just use exactly the
same mechanism, instead of duplicating it.

—
Reply to this email directly or view it on GitHubhttps://github.com//issues/10#issuecomment-19907628
.

Nadav Har'El
nyh@cloudius-systems.com

[loudinthecloud]

On 06/24/2013 05:27 PM, nyh wrote:

I'm not sure that all it takes to change the stack in the middle of C
code
without a disaster is a set_stack() function (I'm not even sure what it
means to change the stack in a function, maybe it needs to be a
macro...).
I'm not saying it can't work, but since we already have the same
mechanism
for normal context-switching, maybe it's better to just use exactly the
same mechanism, instead of duplicating it.

It's possible that set_stack() will be used both by switch_to() and
complete() and that's what I was suggesting.

Obviously, set_stack() will not work if it's not inlined...

Besides that, I support option 2a as well especially if we plan to unify
idle_thread, load_balance and "the terminator".

[avikivity]

On Mon, Jun 24, 2013 at 5:56 PM, loudinthecloud notifications@github.comwrote:

On 06/24/2013 05:27 PM, nyh wrote:

I'm not sure that all it takes to change the stack in the middle of C
code
without a disaster is a set_stack() function (I'm not even sure what it
means to change the stack in a function, maybe it needs to be a
macro...).
I'm not saying it can't work, but since we already have the same
mechanism
for normal context-switching, maybe it's better to just use exactly the
same mechanism, instead of duplicating it.

It's possible that set_stack() will be used both by switch_to() and
complete() and that's what I was suggesting.

Obviously, set_stack() will not work if it's not inlined...

Besides that, I support option 2a as well especially if we plan to unify
idle_thread, load_balance and "the terminator".

Inlining is not sufficient, as the compiler may/will spill variables on
the stack.