4:35 a.m.
Hi,
just a head's up that the linux radix_tree got replaced by something
called xarray in 4.20 (already into master, will be in 4.20-rc1)
You can look at the patch series here:
https://lore.kernel.org/lkml/20180313132639.17387-3-willy@infradead.org/T...
* [PATCH v9 11/61] xarray: Add definition of struct xarray
-> replaces radix_tree_root by xarray
* [PATCH v9 12/61] xarray: Define struct xa_node
-> replaces radix_tree_node by xa_node
As far as I can tell they look fairly close to radix_tree for now, but
while I hoped just renaming fields and removing max height might do the
trick, but it looks like one would need to actually look at the
differences in implementation as just doing that was a bit optimistic...
The tree iteration for running tasks got me 4 tasks so it obviously
didn't get very far; I probably missed something obvious.
For now I wanted to debug something else so went back a notch instead of
trying harder, I'll probably come back to this in the next few weeks if
nobody else has. Don't wait for me if you want to do it though :)
(hopefully that'll save someone a few minutes if they run into this
meanwhile)
Cheers,
--
Dominique Martinet | Asmadeus
9:32 a.m.
----- Original Message -----
Hi,
just a head's up that the linux radix_tree got replaced by something
called xarray in 4.20 (already into master, will be in 4.20-rc1)
You can look at the patch series here:
https://lore.kernel.org/lkml/20180313132639.17387-3-willy@infradead.org/T...
* [PATCH v9 11/61] xarray: Add definition of struct xarray
-> replaces radix_tree_root by xarray
* [PATCH v9 12/61] xarray: Define struct xa_node
-> replaces radix_tree_node by xa_node
As far as I can tell they look fairly close to radix_tree for now, but
while I hoped just renaming fields and removing max height might do the
trick, but it looks like one would need to actually look at the
differences in implementation as just doing that was a bit optimistic...
The tree iteration for running tasks got me 4 tasks so it obviously
didn't get very far; I probably missed something obvious.
For now I wanted to debug something else so went back a notch instead of
trying harder, I'll probably come back to this in the next few weeks if
nobody else has. Don't wait for me if you want to do it though :)
(hopefully that'll save someone a few minutes if they run into this
meanwhile)
Hi Dominique,
Thanks for the heads-up -- this is a critical change w/respect to
the crash utility, affecting several other parts as well as the
PID/task gathering mechanism. I don't have access to 4.20-rc1
kernels in-house, or from Fedora, at the moment, so I won't be able
to do any hands-on work on it for a while. So given the insights
you've gained already, by all means please continue if you can!
Thanks,
Dave
Cheers,
--
Dominique Martinet | Asmadeus
--
Crash-utility mailing list
Crash-utility(a)redhat.com
https://www.redhat.com/mailman/listinfo/crash-utility
10:55 p.m.
New subject: [PATCH for testing only] Make radix tree compatible with 4.20-rc1 xarray
radix trees got replaced with xarrays in 4.20-rc1's f8d5d0cc145
("xarray: Add definition of struct xarray") and 01959dfe77 ("xarray:
Define struct xa_node")
Attempt to detect and support this.
---
Dave Anderson wrote on Tue, Oct 30, 2018:
Thanks for the heads-up -- this is a critical change w/respect to
the crash utility, affecting several other parts as well as the
PID/task gathering mechanism. I don't have access to 4.20-rc1
kernels in-house, or from Fedora, at the moment, so I won't be able
to do any hands-on work on it for a while. So given the insights
you've gained already, by all means please continue if you can!
4.20-rc1 was not released yet so this isn't surprising :)
It came out just this weekend, should probably hit rawhide soon.
Meanwhile I had a second look (thanks for reminding me about the
`--active` switch, I can play with `tree -t radix` more easily now); I
had missed a couple more things with my initial test.
Basically, we need to:
- fall back radix_tree_root to xarray, radix_tree_node to xa_node,
radix_tree_root_rnode to xarray's xa_head, radix_tree_node_slots to
xa_node's slots, radix_tree_node_shift to xa_node's shift
- does not seem to be a max_height anymore
- RADIX_TREE_INTERNAL_NODE changed from 1 to 2 (linux code: that 2 is
hardcoded in include/linux/xarray.h xa_mk_node and xa_to_node...)
The XA_CHUNK_MASK that replaces RADIX_TREE_ENTRY_MASK is bigger but
I didn't need to change that.
To use the same code with both radix tree and xarray, I'm now clearing
the entry mask instead of the interna node bit.
- the second thing I had missed was `MEMBER_SIZE("radix_tree_node",
"slots")` in do_radix_tree_iter as it wasn't with the other fields, need
to fallback to xa_node's slots here as well.
the check !(nlen = MEMBER_SIZE(...)) isn't correct as MEMBER_SIZE will
return -1 on failure, so comparing to 0 might be better.
So ultimately I can get crash to start with the attached patch, but this
is definitely more of monkeying around than a real fix.
One thing I'm not sure about in particular is if the radix tree/xarray
contains values instead of pointers some of the internal bits changed,
but we do not seem to handle that for radix trees right now so it might
not matter...?
Anyway, patch tested on 4.20-rc1, and fedora's 4.18.16-200.fc28.x86_64.
As said previously it probably warrants more testing on 4.20-rc1 and
possibly older centos/rhel kernels, I don't think any of the tree I
tried was multiple levels deep for example...
Please consider it a "FYI" patch more than anything else :)
task.c | 9 +++++++++
tools.c | 23 +++++++++++------------
2 files changed, 20 insertions(+), 12 deletions(-)
diff --git a/task.c b/task.c
index 1eecfce..34327c2 100644
--- a/task.c
+++ b/task.c
@@ -485,6 +485,15 @@ task_init(void)
"radix_tree_node","height");
MEMBER_OFFSET_INIT(radix_tree_node_shift,
"radix_tree_node","shift");
+ } else {
+ STRUCT_SIZE_INIT(radix_tree_root, "xarray");
+ STRUCT_SIZE_INIT(radix_tree_node, "xa_node");
+ MEMBER_OFFSET_INIT(radix_tree_root_rnode,
+ "xarray","xa_head");
+ MEMBER_OFFSET_INIT(radix_tree_node_slots,
+ "xa_node","slots");
+ MEMBER_OFFSET_INIT(radix_tree_node_shift,
+ "xa_node","shift");
}
if (symbol_exists("pidhash") && symbol_exists("pid_hash")
&&
diff --git a/tools.c b/tools.c
index 634aec6..33d3787 100644
--- a/tools.c
+++ b/tools.c
@@ -4415,7 +4415,6 @@ static ulong RADIX_TREE_MAP_SIZE = UNINITIALIZED;
static ulong RADIX_TREE_MAP_MASK = UNINITIALIZED;
#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)
@@ -4436,8 +4435,8 @@ static void do_radix_tree_iter(ulong node, uint height, char *path,
if (!slot)
continue;
- if (slot & RADIX_TREE_INTERNAL_NODE)
- slot &= ~RADIX_TREE_INTERNAL_NODE;
+ if (slot & RADIX_TREE_ENTRY_MASK)
+ slot &= ~RADIX_TREE_ENTRY_MASK;
if (height == 1)
ops->entry(node, slot, path, index | off, ops->private);
@@ -4467,13 +4466,13 @@ int do_radix_tree_traverse(ulong ptr, int is_root, struct
radix_tree_ops *ops)
!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))))
+ !VALID_MEMBER(radix_tree_node_slots))))
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")))
+ if ((nlen = MEMBER_SIZE("radix_tree_node", "slots")) <= 0
&&
+ (nlen = MEMBER_SIZE("xa_node", "slots")) <= 0)
error(FATAL, "cannot determine length of "
"radix_tree_node.slots[] array\n");
nlen /= sizeof(void *);
@@ -4483,7 +4482,7 @@ int do_radix_tree_traverse(ulong ptr, int is_root, struct
radix_tree_ops *ops)
if (ARRAY_LENGTH(height_to_maxindex))
max_height = ARRAY_LENGTH(height_to_maxindex);
- else
+ else if (ARRAY_LENGTH(height_to_maxnodes))
max_height = ARRAY_LENGTH(height_to_maxnodes);
}
@@ -4491,8 +4490,8 @@ int do_radix_tree_traverse(ulong ptr, int is_root, struct
radix_tree_ops *ops)
if (!is_root) {
node_p = ptr;
- if (node_p & RADIX_TREE_INTERNAL_NODE)
- node_p &= ~RADIX_TREE_INTERNAL_NODE;
+ if (node_p & RADIX_TREE_ENTRY_MASK)
+ node_p &= ~RADIX_TREE_ENTRY_MASK;
if (VALID_MEMBER(radix_tree_node_height)) {
readmem(node_p + OFFSET(radix_tree_node_height), KVADDR,
@@ -4516,9 +4515,9 @@ int do_radix_tree_traverse(ulong ptr, int is_root, struct
radix_tree_ops *ops)
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;
+ is_internal = (node_p & RADIX_TREE_ENTRY_MASK);
+ if (node_p & RADIX_TREE_ENTRY_MASK)
+ node_p &= ~RADIX_TREE_ENTRY_MASK;
if (is_internal && VALID_MEMBER(radix_tree_node_shift)) {
readmem(node_p + OFFSET(radix_tree_node_shift), KVADDR, &shift,
--
2.19.1
9:23 a.m.
New subject: [PATCH for testing only] Make radix tree compatible with 4.20-rc1 xarray
----- Original Message -----
radix trees got replaced with xarrays in 4.20-rc1's f8d5d0cc145
("xarray: Add definition of struct xarray") and 01959dfe77 ("xarray:
Define struct xa_node")
Attempt to detect and support this.
---
Dave Anderson wrote on Tue, Oct 30, 2018:
> Thanks for the heads-up -- this is a critical change w/respect to
> the crash utility, affecting several other parts as well as the
> PID/task gathering mechanism. I don't have access to 4.20-rc1
> kernels in-house, or from Fedora, at the moment, so I won't be able
> to do any hands-on work on it for a while. So given the insights
> you've gained already, by all means please continue if you can!
4.20-rc1 was not released yet so this isn't surprising :)
It came out just this weekend, should probably hit rawhide soon.
Yeah, on Friday the guy in the cube next to me was working with a roll-your-own
kernel from the latest upstream git tree, and he saw the crash problem. I created
a "snap.so" vmcore from it, so I can play around with it for now.
Meanwhile I had a second look (thanks for reminding me about the
`--active` switch, I can play with `tree -t radix` more easily now); I
had missed a couple more things with my initial test.
Basically, we need to:
- fall back radix_tree_root to xarray, radix_tree_node to xa_node,
radix_tree_root_rnode to xarray's xa_head, radix_tree_node_slots to
xa_node's slots, radix_tree_node_shift to xa_node's shift
- does not seem to be a max_height anymore
- RADIX_TREE_INTERNAL_NODE changed from 1 to 2 (linux code: that 2 is
hardcoded in include/linux/xarray.h xa_mk_node and xa_to_node...)
The XA_CHUNK_MASK that replaces RADIX_TREE_ENTRY_MASK is bigger but
I didn't need to change that.
To use the same code with both radix tree and xarray, I'm now clearing
the entry mask instead of the interna node bit.
- the second thing I had missed was `MEMBER_SIZE("radix_tree_node",
"slots")` in do_radix_tree_iter as it wasn't with the other fields, need
to fallback to xa_node's slots here as well.
the check !(nlen = MEMBER_SIZE(...)) isn't correct as MEMBER_SIZE will
return -1 on failure, so comparing to 0 might be better.
So ultimately I can get crash to start with the attached patch, but this
is definitely more of monkeying around than a real fix.
That's awesome -- much appreciated.
I just started looking at the xarray kernel code, and w/respect to the crash
utility, I'm thinking it's probably worth biting the bullet and creating
a set of analogous xarray functions/structures/#define's that are similar
in nature (identical except in name in most cases) to the set of exported
radix tree functions/structures/#define's.
Yes, the new pieces will in most places be essentially the same as the
radix tree versions, but the alternative of "hiding" the xarray kernel facility
behind a bunch of radix tree functions and structures is disconcerting.
While it is true that there are many trivial examples in the crash code where,
say, an offset_table entry whose kernel name has changed still conditionally
utilizes the old entry name, but in this case, it's a complete kernel subsystem
whose purpose is to pretty much replace the radix tree. So looking down the line,
it seems reasonable and cleaner to separate the two facilities in the crash utility
support code.
But anyway, let's get it working first!
One thing I'm not sure about in particular is if the radix
tree/xarray
contains values instead of pointers some of the internal bits changed,
but we do not seem to handle that for radix trees right now so it might
not matter...?
That's what the RADIX_TREE_EXCEPTIONAL_ENTRY items are, right? Granted,
I never ran into one until recently when I bumped into a value instead
of a pointer when running "files -p":
commit b9df4d156838b4e8aa2b2f51aff3460a1c61f6a8
Author: Dave Anderson <anderson(a)redhat.com>
Date: Thu Sep 6 14:01:28 2018 -0400
Fix for the "files -p <inode>" option. Without the patch, the
command attempts to translate radix tree node slot entries that
are RADIX_TREE_EXCEPTIONAL_ENTRY types, and as a result may fail
prematurely with an error message of the sort "files: do_radix_tree:
callback operation failed: entry: 5 item: 44788c5000a".
(anderson(a)redhat.com)
Anyway, patch tested on 4.20-rc1, and fedora's 4.18.16-200.fc28.x86_64.
As said previously it probably warrants more testing on 4.20-rc1 and
possibly older centos/rhel kernels, I don't think any of the tree I
tried was multiple levels deep for example...
Please consider it a "FYI" patch more than anything else :)
Cool -- no problem. Again, thanks again for digging into this.
Dave
task.c | 9 +++++++++
tools.c | 23 +++++++++++------------
2 files changed, 20 insertions(+), 12 deletions(-)
diff --git a/task.c b/task.c
index 1eecfce..34327c2 100644
--- a/task.c
+++ b/task.c
@@ -485,6 +485,15 @@ task_init(void)
"radix_tree_node","height");
MEMBER_OFFSET_INIT(radix_tree_node_shift,
"radix_tree_node","shift");
+ } else {
+ STRUCT_SIZE_INIT(radix_tree_root, "xarray");
+ STRUCT_SIZE_INIT(radix_tree_node, "xa_node");
+ MEMBER_OFFSET_INIT(radix_tree_root_rnode,
+ "xarray","xa_head");
+ MEMBER_OFFSET_INIT(radix_tree_node_slots,
+ "xa_node","slots");
+ MEMBER_OFFSET_INIT(radix_tree_node_shift,
+ "xa_node","shift");
}
if (symbol_exists("pidhash") && symbol_exists("pid_hash")
&&
diff --git a/tools.c b/tools.c
index 634aec6..33d3787 100644
--- a/tools.c
+++ b/tools.c
@@ -4415,7 +4415,6 @@ static ulong RADIX_TREE_MAP_SIZE = UNINITIALIZED;
static ulong RADIX_TREE_MAP_MASK = UNINITIALIZED;
#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)
@@ -4436,8 +4435,8 @@ static void do_radix_tree_iter(ulong node, uint height,
char *path,
if (!slot)
continue;
- if (slot & RADIX_TREE_INTERNAL_NODE)
- slot &= ~RADIX_TREE_INTERNAL_NODE;
+ if (slot & RADIX_TREE_ENTRY_MASK)
+ slot &= ~RADIX_TREE_ENTRY_MASK;
if (height == 1)
ops->entry(node, slot, path, index | off, ops->private);
@@ -4467,13 +4466,13 @@ int do_radix_tree_traverse(ulong ptr, int is_root,
struct radix_tree_ops *ops)
!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))))
+ !VALID_MEMBER(radix_tree_node_slots))))
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")))
+ if ((nlen = MEMBER_SIZE("radix_tree_node", "slots")) <= 0
&&
+ (nlen = MEMBER_SIZE("xa_node", "slots")) <= 0)
error(FATAL, "cannot determine length of "
"radix_tree_node.slots[] array\n");
nlen /= sizeof(void *);
@@ -4483,7 +4482,7 @@ int do_radix_tree_traverse(ulong ptr, int is_root,
struct radix_tree_ops *ops)
if (ARRAY_LENGTH(height_to_maxindex))
max_height = ARRAY_LENGTH(height_to_maxindex);
- else
+ else if (ARRAY_LENGTH(height_to_maxnodes))
max_height = ARRAY_LENGTH(height_to_maxnodes);
}
@@ -4491,8 +4490,8 @@ int do_radix_tree_traverse(ulong ptr, int is_root,
struct radix_tree_ops *ops)
if (!is_root) {
node_p = ptr;
- if (node_p & RADIX_TREE_INTERNAL_NODE)
- node_p &= ~RADIX_TREE_INTERNAL_NODE;
+ if (node_p & RADIX_TREE_ENTRY_MASK)
+ node_p &= ~RADIX_TREE_ENTRY_MASK;
if (VALID_MEMBER(radix_tree_node_height)) {
readmem(node_p + OFFSET(radix_tree_node_height), KVADDR,
@@ -4516,9 +4515,9 @@ int do_radix_tree_traverse(ulong ptr, int is_root,
struct radix_tree_ops *ops)
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;
+ is_internal = (node_p & RADIX_TREE_ENTRY_MASK);
+ if (node_p & RADIX_TREE_ENTRY_MASK)
+ node_p &= ~RADIX_TREE_ENTRY_MASK;
if (is_internal && VALID_MEMBER(radix_tree_node_shift)) {
readmem(node_p + OFFSET(radix_tree_node_shift), KVADDR, &shift,
--
2.19.1
5:27 p.m.
New subject: [PATCH for testing only] Make radix tree compatible with 4.20-rc1 xarray
Dave Anderson wrote on Mon, Nov 05, 2018:
> 4.20-rc1 was not released yet so this isn't surprising :)
> It came out just this weekend, should probably hit rawhide soon.
Yeah, on Friday the guy in the cube next to me was working with a roll-your-own
kernel from the latest upstream git tree, and he saw the crash problem. I created
a "snap.so" vmcore from it, so I can play around with it for now.
Oh, another handy extension I didn't know about; will need to play with
this on bigger servers when we have a transient issue to see how it
performs, it's always annoying to do a voluntary crash when we could go
on without it :)
I just started looking at the xarray kernel code, and w/respect to
the crash
utility, I'm thinking it's probably worth biting the bullet and creating
a set of analogous xarray functions/structures/#define's that are similar
in nature (identical except in name in most cases) to the set of exported
radix tree functions/structures/#define's.
Yes, the new pieces will in most places be essentially the same as the
radix tree versions, but the alternative of "hiding" the xarray kernel
facility
behind a bunch of radix tree functions and structures is disconcerting.
Yeah, ultimately I pretty much agree there; it's just close enough to be
alluring to merge but long-term it's definitely better to duplicate the
code.
Past the confusion of hiding the name (we could just alias functions if
that's all it was); Matthew was talking about further modifying the
xarray code so adding hacks on top of other hacks will be more difficult
to understand if we don't do that.
That's what the RADIX_TREE_EXCEPTIONAL_ENTRY items are, right?
Granted,
I never ran into one until recently when I bumped into a value instead
of a pointer when running "files -p":
Ah, that looks right. I think xarray is much more flexible with these,
letting users use any of the first two bits as they please except for
'2' (the new internal value bit); see xa_tag_pointer for example:
* If the user of the XArray prefers, they can tag their pointers instead
* of storing value entries. Three tags are available (0, 1 and 3).
* These are distinct from the xa_mark_t as they are not replicated up
* through the array and cannot be searched for.
--
Dominique
2063
days inactive
2069
days old
devel@lists.crash-utility.osci.io
4 comments
2 participants
participants (2)
-
Dave Anderson -
Dominique Martinet