New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

provide guarantees about whether memory goes in the coroutine frame or stack frame #1194

Open
andrewrk opened this Issue Jul 4, 2018 · 2 comments

Comments

Projects
None yet
1 participant
@andrewrk
Member

andrewrk commented Jul 4, 2018

This test fails:

const std = @import("std");
const builtin = @import("builtin");
const assert = std.debug.assert;

var ptr: *u8 = undefined;

test "where does the coroutine memory go" {
    var da = std.heap.DirectAllocator.init();
    defer da.deinit();

    const p = try async<&da.allocator> simpleAsyncFn();
    _ = blowUpStack(5);
    assert(ptr.* == 0xee);
}

async fn simpleAsyncFn() void {
    var x: u8 = 0xee;
    ptr = &x;
    suspend;

    // Uncomment to make the test pass
    // var a = &x;
}

fn blowUpStack(count: usize) usize {
    if (count == 0) return 0;
    return blowUpStack(count - 1) + blowUpStack(count - 1);
}

In this example, even though a pointer to a variable x on the coroutine frame escapes, LLVM does not spill x into the coroutine frame, because it is not referenced after a suspend point. You can see that if you reference the variable after the suspend point then the test passes because x is spilled into the coroutine frame.

It is important that we support local variables that do not spill, because sometimes we need coroutine code to execute even after the frame has been destroyed. In this situation the unspilled variables are accessible while the spilled variables are not.

There is one more relevant piece of information here, which is that LLVM coroutines provide one more utility that zig does not expose directly to the user. This is that you can access the coroutine "promise" value from the handle. (In zig the handle is of type promise). Point here being that we could have async functions define a type which is guaranteed to be inside the coroutine frame, and is accessible via the promise handle.

So here's one proposal:

async<u8, *std.mem.Allocator> fn simpleAsyncFn() void {
    // Now get coroutine handle with this function instead of suspend syntax
    const my_handle = @handle();
    assert(@typeOf(my_handle) == promise:u8->void);

    // now we access the coroutine frame the same way we would from outside the coroutine
    const frame_ref: *u8 = @coroFrame(my_handle);

    frame_ref.* = 0xee;
    ptr = frame_ref;
    suspend;
}

Note that this makes the global capture unnecessary as the assert could be rewritten:

test "where does the coroutine memory go" {
    var da = std.heap.DirectAllocator.init();
    defer da.deinit();

    const p = try async<&da.allocator> simpleAsyncFn();
    _ = blowUpStack(5);
    assert(@coroFrame(p).* == 0xee);
}

This proposal also makes it possible to write generators:

async<?usize> fn range(start: usize, end: usize) void {
    const my_handle = @handle();
    const result_ptr = @coroFrame(my_handle);
    var i: usize = start;
    while (i < end) : (i += 1) {
        result_ptr.* = i;
        suspend;
    }

    result_ptr.* = null;
}

test "generator" {
    const items = try async<std.debug.global_allocator> range(0, 10);
    defer cancel items;
    while (@coroFrame(items).*) |n| : (resume items) {
        std.debug.warn("n={}\n", n);
    }
}

With this proposal, variables would work the same way they do now, and the first test case would still fail in the same way. However there would be an explicit feature to use when you want to guarantee that memory is inside the coroutine frame.

@andrewrk andrewrk added this to the 0.3.0 milestone Jul 4, 2018

andrewrk added a commit that referenced this issue Jul 5, 2018

M:N threading
 * add std.atomic.QueueMpsc.isEmpty
 * make std.debug.global_allocator thread-safe
 * std.event.Loop: now you have to choose between
   - initSingleThreaded
   - initMultiThreaded
 * std.event.Loop multiplexes coroutines onto kernel threads
 * Remove std.event.Loop.stop. Instead the event loop run() function
   returns once there are no pending coroutines.
 * fix crash in ir.cpp for calling methods under some conditions
 * small progress self-hosted compiler, analyzing top level declarations
 * Introduce std.event.Lock for synchronizing coroutines
 * introduce std.event.Locked(T) for data that only 1 coroutine should
   modify at once.
 * make the self hosted compiler use multi threaded event loop
 * make std.heap.DirectAllocator thread-safe

See #174

TODO:
 * call sched_getaffinity instead of hard coding thread pool size 4
 * support for Windows and MacOS
 * #1194
 * #1197

@andrewrk andrewrk referenced this issue Jul 5, 2018

Merged

M:N threading #1198

3 of 3 tasks complete

andrewrk added a commit that referenced this issue Jul 7, 2018

M:N threading
 * add std.atomic.QueueMpsc.isEmpty
 * make std.debug.global_allocator thread-safe
 * std.event.Loop: now you have to choose between
   - initSingleThreaded
   - initMultiThreaded
 * std.event.Loop multiplexes coroutines onto kernel threads
 * Remove std.event.Loop.stop. Instead the event loop run() function
   returns once there are no pending coroutines.
 * fix crash in ir.cpp for calling methods under some conditions
 * small progress self-hosted compiler, analyzing top level declarations
 * Introduce std.event.Lock for synchronizing coroutines
 * introduce std.event.Locked(T) for data that only 1 coroutine should
   modify at once.
 * make the self hosted compiler use multi threaded event loop
 * make std.heap.DirectAllocator thread-safe

See #174

TODO:
 * call sched_getaffinity instead of hard coding thread pool size 4
 * support for Windows and MacOS
 * #1194
 * #1197
@andrewrk

This comment has been minimized.

Member

andrewrk commented Jul 10, 2018

Note that this is especially important, because here's a modified version of the test that fails in ReleaseFast mode, even with the var a = &x; workaround.

const std = @import("std");
const builtin = @import("builtin");
const assert = std.debug.assert;

var ptr: *u8 = undefined;

test "where does the coroutine memory go" {
    var da = std.heap.DirectAllocator.init();
    defer da.deinit();

    const p = try async<&da.allocator> simpleAsyncFn();
    _ = @noInlineCall(blowUpStack, 5);
    assert(ptr.* == 0xee);
}

async fn simpleAsyncFn() void {
    var x: u8 = 0xee;
    ptr = &x;
    suspend;

    var a = &x;
}

fn blowUpStack(count: usize) usize {
    if (count == 0) return 0;
    asm volatile ("nop");
    return @noInlineCall(blowUpStack, count - 1) + @noInlineCall(blowUpStack, count - 1);
}
@andrewrk

This comment has been minimized.

Member

andrewrk commented Jul 10, 2018

Here's a workaround to make it pass in ReleaseFast mode for now:

const std = @import("std");
const builtin = @import("builtin");
const assert = std.debug.assert;

var ptr: *u8 = undefined;

test "where does the coroutine memory go" {
    var da = std.heap.DirectAllocator.init();
    defer da.deinit();

    const p = try async<&da.allocator> simpleAsyncFn();
    _ = @noInlineCall(blowUpStack, 5);
    assert(ptr.* == 0xee);
}

async fn simpleAsyncFn() void {
    // Comment this out to make the test fail
    suspend |p| {
        resume p;
    }

    var x: u8 = 0xee;
    ptr = &x;
    suspend;
}

fn blowUpStack(count: usize) usize {
    if (count == 0) return 0;
    asm volatile ("nop");
    return @noInlineCall(blowUpStack, count - 1) + @noInlineCall(blowUpStack, count - 1);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment