Heap Management?

[sweetpalma]

I see no sign of dynamic allocation in source files and all examples are compiled with no_std flag, causing no built-in allocator. So how heap memory is managed in this crate?

[Lokathor]

It's not.

Though if you'd like to submit an allocation impl that'd be neat.

[sweetpalma]

I wonder, is there any ARM-compatible allocator crates around already? I am pretty new to Rust, but I am really surprised that such basic thing as a generic memory allocation needs to be reinvented for each embedded system.

[Lokathor]

There might be some for more modern embedded devices.

The major issues i can think of are:

• there's no memory virtualization unit, so your allocation has to come from specific address ranges, which might not even be the hardware's full size of that range because for example you might have a static mut global, and that has to go somewhere too, so that comes out of your heap budget.
• the amount of memory being managed is very small compared to most devices (around 280kb or so?), so even small fixed amounts of overhead cut into your heap space quickly.

That said, I have not been doing GBA programming much lately, and i have not tried very hard to come up with a good plan, so you might think of something good just by putting your mind to it.

[sweetpalma]

I've done some research and made a small working prototype of heap manager over the top of standard libc malloc/free methods. Currently I'm too shy to share the full project code (still polishing it), but the allocator piece looks like the following:

// _sbrk implementation:
// C reference: https://github.com/eblot/newlib/blob/master/libgloss/epiphany/sbrk.c
static mut HEAP_END: *mut u8 = core::ptr::null_mut();

#[no_mangle]
pub extern "C" fn _sbrk(incr: i32) -> *mut u8 {
	unsafe {
		if HEAP_END == core::ptr::null_mut() {
			HEAP_END = 0x03000000 as *mut u8;
		}
		let prev_heap_end = HEAP_END;
		HEAP_END = HEAP_END.offset(incr as isize);
		return prev_heap_end;
	}
}

// Custom allocator:
struct EwramAllocator;

#[link(name = "c")]
extern {
	fn malloc(_size: usize) -> *mut u8;
	fn free(ptr: *mut u8);
}

unsafe impl GlobalAlloc for EwramAllocator {

    unsafe fn alloc(&self, layout: Layout) -> *mut u8 { 
    	return malloc(layout.size());
    }

    unsafe fn dealloc(&self, ptr: *mut u8, _layout: Layout) {
    	free(ptr);
    }
}

#[global_allocator]
static A: EwramAllocator = EwramAllocator;

#[alloc_error_handler]
fn error_handler(_: core::alloc::Layout) -> ! {
    loop {}
}

I had some experience with C, but I am very new to the Rust itself - I wonder, what issues it may case? I tried boxing/unboxing, manual allocating, etc, seems to work, at least for memory allocation.

[Lokathor]

I'll try to look at this later, but for now I'll give a ping to @ketsuban

[ketsuban]

I have a few concerns.

• The constant is wrong; EWRAM is at 0x02_000_000, not 0x03_000_000. Your code overwrites the .data section, which includes its own state in the form of the HEAP_END global.
• I don't see any handling of out-of-memory, which is pretty necessary when your heap is only a quarter of a megabyte. There's no memory-mapping on the GBA (0x02_040_000 is a mirror of 0x02_000_000) so you need to keep a grip on this.
• I'm a little concerned that you're completely ignoring alignment.

I wrote my own allocator implementation a while back, principally based on the one used in pokeemerald. It's not functional code as it stands (it'd need to be rewritten to replace StaticRef with VolAddress) and it's probably very bad, but there it is.

[sweetpalma]

Well, I've done small refactoring of _sbrk function, so first two issues were eliminated:

/// These variables are defined in the linker script.
extern "C" {
	static __ewram_start: usize;
	static __ewram_top:   usize;
}

/// Pointer to the current heap counter, used by _sbrk:
pub static mut HEAP_CURRENT: *mut u8 = core::ptr::null_mut();

/// _sbrk implementation for GBA.
/// C reference: https://github.com/eblot/newlib/blob/master/libgloss/epiphany/sbrk.c
#[no_mangle]
pub unsafe extern "C" fn _sbrk(incr: i32) -> *mut u8 {
	let heap_start = (&__ewram_start as *const usize) as *mut u8;
	let heap_top   = (&__ewram_top   as *const usize) as *mut u8;
	if HEAP_CURRENT == core::ptr::null_mut() {
		HEAP_CURRENT = heap_start;
	}
	if HEAP_CURRENT >= heap_top {
		return (0 as *mut u8).offset(-1);
	}
	let prev_heap_end = HEAP_CURRENT;
	HEAP_CURRENT = HEAP_CURRENT.offset(incr as isize);
	return prev_heap_end;
}

External variables are defined in the linker script:

MEMORY
{
    EWRAM (xrw) : ORIGIN = 0x02000000, LENGTH = 256K
    IWRAM (xrw) : ORIGIN = 0x03000000, LENGTH = 32K
    ROM   (rx)  : ORIGIN = 0x08000000, LENGTH = 32M 
}

__ewram_start     =   ORIGIN(EWRAM);
__ewram_top       =   ORIGIN(EWRAM) + LENGTH(EWRAM);

But what about alignment - that is a real issue... As far as I know, aligned_alloc was introduced in C11, but unfortunately it seems like it was not implemented properly for bare metal in newlib. Any ideas?

Edit: Possible solution would be allocating enough space for size + alignment and padding excessive bytes.

[Lokathor]

Someone pointed me at https://github.com/ivmai/bdwgc/ as a GC that could potentially be used in a very low memory situation so i'm just putting it here as a reminder link.

EDIT: rust crate form: https://github.com/raviqqe/bdwgc-alloc/, and by same author there's also https://github.com/ivmai/tinygc

[sweetpalma]

That's definitely interesting, would take a look.