OSDev.org

The Place to Start for Operating System Developers
It is currently Thu Mar 28, 2024 8:02 pm

All times are UTC - 6 hours




Post new topic Reply to topic  [ 11 posts ] 
Author Message
 Post subject: Memory Allocation - How it works
PostPosted: Mon Feb 09, 2015 10:07 am 
Offline
Member
Member
User avatar

Joined: Fri Jan 16, 2015 10:41 am
Posts: 34
Location: United Kingdom
So, I'm implementing memory allocation in my kernel, so that when I'm done I'll have kmalloc() and kfree().
I'm a bit confused about some things, so could someone please confirm if my explanation is correct/incorrect. :?

This is how I think it works:
1. A physical memory allocator provides frame_alloc(pages) and frame_free(position, pages), which allocates physical memory in blocks of however big a page on the system architecture is. This can be implemented with a bitset, a stack, a buddy allocator, etc.
2. A virtual address allocator provides page_alloc(pages) and page_free(position, pages), which allocates virtual memory addresses in blocks of however big a page on the system architecture is, making use of frame_alloc() and frame_free(). This can be implemented with ???.
3. Finally, the memory allocator itself provides malloc(size) and free(position), which allocates virtual memory of any size. This can be implemented in several ways, and the code is usually linked with program binaries. This makes use of page_alloc() and page_free() through system calls (or directly for the kernel's memory allocator).

Please tell me if anything's incorrect! :)
-bace

_________________
"for example, turning off the system’s power through the movement of a large red switch" - the Advanced Configuration and Power Interface Specification


Top
 Profile  
 
 Post subject: Re: Memory Allocation - How it works
PostPosted: Mon Feb 09, 2015 10:22 am 
Offline
Member
Member

Joined: Fri Jan 30, 2015 4:57 pm
Posts: 215
Location: Germany
Allocating free virtual pages can be done by looping through the page directory and find free pages (or finding free page tables, representing 1024 free pages).


Top
 Profile  
 
 Post subject: Re: Memory Allocation - How it works
PostPosted: Mon Feb 09, 2015 11:15 am 
Offline
Member
Member
User avatar

Joined: Wed Oct 18, 2006 3:45 am
Posts: 9301
Location: On the balcony, where I can actually keep 1½m distance
Roflo wrote:
Allocating free virtual pages can be done by looping through the page directory and find free pages (or finding free page tables, representing 1024 free pages).
In general, if you want map something into virtual space without knowing which address to use for it or if it's free, your logic is flawed to start with.

_________________
"Certainly avoid yourself. He is a newbie and might not realize it. You'll hate his code deeply a few years down the road." - Sortie
[ My OS ] [ VDisk/SFS ]


Top
 Profile  
 
 Post subject: Re: Memory Allocation - How it works
PostPosted: Mon Feb 09, 2015 12:03 pm 
Offline
Member
Member

Joined: Fri Jan 30, 2015 4:57 pm
Posts: 215
Location: Germany
Combuster wrote:
Roflo wrote:
Allocating free virtual pages can be done by looping through the page directory and find free pages (or finding free page tables, representing 1024 free pages).
In general, if you want map something into virtual space without knowing which address to use for it or if it's free, your logic is flawed to start with.

Why?


Top
 Profile  
 
 Post subject: Re: Memory Allocation - How it works
PostPosted: Mon Feb 09, 2015 2:22 pm 
Offline
Member
Member
User avatar

Joined: Fri Jan 16, 2015 10:41 am
Posts: 34
Location: United Kingdom
Combuster wrote:
Roflo wrote:
Allocating free virtual pages can be done by looping through the page directory and find free pages (or finding free page tables, representing 1024 free pages).
In general, if you want map something into virtual space without knowing which address to use for it or if it's free, your logic is flawed to start with.

So, is it the program's job to choose where the physical memory is mapped to in the virtual address space? That doesn't seem right...? :?

_________________
"for example, turning off the system’s power through the movement of a large red switch" - the Advanced Configuration and Power Interface Specification


Top
 Profile  
 
 Post subject: Re: Memory Allocation - How it works
PostPosted: Mon Feb 09, 2015 2:59 pm 
Offline
Member
Member

Joined: Fri Jan 30, 2015 4:57 pm
Posts: 215
Location: Germany
No :lol: I meant this method could be used to detect free and unmapped pages in the virtual address space. Of course the program should not choose the physical memory address to use.


Top
 Profile  
 
 Post subject: Re: Memory Allocation - How it works
PostPosted: Mon Feb 09, 2015 3:48 pm 
Offline
Member
Member
User avatar

Joined: Sat Jan 15, 2005 12:00 am
Posts: 8561
Location: At his keyboard!
Hi,


bace wrote:
This is how I think it works:
1. A physical memory allocator provides frame_alloc(pages) and frame_free(position, pages), which allocates physical memory in blocks of however big a page on the system architecture is. This can be implemented with a bitset, a stack, a buddy allocator, etc.
2. A virtual address allocator provides page_alloc(pages) and page_free(position, pages), which allocates virtual memory addresses in blocks of however big a page on the system architecture is, making use of frame_alloc() and frame_free(). This can be implemented with ???.
3. Finally, the memory allocator itself provides malloc(size) and free(position), which allocates virtual memory of any size. This can be implemented in several ways, and the code is usually linked with program binaries. This makes use of page_alloc() and page_free() through system calls (or directly for the kernel's memory allocator).


That looks mostly right to me; however...

From the kernel's point of view; that final memory allocator should be considered part of the process. It could be "malloc()" and "free()" in a dynamically linked library, it could be something completely different (e.g. garbage collector), and it could also be "nothing" (e.g. programmer explicitly manages their own memory). A kernel doesn't need to know or care what the final memory allocator is.

bace wrote:
Combuster wrote:
Roflo wrote:
Allocating free virtual pages can be done by looping through the page directory and find free pages (or finding free page tables, representing 1024 free pages).
In general, if you want map something into virtual space without knowing which address to use for it or if it's free, your logic is flawed to start with.

So, is it the program's job to choose where the physical memory is mapped to in the virtual address space? That doesn't seem right...? :?


Once the process is started; the final memory allocator (the one the kernel doesn't know or care about, which is part of the process) would decide which virtual addresses are used for what.

The second "virtual address allocator" is more like a memory manager than an allocator. For example, it might have a set of attributes for each page (e.g. if the page is meant to look like RAM, if the page can/can't be sent to swap space, if the page is part of a memory mapped file, if the page is executable or writeable, etc) and provide a single "change n pages starting at <address> to type <attributes>" function that the third memory allocator uses to do things like changing an area to "meant to look like RAM" or changing an area back to "not meant to look like RAM".


Cheers,

Brendan

_________________
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.


Top
 Profile  
 
 Post subject: Re: Memory Allocation - How it works
PostPosted: Mon Feb 09, 2015 5:31 pm 
Offline
Member
Member
User avatar

Joined: Fri Jan 16, 2015 10:41 am
Posts: 34
Location: United Kingdom
Thanks, everyone. I understand it now! :D
-bace

_________________
"for example, turning off the system’s power through the movement of a large red switch" - the Advanced Configuration and Power Interface Specification


Top
 Profile  
 
 Post subject: Re: Memory Allocation - How it works
PostPosted: Tue Feb 10, 2015 3:25 am 
Offline
Member
Member
User avatar

Joined: Wed Oct 18, 2006 3:45 am
Posts: 9301
Location: On the balcony, where I can actually keep 1½m distance
bace wrote:
Combuster wrote:
Roflo wrote:
Allocating free virtual pages can be done by looping through the page directory and find free pages (or finding free page tables, representing 1024 free pages).
In general, if you want map something into virtual space without knowing which address to use for it or if it's free, your logic is flawed to start with.

So, is it the program's job to choose where the physical memory is mapped to in the virtual address space? That doesn't seem right...? :?


If you need more stack space, it has to go next to existing stack, not some random address in memory.
If you need a few MB of RAM allocated for some data, you want that in one sequence, not in 4K chunks in random places in memory.
For the address of everything else you find in a typical program, try running objdump -h on any binary you have.

_________________
"Certainly avoid yourself. He is a newbie and might not realize it. You'll hate his code deeply a few years down the road." - Sortie
[ My OS ] [ VDisk/SFS ]


Top
 Profile  
 
 Post subject: Re: Memory Allocation - How it works
PostPosted: Tue Feb 10, 2015 4:04 am 
Offline
Member
Member

Joined: Fri Jan 30, 2015 4:57 pm
Posts: 215
Location: Germany
Combuster wrote:
If you need more stack space, it has to go next to existing stack, not some random address in memory.
If you need a few MB of RAM allocated for some data, you want that in one sequence, not in 4K chunks in random places in memory.
For the address of everything else you find in a typical program, try running objdump -h on any binary you have.


If the program needs a space for memory mapped files or something else, the virtual memory manager would look through the address space of the program and find a fitting sequence of pages. Where is the problem? :)


Top
 Profile  
 
 Post subject: Re: Memory Allocation - How it works
PostPosted: Tue Feb 10, 2015 4:13 am 
Offline
Member
Member
User avatar

Joined: Wed Oct 18, 2006 3:45 am
Posts: 9301
Location: On the balcony, where I can actually keep 1½m distance
So it takes the first free area in memory, and return a "valid" null pointer? Pick the spot immediately after the heap so that you can't do any future malloc() calls? Put it halfway into another memory-mapped file because only the first few bytes were read and subsequent pages weren't yet loaded and mapped into memory?

_________________
"Certainly avoid yourself. He is a newbie and might not realize it. You'll hate his code deeply a few years down the road." - Sortie
[ My OS ] [ VDisk/SFS ]


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 11 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: No registered users and 26 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group