All-terrain Memory Allocator wanted!

[madram]

Hi there, may your day overflow with joy,

Is anyone willing to code all or part of the memory manager presented in that page?

It would benefit Orgams, IMPdraw2, AyAy Kpttn, etc, individually and for their cohabitation as well.

I miss time to code it myself. Ok, everyone miss time, but what was meant is I miss time even in the generic-tool time of the utilities-time of my CPC time, loaded with other projects.
Anyway, the main reason is that a collaboration would be much more fun.

Prospective users of this allocator are welcome to ask questions or give suggestions.

Regards,

[madram]

NB : some technical discussion already exist on push'n'pop[\url].

[andycadley]

I think some of the design "guidelines" are counter-productive. For example, #1 prevents in-lining metadata with allocations even though that probably works better in many cases. And the argument that it's better for "alignment" reasons doesn't make a whole lot of sense when the API for memory allocation isn't guaranteeing any kind of alignment anyway. I'm also not entirely convinced that allocations over 16K, or straddling different 16K pages makes much sense either.

Requirement #4 (combined with #3) makes allocation a PITA, since you're going to have to find where you stored the internal data structures every single call to allocation/deallocation because there's no consistent place to store it and nowhere you can even store the location of it. It's not even clear if you're expected the allocation code to also exist within banked RAM, because that's going to be nigh on impossible to work with, given how the CPC banking works.

Requirement #8 seems redundant and flawed. If you've reset the machine, then allocated memory can't still be "allocated", there's nothing running that would have any concept of what had once been allocated to it.

Requirement #9 really makes no sense though, if your program is bypassing the allocator at points then all bets are off. Why worry about a situation a programmer can only create for themselves? And if you've really separated metadata from data (as per #1) then there's no way of having guard bytes to indicate the start and end of allocations, so the only data structure you can know has been corrupted is the entire allocation map at which point all bets are off anyway.

[madram]

Thank you very much for your returns. Let's comment the comments :

Of course the memory allocation API do guarantee alignment : cf mem_alloc_aligned.
In-lining metadata doesn't seem useful in my book, since we refer allocations with 16 bits IDs instead of their addresses. The 'fence' bytes around an allocation remains a good idea, though. Actually I don't mind : any way is fine to me, as long as we can allocate a full 64k page !

By the way, if you limit to 16K allocations, each programmer willing to use bigger ones will have extra work to do. The idea is to propose an allocator powerful enough to avoid re-coding parts of memory management in each program.

To "find where you stored the internal data structures" (#4) : it's quite simple. Agreeing to "bank 0 of last page for internal data" convention : just connect bank &fc (on port 78xx to support 4Mb). Without extra RAM it will mirror &c4 (on port 7fxx). So in all cases it will connect your working bank. Then you can check the signature, the available number of pages, etc.

No, I don't expect the allocation code to live in bank itself. Either in ROM or in base RAM outside #4000-#7fff.

Persistence across reset (#8) : I already do it with Orgams. It's a life saver, and I don't want to drop this feature when other software use extra RAM.

Integrity check (#9) : of course it only concerns internal data. Each program must have its own checks for its data. Orgams already do this, so not only your source is alive after a reset and an OCP ART STUDIO session, but you can be pretty confident it has not been corrupted.

[Prodatron]

Hi Madram, great to see you in this forum!
I didn't recognize this thread before, it's a very interesting project! The memory management in SymbOS doesn't use any pointer structures but just a bitmap for free and reserved 256byte chunks due to the restricted system resources. This bitmap is placed in a static area within the primary 64K, so I had to keep it as small as possible. A FAT-like allocation system or your solution would be nicer, but would require much more ram.
Of course it would be nicer and removes some additional work from the application (which is not that much, only if you start to reserve a lot of small single memory portions). I don't want to allocate a static area of e.g. 16KB only for the memory tables, but I was thinking about a system, which devides the memory table into e.g. 2KB chunks, which then can be spreaded around the whole ram as soon as it grows.
Regarding wording:
- yes in SymbOS a "bank" is 64K, a "block" is 16K I took this definition from the german "Schneider CPC" manual, as there it is described exactly like this. No idea how it is called in the english or french manual.
- a "page" is a 256byte chunk (like the Zero page of the 6502)

[andycadley]

Of course the memory allocation API do guarantee alignment : cf mem_alloc_aligned.

I'd missed that, although I suspect coding it would be a bit horrific. And probably not very efficient either.

Persistence across reset (#8) : I already do it with Orgams. It's a life saver, and I don't want to drop this feature when other software use extra RAM.

But you have to lose it. There is simply no way it can work unless your application can make fundamental assumptions about where things are stored inside the extra RAM.

Say, for example, you allocate some memory for a document and then reset the computer. Then you restart your application. The pointer/allocationID of where that document is stored is now long gone. Unless you're going to try and scan all the banked memory in the hope of maybe finding it again, it's a lost cause. Yes it's easy to do something similar if your app owns all the RAM and knows it can check a certain page to find the data structures it was using, but that's all gone the minute you start potentially sharing memory because anything can be anywhere. At best you have to store some sort of "magic string" somewhere in an allocated block of memory, along with details of all your allocationIDs and information about what they were being used for, at which point you're manually recreating a memory manager on top of the existing one!

Even if you could get around that one, by having some kind of identifier passed to functions to indicate the calling application, you start to run into starvation problems: every time you reset the computer the allocator has to retain allocated memory (even if it was being used for temporary data structures) and slowly but surely that means the amount of available RAM dwindles to nothing. There's no way an application can say "Give me back all the RAM", short of just calling the "Reset the whole memory manager" function, which defeats the entire preserve state after a restart feature anyway.

[madram]

Very valid points have been raised !

It's not that hard to keep persistence with multiple programs.

As you said, each program only need to retrieve a main root node, where subsequent IDs have been stored. It can either be done by :

   
• scanning all the bank for a signature, you're right. It can be very quick (much faster than cleaning the screen). And that's not another layer of memory management, since you don't have to modify memory and besides can assume several properties about this root allocation.

   
• requesting to the manager the first ID ever allocated by the program itself (hence the need to keep track of the caller). With ROM programs, it can be done without passing an extra identifier.

Concerning starvation : temporary/persistent allocations must be distinguishable (I must add a flag in the API).
And the API must also expose "user" RSX, to free the memory of a particular program, or the whole memory. Each individual program shouldn't reclaim memory for itself.

Thank you for your insights. Don't underestimate what a CPC can do with well crafted code !