1#
2# Copyright 2020, Data61, CSIRO (ABN 41 687 119 230)
3#
4# SPDX-License-Identifier: BSD-2-Clause
5#
6
7"""
8Various internal utility functions. Pay no mind to this file.
9"""
10
11from __future__ import absolute_import, division, print_function, \
12    unicode_literals
13
14import abc
15
16import six
17from six.moves import range
18
19from .Object import ObjectType, PageTable, PageDirectory, PML4, PDPT, PGD, PUD, get_object_size
20
21# Size of a frame and page (applies to all architectures)
22FRAME_SIZE = 4096  # bytes
23PAGE_SIZE = 4096  # bytes
24
25SIZE_64K = 64 * 1024
26SIZE_1M = 1024 * 1024
27SIZE_2M = 2 * SIZE_1M
28SIZE_4M = 4 * SIZE_1M
29SIZE_16M = 16 * SIZE_1M
30SIZE_32M = 32 * SIZE_1M
31SIZE_1GB = 1 * 1024 * 1024 * 1024
32SIZE_4GB = 4 * SIZE_1GB
33
34
35class Level:
36    """
37    Abstraction of a 'level' in a virtual address space hierarchy. A level
38    is parameterized by things such as; the virtual address range covered
39    by this object, the virtual address range covered by each entry in
40    the level and what kinds of frames (if any) can be placed directly
41    at this level.
42    """
43
44    def __init__(self, coverage, pages, object, make_object, type_name, parent=None, child=None):
45        self.coverage = coverage
46        self.pages = pages
47        self.parent = parent
48        self.child = child
49        self.object = object
50        self.make_object = make_object
51        self.type_name = type_name
52
53    def base_vaddr(self, vaddr):
54        """
55        Base address of the range covered by this level, determined
56        by using a virtual address from somewhere inside this object
57        """
58        return round_down(vaddr, self.coverage)
59
60    def parent_index(self, vaddr):
61        """
62        Index of this object in the parent level. Determine by a
63        using a virtual address from inside this object
64        """
65        return self.parent.child_index(vaddr)
66
67    def child_index(self, vaddr):
68        """
69        Index of a child object that is contained in this object.
70        Determine the index by using a combination of our coverage
71        and coverage of child objects. If we have no child assume
72        our 'child' is a standard page
73        """
74        if self.child is None:
75            return vaddr % self.coverage // PAGE_SIZE
76        else:
77            return vaddr % self.coverage // self.child.coverage
78
79
80def make_levels(levels):
81    assert levels is not None
82    assert len(levels) > 0
83    for i in range(0, len(levels), 1):
84        if i > 0:
85            levels[i].parent = levels[i - 1]
86        if i < len(levels) - 1:
87            levels[i].child = levels[i + 1]
88    return levels[0]
89
90
91class Arch(six.with_metaclass(abc.ABCMeta, object)):
92    def get_pages(self):
93        level = self.vspace()
94        pages = []
95        while level is not None:
96            pages.extend(level.pages)
97            level = level.child
98        return pages
99
100    def vspace(self):
101        return make_levels(self.levels())
102
103    @abc.abstractmethod
104    def levels(self):
105        pass
106
107
108class IA32Arch(Arch):
109    def capdl_name(self):
110        return "ia32"
111
112    def levels(self):
113        return [
114            Level(SIZE_4GB, [ObjectType.seL4_LargePageObject],
115                  ObjectType.seL4_PageDirectoryObject, PageDirectory, "pd"),
116            Level(SIZE_4M, [ObjectType.seL4_SmallPageObject],
117                  ObjectType.seL4_PageTableObject, PageTable, "pt"),
118        ]
119
120    def word_size_bits(self):
121        return 32
122
123    def ipc_buffer_size(self):
124        return 512
125
126
127class X64Arch(Arch):
128    def capdl_name(self):
129        return "x86_64"
130
131    def levels(self):
132        return [
133            Level(2 ** 48, [], ObjectType.seL4_X64_PML4, PML4, "pml4"),
134            Level(2 ** 39, [ObjectType.seL4_HugePageObject],
135                  ObjectType.seL4_X64_PDPT, PDPT, "pdpt"),
136            Level(2 ** 30, [ObjectType.seL4_LargePageObject],
137                  ObjectType.seL4_PageDirectoryObject, PageDirectory, "pd"),
138            Level(2 ** 21, [ObjectType.seL4_SmallPageObject],
139                  ObjectType.seL4_PageTableObject, PageTable, "pt"),
140        ]
141
142    def word_size_bits(self):
143        return 64
144
145    def ipc_buffer_size(self):
146        return 1024
147
148
149class ARM32Arch(Arch):
150    def __init__(self, hyp=False):
151        self.hyp = hyp
152
153    def capdl_name(self):
154        return "arm11"
155
156    def levels(self):
157        return [
158            Level(SIZE_4GB, [ObjectType.seL4_ARM_SectionObject, ObjectType.seL4_ARM_SuperSectionObject],
159                  ObjectType.seL4_PageDirectoryObject, PageDirectory, "pd"),
160            Level(SIZE_2M if self.hyp else SIZE_1M, [
161                  ObjectType.seL4_SmallPageObject, ObjectType.seL4_LargePageObject], ObjectType.seL4_PageTableObject, PageTable, "pt"),
162        ]
163
164    def word_size_bits(self):
165        return 32
166
167    def ipc_buffer_size(self):
168        return 512
169
170
171class AARCH64Arch(Arch):
172    def capdl_name(self):
173        return "aarch64"
174
175    def levels(self):
176        # When on 40-bit PA size on aarch64-hyp the PGD level doesn't exist.
177        if get_object_size(ObjectType.seL4_AARCH64_PGD):
178            return [
179                Level(2 ** 48, [], ObjectType.seL4_AARCH64_PGD, PGD, "pgd"),
180                Level(2 ** 39, [ObjectType.seL4_HugePageObject],
181                      ObjectType.seL4_AARCH64_PUD, PUD, "pud"),
182                Level(2 ** 30, [ObjectType.seL4_LargePageObject],
183                      ObjectType.seL4_PageDirectoryObject, PageDirectory, "pd"),
184                Level(2 ** 21, [ObjectType.seL4_SmallPageObject],
185                      ObjectType.seL4_PageTableObject, PageTable, "pt"),
186            ]
187        else:
188            return [Level(2 ** 39, [ObjectType.seL4_HugePageObject], ObjectType.seL4_AARCH64_PUD, PUD, "pud"),
189                    Level(2 ** 30, [ObjectType.seL4_LargePageObject],
190                          ObjectType.seL4_PageDirectoryObject, PageDirectory, "pd"),
191                    Level(2 ** 21, [ObjectType.seL4_SmallPageObject],
192                          ObjectType.seL4_PageTableObject, PageTable, "pt"),
193                    ]
194
195    def word_size_bits(self):
196        return 64
197
198    def ipc_buffer_size(self):
199        return 1024
200
201
202class RISCV64Arch(Arch):
203    def capdl_name(self):
204        return "riscv"
205
206    def levels(self):
207        return [
208            Level(2 ** 39, [ObjectType.seL4_HugePageObject],
209                  ObjectType.seL4_PageTableObject, PageTable, "pt"),
210            Level(2 ** 30, [ObjectType.seL4_LargePageObject],
211                  ObjectType.seL4_PageTableObject, PageTable, "pt"),
212            Level(2 ** 21, [ObjectType.seL4_SmallPageObject],
213                  ObjectType.seL4_PageTableObject, PageTable, "pt"),
214        ]
215
216    def word_size_bits(self):
217        return 64
218
219    def ipc_buffer_size(self):
220        return 1024
221
222
223class RISCV32Arch(Arch):
224    def capdl_name(self):
225        return "riscv"
226
227    def levels(self):
228        return [
229            Level(2 ** 32, [ObjectType.seL4_LargePageObject],
230                  ObjectType.seL4_PageTableObject, PageTable, "pt"),
231            Level(2 ** 22, [ObjectType.seL4_SmallPageObject],
232                  ObjectType.seL4_PageTableObject, PageTable, "pt"),
233        ]
234
235    def word_size_bits(self):
236        return 32
237
238    def ipc_buffer_size(self):
239        return 512
240
241
242def normalised_map():
243    return {
244        'aarch32': 'aarch32',
245        'aarch64': 'aarch64',
246        'arm': 'aarch32',
247        'arm11': 'aarch32',
248        'arm_hyp': 'arm_hyp',
249        'ia32': 'ia32',
250        'x86': 'ia32',
251        'x86_64': 'x86_64',
252        'riscv64': 'riscv64',
253        'riscv32': 'riscv32'
254    }
255
256
257def valid_architectures():
258    return set(normalised_map().values())
259
260
261def normalise_architecture(arch):
262    try:
263        return normalised_map()[arch.lower()]
264    except KeyError:
265        raise Exception('invalid architecture: %s' % arch)
266
267
268def lookup_architecture(arch):
269    arch_map = {
270        'aarch32': ARM32Arch(),
271        'aarch64': AARCH64Arch(),
272        'arm_hyp': ARM32Arch(hyp=True),
273        'ia32': IA32Arch(),
274        'x86_64': X64Arch(),
275        'riscv64': RISCV64Arch(),
276        'riscv32': RISCV32Arch()
277    }
278    try:
279        return arch_map[normalise_architecture(arch)]
280    except KeyError:
281        raise Exception('invalid architecture: %s' % arch)
282
283
284def round_down(n, alignment=FRAME_SIZE):
285    """
286    Round a number down to 'alignment'.
287    """
288    return n // alignment * alignment
289
290
291def round_up(n, alignment):
292    """
293    Round a number up to 'alignment'
294    """
295    return round_down(n + alignment-1, alignment)
296
297
298def last_level(level):
299    while level.child is not None:
300        level = level.child
301    return level
302
303
304def page_sizes(arch):
305    if isinstance(arch, six.string_types):
306        arch = lookup_architecture(arch)
307    list = [get_object_size(page) for page in arch.get_pages()]
308    list.sort()
309    return list
310
311
312def page_table_coverage(arch):
313    """
314    The number of bytes a page table covers.
315    """
316    return last_level(lookup_architecture(arch).vspace()).coverage
317
318
319def page_table_vaddr(arch, vaddr):
320    """
321    The base virtual address of a page table, derived from the virtual address
322    of a location within that table's coverage.
323    """
324    return last_level(lookup_architecture(arch).vspace()).base_vaddr(vaddr)
325
326
327def page_table_index(arch, vaddr):
328    """
329    The index of a page table within a containing page directory, derived from
330    the virtual address of a location within that table's coverage.
331    """
332    return last_level(lookup_architecture(arch).vspace()).parent_index(vaddr)
333
334
335def page_index(arch, vaddr):
336    """
337    The index of a page within a containing page table, derived from the
338    virtual address of a location within that page.
339    """
340    return last_level(lookup_architecture(arch).vspace()).child_index(vaddr)
341
342
343def page_vaddr(vaddr):
344    """
345    The base virtual address of a page, derived from the virtual address of a
346    location within that page.
347    """
348    return vaddr // PAGE_SIZE * PAGE_SIZE
349
350
351def ctz(size_bytes):
352    """
353    Count trailing zeros in a python integer.
354    The value must be greater than 0.
355    """
356    assert(size_bytes > 0)
357    assert(isinstance(size_bytes, six.integer_types))
358    low = size_bytes & -size_bytes
359    low_bit = -1
360    while low:
361        low = low >> 1
362        low_bit += 1
363    return low_bit
364