metadata alloc fix in machines which has PAGE_SIZE > CLUSTER_SIZE
Hi Mark/Joel,
I meet with some meta allocation bugs when I implement reflink these
days. And after some investigation, I think we should have the same problem when we have PAGE_SIZE > CLUSTER_SIZE. So I create a scenario today in one ppc box and try. the box panic as I expected. ;)
The scenario is that: Create a file with the disk layout like this(with bs=512, and cs=4K).
debugfs: stat 15151
Inode: 66072 Mode: 0644 Generation: 59969160 (0x3930e88) <snip> Tree Depth: 1 Count: 19 Next Free Rec: 2 ## Offset Clusters Block# 0 0 258 86365 1 258 66 86367 SubAlloc Bit: 21 SubAlloc Slot: 0 Blknum: 86365 Next Leaf: 86367 CRC32: N/A ECC: N/A Tree Depth: 0 Count: 28 Next Free Rec: 28 ## Offset Clusters Block# Flags 0 0 1 116696 0x0 <snip> 25 25 1 117096 0x0 26 256 1 117112 0x1 27 257 1 117120 0x0 SubAlloc Bit: 23 SubAlloc Slot: 0 Blknum: 86367 Next Leaf: 0 CRC32: N/A ECC: N/A Tree Depth: 0 Count: 28 Next Free Rec: 2 ## Offset Clusters Block# Flags 0 258 2 117128 0x1 1 260 64 117176 0x1
Please note the extent record from "26" to "0" of the next block are contiguous allocated with unwritten and then divide it by write to the 256 with 1 cluster.
Now if we try to write 40960 bytes at offset 256. We will panic. Why? The reason is that:
1. with ppc box, we have page_size=64K. So in one ocfs2_write_begin_no_lock we will try to handle 40960 bytes together.
2. in ocfs2_lock_allocators we will get that no metadata is need since the 2nd extent block has so many empty extent recs.
3. then write begin one cluster by one in ocfs2_write_cluster.
1) The 1st cluster(256) nothing special.
2) the 2nd (257), it will be merged with 256.
3) the 3rd (258), be merged with 256.
4) the 4th (259), be merged. Now 256-259 will be merged into 1 extent
rec, so the 2nd extent block will be removed. and we will get.
26 256 4 117112 0x0 27 260 64 117176 0x1
5) Now comes the 260, we need to split and call ocfs2_add_branch to
allocate a new block. But wait, we have no metadata reserved. So we panic here.
So my thought is that can we reuse the freed extent block? I guess we can. We just need to store the pointer of ocfs2_cached_dealloc_ctxt in ocfs2_alloc_context. So whenever we allocate a new metadata, we try to search ocfs2_cached_dealloc_ctxt first, if there is some, we use it directly and delete it from ocfs2_cached_dealloc_ctxt. The same can go for cluster allocation I guess although I don't know whether we have such case for clusters.
make sense?
btw, this is critical because we often meet with this type of issue in reflink(the 1st step delete a leaf extent block because of merge while the 2nd step want to create one because of merge while no metadata are reserved). And even worse, I met with a scenario that the process of delete/add goes for 6 times.
Regards,
Tao
PATCH 1/1 ocfs2: Reused freed extent block in b-tree operation.
Hi all,
This is the patch for the RFC. I have tested it in my ppc
box, it works OK.
In some b-tree operations we may have the chance that we haven't reserved any metadata at the beginning because we think we don't need. While the 1st operation free a extent block while the 2nd operation need one. Our current code can't handle this. So this patch try to re-use the freed extent block so that we can pass the scenario above. For more details about the bug, see
[RFC] metadata alloc fix in machines which has PAGE_SIZE > CLUSTER_SIZE
http://oss.oracle.com/pipermail/ocfs2-devel/2009-March/004185.html.
--- fs/ocfs2/alloc.c | 49 +++++++++++++++++++++++++++++++++++++++++++++++-- fs/ocfs2/alloc.h | 7 +++++++ fs/ocfs2/dir.c | 8 ++++---- fs/ocfs2/suballoc.c | 23 +++++++++++++++++++++++ fs/ocfs2/suballoc.h | 3 +++ fs/ocfs2/xattr.c | 6 +++--- 6 files changed, 87 insertions(+), 9 deletions(-)
fs/ocfs2/alloc.c +47 -2
@@ -915,7 +915,7 @@ static int ocfs2_create_new_meta_bhs(struct ocfs2_super *osb, struct buffer_head *bhs[]) {int count, status, i; -u16 suballoc_bit_start; +u16 slot, suballoc_bit_start;u32 num_got;u64 first_blkno;struct ocfs2_extent_block *eb;
@@ -928,6 +928,7 @@ static int ocfs2_create_new_meta_bhs(struct ocfs2_super *osb, handle, meta_ac, wanted - count, + &slot, &suballoc_bit_start, &num_got, &first_blkno);
@@ -958,7 +959,7 @@ static int ocfs2_create_new_meta_bhs(struct ocfs2_super *osb,strcpy (eb->h_signature,OCFS2_EXTENT_BLOCK_SIGNATURE ); eb->h_blkno =cpu_to_le64 (first_blkno); eb->h_fs_generation =cpu_to_le32 (osb->fs_generation); - eb->h_suballoc_slot =cpu_to_le16 (osb->slot_num); + eb->h_suballoc_slot =cpu_to_le16 (slot); eb->h_suballoc_bit =cpu_to_le16 (suballoc_bit_start); eb->h_list.l_count =cpu_to_le16 (ocfs2_extent_recs_per_eb (osb->sb));
@@ -4912,6 +4913,7 @@ static int __ocfs2_mark_extent_written(struct inode *inode,struct ocfs2_extent_rec *rec = &el->l_recs[split_index];struct ocfs2_merge_ctxt ctxt;struct ocfs2_extent_list *rightmost_el; +struct ocfs2_alloc_context local_meta_ac;if (!(rec->e_flags &OCFS2_EXT_UNWRITTEN )) { ret = -EIO ;
@@ -4964,6 +4966,17 @@ static int __ocfs2_mark_extent_written(struct inode *inode, split_index, ctxt.c_contig_type, ctxt.c_has_empty_extent, ctxt.c_split_covers_rec); +/* +* init dealloc in meta_ac here so that we can reuse the freed extent +* block in case. +* If the caller doesn't give us a meta_ac, we just fake one and add +* dealloc in it. +*/ +if (!meta_ac) { +memset (&local_meta_ac,0 ,sizeof (local_meta_ac)); + meta_ac = &local_meta_ac; + } + meta_ac->dealloc = dealloc;if (ctxt.c_contig_type ==CONTIG_NONE ) {if (ctxt.c_split_covers_rec) ret = ocfs2_replace_extent_rec(inode, handle,
@@ -6172,6 +6185,38 @@ int ocfs2_cache_cluster_dealloc(struct ocfs2_cached_dealloc_ctxt *ctxt,return ret; } +int ocfs2_claim_bit_from_dealloc (struct ocfs2_cached_dealloc_ctxt *ctxt, +u16 *slot,u16 *suballoc_bit, +unsigned int *num_bits,u64 *blkno) +{ +struct ocfs2_per_slot_free_list *fl = ctxt->c_first_suballocator; +struct ocfs2_cached_block_free *tmp; + +if (!fl || !fl->f_first) +return -ENOSPC ; + + tmp = fl->f_first->free_next; + + *slot = fl->f_slot; + *suballoc_bit = fl->f_first->free_bit; + *blkno = fl->f_first->free_blk; + *num_bits =1 ; + +mlog (0 ,"claim blkno %llu suballoc_bit %u, slot %u\n" , + (unsigned long long )*blkno, *suballoc_bit, *slot); + +kfree (fl->f_first); + fl->f_first = tmp; + +/* Free the suballocator if there is none. */ +if (!fl->f_first) { + ctxt->c_first_suballocator = fl->f_next_suballocator; +kfree (fl); + } + +return 0 ; +} +static int ocfs2_free_cached_clusters (struct ocfs2_super *osb,struct ocfs2_cached_block_free *head) {
fs/ocfs2/alloc.h +7 -0
@@ -195,10 +195,17 @@ static inline void ocfs2_init_dealloc_ctxt(struct ocfs2_cached_dealloc_ctxt *c) }int ocfs2_cache_cluster_dealloc (struct ocfs2_cached_dealloc_ctxt *ctxt,u64 blkno,unsigned int bit); +static inline int ocfs2_dealloc_has_block (struct ocfs2_cached_dealloc_ctxt *c) +{ +return c->c_first_suballocator !=NULL ; +}static inline int ocfs2_dealloc_has_cluster (struct ocfs2_cached_dealloc_ctxt *c) {return c->c_global_allocator !=NULL ; } +int ocfs2_claim_bit_from_dealloc (struct ocfs2_cached_dealloc_ctxt *ctxt, +u16 *slot,u16 *suballoc_bit, +unsigned int *num_bits,u64 *blkno);int ocfs2_run_deallocs (struct ocfs2_super *osb,struct ocfs2_cached_dealloc_ctxt *ctxt);
fs/ocfs2/dir.c +4 -4
@@ -2394,7 +2394,7 @@ static int ocfs2_dx_dir_attach_index(struct ocfs2_super *osb, {int ret;struct ocfs2_dinode *di = (struct ocfs2_dinode *) di_bh->b_data; -u16 dr_suballoc_bit; +u16 slot, dr_suballoc_bit;u64 dr_blkno;unsigned int num_bits;struct buffer_head *dx_root_bh =NULL ;
@@ -2402,8 +2402,8 @@ static int ocfs2_dx_dir_attach_index(struct ocfs2_super *osb,struct ocfs2_dir_block_trailer *trailer =ocfs2_trailer_from_bh (dirdata_bh, dir->i_sb); - ret =ocfs2_claim_metadata (osb, handle, meta_ac,1 , &dr_suballoc_bit, - &num_bits, &dr_blkno); + ret =ocfs2_claim_metadata (osb, handle, meta_ac,1 , &slot, + &dr_suballoc_bit, &num_bits, &dr_blkno);if (ret) {mlog_errno (ret); goto out;
@@ -2430,7 +2430,7 @@ static int ocfs2_dx_dir_attach_index(struct ocfs2_super *osb, dx_root = (struct ocfs2_dx_root_block *)dx_root_bh->b_data;memset (dx_root,0 , osb->sb->s_blocksize);strcpy (dx_root->dr_signature,OCFS2_DX_ROOT_SIGNATURE ); - dx_root->dr_suballoc_slot =cpu_to_le16 (osb->slot_num); + dx_root->dr_suballoc_slot =cpu_to_le16 (slot); dx_root->dr_suballoc_bit =cpu_to_le16 (dr_suballoc_bit); dx_root->dr_fs_generation =cpu_to_le32 (osb->fs_generation); dx_root->dr_blkno =cpu_to_le64 (dr_blkno);
fs/ocfs2/suballoc.c +23 -0
@@ -1618,6 +1618,7 @@ int ocfs2_claim_metadata(struct ocfs2_super *osb,handle_t *handle, struct ocfs2_alloc_context *ac, u32 bits_wanted, + u16 *slot, u16 *suballoc_bit_start, unsigned int *num_bits, u64 *blkno_start)
@@ -1626,6 +1627,27 @@ int ocfs2_claim_metadata(struct ocfs2_super *osb,u64 bg_blkno;BUG_ON (!ac); + +/* +* If there is no space reserved in ac, check whether we have +* free some before in dealloc. If yes, allocate one form it. +*/ +if (ac->ac_bits_wanted < (ac->ac_bits_given + bits_wanted)) { +mlog (0 ,"alloc context doesn't have enough meta data reserved. " +"It has %d, we need %u\n" , + ac->ac_bits_given - ac->ac_bits_given, bits_wanted); +if (ac->dealloc &&ocfs2_dealloc_has_block (ac->dealloc)) { + status =ocfs2_claim_bit_from_dealloc (ac->dealloc, + slot, + suballoc_bit_start, + num_bits, + blkno_start); +if (!status) + goto bail; +/*fail through, so that it will BUG out. */ + } + } +BUG_ON (ac->ac_bits_wanted < (ac->ac_bits_given + bits_wanted));BUG_ON (ac->ac_which !=OCFS2_AC_USE_META );
@@ -1643,6 +1665,7 @@ int ocfs2_claim_metadata(struct ocfs2_super *osb, }atomic_inc (&osb->alloc_stats.bg_allocs); + *slot = ac->ac_alloc_slot; *blkno_start = bg_blkno + (u64) *suballoc_bit_start; ac->ac_bits_given += (*num_bits); status =0 ;
fs/ocfs2/suballoc.h +3 -0
@@ -34,6 +34,7 @@ typedef int (group_search_t)(struct inode *, u16 *, /* *bit_off */ u16 *); /* *bits_found */ +struct ocfs2_cached_dealloc_ctxt ;struct ocfs2_alloc_context {struct inode *ac_inode;/* which bitmap are we allocating from? */ struct buffer_head *ac_bh;/* file entry bh */
@@ -54,6 +55,7 @@ struct ocfs2_alloc_context {u64 ac_last_group;u64 ac_max_block;/* Highest block number to allocate. 0 is is the same as ~0 - unlimited */ +struct ocfs2_cached_dealloc_ctxt *dealloc; };void ocfs2_free_alloc_context (struct ocfs2_alloc_context *ac);
@@ -83,6 +85,7 @@ int ocfs2_claim_metadata(struct ocfs2_super *osb,handle_t *handle, struct ocfs2_alloc_context *ac, u32 bits_wanted, + u16 *slot, u16 *suballoc_bit_start, u32 *num_bits, u64 *blkno_start);
fs/ocfs2/xattr.c +3 -3
@@ -2098,7 +2098,7 @@ static int ocfs2_xattr_block_set(struct inode *inode,struct ocfs2_dinode *di = (struct ocfs2_dinode *)xs->inode_bh->b_data;handle_t *handle = ctxt->handle;struct ocfs2_xattr_block *xblk =NULL ; -u16 suballoc_bit_start; +u16 slot, suballoc_bit_start;u32 num_got;u64 first_blkno;int ret;
@@ -2112,7 +2112,7 @@ static int ocfs2_xattr_block_set(struct inode *inode, } ret =ocfs2_claim_metadata (osb, handle, ctxt->meta_ac,1 , - &suballoc_bit_start, &num_got, + &slot, &suballoc_bit_start, &num_got, &first_blkno);if (ret <0 ) {mlog_errno (ret);
@@ -2134,7 +2134,7 @@ static int ocfs2_xattr_block_set(struct inode *inode, xblk = (struct ocfs2_xattr_block *)new_bh->b_data;memset (xblk,0 , inode->i_sb->s_blocksize);strcpy ((void *)xblk,OCFS2_XATTR_BLOCK_SIGNATURE ); - xblk->xb_suballoc_slot =cpu_to_le16 (osb->slot_num); + xblk->xb_suballoc_slot =cpu_to_le16 (slot); xblk->xb_suballoc_bit =cpu_to_le16 (suballoc_bit_start); xblk->xb_fs_generation =cpu_to_le32 (osb->fs_generation); xblk->xb_blkno =cpu_to_le64 (first_blkno);
Signature · 1 line
1.6.2.rc2.16.gf474c
PATCH 1/1 ocfs2: Reused freed extent block in b-tree operation.
Quoted 11 lines · Tao Ma
Hi all,
This is the patch for the RFC. I have tested it in my ppc
box, it works OK.In some b-tree operations we may have the chance that we haven't reserved any metadata at the beginning because we think we don't need. While the 1st operation free a extent block while the 2nd operation need one. Our current code can't handle this. So this patch try to re-use the freed extent block so that we can pass the scenario above. For more details about the bug, see
Quoted 4 lines
[RFC] metadata alloc fix in machines which has
PAGE_SIZE>CLUSTER_SIZE
http://oss.oracle.com/pipermail/ocfs2-devel/2009-March/004185.html.Signed-off-by Tao Ma <[email protected]>
This looks sane to me, but I'd like Mark's opinion as well. He
knows the tree code better than I do.
Joel
Signature · 9 lines
Life's Little Instruction Book #274 "Leave everything a little better than you found it." Joel Becker Principal Software Developer Oracle E-mail: joel.becker at oracle.com Phone: (650) 506-8127
Quoted 38 lines · Tao Ma
Hi Mark/Joel,
I meet with some meta allocation bugs when I implement reflink these
days. And after some investigation, I think we should have the same problem when we havePAGE_SIZE>CLUSTER_SIZE. So I create a scenario today in one ppc box and try. the box panic as I expected. ;)The scenario is that: Create a file with the disk layout like
this(with bs=512, and cs=4K).debugfs: stat 15151
Inode: 66072 Mode: 0644 Generation: 59969160 (0x3930e88) <snip> Tree Depth: 1 Count: 19 Next Free Rec: 2 ## Offset Clusters Block# 0 0 258 86365 1 258 66 86367 SubAlloc Bit: 21 SubAlloc Slot: 0 Blknum: 86365 Next Leaf: 86367 CRC32: N/A ECC: N/A Tree Depth: 0 Count: 28 Next Free Rec: 28 ## Offset Clusters Block# Flags 0 0 1 116696 0x0 <snip> 25 25 1 117096 0x0 26 256 1 117112 0x1 27 257 1 117120 0x0 SubAlloc Bit: 23 SubAlloc Slot: 0 Blknum: 86367 Next Leaf: 0 CRC32: N/A ECC: N/A Tree Depth: 0 Count: 28 Next Free Rec: 2 ## Offset Clusters Block# Flags 0 258 2 117128 0x1 1 260 64 117176 0x1Please note the extent record from "26" to "0" of the next block are contiguous allocated with unwritten and then divide it by write to the 256 with 1 cluster.
Quoted 6 lines
Now if we try to write 40960 bytes at offset 256. We will panic. Why? The reason is that:
1. with ppc box, we have page_size=64K. So in oneocfs2_write_begin_no_lockwe will try to handle 40960 bytes together.
2. inocfs2_lock_allocatorswe will get that no metadata is need since the 2nd extent block has so many empty extent recs.
So, the core problem then is that ocfs2_lock_allocators is not doing as good a job calculating the meta data allocation this write needs.
Quoted 11 lines
3. then write begin one cluster by one in
ocfs2_write_cluster.
1) The 1st cluster(256) nothing special.
2) the 2nd (257), it will be merged with 256.
3) the 3rd (258), be merged with 256.
4) the 4th (259), be merged. Now 256-259 will be merged into 1 extent
rec, so the 2nd extent block will be removed. and we will get.26 256 4 117112 0x0 27 260 64 117176 0x15) Now comes the 260, we need to split and call
ocfs2_add_branchto
allocate a new block. But wait, we have no metadata reserved. So we panic here.
Right, ok.
Quoted 9 lines
So my thought is that can we reuse the freed extent block? I guess we can. We just need to store the pointer of
ocfs2_cached_dealloc_ctxtinocfs2_alloc_context. So whenever we allocate a new metadata, we try to searchocfs2_cached_dealloc_ctxtfirst, if there is some, we use it directly and delete it fromocfs2_cached_dealloc_ctxt. The same can go for cluster allocation I guess although I don't know whether we have such case for clusters.make sense?
Yes, but I think a better approach is to fix the core problem, instead of working around it. What we want to do then is make ocfs2_lock_allocators smart enough to catch this case so that it can reserve the proper amount of meta data. The good news is that we already do a scan of the writeable area in ocfs2_populate_write_desc(). It seems to me that scan is a good place where we could store some information about contiguous extents which will be merged. The only thing that'd be left for ocfs2_lock_allocators to do is look at the remaining extent block counts.
--Mark
--
Mark Fasheh
Hi Mark,
Quoted 10 lines · Mark Fasheh
Quoted 9 lines
So my thought is that can we reuse the freed extent block? I guess we can. We just need to store the pointer of
ocfs2_cached_dealloc_ctxtinocfs2_alloc_context. So whenever we allocate a new metadata, we try to searchocfs2_cached_dealloc_ctxtfirst, if there is some, we use it directly and delete it fromocfs2_cached_dealloc_ctxt. The same can go for cluster allocation I guess although I don't know whether we have such case for clusters.make sense?
Quoted 8 lines
Yes, but I think a better approach is to fix the core problem, instead of working around it. What we want to do then is make
ocfs2_lock_allocatorssmart enough to catch this case so that it can reserve the proper amount of meta data. The good news is that we already do a scan of the writeable area inocfs2_populate_write_desc(). It seems to me that scan is a good place where we could store some information about contiguous extents which will be merged. The only thing that'd be left forocfs2_lock_allocatorsto do is look at the remaining extent block counts.
actually this bug is found in reflink implementations. And in that case, it is more complicated. Since we are CoW at most 1M bytes in one transaction, that means 256 clusters at most, so we will have a very great chance to meet with many steps like this. And my simple test case has met with 6 (delete and add) for just one CoW. So I don't think we can make ocfs2_lock_allocators that smart enough to overcome it.
And if you look at my patch sent yesterday afternoon, it is very straightforward, and it only begin to work in the old BUG_ON scenario. So I think it is acceptable.
Regards,
Tao