vendor/github.com/btcsuite/btcd/blockchain/indexers/addrindex_test.go

   1 // Copyright (c) 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 indexers
   6
   7 import (
   8         "bytes"
   9         "fmt"
  10         "testing"
  11
  12         "github.com/btcsuite/btcd/wire"
  13 )
  14
  15 // addrIndexBucket provides a mock address index database bucket by implementing
  16 // the internalBucket interface.
  17 type addrIndexBucket struct {
  18         levels map[[levelKeySize]byte][]byte
  19 }
  20
  21 // Clone returns a deep copy of the mock address index bucket.
  22 func (b *addrIndexBucket) Clone() *addrIndexBucket {
  23         levels := make(map[[levelKeySize]byte][]byte)
  24         for k, v := range b.levels {
  25                 vCopy := make([]byte, len(v))
  26                 copy(vCopy, v)
  27                 levels[k] = vCopy
  28         }
  29         return &addrIndexBucket{levels: levels}
  30 }
  31
  32 // Get returns the value associated with the key from the mock address index
  33 // bucket.
  34 //
  35 // This is part of the internalBucket interface.
  36 func (b *addrIndexBucket) Get(key []byte) []byte {
  37         var levelKey [levelKeySize]byte
  38         copy(levelKey[:], key)
  39         return b.levels[levelKey]
  40 }
  41
  42 // Put stores the provided key/value pair to the mock address index bucket.
  43 //
  44 // This is part of the internalBucket interface.
  45 func (b *addrIndexBucket) Put(key []byte, value []byte) error {
  46         var levelKey [levelKeySize]byte
  47         copy(levelKey[:], key)
  48         b.levels[levelKey] = value
  49         return nil
  50 }
  51
  52 // Delete removes the provided key from the mock address index bucket.
  53 //
  54 // This is part of the internalBucket interface.
  55 func (b *addrIndexBucket) Delete(key []byte) error {
  56         var levelKey [levelKeySize]byte
  57         copy(levelKey[:], key)
  58         delete(b.levels, levelKey)
  59         return nil
  60 }
  61
  62 // printLevels returns a string with a visual representation of the provided
  63 // address key taking into account the max size of each level.  It is useful
  64 // when creating and debugging test cases.
  65 func (b *addrIndexBucket) printLevels(addrKey [addrKeySize]byte) string {
  66         highestLevel := uint8(0)
  67         for k := range b.levels {
  68                 if !bytes.Equal(k[:levelOffset], addrKey[:]) {
  69                         continue
  70                 }
  71                 level := uint8(k[levelOffset])
  72                 if level > highestLevel {
  73                         highestLevel = level
  74                 }
  75         }
  76
  77         var levelBuf bytes.Buffer
  78         _, _ = levelBuf.WriteString("\n")
  79         maxEntries := level0MaxEntries
  80         for level := uint8(0); level <= highestLevel; level++ {
  81                 data := b.levels[keyForLevel(addrKey, level)]
  82                 numEntries := len(data) / txEntrySize
  83                 for i := 0; i < numEntries; i++ {
  84                         start := i * txEntrySize
  85                         num := byteOrder.Uint32(data[start:])
  86                         _, _ = levelBuf.WriteString(fmt.Sprintf("%02d ", num))
  87                 }
  88                 for i := numEntries; i < maxEntries; i++ {
  89                         _, _ = levelBuf.WriteString("_  ")
  90                 }
  91                 _, _ = levelBuf.WriteString("\n")
  92                 maxEntries *= 2
  93         }
  94
  95         return levelBuf.String()
  96 }
  97
  98 // sanityCheck ensures that all data stored in the bucket for the given address
  99 // adheres to the level-based rules described by the address index
 100 // documentation.
 101 func (b *addrIndexBucket) sanityCheck(addrKey [addrKeySize]byte, expectedTotal int) error {
 102         // Find the highest level for the key.
 103         highestLevel := uint8(0)
 104         for k := range b.levels {
 105                 if !bytes.Equal(k[:levelOffset], addrKey[:]) {
 106                         continue
 107                 }
 108                 level := uint8(k[levelOffset])
 109                 if level > highestLevel {
 110                         highestLevel = level
 111                 }
 112         }
 113
 114         // Ensure the expected total number of entries are present and that
 115         // all levels adhere to the rules described in the address index
 116         // documentation.
 117         var totalEntries int
 118         maxEntries := level0MaxEntries
 119         for level := uint8(0); level <= highestLevel; level++ {
 120                 // Level 0 can'have more entries than the max allowed if the
 121                 // levels after it have data and it can't be empty.  All other
 122                 // levels must either be half full or full.
 123                 data := b.levels[keyForLevel(addrKey, level)]
 124                 numEntries := len(data) / txEntrySize
 125                 totalEntries += numEntries
 126                 if level == 0 {
 127                         if (highestLevel != 0 && numEntries == 0) ||
 128                                 numEntries > maxEntries {
 129
 130                                 return fmt.Errorf("level %d has %d entries",
 131                                         level, numEntries)
 132                         }
 133                 } else if numEntries != maxEntries && numEntries != maxEntries/2 {
 134                         return fmt.Errorf("level %d has %d entries", level,
 135                                 numEntries)
 136                 }
 137                 maxEntries *= 2
 138         }
 139         if totalEntries != expectedTotal {
 140                 return fmt.Errorf("expected %d entries - got %d", expectedTotal,
 141                         totalEntries)
 142         }
 143
 144         // Ensure all of the numbers are in order starting from the highest
 145         // level moving to the lowest level.
 146         expectedNum := uint32(0)
 147         for level := highestLevel + 1; level > 0; level-- {
 148                 data := b.levels[keyForLevel(addrKey, level)]
 149                 numEntries := len(data) / txEntrySize
 150                 for i := 0; i < numEntries; i++ {
 151                         start := i * txEntrySize
 152                         num := byteOrder.Uint32(data[start:])
 153                         if num != expectedNum {
 154                                 return fmt.Errorf("level %d offset %d does "+
 155                                         "not contain the expected number of "+
 156                                         "%d - got %d", level, i, num,
 157                                         expectedNum)
 158                         }
 159                         expectedNum++
 160                 }
 161         }
 162
 163         return nil
 164 }
 165
 166 // TestAddrIndexLevels ensures that adding and deleting entries to the address
 167 // index creates multiple levels as described by the address index
 168 // documentation.
 169 func TestAddrIndexLevels(t *testing.T) {
 170         t.Parallel()
 171
 172         tests := []struct {
 173                 name        string
 174                 key         [addrKeySize]byte
 175                 numInsert   int
 176                 printLevels bool // Set to help debug a specific test.
 177         }{
 178                 {
 179                         name:      "level 0 not full",
 180                         numInsert: level0MaxEntries - 1,
 181                 },
 182                 {
 183                         name:      "level 1 half",
 184                         numInsert: level0MaxEntries + 1,
 185                 },
 186                 {
 187                         name:      "level 1 full",
 188                         numInsert: level0MaxEntries*2 + 1,
 189                 },
 190                 {
 191                         name:      "level 2 half, level 1 half",
 192                         numInsert: level0MaxEntries*3 + 1,
 193                 },
 194                 {
 195                         name:      "level 2 half, level 1 full",
 196                         numInsert: level0MaxEntries*4 + 1,
 197                 },
 198                 {
 199                         name:      "level 2 full, level 1 half",
 200                         numInsert: level0MaxEntries*5 + 1,
 201                 },
 202                 {
 203                         name:      "level 2 full, level 1 full",
 204                         numInsert: level0MaxEntries*6 + 1,
 205                 },
 206                 {
 207                         name:      "level 3 half, level 2 half, level 1 half",
 208                         numInsert: level0MaxEntries*7 + 1,
 209                 },
 210                 {
 211                         name:      "level 3 full, level 2 half, level 1 full",
 212                         numInsert: level0MaxEntries*12 + 1,
 213                 },
 214         }
 215
 216 nextTest:
 217         for testNum, test := range tests {
 218                 // Insert entries in order.
 219                 populatedBucket := &addrIndexBucket{
 220                         levels: make(map[[levelKeySize]byte][]byte),
 221                 }
 222                 for i := 0; i < test.numInsert; i++ {
 223                         txLoc := wire.TxLoc{TxStart: i * 2}
 224                         err := dbPutAddrIndexEntry(populatedBucket, test.key,
 225                                 uint32(i), txLoc)
 226                         if err != nil {
 227                                 t.Errorf("dbPutAddrIndexEntry #%d (%s) - "+
 228                                         "unexpected error: %v", testNum,
 229                                         test.name, err)
 230                                 continue nextTest
 231                         }
 232                 }
 233                 if test.printLevels {
 234                         t.Log(populatedBucket.printLevels(test.key))
 235                 }
 236
 237                 // Delete entries from the populated bucket until all entries
 238                 // have been deleted.  The bucket is reset to the fully
 239                 // populated bucket on each iteration so every combination is
 240                 // tested.  Notice the upper limit purposes exceeds the number
 241                 // of entries to ensure attempting to delete more entries than
 242                 // there are works correctly.
 243                 for numDelete := 0; numDelete <= test.numInsert+1; numDelete++ {
 244                         // Clone populated bucket to run each delete against.
 245                         bucket := populatedBucket.Clone()
 246
 247                         // Remove the number of entries for this iteration.
 248                         err := dbRemoveAddrIndexEntries(bucket, test.key,
 249                                 numDelete)
 250                         if err != nil {
 251                                 if numDelete <= test.numInsert {
 252                                         t.Errorf("dbRemoveAddrIndexEntries (%s) "+
 253                                                 " delete %d - unexpected error: "+
 254                                                 "%v", test.name, numDelete, err)
 255                                         continue nextTest
 256                                 }
 257                         }
 258                         if test.printLevels {
 259                                 t.Log(bucket.printLevels(test.key))
 260                         }
 261
 262                         // Sanity check the levels to ensure the adhere to all
 263                         // rules.
 264                         numExpected := test.numInsert
 265                         if numDelete <= test.numInsert {
 266                                 numExpected -= numDelete
 267                         }
 268                         err = bucket.sanityCheck(test.key, numExpected)
 269                         if err != nil {
 270                                 t.Errorf("sanity check fail (%s) delete %d: %v",
 271                                         test.name, numDelete, err)
 272                                 continue nextTest
 273                         }
 274                 }
 275         }
 276 }