8:42 a.m.
On Sat, 2018-06-30 at 21:11 -0400, David Wysochanski wrote:
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.
I have an implementation of both Floyd and Brent's algorithm. Once I
get a bit more testing in, I'll post patch(es) to the list.
The "big win" with either Floyd or Brent vs a hash table is the
elimination of overhead during list traverse while retaining the
ability to detect a list loop. Today with the default "hash on" when
you issue a "list" command, you don't know how big the list will be. If
it turns out the list is huge, the command may never complete with
"hash on" because of the increasing memory needs with each list node
passed. So just traversing the list can be a problem with the default.
That said, there are a couple trade-offs I can see.
The first trade-off with these algorithms is that when a loop is
detected, there are additional list traverse portions required to find
the start of the loop. As compared to the increasing memory usage of a
hash though and since the list traverse is fixed overhead (and likely
in page cache) and this seems like a good trade-off to me. That said,
for a large loop (think worst-case loop size of N with the start of the
loop at N-2), the overhead may be non-trivial and needs testing.
The second trade-off with both of these algorithms is that the output
will not be identical - i.e. you'll end up getting at least a fraction
of the loop printed in most instances. However, this may actually be
viewed as a "feature" since you can more easily see the repeating
values. In addition, we will have the distance to the beginning of the
loop and the loop length, which may be printed. So as an example, this
is what one list loop output shows with my Brent implementation - note
that a few more duplicate entries are printed (a portion of the loop)
rather than just the first duplicate:
crash> list -H 0xffff8ac03c81fc28
ffff8abdf38b7d00
ffff8abdf38b7ac0
ffff8abdf38b7f40
ffff8abe0edb4b00
ffff8abdf3bb5d00
ffff8abdf3bb5b80
ffff8abdf3bb5640
ffff8abe0e92b100
ffff8abe0e92ad40
ffff8abdf3bb5d00
ffff8abdf3bb5b80
ffff8abdf3bb5640
list: loop detected, loop length: 5
list: length from start to loop: 4
list: duplicate list entry: ffff8abdf3bb5d00
crash>
Compare this to existing crash output:
crash> list -H 0xffff8ac03c81fc28
ffff8abdf38b7d00
ffff8abdf38b7ac0
ffff8abdf38b7f40
ffff8abe0edb4b00
ffff8abdf3bb5d00
ffff8abdf3bb5b80
ffff8abdf3bb5640
ffff8abe0e92b100
ffff8abe0e92ad40
ffff8abdf3bb5d00
list: duplicate list entry: ffff8abdf3bb5d00
Below is a short comparison of these algorithms vs the existing crash
"hash on" and "hash off" modes.
"hash on" "hash off" [Floyd]
[Brent]
+---------------------+-------------+------------+------------------+--------------------+
|loop detection | Yes | No | Yes | Yes
|
+----------------------------------------------------------------------------------------+
|start of loop | Yes | No |Yes, requires 2nd |Yes, requires 2nd
|
|identification | | |start to loop trav|list traverse
|
+----------------------------------------------------------------------------------------+
|list command output | Yes | Yes | No | No. But loop
length|
|remains unchanged | | | | is "free"
calc |
+----------------------------------------------------------------------------------------+
|fixed memory overhead| No | Yes | Yes | Yes
|
|for list tra^erse | | | |
|
+----------------------------------------------------------------------------------------+
|fixed disk overhead | Yes | Yes | No but uses |Yes but reads 1
plus|
|during list tra^erse | | | readahead ptr |a fraction of loop
|
+----------------------------------------------------------------------------------------+
|loop length | No | No |Yes but additional| Yes
|
|calculated | | |loop traverse |
|
+----------------------------------------------------------------------------------------+
|distance from start | No | No |Yes, requires read|Yes, requires 2nd
|
|to loop calculated | | |start to loop |list traverse
|
+----------------------------------------------------------------------------------------+
|overhead for list | Yes | Yes | No | No
|
|w/loop same as list | | | |
|
|w/out loop | | | |
|
+---------------------+-------------+------------+------------------+--------------------+
[Floyd] https://en.wikipedia.org/wiki/Cycle_detection#Floyd%27s_Tortoise_and_Hare
[Brent] https://en.wikipedia.org/wiki/Cycle_detection#Brent%27s_algorithm