This is a jolly interesting topic, for lots of reasons. My little 8 bit OS (implemented on a 6809) uses the following simple strategy for its dynamic memory allocator.

Memory blocks are in a single-linked list, with a 5 byte header: Next pointer, a Length value, and a Free boolean. The allocator is a simple "first-fit" (a new term for me, but I like it). Once a block is found that is big enough, it is split with the first half being the new allocated block and the second half being a new free block, if there is sufficient space. I've not tried to implement coalescing of free blocks, but it should be fairly straightforward.

I also wrote a routine to return memory stats: total memory, free memory, and the largest chunk of free memory. That routine ended up being nearly a complex as the malloc()!

I was surprised by how well my simple allocator works, this being the first one (in any language) that I've written. I guess "real" allocators are complex due to handling all the corner cases.

One thing I've wondered is wether the allocator would work better if the "second" half of an existing block was made the allocated block, with the front half being the free remainder? This way the list would find a free block at the start of the list.

So a 6502-related question. My allocator makes extensive use of the 16bit index registers in the 6809, with 16bit comparisons and arithmetic. Writing the code was fairly simple thanks mostly to the 16bit registers. Assuming the kind of allocator Arlet described was written for the 6502, where the 16bit ops would have to be hand-coded, how would it perform? How much harder would it be write?

If anyone is interested in my allocator: https://github.com/aslak3/maxi09os/blob ... memory.asm

I'm really interested in seeing others with similar functionality to my own, especially for the 6502 and 65816.

_________________
8 bit fun and games: https://www.aslak.net/

You're going to need a way to find the start of the previous block for this. The simple way of doing this is to add a 'previous block' pointer to your header and keep both pointers updated when you allocate and free.

The sneaky way is to add a "previous block is free" flag to your "this block is free" byte, and put a pointer to the start of the block at the end of all free blocks. When freeing a block, you check to see whether the previous block is free. If it is, get the pointer to its header from the two bytes before this block.

Blocks have to be a minimum of two bytes for this to work. The easy way of ensuring that is to round all sizes up to an even number of bytes. You can also round just the one-byte allocations up to two, but then you also have to handle e.g. allocating five bytes from a free block of six.



It's not so much the corner cases, but trying to reduce fragmentation and making allocation fast. Your 'first fit' test is about as simple as you can get, but gets very slow if memory is badly fragmented.

My naive idea was to, on free(), look at the next block and see if it is also free, and recombine them if it is. The effectiveness is probably fairly limited, but is at least simple.



Understood. Corner case wasn't the right turn of phrase; I'm just surprised that even a "rubbish" allocator has utility.

The other fantastic feature of these routines is the internals can be completely abstracted from the caller. If I rewrote my allocator in a completely new way, the rest of the code wouldn't have to care.

_________________
8 bit fun and games: https://www.aslak.net/

Hi Aslak3,


I'm curious what the forbid() and permit() routine assembler code is. I assume it's for thread safety.
I did a quick search for the code but couldn't find it.

_________________
http://www.finitron.ca

Hi Rob,



Indeed. It disables task switching by causing the scheduler to return with the same task. A counter is used so calls can be nested. Occasionally it's also necessary to disable interrupts but since I don't do allocations inside ISRs disabling task switching is sufficient.

The code for forbid() is in main/main.asm - which is probably the wrong place. It should be with the scheduler in executive/tasks.asm.

Obviously MAXI09OS is very much a WIP.

_________________
8 bit fun and games: https://www.aslak.net/

If I understand it right, you have a single linked list that contains both free and used blocks. It's a simple strategy, but I think it may get slow in cases where many blocks are allocated.

For instance, I checked an embedded project I'm working on right now, and while the program is running I have 4 free fragments, and 14 allocated ones. I think that's fairly typical, to have more allocated blocks than free ones.

By the way, in your method, do you intend for the top of the heap to go back down if the last block is freed ?

Many, many years back I wrote a short and simple memory allocator that handled blocks of a number of specific sizes, where free blocks were linked into a list specific for this size. There was no block splitting or joining. In a lot of situations, splitting and joining will not be necessary (as long as the memory requirement and distribution of block sizes is relatively constant).

An implementation of this would require only a length field for each allocated block; I placed this just before the actual block. For free blocks, the length field is not strictly necessary, and can be used to link to the next block in the free list instead.

For small allocations, it may be useful to dedicate memory areas (say, blocks of 256 or 4096 bytes) to allocations of a specfic size. Instead of having the length field we could simply deduce the block size from the address, but we would still need to put free'd blocks on a list (or possibly use a bitmap).

The main disadvantage of this is that all allocations will have to be padded up to the smallest block size larger than the allocation request. There is also a fixed overhead (the length field) for each block.

My idea of memory allocator is like a FAT table in a file system.

Have a small block of memory be a bitmap where bit = 1 equals allocated and bit = 0 is free.

On malloc, find the first block that fits the size asked by the application, mark every part with bit 1, and return a point to the first block.
on free, find the address in the bitmap, and mark each block 0 up to the declared size.

(this means that both malloc and free must declare the size of the allocated block).

Not necessarily. malloc( ) can put size of block in first word, and return address of 2nd word.

thats how modern pascal deals with this in strings... with negative indices (for size and ref counting).

Disadvantage of this method is searching for a free block. Can be tricky to do it fast.

I'm still curious to see some 6502 code? Someone must have written a malloc()/free() for the 6502?

_________________
8 bit fun and games: https://www.aslak.net/

I want to throw some code into the mix, but my spare time is extremely limited and sporadic. The older I get, the harder it is to deal with interruptions in my creative flow, and this time is no exception.

@Arlet: yes, if the highest-addressed block is freed, it is merged with any adjacent free block below, then the heap pointer is pointed to the top of the highest-addressed used block + 1.

Mike B.

Yes. I just looked at the source. The malloc() uses first-fit, and free() doesn't do any coalescing, except when block is at top of the heap.

I haven't looked at it in almost two decades, but I'm pretty sure that Daniel Dalman's LUnix had a dynamic memory allocation routine.