runtime: Multiplex goroutines onto OS threads.

From-SVN: r181772

1 files changed, 181 insertions, 0 deletions

diff --git a/libgo/runtime/sema.goc b/libgo/runtime/sema.goc
new file mode 100644
index 0000000..dd58cf3
--- /dev/null
+++ b/libgo/runtime/sema.goc
@@ -0,0 +1,181 @@
+// Copyright 2009 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.
+
+// Semaphore implementation exposed to Go.
+// Intended use is provide a sleep and wakeup
+// primitive that can be used in the contended case
+// of other synchronization primitives.
+// Thus it targets the same goal as Linux's futex,
+// but it has much simpler semantics.
+//
+// That is, don't think of these as semaphores.
+// Think of them as a way to implement sleep and wakeup
+// such that every sleep is paired with a single wakeup,
+// even if, due to races, the wakeup happens before the sleep.
+//
+// See Mullender and Cox, ``Semaphores in Plan 9,''
+// http://swtch.com/semaphore.pdf
+
+package runtime
+#include "runtime.h"
+#include "arch.h"
+
+typedef struct Sema Sema;
+struct Sema
+{
+	uint32 volatile *addr;
+	G *g;
+	Sema *prev;
+	Sema *next;
+};
+
+typedef struct SemaRoot SemaRoot;
+struct SemaRoot
+{
+        Lock;
+	Sema *head;
+	Sema *tail;
+	// Number of waiters. Read w/o the lock.
+	uint32 volatile nwait;
+};
+
+// Prime to not correlate with any user patterns.
+#define SEMTABLESZ 251
+
+static union
+{
+	SemaRoot;
+	uint8 pad[CacheLineSize];
+} semtable[SEMTABLESZ];
+
+static SemaRoot*
+semroot(uint32 volatile *addr)
+{
+	return &semtable[((uintptr)addr >> 3) % SEMTABLESZ];
+}
+
+static void
+semqueue(SemaRoot *root, uint32 volatile *addr, Sema *s)
+{
+	s->g = runtime_g();
+	s->addr = addr;
+	s->next = nil;
+	s->prev = root->tail;
+	if(root->tail)
+		root->tail->next = s;
+	else
+		root->head = s;
+	root->tail = s;
+}
+
+static void
+semdequeue(SemaRoot *root, Sema *s)
+{
+	if(s->next)
+		s->next->prev = s->prev;
+	else
+		root->tail = s->prev;
+	if(s->prev)
+		s->prev->next = s->next;
+	else
+		root->head = s->next;
+	s->prev = nil;
+	s->next = nil;
+}
+
+static int32
+cansemacquire(uint32 volatile *addr)
+{
+	uint32 v;
+
+	while((v = runtime_atomicload(addr)) > 0)
+		if(runtime_cas(addr, v, v-1))
+			return 1;
+	return 0;
+}
+
+void
+runtime_semacquire(uint32 volatile *addr)
+{
+	G *g;
+	Sema s;
+	SemaRoot *root;
+
+	// Easy case.
+	if(cansemacquire(addr))
+		return;
+
+	// Harder case:
+	//	increment waiter count
+	//	try cansemacquire one more time, return if succeeded
+	//	enqueue itself as a waiter
+	//	sleep
+	//	(waiter descriptor is dequeued by signaler)
+	g = runtime_g();
+	root = semroot(addr);
+	for(;;) {
+
+		runtime_lock(root);
+		// Add ourselves to nwait to disable "easy case" in semrelease.
+		runtime_xadd(&root->nwait, 1);
+		// Check cansemacquire to avoid missed wakeup.
+		if(cansemacquire(addr)) {
+			runtime_xadd(&root->nwait, -1);
+			runtime_unlock(root);
+			return;
+		}
+		// Any semrelease after the cansemacquire knows we're waiting
+		// (we set nwait above), so go to sleep.
+		semqueue(root, addr, &s);
+		g->status = Gwaiting;
+		g->waitreason = "semacquire";
+		runtime_unlock(root);
+		runtime_gosched();
+		if(cansemacquire(addr))
+			return;
+	}
+}
+
+void
+runtime_semrelease(uint32 volatile *addr)
+{
+	Sema *s;
+	SemaRoot *root;
+
+	root = semroot(addr);
+	runtime_xadd(addr, 1);
+
+	// Easy case: no waiters?
+	// This check must happen after the xadd, to avoid a missed wakeup
+	// (see loop in semacquire).
+	if(runtime_atomicload(&root->nwait) == 0)
+		return;
+
+	// Harder case: search for a waiter and wake it.
+	runtime_lock(root);
+	if(runtime_atomicload(&root->nwait) == 0) {
+		// The count is already consumed by another goroutine,
+		// so no need to wake up another goroutine.
+		runtime_unlock(root);
+		return;
+	}
+	for(s = root->head; s; s = s->next) {
+		if(s->addr == addr) {
+			runtime_xadd(&root->nwait, -1);
+			semdequeue(root, s);
+			break;
+		}
+	}
+	runtime_unlock(root);
+	if(s)
+		runtime_ready(s->g);
+}
+
+func Semacquire(addr *uint32) {
+	runtime_semacquire(addr);
+}
+
+func Semrelease(addr *uint32) {
+	runtime_semrelease(addr);
+}