From 696a7d192e5eefa53230168a4b200ec0560c8a10 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 5 Feb 2023 00:31:29 -0700 Subject: containers: Rethink the RBTree interface to be simpler --- lib/btrfs/btrfsvol/chunk.go | 5 +++- lib/btrfs/btrfsvol/devext.go | 5 ++++ lib/btrfs/btrfsvol/lvm.go | 67 ++++++++++++++++++++------------------------ 3 files changed, 39 insertions(+), 38 deletions(-) (limited to 'lib/btrfs/btrfsvol') diff --git a/lib/btrfs/btrfsvol/chunk.go b/lib/btrfs/btrfsvol/chunk.go index 08a0b2b..a112fd3 100644 --- a/lib/btrfs/btrfsvol/chunk.go +++ b/lib/btrfs/btrfsvol/chunk.go @@ -22,7 +22,10 @@ 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' diff --git a/lib/btrfs/btrfsvol/devext.go b/lib/btrfs/btrfsvol/devext.go index 037021c..3324476 100644 --- a/lib/btrfs/btrfsvol/devext.go +++ b/lib/btrfs/btrfsvol/devext.go @@ -20,6 +20,11 @@ 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' diff --git a/lib/btrfs/btrfsvol/lvm.go b/lib/btrfs/btrfsvol/lvm.go index 59ca609..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,11 +131,13 @@ func (lv *LogicalVolume[PhysicalVolume]) addMapping(m Mapping, dryRun bool) erro SizeLocked: m.SizeLocked, Flags: m.Flags, } - logicalOverlaps := lv.logical2physical.SearchRange(newChunk.compareRange) + var logicalOverlaps []chunkMapping numOverlappingStripes := 0 - for _, chunk := range logicalOverlaps { - numOverlappingStripes += len(chunk.PAddrs) - } + 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 { @@ -162,7 +152,11 @@ func (lv *LogicalVolume[PhysicalVolume]) addMapping(m Mapping, dryRun bool) erro SizeLocked: m.SizeLocked, Flags: m.Flags, } - physicalOverlaps := lv.physical2logical[m.PAddr.Dev].SearchRange(newExt.compareRange) + 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) @@ -202,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) @@ -227,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, @@ -249,8 +241,9 @@ func (lv *LogicalVolume[PhysicalVolume]) fsck() error { Flags: chunk.Flags, }) } - return nil - }); err != nil { + return true + }) + if err != nil { return err } @@ -270,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{ @@ -280,7 +273,7 @@ func (lv *LogicalVolume[PhysicalVolume]) Mappings() []Mapping { Flags: chunk.Flags, }) } - return nil + return true }) return ret } -- cgit v1.2.3-2-g168b