Change in coreboot[master]: memrange: Add support for stealing required memory from given ranges
Furquan Shaikh has uploaded this change for review. ( https://review.coreboot.org/c/coreboot/+/39484 )
Change subject: memrange: Add support for stealing required memory from given ranges ......................................................................
memrange: Add support for stealing required memory from given ranges
This change adds support for memranges_steal() which allows the user to steal memory from the list of available ranges by providing a set of constraints (limit, size, alignment, tag). It tries to find the first big enough range that can satisfy the constraints, creates a hole as per the request and returns base of the stolen memory.
BUG=b:149186922
Signed-off-by: Furquan Shaikh furquan@google.com Change-Id: Ibe9cfae18fc6101ab2e7e27233e45324c8117708 --- M src/include/memrange.h M src/lib/memrange.c 2 files changed, 60 insertions(+), 0 deletions(-)
git pull ssh://review.coreboot.org:29418/coreboot refs/changes/84/39484/1
diff --git a/src/include/memrange.h b/src/include/memrange.h index fba77af..9b1d1d2 100644 --- a/src/include/memrange.h +++ b/src/include/memrange.h @@ -16,6 +16,7 @@ #define MEMRANGE_H_
#include <device/resource.h> +#include <stdbool.h>
/* A memranges structure consists of a list of range_entry(s). The structure * is exposed so that a memranges can be used on the stack if needed. */ @@ -166,4 +167,17 @@ /* Returns next entry after the provided entry. NULL if r is last. */ struct range_entry *memranges_next_entry(struct memranges *ranges, const struct range_entry *r); + +/* Steals memory from the available list in given ranges as per the constraints: + * limit = Limit beyond which the stolen memory cannot grow. + * size = Requested size for the stolen memory. + * align = Alignment requirements for the starting address of the stolen memory. + * tag = Use a range that matches the given tag. + * + * If it is not possible to fulfill the request as per given constraints, this function returns + * false. Else, it sets the base address of stolen memory in stolen_base, creates a hole of + * required size at the stolen_base and returns true to indicate success. */ +bool memranges_steal(struct memranges *ranges, resource_t limit, resource_t size, size_t align, + unsigned long tag, resource_t *stolen_base); + #endif /* MEMRANGE_H_ */ diff --git a/src/lib/memrange.c b/src/lib/memrange.c index a76f24c..b57c6cb 100644 --- a/src/lib/memrange.c +++ b/src/lib/memrange.c @@ -385,3 +385,49 @@ { return r->next; } + +/* 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, + size_t align, unsigned long tag) +{ + const struct range_entry *r; + resource_t base, end; + + memranges_each_entry(r, ranges) { + + if (r->tag != tag) + continue; + + base = ALIGN_UP(r->begin, align); + end = base + size - 1; + + if (end > r->end) + continue; + + if (end > limit) + continue; + + return r; + } + + return NULL; +} + +bool memranges_steal(struct memranges *ranges, resource_t limit, resource_t size, size_t align, + unsigned long tag, resource_t *stolen_base) +{ + resource_t base; + const struct range_entry *r = memranges_find_entry(ranges, limit, size, align, tag); + + if (r == NULL) + return false; + + base = ALIGN_UP(r->begin, align); + + memranges_create_hole(ranges, base, size); + *stolen_base = base; + + return true; +}
Patrick Georgi has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/39484 )
Change subject: memrange: Add support for stealing required memory from given ranges ......................................................................
Patch Set 1:
(5 comments)
https://review.coreboot.org/c/coreboot/+/39484/1//COMMIT_MSG Commit Message:
https://review.coreboot.org/c/coreboot/+/39484/1//COMMIT_MSG@9 PS1, Line 9: This change adds support for nit: just "Add"?
https://review.coreboot.org/c/coreboot/+/39484/1/src/include/memrange.h File src/include/memrange.h:
https://review.coreboot.org/c/coreboot/+/39484/1/src/include/memrange.h@172 PS1, Line 172: Limit beyond which the stolen memory cannot grow so an upper bound for the memory range to reserve?
https://review.coreboot.org/c/coreboot/+/39484/1/src/include/memrange.h@177 PS1, Line 177: If it is not possible to fulfill the request as per given constraints, this function returns : * false. Else, it sets the base address of stolen memory in stolen_base, creates a hole of : * required size at the stolen_base and returns true to indicate success I think it's better to state the successful case first. It could also be clearer that stolen_base is an output argument, never to be read from (this statement can be interpreted to mean that a value put in there might be used to choose the base address).
How about: "If the constraints can be satified, this functin creates a hole in the memrange, writes the base address of that hole to stolen_base and returns true. Otherwise it returns false"?
https://review.coreboot.org/c/coreboot/+/39484/1/src/lib/memrange.c File src/lib/memrange.c:
https://review.coreboot.org/c/coreboot/+/39484/1/src/lib/memrange.c@397 PS1, Line 397: if (size == 0) return NULL; otherwise memranges_steal() with a computed size==0 leads to weird artifacts in stolen_base. While at it, maybe check that align is a power of two (ALIGN_UP does wonky stuff otherwise)?
https://review.coreboot.org/c/coreboot/+/39484/1/src/lib/memrange.c@403 PS1, Line 403: base = ALIGN_UP(r->begin, align); do you intend to use the new memrange align attribute for comparison, too? if (!IS_ALIGNED(align, r->align)) continue; or something like that?
Hello build bot (Jenkins), Duncan Laurie, Subrata Banik, Aaron Durbin,
I'd like you to reexamine a change. Please visit
https://review.coreboot.org/c/coreboot/+/39484
to look at the new patch set (#2).
Change subject: memrange: Add support for stealing required memory from given ranges ......................................................................
memrange: Add support for stealing required memory from given ranges
This change adds memranges_steal() which allows the user to steal memory from the list of available ranges by providing a set of constraints (limit, size, alignment, tag). It tries to find the first big enough range that can satisfy the constraints, creates a hole as per the request and returns base of the stolen memory.
BUG=b:149186922
Signed-off-by: Furquan Shaikh furquan@google.com Change-Id: Ibe9cfae18fc6101ab2e7e27233e45324c8117708 --- M src/include/memrange.h M src/lib/memrange.c 2 files changed, 70 insertions(+), 0 deletions(-)
git pull ssh://review.coreboot.org:29418/coreboot refs/changes/84/39484/2
Furquan Shaikh has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/39484 )
Change subject: memrange: Add support for stealing required memory from given ranges ......................................................................
Patch Set 2:
(5 comments)
https://review.coreboot.org/c/coreboot/+/39484/1//COMMIT_MSG Commit Message:
https://review.coreboot.org/c/coreboot/+/39484/1//COMMIT_MSG@9 PS1, Line 9: This change adds support for
nit: just "Add"?
Done
https://review.coreboot.org/c/coreboot/+/39484/1/src/include/memrange.h File src/include/memrange.h:
https://review.coreboot.org/c/coreboot/+/39484/1/src/include/memrange.h@172 PS1, Line 172: Limit beyond which the stolen memory cannot grow
so an upper bound for the memory range to reserve?
Done
https://review.coreboot.org/c/coreboot/+/39484/1/src/include/memrange.h@177 PS1, Line 177: If it is not possible to fulfill the request as per given constraints, this function returns : * false. Else, it sets the base address of stolen memory in stolen_base, creates a hole of : * required size at the stolen_base and returns true to indicate success
I think it's better to state the successful case first. […]
Done
https://review.coreboot.org/c/coreboot/+/39484/1/src/lib/memrange.c File src/lib/memrange.c:
https://review.coreboot.org/c/coreboot/+/39484/1/src/lib/memrange.c@397 PS1, Line 397:
if (size == 0) return NULL; otherwise memranges_steal() with a computed size==0 leads to weird artif […]
Done
https://review.coreboot.org/c/coreboot/+/39484/1/src/lib/memrange.c@403 PS1, Line 403: base = ALIGN_UP(r->begin, align);
do you intend to use the new memrange align attribute for comparison, too? if (!IS_ALIGNED(align, r- […]
Done. Add it before the loop since each range entry does not have a separate alignment. It is applicable to entire list of ranges.
Patrick Georgi has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/39484 )
Change subject: memrange: Add support for stealing required memory from given ranges ......................................................................
Patch Set 2: Code-Review+2
Patrick Georgi has submitted this change. ( https://review.coreboot.org/c/coreboot/+/39484 )
Change subject: memrange: Add support for stealing required memory from given ranges ......................................................................
memrange: Add support for stealing required memory from given ranges
This change adds memranges_steal() which allows the user to steal memory from the list of available ranges by providing a set of constraints (limit, size, alignment, tag). It tries to find the first big enough range that can satisfy the constraints, creates a hole as per the request and returns base of the stolen memory.
BUG=b:149186922
Signed-off-by: Furquan Shaikh furquan@google.com Change-Id: Ibe9cfae18fc6101ab2e7e27233e45324c8117708 Reviewed-on: https://review.coreboot.org/c/coreboot/+/39484 Tested-by: build bot (Jenkins) no-reply@coreboot.org Reviewed-by: Patrick Georgi pgeorgi@google.com --- M src/include/memrange.h M src/lib/memrange.c 2 files changed, 70 insertions(+), 0 deletions(-)
Approvals: build bot (Jenkins): Verified Patrick Georgi: Looks good to me, approved
diff --git a/src/include/memrange.h b/src/include/memrange.h index 0d20236..f8fa033 100644 --- a/src/include/memrange.h +++ b/src/include/memrange.h @@ -16,6 +16,7 @@ #define MEMRANGE_H_
#include <device/resource.h> +#include <stdbool.h>
/* A memranges structure consists of a list of range_entry(s). The structure * is exposed so that a memranges can be used on the stack if needed. */ @@ -166,4 +167,18 @@ /* Returns next entry after the provided entry. NULL if r is last. */ struct range_entry *memranges_next_entry(struct memranges *ranges, 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. + * size = Requested size for the stolen memory. + * align = Alignment requirements for the starting address of the stolen memory. + * (Alignment must be a power of 2). + * tag = Use a range that matches the given tag. + * + * 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, size_t align, + unsigned long tag, resource_t *stolen_base); + #endif /* MEMRANGE_H_ */ diff --git a/src/lib/memrange.c b/src/lib/memrange.c index 21fff00..b9c09e8 100644 --- a/src/lib/memrange.c +++ b/src/lib/memrange.c @@ -391,3 +391,58 @@ { return r->next; } + +/* 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, + size_t align, unsigned long tag) +{ + const struct range_entry *r; + resource_t base, end; + + if (size == 0) + return NULL; + + if (!IS_POWER_OF_2(align)) + return NULL; + + if (!IS_ALIGNED(align, ranges->align)) + return NULL; + + memranges_each_entry(r, ranges) { + + if (r->tag != tag) + continue; + + base = ALIGN_UP(r->begin, align); + end = base + size - 1; + + if (end > r->end) + continue; + + if (end > limit) + continue; + + return r; + } + + return NULL; +} + +bool memranges_steal(struct memranges *ranges, resource_t limit, resource_t size, size_t align, + unsigned long tag, resource_t *stolen_base) +{ + resource_t base; + const struct range_entry *r = memranges_find_entry(ranges, limit, size, align, tag); + + if (r == NULL) + return false; + + base = ALIGN_UP(r->begin, align); + + memranges_create_hole(ranges, base, size); + *stolen_base = base; + + return true; +}
Aaron Durbin has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/39484 )
Change subject: memrange: Add support for stealing required memory from given ranges ......................................................................
Patch Set 3:
(1 comment)
https://review.coreboot.org/c/coreboot/+/39484/3/src/lib/memrange.c File src/lib/memrange.c:
https://review.coreboot.org/c/coreboot/+/39484/3/src/lib/memrange.c@410 PS3, Line 410: if (!IS_ALIGNED(align, ranges->align)) Why would the requested alignment have to be equal to the memranges alignment? It seems that it could be limiting in practice. I'll see how the patchset progresses, but it seems we need to either error on large or small alignments then request alignments that match those -- that seems odd.
Aaron Durbin has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/39484 )
Change subject: memrange: Add support for stealing required memory from given ranges ......................................................................
Patch Set 3:
(1 comment)
https://review.coreboot.org/c/coreboot/+/39484/3/src/lib/memrange.c File src/lib/memrange.c:
https://review.coreboot.org/c/coreboot/+/39484/3/src/lib/memrange.c@433 PS3, Line 433: limit Is this inclusive or exclusive? It seems like it's inclusive given the '>' check above.
Aaron Durbin has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/39484 )
Change subject: memrange: Add support for stealing required memory from given ranges ......................................................................
Patch Set 3:
(1 comment)
https://review.coreboot.org/c/coreboot/+/39484/3/src/lib/memrange.c File src/lib/memrange.c:
https://review.coreboot.org/c/coreboot/+/39484/3/src/lib/memrange.c@422 PS3, Line 422: continue; Since the ranges are in order wouldn't this be a return NULL case? Same for the limit check.
Furquan Shaikh has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/39484 )
Change subject: memrange: Add support for stealing required memory from given ranges ......................................................................
Patch Set 3:
(3 comments)
https://review.coreboot.org/c/coreboot/+/39484/3/src/lib/memrange.c File src/lib/memrange.c:
https://review.coreboot.org/c/coreboot/+/39484/3/src/lib/memrange.c@410 PS3, Line 410: if (!IS_ALIGNED(align, ranges->align))
Why would the requested alignment have to be equal to the memranges alignment? It seems that it coul […]
Dropped this as part of https://review.coreboot.org/c/coreboot/+/39810
https://review.coreboot.org/c/coreboot/+/39484/3/src/lib/memrange.c@422 PS3, Line 422: continue;
Since the ranges are in order wouldn't this be a return NULL case? Same for the limit check.
For the limit - yes. But, I don't think that applies to r->end. We can have multiple ranges which are smaller than what the request is and so cannot be satisfied, but there could be a range later on which could potentially satisfy the request.
Example: Ranges: Begin End 0x100 0x1ff 0x300 0xfff
Request: Size: 0x300 Limit: 0xffffffff Align: 1 Tag: xyz
In this case, for first range entry, base = 0x100, end = 0x3ff. Thus, we need to check the next range entry. base = 0x300 end = 0x5ff and carve out a hole out of this.
But, I agree with limit if end has crossed limit, none of the following range entries can satisfy the request.
https://review.coreboot.org/c/coreboot/+/39484/3/src/lib/memrange.c@433 PS3, Line 433: limit
Is this inclusive or exclusive? It seems like it's inclusive given the '>' check above.
Yes, it is inclusive. I will update the comment.
Furquan Shaikh has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/39484 )
Change subject: memrange: Add support for stealing required memory from given ranges ......................................................................
Patch Set 3:
(3 comments)
https://review.coreboot.org/c/coreboot/+/39484/3/src/lib/memrange.c File src/lib/memrange.c:
https://review.coreboot.org/c/coreboot/+/39484/3/src/lib/memrange.c@410 PS3, Line 410: if (!IS_ALIGNED(align, ranges->align))
Dropped this as part of https://review.coreboot. […]
Sorry, I must have missed your comment earlier. Just noticed your comment was from March 26 when I received notification for the other comments.
https://review.coreboot.org/c/coreboot/+/39484/3/src/lib/memrange.c@422 PS3, Line 422: continue;
For the limit - yes. But, I don't think that applies to r->end. […]
https://review.coreboot.org/c/coreboot/+/41104
https://review.coreboot.org/c/coreboot/+/39484/3/src/lib/memrange.c@433 PS3, Line 433: limit
Yes, it is inclusive. I will update the comment.
https://review.coreboot.org/c/coreboot/+/41103
-
Aaron Durbin (Code Review) -
Furquan Shaikh (Code Review)
-
Patrick Georgi (Code Review)