How are programs split up into pages in Memory Paging?

Question

I am a bit confused about how the logical addresses are generated in a paging memory architecture and where and when a program is split up into pages. I understand how logical addresses are translated to physical addresses and everything that happens after that. I just don't understand how a program is split into distinct pages and where and how this happens.

For example, if we consider a non-paging architecture which uses contiguous memory and execution-time binding, a CPU instruction like JUMP 8, where 8 is a logical address, I understand how an MMU with a base register can dynamically relocate a program anywhere in main memory by changing the value stored in base register, while the object code stored in memory is still using the logical address of 8. However, how is this JUMP 8 instruction handled in a paging architecture, as in when will all these simple logical addresses like 8 be converted into logical addresses suitable for paging (with a page number and offset value), does the compiler split the program into pages?

Also, how is the program stored in memory, are the simple logical addresses stored like in execution-time binding, or is the program in memory stored with the paging logical addresses?

Answer 1

The program is not really split up into pages. The program is unaware of where it lands in physical memory. This is all the essence of paging.

For example, if you take Linux on x86 CPUs and the C++ language, you will have the compiler generating machine code which will be linked into a final executable which has a .ELF extension.

ELF files support virtual addresses. ELF files specify the virtual addresses at which the code is going to land. The linker or compiler is going to write the starting virtual address at which the code is going to land. The default virtual address is 0x400000 with ld and g++.

So basically, the ELF executable specifies where the program lands in virtual memory. Since the default virtual address is always 0x400000, then a lot of programs will have that starting virtual address. The kernel thus creates page tables for each process (each executable that you start). These processes will land at different places in memory even if they all have the same virtual address. This is due to the fact that they have different page tables.

In fact Linux holds a page struct for every physical page in the system. This takes up quite some space and there have been discussion to change this pattern. I don't know if it is yet done. The page struct allows the kernel to map all physical pages to know what every page is used for.

So when you start an executable/process the kernel determines what physical pages are available and set up the page tables for that process so that virtual address 0x400000 lands there once translated by the MMU.

The JMP 8 instruction will be translated by the MMU before being placed on the address bus. So the 8 is a virtual address. This virtual address is determined by the compiler and the linker.

There are 2 different kinds of JMPs. Relative JMPs and absolute JMPs (far JMPs). Relative JMPs are calculated as an offset from the current position in the code. Far JMPs in the meantime are calculated as absolute address. They contain a virtual address where the JMP should go. They can JMP anywhere in RAM.

For example,

label:
jmp label

is a relative JMP, while

jmp 0x8000

is an absolute JMP. These jumps are calculated by the compiler and linker. The compiler places the functions you call from main at different positions in the code that it places in the relative JMPs. Far JMPs are mostly used in operating-system development.

The linker plays the role of linking several files. So you have a symbol section in the ELF file. This symbol section contains entries which associate each symbol with an address. I'm not totally aware since I never wrote an ELF interpreter. What I can tell is that the address is the address of the beginning of something like a variable or mostly functions. What happens is that the linker takes the symbol and checks it against other object files you included in the linking command. If it finds the symbol in another file, it places the address of the code in the relative JMP to tell the code where to JMP to get to that function. That is why it is called a linker, because it resolves links. This is why you have to include header files in C++. You tell the linker where to find these other symbols (functions, variables, classes).

Answer 2

On a consumer system, the page management is done by the kernel, but the translation is done by the MMU when you read and write to the memory. You got the idea of the MMU right, but nowadays it uses a page table which maps the virtual address space to your physical memory.

Pages are usually 4kB long, which means each contains 2^12 bytes. To find your page's number the MMU simply discards the 12 least significant bits of your address. Each process has its own page table (in fact there are many "layers" of page tables) and with each context switch (ie. when you change the process that is currently executing on a logical core) the kernel also restores the page table into memory. On x86 there is the CR3 register that holds the address of the page table so it can be read accessed by the MMU.

The page table entry contains a few flags, the most important one is the present/absent. It tells you whether the page is actually present in the memory or not. When your code will try to read or write to that page, if it is missing it will generate a page fault which will be handled by the kernel. If you're allowed to access the requested address (ie. no segmentation fault), the kernel will fetch the page from the disk (if needed to) and put it somewhere in memory and save its physical address in the page table.

The compiler is not usually involved in this process even though it does reorder your code so you ever only accessing a small part of your code. Imagine if all your virtual addresses were 4kB aligned : a char at 0x1000, another at 0x2000, etc. You would be wasting pages and physical memory. So the compiler "knows" paging and avoids doing that. But it does not split. Furthermore the binaries are not directly executed but interpreted instead so you would have to take that into account too.

Of course this process does not apply to the kernel as it cannot handle his own page faults.