1#
2# Copyright 2020, Data61, CSIRO (ABN 41 687 119 230)
3#
4# SPDX-License-Identifier: GPL-2.0-only
5#
6
7from typing import List, Set
8
9import hardware
10from hardware.config import Config
11from hardware.device import WrappedNode
12from hardware.fdt import FdtParser
13from hardware.memory import Region
14from hardware.utils.rule import KernelRegionGroup
15
16
17def get_memory_regions(tree: FdtParser):
18    ''' Get all regions with device_type = memory in the tree '''
19    regions = set()
20
21    def visitor(node: WrappedNode):
22        if node.has_prop('device_type') and node.get_prop('device_type').strings[0] == 'memory':
23            regions.update(node.get_regions())
24    tree.visit(visitor)
25    return regions
26
27
28def merge_memory_regions(regions: Set[Region]) -> Set[Region]:
29    ''' Check all region and merge adjacent ones '''
30    all_regions = [dict(idx=idx, region=region, right_adj=None, left_adj=None)
31                   for (idx, region) in enumerate(regions)]
32
33    # Find all right contiguous regions
34    for dreg in all_regions:
35        for dnreg in all_regions[dreg['idx']+1:]:
36            if dreg['region'].owner == dnreg['region'].owner:
37                if dnreg['region'].base == dreg['region'].base + dreg['region'].size:
38                    dreg['right_adj'] = dnreg
39                    dnreg['left_adj'] = dreg
40                elif dreg['region'].base == dnreg['region'].base + dnreg['region'].size:
41                    dnreg['right_adj'] = dreg
42                    dreg['left_adj'] = dnreg
43
44    # Find all the left-most contiguous regions
45    contiguous_regions = set()
46    for reg in all_regions:
47        if reg['left_adj'] is None:
48            size = reg['region'].size
49            r_adj = reg['right_adj']
50            while r_adj is not None:
51                size += r_adj['region'].size
52                r_adj = r_adj['right_adj']
53            contiguous_regions.add(Region(reg['region'].base, size, reg['region'].owner))
54
55    return contiguous_regions
56
57
58def parse_reserved_regions(node: WrappedNode) -> Set[Region]:
59    ''' Parse a reserved-memory node, looking for regions that are
60        unusable by OS (e.g. reserved for firmware/bootloader) '''
61    if node is None:
62        return set()
63
64    ret = set()
65    for child in node:
66        if child.has_prop('reg') and child.has_prop('no-map'):
67            ret.update(child.get_regions())
68    return ret
69
70
71def reserve_regions(regions: Set[Region], reserved: Set[Region]) -> Set[Region]:
72    ''' Given a set of regions, and a set of reserved regions,
73        return a new set that is the first set of regions minus the second set. '''
74    ret = set(regions)
75
76    while len(reserved) > 0:
77        reserve = reserved.pop()
78        new_ret = set()
79        for el in ret:
80            r = el.reserve(reserve)
81            new_ret.update(r)
82        ret = new_ret
83    return ret
84
85
86def get_physical_memory(tree: FdtParser, config: Config) -> List[Region]:
87    ''' returns a list of regions representing physical memory as used by the kernel '''
88    regions = merge_memory_regions(get_memory_regions(tree))
89    reserved = parse_reserved_regions(tree.get_path('/reserved-memory'))
90    regions = reserve_regions(regions, reserved)
91    regions, extra_reserved, physBase = config.align_memory(regions)
92
93    return regions, reserved.union(extra_reserved), physBase
94
95
96def get_addrspace_exclude(regions: List[Region], config: Config):
97    ''' Returns a list of regions that represents the inverse of the given region list. '''
98    ret = set()
99    # We can't create untypeds that exceed the addrspace_max, so we round down to the smallest
100    # untyped size alignment so that the kernel will be able to turn the entire range into untypeds.
101    as_max = hardware.utils.align_down(config.addrspace_max,
102                                       config.get_smallest_kernel_object_alignment())
103    ret.add(Region(0, as_max))
104
105    for reg in regions:
106        if type(reg) == KernelRegionGroup:
107            if reg.user_ok:
108                continue
109        new_ret = set()
110        for el in ret:
111            new_ret.update(el.reserve(reg))
112
113        ret = new_ret
114    return sorted(ret, key=lambda a: a.base)
115