uvm-memory.rest

Mu and the Memory

Overview

Mu supports automatic memory management via garbage collection. There is a heap which contains garbage-collected objects as well as many stacks and a global memory which contain data that are not garbage-collected.

The heap memory is managed by the garbage collector.

Unlike C or C++, local SSA variables are not bound to memory locations. Stack memory must be allocated by the ALLOCA or ALLOCAHYBRID instructions or using the Mu client interface.

This specification does not mandate any object layout, but it is recommended to layout common data types as in the platform application binary interface (ABI) so that the native interface is easier to implement.

Basic Concepts

Mu Memory

There are three kinds of memory in Mu, namely the heap memory, the stack memory and the global memory. Mu memory means one of them.

Memory is allocated in their respective allocation units. Every allocation unit has a lifetime which begins when the allocation unit is created and ends when it is destroyed.

A memory location is a region of data storage in the memory which can hold data values. A memory location has a type and its value can only be of that type.

NOTE: The Mu memory is defined without mentioning "address". There is no "size", "alignment" or "offset" of a memory location. The relation between a memory location and an address is only established when pinning (discussed later). Even when pinned, the address may or may not be the canonical address where the location is allocated in Mu. For example, Mu objects can be replicated.

When allocating Mu memory locations (in the heap, stack or global memory), Mu guarantee the location can hold Mu values of a particular type and, as long as the type allows atomic access, the location can be accessed atomically. The implementation must ensure all memory locations are allocated in such a way. For example, it should not allocate an integer across page boundary, but it may choose to use locks for atomicity, which, in practice, is usually a bad idea.

For C programmers: The word "object" in the C language is the counterpart of "memory location" in Mu. Mu does not have bit fields and a memory location is always an "object" in C's sense. In Mu's terminology, the word "object" is a synonym of "heap object" or "garbage-collected object".

In C, the word "memory location" must have scalar types, but Mu uses the word for composite types, too.

For a memory location L that represents type T, if c is a member (if applicable) or a component of T, it also has a memory location which is a member or a component of the memory location L, respectively. Memory location L1 contains a memory location L2 if L2 is a component of L1.

The lifetime of a memory location is the same as the allocation unit that contains it.

As implementation details, when an allocation unit is destroyed and another allocation unit occupied the same or overlapping space as the former, they are different allocation units. Different allocation units contain no common memory locations. When a heap object is moved by the garbage collector, it is still the same object. Any memory locations within the same object remain the same.

NOTE: This means the memory of Mu is an abstraction over the memory space of the process.

Native Memory

The native memory is not Mu memory. The native memory is an address space of a sequence of bytes, each can be addressed by an integral address. The size of the address is implementation-defined.

A region of bytes in the native memory can be interpreted as Mu values in an implementation-dependent way. The bytes that represents a Mu value is the bytes representation of that Mu value.

For C programmers: it is similar to the "object representation", but in Mu, unless a memory location is pinned, it may not be represented in such a way.

A Mu memory location can be pinned. In this state, it is mapped to a (contiguous) region of bytes in the native memory which contains the bytes representation of the value the memory location holds. The beginning of the memory location is mapped to the lowest address of the region. Different components of a memory location which do not contain each other do not map to overlapping regions in the address space.

For C programmers:

• Mu assumes 8-bit bytes.
• Mu does not have the bit-field type, but a client can implement bit-fields using integer types and bit operations.
• Mu does not have union types. However, like C, directly casting an address to a pointer has implementation-defined behaviours. If a Mu program interfaces with native programs, it has to also depend on the platform.
• Unlike C, Mu operations work on SSA variables rather than memory locations (the counterpart of objects in C).
• Mu forces the 2's complement representation, though the byte order and alignment requirement are implementation-defined.

See Native Interface for details about the pinning and unpinning operations.

Memory Allocation and Deallocation

An allocation unit in the heap memory is called a heap object, or object when unambiguous. It is created when executing the NEW or NEWHYBRID instructions or the new_fixed or new_hybrid API function. It is destroyed when the object is collected by the garbage collector.

An allocation unit in the stack memory is called an alloca cell. It is created when executing the ALLOCA or ALLOCAHYBRID instruction. It is destroyed when the stack frame containing it is destroyed.

An allocation unit in the global memory is called a global cell. One global cell is created for every .global declaration in a bundle submitted to Mu. Global cells are never destroyed.

Initial Values

The initial value of any memory location is defined as the following, according the type of data value the memory location represents:

• The initial value of int and pointer types is 0 (numerical value or address).
• The initial value of floating point types is positive zero.
• The initial value of ref, iref, weakref, funcref, stackref and threadref is NULL.
• The initial value of tagref64 is a floating point number which is positive zero.
• The initial values of all fields or elements in struct, array, vector and the fixed and variable part of hybrid are the initial values according to their respective types.

Garbage Collection

A root is an object reference or internal reference in:

• any global cell, or
• any bound Mu stacks, or
• the thread-local object reference in any threads, or
• any values held by any client contexts in the API.

A live stack contains references in its alloca cells and live local SSA variables. A dead stack contains no references. A thread can strongly reach its bound stack unless it is temporarily unbound because of trapping.

An object is strongly reachable if it can be reached by traversing only strong, stack and thread references from any root. An object is weakly reachable if it is not strongly reachable, but can be reached by traversing strong stack, thread and weak references from any root. Otherwise an object is unreachable.

The garbage collector can collect unreachable objects. It may also modify weak references which refers to a weakly reachable object to NULL.

NOTE: Doing the latter may make weakly reachable objects become unreachable.

The garbage collector may move objects.

Memory Accessing

Memory accessing operations include load and store operations. To access means to load or store. Atomic read-modify-write operations may have both a load and a store operation, but may have special atomic properties.

NOTE: Instructions are named in capital letters: LOAD and STORE. The abstract operations are in lower case: load, store and access.

Memory access operations can be performed by some Mu instructions (see Instruction Set, API functions (see Client Interface), native programs which accesses the pinned Mu memory, or in other implementation-specific ways.

Two memory accesses conflict if one stores to a memory location and the other loads from or stores to the same memory location.

Parameters and Semantics of Memory Operations

Generally speaking, load operations copy values from the memory and store operations copy values into the memory. The exact results are determined by the memory model. See Memory Model.

A load operation has parameters (ord, T, loc). ord is the memory order of the operation. T is the type of loc, a memory location. The result is a value of the strong variant of type T.

A store operation has parameters (ord, T, loc, newVal). ord is the memory order of the operation. *T is the type of loc, a memory location. newVal is a value whose type is the strong variant of T. This operation does not produce values as result.

A compare exchange operation is an atomic read-modify-write operation. Its parameters are (isWeak, ordSucc, ordFail, T, loc, expected, desired). isWeak is a Boolean parameter which indicates whether the compare exchange operation is weak or string. ordSucc and ordFail are the memory orders of the operation when the comparing is successful or failed. T is the type of the memory location loc. expected and desired are values whose type is the strong variant of T. The result is a pair (v, s), where v has the type of the strong variant of T, and s is a Boolean value.

A compare exchange operation performs a load operation on loc and compares its result with expected. If the comparison is successful, it performs a store operation to location loc with desired as newVal.

If the operation is strong, The comparison succeeds if and only if the result of load equals expected. If it is weak, the comparison succeeds only if the result of load equals the expected value and it may spuriously fail, that is, it may fail even if the loaded value equals the expected value.

The result v is the result of the initial load operation and s is whether the comparison is successful or not.

An atomic-x operation is an atomic read-modify-write operation, where x can be one of (XCHG, ADD, SUB, AND, NAND, OR, XOR, MAX, MIN, UMAX, UMIN). Its parameters are (ord, T, loc, opnd). ord is the memory order of the operation. T is the type of the memory location loc. opnd is a value whose type is the strong variant of T. The result also has the type of the strong variant of T.

An atomic-x operation performs a load operation on location loc. Then according to x, it performs one of the binary operation below, with the result of the load operation as the left-hand-side operand and the value opnd as the right-hand-side operand. The result is:

XCHG

The value of opnd.

ADD

The sum of the two operands.

SUB

The difference of the two operands.

AND

The bitwise AND of the two operands.

NAND

The bitwise NOT of the bitwise AND of the two operands.

OR

The bitwise inclusive OR of the two operands.

XOR

The bitwise exclusive OR of the two operands.

MAX

The maximum value of the two operands, considering both operand as signed.

MIN

The minimum value of the two operands, considering both operand as signed.

UMAX

The maximum value of the two operands, considering both operand as unsigned.

UMIN

The minimum value of the two operands, considering both operand as unsigned.

NOTE: In the C syntax, the semantic of NAND is ~(op1 & op2).

Then it performs a store operation to location loc with the result of the binary operation as newVal.

The result of the atomic-x operation is the result of the initial load operation.

All operators other than XCHG are only applicable for integer types. XCHG is allowed for any type. However, a Mu implementation may only implement some combinations of operators and operand types according to the requirements specified in Portability

Memory Operations on Pointers

Load, store, compare exchange and atomic-x operations can work with native memory in addition to Mu memory locations. In this case, the loc parameter of the above operations become a region of bytes in the native memory (usually represented as uptr<T>) rather than memory locations (usually represented as iref<T>).

Only native-safe types can be accessed via pointers.

When accessing the memory via pointers, if the bytes are mapped to a Mu memory location via pinning (see Native Interface), then if the referent type of the pointer is the same as the Mu memory location, it has the same effect as accessing the corresponding Mu memory location.

When non-atomically loading from or storing to a region R of bytes which is

1. not mapped to (i.e. not perfectly overlapping with) a particular Mu memory location, and
2. each byte in the region is part of any mapped byte region of any pinned Mu memory location,

then such an operation loads or stores on a byte-by-byte basis. Specifically:

• Such a load operation L:

  1. for each address A of byte in the region R, performs a load operation

     on the (only) Mu memory location of scalar types (not composite types) whose mapped byte region R2 contains address A, then extract the byte value b at address A, then

  2. combine all results b from the previous step into a sequence of byte

     values, then interprets it as the bytes representation of a Mu value. This Mu value is the result of the load operation L.

• Such a store operation S:
  1. interprets its newVal argument as its bytes representation B, then

  2. for each address A of byte in the region R, performs a load operation

     on the (only) Mu memory location of scalar types (not composite types) whose mapped byte region R2 contains address A, then update the result by replacing the byte at address A with the byte in B, then perform a store operation on the same Mu memory location with the updated value as newVal.

NOTE: This allows Mu to allocate a byte array and access (by itself or by native programs) it via pointers as if it is a struct or a union, and then interpret the written values as bytes. The requirement of each byte being mapped gives implementation-defined behaviours to accesses beyond the border of any Mu objects (such as array out-of-bound errors), or accessing padding bytes in Mu structs.

Accessing native memory regions not mapped to Mu memory locations has implementation-defined behaviours.

NOTE: Accessing the native memory may have all kinds of results: getting a previously-stored value, storing to one address and affect another address when two addresses are mapped to the same physical memory region/file, segmentation fault, bus error (especially on OSX), turning on/off the light by doing memory-mapped IO, launching nuclear missiles, summoning nasal demons, etc. Mu cannot make much guarantee.

Native programs can access pinned Mu memory locations in implementation-defined ways.

NOTE: This means it requires the efforts from the implementations of both Mu and the native programs to obtain any defined semantics in mixed Mu-native programs. For C, it will involve the C language, the platform ABI and the Mu ABI of that platform.

Memory Layout

Whether or how Mu data of any type are represented in the native memory is implementation-defined. When an object is pinned, the layout is viewed from the native memory in a platform-dependent way.

For Mu implementers, it is recommended to use the layout defined by the application binary interface of the platform in order to ease the data exchange via the native interface implementation.

Mu has some rules about Mu memory locations which must always preserved.

Rules of Memory Locations

Every memory location has an associated type bound when the memory location is created and cannot be changed. The memory location can only hold values of that type.

NOTE: The association between memory location and type is conceptual. This does not mean the Mu implementation has to keep a metadata of the type of all memory locations at runtime. The implementation only needs to keep enough metadata to implement its garbage collector.

A memory location has a beginning and an end. The value it holds is represented in that region. A non-NULL internal reference of type T refers to the memory location of type T at a specific beginning.

NOTE: There can only be one such memory location.

Specifically, there is a memory location of type void at the beginning of any other memory location.

NOTE: This makes it legal to cast any iref<T> to iref<void> and back.

Prefix Rule

NOTE: The prefix rule is design to support having common language-specific object headers in objects. It also supports inheritance in object-oriented programming where a superclass is a prefix of a subclass.

A component C is a prefix of a type T if any of the following is true.

• C is T itself.
• T is a struct and C is its first field.
• T is a hybrid and C is its first field of the fixed part, or the fixed part of T has no fields and C is the first element of the variable part.
• T is an array<T n> or vector<T n> and n >= 1, and C is its first element.
• C is a prefix of another prefix of T.

A prefix of memory location M is the memory location that represents a prefix of the type of M.

All prefixes of a memory location have the same beginning.

The REFCAST instruction or the refcast API function preserves the beginning of the operand. If it casts iref<T1> to iref<T2>, the result is an internal reference to the memory location of type T2 at the same beginning. (see Instruction Set)

Array Rule

A memory array is defined as a contiguous memory location of components of the same type. The array type, the vector type as well as the variable part of a hybrid are all represented in the memory as memory arrays.

Nested array, vector and variable part of hybrid can be considered as a single memory array with the innermost element type of the nested type as the element type.

Example: The variable part of hybrid<T array<array<vector<float 4> 10 20>> can be treated as:

• a memory array of float, or,
• a memory array of vector<float 4>, or
• a memory array of array<vector<float 4> 10>, or
• a memory array of array<array<vector<float 4> 10> 20>, or

Internal references to an element of a memory array can be shifted to other elements in the same memory array using the SHIFTIREF instruction.

NOTE: SHIFTREF may cross the boundary of Mu types, but still remain in the memory array. For example, an internal reference to the first float in the array<array<float 10> 10> array, which is a 10x10 matrix of float, can be shifted to other rows using the SHIFTIREF instruction and cross the 10-element boundary. Shifting by 12 elements from element (0,0) will reach the element at (1,2).