#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.
- */
-static bool dentry_has_name(const struct dentry *dentry, const char *name,
- size_t name_len)
-{
- if (dentry->file_name_utf8_len != name_len)
- return false;
- 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);
}
-/* Transfers file attributes from a `stat' buffer to an inode. */
-void stbuf_to_inode(const struct stat *stbuf, struct inode *inode)
-{
- if (S_ISLNK(stbuf->st_mode)) {
- inode->attributes = FILE_ATTRIBUTE_REPARSE_POINT;
- inode->reparse_tag = WIM_IO_REPARSE_TAG_SYMLINK;
- } else if (S_ISDIR(stbuf->st_mode)) {
- inode->attributes = FILE_ATTRIBUTE_DIRECTORY;
- } else {
- inode->attributes = FILE_ATTRIBUTE_NORMAL;
- }
- if (sizeof(ino_t) >= 8)
- inode->ino = (u64)stbuf->st_ino;
- else
- inode->ino = (u64)stbuf->st_ino |
- ((u64)stbuf->st_dev << (sizeof(ino_t) * 8));
- /* Set timestamps */
- inode->creation_time = timespec_to_wim_timestamp(&stbuf->st_mtim);
- inode->last_write_time = timespec_to_wim_timestamp(&stbuf->st_mtim);
- inode->last_access_time = timespec_to_wim_timestamp(&stbuf->st_atim);
-}
-
#ifdef WITH_FUSE
-/* Transfers file attributes from a struct inode to a `stat' buffer.
+/* Transfers file attributes from a struct inode to a `stat' buffer.
*
* The lookup table entry tells us which stream in the inode we are statting.
* For a named data stream, everything returned is the same as the unnamed data
else if (inode_is_directory(inode))
stbuf->st_mode = S_IFDIR | 0755;
else
- stbuf->st_mode = S_IFREG | 0644;
+ stbuf->st_mode = S_IFREG | 0755;
stbuf->st_ino = (ino_t)inode->ino;
stbuf->st_nlink = inode->link_count;
}
#endif
-/*
- * Calls a function on all directory entries in a directory tree. It is called
- * on a parent before its children.
+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;
+ }
+ }
+}
+
+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;
+}
+
+/*#define RECURSIVE_FOR_DENTRY_IN_TREE*/
+
+#ifdef RECURSIVE_FOR_DENTRY_IN_TREE
+static int for_dentry_tree_in_rbtree(struct rb_node *node,
+ int (*visitor)(struct dentry*, void*),
+ void *arg)
+{
+ int ret;
+ if (node) {
+ ret = for_dentry_tree_in_rbtree(node->rb_left, visitor, arg);
+ if (ret != 0)
+ return ret;
+ ret = for_dentry_in_tree(rbnode_dentry(node), visitor, arg);
+ if (ret != 0)
+ return ret;
+ ret = for_dentry_tree_in_rbtree(node->rb_right, visitor, arg);
+ if (ret != 0)
+ return ret;
+ }
+ return 0;
+}
+#endif
+
+/*
+ * Calls a function on all directory entries in a WIM dentry tree. Logically,
+ * this is a pre-order traversal (the function is called on a parent dentry
+ * before its children), but sibling dentries will be visited in order as well.
+ *
+ * In reality, the data structures are more complicated than the above might
+ * suggest because there is a separate red-black tree for each dentry that
+ * contains its direct children.
*/
-int for_dentry_in_tree(struct dentry *root,
+int for_dentry_in_tree(struct dentry *root,
int (*visitor)(struct dentry*, void*), void *arg)
{
+#ifdef RECURSIVE_FOR_DENTRY_IN_TREE
+ int ret = visitor(root, arg);
+ if (ret != 0)
+ return ret;
+ return for_dentry_tree_in_rbtree(root->d_inode->children.rb_node, visitor, arg);
+#else
int ret;
- struct dentry *child;
+ struct list_head main_stack;
+ struct list_head sibling_stack;
+ struct list_head *sibling_stack_bottom;
+ struct dentry *main_dentry;
+ struct rb_node *node;
+ struct list_head *next_sibling;
+ struct dentry *dentry;
ret = visitor(root, arg);
-
if (ret != 0)
return ret;
- child = root->d_inode->children;
+ main_dentry = root;
+ sibling_stack_bottom = &sibling_stack;
+ INIT_LIST_HEAD(&main_stack);
+ INIT_LIST_HEAD(&sibling_stack);
- if (!child)
- return 0;
+ list_add(&root->tmp_list, &main_stack);
+ node = root->d_inode->children.rb_node;
- 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;
+ while (1) {
+ // Prepare for non-recursive in-order traversal of the red-black
+ // tree of this dentry's children
+
+ while (node) {
+ // Push this node to the sibling stack and examine the
+ // left neighbor, if any
+ list_add(&rbnode_dentry(node)->tmp_list, &sibling_stack);
+ node = node->rb_left;
+ }
+
+ next_sibling = sibling_stack.next;
+ if (next_sibling == sibling_stack_bottom) {
+ // Done with all siblings. Pop the main dentry to move
+ // back up one level.
+ main_dentry = container_of(main_stack.next,
+ struct dentry,
+ tmp_list);
+ list_del(&main_dentry->tmp_list);
+
+ if (main_dentry == root)
+ goto out;
+
+ // Restore sibling stack bottom from the previous level
+ sibling_stack_bottom = (void*)main_dentry->parent;
+
+ // Restore the just-popped main dentry's parent
+ main_dentry->parent = container_of(main_stack.next,
+ struct dentry,
+ tmp_list);
+
+ // The next sibling to traverse in the previous level,
+ // in the in-order traversal of the red-black tree, is
+ // the one to the right.
+ node = main_dentry->rb_node.rb_right;
+ } else {
+ // The sibling stack is not empty, so there are more to
+ // go!
+
+ // Pop a sibling from the stack.
+ list_del(next_sibling);
+ dentry = container_of(next_sibling, struct dentry, tmp_list);
+
+ // Visit the sibling.
+ ret = visitor(dentry, arg);
+ if (ret != 0) {
+ // Failed. Restore parent pointers for the
+ // dentries in the main stack
+ list_for_each_entry(dentry, &main_stack, tmp_list) {
+ dentry->parent = container_of(dentry->tmp_list.next,
+ struct dentry,
+ tmp_list);
+ }
+ goto out;
+ }
+
+ // We'd like to recursively visit the dentry tree rooted
+ // at this sibling. To do this, add it to the main
+ // stack, save the bottom of this level's sibling stack
+ // in the dentry->parent field, re-set the bottom of the
+ // sibling stack to be its current height, and set
+ // main_dentry to the sibling so it becomes the parent
+ // dentry in the next iteration through the outer loop.
+ if (inode_has_children(dentry->d_inode)) {
+ list_add(&dentry->tmp_list, &main_stack);
+ dentry->parent = (void*)sibling_stack_bottom;
+ sibling_stack_bottom = sibling_stack.next;
+
+ main_dentry = dentry;
+ node = main_dentry->d_inode->children.rb_node;
+ } else {
+ node = dentry->rb_node.rb_right;
+ }
+ }
+ }
+out:
+ root->parent = root;
+ return ret;
+#endif
}
-/*
+/*
* Like for_dentry_in_tree(), but the visitor function is always called on a
* dentry's children before on itself.
*/
-int for_dentry_in_tree_depth(struct dentry *root,
+int for_dentry_in_tree_depth(struct dentry *root,
int (*visitor)(struct dentry*, void*), void *arg)
{
+#if 1
int ret;
- struct dentry *child;
- struct dentry *next;
+ ret = for_dentry_tree_in_rbtree_depth(root->d_inode->children.rb_node,
+ visitor, arg);
+ if (ret != 0)
+ return ret;
+ return visitor(root, arg);
- child = root->d_inode->children;
- if (child) {
- do {
- next = child->next;
- ret = for_dentry_in_tree_depth(child, visitor, arg);
- if (ret != 0)
+#else
+ int ret;
+ struct list_head main_stack;
+ struct list_head sibling_stack;
+ struct list_head *sibling_stack_bottom;
+ struct dentry *main_dentry;
+ struct rb_node *node;
+ struct list_head *next_sibling;
+ struct dentry *dentry;
+
+ main_dentry = root;
+ sibling_stack_bottom = &sibling_stack;
+ INIT_LIST_HEAD(&main_stack);
+ INIT_LIST_HEAD(&sibling_stack);
+
+ list_add(&main_dentry->tmp_list, &main_stack);
+
+ while (1) {
+ node = main_dentry->d_inode->children.rb_node;
+
+ while (1) {
+ if (node->rb_left) {
+ list_add(&rbnode_dentry(node)->tmp_list, &sibling_stack);
+ node = node->rb_left;
+ continue;
+ }
+ if (node->rb_right) {
+ list_add(&rbnode_dentry(node)->tmp_list, &sibling_stack);
+ node = node->rb_right;
+ continue;
+ }
+ list_add(&rbnode_dentry(node)->tmp_list, &sibling_stack);
+ }
+
+ pop_sibling:
+ next_sibling = sibling_stack.next;
+ if (next_sibling == sibling_stack_bottom) {
+ main_dentry = container_of(main_stack.next,
+ struct dentry,
+ tmp_list);
+ list_del(&main_dentry->tmp_list);
+
+
+ sibling_stack_bottom = (void*)main_dentry->parent;
+
+ if (main_dentry == root) {
+ main_dentry->parent = main_dentry;
+ ret = visitor(dentry, arg);
+ return ret;
+ } else {
+ main_dentry->parent = container_of(main_stack.next,
+ struct dentry,
+ tmp_list);
+ }
+
+ ret = visitor(main_dentry, arg);
+
+ if (ret != 0) {
+ list_del(&root->tmp_list);
+ list_for_each_entry(dentry, &main_stack, tmp_list) {
+ dentry->parent = container_of(dentry->tmp_list.next,
+ struct dentry,
+ tmp_list);
+ }
+ root->parent = root;
return ret;
- child = next;
- } while (child != root->d_inode->children);
+ }
+ goto pop_sibling;
+ } else {
+
+ list_del(next_sibling);
+ dentry = container_of(next_sibling, struct dentry, tmp_list);
+
+
+ list_add(&dentry->tmp_list, &main_stack);
+ dentry->parent = (void*)sibling_stack_bottom;
+ sibling_stack_bottom = sibling_stack.next;
+
+ main_dentry = dentry;
+ }
}
- return visitor(root, arg);
+#endif
}
-/*
+/*
* Calculate the full path of @dentry, based on its parent's full path and on
- * its UTF-8 file name.
+ * its UTF-8 file name.
*/
int calculate_dentry_full_path(struct dentry *dentry, void *ignore)
{
return WIMLIB_ERR_NOMEM;
}
-/*
- * Recursively calculates the subdir offsets for a directory tree.
+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
}
}
-/* 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)
+static int compare_names(const char *name_1, u16 len_1,
+ const char *name_2, u16 len_2)
{
- 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);
+ int result = strncasecmp(name_1, name_2, min(len_1, len_2));
+ if (result) {
+ return result;
+ } else {
+ return (int)len_1 - (int)len_2;
}
+}
+
+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 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
} else {
hash = inode_stream_hash(inode, 0);
if (hash) {
- printf("Hash = 0x");
+ printf("Hash = 0x");
print_hash(hash);
putchar('\n');
putchar('\n');
inode->ads_entries[i].stream_name_len);
hash = inode_stream_hash(inode, i + 1);
if (hash) {
- printf("Hash = 0x");
+ printf("Hash = 0x");
print_hash(hash);
putchar('\n');
}
static struct inode *new_timeless_inode()
{
struct inode *inode = CALLOC(1, sizeof(struct inode));
- if (!inode)
- return NULL;
- inode->security_id = -1;
- inode->link_count = 1;
- INIT_LIST_HEAD(&inode->dentry_list);
+ if (inode) {
+ inode->security_id = -1;
+ inode->link_count = 1;
+ #ifdef WITH_FUSE
+ inode->next_stream_id = 1;
+ if (pthread_mutex_init(&inode->i_mutex, NULL) != 0) {
+ ERROR_WITH_ERRNO("Error initializing mutex");
+ FREE(inode);
+ return NULL;
+ }
+ #endif
+ INIT_LIST_HEAD(&inode->dentry_list);
+ }
return inode;
}
static struct inode *new_inode()
{
struct inode *inode = new_timeless_inode();
- if (!inode)
- return NULL;
- u64 now = get_wim_timestamp();
- inode->creation_time = now;
- inode->last_access_time = now;
- inode->last_write_time = now;
+ if (inode) {
+ u64 now = get_wim_timestamp();
+ inode->creation_time = now;
+ inode->last_access_time = now;
+ inode->last_write_time = now;
+ }
return inode;
}
-/*
+/*
* Creates an unlinked directory entry.
*
* @name: The UTF-8 filename of the new dentry.
struct dentry *new_dentry(const char *name)
{
struct dentry *dentry;
-
+
dentry = MALLOC(sizeof(struct dentry));
if (!dentry)
goto err;
if (change_dentry_name(dentry, name) != 0)
goto err;
- dentry->next = dentry;
- dentry->prev = dentry;
dentry->parent = dentry;
return dentry;
#ifdef WITH_FUSE
wimlib_assert(inode->num_opened_fds == 0);
FREE(inode->fds);
+ pthread_mutex_destroy(&inode->i_mutex);
#endif
+ FREE(inode->extracted_file);
FREE(inode);
}
}
#endif
{
free_inode(inode);
- inode = NULL;
}
}
}
-/* Frees a WIM dentry.
+/* Frees a WIM dentry.
*
* The inode is freed only if its link count is decremented to 0.
*/
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);
FREE(dentry->full_path_utf8);
- put_inode(dentry->d_inode);
+ if (dentry->d_inode)
+ put_inode(dentry->d_inode);
FREE(dentry);
}
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);
}
-/*
+/*
* This function is passed as an argument to for_dentry_in_tree_depth() in order
* to free a directory tree. __args is a pointer to a `struct free_dentry_args'.
*/
return 0;
}
-/*
+/*
* Unlinks and frees a dentry tree.
*
* @root: The root of the tree.
*/
void free_dentry_tree(struct dentry *root, struct lookup_table *lookup_table)
{
- if (!root || !root->parent)
- return;
- for_dentry_in_tree_depth(root, do_free_dentry, lookup_table);
+ if (root)
+ for_dentry_in_tree_depth(root, do_free_dentry, lookup_table);
}
int increment_dentry_refcnt(struct dentry *dentry, void *ignore)
return 0;
}
-/*
+/*
* Links a dentry into the directory tree.
*
* @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.
+/*
+ * Unlink a dentry from the directory tree.
*
* Note: This merely removes it from the in-memory tree structure.
*/
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
-/* Parameters for calculate_dentry_statistics(). */
-struct image_statistics {
- struct lookup_table *lookup_table;
- u64 *dir_count;
- u64 *file_count;
- u64 *total_bytes;
- u64 *hard_link_bytes;
-};
-
-static int calculate_dentry_statistics(struct dentry *dentry, void *arg)
-{
- struct image_statistics *stats;
- struct lookup_table_entry *lte;
-
- stats = arg;
-
- if (dentry_is_directory(dentry) && !dentry_is_root(dentry))
- ++*stats->dir_count;
- else
- ++*stats->file_count;
-
- for (unsigned i = 0; i <= dentry->d_inode->num_ads; i++) {
- lte = inode_stream_lte(dentry->d_inode, i, stats->lookup_table);
- if (lte) {
- *stats->total_bytes += wim_resource_size(lte);
- if (++lte->out_refcnt == 1)
- *stats->hard_link_bytes += wim_resource_size(lte);
- }
- }
- return 0;
-}
-
-/* Calculates some statistics about a dentry tree. */
-void calculate_dir_tree_statistics(struct dentry *root, struct lookup_table *table,
- u64 *dir_count_ret, u64 *file_count_ret,
- u64 *total_bytes_ret,
- u64 *hard_link_bytes_ret)
-{
- struct image_statistics stats;
- *dir_count_ret = 0;
- *file_count_ret = 0;
- *total_bytes_ret = 0;
- *hard_link_bytes_ret = 0;
- stats.lookup_table = table;
- stats.dir_count = dir_count_ret;
- stats.file_count = file_count_ret;
- stats.total_bytes = total_bytes_ret;
- stats.hard_link_bytes = hard_link_bytes_ret;
- for_lookup_table_entry(table, lte_zero_out_refcnt, NULL);
- for_dentry_in_tree(root, calculate_dentry_statistics, &stats);
-}
-
static inline struct dentry *inode_first_dentry(struct inode *inode)
{
wimlib_assert(inode->dentry_list.next != &inode->dentry_list);
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);
num_unnamed_streams++;
}
if (num_unnamed_streams > 1) {
- ERROR("Dentry `%s' has multiple (%u) un-named streams",
+ ERROR("Dentry `%s' has multiple (%u) un-named streams",
first_dentry->full_path_utf8, num_unnamed_streams);
goto out;
}
/* 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;
}
#endif
#if defined(WITH_FUSE) || defined(WITH_NTFS_3G)
-/*
+/*
* Add an alternate stream entry to an inode and return a pointer to it, or NULL
* if memory could not be allocated.
*/
struct ads_entry *ads_entries;
struct ads_entry *new_entry;
- DEBUG("Add alternate data stream `%s'", stream_name);
+ DEBUG("Add alternate data stream \"%s\"", stream_name);
if (inode->num_ads >= 0xfffe) {
ERROR("Too many alternate data streams in one inode!");
struct ads_entry *ads_entry;
struct lookup_table_entry *lte;
+ wimlib_assert(idx < inode->num_ads);
+ wimlib_assert(inode->resolved);
+
ads_entry = &inode->ads_entries[idx];
- wimlib_assert(ads_entry);
- wimlib_assert(inode->resolved);
+ DEBUG("Remove alternate data stream \"%s\"", ads_entry->stream_name_utf8);
lte = ads_entry->lte;
-
if (lte)
lte_decrement_refcnt(lte, lookup_table);
destroy_ads_entry(ads_entry);
- wimlib_assert(inode->num_ads);
memcpy(&inode->ads_entries[idx],
&inode->ads_entries[idx + 1],
(inode->num_ads - idx - 1) * sizeof(inode->ads_entries[0]));
-/*
+/*
* Reads the alternate data stream entries for a dentry.
*
* @p: Pointer to buffer that starts with the first alternate stream entry.
*
* struct ads_entry_on_disk {
* u64 length; // Length of the entry, in bytes. This includes
- * all fields (including the stream name and
+ * all fields (including the stream name and
* null terminator if present, AND the padding!).
* u64 reserved; // Seems to be unused
* u8 hash[20]; // SHA1 message digest of the uncompressed stream
return ret;
}
-/*
+/*
* Reads a directory entry, including all alternate data stream entries that
* follow it, from the WIM image's metadata resource.
*
* special "end of directory" dentry and not a real dentry. If nonzero, this
* was a real dentry.
*/
-int read_dentry(const u8 metadata_resource[], u64 metadata_resource_len,
+int read_dentry(const u8 metadata_resource[], u64 metadata_resource_len,
u64 offset, struct dentry *dentry)
{
const u8 *p;
p = get_u64(p, &inode->last_write_time);
p = get_bytes(p, SHA1_HASH_SIZE, inode->hash);
-
+
/*
* I don't know what's going on here. It seems like M$ screwed up the
* reparse points, then put the fields in the same place and didn't
/* By the way, the reparse_reserved field does not actually exist (at
* least when the file is not a reparse point) */
-
+
p = get_u16(p, &inode->num_ads);
p = get_u16(p, &short_name_len);
p = get_u16(p, &file_name_len);
/* We now know the length of the file name and short name. Make sure
- * the length of the dentry is large enough to actually hold them.
+ * the length of the dentry is large enough to actually hold them.
*
* The calculated length here is unaligned to allow for the possibility
* that the dentry->length names an unaligned length, although this
if (dentry->length < calculated_size) {
ERROR("Unexpected end of directory entry! (Expected "
"at least %"PRIu64" bytes, got %"PRIu64" bytes. "
- "short_name_len = %hu, file_name_len = %hu)",
+ "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);
/* Convert filename to UTF-8. */
- file_name_utf8 = utf16_to_utf8(file_name, file_name_len,
+ file_name_utf8 = utf16_to_utf8(file_name, file_name_len,
&file_name_utf8_len);
if (!file_name_utf8) {
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;
}
- /*
+ /*
* Read the alternate data streams, if present. dentry->num_ads tells
* us how many they are, and they will directly follow the dentry
* on-disk.
* 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;
struct dentry *dentry)
{
u64 cur_offset = dentry->subdir_offset;
- struct dentry *prev_child = NULL;
- struct dentry *first_child = NULL;
struct dentry *child;
struct dentry cur_child;
int ret;
- /*
+ /*
* If @dentry has no child dentries, nothing more needs to be done for
* this branch. This is the case for regular files, symbolic links, and
* *possibly* empty directories (although an empty directory may also
while (1) {
/* Read next child of @dentry into @cur_child. */
- ret = read_dentry(metadata_resource, metadata_resource_len,
+ ret = read_dentry(metadata_resource, metadata_resource_len,
cur_offset, &cur_child);
if (ret != 0)
break;
break;
}
memcpy(child, &cur_child, sizeof(struct dentry));
-
- if (prev_child) {
- prev_child->next = child;
- child->prev = prev_child;
- } else {
- first_child = child;
- }
-
- child->parent = dentry;
- prev_child = child;
+ dentry_add_child(dentry, child);
inode_add_dentry(child, child->d_inode);
/* If there are children of this child, call this procedure
* recursively. */
if (child->subdir_offset != 0) {
- ret = read_dentry_tree(metadata_resource,
+ ret = read_dentry_tree(metadata_resource,
metadata_resource_len, child);
if (ret != 0)
break;
* 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;
}
-/*
+/*
* Writes a WIM dentry to an output buffer.
*
* @dentry: The dentry structure.
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;
- /* Write child dentries and end-of-directory entry.
+ /* Write child dentries and end-of-directory entry.
*
* Note: we need to write all of this dentry's children before
* 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