1 files changed, 275 insertions, 0 deletions
diff --git a/src/runtime/sema.go b/src/runtime/sema.go
new file mode 100644
index 000000000..26dbd30ea
--- /dev/null
+++ b/src/runtime/sema.go
@@ -0,0 +1,275 @@
+// 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
+
+import "unsafe"
+
+// Asynchronous semaphore for sync.Mutex.
+
+type semaRoot struct {
+	lock  mutex
+	head  *sudog
+	tail  *sudog
+	nwait uint32 // Number of waiters. Read w/o the lock.
+}
+
+// Prime to not correlate with any user patterns.
+const semTabSize = 251
+
+var semtable [semTabSize]struct {
+	root semaRoot
+	pad  [_CacheLineSize - unsafe.Sizeof(semaRoot{})]byte
+}
+
+// Called from sync/net packages.
+func asyncsemacquire(addr *uint32) {
+	semacquire(addr, true)
+}
+
+func asyncsemrelease(addr *uint32) {
+	semrelease(addr)
+}
+
+// Called from runtime.
+func semacquire(addr *uint32, profile bool) {
+	gp := getg()
+	if gp != gp.m.curg {
+		gothrow("semacquire not on the G stack")
+	}
+
+	// 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)
+	s := acquireSudog()
+	root := semroot(addr)
+	t0 := int64(0)
+	s.releasetime = 0
+	if profile && blockprofilerate > 0 {
+		t0 = cputicks()
+		s.releasetime = -1
+	}
+	for {
+		lock(&root.lock)
+		// Add ourselves to nwait to disable "easy case" in semrelease.
+		xadd(&root.nwait, 1)
+		// Check cansemacquire to avoid missed wakeup.
+		if cansemacquire(addr) {
+			xadd(&root.nwait, -1)
+			unlock(&root.lock)
+			break
+		}
+		// Any semrelease after the cansemacquire knows we're waiting
+		// (we set nwait above), so go to sleep.
+		root.queue(addr, s)
+		goparkunlock(&root.lock, "semacquire")
+		if cansemacquire(addr) {
+			break
+		}
+	}
+	if s.releasetime > 0 {
+		blockevent(int64(s.releasetime)-t0, 3)
+	}
+	releaseSudog(s)
+}
+
+func semrelease(addr *uint32) {
+	root := semroot(addr)
+	xadd(addr, 1)
+
+	// Easy case: no waiters?
+	// This check must happen after the xadd, to avoid a missed wakeup
+	// (see loop in semacquire).
+	if atomicload(&root.nwait) == 0 {
+		return
+	}
+
+	// Harder case: search for a waiter and wake it.
+	lock(&root.lock)
+	if atomicload(&root.nwait) == 0 {
+		// The count is already consumed by another goroutine,
+		// so no need to wake up another goroutine.
+		unlock(&root.lock)
+		return
+	}
+	s := root.head
+	for ; s != nil; s = s.next {
+		if s.elem == unsafe.Pointer(addr) {
+			xadd(&root.nwait, -1)
+			root.dequeue(s)
+			break
+		}
+	}
+	unlock(&root.lock)
+	if s != nil {
+		if s.releasetime != 0 {
+			s.releasetime = cputicks()
+		}
+		goready(s.g)
+	}
+}
+
+func semroot(addr *uint32) *semaRoot {
+	return &semtable[(uintptr(unsafe.Pointer(addr))>>3)%semTabSize].root
+}
+
+func cansemacquire(addr *uint32) bool {
+	for {
+		v := atomicload(addr)
+		if v == 0 {
+			return false
+		}
+		if cas(addr, v, v-1) {
+			return true
+		}
+	}
+}
+
+func (root *semaRoot) queue(addr *uint32, s *sudog) {
+	s.g = getg()
+	s.elem = unsafe.Pointer(addr)
+	s.next = nil
+	s.prev = root.tail
+	if root.tail != nil {
+		root.tail.next = s
+	} else {
+		root.head = s
+	}
+	root.tail = s
+}
+
+func (root *semaRoot) dequeue(s *sudog) {
+	if s.next != nil {
+		s.next.prev = s.prev
+	} else {
+		root.tail = s.prev
+	}
+	if s.prev != nil {
+		s.prev.next = s.next
+	} else {
+		root.head = s.next
+	}
+	s.elem = nil
+	s.next = nil
+	s.prev = nil
+}
+
+// Synchronous semaphore for sync.Cond.
+type syncSema struct {
+	lock mutex
+	head *sudog
+	tail *sudog
+}
+
+// Syncsemacquire waits for a pairing syncsemrelease on the same semaphore s.
+func syncsemacquire(s *syncSema) {
+	lock(&s.lock)
+	if s.head != nil && s.head.nrelease > 0 {
+		// Have pending release, consume it.
+		var wake *sudog
+		s.head.nrelease--
+		if s.head.nrelease == 0 {
+			wake = s.head
+			s.head = wake.next
+			if s.head == nil {
+				s.tail = nil
+			}
+		}
+		unlock(&s.lock)
+		if wake != nil {
+			wake.next = nil
+			goready(wake.g)
+		}
+	} else {
+		// Enqueue itself.
+		w := acquireSudog()
+		w.g = getg()
+		w.nrelease = -1
+		w.next = nil
+		w.releasetime = 0
+		t0 := int64(0)
+		if blockprofilerate > 0 {
+			t0 = cputicks()
+			w.releasetime = -1
+		}
+		if s.tail == nil {
+			s.head = w
+		} else {
+			s.tail.next = w
+		}
+		s.tail = w
+		goparkunlock(&s.lock, "semacquire")
+		if t0 != 0 {
+			blockevent(int64(w.releasetime)-t0, 2)
+		}
+		releaseSudog(w)
+	}
+}
+
+// Syncsemrelease waits for n pairing syncsemacquire on the same semaphore s.
+func syncsemrelease(s *syncSema, n uint32) {
+	lock(&s.lock)
+	for n > 0 && s.head != nil && s.head.nrelease < 0 {
+		// Have pending acquire, satisfy it.
+		wake := s.head
+		s.head = wake.next
+		if s.head == nil {
+			s.tail = nil
+		}
+		if wake.releasetime != 0 {
+			wake.releasetime = cputicks()
+		}
+		wake.next = nil
+		goready(wake.g)
+		n--
+	}
+	if n > 0 {
+		// enqueue itself
+		w := acquireSudog()
+		w.g = getg()
+		w.nrelease = int32(n)
+		w.next = nil
+		w.releasetime = 0
+		if s.tail == nil {
+			s.head = w
+		} else {
+			s.tail.next = w
+		}
+		s.tail = w
+		goparkunlock(&s.lock, "semarelease")
+		releaseSudog(w)
+	} else {
+		unlock(&s.lock)
+	}
+}
+
+func syncsemcheck(sz uintptr) {
+	if sz != unsafe.Sizeof(syncSema{}) {
+		print("runtime: bad syncSema size - sync=", sz, " runtime=", unsafe.Sizeof(syncSema{}), "\n")
+		gothrow("bad syncSema size")
+	}
+}