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@xxxxxxxxxx> 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@xxxxxxxxxxxxxxxxxx> > -- Crash-utility mailing list Crash-utility@xxxxxxxxxx https://www.redhat.com/mailman/listinfo/crash-utility
