From dcd0538ff4e854fa9d7f4630b359ca8fdb5cb5a8 Mon Sep 17 00:00:00 2001 From: Mark Fasheh Date: Tue, 16 Jan 2007 11:32:23 -0800 Subject: ocfs2: sparse b-tree support Introduce tree rotations into the b-tree code. This will allow ocfs2 to support sparse files. Much of the added code is designed to be generic (in the ocfs2 sense) so that it can later be re-used to implement large extended attributes. This patch only adds the rotation code and does minimal updates to callers of the extent api. Signed-off-by: Mark Fasheh --- fs/ocfs2/alloc.c | 2494 +++++++++++++++++++++++++++++++++++++++++++----------- 1 file changed, 1987 insertions(+), 507 deletions(-) (limited to 'fs/ocfs2/alloc.c') diff --git a/fs/ocfs2/alloc.c b/fs/ocfs2/alloc.c index f27e5378caf2..a96696867576 100644 --- a/fs/ocfs2/alloc.c +++ b/fs/ocfs2/alloc.c @@ -47,62 +47,230 @@ #include "buffer_head_io.h" -static int ocfs2_extent_contig(struct inode *inode, - struct ocfs2_extent_rec *ext, - u64 blkno); +static void ocfs2_free_truncate_context(struct ocfs2_truncate_context *tc); -static int ocfs2_create_new_meta_bhs(struct ocfs2_super *osb, - handle_t *handle, - struct inode *inode, - int wanted, - struct ocfs2_alloc_context *meta_ac, - struct buffer_head *bhs[]); +/* + * Structures which describe a path through a btree, and functions to + * manipulate them. + * + * The idea here is to be as generic as possible with the tree + * manipulation code. + */ +struct ocfs2_path_item { + struct buffer_head *bh; + struct ocfs2_extent_list *el; +}; -static int ocfs2_add_branch(struct ocfs2_super *osb, - handle_t *handle, - struct inode *inode, - struct buffer_head *fe_bh, - struct buffer_head *eb_bh, - struct buffer_head *last_eb_bh, - struct ocfs2_alloc_context *meta_ac); +#define OCFS2_MAX_PATH_DEPTH 5 -static int ocfs2_shift_tree_depth(struct ocfs2_super *osb, - handle_t *handle, - struct inode *inode, - struct buffer_head *fe_bh, - struct ocfs2_alloc_context *meta_ac, - struct buffer_head **ret_new_eb_bh); +struct ocfs2_path { + int p_tree_depth; + struct ocfs2_path_item p_node[OCFS2_MAX_PATH_DEPTH]; +}; -static int ocfs2_do_insert_extent(struct ocfs2_super *osb, - handle_t *handle, - struct inode *inode, - struct buffer_head *fe_bh, - u64 blkno, - u32 new_clusters); +#define path_root_bh(_path) ((_path)->p_node[0].bh) +#define path_root_el(_path) ((_path)->p_node[0].el) +#define path_leaf_bh(_path) ((_path)->p_node[(_path)->p_tree_depth].bh) +#define path_leaf_el(_path) ((_path)->p_node[(_path)->p_tree_depth].el) +#define path_num_items(_path) ((_path)->p_tree_depth + 1) -static int ocfs2_find_branch_target(struct ocfs2_super *osb, - struct inode *inode, - struct buffer_head *fe_bh, - struct buffer_head **target_bh); +/* + * Reset the actual path elements so that we can re-use the structure + * to build another path. Generally, this involves freeing the buffer + * heads. + */ +static void ocfs2_reinit_path(struct ocfs2_path *path, int keep_root) +{ + int i, start = 0, depth = 0; + struct ocfs2_path_item *node; -static int ocfs2_find_new_last_ext_blk(struct ocfs2_super *osb, - struct inode *inode, - struct ocfs2_dinode *fe, - unsigned int new_i_clusters, - struct buffer_head *old_last_eb, - struct buffer_head **new_last_eb); + if (keep_root) + start = 1; -static void ocfs2_free_truncate_context(struct ocfs2_truncate_context *tc); + for(i = start; i < path_num_items(path); i++) { + node = &path->p_node[i]; + + brelse(node->bh); + node->bh = NULL; + node->el = NULL; + } + + /* + * Tree depth may change during truncate, or insert. If we're + * keeping the root extent list, then make sure that our path + * structure reflects the proper depth. + */ + if (keep_root) + depth = le16_to_cpu(path_root_el(path)->l_tree_depth); + + path->p_tree_depth = depth; +} + +static void ocfs2_free_path(struct ocfs2_path *path) +{ + if (path) { + ocfs2_reinit_path(path, 0); + kfree(path); + } +} + +/* + * Make the *dest path the same as src and re-initialize src path to + * have a root only. + */ +static void ocfs2_mv_path(struct ocfs2_path *dest, struct ocfs2_path *src) +{ + int i; + + BUG_ON(path_root_bh(dest) != path_root_bh(src)); + + for(i = 1; i < OCFS2_MAX_PATH_DEPTH; i++) { + brelse(dest->p_node[i].bh); + + dest->p_node[i].bh = src->p_node[i].bh; + dest->p_node[i].el = src->p_node[i].el; + + src->p_node[i].bh = NULL; + src->p_node[i].el = NULL; + } +} + +/* + * Insert an extent block at given index. + * + * This will not take an additional reference on eb_bh. + */ +static inline void ocfs2_path_insert_eb(struct ocfs2_path *path, int index, + struct buffer_head *eb_bh) +{ + struct ocfs2_extent_block *eb = (struct ocfs2_extent_block *)eb_bh->b_data; + + /* + * Right now, no root bh is an extent block, so this helps + * catch code errors with dinode trees. The assertion can be + * safely removed if we ever need to insert extent block + * structures at the root. + */ + BUG_ON(index == 0); + + path->p_node[index].bh = eb_bh; + path->p_node[index].el = &eb->h_list; +} + +static struct ocfs2_path *ocfs2_new_path(struct buffer_head *root_bh, + struct ocfs2_extent_list *root_el) +{ + struct ocfs2_path *path; -static int ocfs2_extent_contig(struct inode *inode, - struct ocfs2_extent_rec *ext, - u64 blkno) + BUG_ON(le16_to_cpu(root_el->l_tree_depth) >= OCFS2_MAX_PATH_DEPTH); + + path = kzalloc(sizeof(*path), GFP_NOFS); + if (path) { + path->p_tree_depth = le16_to_cpu(root_el->l_tree_depth); + get_bh(root_bh); + path_root_bh(path) = root_bh; + path_root_el(path) = root_el; + } + + return path; +} + +/* + * Allocate and initialize a new path based on a disk inode tree. + */ +static struct ocfs2_path *ocfs2_new_inode_path(struct buffer_head *di_bh) +{ + struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data; + struct ocfs2_extent_list *el = &di->id2.i_list; + + return ocfs2_new_path(di_bh, el); +} + +/* + * Convenience function to journal all components in a path. + */ +static int ocfs2_journal_access_path(struct inode *inode, handle_t *handle, + struct ocfs2_path *path) +{ + int i, ret = 0; + + if (!path) + goto out; + + for(i = 0; i < path_num_items(path); i++) { + ret = ocfs2_journal_access(handle, inode, path->p_node[i].bh, + OCFS2_JOURNAL_ACCESS_WRITE); + if (ret < 0) { + mlog_errno(ret); + goto out; + } + } + +out: + return ret; +} + +enum ocfs2_contig_type { + CONTIG_NONE = 0, + CONTIG_LEFT, + CONTIG_RIGHT +}; + +static int ocfs2_block_extent_contig(struct super_block *sb, + struct ocfs2_extent_rec *ext, + u64 blkno) { return blkno == (le64_to_cpu(ext->e_blkno) + - ocfs2_clusters_to_blocks(inode->i_sb, + ocfs2_clusters_to_blocks(sb, le32_to_cpu(ext->e_clusters))); } +static int ocfs2_extents_adjacent(struct ocfs2_extent_rec *left, + struct ocfs2_extent_rec *right) +{ + return (le32_to_cpu(left->e_cpos) + le32_to_cpu(left->e_clusters) == + le32_to_cpu(right->e_cpos)); +} + +static enum ocfs2_contig_type + ocfs2_extent_contig(struct inode *inode, + struct ocfs2_extent_rec *ext, + struct ocfs2_extent_rec *insert_rec) +{ + u64 blkno = le64_to_cpu(insert_rec->e_blkno); + + if (ocfs2_extents_adjacent(ext, insert_rec) && + ocfs2_block_extent_contig(inode->i_sb, ext, blkno)) + return CONTIG_RIGHT; + + blkno = le64_to_cpu(ext->e_blkno); + if (ocfs2_extents_adjacent(insert_rec, ext) && + ocfs2_block_extent_contig(inode->i_sb, insert_rec, blkno)) + return CONTIG_LEFT; + + return CONTIG_NONE; +} + +/* + * NOTE: We can have pretty much any combination of contiguousness and + * appending. + * + * The usefulness of APPEND_TAIL is more in that it lets us know that + * we'll have to update the path to that leaf. + */ +enum ocfs2_append_type { + APPEND_NONE = 0, + APPEND_TAIL, +}; + +struct ocfs2_insert_type { + enum ocfs2_append_type ins_appending; + enum ocfs2_contig_type ins_contig; + int ins_contig_index; + int ins_free_records; + int ins_tree_depth; +}; + /* * How many free extents have we got before we need more meta data? */ @@ -241,6 +409,28 @@ bail: return status; } +/* + * Helper function for ocfs2_add_branch() and ocfs2_shift_tree_depth(). + * + * Returns the sum of the rightmost extent rec logical offset and + * cluster count. + * + * ocfs2_add_branch() uses this to determine what logical cluster + * value should be populated into the leftmost new branch records. + * + * ocfs2_shift_tree_depth() uses this to determine the # clusters + * value for the new topmost tree record. + */ +static inline u32 ocfs2_sum_rightmost_rec(struct ocfs2_extent_list *el) +{ + int i; + + i = le16_to_cpu(el->l_next_free_rec) - 1; + + return le32_to_cpu(el->l_recs[i].e_cpos) + + le32_to_cpu(el->l_recs[i].e_clusters); +} + /* * Add an entire tree branch to our inode. eb_bh is the extent block * to start at, if we don't want to start the branch at the dinode @@ -268,6 +458,7 @@ static int ocfs2_add_branch(struct ocfs2_super *osb, struct ocfs2_extent_block *eb; struct ocfs2_extent_list *eb_el; struct ocfs2_extent_list *el; + u32 new_cpos; mlog_entry_void(); @@ -302,6 +493,9 @@ static int ocfs2_add_branch(struct ocfs2_super *osb, goto bail; } + eb = (struct ocfs2_extent_block *)last_eb_bh->b_data; + new_cpos = ocfs2_sum_rightmost_rec(&eb->h_list); + /* Note: new_eb_bhs[new_blocks - 1] is the guy which will be * linked with the rest of the tree. * conversly, new_eb_bhs[0] is the new bottommost leaf. @@ -330,7 +524,11 @@ static int ocfs2_add_branch(struct ocfs2_super *osb, eb->h_next_leaf_blk = 0; eb_el->l_tree_depth = cpu_to_le16(i); eb_el->l_next_free_rec = cpu_to_le16(1); - eb_el->l_recs[0].e_cpos = fe->i_clusters; + /* + * This actually counts as an empty extent as + * c_clusters == 0 + */ + eb_el->l_recs[0].e_cpos = cpu_to_le32(new_cpos); eb_el->l_recs[0].e_blkno = cpu_to_le64(next_blkno); eb_el->l_recs[0].e_clusters = cpu_to_le32(0); if (!eb_el->l_tree_depth) @@ -376,7 +574,7 @@ static int ocfs2_add_branch(struct ocfs2_super *osb, * either be on the fe, or the extent block passed in. */ i = le16_to_cpu(el->l_next_free_rec); el->l_recs[i].e_blkno = cpu_to_le64(next_blkno); - el->l_recs[i].e_cpos = fe->i_clusters; + el->l_recs[i].e_cpos = cpu_to_le32(new_cpos); el->l_recs[i].e_clusters = 0; le16_add_cpu(&el->l_next_free_rec, 1); @@ -425,6 +623,7 @@ static int ocfs2_shift_tree_depth(struct ocfs2_super *osb, struct buffer_head **ret_new_eb_bh) { int status, i; + u32 new_clusters; struct buffer_head *new_eb_bh = NULL; struct ocfs2_dinode *fe; struct ocfs2_extent_block *eb; @@ -480,11 +679,13 @@ static int ocfs2_shift_tree_depth(struct ocfs2_super *osb, goto bail; } + new_clusters = ocfs2_sum_rightmost_rec(eb_el); + /* update fe now */ le16_add_cpu(&fe_el->l_tree_depth, 1); fe_el->l_recs[0].e_cpos = 0; fe_el->l_recs[0].e_blkno = eb->h_blkno; - fe_el->l_recs[0].e_clusters = fe->i_clusters; + fe_el->l_recs[0].e_clusters = cpu_to_le32(new_clusters); for(i = 1; i < le16_to_cpu(fe_el->l_next_free_rec); i++) { fe_el->l_recs[i].e_cpos = 0; fe_el->l_recs[i].e_clusters = 0; @@ -514,199 +715,6 @@ bail: return status; } -/* - * Expects the tree to already have room in the rightmost leaf for the - * extent. Updates all the extent blocks (and the dinode) on the way - * down. - */ -static int ocfs2_do_insert_extent(struct ocfs2_super *osb, - handle_t *handle, - struct inode *inode, - struct buffer_head *fe_bh, - u64 start_blk, - u32 new_clusters) -{ - int status, i, num_bhs = 0; - u64 next_blkno; - u16 next_free; - struct buffer_head **eb_bhs = NULL; - struct ocfs2_dinode *fe; - struct ocfs2_extent_block *eb; - struct ocfs2_extent_list *el; - - mlog_entry_void(); - - status = ocfs2_journal_access(handle, inode, fe_bh, - OCFS2_JOURNAL_ACCESS_WRITE); - if (status < 0) { - mlog_errno(status); - goto bail; - } - - fe = (struct ocfs2_dinode *) fe_bh->b_data; - el = &fe->id2.i_list; - if (el->l_tree_depth) { - /* This is another operation where we want to be - * careful about our tree updates. An error here means - * none of the previous changes we made should roll - * forward. As a result, we have to record the buffers - * for this part of the tree in an array and reserve a - * journal write to them before making any changes. */ - num_bhs = le16_to_cpu(fe->id2.i_list.l_tree_depth); - eb_bhs = kcalloc(num_bhs, sizeof(struct buffer_head *), - GFP_KERNEL); - if (!eb_bhs) { - status = -ENOMEM; - mlog_errno(status); - goto bail; - } - - i = 0; - while(el->l_tree_depth) { - next_free = le16_to_cpu(el->l_next_free_rec); - if (next_free == 0) { - ocfs2_error(inode->i_sb, - "Dinode %llu has a bad extent list", - (unsigned long long)OCFS2_I(inode)->ip_blkno); - status = -EIO; - goto bail; - } - next_blkno = le64_to_cpu(el->l_recs[next_free - 1].e_blkno); - - BUG_ON(i >= num_bhs); - status = ocfs2_read_block(osb, next_blkno, &eb_bhs[i], - OCFS2_BH_CACHED, inode); - if (status < 0) { - mlog_errno(status); - goto bail; - } - eb = (struct ocfs2_extent_block *) eb_bhs[i]->b_data; - if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb)) { - OCFS2_RO_ON_INVALID_EXTENT_BLOCK(inode->i_sb, - eb); - status = -EIO; - goto bail; - } - - status = ocfs2_journal_access(handle, inode, eb_bhs[i], - OCFS2_JOURNAL_ACCESS_WRITE); - if (status < 0) { - mlog_errno(status); - goto bail; - } - - el = &eb->h_list; - i++; - /* When we leave this loop, eb_bhs[num_bhs - 1] will - * hold the bottom-most leaf extent block. */ - } - BUG_ON(el->l_tree_depth); - - el = &fe->id2.i_list; - /* If we have tree depth, then the fe update is - * trivial, and we want to switch el out for the - * bottom-most leaf in order to update it with the - * actual extent data below. */ - next_free = le16_to_cpu(el->l_next_free_rec); - if (next_free == 0) { - ocfs2_error(inode->i_sb, - "Dinode %llu has a bad extent list", - (unsigned long long)OCFS2_I(inode)->ip_blkno); - status = -EIO; - goto bail; - } - le32_add_cpu(&el->l_recs[next_free - 1].e_clusters, - new_clusters); - /* (num_bhs - 1) to avoid the leaf */ - for(i = 0; i < (num_bhs - 1); i++) { - eb = (struct ocfs2_extent_block *) eb_bhs[i]->b_data; - el = &eb->h_list; - - /* finally, make our actual change to the - * intermediate extent blocks. */ - next_free = le16_to_cpu(el->l_next_free_rec); - le32_add_cpu(&el->l_recs[next_free - 1].e_clusters, - new_clusters); - - status = ocfs2_journal_dirty(handle, eb_bhs[i]); - if (status < 0) - mlog_errno(status); - } - BUG_ON(i != (num_bhs - 1)); - /* note that the leaf block wasn't touched in - * the loop above */ - eb = (struct ocfs2_extent_block *) eb_bhs[num_bhs - 1]->b_data; - el = &eb->h_list; - BUG_ON(el->l_tree_depth); - } - - /* yay, we can finally add the actual extent now! */ - i = le16_to_cpu(el->l_next_free_rec) - 1; - if (le16_to_cpu(el->l_next_free_rec) && - ocfs2_extent_contig(inode, &el->l_recs[i], start_blk)) { - le32_add_cpu(&el->l_recs[i].e_clusters, new_clusters); - } else if (le16_to_cpu(el->l_next_free_rec) && - (le32_to_cpu(el->l_recs[i].e_clusters) == 0)) { - /* having an empty extent at eof is legal. */ - if (el->l_recs[i].e_cpos != fe->i_clusters) { - ocfs2_error(inode->i_sb, - "Dinode %llu trailing extent is bad: " - "cpos (%u) != number of clusters (%u)", - (unsigned long long)OCFS2_I(inode)->ip_blkno, - le32_to_cpu(el->l_recs[i].e_cpos), - le32_to_cpu(fe->i_clusters)); - status = -EIO; - goto bail; - } - el->l_recs[i].e_blkno = cpu_to_le64(start_blk); - el->l_recs[i].e_clusters = cpu_to_le32(new_clusters); - } else { - /* No contiguous record, or no empty record at eof, so - * we add a new one. */ - - BUG_ON(le16_to_cpu(el->l_next_free_rec) >= - le16_to_cpu(el->l_count)); - i = le16_to_cpu(el->l_next_free_rec); - - el->l_recs[i].e_blkno = cpu_to_le64(start_blk); - el->l_recs[i].e_clusters = cpu_to_le32(new_clusters); - el->l_recs[i].e_cpos = fe->i_clusters; - le16_add_cpu(&el->l_next_free_rec, 1); - } - - /* - * extent_map errors are not fatal, so they are ignored outside - * of flushing the thing. - */ - status = ocfs2_extent_map_append(inode, &el->l_recs[i], - new_clusters); - if (status) { - mlog_errno(status); - ocfs2_extent_map_drop(inode, le32_to_cpu(fe->i_clusters)); - } - - status = ocfs2_journal_dirty(handle, fe_bh); - if (status < 0) - mlog_errno(status); - if (fe->id2.i_list.l_tree_depth) { - status = ocfs2_journal_dirty(handle, eb_bhs[num_bhs - 1]); - if (status < 0) - mlog_errno(status); - } - - status = 0; -bail: - if (eb_bhs) { - for (i = 0; i < num_bhs; i++) - if (eb_bhs[i]) - brelse(eb_bhs[i]); - kfree(eb_bhs); - } - - mlog_exit(status); - return status; -} - /* * Should only be called when there is no space left in any of the * leaf nodes. What we want to do is find the lowest tree depth @@ -774,86 +782,1556 @@ static int ocfs2_find_branch_target(struct ocfs2_super *osb, mlog_errno(status); goto bail; } - + + eb = (struct ocfs2_extent_block *) bh->b_data; + if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb)) { + OCFS2_RO_ON_INVALID_EXTENT_BLOCK(inode->i_sb, eb); + status = -EIO; + goto bail; + } + el = &eb->h_list; + + if (le16_to_cpu(el->l_next_free_rec) < + le16_to_cpu(el->l_count)) { + if (lowest_bh) + brelse(lowest_bh); + lowest_bh = bh; + get_bh(lowest_bh); + } + } + + /* If we didn't find one and the fe doesn't have any room, + * then return '1' */ + if (!lowest_bh + && (fe->id2.i_list.l_next_free_rec == fe->id2.i_list.l_count)) + status = 1; + + *target_bh = lowest_bh; +bail: + if (bh) + brelse(bh); + + mlog_exit(status); + return status; +} + +static inline int ocfs2_is_empty_extent(struct ocfs2_extent_rec *rec) +{ + return !rec->e_clusters; +} + +/* + * This function will discard the rightmost extent record. + */ +static void ocfs2_shift_records_right(struct ocfs2_extent_list *el) +{ + int next_free = le16_to_cpu(el->l_next_free_rec); + int count = le16_to_cpu(el->l_count); + unsigned int num_bytes; + + BUG_ON(!next_free); + /* This will cause us to go off the end of our extent list. */ + BUG_ON(next_free >= count); + + num_bytes = sizeof(struct ocfs2_extent_rec) * next_free; + + memmove(&el->l_recs[1], &el->l_recs[0], num_bytes); +} + +static void ocfs2_rotate_leaf(struct ocfs2_extent_list *el, + struct ocfs2_extent_rec *insert_rec) +{ + int i, insert_index, next_free, has_empty, num_bytes; + u32 insert_cpos = le32_to_cpu(insert_rec->e_cpos); + struct ocfs2_extent_rec *rec; + + next_free = le16_to_cpu(el->l_next_free_rec); + has_empty = ocfs2_is_empty_extent(&el->l_recs[0]); + + BUG_ON(!next_free); + + /* The tree code before us didn't allow enough room in the leaf. */ + if (el->l_next_free_rec == el->l_count && !has_empty) + BUG(); + + /* + * The easiest way to approach this is to just remove the + * empty extent and temporarily decrement next_free. + */ + if (has_empty) { + /* + * If next_free was 1 (only an empty extent), this + * loop won't execute, which is fine. We still want + * the decrement above to happen. + */ + for(i = 0; i < (next_free - 1); i++) + el->l_recs[i] = el->l_recs[i+1]; + + next_free--; + } + + /* + * Figure out what the new record index should be. + */ + for(i = 0; i < next_free; i++) { + rec = &el->l_recs[i]; + + if (insert_cpos < le32_to_cpu(rec->e_cpos)) + break; + } + insert_index = i; + + mlog(0, "ins %u: index %d, has_empty %d, next_free %d, count %d\n", + insert_cpos, insert_index, has_empty, next_free, le16_to_cpu(el->l_count)); + + BUG_ON(insert_index < 0); + BUG_ON(insert_index >= le16_to_cpu(el->l_count)); + BUG_ON(insert_index > next_free); + + /* + * No need to memmove if we're just adding to the tail. + */ + if (insert_index != next_free) { + BUG_ON(next_free >= le16_to_cpu(el->l_count)); + + num_bytes = next_free - insert_index; + num_bytes *= sizeof(struct ocfs2_extent_rec); + memmove(&el->l_recs[insert_index + 1], + &el->l_recs[insert_index], + num_bytes); + } + + /* + * Either we had an empty extent, and need to re-increment or + * there was no empty extent on a non full rightmost leaf node, + * in which case we still need to increment. + */ + next_free++; + el->l_next_free_rec = cpu_to_le16(next_free); + /* + * Make sure none of the math above just messed up our tree. + */ + BUG_ON(le16_to_cpu(el->l_next_free_rec) > le16_to_cpu(el->l_count)); + + el->l_recs[insert_index] = *insert_rec; + +} + +/* + * Create an empty extent record . + * + * l_next_free_rec may be updated. + * + * If an empty extent already exists do nothing. + */ +static void ocfs2_create_empty_extent(struct ocfs2_extent_list *el) +{ + int next_free = le16_to_cpu(el->l_next_free_rec); + + if (next_free == 0) + goto set_and_inc; + + if (ocfs2_is_empty_extent(&el->l_recs[0])) + return; + + mlog_bug_on_msg(el->l_count == el->l_next_free_rec, + "Asked to create an empty extent in a full list:\n" + "count = %u, tree depth = %u", + le16_to_cpu(el->l_count), + le16_to_cpu(el->l_tree_depth)); + + ocfs2_shift_records_right(el); + +set_and_inc: + le16_add_cpu(&el->l_next_free_rec, 1); + memset(&el->l_recs[0], 0, sizeof(struct ocfs2_extent_rec)); +} + +/* + * For a rotation which involves two leaf nodes, the "root node" is + * the lowest level tree node which contains a path to both leafs. This + * resulting set of information can be used to form a complete "subtree" + * + * This function is passed two full paths from the dinode down to a + * pair of adjacent leaves. It's task is to figure out which path + * index contains the subtree root - this can be the root index itself + * in a worst-case rotation. + * + * The array index of the subtree root is passed back. + */ +static int ocfs2_find_subtree_root(struct inode *inode, + struct ocfs2_path *left, + struct ocfs2_path *right) +{ + int i = 0; + + /* + * Check that the caller passed in two paths from the same tree. + */ + BUG_ON(path_root_bh(left) != path_root_bh(right)); + + do { + i++; + + /* + * The caller didn't pass two adjacent paths. + */ + mlog_bug_on_msg(i > left->p_tree_depth, + "Inode %lu, left depth %u, right depth %u\n" + "left leaf blk %llu, right leaf blk %llu\n", + inode->i_ino, left->p_tree_depth, + right->p_tree_depth, + (unsigned long long)path_leaf_bh(left)->b_blocknr, + (unsigned long long)path_leaf_bh(right)->b_blocknr); + } while (left->p_node[i].bh->b_blocknr == + right->p_node[i].bh->b_blocknr); + + return i - 1; +} + +typedef void (path_insert_t)(void *, struct buffer_head *); + +/* + * Traverse a btree path in search of cpos, starting at root_el. + * + * This code can be called with a cpos larger than the tree, in which + * case it will return the rightmost path. + */ +static int __ocfs2_find_path(struct inode *inode, + struct ocfs2_extent_list *root_el, u32 cpos, + path_insert_t *func, void *data) +{ + int i, ret = 0; + u32 range; + u64 blkno; + struct buffer_head *bh = NULL; + struct ocfs2_extent_block *eb; + struct ocfs2_extent_list *el; + struct ocfs2_extent_rec *rec; + struct ocfs2_inode_info *oi = OCFS2_I(inode); + + el = root_el; + while (el->l_tree_depth) { + if (le16_to_cpu(el->l_next_free_rec) == 0) { + ocfs2_error(inode->i_sb, + "Inode %llu has empty extent list at " + "depth %u\n", + (unsigned long long)oi->ip_blkno, + le16_to_cpu(el->l_tree_depth)); + ret = -EROFS; + goto out; + + } + + for(i = 0; i < le16_to_cpu(el->l_next_free_rec) - 1; i++) { + rec = &el->l_recs[i]; + + /* + * In the case that cpos is off the allocation + * tree, this should just wind up returning the + * rightmost record. + */ + range = le32_to_cpu(rec->e_cpos) + + le32_to_cpu(rec->e_clusters); + if (cpos >= le32_to_cpu(rec->e_cpos) && cpos < range) + break; + } + + blkno = le64_to_cpu(el->l_recs[i].e_blkno); + if (blkno == 0) { + ocfs2_error(inode->i_sb, + "Inode %llu has bad blkno in extent list " + "at depth %u (index %d)\n", + (unsigned long long)oi->ip_blkno, + le16_to_cpu(el->l_tree_depth), i); + ret = -EROFS; + goto out; + } + + brelse(bh); + bh = NULL; + ret = ocfs2_read_block(OCFS2_SB(inode->i_sb), blkno, + &bh, OCFS2_BH_CACHED, inode); + if (ret) { + mlog_errno(ret); + goto out; + } + + eb = (struct ocfs2_extent_block *) bh->b_data; + el = &eb->h_list; + if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb)) { + OCFS2_RO_ON_INVALID_EXTENT_BLOCK(inode->i_sb, eb); + ret = -EIO; + goto out; + } + + if (le16_to_cpu(el->l_next_free_rec) > + le16_to_cpu(el->l_count)) { + ocfs2_error(inode->i_sb, + "Inode %llu has bad count in extent list " + "at block %llu (next free=%u, count=%u)\n", + (unsigned long long)oi->ip_blkno, + (unsigned long long)bh->b_blocknr, + le16_to_cpu(el->l_next_free_rec), + le16_to_cpu(el->l_count)); + ret = -EROFS; + goto out; + } + + if (func) + func(data, bh); + } + +out: + /* + * Catch any trailing bh that the loop didn't handle. + */ + brelse(bh); + + return ret; +} + +/* + * Given an initialized path (that is, it has a valid root extent + * list), this function will traverse the btree in search of the path + * which would contain cpos. + * + * The path traveled is recorded in the path structure. + * + * Note that this will not do any comparisons on leaf node extent + * records, so it will work fine in the case that we just added a tree + * branch. + */ +struct find_path_data { + int index; + struct ocfs2_path *path; +}; +static void find_path_ins(void *data, struct buffer_head *bh) +{ + struct find_path_data *fp = data; + + get_bh(bh); + ocfs2_path_insert_eb(fp->path, fp->index, bh); + fp->index++; +} +static int ocfs2_find_path(struct inode *inode, struct ocfs2_path *path, + u32 cpos) +{ + struct find_path_data data; + + data.index = 1; + data.path = path; + return __ocfs2_find_path(inode, path_root_el(path), cpos, + find_path_ins, &data); +} + +static void find_leaf_ins(void *data, struct buffer_head *bh) +{ + struct ocfs2_extent_block *eb =(struct ocfs2_extent_block *)bh->b_data; + struct ocfs2_extent_list *el = &eb->h_list; + struct buffer_head **ret = data; + + /* We want to retain only the leaf block. */ + if (le16_to_cpu(el->l_tree_depth) == 0) { + get_bh(bh); + *ret = bh; + } +} +/* + * Find the leaf block in the tree which would contain cpos. No + * checking of the actual leaf is done. + * + * Some paths want to call this instead of allocating a path structure + * and calling ocfs2_find_path(). + * + * This function doesn't handle non btree extent lists. + */ +static int ocfs2_find_leaf(struct inode *inode, + struct ocfs2_extent_list *root_el, u32 cpos, + struct buffer_head **leaf_bh) +{ + int ret; + struct buffer_head *bh = NULL; + + ret = __ocfs2_find_path(inode, root_el, cpos, find_leaf_ins, &bh); + if (ret) { + mlog_errno(ret); + goto out; + } + + *leaf_bh = bh; +out: + return ret; +} + +/* + * Adjust the adjacent records (left_rec, right_rec) involved in a rotation. + * + * Basically, we've moved stuff around at the bottom of the tree and + * we need to fix up the extent records above the changes to reflect + * the new changes. + * + * left_rec: the record on the left. + * left_child_el: is the child list pointed to by left_rec + * right_rec: the record to the right of left_rec + * right_child_el: is the child list pointed to by right_rec + * + * By definition, this only works on interior nodes. + */ +static void ocfs2_adjust_adjacent_records(struct ocfs2_extent_rec *left_rec, + struct ocfs2_extent_list *left_child_el, + struct ocfs2_extent_rec *right_rec, + struct ocfs2_extent_list *right_child_el) +{ + u32 left_clusters, right_end; + + /* + * Interior nodes never have holes. Their cpos is the cpos of + * the leftmost record in their child list. Their cluster + * count covers the full theoretical range of their child list + * - the range between their cpos and the cpos of the record + * immediately to their right. + */ + left_clusters = le32_to_cpu(right_child_el->l_recs[0].e_cpos); + left_clusters -= le32_to_cpu(left_rec->e_cpos); + left_rec->e_clusters = cpu_to_le32(left_clusters); + + /* + * Calculate the rightmost cluster count boundary before + * moving cpos - we will need to adjust e_clusters after + * updating e_cpos to keep the same highest cluster count. + */ + right_end = le32_to_cpu(right_rec->e_cpos); + right_end += le32_to_cpu(right_rec->e_clusters); + + right_rec->e_cpos = left_rec->e_cpos; + le32_add_cpu(&right_rec->e_cpos, left_clusters); + + right_end -= le32_to_cpu(right_rec->e_cpos); + right_rec->e_clusters = cpu_to_le32(right_end); +} + +/* + * Adjust the adjacent root node records involved in a + * rotation. left_el_blkno is passed in as a key so that we can easily + * find it's index in the root list. + */ +static void ocfs2_adjust_root_records(struct ocfs2_extent_list *root_el, + struct ocfs2_extent_list *left_el, + struct ocfs2_extent_list *right_el, + u64 left_el_blkno) +{ + int i; + + BUG_ON(le16_to_cpu(root_el->l_tree_depth) <= + le16_to_cpu(left_el->l_tree_depth)); + + for(i = 0; i < le16_to_cpu(root_el->l_next_free_rec) - 1; i++) { + if (le64_to_cpu(root_el->l_recs[i].e_blkno) == left_el_blkno) + break; + } + + /* + * The path walking code should have never returned a root and + * two paths which are not adjacent. + */ + BUG_ON(i >= (le16_to_cpu(root_el->l_next_free_rec) - 1)); + + ocfs2_adjust_adjacent_records(&root_el->l_recs[i], left_el, + &root_el->l_recs[i + 1], right_el); +} + +/* + * We've changed a leaf block (in right_path) and need to reflect that + * change back up the subtree. + * + * This happens in multiple places: + * - When we've moved an extent record from the left path leaf to the right + * path leaf to make room for an empty extent in the left path leaf. + * - When our insert into the right path leaf is at the leftmost edge + * and requires an update of the path immediately to it's left. This + * can occur at the end of some types of rotation and appending inserts. + */ +static void ocfs2_complete_edge_insert(struct inode *inode, handle_t *handle, + struct ocfs2_path *left_path, + struct ocfs2_path *right_path, + int subtree_index) +{ + int ret, i, idx; + struct ocfs2_extent_list *el, *left_el, *right_el; + struct ocfs2_extent_rec *left_rec, *right_rec; + struct buffer_head *root_bh = left_path->p_node[subtree_index].bh; + + /* + * Update the counts and position values within all the + * interior nodes to reflect the leaf rotation we just did. + * + * The root node is handled below the loop. + * + * We begin the loop with right_el and left_el pointing to the + * leaf lists and work our way up. + * + * NOTE: within this loop, left_el and right_el always refer + * to the *child* lists. + */ + left_el = path_leaf_el(left_path); + right_el = path_leaf_el(right_path); + for(i = left_path->p_tree_depth - 1; i > subtree_index; i--) { + mlog(0, "Adjust records at index %u\n", i); + + /* + * One nice property of knowing that all of these + * nodes are below the root is that we only deal with + * the leftmost right node record and the rightmost + * left node record. + */ + el = left_path->p_node[i].el; + idx = le16_to_cpu(left_el->l_next_free_rec) - 1; + left_rec = &el->l_recs[idx]; + + el = right_path->p_node[i].el; + right_rec = &el->l_recs[0]; + + ocfs2_adjust_adjacent_records(left_rec, left_el, right_rec, + right_el); + + ret = ocfs2_journal_dirty(handle, left_path->p_node[i].bh); + if (ret) + mlog_errno(ret); + + ret = ocfs2_journal_dirty(handle, right_path->p_node[i].bh); + if (ret) + mlog_errno(ret); + + /* + * Setup our list pointers now so that the current + * parents become children in the next iteration. + */ + left_el = left_path->p_node[i].el; + right_el = right_path->p_node[i].el; + } + + /* + * At the root node, adjust the two adjacent records which + * begin our path to the leaves. + */ + + el = left_path->p_node[subtree_index].el; + left_el = left_path->p_node[subtree_index + 1].el; + right_el = right_path->p_node[subtree_index + 1].el; + + ocfs2_adjust_root_records(el, left_el, right_el, + left_path->p_node[subtree_index + 1].bh->b_blocknr); + + root_bh = left_path->p_node[subtree_index].bh; + + ret = ocfs2_journal_dirty(handle, root_bh); + if (ret) + mlog_errno(ret); +} + +static int ocfs2_rotate_subtree_right(struct inode *inode, + handle_t *handle, + struct ocfs2_path *left_path, + struct ocfs2_path *right_path, + int subtree_index) +{ + int ret, i; + struct buffer_head *right_leaf_bh; + struct buffer_head *left_leaf_bh = NULL; + struct buffer_head *root_bh; + struct ocfs2_extent_list *right_el, *left_el; + struct ocfs2_extent_rec move_rec; + + left_leaf_bh = path_leaf_bh(left_path); + left_el = path_leaf_el(left_path); + + if (left_el->l_next_free_rec != left_el->l_count) { + ocfs2_error(inode->i_sb, + "Inode %llu has non-full interior leaf node %llu" + "(next free = %u)", + (unsigned long long)OCFS2_I(inode)->ip_blkno, + (unsigned long long)left_leaf_bh->b_blocknr, + le16_to_cpu(left_el->l_next_free_rec)); + return -EROFS; + } + + /* + * This extent block may already have an empty record, so we + * return early if so. + */ + if (ocfs2_is_empty_extent(&left_el->l_recs[0])) + return 0; + + root_bh = left_path->p_node[subtree_index].bh; + BUG_ON(root_bh != right_path->p_node[subtree_index].bh); + + ret = ocfs2_journal_access(handle, inode, root_bh, + OCFS2_JOURNAL_ACCESS_WRITE); + if (ret) { + mlog_errno(ret); + goto out; + } + + for(i = subtree_index + 1; i < path_num_items(right_path); i++) { + ret = ocfs2_journal_access(handle, inode, + right_path->p_node[i].bh, + OCFS2_JOURNAL_ACCESS_WRITE); + if (ret) { + mlog_errno(ret); + goto out; + } + + ret = ocfs2_journal_access(handle, inode, + left_path->p_node[i].bh, + OCFS2_JOURNAL_ACCESS_WRITE); + if (ret) { + mlog_errno(ret); + goto out; + } + } + + right_leaf_bh = path_leaf_bh(right_path); + right_el = path_leaf_el(right_path); + + /* This is a code error, not a disk corruption. */ + mlog_bug_on_msg(!right_el->l_next_free_rec, "Inode %llu: Rotate fails " + "because rightmost leaf block %llu is empty\n", + (unsigned long long)OCFS2_I(inode)->ip_blkno, + (unsigned long long)right_leaf_bh->b_blocknr); + + ocfs2_create_empty_extent(right_el); + + ret = ocfs2_journal_dirty(handle, right_leaf_bh); + if (ret) { + mlog_errno(ret); + goto out; + } + + /* Do the copy now. */ + i = le16_to_cpu(left_el->l_next_free_rec) - 1; + move_rec = left_el->l_recs[i]; + right_el->l_recs[0] = move_rec; + + /* + * Clear out the record we just copied and shift everything + * over, leaving an empty extent in the left leaf. + * + * We temporarily subtract from next_free_rec so that the + * shift will lose the tail record (which is now defunct). + */ + le16_add_cpu(&left_el->l_next_free_rec, -1); + ocfs2_shift_records_right(left_el); + memset(&left_el->l_recs[0], 0, sizeof(struct ocfs2_extent_rec)); + le16_add_cpu(&left_el->l_next_free_rec, 1); + + ret = ocfs2_journal_dirty(handle, left_leaf_bh); + if (ret) { + mlog_errno(ret); + goto out; + } + + ocfs2_complete_edge_insert(inode, handle, left_path, right_path, + subtree_index); + +out: + return ret; +} + +/* + * Given a full path, determine what cpos value would return us a path + * containing the leaf immediately to the left of the current one. + * + * Will return zero if the path passed in is already the leftmost path. + */ +static int ocfs2_find_cpos_for_left_leaf(struct super_block *sb, + struct ocfs2_path *path, u32 *cpos) +{ + int i, j, ret = 0; + u64 blkno; + struct ocfs2_extent_list *el; + + *cpos = 0; + + blkno = path_leaf_bh(path)->b_blocknr; + + /* Start at the tree node just above the leaf and work our way up. */ + i = path->p_tree_depth - 1; + while (i >= 0) { + el = path->p_node[i].el; + + /* + * Find the extent record just before the one in our + * path. + */ + for(j = 0; j < le16_to_cpu(el->l_next_free_rec); j++) { + if (le64_to_cpu(el->l_recs[j].e_blkno) == blkno) { + if (j == 0) { + if (i == 0) { + /* + * We've determined that the + * path specified is already + * the leftmost one - return a + * cpos of zero. + */ + goto out; + } + /* + * The leftmost record points to our + * leaf - we need to travel up the + * tree one level. + */ + goto next_node; + } + + *cpos = le32_to_cpu(el->l_recs[j - 1].e_cpos); + *cpos = *cpos + le32_to_cpu(el->l_recs[j - 1].e_clusters) - 1; + goto out; + } + } + + /* + * If we got here, we never found a valid node where + * the tree indicated one should be. + */ + ocfs2_error(sb, + "Invalid extent tree at extent block %llu\n", + (unsigned long long)blkno); + ret = -EROFS; + goto out; + +next_node: + blkno = path->p_node[i].bh->b_blocknr; + i--; + } + +out: + return ret; +} + +static int ocfs2_extend_rotate_transaction(handle_t *handle, int subtree_depth, + struct ocfs2_path *path) +{ + int credits = (path->p_tree_depth - subtree_depth) * 2 + 1; + + if (handle->h_buffer_credits < credits) + return ocfs2_extend_trans(handle, credits); + + return 0; +} + +/* + * Trap the case where we're inserting into the theoretical range past + * the _actual_ left leaf range. Otherwise, we'll rotate a record + * whose cpos is less than ours into the right leaf. + * + * It's only necessary to look at the rightmost record of the left + * leaf because the logic that calls us should ensure that the + * theoretical ranges in the path components above the leaves are + * correct. + */ +static int ocfs2_rotate_requires_path_adjustment(struct ocfs2_path *left_path, + u32 insert_cpos) +{ + struct ocfs2_extent_list *left_el; + struct ocfs2_extent_rec *rec; + int next_free; + + left_el = path_leaf_el(left_path); + next_free = le16_to_cpu(left_el->l_next_free_rec); + rec = &left_el->l_recs[next_free - 1]; + + if (insert_cpos > le32_to_cpu(rec->e_cpos)) + return 1; + return 0; +} + +/* + * Rotate all the records in a btree right one record, starting at insert_cpos. + * + * The path to the rightmost leaf should be passed in. + * + * The array is assumed to be large enough to hold an entire path (tree depth). + * + * Upon succesful return from this function: + * + * - The 'right_path' array will contain a path to the leaf block + * whose range contains e_cpos. + * - That leaf block will have a single empty extent in list index 0. + * - In the case that the rotation requires a post-insert update, + * *ret_left_path will contain a valid path which can be passed to + * ocfs2_insert_path(). + */ +static int ocfs2_rotate_tree_right(struct inode *inode, + handle_t *handle, + u32 insert_cpos, + struct ocfs2_path *right_path, + struct ocfs2_path **ret_left_path) +{ + int ret, start; + u32 cpos; + struct ocfs2_path *left_path = NULL; + + *ret_left_path = NULL; + + left_path = ocfs2_new_path(path_root_bh(right_path), + path_root_el(right_path)); + if (!left_path) { + ret = -ENOMEM; + mlog_errno(ret); + goto out; + } + + ret = ocfs2_find_cpos_for_left_leaf(inode->i_sb, right_path, &cpos); + if (ret) { + mlog_errno(ret); + goto out; + } + + mlog(0, "Insert: %u, first left path cpos: %u\n", insert_cpos, cpos); + + /* + * What we want to do here is: + * + * 1) Start with the rightmost path. + * + * 2) Determine a path to the leaf block directly to the left + * of that leaf. + * + * 3) Determine the 'subtree root' - the lowest level tree node + * which contains a path to both leaves. + * + * 4) Rotate the subtree. + * + * 5) Find the next subtree by considering the left path to be + * the new right path. + * + * The check at the top of this while loop also accepts + * insert_cpos == cpos because cpos is only a _theoretical_ + * value to get us the left path - insert_cpos might very well + * be filling that hole. + * + * Stop at a cpos of '0' because we either started at the + * leftmost branch (i.e., a tree with one branch and a + * rotation inside of it), or we've gone as far as we can in + * rotating subtrees. + */ + while (cpos && insert_cpos <= cpos) { + mlog(0, "Rotating a tree: ins. cpos: %u, left path cpos: %u\n", + insert_cpos, cpos); + + ret = ocfs2_find_path(inode, left_path, cpos); + if (ret) { + mlog_errno(ret); + goto out; + } + + mlog_bug_on_msg(path_leaf_bh(left_path) == + path_leaf_bh(right_path), + "Inode %lu: error during insert of %u " + "(left path cpos %u) results in two identical " + "paths ending at %llu\n", + inode->i_ino, insert_cpos, cpos, + (unsigned long long) + path_leaf_bh(left_path)->b_blocknr); + + if (ocfs2_rotate_requires_path_adjustment(left_path, + insert_cpos)) { + mlog(0, "Path adjustment required\n"); + + /* + * We've rotated the tree as much as we + * should. The rest is up to + * ocfs2_insert_path() to complete, after the + * record insertion. We indicate this + * situation by returning the left path. + * + * The reason we don't adjust the records here + * before the record insert is that an error + * later might break the rule where a parent + * record e_cpos will reflect the actual + * e_cpos of the 1st nonempty record of the + * child list. + */ + *ret_left_path = left_path; + goto out_ret_path; + } + + start = ocfs2_find_subtree_root(inode, left_path, right_path); + + mlog(0, "Subtree root at index %d (blk %llu, depth %d)\n", + start, + (unsigned long long) right_path->p_node[start].bh->b_blocknr, + right_path->p_tree_depth); + + ret = ocfs2_extend_rotate_transaction(handle, start, + right_path); + if (ret) { + mlog_errno(ret); + goto out; + } + + ret = ocfs2_rotate_subtree_right(inode, handle, left_path, + right_path, start); + if (ret) { + mlog_errno(ret); + goto out; + } + + /* + * There is no need to re-read the next right path + * as we know that it'll be our current left + * path. Optimize by copying values instead. + */ + ocfs2_mv_path(right_path, left_path); + + ret = ocfs2_find_cpos_for_left_leaf(inode->i_sb, right_path, + &cpos); + if (ret) { + mlog_errno(ret); + goto out; + } + } + +out: + ocfs2_free_path(left_path); + +out_ret_path: + return ret; +} + +/* + * Do the final bits of extent record insertion at the target leaf + * list. If this leaf is part of an allocation tree, it is assumed + * that the tree above has been prepared. + */ +static void ocfs2_insert_at_leaf(struct ocfs2_extent_rec *insert_rec, + struct ocfs2_extent_list *el, + struct ocfs2_insert_type *insert, + struct inode *inode) +{ + int i = insert->ins_contig_index; + unsigned int range; + struct ocfs2_extent_rec *rec; + + BUG_ON(el->l_tree_depth); + + /* + * Contiguous insert - either left or right. + */ + if (insert->ins_contig != CONTIG_NONE) { + rec = &el->l_recs[i]; + if (insert->ins_contig == CONTIG_LEFT) { + rec->e_blkno = insert_rec->e_blkno; + rec->e_cpos = insert_rec->e_cpos; + } + le32_add_cpu(&rec->e_clusters, + le32_to_cpu(insert_rec->e_clusters)); + return; + } + + /* + * Handle insert into an empty leaf. + */ + if (le16_to_cpu(el->l_next_free_rec) == 0 || + ((le16_to_cpu(el->l_next_free_rec) == 1) && + ocfs2_is_empty_extent(&el->l_recs[0]))) { + el->l_recs[0] = *insert_rec; + el->l_next_free_rec = cpu_to_le16(1); + return; + } + + /* + * Appending insert. + */ + if (insert->ins_appending == APPEND_TAIL) { + i = le16_to_cpu(el->l_next_free_rec) - 1; + rec = &el->l_recs[i]; + range = le32_to_cpu(rec->e_cpos) + le32_to_cpu(rec->e_clusters); + BUG_ON(le32_to_cpu(insert_rec->e_cpos) < range); + + mlog_bug_on_msg(le16_to_cpu(el->l_next_free_rec) >= + le16_to_cpu(el->l_count), + "inode %lu, depth %u, count %u, next free %u, " + "rec.cpos %u, rec.clusters %u, " + "insert.cpos %u, insert.clusters %u\n", + inode->i_ino, + le16_to_cpu(el->l_tree_depth), + le16_to_cpu(el->l_count), + le16_to_cpu(el->l_next_free_rec), + le32_to_cpu(el->l_recs[i].e_cpos), + le32_to_cpu(el->l_recs[i].e_clusters), + le32_to_cpu(insert_rec->e_cpos), + le32_to_cpu(insert_rec->e_clusters)); + i++; + el->l_recs[i] = *insert_rec; + le16_add_cpu(&el->l_next_free_rec, 1); + return; + } + + /* + * Ok, we have to rotate. + * + * At this point, it is safe to assume that inserting into an + * empty leaf and appending to a leaf have both been handled + * above. + * + * This leaf needs to have space, either by the empty 1st + * extent record, or by virtue of an l_next_rec < l_count. + */ + ocfs2_rotate_leaf(el, insert_rec); +} + +static inline void ocfs2_update_dinode_clusters(struct inode *inode, + struct ocfs2_dinode *di, + u32 clusters) +{ + le32_add_cpu(&di->i_clusters, clusters); + spin_lock(&OCFS2_I(inode)->ip_lock); + OCFS2_I(inode)->ip_clusters = le32_to_cpu(di->i_clusters); + spin_unlock(&OCFS2_I(inode)->ip_lock); +} + +static int ocfs2_append_rec_to_path(struct inode *inode, handle_t *handle, + struct ocfs2_extent_rec *insert_rec, + struct ocfs2_path *right_path, + struct ocfs2_path **ret_left_path) +{ + int ret, i, next_free; + struct buffer_head *bh; + struct ocfs2_extent_list *el; + struct ocfs2_path *left_path = NULL; + + *ret_left_path = NULL; + + /* + * If our appending insert is at the leftmost edge of a leaf, + * then we might need to update the rightmost records of the + * neighboring path. + */ + el = path_leaf_el(right_path); + next_free = le16_to_cpu(el->l_next_free_rec); + if (next_free == 0 || + (next_free == 1 && ocfs2_is_empty_extent(&el->l_recs[0]))) { + u32 left_cpos; + + ret = ocfs2_find_cpos_for_left_leaf(inode->i_sb, right_path, + &left_cpos); + if (ret) { + mlog_errno(ret); + goto out; + } + + mlog(0, "Append may need a left path update. cpos: %u, " + "left_cpos: %u\n", le32_to_cpu(insert_rec->e_cpos), + left_cpos); + + /* + * No need to worry if the append is already in the + * leftmost leaf. + */ + if (left_cpos) { + left_path = ocfs2_new_path(path_root_bh(right_path), + path_root_el(right_path)); + if (!left_path) { + ret = -ENOMEM; + mlog_errno(ret); + goto out; + } + + ret = ocfs2_find_path(inode, left_path, left_cpos); + if (ret) { + mlog_errno(ret); + goto out; + } + + /* + * ocfs2_insert_path() will pass the left_path to the + * journal for us. + */ + } + } + + ret = ocfs2_journal_access_path(inode, handle, right_path); + if (ret) { + mlog_errno(ret); + goto out; + } + + el = path_root_el(right_path); + bh = path_root_bh(right_path); + i = 0; + while (1) { + next_free = le16_to_cpu(el->l_next_free_rec); + if (next_free == 0) { + ocfs2_error(inode->i_sb, + "Dinode %llu has a bad extent list", + (unsigned long long)OCFS2_I(inode)->ip_blkno); + ret = -EIO; + goto out; + } + + el->l_recs[next_free - 1].e_clusters = insert_rec->e_cpos; + le32_add_cpu(&el->l_recs[next_free - 1].e_clusters, + le32_to_cpu(insert_rec->e_clusters)); + le32_add_cpu(&el->l_recs[next_free - 1].e_clusters, + -le32_to_cpu(el->l_recs[next_free - 1].e_cpos)); + + ret = ocfs2_journal_dirty(handle, bh); + if (ret) + mlog_errno(ret); + + if (++i >= right_path->p_tree_depth) + break; + + bh = right_path->p_node[i].bh; + el = right_path->p_node[i].el; + } + + *ret_left_path = left_path; + ret = 0; +out: + if (ret != 0) + ocfs2_free_path(left_path); + + return ret; +} + +/* + * This function only does inserts on an allocation b-tree. For dinode + * lists, ocfs2_insert_at_leaf() is called directly. + * + * right_path is the path we want to do the actual insert + * in. left_path should only be passed in if we need to update that + * portion of the tree after an edge insert. + */ +static int ocfs2_insert_path(struct inode *inode, + handle_t *handle, + struct ocfs2_path *left_path, + struct ocfs2_path *right_path, + struct ocfs2_extent_rec *insert_rec, + struct ocfs2_insert_type *insert) +{ + int ret, subtree_index; + struct buffer_head *leaf_bh = path_leaf_bh(right_path); + struct ocfs2_extent_list *el; + + /* + * Pass both paths to the journal. The majority of inserts + * will be touching all components anyway. + */ + ret = ocfs2_journal_access_path(inode, handle, right_path); + if (ret < 0) { + mlog_errno(ret); + goto out; + } + + if (left_path) { + int credits = handle->h_buffer_credits; + + /* + * There's a chance that left_path got passed back to + * us without being accounted for in the + * journal. Extend our transaction here to be sure we + * can change those blocks. + */ + credits += left_path->p_tree_depth; + + ret = ocfs2_extend_trans(handle, credits); + if (ret < 0) { + mlog_errno(ret); + goto out; + } + + ret = ocfs2_journal_access_path(inode, handle, left_path); + if (ret < 0) { + mlog_errno(ret); + goto out; + } + } + + el = path_leaf_el(right_path); + + ocfs2_insert_at_leaf(insert_rec, el, insert, inode); + ret = ocfs2_journal_dirty(handle, leaf_bh); + if (ret) + mlog_errno(ret); + + if (left_path) { + /* + * The rotate code has indicated that we need to fix + * up portions of the tree after the insert. + * + * XXX: Should we extend the transaction here? + */ + subtree_index = ocfs2_find_subtree_root(inode, left_path, + right_path); + ocfs2_complete_edge_insert(inode, handle, left_path, + right_path, subtree_index); + } + + ret = 0; +out: + return ret; +} + +static int ocfs2_do_insert_extent(struct inode *inode, + handle_t *handle, + struct buffer_head *di_bh, + struct ocfs2_extent_rec *insert_rec, + struct ocfs2_insert_type *type) +{ + int ret, rotate = 0; + u32 cpos; + struct ocfs2_path *right_path = NULL; + struct ocfs2_path *left_path = NULL; + struct ocfs2_dinode *di; + struct ocfs2_extent_list *el; + + di = (struct ocfs2_dinode *) di_bh->b_data; + el = &di->id2.i_list; + + ret = ocfs2_journal_access(handle, inode, di_bh, + OCFS2_JOURNAL_ACCESS_WRITE); + if (ret) { + mlog_errno(ret); + goto out; + } + + if (le16_to_cpu(el->l_tree_depth) == 0) { + ocfs2_insert_at_leaf(insert_rec, el, type, inode); + goto out_update_clusters; + } + + right_path = ocfs2_new_inode_path(di_bh); + if (!right_path) { + ret = -ENOMEM; + mlog_errno(ret); + goto out; + } + + /* + * Determine the path to start with. Rotations need the + * rightmost path, everything else can go directly to the + * target leaf. + */ + cpos = le32_to_cpu(insert_rec->e_cpos); + if (type->ins_appending == APPEND_NONE && + type->ins_contig == CONTIG_NONE) { + rotate = 1; + cpos = UINT_MAX; + } + + ret = ocfs2_find_path(inode, right_path, cpos); + if (ret) { + mlog_errno(ret); + goto out; + } + + /* + * Rotations and appends need special treatment - they modify + * parts of the tree's above them. + * + * Both might pass back a path immediate to the left of the + * one being inserted to. This will be cause + * ocfs2_insert_path() to modify the rightmost records of + * left_path to account for an edge insert. + * + * XXX: When modifying this code, keep in mind that an insert + * can wind up skipping both of these two special cases... + */ + if (rotate) { + ret = ocfs2_rotate_tree_right(inode, handle, + le32_to_cpu(insert_rec->e_cpos), + right_path, &left_path); + if (ret) { + mlog_errno(ret); + goto out; + } + } else if (type->ins_appending == APPEND_TAIL + && type->ins_contig != CONTIG_LEFT) { + ret = ocfs2_append_rec_to_path(inode, handle, insert_rec, + right_path, &left_path); + if (ret) { + mlog_errno(ret); + goto out; + } + } + + ret = ocfs2_insert_path(inode, handle, left_path, right_path, + insert_rec, type); + if (ret) { + mlog_errno(ret); + goto out; + } + +out_update_clusters: + ocfs2_update_dinode_clusters(inode, di, + le32_to_cpu(insert_rec->e_clusters)); + + ret = ocfs2_journal_dirty(handle, di_bh); + if (ret) + mlog_errno(ret); + +out: + ocfs2_free_path(left_path); + ocfs2_free_path(right_path); + + return ret; +} + +static void ocfs2_figure_contig_type(struct inode *inode, + struct ocfs2_insert_type *insert, + struct ocfs2_extent_list *el, + struct ocfs2_extent_rec *insert_rec) +{ + int i; + enum ocfs2_contig_type contig_type = CONTIG_NONE; + + for(i = 0; i < le16_to_cpu(el->l_next_free_rec); i++) { + contig_type = ocfs2_extent_contig(inode, &el->l_recs[i], + insert_rec); + if (contig_type != CONTIG_NONE) { + insert->ins_contig_index = i; + break; + } + } + insert->ins_contig = contig_type; +} + +/* + * This should only be called against the righmost leaf extent list. + * + * ocfs2_figure_appending_type() will figure out whether we'll have to + * insert at the tail of the rightmost leaf. + * + * This should also work against the dinode list for tree's with 0 + * depth. If we consider the dinode list to be the rightmost leaf node + * then the logic here makes sense. + */ +static void ocfs2_figure_appending_type(struct ocfs2_insert_type *insert, + struct ocfs2_extent_list *el, + struct ocfs2_extent_rec *insert_rec) +{ + int i; + u32 cpos = le32_to_cpu(insert_rec->e_cpos); + struct ocfs2_extent_rec *rec; + + insert->ins_appending = APPEND_NONE; + + BUG_ON(el->l_tree_depth); + + if (!el->l_next_free_rec) + goto set_tail_append; + + if (ocfs2_is_empty_extent(&el->l_recs[0])) { + /* Were all records empty? */ + if (le16_to_cpu(el->l_next_free_rec) == 1) + goto set_tail_append; + } + + i = le16_to_cpu(el->l_next_free_rec) - 1; + rec = &el->l_recs[i]; + + if (cpos >= (le32_to_cpu(rec->e_cpos) + le32_to_cpu(rec->e_clusters))) + goto set_tail_append; + + return; + +set_tail_append: + insert->ins_appending = APPEND_TAIL; +} + +/* + * Helper function called at the begining of an insert. + * + * This computes a few things that are commonly used in the process of + * inserting into the btree: + * - Whether the new extent is contiguous with an existing one. + * - The current tree depth. + * - Whether the insert is an appending one. + * - The total # of free records in the tree. + * + * All of the information is stored on the ocfs2_insert_type + * structure. + */ +static int ocfs2_figure_insert_type(struct inode *inode, + struct buffer_head *di_bh, + struct buffer_head **last_eb_bh, + struct ocfs2_extent_rec *insert_rec, + struct ocfs2_insert_type *insert) +{ + int ret; + struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data; + struct ocfs2_extent_block *eb; + struct ocfs2_extent_list *el; + struct ocfs2_path *path = NULL; + struct buffer_head *bh = NULL; + + el = &di->id2.i_list; + insert->ins_tree_depth = le16_to_cpu(el->l_tree_depth); + + if (el->l_tree_depth) { + /* + * If we have tree depth, we read in the + * rightmost extent block ahead of time as + * ocfs2_figure_insert_type() and ocfs2_add_branch() + * may want it later. + */ + ret = ocfs2_read_block(OCFS2_SB(inode->i_sb), + le64_to_cpu(di->i_last_eb_blk), &bh, + OCFS2_BH_CACHED, inode); + if (ret) { + mlog_exit(ret); + goto out; + } eb = (struct ocfs2_extent_block *) bh->b_data; - if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb)) { - OCFS2_RO_ON_INVALID_EXTENT_BLOCK(inode->i_sb, eb); - status = -EIO; - goto bail; - } el = &eb->h_list; + } - if (le16_to_cpu(el->l_next_free_rec) < - le16_to_cpu(el->l_count)) { - if (lowest_bh) - brelse(lowest_bh); - lowest_bh = bh; - get_bh(lowest_bh); - } + /* + * Unless we have a contiguous insert, we'll need to know if + * there is room left in our allocation tree for another + * extent record. + * + * XXX: This test is simplistic, we can search for empty + * extent records too. + */ + insert->ins_free_records = le16_to_cpu(el->l_count) - + le16_to_cpu(el->l_next_free_rec); + + if (!insert->ins_tree_depth) { + ocfs2_figure_contig_type(inode, insert, el, insert_rec); + ocfs2_figure_appending_type(insert, el, insert_rec); + return 0; } - /* If we didn't find one and the fe doesn't have any room, - * then return '1' */ - if (!lowest_bh - && (fe->id2.i_list.l_next_free_rec == fe->id2.i_list.l_count)) - status = 1; + path = ocfs2_new_inode_path(di_bh); + if (!path) { + ret = -ENOMEM; + mlog_errno(ret); + goto out; + } - *target_bh = lowest_bh; -bail: - if (bh) - brelse(bh); + /* + * In the case that we're inserting past what the tree + * currently accounts for, ocfs2_find_path() will return for + * us the rightmost tree path. This is accounted for below in + * the appending code. + */ + ret = ocfs2_find_path(inode, path, le32_to_cpu(insert_rec->e_cpos)); + if (ret) { + mlog_errno(ret); + goto out; + } - mlog_exit(status); - return status; + el = path_leaf_el(path); + + /* + * Now that we have the path, there's two things we want to determine: + * 1) Contiguousness (also set contig_index if this is so) + * + * 2) Are we doing an append? We can trivially break this up + * into two types of appends: simple record append, or a + * rotate inside the tail leaf. + */ + ocfs2_figure_contig_type(inode, insert, el, insert_rec); + + /* + * The insert code isn't quite ready to deal with all cases of + * left contiguousness. Specifically, if it's an insert into + * the 1st record in a leaf, it will require the adjustment of + * e_clusters on the last record of the path directly to it's + * left. For now, just catch that case and fool the layers + * above us. This works just fine for tree_depth == 0, which + * is why we allow that above. + */ + if (insert->ins_contig == CONTIG_LEFT && + insert->ins_contig_index == 0) + insert->ins_contig = CONTIG_NONE; + + /* + * Ok, so we can simply compare against last_eb to figure out + * whether the path doesn't exist. This will only happen in + * the case that we're doing a tail append, so maybe we can + * take advantage of that information somehow. + */ + if (le64_to_cpu(di->i_last_eb_blk) == path_leaf_bh(path)->b_blocknr) { + /* + * Ok, ocfs2_find_path() returned us the rightmost + * tree path. This might be an appending insert. There are + * two cases: + * 1) We're doing a true append at the tail: + * -This might even be off the end of the leaf + * 2) We're "appending" by rotating in the tail + */ + ocfs2_figure_appending_type(insert, el, insert_rec); + } + +out: + ocfs2_free_path(path); + + if (ret == 0) + *last_eb_bh = bh; + else + brelse(bh); + return ret; } -/* the caller needs to update fe->i_clusters */ +/* + * Insert an extent into an inode btree. + * + * The caller needs to update fe->i_clusters + */ int ocfs2_insert_extent(struct ocfs2_super *osb, handle_t *handle, struct inode *inode, struct buffer_head *fe_bh, + u32 cpos, u64 start_blk, u32 new_clusters, struct ocfs2_alloc_context *meta_ac) { - int status, i, shift; + int status, shift; struct buffer_head *last_eb_bh = NULL; struct buffer_head *bh = NULL; - struct ocfs2_dinode *fe; - struct ocfs2_extent_block *eb; - struct ocfs2_extent_list *el; - - mlog_entry_void(); - - mlog(0, "add %u clusters starting at block %llu to inode %llu\n", - new_clusters, (unsigned long long)start_blk, - (unsigned long long)OCFS2_I(inode)->ip_blkno); - - fe = (struct ocfs2_dinode *) fe_bh->b_data; - el = &fe->id2.i_list; - - if (el->l_tree_depth) { - /* jump to end of tree */ - status = ocfs2_read_block(osb, le64_to_cpu(fe->i_last_eb_blk), - &last_eb_bh, OCFS2_BH_CACHED, inode); - if (status < 0) { - mlog_exit(status); - goto bail; - } - eb = (struct ocfs2_extent_block *) last_eb_bh->b_data; - el = &eb->h_list; + struct ocfs2_insert_type insert = {0, }; + struct ocfs2_extent_rec rec; + + mlog(0, "add %u clusters at position %u to inode %llu\n", + new_clusters, cpos, (unsigned long long)OCFS2_I(inode)->ip_blkno); + + mlog_bug_on_msg(!ocfs2_sparse_alloc(osb) && + (OCFS2_I(inode)->ip_clusters != cpos), + "Device %s, asking for sparse allocation: inode %llu, " + "cpos %u, clusters %u\n", + osb->dev_str, + (unsigned long long)OCFS2_I(inode)->ip_blkno, cpos, + OCFS2_I(inode)->ip_clusters); + + rec.e_cpos = cpu_to_le32(cpos); + rec.e_blkno = cpu_to_le64(start_blk); + rec.e_clusters = cpu_to_le32(new_clusters); + + status = ocfs2_figure_insert_type(inode, fe_bh, &last_eb_bh, &rec, + &insert); + if (status < 0) { + mlog_errno(status); + goto bail; } - /* Can we allocate without adding/shifting tree bits? */ - i = le16_to_cpu(el->l_next_free_rec) - 1; - if (le16_to_cpu(el->l_next_free_rec) == 0 - || (le16_to_cpu(el->l_next_free_rec) < le16_to_cpu(el->l_count)) - || le32_to_cpu(el->l_recs[i].e_clusters) == 0 - || ocfs2_extent_contig(inode, &el->l_recs[i], start_blk)) - goto out_add; + mlog(0, "Insert.appending: %u, Insert.Contig: %u, " + "Insert.contig_index: %d, Insert.free_records: %d, " + "Insert.tree_depth: %d\n", + insert.ins_appending, insert.ins_contig, insert.ins_contig_index, + insert.ins_free_records, insert.ins_tree_depth); - mlog(0, "ocfs2_allocate_extent: couldn't do a simple add, traversing " - "tree now.\n"); + /* + * Avoid growing the tree unless we're out of records and the + * insert type requres one. + */ + if (insert.ins_contig != CONTIG_NONE || insert.ins_free_records) + goto out_add; shift = ocfs2_find_branch_target(osb, inode, fe_bh, &bh); if (shift < 0) { @@ -866,13 +2344,9 @@ int ocfs2_insert_extent(struct ocfs2_super *osb, * and didn't find room for any more extents - we need to add * another tree level */ if (shift) { - /* if we hit a leaf, we'd better be empty :) */ - BUG_ON(le16_to_cpu(el->l_next_free_rec) != - le16_to_cpu(el->l_count)); BUG_ON(bh); - mlog(0, "ocfs2_allocate_extent: need to shift tree depth " - "(current = %u)\n", - le16_to_cpu(fe->id2.i_list.l_tree_depth)); + mlog(0, "need to shift tree depth " + "(current = %d)\n", insert.ins_tree_depth); /* ocfs2_shift_tree_depth will return us a buffer with * the new extent block (so we can pass that to @@ -883,15 +2357,16 @@ int ocfs2_insert_extent(struct ocfs2_super *osb, mlog_errno(status); goto bail; } + insert.ins_tree_depth++; /* Special case: we have room now if we shifted from * tree_depth 0 */ - if (fe->id2.i_list.l_tree_depth == cpu_to_le16(1)) + if (insert.ins_tree_depth == 1) goto out_add; } /* call ocfs2_add_branch to add the final part of the tree with * the new data. */ - mlog(0, "ocfs2_allocate_extent: add branch. bh = %p\n", bh); + mlog(0, "add branch. bh = %p\n", bh); status = ocfs2_add_branch(osb, handle, inode, fe_bh, bh, last_eb_bh, meta_ac); if (status < 0) { @@ -900,9 +2375,8 @@ int ocfs2_insert_extent(struct ocfs2_super *osb, } out_add: - /* Finally, we can add clusters. */ - status = ocfs2_do_insert_extent(osb, handle, inode, fe_bh, - start_blk, new_clusters); + /* Finally, we can add clusters. This might rotate the tree for us. */ + status = ocfs2_do_insert_extent(inode, handle, fe_bh, &rec, &insert); if (status < 0) mlog_errno(status); @@ -1447,140 +2921,141 @@ int ocfs2_truncate_log_init(struct ocfs2_super *osb) * block will be deleted, and if it will, what the new last extent * block will be so we can update his h_next_leaf_blk field, as well * as the dinodes i_last_eb_blk */ -static int ocfs2_find_new_last_ext_blk(struct ocfs2_super *osb, - struct inode *inode, - struct ocfs2_dinode *fe, +static int ocfs2_find_new_last_ext_blk(struct inode *inode, u32 new_i_clusters, - struct buffer_head *old_last_eb, + struct ocfs2_path *path, struct buffer_head **new_last_eb) { - int i, status = 0; - u64 block = 0; + int ret = 0; + u32 cpos; struct ocfs2_extent_block *eb; struct ocfs2_extent_list *el; struct buffer_head *bh = NULL; *new_last_eb = NULL; - if (!OCFS2_IS_VALID_DINODE(fe)) { - OCFS2_RO_ON_INVALID_DINODE(inode->i_sb, fe); - status = -EIO; - goto bail; - } - /* we have no tree, so of course, no last_eb. */ - if (!fe->id2.i_list.l_tree_depth) - goto bail; + if (!path->p_tree_depth) + goto out; /* trunc to zero special case - this makes tree_depth = 0 * regardless of what it is. */ if (!new_i_clusters) - goto bail; + goto out; - eb = (struct ocfs2_extent_block *) old_last_eb->b_data; - el = &(eb->h_list); + el = path_leaf_el(path); BUG_ON(!el->l_next_free_rec); /* Make sure that this guy will actually be empty after we * clear away the data. */ - if (le32_to_cpu(el->l_recs[0].e_cpos) < new_i_clusters) - goto bail; + if (ocfs2_is_empty_extent(&el->l_recs[0])) { + if (le16_to_cpu(el->l_next_free_rec) > 1 && + le32_to_cpu(el->l_recs[1].e_cpos) < new_i_clusters) + goto out; + } else if (le32_to_cpu(el->l_recs[0].e_cpos) < new_i_clusters) + goto out; - /* Ok, at this point, we know that last_eb will definitely - * change, so lets traverse the tree and find the second to - * last extent block. */ - el = &(fe->id2.i_list); - /* go down the tree, */ - do { - for(i = (le16_to_cpu(el->l_next_free_rec) - 1); i >= 0; i--) { - if (le32_to_cpu(el->l_recs[i].e_cpos) < - new_i_clusters) { - block = le64_to_cpu(el->l_recs[i].e_blkno); - break; - } - } - BUG_ON(i < 0); + ret = ocfs2_find_cpos_for_left_leaf(inode->i_sb, path, &cpos); + if (ret) { + mlog_errno(ret); + goto out; + } - if (bh) { - brelse(bh); - bh = NULL; - } + ret = ocfs2_find_leaf(inode, path_root_el(path), cpos, &bh); + if (ret) { + mlog_errno(ret); + goto out; + } - status = ocfs2_read_block(osb, block, &bh, OCFS2_BH_CACHED, - inode); - if (status < 0) { - mlog_errno(status); - goto bail; - } - eb = (struct ocfs2_extent_block *) bh->b_data; - el = &eb->h_list; - if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb)) { - OCFS2_RO_ON_INVALID_EXTENT_BLOCK(inode->i_sb, eb); - status = -EIO; - goto bail; - } - } while (el->l_tree_depth); + eb = (struct ocfs2_extent_block *) bh->b_data; + el = &eb->h_list; + if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb)) { + OCFS2_RO_ON_INVALID_EXTENT_BLOCK(inode->i_sb, eb); + ret = -EROFS; + goto out; + } *new_last_eb = bh; get_bh(*new_last_eb); - mlog(0, "returning block %llu\n", - (unsigned long long)le64_to_cpu(eb->h_blkno)); -bail: - if (bh) - brelse(bh); + mlog(0, "returning block %llu, (cpos: %u)\n", + (unsigned long long)le64_to_cpu(eb->h_blkno), cpos); +out: + brelse(bh); - return status; + return ret; } static int ocfs2_do_truncate(struct ocfs2_super *osb, unsigned int clusters_to_del, struct inode *inode, struct buffer_head *fe_bh, - struct buffer_head *old_last_eb_bh, handle_t *handle, - struct ocfs2_truncate_context *tc) + struct ocfs2_truncate_context *tc, + struct ocfs2_path *path) { - int status, i, depth; + int status, i, index; struct ocfs2_dinode *fe; struct ocfs2_extent_block *eb; struct ocfs2_extent_block *last_eb = NULL; struct ocfs2_extent_list *el; struct buffer_head *eb_bh = NULL; struct buffer_head *last_eb_bh = NULL; - u64 next_eb = 0; u64 delete_blk = 0; fe = (struct ocfs2_dinode *) fe_bh->b_data; - status = ocfs2_find_new_last_ext_blk(osb, - inode, - fe, + status = ocfs2_find_new_last_ext_blk(inode, le32_to_cpu(fe->i_clusters) - - clusters_to_del, - old_last_eb_bh, - &last_eb_bh); + clusters_to_del, + path, &last_eb_bh); if (status < 0) { mlog_errno(status); goto bail; } - if (last_eb_bh) + + /* + * Each component will be touched, so we might as well journal + * here to avoid having to handle errors later. + */ + for (i = 0; i < path_num_items(path); i++) { + status = ocfs2_journal_access(handle, inode, + path->p_node[i].bh, + OCFS2_JOURNAL_ACCESS_WRITE); + if (status < 0) { + mlog_errno(status); + goto bail; + } + } + + if (last_eb_bh) { + status = ocfs2_journal_access(handle, inode, last_eb_bh, + OCFS2_JOURNAL_ACCESS_WRITE); + if (status < 0) { + mlog_errno(status); + goto bail; + } + last_eb = (struct ocfs2_extent_block *) last_eb_bh->b_data; + } - status = ocfs2_journal_access(handle, inode, fe_bh, - OCFS2_JOURNAL_ACCESS_WRITE); - if (status < 0) { - mlog_errno(status); + el = &(fe->id2.i_list); + + /* + * Lower levels depend on this never happening, but it's best + * to check it up here before changing the tree. + */ + if (el->l_tree_depth && ocfs2_is_empty_extent(&el->l_recs[0])) { + ocfs2_error(inode->i_sb, + "Inode %lu has an empty extent record, depth %u\n", + inode->i_ino, le16_to_cpu(el->l_tree_depth)); goto bail; } - el = &(fe->id2.i_list); spin_lock(&OCFS2_I(inode)->ip_lock); OCFS2_I(inode)->ip_clusters = le32_to_cpu(fe->i_clusters) - clusters_to_del; spin_unlock(&OCFS2_I(inode)->ip_lock); le32_add_cpu(&fe->i_clusters, -clusters_to_del); - fe->i_mtime = cpu_to_le64(CURRENT_TIME.tv_sec); - fe->i_mtime_nsec = cpu_to_le32(CURRENT_TIME.tv_nsec); i = le16_to_cpu(el->l_next_free_rec) - 1; @@ -1589,26 +3064,34 @@ static int ocfs2_do_truncate(struct ocfs2_super *osb, /* tree depth zero, we can just delete the clusters, otherwise * we need to record the offset of the next level extent block * as we may overwrite it. */ - if (!el->l_tree_depth) + if (!el->l_tree_depth) { delete_blk = le64_to_cpu(el->l_recs[i].e_blkno) + ocfs2_clusters_to_blocks(osb->sb, le32_to_cpu(el->l_recs[i].e_clusters)); - else - next_eb = le64_to_cpu(el->l_recs[i].e_blkno); - if (!el->l_recs[i].e_clusters) { - /* if we deleted the whole extent record, then clear - * out the other fields and update the extent - * list. For depth > 0 trees, we've already recorded - * the extent block in 'next_eb' */ - el->l_recs[i].e_cpos = 0; - el->l_recs[i].e_blkno = 0; - BUG_ON(!el->l_next_free_rec); - le16_add_cpu(&el->l_next_free_rec, -1); + if (!el->l_recs[i].e_clusters) { + /* if we deleted the whole extent record, then clear + * out the other fields and update the extent + * list. + */ + el->l_recs[i].e_cpos = 0; + el->l_recs[i].e_blkno = 0; + BUG_ON(!el->l_next_free_rec); + le16_add_cpu(&el->l_next_free_rec, -1); + + /* + * The leftmost record might be an empty extent - + * delete it here too. + */ + if (i == 1 && ocfs2_is_empty_extent(&el->l_recs[0])) { + el->l_recs[0].e_cpos = 0; + el->l_recs[0].e_blkno = 0; + el->l_next_free_rec = 0; + } + } } - depth = le16_to_cpu(el->l_tree_depth); - if (!fe->i_clusters) { + if (le32_to_cpu(fe->i_clusters) == 0) { /* trunc to zero is a special case. */ el->l_tree_depth = 0; fe->i_last_eb_blk = 0; @@ -1625,12 +3108,6 @@ static int ocfs2_do_truncate(struct ocfs2_super *osb, /* If there will be a new last extent block, then by * definition, there cannot be any leaves to the right of * him. */ - status = ocfs2_journal_access(handle, inode, last_eb_bh, - OCFS2_JOURNAL_ACCESS_WRITE); - if (status < 0) { - mlog_errno(status); - goto bail; - } last_eb->h_next_leaf_blk = 0; status = ocfs2_journal_dirty(handle, last_eb_bh); if (status < 0) { @@ -1639,33 +3116,25 @@ static int ocfs2_do_truncate(struct ocfs2_super *osb, } } + index = 1; /* if our tree depth > 0, update all the tree blocks below us. */ - while (depth) { - mlog(0, "traveling tree (depth = %d, next_eb = %llu)\n", - depth, (unsigned long long)next_eb); - status = ocfs2_read_block(osb, next_eb, &eb_bh, - OCFS2_BH_CACHED, inode); - if (status < 0) { - mlog_errno(status); - goto bail; - } + while (index <= path->p_tree_depth) { + eb_bh = path->p_node[index].bh; eb = (struct ocfs2_extent_block *)eb_bh->b_data; - if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb)) { - OCFS2_RO_ON_INVALID_EXTENT_BLOCK(inode->i_sb, eb); - status = -EIO; - goto bail; - } - el = &(eb->h_list); + el = path->p_node[index].el; - status = ocfs2_journal_access(handle, inode, eb_bh, - OCFS2_JOURNAL_ACCESS_WRITE); - if (status < 0) { - mlog_errno(status); - goto bail; - } + mlog(0, "traveling tree (index = %d, extent block: %llu)\n", + index, (unsigned long long)eb_bh->b_blocknr); BUG_ON(le16_to_cpu(el->l_next_free_rec) == 0); - BUG_ON(depth != (le16_to_cpu(el->l_tree_depth) + 1)); + if (index != + (path->p_tree_depth - le16_to_cpu(el->l_tree_depth))) { + ocfs2_error(inode->i_sb, + "Inode %lu has invalid ext. block %llu\n", + inode->i_ino, + (unsigned long long)eb_bh->b_blocknr); + goto bail; + } i = le16_to_cpu(el->l_next_free_rec) - 1; @@ -1680,7 +3149,6 @@ static int ocfs2_do_truncate(struct ocfs2_super *osb, BUG_ON(le32_to_cpu(el->l_recs[i].e_clusters) < clusters_to_del); le32_add_cpu(&el->l_recs[i].e_clusters, -clusters_to_del); - next_eb = le64_to_cpu(el->l_recs[i].e_blkno); /* bottom-most block requires us to delete data.*/ if (!el->l_tree_depth) delete_blk = le64_to_cpu(el->l_recs[i].e_blkno) @@ -1692,6 +3160,12 @@ static int ocfs2_do_truncate(struct ocfs2_super *osb, BUG_ON(!el->l_next_free_rec); le16_add_cpu(&el->l_next_free_rec, -1); } + if (i == 1 && ocfs2_is_empty_extent(&el->l_recs[0])) { + el->l_recs[0].e_cpos = 0; + el->l_recs[0].e_blkno = 0; + el->l_next_free_rec = 0; + } + mlog(0, "extent block %llu, after: record %d: " "(%u, %u, %llu), next = %u\n", (unsigned long long)le64_to_cpu(eb->h_blkno), i, @@ -1714,6 +3188,22 @@ static int ocfs2_do_truncate(struct ocfs2_super *osb, BUG_ON(el->l_recs[0].e_clusters); BUG_ON(el->l_recs[0].e_cpos); BUG_ON(el->l_recs[0].e_blkno); + + /* + * We need to remove this extent block from + * the list above it. + * + * Since we've passed it already in this loop, + * no need to worry about journaling. + */ + el = path->p_node[index - 1].el; + i = le16_to_cpu(el->l_next_free_rec) - 1; + BUG_ON(i < 0); + el->l_recs[i].e_cpos = 0; + el->l_recs[i].e_clusters = 0; + el->l_recs[i].e_blkno = 0; + le16_add_cpu(&el->l_next_free_rec, -1); + if (eb->h_suballoc_slot == 0) { /* * This code only understands how to @@ -1736,9 +3226,7 @@ static int ocfs2_do_truncate(struct ocfs2_super *osb, } } } - brelse(eb_bh); - eb_bh = NULL; - depth--; + index++; } BUG_ON(!delete_blk); @@ -1750,10 +3238,7 @@ static int ocfs2_do_truncate(struct ocfs2_super *osb, } status = 0; bail: - if (!status) - ocfs2_extent_map_trunc(inode, le32_to_cpu(fe->i_clusters)); - else - ocfs2_extent_map_drop(inode, 0); + mlog_exit(status); return status; } @@ -1770,82 +3255,70 @@ int ocfs2_commit_truncate(struct ocfs2_super *osb, struct ocfs2_truncate_context *tc) { int status, i, credits, tl_sem = 0; - u32 clusters_to_del, target_i_clusters; - u64 last_eb = 0; - struct ocfs2_dinode *fe; - struct ocfs2_extent_block *eb; + u32 clusters_to_del, new_highest_cpos, range; struct ocfs2_extent_list *el; - struct buffer_head *last_eb_bh; handle_t *handle = NULL; struct inode *tl_inode = osb->osb_tl_inode; + struct ocfs2_path *path = NULL; mlog_entry_void(); down_write(&OCFS2_I(inode)->ip_alloc_sem); - target_i_clusters = ocfs2_clusters_for_bytes(osb->sb, + new_highest_cpos = ocfs2_clusters_for_bytes(osb->sb, i_size_read(inode)); - last_eb_bh = tc->tc_last_eb_bh; - tc->tc_last_eb_bh = NULL; - - fe = (struct ocfs2_dinode *) fe_bh->b_data; - - if (fe->id2.i_list.l_tree_depth) { - eb = (struct ocfs2_extent_block *) last_eb_bh->b_data; - el = &eb->h_list; - } else - el = &fe->id2.i_list; - last_eb = le64_to_cpu(fe->i_last_eb_blk); + path = ocfs2_new_inode_path(fe_bh); + if (!path) { + status = -ENOMEM; + mlog_errno(status); + goto bail; + } start: - mlog(0, "ocfs2_commit_truncate: fe->i_clusters = %u, " - "last_eb = %llu, fe->i_last_eb_blk = %llu, " - "fe->id2.i_list.l_tree_depth = %u last_eb_bh = %p\n", - le32_to_cpu(fe->i_clusters), (unsigned long long)last_eb, - (unsigned long long)le64_to_cpu(fe->i_last_eb_blk), - le16_to_cpu(fe->id2.i_list.l_tree_depth), last_eb_bh); - - if (last_eb != le64_to_cpu(fe->i_last_eb_blk)) { - mlog(0, "last_eb changed!\n"); - BUG_ON(!fe->id2.i_list.l_tree_depth); - last_eb = le64_to_cpu(fe->i_last_eb_blk); - /* i_last_eb_blk may have changed, read it if - * necessary. We don't have to worry about the - * truncate to zero case here (where there becomes no - * last_eb) because we never loop back after our work - * is done. */ - if (last_eb_bh) { - brelse(last_eb_bh); - last_eb_bh = NULL; - } - - status = ocfs2_read_block(osb, last_eb, - &last_eb_bh, OCFS2_BH_CACHED, - inode); - if (status < 0) { - mlog_errno(status); - goto bail; - } - eb = (struct ocfs2_extent_block *) last_eb_bh->b_data; - if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb)) { - OCFS2_RO_ON_INVALID_EXTENT_BLOCK(inode->i_sb, eb); - status = -EIO; - goto bail; - } - el = &(eb->h_list); + /* + * Truncate always works against the rightmost tree branch. + */ + status = ocfs2_find_path(inode, path, UINT_MAX); + if (status) { + mlog_errno(status); + goto bail; } - /* by now, el will point to the extent list on the bottom most - * portion of this tree. */ + mlog(0, "inode->ip_clusters = %u, tree_depth = %u\n", + OCFS2_I(inode)->ip_clusters, path->p_tree_depth); + + /* + * By now, el will point to the extent list on the bottom most + * portion of this tree. Only the tail record is considered in + * each pass. + * + * We handle the following cases, in order: + * - empty extent: delete the remaining branch + * - remove the entire record + * - remove a partial record + * - no record needs to be removed (truncate has completed) + */ + el = path_leaf_el(path); i = le16_to_cpu(el->l_next_free_rec) - 1; - if (le32_to_cpu(el->l_recs[i].e_cpos) >= target_i_clusters) + range = le32_to_cpu(el->l_recs[i].e_cpos) + + le32_to_cpu(el->l_recs[i].e_clusters); + if (i == 0 && ocfs2_is_empty_extent(&el->l_recs[i])) { + clusters_to_del = 0; + } else if (le32_to_cpu(el->l_recs[i].e_cpos) >= new_highest_cpos) { clusters_to_del = le32_to_cpu(el->l_recs[i].e_clusters); - else + } else if (range > new_highest_cpos) { clusters_to_del = (le32_to_cpu(el->l_recs[i].e_clusters) + le32_to_cpu(el->l_recs[i].e_cpos)) - - target_i_clusters; + new_highest_cpos; + } else { + status = 0; + goto bail; + } - mlog(0, "clusters_to_del = %u in this pass\n", clusters_to_del); + mlog(0, "clusters_to_del = %u in this pass, tail blk=%llu\n", + clusters_to_del, (unsigned long long)path_leaf_bh(path)->b_blocknr); + + BUG_ON(clusters_to_del == 0); mutex_lock(&tl_inode->i_mutex); tl_sem = 1; @@ -1861,7 +3334,8 @@ start: } credits = ocfs2_calc_tree_trunc_credits(osb->sb, clusters_to_del, - fe, el); + (struct ocfs2_dinode *)fe_bh->b_data, + el); handle = ocfs2_start_trans(osb, credits); if (IS_ERR(handle)) { status = PTR_ERR(handle); @@ -1870,13 +3344,8 @@ start: goto bail; } - inode->i_ctime = inode->i_mtime = CURRENT_TIME; - status = ocfs2_mark_inode_dirty(handle, inode, fe_bh); - if (status < 0) - mlog_errno(status); - - status = ocfs2_do_truncate(osb, clusters_to_del, inode, fe_bh, - last_eb_bh, handle, tc); + status = ocfs2_do_truncate(osb, clusters_to_del, inode, fe_bh, handle, + tc, path); if (status < 0) { mlog_errno(status); goto bail; @@ -1888,8 +3357,12 @@ start: ocfs2_commit_trans(osb, handle); handle = NULL; - BUG_ON(le32_to_cpu(fe->i_clusters) < target_i_clusters); - if (le32_to_cpu(fe->i_clusters) > target_i_clusters) + ocfs2_reinit_path(path, 1); + + /* + * Only loop if we still have allocation. + */ + if (OCFS2_I(inode)->ip_clusters) goto start; bail: up_write(&OCFS2_I(inode)->ip_alloc_sem); @@ -1902,8 +3375,7 @@ bail: if (handle) ocfs2_commit_trans(osb, handle); - if (last_eb_bh) - brelse(last_eb_bh); + ocfs2_free_path(path); /* This will drop the ext_alloc cluster lock for us */ ocfs2_free_truncate_context(tc); @@ -1912,7 +3384,6 @@ bail: return status; } - /* * Expects the inode to already be locked. This will figure out which * inodes need to be locked and will put them on the returned truncate @@ -1923,7 +3394,7 @@ int ocfs2_prepare_truncate(struct ocfs2_super *osb, struct buffer_head *fe_bh, struct ocfs2_truncate_context **tc) { - int status, metadata_delete; + int status, metadata_delete, i; unsigned int new_i_clusters; struct ocfs2_dinode *fe; struct ocfs2_extent_block *eb; @@ -1944,7 +3415,8 @@ int ocfs2_prepare_truncate(struct ocfs2_super *osb, "%llu\n", fe->i_clusters, new_i_clusters, (unsigned long long)fe->i_size); - if (le32_to_cpu(fe->i_clusters) <= new_i_clusters) { + if (!ocfs2_sparse_alloc(osb) && + le32_to_cpu(fe->i_clusters) <= new_i_clusters) { ocfs2_error(inode->i_sb, "Dinode %llu has cluster count " "%u and size %llu whereas struct inode has " "cluster count %u and size %llu which caused an " @@ -1986,7 +3458,15 @@ int ocfs2_prepare_truncate(struct ocfs2_super *osb, goto bail; } el = &(eb->h_list); - if (le32_to_cpu(el->l_recs[0].e_cpos) >= new_i_clusters) + + i = 0; + if (ocfs2_is_empty_extent(&el->l_recs[0])) + i = 1; + /* + * XXX: Should we check that next_free_rec contains + * the extent? + */ + if (le32_to_cpu(el->l_recs[i].e_cpos) >= new_i_clusters) metadata_delete = 1; } -- cgit From 363041a5f74b953ab6b705ac9c88e5eda218a24b Mon Sep 17 00:00:00 2001 From: Mark Fasheh Date: Wed, 17 Jan 2007 12:31:35 -0800 Subject: ocfs2: temporarily remove extent map caching The code in extent_map.c is not prepared to deal with a subtree being rotated between lookups. This can happen when filling holes in sparse files. Instead of a lengthy patch to update the code (which would likely lose the benefit of caching subtree roots), we remove most of the algorithms and implement a simple path based lookup. A less ambitious extent caching scheme will be added in a later patch. Signed-off-by: Mark Fasheh --- fs/ocfs2/alloc.c | 5 +- fs/ocfs2/alloc.h | 3 + fs/ocfs2/aops.c | 8 +- fs/ocfs2/dir.c | 2 +- fs/ocfs2/dlmglue.c | 4 - fs/ocfs2/extent_map.c | 1024 ++++--------------------------------------------- fs/ocfs2/extent_map.h | 19 +- fs/ocfs2/inode.c | 6 +- fs/ocfs2/inode.h | 1 - fs/ocfs2/journal.c | 3 +- fs/ocfs2/namei.c | 3 +- fs/ocfs2/ocfs2.h | 5 - fs/ocfs2/slot_map.c | 2 +- fs/ocfs2/super.c | 7 - 14 files changed, 96 insertions(+), 996 deletions(-) (limited to 'fs/ocfs2/alloc.c') diff --git a/fs/ocfs2/alloc.c b/fs/ocfs2/alloc.c index a96696867576..85a05f120249 100644 --- a/fs/ocfs2/alloc.c +++ b/fs/ocfs2/alloc.c @@ -1146,9 +1146,8 @@ static void find_leaf_ins(void *data, struct buffer_head *bh) * * This function doesn't handle non btree extent lists. */ -static int ocfs2_find_leaf(struct inode *inode, - struct ocfs2_extent_list *root_el, u32 cpos, - struct buffer_head **leaf_bh) +int ocfs2_find_leaf(struct inode *inode, struct ocfs2_extent_list *root_el, + u32 cpos, struct buffer_head **leaf_bh) { int ret; struct buffer_head *bh = NULL; diff --git a/fs/ocfs2/alloc.h b/fs/ocfs2/alloc.h index b0880fdb3108..bff2a162b030 100644 --- a/fs/ocfs2/alloc.h +++ b/fs/ocfs2/alloc.h @@ -80,4 +80,7 @@ int ocfs2_commit_truncate(struct ocfs2_super *osb, struct buffer_head *fe_bh, struct ocfs2_truncate_context *tc); +int ocfs2_find_leaf(struct inode *inode, struct ocfs2_extent_list *root_el, + u32 cpos, struct buffer_head **leaf_bh); + #endif /* OCFS2_ALLOC_H */ diff --git a/fs/ocfs2/aops.c b/fs/ocfs2/aops.c index 875c11443817..f3b0cc5cba1a 100644 --- a/fs/ocfs2/aops.c +++ b/fs/ocfs2/aops.c @@ -158,8 +158,7 @@ static int ocfs2_get_block(struct inode *inode, sector_t iblock, if (err) goto bail; - err = ocfs2_extent_map_get_blocks(inode, iblock, 1, &p_blkno, - NULL); + err = ocfs2_extent_map_get_blocks(inode, iblock, &p_blkno, NULL); if (err) { mlog(ML_ERROR, "Error %d from get_blocks(0x%p, %llu, 1, " "%llu, NULL)\n", err, inode, (unsigned long long)iblock, @@ -499,8 +498,7 @@ static sector_t ocfs2_bmap(struct address_space *mapping, sector_t block) down_read(&OCFS2_I(inode)->ip_alloc_sem); } - err = ocfs2_extent_map_get_blocks(inode, block, 1, &p_blkno, - NULL); + err = ocfs2_extent_map_get_blocks(inode, block, &p_blkno, NULL); if (!INODE_JOURNAL(inode)) { up_read(&OCFS2_I(inode)->ip_alloc_sem); @@ -574,7 +572,7 @@ static int ocfs2_direct_IO_get_blocks(struct inode *inode, sector_t iblock, /* This figures out the size of the next contiguous block, and * our logical offset */ - ret = ocfs2_extent_map_get_blocks(inode, iblock, 1, &p_blkno, + ret = ocfs2_extent_map_get_blocks(inode, iblock, &p_blkno, &contig_blocks); if (ret) { mlog(ML_ERROR, "get_blocks() failed iblock=%llu\n", diff --git a/fs/ocfs2/dir.c b/fs/ocfs2/dir.c index 5d211c53a8d8..c91490670ffa 100644 --- a/fs/ocfs2/dir.c +++ b/fs/ocfs2/dir.c @@ -379,7 +379,7 @@ int ocfs2_do_extend_dir(struct super_block *sb, status = ocfs2_extent_map_get_blocks(dir, (dir->i_blocks >> (sb->s_blocksize_bits - 9)), - 1, &p_blkno, NULL); + &p_blkno, NULL); if (status < 0) { mlog_errno(status); goto bail; diff --git a/fs/ocfs2/dlmglue.c b/fs/ocfs2/dlmglue.c index ca4f0e0e7587..8de6678a340a 100644 --- a/fs/ocfs2/dlmglue.c +++ b/fs/ocfs2/dlmglue.c @@ -1614,10 +1614,6 @@ static int ocfs2_meta_lock_update(struct inode *inode, * for the inode metadata. */ ocfs2_metadata_cache_purge(inode); - /* will do nothing for inode types that don't use the extent - * map (bitmap files, etc) */ - ocfs2_extent_map_trunc(inode, 0); - if (ocfs2_meta_lvb_is_trustable(inode, lockres)) { mlog(0, "Trusting LVB on inode %llu\n", (unsigned long long)oi->ip_blkno); diff --git a/fs/ocfs2/extent_map.c b/fs/ocfs2/extent_map.c index 80ac69f11d9f..3b4322fd369a 100644 --- a/fs/ocfs2/extent_map.c +++ b/fs/ocfs2/extent_map.c @@ -3,8 +3,7 @@ * * extent_map.c * - * In-memory extent map for OCFS2. Man, this code was prettier in - * the library. + * Block/Cluster mapping functions * * Copyright (C) 2004 Oracle. All rights reserved. * @@ -26,1016 +25,155 @@ #include #include #include -#include -#include #define MLOG_MASK_PREFIX ML_EXTENT_MAP #include #include "ocfs2.h" +#include "alloc.h" #include "extent_map.h" #include "inode.h" #include "super.h" #include "buffer_head_io.h" - -/* - * SUCK SUCK SUCK - * Our headers are so bad that struct ocfs2_extent_map is in ocfs.h - */ - -struct ocfs2_extent_map_entry { - struct rb_node e_node; - int e_tree_depth; - struct ocfs2_extent_rec e_rec; -}; - -struct ocfs2_em_insert_context { - int need_left; - int need_right; - struct ocfs2_extent_map_entry *new_ent; - struct ocfs2_extent_map_entry *old_ent; - struct ocfs2_extent_map_entry *left_ent; - struct ocfs2_extent_map_entry *right_ent; -}; - -static struct kmem_cache *ocfs2_em_ent_cachep = NULL; - - -static struct ocfs2_extent_map_entry * -ocfs2_extent_map_lookup(struct ocfs2_extent_map *em, - u32 cpos, u32 clusters, - struct rb_node ***ret_p, - struct rb_node **ret_parent); -static int ocfs2_extent_map_insert(struct inode *inode, - struct ocfs2_extent_rec *rec, - int tree_depth); -static int ocfs2_extent_map_insert_entry(struct ocfs2_extent_map *em, - struct ocfs2_extent_map_entry *ent); -static int ocfs2_extent_map_find_leaf(struct inode *inode, - u32 cpos, u32 clusters, - struct ocfs2_extent_list *el); -static int ocfs2_extent_map_lookup_read(struct inode *inode, - u32 cpos, u32 clusters, - struct ocfs2_extent_map_entry **ret_ent); -static int ocfs2_extent_map_try_insert(struct inode *inode, - struct ocfs2_extent_rec *rec, - int tree_depth, - struct ocfs2_em_insert_context *ctxt); - -/* returns 1 only if the rec contains all the given clusters -- that is that - * rec's cpos is <= the cluster cpos and that the rec endpoint (cpos + - * clusters) is >= the argument's endpoint */ -static int ocfs2_extent_rec_contains_clusters(struct ocfs2_extent_rec *rec, - u32 cpos, u32 clusters) -{ - if (le32_to_cpu(rec->e_cpos) > cpos) - return 0; - if (cpos + clusters > le32_to_cpu(rec->e_cpos) + - le32_to_cpu(rec->e_clusters)) - return 0; - return 1; -} - - /* - * Find an entry in the tree that intersects the region passed in. - * Note that this will find straddled intervals, it is up to the - * callers to enforce any boundary conditions. - * - * Callers must hold ip_lock. This lookup is not guaranteed to return - * a tree_depth 0 match, and as such can race inserts if the lock - * were not held. + * Return the index of the extent record which contains cluster #v_cluster. + * -1 is returned if it was not found. * - * The rb_node garbage lets insertion share the search. Trivial - * callers pass NULL. + * Should work fine on interior and exterior nodes. */ -static struct ocfs2_extent_map_entry * -ocfs2_extent_map_lookup(struct ocfs2_extent_map *em, - u32 cpos, u32 clusters, - struct rb_node ***ret_p, - struct rb_node **ret_parent) +static int ocfs2_search_extent_list(struct ocfs2_extent_list *el, + u32 v_cluster) { - struct rb_node **p = &em->em_extents.rb_node; - struct rb_node *parent = NULL; - struct ocfs2_extent_map_entry *ent = NULL; - - while (*p) - { - parent = *p; - ent = rb_entry(parent, struct ocfs2_extent_map_entry, - e_node); - if ((cpos + clusters) <= le32_to_cpu(ent->e_rec.e_cpos)) { - p = &(*p)->rb_left; - ent = NULL; - } else if (cpos >= (le32_to_cpu(ent->e_rec.e_cpos) + - le32_to_cpu(ent->e_rec.e_clusters))) { - p = &(*p)->rb_right; - ent = NULL; - } else - break; - } - - if (ret_p != NULL) - *ret_p = p; - if (ret_parent != NULL) - *ret_parent = parent; - return ent; -} - -/* - * Find the leaf containing the interval we want. While we're on our - * way down the tree, fill in every record we see at any depth, because - * we might want it later. - * - * Note that this code is run without ip_lock. That's because it - * sleeps while reading. If someone is also filling the extent list at - * the same time we are, we might have to restart. - */ -static int ocfs2_extent_map_find_leaf(struct inode *inode, - u32 cpos, u32 clusters, - struct ocfs2_extent_list *el) -{ - int i, ret; - struct buffer_head *eb_bh = NULL; - u64 blkno; - u32 rec_end; - struct ocfs2_extent_block *eb; + int ret = -1; + int i; struct ocfs2_extent_rec *rec; + u32 rec_end, rec_start; - /* - * The bh data containing the el cannot change here, because - * we hold alloc_sem. So we can do this without other - * locks. - */ - while (el->l_tree_depth) - { - blkno = 0; - for (i = 0; i < le16_to_cpu(el->l_next_free_rec); i++) { - rec = &el->l_recs[i]; - rec_end = (le32_to_cpu(rec->e_cpos) + - le32_to_cpu(rec->e_clusters)); - - ret = -EBADR; - if (rec_end > OCFS2_I(inode)->ip_clusters) { - mlog_errno(ret); - ocfs2_error(inode->i_sb, - "Extent %d at e_blkno %llu of inode %llu goes past ip_clusters of %u\n", - i, - (unsigned long long)le64_to_cpu(rec->e_blkno), - (unsigned long long)OCFS2_I(inode)->ip_blkno, - OCFS2_I(inode)->ip_clusters); - goto out_free; - } - - if (rec_end <= cpos) { - ret = ocfs2_extent_map_insert(inode, rec, - le16_to_cpu(el->l_tree_depth)); - if (ret && (ret != -EEXIST)) { - mlog_errno(ret); - goto out_free; - } - continue; - } - if ((cpos + clusters) <= le32_to_cpu(rec->e_cpos)) { - ret = ocfs2_extent_map_insert(inode, rec, - le16_to_cpu(el->l_tree_depth)); - if (ret && (ret != -EEXIST)) { - mlog_errno(ret); - goto out_free; - } - continue; - } - - /* - * We've found a record that matches our - * interval. We don't insert it because we're - * about to traverse it. - */ - - /* Check to see if we're stradling */ - ret = -ESRCH; - if (!ocfs2_extent_rec_contains_clusters(rec, - cpos, - clusters)) { - mlog_errno(ret); - goto out_free; - } - - /* - * If we've already found a record, the el has - * two records covering the same interval. - * EEEK! - */ - ret = -EBADR; - if (blkno) { - mlog_errno(ret); - ocfs2_error(inode->i_sb, - "Multiple extents for (cpos = %u, clusters = %u) on inode %llu; e_blkno %llu and rec %d at e_blkno %llu\n", - cpos, clusters, - (unsigned long long)OCFS2_I(inode)->ip_blkno, - (unsigned long long)blkno, i, - (unsigned long long)le64_to_cpu(rec->e_blkno)); - goto out_free; - } - - blkno = le64_to_cpu(rec->e_blkno); - } - - /* - * We don't support holes, and we're still up - * in the branches, so we'd better have found someone - */ - ret = -EBADR; - if (!blkno) { - ocfs2_error(inode->i_sb, - "No record found for (cpos = %u, clusters = %u) on inode %llu\n", - cpos, clusters, - (unsigned long long)OCFS2_I(inode)->ip_blkno); - mlog_errno(ret); - goto out_free; - } - - if (eb_bh) { - brelse(eb_bh); - eb_bh = NULL; - } - ret = ocfs2_read_block(OCFS2_SB(inode->i_sb), - blkno, &eb_bh, OCFS2_BH_CACHED, - inode); - if (ret) { - mlog_errno(ret); - goto out_free; - } - eb = (struct ocfs2_extent_block *)eb_bh->b_data; - if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb)) { - OCFS2_RO_ON_INVALID_EXTENT_BLOCK(inode->i_sb, eb); - ret = -EIO; - goto out_free; - } - el = &eb->h_list; - } - - BUG_ON(el->l_tree_depth); - - for (i = 0; i < le16_to_cpu(el->l_next_free_rec); i++) { + for(i = 0; i < le16_to_cpu(el->l_next_free_rec); i++) { rec = &el->l_recs[i]; - if ((le32_to_cpu(rec->e_cpos) + le32_to_cpu(rec->e_clusters)) > - OCFS2_I(inode)->ip_clusters) { - ret = -EBADR; - mlog_errno(ret); - ocfs2_error(inode->i_sb, - "Extent %d at e_blkno %llu of inode %llu goes past ip_clusters of %u\n", - i, - (unsigned long long)le64_to_cpu(rec->e_blkno), - (unsigned long long)OCFS2_I(inode)->ip_blkno, - OCFS2_I(inode)->ip_clusters); - return ret; - } + rec_start = le32_to_cpu(rec->e_cpos); + rec_end = rec_start + le32_to_cpu(rec->e_clusters); - ret = ocfs2_extent_map_insert(inode, rec, - le16_to_cpu(el->l_tree_depth)); - if (ret && (ret != -EEXIST)) { - mlog_errno(ret); - goto out_free; + if (v_cluster >= rec_start && v_cluster < rec_end) { + ret = i; + break; } } - ret = 0; - -out_free: - if (eb_bh) - brelse(eb_bh); - return ret; } -/* - * This lookup actually will read from disk. It has one invariant: - * It will never re-traverse blocks. This means that all inserts should - * be new regions or more granular regions (both allowed by insert). - */ -static int ocfs2_extent_map_lookup_read(struct inode *inode, - u32 cpos, - u32 clusters, - struct ocfs2_extent_map_entry **ret_ent) +static int ocfs2_get_clusters(struct inode *inode, u32 v_cluster, + u32 *p_cluster, u32 *num_clusters) { - int ret; - u64 blkno; - struct ocfs2_extent_map *em = &OCFS2_I(inode)->ip_map; - struct ocfs2_extent_map_entry *ent; - struct buffer_head *bh = NULL; - struct ocfs2_extent_block *eb; + int ret, i; + struct buffer_head *di_bh = NULL; + struct buffer_head *eb_bh = NULL; struct ocfs2_dinode *di; + struct ocfs2_extent_block *eb; struct ocfs2_extent_list *el; + struct ocfs2_extent_rec *rec; + u32 coff; - spin_lock(&OCFS2_I(inode)->ip_lock); - ent = ocfs2_extent_map_lookup(em, cpos, clusters, NULL, NULL); - if (ent) { - if (!ent->e_tree_depth) { - spin_unlock(&OCFS2_I(inode)->ip_lock); - *ret_ent = ent; - return 0; - } - blkno = le64_to_cpu(ent->e_rec.e_blkno); - spin_unlock(&OCFS2_I(inode)->ip_lock); - - ret = ocfs2_read_block(OCFS2_SB(inode->i_sb), blkno, &bh, - OCFS2_BH_CACHED, inode); - if (ret) { - mlog_errno(ret); - if (bh) - brelse(bh); - return ret; - } - eb = (struct ocfs2_extent_block *)bh->b_data; - if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb)) { - OCFS2_RO_ON_INVALID_EXTENT_BLOCK(inode->i_sb, eb); - brelse(bh); - return -EIO; - } - el = &eb->h_list; - } else { - spin_unlock(&OCFS2_I(inode)->ip_lock); - - ret = ocfs2_read_block(OCFS2_SB(inode->i_sb), - OCFS2_I(inode)->ip_blkno, &bh, - OCFS2_BH_CACHED, inode); - if (ret) { - mlog_errno(ret); - if (bh) - brelse(bh); - return ret; - } - di = (struct ocfs2_dinode *)bh->b_data; - if (!OCFS2_IS_VALID_DINODE(di)) { - brelse(bh); - OCFS2_RO_ON_INVALID_DINODE(inode->i_sb, di); - return -EIO; - } - el = &di->id2.i_list; - } - - ret = ocfs2_extent_map_find_leaf(inode, cpos, clusters, el); - brelse(bh); + ret = ocfs2_read_block(OCFS2_SB(inode->i_sb), OCFS2_I(inode)->ip_blkno, + &di_bh, OCFS2_BH_CACHED, inode); if (ret) { mlog_errno(ret); - return ret; + goto out; } - ent = ocfs2_extent_map_lookup(em, cpos, clusters, NULL, NULL); - if (!ent) { - ret = -ESRCH; - mlog_errno(ret); - return ret; - } - - /* FIXME: Make sure this isn't a corruption */ - BUG_ON(ent->e_tree_depth); + di = (struct ocfs2_dinode *) di_bh->b_data; + el = &di->id2.i_list; - *ret_ent = ent; - - return 0; -} - -/* - * Callers must hold ip_lock. This can insert pieces of the tree, - * thus racing lookup if the lock weren't held. - */ -static int ocfs2_extent_map_insert_entry(struct ocfs2_extent_map *em, - struct ocfs2_extent_map_entry *ent) -{ - struct rb_node **p, *parent; - struct ocfs2_extent_map_entry *old_ent; - - old_ent = ocfs2_extent_map_lookup(em, le32_to_cpu(ent->e_rec.e_cpos), - le32_to_cpu(ent->e_rec.e_clusters), - &p, &parent); - if (old_ent) - return -EEXIST; - - rb_link_node(&ent->e_node, parent, p); - rb_insert_color(&ent->e_node, &em->em_extents); - - return 0; -} - - -/* - * Simple rule: on any return code other than -EAGAIN, anything left - * in the insert_context will be freed. - * - * Simple rule #2: A return code of -EEXIST from this function or - * its calls to ocfs2_extent_map_insert_entry() signifies that another - * thread beat us to the insert. It is not an actual error, but it - * tells the caller we have no more work to do. - */ -static int ocfs2_extent_map_try_insert(struct inode *inode, - struct ocfs2_extent_rec *rec, - int tree_depth, - struct ocfs2_em_insert_context *ctxt) -{ - int ret; - struct ocfs2_extent_map *em = &OCFS2_I(inode)->ip_map; - struct ocfs2_extent_map_entry *old_ent; - - ctxt->need_left = 0; - ctxt->need_right = 0; - ctxt->old_ent = NULL; - - spin_lock(&OCFS2_I(inode)->ip_lock); - ret = ocfs2_extent_map_insert_entry(em, ctxt->new_ent); - if (!ret) { - ctxt->new_ent = NULL; - goto out_unlock; - } - - /* Since insert_entry failed, the map MUST have old_ent */ - old_ent = ocfs2_extent_map_lookup(em, le32_to_cpu(rec->e_cpos), - le32_to_cpu(rec->e_clusters), - NULL, NULL); - - BUG_ON(!old_ent); + if (el->l_tree_depth) { + ret = ocfs2_find_leaf(inode, el, v_cluster, &eb_bh); + if (ret) { + mlog_errno(ret); + goto out; + } - if (old_ent->e_tree_depth < tree_depth) { - /* Another thread beat us to the lower tree_depth */ - ret = -EEXIST; - goto out_unlock; + eb = (struct ocfs2_extent_block *) eb_bh->b_data; + el = &eb->h_list; } - if (old_ent->e_tree_depth == tree_depth) { + i = ocfs2_search_extent_list(el, v_cluster); + if (i == -1) { /* - * Another thread beat us to this tree_depth. - * Let's make sure we agree with that thread (the - * extent_rec should be identical). + * A hole was found. Return some canned values that + * callers can key on. */ - if (!memcmp(rec, &old_ent->e_rec, - sizeof(struct ocfs2_extent_rec))) - ret = 0; - else - /* FIXME: Should this be ESRCH/EBADR??? */ - ret = -EEXIST; + *p_cluster = 0; + if (num_clusters) + *num_clusters = 1; + } else { + rec = &el->l_recs[i]; - goto out_unlock; - } + BUG_ON(v_cluster < le32_to_cpu(rec->e_cpos)); - /* - * We do it in this order specifically so that no actual tree - * changes occur until we have all the pieces we need. We - * don't want malloc failures to leave an inconsistent tree. - * Whenever we drop the lock, another process could be - * inserting. Also note that, if another process just beat us - * to an insert, we might not need the same pieces we needed - * the first go round. In the end, the pieces we need will - * be used, and the pieces we don't will be freed. - */ - ctxt->need_left = !!(le32_to_cpu(rec->e_cpos) > - le32_to_cpu(old_ent->e_rec.e_cpos)); - ctxt->need_right = !!((le32_to_cpu(old_ent->e_rec.e_cpos) + - le32_to_cpu(old_ent->e_rec.e_clusters)) > - (le32_to_cpu(rec->e_cpos) + le32_to_cpu(rec->e_clusters))); - ret = -EAGAIN; - if (ctxt->need_left) { - if (!ctxt->left_ent) - goto out_unlock; - *(ctxt->left_ent) = *old_ent; - ctxt->left_ent->e_rec.e_clusters = - cpu_to_le32(le32_to_cpu(rec->e_cpos) - - le32_to_cpu(ctxt->left_ent->e_rec.e_cpos)); - } - if (ctxt->need_right) { - if (!ctxt->right_ent) - goto out_unlock; - *(ctxt->right_ent) = *old_ent; - ctxt->right_ent->e_rec.e_cpos = - cpu_to_le32(le32_to_cpu(rec->e_cpos) + + if (!rec->e_blkno) { + ocfs2_error(inode->i_sb, "Inode %lu has bad extent " + "record (%u, %u, 0)", inode->i_ino, + le32_to_cpu(rec->e_cpos), le32_to_cpu(rec->e_clusters)); - ctxt->right_ent->e_rec.e_clusters = - cpu_to_le32((le32_to_cpu(old_ent->e_rec.e_cpos) + - le32_to_cpu(old_ent->e_rec.e_clusters)) - - le32_to_cpu(ctxt->right_ent->e_rec.e_cpos)); - } - - rb_erase(&old_ent->e_node, &em->em_extents); - /* Now that he's erased, set him up for deletion */ - ctxt->old_ent = old_ent; - - if (ctxt->need_left) { - ret = ocfs2_extent_map_insert_entry(em, - ctxt->left_ent); - if (ret) - goto out_unlock; - ctxt->left_ent = NULL; - } - - if (ctxt->need_right) { - ret = ocfs2_extent_map_insert_entry(em, - ctxt->right_ent); - if (ret) - goto out_unlock; - ctxt->right_ent = NULL; - } - - ret = ocfs2_extent_map_insert_entry(em, ctxt->new_ent); - - if (!ret) - ctxt->new_ent = NULL; - -out_unlock: - spin_unlock(&OCFS2_I(inode)->ip_lock); - - return ret; -} - - -static int ocfs2_extent_map_insert(struct inode *inode, - struct ocfs2_extent_rec *rec, - int tree_depth) -{ - int ret; - struct ocfs2_em_insert_context ctxt = {0, }; - - if ((le32_to_cpu(rec->e_cpos) + le32_to_cpu(rec->e_clusters)) > - OCFS2_I(inode)->ip_map.em_clusters) { - ret = -EBADR; - mlog_errno(ret); - return ret; - } - - /* Zero e_clusters means a truncated tail record. It better be EOF */ - if (!rec->e_clusters) { - if ((le32_to_cpu(rec->e_cpos) + le32_to_cpu(rec->e_clusters)) != - OCFS2_I(inode)->ip_map.em_clusters) { - ret = -EBADR; - mlog_errno(ret); - ocfs2_error(inode->i_sb, - "Zero e_clusters on non-tail extent record at e_blkno %llu on inode %llu\n", - (unsigned long long)le64_to_cpu(rec->e_blkno), - (unsigned long long)OCFS2_I(inode)->ip_blkno); - return ret; - } - - /* Ignore the truncated tail */ - return 0; - } - - ret = -ENOMEM; - ctxt.new_ent = kmem_cache_alloc(ocfs2_em_ent_cachep, - GFP_NOFS); - if (!ctxt.new_ent) { - mlog_errno(ret); - return ret; - } - - ctxt.new_ent->e_rec = *rec; - ctxt.new_ent->e_tree_depth = tree_depth; - - do { - ret = -ENOMEM; - if (ctxt.need_left && !ctxt.left_ent) { - ctxt.left_ent = - kmem_cache_alloc(ocfs2_em_ent_cachep, - GFP_NOFS); - if (!ctxt.left_ent) - break; - } - if (ctxt.need_right && !ctxt.right_ent) { - ctxt.right_ent = - kmem_cache_alloc(ocfs2_em_ent_cachep, - GFP_NOFS); - if (!ctxt.right_ent) - break; + ret = -EROFS; + goto out; } - ret = ocfs2_extent_map_try_insert(inode, rec, - tree_depth, &ctxt); - } while (ret == -EAGAIN); + coff = v_cluster - le32_to_cpu(rec->e_cpos); - if ((ret < 0) && (ret != -EEXIST)) - mlog_errno(ret); - - if (ctxt.left_ent) - kmem_cache_free(ocfs2_em_ent_cachep, ctxt.left_ent); - if (ctxt.right_ent) - kmem_cache_free(ocfs2_em_ent_cachep, ctxt.right_ent); - if (ctxt.old_ent) - kmem_cache_free(ocfs2_em_ent_cachep, ctxt.old_ent); - if (ctxt.new_ent) - kmem_cache_free(ocfs2_em_ent_cachep, ctxt.new_ent); - - return ret; -} + *p_cluster = ocfs2_blocks_to_clusters(inode->i_sb, + le64_to_cpu(rec->e_blkno)); + *p_cluster = *p_cluster + coff; -/* - * Append this record to the tail of the extent map. It must be - * tree_depth 0. The record might be an extension of an existing - * record, and as such that needs to be handled. eg: - * - * Existing record in the extent map: - * - * cpos = 10, len = 10 - * |---------| - * - * New Record: - * - * cpos = 10, len = 20 - * |------------------| - * - * The passed record is the new on-disk record. The new_clusters value - * is how many clusters were added to the file. If the append is a - * contiguous append, the new_clusters has been added to - * rec->e_clusters. If the append is an entirely new extent, then - * rec->e_clusters is == new_clusters. - */ -int ocfs2_extent_map_append(struct inode *inode, - struct ocfs2_extent_rec *rec, - u32 new_clusters) -{ - int ret; - struct ocfs2_extent_map *em = &OCFS2_I(inode)->ip_map; - struct ocfs2_extent_map_entry *ent; - struct ocfs2_extent_rec *old; - - BUG_ON(!new_clusters); - BUG_ON(le32_to_cpu(rec->e_clusters) < new_clusters); - - if (em->em_clusters < OCFS2_I(inode)->ip_clusters) { - /* - * Size changed underneath us on disk. Drop any - * straddling records and update our idea of - * i_clusters - */ - ocfs2_extent_map_drop(inode, em->em_clusters - 1); - em->em_clusters = OCFS2_I(inode)->ip_clusters; + if (num_clusters) + *num_clusters = le32_to_cpu(rec->e_clusters) - coff; } - mlog_bug_on_msg((le32_to_cpu(rec->e_cpos) + - le32_to_cpu(rec->e_clusters)) != - (em->em_clusters + new_clusters), - "Inode %llu:\n" - "rec->e_cpos = %u + rec->e_clusters = %u = %u\n" - "em->em_clusters = %u + new_clusters = %u = %u\n", - (unsigned long long)OCFS2_I(inode)->ip_blkno, - le32_to_cpu(rec->e_cpos), le32_to_cpu(rec->e_clusters), - le32_to_cpu(rec->e_cpos) + le32_to_cpu(rec->e_clusters), - em->em_clusters, new_clusters, - em->em_clusters + new_clusters); - - em->em_clusters += new_clusters; - - ret = -ENOENT; - if (le32_to_cpu(rec->e_clusters) > new_clusters) { - /* This is a contiguous append */ - ent = ocfs2_extent_map_lookup(em, le32_to_cpu(rec->e_cpos), 1, - NULL, NULL); - if (ent) { - old = &ent->e_rec; - BUG_ON((le32_to_cpu(rec->e_cpos) + - le32_to_cpu(rec->e_clusters)) != - (le32_to_cpu(old->e_cpos) + - le32_to_cpu(old->e_clusters) + - new_clusters)); - if (ent->e_tree_depth == 0) { - BUG_ON(le32_to_cpu(old->e_cpos) != - le32_to_cpu(rec->e_cpos)); - BUG_ON(le64_to_cpu(old->e_blkno) != - le64_to_cpu(rec->e_blkno)); - ret = 0; - } - /* - * Let non-leafs fall through as -ENOENT to - * force insertion of the new leaf. - */ - le32_add_cpu(&old->e_clusters, new_clusters); - } - } - - if (ret == -ENOENT) - ret = ocfs2_extent_map_insert(inode, rec, 0); - if (ret < 0) - mlog_errno(ret); +out: + brelse(di_bh); + brelse(eb_bh); return ret; } -#if 0 -/* Code here is included but defined out as it completes the extent - * map api and may be used in the future. */ - /* - * Look up the record containing this cluster offset. This record is - * part of the extent map. Do not free it. Any changes you make to - * it will reflect in the extent map. So, if your last extent - * is (cpos = 10, clusters = 10) and you truncate the file by 5 - * clusters, you can do: - * - * ret = ocfs2_extent_map_get_rec(em, orig_size - 5, &rec); - * rec->e_clusters -= 5; - * - * The lookup does not read from disk. If the map isn't filled in for - * an entry, you won't find it. - * - * Also note that the returned record is valid until alloc_sem is - * dropped. After that, truncate and extend can happen. Caveat Emptor. + * This expects alloc_sem to be held. The allocation cannot change at + * all while the map is in the process of being updated. */ -int ocfs2_extent_map_get_rec(struct inode *inode, u32 cpos, - struct ocfs2_extent_rec **rec, - int *tree_depth) -{ - int ret = -ENOENT; - struct ocfs2_extent_map *em = &OCFS2_I(inode)->ip_map; - struct ocfs2_extent_map_entry *ent; - - *rec = NULL; - - if (cpos >= OCFS2_I(inode)->ip_clusters) - return -EINVAL; - - if (cpos >= em->em_clusters) { - /* - * Size changed underneath us on disk. Drop any - * straddling records and update our idea of - * i_clusters - */ - ocfs2_extent_map_drop(inode, em->em_clusters - 1); - em->em_clusters = OCFS2_I(inode)->ip_clusters ; - } - - ent = ocfs2_extent_map_lookup(&OCFS2_I(inode)->ip_map, cpos, 1, - NULL, NULL); - - if (ent) { - *rec = &ent->e_rec; - if (tree_depth) - *tree_depth = ent->e_tree_depth; - ret = 0; - } - - return ret; -} - -int ocfs2_extent_map_get_clusters(struct inode *inode, - u32 v_cpos, int count, - u32 *p_cpos, int *ret_count) -{ - int ret; - u32 coff, ccount; - struct ocfs2_extent_map *em = &OCFS2_I(inode)->ip_map; - struct ocfs2_extent_map_entry *ent = NULL; - - *p_cpos = ccount = 0; - - if ((v_cpos + count) > OCFS2_I(inode)->ip_clusters) - return -EINVAL; - - if ((v_cpos + count) > em->em_clusters) { - /* - * Size changed underneath us on disk. Drop any - * straddling records and update our idea of - * i_clusters - */ - ocfs2_extent_map_drop(inode, em->em_clusters - 1); - em->em_clusters = OCFS2_I(inode)->ip_clusters; - } - - - ret = ocfs2_extent_map_lookup_read(inode, v_cpos, count, &ent); - if (ret) - return ret; - - if (ent) { - /* We should never find ourselves straddling an interval */ - if (!ocfs2_extent_rec_contains_clusters(&ent->e_rec, - v_cpos, - count)) - return -ESRCH; - - coff = v_cpos - le32_to_cpu(ent->e_rec.e_cpos); - *p_cpos = ocfs2_blocks_to_clusters(inode->i_sb, - le64_to_cpu(ent->e_rec.e_blkno)) + - coff; - - if (ret_count) - *ret_count = le32_to_cpu(ent->e_rec.e_clusters) - coff; - - return 0; - } - - - return -ENOENT; -} - -#endif /* 0 */ - -int ocfs2_extent_map_get_blocks(struct inode *inode, - u64 v_blkno, int count, - u64 *p_blkno, int *ret_count) +int ocfs2_extent_map_get_blocks(struct inode *inode, u64 v_blkno, u64 *p_blkno, + int *ret_count) { int ret; - u64 boff; - u32 cpos, clusters; int bpc = ocfs2_clusters_to_blocks(inode->i_sb, 1); - struct ocfs2_extent_map_entry *ent = NULL; - struct ocfs2_extent_map *em = &OCFS2_I(inode)->ip_map; - struct ocfs2_extent_rec *rec; - - *p_blkno = 0; + u32 cpos, num_clusters, p_cluster; + u64 boff = 0; cpos = ocfs2_blocks_to_clusters(inode->i_sb, v_blkno); - clusters = ocfs2_blocks_to_clusters(inode->i_sb, - (u64)count + bpc - 1); - if ((cpos + clusters) > OCFS2_I(inode)->ip_clusters) { - ret = -EINVAL; - mlog_errno(ret); - return ret; - } - if ((cpos + clusters) > em->em_clusters) { - /* - * Size changed underneath us on disk. Drop any - * straddling records and update our idea of - * i_clusters - */ - ocfs2_extent_map_drop(inode, em->em_clusters - 1); - em->em_clusters = OCFS2_I(inode)->ip_clusters; - } - - ret = ocfs2_extent_map_lookup_read(inode, cpos, clusters, &ent); + ret = ocfs2_get_clusters(inode, cpos, &p_cluster, &num_clusters); if (ret) { mlog_errno(ret); - return ret; + goto out; } - if (ent) - { - rec = &ent->e_rec; - - /* We should never find ourselves straddling an interval */ - if (!ocfs2_extent_rec_contains_clusters(rec, cpos, clusters)) { - ret = -ESRCH; - mlog_errno(ret); - return ret; - } - - boff = ocfs2_clusters_to_blocks(inode->i_sb, cpos - - le32_to_cpu(rec->e_cpos)); + /* + * p_cluster == 0 indicates a hole. + */ + if (p_cluster) { + boff = ocfs2_clusters_to_blocks(inode->i_sb, p_cluster); boff += (v_blkno & (u64)(bpc - 1)); - *p_blkno = le64_to_cpu(rec->e_blkno) + boff; - - if (ret_count) { - *ret_count = ocfs2_clusters_to_blocks(inode->i_sb, - le32_to_cpu(rec->e_clusters)) - boff; - } - - return 0; } - return -ENOENT; -} - -int ocfs2_extent_map_init(struct inode *inode) -{ - struct ocfs2_extent_map *em = &OCFS2_I(inode)->ip_map; + *p_blkno = boff; - em->em_extents = RB_ROOT; - em->em_clusters = 0; - - return 0; -} - -/* Needs the lock */ -static void __ocfs2_extent_map_drop(struct inode *inode, - u32 new_clusters, - struct rb_node **free_head, - struct ocfs2_extent_map_entry **tail_ent) -{ - struct rb_node *node, *next; - struct ocfs2_extent_map *em = &OCFS2_I(inode)->ip_map; - struct ocfs2_extent_map_entry *ent; - - *free_head = NULL; - - ent = NULL; - node = rb_last(&em->em_extents); - while (node) - { - next = rb_prev(node); - - ent = rb_entry(node, struct ocfs2_extent_map_entry, - e_node); - if (le32_to_cpu(ent->e_rec.e_cpos) < new_clusters) - break; - - rb_erase(&ent->e_node, &em->em_extents); - - node->rb_right = *free_head; - *free_head = node; - - ent = NULL; - node = next; - } - - /* Do we have an entry straddling new_clusters? */ - if (tail_ent) { - if (ent && - ((le32_to_cpu(ent->e_rec.e_cpos) + - le32_to_cpu(ent->e_rec.e_clusters)) > new_clusters)) - *tail_ent = ent; - else - *tail_ent = NULL; + if (ret_count) { + *ret_count = ocfs2_clusters_to_blocks(inode->i_sb, num_clusters); + *ret_count -= v_blkno & (u64)(bpc - 1); } -} - -static void __ocfs2_extent_map_drop_cleanup(struct rb_node *free_head) -{ - struct rb_node *node; - struct ocfs2_extent_map_entry *ent; - - while (free_head) { - node = free_head; - free_head = node->rb_right; - ent = rb_entry(node, struct ocfs2_extent_map_entry, - e_node); - kmem_cache_free(ocfs2_em_ent_cachep, ent); - } -} - -/* - * Remove all entries past new_clusters, inclusive of an entry that - * contains new_clusters. This is effectively a cache forget. - * - * If you want to also clip the last extent by some number of clusters, - * you need to call ocfs2_extent_map_trunc(). - * This code does not check or modify ip_clusters. - */ -int ocfs2_extent_map_drop(struct inode *inode, u32 new_clusters) -{ - struct rb_node *free_head = NULL; - struct ocfs2_extent_map *em = &OCFS2_I(inode)->ip_map; - struct ocfs2_extent_map_entry *ent; - - spin_lock(&OCFS2_I(inode)->ip_lock); - - __ocfs2_extent_map_drop(inode, new_clusters, &free_head, &ent); - - if (ent) { - rb_erase(&ent->e_node, &em->em_extents); - ent->e_node.rb_right = free_head; - free_head = &ent->e_node; - } - - spin_unlock(&OCFS2_I(inode)->ip_lock); - - if (free_head) - __ocfs2_extent_map_drop_cleanup(free_head); - - return 0; -} - -/* - * Remove all entries past new_clusters and also clip any extent - * straddling new_clusters, if there is one. This does not check - * or modify ip_clusters - */ -int ocfs2_extent_map_trunc(struct inode *inode, u32 new_clusters) -{ - struct rb_node *free_head = NULL; - struct ocfs2_extent_map_entry *ent = NULL; - - spin_lock(&OCFS2_I(inode)->ip_lock); - - __ocfs2_extent_map_drop(inode, new_clusters, &free_head, &ent); - - if (ent) - ent->e_rec.e_clusters = cpu_to_le32(new_clusters - - le32_to_cpu(ent->e_rec.e_cpos)); - - OCFS2_I(inode)->ip_map.em_clusters = new_clusters; - - spin_unlock(&OCFS2_I(inode)->ip_lock); - - if (free_head) - __ocfs2_extent_map_drop_cleanup(free_head); - - return 0; -} - -int __init init_ocfs2_extent_maps(void) -{ - ocfs2_em_ent_cachep = - kmem_cache_create("ocfs2_em_ent", - sizeof(struct ocfs2_extent_map_entry), - 0, SLAB_HWCACHE_ALIGN, NULL, NULL); - if (!ocfs2_em_ent_cachep) - return -ENOMEM; - - return 0; -} - -void exit_ocfs2_extent_maps(void) -{ - kmem_cache_destroy(ocfs2_em_ent_cachep); +out: + return ret; } diff --git a/fs/ocfs2/extent_map.h b/fs/ocfs2/extent_map.h index fa3745efa886..036e23251448 100644 --- a/fs/ocfs2/extent_map.h +++ b/fs/ocfs2/extent_map.h @@ -25,22 +25,7 @@ #ifndef _EXTENT_MAP_H #define _EXTENT_MAP_H -int init_ocfs2_extent_maps(void); -void exit_ocfs2_extent_maps(void); - -/* - * EVERY CALL here except _init, _trunc, and _drop expects alloc_sem - * to be held. The allocation cannot change at all while the map is - * in the process of being updated. - */ -int ocfs2_extent_map_init(struct inode *inode); -int ocfs2_extent_map_append(struct inode *inode, - struct ocfs2_extent_rec *rec, - u32 new_clusters); -int ocfs2_extent_map_get_blocks(struct inode *inode, - u64 v_blkno, int count, - u64 *p_blkno, int *ret_count); -int ocfs2_extent_map_drop(struct inode *inode, u32 new_clusters); -int ocfs2_extent_map_trunc(struct inode *inode, u32 new_clusters); +int ocfs2_extent_map_get_blocks(struct inode *inode, u64 v_blkno, u64 *p_blkno, + int *ret_count); #endif /* _EXTENT_MAP_H */ diff --git a/fs/ocfs2/inode.c b/fs/ocfs2/inode.c index 08d57a3d4e83..5ff8549eb1a3 100644 --- a/fs/ocfs2/inode.c +++ b/fs/ocfs2/inode.c @@ -1003,9 +1003,6 @@ void ocfs2_clear_inode(struct inode *inode) "Clear inode of %llu, inode has io markers\n", (unsigned long long)oi->ip_blkno); - ocfs2_extent_map_drop(inode, 0); - ocfs2_extent_map_init(inode); - status = ocfs2_drop_inode_locks(inode); if (status < 0) mlog_errno(status); @@ -1102,8 +1099,7 @@ struct buffer_head *ocfs2_bread(struct inode *inode, return NULL; } - tmperr = ocfs2_extent_map_get_blocks(inode, block, 1, - &p_blkno, NULL); + tmperr = ocfs2_extent_map_get_blocks(inode, block, &p_blkno, NULL); if (tmperr < 0) { mlog_errno(tmperr); goto fail; diff --git a/fs/ocfs2/inode.h b/fs/ocfs2/inode.h index 042ae20a7132..a9ced009cb9c 100644 --- a/fs/ocfs2/inode.h +++ b/fs/ocfs2/inode.h @@ -43,7 +43,6 @@ struct ocfs2_inode_info spinlock_t ip_lock; u32 ip_open_count; u32 ip_clusters; - struct ocfs2_extent_map ip_map; struct list_head ip_io_markers; struct mutex ip_io_mutex; diff --git a/fs/ocfs2/journal.c b/fs/ocfs2/journal.c index 12445a31f733..2e2e04fe9738 100644 --- a/fs/ocfs2/journal.c +++ b/fs/ocfs2/journal.c @@ -670,8 +670,7 @@ static int ocfs2_force_read_journal(struct inode *inode) (inode->i_blocks >> (inode->i_sb->s_blocksize_bits - 9))) { status = ocfs2_extent_map_get_blocks(inode, v_blkno, - 1, &p_blkno, - &p_blocks); + &p_blkno, &p_blocks); if (status < 0) { mlog_errno(status); goto bail; diff --git a/fs/ocfs2/namei.c b/fs/ocfs2/namei.c index d65fef4a8bd8..5755e0748256 100644 --- a/fs/ocfs2/namei.c +++ b/fs/ocfs2/namei.c @@ -1511,8 +1511,7 @@ static int ocfs2_create_symlink_data(struct ocfs2_super *osb, goto bail; } - status = ocfs2_extent_map_get_blocks(inode, 0, 1, &p_blkno, - &p_blocks); + status = ocfs2_extent_map_get_blocks(inode, 0, &p_blkno, &p_blocks); if (status < 0) { mlog_errno(status); goto bail; diff --git a/fs/ocfs2/ocfs2.h b/fs/ocfs2/ocfs2.h index fe7e1ecafca5..faeb53f2eecf 100644 --- a/fs/ocfs2/ocfs2.h +++ b/fs/ocfs2/ocfs2.h @@ -46,11 +46,6 @@ #include "endian.h" #include "ocfs2_lockid.h" -struct ocfs2_extent_map { - u32 em_clusters; - struct rb_root em_extents; -}; - /* Most user visible OCFS2 inodes will have very few pieces of * metadata, but larger files (including bitmaps, etc) must be taken * into account when designing an access scheme. We allow a small diff --git a/fs/ocfs2/slot_map.c b/fs/ocfs2/slot_map.c index 2d3ac32cb74e..f4416e7330e1 100644 --- a/fs/ocfs2/slot_map.c +++ b/fs/ocfs2/slot_map.c @@ -197,7 +197,7 @@ int ocfs2_init_slot_info(struct ocfs2_super *osb) goto bail; } - status = ocfs2_extent_map_get_blocks(inode, 0ULL, 1, &blkno, NULL); + status = ocfs2_extent_map_get_blocks(inode, 0ULL, &blkno, NULL); if (status < 0) { mlog_errno(status); goto bail; diff --git a/fs/ocfs2/super.c b/fs/ocfs2/super.c index 16564ea6c141..6ab52351943a 100644 --- a/fs/ocfs2/super.c +++ b/fs/ocfs2/super.c @@ -806,9 +806,6 @@ static int __init ocfs2_init(void) ocfs2_print_version(); - if (init_ocfs2_extent_maps()) - return -ENOMEM; - status = init_ocfs2_uptodate_cache(); if (status < 0) { mlog_errno(status); @@ -837,7 +834,6 @@ leave: if (status < 0) { ocfs2_free_mem_caches(); exit_ocfs2_uptodate_cache(); - exit_ocfs2_extent_maps(); } mlog_exit(status); @@ -863,8 +859,6 @@ static void __exit ocfs2_exit(void) unregister_filesystem(&ocfs2_fs_type); - exit_ocfs2_extent_maps(); - exit_ocfs2_uptodate_cache(); mlog_exit_void(); @@ -948,7 +942,6 @@ static void ocfs2_inode_init_once(void *data, oi->ip_flags = 0; oi->ip_open_count = 0; spin_lock_init(&oi->ip_lock); - ocfs2_extent_map_init(&oi->vfs_inode); INIT_LIST_HEAD(&oi->ip_io_markers); oi->ip_created_trans = 0; oi->ip_last_trans = 0; -- cgit From 3a0782d09c07aa3ec767ba6089cd15cfbfbfc508 Mon Sep 17 00:00:00 2001 From: Mark Fasheh Date: Wed, 17 Jan 2007 12:53:31 -0800 Subject: ocfs2: teach extend/truncate about sparse files For ocfs2_truncate_file(), we eliminate the "simple" truncate case which no longer exists since i_size is not tied to i_clusters. In ocfs2_extend_file(), we skip the allocation / page zeroing code for file systems which understand sparse files. The core truncate code is changed to do a bottom up tree traversal. This gets abstracted out into it's own function. To make things more readable, most of the special case handling for in-inode extents from ocfs2_do_truncate() is also removed. Though write support for sparse files comes in a later patch, we at least update ocfs2_prepare_inode_for_write() to skip allocation for sparse files. Signed-off-by: Mark Fasheh --- fs/ocfs2/alloc.c | 480 +++++++++++++++++++++++++++++++++---------------------- fs/ocfs2/file.c | 31 ++-- fs/ocfs2/inode.c | 46 ++---- 3 files changed, 320 insertions(+), 237 deletions(-) (limited to 'fs/ocfs2/alloc.c') diff --git a/fs/ocfs2/alloc.c b/fs/ocfs2/alloc.c index 85a05f120249..9a40603c4d4b 100644 --- a/fs/ocfs2/alloc.c +++ b/fs/ocfs2/alloc.c @@ -2921,12 +2921,13 @@ int ocfs2_truncate_log_init(struct ocfs2_super *osb) * block will be so we can update his h_next_leaf_blk field, as well * as the dinodes i_last_eb_blk */ static int ocfs2_find_new_last_ext_blk(struct inode *inode, - u32 new_i_clusters, + unsigned int clusters_to_del, struct ocfs2_path *path, struct buffer_head **new_last_eb) { - int ret = 0; + int next_free, ret = 0; u32 cpos; + struct ocfs2_extent_rec *rec; struct ocfs2_extent_block *eb; struct ocfs2_extent_list *el; struct buffer_head *bh = NULL; @@ -2939,20 +2940,48 @@ static int ocfs2_find_new_last_ext_blk(struct inode *inode, /* trunc to zero special case - this makes tree_depth = 0 * regardless of what it is. */ - if (!new_i_clusters) + if (OCFS2_I(inode)->ip_clusters == clusters_to_del) goto out; el = path_leaf_el(path); BUG_ON(!el->l_next_free_rec); - /* Make sure that this guy will actually be empty after we - * clear away the data. */ + /* + * Make sure that this extent list will actually be empty + * after we clear away the data. We can shortcut out if + * there's more than one non-empty extent in the + * list. Otherwise, a check of the remaining extent is + * necessary. + */ + next_free = le16_to_cpu(el->l_next_free_rec); + rec = NULL; if (ocfs2_is_empty_extent(&el->l_recs[0])) { - if (le16_to_cpu(el->l_next_free_rec) > 1 && - le32_to_cpu(el->l_recs[1].e_cpos) < new_i_clusters) + if (next_free > 2) goto out; - } else if (le32_to_cpu(el->l_recs[0].e_cpos) < new_i_clusters) - goto out; + + /* We may have a valid extent in index 1, check it. */ + if (next_free == 2) + rec = &el->l_recs[1]; + + /* + * Fall through - no more nonempty extents, so we want + * to delete this leaf. + */ + } else { + if (next_free > 1) + goto out; + + rec = &el->l_recs[0]; + } + + if (rec) { + /* + * Check it we'll only be trimming off the end of this + * cluster. + */ + if (le16_to_cpu(rec->e_clusters) > clusters_to_del) + goto out; + } ret = ocfs2_find_cpos_for_left_leaf(inode->i_sb, path, &cpos); if (ret) { @@ -2984,6 +3013,223 @@ out: return ret; } +/* + * Trim some clusters off the rightmost edge of a tree. Only called + * during truncate. + * + * The caller needs to: + * - start journaling of each path component. + * - compute and fully set up any new last ext block + */ +static int ocfs2_trim_tree(struct inode *inode, struct ocfs2_path *path, + handle_t *handle, struct ocfs2_truncate_context *tc, + u32 clusters_to_del, u64 *delete_start) +{ + int ret, i, index = path->p_tree_depth; + u32 new_edge = 0; + u64 deleted_eb = 0; + struct buffer_head *bh; + struct ocfs2_extent_list *el; + struct ocfs2_extent_rec *rec; + + *delete_start = 0; + + while (index >= 0) { + bh = path->p_node[index].bh; + el = path->p_node[index].el; + + mlog(0, "traveling tree (index = %d, block = %llu)\n", + index, (unsigned long long)bh->b_blocknr); + + BUG_ON(le16_to_cpu(el->l_next_free_rec) == 0); + + if (index != + (path->p_tree_depth - le16_to_cpu(el->l_tree_depth))) { + ocfs2_error(inode->i_sb, + "Inode %lu has invalid ext. block %llu", + inode->i_ino, + (unsigned long long)bh->b_blocknr); + ret = -EROFS; + goto out; + } + +find_tail_record: + i = le16_to_cpu(el->l_next_free_rec) - 1; + rec = &el->l_recs[i]; + + mlog(0, "Extent list before: record %d: (%u, %u, %llu), " + "next = %u\n", i, le32_to_cpu(rec->e_cpos), + le32_to_cpu(rec->e_clusters), + (unsigned long long)le64_to_cpu(rec->e_blkno), + le16_to_cpu(el->l_next_free_rec)); + + BUG_ON(le32_to_cpu(rec->e_clusters) < clusters_to_del); + + if (le16_to_cpu(el->l_tree_depth) == 0) { + /* + * If the leaf block contains a single empty + * extent and no records, we can just remove + * the block. + */ + if (i == 0 && ocfs2_is_empty_extent(rec)) { + memset(rec, 0, + sizeof(struct ocfs2_extent_rec)); + el->l_next_free_rec = cpu_to_le16(0); + + goto delete; + } + + /* + * Remove any empty extents by shifting things + * left. That should make life much easier on + * the code below. This condition is rare + * enough that we shouldn't see a performance + * hit. + */ + if (ocfs2_is_empty_extent(&el->l_recs[0])) { + le16_add_cpu(&el->l_next_free_rec, -1); + + for(i = 0; + i < le16_to_cpu(el->l_next_free_rec); i++) + el->l_recs[i] = el->l_recs[i + 1]; + + memset(&el->l_recs[i], 0, + sizeof(struct ocfs2_extent_rec)); + + /* + * We've modified our extent list. The + * simplest way to handle this change + * is to being the search from the + * start again. + */ + goto find_tail_record; + } + + le32_add_cpu(&rec->e_clusters, -clusters_to_del); + + /* + * We'll use "new_edge" on our way back up the + * tree to know what our rightmost cpos is. + */ + new_edge = le32_to_cpu(rec->e_clusters); + new_edge += le32_to_cpu(rec->e_cpos); + + /* + * The caller will use this to delete data blocks. + */ + *delete_start = le64_to_cpu(rec->e_blkno) + + ocfs2_clusters_to_blocks(inode->i_sb, + le32_to_cpu(rec->e_clusters)); + + /* + * If it's now empty, remove this record. + */ + if (le32_to_cpu(rec->e_clusters) == 0) { + memset(rec, 0, + sizeof(struct ocfs2_extent_rec)); + le16_add_cpu(&el->l_next_free_rec, -1); + } + } else { + if (le64_to_cpu(rec->e_blkno) == deleted_eb) { + memset(rec, 0, + sizeof(struct ocfs2_extent_rec)); + le16_add_cpu(&el->l_next_free_rec, -1); + + goto delete; + } + + /* Can this actually happen? */ + if (le16_to_cpu(el->l_next_free_rec) == 0) + goto delete; + + /* + * We never actually deleted any clusters + * because our leaf was empty. There's no + * reason to adjust the rightmost edge then. + */ + if (new_edge == 0) + goto delete; + + rec->e_clusters = cpu_to_le32(new_edge); + le32_add_cpu(&rec->e_clusters, + -le32_to_cpu(rec->e_cpos)); + + /* + * A deleted child record should have been + * caught above. + */ + BUG_ON(le32_to_cpu(rec->e_clusters) == 0); + } + +delete: + ret = ocfs2_journal_dirty(handle, bh); + if (ret) { + mlog_errno(ret); + goto out; + } + + mlog(0, "extent list container %llu, after: record %d: " + "(%u, %u, %llu), next = %u.\n", + (unsigned long long)bh->b_blocknr, i, + le32_to_cpu(rec->e_cpos), le32_to_cpu(rec->e_clusters), + (unsigned long long)le64_to_cpu(rec->e_blkno), + le16_to_cpu(el->l_next_free_rec)); + + /* + * We must be careful to only attempt delete of an + * extent block (and not the root inode block). + */ + if (index > 0 && le16_to_cpu(el->l_next_free_rec) == 0) { + struct ocfs2_extent_block *eb = + (struct ocfs2_extent_block *)bh->b_data; + + /* + * Save this for use when processing the + * parent block. + */ + deleted_eb = le64_to_cpu(eb->h_blkno); + + mlog(0, "deleting this extent block.\n"); + + ocfs2_remove_from_cache(inode, bh); + + BUG_ON(le32_to_cpu(el->l_recs[0].e_clusters)); + BUG_ON(le32_to_cpu(el->l_recs[0].e_cpos)); + BUG_ON(le64_to_cpu(el->l_recs[0].e_blkno)); + + if (le16_to_cpu(eb->h_suballoc_slot) == 0) { + /* + * This code only understands how to + * lock the suballocator in slot 0, + * which is fine because allocation is + * only ever done out of that + * suballocator too. A future version + * might change that however, so avoid + * a free if we don't know how to + * handle it. This way an fs incompat + * bit will not be necessary. + */ + ret = ocfs2_free_extent_block(handle, + tc->tc_ext_alloc_inode, + tc->tc_ext_alloc_bh, + eb); + + /* An error here is not fatal. */ + if (ret < 0) + mlog_errno(ret); + } + } else { + deleted_eb = 0; + } + + index--; + } + + ret = 0; +out: + return ret; +} + static int ocfs2_do_truncate(struct ocfs2_super *osb, unsigned int clusters_to_del, struct inode *inode, @@ -2992,20 +3238,16 @@ static int ocfs2_do_truncate(struct ocfs2_super *osb, struct ocfs2_truncate_context *tc, struct ocfs2_path *path) { - int status, i, index; + int status; struct ocfs2_dinode *fe; - struct ocfs2_extent_block *eb; struct ocfs2_extent_block *last_eb = NULL; struct ocfs2_extent_list *el; - struct buffer_head *eb_bh = NULL; struct buffer_head *last_eb_bh = NULL; u64 delete_blk = 0; fe = (struct ocfs2_dinode *) fe_bh->b_data; - status = ocfs2_find_new_last_ext_blk(inode, - le32_to_cpu(fe->i_clusters) - - clusters_to_del, + status = ocfs2_find_new_last_ext_blk(inode, clusters_to_del, path, &last_eb_bh); if (status < 0) { mlog_errno(status); @@ -3016,14 +3258,10 @@ static int ocfs2_do_truncate(struct ocfs2_super *osb, * Each component will be touched, so we might as well journal * here to avoid having to handle errors later. */ - for (i = 0; i < path_num_items(path); i++) { - status = ocfs2_journal_access(handle, inode, - path->p_node[i].bh, - OCFS2_JOURNAL_ACCESS_WRITE); - if (status < 0) { - mlog_errno(status); - goto bail; - } + status = ocfs2_journal_access_path(inode, handle, path); + if (status < 0) { + mlog_errno(status); + goto bail; } if (last_eb_bh) { @@ -3047,6 +3285,7 @@ static int ocfs2_do_truncate(struct ocfs2_super *osb, ocfs2_error(inode->i_sb, "Inode %lu has an empty extent record, depth %u\n", inode->i_ino, le16_to_cpu(el->l_tree_depth)); + status = -EROFS; goto bail; } @@ -3056,38 +3295,11 @@ static int ocfs2_do_truncate(struct ocfs2_super *osb, spin_unlock(&OCFS2_I(inode)->ip_lock); le32_add_cpu(&fe->i_clusters, -clusters_to_del); - i = le16_to_cpu(el->l_next_free_rec) - 1; - - BUG_ON(le32_to_cpu(el->l_recs[i].e_clusters) < clusters_to_del); - le32_add_cpu(&el->l_recs[i].e_clusters, -clusters_to_del); - /* tree depth zero, we can just delete the clusters, otherwise - * we need to record the offset of the next level extent block - * as we may overwrite it. */ - if (!el->l_tree_depth) { - delete_blk = le64_to_cpu(el->l_recs[i].e_blkno) - + ocfs2_clusters_to_blocks(osb->sb, - le32_to_cpu(el->l_recs[i].e_clusters)); - - if (!el->l_recs[i].e_clusters) { - /* if we deleted the whole extent record, then clear - * out the other fields and update the extent - * list. - */ - el->l_recs[i].e_cpos = 0; - el->l_recs[i].e_blkno = 0; - BUG_ON(!el->l_next_free_rec); - le16_add_cpu(&el->l_next_free_rec, -1); - - /* - * The leftmost record might be an empty extent - - * delete it here too. - */ - if (i == 1 && ocfs2_is_empty_extent(&el->l_recs[0])) { - el->l_recs[0].e_cpos = 0; - el->l_recs[0].e_blkno = 0; - el->l_next_free_rec = 0; - } - } + status = ocfs2_trim_tree(inode, path, handle, tc, + clusters_to_del, &delete_blk); + if (status) { + mlog_errno(status); + goto bail; } if (le32_to_cpu(fe->i_clusters) == 0) { @@ -3115,125 +3327,13 @@ static int ocfs2_do_truncate(struct ocfs2_super *osb, } } - index = 1; - /* if our tree depth > 0, update all the tree blocks below us. */ - while (index <= path->p_tree_depth) { - eb_bh = path->p_node[index].bh; - eb = (struct ocfs2_extent_block *)eb_bh->b_data; - el = path->p_node[index].el; - - mlog(0, "traveling tree (index = %d, extent block: %llu)\n", - index, (unsigned long long)eb_bh->b_blocknr); - - BUG_ON(le16_to_cpu(el->l_next_free_rec) == 0); - if (index != - (path->p_tree_depth - le16_to_cpu(el->l_tree_depth))) { - ocfs2_error(inode->i_sb, - "Inode %lu has invalid ext. block %llu\n", - inode->i_ino, - (unsigned long long)eb_bh->b_blocknr); - goto bail; - } - - i = le16_to_cpu(el->l_next_free_rec) - 1; - - mlog(0, "extent block %llu, before: record %d: " - "(%u, %u, %llu), next = %u\n", - (unsigned long long)le64_to_cpu(eb->h_blkno), i, - le32_to_cpu(el->l_recs[i].e_cpos), - le32_to_cpu(el->l_recs[i].e_clusters), - (unsigned long long)le64_to_cpu(el->l_recs[i].e_blkno), - le16_to_cpu(el->l_next_free_rec)); - - BUG_ON(le32_to_cpu(el->l_recs[i].e_clusters) < clusters_to_del); - le32_add_cpu(&el->l_recs[i].e_clusters, -clusters_to_del); - - /* bottom-most block requires us to delete data.*/ - if (!el->l_tree_depth) - delete_blk = le64_to_cpu(el->l_recs[i].e_blkno) - + ocfs2_clusters_to_blocks(osb->sb, - le32_to_cpu(el->l_recs[i].e_clusters)); - if (!el->l_recs[i].e_clusters) { - el->l_recs[i].e_cpos = 0; - el->l_recs[i].e_blkno = 0; - BUG_ON(!el->l_next_free_rec); - le16_add_cpu(&el->l_next_free_rec, -1); - } - if (i == 1 && ocfs2_is_empty_extent(&el->l_recs[0])) { - el->l_recs[0].e_cpos = 0; - el->l_recs[0].e_blkno = 0; - el->l_next_free_rec = 0; - } - - mlog(0, "extent block %llu, after: record %d: " - "(%u, %u, %llu), next = %u\n", - (unsigned long long)le64_to_cpu(eb->h_blkno), i, - le32_to_cpu(el->l_recs[i].e_cpos), - le32_to_cpu(el->l_recs[i].e_clusters), - (unsigned long long)le64_to_cpu(el->l_recs[i].e_blkno), - le16_to_cpu(el->l_next_free_rec)); - - status = ocfs2_journal_dirty(handle, eb_bh); + if (delete_blk) { + status = ocfs2_truncate_log_append(osb, handle, delete_blk, + clusters_to_del); if (status < 0) { mlog_errno(status); goto bail; } - - if (!el->l_next_free_rec) { - mlog(0, "deleting this extent block.\n"); - - ocfs2_remove_from_cache(inode, eb_bh); - - BUG_ON(el->l_recs[0].e_clusters); - BUG_ON(el->l_recs[0].e_cpos); - BUG_ON(el->l_recs[0].e_blkno); - - /* - * We need to remove this extent block from - * the list above it. - * - * Since we've passed it already in this loop, - * no need to worry about journaling. - */ - el = path->p_node[index - 1].el; - i = le16_to_cpu(el->l_next_free_rec) - 1; - BUG_ON(i < 0); - el->l_recs[i].e_cpos = 0; - el->l_recs[i].e_clusters = 0; - el->l_recs[i].e_blkno = 0; - le16_add_cpu(&el->l_next_free_rec, -1); - - if (eb->h_suballoc_slot == 0) { - /* - * This code only understands how to - * lock the suballocator in slot 0, - * which is fine because allocation is - * only ever done out of that - * suballocator too. A future version - * might change that however, so avoid - * a free if we don't know how to - * handle it. This way an fs incompat - * bit will not be necessary. - */ - status = ocfs2_free_extent_block(handle, - tc->tc_ext_alloc_inode, - tc->tc_ext_alloc_bh, - eb); - if (status < 0) { - mlog_errno(status); - goto bail; - } - } - } - index++; - } - - BUG_ON(!delete_blk); - status = ocfs2_truncate_log_append(osb, handle, delete_blk, - clusters_to_del); - if (status < 0) { - mlog_errno(status); - goto bail; } status = 0; bail: @@ -3274,6 +3374,14 @@ int ocfs2_commit_truncate(struct ocfs2_super *osb, goto bail; } start: + /* + * Check that we still have allocation to delete. + */ + if (OCFS2_I(inode)->ip_clusters == 0) { + status = 0; + goto bail; + } + /* * Truncate always works against the rightmost tree branch. */ @@ -3298,6 +3406,15 @@ start: * - no record needs to be removed (truncate has completed) */ el = path_leaf_el(path); + if (le16_to_cpu(el->l_next_free_rec) == 0) { + ocfs2_error(inode->i_sb, + "Inode %llu has empty extent block at %llu\n", + (unsigned long long)OCFS2_I(inode)->ip_blkno, + (unsigned long long)path_leaf_bh(path)->b_blocknr); + status = -EROFS; + goto bail; + } + i = le16_to_cpu(el->l_next_free_rec) - 1; range = le32_to_cpu(el->l_recs[i].e_cpos) + le32_to_cpu(el->l_recs[i].e_clusters); @@ -3359,10 +3476,11 @@ start: ocfs2_reinit_path(path, 1); /* - * Only loop if we still have allocation. + * The check above will catch the case where we've truncated + * away all allocation. */ - if (OCFS2_I(inode)->ip_clusters) - goto start; + goto start; + bail: up_write(&OCFS2_I(inode)->ip_alloc_sem); @@ -3414,22 +3532,6 @@ int ocfs2_prepare_truncate(struct ocfs2_super *osb, "%llu\n", fe->i_clusters, new_i_clusters, (unsigned long long)fe->i_size); - if (!ocfs2_sparse_alloc(osb) && - le32_to_cpu(fe->i_clusters) <= new_i_clusters) { - ocfs2_error(inode->i_sb, "Dinode %llu has cluster count " - "%u and size %llu whereas struct inode has " - "cluster count %u and size %llu which caused an " - "invalid truncate to %u clusters.", - (unsigned long long)le64_to_cpu(fe->i_blkno), - le32_to_cpu(fe->i_clusters), - (unsigned long long)le64_to_cpu(fe->i_size), - OCFS2_I(inode)->ip_clusters, i_size_read(inode), - new_i_clusters); - mlog_meta_lvb(ML_ERROR, &OCFS2_I(inode)->ip_meta_lockres); - status = -EIO; - goto bail; - } - *tc = kzalloc(sizeof(struct ocfs2_truncate_context), GFP_KERNEL); if (!(*tc)) { status = -ENOMEM; diff --git a/fs/ocfs2/file.c b/fs/ocfs2/file.c index 8c97fa1c45f6..edc0b617f409 100644 --- a/fs/ocfs2/file.c +++ b/fs/ocfs2/file.c @@ -344,18 +344,6 @@ static int ocfs2_truncate_file(struct inode *inode, } ocfs2_data_unlock(inode, 1); - if (le32_to_cpu(fe->i_clusters) == - ocfs2_clusters_for_bytes(osb->sb, new_i_size)) { - mlog(0, "fe->i_clusters = %u, so we do a simple truncate\n", - fe->i_clusters); - /* No allocation change is required, so lets fast path - * this truncate. */ - status = ocfs2_simple_size_update(inode, di_bh, new_i_size); - if (status < 0) - mlog_errno(status); - goto bail; - } - /* alright, we're going to need to do a full blown alloc size * change. Orphan the inode so that recovery can complete the * truncate if necessary. This does the task of marking @@ -785,7 +773,7 @@ static int ocfs2_extend_file(struct inode *inode, size_t tail_to_skip) { int ret = 0; - u32 clusters_to_add; + u32 clusters_to_add = 0; BUG_ON(!tail_to_skip && !di_bh); @@ -797,6 +785,11 @@ static int ocfs2_extend_file(struct inode *inode, goto out; BUG_ON(new_i_size < i_size_read(inode)); + if (ocfs2_sparse_alloc(OCFS2_SB(inode->i_sb))) { + BUG_ON(tail_to_skip != 0); + goto out_update_size; + } + clusters_to_add = ocfs2_clusters_for_bytes(inode->i_sb, new_i_size) - OCFS2_I(inode)->ip_clusters; @@ -832,6 +825,7 @@ static int ocfs2_extend_file(struct inode *inode, goto out_unlock; } +out_update_size: if (!tail_to_skip) { /* We're being called from ocfs2_setattr() which wants * us to update i_size */ @@ -841,7 +835,8 @@ static int ocfs2_extend_file(struct inode *inode, } out_unlock: - ocfs2_data_unlock(inode, 1); + if (!ocfs2_sparse_alloc(OCFS2_SB(inode->i_sb))) + ocfs2_data_unlock(inode, 1); out: return ret; @@ -1097,6 +1092,14 @@ static int ocfs2_prepare_inode_for_write(struct dentry *dentry, } else { saved_pos = *ppos; } + + /* + * The rest of this loop is concerned with legacy file + * systems which don't support sparse files. + */ + if (ocfs2_sparse_alloc(OCFS2_SB(inode->i_sb))) + break; + newsize = count + saved_pos; mlog(0, "pos=%lld newsize=%lld cursize=%lld\n", diff --git a/fs/ocfs2/inode.c b/fs/ocfs2/inode.c index 5ff8549eb1a3..0bd86a137591 100644 --- a/fs/ocfs2/inode.c +++ b/fs/ocfs2/inode.c @@ -487,7 +487,6 @@ static int ocfs2_truncate_for_delete(struct ocfs2_super *osb, struct buffer_head *fe_bh) { int status = 0; - handle_t *handle = NULL; struct ocfs2_truncate_context *tc = NULL; struct ocfs2_dinode *fe; @@ -495,41 +494,20 @@ static int ocfs2_truncate_for_delete(struct ocfs2_super *osb, fe = (struct ocfs2_dinode *) fe_bh->b_data; - /* zero allocation, zero truncate :) */ - if (!fe->i_clusters) - goto bail; - - handle = ocfs2_start_trans(osb, OCFS2_INODE_UPDATE_CREDITS); - if (IS_ERR(handle)) { - status = PTR_ERR(handle); - handle = NULL; - mlog_errno(status); - goto bail; - } - - status = ocfs2_set_inode_size(handle, inode, fe_bh, 0ULL); - if (status < 0) { - mlog_errno(status); - goto bail; - } - - ocfs2_commit_trans(osb, handle); - handle = NULL; - - status = ocfs2_prepare_truncate(osb, inode, fe_bh, &tc); - if (status < 0) { - mlog_errno(status); - goto bail; - } + if (fe->i_clusters) { + status = ocfs2_prepare_truncate(osb, inode, fe_bh, &tc); + if (status < 0) { + mlog_errno(status); + goto out; + } - status = ocfs2_commit_truncate(osb, inode, fe_bh, tc); - if (status < 0) { - mlog_errno(status); - goto bail; + status = ocfs2_commit_truncate(osb, inode, fe_bh, tc); + if (status < 0) { + mlog_errno(status); + goto out; + } } -bail: - if (handle) - ocfs2_commit_trans(osb, handle); +out: mlog_exit(status); return status; -- cgit From 60b11392f1a09433740bda3048202213daa27736 Mon Sep 17 00:00:00 2001 From: Mark Fasheh Date: Fri, 16 Feb 2007 11:46:50 -0800 Subject: ocfs2: zero tail of sparse files on truncate Since we don't zero on extend anymore, truncate needs to be fixed up to zero the part of a file between i_size and and end of it's cluster. Otherwise a subsequent extend could expose bad data. This introduced a new helper, which can be used in ocfs2_write(). Signed-off-by: Mark Fasheh --- fs/ocfs2/alloc.c | 224 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ fs/ocfs2/alloc.h | 2 + fs/ocfs2/aops.c | 34 ++++----- fs/ocfs2/aops.h | 12 +++ fs/ocfs2/file.c | 40 ++++++++-- fs/ocfs2/inode.c | 30 +++++++- fs/ocfs2/ocfs2.h | 11 +++ 7 files changed, 328 insertions(+), 25 deletions(-) (limited to 'fs/ocfs2/alloc.c') diff --git a/fs/ocfs2/alloc.c b/fs/ocfs2/alloc.c index 9a40603c4d4b..98694a1add43 100644 --- a/fs/ocfs2/alloc.c +++ b/fs/ocfs2/alloc.c @@ -27,6 +27,7 @@ #include #include #include +#include #define MLOG_MASK_PREFIX ML_DISK_ALLOC #include @@ -34,6 +35,7 @@ #include "ocfs2.h" #include "alloc.h" +#include "aops.h" #include "dlmglue.h" #include "extent_map.h" #include "inode.h" @@ -3342,6 +3344,228 @@ bail: return status; } +static int ocfs2_writeback_zero_func(handle_t *handle, struct buffer_head *bh) +{ + set_buffer_uptodate(bh); + mark_buffer_dirty(bh); + return 0; +} + +static int ocfs2_ordered_zero_func(handle_t *handle, struct buffer_head *bh) +{ + set_buffer_uptodate(bh); + mark_buffer_dirty(bh); + return ocfs2_journal_dirty_data(handle, bh); +} + +static void ocfs2_zero_cluster_pages(struct inode *inode, loff_t isize, + struct page **pages, int numpages, + u64 phys, handle_t *handle) +{ + int i, ret, partial = 0; + void *kaddr; + struct page *page; + unsigned int from, to = PAGE_CACHE_SIZE; + struct super_block *sb = inode->i_sb; + + BUG_ON(!ocfs2_sparse_alloc(OCFS2_SB(sb))); + + if (numpages == 0) + goto out; + + from = isize & (PAGE_CACHE_SIZE - 1); /* 1st page offset */ + if (PAGE_CACHE_SHIFT > OCFS2_SB(sb)->s_clustersize_bits) { + /* + * Since 'from' has been capped to a value below page + * size, this calculation won't be able to overflow + * 'to' + */ + to = ocfs2_align_bytes_to_clusters(sb, from); + + /* + * The truncate tail in this case should never contain + * more than one page at maximum. The loop below also + * assumes this. + */ + BUG_ON(numpages != 1); + } + + for(i = 0; i < numpages; i++) { + page = pages[i]; + + BUG_ON(from > PAGE_CACHE_SIZE); + BUG_ON(to > PAGE_CACHE_SIZE); + + ret = ocfs2_map_page_blocks(page, &phys, inode, from, to, 0); + if (ret) + mlog_errno(ret); + + kaddr = kmap_atomic(page, KM_USER0); + memset(kaddr + from, 0, to - from); + kunmap_atomic(kaddr, KM_USER0); + + /* + * Need to set the buffers we zero'd into uptodate + * here if they aren't - ocfs2_map_page_blocks() + * might've skipped some + */ + if (ocfs2_should_order_data(inode)) { + ret = walk_page_buffers(handle, + page_buffers(page), + from, to, &partial, + ocfs2_ordered_zero_func); + if (ret < 0) + mlog_errno(ret); + } else { + ret = walk_page_buffers(handle, page_buffers(page), + from, to, &partial, + ocfs2_writeback_zero_func); + if (ret < 0) + mlog_errno(ret); + } + + if (!partial) + SetPageUptodate(page); + + flush_dcache_page(page); + + /* + * Every page after the 1st one should be completely zero'd. + */ + from = 0; + } +out: + if (pages) { + for (i = 0; i < numpages; i++) { + page = pages[i]; + unlock_page(page); + mark_page_accessed(page); + page_cache_release(page); + } + } +} + +static int ocfs2_grab_eof_pages(struct inode *inode, loff_t isize, struct page **pages, + int *num, u64 *phys) +{ + int i, numpages = 0, ret = 0; + unsigned int csize = OCFS2_SB(inode->i_sb)->s_clustersize; + struct super_block *sb = inode->i_sb; + struct address_space *mapping = inode->i_mapping; + unsigned long index; + u64 next_cluster_bytes; + + BUG_ON(!ocfs2_sparse_alloc(OCFS2_SB(sb))); + + /* Cluster boundary, so we don't need to grab any pages. */ + if ((isize & (csize - 1)) == 0) + goto out; + + ret = ocfs2_extent_map_get_blocks(inode, isize >> sb->s_blocksize_bits, + phys, NULL); + if (ret) { + mlog_errno(ret); + goto out; + } + + /* Tail is a hole. */ + if (*phys == 0) + goto out; + + next_cluster_bytes = ocfs2_align_bytes_to_clusters(inode->i_sb, isize); + index = isize >> PAGE_CACHE_SHIFT; + do { + pages[numpages] = grab_cache_page(mapping, index); + if (!pages[numpages]) { + ret = -ENOMEM; + mlog_errno(ret); + goto out; + } + + numpages++; + index++; + } while (index < (next_cluster_bytes >> PAGE_CACHE_SHIFT)); + +out: + if (ret != 0) { + if (pages) { + for (i = 0; i < numpages; i++) { + if (pages[i]) { + unlock_page(pages[i]); + page_cache_release(pages[i]); + } + } + } + numpages = 0; + } + + *num = numpages; + + return ret; +} + +/* + * Zero the area past i_size but still within an allocated + * cluster. This avoids exposing nonzero data on subsequent file + * extends. + * + * We need to call this before i_size is updated on the inode because + * otherwise block_write_full_page() will skip writeout of pages past + * i_size. The new_i_size parameter is passed for this reason. + */ +int ocfs2_zero_tail_for_truncate(struct inode *inode, handle_t *handle, + u64 new_i_size) +{ + int ret, numpages; + struct page **pages = NULL; + u64 phys; + + /* + * File systems which don't support sparse files zero on every + * extend. + */ + if (!ocfs2_sparse_alloc(OCFS2_SB(inode->i_sb))) + return 0; + + pages = kcalloc(ocfs2_pages_per_cluster(inode->i_sb), + sizeof(struct page *), GFP_NOFS); + if (pages == NULL) { + ret = -ENOMEM; + mlog_errno(ret); + goto out; + } + + ret = ocfs2_grab_eof_pages(inode, new_i_size, pages, &numpages, &phys); + if (ret) { + mlog_errno(ret); + goto out; + } + + /* + * Truncate on an i_size boundary - nothing more to do. + */ + if (numpages == 0) + goto out; + + ocfs2_zero_cluster_pages(inode, new_i_size, pages, numpages, phys, + handle); + + /* + * Initiate writeout of the pages we zero'd here. We don't + * wait on them - the truncate_inode_pages() call later will + * do that for us. + */ + ret = filemap_fdatawrite(inode->i_mapping); + if (ret) + mlog_errno(ret); + +out: + if (pages) + kfree(pages); + + return ret; +} + /* * It is expected, that by the time you call this function, * inode->i_size and fe->i_size have been adjusted. diff --git a/fs/ocfs2/alloc.h b/fs/ocfs2/alloc.h index bff2a162b030..3cb39cd5e478 100644 --- a/fs/ocfs2/alloc.h +++ b/fs/ocfs2/alloc.h @@ -71,6 +71,8 @@ struct ocfs2_truncate_context { struct buffer_head *tc_last_eb_bh; }; +int ocfs2_zero_tail_for_truncate(struct inode *inode, handle_t *handle, + u64 new_i_size); int ocfs2_prepare_truncate(struct ocfs2_super *osb, struct inode *inode, struct buffer_head *fe_bh, diff --git a/fs/ocfs2/aops.c b/fs/ocfs2/aops.c index acf8f0006725..605c82a93f01 100644 --- a/fs/ocfs2/aops.c +++ b/fs/ocfs2/aops.c @@ -308,13 +308,13 @@ int ocfs2_prepare_write_nolock(struct inode *inode, struct page *page, * functionality yet, but IMHO it's better to cut and paste the whole * thing so we can avoid introducing our own bugs (and easily pick up * their fixes when they happen) --Mark */ -static int walk_page_buffers( handle_t *handle, - struct buffer_head *head, - unsigned from, - unsigned to, - int *partial, - int (*fn)( handle_t *handle, - struct buffer_head *bh)) +int walk_page_buffers( handle_t *handle, + struct buffer_head *head, + unsigned from, + unsigned to, + int *partial, + int (*fn)( handle_t *handle, + struct buffer_head *bh)) { struct buffer_head *bh; unsigned block_start, block_end; @@ -654,9 +654,9 @@ static void ocfs2_clear_page_regions(struct page *page, * * This will also skip zeroing, which is handled externally. */ -static int ocfs2_map_page_blocks(struct page *page, u64 *p_blkno, - struct inode *inode, unsigned int from, - unsigned int to, int new) +int ocfs2_map_page_blocks(struct page *page, u64 *p_blkno, + struct inode *inode, unsigned int from, + unsigned int to, int new) { int ret = 0; struct buffer_head *head, *bh, *wait[2], **wait_bh = wait; @@ -675,8 +675,7 @@ static int ocfs2_map_page_blocks(struct page *page, u64 *p_blkno, * Ignore blocks outside of our i/o range - * they may belong to unallocated clusters. */ - if (block_start >= to || - (block_start + bsize) <= from) { + if (block_start >= to || block_end <= from) { if (PageUptodate(page)) set_buffer_uptodate(bh); continue; @@ -971,7 +970,6 @@ static ssize_t ocfs2_write(struct file *file, u32 phys, handle_t *handle, u64 v_blkno, p_blkno; struct address_space *mapping = file->f_mapping; struct inode *inode = mapping->host; - unsigned int cbits = OCFS2_SB(inode->i_sb)->s_clustersize_bits; unsigned long index, start; struct page **cpages; @@ -979,13 +977,11 @@ static ssize_t ocfs2_write(struct file *file, u32 phys, handle_t *handle, /* * Figure out how many pages we'll be manipulating here. For - * non-allocating write, or any writes where cluster size is - * less than page size, we only need one page. Otherwise, - * allocating writes of cluster size larger than page size - * need cluster size pages. + * non allocating write, we just change the one + * page. Otherwise, we'll need a whole clusters worth. */ - if (new && !wc->w_large_pages) - numpages = (1 << cbits) / PAGE_SIZE; + if (new) + numpages = ocfs2_pages_per_cluster(inode->i_sb); cpages = kzalloc(sizeof(*cpages) * numpages, GFP_NOFS); if (!cpages) { diff --git a/fs/ocfs2/aops.h b/fs/ocfs2/aops.h index eeb2c42483e8..7d94071f0ab7 100644 --- a/fs/ocfs2/aops.h +++ b/fs/ocfs2/aops.h @@ -30,6 +30,18 @@ handle_t *ocfs2_start_walk_page_trans(struct inode *inode, unsigned from, unsigned to); +int ocfs2_map_page_blocks(struct page *page, u64 *p_blkno, + struct inode *inode, unsigned int from, + unsigned int to, int new); + +int walk_page_buffers( handle_t *handle, + struct buffer_head *head, + unsigned from, + unsigned to, + int *partial, + int (*fn)( handle_t *handle, + struct buffer_head *bh)); + struct ocfs2_write_ctxt; typedef int (ocfs2_page_writer)(struct inode *, struct ocfs2_write_ctxt *, u64 *, unsigned int *, unsigned int *); diff --git a/fs/ocfs2/file.c b/fs/ocfs2/file.c index 667e5a869bf5..5fd49ec169dc 100644 --- a/fs/ocfs2/file.c +++ b/fs/ocfs2/file.c @@ -262,6 +262,7 @@ static int ocfs2_orphan_for_truncate(struct ocfs2_super *osb, { int status; handle_t *handle; + struct ocfs2_dinode *di; mlog_entry_void(); @@ -275,12 +276,39 @@ static int ocfs2_orphan_for_truncate(struct ocfs2_super *osb, goto out; } - status = ocfs2_set_inode_size(handle, inode, fe_bh, new_i_size); + status = ocfs2_journal_access(handle, inode, fe_bh, + OCFS2_JOURNAL_ACCESS_WRITE); + if (status < 0) { + mlog_errno(status); + goto out_commit; + } + + /* + * Do this before setting i_size. + */ + status = ocfs2_zero_tail_for_truncate(inode, handle, new_i_size); + if (status) { + mlog_errno(status); + goto out_commit; + } + + i_size_write(inode, new_i_size); + inode->i_blocks = ocfs2_align_bytes_to_sectors(new_i_size); + inode->i_ctime = inode->i_mtime = CURRENT_TIME; + + di = (struct ocfs2_dinode *) fe_bh->b_data; + di->i_size = cpu_to_le64(new_i_size); + di->i_ctime = di->i_mtime = cpu_to_le64(inode->i_ctime.tv_sec); + di->i_ctime_nsec = di->i_mtime_nsec = cpu_to_le32(inode->i_ctime.tv_nsec); + + status = ocfs2_journal_dirty(handle, fe_bh); if (status < 0) mlog_errno(status); +out_commit: ocfs2_commit_trans(osb, handle); out: + mlog_exit(status); return status; } @@ -343,7 +371,6 @@ static int ocfs2_truncate_file(struct inode *inode, mlog_errno(status); goto bail; } - ocfs2_data_unlock(inode, 1); /* alright, we're going to need to do a full blown alloc size * change. Orphan the inode so that recovery can complete the @@ -352,22 +379,25 @@ static int ocfs2_truncate_file(struct inode *inode, status = ocfs2_orphan_for_truncate(osb, inode, di_bh, new_i_size); if (status < 0) { mlog_errno(status); - goto bail; + goto bail_unlock_data; } status = ocfs2_prepare_truncate(osb, inode, di_bh, &tc); if (status < 0) { mlog_errno(status); - goto bail; + goto bail_unlock_data; } status = ocfs2_commit_truncate(osb, inode, di_bh, tc); if (status < 0) { mlog_errno(status); - goto bail; + goto bail_unlock_data; } /* TODO: orphan dir cleanup here. */ +bail_unlock_data: + ocfs2_data_unlock(inode, 1); + bail: mlog_exit(status); diff --git a/fs/ocfs2/inode.c b/fs/ocfs2/inode.c index 0bd86a137591..78c99b5050df 100644 --- a/fs/ocfs2/inode.c +++ b/fs/ocfs2/inode.c @@ -489,12 +489,38 @@ static int ocfs2_truncate_for_delete(struct ocfs2_super *osb, int status = 0; struct ocfs2_truncate_context *tc = NULL; struct ocfs2_dinode *fe; + handle_t *handle = NULL; mlog_entry_void(); fe = (struct ocfs2_dinode *) fe_bh->b_data; if (fe->i_clusters) { + handle = ocfs2_start_trans(osb, OCFS2_INODE_UPDATE_CREDITS); + if (IS_ERR(handle)) { + status = PTR_ERR(handle); + mlog_errno(status); + goto out; + } + + status = ocfs2_journal_access(handle, inode, fe_bh, + OCFS2_JOURNAL_ACCESS_WRITE); + if (status < 0) { + mlog_errno(status); + goto out; + } + + i_size_write(inode, 0); + + status = ocfs2_mark_inode_dirty(handle, inode, fe_bh); + if (status < 0) { + mlog_errno(status); + goto out; + } + + ocfs2_commit_trans(osb, handle); + handle = NULL; + status = ocfs2_prepare_truncate(osb, inode, fe_bh, &tc); if (status < 0) { mlog_errno(status); @@ -507,8 +533,10 @@ static int ocfs2_truncate_for_delete(struct ocfs2_super *osb, goto out; } } -out: +out: + if (handle) + ocfs2_commit_trans(osb, handle); mlog_exit(status); return status; } diff --git a/fs/ocfs2/ocfs2.h b/fs/ocfs2/ocfs2.h index 2699f7cac21a..82cc92dcf8a6 100644 --- a/fs/ocfs2/ocfs2.h +++ b/fs/ocfs2/ocfs2.h @@ -495,6 +495,17 @@ static inline unsigned long ocfs2_align_clusters_to_page_index(struct super_bloc return index; } +static inline unsigned int ocfs2_pages_per_cluster(struct super_block *sb) +{ + unsigned int cbits = OCFS2_SB(sb)->s_clustersize_bits; + unsigned int pages_per_cluster = 1; + + if (PAGE_CACHE_SHIFT < cbits) + pages_per_cluster = 1 << (cbits - PAGE_CACHE_SHIFT); + + return pages_per_cluster; +} + #define ocfs2_set_bit ext2_set_bit #define ocfs2_clear_bit ext2_clear_bit #define ocfs2_test_bit ext2_test_bit -- cgit From fa41045fcbf78269991d5aebb1820fc51534f05d Mon Sep 17 00:00:00 2001 From: Mark Fasheh Date: Thu, 1 Mar 2007 11:22:19 -0800 Subject: ocfs2: Use do_sync_mapping_range() in ocfs2_zero_tail_for_truncate() Do this instead of filemap_fdatawrite() - this way we sync only the range between i_size and the cluster boundary. Signed-off-by: Mark Fasheh --- fs/ocfs2/alloc.c | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) (limited to 'fs/ocfs2/alloc.c') diff --git a/fs/ocfs2/alloc.c b/fs/ocfs2/alloc.c index 98694a1add43..027cf5d05ffb 100644 --- a/fs/ocfs2/alloc.c +++ b/fs/ocfs2/alloc.c @@ -3517,6 +3517,7 @@ int ocfs2_zero_tail_for_truncate(struct inode *inode, handle_t *handle, u64 new_i_size) { int ret, numpages; + loff_t endbyte; struct page **pages = NULL; u64 phys; @@ -3555,7 +3556,9 @@ int ocfs2_zero_tail_for_truncate(struct inode *inode, handle_t *handle, * wait on them - the truncate_inode_pages() call later will * do that for us. */ - ret = filemap_fdatawrite(inode->i_mapping); + endbyte = ocfs2_align_bytes_to_clusters(inode->i_sb, new_i_size); + ret = do_sync_mapping_range(inode->i_mapping, new_i_size, + endbyte - 1, SYNC_FILE_RANGE_WRITE); if (ret) mlog_errno(ret); -- cgit From e48edee2d8eab812f31f0ff62c6ba635ca2e1e21 Mon Sep 17 00:00:00 2001 From: Mark Fasheh Date: Wed, 7 Mar 2007 16:46:57 -0800 Subject: ocfs2: make room for unwritten extents flag Due to the size of our group bitmaps, we'll never have a leaf node extent record with more than 16 bits worth of clusters. Split e_clusters up so that leaf nodes can get a flags field where we can mark unwritten extents. Interior nodes whose length references all the child nodes beneath it can't split their e_clusters field, so we use a union to preserve sizing there. Signed-off-by: Mark Fasheh --- fs/ocfs2/alloc.c | 155 +++++++++++++++++++++++++++++++------------------- fs/ocfs2/alloc.h | 19 +++++++ fs/ocfs2/extent_map.c | 19 +++++-- fs/ocfs2/file.c | 6 +- fs/ocfs2/journal.h | 2 +- fs/ocfs2/ocfs2_fs.h | 19 ++++++- 6 files changed, 151 insertions(+), 69 deletions(-) (limited to 'fs/ocfs2/alloc.c') diff --git a/fs/ocfs2/alloc.c b/fs/ocfs2/alloc.c index 027cf5d05ffb..0eab0d328289 100644 --- a/fs/ocfs2/alloc.c +++ b/fs/ocfs2/alloc.c @@ -218,20 +218,32 @@ enum ocfs2_contig_type { CONTIG_RIGHT }; + +/* + * NOTE: ocfs2_block_extent_contig(), ocfs2_extents_adjacent() and + * ocfs2_extent_contig only work properly against leaf nodes! + */ static int ocfs2_block_extent_contig(struct super_block *sb, struct ocfs2_extent_rec *ext, u64 blkno) { - return blkno == (le64_to_cpu(ext->e_blkno) + - ocfs2_clusters_to_blocks(sb, - le32_to_cpu(ext->e_clusters))); + u64 blk_end = le64_to_cpu(ext->e_blkno); + + blk_end += ocfs2_clusters_to_blocks(sb, + le16_to_cpu(ext->e_leaf_clusters)); + + return blkno == blk_end; } static int ocfs2_extents_adjacent(struct ocfs2_extent_rec *left, struct ocfs2_extent_rec *right) { - return (le32_to_cpu(left->e_cpos) + le32_to_cpu(left->e_clusters) == - le32_to_cpu(right->e_cpos)); + u32 left_range; + + left_range = le32_to_cpu(left->e_cpos) + + le16_to_cpu(left->e_leaf_clusters); + + return (left_range == le32_to_cpu(right->e_cpos)); } static enum ocfs2_contig_type @@ -430,7 +442,7 @@ static inline u32 ocfs2_sum_rightmost_rec(struct ocfs2_extent_list *el) i = le16_to_cpu(el->l_next_free_rec) - 1; return le32_to_cpu(el->l_recs[i].e_cpos) + - le32_to_cpu(el->l_recs[i].e_clusters); + ocfs2_rec_clusters(el, &el->l_recs[i]); } /* @@ -442,7 +454,7 @@ static inline u32 ocfs2_sum_rightmost_rec(struct ocfs2_extent_list *el) * for the new last extent block. * * the new branch will be 'empty' in the sense that every block will - * contain a single record with e_clusters == 0. + * contain a single record with cluster count == 0. */ static int ocfs2_add_branch(struct ocfs2_super *osb, handle_t *handle, @@ -532,7 +544,12 @@ static int ocfs2_add_branch(struct ocfs2_super *osb, */ eb_el->l_recs[0].e_cpos = cpu_to_le32(new_cpos); eb_el->l_recs[0].e_blkno = cpu_to_le64(next_blkno); - eb_el->l_recs[0].e_clusters = cpu_to_le32(0); + /* + * eb_el isn't always an interior node, but even leaf + * nodes want a zero'd flags and reserved field so + * this gets the whole 32 bits regardless of use. + */ + eb_el->l_recs[0].e_int_clusters = cpu_to_le32(0); if (!eb_el->l_tree_depth) new_last_eb_blk = le64_to_cpu(eb->h_blkno); @@ -577,7 +594,7 @@ static int ocfs2_add_branch(struct ocfs2_super *osb, i = le16_to_cpu(el->l_next_free_rec); el->l_recs[i].e_blkno = cpu_to_le64(next_blkno); el->l_recs[i].e_cpos = cpu_to_le32(new_cpos); - el->l_recs[i].e_clusters = 0; + el->l_recs[i].e_int_clusters = 0; le16_add_cpu(&el->l_next_free_rec, 1); /* fe needs a new last extent block pointer, as does the @@ -662,11 +679,8 @@ static int ocfs2_shift_tree_depth(struct ocfs2_super *osb, /* copy the fe data into the new extent block */ eb_el->l_tree_depth = fe_el->l_tree_depth; eb_el->l_next_free_rec = fe_el->l_next_free_rec; - for(i = 0; i < le16_to_cpu(fe_el->l_next_free_rec); i++) { - eb_el->l_recs[i].e_cpos = fe_el->l_recs[i].e_cpos; - eb_el->l_recs[i].e_clusters = fe_el->l_recs[i].e_clusters; - eb_el->l_recs[i].e_blkno = fe_el->l_recs[i].e_blkno; - } + for(i = 0; i < le16_to_cpu(fe_el->l_next_free_rec); i++) + eb_el->l_recs[i] = fe_el->l_recs[i]; status = ocfs2_journal_dirty(handle, new_eb_bh); if (status < 0) { @@ -687,12 +701,9 @@ static int ocfs2_shift_tree_depth(struct ocfs2_super *osb, le16_add_cpu(&fe_el->l_tree_depth, 1); fe_el->l_recs[0].e_cpos = 0; fe_el->l_recs[0].e_blkno = eb->h_blkno; - fe_el->l_recs[0].e_clusters = cpu_to_le32(new_clusters); - for(i = 1; i < le16_to_cpu(fe_el->l_next_free_rec); i++) { - fe_el->l_recs[i].e_cpos = 0; - fe_el->l_recs[i].e_clusters = 0; - fe_el->l_recs[i].e_blkno = 0; - } + fe_el->l_recs[0].e_int_clusters = cpu_to_le32(new_clusters); + for(i = 1; i < le16_to_cpu(fe_el->l_next_free_rec); i++) + memset(&fe_el->l_recs[i], 0, sizeof(struct ocfs2_extent_rec)); fe_el->l_next_free_rec = cpu_to_le16(1); /* If this is our 1st tree depth shift, then last_eb_blk @@ -817,9 +828,13 @@ bail: return status; } +/* + * This is only valid for leaf nodes, which are the only ones that can + * have empty extents anyway. + */ static inline int ocfs2_is_empty_extent(struct ocfs2_extent_rec *rec) { - return !rec->e_clusters; + return !rec->e_leaf_clusters; } /* @@ -930,6 +945,8 @@ static void ocfs2_create_empty_extent(struct ocfs2_extent_list *el) { int next_free = le16_to_cpu(el->l_next_free_rec); + BUG_ON(le16_to_cpu(el->l_tree_depth) != 0); + if (next_free == 0) goto set_and_inc; @@ -1034,7 +1051,7 @@ static int __ocfs2_find_path(struct inode *inode, * rightmost record. */ range = le32_to_cpu(rec->e_cpos) + - le32_to_cpu(rec->e_clusters); + ocfs2_rec_clusters(el, rec); if (cpos >= le32_to_cpu(rec->e_cpos) && cpos < range) break; } @@ -1195,21 +1212,21 @@ static void ocfs2_adjust_adjacent_records(struct ocfs2_extent_rec *left_rec, */ left_clusters = le32_to_cpu(right_child_el->l_recs[0].e_cpos); left_clusters -= le32_to_cpu(left_rec->e_cpos); - left_rec->e_clusters = cpu_to_le32(left_clusters); + left_rec->e_int_clusters = cpu_to_le32(left_clusters); /* * Calculate the rightmost cluster count boundary before - * moving cpos - we will need to adjust e_clusters after + * moving cpos - we will need to adjust clusters after * updating e_cpos to keep the same highest cluster count. */ right_end = le32_to_cpu(right_rec->e_cpos); - right_end += le32_to_cpu(right_rec->e_clusters); + right_end += le32_to_cpu(right_rec->e_int_clusters); right_rec->e_cpos = left_rec->e_cpos; le32_add_cpu(&right_rec->e_cpos, left_clusters); right_end -= le32_to_cpu(right_rec->e_cpos); - right_rec->e_clusters = cpu_to_le32(right_end); + right_rec->e_int_clusters = cpu_to_le32(right_end); } /* @@ -1452,6 +1469,8 @@ static int ocfs2_find_cpos_for_left_leaf(struct super_block *sb, u64 blkno; struct ocfs2_extent_list *el; + BUG_ON(path->p_tree_depth == 0); + *cpos = 0; blkno = path_leaf_bh(path)->b_blocknr; @@ -1486,7 +1505,9 @@ static int ocfs2_find_cpos_for_left_leaf(struct super_block *sb, } *cpos = le32_to_cpu(el->l_recs[j - 1].e_cpos); - *cpos = *cpos + le32_to_cpu(el->l_recs[j - 1].e_clusters) - 1; + *cpos = *cpos + ocfs2_rec_clusters(el, + &el->l_recs[j - 1]); + *cpos = *cpos - 1; goto out; } } @@ -1715,7 +1736,7 @@ static void ocfs2_insert_at_leaf(struct ocfs2_extent_rec *insert_rec, unsigned int range; struct ocfs2_extent_rec *rec; - BUG_ON(el->l_tree_depth); + BUG_ON(le16_to_cpu(el->l_tree_depth) != 0); /* * Contiguous insert - either left or right. @@ -1726,8 +1747,8 @@ static void ocfs2_insert_at_leaf(struct ocfs2_extent_rec *insert_rec, rec->e_blkno = insert_rec->e_blkno; rec->e_cpos = insert_rec->e_cpos; } - le32_add_cpu(&rec->e_clusters, - le32_to_cpu(insert_rec->e_clusters)); + le16_add_cpu(&rec->e_leaf_clusters, + le16_to_cpu(insert_rec->e_leaf_clusters)); return; } @@ -1748,7 +1769,8 @@ static void ocfs2_insert_at_leaf(struct ocfs2_extent_rec *insert_rec, if (insert->ins_appending == APPEND_TAIL) { i = le16_to_cpu(el->l_next_free_rec) - 1; rec = &el->l_recs[i]; - range = le32_to_cpu(rec->e_cpos) + le32_to_cpu(rec->e_clusters); + range = le32_to_cpu(rec->e_cpos) + + le16_to_cpu(rec->e_leaf_clusters); BUG_ON(le32_to_cpu(insert_rec->e_cpos) < range); mlog_bug_on_msg(le16_to_cpu(el->l_next_free_rec) >= @@ -1761,9 +1783,9 @@ static void ocfs2_insert_at_leaf(struct ocfs2_extent_rec *insert_rec, le16_to_cpu(el->l_count), le16_to_cpu(el->l_next_free_rec), le32_to_cpu(el->l_recs[i].e_cpos), - le32_to_cpu(el->l_recs[i].e_clusters), + le16_to_cpu(el->l_recs[i].e_leaf_clusters), le32_to_cpu(insert_rec->e_cpos), - le32_to_cpu(insert_rec->e_clusters)); + le16_to_cpu(insert_rec->e_leaf_clusters)); i++; el->l_recs[i] = *insert_rec; le16_add_cpu(&el->l_next_free_rec, 1); @@ -1805,6 +1827,12 @@ static int ocfs2_append_rec_to_path(struct inode *inode, handle_t *handle, *ret_left_path = NULL; + /* + * This shouldn't happen for non-trees. The extent rec cluster + * count manipulation below only works for interior nodes. + */ + BUG_ON(right_path->p_tree_depth == 0); + /* * If our appending insert is at the leftmost edge of a leaf, * then we might need to update the rightmost records of the @@ -1863,6 +1891,8 @@ static int ocfs2_append_rec_to_path(struct inode *inode, handle_t *handle, bh = path_root_bh(right_path); i = 0; while (1) { + struct ocfs2_extent_rec *rec; + next_free = le16_to_cpu(el->l_next_free_rec); if (next_free == 0) { ocfs2_error(inode->i_sb, @@ -1872,16 +1902,19 @@ static int ocfs2_append_rec_to_path(struct inode *inode, handle_t *handle, goto out; } - el->l_recs[next_free - 1].e_clusters = insert_rec->e_cpos; - le32_add_cpu(&el->l_recs[next_free - 1].e_clusters, - le32_to_cpu(insert_rec->e_clusters)); - le32_add_cpu(&el->l_recs[next_free - 1].e_clusters, - -le32_to_cpu(el->l_recs[next_free - 1].e_cpos)); + rec = &el->l_recs[next_free - 1]; + + rec->e_int_clusters = insert_rec->e_cpos; + le32_add_cpu(&rec->e_int_clusters, + le16_to_cpu(insert_rec->e_leaf_clusters)); + le32_add_cpu(&rec->e_int_clusters, + -le32_to_cpu(rec->e_cpos)); ret = ocfs2_journal_dirty(handle, bh); if (ret) mlog_errno(ret); + /* Don't touch the leaf node */ if (++i >= right_path->p_tree_depth) break; @@ -2068,7 +2101,7 @@ static int ocfs2_do_insert_extent(struct inode *inode, out_update_clusters: ocfs2_update_dinode_clusters(inode, di, - le32_to_cpu(insert_rec->e_clusters)); + le16_to_cpu(insert_rec->e_leaf_clusters)); ret = ocfs2_journal_dirty(handle, di_bh); if (ret) @@ -2089,6 +2122,8 @@ static void ocfs2_figure_contig_type(struct inode *inode, int i; enum ocfs2_contig_type contig_type = CONTIG_NONE; + BUG_ON(le16_to_cpu(el->l_tree_depth) != 0); + for(i = 0; i < le16_to_cpu(el->l_next_free_rec); i++) { contig_type = ocfs2_extent_contig(inode, &el->l_recs[i], insert_rec); @@ -2120,7 +2155,7 @@ static void ocfs2_figure_appending_type(struct ocfs2_insert_type *insert, insert->ins_appending = APPEND_NONE; - BUG_ON(el->l_tree_depth); + BUG_ON(le16_to_cpu(el->l_tree_depth) != 0); if (!el->l_next_free_rec) goto set_tail_append; @@ -2134,7 +2169,8 @@ static void ocfs2_figure_appending_type(struct ocfs2_insert_type *insert, i = le16_to_cpu(el->l_next_free_rec) - 1; rec = &el->l_recs[i]; - if (cpos >= (le32_to_cpu(rec->e_cpos) + le32_to_cpu(rec->e_clusters))) + if (cpos >= + (le32_to_cpu(rec->e_cpos) + le16_to_cpu(rec->e_leaf_clusters))) goto set_tail_append; return; @@ -2242,7 +2278,7 @@ static int ocfs2_figure_insert_type(struct inode *inode, * The insert code isn't quite ready to deal with all cases of * left contiguousness. Specifically, if it's an insert into * the 1st record in a leaf, it will require the adjustment of - * e_clusters on the last record of the path directly to it's + * cluster count on the last record of the path directly to it's * left. For now, just catch that case and fool the layers * above us. This works just fine for tree_depth == 0, which * is why we allow that above. @@ -2310,9 +2346,10 @@ int ocfs2_insert_extent(struct ocfs2_super *osb, (unsigned long long)OCFS2_I(inode)->ip_blkno, cpos, OCFS2_I(inode)->ip_clusters); + memset(&rec, 0, sizeof(rec)); rec.e_cpos = cpu_to_le32(cpos); rec.e_blkno = cpu_to_le64(start_blk); - rec.e_clusters = cpu_to_le32(new_clusters); + rec.e_leaf_clusters = cpu_to_le16(new_clusters); status = ocfs2_figure_insert_type(inode, fe_bh, &last_eb_bh, &rec, &insert); @@ -2981,7 +3018,7 @@ static int ocfs2_find_new_last_ext_blk(struct inode *inode, * Check it we'll only be trimming off the end of this * cluster. */ - if (le16_to_cpu(rec->e_clusters) > clusters_to_del) + if (le16_to_cpu(rec->e_leaf_clusters) > clusters_to_del) goto out; } @@ -3061,11 +3098,11 @@ find_tail_record: mlog(0, "Extent list before: record %d: (%u, %u, %llu), " "next = %u\n", i, le32_to_cpu(rec->e_cpos), - le32_to_cpu(rec->e_clusters), + ocfs2_rec_clusters(el, rec), (unsigned long long)le64_to_cpu(rec->e_blkno), le16_to_cpu(el->l_next_free_rec)); - BUG_ON(le32_to_cpu(rec->e_clusters) < clusters_to_del); + BUG_ON(ocfs2_rec_clusters(el, rec) < clusters_to_del); if (le16_to_cpu(el->l_tree_depth) == 0) { /* @@ -3107,13 +3144,13 @@ find_tail_record: goto find_tail_record; } - le32_add_cpu(&rec->e_clusters, -clusters_to_del); + le16_add_cpu(&rec->e_leaf_clusters, -clusters_to_del); /* * We'll use "new_edge" on our way back up the * tree to know what our rightmost cpos is. */ - new_edge = le32_to_cpu(rec->e_clusters); + new_edge = le16_to_cpu(rec->e_leaf_clusters); new_edge += le32_to_cpu(rec->e_cpos); /* @@ -3121,12 +3158,12 @@ find_tail_record: */ *delete_start = le64_to_cpu(rec->e_blkno) + ocfs2_clusters_to_blocks(inode->i_sb, - le32_to_cpu(rec->e_clusters)); + le16_to_cpu(rec->e_leaf_clusters)); /* * If it's now empty, remove this record. */ - if (le32_to_cpu(rec->e_clusters) == 0) { + if (le16_to_cpu(rec->e_leaf_clusters) == 0) { memset(rec, 0, sizeof(struct ocfs2_extent_rec)); le16_add_cpu(&el->l_next_free_rec, -1); @@ -3152,15 +3189,15 @@ find_tail_record: if (new_edge == 0) goto delete; - rec->e_clusters = cpu_to_le32(new_edge); - le32_add_cpu(&rec->e_clusters, + rec->e_int_clusters = cpu_to_le32(new_edge); + le32_add_cpu(&rec->e_int_clusters, -le32_to_cpu(rec->e_cpos)); /* * A deleted child record should have been * caught above. */ - BUG_ON(le32_to_cpu(rec->e_clusters) == 0); + BUG_ON(le32_to_cpu(rec->e_int_clusters) == 0); } delete: @@ -3173,7 +3210,7 @@ delete: mlog(0, "extent list container %llu, after: record %d: " "(%u, %u, %llu), next = %u.\n", (unsigned long long)bh->b_blocknr, i, - le32_to_cpu(rec->e_cpos), le32_to_cpu(rec->e_clusters), + le32_to_cpu(rec->e_cpos), ocfs2_rec_clusters(el, rec), (unsigned long long)le64_to_cpu(rec->e_blkno), le16_to_cpu(el->l_next_free_rec)); @@ -3195,7 +3232,7 @@ delete: ocfs2_remove_from_cache(inode, bh); - BUG_ON(le32_to_cpu(el->l_recs[0].e_clusters)); + BUG_ON(ocfs2_rec_clusters(el, &el->l_recs[0])); BUG_ON(le32_to_cpu(el->l_recs[0].e_cpos)); BUG_ON(le64_to_cpu(el->l_recs[0].e_blkno)); @@ -3283,7 +3320,7 @@ static int ocfs2_do_truncate(struct ocfs2_super *osb, * Lower levels depend on this never happening, but it's best * to check it up here before changing the tree. */ - if (el->l_tree_depth && ocfs2_is_empty_extent(&el->l_recs[0])) { + if (el->l_tree_depth && el->l_recs[0].e_int_clusters == 0) { ocfs2_error(inode->i_sb, "Inode %lu has an empty extent record, depth %u\n", inode->i_ino, le16_to_cpu(el->l_tree_depth)); @@ -3644,13 +3681,13 @@ start: i = le16_to_cpu(el->l_next_free_rec) - 1; range = le32_to_cpu(el->l_recs[i].e_cpos) + - le32_to_cpu(el->l_recs[i].e_clusters); + ocfs2_rec_clusters(el, &el->l_recs[i]); if (i == 0 && ocfs2_is_empty_extent(&el->l_recs[i])) { clusters_to_del = 0; } else if (le32_to_cpu(el->l_recs[i].e_cpos) >= new_highest_cpos) { - clusters_to_del = le32_to_cpu(el->l_recs[i].e_clusters); + clusters_to_del = ocfs2_rec_clusters(el, &el->l_recs[i]); } else if (range > new_highest_cpos) { - clusters_to_del = (le32_to_cpu(el->l_recs[i].e_clusters) + + clusters_to_del = (ocfs2_rec_clusters(el, &el->l_recs[i]) + le32_to_cpu(el->l_recs[i].e_cpos)) - new_highest_cpos; } else { diff --git a/fs/ocfs2/alloc.h b/fs/ocfs2/alloc.h index 3cb39cd5e478..fbcb5934a081 100644 --- a/fs/ocfs2/alloc.h +++ b/fs/ocfs2/alloc.h @@ -85,4 +85,23 @@ int ocfs2_commit_truncate(struct ocfs2_super *osb, int ocfs2_find_leaf(struct inode *inode, struct ocfs2_extent_list *root_el, u32 cpos, struct buffer_head **leaf_bh); +/* + * Helper function to look at the # of clusters in an extent record. + */ +static inline unsigned int ocfs2_rec_clusters(struct ocfs2_extent_list *el, + struct ocfs2_extent_rec *rec) +{ + /* + * Cluster count in extent records is slightly different + * between interior nodes and leaf nodes. This is to support + * unwritten extents which need a flags field in leaf node + * records, thus shrinking the available space for a clusters + * field. + */ + if (el->l_tree_depth) + return le32_to_cpu(rec->e_int_clusters); + else + return le16_to_cpu(rec->e_leaf_clusters); +} + #endif /* OCFS2_ALLOC_H */ diff --git a/fs/ocfs2/extent_map.c b/fs/ocfs2/extent_map.c index 937c2722b753..ea0ce41d4193 100644 --- a/fs/ocfs2/extent_map.c +++ b/fs/ocfs2/extent_map.c @@ -50,13 +50,15 @@ static int ocfs2_search_extent_list(struct ocfs2_extent_list *el, int ret = -1; int i; struct ocfs2_extent_rec *rec; - u32 rec_end, rec_start; + u32 rec_end, rec_start, clusters; for(i = 0; i < le16_to_cpu(el->l_next_free_rec); i++) { rec = &el->l_recs[i]; rec_start = le32_to_cpu(rec->e_cpos); - rec_end = rec_start + le32_to_cpu(rec->e_clusters); + clusters = ocfs2_rec_clusters(el, rec); + + rec_end = rec_start + clusters; if (v_cluster >= rec_start && v_cluster < rec_end) { ret = i; @@ -98,6 +100,15 @@ int ocfs2_get_clusters(struct inode *inode, u32 v_cluster, eb = (struct ocfs2_extent_block *) eb_bh->b_data; el = &eb->h_list; + + if (el->l_tree_depth) { + ocfs2_error(inode->i_sb, + "Inode %lu has non zero tree depth in " + "leaf block %llu\n", inode->i_ino, + (unsigned long long)eb_bh->b_blocknr); + ret = -EROFS; + goto out; + } } i = ocfs2_search_extent_list(el, v_cluster); @@ -118,7 +129,7 @@ int ocfs2_get_clusters(struct inode *inode, u32 v_cluster, ocfs2_error(inode->i_sb, "Inode %lu has bad extent " "record (%u, %u, 0)", inode->i_ino, le32_to_cpu(rec->e_cpos), - le32_to_cpu(rec->e_clusters)); + ocfs2_rec_clusters(el, rec)); ret = -EROFS; goto out; } @@ -130,7 +141,7 @@ int ocfs2_get_clusters(struct inode *inode, u32 v_cluster, *p_cluster = *p_cluster + coff; if (num_clusters) - *num_clusters = le32_to_cpu(rec->e_clusters) - coff; + *num_clusters = ocfs2_rec_clusters(el, rec) - coff; } out: diff --git a/fs/ocfs2/file.c b/fs/ocfs2/file.c index f516619a3744..36176018b4b4 100644 --- a/fs/ocfs2/file.c +++ b/fs/ocfs2/file.c @@ -1127,7 +1127,6 @@ static int ocfs2_check_range_for_holes(struct inode *inode, loff_t pos, size_t count) { int ret = 0; - unsigned int extent_flags; u32 cpos, clusters, extent_len, phys_cpos; struct super_block *sb = inode->i_sb; @@ -1135,14 +1134,13 @@ static int ocfs2_check_range_for_holes(struct inode *inode, loff_t pos, clusters = ocfs2_clusters_for_bytes(sb, pos + count) - cpos; while (clusters) { - ret = ocfs2_get_clusters(inode, cpos, &phys_cpos, &extent_len, - &extent_flags); + ret = ocfs2_get_clusters(inode, cpos, &phys_cpos, &extent_len); if (ret < 0) { mlog_errno(ret); goto out; } - if (phys_cpos == 0 || (extent_flags & OCFS2_EXT_UNWRITTEN)) { + if (phys_cpos == 0) { ret = 1; break; } diff --git a/fs/ocfs2/journal.h b/fs/ocfs2/journal.h index d026b4f27757..3db5de4506da 100644 --- a/fs/ocfs2/journal.h +++ b/fs/ocfs2/journal.h @@ -390,7 +390,7 @@ static inline int ocfs2_calc_tree_trunc_credits(struct super_block *sb, /* We may be deleting metadata blocks, so metadata alloc dinode + one desc. block for each possible delete. */ if (tree_depth && next_free == 1 && - le32_to_cpu(last_el->l_recs[i].e_clusters) == clusters_to_del) + ocfs2_rec_clusters(last_el, &last_el->l_recs[i]) == clusters_to_del) credits += 1 + tree_depth; /* update to the truncate log. */ diff --git a/fs/ocfs2/ocfs2_fs.h b/fs/ocfs2/ocfs2_fs.h index f0101974f4f9..71306479c68f 100644 --- a/fs/ocfs2/ocfs2_fs.h +++ b/fs/ocfs2/ocfs2_fs.h @@ -155,6 +155,12 @@ #define OCFS2_FL_VISIBLE (0x000100FF) /* User visible flags */ #define OCFS2_FL_MODIFIABLE (0x000100FF) /* User modifiable flags */ +/* + * Extent record flags (e_node.leaf.flags) + */ +#define OCFS2_EXT_UNWRITTEN (0x01) /* Extent is allocated but + * unwritten */ + /* * ioctl commands */ @@ -283,10 +289,21 @@ static unsigned char ocfs2_type_by_mode[S_IFMT >> S_SHIFT] = { /* * On disk extent record for OCFS2 * It describes a range of clusters on disk. + * + * Length fields are divided into interior and leaf node versions. + * This leaves room for a flags field (OCFS2_EXT_*) in the leaf nodes. */ struct ocfs2_extent_rec { /*00*/ __le32 e_cpos; /* Offset into the file, in clusters */ - __le32 e_clusters; /* Clusters covered by this extent */ + union { + __le32 e_int_clusters; /* Clusters covered by all children */ + struct { + __le16 e_leaf_clusters; /* Clusters covered by this + extent */ + __u8 e_reserved1; + __u8 e_flags; /* Extent flags */ + }; + }; __le64 e_blkno; /* Physical disk offset, in blocks */ /*10*/ }; -- cgit From 49cb8d2d496ce06869ccca2ab368ed6b0b5b979d Mon Sep 17 00:00:00 2001 From: Mark Fasheh Date: Fri, 9 Mar 2007 16:21:46 -0800 Subject: ocfs2: Read from an unwritten extent returns zeros Return an optional extent flags field from our lookup functions and wire up callers to treat unwritten regions as holes for the purpose of returning zeros to the user. Signed-off-by: Mark Fasheh --- fs/ocfs2/alloc.c | 11 +++++++---- fs/ocfs2/aops.c | 21 ++++++++++++++------- fs/ocfs2/dir.c | 2 +- fs/ocfs2/extent_map.c | 14 +++++++++++--- fs/ocfs2/extent_map.h | 4 ++-- fs/ocfs2/file.c | 6 ++++-- fs/ocfs2/inode.c | 3 ++- fs/ocfs2/journal.c | 2 +- fs/ocfs2/namei.c | 3 ++- fs/ocfs2/slot_map.c | 2 +- 10 files changed, 45 insertions(+), 23 deletions(-) (limited to 'fs/ocfs2/alloc.c') diff --git a/fs/ocfs2/alloc.c b/fs/ocfs2/alloc.c index 0eab0d328289..412a2888a3ed 100644 --- a/fs/ocfs2/alloc.c +++ b/fs/ocfs2/alloc.c @@ -3487,6 +3487,7 @@ static int ocfs2_grab_eof_pages(struct inode *inode, loff_t isize, struct page * { int i, numpages = 0, ret = 0; unsigned int csize = OCFS2_SB(inode->i_sb)->s_clustersize; + unsigned int ext_flags; struct super_block *sb = inode->i_sb; struct address_space *mapping = inode->i_mapping; unsigned long index; @@ -3499,7 +3500,7 @@ static int ocfs2_grab_eof_pages(struct inode *inode, loff_t isize, struct page * goto out; ret = ocfs2_extent_map_get_blocks(inode, isize >> sb->s_blocksize_bits, - phys, NULL); + phys, NULL, &ext_flags); if (ret) { mlog_errno(ret); goto out; @@ -3509,6 +3510,11 @@ static int ocfs2_grab_eof_pages(struct inode *inode, loff_t isize, struct page * if (*phys == 0) goto out; + /* Tail is marked as unwritten, we can count on write to zero + * in that case. */ + if (ext_flags & OCFS2_EXT_UNWRITTEN) + goto out; + next_cluster_bytes = ocfs2_align_bytes_to_clusters(inode->i_sb, isize); index = isize >> PAGE_CACHE_SHIFT; do { @@ -3579,9 +3585,6 @@ int ocfs2_zero_tail_for_truncate(struct inode *inode, handle_t *handle, goto out; } - /* - * Truncate on an i_size boundary - nothing more to do. - */ if (numpages == 0) goto out; diff --git a/fs/ocfs2/aops.c b/fs/ocfs2/aops.c index 014f4f52809c..eb67c902b002 100644 --- a/fs/ocfs2/aops.c +++ b/fs/ocfs2/aops.c @@ -137,6 +137,7 @@ static int ocfs2_get_block(struct inode *inode, sector_t iblock, struct buffer_head *bh_result, int create) { int err = 0; + unsigned int ext_flags; u64 p_blkno, past_eof; struct ocfs2_super *osb = OCFS2_SB(inode->i_sb); @@ -153,7 +154,8 @@ static int ocfs2_get_block(struct inode *inode, sector_t iblock, goto bail; } - err = ocfs2_extent_map_get_blocks(inode, iblock, &p_blkno, NULL); + err = ocfs2_extent_map_get_blocks(inode, iblock, &p_blkno, NULL, + &ext_flags); if (err) { mlog(ML_ERROR, "Error %d from get_blocks(0x%p, %llu, 1, " "%llu, NULL)\n", err, inode, (unsigned long long)iblock, @@ -171,7 +173,8 @@ static int ocfs2_get_block(struct inode *inode, sector_t iblock, "ino %lu, iblock %llu\n", inode->i_ino, (unsigned long long)iblock); - if (p_blkno) + /* Treat the unwritten extent as a hole for zeroing purposes. */ + if (p_blkno && !(ext_flags & OCFS2_EXT_UNWRITTEN)) map_bh(bh_result, inode->i_sb, p_blkno); if (!ocfs2_sparse_alloc(osb)) { @@ -396,7 +399,7 @@ static sector_t ocfs2_bmap(struct address_space *mapping, sector_t block) down_read(&OCFS2_I(inode)->ip_alloc_sem); } - err = ocfs2_extent_map_get_blocks(inode, block, &p_blkno, NULL); + err = ocfs2_extent_map_get_blocks(inode, block, &p_blkno, NULL, NULL); if (!INODE_JOURNAL(inode)) { up_read(&OCFS2_I(inode)->ip_alloc_sem); @@ -438,6 +441,7 @@ static int ocfs2_direct_IO_get_blocks(struct inode *inode, sector_t iblock, int ret; u64 p_blkno, inode_blocks; int contig_blocks; + unsigned int ext_flags; unsigned char blocksize_bits = inode->i_sb->s_blocksize_bits; unsigned long max_blocks = bh_result->b_size >> inode->i_blkbits; @@ -458,7 +462,7 @@ static int ocfs2_direct_IO_get_blocks(struct inode *inode, sector_t iblock, /* This figures out the size of the next contiguous block, and * our logical offset */ ret = ocfs2_extent_map_get_blocks(inode, iblock, &p_blkno, - &contig_blocks); + &contig_blocks, &ext_flags); if (ret) { mlog(ML_ERROR, "get_blocks() failed iblock=%llu\n", (unsigned long long)iblock); @@ -478,8 +482,10 @@ static int ocfs2_direct_IO_get_blocks(struct inode *inode, sector_t iblock, /* * get_more_blocks() expects us to describe a hole by clearing * the mapped bit on bh_result(). + * + * Consider an unwritten extent as a hole. */ - if (p_blkno) + if (p_blkno && !(ext_flags & OCFS2_EXT_UNWRITTEN)) map_bh(bh_result, inode->i_sb, p_blkno); else { /* @@ -1111,7 +1117,8 @@ static ssize_t ocfs2_write(struct file *file, u32 phys, handle_t *handle, } } - ret = ocfs2_extent_map_get_blocks(inode, v_blkno, &p_blkno, NULL); + ret = ocfs2_extent_map_get_blocks(inode, v_blkno, &p_blkno, NULL, + NULL); if (ret < 0) { /* @@ -1215,7 +1222,7 @@ ssize_t ocfs2_buffered_write_cluster(struct file *file, loff_t pos, */ down_write(&OCFS2_I(inode)->ip_alloc_sem); - ret = ocfs2_get_clusters(inode, wc.w_cpos, &phys, NULL); + ret = ocfs2_get_clusters(inode, wc.w_cpos, &phys, NULL, NULL); if (ret) { mlog_errno(ret); goto out_meta; diff --git a/fs/ocfs2/dir.c b/fs/ocfs2/dir.c index c91490670ffa..8d22e1e4a88d 100644 --- a/fs/ocfs2/dir.c +++ b/fs/ocfs2/dir.c @@ -379,7 +379,7 @@ int ocfs2_do_extend_dir(struct super_block *sb, status = ocfs2_extent_map_get_blocks(dir, (dir->i_blocks >> (sb->s_blocksize_bits - 9)), - &p_blkno, NULL); + &p_blkno, NULL, NULL); if (status < 0) { mlog_errno(status); goto bail; diff --git a/fs/ocfs2/extent_map.c b/fs/ocfs2/extent_map.c index ea0ce41d4193..eef6c1887708 100644 --- a/fs/ocfs2/extent_map.c +++ b/fs/ocfs2/extent_map.c @@ -70,9 +70,11 @@ static int ocfs2_search_extent_list(struct ocfs2_extent_list *el, } int ocfs2_get_clusters(struct inode *inode, u32 v_cluster, - u32 *p_cluster, u32 *num_clusters) + u32 *p_cluster, u32 *num_clusters, + unsigned int *extent_flags) { int ret, i; + unsigned int flags = 0; struct buffer_head *di_bh = NULL; struct buffer_head *eb_bh = NULL; struct ocfs2_dinode *di; @@ -142,8 +144,13 @@ int ocfs2_get_clusters(struct inode *inode, u32 v_cluster, if (num_clusters) *num_clusters = ocfs2_rec_clusters(el, rec) - coff; + + flags = rec->e_flags; } + if (extent_flags) + *extent_flags = flags; + out: brelse(di_bh); brelse(eb_bh); @@ -155,7 +162,7 @@ out: * all while the map is in the process of being updated. */ int ocfs2_extent_map_get_blocks(struct inode *inode, u64 v_blkno, u64 *p_blkno, - int *ret_count) + int *ret_count, unsigned int *extent_flags) { int ret; int bpc = ocfs2_clusters_to_blocks(inode->i_sb, 1); @@ -164,7 +171,8 @@ int ocfs2_extent_map_get_blocks(struct inode *inode, u64 v_blkno, u64 *p_blkno, cpos = ocfs2_blocks_to_clusters(inode->i_sb, v_blkno); - ret = ocfs2_get_clusters(inode, cpos, &p_cluster, &num_clusters); + ret = ocfs2_get_clusters(inode, cpos, &p_cluster, &num_clusters, + extent_flags); if (ret) { mlog_errno(ret); goto out; diff --git a/fs/ocfs2/extent_map.h b/fs/ocfs2/extent_map.h index 625d0ee5e04a..0031c59c347f 100644 --- a/fs/ocfs2/extent_map.h +++ b/fs/ocfs2/extent_map.h @@ -26,8 +26,8 @@ #define _EXTENT_MAP_H int ocfs2_get_clusters(struct inode *inode, u32 v_cluster, u32 *p_cluster, - u32 *num_clusters); + u32 *num_clusters, unsigned int *extent_flags); int ocfs2_extent_map_get_blocks(struct inode *inode, u64 v_blkno, u64 *p_blkno, - int *ret_count); + int *ret_count, unsigned int *extent_flags); #endif /* _EXTENT_MAP_H */ diff --git a/fs/ocfs2/file.c b/fs/ocfs2/file.c index 36176018b4b4..f516619a3744 100644 --- a/fs/ocfs2/file.c +++ b/fs/ocfs2/file.c @@ -1127,6 +1127,7 @@ static int ocfs2_check_range_for_holes(struct inode *inode, loff_t pos, size_t count) { int ret = 0; + unsigned int extent_flags; u32 cpos, clusters, extent_len, phys_cpos; struct super_block *sb = inode->i_sb; @@ -1134,13 +1135,14 @@ static int ocfs2_check_range_for_holes(struct inode *inode, loff_t pos, clusters = ocfs2_clusters_for_bytes(sb, pos + count) - cpos; while (clusters) { - ret = ocfs2_get_clusters(inode, cpos, &phys_cpos, &extent_len); + ret = ocfs2_get_clusters(inode, cpos, &phys_cpos, &extent_len, + &extent_flags); if (ret < 0) { mlog_errno(ret); goto out; } - if (phys_cpos == 0) { + if (phys_cpos == 0 || (extent_flags & OCFS2_EXT_UNWRITTEN)) { ret = 1; break; } diff --git a/fs/ocfs2/inode.c b/fs/ocfs2/inode.c index 78c99b5050df..310049bf7f6b 100644 --- a/fs/ocfs2/inode.c +++ b/fs/ocfs2/inode.c @@ -1105,7 +1105,8 @@ struct buffer_head *ocfs2_bread(struct inode *inode, return NULL; } - tmperr = ocfs2_extent_map_get_blocks(inode, block, &p_blkno, NULL); + tmperr = ocfs2_extent_map_get_blocks(inode, block, &p_blkno, NULL, + NULL); if (tmperr < 0) { mlog_errno(tmperr); goto fail; diff --git a/fs/ocfs2/journal.c b/fs/ocfs2/journal.c index 2e2e04fe9738..db77e0996bb7 100644 --- a/fs/ocfs2/journal.c +++ b/fs/ocfs2/journal.c @@ -670,7 +670,7 @@ static int ocfs2_force_read_journal(struct inode *inode) (inode->i_blocks >> (inode->i_sb->s_blocksize_bits - 9))) { status = ocfs2_extent_map_get_blocks(inode, v_blkno, - &p_blkno, &p_blocks); + &p_blkno, &p_blocks, NULL); if (status < 0) { mlog_errno(status); goto bail; diff --git a/fs/ocfs2/namei.c b/fs/ocfs2/namei.c index 5755e0748256..395859edb51f 100644 --- a/fs/ocfs2/namei.c +++ b/fs/ocfs2/namei.c @@ -1511,7 +1511,8 @@ static int ocfs2_create_symlink_data(struct ocfs2_super *osb, goto bail; } - status = ocfs2_extent_map_get_blocks(inode, 0, &p_blkno, &p_blocks); + status = ocfs2_extent_map_get_blocks(inode, 0, &p_blkno, &p_blocks, + NULL); if (status < 0) { mlog_errno(status); goto bail; diff --git a/fs/ocfs2/slot_map.c b/fs/ocfs2/slot_map.c index f4416e7330e1..d921a28329dc 100644 --- a/fs/ocfs2/slot_map.c +++ b/fs/ocfs2/slot_map.c @@ -197,7 +197,7 @@ int ocfs2_init_slot_info(struct ocfs2_super *osb) goto bail; } - status = ocfs2_extent_map_get_blocks(inode, 0ULL, &blkno, NULL); + status = ocfs2_extent_map_get_blocks(inode, 0ULL, &blkno, NULL, NULL); if (status < 0) { mlog_errno(status); goto bail; -- cgit From 83418978827324918a8cd25ce5227312de1d4468 Mon Sep 17 00:00:00 2001 From: Mark Fasheh Date: Mon, 23 Apr 2007 18:53:12 -0700 Subject: ocfs2: Cache extent records The extent map code was ripped out earlier because of an inability to deal with holes. This patch adds back a simpler caching scheme requiring far less code. Our old extent map caching was designed back when meta data block caching in Ocfs2 didn't work very well, resulting in many disk reads. These days our metadata caching is much better, resulting in no un-necessary disk reads. As a result, extent caching doesn't have to be as fancy, nor does it have to cache as many extents. Keeping the last 3 extents seen should be sufficient to give us a small performance boost on some streaming workloads. Signed-off-by: Mark Fasheh --- fs/ocfs2/alloc.c | 5 + fs/ocfs2/dlmglue.c | 2 + fs/ocfs2/extent_map.c | 255 ++++++++++++++++++++++++++++++++++++++++++++++++++ fs/ocfs2/extent_map.h | 20 ++++ fs/ocfs2/inode.c | 2 + fs/ocfs2/inode.h | 4 + fs/ocfs2/super.c | 1 + 7 files changed, 289 insertions(+) (limited to 'fs/ocfs2/alloc.c') diff --git a/fs/ocfs2/alloc.c b/fs/ocfs2/alloc.c index 412a2888a3ed..a0c8667caa72 100644 --- a/fs/ocfs2/alloc.c +++ b/fs/ocfs2/alloc.c @@ -2417,6 +2417,8 @@ out_add: status = ocfs2_do_insert_extent(inode, handle, fe_bh, &rec, &insert); if (status < 0) mlog_errno(status); + else + ocfs2_extent_map_insert_rec(inode, &rec); bail: if (bh) @@ -3640,6 +3642,9 @@ int ocfs2_commit_truncate(struct ocfs2_super *osb, mlog_errno(status); goto bail; } + + ocfs2_extent_map_trunc(inode, new_highest_cpos); + start: /* * Check that we still have allocation to delete. diff --git a/fs/ocfs2/dlmglue.c b/fs/ocfs2/dlmglue.c index 43267eea3538..27e43b0c0eae 100644 --- a/fs/ocfs2/dlmglue.c +++ b/fs/ocfs2/dlmglue.c @@ -1613,6 +1613,8 @@ static int ocfs2_meta_lock_update(struct inode *inode, * for the inode metadata. */ ocfs2_metadata_cache_purge(inode); + ocfs2_extent_map_trunc(inode, 0); + if (ocfs2_meta_lvb_is_trustable(inode, lockres)) { mlog(0, "Trusting LVB on inode %llu\n", (unsigned long long)oi->ip_blkno); diff --git a/fs/ocfs2/extent_map.c b/fs/ocfs2/extent_map.c index f35e04f27f32..ba2b2ab1c6e4 100644 --- a/fs/ocfs2/extent_map.c +++ b/fs/ocfs2/extent_map.c @@ -38,6 +38,254 @@ #include "buffer_head_io.h" +/* + * The extent caching implementation is intentionally trivial. + * + * We only cache a small number of extents stored directly on the + * inode, so linear order operations are acceptable. If we ever want + * to increase the size of the extent map, then these algorithms must + * get smarter. + */ + +void ocfs2_extent_map_init(struct inode *inode) +{ + struct ocfs2_inode_info *oi = OCFS2_I(inode); + + oi->ip_extent_map.em_num_items = 0; + INIT_LIST_HEAD(&oi->ip_extent_map.em_list); +} + +static void __ocfs2_extent_map_lookup(struct ocfs2_extent_map *em, + unsigned int cpos, + struct ocfs2_extent_map_item **ret_emi) +{ + unsigned int range; + struct ocfs2_extent_map_item *emi; + + *ret_emi = NULL; + + list_for_each_entry(emi, &em->em_list, ei_list) { + range = emi->ei_cpos + emi->ei_clusters; + + if (cpos >= emi->ei_cpos && cpos < range) { + list_move(&emi->ei_list, &em->em_list); + + *ret_emi = emi; + break; + } + } +} + +static int ocfs2_extent_map_lookup(struct inode *inode, unsigned int cpos, + unsigned int *phys, unsigned int *len, + unsigned int *flags) +{ + unsigned int coff; + struct ocfs2_inode_info *oi = OCFS2_I(inode); + struct ocfs2_extent_map_item *emi; + + spin_lock(&oi->ip_lock); + + __ocfs2_extent_map_lookup(&oi->ip_extent_map, cpos, &emi); + if (emi) { + coff = cpos - emi->ei_cpos; + *phys = emi->ei_phys + coff; + if (len) + *len = emi->ei_clusters - coff; + if (flags) + *flags = emi->ei_flags; + } + + spin_unlock(&oi->ip_lock); + + if (emi == NULL) + return -ENOENT; + + return 0; +} + +/* + * Forget about all clusters equal to or greater than cpos. + */ +void ocfs2_extent_map_trunc(struct inode *inode, unsigned int cpos) +{ + struct list_head *p, *n; + struct ocfs2_extent_map_item *emi; + struct ocfs2_inode_info *oi = OCFS2_I(inode); + struct ocfs2_extent_map *em = &oi->ip_extent_map; + LIST_HEAD(tmp_list); + unsigned int range; + + spin_lock(&oi->ip_lock); + list_for_each_safe(p, n, &em->em_list) { + emi = list_entry(p, struct ocfs2_extent_map_item, ei_list); + + if (emi->ei_cpos >= cpos) { + /* Full truncate of this record. */ + list_move(&emi->ei_list, &tmp_list); + BUG_ON(em->em_num_items == 0); + em->em_num_items--; + continue; + } + + range = emi->ei_cpos + emi->ei_clusters; + if (range > cpos) { + /* Partial truncate */ + emi->ei_clusters = cpos - emi->ei_cpos; + } + } + spin_unlock(&oi->ip_lock); + + list_for_each_safe(p, n, &tmp_list) { + emi = list_entry(p, struct ocfs2_extent_map_item, ei_list); + list_del(&emi->ei_list); + kfree(emi); + } +} + +/* + * Is any part of emi2 contained within emi1 + */ +static int ocfs2_ei_is_contained(struct ocfs2_extent_map_item *emi1, + struct ocfs2_extent_map_item *emi2) +{ + unsigned int range1, range2; + + /* + * Check if logical start of emi2 is inside emi1 + */ + range1 = emi1->ei_cpos + emi1->ei_clusters; + if (emi2->ei_cpos >= emi1->ei_cpos && emi2->ei_cpos < range1) + return 1; + + /* + * Check if logical end of emi2 is inside emi1 + */ + range2 = emi2->ei_cpos + emi2->ei_clusters; + if (range2 > emi1->ei_cpos && range2 <= range1) + return 1; + + return 0; +} + +static void ocfs2_copy_emi_fields(struct ocfs2_extent_map_item *dest, + struct ocfs2_extent_map_item *src) +{ + dest->ei_cpos = src->ei_cpos; + dest->ei_phys = src->ei_phys; + dest->ei_clusters = src->ei_clusters; + dest->ei_flags = src->ei_flags; +} + +/* + * Try to merge emi with ins. Returns 1 if merge succeeds, zero + * otherwise. + */ +static int ocfs2_try_to_merge_extent_map(struct ocfs2_extent_map_item *emi, + struct ocfs2_extent_map_item *ins) +{ + /* + * Handle contiguousness + */ + if (ins->ei_phys == (emi->ei_phys + emi->ei_clusters) && + ins->ei_cpos == (emi->ei_cpos + emi->ei_clusters) && + ins->ei_flags == emi->ei_flags) { + emi->ei_clusters += ins->ei_clusters; + return 1; + } else if ((ins->ei_phys + ins->ei_clusters) == emi->ei_phys && + (ins->ei_cpos + ins->ei_clusters) == emi->ei_phys && + ins->ei_flags == emi->ei_flags) { + emi->ei_phys = ins->ei_phys; + emi->ei_cpos = ins->ei_cpos; + emi->ei_clusters += ins->ei_clusters; + return 1; + } + + /* + * Overlapping extents - this shouldn't happen unless we've + * split an extent to change it's flags. That is exceedingly + * rare, so there's no sense in trying to optimize it yet. + */ + if (ocfs2_ei_is_contained(emi, ins) || + ocfs2_ei_is_contained(ins, emi)) { + ocfs2_copy_emi_fields(emi, ins); + return 1; + } + + /* No merge was possible. */ + return 0; +} + +/* + * In order to reduce complexity on the caller, this insert function + * is intentionally liberal in what it will accept. + * + * The only rule is that the truncate call *must* be used whenever + * records have been deleted. This avoids inserting overlapping + * records with different physical mappings. + */ +void ocfs2_extent_map_insert_rec(struct inode *inode, + struct ocfs2_extent_rec *rec) +{ + struct ocfs2_inode_info *oi = OCFS2_I(inode); + struct ocfs2_extent_map *em = &oi->ip_extent_map; + struct ocfs2_extent_map_item *emi, *new_emi = NULL; + struct ocfs2_extent_map_item ins; + + ins.ei_cpos = le32_to_cpu(rec->e_cpos); + ins.ei_phys = ocfs2_blocks_to_clusters(inode->i_sb, + le64_to_cpu(rec->e_blkno)); + ins.ei_clusters = le16_to_cpu(rec->e_leaf_clusters); + ins.ei_flags = rec->e_flags; + +search: + spin_lock(&oi->ip_lock); + + list_for_each_entry(emi, &em->em_list, ei_list) { + if (ocfs2_try_to_merge_extent_map(emi, &ins)) { + list_move(&emi->ei_list, &em->em_list); + spin_unlock(&oi->ip_lock); + goto out; + } + } + + /* + * No item could be merged. + * + * Either allocate and add a new item, or overwrite the last recently + * inserted. + */ + + if (em->em_num_items < OCFS2_MAX_EXTENT_MAP_ITEMS) { + if (new_emi == NULL) { + spin_unlock(&oi->ip_lock); + + new_emi = kmalloc(sizeof(*new_emi), GFP_NOFS); + if (new_emi == NULL) + goto out; + + goto search; + } + + ocfs2_copy_emi_fields(new_emi, &ins); + list_add(&new_emi->ei_list, &em->em_list); + em->em_num_items++; + new_emi = NULL; + } else { + BUG_ON(list_empty(&em->em_list) || em->em_num_items == 0); + emi = list_entry(em->em_list.prev, + struct ocfs2_extent_map_item, ei_list); + list_move(&emi->ei_list, &em->em_list); + ocfs2_copy_emi_fields(emi, &ins); + } + + spin_unlock(&oi->ip_lock); + +out: + if (new_emi) + kfree(new_emi); +} + /* * Return the 1st index within el which contains an extent start * larger than v_cluster. @@ -174,6 +422,11 @@ int ocfs2_get_clusters(struct inode *inode, u32 v_cluster, struct ocfs2_extent_rec *rec; u32 coff; + ret = ocfs2_extent_map_lookup(inode, v_cluster, p_cluster, + num_clusters, extent_flags); + if (ret == 0) + goto out; + ret = ocfs2_read_block(OCFS2_SB(inode->i_sb), OCFS2_I(inode)->ip_blkno, &di_bh, OCFS2_BH_CACHED, inode); if (ret) { @@ -245,6 +498,8 @@ int ocfs2_get_clusters(struct inode *inode, u32 v_cluster, *num_clusters = ocfs2_rec_clusters(el, rec) - coff; flags = rec->e_flags; + + ocfs2_extent_map_insert_rec(inode, rec); } if (extent_flags) diff --git a/fs/ocfs2/extent_map.h b/fs/ocfs2/extent_map.h index 1d745e174afc..de91e3e41a22 100644 --- a/fs/ocfs2/extent_map.h +++ b/fs/ocfs2/extent_map.h @@ -25,6 +25,26 @@ #ifndef _EXTENT_MAP_H #define _EXTENT_MAP_H +struct ocfs2_extent_map_item { + unsigned int ei_cpos; + unsigned int ei_phys; + unsigned int ei_clusters; + unsigned int ei_flags; + + struct list_head ei_list; +}; + +#define OCFS2_MAX_EXTENT_MAP_ITEMS 3 +struct ocfs2_extent_map { + unsigned int em_num_items; + struct list_head em_list; +}; + +void ocfs2_extent_map_init(struct inode *inode); +void ocfs2_extent_map_trunc(struct inode *inode, unsigned int cluster); +void ocfs2_extent_map_insert_rec(struct inode *inode, + struct ocfs2_extent_rec *rec); + int ocfs2_get_clusters(struct inode *inode, u32 v_cluster, u32 *p_cluster, u32 *num_clusters, unsigned int *extent_flags); int ocfs2_extent_map_get_blocks(struct inode *inode, u64 v_blkno, u64 *p_blkno, diff --git a/fs/ocfs2/inode.c b/fs/ocfs2/inode.c index 4bfc98c70137..21a605079c62 100644 --- a/fs/ocfs2/inode.c +++ b/fs/ocfs2/inode.c @@ -1008,6 +1008,8 @@ void ocfs2_clear_inode(struct inode *inode) "Clear inode of %llu, inode has io markers\n", (unsigned long long)oi->ip_blkno); + ocfs2_extent_map_trunc(inode, 0); + status = ocfs2_drop_inode_locks(inode); if (status < 0) mlog_errno(status); diff --git a/fs/ocfs2/inode.h b/fs/ocfs2/inode.h index aa84353d0d19..03ae075869ee 100644 --- a/fs/ocfs2/inode.h +++ b/fs/ocfs2/inode.h @@ -26,6 +26,8 @@ #ifndef OCFS2_INODE_H #define OCFS2_INODE_H +#include "extent_map.h" + /* OCFS2 Inode Private Data */ struct ocfs2_inode_info { @@ -63,6 +65,8 @@ struct ocfs2_inode_info struct ocfs2_caching_info ip_metadata_cache; + struct ocfs2_extent_map ip_extent_map; + struct inode vfs_inode; }; diff --git a/fs/ocfs2/super.c b/fs/ocfs2/super.c index 6ab52351943a..5c9e8243691f 100644 --- a/fs/ocfs2/super.c +++ b/fs/ocfs2/super.c @@ -942,6 +942,7 @@ static void ocfs2_inode_init_once(void *data, oi->ip_flags = 0; oi->ip_open_count = 0; spin_lock_init(&oi->ip_lock); + ocfs2_extent_map_init(&oi->vfs_inode); INIT_LIST_HEAD(&oi->ip_io_markers); oi->ip_created_trans = 0; oi->ip_last_trans = 0; -- cgit