13211764208

Committed 08 Feb 2025 03:08AM UTC coverage: 49.288% (-9.5%) from 58.815%

Build # 13211764208

Build Type

Pull #9489

github

Committed by

calvinrzachman

Commit Message

itest: verify switchrpc server enforces send then track

We prevent the rpc server from allowing onion dispatches for
attempt IDs which have already been tracked by rpc clients.

This helps protect the client from leaking a duplicate onion
attempt. NOTE: This is not the only method for solving this
issue! The issue could be addressed via careful client side
programming which accounts for the uncertainty and async
nature of dispatching onions to a remote process via RPC.
This would require some lnd ChannelRouter changes for how
we intend to use these RPCs though.

Pull Request Pull Request #9489: multi: add BuildOnion, SendOnion, and TrackOnion RPCs

Run Details

474 of 990 new or added lines in 11 files covered. (47.88%)

27321 existing lines in 435 files now uncovered.

101192 of 205306 relevant lines covered (49.29%)

1.54 hits per line

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

45.22

/watchtower/wtdb/range_index.go

package wtdb

import (
        "fmt"
        "sync"
)

// rangeItem represents the start and end values of a range.
type rangeItem struct {
        start uint64
        end   uint64
}

// RangeIndexOption describes the signature of a functional option that can be
// used to modify the behaviour of a RangeIndex.
type RangeIndexOption func(*RangeIndex)

// WithSerializeUint64Fn is a functional option that can be used to set the
// function to be used to do the serialization of a uint64 into a byte slice.
func WithSerializeUint64Fn(fn func(uint64) ([]byte, error)) RangeIndexOption {
        return func(index *RangeIndex) {
                index.serializeUint64 = fn
        }
}

// RangeIndex can be used to keep track of which numbers have been added to a
// set. It does so by keeping track of a sorted list of rangeItems. Each
// rangeItem has a start and end value of a range where all values in-between
// have been added to the set. It works well in situations where it is expected
// numbers in the set are not sparse.
type RangeIndex struct {
        // set is a sorted list of rangeItem.
        set []rangeItem

        // mu is used to ensure safe access to set.
        mu sync.Mutex

        // serializeUint64 is the function that can be used to convert a uint64
        // to a byte slice.
        serializeUint64 func(uint64) ([]byte, error)
}

// NewRangeIndex constructs a new RangeIndex. An initial set of ranges may be
// passed to the function in the form of a map.
func NewRangeIndex(ranges map[uint64]uint64,
        opts ...RangeIndexOption) (*RangeIndex, error) {

        index := &RangeIndex{
                serializeUint64: defaultSerializeUint64,
                set:             make([]rangeItem, 0),
        }

        // Apply any functional options.
        for _, o := range opts {
                o(index)
        }

        for s, e := range ranges {
                if err := index.addRange(s, e); err != nil {
                        return nil, err
                }
        }

        return index, nil
}

// addRange can be used to add an entire new range to the set. This method
// should only ever be called by NewRangeIndex to initialise the in-memory
// structure and so the RangeIndex mutex is not held during this method.
func (a *RangeIndex) addRange(start, end uint64) error {
        // Check that the given range is valid.
        if start > end {
                return fmt.Errorf("invalid range. Start height %d is larger "+
                        "than end height %d", start, end)
        }

        // min is a helper closure that will return the minimum of two uint64s.
        min := func(a, b uint64) uint64 {
                if a < b {
                        return a
                }

                return b
        }

        // max is a helper closure that will return the maximum of two uint64s.
        max := func(a, b uint64) uint64 {
                if a > b {
                        return a
                }

                return b
        }

        // Collect the ranges that fall before and after the new range along
        // with the start and end values of the new range.
        var before, after []rangeItem
        for _, x := range a.set {
                // If the new start value can't extend the current ranges end
                // value, then the two cannot be merged. The range is added to
                // the group of ranges that fall before the new range.
                if x.end+1 < start {
                        before = append(before, x)
                        continue
                }

                // If the current ranges start value does not follow on directly
                // from the new end value, then the two cannot be merged. The
                // range is added to the group of ranges that fall after the new
                // range.
                if end+1 < x.start {
                        after = append(after, x)
                        continue
                }

                // Otherwise, there is an overlap and so the two can be merged.
                start = min(start, x.start)
                end = max(end, x.end)
        }

        // Re-construct the range index set.
        a.set = append(append(before, rangeItem{
                start: start,
                end:   end,
        }), after...)

        return nil
}

// IsInIndex returns true if the given number is in the range set.
func (a *RangeIndex) IsInIndex(n uint64) bool {
        a.mu.Lock()
        defer a.mu.Unlock()

        _, isCovered := a.lowerBoundIndex(n)

        return isCovered
}

// NumInSet returns the number of items covered by the range set.
func (a *RangeIndex) NumInSet() uint64 {
        a.mu.Lock()
        defer a.mu.Unlock()

        var numItems uint64
        for _, r := range a.set {
                numItems += r.end - r.start + 1
        }

        return numItems
}

// MaxHeight returns the highest number covered in the range.
func (a *RangeIndex) MaxHeight() uint64 {
        a.mu.Lock()
        defer a.mu.Unlock()

        if len(a.set) == 0 {
                return 0
        }

        return a.set[len(a.set)-1].end
}

// GetAllRanges returns a copy of the range set in the form of a map.
func (a *RangeIndex) GetAllRanges() map[uint64]uint64 {
        a.mu.Lock()
        defer a.mu.Unlock()

        cp := make(map[uint64]uint64, len(a.set))
        for _, item := range a.set {
                cp[item.start] = item.end
        }

        return cp
}

// lowerBoundIndex returns the index of the RangeIndex that is most appropriate
// for the new value, n. In other words, it returns the index of the rangeItem
// set of the range where the start value is the highest start value in the set
// that is still lower than or equal to the given number, n. The returned
// boolean is true if the given number is already covered in the RangeIndex.
// A returned index of -1 indicates that no lower bound range exists in the set.
// Since the most likely case is that the new number will just extend the
// highest range, a check is first done to see if this is the case which will
// make the methods' computational complexity O(1). Otherwise, a binary search
// is done which brings the computational complexity to O(log N).
func (a *RangeIndex) lowerBoundIndex(n uint64) (int, bool) {
        // If the set is empty, then there is no such index and the value
        // definitely is not in the set.
        if len(a.set) == 0 {
                return -1, false
        }

        // In most cases, the last index item will be the one we want. So just
        // do a quick check on that index first to avoid doing the binary
        // search.
        lastIndex := len(a.set) - 1
        lastRange := a.set[lastIndex]
        if lastRange.start <= n {
                return lastIndex, lastRange.end >= n
        }

        // Otherwise, do a binary search to find the index of interest.
        var (
                low        = 0
                high       = len(a.set) - 1
                rangeIndex = -1
        )
        for {
                mid := (low + high) / 2
                currentRange := a.set[mid]

                switch {
                case currentRange.start > n:
                        // If the start of the range is greater than n, we can
                        // completely cut out that entire part of the array.
                        high = mid

                case currentRange.start < n:
                        // If the range already includes the given height, we
                        // can stop searching now.
                        if currentRange.end >= n {
                                return mid, true
                        }

                        // If the start of the range is smaller than n, we can
                        // store this as the new best index to return.
                        rangeIndex = mid

                        // If low and mid are already equal, then increment low
                        // by 1. Exit if this means that low is now greater than
                        // high.
                        if low == mid {
                                low = mid + 1
                                if low > high {
                                        return rangeIndex, false
                                }
                        } else {
                                low = mid
                        }

                        continue

                default:
                        // If the height is equal to the start value of the
                        // current range that mid is pointing to, then the
                        // height is already covered.
                        return mid, true
                }

                // Exit if we have checked all the ranges.
                if low == high {
                        break
                }
        }

        return rangeIndex, false
}

// KVStore is an interface representing a key-value store.
type KVStore interface {
        // Put saves the specified key/value pair to the store. Keys that do not
        // already exist are added and keys that already exist are overwritten.
        Put(key, value []byte) error

        // Delete removes the specified key from the bucket. Deleting a key that
        // does not exist does not return an error.
        Delete(key []byte) error
}

// Add adds a single number to the range set. It first attempts to apply the
// necessary changes to the passed KV store and then only if this succeeds, will
// the changes be applied to the in-memory structure.
func (a *RangeIndex) Add(newHeight uint64, kv KVStore) error {
        a.mu.Lock()
        defer a.mu.Unlock()

        // Compute the changes that will need to be applied to both the sorted
        // rangeItem array representation and the key-value store representation
        // of the range index.
        arrayChanges, kvStoreChanges := a.getChanges(newHeight)

        // First attempt to apply the KV store changes. Only if this succeeds
        // will we apply the changes to our in-memory range index structure.
        err := a.applyKVChanges(kv, kvStoreChanges)
        if err != nil {
                return err
        }

        // Since the DB changes were successful, we can now commit the
        // changes to our in-memory representation of the range set.
        a.applyArrayChanges(arrayChanges)

        return nil
}

// applyKVChanges applies the given set of kvChanges to a KV store. It is
// assumed that a transaction is being held on the kv store so that if any
// of the actions of the function fails, the changes will be reverted.
func (a *RangeIndex) applyKVChanges(kv KVStore, changes *kvChanges) error {
        // Exit early if there are no changes to apply.
        if kv == nil || changes == nil {
                return nil
        }

        // Check if any range pair needs to be deleted.
        if changes.deleteKVKey != nil {
                del, err := a.serializeUint64(*changes.deleteKVKey)
                if err != nil {
                        return err
                }

                if err := kv.Delete(del); err != nil {
                        return err
                }
        }

        start, err := a.serializeUint64(changes.key)
        if err != nil {
                return err
        }

        end, err := a.serializeUint64(changes.value)
        if err != nil {
                return err
        }

        return kv.Put(start, end)
}

// applyArrayChanges applies the given arrayChanges to the in-memory RangeIndex
// itself. This should only be done once the persisted kv store changes have
// already been applied.
func (a *RangeIndex) applyArrayChanges(changes *arrayChanges) {
        if changes == nil {
                return
        }

        if changes.indexToDelete != nil {
                a.set = append(
                        a.set[:*changes.indexToDelete],
                        a.set[*changes.indexToDelete+1:]...,
                )
        }

        if changes.newIndex != nil {
                switch {
                case *changes.newIndex == 0:
                        a.set = append([]rangeItem{{
                                start: changes.start,
                                end:   changes.end,
                        }}, a.set...)

                case *changes.newIndex == len(a.set):
                        a.set = append(a.set, rangeItem{
                                start: changes.start,
                                end:   changes.end,
                        })

                default:
                        a.set = append(
                                a.set[:*changes.newIndex+1],
                                a.set[*changes.newIndex:]...,
                        )
                        a.set[*changes.newIndex] = rangeItem{
                                start: changes.start,
                                end:   changes.end,
                        }
                }

                return
        }

        if changes.indexToEdit != nil {
                a.set[*changes.indexToEdit] = rangeItem{
                        start: changes.start,
                        end:   changes.end,
                }
        }
}

// arrayChanges encompasses the diff to apply to the sorted rangeItem array
// representation of a range index. Such a diff will either include adding a
// new range or editing an existing range. If an existing range is edited, then
// the diff might also include deleting an index (this will be the case if the
// editing of the one range results in the merge of another range).
type arrayChanges struct {
        start uint64
        end   uint64

        // newIndex, if set, is the index of the in-memory range array where a
        // new range, [start:end], should be added. newIndex should never be
        // set at the same time as indexToEdit or indexToDelete.
        newIndex *int

        // indexToDelete, if set, is the index of the sorted rangeItem array
        // that should be deleted. This should be applied before reading the
        // index value of indexToEdit. This should not be set at the same time
        // as newIndex.
        indexToDelete *int

        // indexToEdit is the index of the in-memory range array that should be
        // edited. The range at this index will be changed to [start:end]. This
        // should only be read after indexToDelete index has been deleted.
        indexToEdit *int
}

// kvChanges encompasses the diff to apply to a KV-store representation of a
// range index. A kv-store diff for the addition of a single number to the range
// index will include either a brand new key-value pair or the altering of the
// value of an existing key. Optionally, the diff may also include the deletion
// of an existing key. A deletion will be required if the addition of the new
// number results in the merge of two ranges.
type kvChanges struct {
        key   uint64
        value uint64

        // deleteKVKey, if set, is the key of the kv store representation that
        // should be deleted.
        deleteKVKey *uint64
}

// getChanges will calculate and return the changes that need to be applied to
// both the sorted-rangeItem-array representation and the key-value store
// representation of the range index.
func (a *RangeIndex) getChanges(n uint64) (*arrayChanges, *kvChanges) {
        // If the set is empty then a new range item is added.
        if len(a.set) == 0 {
                // For the array representation, a new range [n:n] is added to
                // the first index of the array.
                firstIndex := 0
                ac := &arrayChanges{
                        newIndex: &firstIndex,
                        start:    n,
                        end:      n,
                }

                // For the KV representation, a new [n:n] pair is added.
                kvc := &kvChanges{
                        key:   n,
                        value: n,
                }

                return ac, kvc
        }

        // Find the index of the lower bound range to the new number.
        indexOfRangeBelow, alreadyCovered := a.lowerBoundIndex(n)

        switch {
        // The new number is already covered by the range index. No changes are
        // required.
        case alreadyCovered:
                return nil, nil

        // No lower bound index exists.
        case indexOfRangeBelow < 0:
                // Check if the very first range can be merged into this new
                // one.
                if n+1 == a.set[0].start {
                        // If so, the two ranges can be merged and so the start
                        // value of the range is n and the end value is the end
                        // of the existing first range.
                        start := n
                        end := a.set[0].end

                        // For the array representation, we can just edit the
                        // first entry of the array
                        editIndex := 0
                        ac := &arrayChanges{
                                indexToEdit: &editIndex,
                                start:       start,
                                end:         end,
                        }

                        // For the KV store representation, we add a new kv pair
                        // and delete the range with the key equal to the start
                        // value of the range we are merging.
                        kvKeyToDelete := a.set[0].start
                        kvc := &kvChanges{
                                key:         start,
                                value:       end,
                                deleteKVKey: &kvKeyToDelete,
                        }

                        return ac, kvc
                }

                // Otherwise, we add a new index.

                // For the array representation, a new range [n:n] is added to
                // the first index of the array.
                newIndex := 0
                ac := &arrayChanges{
                        newIndex: &newIndex,
                        start:    n,
                        end:      n,
                }

                // For the KV representation, a new [n:n] pair is added.
                kvc := &kvChanges{
                        key:   n,
                        value: n,
                }

                return ac, kvc

        // A lower range does exist, and it can be extended to include this new
        // number.
        case a.set[indexOfRangeBelow].end+1 == n:
                start := a.set[indexOfRangeBelow].start
                end := n
                indexToChange := indexOfRangeBelow

                // If there are no intervals above this one or if there are, but
                // they can't be merged into this one then we just need to edit
                // this interval.
                if indexOfRangeBelow == len(a.set)-1 ||
                        a.set[indexOfRangeBelow+1].start != n+1 {

                        // For the array representation, we just edit the index.
                        ac := &arrayChanges{
                                indexToEdit: &indexToChange,
                                start:       start,
                                end:         end,
                        }

                        // For the key-value representation, we just overwrite
                        // the end value at the existing start key.
                        kvc := &kvChanges{
                                key:   start,
                                value: end,
                        }

                        return ac, kvc
                }

                // There is a range above this one that we need to merge into
                // this one.
                delIndex := indexOfRangeBelow + 1
                end = a.set[delIndex].end

                // For the array representation, we delete the range above this
                // one and edit this range to include the end value of the range
                // above.
                ac := &arrayChanges{
                        indexToDelete: &delIndex,
                        indexToEdit:   &indexToChange,
                        start:         start,
                        end:           end,
                }

                // For the kv representation, we tweak the end value of an
                // existing key and delete the key of the range we are deleting.
                deleteKey := a.set[delIndex].start
                kvc := &kvChanges{
                        key:         start,
                        value:       end,
                        deleteKVKey: &deleteKey,
                }

                return ac, kvc

        // A lower range does exist, but it can't be extended to include this
        // new number, and so we need to add a new range after the lower bound
        // range.
        default:
                newIndex := indexOfRangeBelow + 1

                // If there are no ranges above this new one or if there are,
                // but they can't be merged into this new one, then we can just
                // add the new one as is.
                if newIndex == len(a.set) || a.set[newIndex].start != n+1 {
                        ac := &arrayChanges{
                                newIndex: &newIndex,
                                start:    n,
                                end:      n,
                        }

                        kvc := &kvChanges{
                                key:   n,
                                value: n,
                        }

                        return ac, kvc
                }

                // Else, we merge the above index.
                start := n
                end := a.set[newIndex].end
                toEdit := newIndex

                // For the array representation, we edit the range above to
                // include the new start value.
                ac := &arrayChanges{
                        indexToEdit: &toEdit,
                        start:       start,
                        end:         end,
                }

                // For the kv representation, we insert the new start-end key
                // value pair and delete the key using the old start value.
                delKey := a.set[newIndex].start
                kvc := &kvChanges{
                        key:         start,
                        value:       end,
                        deleteKVKey: &delKey,
                }

                return ac, kvc
        }
}

func defaultSerializeUint64(i uint64) ([]byte, error) {
        var b [8]byte
        byteOrder.PutUint64(b[:], i)
        return b[:], nil
}

1	package wtdb
2
3	import (
4	"fmt"
5	"sync"
6	)
7
8	// rangeItem represents the start and end values of a range.
9	type rangeItem struct {
10	start uint64
11	end uint64
12	}
13
14	// RangeIndexOption describes the signature of a functional option that can be
15	// used to modify the behaviour of a RangeIndex.
16	type RangeIndexOption func(*RangeIndex)
17
18	// WithSerializeUint64Fn is a functional option that can be used to set the
19	// function to be used to do the serialization of a uint64 into a byte slice.
20	func WithSerializeUint64Fn(fn func(uint64) ([]byte, error)) RangeIndexOption {	3✔
21	return func(index *RangeIndex) {	6✔
22	index.serializeUint64 = fn	3✔
23	}	3✔
24	}
25
26	// RangeIndex can be used to keep track of which numbers have been added to a
27	// set. It does so by keeping track of a sorted list of rangeItems. Each
28	// rangeItem has a start and end value of a range where all values in-between
29	// have been added to the set. It works well in situations where it is expected
30	// numbers in the set are not sparse.
31	type RangeIndex struct {
32	// set is a sorted list of rangeItem.
33	set []rangeItem
34
35	// mu is used to ensure safe access to set.
36	mu sync.Mutex
37
38	// serializeUint64 is the function that can be used to convert a uint64
39	// to a byte slice.
40	serializeUint64 func(uint64) ([]byte, error)
41	}
42
43	// NewRangeIndex constructs a new RangeIndex. An initial set of ranges may be
44	// passed to the function in the form of a map.
45	func NewRangeIndex(ranges map[uint64]uint64,
46	opts ...RangeIndexOption) (*RangeIndex, error) {	3✔
47		3✔
48	index := &RangeIndex{	3✔
49	serializeUint64: defaultSerializeUint64,	3✔
50	set: make([]rangeItem, 0),	3✔
51	}	3✔
52		3✔
53	// Apply any functional options.	3✔
54	for _, o := range opts {	6✔
55	o(index)	3✔
56	}	3✔
57
58	for s, e := range ranges {	6✔
59	if err := index.addRange(s, e); err != nil {	3✔
UNCOV 60	return nil, err	×
UNCOV 61	}	×
62	}
63
64	return index, nil	3✔
65	}
66
67	// addRange can be used to add an entire new range to the set. This method
68	// should only ever be called by NewRangeIndex to initialise the in-memory
69	// structure and so the RangeIndex mutex is not held during this method.
70	func (a *RangeIndex) addRange(start, end uint64) error {	3✔
71	// Check that the given range is valid.	3✔
72	if start > end {	3✔
UNCOV 73	return fmt.Errorf("invalid range. Start height %d is larger "+	×
UNCOV 74	"than end height %d", start, end)	×
UNCOV 75	}	×
76
77	// min is a helper closure that will return the minimum of two uint64s.
78	min := func(a, b uint64) uint64 {	3✔
UNCOV 79	if a < b {	×
80	return a	×
81	}	×
82
UNCOV 83	return b	×
84	}
85
86	// max is a helper closure that will return the maximum of two uint64s.
87	max := func(a, b uint64) uint64 {	3✔
UNCOV 88	if a > b {	×
UNCOV 89	return a	×
UNCOV 90	}	×
91
92	return b	×
93	}
94
95	// Collect the ranges that fall before and after the new range along
96	// with the start and end values of the new range.
97	var before, after []rangeItem	3✔
98	for _, x := range a.set {	6✔
99	// If the new start value can't extend the current ranges end	3✔
100	// value, then the two cannot be merged. The range is added to	3✔
101	// the group of ranges that fall before the new range.	3✔
102	if x.end+1 < start {	6✔
103	before = append(before, x)	3✔
104	continue	3✔
105	}
106
107	// If the current ranges start value does not follow on directly
108	// from the new end value, then the two cannot be merged. The
109	// range is added to the group of ranges that fall after the new
110	// range.
111	if end+1 < x.start {	2✔
112	after = append(after, x)	1✔
113	continue	1✔
114	}
115
116	// Otherwise, there is an overlap and so the two can be merged.
UNCOV 117	start = min(start, x.start)	×
UNCOV 118	end = max(end, x.end)	×
119	}
120
121	// Re-construct the range index set.
122	a.set = append(append(before, rangeItem{	3✔
123	start: start,	3✔
124	end: end,	3✔
125	}), after...)	3✔
126		3✔
127	return nil	3✔
128	}
129
130	// IsInIndex returns true if the given number is in the range set.
UNCOV 131	func (a *RangeIndex) IsInIndex(n uint64) bool {	×
UNCOV 132	a.mu.Lock()	×
UNCOV 133	defer a.mu.Unlock()	×
UNCOV 134		×
UNCOV 135	_, isCovered := a.lowerBoundIndex(n)	×
UNCOV 136		×
UNCOV 137	return isCovered	×
UNCOV 138	}	×
139
140	// NumInSet returns the number of items covered by the range set.
141	func (a *RangeIndex) NumInSet() uint64 {	3✔
142	a.mu.Lock()	3✔
143	defer a.mu.Unlock()	3✔
144		3✔
145	var numItems uint64	3✔
146	for _, r := range a.set {	6✔
147	numItems += r.end - r.start + 1	3✔
148	}	3✔
149
150	return numItems	3✔
151	}
152
153	// MaxHeight returns the highest number covered in the range.
UNCOV 154	func (a *RangeIndex) MaxHeight() uint64 {	×
UNCOV 155	a.mu.Lock()	×
UNCOV 156	defer a.mu.Unlock()	×
UNCOV 157		×
UNCOV 158	if len(a.set) == 0 {	×
159	return 0	×
160	}	×
161
UNCOV 162	return a.set[len(a.set)-1].end	×
163	}
164
165	// GetAllRanges returns a copy of the range set in the form of a map.
UNCOV 166	func (a *RangeIndex) GetAllRanges() map[uint64]uint64 {	×
UNCOV 167	a.mu.Lock()	×
UNCOV 168	defer a.mu.Unlock()	×
UNCOV 169		×
UNCOV 170	cp := make(map[uint64]uint64, len(a.set))	×
UNCOV 171	for _, item := range a.set {	×
UNCOV 172	cp[item.start] = item.end	×
UNCOV 173	}	×
174
UNCOV 175	return cp	×
176	}
177
178	// lowerBoundIndex returns the index of the RangeIndex that is most appropriate
179	// for the new value, n. In other words, it returns the index of the rangeItem
180	// set of the range where the start value is the highest start value in the set
181	// that is still lower than or equal to the given number, n. The returned
182	// boolean is true if the given number is already covered in the RangeIndex.
183	// A returned index of -1 indicates that no lower bound range exists in the set.
184	// Since the most likely case is that the new number will just extend the
185	// highest range, a check is first done to see if this is the case which will
186	// make the methods' computational complexity O(1). Otherwise, a binary search
187	// is done which brings the computational complexity to O(log N).
188	func (a *RangeIndex) lowerBoundIndex(n uint64) (int, bool) {	3✔
189	// If the set is empty, then there is no such index and the value	3✔
190	// definitely is not in the set.	3✔
191	if len(a.set) == 0 {	3✔
UNCOV 192	return -1, false	×
UNCOV 193	}	×
194
195	// In most cases, the last index item will be the one we want. So just
196	// do a quick check on that index first to avoid doing the binary
197	// search.
198	lastIndex := len(a.set) - 1	3✔
199	lastRange := a.set[lastIndex]	3✔
200	if lastRange.start <= n {	6✔
201	return lastIndex, lastRange.end >= n	3✔
202	}	3✔
203
204	// Otherwise, do a binary search to find the index of interest.
UNCOV 205	var (	×
UNCOV 206	low = 0	×
UNCOV 207	high = len(a.set) - 1	×
UNCOV 208	rangeIndex = -1	×
UNCOV 209	)	×
UNCOV 210	for {	×
UNCOV 211	mid := (low + high) / 2	×
UNCOV 212	currentRange := a.set[mid]	×
UNCOV 213		×
UNCOV 214	switch {	×
UNCOV 215	case currentRange.start > n:	×
UNCOV 216	// If the start of the range is greater than n, we can	×
UNCOV 217	// completely cut out that entire part of the array.	×
UNCOV 218	high = mid	×
219
UNCOV 220	case currentRange.start < n:	×
UNCOV 221	// If the range already includes the given height, we	×
UNCOV 222	// can stop searching now.	×
UNCOV 223	if currentRange.end >= n {	×
UNCOV 224	return mid, true	×
UNCOV 225	}	×
226
227	// If the start of the range is smaller than n, we can
228	// store this as the new best index to return.
UNCOV 229	rangeIndex = mid	×
UNCOV 230		×
UNCOV 231	// If low and mid are already equal, then increment low	×
UNCOV 232	// by 1. Exit if this means that low is now greater than	×
UNCOV 233	// high.	×
UNCOV 234	if low == mid {	×
UNCOV 235	low = mid + 1	×
UNCOV 236	if low > high {	×
237	return rangeIndex, false	×
238	}	×
UNCOV 239	} else {	×
UNCOV 240	low = mid	×
UNCOV 241	}	×
242
UNCOV 243	continue	×
244
UNCOV 245	default:	×
UNCOV 246	// If the height is equal to the start value of the	×
UNCOV 247	// current range that mid is pointing to, then the	×
UNCOV 248	// height is already covered.	×
UNCOV 249	return mid, true	×
250	}
251
252	// Exit if we have checked all the ranges.
UNCOV 253	if low == high {	×
UNCOV 254	break	×
255	}
256	}
257
UNCOV 258	return rangeIndex, false	×
259	}
260
261	// KVStore is an interface representing a key-value store.
262	type KVStore interface {
263	// Put saves the specified key/value pair to the store. Keys that do not
264	// already exist are added and keys that already exist are overwritten.
265	Put(key, value []byte) error
266
267	// Delete removes the specified key from the bucket. Deleting a key that
268	// does not exist does not return an error.
269	Delete(key []byte) error
270	}
271
272	// Add adds a single number to the range set. It first attempts to apply the
273	// necessary changes to the passed KV store and then only if this succeeds, will
274	// the changes be applied to the in-memory structure.
275	func (a *RangeIndex) Add(newHeight uint64, kv KVStore) error {	3✔
276	a.mu.Lock()	3✔
277	defer a.mu.Unlock()	3✔
278		3✔
279	// Compute the changes that will need to be applied to both the sorted	3✔
280	// rangeItem array representation and the key-value store representation	3✔
281	// of the range index.	3✔
282	arrayChanges, kvStoreChanges := a.getChanges(newHeight)	3✔
283		3✔
284	// First attempt to apply the KV store changes. Only if this succeeds	3✔
285	// will we apply the changes to our in-memory range index structure.	3✔
286	err := a.applyKVChanges(kv, kvStoreChanges)	3✔
287	if err != nil {	3✔
UNCOV 288	return err	×
UNCOV 289	}	×
290
291	// Since the DB changes were successful, we can now commit the
292	// changes to our in-memory representation of the range set.
293	a.applyArrayChanges(arrayChanges)	3✔
294		3✔
295	return nil	3✔
296	}
297
298	// applyKVChanges applies the given set of kvChanges to a KV store. It is
299	// assumed that a transaction is being held on the kv store so that if any
300	// of the actions of the function fails, the changes will be reverted.
301	func (a RangeIndex) applyKVChanges(kv KVStore, changes kvChanges) error {	3✔
302	// Exit early if there are no changes to apply.	3✔
303	if kv == nil \|\| changes == nil {	3✔
UNCOV 304	return nil	×
UNCOV 305	}	×
306
307	// Check if any range pair needs to be deleted.
308	if changes.deleteKVKey != nil {	3✔
UNCOV 309	del, err := a.serializeUint64(*changes.deleteKVKey)	×
UNCOV 310	if err != nil {	×
311	return err	×
312	}	×
313
UNCOV 314	if err := kv.Delete(del); err != nil {	×
315	return err	×
316	}	×
317	}
318
319	start, err := a.serializeUint64(changes.key)	3✔
320	if err != nil {	3✔
321	return err	×
322	}	×
323
324	end, err := a.serializeUint64(changes.value)	3✔
325	if err != nil {	3✔
326	return err	×
327	}	×
328
329	return kv.Put(start, end)	3✔
330	}
331
332	// applyArrayChanges applies the given arrayChanges to the in-memory RangeIndex
333	// itself. This should only be done once the persisted kv store changes have
334	// already been applied.
335	func (a RangeIndex) applyArrayChanges(changes arrayChanges) {	3✔
336	if changes == nil {	3✔
UNCOV 337	return	×
UNCOV 338	}	×
339
340	if changes.indexToDelete != nil {	3✔
UNCOV 341	a.set = append(	×
UNCOV 342	a.set[:*changes.indexToDelete],	×
UNCOV 343	a.set[*changes.indexToDelete+1:]...,	×
UNCOV 344	)	×
UNCOV 345	}	×
346
347	if changes.newIndex != nil {	6✔
348	switch {	3✔
349	case *changes.newIndex == 0:	3✔
350	a.set = append([]rangeItem{{	3✔
351	start: changes.start,	3✔
352	end: changes.end,	3✔
353	}}, a.set...)	3✔
354
355	case *changes.newIndex == len(a.set):	3✔
356	a.set = append(a.set, rangeItem{	3✔
357	start: changes.start,	3✔
358	end: changes.end,	3✔
359	})	3✔
360
UNCOV 361	default:	×
UNCOV 362	a.set = append(	×
UNCOV 363	a.set[:*changes.newIndex+1],	×
UNCOV 364	a.set[*changes.newIndex:]...,	×
UNCOV 365	)	×
UNCOV 366	a.set[*changes.newIndex] = rangeItem{	×
UNCOV 367	start: changes.start,	×
UNCOV 368	end: changes.end,	×
UNCOV 369	}	×
370	}
371
372	return	3✔
373	}
374
375	if changes.indexToEdit != nil {	6✔
376	a.set[*changes.indexToEdit] = rangeItem{	3✔
377	start: changes.start,	3✔
378	end: changes.end,	3✔
379	}	3✔
380	}	3✔
381	}
382
383	// arrayChanges encompasses the diff to apply to the sorted rangeItem array
384	// representation of a range index. Such a diff will either include adding a
385	// new range or editing an existing range. If an existing range is edited, then
386	// the diff might also include deleting an index (this will be the case if the
387	// editing of the one range results in the merge of another range).
388	type arrayChanges struct {
389	start uint64
390	end uint64
391
392	// newIndex, if set, is the index of the in-memory range array where a
393	// new range, [start:end], should be added. newIndex should never be
394	// set at the same time as indexToEdit or indexToDelete.
395	newIndex *int
396
397	// indexToDelete, if set, is the index of the sorted rangeItem array
398	// that should be deleted. This should be applied before reading the
399	// index value of indexToEdit. This should not be set at the same time
400	// as newIndex.
401	indexToDelete *int
402
403	// indexToEdit is the index of the in-memory range array that should be
404	// edited. The range at this index will be changed to [start:end]. This
405	// should only be read after indexToDelete index has been deleted.
406	indexToEdit *int
407	}
408
409	// kvChanges encompasses the diff to apply to a KV-store representation of a
410	// range index. A kv-store diff for the addition of a single number to the range
411	// index will include either a brand new key-value pair or the altering of the
412	// value of an existing key. Optionally, the diff may also include the deletion
413	// of an existing key. A deletion will be required if the addition of the new
414	// number results in the merge of two ranges.
415	type kvChanges struct {
416	key uint64
417	value uint64
418
419	// deleteKVKey, if set, is the key of the kv store representation that
420	// should be deleted.
421	deleteKVKey *uint64
422	}
423
424	// getChanges will calculate and return the changes that need to be applied to
425	// both the sorted-rangeItem-array representation and the key-value store
426	// representation of the range index.
427	func (a RangeIndex) getChanges(n uint64) (arrayChanges, *kvChanges) {	3✔
428	// If the set is empty then a new range item is added.	3✔
429	if len(a.set) == 0 {	6✔
430	// For the array representation, a new range [n:n] is added to	3✔
431	// the first index of the array.	3✔
432	firstIndex := 0	3✔
433	ac := &arrayChanges{	3✔
434	newIndex: &firstIndex,	3✔
435	start: n,	3✔
436	end: n,	3✔
437	}	3✔
438		3✔
439	// For the KV representation, a new [n:n] pair is added.	3✔
440	kvc := &kvChanges{	3✔
441	key: n,	3✔
442	value: n,	3✔
443	}	3✔
444		3✔
445	return ac, kvc	3✔
446	}	3✔
447
448	// Find the index of the lower bound range to the new number.
449	indexOfRangeBelow, alreadyCovered := a.lowerBoundIndex(n)	3✔
450		3✔
451	switch {	3✔
452	// The new number is already covered by the range index. No changes are
453	// required.
UNCOV 454	case alreadyCovered:	×
UNCOV 455	return nil, nil	×
456
457	// No lower bound index exists.
UNCOV 458	case indexOfRangeBelow < 0:	×
UNCOV 459	// Check if the very first range can be merged into this new	×
UNCOV 460	// one.	×
UNCOV 461	if n+1 == a.set[0].start {	×
UNCOV 462	// If so, the two ranges can be merged and so the start	×
UNCOV 463	// value of the range is n and the end value is the end	×
UNCOV 464	// of the existing first range.	×
UNCOV 465	start := n	×
UNCOV 466	end := a.set[0].end	×
UNCOV 467		×
UNCOV 468	// For the array representation, we can just edit the	×
UNCOV 469	// first entry of the array	×
UNCOV 470	editIndex := 0	×
UNCOV 471	ac := &arrayChanges{	×
UNCOV 472	indexToEdit: &editIndex,	×
UNCOV 473	start: start,	×
UNCOV 474	end: end,	×
UNCOV 475	}	×
UNCOV 476		×
UNCOV 477	// For the KV store representation, we add a new kv pair	×
UNCOV 478	// and delete the range with the key equal to the start	×
UNCOV 479	// value of the range we are merging.	×
UNCOV 480	kvKeyToDelete := a.set[0].start	×
UNCOV 481	kvc := &kvChanges{	×
UNCOV 482	key: start,	×
UNCOV 483	value: end,	×
UNCOV 484	deleteKVKey: &kvKeyToDelete,	×
UNCOV 485	}	×
UNCOV 486		×
UNCOV 487	return ac, kvc	×
UNCOV 488	}	×
489
490	// Otherwise, we add a new index.
491
492	// For the array representation, a new range [n:n] is added to
493	// the first index of the array.
UNCOV 494	newIndex := 0	×
UNCOV 495	ac := &arrayChanges{	×
UNCOV 496	newIndex: &newIndex,	×
UNCOV 497	start: n,	×
UNCOV 498	end: n,	×
UNCOV 499	}	×
UNCOV 500		×
UNCOV 501	// For the KV representation, a new [n:n] pair is added.	×
UNCOV 502	kvc := &kvChanges{	×
UNCOV 503	key: n,	×
UNCOV 504	value: n,	×
UNCOV 505	}	×
UNCOV 506		×
UNCOV 507	return ac, kvc	×
508
509	// A lower range does exist, and it can be extended to include this new
510	// number.
511	case a.set[indexOfRangeBelow].end+1 == n:	3✔
512	start := a.set[indexOfRangeBelow].start	3✔
513	end := n	3✔
514	indexToChange := indexOfRangeBelow	3✔
515		3✔
516	// If there are no intervals above this one or if there are, but	3✔
517	// they can't be merged into this one then we just need to edit	3✔
518	// this interval.	3✔
519	if indexOfRangeBelow == len(a.set)-1 \|\|	3✔
520	a.set[indexOfRangeBelow+1].start != n+1 {	6✔
521		3✔
522	// For the array representation, we just edit the index.	3✔
523	ac := &arrayChanges{	3✔
524	indexToEdit: &indexToChange,	3✔
525	start: start,	3✔
526	end: end,	3✔
527	}	3✔
528		3✔
529	// For the key-value representation, we just overwrite	3✔
530	// the end value at the existing start key.	3✔
531	kvc := &kvChanges{	3✔
532	key: start,	3✔
533	value: end,	3✔
534	}	3✔
535		3✔
536	return ac, kvc	3✔
537	}	3✔
538
539	// There is a range above this one that we need to merge into
540	// this one.
UNCOV 541	delIndex := indexOfRangeBelow + 1	×
UNCOV 542	end = a.set[delIndex].end	×
UNCOV 543		×
UNCOV 544	// For the array representation, we delete the range above this	×
UNCOV 545	// one and edit this range to include the end value of the range	×
UNCOV 546	// above.	×
UNCOV 547	ac := &arrayChanges{	×
UNCOV 548	indexToDelete: &delIndex,	×
UNCOV 549	indexToEdit: &indexToChange,	×
UNCOV 550	start: start,	×
UNCOV 551	end: end,	×
UNCOV 552	}	×
UNCOV 553		×
UNCOV 554	// For the kv representation, we tweak the end value of an	×
UNCOV 555	// existing key and delete the key of the range we are deleting.	×
UNCOV 556	deleteKey := a.set[delIndex].start	×
UNCOV 557	kvc := &kvChanges{	×
UNCOV 558	key: start,	×
UNCOV 559	value: end,	×
UNCOV 560	deleteKVKey: &deleteKey,	×
UNCOV 561	}	×
UNCOV 562		×
UNCOV 563	return ac, kvc	×
564
565	// A lower range does exist, but it can't be extended to include this
566	// new number, and so we need to add a new range after the lower bound
567	// range.
568	default:	3✔
569	newIndex := indexOfRangeBelow + 1	3✔
570		3✔
571	// If there are no ranges above this new one or if there are,	3✔
572	// but they can't be merged into this new one, then we can just	3✔
573	// add the new one as is.	3✔
574	if newIndex == len(a.set) \|\| a.set[newIndex].start != n+1 {	6✔
575	ac := &arrayChanges{	3✔
576	newIndex: &newIndex,	3✔
577	start: n,	3✔
578	end: n,	3✔
579	}	3✔
580		3✔
581	kvc := &kvChanges{	3✔
582	key: n,	3✔
583	value: n,	3✔
584	}	3✔
585		3✔
586	return ac, kvc	3✔
587	}	3✔
588
589	// Else, we merge the above index.
UNCOV 590	start := n	×
UNCOV 591	end := a.set[newIndex].end	×
UNCOV 592	toEdit := newIndex	×
UNCOV 593		×
UNCOV 594	// For the array representation, we edit the range above to	×
UNCOV 595	// include the new start value.	×
UNCOV 596	ac := &arrayChanges{	×
UNCOV 597	indexToEdit: &toEdit,	×
UNCOV 598	start: start,	×
UNCOV 599	end: end,	×
UNCOV 600	}	×
UNCOV 601		×
UNCOV 602	// For the kv representation, we insert the new start-end key	×
UNCOV 603	// value pair and delete the key using the old start value.	×
UNCOV 604	delKey := a.set[newIndex].start	×
UNCOV 605	kvc := &kvChanges{	×
UNCOV 606	key: start,	×
UNCOV 607	value: end,	×
UNCOV 608	deleteKVKey: &delKey,	×
UNCOV 609	}	×
UNCOV 610		×
UNCOV 611	return ac, kvc	×
612	}
613	}
614
UNCOV 615	func defaultSerializeUint64(i uint64) ([]byte, error) {	×
UNCOV 616	var b [8]byte	×
UNCOV 617	byteOrder.PutUint64(b[:], i)	×
UNCOV 618	return b[:], nil	×
UNCOV 619	}	×

lightningnetwork / lnd / 13211764208

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