Custom allocator issue

Added by Runar Tenfjord about 1 year ago

With reference to issue #669.

I found an venerable implementation of a simple allocator from
the book "The C Programming Language". Details found in
this post : https://stackoverflow.com/a/36512105/10830469

The code is implemented in Oberon and called from the ARM32T runtime.
It seems to work find and is probably good enough for most purposes.

The implementation is using a linked list embedded in the allocated
memory and thus does not use much extra memory at the cost of
less speed and messy code.

Files with allocator and updated runtime attached.

The only problem I have is to call Oberon code from the
assembler runtime routines. How to proper save the LR
when calling the code?:

excerpt from armt32SemihostRun.asm:

; standard free function
.code free
    .alignment    4
    str        lr, [sp, 64]
    ;push    {lr}
    ;add sp, sp, 4
    bl.w    @Std:SysMem.Dispose
    ;sub sp, sp, 4
    ;pop     {lr}
    ldr    lr, [sp, 64]
    bx.n    lr

; standard malloc function
.code malloc
    .alignment    4
    str        lr, [sp, 64]
    ; push {lr}
    ;add sp, sp, 4
    bl.w    @Std:SysMem.New
    ;sub sp, sp, 4
    ; pop {lr}
    ;mov lr, r9
    ldr    lr, [sp, 64]
    bx.n    lr

; fetch heap start
.code get_heap_start
    .alignment    4

    ldr     r0, [pc, offset (start)]
    bx.n    lr

start:  .qbyte  extent (@_trailer)

Could you take a quick look at this problem?

Best regards
Runar Tenfjord

Download all files

armt32SemihostRun.asm (2.11 KB) armt32SemihostRun.asm
Std.SysMem.mod (5.26 KB) Std.SysMem.mod

Replies (4)

RE: Custom allocator issue - Added by Florian Negele about 1 year ago

Using external declarations it is possible to provide alias names for Oberon procedures such that you don't have to write malloc and free at all in assembler:

PROCEDURE Dispose* ["free"] (ptr : ADDRESS);
(* ... *)

PROCEDURE New* ["malloc"] (nbytes : LENGTH): ADDRESS;
(* ... *)

The get_heap_start function also becomes obsolete if you define a forward external declaration to _trailer using the same technique:

VAR ^ heapStart ["_trailer"]: SYSTEM.BYTE;
(* ... *)

Heap := SYSTEM.ADR (heapStart);

The extent operation is not needed here because the referenced section is empty, and thus yields the same address.

RE: Custom allocator issue - Added by Runar Tenfjord about 1 year ago

Excellent.

I could probably just keep the simple bump allocator in
the runtime as a fallback and mark the code here with .replaceable.
It will then be replaced by the Oberon code if linked.

I have done some larger random testing with the same code running
on amd64 and the implementation seems stable. I discovered a small
issue with the Dispose procedure. I will post updated code here for
reference after some more testing.

Best regards
Runar Tenfjord

RE: Custom allocator issue - Added by Florian Negele about 1 year ago

For 64-bit, the type UNSIGNED32 should probably be replaced with ADDRESS. The nested Adr procedures seem to convert a NodePtr to an ADDRESS which could also be done using SYSTEM.VAL.

RE: Custom allocator issue - Added by Runar Tenfjord about 1 year ago

The code was updated with comments above and a small
correction which was causing failures. Now 579 tests are
running fine and with no memory leaks.

I also run some randomized tests without problems.

This indicates the code should probably be good, but there
might still be corner cases hidden.

After all it is ported from C and might rely on undefined behaviour
for a particular platform and compiler combination.

Code attached. Thanks for your helpful comments.

Best regards
Runar Tenfjord

Download all files

armt32SemihostRun.asm (2.14 KB) armt32SemihostRun.asm
Std.SysMem.mod (4.67 KB) Std.SysMem.mod

(1-4/4)

Project

General

Profile

Eigen Compiler Suite