[Crash-utility] [PATCH] Rewrite radix tree traverse
Dave Anderson
anderson at redhat.com
Thu Feb 2 21:22:19 UTC 2017
Hello Ogawa,
I truly appreciate the work you put into this patchset. It's queued for crash-7.1.8:
https://github.com/crash-utility/crash/commit/880574406d0acf3bf4e90402b7e0c22b97083b4a
Note that I moved the 2 new offset_table and array_table entries to the end of the
two structures to prevent pre-compiled extension modules from failing, and fixed
a few compiler warnings generated when building with "make warn".
Thanks very much,
Dave
----- Original Message -----
> 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