[PATCH] xen/arm: bootfdt: Always sort memory banks

[Oleksandr Tyshchenko <olekstysh@gmail.com>]

From: Oleksandr Tyshchenko <oleksandr_tyshchenko@epam.com>

At the moment, Xen expects the memory banks to be ordered.
Unfortunately, there may be a case when updated by firmware
device tree contains unordered banks. This means Xen will panic
when setting xenheap mappings for the subsequent bank with start
address being less than xenheap_mfn_start (start address of
the first bank).

As there is no clear requirment regarding ordering in the device
tree, update code to be able to deal with by sorting memory
banks if we have more than one.

Suggested-by: Julien Grall <jgrall@amazon.com>
Signed-off-by: Oleksandr Tyshchenko <oleksandr_tyshchenko@epam.com>
---

The proposed commit fixes the booting Xen on R-Car M3-W+ SoC:

Starting kernel ...
- UART enabled -
- Boot CPU booting -
- Current EL 00000008 -
- Initialize CPU -
- Turning on paging -
- Zero BSS -
- Ready -
(XEN) Checking for initrd in /chosen
(XEN) Initrd 0000000084000040-0000000085dbc32a
(XEN) RAM: 0000000480000000 - 00000004ffffffff
(XEN) RAM: 0000000048000000 - 00000000bfffffff
(XEN) RAM: 0000000600000000 - 00000006ffffffff

...

(XEN) ****************************************
(XEN) Panic on CPU 0:
(XEN) cannot add xenheap mapping at 48000 below heap start 480000
(XEN) ****************************************
(XEN) 
(XEN) Reboot in five seconds...
---
 xen/arch/arm/bootfdt.c | 22 ++++++++++++++++++++++
 1 file changed, 22 insertions(+)

diff --git a/xen/arch/arm/bootfdt.c b/xen/arch/arm/bootfdt.c
index dcff512..3ef63b3 100644
--- a/xen/arch/arm/bootfdt.c
+++ b/xen/arch/arm/bootfdt.c
@@ -13,6 +13,7 @@
 #include <xen/init.h>
 #include <xen/device_tree.h>
 #include <xen/libfdt/libfdt.h>
+#include <xen/sort.h>
 #include <xsm/xsm.h>
 #include <asm/setup.h>
 
@@ -395,6 +396,21 @@ static void __init early_print_info(void)
     printk("\n");
 }
 
+/* This function assumes that memory regions are not overlapped */
+static int __init cmp_memory_node(const void *key, const void *elem)
+{
+    const struct membank *handler0 = key;
+    const struct membank *handler1 = elem;
+
+    if ( handler0->start < handler1->start )
+        return -1;
+
+    if ( handler0->start >= (handler1->start + handler1->size) )
+        return 1;
+
+    return 0;
+}
+
 /**
  * boot_fdt_info - initialize bootinfo from a DTB
  * @fdt: flattened device tree binary
@@ -412,6 +428,12 @@ size_t __init boot_fdt_info(const void *fdt, paddr_t paddr)
     add_boot_module(BOOTMOD_FDT, paddr, fdt_totalsize(fdt), false);
 
     device_tree_for_each_node((void *)fdt, 0, early_scan_node, NULL);
+    if ( bootinfo.mem.nr_banks > 1 )
+    {
+        /* Some DT may describe unordered banks, sort them in ascending order */
+        sort(bootinfo.mem.bank, bootinfo.mem.nr_banks, sizeof(struct membank),
+             cmp_memory_node, NULL);
+    }
     early_print_info();
 
     return fdt_totalsize(fdt);
-- 
2.7.4