From 574e31f0a046aa6e6fad73fff2cbbb3617fe1bae Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Tue, 10 Jul 2018 20:18:43 -0400 Subject: self-hosted: first passing test * introduce std.atomic.Int * add src-self-hosted/test.zig which is tested by the main test suite - it fully utilizes the multithreaded async/await event loop so the tests should Go Fast * `stage2/bin/zig build-obj test.zig` is able to spit out an error if 2 exported functions collide * ability for `zig test` to accept `--object` and `--assembly` arguments * std.build: TestStep supports addLibPath and addObjectFile --- std/atomic/index.zig | 2 ++ std/atomic/int.zig | 19 +++++++++++++++++++ 2 files changed, 21 insertions(+) create mode 100644 std/atomic/int.zig (limited to 'std/atomic') diff --git a/std/atomic/index.zig b/std/atomic/index.zig index c0ea5be183..cf344a8231 100644 --- a/std/atomic/index.zig +++ b/std/atomic/index.zig @@ -1,9 +1,11 @@ pub const Stack = @import("stack.zig").Stack; pub const QueueMpsc = @import("queue_mpsc.zig").QueueMpsc; pub const QueueMpmc = @import("queue_mpmc.zig").QueueMpmc; +pub const Int = @import("int.zig").Int; test "std.atomic" { _ = @import("stack.zig"); _ = @import("queue_mpsc.zig"); _ = @import("queue_mpmc.zig"); + _ = @import("int.zig"); } diff --git a/std/atomic/int.zig b/std/atomic/int.zig new file mode 100644 index 0000000000..7042bca78d --- /dev/null +++ b/std/atomic/int.zig @@ -0,0 +1,19 @@ +const builtin = @import("builtin"); +const AtomicOrder = builtin.AtomicOrder; + +/// Thread-safe, lock-free integer +pub fn Int(comptime T: type) type { + return struct { + value: T, + + pub const Self = this; + + pub fn init(init_val: T) Self { + return Self{ .value = init_val }; + } + + pub fn next(self: *Self) T { + return @atomicRmw(T, &self.value, builtin.AtomicRmwOp.Add, 1, AtomicOrder.SeqCst); + } + }; +} -- cgit v1.2.3 From 9751a0ae045110fb615c866b94ad47680b9c48c7 Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Wed, 11 Jul 2018 19:38:01 -0400 Subject: std.atomic: use spinlocks the lock-free data structures all had ABA problems and std.atomic.Stack had a possibility to load an unmapped memory address. --- CMakeLists.txt | 3 +- build.zig | 8 +- std/atomic/index.zig | 6 +- std/atomic/queue.zig | 226 ++++++++++++++++++++++++++++++++++++++++++++++ std/atomic/queue_mpmc.zig | 214 ------------------------------------------- std/atomic/queue_mpsc.zig | 185 ------------------------------------- std/atomic/stack.zig | 32 ++++--- std/event/channel.zig | 12 +-- std/event/future.zig | 21 +++-- std/event/lock.zig | 2 +- std/event/loop.zig | 6 +- test/tests.zig | 26 +++--- 12 files changed, 286 insertions(+), 455 deletions(-) create mode 100644 std/atomic/queue.zig delete mode 100644 std/atomic/queue_mpmc.zig delete mode 100644 std/atomic/queue_mpsc.zig (limited to 'std/atomic') diff --git a/CMakeLists.txt b/CMakeLists.txt index 51d348f042..e606855555 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -432,8 +432,7 @@ set(ZIG_STD_FILES "array_list.zig" "atomic/index.zig" "atomic/int.zig" - "atomic/queue_mpmc.zig" - "atomic/queue_mpsc.zig" + "atomic/queue.zig" "atomic/stack.zig" "base64.zig" "buf_map.zig" diff --git a/build.zig b/build.zig index fd37138f33..c9e70887e3 100644 --- a/build.zig +++ b/build.zig @@ -91,11 +91,11 @@ pub fn build(b: *Builder) !void { test_step.dependOn(tests.addPkgTests(b, test_filter, "std/special/compiler_rt/index.zig", "compiler-rt", "Run the compiler_rt tests", modes)); - test_step.dependOn(tests.addCompareOutputTests(b, test_filter)); + test_step.dependOn(tests.addCompareOutputTests(b, test_filter, modes)); test_step.dependOn(tests.addBuildExampleTests(b, test_filter)); - test_step.dependOn(tests.addCompileErrorTests(b, test_filter)); - test_step.dependOn(tests.addAssembleAndLinkTests(b, test_filter)); - test_step.dependOn(tests.addRuntimeSafetyTests(b, test_filter)); + test_step.dependOn(tests.addCompileErrorTests(b, test_filter, modes)); + test_step.dependOn(tests.addAssembleAndLinkTests(b, test_filter, modes)); + test_step.dependOn(tests.addRuntimeSafetyTests(b, test_filter, modes)); test_step.dependOn(tests.addTranslateCTests(b, test_filter)); test_step.dependOn(tests.addGenHTests(b, test_filter)); test_step.dependOn(docs_step); diff --git a/std/atomic/index.zig b/std/atomic/index.zig index cf344a8231..a94cff1973 100644 --- a/std/atomic/index.zig +++ b/std/atomic/index.zig @@ -1,11 +1,9 @@ pub const Stack = @import("stack.zig").Stack; -pub const QueueMpsc = @import("queue_mpsc.zig").QueueMpsc; -pub const QueueMpmc = @import("queue_mpmc.zig").QueueMpmc; +pub const Queue = @import("queue.zig").Queue; pub const Int = @import("int.zig").Int; test "std.atomic" { _ = @import("stack.zig"); - _ = @import("queue_mpsc.zig"); - _ = @import("queue_mpmc.zig"); + _ = @import("queue.zig"); _ = @import("int.zig"); } diff --git a/std/atomic/queue.zig b/std/atomic/queue.zig new file mode 100644 index 0000000000..1fd07714e8 --- /dev/null +++ b/std/atomic/queue.zig @@ -0,0 +1,226 @@ +const builtin = @import("builtin"); +const AtomicOrder = builtin.AtomicOrder; +const AtomicRmwOp = builtin.AtomicRmwOp; + +/// Many producer, many consumer, non-allocating, thread-safe. +/// Uses a spinlock to protect get() and put(). +pub fn Queue(comptime T: type) type { + return struct { + head: ?*Node, + tail: ?*Node, + lock: u8, + + pub const Self = this; + + pub const Node = struct { + next: ?*Node, + data: T, + }; + + pub fn init() Self { + return Self{ + .head = null, + .tail = null, + .lock = 0, + }; + } + + pub fn put(self: *Self, node: *Node) void { + node.next = null; + + while (@atomicRmw(u8, &self.lock, builtin.AtomicRmwOp.Xchg, 1, AtomicOrder.SeqCst) != 0) {} + defer assert(@atomicRmw(u8, &self.lock, builtin.AtomicRmwOp.Xchg, 0, AtomicOrder.SeqCst) == 1); + + const opt_tail = self.tail; + self.tail = node; + if (opt_tail) |tail| { + tail.next = node; + } else { + assert(self.head == null); + self.head = node; + } + } + + pub fn get(self: *Self) ?*Node { + while (@atomicRmw(u8, &self.lock, builtin.AtomicRmwOp.Xchg, 1, AtomicOrder.SeqCst) != 0) {} + defer assert(@atomicRmw(u8, &self.lock, builtin.AtomicRmwOp.Xchg, 0, AtomicOrder.SeqCst) == 1); + + const head = self.head orelse return null; + self.head = head.next; + if (head.next == null) self.tail = null; + return head; + } + + pub fn isEmpty(self: *Self) bool { + return @atomicLoad(?*Node, &self.head, builtin.AtomicOrder.SeqCst) != null; + } + + pub fn dump(self: *Self) void { + while (@atomicRmw(u8, &self.lock, builtin.AtomicRmwOp.Xchg, 1, AtomicOrder.SeqCst) != 0) {} + defer assert(@atomicRmw(u8, &self.lock, builtin.AtomicRmwOp.Xchg, 0, AtomicOrder.SeqCst) == 1); + + std.debug.warn("head: "); + dumpRecursive(self.head, 0); + std.debug.warn("tail: "); + dumpRecursive(self.tail, 0); + } + + fn dumpRecursive(optional_node: ?*Node, indent: usize) void { + var stderr_file = std.io.getStdErr() catch return; + const stderr = &std.io.FileOutStream.init(&stderr_file).stream; + stderr.writeByteNTimes(' ', indent) catch return; + if (optional_node) |node| { + std.debug.warn("0x{x}={}\n", @ptrToInt(node), node.data); + dumpRecursive(node.next, indent + 1); + } else { + std.debug.warn("(null)\n"); + } + } + }; +} + +const std = @import("../index.zig"); +const assert = std.debug.assert; + +const Context = struct { + allocator: *std.mem.Allocator, + queue: *Queue(i32), + put_sum: isize, + get_sum: isize, + get_count: usize, + puts_done: u8, // TODO make this a bool +}; + +// TODO add lazy evaluated build options and then put puts_per_thread behind +// some option such as: "AggressiveMultithreadedFuzzTest". In the AppVeyor +// CI we would use a less aggressive setting since at 1 core, while we still +// want this test to pass, we need a smaller value since there is so much thrashing +// we would also use a less aggressive setting when running in valgrind +const puts_per_thread = 500; +const put_thread_count = 3; + +test "std.atomic.Queue" { + var direct_allocator = std.heap.DirectAllocator.init(); + defer direct_allocator.deinit(); + + var plenty_of_memory = try direct_allocator.allocator.alloc(u8, 300 * 1024); + defer direct_allocator.allocator.free(plenty_of_memory); + + var fixed_buffer_allocator = std.heap.ThreadSafeFixedBufferAllocator.init(plenty_of_memory); + var a = &fixed_buffer_allocator.allocator; + + var queue = Queue(i32).init(); + var context = Context{ + .allocator = a, + .queue = &queue, + .put_sum = 0, + .get_sum = 0, + .puts_done = 0, + .get_count = 0, + }; + + var putters: [put_thread_count]*std.os.Thread = undefined; + for (putters) |*t| { + t.* = try std.os.spawnThread(&context, startPuts); + } + var getters: [put_thread_count]*std.os.Thread = undefined; + for (getters) |*t| { + t.* = try std.os.spawnThread(&context, startGets); + } + + for (putters) |t| + t.wait(); + _ = @atomicRmw(u8, &context.puts_done, builtin.AtomicRmwOp.Xchg, 1, AtomicOrder.SeqCst); + for (getters) |t| + t.wait(); + + if (context.put_sum != context.get_sum) { + std.debug.panic("failure\nput_sum:{} != get_sum:{}", context.put_sum, context.get_sum); + } + + if (context.get_count != puts_per_thread * put_thread_count) { + std.debug.panic( + "failure\nget_count:{} != puts_per_thread:{} * put_thread_count:{}", + context.get_count, + u32(puts_per_thread), + u32(put_thread_count), + ); + } +} + +fn startPuts(ctx: *Context) u8 { + var put_count: usize = puts_per_thread; + var r = std.rand.DefaultPrng.init(0xdeadbeef); + while (put_count != 0) : (put_count -= 1) { + std.os.time.sleep(0, 1); // let the os scheduler be our fuzz + const x = @bitCast(i32, r.random.scalar(u32)); + const node = ctx.allocator.create(Queue(i32).Node{ + .next = undefined, + .data = x, + }) catch unreachable; + ctx.queue.put(node); + _ = @atomicRmw(isize, &ctx.put_sum, builtin.AtomicRmwOp.Add, x, AtomicOrder.SeqCst); + } + return 0; +} + +fn startGets(ctx: *Context) u8 { + while (true) { + const last = @atomicLoad(u8, &ctx.puts_done, builtin.AtomicOrder.SeqCst) == 1; + + while (ctx.queue.get()) |node| { + std.os.time.sleep(0, 1); // let the os scheduler be our fuzz + _ = @atomicRmw(isize, &ctx.get_sum, builtin.AtomicRmwOp.Add, node.data, builtin.AtomicOrder.SeqCst); + _ = @atomicRmw(usize, &ctx.get_count, builtin.AtomicRmwOp.Add, 1, builtin.AtomicOrder.SeqCst); + } + + if (last) return 0; + } +} + +test "std.atomic.Queue single-threaded" { + var queue = Queue(i32).init(); + + var node_0 = Queue(i32).Node{ + .data = 0, + .next = undefined, + }; + queue.put(&node_0); + + var node_1 = Queue(i32).Node{ + .data = 1, + .next = undefined, + }; + queue.put(&node_1); + + assert(queue.get().?.data == 0); + + var node_2 = Queue(i32).Node{ + .data = 2, + .next = undefined, + }; + queue.put(&node_2); + + var node_3 = Queue(i32).Node{ + .data = 3, + .next = undefined, + }; + queue.put(&node_3); + + assert(queue.get().?.data == 1); + + assert(queue.get().?.data == 2); + + var node_4 = Queue(i32).Node{ + .data = 4, + .next = undefined, + }; + queue.put(&node_4); + + assert(queue.get().?.data == 3); + node_3.next = null; + + assert(queue.get().?.data == 4); + + assert(queue.get() == null); +} diff --git a/std/atomic/queue_mpmc.zig b/std/atomic/queue_mpmc.zig deleted file mode 100644 index 7ffc9f9ccb..0000000000 --- a/std/atomic/queue_mpmc.zig +++ /dev/null @@ -1,214 +0,0 @@ -const builtin = @import("builtin"); -const AtomicOrder = builtin.AtomicOrder; -const AtomicRmwOp = builtin.AtomicRmwOp; - -/// Many producer, many consumer, non-allocating, thread-safe, lock-free -/// This implementation has a crippling limitation - it hangs onto node -/// memory for 1 extra get() and 1 extra put() operation - when get() returns a node, that -/// node must not be freed until both the next get() and the next put() completes. -pub fn QueueMpmc(comptime T: type) type { - return struct { - head: *Node, - tail: *Node, - root: Node, - - pub const Self = this; - - pub const Node = struct { - next: ?*Node, - data: T, - }; - - /// TODO: well defined copy elision: https://github.com/ziglang/zig/issues/287 - pub fn init(self: *Self) void { - self.root.next = null; - self.head = &self.root; - self.tail = &self.root; - } - - pub fn put(self: *Self, node: *Node) void { - node.next = null; - - const tail = @atomicRmw(*Node, &self.tail, AtomicRmwOp.Xchg, node, AtomicOrder.SeqCst); - _ = @atomicRmw(?*Node, &tail.next, AtomicRmwOp.Xchg, node, AtomicOrder.SeqCst); - } - - /// node must not be freed until both the next get() and the next put() complete - pub fn get(self: *Self) ?*Node { - var head = @atomicLoad(*Node, &self.head, AtomicOrder.SeqCst); - while (true) { - const node = head.next orelse return null; - head = @cmpxchgWeak(*Node, &self.head, head, node, AtomicOrder.SeqCst, AtomicOrder.SeqCst) orelse return node; - } - } - - ///// This is a debug function that is not thread-safe. - pub fn dump(self: *Self) void { - std.debug.warn("head: "); - dumpRecursive(self.head, 0); - std.debug.warn("tail: "); - dumpRecursive(self.tail, 0); - } - - fn dumpRecursive(optional_node: ?*Node, indent: usize) void { - var stderr_file = std.io.getStdErr() catch return; - const stderr = &std.io.FileOutStream.init(&stderr_file).stream; - stderr.writeByteNTimes(' ', indent) catch return; - if (optional_node) |node| { - std.debug.warn("0x{x}={}\n", @ptrToInt(node), node.data); - dumpRecursive(node.next, indent + 1); - } else { - std.debug.warn("(null)\n"); - } - } - }; -} - -const std = @import("std"); -const assert = std.debug.assert; - -const Context = struct { - allocator: *std.mem.Allocator, - queue: *QueueMpmc(i32), - put_sum: isize, - get_sum: isize, - get_count: usize, - puts_done: u8, // TODO make this a bool -}; - -// TODO add lazy evaluated build options and then put puts_per_thread behind -// some option such as: "AggressiveMultithreadedFuzzTest". In the AppVeyor -// CI we would use a less aggressive setting since at 1 core, while we still -// want this test to pass, we need a smaller value since there is so much thrashing -// we would also use a less aggressive setting when running in valgrind -const puts_per_thread = 500; -const put_thread_count = 3; - -test "std.atomic.queue_mpmc" { - var direct_allocator = std.heap.DirectAllocator.init(); - defer direct_allocator.deinit(); - - var plenty_of_memory = try direct_allocator.allocator.alloc(u8, 300 * 1024); - defer direct_allocator.allocator.free(plenty_of_memory); - - var fixed_buffer_allocator = std.heap.ThreadSafeFixedBufferAllocator.init(plenty_of_memory); - var a = &fixed_buffer_allocator.allocator; - - var queue: QueueMpmc(i32) = undefined; - queue.init(); - var context = Context{ - .allocator = a, - .queue = &queue, - .put_sum = 0, - .get_sum = 0, - .puts_done = 0, - .get_count = 0, - }; - - var putters: [put_thread_count]*std.os.Thread = undefined; - for (putters) |*t| { - t.* = try std.os.spawnThread(&context, startPuts); - } - var getters: [put_thread_count]*std.os.Thread = undefined; - for (getters) |*t| { - t.* = try std.os.spawnThread(&context, startGets); - } - - for (putters) |t| - t.wait(); - _ = @atomicRmw(u8, &context.puts_done, builtin.AtomicRmwOp.Xchg, 1, AtomicOrder.SeqCst); - for (getters) |t| - t.wait(); - - if (context.put_sum != context.get_sum) { - std.debug.panic("failure\nput_sum:{} != get_sum:{}", context.put_sum, context.get_sum); - } - - if (context.get_count != puts_per_thread * put_thread_count) { - std.debug.panic( - "failure\nget_count:{} != puts_per_thread:{} * put_thread_count:{}", - context.get_count, - u32(puts_per_thread), - u32(put_thread_count), - ); - } -} - -fn startPuts(ctx: *Context) u8 { - var put_count: usize = puts_per_thread; - var r = std.rand.DefaultPrng.init(0xdeadbeef); - while (put_count != 0) : (put_count -= 1) { - std.os.time.sleep(0, 1); // let the os scheduler be our fuzz - const x = @bitCast(i32, r.random.scalar(u32)); - const node = ctx.allocator.create(QueueMpmc(i32).Node{ - .next = undefined, - .data = x, - }) catch unreachable; - ctx.queue.put(node); - _ = @atomicRmw(isize, &ctx.put_sum, builtin.AtomicRmwOp.Add, x, AtomicOrder.SeqCst); - } - return 0; -} - -fn startGets(ctx: *Context) u8 { - while (true) { - const last = @atomicLoad(u8, &ctx.puts_done, builtin.AtomicOrder.SeqCst) == 1; - - while (ctx.queue.get()) |node| { - std.os.time.sleep(0, 1); // let the os scheduler be our fuzz - _ = @atomicRmw(isize, &ctx.get_sum, builtin.AtomicRmwOp.Add, node.data, builtin.AtomicOrder.SeqCst); - _ = @atomicRmw(usize, &ctx.get_count, builtin.AtomicRmwOp.Add, 1, builtin.AtomicOrder.SeqCst); - } - - if (last) return 0; - } -} - -test "std.atomic.queue_mpmc single-threaded" { - var queue: QueueMpmc(i32) = undefined; - queue.init(); - - var node_0 = QueueMpmc(i32).Node{ - .data = 0, - .next = undefined, - }; - queue.put(&node_0); - - var node_1 = QueueMpmc(i32).Node{ - .data = 1, - .next = undefined, - }; - queue.put(&node_1); - - assert(queue.get().?.data == 0); - - var node_2 = QueueMpmc(i32).Node{ - .data = 2, - .next = undefined, - }; - queue.put(&node_2); - - var node_3 = QueueMpmc(i32).Node{ - .data = 3, - .next = undefined, - }; - queue.put(&node_3); - - assert(queue.get().?.data == 1); - - assert(queue.get().?.data == 2); - - var node_4 = QueueMpmc(i32).Node{ - .data = 4, - .next = undefined, - }; - queue.put(&node_4); - - assert(queue.get().?.data == 3); - // if we were to set node_3.next to null here, it would cause this test - // to fail. this demonstrates the limitation of hanging on to extra memory. - - assert(queue.get().?.data == 4); - - assert(queue.get() == null); -} diff --git a/std/atomic/queue_mpsc.zig b/std/atomic/queue_mpsc.zig deleted file mode 100644 index 978e189453..0000000000 --- a/std/atomic/queue_mpsc.zig +++ /dev/null @@ -1,185 +0,0 @@ -const std = @import("../index.zig"); -const assert = std.debug.assert; -const builtin = @import("builtin"); -const AtomicOrder = builtin.AtomicOrder; -const AtomicRmwOp = builtin.AtomicRmwOp; - -/// Many producer, single consumer, non-allocating, thread-safe, lock-free -pub fn QueueMpsc(comptime T: type) type { - return struct { - inboxes: [2]std.atomic.Stack(T), - outbox: std.atomic.Stack(T), - inbox_index: usize, - - pub const Self = this; - - pub const Node = std.atomic.Stack(T).Node; - - /// Not thread-safe. The call to init() must complete before any other functions are called. - /// No deinitialization required. - pub fn init() Self { - return Self{ - .inboxes = []std.atomic.Stack(T){ - std.atomic.Stack(T).init(), - std.atomic.Stack(T).init(), - }, - .outbox = std.atomic.Stack(T).init(), - .inbox_index = 0, - }; - } - - /// Fully thread-safe. put() may be called from any thread at any time. - pub fn put(self: *Self, node: *Node) void { - const inbox_index = @atomicLoad(usize, &self.inbox_index, AtomicOrder.SeqCst); - const inbox = &self.inboxes[inbox_index]; - inbox.push(node); - } - - /// Must be called by only 1 consumer at a time. Every call to get() and isEmpty() must complete before - /// the next call to get(). - pub fn get(self: *Self) ?*Node { - if (self.outbox.pop()) |node| { - return node; - } - const prev_inbox_index = @atomicRmw(usize, &self.inbox_index, AtomicRmwOp.Xor, 0x1, AtomicOrder.SeqCst); - const prev_inbox = &self.inboxes[prev_inbox_index]; - while (prev_inbox.pop()) |node| { - self.outbox.push(node); - } - return self.outbox.pop(); - } - - /// Must be called by only 1 consumer at a time. Every call to get() and isEmpty() must complete before - /// the next call to isEmpty(). - pub fn isEmpty(self: *Self) bool { - if (!self.outbox.isEmpty()) return false; - const prev_inbox_index = @atomicRmw(usize, &self.inbox_index, AtomicRmwOp.Xor, 0x1, AtomicOrder.SeqCst); - const prev_inbox = &self.inboxes[prev_inbox_index]; - while (prev_inbox.pop()) |node| { - self.outbox.push(node); - } - return self.outbox.isEmpty(); - } - - /// For debugging only. No API guarantees about what this does. - pub fn dump(self: *Self) void { - { - var it = self.outbox.root; - while (it) |node| { - std.debug.warn("0x{x} -> ", @ptrToInt(node)); - it = node.next; - } - } - const inbox_index = self.inbox_index; - const inboxes = []*std.atomic.Stack(T){ - &self.inboxes[self.inbox_index], - &self.inboxes[1 - self.inbox_index], - }; - for (inboxes) |inbox| { - var it = inbox.root; - while (it) |node| { - std.debug.warn("0x{x} -> ", @ptrToInt(node)); - it = node.next; - } - } - - std.debug.warn("null\n"); - } - }; -} - -const Context = struct { - allocator: *std.mem.Allocator, - queue: *QueueMpsc(i32), - put_sum: isize, - get_sum: isize, - get_count: usize, - puts_done: u8, // TODO make this a bool -}; - -// TODO add lazy evaluated build options and then put puts_per_thread behind -// some option such as: "AggressiveMultithreadedFuzzTest". In the AppVeyor -// CI we would use a less aggressive setting since at 1 core, while we still -// want this test to pass, we need a smaller value since there is so much thrashing -// we would also use a less aggressive setting when running in valgrind -const puts_per_thread = 500; -const put_thread_count = 3; - -test "std.atomic.queue_mpsc" { - var direct_allocator = std.heap.DirectAllocator.init(); - defer direct_allocator.deinit(); - - var plenty_of_memory = try direct_allocator.allocator.alloc(u8, 300 * 1024); - defer direct_allocator.allocator.free(plenty_of_memory); - - var fixed_buffer_allocator = std.heap.ThreadSafeFixedBufferAllocator.init(plenty_of_memory); - var a = &fixed_buffer_allocator.allocator; - - var queue = QueueMpsc(i32).init(); - var context = Context{ - .allocator = a, - .queue = &queue, - .put_sum = 0, - .get_sum = 0, - .puts_done = 0, - .get_count = 0, - }; - - var putters: [put_thread_count]*std.os.Thread = undefined; - for (putters) |*t| { - t.* = try std.os.spawnThread(&context, startPuts); - } - var getters: [1]*std.os.Thread = undefined; - for (getters) |*t| { - t.* = try std.os.spawnThread(&context, startGets); - } - - for (putters) |t| - t.wait(); - _ = @atomicRmw(u8, &context.puts_done, builtin.AtomicRmwOp.Xchg, 1, AtomicOrder.SeqCst); - for (getters) |t| - t.wait(); - - if (context.put_sum != context.get_sum) { - std.debug.panic("failure\nput_sum:{} != get_sum:{}", context.put_sum, context.get_sum); - } - - if (context.get_count != puts_per_thread * put_thread_count) { - std.debug.panic( - "failure\nget_count:{} != puts_per_thread:{} * put_thread_count:{}", - context.get_count, - u32(puts_per_thread), - u32(put_thread_count), - ); - } -} - -fn startPuts(ctx: *Context) u8 { - var put_count: usize = puts_per_thread; - var r = std.rand.DefaultPrng.init(0xdeadbeef); - while (put_count != 0) : (put_count -= 1) { - std.os.time.sleep(0, 1); // let the os scheduler be our fuzz - const x = @bitCast(i32, r.random.scalar(u32)); - const node = ctx.allocator.create(QueueMpsc(i32).Node{ - .next = undefined, - .data = x, - }) catch unreachable; - ctx.queue.put(node); - _ = @atomicRmw(isize, &ctx.put_sum, builtin.AtomicRmwOp.Add, x, AtomicOrder.SeqCst); - } - return 0; -} - -fn startGets(ctx: *Context) u8 { - while (true) { - const last = @atomicLoad(u8, &ctx.puts_done, builtin.AtomicOrder.SeqCst) == 1; - - while (ctx.queue.get()) |node| { - std.os.time.sleep(0, 1); // let the os scheduler be our fuzz - _ = @atomicRmw(isize, &ctx.get_sum, builtin.AtomicRmwOp.Add, node.data, builtin.AtomicOrder.SeqCst); - _ = @atomicRmw(usize, &ctx.get_count, builtin.AtomicRmwOp.Add, 1, builtin.AtomicOrder.SeqCst); - } - - if (last) return 0; - } -} diff --git a/std/atomic/stack.zig b/std/atomic/stack.zig index d74bee8e8b..16d5c9503b 100644 --- a/std/atomic/stack.zig +++ b/std/atomic/stack.zig @@ -1,10 +1,13 @@ +const assert = std.debug.assert; const builtin = @import("builtin"); const AtomicOrder = builtin.AtomicOrder; -/// Many reader, many writer, non-allocating, thread-safe, lock-free +/// Many reader, many writer, non-allocating, thread-safe +/// Uses a spinlock to protect push() and pop() pub fn Stack(comptime T: type) type { return struct { root: ?*Node, + lock: u8, pub const Self = this; @@ -14,7 +17,10 @@ pub fn Stack(comptime T: type) type { }; pub fn init() Self { - return Self{ .root = null }; + return Self{ + .root = null, + .lock = 0, + }; } /// push operation, but only if you are the first item in the stack. if you did not succeed in @@ -25,18 +31,20 @@ pub fn Stack(comptime T: type) type { } pub fn push(self: *Self, node: *Node) void { - var root = @atomicLoad(?*Node, &self.root, AtomicOrder.SeqCst); - while (true) { - node.next = root; - root = @cmpxchgWeak(?*Node, &self.root, root, node, AtomicOrder.SeqCst, AtomicOrder.SeqCst) orelse break; - } + while (@atomicRmw(u8, &self.lock, builtin.AtomicRmwOp.Xchg, 1, AtomicOrder.SeqCst) != 0) {} + defer assert(@atomicRmw(u8, &self.lock, builtin.AtomicRmwOp.Xchg, 0, AtomicOrder.SeqCst) == 1); + + node.next = self.root; + self.root = node; } pub fn pop(self: *Self) ?*Node { - var root = @atomicLoad(?*Node, &self.root, AtomicOrder.SeqCst); - while (true) { - root = @cmpxchgWeak(?*Node, &self.root, root, (root orelse return null).next, AtomicOrder.SeqCst, AtomicOrder.SeqCst) orelse return root; - } + while (@atomicRmw(u8, &self.lock, builtin.AtomicRmwOp.Xchg, 1, AtomicOrder.SeqCst) != 0) {} + defer assert(@atomicRmw(u8, &self.lock, builtin.AtomicRmwOp.Xchg, 0, AtomicOrder.SeqCst) == 1); + + const root = self.root orelse return null; + self.root = root.next; + return root; } pub fn isEmpty(self: *Self) bool { @@ -45,7 +53,7 @@ pub fn Stack(comptime T: type) type { }; } -const std = @import("std"); +const std = @import("../index.zig"); const Context = struct { allocator: *std.mem.Allocator, stack: *Stack(i32), diff --git a/std/event/channel.zig b/std/event/channel.zig index 4b3a7177a2..d4d713bdee 100644 --- a/std/event/channel.zig +++ b/std/event/channel.zig @@ -12,8 +12,8 @@ pub fn Channel(comptime T: type) type { return struct { loop: *Loop, - getters: std.atomic.QueueMpsc(GetNode), - putters: std.atomic.QueueMpsc(PutNode), + getters: std.atomic.Queue(GetNode), + putters: std.atomic.Queue(PutNode), get_count: usize, put_count: usize, dispatch_lock: u8, // TODO make this a bool @@ -46,8 +46,8 @@ pub fn Channel(comptime T: type) type { .buffer_index = 0, .dispatch_lock = 0, .need_dispatch = 0, - .getters = std.atomic.QueueMpsc(GetNode).init(), - .putters = std.atomic.QueueMpsc(PutNode).init(), + .getters = std.atomic.Queue(GetNode).init(), + .putters = std.atomic.Queue(PutNode).init(), .get_count = 0, .put_count = 0, }); @@ -81,7 +81,7 @@ pub fn Channel(comptime T: type) type { .next = undefined, .data = handle, }; - var queue_node = std.atomic.QueueMpsc(PutNode).Node{ + var queue_node = std.atomic.Queue(PutNode).Node{ .data = PutNode{ .tick_node = &my_tick_node, .data = data, @@ -111,7 +111,7 @@ pub fn Channel(comptime T: type) type { .next = undefined, .data = handle, }; - var queue_node = std.atomic.QueueMpsc(GetNode).Node{ + var queue_node = std.atomic.Queue(GetNode).Node{ .data = GetNode{ .ptr = &result, .tick_node = &my_tick_node, diff --git a/std/event/future.zig b/std/event/future.zig index 8001f675a2..6c03641828 100644 --- a/std/event/future.zig +++ b/std/event/future.zig @@ -17,7 +17,7 @@ pub fn Future(comptime T: type) type { available: u8, // TODO make this a bool const Self = this; - const Queue = std.atomic.QueueMpsc(promise); + const Queue = std.atomic.Queue(promise); pub fn init(loop: *Loop) Self { return Self{ @@ -30,19 +30,19 @@ pub fn Future(comptime T: type) type { /// Obtain the value. If it's not available, wait until it becomes /// available. /// Thread-safe. - pub async fn get(self: *Self) T { + pub async fn get(self: *Self) *T { if (@atomicLoad(u8, &self.available, AtomicOrder.SeqCst) == 1) { - return self.data; + return &self.data; } const held = await (async self.lock.acquire() catch unreachable); - defer held.release(); + held.release(); - return self.data; + return &self.data; } /// Make the data become available. May be called only once. - pub fn put(self: *Self, value: T) void { - self.data = value; + /// Before calling this, modify the `data` property. + pub fn resolve(self: *Self) void { const prev = @atomicRmw(u8, &self.available, AtomicRmwOp.Xchg, 1, AtomicOrder.SeqCst); assert(prev == 0); // put() called twice Lock.Held.release(Lock.Held{ .lock = &self.lock }); @@ -57,7 +57,7 @@ test "std.event.Future" { const allocator = &da.allocator; var loop: Loop = undefined; - try loop.initMultiThreaded(allocator); + try loop.initSingleThreaded(allocator); defer loop.deinit(); const handle = try async testFuture(&loop); @@ -79,9 +79,10 @@ async fn testFuture(loop: *Loop) void { } async fn waitOnFuture(future: *Future(i32)) i32 { - return await (async future.get() catch @panic("memory")); + return (await (async future.get() catch @panic("memory"))).*; } async fn resolveFuture(future: *Future(i32)) void { - future.put(6); + future.data = 6; + future.resolve(); } diff --git a/std/event/lock.zig b/std/event/lock.zig index cba3594b50..2013b5595f 100644 --- a/std/event/lock.zig +++ b/std/event/lock.zig @@ -15,7 +15,7 @@ pub const Lock = struct { queue: Queue, queue_empty_bit: u8, // TODO make this a bool - const Queue = std.atomic.QueueMpsc(promise); + const Queue = std.atomic.Queue(promise); pub const Held = struct { lock: *Lock, diff --git a/std/event/loop.zig b/std/event/loop.zig index 646f15875f..07575cf2e8 100644 --- a/std/event/loop.zig +++ b/std/event/loop.zig @@ -9,7 +9,7 @@ const AtomicOrder = builtin.AtomicOrder; pub const Loop = struct { allocator: *mem.Allocator, - next_tick_queue: std.atomic.QueueMpsc(promise), + next_tick_queue: std.atomic.Queue(promise), os_data: OsData, final_resume_node: ResumeNode, dispatch_lock: u8, // TODO make this a bool @@ -21,7 +21,7 @@ pub const Loop = struct { available_eventfd_resume_nodes: std.atomic.Stack(ResumeNode.EventFd), eventfd_resume_nodes: []std.atomic.Stack(ResumeNode.EventFd).Node, - pub const NextTickNode = std.atomic.QueueMpsc(promise).Node; + pub const NextTickNode = std.atomic.Queue(promise).Node; pub const ResumeNode = struct { id: Id, @@ -77,7 +77,7 @@ pub const Loop = struct { .pending_event_count = 0, .allocator = allocator, .os_data = undefined, - .next_tick_queue = std.atomic.QueueMpsc(promise).init(), + .next_tick_queue = std.atomic.Queue(promise).init(), .dispatch_lock = 1, // start locked so threads go directly into epoll wait .extra_threads = undefined, .available_eventfd_resume_nodes = std.atomic.Stack(ResumeNode.EventFd).init(), diff --git a/test/tests.zig b/test/tests.zig index b1453776a8..3a72f58753 100644 --- a/test/tests.zig +++ b/test/tests.zig @@ -47,12 +47,13 @@ const test_targets = []TestTarget{ const max_stdout_size = 1 * 1024 * 1024; // 1 MB -pub fn addCompareOutputTests(b: *build.Builder, test_filter: ?[]const u8) *build.Step { +pub fn addCompareOutputTests(b: *build.Builder, test_filter: ?[]const u8, modes: []const Mode) *build.Step { const cases = b.allocator.create(CompareOutputContext{ .b = b, .step = b.step("test-compare-output", "Run the compare output tests"), .test_index = 0, .test_filter = test_filter, + .modes = modes, }) catch unreachable; compare_output.addCases(cases); @@ -60,12 +61,13 @@ pub fn addCompareOutputTests(b: *build.Builder, test_filter: ?[]const u8) *build return cases.step; } -pub fn addRuntimeSafetyTests(b: *build.Builder, test_filter: ?[]const u8) *build.Step { +pub fn addRuntimeSafetyTests(b: *build.Builder, test_filter: ?[]const u8, modes: []const Mode) *build.Step { const cases = b.allocator.create(CompareOutputContext{ .b = b, .step = b.step("test-runtime-safety", "Run the runtime safety tests"), .test_index = 0, .test_filter = test_filter, + .modes = modes, }) catch unreachable; runtime_safety.addCases(cases); @@ -73,12 +75,13 @@ pub fn addRuntimeSafetyTests(b: *build.Builder, test_filter: ?[]const u8) *build return cases.step; } -pub fn addCompileErrorTests(b: *build.Builder, test_filter: ?[]const u8) *build.Step { +pub fn addCompileErrorTests(b: *build.Builder, test_filter: ?[]const u8, modes: []const Mode) *build.Step { const cases = b.allocator.create(CompileErrorContext{ .b = b, .step = b.step("test-compile-errors", "Run the compile error tests"), .test_index = 0, .test_filter = test_filter, + .modes = modes, }) catch unreachable; compile_errors.addCases(cases); @@ -99,12 +102,13 @@ pub fn addBuildExampleTests(b: *build.Builder, test_filter: ?[]const u8) *build. return cases.step; } -pub fn addAssembleAndLinkTests(b: *build.Builder, test_filter: ?[]const u8) *build.Step { +pub fn addAssembleAndLinkTests(b: *build.Builder, test_filter: ?[]const u8, modes: []const Mode) *build.Step { const cases = b.allocator.create(CompareOutputContext{ .b = b, .step = b.step("test-asm-link", "Run the assemble and link tests"), .test_index = 0, .test_filter = test_filter, + .modes = modes, }) catch unreachable; assemble_and_link.addCases(cases); @@ -173,6 +177,7 @@ pub const CompareOutputContext = struct { step: *build.Step, test_index: usize, test_filter: ?[]const u8, + modes: []const Mode, const Special = enum { None, @@ -423,12 +428,7 @@ pub const CompareOutputContext = struct { self.step.dependOn(&run_and_cmp_output.step); }, Special.None => { - for ([]Mode{ - Mode.Debug, - Mode.ReleaseSafe, - Mode.ReleaseFast, - Mode.ReleaseSmall, - }) |mode| { + for (self.modes) |mode| { const annotated_case_name = fmt.allocPrint(self.b.allocator, "{} {} ({})", "compare-output", case.name, @tagName(mode)) catch unreachable; if (self.test_filter) |filter| { if (mem.indexOf(u8, annotated_case_name, filter) == null) continue; @@ -483,6 +483,7 @@ pub const CompileErrorContext = struct { step: *build.Step, test_index: usize, test_filter: ?[]const u8, + modes: []const Mode, const TestCase = struct { name: []const u8, @@ -673,10 +674,7 @@ pub const CompileErrorContext = struct { pub fn addCase(self: *CompileErrorContext, case: *const TestCase) void { const b = self.b; - for ([]Mode{ - Mode.Debug, - Mode.ReleaseFast, - }) |mode| { + for (self.modes) |mode| { const annotated_case_name = fmt.allocPrint(self.b.allocator, "compile-error {} ({})", case.name, @tagName(mode)) catch unreachable; if (self.test_filter) |filter| { if (mem.indexOf(u8, annotated_case_name, filter) == null) continue; -- cgit v1.2.3 From 278829fc2cc23e55b09915ce07ce1ec2dbf7e68b Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Sat, 14 Jul 2018 15:45:15 -0400 Subject: self-hosted: adding a fn to an llvm module --- src-self-hosted/codegen.zig | 61 ++++++++++++++++++ src-self-hosted/ir.zig | 9 +-- src-self-hosted/llvm.zig | 23 ++++++- src-self-hosted/main.zig | 7 ++- src-self-hosted/module.zig | 112 ++++++++++++++++++++++----------- src-self-hosted/test.zig | 11 +++- src-self-hosted/type.zig | 147 +++++++++++++++++++++++++++++++++++++++++++- src-self-hosted/value.zig | 20 ++++-- std/atomic/int.zig | 18 ++++-- std/event/loop.zig | 1 - 10 files changed, 346 insertions(+), 63 deletions(-) create mode 100644 src-self-hosted/codegen.zig (limited to 'std/atomic') diff --git a/src-self-hosted/codegen.zig b/src-self-hosted/codegen.zig new file mode 100644 index 0000000000..df8f451856 --- /dev/null +++ b/src-self-hosted/codegen.zig @@ -0,0 +1,61 @@ +const std = @import("std"); +// TODO codegen pretends that Module is renamed to Build because I plan to +// do that refactor at some point +const Build = @import("module.zig").Module; +// we go through llvm instead of c for 2 reasons: +// 1. to avoid accidentally calling the non-thread-safe functions +// 2. patch up some of the types to remove nullability +const llvm = @import("llvm.zig"); +const ir = @import("ir.zig"); +const Value = @import("value.zig").Value; +const Type = @import("type.zig").Type; +const event = std.event; + +pub async fn renderToLlvm(build: *Build, fn_val: *Value.Fn, code: *ir.Code) !void { + fn_val.base.ref(); + defer fn_val.base.deref(build); + defer code.destroy(build.a()); + + const llvm_handle = try build.event_loop_local.getAnyLlvmContext(); + defer llvm_handle.release(build.event_loop_local); + + const context = llvm_handle.node.data; + + const module = llvm.ModuleCreateWithNameInContext(build.name.ptr(), context) orelse return error.OutOfMemory; + defer llvm.DisposeModule(module); + + const builder = llvm.CreateBuilderInContext(context) orelse return error.OutOfMemory; + defer llvm.DisposeBuilder(builder); + + var cunit = CompilationUnit{ + .build = build, + .module = module, + .builder = builder, + .context = context, + .lock = event.Lock.init(build.loop), + }; + + try renderToLlvmModule(&cunit, fn_val, code); + + if (build.verbose_llvm_ir) { + llvm.DumpModule(cunit.module); + } +} + +pub const CompilationUnit = struct { + build: *Build, + module: llvm.ModuleRef, + builder: llvm.BuilderRef, + context: llvm.ContextRef, + lock: event.Lock, + + fn a(self: *CompilationUnit) *std.mem.Allocator { + return self.build.a(); + } +}; + +pub fn renderToLlvmModule(cunit: *CompilationUnit, fn_val: *Value.Fn, code: *ir.Code) !void { + // TODO audit more of codegen.cpp:fn_llvm_value and port more logic + const llvm_fn_type = try fn_val.base.typeof.getLlvmType(cunit); + const llvm_fn = llvm.AddFunction(cunit.module, fn_val.symbol_name.ptr(), llvm_fn_type); +} diff --git a/src-self-hosted/ir.zig b/src-self-hosted/ir.zig index 22161a0c27..f1c395a790 100644 --- a/src-self-hosted/ir.zig +++ b/src-self-hosted/ir.zig @@ -375,15 +375,8 @@ pub const Instruction = struct { pub fn analyze(self: *const AddImplicitReturnType, ira: *Analyze) !*Instruction { const target = try self.params.target.getAsParam(); - try ira.src_implicit_return_type_list.append(target); - - return ira.irb.build( - AddImplicitReturnType, - self.base.scope, - self.base.span, - Params{ .target = target }, - ); + return ira.irb.buildConstVoid(self.base.scope, self.base.span, true); } }; }; diff --git a/src-self-hosted/llvm.zig b/src-self-hosted/llvm.zig index 391a92cd63..b815f75b05 100644 --- a/src-self-hosted/llvm.zig +++ b/src-self-hosted/llvm.zig @@ -2,10 +2,27 @@ const builtin = @import("builtin"); const c = @import("c.zig"); const assert = @import("std").debug.assert; -pub const ValueRef = removeNullability(c.LLVMValueRef); -pub const ModuleRef = removeNullability(c.LLVMModuleRef); -pub const ContextRef = removeNullability(c.LLVMContextRef); pub const BuilderRef = removeNullability(c.LLVMBuilderRef); +pub const ContextRef = removeNullability(c.LLVMContextRef); +pub const ModuleRef = removeNullability(c.LLVMModuleRef); +pub const ValueRef = removeNullability(c.LLVMValueRef); +pub const TypeRef = removeNullability(c.LLVMTypeRef); + +pub const AddFunction = c.LLVMAddFunction; +pub const CreateBuilderInContext = c.LLVMCreateBuilderInContext; +pub const DisposeBuilder = c.LLVMDisposeBuilder; +pub const DisposeModule = c.LLVMDisposeModule; +pub const DumpModule = c.LLVMDumpModule; +pub const ModuleCreateWithNameInContext = c.LLVMModuleCreateWithNameInContext; +pub const VoidTypeInContext = c.LLVMVoidTypeInContext; + +pub const FunctionType = LLVMFunctionType; +extern fn LLVMFunctionType( + ReturnType: TypeRef, + ParamTypes: [*]TypeRef, + ParamCount: c_uint, + IsVarArg: c_int, +) ?TypeRef; fn removeNullability(comptime T: type) type { comptime assert(@typeId(T) == builtin.TypeId.Optional); diff --git a/src-self-hosted/main.zig b/src-self-hosted/main.zig index 972aaae9ac..77ec7f6d32 100644 --- a/src-self-hosted/main.zig +++ b/src-self-hosted/main.zig @@ -14,6 +14,7 @@ const c = @import("c.zig"); const introspect = @import("introspect.zig"); const Args = arg.Args; const Flag = arg.Flag; +const EventLoopLocal = @import("module.zig").EventLoopLocal; const Module = @import("module.zig").Module; const Target = @import("target.zig").Target; const errmsg = @import("errmsg.zig"); @@ -386,9 +387,13 @@ fn buildOutputType(allocator: *Allocator, args: []const []const u8, out_type: Mo var loop: event.Loop = undefined; try loop.initMultiThreaded(allocator); + defer loop.deinit(); + + var event_loop_local = EventLoopLocal.init(&loop); + defer event_loop_local.deinit(); var module = try Module.create( - &loop, + &event_loop_local, root_name, root_source_file, Target.Native, diff --git a/src-self-hosted/module.zig b/src-self-hosted/module.zig index 3fbe6d54ad..617bd0d44a 100644 --- a/src-self-hosted/module.zig +++ b/src-self-hosted/module.zig @@ -25,14 +25,58 @@ const ParsedFile = @import("parsed_file.zig").ParsedFile; const Value = @import("value.zig").Value; const Type = Value.Type; const Span = errmsg.Span; +const codegen = @import("codegen.zig"); + +/// Data that is local to the event loop. +pub const EventLoopLocal = struct { + loop: *event.Loop, + llvm_handle_pool: std.atomic.Stack(llvm.ContextRef), + + fn init(loop: *event.Loop) EventLoopLocal { + return EventLoopLocal{ + .loop = loop, + .llvm_handle_pool = std.atomic.Stack(llvm.ContextRef).init(), + }; + } + + fn deinit(self: *EventLoopLocal) void { + while (self.llvm_handle_pool.pop()) |node| { + c.LLVMContextDispose(node.data); + self.loop.allocator.destroy(node); + } + } + + /// Gets an exclusive handle on any LlvmContext. + /// Caller must release the handle when done. + pub fn getAnyLlvmContext(self: *EventLoopLocal) !LlvmHandle { + if (self.llvm_handle_pool.pop()) |node| return LlvmHandle{ .node = node }; + + const context_ref = c.LLVMContextCreate() orelse return error.OutOfMemory; + errdefer c.LLVMContextDispose(context_ref); + + const node = try self.loop.allocator.create(std.atomic.Stack(llvm.ContextRef).Node{ + .next = undefined, + .data = context_ref, + }); + errdefer self.loop.allocator.destroy(node); + + return LlvmHandle{ .node = node }; + } +}; + +pub const LlvmHandle = struct { + node: *std.atomic.Stack(llvm.ContextRef).Node, + + pub fn release(self: LlvmHandle, event_loop_local: *EventLoopLocal) void { + event_loop_local.llvm_handle_pool.push(self.node); + } +}; pub const Module = struct { + event_loop_local: *EventLoopLocal, loop: *event.Loop, name: Buffer, root_src_path: ?[]const u8, - llvm_module: llvm.ModuleRef, - context: llvm.ContextRef, - builder: llvm.BuilderRef, target: Target, build_mode: builtin.Mode, zig_lib_dir: []const u8, @@ -187,7 +231,7 @@ pub const Module = struct { }; pub fn create( - loop: *event.Loop, + event_loop_local: *EventLoopLocal, name: []const u8, root_src_path: ?[]const u8, target: *const Target, @@ -196,29 +240,20 @@ pub const Module = struct { zig_lib_dir: []const u8, cache_dir: []const u8, ) !*Module { + const loop = event_loop_local.loop; + var name_buffer = try Buffer.init(loop.allocator, name); errdefer name_buffer.deinit(); - const context = c.LLVMContextCreate() orelse return error.OutOfMemory; - errdefer c.LLVMContextDispose(context); - - const llvm_module = c.LLVMModuleCreateWithNameInContext(name_buffer.ptr(), context) orelse return error.OutOfMemory; - errdefer c.LLVMDisposeModule(llvm_module); - - const builder = c.LLVMCreateBuilderInContext(context) orelse return error.OutOfMemory; - errdefer c.LLVMDisposeBuilder(builder); - const events = try event.Channel(Event).create(loop, 0); errdefer events.destroy(); const module = try loop.allocator.create(Module{ .loop = loop, + .event_loop_local = event_loop_local, .events = events, .name = name_buffer, .root_src_path = root_src_path, - .llvm_module = llvm_module, - .context = context, - .builder = builder, .target = target.*, .kind = kind, .build_mode = build_mode, @@ -290,7 +325,7 @@ pub const Module = struct { .base = Value{ .id = Value.Id.Type, .typeof = undefined, - .ref_count = 3, // 3 because it references itself twice + .ref_count = std.atomic.Int(usize).init(3), // 3 because it references itself twice }, .id = builtin.TypeId.Type, }, @@ -305,7 +340,7 @@ pub const Module = struct { .base = Value{ .id = Value.Id.Type, .typeof = &Type.MetaType.get(module).base, - .ref_count = 1, + .ref_count = std.atomic.Int(usize).init(1), }, .id = builtin.TypeId.Void, }, @@ -317,7 +352,7 @@ pub const Module = struct { .base = Value{ .id = Value.Id.Type, .typeof = &Type.MetaType.get(module).base, - .ref_count = 1, + .ref_count = std.atomic.Int(usize).init(1), }, .id = builtin.TypeId.NoReturn, }, @@ -329,7 +364,7 @@ pub const Module = struct { .base = Value{ .id = Value.Id.Type, .typeof = &Type.MetaType.get(module).base, - .ref_count = 1, + .ref_count = std.atomic.Int(usize).init(1), }, .id = builtin.TypeId.Bool, }, @@ -340,7 +375,7 @@ pub const Module = struct { .base = Value{ .id = Value.Id.Void, .typeof = &Type.Void.get(module).base, - .ref_count = 1, + .ref_count = std.atomic.Int(usize).init(1), }, }); errdefer module.a().destroy(module.void_value); @@ -349,7 +384,7 @@ pub const Module = struct { .base = Value{ .id = Value.Id.Bool, .typeof = &Type.Bool.get(module).base, - .ref_count = 1, + .ref_count = std.atomic.Int(usize).init(1), }, .x = true, }); @@ -359,7 +394,7 @@ pub const Module = struct { .base = Value{ .id = Value.Id.Bool, .typeof = &Type.Bool.get(module).base, - .ref_count = 1, + .ref_count = std.atomic.Int(usize).init(1), }, .x = false, }); @@ -369,16 +404,12 @@ pub const Module = struct { .base = Value{ .id = Value.Id.NoReturn, .typeof = &Type.NoReturn.get(module).base, - .ref_count = 1, + .ref_count = std.atomic.Int(usize).init(1), }, }); errdefer module.a().destroy(module.noreturn_value); } - fn dump(self: *Module) void { - c.LLVMDumpModule(self.module); - } - pub fn destroy(self: *Module) void { self.noreturn_value.base.deref(self); self.void_value.base.deref(self); @@ -389,9 +420,6 @@ pub const Module = struct { self.meta_type.base.base.deref(self); self.events.destroy(); - c.LLVMDisposeBuilder(self.builder); - c.LLVMDisposeModule(self.llvm_module); - c.LLVMContextDispose(self.context); self.name.deinit(); self.a().destroy(self); @@ -657,10 +685,19 @@ async fn generateDeclFn(module: *Module, fn_decl: *Decl.Fn) !void { const fndef_scope = try Scope.FnDef.create(module, fn_decl.base.parent_scope); defer fndef_scope.base.deref(module); - const fn_type = try Type.Fn.create(module); + // TODO actually look at the return type of the AST + const return_type = &Type.Void.get(module).base; + defer return_type.base.deref(module); + + const is_var_args = false; + const params = ([*]Type.Fn.Param)(undefined)[0..0]; + const fn_type = try Type.Fn.create(module, return_type, params, is_var_args); defer fn_type.base.base.deref(module); - const fn_val = try Value.Fn.create(module, fn_type, fndef_scope); + var symbol_name = try std.Buffer.init(module.a(), fn_decl.base.name); + errdefer symbol_name.deinit(); + + const fn_val = try Value.Fn.create(module, fn_type, fndef_scope, symbol_name); defer fn_val.base.deref(module); fn_decl.value = Decl.Fn.Val{ .Ok = fn_val }; @@ -674,6 +711,7 @@ async fn generateDeclFn(module: *Module, fn_decl: *Decl.Fn) !void { ) catch unreachable)) catch |err| switch (err) { // This poison value should not cause the errdefers to run. It simply means // that self.compile_errors is populated. + // TODO https://github.com/ziglang/zig/issues/769 error.SemanticAnalysisFailed => return {}, else => return err, }; @@ -692,14 +730,18 @@ async fn generateDeclFn(module: *Module, fn_decl: *Decl.Fn) !void { ) catch unreachable)) catch |err| switch (err) { // This poison value should not cause the errdefers to run. It simply means // that self.compile_errors is populated. + // TODO https://github.com/ziglang/zig/issues/769 error.SemanticAnalysisFailed => return {}, else => return err, }; - defer analyzed_code.destroy(module.a()); + errdefer analyzed_code.destroy(module.a()); if (module.verbose_ir) { std.debug.warn("analyzed:\n"); analyzed_code.dump(); } - // TODO now render to LLVM module + + // Kick off rendering to LLVM module, but it doesn't block the fn decl + // analysis from being complete. + try module.build_group.call(codegen.renderToLlvm, module, fn_val, analyzed_code); } diff --git a/src-self-hosted/test.zig b/src-self-hosted/test.zig index 4455352f95..e609eb2791 100644 --- a/src-self-hosted/test.zig +++ b/src-self-hosted/test.zig @@ -6,6 +6,7 @@ const Module = @import("module.zig").Module; const introspect = @import("introspect.zig"); const assertOrPanic = std.debug.assertOrPanic; const errmsg = @import("errmsg.zig"); +const EventLoopLocal = @import("module.zig").EventLoopLocal; test "compile errors" { var ctx: TestContext = undefined; @@ -22,6 +23,7 @@ const allocator = std.heap.c_allocator; pub const TestContext = struct { loop: std.event.Loop, + event_loop_local: EventLoopLocal, zig_lib_dir: []u8, zig_cache_dir: []u8, file_index: std.atomic.Int(usize), @@ -34,6 +36,7 @@ pub const TestContext = struct { self.* = TestContext{ .any_err = {}, .loop = undefined, + .event_loop_local = undefined, .zig_lib_dir = undefined, .zig_cache_dir = undefined, .group = undefined, @@ -43,6 +46,9 @@ pub const TestContext = struct { try self.loop.initMultiThreaded(allocator); errdefer self.loop.deinit(); + self.event_loop_local = EventLoopLocal.init(&self.loop); + errdefer self.event_loop_local.deinit(); + self.group = std.event.Group(error!void).init(&self.loop); errdefer self.group.cancelAll(); @@ -60,6 +66,7 @@ pub const TestContext = struct { std.os.deleteTree(allocator, tmp_dir_name) catch {}; allocator.free(self.zig_cache_dir); allocator.free(self.zig_lib_dir); + self.event_loop_local.deinit(); self.loop.deinit(); } @@ -83,7 +90,7 @@ pub const TestContext = struct { msg: []const u8, ) !void { var file_index_buf: [20]u8 = undefined; - const file_index = try std.fmt.bufPrint(file_index_buf[0..], "{}", self.file_index.next()); + const file_index = try std.fmt.bufPrint(file_index_buf[0..], "{}", self.file_index.incr()); const file1_path = try std.os.path.join(allocator, tmp_dir_name, file_index, file1); if (std.os.path.dirname(file1_path)) |dirname| { @@ -94,7 +101,7 @@ pub const TestContext = struct { try std.io.writeFile(allocator, file1_path, source); var module = try Module.create( - &self.loop, + &self.event_loop_local, "test", file1_path, Target.Native, diff --git a/src-self-hosted/type.zig b/src-self-hosted/type.zig index 66e1470cc0..e4c31018a3 100644 --- a/src-self-hosted/type.zig +++ b/src-self-hosted/type.zig @@ -1,7 +1,10 @@ +const std = @import("std"); const builtin = @import("builtin"); const Scope = @import("scope.zig").Scope; const Module = @import("module.zig").Module; const Value = @import("value.zig").Value; +const llvm = @import("llvm.zig"); +const CompilationUnit = @import("codegen.zig").CompilationUnit; pub const Type = struct { base: Value, @@ -39,6 +42,36 @@ pub const Type = struct { } } + pub fn getLlvmType(base: *Type, cunit: *CompilationUnit) (error{OutOfMemory}!llvm.TypeRef) { + switch (base.id) { + Id.Struct => return @fieldParentPtr(Struct, "base", base).getLlvmType(cunit), + Id.Fn => return @fieldParentPtr(Fn, "base", base).getLlvmType(cunit), + Id.Type => unreachable, + Id.Void => unreachable, + Id.Bool => return @fieldParentPtr(Bool, "base", base).getLlvmType(cunit), + Id.NoReturn => unreachable, + Id.Int => return @fieldParentPtr(Int, "base", base).getLlvmType(cunit), + Id.Float => return @fieldParentPtr(Float, "base", base).getLlvmType(cunit), + Id.Pointer => return @fieldParentPtr(Pointer, "base", base).getLlvmType(cunit), + Id.Array => return @fieldParentPtr(Array, "base", base).getLlvmType(cunit), + Id.ComptimeFloat => unreachable, + Id.ComptimeInt => unreachable, + Id.Undefined => unreachable, + Id.Null => unreachable, + Id.Optional => return @fieldParentPtr(Optional, "base", base).getLlvmType(cunit), + Id.ErrorUnion => return @fieldParentPtr(ErrorUnion, "base", base).getLlvmType(cunit), + Id.ErrorSet => return @fieldParentPtr(ErrorSet, "base", base).getLlvmType(cunit), + Id.Enum => return @fieldParentPtr(Enum, "base", base).getLlvmType(cunit), + Id.Union => return @fieldParentPtr(Union, "base", base).getLlvmType(cunit), + Id.Namespace => unreachable, + Id.Block => unreachable, + Id.BoundFn => return @fieldParentPtr(BoundFn, "base", base).getLlvmType(cunit), + Id.ArgTuple => unreachable, + Id.Opaque => return @fieldParentPtr(Opaque, "base", base).getLlvmType(cunit), + Id.Promise => return @fieldParentPtr(Promise, "base", base).getLlvmType(cunit), + } + } + pub fn dump(base: *const Type) void { std.debug.warn("{}", @tagName(base.id)); } @@ -54,27 +87,72 @@ pub const Type = struct { pub fn destroy(self: *Struct, module: *Module) void { module.a().destroy(self); } + + pub fn getLlvmType(self: *Struct, cunit: *CompilationUnit) llvm.TypeRef { + @panic("TODO"); + } }; pub const Fn = struct { base: Type, + return_type: *Type, + params: []Param, + is_var_args: bool, - pub fn create(module: *Module) !*Fn { - return module.a().create(Fn{ + pub const Param = struct { + is_noalias: bool, + typeof: *Type, + }; + + pub fn create(module: *Module, return_type: *Type, params: []Param, is_var_args: bool) !*Fn { + const result = try module.a().create(Fn{ .base = Type{ .base = Value{ .id = Value.Id.Type, .typeof = &MetaType.get(module).base, - .ref_count = 1, + .ref_count = std.atomic.Int(usize).init(1), }, .id = builtin.TypeId.Fn, }, + .return_type = return_type, + .params = params, + .is_var_args = is_var_args, }); + errdefer module.a().destroy(result); + + result.return_type.base.ref(); + for (result.params) |param| { + param.typeof.base.ref(); + } + return result; } pub fn destroy(self: *Fn, module: *Module) void { + self.return_type.base.deref(module); + for (self.params) |param| { + param.typeof.base.deref(module); + } module.a().destroy(self); } + + pub fn getLlvmType(self: *Fn, cunit: *CompilationUnit) !llvm.TypeRef { + const llvm_return_type = switch (self.return_type.id) { + Type.Id.Void => llvm.VoidTypeInContext(cunit.context) orelse return error.OutOfMemory, + else => try self.return_type.getLlvmType(cunit), + }; + const llvm_param_types = try cunit.a().alloc(llvm.TypeRef, self.params.len); + defer cunit.a().free(llvm_param_types); + for (llvm_param_types) |*llvm_param_type, i| { + llvm_param_type.* = try self.params[i].typeof.getLlvmType(cunit); + } + + return llvm.FunctionType( + llvm_return_type, + llvm_param_types.ptr, + @intCast(c_uint, llvm_param_types.len), + @boolToInt(self.is_var_args), + ) orelse error.OutOfMemory; + } }; pub const MetaType = struct { @@ -118,6 +196,10 @@ pub const Type = struct { pub fn destroy(self: *Bool, module: *Module) void { module.a().destroy(self); } + + pub fn getLlvmType(self: *Bool, cunit: *CompilationUnit) llvm.TypeRef { + @panic("TODO"); + } }; pub const NoReturn = struct { @@ -140,6 +222,10 @@ pub const Type = struct { pub fn destroy(self: *Int, module: *Module) void { module.a().destroy(self); } + + pub fn getLlvmType(self: *Int, cunit: *CompilationUnit) llvm.TypeRef { + @panic("TODO"); + } }; pub const Float = struct { @@ -148,6 +234,10 @@ pub const Type = struct { pub fn destroy(self: *Float, module: *Module) void { module.a().destroy(self); } + + pub fn getLlvmType(self: *Float, cunit: *CompilationUnit) llvm.TypeRef { + @panic("TODO"); + } }; pub const Pointer = struct { base: Type, @@ -180,14 +270,24 @@ pub const Type = struct { ) *Pointer { @panic("TODO get pointer"); } + + pub fn getLlvmType(self: *Pointer, cunit: *CompilationUnit) llvm.TypeRef { + @panic("TODO"); + } }; + pub const Array = struct { base: Type, pub fn destroy(self: *Array, module: *Module) void { module.a().destroy(self); } + + pub fn getLlvmType(self: *Array, cunit: *CompilationUnit) llvm.TypeRef { + @panic("TODO"); + } }; + pub const ComptimeFloat = struct { base: Type, @@ -195,6 +295,7 @@ pub const Type = struct { module.a().destroy(self); } }; + pub const ComptimeInt = struct { base: Type, @@ -202,6 +303,7 @@ pub const Type = struct { module.a().destroy(self); } }; + pub const Undefined = struct { base: Type, @@ -209,6 +311,7 @@ pub const Type = struct { module.a().destroy(self); } }; + pub const Null = struct { base: Type, @@ -216,41 +319,67 @@ pub const Type = struct { module.a().destroy(self); } }; + pub const Optional = struct { base: Type, pub fn destroy(self: *Optional, module: *Module) void { module.a().destroy(self); } + + pub fn getLlvmType(self: *Optional, cunit: *CompilationUnit) llvm.TypeRef { + @panic("TODO"); + } }; + pub const ErrorUnion = struct { base: Type, pub fn destroy(self: *ErrorUnion, module: *Module) void { module.a().destroy(self); } + + pub fn getLlvmType(self: *ErrorUnion, cunit: *CompilationUnit) llvm.TypeRef { + @panic("TODO"); + } }; + pub const ErrorSet = struct { base: Type, pub fn destroy(self: *ErrorSet, module: *Module) void { module.a().destroy(self); } + + pub fn getLlvmType(self: *ErrorSet, cunit: *CompilationUnit) llvm.TypeRef { + @panic("TODO"); + } }; + pub const Enum = struct { base: Type, pub fn destroy(self: *Enum, module: *Module) void { module.a().destroy(self); } + + pub fn getLlvmType(self: *Enum, cunit: *CompilationUnit) llvm.TypeRef { + @panic("TODO"); + } }; + pub const Union = struct { base: Type, pub fn destroy(self: *Union, module: *Module) void { module.a().destroy(self); } + + pub fn getLlvmType(self: *Union, cunit: *CompilationUnit) llvm.TypeRef { + @panic("TODO"); + } }; + pub const Namespace = struct { base: Type, @@ -273,6 +402,10 @@ pub const Type = struct { pub fn destroy(self: *BoundFn, module: *Module) void { module.a().destroy(self); } + + pub fn getLlvmType(self: *BoundFn, cunit: *CompilationUnit) llvm.TypeRef { + @panic("TODO"); + } }; pub const ArgTuple = struct { @@ -289,6 +422,10 @@ pub const Type = struct { pub fn destroy(self: *Opaque, module: *Module) void { module.a().destroy(self); } + + pub fn getLlvmType(self: *Opaque, cunit: *CompilationUnit) llvm.TypeRef { + @panic("TODO"); + } }; pub const Promise = struct { @@ -297,5 +434,9 @@ pub const Type = struct { pub fn destroy(self: *Promise, module: *Module) void { module.a().destroy(self); } + + pub fn getLlvmType(self: *Promise, cunit: *CompilationUnit) llvm.TypeRef { + @panic("TODO"); + } }; }; diff --git a/src-self-hosted/value.zig b/src-self-hosted/value.zig index 7ee594b41c..779e5c2e45 100644 --- a/src-self-hosted/value.zig +++ b/src-self-hosted/value.zig @@ -8,15 +8,16 @@ const Module = @import("module.zig").Module; pub const Value = struct { id: Id, typeof: *Type, - ref_count: usize, + ref_count: std.atomic.Int(usize), + /// Thread-safe pub fn ref(base: *Value) void { - base.ref_count += 1; + _ = base.ref_count.incr(); } + /// Thread-safe pub fn deref(base: *Value, module: *Module) void { - base.ref_count -= 1; - if (base.ref_count == 0) { + if (base.ref_count.decr() == 1) { base.typeof.base.deref(module); switch (base.id) { Id.Type => @fieldParentPtr(Type, "base", base).destroy(module), @@ -52,6 +53,10 @@ pub const Value = struct { pub const Fn = struct { base: Value, + /// The main external name that is used in the .o file. + /// TODO https://github.com/ziglang/zig/issues/265 + symbol_name: std.Buffer, + /// parent should be the top level decls or container decls fndef_scope: *Scope.FnDef, @@ -62,16 +67,18 @@ pub const Value = struct { block_scope: *Scope.Block, /// Creates a Fn value with 1 ref - pub fn create(module: *Module, fn_type: *Type.Fn, fndef_scope: *Scope.FnDef) !*Fn { + /// Takes ownership of symbol_name + pub fn create(module: *Module, fn_type: *Type.Fn, fndef_scope: *Scope.FnDef, symbol_name: std.Buffer) !*Fn { const self = try module.a().create(Fn{ .base = Value{ .id = Value.Id.Fn, .typeof = &fn_type.base, - .ref_count = 1, + .ref_count = std.atomic.Int(usize).init(1), }, .fndef_scope = fndef_scope, .child_scope = &fndef_scope.base, .block_scope = undefined, + .symbol_name = symbol_name, }); fn_type.base.base.ref(); fndef_scope.fn_val = self; @@ -81,6 +88,7 @@ pub const Value = struct { pub fn destroy(self: *Fn, module: *Module) void { self.fndef_scope.base.deref(module); + self.symbol_name.deinit(); module.a().destroy(self); } }; diff --git a/std/atomic/int.zig b/std/atomic/int.zig index 7042bca78d..d51454c673 100644 --- a/std/atomic/int.zig +++ b/std/atomic/int.zig @@ -4,16 +4,26 @@ const AtomicOrder = builtin.AtomicOrder; /// Thread-safe, lock-free integer pub fn Int(comptime T: type) type { return struct { - value: T, + unprotected_value: T, pub const Self = this; pub fn init(init_val: T) Self { - return Self{ .value = init_val }; + return Self{ .unprotected_value = init_val }; } - pub fn next(self: *Self) T { - return @atomicRmw(T, &self.value, builtin.AtomicRmwOp.Add, 1, AtomicOrder.SeqCst); + /// Returns previous value + pub fn incr(self: *Self) T { + return @atomicRmw(T, &self.unprotected_value, builtin.AtomicRmwOp.Add, 1, AtomicOrder.SeqCst); + } + + /// Returns previous value + pub fn decr(self: *Self) T { + return @atomicRmw(T, &self.unprotected_value, builtin.AtomicRmwOp.Sub, 1, AtomicOrder.SeqCst); + } + + pub fn get(self: *Self) T { + return @atomicLoad(T, &self.unprotected_value, AtomicOrder.SeqCst); } }; } diff --git a/std/event/loop.zig b/std/event/loop.zig index ba75109a72..fc927592b9 100644 --- a/std/event/loop.zig +++ b/std/event/loop.zig @@ -101,7 +101,6 @@ pub const Loop = struct { errdefer self.deinitOsData(); } - /// must call stop before deinit pub fn deinit(self: *Loop) void { self.deinitOsData(); self.allocator.free(self.extra_threads); -- cgit v1.2.3