8 files changed, 437 insertions, 0 deletions
diff --git a/libgo/go/sync/cas.c b/libgo/go/sync/cas.c
new file mode 100644
index 000000000..ffcd133cb
--- /dev/null
+++ b/libgo/go/sync/cas.c
@@ -0,0 +1,15 @@
+/* cas.c -- implement sync.cas for Go.
+
+   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.  */
+
+#include <stdint.h>
+
+_Bool cas (int32_t *, int32_t, int32_t) asm ("libgo_sync.sync.cas");
+
+_Bool
+cas (int32_t *ptr, int32_t old, int32_t new)
+{
+  return __sync_bool_compare_and_swap (ptr, old, new);
+}
diff --git a/libgo/go/sync/mutex.go b/libgo/go/sync/mutex.go
new file mode 100644
index 000000000..9a2bb2bb4
--- /dev/null
+++ b/libgo/go/sync/mutex.go
@@ -0,0 +1,61 @@
+// 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.
+
+// The sync package provides basic synchronization primitives
+// such as mutual exclusion locks.  Other than the Once type,
+// most are intended for use by low-level library routines.
+// Higher-level synchronization  is better done via channels
+// and communication.
+package sync
+
+import "runtime"
+
+func cas(val *uint32, old, new uint32) bool
+
+// A Mutex is a mutual exclusion lock.
+// Mutexes can be created as part of other structures;
+// the zero value for a Mutex is an unlocked mutex.
+type Mutex struct {
+	key  uint32
+	sema uint32
+}
+
+// Add delta to *val, and return the new *val in a thread-safe way. If multiple
+// goroutines call xadd on the same val concurrently, the changes will be
+// serialized, and all the deltas will be added in an undefined order.
+func xadd(val *uint32, delta int32) (new uint32) {
+	for {
+		v := *val
+		nv := v + uint32(delta)
+		if cas(val, v, nv) {
+			return nv
+		}
+	}
+	panic("unreached")
+}
+
+// Lock locks m.
+// If the lock is already in use, the calling goroutine
+// blocks until the mutex is available.
+func (m *Mutex) Lock() {
+	if xadd(&m.key, 1) == 1 {
+		// changed from 0 to 1; we hold lock
+		return
+	}
+	runtime.Semacquire(&m.sema)
+}
+
+// Unlock unlocks m.
+// It is a run-time error if m is not locked on entry to Unlock.
+//
+// A locked Mutex is not associated with a particular goroutine.
+// It is allowed for one goroutine to lock a Mutex and then
+// arrange for another goroutine to unlock it.
+func (m *Mutex) Unlock() {
+	if xadd(&m.key, -1) == 0 {
+		// changed from 1 to 0; no contention
+		return
+	}
+	runtime.Semrelease(&m.sema)
+}
diff --git a/libgo/go/sync/mutex_test.go b/libgo/go/sync/mutex_test.go
new file mode 100644
index 000000000..d0e048ed7
--- /dev/null
+++ b/libgo/go/sync/mutex_test.go
@@ -0,0 +1,91 @@
+// 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.
+
+// GOMAXPROCS=10 gotest
+
+package sync_test
+
+import (
+	"runtime"
+	. "sync"
+	"testing"
+)
+
+func HammerSemaphore(s *uint32, loops int, cdone chan bool) {
+	for i := 0; i < loops; i++ {
+		runtime.Semacquire(s)
+		runtime.Semrelease(s)
+	}
+	cdone <- true
+}
+
+func TestSemaphore(t *testing.T) {
+	s := new(uint32)
+	*s = 1
+	c := make(chan bool)
+	for i := 0; i < 10; i++ {
+		go HammerSemaphore(s, 1000, c)
+	}
+	for i := 0; i < 10; i++ {
+		<-c
+	}
+}
+
+func BenchmarkUncontendedSemaphore(b *testing.B) {
+	s := new(uint32)
+	*s = 1
+	HammerSemaphore(s, b.N, make(chan bool, 2))
+}
+
+func BenchmarkContendedSemaphore(b *testing.B) {
+	b.StopTimer()
+	s := new(uint32)
+	*s = 1
+	c := make(chan bool)
+	runtime.GOMAXPROCS(2)
+	b.StartTimer()
+
+	go HammerSemaphore(s, b.N/2, c)
+	go HammerSemaphore(s, b.N/2, c)
+	<-c
+	<-c
+}
+
+
+func HammerMutex(m *Mutex, loops int, cdone chan bool) {
+	for i := 0; i < loops; i++ {
+		m.Lock()
+		m.Unlock()
+	}
+	cdone <- true
+}
+
+func TestMutex(t *testing.T) {
+	m := new(Mutex)
+	c := make(chan bool)
+	for i := 0; i < 10; i++ {
+		go HammerMutex(m, 1000, c)
+	}
+	for i := 0; i < 10; i++ {
+		<-c
+	}
+}
+
+func BenchmarkUncontendedMutex(b *testing.B) {
+	m := new(Mutex)
+	HammerMutex(m, b.N, make(chan bool, 2))
+}
+
+func BenchmarkContendedMutex(b *testing.B) {
+	b.StopTimer()
+	m := new(Mutex)
+	c := make(chan bool)
+	runtime.GOMAXPROCS(2)
+	b.StartTimer()
+
+	go HammerMutex(m, b.N/2, c)
+	go HammerMutex(m, b.N/2, c)
+	<-c
+	<-c
+}
diff --git a/libgo/go/sync/once.go b/libgo/go/sync/once.go
new file mode 100644
index 000000000..8c877cdec
--- /dev/null
+++ b/libgo/go/sync/once.go
@@ -0,0 +1,35 @@
+// 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.
+
+package sync
+
+// Once is an object that will perform exactly one action.
+type Once struct {
+	m    Mutex
+	done bool
+}
+
+// Do calls the function f if and only if the method is being called for the
+// first time with this receiver.  In other words, given
+// 	var once Once
+// if Do(f) is called multiple times, only the first call will invoke f,
+// even if f has a different value in each invocation.  A new instance of
+// Once is required for each function to execute.
+//
+// Do is intended for initialization that must be run exactly once.  Since f
+// is niladic, it may be necessary to use a function literal to capture the
+// arguments to a function to be invoked by Do:
+// 	config.once.Do(func() { config.init(filename) })
+//
+// Because no call to Do returns until the one call to f returns, if f causes
+// Do to be called, it will deadlock.
+//
+func (o *Once) Do(f func()) {
+	o.m.Lock()
+	defer o.m.Unlock()
+	if !o.done {
+		o.done = true
+		f()
+	}
+}
diff --git a/libgo/go/sync/once_test.go b/libgo/go/sync/once_test.go
new file mode 100644
index 000000000..155954a49
--- /dev/null
+++ b/libgo/go/sync/once_test.go
@@ -0,0 +1,37 @@
+// 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.
+
+package sync_test
+
+import (
+	. "sync"
+	"testing"
+)
+
+type one int
+
+func (o *one) Increment() {
+	*o++
+}
+
+func run(once *Once, o *one, c chan bool) {
+	once.Do(func() { o.Increment() })
+	c <- true
+}
+
+func TestOnce(t *testing.T) {
+	o := new(one)
+	once := new(Once)
+	c := make(chan bool)
+	const N = 10
+	for i := 0; i < N; i++ {
+		go run(once, o, c)
+	}
+	for i := 0; i < N; i++ {
+		<-c
+	}
+	if *o != 1 {
+		t.Errorf("once failed: %d is not 1", *o)
+	}
+}
diff --git a/libgo/go/sync/rwmutex.go b/libgo/go/sync/rwmutex.go
new file mode 100644
index 000000000..06fd0b0ff
--- /dev/null
+++ b/libgo/go/sync/rwmutex.go
@@ -0,0 +1,75 @@
+// 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.
+
+package sync
+
+// An RWMutex is a reader/writer mutual exclusion lock.
+// The lock can be held by an arbitrary number of readers
+// or a single writer.
+// RWMutexes can be created as part of other
+// structures; the zero value for a RWMutex is
+// an unlocked mutex.
+//
+// Writers take priority over Readers: no new RLocks
+// are granted while a blocked Lock call is waiting.
+type RWMutex struct {
+	w           Mutex  // held if there are pending readers or writers
+	r           Mutex  // held if the w is being rd
+	readerCount uint32 // number of pending readers
+}
+
+// RLock locks rw for reading.
+// If the lock is already locked for writing or there is a writer already waiting
+// to release the lock, RLock blocks until the writer has released the lock.
+func (rw *RWMutex) RLock() {
+	// Use rw.r.Lock() to block granting the RLock if a goroutine
+	// is waiting for its Lock. This is the prevent starvation of W in
+	// this situation:
+	//   A: rw.RLock()  // granted
+	//   W: rw.Lock()   // waiting for rw.w().Lock()
+	//   B: rw.RLock()  // granted
+	//   C: rw.RLock()  // granted
+	//   B: rw.RUnlock()
+	//   ... (new readers come and go indefinitely, W is starving)
+	rw.r.Lock()
+	if xadd(&rw.readerCount, 1) == 1 {
+		// The first reader locks rw.w, so writers will be blocked
+		// while the readers have the RLock.
+		rw.w.Lock()
+	}
+	rw.r.Unlock()
+}
+
+// RUnlock undoes a single RLock call;
+// it does not affect other simultaneous readers.
+// It is a run-time error if rw is not locked for reading
+// on entry to RUnlock.
+func (rw *RWMutex) RUnlock() {
+	if xadd(&rw.readerCount, -1) == 0 {
+		// last reader finished, enable writers
+		rw.w.Unlock()
+	}
+}
+
+// Lock locks rw for writing.
+// If the lock is already locked for reading or writing,
+// Lock blocks until the lock is available.
+// To ensure that the lock eventually becomes available,
+// a blocked Lock call excludes new readers from acquiring
+// the lock.
+func (rw *RWMutex) Lock() {
+	rw.r.Lock()
+	rw.w.Lock()
+	rw.r.Unlock()
+}
+
+// Unlock unlocks rw for writing.
+// It is a run-time error if rw is not locked for writing
+// on entry to Unlock.
+//
+// Like for Mutexes,
+// a locked RWMutex is not associated with a particular goroutine.
+// It is allowed for one goroutine to RLock (Lock) an RWMutex and then
+// arrange for another goroutine to RUnlock (Unlock) it.
+func (rw *RWMutex) Unlock() { rw.w.Unlock() }
diff --git a/libgo/go/sync/rwmutex_test.go b/libgo/go/sync/rwmutex_test.go
new file mode 100644
index 000000000..111bca1e3
--- /dev/null
+++ b/libgo/go/sync/rwmutex_test.go
@@ -0,0 +1,114 @@
+// 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.
+
+// GOMAXPROCS=10 gotest
+
+package sync_test
+
+import (
+	"fmt"
+	"runtime"
+	. "sync"
+	"testing"
+)
+
+func parallelReader(m *RWMutex, clocked, cunlock, cdone chan bool) {
+	m.RLock()
+	clocked <- true
+	<-cunlock
+	m.RUnlock()
+	cdone <- true
+}
+
+func doTestParallelReaders(numReaders, gomaxprocs int) {
+	runtime.GOMAXPROCS(gomaxprocs)
+	var m RWMutex
+	clocked := make(chan bool)
+	cunlock := make(chan bool)
+	cdone := make(chan bool)
+	for i := 0; i < numReaders; i++ {
+		go parallelReader(&m, clocked, cunlock, cdone)
+	}
+	// Wait for all parallel RLock()s to succeed.
+	for i := 0; i < numReaders; i++ {
+		<-clocked
+	}
+	for i := 0; i < numReaders; i++ {
+		cunlock <- true
+	}
+	// Wait for the goroutines to finish.
+	for i := 0; i < numReaders; i++ {
+		<-cdone
+	}
+}
+
+func TestParallelReaders(t *testing.T) {
+	doTestParallelReaders(1, 4)
+	doTestParallelReaders(3, 4)
+	doTestParallelReaders(4, 2)
+}
+
+func reader(rwm *RWMutex, num_iterations int, activity *uint32, cdone chan bool) {
+	for i := 0; i < num_iterations; i++ {
+		rwm.RLock()
+		n := Xadd(activity, 1)
+		if n < 1 || n >= 10000 {
+			panic(fmt.Sprintf("wlock(%d)\n", n))
+		}
+		for i := 0; i < 100; i++ {
+		}
+		Xadd(activity, -1)
+		rwm.RUnlock()
+	}
+	cdone <- true
+}
+
+func writer(rwm *RWMutex, num_iterations int, activity *uint32, cdone chan bool) {
+	for i := 0; i < num_iterations; i++ {
+		rwm.Lock()
+		n := Xadd(activity, 10000)
+		if n != 10000 {
+			panic(fmt.Sprintf("wlock(%d)\n", n))
+		}
+		for i := 0; i < 100; i++ {
+		}
+		Xadd(activity, -10000)
+		rwm.Unlock()
+	}
+	cdone <- true
+}
+
+func HammerRWMutex(gomaxprocs, numReaders, num_iterations int) {
+	runtime.GOMAXPROCS(gomaxprocs)
+	// Number of active readers + 10000 * number of active writers.
+	var activity uint32
+	var rwm RWMutex
+	cdone := make(chan bool)
+	go writer(&rwm, num_iterations, &activity, cdone)
+	var i int
+	for i = 0; i < numReaders/2; i++ {
+		go reader(&rwm, num_iterations, &activity, cdone)
+	}
+	go writer(&rwm, num_iterations, &activity, cdone)
+	for ; i < numReaders; i++ {
+		go reader(&rwm, num_iterations, &activity, cdone)
+	}
+	// Wait for the 2 writers and all readers to finish.
+	for i := 0; i < 2+numReaders; i++ {
+		<-cdone
+	}
+}
+
+func TestRWMutex(t *testing.T) {
+	HammerRWMutex(1, 1, 1000)
+	HammerRWMutex(1, 3, 1000)
+	HammerRWMutex(1, 10, 1000)
+	HammerRWMutex(4, 1, 1000)
+	HammerRWMutex(4, 3, 1000)
+	HammerRWMutex(4, 10, 1000)
+	HammerRWMutex(10, 1, 1000)
+	HammerRWMutex(10, 3, 1000)
+	HammerRWMutex(10, 10, 1000)
+	HammerRWMutex(10, 5, 10000)
+}
diff --git a/libgo/go/sync/xadd_test.go b/libgo/go/sync/xadd_test.go
new file mode 100644
index 000000000..8b2ef76e6
--- /dev/null
+++ b/libgo/go/sync/xadd_test.go
@@ -0,0 +1,9 @@
+// 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.
+
+package sync
+
+func Xadd(val *uint32, delta int32) (new uint32) {
+	return xadd(val, delta)
+}