forked from ledgerwatch/erigon
/
state_recon.go
216 lines (190 loc) · 5.36 KB
/
state_recon.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
205
206
207
208
209
210
211
212
213
214
215
216
/*
Copyright 2022 Erigon contributors
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/
package state
import (
"bytes"
"encoding/binary"
"github.com/tenderly/erigon/erigon-lib/compress"
"github.com/tenderly/erigon/erigon-lib/recsplit"
"github.com/tenderly/erigon/erigon-lib/recsplit/eliasfano32"
)
// Algorithms for reconstituting the state from state history
type ReconItem struct {
g *compress.Getter
key []byte
txNum uint64
startTxNum uint64
endTxNum uint64
startOffset uint64
lastOffset uint64
}
type ReconHeap []*ReconItem
func (rh ReconHeap) Len() int {
return len(rh)
}
// Less (part of heap.Interface) compares two links. For persisted links, those with the lower block heights get evicted first. This means that more recently persisted links are preferred.
// For non-persisted links, those with the highest block heights get evicted first. This is to prevent "holes" in the block heights that may cause inability to
// insert headers in the ascending order of their block heights.
func (rh ReconHeap) Less(i, j int) bool {
c := bytes.Compare(rh[i].key, rh[j].key)
if c == 0 {
return rh[i].txNum < rh[j].txNum
}
return c < 0
}
// Swap (part of heap.Interface) moves two links in the queue into each other's places. Note that each link has idx attribute that is getting adjusted during
// the swap. The idx attribute allows the removal of links from the middle of the queue (in case if links are getting invalidated due to
// failed verification of unavailability of parent headers)
func (rh ReconHeap) Swap(i, j int) {
rh[i], rh[j] = rh[j], rh[i]
}
// Push (part of heap.Interface) places a new link onto the end of queue. Note that idx attribute is set to the correct position of the new link
func (rh *ReconHeap) Push(x interface{}) {
// Push and Pop use pointer receivers because they modify the slice's length,
// not just its contents.
l := x.(*ReconItem)
*rh = append(*rh, l)
}
// Pop (part of heap.Interface) removes the first link from the queue
func (rh *ReconHeap) Pop() interface{} {
old := *rh
n := len(old)
x := old[n-1]
old[n-1] = nil
*rh = old[0 : n-1]
return x
}
type ReconHeapOlderFirst struct {
ReconHeap
}
func (rh ReconHeapOlderFirst) Less(i, j int) bool {
c := bytes.Compare(rh.ReconHeap[i].key, rh.ReconHeap[j].key)
if c == 0 {
return rh.ReconHeap[i].txNum >= rh.ReconHeap[j].txNum
}
return c < 0
}
type ScanIteratorInc struct {
g *compress.Getter
key []byte
nextTxNum uint64
hasNext bool
}
func (sii *ScanIteratorInc) advance() {
if !sii.hasNext {
return
}
if sii.key == nil {
sii.hasNext = false
return
}
val, _ := sii.g.NextUncompressed()
max := eliasfano32.Max(val)
sii.nextTxNum = max
if sii.g.HasNext() {
sii.key, _ = sii.g.NextUncompressed()
} else {
sii.key = nil
}
}
func (sii *ScanIteratorInc) HasNext() bool {
return sii.hasNext
}
func (sii *ScanIteratorInc) Next() (uint64, error) {
n := sii.nextTxNum
sii.advance()
return n, nil
}
func (hs *HistoryStep) iterateTxs() *ScanIteratorInc {
var sii ScanIteratorInc
sii.g = hs.indexFile.getter
sii.g.Reset(0)
if sii.g.HasNext() {
sii.key, _ = sii.g.NextUncompressed()
sii.hasNext = true
} else {
sii.hasNext = false
}
sii.advance()
return &sii
}
type HistoryIteratorInc struct {
uptoTxNum uint64
indexG *compress.Getter
historyG *compress.Getter
r *recsplit.IndexReader
key []byte
nextKey []byte
nextVal []byte
hasNext bool
compressVals bool
}
func (hs *HistoryStep) interateHistoryBeforeTxNum(txNum uint64) *HistoryIteratorInc {
var hii HistoryIteratorInc
hii.indexG = hs.indexFile.getter
hii.historyG = hs.historyFile.getter
hii.r = hs.historyFile.reader
hii.compressVals = hs.compressVals
hii.indexG.Reset(0)
if hii.indexG.HasNext() {
hii.key, _ = hii.indexG.NextUncompressed()
hii.uptoTxNum = txNum
hii.hasNext = true
} else {
hii.hasNext = false
}
hii.advance()
return &hii
}
func (hii *HistoryIteratorInc) advance() {
if !hii.hasNext {
return
}
if hii.key == nil {
hii.hasNext = false
return
}
hii.nextKey = nil
for hii.nextKey == nil && hii.key != nil {
val, _ := hii.indexG.NextUncompressed()
ef, _ := eliasfano32.ReadEliasFano(val)
if n, ok := ef.Search(hii.uptoTxNum); ok {
var txKey [8]byte
binary.BigEndian.PutUint64(txKey[:], n)
offset := hii.r.Lookup2(txKey[:], hii.key)
hii.historyG.Reset(offset)
hii.nextKey = hii.key
if hii.compressVals {
hii.nextVal, _ = hii.historyG.Next(nil)
} else {
hii.nextVal, _ = hii.historyG.NextUncompressed()
}
}
if hii.indexG.HasNext() {
hii.key, _ = hii.indexG.NextUncompressed()
} else {
hii.key = nil
}
}
if hii.nextKey == nil {
hii.hasNext = false
}
}
func (hii *HistoryIteratorInc) HasNext() bool {
return hii.hasNext
}
func (hii *HistoryIteratorInc) Next() ([]byte, []byte, error) {
k, v := hii.nextKey, hii.nextVal
hii.advance()
return k, v, nil
}