| /* SPDX-License-Identifier: GPL-2.0-only */ |
| |
| #include <commonlib/bsd/helpers.h> |
| #include <console/console.h> |
| #include <device/device.h> |
| #include <memrange.h> |
| #include <post.h> |
| #include <types.h> |
| |
| 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 void print_domain_res(const struct device *dev, |
| const struct resource *res, const char *suffix) |
| { |
| printk(BIOS_DEBUG, "%s %s: base: %llx size: %llx align: %u gran: %u limit: %llx%s\n", |
| dev_path(dev), resource2str(res), res->base, res->size, |
| res->align, res->gran, res->limit, suffix); |
| } |
| |
| #define res_printk(depth, str, ...) printk(BIOS_DEBUG, "%*c"str, depth, ' ', __VA_ARGS__) |
| |
| static void print_bridge_res(const struct device *dev, const struct resource *res, |
| int depth, const char *suffix) |
| { |
| res_printk(depth, "%s %s: size: %llx align: %u gran: %u limit: %llx%s\n", dev_path(dev), |
| resource2str(res), res->size, res->align, res->gran, res->limit, suffix); |
| } |
| |
| static void print_child_res(const struct device *dev, const struct resource *res, int depth) |
| { |
| res_printk(depth + 1, "%s %02lx * [0x%llx - 0x%llx] %s\n", dev_path(dev), |
| res->index, res->base, res->base + res->size - 1, resource2str(res)); |
| } |
| |
| static void print_fixed_res(const struct device *dev, |
| const struct resource *res, const char *prefix) |
| { |
| printk(BIOS_DEBUG, " %s: %s %02lx base %08llx limit %08llx %s (fixed)\n", |
| prefix, dev_path(dev), res->index, res->base, res->base + res->size - 1, |
| resource2str(res)); |
| } |
| |
| static void print_assigned_res(const struct device *dev, const struct resource *res) |
| { |
| printk(BIOS_DEBUG, " %s %02lx * [0x%llx - 0x%llx] limit: %llx %s\n", |
| dev_path(dev), res->index, res->base, res->limit, res->limit, resource2str(res)); |
| } |
| |
| static void print_failed_res(const struct device *dev, const struct resource *res) |
| { |
| printk(BIOS_DEBUG, " %s %02lx * size: 0x%llx limit: %llx %s\n", |
| dev_path(dev), res->index, res->size, res->limit, resource2str(res)); |
| } |
| |
| static void print_resource_ranges(const struct device *dev, const struct memranges *ranges) |
| { |
| const struct range_entry *r; |
| |
| printk(BIOS_INFO, " %s: Resource ranges:\n", dev_path(dev)); |
| |
| 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 bool dev_has_children(const struct device *dev) |
| { |
| const struct bus *bus = dev->downstream; |
| return bus && bus->children; |
| } |
| |
| static resource_t effective_limit(const struct resource *const res) |
| { |
| if (CONFIG(ALWAYS_ALLOW_ABOVE_4G_ALLOCATION)) |
| return res->limit; |
| |
| /* Always allow bridge resources above 4G. */ |
| if (res->flags & IORESOURCE_BRIDGE) |
| return res->limit; |
| |
| const resource_t quirk_4g_limit = |
| res->flags & IORESOURCE_ABOVE_4G ? UINT64_MAX : UINT32_MAX; |
| return MIN(res->limit, quirk_4g_limit); |
| } |
| |
| /* |
| * 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. |
| * |
| * Last but not least, it stores the offset inside the bridge resource |
| * for each child resource in its base field. This simplifies pass 2 |
| * for resources behind a bridge, as we only have to add offsets to the |
| * allocated base of the bridge resource. |
| */ |
| static void update_bridge_resource(const struct device *bridge, struct resource *bridge_res, |
| int print_depth) |
| { |
| const struct device *child; |
| struct resource *child_res; |
| resource_t base; |
| const unsigned long type_mask = IORESOURCE_TYPE_MASK | IORESOURCE_PREFETCH; |
| const unsigned long type_match = bridge_res->flags & type_mask; |
| struct bus *bus = bridge->downstream; |
| |
| child_res = NULL; |
| |
| /* |
| * `base` keeps track of where the next allocation for child resources |
| * 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; |
| |
| print_bridge_res(bridge, bridge_res, print_depth, ""); |
| |
| while ((child = largest_resource(bus, &child_res, type_mask, type_match))) { |
| |
| /* Size 0 resources can be skipped. */ |
| if (!child_res->size) |
| continue; |
| |
| /* Resources with 0 limit can't be assigned anything. */ |
| if (!child_res->limit) |
| continue; |
| |
| /* |
| * Propagate the resource alignment to the bridge resource. The |
| * condition can only be true for the first (largest) resource. For all |
| * other child resources, alignment is taken care of by rounding their |
| * base up. |
| */ |
| if (child_res->align > bridge_res->align) |
| bridge_res->align = child_res->align; |
| |
| /* |
| * Propagate the resource limit to the bridge resource. If a downstream |
| * device has stricter requirements w.r.t. limits for any resource, that |
| * constraint needs to be propagated back up to the bridges downstream |
| * of the domain. This way, the whole bridge resource fulfills the limit. |
| */ |
| if (effective_limit(child_res) < bridge_res->limit) |
| bridge_res->limit = effective_limit(child_res); |
| |
| /* |
| * Alignment value of 0 means that the child resource has no alignment |
| * requirements and so the base value remains unchanged here. |
| */ |
| base = ALIGN_UP(base, POWER_OF_2(child_res->align)); |
| |
| /* |
| * Store the relative offset inside the bridge resource for later |
| * consumption in allocate_bridge_resources(), and invalidate flags |
| * related to the base. |
| */ |
| child_res->base = base; |
| child_res->flags &= ~(IORESOURCE_ASSIGNED | IORESOURCE_STORED); |
| |
| print_child_res(child, child_res, print_depth); |
| |
| 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 = ALIGN_UP(base, POWER_OF_2(bridge_res->gran)); |
| |
| print_bridge_res(bridge, bridge_res, print_depth, " done"); |
| } |
| |
| /* |
| * During pass 1, at the bridge level, the resource allocator 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, |
| int print_depth) |
| { |
| const struct device *child; |
| struct resource *res; |
| struct bus *bus = bridge->downstream; |
| 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, print_depth + 1); |
| } |
| |
| /* |
| * Update the window for current bridge resource now that all downstream |
| * requirements are gathered. |
| */ |
| update_bridge_resource(bridge, res, print_depth); |
| } |
| } |
| |
| /* |
| * During pass 1, the 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 the 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; |
| const int print_depth = 1; |
| |
| if (domain->downstream == NULL) |
| return; |
| |
| for (child = domain->downstream->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, print_depth); |
| compute_bridge_resources(child, IORESOURCE_MEM, print_depth); |
| compute_bridge_resources(child, IORESOURCE_MEM | IORESOURCE_PREFETCH, |
| print_depth); |
| } |
| } |
| |
| /* |
| * 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 a memrange for entire address space. |
| * So, this function punches holes in the address space for all fixed |
| * resources that are already defined. Both I/O 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; |
| if (!res->size) |
| continue; |
| print_fixed_res(dev, res, __func__); |
| memranges_create_hole(ranges, res->base, res->size); |
| } |
| |
| bus = dev->downstream; |
| if (bus == NULL) |
| return; |
| |
| for (child = bus->children; child != NULL; child = child->sibling) |
| avoid_fixed_resources(ranges, child, mask_match); |
| } |
| |
| /* |
| * This function creates a list of memranges of given type using the |
| * resource that is provided. It applies additional constraints to |
| * ensure that the memranges do not overlap any of the fixed resources |
| * under the domain. The domain typically provides a memrange for the |
| * 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 *const domain, |
| const unsigned long type, |
| struct memranges *const ranges) |
| { |
| /* Align mem resources to 2^12 (4KiB pages) at a minimum, so they |
| can be memory-mapped individually (e.g. for virtualization guests). */ |
| const unsigned char alignment = type == IORESOURCE_MEM ? 12 : 0; |
| const unsigned long type_mask = IORESOURCE_TYPE_MASK | IORESOURCE_FIXED; |
| |
| memranges_init_empty_with_alignment(ranges, NULL, 0, alignment); |
| |
| for (struct resource *res = domain->resource_list; res != NULL; res = res->next) { |
| if ((res->flags & type_mask) != type) |
| continue; |
| print_domain_res(domain, res, ""); |
| memranges_insert(ranges, res->base, res->limit - res->base + 1, type); |
| } |
| |
| 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 - 0x3b0 + 1); |
| |
| /* |
| * 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, type | IORESOURCE_FIXED); |
| |
| print_resource_ranges(domain, ranges); |
| } |
| |
| static void cleanup_domain_resource_ranges(const struct device *dev, struct memranges *ranges, |
| unsigned long type) |
| { |
| memranges_teardown(ranges); |
| for (struct resource *res = dev->resource_list; res != NULL; res = res->next) { |
| if (res->flags & IORESOURCE_FIXED) |
| continue; |
| if ((res->flags & IORESOURCE_TYPE_MASK) != type) |
| continue; |
| print_domain_res(dev, res, " done"); |
| } |
| } |
| |
| static void assign_resource(struct resource *const res, const resource_t base, |
| const struct device *const dev) |
| { |
| res->base = base; |
| res->limit = res->base + res->size - 1; |
| res->flags |= IORESOURCE_ASSIGNED; |
| res->flags &= ~IORESOURCE_STORED; |
| |
| print_assigned_res(dev, res); |
| } |
| |
| /* |
| * This is where the actual allocation of resources happens during |
| * pass 2. We construct a list of memory ranges corresponding to the |
| * resource of a given type, then look for the biggest unallocated |
| * resource on the downstream bus. This continues in a descending order |
| * until all resources of a given type have space allocated within the |
| * domain's resource window. |
| */ |
| static void allocate_toplevel_resources(const struct device *const domain, |
| const unsigned long type) |
| { |
| const unsigned long type_mask = IORESOURCE_TYPE_MASK; |
| struct resource *res = NULL; |
| const struct device *dev; |
| struct memranges ranges; |
| resource_t base; |
| |
| if (!dev_has_children(domain)) |
| return; |
| |
| setup_resource_ranges(domain, type, &ranges); |
| |
| while ((dev = largest_resource(domain->downstream, &res, type_mask, type))) { |
| |
| if (!res->size) |
| continue; |
| |
| if (!memranges_steal(&ranges, effective_limit(res), res->size, res->align, |
| type, &base, CONFIG(RESOURCE_ALLOCATION_TOP_DOWN))) { |
| printk(BIOS_ERR, "Resource didn't fit!!!\n"); |
| print_failed_res(dev, res); |
| continue; |
| } |
| |
| assign_resource(res, base, dev); |
| } |
| |
| cleanup_domain_resource_ranges(domain, &ranges, type); |
| } |
| |
| /* |
| * Pass 2 of the resource allocator at the bridge level loops through |
| * all the resources for the bridge and assigns all the base addresses |
| * of its children's resources of the same type. update_bridge_resource() |
| * of pass 1 pre-calculated the offsets of these bases inside the bridge |
| * resource. Now that the bridge resource is allocated, all we have to |
| * do is to add its final base to these offsets. |
| * |
| * Once allocation at the current bridge is complete, resource allocator |
| * continues walking down the downstream bridges until it hits the leaf |
| * devices. |
| */ |
| static void assign_resource_cb(void *param, struct device *dev, struct resource *res) |
| { |
| /* We have to filter the same resources as update_bridge_resource(). */ |
| if (!res->size || !res->limit) |
| return; |
| |
| assign_resource(res, *(const resource_t *)param + res->base, dev); |
| } |
| static void allocate_bridge_resources(const struct device *bridge) |
| { |
| const unsigned long type_mask = |
| IORESOURCE_TYPE_MASK | IORESOURCE_PREFETCH | IORESOURCE_FIXED; |
| struct bus *const bus = bridge->downstream; |
| struct resource *res; |
| struct device *child; |
| |
| for (res = bridge->resource_list; res != NULL; res = res->next) { |
| if (!res->size) |
| continue; |
| |
| if (!(res->flags & IORESOURCE_BRIDGE)) |
| continue; |
| |
| if (!(res->flags & IORESOURCE_ASSIGNED)) |
| continue; |
| |
| /* Run assign_resource_cb() for all downstream resources of the same type. */ |
| search_bus_resources(bus, type_mask, res->flags & type_mask, |
| assign_resource_cb, &res->base); |
| } |
| |
| for (child = bus->children; child != NULL; child = child->sibling) { |
| if (!dev_has_children(child)) |
| continue; |
| |
| allocate_bridge_resources(child); |
| } |
| } |
| |
| /* |
| * 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 finish resource assignment |
| * of its children resources within its own window. |
| */ |
| static void allocate_domain_resources(const struct device *domain) |
| { |
| /* Resource type I/O */ |
| allocate_toplevel_resources(domain, IORESOURCE_IO); |
| |
| /* |
| * 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. |
| */ |
| allocate_toplevel_resources(domain, IORESOURCE_MEM); |
| |
| struct device *child; |
| for (child = domain->downstream->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 the resource allocator. |
| * |
| * Once the requirements for all the devices under the domain are |
| * gathered, the 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). At the domain level we don't 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 independent of the prefetch type. Once the |
| * resource allocation for all immediate downstream devices is complete |
| * at the domain level, the resource allocator walks down the subtree |
| * for each downstream bridge to continue the allocation process at the |
| * bridge level. Since bridges have either their whole window allocated |
| * or nothing, we only need to place downstream resources inside these |
| * windows by re-using offsets that were pre-calculated in pass 1. This |
| * continues until resource allocation is realized for all downstream |
| * bridges in the domain sub-tree. This is referred to as pass 2 of the |
| * 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. |
| * - 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->downstream == NULL)) |
| return; |
| |
| for (child = root->downstream->children; child; child = child->sibling) { |
| |
| if (child->path.type != DEVICE_PATH_DOMAIN) |
| continue; |
| |
| post_log_path(child); |
| |
| /* Pass 1 - Relative placement. */ |
| printk(BIOS_INFO, "=== Resource allocator: %s - Pass 1 (relative placement) ===\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); |
| |
| printk(BIOS_INFO, "=== Resource allocator: %s - resource allocation complete ===\n", |
| dev_path(child)); |
| } |
| } |