aboutsummaryrefslogtreecommitdiffstats
path: root/Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/cache/cache_test.go
diff options
context:
space:
mode:
Diffstat (limited to 'Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/cache/cache_test.go')
-rw-r--r--Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/cache/cache_test.go564
1 files changed, 441 insertions, 123 deletions
diff --git a/Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/cache/cache_test.go b/Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/cache/cache_test.go
index 07a9939b2..c2a50156f 100644
--- a/Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/cache/cache_test.go
+++ b/Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/cache/cache_test.go
@@ -8,17 +8,289 @@ package cache
import (
"math/rand"
+ "runtime"
+ "sync"
+ "sync/atomic"
"testing"
+ "time"
+ "unsafe"
)
-func set(ns Namespace, key uint64, value interface{}, charge int, fin func()) Object {
- obj, _ := ns.Get(key, func() (bool, interface{}, int, SetFin) {
- return true, value, charge, fin
+type int32o int32
+
+func (o *int32o) acquire() {
+ if atomic.AddInt32((*int32)(o), 1) != 1 {
+ panic("BUG: invalid ref")
+ }
+}
+
+func (o *int32o) Release() {
+ if atomic.AddInt32((*int32)(o), -1) != 0 {
+ panic("BUG: invalid ref")
+ }
+}
+
+type releaserFunc struct {
+ fn func()
+ value Value
+}
+
+func (r releaserFunc) Release() {
+ if r.fn != nil {
+ r.fn()
+ }
+}
+
+func set(c *Cache, ns, key uint64, value Value, charge int, relf func()) *Handle {
+ return c.Get(ns, key, func() (int, Value) {
+ if relf != nil {
+ return charge, releaserFunc{relf, value}
+ } else {
+ return charge, value
+ }
+ })
+}
+
+func TestCacheMap(t *testing.T) {
+ runtime.GOMAXPROCS(runtime.NumCPU())
+
+ nsx := []struct {
+ nobjects, nhandles, concurrent, repeat int
+ }{
+ {10000, 400, 50, 3},
+ {100000, 1000, 100, 10},
+ }
+
+ var (
+ objects [][]int32o
+ handles [][]unsafe.Pointer
+ )
+
+ for _, x := range nsx {
+ objects = append(objects, make([]int32o, x.nobjects))
+ handles = append(handles, make([]unsafe.Pointer, x.nhandles))
+ }
+
+ c := NewCache(nil)
+
+ wg := new(sync.WaitGroup)
+ var done int32
+
+ for ns, x := range nsx {
+ for i := 0; i < x.concurrent; i++ {
+ wg.Add(1)
+ go func(ns, i, repeat int, objects []int32o, handles []unsafe.Pointer) {
+ defer wg.Done()
+ r := rand.New(rand.NewSource(time.Now().UnixNano()))
+
+ for j := len(objects) * repeat; j >= 0; j-- {
+ key := uint64(r.Intn(len(objects)))
+ h := c.Get(uint64(ns), key, func() (int, Value) {
+ o := &objects[key]
+ o.acquire()
+ return 1, o
+ })
+ if v := h.Value().(*int32o); v != &objects[key] {
+ t.Fatalf("#%d invalid value: want=%p got=%p", ns, &objects[key], v)
+ }
+ if objects[key] != 1 {
+ t.Fatalf("#%d invalid object %d: %d", ns, key, objects[key])
+ }
+ if !atomic.CompareAndSwapPointer(&handles[r.Intn(len(handles))], nil, unsafe.Pointer(h)) {
+ h.Release()
+ }
+ }
+ }(ns, i, x.repeat, objects[ns], handles[ns])
+ }
+
+ go func(handles []unsafe.Pointer) {
+ r := rand.New(rand.NewSource(time.Now().UnixNano()))
+
+ for atomic.LoadInt32(&done) == 0 {
+ i := r.Intn(len(handles))
+ h := (*Handle)(atomic.LoadPointer(&handles[i]))
+ if h != nil && atomic.CompareAndSwapPointer(&handles[i], unsafe.Pointer(h), nil) {
+ h.Release()
+ }
+ time.Sleep(time.Millisecond)
+ }
+ }(handles[ns])
+ }
+
+ go func() {
+ handles := make([]*Handle, 100000)
+ for atomic.LoadInt32(&done) == 0 {
+ for i := range handles {
+ handles[i] = c.Get(999999999, uint64(i), func() (int, Value) {
+ return 1, 1
+ })
+ }
+ for _, h := range handles {
+ h.Release()
+ }
+ }
+ }()
+
+ wg.Wait()
+
+ atomic.StoreInt32(&done, 1)
+
+ for _, handles0 := range handles {
+ for i := range handles0 {
+ h := (*Handle)(atomic.LoadPointer(&handles0[i]))
+ if h != nil && atomic.CompareAndSwapPointer(&handles0[i], unsafe.Pointer(h), nil) {
+ h.Release()
+ }
+ }
+ }
+
+ for ns, objects0 := range objects {
+ for i, o := range objects0 {
+ if o != 0 {
+ t.Fatalf("invalid object #%d.%d: ref=%d", ns, i, o)
+ }
+ }
+ }
+}
+
+func TestCacheMap_NodesAndSize(t *testing.T) {
+ c := NewCache(nil)
+ if c.Nodes() != 0 {
+ t.Errorf("invalid nodes counter: want=%d got=%d", 0, c.Nodes())
+ }
+ if c.Size() != 0 {
+ t.Errorf("invalid size counter: want=%d got=%d", 0, c.Size())
+ }
+ set(c, 0, 1, 1, 1, nil)
+ set(c, 0, 2, 2, 2, nil)
+ set(c, 1, 1, 3, 3, nil)
+ set(c, 2, 1, 4, 1, nil)
+ if c.Nodes() != 4 {
+ t.Errorf("invalid nodes counter: want=%d got=%d", 4, c.Nodes())
+ }
+ if c.Size() != 7 {
+ t.Errorf("invalid size counter: want=%d got=%d", 4, c.Size())
+ }
+}
+
+func TestLRUCache_Capacity(t *testing.T) {
+ c := NewCache(NewLRU(10))
+ if c.Capacity() != 10 {
+ t.Errorf("invalid capacity: want=%d got=%d", 10, c.Capacity())
+ }
+ set(c, 0, 1, 1, 1, nil).Release()
+ set(c, 0, 2, 2, 2, nil).Release()
+ set(c, 1, 1, 3, 3, nil).Release()
+ set(c, 2, 1, 4, 1, nil).Release()
+ set(c, 2, 2, 5, 1, nil).Release()
+ set(c, 2, 3, 6, 1, nil).Release()
+ set(c, 2, 4, 7, 1, nil).Release()
+ set(c, 2, 5, 8, 1, nil).Release()
+ if c.Nodes() != 7 {
+ t.Errorf("invalid nodes counter: want=%d got=%d", 7, c.Nodes())
+ }
+ if c.Size() != 10 {
+ t.Errorf("invalid size counter: want=%d got=%d", 10, c.Size())
+ }
+ c.SetCapacity(9)
+ if c.Capacity() != 9 {
+ t.Errorf("invalid capacity: want=%d got=%d", 9, c.Capacity())
+ }
+ if c.Nodes() != 6 {
+ t.Errorf("invalid nodes counter: want=%d got=%d", 6, c.Nodes())
+ }
+ if c.Size() != 8 {
+ t.Errorf("invalid size counter: want=%d got=%d", 8, c.Size())
+ }
+}
+
+func TestCacheMap_NilValue(t *testing.T) {
+ c := NewCache(NewLRU(10))
+ h := c.Get(0, 0, func() (size int, value Value) {
+ return 1, nil
})
- return obj
+ if h != nil {
+ t.Error("cache handle is non-nil")
+ }
+ if c.Nodes() != 0 {
+ t.Errorf("invalid nodes counter: want=%d got=%d", 0, c.Nodes())
+ }
+ if c.Size() != 0 {
+ t.Errorf("invalid size counter: want=%d got=%d", 0, c.Size())
+ }
}
-func TestCache_HitMiss(t *testing.T) {
+func TestLRUCache_GetLatency(t *testing.T) {
+ runtime.GOMAXPROCS(runtime.NumCPU())
+
+ const (
+ concurrentSet = 30
+ concurrentGet = 3
+ duration = 3 * time.Second
+ delay = 3 * time.Millisecond
+ maxkey = 100000
+ )
+
+ var (
+ set, getHit, getAll int32
+ getMaxLatency, getDuration int64
+ )
+
+ c := NewCache(NewLRU(5000))
+ wg := &sync.WaitGroup{}
+ until := time.Now().Add(duration)
+ for i := 0; i < concurrentSet; i++ {
+ wg.Add(1)
+ go func(i int) {
+ defer wg.Done()
+ r := rand.New(rand.NewSource(time.Now().UnixNano()))
+ for time.Now().Before(until) {
+ c.Get(0, uint64(r.Intn(maxkey)), func() (int, Value) {
+ time.Sleep(delay)
+ atomic.AddInt32(&set, 1)
+ return 1, 1
+ }).Release()
+ }
+ }(i)
+ }
+ for i := 0; i < concurrentGet; i++ {
+ wg.Add(1)
+ go func(i int) {
+ defer wg.Done()
+ r := rand.New(rand.NewSource(time.Now().UnixNano()))
+ for {
+ mark := time.Now()
+ if mark.Before(until) {
+ h := c.Get(0, uint64(r.Intn(maxkey)), nil)
+ latency := int64(time.Now().Sub(mark))
+ m := atomic.LoadInt64(&getMaxLatency)
+ if latency > m {
+ atomic.CompareAndSwapInt64(&getMaxLatency, m, latency)
+ }
+ atomic.AddInt64(&getDuration, latency)
+ if h != nil {
+ atomic.AddInt32(&getHit, 1)
+ h.Release()
+ }
+ atomic.AddInt32(&getAll, 1)
+ } else {
+ break
+ }
+ }
+ }(i)
+ }
+
+ wg.Wait()
+ getAvglatency := time.Duration(getDuration) / time.Duration(getAll)
+ t.Logf("set=%d getHit=%d getAll=%d getMaxLatency=%v getAvgLatency=%v",
+ set, getHit, getAll, time.Duration(getMaxLatency), getAvglatency)
+
+ if getAvglatency > delay/3 {
+ t.Errorf("get avg latency > %v: got=%v", delay/3, getAvglatency)
+ }
+}
+
+func TestLRUCache_HitMiss(t *testing.T) {
cases := []struct {
key uint64
value string
@@ -36,36 +308,37 @@ func TestCache_HitMiss(t *testing.T) {
}
setfin := 0
- c := NewLRUCache(1000)
- ns := c.GetNamespace(0)
+ c := NewCache(NewLRU(1000))
for i, x := range cases {
- set(ns, x.key, x.value, len(x.value), func() {
+ set(c, 0, x.key, x.value, len(x.value), func() {
setfin++
}).Release()
for j, y := range cases {
- r, ok := ns.Get(y.key, nil)
+ h := c.Get(0, y.key, nil)
if j <= i {
// should hit
- if !ok {
+ if h == nil {
t.Errorf("case '%d' iteration '%d' is miss", i, j)
- } else if r.Value().(string) != y.value {
- t.Errorf("case '%d' iteration '%d' has invalid value got '%s', want '%s'", i, j, r.Value().(string), y.value)
+ } else {
+ if x := h.Value().(releaserFunc).value.(string); x != y.value {
+ t.Errorf("case '%d' iteration '%d' has invalid value got '%s', want '%s'", i, j, x, y.value)
+ }
}
} else {
// should miss
- if ok {
- t.Errorf("case '%d' iteration '%d' is hit , value '%s'", i, j, r.Value().(string))
+ if h != nil {
+ t.Errorf("case '%d' iteration '%d' is hit , value '%s'", i, j, h.Value().(releaserFunc).value.(string))
}
}
- if ok {
- r.Release()
+ if h != nil {
+ h.Release()
}
}
}
for i, x := range cases {
finalizerOk := false
- ns.Delete(x.key, func(exist bool) {
+ c.Delete(0, x.key, func() {
finalizerOk = true
})
@@ -74,22 +347,24 @@ func TestCache_HitMiss(t *testing.T) {
}
for j, y := range cases {
- r, ok := ns.Get(y.key, nil)
+ h := c.Get(0, y.key, nil)
if j > i {
// should hit
- if !ok {
+ if h == nil {
t.Errorf("case '%d' iteration '%d' is miss", i, j)
- } else if r.Value().(string) != y.value {
- t.Errorf("case '%d' iteration '%d' has invalid value got '%s', want '%s'", i, j, r.Value().(string), y.value)
+ } else {
+ if x := h.Value().(releaserFunc).value.(string); x != y.value {
+ t.Errorf("case '%d' iteration '%d' has invalid value got '%s', want '%s'", i, j, x, y.value)
+ }
}
} else {
// should miss
- if ok {
- t.Errorf("case '%d' iteration '%d' is hit, value '%s'", i, j, r.Value().(string))
+ if h != nil {
+ t.Errorf("case '%d' iteration '%d' is hit, value '%s'", i, j, h.Value().(releaserFunc).value.(string))
}
}
- if ok {
- r.Release()
+ if h != nil {
+ h.Release()
}
}
}
@@ -100,137 +375,180 @@ func TestCache_HitMiss(t *testing.T) {
}
func TestLRUCache_Eviction(t *testing.T) {
- c := NewLRUCache(12)
- ns := c.GetNamespace(0)
- o1 := set(ns, 1, 1, 1, nil)
- set(ns, 2, 2, 1, nil).Release()
- set(ns, 3, 3, 1, nil).Release()
- set(ns, 4, 4, 1, nil).Release()
- set(ns, 5, 5, 1, nil).Release()
- if r, ok := ns.Get(2, nil); ok { // 1,3,4,5,2
- r.Release()
- }
- set(ns, 9, 9, 10, nil).Release() // 5,2,9
-
- for _, x := range []uint64{9, 2, 5, 1} {
- r, ok := ns.Get(x, nil)
- if !ok {
- t.Errorf("miss for key '%d'", x)
+ c := NewCache(NewLRU(12))
+ o1 := set(c, 0, 1, 1, 1, nil)
+ set(c, 0, 2, 2, 1, nil).Release()
+ set(c, 0, 3, 3, 1, nil).Release()
+ set(c, 0, 4, 4, 1, nil).Release()
+ set(c, 0, 5, 5, 1, nil).Release()
+ if h := c.Get(0, 2, nil); h != nil { // 1,3,4,5,2
+ h.Release()
+ }
+ set(c, 0, 9, 9, 10, nil).Release() // 5,2,9
+
+ for _, key := range []uint64{9, 2, 5, 1} {
+ h := c.Get(0, key, nil)
+ if h == nil {
+ t.Errorf("miss for key '%d'", key)
} else {
- if r.Value().(int) != int(x) {
- t.Errorf("invalid value for key '%d' want '%d', got '%d'", x, x, r.Value().(int))
+ if x := h.Value().(int); x != int(key) {
+ t.Errorf("invalid value for key '%d' want '%d', got '%d'", key, key, x)
}
- r.Release()
+ h.Release()
}
}
o1.Release()
- for _, x := range []uint64{1, 2, 5} {
- r, ok := ns.Get(x, nil)
- if !ok {
- t.Errorf("miss for key '%d'", x)
+ for _, key := range []uint64{1, 2, 5} {
+ h := c.Get(0, key, nil)
+ if h == nil {
+ t.Errorf("miss for key '%d'", key)
} else {
- if r.Value().(int) != int(x) {
- t.Errorf("invalid value for key '%d' want '%d', got '%d'", x, x, r.Value().(int))
+ if x := h.Value().(int); x != int(key) {
+ t.Errorf("invalid value for key '%d' want '%d', got '%d'", key, key, x)
}
- r.Release()
+ h.Release()
}
}
- for _, x := range []uint64{3, 4, 9} {
- r, ok := ns.Get(x, nil)
- if ok {
- t.Errorf("hit for key '%d'", x)
- if r.Value().(int) != int(x) {
- t.Errorf("invalid value for key '%d' want '%d', got '%d'", x, x, r.Value().(int))
+ for _, key := range []uint64{3, 4, 9} {
+ h := c.Get(0, key, nil)
+ if h != nil {
+ t.Errorf("hit for key '%d'", key)
+ if x := h.Value().(int); x != int(key) {
+ t.Errorf("invalid value for key '%d' want '%d', got '%d'", key, key, x)
}
- r.Release()
+ h.Release()
}
}
}
-func TestLRUCache_SetGet(t *testing.T) {
- c := NewLRUCache(13)
- ns := c.GetNamespace(0)
- for i := 0; i < 200; i++ {
- n := uint64(rand.Intn(99999) % 20)
- set(ns, n, n, 1, nil).Release()
- if p, ok := ns.Get(n, nil); ok {
- if p.Value() == nil {
- t.Errorf("key '%d' contains nil value", n)
+func TestLRUCache_Evict(t *testing.T) {
+ c := NewCache(NewLRU(6))
+ set(c, 0, 1, 1, 1, nil).Release()
+ set(c, 0, 2, 2, 1, nil).Release()
+ set(c, 1, 1, 4, 1, nil).Release()
+ set(c, 1, 2, 5, 1, nil).Release()
+ set(c, 2, 1, 6, 1, nil).Release()
+ set(c, 2, 2, 7, 1, nil).Release()
+
+ for ns := 0; ns < 3; ns++ {
+ for key := 1; key < 3; key++ {
+ if h := c.Get(uint64(ns), uint64(key), nil); h != nil {
+ h.Release()
} else {
- got := p.Value().(uint64)
- if got != n {
- t.Errorf("invalid value for key '%d' want '%d', got '%d'", n, n, got)
- }
+ t.Errorf("Cache.Get on #%d.%d return nil", ns, key)
}
- p.Release()
- } else {
- t.Errorf("key '%d' doesn't exist", n)
}
}
-}
-func TestLRUCache_Purge(t *testing.T) {
- c := NewLRUCache(3)
- ns1 := c.GetNamespace(0)
- o1 := set(ns1, 1, 1, 1, nil)
- o2 := set(ns1, 2, 2, 1, nil)
- ns1.Purge(nil)
- set(ns1, 3, 3, 1, nil).Release()
- for _, x := range []uint64{1, 2, 3} {
- r, ok := ns1.Get(x, nil)
- if !ok {
- t.Errorf("miss for key '%d'", x)
- } else {
- if r.Value().(int) != int(x) {
- t.Errorf("invalid value for key '%d' want '%d', got '%d'", x, x, r.Value().(int))
+ if ok := c.Evict(0, 1); !ok {
+ t.Error("first Cache.Evict on #0.1 return false")
+ }
+ if ok := c.Evict(0, 1); ok {
+ t.Error("second Cache.Evict on #0.1 return true")
+ }
+ if h := c.Get(0, 1, nil); h != nil {
+ t.Errorf("Cache.Get on #0.1 return non-nil: %v", h.Value())
+ }
+
+ c.EvictNS(1)
+ if h := c.Get(1, 1, nil); h != nil {
+ t.Errorf("Cache.Get on #1.1 return non-nil: %v", h.Value())
+ }
+ if h := c.Get(1, 2, nil); h != nil {
+ t.Errorf("Cache.Get on #1.2 return non-nil: %v", h.Value())
+ }
+
+ c.EvictAll()
+ for ns := 0; ns < 3; ns++ {
+ for key := 1; key < 3; key++ {
+ if h := c.Get(uint64(ns), uint64(key), nil); h != nil {
+ t.Errorf("Cache.Get on #%d.%d return non-nil: %v", ns, key, h.Value())
}
- r.Release()
}
}
- o1.Release()
- o2.Release()
- for _, x := range []uint64{1, 2} {
- r, ok := ns1.Get(x, nil)
- if ok {
- t.Errorf("hit for key '%d'", x)
- if r.Value().(int) != int(x) {
- t.Errorf("invalid value for key '%d' want '%d', got '%d'", x, x, r.Value().(int))
- }
- r.Release()
+}
+
+func TestLRUCache_Delete(t *testing.T) {
+ delFuncCalled := 0
+ delFunc := func() {
+ delFuncCalled++
+ }
+
+ c := NewCache(NewLRU(2))
+ set(c, 0, 1, 1, 1, nil).Release()
+ set(c, 0, 2, 2, 1, nil).Release()
+
+ if ok := c.Delete(0, 1, delFunc); !ok {
+ t.Error("Cache.Delete on #1 return false")
+ }
+ if h := c.Get(0, 1, nil); h != nil {
+ t.Errorf("Cache.Get on #1 return non-nil: %v", h.Value())
+ }
+ if ok := c.Delete(0, 1, delFunc); ok {
+ t.Error("Cache.Delete on #1 return true")
+ }
+
+ h2 := c.Get(0, 2, nil)
+ if h2 == nil {
+ t.Error("Cache.Get on #2 return nil")
+ }
+ if ok := c.Delete(0, 2, delFunc); !ok {
+ t.Error("(1) Cache.Delete on #2 return false")
+ }
+ if ok := c.Delete(0, 2, delFunc); !ok {
+ t.Error("(2) Cache.Delete on #2 return false")
+ }
+
+ set(c, 0, 3, 3, 1, nil).Release()
+ set(c, 0, 4, 4, 1, nil).Release()
+ c.Get(0, 2, nil).Release()
+
+ for key := 2; key <= 4; key++ {
+ if h := c.Get(0, uint64(key), nil); h != nil {
+ h.Release()
+ } else {
+ t.Errorf("Cache.Get on #%d return nil", key)
}
}
-}
-func BenchmarkLRUCache_SetRelease(b *testing.B) {
- capacity := b.N / 100
- if capacity <= 0 {
- capacity = 10
+ h2.Release()
+ if h := c.Get(0, 2, nil); h != nil {
+ t.Errorf("Cache.Get on #2 return non-nil: %v", h.Value())
}
- c := NewLRUCache(capacity)
- ns := c.GetNamespace(0)
- b.ResetTimer()
- for i := uint64(0); i < uint64(b.N); i++ {
- set(ns, i, nil, 1, nil).Release()
+
+ if delFuncCalled != 4 {
+ t.Errorf("delFunc isn't called 4 times: got=%d", delFuncCalled)
}
}
-func BenchmarkLRUCache_SetReleaseTwice(b *testing.B) {
- capacity := b.N / 100
- if capacity <= 0 {
- capacity = 10
+func TestLRUCache_Close(t *testing.T) {
+ relFuncCalled := 0
+ relFunc := func() {
+ relFuncCalled++
+ }
+ delFuncCalled := 0
+ delFunc := func() {
+ delFuncCalled++
}
- c := NewLRUCache(capacity)
- ns := c.GetNamespace(0)
- b.ResetTimer()
- na := b.N / 2
- nb := b.N - na
+ c := NewCache(NewLRU(2))
+ set(c, 0, 1, 1, 1, relFunc).Release()
+ set(c, 0, 2, 2, 1, relFunc).Release()
- for i := uint64(0); i < uint64(na); i++ {
- set(ns, i, nil, 1, nil).Release()
+ h3 := set(c, 0, 3, 3, 1, relFunc)
+ if h3 == nil {
+ t.Error("Cache.Get on #3 return nil")
}
+ if ok := c.Delete(0, 3, delFunc); !ok {
+ t.Error("Cache.Delete on #3 return false")
+ }
+
+ c.Close()
- for i := uint64(0); i < uint64(nb); i++ {
- set(ns, i, nil, 1, nil).Release()
+ if relFuncCalled != 3 {
+ t.Errorf("relFunc isn't called 3 times: got=%d", relFuncCalled)
+ }
+ if delFuncCalled != 1 {
+ t.Errorf("delFunc isn't called 1 times: got=%d", delFuncCalled)
}
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-09-13 07:57:40 +0800