13566028875

Committed 27 Feb 2025 12:09PM UTC coverage: 49.396% (-9.4%) from 58.748%

Build # 13566028875

Build Type

Pull #9555

github

Committed by

ellemouton

Commit Message

graph/db: populate the graph cache in Start instead of during construction

In this commit, we move the graph cache population logic out of the
ChannelGraph constructor and into its Start method instead.

Pull Request Pull Request #9555: graph: extract cache from CRUD [6]

Run Details

34 of 54 new or added lines in 4 files covered. (62.96%)

27464 existing lines in 436 files now uncovered.

101095 of 204664 relevant lines covered (49.4%)

1.54 hits per line

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

77.43

/routing/unified_edges.go

package routing

import (
        "math"

        "github.com/btcsuite/btcd/btcutil"
        graphdb "github.com/lightningnetwork/lnd/graph/db"
        "github.com/lightningnetwork/lnd/graph/db/models"
        "github.com/lightningnetwork/lnd/lnwire"
        "github.com/lightningnetwork/lnd/routing/route"
)

// nodeEdgeUnifier holds all edge unifiers for connections towards a node.
type nodeEdgeUnifier struct {
        // edgeUnifiers contains an edge unifier for every from node.
        edgeUnifiers map[route.Vertex]*edgeUnifier

        // sourceNode is the sender of a payment. The rules to pick the final
        // policy are different for local channels.
        sourceNode route.Vertex

        // toNode is the node for which the edge unifiers are instantiated.
        toNode route.Vertex

        // useInboundFees indicates whether to take inbound fees into account.
        useInboundFees bool

        // outChanRestr is an optional outgoing channel restriction for the
        // local channel to use.
        outChanRestr map[uint64]struct{}
}

// newNodeEdgeUnifier instantiates a new nodeEdgeUnifier object. Channel
// policies can be added to this object.
func newNodeEdgeUnifier(sourceNode, toNode route.Vertex, useInboundFees bool,
        outChanRestr map[uint64]struct{}) *nodeEdgeUnifier {

        return &nodeEdgeUnifier{
                edgeUnifiers:   make(map[route.Vertex]*edgeUnifier),
                toNode:         toNode,
                useInboundFees: useInboundFees,
                sourceNode:     sourceNode,
                outChanRestr:   outChanRestr,
        }
}

// addPolicy adds a single channel policy. Capacity may be zero if unknown
// (light clients). We expect a non-nil payload size function and will request a
// graceful shutdown if it is not provided as this indicates that edges are
// incorrectly specified.
func (u *nodeEdgeUnifier) addPolicy(fromNode route.Vertex,
        edge *models.CachedEdgePolicy, inboundFee models.InboundFee,
        capacity btcutil.Amount, hopPayloadSizeFn PayloadSizeFunc,
        blindedPayment *BlindedPayment) {

        localChan := fromNode == u.sourceNode

        // Skip channels if there is an outgoing channel restriction.
        if localChan && u.outChanRestr != nil {
                if _, ok := u.outChanRestr[edge.ChannelID]; !ok {
                        log.Debugf("Skipped adding policy for restricted edge "+
                                "%v", edge.ChannelID)

                        return
                }
        }

        // Update the edgeUnifiers map.
        unifier, ok := u.edgeUnifiers[fromNode]
        if !ok {
                unifier = &edgeUnifier{
                        localChan: localChan,
                }
                u.edgeUnifiers[fromNode] = unifier
        }

        // In case no payload size function was provided a graceful shutdown
        // is requested, because this function is not used as intended.
        if hopPayloadSizeFn == nil {
                log.Criticalf("No payloadsize function was provided for the "+
                        "edge (chanid=%v) when adding it to the edge unifier "+
                        "of node: %v", edge.ChannelID, fromNode)

                return
        }

        // Zero inbound fee for exit hops.
        if !u.useInboundFees {
                inboundFee = models.InboundFee{}
        }

        unifier.edges = append(unifier.edges, newUnifiedEdge(
                edge, capacity, inboundFee, hopPayloadSizeFn, blindedPayment,
        ))
}

// addGraphPolicies adds all policies that are known for the toNode in the
// graph.
func (u *nodeEdgeUnifier) addGraphPolicies(g Graph) error {
        cb := func(channel *graphdb.DirectedChannel) error {
                // If there is no edge policy for this candidate node, skip.
                // Note that we are searching backwards so this node would have
                // come prior to the pivot node in the route.
                if channel.InPolicy == nil {
                        log.Debugf("Skipped adding edge %v due to nil policy",
                                channel.ChannelID)

                        return nil
                }

                // Add this policy to the corresponding edgeUnifier. We default
                // to the clear hop payload size function because
                // `addGraphPolicies` is only used for cleartext intermediate
                // hops in a route.
                inboundFee := models.NewInboundFeeFromWire(
                        channel.InboundFee,
                )

                u.addPolicy(
                        channel.OtherNode, channel.InPolicy, inboundFee,
                        channel.Capacity, defaultHopPayloadSize, nil,
                )

                return nil
        }

        // Iterate over all channels of the to node.
        return g.ForEachNodeDirectedChannel(u.toNode, cb)
}

// unifiedEdge is the individual channel data that is kept inside an edgeUnifier
// object.
type unifiedEdge struct {
        policy      *models.CachedEdgePolicy
        capacity    btcutil.Amount
        inboundFees models.InboundFee

        // hopPayloadSize supplies an edge with the ability to calculate the
        // exact payload size if this edge would be included in a route. This
        // is needed because hops of a blinded path differ in their payload
        // structure compared to cleartext hops.
        hopPayloadSizeFn PayloadSizeFunc

        // blindedPayment if set, is the BlindedPayment that this edge was
        // derived from originally.
        blindedPayment *BlindedPayment
}

// newUnifiedEdge constructs a new unifiedEdge.
func newUnifiedEdge(policy *models.CachedEdgePolicy, capacity btcutil.Amount,
        inboundFees models.InboundFee, hopPayloadSizeFn PayloadSizeFunc,
        blindedPayment *BlindedPayment) *unifiedEdge {

        return &unifiedEdge{
                policy:           policy,
                capacity:         capacity,
                inboundFees:      inboundFees,
                hopPayloadSizeFn: hopPayloadSizeFn,
                blindedPayment:   blindedPayment,
        }
}

// amtInRange checks whether an amount falls within the valid range for a
// channel.
func (u *unifiedEdge) amtInRange(amt lnwire.MilliSatoshi) bool {
        // If the capacity is available (non-light clients), skip channels that
        // are too small.
        if u.capacity > 0 &&
                amt > lnwire.NewMSatFromSatoshis(u.capacity) {

                log.Tracef("Not enough capacity: amt=%v, capacity=%v",
                        amt, u.capacity)
                return false
        }

        // Skip channels for which this htlc is too large.
        if u.policy.MessageFlags.HasMaxHtlc() &&
                amt > u.policy.MaxHTLC {

                log.Tracef("Exceeds policy's MaxHTLC: amt=%v, MaxHTLC=%v",
                        amt, u.policy.MaxHTLC)
                return false
        }

        // Skip channels for which this htlc is too small.
        if amt < u.policy.MinHTLC {
                log.Tracef("below policy's MinHTLC: amt=%v, MinHTLC=%v",
                        amt, u.policy.MinHTLC)
                return false
        }

        return true
}

// edgeUnifier is an object that covers all channels between a pair of nodes.
type edgeUnifier struct {
        edges     []*unifiedEdge
        localChan bool
}

// getEdge returns the optimal unified edge to use for this connection given a
// specific amount to send. It differentiates between local and network
// channels.
func (u *edgeUnifier) getEdge(netAmtReceived lnwire.MilliSatoshi,
        bandwidthHints bandwidthHints,
        nextOutFee lnwire.MilliSatoshi) *unifiedEdge {

        if u.localChan {
                return u.getEdgeLocal(
                        netAmtReceived, bandwidthHints, nextOutFee,
                )
        }

        return u.getEdgeNetwork(netAmtReceived, nextOutFee)
}

// calcCappedInboundFee calculates the inbound fee for a channel, taking into
// account the total node fee for the "to" node.
func calcCappedInboundFee(edge *unifiedEdge, amt lnwire.MilliSatoshi,
        nextOutFee lnwire.MilliSatoshi) int64 {

        // Calculate the inbound fee charged for the amount that passes over the
        // channel.
        inboundFee := edge.inboundFees.CalcFee(amt)

        // Take into account that the total node fee cannot be negative.
        if inboundFee < -int64(nextOutFee) {
                inboundFee = -int64(nextOutFee)
        }

        return inboundFee
}

// getEdgeLocal returns the optimal unified edge to use for this local
// connection given a specific amount to send.
func (u *edgeUnifier) getEdgeLocal(netAmtReceived lnwire.MilliSatoshi,
        bandwidthHints bandwidthHints,
        nextOutFee lnwire.MilliSatoshi) *unifiedEdge {

        var (
                bestEdge     *unifiedEdge
                maxBandwidth lnwire.MilliSatoshi
        )

        for _, edge := range u.edges {
                // Calculate the inbound fee charged at the receiving node.
                inboundFee := calcCappedInboundFee(
                        edge, netAmtReceived, nextOutFee,
                )

                // Add inbound fee to get to the amount that is sent over the
                // local channel.
                amt := netAmtReceived + lnwire.MilliSatoshi(inboundFee)

                // Check valid amount range for the channel. We skip this test
                // for payments with custom HTLC data, as the amount sent on
                // the BTC layer may differ from the amount that is actually
                // forwarded in custom channels.
                if bandwidthHints.firstHopCustomBlob().IsNone() &&
                        !edge.amtInRange(amt) {

                        log.Debugf("Amount %v not in range for edge %v",
                                netAmtReceived, edge.policy.ChannelID)

                        continue
                }

                // For local channels, there is no fee to pay or an extra time
                // lock. We only consider the currently available bandwidth for
                // channel selection. The disabled flag is ignored for local
                // channels.

                // Retrieve bandwidth for this local channel. If not
                // available, assume this channel has enough bandwidth.
                //
                // TODO(joostjager): Possibly change to skipping this
                // channel. The bandwidth hint is expected to be
                // available.
                bandwidth, ok := bandwidthHints.availableChanBandwidth(
                        edge.policy.ChannelID, amt,
                )
                if !ok {
                        log.Debugf("Cannot get bandwidth for edge %v, use max "+
                                "instead", edge.policy.ChannelID)
                        bandwidth = lnwire.MaxMilliSatoshi
                }

                // TODO(yy): if the above `!ok` is chosen, we'd have
                // `bandwidth` to be the max value, which will end up having
                // the `maxBandwidth` to be have the largest value and this
                // edge will be the chosen one. This is wrong in two ways,
                // 1. we need to understand why `availableChanBandwidth` cannot
                // find bandwidth for this edge as something is wrong with this
                // channel, and,
                // 2. this edge is likely NOT the local channel with the
                // highest available bandwidth.
                //
                // Skip channels that can't carry the payment.
                if amt > bandwidth {
                        log.Debugf("Skipped edge %v: not enough bandwidth, "+
                                "bandwidth=%v, amt=%v", edge.policy.ChannelID,
                                bandwidth, amt)

                        continue
                }

                // We pick the local channel with the highest available
                // bandwidth, to maximize the success probability. It can be
                // that the channel state changes between querying the bandwidth
                // hints and sending out the htlc.
                if bandwidth < maxBandwidth {
                        log.Debugf("Skipped edge %v: not max bandwidth, "+
                                "bandwidth=%v, maxBandwidth=%v",
                                edge.policy.ChannelID, bandwidth, maxBandwidth)

                        continue
                }
                maxBandwidth = bandwidth

                // Update best edge.
                bestEdge = newUnifiedEdge(
                        edge.policy, edge.capacity, edge.inboundFees,
                        edge.hopPayloadSizeFn, edge.blindedPayment,
                )
        }

        return bestEdge
}

// getEdgeNetwork returns the optimal unified edge to use for this connection
// given a specific amount to send. The goal is to return a unified edge with a
// policy that maximizes the probability of a successful forward in a non-strict
// forwarding context.
func (u *edgeUnifier) getEdgeNetwork(netAmtReceived lnwire.MilliSatoshi,
        nextOutFee lnwire.MilliSatoshi) *unifiedEdge {

        var (
                bestPolicy       *unifiedEdge
                maxFee           int64 = math.MinInt64
                maxTimelock      uint16
                maxCapMsat       lnwire.MilliSatoshi
                hopPayloadSizeFn PayloadSizeFunc
        )

        for _, edge := range u.edges {
                // Calculate the inbound fee charged at the receiving node.
                inboundFee := calcCappedInboundFee(
                        edge, netAmtReceived, nextOutFee,
                )

                // Add inbound fee to get to the amount that is sent over the
                // channel.
                amt := netAmtReceived + lnwire.MilliSatoshi(inboundFee)

                // Check valid amount range for the channel.
                if !edge.amtInRange(amt) {
                        log.Debugf("Amount %v not in range for edge %v",
                                amt, edge.policy.ChannelID)
                        continue
                }

                // For network channels, skip the disabled ones.
                edgeFlags := edge.policy.ChannelFlags
                isDisabled := edgeFlags&lnwire.ChanUpdateDisabled != 0
                if isDisabled {
                        log.Debugf("Skipped edge %v due to it being disabled",
                                edge.policy.ChannelID)
                        continue
                }

                // Track the maximal capacity for usable channels. If we don't
                // know the capacity, we fall back to MaxHTLC.
                capMsat := lnwire.NewMSatFromSatoshis(edge.capacity)
                if capMsat == 0 && edge.policy.MessageFlags.HasMaxHtlc() {
                        log.Tracef("No capacity available for channel %v, "+
                                "using MaxHtlcMsat (%v) as a fallback.",
                                edge.policy.ChannelID, edge.policy.MaxHTLC)

                        capMsat = edge.policy.MaxHTLC
                }
                maxCapMsat = max(capMsat, maxCapMsat)

                // Track the maximum time lock of all channels that are
                // candidate for non-strict forwarding at the routing node.
                maxTimelock = max(maxTimelock, edge.policy.TimeLockDelta)

                outboundFee := int64(edge.policy.ComputeFee(amt))
                fee := outboundFee + inboundFee

                // Use the policy that results in the highest fee for this
                // specific amount.
                if fee < maxFee {
                        log.Debugf("Skipped edge %v due to it produces less "+
                                "fee: fee=%v, maxFee=%v",
                                edge.policy.ChannelID, fee, maxFee)

                        continue
                }
                maxFee = fee

                bestPolicy = newUnifiedEdge(
                        edge.policy, 0, edge.inboundFees, nil,
                        edge.blindedPayment,
                )

                // The payload size function for edges to a connected peer is
                // always the same hence there is not need to find the maximum.
                // This also counts for blinded edges where we only have one
                // edge to a blinded peer.
                hopPayloadSizeFn = edge.hopPayloadSizeFn
        }

        // Return early if no channel matches.
        if bestPolicy == nil {
                return nil
        }

        // We have already picked the highest fee that could be required for
        // non-strict forwarding. To also cover the case where a lower fee
        // channel requires a longer time lock, we modify the policy by setting
        // the maximum encountered time lock. Note that this results in a
        // synthetic policy that is not actually present on the routing node.
        //
        // The reason we do this, is that we try to maximize the chance that we
        // get forwarded. Because we penalize pair-wise, there won't be a second
        // chance for this node pair. But this is all only needed for nodes that
        // have distinct policies for channels to the same peer.
        policyCopy := *bestPolicy.policy
        policyCopy.TimeLockDelta = maxTimelock
        modifiedEdge := newUnifiedEdge(
                &policyCopy, maxCapMsat.ToSatoshis(), bestPolicy.inboundFees,
                hopPayloadSizeFn, bestPolicy.blindedPayment,
        )

        return modifiedEdge
}

// minAmt returns the minimum amount that can be forwarded on this connection.
func (u *edgeUnifier) minAmt() lnwire.MilliSatoshi {
        minAmount := lnwire.MaxMilliSatoshi
        for _, edge := range u.edges {
                minAmount = min(minAmount, edge.policy.MinHTLC)
        }

        return minAmount
}

1	package routing
2
3	import (
4	"math"
5
6	"github.com/btcsuite/btcd/btcutil"
7	graphdb "github.com/lightningnetwork/lnd/graph/db"
8	"github.com/lightningnetwork/lnd/graph/db/models"
9	"github.com/lightningnetwork/lnd/lnwire"
10	"github.com/lightningnetwork/lnd/routing/route"
11	)
12
13	// nodeEdgeUnifier holds all edge unifiers for connections towards a node.
14	type nodeEdgeUnifier struct {
15	// edgeUnifiers contains an edge unifier for every from node.
16	edgeUnifiers map[route.Vertex]*edgeUnifier
17
18	// sourceNode is the sender of a payment. The rules to pick the final
19	// policy are different for local channels.
20	sourceNode route.Vertex
21
22	// toNode is the node for which the edge unifiers are instantiated.
23	toNode route.Vertex
24
25	// useInboundFees indicates whether to take inbound fees into account.
26	useInboundFees bool
27
28	// outChanRestr is an optional outgoing channel restriction for the
29	// local channel to use.
30	outChanRestr map[uint64]struct{}
31	}
32
33	// newNodeEdgeUnifier instantiates a new nodeEdgeUnifier object. Channel
34	// policies can be added to this object.
35	func newNodeEdgeUnifier(sourceNode, toNode route.Vertex, useInboundFees bool,
36	outChanRestr map[uint64]struct{}) *nodeEdgeUnifier {	3✔
37		3✔
38	return &nodeEdgeUnifier{	3✔
39	edgeUnifiers: make(map[route.Vertex]*edgeUnifier),	3✔
40	toNode: toNode,	3✔
41	useInboundFees: useInboundFees,	3✔
42	sourceNode: sourceNode,	3✔
43	outChanRestr: outChanRestr,	3✔
44	}	3✔
45	}	3✔
46
47	// addPolicy adds a single channel policy. Capacity may be zero if unknown
48	// (light clients). We expect a non-nil payload size function and will request a
49	// graceful shutdown if it is not provided as this indicates that edges are
50	// incorrectly specified.
51	func (u *nodeEdgeUnifier) addPolicy(fromNode route.Vertex,
52	edge *models.CachedEdgePolicy, inboundFee models.InboundFee,
53	capacity btcutil.Amount, hopPayloadSizeFn PayloadSizeFunc,
54	blindedPayment *BlindedPayment) {	3✔
55		3✔
56	localChan := fromNode == u.sourceNode	3✔
57		3✔
58	// Skip channels if there is an outgoing channel restriction.	3✔
59	if localChan && u.outChanRestr != nil {	3✔
UNCOV 60	if _, ok := u.outChanRestr[edge.ChannelID]; !ok {	×
UNCOV 61	log.Debugf("Skipped adding policy for restricted edge "+	×
UNCOV 62	"%v", edge.ChannelID)	×
UNCOV 63		×
UNCOV 64	return	×
UNCOV 65	}	×
66	}
67
68	// Update the edgeUnifiers map.
69	unifier, ok := u.edgeUnifiers[fromNode]	3✔
70	if !ok {	6✔
71	unifier = &edgeUnifier{	3✔
72	localChan: localChan,	3✔
73	}	3✔
74	u.edgeUnifiers[fromNode] = unifier	3✔
75	}	3✔
76
77	// In case no payload size function was provided a graceful shutdown
78	// is requested, because this function is not used as intended.
79	if hopPayloadSizeFn == nil {	3✔
80	log.Criticalf("No payloadsize function was provided for the "+	×
81	"edge (chanid=%v) when adding it to the edge unifier "+	×
82	"of node: %v", edge.ChannelID, fromNode)	×
83		×
84	return	×
85	}	×
86
87	// Zero inbound fee for exit hops.
88	if !u.useInboundFees {	6✔
89	inboundFee = models.InboundFee{}	3✔
90	}	3✔
91
92	unifier.edges = append(unifier.edges, newUnifiedEdge(	3✔
93	edge, capacity, inboundFee, hopPayloadSizeFn, blindedPayment,	3✔
94	))	3✔
95	}
96
97	// addGraphPolicies adds all policies that are known for the toNode in the
98	// graph.
99	func (u *nodeEdgeUnifier) addGraphPolicies(g Graph) error {	3✔
100	cb := func(channel *graphdb.DirectedChannel) error {	6✔
101	// If there is no edge policy for this candidate node, skip.	3✔
102	// Note that we are searching backwards so this node would have	3✔
103	// come prior to the pivot node in the route.	3✔
104	if channel.InPolicy == nil {	3✔
105	log.Debugf("Skipped adding edge %v due to nil policy",	×
106	channel.ChannelID)	×
107		×
108	return nil	×
109	}	×
110
111	// Add this policy to the corresponding edgeUnifier. We default
112	// to the clear hop payload size function because
113	// `addGraphPolicies` is only used for cleartext intermediate
114	// hops in a route.
115	inboundFee := models.NewInboundFeeFromWire(	3✔
116	channel.InboundFee,	3✔
117	)	3✔
118		3✔
119	u.addPolicy(	3✔
120	channel.OtherNode, channel.InPolicy, inboundFee,	3✔
121	channel.Capacity, defaultHopPayloadSize, nil,	3✔
122	)	3✔
123		3✔
124	return nil	3✔
125	}
126
127	// Iterate over all channels of the to node.
128	return g.ForEachNodeDirectedChannel(u.toNode, cb)	3✔
129	}
130
131	// unifiedEdge is the individual channel data that is kept inside an edgeUnifier
132	// object.
133	type unifiedEdge struct {
134	policy *models.CachedEdgePolicy
135	capacity btcutil.Amount
136	inboundFees models.InboundFee
137
138	// hopPayloadSize supplies an edge with the ability to calculate the
139	// exact payload size if this edge would be included in a route. This
140	// is needed because hops of a blinded path differ in their payload
141	// structure compared to cleartext hops.
142	hopPayloadSizeFn PayloadSizeFunc
143
144	// blindedPayment if set, is the BlindedPayment that this edge was
145	// derived from originally.
146	blindedPayment *BlindedPayment
147	}
148
149	// newUnifiedEdge constructs a new unifiedEdge.
150	func newUnifiedEdge(policy *models.CachedEdgePolicy, capacity btcutil.Amount,
151	inboundFees models.InboundFee, hopPayloadSizeFn PayloadSizeFunc,
152	blindedPayment BlindedPayment) unifiedEdge {	3✔
153		3✔
154	return &unifiedEdge{	3✔
155	policy: policy,	3✔
156	capacity: capacity,	3✔
157	inboundFees: inboundFees,	3✔
158	hopPayloadSizeFn: hopPayloadSizeFn,	3✔
159	blindedPayment: blindedPayment,	3✔
160	}	3✔
161	}	3✔
162
163	// amtInRange checks whether an amount falls within the valid range for a
164	// channel.
165	func (u *unifiedEdge) amtInRange(amt lnwire.MilliSatoshi) bool {	3✔
166	// If the capacity is available (non-light clients), skip channels that	3✔
167	// are too small.	3✔
168	if u.capacity > 0 &&	3✔
169	amt > lnwire.NewMSatFromSatoshis(u.capacity) {	3✔
UNCOV 170		×
UNCOV 171	log.Tracef("Not enough capacity: amt=%v, capacity=%v",	×
UNCOV 172	amt, u.capacity)	×
UNCOV 173	return false	×
UNCOV 174	}	×
175
176	// Skip channels for which this htlc is too large.
177	if u.policy.MessageFlags.HasMaxHtlc() &&	3✔
178	amt > u.policy.MaxHTLC {	6✔
179		3✔
180	log.Tracef("Exceeds policy's MaxHTLC: amt=%v, MaxHTLC=%v",	3✔
181	amt, u.policy.MaxHTLC)	3✔
182	return false	3✔
183	}	3✔
184
185	// Skip channels for which this htlc is too small.
186	if amt < u.policy.MinHTLC {	6✔
187	log.Tracef("below policy's MinHTLC: amt=%v, MinHTLC=%v",	3✔
188	amt, u.policy.MinHTLC)	3✔
189	return false	3✔
190	}	3✔
191
192	return true	3✔
193	}
194
195	// edgeUnifier is an object that covers all channels between a pair of nodes.
196	type edgeUnifier struct {
197	edges []*unifiedEdge
198	localChan bool
199	}
200
201	// getEdge returns the optimal unified edge to use for this connection given a
202	// specific amount to send. It differentiates between local and network
203	// channels.
204	func (u *edgeUnifier) getEdge(netAmtReceived lnwire.MilliSatoshi,
205	bandwidthHints bandwidthHints,
206	nextOutFee lnwire.MilliSatoshi) *unifiedEdge {	3✔
207		3✔
208	if u.localChan {	6✔
209	return u.getEdgeLocal(	3✔
210	netAmtReceived, bandwidthHints, nextOutFee,	3✔
211	)	3✔
212	}	3✔
213
214	return u.getEdgeNetwork(netAmtReceived, nextOutFee)	3✔
215	}
216
217	// calcCappedInboundFee calculates the inbound fee for a channel, taking into
218	// account the total node fee for the "to" node.
219	func calcCappedInboundFee(edge *unifiedEdge, amt lnwire.MilliSatoshi,
220	nextOutFee lnwire.MilliSatoshi) int64 {	3✔
221		3✔
222	// Calculate the inbound fee charged for the amount that passes over the	3✔
223	// channel.	3✔
224	inboundFee := edge.inboundFees.CalcFee(amt)	3✔
225		3✔
226	// Take into account that the total node fee cannot be negative.	3✔
227	if inboundFee < -int64(nextOutFee) {	3✔
UNCOV 228	inboundFee = -int64(nextOutFee)	×
UNCOV 229	}	×
230
231	return inboundFee	3✔
232	}
233
234	// getEdgeLocal returns the optimal unified edge to use for this local
235	// connection given a specific amount to send.
236	func (u *edgeUnifier) getEdgeLocal(netAmtReceived lnwire.MilliSatoshi,
237	bandwidthHints bandwidthHints,
238	nextOutFee lnwire.MilliSatoshi) *unifiedEdge {	3✔
239		3✔
240	var (	3✔
241	bestEdge *unifiedEdge	3✔
242	maxBandwidth lnwire.MilliSatoshi	3✔
243	)	3✔
244		3✔
245	for _, edge := range u.edges {	6✔
246	// Calculate the inbound fee charged at the receiving node.	3✔
247	inboundFee := calcCappedInboundFee(	3✔
248	edge, netAmtReceived, nextOutFee,	3✔
249	)	3✔
250		3✔
251	// Add inbound fee to get to the amount that is sent over the	3✔
252	// local channel.	3✔
253	amt := netAmtReceived + lnwire.MilliSatoshi(inboundFee)	3✔
254		3✔
255	// Check valid amount range for the channel. We skip this test	3✔
256	// for payments with custom HTLC data, as the amount sent on	3✔
257	// the BTC layer may differ from the amount that is actually	3✔
258	// forwarded in custom channels.	3✔
259	if bandwidthHints.firstHopCustomBlob().IsNone() &&	3✔
260	!edge.amtInRange(amt) {	3✔
UNCOV 261		×
UNCOV 262	log.Debugf("Amount %v not in range for edge %v",	×
UNCOV 263	netAmtReceived, edge.policy.ChannelID)	×
UNCOV 264		×
UNCOV 265	continue	×
266	}
267
268	// For local channels, there is no fee to pay or an extra time
269	// lock. We only consider the currently available bandwidth for
270	// channel selection. The disabled flag is ignored for local
271	// channels.
272
273	// Retrieve bandwidth for this local channel. If not
274	// available, assume this channel has enough bandwidth.
275	//
276	// TODO(joostjager): Possibly change to skipping this
277	// channel. The bandwidth hint is expected to be
278	// available.
279	bandwidth, ok := bandwidthHints.availableChanBandwidth(	3✔
280	edge.policy.ChannelID, amt,	3✔
281	)	3✔
282	if !ok {	3✔
UNCOV 283	log.Debugf("Cannot get bandwidth for edge %v, use max "+	×
UNCOV 284	"instead", edge.policy.ChannelID)	×
UNCOV 285	bandwidth = lnwire.MaxMilliSatoshi	×
UNCOV 286	}	×
287
288	// TODO(yy): if the above `!ok` is chosen, we'd have
289	// `bandwidth` to be the max value, which will end up having
290	// the `maxBandwidth` to be have the largest value and this
291	// edge will be the chosen one. This is wrong in two ways,
292	// 1. we need to understand why `availableChanBandwidth` cannot
293	// find bandwidth for this edge as something is wrong with this
294	// channel, and,
295	// 2. this edge is likely NOT the local channel with the
296	// highest available bandwidth.
297	//
298	// Skip channels that can't carry the payment.
299	if amt > bandwidth {	6✔
300	log.Debugf("Skipped edge %v: not enough bandwidth, "+	3✔
301	"bandwidth=%v, amt=%v", edge.policy.ChannelID,	3✔
302	bandwidth, amt)	3✔
303		3✔
304	continue	3✔
305	}
306
307	// We pick the local channel with the highest available
308	// bandwidth, to maximize the success probability. It can be
309	// that the channel state changes between querying the bandwidth
310	// hints and sending out the htlc.
311	if bandwidth < maxBandwidth {	3✔
UNCOV 312	log.Debugf("Skipped edge %v: not max bandwidth, "+	×
UNCOV 313	"bandwidth=%v, maxBandwidth=%v",	×
UNCOV 314	edge.policy.ChannelID, bandwidth, maxBandwidth)	×
UNCOV 315		×
UNCOV 316	continue	×
317	}
318	maxBandwidth = bandwidth	3✔
319		3✔
320	// Update best edge.	3✔
321	bestEdge = newUnifiedEdge(	3✔
322	edge.policy, edge.capacity, edge.inboundFees,	3✔
323	edge.hopPayloadSizeFn, edge.blindedPayment,	3✔
324	)	3✔
325	}
326
327	return bestEdge	3✔
328	}
329
330	// getEdgeNetwork returns the optimal unified edge to use for this connection
331	// given a specific amount to send. The goal is to return a unified edge with a
332	// policy that maximizes the probability of a successful forward in a non-strict
333	// forwarding context.
334	func (u *edgeUnifier) getEdgeNetwork(netAmtReceived lnwire.MilliSatoshi,
335	nextOutFee lnwire.MilliSatoshi) *unifiedEdge {	3✔
336		3✔
337	var (	3✔
338	bestPolicy *unifiedEdge	3✔
339	maxFee int64 = math.MinInt64	3✔
340	maxTimelock uint16	3✔
341	maxCapMsat lnwire.MilliSatoshi	3✔
342	hopPayloadSizeFn PayloadSizeFunc	3✔
343	)	3✔
344		3✔
345	for _, edge := range u.edges {	6✔
346	// Calculate the inbound fee charged at the receiving node.	3✔
347	inboundFee := calcCappedInboundFee(	3✔
348	edge, netAmtReceived, nextOutFee,	3✔
349	)	3✔
350		3✔
351	// Add inbound fee to get to the amount that is sent over the	3✔
352	// channel.	3✔
353	amt := netAmtReceived + lnwire.MilliSatoshi(inboundFee)	3✔
354		3✔
355	// Check valid amount range for the channel.	3✔
356	if !edge.amtInRange(amt) {	6✔
357	log.Debugf("Amount %v not in range for edge %v",	3✔
358	amt, edge.policy.ChannelID)	3✔
359	continue	3✔
360	}
361
362	// For network channels, skip the disabled ones.
363	edgeFlags := edge.policy.ChannelFlags	3✔
364	isDisabled := edgeFlags&lnwire.ChanUpdateDisabled != 0	3✔
365	if isDisabled {	3✔
UNCOV 366	log.Debugf("Skipped edge %v due to it being disabled",	×
UNCOV 367	edge.policy.ChannelID)	×
UNCOV 368	continue	×
369	}
370
371	// Track the maximal capacity for usable channels. If we don't
372	// know the capacity, we fall back to MaxHTLC.
373	capMsat := lnwire.NewMSatFromSatoshis(edge.capacity)	3✔
374	if capMsat == 0 && edge.policy.MessageFlags.HasMaxHtlc() {	3✔
UNCOV 375	log.Tracef("No capacity available for channel %v, "+	×
UNCOV 376	"using MaxHtlcMsat (%v) as a fallback.",	×
UNCOV 377	edge.policy.ChannelID, edge.policy.MaxHTLC)	×
UNCOV 378		×
UNCOV 379	capMsat = edge.policy.MaxHTLC	×
UNCOV 380	}	×
381	maxCapMsat = max(capMsat, maxCapMsat)	3✔
382		3✔
383	// Track the maximum time lock of all channels that are	3✔
384	// candidate for non-strict forwarding at the routing node.	3✔
385	maxTimelock = max(maxTimelock, edge.policy.TimeLockDelta)	3✔
386		3✔
387	outboundFee := int64(edge.policy.ComputeFee(amt))	3✔
388	fee := outboundFee + inboundFee	3✔
389		3✔
390	// Use the policy that results in the highest fee for this	3✔
391	// specific amount.	3✔
392	if fee < maxFee {	3✔
UNCOV 393	log.Debugf("Skipped edge %v due to it produces less "+	×
UNCOV 394	"fee: fee=%v, maxFee=%v",	×
UNCOV 395	edge.policy.ChannelID, fee, maxFee)	×
UNCOV 396		×
UNCOV 397	continue	×
398	}
399	maxFee = fee	3✔
400		3✔
401	bestPolicy = newUnifiedEdge(	3✔
402	edge.policy, 0, edge.inboundFees, nil,	3✔
403	edge.blindedPayment,	3✔
404	)	3✔
405		3✔
406	// The payload size function for edges to a connected peer is	3✔
407	// always the same hence there is not need to find the maximum.	3✔
408	// This also counts for blinded edges where we only have one	3✔
409	// edge to a blinded peer.	3✔
410	hopPayloadSizeFn = edge.hopPayloadSizeFn	3✔
411	}
412
413	// Return early if no channel matches.
414	if bestPolicy == nil {	6✔
415	return nil	3✔
416	}	3✔
417
418	// We have already picked the highest fee that could be required for
419	// non-strict forwarding. To also cover the case where a lower fee
420	// channel requires a longer time lock, we modify the policy by setting
421	// the maximum encountered time lock. Note that this results in a
422	// synthetic policy that is not actually present on the routing node.
423	//
424	// The reason we do this, is that we try to maximize the chance that we
425	// get forwarded. Because we penalize pair-wise, there won't be a second
426	// chance for this node pair. But this is all only needed for nodes that
427	// have distinct policies for channels to the same peer.
428	policyCopy := *bestPolicy.policy	3✔
429	policyCopy.TimeLockDelta = maxTimelock	3✔
430	modifiedEdge := newUnifiedEdge(	3✔
431	&policyCopy, maxCapMsat.ToSatoshis(), bestPolicy.inboundFees,	3✔
432	hopPayloadSizeFn, bestPolicy.blindedPayment,	3✔
433	)	3✔
434		3✔
435	return modifiedEdge	3✔
436	}
437
438	// minAmt returns the minimum amount that can be forwarded on this connection.
UNCOV 439	func (u *edgeUnifier) minAmt() lnwire.MilliSatoshi {	×
UNCOV 440	minAmount := lnwire.MaxMilliSatoshi	×
UNCOV 441	for _, edge := range u.edges {	×
UNCOV 442	minAmount = min(minAmount, edge.policy.MinHTLC)	×
UNCOV 443	}	×
444
UNCOV 445	return minAmount	×
446	}

lightningnetwork / lnd / 13566028875

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

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