wip ls-files

6 files changed, 266 insertions, 52 deletions

diff --git a/cmd/btrfs-ls-files/main.go b/cmd/btrfs-ls-files/main.go
new file mode 100644
index 0000000..4cb4b56
--- /dev/null
+++ b/cmd/btrfs-ls-files/main.go
@@ -0,0 +1,83 @@
+package main
+
+import (
+	"fmt"
+	"os"
+
+	"lukeshu.com/btrfs-tools/pkg/btrfs"
+	"lukeshu.com/btrfs-tools/pkg/btrfs/btrfsitem"
+	"lukeshu.com/btrfs-tools/pkg/btrfsmisc"
+	"lukeshu.com/btrfs-tools/pkg/util"
+)
+
+func main() {
+	if err := Main(os.Args[1:]...); err != nil {
+		fmt.Fprintf(os.Stderr, "%v: error: %v\n", os.Args[0], err)
+		os.Exit(1)
+	}
+}
+
+func Main(imgfilenames ...string) (err error) {
+	maybeSetErr := func(_err error) {
+		if _err != nil && err == nil {
+			err = _err
+		}
+	}
+
+	fs, err := btrfsmisc.Open(os.O_RDONLY, imgfilenames...)
+	if err != nil {
+		return err
+	}
+	defer func() {
+		maybeSetErr(fs.Close())
+	}()
+
+	sb, err := fs.Superblock()
+	if err != nil {
+		return err
+	}
+
+	fsTreeRoot, err := fs.TreeLookup(sb.Data.RootTree, btrfs.Key{
+		ObjectID: btrfs.FS_TREE_OBJECTID,
+		ItemType: btrfsitem.ROOT_ITEM_KEY,
+		Offset:   0,
+	})
+	if err != nil {
+		return fmt.Errorf("look up FS_TREE: %w", err)
+	}
+	fsTreeRootBody := fsTreeRoot.Body.(btrfsitem.Root)
+	fsTree := fsTreeRootBody.ByteNr
+
+	return printDir(fs, fsTree, "", "/", fsTreeRootBody.RootDirID, fsTreeRootBody.Inode)
+}
+
+func printDir(fs *btrfs.FS, fsTree btrfs.LogicalAddr, prefix, dirName string, dirInodeNum btrfs.ObjID, dirInode btrfsitem.Inode) error {
+	fmt.Printf("%s[%s\tino=%d\tuid=%d\tgid=%d\tsize=%d] %s\n",
+		prefix,
+		dirInode.Mode, dirInodeNum, dirInode.UID, dirInode.GID, dirInode.Size,
+		dirName)
+	items, err := fs.TreeSearchAll(fsTree, func(key btrfs.Key) int {
+		return util.CmpUint(dirInodeNum, key.ObjectID)
+	})
+	if err != nil {
+		return fmt.Errorf("read directory %q: %w", dirName, err)
+	}
+	for _, item := range items {
+		switch item.Head.Key.ItemType {
+		case btrfsitem.INODE_ITEM_KEY:
+			// TODO
+		case btrfsitem.INODE_REF_KEY:
+			// TODO
+		case btrfsitem.DIR_ITEM_KEY:
+			// skip?
+		case btrfsitem.DIR_INDEX_KEY:
+			for _, entry := range item.Body.(btrfsitem.DirList) {
+				fmt.Println(string(entry.Name))
+			}
+		case btrfsitem.XATTR_ITEM_KEY:
+		default:
+			panic(fmt.Errorf("TODO: handle item type %v", item.Head.Key.ItemType))
+		}
+	}
+	return nil
+}
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[:])
+}