coding a kmalloc()/kfree()

[aladdin]

my actual kmalloc() uses a bitmap to store information about used and free data, but now I'm thinking about a new idea, and i want to have your opinons.

i don't want to use slab algorithm (like linux), since it's too complicated for my littme OS.

my idea is to use a page to store chained list of free spaces
and tags to store information about used areas of memory

each used tag will point to the next used tag, and to free neighbors

each free area pointer will store the base, and the size of free area....

i thing , this way can limit internal defragmentation.

but what about performance ??

[Neo]

I hope youve read Tim Robinson's tutorials. they do give you about some ideas about mem management. The struc use use is also referred to (IIRC) and gives you its demerits, BTW is yours with refrence to physical memory pages or variables sized blocks??

[aladdin]

it's about variable sized blocks, the tag contain the size of the allocated block, and the base adress can be calculated by adding the tag's size to its base adress.

[Neo]

Should have made myself clearer.
Do you have a low-level manager already that allocates pages (some fixed size like 4KB/8KB etc) or are you tryin to allocate physical memory in variable size blocks straight away?
The demerit I was talking about is that if you overwrite any part of the header in any block the whole scheme comes crashing down (so this wont be very good for physical mem allocation IMHO).
Performance in terms of speed of allocation will of course be faster than the bitmap scheme.

[aladdin]

yes of course, i have a page allocator (4Kb-4Mb), but now i'am working on allocating blocks smaller than 4kb.

[Tim]

The best way is to download Doug Lea's malloc (dlmalloc), put it in your kernel, and forget about it. dlmalloc is really good, but to write it would be really boring. You're not here to write boring code, are you?

Alternatively, look at a copy of Kernighan & Ritchie. There is a simple, neat malloc/free implementation there.

K&R's scheme is to keep a linked list of free memory blocks. To allocate a block, walk the list til you find a block big enough. If you reach the end of the list (or the list is empty), ask morecore for a block at least as big as you need and start again. Once you've found a block, split it in two. Put the second half back in the free list and return the first half to the caller.

To free a block, walk the free list til you find a block adjacent to the block you're freeing. If found, merge the two blocks into one. If not found, add the block to the end of the list.

[Neo]

I wrote my own malloc() and free() (althoug i cant say im totally sure their error-free ). The main reason i did this is that im not trying to create a very good OS or something, but here to learn and the best way IMHO is to dirty my hands.
However i must add that it took a lot of drawing and figuring out and as i said im still not very proud of it (but it works). and yeah i finally looked at K & R to get an idea and was surprised to see that mine looked quite similar logic-wise (not as efficient though ??? ).
Well enough rambling...
@alladin: i hope you have a working mcore(), mapping function etc. (discussed in Tim's tutorial) before tryin out this i.e if you are using paging (you are aren't you?)

[aladdin]

I agree with u neo, i want to learn how to code a working malloc(), and don't want to copy/past an existing one.
since I'm not working on a new Linux or WindoZZ

[Pype.Clicker]

checking the documentation of DLMalloc may be a very good starting point for implementing YourOwnMalloc ... And checking the chapter 8 of my report on Clicker might be another (though probably not as good and useful for french-speaking people only) starting point.

[mr. xsism]

pype, that lnik isnt valid. I only see up to chapter 7 on SF site also.

make sure you have it uploaded 1st :d

[Solar]

I agree with u neo, i want to learn how to code a working malloc(), and don't want to copy/past an existing one.
since I'm not working on a new Linux or WindoZZ

One, the implementation of malloc() / free() has little to do with the OS, or even the CPU, and lots to do with managing lists and implementing smart algorithms.

Two, you usually learn much more by also looking at previous, "known-good" art. dlmalloc() is definitely worth a look, since it's "production grade", i.e. all the silly design bugs taken out.

[Pype.Clicker]

pype, that lnik isnt valid. I only see up to chapter 7 on SF site also.

make sure you have it uploaded 1st :d

doh ? it worked for me ... maybe using another mirror will help ... 'UNC' worked fine, as well as 'belnet' ...

[Neo]

I agree with u neo, i want to learn how to code a working malloc(), and don't want to copy/past an existing one.
since I'm not working on a new Linux or WindoZZ

One, the implementation of malloc() / free() has little to do with the OS, or even the CPU, and lots to do with managing lists and implementing smart algorithms.

Two, you usually learn much more by also looking at previous, "known-good" art. dlmalloc() is definitely worth a look, since it's "production grade", i.e. all the silly design bugs taken out.

Still there's nothing like making an effort first on your own first and then looking up others code only when you're stuck.
IMHO this also makes it easier to understand the logic