diff options
author | Luke Shumaker <lukeshu@lukeshu.com> | 2023-02-12 02:44:35 -0700 |
---|---|---|
committer | Luke Shumaker <lukeshu@lukeshu.com> | 2023-02-12 02:44:35 -0700 |
commit | 128e4d9aa876e14a1203ce98bfaa7ad399ad97c7 (patch) | |
tree | 039c3c549414c21b15d58c3d695ee87c3feb1402 /lib/btrfs | |
parent | 53d7fbb73869eb5defa1ca5c52b26abd346b13b9 (diff) | |
parent | 696a7d192e5eefa53230168a4b200ec0560c8a10 (diff) |
Merge branch 'lukeshu/containers'
Diffstat (limited to 'lib/btrfs')
-rw-r--r-- | lib/btrfs/btrfsprim/misc.go | 8 | ||||
-rw-r--r-- | lib/btrfs/btrfsprim/uuid.go | 2 | ||||
-rw-r--r-- | lib/btrfs/btrfstree/ops.go | 2 | ||||
-rw-r--r-- | lib/btrfs/btrfstree/root.go | 2 | ||||
-rw-r--r-- | lib/btrfs/btrfstree/types_node.go | 4 | ||||
-rw-r--r-- | lib/btrfs/btrfsvol/addr.go | 4 | ||||
-rw-r--r-- | lib/btrfs/btrfsvol/blockgroupflags.go | 5 | ||||
-rw-r--r-- | lib/btrfs/btrfsvol/chunk.go | 13 | ||||
-rw-r--r-- | lib/btrfs/btrfsvol/devext.go | 11 | ||||
-rw-r--r-- | lib/btrfs/btrfsvol/lvm.go | 93 | ||||
-rw-r--r-- | lib/btrfs/io4_fs.go | 2 |
11 files changed, 89 insertions, 57 deletions
diff --git a/lib/btrfs/btrfsprim/misc.go b/lib/btrfs/btrfsprim/misc.go index 22939bf..da661f6 100644 --- a/lib/btrfs/btrfsprim/misc.go +++ b/lib/btrfs/btrfsprim/misc.go @@ -44,14 +44,14 @@ func (key Key) Mm() Key { return key } -func (a Key) Cmp(b Key) int { - if d := containers.NativeCmp(a.ObjectID, b.ObjectID); d != 0 { +func (a Key) Compare(b Key) int { + if d := containers.NativeCompare(a.ObjectID, b.ObjectID); d != 0 { return d } - if d := containers.NativeCmp(a.ItemType, b.ItemType); d != 0 { + if d := containers.NativeCompare(a.ItemType, b.ItemType); d != 0 { return d } - return containers.NativeCmp(a.Offset, b.Offset) + return containers.NativeCompare(a.Offset, b.Offset) } var _ containers.Ordered[Key] = Key{} diff --git a/lib/btrfs/btrfsprim/uuid.go b/lib/btrfs/btrfsprim/uuid.go index 0103ee4..232ab58 100644 --- a/lib/btrfs/btrfsprim/uuid.go +++ b/lib/btrfs/btrfsprim/uuid.go @@ -47,7 +47,7 @@ func (uuid UUID) Format(f fmt.State, verb rune) { fmtutil.FormatByteArrayStringer(uuid, uuid[:], f, verb) } -func (a UUID) Cmp(b UUID) int { +func (a UUID) Compare(b UUID) int { for i := range a { if d := int(a[i]) - int(b[i]); d != 0 { return d diff --git a/lib/btrfs/btrfstree/ops.go b/lib/btrfs/btrfstree/ops.go index 537773a..cdacef9 100644 --- a/lib/btrfs/btrfstree/ops.go +++ b/lib/btrfs/btrfstree/ops.go @@ -481,7 +481,7 @@ func KeySearch(fn func(btrfsprim.Key) int) func(btrfsprim.Key, uint32) int { // TreeLookup implements the 'Trees' interface. func (fs TreeOperatorImpl) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (Item, error) { - item, err := fs.TreeSearch(treeID, KeySearch(key.Cmp)) + item, err := fs.TreeSearch(treeID, KeySearch(key.Compare)) if err != nil { err = fmt.Errorf("item with key=%v: %w", key, err) } diff --git a/lib/btrfs/btrfstree/root.go b/lib/btrfs/btrfstree/root.go index 6ec45b5..319904b 100644 --- a/lib/btrfs/btrfstree/root.go +++ b/lib/btrfs/btrfstree/root.go @@ -30,7 +30,7 @@ func RootItemSearchFn(treeID btrfsprim.ObjID) func(btrfsprim.Key, uint32) int { ObjectID: treeID, ItemType: btrfsitem.ROOT_ITEM_KEY, Offset: 0, - }.Cmp(key) + }.Compare(key) } } diff --git a/lib/btrfs/btrfstree/types_node.go b/lib/btrfs/btrfstree/types_node.go index a26215b..d9d7118 100644 --- a/lib/btrfs/btrfstree/types_node.go +++ b/lib/btrfs/btrfstree/types_node.go @@ -507,11 +507,11 @@ func ReadNode[Addr ~int64](fs diskio.File[Addr], sb Superblock, addr Addr, exp N if nodeRef.Data.Head.NumItems == 0 { errs = append(errs, fmt.Errorf("has no items")) } else { - if minItem, _ := nodeRef.Data.MinItem(); exp.MinItem.OK && exp.MinItem.Val.Cmp(minItem) > 0 { + if minItem, _ := nodeRef.Data.MinItem(); exp.MinItem.OK && exp.MinItem.Val.Compare(minItem) > 0 { errs = append(errs, fmt.Errorf("expected minItem>=%v but node has minItem=%v", exp.MinItem, minItem)) } - if maxItem, _ := nodeRef.Data.MaxItem(); exp.MaxItem.OK && exp.MaxItem.Val.Cmp(maxItem) < 0 { + if maxItem, _ := nodeRef.Data.MaxItem(); exp.MaxItem.OK && exp.MaxItem.Val.Compare(maxItem) < 0 { errs = append(errs, fmt.Errorf("expected maxItem<=%v but node has maxItem=%v", exp.MaxItem, maxItem)) } diff --git a/lib/btrfs/btrfsvol/addr.go b/lib/btrfs/btrfsvol/addr.go index 94320ef..655f4e9 100644 --- a/lib/btrfs/btrfsvol/addr.go +++ b/lib/btrfs/btrfsvol/addr.go @@ -1,4 +1,4 @@ -// Copyright (C) 2022 Luke Shumaker <lukeshu@lukeshu.com> +// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com> // // SPDX-License-Identifier: GPL-2.0-or-later @@ -50,7 +50,7 @@ func (a QualifiedPhysicalAddr) Add(b AddrDelta) QualifiedPhysicalAddr { } } -func (a QualifiedPhysicalAddr) Cmp(b QualifiedPhysicalAddr) int { +func (a QualifiedPhysicalAddr) Compare(b QualifiedPhysicalAddr) int { if d := int(a.Dev - b.Dev); d != 0 { return d } diff --git a/lib/btrfs/btrfsvol/blockgroupflags.go b/lib/btrfs/btrfsvol/blockgroupflags.go index 4ca5544..0125664 100644 --- a/lib/btrfs/btrfsvol/blockgroupflags.go +++ b/lib/btrfs/btrfsvol/blockgroupflags.go @@ -23,6 +23,11 @@ const ( BLOCK_GROUP_RAID1C3 BLOCK_GROUP_RAID1C4 + // BLOCK_GROUP_RAID_MASK is the set of bits that mean that + // mean the logical:physical relationship is a one:many + // relationship rather than a one:one relationship. + // + // Notably, this does not include BLOCK_GROUP_RAID0. BLOCK_GROUP_RAID_MASK = (BLOCK_GROUP_RAID1 | BLOCK_GROUP_DUP | BLOCK_GROUP_RAID10 | BLOCK_GROUP_RAID5 | BLOCK_GROUP_RAID6 | BLOCK_GROUP_RAID1C3 | BLOCK_GROUP_RAID1C4) ) diff --git a/lib/btrfs/btrfsvol/chunk.go b/lib/btrfs/btrfsvol/chunk.go index 5f1baa8..a112fd3 100644 --- a/lib/btrfs/btrfsvol/chunk.go +++ b/lib/btrfs/btrfsvol/chunk.go @@ -1,4 +1,4 @@ -// Copyright (C) 2022 Luke Shumaker <lukeshu@lukeshu.com> +// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com> // // SPDX-License-Identifier: GPL-2.0-or-later @@ -22,12 +22,15 @@ type chunkMapping struct { Flags containers.Optional[BlockGroupFlags] } -type ChunkMapping = chunkMapping +// Compare implements containers.Ordered. +func (a chunkMapping) Compare(b chunkMapping) int { + return containers.NativeCompare(a.LAddr, b.LAddr) +} // return -1 if 'a' is wholly to the left of 'b' // return 0 if there is some overlap between 'a' and 'b' // return 1 if 'a is wholly to the right of 'b' -func (a chunkMapping) cmpRange(b chunkMapping) int { +func (a chunkMapping) compareRange(b chunkMapping) int { switch { case a.LAddr.Add(a.Size) <= b.LAddr: // 'a' is wholly to the left of 'b'. @@ -44,7 +47,7 @@ func (a chunkMapping) cmpRange(b chunkMapping) int { func (a chunkMapping) union(rest ...chunkMapping) (chunkMapping, error) { // sanity check for _, chunk := range rest { - if a.cmpRange(chunk) != 0 { + if a.compareRange(chunk) != 0 { return chunkMapping{}, fmt.Errorf("chunks don't overlap") } } @@ -79,7 +82,7 @@ func (a chunkMapping) union(rest ...chunkMapping) (chunkMapping, error) { } ret.PAddrs = maps.Keys(paddrs) sort.Slice(ret.PAddrs, func(i, j int) bool { - return ret.PAddrs[i].Cmp(ret.PAddrs[j]) < 0 + return ret.PAddrs[i].Compare(ret.PAddrs[j]) < 0 }) // figure out the flags (.Flags) for _, chunk := range chunks { diff --git a/lib/btrfs/btrfsvol/devext.go b/lib/btrfs/btrfsvol/devext.go index e8e5446..3324476 100644 --- a/lib/btrfs/btrfsvol/devext.go +++ b/lib/btrfs/btrfsvol/devext.go @@ -1,4 +1,4 @@ -// Copyright (C) 2022 Luke Shumaker <lukeshu@lukeshu.com> +// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com> // // SPDX-License-Identifier: GPL-2.0-or-later @@ -20,10 +20,15 @@ type devextMapping struct { Flags containers.Optional[BlockGroupFlags] } +// Compare implements containers.Ordered. +func (a devextMapping) Compare(b devextMapping) int { + return containers.NativeCompare(a.PAddr, b.PAddr) +} + // return -1 if 'a' is wholly to the left of 'b' // return 0 if there is some overlap between 'a' and 'b' // return 1 if 'a is wholly to the right of 'b' -func (a devextMapping) cmpRange(b devextMapping) int { +func (a devextMapping) compareRange(b devextMapping) int { switch { case a.PAddr.Add(a.Size) <= b.PAddr: // 'a' is wholly to the left of 'b'. @@ -40,7 +45,7 @@ func (a devextMapping) cmpRange(b devextMapping) int { func (a devextMapping) union(rest ...devextMapping) (devextMapping, error) { // sanity check for _, ext := range rest { - if a.cmpRange(ext) != 0 { + if a.compareRange(ext) != 0 { return devextMapping{}, fmt.Errorf("devexts don't overlap") } } diff --git a/lib/btrfs/btrfsvol/lvm.go b/lib/btrfs/btrfsvol/lvm.go index 1cb1ded..93ec438 100644 --- a/lib/btrfs/btrfsvol/lvm.go +++ b/lib/btrfs/btrfsvol/lvm.go @@ -22,8 +22,8 @@ type LogicalVolume[PhysicalVolume diskio.File[PhysicalAddr]] struct { id2pv map[DeviceID]PhysicalVolume - logical2physical *containers.RBTree[containers.NativeOrdered[LogicalAddr], chunkMapping] - physical2logical map[DeviceID]*containers.RBTree[containers.NativeOrdered[PhysicalAddr], devextMapping] + logical2physical *containers.RBTree[chunkMapping] + physical2logical map[DeviceID]*containers.RBTree[devextMapping] } var _ diskio.File[LogicalAddr] = (*LogicalVolume[diskio.File[PhysicalAddr]])(nil) @@ -33,22 +33,14 @@ func (lv *LogicalVolume[PhysicalVolume]) init() { lv.id2pv = make(map[DeviceID]PhysicalVolume) } if lv.logical2physical == nil { - lv.logical2physical = &containers.RBTree[containers.NativeOrdered[LogicalAddr], chunkMapping]{ - KeyFn: func(chunk chunkMapping) containers.NativeOrdered[LogicalAddr] { - return containers.NativeOrdered[LogicalAddr]{Val: chunk.LAddr} - }, - } + lv.logical2physical = new(containers.RBTree[chunkMapping]) } if lv.physical2logical == nil { - lv.physical2logical = make(map[DeviceID]*containers.RBTree[containers.NativeOrdered[PhysicalAddr], devextMapping], len(lv.id2pv)) + lv.physical2logical = make(map[DeviceID]*containers.RBTree[devextMapping], len(lv.id2pv)) } for devid := range lv.id2pv { if _, ok := lv.physical2logical[devid]; !ok { - lv.physical2logical[devid] = &containers.RBTree[containers.NativeOrdered[PhysicalAddr], devextMapping]{ - KeyFn: func(ext devextMapping) containers.NativeOrdered[PhysicalAddr] { - return containers.NativeOrdered[PhysicalAddr]{Val: ext.PAddr} - }, - } + lv.physical2logical[devid] = new(containers.RBTree[devextMapping]) } } } @@ -90,11 +82,7 @@ func (lv *LogicalVolume[PhysicalVolume]) AddPhysicalVolume(id DeviceID, dev Phys lv, dev.Name(), other.Name(), id) } lv.id2pv[id] = dev - lv.physical2logical[id] = &containers.RBTree[containers.NativeOrdered[PhysicalAddr], devextMapping]{ - KeyFn: func(ext devextMapping) containers.NativeOrdered[PhysicalAddr] { - return containers.NativeOrdered[PhysicalAddr]{Val: ext.PAddr} - }, - } + lv.physical2logical[id] = new(containers.RBTree[devextMapping]) return nil } @@ -143,7 +131,13 @@ func (lv *LogicalVolume[PhysicalVolume]) addMapping(m Mapping, dryRun bool) erro SizeLocked: m.SizeLocked, Flags: m.Flags, } - logicalOverlaps := lv.logical2physical.SearchRange(newChunk.cmpRange) + var logicalOverlaps []chunkMapping + numOverlappingStripes := 0 + lv.logical2physical.Subrange(newChunk.compareRange, func(node *containers.RBNode[chunkMapping]) bool { + logicalOverlaps = append(logicalOverlaps, node.Value) + numOverlappingStripes += len(node.Value.PAddrs) + return true + }) var err error newChunk, err = newChunk.union(logicalOverlaps...) if err != nil { @@ -158,12 +152,38 @@ func (lv *LogicalVolume[PhysicalVolume]) addMapping(m Mapping, dryRun bool) erro SizeLocked: m.SizeLocked, Flags: m.Flags, } - physicalOverlaps := lv.physical2logical[m.PAddr.Dev].SearchRange(newExt.cmpRange) + var physicalOverlaps []devextMapping + lv.physical2logical[m.PAddr.Dev].Subrange(newExt.compareRange, func(node *containers.RBNode[devextMapping]) bool { + physicalOverlaps = append(physicalOverlaps, node.Value) + return true + }) newExt, err = newExt.union(physicalOverlaps...) if err != nil { return fmt.Errorf("(%p).AddMapping: %w", lv, err) } + if newChunk.Flags != newExt.Flags { + // If these don't match up, it's a bug in this code. + panic(fmt.Errorf("should not happen: newChunk.Flags:%+v != newExt.Flags:%+v", + newChunk.Flags, newExt.Flags)) + } + switch { + case len(physicalOverlaps) == numOverlappingStripes: + // normal case + case len(physicalOverlaps) < numOverlappingStripes: + // .Flags = DUP or RAID{X} + if newChunk.Flags.OK && newChunk.Flags.Val&BLOCK_GROUP_RAID_MASK == 0 { + return fmt.Errorf("multiple stripes but flags=%v does not allow multiple stripes", + newChunk.Flags.Val) + } + case len(physicalOverlaps) > numOverlappingStripes: + // This should not happen because calling .AddMapping + // should update the two in lockstep; if these don't + // match up, it's a bug in this code. + panic(fmt.Errorf("should not happen: len(physicalOverlaps):%d != numOverlappingStripes:%d", + len(physicalOverlaps), numOverlappingStripes)) + } + if dryRun { return nil } @@ -176,13 +196,13 @@ func (lv *LogicalVolume[PhysicalVolume]) addMapping(m Mapping, dryRun bool) erro // logical2physical for _, chunk := range logicalOverlaps { - lv.logical2physical.Delete(containers.NativeOrdered[LogicalAddr]{Val: chunk.LAddr}) + lv.logical2physical.Delete(lv.logical2physical.Search(chunk.Compare)) } lv.logical2physical.Insert(newChunk) // physical2logical for _, ext := range physicalOverlaps { - lv.physical2logical[m.PAddr.Dev].Delete(containers.NativeOrdered[PhysicalAddr]{Val: ext.PAddr}) + lv.physical2logical[m.PAddr.Dev].Delete(lv.physical2logical[m.PAddr.Dev].Search(ext.Compare)) } lv.physical2logical[m.PAddr.Dev].Insert(newExt) @@ -201,20 +221,18 @@ func (lv *LogicalVolume[PhysicalVolume]) addMapping(m Mapping, dryRun bool) erro } func (lv *LogicalVolume[PhysicalVolume]) fsck() error { - physical2logical := make(map[DeviceID]*containers.RBTree[containers.NativeOrdered[PhysicalAddr], devextMapping]) - if err := lv.logical2physical.Walk(func(node *containers.RBNode[chunkMapping]) error { + physical2logical := make(map[DeviceID]*containers.RBTree[devextMapping]) + var err error + lv.logical2physical.Range(func(node *containers.RBNode[chunkMapping]) bool { chunk := node.Value for _, stripe := range chunk.PAddrs { if _, devOK := lv.id2pv[stripe.Dev]; !devOK { - return fmt.Errorf("(%p).fsck: chunk references physical volume %v which does not exist", + err = fmt.Errorf("(%p).fsck: chunk references physical volume %v which does not exist", lv, stripe.Dev) + return false } if _, exists := physical2logical[stripe.Dev]; !exists { - physical2logical[stripe.Dev] = &containers.RBTree[containers.NativeOrdered[PhysicalAddr], devextMapping]{ - KeyFn: func(ext devextMapping) containers.NativeOrdered[PhysicalAddr] { - return containers.NativeOrdered[PhysicalAddr]{Val: ext.PAddr} - }, - } + physical2logical[stripe.Dev] = new(containers.RBTree[devextMapping]) } physical2logical[stripe.Dev].Insert(devextMapping{ PAddr: stripe.Addr, @@ -223,8 +241,9 @@ func (lv *LogicalVolume[PhysicalVolume]) fsck() error { Flags: chunk.Flags, }) } - return nil - }); err != nil { + return true + }) + if err != nil { return err } @@ -244,7 +263,7 @@ func (lv *LogicalVolume[PhysicalVolume]) fsck() error { func (lv *LogicalVolume[PhysicalVolume]) Mappings() []Mapping { var ret []Mapping - _ = lv.logical2physical.Walk(func(node *containers.RBNode[chunkMapping]) error { + lv.logical2physical.Range(func(node *containers.RBNode[chunkMapping]) bool { chunk := node.Value for _, slice := range chunk.PAddrs { ret = append(ret, Mapping{ @@ -254,14 +273,14 @@ func (lv *LogicalVolume[PhysicalVolume]) Mappings() []Mapping { Flags: chunk.Flags, }) } - return nil + return true }) return ret } func (lv *LogicalVolume[PhysicalVolume]) Resolve(laddr LogicalAddr) (paddrs containers.Set[QualifiedPhysicalAddr], maxlen AddrDelta) { node := lv.logical2physical.Search(func(chunk chunkMapping) int { - return chunkMapping{LAddr: laddr, Size: 1}.cmpRange(chunk) + return chunkMapping{LAddr: laddr, Size: 1}.compareRange(chunk) }) if node == nil { return nil, 0 @@ -281,7 +300,7 @@ func (lv *LogicalVolume[PhysicalVolume]) Resolve(laddr LogicalAddr) (paddrs cont func (lv *LogicalVolume[PhysicalVolume]) ResolveAny(laddr LogicalAddr, size AddrDelta) (LogicalAddr, QualifiedPhysicalAddr) { node := lv.logical2physical.Search(func(chunk chunkMapping) int { - return chunkMapping{LAddr: laddr, Size: size}.cmpRange(chunk) + return chunkMapping{LAddr: laddr, Size: size}.compareRange(chunk) }) if node == nil { return -1, QualifiedPhysicalAddr{0, -1} @@ -291,7 +310,7 @@ func (lv *LogicalVolume[PhysicalVolume]) ResolveAny(laddr LogicalAddr, size Addr func (lv *LogicalVolume[PhysicalVolume]) UnResolve(paddr QualifiedPhysicalAddr) LogicalAddr { node := lv.physical2logical[paddr.Dev].Search(func(ext devextMapping) int { - return devextMapping{PAddr: paddr.Addr, Size: 1}.cmpRange(ext) + return devextMapping{PAddr: paddr.Addr, Size: 1}.compareRange(ext) }) if node == nil { return -1 diff --git a/lib/btrfs/io4_fs.go b/lib/btrfs/io4_fs.go index 799c865..fce9c76 100644 --- a/lib/btrfs/io4_fs.go +++ b/lib/btrfs/io4_fs.go @@ -152,7 +152,7 @@ func (sv *Subvolume) LoadFullInode(inode btrfsprim.ObjID) (*FullInode, error) { XAttrs: make(map[string]string), } items, err := sv.FS.TreeSearchAll(sv.TreeID, func(key btrfsprim.Key, _ uint32) int { - return containers.NativeCmp(inode, key.ObjectID) + return containers.NativeCompare(inode, key.ObjectID) }) if err != nil { val.Errs = append(val.Errs, err) |