1 // Copyright (c) 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.
11 // approxNodesPerWeek is an approximation of the number of new blocks there are
12 // in a week on average.
13 const approxNodesPerWeek = 6 * 24 * 7
15 // log2FloorMasks defines the masks to use when quickly calculating
16 // floor(log2(x)) in a constant log2(32) = 5 steps, where x is a uint32, using
17 // shifts. They are derived from (2^(2^x) - 1) * (2^(2^x)), for x in 4..0.
18 var log2FloorMasks = []uint32{0xffff0000, 0xff00, 0xf0, 0xc, 0x2}
20 // fastLog2Floor calculates and returns floor(log2(x)) in a constant 5 steps.
21 func fastLog2Floor(n uint32) uint8 {
24 for i := 0; i < 5; i++ {
25 if n&log2FloorMasks[i] != 0 {
34 // chainView provides a flat view of a specific branch of the block chain from
35 // its tip back to the genesis block and provides various convenience functions
36 // for comparing chains.
38 // For example, assume a block chain with a side chain as depicted below:
39 // genesis -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
42 // The chain view for the branch ending in 6a consists of:
43 // genesis -> 1 -> 2 -> 3 -> 4a -> 5a -> 6a
44 type chainView struct {
49 // newChainView returns a new chain view for the given tip block node. Passing
50 // nil as the tip will result in a chain view that is not initialized. The tip
51 // can be updated at any time via the setTip function.
52 func newChainView(tip *blockNode) *chainView {
53 // The mutex is intentionally not held since this is a constructor.
59 // genesis returns the genesis block for the chain view. This only differs from
60 // the exported version in that it is up to the caller to ensure the lock is
63 // This function MUST be called with the view mutex locked (for reads).
64 func (c *chainView) genesis() *blockNode {
65 if len(c.nodes) == 0 {
72 // Genesis returns the genesis block for the chain view.
74 // This function is safe for concurrent access.
75 func (c *chainView) Genesis() *blockNode {
77 genesis := c.genesis()
82 // tip returns the current tip block node for the chain view. It will return
83 // nil if there is no tip. This only differs from the exported version in that
84 // it is up to the caller to ensure the lock is held.
86 // This function MUST be called with the view mutex locked (for reads).
87 func (c *chainView) tip() *blockNode {
88 if len(c.nodes) == 0 {
92 return c.nodes[len(c.nodes)-1]
95 // Tip returns the current tip block node for the chain view. It will return
96 // nil if there is no tip.
98 // This function is safe for concurrent access.
99 func (c *chainView) Tip() *blockNode {
106 // setTip sets the chain view to use the provided block node as the current tip
107 // and ensures the view is consistent by populating it with the nodes obtained
108 // by walking backwards all the way to genesis block as necessary. Further
109 // calls will only perform the minimum work needed, so switching between chain
110 // tips is efficient. This only differs from the exported version in that it is
111 // up to the caller to ensure the lock is held.
113 // This function MUST be called with the view mutex locked (for writes).
114 func (c *chainView) setTip(node *blockNode) {
116 // Keep the backing array around for potential future use.
117 c.nodes = c.nodes[:0]
121 // Create or resize the slice that will hold the block nodes to the
122 // provided tip height. When creating the slice, it is created with
123 // some additional capacity for the underlying array as append would do
124 // in order to reduce overhead when extending the chain later. As long
125 // as the underlying array already has enough capacity, simply expand or
126 // contract the slice accordingly. The additional capacity is chosen
127 // such that the array should only have to be extended about once a
129 needed := node.height + 1
130 if int32(cap(c.nodes)) < needed {
131 nodes := make([]*blockNode, needed, needed+approxNodesPerWeek)
135 prevLen := int32(len(c.nodes))
136 c.nodes = c.nodes[0:needed]
137 for i := prevLen; i < needed; i++ {
142 for node != nil && c.nodes[node.height] != node {
143 c.nodes[node.height] = node
148 // SetTip sets the chain view to use the provided block node as the current tip
149 // and ensures the view is consistent by populating it with the nodes obtained
150 // by walking backwards all the way to genesis block as necessary. Further
151 // calls will only perform the minimum work needed, so switching between chain
152 // tips is efficient.
154 // This function is safe for concurrent access.
155 func (c *chainView) SetTip(node *blockNode) {
161 // height returns the height of the tip of the chain view. It will return -1 if
162 // there is no tip (which only happens if the chain view has not been
163 // initialized). This only differs from the exported version in that it is up
164 // to the caller to ensure the lock is held.
166 // This function MUST be called with the view mutex locked (for reads).
167 func (c *chainView) height() int32 {
168 return int32(len(c.nodes) - 1)
171 // Height returns the height of the tip of the chain view. It will return -1 if
172 // there is no tip (which only happens if the chain view has not been
175 // This function is safe for concurrent access.
176 func (c *chainView) Height() int32 {
183 // nodeByHeight returns the block node at the specified height. Nil will be
184 // returned if the height does not exist. This only differs from the exported
185 // version in that it is up to the caller to ensure the lock is held.
187 // This function MUST be called with the view mutex locked (for reads).
188 func (c *chainView) nodeByHeight(height int32) *blockNode {
189 if height < 0 || height >= int32(len(c.nodes)) {
193 return c.nodes[height]
196 // NodeByHeight returns the block node at the specified height. Nil will be
197 // returned if the height does not exist.
199 // This function is safe for concurrent access.
200 func (c *chainView) NodeByHeight(height int32) *blockNode {
202 node := c.nodeByHeight(height)
207 // Equals returns whether or not two chain views are the same. Uninitialized
208 // views (tip set to nil) are considered equal.
210 // This function is safe for concurrent access.
211 func (c *chainView) Equals(other *chainView) bool {
214 equals := len(c.nodes) == len(other.nodes) && c.tip() == other.tip()
220 // contains returns whether or not the chain view contains the passed block
221 // node. This only differs from the exported version in that it is up to the
222 // caller to ensure the lock is held.
224 // This function MUST be called with the view mutex locked (for reads).
225 func (c *chainView) contains(node *blockNode) bool {
226 return c.nodeByHeight(node.height) == node
229 // Contains returns whether or not the chain view contains the passed block
232 // This function is safe for concurrent access.
233 func (c *chainView) Contains(node *blockNode) bool {
235 contains := c.contains(node)
240 // next returns the successor to the provided node for the chain view. It will
241 // return nil if there is no successor or the provided node is not part of the
242 // view. This only differs from the exported version in that it is up to the
243 // caller to ensure the lock is held.
245 // See the comment on the exported function for more details.
247 // This function MUST be called with the view mutex locked (for reads).
248 func (c *chainView) next(node *blockNode) *blockNode {
249 if node == nil || !c.contains(node) {
253 return c.nodeByHeight(node.height + 1)
256 // Next returns the successor to the provided node for the chain view. It will
257 // return nil if there is no successfor or the provided node is not part of the
260 // For example, assume a block chain with a side chain as depicted below:
261 // genesis -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
262 // \-> 4a -> 5a -> 6a
264 // Further, assume the view is for the longer chain depicted above. That is to
265 // say it consists of:
266 // genesis -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
268 // Invoking this function with block node 5 would return block node 6 while
269 // invoking it with block node 5a would return nil since that node is not part
272 // This function is safe for concurrent access.
273 func (c *chainView) Next(node *blockNode) *blockNode {
280 // findFork returns the final common block between the provided node and the
281 // the chain view. It will return nil if there is no common block. This only
282 // differs from the exported version in that it is up to the caller to ensure
285 // See the exported FindFork comments for more details.
287 // This function MUST be called with the view mutex locked (for reads).
288 func (c *chainView) findFork(node *blockNode) *blockNode {
289 // No fork point for node that doesn't exist.
294 // When the height of the passed node is higher than the height of the
295 // tip of the current chain view, walk backwards through the nodes of
296 // the other chain until the heights match (or there or no more nodes in
297 // which case there is no common node between the two).
299 // NOTE: This isn't strictly necessary as the following section will
300 // find the node as well, however, it is more efficient to avoid the
301 // contains check since it is already known that the common node can't
302 // possibly be past the end of the current chain view. It also allows
303 // this code to take advantage of any potential future optimizations to
304 // the Ancestor function such as using an O(log n) skip list.
305 chainHeight := c.height()
306 if node.height > chainHeight {
307 node = node.Ancestor(chainHeight)
310 // Walk the other chain backwards as long as the current one does not
311 // contain the node or there are no more nodes in which case there is no
312 // common node between the two.
313 for node != nil && !c.contains(node) {
320 // FindFork returns the final common block between the provided node and the
321 // the chain view. It will return nil if there is no common block.
323 // For example, assume a block chain with a side chain as depicted below:
324 // genesis -> 1 -> 2 -> ... -> 5 -> 6 -> 7 -> 8
327 // Further, assume the view is for the longer chain depicted above. That is to
328 // say it consists of:
329 // genesis -> 1 -> 2 -> ... -> 5 -> 6 -> 7 -> 8.
331 // Invoking this function with block node 7a would return block node 5 while
332 // invoking it with block node 7 would return itself since it is already part of
333 // the branch formed by the view.
335 // This function is safe for concurrent access.
336 func (c *chainView) FindFork(node *blockNode) *blockNode {
338 fork := c.findFork(node)
343 // blockLocator returns a block locator for the passed block node. The passed
344 // node can be nil in which case the block locator for the current tip
345 // associated with the view will be returned. This only differs from the
346 // exported version in that it is up to the caller to ensure the lock is held.
348 // See the exported BlockLocator function comments for more details.
350 // This function MUST be called with the view mutex locked (for reads).
351 func (c *chainView) blockLocator(node *blockNode) BlockLocator {
352 // Use the current tip if requested.
360 // Calculate the max number of entries that will ultimately be in the
361 // block locator. See the description of the algorithm for how these
362 // numbers are derived.
364 if node.height <= 12 {
365 maxEntries = uint8(node.height) + 1
367 // Requested hash itself + previous 10 entries + genesis block.
368 // Then floor(log2(height-10)) entries for the skip portion.
369 adjustedHeight := uint32(node.height) - 10
370 maxEntries = 12 + fastLog2Floor(adjustedHeight)
372 locator := make(BlockLocator, 0, maxEntries)
376 locator = append(locator, &node.hash)
378 // Nothing more to add once the genesis block has been added.
379 if node.height == 0 {
383 // Calculate height of previous node to include ensuring the
384 // final node is the genesis block.
385 height := node.height - step
390 // When the node is in the current chain view, all of its
391 // ancestors must be too, so use a much faster O(1) lookup in
392 // that case. Otherwise, fall back to walking backwards through
393 // the nodes of the other chain to the correct ancestor.
394 if c.contains(node) {
395 node = c.nodes[height]
397 node = node.Ancestor(height)
400 // Once 11 entries have been included, start doubling the
401 // distance between included hashes.
402 if len(locator) > 10 {
410 // BlockLocator returns a block locator for the passed block node. The passed
411 // node can be nil in which case the block locator for the current tip
412 // associated with the view will be returned.
414 // See the BlockLocator type for details on the algorithm used to create a block
417 // This function is safe for concurrent access.
418 func (c *chainView) BlockLocator(node *blockNode) BlockLocator {
420 locator := c.blockLocator(node)