Easy 64-bit malloc implementation

[evoex]

Hi all,

I'm currently working on getting more functionality to my user space. So far I've managed to code the kernel without any need for dynamic allocation (except for the way easier fixed-size dynamic allocation, of course), but right now I'd like to add a working malloc to user-space. I do have one I implemented in about half an hour, but it is incapable of releasing memory and it's poor - but it was only to run some tests.
However, I can't be bothered to implement a good/mediocre memory manager myself. I want to focus on other aspects of the programming for now and revisit it for improvement later.
Hence: I want a simple to implement, ready made malloc implementation.

Of course, I started out implementing liballoc (having to ignore loads of compiler warnings). It resulted in some page faults as a result of casting a pointer to unsigned integer back to pointer... But my OS is 64-bits. So, the address was truncated, bad memory was written to, and the whole thing came down to a halt.
I tried fixing it by changing the casts to uintptr_t, as they should have been in the first place. It seemed to allocate memory properly, but I did 20 malloc(123) calls, and this ended up in 40 calls to liballoc_alloc(16), which can't be right.
So, liballoc seems no good for 64-bits (perhaps this is worth mentioning on the Wiki - it doesn't seem to be mentioned anywhere else).
DLMalloc seems far from easy to implement, as do the others mentioned on the Wiki (http://wiki.osdev.org/Memory_Allocation). Perhaps I'm wrong here, but it does seem to require a lot of interfacing, rather than the 4 functions of liballoc.

So, what is the easiest malloc implementation to implement that is at least mediocre in quality? As stated, it's only temporarily, so it doesn't need to be great.
Also, if I have a choice between sbrk, morecore or mmap, what would you suggest? sbrk seems to be... outdated, especially when using paging. Mmap seems to be hard to fully implement, and my goal is not any form of POSIX/Linux compliance, so mmap feels like an overkill, at least for now. That leaves morecore, but I can't find any resources on what it's even supposed to do.
Hence also if you suggest morecore: could you point me to its specifications?

Thanks in advance!

[gerryg400]

K and R has a working Malloc. It's trivially simple and portable.

[kenod]

I ported dlmalloc to my kernel, the only things I had to implement were errno.h, which is extremely simple, a fprintf wrapper that checks for stdout and stderr and then forwards it to printf. I used the meaty skeleton tutorial as basis.
(I also used the following defines)

Code: Select all

#define HAVE_MMAP 0
#define LACKS_SYS_TYPES_H 1
#define LACKS_TIME_H 1
#define LACKS_UNISTD_H 1
#define LACKS_SYS_PARAM_H 1
#define PAGESIZE 4096
#define assert(x) ASSERT(x)

You also need to write sbrk but I think you already did that.
P.S.
I do have a 32 bit kernel, but I think this should work on a 64 bit kernel too

[evoex]

Thanks guys!

@kenod: That is easier than I thought. I'll probably implement it later, but for now I'll go for the K&R malloc, as it's even easier.

@gerryg400: Thanks for the pointer to K&R. Looking it up I immediately found the reference to "morecore", which kind of indicates what it's supposed to do. It's still not thoroughly discussed though; the details remain unclear. Do you have any more references?