11170835610

Committed 03 Oct 2024 10:41PM UTC coverage: 49.188% (-9.6%) from 58.738%

Build # 11170835610

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #9154 from ziggie1984/master

multi: bump btcd version.

Run Details

3 of 6 new or added lines in 6 files covered. (50.0%)

26110 existing lines in 428 files now uncovered.

97359 of 197934 relevant lines covered (49.19%)

1.04 hits per line

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

89.29

/lnwallet/update_log.go

package lnwallet

import (
        "github.com/lightningnetwork/lnd/fn"
)

// updateLog is an append-only log that stores updates to a node's commitment
// chain. This structure can be seen as the "mempool" within Lightning where
// changes are stored before they're committed to the chain. Once an entry has
// been committed in both the local and remote commitment chain, then it can be
// removed from this log.
//
// TODO(roasbeef): create lightning package, move commitment and update to
// package?
//   - also move state machine, separate from lnwallet package
//   - possible embed updateLog within commitmentChain.
type updateLog struct {
        // logIndex is a monotonically increasing integer that tracks the total
        // number of update entries ever applied to the log. When sending new
        // commitment states, we include all updates up to this index.
        logIndex uint64

        // htlcCounter is a monotonically increasing integer that tracks the
        // total number of offered HTLC's by the owner of this update log,
        // hence the `Add` update type. We use a distinct index for this
        // purpose, as update's that remove entries from the log will be
        // indexed using this counter.
        htlcCounter uint64

        // List is the updatelog itself, we embed this value so updateLog has
        // access to all the method of a list.List.
        *fn.List[*paymentDescriptor]

        // updateIndex maps a `logIndex` to a particular update entry. It
        // deals with the four update types:
        //   `Fail|MalformedFail|Settle|FeeUpdate`
        updateIndex map[uint64]*fn.Node[*paymentDescriptor]

        // htlcIndex maps a `htlcCounter` to an offered HTLC entry, hence the
        // `Add` update.
        htlcIndex map[uint64]*fn.Node[*paymentDescriptor]

        // modifiedHtlcs is a set that keeps track of all the current modified
        // htlcs, hence update types `Fail|MalformedFail|Settle`. A modified
        // HTLC is one that's present in the log, and has as a pending fail or
        // settle that's attempting to consume it.
        modifiedHtlcs fn.Set[uint64]
}

// newUpdateLog creates a new updateLog instance.
func newUpdateLog(logIndex, htlcCounter uint64) *updateLog {
        return &updateLog{
                List:          fn.NewList[*paymentDescriptor](),
                updateIndex:   make(map[uint64]*fn.Node[*paymentDescriptor]),
                htlcIndex:     make(map[uint64]*fn.Node[*paymentDescriptor]),
                logIndex:      logIndex,
                htlcCounter:   htlcCounter,
                modifiedHtlcs: fn.NewSet[uint64](),
        }
}

// restoreHtlc will "restore" a prior HTLC to the updateLog. We say restore as
// this method is intended to be used when re-covering a prior commitment
// state. This function differs from appendHtlc in that it won't increment
// either of log's counters. If the HTLC is already present, then it is
// ignored.
func (u *updateLog) restoreHtlc(pd *paymentDescriptor) {
        if _, ok := u.htlcIndex[pd.HtlcIndex]; ok {
                return
        }

        u.htlcIndex[pd.HtlcIndex] = u.PushBack(pd)
}

// appendUpdate appends a new update to the tip of the updateLog. The entry is
// also added to index accordingly.
func (u *updateLog) appendUpdate(pd *paymentDescriptor) {
        u.updateIndex[u.logIndex] = u.PushBack(pd)
        u.logIndex++
}

// restoreUpdate appends a new update to the tip of the updateLog. The entry is
// also added to index accordingly. This function differs from appendUpdate in
// that it won't increment the log index counter.
func (u *updateLog) restoreUpdate(pd *paymentDescriptor) {
        u.updateIndex[pd.LogIndex] = u.PushBack(pd)
}

// appendHtlc appends a new HTLC offer to the tip of the update log. The entry
// is also added to the offer index accordingly.
func (u *updateLog) appendHtlc(pd *paymentDescriptor) {
        u.htlcIndex[u.htlcCounter] = u.PushBack(pd)
        u.htlcCounter++

        u.logIndex++
}

// lookupHtlc attempts to look up an offered HTLC according to its offer
// index. If the entry isn't found, then a nil pointer is returned.
func (u *updateLog) lookupHtlc(i uint64) *paymentDescriptor {
        htlc, ok := u.htlcIndex[i]
        if !ok {
                return nil
        }

        return htlc.Value
}

// remove attempts to remove an entry from the update log. If the entry is
// found, then the entry will be removed from the update log and index.
func (u *updateLog) removeUpdate(i uint64) {
        entry := u.updateIndex[i]
        u.Remove(entry)
        delete(u.updateIndex, i)
}

// removeHtlc attempts to remove an HTLC offer form the update log. If the
// entry is found, then the entry will be removed from both the main log and
// the offer index.
func (u *updateLog) removeHtlc(i uint64) {
        entry := u.htlcIndex[i]
        u.Remove(entry)
        delete(u.htlcIndex, i)

        u.modifiedHtlcs.Remove(i)
}

// htlcHasModification returns true if the HTLC identified by the passed index
// has a pending modification within the log.
func (u *updateLog) htlcHasModification(i uint64) bool {
        return u.modifiedHtlcs.Contains(i)
}

// markHtlcModified marks an HTLC as modified based on its HTLC index. After a
// call to this method, htlcHasModification will return true until the HTLC is
// removed.
func (u *updateLog) markHtlcModified(i uint64) {
        u.modifiedHtlcs.Add(i)
}

// compactLogs performs garbage collection within the log removing HTLCs which
// have been removed from the point-of-view of the tail of both chains. The
// entries which timeout/settle HTLCs are also removed.
func compactLogs(ourLog, theirLog *updateLog,
        localChainTail, remoteChainTail uint64) {

        compactLog := func(logA, logB *updateLog) {
                var nextA *fn.Node[*paymentDescriptor]
                for e := logA.Front(); e != nil; e = nextA {
                        // Assign next iteration element at top of loop because
                        // we may remove the current element from the list,
                        // which can change the iterated sequence.
                        nextA = e.Next()

                        htlc := e.Value

                        // We skip Adds, as they will be removed along with the
                        // fail/settles below.
                        if htlc.EntryType == Add {
                                continue
                        }

                        // If the HTLC hasn't yet been removed from either
                        // chain, the skip it.
                        if htlc.removeCommitHeightRemote == 0 ||
                                htlc.removeCommitHeightLocal == 0 {

                                continue
                        }

                        // Otherwise if the height of the tail of both chains
                        // is at least the height in which the HTLC was
                        // removed, then evict the settle/timeout entry along
                        // with the original add entry.
                        if remoteChainTail >= htlc.removeCommitHeightRemote &&
                                localChainTail >= htlc.removeCommitHeightLocal {

                                // Fee updates have no parent htlcs, so we only
                                // remove the update itself.
                                if htlc.EntryType == FeeUpdate {
                                        logA.removeUpdate(htlc.LogIndex)
                                        continue
                                }

                                // The other types (fail/settle) do have a
                                // parent HTLC, so we'll remove that HTLC from
                                // the other log.
                                logA.removeUpdate(htlc.LogIndex)
                                logB.removeHtlc(htlc.ParentIndex)
                        }
                }
        }

        compactLog(ourLog, theirLog)
        compactLog(theirLog, ourLog)
}

1	package lnwallet
2
3	import (
4	"github.com/lightningnetwork/lnd/fn"
5	)
6
7	// updateLog is an append-only log that stores updates to a node's commitment
8	// chain. This structure can be seen as the "mempool" within Lightning where
9	// changes are stored before they're committed to the chain. Once an entry has
10	// been committed in both the local and remote commitment chain, then it can be
11	// removed from this log.
12	//
13	// TODO(roasbeef): create lightning package, move commitment and update to
14	// package?
15	// - also move state machine, separate from lnwallet package
16	// - possible embed updateLog within commitmentChain.
17	type updateLog struct {
18	// logIndex is a monotonically increasing integer that tracks the total
19	// number of update entries ever applied to the log. When sending new
20	// commitment states, we include all updates up to this index.
21	logIndex uint64
22
23	// htlcCounter is a monotonically increasing integer that tracks the
24	// total number of offered HTLC's by the owner of this update log,
25	// hence the `Add` update type. We use a distinct index for this
26	// purpose, as update's that remove entries from the log will be
27	// indexed using this counter.
28	htlcCounter uint64
29
30	// List is the updatelog itself, we embed this value so updateLog has
31	// access to all the method of a list.List.
32	fn.List[paymentDescriptor]
33
34	// updateIndex maps a `logIndex` to a particular update entry. It
35	// deals with the four update types:
36	// `Fail\|MalformedFail\|Settle\|FeeUpdate`
37	updateIndex map[uint64]fn.Node[paymentDescriptor]
38
39	// htlcIndex maps a `htlcCounter` to an offered HTLC entry, hence the
40	// `Add` update.
41	htlcIndex map[uint64]fn.Node[paymentDescriptor]
42
43	// modifiedHtlcs is a set that keeps track of all the current modified
44	// htlcs, hence update types `Fail\|MalformedFail\|Settle`. A modified
45	// HTLC is one that's present in the log, and has as a pending fail or
46	// settle that's attempting to consume it.
47	modifiedHtlcs fn.Set[uint64]
48	}
49
50	// newUpdateLog creates a new updateLog instance.
51	func newUpdateLog(logIndex, htlcCounter uint64) *updateLog {	2✔
52	return &updateLog{	2✔
53	List: fn.NewList[*paymentDescriptor](),	2✔
54	updateIndex: make(map[uint64]fn.Node[paymentDescriptor]),	2✔
55	htlcIndex: make(map[uint64]fn.Node[paymentDescriptor]),	2✔
56	logIndex: logIndex,	2✔
57	htlcCounter: htlcCounter,	2✔
58	modifiedHtlcs: fn.NewSet[uint64](),	2✔
59	}	2✔
60	}	2✔
61
62	// restoreHtlc will "restore" a prior HTLC to the updateLog. We say restore as
63	// this method is intended to be used when re-covering a prior commitment
64	// state. This function differs from appendHtlc in that it won't increment
65	// either of log's counters. If the HTLC is already present, then it is
66	// ignored.
67	func (u updateLog) restoreHtlc(pd paymentDescriptor) {	2✔
68	if _, ok := u.htlcIndex[pd.HtlcIndex]; ok {	2✔
69	return	×
70	}	×
71
72	u.htlcIndex[pd.HtlcIndex] = u.PushBack(pd)	2✔
73	}
74
75	// appendUpdate appends a new update to the tip of the updateLog. The entry is
76	// also added to index accordingly.
77	func (u updateLog) appendUpdate(pd paymentDescriptor) {	2✔
78	u.updateIndex[u.logIndex] = u.PushBack(pd)	2✔
79	u.logIndex++	2✔
80	}	2✔
81
82	// restoreUpdate appends a new update to the tip of the updateLog. The entry is
83	// also added to index accordingly. This function differs from appendUpdate in
84	// that it won't increment the log index counter.
UNCOV 85	func (u updateLog) restoreUpdate(pd paymentDescriptor) {	×
UNCOV 86	u.updateIndex[pd.LogIndex] = u.PushBack(pd)	×
UNCOV 87	}	×
88
89	// appendHtlc appends a new HTLC offer to the tip of the update log. The entry
90	// is also added to the offer index accordingly.
91	func (u updateLog) appendHtlc(pd paymentDescriptor) {	2✔
92	u.htlcIndex[u.htlcCounter] = u.PushBack(pd)	2✔
93	u.htlcCounter++	2✔
94		2✔
95	u.logIndex++	2✔
96	}	2✔
97
98	// lookupHtlc attempts to look up an offered HTLC according to its offer
99	// index. If the entry isn't found, then a nil pointer is returned.
100	func (u updateLog) lookupHtlc(i uint64) paymentDescriptor {	2✔
101	htlc, ok := u.htlcIndex[i]	2✔
102	if !ok {	2✔
UNCOV 103	return nil	×
UNCOV 104	}	×
105
106	return htlc.Value	2✔
107	}
108
109	// remove attempts to remove an entry from the update log. If the entry is
110	// found, then the entry will be removed from the update log and index.
111	func (u *updateLog) removeUpdate(i uint64) {	2✔
112	entry := u.updateIndex[i]	2✔
113	u.Remove(entry)	2✔
114	delete(u.updateIndex, i)	2✔
115	}	2✔
116
117	// removeHtlc attempts to remove an HTLC offer form the update log. If the
118	// entry is found, then the entry will be removed from both the main log and
119	// the offer index.
120	func (u *updateLog) removeHtlc(i uint64) {	2✔
121	entry := u.htlcIndex[i]	2✔
122	u.Remove(entry)	2✔
123	delete(u.htlcIndex, i)	2✔
124		2✔
125	u.modifiedHtlcs.Remove(i)	2✔
126	}	2✔
127
128	// htlcHasModification returns true if the HTLC identified by the passed index
129	// has a pending modification within the log.
130	func (u *updateLog) htlcHasModification(i uint64) bool {	2✔
131	return u.modifiedHtlcs.Contains(i)	2✔
132	}	2✔
133
134	// markHtlcModified marks an HTLC as modified based on its HTLC index. After a
135	// call to this method, htlcHasModification will return true until the HTLC is
136	// removed.
137	func (u *updateLog) markHtlcModified(i uint64) {	2✔
138	u.modifiedHtlcs.Add(i)	2✔
139	}	2✔
140
141	// compactLogs performs garbage collection within the log removing HTLCs which
142	// have been removed from the point-of-view of the tail of both chains. The
143	// entries which timeout/settle HTLCs are also removed.
144	func compactLogs(ourLog, theirLog *updateLog,
145	localChainTail, remoteChainTail uint64) {	2✔
146		2✔
147	compactLog := func(logA, logB *updateLog) {	4✔
148	var nextA fn.Node[paymentDescriptor]	2✔
149	for e := logA.Front(); e != nil; e = nextA {	4✔
150	// Assign next iteration element at top of loop because	2✔
151	// we may remove the current element from the list,	2✔
152	// which can change the iterated sequence.	2✔
153	nextA = e.Next()	2✔
154		2✔
155	htlc := e.Value	2✔
156		2✔
157	// We skip Adds, as they will be removed along with the	2✔
158	// fail/settles below.	2✔
159	if htlc.EntryType == Add {	4✔
160	continue	2✔
161	}
162
163	// If the HTLC hasn't yet been removed from either
164	// chain, the skip it.
165	if htlc.removeCommitHeightRemote == 0 \|\|	2✔
166	htlc.removeCommitHeightLocal == 0 {	4✔
167		2✔
168	continue	2✔
169	}
170
171	// Otherwise if the height of the tail of both chains
172	// is at least the height in which the HTLC was
173	// removed, then evict the settle/timeout entry along
174	// with the original add entry.
175	if remoteChainTail >= htlc.removeCommitHeightRemote &&	2✔
176	localChainTail >= htlc.removeCommitHeightLocal {	4✔
177		2✔
178	// Fee updates have no parent htlcs, so we only	2✔
179	// remove the update itself.	2✔
180	if htlc.EntryType == FeeUpdate {	2✔
UNCOV 181	logA.removeUpdate(htlc.LogIndex)	×
UNCOV 182	continue	×
183	}
184
185	// The other types (fail/settle) do have a
186	// parent HTLC, so we'll remove that HTLC from
187	// the other log.
188	logA.removeUpdate(htlc.LogIndex)	2✔
189	logB.removeHtlc(htlc.ParentIndex)	2✔
190	}
191	}
192	}
193
194	compactLog(ourLog, theirLog)	2✔
195	compactLog(theirLog, ourLog)	2✔
196	}

lightningnetwork / lnd / 11170835610

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