[Ocfs2-tools-devel] [PATCH 2/2] looped chain - Break loop in fsck

[tristan ye]

Goldwyn Rodrigues wrote:
> Hi Tristan,
>
>
> On Fri, Mar 5, 2010 at 8:44 AM, tristan ye <tristan.ye at oracle.com> wrote:
>
> <snip>
>
>   
>>> Now you are trying to cover up your mistake ;)
>>>
>>>       
>> Yes, the previous codes has not been tested well, it's nothing realistic but
>> a  concept I guess. while the latest one I pasted last time is workable
>> under testing, is there still any mistakes?
>>
>>     
>
> No, there are no mistakes that I can tell in the linked list implementation.
>   

Hi Goldwyn,

Yeah, the attachment of codes I pasted was trial, it however, is 
runnable for testing things, though was not based on ocfs2-tools:)

>
>   
>>> I fully understand the algorithm and the algorithm posted on the
>>> various internet sites are correct. For that matter, if you know the
>>> loop is large enough, using relatively prime number of hops will help
>>> you achieve the "meeting point" faster.
>>>
>>> It is *your implementation* of the algorithm I am not willing to agree
>>> with.
>>>
>>>       
>> Hi Goldwyn,
>>
>> Thanks for your patient follow-up on this issue:)
>>
>> I admit that previous code skeleton pasted by has mistakes, it's just a
>> rough solution to illustrate my general idea against the algorithm. and I've
>> not tested it in a real env. However, the last code I pasted was feasible
>> under testing by your cases. Do you think it's still a unrealistic one?
>>
>>     
>
> No. For that matter, I never thought or stated it was unrealistic. I
> was pointing out flaws in your implementation (which I misstated as
> your algorithm)
>   

Thank you so much for finding out the flaws in my previous mail.

>
>   
>> Let me know if you have some other suggestions on it.
>>     
>>>       
>>>> The code skeleton works for me now as follows:
>>>>
>>>> int detect_loop(struct link_node *head, int breakage)
>>>> {
>>>>      struct link_node *fast, *slow, *prev;
>>>>      int looped = 0;
>>>>
>>>>      prev = fast = slow = head;
>>>>
>>>>      while (1) {
>>>>              if (fast && fast->next)
>>>>                      fast = fast->next->next;
>>>>              else
>>>>                      return looped;
>>>>
>>>>              prev = slow;
>>>>              slow = slow->next;
>>>>
>>>>              if (fast == slow) {
>>>>                      looped = 1;
>>>>                      break;
>>>>              }
>>>>      }
>>>>
>>>>      if (looped && breakage) {
>>>>
>>>>              fast = head;
>>>>              while (fast != slow) {
>>>>                      prev = slow;
>>>>                      slow = slow->next;
>>>>                      fast = fast->next;
>>>>              }
>>>>
>>>>         
>>> You have changed (corrected) this! In analogy  to your previous
>>> posting, fast=slow->next, which is causing the infinite loop.
>>>
>>> For your convenince, I will paste it again:
>>>
>>>
>>>       
>>>>>>>>  while (blkno != slow) {
>>>>>>>>   blkno = get_group_desc_next(ost, blkno, buf);
>>>>>>>>   slow = get_group_desc_next(ost, blkno, buf);
>>>>>>>>  }
>>>>>>>>
>>>>>>>>                 
>>> I would appreciate if you would post the correct implementation for
>>> the good audit.
>>> I understand what you are trying to do and I agree the algorithm is
>>> much better with respect to time and space efficiency. However, if it
>>> does not run correctly, it is not acceptable.
>>>
>>> Please post the final patch with respect to ocfs2-tools.
>>>
>>>       
>> I can post the final patch regarding ocfs2-tools if you have no objection
>> against my above algorithm which is feasible in a experimental env.
>>     
>
> I have no objections to the algorithm, I might have to the implementation ;)
>   

Cool, waiting for your next patch, thank you for the hard work again:)



Tristan.

>
>