summaryrefslogtreecommitdiff
path: root/src/device/resource_allocator_v4.c
blob: b65fc8bf37f101d73c7cd1b92e4e02924a052cac (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
/* SPDX-License-Identifier: GPL-2.0-only */

#include <console/console.h>
#include <device/device.h>
#include <memrange.h>
#include <post.h>

/**
 * Round a number up to an alignment.
 *
 * @param val The starting value.
 * @param pow Alignment as a power of two.
 * @return Rounded up number.
 */
static resource_t round(resource_t val, unsigned long pow)
{
	return ALIGN_UP(val, POWER_OF_2(pow));
}

static const char *resource2str(const struct resource *res)
{
	if (res->flags & IORESOURCE_IO)
		return "io";
	if (res->flags & IORESOURCE_PREFETCH)
		return "prefmem";
	if (res->flags & IORESOURCE_MEM)
		return "mem";
	return "undefined";
}

static bool dev_has_children(const struct device *dev)
{
	const struct bus *bus = dev->link_list;
	return bus && bus->children;
}

/*
 * During pass 1, once all the requirements for downstream devices of a bridge are gathered,
 * this function calculates the overall resource requirement for the bridge. It starts by
 * picking the largest resource requirement downstream for the given resource type and works by
 * adding requirements in descending order.
 *
 * Additionally, it takes alignment and limits of the downstream devices into consideration and
 * ensures that they get propagated to the bridge resource. This is required to guarantee that
 * the upstream bridge/domain honors the limit and alignment requirements for this bridge based
 * on the tightest constraints downstream.
 */
static void update_bridge_resource(const struct device *bridge, struct resource *bridge_res,
				   unsigned long type_match)
{
	const struct device *child;
	struct resource *child_res;
	resource_t base;
	bool first_child_res = true;
	const unsigned long type_mask = IORESOURCE_TYPE_MASK | IORESOURCE_PREFETCH;
	struct bus *bus = bridge->link_list;

	child_res = NULL;

	/*
	 * `base` keeps track of where the next allocation for child resource can take place
	 * from within the bridge resource window. Since the bridge resource window allocation
	 * is not performed yet, it can start at 0. Base gets updated every time a resource
	 * requirement is accounted for in the loop below. After scanning all these resources,
	 * base will indicate the total size requirement for the current bridge resource
	 * window.
	 */
	base = 0;

	printk(BIOS_SPEW, "%s %s: size: %llx align: %d gran: %d limit: %llx\n",
	       dev_path(bridge), resource2str(bridge_res), bridge_res->size,
	       bridge_res->align, bridge_res->gran, bridge_res->limit);

	while ((child = largest_resource(bus, &child_res, type_mask, type_match))) {

		/* Size 0 resources can be skipped. */
		if (!child_res->size)
			continue;

		/*
		 * Propagate the resource alignment to the bridge resource if this is the first
		 * child resource with non-zero size being considered. For all other children
		 * resources, alignment is taken care of by updating the base to round up as per
		 * the child resource alignment. It is guaranteed that pass 2 follows the exact
		 * same method of picking the resource for allocation using
		 * largest_resource(). Thus, as long as the alignment for first child resource
		 * is propagated up to the bridge resource, it can be guaranteed that the
		 * alignment for all resources is appropriately met.
		 */
		if (first_child_res && (child_res->align > bridge_res->align))
			bridge_res->align = child_res->align;

		first_child_res = false;

		/*
		 * Propagate the resource limit to the bridge resource only if child resource
		 * limit is non-zero. If a downstream device has stricter requirements
		 * w.r.t. limits for any resource, that constraint needs to be propagated back
		 * up to the downstream bridges of the domain. This guarantees that the resource
		 * allocation which starts at the domain level takes into account all these
		 * constraints thus working on a global view.
		 */
		if (child_res->limit && (child_res->limit < bridge_res->limit))
			bridge_res->limit = child_res->limit;

		/*
		 * Alignment value of 0 means that the child resource has no alignment
		 * requirements and so the base value remains unchanged here.
		 */
		base = round(base, child_res->align);

		printk(BIOS_SPEW, "%s %02lx *  [0x%llx - 0x%llx] %s\n",
		       dev_path(child), child_res->index, base, base + child_res->size - 1,
		       resource2str(child_res));

		base += child_res->size;
	}

	/*
	 * After all downstream device resources are scanned, `base` represents the total size
	 * requirement for the current bridge resource window. This size needs to be rounded up
	 * to the granularity requirement of the bridge to ensure that the upstream
	 * bridge/domain allocates big enough window.
	 */
	bridge_res->size = round(base, bridge_res->gran);

	printk(BIOS_SPEW, "%s %s: size: %llx align: %d gran: %d limit: %llx done\n",
	       dev_path(bridge), resource2str(bridge_res), bridge_res->size,
	       bridge_res->align, bridge_res->gran, bridge_res->limit);
}

/*
 * During pass 1, resource allocator at bridge level gathers requirements from downstream
 * devices and updates its own resource windows for the provided resource type.
 */
static void compute_bridge_resources(const struct device *bridge, unsigned long type_match)
{
	const struct device *child;
	struct resource *res;
	struct bus *bus = bridge->link_list;
	const unsigned long type_mask = IORESOURCE_TYPE_MASK | IORESOURCE_PREFETCH;

	for (res = bridge->resource_list; res; res = res->next) {
		if (!(res->flags & IORESOURCE_BRIDGE))
			continue;

		if ((res->flags & type_mask) != type_match)
			continue;

		/*
		 * Ensure that the resource requirements for all downstream bridges are
		 * gathered before updating the window for current bridge resource.
		 */
		for (child = bus->children; child; child = child->sibling) {
			if (!dev_has_children(child))
				continue;
			compute_bridge_resources(child, type_match);
		}

		/*
		 * Update the window for current bridge resource now that all downstream
		 * requirements are gathered.
		 */
		update_bridge_resource(bridge, res, type_match);
	}
}

/*
 * During pass 1, resource allocator walks down the entire sub-tree of a domain. It gathers
 * resource requirements for every downstream bridge by looking at the resource requests of its
 * children. Thus, the requirement gathering begins at the leaf devices and is propagated back
 * up to the downstream bridges of the domain.
 *
 * At domain level, it identifies every downstream bridge and walks down that bridge to gather
 * requirements for each resource type i.e. i/o, mem and prefmem. Since bridges have separate
 * windows for mem and prefmem, requirements for each need to be collected separately.
 *
 * Domain resource windows are fixed ranges and hence requirement gathering does not result in
 * any changes to these fixed ranges.
 */
static void compute_domain_resources(const struct device *domain)
{
	const struct device *child;

	if (domain->link_list == NULL)
		return;

	for (child = domain->link_list->children; child; child = child->sibling) {

		/* Skip if this is not a bridge or has no children under it. */
		if (!dev_has_children(child))
			continue;

		compute_bridge_resources(child, IORESOURCE_IO);
		compute_bridge_resources(child, IORESOURCE_MEM);
		compute_bridge_resources(child, IORESOURCE_MEM | IORESOURCE_PREFETCH);
	}
}

static unsigned char get_alignment_by_resource_type(const struct resource *res)
{
	if (res->flags & IORESOURCE_MEM)
		return 12;  /* Page-aligned --> log2(4KiB) */
	else if (res->flags & IORESOURCE_IO)
		return 0;   /* No special alignment required --> log2(1) */

	die("Unexpected resource type: flags(%d)!\n", res->flags);
}

static void initialize_memranges(struct memranges *ranges, const struct resource *res,
				 unsigned long memrange_type)
{
	resource_t res_base;
	resource_t res_limit;
	unsigned char align = get_alignment_by_resource_type(res);

	memranges_init_empty_with_alignment(ranges, NULL, 0, align);

	if ((res == NULL) || !(res->flags & IORESOURCE_ASSIGNED))
		return;

	res_base = res->base;
	res_limit = res->limit;

	memranges_insert(ranges, res_base, res_limit - res_base + 1, memrange_type);
}

static void print_resource_ranges(const struct memranges *ranges)
{
	const struct range_entry *r;

	printk(BIOS_INFO, "Resource ranges:\n");

	if (memranges_is_empty(ranges))
		printk(BIOS_INFO, "EMPTY!!\n");

	memranges_each_entry(r, ranges) {
		printk(BIOS_INFO, "Base: %llx, Size: %llx, Tag: %lx\n",
		       range_entry_base(r), range_entry_size(r), range_entry_tag(r));
	}
}

/*
 * This is where the actual allocation of resources happens during pass 2. Given the list of
 * memory ranges corresponding to the resource of given type, it finds the biggest unallocated
 * resource using the type mask on the downstream bus. This continues in a descending
 * order until all resources of given type are allocated address space within the current
 * resource window.
 */
static void allocate_child_resources(struct bus *bus, struct memranges *ranges,
				     unsigned long type_mask, unsigned long type_match)
{
	struct resource *resource = NULL;
	const struct device *dev;

	while ((dev = largest_resource(bus, &resource, type_mask, type_match))) {

		if (!resource->size)
			continue;

		if (memranges_steal(ranges, resource->limit, resource->size, resource->align,
				    type_match, &resource->base) == false) {
			printk(BIOS_ERR, "ERROR: Resource didn't fit!!! ");
			printk(BIOS_SPEW, "%s %02lx *  size: 0x%llx limit: %llx %s\n",
			       dev_path(dev), resource->index,
			       resource->size, resource->limit, resource2str(resource));
			continue;
		}

		resource->limit = resource->base + resource->size - 1;
		resource->flags |= IORESOURCE_ASSIGNED;

		printk(BIOS_SPEW, "%s %02lx *  [0x%llx - 0x%llx] limit: %llx %s\n",
		       dev_path(dev), resource->index, resource->base,
		       resource->size ? resource->base + resource->size - 1 :
		       resource->base, resource->limit, resource2str(resource));
	}
}

static void update_constraints(struct memranges *ranges, const struct device *dev,
			      const struct resource *res)
{
	if (!res->size)
		return;

	printk(BIOS_SPEW, "%s: %s %02lx base %08llx limit %08llx %s (fixed)\n",
	       __func__, dev_path(dev), res->index, res->base,
	       res->base + res->size - 1, resource2str(res));

	memranges_create_hole(ranges, res->base, res->size);
}

/*
 * Scan the entire tree to identify any fixed resources allocated by any device to
 * ensure that the address map for domain resources are appropriately updated.
 *
 * Domains can typically provide memrange for entire address space. So, this function
 * punches holes in the address space for all fixed resources that are already
 * defined. Both IO and normal memory resources are added as fixed. Both need to be
 * removed from address space where dynamic resource allocations are sourced.
 */
static void avoid_fixed_resources(struct memranges *ranges, const struct device *dev,
				  unsigned long mask_match)
{
	const struct resource *res;
	const struct device *child;
	const struct bus *bus;

	for (res = dev->resource_list; res != NULL; res = res->next) {
		if ((res->flags & mask_match) != mask_match)
			continue;
		update_constraints(ranges, dev, res);
	}

	bus = dev->link_list;
	if (bus == NULL)
		return;

	for (child = bus->children; child != NULL; child = child->sibling)
		avoid_fixed_resources(ranges, child, mask_match);
}

static void constrain_domain_resources(const struct device *domain, struct memranges *ranges,
				       unsigned long type)
{
	unsigned long mask_match = type | IORESOURCE_FIXED;

	if (type == IORESOURCE_IO) {
		/*
		 * Don't allow allocations in the VGA I/O range. PCI has special cases for
		 * that.
		 */
		memranges_create_hole(ranges, 0x3b0, 0x3df - 0x3b0 + 1);

		/*
		 * Resource allocator no longer supports the legacy behavior where I/O resource
		 * allocation is guaranteed to avoid aliases over legacy PCI expansion card
		 * addresses.
		 */
	}

	avoid_fixed_resources(ranges, domain, mask_match);
}

/*
 * This function creates a list of memranges of given type using the resource that is
 * provided. If the given resource is NULL or if the resource window size is 0, then it creates
 * an empty list. This results in resource allocation for that resource type failing for all
 * downstream devices since there is nothing to allocate from.
 *
 * In case of domain, it applies additional constraints to ensure that the memranges do not
 * overlap any of the fixed resources under that domain. Domain typically seems to provide
 * memrange for entire address space. Thus, it is up to the chipset to add DRAM and all other
 * windows which cannot be used for resource allocation as fixed resources.
 */
static void setup_resource_ranges(const struct device *dev, const struct resource *res,
				  unsigned long type, struct memranges *ranges)
{
	printk(BIOS_SPEW, "%s %s: base: %llx size: %llx align: %d gran: %d limit: %llx\n",
	       dev_path(dev), resource2str(res), res->base, res->size, res->align,
	       res->gran, res->limit);

	initialize_memranges(ranges, res, type);

	if (dev->path.type == DEVICE_PATH_DOMAIN)
		constrain_domain_resources(dev, ranges, type);

	print_resource_ranges(ranges);
}

static void cleanup_resource_ranges(const struct device *dev, struct memranges *ranges,
				    const struct resource *res)
{
	memranges_teardown(ranges);
	printk(BIOS_SPEW, "%s %s: base: %llx size: %llx align: %d gran: %d limit: %llx done\n",
	       dev_path(dev), resource2str(res), res->base, res->size, res->align,
	       res->gran, res->limit);
}

/*
 * Pass 2 of resource allocator at the bridge level loops through all the resources for the
 * bridge and generates a list of memory ranges similar to that at the domain level. However,
 * there is no need to apply any additional constraints since the window allocated to the bridge
 * is guaranteed to be non-overlapping by the allocator at domain level.
 *
 * Allocation at the bridge level works the same as at domain level (starts with the biggest
 * resource requirement from downstream devices and continues in descending order). One major
 * difference at the bridge level is that it considers prefmem resources separately from mem
 * resources.
 *
 * Once allocation at the current bridge is complete, resource allocator continues walking down
 * the downstream bridges until it hits the leaf devices.
 */
static void allocate_bridge_resources(const struct device *bridge)
{
	struct memranges ranges;
	const struct resource *res;
	struct bus *bus = bridge->link_list;
	unsigned long type_match;
	struct device *child;
	const unsigned long type_mask = IORESOURCE_TYPE_MASK | IORESOURCE_PREFETCH;

	for (res = bridge->resource_list; res; res = res->next) {
		if (!res->size)
			continue;

		if (!(res->flags & IORESOURCE_BRIDGE))
			continue;

		type_match = res->flags & type_mask;

		setup_resource_ranges(bridge, res, type_match, &ranges);
		allocate_child_resources(bus, &ranges, type_mask, type_match);
		cleanup_resource_ranges(bridge, &ranges, res);
	}

	for (child = bus->children; child; child = child->sibling) {
		if (!dev_has_children(child))
			continue;

		allocate_bridge_resources(child);
	}
}

static const struct resource *find_domain_resource(const struct device *domain,
						   unsigned long type)
{
	const struct resource *res;

	for (res = domain->resource_list; res; res = res->next) {
		if (res->flags & IORESOURCE_FIXED)
			continue;

		if ((res->flags & IORESOURCE_TYPE_MASK) == type)
			return res;
	}

	return NULL;
}

/*
 * Pass 2 of resource allocator begins at the domain level. Every domain has two types of
 * resources - io and mem. For each of these resources, this function creates a list of memory
 * ranges that can be used for downstream resource allocation. This list is constrained to
 * remove any fixed resources in the domain sub-tree of the given resource type. It then uses
 * the memory ranges to apply best fit on the resource requirements of the downstream devices.
 *
 * Once resources are allocated to all downstream devices of the domain, it walks down each
 * downstream bridge to continue the same process until resources are allocated to all devices
 * under the domain.
 */
static void allocate_domain_resources(const struct device *domain)
{
	struct memranges ranges;
	struct device *child;
	const struct resource *res;

	/* Resource type I/O */
	res = find_domain_resource(domain, IORESOURCE_IO);
	if (res) {
		setup_resource_ranges(domain, res, IORESOURCE_IO, &ranges);
		allocate_child_resources(domain->link_list, &ranges, IORESOURCE_TYPE_MASK,
					 IORESOURCE_IO);
		cleanup_resource_ranges(domain, &ranges, res);
	}

	/*
	 * Resource type Mem:
	 * Domain does not distinguish between mem and prefmem resources. Thus, the resource
	 * allocation at domain level considers mem and prefmem together when finding the best
	 * fit based on the biggest resource requirement.
	 */
	res = find_domain_resource(domain, IORESOURCE_MEM);
	if (res) {
		setup_resource_ranges(domain, res, IORESOURCE_MEM, &ranges);
		allocate_child_resources(domain->link_list, &ranges, IORESOURCE_TYPE_MASK,
					 IORESOURCE_MEM);
		cleanup_resource_ranges(domain, &ranges, res);
	}

	for (child = domain->link_list->children; child; child = child->sibling) {
		if (!dev_has_children(child))
			continue;

		/* Continue allocation for all downstream bridges. */
		allocate_bridge_resources(child);
	}
}

/*
 * This function forms the guts of the resource allocator. It walks through the entire device
 * tree for each domain two times.
 *
 * Every domain has a fixed set of ranges. These ranges cannot be relaxed based on the
 * requirements of the downstream devices. They represent the available windows from which
 * resources can be allocated to the different devices under the domain.
 *
 * In order to identify the requirements of downstream devices, resource allocator walks in a
 * DFS fashion. It gathers the requirements from leaf devices and propagates those back up
 * to their upstream bridges until the requirements for all the downstream devices of the domain
 * are gathered. This is referred to as pass 1 of resource allocator.
 *
 * Once the requirements for all the devices under the domain are gathered, resource allocator
 * walks a second time to allocate resources to downstream devices as per the
 * requirements. It always picks the biggest resource request as per the type (i/o and mem) to
 * allocate space from its fixed window to the immediate downstream device of the domain. In
 * order to accomplish best fit for the resources, a list of ranges is maintained by each
 * resource type (i/o and mem). Domain does not differentiate between mem and prefmem. Since
 * they are allocated space from the same window, the resource allocator at the domain level
 * ensures that the biggest requirement is selected indepedent of the prefetch type. Once the
 * resource allocation for all immediate downstream devices is complete at the domain level,
 * resource allocator walks down the subtree for each downstream bridge to continue the
 * allocation process at the bridge level. Since bridges have separate windows for i/o, mem and
 * prefmem, best fit algorithm at bridge level looks for the biggest requirement considering
 * prefmem resources separately from non-prefmem resources. This continues until resource
 * allocation is performed for all downstream bridges in the domain sub-tree. This is referred
 * to as pass 2 of resource allocator.
 *
 * Some rules that are followed by the resource allocator:
 *  - Allocate resource locations for every device as long as the requirements can be satisfied.
 *  - If a resource cannot be allocated any address space, then that resource needs to be
 * properly updated to ensure that it does not incorrectly overlap some address space reserved
 * for a different purpose.
 *  - Don't overlap with resources in fixed locations.
 *  - Don't overlap and follow the rules of bridges -- downstream devices of bridges should use
 * parts of the address space allocated to the bridge.
 */
void allocate_resources(const struct device *root)
{
	const struct device *child;

	if ((root == NULL) || (root->link_list == NULL))
		return;

	for (child = root->link_list->children; child; child = child->sibling) {

		if (child->path.type != DEVICE_PATH_DOMAIN)
			continue;

		post_log_path(child);

		/* Pass 1 - Gather requirements. */
		printk(BIOS_INFO, "Resource allocator: %s - Pass 1 (gathering requirements)\n",
		       dev_path(child));
		compute_domain_resources(child);

		/* Pass 2 - Allocate resources as per gathered requirements. */
		printk(BIOS_INFO, "Resource allocator: %s - Pass 2 (allocating resources)\n",
		       dev_path(child));
		allocate_domain_resources(child);
	}
}