summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--src/device/Kconfig7
-rw-r--r--src/device/Makefile.inc3
-rw-r--r--src/device/device.c593
-rw-r--r--src/device/resource_allocator_common.c61
-rw-r--r--src/device/resource_allocator_v3.c546
-rw-r--r--src/include/device/resource.h20
6 files changed, 638 insertions, 592 deletions
diff --git a/src/device/Kconfig b/src/device/Kconfig
index 751083cf81..a60965a01a 100644
--- a/src/device/Kconfig
+++ b/src/device/Kconfig
@@ -777,4 +777,11 @@ config SOFTWARE_I2C
I2C controller is not (yet) available. The platform code needs to
provide bindings to manually toggle I2C lines.
+config RESOURCE_ALLOCATOR_V3
+ bool
+ default y
+ help
+ This config option enables resource allocator v3 which performs
+ top down allocation of resources in a single MMIO window.
+
endmenu
diff --git a/src/device/Makefile.inc b/src/device/Makefile.inc
index 966ca0d198..9bbab37fce 100644
--- a/src/device/Makefile.inc
+++ b/src/device/Makefile.inc
@@ -58,3 +58,6 @@ bootblock-y += mmio.c
verstage-y += mmio.c
romstage-y += mmio.c
ramstage-y += mmio.c
+
+ramstage-y += resource_allocator_common.c
+ramstage-$(CONFIG_RESOURCE_ALLOCATOR_V3) += resource_allocator_v3.c
diff --git a/src/device/device.c b/src/device/device.c
index e4b5f12023..c54a345eeb 100644
--- a/src/device/device.c
+++ b/src/device/device.c
@@ -146,33 +146,6 @@ struct device *alloc_find_dev(struct bus *parent, struct device_path *path)
}
/**
- * 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)
-{
- resource_t mask;
- mask = (1ULL << pow) - 1ULL;
- val += mask;
- val &= ~mask;
- return val;
-}
-
-static const char *resource2str(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";
-}
-
-/**
* Read the resources on all devices of a given bus.
*
* @param bus Bus to read the resources on.
@@ -209,523 +182,6 @@ static void read_resources(struct bus *bus)
dev_path(bus->dev), bus->secondary, bus->link_num);
}
-struct pick_largest_state {
- struct resource *last;
- const struct device *result_dev;
- struct resource *result;
- int seen_last;
-};
-
-static void pick_largest_resource(void *gp, struct device *dev,
- struct resource *resource)
-{
- struct pick_largest_state *state = gp;
- struct resource *last;
-
- last = state->last;
-
- /* Be certain to pick the successor to last. */
- if (resource == last) {
- state->seen_last = 1;
- return;
- }
- if (resource->flags & IORESOURCE_FIXED)
- return; /* Skip it. */
- if (last && ((last->align < resource->align) ||
- ((last->align == resource->align) &&
- (last->size < resource->size)) ||
- ((last->align == resource->align) &&
- (last->size == resource->size) && (!state->seen_last)))) {
- return;
- }
- if (!state->result ||
- (state->result->align < resource->align) ||
- ((state->result->align == resource->align) &&
- (state->result->size < resource->size))) {
- state->result_dev = dev;
- state->result = resource;
- }
-}
-
-static const struct device *largest_resource(struct bus *bus,
- struct resource **result_res,
- unsigned long type_mask,
- unsigned long type)
-{
- struct pick_largest_state state;
-
- state.last = *result_res;
- state.result_dev = NULL;
- state.result = NULL;
- state.seen_last = 0;
-
- search_bus_resources(bus, type_mask, type, pick_largest_resource,
- &state);
-
- *result_res = state.result;
- return state.result_dev;
-}
-
-/**
- * This function is the guts of the resource allocator.
- *
- * The problem.
- * - Allocate resource locations for every device.
- * - Don't overlap, and follow the rules of bridges.
- * - Don't overlap with resources in fixed locations.
- * - Be efficient so we don't have ugly strategies.
- *
- * The strategy.
- * - Devices that have fixed addresses are the minority so don't
- * worry about them too much. Instead only use part of the address
- * space for devices with programmable addresses. This easily handles
- * everything except bridges.
- *
- * - PCI devices are required to have their sizes and their alignments
- * equal. In this case an optimal solution to the packing problem
- * exists. Allocate all devices from highest alignment to least
- * alignment or vice versa. Use this.
- *
- * - So we can handle more than PCI run two allocation passes on bridges. The
- * first to see how large the resources are behind the bridge, and what
- * their alignment requirements are. The second to assign a safe address to
- * the devices behind the bridge. This allows us to treat a bridge as just
- * a device with a couple of resources, and not need to special case it in
- * the allocator. Also this allows handling of other types of bridges.
- *
- * @param bus The bus we are traversing.
- * @param bridge The bridge resource which must contain the bus' resources.
- * @param type_mask This value gets ANDed with the resource type.
- * @param type This value must match the result of the AND.
- * @return TODO
- */
-static void compute_resources(struct bus *bus, struct resource *bridge,
- unsigned long type_mask, unsigned long type)
-{
- const struct device *dev;
- struct resource *resource;
- resource_t base;
- base = round(bridge->base, bridge->align);
-
- if (!bus)
- return;
-
- printk(BIOS_SPEW, "%s %s: base: %llx size: %llx align: %d gran: %d"
- " limit: %llx\n", dev_path(bus->dev), resource2str(bridge),
- base, bridge->size, bridge->align,
- bridge->gran, bridge->limit);
-
- /* For each child which is a bridge, compute the resource needs. */
- for (dev = bus->children; dev; dev = dev->sibling) {
- struct resource *child_bridge;
-
- if (!dev->link_list)
- continue;
-
- /* Find the resources with matching type flags. */
- for (child_bridge = dev->resource_list; child_bridge;
- child_bridge = child_bridge->next) {
- struct bus* link;
-
- if (!(child_bridge->flags & IORESOURCE_BRIDGE)
- || (child_bridge->flags & type_mask) != type)
- continue;
-
- /*
- * Split prefetchable memory if combined. Many domains
- * use the same address space for prefetchable memory
- * and non-prefetchable memory. Bridges below them need
- * it separated. Add the PREFETCH flag to the type_mask
- * and type.
- */
- link = dev->link_list;
- while (link && link->link_num !=
- IOINDEX_LINK(child_bridge->index))
- link = link->next;
-
- if (link == NULL) {
- printk(BIOS_ERR, "link %ld not found on %s\n",
- IOINDEX_LINK(child_bridge->index),
- dev_path(dev));
- }
-
- compute_resources(link, child_bridge,
- type_mask | IORESOURCE_PREFETCH,
- type | (child_bridge->flags &
- IORESOURCE_PREFETCH));
- }
- }
-
- /* Remember we haven't found anything yet. */
- resource = NULL;
-
- /*
- * Walk through all the resources on the current bus and compute the
- * amount of address space taken by them. Take granularity and
- * alignment into account.
- */
- while ((dev = largest_resource(bus, &resource, type_mask, type))) {
-
- /* Size 0 resources can be skipped. */
- if (!resource->size)
- continue;
-
- /* Propagate the resource alignment to the bridge resource. */
- if (resource->align > bridge->align)
- bridge->align = resource->align;
-
- /* Propagate the resource limit to the bridge register. */
- if (bridge->limit > resource->limit)
- bridge->limit = resource->limit;
-
- /* Warn if it looks like APICs aren't declared. */
- if ((resource->limit == 0xffffffff) &&
- (resource->flags & IORESOURCE_ASSIGNED)) {
- printk(BIOS_ERR,
- "Resource limit looks wrong! (no APIC?)\n");
- printk(BIOS_ERR, "%s %02lx limit %08llx\n",
- dev_path(dev), resource->index, resource->limit);
- }
-
- if (resource->flags & IORESOURCE_IO) {
- /*
- * Don't allow potential aliases over the legacy PCI
- * expansion card addresses. The legacy PCI decodes
- * only 10 bits, uses 0x100 - 0x3ff. Therefore, only
- * 0x00 - 0xff can be used out of each 0x400 block of
- * I/O space.
- */
- if ((base & 0x300) != 0) {
- base = (base & ~0x3ff) + 0x400;
- }
- /*
- * Don't allow allocations in the VGA I/O range.
- * PCI has special cases for that.
- */
- else if ((base >= 0x3b0) && (base <= 0x3df)) {
- base = 0x3e0;
- }
- }
- /* Base must be aligned. */
- base = round(base, resource->align);
- resource->base = base;
- base += resource->size;
-
- printk(BIOS_SPEW, "%s %02lx * [0x%llx - 0x%llx] %s\n",
- dev_path(dev), resource->index, resource->base,
- resource->base + resource->size - 1,
- resource2str(resource));
- }
-
- /*
- * A PCI bridge resource does not need to be a power of two size, but
- * it does have a minimum granularity. Round the size up to that
- * minimum granularity so we know not to place something else at an
- * address positively decoded by the bridge.
- */
- bridge->size = round(base, bridge->gran) -
- round(bridge->base, bridge->align);
-
- printk(BIOS_SPEW, "%s %s: base: %llx size: %llx align: %d gran: %d"
- " limit: %llx done\n", dev_path(bus->dev),
- resource2str(bridge),
- base, bridge->size, bridge->align, bridge->gran, bridge->limit);
-}
-
-/**
- * This function is the second part of the resource allocator.
- *
- * See the compute_resources function for a more detailed explanation.
- *
- * This function assigns the resources a value.
- *
- * @param bus The bus we are traversing.
- * @param bridge The bridge resource which must contain the bus' resources.
- * @param type_mask This value gets ANDed with the resource type.
- * @param type This value must match the result of the AND.
- *
- * @see compute_resources
- */
-static void allocate_resources(struct bus *bus, struct resource *bridge,
- unsigned long type_mask, unsigned long type)
-{
- const struct device *dev;
- struct resource *resource;
- resource_t base;
- base = bridge->base;
-
- if (!bus)
- return;
-
- printk(BIOS_SPEW, "%s %s: base:%llx size:%llx align:%d gran:%d "
- "limit:%llx\n", dev_path(bus->dev),
- resource2str(bridge),
- base, bridge->size, bridge->align, bridge->gran, bridge->limit);
-
- /* Remember we haven't found anything yet. */
- resource = NULL;
-
- /*
- * Walk through all the resources on the current bus and allocate them
- * address space.
- */
- while ((dev = largest_resource(bus, &resource, type_mask, type))) {
-
- /* Propagate the bridge limit to the resource register. */
- if (resource->limit > bridge->limit)
- resource->limit = bridge->limit;
-
- /* Size 0 resources can be skipped. */
- if (!resource->size) {
- /* Set the base to limit so it doesn't confuse tolm. */
- resource->base = resource->limit;
- resource->flags |= IORESOURCE_ASSIGNED;
- continue;
- }
-
- if (resource->flags & IORESOURCE_IO) {
- /*
- * Don't allow potential aliases over the legacy PCI
- * expansion card addresses. The legacy PCI decodes
- * only 10 bits, uses 0x100 - 0x3ff. Therefore, only
- * 0x00 - 0xff can be used out of each 0x400 block of
- * I/O space.
- */
- if ((base & 0x300) != 0) {
- base = (base & ~0x3ff) + 0x400;
- }
- /*
- * Don't allow allocations in the VGA I/O range.
- * PCI has special cases for that.
- */
- else if ((base >= 0x3b0) && (base <= 0x3df)) {
- base = 0x3e0;
- }
- }
-
- if ((round(base, resource->align) + resource->size - 1) <=
- resource->limit) {
- /* Base must be aligned. */
- base = round(base, resource->align);
- resource->base = base;
- resource->limit = resource->base + resource->size - 1;
- resource->flags |= IORESOURCE_ASSIGNED;
- resource->flags &= ~IORESOURCE_STORED;
- base += resource->size;
- } else {
- printk(BIOS_ERR, "!! Resource didn't fit !!\n");
- printk(BIOS_ERR, " aligned base %llx size %llx "
- "limit %llx\n", round(base, resource->align),
- resource->size, resource->limit);
- printk(BIOS_ERR, " %llx needs to be <= %llx "
- "(limit)\n", (round(base, resource->align) +
- resource->size) - 1, resource->limit);
- printk(BIOS_ERR, " %s%s %02lx * [0x%llx - 0x%llx]"
- " %s\n", (resource->flags & IORESOURCE_ASSIGNED)
- ? "Assigned: " : "", dev_path(dev),
- resource->index, resource->base,
- resource->base + resource->size - 1,
- resource2str(resource));
- }
-
- printk(BIOS_SPEW, "%s %02lx * [0x%llx - 0x%llx] %s\n",
- dev_path(dev), resource->index, resource->base,
- resource->size ? resource->base + resource->size - 1 :
- resource->base, resource2str(resource));
- }
-
- /*
- * A PCI bridge resource does not need to be a power of two size, but
- * it does have a minimum granularity. Round the size up to that
- * minimum granularity so we know not to place something else at an
- * address positively decoded by the bridge.
- */
-
- bridge->flags |= IORESOURCE_ASSIGNED;
-
- printk(BIOS_SPEW, "%s %s: next_base: %llx size: %llx align: %d "
- "gran: %d done\n", dev_path(bus->dev),
- resource2str(bridge), base, bridge->size, bridge->align,
- bridge->gran);
-
- /* For each child which is a bridge, allocate_resources. */
- for (dev = bus->children; dev; dev = dev->sibling) {
- struct resource *child_bridge;
-
- if (!dev->link_list)
- continue;
-
- /* Find the resources with matching type flags. */
- for (child_bridge = dev->resource_list; child_bridge;
- child_bridge = child_bridge->next) {
- struct bus* link;
-
- if (!(child_bridge->flags & IORESOURCE_BRIDGE) ||
- (child_bridge->flags & type_mask) != type)
- continue;
-
- /*
- * Split prefetchable memory if combined. Many domains
- * use the same address space for prefetchable memory
- * and non-prefetchable memory. Bridges below them need
- * it separated. Add the PREFETCH flag to the type_mask
- * and type.
- */
- link = dev->link_list;
- while (link && link->link_num !=
- IOINDEX_LINK(child_bridge->index))
- link = link->next;
- if (link == NULL)
- printk(BIOS_ERR, "link %ld not found on %s\n",
- IOINDEX_LINK(child_bridge->index),
- dev_path(dev));
-
- allocate_resources(link, child_bridge,
- type_mask | IORESOURCE_PREFETCH,
- type | (child_bridge->flags &
- IORESOURCE_PREFETCH));
- }
- }
-}
-
-static int resource_is(struct resource *res, u32 type)
-{
- return (res->flags & IORESOURCE_TYPE_MASK) == type;
-}
-
-struct constraints {
- struct resource io, mem;
-};
-
-static struct resource *resource_limit(struct constraints *limits,
- struct resource *res)
-{
- struct resource *lim = NULL;
-
- /* MEM, or I/O - skip any others. */
- if (resource_is(res, IORESOURCE_MEM))
- lim = &limits->mem;
- else if (resource_is(res, IORESOURCE_IO))
- lim = &limits->io;
-
- return lim;
-}
-
-static void constrain_resources(const struct device *dev,
- struct constraints* limits)
-{
- const struct device *child;
- struct resource *res;
- struct resource *lim;
- struct bus *link;
-
- /* Constrain limits based on the fixed resources of this device. */
- for (res = dev->resource_list; res; res = res->next) {
- if (!(res->flags & IORESOURCE_FIXED))
- continue;
- if (!res->size) {
- /* It makes no sense to have 0-sized, fixed resources.*/
- printk(BIOS_ERR, "skipping %s@%lx fixed resource, "
- "size=0!\n", dev_path(dev), res->index);
- continue;
- }
-
- lim = resource_limit(limits, res);
- if (!lim)
- continue;
-
- /*
- * Is it a fixed resource outside the current known region?
- * If so, we don't have to consider it - it will be handled
- * correctly and doesn't affect current region's limits.
- */
- if (((res->base + res->size -1) < lim->base)
- || (res->base > lim->limit))
- continue;
-
- 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));
-
- /*
- * Choose to be above or below fixed resources. This check is
- * signed so that "negative" amounts of space are handled
- * correctly.
- */
- if ((signed long long)(lim->limit - (res->base + res->size -1))
- > (signed long long)(res->base - lim->base))
- lim->base = res->base + res->size;
- else
- lim->limit = res->base -1;
- }
-
- /* Descend into every enabled child and look for fixed resources. */
- for (link = dev->link_list; link; link = link->next) {
- for (child = link->children; child; child = child->sibling) {
- if (child->enabled)
- constrain_resources(child, limits);
- }
- }
-}
-
-static void avoid_fixed_resources(const struct device *dev)
-{
- struct constraints limits;
- struct resource *res;
- struct resource *lim;
-
- printk(BIOS_SPEW, "%s: %s\n", __func__, dev_path(dev));
-
- /* Initialize constraints to maximum size. */
- limits.io.base = 0;
- limits.io.limit = 0xffffffffffffffffULL;
- limits.mem.base = 0;
- limits.mem.limit = 0xffffffffffffffffULL;
-
- /* Constrain the limits to dev's initial resources. */
- for (res = dev->resource_list; res; res = res->next) {
- if ((res->flags & IORESOURCE_FIXED))
- continue;
- printk(BIOS_SPEW, "%s:@%s %02lx limit %08llx\n", __func__,
- dev_path(dev), res->index, res->limit);
-
- lim = resource_limit(&limits, res);
- if (!lim)
- continue;
-
- if (res->base > lim->base)
- lim->base = res->base;
- if (res->limit < lim->limit)
- lim->limit = res->limit;
- }
-
- /* Look through the tree for fixed resources and update the limits. */
- constrain_resources(dev, &limits);
-
- /* Update dev's resources with new limits. */
- for (res = dev->resource_list; res; res = res->next) {
- if ((res->flags & IORESOURCE_FIXED))
- continue;
-
- lim = resource_limit(&limits, res);
- if (!lim)
- continue;
-
- /* Is the resource outside the limits? */
- if (lim->base > res->base)
- res->base = lim->base;
- if (res->limit > lim->limit)
- res->limit = lim->limit;
-
- /* MEM resources need to start at the highest address manageable. */
- if (res->flags & IORESOURCE_MEM)
- res->base = resource_max(res);
-
- printk(BIOS_SPEW, "%s:@%s %02lx base %08llx limit %08llx\n",
- __func__, dev_path(dev), res->index, res->base, res->limit);
- }
-}
-
struct device *vga_pri = NULL;
static void set_vga_bridge_bits(void)
{
@@ -996,9 +452,7 @@ void dev_enumerate(void)
*/
void dev_configure(void)
{
- struct resource *res;
const struct device *root;
- const struct device *child;
set_vga_bridge_bits();
@@ -1020,53 +474,8 @@ void dev_configure(void)
print_resource_tree(root, BIOS_SPEW, "After reading.");
- /* Compute resources for all domains. */
- for (child = root->link_list->children; child; child = child->sibling) {
- if (!(child->path.type == DEVICE_PATH_DOMAIN))
- continue;
- post_log_path(child);
- for (res = child->resource_list; res; res = res->next) {
- if (res->flags & IORESOURCE_FIXED)
- continue;
- if (res->flags & IORESOURCE_MEM) {
- compute_resources(child->link_list,
- res, IORESOURCE_TYPE_MASK, IORESOURCE_MEM);
- continue;
- }
- if (res->flags & IORESOURCE_IO) {
- compute_resources(child->link_list,
- res, IORESOURCE_TYPE_MASK, IORESOURCE_IO);
- continue;
- }
- }
- }
-
- /* For all domains. */
- for (child = root->link_list->children; child; child=child->sibling)
- if (child->path.type == DEVICE_PATH_DOMAIN)
- avoid_fixed_resources(child);
+ allocate_resources(root);
- /* Store the computed resource allocations into device registers ... */
- printk(BIOS_INFO, "Setting resources...\n");
- for (child = root->link_list->children; child; child = child->sibling) {
- if (!(child->path.type == DEVICE_PATH_DOMAIN))
- continue;
- post_log_path(child);
- for (res = child->resource_list; res; res = res->next) {
- if (res->flags & IORESOURCE_FIXED)
- continue;
- if (res->flags & IORESOURCE_MEM) {
- allocate_resources(child->link_list,
- res, IORESOURCE_TYPE_MASK, IORESOURCE_MEM);
- continue;
- }
- if (res->flags & IORESOURCE_IO) {
- allocate_resources(child->link_list,
- res, IORESOURCE_TYPE_MASK, IORESOURCE_IO);
- continue;
- }
- }
- }
assign_resources(root->link_list);
printk(BIOS_INFO, "Done setting resources.\n");
print_resource_tree(root, BIOS_SPEW, "After assigning values.");
diff --git a/src/device/resource_allocator_common.c b/src/device/resource_allocator_common.c
new file mode 100644
index 0000000000..202318bfe6
--- /dev/null
+++ b/src/device/resource_allocator_common.c
@@ -0,0 +1,61 @@
+/* SPDX-License-Identifier: GPL-2.0-only */
+
+#include <console/console.h>
+#include <device/device.h>
+
+struct pick_largest_state {
+ struct resource *last;
+ const struct device *result_dev;
+ struct resource *result;
+ int seen_last;
+};
+
+static void pick_largest_resource(void *gp, struct device *dev,
+ struct resource *resource)
+{
+ struct pick_largest_state *state = gp;
+ struct resource *last;
+
+ last = state->last;
+
+ /* Be certain to pick the successor to last. */
+ if (resource == last) {
+ state->seen_last = 1;
+ return;
+ }
+ if (resource->flags & IORESOURCE_FIXED)
+ return; /* Skip it. */
+ if (last && ((last->align < resource->align) ||
+ ((last->align == resource->align) &&
+ (last->size < resource->size)) ||
+ ((last->align == resource->align) &&
+ (last->size == resource->size) && (!state->seen_last)))) {
+ return;
+ }
+ if (!state->result ||
+ (state->result->align < resource->align) ||
+ ((state->result->align == resource->align) &&
+ (state->result->size < resource->size))) {
+ state->result_dev = dev;
+ state->result = resource;
+ }
+}
+
+const struct device *largest_resource(struct bus *bus,
+ struct resource **result_res,
+ unsigned long type_mask,
+ unsigned long type)
+{
+ struct pick_largest_state state;
+
+ state.last = *result_res;
+ state.result_dev = NULL;
+ state.result = NULL;
+ state.seen_last = 0;
+
+ search_bus_resources(bus, type_mask, type, pick_largest_resource,
+ &state);
+
+ *result_res = state.result;
+ return state.result_dev;
+}
diff --git a/src/device/resource_allocator_v3.c b/src/device/resource_allocator_v3.c
new file mode 100644
index 0000000000..4eeb2409f8
--- /dev/null
+++ b/src/device/resource_allocator_v3.c
@@ -0,0 +1,546 @@
+/* SPDX-License-Identifier: GPL-2.0-only */
+
+#include <console/console.h>
+#include <device/device.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)
+{
+ resource_t mask;
+ mask = (1ULL << pow) - 1ULL;
+ val += mask;
+ val &= ~mask;
+ return val;
+}
+
+static const char *resource2str(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";
+}
+
+/**
+ * This function is the guts of the resource allocator.
+ *
+ * The problem.
+ * - Allocate resource locations for every device.
+ * - Don't overlap, and follow the rules of bridges.
+ * - Don't overlap with resources in fixed locations.
+ * - Be efficient so we don't have ugly strategies.
+ *
+ * The strategy.
+ * - Devices that have fixed addresses are the minority so don't
+ * worry about them too much. Instead only use part of the address
+ * space for devices with programmable addresses. This easily handles
+ * everything except bridges.
+ *
+ * - PCI devices are required to have their sizes and their alignments
+ * equal. In this case an optimal solution to the packing problem
+ * exists. Allocate all devices from highest alignment to least
+ * alignment or vice versa. Use this.
+ *
+ * - So we can handle more than PCI run two allocation passes on bridges. The
+ * first to see how large the resources are behind the bridge, and what
+ * their alignment requirements are. The second to assign a safe address to
+ * the devices behind the bridge. This allows us to treat a bridge as just
+ * a device with a couple of resources, and not need to special case it in
+ * the allocator. Also this allows handling of other types of bridges.
+ *
+ * @param bus The bus we are traversing.
+ * @param bridge The bridge resource which must contain the bus' resources.
+ * @param type_mask This value gets ANDed with the resource type.
+ * @param type This value must match the result of the AND.
+ * @return TODO
+ */
+static void compute_resources(struct bus *bus, struct resource *bridge,
+ unsigned long type_mask, unsigned long type)
+{
+ const struct device *dev;
+ struct resource *resource;
+ resource_t base;
+ base = round(bridge->base, bridge->align);
+
+ if (!bus)
+ return;
+
+ printk(BIOS_SPEW, "%s %s: base: %llx size: %llx align: %d gran: %d"
+ " limit: %llx\n", dev_path(bus->dev), resource2str(bridge),
+ base, bridge->size, bridge->align,
+ bridge->gran, bridge->limit);
+
+ /* For each child which is a bridge, compute the resource needs. */
+ for (dev = bus->children; dev; dev = dev->sibling) {
+ struct resource *child_bridge;
+
+ if (!dev->link_list)
+ continue;
+
+ /* Find the resources with matching type flags. */
+ for (child_bridge = dev->resource_list; child_bridge;
+ child_bridge = child_bridge->next) {
+ struct bus* link;
+
+ if (!(child_bridge->flags & IORESOURCE_BRIDGE)
+ || (child_bridge->flags & type_mask) != type)
+ continue;
+
+ /*
+ * Split prefetchable memory if combined. Many domains
+ * use the same address space for prefetchable memory
+ * and non-prefetchable memory. Bridges below them need
+ * it separated. Add the PREFETCH flag to the type_mask
+ * and type.
+ */
+ link = dev->link_list;
+ while (link && link->link_num !=
+ IOINDEX_LINK(child_bridge->index))
+ link = link->next;
+
+ if (link == NULL) {
+ printk(BIOS_ERR, "link %ld not found on %s\n",
+ IOINDEX_LINK(child_bridge->index),
+ dev_path(dev));
+ }
+
+ compute_resources(link, child_bridge,
+ type_mask | IORESOURCE_PREFETCH,
+ type | (child_bridge->flags &
+ IORESOURCE_PREFETCH));
+ }
+ }
+
+ /* Remember we haven't found anything yet. */
+ resource = NULL;
+
+ /*
+ * Walk through all the resources on the current bus and compute the
+ * amount of address space taken by them. Take granularity and
+ * alignment into account.
+ */
+ while ((dev = largest_resource(bus, &resource, type_mask, type))) {
+
+ /* Size 0 resources can be skipped. */
+ if (!resource->size)
+ continue;
+
+ /* Propagate the resource alignment to the bridge resource. */
+ if (resource->align > bridge->align)
+ bridge->align = resource->align;
+
+ /* Propagate the resource limit to the bridge register. */
+ if (bridge->limit > resource->limit)
+ bridge->limit = resource->limit;
+
+ /* Warn if it looks like APICs aren't declared. */
+ if ((resource->limit == 0xffffffff) &&
+ (resource->flags & IORESOURCE_ASSIGNED)) {
+ printk(BIOS_ERR,
+ "Resource limit looks wrong! (no APIC?)\n");
+ printk(BIOS_ERR, "%s %02lx limit %08llx\n",
+ dev_path(dev), resource->index, resource->limit);
+ }
+
+ if (resource->flags & IORESOURCE_IO) {
+ /*
+ * Don't allow potential aliases over the legacy PCI
+ * expansion card addresses. The legacy PCI decodes
+ * only 10 bits, uses 0x100 - 0x3ff. Therefore, only
+ * 0x00 - 0xff can be used out of each 0x400 block of
+ * I/O space.
+ */
+ if ((base & 0x300) != 0) {
+ base = (base & ~0x3ff) + 0x400;
+ }
+ /*
+ * Don't allow allocations in the VGA I/O range.
+ * PCI has special cases for that.
+ */
+ else if ((base >= 0x3b0) && (base <= 0x3df)) {
+ base = 0x3e0;
+ }
+ }
+ /* Base must be aligned. */
+ base = round(base, resource->align);
+ resource->base = base;
+ base += resource->size;
+
+ printk(BIOS_SPEW, "%s %02lx * [0x%llx - 0x%llx] %s\n",
+ dev_path(dev), resource->index, resource->base,
+ resource->base + resource->size - 1,
+ resource2str(resource));
+ }
+
+ /*
+ * A PCI bridge resource does not need to be a power of two size, but
+ * it does have a minimum granularity. Round the size up to that
+ * minimum granularity so we know not to place something else at an
+ * address positively decoded by the bridge.
+ */
+ bridge->size = round(base, bridge->gran) -
+ round(bridge->base, bridge->align);
+
+ printk(BIOS_SPEW, "%s %s: base: %llx size: %llx align: %d gran: %d"
+ " limit: %llx done\n", dev_path(bus->dev),
+ resource2str(bridge),
+ base, bridge->size, bridge->align, bridge->gran, bridge->limit);
+}
+
+/**
+ * This function is the second part of the resource allocator.
+ *
+ * See the compute_resources function for a more detailed explanation.
+ *
+ * This function assigns the resources a value.
+ *
+ * @param bus The bus we are traversing.
+ * @param bridge The bridge resource which must contain the bus' resources.
+ * @param type_mask This value gets ANDed with the resource type.
+ * @param type This value must match the result of the AND.
+ *
+ * @see compute_resources
+ */
+static void __allocate_resources(struct bus *bus, struct resource *bridge,
+ unsigned long type_mask, unsigned long type)
+{
+ const struct device *dev;
+ struct resource *resource;
+ resource_t base;
+ base = bridge->base;
+
+ if (!bus)
+ return;
+
+ printk(BIOS_SPEW, "%s %s: base:%llx size:%llx align:%d gran:%d "
+ "limit:%llx\n", dev_path(bus->dev),
+ resource2str(bridge),
+ base, bridge->size, bridge->align, bridge->gran, bridge->limit);
+
+ /* Remember we haven't found anything yet. */
+ resource = NULL;
+
+ /*
+ * Walk through all the resources on the current bus and allocate them
+ * address space.
+ */
+ while ((dev = largest_resource(bus, &resource, type_mask, type))) {
+
+ /* Propagate the bridge limit to the resource register. */
+ if (resource->limit > bridge->limit)
+ resource->limit = bridge->limit;
+
+ /* Size 0 resources can be skipped. */
+ if (!resource->size) {
+ /* Set the base to limit so it doesn't confuse tolm. */
+ resource->base = resource->limit;
+ resource->flags |= IORESOURCE_ASSIGNED;
+ continue;
+ }
+
+ if (resource->flags & IORESOURCE_IO) {
+ /*
+ * Don't allow potential aliases over the legacy PCI
+ * expansion card addresses. The legacy PCI decodes
+ * only 10 bits, uses 0x100 - 0x3ff. Therefore, only
+ * 0x00 - 0xff can be used out of each 0x400 block of
+ * I/O space.
+ */
+ if ((base & 0x300) != 0) {
+ base = (base & ~0x3ff) + 0x400;
+ }
+ /*
+ * Don't allow allocations in the VGA I/O range.
+ * PCI has special cases for that.
+ */
+ else if ((base >= 0x3b0) && (base <= 0x3df)) {
+ base = 0x3e0;
+ }
+ }
+
+ if ((round(base, resource->align) + resource->size - 1) <=
+ resource->limit) {
+ /* Base must be aligned. */
+ base = round(base, resource->align);
+ resource->base = base;
+ resource->limit = resource->base + resource->size - 1;
+ resource->flags |= IORESOURCE_ASSIGNED;
+ resource->flags &= ~IORESOURCE_STORED;
+ base += resource->size;
+ } else {
+ printk(BIOS_ERR, "!! Resource didn't fit !!\n");
+ printk(BIOS_ERR, " aligned base %llx size %llx "
+ "limit %llx\n", round(base, resource->align),
+ resource->size, resource->limit);
+ printk(BIOS_ERR, " %llx needs to be <= %llx "
+ "(limit)\n", (round(base, resource->align) +
+ resource->size) - 1, resource->limit);
+ printk(BIOS_ERR, " %s%s %02lx * [0x%llx - 0x%llx]"
+ " %s\n", (resource->flags & IORESOURCE_ASSIGNED)
+ ? "Assigned: " : "", dev_path(dev),
+ resource->index, resource->base,
+ resource->base + resource->size - 1,
+ resource2str(resource));
+ }
+
+ printk(BIOS_SPEW, "%s %02lx * [0x%llx - 0x%llx] %s\n",
+ dev_path(dev), resource->index, resource->base,
+ resource->size ? resource->base + resource->size - 1 :
+ resource->base, resource2str(resource));
+ }
+
+ /*
+ * A PCI bridge resource does not need to be a power of two size, but
+ * it does have a minimum granularity. Round the size up to that
+ * minimum granularity so we know not to place something else at an
+ * address positively decoded by the bridge.
+ */
+
+ bridge->flags |= IORESOURCE_ASSIGNED;
+
+ printk(BIOS_SPEW, "%s %s: next_base: %llx size: %llx align: %d "
+ "gran: %d done\n", dev_path(bus->dev),
+ resource2str(bridge), base, bridge->size, bridge->align,
+ bridge->gran);
+
+ /* For each child which is a bridge, __allocate_resources. */
+ for (dev = bus->children; dev; dev = dev->sibling) {
+ struct resource *child_bridge;
+
+ if (!dev->link_list)
+ continue;
+
+ /* Find the resources with matching type flags. */
+ for (child_bridge = dev->resource_list; child_bridge;
+ child_bridge = child_bridge->next) {
+ struct bus* link;
+
+ if (!(child_bridge->flags & IORESOURCE_BRIDGE) ||
+ (child_bridge->flags & type_mask) != type)
+ continue;
+
+ /*
+ * Split prefetchable memory if combined. Many domains
+ * use the same address space for prefetchable memory
+ * and non-prefetchable memory. Bridges below them need
+ * it separated. Add the PREFETCH flag to the type_mask
+ * and type.
+ */
+ link = dev->link_list;
+ while (link && link->link_num !=
+ IOINDEX_LINK(child_bridge->index))
+ link = link->next;
+ if (link == NULL)
+ printk(BIOS_ERR, "link %ld not found on %s\n",
+ IOINDEX_LINK(child_bridge->index),
+ dev_path(dev));
+
+ __allocate_resources(link, child_bridge,
+ type_mask | IORESOURCE_PREFETCH,
+ type | (child_bridge->flags &
+ IORESOURCE_PREFETCH));
+ }
+ }
+}
+
+static int resource_is(struct resource *res, u32 type)
+{
+ return (res->flags & IORESOURCE_TYPE_MASK) == type;
+}
+
+struct constraints {
+ struct resource io, mem;
+};
+
+static struct resource *resource_limit(struct constraints *limits,
+ struct resource *res)
+{
+ struct resource *lim = NULL;
+
+ /* MEM, or I/O - skip any others. */
+ if (resource_is(res, IORESOURCE_MEM))
+ lim = &limits->mem;
+ else if (resource_is(res, IORESOURCE_IO))
+ lim = &limits->io;
+
+ return lim;
+}
+
+static void constrain_resources(const struct device *dev,
+ struct constraints* limits)
+{
+ const struct device *child;
+ struct resource *res;
+ struct resource *lim;
+ struct bus *link;
+
+ /* Constrain limits based on the fixed resources of this device. */
+ for (res = dev->resource_list; res; res = res->next) {
+ if (!(res->flags & IORESOURCE_FIXED))
+ continue;
+ if (!res->size) {
+ /* It makes no sense to have 0-sized, fixed resources.*/
+ printk(BIOS_ERR, "skipping %s@%lx fixed resource, "
+ "size=0!\n", dev_path(dev), res->index);
+ continue;
+ }
+
+ lim = resource_limit(limits, res);
+ if (!lim)
+ continue;
+
+ /*
+ * Is it a fixed resource outside the current known region?
+ * If so, we don't have to consider it - it will be handled
+ * correctly and doesn't affect current region's limits.
+ */
+ if (((res->base + res->size -1) < lim->base)
+ || (res->base > lim->limit))
+ continue;
+
+ 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));
+
+ /*
+ * Choose to be above or below fixed resources. This check is
+ * signed so that "negative" amounts of space are handled
+ * correctly.
+ */
+ if ((signed long long)(lim->limit - (res->base + res->size -1))
+ > (signed long long)(res->base - lim->base))
+ lim->base = res->base + res->size;
+ else
+ lim->limit = res->base -1;
+ }
+
+ /* Descend into every enabled child and look for fixed resources. */
+ for (link = dev->link_list; link; link = link->next) {
+ for (child = link->children; child; child = child->sibling) {
+ if (child->enabled)
+ constrain_resources(child, limits);
+ }
+ }
+}
+
+static void avoid_fixed_resources(const struct device *dev)
+{
+ struct constraints limits;
+ struct resource *res;
+ struct resource *lim;
+
+ printk(BIOS_SPEW, "%s: %s\n", __func__, dev_path(dev));
+
+ /* Initialize constraints to maximum size. */
+ limits.io.base = 0;
+ limits.io.limit = 0xffffffffffffffffULL;
+ limits.mem.base = 0;
+ limits.mem.limit = 0xffffffffffffffffULL;
+
+ /* Constrain the limits to dev's initial resources. */
+ for (res = dev->resource_list; res; res = res->next) {
+ if ((res->flags & IORESOURCE_FIXED))
+ continue;
+ printk(BIOS_SPEW, "%s:@%s %02lx limit %08llx\n", __func__,
+ dev_path(dev), res->index, res->limit);
+
+ lim = resource_limit(&limits, res);
+ if (!lim)
+ continue;
+
+ if (res->base > lim->base)
+ lim->base = res->base;
+ if (res->limit < lim->limit)
+ lim->limit = res->limit;
+ }
+
+ /* Look through the tree for fixed resources and update the limits. */
+ constrain_resources(dev, &limits);
+
+ /* Update dev's resources with new limits. */
+ for (res = dev->resource_list; res; res = res->next) {
+ if ((res->flags & IORESOURCE_FIXED))
+ continue;
+
+ lim = resource_limit(&limits, res);
+ if (!lim)
+ continue;
+
+ /* Is the resource outside the limits? */
+ if (lim->base > res->base)
+ res->base = lim->base;
+ if (res->limit > lim->limit)
+ res->limit = lim->limit;
+
+ /* MEM resources need to start at the highest address manageable. */
+ if (res->flags & IORESOURCE_MEM)
+ res->base = resource_max(res);
+
+ printk(BIOS_SPEW, "%s:@%s %02lx base %08llx limit %08llx\n",
+ __func__, dev_path(dev), res->index, res->base, res->limit);
+ }
+}
+
+void allocate_resources(const struct device *root)
+{
+ struct resource *res;
+ const struct device *child;
+
+ /* Compute resources for all domains. */
+ for (child = root->link_list->children; child; child = child->sibling) {
+ if (!(child->path.type == DEVICE_PATH_DOMAIN))
+ continue;
+ post_log_path(child);
+ for (res = child->resource_list; res; res = res->next) {
+ if (res->flags & IORESOURCE_FIXED)
+ continue;
+ if (res->flags & IORESOURCE_MEM) {
+ compute_resources(child->link_list,
+ res, IORESOURCE_TYPE_MASK, IORESOURCE_MEM);
+ continue;
+ }
+ if (res->flags & IORESOURCE_IO) {
+ compute_resources(child->link_list,
+ res, IORESOURCE_TYPE_MASK, IORESOURCE_IO);
+ continue;
+ }
+ }
+ }
+
+ /* For all domains. */
+ for (child = root->link_list->children; child; child=child->sibling)
+ if (child->path.type == DEVICE_PATH_DOMAIN)
+ avoid_fixed_resources(child);
+
+ /* Store the computed resource allocations into device registers ... */
+ printk(BIOS_INFO, "Setting resources...\n");
+ for (child = root->link_list->children; child; child = child->sibling) {
+ if (!(child->path.type == DEVICE_PATH_DOMAIN))
+ continue;
+ post_log_path(child);
+ for (res = child->resource_list; res; res = res->next) {
+ if (res->flags & IORESOURCE_FIXED)
+ continue;
+ if (res->flags & IORESOURCE_MEM) {
+ __allocate_resources(child->link_list,
+ res, IORESOURCE_TYPE_MASK, IORESOURCE_MEM);
+ continue;
+ }
+ if (res->flags & IORESOURCE_IO) {
+ __allocate_resources(child->link_list,
+ res, IORESOURCE_TYPE_MASK, IORESOURCE_IO);
+ continue;
+ }
+ }
+ }
+}
diff --git a/src/include/device/resource.h b/src/include/device/resource.h
index 1d04e9a1c8..c97b01d22f 100644
--- a/src/include/device/resource.h
+++ b/src/include/device/resource.h
@@ -91,4 +91,24 @@ static inline void *res2mmio(struct resource *res, unsigned long offset,
return (void *)(uintptr_t)((res->base + offset) & ~mask);
}
+/*
+ * Pick largest resource on the bus using the given mask and type.
+ * Params:
+ * bus = Bus from which the resource needs to picked from.
+ * result_res = If NULL, there was no previous resource picked on this bus, else it points to
+ * the last picked resource.
+ * type_mask = Mask to be applied when searching for resource
+ * type = Expected type for the resource
+ *
+ * Returns:
+ * If resource is found, returns the device and sets result_rest to point to the resource. Else
+ * returns NULL.
+ */
+const struct device *largest_resource(struct bus *bus, struct resource **result_res,
+ unsigned long type_mask, unsigned long type);
+
+
+/* Compute and allocate resources. This is the main resource allocator entry point. */
+void allocate_resources(const struct device *root);
+
#endif /* DEVICE_RESOURCE_H */