From 554fd8c5195424bdbcabf5de30fdc183aba391bd Mon Sep 17 00:00:00 2001 From: upstream source tree Date: Sun, 15 Mar 2015 20:14:05 -0400 Subject: obtained gcc-4.6.4.tar.bz2 from upstream website; verified gcc-4.6.4.tar.bz2.sig; imported gcc-4.6.4 source tree from verified upstream tarball. downloading a git-generated archive based on the 'upstream' tag should provide you with a source tree that is binary identical to the one extracted from the above tarball. if you have obtained the source via the command 'git clone', however, do note that line-endings of files in your working directory might differ from line-endings of the respective files in the upstream repository. --- libgo/go/sync/cas.c | 15 ++++++ libgo/go/sync/mutex.go | 61 ++++++++++++++++++++++ libgo/go/sync/mutex_test.go | 91 +++++++++++++++++++++++++++++++++ libgo/go/sync/once.go | 35 +++++++++++++ libgo/go/sync/once_test.go | 37 ++++++++++++++ libgo/go/sync/rwmutex.go | 75 +++++++++++++++++++++++++++ libgo/go/sync/rwmutex_test.go | 114 ++++++++++++++++++++++++++++++++++++++++++ libgo/go/sync/xadd_test.go | 9 ++++ 8 files changed, 437 insertions(+) create mode 100644 libgo/go/sync/cas.c create mode 100644 libgo/go/sync/mutex.go create mode 100644 libgo/go/sync/mutex_test.go create mode 100644 libgo/go/sync/once.go create mode 100644 libgo/go/sync/once_test.go create mode 100644 libgo/go/sync/rwmutex.go create mode 100644 libgo/go/sync/rwmutex_test.go create mode 100644 libgo/go/sync/xadd_test.go (limited to 'libgo/go/sync') 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 + +_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) +} -- cgit v1.2.3