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

[Goldwyn Rodrigues]

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.


>> 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)


> 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 ;)


-- 
Goldwyn