On Tue, 2018-06-26 at 15:34 +0100, Jeremy Harris wrote:
> On 06/26/2018 03:29 PM, David Wysochanski wrote:
> > On Tue, 2018-06-26 at 09:21 -0400, Dave Anderson wrote:
> > > 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.
> > >
> >
> > Ah ok yeah I forgot about the built-in list loop detection!
>
> 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.
I have a POC patch implementing this I'm testing. Right now I don't
have a vmcore with a list loop in it so I cannot really test it much.
Keep in mind it may be a total non-starter and I don't really know if
it works yet.
From a594388975f31663c94c46c7b87f7a423ad17e49 Mon Sep 17 00:00:00 2001
From: Dave Wysochanski <dwysocha@xxxxxxxxxx>
Date: Wed, 27 Jun 2018 17:29:00 -0400
Subject: [PATCH] Add 'T' option to 'list' command to implement faster loop
detection
The 'T' option of the 'list' command implements a version of the tortoise
and hare algorithm for loop detection. The speed of the hare is set at
2 and if it ever passes the tortoise a loop is detected. The tortoise
is the normal loop iteration.
All other functions in the 'do_list()' function should remain in tact.
This function is only implemented currently on the 'list' function by
adding a '-T' on the crash list command.
Signed-off-by: Dave Wysochanski <dwysocha@xxxxxxxxxx>
---
defs.h | 3 +++
tools.c | 27 +++++++++++++++++++++++++--
2 files changed, 28 insertions(+), 2 deletions(-)
diff --git a/defs.h b/defs.h
index 931be07..7019002 100644
--- a/defs.h
+++ b/defs.h
@@ -2490,6 +2490,9 @@ struct list_data { /* generic structure used by do_list() to walk */
#define CALLBACK_RETURN (VERBOSE << 12)
#define LIST_PARSE_MEMBER (VERBOSE << 13)
#define LIST_READ_MEMBER (VERBOSE << 14)
+#define LIST_TORTOISE_HARE (VERBOSE << 15)
+
+#define HARE_SPEED 2
struct tree_data {
ulong flags;
diff --git a/tools.c b/tools.c
index 1a83643..ed46bf0 100644
--- a/tools.c
+++ b/tools.c
@@ -3266,9 +3266,14 @@ cmd_list(void)
BZERO(ld, sizeof(struct list_data));
struct_list_offset = 0;
- while ((c = getopt(argcnt, args, "Hhrs:S:e:o:xdl:")) != EOF) {
+ while ((c = getopt(argcnt, args, "THhrs:S:e:o:xdl:")) != EOF) {
switch(c)
{
+ case 'T':
+ ld->flags |= LIST_TORTOISE_HARE;
+ ld->flags &= LIST_ALLOCATE;
+ break;
+
case 'H':
ld->flags |= LIST_HEAD_FORMAT;
ld->flags |= LIST_HEAD_POINTER;
@@ -3655,6 +3660,7 @@ int
do_list(struct list_data *ld)
{
ulong next, last, first, offset;
+ ulong hare, hare_idx;
ulong searchfor, readflag;
int i, count, others, close_hq_on_return;
unsigned int radix;
@@ -3776,7 +3782,8 @@ do_list(struct list_data *ld)
}
}
- if (next && !hq_enter(next - ld->list_head_offset)) {
+ if (!(ld->flags & LIST_TORTOISE_HARE) &&
+ next && !hq_enter(next - ld->list_head_offset)) {
if (ld->flags &
(RETURN_ON_DUPLICATE|RETURN_ON_LIST_ERROR)) {
error(INFO, "\nduplicate list entry: %lx\n",
@@ -3808,6 +3815,22 @@ do_list(struct list_data *ld)
return -1;
}
+ if (ld->flags & LIST_TORTOISE_HARE) {
+ hare = next;
+ for (hare_idx = 0; hare_idx < HARE_SPEED; hare_idx++) {
+ if (!readmem(hare + ld->member_offset, KVADDR, &hare,
+ sizeof(void *), "list entry", readflag)) {
+ error(INFO, "\ninvalid list entry: %lx\n", hare);
+ return -1;
+ }
+ if (hare == next) {
+ error(INFO, "\nduplicate list entry: %lx\n",
+ next);
+ return -1;
+ }
+ }
+ }
+
if (next == 0) {
if (ld->flags & LIST_HEAD_FORMAT) {
error(INFO, "\ninvalid list entry: 0\n");
--
1.8.3.1
--
Crash-utility mailing list
Crash-utility@xxxxxxxxxx
https://www.redhat.com/mailman/listinfo/crash-utility
