From: Luca Fancellu <luca.fancellu@arm.com>
To: xen-devel@lists.xenproject.org
Cc: Stefano Stabellini <sstabellini@kernel.org>,
Julien Grall <julien@xen.org>,
Bertrand Marquis <bertrand.marquis@arm.com>,
Michal Orzel <michal.orzel@amd.com>,
Volodymyr Babchuk <Volodymyr_Babchuk@epam.com>
Subject: [RFC PATCH 2/2] xen/arm: Rework dt_unreserved_regions to avoid recursion
Date: Thu, 25 Apr 2024 14:11:19 +0100 [thread overview]
Message-ID: <20240425131119.2299629-3-luca.fancellu@arm.com> (raw)
In-Reply-To: <20240425131119.2299629-1-luca.fancellu@arm.com>
The function dt_unreserved_regions is currently using recursion
to compute the non overlapping ranges of a passed region against
the reserved memory banks, in the spirit of removing the recursion
to improve safety and also improve the scalability of the function,
rework its code to use an iterative algorithm with the same result.
The function was taking an additional parameter 'first', but given
the rework and given that the function was always initially called
with this parameter as zero, remove the parameter and update the
codebase to reflect the change.
Signed-off-by: Luca Fancellu <luca.fancellu@arm.com>
---
xen/arch/arm/include/asm/setup.h | 8 +-
xen/arch/arm/include/asm/static-shmem.h | 7 +-
xen/arch/arm/kernel.c | 2 +-
xen/arch/arm/setup.c | 133 ++++++++++++++++--------
4 files changed, 96 insertions(+), 54 deletions(-)
diff --git a/xen/arch/arm/include/asm/setup.h b/xen/arch/arm/include/asm/setup.h
index fc6967f9a435..24519b9ed969 100644
--- a/xen/arch/arm/include/asm/setup.h
+++ b/xen/arch/arm/include/asm/setup.h
@@ -9,7 +9,12 @@
#define MAX_FDT_SIZE SZ_2M
#define NR_MEM_BANKS 256
+
+#ifdef CONFIG_STATIC_SHM
#define NR_SHMEM_BANKS 32
+#else
+#define NR_SHMEM_BANKS 0
+#endif
#define MAX_MODULES 32 /* Current maximum useful modules */
@@ -215,8 +220,7 @@ void create_dom0(void);
void discard_initial_modules(void);
void fw_unreserved_regions(paddr_t s, paddr_t e,
- void (*cb)(paddr_t ps, paddr_t pe),
- unsigned int first);
+ void (*cb)(paddr_t ps, paddr_t pe));
size_t boot_fdt_info(const void *fdt, paddr_t paddr);
const char *boot_fdt_cmdline(const void *fdt);
diff --git a/xen/arch/arm/include/asm/static-shmem.h b/xen/arch/arm/include/asm/static-shmem.h
index 3b6569e5703f..1b7c7ea0e17d 100644
--- a/xen/arch/arm/include/asm/static-shmem.h
+++ b/xen/arch/arm/include/asm/static-shmem.h
@@ -7,11 +7,11 @@
#include <asm/kernel.h>
#include <asm/setup.h>
-#ifdef CONFIG_STATIC_SHM
-
/* Worst case /memory node reg element: (addrcells + sizecells) */
#define DT_MEM_NODE_REG_RANGE_SIZE ((NR_MEM_BANKS + NR_SHMEM_BANKS) * 4)
+#ifdef CONFIG_STATIC_SHM
+
int make_resv_memory_node(const struct kernel_info *kinfo, int addrcells,
int sizecells);
@@ -47,9 +47,6 @@ void shm_mem_node_fill_reg_range(const struct kernel_info *kinfo, __be32 *reg,
#else /* !CONFIG_STATIC_SHM */
-/* Worst case /memory node reg element: (addrcells + sizecells) */
-#define DT_MEM_NODE_REG_RANGE_SIZE (NR_MEM_BANKS * 4)
-
static inline int make_resv_memory_node(const struct kernel_info *kinfo,
int addrcells, int sizecells)
{
diff --git a/xen/arch/arm/kernel.c b/xen/arch/arm/kernel.c
index 674388fa11a2..ecbeec518754 100644
--- a/xen/arch/arm/kernel.c
+++ b/xen/arch/arm/kernel.c
@@ -247,7 +247,7 @@ static __init int kernel_decompress(struct bootmodule *mod, uint32_t offset)
* Free the original kernel, update the pointers to the
* decompressed kernel
*/
- fw_unreserved_regions(addr, addr + size, init_domheap_pages, 0);
+ fw_unreserved_regions(addr, addr + size, init_domheap_pages);
return 0;
}
diff --git a/xen/arch/arm/setup.c b/xen/arch/arm/setup.c
index c4e5c19b11d6..d737fe56e539 100644
--- a/xen/arch/arm/setup.c
+++ b/xen/arch/arm/setup.c
@@ -204,55 +204,97 @@ static void __init processor_id(void)
}
static void __init dt_unreserved_regions(paddr_t s, paddr_t e,
- void (*cb)(paddr_t ps, paddr_t pe),
- unsigned int first)
+ void (*cb)(paddr_t ps, paddr_t pe))
{
- const struct membanks *reserved_mem = bootinfo_get_reserved_mem();
-#ifdef CONFIG_STATIC_SHM
- const struct membanks *shmem = bootinfo_get_shmem();
- unsigned int offset;
-#endif
- unsigned int i;
-
/*
- * i is the current bootmodule we are evaluating across all possible
- * kinds.
+ * The worst case scenario is to have N reserved region ovelapping the
+ * passed one, so having N+1 regions in the stack
*/
- for ( i = first; i < reserved_mem->nr_banks; i++ )
- {
- paddr_t r_s = reserved_mem->bank[i].start;
- paddr_t r_e = r_s + reserved_mem->bank[i].size;
-
- if ( s < r_e && r_s < e )
- {
- dt_unreserved_regions(r_e, e, cb, i + 1);
- dt_unreserved_regions(s, r_s, cb, i + 1);
- return;
- }
- }
-
+ struct {
+ paddr_t s;
+ paddr_t e;
+ unsigned int dict;
+ unsigned int bank;
+ } stack[NR_MEM_BANKS + NR_SHMEM_BANKS + 1];
+ const struct membanks *mem_banks[] = {
+ bootinfo_get_reserved_mem(),
#ifdef CONFIG_STATIC_SHM
- /*
- * When retrieving the corresponding shared memory addresses
- * below, we need to index the shmem->bank starting from 0, hence
- * we need to use i - reserved_mem->nr_banks.
- */
- offset = reserved_mem->nr_banks;
- for ( ; i - offset < shmem->nr_banks; i++ )
+ bootinfo_get_shmem(),
+#endif
+ };
+ unsigned int count = 0;
+ unsigned int i, j;
+
+ /* Push the initial region into the stack */
+ stack[count].s = s;
+ stack[count].e = e;
+ stack[count].dict = 0;
+ stack[count].bank = 0;
+ count++;
+ while ( count > 0 )
{
- paddr_t r_s = shmem->bank[i - offset].start;
- paddr_t r_e = r_s + shmem->bank[i - offset].size;
-
- if ( s < r_e && r_s < e )
+ paddr_t b_s, b_e;
+ /* Take out last element of the stack */
+ count--;
+ i = stack[count].dict;
+ j = stack[count].bank;
+ b_s = stack[count].s;
+ b_e = stack[count].e;
+ /* Start checking for overlapping banks */
+ for ( ; i < ARRAY_SIZE(mem_banks); i++ )
{
- dt_unreserved_regions(r_e, e, cb, i + 1);
- dt_unreserved_regions(s, r_s, cb, i + 1);
- return;
+ for ( ; j < mem_banks[i]->nr_banks; j++ )
+ {
+ paddr_t r_s = mem_banks[i]->bank[j].start;
+ paddr_t r_e = r_s + mem_banks[i]->bank[j].size;
+
+ if ( b_s < r_e && r_s < b_e )
+ {
+ /*
+ * Region is overlapping, push the two non overlap ranges in
+ * the stack
+ */
+ if ( (count + 2) < ARRAY_SIZE(stack) )
+ {
+ /*
+ * Push initial non overlapping part of the region into
+ * the stack
+ */
+ stack[count].s = b_s;
+ stack[count].e = r_s;
+ stack[count].dict = i;
+ stack[count].bank = j + 1;
+ count++;
+ /*
+ * Push last non overlapping part of the region into
+ * the stack
+ */
+ stack[count].s = r_e;
+ stack[count].e = b_e;
+ stack[count].dict = i;
+ stack[count].bank = j + 1;
+ count++;
+ }
+ else
+ panic("dt_unreserved_regions: stack space exausted");
+
+ /*
+ * Retrieve the last region pushed to check against other
+ * banks, so break the loop through the banks and pop
+ * a new region from the stack
+ */
+ goto regions_pushed;
+ }
+ }
+ j = 0;
}
+ /*
+ * This point is reached when the region doesn't overlap with any other
+ * region, so call the callback on it.
+ */
+ cb(b_s, b_e);
+ regions_pushed:
}
-#endif
-
- cb(s, e);
}
/*
@@ -316,11 +358,10 @@ static bool __init bootmodules_overlap_check(struct bootmodules *bootmodules,
}
void __init fw_unreserved_regions(paddr_t s, paddr_t e,
- void (*cb)(paddr_t ps, paddr_t pe),
- unsigned int first)
+ void (*cb)(paddr_t ps, paddr_t pe))
{
if ( acpi_disabled )
- dt_unreserved_regions(s, e, cb, first);
+ dt_unreserved_regions(s, e, cb);
else
cb(s, e);
}
@@ -527,7 +568,7 @@ void __init discard_initial_modules(void)
!mfn_valid(maddr_to_mfn(e)) )
continue;
- fw_unreserved_regions(s, e, init_domheap_pages, 0);
+ fw_unreserved_regions(s, e, init_domheap_pages);
}
mi->nr_mods = 0;
@@ -702,7 +743,7 @@ void __init populate_boot_allocator(void)
}
#endif
- fw_unreserved_regions(s, e, init_boot_pages, 0);
+ fw_unreserved_regions(s, e, init_boot_pages);
s = n;
}
}
--
2.34.1
next prev parent reply other threads:[~2024-04-25 13:11 UTC|newest]
Thread overview: 9+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-04-25 13:11 [RFC PATCH 0/2] xen/arm: Remove recursion from dt_unreserved_regions Luca Fancellu
2024-04-25 13:11 ` [RFC PATCH 1/2] xen/arm: Add DT reserve map regions to bootinfo.reserved_mem Luca Fancellu
2024-05-13 21:54 ` Julien Grall
2024-05-14 7:53 ` Luca Fancellu
2024-05-14 21:06 ` Julien Grall
2024-05-15 10:05 ` Luca Fancellu
2024-05-16 21:23 ` Julien Grall
2024-04-25 13:11 ` Luca Fancellu [this message]
2024-05-13 22:16 ` [RFC PATCH 2/2] xen/arm: Rework dt_unreserved_regions to avoid recursion Julien Grall
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20240425131119.2299629-3-luca.fancellu@arm.com \
--to=luca.fancellu@arm.com \
--cc=Volodymyr_Babchuk@epam.com \
--cc=bertrand.marquis@arm.com \
--cc=julien@xen.org \
--cc=michal.orzel@amd.com \
--cc=sstabellini@kernel.org \
--cc=xen-devel@lists.xenproject.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).