OSDev.org

I'm just a little confused as to how a kmalloc works. I mean, I understand the underlying concept of taking a big 4k page of memory and divvying it up, but I don't quite get if the kernel's heap memory is supposed to be a stack-like deal (where kmalloc is like push and free is like pop) or if the chunks of memory it returns are supposed to stay put and when allocating more memory you have to search for holes in the memory...?

the later. You have to cope with holes in memory. One way to help solve this problem is to use paging which then allows you to move 4kb pages around "virtually". Writing malloc is easy. Writing a good malloc which allows free to work is VERY hard to get right. There's no "correct" way to do it.

Search the net and you'll probally get v. long docs. At bonafide I think there are a few smaller ones. (eg Cottontail method for physical memory)

Good Luck!!

Pete

So if the memory is persistent, how would a function that is being called multiple times consistently access the same information? Would you have to have an initialization function or use statics or what?

Not only that, but how would multiple functions in the kernel share memory?

wangpeng wrote: So if the memory is persistent...

Erm... "persistent" as in "not a stack-like layout but one dealing with holes in memory", or "persistent" as in "recoverable after power-loss", or...?

I think we have a conceptual misunderstanding here, but I'm not sure...

How would a function that is being called multiple times consistently access the same information?

You mean, a "function variable" that keeps its value across multiple calls? That'd be "static", and has nothing to do with kmalloc().

Not only that, but how would multiple functions in the kernel share memory?

When you are in kernel space, you have access to all memory. All kernel functions work in the same address space. You could e.g. declare global variables (with the usual synchronisation primitives to avoid troubles when multiple accesses to that data area overlaps with each other).

Yes, speaking in the very limited terms of kmalloc(), persistent as in has to remain allocated longer than the function is using it. Sorry for the verbal snafu, but it's the best word I could come up with at the time ::)

Thanks for the info however. It's very helpful, I guess I was just looking for a way around using globals because it's rather...looked down upon?

Well, just writing it once again:
- there is data visibility and data lifetime. The visibility (or scope) tells what portion of your code knows the data exists and can access it (is it a local or a global variable).
- The lifetime tells how long the variable will keep its value. C basically supports program-lifetime (i.e. the variable will always have the same value when re-accessed somewhere else) and block-lifetime (the current value is lost when you get out of the block).


The purpose of (k)malloc is to offer the ability for the program to create datas that will live longer than a block, but less time than the whole program. In some way, the heap acts a bit like a memory-mapped filesystem, where alloc create a new file of a limited size and free release the space used by a file for future other files. Those files have no name but addresses stored in pointers.


Over the time, you'll have small (or big) amount of free space 'lost' among the 'files', but the best you can do is reassemble contiguous free blocks in one larger block. You cannot 'defrag' your heap, because your program accesses 'files' through their address and you have no list of 'what should be updated to make the program know the block moved'.

This is merely a 'General Programming' issue, but if you're working in ASM, it may occur that you never used it before.

hmmm ... I 'm considering contributing my small malloc library to Solars pdclib. It of course needs some add ons - like concatenating of adjacent empty blocks (hmmm ... the problem is, I don't consider this a *really* good idea for I use a mixture of best-fit and first-fit algorithm. No need to throw away a perfect good place for another instance of a freed data type. --- or am I utterly wrong?)

@wangpeng: What's speaking against some very well placed global variables? I am using them for some statistics - and the process queues f. ex. are shared among some modules of the kernel.

anyway... wouldn't it be a nice thing to do some Howto with graphics about the topic: Malloc/Free? I'll see then, if I can place something onto my web.

stay safe.

@pype: true this is. and Fragmentation of the heap is something that one just can minimixe but not completely diminish even with the best algorithms.

@solar: imho, if you're wishing to allocate a lot of constant-sized stuff, you should rather go for a 'cell allocator', which will build a 'list of free cells' for a given size and perform alloc/free much more efficiently. New blocks of N cells can be requested through a kmalloc when the 'cache' for free objects is exhausted.

I wouldn't like the kernel to fail loading a module (large kmalloc) because i opened and closed many files just before ... And i'm not sure sweeping the free blocks list and trying to merge them when no large block can be found is a wise politic either ...

@pype: how about a new lib that has a cleaner thread that merges blocks in its time? Doesn't that end up with the best of 2? I put it in the free() function with the idea that when you allocate memory you want to do something, so the user is waiting for you, and when you free memory, you just finished something, so the user doesn't mind a short extra wait.

For application-level alloc's and dealloc's, you might think of a wrapper function that waits for a number of free()'s and then releases them all on the malloc lib, while the user-time flag is true. In that way, all free()s are done in the time the user is typing or clicking, so he wouldn't even notice it (improving performance by another 0.02 percent ). I really like programs that give me the idea I'm in full control

Instead of forwarding a lot of his ideas, I'd rather point you to Doug Lea's homepage at http://g.oswego.edu/. His dlmalloc() is bullet point 4 (out of five) in the "software" section, right on top.

dlmalloc() is used by squid, Cygwin, python, and several other Open Source projects... pretty solid code, and in the very least worth a look. However, be warned - it's more than a screenful of code.

here I am again, back on track *rofl*.

I've put together a small text about malloc(), which might help Sir WangPeng a bit.

check out
malloc for a maybe elucidatiing read. *gg*

stay safe.