get some item iteration working

4 files changed, 163 insertions, 80 deletions

diff --git a/cmd/btrfs-dump-tree/main.go b/cmd/btrfs-dump-tree/main.go
index bdfd339..ccb7acb 100644
--- a/cmd/btrfs-dump-tree/main.go
+++ b/cmd/btrfs-dump-tree/main.go
@@ -2,6 +2,7 @@ package main
 
 import (
 	"fmt"
+"strings"
 	"os"
 
 	"lukeshu.com/btrfs-tools/pkg/btrfs"
@@ -64,7 +65,7 @@ func Main(imgfilename string) (err error) {
 	return nil
 }
 
-// printTree mimics btrfs-progs kernel-shared/print-tree.c:btrfs_print_tree()
+// printTree mimics btrfs-progs kernel-shared/print-tree.c:btrfs_print_tree() and  kernel-shared/print-tree.c:btrfs_print_leaf()
 func printTree(fs *btrfs.FS, root btrfs.LogicalAddr) {
 	node, err := fs.ReadNode(root)
 	if err != nil {
@@ -72,7 +73,18 @@ func printTree(fs *btrfs.FS, root btrfs.LogicalAddr) {
 		return
 	}
 	printHeaderInfo(node)
-	// TODO
+	switch node := node.(type) {
+	case *btrfs.InternalNode:
+		// TODO
+	case *btrfs.LeafNode:
+		for i, item := range node.Body {
+			fmt.Printf("\titem %d %s itemoff %d itemsize %d\n",
+				i,
+				fmtKey(item.Data.Key),
+				item.Data.DataOffset,
+				item.Data.DataSize)
+		}
+	}
 }
 
 // printHeaderInfo mimics btrfs-progs kernel-shared/print-tree.c:print_header_info()
@@ -103,3 +115,24 @@ func printHeaderInfo(node btrfs.Node) {
 		node.GetNodeHeader().Data.Flags,
 		node.GetNodeHeader().Data.BackrefRev)
 }
+
+// mimics print-tree.c:btrfs_print_key()
+func fmtKey(key btrfs.Key) string {
+	var out strings.Builder
+	fmt.Fprintf(&out, "key (%s %v", key.ObjectID.Format(key.ItemType), key.ItemType)
+	switch key.ItemType {
+	case btrfs.BTRFS_QGROUP_RELATION_KEY, btrfs.BTRFS_QGROUP_INFO_KEY, btrfs.BTRFS_QGROUP_LIMIT_KEY:
+		panic("not implemented")
+	case btrfs.BTRFS_UUID_KEY_SUBVOL, btrfs.BTRFS_UUID_KEY_RECEIVED_SUBVOL:
+		fmt.Fprintf(&out, " 0x%016x)", key.Offset)
+	case btrfs.BTRFS_ROOT_ITEM_KEY:
+		fmt.Fprintf(&out, " %v)", btrfs.ObjID(key.Offset))
+	default:
+		if key.Offset == btrfs.MaxUint64pp-1 {
+			fmt.Fprintf(&out, " -1)")
+		} else {
+			fmt.Fprintf(&out, " %d)", key.Offset)
+		}
+	}
+	return out.String()
+}
diff --git a/pkg/btrfs/types_item.go b/pkg/btrfs/types_item.go
index 624161e..3db4174 100644
--- a/pkg/btrfs/types_item.go
+++ b/pkg/btrfs/types_item.go
@@ -139,47 +139,47 @@ const (
 
 func (t ItemType) String() string {
 	names := map[ItemType]string{
-		BTRFS_INODE_ITEM_KEY:           "BTRFS_INODE_ITEM_KEY",
-		BTRFS_INODE_REF_KEY:            "BTRFS_INODE_REF_KEY",
-		BTRFS_INODE_EXTREF_KEY:         "BTRFS_INODE_EXTREF_KEY",
-		BTRFS_XATTR_ITEM_KEY:           "BTRFS_XATTR_ITEM_KEY",
-		BTRFS_VERITY_DESC_ITEM_KEY:     "BTRFS_VERITY_DESC_ITEM_KEY",
-		BTRFS_VERITY_MERKLE_ITEM_KEY:   "BTRFS_VERITY_MERKLE_ITEM_KEY",
-		BTRFS_ORPHAN_ITEM_KEY:          "BTRFS_ORPHAN_ITEM_KEY",
-		BTRFS_DIR_LOG_ITEM_KEY:         "BTRFS_DIR_LOG_ITEM_KEY",
-		BTRFS_DIR_LOG_INDEX_KEY:        "BTRFS_DIR_LOG_INDEX_KEY",
-		BTRFS_DIR_ITEM_KEY:             "BTRFS_DIR_ITEM_KEY",
-		BTRFS_DIR_INDEX_KEY:            "BTRFS_DIR_INDEX_KEY",
-		BTRFS_EXTENT_DATA_KEY:          "BTRFS_EXTENT_DATA_KEY",
-		BTRFS_CSUM_ITEM_KEY:            "BTRFS_CSUM_ITEM_KEY",
-		BTRFS_EXTENT_CSUM_KEY:          "BTRFS_EXTENT_CSUM_KEY",
-		BTRFS_ROOT_ITEM_KEY:            "BTRFS_ROOT_ITEM_KEY",
-		BTRFS_ROOT_BACKREF_KEY:         "BTRFS_ROOT_BACKREF_KEY",
-		BTRFS_ROOT_REF_KEY:             "BTRFS_ROOT_REF_KEY",
-		BTRFS_EXTENT_ITEM_KEY:          "BTRFS_EXTENT_ITEM_KEY",
-		BTRFS_METADATA_ITEM_KEY:        "BTRFS_METADATA_ITEM_KEY",
-		BTRFS_TREE_BLOCK_REF_KEY:       "BTRFS_TREE_BLOCK_REF_KEY",
-		BTRFS_EXTENT_DATA_REF_KEY:      "BTRFS_EXTENT_DATA_REF_KEY",
-		BTRFS_EXTENT_REF_V0_KEY:        "BTRFS_EXTENT_REF_V0_KEY",
-		BTRFS_SHARED_BLOCK_REF_KEY:     "BTRFS_SHARED_BLOCK_REF_KEY",
-		BTRFS_SHARED_DATA_REF_KEY:      "BTRFS_SHARED_DATA_REF_KEY",
-		BTRFS_BLOCK_GROUP_ITEM_KEY:     "BTRFS_BLOCK_GROUP_ITEM_KEY",
-		BTRFS_FREE_SPACE_INFO_KEY:      "BTRFS_FREE_SPACE_INFO_KEY",
-		BTRFS_FREE_SPACE_EXTENT_KEY:    "BTRFS_FREE_SPACE_EXTENT_KEY",
-		BTRFS_FREE_SPACE_BITMAP_KEY:    "BTRFS_FREE_SPACE_BITMAP_KEY",
-		BTRFS_DEV_EXTENT_KEY:           "BTRFS_DEV_EXTENT_KEY",
-		BTRFS_DEV_ITEM_KEY:             "BTRFS_DEV_ITEM_KEY",
-		BTRFS_CHUNK_ITEM_KEY:           "BTRFS_CHUNK_ITEM_KEY",
-		BTRFS_QGROUP_STATUS_KEY:        "BTRFS_QGROUP_STATUS_KEY",
-		BTRFS_QGROUP_INFO_KEY:          "BTRFS_QGROUP_INFO_KEY",
-		BTRFS_QGROUP_LIMIT_KEY:         "BTRFS_QGROUP_LIMIT_KEY",
-		BTRFS_QGROUP_RELATION_KEY:      "BTRFS_QGROUP_RELATION_KEY",
-		BTRFS_TEMPORARY_ITEM_KEY:       "BTRFS_TEMPORARY_ITEM_KEY",
-		BTRFS_PERSISTENT_ITEM_KEY:      "BTRFS_PERSISTENT_ITEM_KEY",
-		BTRFS_DEV_REPLACE_KEY:          "BTRFS_DEV_REPLACE_KEY",
-		BTRFS_UUID_KEY_SUBVOL:          "BTRFS_UUID_KEY_SUBVOL",
-		BTRFS_UUID_KEY_RECEIVED_SUBVOL: "BTRFS_UUID_KEY_RECEIVED_SUBVOL",
-		BTRFS_STRING_ITEM_KEY:          "BTRFS_STRING_ITEM_KEY",
+		BTRFS_INODE_ITEM_KEY:           "INODE_ITEM",
+		BTRFS_INODE_REF_KEY:            "INODE_REF",
+		BTRFS_INODE_EXTREF_KEY:         "INODE_EXTREF",
+		BTRFS_XATTR_ITEM_KEY:           "XATTR_ITEM",
+		BTRFS_VERITY_DESC_ITEM_KEY:     "VERITY_DESC_ITEM",
+		BTRFS_VERITY_MERKLE_ITEM_KEY:   "VERITY_MERKLE_ITEM",
+		BTRFS_ORPHAN_ITEM_KEY:          "ORPHAN_ITEM",
+		BTRFS_DIR_LOG_ITEM_KEY:         "DIR_LOG_ITEM",
+		BTRFS_DIR_LOG_INDEX_KEY:        "DIR_LOG_INDEX",
+		BTRFS_DIR_ITEM_KEY:             "DIR_ITEM",
+		BTRFS_DIR_INDEX_KEY:            "DIR_INDEX",
+		BTRFS_EXTENT_DATA_KEY:          "EXTENT_DATA",
+		BTRFS_CSUM_ITEM_KEY:            "CSUM_ITEM",
+		BTRFS_EXTENT_CSUM_KEY:          "EXTENT_CSUM",
+		BTRFS_ROOT_ITEM_KEY:            "ROOT_ITEM",
+		BTRFS_ROOT_BACKREF_KEY:         "ROOT_BACKREF",
+		BTRFS_ROOT_REF_KEY:             "ROOT_REF",
+		BTRFS_EXTENT_ITEM_KEY:          "EXTENT_ITEM",
+		BTRFS_METADATA_ITEM_KEY:        "METADATA_ITEM",
+		BTRFS_TREE_BLOCK_REF_KEY:       "TREE_BLOCK_REF",
+		BTRFS_EXTENT_DATA_REF_KEY:      "EXTENT_DATA_REF",
+		BTRFS_EXTENT_REF_V0_KEY:        "EXTENT_REF_V0",
+		BTRFS_SHARED_BLOCK_REF_KEY:     "SHARED_BLOCK_REF",
+		BTRFS_SHARED_DATA_REF_KEY:      "SHARED_DATA_REF",
+		BTRFS_BLOCK_GROUP_ITEM_KEY:     "BLOCK_GROUP_ITEM",
+		BTRFS_FREE_SPACE_INFO_KEY:      "FREE_SPACE_INFO",
+		BTRFS_FREE_SPACE_EXTENT_KEY:    "FREE_SPACE_EXTENT",
+		BTRFS_FREE_SPACE_BITMAP_KEY:    "FREE_SPACE_BITMAP",
+		BTRFS_DEV_EXTENT_KEY:           "DEV_EXTENT",
+		BTRFS_DEV_ITEM_KEY:             "DEV_ITEM",
+		BTRFS_CHUNK_ITEM_KEY:           "CHUNK_ITEM",
+		BTRFS_QGROUP_STATUS_KEY:        "QGROUP_STATUS",
+		BTRFS_QGROUP_INFO_KEY:          "QGROUP_INFO",
+		BTRFS_QGROUP_LIMIT_KEY:         "QGROUP_LIMIT",
+		BTRFS_QGROUP_RELATION_KEY:      "QGROUP_RELATION",
+		BTRFS_TEMPORARY_ITEM_KEY:       "TEMPORARY_ITEM",
+		BTRFS_PERSISTENT_ITEM_KEY:      "PERSISTENT_ITEM",
+		BTRFS_DEV_REPLACE_KEY:          "DEV_REPLACE",
+		BTRFS_UUID_KEY_SUBVOL:          "UUID_KEY_SUBVOL",
+		BTRFS_UUID_KEY_RECEIVED_SUBVOL: "UUID_KEY_RECEIVED_SUBVOL",
+		BTRFS_STRING_ITEM_KEY:          "STRING_ITEM",
 	}
 	if name, ok := names[t]; ok {
 		return name
diff --git a/pkg/btrfs/types_objid.go b/pkg/btrfs/types_objid.go
index 6213167..b08cf3a 100644
--- a/pkg/btrfs/types_objid.go
+++ b/pkg/btrfs/types_objid.go
@@ -6,7 +6,7 @@ import (
 
 type ObjID uint64
 
-const maxUint64pp = 0x1_0000_0000
+const MaxUint64pp = 0x1_0000_0000
 
 const (
 	// The IDs of the various trees
@@ -26,21 +26,21 @@ const (
 	BTRFS_DEV_STATS_OBJECTID = ObjID(0) // device stats in the device tree
 
 	// ???
-	BTRFS_BALANCE_OBJECTID         = ObjID(maxUint64pp - 4) // for storing balance parameters in the root tree
-	BTRFS_ORPHAN_OBJECTID          = ObjID(maxUint64pp - 5) // orphan objectid for tracking unlinked/truncated files
-	BTRFS_TREE_LOG_OBJECTID        = ObjID(maxUint64pp - 6) // does write ahead logging to speed up fsyncs
-	BTRFS_TREE_LOG_FIXUP_OBJECTID  = ObjID(maxUint64pp - 7)
-	BTRFS_TREE_RELOC_OBJECTID      = ObjID(maxUint64pp - 8) // space balancing
-	BTRFS_DATA_RELOC_TREE_OBJECTID = ObjID(maxUint64pp - 9)
-	BTRFS_EXTENT_CSUM_OBJECTID     = ObjID(maxUint64pp - 10) // extent checksums all have this objectid
-	BTRFS_FREE_SPACE_OBJECTID      = ObjID(maxUint64pp - 11) // For storing free space cache
-	BTRFS_FREE_INO_OBJECTID        = ObjID(maxUint64pp - 12) // stores the inode number for the free-ino cache
-
-	BTRFS_MULTIPLE_OBJECTIDS = ObjID(maxUint64pp - 255) // dummy objectid represents multiple objectids
+	BTRFS_BALANCE_OBJECTID         = ObjID(MaxUint64pp - 4) // for storing balance parameters in the root tree
+	BTRFS_ORPHAN_OBJECTID          = ObjID(MaxUint64pp - 5) // orphan objectid for tracking unlinked/truncated files
+	BTRFS_TREE_LOG_OBJECTID        = ObjID(MaxUint64pp - 6) // does write ahead logging to speed up fsyncs
+	BTRFS_TREE_LOG_FIXUP_OBJECTID  = ObjID(MaxUint64pp - 7)
+	BTRFS_TREE_RELOC_OBJECTID      = ObjID(MaxUint64pp - 8) // space balancing
+	BTRFS_DATA_RELOC_TREE_OBJECTID = ObjID(MaxUint64pp - 9)
+	BTRFS_EXTENT_CSUM_OBJECTID     = ObjID(MaxUint64pp - 10) // extent checksums all have this objectid
+	BTRFS_FREE_SPACE_OBJECTID      = ObjID(MaxUint64pp - 11) // For storing free space cache
+	BTRFS_FREE_INO_OBJECTID        = ObjID(MaxUint64pp - 12) // stores the inode number for the free-ino cache
+
+	BTRFS_MULTIPLE_OBJECTIDS = ObjID(MaxUint64pp - 255) // dummy objectid represents multiple objectids
 
 	// All files have objectids in this range.
 	BTRFS_FIRST_FREE_OBJECTID = ObjID(256)
-	BTRFS_LAST_FREE_OBJECTID  = ObjID(maxUint64pp - 256)
+	BTRFS_LAST_FREE_OBJECTID  = ObjID(MaxUint64pp - 256)
 
 	BTRFS_FIRST_CHUNK_TREE_OBJECTID = ObjID(256)
 
@@ -51,8 +51,25 @@ const (
 	BTRFS_EMPTY_SUBVOL_DIR_OBJECTID = ObjID(2)
 )
 
-func (id ObjID) String() string {
-	if id > BTRFS_LAST_FREE_OBJECTID {
+func (id ObjID) Format(typ ItemType) string {
+	switch typ {
+	case BTRFS_PERSISTENT_ITEM_KEY:
+		names := map[ObjID]string{
+			BTRFS_DEV_STATS_OBJECTID: "DEV_STATS",
+		}
+		if name, ok := names[id]; ok {
+			return name
+		}
+		return fmt.Sprintf("%d", int64(id))
+	case BTRFS_DEV_EXTENT_KEY:
+		return fmt.Sprintf("%d", int64(id))
+	case BTRFS_QGROUP_RELATION_KEY:
+		return fmt.Sprintf("%d/%d",
+			uint64(id)>>48,
+			uint64(id)&((1<<48)-1))
+	case BTRFS_UUID_KEY_SUBVOL, BTRFS_UUID_KEY_RECEIVED_SUBVOL:
+		return fmt.Sprintf("0x%016x", uint64(id))
+	case BTRFS_DEV_ITEM_KEY:
 		names := map[ObjID]string{
 			BTRFS_BALANCE_OBJECTID:         "BALANCE",
 			BTRFS_ORPHAN_OBJECTID:          "ORPHAN",
@@ -64,33 +81,66 @@ func (id ObjID) String() string {
 			BTRFS_FREE_SPACE_OBJECTID:      "FREE_SPACE",
 			BTRFS_FREE_INO_OBJECTID:        "FREE_INO",
 			BTRFS_MULTIPLE_OBJECTIDS:       "MULTIPLE",
+
+			BTRFS_DEV_ITEMS_OBJECTID: "DEV_ITEMS",
 		}
 		if name, ok := names[id]; ok {
 			return name
 		}
 		return fmt.Sprintf("%d", int64(id))
+	case BTRFS_CHUNK_ITEM_KEY:
+		names := map[ObjID]string{
+			BTRFS_BALANCE_OBJECTID:         "BALANCE",
+			BTRFS_ORPHAN_OBJECTID:          "ORPHAN",
+			BTRFS_TREE_LOG_OBJECTID:        "TREE_LOG",
+			BTRFS_TREE_LOG_FIXUP_OBJECTID:  "TREE_LOG_FIXUP",
+			BTRFS_TREE_RELOC_OBJECTID:      "TREE_RELOC",
+			BTRFS_DATA_RELOC_TREE_OBJECTID: "DATA_RELOC_TREE",
+			BTRFS_EXTENT_CSUM_OBJECTID:     "EXTENT_CSUM",
+			BTRFS_FREE_SPACE_OBJECTID:      "FREE_SPACE",
+			BTRFS_FREE_INO_OBJECTID:        "FREE_INO",
+			BTRFS_MULTIPLE_OBJECTIDS:       "MULTIPLE",
+
+			BTRFS_FIRST_CHUNK_TREE_OBJECTID: "FIRST_CHUNK_TREE",
+		}
+		if name, ok := names[id]; ok {
+			return name
+		}
+		return fmt.Sprintf("%d", int64(id))
+	default:
+		names := map[ObjID]string{
+			BTRFS_BALANCE_OBJECTID:         "BALANCE",
+			BTRFS_ORPHAN_OBJECTID:          "ORPHAN",
+			BTRFS_TREE_LOG_OBJECTID:        "TREE_LOG",
+			BTRFS_TREE_LOG_FIXUP_OBJECTID:  "TREE_LOG_FIXUP",
+			BTRFS_TREE_RELOC_OBJECTID:      "TREE_RELOC",
+			BTRFS_DATA_RELOC_TREE_OBJECTID: "DATA_RELOC_TREE",
+			BTRFS_EXTENT_CSUM_OBJECTID:     "EXTENT_CSUM",
+			BTRFS_FREE_SPACE_OBJECTID:      "FREE_SPACE",
+			BTRFS_FREE_INO_OBJECTID:        "FREE_INO",
+			BTRFS_MULTIPLE_OBJECTIDS:       "MULTIPLE",
+
+			BTRFS_ROOT_TREE_OBJECTID:        "ROOT_TREE",
+			BTRFS_EXTENT_TREE_OBJECTID:      "EXTENT_TREE",
+			BTRFS_CHUNK_TREE_OBJECTID:       "CHUNK_TREE",
+			BTRFS_DEV_TREE_OBJECTID:         "DEV_TREE",
+			BTRFS_FS_TREE_OBJECTID:          "FS_TREE",
+			BTRFS_ROOT_TREE_DIR_OBJECTID:    "ROOT_TREE_DIR",
+			BTRFS_CSUM_TREE_OBJECTID:        "CSUM_TREE",
+			BTRFS_QUOTA_TREE_OBJECTID:       "QUOTA_TREE",
+			BTRFS_UUID_TREE_OBJECTID:        "UUID_TREE",
+			BTRFS_FREE_SPACE_TREE_OBJECTID:  "FREE_SPACE_TREE",
+			BTRFS_BLOCK_GROUP_TREE_OBJECTID: "BLOCK_GROUP_TREE",
+		}
+		if names != nil {
+			if name, ok := names[id]; ok {
+				return name
+			}
+		}
+		return fmt.Sprintf("%d", int64(id))
 	}
-	return fmt.Sprintf("%d", id)
 }
 
-type TreeObjID ObjID
-
-func (id TreeObjID) String() string {
-	names := map[ObjID]string{
-		BTRFS_ROOT_TREE_OBJECTID:        "ROOT_TREE",
-		BTRFS_EXTENT_TREE_OBJECTID:      "EXTENT_TREE",
-		BTRFS_CHUNK_TREE_OBJECTID:       "CHUNK_TREE",
-		BTRFS_DEV_TREE_OBJECTID:         "DEV_TREE",
-		BTRFS_FS_TREE_OBJECTID:          "FS_TREE",
-		BTRFS_ROOT_TREE_DIR_OBJECTID:    "ROOT_TREE_DIR",
-		BTRFS_CSUM_TREE_OBJECTID:        "CSUM_TREE",
-		BTRFS_QUOTA_TREE_OBJECTID:       "QUOTA_TREE",
-		BTRFS_UUID_TREE_OBJECTID:        "UUID_TREE",
-		BTRFS_FREE_SPACE_TREE_OBJECTID:  "FREE_SPACE_TREE",
-		BTRFS_BLOCK_GROUP_TREE_OBJECTID: "BLOCK_GROUP_TREE",
-	}
-	if name, ok := names[ObjID(id)]; ok {
-		return name
-	}
-	return ObjID(id).String()
+func (id ObjID) String() string {
+	return id.Format(BTRFS_STRING_ITEM_KEY)
 }
diff --git a/pkg/btrfs/types_structs.go b/pkg/btrfs/types_structs.go
index 5063d86..f96c20a 100644
--- a/pkg/btrfs/types_structs.go
+++ b/pkg/btrfs/types_structs.go
@@ -207,7 +207,7 @@ type NodeHeader struct {
 	BackrefRev    uint8       `bin:"off=3f, siz=1"`
 	ChunkTreeUUID UUID        `bin:"off=40, siz=10"` // Chunk tree UUID
 	Generation    Generation  `bin:"off=50, siz=8"`  // Generation
-	Owner         TreeObjID   `bin:"off=58, siz=8"`  // The ID of the tree that contains this node
+	Owner         ObjID       `bin:"off=58, siz=8"`  // The ID of the tree that contains this node
 	NumItems      uint32      `bin:"off=60, siz=4"`  // Number of items
 	Level         uint8       `bin:"off=64, siz=1"`  // Level (0 for leaf nodes)
 	binstruct.End `bin:"off=65"`