[Crash-utility] [PATCH] Rewrite radix tree traverse
OGAWA Hirofumi
hirofumi at mail.parknet.co.jp
Thu Feb 2 04:57:50 UTC 2017
Dave Anderson <anderson at redhat.com> writes:
> Hello Ogawa,
Hello, Dave.
> I haven't really started looking at this patch, but one question comes
> to mind immediately.
>
> In the current defs.h, the old construct is exported:
>
> #define RADIX_TREE_COUNT (1)
> #define RADIX_TREE_SEARCH (2)
> #define RADIX_TREE_DUMP (3)
> #define RADIX_TREE_GATHER (4)
> #define RADIX_TREE_DUMP_CB (5)
> struct radix_tree_pair {
> ulong index;
> void *value;
> };
> ulong do_radix_tree(ulong, int, struct radix_tree_pair *);
>
> Your patch removes the do_radix_tree() function, the radix_tree_pair
> structure, and the flags.
>
> Since an existing extension module could conceivably be using
> do_radix_tree(), would it be possible for you to also create a new
> do_radix_tree() function that translates the old flag argument,
> populates the radix_tree_pair structure(s), while doing so by
> utilizing your new functionality to accomplish the task?
OK.
This version of the patch preserves do_radix_tree() API (with 1 FIXME,
because do_radix_tree_traverse() doesn't have efficient search ability
for now, possible to add probably though.). And old do_radix_tree()
users are not converted to new API (on v4.9, it seems to be working as
expected).
Thanks.
---
Rewrite radix tree traverse
Now, radix tree traverse is broken for kernel v4.9. Furthermore, there
are similar functions in filesys.c and tools.c.
So, to fix it, this rewrites radix tree traverse with callback based
function to support all current usages with one function. New API is
do_radix_tree_traverse() that controlled by "struct radix_tree_ops".
radix_tree_ops.entry - called for each radix tree entry (exclude internal)
radix_tree_ops.radix - when error happened, dump struct by this radix
radix_tree_ops.private - user pointer that passing to radix_tree_ops.entry
---
defs.h | 9 +
filesys.c | 258 ++++++++++++++++++++---------------------------------
symbols.c | 6 +
tools.c | 292 +++++++++++++++++++++++++++++++++++++------------------------
4 files changed, 294 insertions(+), 271 deletions(-)
diff -puN defs.h~radix-tree-fix defs.h
--- crash-64/defs.h~radix-tree-fix 2017-02-02 13:45:41.867688787 +0900
+++ crash-64-hirofumi/defs.h 2017-02-02 13:45:41.871688812 +0900
@@ -1879,6 +1879,7 @@ struct offset_table {
long super_block_s_fs_info;
long rq_timestamp;
long radix_tree_node_height;
+ long radix_tree_node_shift;
long rb_root_rb_node;
long rb_node_rb_left;
long rb_node_rb_right;
@@ -2149,6 +2150,7 @@ struct array_table {
int free_area_DIMENSION;
int prio_array_queue;
int height_to_maxindex;
+ int height_to_maxnodes;
int pid_hash;
int kmem_cache_node;
int kmem_cache_cpu_slab;
@@ -4803,6 +4805,13 @@ char *shift_string_right(char *, int);
int bracketed(char *, char *, int);
void backspace(int);
int do_list(struct list_data *);
+struct radix_tree_ops {
+ void (*entry)(ulong node, ulong slot, const char *path,
+ ulong index, void *private);
+ uint radix;
+ void *private;
+};
+int do_radix_tree_traverse(ulong ptr, int is_root, struct radix_tree_ops *ops);
int do_rdtree(struct tree_data *);
int do_rbtree(struct tree_data *);
int retrieve_list(ulong *, int);
diff -puN filesys.c~radix-tree-fix filesys.c
--- crash-64/filesys.c~radix-tree-fix 2017-02-02 13:45:41.867688787 +0900
+++ crash-64-hirofumi/filesys.c 2017-02-02 13:47:09.114230904 +0900
@@ -2080,14 +2080,25 @@ vfs_init(void)
if (!(ft->inode_cache = (char *)malloc(SIZE(inode)*INODE_CACHE)))
error(FATAL, "cannot malloc inode cache\n");
- if (symbol_exists("height_to_maxindex")) {
+ if (symbol_exists("height_to_maxindex") ||
+ symbol_exists("height_to_maxnodes")) {
+ int newver = symbol_exists("height_to_maxnodes");
int tmp ATTRIBUTE_UNUSED;
- if (LKCD_KERNTYPES())
- ARRAY_LENGTH_INIT_ALT(tmp, "height_to_maxindex",
- "radix_tree_preload.nodes", NULL, 0);
- else
- ARRAY_LENGTH_INIT(tmp, height_to_maxindex,
- "height_to_maxindex", NULL, 0);
+ if (!newver) {
+ if (LKCD_KERNTYPES())
+ ARRAY_LENGTH_INIT_ALT(tmp, "height_to_maxindex",
+ "radix_tree_preload.nodes", NULL, 0);
+ else
+ ARRAY_LENGTH_INIT(tmp, height_to_maxindex,
+ "height_to_maxindex", NULL, 0);
+ } else {
+ if (LKCD_KERNTYPES())
+ ARRAY_LENGTH_INIT_ALT(tmp, "height_to_maxnodes",
+ "radix_tree_preload.nodes", NULL, 0);
+ else
+ ARRAY_LENGTH_INIT(tmp, height_to_maxnodes,
+ "height_to_maxnodes", NULL, 0);
+ }
STRUCT_SIZE_INIT(radix_tree_root, "radix_tree_root");
STRUCT_SIZE_INIT(radix_tree_node, "radix_tree_node");
MEMBER_OFFSET_INIT(radix_tree_root_height,
@@ -2098,6 +2109,8 @@ vfs_init(void)
"radix_tree_node","slots");
MEMBER_OFFSET_INIT(radix_tree_node_height,
"radix_tree_node","height");
+ MEMBER_OFFSET_INIT(radix_tree_node_shift,
+ "radix_tree_node","shift");
}
MEMBER_OFFSET_INIT(rb_root_rb_node,
"rb_root","rb_node");
@@ -3969,15 +3982,64 @@ cleanup_memory_driver(void)
return errors ? FALSE : TRUE;
}
+struct do_radix_tree_info {
+ ulong maxcount;
+ ulong count;
+ void *data;
+};
+static void do_radix_tree_count(ulong node, ulong slot, const char *path,
+ ulong index, void *private)
+{
+ struct do_radix_tree_info *info = private;
+ info->count++;
+}
+static void do_radix_tree_search(ulong node, ulong slot, const char *path,
+ ulong index, void *private)
+{
+ struct do_radix_tree_info *info = private;
+ struct radix_tree_pair *rtp = info->data;
-/*
- * Use the kernel's radix_tree_lookup() function as a template to dump
- * a radix tree's entries.
- */
+ if (rtp->index == index) {
+ rtp->value = (void *)slot;
+ info->count = 1;
+ }
+}
+static void do_radix_tree_dump(ulong node, ulong slot, const char *path,
+ ulong index, void *private)
+{
+ struct do_radix_tree_info *info = private;
+ fprintf(fp, "[%ld] %lx\n", index, slot);
+ info->count++;
+}
+static void do_radix_tree_gather(ulong node, ulong slot, const char *path,
+ ulong index, void *private)
+{
+ struct do_radix_tree_info *info = private;
+ struct radix_tree_pair *rtp = info->data;
-ulong RADIX_TREE_MAP_SHIFT = UNINITIALIZED;
-ulong RADIX_TREE_MAP_SIZE = UNINITIALIZED;
-ulong RADIX_TREE_MAP_MASK = UNINITIALIZED;
+ if (info->maxcount) {
+ rtp[info->count].index = index;
+ rtp[info->count].value = (void *)slot;
+
+ info->count++;
+ info->maxcount--;
+ }
+}
+static void do_radix_tree_dump_cb(ulong node, ulong slot, const char *path,
+ ulong index, void *private)
+{
+ struct do_radix_tree_info *info = private;
+ struct radix_tree_pair *rtp = info->data;
+ int (*cb)(ulong) = rtp->value;
+
+ /* Caller defined operation */
+ if (!cb(slot)) {
+ error(FATAL, "do_radix_tree: callback "
+ "operation failed: entry: %ld item: %lx\n",
+ info->count, slot);
+ }
+ info->count++;
+}
/*
* do_radix_tree argument usage:
@@ -4011,116 +4073,39 @@ ulong RADIX_TREE_MAP_MASK = UNINITIALIZE
ulong
do_radix_tree(ulong root, int flag, struct radix_tree_pair *rtp)
{
- int i, ilen, height;
- long nlen;
- ulong index, maxindex, count, maxcount;
- long *height_to_maxindex;
- char *radix_tree_root_buf;
- struct radix_tree_pair *r;
- ulong root_rnode;
- void *ret;
- int (*cb)(ulong) = NULL;
-
- count = 0;
-
- if (!VALID_STRUCT(radix_tree_root) || !VALID_STRUCT(radix_tree_node) ||
- !VALID_MEMBER(radix_tree_root_height) ||
- !VALID_MEMBER(radix_tree_root_rnode) ||
- !VALID_MEMBER(radix_tree_node_slots) ||
- !ARRAY_LENGTH(height_to_maxindex))
- error(FATAL,
- "radix trees do not exist (or have changed their format)\n");
-
- if (RADIX_TREE_MAP_SHIFT == UNINITIALIZED) {
- if (!(nlen = MEMBER_SIZE("radix_tree_node", "slots")))
- error(FATAL, "cannot determine length of "
- "radix_tree_node.slots[] array\n");
- nlen /= sizeof(void *);
- RADIX_TREE_MAP_SHIFT = ffsl(nlen) - 1;
- RADIX_TREE_MAP_SIZE = (1UL << RADIX_TREE_MAP_SHIFT);
- RADIX_TREE_MAP_MASK = (RADIX_TREE_MAP_SIZE-1);
- }
-
- ilen = ARRAY_LENGTH(height_to_maxindex);
- height_to_maxindex = (long *)GETBUF(ilen * sizeof(long));
- readmem(symbol_value("height_to_maxindex"), KVADDR,
- height_to_maxindex, ilen*sizeof(long),
- "height_to_maxindex array", FAULT_ON_ERROR);
-
- if (CRASHDEBUG(1)) {
- fprintf(fp, "radix_tree_node.slots[%ld]\n",
- RADIX_TREE_MAP_SIZE);
- fprintf(fp, "height_to_maxindex[%d]: ", ilen);
- for (i = 0; i < ilen; i++)
- fprintf(fp, "%lu ", height_to_maxindex[i]);
- fprintf(fp, "\n");
- fprintf(fp, "radix_tree_root at %lx:\n", root);
- dump_struct("radix_tree_root", (ulong)root, RADIX(16));
- }
-
- radix_tree_root_buf = GETBUF(SIZE(radix_tree_root));
- readmem(root, KVADDR, radix_tree_root_buf, SIZE(radix_tree_root),
- "radix_tree_root", FAULT_ON_ERROR);
- height = UINT(radix_tree_root_buf + OFFSET(radix_tree_root_height));
-
- if ((height < 0) || (height > ilen)) {
- error(INFO, "height_to_maxindex[] index: %ld\n", ilen);
- fprintf(fp, "invalid height in radix_tree_root at %lx:\n", root);
- dump_struct("radix_tree_root", (ulong)root, RADIX(16));
- return 0;
- }
-
- maxindex = height_to_maxindex[height];
- FREEBUF(height_to_maxindex);
- FREEBUF(radix_tree_root_buf);
-
- root_rnode = root + OFFSET(radix_tree_root_rnode);
+ struct do_radix_tree_info info = {
+ .count = 0,
+ .data = rtp,
+ };
+ struct radix_tree_ops ops = {
+ .radix = 16,
+ .private = &info,
+ };
switch (flag)
{
case RADIX_TREE_COUNT:
- for (index = count = 0; index <= maxindex; index++) {
- if (radix_tree_lookup(root_rnode, index, height))
- count++;
- }
+ ops.entry = do_radix_tree_count;
break;
case RADIX_TREE_SEARCH:
- count = 0;
- if (rtp->index > maxindex)
- break;
-
- if ((ret = radix_tree_lookup(root_rnode, rtp->index, height))) {
- rtp->value = ret;
- count++;
- }
+ /*
+ * FIXME: do_radix_tree_traverse() traverses whole
+ * radix tree, not binary search. So this search is
+ * not efficient.
+ */
+ ops.entry = do_radix_tree_search;
break;
case RADIX_TREE_DUMP:
- for (index = count = 0; index <= maxindex; index++) {
- if ((ret =
- radix_tree_lookup(root_rnode, index, height))) {
- fprintf(fp, "[%ld] %lx\n", index, (ulong)ret);
- count++;
- }
- }
+ ops.entry = do_radix_tree_dump;
break;
case RADIX_TREE_GATHER:
- if (!(maxcount = rtp->index))
- maxcount = (ulong)(-1); /* caller beware */
+ if (!(info.maxcount = rtp->index))
+ info.maxcount = (ulong)(-1); /* caller beware */
- for (index = count = 0, r = rtp; index <= maxindex; index++) {
- if ((ret =
- radix_tree_lookup(root_rnode, index, height))) {
- r->index = index;
- r->value = ret;
- count++;
- if (--maxcount <= 0)
- break;
- r++;
- }
- }
+ ops.entry = do_radix_tree_gather;
break;
case RADIX_TREE_DUMP_CB:
@@ -4128,62 +4113,15 @@ do_radix_tree(ulong root, int flag, stru
error(FATAL, "do_radix_tree: need set callback function");
return -EINVAL;
}
- cb = (int (*)(ulong))rtp->value;
- for (index = count = 0; index <= maxindex; index++) {
- if ((ret =
- radix_tree_lookup(root_rnode, index, height))) {
- /* Caller defined operation */
- if (!cb((ulong)ret)) {
- error(FATAL, "do_radix_tree: callback "
- "operation failed: entry: %ld item: %lx\n",
- count, (ulong)ret);
- }
- count++;
- }
- }
+ ops.entry = do_radix_tree_dump_cb;
break;
default:
error(FATAL, "do_radix_tree: invalid flag: %lx\n", flag);
}
- return count;
-}
-
-static void *
-radix_tree_lookup(ulong root_rnode, ulong index, int height)
-{
- unsigned int shift;
- ulong rnode;
- ulong *slots;
-
- shift = (height-1) * RADIX_TREE_MAP_SHIFT;
-
- readmem(root_rnode, KVADDR, &rnode, sizeof(void *),
- "radix_tree_root rnode", FAULT_ON_ERROR);
-
- if (rnode & 1)
- rnode &= ~1;
-
- slots = (ulong *)GETBUF(sizeof(void *) * RADIX_TREE_MAP_SIZE);
-
- while (height > 0) {
- if (rnode == 0)
- break;
-
- readmem((ulong)rnode+OFFSET(radix_tree_node_slots), KVADDR,
- &slots[0], sizeof(void *) * RADIX_TREE_MAP_SIZE,
- "radix_tree_node.slots array", FAULT_ON_ERROR);
-
- rnode = slots[((index >> shift) & RADIX_TREE_MAP_MASK)];
-
- shift -= RADIX_TREE_MAP_SHIFT;
- height--;
- }
-
- FREEBUF(slots);
-
- return (void *)rnode;
+ do_radix_tree_traverse(root, 1, &ops);
+ return info.count;
}
int
diff -puN symbols.c~radix-tree-fix symbols.c
--- crash-64/symbols.c~radix-tree-fix 2017-02-02 13:45:41.868688793 +0900
+++ crash-64-hirofumi/symbols.c 2017-02-02 13:45:41.872688818 +0900
@@ -8369,6 +8369,8 @@ builtin_array_length(char *s, int len, i
lenptr = &array_table.prio_array_queue;
else if (STREQ(s, "height_to_maxindex"))
lenptr = &array_table.height_to_maxindex;
+ else if (STREQ(s, "height_to_maxnodes"))
+ lenptr = &array_table.height_to_maxnodes;
else if (STREQ(s, "pid_hash"))
lenptr = &array_table.pid_hash;
else if (STREQ(s, "free_area")) {
@@ -9771,6 +9773,8 @@ dump_offset_table(char *spec, ulong make
OFFSET(radix_tree_node_slots));
fprintf(fp, " radix_tree_node_height: %ld\n",
OFFSET(radix_tree_node_height));
+ fprintf(fp, " radix_tree_node_shift: %ld\n",
+ OFFSET(radix_tree_node_shift));
fprintf(fp, " rb_root_rb_node: %ld\n",
OFFSET(rb_root_rb_node));
@@ -10406,6 +10410,8 @@ dump_offset_table(char *spec, ulong make
get_array_length("prio_array.queue", NULL, SIZE(list_head)));
fprintf(fp, " height_to_maxindex: %d\n",
ARRAY_LENGTH(height_to_maxindex));
+ fprintf(fp, " height_to_maxnodes: %d\n",
+ ARRAY_LENGTH(height_to_maxnodes));
fprintf(fp, " pid_hash: %d\n",
ARRAY_LENGTH(pid_hash));
fprintf(fp, " kmem_cache_node: %d\n",
diff -puN tools.c~radix-tree-fix tools.c
--- crash-64/tools.c~radix-tree-fix 2017-02-02 13:45:41.869688799 +0900
+++ crash-64-hirofumi/tools.c 2017-02-02 13:45:41.870688805 +0900
@@ -4091,161 +4091,231 @@ static ulong RADIX_TREE_MAP_SHIFT = UNIN
static ulong RADIX_TREE_MAP_SIZE = UNINITIALIZED;
static ulong RADIX_TREE_MAP_MASK = UNINITIALIZED;
-int
-do_rdtree(struct tree_data *td)
+#define RADIX_TREE_ENTRY_MASK 3UL
+#define RADIX_TREE_INTERNAL_NODE 1UL
+
+static void do_radix_tree_iter(ulong node, uint height, char *path,
+ ulong index, struct radix_tree_ops *ops)
{
- long nlen;
+ uint off;
+
+ for (off = 0; off < RADIX_TREE_MAP_SIZE; off++) {
+ ulong slot;
+ ulong shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
+
+ readmem(node + OFFSET(radix_tree_node_slots) +
+ sizeof(void *) * off, KVADDR, &slot, sizeof(void *),
+ "radix_tree_node.slot[off]", FAULT_ON_ERROR);
+ if (!slot)
+ continue;
+
+ if (slot & RADIX_TREE_INTERNAL_NODE)
+ slot &= ~RADIX_TREE_INTERNAL_NODE;
+
+ if (height == 1)
+ ops->entry(node, slot, path, index | off, ops->private);
+ else {
+ ulong child_index = index | (off << shift);
+ char child_path[BUFSIZE];
+ sprintf(child_path, "%s/%ld", path, off);
+ do_radix_tree_iter(slot, height - 1,
+ child_path, child_index, ops);
+ }
+ }
+}
+
+int do_radix_tree_traverse(ulong ptr, int is_root, struct radix_tree_ops *ops)
+{
+ static ulong max_height = UNINITIALIZED;
ulong node_p;
- uint print_radix, height;
- char pos[BUFSIZE];
+ long nlen;
+ uint height, is_internal;
+ char path[BUFSIZE];
if (!VALID_STRUCT(radix_tree_root) || !VALID_STRUCT(radix_tree_node) ||
- !VALID_MEMBER(radix_tree_root_height) ||
- !VALID_MEMBER(radix_tree_root_rnode) ||
- !VALID_MEMBER(radix_tree_node_slots) ||
- !ARRAY_LENGTH(height_to_maxindex))
+ ((!VALID_MEMBER(radix_tree_root_height) ||
+ !VALID_MEMBER(radix_tree_root_rnode) ||
+ !VALID_MEMBER(radix_tree_node_slots) ||
+ !ARRAY_LENGTH(height_to_maxindex)) &&
+ (!VALID_MEMBER(radix_tree_root_rnode) ||
+ !VALID_MEMBER(radix_tree_node_shift) ||
+ !VALID_MEMBER(radix_tree_node_slots) ||
+ !ARRAY_LENGTH(height_to_maxnodes))))
error(FATAL, "radix trees do not exist or have changed "
"their format\n");
if (RADIX_TREE_MAP_SHIFT == UNINITIALIZED) {
if (!(nlen = MEMBER_SIZE("radix_tree_node", "slots")))
- error(FATAL, "cannot determine length of "
+ error(FATAL, "cannot determine length of "
"radix_tree_node.slots[] array\n");
nlen /= sizeof(void *);
RADIX_TREE_MAP_SHIFT = ffsl(nlen) - 1;
RADIX_TREE_MAP_SIZE = (1UL << RADIX_TREE_MAP_SHIFT);
RADIX_TREE_MAP_MASK = (RADIX_TREE_MAP_SIZE-1);
- }
- if (td->flags & TREE_STRUCT_RADIX_10)
- print_radix = 10;
- else if (td->flags & TREE_STRUCT_RADIX_16)
- print_radix = 16;
- else
- print_radix = 0;
+ if (ARRAY_LENGTH(height_to_maxindex))
+ max_height = ARRAY_LENGTH(height_to_maxindex);
+ else
+ max_height = ARRAY_LENGTH(height_to_maxnodes);
+ }
- if (td->flags & TREE_NODE_POINTER) {
- node_p = td->start;
+ height = 0;
+ if (!is_root) {
+ node_p = ptr;
- if (node_p & 1)
- node_p &= ~1;
+ if (node_p & RADIX_TREE_INTERNAL_NODE)
+ node_p &= ~RADIX_TREE_INTERNAL_NODE;
if (VALID_MEMBER(radix_tree_node_height)) {
readmem(node_p + OFFSET(radix_tree_node_height), KVADDR,
&height, sizeof(uint), "radix_tree_node height",
FAULT_ON_ERROR);
-
- if (height > ARRAY_LENGTH(height_to_maxindex)) {
- fprintf(fp, "radix_tree_node at %lx\n", node_p);
- dump_struct("radix_tree_node", node_p, print_radix);
- error(FATAL, "height %d is greater than "
- "height_to_maxindex[] index %ld\n",
- height, ARRAY_LENGTH(height_to_maxindex));
- }
- } else
+ } else if (VALID_MEMBER(radix_tree_node_shift)) {
+ unsigned char shift;
+ readmem(node_p + OFFSET(radix_tree_node_shift), KVADDR,
+ &shift, sizeof(shift), "radix_tree_node shift",
+ FAULT_ON_ERROR);
+ height = (shift / RADIX_TREE_MAP_SHIFT) + 1;
+ } else
error(FATAL, "-N option is not supported or applicable"
" for radix trees on this architecture or kernel\n");
+ if (height > max_height)
+ goto error_height;
} else {
- readmem(td->start + OFFSET(radix_tree_root_height), KVADDR, &height,
- sizeof(uint), "radix_tree_root height", FAULT_ON_ERROR);
-
- if (height > ARRAY_LENGTH(height_to_maxindex)) {
- fprintf(fp, "radix_tree_root at %lx\n", td->start);
- dump_struct("radix_tree_root", (ulong)td->start, print_radix);
- error(FATAL, "height %d is greater than "
- "height_to_maxindex[] index %ld\n",
- height, ARRAY_LENGTH(height_to_maxindex));
+ if (VALID_MEMBER(radix_tree_root_height)) {
+ readmem(ptr + OFFSET(radix_tree_root_height), KVADDR, &height,
+ sizeof(uint), "radix_tree_root height", FAULT_ON_ERROR);
}
- readmem(td->start + OFFSET(radix_tree_root_rnode), KVADDR, &node_p,
+ readmem(ptr + OFFSET(radix_tree_root_rnode), KVADDR, &node_p,
sizeof(void *), "radix_tree_root rnode", FAULT_ON_ERROR);
+ is_internal = (node_p & RADIX_TREE_INTERNAL_NODE);
+ if (node_p & RADIX_TREE_INTERNAL_NODE)
+ node_p &= ~RADIX_TREE_INTERNAL_NODE;
+
+ if (is_internal && VALID_MEMBER(radix_tree_node_shift)) {
+ unsigned char shift;
+ readmem(node_p + OFFSET(radix_tree_node_shift), KVADDR, &shift,
+ sizeof(shift), "radix_tree_node shift", FAULT_ON_ERROR);
+ height = (shift / RADIX_TREE_MAP_SHIFT) + 1;
+ }
+
+ if (height > max_height) {
+ node_p = ptr;
+ goto error_height;
+ }
}
- if (node_p & 1)
- node_p &= ~1;
+ if (CRASHDEBUG(1)) {
+ fprintf(fp, "radix_tree_node.slots[%ld]\n",
+ RADIX_TREE_MAP_SIZE);
+ fprintf(fp, "max_height %d: ", max_height);
+ fprintf(fp, "\n");
+ fprintf(fp, "pointer at %lx (is_root? %s):\n",
+ node_p, is_root ? "yes" : "no");
+ if (is_root)
+ dump_struct("radix_tree_root", ptr, RADIX(ops->radix));
+ else
+ dump_struct("radix_tree_node", node_p, RADIX(ops->radix));
+ }
- sprintf(pos, "root");
+ if (height == 0) {
+ strcpy(path, "direct");
+ ops->entry(node_p, node_p, path, 0, ops->private);
+ } else {
+ strcpy(path, "root");
+ do_radix_tree_iter(node_p, height, path, 0, ops);
+ }
- rdtree_iteration(node_p, td, pos, -1, height);
+ return 0;
- return td->count;
+error_height:
+ fprintf(fp, "radix_tree_node at %lx\n", node_p);
+ dump_struct("radix_tree_node", node_p, RADIX(ops->radix));
+ error(FATAL, "height %d is greater than "
+ "maximum radix tree height index %ld\n",
+ height, max_height);
+ return -1;
}
-void
-rdtree_iteration(ulong node_p, struct tree_data *td, char *ppos, ulong indexnum, uint height)
+static void do_rdtree_entry(ulong node, ulong slot, const char *path,
+ ulong index, void *private)
{
- ulong slot;
- int i, index;
- uint print_radix;
- char pos[BUFSIZE];
+ struct tree_data *td = private;
static struct req_entry **e = NULL;
+ uint print_radix;
+ int i;
- if (indexnum != -1)
- sprintf(pos, "%s/%ld", ppos, indexnum);
- else
- sprintf(pos, "%s", ppos);
+ if (!td->count && td->structname_args) {
+ /*
+ * Retrieve all members' info only once (count == 0)
+ * After last iteration all memory will be freed up
+ */
+ e = (struct req_entry **)GETBUF(sizeof(*e) * td->structname_args);
+ for (i = 0; i < td->structname_args; i++)
+ e[i] = fill_member_offsets(td->structname[i]);
+ }
- for (index = 0; index < RADIX_TREE_MAP_SIZE; index++) {
- readmem((ulong)node_p + OFFSET(radix_tree_node_slots) +
- sizeof(void *) * index, KVADDR, &slot, sizeof(void *),
- "radix_tree_node.slot[index]", FAULT_ON_ERROR);
- if (!slot)
- continue;
- if (height == 1) {
- if (!td->count && td->structname_args) {
- /*
- * Retrieve all members' info only once (count == 0)
- * After last iteration all memory will be freed up
- */
- e = (struct req_entry **)GETBUF(sizeof(*e) *
- td->structname_args);
- for (i = 0; i < td->structname_args; i++)
- e[i] = fill_member_offsets(td->structname[i]);
- }
+ if (hq_enter(slot))
+ td->count++;
+ else
+ error(FATAL,
+ "\nduplicate tree entry: radix_tree_node: %lx slots[%d]: %lx\n",
+ node, index, slot);
+
+ if (td->flags & VERBOSE)
+ fprintf(fp, "%lx\n", slot);
+
+ if (td->flags & TREE_POSITION_DISPLAY) {
+ fprintf(fp, " position: %s/%d\n",
+ path, index & RADIX_TREE_MAP_MASK);
+ }
- if (hq_enter(slot))
- td->count++;
- else
- error(FATAL,
- "\nduplicate tree entry: radix_tree_node: %lx slots[%d]: %lx\n",
- node_p, index, slot);
-
- if (td->flags & VERBOSE)
- fprintf(fp, "%lx\n",slot);
-
- if (td->flags & TREE_POSITION_DISPLAY)
- fprintf(fp, " position: %s/%d\n", pos, index);
-
- if (td->structname) {
- if (td->flags & TREE_STRUCT_RADIX_10)
- print_radix = 10;
- else if (td->flags & TREE_STRUCT_RADIX_16)
- print_radix = 16;
- else
- print_radix = 0;
-
- for (i = 0; i < td->structname_args; i++) {
- switch(count_chars(td->structname[i], '.'))
- {
- case 0:
- dump_struct(td->structname[i],
- slot, print_radix);
- break;
- default:
- if (td->flags & TREE_PARSE_MEMBER)
- dump_struct_members_for_tree(td, i,
- slot);
- else if (td->flags & TREE_READ_MEMBER)
- dump_struct_members_fast(e[i], print_radix, slot);
- break;
- }
- }
+ if (td->structname) {
+ if (td->flags & TREE_STRUCT_RADIX_10)
+ print_radix = 10;
+ else if (td->flags & TREE_STRUCT_RADIX_16)
+ print_radix = 16;
+ else
+ print_radix = 0;
+
+ for (i = 0; i < td->structname_args; i++) {
+ switch (count_chars(td->structname[i], '.')) {
+ case 0:
+ dump_struct(td->structname[i], slot, print_radix);
+ break;
+ default:
+ if (td->flags & TREE_PARSE_MEMBER)
+ dump_struct_members_for_tree(td, i, slot);
+ else if (td->flags & TREE_READ_MEMBER)
+ dump_struct_members_fast(e[i], print_radix, slot);
+ break;
}
- } else
- rdtree_iteration(slot, td, pos, index, height-1);
+ }
}
}
+int do_rdtree(struct tree_data *td)
+{
+ struct radix_tree_ops ops = {
+ .entry = do_rdtree_entry,
+ .private = td,
+ };
+ int is_root = !(td->flags & TREE_NODE_POINTER);
+ uint print_radix;
+
+ if (td->flags & TREE_STRUCT_RADIX_10)
+ ops.radix = 10;
+ else if (td->flags & TREE_STRUCT_RADIX_16)
+ ops.radix = 16;
+ else
+ ops.radix = 0;
+
+ do_radix_tree_traverse(td->start, is_root, &ops);
+
+ return 0;
+}
+
int
do_rbtree(struct tree_data *td)
{
_
--
OGAWA Hirofumi <hirofumi at mail.parknet.co.jp>
More information about the Crash-utility
mailing list