diff options
| -rw-r--r-- | src/device/Kconfig | 9 | ||||
| -rw-r--r-- | src/device/Makefile.inc | 1 | ||||
| -rw-r--r-- | src/device/resource_allocator_v4.c | 552 |
3 files changed, 562 insertions, 0 deletions
diff --git a/src/device/Kconfig b/src/device/Kconfig index a60965a01a..801b040e08 100644 --- a/src/device/Kconfig +++ b/src/device/Kconfig @@ -784,4 +784,13 @@ config RESOURCE_ALLOCATOR_V3 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 9bbab37fce..2e62d4284d 100644 --- a/src/device/Makefile.inc +++ b/src/device/Makefile.inc @@ -61,3 +61,4 @@ ramstage-y += mmio.c 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 0000000000..ece7150b32 --- /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); + } +} |