CX16 HEAP MANAGER for BANKED RAM and VERA VRAM

svenvandevelde · Post by **svenvandevelde** » Sun May 23, 2021 8:15 am

I'm working on a development to optimize the memory management for the CX16, allowing to dynamically allocate and free memory space at run time in CX16 BANKED RAM (BRAM) and VERA RAM (VRAM).

The heap manager is being built using the kickc compiler of @Jesper Gravgaard, and we are working together to optimize this development for a larger audience (later).

The idea came while making my "space game", I really needed a mechanism to dynamically load and free memory in both RAM types on the fly at run time.

The complete source code of the heap manager van be found here:

https://gitlab.com/Flight_Control/kickc/-/blob/CX16_VERA/src/main/kc/lib/cx16-heap.c

This heap manager now allows to dynamically load graphics (files) into BRAM and when not needed anymore, to dynamically free these graphics from memory. Typically such activities would happen when switching between "levels" during gameplay,

or at certain transition moments. The heap manager has not implemented the logic to load the files, but a loader routine using CX16 kernal calls has been made, that uses the heap manager to dynamically allocate memory as graphics files are loaded.

This allows me to design the graphics flexibly, specifying the file properties, and the heap manager will allocate the required memory at run time in memory.

During gameplay or "on the fly", the heap manager covers the needed functionality to dynamically manage the limited memory space in VRAM, for tiles and sprites and other graphic objects.

The heap manager allows to dynamicall allocate required memory in VRAM during gameplay, and free up VRAM memory when the space is not anymore needed, freeing up memory for new graphic objects to be allocated in VRAM, on the fly.

On top, I've added CX16 library functions to copy memory between RAM, VRAM and BRAM. One such important function is to quickly copy memory from BRAM into VRAM. Typically this is used for sprites during gameplay.

In other words, the heap manager allows me to load up the graphics from disk during transition moments, filling the 512/1024/1536/2048 banked memory space in the CX16, which is slow loading.

But then, during gameplay, it allows me to quickly manage the VRAM memory space and copy graphics in and out from BRAM into VRAM on the fly.

The CX16 heap manager has been made with the following requirements in mind:

The heap manager needs a small code footprint, supporting both BRAM as VRAM dynamic memory allocations using the same code base, which is located in RAM.

Programmers will only use the heap manager to allocate larger portions of memory. For smaller dynamic memory allocations, other methods are to be used (like arrays, vectors).

Align the allocated memory with the BRAM BANKS or VRAM BANKS structure. No header information polluting the data. This is also very important to avoid VRAM having any header information! (We don't want sprite or bitmap info polluted with header blocks, do we...)

Minimize the size of the headers, as large headers quickly will consume a lot of memory.

Avoid memory fragmentation, which is resolved by coalescing the freed data blocks.

Relatively fast, but not super fast. Speed for dynamic memory allocation is not an issue. For games, allocating and freeing memory would happen between paused moment.

Use helper function(s) to address the memory, while traversing the memory space.

Easy use for the programmer, and improve the code readability, through a well defined API.

(Later) Allow the heap manager to be used by programmers using other languages, using an assembler library.

The CX16 heap manager has taken the following design decisions:

There are 16 memory segments that can handle the allocation of various data segments in CX16 BRAM and VERA VRAM.

Allocated blocks are aligned to 8 bytes in BRAM and VRAM. This should not be a problem, s

Header information is placed in BRAM, to avoid any HEAP dynamic allocated memory to be placed in CX16 MAIN RAM. So no dynamic memory is allocated in CX16 RAM before 0xA000.

Use handles instead of direct pointers to memory locations. This is important, since CX16 memory in BRAM is banked, and VERA memory cannot be addressed directly anyway! This will also allow for memory compression or re-alloc later. It also avoids the programmers code to have direct pointers being used, instead, using handles, the pointers will be "indirect". This has a small performance impact, but greatly improves memory management flexibility.

The header blocks are separated from the data blocks. This is important for VERA VRAM. Header information placed in VRAM would pollute the graphics!!! We don't want sprites set to be polluted with header information, do we?

Hope that this development will insprire others. Please contact me or @Jesper Gravgaard if the heap manager is of interest to you.

Note that this development is still work in progress and is evolving till i'm satisfied with the design of the overall API.

svenvandevelde · Post by **svenvandevelde** » Sun May 23, 2021 10:38 am

The first that needs to be done, is to define a SEGMENT.

The heap manager allows to administer multiple segments, 16 of them, as dynamically allocatable memory space both in BRAM and VRAM.

In other words, for different purposes, memory space can be subdivided in big chunks of fixed memory locations for different purposes.

An example could be to divide tiles and sprite data as separate chunks of memory.

To define a segment to dynamically administer a memory space in BRAM, use:

To define a segment to dynamically administer a memory space in VRAM, use:

The segments reduce the run-time overhead of heap memory management, as each heap will allocate a header list that contains the information of each heap block that was allocated.

I've carefully considered the options how to administer and where to keep the header information of each dynamically allocated heap block. I've chosen to keep the header information separately

from the heap blocks, as I didn't want heap memory to be polluted with header information. This is very important for the VERA, as memory allocated with be displayed on the screen.

This decision brings a little overhead for the header block memory management, but in reality this overhead is not so much if the amount of heap blocks is kept "small".

Performance overhead will occur when freeing up memory, as the heap manager will coalesce the freed heap blocks.

svenvandevelde · Post by **svenvandevelde** » Sun May 23, 2021 11:07 am

The next step is to dynamically allocate or free memory.

The underlying slide explains the functions heap_alloc() and heap_free().

A couple of examples of the heap_alloc() function.

Example:

    printf("\nTC01: First allocation of header 0[8,\"A:8\"] bytes.\n");

    heap_handle p1 = heap_alloc(s1, 6);

    char* p1_data = (char*)heap_data_ptr(p1);

    heap_header_size p1_size = heap_header_size_get(p1);

    strcpy(p1_data, "A:8");

    heap_dump(s1);

Example:

heap_handle p5 = heap_alloc(s1,8);

strcpy((char*)heap_data_ptr(p5), "E:8");

A couple of examples of the heap_free() function:

Example:

printf("\nTC05: First free of header 5[8,\"E:8\"] bytes.\n");

heap_free(s1, p5);

heap_dump(s1);

Example:

printf("\nTC08: Free of header 1[16,\"B:16\"] bytes,\n");

printf("coalescing to the right with header 2[8,\"C:8\"]\n");

heap_free(s1, p2);

heap_dump(s1);

The next slide explains how to obtain the data from a heap handle.

This is accomplished using the heap_data_ptr() and optionally the heap_data_bank() functions.

A couple of examples of the heap_data_ptr() function.

Example:

char* p1_data = (char*)heap_data_ptr(p1);

heap_header_size p1_size = heap_header_size_get(p1);

strcpy(p1_data, "A:8");

heap_dump(s1);

Example:

heap_handle p5 = heap_alloc(s1,8);

strcpy((char*)heap_data_ptr(p5), "E:8");

The next explains the appliance of the optional heap_data_bank() function.

Example:

printf("\nThe data of p1_data resides in bram bank %x\n", heap_data_bank(h1));

svenvandevelde · Post by **svenvandevelde** » Sun May 23, 2021 11:12 am

Find the complete source code of the examples here:

#include <stdio.h>

#include <string.h>

#include <cx16-heap.h>

void main() {

heap_segment s1 = heap_segment_bram(0, 10, 0xB000, 1, 0xA000 ); // add a segment of 8 banks * $2000 bytes + 1 bank of $1000 bytes;

printf("\nTC01: First allocation of header 0[8,\"A:8\"] bytes.\n");

heap_handle h1 = heap_alloc(s1, 6);

char* p1_data = (char*)heap_data_ptr(h1);

heap_header_size p1_size = heap_header_size_get(h1);

strcpy(p1_data, "A:8");

heap_dump(s1);

printf("\nThe data of p1_data resides in bram bank %x\n", heap_data_bank(h1));

printf("\nTC02: Second allocation of B:16 bytes.\n");

heap_handle h2 = heap_alloc(s1, 12);

char* p2_data = (char*)heap_data_ptr(h2);

heap_header_size p2_size = heap_header_size_get(h2);

strcpy(p2_data, "B:16");

heap_dump(s1);

printf("\nTC03: Third allocation of C:8 bytes.\n");

heap_handle h3 = heap_alloc(s1,6);

char* p3_data = (char*)heap_data_ptr(h3);

heap_header_size p3_size = heap_header_size_get(h3);

strcpy(p3_data, "C:8");

heap_dump(s1);

printf("\nTC04: More allocation of D:8, E:8, F:8, G:16, H:8 bytes.\n");

heap_handle h4 = heap_alloc(s1,6);

char* p4_data = (char*)heap_data_ptr(h4);

printf("p4_data: $%04p\n", p4_data);

strcpy(p4_data, "D:8");

heap_dump(s1);

heap_handle h5 = heap_alloc(s1,8);

strcpy((char*)heap_data_ptr(h5), "E:8");

heap_handle h6 = heap_alloc(s1,8);

char* p6_data = (char*)heap_data_ptr(h6);

strcpy(p6_data, "F:8");

heap_handle h7 = heap_alloc(s1,16);

char* p7_data = (char*)heap_data_ptr(h7);

strcpy(p7_data, "G:16");

heap_handle h8 = heap_alloc(s1,8);

char* p8_data = (char*)heap_data_ptr(h8);

strcpy(p8_data, "H:8");

heap_dump(s1);

printf("\nEnd of alloc memory, press any key to continue to the free memory without coalescing\n");

while(!getin());

printf("\n\nStart Heap position before free memory:\n");

heap_dump(s1);

printf("\nTC05: First free of header 5[8,\"E:8\"] bytes.\n");

heap_free(s1, h5);

heap_dump(s1);

printf("\nTC06: Second free of header 3[8,\"C:8\"] bytes.\n");

heap_free(s1, h3);

heap_dump(s1);

printf("\nTC07: Third free of header 6[16,\"G:16\"] bytes.\n");

heap_free(s1, h7);

heap_dump(s1);

printf("\nEnd of free memory without coalescing, press any key to continue to the free memory with coalescing\n");

while(!getin());

printf("\n\nStart Heap position before free memory with coalescing:\n");

heap_dump(s1);

printf("\nTC08: Free of header 1[16,\"B:16\"] bytes,\n");

printf("coalescing to the right with header 2[8,\"C:8\"]\n");

heap_free(s1, h2);

heap_dump(s1);

printf("\nTC09: Free of header 7[8,\"H:8\"] bytes,\n");

printf("coalescing to the left with header 6[8,\"G:16\"]\n");

heap_free(s1, h8);

heap_dump(s1);

printf("\nTC10: Free of header 3[8,\"D:8\"] bytes,\n");

printf("coalescing to the left with header 1[8,\"E:8\"],\n");

printf("coalescing to the right with header 4[24,\"B:16\"].\n");

heap_free(s1, h4);

heap_dump(s1);

printf("\nTC11: Allocate new header of 32 bytes,\n");

printf("splitting header 3[40,\"E:8\"] into free header 4[8,\"E:8\",7,7],\n");

printf("and used header 3[32,\"I:32\",0,5].\n");

heap_handle p10 = heap_alloc(s1, 32);

char* p10_data = (char*)heap_data_ptr(p10);

strcpy(p10_data, "I:32");

heap_dump(s1);

printf("\nTC12: Allocate blocks of 8 bytes.\n");

heap_handle p11 = heap_alloc(s1, 8);

strcpy((char*)heap_data_ptr(p11), "J:8");

heap_dump(s1);

printf("\nTC13: Allocate blocks of 8 bytes.\n");

heap_handle p12 = heap_alloc(s1, 8);

strcpy((char*)heap_data_ptr(p12), "K:8");

heap_dump(s1);

}

The example implements a heap management scenario, which is graphically illustrated below.

Sven

SlithyMatt · Post by **SlithyMatt** » Sun May 23, 2021 2:29 pm

Why would you want a VRAM heap?

svenvandevelde · Post by **svenvandevelde** » Sun May 23, 2021 2:57 pm

This heap manager now allows to dynamically load graphics (files) into BRAM and when not needed anymore, to dynamically free these graphics from memory. Typically such activities would happen when switching between "levels" during gameplay,

or at certain transition moments. The heap manager has not implemented the logic to load the files, but a loader routine using CX16 kernal calls has been made, that uses the heap manager to dynamically allocate memory as graphics files are loaded.

This allows me to design the graphics flexibly, specifying the file properties, and the heap manager will allocate the required memory at run time in memory.

During gameplay or "on the fly", the heap manager covers the needed functionality to dynamically manage the limited memory space in VRAM, for tiles and sprites and other graphic objects.

The heap manager allows to dynamicall allocate required memory in VRAM during gameplay, and free up VRAM memory when the space is not anymore needed, freeing up memory for new graphic objects to be allocated in VRAM, on the fly.

On top, I've added CX16 library functions to dynamically copy and set memory and RAM, VRAM and BRAM. One such important function is to copy memory from BRAM into VRAM. Typically this is used for sprites during gameplay.

In other words, the heap manager allows me to load up the graphics from disk during transition moments, filling the 512/1024/1536/2048 banked memory space in the CX16, which is slow loading.

But then, during gameplay, it allows me to quickly manage the VRAM memory space and copy graphics in and out from BRAM into VRAM on the fly.

Scott Robison · Post by **Scott Robison** » Sun May 23, 2021 3:00 pm

27 minutes ago, SlithyMatt said:

Why would you want a VRAM heap?

If you are trying to have multiple programs (multi-processing/tasking/threading, take your pick) it is useful to have a way for those processes, each of which might want to use VERA, to communicate which blocks are in use.

These are of course advisory only on a system without hardware memory management and easily ignored by ne'er do wells, but it can be handy. I've been working on similar things (though less so in VRAM, my idea being to allow "multi-tasks" to write to a virtualized VRAM that can be swapped over on demand when that process is the foreground process).

BruceMcF · Post by **BruceMcF** » Sun May 23, 2021 3:10 pm

25 minutes ago, SlithyMatt said:

Why would you want a VRAM heap?

In assembly or in C? In C, it seems like it would be to organize the use of the space in the VRAM and tell the C compiler what kinds of information you want to go where. If, that is, you want to write screen drivers for Vera in C.

Mind, writing a screen driver for Vera in C is not the kind of thing I can imagine doing. It's the kind of thing where, back in the day I used C, I would hope somebody clever had done, and done correctly.

In assembler?

I dunno, I just call the Kernel and it makes the letters go up on the screen, and I say "thank you, Mr. Kernel!" because my mom raised us to be polite.

svenvandevelde · Post by **svenvandevelde** » Sun May 23, 2021 3:19 pm

in C

BruceMcF · Post by **BruceMcF** » Sun May 23, 2021 3:25 pm

2 minutes ago, svenvandevelde said:

In C Bruce. C ... ?. The heap manager does memory management for you in banked ram. It allows to utilize the 512 KB dynamically. And then to dynamically pull the relevant data from bram into vera vram when needed, dynamically. Note that this is graphics of various sizes, bit depth and animation lengths. The memory manager will take care of it.

In C.

Sven

The dot point right near the end of the requirements list, "(Later) Allow the heap manager to be used by programmers using other languages, using an assembler library." is what might trigger assembly language programmers to consider the question.

But an assembly language library to the heap language isn't just for assembly language programmers. It is also, for example, useful for calling the manager from Forth.