kmalloc implementation!

[amirsadig]

I have written the basic part for my OS ( small video driver, keyboard) and now I try to concenrate on memory mannagement. I use now only segmentation without paging which it is simple and I can begin with it until I can understand paging.
to load process image I need to write kmalloc ( for internal use in kernel) and malloc ( for application).
I would like to know the mechanism of memory allocation.
It will be very good if there exambles also.

[amirsadig]

I can locate a memory like ( corect me if I wrong):

char *var;
or void *var;

let see this function ..
void *kmalloc(int size)
{
char *blk, *ret_val;
ret_val = blk + size;

return ret_val;
}

You see here there is no check if there is no available memory. How could I know that there is no memory available?

[crazybuddha]

Make a list of available memory "blocks". As a request is made, and the pointer to a memory block is given out, the block(s) is removed from the "free list". When free() is called, the blocks are returned to the free list. A trivial implementation of malloc() is given in K&R. Also DOS used a similar scheme of block headers knowing the size of a block and the location of the next available block, although it went in order.

The available memory is whatever the descriptor for the process says it is (base address and limit). If you need more, the limit will have to change through a system call.

In the K&R example (which may be true of other standard library implementations), free() does not return memory to the OS. It merely puts it back on the free list.

[amirsadig]

Ok, and how can I calculate the physical memory size( for examble 254Mb), so that I can create the blocks I need not these defined in the describtors.

[crazybuddha]

If I understand correctly, you want to know how much memory there is. See this thread :

http://www.mega-tokyo.com/forum/index.p ... readid=825

[Pype.Clicker]

I can locate a memory like ( corect me if I wrong):

char *var;
or void *var;

let see this function ..
void *kmalloc(int size)
{
char *blk, *ret_val;
ret_val = blk + size;

return ret_val;
}

You see here there is no check if there is no available memory. How could I know that there is no memory available?

You are definitively wrong ... adding a value to an undefined pointer never returned a free block! if you think it does, then consider looking back at how your C code is translated in ASM before continuing writing an OS !!!

however, you can have simple "bottom-up" allocation using the following code

void* free; //<- initialize this with a block of free size obtained by any
void* end_of_free_mem; // detection technique

void* bottom_up_alloc(int size) {
void *ret=NULL;
if (free+size<end_of_free_mem) {
ret=free;
free+=size;
}
return ret;
}

But note that there's no simple way to implement "free" using this technique. However, it can be very handy at early stage (before your system is ready enough to have a full memory system (the current alloc() function can be very easily translated into an ASM one that won't be much longer .

It can also be useful if you just need to allocate blocks of memory that aren't prone to free (like parts of your kernel loaded dynamically, etc.)

[Pype.Clicker]

http://www.openbg.net/sto/os/xml/memory1.html seems to be a quite complete and comprehensive tutorial (though quite long) on the problem of memory management ...

[Tim]

Yep, although note that, at the moment, this is missing a proper description of malloc and free.

[Neo]

isn't it worse to allocate memory from the tail-end of a free block rather than the head-end?
of course the allocation is faster but won't the fragmentation be greater? Any ideas on this? or anyone has a better idea?

(thought i'd add this here for some answers) :-\

[Pype.Clicker]

maybe i should get those boring statistic course back, but i hardly see how picking one end rather than the other can augment fragmentation ...
One thing is certain: by picking the tail-end, you're less likely to be able to size-up your component without moving it (realloc -- d4rk s1de c0ding ...)

[Neo]

you're less likely to be able to size-up your component without moving it (realloc -- d4rk s1de c0ding ...)

what component? free block or allocated one?

[Schol-R-LEA]

You may want to refer to this thread, regarding tracking memory blocks, esp. the zip file attached to the last message This mapping method is probably too simple for a system memory allocator, but for process-local allocation it should be acceptable. The first-fit algorithm it uses is also inadequate; a worst-fit (i.e., always allocate from part of the largest block of available memory) is probably best, as it should minimize fragmentation.

Unfortunately, this one does not address the issue of kernel versus user memory; it is probably better to have a system-wide memory manager that handles page management, and then let each process have it's own memory allocation/deallocation functions within their process local address space. The local memory allocator would act as if the whole address space is available, with the system page manager handling the actual mapping of logical addresses to physical memory.