Furquan Shaikh has uploaded this change for review. ( https://review.coreboot.org/c/coreboot/+/41443 )
Change subject: device: Add support for resource allocator v4 ......................................................................
device: Add support for resource allocator v4
This change adds back support for the resource allocator using multiple ranges as originally landed in CB:39486 and reverted in CB:41413. The new resource allocator can be selected by Kconfig option RESOURCE_ALLOCATOR_V4. It was identified that there are some AMD chipsets in the tree that do not really work well with the dynamic resource allocation. Until these chipsets are fixed, old(v3) and new(v4) of the resource allocator need to live side-by-side in the tree.
This change picks up the same additions as performed in CB:39486 along with the following changes: 1. Changes are incorporated to avoid fixed resources hanging off pci domain device (CB:41363) 2. Changes to set up alignment for memranges when intializing them. This is done to ensure that the right granularity is used for IORESOURCE_IO(no special alignment) and IORESOURCE_MEM(4KiB) resource requests.
Original commit message: This change updates the resource allocator in coreboot to allow using multiple ranges for resource allocation rather than restricting available window to a single base/limit pair. This is done in preparation to allow 64-bit resource allocation.
Following changes are made as part of this: a) Resource allocator still makes 2 passes at the entire tree. The first pass is to gather the resource requirements of each device under each domain. It walks recursively in DFS fashion to gather the requirements of the leaf devices and propagates this back up to the downstream bridges of the domain. Domain is special in the sense that it has fixed resource ranges. Hence, the resource requirements from the downstream devices have no effect on the domain resource windows. This results in domain resource limits being unmodified after the first pass.
b) Once the requirements for all the devices under the domain are gathered, resource allocator walks a second time to allocate resources to downstream devices as per the requirements. Here, instead of maintaining a single window for allocating resources, it creates a list of memranges starting with the resource window at domain and then applying constraints to create holes for any fixed resources. This ensures that there is no overlap with fixed resources under the domain.
c) Domain does not differentiate between mem and prefmem. Since they are allocated space from the same resource window at the domain level, it considers all resource requests from downstream devices of the domain independent of the prefetch type.
d) Once resource allocation is done at the domain level, resource allocator walks down the downstream bridges and continues the same process until it reaches the leaves. Bridges have separate windows for mem and prefmem. Hence, unlike domain, the resource allocator at bridge level ensures that downstream requirements are satisfied by taking prefetch type into consideration.
e) This whole 2-pass process is performed for every domain in the system under the assumption that domains do not have overlapping address spaces.
Noticeable differences from previous resource allocator: a) Changes in print logs observed due to flows being slightly different. b) Base, limit and size of domain resources are no longer updated based on downstream requirements. c) Memranges are used instead of a single base/limit pair for determining resource allocation. d) Previously, if a resource request did not fit in the available base/limit window, then the resource would be allocated over DRAM or any other address space defeating the principle of "no overlap". With this change, any time a resource cannot fit in the available ranges, it complains and ensures that the resource is effectively disabled by setting base same as the limit. e) Resource allocator no longer looks at multiple links to determine the right bus for a resource. None of the current boards have multiple buses under any downstream device of the domain. The only device with multiple links seems to be the cpu cluster device for some AMD platforms.
Change-Id: Ide4d98528197bb03850a8fb4d73c41cd2c0195aa Signed-off-by: Furquan Shaikh furquan@google.com --- M src/device/Kconfig M src/device/Makefile.inc A src/device/resource_allocator_v4.c 3 files changed, 570 insertions(+), 0 deletions(-)
git pull ssh://review.coreboot.org:29418/coreboot refs/changes/43/41443/1
diff --git a/src/device/Kconfig b/src/device/Kconfig index bfa4759..e340841 100644 --- a/src/device/Kconfig +++ b/src/device/Kconfig @@ -801,4 +801,13 @@ This config option enables resource allocator v3 which performs top down allocation of resources in a single MMIO window.
+config RESOURCE_ALLOCATOR_V4 + bool + default n if RESOURCE_ALLOCATOR_V3 + default y if !RESOURCE_ALLOCATOR_V3 + help + This config option enables resource allocator v4 which uses multiple + ranges for allocating resources. This allows allocation of resources + above 4G boundary as well. + endmenu diff --git a/src/device/Makefile.inc b/src/device/Makefile.inc index 9bbab37..2e62d42 100644 --- a/src/device/Makefile.inc +++ b/src/device/Makefile.inc @@ -61,3 +61,4 @@
ramstage-y += resource_allocator_common.c ramstage-$(CONFIG_RESOURCE_ALLOCATOR_V3) += resource_allocator_v3.c +ramstage-$(CONFIG_RESOURCE_ALLOCATOR_V4) += resource_allocator_v4.c diff --git a/src/device/resource_allocator_v4.c b/src/device/resource_allocator_v4.c new file mode 100644 index 0000000..ac65ed4 --- /dev/null +++ b/src/device/resource_allocator_v4.c @@ -0,0 +1,560 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ + +#include <console/console.h> +#include <device/device.h> +#include <memrange.h> +#include <post.h> + +/** + * Round a number up to an alignment. + * + * @param val The starting value. + * @param pow Alignment as a power of two. + * @return Rounded up number. + */ +static resource_t round(resource_t val, unsigned long pow) +{ + return ALIGN_UP(val, POWER_OF_2(pow)); +} + +static const char *resource2str(const struct resource *res) +{ + if (res->flags & IORESOURCE_IO) + return "io"; + if (res->flags & IORESOURCE_PREFETCH) + return "prefmem"; + if (res->flags & IORESOURCE_MEM) + return "mem"; + return "undefined"; +} + +static bool dev_has_children(const struct device *dev) +{ + const struct bus *bus = dev->link_list; + return bus && bus->children; +} + +/* + * During pass 1, once all the requirements for downstream devices of a bridge are gathered, + * this function calculates the overall resource requirement for the bridge. It starts by + * picking the largest resource requirement downstream for the given resource type and works by + * adding requirements in descending order. + * + * Additionally, it takes alignment and limits of the downstream devices into consideration and + * ensures that they get propagated to the bridge resource. This is required to guarantee that + * the upstream bridge/domain honors the limit and alignment requirements for this bridge based + * on the tightest constraints downstream. + */ +static void update_bridge_resource(const struct device *bridge, struct resource *bridge_res, + unsigned long type_match) +{ + const struct device *child; + struct resource *child_res; + resource_t base; + bool first_child_res = true; + const unsigned long type_mask = IORESOURCE_TYPE_MASK | IORESOURCE_PREFETCH; + struct bus *bus = bridge->link_list; + + child_res = NULL; + + /* + * `base` keeps track of where the next allocation for child resource can take place + * from within the bridge resource window. Since the bridge resource window allocation + * is not performed yet, it can start at 0. Base gets updated every time a resource + * requirement is accounted for in the loop below. After scanning all these resources, + * base will indicate the total size requirement for the current bridge resource + * window. + */ + base = 0; + + printk(BIOS_SPEW, "%s %s: size: %llx align: %d gran: %d limit: %llx\n", + dev_path(bridge), resource2str(bridge_res), bridge_res->size, + bridge_res->align, bridge_res->gran, bridge_res->limit); + + while ((child = largest_resource(bus, &child_res, type_mask, type_match))) { + + /* Size 0 resources can be skipped. */ + if (!child_res->size) + continue; + + /* + * Propagate the resource alignment to the bridge resource if this is the first + * child resource with non-zero size being considered. For all other children + * resources, alignment is taken care of by updating the base to round up as per + * the child resource alignment. It is guaranteed that pass 2 follows the exact + * same method of picking the resource for allocation using + * largest_resource(). Thus, as long as the alignment for first child resource + * is propagated up to the bridge resource, it can be guaranteed that the + * alignment for all resources is appropriately met. + */ + if (first_child_res && (child_res->align > bridge_res->align)) + bridge_res->align = child_res->align; + + first_child_res = false; + + /* + * Propagate the resource limit to the bridge resource only if child resource + * limit is non-zero. If a downstream device has stricter requirements + * w.r.t. limits for any resource, that constraint needs to be propagated back + * up to the downstream bridges of the domain. This guarantees that the resource + * allocation which starts at the domain level takes into account all these + * constraints thus working on a global view. + */ + if (child_res->limit && (child_res->limit < bridge_res->limit)) + bridge_res->limit = child_res->limit; + + /* + * Alignment value of 0 means that the child resource has no alignment + * requirements and so the base value remains unchanged here. + */ + base = round(base, child_res->align); + + printk(BIOS_SPEW, "%s %02lx * [0x%llx - 0x%llx] %s\n", + dev_path(child), child_res->index, base, base + child_res->size - 1, + resource2str(child_res)); + + base += child_res->size; + } + + /* + * After all downstream device resources are scanned, `base` represents the total size + * requirement for the current bridge resource window. This size needs to be rounded up + * to the granularity requirement of the bridge to ensure that the upstream + * bridge/domain allocates big enough window. + */ + bridge_res->size = round(base, bridge_res->gran); + + printk(BIOS_SPEW, "%s %s: size: %llx align: %d gran: %d limit: %llx done\n", + dev_path(bridge), resource2str(bridge_res), bridge_res->size, + bridge_res->align, bridge_res->gran, bridge_res->limit); +} + +/* + * During pass 1, resource allocator at bridge level gathers requirements from downstream + * devices and updates its own resource windows for the provided resource type. + */ +static void compute_bridge_resources(const struct device *bridge, unsigned long type_match) +{ + const struct device *child; + struct resource *res; + struct bus *bus = bridge->link_list; + const unsigned long type_mask = IORESOURCE_TYPE_MASK | IORESOURCE_PREFETCH; + + for (res = bridge->resource_list; res; res = res->next) { + if (!(res->flags & IORESOURCE_BRIDGE)) + continue; + + if ((res->flags & type_mask) != type_match) + continue; + + /* + * Ensure that the resource requirements for all downstream bridges are + * gathered before updating the window for current bridge resource. + */ + for (child = bus->children; child; child = child->sibling) { + if (!dev_has_children(child)) + continue; + compute_bridge_resources(child, type_match); + } + + /* + * Update the window for current bridge resource now that all downstream + * requirements are gathered. + */ + update_bridge_resource(bridge, res, type_match); + } +} + +/* + * During pass 1, resource allocator walks down the entire sub-tree of a domain. It gathers + * resource requirements for every downstream bridge by looking at the resource requests of its + * children. Thus, the requirement gathering begins at the leaf devices and is propagated back + * up to the downstream bridges of the domain. + * + * At domain level, it identifies every downstream bridge and walks down that bridge to gather + * requirements for each resource type i.e. i/o, mem and prefmem. Since bridges have separate + * windows for mem and prefmem, requirements for each need to be collected separately. + * + * Domain resource windows are fixed ranges and hence requirement gathering does not result in + * any changes to these fixed ranges. + */ +static void compute_domain_resources(const struct device *domain) +{ + const struct device *child; + + if (domain->link_list == NULL) + return; + + for (child = domain->link_list->children; child; child = child->sibling) { + + /* Skip if this is not a bridge or has no children under it. */ + if (!dev_has_children(child)) + continue; + + compute_bridge_resources(child, IORESOURCE_IO); + compute_bridge_resources(child, IORESOURCE_MEM); + compute_bridge_resources(child, IORESOURCE_MEM | IORESOURCE_PREFETCH); + } +} + +static unsigned char get_alignment_by_resource_type(const struct resource *res) +{ + if (res->flags & IORESOURCE_MEM) + return 12; /* Page-aligned --> log2(4KiB) */ + else if (res->flags & IORESOURCE_IO) + return 0; /* No special alignment required --> log2(1) */ + + die("Unexpected resource type: flags(%d)!\n", res->flags); +} + +static void initialize_memranges(struct memranges *ranges, const struct resource *res, + unsigned long memrange_type) +{ + resource_t res_base; + resource_t res_limit; + unsigned align = get_alignment_by_resource_type(res); + + memranges_init_empty_with_alignment(ranges, NULL, 0, align); + + if (res == NULL) + return; + + res_base = res->base; + res_limit = res->limit; + + if (res_base == res_limit) + return; + + memranges_insert(ranges, res_base, res_limit - res_base + 1, memrange_type); +} + +static void print_resource_ranges(const struct memranges *ranges) +{ + const struct range_entry *r; + + printk(BIOS_INFO, "Resource ranges:\n"); + + if (memranges_is_empty(ranges)) + printk(BIOS_INFO, "EMPTY!!\n"); + + memranges_each_entry(r, ranges) { + printk(BIOS_INFO, "Base: %llx, Size: %llx, Tag: %lx\n", + range_entry_base(r), range_entry_size(r), range_entry_tag(r)); + } +} + +static void mark_resource_invalid(struct resource *res) +{ + res->base = res->limit; + res->flags |= IORESOURCE_ASSIGNED; +} + +/* + * This is where the actual allocation of resources happens during pass 2. Given the list of + * memory ranges corresponding to the resource of given type, it finds the biggest unallocated + * resource using the type mask on the downstream bus. This continues in a descending + * order until all resources of given type are allocated address space within the current + * resource window. + * + * If a downstream resource cannot be allocated space for any reason, then its base is set to + * its limit and flags are updated to indicate that the resource assignment is complete. This is + * done to ensure that it does not confuse find_pci_tolm(). + */ +static void allocate_child_resources(struct bus *bus, struct memranges *ranges, + unsigned long type_mask, unsigned long type_match) +{ + struct resource *resource = NULL; + const struct device *dev; + + while ((dev = largest_resource(bus, &resource, type_mask, type_match))) { + + if (!resource->size) { + mark_resource_invalid(resource); + continue; + } + + if (memranges_steal(ranges, resource->limit, resource->size, resource->align, + type_match, &resource->base) == false) { + printk(BIOS_ERR, "ERROR: Resource didn't fit!!! "); + printk(BIOS_SPEW, "%s %02lx * size: 0x%llx limit: %llx %s\n", + dev_path(dev), resource->index, + resource->size, resource->limit, resource2str(resource)); + mark_resource_invalid(resource); + continue; + } + + resource->limit = resource->base + resource->size - 1; + resource->flags |= IORESOURCE_ASSIGNED; + + printk(BIOS_SPEW, "%s %02lx * [0x%llx - 0x%llx] limit: %llx %s\n", + dev_path(dev), resource->index, resource->base, + resource->size ? resource->base + resource->size - 1 : + resource->base, resource->limit, resource2str(resource)); + } +} + +static void update_constraints(void *gp, struct device *dev, struct resource *res) +{ + struct memranges *ranges = gp; + + if (!res->size) + return; + + printk(BIOS_SPEW, "%s: %s %02lx base %08llx limit %08llx %s (fixed)\n", + __func__, dev_path(dev), res->index, res->base, + res->base + res->size - 1, resource2str(res)); + + memranges_create_hole(ranges, res->base, res->size); +} + +static void constrain_domain_resources(struct device *domain, struct memranges *ranges, + unsigned long type) +{ + struct resource *res; + struct bus *bus = domain->link_list; + unsigned long mask_match = type | IORESOURCE_FIXED; + + /* + * Scan the entire tree to identify any fixed resources allocated by any device to + * ensure that the address map for domain resources are appropriately updated. + * + * Domains can typically provide memrange for entire address space. So, this function + * punches holes in the address space for all fixed resources that are already + * defined. Both IO and normal memory resources are added as fixed. Both need to be + * removed from address space where dynamic resource allocations are sourced. + */ + search_bus_resources(bus, mask_match, mask_match, update_constraints, ranges); + + if (type == IORESOURCE_IO) { + /* + * Don't allow allocations in the VGA I/O range. PCI has special cases for + * that. + */ + memranges_create_hole(ranges, 0x3b0, 0x3df); + + /* + * Resource allocator no longer supports the legacy behavior where I/O resource + * allocation is guaranteed to avoid aliases over legacy PCI expansion card + * addresses. + */ + } + + /* + * Some domains have fixed resources hanging directly off the device. Avoid those fixed + * resources in the address space for alocation. + */ + for (res = domain->resource_list; res != NULL; res = res->next) { + if ((res->flags & mask_match) != mask_match) + continue; + update_constraints(ranges, domain, res); + } +} + +/* + * This function creates a list of memranges of given type using the resource that is + * provided. If the given resource is NULL or if the resource window size is 0, then it creates + * an empty list. This results in resource allocation for that resource type failing for all + * downstream devices since there is nothing to allocate from. + * + * In case of domain, it applies additional constraints to ensure that the memranges do not + * overlap any of the fixed resources under that domain. Domain typically seems to provide + * memrange for entire address space. Thus, it is up to the chipset to add DRAM and all other + * windows which cannot be used for resource allocation as fixed resources. + */ +static void setup_resource_ranges(struct device *dev, const struct resource *res, + unsigned long type, struct memranges *ranges) +{ + printk(BIOS_SPEW, "%s %s: base: %llx size: %llx align: %d gran: %d limit: %llx\n", + dev_path(dev), resource2str(res), res->base, res->size, res->align, + res->gran, res->limit); + + initialize_memranges(ranges, res, type); + + if (dev->path.type == DEVICE_PATH_DOMAIN) + constrain_domain_resources(dev, ranges, type); + + print_resource_ranges(ranges); +} + +static void cleanup_resource_ranges(const struct device *dev, struct memranges *ranges, + const struct resource *res) +{ + memranges_teardown(ranges); + printk(BIOS_SPEW, "%s %s: base: %llx size: %llx align: %d gran: %d limit: %llx done\n", + dev_path(dev), resource2str(res), res->base, res->size, res->align, + res->gran, res->limit); +} + +/* + * Pass 2 of resource allocator at the bridge level loops through all the resources for the + * bridge and generates a list of memory ranges similar to that at the domain level. However, + * there is no need to apply any additional constraints since the window allocated to the bridge + * is guaranteed to be non-overlapping by the allocator at domain level. + * + * Allocation at the bridge level works the same as at domain level (starts with the biggest + * resource requirement from downstream devices and continues in descending order). One major + * difference at the bridge level is that it considers prefmem resources separately from mem + * resources. + * + * Once allocation at the current bridge is complete, resource allocator continues walking down + * the downstream bridges until it hits the leaf devices. + */ +static void allocate_bridge_resources(struct device *bridge) +{ + struct memranges ranges; + const struct resource *res; + struct bus *bus = bridge->link_list; + unsigned long type_match; + struct device *child; + const unsigned long type_mask = IORESOURCE_TYPE_MASK | IORESOURCE_PREFETCH; + + for (res = bridge->resource_list; res; res = res->next) { + if (!res->size) + continue; + + if (!(res->flags & IORESOURCE_BRIDGE)) + continue; + + type_match = res->flags & type_mask; + + setup_resource_ranges(bridge, res, type_match, &ranges); + allocate_child_resources(bus, &ranges, type_mask, type_match); + cleanup_resource_ranges(bridge, &ranges, res); + } + + for (child = bus->children; child; child = child->sibling) { + if (!dev_has_children(child)) + continue; + + allocate_bridge_resources(child); + } +} + +static const struct resource *find_domain_resource(const struct device *domain, + unsigned long type) +{ + const struct resource *res; + + for (res = domain->resource_list; res; res = res->next) { + if (res->flags & IORESOURCE_FIXED) + continue; + + if ((res->flags & IORESOURCE_TYPE_MASK) == type) + return res; + } + + return NULL; +} + +/* + * Pass 2 of resource allocator begins at the domain level. Every domain has two types of + * resources - io and mem. For each of these resources, this function creates a list of memory + * ranges that can be used for downstream resource allocation. This list is constrained to + * remove any fixed resources in the domain sub-tree of the given resource type. It then uses + * the memory ranges to apply best fit on the resource requirements of the downstream devices. + * + * Once resources are allocated to all downstream devices of the domain, it walks down each + * downstream bridge to continue the same process until resources are allocated to all devices + * under the domain. + */ +static void allocate_domain_resources(struct device *domain) +{ + struct memranges ranges; + struct device *child; + const struct resource *res; + + /* Resource type I/O */ + res = find_domain_resource(domain, IORESOURCE_IO); + if (res) { + setup_resource_ranges(domain, res, IORESOURCE_IO, &ranges); + allocate_child_resources(domain->link_list, &ranges, IORESOURCE_TYPE_MASK, + IORESOURCE_IO); + cleanup_resource_ranges(domain, &ranges, res); + } + + /* + * Resource type Mem: + * Domain does not distinguish between mem and prefmem resources. Thus, the resource + * allocation at domain level considers mem and prefmem together when finding the best + * fit based on the biggest resource requirement. + */ + res = find_domain_resource(domain, IORESOURCE_MEM); + if (res) { + setup_resource_ranges(domain, res, IORESOURCE_MEM, &ranges); + allocate_child_resources(domain->link_list, &ranges, IORESOURCE_TYPE_MASK, + IORESOURCE_MEM); + cleanup_resource_ranges(domain, &ranges, res); + } + + for (child = domain->link_list->children; child; child = child->sibling) { + if (!dev_has_children(child)) + continue; + + /* Continue allocation for all downstream bridges. */ + allocate_bridge_resources(child); + } +} + +/* + * This function forms the guts of the resource allocator. It walks through the entire device + * tree for each domain two times. + * + * Every domain has a fixed set of ranges. These ranges cannot be relaxed based on the + * requirements of the downstream devices. They represent the available windows from which + * resources can be allocated to the different devices under the domain. + * + * In order to identify the requirements of downstream devices, resource allocator walks in a + * DFS fashion. It gathers the requirements from leaf devices and propagates those back up + * to their upstream bridges until the requirements for all the downstream devices of the domain + * are gathered. This is referred to as pass 1 of resource allocator. + * + * Once the requirements for all the devices under the domain are gathered, resource allocator + * walks a second time to allocate resources to downstream devices as per the + * requirements. It always picks the biggest resource request as per the type (i/o and mem) to + * allocate space from its fixed window to the immediate downstream device of the domain. In + * order to accomplish best fit for the resources, a list of ranges is maintained by each + * resource type (i/o and mem). Domain does not differentiate between mem and prefmem. Since + * they are allocated space from the same window, the resource allocator at the domain level + * ensures that the biggest requirement is selected indepedent of the prefetch type. Once the + * resource allocation for all immediate downstream devices is complete at the domain level, + * resource allocator walks down the subtree for each downstream bridge to continue the + * allocation process at the bridge level. Since bridges have separate windows for i/o, mem and + * prefmem, best fit algorithm at bridge level looks for the biggest requirement considering + * prefmem resources separately from non-prefmem resources. This continues until resource + * allocation is performed for all downstream bridges in the domain sub-tree. This is referred + * to as pass 2 of resource allocator. + * + * Some rules that are followed by the resource allocator: + * - Allocate resource locations for every device as long as the requirements can be satisfied. + * - If a resource cannot be allocated any address space, then that resource needs to be + * properly updated to ensure that it does not incorrectly overlap some address space reserved + * for a different purpose. + * - Don't overlap with resources in fixed locations. + * - Don't overlap and follow the rules of bridges -- downstream devices of bridges should use + * parts of the address space allocated to the bridge. + */ +void allocate_resources(const struct device *root) +{ + struct device *child; + + if ((root == NULL) || (root->link_list == NULL)) + return; + + for (child = root->link_list->children; child; child = child->sibling) { + + if (child->path.type != DEVICE_PATH_DOMAIN) + continue; + + post_log_path(child); + + /* Pass 1 - Gather requirements. */ + printk(BIOS_INFO, "Resource allocator: %s - Pass 1 (gathering requirements)\n", + dev_path(child)); + compute_domain_resources(child); + + /* Pass 2 - Allocate resources as per gathered requirements. */ + printk(BIOS_INFO, "Resource allocator: %s - Pass 2 (allocating resources)\n", + dev_path(child)); + allocate_domain_resources(child); + } +}
build bot (Jenkins) has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41443 )
Change subject: device: Add support for resource allocator v4 ......................................................................
Patch Set 1:
(1 comment)
https://review.coreboot.org/c/coreboot/+/41443/1/src/device/resource_allocat... File src/device/resource_allocator_v4.c:
https://review.coreboot.org/c/coreboot/+/41443/1/src/device/resource_allocat... PS1, Line 215: unsigned align = get_alignment_by_resource_type(res); Prefer 'unsigned int' to bare use of 'unsigned'
Hello Patrick Georgi, Martin Roth, Aaron Durbin,
I'd like you to reexamine a change. Please visit
https://review.coreboot.org/c/coreboot/+/41443
to look at the new patch set (#2).
Change subject: device: Add support for resource allocator v4 ......................................................................
device: Add support for resource allocator v4
This change adds back support for the resource allocator using multiple ranges as originally landed in CB:39486 and reverted in CB:41413. The new resource allocator can be selected by Kconfig option RESOURCE_ALLOCATOR_V4. It was identified that there are some AMD chipsets in the tree that do not really work well with the dynamic resource allocation. Until these chipsets are fixed, old(v3) and new(v4) of the resource allocator need to live side-by-side in the tree.
This change picks up the same additions as performed in CB:39486 along with the following changes: 1. Changes are incorporated to avoid fixed resources hanging off pci domain device (CB:41363) 2. Changes to set up alignment for memranges when intializing them. This is done to ensure that the right granularity is used for IORESOURCE_IO(no special alignment) and IORESOURCE_MEM(4KiB) resource requests.
Original commit message: This change updates the resource allocator in coreboot to allow using multiple ranges for resource allocation rather than restricting available window to a single base/limit pair. This is done in preparation to allow 64-bit resource allocation.
Following changes are made as part of this: a) Resource allocator still makes 2 passes at the entire tree. The first pass is to gather the resource requirements of each device under each domain. It walks recursively in DFS fashion to gather the requirements of the leaf devices and propagates this back up to the downstream bridges of the domain. Domain is special in the sense that it has fixed resource ranges. Hence, the resource requirements from the downstream devices have no effect on the domain resource windows. This results in domain resource limits being unmodified after the first pass.
b) Once the requirements for all the devices under the domain are gathered, resource allocator walks a second time to allocate resources to downstream devices as per the requirements. Here, instead of maintaining a single window for allocating resources, it creates a list of memranges starting with the resource window at domain and then applying constraints to create holes for any fixed resources. This ensures that there is no overlap with fixed resources under the domain.
c) Domain does not differentiate between mem and prefmem. Since they are allocated space from the same resource window at the domain level, it considers all resource requests from downstream devices of the domain independent of the prefetch type.
d) Once resource allocation is done at the domain level, resource allocator walks down the downstream bridges and continues the same process until it reaches the leaves. Bridges have separate windows for mem and prefmem. Hence, unlike domain, the resource allocator at bridge level ensures that downstream requirements are satisfied by taking prefetch type into consideration.
e) This whole 2-pass process is performed for every domain in the system under the assumption that domains do not have overlapping address spaces.
Noticeable differences from previous resource allocator: a) Changes in print logs observed due to flows being slightly different. b) Base, limit and size of domain resources are no longer updated based on downstream requirements. c) Memranges are used instead of a single base/limit pair for determining resource allocation. d) Previously, if a resource request did not fit in the available base/limit window, then the resource would be allocated over DRAM or any other address space defeating the principle of "no overlap". With this change, any time a resource cannot fit in the available ranges, it complains and ensures that the resource is effectively disabled by setting base same as the limit. e) Resource allocator no longer looks at multiple links to determine the right bus for a resource. None of the current boards have multiple buses under any downstream device of the domain. The only device with multiple links seems to be the cpu cluster device for some AMD platforms.
Change-Id: Ide4d98528197bb03850a8fb4d73c41cd2c0195aa Signed-off-by: Furquan Shaikh furquan@google.com --- M src/device/Kconfig M src/device/Makefile.inc A src/device/resource_allocator_v4.c 3 files changed, 570 insertions(+), 0 deletions(-)
git pull ssh://review.coreboot.org:29418/coreboot refs/changes/43/41443/2
Furquan Shaikh has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41443 )
Change subject: device: Add support for resource allocator v4 ......................................................................
Patch Set 2:
(1 comment)
https://review.coreboot.org/c/coreboot/+/41443/1/src/device/resource_allocat... File src/device/resource_allocator_v4.c:
https://review.coreboot.org/c/coreboot/+/41443/1/src/device/resource_allocat... PS1, Line 215: unsigned align = get_alignment_by_resource_type(res);
Prefer 'unsigned int' to bare use of 'unsigned'
Done
HAOUAS Elyes has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41443 )
Change subject: device: Add support for resource allocator v4 ......................................................................
Patch Set 2:
FreeBSD & debian boots
Paul Menzel has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41443 )
Change subject: device: Add support for resource allocator v4 ......................................................................
Patch Set 3:
(5 comments)
https://review.coreboot.org/c/coreboot/+/41443/3//COMMIT_MSG Commit Message:
https://review.coreboot.org/c/coreboot/+/41443/3//COMMIT_MSG@10 PS3, Line 10: CB:39486 I’d prefer (at least addition) of commit hashes, so the git commands can easily be used.
https://review.coreboot.org/c/coreboot/+/41443/3//COMMIT_MSG@12 PS3, Line 12: are some AMD : chipsets in the tree that do not really work well with the dynamic : resource allocation Mention that other devices also had problems but were fixed in the mean-time?
https://review.coreboot.org/c/coreboot/+/41443/3//COMMIT_MSG@14 PS3, Line 14: old(v3) Please add a space.
https://review.coreboot.org/c/coreboot/+/41443/3//COMMIT_MSG@15 PS3, Line 15: new(v4) of the resource allocator need to live side-by-side in the Ditto.
https://review.coreboot.org/c/coreboot/+/41443/3//COMMIT_MSG@22 PS3, Line 22: intializing initializing
Angel Pons has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41443 )
Change subject: device: Add support for resource allocator v4 ......................................................................
Patch Set 3: Code-Review+1
(1 comment)
https://review.coreboot.org/c/coreboot/+/41443/3//COMMIT_MSG Commit Message:
https://review.coreboot.org/c/coreboot/+/41443/3//COMMIT_MSG@22 PS3, Line 22: intializing
initializing
note: problem is a missing `i` between the 2nd and 3rd character
Mike Banon has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41443 )
Change subject: device: Add support for resource allocator v4 ......................................................................
Patch Set 3: Code-Review+1
after a few typos fix (see above), this could become a +2
Hello build bot (Jenkins), Patrick Georgi, Martin Roth, Angel Pons, Mike Banon, Aaron Durbin,
I'd like you to reexamine a change. Please visit
https://review.coreboot.org/c/coreboot/+/41443
to look at the new patch set (#4).
Change subject: device: Add support for resource allocator v4 ......................................................................
device: Add support for resource allocator v4
This change adds back support for the resource allocator using multiple ranges as originally landed in CB:39486(commit hash 3b02006) and reverted in CB:41413(commit hash 6186cbc). The new resource allocator can be selected by Kconfig option RESOURCE_ALLOCATOR_V4. It was identified that there are some AMD chipsets in the tree that do not really work well with the dynamic resource allocation. Until these chipsets are fixed, old (v3) and new (v4) of the resource allocator need to live side-by-side in the tree. There were some other chipsets in the tree which originally demonstrated problems with the new resource allocator, but have been since fixed in the tree.
This change picks up the same additions as performed in CB:39486 along with the following changes: 1. Changes to avoid fixed resources in the entire tree. Use of search_bus_resources() is replaced with a walk of the entire tree in avoid_fixed_resources(). This is required to ensure that all fixed resources added to any device (including domain) are taken into consideration to avoid overlap during dynamic resource allocation. 2. Changes to set up alignment for memranges when initializing them. This is done to ensure that the right granularity is used for IORESOURCE_IO(no special alignment) and IORESOURCE_MEM(4KiB) resource requests.
Original commit message: This change updates the resource allocator in coreboot to allow using multiple ranges for resource allocation rather than restricting available window to a single base/limit pair. This is done in preparation to allow 64-bit resource allocation.
Following changes are made as part of this: a) Resource allocator still makes 2 passes at the entire tree. The first pass is to gather the resource requirements of each device under each domain. It walks recursively in DFS fashion to gather the requirements of the leaf devices and propagates this back up to the downstream bridges of the domain. Domain is special in the sense that it has fixed resource ranges. Hence, the resource requirements from the downstream devices have no effect on the domain resource windows. This results in domain resource limits being unmodified after the first pass.
b) Once the requirements for all the devices under the domain are gathered, resource allocator walks a second time to allocate resources to downstream devices as per the requirements. Here, instead of maintaining a single window for allocating resources, it creates a list of memranges starting with the resource window at domain and then applying constraints to create holes for any fixed resources. This ensures that there is no overlap with fixed resources under the domain.
c) Domain does not differentiate between mem and prefmem. Since they are allocated space from the same resource window at the domain level, it considers all resource requests from downstream devices of the domain independent of the prefetch type.
d) Once resource allocation is done at the domain level, resource allocator walks down the downstream bridges and continues the same process until it reaches the leaves. Bridges have separate windows for mem and prefmem. Hence, unlike domain, the resource allocator at bridge level ensures that downstream requirements are satisfied by taking prefetch type into consideration.
e) This whole 2-pass process is performed for every domain in the system under the assumption that domains do not have overlapping address spaces.
Noticeable differences from previous resource allocator: a) Changes in print logs observed due to flows being slightly different. b) Base, limit and size of domain resources are no longer updated based on downstream requirements. c) Memranges are used instead of a single base/limit pair for determining resource allocation. d) Previously, if a resource request did not fit in the available base/limit window, then the resource would be allocated over DRAM or any other address space defeating the principle of "no overlap". With this change, any time a resource cannot fit in the available ranges, it complains and ensures that the resource is effectively disabled by setting base same as the limit. e) Resource allocator no longer looks at multiple links to determine the right bus for a resource. None of the current boards have multiple buses under any downstream device of the domain. The only device with multiple links seems to be the cpu cluster device for some AMD platforms.
Change-Id: Ide4d98528197bb03850a8fb4d73c41cd2c0195aa Signed-off-by: Furquan Shaikh furquan@google.com --- M src/device/Kconfig M src/device/Makefile.inc A src/device/resource_allocator_v4.c 3 files changed, 570 insertions(+), 0 deletions(-)
git pull ssh://review.coreboot.org:29418/coreboot refs/changes/43/41443/4
Furquan Shaikh has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41443 )
Change subject: device: Add support for resource allocator v4 ......................................................................
Patch Set 4:
(5 comments)
https://review.coreboot.org/c/coreboot/+/41443/3//COMMIT_MSG Commit Message:
https://review.coreboot.org/c/coreboot/+/41443/3//COMMIT_MSG@10 PS3, Line 10: CB:39486
I’d prefer (at least addition) of commit hashes, so the git commands can easily be used.
Done
https://review.coreboot.org/c/coreboot/+/41443/3//COMMIT_MSG@12 PS3, Line 12: are some AMD : chipsets in the tree that do not really work well with the dynamic : resource allocation
Mention that other devices also had problems but were fixed in the mean-time?
Done
https://review.coreboot.org/c/coreboot/+/41443/3//COMMIT_MSG@14 PS3, Line 14: old(v3)
Please add a space.
Done
https://review.coreboot.org/c/coreboot/+/41443/3//COMMIT_MSG@15 PS3, Line 15: new(v4) of the resource allocator need to live side-by-side in the
Ditto.
Done
https://review.coreboot.org/c/coreboot/+/41443/3//COMMIT_MSG@22 PS3, Line 22: intializing
note: problem is a missing `i` between the 2nd and 3rd character
Done
Hello build bot (Jenkins), Patrick Georgi, Martin Roth, Angel Pons, Mike Banon, Aaron Durbin,
I'd like you to reexamine a change. Please visit
https://review.coreboot.org/c/coreboot/+/41443
to look at the new patch set (#5).
Change subject: device: Add support for resource allocator v4 ......................................................................
device: Add support for resource allocator v4
This change adds back support for the resource allocator using multiple ranges as originally landed in CB:39486(commit hash 3b02006) and reverted in CB:41413(commit hash 6186cbc). The new resource allocator can be selected by Kconfig option RESOURCE_ALLOCATOR_V4. It was identified that there are some AMD chipsets in the tree that do not really work well with the dynamic resource allocation. Until these chipsets are fixed, old (v3) and new (v4) of the resource allocator need to live side-by-side in the tree. There were some other chipsets in the tree which originally demonstrated problems with the new resource allocator, but have been since fixed in the tree.
This change picks up the same additions as performed in CB:39486 along with the following changes: 1. Changes to avoid fixed resources in the entire tree. Use of search_bus_resources() is replaced with a walk of the entire tree in avoid_fixed_resources(). This is required to ensure that all fixed resources added to any device (including domain) are taken into consideration to avoid overlap during dynamic resource allocation. 2. Changes to set up alignment for memranges when initializing them. This is done to ensure that the right granularity is used for IORESOURCE_IO(no special alignment) and IORESOURCE_MEM(4KiB) resource requests.
Original commit message: This change updates the resource allocator in coreboot to allow using multiple ranges for resource allocation rather than restricting available window to a single base/limit pair. This is done in preparation to allow 64-bit resource allocation.
Following changes are made as part of this: a) Resource allocator still makes 2 passes at the entire tree. The first pass is to gather the resource requirements of each device under each domain. It walks recursively in DFS fashion to gather the requirements of the leaf devices and propagates this back up to the downstream bridges of the domain. Domain is special in the sense that it has fixed resource ranges. Hence, the resource requirements from the downstream devices have no effect on the domain resource windows. This results in domain resource limits being unmodified after the first pass.
b) Once the requirements for all the devices under the domain are gathered, resource allocator walks a second time to allocate resources to downstream devices as per the requirements. Here, instead of maintaining a single window for allocating resources, it creates a list of memranges starting with the resource window at domain and then applying constraints to create holes for any fixed resources. This ensures that there is no overlap with fixed resources under the domain.
c) Domain does not differentiate between mem and prefmem. Since they are allocated space from the same resource window at the domain level, it considers all resource requests from downstream devices of the domain independent of the prefetch type.
d) Once resource allocation is done at the domain level, resource allocator walks down the downstream bridges and continues the same process until it reaches the leaves. Bridges have separate windows for mem and prefmem. Hence, unlike domain, the resource allocator at bridge level ensures that downstream requirements are satisfied by taking prefetch type into consideration.
e) This whole 2-pass process is performed for every domain in the system under the assumption that domains do not have overlapping address spaces.
Noticeable differences from previous resource allocator: a) Changes in print logs observed due to flows being slightly different. b) Base, limit and size of domain resources are no longer updated based on downstream requirements. c) Memranges are used instead of a single base/limit pair for determining resource allocation. d) Previously, if a resource request did not fit in the available base/limit window, then the resource would be allocated over DRAM or any other address space defeating the principle of "no overlap". With this change, any time a resource cannot fit in the available ranges, it complains and ensures that the resource is effectively disabled by setting base same as the limit. e) Resource allocator no longer looks at multiple links to determine the right bus for a resource. None of the current boards have multiple buses under any downstream device of the domain. The only device with multiple links seems to be the cpu cluster device for some AMD platforms.
Change-Id: Ide4d98528197bb03850a8fb4d73c41cd2c0195aa Signed-off-by: Furquan Shaikh furquan@google.com --- M src/device/Kconfig M src/device/Makefile.inc A src/device/resource_allocator_v4.c 3 files changed, 578 insertions(+), 0 deletions(-)
git pull ssh://review.coreboot.org:29418/coreboot refs/changes/43/41443/5
Furquan Shaikh has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41443 )
Change subject: device: Add support for resource allocator v4 ......................................................................
Patch Set 5:
(2 comments)
https://review.coreboot.org/c/coreboot/+/41443/5/src/device/resource_allocat... File src/device/resource_allocator_v4.c:
https://review.coreboot.org/c/coreboot/+/41443/5/src/device/resource_allocat... PS5, Line 217: memranges_init_empty_with_alignment For reviewers:
This has changed since the original CL was pushed. Earlier it used memranges_init_empty() which uses alignment of 12 i.e. 4KiB. But that is required only for IORESOURCE_MEM and not for IORESOURCE_IO. Hence, get_alignment_by_resource_type() returns the correct alignment to be used when initializing memranges.
https://review.coreboot.org/c/coreboot/+/41443/5/src/device/resource_allocat... PS5, Line 358: avoid_fixed_resources For reviewers:
This is different than the original CL that was pushed. Initially this function used search_bus_resources(). But, that does not really walk down the entire tree and also domain fixed resources were not being considered. Thus, avoid_fixed_resources() is added to consider fixed resources in the entire tree.
Nico Huber has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41443 )
Change subject: device: Add support for resource allocator v4 ......................................................................
Patch Set 6:
(2 comments)
https://review.coreboot.org/c/coreboot/+/41443/6/src/device/resource_allocat... File src/device/resource_allocator_v4.c:
https://review.coreboot.org/c/coreboot/+/41443/6/src/device/resource_allocat... PS6, Line 249: res->flags |= IORESOURCE_ASSIGNED; This doesn't seem like a good idea, and I don't understand the reason behind it. Any `.set_resources` would have to check if `base + size - 1 <= limit` before it writes "assigned" resources. IMHO, we should only set IORESOURCE_ASSIGNED if the resource is valid.
https://review.coreboot.org/c/coreboot/+/41443/6/src/device/resource_allocat... PS6, Line 261: find_pci_tolm() Why start a new allocator with a quirk? It seems easy to ignore unassigned resources in find_pci_tolm().
Nico Huber has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41443 )
Change subject: device: Add support for resource allocator v4 ......................................................................
Patch Set 6:
(1 comment)
https://review.coreboot.org/c/coreboot/+/41443/6/src/device/resource_allocat... File src/device/resource_allocator_v4.c:
https://review.coreboot.org/c/coreboot/+/41443/6/src/device/resource_allocat... PS6, Line 225: if (res_base == res_limit) I'm not sure anymore, if this is a valid test. Are we certain that there is never a resource of size 1?
Nico Huber has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41443 )
Change subject: device: Add support for resource allocator v4 ......................................................................
Patch Set 6:
(1 comment)
https://review.coreboot.org/c/coreboot/+/41443/6/src/device/resource_allocat... File src/device/resource_allocator_v4.c:
https://review.coreboot.org/c/coreboot/+/41443/6/src/device/resource_allocat... PS6, Line 225: if (res_base == res_limit)
I'm not sure anymore, if this is a valid test. Are we certain that […]
If we wouldn't spuriously set IORESOURCE_ASSIGNED, we could check for that, I guess.
Furquan Shaikh has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41443 )
Change subject: device: Add support for resource allocator v4 ......................................................................
Patch Set 6:
(3 comments)
https://review.coreboot.org/c/coreboot/+/41443/6/src/device/resource_allocat... File src/device/resource_allocator_v4.c:
https://review.coreboot.org/c/coreboot/+/41443/6/src/device/resource_allocat... PS6, Line 225: if (res_base == res_limit)
If we wouldn't spuriously set IORESOURCE_ASSIGNED, we could […]
Sure. I have uploaded the changes. Once those go through, I can update this.
https://review.coreboot.org/c/coreboot/+/41443/6/src/device/resource_allocat... PS6, Line 249: res->flags |= IORESOURCE_ASSIGNED;
This doesn't seem like a good idea, and I don't understand the […]
Makes sense. I went through the set_resources() calls and I see that most check IORESOURCE_ASSIGNED to decide if they should skip the assignment if IORESOURCE_ASSIGNED is not set, which makes sense. I see that pci_set_resource() was printing an error if IORESOURCE_ASSIGNED is not set. So, I added a check there: https://review.coreboot.org/c/coreboot/+/41523
https://review.coreboot.org/c/coreboot/+/41443/6/src/device/resource_allocat... PS6, Line 261: find_pci_tolm()
Why start a new allocator with a quirk? It seems easy to ignore […]
Done. Added check here: https://review.coreboot.org/c/coreboot/+/41524
Nico Huber has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41443 )
Change subject: device: Add support for resource allocator v4 ......................................................................
Patch Set 6:
(1 comment)
pci_set_resource() sets some nasty constraints here. Not sure if we should adapt it first or handle its quirks here. On one hand, we have to always mark bridge resources to be assigned. Otherwise the bridge window won't be written (and the PCI spec explicitly mentions that we have to because there is no sane default). On the other hand, if we mark a regular resource as assigned, there are no further checks if it fits (e.g. `base + size - 1 <= limit` can be violated). So we mustn't mark non- bridge resources as assigned if allocation failed.
IMHO, the best solution would be to patch pci_set_resource() to always process bridge resources if their size is 0. If it is not 0, or it's a non-bridge resource, check the assigned status. iow.
if ((!(resource->flags & IORESOURCE_BRIDGE) || resource->size > 0) && !(resource->flags & IORESOURCE_ASSIGNED)) { complain; return; }
https://review.coreboot.org/c/coreboot/+/41443/6/src/device/resource_allocat... File src/device/resource_allocator_v4.c:
https://review.coreboot.org/c/coreboot/+/41443/6/src/device/resource_allocat... PS6, Line 272: mark_resource_invalid(resource); pci_set_resource() is odd. The old allocator set IORESOURCE_ASSIGNED on purpose on this path. We can either set it here or patch pci_set_resource() to ignore the assigned status if the resource size is 0.
Both seems logically sound to me. If the size is 0, other properties (base, limit, assigned, ...) have no real meaning. (I wouldn't call it invalid, though.)
Nico Huber has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41443 )
Change subject: device: Add support for resource allocator v4 ......................................................................
Patch Set 6:
IMHO, the best solution would be to patch pci_set_resource() to always process bridge resources if their size is 0. If it is not 0, or it's a non-bridge resource, check the assigned status. iow.
if ((!(resource->flags & IORESOURCE_BRIDGE) || resource->size > 0) && !(resource->flags & IORESOURCE_ASSIGNED)) { complain; return; }
Probably even better would be to always treat unassigned bridge resources as if their size was 0. This would leave only a single assumption about the allocator: If a resource is marked as assigned, it is properly allocated.
Furquan Shaikh has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41443 )
Change subject: device: Add support for resource allocator v4 ......................................................................
Patch Set 6:
(2 comments)
https://review.coreboot.org/c/coreboot/+/41443/6/src/device/resource_allocat... File src/device/resource_allocator_v4.c:
https://review.coreboot.org/c/coreboot/+/41443/6/src/device/resource_allocat... PS6, Line 249: res->flags |= IORESOURCE_ASSIGNED;
Makes sense. […]
As commented below, I think we should still set IORESOURCE_ASSIGNED. It means that the resource allocator has actually assigned a value to its base -- either the value which corresponds to address space allocated to it or limit if the resource needs to be disabled.
https://review.coreboot.org/c/coreboot/+/41443/6/src/device/resource_allocat... PS6, Line 272: mark_resource_invalid(resource);
pci_set_resource() is odd. The old allocator set IORESOURCE_ASSIGNED on […]
Revisiting this and pci_set_resource(), this is what I am thinking:
- At the end of resource allocation, all resources that have been assigned base and limit, should have IORESOURCE_ASSIGNED flag set. - This should be true for even the resources that request a size of 0. When a resource requests size 0, resource allocator should set the base = limit to ensure that it is properly disabled. Since,the resource allocator has actually assigned base (even though it it set to disabled), IORESOURCE_ASSIGNED flag should be set.
This should just work with how pci_set_resource() is written. And it is also helpful in case we really encounter a situation where pci_set_resource() is called without IORESOURCE_ASSIGNED being set, so that it can complain and highlight the issue.
Nico Huber has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41443 )
Change subject: device: Add support for resource allocator v4 ......................................................................
Patch Set 6:
(1 comment)
https://review.coreboot.org/c/coreboot/+/41443/6/src/device/resource_allocat... File src/device/resource_allocator_v4.c:
https://review.coreboot.org/c/coreboot/+/41443/6/src/device/resource_allocat... PS6, Line 272: mark_resource_invalid(resource);
Revisiting this and pci_set_resource(), this is what I am thinking: […]
First, I don't see how `base == limit` implies or disables anything. Please explain.
Second, what you say is true for bridge resources, and I already agreed to set IORESOURCE_ASSIGNED in this case (even though, I don't like it). But please tell me how pci_set_resource() does the right thing for a non- bridge resource. I just don't see it.
Furquan Shaikh has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41443 )
Change subject: device: Add support for resource allocator v4 ......................................................................
Patch Set 6:
(1 comment)
https://review.coreboot.org/c/coreboot/+/41443/6/src/device/resource_allocat... File src/device/resource_allocator_v4.c:
https://review.coreboot.org/c/coreboot/+/41443/6/src/device/resource_allocat... PS6, Line 272: mark_resource_invalid(resource);
First, I don't see how `base == limit` implies or disables anything. Please explain.
I think what you are looking for is limit < base so that it is disabled as per the PCI Specification?
But please tell me how pci_set_resource() does the right thing for a non-
bridge resource. I just don't see it.
What is the definition of right thing for a non-bridge resource to be disabled? Again as per PCI specification, there are separate enable control bits that decide when to enable the decoding for I/O and mem for non-bridge resource. So, how do you really define that a resource is disabled?
My argument here is that we are bringing in the semantics of PCI devices into the resource allocator. I understand that we are dealing only with PCI devices right now, but both the old and new resource allocators are written without really making assumptions about the kind of devices that are requesting these resources. In that case, we need to come up with a notion of saying how you mark a device as invalid/disabled.
* Setting IORESOURCE_ASSIGNED indicates that the resource for the device has been considered by the resource allocator and assigned some base value.
* Setting base = limit indicates that the resource could not really be allocated any space. If you are concerned about resources requesting a size of 1,we can set base = limit and limit = base - 1 and set size = 0. I think we need to set the semantics of how resource allocator indicates to rest of the drivers that a resource is disabled.
Now, how pci_set_resource() uses it is upto that driver. For a bridge resource, it can set base and limit as per the specification. For a non-bridge resource, it can check size as 0 and decide for itself that IO and mem decoding should not be enabled. But, that shouldn't be done as part of the allocator.
Nico Huber has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41443 )
Change subject: device: Add support for resource allocator v4 ......................................................................
Patch Set 6:
(1 comment)
https://review.coreboot.org/c/coreboot/+/41443/6/src/device/resource_allocat... File src/device/resource_allocator_v4.c:
https://review.coreboot.org/c/coreboot/+/41443/6/src/device/resource_allocat... PS6, Line 272: mark_resource_invalid(resource);
First, I don't see how `base == limit` implies or disables anything. Please explain.
I think what you are looking for is limit < base so that it is disabled as per the PCI Specification?
No, I'm looking for anything. It seems to me that you just made that rule up. If not, please tell me where I'm wrong.
But please tell me how pci_set_resource() does the right thing for a non-
bridge resource. I just don't see it.
What is the definition of right thing for a non-bridge resource to be disabled? Again as per PCI specification, there are separate enable control bits that decide when to enable the decoding for I/O and mem for non-bridge resource. So, how do you really define that a resource is disabled?
For PCI it's when the command bit is not set. For coreboot, I only see a single option: don't set IORESOURCE_ASSIGNED as we always did.
My argument here is that we are bringing in the semantics of PCI devices into the resource allocator.
That's exactly what I want to prevent and why I suggest to adapt the PCI code instead of adding quirks to the allocator.
I understand that we are dealing only with PCI devices right now, but both the old and new resource allocators are written without really making assumptions about the kind of devices that are requesting these resources. In that case, we need to come up with a notion of saying how you mark a device as invalid/disabled.
We already have that. The old allocator didn't set IORESOURCE_ASSIGNED on the error path (ok, that path failed to execute but the idea was there and sound, IMHO).
If you think that needs to be changed, ok. But it's exactly this kind of change that is harder with two allocators in the tree...
Furquan Shaikh has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41443 )
Change subject: device: Add support for resource allocator v4 ......................................................................
Patch Set 6:
(1 comment)
https://review.coreboot.org/c/coreboot/+/41443/6/src/device/resource_allocat... File src/device/resource_allocator_v4.c:
https://review.coreboot.org/c/coreboot/+/41443/6/src/device/resource_allocat... PS6, Line 272: mark_resource_invalid(resource);
First, I don't see how `base == limit` implies or disables anything. Please explain. […]
Okay. I think I understand what you are saying. Let's continue discussion on the PCI driver CLs you have pushed. I think it makes sense to use the semantics:
IORESOURCE_ASSIGNED: Resource is allocated space by the allocator. If allocation fails, IORESOURCE_ASSIGNED will not be set and all resource attributes(base, limit, size) will be left untouched.
Hello build bot (Jenkins), Patrick Georgi, Martin Roth, Angel Pons, Mike Banon, Aaron Durbin,
I'd like you to reexamine a change. Please visit
https://review.coreboot.org/c/coreboot/+/41443
to look at the new patch set (#7).
Change subject: device: Add support for resource allocator v4 ......................................................................
device: Add support for resource allocator v4
This change adds back support for the resource allocator using multiple ranges as originally landed in CB:39486(commit hash 3b02006) and reverted in CB:41413(commit hash 6186cbc). The new resource allocator can be selected by Kconfig option RESOURCE_ALLOCATOR_V4. It was identified that there are some AMD chipsets in the tree that do not really work well with the dynamic resource allocation. Until these chipsets are fixed, old (v3) and new (v4) of the resource allocator need to live side-by-side in the tree. There were some other chipsets in the tree which originally demonstrated problems with the new resource allocator, but have been since fixed in the tree.
This change picks up the same additions as performed in CB:39486 along with the following changes: 1. Changes to avoid fixed resources in the entire tree. Use of search_bus_resources() is replaced with a walk of the entire tree in avoid_fixed_resources(). This is required to ensure that all fixed resources added to any device (including domain) are taken into consideration to avoid overlap during dynamic resource allocation. 2. Changes to set up alignment for memranges when initializing them. This is done to ensure that the right granularity is used for IORESOURCE_IO(no special alignment) and IORESOURCE_MEM(4KiB) resource requests. 3. mark_resource_invalid() is dropped as the resource no longer needs to be marked in any special way if allocation is not being done. Instead setting of IORESOURCE_ASSIGNED flag is skipped in this case. 4. initialize_memranges() is updated to check IORESOURCE_ASSIGNED instead of base == limit.
Original commit message: This change updates the resource allocator in coreboot to allow using multiple ranges for resource allocation rather than restricting available window to a single base/limit pair. This is done in preparation to allow 64-bit resource allocation.
Following changes are made as part of this: a) Resource allocator still makes 2 passes at the entire tree. The first pass is to gather the resource requirements of each device under each domain. It walks recursively in DFS fashion to gather the requirements of the leaf devices and propagates this back up to the downstream bridges of the domain. Domain is special in the sense that it has fixed resource ranges. Hence, the resource requirements from the downstream devices have no effect on the domain resource windows. This results in domain resource limits being unmodified after the first pass.
b) Once the requirements for all the devices under the domain are gathered, resource allocator walks a second time to allocate resources to downstream devices as per the requirements. Here, instead of maintaining a single window for allocating resources, it creates a list of memranges starting with the resource window at domain and then applying constraints to create holes for any fixed resources. This ensures that there is no overlap with fixed resources under the domain.
c) Domain does not differentiate between mem and prefmem. Since they are allocated space from the same resource window at the domain level, it considers all resource requests from downstream devices of the domain independent of the prefetch type.
d) Once resource allocation is done at the domain level, resource allocator walks down the downstream bridges and continues the same process until it reaches the leaves. Bridges have separate windows for mem and prefmem. Hence, unlike domain, the resource allocator at bridge level ensures that downstream requirements are satisfied by taking prefetch type into consideration.
e) This whole 2-pass process is performed for every domain in the system under the assumption that domains do not have overlapping address spaces.
Noticeable differences from previous resource allocator: a) Changes in print logs observed due to flows being slightly different. b) Base, limit and size of domain resources are no longer updated based on downstream requirements. c) Memranges are used instead of a single base/limit pair for determining resource allocation. d) Previously, if a resource request did not fit in the available base/limit window, then the resource would be allocated over DRAM or any other address space defeating the principle of "no overlap". With this change, any time a resource cannot fit in the available ranges, it complains and ensures that the resource is effectively disabled by setting base same as the limit. e) Resource allocator no longer looks at multiple links to determine the right bus for a resource. None of the current boards have multiple buses under any downstream device of the domain. The only device with multiple links seems to be the cpu cluster device for some AMD platforms.
Change-Id: Ide4d98528197bb03850a8fb4d73c41cd2c0195aa Signed-off-by: Furquan Shaikh furquan@google.com --- M src/device/Kconfig M src/device/Makefile.inc A src/device/resource_allocator_v4.c 3 files changed, 562 insertions(+), 0 deletions(-)
git pull ssh://review.coreboot.org:29418/coreboot refs/changes/43/41443/7
Furquan Shaikh has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41443 )
Change subject: device: Add support for resource allocator v4 ......................................................................
Patch Set 7:
(4 comments)
https://review.coreboot.org/c/coreboot/+/41443/6/src/device/resource_allocat... File src/device/resource_allocator_v4.c:
https://review.coreboot.org/c/coreboot/+/41443/6/src/device/resource_allocat... PS6, Line 225: if (res_base == res_limit)
Sure. I have uploaded the changes. Once those go through, I can update this.
Done
https://review.coreboot.org/c/coreboot/+/41443/6/src/device/resource_allocat... PS6, Line 249: res->flags |= IORESOURCE_ASSIGNED;
As commented below, I think we should still set IORESOURCE_ASSIGNED. […]
Done
https://review.coreboot.org/c/coreboot/+/41443/6/src/device/resource_allocat... PS6, Line 261: find_pci_tolm()
Done. Added check here: https://review.coreboot. […]
Done
https://review.coreboot.org/c/coreboot/+/41443/6/src/device/resource_allocat... PS6, Line 272: mark_resource_invalid(resource);
Okay. I think I understand what you are saying. […]
Dropped mark_resource_invalid().
Nico Huber has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41443 )
Change subject: device: Add support for resource allocator v4 ......................................................................
Patch Set 7: Code-Review+1
(1 comment)
Looks good to me, I'll try to read through everything again after some sleep :)
https://review.coreboot.org/c/coreboot/+/41443/6/src/device/resource_allocat... File src/device/resource_allocator_v4.c:
https://review.coreboot.org/c/coreboot/+/41443/6/src/device/resource_allocat... PS6, Line 272: mark_resource_invalid(resource);
IORESOURCE_ASSIGNED: Resource is allocated space by the allocator. If allocation fails, IORESOURCE_ASSIGNED will not be set and all resource attributes(base, limit, size) will be left untouched.
That's a bit too tight, IMHO. For instance the old allocator changed `base` already in the first pass (and I think this could actually be useful, e.g. to optimize the second largest-resource run away). Let's just say, if IORESOURCE_ASSIGNED is set, `base` is valid? And not make assumptions when it's unset.
Furquan Shaikh has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41443 )
Change subject: device: Add support for resource allocator v4 ......................................................................
Patch Set 7:
(1 comment)
https://review.coreboot.org/c/coreboot/+/41443/6/src/device/resource_allocat... File src/device/resource_allocator_v4.c:
https://review.coreboot.org/c/coreboot/+/41443/6/src/device/resource_allocat... PS6, Line 272: mark_resource_invalid(resource);
Let's just say, if IORESOURCE_ASSIGNED is set, `base` is valid? And not make assumptions when it's unset.
SGTM.
Nico Huber has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41443 )
Change subject: device: Add support for resource allocator v4 ......................................................................
Patch Set 9: Code-Review+2
Patrick Georgi has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41443 )
Change subject: device: Add support for resource allocator v4 ......................................................................
Patch Set 9:
(2 comments)
https://review.coreboot.org/c/coreboot/+/41443/5/src/device/resource_allocat... File src/device/resource_allocator_v4.c:
https://review.coreboot.org/c/coreboot/+/41443/5/src/device/resource_allocat... PS5, Line 217: memranges_init_empty_with_alignment
For reviewers: […]
Ack
https://review.coreboot.org/c/coreboot/+/41443/5/src/device/resource_allocat... PS5, Line 358: avoid_fixed_resources
For reviewers: […]
Ack
Patrick Georgi has submitted this change. ( https://review.coreboot.org/c/coreboot/+/41443 )
Change subject: device: Add support for resource allocator v4 ......................................................................
device: Add support for resource allocator v4
This change adds back support for the resource allocator using multiple ranges as originally landed in CB:39486(commit hash 3b02006) and reverted in CB:41413(commit hash 6186cbc). The new resource allocator can be selected by Kconfig option RESOURCE_ALLOCATOR_V4. It was identified that there are some AMD chipsets in the tree that do not really work well with the dynamic resource allocation. Until these chipsets are fixed, old (v3) and new (v4) of the resource allocator need to live side-by-side in the tree. There were some other chipsets in the tree which originally demonstrated problems with the new resource allocator, but have been since fixed in the tree.
This change picks up the same additions as performed in CB:39486 along with the following changes: 1. Changes to avoid fixed resources in the entire tree. Use of search_bus_resources() is replaced with a walk of the entire tree in avoid_fixed_resources(). This is required to ensure that all fixed resources added to any device (including domain) are taken into consideration to avoid overlap during dynamic resource allocation. 2. Changes to set up alignment for memranges when initializing them. This is done to ensure that the right granularity is used for IORESOURCE_IO(no special alignment) and IORESOURCE_MEM(4KiB) resource requests. 3. mark_resource_invalid() is dropped as the resource no longer needs to be marked in any special way if allocation is not being done. Instead setting of IORESOURCE_ASSIGNED flag is skipped in this case. 4. initialize_memranges() is updated to check IORESOURCE_ASSIGNED instead of base == limit.
Original commit message: This change updates the resource allocator in coreboot to allow using multiple ranges for resource allocation rather than restricting available window to a single base/limit pair. This is done in preparation to allow 64-bit resource allocation.
Following changes are made as part of this: a) Resource allocator still makes 2 passes at the entire tree. The first pass is to gather the resource requirements of each device under each domain. It walks recursively in DFS fashion to gather the requirements of the leaf devices and propagates this back up to the downstream bridges of the domain. Domain is special in the sense that it has fixed resource ranges. Hence, the resource requirements from the downstream devices have no effect on the domain resource windows. This results in domain resource limits being unmodified after the first pass.
b) Once the requirements for all the devices under the domain are gathered, resource allocator walks a second time to allocate resources to downstream devices as per the requirements. Here, instead of maintaining a single window for allocating resources, it creates a list of memranges starting with the resource window at domain and then applying constraints to create holes for any fixed resources. This ensures that there is no overlap with fixed resources under the domain.
c) Domain does not differentiate between mem and prefmem. Since they are allocated space from the same resource window at the domain level, it considers all resource requests from downstream devices of the domain independent of the prefetch type.
d) Once resource allocation is done at the domain level, resource allocator walks down the downstream bridges and continues the same process until it reaches the leaves. Bridges have separate windows for mem and prefmem. Hence, unlike domain, the resource allocator at bridge level ensures that downstream requirements are satisfied by taking prefetch type into consideration.
e) This whole 2-pass process is performed for every domain in the system under the assumption that domains do not have overlapping address spaces.
Noticeable differences from previous resource allocator: a) Changes in print logs observed due to flows being slightly different. b) Base, limit and size of domain resources are no longer updated based on downstream requirements. c) Memranges are used instead of a single base/limit pair for determining resource allocation. d) Previously, if a resource request did not fit in the available base/limit window, then the resource would be allocated over DRAM or any other address space defeating the principle of "no overlap". With this change, any time a resource cannot fit in the available ranges, it complains and ensures that the resource is effectively disabled by setting base same as the limit. e) Resource allocator no longer looks at multiple links to determine the right bus for a resource. None of the current boards have multiple buses under any downstream device of the domain. The only device with multiple links seems to be the cpu cluster device for some AMD platforms.
Change-Id: Ide4d98528197bb03850a8fb4d73c41cd2c0195aa Signed-off-by: Furquan Shaikh furquan@google.com Reviewed-on: https://review.coreboot.org/c/coreboot/+/41443 Reviewed-by: Nico Huber nico.h@gmx.de Tested-by: build bot (Jenkins) no-reply@coreboot.org --- M src/device/Kconfig M src/device/Makefile.inc A src/device/resource_allocator_v4.c 3 files changed, 562 insertions(+), 0 deletions(-)
Approvals: build bot (Jenkins): Verified Nico Huber: Looks good to me, approved
diff --git a/src/device/Kconfig b/src/device/Kconfig index a60965a..801b040 100644 --- a/src/device/Kconfig +++ b/src/device/Kconfig @@ -784,4 +784,13 @@ This config option enables resource allocator v3 which performs top down allocation of resources in a single MMIO window.
+config RESOURCE_ALLOCATOR_V4 + bool + default n if RESOURCE_ALLOCATOR_V3 + default y if !RESOURCE_ALLOCATOR_V3 + help + This config option enables resource allocator v4 which uses multiple + ranges for allocating resources. This allows allocation of resources + above 4G boundary as well. + endmenu diff --git a/src/device/Makefile.inc b/src/device/Makefile.inc index 9bbab37..2e62d42 100644 --- a/src/device/Makefile.inc +++ b/src/device/Makefile.inc @@ -61,3 +61,4 @@
ramstage-y += resource_allocator_common.c ramstage-$(CONFIG_RESOURCE_ALLOCATOR_V3) += resource_allocator_v3.c +ramstage-$(CONFIG_RESOURCE_ALLOCATOR_V4) += resource_allocator_v4.c diff --git a/src/device/resource_allocator_v4.c b/src/device/resource_allocator_v4.c new file mode 100644 index 0000000..ece7150 --- /dev/null +++ b/src/device/resource_allocator_v4.c @@ -0,0 +1,552 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ + +#include <console/console.h> +#include <device/device.h> +#include <memrange.h> +#include <post.h> + +/** + * Round a number up to an alignment. + * + * @param val The starting value. + * @param pow Alignment as a power of two. + * @return Rounded up number. + */ +static resource_t round(resource_t val, unsigned long pow) +{ + return ALIGN_UP(val, POWER_OF_2(pow)); +} + +static const char *resource2str(const struct resource *res) +{ + if (res->flags & IORESOURCE_IO) + return "io"; + if (res->flags & IORESOURCE_PREFETCH) + return "prefmem"; + if (res->flags & IORESOURCE_MEM) + return "mem"; + return "undefined"; +} + +static bool dev_has_children(const struct device *dev) +{ + const struct bus *bus = dev->link_list; + return bus && bus->children; +} + +/* + * During pass 1, once all the requirements for downstream devices of a bridge are gathered, + * this function calculates the overall resource requirement for the bridge. It starts by + * picking the largest resource requirement downstream for the given resource type and works by + * adding requirements in descending order. + * + * Additionally, it takes alignment and limits of the downstream devices into consideration and + * ensures that they get propagated to the bridge resource. This is required to guarantee that + * the upstream bridge/domain honors the limit and alignment requirements for this bridge based + * on the tightest constraints downstream. + */ +static void update_bridge_resource(const struct device *bridge, struct resource *bridge_res, + unsigned long type_match) +{ + const struct device *child; + struct resource *child_res; + resource_t base; + bool first_child_res = true; + const unsigned long type_mask = IORESOURCE_TYPE_MASK | IORESOURCE_PREFETCH; + struct bus *bus = bridge->link_list; + + child_res = NULL; + + /* + * `base` keeps track of where the next allocation for child resource can take place + * from within the bridge resource window. Since the bridge resource window allocation + * is not performed yet, it can start at 0. Base gets updated every time a resource + * requirement is accounted for in the loop below. After scanning all these resources, + * base will indicate the total size requirement for the current bridge resource + * window. + */ + base = 0; + + printk(BIOS_SPEW, "%s %s: size: %llx align: %d gran: %d limit: %llx\n", + dev_path(bridge), resource2str(bridge_res), bridge_res->size, + bridge_res->align, bridge_res->gran, bridge_res->limit); + + while ((child = largest_resource(bus, &child_res, type_mask, type_match))) { + + /* Size 0 resources can be skipped. */ + if (!child_res->size) + continue; + + /* + * Propagate the resource alignment to the bridge resource if this is the first + * child resource with non-zero size being considered. For all other children + * resources, alignment is taken care of by updating the base to round up as per + * the child resource alignment. It is guaranteed that pass 2 follows the exact + * same method of picking the resource for allocation using + * largest_resource(). Thus, as long as the alignment for first child resource + * is propagated up to the bridge resource, it can be guaranteed that the + * alignment for all resources is appropriately met. + */ + if (first_child_res && (child_res->align > bridge_res->align)) + bridge_res->align = child_res->align; + + first_child_res = false; + + /* + * Propagate the resource limit to the bridge resource only if child resource + * limit is non-zero. If a downstream device has stricter requirements + * w.r.t. limits for any resource, that constraint needs to be propagated back + * up to the downstream bridges of the domain. This guarantees that the resource + * allocation which starts at the domain level takes into account all these + * constraints thus working on a global view. + */ + if (child_res->limit && (child_res->limit < bridge_res->limit)) + bridge_res->limit = child_res->limit; + + /* + * Alignment value of 0 means that the child resource has no alignment + * requirements and so the base value remains unchanged here. + */ + base = round(base, child_res->align); + + printk(BIOS_SPEW, "%s %02lx * [0x%llx - 0x%llx] %s\n", + dev_path(child), child_res->index, base, base + child_res->size - 1, + resource2str(child_res)); + + base += child_res->size; + } + + /* + * After all downstream device resources are scanned, `base` represents the total size + * requirement for the current bridge resource window. This size needs to be rounded up + * to the granularity requirement of the bridge to ensure that the upstream + * bridge/domain allocates big enough window. + */ + bridge_res->size = round(base, bridge_res->gran); + + printk(BIOS_SPEW, "%s %s: size: %llx align: %d gran: %d limit: %llx done\n", + dev_path(bridge), resource2str(bridge_res), bridge_res->size, + bridge_res->align, bridge_res->gran, bridge_res->limit); +} + +/* + * During pass 1, resource allocator at bridge level gathers requirements from downstream + * devices and updates its own resource windows for the provided resource type. + */ +static void compute_bridge_resources(const struct device *bridge, unsigned long type_match) +{ + const struct device *child; + struct resource *res; + struct bus *bus = bridge->link_list; + const unsigned long type_mask = IORESOURCE_TYPE_MASK | IORESOURCE_PREFETCH; + + for (res = bridge->resource_list; res; res = res->next) { + if (!(res->flags & IORESOURCE_BRIDGE)) + continue; + + if ((res->flags & type_mask) != type_match) + continue; + + /* + * Ensure that the resource requirements for all downstream bridges are + * gathered before updating the window for current bridge resource. + */ + for (child = bus->children; child; child = child->sibling) { + if (!dev_has_children(child)) + continue; + compute_bridge_resources(child, type_match); + } + + /* + * Update the window for current bridge resource now that all downstream + * requirements are gathered. + */ + update_bridge_resource(bridge, res, type_match); + } +} + +/* + * During pass 1, resource allocator walks down the entire sub-tree of a domain. It gathers + * resource requirements for every downstream bridge by looking at the resource requests of its + * children. Thus, the requirement gathering begins at the leaf devices and is propagated back + * up to the downstream bridges of the domain. + * + * At domain level, it identifies every downstream bridge and walks down that bridge to gather + * requirements for each resource type i.e. i/o, mem and prefmem. Since bridges have separate + * windows for mem and prefmem, requirements for each need to be collected separately. + * + * Domain resource windows are fixed ranges and hence requirement gathering does not result in + * any changes to these fixed ranges. + */ +static void compute_domain_resources(const struct device *domain) +{ + const struct device *child; + + if (domain->link_list == NULL) + return; + + for (child = domain->link_list->children; child; child = child->sibling) { + + /* Skip if this is not a bridge or has no children under it. */ + if (!dev_has_children(child)) + continue; + + compute_bridge_resources(child, IORESOURCE_IO); + compute_bridge_resources(child, IORESOURCE_MEM); + compute_bridge_resources(child, IORESOURCE_MEM | IORESOURCE_PREFETCH); + } +} + +static unsigned char get_alignment_by_resource_type(const struct resource *res) +{ + if (res->flags & IORESOURCE_MEM) + return 12; /* Page-aligned --> log2(4KiB) */ + else if (res->flags & IORESOURCE_IO) + return 0; /* No special alignment required --> log2(1) */ + + die("Unexpected resource type: flags(%d)!\n", res->flags); +} + +static void initialize_memranges(struct memranges *ranges, const struct resource *res, + unsigned long memrange_type) +{ + resource_t res_base; + resource_t res_limit; + unsigned char align = get_alignment_by_resource_type(res); + + memranges_init_empty_with_alignment(ranges, NULL, 0, align); + + if ((res == NULL) || !(res->flags & IORESOURCE_ASSIGNED)) + return; + + res_base = res->base; + res_limit = res->limit; + + memranges_insert(ranges, res_base, res_limit - res_base + 1, memrange_type); +} + +static void print_resource_ranges(const struct memranges *ranges) +{ + const struct range_entry *r; + + printk(BIOS_INFO, "Resource ranges:\n"); + + if (memranges_is_empty(ranges)) + printk(BIOS_INFO, "EMPTY!!\n"); + + memranges_each_entry(r, ranges) { + printk(BIOS_INFO, "Base: %llx, Size: %llx, Tag: %lx\n", + range_entry_base(r), range_entry_size(r), range_entry_tag(r)); + } +} + +/* + * This is where the actual allocation of resources happens during pass 2. Given the list of + * memory ranges corresponding to the resource of given type, it finds the biggest unallocated + * resource using the type mask on the downstream bus. This continues in a descending + * order until all resources of given type are allocated address space within the current + * resource window. + */ +static void allocate_child_resources(struct bus *bus, struct memranges *ranges, + unsigned long type_mask, unsigned long type_match) +{ + struct resource *resource = NULL; + const struct device *dev; + + while ((dev = largest_resource(bus, &resource, type_mask, type_match))) { + + if (!resource->size) + continue; + + if (memranges_steal(ranges, resource->limit, resource->size, resource->align, + type_match, &resource->base) == false) { + printk(BIOS_ERR, "ERROR: Resource didn't fit!!! "); + printk(BIOS_SPEW, "%s %02lx * size: 0x%llx limit: %llx %s\n", + dev_path(dev), resource->index, + resource->size, resource->limit, resource2str(resource)); + continue; + } + + resource->limit = resource->base + resource->size - 1; + resource->flags |= IORESOURCE_ASSIGNED; + + printk(BIOS_SPEW, "%s %02lx * [0x%llx - 0x%llx] limit: %llx %s\n", + dev_path(dev), resource->index, resource->base, + resource->size ? resource->base + resource->size - 1 : + resource->base, resource->limit, resource2str(resource)); + } +} + +static void update_constraints(struct memranges *ranges, const struct device *dev, + const struct resource *res) +{ + if (!res->size) + return; + + printk(BIOS_SPEW, "%s: %s %02lx base %08llx limit %08llx %s (fixed)\n", + __func__, dev_path(dev), res->index, res->base, + res->base + res->size - 1, resource2str(res)); + + memranges_create_hole(ranges, res->base, res->size); +} + +/* + * Scan the entire tree to identify any fixed resources allocated by any device to + * ensure that the address map for domain resources are appropriately updated. + * + * Domains can typically provide memrange for entire address space. So, this function + * punches holes in the address space for all fixed resources that are already + * defined. Both IO and normal memory resources are added as fixed. Both need to be + * removed from address space where dynamic resource allocations are sourced. + */ +static void avoid_fixed_resources(struct memranges *ranges, const struct device *dev, + unsigned long mask_match) +{ + const struct resource *res; + const struct device *child; + const struct bus *bus; + + for (res = dev->resource_list; res != NULL; res = res->next) { + if ((res->flags & mask_match) != mask_match) + continue; + update_constraints(ranges, dev, res); + } + + bus = dev->link_list; + if (bus == NULL) + return; + + for (child = bus->children; child != NULL; child = child->sibling) + avoid_fixed_resources(ranges, child, mask_match); +} + +static void constrain_domain_resources(const struct device *domain, struct memranges *ranges, + unsigned long type) +{ + unsigned long mask_match = type | IORESOURCE_FIXED; + + if (type == IORESOURCE_IO) { + /* + * Don't allow allocations in the VGA I/O range. PCI has special cases for + * that. + */ + memranges_create_hole(ranges, 0x3b0, 0x3df); + + /* + * Resource allocator no longer supports the legacy behavior where I/O resource + * allocation is guaranteed to avoid aliases over legacy PCI expansion card + * addresses. + */ + } + + avoid_fixed_resources(ranges, domain, mask_match); +} + +/* + * This function creates a list of memranges of given type using the resource that is + * provided. If the given resource is NULL or if the resource window size is 0, then it creates + * an empty list. This results in resource allocation for that resource type failing for all + * downstream devices since there is nothing to allocate from. + * + * In case of domain, it applies additional constraints to ensure that the memranges do not + * overlap any of the fixed resources under that domain. Domain typically seems to provide + * memrange for entire address space. Thus, it is up to the chipset to add DRAM and all other + * windows which cannot be used for resource allocation as fixed resources. + */ +static void setup_resource_ranges(const struct device *dev, const struct resource *res, + unsigned long type, struct memranges *ranges) +{ + printk(BIOS_SPEW, "%s %s: base: %llx size: %llx align: %d gran: %d limit: %llx\n", + dev_path(dev), resource2str(res), res->base, res->size, res->align, + res->gran, res->limit); + + initialize_memranges(ranges, res, type); + + if (dev->path.type == DEVICE_PATH_DOMAIN) + constrain_domain_resources(dev, ranges, type); + + print_resource_ranges(ranges); +} + +static void cleanup_resource_ranges(const struct device *dev, struct memranges *ranges, + const struct resource *res) +{ + memranges_teardown(ranges); + printk(BIOS_SPEW, "%s %s: base: %llx size: %llx align: %d gran: %d limit: %llx done\n", + dev_path(dev), resource2str(res), res->base, res->size, res->align, + res->gran, res->limit); +} + +/* + * Pass 2 of resource allocator at the bridge level loops through all the resources for the + * bridge and generates a list of memory ranges similar to that at the domain level. However, + * there is no need to apply any additional constraints since the window allocated to the bridge + * is guaranteed to be non-overlapping by the allocator at domain level. + * + * Allocation at the bridge level works the same as at domain level (starts with the biggest + * resource requirement from downstream devices and continues in descending order). One major + * difference at the bridge level is that it considers prefmem resources separately from mem + * resources. + * + * Once allocation at the current bridge is complete, resource allocator continues walking down + * the downstream bridges until it hits the leaf devices. + */ +static void allocate_bridge_resources(const struct device *bridge) +{ + struct memranges ranges; + const struct resource *res; + struct bus *bus = bridge->link_list; + unsigned long type_match; + struct device *child; + const unsigned long type_mask = IORESOURCE_TYPE_MASK | IORESOURCE_PREFETCH; + + for (res = bridge->resource_list; res; res = res->next) { + if (!res->size) + continue; + + if (!(res->flags & IORESOURCE_BRIDGE)) + continue; + + type_match = res->flags & type_mask; + + setup_resource_ranges(bridge, res, type_match, &ranges); + allocate_child_resources(bus, &ranges, type_mask, type_match); + cleanup_resource_ranges(bridge, &ranges, res); + } + + for (child = bus->children; child; child = child->sibling) { + if (!dev_has_children(child)) + continue; + + allocate_bridge_resources(child); + } +} + +static const struct resource *find_domain_resource(const struct device *domain, + unsigned long type) +{ + const struct resource *res; + + for (res = domain->resource_list; res; res = res->next) { + if (res->flags & IORESOURCE_FIXED) + continue; + + if ((res->flags & IORESOURCE_TYPE_MASK) == type) + return res; + } + + return NULL; +} + +/* + * Pass 2 of resource allocator begins at the domain level. Every domain has two types of + * resources - io and mem. For each of these resources, this function creates a list of memory + * ranges that can be used for downstream resource allocation. This list is constrained to + * remove any fixed resources in the domain sub-tree of the given resource type. It then uses + * the memory ranges to apply best fit on the resource requirements of the downstream devices. + * + * Once resources are allocated to all downstream devices of the domain, it walks down each + * downstream bridge to continue the same process until resources are allocated to all devices + * under the domain. + */ +static void allocate_domain_resources(const struct device *domain) +{ + struct memranges ranges; + struct device *child; + const struct resource *res; + + /* Resource type I/O */ + res = find_domain_resource(domain, IORESOURCE_IO); + if (res) { + setup_resource_ranges(domain, res, IORESOURCE_IO, &ranges); + allocate_child_resources(domain->link_list, &ranges, IORESOURCE_TYPE_MASK, + IORESOURCE_IO); + cleanup_resource_ranges(domain, &ranges, res); + } + + /* + * Resource type Mem: + * Domain does not distinguish between mem and prefmem resources. Thus, the resource + * allocation at domain level considers mem and prefmem together when finding the best + * fit based on the biggest resource requirement. + */ + res = find_domain_resource(domain, IORESOURCE_MEM); + if (res) { + setup_resource_ranges(domain, res, IORESOURCE_MEM, &ranges); + allocate_child_resources(domain->link_list, &ranges, IORESOURCE_TYPE_MASK, + IORESOURCE_MEM); + cleanup_resource_ranges(domain, &ranges, res); + } + + for (child = domain->link_list->children; child; child = child->sibling) { + if (!dev_has_children(child)) + continue; + + /* Continue allocation for all downstream bridges. */ + allocate_bridge_resources(child); + } +} + +/* + * This function forms the guts of the resource allocator. It walks through the entire device + * tree for each domain two times. + * + * Every domain has a fixed set of ranges. These ranges cannot be relaxed based on the + * requirements of the downstream devices. They represent the available windows from which + * resources can be allocated to the different devices under the domain. + * + * In order to identify the requirements of downstream devices, resource allocator walks in a + * DFS fashion. It gathers the requirements from leaf devices and propagates those back up + * to their upstream bridges until the requirements for all the downstream devices of the domain + * are gathered. This is referred to as pass 1 of resource allocator. + * + * Once the requirements for all the devices under the domain are gathered, resource allocator + * walks a second time to allocate resources to downstream devices as per the + * requirements. It always picks the biggest resource request as per the type (i/o and mem) to + * allocate space from its fixed window to the immediate downstream device of the domain. In + * order to accomplish best fit for the resources, a list of ranges is maintained by each + * resource type (i/o and mem). Domain does not differentiate between mem and prefmem. Since + * they are allocated space from the same window, the resource allocator at the domain level + * ensures that the biggest requirement is selected indepedent of the prefetch type. Once the + * resource allocation for all immediate downstream devices is complete at the domain level, + * resource allocator walks down the subtree for each downstream bridge to continue the + * allocation process at the bridge level. Since bridges have separate windows for i/o, mem and + * prefmem, best fit algorithm at bridge level looks for the biggest requirement considering + * prefmem resources separately from non-prefmem resources. This continues until resource + * allocation is performed for all downstream bridges in the domain sub-tree. This is referred + * to as pass 2 of resource allocator. + * + * Some rules that are followed by the resource allocator: + * - Allocate resource locations for every device as long as the requirements can be satisfied. + * - If a resource cannot be allocated any address space, then that resource needs to be + * properly updated to ensure that it does not incorrectly overlap some address space reserved + * for a different purpose. + * - Don't overlap with resources in fixed locations. + * - Don't overlap and follow the rules of bridges -- downstream devices of bridges should use + * parts of the address space allocated to the bridge. + */ +void allocate_resources(const struct device *root) +{ + const struct device *child; + + if ((root == NULL) || (root->link_list == NULL)) + return; + + for (child = root->link_list->children; child; child = child->sibling) { + + if (child->path.type != DEVICE_PATH_DOMAIN) + continue; + + post_log_path(child); + + /* Pass 1 - Gather requirements. */ + printk(BIOS_INFO, "Resource allocator: %s - Pass 1 (gathering requirements)\n", + dev_path(child)); + compute_domain_resources(child); + + /* Pass 2 - Allocate resources as per gathered requirements. */ + printk(BIOS_INFO, "Resource allocator: %s - Pass 2 (allocating resources)\n", + dev_path(child)); + allocate_domain_resources(child); + } +}
Nico Huber has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41443 )
Change subject: device: Add support for resource allocator v4 ......................................................................
Patch Set 10:
(3 comments)
Some late comments I forgot to send. Nothing serious.
https://review.coreboot.org/c/coreboot/+/41443/9/src/device/resource_allocat... File src/device/resource_allocator_v4.c:
https://review.coreboot.org/c/coreboot/+/41443/9/src/device/resource_allocat... PS9, Line 103: child_res->limit && Why? doesn't it cover up errors?
https://review.coreboot.org/c/coreboot/+/41443/9/src/device/resource_allocat... PS9, Line 271: resource->flags |= IORESOURCE_ASSIGNED; Not clearing IORESOURCE_STORED means we must be called with all non-fixed resources without it set. The old behavior seemed correct.
https://review.coreboot.org/c/coreboot/+/41443/9/src/device/resource_allocat... PS9, Line 333: 0x3df Last parameter is the size.
9elements QA has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41443 )
Change subject: device: Add support for resource allocator v4 ......................................................................
Patch Set 10:
Automatic boot test returned (PASS/FAIL/TOTAL): 4/0/4 Emulation targets: "QEMU x86 q35/ich9" using payload TianoCore : SUCCESS : https://lava.9esec.io/r/4143 "QEMU x86 q35/ich9" using payload SeaBIOS : SUCCESS : https://lava.9esec.io/r/4142 "QEMU x86 i440fx/piix4" using payload SeaBIOS : SUCCESS : https://lava.9esec.io/r/4141 "QEMU AArch64" using payload LinuxBoot_u-root_kexec : SUCCESS : https://lava.9esec.io/r/4140
Please note: This test is under development and might not be accurate at all!
Furquan Shaikh has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41443 )
Change subject: device: Add support for resource allocator v4 ......................................................................
Patch Set 10:
(3 comments)
https://review.coreboot.org/c/coreboot/+/41443/9/src/device/resource_allocat... File src/device/resource_allocator_v4.c:
https://review.coreboot.org/c/coreboot/+/41443/9/src/device/resource_allocat... PS9, Line 103: child_res->limit &&
Why? doesn't it cover up errors?
Resource allocation for that child would still fail in pass 2 and get reported accordingly. And it also allows the resource allocation for rest of the children of the bridge.
https://review.coreboot.org/c/coreboot/+/41443/9/src/device/resource_allocat... PS9, Line 271: resource->flags |= IORESOURCE_ASSIGNED;
Not clearing IORESOURCE_STORED means we must be called with all non-fixed resources without it set.
Shouldn't that be the expectation? IORESOURCE_STORED should be set only after the resource assignment is actually stored within the device.
https://review.coreboot.org/c/coreboot/+/41443/9/src/device/resource_allocat... PS9, Line 333: 0x3df
Last parameter is the size.
Thanks for catching this: https://review.coreboot.org/c/coreboot/+/41737
Nico Huber has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41443 )
Change subject: device: Add support for resource allocator v4 ......................................................................
Patch Set 10:
(2 comments)
https://review.coreboot.org/c/coreboot/+/41443/9/src/device/resource_allocat... File src/device/resource_allocator_v4.c:
https://review.coreboot.org/c/coreboot/+/41443/9/src/device/resource_allocat... PS9, Line 103: child_res->limit &&
Resource allocation for that child would still fail in pass 2 and get reported accordingly. […]
Yes, but shouldn't we skip the whole resource? Pass 2 skips it implicitly, so accounting for its size seems wrong (only matters if we run out of space).
https://review.coreboot.org/c/coreboot/+/41443/9/src/device/resource_allocat... PS9, Line 271: resource->flags |= IORESOURCE_ASSIGNED;
Not clearing IORESOURCE_STORED means we must be called with all non-fixed resources without it set […]
There are potentially resources already stored by blobs. And in some cases, there I'm sure, we have resources stored for console devices. If that's anywhere reported via IORESOURCE_STORED, I don't know. But the old allocator explicitly supported this case.
Mike Banon has posted comments on this change. ( https://review.coreboot.org/c/coreboot/+/41443 )
Change subject: device: Add support for resource allocator v4 ......................................................................
Patch Set 10:
Some comments unresolved :P