From 9c581316735f78c4fec9787aa4fd8635398b4c51 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sat, 2 Jul 2022 12:49:24 -0600 Subject: wip ls-files --- pkg/btrfs/btree.go | 60 +++++++++++++++++++------ pkg/btrfs/btrfsitem/item_dir.go | 4 ++ pkg/btrfs/btrfsitem/item_inode.go | 33 +++++++------- pkg/btrfs/btrfsitem/item_root.go | 46 ++++++++++---------- pkg/linux/stat.go | 92 +++++++++++++++++++++++++++++++++++++++ 5 files changed, 183 insertions(+), 52 deletions(-) create mode 100644 pkg/linux/stat.go (limited to 'pkg') diff --git a/pkg/btrfs/btree.go b/pkg/btrfs/btree.go index fb3dd65..9f38eee 100644 --- a/pkg/btrfs/btree.go +++ b/pkg/btrfs/btree.go @@ -8,7 +8,6 @@ import ( "math" "strings" - "lukeshu.com/btrfs-tools/pkg/btrfs/btrfsitem" "lukeshu.com/btrfs-tools/pkg/util" ) @@ -261,7 +260,7 @@ func (fs *FS) prev(path TreePath, node *util.Ref[LogicalAddr, Node]) (TreePath, path = append(TreePath(nil), path...) // go up - for path[len(path)-1].ItemIdx == 0 { + for path[len(path)-1].ItemIdx < 1 { path = path[:len(path)-1] if len(path) == 0 { return nil, nil, nil @@ -269,6 +268,15 @@ func (fs *FS) prev(path TreePath, node *util.Ref[LogicalAddr, Node]) (TreePath, } // go left path[len(path)-1].ItemIdx-- + if path[len(path)-1].NodeAddr != 0 { + if node.Addr != path[len(path)-2].NodeAddr { + node, err = fs.readNodeAtLevel(path[len(path)-2].NodeAddr, path[len(path)-2].NodeLevel) + if err != nil { + return nil, nil, err + } + path[len(path)-1].NodeAddr = node.Data.BodyInternal[path[len(path)-1].ItemIdx].BlockPtr + } + } // go down for path[len(path)-1].NodeAddr != 0 { if node.Addr != path[len(path)-1].NodeAddr { @@ -276,7 +284,6 @@ func (fs *FS) prev(path TreePath, node *util.Ref[LogicalAddr, Node]) (TreePath, if err != nil { return nil, nil, err } - path[len(path)-1].NodeLevel = node.Data.Head.Level } if node.Data.Head.Level > 0 { path = append(path, TreePathElem{ @@ -327,6 +334,15 @@ func (fs *FS) next(path TreePath, node *util.Ref[LogicalAddr, Node]) (TreePath, } // go left path[len(path)-1].ItemIdx++ + if path[len(path)-1].NodeAddr != 0 { + if node.Addr != path[len(path)-2].NodeAddr { + node, err = fs.readNodeAtLevel(path[len(path)-2].NodeAddr, path[len(path)-2].NodeLevel) + if err != nil { + return nil, nil, err + } + path[len(path)-1].NodeAddr = node.Data.BodyInternal[path[len(path)-1].ItemIdx].BlockPtr + } + } // go down for path[len(path)-1].NodeAddr != 0 { if node.Addr != path[len(path)-1].NodeAddr { @@ -358,16 +374,15 @@ func (fs *FS) next(path TreePath, node *util.Ref[LogicalAddr, Node]) (TreePath, return path, node, nil } -func (fs *FS) TreeSearch(treeRoot LogicalAddr, fn func(Key) int) (Key, btrfsitem.Item, error) { +func (fs *FS) TreeSearch(treeRoot LogicalAddr, fn func(Key) int) (Item, error) { path, node, err := fs.treeSearch(treeRoot, fn) if err != nil { - return Key{}, nil, err + return Item{}, err } - item := node.Data.BodyLeaf[path[len(path)-1].ItemIdx] - return item.Head.Key, item.Body, nil + return node.Data.BodyLeaf[path[len(path)-1].ItemIdx], nil } -func (fs *FS) TreeLookup(treeRoot LogicalAddr, key Key) (Key, btrfsitem.Item, error) { +func (fs *FS) TreeLookup(treeRoot LogicalAddr, key Key) (Item, error) { return fs.TreeSearch(treeRoot, key.Cmp) } @@ -376,22 +391,41 @@ func (fs *FS) TreeSearchAll(treeRoot LogicalAddr, fn func(Key) int) ([]Item, err if err != nil { return nil, err } + middleItem := middleNode.Data.BodyLeaf[middlePath[len(middlePath)-1].ItemIdx] - var ret = []Item{middleNode.Data.BodyLeaf[middlePath[len(middlePath)-1].ItemIdx]} - for prevPath, prevNode := middlePath, middleNode; prevPath != nil; { + var ret = []Item{middleItem} + i := 0 + for prevPath, prevNode := middlePath, middleNode; true; { + i-- prevPath, prevNode, err = fs.prev(prevPath, prevNode) if err != nil { return nil, err } - ret = append(ret, prevNode.Data.BodyLeaf[prevPath[len(prevPath)-1].ItemIdx]) + if prevPath == nil { + break + } + prevItem := prevNode.Data.BodyLeaf[prevPath[len(prevPath)-1].ItemIdx] + if fn(prevItem.Head.Key) != 0 { + break + } + ret = append(ret, prevItem) } util.ReverseSlice(ret) - for nextPath, nextNode := middlePath, middleNode; nextPath != nil; { + i = 0 + for nextPath, nextNode := middlePath, middleNode; true; { + i++ nextPath, nextNode, err = fs.next(nextPath, nextNode) if err != nil { return nil, err } - ret = append(ret, nextNode.Data.BodyLeaf[nextPath[len(nextPath)-1].ItemIdx]) + if nextPath == nil { + break + } + nextItem := nextNode.Data.BodyLeaf[nextPath[len(nextPath)-1].ItemIdx] + if fn(nextItem.Head.Key) != 0 { + break + } + ret = append(ret, nextItem) } return ret, nil } diff --git a/pkg/btrfs/btrfsitem/item_dir.go b/pkg/btrfs/btrfsitem/item_dir.go index d239332..253d257 100644 --- a/pkg/btrfs/btrfsitem/item_dir.go +++ b/pkg/btrfs/btrfsitem/item_dir.go @@ -7,6 +7,10 @@ import ( "lukeshu.com/btrfs-tools/pkg/btrfs/internal" ) +// key.objectid = inode of directory containing this entry +// key.offset = +// for DIR_ITEM and XATTR_ITEM = crc32c(name) +// for DIR_INDEX = index id in the directory (starting at 2, because "." and "..") type DirList []Dir // DIR_ITEM=84 DIR_INDEX=96 XATTR_ITEM=24 func (o *DirList) UnmarshalBinary(dat []byte) (int, error) { diff --git a/pkg/btrfs/btrfsitem/item_inode.go b/pkg/btrfs/btrfsitem/item_inode.go index 3b7d577..b41f288 100644 --- a/pkg/btrfs/btrfsitem/item_inode.go +++ b/pkg/btrfs/btrfsitem/item_inode.go @@ -3,27 +3,28 @@ package btrfsitem import ( "lukeshu.com/btrfs-tools/pkg/binstruct" "lukeshu.com/btrfs-tools/pkg/btrfs/internal" + "lukeshu.com/btrfs-tools/pkg/linux" "lukeshu.com/btrfs-tools/pkg/util" ) type Inode struct { // INODE_ITEM=1 - Generation internal.Generation `bin:"off=0x0, siz=0x8"` - TransID int64 `bin:"off=0x8, siz=0x8"` - Size int64 `bin:"off=0x10, siz=0x8"` - NumBytes int64 `bin:"off=0x18, siz=0x8"` - BlockGroup int64 `bin:"off=0x20, siz=0x8"` - NLink int32 `bin:"off=0x28, siz=0x4"` - UID int32 `bin:"off=0x2C, siz=0x4"` - GID int32 `bin:"off=0x30, siz=0x4"` - Mode int32 `bin:"off=0x34, siz=0x4"` - RDev int64 `bin:"off=0x38, siz=0x8"` - Flags InodeFlags `bin:"off=0x40, siz=0x8"` - Sequence int64 `bin:"off=0x48, siz=0x8"` + Generation internal.Generation `bin:"off=0x00, siz=0x08"` + TransID int64 `bin:"off=0x08, siz=0x08"` + Size int64 `bin:"off=0x10, siz=0x08"` // stat + NumBytes int64 `bin:"off=0x18, siz=0x08"` + BlockGroup int64 `bin:"off=0x20, siz=0x08"` + NLink int32 `bin:"off=0x28, siz=0x04"` // stat + UID int32 `bin:"off=0x2C, siz=0x04"` // stat + GID int32 `bin:"off=0x30, siz=0x04"` // stat + Mode linux.StatMode `bin:"off=0x34, siz=0x04"` // stat + RDev int64 `bin:"off=0x38, siz=0x08"` // stat + Flags InodeFlags `bin:"off=0x40, siz=0x08"` // statx.stx_attributes, sorta + Sequence int64 `bin:"off=0x48, siz=0x08"` // NFS Reserved [4]int64 `bin:"off=0x50, siz=0x20"` - ATime internal.Time `bin:"off=0x70, siz=0xc"` - CTime internal.Time `bin:"off=0x7c, siz=0xc"` - MTime internal.Time `bin:"off=0x88, siz=0xc"` - OTime internal.Time `bin:"off=0x94, siz=0xc"` + ATime internal.Time `bin:"off=0x70, siz=0x0c"` // stat + CTime internal.Time `bin:"off=0x7c, siz=0x0c"` // stat + MTime internal.Time `bin:"off=0x88, siz=0x0c"` // stat + OTime internal.Time `bin:"off=0x94, siz=0x0c"` // statx.stx_btime (why is this called "otime" instead of "btime"?) binstruct.End `bin:"off=0xa0"` } diff --git a/pkg/btrfs/btrfsitem/item_root.go b/pkg/btrfs/btrfsitem/item_root.go index bdf1b7b..de0a070 100644 --- a/pkg/btrfs/btrfsitem/item_root.go +++ b/pkg/btrfs/btrfsitem/item_root.go @@ -8,31 +8,31 @@ import ( ) type Root struct { // ROOT_ITEM=132 - Inode Inode `bin:"off=0x0, siz=0xa0"` - Generation internal.Generation `bin:"off=0xa0, siz=0x8"` - RootDirID int64 `bin:"off=0xa8, siz=0x8"` - ByteNr btrfsvol.LogicalAddr `bin:"off=0xb0, siz=0x8"` - ByteLimit int64 `bin:"off=0xb8, siz=0x8"` - BytesUsed int64 `bin:"off=0xc0, siz=0x8"` - LastSnapshot int64 `bin:"off=0xc8, siz=0x8"` - Flags RootFlags `bin:"off=0xd0, siz=0x8"` - Refs int32 `bin:"off=0xd8, siz=0x4"` - DropProgress internal.Key `bin:"off=0xdc, siz=0x11"` - DropLevel uint8 `bin:"off=0xed, siz=0x1"` - Level uint8 `bin:"off=0xee, siz=0x1"` - GenerationV2 internal.Generation `bin:"off=0xef, siz=0x8"` - UUID util.UUID `bin:"off=0xF7, siz=0x10"` + Inode Inode `bin:"off=0x000, siz=0xa0"` + Generation internal.Generation `bin:"off=0x0a0, siz=0x08"` + RootDirID internal.ObjID `bin:"off=0x0a8, siz=0x08"` + ByteNr btrfsvol.LogicalAddr `bin:"off=0x0b0, siz=0x08"` + ByteLimit int64 `bin:"off=0x0b8, siz=0x08"` + BytesUsed int64 `bin:"off=0x0c0, siz=0x08"` + LastSnapshot int64 `bin:"off=0x0c8, siz=0x08"` + Flags RootFlags `bin:"off=0x0d0, siz=0x08"` + Refs int32 `bin:"off=0x0d8, siz=0x04"` + DropProgress internal.Key `bin:"off=0x0dc, siz=0x11"` + DropLevel uint8 `bin:"off=0x0ed, siz=0x01"` + Level uint8 `bin:"off=0x0ee, siz=0x01"` + GenerationV2 internal.Generation `bin:"off=0x0ef, siz=0x08"` + UUID util.UUID `bin:"off=0x0f7, siz=0x10"` ParentUUID util.UUID `bin:"off=0x107, siz=0x10"` ReceivedUUID util.UUID `bin:"off=0x117, siz=0x10"` - CTransID int64 `bin:"off=0x127, siz=0x8"` - OTransID int64 `bin:"off=0x12f, siz=0x8"` - STransID int64 `bin:"off=0x137, siz=0x8"` - RTransID int64 `bin:"off=0x13f, siz=0x8"` - CTime internal.Time `bin:"off=0x147, siz=0xc"` - OTime internal.Time `bin:"off=0x153, siz=0xc"` - STime internal.Time `bin:"off=0x15F, siz=0xc"` - RTime internal.Time `bin:"off=0x16b, siz=0xc"` - GlobalTreeID internal.ObjID `bin:"off=0x177, siz=0x8"` + CTransID int64 `bin:"off=0x127, siz=0x08"` + OTransID int64 `bin:"off=0x12f, siz=0x08"` + STransID int64 `bin:"off=0x137, siz=0x08"` + RTransID int64 `bin:"off=0x13f, siz=0x08"` + CTime internal.Time `bin:"off=0x147, siz=0x0c"` + OTime internal.Time `bin:"off=0x153, siz=0x0c"` + STime internal.Time `bin:"off=0x15f, siz=0x0c"` + RTime internal.Time `bin:"off=0x16b, siz=0x0c"` + GlobalTreeID internal.ObjID `bin:"off=0x177, siz=0x08"` Reserved [7]int64 `bin:"off=0x17f, siz=0x38"` binstruct.End `bin:"off=0x1b7"` } diff --git a/pkg/linux/stat.go b/pkg/linux/stat.go new file mode 100644 index 0000000..15e18a9 --- /dev/null +++ b/pkg/linux/stat.go @@ -0,0 +1,92 @@ +package linux + +type StatMode uint32 + +const ( + // 16 bits = 5⅓ octal characters + + ModeFmt StatMode = 0o17_0000 // mask for the type bits + + _ModeFmtUnused000 StatMode = 0o00_0000 + ModeFmtNamedPipe StatMode = 0o01_0000 // type: named pipe (FIFO) + ModeFmtCharDevice StatMode = 0o02_0000 // type: character device + _ModeFmtUnused003 StatMode = 0o03_0000 + ModeFmtDir StatMode = 0o04_0000 // type: directory + _ModeFmtUnused005 StatMode = 0o05_0000 + ModeFmtBlockDevice StatMode = 0o06_0000 // type: block device + _ModeFmtUnused007 StatMode = 0o07_0000 + ModeFmtRegular StatMode = 0o10_0000 // type: regular file + _ModeFmtUnused011 StatMode = 0o11_0000 + ModeFmtSymlink StatMode = 0o12_0000 // type: symbolic link + _ModeFmtUnused013 StatMode = 0o13_0000 + ModeFmtSocket StatMode = 0o14_0000 // type: socket file + _ModeFmtUnused015 StatMode = 0o15_0000 + _ModeFmtUnused016 StatMode = 0o16_0000 + _ModeFmtUnused017 StatMode = 0o17_0000 + + ModePerm StatMode = 0o00_7777 // mask for permission bits + + ModePermSetUID StatMode = 0o00_4000 // permission: set user id + ModePermSetGID StatMode = 0o00_2000 // permission: set group ID + ModePermSticky StatMode = 0o00_1000 // permission: sticky bit + + ModePermUsrR StatMode = 0o00_0400 // permission: user: read + ModePermUsrW StatMode = 0o00_0200 // permission: user: write + ModePermUsrX StatMode = 0o00_0100 // permission: user: execute + + ModePermGrpR StatMode = 0o00_0040 // permission: group: read + ModePermGrpW StatMode = 0o00_0020 // permission: group: write + ModePermGrpX StatMode = 0o00_0010 // permission: group: execute + + ModePermOthR StatMode = 0o00_0004 // permission: other: read + ModePermOthW StatMode = 0o00_0002 // permission: other: write + ModePermOthX StatMode = 0o00_0001 // permission: other: execute +) + +// IsDir reports whether mode describes a directory. +// +// That is, it tests that the ModeFmt bits are set to ModeFmtDir. +func (mode StatMode) IsDir() bool { + return mode&ModeFmt == ModeFmtDir +} + +// IsRegular reports whether m describes a regular file. +// +// That is, it tests that the ModeFmt bits are set to ModeFmtRegular. +func (mode StatMode) IsRegular() bool { + return mode&ModeFmt == ModeFmtRegular +} + +// String returns a textual representation of the mode. +// +// This is the format that POSIX specifies for showing the mode in the +// output of the `ls -l` command. POSIX does not specify the +// character to use to indicate a ModeFmtSocket file; this method uses +// 's' (GNU `ls` behavior; though POSIX notes that many +// implementations use '=' for sockets). +func (mode StatMode) String() string { + buf := [10]byte{ + // type: This string is easy; it directly pairs with + // the above ModeFmtXXX list above; the character in + // the string left-to-right corresponds with the + // constant in the list top-to-bottom. + "?pc?d?b?-?l?s???"[mode>>12], + + // owner + "-r"[(mode>>8)&0o1], + "-w"[(mode>>7)&0o1], + "-xSs"[((mode>>6)&0o1)|((mode>>10)&0o2)], + + // group + "-r"[(mode>>5)&0o1], + "-w"[(mode>>4)&0o1], + "-xSs"[((mode>>3)&0o1)|((mode>>9)&0o2)], + + // group + "-r"[(mode>>2)&0o1], + "-w"[(mode>>1)&0o1], + "-xTt"[((mode>>0)&0o1)|((mode>>8)&0o2)], + } + + return string(buf[:]) +} -- cgit v1.2.3-2-g168b