Skip to contentSkip to conversation

libfdt / fdt_check_node_offset_ with VALID_INPUT

DISCUSSION Frank Mehnert 3 participants 5 messages Aug 12, 2020 – Aug 20, 2020 2 messages not in the archive

lore
Share & tools
lore
#0 lore raw

Hi all,

I'm not sure if I found a bug or if I mis-use libfdt.

I have a valid Linux device tree in memory and want to recursively scan thru it. The device tree contains a root node and several subnodes.

First, I start with the root node:

  int root = fdt_next_node(fdt, -1, NULL);

Here, root is set to 0. Now I determine the offset of the first sub node:

  int subnode = fdt_first_subnode(fdt, root);

Here, subnode is either 0 if FDT_ASSUME_MASK contains ASSUME_VALID_INPUT or 164 (in my case) if FDT_ASSUME_MASK does not contain ASSUME_VALID_INPUT.

As far as I understand, fdt_first_subnode() should not return the node offset of the current node if there are subnodes available.

I think the problem origins at fdt_check_node_offset_() in fdt.c: If VALID_INPUT is set, the whole code in that function is skipped. If that flag is not set then fdt_next_tag(fdt, offset, &offset) is called and the resulting 'offset' is returned.

In other words, fdt_check_node_offset_() has a side effect which depends on the VALID_INPUT flag.

Thanks!

Frank

#1 lore raw
Quoted 10 lines · Frank Mehnert

Hi all,

I'm not sure if I found a bug or if I mis-use libfdt.

I have a valid Linux device tree in memory and want to recursively scan thru it. The device tree contains a root node and several subnodes.

First, I start with the root node:

  int root = fdt_next_node(fdt, -1, NULL);

Tangential aside: the offset of the root node is *always* 0, you don't need to "find" it with code like this.

Quoted 6 lines

Here, root is set to 0. Now I determine the offset of the first sub node:

  int subnode = fdt_first_subnode(fdt, root);

Here, subnode is either 0 if FDT_ASSUME_MASK contains ASSUME_VALID_INPUT or 164 (in my case) if FDT_ASSUME_MASK does not contain ASSUME_VALID_INPUT.

That certainly sounds like a bug. Adding things to FDT_ASSUME_MASK shouldn't change behaviour for valid inputs.

Quoted 2 lines

As far as I understand, fdt_first_subnode() should not return the node offset of the current node if there are subnodes available.

That's correct.

Quoted 7 lines

I think the problem origins at fdt_check_node_offset_() in fdt.c: If VALID_INPUT is set, the whole code in that function is skipped. If that flag is not set then fdt_next_tag(fdt, offset, &offset) is called and the resulting 'offset' is returned.

In other words, fdt_check_node_offset_() has a side effect which depends on the VALID_INPUT flag.

Right. Looks like the problem is that the next if *looks* like just an error/sanity check, which can_assume(VALID_INPUT) is bypassing. However, it also has the fdt_next_tag() call which alters offset.

I was afraid of this sort of thing when we added the assumptions stuff. Really we need to be running the testsuite with different assumptions masks, but it's fiddly to do.

Care to send a patch?

[Another aside: why are you using ASSUME_VALID_INPUT - it's really only of value if you have to run your code in an *extremely* space limited environment, I don't recommend it as a rule]

Signature · 4 lines
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson

A message that is not in the archive (sent off-list or not yet received): [email protected]

#3 lore raw

Hi David,

Quoted 37 lines · On Donnerstag, 13. August 2020 09:09:45 CEST David Gibson wrote:
Quoted 9 lines · Frank Mehnert

Hi all,

I'm not sure if I found a bug or if I mis-use libfdt.

I have a valid Linux device tree in memory and want to recursively scan thru it. The device tree contains a root node and several subnodes.

First, I start with the root node:
int root = fdt_next_node(fdt, -1, NULL);

Tangential aside: the offset of the root node is *always* 0, you don't need to "find" it with code like this.

Quoted 6 lines

Here, root is set to 0. Now I determine the offset of the first sub node:
int subnode = fdt_first_subnode(fdt, root);

Here, subnode is either 0 if FDT_ASSUME_MASK contains ASSUME_VALID_INPUT or 164 (in my case) if FDT_ASSUME_MASK does not contain ASSUME_VALID_INPUT.

That certainly sounds like a bug. Adding things to FDT_ASSUME_MASK shouldn't change behaviour for valid inputs.

Quoted 2 lines

As far as I understand, fdt_first_subnode() should not return the node offset of the current node if there are subnodes available.

That's correct.

Quoted 7 lines

I think the problem origins at fdt_check_node_offset_() in fdt.c: If VALID_INPUT is set, the whole code in that function is skipped. If that flag is not set then fdt_next_tag(fdt, offset, &offset) is called and the resulting 'offset' is returned.

In other words, fdt_check_node_offset_() has a side effect which depends on the VALID_INPUT flag.

Quoted 7 lines

Right. Looks like the problem is that the next if *looks* like just an error/sanity check, which can_assume(VALID_INPUT) is bypassing. However, it also has the fdt_next_tag() call which alters offset.

I was afraid of this sort of thing when we added the assumptions stuff. Really we need to be running the testsuite with different assumptions masks, but it's fiddly to do.

Thank you for these explanations!

Quoted 1 line

Care to send a patch?

Done in a separate e-mail. Please forgive me if the format is not 100% correct.

Quoted 3 lines

[Another aside: why are you using ASSUME_VALID_INPUT - it's really only of value if you have to run your code in an *extremely* space limited environment, I don't recommend it as a rule]

Actually we are using libfdt for parsing and altering the device tree before starting a Linux guest in a virtual machine. The setup is kind of static, that is, we can assume that the device tree is valid for the setup.

Parsing and altering the device tree is part of the setup boot time which we need to keep low. Therefore I investigated several approaches to speed up parsing and to prevent expensive operations.

I'm completely aware that libfdt is not made for benchmarks and in time-critical scenarios it would be probably better to read the device tree, create an internal tree representation in memory of it, then do the required modifications and finally create a new device tree from memory and use that blob for the guest.

However, so far we didn't want to take the effort of such a project, because that also requires test cases and proves of correctness.

Thanks

Frank

Signature · 4 lines
Dr.-Ing. Frank Mehnert, [email protected], +49-351-41 883 224

Kernkonzept GmbH.  Sitz: Dresden.  Amtsgericht Dresden, HRB 31129.
Geschäftsführer: Dr.-Ing. Michael Hohmuth
#4 lore raw
Quoted 69 lines · Frank Mehnert

Hi David,

Quoted 37 lines · On Donnerstag, 13. August 2020 09:09:45 CEST David Gibson wrote:
Quoted 9 lines · Frank Mehnert

Hi all,

I'm not sure if I found a bug or if I mis-use libfdt.

I have a valid Linux device tree in memory and want to recursively scan thru it. The device tree contains a root node and several subnodes.

First, I start with the root node:
int root = fdt_next_node(fdt, -1, NULL);

Tangential aside: the offset of the root node is *always* 0, you don't need to "find" it with code like this.

Quoted 6 lines

Here, root is set to 0. Now I determine the offset of the first sub node:
int subnode = fdt_first_subnode(fdt, root);

Here, subnode is either 0 if FDT_ASSUME_MASK contains ASSUME_VALID_INPUT or 164 (in my case) if FDT_ASSUME_MASK does not contain ASSUME_VALID_INPUT.

That certainly sounds like a bug. Adding things to FDT_ASSUME_MASK shouldn't change behaviour for valid inputs.

Quoted 2 lines

As far as I understand, fdt_first_subnode() should not return the node offset of the current node if there are subnodes available.

That's correct.

Quoted 7 lines

I think the problem origins at fdt_check_node_offset_() in fdt.c: If VALID_INPUT is set, the whole code in that function is skipped. If that flag is not set then fdt_next_tag(fdt, offset, &offset) is called and the resulting 'offset' is returned.

In other words, fdt_check_node_offset_() has a side effect which depends on the VALID_INPUT flag.

Quoted 7 lines

Right. Looks like the problem is that the next if *looks* like just an error/sanity check, which can_assume(VALID_INPUT) is bypassing. However, it also has the fdt_next_tag() call which alters offset.

I was afraid of this sort of thing when we added the assumptions stuff. Really we need to be running the testsuite with different assumptions masks, but it's fiddly to do.

Thank you for these explanations!

Quoted 1 line

Care to send a patch?

Done in a separate e-mail. Please forgive me if the format is not 100% correct.

Quoted 3 lines

[Another aside: why are you using ASSUME_VALID_INPUT - it's really only of value if you have to run your code in an *extremely* space limited environment, I don't recommend it as a rule]

Actually we are using libfdt for parsing and altering the device tree before starting a Linux guest in a virtual machine. The setup is kind of static, that is, we can assume that the device tree is valid for the setup.

Parsing and altering the device tree is part of the setup boot time which we need to keep low. Therefore I investigated several approaches to speed up parsing and to prevent expensive operations.

Quoted 8 lines

I'm completely aware that libfdt is not made for benchmarks and in time-critical scenarios it would be probably better to read the device tree, create an internal tree representation in memory of it, then do the required modifications and finally create a new device tree from memory and use that blob for the guest.

However, so far we didn't want to take the effort of such a project, because that also requires test cases and proves of correctness.

FYI, there's been some related discussions related to this (mostly at past Linux Plumbers). One idea is to extend the FDT format to append overlays rather than applying them in place to the FDT (which is probably also slow). Then the overlays can be applied later in boot on an unflattened tree. The other is creating a 'libdt' as a common API to work on unflattened DTs. dtc has its own unflattened representation and so does the Linux kernel. Both implementations would need relicensing as we'd want it dual licensed. The kernel one is more featureful, but the dtc one would be easier to relicense.

Rob

A message that is not in the archive (sent off-list or not yet received): CAL_JsqLAWa-wMMiD=VffemMiqAv-3=GNehNojWrFQqED_+QDow-JsoAwUIsXosN+BqQ9rBEUg@public.gmane.org

#6 lore raw
Quoted 77 lines · Rob Herring
Quoted 75 lines · Frank Mehnert

Hi David,

Quoted 37 lines · On Donnerstag, 13. August 2020 09:09:45 CEST David Gibson wrote:
Quoted 9 lines · Frank Mehnert

Hi all,

I'm not sure if I found a bug or if I mis-use libfdt.

I have a valid Linux device tree in memory and want to recursively scan thru it. The device tree contains a root node and several subnodes.

First, I start with the root node:
int root = fdt_next_node(fdt, -1, NULL);

Tangential aside: the offset of the root node is *always* 0, you don't need to "find" it with code like this.

Quoted 6 lines

Here, root is set to 0. Now I determine the offset of the first sub node:
int subnode = fdt_first_subnode(fdt, root);

Here, subnode is either 0 if FDT_ASSUME_MASK contains ASSUME_VALID_INPUT or 164 (in my case) if FDT_ASSUME_MASK does not contain ASSUME_VALID_INPUT.

That certainly sounds like a bug. Adding things to FDT_ASSUME_MASK shouldn't change behaviour for valid inputs.

Quoted 2 lines

As far as I understand, fdt_first_subnode() should not return the node offset of the current node if there are subnodes available.

That's correct.

Quoted 7 lines

I think the problem origins at fdt_check_node_offset_() in fdt.c: If VALID_INPUT is set, the whole code in that function is skipped. If that flag is not set then fdt_next_tag(fdt, offset, &offset) is called and the resulting 'offset' is returned.

In other words, fdt_check_node_offset_() has a side effect which depends on the VALID_INPUT flag.

Quoted 7 lines

Right. Looks like the problem is that the next if *looks* like just an error/sanity check, which can_assume(VALID_INPUT) is bypassing. However, it also has the fdt_next_tag() call which alters offset.

I was afraid of this sort of thing when we added the assumptions stuff. Really we need to be running the testsuite with different assumptions masks, but it's fiddly to do.

Thank you for these explanations!

Quoted 1 line

Care to send a patch?

Done in a separate e-mail. Please forgive me if the format is not 100% correct.

Quoted 3 lines

[Another aside: why are you using ASSUME_VALID_INPUT - it's really only of value if you have to run your code in an *extremely* space limited environment, I don't recommend it as a rule]

Actually we are using libfdt for parsing and altering the device tree before starting a Linux guest in a virtual machine. The setup is kind of static, that is, we can assume that the device tree is valid for the setup.

Parsing and altering the device tree is part of the setup boot time which we need to keep low. Therefore I investigated several approaches to speed up parsing and to prevent expensive operations.

I'm completely aware that libfdt is not made for benchmarks and in time-critical scenarios it would be probably better to read the device tree, create an internal tree representation in memory of it, then do the required modifications and finally create a new device tree from memory and use that blob for the guest.

Quoted 7 lines
Quoted 2 lines

However, so far we didn't want to take the effort of such a project, because that also requires test cases and proves of correctness.

FYI, there's been some related discussions related to this (mostly at past Linux Plumbers). One idea is to extend the FDT format to append overlays rather than applying them in place to the FDT (which is probably also slow).

Hm, I don't really see what a format extension would give you over just giving a bundle of dtbs concatenated.

Quoted 6 lines

Then the overlays can be applied later in boot on
an unflattened tree. The other is creating a 'libdt' as a common API to work on unflattened DTs. dtc has its own unflattened representation and so does the Linux kernel. Both implementations would need relicensing as we'd want it dual licensed. The kernel one is more featureful, but the dtc one would be easier to relicense.

I tend to think the dtc implementation isn't really suitable for general usage. It's augmented with a bunch of extra information that's important to it as a compiler but not really for any other purpose.

That said, actually writing a live dt implementation is almost trivial. What's hard is designing a good interface for it that's flexible enough to cover the use cases without become too complex to set up and use.

Signature · 4 lines
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson