From 7097dda129654a5e054c1d64e72bfd189b4964b2 Mon Sep 17 00:00:00 2001
From: David Oberhollenzer <david.oberhollenzer@sigma-star.at>
Date: Fri, 10 May 2019 19:59:49 +0200
Subject: Add extended attributes to fstree

We use a str_table_t to generate unique IDs for all unique keys and all
unique values and then use a post processing step to deduplicate xattr
listings.

Signed-off-by: David Oberhollenzer <david.oberhollenzer@sigma-star.at>
---
 lib/fstree/fstree.c | 144 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 144 insertions(+)

(limited to 'lib')

diff --git a/lib/fstree/fstree.c b/lib/fstree/fstree.c
index 8081931..356f65a 100644
--- a/lib/fstree/fstree.c
+++ b/lib/fstree/fstree.c
@@ -171,6 +171,130 @@ tree_node_t *fstree_add_file(fstree_t *fs, const char *path, uint16_t mode,
 	return node;
 }
 
+int fstree_add_xattr(fstree_t *fs, tree_node_t *node,
+		     const char *key, const char *value)
+{
+	tree_xattr_t *xattr, *prev, *it;
+	size_t key_idx, value_idx;
+
+	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(uint32_t)) {
+		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;
+		}
+	}
+
+	if (node->xattr == NULL) {
+		xattr = calloc(1, sizeof(*xattr) + sizeof(uint64_t) * 4);
+		if (xattr == NULL) {
+			perror("adding extended attributes");
+			return -1;
+		}
+
+		xattr->max_attr = 4;
+		xattr->owner = node;
+
+		xattr->next = fs->xattr;
+		fs->xattr = xattr;
+
+		node->xattr = xattr;
+	} else {
+		xattr = node->xattr;
+
+		if (xattr->max_attr == xattr->num_attr) {
+			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;
+			}
+
+			node->xattr = NULL;
+
+			it = realloc(xattr, sizeof(*xattr) +
+				     sizeof(uint64_t) * xattr->max_attr * 2);
+
+			if (it == NULL) {
+				perror("adding extended attributes");
+				free(xattr);
+				return -1;
+			}
+
+			xattr = it;
+			xattr->max_attr *= 2;
+
+			node->xattr = xattr;
+			xattr->next = fs->xattr;
+			fs->xattr = xattr;
+		}
+	}
+
+	xattr->ref[xattr->num_attr]  = (uint64_t)key_idx << 32;
+	xattr->ref[xattr->num_attr] |= (uint64_t)value_idx;
+	xattr->num_attr += 1;
+	return 0;
+}
+
+static int cmp_u64(const void *lhs, const void *rhs)
+{
+	uint64_t l = *((uint64_t *)lhs), r = *((uint64_t *)rhs);
+
+	return l < r ? -1 : (l > r ? 1 : 0);
+}
+
+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->ref, it->num_attr, sizeof(it->ref[0]), cmp_u64);
+
+	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->ref, it->ref,
+				      it->num_attr * sizeof(it->ref[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;
+		}
+	}
+}
+
 int fstree_init(fstree_t *fs, size_t block_size, uint32_t mtime,
 		uint16_t default_mode, uint32_t default_uid,
 		uint32_t default_gid)
@@ -183,11 +307,21 @@ int fstree_init(fstree_t *fs, size_t block_size, uint32_t mtime,
 	fs->default_mtime = mtime;
 	fs->block_size = block_size;
 
+	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 = mknode(NULL, "", 0, 0, S_IFDIR | fs->default_mode,
 			  default_uid, default_gid);
 
 	if (fs->root == NULL) {
 		perror("initializing file system tree");
+		str_table_cleanup(&fs->xattr_values);
+		str_table_cleanup(&fs->xattr_keys);
 		return -1;
 	}
 
@@ -196,6 +330,16 @@ int fstree_init(fstree_t *fs, size_t block_size, uint32_t mtime,
 
 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);
 	memset(fs, 0, sizeof(*fs));
 }
-- 
cgit v1.2.3