Skip to contentSkip to conversation

ocfs2: Directory indexing support

RFC PATCH New Mark Fasheh 2 participants 10 messages Nov 13, 2008 OCFS2

lore
Share & tools
lore

Mark Fasheh

author
#0 lore raw

cover ocfs2: Directory indexing support

The following patches implement indexed directory support in Ocfs2, mostly according to the design doc I wrote up a while ago:

http://oss.oracle.com/osswiki/OCFS2/DesignDocs/IndexedDirectories

The patches have been rebased on top of the current merge_window branch in Ocfs2.

Testing so far has mostly been kernel tree builds and unit tests from the ocfs2-test project. Everything seems pretty stable, but I'm sure we could pound on it some more. I have yet to test this particular set of patches - rebasing took longer than I thought it would, and I wanted to get these out to the list for early review :) I will report back on testing results, as well as performance numbers in the next couple days.

Very basic ocfs2-tools patches will also follow in the next couple days or so. This will mostly be mkfs and debugfs support. I think it might be best to build the libocfs2 support on top of whatever patches we have for extended attributes as the tree code will have to change for that.

Future Improvements:

We can optimize away the index reads for "medium" sized directories, if the number of blocks in the unindexed tree is less than the minimum number of reads required to read the index. Taking contiguousness into account might yield even better results.

Open questions:

Should we just drop the signature in ocfs2_dir_block_trailer? I can't help but feel that it might have limited usefulness as it's not at the front of the block (like the rest of our signatures) and that the nature of a dirent block might be that we can't trust the existence of the signature to actually mean there's a valid ocfs2_dir_block_trailer there. The answer is probably still to keep the signature, but I thought I'd throw this out there.

Is it worth storing index (ocfs2_dx_entry) records inline inside of ocfs2_dx_root_block and only growing out to a tree when we exhaust the available space? Running the math, we could store between 18 (512 byte blocks) and 242 (4k blocksize) records in the space occupied by the extent list.

In order to keep the code simple, I've gone with a single linked-list for the free dirent block search. There might be situations though, where this performs poorly. My plan is to version the free dirent block list so that we can 'upgrade' it (maybe to multiple lists) at a later point. Old versions would fall back to the less optimized unindexed leaf search. That way the upgrade would be seamless to the user.

	--Mark

--
Mark Fasheh

author
#1 lore raw

PATCH 1/4 ocfs2: turn __ocfs2_remove_inode_range() into ocfs2_remove_btree_range()

This patch genericizes the high level handling of extent removal. ocfs2_remove_btree_range() is nearly identical to __ocfs2_remove_inode_range(), except that extent tree operations have been used where necessary. We update ocfs2_remove_inode_range() to use the generic helper. Now extent tree based structures have an easy way to truncate ranges.

Signed-off-by Mark Fasheh <[email protected]>
---
 fs/ocfs2/alloc.c |   72 +++++++++++++++++++++++++++++++++++++++++++++
 fs/ocfs2/alloc.h |    5 +++
 fs/ocfs2/file.c  |   85 +++--------------------------------------------------
 3 files changed, 82 insertions(+), 80 deletions(-)
fs/ocfs2/alloc.c +72 -0
index 4614614..5592a2f 100644
@@ -5255,6 +5255,78 @@ out:
 	return ret;
 }
 
+int ocfs2_remove_btree_range(struct inode *inode,
+			     struct ocfs2_extent_tree *et,
+			     u32 cpos, u32 phys_cpos, u32 len,
+			     struct ocfs2_cached_dealloc_ctxt *dealloc)
+{
+	int ret;
+	u64 phys_blkno = ocfs2_clusters_to_blocks(inode->i_sb, phys_cpos);
+	struct ocfs2_super *osb = OCFS2_SB(inode->i_sb);
+	struct inode *tl_inode = osb->osb_tl_inode;
+	handle_t *handle;
+	struct ocfs2_alloc_context *meta_ac = NULL;
+
+	ret = ocfs2_lock_allocators(inode, et, 0, 1, NULL, &meta_ac);
+	if (ret) {
+		mlog_errno(ret);
+		return ret;
+	}
+
+	mutex_lock(&tl_inode->i_mutex);
+
+	if (ocfs2_truncate_log_needs_flush(osb)) {
+		ret = __ocfs2_flush_truncate_log(osb);
+		if (ret < 0) {
+			mlog_errno(ret);
+			goto out;
+		}
+	}
+
+	handle = ocfs2_start_trans(osb, OCFS2_REMOVE_EXTENT_CREDITS);
+	if (IS_ERR(handle)) {
+		ret = PTR_ERR(handle);
+		mlog_errno(ret);
+		goto out;
+	}
+
+	ret = ocfs2_journal_access(handle, inode, et->et_root_bh,
+				   OCFS2_JOURNAL_ACCESS_WRITE);
+	if (ret) {
+		mlog_errno(ret);
+		goto out;
+	}
+
+	ret = ocfs2_remove_extent(inode, et, cpos, len, handle, meta_ac,
+				  dealloc);
+	if (ret) {
+		mlog_errno(ret);
+		goto out_commit;
+	}
+
+	ocfs2_et_update_clusters(inode, et, -len);
+
+	ret = ocfs2_journal_dirty(handle, et->et_root_bh);
+	if (ret) {
+		mlog_errno(ret);
+		goto out_commit;
+	}
+
+	ret = ocfs2_truncate_log_append(osb, handle, phys_blkno, len);
+	if (ret)
+		mlog_errno(ret);
+
+out_commit:
+	ocfs2_commit_trans(osb, handle);
+out:
+	mutex_unlock(&tl_inode->i_mutex);
+
+	if (meta_ac)
+		ocfs2_free_alloc_context(meta_ac);
+
+	return ret;
+}
+
 int ocfs2_truncate_log_needs_flush(struct ocfs2_super *osb)
 {
 	struct buffer_head *tl_bh = osb->osb_tl_bh;
fs/ocfs2/alloc.h +5 -0
index 3eb735e..0fbf8fc 100644
@@ -110,6 +110,11 @@ int ocfs2_remove_extent(struct inode *inode,
 			u32 cpos, u32 len, handle_t *handle,
 			struct ocfs2_alloc_context *meta_ac,
 			struct ocfs2_cached_dealloc_ctxt *dealloc);
+int ocfs2_remove_btree_range(struct inode *inode,
+			     struct ocfs2_extent_tree *et,
+			     u32 cpos, u32 phys_cpos, u32 len,
+			     struct ocfs2_cached_dealloc_ctxt *dealloc);
+
 int ocfs2_num_free_extents(struct ocfs2_super *osb,
 			   struct inode *inode,
 			   struct ocfs2_extent_tree *et);
fs/ocfs2/file.c +5 -80

104 lines not on this page · raw message

Signature · 1 line
1.5.4.1
#2 lore raw

PATCH 1/4 ocfs2: turn __ocfs2_remove_inode_range() into ocfs2_remove_btree_range()

Quoted 8 lines · Mark Fasheh

This patch genericizes the high level handling of extent removal. ocfs2_remove_btree_range() is nearly identical to __ocfs2_remove_inode_range(), except that extent tree operations have been used where necessary. We update ocfs2_remove_inode_range() to use the generic helper. Now extent tree based structures have an easy way to truncate ranges.

Signed-off-by Mark Fasheh <[email protected]>

I like it!

Signed-off-by Joel Becker <[email protected]>
Quoted 219 lines
---
 fs/ocfs2/alloc.c |   72 +++++++++++++++++++++++++++++++++++++++++++++
 fs/ocfs2/alloc.h |    5 +++
 fs/ocfs2/file.c  |   85 +++--------------------------------------------------
 3 files changed, 82 insertions(+), 80 deletions(-)
fs/ocfs2/alloc.c +72 -0
index 4614614..5592a2f 100644
@@ -5255,6 +5255,78 @@ out:
 	return ret;
 }
 
+int ocfs2_remove_btree_range(struct inode *inode,
+			     struct ocfs2_extent_tree *et,
+			     u32 cpos, u32 phys_cpos, u32 len,
+			     struct ocfs2_cached_dealloc_ctxt *dealloc)
+{
+	int ret;
+	u64 phys_blkno = ocfs2_clusters_to_blocks(inode->i_sb, phys_cpos);
+	struct ocfs2_super *osb = OCFS2_SB(inode->i_sb);
+	struct inode *tl_inode = osb->osb_tl_inode;
+	handle_t *handle;
+	struct ocfs2_alloc_context *meta_ac = NULL;
+
+	ret = ocfs2_lock_allocators(inode, et, 0, 1, NULL, &meta_ac);
+	if (ret) {
+		mlog_errno(ret);
+		return ret;
+	}
+
+	mutex_lock(&tl_inode->i_mutex);
+
+	if (ocfs2_truncate_log_needs_flush(osb)) {
+		ret = __ocfs2_flush_truncate_log(osb);
+		if (ret < 0) {
+			mlog_errno(ret);
+			goto out;
+		}
+	}
+
+	handle = ocfs2_start_trans(osb, OCFS2_REMOVE_EXTENT_CREDITS);
+	if (IS_ERR(handle)) {
+		ret = PTR_ERR(handle);
+		mlog_errno(ret);
+		goto out;
+	}
+
+	ret = ocfs2_journal_access(handle, inode, et->et_root_bh,
+				   OCFS2_JOURNAL_ACCESS_WRITE);
+	if (ret) {
+		mlog_errno(ret);
+		goto out;
+	}
+
+	ret = ocfs2_remove_extent(inode, et, cpos, len, handle, meta_ac,
+				  dealloc);
+	if (ret) {
+		mlog_errno(ret);
+		goto out_commit;
+	}
+
+	ocfs2_et_update_clusters(inode, et, -len);
+
+	ret = ocfs2_journal_dirty(handle, et->et_root_bh);
+	if (ret) {
+		mlog_errno(ret);
+		goto out_commit;
+	}
+
+	ret = ocfs2_truncate_log_append(osb, handle, phys_blkno, len);
+	if (ret)
+		mlog_errno(ret);
+
+out_commit:
+	ocfs2_commit_trans(osb, handle);
+out:
+	mutex_unlock(&tl_inode->i_mutex);
+
+	if (meta_ac)
+		ocfs2_free_alloc_context(meta_ac);
+
+	return ret;
+}
+
 int ocfs2_truncate_log_needs_flush(struct ocfs2_super *osb)
 {
 	struct buffer_head *tl_bh = osb->osb_tl_bh;
fs/ocfs2/alloc.h +5 -0
index 3eb735e..0fbf8fc 100644
@@ -110,6 +110,11 @@ int ocfs2_remove_extent(struct inode *inode,
 			u32 cpos, u32 len, handle_t *handle,
 			struct ocfs2_alloc_context *meta_ac,
 			struct ocfs2_cached_dealloc_ctxt *dealloc);
+int ocfs2_remove_btree_range(struct inode *inode,
+			     struct ocfs2_extent_tree *et,
+			     u32 cpos, u32 phys_cpos, u32 len,
+			     struct ocfs2_cached_dealloc_ctxt *dealloc);
+
 int ocfs2_num_free_extents(struct ocfs2_super *osb,
 			   struct inode *inode,
 			   struct ocfs2_extent_tree *et);
fs/ocfs2/file.c +5 -80
index e2570a3..3605491 100644
@@ -1226,83 +1226,6 @@ out:
 	return ret;
 }
 
-static int __ocfs2_remove_inode_range(struct inode *inode,
-				      struct buffer_head *di_bh,
-				      u32 cpos, u32 phys_cpos, u32 len,
-				      struct ocfs2_cached_dealloc_ctxt *dealloc)
-{
-	int ret;
-	u64 phys_blkno = ocfs2_clusters_to_blocks(inode->i_sb, phys_cpos);
-	struct ocfs2_super *osb = OCFS2_SB(inode->i_sb);
-	struct inode *tl_inode = osb->osb_tl_inode;
-	handle_t *handle;
-	struct ocfs2_alloc_context *meta_ac = NULL;
-	struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data;
-	struct ocfs2_extent_tree et;
-
-	ocfs2_init_dinode_extent_tree(&et, inode, di_bh);
-
-	ret = ocfs2_lock_allocators(inode, &et, 0, 1, NULL, &meta_ac);
-	if (ret) {
-		mlog_errno(ret);
-		return ret;
-	}
-
-	mutex_lock(&tl_inode->i_mutex);
-
-	if (ocfs2_truncate_log_needs_flush(osb)) {
-		ret = __ocfs2_flush_truncate_log(osb);
-		if (ret < 0) {
-			mlog_errno(ret);
-			goto out;
-		}
-	}
-
-	handle = ocfs2_start_trans(osb, OCFS2_REMOVE_EXTENT_CREDITS);
-	if (IS_ERR(handle)) {
-		ret = PTR_ERR(handle);
-		mlog_errno(ret);
-		goto out;
-	}
-
-	ret = ocfs2_journal_access(handle, inode, di_bh,
-				   OCFS2_JOURNAL_ACCESS_WRITE);
-	if (ret) {
-		mlog_errno(ret);
-		goto out;
-	}
-
-	ret = ocfs2_remove_extent(inode, &et, cpos, len, handle, meta_ac,
-				  dealloc);
-	if (ret) {
-		mlog_errno(ret);
-		goto out_commit;
-	}
-
-	OCFS2_I(inode)->ip_clusters -= len;
-	di->i_clusters = cpu_to_le32(OCFS2_I(inode)->ip_clusters);
-
-	ret = ocfs2_journal_dirty(handle, di_bh);
-	if (ret) {
-		mlog_errno(ret);
-		goto out_commit;
-	}
-
-	ret = ocfs2_truncate_log_append(osb, handle, phys_blkno, len);
-	if (ret)
-		mlog_errno(ret);
-
-out_commit:
-	ocfs2_commit_trans(osb, handle);
-out:
-	mutex_unlock(&tl_inode->i_mutex);
-
-	if (meta_ac)
-		ocfs2_free_alloc_context(meta_ac);
-
-	return ret;
-}
-
 /*
  * Truncate a byte range, avoiding pages within partial clusters. This
  * preserves those pages for the zeroing code to write to.

@@ -1402,7 +1325,9 @@ static int ocfs2_remove_inode_range(struct inode *inode,
 	struct ocfs2_super *osb = OCFS2_SB(inode->i_sb);
 	struct ocfs2_cached_dealloc_ctxt dealloc;
 	struct address_space *mapping = inode->i_mapping;
+	struct ocfs2_extent_tree et;
 
+	ocfs2_init_dinode_extent_tree(&et, inode, di_bh);
 	ocfs2_init_dealloc_ctxt(&dealloc);
 
 	if (byte_len == 0)

@@ -1458,9 +1383,9 @@ static int ocfs2_remove_inode_range(struct inode *inode,
 
 		/* Only do work for non-holes */
 		if (phys_cpos != 0) {
-			ret = __ocfs2_remove_inode_range(inode, di_bh, cpos,
-							 phys_cpos, alloc_size,
-							 &dealloc);
+			ret = ocfs2_remove_btree_range(inode, &et, cpos,
+						       phys_cpos, alloc_size,
+						       &dealloc);
 			if (ret) {
 				mlog_errno(ret);
 				goto out;
Signature · 1 line
1.5.4.1
Signature · 9 lines
Life's Little Instruction Book #451

	"Don't be afraid to say, 'I'm sorry.'"

Joel Becker
Principal Software Developer
Oracle
E-mail: joel.becker at oracle.com
Phone: (650) 506-8127
author
#3 lore raw

PATCH 2/4 ocfs2: Introduce dir lookup helper struct

In reply to Mark Fasheh

Many directory manipulation calls pass around a tuple of dirent, and it's containing buffer_head. Dir indexing has a bit more state, but instead of adding yet more arguments to functions, we introduce 'struct ocfs2_dir_lookup_result'. In this patch, it simply holds the same tuple, but future patches will add more state.

Signed-off-by Mark Fasheh <[email protected]>
---
 fs/ocfs2/dir.c   |  103 ++++++++++++++++++++-----------------
 fs/ocfs2/dir.h   |   30 ++++++-----
 fs/ocfs2/namei.c |  150 ++++++++++++++++++++++++++++--------------------------
 3 files changed, 150 insertions(+), 133 deletions(-)
fs/ocfs2/dir.c +56 -47
index 026e6eb..fa7870a 100644
@@ -125,6 +125,11 @@ fail:
 	return NULL;
 }
 
+void ocfs2_free_dir_lookup_result(struct ocfs2_dir_lookup_result *res)
+{
+	brelse(res->dl_leaf_bh);
+}
+
 /*
  * bh passed here can be an inode block or a dir data block, depending
  * on the inode inline data flag.

@@ -352,42 +357,52 @@ cleanup_and_exit:
 /*
  * Try to find an entry of the provided name within 'dir'.
  *
- * If nothing was found, NULL is returned. Otherwise, a buffer_head
- * and pointer to the dir entry are passed back.
+ * If nothing was found, -ENOENT is returned. Otherwise, zero is
+ * returned and the struct 'res' will contain information useful to
+ * other directory manipulation functions.
  *
  * Caller can NOT assume anything about the contents of the
- * buffer_head - it is passed back only so that it can be passed into
+ * buffer_heads - they are passed back only so that it can be passed into
  * any one of the manipulation functions (add entry, delete entry,
  * etc). As an example, bh in the extent directory case is a data
  * block, in the inline-data case it actually points to an inode.
  */
-struct buffer_head *ocfs2_find_entry(const char *name, int namelen,
-				     struct inode *dir,
-				     struct ocfs2_dir_entry **res_dir)
+int ocfs2_find_entry(const char *name, int namelen,
+		     struct inode *dir,
+		     struct ocfs2_dir_lookup_result *lookup)
 {
-	*res_dir = NULL;
+	struct buffer_head *bh;
+	struct ocfs2_dir_entry *res_dir = NULL;
 
 	if (OCFS2_I(dir)->ip_dyn_features & OCFS2_INLINE_DATA_FL)
-		return ocfs2_find_entry_id(name, namelen, dir, res_dir);
+		bh = ocfs2_find_entry_id(name, namelen, dir, &res_dir);
+	else
+		bh = ocfs2_find_entry_el(name, namelen, dir, &res_dir);
+
+	if (bh == NULL)
+		return -ENOENT;
 
-	return ocfs2_find_entry_el(name, namelen, dir, res_dir);
+	lookup->dl_leaf_bh = bh;
+	lookup->dl_entry = res_dir;
+	return 0;
 }
 
 /*
  * Update inode number and type of a previously found directory entry.
  */
 int ocfs2_update_entry(struct inode *dir, handle_t *handle,
-		       struct buffer_head *de_bh, struct ocfs2_dir_entry *de,
+		       struct ocfs2_dir_lookup_result *res,
 		       struct inode *new_entry_inode)
 {
 	int ret;
+	struct ocfs2_dir_entry *de = res->dl_entry;
 
 	/*
 	 * The same code works fine for both inline-data and extent
 	 * based directories, so no need to split this up.
 	 */
 
-	ret = ocfs2_journal_access(handle, dir, de_bh,
+	ret = ocfs2_journal_access(handle, dir, res->dl_leaf_bh,
 				   OCFS2_JOURNAL_ACCESS_WRITE);
 	if (ret) {
 		mlog_errno(ret);

@@ -397,7 +412,7 @@ int ocfs2_update_entry(struct inode *dir, handle_t *handle,
 	de->inode = cpu_to_le64(OCFS2_I(new_entry_inode)->ip_blkno);
 	ocfs2_set_de_type(de, new_entry_inode->i_mode);
 
-	ocfs2_journal_dirty(handle, de_bh);
+	ocfs2_journal_dirty(handle, res->dl_leaf_bh);
 
 out:
 	return ret;

@@ -490,13 +505,14 @@ static inline int ocfs2_delete_entry_el(handle_t *handle,
  */
 int ocfs2_delete_entry(handle_t *handle,
 		       struct inode *dir,
-		       struct ocfs2_dir_entry *de_del,
-		       struct buffer_head *bh)
+		       struct ocfs2_dir_lookup_result *res)
 {
 	if (OCFS2_I(dir)->ip_dyn_features & OCFS2_INLINE_DATA_FL)
-		return ocfs2_delete_entry_id(handle, dir, de_del, bh);
+		return ocfs2_delete_entry_id(handle, dir, res->dl_entry,
+					     res->dl_leaf_bh);
 
-	return ocfs2_delete_entry_el(handle, dir, de_del, bh);
+	return ocfs2_delete_entry_el(handle, dir, res->dl_entry,
+				     res->dl_leaf_bh);
 }
 
 /*

@@ -527,15 +543,15 @@ static inline int ocfs2_dirent_would_fit(struct ocfs2_dir_entry *de,
 /* we don't always have a dentry for what we want to add, so people
  * like orphan dir can call this instead.
  *
- * If you pass me insert_bh, I'll skip the search of the other dir
- * blocks and put the record in there.
+ * The lookup context must have been filled from
+ * ocfs2_prepare_dir_for_insert.
  */
 int __ocfs2_add_entry(handle_t *handle,
 		      struct inode *dir,
 		      const char *name, int namelen,
 		      struct inode *inode, u64 blkno,
 		      struct buffer_head *parent_fe_bh,
-		      struct buffer_head *insert_bh)
+		      struct ocfs2_dir_lookup_result *lookup)
 {
 	unsigned long offset;
 	unsigned short rec_len;

@@ -544,6 +560,7 @@ int __ocfs2_add_entry(handle_t *handle,
 	struct super_block *sb = dir->i_sb;
 	int retval, status;
 	unsigned int size = sb->s_blocksize;
+	struct buffer_head *insert_bh = lookup->dl_leaf_bh;
 	char *data_start = insert_bh->b_data;
 
 	mlog_entry_void();

@@ -917,31 +934,22 @@ int ocfs2_find_files_on_disk(const char *name,
 			     int namelen,
 			     u64 *blkno,
 			     struct inode *inode,
-			     struct buffer_head **dirent_bh,
-			     struct ocfs2_dir_entry **dirent)
+			     struct ocfs2_dir_lookup_result *lookup)
 {
 	int status = -ENOENT;
 
-	mlog_entry("(name=%.*s, blkno=%p, inode=%p, dirent_bh=%p, dirent=%p)\n",
-		   namelen, name, blkno, inode, dirent_bh, dirent);
+	mlog(0, "name=%.*s, blkno=%p, inode=%llu\n", namelen, name, blkno,
+	     (unsigned long long)OCFS2_I(inode)->ip_blkno);
 
-	*dirent_bh = ocfs2_find_entry(name, namelen, inode, dirent);
-	if (!*dirent_bh || !*dirent) {
-		status = -ENOENT;
+	status = ocfs2_find_entry(name, namelen, inode, lookup);
+	if (status)
 		goto leave;
-	}
 
-	*blkno = le64_to_cpu((*dirent)->inode);
+	*blkno = le64_to_cpu(lookup->dl_entry->inode);
 
 	status = 0;
 leave:
-	if (status < 0) {
-		*dirent = NULL;
-		brelse(*dirent_bh);
-		*dirent_bh = NULL;
-	}
 
-	mlog_exit(status);
 	return status;
 }
 

@@ -953,11 +961,10 @@ int ocfs2_lookup_ino_from_name(struct inode *dir, const char *name,
 			       int namelen, u64 *blkno)
 {
 	int ret;
-	struct buffer_head *bh = NULL;
-	struct ocfs2_dir_entry *dirent = NULL;
+	struct ocfs2_dir_lookup_result lookup = { NULL, };
 
-	ret = ocfs2_find_files_on_disk(name, namelen, blkno, dir, &bh, &dirent);
-	brelse(bh);
+	ret = ocfs2_find_files_on_disk(name, namelen, blkno, dir, &lookup);
+	ocfs2_free_dir_lookup_result(&lookup);
 
 	return ret;
 }

@@ -974,20 +981,18 @@ int ocfs2_check_dir_for_entry(struct inode *dir,
 			      int namelen)
 {
 	int ret;
-	struct buffer_head *dirent_bh = NULL;
-	struct ocfs2_dir_entry *dirent = NULL;
+	struct ocfs2_dir_lookup_result lookup = { NULL, };
 
 	mlog_entry("dir %llu, name '%.*s'\n",
 		   (unsigned long long)OCFS2_I(dir)->ip_blkno, namelen, name);
 
 	ret = -EEXIST;
-	dirent_bh = ocfs2_find_entry(name, namelen, dir, &dirent);
-	if (dirent_bh)
+	if (ocfs2_find_entry(name, namelen, dir, &lookup) == 0)
 		goto bail;
 
 	ret = 0;
 bail:
-	brelse(dirent_bh);
+	ocfs2_free_dir_lookup_result(&lookup);
 
 	mlog_exit(ret);
 	return ret;

@@ -1741,12 +1746,18 @@ bail:
 	return status;
 }
 
+/*
+ * Get a directory ready for insert. Any directory allocation required
+ * happens here. Success returns zero, and enough context in the dir
+ * lookup result that ocfs2_add_entry() will be able complete the task
+ * with minimal performance impact.
+ */
 int ocfs2_prepare_dir_for_insert(struct ocfs2_super *osb,
 				 struct inode *dir,
 				 struct buffer_head *parent_fe_bh,
 				 const char *name,
 				 int namelen,
-				 struct buffer_head **ret_de_bh)
+				 struct ocfs2_dir_lookup_result *lookup)
 {
 	int ret;
 	unsigned int blocks_wanted = 1;

@@ -1755,8 +1766,6 @@ int ocfs2_prepare_dir_for_insert(struct ocfs2_super *osb,
 	mlog(0, "getting ready to insert namelen %d into dir %llu\n",
 	     namelen, (unsigned long long)OCFS2_I(dir)->ip_blkno);
 
-	*ret_de_bh = NULL;
-
 	if (!namelen) {
 		ret = -EINVAL;
 		mlog_errno(ret);

@@ -1791,7 +1800,7 @@ int ocfs2_prepare_dir_for_insert(struct ocfs2_super *osb,
 		BUG_ON(!bh);
 	}
 
-	*ret_de_bh = bh;
+	lookup->dl_leaf_bh = bh;
 	bh = NULL;
 out:
 	brelse(bh);
fs/ocfs2/dir.h +17 -13
index ce48b90..768ee9f 100644
@@ -26,44 +26,48 @@
 #ifndef OCFS2_DIR_H
 #define OCFS2_DIR_H
 
-struct buffer_head *ocfs2_find_entry(const char *name,
-				     int namelen,
-				     struct inode *dir,
-				     struct ocfs2_dir_entry **res_dir);
+struct ocfs2_dir_lookup_result {
+	struct buffer_head		*dl_leaf_bh;
+	struct ocfs2_dir_entry		*dl_entry;
+};
+void ocfs2_free_dir_lookup_result(struct ocfs2_dir_lookup_result *res);
+
+int ocfs2_find_entry(const char *name, int namelen,
+		     struct inode *dir,
+		     struct ocfs2_dir_lookup_result *lookup);
 int ocfs2_delete_entry(handle_t *handle,
 		       struct inode *dir,
-		       struct ocfs2_dir_entry *de_del,
-		       struct buffer_head *bh);
+		       struct ocfs2_dir_lookup_result *res);
 int __ocfs2_add_entry(handle_t *handle,
 		      struct inode *dir,
 		      const char *name, int namelen,
 		      struct inode *inode, u64 blkno,
 		      struct buffer_head *parent_fe_bh,
-		      struct buffer_head *insert_bh);
+		      struct ocfs2_dir_lookup_result *lookup);
 static inline int ocfs2_add_entry(handle_t *handle,
 				  struct dentry *dentry,
 				  struct inode *inode, u64 blkno,
 				  struct buffer_head *parent_fe_bh,
-				  struct buffer_head *insert_bh)
+				  struct ocfs2_dir_lookup_result *lookup)
 {
 	return __ocfs2_add_entry(handle, dentry->d_parent->d_inode,
 				 dentry->d_name.name, dentry->d_name.len,
-				 inode, blkno, parent_fe_bh, insert_bh);
+				 inode, blkno, parent_fe_bh, lookup);
 }
 int ocfs2_update_entry(struct inode *dir, handle_t *handle,
-		       struct buffer_head *de_bh, struct ocfs2_dir_entry *de,
+		       struct ocfs2_dir_lookup_result *res,
 		       struct inode *new_entry_inode);
 
 int ocfs2_check_dir_for_entry(struct inode *dir,
 			      const char *name,
 			      int namelen);
 int ocfs2_empty_dir(struct inode *inode);
+
 int ocfs2_find_files_on_disk(const char *name,
 			     int namelen,
 			     u64 *blkno,
 			     struct inode *inode,
-			     struct buffer_head **dirent_bh,
-			     struct ocfs2_dir_entry **dirent);
+			     struct ocfs2_dir_lookup_result *res);
 int ocfs2_lookup_ino_from_name(struct inode *dir, const char *name,
 			       int namelen, u64 *blkno);
 int ocfs2_readdir(struct file *filp, void *dirent, filldir_t filldir);

@@ -74,7 +78,7 @@ int ocfs2_prepare_dir_for_insert(struct ocfs2_super *osb,
 				 struct buffer_head *parent_fe_bh,
 				 const char *name,
 				 int namelen,
-				 struct buffer_head **ret_de_bh);
+				 struct ocfs2_dir_lookup_result *lookup);
 struct ocfs2_alloc_context;
 int ocfs2_fill_new_dir(struct ocfs2_super *osb,
 		       handle_t *handle,
fs/ocfs2/namei.c +77 -73

441 lines not on this page · raw message

Signature · 1 line
1.5.4.1
#4 lore raw

PATCH 2/4 ocfs2: Introduce dir lookup helper struct

Quoted 5 lines · Mark Fasheh

Many directory manipulation calls pass around a tuple of dirent, and it's containing buffer_head. Dir indexing has a bit more state, but instead of adding yet more arguments to functions, we introduce 'struct ocfs2_dir_lookup_result'. In this patch, it simply holds the same tuple, but future patches will add more state.

I really like this, especially that we're fixing functions that
return in two places (via the actual return and a ** argument). I'd be tempted to pass the *lookup down into find_el and find_id just to continue that pattern - but that's just me.
Also, rename, wow :-)

Signed-off-by Joel Becker <[email protected]>
Signature · 7 lines
"People with narrow minds usually have broad tongues."

Joel Becker
Principal Software Developer
Oracle
E-mail: joel.becker at oracle.com
Phone: (650) 506-8127
author
#5 lore raw

PATCH 3/4 ocfs2: Add a name indexed b-tree to directory inodes

In reply to Mark Fasheh

This patch makes use of Ocfs2's flexible btree code to add an additional tree to directory inodes. The new tree stores an array of small, fixed-length records in each leaf block. Each record stores a hash value, and pointer to a block in the traditional (unindexed) directory tree where a dirent with the given name hash resides. Lookup exclusively uses this tree to find dirents, thus providing us with constant time name lookups.

Some of the hashing code was copied from ext3. Unfortunately, it has lots of unfixed checkpatch errors. I left that as-is so that tracking changes would be easier.

Signed-off-by Mark Fasheh <[email protected]>
---
 fs/ocfs2/alloc.c    |   65 ++
 fs/ocfs2/alloc.h    |    3 +
 fs/ocfs2/dir.c      | 1683 ++++++++++++++++++++++++++++++++++++++++++++++++++-
 fs/ocfs2/dir.h      |   14 +-
 fs/ocfs2/inode.c    |    9 +
 fs/ocfs2/journal.h  |   53 ++-
 fs/ocfs2/namei.c    |   34 +-
 fs/ocfs2/ocfs2.h    |   31 +
 fs/ocfs2/ocfs2_fs.h |   95 +++-
 fs/ocfs2/super.c    |    6 +
 10 files changed, 1940 insertions(+), 53 deletions(-)
fs/ocfs2/alloc.c +65 -0
index 5592a2f..d10580d 100644
@@ -301,6 +301,62 @@ static struct ocfs2_extent_tree_operations ocfs2_xattr_tree_et_ops = {
 	.eo_fill_max_leaf_clusters = ocfs2_xattr_tree_fill_max_leaf_clusters,
 };
 
+static void ocfs2_dx_root_set_last_eb_blk(struct ocfs2_extent_tree *et,
+					  u64 blkno)
+{
+	struct ocfs2_dx_root_block *dx_root = et->et_object;
+
+	dx_root->dr_last_eb_blk = cpu_to_le64(blkno);
+}
+
+static u64 ocfs2_dx_root_get_last_eb_blk(struct ocfs2_extent_tree *et)
+{
+	struct ocfs2_dx_root_block *dx_root = et->et_object;
+
+	return le64_to_cpu(dx_root->dr_last_eb_blk);
+}
+
+static void ocfs2_dx_root_update_clusters(struct inode *inode,
+					  struct ocfs2_extent_tree *et,
+					  u32 clusters)
+{
+	struct ocfs2_dx_root_block *dx_root = et->et_object;
+
+	le32_add_cpu(&dx_root->dr_clusters, clusters);
+}
+
+static int ocfs2_dx_root_sanity_check(struct inode *inode,
+				      struct ocfs2_extent_tree *et)
+{
+	int ret = 0;
+	struct ocfs2_dx_root_block *dx_root = et->et_object;
+
+	dx_root = et->et_object;
+	if (!OCFS2_IS_VALID_DX_ROOT(dx_root)) {
+		ret = -EIO;
+		ocfs2_error(inode->i_sb,
+			"Directory %llu has invalid dx root",
+			(unsigned long long)OCFS2_I(inode)->ip_blkno);
+	}
+
+	return ret;
+}
+
+static void ocfs2_dx_root_fill_root_el(struct ocfs2_extent_tree *et)
+{
+	struct ocfs2_dx_root_block *dx_root = et->et_object;
+
+	et->et_root_el = &dx_root->dr_list;
+}
+
+static struct ocfs2_extent_tree_operations ocfs2_dx_root_et_ops = {
+	.eo_set_last_eb_blk	= ocfs2_dx_root_set_last_eb_blk,
+	.eo_get_last_eb_blk	= ocfs2_dx_root_get_last_eb_blk,
+	.eo_update_clusters	= ocfs2_dx_root_update_clusters,
+	.eo_sanity_check	= ocfs2_dx_root_sanity_check,
+	.eo_fill_root_el	= ocfs2_dx_root_fill_root_el,
+};
+
 static void __ocfs2_init_extent_tree(struct ocfs2_extent_tree *et,
 				     struct inode *inode,
 				     struct buffer_head *bh,

@@ -344,6 +400,15 @@ void ocfs2_init_xattr_value_extent_tree(struct ocfs2_extent_tree *et,
 				 &ocfs2_xattr_value_et_ops);
 }
 
+void ocfs2_init_dx_root_extent_tree(struct ocfs2_extent_tree *et,
+				    struct inode *inode,
+				    struct buffer_head *bh)
+{
+	__ocfs2_init_extent_tree(et, inode, bh, NULL, &ocfs2_dx_root_et_ops);
+}
+
+
+
 static inline void ocfs2_et_set_last_eb_blk(struct ocfs2_extent_tree *et,
 					    u64 new_last_eb_blk)
 {
fs/ocfs2/alloc.h +3 -0
index 0fbf8fc..e1763cc 100644
@@ -72,6 +72,9 @@ void ocfs2_init_xattr_value_extent_tree(struct ocfs2_extent_tree *et,
 					struct inode *inode,
 					struct buffer_head *bh,
 					struct ocfs2_xattr_value_root *xv);
+void ocfs2_init_dx_root_extent_tree(struct ocfs2_extent_tree *et,
+				    struct inode *inode,
+				    struct buffer_head *bh);
 
 struct ocfs2_alloc_context;
 int ocfs2_insert_extent(struct ocfs2_super *osb,
fs/ocfs2/dir.c +1655 -28

1,907 lines not on this page · raw message

fs/ocfs2/dir.h +13 -1
index 768ee9f..d035b75 100644
@@ -26,9 +26,18 @@
 #ifndef OCFS2_DIR_H
 #define OCFS2_DIR_H
 
+struct ocfs2_dx_hinfo {
+	u32	major_hash;
+	u32	minor_hash;
+};
+
 struct ocfs2_dir_lookup_result {
 	struct buffer_head		*dl_leaf_bh;
 	struct ocfs2_dir_entry		*dl_entry;
+
+	struct buffer_head		*dl_dx_leaf_bh;
+	struct ocfs2_dx_entry		*dl_dx_entry;
+	struct ocfs2_dx_hinfo		dl_hinfo;
 };
 void ocfs2_free_dir_lookup_result(struct ocfs2_dir_lookup_result *res);
 

@@ -85,6 +94,9 @@ int ocfs2_fill_new_dir(struct ocfs2_super *osb,
 		       struct inode *parent,
 		       struct inode *inode,
 		       struct buffer_head *fe_bh,
-		       struct ocfs2_alloc_context *data_ac);
+		       struct ocfs2_alloc_context *data_ac,
+		       struct ocfs2_alloc_context *meta_ac);
+
+int ocfs2_dx_dir_truncate(struct inode *dir, struct buffer_head *di_bh);
 
 #endif /* OCFS2_DIR_H */
fs/ocfs2/inode.c +9 -0
index 7aa00d5..bdfe09f 100644
@@ -37,6 +37,7 @@
 #include "ocfs2.h"
 
 #include "alloc.h"
+#include "dir.h"
 #include "dlmglue.h"
 #include "extent_map.h"
 #include "file.h"

@@ -748,6 +749,14 @@ static int ocfs2_wipe_inode(struct inode *inode,
 		goto bail_unlock_dir;
 	}
 
+	if (S_ISDIR(inode->i_mode)) {
+		status = ocfs2_dx_dir_truncate(inode, di_bh);
+		if (status) {
+			mlog_errno(status);
+			goto bail_unlock_dir;
+		}
+	}
+
 	/*Free extended attribute resources associated with this inode.*/
 	status = ocfs2_xattr_remove(inode, di_bh);
 	if (status < 0) {
fs/ocfs2/journal.h +39 -14

90 lines not on this page · raw message

fs/ocfs2/namei.c +27 -7
index d136bdf..862c576 100644
@@ -191,7 +191,7 @@ static int ocfs2_mknod(struct inode *dir,
 		       int mode,
 		       dev_t dev)
 {
-	int status = 0;
+	int status = 0, newdir_clusters;
 	struct buffer_head *parent_fe_bh = NULL;
 	handle_t *handle = NULL;
 	struct ocfs2_super *osb;

@@ -199,6 +199,7 @@ static int ocfs2_mknod(struct inode *dir,
 	struct buffer_head *new_fe_bh = NULL;
 	struct inode *inode = NULL;
 	struct ocfs2_alloc_context *inode_ac = NULL;
+	struct ocfs2_alloc_context *meta_ac = NULL;
 	struct ocfs2_alloc_context *data_ac = NULL;
 	struct ocfs2_dir_lookup_result lookup = { NULL, };
 

@@ -252,7 +253,21 @@ static int ocfs2_mknod(struct inode *dir,
 
 	/* Reserve a cluster if creating an extent based directory. */
 	if (S_ISDIR(mode) && !ocfs2_supports_inline_data(osb)) {
-		status = ocfs2_reserve_clusters(osb, 1, &data_ac);
+		newdir_clusters = 1;
+
+		if (ocfs2_supports_indexed_dirs(osb)) {
+			newdir_clusters++;
+
+			status = ocfs2_reserve_new_metadata_blocks(osb, 1,
+								   &meta_ac);
+			if (status < 0) {
+				if (status != -ENOSPC)
+					mlog_errno(status);
+				goto leave;
+			}
+		}
+
+		status = ocfs2_reserve_clusters(osb, newdir_clusters, &data_ac);
 		if (status < 0) {
 			if (status != -ENOSPC)
 				mlog_errno(status);

@@ -260,7 +275,8 @@ static int ocfs2_mknod(struct inode *dir,
 		}
 	}
 
-	handle = ocfs2_start_trans(osb, OCFS2_MKNOD_CREDITS);
+	handle = ocfs2_start_trans(osb, ocfs2_mknod_credits(osb->sb,
+							    S_ISDIR(mode)));
 	if (IS_ERR(handle)) {
 		status = PTR_ERR(handle);
 		handle = NULL;

@@ -279,7 +295,7 @@ static int ocfs2_mknod(struct inode *dir,
 
 	if (S_ISDIR(mode)) {
 		status = ocfs2_fill_new_dir(osb, handle, dir, inode,
-					    new_fe_bh, data_ac);
+					    new_fe_bh, data_ac, meta_ac);
 		if (status < 0) {
 			mlog_errno(status);
 			goto leave;

@@ -339,6 +355,9 @@ leave:
 	if (inode_ac)
 		ocfs2_free_alloc_context(inode_ac);
 
+	if (meta_ac)
+		ocfs2_free_alloc_context(meta_ac);
+
 	if (data_ac)
 		ocfs2_free_alloc_context(data_ac);
 

@@ -362,6 +381,7 @@ static int ocfs2_mknod_locked(struct ocfs2_super *osb,
 	struct ocfs2_extent_list *fel;
 	u64 fe_blkno = 0;
 	u16 suballoc_bit;
+	u16 feat;
 	struct inode *inode = NULL;
 
 	mlog_entry("(0x%p, 0x%p, %d, %lu, '%.*s')\n", dir, dentry, mode,

@@ -445,11 +465,11 @@ static int ocfs2_mknod_locked(struct ocfs2_super *osb,
 	fe->i_dtime = 0;
 
 	/*
-	 * If supported, directories start with inline data.
+	 * If supported, directories start with inline data. If inline
+	 * isn't supported, but indexing is, we start them as indexed.
 	 */
+	feat = le16_to_cpu(fe->i_dyn_features);
 	if (S_ISDIR(mode) && ocfs2_supports_inline_data(osb)) {
-		u16 feat = le16_to_cpu(fe->i_dyn_features);
-
 		fe->i_dyn_features = cpu_to_le16(feat | OCFS2_INLINE_DATA_FL);
 
 		fe->id2.i_data.id_count = cpu_to_le16(ocfs2_max_inline_data(osb->sb));
fs/ocfs2/ocfs2.h +31 -0
index 3fed9e3..e87fedd 100644
@@ -329,6 +329,9 @@ struct ocfs2_super
 	struct ocfs2_node_map		osb_recovering_orphan_dirs;
 	unsigned int			*osb_orphan_wipes;
 	wait_queue_head_t		osb_wipe_event;
+
+	unsigned int			osb_dx_mask;
+	u32				osb_dx_seed[4];
 };
 
 #define OCFS2_SB(sb)	    ((struct ocfs2_super *)(sb)->s_fs_info)

@@ -376,6 +379,13 @@ static inline int ocfs2_supports_xattr(struct ocfs2_super *osb)
 	return 0;
 }
 
+static inline int ocfs2_supports_indexed_dirs(struct ocfs2_super *osb)
+{
+	if (osb->s_feature_incompat & OCFS2_FEATURE_INCOMPAT_INDEXED_DIRS)
+		return 1;
+	return 0;
+}
+
 /* set / clear functions because cluster events can make these happen
  * in parallel so we want the transitions to be atomic. this also
  * means that any future flags osb_flags must be protected by spinlock

@@ -476,6 +486,27 @@ static inline int ocfs2_uses_extended_slot_map(struct ocfs2_super *osb)
 #define OCFS2_IS_VALID_XATTR_BLOCK(ptr)					\
 	(!strcmp((ptr)->xb_signature, OCFS2_XATTR_BLOCK_SIGNATURE))
 
+#define OCFS2_IS_VALID_DX_ROOT(ptr)					\
+	(!strcmp((ptr)->dr_signature, OCFS2_DX_ROOT_SIGNATURE))
+
+#define OCFS2_RO_ON_INVALID_DX_ROOT(__sb, __ir)	do {			\
+	typeof(__ir) ____ir = (__ir);					\
+		ocfs2_error((__sb),					\
+		"Dir Index Root # %llu has bad signature %.*s",		\
+		(unsigned long long)le64_to_cpu((____ir)->dr_blkno), 7,	\
+		(____ir)->dr_signature);				\
+} while (0)
+
+#define OCFS2_IS_VALID_DX_LEAF(ptr)					\
+	(!strcmp((ptr)->dl_signature, OCFS2_DX_LEAF_SIGNATURE))
+
+#define OCFS2_RO_ON_INVALID_DX_LEAF(__sb, __ir)	do {			\
+	typeof(__ir) ____ir = (__ir);					\
+		ocfs2_error((__sb),					\
+		"Dir Index Leaf has bad signature %.*s",		\
+		7, (____ir)->dl_signature);				\
+} while (0)
+
 static inline unsigned long ino_from_blkno(struct super_block *sb,
 					   u64 blkno)
 {
fs/ocfs2/ocfs2_fs.h +92 -3

137 lines not on this page · raw message

fs/ocfs2/super.c +6 -0
index 304b63a..ccbb438 100644
@@ -1421,6 +1421,12 @@ static int ocfs2_initialize_super(struct super_block *sb,
 	bbits = le32_to_cpu(di->id2.i_super.s_blocksize_bits);
 	sb->s_maxbytes = ocfs2_max_file_offset(bbits, cbits);
 
+	osb->osb_dx_mask = (1 << (cbits - bbits)) - 1;
+
+	for (i = 0; i < 3; i++)
+		osb->osb_dx_seed[i] = le32_to_cpu(di->id2.i_super.s_dx_seed[i]);
+	osb->osb_dx_seed[3] = le32_to_cpu(di->id2.i_super.s_uuid_hash);
+
 	osb->sb = sb;
 	/* Save off for ocfs2_rw_direct */
 	osb->s_sectsize_bits = blksize_bits(sector_size);
Signature · 1 line
1.5.4.1
#6 lore raw

PATCH 3/4 ocfs2: Add a name indexed b-tree to directory inodes

Quoted 6 lines · Mark Fasheh

This patch makes use of Ocfs2's flexible btree code to add an additional tree to directory inodes. The new tree stores an array of small, fixed-length records in each leaf block. Each record stores a hash value, and pointer to a block in the traditional (unindexed) directory tree where a dirent with the given name hash resides. Lookup exclusively uses this tree to find dirents, thus providing us with constant time name lookups.

Whee!

fs/ocfs2/alloc.c static struct ocfs2_extent_tree_operations ocfs2_xattr_tree_et_ops = { · line 358

Quoted 7 lines
fs/ocfs2/alloc.c +7 -0
+static struct ocfs2_extent_tree_operations ocfs2_dx_root_et_ops = {
+	.eo_set_last_eb_blk	= ocfs2_dx_root_set_last_eb_blk,
+	.eo_get_last_eb_blk	= ocfs2_dx_root_get_last_eb_blk,
+	.eo_update_clusters	= ocfs2_dx_root_update_clusters,
+	.eo_sanity_check	= ocfs2_dx_root_sanity_check,
+	.eo_fill_root_el	= ocfs2_dx_root_fill_root_el,
+};

This makes me happy.

Quoted 14 lines
fs/ocfs2/dir.c +14 -0
+static int ocfs2_dx_dir_lookup(struct inode *inode,
+			       struct ocfs2_extent_list *el,
+			       struct ocfs2_dx_hinfo *hinfo,
+			       u32 *ret_cpos,
+			       u64 *ret_phys_blkno)
+{
+	int ret = 0;
+	unsigned int cend, uninitialized_var(clen);
+	u32 uninitialized_var(cpos);
+	u64 uninitialized_var(blkno);
+	u32 name_hash = hinfo->major_hash;
+
+	ret = ocfs2_dx_dir_lookup_rec(inode, el, name_hash, &cpos, &blkno,
+				      &clen);

fs/ocfs2/dir.c cleanup_and_exit: · line 550

Quoted 10 lines
fs/ocfs2/dir.c +10 -0
+	if (ret) {
+		mlog_errno(ret);
+		goto out;
+	}
+
+	cend = cpos + clen;
+	if (name_hash >= cend) {
+		/* We want the last cluster */
+		blkno += ocfs2_clusters_to_blocks(inode->i_sb, clen - 1);
+		cpos += clen - 1;

I assume this means that we have an "anything at the end"
behavior going on here? Perhaps an explicit comment on that.

Quoted 45 lines
fs/ocfs2/dir.c +45 -0
+static int ocfs2_delete_entry_dx(handle_t *handle, struct inode *dir,
+				 struct ocfs2_dir_lookup_result *lookup)
+{
+	int ret, index;
+	struct buffer_head *leaf_bh = lookup->dl_leaf_bh;
+	struct ocfs2_dx_leaf *dx_leaf;
+	struct ocfs2_dx_entry *dx_entry = lookup->dl_dx_entry;
+
+	dx_leaf = (struct ocfs2_dx_leaf *) lookup->dl_dx_leaf_bh->b_data;
+	/* Neither of these are a disk corruption - that should have
+	 * been caught by lookup, before we got here. */
+	BUG_ON(le16_to_cpu(dx_leaf->dl_count) <= 0);
+	BUG_ON(le16_to_cpu(dx_leaf->dl_num_used) <= 0);
+
+	index = (char *)dx_entry - (char *)dx_leaf->dl_entries;
+	index /= sizeof(*dx_entry);
+
+	if (index >= le16_to_cpu(dx_leaf->dl_num_used)) {
+		mlog(ML_ERROR, "Dir %llu: Bad dx_entry ptr idx %d, (%p, %p)\n",
+		     (unsigned long long)OCFS2_I(dir)->ip_blkno, index, dx_leaf,
+		     dx_entry);
+		return -EIO;
+	}
+
+	mlog(0, "Dir %llu: delete entry at index: %d\n",
+	     (unsigned long long)OCFS2_I(dir)->ip_blkno, index);
+
+	/*
+	 * Add the index leaf into the journal before removing the
+	 * unindexed entry. If we get an error return from
+	 * __ocfs2_delete_entry(), then it hasn't removed the entry
+	 * yet. Likewise, successful return means we *must* remove the
+	 * indexed entry.
+	 */
+	ret = ocfs2_journal_access(handle, dir, lookup->dl_dx_leaf_bh,
+				   OCFS2_JOURNAL_ACCESS_WRITE);
+	if (ret) {
+		mlog_errno(ret);
+		goto out;
+	}
+
+	ret = __ocfs2_delete_entry(handle, dir, lookup->dl_entry,
+				   leaf_bh, leaf_bh->b_data, leaf_bh->b_size);
+	if (ret) {
+		mlog_errno(ret);

fs/ocfs2/dir.c bail: · line 947

Quoted 10 lines
fs/ocfs2/dir.c +10 -0
+		goto out;
+	}
+
+	ocfs2_dx_leaf_remove_entry(dx_leaf, index);
+
+	ocfs2_journal_dirty(handle, lookup->dl_dx_leaf_bh);
+
+out:
+	return ret;
+}

I love using indexed lookup for unlink(2).

Quoted 5 lines

static int ocfs2_expand_inline_dir(struct inode *dir, struct buffer_head *di_bh,

fs/ocfs2/dir.c +1 -0
 				   unsigned int blocks_wanted,
+				   struct ocfs2_dir_lookup_result *lookup,
 				   struct buffer_head **first_block_bh)
 {

<snip>

Review

Quoted 1 line
(quoted diff) +1 -0
+	if (ocfs2_supports_indexed_dirs(osb)) {

The multiple places you have to stick this check in for proper
ordering is fun. I understand why, though.

Quoted 51 lines

/*
+ * A directory indexing block. Each indexed directory has one of these,
+ * pointed to by ocfs2_dinode.
+ *
+ * This block stores an indexed btree root, and a set of free space
+ * start-of-list pointers.
+ */

fs/ocfs2/ocfs2_fs.h +44 -0
+struct ocfs2_dx_root_block {
+	__u8		dr_signature[8];	/* Signature for verification */
+	__le64		dr_csum;		/* Checksum (unused) */
+	__le16		dr_suballoc_slot;	/* Slot suballocator this
+						 * block belongs to. */
+	__le16		dr_suballoc_bit;	/* Bit offset in suballocator
+						 * block group */
+	__le32		dr_fs_generation;	/* Must match super block */
+	__le64		dr_blkno;		/* Offset on disk, in blocks */
+	__le64		dr_last_eb_blk;		/* Pointer to last
+						 * extent block */
+	__le32		dr_clusters;		/* Clusters allocated
+						 * to the indexed tree. */
+	__le32		dr_reserved1;
+	__le64		dr_dir_blkno;		/* Pointer to parent inode */
+	__le64		dr_reserved2;
+	__le64		dr_reserved3[16];
+	struct ocfs2_extent_list	dr_list; /* Keep this aligned to 128
+						  * bits for maximum space
+						  * efficiency. */
+};
+
+/*
+ * A directory entry in the indexed tree. We don't store the full name here,
+ * but instead provide a pointer to the full dirent in the unindexed tree.
+ *
+ * We also store name_len here so as to reduce the number of leaf blocks we
+ * need to search in case of collisions.
+ */
+struct ocfs2_dx_entry {
+	__le32		dx_major_hash;	/* Used to find logical
+					 * cluster in index */
+	__le32		dx_minor_hash;	/* Lower bits used to find
+					 * block in cluster */
+	__le64		dx_dirent_blk;	/* Physical block in unindexed
+					 * tree holding this dirent. */
+};
+
+/*
+ * The header of a leaf block in the indexed tree.
+ */
+struct ocfs2_dx_leaf {
+	__u8		dl_signature[8];/* Signature for verification */
+	__le64		dl_csum;	/* Checksum (unused) */

fs/ocfs2/ocfs2_fs.h struct ocfs2_dir_entry { · line 778

Quoted 10 lines
fs/ocfs2/ocfs2_fs.h +10 -0
+	__le64		dl_reserved1;
+	__le32		dl_reserved2;
+	__le16		dl_count;	/* Maximum number of entries
+					 * possible in ih_entries */
+	__le16		dl_num_used;	/* Current number of
+					 * ih_entries entries */
+	struct	ocfs2_dx_entry		dl_entries[0];	/* Indexed dir entries
+							 * in a packed array of
+							 * length ih_num_used */
+};

I'd love to see offset annotations on these structures. Otherwise, this is awesome!

Joel

Signature · 9 lines
"The first requisite of a good citizen in this republic of ours
 is that he shall be able and willing to pull his weight."
	- Theodore Roosevelt

Joel Becker
Principal Software Developer
Oracle
E-mail: joel.becker at oracle.com
Phone: (650) 506-8127
author
#7 lore raw

PATCH 4/4 ocfs2: Introduce dir free space list

In reply to Mark Fasheh

The only operation which doesn't get faster with directory indexing is insert, which still has to walk the entire unindexed directory portion to find a free block. This patch provides an improvement in directory insert performance by maintaining a singly linked list of directory leaf blocks which have space for additional dirents.

As the disk format is now finalized, we also turn on directory indexing support.

Signed-off-by Mark Fasheh <[email protected]>
---
 fs/ocfs2/dir.c      |  536 +++++++++++++++++++++++++++++++++++++++++++++++----
 fs/ocfs2/dir.h      |    4 +
 fs/ocfs2/journal.h  |   12 +-
 fs/ocfs2/namei.c    |    8 +-
 fs/ocfs2/ocfs2_fs.h |   32 +++-
 5 files changed, 539 insertions(+), 53 deletions(-)
fs/ocfs2/dir.c +494 -42
index f113704..479d2b7 100644
@@ -130,6 +130,89 @@ static int ocfs2_dir_indexed(struct inode *inode)
 }
 
 /*
+ * These are distinct checks because future versions of the file system will
+ * want to have a trailing dirent structure independent of indexing.
+ */
+static int ocfs2_dir_has_trailer(struct inode *dir)
+{
+	return ocfs2_dir_indexed(dir);
+}
+static int ocfs2_supports_dir_trailer(struct ocfs2_super *osb)
+{
+	return ocfs2_supports_indexed_dirs(osb);
+}
+
+static inline unsigned int ocfs2_dir_trailer_blk_off(struct super_block *sb)
+{
+	return sb->s_blocksize - sizeof(struct ocfs2_dir_block_trailer);
+}
+
+#define ocfs2_trailer_from_bh(_bh, _sb) ((struct ocfs2_dir_block_trailer *) ((_bh)->b_data + ocfs2_dir_trailer_blk_off((_sb))))
+
+/*
+ * XXX: This is executed once on every dirent. We should consider optimizing
+ * it.
+ */
+static int ocfs2_skip_dir_trailer(struct inode *dir,
+				  struct ocfs2_dir_entry *de,
+				  unsigned long offset,
+				  unsigned long blklen)
+{
+	unsigned long toff = blklen - sizeof(struct ocfs2_dir_block_trailer);
+
+	if (!ocfs2_dir_has_trailer(dir))
+		return 0;
+
+	if (offset != toff)
+		return 0;
+
+	return 1;
+}
+
+static void ocfs2_init_dir_trailer(struct super_block *sb,
+				   struct buffer_head *bh, u16 rec_len)
+{
+	struct ocfs2_dir_block_trailer *trailer;
+
+	trailer = ocfs2_trailer_from_bh(bh, sb);
+	strcpy(trailer->db_signature, OCFS2_DIR_TRAILER_SIGNATURE);
+	trailer->db_compat_rec_len =
+			le16_to_cpu(sizeof(struct ocfs2_dir_block_trailer));
+	trailer->db_free_rec_len = cpu_to_le16(rec_len);
+}
+
+/*
+ * Link an unindexed block with a dir trailer structure into the index free
+ * list. This function will modify dirdata_bh, but assumes you've already
+ * passed it to the journal.
+ */
+static int ocfs2_dx_dir_link_trailer(struct inode *dir, handle_t *handle,
+				     struct buffer_head *dx_root_bh,
+				     struct buffer_head *dirdata_bh)
+{
+	int ret;
+	struct ocfs2_dx_root_block *dx_root;
+	struct ocfs2_dir_block_trailer *trailer;
+
+	ret = ocfs2_journal_access(handle, dir, dx_root_bh,
+				   OCFS2_JOURNAL_ACCESS_WRITE);
+	if (ret) {
+		mlog_errno(ret);
+		goto out;
+	}
+	trailer = ocfs2_trailer_from_bh(dirdata_bh, dir->i_sb);
+	dx_root = (struct ocfs2_dx_root_block *)dx_root_bh->b_data;
+
+	trailer->db_free_next = dx_root->dr_free_blk;
+	dx_root->dr_free_blk = cpu_to_le64(dirdata_bh->b_blocknr);
+
+	ocfs2_journal_dirty(handle, dx_root_bh);
+
+out:
+	return ret;
+}
+
+/*
  * Hashing code adapted from ext3
  */
 #define DELTA 0x9E3779B9

@@ -874,6 +957,45 @@ bail:
 	return status;
 }
 
+static unsigned int ocfs2_figure_dirent_hole(struct ocfs2_dir_entry *de)
+{
+	unsigned int hole;
+
+	if (le64_to_cpu(de->inode) == 0)
+		hole = le16_to_cpu(de->rec_len);
+	else
+		hole = le16_to_cpu(de->rec_len) -
+			OCFS2_DIR_REC_LEN(de->name_len);
+
+	return hole;	
+}
+
+static int ocfs2_find_max_rec_len(struct super_block *sb,
+				  struct buffer_head *dirblock_bh)
+{
+	int size, this_hole, largest_hole = 0;
+	char *trailer, *de_buf, *limit, *start = dirblock_bh->b_data;
+	struct ocfs2_dir_entry *de;
+
+	trailer = (char *)ocfs2_trailer_from_bh(dirblock_bh, sb);
+	size = ocfs2_dir_trailer_blk_off(sb);
+	limit = start + size;
+	de_buf = start;
+	de = (struct ocfs2_dir_entry *)de_buf;
+	do {
+		if (de_buf != trailer) {
+			this_hole = ocfs2_figure_dirent_hole(de);
+			if (this_hole > largest_hole)
+				largest_hole = this_hole;
+		}
+
+		de_buf += le16_to_cpu(de->rec_len);
+		de = (struct ocfs2_dir_entry *)de_buf;
+	} while (de_buf < limit);
+
+	return largest_hole;
+}
+
 static void ocfs2_dx_leaf_remove_entry(struct ocfs2_dx_leaf *dx_leaf, int index)
 {
 	int num_used = le16_to_cpu(dx_leaf->dl_num_used);

@@ -891,12 +1013,17 @@ clear:
 }
 
 static int ocfs2_delete_entry_dx(handle_t *handle, struct inode *dir,
+				 struct buffer_head *dir_di_bh,
 				 struct ocfs2_dir_lookup_result *lookup)
 {
-	int ret, index;
+	int ret, index, max_rec_len;
 	struct buffer_head *leaf_bh = lookup->dl_leaf_bh;
+	struct buffer_head *dx_root_bh = NULL;
 	struct ocfs2_dx_leaf *dx_leaf;
 	struct ocfs2_dx_entry *dx_entry = lookup->dl_dx_entry;
+	struct ocfs2_dir_block_trailer *trailer;
+	struct ocfs2_dx_root_block *uninitialized_var(dx_root);
+	struct ocfs2_dinode *di = (struct ocfs2_dinode *)dir_di_bh->b_data;
 
 	dx_leaf = (struct ocfs2_dx_leaf *) lookup->dl_dx_leaf_bh->b_data;
 	/* Neither of these are a disk corruption - that should have

@@ -914,6 +1041,25 @@ static int ocfs2_delete_entry_dx(handle_t *handle, struct inode *dir,
 		return -EIO;
 	}
 
+	trailer = ocfs2_trailer_from_bh(leaf_bh, dir->i_sb);
+	if (trailer->db_free_rec_len == 0) {
+		/* We'll have to put this block on the free list. */
+		ret = ocfs2_dx_dir_read_root(dir, di, &dx_root_bh);
+		if (ret) {
+			mlog_errno(ret);
+			goto out;
+		}
+
+		ret = ocfs2_journal_access(handle, dir, dx_root_bh,
+					   OCFS2_JOURNAL_ACCESS_WRITE);
+		if (ret) {
+			mlog_errno(ret);
+			goto out;
+		}
+
+		dx_root = (struct ocfs2_dx_root_block *)dx_root_bh->b_data;
+	}
+
 	mlog(0, "Dir %llu: delete entry at index: %d\n",
 	     (unsigned long long)OCFS2_I(dir)->ip_blkno, index);
 

@@ -938,11 +1084,22 @@ static int ocfs2_delete_entry_dx(handle_t *handle, struct inode *dir,
 		goto out;
 	}
 
+	max_rec_len = ocfs2_find_max_rec_len(dir->i_sb, leaf_bh);
+	trailer->db_free_rec_len = cpu_to_le16(max_rec_len);
+	if (dx_root_bh) {
+		trailer->db_free_next = dx_root->dr_free_blk;
+		dx_root->dr_free_blk = cpu_to_le64(leaf_bh->b_blocknr);
+		ocfs2_journal_dirty(handle, dx_root_bh);
+	}
+	/* leaf_bh was journal_accessed for us in __ocfs2_delete_entry */
+	ocfs2_journal_dirty(handle, leaf_bh);
+
 	ocfs2_dx_leaf_remove_entry(dx_leaf, index);
 
 	ocfs2_journal_dirty(handle, lookup->dl_dx_leaf_bh);
 
 out:
+	brelse(dx_root_bh);
 	return ret;
 }
 

@@ -988,10 +1145,11 @@ static inline int ocfs2_delete_entry_el(handle_t *handle,
  */
 int ocfs2_delete_entry(handle_t *handle,
 		       struct inode *dir,
+		       struct buffer_head *dir_di_bh,
 		       struct ocfs2_dir_lookup_result *lookup)
 {
 	if (ocfs2_dir_indexed(dir))
-		return ocfs2_delete_entry_dx(handle, dir, lookup);
+		return ocfs2_delete_entry_dx(handle, dir, dir_di_bh, lookup);
 
 	if (OCFS2_I(dir)->ip_dyn_features & OCFS2_INLINE_DATA_FL)
 		return ocfs2_delete_entry_id(handle, dir, lookup->dl_entry,

@@ -1078,6 +1236,57 @@ static int ocfs2_dx_dir_leaf_insert(struct inode *dir, handle_t *handle,
 					  lookup->dl_dx_leaf_bh);
 }
 
+static void ocfs2_remove_block_from_free_list(struct inode *dir,
+				       handle_t *handle,
+				       struct ocfs2_dir_lookup_result *lookup)
+{
+	struct ocfs2_dir_block_trailer *trailer, *prev;
+	struct ocfs2_dx_root_block *dx_root;
+	struct buffer_head *prev_bh = lookup->dl_prev_leaf_bh;
+
+	trailer = ocfs2_trailer_from_bh(lookup->dl_leaf_bh, dir->i_sb);
+
+	if (lookup->dl_prev_is_dx_root) {
+		dx_root = (struct ocfs2_dx_root_block *)prev_bh->b_data;
+		dx_root->dr_free_blk = trailer->db_free_next;
+	} else {
+		prev = ocfs2_trailer_from_bh(prev_bh, dir->i_sb);
+		prev->db_free_next = trailer->db_free_next;
+	}
+
+	trailer->db_free_rec_len = cpu_to_le16(0);
+	trailer->db_free_next = cpu_to_le64(0);
+
+	ocfs2_journal_dirty(handle, prev_bh);
+	ocfs2_journal_dirty(handle, lookup->dl_leaf_bh);
+}
+
+/*
+ * This expects that a journal write has been reserved on
+ * lookup->dl_prev_leaf_bh
+ */
+static void ocfs2_recalc_free_list(struct inode *dir, handle_t *handle,
+				   struct ocfs2_dir_lookup_result *lookup)
+{
+	int max_rec_len;
+	struct ocfs2_dir_block_trailer *trailer;
+
+	/* Walk dl_leaf_bh to figure out what the new free rec_len is. */
+	max_rec_len = ocfs2_find_max_rec_len(dir->i_sb, lookup->dl_leaf_bh);
+	if (max_rec_len) {
+		/*
+		 * There's still room in this block, so no need to remove it
+		 * from the free list. In this case, we just want to update
+		 * the rec len accounting.
+		 */
+		trailer = ocfs2_trailer_from_bh(lookup->dl_leaf_bh, dir->i_sb);
+		trailer->db_free_rec_len = cpu_to_le16(max_rec_len);
+		ocfs2_journal_dirty(handle, lookup->dl_leaf_bh);
+	} else {
+		ocfs2_remove_block_from_free_list(dir, handle, lookup);
+	}
+}
+
 /* we don't always have a dentry for what we want to add, so people
  * like orphan dir can call this instead.
  *

@@ -1106,7 +1315,23 @@ int __ocfs2_add_entry(handle_t *handle,
 	if (!namelen)
 		return -EINVAL;
 
-	if (OCFS2_I(dir)->ip_dyn_features & OCFS2_INLINE_DATA_FL) {
+	if (ocfs2_dir_indexed(dir)) {
+		/*
+		 * An indexed dir may require that we update the free space
+		 * list. Reserve a write to the previous node in the list so
+		 * that we don't fail later.
+		 *
+		 * XXX: This can be either a dx_root_block, or an unindexed
+		 * directory tree leaf block.
+		 */
+		retval = ocfs2_journal_access(handle, dir,
+					      lookup->dl_prev_leaf_bh,
+					      OCFS2_JOURNAL_ACCESS_WRITE);
+		if (retval) {
+			mlog_errno(retval);
+			return retval;
+		}
+	} else if (OCFS2_I(dir)->ip_dyn_features & OCFS2_INLINE_DATA_FL) {
 		data_start = di->id2.i_data.id_data;
 		size = i_size_read(dir);
 

@@ -1131,6 +1356,9 @@ int __ocfs2_add_entry(handle_t *handle,
 			goto bail;
 		}
 
+		if (ocfs2_skip_dir_trailer(dir, de, offset, size))
+			goto next;
+
 		if (ocfs2_dirent_would_fit(de, rec_len)) {
 			dir->i_mtime = dir->i_ctime = CURRENT_TIME;
 			retval = ocfs2_mark_inode_dirty(handle, dir, parent_fe_bh);

@@ -1171,11 +1399,15 @@ int __ocfs2_add_entry(handle_t *handle,
 			de->name_len = namelen;
 			memcpy(de->name, name, namelen);
 
+			if (ocfs2_dir_indexed(dir))
+				ocfs2_recalc_free_list(dir, handle, lookup);
+
 			dir->i_version++;
 			status = ocfs2_journal_dirty(handle, insert_bh);
 			retval = 0;
 			goto bail;
 		}
+next:
 		offset += le16_to_cpu(de->rec_len);
 		de = (struct ocfs2_dir_entry *) ((char *) de + le16_to_cpu(de->rec_len));
 	}

@@ -1609,9 +1841,15 @@ int ocfs2_empty_dir(struct inode *inode)
 	return !priv.seen_other;
 }
 
-static void ocfs2_fill_initial_dirents(struct inode *inode,
-				       struct inode *parent,
-				       char *start, unsigned int size)
+/*
+ * Fills "." and ".." dirents in a new directory block. Returns dirent for
+ * "..", which might be used during creation of a directory with a trailing
+ * header. It is otherwise safe to ignore the return code.
+ */
+static struct ocfs2_dir_entry *ocfs2_fill_initial_dirents(struct inode *inode,
+							  struct inode *parent,
+							  char *start,
+							  unsigned int size)
 {
 	struct ocfs2_dir_entry *de = (struct ocfs2_dir_entry *)start;
 

@@ -1628,6 +1866,8 @@ static void ocfs2_fill_initial_dirents(struct inode *inode,
 	de->name_len = 2;
 	strcpy(de->name, "..");
 	ocfs2_set_de_type(de, S_IFDIR);
+
+	return de;
 }
 
 /*

@@ -1681,10 +1921,15 @@ static int ocfs2_fill_new_dir_el(struct ocfs2_super *osb,
 				 struct buffer_head **ret_new_bh)
 {
 	int status;
+	unsigned int size = osb->sb->s_blocksize;
 	struct buffer_head *new_bh = NULL;
+	struct ocfs2_dir_entry *de;
 
 	mlog_entry_void();
 
+	if (ocfs2_supports_dir_trailer(osb))
+		size = ocfs2_dir_trailer_blk_off(parent->i_sb);
+
 	status = ocfs2_do_extend_dir(osb->sb, handle, inode, fe_bh,
 				     data_ac, NULL, &new_bh);
 	if (status < 0) {

@@ -1702,8 +1947,11 @@ static int ocfs2_fill_new_dir_el(struct ocfs2_super *osb,
 	}
 	memset(new_bh->b_data, 0, osb->sb->s_blocksize);
 
-	ocfs2_fill_initial_dirents(inode, parent, new_bh->b_data,
-				   osb->sb->s_blocksize);
+	de = ocfs2_fill_initial_dirents(inode, parent, new_bh->b_data, size);
+
+	if (ocfs2_supports_dir_trailer(osb))
+		ocfs2_init_dir_trailer(parent->i_sb, new_bh,
+				       le16_to_cpu(de->rec_len));
 
 	status = ocfs2_journal_dirty(handle, new_bh);
 	if (status < 0) {

@@ -1735,6 +1983,7 @@ bail:
 static int ocfs2_dx_dir_attach_index(struct ocfs2_super *osb,
 				     handle_t *handle, struct inode *dir,
 				     struct buffer_head *di_bh,
+				     struct buffer_head *dirdata_bh,
 				     struct ocfs2_alloc_context *meta_ac,
 				     struct buffer_head **ret_dx_root_bh)
 {

@@ -1781,6 +2030,7 @@ static int ocfs2_dx_dir_attach_index(struct ocfs2_super *osb,
 	dx_root->dr_dir_blkno = cpu_to_le64(OCFS2_I(dir)->ip_blkno);
 	dx_root->dr_list.l_count =
 		cpu_to_le16(ocfs2_extent_recs_per_dx_root(osb->sb));
+	dx_root->dr_free_blk = cpu_to_le64(dirdata_bh->b_blocknr);
 
 	ret = ocfs2_journal_dirty(handle, dx_root_bh);
 	if (ret)

@@ -2017,8 +2267,8 @@ static int ocfs2_fill_new_dir_dx(struct ocfs2_super *osb,
 		goto out;
 	}
 
-	ret = ocfs2_dx_dir_attach_index(osb, handle, inode, di_bh, meta_ac,
-					&dx_root_bh);
+	ret = ocfs2_dx_dir_attach_index(osb, handle, inode, di_bh, leaf_bh,
+					meta_ac, &dx_root_bh);
 	if (ret) {
 		mlog_errno(ret);
 		goto out;

@@ -2104,24 +2354,55 @@ out:
 	return ret;
 }
 
-static void ocfs2_expand_last_dirent(char *start, unsigned int old_size,
-				     unsigned int new_size)
+/*
+ * Expand rec_len of the rightmost dirent in a directory block so that it
+ * contains the end of our valid space for dirents. We do this during
+ * expansion from an inline directory to one with extents. The first dir block
+ * in that case is taken from the inline data portion of the inode block.
+ *
+ * This will also return the largest amount of contiguous space for a dirent
+ * in the block. That value is *not* necessarily the last dirent, even after
+ * expansion. The directory indexing code wants this value for free space
+ * accounting. We do this here since we're already walking the entire dir
+ * block.
+ */
+static unsigned int ocfs2_expand_last_dirent(char *start, unsigned int old_size,
+					     struct super_block *sb)
 {
 	struct ocfs2_dir_entry *de;
 	struct ocfs2_dir_entry *prev_de;
 	char *de_buf, *limit;
-	unsigned int bytes = new_size - old_size;
+	unsigned int new_size = sb->s_blocksize;
+	unsigned int bytes, this_hole;
+	unsigned int largest_hole = 0;
+
+	if (ocfs2_supports_indexed_dirs(OCFS2_SB(sb)))
+		new_size = ocfs2_dir_trailer_blk_off(sb);
+
+	bytes = new_size - old_size;
 
 	limit = start + old_size;
 	de_buf = start;
 	de = (struct ocfs2_dir_entry *)de_buf;
 	do {
+		this_hole = ocfs2_figure_dirent_hole(de);
+		if (this_hole > largest_hole)
+			largest_hole = this_hole;
+
 		prev_de = de;
 		de_buf += le16_to_cpu(de->rec_len);
 		de = (struct ocfs2_dir_entry *)de_buf;
 	} while (de_buf < limit);
 
 	le16_add_cpu(&prev_de->rec_len, bytes);
+
+	/* We need to double check this after modification of the final
+	 * dirent. */
+	this_hole = ocfs2_figure_dirent_hole(prev_de);
+	if (this_hole > largest_hole)
+		largest_hole = this_hole;
+
+	return largest_hole;
 }
 
 /*

@@ -2135,6 +2416,7 @@ static void ocfs2_expand_last_dirent(char *start, unsigned int old_size,
 static int ocfs2_expand_inline_dir(struct inode *dir, struct buffer_head *di_bh,
 				   unsigned int blocks_wanted,
 				   struct ocfs2_dir_lookup_result *lookup,
+				   struct buffer_head **ret_dx_root_bh,
 				   struct buffer_head **first_block_bh)
 {
 	int ret, i, num_dx_leaves = 0, credits = OCFS2_INLINE_TO_EXTENTS_CREDITS;

@@ -2262,8 +2544,16 @@ static int ocfs2_expand_inline_dir(struct inode *dir, struct buffer_head *di_bh,
 	memcpy(dirdata_bh->b_data, di->id2.i_data.id_data, i_size_read(dir));
 	memset(dirdata_bh->b_data + i_size_read(dir), 0,
 	       sb->s_blocksize - i_size_read(dir));
-	ocfs2_expand_last_dirent(dirdata_bh->b_data, i_size_read(dir),
-				 sb->s_blocksize);
+	i = ocfs2_expand_last_dirent(dirdata_bh->b_data, i_size_read(dir), sb);
+	if (ocfs2_supports_dir_trailer(osb)) {
+		/*
+		 * Prepare the dir trailer up front. It will otherwise look
+		 * like a valid dirent. Even if inserting the index fails
+		 * (unlikely), then all we'll have done is given first dir
+		 * block a small amount of fragmentation.
+		 */
+		ocfs2_init_dir_trailer(sb, dirdata_bh, i);
+	}
 
 	ret = ocfs2_journal_dirty(handle, dirdata_bh);
 	if (ret) {

@@ -2334,7 +2624,8 @@ static int ocfs2_expand_inline_dir(struct inode *dir, struct buffer_head *di_bh,
 
 	if (ocfs2_supports_indexed_dirs(osb)) {
 		ret = ocfs2_dx_dir_attach_index(osb, handle, dir, di_bh,
-						meta_ac, &dx_root_bh);
+						dirdata_bh, meta_ac,
+						&dx_root_bh);
 		if (ret) {
 			mlog_errno(ret);
 			goto out_commit;

@@ -2381,6 +2672,8 @@ static int ocfs2_expand_inline_dir(struct inode *dir, struct buffer_head *di_bh,
 					    &lookup->dl_hinfo);
 		get_bh(dx_leaves[off]);
 		lookup->dl_dx_leaf_bh = dx_leaves[off];
+		*ret_dx_root_bh = dx_root_bh;
+		dx_root_bh = NULL;
 	}
 
 out_commit:

@@ -2463,12 +2756,15 @@ bail:
  * is to be turned into an extent based one. The size of the dirent to
  * insert might be larger than the space gained by growing to just one
  * block, so we may have to grow the inode by two blocks in that case.
+ *
+ * If the directory is already indexed, dx_root_bh must be provided.
  */
 static int ocfs2_extend_dir(struct ocfs2_super *osb,
 			    struct inode *dir,
 			    struct buffer_head *parent_fe_bh,
 			    unsigned int blocks_wanted,
 			    struct ocfs2_dir_lookup_result *lookup,
+			    struct buffer_head *dx_root_bh,
 			    struct buffer_head **new_de_bh)
 {
 	int status = 0;

@@ -2486,9 +2782,19 @@ static int ocfs2_extend_dir(struct ocfs2_super *osb,
 
 	mlog_entry_void();
 
+	if (dx_root_bh)
+		get_bh(dx_root_bh);
+
 	if (OCFS2_I(dir)->ip_dyn_features & OCFS2_INLINE_DATA_FL) {
+		/*
+		 * This would be a code error as an inline directory should
+		 * never have an index root.
+		 */
+		BUG_ON(dx_root_bh);
+
 		status = ocfs2_expand_inline_dir(dir, parent_fe_bh,
 						 blocks_wanted, lookup,
+						 &dx_root_bh,
 						 &new_bh);
 		if (status) {
 			mlog_errno(status);

@@ -2558,6 +2864,10 @@ static int ocfs2_extend_dir(struct ocfs2_super *osb,
 	}
 
 do_extend:
+	if (ocfs2_dir_indexed(dir))
+		credits++; /* For attaching the new dirent block to the
+			    * dx_root */
+
 	down_write(&OCFS2_I(dir)->ip_alloc_sem);
 	drop_alloc_sem = 1;
 

@@ -2585,9 +2895,25 @@ do_extend:
 		goto bail;
 	}
 	memset(new_bh->b_data, 0, sb->s_blocksize);
+
 	de = (struct ocfs2_dir_entry *) new_bh->b_data;
 	de->inode = 0;
-	de->rec_len = cpu_to_le16(sb->s_blocksize);
+	if (ocfs2_dir_has_trailer(dir)) {
+		de->rec_len = ocfs2_dir_trailer_blk_off(sb);
+
+		ocfs2_init_dir_trailer(sb, new_bh, le16_to_cpu(de->rec_len));
+
+		if (ocfs2_dir_indexed(dir)) {
+			status = ocfs2_dx_dir_link_trailer(dir, handle,
+							   dx_root_bh, new_bh);
+			if (status) {
+				mlog_errno(status);
+				goto bail;
+			}
+		}
+	} else {
+		de->rec_len = cpu_to_le16(sb->s_blocksize);
+	}
 	status = ocfs2_journal_dirty(handle, new_bh);
 	if (status < 0) {
 		mlog_errno(status);

@@ -2618,6 +2944,7 @@ bail:
 		ocfs2_free_alloc_context(meta_ac);
 
 	brelse(new_bh);
+	brelse(dx_root_bh);
 
 	mlog_exit(status);
 	return status;

@@ -2629,11 +2956,21 @@ static int ocfs2_find_dir_space_id(struct inode *dir, struct buffer_head *di_bh,
 				   unsigned int *blocks_wanted)
 {
 	int ret;
+	struct super_block *sb = dir->i_sb;
 	struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data;
 	struct ocfs2_dir_entry *de, *last_de = NULL;
 	char *de_buf, *limit;
 	unsigned long offset = 0;
-	unsigned int rec_len, new_rec_len;
+	unsigned int rec_len, new_rec_len, free_space = dir->i_sb->s_blocksize;
+
+	/*
+	 * This calculates how many free bytes we'd have in block zero, should
+	 * this function force expansion to an extent tree.
+	 */
+	if (ocfs2_supports_indexed_dirs(OCFS2_SB(sb)))
+		free_space = ocfs2_dir_trailer_blk_off(sb) - i_size_read(dir);
+	else
+		free_space = dir->i_sb->s_blocksize - i_size_read(dir);
 
 	de_buf = di->id2.i_data.id_data;
 	limit = de_buf + i_size_read(dir);

@@ -2650,6 +2987,11 @@ static int ocfs2_find_dir_space_id(struct inode *dir, struct buffer_head *di_bh,
 			ret = -EEXIST;
 			goto out;
 		}
+		/*
+		 * No need to check for a trailing dirent record here as
+		 * they're not used for inline dirs.
+		 */
+
 		if (ocfs2_dirent_would_fit(de, rec_len)) {
 			/* Ok, we found a spot. Return this bh and let
 			 * the caller actually fill it in. */

@@ -2670,7 +3012,7 @@ static int ocfs2_find_dir_space_id(struct inode *dir, struct buffer_head *di_bh,
 	 * dirent can be found.
 	 */
 	*blocks_wanted = 1;
-	new_rec_len = le16_to_cpu(last_de->rec_len) + (dir->i_sb->s_blocksize - i_size_read(dir));
+	new_rec_len = le16_to_cpu(last_de->rec_len) + free_space;
 	if (new_rec_len < (rec_len + OCFS2_DIR_REC_LEN(last_de->name_len)))
 		*blocks_wanted = 2;
 

@@ -2730,6 +3072,11 @@ static int ocfs2_find_dir_space_el(struct inode *dir, const char *name,
 			status = -EEXIST;
 			goto bail;
 		}
+
+		if (ocfs2_skip_dir_trailer(dir, de, offset,
+					   dir->i_sb->s_blocksize))
+			goto next;
+
 		if (ocfs2_dirent_would_fit(de, rec_len)) {
 			/* Ok, we found a spot. Return this bh and let
 			 * the caller actually fill it in. */

@@ -2738,6 +3085,7 @@ static int ocfs2_find_dir_space_el(struct inode *dir, const char *name,
 			status = 0;
 			goto bail;
 		}
+next:
 		offset += le16_to_cpu(de->rec_len);
 		de = (struct ocfs2_dir_entry *)((char *) de + le16_to_cpu(de->rec_len));
 	}

@@ -3130,25 +3478,18 @@ out:
 }
 
 static int ocfs2_find_dir_space_dx(struct ocfs2_super *osb, struct inode *dir,
-				   struct buffer_head *di_bh, const char *name,
-				   int namelen,
+				   struct buffer_head *di_bh,
+				   struct buffer_head *dx_root_bh,
+				   const char *name, int namelen,
 				   struct ocfs2_dir_lookup_result *lookup)
 {
 	int ret, rebalanced = 0;
-	struct buffer_head *dx_root_bh = NULL;
 	struct ocfs2_dx_root_block *dx_root;
 	struct buffer_head *dx_leaf_bh = NULL;
 	struct ocfs2_dx_leaf *dx_leaf;
-	struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data;
 	u64 blkno;
 	u32 leaf_cpos;
 
-	ret = ocfs2_dx_dir_read_root(dir, di, &dx_root_bh);
-	if (ret) {
-		mlog_errno(ret);
-		goto out;
-	}
-
 	dx_root = (struct ocfs2_dx_root_block *)dx_root_bh->b_data;
 
 restart_search:

@@ -3211,6 +3552,125 @@ restart_search:
 
 out:
 	brelse(dx_leaf_bh);
+	return ret;
+}
+
+static int ocfs2_search_dx_free_list(struct inode *dir,
+				     struct buffer_head *dx_root_bh,
+				     int namelen,
+				     struct ocfs2_dir_lookup_result *lookup)
+{
+	int ret = -ENOSPC;
+	struct buffer_head *leaf_bh = NULL, *prev_leaf_bh = NULL;
+	struct ocfs2_dir_block_trailer *db;
+	u64 next_block;
+	int rec_len = OCFS2_DIR_REC_LEN(namelen);
+	struct ocfs2_dx_root_block *dx_root;
+
+	dx_root = (struct ocfs2_dx_root_block *)dx_root_bh->b_data;
+	next_block = le64_to_cpu(dx_root->dr_free_blk);
+
+	while (next_block) {
+		brelse(prev_leaf_bh);
+		prev_leaf_bh = leaf_bh;
+		leaf_bh = NULL;
+
+		ret = ocfs2_read_block(dir, next_block, &leaf_bh);
+		if (ret) {
+			mlog_errno(ret);
+			goto out;
+		}
+
+		db = ocfs2_trailer_from_bh(leaf_bh, dir->i_sb);
+		if (rec_len <= le16_to_cpu(db->db_free_rec_len)) {
+			lookup->dl_leaf_bh = leaf_bh;
+			if (prev_leaf_bh)
+				lookup->dl_prev_leaf_bh = prev_leaf_bh;
+			else {
+				lookup->dl_prev_leaf_bh = dx_root_bh;
+				lookup->dl_prev_is_dx_root = 1;
+			}
+			leaf_bh = NULL;
+			prev_leaf_bh = NULL;
+			break;
+		}
+
+		next_block = le64_to_cpu(db->db_free_next);
+	}
+
+	if (!next_block)
+		ret = -ENOSPC;
+
+out:
+
+	brelse(leaf_bh);
+	brelse(prev_leaf_bh);
+	return ret;
+}
+
+static int ocfs2_prepare_dx_dir_for_insert(struct inode *dir, 
+					   struct buffer_head *di_bh,
+					   const char *name,
+					   int namelen,
+					   struct ocfs2_dir_lookup_result *lookup)
+{
+	int ret;
+	struct ocfs2_super *osb = OCFS2_SB(dir->i_sb);
+	struct buffer_head *dx_root_bh = NULL;
+	struct buffer_head *leaf_bh = NULL;
+	struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data;
+
+	ocfs2_dx_dir_name_hash(dir, name, namelen, &lookup->dl_hinfo);
+
+	ret = ocfs2_dx_dir_read_root(dir, di, &dx_root_bh);
+	if (ret) {
+		mlog_errno(ret);
+		goto out;
+	}
+
+	/*
+	 * Insert preparation for an indexed directory is split into two
+	 * steps. The call to find_dir_space_dx reserves room in the index for
+	 * an additional item. If we run out of space there, it's a real error
+	 * we can't continue on.
+	 */
+	ret = ocfs2_find_dir_space_dx(osb, dir, di_bh, dx_root_bh, name,
+				      namelen, lookup);
+	if (ret) {
+		mlog_errno(ret);
+		goto out;
+	}
+
+	/*
+	 * Next, we need to find space in the unindexed tree. This call
+	 * searches using the free space linked list. If the unindexed tree
+	 * lacks sufficient space, we'll expand it below. The expansion code
+	 * is smart enough to add any new blocks to the free space list.
+	 */
+	ret = ocfs2_search_dx_free_list(dir, dx_root_bh, namelen, lookup);
+	if (ret && ret != -ENOSPC) {
+		mlog_errno(ret);
+		goto out;
+	}
+	if (ret == -ENOSPC) {
+		ret = ocfs2_extend_dir(osb, dir, di_bh, 1, lookup, dx_root_bh,
+				       &leaf_bh);
+		if (ret) {
+			mlog_errno(ret);
+			goto out;
+		}
+
+		/*
+		 * We make the assumption here that new leaf blocks are added
+		 * to the front of our free list.
+		 */
+		get_bh(dx_root_bh);
+		lookup->dl_prev_leaf_bh = dx_root_bh;
+		lookup->dl_prev_is_dx_root = 1;
+		lookup->dl_leaf_bh = leaf_bh;
+	}
+
+out:
 	brelse(dx_root_bh);
 	return ret;
 }

@@ -3241,20 +3701,12 @@ int ocfs2_prepare_dir_for_insert(struct ocfs2_super *osb,
 		goto out;
 	}
 
-	ocfs2_dx_dir_name_hash(dir, name, namelen, &lookup->dl_hinfo);
-
 	if (ocfs2_dir_indexed(dir)) {
-		ret = ocfs2_find_dir_space_dx(osb, dir, parent_fe_bh, name,
-					      namelen, lookup);
-		if (ret) {
+		ret = ocfs2_prepare_dx_dir_for_insert(dir, parent_fe_bh,
+						      name, namelen, lookup);
+		if (ret)
 			mlog_errno(ret);
-			goto out;
-		}
-
-		/*
-		 * We intentionally fall through so that the unindexed
-		 * tree can also be prepared.
-		 */
+		goto out;
 	}
 
 	if (OCFS2_I(dir)->ip_dyn_features & OCFS2_INLINE_DATA_FL) {

@@ -3275,7 +3727,7 @@ int ocfs2_prepare_dir_for_insert(struct ocfs2_super *osb,
 		BUG_ON(bh);
 
 		ret = ocfs2_extend_dir(osb, dir, parent_fe_bh, blocks_wanted,
-				       lookup, &bh);
+				       lookup, NULL, &bh);
 		if (ret) {
 			if (ret != -ENOSPC)
 				mlog_errno(ret);
fs/ocfs2/dir.h +4 -0
index d035b75..e35689b 100644
@@ -38,6 +38,9 @@ struct ocfs2_dir_lookup_result {
 	struct buffer_head		*dl_dx_leaf_bh;
 	struct ocfs2_dx_entry		*dl_dx_entry;
 	struct ocfs2_dx_hinfo		dl_hinfo;
+
+	struct buffer_head		*dl_prev_leaf_bh;
+	int				dl_prev_is_dx_root;
 };
 void ocfs2_free_dir_lookup_result(struct ocfs2_dir_lookup_result *res);
 

@@ -46,6 +49,7 @@ int ocfs2_find_entry(const char *name, int namelen,
 		     struct ocfs2_dir_lookup_result *lookup);
 int ocfs2_delete_entry(handle_t *handle,
 		       struct inode *dir,
+		       struct buffer_head *dir_di_bh,
 		       struct ocfs2_dir_lookup_result *res);
 int __ocfs2_add_entry(handle_t *handle,
 		      struct inode *dir,
fs/ocfs2/journal.h +6 -6
index 354fd24..ba8f9bf 100644
@@ -316,8 +316,8 @@ int                  ocfs2_journal_dirty_data(handle_t *handle,
 #define OCFS2_REMOVE_EXTENT_CREDITS (OCFS2_TRUNCATE_LOG_UPDATE + OCFS2_INODE_UPDATE_CREDITS)
 
 /* data block for new dir/symlink, 2 for bitmap updates (bitmap fe +
- * bitmap block for the new bit) */
-#define OCFS2_DIR_LINK_ADDITIONAL_CREDITS (1 + 2)
+ * bitmap block for the new bit) + dx_root update for free list */
+#define OCFS2_DIR_LINK_ADDITIONAL_CREDITS (1 + 2 + 1)
 
 /* parent fe, parent block, new file entry, index leaf, inode
  * alloc fe, inode alloc group descriptor + mkdir/symlink blocks */

@@ -333,13 +333,13 @@ int                  ocfs2_journal_dirty_data(handle_t *handle,
 #define OCFS2_SIMPLE_DIR_EXTEND_CREDITS (2)
 
 /* file update (nlink, etc) + directory mtime/ctime + dir entry block
- * + index leaf */
-#define OCFS2_LINK_CREDITS  (2*OCFS2_INODE_UPDATE_CREDITS + 2)
+ * + index leaf + dx_root update for free list */
+#define OCFS2_LINK_CREDITS  (2*OCFS2_INODE_UPDATE_CREDITS + 3)
 
 /* inode + dir inode (if we unlink a dir), + dir entry block + orphan
- * dir inode link + dir inode index leaf */
+ * dir inode link + dir inode index leaf + dir index root */
 #define OCFS2_UNLINK_CREDITS  (2 * OCFS2_INODE_UPDATE_CREDITS + 1             \
-			      + OCFS2_LINK_CREDITS + 1)
+			      + OCFS2_LINK_CREDITS + 1 + 1)
 
 /* dinode + orphan dir dinode + inode alloc dinode + orphan dir entry +
  * inode alloc group descriptor + orphan dir index leaf */
fs/ocfs2/namei.c +5 -3
index 862c576..f726e70 100644
@@ -822,7 +822,7 @@ static int ocfs2_unlink(struct inode *dir,
 	}
 
 	/* delete the name from the parent dir */
-	status = ocfs2_delete_entry(handle, dir, &lookup);
+	status = ocfs2_delete_entry(handle, dir, parent_node_bh, &lookup);
 	if (status < 0) {
 		mlog_errno(status);
 		goto leave;

@@ -1295,7 +1295,8 @@ static int ocfs2_rename(struct inode *old_dir,
 	if (status)
 		goto bail;
 
-	status = ocfs2_delete_entry(handle, old_dir, &old_entry_lookup);
+	status = ocfs2_delete_entry(handle, old_dir, old_dir_bh,
+				    &old_entry_lookup);
 	if (status < 0) {
 		mlog_errno(status);
 		goto bail;

@@ -1868,7 +1869,8 @@ int ocfs2_orphan_del(struct ocfs2_super *osb,
 	}
 
 	/* remove it from the orphan directory */
-	status = ocfs2_delete_entry(handle, orphan_dir_inode, &lookup);
+	status = ocfs2_delete_entry(handle, orphan_dir_inode, orphan_dir_bh,
+				    &lookup);
 	if (status < 0) {
 		mlog_errno(status);
 		goto leave;
fs/ocfs2/ocfs2_fs.h +30 -2
index c723d5e..2e19869 100644
@@ -67,6 +67,7 @@
 #define OCFS2_XATTR_BLOCK_SIGNATURE	"XATTR01"
 #define OCFS2_DX_ROOT_SIGNATURE		"DXDIR01"
 #define OCFS2_DX_LEAF_SIGNATURE		"DXLEAF1"
+#define OCFS2_DIR_TRAILER_SIGNATURE	"DIRTRL1"
 
 /* Compatibility flags */
 #define OCFS2_HAS_COMPAT_FEATURE(sb,mask)			\

@@ -94,7 +95,8 @@
 					 | OCFS2_FEATURE_INCOMPAT_INLINE_DATA \
 					 | OCFS2_FEATURE_INCOMPAT_EXTENDED_SLOT_MAP \
 					 | OCFS2_FEATURE_INCOMPAT_USERSPACE_STACK \
-					 | OCFS2_FEATURE_INCOMPAT_XATTR)
+					 | OCFS2_FEATURE_INCOMPAT_XATTR	\
+					 | OCFS2_FEATURE_INCOMPAT_INDEXED_DIRS)
 #define OCFS2_FEATURE_RO_COMPAT_SUPP	OCFS2_FEATURE_RO_COMPAT_UNWRITTEN
 
 /*

@@ -716,6 +718,30 @@ struct ocfs2_dir_entry {
 } __attribute__ ((packed));
 
 /*
+ * Per-block record for the unindexed directory btree. This is carefully
+ * crafted so that the rec_len and name_len records of an ocfs2_dir_entry are
+ * mirrored. That way, the directory manipulation code needs a minimal amount
+ * of update.
+ *
+ * NOTE: Keep this structure aligned to a multiple of 4 bytes.
+ */
+struct ocfs2_dir_block_trailer {
+/*00*/	__le64		db_compat_inode;	/* Always zero. Was inode */
+
+	__le16		db_compat_rec_len;	/* Backwards compatible with
+						 * ocfs2_dir_entry. */
+	__u8		db_compat_name_len;	/* Always zero. Was name_len */
+	__u8		db_reserved0;
+	__le16		db_reserved1;
+	__le16		db_free_rec_len;	/* Size of largest empty hole
+						 * in this block. */
+	__u8		db_signature[8];	/* Signature for verification */
+	__le64		db_reserved2;
+	__le64		db_free_next;		/* Next block in list */
+	__le64		db_csum;		/* Checksum (unused) */
+};
+
+/*
  * A directory indexing block. Each indexed directory has one of these,
  * pointed to by ocfs2_dinode.
  *

@@ -738,7 +764,9 @@ struct ocfs2_dx_root_block {
 	__le32		dr_reserved1;
 	__le64		dr_dir_blkno;		/* Pointer to parent inode */
 	__le64		dr_reserved2;
-	__le64		dr_reserved3[16];
+	__le64		dr_free_blk;		/* Pointer to head of free
+						 * unindexed block list. */
+	__le64		dr_reserved3[15];
 	struct ocfs2_extent_list	dr_list; /* Keep this aligned to 128
 						  * bits for maximum space
 						  * efficiency. */
Signature · 1 line
1.5.4.1
#8 lore raw

PATCH 4/4 ocfs2: Introduce dir free space list

Quoted 9 lines · Mark Fasheh

The only operation which doesn't get faster with directory indexing is insert, which still has to walk the entire unindexed directory portion to find a free block. This patch provides an improvement in directory insert performance by maintaining a singly linked list of directory leaf blocks which have space for additional dirents.

As the disk format is now finalized, we also turn on directory indexing support.

Signed-off-by Mark Fasheh <[email protected]>

Looks good. I realize that you're going to add the versioning
support. And that on-disk trailer structure needs offset annotation.

Joel

Signature · 10 lines
"And yet I find,
 And yet I find repeating in my head.
 If I can't be my own, 
 I'd feel better dead."

Joel Becker
Principal Software Developer
Oracle
E-mail: joel.becker at oracle.com
Phone: (650) 506-8127
#9 lore raw

cover ocfs2: Directory indexing support

In reply to Mark Fasheh
Quoted 2 lines · Mark Fasheh

The following patches implement indexed directory support in Ocfs2, mostly according to the design doc I wrote up a while ago:

<snip>

Quoted 4 lines

Very basic ocfs2-tools patches will also follow in the next couple days or so. This will mostly be mkfs and debugfs support. I think it might be best to build the libocfs2 support on top of whatever patches we have for extended attributes as the tree code will have to change for that.

I agree. I hope we see those soon. We have a lot of stuff now
that isn't fully tools supported.

Quoted 9 lines

Open questions:

Should we just drop the signature in ocfs2_dir_block_trailer? I can't help but feel that it might have limited usefulness as it's not at the front of the block (like the rest of our signatures) and that the nature of a dirent block might be that we can't trust the existence of the signature to actually mean there's a valid ocfs2_dir_block_trailer there. The answer is probably still to keep the signature, but I thought I'd throw this out there.

I like having it, because it sticks right out in bvi/hexdump.
With any of our metadata structures, we generally have to figure out if they are "really" a such-and-such by hand after validating the signature. But if we start from the knowledge "block N is or is not supposed to be of type X", the signature is a quick way to see if something is wrong.

Quoted 5 lines

Is it worth storing index (ocfs2_dx_entry) records inline inside of ocfs2_dx_root_block and only growing out to a tree when we exhaust the available space? Running the math, we could store between 18 (512 byte blocks) and 242 (4k blocksize) records in the space occupied by the extent list.

I'd say we should do _something_. Many (most?) directories have
less than 242 entries, and this saves us a sync read on any cold-cache lookup. What about a way we could readahead the first index leaf instead? I suppose we could store "first leaf" on the inode right next to the dx root, and then fire of readahead for the first leaf right before we sync-read the dx_root. If the directory fits in one index leaf, that first leaf is already in our cache. If not, we just ignore it. For 4k/4k, this is a single block. Then the dx_root doesn't have to have special logic for inline-entries.

Quoted 6 lines

In order to keep the code simple, I've gone with a single linked-list for the free dirent block search. There might be situations though, where this performs poorly. My plan is to version the free dirent block list so that we can 'upgrade' it (maybe to multiple lists) at a later point. Old versions would fall back to the less optimized unindexed leaf search. That way the upgrade would be seamless to the user.

I always liked this. Wouldn't this mean that old versions might
leave 'full' dirblocks on the free list?

Joel

Signature · 9 lines
"There are some experiences in life which should not be demanded
 twice from any man, and one of them is listening to the Brahms Requiem."
        - George Bernard Shaw

Joel Becker
Principal Software Developer
Oracle
E-mail: joel.becker at oracle.com
Phone: (650) 506-8127