allocator_v4: Use memranges only for toplevel

During phase 1 of the resource allocation we gather all the size
requirements. Starting from the leafs of our devicetree, we cal-
culate the requirements per bus, until we reach the resource do-
main.

However, because alignment plays a role, we can't just accumulate
the sizes of all resources on a bus. Instead, we already sort all
the resources per bus to predict their relative placement, inclu-
ding alignment gaps. Then, phase 2 has to perform the final allo-
cations with the exact same relative placement.

This patch introduces a very simple mechanism to avoid repeating
all the calculations: In phase 1, we note the relative `base` of
each resource on a bus. And after we allocated all the resources
directly below the domain in phase 2, we add the absolute `base`
of bridge resources to the relative `base` of child resources.

This saves most of the computational complexity in phase 2. How-
ever, with a shallow devicetree with most devices directly below
the domain, this won't have a measurable impact.

Example after phase 1:

  domain
    |
    `-- bridge #0
          |   res #0, base 0x000000 (relative),
          |   size 12M, align 8M
          |
          |-- device #0
          |         res #1, base 0x800000 (relative),
          |         size 4M, align 4M
          |
          `-- bridge #1
                |   res #2, base 0x000000 (relative),
                |   size 8M, align 8M
                |
                `-- device #1
                          res #3, base 0x000000 (relative),
                          size 8M, align 8M

After phase 2 allocation at the domain level (assuming res #0 got
0xa000000 assigned):

  domain
    |
    `-- bridge #0
          |   res #0, base 0xa000000 (absolute),
          |   size 12M, align 8M
          |
          |-- device #0
          |         res #1, base 0x800000 (relative),
          |         size 4M, align 4M
          |
          `-- bridge #1
                |   res #2, base 0x000000 (relative),
                |   size 8M, align 8M
                |
                `-- device #1
                          res #3, base 0x000000 (relative),
                          size 8M, align 8M

Now, all we need to do is to add the `base` of bridge resources
recursively. Starting with resources on the bus below bridge #0:

  domain
    |
    `-- bridge #0
          |   res #0, base 0xa000000 (absolute),
          |   size 12M, align 8M
          |
          |-- device #0
          |         res #1, base 0xa800000 (absolute),
          |         size 4M, align 4M
          |
          `-- bridge #1
                |   res #2, base 0xa000000 (absolute),
                |   size 8M, align 8M
                |
                `-- device #1
                          res #3, base 0x000000 (relative),
                          size 8M, align 8M

And finally for resources on the bus below bridge #1:

  domain
    |
    `-- bridge #0
          |   res #0, base 0xa000000 (absolute),
          |   size 12M, align 8M
          |
          |-- device #0
          |         res #1, base 0xa800000 (absolute),
          |         size 4M, align 4M
          |
          `-- bridge #1
                |   res #2, base 0xa000000 (absolute),
                |   size 8M, align 8M
                |
                `-- device #1
                          res #3, base 0xa000000 (absolute),
                          size 8M, align 8M

Change-Id: I70c700318a85f6760f27597730bc9c9a86dbe6b3
Signed-off-by: Nico Huber <nico.h@gmx.de>
Reviewed-on: https://review.coreboot.org/c/coreboot/+/65420
Reviewed-by: Lean Sheng Tan <sheng.tan@9elements.com>
Reviewed-by: Arthur Heymans <arthur@aheymans.xyz>
Tested-by: build bot (Jenkins) <no-reply@coreboot.org>
Reviewed-by: Felix Singer <service+coreboot-gerrit@felixsinger.de>

0 files changed, 0 insertions, 0 deletions