sync/atomic: add Value

A Value provides an atomic load and store of a consistently typed value.
It's intended to be used with copy-on-write idiom (see the example).

Performance:
BenchmarkValueRead	50000000	        21.7 ns/op
BenchmarkValueRead-2	200000000	         8.63 ns/op
BenchmarkValueRead-4	300000000	         4.33 ns/op

TBR=rsc
R=golang-codereviews
CC=golang-codereviews
https://codereview.appspot.com/136710045

4 files changed, 325 insertions, 0 deletions

diff --git a/src/sync/atomic/norace.go b/src/sync/atomic/norace.go
new file mode 100644
index 000000000..1866fd16c
--- /dev/null
+++ b/src/sync/atomic/norace.go
@@ -0,0 +1,17 @@
+// Copyright 2014 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.
+
+// +build !race
+
+package atomic
+
+import "unsafe"
+
+const raceenabled = false
+
+func raceAcquire(addr unsafe.Pointer) {
+}
+
+func raceReleaseMerge(addr unsafe.Pointer) {
+}
diff --git a/src/sync/atomic/race.go b/src/sync/atomic/race.go
new file mode 100644
index 000000000..a833d9e7f
--- /dev/null
+++ b/src/sync/atomic/race.go
@@ -0,0 +1,22 @@
+// Copyright 2014 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.
+
+// +build race
+
+package atomic
+
+import (
+	"runtime"
+	"unsafe"
+)
+
+const raceenabled = true
+
+func raceAcquire(addr unsafe.Pointer) {
+	runtime.RaceAcquire(addr)
+}
+
+func raceReleaseMerge(addr unsafe.Pointer) {
+	runtime.RaceReleaseMerge(addr)
+}
diff --git a/src/sync/atomic/value.go b/src/sync/atomic/value.go
new file mode 100644
index 000000000..c290fdab8
--- /dev/null
+++ b/src/sync/atomic/value.go
@@ -0,0 +1,91 @@
+// Copyright 2014 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 atomic
+
+import (
+	"unsafe"
+)
+
+// A Value provides an atomic load and store of a consistently typed value.
+// Values can be created as part of other data structures.
+// The zero value for a Value returns nil from Load.
+// Once Store has been called, a Value must not be copied.
+type Value struct {
+	v interface{}
+}
+
+// ifaceWords is interface{} internal representation.
+type ifaceWords struct {
+	typ  unsafe.Pointer
+	data unsafe.Pointer
+}
+
+// Load returns the value set by the most recent Store.
+// It returns nil if there has been no call to Store for this Value.
+func (v *Value) Load() (x interface{}) {
+	vp := (*ifaceWords)(unsafe.Pointer(v))
+	typ := LoadPointer(&vp.typ)
+	if typ == nil || uintptr(typ) == ^uintptr(0) {
+		// First store not yet completed.
+		return nil
+	}
+	data := LoadPointer(&vp.data)
+	xp := (*ifaceWords)(unsafe.Pointer(&x))
+	xp.typ = typ
+	xp.data = data
+	if raceenabled {
+		raceAcquire(unsafe.Pointer(v))
+	}
+	return
+}
+
+// Store sets the value of the Value to v.
+// All calls to Store for a given Value must use values of the same concrete type.
+// Store of an inconsistent type panics, as does Store(nil).
+func (v *Value) Store(x interface{}) {
+	if x == nil {
+		panic("sync/atomic: store of nil value into Value")
+	}
+	if raceenabled {
+		raceReleaseMerge(unsafe.Pointer(v))
+	}
+	vp := (*ifaceWords)(unsafe.Pointer(v))
+	xp := (*ifaceWords)(unsafe.Pointer(&x))
+	for {
+		typ := LoadPointer(&vp.typ)
+		if typ == nil {
+			// Attempt to start first store.
+			// Disable preemption so that other goroutines can use
+			// active spin wait to wait for completion; and so that
+			// GC does not see the fake type accidentally.
+			runtime_procPin()
+			if !CompareAndSwapPointer(&vp.typ, nil, unsafe.Pointer(^uintptr(0))) {
+				runtime_procUnpin()
+				continue
+			}
+			// Complete first store.
+			StorePointer(&vp.data, xp.data)
+			StorePointer(&vp.typ, xp.typ)
+			runtime_procUnpin()
+			return
+		}
+		if uintptr(typ) == ^uintptr(0) {
+			// First store in progress. Wait.
+			// Since we disable preemption around the first store,
+			// we can wait with active spinning.
+			continue
+		}
+		// First store completed. Check type and overwrite data.
+		if typ != xp.typ {
+			panic("sync/atomic: store of inconsistently typed value into Value")
+		}
+		StorePointer(&vp.data, xp.data)
+		return
+	}
+}
+
+// Disable/enable preemption, implemented in runtime.
+func runtime_procPin()
+func runtime_procUnpin()
diff --git a/src/sync/atomic/value_test.go b/src/sync/atomic/value_test.go
new file mode 100644
index 000000000..382dc6854
--- /dev/null
+++ b/src/sync/atomic/value_test.go
@@ -0,0 +1,195 @@
+// Copyright 2014 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 atomic_test
+
+import (
+	"math/rand"
+	"runtime"
+	"sync"
+	. "sync/atomic"
+	"testing"
+	"time"
+)
+
+func TestValue(t *testing.T) {
+	var v Value
+	if v.Load() != nil {
+		t.Fatal("initial Value is not nil")
+	}
+	v.Store(42)
+	x := v.Load()
+	if xx, ok := x.(int); !ok || xx != 42 {
+		t.Fatalf("wrong value: got %+v, want 42", x)
+	}
+	v.Store(84)
+	x = v.Load()
+	if xx, ok := x.(int); !ok || xx != 84 {
+		t.Fatalf("wrong value: got %+v, want 84", x)
+	}
+}
+
+func TestValueLarge(t *testing.T) {
+	var v Value
+	v.Store("foo")
+	x := v.Load()
+	if xx, ok := x.(string); !ok || xx != "foo" {
+		t.Fatalf("wrong value: got %+v, want foo", x)
+	}
+	v.Store("barbaz")
+	x = v.Load()
+	if xx, ok := x.(string); !ok || xx != "barbaz" {
+		t.Fatalf("wrong value: got %+v, want barbaz", x)
+	}
+}
+
+func TestValuePanic(t *testing.T) {
+	const nilErr = "sync/atomic: store of nil value into Value"
+	const badErr = "sync/atomic: store of inconsistently typed value into Value"
+	var v Value
+	func() {
+		defer func() {
+			err := recover()
+			if err != nilErr {
+				t.Fatalf("inconsistent store panic: got '%v', want '%v'", err, nilErr)
+			}
+		}()
+		v.Store(nil)
+	}()
+	v.Store(42)
+	func() {
+		defer func() {
+			err := recover()
+			if err != badErr {
+				t.Fatalf("inconsistent store panic: got '%v', want '%v'", err, badErr)
+			}
+		}()
+		v.Store("foo")
+	}()
+	func() {
+		defer func() {
+			err := recover()
+			if err != nilErr {
+				t.Fatalf("inconsistent store panic: got '%v', want '%v'", err, nilErr)
+			}
+		}()
+		v.Store(nil)
+	}()
+}
+
+func TestValueConcurrent(t *testing.T) {
+	tests := [][]interface{}{
+		{uint16(0), ^uint16(0), uint16(1 + 2<<8), uint16(3 + 4<<8)},
+		{uint32(0), ^uint32(0), uint32(1 + 2<<16), uint32(3 + 4<<16)},
+		{uint64(0), ^uint64(0), uint64(1 + 2<<32), uint64(3 + 4<<32)},
+		{complex(0, 0), complex(1, 2), complex(3, 4), complex(5, 6)},
+	}
+	p := 4 * runtime.GOMAXPROCS(0)
+	for _, test := range tests {
+		var v Value
+		done := make(chan bool)
+		for i := 0; i < p; i++ {
+			go func() {
+				r := rand.New(rand.NewSource(rand.Int63()))
+			loop:
+				for j := 0; j < 1e5; j++ {
+					x := test[r.Intn(len(test))]
+					v.Store(x)
+					x = v.Load()
+					for _, x1 := range test {
+						if x == x1 {
+							continue loop
+						}
+					}
+					t.Logf("loaded unexpected value %+v, want %+v", x, test)
+					done <- false
+				}
+				done <- true
+			}()
+		}
+		for i := 0; i < p; i++ {
+			if !<-done {
+				t.FailNow()
+			}
+		}
+	}
+}
+
+func BenchmarkValueRead(b *testing.B) {
+	var v Value
+	v.Store(new(int))
+	b.RunParallel(func(pb *testing.PB) {
+		for pb.Next() {
+			x := v.Load().(*int)
+			if *x != 0 {
+				b.Fatalf("wrong value: got %v, want 0", *x)
+			}
+		}
+	})
+}
+
+// The following example shows how to use Value for periodic program config updates
+// and propagation of the changes to worker goroutines.
+func ExampleValue_config() {
+	var config Value // holds current server configuration
+	// Create initial config value and store into config.
+	config.Store(loadConfig())
+	go func() {
+		// Reload config every 10 seconds
+		// and update config value with the new version.
+		for {
+			time.Sleep(10 * time.Second)
+			config.Store(loadConfig())
+		}
+	}()
+	// Create worker goroutines that handle incoming requests
+	// using the latest config value.
+	for i := 0; i < 10; i++ {
+		go func() {
+			for r := range requests() {
+				c := config.Load()
+				// Handle request r using config c.
+				_, _ = r, c
+			}
+		}()
+	}
+}
+
+func loadConfig() map[string]string {
+	return make(map[string]string)
+}
+
+func requests() chan int {
+	return make(chan int)
+}
+
+// The following example shows how to maintain a scalable frequently read,
+// but infrequently updated data structure using copy-on-write idiom.
+func ExampleValue_readMostly() {
+	type Map map[string]string
+	var m Value
+	m.Store(make(Map))
+	var mu sync.Mutex // used only by writers
+	// read function can be used to read the data without further synchronization
+	read := func(key string) (val string) {
+		m1 := m.Load().(Map)
+		return m1[key]
+	}
+	// insert function can be used to update the data without further synchronization
+	insert := func(key, val string) {
+		mu.Lock() // synchronize with other potential writers
+		defer mu.Unlock()
+		m1 := m.Load().(Map) // load current value of the data structure
+		m2 := make(Map)      // create a new value
+		for k, v := range m1 {
+			m2[k] = v // copy all data from the current object to the new one
+		}
+		m2[key] = val // do the update that we need
+		m.Store(m2)   // atomically replace the current object with the new one
+		// At this point all new readers start working with the new version.
+		// The old version will be garbage collected once the existing readers
+		// (if any) are done with it.
+	}
+	_, _ = read, insert
+}