blob: 222f1e9a47078e892be3820954ce65ca083bd649 [file] [log] [blame]
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -07001/* SPDX-License-Identifier: GPL-2.0-only */
2
3#include <console/console.h>
4#include <device/device.h>
5#include <memrange.h>
6#include <post.h>
7
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -07008static const char *resource2str(const struct resource *res)
9{
10 if (res->flags & IORESOURCE_IO)
11 return "io";
12 if (res->flags & IORESOURCE_PREFETCH)
13 return "prefmem";
14 if (res->flags & IORESOURCE_MEM)
15 return "mem";
16 return "undefined";
17}
18
19static bool dev_has_children(const struct device *dev)
20{
21 const struct bus *bus = dev->link_list;
22 return bus && bus->children;
23}
24
Furquan Shaikhc3568612020-05-16 15:18:23 -070025#define res_printk(depth, str, ...) printk(BIOS_DEBUG, "%*c"str, depth, ' ', __VA_ARGS__)
26
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -070027/*
Nico Huber9d7728a2020-05-23 18:00:10 +020028 * During pass 1, once all the requirements for downstream devices of a
29 * bridge are gathered, this function calculates the overall resource
30 * requirement for the bridge. It starts by picking the largest resource
31 * requirement downstream for the given resource type and works by
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -070032 * adding requirements in descending order.
33 *
Nico Huber9d7728a2020-05-23 18:00:10 +020034 * Additionally, it takes alignment and limits of the downstream devices
35 * into consideration and ensures that they get propagated to the bridge
36 * resource. This is required to guarantee that the upstream bridge/
37 * domain honors the limit and alignment requirements for this bridge
38 * based on the tightest constraints downstream.
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -070039 */
40static void update_bridge_resource(const struct device *bridge, struct resource *bridge_res,
Furquan Shaikhc3568612020-05-16 15:18:23 -070041 unsigned long type_match, int print_depth)
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -070042{
43 const struct device *child;
44 struct resource *child_res;
45 resource_t base;
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -070046 const unsigned long type_mask = IORESOURCE_TYPE_MASK | IORESOURCE_PREFETCH;
47 struct bus *bus = bridge->link_list;
48
49 child_res = NULL;
50
51 /*
Nico Huber9d7728a2020-05-23 18:00:10 +020052 * `base` keeps track of where the next allocation for child resources
53 * can take place from within the bridge resource window. Since the
54 * bridge resource window allocation is not performed yet, it can start
55 * at 0. Base gets updated every time a resource requirement is
56 * accounted for in the loop below. After scanning all these resources,
57 * base will indicate the total size requirement for the current bridge
58 * resource window.
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -070059 */
60 base = 0;
61
Furquan Shaikhc3568612020-05-16 15:18:23 -070062 res_printk(print_depth, "%s %s: size: %llx align: %d gran: %d limit: %llx\n",
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -070063 dev_path(bridge), resource2str(bridge_res), bridge_res->size,
64 bridge_res->align, bridge_res->gran, bridge_res->limit);
65
66 while ((child = largest_resource(bus, &child_res, type_mask, type_match))) {
67
68 /* Size 0 resources can be skipped. */
69 if (!child_res->size)
70 continue;
71
Nico Huberec7b3132020-05-23 18:20:47 +020072 /* Resources with 0 limit can't be assigned anything. */
73 if (!child_res->limit)
74 continue;
75
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -070076 /*
Nico Huber74169c12020-05-23 18:15:34 +020077 * Propagate the resource alignment to the bridge resource. The
78 * condition can only be true for the first (largest) resource. For all
Nico Huber9d7728a2020-05-23 18:00:10 +020079 * other children resources, alignment is taken care of by updating the
80 * base to round up as per the child resource alignment. It is
81 * guaranteed that pass 2 follows the exact same method of picking the
82 * resource for allocation using largest_resource(). Thus, as long as
Nico Huber74169c12020-05-23 18:15:34 +020083 * the alignment for the largest child resource is propagated up to the
84 * bridge resource, it can be guaranteed that the alignment for all
85 * resources is appropriately met.
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -070086 */
Nico Huber74169c12020-05-23 18:15:34 +020087 if (child_res->align > bridge_res->align)
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -070088 bridge_res->align = child_res->align;
89
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -070090 /*
Nico Huberec7b3132020-05-23 18:20:47 +020091 * Propagate the resource limit to the bridge resource. If a downstream
92 * device has stricter requirements w.r.t. limits for any resource, that
93 * constraint needs to be propagated back up to the downstream bridges
94 * of the domain. This guarantees that the resource allocation which
95 * starts at the domain level takes into account all these constraints
96 * thus working on a global view.
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -070097 */
Nico Huber38aafa32022-09-04 22:20:21 +020098 if (child_res->limit < bridge_res->limit)
99 bridge_res->limit = child_res->limit;
100
101 /*
102 * Propagate the downstream resource request to allocate above 4G
103 * boundary to upstream bridge resource. This ensures that during
104 * pass 2, the resource allocator at domain level has a global view
105 * of all the downstream device requirements and thus address space
106 * is allocated as per updated flags in the bridge resource.
107 *
108 * Since the bridge resource is a single window, all the downstream
109 * resources of this bridge resource will be allocated in space above
110 * the 4G boundary.
111 */
112 if (child_res->flags & IORESOURCE_ABOVE_4G)
113 bridge_res->flags |= IORESOURCE_ABOVE_4G;
Furquan Shaikh1bb05ef302020-05-15 17:33:52 -0700114
115 /*
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700116 * Alignment value of 0 means that the child resource has no alignment
117 * requirements and so the base value remains unchanged here.
118 */
Nico Huberb3277042020-05-23 18:08:50 +0200119 base = ALIGN_UP(base, POWER_OF_2(child_res->align));
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700120
Furquan Shaikhc3568612020-05-16 15:18:23 -0700121 res_printk(print_depth + 1, "%s %02lx * [0x%llx - 0x%llx] %s\n",
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700122 dev_path(child), child_res->index, base, base + child_res->size - 1,
123 resource2str(child_res));
124
125 base += child_res->size;
126 }
127
128 /*
Nico Huber9d7728a2020-05-23 18:00:10 +0200129 * After all downstream device resources are scanned, `base` represents
130 * the total size requirement for the current bridge resource window.
131 * This size needs to be rounded up to the granularity requirement of
132 * the bridge to ensure that the upstream bridge/domain allocates big
133 * enough window.
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700134 */
Nico Huberb3277042020-05-23 18:08:50 +0200135 bridge_res->size = ALIGN_UP(base, POWER_OF_2(bridge_res->gran));
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700136
Furquan Shaikhc3568612020-05-16 15:18:23 -0700137 res_printk(print_depth, "%s %s: size: %llx align: %d gran: %d limit: %llx done\n",
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700138 dev_path(bridge), resource2str(bridge_res), bridge_res->size,
139 bridge_res->align, bridge_res->gran, bridge_res->limit);
140}
141
142/*
Nico Huber9d7728a2020-05-23 18:00:10 +0200143 * During pass 1, at the bridge level, the resource allocator gathers
144 * requirements from downstream devices and updates its own resource
145 * windows for the provided resource type.
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700146 */
Furquan Shaikhc3568612020-05-16 15:18:23 -0700147static void compute_bridge_resources(const struct device *bridge, unsigned long type_match,
148 int print_depth)
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700149{
150 const struct device *child;
151 struct resource *res;
152 struct bus *bus = bridge->link_list;
153 const unsigned long type_mask = IORESOURCE_TYPE_MASK | IORESOURCE_PREFETCH;
154
155 for (res = bridge->resource_list; res; res = res->next) {
156 if (!(res->flags & IORESOURCE_BRIDGE))
157 continue;
158
159 if ((res->flags & type_mask) != type_match)
160 continue;
161
162 /*
163 * Ensure that the resource requirements for all downstream bridges are
164 * gathered before updating the window for current bridge resource.
165 */
166 for (child = bus->children; child; child = child->sibling) {
167 if (!dev_has_children(child))
168 continue;
Furquan Shaikhc3568612020-05-16 15:18:23 -0700169 compute_bridge_resources(child, type_match, print_depth + 1);
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700170 }
171
172 /*
173 * Update the window for current bridge resource now that all downstream
174 * requirements are gathered.
175 */
Furquan Shaikhc3568612020-05-16 15:18:23 -0700176 update_bridge_resource(bridge, res, type_match, print_depth);
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700177 }
178}
179
180/*
Nico Huber9d7728a2020-05-23 18:00:10 +0200181 * During pass 1, the resource allocator walks down the entire sub-tree
182 * of a domain. It gathers resource requirements for every downstream
183 * bridge by looking at the resource requests of its children. Thus, the
184 * requirement gathering begins at the leaf devices and is propagated
185 * back up to the downstream bridges of the domain.
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700186 *
Nico Huber9d7728a2020-05-23 18:00:10 +0200187 * At the domain level, it identifies every downstream bridge and walks
188 * down that bridge to gather requirements for each resource type i.e.
189 * i/o, mem and prefmem. Since bridges have separate windows for mem and
190 * prefmem, requirements for each need to be collected separately.
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700191 *
Nico Huber9d7728a2020-05-23 18:00:10 +0200192 * Domain resource windows are fixed ranges and hence requirement
193 * gathering does not result in any changes to these fixed ranges.
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700194 */
195static void compute_domain_resources(const struct device *domain)
196{
197 const struct device *child;
Furquan Shaikhc3568612020-05-16 15:18:23 -0700198 const int print_depth = 1;
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700199
200 if (domain->link_list == NULL)
201 return;
202
203 for (child = domain->link_list->children; child; child = child->sibling) {
204
205 /* Skip if this is not a bridge or has no children under it. */
206 if (!dev_has_children(child))
207 continue;
208
Furquan Shaikhc3568612020-05-16 15:18:23 -0700209 compute_bridge_resources(child, IORESOURCE_IO, print_depth);
210 compute_bridge_resources(child, IORESOURCE_MEM, print_depth);
211 compute_bridge_resources(child, IORESOURCE_MEM | IORESOURCE_PREFETCH,
212 print_depth);
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700213 }
214}
215
216static unsigned char get_alignment_by_resource_type(const struct resource *res)
217{
218 if (res->flags & IORESOURCE_MEM)
219 return 12; /* Page-aligned --> log2(4KiB) */
220 else if (res->flags & IORESOURCE_IO)
221 return 0; /* No special alignment required --> log2(1) */
222
223 die("Unexpected resource type: flags(%d)!\n", res->flags);
224}
225
Nico Huber38aafa32022-09-04 22:20:21 +0200226/*
227 * If the resource is NULL or if the resource is not assigned, then it
228 * cannot be used for allocation for downstream devices.
229 */
230static bool is_resource_invalid(const struct resource *res)
231{
232 return (res == NULL) || !(res->flags & IORESOURCE_ASSIGNED);
233}
234
235static void initialize_domain_io_resource_memranges(struct memranges *ranges,
236 const struct resource *res,
237 unsigned long memrange_type)
238{
239 memranges_insert(ranges, res->base, res->limit - res->base + 1, memrange_type);
240}
241
242static void initialize_domain_mem_resource_memranges(struct memranges *ranges,
243 const struct resource *res,
244 unsigned long memrange_type)
245{
246 resource_t res_base;
247 resource_t res_limit;
248
249 const resource_t limit_4g = 0xffffffff;
250
251 res_base = res->base;
252 res_limit = res->limit;
253
254 /*
255 * Split the resource into two separate ranges if it crosses the 4G
256 * boundary. Memrange type is set differently to ensure that memrange
257 * does not merge these two ranges. For the range above 4G boundary,
258 * given memrange type is ORed with IORESOURCE_ABOVE_4G.
259 */
260 if (res_base <= limit_4g) {
261
262 resource_t range_limit;
263
264 /* Clip the resource limit at 4G boundary if necessary. */
265 range_limit = MIN(res_limit, limit_4g);
266 memranges_insert(ranges, res_base, range_limit - res_base + 1, memrange_type);
267
268 /*
269 * If the resource lies completely below the 4G boundary, nothing more
270 * needs to be done.
271 */
272 if (res_limit <= limit_4g)
273 return;
274
275 /*
276 * If the resource window crosses the 4G boundary, then update res_base
277 * to add another entry for the range above the boundary.
278 */
279 res_base = limit_4g + 1;
280 }
281
282 if (res_base > res_limit)
283 return;
284
285 /*
286 * If resource lies completely above the 4G boundary or if the resource
287 * was clipped to add two separate ranges, the range above 4G boundary
288 * has the resource flag IORESOURCE_ABOVE_4G set. This allows domain to
289 * handle any downstream requests for resource allocation above 4G
290 * differently.
291 */
292 memranges_insert(ranges, res_base, res_limit - res_base + 1,
293 memrange_type | IORESOURCE_ABOVE_4G);
294}
295
296/*
297 * This function initializes memranges for domain device. If the
298 * resource crosses 4G boundary, then this function splits it into two
299 * ranges -- one for the window below 4G and the other for the window
300 * above 4G. The latter range has IORESOURCE_ABOVE_4G flag set to
301 * satisfy resource requests from downstream devices for allocations
302 * above 4G.
303 */
304static void initialize_domain_memranges(struct memranges *ranges, const struct resource *res,
305 unsigned long memrange_type)
306{
307 unsigned char align = get_alignment_by_resource_type(res);
308
309 memranges_init_empty_with_alignment(ranges, NULL, 0, align);
310
311 if (is_resource_invalid(res))
312 return;
313
314 if (res->flags & IORESOURCE_IO)
315 initialize_domain_io_resource_memranges(ranges, res, memrange_type);
316 else
317 initialize_domain_mem_resource_memranges(ranges, res, memrange_type);
318}
319
320/*
321 * This function initializes memranges for bridge device. Unlike domain,
322 * bridge does not need to care about resource window crossing 4G
323 * boundary. This is handled by the resource allocator at domain level
324 * to ensure that all downstream bridges are allocated space either
325 * above or below 4G boundary as per the state of IORESOURCE_ABOVE_4G
326 * for the respective bridge resource.
327 *
328 * So, this function creates a single range of the entire resource
329 * window available for the bridge resource. Thus all downstream
330 * resources of the bridge for the given resource type get allocated
331 * space from the same window. If there is any downstream resource of
332 * the bridge which requests allocation above 4G, then all other
333 * downstream resources of the same type under the bridge get allocated
334 * above 4G.
335 */
336static void initialize_bridge_memranges(struct memranges *ranges, const struct resource *res,
337 unsigned long memrange_type)
338{
339 unsigned char align = get_alignment_by_resource_type(res);
340
341 memranges_init_empty_with_alignment(ranges, NULL, 0, align);
342
343 if (is_resource_invalid(res))
344 return;
345
346 memranges_insert(ranges, res->base, res->limit - res->base + 1, memrange_type);
347}
348
Furquan Shaikhc3568612020-05-16 15:18:23 -0700349static void print_resource_ranges(const struct device *dev, const struct memranges *ranges)
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700350{
351 const struct range_entry *r;
352
Furquan Shaikhc3568612020-05-16 15:18:23 -0700353 printk(BIOS_INFO, " %s: Resource ranges:\n", dev_path(dev));
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700354
355 if (memranges_is_empty(ranges))
Furquan Shaikhc3568612020-05-16 15:18:23 -0700356 printk(BIOS_INFO, " * EMPTY!!\n");
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700357
358 memranges_each_entry(r, ranges) {
Furquan Shaikhc3568612020-05-16 15:18:23 -0700359 printk(BIOS_INFO, " * Base: %llx, Size: %llx, Tag: %lx\n",
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700360 range_entry_base(r), range_entry_size(r), range_entry_tag(r));
361 }
362}
363
364/*
Nico Huber9d7728a2020-05-23 18:00:10 +0200365 * This is where the actual allocation of resources happens during
366 * pass 2. Given the list of memory ranges corresponding to the
367 * resource of given type, it finds the biggest unallocated resource
368 * using the type mask on the downstream bus. This continues in a
369 * descending order until all resources of given type are allocated
370 * address space within the current resource window.
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700371 */
372static void allocate_child_resources(struct bus *bus, struct memranges *ranges,
373 unsigned long type_mask, unsigned long type_match)
374{
Nico Huber526c6422020-05-25 00:03:14 +0200375 const bool allocate_top_down =
376 bus->dev->path.type == DEVICE_PATH_DOMAIN &&
377 CONFIG(RESOURCE_ALLOCATION_TOP_DOWN);
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700378 struct resource *resource = NULL;
379 const struct device *dev;
380
381 while ((dev = largest_resource(bus, &resource, type_mask, type_match))) {
382
383 if (!resource->size)
384 continue;
385
Nico Huber38aafa32022-09-04 22:20:21 +0200386 if (memranges_steal(ranges, resource->limit, resource->size, resource->align,
387 type_match, &resource->base, allocate_top_down) == false) {
Furquan Shaikhc3568612020-05-16 15:18:23 -0700388 printk(BIOS_ERR, " ERROR: Resource didn't fit!!! ");
389 printk(BIOS_DEBUG, " %s %02lx * size: 0x%llx limit: %llx %s\n",
Nico Huber38aafa32022-09-04 22:20:21 +0200390 dev_path(dev), resource->index,
391 resource->size, resource->limit, resource2str(resource));
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700392 continue;
393 }
394
395 resource->limit = resource->base + resource->size - 1;
396 resource->flags |= IORESOURCE_ASSIGNED;
397
Furquan Shaikhc3568612020-05-16 15:18:23 -0700398 printk(BIOS_DEBUG, " %s %02lx * [0x%llx - 0x%llx] limit: %llx %s\n",
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700399 dev_path(dev), resource->index, resource->base,
400 resource->size ? resource->base + resource->size - 1 :
401 resource->base, resource->limit, resource2str(resource));
402 }
403}
404
405static void update_constraints(struct memranges *ranges, const struct device *dev,
406 const struct resource *res)
407{
408 if (!res->size)
409 return;
410
Furquan Shaikhc3568612020-05-16 15:18:23 -0700411 printk(BIOS_DEBUG, " %s: %s %02lx base %08llx limit %08llx %s (fixed)\n",
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700412 __func__, dev_path(dev), res->index, res->base,
413 res->base + res->size - 1, resource2str(res));
414
415 memranges_create_hole(ranges, res->base, res->size);
416}
417
418/*
Nico Huber9d7728a2020-05-23 18:00:10 +0200419 * Scan the entire tree to identify any fixed resources allocated by
420 * any device to ensure that the address map for domain resources are
421 * appropriately updated.
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700422 *
Nico Huber9d7728a2020-05-23 18:00:10 +0200423 * Domains can typically provide a memrange for entire address space.
424 * So, this function punches holes in the address space for all fixed
425 * resources that are already defined. Both I/O and normal memory
426 * resources are added as fixed. Both need to be removed from address
427 * space where dynamic resource allocations are sourced.
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700428 */
429static void avoid_fixed_resources(struct memranges *ranges, const struct device *dev,
430 unsigned long mask_match)
431{
432 const struct resource *res;
433 const struct device *child;
434 const struct bus *bus;
435
436 for (res = dev->resource_list; res != NULL; res = res->next) {
437 if ((res->flags & mask_match) != mask_match)
438 continue;
439 update_constraints(ranges, dev, res);
440 }
441
442 bus = dev->link_list;
443 if (bus == NULL)
444 return;
445
446 for (child = bus->children; child != NULL; child = child->sibling)
447 avoid_fixed_resources(ranges, child, mask_match);
448}
449
450static void constrain_domain_resources(const struct device *domain, struct memranges *ranges,
451 unsigned long type)
452{
453 unsigned long mask_match = type | IORESOURCE_FIXED;
454
455 if (type == IORESOURCE_IO) {
456 /*
Nico Huber9d7728a2020-05-23 18:00:10 +0200457 * Don't allow allocations in the VGA I/O range. PCI has special
458 * cases for that.
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700459 */
Furquan Shaikh563e6142020-05-26 12:04:35 -0700460 memranges_create_hole(ranges, 0x3b0, 0x3df - 0x3b0 + 1);
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700461
462 /*
Nico Huber9d7728a2020-05-23 18:00:10 +0200463 * Resource allocator no longer supports the legacy behavior where
464 * I/O resource allocation is guaranteed to avoid aliases over legacy
465 * PCI expansion card addresses.
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700466 */
467 }
468
469 avoid_fixed_resources(ranges, domain, mask_match);
470}
471
472/*
Nico Huber9d7728a2020-05-23 18:00:10 +0200473 * This function creates a list of memranges of given type using the
Nico Huber38aafa32022-09-04 22:20:21 +0200474 * resource that is provided. If the given resource is NULL or if the
475 * resource window size is 0, then it creates an empty list. This
Nico Huber9d7728a2020-05-23 18:00:10 +0200476 * results in resource allocation for that resource type failing for
477 * all downstream devices since there is nothing to allocate from.
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700478 *
Nico Huber9d7728a2020-05-23 18:00:10 +0200479 * In case of domain, it applies additional constraints to ensure that
480 * the memranges do not overlap any of the fixed resources under that
481 * domain. Domain typically seems to provide memrange for entire address
482 * space. Thus, it is up to the chipset to add DRAM and all other
483 * windows which cannot be used for resource allocation as fixed
484 * resources.
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700485 */
486static void setup_resource_ranges(const struct device *dev, const struct resource *res,
487 unsigned long type, struct memranges *ranges)
488{
Furquan Shaikhc0dc1e12020-05-16 13:54:37 -0700489 printk(BIOS_DEBUG, "%s %s: base: %llx size: %llx align: %d gran: %d limit: %llx\n",
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700490 dev_path(dev), resource2str(res), res->base, res->size, res->align,
491 res->gran, res->limit);
492
Nico Huber38aafa32022-09-04 22:20:21 +0200493 if (dev->path.type == DEVICE_PATH_DOMAIN) {
494 initialize_domain_memranges(ranges, res, type);
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700495 constrain_domain_resources(dev, ranges, type);
Nico Huber38aafa32022-09-04 22:20:21 +0200496 } else {
497 initialize_bridge_memranges(ranges, res, type);
498 }
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700499
Furquan Shaikhc3568612020-05-16 15:18:23 -0700500 print_resource_ranges(dev, ranges);
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700501}
502
503static void cleanup_resource_ranges(const struct device *dev, struct memranges *ranges,
504 const struct resource *res)
505{
506 memranges_teardown(ranges);
Furquan Shaikhc0dc1e12020-05-16 13:54:37 -0700507 printk(BIOS_DEBUG, "%s %s: base: %llx size: %llx align: %d gran: %d limit: %llx done\n",
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700508 dev_path(dev), resource2str(res), res->base, res->size, res->align,
509 res->gran, res->limit);
510}
511
512/*
Nico Huber9d7728a2020-05-23 18:00:10 +0200513 * Pass 2 of the resource allocator at the bridge level loops through
514 * all the resources for the bridge and generates a list of memory
515 * ranges similar to that at the domain level. However, there is no need
516 * to apply any additional constraints since the window allocated to the
517 * bridge is guaranteed to be non-overlapping by the allocator at domain
518 * level.
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700519 *
Nico Huber9d7728a2020-05-23 18:00:10 +0200520 * Allocation at the bridge level works the same as at domain level
521 * (starts with the biggest resource requirement from downstream devices
522 * and continues in descending order). One major difference at the
523 * bridge level is that it considers prefmem resources separately from
524 * mem resources.
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700525 *
Nico Huber9d7728a2020-05-23 18:00:10 +0200526 * Once allocation at the current bridge is complete, resource allocator
527 * continues walking down the downstream bridges until it hits the leaf
528 * devices.
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700529 */
530static void allocate_bridge_resources(const struct device *bridge)
531{
532 struct memranges ranges;
533 const struct resource *res;
534 struct bus *bus = bridge->link_list;
535 unsigned long type_match;
536 struct device *child;
537 const unsigned long type_mask = IORESOURCE_TYPE_MASK | IORESOURCE_PREFETCH;
538
539 for (res = bridge->resource_list; res; res = res->next) {
540 if (!res->size)
541 continue;
542
543 if (!(res->flags & IORESOURCE_BRIDGE))
544 continue;
545
546 type_match = res->flags & type_mask;
547
548 setup_resource_ranges(bridge, res, type_match, &ranges);
549 allocate_child_resources(bus, &ranges, type_mask, type_match);
550 cleanup_resource_ranges(bridge, &ranges, res);
551 }
552
553 for (child = bus->children; child; child = child->sibling) {
554 if (!dev_has_children(child))
555 continue;
556
557 allocate_bridge_resources(child);
558 }
559}
560
561static const struct resource *find_domain_resource(const struct device *domain,
562 unsigned long type)
563{
564 const struct resource *res;
565
566 for (res = domain->resource_list; res; res = res->next) {
567 if (res->flags & IORESOURCE_FIXED)
568 continue;
569
570 if ((res->flags & IORESOURCE_TYPE_MASK) == type)
571 return res;
572 }
573
574 return NULL;
575}
576
577/*
Nico Huber9d7728a2020-05-23 18:00:10 +0200578 * Pass 2 of resource allocator begins at the domain level. Every domain
579 * has two types of resources - io and mem. For each of these resources,
580 * this function creates a list of memory ranges that can be used for
581 * downstream resource allocation. This list is constrained to remove
582 * any fixed resources in the domain sub-tree of the given resource
583 * type. It then uses the memory ranges to apply best fit on the
584 * resource requirements of the downstream devices.
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700585 *
Nico Huber9d7728a2020-05-23 18:00:10 +0200586 * Once resources are allocated to all downstream devices of the domain,
587 * it walks down each downstream bridge to continue the same process
588 * until resources are allocated to all devices under the domain.
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700589 */
590static void allocate_domain_resources(const struct device *domain)
591{
592 struct memranges ranges;
593 struct device *child;
594 const struct resource *res;
595
596 /* Resource type I/O */
597 res = find_domain_resource(domain, IORESOURCE_IO);
598 if (res) {
599 setup_resource_ranges(domain, res, IORESOURCE_IO, &ranges);
600 allocate_child_resources(domain->link_list, &ranges, IORESOURCE_TYPE_MASK,
601 IORESOURCE_IO);
602 cleanup_resource_ranges(domain, &ranges, res);
603 }
604
605 /*
606 * Resource type Mem:
Nico Huber9d7728a2020-05-23 18:00:10 +0200607 * Domain does not distinguish between mem and prefmem resources. Thus,
608 * the resource allocation at domain level considers mem and prefmem
609 * together when finding the best fit based on the biggest resource
610 * requirement.
Nico Huber38aafa32022-09-04 22:20:21 +0200611 *
612 * However, resource requests for allocation above 4G boundary need to
613 * be handled separately if the domain resource window crosses this
614 * boundary. There is a single window for resource of type
615 * IORESOURCE_MEM. When creating memranges, this resource is split into
616 * two separate ranges -- one for the window below 4G boundary and other
617 * for the window above 4G boundary (with IORESOURCE_ABOVE_4G flag set).
618 * Thus, when allocating child resources, requests for below and above
619 * the 4G boundary are handled separately by setting the type_mask and
620 * type_match to allocate_child_resources() accordingly.
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700621 */
622 res = find_domain_resource(domain, IORESOURCE_MEM);
623 if (res) {
624 setup_resource_ranges(domain, res, IORESOURCE_MEM, &ranges);
Furquan Shaikh1bb05ef302020-05-15 17:33:52 -0700625 allocate_child_resources(domain->link_list, &ranges,
Nico Huber38aafa32022-09-04 22:20:21 +0200626 IORESOURCE_TYPE_MASK | IORESOURCE_ABOVE_4G,
627 IORESOURCE_MEM);
628 allocate_child_resources(domain->link_list, &ranges,
629 IORESOURCE_TYPE_MASK | IORESOURCE_ABOVE_4G,
630 IORESOURCE_MEM | IORESOURCE_ABOVE_4G);
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700631 cleanup_resource_ranges(domain, &ranges, res);
632 }
633
634 for (child = domain->link_list->children; child; child = child->sibling) {
635 if (!dev_has_children(child))
636 continue;
637
638 /* Continue allocation for all downstream bridges. */
639 allocate_bridge_resources(child);
640 }
641}
642
643/*
Nico Huber9d7728a2020-05-23 18:00:10 +0200644 * This function forms the guts of the resource allocator. It walks
645 * through the entire device tree for each domain two times.
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700646 *
Nico Huber9d7728a2020-05-23 18:00:10 +0200647 * Every domain has a fixed set of ranges. These ranges cannot be
648 * relaxed based on the requirements of the downstream devices. They
649 * represent the available windows from which resources can be allocated
650 * to the different devices under the domain.
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700651 *
Nico Huber9d7728a2020-05-23 18:00:10 +0200652 * In order to identify the requirements of downstream devices, resource
653 * allocator walks in a DFS fashion. It gathers the requirements from
654 * leaf devices and propagates those back up to their upstream bridges
655 * until the requirements for all the downstream devices of the domain
656 * are gathered. This is referred to as pass 1 of the resource allocator.
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700657 *
Nico Huber9d7728a2020-05-23 18:00:10 +0200658 * Once the requirements for all the devices under the domain are
659 * gathered, the resource allocator walks a second time to allocate
660 * resources to downstream devices as per the requirements. It always
661 * picks the biggest resource request as per the type (i/o and mem) to
662 * allocate space from its fixed window to the immediate downstream
663 * device of the domain. In order to accomplish best fit for the
664 * resources, a list of ranges is maintained by each resource type (i/o
665 * and mem). At the domain level we don't differentiate between mem and
666 * prefmem. Since they are allocated space from the same window, the
667 * resource allocator at the domain level ensures that the biggest
668 * requirement is selected independent of the prefetch type. Once the
669 * resource allocation for all immediate downstream devices is complete
670 * at the domain level, the resource allocator walks down the subtree
671 * for each downstream bridge to continue the allocation process at the
672 * bridge level. Since bridges have separate windows for i/o, mem and
673 * prefmem, best fit algorithm at bridge level looks for the biggest
674 * requirement considering prefmem resources separately from non-prefmem
675 * resources. This continues until resource allocation is performed for
676 * all downstream bridges in the domain sub-tree. This is referred to as
677 * pass 2 of the resource allocator.
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700678 *
679 * Some rules that are followed by the resource allocator:
Nico Huber9d7728a2020-05-23 18:00:10 +0200680 * - Allocate resource locations for every device as long as
681 * the requirements can be satisfied.
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700682 * - Don't overlap with resources in fixed locations.
Nico Huber9d7728a2020-05-23 18:00:10 +0200683 * - Don't overlap and follow the rules of bridges -- downstream
684 * devices of bridges should use parts of the address space
685 * allocated to the bridge.
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700686 */
687void allocate_resources(const struct device *root)
688{
689 const struct device *child;
690
691 if ((root == NULL) || (root->link_list == NULL))
692 return;
693
694 for (child = root->link_list->children; child; child = child->sibling) {
695
696 if (child->path.type != DEVICE_PATH_DOMAIN)
697 continue;
698
699 post_log_path(child);
700
701 /* Pass 1 - Gather requirements. */
Paul Menzel2efcafa2021-07-02 17:39:45 +0200702 printk(BIOS_INFO, "=== Resource allocator: %s - Pass 1 (gathering requirements) ===\n",
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700703 dev_path(child));
704 compute_domain_resources(child);
705
706 /* Pass 2 - Allocate resources as per gathered requirements. */
Furquan Shaikhc3568612020-05-16 15:18:23 -0700707 printk(BIOS_INFO, "=== Resource allocator: %s - Pass 2 (allocating resources) ===\n",
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700708 dev_path(child));
709 allocate_domain_resources(child);
Furquan Shaikhc3568612020-05-16 15:18:23 -0700710
711 printk(BIOS_INFO, "=== Resource allocator: %s - resource allocation complete ===\n",
712 dev_path(child));
Furquan Shaikhf4bc9eb2020-05-15 16:04:28 -0700713 }
714}