Add a new do_list_no_hash() function which is similar to do_list() but without the hash_table overhead and without the LIST_ALLOCATE. This function will be useful for faster and lower overhead list enumeration, especially for the "list" command. Signed-off-by: Dave Wysochanski <dwysocha(a)redhat.com&gt; --- defs.h | 1 + tools.c | 189 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 190 insertions(+) diff --git a/defs.h b/defs.h index b05aecc..3ab295a 100644 --- a/defs.h +++ b/defs.h @@ -4944,6 +4944,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..a642d60 100644 --- a/tools.c +++ b/tools.c @@ -3863,6 +3863,195 @@ do_list(struct list_data *ld) } /* + * Similar to do_list() but without the hash_table or LIST_ALLOCATE. + * Useful for the 'list' command and other callers needing faster list + * enumeration. + */ +int +do_list_no_hash(struct list_data *ld) +{ + ulong next, last, first, offset; + ulong searchfor, readflag; + 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]); + } + + 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 (next && 0) { /* FIXME - duplicate detection */ + if (ld->flags & + (RETURN_ON_DUPLICATE|RETURN_ON_LIST_ERROR)) { + error(INFO, "\nduplicate list entry: %lx\n", + next); + return -1; + } + error(FATAL, "\nduplicate list entry: %lx\n", next); + } + + 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; + } + + 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.8.3.1

Create do_list_output_struct function to dump out the structure name and members. No functional change. Signed-off-by: Dave Wysochanski <dwysocha(a)redhat.com&gt; --- tools.c | 42 +++++++++++++++++++++++++----------------- 1 file changed, 25 insertions(+), 17 deletions(-) diff --git a/tools.c b/tools.c index 2af114f..f9bf56f 100644 --- a/tools.c +++ b/tools.c @@ -3914,6 +3914,30 @@ static void do_list_debug_entry(struct list_data *ld) } } + +static void do_list_output_struct(struct list_data *ld, ulong next, ulong offset, + unsigned int radix, struct req_entry **e) +{ + int i; + + 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; + } + } +} + /* * Similar to do_list() but without the hash_table or LIST_ALLOCATE. * Useful for the 'list' command and other callers needing faster list @@ -3964,24 +3988,8 @@ do_list_no_hash(struct list_data *ld) 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; - } - } + do_list_output_struct(ld, next, offset, radix, e); } } -- 1.8.3.1

The existing "list" command uses a hash table to detect duplicate items as it traverses the list. The hash table approach has worked well for many years. However, with increasing memory sizes and list sizes, the overhead of the hash table can be substantial, often leading to commands running for a very long time. For large lists, we have found that the existing hash based approach may slow the system to a crawl and possibly never complete. You can turn off the hash with "hash off" but then there is no loop detection. In this case, loop detection must be done manually after dumping the list to disk or some other method. This patch is an implementation of the cycle detection algorithm from R. P. Brent as an alternative algorithm for the "list" command. The algorithm both avoids the overhead of the hash table and yet is able to detect a loop. In addition, further loop characteristics are printed, such as the distance to the start of the loop as well as the loop length. The algorithm from R. P. Brent uses only a tiny amount of memory (two pointers) and adds extremely minimal overhead if no loop is detected. If a loop is detected it adds additional overhead of advancing through the list to find the start of the loop. While this overhead may be non-trivial for large lists, the cost of each list advance should be a fixed cost and compares favorably to an ever increasing cost of a list advance with a hash table. Thus in all instances, the algorithm is superior to a hash table approach for list traversal. The algorithm is divided into two phases, detection of a loop, and detection of the loop start (first duplicate). The first phase of the algorithm adds almost no overhead to an existing list traversal. To detect a loop a second pointer is added which follows the first list traversal pointer periodically according to an increasing power of two length. Eventually, if there is a loop, this increasing power of two will be larger than the loop size, and the list traversal pointer will eventually be equal to the second pointer that is periodically moved. If the list traversal pointer never reaches this second pointer, there is no loop. If a loop is detected, the second phase of the algorithm is entered, and this adds overhead. First a couple points of explanation and a diagram of a list with a loop example: non_loop_len = 5 +--->--->--->---^---> | | loop_len = 4 | | <---v In the above diagram, we have two segments: a) a non_loop segment (or "non-perodic" segment), and b) a loop segment (or "periodic" segment). As a side note, in the literature, these lengths are often given two specific greek letters with the length of the loop segment referred to as lambda, while the non-loop segment length is referred to as mu. In any case, the important thing to understand is there are two distinct segments now, with two different lengths. Once we have exited from Brent's first phase, the loop length is known. Why is that? For the first phase to have exited, the traversal pointer had to have met the following pointer. And for that to happen, the traversal pointer had to have been stationary for the length of the loop, and the power of two was greater than the loop length. When the loop is detected, the following message is printed: list loop detected, loop length: 4 The second phase of the loop is entered, with the purpose of identifying the non-loop length as well as the point at which the loop and the non-loop intersect (this is the first duplicate). To obtain these objectives, we note the following relation of steps required to reach the intersection: itersection = non_loop_len + N*loop_len for any integer N where N >= 0 The second phase does the following: 1. Reset the first and second pointer to the start 2. Advance the second pointer loop_len steps 3. Advance both pointers until they meet, saving the step count The second pointer will have gone both non_loop_len + loop_len steps to arrive at the intersection, and the first pointer will have gone non_loop_len steps to arrive at the intersection. When the second phase exits (both pointers are equal) we have the non_loop length. When the loop exits, the following message is printed: list loop length from start to loop: 5 duplicate list entry: ffff8abdf3bb5d00 An example of the full output of this new algorithm when a list loop is detected is as follows: crash> list -H 0xffff8ac03c81fc28 ffff8abdf38b7d00 ffff8abdf38b7ac0 ffff8abdf38b7f40 ffff8abe0edb4b00 ffff8abdf3bb5d00 ffff8abdf3bb5b80 ffff8abdf3bb5640 ffff8abe0e92b100 ffff8abe0e92ad40 ffff8abdf3bb5d00 ffff8abdf3bb5b80 ffff8abdf3bb5640 list: loop detected, loop length: 5 list: length from start to loop: 4 list: duplicate list entry: ffff8abdf3bb5d00 crash> This compares with existing crash output as follows: crash> list -H 0xffff8ac03c81fc28 ffff8abdf38b7d00 ffff8abdf38b7ac0 ffff8abdf38b7f40 ffff8abe0edb4b00 ffff8abdf3bb5d00 ffff8abdf3bb5b80 ffff8abdf3bb5640 ffff8abe0e92b100 ffff8abe0e92ad40 ffff8abdf3bb5d00 list: duplicate list entry: ffff8abdf3bb5d00 crash> Signed-off-by: Dave Wysochanski <dwysocha(a)redhat.com&gt; --- tools.c | 68 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 64 insertions(+), 4 deletions(-) diff --git a/tools.c b/tools.c index 0d4b8e5..ba525a8 100644 --- a/tools.c +++ b/tools.c @@ -3949,6 +3949,21 @@ static int do_list_no_hash_readmem(struct list_data *ld, ulong *next_ptr, return 0; } +ulong brent_x; /* tortoise */ +ulong brent_y; /* hare */ +ulong brent_r; /* power */ +ulong brent_lambda; /* loop length */ +ulong brent_mu; /* distance to start of loop */ +ulong brent_loop_detect; +ulong brent_loop_exit; +/* + * 'ptr': representative of x or y; modified on return + */ +static int brent_f(ulong *ptr, struct list_data *ld, ulong readflag) +{ + return do_list_no_hash_readmem(ld, ptr, readflag); +} + /* * Similar to do_list() but without the hash_table or LIST_ALLOCATE. * Useful for the 'list' command and other callers needing faster list @@ -3996,22 +4011,29 @@ do_list_no_hash(struct list_data *ld) e[i] = fill_member_offsets(ld->structname[i]); } + brent_loop_detect = brent_loop_exit = 0; + brent_lambda = 0; + brent_r = 2; + brent_x = brent_y = next; + ret = brent_f(&brent_y, ld, readflag); + if (ret == -1) + return -1; while (1) { - if (ld->flags & VERBOSE) { + if (!brent_loop_detect && ld->flags & VERBOSE) { fprintf(fp, "%lx\n", next - ld->list_head_offset); if (ld->structname) { do_list_output_struct(ld, next, offset, radix, e); } } - if (next && 0) { /* FIXME - duplicate detection */ + if (next && brent_loop_exit) { if (ld->flags & (RETURN_ON_DUPLICATE|RETURN_ON_LIST_ERROR)) { error(INFO, "\nduplicate list entry: %lx\n", - next); + brent_x); return -1; } - error(FATAL, "\nduplicate list entry: %lx\n", next); + error(FATAL, "\nduplicate list entry: %lx\n", brent_x); } if ((searchfor == next) || @@ -4030,6 +4052,43 @@ do_list_no_hash(struct list_data *ld) if (ret == -1) return -1; + if (!brent_loop_detect) { + if (brent_x == brent_y) { + brent_loop_detect = 1; + error(INFO, "loop detected, loop length: %lx\n", brent_lambda); + /* reset x and y to start; advance y loop length */ + brent_mu = 0; + brent_x = brent_y = ld->start; + while (brent_lambda--) { + ret = brent_f(&brent_y, ld, readflag); + if (ret == -1) + return -1; + } + } else { + if (brent_r == brent_lambda) { + brent_x = brent_y; + brent_r *= 2; + brent_lambda = 0; + } + brent_y = next; + brent_lambda++; + } + } else { + if (!brent_loop_exit && brent_x == brent_y) { + brent_loop_exit = 1; + error(INFO, "length from start to loop: %lx", + brent_mu); + } else { + ret = brent_f(&brent_x, ld, readflag); + if (ret == -1) + return -1; + ret = brent_f(&brent_y, ld, readflag); + if (ret == -1) + return -1; + brent_mu++; + } + } + if (next == 0) { if (ld->flags & LIST_HEAD_FORMAT) { error(INFO, "\ninvalid list entry: 0\n"); @@ -4037,6 +4096,7 @@ do_list_no_hash(struct list_data *ld) } if (CRASHDEBUG(1)) console("do_list end: next:%lx\n", next); + break; } -- 1.8.3.1