[v2,2/2] of: reserved_mem: Use stable allocation order

Message ID 20230510-dt-resv-bottom-up-v2-2-aeb2afc8ac25@gerhold.net
State New
Headers
Series of: reserved_mem: Improve range allocations |

Commit Message

Stephan Gerhold June 14, 2023, 7:20 p.m. UTC
  sort() in Linux is based on heapsort which is not a stable sort
algorithm - equal elements are being reordered. For reserved memory in
the device tree this happens mainly for dynamic allocations: They do not
have an address to sort with, so they are reordered somewhat randomly
when adding/removing other unrelated reserved memory nodes.

Functionally this is not a big problem, but it's confusing during
development when all the addresses change after adding unrelated
reserved memory nodes.

Make the order stable by sorting dynamic allocations according to
the node order in the device tree. Static allocations are not affected
by this because they are still sorted by their (fixed) address.

Signed-off-by: Stephan Gerhold <stephan@gerhold.net>
---
 drivers/of/of_reserved_mem.c | 5 +++++
 1 file changed, 5 insertions(+)
  

Comments

Rob Herring June 20, 2023, 3:35 p.m. UTC | #1
On Wed, 14 Jun 2023 21:20:43 +0200, Stephan Gerhold wrote:
> sort() in Linux is based on heapsort which is not a stable sort
> algorithm - equal elements are being reordered. For reserved memory in
> the device tree this happens mainly for dynamic allocations: They do not
> have an address to sort with, so they are reordered somewhat randomly
> when adding/removing other unrelated reserved memory nodes.
> 
> Functionally this is not a big problem, but it's confusing during
> development when all the addresses change after adding unrelated
> reserved memory nodes.
> 
> Make the order stable by sorting dynamic allocations according to
> the node order in the device tree. Static allocations are not affected
> by this because they are still sorted by their (fixed) address.
> 
> Signed-off-by: Stephan Gerhold <stephan@gerhold.net>
> ---
>  drivers/of/of_reserved_mem.c | 5 +++++
>  1 file changed, 5 insertions(+)
> 

Applied, thanks!
  

Patch

diff --git a/drivers/of/of_reserved_mem.c b/drivers/of/of_reserved_mem.c
index 7f892c3dcc63..7ec94cfcbddb 100644
--- a/drivers/of/of_reserved_mem.c
+++ b/drivers/of/of_reserved_mem.c
@@ -268,6 +268,11 @@  static int __init __rmem_cmp(const void *a, const void *b)
 	if (ra->size > rb->size)
 		return 1;
 
+	if (ra->fdt_node < rb->fdt_node)
+		return -1;
+	if (ra->fdt_node > rb->fdt_node)
+		return 1;
+
 	return 0;
 }