vendor/github.com/btcsuite/btcd/peer/mruinvmap_test.go

   1 // Copyright (c) 2013-2016 The btcsuite developers
   2 // Use of this source code is governed by an ISC
   3 // license that can be found in the LICENSE file.
   4
   5 package peer
   6
   7 import (
   8         "crypto/rand"
   9         "fmt"
  10         "testing"
  11
  12         "github.com/btcsuite/btcd/chaincfg/chainhash"
  13         "github.com/btcsuite/btcd/wire"
  14 )
  15
  16 // TestMruInventoryMap ensures the MruInventoryMap behaves as expected including
  17 // limiting, eviction of least-recently used entries, specific entry removal,
  18 // and existence tests.
  19 func TestMruInventoryMap(t *testing.T) {
  20         // Create a bunch of fake inventory vectors to use in testing the mru
  21         // inventory code.
  22         numInvVects := 10
  23         invVects := make([]*wire.InvVect, 0, numInvVects)
  24         for i := 0; i < numInvVects; i++ {
  25                 hash := &chainhash.Hash{byte(i)}
  26                 iv := wire.NewInvVect(wire.InvTypeBlock, hash)
  27                 invVects = append(invVects, iv)
  28         }
  29
  30         tests := []struct {
  31                 name  string
  32                 limit int
  33         }{
  34                 {name: "limit 0", limit: 0},
  35                 {name: "limit 1", limit: 1},
  36                 {name: "limit 5", limit: 5},
  37                 {name: "limit 7", limit: 7},
  38                 {name: "limit one less than available", limit: numInvVects - 1},
  39                 {name: "limit all available", limit: numInvVects},
  40         }
  41
  42 testLoop:
  43         for i, test := range tests {
  44                 // Create a new mru inventory map limited by the specified test
  45                 // limit and add all of the test inventory vectors.  This will
  46                 // cause evicition since there are more test inventory vectors
  47                 // than the limits.
  48                 mruInvMap := newMruInventoryMap(uint(test.limit))
  49                 for j := 0; j < numInvVects; j++ {
  50                         mruInvMap.Add(invVects[j])
  51                 }
  52
  53                 // Ensure the limited number of most recent entries in the
  54                 // inventory vector list exist.
  55                 for j := numInvVects - test.limit; j < numInvVects; j++ {
  56                         if !mruInvMap.Exists(invVects[j]) {
  57                                 t.Errorf("Exists #%d (%s) entry %s does not "+
  58                                         "exist", i, test.name, *invVects[j])
  59                                 continue testLoop
  60                         }
  61                 }
  62
  63                 // Ensure the entries before the limited number of most recent
  64                 // entries in the inventory vector list do not exist.
  65                 for j := 0; j < numInvVects-test.limit; j++ {
  66                         if mruInvMap.Exists(invVects[j]) {
  67                                 t.Errorf("Exists #%d (%s) entry %s exists", i,
  68                                         test.name, *invVects[j])
  69                                 continue testLoop
  70                         }
  71                 }
  72
  73                 // Readd the entry that should currently be the least-recently
  74                 // used entry so it becomes the most-recently used entry, then
  75                 // force an eviction by adding an entry that doesn't exist and
  76                 // ensure the evicted entry is the new least-recently used
  77                 // entry.
  78                 //
  79                 // This check needs at least 2 entries.
  80                 if test.limit > 1 {
  81                         origLruIndex := numInvVects - test.limit
  82                         mruInvMap.Add(invVects[origLruIndex])
  83
  84                         iv := wire.NewInvVect(wire.InvTypeBlock,
  85                                 &chainhash.Hash{0x00, 0x01})
  86                         mruInvMap.Add(iv)
  87
  88                         // Ensure the original lru entry still exists since it
  89                         // was updated and should've have become the mru entry.
  90                         if !mruInvMap.Exists(invVects[origLruIndex]) {
  91                                 t.Errorf("MRU #%d (%s) entry %s does not exist",
  92                                         i, test.name, *invVects[origLruIndex])
  93                                 continue testLoop
  94                         }
  95
  96                         // Ensure the entry that should've become the new lru
  97                         // entry was evicted.
  98                         newLruIndex := origLruIndex + 1
  99                         if mruInvMap.Exists(invVects[newLruIndex]) {
 100                                 t.Errorf("MRU #%d (%s) entry %s exists", i,
 101                                         test.name, *invVects[newLruIndex])
 102                                 continue testLoop
 103                         }
 104                 }
 105
 106                 // Delete all of the entries in the inventory vector list,
 107                 // including those that don't exist in the map, and ensure they
 108                 // no longer exist.
 109                 for j := 0; j < numInvVects; j++ {
 110                         mruInvMap.Delete(invVects[j])
 111                         if mruInvMap.Exists(invVects[j]) {
 112                                 t.Errorf("Delete #%d (%s) entry %s exists", i,
 113                                         test.name, *invVects[j])
 114                                 continue testLoop
 115                         }
 116                 }
 117         }
 118 }
 119
 120 // TestMruInventoryMapStringer tests the stringized output for the
 121 // MruInventoryMap type.
 122 func TestMruInventoryMapStringer(t *testing.T) {
 123         // Create a couple of fake inventory vectors to use in testing the mru
 124         // inventory stringer code.
 125         hash1 := &chainhash.Hash{0x01}
 126         hash2 := &chainhash.Hash{0x02}
 127         iv1 := wire.NewInvVect(wire.InvTypeBlock, hash1)
 128         iv2 := wire.NewInvVect(wire.InvTypeBlock, hash2)
 129
 130         // Create new mru inventory map and add the inventory vectors.
 131         mruInvMap := newMruInventoryMap(uint(2))
 132         mruInvMap.Add(iv1)
 133         mruInvMap.Add(iv2)
 134
 135         // Ensure the stringer gives the expected result.  Since map iteration
 136         // is not ordered, either entry could be first, so account for both
 137         // cases.
 138         wantStr1 := fmt.Sprintf("<%d>[%s, %s]", 2, *iv1, *iv2)
 139         wantStr2 := fmt.Sprintf("<%d>[%s, %s]", 2, *iv2, *iv1)
 140         gotStr := mruInvMap.String()
 141         if gotStr != wantStr1 && gotStr != wantStr2 {
 142                 t.Fatalf("unexpected string representation - got %q, want %q "+
 143                         "or %q", gotStr, wantStr1, wantStr2)
 144         }
 145 }
 146
 147 // BenchmarkMruInventoryList performs basic benchmarks on the most recently
 148 // used inventory handling.
 149 func BenchmarkMruInventoryList(b *testing.B) {
 150         // Create a bunch of fake inventory vectors to use in benchmarking
 151         // the mru inventory code.
 152         b.StopTimer()
 153         numInvVects := 100000
 154         invVects := make([]*wire.InvVect, 0, numInvVects)
 155         for i := 0; i < numInvVects; i++ {
 156                 hashBytes := make([]byte, chainhash.HashSize)
 157                 rand.Read(hashBytes)
 158                 hash, _ := chainhash.NewHash(hashBytes)
 159                 iv := wire.NewInvVect(wire.InvTypeBlock, hash)
 160                 invVects = append(invVects, iv)
 161         }
 162         b.StartTimer()
 163
 164         // Benchmark the add plus evicition code.
 165         limit := 20000
 166         mruInvMap := newMruInventoryMap(uint(limit))
 167         for i := 0; i < b.N; i++ {
 168                 mruInvMap.Add(invVects[i%numInvVects])
 169         }
 170 }