Hey all, wondering if there exists a heap & memory allocator implementation for the 65816, so that I can use it for a PoC project of mine (Heaps are not my thing of expertise, would be real glad if somebody's already done this for me.)

I only need one bank for the allocator, and preferably it's code should fit in one bank as well, although it's not a strict requirement. Unfortunately I cannot work without the heap, it's a requirement (this is a PoC after all.)

I wrote a simple first-fit malloc type thing recently for the 6502 - however I wrote it in sweet-16, so this may or may not be of-use to you.

I'm currently (slowly) re-writing it in 65816 native code for my '816 system, however I only plan to write the malloc part as the free part will be written in a higher level language. I plan to make it multi-bank, but only have the ability to allocate a max. block size of about 63KB due to some limitations I have for now. It doesn't coalesce adjacent free blocks - that was a task for later...

If you want the sweet-16 version just let me know. (I also wrote my own sw16 interpreter which is a bit quicker than Woz's one at the expense of size)

-Gordon

_________________
--
Gordon Henderson.
See my Ruby 6502 and 65816 SBC projects here: https://projects.drogon.net/ruby/

Welcome, mid! There was a fun thread setting a challenge to write an allocator - you might find some pointers in that discussion.
Programming challenge: dynamic memory allocator

I remember reading that and didn't find any real code which is why I embarked on my own... I started it in 65C02 code and found I was spending a lot of time doing 16-bit manipulations, then the lightbulb moment when I remembered sweet16 - an promptly went down that rabbit hole writing my own implementation of sweet16 which, now that I'm using the '816 I'll probably never use again. Ah well...

Although it was handy having a dozen general purpose 16-bit registers...

-Gordon

_________________
--
Gordon Henderson.
See my Ruby 6502 and 65816 SBC projects here: https://projects.drogon.net/ruby/

Sweet16 is fine, perhaps I'll switch to a pure 65816 one later on as this is only in the prototype stage, but I just want it to work at the moment.

Here it is...



If nothing else it might give you ideas and hints about the structure and so on.

One thing it lacks is 'guard' words - e.g. putting a known word/byte value in the header of each segment allocated and another at the end (not counted in the allocation size, so the caller gets the bytes they ask for). This can be used during free to check for corruption/overflow.

You might want to explicitly set HIMEM (top of heap) and LOMEM (start of the heap) somewhere.

It contains references to RubyOS system calls, but that's mainly for printing debug information, but if you can't work out anything that looks weird just let me know.

Enjoy,

-Gordon

_________________
--
Gordon Henderson.
See my Ruby 6502 and 65816 SBC projects here: https://projects.drogon.net/ruby/

By design, a 65C816 program cannot span banks. When PC reaches $FFFF it will wrap to $0000, but PB will not be incremented. So your allocation code would be forced to fit in one bank (although a long JuMP into the next bank would work). In any case, a 64KB program is huge by 65xx standards, so it's not likely to be a significant issue.

Not knowing how much you know about the 65C816's architecture, I will mention that bank $00 must be used for the hardware stack (or stacks—you can have more than one), direct (zero) page, reset code, and the front end of your interrupt handlers. There are a few other such requirements as well, but the ones I enumerated are most important to know.

As for the heap itself, that can span as many banks as you wish, since during data fetches and stores the 65C816 treats memory as flat space. Somewhere in your POST code you will need to make a determination of how much "extended" RAM (RAM beyond $00FFFF) is present so your allocator can report an "out of memory" error when the heap space has been exhausted.

Let us know how your project is coming along.

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

Yup, that's what I meant. I just don't know how complex a simple memory allocator can get, so I noted that.

I'd say I'm a 4/10 at the 6502, I've dabbled with NES and SNES programming before and only read about it mostly, but I have experience with other architectures (mostly z80 and x86).


Will do (if nothing goes wrong). I may have been a bit ambitious, though, so I don't guarantee anything.

Better to be ambitious and fail than to be lazy and accomplish nothing.

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

I see nothing stopping one from doing all of the above. :-)

_________________
Curt J. Sampson - github.com/0cjs

Okay, let's have a stab at this. I'm going to assume that you pass the 64K data bank in question in DBR - so that absolute addressing lands there - and that you will dedicate the *entire* such bank to be managed by these routines. The code will be quite small, so I'll use RTS instead of RTL; you can add four-byte stubs which consist of "JSR xxxx ; RTL" to permit cross-bank calling if you need it.

The very simplest type of memory allocator is one that can't return any memory on free(). All you need to implement this is a pointer to the next free byte, which you can insert at the beginning of the data bank being managed. This also serves as a (two's complement, negative) counter of how much space is still free, and helps to define an invalid NULL pointer to return when there's not enough memory left: This should be enough to get simple programs running.

However, most good allocators have the ability to free memory and return it to the heap. This at minimum requires a little extra sophistication, in the form of a second counter which tracks the net number of allocations made. When the number of frees equals the number of allocations, you can reset the heap to the empty state: This method is crude in the extreme, but might be useful in limited circumstances due to its simplicity.

Another, more sophisticated approach is to keep all free blocks of memory in a linked list. This means any block can be returned to the heap by adding it to that list. The size of each block must be remembered to make this work, so the overheads become significant; this method should be used to allocate significant chunks of memory, not individual small objects. If the freelist is kept in sorted order, that makes it easier to coalesce consecutive blocks and thus prevent fragmentation, but for simplicity the following code doesn't actually coalesce blocks. I leave coalescing blocks as an exercise for the reader. You could do it on free, in which case you should remember that consecutive blocks may appear before, after, or both sides of a block being freed, and that the block size in the header is two bytes less than the offset between blocks. Or you could do it as a hail-mary pass upon allocation failure, which may be easier to implement (you only have to recursively coalesce a block with a following one) but may also end up with more failures due to memory fragmentation.

(Edited to ensure that the Z flag reflects the state of the X register on return of AllocHeap, to simplify calling.)

The above are by no means the only reasonable approaches to an allocating heap, but they have a reasonable chance of working and are simple enough for hobby use.

I haven't checked your code, but that's a nice writeup! I particularly like the cheapest-possible reclaim, which waits until nothing is left claimed.

As a supplement, here's a routine which coalesces free blocks in the current heap, for use with the third allocator in my previous post. This could be called manually after a sequence of FreeHeap calls which may have left consecutive free blocks, and also upon allocation failure followed by a retry. Or you could just fall through to it from FreeHeap, ensuring the free space is always coalesced at the expense of some performance. As with the rest of this, it's completely untested. I don't even have an '816 running yet…

Jesus, man, I didn't expect that, will test that when I can