Re: [Crash-utility] [PATCH] Rewrite radix tree traverse
by OGAWA Hirofumi
Dave Anderson <anderson(a)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(a)mail.parknet.co.jp>
7 years, 9 months
- 2
- 2
[PATCH] Rewrite radix tree traverse
by OGAWA Hirofumi
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(a)mail.parknet.co.jp>
7 years, 9 months
- 2
- 2