Lprogster wrote:
With malloc (for the moment) any sized allocation is fine...
Actually, now that I've eaten, I could explain the basic idea of malloc/free.
These two functions (and typically calloc/realloc as well) manage the so-called heap. When a program written in a typical language like C runs, it uses three types of memory: there statically allocate memory, stack, and heap. The situation is typically more or less the same, whether you're in a normal program, or a kernel, though a kernel will have to deal with some more issues, ofcourse.
Statically allocate memory includes the program text, as well as any "global" variables and other data (like anything with "static" qualifier in C) that will exist from the start of the program all the way to the end of it. Normally there are three program segments (not to be confused with hardware segments, which are best ignored) defined: .text which is the program code and often read-only, .data which is any static data with it's initial content defined in the program, and then .bss, which isn't really in the binary, rather only it's size is kept, and at load time the .bss is simply allocated and cleared with zeroes. Then there's often also .rodata (for constant strings) but you can tell your linker to put any .rodata segments into the .text segment of the program.
If you use something like GRUB to boot your kernel, it'll take care of these segments, load .text and .data where they are specified to be loaded (usually 1MB) and clear .bss for you. When your kernel loads a program, it'll do the same for the program in question.
Now, if we always knew how much memory we need, all would be easy. But we typically don't, so there's the stack and the heap. For normal programs stack is normally kept at the end of their address space, though multi-threading complicates matters (you have to place somewhere a stack for each thread). In a kernel, you typically keep an initial stack in .bss, and if we need more stacks (for each thread we have in kernel) we just allocate them from the heap or something. Or maybe allocate pages for them directly. Depends on what you want. But the point about stack, is that once you have a stack, you can allocate/deallocate by moving a stack pointer up and down. A compiler does this for you automatically when you use local variables.
Now, heap is different. Heap is for data which we don't know how much we need, and how long we need it. That's what malloc()/free() are for. Heap normally begins at some fixed adress (after .bss is one option, but for kernel you might want something else) and it's size can usually be grown (map more pages at the end of it). When you malloc() something, it looks around the heap for a free block. If there's none, it asks the operating system (or in case of kernel, your virtual memory manager) to grow the heap, until there's enough space. When you free() something, it marks that area of the heap free, so next time you malloc() something, it can be used.
So how do you do that? Well, as long as we don't need to free() anything, we can simply look at the last allocation we did, and if you asked for 16 bytes of memory, give you the address of the free area, and mark down that 16 more bytes where allocated (advance the free-area pointer by 16 bytes). But in reality you want to free() as well, right?
There's a few options, but easiest is for malloc() to take a block that's a bit larger than what you asked for, write down in the beginning of it how much you allocated, and then give you a pointer to the memory after the "header" that it just wrote. free() can then look what's just before the pointer you gave it, to find the size of the block, and add it to some sort of free-list. Now malloc() first scans the freelist to see if there's already a free block large enough (and possibly splits a too large block, or something) and only if there's no suitable block, it goes and actually allocates new memory.
That's the basic idea at least. In reality, there's a few complications. You typically want to align the blocks at least to pointer size or more (so, say, you want to align to 8 bytes, you round any allocation up until it's a multiple of
. You also might want to keep more than the size. I keep the size of previous block as well, and whether it's allocated, so that I can join two free blocks together. When a block is free, you can use the block itself to keep a linked freelist, but this means you need to have the smallest allocation size fit at least two pointers (so 8 bytes on 32-bit architectures) plus whatever headers you have (say, I have 8 bytes for headers, giving me a minimum blocksize of 16-bytes, of which the client can use
.
You could also keep different free-lists for different sizes, so that if you are looking for a large block, you don't need to scan a free-list full of small blocks that are way too small... and such.
You could search for dlmalloc which is a known-to-be-good malloc. It's page also has a description of how (an older version of it) works, which can be helpful. Then there's also some descriptions of mallocs in books like K&R's C programming language, and various lecture slides and what not, but most of those are not very good. You could also have your malloc()/free() return memory areas back to the kernel when larger areas are freed, but I don't think there's much point doing this before your kernel is advanced enough that this actually becomes an issue.
You could also search the forum for "malloc" as this is not the first (and probably not the best) description I've written about mallocs. I even posted an old version of my own malloc here at some point (was in announcements forum though, I think). I could probably post my improved version some time real-soon-now.
Hope that helps.
...