cubefs

1
/**
2
 * A thread-safe tree which caches inverted matrices.
3
 *
4
 * Copyright 2016, Peter Collins
5
 */
6

7
package reedsolomon
8

9
import (
10
	"errors"
11
	"sync"
12
)
13

14
// The tree uses a Reader-Writer mutex to make it thread-safe
15
// when accessing cached matrices and inserting new ones.
16
type inversionTree struct {
17
	mutex sync.RWMutex
18
	root  inversionNode
19
}
20

21
type inversionNode struct {
22
	matrix   matrix
23
	children []*inversionNode
24
}
25

26
// newInversionTree initializes a tree for storing inverted matrices.
27
// Note that the root node is the identity matrix as it implies
28
// there were no errors with the original data.
29
func newInversionTree(dataShards, parityShards int) *inversionTree {
30
	identity, _ := identityMatrix(dataShards)
31
	return &inversionTree{
32
		root: inversionNode{
33
			matrix:   identity,
34
			children: make([]*inversionNode, dataShards+parityShards),
35
		},
36
	}
37
}
38

39
// GetInvertedMatrix returns the cached inverted matrix or nil if it
40
// is not found in the tree keyed on the indices of invalid rows.
41
func (t *inversionTree) GetInvertedMatrix(invalidIndices []int) matrix {
42
	if t == nil {
43
		return nil
44
	}
45
	// Lock the tree for reading before accessing the tree.
46
	t.mutex.RLock()
47
	defer t.mutex.RUnlock()
48

49
	// If no invalid indices were give we should return the root
50
	// identity matrix.
51
	if len(invalidIndices) == 0 {
52
		return t.root.matrix
53
	}
54

55
	// Recursively search for the inverted matrix in the tree, passing in
56
	// 0 as the parent index as we start at the root of the tree.
57
	return t.root.getInvertedMatrix(invalidIndices, 0)
58
}
59

60
// errAlreadySet is returned if the root node matrix is overwritten
61
var errAlreadySet = errors.New("the root node identity matrix is already set")
62

63
// InsertInvertedMatrix inserts a new inverted matrix into the tree
64
// keyed by the indices of invalid rows.  The total number of shards
65
// is required for creating the proper length lists of child nodes for
66
// each node.
67
func (t *inversionTree) InsertInvertedMatrix(invalidIndices []int, matrix matrix, shards int) error {
68
	if t == nil {
69
		return nil
70
	}
71
	// If no invalid indices were given then we are done because the
72
	// root node is already set with the identity matrix.
73
	if len(invalidIndices) == 0 {
74
		return errAlreadySet
75
	}
76

77
	if !matrix.IsSquare() {
78
		return errNotSquare
79
	}
80

81
	// Lock the tree for writing and reading before accessing the tree.
82
	t.mutex.Lock()
83
	defer t.mutex.Unlock()
84

85
	// Recursively create nodes for the inverted matrix in the tree until
86
	// we reach the node to insert the matrix to.  We start by passing in
87
	// 0 as the parent index as we start at the root of the tree.
88
	t.root.insertInvertedMatrix(invalidIndices, matrix, shards, 0)
89

90
	return nil
91
}
92

93
func (n *inversionNode) getInvertedMatrix(invalidIndices []int, parent int) matrix {
94
	// Get the child node to search next from the list of children.  The
95
	// list of children starts relative to the parent index passed in
96
	// because the indices of invalid rows is sorted (by default).  As we
97
	// search recursively, the first invalid index gets popped off the list,
98
	// so when searching through the list of children, use that first invalid
99
	// index to find the child node.
100
	firstIndex := invalidIndices[0]
101
	node := n.children[firstIndex-parent]
102

103
	// If the child node doesn't exist in the list yet, fail fast by
104
	// returning, so we can construct and insert the proper inverted matrix.
105
	if node == nil {
106
		return nil
107
	}
108

109
	// If there's more than one invalid index left in the list we should
110
	// keep searching recursively.
111
	if len(invalidIndices) > 1 {
112
		// Search recursively on the child node by passing in the invalid indices
113
		// with the first index popped off the front.  Also the parent index to
114
		// pass down is the first index plus one.
115
		return node.getInvertedMatrix(invalidIndices[1:], firstIndex+1)
116
	}
117
	// If there aren't any more invalid indices to search, we've found our
118
	// node.  Return it, however keep in mind that the matrix could still be
119
	// nil because intermediary nodes in the tree are created sometimes with
120
	// their inversion matrices uninitialized.
121
	return node.matrix
122
}
123

124
func (n *inversionNode) insertInvertedMatrix(invalidIndices []int, matrix matrix, shards, parent int) {
125
	// As above, get the child node to search next from the list of children.
126
	// The list of children starts relative to the parent index passed in
127
	// because the indices of invalid rows is sorted (by default).  As we
128
	// search recursively, the first invalid index gets popped off the list,
129
	// so when searching through the list of children, use that first invalid
130
	// index to find the child node.
131
	firstIndex := invalidIndices[0]
132
	node := n.children[firstIndex-parent]
133

134
	// If the child node doesn't exist in the list yet, create a new
135
	// node because we have the writer lock and add it to the list
136
	// of children.
137
	if node == nil {
138
		// Make the length of the list of children equal to the number
139
		// of shards minus the first invalid index because the list of
140
		// invalid indices is sorted, so only this length of errors
141
		// are possible in the tree.
142
		node = &inversionNode{
143
			children: make([]*inversionNode, shards-firstIndex),
144
		}
145
		// Insert the new node into the tree at the first index relative
146
		// to the parent index that was given in this recursive call.
147
		n.children[firstIndex-parent] = node
148
	}
149

150
	// If there's more than one invalid index left in the list we should
151
	// keep searching recursively in order to find the node to add our
152
	// matrix.
153
	if len(invalidIndices) > 1 {
154
		// As above, search recursively on the child node by passing in
155
		// the invalid indices with the first index popped off the front.
156
		// Also the total number of shards and parent index are passed down
157
		// which is equal to the first index plus one.
158
		node.insertInvertedMatrix(invalidIndices[1:], matrix, shards, firstIndex+1)
159
	} else {
160
		// If there aren't any more invalid indices to search, we've found our
161
		// node.  Cache the inverted matrix in this node.
162
		node.matrix = matrix
163
	}
164
}
165