<|start_filename|>lock_test.go<|end_filename|>
package stm

import "testing"

const (
	minVersion = 0
	midVersion = 1 << 32
)

func helperEncode(locked bool, version uint64) (lock *versionedLock) {
	new := (versionedLock)(encode(locked, version))
	return &new
}

func helperDecode(lock *versionedLock) (locked bool, version uint64) {
	return decode((uint64)(*lock))
}

func TestTryLock(t *testing.T) {
	cases := []struct {
		locked  bool
		version uint64
	}{
		{false, minVersion},
		{false, midVersion},
		{true, minVersion},
		{true, midVersion},
	}

	for _, tc := range cases {
		lock := helperEncode(tc.locked, tc.version)

		ok := lock.tryLock()
		if ok == tc.locked {
			t.Errorf("got: ok = %v, want: ok = %v", ok, !ok)
		}

		locked, version := helperDecode(lock)
		if locked != true || version != tc.version {
			t.Errorf("got: (%v, %v) want: (%v, %v)", locked, version, true, tc.version)
		}
	}
}

func TestUnlock(t *testing.T) {
	cases := []struct {
		locked  bool
		version uint64
	}{
		{true, minVersion},
		{true, midVersion},
	}

	for _, tc := range cases {
		lock := helperEncode(tc.locked, tc.version)
		lock.unlock()

		locked, version := helperDecode(lock)
		if locked != false || version != tc.version {
			t.Errorf("got: (%v, %v) want: (%v, %v)", locked, version, false, tc.version)
		}
	}
}

func TestUnlockAndUpdate(t *testing.T) {
	cases := []struct {
		locked  bool
		version uint64
		input   uint64
	}{
		{true, minVersion, minVersion + 1},
		{true, midVersion, midVersion + 1},
	}

	for _, tc := range cases {
		lock := helperEncode(tc.locked, tc.version)
		lock.unlockAndUpdate(tc.input)

		locked, version := helperDecode(lock)
		if locked != false || version != tc.input {
			t.Errorf("got: (%v, %v) want: (%v, %v)", locked, version, false, tc.input)
		}
	}
}


<|start_filename|>benchmark/bench_test.go<|end_filename|>
package bench

import (
	"sync"
	"sync/atomic"
	"testing"

	de "github.com/decillion/go-stm"
	lu "github.com/lukechampine/stm"
)

func Benchmark_Read100_RWMutex(b *testing.B) {
	var x, y int
	mu := &sync.RWMutex{}
	b.ResetTimer()

	b.RunParallel(func(pb *testing.PB) {
		for pb.Next() {
			mu.RLock()
			_ = x
			_ = y
			mu.RUnlock()
		}
	})
}
func Benchmark_Read100_decillion(b *testing.B) {
	x := de.New(0)
	y := de.New(0)

	load := func(rec *de.TRec) interface{} {
		rec.Load(x)
		rec.Load(y)
		return nil
	}
	b.ResetTimer()

	b.RunParallel(func(pb *testing.PB) {
		for pb.Next() {
			de.Atomically(load)
		}
	})
}

func Benchmark_Read100_lukechampine(b *testing.B) {
	x := lu.NewVar(0)
	y := lu.NewVar(0)

	load := func(tx *lu.Tx) {
		tx.Get(x)
		tx.Get(y)
	}
	b.ResetTimer()

	b.RunParallel(func(pb *testing.PB) {
		for pb.Next() {
			lu.Atomically(load)
		}
	})
}

func Benchmark_Read90Write10_RWMutex(b *testing.B) {
	var x, y int
	mu := &sync.RWMutex{}
	b.ResetTimer()

	var counter uint64
	b.RunParallel(func(pb *testing.PB) {
		for pb.Next() {
			id := atomic.AddUint64(&counter, 1)
			if id%10 == 0 {
				mu.Lock()
				x++
				y++
				mu.Unlock()
			} else {
				mu.RLock()
				_ = x
				_ = y
				mu.RUnlock()
			}
		}
	})
}

func Benchmark_Read90Write10_decillion(b *testing.B) {
	x := de.New(0)
	y := de.New(0)

	inc := func(rec *de.TRec) interface{} {
		rec.Store(x, rec.Load(x).(int)+1)
		rec.Store(y, rec.Load(y).(int)+1)
		return nil
	}
	load := func(rec *de.TRec) interface{} {
		rec.Load(x)
		rec.Load(y)
		return nil
	}
	b.ResetTimer()

	var counter uint64
	b.RunParallel(func(pb *testing.PB) {
		for pb.Next() {
			id := atomic.AddUint64(&counter, 1)
			if id%10 == 0 {
				de.Atomically(inc)
			} else {
				de.Atomically(load)
			}
		}
	})
}

func Benchmark_Read90Write10_lukechampine(b *testing.B) {
	x := lu.NewVar(0)
	y := lu.NewVar(0)

	inc := func(tx *lu.Tx) {
		tx.Set(x, tx.Get(x).(int)+1)
		tx.Set(y, tx.Get(y).(int)+1)
	}
	load := func(tx *lu.Tx) {
		tx.Get(x)
		tx.Get(y)
	}
	b.ResetTimer()

	var counter uint64
	b.RunParallel(func(pb *testing.PB) {
		for pb.Next() {
			id := atomic.AddUint64(&counter, 1)
			if id%10 == 0 {
				lu.Atomically(inc)
			} else {
				lu.Atomically(load)
			}
		}
	})
}


<|start_filename|>tran.go<|end_filename|>
// Package stm is a software transactional memory implementation for Go, which
// is based on the Transactional Locking II (TL2) proposed by Dice et al.
// https://doi.org/10.1007/11864219_14
package stm

import "sync/atomic"

type clock uint64

func (c *clock) incAndFetch() (t uint64) {
	return atomic.AddUint64((*uint64)(c), 1)
}

func (c *clock) sampleClock() (t uint64) {
	return atomic.LoadUint64((*uint64)(c))
}

var globalClock clock

// TVar is a transactional variable.
type TVar struct {
	lock  versionedLock
	value atomic.Value
}

// New creates a transactional variable and initialize it by the given value v.
func New(v interface{}) (x *TVar) {
	x = &TVar{}
	x.value.Store(v)
	return x
}

// TRec is an auxiliary data type for recording meta data of a transaction.
type TRec struct {
	aborted      bool
	readVersion  uint64
	writeVersion uint64
	readSet      map[*TVar]struct{}
	writeSet     map[*TVar]interface{}
}

// Load returns the value of the transactional variable x.
func (rec *TRec) Load(x *TVar) (v interface{}) {
	if v, ok := rec.writeSet[x]; ok {
		return v // No validation
	}
	if rec.readSet == nil {
		rec.readSet = make(map[*TVar]struct{})
	}
	rec.readSet[x] = struct{}{}
	_, pre := x.lock.sampleLock()
	v = x.value.Load()
	locked, post := x.lock.sampleLock()
	if locked || pre != post || post > rec.readVersion {
		rec.aborted = true
	}
	return v
}

// Store sets the value of the transactional variable x to the given value v.
func (rec *TRec) Store(x *TVar, v interface{}) {
	if rec.writeSet == nil {
		rec.writeSet = make(map[*TVar]interface{})
	}
	rec.writeSet[x] = v
}

// Atomically executes the given transaction tx atomically. The transaction tx
// should not contain operations with side effects apart from Store and operations
// to variables declared in tx. The return value of Atomically is the very value
// returned by tx.
func Atomically(tx func(rec *TRec) interface{}) interface{} {
RETRY:

	rec := &TRec{
		readVersion: globalClock.sampleClock(),
	}

	v := tx(rec) // speculative execution
	if rec.aborted {
		goto RETRY
	}

	if len(rec.writeSet) == 0 {
		return v // A fast path for read-only transaction
	}

	lockedSet := make(map[*TVar]struct{})
	for x := range rec.writeSet {
		if !x.lock.tryLock() {
			for x := range lockedSet {
				x.lock.unlock()
			}
			goto RETRY
		}
		lockedSet[x] = struct{}{}
	}

	rec.writeVersion = globalClock.incAndFetch()

	// Validate the elements of the read-set.
	if rec.writeVersion != rec.readVersion+1 {
		for x := range rec.readSet {
			locked, version := x.lock.sampleLock()
			_, lockedByMe := lockedSet[x]
			if (!lockedByMe && locked) || version > rec.readVersion {
				for y := range lockedSet {
					y.lock.unlock()
				}
				goto RETRY
			}
		}
	}

	for x, val := range rec.writeSet {
		x.value.Store(val)
		x.lock.unlockAndUpdate(rec.writeVersion)
	}
	return v
}


<|start_filename|>tran_test.go<|end_filename|>
package stm

import (
	"fmt"
	"sync"
	"testing"
)

func Example() {
	// There are two bank accounts of Alice and Bob.
	accountA := New(100)
	accountB := New(0)

	// Transfer 20 from Alice's account to Bob's one.
	transfer := func(rec *TRec) interface{} {
		currA := rec.Load(accountA).(int)
		currB := rec.Load(accountB).(int)
		rec.Store(accountA, currA-20)
		rec.Store(accountB, currB+20)
		return nil
	}
	Atomically(transfer)

	// Check the balance of accounts of Alice and Bob.
	inquiries := func(rec *TRec) interface{} {
		balance := make(map[*TVar]int)
		balance[accountA] = rec.Load(accountA).(int)
		balance[accountB] = rec.Load(accountB).(int)
		return balance
	}
	balance := Atomically(inquiries).(map[*TVar]int)

	fmt.Printf("The account of Alice holds %v.\nThe account of Bob holds %v.",
		balance[accountA], balance[accountB])
	// Output:
	// The account of Alice holds 80.
	// The account of Bob holds 20.
}

func TestIncrement(t *testing.T) {
	iter := 10000

	x := New(0)
	y := New(0)

	inc := func(rec *TRec) interface{} {
		rec.Store(x, rec.Load(x).(int)+1)
		rec.Store(y, rec.Load(y).(int)+1)
		return nil
	}

	read := func(rec *TRec) interface{} {
		var curr [2]int
		curr[0] = rec.Load(x).(int)
		curr[1] = rec.Load(y).(int)
		return curr
	}

	wg := sync.WaitGroup{}

	for i := 0; i < 2*iter; i++ {
		wg.Add(1)
		j := i
		go func() {
			if j%2 == 0 {
				Atomically(inc)
			} else {
				Atomically(read)
			}
			wg.Done()
		}()
	}

	wg.Wait()

	curr := Atomically(read).([2]int)
	currX, currY := curr[0], curr[1]

	if currX != iter || currY != iter {
		t.Errorf("want: (x, y) = (%v, %v) got: (x, y) = (%v, %v)",
			iter, iter, currX, currY)
	}
}


<|start_filename|>lock.go<|end_filename|>
package stm

import "sync/atomic"

// versionedLock virtually maintains two fields, a lock bit and a version
// number. The first bit of uint64 is used to hold the lock bit and the rest
// is used to hold the version number. The zero value of versionedLock is
// (locked, version) = (false, 0).
type versionedLock uint64

func encode(locked bool, version uint64) (encoded uint64) {
	if (version >> 63) == 1 {
		panic("stm: version number exceeds 2^63-1.")
	}
	if locked {
		return (1 << 63) | version
	}
	return version
}

func decode(encoded uint64) (locked bool, version uint64) {
	if (encoded >> 63) == 1 {
		locked = true
	}
	version = (1<<63 - 1) & encoded
	return
}

func (lock *versionedLock) sampleLock() (locked bool, version uint64) {
	return decode(atomic.LoadUint64((*uint64)(lock)))
}

func (lock *versionedLock) tryLock() (ok bool) {
	old := atomic.LoadUint64((*uint64)(lock))
	locked, version := decode(old)
	if locked {
		return false
	}
	new := encode(true, version)
	return atomic.CompareAndSwapUint64((*uint64)(lock), old, new)
}

func (lock *versionedLock) unlock() {
	locked, version := lock.sampleLock()
	if !locked {
		panic("stm: unlock of unlocked versioned-lock.")
	}
	new := encode(false, version)
	atomic.StoreUint64((*uint64)(lock), new)
}

func (lock *versionedLock) unlockAndUpdate(version uint64) {
	locked, _ := lock.sampleLock()
	if !locked {
		panic("stm: unlock of unlocked versioned-lock.")
	}
	new := encode(false, version)
	atomic.StoreUint64((*uint64)(lock), new)
}
