more work on ls-files

5 files changed, 118 insertions, 29 deletions

diff --git a/cmd/btrfs-ls-files/main.go b/cmd/btrfs-ls-files/main.go
index 4f9f520..d6b8c97 100644
--- a/cmd/btrfs-ls-files/main.go
+++ b/cmd/btrfs-ls-files/main.go
@@ -3,6 +3,10 @@ package main
 import (
 	"fmt"
 	"os"
+	"reflect"
+	"strings"
+
+	"github.com/datawire/dlib/derror"
 
 	"lukeshu.com/btrfs-tools/pkg/btrfs"
 	"lukeshu.com/btrfs-tools/pkg/btrfs/btrfsitem"
@@ -49,36 +53,116 @@ func Main(imgfilenames ...string) (err error) {
 	fsTreeRootBody := fsTreeRoot.Body.(btrfsitem.Root)
 	fsTree := fsTreeRootBody.ByteNr
 
-	return printDir(fs, fsTree, "", "/", fsTreeRootBody.RootDirID, fsTreeRootBody.Inode)
+	printDir(fs, fsTree, "", "", "/", fsTreeRootBody.RootDirID)
+	return nil
 }
 
-func printDir(fs *btrfs.FS, fsTree btrfsvol.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)
+const (
+	tS = "    "
+	tl = "│   "
+	tT = "├── "
+	tL = "└── "
+)
+
+func printDir(fs *btrfs.FS, fsTree btrfsvol.LogicalAddr, prefix0, prefix1, dirName string, dirInode btrfs.ObjID) {
+	var errs derror.MultiError
 	items, err := fs.TreeSearchAll(fsTree, func(key btrfs.Key) int {
-		return util.CmpUint(dirInodeNum, key.ObjectID)
+		return util.CmpUint(dirInode, key.ObjectID)
 	})
 	if err != nil {
-		return fmt.Errorf("read directory %q: %w", dirName, err)
+		errs = append(errs, fmt.Errorf("read dir: %w", err))
 	}
+	var dirInodeDat btrfsitem.Inode
+	var dirInodeDatOK bool
+	membersByIndex := make(map[uint64]btrfsitem.DirEntry)
+	membersByNameHash := make(map[uint64]btrfsitem.DirEntry)
 	for _, item := range items {
 		switch item.Head.Key.ItemType {
 		case btrfsitem.INODE_ITEM_KEY:
-			// TODO
+			if dirInodeDatOK {
+				errs = append(errs, fmt.Errorf("read dir: multiple inodes"))
+				continue
+			}
+			dirInodeDat = item.Body.(btrfsitem.Inode)
+			dirInodeDatOK = true
 		case btrfsitem.INODE_REF_KEY:
 			// TODO
 		case btrfsitem.DIR_ITEM_KEY:
-			// skip?
+			body := item.Body.(btrfsitem.DirEntries)
+			if len(body) != 1 {
+				errs = append(errs, fmt.Errorf("read dir: multiple direntries in single dir_item?"))
+				continue
+			}
+			for _, entry := range body {
+				namehash := btrfsitem.NameHash(entry.Name)
+				if namehash != item.Head.Key.Offset {
+					errs = append(errs, fmt.Errorf("read dir: direntry crc32c mismatch: key=%#x crc32c(%q)=%#x",
+						item.Head.Key.Offset, entry.Name, namehash))
+					continue
+				}
+				if other, exists := membersByNameHash[namehash]; exists {
+					errs = append(errs, fmt.Errorf("read dir: multiple instances of direntry crc32c(%q|%q)=%#x",
+						other.Name, entry.Name, namehash))
+					continue
+				}
+				membersByNameHash[btrfsitem.NameHash(entry.Name)] = entry
+			}
 		case btrfsitem.DIR_INDEX_KEY:
-			for _, entry := range item.Body.(btrfsitem.DirList) {
-				fmt.Println(string(entry.Name))
+			for i, entry := range item.Body.(btrfsitem.DirEntries) {
+				index := item.Head.Key.Offset + uint64(i)
+				if _, exists := membersByIndex[index]; exists {
+					errs = append(errs, fmt.Errorf("read dir: multiple instances of direntry index %v", index))
+					continue
+				}
+				membersByIndex[index] = entry
 			}
 		case btrfsitem.XATTR_ITEM_KEY:
 		default:
 			panic(fmt.Errorf("TODO: handle item type %v", item.Head.Key.ItemType))
 		}
 	}
-	return nil
+	fmt.Printf("%s%q\t[ino=%d\t",
+		prefix0, dirName, dirInode)
+	if dirInodeDatOK {
+		fmt.Printf("uid=%d\tgid=%d\tsize=%d]\n",
+			dirInodeDat.UID, dirInodeDat.GID, dirInodeDat.Size)
+	} else {
+		fmt.Printf("error=read dir: no inode data\n")
+	}
+	for i, index := range util.SortedMapKeys(membersByIndex) {
+		entry := membersByIndex[index]
+		namehash := btrfsitem.NameHash(entry.Name)
+		if other, ok := membersByNameHash[namehash]; ok {
+			if !reflect.DeepEqual(entry, other) {
+				errs = append(errs, fmt.Errorf("read dir: index=%d disagrees with crc32c(%q)=%#x",
+					index, entry.Name, namehash))
+			}
+			delete(membersByNameHash, namehash)
+		} else {
+			errs = append(errs, fmt.Errorf("read dir: no DIR_ITEM crc32c(%q)=%#x for DIR_INDEX index=%d",
+				entry.Name, namehash, index))
+		}
+		prefix := tT
+		if (i == len(membersByIndex)-1) && (len(membersByNameHash) == 0) && (len(errs) == 0) {
+			prefix = tL
+		}
+		printItem(fs, fsTree, prefix1+prefix, prefix1+tS, string(entry.Name), entry.Location)
+	}
+	for _, namehash := range util.SortedMapKeys(membersByNameHash) {
+		entry := membersByNameHash[namehash]
+		errs = append(errs, fmt.Errorf("read dir: no DIR_INDEX for DIR_ITEM crc32c(%q)=%#x",
+			entry.Name, namehash))
+		printItem(fs, fsTree, prefix1+tT, prefix1+tS, string(entry.Name), entry.Location)
+	}
+	for i, err := range errs {
+		prefix := tT
+		if i == len(errs)-1 {
+			prefix = tL
+		}
+		fmt.Printf("%s%s%s\n", prefix1, prefix, strings.ReplaceAll(err.Error(), "\n", prefix1+tS+"\n"))
+	}
+}
+
+func printItem(fs *btrfs.FS, fsTree btrfsvol.LogicalAddr, prefix0, prefix1, name string, location btrfs.Key) {
+	fmt.Printf("%s%q\t[location=%v]\n", prefix0, name, location)
 }
diff --git a/pkg/btrfs/btrfsitem/item_dir.go b/pkg/btrfs/btrfsitem/item_dir.go
index 253d257..14541bd 100644
--- a/pkg/btrfs/btrfsitem/item_dir.go
+++ b/pkg/btrfs/btrfsitem/item_dir.go
@@ -2,6 +2,7 @@ package btrfsitem
 
 import (
 	"fmt"
+	"hash/crc32"
 
 	"lukeshu.com/btrfs-tools/pkg/binstruct"
 	"lukeshu.com/btrfs-tools/pkg/btrfs/internal"
@@ -9,15 +10,19 @@ import (
 
 // key.objectid = inode of directory containing this entry
 // key.offset =
-//    for DIR_ITEM and XATTR_ITEM = crc32c(name)
+//    for DIR_ITEM and XATTR_ITEM = NameHash(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
+type DirEntries []DirEntry // DIR_ITEM=84 DIR_INDEX=96 XATTR_ITEM=24
 
-func (o *DirList) UnmarshalBinary(dat []byte) (int, error) {
+func NameHash(dat []byte) uint64 {
+	return uint64(^crc32.Update(1, crc32.MakeTable(crc32.Castagnoli), dat))
+}
+
+func (o *DirEntries) UnmarshalBinary(dat []byte) (int, error) {
 	*o = nil
 	n := 0
 	for n < len(dat) {
-		var ref Dir
+		var ref DirEntry
 		_n, err := binstruct.Unmarshal(dat, &ref)
 		n += _n
 		if err != nil {
@@ -28,7 +33,7 @@ func (o *DirList) UnmarshalBinary(dat []byte) (int, error) {
 	return n, nil
 }
 
-func (o DirList) MarshalBinary() ([]byte, error) {
+func (o DirEntries) MarshalBinary() ([]byte, error) {
 	var ret []byte
 	for _, ref := range o {
 		bs, err := binstruct.Marshal(ref)
@@ -40,7 +45,7 @@ func (o DirList) MarshalBinary() ([]byte, error) {
 	return ret, nil
 }
 
-type Dir struct {
+type DirEntry struct {
 	Location      internal.Key `bin:"off=0x0, siz=0x11"`
 	TransID       int64        `bin:"off=0x11, siz=8"`
 	DataLen       uint16       `bin:"off=0x19, siz=2"` // [ignored-when-writing]
@@ -51,7 +56,7 @@ type Dir struct {
 	Name          []byte `bin:"-"`
 }
 
-func (o *Dir) UnmarshalBinary(dat []byte) (int, error) {
+func (o *DirEntry) UnmarshalBinary(dat []byte) (int, error) {
 	n, err := binstruct.UnmarshalWithoutInterface(dat, o)
 	if err != nil {
 		return n, err
@@ -63,7 +68,7 @@ func (o *Dir) UnmarshalBinary(dat []byte) (int, error) {
 	return n, nil
 }
 
-func (o Dir) MarshalBinary() ([]byte, error) {
+func (o DirEntry) MarshalBinary() ([]byte, error) {
 	o.DataLen = uint16(len(o.Data))
 	o.NameLen = uint16(len(o.Name))
 	dat, err := binstruct.MarshalWithoutInterface(o)
diff --git a/pkg/btrfs/btrfsitem/items.txt b/pkg/btrfs/btrfsitem/items.txt
index dbcd260..a5f247f 100644
--- a/pkg/btrfs/btrfsitem/items.txt
+++ b/pkg/btrfs/btrfsitem/items.txt
@@ -2,8 +2,8 @@ BLOCK_GROUP_ITEM=192 BlockGroup
 CHUNK_ITEM=228 Chunk
 DEV_EXTENT=204 DevExtent
 DEV_ITEM=216 Dev
-DIR_INDEX=96 DirList
-DIR_ITEM=84 DirList
+DIR_INDEX=96 DirEntries
+DIR_ITEM=84 DirEntries
 EXTENT_CSUM=128 ExtentCSum
 EXTENT_DATA=108 FileExtent
 EXTENT_DATA_REF=178 ExtentDataRef
@@ -24,4 +24,4 @@ TREE_BLOCK_REF=176 Empty
 UNTYPED=0:FREE_SPACE_OBJECTID FreeSpaceHeader
 UUID_RECEIVED_SUBVOL=252 UUIDMap
 UUID_SUBVOL=251 UUIDMap
-XATTR_ITEM=24 DirList
+XATTR_ITEM=24 DirEntries
diff --git a/pkg/btrfs/btrfsitem/items_gen.go b/pkg/btrfs/btrfsitem/items_gen.go
index f0a4274..92e2523 100644
--- a/pkg/btrfs/btrfsitem/items_gen.go
+++ b/pkg/btrfs/btrfsitem/items_gen.go
@@ -43,8 +43,8 @@ var keytype2gotype = map[Type]reflect.Type{
 	CHUNK_ITEM_KEY:           reflect.TypeOf(Chunk{}),
 	DEV_EXTENT_KEY:           reflect.TypeOf(DevExtent{}),
 	DEV_ITEM_KEY:             reflect.TypeOf(Dev{}),
-	DIR_INDEX_KEY:            reflect.TypeOf(DirList{}),
-	DIR_ITEM_KEY:             reflect.TypeOf(DirList{}),
+	DIR_INDEX_KEY:            reflect.TypeOf(DirEntries{}),
+	DIR_ITEM_KEY:             reflect.TypeOf(DirEntries{}),
 	EXTENT_CSUM_KEY:          reflect.TypeOf(ExtentCSum{}),
 	EXTENT_DATA_KEY:          reflect.TypeOf(FileExtent{}),
 	EXTENT_DATA_REF_KEY:      reflect.TypeOf(ExtentDataRef{}),
@@ -64,7 +64,7 @@ var keytype2gotype = map[Type]reflect.Type{
 	TREE_BLOCK_REF_KEY:       reflect.TypeOf(Empty{}),
 	UUID_RECEIVED_SUBVOL_KEY: reflect.TypeOf(UUIDMap{}),
 	UUID_SUBVOL_KEY:          reflect.TypeOf(UUIDMap{}),
-	XATTR_ITEM_KEY:           reflect.TypeOf(DirList{}),
+	XATTR_ITEM_KEY:           reflect.TypeOf(DirEntries{}),
 }
 var untypedObjID2gotype = map[internal.ObjID]reflect.Type{
 	internal.FREE_SPACE_OBJECTID: reflect.TypeOf(FreeSpaceHeader{}),
@@ -75,7 +75,7 @@ func (Chunk) isItem()           {}
 func (Dev) isItem()             {}
 func (DevExtent) isItem()       {}
 func (DevStats) isItem()        {}
-func (DirList) isItem()         {}
+func (DirEntries) isItem()      {}
 func (Empty) isItem()           {}
 func (Extent) isItem()          {}
 func (ExtentCSum) isItem()      {}
diff --git a/pkg/btrfsmisc/print_tree.go b/pkg/btrfsmisc/print_tree.go
index 3a13504..76eb19c 100644
--- a/pkg/btrfsmisc/print_tree.go
+++ b/pkg/btrfsmisc/print_tree.go
@@ -64,7 +64,7 @@ func PrintTree(fs *btrfs.FS, root btrfsvol.LogicalAddr) error {
 				}
 			//case btrfsitem.INODE_EXTREF_KEY:
 			//	// TODO
-			case btrfsitem.DirList:
+			case btrfsitem.DirEntries:
 				for _, dir := range body {
 					fmt.Printf("\t\tlocation %v type %v\n",
 						FmtKey(dir.Location), dir.Type)