[Crash-utility] [PATCH 6/6] Add a '-B' flag to the list command to call the brent algorithm.
The do_list_no_hash function does not use a hash table or allocate
much memory to enumerate lists, and thus it is much faster.
The new function implements Brent's algorithm for cycle detection,
so in addition to being faster it adds a couple additional loop
statistics to the output. Add a new '-B' option to the list command
allows use of this new algorithm while still retaining the default
behavior of the 'list' command.
Signed-off-by: Dave Wysochanski <dwysocha(a)redhat.com>
---
defs.h | 1 +
help.c | 6 ++++++
tools.c | 15 +++++++++++----
3 files changed, 18 insertions(+), 4 deletions(-)
diff --git a/defs.h b/defs.h
index 3ab295a..5af82be 100644
--- a/defs.h
+++ b/defs.h
@@ -2491,6 +2491,7 @@ 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_BRENT_ALGO (VERBOSE << 15)
struct tree_data {
ulong flags;
diff --git a/help.c b/help.c
index 638c6ec..a1c4c63 100644
--- a/help.c
+++ b/help.c
@@ -5822,6 +5822,12 @@ char *help__list[] = {
" -r For a list linked with list_head structures, traverse the
list",
" in the reverse order by using the \"prev\" pointer
instead",
" of \"next\".",
+" -B Use the algorithm from R. P. Brent to detect loops instead
of",
+" using a hash table. This algorithm uses a tiny fixed amount
of",
+" memory and so is especially helpful for longer lists. The
output",
+" is slightly different than the normal list output as it will",
+" print the length of the loop, the start of the loop, and the",
+" first duplicate in the list.",
" ",
" The meaning of the \"start\" argument, which can be expressed
symbolically,",
" in hexadecimal format, or an expression evaluating to an address, depends",
diff --git a/tools.c b/tools.c
index ba525a8..eeba4c4 100644
--- a/tools.c
+++ b/tools.c
@@ -3266,9 +3266,12 @@ 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, "BHhrs:S:e:o:xdl:")) != EOF) {
switch(c)
{
+ case 'B':
+ ld->flags |= LIST_BRENT_ALGO;
+ break;
case 'H':
ld->flags |= LIST_HEAD_FORMAT;
ld->flags |= LIST_HEAD_POINTER;
@@ -3516,9 +3519,13 @@ next_arg:
ld->flags &= ~(LIST_OFFSET_ENTERED|LIST_START_ENTERED);
ld->flags |= VERBOSE;
- hq_open();
- c = do_list(ld);
- hq_close();
+ if (ld->flags & LIST_BRENT_ALGO)
+ c = do_list_no_hash(ld);
+ else {
+ hq_open();
+ c = do_list(ld);
+ hq_close();
+ }
if (ld->structname_args)
FREEBUF(ld->structname);
--
1.8.3.1