* [PATCH v2 0/2] of: reserved_mem: Improve range allocations @ 2023-06-14 19:20 Stephan Gerhold [not found] ` <20230510-dt-resv-bottom-up-v2-0-aeb2afc8ac25-3XONVrnlUWDR7s880joybQ@public.gmane.org> 2023-06-14 19:20 ` [PATCH v2 2/2] of: reserved_mem: Use stable allocation order Stephan Gerhold 0 siblings, 2 replies; 5+ messages in thread From: Stephan Gerhold @ 2023-06-14 19:20 UTC (permalink / raw) To: Rob Herring, Krzysztof Kozlowski, Conor Dooley, Frank Rowand Cc: Andy Gross, Bjorn Andersson, Konrad Dybcio, devicetree-u79uwXL29TY76Z2rM5mHXA, devicetree-spec-u79uwXL29TY76Z2rM5mHXA, linux-kernel-u79uwXL29TY76Z2rM5mHXA, linux-arm-msm-u79uwXL29TY76Z2rM5mHXA, Stephan Gerhold Try to allocate dynamic reserved memory regions with "alloc-ranges" close to other static regions by choosing between allocating them bottom-up or top-down. This keeps the reserved memory regions closer together rather than potentially having them spread all over the RAM. Also make the allocation order of dynamic reserved memory regions deterministic so it doesn't change randomly when adding unrelated reserved memory regions. Signed-off-by: Stephan Gerhold <stephan-3XONVrnlUWDR7s880joybQ@public.gmane.org> --- Changes in v2: - Drop explicit "allocate-bottom-up"/"allocate-top-down" properties Instead, try to guess in the implementation based on the already available information in the DT. (Rob) - Drop examples that were just included to show the motivation. They are still available on v1 if needed. - Link to v1: https://lore.kernel.org/r/20230510-dt-resv-bottom-up-v1-0-3bf68873dbed-3XONVrnlUWDR7s880joybQ@public.gmane.org --- Stephan Gerhold (2): of: reserved_mem: Try to keep range allocations contiguous of: reserved_mem: Use stable allocation order drivers/of/of_reserved_mem.c | 60 ++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 58 insertions(+), 2 deletions(-) --- base-commit: b16049b21162bb649cdd8519642a35972b7910fe change-id: 20230510-dt-resv-bottom-up-68d71ff6628f Best regards, -- Stephan Gerhold <stephan-3XONVrnlUWDR7s880joybQ@public.gmane.org> ^ permalink raw reply [flat|nested] 5+ messages in thread
[parent not found: <20230510-dt-resv-bottom-up-v2-0-aeb2afc8ac25-3XONVrnlUWDR7s880joybQ@public.gmane.org>]
* [PATCH v2 1/2] of: reserved_mem: Try to keep range allocations contiguous [not found] ` <20230510-dt-resv-bottom-up-v2-0-aeb2afc8ac25-3XONVrnlUWDR7s880joybQ@public.gmane.org> @ 2023-06-14 19:20 ` Stephan Gerhold [not found] ` <20230510-dt-resv-bottom-up-v2-1-aeb2afc8ac25-3XONVrnlUWDR7s880joybQ@public.gmane.org> 0 siblings, 1 reply; 5+ messages in thread From: Stephan Gerhold @ 2023-06-14 19:20 UTC (permalink / raw) To: Rob Herring, Krzysztof Kozlowski, Conor Dooley, Frank Rowand Cc: Andy Gross, Bjorn Andersson, Konrad Dybcio, devicetree-u79uwXL29TY76Z2rM5mHXA, devicetree-spec-u79uwXL29TY76Z2rM5mHXA, linux-kernel-u79uwXL29TY76Z2rM5mHXA, linux-arm-msm-u79uwXL29TY76Z2rM5mHXA, Stephan Gerhold Right now dynamic reserved memory regions are allocated either bottom-up or top-down, depending on the memblock setting of the architecture. This is fine when the address is arbitrary. However, when using "alloc-ranges" the regions are often placed somewhere in the middle of (free) RAM, even if the range starts or ends next to another (static) reservation. Try to detect this situation, and choose explicitly between bottom-up or top-down to allocate the memory close to the other reservations: 1. If the "alloc-range" starts at the end or inside an existing reservation, use bottom-up. 2. If the "alloc-range" ends at the start or inside an existing reservation, use top-down. 3. If both or none is the case, keep the current (architecture-specific) behavior. There are plenty of edge cases where only a more complex algorithm would help, but even this simple approach helps in many cases to keep the reserved memory (and therefore also the free memory) contiguous. Signed-off-by: Stephan Gerhold <stephan-3XONVrnlUWDR7s880joybQ@public.gmane.org> --- drivers/of/of_reserved_mem.c | 55 ++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 53 insertions(+), 2 deletions(-) diff --git a/drivers/of/of_reserved_mem.c b/drivers/of/of_reserved_mem.c index 948efa9f99e3..7f892c3dcc63 100644 --- a/drivers/of/of_reserved_mem.c +++ b/drivers/of/of_reserved_mem.c @@ -77,6 +77,57 @@ void __init fdt_reserved_mem_save_node(unsigned long node, const char *uname, return; } +/* + * __reserved_mem_alloc_in_range() - allocate reserved memory described with + * 'alloc-ranges'. Choose bottom-up/top-down depending on nearby existing + * reserved regions to keep the reserved memory contiguous if possible. + */ +static int __init __reserved_mem_alloc_in_range(phys_addr_t size, + phys_addr_t align, phys_addr_t start, phys_addr_t end, bool nomap, + phys_addr_t *res_base) +{ + bool prev_bottom_up = memblock_bottom_up(); + bool bottom_up = false, top_down = false; + int ret, i; + + for (i = 0; i < reserved_mem_count; i++) { + struct reserved_mem *rmem = &reserved_mem[i]; + + /* Skip regions that were not reserved yet */ + if (rmem->size == 0) + continue; + + /* + * If range starts next to an existing reservation, use bottom-up: + * |....RRRR................RRRRRRRR..............| + * --RRRR------ + */ + if (start >= rmem->base && start <= (rmem->base + rmem->size)) + bottom_up = true; + + /* + * If range ends next to an existing reservation, use top-down: + * |....RRRR................RRRRRRRR..............| + * -------RRRR----- + */ + if (end >= rmem->base && end <= (rmem->base + rmem->size)) + top_down = true; + } + + /* Change setting only if either bottom-up or top-down was selected */ + if (bottom_up != top_down) + memblock_set_bottom_up(bottom_up); + + ret = early_init_dt_alloc_reserved_memory_arch(size, align, + start, end, nomap, res_base); + + /* Restore old setting if needed */ + if (bottom_up != top_down) + memblock_set_bottom_up(prev_bottom_up); + + return ret; +} + /* * __reserved_mem_alloc_size() - allocate reserved memory described by * 'size', 'alignment' and 'alloc-ranges' properties. @@ -137,8 +188,8 @@ static int __init __reserved_mem_alloc_size(unsigned long node, end = start + dt_mem_next_cell(dt_root_size_cells, &prop); - ret = early_init_dt_alloc_reserved_memory_arch(size, - align, start, end, nomap, &base); + ret = __reserved_mem_alloc_in_range(size, align, + start, end, nomap, &base); if (ret == 0) { pr_debug("allocated memory for '%s' node: base %pa, size %lu MiB\n", uname, &base, -- 2.40.1 ^ permalink raw reply related [flat|nested] 5+ messages in thread
[parent not found: <20230510-dt-resv-bottom-up-v2-1-aeb2afc8ac25-3XONVrnlUWDR7s880joybQ@public.gmane.org>]
* Re: [PATCH v2 1/2] of: reserved_mem: Try to keep range allocations contiguous [not found] ` <20230510-dt-resv-bottom-up-v2-1-aeb2afc8ac25-3XONVrnlUWDR7s880joybQ@public.gmane.org> @ 2023-06-20 15:34 ` Rob Herring 0 siblings, 0 replies; 5+ messages in thread From: Rob Herring @ 2023-06-20 15:34 UTC (permalink / raw) To: Stephan Gerhold Cc: devicetree-u79uwXL29TY76Z2rM5mHXA, Konrad Dybcio, devicetree-spec-u79uwXL29TY76Z2rM5mHXA, Conor Dooley, Bjorn Andersson, Rob Herring, linux-kernel-u79uwXL29TY76Z2rM5mHXA, Frank Rowand, linux-arm-msm-u79uwXL29TY76Z2rM5mHXA, Andy Gross, Krzysztof Kozlowski On Wed, 14 Jun 2023 21:20:42 +0200, Stephan Gerhold wrote: > Right now dynamic reserved memory regions are allocated either > bottom-up or top-down, depending on the memblock setting of the > architecture. This is fine when the address is arbitrary. However, > when using "alloc-ranges" the regions are often placed somewhere > in the middle of (free) RAM, even if the range starts or ends next > to another (static) reservation. > > Try to detect this situation, and choose explicitly between bottom-up > or top-down to allocate the memory close to the other reservations: > > 1. If the "alloc-range" starts at the end or inside an existing > reservation, use bottom-up. > 2. If the "alloc-range" ends at the start or inside an existing > reservation, use top-down. > 3. If both or none is the case, keep the current > (architecture-specific) behavior. > > There are plenty of edge cases where only a more complex algorithm > would help, but even this simple approach helps in many cases to keep > the reserved memory (and therefore also the free memory) contiguous. > > Signed-off-by: Stephan Gerhold <stephan-3XONVrnlUWDR7s880joybQ@public.gmane.org> > --- > drivers/of/of_reserved_mem.c | 55 ++++++++++++++++++++++++++++++++++++++++++-- > 1 file changed, 53 insertions(+), 2 deletions(-) > Applied, thanks! ^ permalink raw reply [flat|nested] 5+ messages in thread
* [PATCH v2 2/2] of: reserved_mem: Use stable allocation order 2023-06-14 19:20 [PATCH v2 0/2] of: reserved_mem: Improve range allocations Stephan Gerhold [not found] ` <20230510-dt-resv-bottom-up-v2-0-aeb2afc8ac25-3XONVrnlUWDR7s880joybQ@public.gmane.org> @ 2023-06-14 19:20 ` Stephan Gerhold 2023-06-20 15:35 ` Rob Herring 1 sibling, 1 reply; 5+ messages in thread From: Stephan Gerhold @ 2023-06-14 19:20 UTC (permalink / raw) To: Rob Herring, Krzysztof Kozlowski, Conor Dooley, Frank Rowand Cc: Andy Gross, Bjorn Andersson, Konrad Dybcio, devicetree, devicetree-spec, linux-kernel, linux-arm-msm, Stephan Gerhold 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(+) 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; } -- 2.40.1 ^ permalink raw reply related [flat|nested] 5+ messages in thread
* Re: [PATCH v2 2/2] of: reserved_mem: Use stable allocation order 2023-06-14 19:20 ` [PATCH v2 2/2] of: reserved_mem: Use stable allocation order Stephan Gerhold @ 2023-06-20 15:35 ` Rob Herring 0 siblings, 0 replies; 5+ messages in thread From: Rob Herring @ 2023-06-20 15:35 UTC (permalink / raw) To: Stephan Gerhold Cc: Krzysztof Kozlowski, Conor Dooley, Konrad Dybcio, Frank Rowand, linux-arm-msm, linux-kernel, Rob Herring, devicetree-spec, devicetree, Bjorn Andersson, Andy Gross 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! ^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2023-06-20 15:35 UTC | newest] Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2023-06-14 19:20 [PATCH v2 0/2] of: reserved_mem: Improve range allocations Stephan Gerhold [not found] ` <20230510-dt-resv-bottom-up-v2-0-aeb2afc8ac25-3XONVrnlUWDR7s880joybQ@public.gmane.org> 2023-06-14 19:20 ` [PATCH v2 1/2] of: reserved_mem: Try to keep range allocations contiguous Stephan Gerhold [not found] ` <20230510-dt-resv-bottom-up-v2-1-aeb2afc8ac25-3XONVrnlUWDR7s880joybQ@public.gmane.org> 2023-06-20 15:34 ` Rob Herring 2023-06-14 19:20 ` [PATCH v2 2/2] of: reserved_mem: Use stable allocation order Stephan Gerhold 2023-06-20 15:35 ` Rob Herring
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 NNTP newsgroup(s).