Skip to content
GitLab
Open
Issue created by Kunshan Wang@u5211824Owner

External linkage of uptr fields in the boot image

This issue addresses the need that in addition to "external constants" (.const @blah <@T> = EXTERN "blah"), some uptr fields in the Mu memory needs to be initialised to the address of external symbols, too. This pattern exists in regular C programs as well as PyPy which compiles to C.

However, there is a pure client-side solution which can relocate uptr fields without extending either the Mu IR or the API.

Another solution that adds only one API call can let the Mu boot image builder use the system linker/loader.

Problem

In C, global variables can be initialised to constant values. The values can be literals, and can also be pointers to other global variables. In the latter case, the pointers are expressed in the form of &symbol where symbol is the name of the other global variable.

Consider the following C program:

// Foo.c
struct Foo {
    int v;
    struct Bar *bar;
};

struct Bar {
    double w;
};

struct Baz {
    File *fp
};

struct Bar bar1 = { 3.14 };

struct Foo foo1 = {
    42,
    &bar1    // This field is initialised to the pointer to bar1 at link time.
};

struct Baz baz1 = {
    &stdin    // This field is initialised to the pointer to stdin at link time.
};

Both the foo1.bar and the baz1.fp fields are initialised to pointers. The former points to an object in the same compilation unit, while the latter points to a variable in the standard library.

However, the address of neither destinations can be determined at compile time nor link time.

  1. Obviously, the address of stdin is determined only after libc is loaded.
  2. The address of bar1, though only referenced within a .c file, is also indeterminate. The reason is that the current module (executable or .so), may be loaded at different memory addresses for each run. So it is not until the program is loaded could the run-time linker figure out their absolute addresses, and patch the foo1.bar field.

Use in PyPy

PyPy uses some external libraries. One example is libffi.

libffi defines some global variables which the libffi users are supposed to use.

// Excerpt from ffi.h
// libffi is an FFI implementation 

// This struct describes a C data type, including both primitive types and structs.
// For structs, the *elements member points to an array of field types.
typedef struct _ffi_type
{
  size_t size;
  unsigned short alignment;
  unsigned short type;
  struct _ffi_type **elements;
} ffi_type;

// These are the descriptors of primitive C types.
FFI_EXTERN ffi_type ffi_type_void;
FFI_EXTERN ffi_type ffi_type_uint8;
FFI_EXTERN ffi_type ffi_type_sint8;
FFI_EXTERN ffi_type ffi_type_uint16;
FFI_EXTERN ffi_type ffi_type_sint16;
FFI_EXTERN ffi_type ffi_type_uint32;
FFI_EXTERN ffi_type ffi_type_sint32;
FFI_EXTERN ffi_type ffi_type_uint64;
FFI_EXTERN ffi_type ffi_type_sint64;
FFI_EXTERN ffi_type ffi_type_float;
FFI_EXTERN ffi_type ffi_type_double;
FFI_EXTERN ffi_type ffi_type_pointer;

libffi describes C data types using the ffi_type struct. Primitive types are pre-defined global variables. If the user wants to describe a custom C struct, it creates an instance of ffi_type and fills in the fields.

// Suppose we want to describe this struct:
struct Foo { int a; char b; void* c; };

// We define an ffi_type instance:

/// First make an array of field types
ffi_type field_types[4] = { &ffi_type_int, &ffi_type_int8, &ffi_type_pointer, NULL };

/// Then describe struct Foo itself.
ffi_type foo_type = {
    0,  // will be initialised by libffi
    0,  // will be initialised by libffi
    FFI_TYPE_STRUCT,    // it means "Foo is a struct"
    &field_types                // "Foo has these fields"
};

Keep in mind that these data structures are raw C data structures.

PyPy, as a high-level language, will store the pointer to such structs into PyPy-level heap objects and use the pointer later. In RPython, heap objects in their "boot image" (the pypy executable) are global C variables. It will look like:

struct pypy_path_to_module_SomePyPyObjectType object = {
    GC_HEADER,
    HASHCODE,
    BLAHBLAH,
    &foo_type     // Untraced pointer to C global variable
};

At compile time (from RPython source code to C source code), the RPython toolchain describes objects in the boot image symbolically: structs are described field by field, and may contain pointers to other struct values. The toolchain also makes uses of the fact that RPython program eventually compiles to C. All of such struct values become global variables in C, no matter whether they are GC-ed heap objects or not (this also mean they are immortal). This approach avoided the dynamic linking problem because C source code can still refer to other global variables symbolically, whether they are traced or not, and off-loads the task of address resolution to the linker and the loader.

Problem to handle this in Mu

Mu strictly distinguishes between traced references (ref<T>) and untraced pointers (uptr<T>). Mu treats uptr<T> as raw integer values and does not care about its destination. This means, in Mu, untraced pointers are literally untraced.

But the reason why the boot image builder work is that the boot image builder can use the GC to trace all references in all heap objects and global cells (which are still scanned) and find the transitive closures. The GC can find all reference fields and record references between objects. This object-reference graph can generate relocation entries which allows the loader to fix reference between heap objects.

So the boot image builder has no power to "trace" "untraced pointers" and find "which memory location contains a raw pointer to which untraced memory region". i.e. The boot image builder cannot express the following C structure:

struct Foo {
    int v;
    struct Bar *bar;
};

struct Bar {
    double w;
};
struct Bar bar1 = { 3.14 };

struct Foo foo1 = {
    42,
    &bar1  // Cannot express this, because it is UNTRACED pointer.
};

The reason is, the boot image builder takes the value held inside objects as the input, not their symbolic initialisers. The boot image builder sees the current address of bar1, but the boot image is relocatable, and the address will not be valid after loading.

Solution

Solution 1: Redesign the PyPy-level library, or the translation process.

The reason why PyPy needs such C structs is because it needs to call C functions that need them. Currently these C structs are expressed as "constant struct values", which are initialised at compile time. If the PyPy-side library were written with the fact that "raw pointer are not preserved across boot image building" in mind, such structs would have been created at run time rather than compile time, and there will be no need to preserve "pointers from one struct to another".

Alternatively, all untraced structs can be translated to C programs, compiled by conventional C compilers (GCC), and linked against the Mu program (pypy in this case) dynamically. Given that the program's purpose is to interact with native C programs, having extra C programs is not completely wrong, though not very elegant.

Solution 2: Let the client reinvent the linker

This approach require the client to record a list of (iref, symbol) pairs. Each pair means: "Please fill the pointer field at this iref to the address of this symbol before running the main function". This is exactly what the system linker is doing. With the existing .const @blah <@T> = EXTERN "blah" external constant, the client only needs to generate an intialiser function which has a list of STORE instructions to update each iref. The list of irefs can be saved in a heap object which is held by a global cell and built into the boot image. As soon as this list is used, it can be GC-ed (just nullify the only global cell that holds reference to it).

Solution 3: Let Mu support such relocation

There is just one API function need to be added:

void (*add_ptr_reloc)(MuCtx *ctx, MuIRefValue field, const char *symbol);

field is an IRef to a memory location (heap object or global cell) of uptr<T> or ufuncptr<sig> type. This function, when called, will add a relocation entry to the running micro VM. It has no effect on the running VM. But when the client later orders the micro VM to build a boot image, the boot image will contain relocation entries that will re-initialise the given field to the address of the given symbol.

Unlike Solution 2, this solution can make use of the system linker/loader, but adds more burden to the micro VM. But given that the micro VM's boot image builder already has to handle relocation entries, this requirement looks reasonable.