RFC: Fully dynamic memory

[wegendt-bosch]

Introduction

In embedded devices memory is hard. This is reflected in the way embedded C programs are designed: memory allocation is static or on the stack. This makes it hard to work with memory: you can't return memory you allocate in your stack frame, so you need to allocate it at the caller site, pass in a pointer and the called function then writes to that memory.

In Mita this is invisible: we allocate memory for you and give it to functions you call. However for this we need to know how much memory you will allocate in any given function.

Current Situation

To find out how much memory you will need we do a worst case analysis: for strings that get concatenated in different control paths we take the maximum of both etc.

This aproach is obviously limited: concatenation in loops can't be inferred right now, and in general inferring this statically during compile time is equivalent to solving the halting problem which is impossible.

What happens if you want to concatenate in a loop? The compiler will tell you to tell it how much memory you will need. This is cumbersome and still won't be able to handle all situations, e.g. when you receive a response from an HTTP-GET.

Generated Types and Functions have an even harder solution: instead of being able to do the calculation by hand you need to program in Java. While this is better than C it still requires yet another language to learn and you need to navigate a complicated language model. Also generated size inferrers have the same shortcomings as explicit maximum lengths: You will never be able to correctly infer sizes for runtime dependent results.

Proposal

For those really hard to do cases where the size depends on your environment you could write a size inferrer in Mita that get's called before memory needs to be allocated, or Just-In-Time. Short examples for the proposed syntax and corresponding C code follow:

fn foo(x : int32, y : int32) : string {
    var res = "";
    for(var i = 0; i < x + y; i++) {
        res += "a";
    }
}
fn foo.size(x : int32, y : int32) : uint32 {
    return x + y;
}
fn bar() {
    let eightAs = foo(2, 4);
}

Retcode_T foo(char** res, int32_t x, int32_t y) {
/* ... */
}
Retcode_T foo_size(uint32_t* res, int32_t x, int32_t y) {
    *res = x + y;
    return NO_EXCEPTION;
}

Retcode_T bar() {
    uint32_t eightAsSize;
    exception = foo_size(eightAsSize, 2, 4);
    if(exception != NO_EXCEPTION) return exception;
    char eightAs[eightAsSize];
    exception = foo(eightAs, 2, 4);
}

Generated types and functions and platform resources already specify a size inferrer and generate custom C code; these would create custom C code and return a special kind of SizeInferenceResult indicating JIT-memory. This resoult could contain the name of the C function that calculates how much space is needed.

Implications

Once the type system is overhauled (#50) some more advanced memory structures are imaginable: arrays containing structs containing arrays and so on. For these we would need to return a more complicated data structure like an array containing uint32. This function in turn would require a size inferrer.

An easier but less flexible solution would be to return tuples for each level of dynamic memory. An array containing a struct containing two arrays would need a size inferrer of result type (uint32, (uint32, uint32)), indicating that every array contained in the struct has the same maximum size.

Allocation would be a bit messier. Since we can't allocate that memory in a loop we need to calculate the total amount of bytes, create a block of memory uint8_t[] on the stack and then do pointer arithmetic.

However in total we stay with the stack-only memory model which guarantees allocation without fragmentation.