+static int dx_leaf_sort_cmp(const void *a, const void *b)
+{
+ const struct ocfs2_dx_entry *entry1 = a;
+ const struct ocfs2_dx_entry *entry2 = b;
+ u32 major_hash1 = le32_to_cpu(entry1->dx_major_hash);
+ u32 major_hash2 = le32_to_cpu(entry2->dx_major_hash);
+ u32 minor_hash1 = le32_to_cpu(entry1->dx_minor_hash);
+ u32 minor_hash2 = le32_to_cpu(entry2->dx_minor_hash);
+
+ if (major_hash1 > major_hash2)
+ return 1;
+ if (major_hash1 < major_hash2)
+ return -1;
+
+ /*
+ * It is not strictly necessary to sort by minor
+ */
+ if (minor_hash1 > minor_hash2)
+ return 1;
+ if (minor_hash1 < minor_hash2)
+ return -1;
+ return 0;
+}
+
+static void dx_leaf_sort_swap(void *a, void *b, int size)
+{
+ struct ocfs2_dx_entry *entry1 = a;
+ struct ocfs2_dx_entry *entry2 = b;
+ struct ocfs2_dx_entry tmp;
+
+ BUG_ON(size != sizeof(*entry1));
+
+ tmp = *entry1;
+ *entry1 = *entry2;
+ *entry2 = tmp;
+}
+
+static int ocfs2_dx_leaf_same_major(struct ocfs2_dx_leaf *dx_leaf)
+{
+ struct ocfs2_dx_entry_list *dl_list = &dx_leaf->dl_list;
+ int i, num = le16_to_cpu(dl_list->de_num_used);
+
+ for (i = 0; i < (num - 1); i++) {
+ if (le32_to_cpu(dl_list->de_entries[i].dx_major_hash) !=
+ le32_to_cpu(dl_list->de_entries[i + 1].dx_major_hash))
+ return 0;
+ }
+
+ return 1;
+}
+
+/*
+ * Find the optimal value to split this leaf on. This expects the leaf
+ * entries to be in sorted order.
+ *
+ * leaf_cpos is the cpos of the leaf we're splitting. insert_hash is
+ * the hash we want to insert.
+ *
+ * This function is only concerned with the major hash - that which
+ * determines which cluster an item belongs to.
+ */
+static int ocfs2_dx_dir_find_leaf_split(struct ocfs2_dx_leaf *dx_leaf,
+ u32 leaf_cpos, u32 insert_hash,
+ u32 *split_hash)
+{
+ struct ocfs2_dx_entry_list *dl_list = &dx_leaf->dl_list;
+ int i, num_used = le16_to_cpu(dl_list->de_num_used);
+ int allsame;
+
+ /*
+ * There's a couple rare, but nasty corner cases we have to
+ * check for here. All of them involve a leaf where all value
+ * have the same hash, which is what we look for first.
+ *
+ * Most of the time, all of the above is false, and we simply
+ * pick the median value for a split.
+ */
+ allsame = ocfs2_dx_leaf_same_major(dx_leaf);
+ if (allsame) {
+ u32 val = le32_to_cpu(dl_list->de_entries[0].dx_major_hash);
+
+ if (val == insert_hash) {
+ /*
+ * No matter where we would choose to split,
+ * the new entry would want to occupy the same
+ * block as these. Since there's no space left
+ * in their existing block, we know there
+ * won't be space after the split.
+ */
+ return -ENOSPC;
+ }
+
+ if (val == leaf_cpos) {
+ /*
+ * Because val is the same as leaf_cpos (which
+ * is the smallest value this leaf can have),
+ * yet is not equal to insert_hash, then we
+ * know that insert_hash *must* be larger than
+ * val (and leaf_cpos). At least cpos+1 in value.
+ *
+ * We also know then, that there cannot be an
+ * adjacent extent (otherwise we'd be looking
+ * at it). Choosing this value gives us a
+ * chance to get some contiguousness.
+ */
+ *split_hash = leaf_cpos + 1;
+ return 0;
+ }
+
+ if (val > insert_hash) {
+ /*
+ * val can not be the same as insert hash, and
+ * also must be larger than leaf_cpos. Also,
+ * we know that there can't be a leaf between
+ * cpos and val, otherwise the entries with
+ * hash 'val' would be there.
+ */
+ *split_hash = val;
+ return 0;
+ }
+
+ *split_hash = insert_hash;
+ return 0;
+ }
+
+ /*
+ * Since the records are sorted and the checks above
+ * guaranteed that not all records in this block are the same,
+ * we simple travel forward, from the median, and pick the 1st
+ * record whose value is larger than leaf_cpos.
+ */
+ for (i = (num_used / 2); i < num_used; i++)
+ if (le32_to_cpu(dl_list->de_entries[i].dx_major_hash) >
+ leaf_cpos)
+ break;
+
+ BUG_ON(i == num_used); /* Should be impossible */
+ *split_hash = le32_to_cpu(dl_list->de_entries[i].dx_major_hash);
+ return 0;
+}
+
+/*
+ * Transfer all entries in orig_dx_leaves whose major hash is equal to or
+ * larger than split_hash into new_dx_leaves. We use a temporary
+ * buffer (tmp_dx_leaf) to make the changes to the original leaf blocks.
+ *
+ * Since the block offset inside a leaf (cluster) is a constant mask
+ * of minor_hash, we can optimize - an item at block offset X within
+ * the original cluster, will be at offset X within the new cluster.
+ */
+static void ocfs2_dx_dir_transfer_leaf(struct inode *dir, u32 split_hash,
+ handle_t *handle,
+ struct ocfs2_dx_leaf *tmp_dx_leaf,
+ struct buffer_head **orig_dx_leaves,
+ struct buffer_head **new_dx_leaves,
+ int num_dx_leaves)
+{
+ int i, j, num_used;
+ u32 major_hash;
+ struct ocfs2_dx_leaf *orig_dx_leaf, *new_dx_leaf;
+ struct ocfs2_dx_entry_list *orig_list, *new_list, *tmp_list;
+ struct ocfs2_dx_entry *dx_entry;
+
+ tmp_list = &tmp_dx_leaf->dl_list;
+
+ for (i = 0; i < num_dx_leaves; i++) {
+ orig_dx_leaf = (struct ocfs2_dx_leaf *) orig_dx_leaves[i]->b_data;
+ orig_list = &orig_dx_leaf->dl_list;
+ new_dx_leaf = (struct ocfs2_dx_leaf *) new_dx_leaves[i]->b_data;
+ new_list = &new_dx_leaf->dl_list;
+
+ num_used = le16_to_cpu(orig_list->de_num_used);
+
+ memcpy(tmp_dx_leaf, orig_dx_leaf, dir->i_sb->s_blocksize);
+ tmp_list->de_num_used = cpu_to_le16(0);
+ memset(&tmp_list->de_entries, 0, sizeof(*dx_entry)*num_used);
+
+ for (j = 0; j < num_used; j++) {
+ dx_entry = &orig_list->de_entries[j];
+ major_hash = le32_to_cpu(dx_entry->dx_major_hash);
+ if (major_hash >= split_hash)
+ ocfs2_dx_dir_leaf_insert_tail(new_dx_leaf,
+ dx_entry);
+ else
+ ocfs2_dx_dir_leaf_insert_tail(tmp_dx_leaf,
+ dx_entry);
+ }
+ memcpy(orig_dx_leaf, tmp_dx_leaf, dir->i_sb->s_blocksize);
+
+ ocfs2_journal_dirty(handle, orig_dx_leaves[i]);
+ ocfs2_journal_dirty(handle, new_dx_leaves[i]);
+ }
+}
+
+static int ocfs2_dx_dir_rebalance_credits(struct ocfs2_super *osb,
+ struct ocfs2_dx_root_block *dx_root)
+{
+ int credits = ocfs2_clusters_to_blocks(osb->sb, 2);
+
+ credits += ocfs2_calc_extend_credits(osb->sb, &dx_root->dr_list, 1);
+ credits += ocfs2_quota_trans_credits(osb->sb);
+ return credits;
+}
+
+/*
+ * Find the median value in dx_leaf_bh and allocate a new leaf to move
+ * half our entries into.
+ */
+static int ocfs2_dx_dir_rebalance(struct ocfs2_super *osb, struct inode *dir,
+ struct buffer_head *dx_root_bh,
+ struct buffer_head *dx_leaf_bh,
+ struct ocfs2_dx_hinfo *hinfo, u32 leaf_cpos,
+ u64 leaf_blkno)
+{
+ struct ocfs2_dx_leaf *dx_leaf = (struct ocfs2_dx_leaf *)dx_leaf_bh->b_data;
+ int credits, ret, i, num_used, did_quota = 0;
+ u32 cpos, split_hash, insert_hash = hinfo->major_hash;
+ u64 orig_leaves_start;
+ int num_dx_leaves;
+ struct buffer_head **orig_dx_leaves = NULL;
+ struct buffer_head **new_dx_leaves = NULL;
+ struct ocfs2_alloc_context *data_ac = NULL, *meta_ac = NULL;
+ struct ocfs2_extent_tree et;
+ handle_t *handle = NULL;
+ struct ocfs2_dx_root_block *dx_root;
+ struct ocfs2_dx_leaf *tmp_dx_leaf = NULL;
+
+ mlog(0, "DX Dir: %llu, rebalance leaf leaf_blkno: %llu insert: %u\n",
+ (unsigned long long)OCFS2_I(dir)->ip_blkno,
+ (unsigned long long)leaf_blkno, insert_hash);
+
+ ocfs2_init_dx_root_extent_tree(&et, INODE_CACHE(dir), dx_root_bh);
+
+ dx_root = (struct ocfs2_dx_root_block *)dx_root_bh->b_data;
+ /*
+ * XXX: This is a rather large limit. We should use a more
+ * realistic value.
+ */
+ if (le32_to_cpu(dx_root->dr_clusters) == UINT_MAX)
+ return -ENOSPC;
+
+ num_used = le16_to_cpu(dx_leaf->dl_list.de_num_used);
+ if (num_used < le16_to_cpu(dx_leaf->dl_list.de_count)) {
+ mlog(ML_ERROR, "DX Dir: %llu, Asked to rebalance empty leaf: "
+ "%llu, %d\n", (unsigned long long)OCFS2_I(dir)->ip_blkno,
+ (unsigned long long)leaf_blkno, num_used);
+ ret = -EIO;
+ goto out;
+ }
+
+ orig_dx_leaves = ocfs2_dx_dir_kmalloc_leaves(osb->sb, &num_dx_leaves);
+ if (!orig_dx_leaves) {
+ ret = -ENOMEM;
+ mlog_errno(ret);
+ goto out;
+ }
+
+ new_dx_leaves = ocfs2_dx_dir_kmalloc_leaves(osb->sb, NULL);
+ if (!new_dx_leaves) {
+ ret = -ENOMEM;
+ mlog_errno(ret);
+ goto out;
+ }
+
+ ret = ocfs2_lock_allocators(dir, &et, 1, 0, &data_ac, &meta_ac);
+ if (ret) {
+ if (ret != -ENOSPC)
+ mlog_errno(ret);
+ goto out;
+ }
+
+ credits = ocfs2_dx_dir_rebalance_credits(osb, dx_root);
+ handle = ocfs2_start_trans(osb, credits);
+ if (IS_ERR(handle)) {
+ ret = PTR_ERR(handle);
+ handle = NULL;
+ mlog_errno(ret);
+ goto out;
+ }
+
+ if (vfs_dq_alloc_space_nodirty(dir,
+ ocfs2_clusters_to_bytes(dir->i_sb, 1))) {
+ ret = -EDQUOT;
+ goto out_commit;
+ }
+ did_quota = 1;
+
+ ret = ocfs2_journal_access_dl(handle, INODE_CACHE(dir), dx_leaf_bh,
+ OCFS2_JOURNAL_ACCESS_WRITE);
+ if (ret) {
+ mlog_errno(ret);
+ goto out_commit;
+ }
+
+ /*
+ * This block is changing anyway, so we can sort it in place.
+ */
+ sort(dx_leaf->dl_list.de_entries, num_used,
+ sizeof(struct ocfs2_dx_entry), dx_leaf_sort_cmp,
+ dx_leaf_sort_swap);
+
+ ret = ocfs2_journal_dirty(handle, dx_leaf_bh);
+ if (ret) {
+ mlog_errno(ret);
+ goto out_commit;
+ }
+
+ ret = ocfs2_dx_dir_find_leaf_split(dx_leaf, leaf_cpos, insert_hash,
+ &split_hash);
+ if (ret) {
+ mlog_errno(ret);
+ goto out_commit;
+ }
+
+ mlog(0, "Split leaf (%u) at %u, insert major hash is %u\n",
+ leaf_cpos, split_hash, insert_hash);
+
+ /*
+ * We have to carefully order operations here. There are items
+ * which want to be in the new cluster before insert, but in
+ * order to put those items in the new cluster, we alter the
+ * old cluster. A failure to insert gets nasty.
+ *
+ * So, start by reserving writes to the old
+ * cluster. ocfs2_dx_dir_new_cluster will reserve writes on
+ * the new cluster for us, before inserting it. The insert
+ * won't happen if there's an error before that. Once the
+ * insert is done then, we can transfer from one leaf into the
+ * other without fear of hitting any error.
+ */
+
+ /*
+ * The leaf transfer wants some scratch space so that we don't
+ * wind up doing a bunch of expensive memmove().
+ */
+ tmp_dx_leaf = kmalloc(osb->sb->s_blocksize, GFP_NOFS);
+ if (!tmp_dx_leaf) {
+ ret = -ENOMEM;
+ mlog_errno(ret);
+ goto out_commit;
+ }
+
+ orig_leaves_start = ocfs2_block_to_cluster_start(dir->i_sb, leaf_blkno);
+ ret = ocfs2_read_dx_leaves(dir, orig_leaves_start, num_dx_leaves,
+ orig_dx_leaves);
+ if (ret) {
+ mlog_errno(ret);
+ goto out_commit;
+ }
+
+ for (i = 0; i < num_dx_leaves; i++) {
+ ret = ocfs2_journal_access_dl(handle, INODE_CACHE(dir),
+ orig_dx_leaves[i],
+ OCFS2_JOURNAL_ACCESS_WRITE);
+ if (ret) {
+ mlog_errno(ret);
+ goto out_commit;
+ }
+ }
+
+ cpos = split_hash;
+ ret = ocfs2_dx_dir_new_cluster(dir, &et, cpos, handle,
+ data_ac, meta_ac, new_dx_leaves,
+ num_dx_leaves);
+ if (ret) {
+ mlog_errno(ret);
+ goto out_commit;
+ }
+
+ ocfs2_dx_dir_transfer_leaf(dir, split_hash, handle, tmp_dx_leaf,
+ orig_dx_leaves, new_dx_leaves, num_dx_leaves);
+
+out_commit:
+ if (ret < 0 && did_quota)
+ vfs_dq_free_space_nodirty(dir,
+ ocfs2_clusters_to_bytes(dir->i_sb, 1));
+
+ ocfs2_commit_trans(osb, handle);
+
+out:
+ if (orig_dx_leaves || new_dx_leaves) {
+ for (i = 0; i < num_dx_leaves; i++) {
+ if (orig_dx_leaves)
+ brelse(orig_dx_leaves[i]);
+ if (new_dx_leaves)
+ brelse(new_dx_leaves[i]);
+ }
+ kfree(orig_dx_leaves);
+ kfree(new_dx_leaves);
+ }
+
+ if (meta_ac)
+ ocfs2_free_alloc_context(meta_ac);
+ if (data_ac)
+ ocfs2_free_alloc_context(data_ac);
+
+ kfree(tmp_dx_leaf);
+ return ret;
+}
+
+static int ocfs2_find_dir_space_dx(struct ocfs2_super *osb, struct inode *dir,
+ 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 ocfs2_dx_root_block *dx_root;
+ struct buffer_head *dx_leaf_bh = NULL;
+ struct ocfs2_dx_leaf *dx_leaf;
+ u64 blkno;
+ u32 leaf_cpos;
+
+ dx_root = (struct ocfs2_dx_root_block *)dx_root_bh->b_data;
+
+restart_search:
+ ret = ocfs2_dx_dir_lookup(dir, &dx_root->dr_list, &lookup->dl_hinfo,
+ &leaf_cpos, &blkno);
+ if (ret) {
+ mlog_errno(ret);
+ goto out;
+ }
+
+ ret = ocfs2_read_dx_leaf(dir, blkno, &dx_leaf_bh);
+ if (ret) {
+ mlog_errno(ret);
+ goto out;
+ }
+
+ dx_leaf = (struct ocfs2_dx_leaf *)dx_leaf_bh->b_data;
+
+ if (le16_to_cpu(dx_leaf->dl_list.de_num_used) >=
+ le16_to_cpu(dx_leaf->dl_list.de_count)) {
+ if (rebalanced) {
+ /*
+ * Rebalancing should have provided us with
+ * space in an appropriate leaf.
+ *
+ * XXX: Is this an abnormal condition then?
+ * Should we print a message here?
+ */
+ ret = -ENOSPC;
+ goto out;
+ }
+
+ ret = ocfs2_dx_dir_rebalance(osb, dir, dx_root_bh, dx_leaf_bh,
+ &lookup->dl_hinfo, leaf_cpos,
+ blkno);
+ if (ret) {
+ if (ret != -ENOSPC)
+ mlog_errno(ret);
+ goto out;
+ }
+
+ /*
+ * Restart the lookup. The rebalance might have
+ * changed which block our item fits into. Mark our
+ * progress, so we only execute this once.
+ */
+ brelse(dx_leaf_bh);
+ dx_leaf_bh = NULL;
+ rebalanced = 1;
+ goto restart_search;
+ }
+
+ lookup->dl_dx_leaf_bh = dx_leaf_bh;
+ dx_leaf_bh = NULL;
+
+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_dir_block_direct(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;
+ lookup->dl_prev_leaf_bh = prev_leaf_bh;
+ 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_expand_inline_dx_root(struct inode *dir,
+ struct buffer_head *dx_root_bh)
+{
+ int ret, num_dx_leaves, i, j, did_quota = 0;
+ struct buffer_head **dx_leaves = NULL;
+ struct ocfs2_extent_tree et;
+ u64 insert_blkno;
+ struct ocfs2_alloc_context *data_ac = NULL;
+ struct ocfs2_super *osb = OCFS2_SB(dir->i_sb);
+ handle_t *handle = NULL;
+ struct ocfs2_dx_root_block *dx_root;
+ struct ocfs2_dx_entry_list *entry_list;
+ struct ocfs2_dx_entry *dx_entry;
+ struct ocfs2_dx_leaf *target_leaf;
+
+ ret = ocfs2_reserve_clusters(osb, 1, &data_ac);
+ if (ret) {
+ mlog_errno(ret);
+ goto out;
+ }
+
+ dx_leaves = ocfs2_dx_dir_kmalloc_leaves(osb->sb, &num_dx_leaves);
+ if (!dx_leaves) {
+ ret = -ENOMEM;
+ mlog_errno(ret);
+ goto out;
+ }
+
+ handle = ocfs2_start_trans(osb, ocfs2_calc_dxi_expand_credits(osb->sb));
+ if (IS_ERR(handle)) {
+ ret = PTR_ERR(handle);
+ mlog_errno(ret);
+ goto out;
+ }
+
+ if (vfs_dq_alloc_space_nodirty(dir,
+ ocfs2_clusters_to_bytes(osb->sb, 1))) {
+ ret = -EDQUOT;
+ goto out_commit;
+ }
+ did_quota = 1;
+
+ /*
+ * We do this up front, before the allocation, so that a
+ * failure to add the dx_root_bh to the journal won't result
+ * us losing clusters.
+ */
+ ret = ocfs2_journal_access_dr(handle, INODE_CACHE(dir), dx_root_bh,
+ OCFS2_JOURNAL_ACCESS_WRITE);
+ if (ret) {
+ mlog_errno(ret);
+ goto out_commit;
+ }
+
+ ret = __ocfs2_dx_dir_new_cluster(dir, 0, handle, data_ac, dx_leaves,
+ num_dx_leaves, &insert_blkno);
+ if (ret) {
+ mlog_errno(ret);
+ goto out_commit;
+ }
+
+ /*
+ * Transfer the entries from our dx_root into the appropriate
+ * block
+ */
+ dx_root = (struct ocfs2_dx_root_block *) dx_root_bh->b_data;
+ entry_list = &dx_root->dr_entries;
+
+ for (i = 0; i < le16_to_cpu(entry_list->de_num_used); i++) {
+ dx_entry = &entry_list->de_entries[i];
+
+ j = __ocfs2_dx_dir_hash_idx(osb,
+ le32_to_cpu(dx_entry->dx_minor_hash));
+ target_leaf = (struct ocfs2_dx_leaf *)dx_leaves[j]->b_data;
+
+ ocfs2_dx_dir_leaf_insert_tail(target_leaf, dx_entry);
+
+ /* Each leaf has been passed to the journal already
+ * via __ocfs2_dx_dir_new_cluster() */
+ }
+
+ dx_root->dr_flags &= ~OCFS2_DX_FLAG_INLINE;
+ memset(&dx_root->dr_list, 0, osb->sb->s_blocksize -
+ offsetof(struct ocfs2_dx_root_block, dr_list));
+ dx_root->dr_list.l_count =
+ cpu_to_le16(ocfs2_extent_recs_per_dx_root(osb->sb));
+
+ /* This should never fail considering we start with an empty
+ * dx_root. */
+ ocfs2_init_dx_root_extent_tree(&et, INODE_CACHE(dir), dx_root_bh);
+ ret = ocfs2_insert_extent(handle, &et, 0, insert_blkno, 1, 0, NULL);
+ if (ret)
+ mlog_errno(ret);
+ did_quota = 0;
+
+ ocfs2_journal_dirty(handle, dx_root_bh);
+
+out_commit:
+ if (ret < 0 && did_quota)
+ vfs_dq_free_space_nodirty(dir,
+ ocfs2_clusters_to_bytes(dir->i_sb, 1));
+
+ ocfs2_commit_trans(osb, handle);
+
+out:
+ if (data_ac)
+ ocfs2_free_alloc_context(data_ac);
+
+ if (dx_leaves) {
+ for (i = 0; i < num_dx_leaves; i++)
+ brelse(dx_leaves[i]);
+ kfree(dx_leaves);
+ }
+ return ret;
+}
+
+static int ocfs2_inline_dx_has_space(struct buffer_head *dx_root_bh)
+{
+ struct ocfs2_dx_root_block *dx_root;
+ struct ocfs2_dx_entry_list *entry_list;
+
+ dx_root = (struct ocfs2_dx_root_block *) dx_root_bh->b_data;
+ entry_list = &dx_root->dr_entries;
+
+ if (le16_to_cpu(entry_list->de_num_used) >=
+ le16_to_cpu(entry_list->de_count))
+ return -ENOSPC;
+
+ return 0;
+}
+
+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, free_dx_root = 1;
+ 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;
+ struct ocfs2_dx_root_block *dx_root;
+
+ ret = ocfs2_read_dx_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;
+ if (le32_to_cpu(dx_root->dr_num_entries) == OCFS2_DX_ENTRIES_MAX) {
+ ret = -ENOSPC;
+ mlog_errno(ret);
+ goto out;
+ }
+
+ if (ocfs2_dx_root_inline(dx_root)) {
+ ret = ocfs2_inline_dx_has_space(dx_root_bh);
+
+ if (ret == 0)
+ goto search_el;
+
+ /*
+ * We ran out of room in the root block. Expand it to
+ * an extent, then allow ocfs2_find_dir_space_dx to do
+ * the rest.
+ */
+ ret = ocfs2_expand_inline_dx_root(dir, 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;
+ }
+
+search_el:
+ /*
+ * 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;
+ }
+
+ /* Do this up here - ocfs2_extend_dir might need the dx_root */
+ lookup->dl_dx_root_bh = dx_root_bh;
+ free_dx_root = 0;
+
+ if (ret == -ENOSPC) {
+ ret = ocfs2_extend_dir(osb, dir, di_bh, 1, lookup, &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.
+ */
+ lookup->dl_prev_leaf_bh = NULL;
+ lookup->dl_leaf_bh = leaf_bh;
+ }
+
+out:
+ if (free_dx_root)
+ brelse(dx_root_bh);
+ return ret;
+}
+
+/*
+ * 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.
+ */