OSDev.org

The malloc() function is probably the single function with the biggest optimization potential in a C library. I am at the point where I should implement it in my PDCLib, and would like to hear some opinions.

I could take the very sophisticated dlmalloc(), strip it of the "extras" (as PDCLib aims at providing the standard, nothing more), and adapt it to PDCLib. This would be a significant chunk of work, and I am a bit worried that the stripping of extras might mean that most people will replace the result with their own adaption or implementation.

I could take some solid but less sophisticated implementations, add a few thoughts of my own and create a version of malloc() that is "good enough" for a hobby OS, but not really state-of-the-art. Means, neither this nor that - powerusers would still replace it with their own, and I would still have to invest many hours of work.

Then, I could write a very basic malloc (e.g., a first-fit algorithm that doesn't care about fragmentation), and expect anyone who really wants to use PDCLib to provide their own, better implementation. Easiest for me, but it would seriously reduce the out-of-the-box quality of PDCLib.

What do you think? What would make PDCLib the most useful for you?

I'm not familiar with dlmalloc(), but if the dl stands for "dynamic linking" as it does in dlopen(), then I'd say it's overkill.

Consider the way Windows works -- there is already a user-mode Heap Manager sitting behind the Win32 APIs that can be used by any language run-time. malloc() just wraps the Win32 Heap functions. So, I'd suggest providing a reasonable (but not necessarily sophisticated) default implementation, but allow hooks for each OS' own user-mode heap manager (if it has one).

Colonel Kernel wrote: I'm not familiar with dlmalloc(), but if the dl stands for "dynamic linking" as it does in dlopen(), then I'd say it's overkill.

It stands for Doug Lea. He wrote a Public Domain malloc() that is definitely production-grade, and has spawned many other implementations, including the one in glibc.

Consider the way Windows works -- there is already a user-mode Heap Manager sitting behind the Win32 APIs that can be used by any language run-time.

Same with Linux (sbrk()).

malloc() just wraps the Win32 Heap functions.

It is also probably the major performance bottleneck if implemented shoddily. malloc() is basically a "cache" for the OS heap functions, as to avoid every memory allocation / freeing resulting in a system call. If you want production-grade C/C++ apps, you need the best malloc() you can find.

Shoddy workmanship here leads to reserving more memory than actually required, slow performance, memory fragmentation or all three combined.

The question is, can / should PDCLib provide a production-grade malloc(), should it rest on the shoulders of its users, or should I chose a middle road (which would please neither side)?

well, i'd be advocating for the Doug Lea's implementation if that doesn't mean we don't see you on MT for 3 years ...

Not to fear. Coding work is in the train or (more seldom) on weekends. MT is mostly from the office. ;D

Hi,

I currently have two implementations of a malloc algorithm available if you want. A linked list implementation and a 2^n free-page implementation.

The linked list one is far simpler, slower and reliable with little fragmentation problems. I much prefer this one because it's much more reliable and more predictable. The 2^n free page implementation is fast, a bit complicated and has terrible fragmentation problems for a large amount of small allocations. I wouldn't recommend it.

You're welcome to either under public domain, if you like. My kernel uses the linked-list implementation and my userland is using the free-page allocation but I'm going to either fix it up or replaced it with the list.

Also, porting to any system requires only 4 function implementations: alloc, free, lock, unlock (in functional sense).

If you're interested...

Not necessary as I have two "simpler" implementations and design hints for another two at hand already. But thanks anyway!

Unless the vote swings around or it turns out to be too hard, it looks like I'll try my hands at a full dlmalloc() adaption.

I'd opt for the minimal implementation, if users want they can build off that implementation or use dlmalloc on thier own.

I voted for the simplest one, just make one that works and doesn't cause any errors (watermark for all I care) and make it easy to replace. Then, if you feel like it later on, you can replace it in pdclib itself or just allow all users to replace it themselves.

I'll see how hard / easy adapting dlmalloc() is. If it turns out to be holding me up, I'll probably write up a "barebones" (e.g., first-fit, don't-care-about-fragmentation) malloc() to get going and return to it later.

It's just that I feel like it's cheating.

Solar wrote: It's just that I feel like it's cheating.

If "cheating" gets a full pdclib out sooner, we can start messing with the external interface. You can then replace the innards and improve on it. I'd like that .

Can you give samo good link about dlmalloc(), I have never heard about it before :-\

kataklinger wrote: Can you give samo good link about dlmalloc(), I have never heard about it before :-\

http://www.google.com/search?q=dlmalloc

You could've thought that up yourself. Try the first hit.

Google, dlmalloc, first link. ::)