Replace fstree/sqfshelper xattr code with sqfs_xattr_writer_t

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

14 files changed, 121 insertions, 605 deletions

diff --git a/include/fstree.h b/include/fstree.h
index a60b214..b355f06 100644
--- a/include/fstree.h
+++ b/include/fstree.h
@@ -14,50 +14,13 @@
 #include <stddef.h>
 #include <stdio.h>
 
-#include "str_table.h"
+#include "sqfs/predef.h"
 #include "compat.h"
 
-#define FSTREE_XATTR_KEY_BUCKETS 31
-#define FSTREE_XATTR_VALUE_BUCKETS 511
-
 typedef struct tree_node_t tree_node_t;
 typedef struct file_info_t file_info_t;
 typedef struct dir_info_t dir_info_t;
 typedef struct fstree_t fstree_t;
-typedef struct tree_xattr_t tree_xattr_t;
-
-/* Encapsulates a set of key-value pairs attached to a tree_node_t */
-struct tree_xattr_t {
-	/* Number of key-value pairs */
-	size_t num_attr;
-
-	/* Total size of the array, i.e. it's capacity */
-	size_t max_attr;
-
-	/* Offset of the meta data block where the pairs are stored */
-	sqfs_u64 block;
-
-	/* Offset into a meta data block where the pairs start */
-	sqfs_u32 offset;
-
-	/* Number of bytes written to disk */
-	sqfs_u32 size;
-
-	/* Incremental index within all xattr blocks */
-	size_t index;
-
-	/* Back reference to the tree node this was created for */
-	tree_node_t *owner;
-
-	/* linked list pointer of list of attributes in @ref fstree_t */
-	tree_xattr_t *next;
-
-	/* Array with pairs of key-value tupples */
-	struct {
-		sqfs_u32 key_index;
-		sqfs_u32 value_index;
-	} attr[];
-};
 
 /* Additional meta data stored in a tree_node_t for regular files. */
 struct file_info_t {
@@ -90,21 +53,13 @@ struct tree_node_t {
 	/* For the root node, this points to an empty string. */
 	char *name;
 
-	/*
-	  A pointer to an extended attribute array or NULL if unused.
-
-	  This field is not stored in-line and taken care of by the generic
-	  fstree cleanup code, since it is generatde after the tree already
-	  exists and shared across multiple nodes.
-	*/
-	tree_xattr_t *xattr;
-
+	sqfs_u32 xattr_idx;
 	sqfs_u32 uid;
 	sqfs_u32 gid;
 	sqfs_u32 inode_num;
 	sqfs_u32 mod_time;
 	sqfs_u16 mode;
-	sqfs_u16 pad0[3];
+	sqfs_u16 pad0;
 
 	/* SquashFS inode refernce number. 32 bit offset of the meta data
 	   block start (relative to inode table start), shifted left by 16
@@ -130,11 +85,7 @@ struct fstree_t {
 	size_t block_size;
 	size_t inode_tbl_size;
 
-	str_table_t xattr_keys;
-	str_table_t xattr_values;
-
 	tree_node_t *root;
-	tree_xattr_t *xattr;
 
 	/* linear array of tree nodes. inode number is array index */
 	tree_node_t **inode_table;
@@ -194,20 +145,6 @@ tree_node_t *fstree_add_generic(fstree_t *fs, const char *path,
 				const struct stat *sb, const char *extra);
 
 /*
-  Add an extended attribute key value pair to a tree node.
-
-  Returns 0 on success, prints error to stderr on failure.
-*/
-int fstree_add_xattr(fstree_t *fs, tree_node_t *node,
-		     const char *key, const char *value);
-
-/* Recompute running index number of all xattr blocks. */
-void fstree_xattr_reindex(fstree_t *fs);
-
-/* Sort and dedupliciate xattr blocks, then recumpute the index numbers. */
-void fstree_xattr_deduplicate(fstree_t *fs);
-
-/*
   Parses the file format accepted by gensquashfs and produce a file system
   tree from it. File input paths are interpreted as relative to the current
   working directory.
diff --git a/lib/fstree/Makemodule.am b/lib/fstree/Makemodule.am
index fe2c5ca..be5f8fc 100644
--- a/lib/fstree/Makemodule.am
+++ b/lib/fstree/Makemodule.am
@@ -2,7 +2,7 @@ libfstree_a_SOURCES = lib/fstree/fstree.c lib/fstree/fstree_from_file.c
 libfstree_a_SOURCES += lib/fstree/fstree_sort.c
 libfstree_a_SOURCES += lib/fstree/gen_inode_table.c lib/fstree/get_path.c
 libfstree_a_SOURCES += lib/fstree/mknode.c
-libfstree_a_SOURCES += lib/fstree/add_by_path.c lib/fstree/xattr.c
+libfstree_a_SOURCES += lib/fstree/add_by_path.c
 libfstree_a_SOURCES += include/fstree.h
 libfstree_a_SOURCES += lib/fstree/gen_file_list.c
 libfstree_a_SOURCES += lib/fstree/source_date_epoch.c
diff --git a/lib/fstree/fstree.c b/lib/fstree/fstree.c
index 357fd3d..efb6a78 100644
--- a/lib/fstree/fstree.c
+++ b/lib/fstree/fstree.c
@@ -117,20 +117,10 @@ int fstree_init(fstree_t *fs, size_t block_size, char *defaults)
 	if (defaults != NULL && process_defaults(&fs->defaults, defaults) != 0)
 		return -1;
 
-	if (str_table_init(&fs->xattr_keys, FSTREE_XATTR_KEY_BUCKETS))
-		return -1;
-
-	if (str_table_init(&fs->xattr_values, FSTREE_XATTR_VALUE_BUCKETS)) {
-		str_table_cleanup(&fs->xattr_keys);
-		return -1;
-	}
-
 	fs->root = fstree_mknode(NULL, "", 0, NULL, &fs->defaults);
 
 	if (fs->root == NULL) {
 		perror("initializing file system tree");
-		str_table_cleanup(&fs->xattr_values);
-		str_table_cleanup(&fs->xattr_keys);
 		return -1;
 	}
 
@@ -139,16 +129,6 @@ int fstree_init(fstree_t *fs, size_t block_size, char *defaults)
 
 void fstree_cleanup(fstree_t *fs)
 {
-	tree_xattr_t *xattr;
-
-	while (fs->xattr != NULL) {
-		xattr = fs->xattr;
-		fs->xattr = xattr->next;
-		free(xattr);
-	}
-
-	str_table_cleanup(&fs->xattr_keys);
-	str_table_cleanup(&fs->xattr_values);
 	free_recursive(fs->root);
 	free(fs->inode_table);
 	memset(fs, 0, sizeof(*fs));
diff --git a/lib/fstree/mknode.c b/lib/fstree/mknode.c
index f90bd00..6274ba7 100644
--- a/lib/fstree/mknode.c
+++ b/lib/fstree/mknode.c
@@ -39,6 +39,7 @@ tree_node_t *fstree_mknode(tree_node_t *parent, const char *name,
 		n->parent = parent;
 	}
 
+	n->xattr_idx = 0xFFFFFFFF;
 	n->uid = sb->st_uid;
 	n->gid = sb->st_gid;
 	n->mode = sb->st_mode;
diff --git a/lib/fstree/xattr.c b/lib/fstree/xattr.c
deleted file mode 100644
index 45ea8a6..0000000
--- a/lib/fstree/xattr.c
+++ /dev/null
@@ -1,174 +0,0 @@
-/* SPDX-License-Identifier: GPL-3.0-or-later */
-/*
- * xattr.c
- *
- * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
- */
-#include "config.h"
-
-#include "fstree.h"
-#include "util.h"
-
-#include <stdlib.h>
-#include <string.h>
-#include <stdio.h>
-#include <errno.h>
-
-static void remove_from_list(fstree_t *fs, tree_xattr_t *xattr)
-{
-	tree_xattr_t *prev = NULL, *it = fs->xattr;
-
-	while (it != xattr) {
-		prev = it;
-		it = it->next;
-	}
-
-	if (prev == NULL) {
-		fs->xattr = xattr->next;
-	} else {
-		prev->next = xattr->next;
-	}
-}
-
-static tree_xattr_t *grow_xattr_block(tree_xattr_t *xattr)
-{
-	size_t new_size, old_size = 0, new_count = 4;
-	void *new;
-
-	if (xattr != NULL) {
-		if (SZ_MUL_OV(xattr->max_attr, 2, &new_count))
-			goto fail_ov;
-		old_size = sizeof(*xattr) + sizeof(sqfs_u64) * xattr->max_attr;
-	}
-
-	if (SZ_MUL_OV(sizeof(sqfs_u64), new_count, &new_size) ||
-	    SZ_ADD_OV(sizeof(*xattr), new_size, &new_size)) {
-		goto fail_ov;
-	}
-
-	new = realloc(xattr, new_size);
-	if (new == NULL)
-		goto fail;
-
-	memset((char *)new + old_size, 0, new_size - old_size);
-
-	xattr = new;
-	xattr->max_attr = new_count;
-	return xattr;
-fail_ov:
-	errno = EOVERFLOW;
-fail:
-	perror("adding extended attributes");
-	free(xattr);
-	return NULL;
-}
-
-int fstree_add_xattr(fstree_t *fs, tree_node_t *node,
-		     const char *key, const char *value)
-{
-	size_t key_idx, value_idx;
-	tree_xattr_t *xattr;
-
-	if (str_table_get_index(&fs->xattr_keys, key, &key_idx))
-		return -1;
-
-	if (str_table_get_index(&fs->xattr_values, value, &value_idx))
-		return -1;
-
-	if (sizeof(size_t) > sizeof(sqfs_u32)) {
-		if (key_idx > 0xFFFFFFFFUL) {
-			fputs("Too many unique xattr keys\n", stderr);
-			return -1;
-		}
-
-		if (value_idx > 0xFFFFFFFFUL) {
-			fputs("Too many unique xattr values\n", stderr);
-			return -1;
-		}
-	}
-
-	xattr = node->xattr;
-
-	if (xattr == NULL || xattr->max_attr == xattr->num_attr) {
-		if (xattr != NULL)
-			remove_from_list(fs, xattr);
-
-		xattr = grow_xattr_block(xattr);
-		if (xattr == NULL)
-			return -1;
-
-		node->xattr = xattr;
-		xattr->owner = node;
-		xattr->next = fs->xattr;
-		fs->xattr = xattr;
-	}
-
-	xattr->attr[xattr->num_attr].key_index = key_idx;
-	xattr->attr[xattr->num_attr].value_index = value_idx;
-	xattr->num_attr += 1;
-	return 0;
-}
-
-static int cmp_attr(const void *lhs, const void *rhs)
-{
-	return memcmp(lhs, rhs, sizeof(((tree_xattr_t *)0)->attr[0]));
-}
-
-void fstree_xattr_reindex(fstree_t *fs)
-{
-	sqfs_u32 key_idx, value_idx;
-	size_t i, index = 0;
-	tree_xattr_t *it;
-
-	str_table_reset_ref_count(&fs->xattr_keys);
-	str_table_reset_ref_count(&fs->xattr_values);
-
-	for (it = fs->xattr; it != NULL; it = it->next) {
-		it->index = index++;
-
-		for (i = 0; i < it->num_attr; ++i) {
-			key_idx = it->attr[i].key_index;
-			value_idx = it->attr[i].value_index;
-
-			str_table_add_ref(&fs->xattr_keys, key_idx);
-			str_table_add_ref(&fs->xattr_values, value_idx);
-		}
-	}
-}
-
-void fstree_xattr_deduplicate(fstree_t *fs)
-{
-	tree_xattr_t *it, *it1, *prev;
-	int diff;
-
-	for (it = fs->xattr; it != NULL; it = it->next)
-		qsort(it->attr, it->num_attr, sizeof(it->attr[0]), cmp_attr);
-
-	prev = NULL;
-	it = fs->xattr;
-
-	while (it != NULL) {
-		for (it1 = fs->xattr; it1 != it; it1 = it1->next) {
-			if (it1->num_attr != it->num_attr)
-				continue;
-
-			diff = memcmp(it1->attr, it->attr,
-				      it->num_attr * sizeof(it->attr[0]));
-			if (diff == 0)
-				break;
-		}
-
-		if (it1 != it) {
-			prev->next = it->next;
-			it->owner->xattr = it1;
-
-			free(it);
-			it = prev->next;
-		} else {
-			prev = it;
-			it = it->next;
-		}
-	}
-
-	fstree_xattr_reindex(fs);
-}
diff --git a/lib/sqfshelper/Makemodule.am b/lib/sqfshelper/Makemodule.am
index 896605a..2ae1ac2 100644
--- a/lib/sqfshelper/Makemodule.am
+++ b/lib/sqfshelper/Makemodule.am
@@ -6,8 +6,7 @@ libsqfshelper_a_SOURCES += lib/sqfshelper/print_version.c
 libsqfshelper_a_SOURCES += lib/sqfshelper/inode_stat.c
 libsqfshelper_a_SOURCES += lib/sqfshelper/data_reader_dump.c
 libsqfshelper_a_SOURCES += lib/sqfshelper/compress.c lib/sqfshelper/comp_opt.c
-libsqfshelper_a_SOURCES += lib/sqfshelper/data_writer.c
-libsqfshelper_a_SOURCES += lib/sqfshelper/write_xattr.c include/highlevel.h
+libsqfshelper_a_SOURCES += lib/sqfshelper/data_writer.c include/highlevel.h
 libsqfshelper_a_SOURCES += lib/sqfshelper/get_path.c lib/sqfshelper/io_stdin.c
 
 noinst_LIBRARIES += libsqfshelper.a
diff --git a/lib/sqfshelper/serialize_fstree.c b/lib/sqfshelper/serialize_fstree.c
index 2ec7daa..9a122ac 100644
--- a/lib/sqfshelper/serialize_fstree.c
+++ b/lib/sqfshelper/serialize_fstree.c
@@ -36,7 +36,7 @@ static sqfs_inode_generic_t *write_dir_entries(sqfs_dir_writer_t *dirw,
 	if (sqfs_dir_writer_end(dirw))
 		return NULL;
 
-	xattr = (node->xattr == NULL) ? 0xFFFFFFFF : node->xattr->index;
+	xattr = node->xattr_idx;
 	parent_inode = (node->parent == NULL) ? 1 : node->parent->inode_num;
 
 	inode = sqfs_dir_writer_create_inode(dirw, 0, xattr, parent_inode);
diff --git a/lib/sqfshelper/tree_node_to_inode.c b/lib/sqfshelper/tree_node_to_inode.c
index d75e959..bafaaf7 100644
--- a/lib/sqfshelper/tree_node_to_inode.c
+++ b/lib/sqfshelper/tree_node_to_inode.c
@@ -18,26 +18,11 @@
 static int get_type(tree_node_t *node)
 {
 	switch (node->mode & S_IFMT) {
-	case S_IFSOCK:
-		if (node->xattr != NULL)
-			return SQFS_INODE_EXT_SOCKET;
-		return SQFS_INODE_SOCKET;
-	case S_IFIFO:
-		if (node->xattr != NULL)
-			return SQFS_INODE_EXT_FIFO;
-		return SQFS_INODE_FIFO;
-	case S_IFLNK:
-		if (node->xattr != NULL)
-			return SQFS_INODE_EXT_SLINK;
-		return SQFS_INODE_SLINK;
-	case S_IFBLK:
-		if (node->xattr != NULL)
-			return SQFS_INODE_EXT_BDEV;
-		return SQFS_INODE_BDEV;
-	case S_IFCHR:
-		if (node->xattr != NULL)
-			return SQFS_INODE_EXT_CDEV;
-		return SQFS_INODE_CDEV;
+	case S_IFSOCK: return SQFS_INODE_SOCKET;
+	case S_IFIFO: return SQFS_INODE_FIFO;
+	case S_IFLNK: return SQFS_INODE_SLINK;
+	case S_IFBLK: return SQFS_INODE_BDEV;
+	case S_IFCHR: return SQFS_INODE_CDEV;
 	}
 	assert(0);
 }
@@ -47,7 +32,6 @@ sqfs_inode_generic_t *tree_node_to_inode(sqfs_id_table_t *idtbl,
 {
 	sqfs_inode_generic_t *inode;
 	sqfs_u16 uid_idx, gid_idx;
-	sqfs_u32 xattr = 0xFFFFFFFF;
 	size_t extra = 0;
 
 	if (S_ISREG(node->mode)) {
@@ -78,8 +62,8 @@ sqfs_inode_generic_t *tree_node_to_inode(sqfs_id_table_t *idtbl,
 	if (sqfs_id_table_id_to_index(idtbl, node->gid, &gid_idx))
 		goto fail;
 
-	if (node->xattr != NULL)
-		xattr = node->xattr->index;
+	if (node->xattr_idx != 0xFFFFFFFF)
+		sqfs_inode_make_extended(inode);
 
 	inode->base.mode = node->mode;
 	inode->base.uid_idx = uid_idx;
@@ -95,7 +79,7 @@ sqfs_inode_generic_t *tree_node_to_inode(sqfs_id_table_t *idtbl,
 	case SQFS_INODE_EXT_FIFO:
 	case SQFS_INODE_EXT_SOCKET:
 		inode->data.ipc_ext.nlink = 1;
-		inode->data.ipc_ext.xattr_idx = xattr;
+		inode->data.ipc_ext.xattr_idx = node->xattr_idx;
 		break;
 	case SQFS_INODE_SLINK:
 		inode->data.slink.nlink = 1;
@@ -104,7 +88,7 @@ sqfs_inode_generic_t *tree_node_to_inode(sqfs_id_table_t *idtbl,
 	case SQFS_INODE_EXT_SLINK:
 		inode->data.slink_ext.nlink = 1;
 		inode->data.slink_ext.target_size = extra;
-		inode->data.slink_ext.xattr_idx = xattr;
+		inode->data.slink_ext.xattr_idx = node->xattr_idx;
 		break;
 	case SQFS_INODE_BDEV:
 	case SQFS_INODE_CDEV:
@@ -115,15 +99,12 @@ sqfs_inode_generic_t *tree_node_to_inode(sqfs_id_table_t *idtbl,
 	case SQFS_INODE_EXT_CDEV:
 		inode->data.dev_ext.nlink = 1;
 		inode->data.dev_ext.devno = node->data.devno;
-		inode->data.dev_ext.xattr_idx = xattr;
+		inode->data.dev_ext.xattr_idx = node->xattr_idx;
 		break;
 	case SQFS_INODE_FILE:
-		if (xattr != 0xFFFFFFFF) {
-			sqfs_inode_make_extended(inode);
-			inode->data.file_ext.xattr_idx = xattr;
-		}
 		break;
 	case SQFS_INODE_EXT_FILE:
+		inode->data.file_ext.xattr_idx = node->xattr_idx;
 		break;
 	default:
 		goto fail;
diff --git a/lib/sqfshelper/write_xattr.c b/lib/sqfshelper/write_xattr.c
deleted file mode 100644
index a3f5170..0000000
--- a/lib/sqfshelper/write_xattr.c
+++ /dev/null
@@ -1,278 +0,0 @@
-/* SPDX-License-Identifier: GPL-3.0-or-later */
-/*
- * write_xattr.c
- *
- * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
- */
-#include "config.h"
-
-#include "sqfs/meta_writer.h"
-#include "sqfs/xattr.h"
-#include "highlevel.h"
-#include "util.h"
-
-#include <assert.h>
-#include <stdlib.h>
-#include <string.h>
-#include <stdio.h>
-
-static int write_key(sqfs_meta_writer_t *mw, const char *key,
-		     tree_xattr_t *xattr, bool value_is_ool)
-{
-	sqfs_xattr_entry_t kent;
-	int type;
-
-	type = sqfs_get_xattr_prefix_id(key);
-	if (type < 0) {
-		fprintf(stderr, "unsupported xattr key '%s'\n", key);
-		return -1;
-	}
-
-	key = strchr(key, '.');
-	assert(key != NULL);
-	++key;
-
-	if (value_is_ool)
-		type |= SQFS_XATTR_FLAG_OOL;
-
-	kent.type = htole16(type);
-	kent.size = htole16(strlen(key));
-
-	if (sqfs_meta_writer_append(mw, &kent, sizeof(kent)))
-		return -1;
-	if (sqfs_meta_writer_append(mw, key, strlen(key)))
-		return -1;
-
-	xattr->size += sizeof(sqfs_xattr_entry_t) + strlen(key);
-	return 0;
-}
-
-static int write_value(sqfs_meta_writer_t *mw, const char *value,
-		       tree_xattr_t *xattr, sqfs_u64 *value_ref_out)
-{
-	sqfs_xattr_value_t vent;
-	sqfs_u32 offset;
-	sqfs_u64 block;
-
-	sqfs_meta_writer_get_position(mw, &block, &offset);
-	*value_ref_out = (block << 16) | (offset & 0xFFFF);
-
-	vent.size = htole32(strlen(value));
-
-	if (sqfs_meta_writer_append(mw, &vent, sizeof(vent)))
-		return -1;
-
-	if (sqfs_meta_writer_append(mw, value, strlen(value)))
-		return -1;
-
-	xattr->size += sizeof(vent) + strlen(value);
-	return 0;
-}
-
-static int write_value_ool(sqfs_meta_writer_t *mw, sqfs_u64 location,
-			   tree_xattr_t *xattr)
-{
-	sqfs_xattr_value_t vent;
-	sqfs_u64 ref;
-
-	vent.size = htole32(sizeof(location));
-	if (sqfs_meta_writer_append(mw, &vent, sizeof(vent)))
-		return -1;
-
-	ref = htole64(location);
-	if (sqfs_meta_writer_append(mw, &ref, sizeof(ref)))
-		return -1;
-
-	xattr->size += sizeof(vent) + sizeof(ref);
-	return 0;
-}
-
-static bool should_store_ool(fstree_t *fs, const char *value, size_t index)
-{
-	size_t refcount;
-
-	refcount = str_table_get_ref_count(&fs->xattr_values, index);
-	if (refcount < 2)
-		return false;
-
-	/*
-	  Storing in line needs this many bytes: refcount * len
-
-	  Storing out-of-line needs this many: len + (refcount - 1) * 8
-
-	  Out-of-line prefereable if:
-	      refcount * len > len + (refcount - 1) * 8
-	   => refcount * len - len > (refcount - 1) * 8
-	   => (refcount - 1) * len > (refcount - 1) * 8
-	   => len > 8
-
-	   Note that this only holds iff refcount - 1 != 0, i.e. refcount > 1,
-	   otherwise we would be dividing by 0 in the 3rd step.
-	 */
-	return strlen(value) > sizeof(sqfs_u64);
-}
-
-static int write_kv_pairs(fstree_t *fs, sqfs_meta_writer_t *mw,
-			  tree_xattr_t *xattr, sqfs_u64 *ool_locations)
-{
-	sqfs_u32 key_idx, val_idx;
-	const char *key, *value;
-	sqfs_u64 ref;
-	size_t i;
-
-	for (i = 0; i < xattr->num_attr; ++i) {
-		key_idx = xattr->attr[i].key_index;
-		val_idx = xattr->attr[i].value_index;
-
-		key = str_table_get_string(&fs->xattr_keys, key_idx);
-		value = str_table_get_string(&fs->xattr_values, val_idx);
-
-		if (ool_locations[val_idx] == 0xFFFFFFFFFFFFFFFF) {
-			if (write_key(mw, key, xattr, false))
-				return -1;
-
-			if (write_value(mw, value, xattr, &ref))
-				return -1;
-
-			if (should_store_ool(fs, value, val_idx))
-				ool_locations[val_idx] = ref;
-		} else {
-			if (write_key(mw, key, xattr, true))
-				return -1;
-
-			if (write_value_ool(mw, ool_locations[val_idx], xattr))
-				return -1;
-		}
-	}
-
-	return 0;
-}
-
-static sqfs_u64 *create_ool_locations_table(fstree_t *fs)
-{
-	sqfs_u64 *table;
-	size_t i;
-
-	table = alloc_array(sizeof(sqfs_u64), fs->xattr_values.num_strings);
-
-	if (table == NULL) {
-		perror("allocating Xattr OOL locations table");
-		return NULL;
-	}
-
-	for (i = 0; i < fs->xattr_values.num_strings; ++i) {
-		table[i] = 0xFFFFFFFFFFFFFFFFUL;
-	}
-
-	return table;
-}
-
-int write_xattr(sqfs_file_t *file, fstree_t *fs, sqfs_super_t *super,
-		sqfs_compressor_t *cmp)
-{
-	sqfs_u64 kv_start, id_start, block, off, *tbl, *ool_locations;
-	size_t i = 0, count = 0, blocks;
-	sqfs_xattr_id_table_t idtbl;
-	sqfs_xattr_id_t id_ent;
-	sqfs_meta_writer_t *mw;
-	tree_xattr_t *it;
-	sqfs_u32 offset;
-
-	if (fs->xattr == NULL)
-		return 0;
-
-	ool_locations = create_ool_locations_table(fs);
-	if (ool_locations == NULL)
-		return -1;
-
-	mw = sqfs_meta_writer_create(file, cmp, 0);
-	if (mw == NULL)
-		goto fail_ool;
-
-	/* write xattr key-value pairs */
-	kv_start = file->get_size(file);
-
-	for (it = fs->xattr; it != NULL; it = it->next) {
-		sqfs_meta_writer_get_position(mw, &it->block, &it->offset);
-		it->size = 0;
-
-		if (write_kv_pairs(fs, mw, it, ool_locations))
-			goto fail_mw;
-
-		++count;
-	}
-
-	if (sqfs_meta_writer_flush(mw))
-		goto fail_mw;
-
-	sqfs_meta_writer_reset(mw);
-
-	/* allocate location table */
-	blocks = (count * sizeof(id_ent)) / SQFS_META_BLOCK_SIZE;
-
-	if ((count * sizeof(id_ent)) % SQFS_META_BLOCK_SIZE)
-		++blocks;
-
-	tbl = alloc_array(sizeof(sqfs_u64), blocks);
-
-	if (tbl == NULL) {
-		perror("generating xattr ID table");
-		goto fail_mw;
-	}
-
-	/* write ID table referring to key value pairs, record offsets */
-	id_start = 0;
-	off = file->get_size(file);
-	tbl[i++] = htole64(off);
-
-	for (it = fs->xattr; it != NULL; it = it->next) {
-		id_ent.xattr = htole64((it->block << 16) | it->offset);
-		id_ent.count = htole32(it->num_attr);
-		id_ent.size = htole32(it->size);
-
-		if (sqfs_meta_writer_append(mw, &id_ent, sizeof(id_ent)))
-			goto fail_tbl;
-
-		sqfs_meta_writer_get_position(mw, &block, &offset);
-
-		if (block != id_start) {
-			id_start = block;
-			tbl[i++] = htole64(off + id_start);
-		}
-	}
-
-	if (sqfs_meta_writer_flush(mw))
-		goto fail_tbl;
-
-	/* write offset table */
-	idtbl.xattr_table_start = htole64(kv_start);
-	idtbl.xattr_ids = htole32(count);
-	idtbl.unused = 0;
-
-	super->xattr_id_table_start = file->get_size(file);
-	super->flags &= ~SQFS_FLAG_NO_XATTRS;
-
-	if (file->write_at(file, super->xattr_id_table_start,
-			   &idtbl, sizeof(idtbl))) {
-		perror("writing xattr ID table");
-		goto fail_tbl;
-	}
-
-	if (file->write_at(file, super->xattr_id_table_start + sizeof(idtbl),
-			   tbl, sizeof(tbl[0]) * blocks)) {
-		perror("writing xattr ID table");
-		goto fail_tbl;
-	}
-
-	free(tbl);
-	sqfs_meta_writer_destroy(mw);
-	free(ool_locations);
-	return 0;
-fail_tbl:
-	free(tbl);
-fail_mw:
-	sqfs_meta_writer_destroy(mw);
-fail_ool:
-	free(ool_locations);
-	return -1;
-}
diff --git a/mkfs/dirscan.c b/mkfs/dirscan.c
index 160fbc3..e33e6f7 100644
--- a/mkfs/dirscan.c
+++ b/mkfs/dirscan.c
@@ -40,7 +40,7 @@ fail:
 }
 
 #ifdef HAVE_SYS_XATTR_H
-static int populate_xattr(fstree_t *fs, tree_node_t *node)
+static int populate_xattr(sqfs_xattr_writer_t *xwr, tree_node_t *node)
 {
 	char *key, *value = NULL, *buffer = NULL;
 	ssize_t buflen, vallen, keylen;
@@ -74,7 +74,7 @@ static int populate_xattr(fstree_t *fs, tree_node_t *node)
 			goto fail;
 
 		if (vallen > 0) {
-			value = alloc_string(vallen);
+			value = calloc(1, vallen);
 			if (value == NULL) {
 				perror("xattr value buffer");
 				goto fail;
@@ -86,9 +86,11 @@ static int populate_xattr(fstree_t *fs, tree_node_t *node)
 				goto fail;
 			}
 
-			value[vallen] = 0;
-			if (fstree_add_xattr(fs, node, key, value))
+			if (sqfs_xattr_writer_add(xwr, key, value, vallen)) {
+				fputs("Error storing xattr key-value pair\n",
+				      stderr);
 				goto fail;
+			}
 
 			free(value);
 			value = NULL;
@@ -109,7 +111,8 @@ fail:
 #endif
 
 static int populate_dir(fstree_t *fs, tree_node_t *root, dev_t devstart,
-			void *selinux_handle, unsigned int flags)
+			void *selinux_handle, sqfs_xattr_writer_t *xwr,
+			unsigned int flags)
 {
 	char *extra = NULL, *path;
 	struct dirent *ent;
@@ -171,9 +174,14 @@ static int populate_dir(fstree_t *fs, tree_node_t *root, dev_t devstart,
 			goto fail;
 		}
 
+		if (sqfs_xattr_writer_begin(xwr)) {
+			fputs("error recoding xattr key-value pairs\n", stderr);
+			return -1;
+		}
+
 #ifdef HAVE_SYS_XATTR_H
 		if (flags & DIR_SCAN_READ_XATTR) {
-			if (populate_xattr(fs, n))
+			if (populate_xattr(xwr, n))
 				goto fail;
 		}
 #endif
@@ -185,7 +193,8 @@ static int populate_dir(fstree_t *fs, tree_node_t *root, dev_t devstart,
 				goto fail;
 			}
 
-			if (selinux_relable_node(selinux_handle, fs, n, path)) {
+			if (selinux_relable_node(selinux_handle, xwr,
+						 n, path)) {
 				free(path);
 				goto fail;
 			}
@@ -193,6 +202,11 @@ static int populate_dir(fstree_t *fs, tree_node_t *root, dev_t devstart,
 			free(path);
 		}
 
+		if (sqfs_xattr_writer_end(xwr, &n->xattr_idx)) {
+			fputs("error generating xattr index\n", stderr);
+			return -1;
+		}
+
 		free(extra);
 		extra = NULL;
 	}
@@ -204,8 +218,10 @@ static int populate_dir(fstree_t *fs, tree_node_t *root, dev_t devstart,
 			if (pushd(n->name))
 				return -1;
 
-			if (populate_dir(fs, n, devstart, selinux_handle, flags))
+			if (populate_dir(fs, n, devstart, selinux_handle,
+					 xwr, flags)) {
 				return -1;
+			}
 
 			if (popd())
 				return -1;
@@ -222,7 +238,7 @@ fail:
 }
 
 int fstree_from_dir(fstree_t *fs, const char *path, void *selinux_handle,
-		    unsigned int flags)
+		    sqfs_xattr_writer_t *xwr, unsigned int flags)
 {
 	struct stat sb;
 	int ret;
@@ -235,7 +251,8 @@ int fstree_from_dir(fstree_t *fs, const char *path, void *selinux_handle,
 	if (pushd(path))
 		return -1;
 
-	ret = populate_dir(fs, fs->root, sb.st_dev, selinux_handle, flags);
+	ret = populate_dir(fs, fs->root, sb.st_dev, selinux_handle,
+			   xwr, flags);
 
 	if (popd())
 		ret = -1;
diff --git a/mkfs/mkfs.c b/mkfs/mkfs.c
index c3a4e73..2facc51 100644
--- a/mkfs/mkfs.c
+++ b/mkfs/mkfs.c
@@ -89,7 +89,8 @@ static int pack_files(sqfs_data_writer_t *data, fstree_t *fs,
 	return restore_working_dir(opt);
 }
 
-static int relabel_tree_dfs(fstree_t *fs, tree_node_t *n, void *selinux_handle)
+static int relabel_tree_dfs(sqfs_xattr_writer_t *xwr, tree_node_t *n,
+			    void *selinux_handle)
 {
 	char *path = fstree_get_path(n);
 
@@ -98,16 +99,26 @@ static int relabel_tree_dfs(fstree_t *fs, tree_node_t *n, void *selinux_handle)
 		return -1;
 	}
 
-	if (selinux_relable_node(selinux_handle, fs, n, path)) {
+	if (sqfs_xattr_writer_begin(xwr)) {
+		fputs("error recoding xattr key-value pairs\n", stderr);
+		return -1;
+	}
+
+	if (selinux_relable_node(selinux_handle, xwr, n, path)) {
 		free(path);
 		return -1;
 	}
 
+	if (sqfs_xattr_writer_end(xwr, &n->xattr_idx)) {
+		fputs("error generating xattr index\n", stderr);
+		return -1;
+	}
+
 	free(path);
 
 	if (S_ISDIR(n->mode)) {
 		for (n = n->data.dir.children; n != NULL; n = n->next) {
-			if (relabel_tree_dfs(fs, n, selinux_handle))
+			if (relabel_tree_dfs(xwr, n, selinux_handle))
 				return -1;
 		}
 	}
@@ -115,14 +126,15 @@ static int relabel_tree_dfs(fstree_t *fs, tree_node_t *n, void *selinux_handle)
 	return 0;
 }
 
-static int read_fstree(fstree_t *fs, options_t *opt, void *selinux_handle)
+static int read_fstree(fstree_t *fs, options_t *opt, sqfs_xattr_writer_t *xwr,
+		       void *selinux_handle)
 {
 	FILE *fp;
 	int ret;
 
 	if (opt->infile == NULL) {
 		return fstree_from_dir(fs, opt->packdir, selinux_handle,
-				       opt->dirscan_flags);
+				       xwr, opt->dirscan_flags);
 	}
 
 	fp = fopen(opt->infile, "rb");
@@ -144,7 +156,7 @@ static int read_fstree(fstree_t *fs, options_t *opt, void *selinux_handle)
 		return -1;
 
 	if (ret == 0 && selinux_handle != NULL)
-		ret = relabel_tree_dfs(fs, fs->root, selinux_handle);
+		ret = relabel_tree_dfs(xwr, fs->root, selinux_handle);
 
 	return ret;
 }
@@ -155,6 +167,7 @@ int main(int argc, char **argv)
 	sqfs_compressor_config_t cfg;
 	data_writer_stats_t stats;
 	sqfs_data_writer_t *data;
+	sqfs_xattr_writer_t *xwr;
 	sqfs_compressor_t *cmp;
 	sqfs_id_table_t *idtbl;
 	sqfs_file_t *outfile;
@@ -197,10 +210,16 @@ int main(int argc, char **argv)
 			goto out_outfile;
 	}
 
-	if (read_fstree(&fs, &opt, sehnd)) {
+	xwr = sqfs_xattr_writer_create();
+	if (xwr == NULL) {
+		perror("creating Xattr writer");
+		goto out_outfile;
+	}
+
+	if (read_fstree(&fs, &opt, xwr, sehnd)) {
 		if (sehnd != NULL)
 			selinux_close_context_file(sehnd);
-		goto out_outfile;
+		goto out_xwr;
 	}
 
 	if (sehnd != NULL) {
@@ -211,18 +230,16 @@ int main(int argc, char **argv)
 	tree_node_sort_recursive(fs.root);
 
 	if (fstree_gen_inode_table(&fs))
-		goto out_outfile;
+		goto out_xwr;
 
 	fstree_gen_file_list(&fs);
 
 	super.inode_count = fs.inode_tbl_size - 2;
 
-	fstree_xattr_deduplicate(&fs);
-
 	cmp = sqfs_compressor_create(&cfg);
 	if (cmp == NULL) {
 		fputs("Error creating compressor\n", stderr);
-		goto out_outfile;
+		goto out_xwr;
 	}
 
 	ret = cmp->write_options(cmp, outfile);
@@ -257,8 +274,10 @@ int main(int argc, char **argv)
 	if (sqfs_id_table_write(idtbl, outfile, &super, cmp))
 		goto out_data;
 
-	if (write_xattr(outfile, &fs, &super, cmp))
+	if (sqfs_xattr_writer_flush(xwr, outfile, &super, cmp)) {
+		fputs("Error writing xattr table\n", stderr);
 		goto out_data;
+	}
 
 	super.bytes_used = outfile->get_size(outfile);
 
@@ -276,6 +295,8 @@ out_data:
 	sqfs_data_writer_destroy(data);
 out_cmp:
 	cmp->destroy(cmp);
+out_xwr:
+	sqfs_xattr_writer_destroy(xwr);
 out_outfile:
 	outfile->destroy(outfile);
 out_idtbl:
diff --git a/mkfs/mkfs.h b/mkfs/mkfs.h
index 3a139a7..16dcac7 100644
--- a/mkfs/mkfs.h
+++ b/mkfs/mkfs.h
@@ -9,6 +9,7 @@
 
 #include "config.h"
 
+#include "sqfs/xattr_writer.h"
 #include "sqfs/meta_writer.h"
 #include "sqfs/compress.h"
 #include "sqfs/id_table.h"
@@ -69,12 +70,12 @@ enum {
 void process_command_line(options_t *opt, int argc, char **argv);
 
 int fstree_from_dir(fstree_t *fs, const char *path, void *selinux_handle,
-		    unsigned int flags);
+		    sqfs_xattr_writer_t *xwr, unsigned int flags);
 
 
 void *selinux_open_context_file(const char *filename);
 
-int selinux_relable_node(void *sehnd, fstree_t *fs,
+int selinux_relable_node(void *sehnd, sqfs_xattr_writer_t *xwr,
 			 tree_node_t *node, const char *path);
 
 void selinux_close_context_file(void *sehnd);
diff --git a/mkfs/selinux.c b/mkfs/selinux.c
index a4cda71..d5de9a8 100644
--- a/mkfs/selinux.c
+++ b/mkfs/selinux.c
@@ -10,7 +10,7 @@
 #define XATTR_VALUE_SELINUX "system_u:object_r:unlabeled_t:s0"
 
 #ifdef WITH_SELINUX
-int selinux_relable_node(void *sehnd, fstree_t *fs,
+int selinux_relable_node(void *sehnd, sqfs_xattr_writer_t *xwr,
 			 tree_node_t *node, const char *path)
 {
 	char *context = NULL;
@@ -22,8 +22,13 @@ int selinux_relable_node(void *sehnd, fstree_t *fs,
 			goto fail;
 	}
 
-	ret = fstree_add_xattr(fs, node, XATTR_NAME_SELINUX, context);
+	ret = sqfs_xattr_writer_add(xwr, XATTR_NAME_SELINUX,
+				    context, strlen(context));
 	free(context);
+
+	if (ret)
+		fputs("Error relabeling tree node\n", stderr);
+
 	return ret;
 fail:
 	perror("relabeling files");
diff --git a/tar/tar2sqfs.c b/tar/tar2sqfs.c
index 5a404f4..98c0489 100644
--- a/tar/tar2sqfs.c
+++ b/tar/tar2sqfs.c
@@ -6,6 +6,7 @@
  */
 #include "config.h"
 
+#include "sqfs/xattr_writer.h"
 #include "sqfs/compress.h"
 #include "sqfs/id_table.h"
 #include "sqfs/xattr.h"
@@ -109,6 +110,7 @@ static bool dont_skip = false;
 static bool no_xattr = false;
 static bool exportable = false;
 static bool keep_time = false;
+static sqfs_xattr_writer_t *xwr = NULL;
 static data_writer_stats_t stats;
 
 static void process_args(int argc, char **argv)
@@ -278,11 +280,16 @@ static int write_file(tar_header_decoded_t *hdr, file_info_t *fi,
 			    filesize : hdr->record_size);
 }
 
-static int copy_xattr(fstree_t *fs, tree_node_t *node,
+static int copy_xattr(sqfs_xattr_writer_t *xwr, tree_node_t *node,
 		      tar_header_decoded_t *hdr)
 {
 	tar_xattr_t *xattr;
 
+	if (sqfs_xattr_writer_begin(xwr)) {
+		fputs("Error beginning xattr block\n", stderr);
+		return -1;
+	}
+
 	for (xattr = hdr->xattr; xattr != NULL; xattr = xattr->next) {
 		if (!sqfs_has_xattr(xattr->key)) {
 			if (dont_skip) {
@@ -296,8 +303,17 @@ static int copy_xattr(fstree_t *fs, tree_node_t *node,
 			continue;
 		}
 
-		if (fstree_add_xattr(fs, node, xattr->key, xattr->value))
+		if (sqfs_xattr_writer_add(xwr, xattr->key, xattr->value,
+					  strlen(xattr->value))) {
+			fputs("Error converting xattr key-value pair\n",
+			      stderr);
 			return -1;
+		}
+	}
+
+	if (sqfs_xattr_writer_end(xwr, &node->xattr_idx)) {
+		fputs("Error completing xattr block\n", stderr);
+		return -1;
 	}
 
 	return 0;
@@ -320,7 +336,7 @@ static int create_node_and_repack_data(tar_header_decoded_t *hdr, fstree_t *fs,
 		printf("Packing %s\n", hdr->name);
 
 	if (!no_xattr) {
-		if (copy_xattr(fs, node, hdr))
+		if (copy_xattr(xwr, node, hdr))
 			return -1;
 	}
 
@@ -465,6 +481,14 @@ int main(int argc, char **argv)
 	if (idtbl == NULL)
 		goto out_data;
 
+	if (!no_xattr) {
+		xwr = sqfs_xattr_writer_create();
+		if (xwr == NULL) {
+			perror("creating xattr writer");
+			goto out;
+		}
+	}
+
 	if (process_tar_ball(&fs, data))
 		goto out;
 
@@ -477,8 +501,6 @@ int main(int argc, char **argv)
 
 	super.inode_count = fs.inode_tbl_size - 2;
 
-	fstree_xattr_deduplicate(&fs);
-
 	if (sqfs_serialize_fstree(outfile, &super, &fs, cmp, idtbl))
 		goto out;
 
@@ -493,8 +515,10 @@ int main(int argc, char **argv)
 	if (sqfs_id_table_write(idtbl, outfile, &super, cmp))
 		goto out;
 
-	if (write_xattr(outfile, &fs, &super, cmp))
+	if (sqfs_xattr_writer_flush(xwr, outfile, &super, cmp)) {
+		fputs("Error writing xattr table\n", stderr);
 		goto out;
+	}
 
 	super.bytes_used = outfile->get_size(outfile);
 
@@ -509,6 +533,8 @@ int main(int argc, char **argv)
 
 	status = EXIT_SUCCESS;
 out:
+	if (xwr != NULL)
+		sqfs_xattr_writer_destroy(xwr);
 	sqfs_id_table_destroy(idtbl);
 out_data:
 	sqfs_data_writer_destroy(data);