Remove fstree code from rdsquashfs

Use the directory reader from libsquashfs instead.

Signed-off-by: David Oberhollenzer <david.oberhollenzer@sigma-star.at>

10 files changed, 501 insertions, 293 deletions

diff --git a/unpack/Makemodule.am b/unpack/Makemodule.am
index 964cc05..0dbd07f 100644
--- a/unpack/Makemodule.am
+++ b/unpack/Makemodule.am
@@ -1,7 +1,7 @@
 rdsquashfs_SOURCES = unpack/rdsquashfs.c unpack/rdsquashfs.h
 rdsquashfs_SOURCES += unpack/list_files.c unpack/options.c
 rdsquashfs_SOURCES += unpack/restore_fstree.c unpack/describe.c
-rdsquashfs_SOURCES += unpack/fill_files.c unpack/optimize_unpack_order.c
+rdsquashfs_SOURCES += unpack/fill_files.c unpack/dump_xattrs.c
 rdsquashfs_LDADD = libsqfshelper.a libsquashfs.la libfstree.a libutil.la
 
 bin_PROGRAMS += rdsquashfs
diff --git a/unpack/describe.c b/unpack/describe.c
index c3166c4..336eb4d 100644
--- a/unpack/describe.c
+++ b/unpack/describe.c
@@ -6,9 +6,9 @@
  */
 #include "rdsquashfs.h"
 
-static int print_name(tree_node_t *n)
+static int print_name(const sqfs_tree_node_t *n)
 {
-	char *start, *ptr, *name = fstree_get_path(n);
+	char *start, *ptr, *name = sqfs_tree_node_get_path(n);
 	int ret;
 
 	if (name == NULL) {
@@ -48,12 +48,13 @@ static int print_name(tree_node_t *n)
 	return 0;
 }
 
-static void print_perm(tree_node_t *n)
+static void print_perm(const sqfs_tree_node_t *n)
 {
-	printf(" 0%o %d %d", n->mode & (~S_IFMT), n->uid, n->gid);
+	printf(" 0%o %d %d", n->inode->base.mode & (~S_IFMT), n->uid, n->gid);
 }
 
-static int print_simple(const char *type, tree_node_t *n, const char *extra)
+static int print_simple(const char *type, const sqfs_tree_node_t *n,
+			const char *extra)
 {
 	printf("%s ", type);
 	if (print_name(n))
@@ -65,15 +66,15 @@ static int print_simple(const char *type, tree_node_t *n, const char *extra)
 	return 0;
 }
 
-int describe_tree(tree_node_t *root, const char *unpack_root)
+int describe_tree(const sqfs_tree_node_t *root, const char *unpack_root)
 {
-	tree_node_t *n;
+	const sqfs_tree_node_t *n;
 
-	switch (root->mode & S_IFMT) {
+	switch (root->inode->base.mode & S_IFMT) {
 	case S_IFSOCK:
 		return print_simple("sock", root, NULL);
 	case S_IFLNK:
-		return print_simple("slink", root, root->data.slink_target);
+		return print_simple("slink", root, root->inode->slink_target);
 	case S_IFIFO:
 		return print_simple("pipe", root, NULL);
 	case S_IFREG:
@@ -92,8 +93,18 @@ int describe_tree(tree_node_t *root, const char *unpack_root)
 	case S_IFCHR:
 	case S_IFBLK: {
 		char buffer[32];
-		sprintf(buffer, "%c %d %d", S_ISCHR(root->mode) ? 'c' : 'b',
-		       major(root->data.devno), minor(root->data.devno));
+		uint32_t devno;
+
+		if (root->inode->base.type == SQFS_INODE_EXT_BDEV ||
+		    root->inode->base.type == SQFS_INODE_EXT_CDEV) {
+			devno = root->inode->data.dev_ext.devno;
+		} else {
+			devno = root->inode->data.dev.devno;
+		}
+
+		sprintf(buffer, "%c %d %d",
+			S_ISCHR(root->inode->base.mode) ? 'c' : 'b',
+			major(devno), minor(devno));
 		return print_simple("nod", root, buffer);
 	}
 	case S_IFDIR:
@@ -102,7 +113,7 @@ int describe_tree(tree_node_t *root, const char *unpack_root)
 				return -1;
 		}
 
-		for (n = root->data.dir->children; n != NULL; n = n->next) {
+		for (n = root->children; n != NULL; n = n->next) {
 			if (describe_tree(n, unpack_root))
 				return -1;
 		}
diff --git a/unpack/dump_xattrs.c b/unpack/dump_xattrs.c
new file mode 100644
index 0000000..c619767
--- /dev/null
+++ b/unpack/dump_xattrs.c
@@ -0,0 +1,73 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * dump_xattrs.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "rdsquashfs.h"
+
+int dump_xattrs(sqfs_xattr_reader_t *xattr, const sqfs_inode_generic_t *inode)
+{
+	sqfs_xattr_value_t *value;
+	sqfs_xattr_entry_t *key;
+	sqfs_xattr_id_t desc;
+	uint32_t index;
+	size_t i;
+
+	if (xattr == NULL)
+		return 0;
+
+	switch (inode->base.type) {
+	case SQFS_INODE_EXT_DIR:
+		index = inode->data.dir_ext.xattr_idx;
+		break;
+	case SQFS_INODE_EXT_FILE:
+		index = inode->data.file_ext.xattr_idx;
+		break;
+	case SQFS_INODE_EXT_SLINK:
+		index = inode->data.slink_ext.xattr_idx;
+		break;
+	case SQFS_INODE_EXT_BDEV:
+	case SQFS_INODE_EXT_CDEV:
+		index = inode->data.dev_ext.xattr_idx;
+		break;
+	case SQFS_INODE_EXT_FIFO:
+	case SQFS_INODE_EXT_SOCKET:
+		index = inode->data.ipc_ext.xattr_idx;
+		break;
+	default:
+		return 0;
+	}
+
+	if (index == 0xFFFFFFFF)
+		return 0;
+
+	if (sqfs_xattr_reader_get_desc(xattr, index, &desc)) {
+		fputs("Error resolving xattr index\n", stderr);
+		return -1;
+	}
+
+	if (sqfs_xattr_reader_seek_kv(xattr, &desc)) {
+		fputs("Error locating xattr key-value pairs\n", stderr);
+		return -1;
+	}
+
+	for (i = 0; i < desc.count; ++i) {
+		if (sqfs_xattr_reader_read_key(xattr, &key)) {
+			fputs("Error reading xattr key\n", stderr);
+			return -1;
+		}
+
+		if (sqfs_xattr_reader_read_value(xattr, key, &value)) {
+			fputs("Error reading xattr value\n", stderr);
+			free(key);
+			return -1;
+		}
+
+		printf("%s=%s\n", key->key, value->value);
+		free(key);
+		free(value);
+	}
+
+	return 0;
+}
diff --git a/unpack/fill_files.c b/unpack/fill_files.c
index df6ca7e..de0b676 100644
--- a/unpack/fill_files.c
+++ b/unpack/fill_files.c
@@ -7,27 +7,173 @@
 #include "config.h"
 #include "rdsquashfs.h"
 
-static int fill_files(data_reader_t *data, file_info_t *list, int flags)
+static struct file_ent {
+	char *path;
+	const sqfs_inode_generic_t *inode;
+} *files = NULL;
+
+static size_t num_files = 0, max_files = 0;
+static size_t block_size = 0;
+
+static uint32_t get_frag_idx(const sqfs_inode_generic_t *inode)
 {
-	file_info_t *fi;
-	int fd;
+	if (inode->base.type == SQFS_INODE_EXT_FILE)
+		return inode->data.file_ext.fragment_idx;
+
+	return inode->data.file.fragment_index;
+}
+
+static uint32_t get_frag_off(const sqfs_inode_generic_t *inode)
+{
+	if (inode->base.type == SQFS_INODE_EXT_FILE)
+		return inode->data.file_ext.fragment_offset;
+
+	return inode->data.file.fragment_offset;
+}
+
+static uint64_t get_size(const sqfs_inode_generic_t *inode)
+{
+	if (inode->base.type == SQFS_INODE_EXT_FILE)
+		return inode->data.file_ext.file_size;
+
+	return inode->data.file.file_size;
+}
+
+static uint64_t get_start(const sqfs_inode_generic_t *inode)
+{
+	if (inode->base.type == SQFS_INODE_EXT_FILE)
+		return inode->data.file_ext.blocks_start;
+
+	return inode->data.file.blocks_start;
+}
+
+static bool has_fragment(const struct file_ent *ent)
+{
+	if (get_size(ent->inode) % block_size == 0)
+		return false;
+
+	return get_frag_off(ent->inode) < block_size &&
+		(get_frag_idx(ent->inode) != 0xFFFFFFFF);
+}
+
+static int compare_files(const void *l, const void *r)
+{
+	const struct file_ent *lhs = l, *rhs = r;
+
+	/* Files with fragments come first, ordered by ID.
+	   In case of tie, files without data blocks come first,
+	   and the others are ordered by start block. */
+	if (has_fragment(lhs)) {
+		if (!(has_fragment(rhs)))
+			return -1;
+
+		if (get_frag_idx(lhs->inode) < get_frag_idx(rhs->inode))
+			return -1;
+
+		if (get_frag_idx(lhs->inode) > get_frag_idx(rhs->inode))
+			return 1;
+
+		if (get_size(lhs->inode) < block_size)
+			return (get_size(rhs->inode) < block_size) ? 0 : -1;
+
+		if (get_size(rhs->inode) < block_size)
+			return 1;
+
+		goto order_by_start;
+	}
+
+	if (has_fragment(rhs))
+		return 1;
 
-	for (fi = list; fi != NULL; fi = fi->next) {
-		if (fi->input_file == NULL)
-			continue;
+	/* order the rest by start block */
+order_by_start:
+	return get_start(lhs->inode) < get_start(rhs->inode) ? -1 :
+		get_start(lhs->inode) > get_start(rhs->inode) ? 1 : 0;
+}
+
+static int add_file(const sqfs_tree_node_t *node)
+{
+	size_t new_sz;
+	char *path;
+	void *new;
+
+	if (num_files == max_files) {
+		new_sz = max_files ? max_files * 2 : 256;
+		new = realloc(files, sizeof(files[0]) * new_sz);
+
+		if (new == NULL) {
+			perror("expanding file list");
+			return -1;
+		}
+
+		files = new;
+		max_files = new_sz;
+	}
 
-		fd = open(fi->input_file, O_WRONLY);
+	path = sqfs_tree_node_get_path(node);
+	if (path == NULL) {
+		perror("assembling file path");
+		return -1;
+	}
+
+	if (canonicalize_name(path)) {
+		fprintf(stderr, "Invalid file path '%s'\n", path);
+		free(path);
+		return -1;
+	}
+
+	files[num_files].path = path;
+	files[num_files].inode = node->inode;
+	num_files++;
+	return 0;
+}
+
+static void clear_file_list(void)
+{
+	size_t i;
+
+	for (i = 0; i < num_files; ++i)
+		free(files[i].path);
+
+	free(files);
+	files = NULL;
+	num_files = 0;
+	max_files = 0;
+}
+
+static int gen_file_list_dfs(const sqfs_tree_node_t *n)
+{
+	if (S_ISREG(n->inode->base.mode))
+		return add_file(n);
+
+	if (S_ISDIR(n->inode->base.mode)) {
+		for (n = n->children; n != NULL; n = n->next) {
+			if (gen_file_list_dfs(n))
+				return -1;
+		}
+	}
+
+	return 0;
+}
+
+static int fill_files(data_reader_t *data, int flags)
+{
+	size_t i;
+	int fd;
+
+	for (i = 0; i < num_files; ++i) {
+		fd = open(files[i].path, O_WRONLY);
 		if (fd < 0) {
 			fprintf(stderr, "unpacking %s: %s\n",
-				fi->input_file, strerror(errno));
+				files[i].path, strerror(errno));
 			return -1;
 		}
 
 		if (!(flags & UNPACK_QUIET))
-			printf("unpacking %s\n", fi->input_file);
+			printf("unpacking %s\n", files[i].path);
 
-		if (data_reader_dump_file(data, fi, fd,
-					  (flags & UNPACK_NO_SPARSE) == 0)) {
+		if (data_reader_dump(data, files[i].inode, fd,
+				     (flags & UNPACK_NO_SPARSE) == 0)) {
 			close(fd);
 			return -1;
 		}
@@ -38,17 +184,21 @@ static int fill_files(data_reader_t *data, file_info_t *list, int flags)
 	return 0;
 }
 
-int fill_unpacked_files(fstree_t *fs, data_reader_t *data, int flags)
+int fill_unpacked_files(size_t blk_sz, const sqfs_tree_node_t *root,
+			data_reader_t *data, int flags)
 {
-	file_info_t *list, *it;
-	int status = 0;
+	int status;
 
-	list = optimize_unpack_order(fs);
+	block_size = blk_sz;
 
-	status = fill_files(data, list, flags);
+	if (gen_file_list_dfs(root)) {
+		clear_file_list();
+		return -1;
+	}
 
-	for (it = list; it != NULL; it = it->next)
-		free(it->input_file);
+	qsort(files, num_files, sizeof(files[0]), compare_files);
 
+	status = fill_files(data, flags);
+	clear_file_list();
 	return status;
 }
diff --git a/unpack/list_files.c b/unpack/list_files.c
index 857657b..11e18cb 100644
--- a/unpack/list_files.c
+++ b/unpack/list_files.c
@@ -81,23 +81,40 @@ static void print_size(uint64_t size, char *buffer)
 	}
 }
 
-static void print_node_size(tree_node_t *n, char *buffer)
+static void print_node_size(const sqfs_tree_node_t *n, char *buffer)
 {
-	switch (n->mode & S_IFMT) {
+	switch (n->inode->base.mode & S_IFMT) {
 	case S_IFLNK:
-		print_size(strlen(n->data.slink_target), buffer);
+		print_size(strlen(n->inode->slink_target), buffer);
 		break;
 	case S_IFREG:
-		print_size(n->data.file->size, buffer);
+		if (n->inode->base.type == SQFS_INODE_EXT_FILE) {
+			print_size(n->inode->data.file_ext.file_size, buffer);
+		} else {
+			print_size(n->inode->data.file.file_size, buffer);
+		}
 		break;
 	case S_IFDIR:
-		print_size(n->data.dir->size, buffer);
+		if (n->inode->base.type == SQFS_INODE_EXT_DIR) {
+			print_size(n->inode->data.dir_ext.size, buffer);
+		} else {
+			print_size(n->inode->data.dir.size, buffer);
+		}
 		break;
 	case S_IFBLK:
-	case S_IFCHR:
-		sprintf(buffer, "%u:%u", major(n->data.devno),
-			minor(n->data.devno));
+	case S_IFCHR: {
+		uint32_t devno;
+
+		if (n->inode->base.type == SQFS_INODE_EXT_BDEV ||
+		    n->inode->base.type == SQFS_INODE_EXT_CDEV) {
+			devno = n->inode->data.dev_ext.devno;
+		} else {
+			devno = n->inode->data.dev.devno;
+		}
+
+		sprintf(buffer, "%u:%u", major(devno), minor(devno));
 		break;
+	}
 	default:
 		buffer[0] = '0';
 		buffer[1] = '\0';
@@ -105,14 +122,14 @@ static void print_node_size(tree_node_t *n, char *buffer)
 	}
 }
 
-void list_files(tree_node_t *node)
+void list_files(const sqfs_tree_node_t *node)
 {
 	int i, max_uid_chars = 0, max_gid_chars = 0, max_sz_chars = 0;
 	char modestr[12], sizestr[32];
-	tree_node_t *n;
+	const sqfs_tree_node_t *n;
 
-	if (S_ISDIR(node->mode)) {
-		for (n = node->data.dir->children; n != NULL; n = n->next) {
+	if (S_ISDIR(node->inode->base.mode)) {
+		for (n = node->children; n != NULL; n = n->next) {
 			i = count_int_chars(n->uid);
 			max_uid_chars = i > max_uid_chars ? i : max_uid_chars;
 
@@ -124,8 +141,8 @@ void list_files(tree_node_t *node)
 			max_sz_chars = i > max_sz_chars ? i : max_sz_chars;
 		}
 
-		for (n = node->data.dir->children; n != NULL; n = n->next) {
-			mode_to_str(n->mode, modestr);
+		for (n = node->children; n != NULL; n = n->next) {
+			mode_to_str(n->inode->base.mode, modestr);
 			print_node_size(n, sizestr);
 
 			printf("%s %*u/%-*u %*s %s", modestr,
@@ -134,21 +151,21 @@ void list_files(tree_node_t *node)
 			       max_sz_chars, sizestr,
 			       n->name);
 
-			if (S_ISLNK(n->mode)) {
-				printf(" -> %s\n", n->data.slink_target);
+			if (S_ISLNK(n->inode->base.mode)) {
+				printf(" -> %s\n", n->inode->slink_target);
 			} else {
 				fputc('\n', stdout);
 			}
 		}
 	} else {
-		mode_to_str(node->mode, modestr);
+		mode_to_str(node->inode->base.mode, modestr);
 		print_node_size(node, sizestr);
 
 		printf("%s %u/%u %s %s", modestr,
 		       node->uid, node->gid, sizestr, node->name);
 
-		if (S_ISLNK(node->mode)) {
-			printf(" -> %s\n", node->data.slink_target);
+		if (S_ISLNK(node->inode->base.mode)) {
+			printf(" -> %s\n", node->inode->slink_target);
 		} else {
 			fputc('\n', stdout);
 		}
diff --git a/unpack/optimize_unpack_order.c b/unpack/optimize_unpack_order.c
deleted file mode 100644
index a76dd51..0000000
--- a/unpack/optimize_unpack_order.c
+++ /dev/null
@@ -1,119 +0,0 @@
-/* SPDX-License-Identifier: GPL-3.0-or-later */
-/*
- * optimize_unpack_order.c
- *
- * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
- */
-#include "config.h"
-#include "rdsquashfs.h"
-
-static bool has_fragment(const fstree_t *fs, const file_info_t *file)
-{
-	if (file->size % fs->block_size == 0)
-		return false;
-
-	return file->fragment_offset < fs->block_size &&
-		(file->fragment != 0xFFFFFFFF);
-}
-
-static int compare_files(const fstree_t *fs, const file_info_t *lhs,
-			 const file_info_t *rhs)
-{
-	/* NOOP < everything else */
-	if (lhs->input_file == NULL)
-		return rhs->input_file == NULL ? 0 : -1;
-
-	if (rhs->input_file == NULL)
-		return 1;
-
-	/* Files with fragments come first, ordered by ID.
-	   In case of tie, files without data blocks come first,
-	   and the others are ordered by start block. */
-	if (has_fragment(fs, lhs)) {
-		if (!(has_fragment(fs, rhs)))
-			return -1;
-
-		if (lhs->fragment < rhs->fragment)
-			return -1;
-		if (lhs->fragment > rhs->fragment)
-			return 1;
-
-		if (lhs->size < fs->block_size)
-			return (rhs->size < fs->block_size) ? 0 : -1;
-		if (rhs->size < fs->block_size)
-			return 1;
-		goto order_by_start;
-	}
-
-	if (has_fragment(fs, rhs))
-		return 1;
-
-	/* order the rest by start block */
-order_by_start:
-	return lhs->startblock < rhs->startblock ? -1 :
-		lhs->startblock > rhs->startblock ? 1 : 0;
-}
-
-/* TODO: unify ad-hoc merge sort with the one in fstree_sort */
-static file_info_t *merge(const fstree_t *fs, file_info_t *lhs,
-			  file_info_t *rhs)
-{
-	file_info_t *it;
-	file_info_t *head = NULL;
-	file_info_t **next_ptr = &head;
-
-	while (lhs != NULL && rhs != NULL) {
-		if (compare_files(fs, lhs, rhs) <= 0) {
-			it = lhs;
-			lhs = lhs->next;
-		} else {
-			it = rhs;
-			rhs = rhs->next;
-		}
-
-		*next_ptr = it;
-		next_ptr = &it->next;
-	}
-
-	it = (lhs != NULL ? lhs : rhs);
-	*next_ptr = it;
-	return head;
-}
-
-static file_info_t *list_sort(const fstree_t *fs, file_info_t *head)
-{
-	file_info_t *it, *half, *prev;
-
-	it = half = prev = head;
-	while (it != NULL) {
-		prev = half;
-		half = half->next;
-		it = it->next;
-		if (it != NULL) {
-			it = it->next;
-		}
-	}
-
-	// half refers to the (count/2)'th element ROUNDED UP.
-	// It will be null therefore only in the empty and the
-	// single element list
-	if (half == NULL) {
-		return head;
-	}
-
-	prev->next = NULL;
-
-	return merge(fs, list_sort(fs, head), list_sort(fs, half));
-}
-
-file_info_t *optimize_unpack_order(fstree_t *fs)
-{
-	file_info_t *file_list;
-
-	file_list = list_sort(fs, fs->files);
-	while (file_list != NULL && file_list->input_file == NULL)
-		file_list = file_list->next;
-
-	fs->files = NULL;
-	return file_list;
-}
diff --git a/unpack/options.c b/unpack/options.c
index c7689eb..190a78b 100644
--- a/unpack/options.c
+++ b/unpack/options.c
@@ -124,19 +124,19 @@ void process_command_line(options_t *opt, int argc, char **argv)
 
 		switch (i) {
 		case 'D':
-			opt->rdtree_flags |= RDTREE_NO_DEVICES;
+			opt->rdtree_flags |= SQFS_TREE_NO_DEVICES;
 			break;
 		case 'S':
-			opt->rdtree_flags |= RDTREE_NO_SOCKETS;
+			opt->rdtree_flags |= SQFS_TREE_NO_SOCKETS;
 			break;
 		case 'F':
-			opt->rdtree_flags |= RDTREE_NO_FIFO;
+			opt->rdtree_flags |= SQFS_TREE_NO_FIFO;
 			break;
 		case 'L':
-			opt->rdtree_flags |= RDTREE_NO_SLINKS;
+			opt->rdtree_flags |= SQFS_TREE_NO_SLINKS;
 			break;
 		case 'E':
-			opt->rdtree_flags |= RDTREE_NO_EMPTY;
+			opt->rdtree_flags |= SQFS_TREE_NO_EMPTY;
 			break;
 		case 'C':
 			opt->flags |= UNPACK_CHMOD;
@@ -150,7 +150,6 @@ void process_command_line(options_t *opt, int argc, char **argv)
 #ifdef HAVE_SYS_XATTR_H
 		case 'X':
 			opt->flags |= UNPACK_SET_XATTR;
-			opt->rdtree_flags |= RDTREE_READ_XATTR;
 			break;
 #endif
 		case 'T':
@@ -167,7 +166,6 @@ void process_command_line(options_t *opt, int argc, char **argv)
 			break;
 		case 'x':
 			opt->op = OP_RDATTR;
-			opt->rdtree_flags |= RDTREE_READ_XATTR;
 			opt->cmdpath = get_path(opt->cmdpath, optarg);
 			break;
 		case 'l':
@@ -202,6 +200,10 @@ void process_command_line(options_t *opt, int argc, char **argv)
 		goto fail_arg;
 	}
 
+	if (opt->op == OP_LS || opt->op == OP_CAT || opt->op == OP_RDATTR) {
+		opt->rdtree_flags |= SQFS_TREE_NO_RECURSE;
+	}
+
 	if (optind >= argc) {
 		fputs("Missing image argument\n", stderr);
 		goto fail_arg;
diff --git a/unpack/rdsquashfs.c b/unpack/rdsquashfs.c
index ea21318..60bfd19 100644
--- a/unpack/rdsquashfs.c
+++ b/unpack/rdsquashfs.c
@@ -6,32 +6,20 @@
  */
 #include "rdsquashfs.h"
 
-static void dump_xattrs(fstree_t *fs, tree_xattr_t *xattr)
-{
-	const char *key, *value;
-	size_t i;
-
-	for (i = 0; i < xattr->num_attr; ++i) {
-		key = str_table_get_string(&fs->xattr_keys,
-					   xattr->attr[i].key_index);
-		value = str_table_get_string(&fs->xattr_values,
-					     xattr->attr[i].value_index);
-
-		printf("%s=%s\n", key, value);
-	}
-}
-
 int main(int argc, char **argv)
 {
+	sqfs_xattr_reader_t *xattr = NULL;
 	sqfs_compressor_config_t cfg;
 	int status = EXIT_FAILURE;
+	sqfs_dir_reader_t *dirrd;
 	sqfs_compressor_t *cmp;
+	sqfs_id_table_t *idtbl;
+	sqfs_tree_node_t *n;
 	data_reader_t *data;
 	sqfs_super_t super;
 	sqfs_file_t *file;
-	tree_node_t *n;
 	options_t opt;
-	fstree_t fs;
+	int ret;
 
 	process_command_line(&opt, argc, argv);
 
@@ -66,26 +54,41 @@ int main(int argc, char **argv)
 			goto out_cmp;
 	}
 
-	if (super.flags & SQFS_FLAG_NO_XATTRS)
-		opt.rdtree_flags &= ~RDTREE_READ_XATTR;
+	if (!(super.flags & SQFS_FLAG_NO_XATTRS)) {
+		xattr = sqfs_xattr_reader_create(file, &super, cmp);
+
+		if (sqfs_xattr_reader_load_locations(xattr)) {
+			fputs("Error loading xattr table\n", stderr);
+			goto out_xr;
+		}
+	}
+
+	idtbl = sqfs_id_table_create();
+	if (idtbl == NULL) {
+		perror("creating ID table");
+		goto out_xr;
+	}
 
-	if (deserialize_fstree(&fs, &super, cmp, file, opt.rdtree_flags))
-		goto out_cmp;
+	if (sqfs_id_table_read(idtbl, file, &super, cmp)) {
+		fputs("error loading ID table\n", stderr);
+		goto out_id;
+	}
 
-	fstree_gen_file_list(&fs);
+	dirrd = sqfs_dir_reader_create(&super, cmp, file);
+	if (dirrd == NULL) {
+		perror("creating dir reader");
+		goto out_id;
+	}
 
 	data = data_reader_create(file, &super, cmp);
 	if (data == NULL)
-		goto out_fs;
+		goto out_dr;
 
-	if (opt.cmdpath != NULL) {
-		n = fstree_node_from_path(&fs, opt.cmdpath);
-		if (n == NULL) {
-			perror(opt.cmdpath);
-			goto out;
-		}
-	} else {
-		n = fs.root;
+	ret = sqfs_dir_reader_get_full_hierarchy(dirrd, idtbl, opt.cmdpath,
+						 opt.rdtree_flags, &n);
+	if (ret) {
+		fprintf(stderr, "error reading hierarchy: %d\n", ret);
+		goto out_data;
 	}
 
 	switch (opt.op) {
@@ -93,14 +96,13 @@ int main(int argc, char **argv)
 		list_files(n);
 		break;
 	case OP_CAT:
-		if (!S_ISREG(n->mode)) {
+		if (!S_ISREG(n->inode->base.mode)) {
 			fprintf(stderr, "/%s: not a regular file\n",
 				opt.cmdpath);
 			goto out;
 		}
 
-		if (data_reader_dump_file(data, n->data.file,
-					  STDOUT_FILENO, false))
+		if (data_reader_dump(data, n->inode, STDOUT_FILENO, false))
 			goto out;
 		break;
 	case OP_UNPACK:
@@ -115,30 +117,37 @@ int main(int argc, char **argv)
 		if (restore_fstree(n, opt.flags))
 			goto out;
 
-		if (fill_unpacked_files(&fs, data, opt.flags))
+		if (fill_unpacked_files(super.block_size, n, data, opt.flags))
 			goto out;
 
-		if (update_tree_attribs(&fs, n, opt.flags))
+		if (update_tree_attribs(xattr, n, opt.flags))
 			goto out;
 
 		if (opt.unpack_root != NULL && popd() != 0)
 			goto out;
 		break;
 	case OP_DESCRIBE:
-		if (describe_tree(fs.root, opt.unpack_root))
+		if (describe_tree(n, opt.unpack_root))
 			goto out;
 		break;
 	case OP_RDATTR:
-		if (n->xattr != NULL)
-			dump_xattrs(&fs, n->xattr);
+		if (dump_xattrs(xattr, n->inode))
+			goto out;
 		break;
 	}
 
 	status = EXIT_SUCCESS;
 out:
+	sqfs_dir_tree_destroy(n);
+out_data:
 	data_reader_destroy(data);
-out_fs:
-	fstree_cleanup(&fs);
+out_dr:
+	sqfs_dir_reader_destroy(dirrd);
+out_id:
+	sqfs_id_table_destroy(idtbl);
+out_xr:
+	if (xattr != NULL)
+		sqfs_xattr_reader_destroy(xattr);
 out_cmp:
 	cmp->destroy(cmp);
 out_file:
diff --git a/unpack/rdsquashfs.h b/unpack/rdsquashfs.h
index 065f4aa..e348293 100644
--- a/unpack/rdsquashfs.h
+++ b/unpack/rdsquashfs.h
@@ -12,7 +12,9 @@
 #include "sqfs/meta_reader.h"
 #include "sqfs/compress.h"
 #include "sqfs/id_table.h"
+#include "sqfs/xattr.h"
 #include "sqfs/data.h"
+
 #include "data_reader.h"
 #include "highlevel.h"
 #include "fstree.h"
@@ -62,18 +64,20 @@ typedef struct {
 	const char *image_name;
 } options_t;
 
-void list_files(tree_node_t *node);
+void list_files(const sqfs_tree_node_t *node);
 
-int restore_fstree(tree_node_t *root, int flags);
+int restore_fstree(sqfs_tree_node_t *root, int flags);
 
-int update_tree_attribs(fstree_t *fs, tree_node_t *root, int flags);
+int update_tree_attribs(sqfs_xattr_reader_t *xattr,
+			const sqfs_tree_node_t *root, int flags);
 
-int fill_unpacked_files(fstree_t *fs, data_reader_t *data, int flags);
+int fill_unpacked_files(size_t blk_sz, const sqfs_tree_node_t *root,
+			data_reader_t *data, int flags);
 
-int describe_tree(tree_node_t *root, const char *unpack_root);
+int describe_tree(const sqfs_tree_node_t *root, const char *unpack_root);
 
-void process_command_line(options_t *opt, int argc, char **argv);
+int dump_xattrs(sqfs_xattr_reader_t *xattr, const sqfs_inode_generic_t *inode);
 
-file_info_t *optimize_unpack_order(fstree_t *fs);
+void process_command_line(options_t *opt, int argc, char **argv);
 
 #endif /* RDSQUASHFS_H */
diff --git a/unpack/restore_fstree.c b/unpack/restore_fstree.c
index 21bae3f..afa4abb 100644
--- a/unpack/restore_fstree.c
+++ b/unpack/restore_fstree.c
@@ -6,30 +6,30 @@
  */
 #include "rdsquashfs.h"
 
-static int create_node(tree_node_t *n, int flags)
+static int create_node(const sqfs_tree_node_t *n, int flags)
 {
-	tree_node_t *c;
-	int fd, ret;
+	const sqfs_tree_node_t *c;
 	char *name;
+	int fd;
 
 	if (!(flags & UNPACK_QUIET)) {
-		name = fstree_get_path(n);
+		name = sqfs_tree_node_get_path(n);
 		printf("creating %s\n", name);
 		free(name);
 	}
 
-	switch (n->mode & S_IFMT) {
+	switch (n->inode->base.mode & S_IFMT) {
 	case S_IFDIR:
-		if (mkdir(n->name, 0755) && errno != EEXIST) {
+		if (mkdir((const char *)n->name, 0755) && errno != EEXIST) {
 			fprintf(stderr, "mkdir %s: %s\n",
 				n->name, strerror(errno));
 			return -1;
 		}
 
-		if (pushd(n->name))
+		if (pushd((const char *)n->name))
 			return -1;
 
-		for (c = n->data.dir->children; c != NULL; c = c->next) {
+		for (c = n->children; c != NULL; c = c->next) {
 			if (create_node(c, flags))
 				return -1;
 		}
@@ -38,31 +38,44 @@ static int create_node(tree_node_t *n, int flags)
 			return -1;
 		break;
 	case S_IFLNK:
-		if (symlink(n->data.slink_target, n->name)) {
+		if (symlink(n->inode->slink_target, (const char *)n->name)) {
 			fprintf(stderr, "ln -s %s %s: %s\n",
-				n->data.slink_target, n->name,
+				n->inode->slink_target, n->name,
 				strerror(errno));
 			return -1;
 		}
 		break;
 	case S_IFSOCK:
 	case S_IFIFO:
-		if (mknod(n->name, (n->mode & S_IFMT) | 0700, 0)) {
+		if (mknod((const char *)n->name,
+			  (n->inode->base.mode & S_IFMT) | 0700, 0)) {
 			fprintf(stderr, "creating %s: %s\n",
 				n->name, strerror(errno));
 			return -1;
 		}
 		break;
 	case S_IFBLK:
-	case S_IFCHR:
-		if (mknod(n->name, n->mode & S_IFMT, n->data.devno)) {
+	case S_IFCHR: {
+		uint32_t devno;
+
+		if (n->inode->base.type == SQFS_INODE_EXT_BDEV ||
+		    n->inode->base.type == SQFS_INODE_EXT_CDEV) {
+			devno = n->inode->data.dev_ext.devno;
+		} else {
+			devno = n->inode->data.dev.devno;
+		}
+
+		if (mknod((const char *)n->name, n->inode->base.mode & S_IFMT,
+			  devno)) {
 			fprintf(stderr, "creating device %s: %s\n",
 				n->name, strerror(errno));
 			return -1;
 		}
 		break;
+	}
 	case S_IFREG:
-		fd = open(n->name, O_WRONLY | O_CREAT | O_EXCL, 0600);
+		fd = open((const char *)n->name, O_WRONLY | O_CREAT | O_EXCL,
+			  0600);
 		if (fd < 0) {
 			fprintf(stderr, "creating %s: %s\n",
 				n->name, strerror(errno));
@@ -70,38 +83,99 @@ static int create_node(tree_node_t *n, int flags)
 		}
 
 		close(fd);
+		break;
+	default:
+		break;
+	}
 
-		if (n->parent != NULL) {
-			n->data.file->input_file = fstree_get_path(n);
-		} else {
-			n->data.file->input_file = strdup(n->name);
+	return 0;
+}
+
+#ifdef HAVE_SYS_XATTR_H
+static int set_xattr(sqfs_xattr_reader_t *xattr, const sqfs_tree_node_t *n)
+{
+	sqfs_xattr_value_t *value;
+	sqfs_xattr_entry_t *key;
+	sqfs_xattr_id_t desc;
+	uint32_t index;
+	size_t i;
+	int ret;
+
+	switch (n->inode->base.type) {
+	case SQFS_INODE_EXT_DIR:
+		index = n->inode->data.dir_ext.xattr_idx;
+		break;
+	case SQFS_INODE_EXT_FILE:
+		index = n->inode->data.file_ext.xattr_idx;
+		break;
+	case SQFS_INODE_EXT_SLINK:
+		index = n->inode->data.slink_ext.xattr_idx;
+		break;
+	case SQFS_INODE_EXT_BDEV:
+	case SQFS_INODE_EXT_CDEV:
+		index = n->inode->data.dev_ext.xattr_idx;
+		break;
+	case SQFS_INODE_EXT_FIFO:
+	case SQFS_INODE_EXT_SOCKET:
+		index = n->inode->data.ipc_ext.xattr_idx;
+		break;
+	default:
+		return 0;
+	}
+
+	if (index == 0xFFFFFFFF)
+		return 0;
+
+	if (sqfs_xattr_reader_get_desc(xattr, index, &desc)) {
+		fputs("Error resolving xattr index\n", stderr);
+		return -1;
+	}
+
+	if (sqfs_xattr_reader_seek_kv(xattr, &desc)) {
+		fputs("Error locating xattr key-value pairs\n", stderr);
+		return -1;
+	}
+
+	for (i = 0; i < desc.count; ++i) {
+		if (sqfs_xattr_reader_read_key(xattr, &key)) {
+			fputs("Error reading xattr key\n", stderr);
+			return -1;
 		}
 
-		if (n->data.file->input_file == NULL) {
-			perror("restoring file path");
+		if (sqfs_xattr_reader_read_value(xattr, key, &value)) {
+			fputs("Error reading xattr value\n", stderr);
+			free(key);
 			return -1;
 		}
 
-		ret = canonicalize_name(n->data.file->input_file);
-		assert(ret == 0);
-		break;
-	default:
-		break;
+		ret = lsetxattr((const char *)n->name, (const char *)key->key,
+				value->value, value->size, 0);
+		if (ret) {
+			fprintf(stderr, "setting xattr '%s' on %s: %s\n",
+				key->key, n->name, strerror(errno));
+		}
+
+		free(key);
+		free(value);
+		if (ret)
+			return -1;
 	}
 
 	return 0;
 }
+#endif
 
-static int set_attribs(fstree_t *fs, tree_node_t *n, int flags)
+static int set_attribs(sqfs_xattr_reader_t *xattr,
+		       const sqfs_tree_node_t *n, int flags)
 {
-	tree_node_t *c;
+	const sqfs_tree_node_t *c;
 
-	if (S_ISDIR(n->mode)) {
-		if (pushd(n->name))
+	if (S_ISDIR(n->inode->base.mode)) {
+		if (pushd((const char *)n->name))
 			return -1;
 
-		for (c = n->data.dir->children; c != NULL; c = c->next) {
-			if (set_attribs(fs, c, flags))
+		for (c = n->children; c != NULL; c = c->next) {
+			if (set_attribs(xattr, c, flags))
 				return -1;
 		}
 
@@ -110,38 +184,21 @@ static int set_attribs(fstree_t *fs, tree_node_t *n, int flags)
 	}
 
 #ifdef HAVE_SYS_XATTR_H
-	if ((flags & UNPACK_SET_XATTR) && n->xattr != NULL) {
-		size_t i, len, kidx, vidx;
-		const char *key, *value;
-
-		for (i = 0; i < n->xattr->num_attr; ++i) {
-			kidx = n->xattr->attr[i].key_index;
-			vidx = n->xattr->attr[i].value_index;
-
-			key = str_table_get_string(&fs->xattr_keys, kidx);
-			value = str_table_get_string(&fs->xattr_values, vidx);
-			len = strlen(value);
-
-			if (lsetxattr(n->name, key, value, len, 0)) {
-				fprintf(stderr,
-					"setting xattr '%s' on %s: %s\n",
-					key, n->name, strerror(errno));
-				return -1;
-			}
-		}
+	if ((flags & UNPACK_SET_XATTR) && xattr != NULL) {
+		if (set_xattr(xattr, n))
+			return -1;
 	}
-#else
-	(void)fs;
 #endif
 
 	if (flags & UNPACK_SET_TIMES) {
 		struct timespec times[2];
 
 		memset(times, 0, sizeof(times));
-		times[0].tv_sec = n->mod_time;
-		times[1].tv_sec = n->mod_time;
+		times[0].tv_sec = n->inode->base.mod_time;
+		times[1].tv_sec = n->inode->base.mod_time;
 
-		if (utimensat(AT_FDCWD, n->name, times, AT_SYMLINK_NOFOLLOW)) {
+		if (utimensat(AT_FDCWD, (const char *)n->name, times,
+			      AT_SYMLINK_NOFOLLOW)) {
 			fprintf(stderr, "setting timestamp on %s: %s\n",
 				n->name, strerror(errno));
 			return -1;
@@ -149,7 +206,7 @@ static int set_attribs(fstree_t *fs, tree_node_t *n, int flags)
 	}
 
 	if (flags & UNPACK_CHOWN) {
-		if (fchownat(AT_FDCWD, n->name, n->uid, n->gid,
+		if (fchownat(AT_FDCWD, (const char *)n->name, n->uid, n->gid,
 			     AT_SYMLINK_NOFOLLOW)) {
 			fprintf(stderr, "chown %s: %s\n",
 				n->name, strerror(errno));
@@ -157,8 +214,9 @@ static int set_attribs(fstree_t *fs, tree_node_t *n, int flags)
 		}
 	}
 
-	if (flags & UNPACK_CHMOD && !S_ISLNK(n->mode)) {
-		if (fchmodat(AT_FDCWD, n->name, n->mode, 0)) {
+	if (flags & UNPACK_CHMOD && !S_ISLNK(n->inode->base.mode)) {
+		if (fchmodat(AT_FDCWD, (const char *)n->name,
+			     n->inode->base.mode & ~S_IFMT, 0)) {
 			fprintf(stderr, "chmod %s: %s\n",
 				n->name, strerror(errno));
 			return -1;
@@ -167,16 +225,16 @@ static int set_attribs(fstree_t *fs, tree_node_t *n, int flags)
 	return 0;
 }
 
-int restore_fstree(tree_node_t *root, int flags)
+int restore_fstree(sqfs_tree_node_t *root, int flags)
 {
-	tree_node_t *n, *old_parent;
+	sqfs_tree_node_t *n, *old_parent;
 
 	/* make sure fstree_get_path() stops at this node */
 	old_parent = root->parent;
 	root->parent = NULL;
 
-	if (S_ISDIR(root->mode)) {
-		for (n = root->data.dir->children; n != NULL; n = n->next) {
+	if (S_ISDIR(root->inode->base.mode)) {
+		for (n = root->children; n != NULL; n = n->next) {
 			if (create_node(n, flags))
 				return -1;
 		}
@@ -189,20 +247,23 @@ int restore_fstree(tree_node_t *root, int flags)
 	return 0;
 }
 
-int update_tree_attribs(fstree_t *fs, tree_node_t *root, int flags)
+int update_tree_attribs(sqfs_xattr_reader_t *xattr,
+			const sqfs_tree_node_t *root, int flags)
 {
-	tree_node_t *n;
+	const sqfs_tree_node_t *n;
 
-	if ((flags & (UNPACK_CHOWN | UNPACK_CHMOD | UNPACK_SET_TIMES)) == 0)
+	if ((flags & (UNPACK_CHOWN | UNPACK_CHMOD |
+		      UNPACK_SET_TIMES | UNPACK_SET_XATTR)) == 0) {
 		return 0;
+	}
 
-	if (S_ISDIR(root->mode)) {
-		for (n = root->data.dir->children; n != NULL; n = n->next) {
-			if (set_attribs(fs, n, flags))
+	if (S_ISDIR(root->inode->base.mode)) {
+		for (n = root->children; n != NULL; n = n->next) {
+			if (set_attribs(xattr, n, flags))
 				return -1;
 		}
 	} else {
-		if (set_attribs(fs, root, flags))
+		if (set_attribs(xattr, root, flags))
 			return -1;
 	}