vendor/github.com/golang/groupcache/groupcache_test.go

   1 /*
   2 Copyright 2012 Google Inc.
   3
   4 Licensed under the Apache License, Version 2.0 (the "License");
   5 you may not use this file except in compliance with the License.
   6 You may obtain a copy of the License at
   7
   8      http://www.apache.org/licenses/LICENSE-2.0
   9
  10 Unless required by applicable law or agreed to in writing, software
  11 distributed under the License is distributed on an "AS IS" BASIS,
  12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13 See the License for the specific language governing permissions and
  14 limitations under the License.
  15 */
  16
  17 // Tests for groupcache.
  18
  19 package groupcache
  20
  21 import (
  22         "errors"
  23         "fmt"
  24         "hash/crc32"
  25         "math/rand"
  26         "reflect"
  27         "sync"
  28         "testing"
  29         "time"
  30         "unsafe"
  31
  32         "github.com/golang/protobuf/proto"
  33
  34         pb "github.com/golang/groupcache/groupcachepb"
  35         testpb "github.com/golang/groupcache/testpb"
  36 )
  37
  38 var (
  39         once                    sync.Once
  40         stringGroup, protoGroup Getter
  41
  42         stringc = make(chan string)
  43
  44         dummyCtx Context
  45
  46         // cacheFills is the number of times stringGroup or
  47         // protoGroup's Getter have been called. Read using the
  48         // cacheFills function.
  49         cacheFills AtomicInt
  50 )
  51
  52 const (
  53         stringGroupName = "string-group"
  54         protoGroupName  = "proto-group"
  55         testMessageType = "google3/net/groupcache/go/test_proto.TestMessage"
  56         fromChan        = "from-chan"
  57         cacheSize       = 1 << 20
  58 )
  59
  60 func testSetup() {
  61         stringGroup = NewGroup(stringGroupName, cacheSize, GetterFunc(func(_ Context, key string, dest Sink) error {
  62                 if key == fromChan {
  63                         key = <-stringc
  64                 }
  65                 cacheFills.Add(1)
  66                 return dest.SetString("ECHO:" + key)
  67         }))
  68
  69         protoGroup = NewGroup(protoGroupName, cacheSize, GetterFunc(func(_ Context, key string, dest Sink) error {
  70                 if key == fromChan {
  71                         key = <-stringc
  72                 }
  73                 cacheFills.Add(1)
  74                 return dest.SetProto(&testpb.TestMessage{
  75                         Name: proto.String("ECHO:" + key),
  76                         City: proto.String("SOME-CITY"),
  77                 })
  78         }))
  79 }
  80
  81 // tests that a Getter's Get method is only called once with two
  82 // outstanding callers.  This is the string variant.
  83 func TestGetDupSuppressString(t *testing.T) {
  84         once.Do(testSetup)
  85         // Start two getters. The first should block (waiting reading
  86         // from stringc) and the second should latch on to the first
  87         // one.
  88         resc := make(chan string, 2)
  89         for i := 0; i < 2; i++ {
  90                 go func() {
  91                         var s string
  92                         if err := stringGroup.Get(dummyCtx, fromChan, StringSink(&s)); err != nil {
  93                                 resc <- "ERROR:" + err.Error()
  94                                 return
  95                         }
  96                         resc <- s
  97                 }()
  98         }
  99
 100         // Wait a bit so both goroutines get merged together via
 101         // singleflight.
 102         // TODO(bradfitz): decide whether there are any non-offensive
 103         // debug/test hooks that could be added to singleflight to
 104         // make a sleep here unnecessary.
 105         time.Sleep(250 * time.Millisecond)
 106
 107         // Unblock the first getter, which should unblock the second
 108         // as well.
 109         stringc <- "foo"
 110
 111         for i := 0; i < 2; i++ {
 112                 select {
 113                 case v := <-resc:
 114                         if v != "ECHO:foo" {
 115                                 t.Errorf("got %q; want %q", v, "ECHO:foo")
 116                         }
 117                 case <-time.After(5 * time.Second):
 118                         t.Errorf("timeout waiting on getter #%d of 2", i+1)
 119                 }
 120         }
 121 }
 122
 123 // tests that a Getter's Get method is only called once with two
 124 // outstanding callers.  This is the proto variant.
 125 func TestGetDupSuppressProto(t *testing.T) {
 126         once.Do(testSetup)
 127         // Start two getters. The first should block (waiting reading
 128         // from stringc) and the second should latch on to the first
 129         // one.
 130         resc := make(chan *testpb.TestMessage, 2)
 131         for i := 0; i < 2; i++ {
 132                 go func() {
 133                         tm := new(testpb.TestMessage)
 134                         if err := protoGroup.Get(dummyCtx, fromChan, ProtoSink(tm)); err != nil {
 135                                 tm.Name = proto.String("ERROR:" + err.Error())
 136                         }
 137                         resc <- tm
 138                 }()
 139         }
 140
 141         // Wait a bit so both goroutines get merged together via
 142         // singleflight.
 143         // TODO(bradfitz): decide whether there are any non-offensive
 144         // debug/test hooks that could be added to singleflight to
 145         // make a sleep here unnecessary.
 146         time.Sleep(250 * time.Millisecond)
 147
 148         // Unblock the first getter, which should unblock the second
 149         // as well.
 150         stringc <- "Fluffy"
 151         want := &testpb.TestMessage{
 152                 Name: proto.String("ECHO:Fluffy"),
 153                 City: proto.String("SOME-CITY"),
 154         }
 155         for i := 0; i < 2; i++ {
 156                 select {
 157                 case v := <-resc:
 158                         if !reflect.DeepEqual(v, want) {
 159                                 t.Errorf(" Got: %v\nWant: %v", proto.CompactTextString(v), proto.CompactTextString(want))
 160                         }
 161                 case <-time.After(5 * time.Second):
 162                         t.Errorf("timeout waiting on getter #%d of 2", i+1)
 163                 }
 164         }
 165 }
 166
 167 func countFills(f func()) int64 {
 168         fills0 := cacheFills.Get()
 169         f()
 170         return cacheFills.Get() - fills0
 171 }
 172
 173 func TestCaching(t *testing.T) {
 174         once.Do(testSetup)
 175         fills := countFills(func() {
 176                 for i := 0; i < 10; i++ {
 177                         var s string
 178                         if err := stringGroup.Get(dummyCtx, "TestCaching-key", StringSink(&s)); err != nil {
 179                                 t.Fatal(err)
 180                         }
 181                 }
 182         })
 183         if fills != 1 {
 184                 t.Errorf("expected 1 cache fill; got %d", fills)
 185         }
 186 }
 187
 188 func TestCacheEviction(t *testing.T) {
 189         once.Do(testSetup)
 190         testKey := "TestCacheEviction-key"
 191         getTestKey := func() {
 192                 var res string
 193                 for i := 0; i < 10; i++ {
 194                         if err := stringGroup.Get(dummyCtx, testKey, StringSink(&res)); err != nil {
 195                                 t.Fatal(err)
 196                         }
 197                 }
 198         }
 199         fills := countFills(getTestKey)
 200         if fills != 1 {
 201                 t.Fatalf("expected 1 cache fill; got %d", fills)
 202         }
 203
 204         g := stringGroup.(*Group)
 205         evict0 := g.mainCache.nevict
 206
 207         // Trash the cache with other keys.
 208         var bytesFlooded int64
 209         // cacheSize/len(testKey) is approximate
 210         for bytesFlooded < cacheSize+1024 {
 211                 var res string
 212                 key := fmt.Sprintf("dummy-key-%d", bytesFlooded)
 213                 stringGroup.Get(dummyCtx, key, StringSink(&res))
 214                 bytesFlooded += int64(len(key) + len(res))
 215         }
 216         evicts := g.mainCache.nevict - evict0
 217         if evicts <= 0 {
 218                 t.Errorf("evicts = %v; want more than 0", evicts)
 219         }
 220
 221         // Test that the key is gone.
 222         fills = countFills(getTestKey)
 223         if fills != 1 {
 224                 t.Fatalf("expected 1 cache fill after cache trashing; got %d", fills)
 225         }
 226 }
 227
 228 type fakePeer struct {
 229         hits int
 230         fail bool
 231 }
 232
 233 func (p *fakePeer) Get(_ Context, in *pb.GetRequest, out *pb.GetResponse) error {
 234         p.hits++
 235         if p.fail {
 236                 return errors.New("simulated error from peer")
 237         }
 238         out.Value = []byte("got:" + in.GetKey())
 239         return nil
 240 }
 241
 242 type fakePeers []ProtoGetter
 243
 244 func (p fakePeers) PickPeer(key string) (peer ProtoGetter, ok bool) {
 245         if len(p) == 0 {
 246                 return
 247         }
 248         n := crc32.Checksum([]byte(key), crc32.IEEETable) % uint32(len(p))
 249         return p[n], p[n] != nil
 250 }
 251
 252 // tests that peers (virtual, in-process) are hit, and how much.
 253 func TestPeers(t *testing.T) {
 254         once.Do(testSetup)
 255         rand.Seed(123)
 256         peer0 := &fakePeer{}
 257         peer1 := &fakePeer{}
 258         peer2 := &fakePeer{}
 259         peerList := fakePeers([]ProtoGetter{peer0, peer1, peer2, nil})
 260         const cacheSize = 0 // disabled
 261         localHits := 0
 262         getter := func(_ Context, key string, dest Sink) error {
 263                 localHits++
 264                 return dest.SetString("got:" + key)
 265         }
 266         testGroup := newGroup("TestPeers-group", cacheSize, GetterFunc(getter), peerList)
 267         run := func(name string, n int, wantSummary string) {
 268                 // Reset counters
 269                 localHits = 0
 270                 for _, p := range []*fakePeer{peer0, peer1, peer2} {
 271                         p.hits = 0
 272                 }
 273
 274                 for i := 0; i < n; i++ {
 275                         key := fmt.Sprintf("key-%d", i)
 276                         want := "got:" + key
 277                         var got string
 278                         err := testGroup.Get(dummyCtx, key, StringSink(&got))
 279                         if err != nil {
 280                                 t.Errorf("%s: error on key %q: %v", name, key, err)
 281                                 continue
 282                         }
 283                         if got != want {
 284                                 t.Errorf("%s: for key %q, got %q; want %q", name, key, got, want)
 285                         }
 286                 }
 287                 summary := func() string {
 288                         return fmt.Sprintf("localHits = %d, peers = %d %d %d", localHits, peer0.hits, peer1.hits, peer2.hits)
 289                 }
 290                 if got := summary(); got != wantSummary {
 291                         t.Errorf("%s: got %q; want %q", name, got, wantSummary)
 292                 }
 293         }
 294         resetCacheSize := func(maxBytes int64) {
 295                 g := testGroup
 296                 g.cacheBytes = maxBytes
 297                 g.mainCache = cache{}
 298                 g.hotCache = cache{}
 299         }
 300
 301         // Base case; peers all up, with no problems.
 302         resetCacheSize(1 << 20)
 303         run("base", 200, "localHits = 49, peers = 51 49 51")
 304
 305         // Verify cache was hit.  All localHits are gone, and some of
 306         // the peer hits (the ones randomly selected to be maybe hot)
 307         run("cached_base", 200, "localHits = 0, peers = 49 47 48")
 308         resetCacheSize(0)
 309
 310         // With one of the peers being down.
 311         // TODO(bradfitz): on a peer number being unavailable, the
 312         // consistent hashing should maybe keep trying others to
 313         // spread the load out. Currently it fails back to local
 314         // execution if the first consistent-hash slot is unavailable.
 315         peerList[0] = nil
 316         run("one_peer_down", 200, "localHits = 100, peers = 0 49 51")
 317
 318         // Failing peer
 319         peerList[0] = peer0
 320         peer0.fail = true
 321         run("peer0_failing", 200, "localHits = 100, peers = 51 49 51")
 322 }
 323
 324 func TestTruncatingByteSliceTarget(t *testing.T) {
 325         var buf [100]byte
 326         s := buf[:]
 327         if err := stringGroup.Get(dummyCtx, "short", TruncatingByteSliceSink(&s)); err != nil {
 328                 t.Fatal(err)
 329         }
 330         if want := "ECHO:short"; string(s) != want {
 331                 t.Errorf("short key got %q; want %q", s, want)
 332         }
 333
 334         s = buf[:6]
 335         if err := stringGroup.Get(dummyCtx, "truncated", TruncatingByteSliceSink(&s)); err != nil {
 336                 t.Fatal(err)
 337         }
 338         if want := "ECHO:t"; string(s) != want {
 339                 t.Errorf("truncated key got %q; want %q", s, want)
 340         }
 341 }
 342
 343 func TestAllocatingByteSliceTarget(t *testing.T) {
 344         var dst []byte
 345         sink := AllocatingByteSliceSink(&dst)
 346
 347         inBytes := []byte("some bytes")
 348         sink.SetBytes(inBytes)
 349         if want := "some bytes"; string(dst) != want {
 350                 t.Errorf("SetBytes resulted in %q; want %q", dst, want)
 351         }
 352         v, err := sink.view()
 353         if err != nil {
 354                 t.Fatalf("view after SetBytes failed: %v", err)
 355         }
 356         if &inBytes[0] == &dst[0] {
 357                 t.Error("inBytes and dst share memory")
 358         }
 359         if &inBytes[0] == &v.b[0] {
 360                 t.Error("inBytes and view share memory")
 361         }
 362         if &dst[0] == &v.b[0] {
 363                 t.Error("dst and view share memory")
 364         }
 365 }
 366
 367 // orderedFlightGroup allows the caller to force the schedule of when
 368 // orig.Do will be called.  This is useful to serialize calls such
 369 // that singleflight cannot dedup them.
 370 type orderedFlightGroup struct {
 371         mu     sync.Mutex
 372         stage1 chan bool
 373         stage2 chan bool
 374         orig   flightGroup
 375 }
 376
 377 func (g *orderedFlightGroup) Do(key string, fn func() (interface{}, error)) (interface{}, error) {
 378         <-g.stage1
 379         <-g.stage2
 380         g.mu.Lock()
 381         defer g.mu.Unlock()
 382         return g.orig.Do(key, fn)
 383 }
 384
 385 // TestNoDedup tests invariants on the cache size when singleflight is
 386 // unable to dedup calls.
 387 func TestNoDedup(t *testing.T) {
 388         const testkey = "testkey"
 389         const testval = "testval"
 390         g := newGroup("testgroup", 1024, GetterFunc(func(_ Context, key string, dest Sink) error {
 391                 return dest.SetString(testval)
 392         }), nil)
 393
 394         orderedGroup := &orderedFlightGroup{
 395                 stage1: make(chan bool),
 396                 stage2: make(chan bool),
 397                 orig:   g.loadGroup,
 398         }
 399         // Replace loadGroup with our wrapper so we can control when
 400         // loadGroup.Do is entered for each concurrent request.
 401         g.loadGroup = orderedGroup
 402
 403         // Issue two idential requests concurrently.  Since the cache is
 404         // empty, it will miss.  Both will enter load(), but we will only
 405         // allow one at a time to enter singleflight.Do, so the callback
 406         // function will be called twice.
 407         resc := make(chan string, 2)
 408         for i := 0; i < 2; i++ {
 409                 go func() {
 410                         var s string
 411                         if err := g.Get(dummyCtx, testkey, StringSink(&s)); err != nil {
 412                                 resc <- "ERROR:" + err.Error()
 413                                 return
 414                         }
 415                         resc <- s
 416                 }()
 417         }
 418
 419         // Ensure both goroutines have entered the Do routine.  This implies
 420         // both concurrent requests have checked the cache, found it empty,
 421         // and called load().
 422         orderedGroup.stage1 <- true
 423         orderedGroup.stage1 <- true
 424         orderedGroup.stage2 <- true
 425         orderedGroup.stage2 <- true
 426
 427         for i := 0; i < 2; i++ {
 428                 if s := <-resc; s != testval {
 429                         t.Errorf("result is %s want %s", s, testval)
 430                 }
 431         }
 432
 433         const wantItems = 1
 434         if g.mainCache.items() != wantItems {
 435                 t.Errorf("mainCache has %d items, want %d", g.mainCache.items(), wantItems)
 436         }
 437
 438         // If the singleflight callback doesn't double-check the cache again
 439         // upon entry, we would increment nbytes twice but the entry would
 440         // only be in the cache once.
 441         const wantBytes = int64(len(testkey) + len(testval))
 442         if g.mainCache.nbytes != wantBytes {
 443                 t.Errorf("cache has %d bytes, want %d", g.mainCache.nbytes, wantBytes)
 444         }
 445 }
 446
 447 func TestGroupStatsAlignment(t *testing.T) {
 448         var g Group
 449         off := unsafe.Offsetof(g.Stats)
 450         if off%8 != 0 {
 451                 t.Fatal("Stats structure is not 8-byte aligned.")
 452         }
 453 }
 454
 455 // TODO(bradfitz): port the Google-internal full integration test into here,
 456 // using HTTP requests instead of our RPC system.