If the virtual address space can be larger than the physical address space, how are the address mappings stored in memory?

Question

Let's say we are working with a system that has 40 physical address bits. The total physical address space (assuming byte-addressable memory) is $2^{40}$ bytes, or 1 TiB. And if virtual addresses are 48 bits in length, that means there are more addresses available to virtual memory than there are locations in physical memory.

This makes sense to me, because the "excess" addresses could refer to hard disk locations as well. However, what I don't understand is how the translation between virtual and physical addresses occurs. I assume there is a mapping stored somewhere which links VAS locations to the physical locations. If there are more virtual address locations than physical locations, how can all of these mappings possibly be stored in memory? At minimum you would need 48 bits to store each virtual address, and then another 40 to store the physical location it maps to. So obviously you cannot just store a 1:1 mapping of each virtual address to its physical counterpart, as mapping every location would take more memory than physical memory itself.

What exactly am I missing here?

Answer 1

The trick to making this work is "paging." When bringing data from a hard disk into physical memory, you don't just bring a few bytes. You bring an entire page. 4k bytes is a very common page size.

If you only need to keep track of pages, not each individual byte, the mapping becomes much cheaper. If you have a 48 bit address space and 4096 byte pages, you only need to track which of the 2^36 pages (roughly 69 billion pages). That's much easier! The record of where all of the pages are found is known as a "page table."

If you actually need 1-256 TiB of memory, then giving up a few gigabytes to store this page table isn't a big deal. In practice however, we'll do things like use multi-level page tables, which lets us be a bit more efficient, keeping pages only for regions of the address space that we are actually using.

Answer 2

Cort Ammon's answer says

multi-level page tables [let] us be a bit more efficient, keeping pages only for regions of the address space that we are actually using.

and gnasher729's answer says

1 GB of page table could handle 512 GB of address space.

I think they both overlooked, or at least didn't make clear, an important point: the page table only contains the virtual-to-physical address mapping for pages that have a physical address. Its size is therefore a function of the amount of physical RAM in use, not the amount of virtual address space in use.

For example, if you have 8 GB of RAM and you mmap a 10-terabyte file, the OS most likely won't modify the page table at all at first; it will just record information about the mapping in some other private data structure. That data structure doesn't need to have an entry for every page of virtual address space covered by the file. It may be an interval tree in which the entry for the whole file takes just a few tens of bytes.

Later, when the user process tries to access a part of the mmapped file, the CPU will find no page table entry for the virtual address and will generate a page fault. The OS's page-fault handler will look up the virtual address, find that it's backed by the disk file, and start the process of reading a portion of the file into physical RAM. After the read completes, it will update the page table and restart the faulting instruction.

The user process may eventually read the entire 10 terabytes of data, but long before it finishes doing that, the OS will have started evicting earlier pages from RAM to make room for new ones. When the pages are evicted, the corresponding entries in the page table can also be freed. So the page table never grows to 10 TB / page_size * entry_size. Its size is closer to 8 GB / page_size * entry_size.

---

Also not mentioned in other answers is that the virtual address isn't stored in the page table entry. The table is indexed by the virtual address, so it's coded implicitly by position. With a 40-bit address bus and 2¹²-byte pages, each leaf entry only needs to contain the high 28 bits of the physical address and some metadata like write and execute permission bits.

---

In a comment, Nate Eldredge said

When actual memory is large, another way of reducing the memory needed for page tables is to allow for larger pages. x86 has an option to mix 4 KiB pages with 2/4 MiB pages.

As far as I know, the motivation for large pages is to save time, not space. CPUs since the earliest days of paging have had a specialized cache for page table entries, the TLB. This cache isn't very large, and misses require an expensive lookup in the in-RAM page table. If the pages are 512 times larger then it's like your TLB has 512 times more entries.

Larger pages do save page table space, but the overhead for 4K pages is already only 0.2% assuming a 8-byte entry size. Large pages also waste space to coarser allocation granularity.

Answer 3

Your processor typically uses 8 bytes to store the information for 4,096 byte table. So 1 GB of page table could handle 512 GB of address space. Yes, there is a limit where it might be impossible to use all of the theoretically possible address space. But then many processors now have 64 bit of address space (256 billion billion bytes), so it is to be expected that you can't use all of it.

What is often possible is to have used logical address space that is at random places within that 64 bit space; this can be used to prevent attacks from hackers because they cannot know where in that huge logical space your data is. (So for example malloc might return addresses anywhere in the 64 bit space, but only for a total of say 64 GB of data).