Memory model

[vasucp1207]

Thread to discuss about different memory models

[vasucp1207]

Things to consider while choosing the memory model,

• Dangling pointers
• Use after free
• Multiple ownership
• Object aliasing
• Stack escapes
• Handling raw pointers
• Compile time memory type checks

Memory model to discuss,

• Region based memory(cyclone)
• Generational References(vale)
• Ownership model(lobster)
• GC with stack escape analysis(go)

[Aliqyan-21]

@vasucp1207 we have put unsafe in our grammar, so we could use some boundary of safe and unsafe to design around or we can consider removing unsafe too if need arises?

[Aliqyan-21]

Generational References

For Bedrock, we want deterministic performance, and the runtime should be lightweight and easy to implement.

The best approach that I can think of is a Hybrid Generational Memory Model (inspired by Vale).
It basically pairs a compile-time move checking for single ownership (Box[T]) with runtime generation checks for aliased references (Ref[T]).

By extending generation tracking to stack frames alongside heap allocations, both safe and unsafe code stay clean and well-defined.

so we can provide safety in both stack and heap.

• Stack Generation Tracking (Safe): Each stack frame gets a lightweight 32-bit generation ID on entry.
  Taking &stack_val produces a safe Ref[T]. If code tries to access that reference after the stack frame exits,
  it traps deterministically (killing use-after-return bugs).
• Unsafe Escape Hatch (*T): Raw pointers are reserved for unsafe blocks for FFI,
  pointer arithmetic, and zero-overhead hotpaths.

we can have system that have debug and release builds, in debug runtime assertions can stay active inside unsafe to catch bugs early,
while release builds strip them down to pure assembly instructions.

proc main()
    // this is safe Box[i32] (owned) + Ref[i32] (checked heap alias)
    var b: Box[i32] = Box.new(42);
    var r1: Ref[i32] = b.ref();

    // this is safe too Stack Generation Tracking lets & produce a safe Ref[i32]
    var stack_val: i32 = 100;
    var r2: Ref[i32] = &stack_val;

    // and in usafe Raw pointers (*T) will access bare-metal performance or FFI
    unsafe
        var ptr: *i32 = b.raw_ptr();
        io.println(ptr.*);
    end
end

[vasucp1207]

Tracing GC

This is traditional tracing GC memory model. User will allocate data on heap using new keyword, GC will keep track of data that is not reachable from the root node and reclaim it as usual using mark and sweep. Values that do not escape their current scope can remain on the stack.If a stack value tries to escape its function scope then it will gets promote to heap and will be managed by GC afterwards.

func ret_person() -> Person
    var p = Person(id = 0, age = 24)                     <----- lives on stack
    return &p                                            <----- escape the current function, promoted to heap
end

GC will allow multiple references without enforcing any ownership model. The data remain alive as long as it is reachable through GC tracing.

func person() -> void
    var p = Person(id = 0, age = 24)
    var a = p
    var b = p
end

The benefit of this model is its very simplicity and the grammer will remains relatively clean just a couple of new addition of keywords like new, * and &.

[vasucp1207]

Region based memory model

This model uses regions to manages memory in this objects are allocated in a region are reclaimed all at once when the region goes out of scope intead of keep tracking each allocation.

The compiler tracks the lifetime of references to make sure that a reference cannot outlive the region it currently lives in.

func ret_person() -> &Person
    region R
      var p = Person(id = 0, age = 24)
      return &p
    end
end

The compiler can determine that lifetime of return is = caller and lifetime of p R ends before caller uses the return reference, preventing dangling reference at compile time.
User is not explicitly required to annotate the region R in the above example the compiler can infer the lifetime in a function body.

func ret_person() -> Person
    region R
      var p = Person(id = 0, age = 24)
      return p
    end
end

Here the value will be copied or moved outside the region.

func person() -> void
    region R
      var p1 = Person(id = 0, age = 24)
      region I
        var p2 =  Person(id = 0, age = 24)
        p1 = p2                                                 <------- error region R outlives I
    end
end

[Aliqyan-21]

@vasucp1207 \How unsafe will be incorporated in Tracing GC and Region Based Memory Model ?

[vasucp1207]

using unsafe will not switch to different memory model its upto the programmer, they have to ensure about the behaviour about the unsafe block.

[Aliqyan-21]

@vasucp1207 could you give the document for the region based memory model you were talking about, I wanna know how it will work.

[vasucp1207]

Arena Region memory model

The memory model is based on regions(arenas). Every allocation belongs to exactly one region, and the region determines when that allocation is reclaimed.

Invariants about region model

• Every allocation belongs to one region, all allocations within an arena are reclaimed together when that region is destroyed.
• A reference cannot outlive its target, program cannot contain dangling references.
• Destruction happens exactly once when the region goes out of scope.

Lifetimes concepts

Lexical region

A lexical region corresponds to a local scope.

proc lexical()
    region @outer
        var p1: &Person
            region @inner
                // currently don't have `new` for heap allocation in grammer
                var p2 = new Person(name = "Alice", age = 24)
                p1 = &p2
            end
    end
end

Here both p1 and p2 are in lexical region, lifetime(p2) < lifetime(p1) so p1 cannot reference to p2.
Its not necessary to type the region block manually the compiler can infer the region annotations in this case.

See the same example without implicit region blocks

proc lexical()
    var p1: &Person
        // currently don't have blocks in grammer
        block
             var p2 = new Person(name = "Alice", age = 24)
             p1 = &p2
        end
end

Function params

Parameters are not a separate storage region. A reference parameter borrows an allocation from the caller.

proc set_friend(p: &Person, friend: &Person)
    p.friend = friend
end

Because friend might have a shorter lifetime than p, we need some lifetime annotation hints here.

proc set_friend(p: &@p Person, friend: &@r Person)[@p <= @r]
    p.friend = friend
end

Return

A function cannot return a reference to storage whose lifetime ends before the caller can use the return value.
Local references cannot escape their lexical region. We cannot return a reference to local variable to the caller that will result in dangling pointer.

func foo() -> &Person
    var p = Person(name = "Alice", age = 24)
    return &p

Static region

Static storage lives for the entire program.

var p: &Person
proc foo()
    var local = Person(name = "Alice", age = 24)
    p = &local                     <--------- fail as p has global lifetime cannot ref to a lexical var

TODOS

• Region promotion of regions.
• Ownership model

[Aliqyan-21]

Sorry if the question is dumb but why not just 'new Person(...)'

[vasucp1207]

If we just use new Person(...) then the allocation by default will belongs to the current lexical region and the memory will be reclaimed when the lexical region goes out of scope(standard Arena allocation working). For assigning it to global var we have to promote the allocation to global region.

[Aliqyan-21]

Ohhh now I see, ok got it! that's good

[skadewdl3]

@vasucp1207 How are mutability and reference going to work?

For example, consider two cases: a hashmap (string -> func()) in global and in lexical region memory.

What happens if we need to store closures that captures some stuff from the current lexical region in the hashmap?

TLDR; I wanna know how the user can specify when to move a value into a region v/s when the region should borrow it.

[vasucp1207]

@vasucp1207, Currently I am not sure and thinking about the borrowing and ownership rules and do we support the multiple mutable refs or not. The thing is if we does not allow the multiple mutable refs then we have to introduce some other type of refs for mut refs maybe using ref counting.

[skadewdl3]

Also, @vasucp1207 we need to define how memory managed by the regions interacts with unsafe blocks. For eample:

extern proc free(ptr: *u8)

type Person = struct
  age: u32
end

func main()
  var a = Person(age = 42)
  unsafe
    free(&a)   // <------- What happens here? Compile-time error? Blame the user?
  end
end

[skadewdl3]

There's no real way to know what a function does with a pointer passed to it. If it deallocates memory, I say we blame the user since it's inside an unsafe block.

[skadewdl3]

And do we differentiate between raw pointers (aka C pointers) and references (used in safe bedrock)? If so, how?