1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
|
// Copyright (C) 2022 Luke Shumaker <lukeshu@lukeshu.com>
//
// SPDX-License-Identifier: GPL-2.0-or-later
package rebuildmappings
import (
"context"
"strings"
"github.com/datawire/dlib/dlog"
"git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfssum"
"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
"git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect"
"git.lukeshu.com/btrfs-progs-ng/lib/maps"
"git.lukeshu.com/btrfs-progs-ng/lib/slices"
)
func ExtractLogicalSums(ctx context.Context, scanResults btrfsinspect.ScanDevicesResult) btrfssum.SumRunWithGaps[btrfsvol.LogicalAddr] {
dlog.Info(ctx, "... Mapping the logical address space...")
type record struct {
Gen btrfs.Generation
Sum btrfssum.ShortSum
}
addrspace := make(map[btrfsvol.LogicalAddr]record)
var sumSize int
for _, devResults := range scanResults {
sumSize = devResults.Checksums.ChecksumSize
for _, sumItem := range devResults.FoundExtentCSums {
_ = sumItem.Sums.Walk(ctx, func(pos btrfsvol.LogicalAddr, sum btrfssum.ShortSum) error {
new := record{
Gen: sumItem.Generation,
Sum: sum,
}
if old, ok := addrspace[pos]; ok {
switch {
case old.Gen > new.Gen:
// do nothing
case old.Gen < new.Gen:
addrspace[pos] = new
case old.Gen == new.Gen:
if old != new {
dlog.Errorf(ctx, "mismatch of laddr=%v sum: %v != %v", pos, old, new)
}
}
} else {
addrspace[pos] = new
}
return nil
})
}
}
dlog.Info(ctx, "... ... done mapping")
var flattened btrfssum.SumRunWithGaps[btrfsvol.LogicalAddr]
if len(addrspace) == 0 {
return flattened
}
dlog.Info(ctx, "... Flattening the map ...")
var curAddr btrfsvol.LogicalAddr
var curSums strings.Builder
for _, laddr := range maps.SortedKeys(addrspace) {
if laddr != curAddr+(btrfsvol.LogicalAddr(curSums.Len()/sumSize)*btrfssum.BlockSize) {
if curSums.Len() > 0 {
flattened.Runs = append(flattened.Runs, btrfssum.SumRun[btrfsvol.LogicalAddr]{
ChecksumSize: sumSize,
Addr: curAddr,
Sums: btrfssum.ShortSum(curSums.String()),
})
}
curAddr = laddr
curSums.Reset()
}
curSums.WriteString(string(addrspace[laddr].Sum))
}
if curSums.Len() > 0 {
flattened.Runs = append(flattened.Runs, btrfssum.SumRun[btrfsvol.LogicalAddr]{
ChecksumSize: sumSize,
Addr: curAddr,
Sums: btrfssum.ShortSum(curSums.String()),
})
}
flattened.Addr = flattened.Runs[0].Addr
last := flattened.Runs[len(flattened.Runs)-1]
end := last.Addr.Add(last.Size())
flattened.Size = end.Sub(flattened.Addr)
dlog.Info(ctx, "... ... done flattening")
return flattened
}
func ListUnmappedLogicalRegions(fs *btrfs.FS, logicalSums btrfssum.SumRunWithGaps[btrfsvol.LogicalAddr]) []btrfssum.SumRun[btrfsvol.LogicalAddr] {
// There are a lot of ways this algorithm could be made
// faster.
var ret []btrfssum.SumRun[btrfsvol.LogicalAddr]
var cur struct {
Addr btrfsvol.LogicalAddr
Size btrfsvol.AddrDelta
}
for _, run := range logicalSums.Runs {
for addr := run.Addr; addr < run.Addr.Add(run.Size()); addr += btrfssum.BlockSize {
if _, maxlen := fs.LV.Resolve(addr); maxlen < btrfssum.BlockSize {
if cur.Size == 0 {
cur.Addr = addr
cur.Size = 0
}
cur.Size += btrfssum.BlockSize
} else if cur.Size > 0 {
begIdx := int(cur.Addr.Sub(run.Addr)/btrfssum.BlockSize) * run.ChecksumSize
lenIdx := (int(cur.Size) / btrfssum.BlockSize) * run.ChecksumSize
endIdx := begIdx + lenIdx
ret = append(ret, btrfssum.SumRun[btrfsvol.LogicalAddr]{
ChecksumSize: run.ChecksumSize,
Addr: cur.Addr,
Sums: run.Sums[begIdx:endIdx],
})
cur.Size = 0
}
}
if cur.Size > 0 {
begIdx := int(cur.Addr.Sub(run.Addr)/btrfssum.BlockSize) * run.ChecksumSize
lenIdx := (int(cur.Size) / btrfssum.BlockSize) * run.ChecksumSize
endIdx := begIdx + lenIdx
ret = append(ret, btrfssum.SumRun[btrfsvol.LogicalAddr]{
ChecksumSize: run.ChecksumSize,
Addr: cur.Addr,
Sums: run.Sums[begIdx:endIdx],
})
cur.Size = 0
}
}
return ret
}
func SumsForLogicalRegion(sums btrfssum.SumRunWithGaps[btrfsvol.LogicalAddr], beg btrfsvol.LogicalAddr, size btrfsvol.AddrDelta) btrfssum.SumRunWithGaps[btrfsvol.LogicalAddr] {
runs := btrfssum.SumRunWithGaps[btrfsvol.LogicalAddr]{
Addr: beg,
Size: size,
}
for laddr := beg; laddr < beg.Add(size); {
run, next, ok := sums.RunForAddr(laddr)
if !ok {
laddr = next
continue
}
off := int((laddr-run.Addr)/btrfssum.BlockSize) * run.ChecksumSize
deltaAddr := slices.Min[btrfsvol.AddrDelta](
size-laddr.Sub(beg),
btrfsvol.AddrDelta((len(run.Sums)-off)/run.ChecksumSize)*btrfssum.BlockSize)
deltaOff := int(deltaAddr/btrfssum.BlockSize) * run.ChecksumSize
runs.Runs = append(runs.Runs, btrfssum.SumRun[btrfsvol.LogicalAddr]{
ChecksumSize: run.ChecksumSize,
Addr: laddr,
Sums: run.Sums[off : off+deltaOff],
})
laddr = laddr.Add(deltaAddr)
}
return runs
}
|
