Printable View
Hi guys. My first post here!
I'm trying to build an OS kernel. Now I would like to allocate memory blocks of fixed size. Since I cannot use standard C libraries, malloc or calloc are not options for me. I was wondering if you guys have any kind of tips or ideas for me. I don't need paging or segmentation or anything. Really basic memory allocation. I'm really stumped.
PS: I'm not asking you to give me the code or anything. Just some tips or ideas. Thanks in advance!
You are aware that building an OS kernel is nowhere near as easy as it sounds, I assume? . . . . Hint: you can't just create a main() function and not use standard C functions and hope to have a kernel. I'll have to assume you know what you're doing. :)
If I were you I'd emulate the standard way of dynamically allocating memory. I believe old UNIX systems used to use a brk pointer to the "top" of the heap, which one could just increment when new memory was to be allocated. Even more simply, you could create a largish static data segment and have a "next available block" pointer within it -- when a new request comes in, return the value of the pointer and increment it. Same sort of idea, I suppose, but I imagine you'll find it a lot easier to deal with a static data segment.
Finally, if you have some sort of stack you can do something really nasty: in your first function you could allocate a large chunk of memory on the stack and then refer to parts of it later on in the code . . . .
I think you'll have to post some more information if you want more meaningful advice.
Thanks for your response dwks! Haha, I'm aware building a kernel is not as easy as it sounds. I should have given more info. I'm building the kernel for the motorola coldfire hardware. I've got switching between a couple of processes working. I want to be able to allocate memory for each process so that they'll use that block of memory for their operations. Once they're preempted, this block of memory should become free or given to another process. I'm still a beginner in C, so I wasn't aware of how to allocate memory without malloc.
Could you please expand on the static data segment? I'm not entirely sure on how to create or access this data segment.
Also, there is a stack, but that solution seems a little too nasty.
Sorry -- I didn't mean to insult your ability. But you'd be surprised how many people ask about creating operating systems who don't know the first thing about it . . . .
The only way to do this directly from C that I can think of is by using the stack (which is admittedly nasty), or by using static memory. Static variables by default go into a static data segment (.bss for zero-initialized memory, .data for uninitialized memory, if you know your Intel segments). So you can create a global variable (or a static one) and it will be accessible all of the time.
I'd suggest declaring a big global array and "allocating" memory blocks from it as if from a pool. If you don't free memory blocks very often, you can just use something like this:
That ignores a lot of issues. It never tries to free any blocks, it doesn't worry about alignment -- e.g. making sure 32-bit ints are aligned on an address which is divisible by 4. (On SPARC you have to use alignment and on Intel it's more efficient if you do -- you may want to find out what the case is for your hardware.)Code:unsigned char malloc_data[MAX_SIZE];
size_t malloc_used; /* automatically initialized to zero */
void *stack_malloc(size_t size) {
void *p = &malloc_data[malloc_used];
if(size + malloc_used > MAX_SIZE) return 0; /* out of memory */
malloc_used += size;
return p;
}
If you know that your blocks of memory are always the same size, you can implement a simple freeing mechanism by maintaining an array of "bools" indicating whether a block of memory is free or not. If the sizes can vary, things are more complicated.
A scheme you could use is to put at the beginning of each free block the size of the block and a pointer to the next free block. Then you just maintain a pointer to the first free block and you can do a linear search for a space large enough when you need more memory. This is really inefficient, of course, and it doesn't try to deal with fragmentation, etc. If you want better schemes you could look into something like a B-tree.
I don't know the actual data structures that are used in memory allocation these days, but I think it's something like a hierarchical tree that divides the memory into slabs, maybe maintaining information about the largest free contiguous block inside a slab, etc.
Memory management itself could keep you busy for years . . . I'd try something simple at first. :)
----
Also, if you're willing to go into assembly, there are many other ways you could achieve this. You could find out the beginning of the static data segment and its size, and fill it up with as much data as you can fit into it, for example.
Dwks, thanks for taking your time to explain to me. Also no offense taken, it was a valid question.
Now, I see what you're saying with the static data segment. However, it seems like freeing these memory blocks can be a hassle if the size of the blocks can vary. I'm talking about fixed partitioning. The memory is divided into equal blocks, but the size of the blocks can vary.
If I use inline assembly with C, could I make a linked list structure of memory blocks. Initialize these blocks to zero at start. This way, a linear search can be done for the next free block. If a block of memory has to be freed, just set the block back to zero. Is this something that seems valid? I know it's probably really rudimentary but I just want something simple here.
What you seem to want to create is a slab allocator, a dedicated memory allocator for identical blocks of memory that get allocated,reallocated and deallocated often. You should read up on the topic on Google.