aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDavid Oberhollenzer <david.oberhollenzer@sigma-star.at>2019-05-10 19:59:49 +0200
committerDavid Oberhollenzer <david.oberhollenzer@sigma-star.at>2019-05-19 14:27:34 +0200
commit7097dda129654a5e054c1d64e72bfd189b4964b2 (patch)
treecc5975410a281479e67670ca3c38e483c8ff1a60
parentfe5102f23da752870c9514d5ffe79b7f067f70c4 (diff)
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>
-rw-r--r--include/fstree.h68
-rw-r--r--lib/fstree/fstree.c144
2 files changed, 212 insertions, 0 deletions
diff --git a/include/fstree.h b/include/fstree.h
index f2ed67f..64541a3 100644
--- a/include/fstree.h
+++ b/include/fstree.h
@@ -8,10 +8,43 @@
#include <stdint.h>
#include <stddef.h>
+#include "str_table.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;
+
+/**
+ * @struct tree_xattr_t
+ *
+ * @brief Encapsulates a set of key-value pairs attached to a @ref tree_node_t
+ */
+struct tree_xattr_t {
+ size_t num_attr;
+ size_t max_attr;
+
+ /**
+ * @brief Back reference to the tree node this was created for
+ */
+ tree_node_t *owner;
+
+ /**
+ * @brief linked list pointer of list of attributes in @ref fstree_t
+ */
+ tree_xattr_t *next;
+
+ /**
+ * @brief An array with pairs of key-value tupples
+ *
+ * Each key-value tupple is encoded as (key << 32) | value.
+ */
+ uint64_t ref[];
+};
/**
* @struct file_info_t
@@ -131,6 +164,11 @@ struct tree_node_t {
*/
char *name;
+ /**
+ * @brief A pointer to an extended attribute array or NULL if unused
+ */
+ tree_xattr_t *xattr;
+
uint32_t uid;
uint32_t gid;
uint16_t mode;
@@ -211,7 +249,11 @@ struct fstree_t {
uint32_t default_mtime;
size_t block_size;
+ str_table_t xattr_keys;
+ str_table_t xattr_values;
+
tree_node_t *root;
+ tree_xattr_t *xattr;
};
/**
@@ -293,6 +335,32 @@ tree_node_t *fstree_add_file(fstree_t *fs, const char *path, uint16_t mode,
const char *input);
/**
+ * @brief Add an extended attribute key value pair to a tree node
+ *
+ * @memberof fstree_t
+ *
+ * @param fs A pointer to the fstree object
+ * @param node A pointer to the tree node to attach attributes to
+ * @param key The xattr key with namespace prefix
+ * @param value The xattr value string
+ *
+ * @return Zero on success, -1 on failure (prints error to stderr)
+ */
+int fstree_add_xattr(fstree_t *fs, tree_node_t *node,
+ const char *key, const char *value);
+
+/**
+ * @brief Remove dupliciate xattr listings
+ *
+ * @memberof fstree_t
+ *
+ * If two tree nodes have pointers to distinct @ref tree_xattr_t listings that
+ * turn out to be equivalent, throw one of the two away and make both nodes
+ * point to the same instance.
+ */
+void fstree_xattr_deduplicate(fstree_t *fs);
+
+/**
* @brief Load an fstree from a text file describing it
*
* @memberof fstree_t
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));
}