[Crash-utility] [PATCH] Rewrite radix tree traverse
Dave Anderson
anderson at redhat.com
Tue Jan 31 20:01:32 UTC 2017
Hi Ogawa,
I really appreciate the work you've put into this patch -- I will try to review
and test it tomorrow.
Thanks,
Dave
----- Original Message -----
>
> 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
>
> Changes lines are 275 insertions, 368 deletions.
>
> ---
>
> defs.h | 19 +--
> filesys.c | 266 +++++++------------------------------------------------
> kernel.c | 59 ++++++++----
> symbols.c | 6 +
> tools.c | 292
> +++++++++++++++++++++++++++++++++++++------------------------
> 5 files changed, 275 insertions(+), 367 deletions(-)
>
> diff -puN tools.c~radix-tree-fix tools.c
> --- crash-64/tools.c~radix-tree-fix 2017-01-30 10:25:04.511971087 +0900
> +++ crash-64-hirofumi/tools.c 2017-01-31 23:51:40.051399318 +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)
> {
> diff -puN defs.h~radix-tree-fix defs.h
> --- crash-64/defs.h~radix-tree-fix 2017-01-30 10:25:04.512971092 +0900
> +++ crash-64-hirofumi/defs.h 2017-01-30 10:25:04.516971115 +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);
> @@ -5081,16 +5090,6 @@ char *fill_inode_cache(ulong);
> void clear_inode_cache(void);
> int monitor_memory(long *, long *, long *, long *);
> int is_readable(char *);
> -#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 *);
> int file_dump(ulong, ulong, ulong, int, int);
> #define DUMP_FULL_NAME 0x1
> #define DUMP_INODE_ONLY 0x2
> diff -puN filesys.c~radix-tree-fix filesys.c
> --- crash-64/filesys.c~radix-tree-fix 2017-01-30 10:25:04.513971098 +0900
> +++ crash-64-hirofumi/filesys.c 2017-01-30 10:28:51.501266260 +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");
> @@ -2190,12 +2203,25 @@ get_inode_nrpages(ulong i_mapping)
> return nrpages;
> }
>
> +static void dump_inode_rdtree_entry(ulong node, ulong slot, const char
> *path,
> + ulong index, void *private)
> +{
> + ulong *count = private;
> + (*count)++;
> + dump_inode_page(slot);
> +}
> +
> static void
> dump_inode_page_cache_info(ulong inode)
> {
> + ulong count = 0;
> + struct radix_tree_ops ops = {
> + .entry = dump_inode_rdtree_entry,
> + .radix = 16,
> + .private = &count,
> + };
> char *inode_buf;
> - ulong i_mapping, nrpages, root_rnode, count;
> - struct radix_tree_pair rtp;
> + ulong i_mapping, nrpages, root_rnode;
> char header[BUFSIZE];
> char buf1[BUFSIZE];
> char buf2[BUFSIZE];
> @@ -2220,10 +2246,7 @@ dump_inode_page_cache_info(ulong inode)
> MKSTR(nrpages)));
>
> root_rnode = i_mapping + OFFSET(address_space_page_tree);
> - rtp.index = 0;
> - rtp.value = (void *)&dump_inode_page;
> -
> - count = do_radix_tree(root_rnode, RADIX_TREE_DUMP_CB, &rtp);
> + do_radix_tree_traverse(root_rnode, 1, &ops);
>
> if (count != nrpages)
> error(INFO, "page_tree count: %ld nrpages: %ld\n",
> @@ -3969,223 +3992,6 @@ cleanup_memory_driver(void)
> return errors ? FALSE : TRUE;
> }
>
> -
> -/*
> - * Use the kernel's radix_tree_lookup() function as a template to dump
> - * a radix tree's entries.
> - */
> -
> -ulong RADIX_TREE_MAP_SHIFT = UNINITIALIZED;
> -ulong RADIX_TREE_MAP_SIZE = UNINITIALIZED;
> -ulong RADIX_TREE_MAP_MASK = UNINITIALIZED;
> -
> -/*
> - * do_radix_tree argument usage:
> - *
> - * root: Address of a radix_tree_root structure
> - *
> - * flag: RADIX_TREE_COUNT - Return the number of entries in the tree.
> - * RADIX_TREE_SEARCH - Search for an entry at rtp->index; if found,
> - * store the entry in rtp->value and return a count of 1;
> otherwise
> - * return a count of 0.
> - * RADIX_TREE_DUMP - Dump all existing index/value pairs.
> - * RADIX_TREE_GATHER - Store all existing index/value pairs in the
> - * passed-in array of radix_tree_pair structs starting at rtp,
> - * returning the count of entries stored; the caller can/should
> - * limit the number of returned entries by putting the array size
> - * (max count) in the rtp->index field of the first structure
> - * in the passed-in array.
> - * RADIX_TREE_DUMP_CB - Similar with RADIX_TREE_DUMP, but for each
> - * radix tree entry, a user defined callback at rtp->value will
> - * be invoked.
> - *
> - * rtp: Unused by RADIX_TREE_COUNT and RADIX_TREE_DUMP.
> - * A pointer to a radix_tree_pair structure for RADIX_TREE_SEARCH.
> - * A pointer to an array of radix_tree_pair structures for
> - * RADIX_TREE_GATHER; the dimension (max count) of the array may
> - * be stored in the index field of the first structure to avoid
> - * any chance of an overrun.
> - * For RADIX_TREE_DUMP_CB, the rtp->value must be initialized as a
> - * callback function. The callback prototype must be: int
> (*)(ulong);
> - */
> -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);
> -
> - switch (flag)
> - {
> - case RADIX_TREE_COUNT:
> - for (index = count = 0; index <= maxindex; index++) {
> - if (radix_tree_lookup(root_rnode, index, height))
> - 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++;
> - }
> - 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++;
> - }
> - }
> - break;
> -
> - case RADIX_TREE_GATHER:
> - if (!(maxcount = rtp->index))
> - 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++;
> - }
> - }
> - break;
> -
> - case RADIX_TREE_DUMP_CB:
> - if (rtp->value == NULL) {
> - 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++;
> - }
> - }
> - 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;
> -}
> -
> int
> is_readable(char *filename)
> {
> diff -puN symbols.c~radix-tree-fix symbols.c
> --- crash-64/symbols.c~radix-tree-fix 2017-01-30 10:25:04.513971098 +0900
> +++ crash-64-hirofumi/symbols.c 2017-01-30 10:25:04.517971121 +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 kernel.c~radix-tree-fix kernel.c
> --- crash-64/kernel.c~radix-tree-fix 2017-01-30 10:25:04.514971103 +0900
> +++ crash-64-hirofumi/kernel.c 2017-01-30 10:25:04.518971126 +0900
> @@ -6218,16 +6218,34 @@ cmd_irq(void)
> }
> }
>
> +struct irq_desc_tree_info {
> + ulong count;
> + struct {
> + ulong node;
> + ulong index;
> + } *descs;
> + uint pos;
> +};
> +static void irq_desc_tree_entry(ulong node, ulong slot, const char *path,
> + ulong index, void *private)
> +{
> + struct irq_desc_tree_info *info = private;
> + info->count++;
> + if (info->descs) {
> + info->descs[info->pos].node = slot;
> + info->descs[info->pos].index = index;
> + info->pos++;
> + }
> +}
> +
> static ulong
> get_irq_desc_addr(int irq)
> {
> int c;
> - ulong cnt, addr, ptr;
> + ulong addr, ptr;
> long len;
> - struct radix_tree_pair *rtp;
>
> addr = 0;
> - rtp = NULL;
>
> if (!VALID_STRUCT(irq_desc_t))
> error(FATAL, "cannot determine size of irq_desc_t\n");
> @@ -6247,31 +6265,40 @@ get_irq_desc_addr(int irq)
> sizeof(void *), "irq_desc_ptrs entry",
> FAULT_ON_ERROR);
> } else if (kt->flags & IRQ_DESC_TREE) {
> + struct irq_desc_tree_info info;
> + struct radix_tree_ops ops = {
> + .entry = irq_desc_tree_entry,
> + .radix = 16,
> + .private = &info,
> + };
> +
> if (kt->highest_irq && (irq > kt->highest_irq))
> return addr;
>
> - cnt = do_radix_tree(symbol_value("irq_desc_tree"),
> - RADIX_TREE_COUNT, NULL);
> - len = sizeof(struct radix_tree_pair) * (cnt+1);
> - rtp = (struct radix_tree_pair *)GETBUF(len);
> - rtp[0].index = cnt;
> - cnt = do_radix_tree(symbol_value("irq_desc_tree"),
> - RADIX_TREE_GATHER, rtp);
> + info.count = 0;
> + info.descs = NULL;
> + do_radix_tree_traverse(symbol_value("irq_desc_tree"), 1, &ops);
> + len = sizeof(*info.descs) * (info.count + 1);
> + info.count = 0;
> + info.descs = (void *)GETBUF(len);
> + info.pos = 0;
> + do_radix_tree_traverse(symbol_value("irq_desc_tree"), 1, &ops);
>
> if (kt->highest_irq == 0)
> - kt->highest_irq = rtp[cnt-1].index;
> + kt->highest_irq = info.descs[info.count - 1].index;
>
> - for (c = 0; c < cnt; c++) {
> - if (rtp[c].index == irq) {
> + for (c = 0; c < info.count; c++) {
> + if (info.descs[c].index == irq) {
> if (CRASHDEBUG(1))
> fprintf(fp, "index: %ld value: %lx\n",
> - rtp[c].index, (ulong)rtp[c].value);
> - addr = (ulong)rtp[c].value;
> + info.descs[c].index,
> + info.descs[c].node);
> + addr = info.descs[c].node;
> break;
> }
> }
>
> - FREEBUF(rtp);
> + FREEBUF(info.descs);
> } else {
> error(FATAL,
> "neither irq_desc, _irq_desc, irq_desc_ptrs "
> _
>
> --
> OGAWA Hirofumi <hirofumi at mail.parknet.co.jp>
>
> --
> Crash-utility mailing list
> Crash-utility at redhat.com
> https://www.redhat.com/mailman/listinfo/crash-utility
>
More information about the Crash-utility
mailing list