The Hungry Hippo (MM in Userspace)

[elderK]

Hey people.
Crazy, crazyness. I tell you.

Thing #1: Zenobit1dc0.1 is now multitasking, multithreading in a limited capacity - Ring3 Userspace is working nicely. Only problem is you cant do anything useful yet with the Userspace programs.

So, thats why Im here to ask views on Userspace Memory Management. Do you all use a standard MALLOC ish call within Userspace - and when there isnt a block available, the Malloc stuff makes a call to the OS requesting more memory?

Ive spent a good deal of time handling Memory stuff in the Kernel, but Userspace seems different - a lot different, so any advice/suggestions would be very welcome.

Zenobit sourcecode is available on request, however, there is a LOT of work that still needs to be done before it will actually be anything somewhat useful. (To the user).

~Zeii.

[elderK]

Before I forget - I assume the tracking of the Malloc-stuff is within Userspace?.
The Kernel only has to dish out the appriopriate pages to expand the Userspace Heap, if neccessary?

The actual tracking of the memory in use, free, is up to the Userspace Process, no?

~Z

[Combuster]

Malloc generally involves a system call, however how you decide to do it is up to you. Userspace can track used/free memory. However, to be secure the kernel must keep track of used memory as well in one way or another so that bogus apps can not mess up the kernel by returning the 'wrong' memory. What usually(?) happens is that the kernel keeps track of pages, and userspace splits them in parts and hand them out to the various malloc-calling code snippets.

My kernel hands out pages of memory to the userspace app when requested, after that the program can control for itself where to put it. (to make it easier on the kernel, the memory must be mapped at least once, so when allocating memory the userspace program has to supply an initial location). After that the process can duplicate, move, and unmap pages, as well as sharing them with another address space. The kernel keeps a reference counter, and the page is returned to the kernel when the counter reaches zero (either through unmapping, or through an address space being removed).

Or at least, that's my model. Right now it only supports page allocation, which is enough to build a malloc() function around and get a working environment to write apps for

My current implementation (if you are interested):
[ C Runtime ] [ allocator, part 1 ] [ allocator, part 2 ] [ malloc (from Solar's PDCLib) ]

[deadmutex]

You could also use demand paging. malloc() simply record the memory allocation information in a list somewhere. When the memory location is accessed, it will trigger a page fault. The page fault handler can then commit the missing page to memory. This is useful because pages aren't actually given to apps all at once and it prevents wastage.

[AJ]

Of course, it's all a speed balance too...

The method just described is fine if you are using the memory for, example, some kind of database where you are only going to be accessing certain pages at a time - I guess using the pf handler will work very well.

OTOH, supposing you have a 1GB file that you want to load directly from the HD in to RAM. presumably, causing a PF every time you hit a new page boundary is going to reduce performance (although I guess the HD speed will reduce performance anyway....)

I'm just looking at putting a malloc implementation in to my kernel and haven't decided which route to go down yet.

Adam

[elderK]

Hmm, I figure maybe...

a) The kernel aspect of Userspace MM is simple : A call to claim a Page. This call will simple allocate a page and map it into the Process' Address space. The process itself can share it later on.

b) The actual organization of the Memory that the Process pulls in. Obviously, You are going to need to track this memory somehow. But, in a way that doesnt itself take up a CRAPLOAD of space.

c) Old Zenobit MM routines were Buddy allocation, using Binary search tree. Each node in that circumstance though was 12 bytes. Seems a little pudgy considering we might only be allocating 4-8b....

Processes in Zenobit have 2GB of Virtual space for their use. 3GB+ is Kernelspace.

0-1MB is left unmapped. Mainly because sub-megabyte addresses are used for lots of crazy things Hardware wise (EGA/VGA, Realmode BIOS, etc)

Id need a place to use as Tracking. :/ How did you guys tackle the actual tracking of things? Since "Nodes" in a List, all need space.

~zeii
PS: If I go buddy allocation (which is a nice system, ive used it before), Ill have to choose a minimum granularity (aswell as a maximum). Whats a fair guess - for the smallest size that most people will actually allocate dynamically?

[Solar]

You might want to refer to Doug Lea's "A Memory Allocator", which is about as "canon" an introduction to the subject as it gets.

[elderK]

Okay.. hmm.

So, What? We get a Page from the Kernel... mapped in.
Add it to the bin list thing? When we allocate say, 16 bytes, subdivide it until we get the size we want? The space of the 'blocks' themselves, are the tracking points?

SIZE/STATUS
... dataspace
SIZE

Okay, no problem there.
The header and footer of the block are both 4b.
The Size is turnt into the Status by what? A XOR or something, to show that it is in use?

Hhm..... *ponderponder*

~Z

[Solar]

You apparently missed the link to the (Public Domain) C source of dlmalloc... search the text for malloc.c...

[elderK]

Said it before and ill say it again.

... I like to understand things completely and in detail, before spending an hour or more writing code that ill probably redo.

~Z

[Solar]

Agreed (if you meant reading code you'll probably redo)... but documentation only ever tells you what is being done, and why, but usually not the how. That's what the source is for. (Note that the reverse is also true.)

[mathematician]

c) Old Zenobit MM routines were Buddy allocation, using Binary search tree. Each node in that circumstance though was 12 bytes. Seems a little pudgy considering we might only be allocating 4-8b....

Don't mind me asking, but why use malloc to allocate 4-8 bytes? For that amount of memory I would use a static or dynamic variable.

[elderK]

I wouldnt allocate something so small.
But thats me. What about some newbie?

Thanks for the link Solar.
Sorry I snapped at you. My kittens being a @!#%ing menace and im out of cigarettes to ease the pain.

(Read: She murdered a few pages of my OS Theory book. Its crazy how cats have an appetite for paper...)

~Z