-
Notifications
You must be signed in to change notification settings - Fork 1.3k
/
searchwait.go
353 lines (296 loc) · 10.9 KB
/
searchwait.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
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
package stmgr
import (
"context"
"errors"
"fmt"
"github.com/ipfs/go-cid"
"golang.org/x/xerrors"
"github.com/filecoin-project/go-state-types/abi"
"github.com/filecoin-project/lotus/chain/index"
"github.com/filecoin-project/lotus/chain/store"
"github.com/filecoin-project/lotus/chain/types"
)
// WaitForMessage blocks until a message appears on chain. It looks backwards in the chain to see if this has already
// happened, with an optional limit to how many epochs it will search. It guarantees that the message has been on
// chain for at least confidence epochs without being reverted before returning.
func (sm *StateManager) WaitForMessage(ctx context.Context, mcid cid.Cid, confidence uint64, lookbackLimit abi.ChainEpoch, allowReplaced bool) (*types.TipSet, *types.MessageReceipt, cid.Cid, error) {
// TODO use the index to speed this up.
ctx, cancel := context.WithCancel(ctx)
defer cancel()
msg, err := sm.cs.GetCMessage(ctx, mcid)
if err != nil {
return nil, nil, cid.Undef, fmt.Errorf("failed to load message: %w", err)
}
tsub := sm.cs.SubHeadChanges(ctx)
head, ok := <-tsub
if !ok {
return nil, nil, cid.Undef, fmt.Errorf("SubHeadChanges stream was invalid")
}
if len(head) != 1 {
return nil, nil, cid.Undef, fmt.Errorf("SubHeadChanges first entry should have been one item")
}
if head[0].Type != store.HCCurrent {
return nil, nil, cid.Undef, fmt.Errorf("expected current head on SHC stream (got %s)", head[0].Type)
}
r, foundMsg, err := sm.tipsetExecutedMessage(ctx, head[0].Val, mcid, msg.VMMessage(), allowReplaced)
if err != nil {
return nil, nil, cid.Undef, err
}
if r != nil {
return head[0].Val, r, foundMsg, nil
}
var backTs *types.TipSet
var backRcp *types.MessageReceipt
var backFm cid.Cid
backSearchWait := make(chan struct{})
go func() {
fts, r, foundMsg, err := sm.searchForIndexedMsg(ctx, mcid, msg)
found := (err == nil && r != nil && foundMsg.Defined())
if !found {
fts, r, foundMsg, err = sm.searchBackForMsg(ctx, head[0].Val, msg, lookbackLimit, allowReplaced)
if err != nil {
log.Warnf("failed to look back through chain for message: %v", err)
return
}
}
backTs = fts
backRcp = r
backFm = foundMsg
close(backSearchWait)
}()
var candidateTs *types.TipSet
var candidateRcp *types.MessageReceipt
var candidateFm cid.Cid
heightOfHead := head[0].Val.Height()
reverts := map[types.TipSetKey]bool{}
for {
select {
case notif, ok := <-tsub:
if !ok {
return nil, nil, cid.Undef, ctx.Err()
}
for _, val := range notif {
switch val.Type {
case store.HCRevert:
if val.Val.Equals(candidateTs) {
candidateTs = nil
candidateRcp = nil
candidateFm = cid.Undef
}
if backSearchWait != nil {
reverts[val.Val.Key()] = true
}
case store.HCApply:
if candidateTs != nil && val.Val.Height() >= candidateTs.Height()+abi.ChainEpoch(confidence) {
return candidateTs, candidateRcp, candidateFm, nil
}
r, foundMsg, err := sm.tipsetExecutedMessage(ctx, val.Val, mcid, msg.VMMessage(), allowReplaced)
if err != nil {
return nil, nil, cid.Undef, err
}
if r != nil {
if confidence == 0 {
return val.Val, r, foundMsg, err
}
candidateTs = val.Val
candidateRcp = r
candidateFm = foundMsg
}
heightOfHead = val.Val.Height()
}
}
case <-backSearchWait:
// check if we found the message in the chain and that is hasn't been reverted since we started searching
if backTs != nil && !reverts[backTs.Key()] {
// if head is at or past confidence interval, return immediately
if heightOfHead >= backTs.Height()+abi.ChainEpoch(confidence) {
return backTs, backRcp, backFm, nil
}
// wait for confidence interval
candidateTs = backTs
candidateRcp = backRcp
candidateFm = backFm
}
reverts = nil
backSearchWait = nil
case <-ctx.Done():
return nil, nil, cid.Undef, ctx.Err()
}
}
}
func (sm *StateManager) SearchForMessage(ctx context.Context, head *types.TipSet, mcid cid.Cid, lookbackLimit abi.ChainEpoch, allowReplaced bool) (*types.TipSet, *types.MessageReceipt, cid.Cid, error) {
msg, err := sm.cs.GetCMessage(ctx, mcid)
if err != nil {
return nil, nil, cid.Undef, fmt.Errorf("failed to load message: %w", err)
}
r, foundMsg, err := sm.tipsetExecutedMessage(ctx, head, mcid, msg.VMMessage(), allowReplaced)
if err != nil {
return nil, nil, cid.Undef, err
}
if r != nil {
return head, r, foundMsg, nil
}
fts, r, foundMsg, err := sm.searchForIndexedMsg(ctx, mcid, msg)
switch {
case err == nil:
if r != nil && foundMsg.Defined() {
return fts, r, foundMsg, nil
}
// debug log this, it's noteworthy
if r == nil {
log.Debugf("missing receipt for message in index for %s", mcid)
}
if !foundMsg.Defined() {
log.Debugf("message %s not found", mcid)
}
case errors.Is(err, index.ErrNotFound):
// ok for the index to have incomplete data
default:
log.Warnf("error searching message index: %s", err)
}
fts, r, foundMsg, err = sm.searchBackForMsg(ctx, head, msg, lookbackLimit, allowReplaced)
if err != nil {
log.Warnf("failed to look back through chain for message %s", mcid)
return nil, nil, cid.Undef, err
}
if fts == nil {
return nil, nil, cid.Undef, nil
}
return fts, r, foundMsg, nil
}
func (sm *StateManager) searchForIndexedMsg(ctx context.Context, mcid cid.Cid, m types.ChainMsg) (*types.TipSet, *types.MessageReceipt, cid.Cid, error) {
minfo, err := sm.msgIndex.GetMsgInfo(ctx, mcid)
if err != nil {
return nil, nil, cid.Undef, xerrors.Errorf("error looking up message in index: %w", err)
}
// check the height against the current tipset; minimum execution confidence requires that the
// inclusion tipset height is lower than the current head + 1
curTs := sm.cs.GetHeaviestTipSet()
if curTs.Height() <= minfo.Epoch+1 {
return nil, nil, cid.Undef, xerrors.Errorf("indexed message does not appear before the current tipset; index epoch: %d, current epoch: %d", minfo.Epoch, curTs.Height())
}
// now get the execution tipset
// TODO optimization: the index should have it implicitly so we can return it in the msginfo.
xts, err := sm.cs.GetTipsetByHeight(ctx, minfo.Epoch+1, curTs, false)
if err != nil {
return nil, nil, cid.Undef, xerrors.Errorf("error looking up execution tipset: %w", err)
}
// check that the parent of the execution index is indeed the inclusion tipset
parent := xts.Parents()
parentCid, err := parent.Cid()
if err != nil {
return nil, nil, cid.Undef, xerrors.Errorf("error computing tipset cid: %w", err)
}
if !parentCid.Equals(minfo.TipSet) {
return nil, nil, cid.Undef, xerrors.Errorf("inclusion tipset mismatch: have %s, expected %s", parentCid, minfo.TipSet)
}
r, foundMsg, err := sm.tipsetExecutedMessage(ctx, xts, mcid, m.VMMessage(), false)
if err != nil {
return nil, nil, cid.Undef, xerrors.Errorf("error in tipstExecutedMessage: %w", err)
}
return xts, r, foundMsg, nil
}
// searchBackForMsg searches up to limit tipsets backwards from the given
// tipset for a message receipt.
// If limit is
// - 0 then no tipsets are searched
// - 5 then five tipset are searched
// - LookbackNoLimit then there is no limit
func (sm *StateManager) searchBackForMsg(ctx context.Context, from *types.TipSet, m types.ChainMsg, limit abi.ChainEpoch, allowReplaced bool) (*types.TipSet, *types.MessageReceipt, cid.Cid, error) {
limitHeight := from.Height() - limit
noLimit := limit == LookbackNoLimit
cur := from
curActor, err := sm.LoadActor(ctx, m.VMMessage().From, cur)
if err != nil {
return nil, nil, cid.Undef, xerrors.Errorf("failed to load initital tipset")
}
mFromId, err := sm.LookupIDAddress(ctx, m.VMMessage().From, from)
if err != nil {
return nil, nil, cid.Undef, xerrors.Errorf("looking up From id address: %w", err)
}
mNonce := m.VMMessage().Nonce
for {
// If we've reached the genesis block, or we've reached the limit of
// how far back to look
if cur.Height() == 0 || !noLimit && cur.Height() <= limitHeight {
// it ain't here!
return nil, nil, cid.Undef, nil
}
select {
case <-ctx.Done():
return nil, nil, cid.Undef, nil
default:
}
// we either have no messages from the sender, or the latest message we found has a lower nonce than the one being searched for,
// either way, no reason to lookback, it ain't there
if curActor == nil || curActor.Nonce == 0 || curActor.Nonce < mNonce {
return nil, nil, cid.Undef, nil
}
pts, err := sm.cs.LoadTipSet(ctx, cur.Parents())
if err != nil {
return nil, nil, cid.Undef, xerrors.Errorf("failed to load tipset during msg wait searchback: %w", err)
}
act, err := sm.LoadActor(ctx, mFromId, pts)
actorNoExist := errors.Is(err, types.ErrActorNotFound)
if err != nil && !actorNoExist {
return nil, nil, cid.Cid{}, xerrors.Errorf("failed to load the actor: %w", err)
}
// check that between cur and parent tipset the nonce fell into range of our message
if actorNoExist || (curActor.Nonce > mNonce && act.Nonce <= mNonce) {
r, foundMsg, err := sm.tipsetExecutedMessage(ctx, cur, m.Cid(), m.VMMessage(), allowReplaced)
if err != nil {
return nil, nil, cid.Undef, xerrors.Errorf("checking for message execution during lookback: %w", err)
}
if r != nil {
return cur, r, foundMsg, nil
}
}
cur = pts
curActor = act
}
}
func (sm *StateManager) tipsetExecutedMessage(ctx context.Context, ts *types.TipSet, msg cid.Cid, vmm *types.Message, allowReplaced bool) (*types.MessageReceipt, cid.Cid, error) {
// The genesis block did not execute any messages
if ts.Height() == 0 {
return nil, cid.Undef, nil
}
pts, err := sm.cs.LoadTipSet(ctx, ts.Parents())
if err != nil {
return nil, cid.Undef, err
}
cm, err := sm.cs.MessagesForTipset(ctx, pts)
if err != nil {
return nil, cid.Undef, err
}
for ii := range cm {
// iterate in reverse because we going backwards through the chain
i := len(cm) - ii - 1
m := cm[i]
if m.VMMessage().From == vmm.From { // cheaper to just check origin first
if m.VMMessage().Nonce == vmm.Nonce {
if !m.VMMessage().EqualCall(vmm) {
// this is an entirely different message, fail
return nil, cid.Undef, xerrors.Errorf("found message with equal nonce as the one we are looking for that is NOT a valid replacement message (F:%s n %d, TS: %s n%d)",
msg, vmm.Nonce, m.Cid(), m.VMMessage().Nonce)
}
if m.Cid() != msg {
if !allowReplaced {
log.Warnw("found message with equal nonce and call params but different CID",
"wanted", msg, "found", m.Cid(), "nonce", vmm.Nonce, "from", vmm.From)
return nil, cid.Undef, xerrors.Errorf("found message with equal nonce as the one we are looking for (F:%s n %d, TS: %s n%d)",
msg, vmm.Nonce, m.Cid(), m.VMMessage().Nonce)
}
}
pr, err := sm.cs.GetParentReceipt(ctx, ts.Blocks()[0], i)
if err != nil {
return nil, cid.Undef, err
}
return pr, m.Cid(), nil
}
if m.VMMessage().Nonce < vmm.Nonce {
return nil, cid.Undef, nil // don't bother looking further
}
}
}
return nil, cid.Undef, nil
}