-
Notifications
You must be signed in to change notification settings - Fork 0
/
orphans.go
205 lines (173 loc) · 6.32 KB
/
orphans.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
package flowcontext
import (
"github.com/karlsend/PYVERT/testfork/karlsend/domain/consensus/model/externalapi"
"github.com/karlsend/PYVERT/testfork/karlsend/domain/consensus/ruleerrors"
"github.com/karlsend/PYVERT/testfork/karlsend/domain/consensus/utils/consensushashing"
"github.com/karlsend/PYVERT/testfork/karlsend/domain/consensus/utils/hashset"
"github.com/karlsend/PYVERT/testfork/karlsend/infrastructure/logger"
"github.com/pkg/errors"
)
// maxOrphans is the maximum amount of orphans allowed in the
// orphans collection. This number is an approximation of how
// many orphans there can possibly be on average. It is based
// on: 2^orphanResolutionRange * PHANTOM K.
const maxOrphans = 600
// AddOrphan adds the block to the orphan set
func (f *FlowContext) AddOrphan(orphanBlock *externalapi.DomainBlock) {
f.orphansMutex.Lock()
defer f.orphansMutex.Unlock()
orphanHash := consensushashing.BlockHash(orphanBlock)
f.orphans[*orphanHash] = orphanBlock
if len(f.orphans) > maxOrphans {
log.Debugf("Orphan collection size exceeded. Evicting a random orphan")
f.evictRandomOrphan()
}
log.Infof("Received a block with missing parents, adding to orphan pool: %s", orphanHash)
}
func (f *FlowContext) evictRandomOrphan() {
var toEvict externalapi.DomainHash
for hash := range f.orphans {
toEvict = hash
break
}
delete(f.orphans, toEvict)
log.Debugf("Evicted %s from the orphan collection", toEvict)
}
// IsOrphan returns whether the given blockHash belongs to an orphan block
func (f *FlowContext) IsOrphan(blockHash *externalapi.DomainHash) bool {
f.orphansMutex.RLock()
defer f.orphansMutex.RUnlock()
_, ok := f.orphans[*blockHash]
return ok
}
// UnorphanBlocks removes the block from the orphan set, and remove all of the blocks that are not orphans anymore.
func (f *FlowContext) UnorphanBlocks(rootBlock *externalapi.DomainBlock) ([]*externalapi.DomainBlock, error) {
f.orphansMutex.Lock()
defer f.orphansMutex.Unlock()
// Find all the children of rootBlock among the orphans
// and add them to the process queue
rootBlockHash := consensushashing.BlockHash(rootBlock)
processQueue := f.addChildOrphansToProcessQueue(rootBlockHash, []externalapi.DomainHash{})
var unorphanedBlocks []*externalapi.DomainBlock
for len(processQueue) > 0 {
var orphanHash externalapi.DomainHash
orphanHash, processQueue = processQueue[0], processQueue[1:]
orphanBlock := f.orphans[orphanHash]
log.Debugf("Considering to unorphan block %s with parents %s",
orphanHash, orphanBlock.Header.DirectParents())
canBeUnorphaned := true
for _, orphanBlockParentHash := range orphanBlock.Header.DirectParents() {
orphanBlockParentInfo, err := f.domain.Consensus().GetBlockInfo(orphanBlockParentHash)
if err != nil {
return nil, err
}
if !orphanBlockParentInfo.Exists || orphanBlockParentInfo.BlockStatus == externalapi.StatusHeaderOnly {
log.Debugf("Cannot unorphan block %s. It's missing at "+
"least the following parent: %s", orphanHash, orphanBlockParentHash)
canBeUnorphaned = false
break
}
}
if canBeUnorphaned {
unorphaningSucceeded, err := f.unorphanBlock(orphanHash)
if err != nil {
return nil, err
}
if unorphaningSucceeded {
unorphanedBlocks = append(unorphanedBlocks, orphanBlock)
processQueue = f.addChildOrphansToProcessQueue(&orphanHash, processQueue)
}
}
}
return unorphanedBlocks, nil
}
// addChildOrphansToProcessQueue finds all child orphans of `blockHash`
// and adds them to the given `processQueue` if they don't already exist
// inside of it
// Note that this method does not modify the given `processQueue`
func (f *FlowContext) addChildOrphansToProcessQueue(blockHash *externalapi.DomainHash,
processQueue []externalapi.DomainHash) []externalapi.DomainHash {
blockChildren := f.findChildOrphansOfBlock(blockHash)
for _, blockChild := range blockChildren {
exists := false
for _, queueOrphan := range processQueue {
if queueOrphan == blockChild {
exists = true
break
}
}
if !exists {
processQueue = append(processQueue, blockChild)
}
}
return processQueue
}
func (f *FlowContext) findChildOrphansOfBlock(blockHash *externalapi.DomainHash) []externalapi.DomainHash {
var childOrphans []externalapi.DomainHash
for orphanHash, orphanBlock := range f.orphans {
for _, orphanBlockParentHash := range orphanBlock.Header.DirectParents() {
if orphanBlockParentHash.Equal(blockHash) {
childOrphans = append(childOrphans, orphanHash)
break
}
}
}
return childOrphans
}
func (f *FlowContext) unorphanBlock(orphanHash externalapi.DomainHash) (bool, error) {
orphanBlock, ok := f.orphans[orphanHash]
if !ok {
return false, errors.Errorf("attempted to unorphan a non-orphan block %s", orphanHash)
}
delete(f.orphans, orphanHash)
err := f.domain.Consensus().ValidateAndInsertBlock(orphanBlock, true)
if err != nil {
if errors.As(err, &ruleerrors.RuleError{}) {
log.Warnf("Validation failed for orphan block %s: %s", orphanHash, err)
return false, nil
}
return false, err
}
log.Infof("Unorphaned block %s", orphanHash)
return true, nil
}
// GetOrphanRoots returns the roots of the missing ancestors DAG of the given orphan
func (f *FlowContext) GetOrphanRoots(orphan *externalapi.DomainHash) ([]*externalapi.DomainHash, bool, error) {
onEnd := logger.LogAndMeasureExecutionTime(log, "GetOrphanRoots")
defer onEnd()
f.orphansMutex.RLock()
defer f.orphansMutex.RUnlock()
_, ok := f.orphans[*orphan]
if !ok {
return nil, false, nil
}
queue := []*externalapi.DomainHash{orphan}
addedToQueueSet := hashset.New()
addedToQueueSet.Add(orphan)
roots := []*externalapi.DomainHash{}
for len(queue) > 0 {
var current *externalapi.DomainHash
current, queue = queue[0], queue[1:]
block, ok := f.orphans[*current]
if !ok {
blockInfo, err := f.domain.Consensus().GetBlockInfo(current)
if err != nil {
return nil, false, err
}
if !blockInfo.Exists || blockInfo.BlockStatus == externalapi.StatusHeaderOnly {
roots = append(roots, current)
} else {
log.Debugf("Block %s was skipped when checking for orphan roots: "+
"exists: %t, status: %s", current, blockInfo.Exists, blockInfo.BlockStatus)
}
continue
}
for _, parent := range block.Header.DirectParents() {
if !addedToQueueSet.Contains(parent) {
queue = append(queue, parent)
addedToQueueSet.Add(parent)
}
}
}
return roots, true, nil
}