What's next for virtual memory management?

[makerimages]

Hi everyone! So, I'm having a bit of a logical block with the development of my virtual memory manager.

Right now I have the identity mapped 1MB set up and paging enabled. What I'm struggling to understand how to implement now, is the logic that comes after a malloc call. More precisely, I've managed to come up with the following questions.

• Where does malloc get the virtual address to return?
• Am I correct in my understanding, that the logic that should happen once the code calls malloc, is something like this?
  • Somehow find the next free virtual address in the address space (how?) What does this address represent? index of page table in dir + index of entry in table?
  • See if that address is already mapped (in the page directory of this process, go over page tables and do What?)
  • If not, add to the page table an entry. Find the next free physical block (but don't access it!), build the entry, and insert it. Access the virtual address to do anything else needed (like get next from a linked list
  • Return virtual address

And if someone wants to help directly, or have a look at what I have (kernel/mem for this post), the link is: https://github.com/SinusOS/Sinus-OS

[onlyonemac]

It goes something like this, after a malloc call:

• Find the next free virtual address. You'll need to keep track of the allocated virtual addresses for each process. If there's anything that needs to be identity-mapped in each process's address space (e.g. your kernel entry point), make sure you record this as "allocated". Remember that you can allocate the same virtual address to two different processes - each process has its own address space and can't see the memory that's allocated to other processes (if you're doing it right, that is).
• Find a physical page (or pages) to map to this address. This is where your physical memory allocator (which keeps track of all physical memory allocations to all processes) comes in. Remember that the physical pages don't have to be allocated contiguously; as long as you're working a blocks of one page, physical memory fragmentation doesn't matter - just find however many pages you need.
• Add your selected physical pages to the page table for the process that requested the memory allocation, mapping them to the virtual address that you've allocated.

You might also want to optimise things by not allocating physical memory straight away but only when the process actually writes to the virtual addresses that you've allocated - that why you're not wasting physical memory on processes that allocate, for example, a large buffer for copying some data but only use a small part of it, or which allocate memory but don't use it straight away (if ever). If you've got support for swapping to disk, you'll need to include that when you're looking for a physical page to map to a newly-allocated virtual page, as if there isn't any physical memory left you'll have to free some up by moving other virtual pages to disk.

[crunch]

"Sinus"....Just why?

On topic, agree with what mac said. There are many ways of keeping tracking of virtual address space, I.e. linked lists, stacks, slab allocators, etc.
For kernel objects, I map a heap to physical pages, and when the heap has reached its top, allocate more physical pages.

If you don't already have a physical memory allocator, I would work on that first.

[Brendan]

Hi,

Right now I have the identity mapped 1MB set up and paging enabled. What I'm struggling to understand how to implement now, is the logic that comes after a malloc call. More precisely, I've managed to come up with the following questions.

• Where does malloc get the virtual address to return?
• Am I correct in my understanding, that the logic that should happen once the code calls malloc, is something like this?
  • Somehow find the next free virtual address in the address space (how?) What does this address represent? index of page table in dir + index of entry in table?
  • See if that address is already mapped (in the page directory of this process, go over page tables and do What?)
  • If not, add to the page table an entry. Find the next free physical block (but don't access it!), build the entry, and insert it. Access the virtual address to do anything else needed (like get next from a linked list
  • Return virtual address

Note: for C, "malloc()" typically uses "brk()" or "mmap()" (or both) to get more memory. This doesn't really change much (it just means that your next question would be where "brk()" or "mmap()" get addresses from). Also note that "how C's standard library works" may be (and I'd be tempted to say "should be") entirely irrelevant - e.g. processes in user-space can be written in any of 100+ languages (where C is only one of many) and you really want something that all possible languages (including those that don't exist yet) can use regardless of how the language and its run-time are designed (and not something that is only designed for one language that is potentially crippled for other languages).

In general, for "what decides which areas of the virtual address space are used for what", people are divided:

• Some people put it in the virtual memory manager (in the kernel), where a thread would ask kernel to (e.g.) allocate some pages and the kernel finds a free place to put the pages and then allocates them.
• Some people put it in user-space, where (e.g.) a thread finds a free place to allocate some pages itself and then ask kernel to allocate free pages at a specific virtual address, and kernel only allocates them (at the address it was told).

The former is easier, but the latter is more flexible. For C it makes no difference (any differences are buried by the C library, so normal C code doesn't need to know).

I do the latter. More specifically, my kernel's virtual memory manager has a function that user-space can use to change the "virtual type" of any area of user-space it likes - sort of like "int change_virtual_type_for_area(void *start_page, int number_of_pages, int new_type);". User-space does whatever it wants with its virtual address space in any way it wants to; which might be "brk()" (which mostly only needs "data_area_top" variable to manage) or something more advanced/complex, or something completely different, or nothing (e.g. pre-determined at compile-time), or 20 different things (in 20 different zones). Note that my kernel's "change_virtual_type_for_area()" is quite dangerous because it does what it's told (and overwrites the old virtual type/s regardless of what they were before). For example, with a single "change_virtual_type_for_area()" you could change the type of every page in user-space to the "not present" virtual type (and then crash because your own code doesn't exist after that).


Cheers,

Brendan

[Boris]

Hi,
Kernel or userland malloc ?

For kernel it is simpler because of how it is easy to talk between kernel components. Plus, you have control over your heap.For example, Since I allow only 1Gb of kheap and I use 2Mb pages for them, i know that I have to manage up to 512 virtual memory entries. So virtual memory allocator looks like two ordered linked lists, one per size, the other per address in vmem. They are statically allocated ( nodes[512] ) I use the by-size list to quickly allocate any amount of contiguous pages , and the by address to quickly free and merge unused blocks.


In short , You need :
* a malloc library that takes and free virtual pages,and allocate chunks of memory in those.
* a virtual pages allocator.
* a physical memory allocator ( I used buddies allocator )

[makerimages]

Allright, If I now understand the Wiki correctly, the virtual address that I return to the process/whatever, is derived from where the resulting mapping is in the directory and table, right?

So, each directory contains 1024 entries, each table the same amount. Table 1 therefore contains the first 4MB - addresses 0x0000-0x3FFFFC. Table two the second 8MB 0x40FFC-0x800FF8. Say the first free entry in the second table is at index 23. According to the wiki, I can calculate the address like so (PageDirIndexOfTable * 1024) + PageTabIndexOfPage. Multiply that by 4 to get the address in KB and then *1024 for it in B. So that turns to (1*1024)+23 = 1047 * 4 = 4188 * 1024 = 4288512 which I return to the process, in hex this is address 0x417000. Am I correct?

[Boris]

your numbers are for your kernel we can't validate them.
But, I advise against iterating those tables in order to find free virtual memory : worse case is 1Gb iterations in 32 bit.
you must create your own data structures.