From 20de3140073547344d159a65db1a7e5c90ef95e9 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Fri, 31 Mar 2023 17:40:36 -0600 Subject: =?UTF-8?q?btrfsutil:=20Graph:=20I=20missed=20.FromItem=20in=20the?= =?UTF-8?q?=20"item"=E2=86=92"slot"=20switch?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- lib/btrfsutil/graph.go | 14 +++++++------- lib/btrfsutil/graph_loops.go | 2 +- 2 files changed, 8 insertions(+), 8 deletions(-) (limited to 'lib') diff --git a/lib/btrfsutil/graph.go b/lib/btrfsutil/graph.go index ea33be7..090ccf4 100644 --- a/lib/btrfsutil/graph.go +++ b/lib/btrfsutil/graph.go @@ -59,7 +59,7 @@ type GraphEdge struct { // superblock. FromRoot btrfsvol.LogicalAddr FromNode btrfsvol.LogicalAddr - FromItem int // only valid if one of FromRoot or FromNode is non-zero + FromSlot int // only valid if one of FromRoot or FromNode is non-zero FromTree btrfsprim.ObjID @@ -74,10 +74,10 @@ func (kp GraphEdge) String() string { switch { case kp.FromRoot != 0: from = fmt.Sprintf("root@%v[%d]:%v", - kp.FromRoot, kp.FromItem, kp.FromTree) + kp.FromRoot, kp.FromSlot, kp.FromTree) case kp.FromNode != 0: from = fmt.Sprintf("{node:%v, tree:%v}[%d]", - kp.FromNode, kp.FromTree, kp.FromItem) + kp.FromNode, kp.FromTree, kp.FromSlot) default: from = fmt.Sprintf("superblock:%v", kp.FromTree) } @@ -103,8 +103,8 @@ func (g Graph) insertEdge(ptr *GraphEdge) { if ptr.FromRoot != 0 && ptr.FromNode != 0 { panic("kp.FromRoot and kp.FromNode should not both be set") } - if (ptr.FromRoot == 0 && ptr.FromNode == 0) && ptr.FromItem != 0 { - panic("kp.FromItem should only be set if either kp.FromRoot or kp.FromItem is set") + if (ptr.FromRoot == 0 && ptr.FromNode == 0) && ptr.FromSlot != 0 { + panic("kp.FromSlot should only be set if either kp.FromRoot or kp.FromSlot is set") } g.EdgesFrom[ptr.FromNode] = append(g.EdgesFrom[ptr.FromNode], ptr) g.EdgesTo[ptr.ToNode] = append(g.EdgesTo[ptr.ToNode], ptr) @@ -171,7 +171,7 @@ func (g Graph) InsertNode(node *btrfstree.Node) { if itemBody, ok := item.Body.(*btrfsitem.Root); ok { kps = append(kps, GraphEdge{ FromRoot: node.Head.Addr, - FromItem: i, + FromSlot: i, FromTree: item.Key.ObjectID, ToNode: itemBody.ByteNr, ToLevel: itemBody.Level, @@ -186,7 +186,7 @@ func (g Graph) InsertNode(node *btrfstree.Node) { for i, kp := range node.BodyInterior { kps[i] = GraphEdge{ FromNode: node.Head.Addr, - FromItem: i, + FromSlot: i, FromTree: node.Head.Owner, ToNode: kp.BlockPtr, ToLevel: node.Head.Level - 1, diff --git a/lib/btrfsutil/graph_loops.go b/lib/btrfsutil/graph_loops.go index b5690af..d613481 100644 --- a/lib/btrfsutil/graph_loops.go +++ b/lib/btrfsutil/graph_loops.go @@ -43,7 +43,7 @@ func (g Graph) renderNode(node btrfsvol.LogicalAddr) []string { } func (g Graph) renderEdge(kp GraphEdge) []string { - a := fmt.Sprintf("[%d]={", kp.FromItem) + a := fmt.Sprintf("[%d]={", kp.FromSlot) b := strings.Repeat(" ", len(a)) ret := []string{ a + fmt.Sprintf("ToNode: %v,", kp.ToNode), -- cgit v1.2.3-2-g168b From 0533a704078ae90782b88609b831627e87092b98 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sat, 1 Apr 2023 17:12:47 -0600 Subject: btrfsutil: OldRebuiltForrest: TreeWalk: At least visit leaf nodes --- lib/btrfsutil/old_rebuilt_forrest.go | 77 +++++++++++++++++++++++------------- 1 file changed, 50 insertions(+), 27 deletions(-) (limited to 'lib') diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go index e6a0399..9035b98 100644 --- a/lib/btrfsutil/old_rebuilt_forrest.go +++ b/lib/btrfsutil/old_rebuilt_forrest.go @@ -346,12 +346,13 @@ func (tree oldRebuiltTree) TreeSubrange(ctx context.Context, min int, searcher b return err } -// TreeWalk implements btrfstree.Tree. It doesn't actually visit -// nodes or keypointers (just items). +// TreeWalk implements btrfstree.Tree. It only visits items and valid +// leaf nodes (not the superblock, interior nodes, or bad nodes). func (tree oldRebuiltTree) TreeWalk(ctx context.Context, cbs btrfstree.TreeWalkHandler) { - if cbs.Item == nil && cbs.BadItem == nil { + if cbs.Node == nil && cbs.Item == nil && cbs.BadItem == nil { return } + visitedNodes := make(containers.Set[btrfsvol.LogicalAddr]) var node *btrfstree.Node tree.Items.Range(func(indexItem *containers.RBNode[oldRebuiltTreeValue]) bool { if ctx.Err() != nil { @@ -361,34 +362,56 @@ func (tree oldRebuiltTree) TreeWalk(ctx context.Context, cbs btrfstree.TreeWalkH if node == nil || node.Head.Addr != indexItem.Value.Node.LAddr { tree.forrest.ReleaseNode(node) node = tree.forrest.readNode(ctx, indexItem.Value.Node) + if cbs.Node != nil && !visitedNodes.Has(indexItem.Value.Node.LAddr) { + nodePath := btrfstree.Path{ + btrfstree.PathRoot{ + Tree: tree, + TreeID: tree.ID, + ToAddr: indexItem.Value.Node.LAddr, + ToGeneration: indexItem.Value.Node.Generation, + ToLevel: indexItem.Value.Node.Level, + }, + } + cbs.Node(nodePath, node) + if ctx.Err() != nil { + return false + } + visitedNodes.Insert(indexItem.Value.Node.LAddr) + } } - item := node.BodyLeaf[indexItem.Value.Slot] - - itemPath := btrfstree.Path{ - btrfstree.PathRoot{ - Tree: tree, - TreeID: tree.ID, - ToAddr: indexItem.Value.Node.LAddr, - ToGeneration: indexItem.Value.Node.Generation, - ToLevel: indexItem.Value.Node.Level, - }, - btrfstree.PathItem{ - FromTree: indexItem.Value.Node.Owner, - FromSlot: indexItem.Value.Slot, - ToKey: indexItem.Value.Key, - }, - } - switch item.Body.(type) { - case *btrfsitem.Error: - if cbs.BadItem != nil { - cbs.BadItem(itemPath, item) + + if cbs.Item != nil || cbs.BadItem != nil { + item := node.BodyLeaf[indexItem.Value.Slot] + itemPath := btrfstree.Path{ + btrfstree.PathRoot{ + Tree: tree, + TreeID: tree.ID, + ToAddr: indexItem.Value.Node.LAddr, + ToGeneration: indexItem.Value.Node.Generation, + ToLevel: indexItem.Value.Node.Level, + }, + btrfstree.PathItem{ + FromTree: indexItem.Value.Node.Owner, + FromSlot: indexItem.Value.Slot, + ToKey: indexItem.Value.Key, + }, } - default: - if cbs.Item != nil { - cbs.Item(itemPath, item) + switch item.Body.(type) { + case *btrfsitem.Error: + if cbs.BadItem != nil { + cbs.BadItem(itemPath, item) + } + default: + if cbs.Item != nil { + cbs.Item(itemPath, item) + } + } + if ctx.Err() != nil { + return false } } - return ctx.Err() == nil + + return true }) tree.forrest.ReleaseNode(node) } -- cgit v1.2.3-2-g168b From 489eeb7da06700fdfadba337cb4ad6aa33b6f99b Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 2 Apr 2023 09:32:48 -0600 Subject: btrfsutil: RebuiltTree: Update comments for the new cache interface --- lib/btrfsutil/rebuilt_tree.go | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'lib') diff --git a/lib/btrfsutil/rebuilt_tree.go b/lib/btrfsutil/rebuilt_tree.go index e65a3f6..d25ffc3 100644 --- a/lib/btrfsutil/rebuilt_tree.go +++ b/lib/btrfsutil/rebuilt_tree.go @@ -33,13 +33,13 @@ type RebuiltTree struct { mu sync.RWMutex Roots containers.Set[btrfsvol.LogicalAddr] // There are 3 more mutable "members" that are protected by - // `mu`; but they live in a shared ARCache. They are all + // `mu`; but they live in a shared Cache. They are all // derived from tree.Roots, which is why it's OK if they get // evicted. // - // 1. tree.leafToRoots() = tree.forrest.leafs.Load(tree.ID) - // 2. tree.RebuiltItems() = tree.forrest.incItems.Load(tree.ID) - // 3. tree.RebuiltPotentialItems() = tree.forrest.excItems.Load(tree.ID) + // 1. tree.leafToRoots() = tree.forrest.leafs.Acquire(tree.ID) + // 2. tree.RebuiltItems() = tree.forrest.incItems.Acquire(tree.ID) + // 3. tree.RebuiltPotentialItems() = tree.forrest.excItems.Acquire(tree.ID) } // evictable member 1: .leafToRoots() ////////////////////////////////////////////////////////////////////////////////// -- cgit v1.2.3-2-g168b From 2bdf2ac12d3fc2770cd101cc30c221255a7fdff6 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 2 Apr 2023 21:11:23 -0600 Subject: btrfsutil: noopRebuiltForrestCallbacks: Add a missing failure-check --- lib/btrfsutil/rebuilt_forrest.go | 3 +++ 1 file changed, 3 insertions(+) (limited to 'lib') diff --git a/lib/btrfsutil/rebuilt_forrest.go b/lib/btrfsutil/rebuilt_forrest.go index 60f3010..fcfb353 100644 --- a/lib/btrfsutil/rebuilt_forrest.go +++ b/lib/btrfsutil/rebuilt_forrest.go @@ -47,6 +47,9 @@ func (cb noopRebuiltForrestCallbacks) LookupRoot(ctx context.Context, tree btrfs key.Offset = 0 return tgt.Compare(key) }) + if !ok { + return 0, btrfsitem.Root{}, false + } itemBody := cb.forrest.readItem(ctx, itemPtr) defer itemBody.Free() switch itemBody := itemBody.(type) { -- cgit v1.2.3-2-g168b From 74a82894df9bdef19d321611255b7923f9f25aff Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 2 Apr 2023 18:36:11 -0600 Subject: btrfsutil: GraphNode: Have .MinItem and .MaxItem work on interior nodes too --- lib/btrfsutil/graph.go | 39 +++++++++++++++++++++++++++++---------- lib/btrfsutil/graph_loops.go | 20 ++++++++++---------- lib/btrfsutil/rebuilt_readitem.go | 4 ++-- 3 files changed, 41 insertions(+), 22 deletions(-) (limited to 'lib') diff --git a/lib/btrfsutil/graph.go b/lib/btrfsutil/graph.go index 090ccf4..fe7fe70 100644 --- a/lib/btrfsutil/graph.go +++ b/lib/btrfsutil/graph.go @@ -23,34 +23,52 @@ import ( ) type GraphNode struct { + Addr btrfsvol.LogicalAddr Level uint8 Generation btrfsprim.Generation Owner btrfsprim.ObjID Items []btrfsprim.Key } -func (n GraphNode) MinItem() btrfsprim.Key { - if len(n.Items) == 0 { +func (n GraphNode) NumItems(g Graph) int { + switch n.Level { + case 0: + return len(n.Items) + default: + return len(g.EdgesFrom[n.Addr]) + } +} + +func (n GraphNode) MinItem(g Graph) btrfsprim.Key { + if n.NumItems(g) == 0 { return btrfsprim.Key{} } - return n.Items[0] + switch n.Level { + case 0: + return n.Items[0] + default: + return g.EdgesFrom[n.Addr][0].ToKey + } } -func (n GraphNode) MaxItem() btrfsprim.Key { - if len(n.Items) == 0 { +func (n GraphNode) MaxItem(g Graph) btrfsprim.Key { + if n.NumItems(g) == 0 { return btrfsprim.Key{} } - return n.Items[len(n.Items)-1] + switch n.Level { + case 0: + return n.Items[len(n.Items)-1] + default: + return g.EdgesFrom[n.Addr][len(g.EdgesFrom[n.Addr])-1].ToKey + } } func (n GraphNode) String() string { if reflect.ValueOf(n).IsZero() { return "{}" } - return fmt.Sprintf(`{lvl:%v, gen:%v, tree:%v, cnt:%v, min:(%v,%v,%v), max:(%v,%v,%v)}`, - n.Level, n.Generation, n.Owner, len(n.Items), - n.MinItem().ObjectID, n.MinItem().ItemType, n.MinItem().Offset, - n.MaxItem().ObjectID, n.MaxItem().ItemType, n.MaxItem().Offset) + return fmt.Sprintf(`{lvl:%v, gen:%v, tree:%v, cnt:%v}`, + n.Level, n.Generation, n.Owner, len(n.Items)) } type GraphEdge struct { @@ -150,6 +168,7 @@ func NewGraph(ctx context.Context, sb btrfstree.Superblock) Graph { func (g Graph) InsertNode(node *btrfstree.Node) { nodeData := GraphNode{ + Addr: node.Head.Addr, Level: node.Head.Level, Generation: node.Head.Generation, Owner: node.Head.Owner, diff --git a/lib/btrfsutil/graph_loops.go b/lib/btrfsutil/graph_loops.go index d613481..2819482 100644 --- a/lib/btrfsutil/graph_loops.go +++ b/lib/btrfsutil/graph_loops.go @@ -24,13 +24,13 @@ func (g Graph) renderNode(node btrfsvol.LogicalAddr) []string { fmt.Sprintf(" gen: %v,", nodeData.Generation), fmt.Sprintf(" num_items: %v,", len(nodeData.Items)), fmt.Sprintf(" min_item: {%d,%v,%d},", - nodeData.MinItem().ObjectID, - nodeData.MinItem().ItemType, - nodeData.MinItem().Offset), + nodeData.MinItem(g).ObjectID, + nodeData.MinItem(g).ItemType, + nodeData.MinItem(g).Offset), fmt.Sprintf(" max_item: {%d,%v,%d}}", - nodeData.MaxItem().ObjectID, - nodeData.MaxItem().ItemType, - nodeData.MaxItem().Offset), + nodeData.MaxItem(g).ObjectID, + nodeData.MaxItem(g).ItemType, + nodeData.MaxItem(g).Offset), } } else if nodeErr, ok := g.BadNodes[node]; ok { return []string{ @@ -59,7 +59,7 @@ func (g Graph) renderEdge(kp GraphEdge) []string { if toNode, ok := g.Nodes[kp.ToNode]; !ok { err = g.BadNodes[kp.ToNode] } else { - err = checkNodeExpectations(kp, toNode) + err = g.loopCheckNodeExpectations(kp, toNode) } if err != nil { c := strings.Repeat(" ", len(a)-1) @@ -110,7 +110,7 @@ func (g Graph) renderLoop(stack []btrfsvol.LogicalAddr) []string { return lines } -func checkNodeExpectations(kp GraphEdge, toNode GraphNode) error { +func (g Graph) loopCheckNodeExpectations(kp GraphEdge, toNode GraphNode) error { var errs derror.MultiError if toNode.Level != kp.ToLevel { errs = append(errs, fmt.Errorf("kp.level=%v != node.level=%v", @@ -123,9 +123,9 @@ func checkNodeExpectations(kp GraphEdge, toNode GraphNode) error { switch { case len(toNode.Items) == 0: errs = append(errs, fmt.Errorf("node.num_items=0")) - case kp.ToKey != (btrfsprim.Key{}) && toNode.MinItem() != kp.ToKey: + case kp.ToKey != (btrfsprim.Key{}) && toNode.MinItem(g) != kp.ToKey: errs = append(errs, fmt.Errorf("kp.key=%v != node.items[0].key=%v", - kp.ToKey, toNode.MinItem())) + kp.ToKey, toNode.MinItem(g))) } if len(errs) > 0 { return errs diff --git a/lib/btrfsutil/rebuilt_readitem.go b/lib/btrfsutil/rebuilt_readitem.go index 73dc01e..80a9e4b 100644 --- a/lib/btrfsutil/rebuilt_readitem.go +++ b/lib/btrfsutil/rebuilt_readitem.go @@ -48,8 +48,8 @@ func (ts *RebuiltForrest) readItem(ctx context.Context, ptr ItemPtr) btrfsitem.I } return nil }, - MinItem: containers.OptionalValue(graphInfo.MinItem()), - MaxItem: containers.OptionalValue(graphInfo.MaxItem()), + MinItem: containers.OptionalValue(graphInfo.MinItem(ts.graph)), + MaxItem: containers.OptionalValue(graphInfo.MaxItem(ts.graph)), }) defer ts.file.ReleaseNode(node) if err != nil { -- cgit v1.2.3-2-g168b From d39e73e41249f5daaf60069a9c77f5728d5d4398 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Mon, 3 Apr 2023 17:30:34 -0600 Subject: btrfsutil: RebuiltTree: Fix a comment --- lib/btrfsutil/rebuilt_tree.go | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/btrfsutil/rebuilt_tree.go b/lib/btrfsutil/rebuilt_tree.go index d25ffc3..b996bdb 100644 --- a/lib/btrfsutil/rebuilt_tree.go +++ b/lib/btrfsutil/rebuilt_tree.go @@ -120,7 +120,7 @@ func (tree *RebuiltTree) indexNode(ctx context.Context, node btrfsvol.LogicalAdd } // isOwnerOK returns whether it is permissible for a node with -// .Head.Owner=owner to be in this tree. +// .Head.Owner=owner and .Head.Generation=gen to be in this tree. func (tree *RebuiltTree) isOwnerOK(owner btrfsprim.ObjID, gen btrfsprim.Generation) bool { for { if owner == tree.ID { -- cgit v1.2.3-2-g168b From 607ea25ea1c0397749db39a15bd52c5e0d3cf552 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Tue, 4 Apr 2023 10:52:13 -0600 Subject: containers: IntervalTree: Add a sanity check that intervals aren't backward --- lib/containers/intervaltree.go | 14 ++++++++++++-- 1 file changed, 12 insertions(+), 2 deletions(-) (limited to 'lib') diff --git a/lib/containers/intervaltree.go b/lib/containers/intervaltree.go index d2e2732..16a9fdd 100644 --- a/lib/containers/intervaltree.go +++ b/lib/containers/intervaltree.go @@ -4,6 +4,10 @@ package containers +import ( + "fmt" +) + type interval[K Ordered[K]] struct { Min, Max K } @@ -71,11 +75,17 @@ func (t *IntervalTree[K, V]) Equal(u *IntervalTree[K, V]) bool { func (t *IntervalTree[K, V]) Insert(val V) { t.init() + min := t.MinFn(val) + max := t.MaxFn(val) + if max.Compare(min) < 0 { + panic(fmt.Errorf("containers.IntervalTree.Insert: max < min: [%v, %v]: %v", + min, max, val)) + } t.inner.Insert(intervalValue[K, V]{ Val: val, ValSpan: interval[K]{ - Min: t.MinFn(val), - Max: t.MaxFn(val), + Min: min, + Max: max, }, }) } -- cgit v1.2.3-2-g168b