Attachment 1455222 Details for Bug 1595389 – RFC patch (under testing) with do_list() replacement using Brent's algorithm for cycle detection

RFC patch (under testing) with do_list() replacement using Brent's algorithm for cycle detection

0001-Add-alternative-do_list_no_hash-function-for-the-lis.patch (text/plain), 7.69 KB, created by Dave Wysochanski on 2018-06-28 09:52:54 UTC

(hide)

Description:

Filename:

MIME Type:

Creator: Dave Wysochanski

Created: 2018-06-28 09:52:54 UTC

Size: 7.69 KB

patch

obsolete

>From 4c1bfd455aa41cb36fe5eed04b36e785df775f94 Mon Sep 17 00:00:00 2001
>From: Dave Wysochanski <dwysocha@redhat.com>
>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@redhat.com>
>---
> 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
>

Actions: View

Attachments on bug 1595389: 1455126 | 1455134 | 1455139 | 1455200 | 1455222