how does paging work in terms of the OS using pages?

[yemista]

I understand how paging works on the technical level, however, how does it work in actual application? What I mean to ask is, lets say your kernel needs to allocate memory. Ok, it finds a free page, and gets a pointer to that page. That part seems simple enough, but what about cases where it needs an amount of memory greater than 4KB, or if it wants to load a program that needs more than one page, but there are no two continuous pages free? AFAIK, programs assume a continuous address space, so what about cases where that cant be true? If anyone can direct me to some documents or tutorials that go into paging more in depth I would appreciate it.

[Firestryke31]

The pages in physical memory don't have to be continuous, because the processor can 'pretend' that they are by moving them around in a way.

Basically, when you write to the page table/directory, the value you write is the physical memory, and where you write it is the 'virtual' memory, or where that memory will appear to be to the processor. this means you can take 2 physical pages, one at the beginning and one at the end, and make them look to the processor like they're right next to each other. Someone else can explain in greater technical detail...

[yemista]

No, this part I understand. Each page table entry has a frame, and this is how the processor figures out to what frame each page is mapped. I also understand that you can map any frame to any page, however, the thing Im missing is, how can you ever guarantee that there will be two continuous frames available?

[Firestryke31]

You mean two consecutive virtual address blocks (IDK the 'official' term)? I guess if you can't find that you should just fail the allocation (I.E. malloc's returning NULL or new's exception/NULL return).

[AJ]

Hi,

The source of your misunderstanding here seems to be the linear vs. physical address space.

When you load a program in your user space, you generally create a new address space (new CR3) - I guess you understand that bit already. Now, say you load the program at 0x100000 and it needs 2 pages, that's fine. The physical pages do not have to be contiguous.

This means that for lazy loading, you could set the initial EIP to 0x100000 (for arguments sake, assume this is the entry point). Because you have not paged in, this will generate a PFE. Now, the kernel know that 0x100000 should contain the first 4k of the program. It therefore pages in any free physical page and loads the executable from disk. The program now merrily executes, until it hits an instruction stored in the second 4k.

A page fault will happen again, but again, the kernel knows that the next 4k of the program resides there. It therefore pages in any other free page of physical RAM. This may be contiguous, it may not. It then loads the second half of the executable from disk and program execution can continue.

The only event I can see where you need contiguous physical pages is ISA DMA (I've no idea about busmaster). As I don't do legacy DMA, I use a physical memory stack (rather than a bitmap) fr page allocation. This is faster, but it means I neer know where the next physical page is coming from.

HTH,
Adam

[JAAman]

i dont think you understand his question...

i believe his question is about consecutive virtual addresses

the reason nobody understood this is that it really isnt much of a question, while the other is a common misunderstanding

since the application is the only one running in its address space, it should always be able to provide the consecutive space required, unless the application itself already used the entire available address space

in this case, the virtual memory allocator should probably return an error (not entirely sure myself here...)... but its not going to happen often, though it might sometimes for 32bit programs (if its happening in 64 bit programs, you have much bigger problems with that program...)

[yemista]

no, his answer was the best answer, and thats what I was wondering. If you cant allocate consecutive frames, then you return a failure. However, what you said raises another issue. Ive been following James Molloys paging tutorial, and he using a bitset to determine which frames are free. Thats all well and good, however, there is a problem in that finding the first free frame, and the next free frame, might not necessarily be continuous, or maybe I have it backwards, and you want consecutive virtual addresses to be free. Either way, its a problem somehow because you have to have a way to find either pages or frames free with consecutive addresses. Any comments on how others do it? I was originally planning to use a stack based system and pop the next free page address off the stack, but now because of what you said I realize that you cant necessarily get continuous addresses. Is this even a problem as I see it? Maybe due to the nature of virtual memory this doesnt matter and Im missing the point, but I dont know. Can anyone clarify this for me?

[Hangin10]

generally, the virtual address space is divided into parts. For example, the kernel heap might be 0xD0000000-0xDFFFFFFF virtual. Any physical 4KB frame could be mapped as any 4KB virtual page in that range. The heap typically only expands or contracts, it doesn't free (mark as non-present) any physical memory mapped in, only at the ends. That way you don't need much of an allocator for virtual memory, only knowing what the last mapped virtual page is. Then if more is needed, allocate a physical page, if less is needed, release the physical page.

As for the application code itself, it gets it's own virtual space, say 0x400000 - 0x1000000 (small apps in this hypothetical OS ). In this case, the application just uses that range of virtual space, maybe not all of it, and each virtual 4KB page could have been allocated any physical page.

[yemista]

ok then I guess the real problem Im wondering about here(and sorry it took so long to get to it, Ive been a bit confused about virtual and physical address spaces) is managing the virtual address space. How can you guarantee there will be continuous virtual addresses available? especially after the system has been up and running for a while? I see that the physical addresses dont matter because any frame can be assigned to any page, so as long as the virtual address space is continous as far as the application knows, but what if your virtual address space is 0x00100000 to 0x00500000, and you assign 0x001000000 to 0x00200000 to the first app, 0x00300000 to 0x00400000 to the second app, and 0x00500000 to the third app, then the first app exits, the third app exits, and you try to run a program that takes 2 MB. You will have that much RAM free, but not that much continuous virtual address space free. This is what I am concerned with.

[Tomaka17]

but what if your virtual address space is 0x00100000 to 0x00500000, and you assign 0x001000000 to 0x00200000 to the first app, 0x00300000 to 0x00400000 to the second app, and 0x00500000 to the third app

Each process has a different view of the memory (except for the part of the memory which contains the kernel)
For example address 0x100 can contain different data for process 1 and 2

In most cases, it's even the executable file which tells the O/S where it has to be loaded
and so you can't share memory between processes as you could not handle the case where two executables would request the same loading address


Remember that the page directory doesn't have to be full

[xlq]

How can you guarantee there will be continuous virtual addresses available? especially after the system has been up and running for a while?

Each process has its own virtual address space.

Even if the system has been up and running for months, when you create a new process, it'll have a new virtual address space. I.e. 0x1000 in process A will be different to 0x1000 in process B.

The process will only run out of virtual address space if it allocates it all itself (there could be over 3 gigabytes of it, on x86). In that case, it's the process' silly fault for using up all its address space.

[abachler]

When the processor loads a memory address with say

Code: Select all

mov EAX , [foo]

foo is a virtual address. Which to the application is an actual address in its linear address space, however, the processor uses this 'address' as an index of sorts to look up in the paging table where that virtual address is actually stored in physical memory. So the paging mechanism basically acts as a translation layer between virtual address used by applications and physical addresses in ram. The OS can set up two consecutive virtual memory blocks in completely seperate areas of physical memory. So that foo[4095] may be located at physical address 0x00000FFF while foo[4096] may be at 0xFFFF0000. To the application though it would appear as though they were right next to each other, and &foo[4095] + 1 would == &foo[4096] (assuming char foo[]) in virtual address land.

[yemista]

Ok, I think I had the whole wrong idea about paging. So would you say then that it is true, that, each process has its own page directory table, and the kernel has its own as well? Is that how you make it so that each process has a 4GB address space, and when task switching, you swap in the appropriate PDE? That would then make sense.

[Hangin10]

Ok, I think I had the whole wrong idea about paging. So would you say then that it is true, that, each process has its own page directory table, and the kernel has its own as well? Is that how you make it so that each process has a 4GB address space, and when task switching, you swap in the appropriate PDE? That would then make sense.

Yes, on a task switch, CR3 will be loaded with the physical address of the top of the paging hierarchy (a page directory on legacy systems). The kernel is (in most systems) mapped into all the processes. That way, the various other tables required by the processor are present. It also prevents needing a complicated system to swap address spaces when a syscall (not necessarily the instruction syscall) occurs. Often the range 0xC0000000-0xFFFFFFFF is called kernel space, as the range is used for the kernel only, and below that is user space for the application (notice singular). This is true for each process. In this way, a kernel becomes more a series of routines callable by applications. An application could run in ring zero, but then it would have complete access to all of the address space; usually an attempt by an application to access kernel space would cause a fault.