4 ms·

ARM32 Page Tables

66 points by sohkamyung 6y ago

bla3 6y ago
Does anyone know how different things are on arm64?
twic 6y ago
Has any chip used an extent-based virtual memory system? That is, rather than having fixed-size pages, with a leaf page table entry for each one, have variable-sized extents that span many pages, with a single entry for the extent. This would reduce the amount of bookkeeping if the OS hands out physical memory in large contiguous tracts, but increase it if it is shuffling around individual pages. I have no idea what OS behaviour here actually is.
- dragontamer 6y ago
  x86 has 4k, 2MB, and 1GB page sizes. > This would reduce the amount of bookkeeping if the OS hands out physical memory in large contiguous tracts, but increase it if it is shuffling around individual pages. I have no idea what OS behaviour here actually is. On x86, large 2MB and 1GB __cannot__ be paged. The latency associated with a 2MB or 1GB read/write to disk is just too long to be reasonable. These are called "huge pages" (2MB or larger). Memory-intensive applications see benefits from huge-pages, but the additional book-keeping to the user (in particular: huge pages CANNOT be paged, and therefore are a "rare-ish resource") has made HugePages somewhat uncommon on both Linux and Windows. (Windows only supports the 2MB hugepage, and ignores the 1GB option entirely) > This would reduce the amount of bookkeeping if the OS hands out physical memory in large contiguous tracts Note that all modern chips have a TLB-cache, to the point where the bookkeeping is largely handled by the CPU itself. This TLB-cache still has restrictions, so a huge-page reduces book-keeping and accelerates the speed of memory access slightly. The OS sets up the table, but the CPU itself handles the whole shebang nearly transparently. That's why all of these memory-address and data-structure specific details show up when talking about page-tables, you've got to set up the data-structure precisely so that the dedicated hradware inside the CPU can traverse the table correctly.
  - throwaway525142 6y ago
    > On x86, large 2MB and 1GB __cannot__ be paged. The latency associated with a 2MB or 1GB read/write to disk is just too long to be reasonable. Do you have a link where I can read about this? Couldn't find it quickly.
    - dragontamer 6y ago
      Debian's hugepage docs are pretty good: https://wiki.debian.org/Hugepages https://wiki.debian.org/Hugepages Windows has Large-Page documentation: https://docs.microsoft.com/en-us/windows/win32/memory/large-page-support https://docs.microsoft.com/en-us/windows/win32/memory/large-... Linux kernel also has docs: https://www.kernel.org/doc/Documentation/vm/hugetlbpage.txt https://www.kernel.org/doc/Documentation/vm/hugetlbpage.txt In my experience, most Linux distros have huge-pages enabled, but just doesn't use them unless the user sets some configuration flags in various locations.
      - throwaway525142 6y ago
        Thanks, that was interesting. :)
  - marcan_42 6y ago
    > The latency associated with a 2MB or 1GB read/write to disk is just too long to be reasonable. On spinning rust, seek times are O(10ms) and speeds are O(100MB/s). That means in the time it takes to seek to page in a page, you could read about 1MB worth of data. That should make that order of page size vastly more efficient for paging in data than tiny 4kB pages, from an HDD. From an SSD, sure, the seek penalty is much lower so things should skew in favor of smaller reads.
    - brandmeyer 6y ago
      The seek penalty is lower, true. However, the peak throughput is also much higher, so SSDs share this behavior with HDDs.
    - 6y ago
- lgunsch 6y ago
  Memory allocated in variable sized chunks has a lot more fragmentation. The OS would have to search around for free areas and keep track of them to be able to give memory out. Although, this is what user space allocators already do. The book Operating Systems: Three Easy Pieces has a section to answer this very question.
  - dragontamer 6y ago
    > The OS would have to search around for free areas and keep track of them to be able to give memory out. I don't think fragmentation is the issue. The OS doesn't search the page tables. The __CPU__ does, EVERY single time any program does a memory lookup (load/store operation), the CPU may have to traverse the page table. Page-table entries are often cached in the TLB-cache, but if the cache is full, a full table-traversal is necessary. Its clear that page-tables are optimized for minimum latency: so that the smallest area of the CPU can be used, and the simplest hardware can implement the page-lookup procedure. "blah = blah->next" is a very common pattern in programming. Since the page-table implementation in the CPU can speed this operation up (or slow it down), its extremely important to optimize for absolute fastest latency. ----- A lot of stuff goes on with "blah = blah->next". If blah->next is outside the TLB cache, the CPU will have to jump to the page-table, traverse the 1st, 2nd, and 3rd levels of paging (looking for the physical location of blah->next). A "variable length page" would complicate this lookup severely: the CPU wouldn't know which offset to lookup pages, and your non-TLB pages will be much much slower as a result. x86 "huge pages" are based on only searching one (1GB) or two (2MB) layers of the page-lookup procedure, instead of all three (going down to 4kB pages). That's how you get support for other sizes without variable-length entries in the page tables / page directory table / etc. etc.
    - lgunsch 6y ago
      The OS must search page tables to allocate them to a processes memory space upon request. Without fixed sized pages the OS has to search for appropriately sized areas to satisfy allocation requests. Fixed sized pages solves this problem. Edit: you would also then suffer memory fragmentation, not just lookup latency. For already mapped pages latency would be an issue as you described.
- repiret 6y ago
  Arm. See [1]. In fact, I'm aware of no architecture that supports only a single page size. [1]: https://developer.arm.com/documentation/ddi0333/h/memory-management-unit/mmu-descriptors/first-level-descriptor-address https://developer.arm.com/documentation/ddi0333/h/memory-man... This is specifically for the old ARM1176, but there are only minor page table format tweaks in ARMv7-A and ARMv8-A AArch32 short descriptor page tables. ARMv7+ also supports what they call Long Descriptor Page Tables, which are fundamentally similar, but have 8-byte page table entries, support larger physical addresses, and have a different set of available page sizes, and lots of other little details are different.
- rrss 6y ago
  PowerPC had support for block address translation, which provides a handful of registers to specify translations for variable-sized blocks, which is close-ish to what you have in mind (though very limited), in addition to an inverted page table. More recent revisions of the architecture (POWER9) have shifted towards a more typical radix page table.
brandmeyer 6y ago
Serious question: Why does each level in the page directory get its own name, instead of just being the N'th directory? Also, why count the directories from the bottom instead of the top?
- Veserv 6y ago
  They have their own names because Linux was x86 first which had different names for the levels. I do not know why x86 had different names for the levels, but they probably did not notice or care about the generalizability as the exact layout of control bits (read/write permissions, etc) at each level is not fully consistent. They did somewhat realize this in the future as the first depth extension, the addition of the 4th level, has the reasonable name of Level 4 entries. ARM is much better about the naming convention in its documentation and somewhat more consistent with its control bits. You count directories from the bottom because you may need to add another level in future hardware to allow handling greater maximum virtual addresses. Choosing a naming convention where extensions increase in numbering is generally a better idea otherwise you end up with a travesty like x86 privilege level (ring) numbering which used lower numbers (ring 0) for higher privilege, so when they needed a higher privilege level they needed to add ring -1, -2, -3, etc. This also is in contrast to how ARM uses higher numbers for higher privilege (EL{x}), so could add EL2, EL3, etc. when they needed higher levels.
andy_threos_io 6y ago
Nice article, but there are several issues with the older ARM MMU concept, and as some Linux distros does not support x86 32 bit anymore, I think we should move on, and forget about the classic ARM MMU. In our OS Threos ( https://threos.io https://threos.io ) on ARM we are only support LPAE (Large Physical Address Extension). The classic ARM MMU 1kb page size is just too small, needs too much accounting does not worth it. BTW as I remember on iOS ARM the minimum page allocation size is 16kb.

66 points by sohkamyung 6y ago

bla3 6y ago

Does anyone know how different things are on arm64?

twic 6y ago

Has any chip used an extent-based virtual memory system? That is, rather than having fixed-size pages, with a leaf page table entry for each one, have variable-sized extents that span many pages, with a single entry for the extent. This would reduce the amount of bookkeeping if the OS hands out physical memory in large contiguous tracts, but increase it if it is shuffling around individual pages. I have no idea what OS behaviour here actually is.

dragontamer 6y ago
x86 has 4k, 2MB, and 1GB page sizes. > This would reduce the amount of bookkeeping if the OS hands out physical memory in large contiguous tracts, but increase it if it is shuffling around individual pages. I have no idea what OS behaviour here actually is. On x86, large 2MB and 1GB __cannot__ be paged. The latency associated with a 2MB or 1GB read/write to disk is just too long to be reasonable. These are called "huge pages" (2MB or larger). Memory-intensive applications see benefits from huge-pages, but the additional book-keeping to the user (in particular: huge pages CANNOT be paged, and therefore are a "rare-ish resource") has made HugePages somewhat uncommon on both Linux and Windows. (Windows only supports the 2MB hugepage, and ignores the 1GB option entirely) > This would reduce the amount of bookkeeping if the OS hands out physical memory in large contiguous tracts Note that all modern chips have a TLB-cache, to the point where the bookkeeping is largely handled by the CPU itself. This TLB-cache still has restrictions, so a huge-page reduces book-keeping and accelerates the speed of memory access slightly. The OS sets up the table, but the CPU itself handles the whole shebang nearly transparently. That's why all of these memory-address and data-structure specific details show up when talking about page-tables, you've got to set up the data-structure precisely so that the dedicated hradware inside the CPU can traverse the table correctly.
- throwaway525142 6y ago
  > On x86, large 2MB and 1GB __cannot__ be paged. The latency associated with a 2MB or 1GB read/write to disk is just too long to be reasonable. Do you have a link where I can read about this? Couldn't find it quickly.
  - dragontamer 6y ago
    Debian's hugepage docs are pretty good: https://wiki.debian.org/Hugepages https://wiki.debian.org/Hugepages Windows has Large-Page documentation: https://docs.microsoft.com/en-us/windows/win32/memory/large-page-support https://docs.microsoft.com/en-us/windows/win32/memory/large-... Linux kernel also has docs: https://www.kernel.org/doc/Documentation/vm/hugetlbpage.txt https://www.kernel.org/doc/Documentation/vm/hugetlbpage.txt In my experience, most Linux distros have huge-pages enabled, but just doesn't use them unless the user sets some configuration flags in various locations.
    - throwaway525142 6y ago
      Thanks, that was interesting. :)
- marcan_42 6y ago
  > The latency associated with a 2MB or 1GB read/write to disk is just too long to be reasonable. On spinning rust, seek times are O(10ms) and speeds are O(100MB/s). That means in the time it takes to seek to page in a page, you could read about 1MB worth of data. That should make that order of page size vastly more efficient for paging in data than tiny 4kB pages, from an HDD. From an SSD, sure, the seek penalty is much lower so things should skew in favor of smaller reads.
  - brandmeyer 6y ago
    The seek penalty is lower, true. However, the peak throughput is also much higher, so SSDs share this behavior with HDDs.
  - 6y ago
lgunsch 6y ago
Memory allocated in variable sized chunks has a lot more fragmentation. The OS would have to search around for free areas and keep track of them to be able to give memory out. Although, this is what user space allocators already do. The book Operating Systems: Three Easy Pieces has a section to answer this very question.
- dragontamer 6y ago
  > The OS would have to search around for free areas and keep track of them to be able to give memory out. I don't think fragmentation is the issue. The OS doesn't search the page tables. The __CPU__ does, EVERY single time any program does a memory lookup (load/store operation), the CPU may have to traverse the page table. Page-table entries are often cached in the TLB-cache, but if the cache is full, a full table-traversal is necessary. Its clear that page-tables are optimized for minimum latency: so that the smallest area of the CPU can be used, and the simplest hardware can implement the page-lookup procedure. "blah = blah->next" is a very common pattern in programming. Since the page-table implementation in the CPU can speed this operation up (or slow it down), its extremely important to optimize for absolute fastest latency. ----- A lot of stuff goes on with "blah = blah->next". If blah->next is outside the TLB cache, the CPU will have to jump to the page-table, traverse the 1st, 2nd, and 3rd levels of paging (looking for the physical location of blah->next). A "variable length page" would complicate this lookup severely: the CPU wouldn't know which offset to lookup pages, and your non-TLB pages will be much much slower as a result. x86 "huge pages" are based on only searching one (1GB) or two (2MB) layers of the page-lookup procedure, instead of all three (going down to 4kB pages). That's how you get support for other sizes without variable-length entries in the page tables / page directory table / etc. etc.
  - lgunsch 6y ago
    The OS must search page tables to allocate them to a processes memory space upon request. Without fixed sized pages the OS has to search for appropriately sized areas to satisfy allocation requests. Fixed sized pages solves this problem. Edit: you would also then suffer memory fragmentation, not just lookup latency. For already mapped pages latency would be an issue as you described.
repiret 6y ago
Arm. See [1]. In fact, I'm aware of no architecture that supports only a single page size. [1]: https://developer.arm.com/documentation/ddi0333/h/memory-management-unit/mmu-descriptors/first-level-descriptor-address https://developer.arm.com/documentation/ddi0333/h/memory-man... This is specifically for the old ARM1176, but there are only minor page table format tweaks in ARMv7-A and ARMv8-A AArch32 short descriptor page tables. ARMv7+ also supports what they call Long Descriptor Page Tables, which are fundamentally similar, but have 8-byte page table entries, support larger physical addresses, and have a different set of available page sizes, and lots of other little details are different.
rrss 6y ago
PowerPC had support for block address translation, which provides a handful of registers to specify translations for variable-sized blocks, which is close-ish to what you have in mind (though very limited), in addition to an inverted page table. More recent revisions of the architecture (POWER9) have shifted towards a more typical radix page table.

brandmeyer 6y ago

Serious question: Why does each level in the page directory get its own name, instead of just being the N'th directory? Also, why count the directories from the bottom instead of the top?

Veserv 6y ago
They have their own names because Linux was x86 first which had different names for the levels. I do not know why x86 had different names for the levels, but they probably did not notice or care about the generalizability as the exact layout of control bits (read/write permissions, etc) at each level is not fully consistent. They did somewhat realize this in the future as the first depth extension, the addition of the 4th level, has the reasonable name of Level 4 entries. ARM is much better about the naming convention in its documentation and somewhat more consistent with its control bits. You count directories from the bottom because you may need to add another level in future hardware to allow handling greater maximum virtual addresses. Choosing a naming convention where extensions increase in numbering is generally a better idea otherwise you end up with a travesty like x86 privilege level (ring) numbering which used lower numbers (ring 0) for higher privilege, so when they needed a higher privilege level they needed to add ring -1, -2, -3, etc. This also is in contrast to how ARM uses higher numbers for higher privilege (EL{x}), so could add EL2, EL3, etc. when they needed higher levels.

andy_threos_io 6y ago

Nice article, but there are several issues with the older ARM MMU concept, and as some Linux distros does not support x86 32 bit anymore, I think we should move on, and forget about the classic ARM MMU. In our OS Threos ( https://threos.io https://threos.io ) on ARM we are only support LPAE (Large Physical Address Extension). The classic ARM MMU 1kb page size is just too small, needs too much accounting does not worth it. BTW as I remember on iOS ARM the minimum page allocation size is 16kb.