----- Original Message ----- Yes, by default all list entries encountered are put in the built-in hash queue, specifically for the purpose of determining whether there are duplicate entries. So if it's still running, it hasn't found any. To avoid the use of the hashing feature, try entering "set hash off" before kicking off the command. But of course if it finds any, it will loop forever. Dave

On 06/26/2018 03:29 PM, David Wysochanski wrote: For a storage-less method of list loop-detection: run two walkers down the list, advancing two versus one elements. If you ever match the same element location after starting, you have a loop. -- Cheers, Jeremy

----- Original Message ----- I'll await your patch... Right, just as in any case where malloc() is used, the freed memory is not removed the user address space, but remains for subsequent allocations. Dave

----- Original Message ----- For maintenance sake, it's probably worth keeping the hash queue option in place, primarily since there are a few dozen other internal facilities besides the user "list" command that use the do_list() function. Dave

----- Original Message ----- Could be. That's what the "crash --hash <count>" command line option may alleviate. But remember that we changed the default number of hash queue heads to 32768. Yep, you're right. I was thinking that the hq_close() done by restore_sanity() would free the memory even if you end the command with Ctrl-c, but it does keep it around for the next user. Dave

On 06/26/2018 10:40 AM, David Wysochanski wrote: Could the same algorithm be modified so that it can slow down after a certain number of list members, say maybe saving only every 10th element to the hash (but checking every new one)?

On 06/26/2018 11:15 AM, Dave Anderson wrote: Right, but if we didn't detect the first duplicate, we should still see one in the next 10 entries. Once the list repeats, it should repeat identically.

On 06/27/2018 09:02 AM, David Mair wrote: I was just throwing the idea out there and wanted to keep it simple at first. If this is a feasible solution we can improve upon it.

On Tue, 2018-06-26 at 15:34 +0100, Jeremy Harris 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. Attached is my latest patch I was testing.

On 06/29/2018 05:04 AM, Jeremy Harris wrote: That's much less work than using two walkers with differing step sizes looking for them to ever match within the list but it assumes a doubly linked list for all cases and the knowledge of where the prev pointer is relative to the next pointer. Are we talking about commands (list) that aren't to be used on singly linked (next only) lists. -- David.

On Sat, 2018-06-30 at 21:11 -0400, David Wysochanski wrote: 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

On 06/29/2018 11:29 AM, David Mair wrote: Corrections for two errors, both walkers have to do the left margin so the total steps for two walkers can't be less than 1M for the described loop and at 10:1 the overhead isn't as big as above: 10:1 5.500M 99:98 1.005M ...or to put it another way. The wasted time spent by the long step walker iterating the loop when the short step walker has yet to reach the loop is: left margin * ((big step - short step) / short step) Meaning for the same ratios in the same loop case the big walker wasted effort in the loop is: Ratio Overhead (additional steps by long walker) (long step : short step) 2:1 500k 4:1 1.50M 10:1 4.50M 3:2 250k 5:4 125k 99:98 5102 Then, when both walkers are withing the loop the long step walker is guaranteed to walk the loop at least once. It's already stepping the loop before the short step walker can reach the loop. Meaning the Overhead (additional step...) cases above are also "saved effort" when the loop is longer than them because they are progress into the required loop completion by the long step walker before it can find the short step walker. So, for very long loops very high ratios of long step to short step with very small values of short step are fastest for finding the match when both walkers are within the loop. For very short loops it probably doesn't make much difference but if the match is only being checked for in one of the walkers then it's probably best if it's the long step walker and that the short step walker is as close as possible to one (minimizes how far into the loop or number of iterations of thew loop the short step walker can be at when it is found). Since the size of the loop isn't guaranteed to be long or short for each of a set of cases the optimal approach is probably to favor the smallest size for the short step and one greater than that for the long step. -- David.