2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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).

$\endgroup$
6
  • $\begingroup$ Thanks for the answer. You skipped over the main part of my question, how is the JMP 8 instruction translated? And again I'm not talking about the process of taking a page number and offset value and getting a physical address, I understand how that works. But how is this 8 (or 0x400008) which is the instruction stored in memory translated to a page number and offset value. $\endgroup$
    – Kartheyan
    Jan 10 at 4:59
  • $\begingroup$ It is conventionnal. It depends on the architecture whether it is 32 bits or 64 bits. If it is 32 bits then the virtual address is split into 3 parts. 12 bits for the offset in the page, 10 bits for the offset in the page table, and 10 bits for the offset in the page directory. The CR3 register contains the address of the bottom of the page directory. For x64 it's similar but with 5 parts. $\endgroup$
    – user123
    Jan 10 at 5:04
  • $\begingroup$ When is the page number that will store the data stored in the address 8 referenced by the program determined? Let's consider two pages stored in memory (at two random physical locations), one storing data and the other storing an instruction referencing that data. How is the address stored in that instruction know what page or what the offset is for that piece of data? $\endgroup$
    – Kartheyan
    Jan 10 at 5:09
  • $\begingroup$ The physical page number is determined when you launch the process. Processes can have both static and dynamic memory allocation. Static is when the program is stored completely in the ELF executable. Dynamic is when the program asks for more memory during execution. In C++ you use new to ask for more memory. The physical page where your process's code lands is determined when you launch that process. Like I said in my answer the kernel maps the available pages using page C structures. It then determines what pages the process gets by an algorithm called the buddy algorithm. $\endgroup$
    – user123
    Jan 10 at 5:15
  • $\begingroup$ In a segmented memory architecture, when the instruction JUMP 8 is stored in memory, the address 8 is resolved by the MMU using a base register by adding a number which translates into a physical address. However, the MMU for a paging architecture is described as taking in a page number and offset and then getting the physical address. How is this 8 stored in some page translated to a page number? I think you are explaining how the process is split into pages, where I am referring to the instructions stored within these pages and how these instructions themselves reference memory locations. $\endgroup$
    – Kartheyan
    Jan 10 at 5:26
0
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Page tables are actually in memory except there is a page cache called the TLB. The MMU is really just a calculator which translates the virtual address into physical address. $\endgroup$
    – user123
    Jan 10 at 4:11
  • $\begingroup$ If we consider a compiled object code instruction JUMP 8 stored in a frame. How is that 8 translated to a logical address with a page number and an offset to then be translated to a physical address by an MMU. In a segmentation architecture, a base register is used and a number is added to 8, this directly gives the physical address. How do we go from 8 to a logical address made up of a page number and offset to a physical address. I understand how from a logical address made up of a page number and offset we can get the physical address. $\endgroup$
    – Kartheyan
    Jan 10 at 4:20
  • $\begingroup$ Thanks, yes, you're right, I forgot about the CR3 register, I was rather thinking about saving the TLB, but it's not usually done. I edited my answer $\endgroup$ Jan 10 at 4:22
  • $\begingroup$ Obtaining the page number is a bit more complex than just discarding the least significant bytes, but fundamentally it is the same. Let's say you are accessing 0x800B001. Your page number is 0x800B. You find the physical address corresponding in your page table. It is 4k aligned so it could be 0x1000. Then you append your last 12 bits so you ends up reading at 0x1001. $\endgroup$ Jan 10 at 4:28
  • $\begingroup$ I'm not talking about getting the physical address from a given page number and offset value, this is what the MMU does. But how do we get the page number and offset value in the first place from the instruction stored in memory, like JUMP 8 or to get store data from memory at location 3 in a register. Obviously, 8 and 3 aren't actually physical addresses but they also have no information about what page the data in 3 is stored on. $\endgroup$
    – Kartheyan
    Jan 10 at 5:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.