Change in coreboot[master]: device: Move resource allocation into a separate compilation unit - coreboot-gerrit

15 May 2020

Furquan Shaikh has uploaded this change for review. ( https://review.coreboot.org/c/coreboot/+/41442 )
Change subject: device: Move resource allocation into a separate compilation unit
......................................................................
device: Move resource allocation into a separate compilation unit
This change moves the resource alllocator functions out of device.c
and into two separate files:
resource_allocator_v3.c: This is the old implementation of
resource allocator that uses a single window for resource
allocation. It is required to support some AMD chipsets that do not
provide an accurate map of allocated resources by the time the
allocator runs. They work fine with the old allocator since it
restricts itself to allocations in a single window at the top of the
4G space.
resource_allocator_common.c: This file contains the functions that can
be shared by the old and new resource allocator.
Entry point into the resource allocation is allocate_resources() which
can be implemented by both old and new allocators. This change also
adds a Kconfig option RESOURCE_ALLOCATOR_V3 which enables the old
resource allocator. This config option is enabled by default
currently, but in the following CLs this will be enbaled only for the
broken boards.
Change-Id: I2f5440cf83c6e9e15a5f22e79cc3c66aa2cec4c0
Signed-off-by: Furquan Shaikh furquan@google.com
---
M src/device/Kconfig
M src/device/Makefile.inc
M src/device/device.c
A src/device/resource_allocator_common.c
A src/device/resource_allocator_v3.c
M src/include/device/resource.h
6 files changed, 638 insertions(+), 592 deletions(-)
git pull ssh://review.coreboot.org:29418/coreboot refs/changes/42/41442/1

diff --git a/src/device/Kconfig b/src/device/Kconfig
index 2976a61..bfa4759 100644
--- a/src/device/Kconfig
+++ b/src/device/Kconfig
@@ -794,4 +794,11 @@
      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 966ca0d..9bbab37 100644
--- a/src/device/Makefile.inc
+++ b/src/device/Makefile.inc
@@ -58,3 +58,6 @@
 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 e4b5f12..c54a345 100644
--- a/src/device/device.c
+++ b/src/device/device.c
@@ -146,33 +146,6 @@
 }
/**
- * 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 @@
           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_configure(void)
 {
-	struct resource *res;
    const struct device *root;
-	const struct device *child;
set_vga_bridge_bits();
@@ -1020,53 +474,8 @@
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;
-			}
-		}
-	}
+	allocate_resources(root);
-	/* 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;
-			}
-		}
-	}
    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 0000000..202318b
--- /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 0000000..4eeb240
--- /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 1d04e9a..c97b01d 100644
--- a/src/include/device/resource.h
+++ b/src/include/device/resource.h
@@ -91,4 +91,24 @@
    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 */
-- 
To view, visit https://review.coreboot.org/c/coreboot/+/41442
To unsubscribe, or for help writing mail filters, visit https://review.coreboot.org/settings

Gerrit-Project: coreboot
Gerrit-Branch: master
Gerrit-Change-Id: I2f5440cf83c6e9e15a5f22e79cc3c66aa2cec4c0
Gerrit-Change-Number: 41442
Gerrit-PatchSet: 1
Gerrit-Owner: Furquan Shaikh furquan@google.com
Gerrit-MessageType: newchange



    