X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=src%2Fdentry.c;h=5ea26d3ecbb9c7285770f1269e1be52996b493b3;hp=ee33d1240a5a066c7b6ae28de4965c275a6fa8e5;hb=c8929560c0771ea60649c962ca17902133d0b582;hpb=7231431086332de22b2556477bcc5fc2c3e4bdcf

diff --git a/src/dentry.c b/src/dentry.c
index ee33d124..5ea26d3e 100644
--- a/src/dentry.c
+++ b/src/dentry.c
@@ -71,16 +71,6 @@ static u64 dentry_correct_length(const struct dentry *dentry)
 	return (dentry_correct_length_unaligned(dentry) + 7) & ~7;
 }
 
-/* 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)
-{
-	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,
@@ -185,28 +175,6 @@ static u64 dentry_total_length(const struct dentry *dentry)
 	return __dentry_total_length(dentry, dentry->length);
 }
 
-/* Transfers file attributes from a `stat' buffer to a WIM "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) & 63));
-	/* 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.
  *
@@ -221,7 +189,7 @@ int inode_to_stbuf(const struct inode *inode, struct lookup_table_entry *lte,
 	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;
@@ -253,33 +221,196 @@ int inode_to_stbuf(const struct inode *inode, struct lookup_table_entry *lte,
 }
 #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;
+		}
+	}
+}
+
+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 directory tree.  It is called
- * on a parent before its children.
+ * 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 (*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
 }
 
 /*
@@ -289,21 +420,96 @@ int for_dentry_in_tree(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
 }
 
 /*
@@ -356,6 +562,19 @@ oom:
 	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.
  *
@@ -365,29 +584,21 @@ oom:
  */
 void calculate_subdir_offsets(struct dentry *dentry, u64 *subdir_offset_p)
 {
-	struct dentry *child, *children;
+	struct rb_node *node;
 
-	children = dentry->d_inode->children;
-	child = 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 != 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 != 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
@@ -399,46 +610,74 @@ void calculate_subdir_offsets(struct dentry *dentry, u64 *subdir_offset_p)
 	}
 }
 
+static int compare_names(const char *name_1, u16 len_1,
+			 const char *name_2, u16 len_2)
+{
+	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 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;
 }
@@ -605,6 +844,11 @@ static struct inode *new_timeless_inode()
 		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);
 	}
@@ -642,8 +886,6 @@ struct dentry *new_dentry(const char *name)
 	if (change_dentry_name(dentry, name) != 0)
 		goto err;
 
-	dentry->next   = dentry;
-	dentry->prev   = dentry;
 	dentry->parent = dentry;
 
 	return dentry;
@@ -712,6 +954,7 @@ void free_inode(struct inode *inode)
 	#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);
@@ -794,9 +1037,8 @@ static int do_free_dentry(struct dentry *dentry, void *__lookup_table)
  */
 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)
@@ -811,25 +1053,34 @@ int increment_dentry_refcnt(struct dentry *dentry, void *ignore)
  * @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.
@@ -838,16 +1089,10 @@ void link_dentry(struct dentry *dentry, struct dentry *parent)
  */
 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
 
@@ -1253,11 +1498,11 @@ out_free_ads_entries:
  * @offset:	Offset of this directory entry in the metadata resource.
  * @dentry:	A `struct dentry' that will be filled in by this function.
  *
- * Return 0 on success or nonzero on failure.  On failure, @dentry have been
- * modified, bu it will be left with no pointers to any allocated buffers.
- * On success, the dentry->length field must be examined.  If zero, this was a
- * special "end of directory" dentry and not a real dentry.  If nonzero, this
- * was a real dentry.
+ * Return 0 on success or nonzero on failure.  On failure, @dentry will have
+ * been modified, but it will not be left with pointers to any allocated
+ * buffers.  On success, the dentry->length field must be examined.  If zero,
+ * this was a 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,
 		u64 offset, struct dentry *dentry)
@@ -1498,7 +1743,7 @@ 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;
@@ -1537,8 +1782,6 @@ int read_dentry_tree(const u8 metadata_resource[], u64 metadata_resource_len,
 		     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;
@@ -1575,16 +1818,7 @@ int read_dentry_tree(const u8 metadata_resource[], u64 metadata_resource_len,
 			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
@@ -1603,14 +1837,6 @@ int read_dentry_tree(const u8 metadata_resource[], u64 metadata_resource_len,
 		 * 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;
 }
 
@@ -1694,12 +1920,26 @@ static u8 *write_dentry(const struct dentry *dentry, u8 *p)
 	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, *children;
-
 	/* Nothing to do if this dentry has no children. */
 	if (parent->subdir_offset == 0)
 		return p;
@@ -1710,25 +1950,14 @@ static u8 *write_dentry_tree_recursive(const struct dentry *parent, u8 *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! */
-	children = parent->d_inode->children;
-	child = children;
-	if (child) {
-		do {
-			p = write_dentry(child, p);
-			child = child->next;
-		} while (child != 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 != children);
-	}
+	for_dentry_in_rbtree(parent->d_inode->children.rb_node,
+			     write_dentry_tree_recursive_cb, &p);
 	return p;
 }