vendor/github.com/btcsuite/btcd/blockchain/blockindex.go

   1 // Copyright (c) 2015-2017 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 blockchain
   6
   7 import (
   8         "math/big"
   9         "sort"
  10         "sync"
  11         "time"
  12
  13         "github.com/btcsuite/btcd/chaincfg"
  14         "github.com/btcsuite/btcd/chaincfg/chainhash"
  15         "github.com/btcsuite/btcd/database"
  16         "github.com/btcsuite/btcd/wire"
  17 )
  18
  19 // blockNode represents a block within the block chain and is primarily used to
  20 // aid in selecting the best chain to be the main chain.  The main chain is
  21 // stored into the block database.
  22 type blockNode struct {
  23         // NOTE: Additions, deletions, or modifications to the order of the
  24         // definitions in this struct should not be changed without considering
  25         // how it affects alignment on 64-bit platforms.  The current order is
  26         // specifically crafted to result in minimal padding.  There will be
  27         // hundreds of thousands of these in memory, so a few extra bytes of
  28         // padding adds up.
  29
  30         // parent is the parent block for this node.
  31         parent *blockNode
  32
  33         // hash is the double sha 256 of the block.
  34         hash chainhash.Hash
  35
  36         // workSum is the total amount of work in the chain up to and including
  37         // this node.
  38         workSum *big.Int
  39
  40         // height is the position in the block chain.
  41         height int32
  42
  43         // Some fields from block headers to aid in best chain selection and
  44         // reconstructing headers from memory.  These must be treated as
  45         // immutable and are intentionally ordered to avoid padding on 64-bit
  46         // platforms.
  47         version    int32
  48         bits       uint32
  49         nonce      uint32
  50         timestamp  int64
  51         merkleRoot chainhash.Hash
  52 }
  53
  54 // initBlockNode initializes a block node from the given header and height.  The
  55 // node is completely disconnected from the chain and the workSum value is just
  56 // the work for the passed block.  The work sum must be updated accordingly when
  57 // the node is inserted into a chain.
  58 //
  59 // This function is NOT safe for concurrent access.  It must only be called when
  60 // initially creating a node.
  61 func initBlockNode(node *blockNode, blockHeader *wire.BlockHeader, height int32) {
  62         *node = blockNode{
  63                 hash:       blockHeader.BlockHash(),
  64                 workSum:    CalcWork(blockHeader.Bits),
  65                 height:     height,
  66                 version:    blockHeader.Version,
  67                 bits:       blockHeader.Bits,
  68                 nonce:      blockHeader.Nonce,
  69                 timestamp:  blockHeader.Timestamp.Unix(),
  70                 merkleRoot: blockHeader.MerkleRoot,
  71         }
  72 }
  73
  74 // newBlockNode returns a new block node for the given block header.  It is
  75 // completely disconnected from the chain and the workSum value is just the work
  76 // for the passed block.  The work sum must be updated accordingly when the node
  77 // is inserted into a chain.
  78 func newBlockNode(blockHeader *wire.BlockHeader, height int32) *blockNode {
  79         var node blockNode
  80         initBlockNode(&node, blockHeader, height)
  81         return &node
  82 }
  83
  84 // Header constructs a block header from the node and returns it.
  85 //
  86 // This function is safe for concurrent access.
  87 func (node *blockNode) Header() wire.BlockHeader {
  88         // No lock is needed because all accessed fields are immutable.
  89         prevHash := zeroHash
  90         if node.parent != nil {
  91                 prevHash = &node.parent.hash
  92         }
  93         return wire.BlockHeader{
  94                 Version:    node.version,
  95                 PrevBlock:  *prevHash,
  96                 MerkleRoot: node.merkleRoot,
  97                 Timestamp:  time.Unix(node.timestamp, 0),
  98                 Bits:       node.bits,
  99                 Nonce:      node.nonce,
 100         }
 101 }
 102
 103 // Ancestor returns the ancestor block node at the provided height by following
 104 // the chain backwards from this node.  The returned block will be nil when a
 105 // height is requested that is after the height of the passed node or is less
 106 // than zero.
 107 //
 108 // This function is safe for concurrent access.
 109 func (node *blockNode) Ancestor(height int32) *blockNode {
 110         if height < 0 || height > node.height {
 111                 return nil
 112         }
 113
 114         n := node
 115         for ; n != nil && n.height != height; n = n.parent {
 116                 // Intentionally left blank
 117         }
 118
 119         return n
 120 }
 121
 122 // RelativeAncestor returns the ancestor block node a relative 'distance' blocks
 123 // before this node.  This is equivalent to calling Ancestor with the node's
 124 // height minus provided distance.
 125 //
 126 // This function is safe for concurrent access.
 127 func (node *blockNode) RelativeAncestor(distance int32) *blockNode {
 128         return node.Ancestor(node.height - distance)
 129 }
 130
 131 // CalcPastMedianTime calculates the median time of the previous few blocks
 132 // prior to, and including, the block node.
 133 //
 134 // This function is safe for concurrent access.
 135 func (node *blockNode) CalcPastMedianTime() time.Time {
 136         // Create a slice of the previous few block timestamps used to calculate
 137         // the median per the number defined by the constant medianTimeBlocks.
 138         timestamps := make([]int64, medianTimeBlocks)
 139         numNodes := 0
 140         iterNode := node
 141         for i := 0; i < medianTimeBlocks && iterNode != nil; i++ {
 142                 timestamps[i] = iterNode.timestamp
 143                 numNodes++
 144
 145                 iterNode = iterNode.parent
 146         }
 147
 148         // Prune the slice to the actual number of available timestamps which
 149         // will be fewer than desired near the beginning of the block chain
 150         // and sort them.
 151         timestamps = timestamps[:numNodes]
 152         sort.Sort(timeSorter(timestamps))
 153
 154         // NOTE: The consensus rules incorrectly calculate the median for even
 155         // numbers of blocks.  A true median averages the middle two elements
 156         // for a set with an even number of elements in it.   Since the constant
 157         // for the previous number of blocks to be used is odd, this is only an
 158         // issue for a few blocks near the beginning of the chain.  I suspect
 159         // this is an optimization even though the result is slightly wrong for
 160         // a few of the first blocks since after the first few blocks, there
 161         // will always be an odd number of blocks in the set per the constant.
 162         //
 163         // This code follows suit to ensure the same rules are used, however, be
 164         // aware that should the medianTimeBlocks constant ever be changed to an
 165         // even number, this code will be wrong.
 166         medianTimestamp := timestamps[numNodes/2]
 167         return time.Unix(medianTimestamp, 0)
 168 }
 169
 170 // blockIndex provides facilities for keeping track of an in-memory index of the
 171 // block chain.  Although the name block chain suggests a single chain of
 172 // blocks, it is actually a tree-shaped structure where any node can have
 173 // multiple children.  However, there can only be one active branch which does
 174 // indeed form a chain from the tip all the way back to the genesis block.
 175 type blockIndex struct {
 176         // The following fields are set when the instance is created and can't
 177         // be changed afterwards, so there is no need to protect them with a
 178         // separate mutex.
 179         db          database.DB
 180         chainParams *chaincfg.Params
 181
 182         sync.RWMutex
 183         index map[chainhash.Hash]*blockNode
 184 }
 185
 186 // newBlockIndex returns a new empty instance of a block index.  The index will
 187 // be dynamically populated as block nodes are loaded from the database and
 188 // manually added.
 189 func newBlockIndex(db database.DB, chainParams *chaincfg.Params) *blockIndex {
 190         return &blockIndex{
 191                 db:          db,
 192                 chainParams: chainParams,
 193                 index:       make(map[chainhash.Hash]*blockNode),
 194         }
 195 }
 196
 197 // HaveBlock returns whether or not the block index contains the provided hash.
 198 //
 199 // This function is safe for concurrent access.
 200 func (bi *blockIndex) HaveBlock(hash *chainhash.Hash) bool {
 201         bi.RLock()
 202         _, hasBlock := bi.index[*hash]
 203         bi.RUnlock()
 204         return hasBlock
 205 }
 206
 207 // LookupNode returns the block node identified by the provided hash.  It will
 208 // return nil if there is no entry for the hash.
 209 //
 210 // This function is safe for concurrent access.
 211 func (bi *blockIndex) LookupNode(hash *chainhash.Hash) *blockNode {
 212         bi.RLock()
 213         node := bi.index[*hash]
 214         bi.RUnlock()
 215         return node
 216 }
 217
 218 // AddNode adds the provided node to the block index.  Duplicate entries are not
 219 // checked so it is up to caller to avoid adding them.
 220 //
 221 // This function is safe for concurrent access.
 222 func (bi *blockIndex) AddNode(node *blockNode) {
 223         bi.Lock()
 224         bi.index[node.hash] = node
 225         bi.Unlock()
 226 }
 227
 228 // RemoveNode removes the provided node from the block index.  There is no check
 229 // whether another node in the index depends on this one, so it is up to caller
 230 // to avoid that situation.
 231 //
 232 // This function is safe for concurrent access.
 233 func (bi *blockIndex) RemoveNode(node *blockNode) {
 234         bi.Lock()
 235         delete(bi.index, node.hash)
 236         bi.Unlock()
 237 }