• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

lightningnetwork / lnd / 11670805668

04 Nov 2024 06:50PM UTC coverage: 49.796% (-9.0%) from 58.837%
11670805668

Pull #9241

github

Crypt-iQ
discovery+graph: track job set dependencies in ValidationBarrier

Prior to this commit, it was rare, but possible that proper
validation order was not adhered to when using the ValidationBarrier.
This commit does two things that fix this:
- removes the concept of allow / deny. Having this in place was a
  minor optimization and removing it makes the solution simpler.
- changes the job dependency tracking to track sets of parent jobs
  rather than individual parent jobs.

As a note, the purpose of the ValidationBarrier is that it allows us
to launch gossip validation jobs in goroutines while still ensuring
that the validation order of these goroutines is adhered to when it
comes to validating ChannelAnnouncement _before_ ChannelUpdate and
_before_ NodeAnnouncement.
Pull Request #9241: [DRAFT] discovery+graph: track job set dependencies in vb

183 of 208 new or added lines in 3 files covered. (87.98%)

25473 existing lines in 433 files now uncovered.

99304 of 199422 relevant lines covered (49.8%)

1.55 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

95.56
/sweep/fee_function.go
1
package sweep
2

3
import (
4
        "errors"
5
        "fmt"
6

7
        "github.com/btcsuite/btcd/btcutil"
8
        "github.com/lightningnetwork/lnd/fn"
9
        "github.com/lightningnetwork/lnd/lnwallet/chainfee"
10
        "github.com/lightningnetwork/lnd/lnwire"
11
)
12

13
var (
14
        // ErrMaxPosition is returned when trying to increase the position of
15
        // the fee function while it's already at its max.
16
        ErrMaxPosition = errors.New("position already at max")
17
)
18

19
// mSatPerKWeight represents a fee rate in msat/kw.
20
//
21
// TODO(yy): unify all the units to be virtual bytes.
22
type mSatPerKWeight lnwire.MilliSatoshi
23

24
// String returns a human-readable string of the fee rate.
25
func (m mSatPerKWeight) String() string {
3✔
26
        s := lnwire.MilliSatoshi(m)
3✔
27
        return fmt.Sprintf("%v/kw", s)
3✔
28
}
3✔
29

30
// FeeFunction defines an interface that is used to calculate fee rates for
31
// transactions. It's expected the implementations use three params, the
32
// starting fee rate, the ending fee rate, and number of blocks till deadline
33
// block height, to build an algorithm to calculate the fee rate based on the
34
// current block height.
35
type FeeFunction interface {
36
        // FeeRate returns the current fee rate calculated by the fee function.
37
        FeeRate() chainfee.SatPerKWeight
38

39
        // Increment increases the fee rate by one step. The definition of one
40
        // step is up to the implementation. After calling this method, it's
41
        // expected to change the state of the fee function such that calling
42
        // `FeeRate` again will return the increased value.
43
        //
44
        // It returns a boolean to indicate whether the fee rate is increased,
45
        // as fee bump should not be attempted if the increased fee rate is not
46
        // greater than the current fee rate, which may happen if the algorithm
47
        // gives the same fee rates at two positions.
48
        //
49
        // An error is returned when the max fee rate is reached.
50
        //
51
        // NOTE: we intentionally don't return the new fee rate here, so both
52
        // the implementation and the caller are aware of the state change.
53
        Increment() (bool, error)
54

55
        // IncreaseFeeRate increases the fee rate to the new position
56
        // calculated using (width - confTarget). It returns a boolean to
57
        // indicate whether the fee rate is increased, and an error if the
58
        // position is greater than the width.
59
        //
60
        // NOTE: this method is provided to allow the caller to increase the
61
        // fee rate based on a conf target without taking care of the fee
62
        // function's current state (position).
63
        IncreaseFeeRate(confTarget uint32) (bool, error)
64
}
65

66
// LinearFeeFunction implements the FeeFunction interface with a linear
67
// function:
68
//
69
//        feeRate = startingFeeRate + position * delta.
70
//             - width: deadlineBlockHeight - startingBlockHeight
71
//             - delta: (endingFeeRate - startingFeeRate) / width
72
//             - position: currentBlockHeight - startingBlockHeight
73
//
74
// The fee rate will be capped at endingFeeRate.
75
//
76
// TODO(yy): implement more functions specified here:
77
// - https://github.com/lightningnetwork/lnd/issues/4215
78
type LinearFeeFunction struct {
79
        // startingFeeRate specifies the initial fee rate to begin with.
80
        startingFeeRate chainfee.SatPerKWeight
81

82
        // endingFeeRate specifies the max allowed fee rate.
83
        endingFeeRate chainfee.SatPerKWeight
84

85
        // currentFeeRate specifies the current calculated fee rate.
86
        currentFeeRate chainfee.SatPerKWeight
87

88
        // width is the number of blocks between the starting block height
89
        // and the deadline block height minus one.
90
        //
91
        // NOTE: We do minus one from the conf target here because we want to
92
        // max out the budget before the deadline height is reached.
93
        width uint32
94

95
        // position is the fee function's current position, given a width of w,
96
        // a valid position should lie in range [0, w].
97
        position uint32
98

99
        // deltaFeeRate is the fee rate (msat/kw) increase per block.
100
        //
101
        // NOTE: this is used to increase precision.
102
        deltaFeeRate mSatPerKWeight
103

104
        // estimator is the fee estimator used to estimate the fee rate. We use
105
        // it to get the initial fee rate and, use it as a benchmark to decide
106
        // whether we want to used the estimated fee rate or the calculated fee
107
        // rate based on different strategies.
108
        estimator chainfee.Estimator
109
}
110

111
// Compile-time check to ensure LinearFeeFunction satisfies the FeeFunction.
112
var _ FeeFunction = (*LinearFeeFunction)(nil)
113

114
// NewLinearFeeFunction creates a new linear fee function and initializes it
115
// with a starting fee rate which is an estimated value returned from the fee
116
// estimator using the initial conf target.
117
func NewLinearFeeFunction(maxFeeRate chainfee.SatPerKWeight,
118
        confTarget uint32, estimator chainfee.Estimator,
119
        startingFeeRate fn.Option[chainfee.SatPerKWeight]) (
120
        *LinearFeeFunction, error) {
3✔
121

3✔
122
        // If the deadline is one block away or has already been reached,
3✔
123
        // there's nothing the fee function can do. In this case, we'll use the
3✔
124
        // max fee rate immediately.
3✔
125
        if confTarget <= 1 {
6✔
126
                return &LinearFeeFunction{
3✔
127
                        startingFeeRate: maxFeeRate,
3✔
128
                        endingFeeRate:   maxFeeRate,
3✔
129
                        currentFeeRate:  maxFeeRate,
3✔
130
                }, nil
3✔
131
        }
3✔
132

133
        l := &LinearFeeFunction{
3✔
134
                endingFeeRate: maxFeeRate,
3✔
135
                width:         confTarget - 1,
3✔
136
                estimator:     estimator,
3✔
137
        }
3✔
138

3✔
139
        // If the caller specifies the starting fee rate, we'll use it instead
3✔
140
        // of estimating it based on the deadline.
3✔
141
        start, err := startingFeeRate.UnwrapOrFuncErr(
3✔
142
                func() (chainfee.SatPerKWeight, error) {
6✔
143
                        // Estimate the initial fee rate.
3✔
144
                        //
3✔
145
                        // NOTE: estimateFeeRate guarantees the returned fee
3✔
146
                        // rate is capped by the ending fee rate, so we don't
3✔
147
                        // need to worry about overpay.
3✔
148
                        return l.estimateFeeRate(confTarget)
3✔
149
                })
3✔
150
        if err != nil {
3✔
UNCOV
151
                return nil, fmt.Errorf("estimate initial fee rate: %w", err)
×
UNCOV
152
        }
×
153

154
        // Calculate how much fee rate should be increased per block.
155
        end := l.endingFeeRate
3✔
156

3✔
157
        // The starting and ending fee rates are in sat/kw, so we need to
3✔
158
        // convert them to msat/kw by multiplying by 1000.
3✔
159
        delta := btcutil.Amount(end - start).MulF64(1000 / float64(l.width))
3✔
160
        l.deltaFeeRate = mSatPerKWeight(delta)
3✔
161

3✔
162
        // We only allow the delta to be zero if the width is one - when the
3✔
163
        // delta is zero, it means the starting and ending fee rates are the
3✔
164
        // same, which means there's nothing to increase, so any width greater
3✔
165
        // than 1 doesn't provide any utility. This could happen when the
3✔
166
        // budget is too small.
3✔
167
        if l.deltaFeeRate == 0 && l.width != 1 {
6✔
168
                log.Errorf("Failed to init fee function: startingFeeRate=%v, "+
3✔
169
                        "endingFeeRate=%v, width=%v, delta=%v", start, end,
3✔
170
                        l.width, l.deltaFeeRate)
3✔
171

3✔
172
                return nil, fmt.Errorf("fee rate delta is zero")
3✔
173
        }
3✔
174

175
        // Attach the calculated values to the fee function.
176
        l.startingFeeRate = start
3✔
177
        l.currentFeeRate = start
3✔
178

3✔
179
        log.Debugf("Linear fee function initialized with startingFeeRate=%v, "+
3✔
180
                "endingFeeRate=%v, width=%v, delta=%v", start, end,
3✔
181
                l.width, l.deltaFeeRate)
3✔
182

3✔
183
        return l, nil
3✔
184
}
185

186
// FeeRate returns the current fee rate.
187
//
188
// NOTE: part of the FeeFunction interface.
189
func (l *LinearFeeFunction) FeeRate() chainfee.SatPerKWeight {
3✔
190
        return l.currentFeeRate
3✔
191
}
3✔
192

193
// Increment increases the fee rate by one position, returns a boolean to
194
// indicate whether the fee rate was increased, and an error if the position is
195
// greater than the width. The increased fee rate will be set as the current
196
// fee rate, and the internal position will be incremented.
197
//
198
// NOTE: this method will change the state of the fee function as it increases
199
// its current fee rate.
200
//
201
// NOTE: part of the FeeFunction interface.
202
func (l *LinearFeeFunction) Increment() (bool, error) {
2✔
203
        return l.increaseFeeRate(l.position + 1)
2✔
204
}
2✔
205

206
// IncreaseFeeRate calculate a new position using the given conf target, and
207
// increases the fee rate to the new position by calling the Increment method.
208
//
209
// NOTE: this method will change the state of the fee function as it increases
210
// its current fee rate.
211
//
212
// NOTE: part of the FeeFunction interface.
213
func (l *LinearFeeFunction) IncreaseFeeRate(confTarget uint32) (bool, error) {
3✔
214
        newPosition := uint32(0)
3✔
215

3✔
216
        // Only calculate the new position when the conf target is less than
3✔
217
        // the function's width - the width is the initial conf target-1, and
3✔
218
        // we expect the current conf target to decrease over time. However, we
3✔
219
        // still allow the supplied conf target to be greater than the width,
3✔
220
        // and we won't increase the fee rate in that case.
3✔
221
        if confTarget < l.width+1 {
6✔
222
                newPosition = l.width + 1 - confTarget
3✔
223
                log.Tracef("Increasing position from %v to %v", l.position,
3✔
224
                        newPosition)
3✔
225
        }
3✔
226

227
        if newPosition <= l.position {
6✔
228
                log.Tracef("Skipped increase feerate: position=%v, "+
3✔
229
                        "newPosition=%v ", l.position, newPosition)
3✔
230

3✔
231
                return false, nil
3✔
232
        }
3✔
233

234
        return l.increaseFeeRate(newPosition)
3✔
235
}
236

237
// increaseFeeRate increases the fee rate by the specified position, returns a
238
// boolean to indicate whether the fee rate was increased, and an error if the
239
// position is greater than the width. The increased fee rate will be set as
240
// the current fee rate, and the internal position will be set to the specified
241
// position.
242
//
243
// NOTE: this method will change the state of the fee function as it increases
244
// its current fee rate.
245
func (l *LinearFeeFunction) increaseFeeRate(position uint32) (bool, error) {
3✔
246
        // If the new position is already at the end, we return an error.
3✔
247
        if l.position >= l.width {
6✔
248
                return false, ErrMaxPosition
3✔
249
        }
3✔
250

251
        // Get the old fee rate.
252
        oldFeeRate := l.currentFeeRate
3✔
253

3✔
254
        // Update its internal state.
3✔
255
        l.position = position
3✔
256
        l.currentFeeRate = l.feeRateAtPosition(position)
3✔
257

3✔
258
        log.Tracef("Fee rate increased from %v to %v at position %v",
3✔
259
                oldFeeRate, l.currentFeeRate, l.position)
3✔
260

3✔
261
        return l.currentFeeRate > oldFeeRate, nil
3✔
262
}
263

264
// feeRateAtPosition calculates the fee rate at a given position and caps it at
265
// the ending fee rate.
266
func (l *LinearFeeFunction) feeRateAtPosition(p uint32) chainfee.SatPerKWeight {
3✔
267
        if p >= l.width {
6✔
268
                return l.endingFeeRate
3✔
269
        }
3✔
270

271
        // deltaFeeRate is in msat/kw, so we need to divide by 1000 to get the
272
        // fee rate in sat/kw.
273
        feeRateDelta := btcutil.Amount(l.deltaFeeRate).MulF64(float64(p) / 1000)
3✔
274

3✔
275
        feeRate := l.startingFeeRate + chainfee.SatPerKWeight(feeRateDelta)
3✔
276
        if feeRate > l.endingFeeRate {
3✔
277
                return l.endingFeeRate
×
278
        }
×
279

280
        return feeRate
3✔
281
}
282

283
// estimateFeeRate asks the fee estimator to estimate the fee rate based on its
284
// conf target.
285
func (l *LinearFeeFunction) estimateFeeRate(
286
        confTarget uint32) (chainfee.SatPerKWeight, error) {
3✔
287

3✔
288
        fee := FeeEstimateInfo{
3✔
289
                ConfTarget: confTarget,
3✔
290
        }
3✔
291

3✔
292
        // If the conf target is greater or equal to the max allowed value
3✔
293
        // (1008), we will use the min relay fee instead.
3✔
294
        if confTarget >= chainfee.MaxBlockTarget {
6✔
295
                minFeeRate := l.estimator.RelayFeePerKW()
3✔
296
                log.Infof("Conf target %v is greater than max block target, "+
3✔
297
                        "using min relay fee rate %v", confTarget, minFeeRate)
3✔
298

3✔
299
                return minFeeRate, nil
3✔
300
        }
3✔
301

302
        // endingFeeRate comes from budget/txWeight, which means the returned
303
        // fee rate will always be capped by this value, hence we don't need to
304
        // worry about overpay.
305
        estimatedFeeRate, err := fee.Estimate(l.estimator, l.endingFeeRate)
3✔
306
        if err != nil {
3✔
UNCOV
307
                return 0, err
×
UNCOV
308
        }
×
309

310
        return estimatedFeeRate, nil
3✔
311
}
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2026 Coveralls, Inc