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.
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.
From 4c1bfd455aa41cb36fe5eed04b36e785df775f94 Mon Sep 17 00:00:00 2001
From: Dave Wysochanski <dwysocha@xxxxxxxxxx>
Date: Thu, 28 Jun 2018 04:52:05 -0400
Subject: [PATCH] Add alternative do_list_no_hash() function for the list command.
The do_list() function is called from many places and uses the hq_*
functions for cycle detection and a couple other functions. The list
command though only uses cycle detection, and for large lists, the
memory usage of the hash can become substantial.
Add a new do_list_no_hash() function that uses an alternative
algorithm to detect cycles, the Brent algorithm which is a variation
on Floyd's "tortoise and hare" algorithm.
The change in algorithm from using a hash based approach to the new
Brent results in the following memory usage and time while listing
one "list -H <addr>" command with a few billion entries:
<insert test results here>
Signed-off-by: Dave Wysochanski <dwysocha@xxxxxxxxxx>
---
defs.h | 1 +
tools.c | 200 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
2 files changed, 198 insertions(+), 3 deletions(-)
diff --git a/defs.h b/defs.h
index 931be07..eee5151 100644
--- a/defs.h
+++ b/defs.h
@@ -4939,6 +4939,7 @@ char *shift_string_right(char *, int);
int bracketed(char *, char *, int);
void backspace(int);
int do_list(struct list_data *);
+int do_list_no_hash(struct list_data *);
struct radix_tree_ops {
void (*entry)(ulong node, ulong slot, const char *path,
ulong index, void *private);
diff --git a/tools.c b/tools.c
index 1a83643..b869c57 100644
--- a/tools.c
+++ b/tools.c
@@ -3516,9 +3516,7 @@ next_arg:
ld->flags &= ~(LIST_OFFSET_ENTERED|LIST_START_ENTERED);
ld->flags |= VERBOSE;
- hq_open();
- c = do_list(ld);
- hq_close();
+ c = do_list_no_hash(ld);
if (ld->structname_args)
FREEBUF(ld->structname);
@@ -3863,6 +3861,202 @@ do_list(struct list_data *ld)
}
/*
+ * Similar to do_list but without the hq_* functions.
+ */
+int
+do_list_no_hash(struct list_data *ld)
+{
+ ulong next, last, first, offset;
+ ulong searchfor, readflag;
+ ulong brent_turtle, brent_steps_taken, brent_steps_limit;
+ int i, count, others;
+ unsigned int radix;
+ struct req_entry **e = NULL;
+
+ if (CRASHDEBUG(1)) {
+ others = 0;
+ console(" flags: %lx (", ld->flags);
+ if (ld->flags & VERBOSE)
+ console("%sVERBOSE", others++ ? "|" : "");
+ if (ld->flags & LIST_OFFSET_ENTERED)
+ console("%sLIST_OFFSET_ENTERED", others++ ? "|" : "");
+ if (ld->flags & LIST_START_ENTERED)
+ console("%sLIST_START_ENTERED", others++ ? "|" : "");
+ if (ld->flags & LIST_HEAD_FORMAT)
+ console("%sLIST_HEAD_FORMAT", others++ ? "|" : "");
+ if (ld->flags & LIST_HEAD_POINTER)
+ console("%sLIST_HEAD_POINTER", others++ ? "|" : "");
+ if (ld->flags & RETURN_ON_DUPLICATE)
+ console("%sRETURN_ON_DUPLICATE", others++ ? "|" : "");
+ if (ld->flags & RETURN_ON_LIST_ERROR)
+ console("%sRETURN_ON_LIST_ERROR", others++ ? "|" : "");
+ if (ld->flags & RETURN_ON_LIST_ERROR)
+ console("%sRETURN_ON_LIST_ERROR", others++ ? "|" : "");
+ if (ld->flags & LIST_STRUCT_RADIX_10)
+ console("%sLIST_STRUCT_RADIX_10", others++ ? "|" : "");
+ if (ld->flags & LIST_STRUCT_RADIX_16)
+ console("%sLIST_STRUCT_RADIX_16", others++ ? "|" : "");
+ if (ld->flags & LIST_ALLOCATE)
+ console("%sLIST_ALLOCATE", others++ ? "|" : "");
+ if (ld->flags & LIST_CALLBACK)
+ console("%sLIST_CALLBACK", others++ ? "|" : "");
+ if (ld->flags & CALLBACK_RETURN)
+ console("%sCALLBACK_RETURN", others++ ? "|" : "");
+ console(")\n");
+ console(" start: %lx\n", ld->start);
+ console(" member_offset: %ld\n", ld->member_offset);
+ console(" list_head_offset: %ld\n", ld->list_head_offset);
+ console(" end: %lx\n", ld->end);
+ console(" searchfor: %lx\n", ld->searchfor);
+ console(" structname_args: %lx\n", ld->structname_args);
+ if (!ld->structname_args)
+ console(" structname: (unused)\n");
+ for (i = 0; i < ld->structname_args; i++)
+ console(" structname[%d]: %s\n", i, ld->structname[i]);
+ console(" header: %s\n", ld->header);
+ console(" list_ptr: %lx\n", (ulong)ld->list_ptr);
+ console(" callback_func: %lx\n", (ulong)ld->callback_func);
+ console(" callback_data: %lx\n", (ulong)ld->callback_data);
+ console("struct_list_offset: %lx\n", ld->struct_list_offset);
+ }
+
+ count = 0;
+ searchfor = ld->searchfor;
+ ld->searchfor = 0;
+ if (ld->flags & LIST_STRUCT_RADIX_10)
+ radix = 10;
+ else if (ld->flags & LIST_STRUCT_RADIX_16)
+ radix = 16;
+ else
+ radix = 0;
+ next = ld->start;
+
+ readflag = ld->flags & RETURN_ON_LIST_ERROR ?
+ (RETURN_ON_ERROR|QUIET) : FAULT_ON_ERROR;
+
+ if (!readmem(next + ld->member_offset, KVADDR, &first, sizeof(void *),
+ "first list entry", readflag)) {
+ error(INFO, "\ninvalid list entry: %lx\n", next);
+ return -1;
+ }
+
+ if (ld->header)
+ fprintf(fp, "%s", ld->header);
+
+ offset = ld->list_head_offset + ld->struct_list_offset;
+
+ if (ld->structname && (ld->flags & LIST_READ_MEMBER)) {
+ e = (struct req_entry **)GETBUF(sizeof(*e) * ld->structname_args);
+ for (i = 0; i < ld->structname_args; i++)
+ e[i] = fill_member_offsets(ld->structname[i]);
+ }
+
+ brent_turtle = next;
+ brent_steps_taken = 0;
+ brent_steps_limit = 2;
+
+ while (1) {
+ if (ld->flags & VERBOSE) {
+ fprintf(fp, "%lx\n", next - ld->list_head_offset);
+
+ if (ld->structname) {
+ for (i = 0; i < ld->structname_args; i++) {
+ switch (count_chars(ld->structname[i], '.'))
+ {
+ case 0:
+ dump_struct(ld->structname[i],
+ next - offset, radix);
+ break;
+ default:
+ if (ld->flags & LIST_PARSE_MEMBER)
+ dump_struct_members(ld, i, next);
+ else if (ld->flags & LIST_READ_MEMBER)
+ dump_struct_members_fast(e[i],
+ radix, next - offset);
+ break;
+ }
+ }
+ }
+ }
+
+ if ((searchfor == next) ||
+ (searchfor == (next - ld->list_head_offset)))
+ ld->searchfor = searchfor;
+
+ count++;
+ last = next;
+
+ if ((ld->flags & LIST_CALLBACK) &&
+ ld->callback_func((void *)(next - ld->list_head_offset),
+ ld->callback_data) && (ld->flags & CALLBACK_RETURN))
+ break;
+
+ if (!readmem(next + ld->member_offset, KVADDR, &next,
+ sizeof(void *), "list entry", readflag)) {
+ error(INFO, "\ninvalid list entry: %lx\n", next);
+ return -1;
+ }
+
+ /*
+ * R. P. Brent algorithm for cycle detection.
+ */
+ brent_steps_taken++;
+ if (brent_turtle == next) {
+ error(INFO, "\nduplicate list entry: %lx\n", next);
+ return -1;
+ }
+ if (brent_steps_taken == brent_steps_limit) {
+ brent_steps_taken = 0;
+ brent_steps_limit *= 2;
+ brent_turtle = next;
+ }
+
+ if (next == 0) {
+ if (ld->flags & LIST_HEAD_FORMAT) {
+ error(INFO, "\ninvalid list entry: 0\n");
+ return -1;
+ }
+ if (CRASHDEBUG(1))
+ console("do_list end: next:%lx\n", next);
+ break;
+ }
+
+ if (next == ld->end) {
+ if (CRASHDEBUG(1))
+ console("do_list end: next:%lx == end:%lx\n",
+ next, ld->end);
+ break;
+ }
+
+ if (next == ld->start) {
+ if (CRASHDEBUG(1))
+ console("do_list end: next:%lx == start:%lx\n",
+ next, ld->start);
+ break;
+ }
+
+ if (next == last) {
+ if (CRASHDEBUG(1))
+ console("do_list end: next:%lx == last:%lx\n",
+ next, last);
+ break;
+ }
+
+ if ((next == first) && (count != 1)) {
+ if (CRASHDEBUG(1))
+ console("do_list end: next:%lx == first:%lx (count %d)\n",
+ next, last, count);
+ break;
+ }
+ }
+
+ if (CRASHDEBUG(1))
+ console("do_list count: %d\n", count);
+
+ return count;
+}
+
+/*
* Issue a dump_struct_member() call for one or more structure
* members. Multiple members are passed in a comma-separated
* list using the the format:
--
1.7.1
--
Crash-utility mailing list
Crash-utility@xxxxxxxxxx
https://www.redhat.com/mailman/listinfo/crash-utility
