1package cache
2
3import (
4	"crypto/rand"
5	"math"
6	"math/big"
7	insecurerand "math/rand"
8	"os"
9	"runtime"
10	"time"
11)
12
13// This is an experimental and unexported (for now) attempt at making a cache
14// with better algorithmic complexity than the standard one, namely by
15// preventing write locks of the entire cache when an item is added. As of the
16// time of writing, the overhead of selecting buckets results in cache
17// operations being about twice as slow as for the standard cache with small
18// total cache sizes, and faster for larger ones.
19//
20// See cache_test.go for a few benchmarks.
21
22type unexportedShardedCache struct {
23	*shardedCache
24}
25
26type shardedCache struct {
27	seed    uint32
28	m       uint32
29	cs      []*cache
30	janitor *shardedJanitor
31}
32
33// djb2 with better shuffling. 5x faster than FNV with the hash.Hash overhead.
34func djb33(seed uint32, k string) uint32 {
35	var (
36		l = uint32(len(k))
37		d = 5381 + seed + l
38		i = uint32(0)
39	)
40	// Why is all this 5x faster than a for loop?
41	if l >= 4 {
42		for i < l-4 {
43			d = (d * 33) ^ uint32(k[i])
44			d = (d * 33) ^ uint32(k[i+1])
45			d = (d * 33) ^ uint32(k[i+2])
46			d = (d * 33) ^ uint32(k[i+3])
47			i += 4
48		}
49	}
50	switch l - i {
51	case 1:
52	case 2:
53		d = (d * 33) ^ uint32(k[i])
54	case 3:
55		d = (d * 33) ^ uint32(k[i])
56		d = (d * 33) ^ uint32(k[i+1])
57	case 4:
58		d = (d * 33) ^ uint32(k[i])
59		d = (d * 33) ^ uint32(k[i+1])
60		d = (d * 33) ^ uint32(k[i+2])
61	}
62	return d ^ (d >> 16)
63}
64
65func (sc *shardedCache) bucket(k string) *cache {
66	return sc.cs[djb33(sc.seed, k)%sc.m]
67}
68
69func (sc *shardedCache) Set(k string, x interface{}, d time.Duration) {
70	sc.bucket(k).Set(k, x, d)
71}
72
73func (sc *shardedCache) Add(k string, x interface{}, d time.Duration) error {
74	return sc.bucket(k).Add(k, x, d)
75}
76
77func (sc *shardedCache) Replace(k string, x interface{}, d time.Duration) error {
78	return sc.bucket(k).Replace(k, x, d)
79}
80
81func (sc *shardedCache) Get(k string) (interface{}, bool) {
82	return sc.bucket(k).Get(k)
83}
84
85func (sc *shardedCache) Increment(k string, n int64) error {
86	return sc.bucket(k).Increment(k, n)
87}
88
89func (sc *shardedCache) IncrementFloat(k string, n float64) error {
90	return sc.bucket(k).IncrementFloat(k, n)
91}
92
93func (sc *shardedCache) Decrement(k string, n int64) error {
94	return sc.bucket(k).Decrement(k, n)
95}
96
97func (sc *shardedCache) Delete(k string) {
98	sc.bucket(k).Delete(k)
99}
100
101func (sc *shardedCache) DeleteExpired() {
102	for _, v := range sc.cs {
103		v.DeleteExpired()
104	}
105}
106
107// Returns the items in the cache. This may include items that have expired,
108// but have not yet been cleaned up. If this is significant, the Expiration
109// fields of the items should be checked. Note that explicit synchronization
110// is needed to use a cache and its corresponding Items() return values at
111// the same time, as the maps are shared.
112func (sc *shardedCache) Items() []map[string]Item {
113	res := make([]map[string]Item, len(sc.cs))
114	for i, v := range sc.cs {
115		res[i] = v.Items()
116	}
117	return res
118}
119
120func (sc *shardedCache) Flush() {
121	for _, v := range sc.cs {
122		v.Flush()
123	}
124}
125
126type shardedJanitor struct {
127	Interval time.Duration
128	stop     chan bool
129}
130
131func (j *shardedJanitor) Run(sc *shardedCache) {
132	j.stop = make(chan bool)
133	tick := time.Tick(j.Interval)
134	for {
135		select {
136		case <-tick:
137			sc.DeleteExpired()
138		case <-j.stop:
139			return
140		}
141	}
142}
143
144func stopShardedJanitor(sc *unexportedShardedCache) {
145	sc.janitor.stop <- true
146}
147
148func runShardedJanitor(sc *shardedCache, ci time.Duration) {
149	j := &shardedJanitor{
150		Interval: ci,
151	}
152	sc.janitor = j
153	go j.Run(sc)
154}
155
156func newShardedCache(n int, de time.Duration) *shardedCache {
157	max := big.NewInt(0).SetUint64(uint64(math.MaxUint32))
158	rnd, err := rand.Int(rand.Reader, max)
159	var seed uint32
160	if err != nil {
161		os.Stderr.Write([]byte("WARNING: go-cache's newShardedCache failed to read from the system CSPRNG (/dev/urandom or equivalent.) Your system's security may be compromised. Continuing with an insecure seed.\n"))
162		seed = insecurerand.Uint32()
163	} else {
164		seed = uint32(rnd.Uint64())
165	}
166	sc := &shardedCache{
167		seed: seed,
168		m:    uint32(n),
169		cs:   make([]*cache, n),
170	}
171	for i := 0; i < n; i++ {
172		c := &cache{
173			defaultExpiration: de,
174			items:             map[string]Item{},
175		}
176		sc.cs[i] = c
177	}
178	return sc
179}
180
181func unexportedNewSharded(defaultExpiration, cleanupInterval time.Duration, shards int) *unexportedShardedCache {
182	if defaultExpiration == 0 {
183		defaultExpiration = -1
184	}
185	sc := newShardedCache(shards, defaultExpiration)
186	SC := &unexportedShardedCache{sc}
187	if cleanupInterval > 0 {
188		runShardedJanitor(sc, cleanupInterval)
189		runtime.SetFinalizer(SC, stopShardedJanitor)
190	}
191	return SC
192}
193