diff options
Diffstat (limited to 'lib')
-rw-r--r-- | lib/btrfs/btrfstree/btree_tree.go | 66 | ||||
-rw-r--r-- | lib/btrfs/btrfstree/path.go | 22 | ||||
-rw-r--r-- | lib/btrfsutil/old_rebuilt_forrest.go | 6 | ||||
-rw-r--r-- | lib/btrfsutil/rebuilt_readitem.go | 18 | ||||
-rw-r--r-- | lib/btrfsutil/rebuilt_tree.go | 2 | ||||
-rw-r--r-- | lib/btrfsutil/skinny_paths.go | 32 |
6 files changed, 73 insertions, 73 deletions
diff --git a/lib/btrfs/btrfstree/btree_tree.go b/lib/btrfs/btrfstree/btree_tree.go index f88dd44..e75eb0b 100644 --- a/lib/btrfs/btrfstree/btree_tree.go +++ b/lib/btrfs/btrfstree/btree_tree.go @@ -115,7 +115,7 @@ func (fs TreeOperatorImpl) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, func (fs TreeOperatorImpl) RawTreeWalk(ctx context.Context, rootInfo TreeRoot, errHandle func(*TreeError), cbs TreeWalkHandler) { path := TreePath{{ FromTree: rootInfo.TreeID, - FromItemIdx: -1, + FromItemSlot: -1, ToNodeAddr: rootInfo.RootNode, ToNodeGeneration: rootInfo.Generation, ToNodeLevel: rootInfo.Level, @@ -176,7 +176,7 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandl } itemPath := append(path, TreePathElem{ FromTree: node.Data.Head.Owner, - FromItemIdx: i, + FromItemSlot: i, ToNodeAddr: item.BlockPtr, ToNodeGeneration: item.Generation, ToNodeLevel: node.Data.Head.Level - 1, @@ -203,10 +203,10 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandl } for i, item := range node.Data.BodyLeaf { itemPath := append(path, TreePathElem{ - FromTree: node.Data.Head.Owner, - FromItemIdx: i, - ToKey: item.Key, - ToMaxKey: item.Key, + FromTree: node.Data.Head.Owner, + FromItemSlot: i, + ToKey: item.Key, + ToMaxKey: item.Key, }) if errBody, isErr := item.Body.(*btrfsitem.Error); isErr { if cbs.BadItem == nil { @@ -244,7 +244,7 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandl func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, uint32) int) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) { path := TreePath{{ FromTree: treeRoot.TreeID, - FromItemIdx: -1, + FromItemSlot: -1, ToNodeAddr: treeRoot.RootNode, ToNodeGeneration: treeRoot.Generation, ToNodeLevel: treeRoot.Level, @@ -284,7 +284,7 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, } path = append(path, TreePathElem{ FromTree: node.Data.Head.Owner, - FromItemIdx: lastGood, + FromItemSlot: lastGood, ToNodeAddr: node.Data.BodyInterior[lastGood].BlockPtr, ToNodeGeneration: node.Data.BodyInterior[lastGood].Generation, ToNodeLevel: node.Data.Head.Level - 1, @@ -305,7 +305,7 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, // is returned. // // Implement this search as a binary search. - idx, ok := slices.Search(node.Data.BodyLeaf, func(item Item) int { + slot, ok := slices.Search(node.Data.BodyLeaf, func(item Item) int { return fn(item.Key, item.BodySize) }) if !ok { @@ -313,10 +313,10 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, return nil, nil, iofs.ErrNotExist } path = append(path, TreePathElem{ - FromTree: node.Data.Head.Owner, - FromItemIdx: idx, - ToKey: node.Data.BodyLeaf[idx].Key, - ToMaxKey: node.Data.BodyLeaf[idx].Key, + FromTree: node.Data.Head.Owner, + FromItemSlot: slot, + ToKey: node.Data.BodyLeaf[slot].Key, + ToMaxKey: node.Data.BodyLeaf[slot].Key, }) return path, node, nil } @@ -328,14 +328,14 @@ func (fs TreeOperatorImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.Logical path = path.DeepCopy() // go up - for path.Node(-1).FromItemIdx < 1 { + for path.Node(-1).FromItemSlot < 1 { path = path.Parent() if len(path) == 0 { return nil, nil, nil } } // go left - path.Node(-1).FromItemIdx-- + path.Node(-1).FromItemSlot-- if path.Node(-1).ToNodeAddr != 0 { if node.Addr != path.Node(-2).ToNodeAddr { FreeNodeRef(node) @@ -344,7 +344,7 @@ func (fs TreeOperatorImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.Logical FreeNodeRef(node) return nil, nil, err } - path.Node(-1).ToNodeAddr = node.Data.BodyInterior[path.Node(-1).FromItemIdx].BlockPtr + path.Node(-1).ToNodeAddr = node.Data.BodyInterior[path.Node(-1).FromItemSlot].BlockPtr } } // go down @@ -360,7 +360,7 @@ func (fs TreeOperatorImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.Logical if node.Data.Head.Level > 0 { path = append(path, TreePathElem{ FromTree: node.Data.Head.Owner, - FromItemIdx: len(node.Data.BodyInterior) - 1, + FromItemSlot: len(node.Data.BodyInterior) - 1, ToNodeAddr: node.Data.BodyInterior[len(node.Data.BodyInterior)-1].BlockPtr, ToNodeGeneration: node.Data.BodyInterior[len(node.Data.BodyInterior)-1].Generation, ToNodeLevel: node.Data.Head.Level - 1, @@ -369,10 +369,10 @@ func (fs TreeOperatorImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.Logical }) } else { path = append(path, TreePathElem{ - FromTree: node.Data.Head.Owner, - FromItemIdx: len(node.Data.BodyLeaf) - 1, - ToKey: node.Data.BodyLeaf[len(node.Data.BodyLeaf)-1].Key, - ToMaxKey: node.Data.BodyLeaf[len(node.Data.BodyLeaf)-1].Key, + FromTree: node.Data.Head.Owner, + FromItemSlot: len(node.Data.BodyLeaf) - 1, + ToKey: node.Data.BodyLeaf[len(node.Data.BodyLeaf)-1].Key, + ToMaxKey: node.Data.BodyLeaf[len(node.Data.BodyLeaf)-1].Key, }) } } @@ -402,7 +402,7 @@ func (fs TreeOperatorImpl) next(path TreePath, node *diskio.Ref[btrfsvol.Logical } path.Node(-2).ToNodeLevel = node.Data.Head.Level } - for path.Node(-1).FromItemIdx+1 >= int(node.Data.Head.NumItems) { + for path.Node(-1).FromItemSlot+1 >= int(node.Data.Head.NumItems) { path = path.Parent() if len(path) == 1 { return nil, nil, nil @@ -418,7 +418,7 @@ func (fs TreeOperatorImpl) next(path TreePath, node *diskio.Ref[btrfsvol.Logical } } // go right - path.Node(-1).FromItemIdx++ + path.Node(-1).FromItemSlot++ if path.Node(-1).ToNodeAddr != 0 { if node.Addr != path.Node(-2).ToNodeAddr { FreeNodeRef(node) @@ -427,7 +427,7 @@ func (fs TreeOperatorImpl) next(path TreePath, node *diskio.Ref[btrfsvol.Logical FreeNodeRef(node) return nil, nil, err } - path.Node(-1).ToNodeAddr = node.Data.BodyInterior[path.Node(-1).FromItemIdx].BlockPtr + path.Node(-1).ToNodeAddr = node.Data.BodyInterior[path.Node(-1).FromItemSlot].BlockPtr } } // go down @@ -448,7 +448,7 @@ func (fs TreeOperatorImpl) next(path TreePath, node *diskio.Ref[btrfsvol.Logical } path = append(path, TreePathElem{ FromTree: node.Data.Head.Owner, - FromItemIdx: 0, + FromItemSlot: 0, ToNodeAddr: node.Data.BodyInterior[0].BlockPtr, ToNodeGeneration: node.Data.BodyInterior[0].Generation, ToNodeLevel: node.Data.Head.Level - 1, @@ -457,10 +457,10 @@ func (fs TreeOperatorImpl) next(path TreePath, node *diskio.Ref[btrfsvol.Logical }) } else { path = append(path, TreePathElem{ - FromTree: node.Data.Head.Owner, - FromItemIdx: 0, - ToKey: node.Data.BodyInterior[0].Key, - ToMaxKey: node.Data.BodyInterior[0].Key, + FromTree: node.Data.Head.Owner, + FromItemSlot: 0, + ToKey: node.Data.BodyInterior[0].Key, + ToMaxKey: node.Data.BodyInterior[0].Key, }) } } @@ -490,7 +490,7 @@ func (fs TreeOperatorImpl) TreeSearch(treeID btrfsprim.ObjID, fn func(btrfsprim. if err != nil { return Item{}, err } - item := node.Data.BodyLeaf[path.Node(-1).FromItemIdx] + item := node.Data.BodyLeaf[path.Node(-1).FromItemSlot] item.Body = item.Body.CloneItem() FreeNodeRef(node) return item, nil @@ -526,7 +526,7 @@ func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfspr if err != nil { return nil, err } - middleItem := middleNode.Data.BodyLeaf[middlePath.Node(-1).FromItemIdx] + middleItem := middleNode.Data.BodyLeaf[middlePath.Node(-1).FromItemSlot] ret := []Item{middleItem} var errs derror.MultiError @@ -540,7 +540,7 @@ func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfspr if len(prevPath) == 0 { break } - prevItem := prevNode.Data.BodyLeaf[prevPath.Node(-1).FromItemIdx] + prevItem := prevNode.Data.BodyLeaf[prevPath.Node(-1).FromItemSlot] if fn(prevItem.Key, prevItem.BodySize) != 0 { break } @@ -567,7 +567,7 @@ func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfspr if len(nextPath) == 0 { break } - nextItem := nextNode.Data.BodyLeaf[nextPath.Node(-1).FromItemIdx] + nextItem := nextNode.Data.BodyLeaf[nextPath.Node(-1).FromItemSlot] if fn(nextItem.Key, nextItem.BodySize) != 0 { break } diff --git a/lib/btrfs/btrfstree/path.go b/lib/btrfs/btrfstree/path.go index dd2cb74..9b1a5c7 100644 --- a/lib/btrfs/btrfstree/path.go +++ b/lib/btrfs/btrfstree/path.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 @@ -17,7 +17,7 @@ import ( // system) to the a node or item within one of the btrees in the // system. // -// - The first element will always have an ItemIdx of -1. +// - The first element will always have an ItemSlot of -1. // // - For .Item() callbacks, the last element will always have a // NodeAddr of 0. @@ -26,7 +26,7 @@ import ( // // [superblock: tree=B, lvl=3, gen=6] // | -// | <------------------------------------------ pathElem={from_tree:B, from_idx=-1, +// | <------------------------------------------ pathElem={from_tree:B, from_slot=-1, // | to_addr:0x01, to_gen=6, to_lvl=3} // +[0x01]-------------+ // | lvl=3 gen=6 own=B | @@ -34,7 +34,7 @@ import ( // |0|1|2|3|4|5|6|7|8|9| // +-+-+-+-+-+-+-+-+-+-+ // | -// | <------------------------------ pathElem:{from_tree:B, from_idx:7, +// | <------------------------------ pathElem:{from_tree:B, from_slot:7, // | to_addr:0x02, to_gen:5, to_lvl:2} // +[0x02]--------------+ // | lvl=2 gen=5 own=B | @@ -42,7 +42,7 @@ import ( // |0|1|2|3|4|5|6|7|8|9| // +-+-+-+-+-+-+-+-+-+-+ // | -// | <-------------------- pathElem={from_tree:B, from_idx:6, +// | <-------------------- pathElem={from_tree:B, from_slot:6, // | to_addr:0x03, to_gen:5, to_lvl:1} // +[0x03]-------------+ // | lvl=1 gen=5 own=A | @@ -50,7 +50,7 @@ import ( // |0|1|2|3|4|5|6|7|8|9| // +-+-+-+-+-+-+-+-+-+-+ // | -// | <---------------- pathElem={from_tree:A, from_idx:3, +// | <---------------- pathElem={from_tree:A, from_slot:3, // | to_addr:0x04, to_gen:2, lvl:0} // +[0x04]-------------+ // | lvl=0 gen=2 own=A | @@ -58,7 +58,7 @@ import ( // |0|1|2|3|4|5|6|7|8|9| // +-+-+-+-+-+-+-+-+-+-+ // | -// | <--------------- pathElem={from_tree:A, from_idx:1, +// | <--------------- pathElem={from_tree:A, from_slot:1, // | to_addr:0, to_gen: 0, to_lvl:0} // [item] type TreePath []TreePathElem @@ -68,9 +68,9 @@ type TreePathElem struct { // FromTree is the owning tree ID of the parent node; or the // well-known tree ID if this is the root. FromTree btrfsprim.ObjID - // FromItemIdx is the index of this KeyPointer in the parent + // FromItemSlot is the index of this KeyPointer in the parent // Node; or -1 if this is the root and there is no KeyPointer. - FromItemIdx int + FromItemSlot int // ToNodeAddr is the address of the node that the KeyPointer // points at, or 0 if this is a leaf item and nothing is being @@ -104,13 +104,13 @@ func (path TreePath) String() string { } else { var ret strings.Builder fmt.Fprintf(&ret, "%s->", path[0].FromTree.Format(btrfsprim.ROOT_TREE_OBJECTID)) - if len(path) == 1 && path[0] == (TreePathElem{FromTree: path[0].FromTree, FromItemIdx: -1}) { + if len(path) == 1 && path[0] == (TreePathElem{FromTree: path[0].FromTree, FromItemSlot: -1}) { ret.WriteString("(empty-path)") } else { path[0].writeNodeTo(&ret) } for _, elem := range path[1:] { - fmt.Fprintf(&ret, "[%v]", elem.FromItemIdx) + fmt.Fprintf(&ret, "[%v]", elem.FromItemSlot) if elem.ToNodeAddr != 0 { ret.WriteString("->") elem.writeNodeTo(&ret) diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go index 2386803..6014793 100644 --- a/lib/btrfsutil/old_rebuilt_forrest.go +++ b/lib/btrfsutil/old_rebuilt_forrest.go @@ -237,7 +237,7 @@ func (bt *OldRebuiltForrest) TreeSearch(treeID btrfsprim.ObjID, fn func(btrfspri return btrfstree.Item{}, bt.addErrs(tree, fn, err) } - item := node.Data.BodyLeaf[itemPath.Node(-1).FromItemIdx] + item := node.Data.BodyLeaf[itemPath.Node(-1).FromItemSlot] item.Body = item.Body.CloneItem() // Since we were only asked to return 1 item, it isn't @@ -275,7 +275,7 @@ func (bt *OldRebuiltForrest) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfs return nil, bt.addErrs(tree, fn, err) } } - ret[i] = node.Data.BodyLeaf[itemPath.Node(-1).FromItemIdx] + ret[i] = node.Data.BodyLeaf[itemPath.Node(-1).FromItemSlot] ret[i].Body = ret[i].Body.CloneItem() } btrfstree.FreeNodeRef(node) @@ -315,7 +315,7 @@ func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjI return true } } - item := node.Data.BodyLeaf[itemPath.Node(-1).FromItemIdx] + item := node.Data.BodyLeaf[itemPath.Node(-1).FromItemSlot] if err := cbs.Item(itemPath, item); err != nil { errHandle(&btrfstree.TreeError{Path: itemPath, Err: err}) } diff --git a/lib/btrfsutil/rebuilt_readitem.go b/lib/btrfsutil/rebuilt_readitem.go index a508d99..016299c 100644 --- a/lib/btrfsutil/rebuilt_readitem.go +++ b/lib/btrfsutil/rebuilt_readitem.go @@ -22,11 +22,11 @@ import ( type ItemPtr struct { Node btrfsvol.LogicalAddr - Idx int + Slot int } func (ptr ItemPtr) String() string { - return fmt.Sprintf("node@%v[%v]", ptr.Node, ptr.Idx) + return fmt.Sprintf("node@%v[%v]", ptr.Node, ptr.Slot) } type SizeAndErr struct { @@ -74,7 +74,7 @@ func (o *KeyIO) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.N for i, item := range nodeRef.Data.BodyLeaf { ptr := ItemPtr{ Node: nodeRef.Addr, - Idx: i, + Slot: i, } switch itemBody := item.Body.(type) { case *btrfsitem.Inode: @@ -159,13 +159,13 @@ func (o *KeyIO) ReadItem(ctx context.Context, ptr ItemPtr) btrfsitem.Item { if o.graph.Nodes[ptr.Node].Level != 0 { panic(fmt.Errorf("should not happen: btrfsutil.KeyIO.ReadItem called for non-leaf node@%v", ptr.Node)) } - if ptr.Idx < 0 { - panic(fmt.Errorf("should not happen: btrfsutil.KeyIO.ReadItem called for negative item index: %v", ptr.Idx)) + if ptr.Slot < 0 { + panic(fmt.Errorf("should not happen: btrfsutil.KeyIO.ReadItem called for negative item slot: %v", ptr.Slot)) } items := o.readNode(ctx, ptr.Node).Data.BodyLeaf - if ptr.Idx >= len(items) { - panic(fmt.Errorf("should not happen: btrfsutil.KeyIO.ReadItem called for out-of-bounds item index: index=%v len=%v", - ptr.Idx, len(items))) + if ptr.Slot >= len(items) { + panic(fmt.Errorf("should not happen: btrfsutil.KeyIO.ReadItem called for out-of-bounds item slot: slot=%v len=%v", + ptr.Slot, len(items))) } - return items[ptr.Idx].Body.CloneItem() + return items[ptr.Slot].Body.CloneItem() } diff --git a/lib/btrfsutil/rebuilt_tree.go b/lib/btrfsutil/rebuilt_tree.go index 1009204..9e23074 100644 --- a/lib/btrfsutil/rebuilt_tree.go +++ b/lib/btrfsutil/rebuilt_tree.go @@ -192,7 +192,7 @@ func (tree *RebuiltTree) items(ctx context.Context, cache containers.Map[btrfspr for j, itemKey := range tree.forrest.graph.Nodes[leaf].Items { newPtr := ItemPtr{ Node: leaf, - Idx: j, + Slot: j, } if oldPtr, exists := index.Load(itemKey); !exists { index.Store(itemKey, newPtr) diff --git a/lib/btrfsutil/skinny_paths.go b/lib/btrfsutil/skinny_paths.go index da86273..adf539b 100644 --- a/lib/btrfsutil/skinny_paths.go +++ b/lib/btrfsutil/skinny_paths.go @@ -39,8 +39,8 @@ func (a *SkinnyPathArena) init() { } } -func (a *SkinnyPathArena) getItem(parent btrfstree.TreePath, itemIdx int) (btrfstree.TreePathElem, error) { - if itemIdx < 0 { +func (a *SkinnyPathArena) getItem(parent btrfstree.TreePath, itemSlot int) (btrfstree.TreePathElem, error) { + if itemSlot < 0 { panic("should not happen") } @@ -48,7 +48,7 @@ func (a *SkinnyPathArena) getItem(parent btrfstree.TreePath, itemIdx int) (btrfs ret, ok := a.fatItems.Load(skinnyItem{ Node: parent.Node(-1).ToNodeAddr, - Item: itemIdx, + Item: itemSlot, }) if ok { return ret, nil @@ -60,7 +60,7 @@ func (a *SkinnyPathArena) getItem(parent btrfstree.TreePath, itemIdx int) (btrfs return btrfstree.TreePathElem{}, err } if node.Data.Head.Level > 0 { - if itemIdx >= len(node.Data.BodyInterior) { + if itemSlot >= len(node.Data.BodyInterior) { panic("should not happen") } for i, item := range node.Data.BodyInterior { @@ -70,7 +70,7 @@ func (a *SkinnyPathArena) getItem(parent btrfstree.TreePath, itemIdx int) (btrfs } elem := btrfstree.TreePathElem{ FromTree: node.Data.Head.Owner, - FromItemIdx: i, + FromItemSlot: i, ToNodeAddr: item.BlockPtr, ToNodeGeneration: item.Generation, ToNodeLevel: node.Data.Head.Level - 1, @@ -78,23 +78,23 @@ func (a *SkinnyPathArena) getItem(parent btrfstree.TreePath, itemIdx int) (btrfs ToMaxKey: toMaxKey, } a.fatItems.Store(skinnyItem{Node: parent.Node(-1).ToNodeAddr, Item: i}, elem) - if i == itemIdx { + if i == itemSlot { ret = elem } } } else { - if itemIdx >= len(node.Data.BodyLeaf) { + if itemSlot >= len(node.Data.BodyLeaf) { panic("should not happen") } for i, item := range node.Data.BodyLeaf { elem := btrfstree.TreePathElem{ - FromTree: node.Data.Head.Owner, - FromItemIdx: i, - ToKey: item.Key, - ToMaxKey: item.Key, + FromTree: node.Data.Head.Owner, + FromItemSlot: i, + ToKey: item.Key, + ToMaxKey: item.Key, } a.fatItems.Store(skinnyItem{Node: parent.Node(-1).ToNodeAddr, Item: i}, elem) - if i == itemIdx { + if i == itemSlot { ret = elem } } @@ -114,8 +114,8 @@ func (a *SkinnyPathArena) Deflate(fat btrfstree.TreePath) SkinnyPath { a.fatRoots[elem.ToNodeAddr] = elem ret.Root = elem.ToNodeAddr } else { - a.fatItems.Store(skinnyItem{Node: prevNode, Item: elem.FromItemIdx}, elem) - ret.Items = append(ret.Items, elem.FromItemIdx) + a.fatItems.Store(skinnyItem{Node: prevNode, Item: elem.FromItemSlot}, elem) + ret.Items = append(ret.Items, elem.FromItemSlot) } prevNode = elem.ToNodeAddr } @@ -134,8 +134,8 @@ func (a *SkinnyPathArena) Inflate(skinny SkinnyPath) btrfstree.TreePath { } ret = append(ret, root) - for _, itemIdx := range skinny.Items { - elem, err := a.getItem(ret, itemIdx) + for _, itemSlot := range skinny.Items { + elem, err := a.getItem(ret, itemSlot) if err != nil { panic(err) } |