From 9751a0ae045110fb615c866b94ad47680b9c48c7 Mon Sep 17 00:00:00 2001
From: Andrew Kelley <superjoe30@gmail.com>
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.
---
 std/atomic/stack.zig | 32 ++++++++++++++++++++------------
 1 file changed, 20 insertions(+), 12 deletions(-)

(limited to 'std/atomic/stack.zig')

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),
-- 
cgit v1.2.3