Attachment 1455200 Details for Bug 1595389 – RFC PATCH Brent algo for list command loop detection - more efficient than Floyd / tortoise and hare

RFC PATCH Brent algo for list command loop detection - more efficient than Floyd / tortoise and hare

0002-Add-Brent-algorithm-for-cycle-detection-in-do_list.patch (text/plain), 3.74 KB, created by Dave Wysochanski on 2018-06-28 07:19:33 UTC

(hide)

Description:

Filename:

MIME Type:

Creator: Dave Wysochanski

Created: 2018-06-28 07:19:33 UTC

Size: 3.74 KB

patch

obsolete

>From 0c2c0c71e56f1116225cb2c3c11c6824ae97d16e Mon Sep 17 00:00:00 2001
>From: Dave Wysochanski <dwysocha@redhat.com>
>Date: Thu, 28 Jun 2018 03:14:28 -0400
>Subject: [PATCH 2/2] Add Brent algorithm for cycle detection in 'do_list'
>MIME-Version: 1.0
>Content-Type: text/plain; charset=UTF-8
>Content-Transfer-Encoding: 8bit
>
>Add the loop detection algorithm by R. P. Brent to list command.
>Brent is a variation on the "turtle and hare" from Floyd but with
>a "teleporting turtle".  Basically the single pointer ("hare")
>advances at a single step and a step_count starts at two and
>is doubled after the "hare" has gone step_count items.
>The slower pointer (the "turtle") starts at the same value and
>is checked against the faster pointer after each step.  If the
>"hare" ever equals "turtle" then there is a loop.  Once the
>"hare" goes step_count items, the turtle is "teleported" to the
>"hare" location.  The advancing of the second pointer in a doubling
>manner avoids some of the overhead of the traditional "turtle and
>hare" algorithm attributed to Floyd.
>
>References
>https://en.wikipedia.org/wiki/Cycle_detection#Brent%27s_algorithm
>http://www.siafoo.net/algorithm/11
>Brent, R. P. (1980), "An improved Monte Carlo factorization algorithm"
>(PDF), BIT Numerical Mathematics , 20 (2): 176â184,
>doi:10.1007/BF01933190 (https://doi.org/10.1007%2FBF01933190)
>
>Signed-off-by: Dave Wysochanski <dwysocha@redhat.com>
>---
> defs.h  |  1 +
> tools.c | 28 +++++++++++++++++++++++++++-
> 2 files changed, 28 insertions(+), 1 deletion(-)
>
>diff --git a/defs.h b/defs.h
>index 7019002..61bf29b 100644
>--- a/defs.h
>+++ b/defs.h
>@@ -2491,6 +2491,7 @@ struct list_data {             /* generic structure used by do_list() to walk */
> #define LIST_PARSE_MEMBER   (VERBOSE << 13)
> #define LIST_READ_MEMBER    (VERBOSE << 14)
> #define LIST_TORTOISE_HARE  (VERBOSE << 15)
>+#define LIST_BRENT_ALGO     (VERBOSE << 16)
> 
> #define HARE_SPEED 2
> 
>diff --git a/tools.c b/tools.c
>index ce87418..d56f789 100644
>--- a/tools.c
>+++ b/tools.c
>@@ -3266,9 +3266,13 @@ cmd_list(void)
> 	BZERO(ld, sizeof(struct list_data));
> 	struct_list_offset = 0;
> 
>-	while ((c = getopt(argcnt, args, "THhrs:S:e:o:xdl:")) != EOF) {
>+	while ((c = getopt(argcnt, args, "BTHhrs:S:e:o:xdl:")) != EOF) {
>                 switch(c)
> 		{
>+		case 'B':
>+			ld->flags |= LIST_BRENT_ALGO;
>+			break;
>+
> 		case 'T':
> 			ld->flags |= LIST_TORTOISE_HARE;
> 			break;
>@@ -3661,6 +3665,7 @@ do_list(struct list_data *ld)
> 	ulong next, last, first, offset;
> 	ulong hare, hare_idx;
> 	ulong searchfor, readflag;
>+	ulong brent_turtle, brent_steps_taken, brent_steps_limit;
> 	int i, count, others, close_hq_on_return;
> 	unsigned int radix;
> 	struct req_entry **e = NULL;
>@@ -3757,6 +3762,12 @@ do_list(struct list_data *ld)
> 			e[i] = fill_member_offsets(ld->structname[i]);
> 	}
> 
>+	if (ld->flags & LIST_BRENT_ALGO) {
>+		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);
>@@ -3782,6 +3793,7 @@ do_list(struct list_data *ld)
> 		}
> 
>                 if (!(ld->flags & LIST_TORTOISE_HARE) &&
>+		    !(ld->flags & LIST_BRENT_ALGO) &&
> 		    next && !hq_enter(next - ld->list_head_offset)) {
> 			if (ld->flags & 
> 			    (RETURN_ON_DUPLICATE|RETURN_ON_LIST_ERROR)) {
>@@ -3830,6 +3842,20 @@ do_list(struct list_data *ld)
> 			}
> 		}
> 
>+		if (ld->flags & LIST_BRENT_ALGO) {
>+			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");
>-- 
>1.8.3.1
>

Actions: View

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