Change in coreboot[master]: device: Introduce RESOURCE_ALLOCATION_TOP_DOWN

Nico Huber has uploaded this change for review. ( https://review.coreboot.org/c/coreboot/+/41957 ) Change subject: device: Introduce RESOURCE_ALLOCATION_TOP_DOWN ...................................................................... device: Introduce RESOURCE_ALLOCATION_TOP_DOWN Add option to resource allocators v4 and v4.5 that restores the top-down allocation approach at the domain level. Change-Id: Iaf463d3e6b37d52e46761d8e210034fded58a8a4 Signed-off-by: Nico Huber <nico.h@gmx.de> --- M src/device/Kconfig M src/device/resource_allocator_v4.5.c M src/device/resource_allocator_v4.c M src/include/memrange.h M src/lib/memrange.c 5 files changed, 37 insertions(+), 21 deletions(-) git pull ssh://review.coreboot.org:29418/coreboot refs/changes/57/41957/1 diff --git a/src/device/Kconfig b/src/device/Kconfig index ee6fb21..35433b0 100644 --- a/src/device/Kconfig +++ b/src/device/Kconfig @@ -821,4 +821,8 @@ endchoice +config RESOURCE_ALLOCATION_TOP_DOWN + bool "Allocate resources from top down" + depends on RESOURCE_ALLOCATOR_V4 || RESOURCE_ALLOCATOR_V4_5 + endmenu diff --git a/src/device/resource_allocator_v4.5.c b/src/device/resource_allocator_v4.5.c index 6b9e712..4a03a23 100644 --- a/src/device/resource_allocator_v4.5.c +++ b/src/device/resource_allocator_v4.5.c @@ -403,7 +403,8 @@ if (!res->size) continue; - if (!memranges_steal(&ranges, res->limit, res->size, res->align, type, &base)) { + if (!memranges_steal(&ranges, res->limit, res->size, res->align, type, &base, + CONFIG(RESOURCE_ALLOCATION_TOP_DOWN))) { printk(BIOS_ERR, "ERROR: Resource didn't fit!!!\n"); print_failed_res(dev, res); continue; diff --git a/src/device/resource_allocator_v4.c b/src/device/resource_allocator_v4.c index 3a11032..4e967f2 100644 --- a/src/device/resource_allocator_v4.c +++ b/src/device/resource_allocator_v4.c @@ -365,6 +365,9 @@ static void allocate_child_resources(struct bus *bus, struct memranges *ranges, unsigned long type_mask, unsigned long type_match) { + const bool allocate_top_down = + bus->dev->path.type == DEVICE_PATH_DOMAIN && + CONFIG(RESOURCE_ALLOCATION_TOP_DOWN); struct resource *resource = NULL; const struct device *dev; @@ -373,8 +376,9 @@ if (!resource->size) continue; - if (memranges_steal(ranges, resource->limit, resource->size, resource->align, - type_match, &resource->base) == false) { + if (memranges_steal(ranges, resource->limit, resource->size, + resource->align, type_match, &resource->base, + allocate_top_down)) == false) { printk(BIOS_ERR, " ERROR: Resource didn't fit!!! "); printk(BIOS_DEBUG, " %s %02lx * size: 0x%llx limit: %llx %s\n", dev_path(dev), resource->index, diff --git a/src/include/memrange.h b/src/include/memrange.h index 2b8c00e..d50a9c8 100644 --- a/src/include/memrange.h +++ b/src/include/memrange.h @@ -161,15 +161,17 @@ const struct range_entry *r); /* Steals memory from the available list in given ranges as per the constraints: - * limit = Upper bound for the memory range to steal (Inclusive). - * size = Requested size for the stolen memory. - * align = Required alignment(log 2) for the starting address of the stolen memory. - * tag = Use a range that matches the given tag. + * limit = Upper bound for the memory range to steal (Inclusive). + * size = Requested size for the stolen memory. + * align = Required alignment(log 2) for the starting address of the stolen memory. + * tag = Use a range that matches the given tag. + * from_top = Steal the highest possible range. * * If the constraints can be satisfied, this function creates a hole in the memrange, * writes the base address of that hole to stolen_base and returns true. Otherwise it returns * false. */ bool memranges_steal(struct memranges *ranges, resource_t limit, resource_t size, - unsigned char align, unsigned long tag, resource_t *stolen_base); + unsigned char align, unsigned long tag, resource_t *stolen_base, + bool from_top); #endif /* MEMRANGE_H_ */ diff --git a/src/lib/memrange.c b/src/lib/memrange.c index 39f502c..2f6d55c 100644 --- a/src/lib/memrange.c +++ b/src/lib/memrange.c @@ -378,11 +378,11 @@ /* Find a range entry that satisfies the given constraints to fit a hole that matches the * required alignment, is big enough, does not exceed the limit and has a matching tag. */ -static const struct range_entry *memranges_find_entry(struct memranges *ranges, - resource_t limit, resource_t size, - unsigned char align, unsigned long tag) +static const struct range_entry * +memranges_find_entry(struct memranges *ranges, resource_t limit, resource_t size, + unsigned char align, unsigned long tag, bool last) { - const struct range_entry *r; + const struct range_entry *r, *last_entry = NULL; resource_t base, end; if (size == 0) @@ -407,25 +407,30 @@ if (end > limit) break; - return r; + if (!last) + return r; + + last_entry = r; } - return NULL; + return last_entry; } bool memranges_steal(struct memranges *ranges, resource_t limit, resource_t size, - unsigned char align, unsigned long tag, resource_t *stolen_base) + unsigned char align, unsigned long tag, resource_t *stolen_base, + bool from_top) { - resource_t base; - const struct range_entry *r = memranges_find_entry(ranges, limit, size, align, tag); + const struct range_entry *r; + r = memranges_find_entry(ranges, limit, size, align, tag, from_top); if (r == NULL) return false; - base = ALIGN_UP(r->begin, POWER_OF_2(align)); - - memranges_create_hole(ranges, base, size); - *stolen_base = base; + if (from_top) + *stolen_base = ALIGN_DOWN(range_entry_end(r) - size, POWER_OF_2(align)); + else + *stolen_base = ALIGN_UP(r->begin, POWER_OF_2(align)); + memranges_create_hole(ranges, *stolen_base, size); return true; } -- To view, visit https://review.coreboot.org/c/coreboot/+/41957 To unsubscribe, or for help writing mail filters, visit https://review.coreboot.org/settings Gerrit-Project: coreboot Gerrit-Branch: master Gerrit-Change-Id: Iaf463d3e6b37d52e46761d8e210034fded58a8a4 Gerrit-Change-Number: 41957 Gerrit-PatchSet: 1 Gerrit-Owner: Nico Huber <nico.h@gmx.de> Gerrit-MessageType: newchange

build bot (Jenkins) has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41957 ) Change subject: device: Introduce RESOURCE_ALLOCATION_TOP_DOWN ...................................................................... Patch Set 1: (1 comment) https://review.coreboot.org/c/coreboot/+/41957/1/src/device/resource_allocat... File src/device/resource_allocator_v4.c: https://review.coreboot.org/c/coreboot/+/41957/1/src/device/resource_allocat... PS1, Line 379: if (memranges_steal(ranges, resource->limit, resource->size, trailing statements should be on next line -- To view, visit https://review.coreboot.org/c/coreboot/+/41957 To unsubscribe, or for help writing mail filters, visit https://review.coreboot.org/settings Gerrit-Project: coreboot Gerrit-Branch: master Gerrit-Change-Id: Iaf463d3e6b37d52e46761d8e210034fded58a8a4 Gerrit-Change-Number: 41957 Gerrit-PatchSet: 1 Gerrit-Owner: Nico Huber <nico.h@gmx.de> Gerrit-CC: build bot (Jenkins) <no-reply@coreboot.org> Gerrit-Comment-Date: Sun, 31 May 2020 19:13:48 +0000 Gerrit-HasComments: Yes Gerrit-Has-Labels: No Gerrit-MessageType: comment

Hello build bot (Jenkins), I'd like you to reexamine a change. Please visit https://review.coreboot.org/c/coreboot/+/41957 to look at the new patch set (#2). Change subject: device: Introduce RESOURCE_ALLOCATION_TOP_DOWN ...................................................................... device: Introduce RESOURCE_ALLOCATION_TOP_DOWN Add option to resource allocators v4 and v4.5 that restores the top-down allocation approach at the domain level. Change-Id: Iaf463d3e6b37d52e46761d8e210034fded58a8a4 Signed-off-by: Nico Huber <nico.h@gmx.de> --- M src/device/Kconfig M src/device/resource_allocator_v4.5.c M src/device/resource_allocator_v4.c M src/include/memrange.h M src/lib/memrange.c 5 files changed, 35 insertions(+), 20 deletions(-) git pull ssh://review.coreboot.org:29418/coreboot refs/changes/57/41957/2 -- To view, visit https://review.coreboot.org/c/coreboot/+/41957 To unsubscribe, or for help writing mail filters, visit https://review.coreboot.org/settings Gerrit-Project: coreboot Gerrit-Branch: master Gerrit-Change-Id: Iaf463d3e6b37d52e46761d8e210034fded58a8a4 Gerrit-Change-Number: 41957 Gerrit-PatchSet: 2 Gerrit-Owner: Nico Huber <nico.h@gmx.de> Gerrit-Reviewer: build bot (Jenkins) <no-reply@coreboot.org> Gerrit-MessageType: newpatchset

Aaron Durbin has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41957 ) Change subject: device: Introduce RESOURCE_ALLOCATION_TOP_DOWN ...................................................................... Patch Set 2: (1 comment) https://review.coreboot.org/c/coreboot/+/41957/2/src/lib/memrange.c File src/lib/memrange.c: https://review.coreboot.org/c/coreboot/+/41957/2/src/lib/memrange.c@430 PS2, Line 430: *stolen_base = ALIGN_DOWN(range_entry_end(r) - size, POWER_OF_2(align)); Don't we need to handle the from_top logic in memranges_find_entry() for region size checking? We're doing the align up check there, but I'm not convinced that's enough. -- To view, visit https://review.coreboot.org/c/coreboot/+/41957 To unsubscribe, or for help writing mail filters, visit https://review.coreboot.org/settings Gerrit-Project: coreboot Gerrit-Branch: master Gerrit-Change-Id: Iaf463d3e6b37d52e46761d8e210034fded58a8a4 Gerrit-Change-Number: 41957 Gerrit-PatchSet: 2 Gerrit-Owner: Nico Huber <nico.h@gmx.de> Gerrit-Reviewer: build bot (Jenkins) <no-reply@coreboot.org> Gerrit-CC: Aaron Durbin <adurbin@chromium.org> Gerrit-Comment-Date: Mon, 01 Jun 2020 18:35:10 +0000 Gerrit-HasComments: Yes Gerrit-Has-Labels: No Gerrit-MessageType: comment

Nico Huber has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41957 ) Change subject: device: Introduce RESOURCE_ALLOCATION_TOP_DOWN ...................................................................... Patch Set 2: (1 comment) https://review.coreboot.org/c/coreboot/+/41957/2/src/lib/memrange.c File src/lib/memrange.c: https://review.coreboot.org/c/coreboot/+/41957/2/src/lib/memrange.c@430 PS2, Line 430: *stolen_base = ALIGN_DOWN(range_entry_end(r) - size, POWER_OF_2(align));
Don't we need to handle the from_top logic in memranges_find_entry() for region size checking? We're […] Then, let me convince you. :)
The check in memranges_find_entry() guarantees that there is enough (>= size) space between `r->begin` aligned up and `r->end`. Thus, `r->end + 1 - size` is above or equal to `r->begin` aligned up. And aligning it down would result in `r->begin` aligned up in the worst case. Long story: I guess what we have to prove is that every `stolen_base` with (1) stolen_base = ALIGN_DOWN(range_entry_end(r) - size, POWER_OF_2(align)) is above `r->begin` (2) stolen_base >= r->begin We divide (1) into two cases: (1.1) range_entry_end(r) - size < ALIGN_UP(r->begin, POWER_OF_2(align)) (1.2) range_entry_end(r) - size >= ALIGN_UP(r->begin, POWER_OF_2(align)) (1.1) is what we check in memranges_find_entry(). For (1.2) we can see via (1) (3) stolen_base >= ALIGN_DOWN(ALIGN_UP(r->begin, POWER_OF_2(align), POWER_OF_2(align)) Aligning down what is already aligned has no effect, thus (4) stolen_base >= ALIGN_UP(r->begin, POWER_OF_2(align)) >= r->begin -- To view, visit https://review.coreboot.org/c/coreboot/+/41957 To unsubscribe, or for help writing mail filters, visit https://review.coreboot.org/settings Gerrit-Project: coreboot Gerrit-Branch: master Gerrit-Change-Id: Iaf463d3e6b37d52e46761d8e210034fded58a8a4 Gerrit-Change-Number: 41957 Gerrit-PatchSet: 2 Gerrit-Owner: Nico Huber <nico.h@gmx.de> Gerrit-Reviewer: build bot (Jenkins) <no-reply@coreboot.org> Gerrit-CC: Aaron Durbin <adurbin@chromium.org> Gerrit-Comment-Date: Tue, 02 Jun 2020 11:56:49 +0000 Gerrit-HasComments: Yes Gerrit-Has-Labels: No Comment-In-Reply-To: Aaron Durbin <adurbin@chromium.org> Gerrit-MessageType: comment

Aaron Durbin has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41957 ) Change subject: device: Introduce RESOURCE_ALLOCATION_TOP_DOWN ...................................................................... Patch Set 2: (1 comment) https://review.coreboot.org/c/coreboot/+/41957/2/src/lib/memrange.c File src/lib/memrange.c: https://review.coreboot.org/c/coreboot/+/41957/2/src/lib/memrange.c@430 PS2, Line 430: *stolen_base = ALIGN_DOWN(range_entry_end(r) - size, POWER_OF_2(align));
Then, let me convince you. :) […] OK. Makes sense. We should probably add a comment up there that the one check is sufficient. That comment would be associated with this CL so we can find this commentary in case anyone is interested.
-- To view, visit https://review.coreboot.org/c/coreboot/+/41957 To unsubscribe, or for help writing mail filters, visit https://review.coreboot.org/settings Gerrit-Project: coreboot Gerrit-Branch: master Gerrit-Change-Id: Iaf463d3e6b37d52e46761d8e210034fded58a8a4 Gerrit-Change-Number: 41957 Gerrit-PatchSet: 2 Gerrit-Owner: Nico Huber <nico.h@gmx.de> Gerrit-Reviewer: build bot (Jenkins) <no-reply@coreboot.org> Gerrit-CC: Aaron Durbin <adurbin@chromium.org> Gerrit-CC: Paul Menzel <paulepanter@users.sourceforge.net> Gerrit-Comment-Date: Wed, 03 Jun 2020 15:45:51 +0000 Gerrit-HasComments: Yes Gerrit-Has-Labels: No Comment-In-Reply-To: Nico Huber <nico.h@gmx.de> Comment-In-Reply-To: Aaron Durbin <adurbin@chromium.org> Gerrit-MessageType: comment

Angel Pons has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41957 ) Change subject: device: Introduce RESOURCE_ALLOCATION_TOP_DOWN ...................................................................... Patch Set 2: Code-Review+2 -- To view, visit https://review.coreboot.org/c/coreboot/+/41957 To unsubscribe, or for help writing mail filters, visit https://review.coreboot.org/settings Gerrit-Project: coreboot Gerrit-Branch: master Gerrit-Change-Id: Iaf463d3e6b37d52e46761d8e210034fded58a8a4 Gerrit-Change-Number: 41957 Gerrit-PatchSet: 2 Gerrit-Owner: Nico Huber <nico.h@gmx.de> Gerrit-Reviewer: Angel Pons <th3fanbus@gmail.com> Gerrit-Reviewer: build bot (Jenkins) <no-reply@coreboot.org> Gerrit-CC: Aaron Durbin <adurbin@chromium.org> Gerrit-CC: Paul Menzel <paulepanter@users.sourceforge.net> Gerrit-Comment-Date: Tue, 04 Aug 2020 22:13:17 +0000 Gerrit-HasComments: No Gerrit-Has-Labels: Yes Gerrit-MessageType: comment

Arthur Heymans has uploaded a new patch set (#3) to the change originally created by Nico Huber. ( https://review.coreboot.org/c/coreboot/+/41957 ) Change subject: device: Introduce RESOURCE_ALLOCATION_TOP_DOWN ...................................................................... device: Introduce RESOURCE_ALLOCATION_TOP_DOWN Add option to resource allocators v4 and v4.5 that restores the top-down allocation approach at the domain level. Change-Id: Iaf463d3e6b37d52e46761d8e210034fded58a8a4 Signed-off-by: Nico Huber <nico.h@gmx.de> --- M src/device/Kconfig M src/device/resource_allocator_v4.5.c M src/device/resource_allocator_v4.c M src/include/memrange.h M src/lib/memrange.c 5 files changed, 35 insertions(+), 20 deletions(-) git pull ssh://review.coreboot.org:29418/coreboot refs/changes/57/41957/3 -- To view, visit https://review.coreboot.org/c/coreboot/+/41957 To unsubscribe, or for help writing mail filters, visit https://review.coreboot.org/settings Gerrit-Project: coreboot Gerrit-Branch: master Gerrit-Change-Id: Iaf463d3e6b37d52e46761d8e210034fded58a8a4 Gerrit-Change-Number: 41957 Gerrit-PatchSet: 3 Gerrit-Owner: Nico Huber <nico.h@gmx.de> Gerrit-Reviewer: Angel Pons <th3fanbus@gmail.com> Gerrit-Reviewer: build bot (Jenkins) <no-reply@coreboot.org> Gerrit-CC: Aaron Durbin <adurbin@chromium.org> Gerrit-CC: Arthur Heymans <arthur@aheymans.xyz> Gerrit-CC: Paul Menzel <paulepanter@mailbox.org> Gerrit-MessageType: newpatchset

Attention is currently required from: Arthur Heymans, Bill XIE, Nico Huber, Jakub Czapiga, Julius Werner, Angel Pons, Eric Lai, Werner Zeh, Kyösti Mälkki. Subrata Banik has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41957 ) Change subject: allocator_v4: Introduce RESOURCE_ALLOCATION_TOP_DOWN ...................................................................... Patch Set 7: Code-Review+2 -- To view, visit https://review.coreboot.org/c/coreboot/+/41957 To unsubscribe, or for help writing mail filters, visit https://review.coreboot.org/settings Gerrit-Project: coreboot Gerrit-Branch: master Gerrit-Change-Id: Iaf463d3e6b37d52e46761d8e210034fded58a8a4 Gerrit-Change-Number: 41957 Gerrit-PatchSet: 7 Gerrit-Owner: Nico Huber <nico.h@gmx.de> Gerrit-Reviewer: Angel Pons <th3fanbus@gmail.com> Gerrit-Reviewer: Arthur Heymans <arthur.heymans@9elements.com> Gerrit-Reviewer: Arthur Heymans <arthur@aheymans.xyz> Gerrit-Reviewer: Bill XIE <persmule@hardenedlinux.org> Gerrit-Reviewer: Eric Lai <eric_lai@quanta.corp-partner.google.com> Gerrit-Reviewer: Jakub Czapiga <jacz@semihalf.com> Gerrit-Reviewer: Julius Werner <jwerner@chromium.org> Gerrit-Reviewer: Kyösti Mälkki <kyosti.malkki@gmail.com> Gerrit-Reviewer: Lean Sheng Tan <sheng.tan@9elements.com> Gerrit-Reviewer: Subrata Banik <subratabanik@google.com> Gerrit-Reviewer: Tim Wawrzynczak <twawrzynczak@chromium.org> Gerrit-Reviewer: Werner Zeh <werner.zeh@siemens.com> Gerrit-Reviewer: build bot (Jenkins) <no-reply@coreboot.org> Gerrit-CC: Aaron Durbin <adurbin@chromium.org> Gerrit-CC: Paul Menzel <paulepanter@mailbox.org> Gerrit-CC: Varshit Pandya <pandyavarshit@gmail.com> Gerrit-Attention: Arthur Heymans <arthur.heymans@9elements.com> Gerrit-Attention: Bill XIE <persmule@hardenedlinux.org> Gerrit-Attention: Nico Huber <nico.h@gmx.de> Gerrit-Attention: Jakub Czapiga <jacz@semihalf.com> Gerrit-Attention: Julius Werner <jwerner@chromium.org> Gerrit-Attention: Angel Pons <th3fanbus@gmail.com> Gerrit-Attention: Eric Lai <eric_lai@quanta.corp-partner.google.com> Gerrit-Attention: Werner Zeh <werner.zeh@siemens.com> Gerrit-Attention: Kyösti Mälkki <kyosti.malkki@gmail.com> Gerrit-Comment-Date: Fri, 02 Sep 2022 07:05:13 +0000 Gerrit-HasComments: No Gerrit-Has-Labels: Yes Gerrit-MessageType: comment

Martin L Roth has submitted this change. ( https://review.coreboot.org/c/coreboot/+/41957 ) Change subject: allocator_v4: Introduce RESOURCE_ALLOCATION_TOP_DOWN ...................................................................... allocator_v4: Introduce RESOURCE_ALLOCATION_TOP_DOWN Add option to resource allocator v4 that restores the top-down allocation approach at the domain level. This makes it easier to handle 64-bit resources natively. With the top-down approach, resources that can be placed either above or below 4G would be placed above, to save precious space below the 4G boundary. Change-Id: Iaf463d3e6b37d52e46761d8e210034fded58a8a4 Signed-off-by: Nico Huber <nico.h@gmx.de> Reviewed-on: https://review.coreboot.org/c/coreboot/+/41957 Tested-by: build bot (Jenkins) <no-reply@coreboot.org> Reviewed-by: Tim Wawrzynczak <twawrzynczak@chromium.org> Reviewed-by: Lean Sheng Tan <sheng.tan@9elements.com> Reviewed-by: Subrata Banik <subratabanik@google.com> --- M src/device/Kconfig M src/device/resource_allocator_v4.c M src/include/memrange.h M src/lib/memrange.c M tests/lib/memrange-test.c 5 files changed, 95 insertions(+), 34 deletions(-) Approvals: build bot (Jenkins): Verified Lean Sheng Tan: Looks good to me, but someone else must approve Tim Wawrzynczak: Looks good to me, approved Subrata Banik: Looks good to me, approved diff --git a/src/device/Kconfig b/src/device/Kconfig index 6f4a24e..af9beb3 100644 --- a/src/device/Kconfig +++ b/src/device/Kconfig @@ -933,6 +933,11 @@ ranges for allocating resources. This allows allocation of resources above 4G boundary as well. +config RESOURCE_ALLOCATION_TOP_DOWN + bool "Allocate resources from top down" + default y + depends on RESOURCE_ALLOCATOR_V4 + config XHCI_UTILS def_bool n help diff --git a/src/device/resource_allocator_v4.c b/src/device/resource_allocator_v4.c index 2b62fc8..222f1e9 100644 --- a/src/device/resource_allocator_v4.c +++ b/src/device/resource_allocator_v4.c @@ -372,6 +372,9 @@ static void allocate_child_resources(struct bus *bus, struct memranges *ranges, unsigned long type_mask, unsigned long type_match) { + const bool allocate_top_down = + bus->dev->path.type == DEVICE_PATH_DOMAIN && + CONFIG(RESOURCE_ALLOCATION_TOP_DOWN); struct resource *resource = NULL; const struct device *dev; @@ -381,7 +384,7 @@ continue; if (memranges_steal(ranges, resource->limit, resource->size, resource->align, - type_match, &resource->base) == false) { + type_match, &resource->base, allocate_top_down) == false) { printk(BIOS_ERR, " ERROR: Resource didn't fit!!! "); printk(BIOS_DEBUG, " %s %02lx * size: 0x%llx limit: %llx %s\n", dev_path(dev), resource->index, diff --git a/src/include/memrange.h b/src/include/memrange.h index a8a8de9..f7c5bfc 100644 --- a/src/include/memrange.h +++ b/src/include/memrange.h @@ -161,15 +161,17 @@ const struct range_entry *r); /* Steals memory from the available list in given ranges as per the constraints: - * limit = Upper bound for the memory range to steal (Inclusive). - * size = Requested size for the stolen memory. - * align = Required alignment(log 2) for the starting address of the stolen memory. - * tag = Use a range that matches the given tag. + * limit = Upper bound for the memory range to steal (Inclusive). + * size = Requested size for the stolen memory. + * align = Required alignment(log 2) for the starting address of the stolen memory. + * tag = Use a range that matches the given tag. + * from_top = Steal the highest possible range. * * If the constraints can be satisfied, this function creates a hole in the memrange, * writes the base address of that hole to stolen_base and returns true. Otherwise it returns * false. */ bool memranges_steal(struct memranges *ranges, resource_t limit, resource_t size, - unsigned char align, unsigned long tag, resource_t *stolen_base); + unsigned char align, unsigned long tag, resource_t *stolen_base, + bool from_top); #endif /* MEMRANGE_H_ */ diff --git a/src/lib/memrange.c b/src/lib/memrange.c index 39f502c..b68b86e 100644 --- a/src/lib/memrange.c +++ b/src/lib/memrange.c @@ -378,11 +378,11 @@ /* Find a range entry that satisfies the given constraints to fit a hole that matches the * required alignment, is big enough, does not exceed the limit and has a matching tag. */ -static const struct range_entry *memranges_find_entry(struct memranges *ranges, - resource_t limit, resource_t size, - unsigned char align, unsigned long tag) +static const struct range_entry * +memranges_find_entry(struct memranges *ranges, resource_t limit, resource_t size, + unsigned char align, unsigned long tag, bool last) { - const struct range_entry *r; + const struct range_entry *r, *last_entry = NULL; resource_t base, end; if (size == 0) @@ -407,25 +407,35 @@ if (end > limit) break; - return r; + if (!last) + return r; + + last_entry = r; } - return NULL; + return last_entry; } bool memranges_steal(struct memranges *ranges, resource_t limit, resource_t size, - unsigned char align, unsigned long tag, resource_t *stolen_base) + unsigned char align, unsigned long tag, resource_t *stolen_base, + bool from_top) { - resource_t base; - const struct range_entry *r = memranges_find_entry(ranges, limit, size, align, tag); + const struct range_entry *r; + r = memranges_find_entry(ranges, limit, size, align, tag, from_top); if (r == NULL) return false; - base = ALIGN_UP(r->begin, POWER_OF_2(align)); - - memranges_create_hole(ranges, base, size); - *stolen_base = base; + if (from_top) { + /* Ensure we're within the range, even aligned down. + Proof is simple: If ALIGN_UP(r->begin) would be + higher, the stolen range wouldn't fit.*/ + assert(r->begin <= ALIGN_DOWN(range_entry_end(r) - size, POWER_OF_2(align))); + *stolen_base = ALIGN_DOWN(range_entry_end(r) - size, POWER_OF_2(align)); + } else { + *stolen_base = ALIGN_UP(r->begin, POWER_OF_2(align)); + } + memranges_create_hole(ranges, *stolen_base, size); return true; } diff --git a/tests/lib/memrange-test.c b/tests/lib/memrange-test.c index 557ade4..9871484 100644 --- a/tests/lib/memrange-test.c +++ b/tests/lib/memrange-test.c @@ -457,8 +457,9 @@ } /* - * This test verifies memranges_steal() function. Simple check is done by attempt so steal some - * memory from region with READONLY_TAG. + * This test verifies memranges_steal() function. Simple check is done by attempt + * to steal some memory from the top of region with CACHEABLE_TAG and some from + * the bottom of region with READONLY_TAG. * * Example memory ranges (res_mock1) for test_memrange_steal. * Space marked with (/) is stolen during the test. @@ -466,8 +467,8 @@ * +--------CACHEABLE_TAG--------+ <-0xE000 * | | * | | - * | | - * +-----------------------------+ <-0x100000 + * |/////////////////////////////| <-stolen_base + * +-----------------------------+ <-0x100000 <-stolen_base + 0x4000 * * * @@ -501,13 +502,27 @@ status = memranges_steal(&test_memrange, res_mock[RESERVED_TAG].base + res_mock[RESERVED_TAG].size, - stolen_range_size, 12, READONLY_TAG, &stolen); + stolen_range_size, 12, CACHEABLE_TAG, &stolen, true); + assert_true(status); + assert_in_range(stolen, res_mock[CACHEABLE_TAG].base, + res_mock[CACHEABLE_TAG].base + res_mock[CACHEABLE_TAG].size); + status = memranges_steal(&test_memrange, + res_mock[RESERVED_TAG].base + res_mock[RESERVED_TAG].size, + stolen_range_size, 12, READONLY_TAG, &stolen, false); assert_true(status); assert_in_range(stolen, res_mock[READONLY_TAG].base, res_mock[READONLY_TAG].base + res_mock[READONLY_TAG].size); memranges_each_entry(ptr, &test_memrange) { + if (range_entry_tag(ptr) == CACHEABLE_TAG) { + assert_int_equal(range_entry_end(ptr), + ALIGN_DOWN(ALIGN_UP(res_mock[CACHEABLE_TAG].base + + res_mock[CACHEABLE_TAG].size, + MEMRANGE_ALIGN) + - stolen_range_size, + MEMRANGE_ALIGN)); + } if (range_entry_tag(ptr) == READONLY_TAG) { assert_int_equal(range_entry_base(ptr), ALIGN_DOWN(res_mock[READONLY_TAG].base, MEMRANGE_ALIGN) @@ -518,20 +533,23 @@ assert_int_equal(count, 3); count = 0; - /* Check if inserting range in previously stolen area will merge it. */ + /* Check if inserting ranges in previously stolen areas will merge them. */ + memranges_insert(&test_memrange, + res_mock[CACHEABLE_TAG].base + res_mock[CACHEABLE_TAG].size + - stolen_range_size - 0x12, + stolen_range_size, CACHEABLE_TAG); memranges_insert(&test_memrange, res_mock[READONLY_TAG].base + 0xCC, stolen_range_size, READONLY_TAG); memranges_each_entry(ptr, &test_memrange) { - if (range_entry_tag(ptr) == READONLY_TAG) { - assert_int_equal( - range_entry_base(ptr), - ALIGN_DOWN(res_mock[READONLY_TAG].base, MEMRANGE_ALIGN)); - assert_int_equal( - range_entry_end(ptr), - ALIGN_UP(res_mock[READONLY_TAG].base + res_mock[READONLY_TAG].size, - MEMRANGE_ALIGN)); - } + const unsigned long tag = range_entry_tag(ptr); + assert_true(tag == CACHEABLE_TAG || tag == READONLY_TAG || tag == RESERVED_TAG); + assert_int_equal( + range_entry_base(ptr), + ALIGN_DOWN(res_mock[tag].base, MEMRANGE_ALIGN)); + assert_int_equal( + range_entry_end(ptr), + ALIGN_UP(res_mock[tag].base + res_mock[tag].size, MEMRANGE_ALIGN)); count++; } assert_int_equal(count, 3); -- To view, visit https://review.coreboot.org/c/coreboot/+/41957 To unsubscribe, or for help writing mail filters, visit https://review.coreboot.org/settings Gerrit-Project: coreboot Gerrit-Branch: master Gerrit-Change-Id: Iaf463d3e6b37d52e46761d8e210034fded58a8a4 Gerrit-Change-Number: 41957 Gerrit-PatchSet: 8 Gerrit-Owner: Nico Huber <nico.h@gmx.de> Gerrit-Reviewer: Angel Pons <th3fanbus@gmail.com> Gerrit-Reviewer: Arthur Heymans <arthur.heymans@9elements.com> Gerrit-Reviewer: Arthur Heymans <arthur@aheymans.xyz> Gerrit-Reviewer: Bill XIE <persmule@hardenedlinux.org> Gerrit-Reviewer: Eric Lai <eric_lai@quanta.corp-partner.google.com> Gerrit-Reviewer: Jakub Czapiga <jacz@semihalf.com> Gerrit-Reviewer: Julius Werner <jwerner@chromium.org> Gerrit-Reviewer: Kyösti Mälkki <kyosti.malkki@gmail.com> Gerrit-Reviewer: Lean Sheng Tan <sheng.tan@9elements.com> Gerrit-Reviewer: Martin L Roth <gaumless@gmail.com> Gerrit-Reviewer: Subrata Banik <subratabanik@google.com> Gerrit-Reviewer: Tim Wawrzynczak <twawrzynczak@chromium.org> Gerrit-Reviewer: Werner Zeh <werner.zeh@siemens.com> Gerrit-Reviewer: build bot (Jenkins) <no-reply@coreboot.org> Gerrit-CC: Aaron Durbin <adurbin@chromium.org> Gerrit-CC: Paul Menzel <paulepanter@mailbox.org> Gerrit-CC: Varshit Pandya <pandyavarshit@gmail.com> Gerrit-MessageType: merged

9elements QA has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41957 ) Change subject: allocator_v4: Introduce RESOURCE_ALLOCATION_TOP_DOWN ...................................................................... Patch Set 8: Automatic boot test returned (PASS/FAIL/TOTAL): 12 / 3 / 15 FAIL: x86_32 "Hermes CFL" , build config PRODRIVE_HERMES_ and payload TianoCore_UefiPayloadPkg : https://lava.9esec.io/r/122711 FAIL: x86_32 "Hermes CFL" , build config PRODRIVE_HERMES and payload TianoCore_UefiPayloadPkg : https://lava.9esec.io/r/122710 FAIL: x86_32 "ThinkPad T500" , build config LENOVO_T500 and payload SeaBIOS : https://lava.9esec.io/r/122709 PASS: x86_32 "HP Z220 SFF Workstation" , build config HP_Z220_SFF_WORKSTATION and payload LinuxBoot_BB_kexec : https://lava.9esec.io/r/122708 PASS: x86_64 "HP Compaq 8200 Elite SFF PC" , build config HP_COMPAQ_8200_ELITE_SFF_PC.X86_64 and payload TianoCore : https://lava.9esec.io/r/122707 PASS: x86_64 "HP Compaq 8200 Elite SFF PC" , build config HP_COMPAQ_8200_ELITE_SFF_PC.X86_64 and payload SeaBIOS : https://lava.9esec.io/r/122706 PASS: x86_32 "HP Compaq 8200 Elite SFF PC" , build config HP_COMPAQ_8200_ELITE_SFF_PC and payload TianoCore : https://lava.9esec.io/r/122705 PASS: x86_32 "HP Compaq 8200 Elite SFF PC" , build config HP_COMPAQ_8200_ELITE_SFF_PC and payload SeaBIOS : https://lava.9esec.io/r/122704 PASS: x86_32 "QEMU x86 q35/ich9" , build config EMULATION_QEMU_X86_Q35_SMM_TSEG and payload TianoCore : https://lava.9esec.io/r/122703 PASS: x86_32 "QEMU x86 q35/ich9" , build config EMULATION_QEMU_X86_Q35 and payload TianoCore : https://lava.9esec.io/r/122701 PASS: x86_32 "QEMU x86 q35/ich9" , build config EMULATION_QEMU_X86_Q35 and payload SeaBIOS : https://lava.9esec.io/r/122700 PASS: x86_64 "QEMU x86 i440fx/piix4" , build config EMULATION_QEMU_X86_I440FX_X86_64 and payload SeaBIOS : https://lava.9esec.io/r/122699 PASS: x86_32 "QEMU x86 i440fx/piix4" , build config EMULATION_QEMU_X86_I440FX_ASAN and payload SeaBIOS : https://lava.9esec.io/r/122698 PASS: x86_32 "QEMU x86 i440fx/piix4" , build config EMULATION_QEMU_X86_I440FX_ and payload SeaBIOS : https://lava.9esec.io/r/122697 PASS: x86_32 "QEMU x86 i440fx/piix4" , build config EMULATION_QEMU_X86_I440FX and payload SeaBIOS : https://lava.9esec.io/r/122696 Please note: This test is under development and might not be accurate at all! -- To view, visit https://review.coreboot.org/c/coreboot/+/41957 To unsubscribe, or for help writing mail filters, visit https://review.coreboot.org/settings Gerrit-Project: coreboot Gerrit-Branch: master Gerrit-Change-Id: Iaf463d3e6b37d52e46761d8e210034fded58a8a4 Gerrit-Change-Number: 41957 Gerrit-PatchSet: 8 Gerrit-Owner: Nico Huber <nico.h@gmx.de> Gerrit-Reviewer: Angel Pons <th3fanbus@gmail.com> Gerrit-Reviewer: Arthur Heymans <arthur.heymans@9elements.com> Gerrit-Reviewer: Arthur Heymans <arthur@aheymans.xyz> Gerrit-Reviewer: Bill XIE <persmule@hardenedlinux.org> Gerrit-Reviewer: Eric Lai <eric_lai@quanta.corp-partner.google.com> Gerrit-Reviewer: Jakub Czapiga <jacz@semihalf.com> Gerrit-Reviewer: Julius Werner <jwerner@chromium.org> Gerrit-Reviewer: Kyösti Mälkki <kyosti.malkki@gmail.com> Gerrit-Reviewer: Lean Sheng Tan <sheng.tan@9elements.com> Gerrit-Reviewer: Martin L Roth <gaumless@gmail.com> Gerrit-Reviewer: Subrata Banik <subratabanik@google.com> Gerrit-Reviewer: Tim Wawrzynczak <twawrzynczak@chromium.org> Gerrit-Reviewer: Werner Zeh <werner.zeh@siemens.com> Gerrit-Reviewer: build bot (Jenkins) <no-reply@coreboot.org> Gerrit-CC: 9elements QA <hardwaretestrobot@gmail.com> Gerrit-CC: Aaron Durbin <adurbin@chromium.org> Gerrit-CC: Paul Menzel <paulepanter@mailbox.org> Gerrit-CC: Varshit Pandya <pandyavarshit@gmail.com> Gerrit-Comment-Date: Sun, 04 Sep 2022 18:28:13 +0000 Gerrit-HasComments: No Gerrit-Has-Labels: No Gerrit-MessageType: comment

Angel Pons has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41957 ) Change subject: allocator_v4: Introduce RESOURCE_ALLOCATION_TOP_DOWN ...................................................................... Patch Set 8: (1 comment) Patchset: PS8: Note: This was disabled in CB:67328 as it caused regressions on several platforms. -- To view, visit https://review.coreboot.org/c/coreboot/+/41957 To unsubscribe, or for help writing mail filters, visit https://review.coreboot.org/settings Gerrit-Project: coreboot Gerrit-Branch: master Gerrit-Change-Id: Iaf463d3e6b37d52e46761d8e210034fded58a8a4 Gerrit-Change-Number: 41957 Gerrit-PatchSet: 8 Gerrit-Owner: Nico Huber <nico.h@gmx.de> Gerrit-Reviewer: Angel Pons <th3fanbus@gmail.com> Gerrit-Reviewer: Arthur Heymans <arthur.heymans@9elements.com> Gerrit-Reviewer: Arthur Heymans <arthur@aheymans.xyz> Gerrit-Reviewer: Bill XIE <persmule@hardenedlinux.org> Gerrit-Reviewer: Eric Lai <eric_lai@quanta.corp-partner.google.com> Gerrit-Reviewer: Jakub Czapiga <jacz@semihalf.com> Gerrit-Reviewer: Julius Werner <jwerner@chromium.org> Gerrit-Reviewer: Kyösti Mälkki <kyosti.malkki@gmail.com> Gerrit-Reviewer: Lean Sheng Tan <sheng.tan@9elements.com> Gerrit-Reviewer: Martin L Roth <gaumless@gmail.com> Gerrit-Reviewer: Subrata Banik <subratabanik@google.com> Gerrit-Reviewer: Tim Wawrzynczak <twawrzynczak@chromium.org> Gerrit-Reviewer: Werner Zeh <werner.zeh@siemens.com> Gerrit-Reviewer: build bot (Jenkins) <no-reply@coreboot.org> Gerrit-CC: 9elements QA <hardwaretestrobot@gmail.com> Gerrit-CC: Aaron Durbin <adurbin@chromium.org> Gerrit-CC: Paul Menzel <paulepanter@mailbox.org> Gerrit-CC: Varshit Pandya <pandyavarshit@gmail.com> Gerrit-Comment-Date: Wed, 07 Sep 2022 11:01:15 +0000 Gerrit-HasComments: Yes Gerrit-Has-Labels: No Gerrit-MessageType: comment
participants (8)
-
9elements QA (Code Review)
-
Aaron Durbin (Code Review)
-
Angel Pons (Code Review)
-
Arthur Heymans (Code Review)
-
build bot (Jenkins) (Code Review)
-
Martin L Roth (Code Review)
-
Nico Huber (Code Review)
-
Subrata Banik (Code Review)