New & Improved Memory Manager!

Here's something I was supposed to upload weeks ago - a better version of my memory manager (it would have been up sooner if ION wifi worked more often... I never remember this stuff when it does!) This one doesn't partition the available memory on startup - it dynamically sizes blocks, and provides the following replacements for the malloc.h functions:

qmalloc()

qfree()

qcalloc()

qrealloc()

Here is the source:

qmalloc.c

qmalloc.h

I've just used a volatile for locking so it's not threadsafe (read/write may get interleaved.) It should run basic applications without crashing though. See for yourself: Remove 'q' from the function names, compile it to a shared object and replace your system malloc.so on Linux. Alternatively, in your Bash profile you can set LD_PRELOAD to point to this shared object.

As for performance, this is faster than GCC's malloc for simple usecases.

On an unrelated note, if you're one of the unfortunates who have a PSP-2006 G (or any of the PSP 3000s), and want to play homebrew games, here are two useful links. The process has been tried successfully on two different PSPs. Tinkering with the PSP is risky so I'm glad Ishan (roomie) shared what he knew about it.

Partitioned Memory Manager

Hello world!

This blog will hopefully be a place where I can share code with friends, talk about programming and technology related stuff, and serve as a repository for my past stuff when I need it later...

To start off, here's something I worked on a while back: A memory allocator that implements the C functions nmalloc and nfree (which basically do the same thing as malloc and free in malloc.h).

nmalloc.c : http://pastebin.com/f72460c04

nmalloc.h : http://pastebin.com/f4a8b27bc

Memory is divided into many partitions by the function nmalloc_init. Each partition has an associated block size. All blocks within one partition have the same length. While this leads to internal fragmentation, it avoids the overhead involved in managing blocks of variable length. The blocks within a partition are chained into 2 linked lists – the Used list and the Free list. Each partition has it’s own pair of linked lists. (The layout of the partitions is provided by the calling program)

If you already know the sizes of objects that will be used in your program, it speeds up allocation considerably. Unfortunately it has considerable space overhead, and isn't exactly thread friendly. I haven't optimised it because the performance was good enough for my purposes :-

O(1) allocation and deallocation when memory partitions are empty, since operations are more or less independent of number of blocks etc. (Typical delay: 2-6 µs)

O(n) allocation and deallocation when partitions start filling up, since smaller blocks must be merged. Time taken becomes proportional to size requested.