[Ocfs2-tools-devel] [PATCH 2/2] looped chain - Break loop in fsck
tristan
tristan.ye at oracle.com
Tue Mar 2 19:13:18 PST 2010
Hi Goldwyn,
Comments are inlined:
Firstly, please check the patch by /kernel-src/script/checkpatch.pl
your-patch to detect the coding issues at the very beginning, since I
found some coding style problems when apply your patch:
Applying looped chain - Break loop in fsck
.dotest/patch:57: trailing whitespace.
ret = ocfs2_write_group_desc(ost->ost_fs,
.dotest/patch:90: trailing whitespace.
". Break the loop?",cs->cs_chain_no,
.dotest/patch:94: trailing whitespace.
}
.dotest/patch:115: trailing whitespace.
verbosef("cl cpg %u bpc %u count %u next %u gds %u max_ch_len %u\n",
warning: 4 lines add whitespace errors.
As for the coding style of ocfs2 src, please refer to:
http://www.kernel.org/doc/Documentation/CodingStyle
Goldwyn Rodrigues wrote:
> Detects a loop by checking hops against the theoretical limit of
> number of chains in a chain_rec. If a loop is found, it breaks it by
> storing the block numbers, and comparing with existing block numbers.
>
> Signed-off-by: Goldwyn Rodrigues <rgoldwyn at suse.de>
> Acked-by: Mark Fasheh <mfasheh at suse.com>
>
> ---
> diff --git a/fsck.ocfs2/fsck.ocfs2.checks.8.in b/fsck.ocfs2/fsck.ocfs2.checks.8.in
> index 05561ae..798a1e4 100644
> --- a/fsck.ocfs2/fsck.ocfs2.checks.8.in
> +++ b/fsck.ocfs2/fsck.ocfs2.checks.8.in
> @@ -202,6 +202,15 @@ valid in its bitmap.
> Answering yes decreases the number of recorded free bits so that it equals
> the total number of bits in the group descriptor's bitmap.
>
> +.SS "CHAIN_LOOP"
> +A chain may loop if the next field of the group descriptor points to one of
> +the previous group descriptors in the chain. This causes the ocfs2 code, both
> +user space and kernel module to loop forever.
> +
> +Answering yes breaks the loop at an optimum location so that all the existing
> +group descriptors are in the chain. However, it cannot re-connect stray group
> +descriptors and must rely on the rest of the fsck code to fix it.
> +
> .SS "CHAIN_COUNT"
> The chain list embedded in an inode is limited by the block size and the
> number of bytes consumed by the rest of the inode. A chain list header was
> diff --git a/fsck.ocfs2/pass0.c b/fsck.ocfs2/pass0.c
> index a32bd18..1b59cc1 100644
> --- a/fsck.ocfs2/pass0.c
> +++ b/fsck.ocfs2/pass0.c
> @@ -455,6 +455,46 @@ out:
> return ret;
> }
>
> +static errcode_t break_loop(o2fsck_state *ost, struct ocfs2_chain_rec *chain,
> + unsigned int max_depth)
>
I guess it will make more sense if your rename the func name as
break_chain_loop() :)
> +{
> + uint64_t *list;
> + int i;
> + unsigned int depth = 0;
> + uint64_t blkno = chain->c_blkno;
>
blkno = le64_to_cpu(chain->c_blkno);
> + char *buf;
> + struct ocfs2_group_desc *gd;
> + errcode_t ret = ocfs2_malloc0(sizeof(uint64_t) * max_depth, &list);
>
I recognized all what you do here is to locate the index where loop
happens, and break the loop by terminating the 'next' to NULL. I loved
the way your treating the loop chain, but I don't like the method you
locate a the position where loops happening.
You see, you used an extra array to record 'depth' of all previous
nodes, what's more, you also have to come back for checking each
previous nodes each step, that means your space complexity is O(N), and
time complexity here is O(N2), that's not so pleasant to me:)
> + if (ret)
> + goto out;
> + ret = ocfs2_malloc_block(ost->ost_fs->fs_io, &buf);
> + if (ret)
> + goto out;
> + gd = (struct ocfs2_group_desc *)buf;
> +
> + while (blkno && (depth<=max_depth)) {
> + list[depth++] = blkno;
> + ret = ocfs2_read_group_desc(ost->ost_fs, blkno, buf);
> + if (ret)
> + goto out;
> + blkno = gd->bg_next_group;
> + for (i=0; i<depth; i++)
> + if (list[i]==blkno) {
> + gd->bg_next_group = 0;
> + verbosef("Breaking gd loop %"PRIu64"\n", blkno);
> + ret = ocfs2_write_group_desc(ost->ost_fs,
> + blkno, buf);
> + goto out;
> + }
> + }
>
To detect and locate a loop in a list, you may have a better solution,
use 2 pointers, one is 'slow', and the other is 'fast', 'slow' pointer
proceed the list by one hop, and 'fast' one will go two hops each step,
so the essence of this alogrithm is, the fast pointer will meet slow
pointer somehow if there is a loop exists, otherwise, fast and slow
never meet, and end up with NULLs respectively. the code skeleton will
be as follows:
static unit64_t get_group_desc_next(o2fsck_state *ost, uint64_t blkno,
char *buf)
{
uint64_t next = 0;
struct ocfs2_group_desc *gd;
ret = ocfs2_read_group_desc(ost->ost_fs, blkno, buf);
if (ret)
return next;
gd = (struct ocfs2_group_desc *)buf;
next = gd->gb_next_group;
return next;
}
in function break_chain_loop():
uint64_t loop_blkno, blkno, slow, fast;
blkno = slow = fast = le64_to_cpu(chain->c_blkno);
while (fast && get_group_desc_next(ost, fast, buf)) {
/*
* fast ptr meet the slow means a loop happening there
*/
if ((fast == slow) || (get_group_desc_next(ost, fast, buf) == slow)) {
/*
* Loop happened at the node before fast and slow
*/
if (fast == slow)
loop_blkno = blkno;
/*
* Loop happend at the node of fast
*/
if (get_group_desc_next(ost, fast, buf) == slow)
loop_blkno = fast;
ret = ocfs2_read_group_desc(ost->ost_fs, loop_blkno, buf);
if (ret)
goto bail;
gd = (struct ocfs2_group_desc *)buf;
gd->bg_next_group = 0;
verbose("Breaking gd loop %"PRIu64"\n", loop_blkno);
ret = ocfs2_write_group_desc(ost->ost_fs, loop_blkno, buf);
if (ret)
goto bail;
break;
} else {
blkno = slow;
/*
* Slow ptr goes one by one hop each time.
*/
slow = get_group_desc_next(ost, slow, buf);
/*
* Fast ptr proceeds by 2 hops each step.
*/
fast = get_group_desc_next(ost, fast, buf);
fast = get_group_desc_next(ost, fast, buf);
}
}
...
According to above algorithm, we easily found that the space complexity
is 0, and time complexity was declined to O(N).
Regards,
Tristan.
> +out:
> + if (list)
> + ocfs2_free(&list);
> + if (buf)
> + ocfs2_free(&buf);
> + return ret;
> +}
> +
> /* this takes a slightly ridiculous number of arguments :/ */
> static errcode_t check_chain(o2fsck_state *ost,
> struct ocfs2_dinode *di,
> @@ -465,7 +505,8 @@ static errcode_t check_chain(o2fsck_state *ost,
> char *pre_cache_buf,
> int *chain_changed,
> ocfs2_bitmap *allowed,
> - ocfs2_bitmap *forbidden)
> + ocfs2_bitmap *forbidden,
> + unsigned int max_depth)
> {
> struct ocfs2_group_desc *bg1 = (struct ocfs2_group_desc *)buf1;
> struct ocfs2_group_desc *bg2 = (struct ocfs2_group_desc *)buf2;
> @@ -593,6 +634,14 @@ static errcode_t check_chain(o2fsck_state *ost,
> /* the loop will now start by reading bg1->next_group */
> memcpy(buf1, buf2, ost->ost_fs->fs_blocksize);
> depth++;
> + if (depth > max_depth) {
> + if (prompt(ost, PY, PR_CHAIN_LOOP,
> + "Loop detected in chain %d at block %"PRIu64
> + ". Break the loop?",cs->cs_chain_no,
> + (uint64_t) chain->c_blkno))
> + ret = break_loop(ost, chain, max_depth);
> + break;
> + }
> }
>
> /* we hit the premature end of a chain.. clear the last
> @@ -656,6 +705,7 @@ static errcode_t verify_chain_alloc(o2fsck_state *ost,
> int changed = 0, trust_next_free = 1;
> errcode_t ret = 0;
> uint64_t chain_bytes;
> + unsigned int num_gds, max_chain_len;
>
> if (memcmp(di->i_signature, OCFS2_INODE_SIGNATURE,
> strlen(OCFS2_INODE_SIGNATURE))) {
> @@ -685,9 +735,12 @@ static errcode_t verify_chain_alloc(o2fsck_state *ost,
> /* XXX should we check suballoc_node? */
>
> cl = &di->id2.i_chain;
> + num_gds = (di->i_clusters + cl->cl_cpg)/cl->cl_cpg;
> + max_chain_len = (num_gds + cl->cl_count)/cl->cl_count;
>
> - verbosef("cl cpg %u bpc %u count %u next %u\n",
> - cl->cl_cpg, cl->cl_bpc, cl->cl_count, cl->cl_next_free_rec);
> + verbosef("cl cpg %u bpc %u count %u next %u gds %u max_ch_len %u\n",
> + cl->cl_cpg, cl->cl_bpc, cl->cl_count, cl->cl_next_free_rec,
> + num_gds, max_chain_len);
>
> max_count = ocfs2_chain_recs_per_inode(ost->ost_fs->fs_blocksize);
>
> @@ -756,7 +809,7 @@ static errcode_t verify_chain_alloc(o2fsck_state *ost,
> .cs_cpg = cl->cl_cpg,
> };
> ret = check_chain(ost, di, &cs, cr, buf1, buf2, pre_cache_buf,
> - &changed, allowed, forbidden);
> + &changed, allowed, forbidden, max_chain_len);
> /* XXX what? not checking ret? */
>
> if (cr->c_blkno != 0) {
>
>
> _______________________________________________
> Ocfs2-tools-devel mailing list
> Ocfs2-tools-devel at oss.oracle.com
> http://oss.oracle.com/mailman/listinfo/ocfs2-tools-devel
>
More information about the Ocfs2-tools-devel
mailing list