Developing modules for Limbo in C

While building Inferno, file module/example.m analysed, and corresponding C data structures is generated. General information about this module saved in separate file libinterp/examplemod.h. Structures describing module’s public interface (constants, adt, functions) appended to file libinterp/runt.h (which contain information about all C modules). Both these .h-files are already included in our libinterp/example.c.

Next, while booting OS Inferno will call our function examplemodinit(), which should initialize global data of our module (if such data exist) and attach it (by executing builtinmod()) to kernel. builtinmod() will set connection between our module and it pseudo-path '$Example' defined in constant PATH, used from Limbo to load our module.

Let’s begin with simple data types, to not overcomplicate initial examples with pointers.

Rebuild Inferno.

Don’t forget to restart emu before executing our example application because currently running emu doesn’t contain modified C module.

While building, definition for function increment() (found in module/example.m), it parameters and returned value was automatically generated and appended into libinterp/runt.h:

I didn’t check yet what regs is; temps added for data alignment; ret is a pointer to returned value; and i is our parameter.

Build, restart, test:

Here is what we got in libinterp/runt.h:

With noret vs ret it’s all clear - function say() return nothing. Type String* is C implementation of Limbo’s strings. You can find struct String in include/interp.h, helper functions working with strings (like used in our example string2c()) are in libinterp/string.c.

In similar way you can work with all other Limbo’s data types: using Array*, List*, etc. Not for all data types there are available helper functions like for strings, but you can find enough examples in VM’s opcodes implementation (in libinterp/xec.c) - for example, how to handle array slices).

User adt defined in module/example.m converted to usual C struct (pick adt into union). Tuple also became usual struct.

It’s very likely you will have to run Inferno rebuild (which will fail) after modifying module/example.m just to update libinterp/runt.h and let you see which exactly structures was generated for your data types and understood how to handle them in libinterp/example.c.

To raise exception it’s enough to call error(). You can include raise.h to raise standard exceptions defined in libinterp/raise.c or define your own exceptions in similar way in libinterp/example.c.

Of course, if you manually allocated memory using malloc(), then before calling error() you have to free() than memory to avoid leaking. Objects allocated in standard way on heap (like String* and Array*) may not be destroyed, they will be freed later by GC anyway (more about GC below).

One subtle thing about returning result from functions is *f->ret already pointing to user’s variable, which should keep function result value after it returns. There are two consequences because of this:

To demonstrate first issue let’s modify our function increment() in this way:

So solve second issue in C functions before storing returned value into *f->ret you have to free current value. Usually it’s done either in this way:

or in this way (H is C equivalent for Limbo’s nil):

As far as I understood, right now both snippets do the same, and there is no difference between them. But if Dis will be changed to run simultaneously on multiple CPU/Core, then second snippet will work correctly while first one will not.

To simply allocate n bytes in heap, and then free them, you should do this:

This result in allocating 256 + size of heap header bytes, which will begin with heap header first and your data next. Heap header is struct Heap, plus there are two macros to convert pointer to heap header to pointer to your data (with type cast at same time for usability) H2D() and vice versa D2H(). Function destroy() uses D2H() to convert pointer to beginning of user’s data with unknown size to pointer to heap header and find out so how many bytes it should free.

So, what’s in heap header? I don’t know about hprof, I didn’t look in heap profiling, but all other fields are very important.

At first, few words about garbage collection in Inferno. There are two strategies used: simple reference counting (which is enough for most data structures), plus sort of tri-colour marking algorithm to free data structures with cyclic references. So, ref is reference counter, and color is used by tri-colour marking. When nheap() or another similar function allocate on heap new data object, it heap header’s ref value is set to 1. When you call destroy(), it decrease ref value by 1, and if ref become equal to 0 it will actually free memory used by this object.

So, while you keep value returned by nheap() (or any other similar function) in single variable - you’ve exactly one reference to that object, and object’s ref set to 1. As soon as you will copy that pointer into another variable - you must increase reference counter plus notify tri-colour algorithm about this. This is done in this way (Setmark() is also macros, but to understand what it does you have to understand how Inferno’s tri-colour algorithm works, which will be explained later):

Of course, if you allocated object on heap, and then returned it to user by copying to *f->ret, you don’t need to do something with ref and color - pointer to that object stored in your function’s local variables will be deleted as soon as you return from function, so there is will be still just one pointer to that data - in user’s variable where she store value returned by your function. So, it was actually pointer moving, not copying.

There is one subtle issue related to moving pointers. In previous example with value returned from function we move new, just allocated pointer, and don’t need to do anything more. But if you moved pointer from one existing data structure to another existing data structure, you must notify tri-colour algorithm about this by calling Setmark() (this is also related to implementation details of Inferno GC and will be explained later):

Previous example with nheap() probably never used in real code because Limbo doesn’t have such data type: n bytes. So, you can’t receive such data object from Limbo as parameter for your function, and you can’t return object allocated with nheap() to Limbo. As for your function’s internal needs, it’s usually enough to use malloc() and free().

All objects in heap which can be accessed by Limbo must have some type, defined by struct Type. This is needed to solve task of finding all pointers inside any object - which is required for:

For standard data types (any adt/tuple/struct which contain either non-pointer fields or fields with pointers to usual heap-objects, which can be freed using destroy() - like String* and Array*) the fields np and map are used. Field map contain bit mask, with one bit (starting from most significant bit in first byte) per each 4 bytes of adt/tuple/struct, where set bit mean corresponding 4 bytes is a pointer to heap-object. Field np contain length of map field in bytes.

Some data types use memory in non-standard way. Typical examples are String and Array - first one contain char* field, which have to be freed with free(); second may consist of adt/tuple/struct which should be freed according to their type, not type of Array struct itself. The Type struct allow defining own non-standard functions-handlers for such types, which will be called while allocating/initializing memory, by destroy() and from GC: free, mark, destroy and initialize.

Field size contain size of structure for that type (if we have to provide type while allocating new object of that type anyway, keeping size inside type allow us to avoid providing both type and size separately).

Field ref is used to keep current amount of objects of that type in heap. Thing is, type list is not limited by list of predefined types like string, array of, etc. - any tuple defined on the fly is a separate type, which needs its own definition by structure Type. That means, some types are created by Limbo on the fly, stored in same heap, and must be freed from memory as soon as there are no more objects of that type in heap. To make this work, when creating every new object of some type, that type’s ref must be increased, and while freeing object of some type destroy() will also decrease object type’s ref and will free that type after freeing object if type’s ref become 0.

Values of Type for standard types are defined statically, with ref set to 1 (so their ref never become less than 1 and they never will be freed) - you can find their definitions in libinterp/head.c:

Types for your own adt/tuple/struct in some cases can be defined with help of libinterp/runt.h (it will calculate your struct size for Type.size and pointers bit mask for Type.map and Type.np), in other cases you will have to define it manually (for example, to create and return tuple from C function). Usually these types defined while initializing your module (back to our module Example) using helper function dtype(). And you will allocate memory for your objects using heap(&Tsometime) instead of nheap(n_bytes).

There is subtle difference between Limbo and C in how they handle adt and ref adt. On Limbo they look very similar:

but on C it’s completely different things:

While GC delete from memory all objects which doesn’t referenced from "root" objects (which is probably consists of working threads, loaded modules, etc.) ignoring their ref value, then we can’t keep pointer to heap object outside Limbo threads (for example in global variables of our C module). To prevent GC from freeing such our objects in heap we should detach them from GC using poolimmutable() (later we can attach it back to GC using poolmutable()):