diff options
| -rw-r--r-- | include/fstree.h | 68 | ||||
| -rw-r--r-- | lib/fstree/fstree.c | 144 |
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)); } |