+++ /dev/null
-// Copyright (c) 2017 The btcsuite developers
-// Use of this source code is governed by an ISC
-// license that can be found in the LICENSE file.
-
-package blockchain
-
-import (
- "sync"
-)
-
-// approxNodesPerWeek is an approximation of the number of new blocks there are
-// in a week on average.
-const approxNodesPerWeek = 6 * 24 * 7
-
-// log2FloorMasks defines the masks to use when quickly calculating
-// floor(log2(x)) in a constant log2(32) = 5 steps, where x is a uint32, using
-// shifts. They are derived from (2^(2^x) - 1) * (2^(2^x)), for x in 4..0.
-var log2FloorMasks = []uint32{0xffff0000, 0xff00, 0xf0, 0xc, 0x2}
-
-// fastLog2Floor calculates and returns floor(log2(x)) in a constant 5 steps.
-func fastLog2Floor(n uint32) uint8 {
- rv := uint8(0)
- exponent := uint8(16)
- for i := 0; i < 5; i++ {
- if n&log2FloorMasks[i] != 0 {
- rv += exponent
- n >>= exponent
- }
- exponent >>= 1
- }
- return rv
-}
-
-// chainView provides a flat view of a specific branch of the block chain from
-// its tip back to the genesis block and provides various convenience functions
-// for comparing chains.
-//
-// For example, assume a block chain with a side chain as depicted below:
-// genesis -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
-// \-> 4a -> 5a -> 6a
-//
-// The chain view for the branch ending in 6a consists of:
-// genesis -> 1 -> 2 -> 3 -> 4a -> 5a -> 6a
-type chainView struct {
- mtx sync.Mutex
- nodes []*blockNode
-}
-
-// newChainView returns a new chain view for the given tip block node. Passing
-// nil as the tip will result in a chain view that is not initialized. The tip
-// can be updated at any time via the setTip function.
-func newChainView(tip *blockNode) *chainView {
- // The mutex is intentionally not held since this is a constructor.
- var c chainView
- c.setTip(tip)
- return &c
-}
-
-// genesis returns the genesis block for the chain view. This only differs from
-// the exported version in that it is up to the caller to ensure the lock is
-// held.
-//
-// This function MUST be called with the view mutex locked (for reads).
-func (c *chainView) genesis() *blockNode {
- if len(c.nodes) == 0 {
- return nil
- }
-
- return c.nodes[0]
-}
-
-// Genesis returns the genesis block for the chain view.
-//
-// This function is safe for concurrent access.
-func (c *chainView) Genesis() *blockNode {
- c.mtx.Lock()
- genesis := c.genesis()
- c.mtx.Unlock()
- return genesis
-}
-
-// tip returns the current tip block node for the chain view. It will return
-// nil if there is no tip. This only differs from the exported version in that
-// it is up to the caller to ensure the lock is held.
-//
-// This function MUST be called with the view mutex locked (for reads).
-func (c *chainView) tip() *blockNode {
- if len(c.nodes) == 0 {
- return nil
- }
-
- return c.nodes[len(c.nodes)-1]
-}
-
-// Tip returns the current tip block node for the chain view. It will return
-// nil if there is no tip.
-//
-// This function is safe for concurrent access.
-func (c *chainView) Tip() *blockNode {
- c.mtx.Lock()
- tip := c.tip()
- c.mtx.Unlock()
- return tip
-}
-
-// setTip sets the chain view to use the provided block node as the current tip
-// and ensures the view is consistent by populating it with the nodes obtained
-// by walking backwards all the way to genesis block as necessary. Further
-// calls will only perform the minimum work needed, so switching between chain
-// tips is efficient. This only differs from the exported version in that it is
-// up to the caller to ensure the lock is held.
-//
-// This function MUST be called with the view mutex locked (for writes).
-func (c *chainView) setTip(node *blockNode) {
- if node == nil {
- // Keep the backing array around for potential future use.
- c.nodes = c.nodes[:0]
- return
- }
-
- // Create or resize the slice that will hold the block nodes to the
- // provided tip height. When creating the slice, it is created with
- // some additional capacity for the underlying array as append would do
- // in order to reduce overhead when extending the chain later. As long
- // as the underlying array already has enough capacity, simply expand or
- // contract the slice accordingly. The additional capacity is chosen
- // such that the array should only have to be extended about once a
- // week.
- needed := node.height + 1
- if int32(cap(c.nodes)) < needed {
- nodes := make([]*blockNode, needed, needed+approxNodesPerWeek)
- copy(nodes, c.nodes)
- c.nodes = nodes
- } else {
- prevLen := int32(len(c.nodes))
- c.nodes = c.nodes[0:needed]
- for i := prevLen; i < needed; i++ {
- c.nodes[i] = nil
- }
- }
-
- for node != nil && c.nodes[node.height] != node {
- c.nodes[node.height] = node
- node = node.parent
- }
-}
-
-// SetTip sets the chain view to use the provided block node as the current tip
-// and ensures the view is consistent by populating it with the nodes obtained
-// by walking backwards all the way to genesis block as necessary. Further
-// calls will only perform the minimum work needed, so switching between chain
-// tips is efficient.
-//
-// This function is safe for concurrent access.
-func (c *chainView) SetTip(node *blockNode) {
- c.mtx.Lock()
- c.setTip(node)
- c.mtx.Unlock()
-}
-
-// height returns the height of the tip of the chain view. It will return -1 if
-// there is no tip (which only happens if the chain view has not been
-// initialized). This only differs from the exported version in that it is up
-// to the caller to ensure the lock is held.
-//
-// This function MUST be called with the view mutex locked (for reads).
-func (c *chainView) height() int32 {
- return int32(len(c.nodes) - 1)
-}
-
-// Height returns the height of the tip of the chain view. It will return -1 if
-// there is no tip (which only happens if the chain view has not been
-// initialized).
-//
-// This function is safe for concurrent access.
-func (c *chainView) Height() int32 {
- c.mtx.Lock()
- height := c.height()
- c.mtx.Unlock()
- return height
-}
-
-// nodeByHeight returns the block node at the specified height. Nil will be
-// returned if the height does not exist. This only differs from the exported
-// version in that it is up to the caller to ensure the lock is held.
-//
-// This function MUST be called with the view mutex locked (for reads).
-func (c *chainView) nodeByHeight(height int32) *blockNode {
- if height < 0 || height >= int32(len(c.nodes)) {
- return nil
- }
-
- return c.nodes[height]
-}
-
-// NodeByHeight returns the block node at the specified height. Nil will be
-// returned if the height does not exist.
-//
-// This function is safe for concurrent access.
-func (c *chainView) NodeByHeight(height int32) *blockNode {
- c.mtx.Lock()
- node := c.nodeByHeight(height)
- c.mtx.Unlock()
- return node
-}
-
-// Equals returns whether or not two chain views are the same. Uninitialized
-// views (tip set to nil) are considered equal.
-//
-// This function is safe for concurrent access.
-func (c *chainView) Equals(other *chainView) bool {
- c.mtx.Lock()
- other.mtx.Lock()
- equals := len(c.nodes) == len(other.nodes) && c.tip() == other.tip()
- other.mtx.Unlock()
- c.mtx.Unlock()
- return equals
-}
-
-// contains returns whether or not the chain view contains the passed block
-// node. This only differs from the exported version in that it is up to the
-// caller to ensure the lock is held.
-//
-// This function MUST be called with the view mutex locked (for reads).
-func (c *chainView) contains(node *blockNode) bool {
- return c.nodeByHeight(node.height) == node
-}
-
-// Contains returns whether or not the chain view contains the passed block
-// node.
-//
-// This function is safe for concurrent access.
-func (c *chainView) Contains(node *blockNode) bool {
- c.mtx.Lock()
- contains := c.contains(node)
- c.mtx.Unlock()
- return contains
-}
-
-// next returns the successor to the provided node for the chain view. It will
-// return nil if there is no successor or the provided node is not part of the
-// view. This only differs from the exported version in that it is up to the
-// caller to ensure the lock is held.
-//
-// See the comment on the exported function for more details.
-//
-// This function MUST be called with the view mutex locked (for reads).
-func (c *chainView) next(node *blockNode) *blockNode {
- if node == nil || !c.contains(node) {
- return nil
- }
-
- return c.nodeByHeight(node.height + 1)
-}
-
-// Next returns the successor to the provided node for the chain view. It will
-// return nil if there is no successfor or the provided node is not part of the
-// view.
-//
-// For example, assume a block chain with a side chain as depicted below:
-// genesis -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
-// \-> 4a -> 5a -> 6a
-//
-// Further, assume the view is for the longer chain depicted above. That is to
-// say it consists of:
-// genesis -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
-//
-// Invoking this function with block node 5 would return block node 6 while
-// invoking it with block node 5a would return nil since that node is not part
-// of the view.
-//
-// This function is safe for concurrent access.
-func (c *chainView) Next(node *blockNode) *blockNode {
- c.mtx.Lock()
- next := c.next(node)
- c.mtx.Unlock()
- return next
-}
-
-// findFork returns the final common block between the provided node and the
-// the chain view. It will return nil if there is no common block. This only
-// differs from the exported version in that it is up to the caller to ensure
-// the lock is held.
-//
-// See the exported FindFork comments for more details.
-//
-// This function MUST be called with the view mutex locked (for reads).
-func (c *chainView) findFork(node *blockNode) *blockNode {
- // No fork point for node that doesn't exist.
- if node == nil {
- return nil
- }
-
- // When the height of the passed node is higher than the height of the
- // tip of the current chain view, walk backwards through the nodes of
- // the other chain until the heights match (or there or no more nodes in
- // which case there is no common node between the two).
- //
- // NOTE: This isn't strictly necessary as the following section will
- // find the node as well, however, it is more efficient to avoid the
- // contains check since it is already known that the common node can't
- // possibly be past the end of the current chain view. It also allows
- // this code to take advantage of any potential future optimizations to
- // the Ancestor function such as using an O(log n) skip list.
- chainHeight := c.height()
- if node.height > chainHeight {
- node = node.Ancestor(chainHeight)
- }
-
- // Walk the other chain backwards as long as the current one does not
- // contain the node or there are no more nodes in which case there is no
- // common node between the two.
- for node != nil && !c.contains(node) {
- node = node.parent
- }
-
- return node
-}
-
-// FindFork returns the final common block between the provided node and the
-// the chain view. It will return nil if there is no common block.
-//
-// For example, assume a block chain with a side chain as depicted below:
-// genesis -> 1 -> 2 -> ... -> 5 -> 6 -> 7 -> 8
-// \-> 6a -> 7a
-//
-// Further, assume the view is for the longer chain depicted above. That is to
-// say it consists of:
-// genesis -> 1 -> 2 -> ... -> 5 -> 6 -> 7 -> 8.
-//
-// Invoking this function with block node 7a would return block node 5 while
-// invoking it with block node 7 would return itself since it is already part of
-// the branch formed by the view.
-//
-// This function is safe for concurrent access.
-func (c *chainView) FindFork(node *blockNode) *blockNode {
- c.mtx.Lock()
- fork := c.findFork(node)
- c.mtx.Unlock()
- return fork
-}
-
-// blockLocator returns a block locator for the passed block node. The passed
-// node can be nil in which case the block locator for the current tip
-// associated with the view will be returned. This only differs from the
-// exported version in that it is up to the caller to ensure the lock is held.
-//
-// See the exported BlockLocator function comments for more details.
-//
-// This function MUST be called with the view mutex locked (for reads).
-func (c *chainView) blockLocator(node *blockNode) BlockLocator {
- // Use the current tip if requested.
- if node == nil {
- node = c.tip()
- }
- if node == nil {
- return nil
- }
-
- // Calculate the max number of entries that will ultimately be in the
- // block locator. See the description of the algorithm for how these
- // numbers are derived.
- var maxEntries uint8
- if node.height <= 12 {
- maxEntries = uint8(node.height) + 1
- } else {
- // Requested hash itself + previous 10 entries + genesis block.
- // Then floor(log2(height-10)) entries for the skip portion.
- adjustedHeight := uint32(node.height) - 10
- maxEntries = 12 + fastLog2Floor(adjustedHeight)
- }
- locator := make(BlockLocator, 0, maxEntries)
-
- step := int32(1)
- for node != nil {
- locator = append(locator, &node.hash)
-
- // Nothing more to add once the genesis block has been added.
- if node.height == 0 {
- break
- }
-
- // Calculate height of previous node to include ensuring the
- // final node is the genesis block.
- height := node.height - step
- if height < 0 {
- height = 0
- }
-
- // When the node is in the current chain view, all of its
- // ancestors must be too, so use a much faster O(1) lookup in
- // that case. Otherwise, fall back to walking backwards through
- // the nodes of the other chain to the correct ancestor.
- if c.contains(node) {
- node = c.nodes[height]
- } else {
- node = node.Ancestor(height)
- }
-
- // Once 11 entries have been included, start doubling the
- // distance between included hashes.
- if len(locator) > 10 {
- step *= 2
- }
- }
-
- return locator
-}
-
-// BlockLocator returns a block locator for the passed block node. The passed
-// node can be nil in which case the block locator for the current tip
-// associated with the view will be returned.
-//
-// See the BlockLocator type for details on the algorithm used to create a block
-// locator.
-//
-// This function is safe for concurrent access.
-func (c *chainView) BlockLocator(node *blockNode) BlockLocator {
- c.mtx.Lock()
- locator := c.blockLocator(node)
- c.mtx.Unlock()
- return locator
-}
OSDN Git Service
