#include "wimlib_internal.h"
+/* Calculates the unaligned length, in bytes, of an on-disk WIM dentry that has
+ * a file name and short name that take the specified numbers of bytes. This
+ * excludes any alternate data stream entries that may follow the dentry. */
static u64 __dentry_correct_length_unaligned(u16 file_name_len,
u16 short_name_len)
{
return length;
}
+/* Calculates the unaligned length, in bytes, of an on-disk WIM dentry, based on
+ * the file name length and short name length. Note that dentry->length is
+ * ignored; also, this excludes any alternate data stream entries that may
+ * follow the dentry. */
static u64 dentry_correct_length_unaligned(const struct dentry *dentry)
{
return __dentry_correct_length_unaligned(dentry->file_name_len,
dentry->short_name_len);
}
-/* Return the "correct" value to write in the length field of the dentry, based
- * on the file name length and short name length */
+/* Return the "correct" value to write in the length field of a WIM dentry,
+ * based on the file name length and short name length. */
static u64 dentry_correct_length(const struct dentry *dentry)
{
return (dentry_correct_length_unaligned(dentry) + 7) & ~7;
}
-/*
- * Returns true if @dentry has the UTF-8 file name @name that has length
- * @name_len.
- */
+/* Return %true iff @dentry has the UTF-8 file name @name that has length
+ * @name_len bytes. */
static bool dentry_has_name(const struct dentry *dentry, const char *name,
size_t name_len)
{
return memcmp(dentry->file_name_utf8, name, name_len) == 0;
}
+/* Return %true iff the alternate data stream entry @entry has the UTF-8 stream
+ * name @name that has length @name_len bytes. */
static inline bool ads_entry_has_name(const struct ads_entry *entry,
const char *name, size_t name_len)
{
return (length + 7) & ~7;
}
+/* Calculate the aligned *total* length of an on-disk WIM dentry. This includes
+ * all alternate data streams. */
u64 dentry_correct_total_length(const struct dentry *dentry)
{
return __dentry_total_length(dentry,
dentry_correct_length_unaligned(dentry));
}
-/* Real length of a dentry, including the alternate data stream entries, which
- * are not included in the dentry->length field... */
+/* Like dentry_correct_total_length(), but use the existing dentry->length field
+ * instead of calculating its "correct" value. */
static u64 dentry_total_length(const struct dentry *dentry)
{
return __dentry_total_length(dentry, dentry->length);
}
#endif
+int for_dentry_in_rbtree(struct rb_node *root,
+ int (*visitor)(struct dentry *, void *),
+ void *arg)
+{
+ int ret;
+ struct rb_node *node = root;
+ LIST_HEAD(stack);
+ while (true) {
+ if (node) {
+ list_add(&rbnode_dentry(node)->tmp_list, &stack);
+ node = node->rb_left;
+ } else {
+ struct list_head *next;
+ struct dentry *dentry;
+
+ next = stack.next;
+ if (next == &stack)
+ return 0;
+ dentry = container_of(next, struct dentry, tmp_list);
+ list_del(next);
+ ret = visitor(dentry, arg);
+ if (ret != 0)
+ return ret;
+ node = dentry->rb_node.rb_right;
+ }
+ }
+}
+
+int for_dentry_tree_in_rbtree(struct rb_node *root,
+ int (*visitor)(struct dentry*, void*),
+ void *arg)
+{
+ int ret;
+ struct rb_node *node = root;
+ LIST_HEAD(stack);
+ while (true) {
+ if (node) {
+ list_add(&rbnode_dentry(node)->tmp_list, &stack);
+ node = node->rb_left;
+ } else {
+ struct list_head *next;
+ struct dentry *dentry;
+
+ next = stack.next;
+ if (next == &stack)
+ return 0;
+ dentry = container_of(next, struct dentry, tmp_list);
+ list_del(next);
+ ret = for_dentry_in_tree(dentry, visitor, arg);
+ if (ret != 0)
+ return ret;
+ node = dentry->rb_node.rb_right;
+ }
+ }
+}
+
+static int for_dentry_tree_in_rbtree_depth(struct rb_node *node,
+ int (*visitor)(struct dentry*, void*),
+ void *arg)
+{
+ int ret;
+ if (node) {
+ ret = for_dentry_tree_in_rbtree_depth(node->rb_left,
+ visitor, arg);
+ if (ret != 0)
+ return ret;
+ ret = for_dentry_tree_in_rbtree_depth(node->rb_right,
+ visitor, arg);
+ if (ret != 0)
+ return ret;
+ ret = for_dentry_in_tree_depth(rbnode_dentry(node), visitor, arg);
+ if (ret != 0)
+ return ret;
+ }
+ return 0;
+}
+
/*
* Calls a function on all directory entries in a directory tree. It is called
* on a parent before its children.
int for_dentry_in_tree(struct dentry *root,
int (*visitor)(struct dentry*, void*), void *arg)
{
- int ret;
- struct dentry *child;
-
- ret = visitor(root, arg);
-
+ int ret = visitor(root, arg);
if (ret != 0)
return ret;
- child = root->d_inode->children;
-
- if (!child)
- return 0;
-
- do {
- ret = for_dentry_in_tree(child, visitor, arg);
- if (ret != 0)
- return ret;
- child = child->next;
- } while (child != root->d_inode->children);
- return 0;
+ return for_dentry_tree_in_rbtree(root->d_inode->children.rb_node,
+ visitor, arg);
}
/*
int for_dentry_in_tree_depth(struct dentry *root,
int (*visitor)(struct dentry*, void*), void *arg)
{
- int ret;
- struct dentry *child;
- struct dentry *next;
- child = root->d_inode->children;
- if (child) {
- do {
- next = child->next;
- ret = for_dentry_in_tree_depth(child, visitor, arg);
- if (ret != 0)
- return ret;
- child = next;
- } while (child != root->d_inode->children);
- }
+ int ret = for_dentry_tree_in_rbtree_depth(root->d_inode->children.rb_node,
+ visitor, arg);
+ if (ret != 0)
+ return ret;
return visitor(root, arg);
}
return WIMLIB_ERR_NOMEM;
}
+static int increment_subdir_offset(struct dentry *dentry, void *subdir_offset_p)
+{
+ *(u64*)subdir_offset_p += dentry_correct_total_length(dentry);
+ return 0;
+}
+
+static int call_calculate_subdir_offsets(struct dentry *dentry,
+ void *subdir_offset_p)
+{
+ calculate_subdir_offsets(dentry, subdir_offset_p);
+ return 0;
+}
+
/*
* Recursively calculates the subdir offsets for a directory tree.
*
* @dentry: The root of the directory tree.
* @subdir_offset_p: The current subdirectory offset; i.e., the subdirectory
- * offset for @dentry.
+ * offset for @dentry.
*/
void calculate_subdir_offsets(struct dentry *dentry, u64 *subdir_offset_p)
{
- struct dentry *child;
+ struct rb_node *node;
- child = dentry->d_inode->children;
dentry->subdir_offset = *subdir_offset_p;
-
- if (child) {
+ node = dentry->d_inode->children.rb_node;
+ if (node) {
/* Advance the subdir offset by the amount of space the children
* of this dentry take up. */
- do {
- *subdir_offset_p += dentry_correct_total_length(child);
- child = child->next;
- } while (child != dentry->d_inode->children);
+ for_dentry_in_rbtree(node, increment_subdir_offset, subdir_offset_p);
/* End-of-directory dentry on disk. */
*subdir_offset_p += 8;
/* Recursively call calculate_subdir_offsets() on all the
* children. */
- do {
- calculate_subdir_offsets(child, subdir_offset_p);
- child = child->next;
- } while (child != dentry->d_inode->children);
+ for_dentry_in_rbtree(node, call_calculate_subdir_offsets, subdir_offset_p);
} else {
/* On disk, childless directories have a valid subdir_offset
* that points to an 8-byte end-of-directory dentry. Regular
}
}
+static int compare_names(const char *name_1, size_t len_1,
+ const char *name_2, size_t len_2)
+{
+ if (len_1 < len_2)
+ return -1;
+ else if (len_1 > len_2)
+ return 1;
+ else
+ return memcmp(name_1, name_2, len_1);
+}
+
+static int dentry_compare_names(const struct dentry *d1, const struct dentry *d2)
+{
+ return compare_names(d1->file_name_utf8, d1->file_name_utf8_len,
+ d2->file_name_utf8, d2->file_name_utf8_len);
+}
+
+
+static struct dentry *
+get_rbtree_child_with_name(const struct rb_node *node,
+ const char *name, size_t name_len)
+{
+ do {
+ struct dentry *child = rbnode_dentry(node);
+ int result = compare_names(name, name_len,
+ child->file_name_utf8,
+ child->file_name_utf8_len);
+ if (result < 0)
+ node = node->rb_left;
+ else if (result > 0)
+ node = node->rb_right;
+ else
+ return child;
+ } while (node);
+ return NULL;
+}
+
/* Returns the child of @dentry that has the file name @name.
* Returns NULL if no child has the name. */
struct dentry *get_dentry_child_with_name(const struct dentry *dentry,
const char *name)
{
- struct dentry *child;
- size_t name_len;
-
- child = dentry->d_inode->children;
- if (child) {
- name_len = strlen(name);
- do {
- if (dentry_has_name(child, name, name_len))
- return child;
- child = child->next;
- } while (child != dentry->d_inode->children);
- }
- return NULL;
+ struct rb_node *node = dentry->d_inode->children.rb_node;
+ if (node)
+ return get_rbtree_child_with_name(node, name, strlen(name));
+ else
+ return NULL;
}
/* Retrieves the dentry that has the UTF-8 @path relative to the dentry
- * @cur_dir. Returns NULL if no dentry having the path is found. */
-static struct dentry *get_dentry_relative_path(struct dentry *cur_dir,
+ * @cur_dentry. Returns NULL if no dentry having the path is found. */
+static struct dentry *get_dentry_relative_path(struct dentry *cur_dentry,
const char *path)
{
- struct dentry *child;
- size_t base_len;
- const char *new_path;
-
if (*path == '\0')
- return cur_dir;
+ return cur_dentry;
+
+ struct rb_node *node = cur_dentry->d_inode->children.rb_node;
+ if (node) {
+ struct dentry *child;
+ size_t base_len;
+ const char *new_path;
- child = cur_dir->d_inode->children;
- if (child) {
new_path = path_next_part(path, &base_len);
- do {
- if (dentry_has_name(child, path, base_len))
- return get_dentry_relative_path(child, new_path);
- child = child->next;
- } while (child != cur_dir->d_inode->children);
+
+ child = get_rbtree_child_with_name(node, path, base_len);
+ if (child)
+ return get_dentry_relative_path(child, new_path);
}
return NULL;
}
{
struct dentry *dentry;
dentry = get_dentry(w, path);
- if (!dentry)
- return NULL;
- else
+ if (dentry)
return dentry->d_inode;
+ else
+ return NULL;
}
/* Returns the dentry that corresponds to the parent directory of @path, or NULL
if (change_dentry_name(dentry, name) != 0)
goto err;
- dentry->next = dentry;
- dentry->prev = dentry;
dentry->parent = dentry;
return dentry;
*/
void free_dentry(struct dentry *dentry)
{
- wimlib_assert(dentry);
- struct inode *inode;
-
+ wimlib_assert(dentry != NULL);
FREE(dentry->file_name);
FREE(dentry->file_name_utf8);
FREE(dentry->short_name);
void put_dentry(struct dentry *dentry)
{
- wimlib_assert(dentry);
- wimlib_assert(dentry->refcnt);
+ wimlib_assert(dentry != NULL);
+ wimlib_assert(dentry->refcnt != 0);
if (--dentry->refcnt == 0)
free_dentry(dentry);
* @dentry: The dentry to link.
* @parent: The dentry that will be the parent of @dentry.
*/
-void link_dentry(struct dentry *dentry, struct dentry *parent)
+bool dentry_add_child(struct dentry * restrict parent,
+ struct dentry * restrict child)
{
wimlib_assert(dentry_is_directory(parent));
- dentry->parent = parent;
- if (parent->d_inode->children) {
- /* Not an only child; link to siblings. */
- dentry->next = parent->d_inode->children;
- dentry->prev = parent->d_inode->children->prev;
- dentry->next->prev = dentry;
- dentry->prev->next = dentry;
- } else {
- /* Only child; link to parent. */
- parent->d_inode->children = dentry;
- dentry->next = dentry;
- dentry->prev = dentry;
+
+ struct rb_root *root = &parent->d_inode->children;
+ struct rb_node **new = &(root->rb_node);
+ struct rb_node *rb_parent = NULL;
+
+ while (*new) {
+ struct dentry *this = rbnode_dentry(*new);
+ int result = dentry_compare_names(child, this);
+
+ rb_parent = *new;
+
+ if (result < 0)
+ new = &((*new)->rb_left);
+ else if (result > 0)
+ new = &((*new)->rb_right);
+ else
+ return false;
}
+ child->parent = parent;
+ rb_link_node(&child->rb_node, rb_parent, new);
+ rb_insert_color(&child->rb_node, root);
+ return true;
}
-
#ifdef WITH_FUSE
/*
* Unlink a dentry from the directory tree.
*/
void unlink_dentry(struct dentry *dentry)
{
- if (dentry_is_root(dentry))
+ struct dentry *parent = dentry->parent;
+ if (parent == dentry)
return;
- if (dentry_is_only_child(dentry)) {
- dentry->parent->d_inode->children = NULL;
- } else {
- if (dentry_is_first_sibling(dentry))
- dentry->parent->d_inode->children = dentry->next;
- dentry->next->prev = dentry->prev;
- dentry->prev->next = dentry->next;
- }
+ rb_erase(&dentry->rb_node, &parent->d_inode->children);
}
#endif
WARNING("The following lookup table entry "
"has a reference count of %u, but",
lte->refcnt);
- WARNING("We found %zu references to it",
+ WARNING("We found %u references to it",
lte->real_refcnt);
WARNING("(One dentry referencing it is at `%s')",
first_dentry->full_path_utf8);
/* Run some miscellaneous verifications on a WIM dentry */
int verify_dentry(struct dentry *dentry, void *wim)
{
- const WIMStruct *w = wim;
- const struct inode *inode = dentry->d_inode;
- int ret = WIMLIB_ERR_INVALID_DENTRY;
+ int ret;
if (!dentry->d_inode->verified) {
- ret = verify_inode(dentry->d_inode, w);
+ ret = verify_inode(dentry->d_inode, wim);
if (ret != 0)
- goto out;
+ return ret;
}
/* Cannot have a short name but no long name */
if (dentry->short_name_len && !dentry->file_name_len) {
ERROR("Dentry `%s' has a short name but no long name",
dentry->full_path_utf8);
- goto out;
+ return WIMLIB_ERR_INVALID_DENTRY;
}
/* Make sure root dentry is unnamed */
if (dentry->file_name_len) {
ERROR("The root dentry is named `%s', but it must "
"be unnamed", dentry->file_name_utf8);
- goto out;
+ return WIMLIB_ERR_INVALID_DENTRY;
}
}
}
#endif
- ret = 0;
-out:
- return ret;
+ return 0;
}
"short_name_len = %hu, file_name_len = %hu)",
calculated_size, dentry->length,
short_name_len, file_name_len);
- return WIMLIB_ERR_INVALID_DENTRY;
+ ret = WIMLIB_ERR_INVALID_DENTRY;
+ goto out_free_inode;
}
/* Read the filename if present. Note: if the filename is empty, there
if (!file_name) {
ERROR("Failed to allocate %hu bytes for dentry file name",
file_name_len);
- return WIMLIB_ERR_NOMEM;
+ ret = WIMLIB_ERR_NOMEM;
+ goto out_free_inode;
}
p = get_bytes(p, file_name_len, file_name);
p = get_bytes(p, short_name_len, short_name);
if (*(u16*)p)
- WARNING("Expected two zero bytes following the file name "
+ WARNING("Expected two zero bytes following the short name of "
"`%s', but found non-zero bytes", file_name_utf8);
p += 2;
}
* included in the dentry->length field for some reason.
*/
if (inode->num_ads != 0) {
- if (calculated_size > metadata_resource_len - offset) {
- ERROR("Not enough space in metadata resource for "
- "alternate stream entries");
- ret = WIMLIB_ERR_INVALID_DENTRY;
- goto out_free_short_name;
+
+ /* Trying different lengths is just a hack to make sure we have
+ * a chance of reading the ADS entries correctly despite the
+ * poor documentation. */
+
+ if (calculated_size != dentry->length) {
+ WARNING("Trying calculated dentry length (%"PRIu64") "
+ "instead of dentry->length field (%"PRIu64") "
+ "to read ADS entries",
+ calculated_size, dentry->length);
}
- ret = read_ads_entries(&metadata_resource[offset + calculated_size],
- inode,
- metadata_resource_len - offset - calculated_size);
- if (ret != 0)
- goto out_free_short_name;
+ u64 lengths_to_try[3] = {calculated_size,
+ (dentry->length + 7) & ~7,
+ dentry->length};
+ ret = WIMLIB_ERR_INVALID_DENTRY;
+ for (size_t i = 0; i < ARRAY_LEN(lengths_to_try); i++) {
+ if (lengths_to_try[i] > metadata_resource_len - offset)
+ continue;
+ ret = read_ads_entries(&metadata_resource[offset + lengths_to_try[i]],
+ inode,
+ metadata_resource_len - offset - lengths_to_try[i]);
+ if (ret == 0)
+ goto out;
+ }
+ ERROR("Failed to read alternate data stream "
+ "entries of `%s'", dentry->file_name_utf8);
+ goto out_free_short_name;
}
+out:
/* We've read all the data for this dentry. Set the names and their
* lengths, and we've done. */
- dentry->d_inode = inode;
+ dentry->d_inode = inode;
dentry->file_name = file_name;
dentry->file_name_utf8 = file_name_utf8;
dentry->short_name = short_name;
}
memcpy(child, &cur_child, sizeof(struct dentry));
- if (prev_child) {
- prev_child->next = child;
- child->prev = prev_child;
- } else {
- first_child = child;
- }
+ dentry_add_child(dentry, child);
- child->parent = dentry;
- prev_child = child;
inode_add_dentry(child, child->d_inode);
/* If there are children of this child, call this procedure
* entries. */
cur_offset += dentry_total_length(child);
}
-
- /* Link last child to first one, and set parent's children pointer to
- * the first child. */
- if (prev_child) {
- prev_child->next = first_child;
- first_child->prev = prev_child;
- }
- dentry->d_inode->children = first_child;
return ret;
}
return p;
}
+static int write_dentry_cb(struct dentry *dentry, void *_p)
+{
+ u8 **p = _p;
+ *p = write_dentry(dentry, *p);
+ return 0;
+}
+
+static u8 *write_dentry_tree_recursive(const struct dentry *parent, u8 *p);
+
+static int write_dentry_tree_recursive_cb(struct dentry *dentry, void *_p)
+{
+ u8 **p = _p;
+ *p = write_dentry_tree_recursive(dentry, *p);
+ return 0;
+}
+
/* Recursive function that writes a dentry tree rooted at @parent, not including
* @parent itself, which has already been written. */
static u8 *write_dentry_tree_recursive(const struct dentry *parent, u8 *p)
{
- const struct dentry *child;
-
/* Nothing to do if this dentry has no children. */
if (parent->subdir_offset == 0)
return p;
* recursively writing the directory trees rooted at each of the child
* dentries, since the on-disk dentries for a dentry's children are
* always located at consecutive positions in the metadata resource! */
- child = parent->d_inode->children;
- if (child) {
- do {
- p = write_dentry(child, p);
- child = child->next;
- } while (child != parent->d_inode->children);
- }
+ for_dentry_in_rbtree(parent->d_inode->children.rb_node, write_dentry_cb, &p);
/* write end of directory entry */
p = put_u64(p, 0);
/* Recurse on children. */
- if (child) {
- do {
- p = write_dentry_tree_recursive(child, p);
- child = child->next;
- } while (child != parent->d_inode->children);
- }
+ for_dentry_in_rbtree(parent->d_inode->children.rb_node,
+ write_dentry_tree_recursive_cb, &p);
return p;
}
*/
u8 *write_dentry_tree(const struct dentry *root, u8 *p)
{
+ DEBUG("Writing dentry tree.");
wimlib_assert(dentry_is_root(root));
/* If we're the root dentry, we have no parent that already
git://wimlib.net / wimlib / blobdiff