Attachment 1455134 Details for Bug 1595389 – POC v2 patch (lightly tested) for a tortoise and hare loop detection algo for the 'list' command

[patch] POC v2 patch (lightly tested) for a tortoise and hare loop detection algo for the 'list' command

0001-Add-T-option-to-list-command-to-implement-faster-loo.patch (text/plain), 2.99 KB, created by Dave Wysochanski on 2018-06-27 21:41:27 UTC

(hide)

Description:

Filename:

MIME Type:

Creator: Dave Wysochanski

Created: 2018-06-27 21:41:27 UTC

Size: 2.99 KB

patch

obsolete

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

Actions: View | Diff

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