path: root/Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/cache/cache_test.go

// 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}
        } 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
    })
    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)
    }
}