civlib: small libraries for Civboot

Note: I will be migrating the lua code here to https://github.com/civboot/civlua after I return from a 6 month hiatus.

civlib is a set of small libraries embodying Civboot's software design principles. It is primarily to bootstrap fngi and set up Civboot OS's software, but is made available if others would like to experiment with similar minimalist software stacks in C. Installation is done by simply copying the civlib directory and including the relevant files for your program.

civc: the civlib C library

The fngi runtime depends on the following, which are provided by civc:

• Core data types including Slc, Buf, CStr (byte counted string), Ring buffer, SLL and DLL (single/double linked lists), and BST (binary search tree) -- as well as common methods and safe type conversion functions.
• A 0x1000 byte (4KiB) block allocator, permitting allocating and freeing single blocks without memory fragmentation.
• A basic arena allocator allowing allocation and freeing of both aligned and non-aligned memory.
• A File Role type, permitting reading and writing to byte stream resources through standardized method pointer offsets (see Role section).
• A basic concept of Fibers, allowing for implementing a cooperatively scheduled system on top.
• A global environment for the allocated values, giving implementors a standard base to interact with their environment.

Data Inheritance

Inheritance in civc is simple. If the beginning of your struct is laid out identically to another struct, then it can be a child of that struct and the pointer can safely be converted. For example:

struct A { int a; };
struct B { int a; int b; }

A pointer of type B can be converted safely to a pointer of type A, since B contains all of A's fields. We therefore write the function:

A\* B\_asA(B\* b) { return (A\*)b; }

Converting the other way (from A to B) is not safe and should not be written.

This is most commonly used for child structs of data structures like linked lists. Being able to convert pointer types allows us to write logic for these types once and reuse it for any other shape of the payload. Writing the safe conversions helps prevent us from accidentally doing invalid conversions.

Role

Roles allow cheap abstractions for things like allocating, file reading, or other behavior with a common API but many possible implementations and data layouts depending on the hardware and use case.

Roles are very similar to interfaces in other languages, but boiled down to the most minimal possible implementation.

An instance of a Role is composed of two things:

• A pointer to a global struct value who's members are pointers to functions (aka methods).
• A pointer to that instance's data.

In code this simply looks like:

// A Role is just a collection of methods and some data.
typedef struct {
  void (\*add)(void\* this, int a); // pointer to add method
  ... other methods
} MExampleRole;

typedef struct {
  MExampleRole\* m, // a pointer to methods
  void\* d;         // a pointer to data of an unknown type
} ExampleRole;

// Creating something that implements the role:

typedef struct {int a;} ExampleInstance;

// defines:
// - ExampleInstance\_add function.
// - M\_ExampleInstance\_add method pointer.
METHOD\_DEFINE(/\*return\*/void, ExampleInstance,add, int a) {
  this->a += a;
}

METHODS\_DEFINE(MExampleRole, ExampleInstance\_mExampleRole,
  .add  = M\_ExampleInstance\_add,
)

ExampleRole ExampleInstance\_asExampleRole(ExampleInstance\* d) {
  return (ExampleRole) { .m = ExampleInstance\_mExampleRole, .d = d };
}

The role can then be used like:

ExampleInstance d = {0};
ExampleInstance\_add(&d, 4);
ExampleRole r = ExampleInstance\_asExampleRole(&d);
Xr(r, add, 4); // macro to call role method add
assert(d.a == 8);

It's a fair amount of boilerplate in C, but it is EXTREMELY simple and performant. Also, using a role is much easier than defining one, which is good since they are used extensively. See civ/civ.h for more documentation.

Since a role is only two pointers, best practice is to take them by value (not by pointer). I.e. "myFunction(MyRole role, int arg)"

Differences with "normal" C

The civc software stack (fngi) shares much of the C design philosophy. This includes control over memory layout and management as a central element, as well as imperative bitwise operations and logic. Unlike C, it defines a few basic data types and algorithms for manipulating them in it's std library.

The C std library has APIs that are heavily system dependant and are very tied to the unix philosophy and syscall APIs, which include hardware-heavy technology like virtual memory (handling fragmentation in hardware), preemptive multitasking and byte buffer streams. In contrast, civc provides only a block allocator, cooperative multitasking and block/sector passing.

civc is built to run on simpler hardware, with suitable abstractions (Roles) for running on more powerful hardware. Core types can work with small allocators while still working fine with larger allocators as well.

More details:

• C has no generic resource encapsulation. Civc uses Roles for this, allowing for implementing common behaviors like reading an entire file for any kind of file-like object.
• Dynamic memory management in C practically requires virtual memory, and therefore cannot be implemented on minimal hardware. Civc's core types only require a block allocator, so can be implemented on almost any hardware. Civc also uses a Role object for it's arena allocators, allowing a range of possibilities for their implementation depending on the hardware or use-case.
• Because civc is block-based, passing blocks of memory between processes should be trivial to implement at the kernel level (the kernel can keep track of who owns what block). Passing blocks and sectors of memory is much more efficient than passing bytes. While such a thing is possible in C, it is far from simple.
• Core types typically have attributes like length and capacity included, and can be safely converted between each other. This reduces programmer error and permits efficient re-use of code.
• Quality of life: known-sized types like I4 and U2 are standard. Civc believes that known constraints are better than "growing with the hardware" for systems programming. The Slot type (size_t) is the exception, since the size of a pointer must be system dependent.

Growth of a new language

The primary purpose of civc is to provide a tested foundation for the fngi language. Like C, fngi is low level. Unlike C, fngi's macros are powerful enough to inspect types and alter the syntax of the language inline. This means that it can easily build the Role types in a library using macros.

Besides civc, which itself is a very small set of data structures, fngi is intended to be a very minimalist language to bootstrap, requring only about 1000 lines of C beyond what is in civc (which itself is very minimalistic).

civ lua module

I will write more about Lua in the future. For now let it suffice that it is a tiny and powerful language with many of the feels of Python and is an excellent target language Civboot to be used primarily for scripting and building (primarily text-based) UIs.

The civ lua module provides some much-needed extentions to lua:

• expressing structs and gain minor type safety (prevent nil footguns)
• better formatting of tables and asserting equality
• essential data structures

License

civc is part of the Civboot project and is released to the public domain (see UNLICENSE) or licensed MIT under your discression. Modify this directory in any way you wish. Contributions are welcome.