+++ /dev/null
-// Copyright (c) 2012, Suryandaru Triandana <syndtr@gmail.com>
-// All rights reserved.
-//
-// Use of this source code is governed by a BSD-style license that can be
-// found in the LICENSE file.
-
-package cache
-
-import (
- "math/rand"
- "runtime"
- "sync"
- "sync/atomic"
- "testing"
- "time"
- "unsafe"
-)
-
-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}
- }
- return charge, value
- })
-}
-
-type cacheMapTestParams struct {
- nobjects, nhandles, concurrent, repeat int
-}
-
-func TestCacheMap(t *testing.T) {
- runtime.GOMAXPROCS(runtime.NumCPU())
-
- var params []cacheMapTestParams
- if testing.Short() {
- params = []cacheMapTestParams{
- {1000, 100, 20, 3},
- {10000, 300, 50, 10},
- }
- } else {
- params = []cacheMapTestParams{
- {10000, 400, 50, 3},
- {100000, 1000, 100, 10},
- }
- }
-
- var (
- objects [][]int32o
- handles [][]unsafe.Pointer
- )
-
- for _, x := range params {
- 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 params {
- 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
- })
- 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 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
- }{
- {1, "vvvvvvvvv"},
- {100, "v1"},
- {0, "v2"},
- {12346, "v3"},
- {777, "v4"},
- {999, "v5"},
- {7654, "v6"},
- {2, "v7"},
- {3, "v8"},
- {9, "v9"},
- }
-
- setfin := 0
- c := NewCache(NewLRU(1000))
- for i, x := range cases {
- set(c, 0, x.key, x.value, len(x.value), func() {
- setfin++
- }).Release()
- for j, y := range cases {
- h := c.Get(0, y.key, nil)
- if j <= i {
- // should hit
- if h == nil {
- t.Errorf("case '%d' iteration '%d' is miss", i, j)
- } 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 h != nil {
- t.Errorf("case '%d' iteration '%d' is hit , value '%s'", i, j, h.Value().(releaserFunc).value.(string))
- }
- }
- if h != nil {
- h.Release()
- }
- }
- }
-
- for i, x := range cases {
- finalizerOk := false
- c.Delete(0, x.key, func() {
- finalizerOk = true
- })
-
- if !finalizerOk {
- t.Errorf("case %d delete finalizer not executed", i)
- }
-
- for j, y := range cases {
- h := c.Get(0, y.key, nil)
- if j > i {
- // should hit
- if h == nil {
- t.Errorf("case '%d' iteration '%d' is miss", i, j)
- } 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 h != nil {
- t.Errorf("case '%d' iteration '%d' is hit, value '%s'", i, j, h.Value().(releaserFunc).value.(string))
- }
- }
- if h != nil {
- h.Release()
- }
- }
- }
-
- if setfin != len(cases) {
- t.Errorf("some set finalizer may not be executed, want=%d got=%d", len(cases), setfin)
- }
-}
-
-func TestLRUCache_Eviction(t *testing.T) {
- 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 x := h.Value().(int); x != int(key) {
- t.Errorf("invalid value for key '%d' want '%d', got '%d'", key, key, x)
- }
- h.Release()
- }
- }
- o1.Release()
- 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 x := h.Value().(int); x != int(key) {
- t.Errorf("invalid value for key '%d' want '%d', got '%d'", key, key, x)
- }
- h.Release()
- }
- }
- 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)
- }
- h.Release()
- }
- }
-}
-
-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 {
- t.Errorf("Cache.Get on #%d.%d return nil", ns, key)
- }
- }
- }
-
- 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())
- }
- }
- }
-}
-
-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)
- }
- }
-
- h2.Release()
- if h := c.Get(0, 2, nil); h != nil {
- t.Errorf("Cache.Get on #2 return non-nil: %v", h.Value())
- }
-
- if delFuncCalled != 4 {
- t.Errorf("delFunc isn't called 4 times: got=%d", delFuncCalled)
- }
-}
-
-func TestLRUCache_Close(t *testing.T) {
- relFuncCalled := 0
- relFunc := func() {
- relFuncCalled++
- }
- delFuncCalled := 0
- delFunc := func() {
- delFuncCalled++
- }
-
- c := NewCache(NewLRU(2))
- set(c, 0, 1, 1, 1, relFunc).Release()
- set(c, 0, 2, 2, 1, relFunc).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()
-
- 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)
- }
-}
OSDN Git Service
