Re: [Crash-utility] crash-7.3.2 very long list iteration progressively increasing memory usage
On Fri, 2018-06-29 at 12:04 +0100, Jeremy Harris wrote:
On 06/28/2018 11:09 PM, David Wysochanski wrote:
> One problem with all of these non-storage location algorithms is that
> it won't give you the precise location of the start of the loop in the
> list (i.e. the one with the corrupted 'prev' list entry.
>
> I am not sure if this is a show stopper but that is fairly important
> information in most instances.
Um, one list-walker checking the back-pointer against where it
just came from would seem to suffice for that?
It's not as simple as that no.
I have a test patch now that implements the floyd algorithm, so it
handles the start of the loop problem (it is part b of the algorithm).
Once I do some more testing I'll send it to the list.
One thing I'm not sure about with floyd is the overhead of the fast
walker but it is almost like a readahead.
I am also testing Brent's algorithm which seems superior in loop
detection (no second walker needed) overhead. I have not coded up the
second part of the algorithm yet though.
My thought is if we can cut down the overhead to almost nil in the
normal list walk case, and then there's additional overhead once a loop
is detected to obtain the start of the loop, that is ok.