Programming challenge: dynamic memory allocator

[GARTHWILSON]

I don't have any interest in the "challenge" per se, but I'm interested in the discussion, to pick up a new tool. I've imagined dynamic memory allocators for years but never needed them urgently enough to spend the time to figure it out. For the uses I imagine, there's no particular need to do it extremely fast.

[Rob Finch]

Looks good Arlet. Economical and efficient.

For a heap management I've been using a header structure like this (16 bytes on a 32 bit machine):

Code: Select all

// This structure is only known to the memory routines.

typedef struct tagMEM {
	int checkstr;
	int size;
	struct tagMEM *next;
	int resv;
} MEM;

checkstr is a four byte ascii string 'MBK' (3 chars plus 0). Checkstr helps in cases of writing too much data to a buffer.
size is the size of the memory allocation including the header.
next is a pointer to the next available block of memory
resv is four bytes padding reserved.

Both the size (which is rounded to size of the header) and a pointer to the next block are maintained. This is a little bit
redundant but may have been done to improve performance.

The memory functions maintain a semaphore for thread safety.
On a free() the operation has to chase down the chain representing the free list as blocks need to be maintained on the list
in memory address order.
Free() combines neighbouring blocks into a larger one.

Code: Select all

// Free a block of memory
void freeMem(void *m)
{
	MEM *p;
	MEM *prev;
	MEM *next;
	MEM *mem;

	if (m==null)
		return;
	mem = &((MEM*)m)[-1];
	if (mem->next)	// is block already free ?
		return;
	spin_lock(&sfFreeMem);
	p = freeMemList;
	if (p==null) {
		freeMemList = mem;
		mem->next = 0;
		spin_unlock(&sfFreeMem);
		return;
	}
	for (prev = null; p && p < mem; prev = p, p = p->next);
	if (!prev) {
		mem->next = freeMemList;
		freeMemList = mem;
	}
	else {
		mem->next = prev->next;
		prev->next = mem;
	}
	next = mem->next;
	// Can it be combined with next ?
	if ((char *)mem + mem->size>=(char *)next) {
		mem->size = mem->size + next->size;
		mem->next = next->next;
	}
	// Can it be combined with the previous ?
	if ((char*)prev + prev->size>=(char *)mem) {
		prev->size = prev->size + mem->size;
		prev->next = mem->next;
	}
	spin_unlock(&sfFreeMem);
}

allocMem() uses a first fit algorithm so I've not shown it. I'll have to re-write it for the challenge.

[Arlet]

First version on STM8 is surprisingly quick. 76 cycles for alloc() call with clean heap. Even though the CPU supports 24 bit addresses, I'm only using 16 bit pointers, because there are no devices that have so much RAM.

[barrym95838]

Arlet, would it be against your challenge rules to provide us with your reference source, so we can use it as a starting point for our own versions? There are several high-level examples floating around the www, but I would be more comfortable with something from you. One possible method I imagined would be to grow the alloc'd blocks up from the lowest possible heap address and grow the headers down from the highest possible heap address, but that would require knowing and claiming the heap's maximum size before using it, and that might not be as "dynamic" as it should be, especially if the heap is supposed to co-exist politely with other dynamic resources.

Mike B.

[Arlet]

Here's my C source code and the ARM Cortex M4 assembly version

Note that this the 32 bit version. If you have any questions, let me know, and I'll be happy to explain.

[Arlet]

A small optimization would be to replace the 2nd size field with a pointer to the beginning of the block. That would save a subtract in the free().

Edit: oops, no, that won't work because the code needs the MSB for the flag.

[barrym95838]

I edited my post above while you were posting, so I'll repeat it here:

Quote:

One possible method I imagined would be to grow the alloc'd blocks up from the lowest possible heap address and grow the headers down from the highest possible heap address, but that would require knowing and claiming the heap's maximum size before using it, and that might not be as "dynamic" as it should be, especially if the heap is supposed to co-exist politely with other dynamic resources.

Am I making any sense?

Mike B.

[Arlet]

For the purpose of the benchmark, I've assumed a fixed-sized heap, but it would be nice if the code could be easily modified to allow for a dynamically growing heap.

[Arlet]

Note that on 65(C)02 and similar 8 bit targets, there's a requirement that the allocator works with up to 64kB of memory, and also allows allocating all of the heap in one call (minus a few bytes of necessary bookkeeping).

[barrym95838]

Okay, so you see where I'm trying to go with this. For some of the "torture tests" I imagined you might specify later, it would be nice to keep the fixed-width headers separate and sorted for speed. It could still be done "dynamically", but would require keeping the header structure at the top of the allocated blocks and moving it every time the heap grew or shrank.

Mike B.

[Arlet]

Whether there will be "torture tests" depends on the implementation. For instance, my free() is constant time, with 4 slightly different variations. It's easy to measure all 4 types, and just list the cycle times, without any need for further testing. For the malloc() the only factor is the length of the free list, so you could specify the timing as A + n*B, and be done with it.

If your implementation allows some similar method, we can just compare these results directly. Testing with realistic data is hard, because there's more than one realistic pattern. A BASIC string handling package will have a totally different pattern as a compiler, or a network protocol.

[barrym95838]

My initial sketch would only require a heap pointer and then a single address field at the top of each associated block. The block addresses can only be even, because they are stored in the field shifted 1 bit to the right, with the high bit as a used/unused flag. Since the list is only singly-linked, free() has to traverse part of the list to keep track of a potential unused previous block, but it also adds a tiny bit of security, in that it can reject an invalid free() pointer instead of instantly corrupting the heap. Of course, it would still be ridiculously easy for the users of alloc() to corrupt the list by writing outside their boundaries ...

Mike B.

[Arlet]

Quote:

The block addresses can only be even, because they are stored in the field shifted 1 bit to the right, with the high bit as a used/unused flag

How about using the low bit as the flag, and just clearing it when you need the address ? Maybe a little faster.

[barrym95838]

You may have a point, but I think that I'll pretty much always need the address in my scheme, and ASL (ROR) BCC/BCS might be more economical than the alternative. It's still a bit in the early stages, but I would like to find enough time to write NMOS 6502 and VaporMOS 65m32 versions. I am doing the 'm32 version first, because it fits so well with that tiny little creative part of my brain. The '02 translation will follow, and that will be the only one I'll be able to test on real hardware, because I haven't yet compiled my 'm32 simulator. It's going to be difficult to track my development time, because I'm just daydreaming about the details whenever I get a chance. I have to go to work now, but I'll try to post a few sample heap diagrams tonight.

Mike B.

[barrym95838]

Okay, here's how I'm going to attempt it. Addresses and addressable cells are 32-bits wide here:

Code: Select all

heap_init();

                 address     contents
             ---------------------------
HEAPBASE --> |  0f000000  |  90000000  |  (high limit value for hp)
             ---------------------------
             |  0f000001  |  0f000002  |  (current value of heap pointer)
             ===========================
   hp   -->  |  0f000002  |  ????????  |  (non-allocated space)
             ---------------------------

a = malloc(1);

                 address     contents
             ---------------------------
HEAPBASE --> |  0f000000  |  90000000  |  (hl)
             ---------------------------
             |  0f000001  |  0f000004  |  (hp)
             ===========================
    a   -->  |  0f000002  |  ????????  |  (allocated cell a[0])
             ---------------------------
             |  0f000003  |  07800001  |  (header for block a)
             ---------------------------
   hp   -->  |  0f000004  |  ????????  |  (begin non-allocated space)
             ---------------------------

b = malloc(2);

                 address     contents
             ---------------------------
HEAPBASE --> |  0f000000  |  90000000  |  (hl)
             ---------------------------
             |  0f000001  |  0f000008  |  (hp)
             ===========================
    a   -->  |  0f000002  |  ????????  |  (allocated cell a[0])
             ---------------------------
             |  0f000003  |  07800001  |  (header for block a)
             ---------------------------
    b   -->  |  0f000004  |  ????????  |  (allocated cell b[0])
             ---------------------------
             |  0f000005  |  ????????  |  (allocated cell b[1])
             ---------------------------
             |  0f000006  |  ????????  |  (extra allocated cell b[2])
             ---------------------------
             |  0f000007  |  07800002  |  (header for block b)
             ---------------------------
   hp   -->  |  0f000008  |  ????????  |  (begin non-allocated space)
             ---------------------------

c = malloc(1);

                 address     contents
             ---------------------------
HEAPBASE --> |  0f000000  |  90000000  |  (hl)
             ---------------------------
             |  0f000001  |  0f00000a  |  (hp)
             ===========================
    a   -->  |  0f000002  |  ????????  |  (allocated cell a[0])
             ---------------------------
             |  0f000003  |  07800001  |  (header for block a)
             ---------------------------
    b   -->  |  0f000004  |  ????????  |  (allocated cell b[0])
             ---------------------------
             |  0f000005  |  ????????  |  (allocated cell b[1])
             ---------------------------
             |  0f000006  |  ????????  |  (extra allocated cell b[2])
             ---------------------------
             |  0f000007  |  07800002  |  (header for block b)
             ---------------------------
    c   -->  |  0f000008  |  ????????  |  (allocated cell c[0])
             ---------------------------
             |  0f000009  |  07800004  |  (header for block c)
             ---------------------------
   hp   -->  |  0f00000a  |  ????????  |  (begin non-allocated space)
             ---------------------------

free(b);

                 address     contents
             ---------------------------
HEAPBASE --> |  0f000000  |  90000000  |  (hl)
             ---------------------------
             |  0f000001  |  0f00000a  |  (hp)
             ===========================
    a   -->  |  0f000002  |  ????????  |  (allocated cell a[0])
             ---------------------------
             |  0f000003  |  07800001  |  (header for block a)
             ---------------------------
    b   -->  |  0f000004  |  ????????  |  (freed cell b[0])
             ---------------------------
             |  0f000005  |  ????????  |  (freed cell b[1])
             ---------------------------
             |  0f000006  |  ????????  |  (extra freed cell b[2])
             ---------------------------
             |  0f000007  |  87800002  |  (header for freed block b)
             ---------------------------
    c   -->  |  0f000008  |  ????????  |  (allocated cell c[0])
             ---------------------------
             |  0f000009  |  07800004  |  (header for block c)
             ---------------------------
   hp   -->  |  0f00000a  |  ????????  |  (begin non-allocated space)
             ---------------------------

free(a);

                 address     contents
             ---------------------------
HEAPBASE --> |  0f000000  |  90000000  |  (hl)
             ---------------------------
             |  0f000001  |  0f00000a  |  (hp)
             ===========================
    a   -->  |  0f000002  |  ????????  |  (freed cell a[0])
             ---------------------------
             |  0f000003  |  07800001  |  (unlinked header for freed block a)
             ---------------------------
    b   -->  |  0f000004  |  ????????  |  (freed cell b[0])
             ---------------------------
             |  0f000005  |  ????????  |  (freed cell b[1])
             ---------------------------
             |  0f000006  |  ????????  |  (extra freed cell b[2])
             ---------------------------
             |  0f000007  |  87800001  |  (header for freed block a:b)
             ---------------------------
    c   -->  |  0f000008  |  ????????  |  (allocated cell c[0])
             ---------------------------
             |  0f000009  |  07800004  |  (header for block c)
             ---------------------------
   hp   -->  |  0f00000a  |  ????????  |  (begin non-allocated space)
             ---------------------------

The header for each block is the address of its beginning divided by two, with the high-bit-set indicating "freed".

Mike B.