Page 1 of 2

Physical and Virtual Memory Allocator

Posted: Wed Aug 06, 2008 2:23 am
by leledumbo
I need some explanation on this.
Physical Memory Allocator will manage (i.e. Allocate and Free) pages in memory, which should be physical. Then we have to create a Virtual Memory Allocator based on this. The weird thing is when Paging is active, all memory references will be virtual. So, the page returned by Physical Memory Allocator will be virtual, too. It's no longer a Physical Memory Allocator then. Plus, if the returned page isn't yet present in page directory, a page fault will be triggered. To the best of my knowledge, Physical Memory Allocator should never trigger any page fault since it returns page based on available memory. Is there something I miss here?

Re: Physical and Virtual Memory Allocator

Posted: Wed Aug 06, 2008 2:58 am
by JamesM
Hi,

A physical memory allocator does just that - allocates and frees physical memory. Yes, all memory accesses when paging is enabled are virtual, but you still have to define the virtual->physical memory mapping for every page, so you still need to be able to allocate physical memory!

The usual use case for a physical memory allocator is:

Code: Select all

// Map a region of virtual addresses to somewhere in RAM (allocate a region of virtual memory).
// Assumes length is a multiple of 4K.
bool allocateVirtualRegion(uintptr_t begin, size_t length)
{
  // For every page...
  for (uintptr_t page = begin; page < begin+length; page += PAGE_SIZE)
  {
    physical_uintptr_t physical = getPhysicalPage(); // This calls the physical memory allocator, and asks for it to allocate one page.
    mapPage(page, physical); // This tells the virtual memory manager to map the virtual page "page" to the physical page "physical".
  }
  return true;
}
The point is that there is usually no reason to have to access the physical page your allocator returns directly - it's usually mapped into the virtual address space right after.

I hope I explained that well enough - please do ask again if it's not clear!

Cheers,

James

Re: Physical and Virtual Memory Allocator

Posted: Wed Aug 06, 2008 3:57 am
by leledumbo
Thanks, I understand. But there are some things that look suspicious. Let's take an example:
Assume that paging is enabled. The Physical Memory Allocator (PMA) gives me a free page, let's say at address $1000_0000 (underscore is used as Word separator). This is a virtual address. The map function then maps this to, let's say $0200_0000. When I access this mapped address, wouldn't it be considered as virtual, too (which means, it will be mapped again)?

Re: Physical and Virtual Memory Allocator

Posted: Wed Aug 06, 2008 4:04 am
by JamesM
leledumbo wrote:Thanks, I understand. But there are some things that look suspicious. Let's take an example:
Assume that paging is enabled. The Physical Memory Allocator (PMA) gives me a free page, let's say at address $1000_0000 (underscore is used as Word separator). This is a virtual address. The map function then maps this to, let's say $0200_0000. When I access this mapped address, wouldn't it be considered as virtual, too (which means, it will be mapped again)?
Hi,

Remember that you work in two different address spaces - physical and virtual. The physical memory manager returns an address in the physical address space, which will normally not be immediately accessible through the virtual address space.

So your physical manager returns 0x10000000, which is a physical address. The map function maps this to 0x2000000. When you access the address 0x2000000, the contents of physical address 0x10000000 will be modified/returned.

Cheers,

James

Re: Physical and Virtual Memory Allocator

Posted: Wed Aug 06, 2008 4:09 am
by samueldotj
leledumbo wrote:I need some explanation on this.
Physical Memory Allocator will manage (i.e. Allocate and Free) pages in memory, which should be physical. Then we have to create a Virtual Memory Allocator based on this. The weird thing is when Paging is active, all memory references will be virtual. So, the page returned by Physical Memory Allocator will be virtual, too. It's no longer a Physical Memory Allocator then. Plus, if the returned page isn't yet present in page directory, a page fault will be triggered. To the best of my knowledge, Physical Memory Allocator should never trigger any page fault since it returns page based on available memory. Is there something I miss here?
Physical Memory Allocator - Manages physical memory of a system.
Virtual Memory Allocator - Manages virtual address space of all applications and kernel.

To manage physical memory, physical memory allocator uses some data structure (meta data) which is mapped in the kernel virtual address space.
physical memory allocator manipulates only this virtual memory and does not touches the actual physical memory.
Then we have to create a Virtual Memory Allocator based on this.
Virtual Memory Allocator is not based on Physical Memory Allocator.
Most OS's Virtual Memory Allocators just allocates virtual address range when requested. The actual allocation of Physical Page is done only during first page fault, if at all it happens.
The weird thing is when Paging is active, all memory references will be virtual.
It is true for x86, however there are some platforms which allows accessing physical memory directly without a virtual address(example - Alpha and IA64).
So, the page returned by Physical Memory Allocator will be virtual, too. It's no longer a Physical Memory Allocator then.
In my implementation, Physical Memory Allocator returns starting address of a free physical page. Mapping it with a Virtual Address is handled in the upper layer.
To the best of my knowledge, Physical Memory Allocator should never trigger any page fault since it returns page based on available memory.
It depends on implementation. Most kernels allocates the memory needed to manage physical memory from it is non-pagable pool, those kernel don't expect page fault from Physical Memory Allocator.

Sam

Re: Physical and Virtual Memory Allocator

Posted: Wed Aug 06, 2008 4:31 am
by leledumbo

Code: Select all

Virtual Memory Allocator is not based on Physical Memory Allocator
What I mean by "based on" is that VMA needs to ask PMA to allocate/free some pages.

I'll copy this thread and bring it home, I need to concentrate (Why am I so stupid on this?!).
I'll post my code later.

Thanks for all. (^_^)

Re: Physical and Virtual Memory Allocator

Posted: Wed Aug 06, 2008 6:37 am
by Adek336
The physical memory allocator actually returns a number - like say, 0x1000. There may be both a virtual address 0x1000 and a program when accesses memory asks for a virtual address; and a physical memory address 0x1000 which means what address is being sent down the system bus, when a virtual page mapped to physical page 0x1000 is being accessed.

If 0x30000 virtual was mapped to 0x4000 physical, a program which wanted to write to cell 0x30000 would result in address 0x4000 appearing on the system bus.

Re: Physical and Virtual Memory Allocator

Posted: Wed Aug 06, 2008 2:58 pm
by -m32
It's rather simple.

Prior to enabling paging, you enumerate all available _usable_ physical memory in the system (using BIOS memory map to determine "usable" areas) and create a list to contain all of the page aligned addresses from that space. So, if memory from 0x100000 to 0x300000 is usable, you'd add to your list: 0x100000, 0x101000, 0x102000, 0x103000, ... 0x2FF000.

When paging is enabled, if you need the physical address of a "free" page frame, pop one of the addresses from the list that was created earlier. If you want to release (ie free) that frame, push it's physical address back into the list. Use the physical addresses from that list in your page tables, etc...

Easy as pie ;)

That's one approach anyway....

Re: Physical and Virtual Memory Allocator

Posted: Thu Aug 07, 2008 6:35 pm
by huxuelei
So, the physical allocator always return a free page. Is that it?

Re: Physical and Virtual Memory Allocator

Posted: Thu Aug 07, 2008 7:19 pm
by -m32
huxuelei wrote:So, the physical allocator always return a free page. Is that it?
Yes. Or a set/range of pages

Re: Physical and Virtual Memory Allocator

Posted: Fri Aug 08, 2008 12:46 am
by leledumbo
Time to play with code. Here's my PMM unit:

Code: Select all

unit pmm;

interface

var
  FrameStack: PLongWord;
  FrameStackTop: LongWord;
  NumOfFrames: LongWord;

function AllocFrame: PLongWord;
procedure FreeFrame(var Addr: PLongWord);
function FreeFramesLeft: LongWord;
procedure InstallPMM(FrameCount: LongWord);

implementation

uses
  console,paging;

function AllocFrame: PLongWord;
begin
  if FrameStackTop<NumOfFrames then begin
    AllocFrame:=PLongWord(FrameStack[FrameStackTop]);
    Inc(FrameStackTop);
  end else begin
    { Well, a swap should be tried before showing this }
    SetTextColor(scBlack,scRed);
    WriteString('Out of physical memory!');
    SetTextColor(scBlack,scLightGrey);
    WriteChar(#10);
    AllocFrame:=nil;
  end;
end;

procedure FreeFrame(var Addr: PLongWord);
begin
  Dec(FrameStackTop);
  FrameStack[FrameStackTop]:=PtrUInt(Addr);
  Addr:=nil;
end;

function FreeFramesLeft: LongWord;
begin
  FreeFramesLeft:=NumOfFrames-FrameStackTop+1;
end;

procedure InstallPMM(FrameCount: LongWord);
var
  i: LongWord;
begin
  WriteString('Installing Physical MM...'#9);
  FrameStack:=PageTable[768]+1024;
  FrameStackTop:=0;
  NumOfFrames:=FrameCount;
  for i:=0 to NumOfFrames-1 do
    FrameStack[i]:=PtrUInt(@FrameStack[NumOfFrames-1])+PageSize+(i*PageSize);
  WriteStrLn('[ OK ]');
end;

end.
The memory is organized like this:

$00100000 Kernel
$00119000 Page Directory ( 'end' is defined somewhere before this )
$0011A000 Page Table 0 ( identity map )
$0011B000 Page Table 768 ( maps kernel to $C0000000)
$0011C000 Frame Stack ( Assuming the memory is 128 MB, the first allocation should pop address $13CFA4 )

InstallPMM is called prior to enabling paging, so the above map should be right (I'm sure... 90%). After paging is enabled, I try to call AllocFrame in a loop hoping it runs until 'Out of physical memory!' is printed out. Something like:

Code: Select all

repeat
  WriteStrLn(HexStr(PtrUInt(p),8)+' = '+HexStr(p^,8));
  p:=AllocFrame;
until not Assigned(p);
But the memory reference only valid until $0003FF000 (end of page table 0) and I got page fault at the next call (at $00400000). This is what I'm confusing about.

Re: Physical and Virtual Memory Allocator

Posted: Sun Aug 10, 2008 7:50 pm
by leledumbo
Any memory guru, please help me... :cry:

Re: Physical and Virtual Memory Allocator

Posted: Mon Aug 11, 2008 1:47 am
by Combuster
Grab a debugger (bochs can help) and then find out which line in your source code is causing the exception. Most likely you are dereferencing the returned location and you only have the first page directory mapped

Re: Physical and Virtual Memory Allocator

Posted: Mon Aug 11, 2008 2:19 am
by leledumbo
Most likely you are dereferencing the returned location and you only have the first page directory mapped
Grab a debugger (bochs can help) and then find out which line in your source code is causing the exception
No need for that, I know exactly which one.
Most likely you are dereferencing the returned location and you only have the first page directory mapped
Well, that's right. I only map the first (and the 768 for higher half kernel) page table(s). Should I map ALL (that is, from 0 to 1023) page tables I have? Is it the way virtual memory manager works? And does my stack approach look OK?

Re: Physical and Virtual Memory Allocator

Posted: Mon Aug 11, 2008 2:32 am
by Combuster
The problem is, you wrote a physical memory manager, and you're using it as a virtual memory manager, which obviously does not work.

The physical memory manager returns available memory. The virtual memory manager will have to make that available in the process' address space.