code review 5993043: runtime: add lock-free stack (issue 5993043)

[dvy...@google.com]

Reviewers: golang-dev_googlegroups.com,

Message:
Hello golan...@googlegroups.com,

I'd like you to review this change to
https://go.googlecode.com/hg/


Description:
runtime: add lock-free stack
This is factored out part of the:
http://codereview.appspot.com/5279048/
(parallel GC)

Please review this at http://codereview.appspot.com/5993043/

Affected files:
M src/pkg/runtime/export_test.go
A src/pkg/runtime/lfstack.c
M src/pkg/runtime/runtime.h


Index: src/pkg/runtime/export_test.go
===================================================================
--- a/src/pkg/runtime/export_test.go
+++ b/src/pkg/runtime/export_test.go
@@ -25,3 +25,14 @@
var Exitsyscall = exitsyscall
var LockedOSThread = golockedOSThread
var Stackguard = stackguard
+
+type LFNode struct {
+ Next *LFNode
+ Pushcnt uintptr
+}
+
+func lfstackpush(head *uint64, node *LFNode)
+func lfstackpop2(head *uint64) *LFNode
+
+var LFStackPush = lfstackpush
+var LFStackPop = lfstackpop2
Index: src/pkg/runtime/lfstack.c
===================================================================
new file mode 100644
--- /dev/null
+++ b/src/pkg/runtime/lfstack.c
@@ -0,0 +1,64 @@
+// Copyright 2012 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Lock-free stack.
+
+#include "runtime.h"
+#include "arch_GOARCH.h"
+
+#ifdef _64BIT
+// Amd64 uses 48-bit virtual addresses, 47-th bit is used as kernel/user
flag.
+// So we use 17msb of pointers as ABA counter.
+# define PTR_BITS 47
+#else
+# define PTR_BITS 32
+#endif
+#define PTR_MASK ((1ull<<PTR_BITS)-1)
+
+void
+runtime·lfstackpush(uint64 *head, LFNode *node)
+{
+ uint64 old, new;
+
+ if((uint64)node != ((uint64)node&PTR_MASK)) {
+ runtime·printf("p=%p\n", node);
+ runtime·throw("runtime·lfstackpush: invalid pointer");
+ }
+
+ node->pushcnt++;
+ new = (uint64)node|(((uint64)node->pushcnt)<<PTR_BITS);
+ old = runtime·atomicload64(head);
+ for(;;) {
+ node->next = (LFNode*)(old&PTR_MASK);
+ if(runtime·cas64(head, &old, new))
+ break;
+ }
+}
+
+LFNode*
+runtime·lfstackpop(uint64 *head)
+{
+ LFNode *node, *node2;
+ uint64 old, new;
+
+ old = runtime·atomicload64(head);
+ for(;;) {
+ if(old == 0)
+ return nil;
+ node = (LFNode*)(old&PTR_MASK);
+ node2 = runtime·atomicloadp(&node->next);
+ new = 0;
+ if(node2 != nil)
+ new = (uint64)node2|(((uint64)node2->pushcnt)<<PTR_BITS);
+ if(runtime·cas64(head, &old, new))
+ return node;
+ }
+}
+
+void
+runtime·lfstackpop2(uint64 *head, LFNode *node)
+{
+ node = runtime·lfstackpop(head);
+ FLUSH(&node);
+}
Index: src/pkg/runtime/runtime.h
===================================================================
--- a/src/pkg/runtime/runtime.h
+++ b/src/pkg/runtime/runtime.h
@@ -72,6 +72,7 @@
typedef struct Timers Timers;
typedef struct Timer Timer;
typedef struct GCStats GCStats;
+typedef struct LFNode LFNode;

/*
* per-cpu declaration.
@@ -351,6 +352,13 @@
Eface arg;
};

+// Lock-free stack node.
+struct LFNode
+{
+ LFNode *next;
+ uintptr pushcnt;
+};
+
/*
* defined macros
* you need super-gopher-guru privilege
@@ -652,6 +660,12 @@
void runtime·futexwakeup(uint32*, uint32);

/*
+ * Lock-free stack.
+ */
+void runtime·lfstackpush(uint64 *head, LFNode *node);
+LFNode* runtime·lfstackpop(uint64 *head);
+
+/*
* This is consistent across Linux and BSD.
* If a new OS is added that is different, move this to
* $GOOS/$GOARCH/defs.h.

[Russ Cox]

LGTM