Feature Request [Proto] Common Libraries

[HartmannNico]

Common Issues

This feature request is a prototype to act as collector for potential common libraries and frameworks in the S-Core stack.

Core

Core framework contains common basic capabilities to be assumed as generally present for all other frameworks in the S-Core stack.

Identification

Many items in a complex framework of frameworks need identification. Although strings as names come to mind naturally they are slow and bulky in handling.

Instead, we propose an Id and Tag mechanism that allows atomic and fast manipulation and comparison without giving too much intuition away.

Id

An Id is a single number uniquely identifying an element of the framework. The number should have a length of 64 bits. We propose to have a specific type for this instead of simply an u64 / uint64_t to have the purpose of the number clearly stated through the type.

Id should have an invalid value. We propose u64.MAX / (uint64_t)(-1).

No valid arithmetic operations are defined on ids.

Tag

Like an Id a Tag is a single value which can be guessed and read by human reasoning.

Taking a 64 bit number we can read this as 8 bytes or characters. Reading this number as 8-character word makes up a name of fixed length. This can easily converted forth and back into a string. As a plus, these tags when used in memory directly read as a single word.

Like Id's, tags shall have an invalid value. We propose u64.MAX / (uint64_t)(-1).

Example: 'ValidTag' is a valid tag with the above properties, the byte string is 0x56 0x61 0x6c 0x69 0x64 0x54 0x61 0x67, resulting in the value 0x67615464696c6156.

On top, longer names can be converted into such a number using a hashing algorithm. We propose Fowler-Noll-Vo 1a for this as it is fast, has excellent collision behavior and can statically be calculated.

Note: As tags will in practice all be known before runtime freedom from colliding hashes can be guaranteed.

To distinguish hash tags from name tags we propose to use the MSB of the word which is zero in names anyway and can be set to one in hash values.

No valid arithmetic operations are defined on tags.

Type System

In a distributed framework the presence of uniquely identifiable types with a defined memory layout is essential. Especially in combination with zero-copy communication patterns shared data must have formats all sharing participant unanimously read and write the same.

Type Identification

We propose to give types a unique Tag within the S-Core stack that is independent from compiler, operating system or architecture.

This unique name can easily be attached to a type with traits in Rust and C++. Rules for composed types like tuples, arrays and structs extend the tagging mechanism to these types.

Example

impl TypeTag for bool {
    const TYPE_TAG: Tag = Tag::new(*b"@bool___");
}

Type Properties

For data stored and eligible for exchange in zero-copy memory some additional properties are required.

To ensure unanimous interpretation of any value we need the following properties on the type:

• Reloc: The type must be relocatable. That is, it writes and reads the same without regard of the absolute memory location it is currently in.
• Coherent: The type must be coherent. That is, all data of a value of the type occupies adjacent memory locations. That way serialization and deserialization is not required when transferring those values through zero-copy mechanisms.
• Fixed: The type must have a fixed size. The fixed size does not necessarily need to be known at compile time (which is Sized), but at allocation of a value. The type can still store a dynamic number of values, but does not have a dynamic size.

In addition, a useful but not necessary property of a type is a statement about operations on that type being lock-free (Lockfree).

Implementation Note: These properties can easliy associated with types using marker traits.

Collection Types

For the standard QM-case we propose to use the standard library implementations of the respective programming languages.

However, in safety-critical and zero-copy scenarios additional properties of types to guarantee certain behavior of the operations like 'no allocations', 'lock-free', 'no exceptions thrown'.

The following data structures should be available in a lock-free (Lockfree) implementation, both for allocating and non-allocating, fixed size (Fixed) variants:

• Stack<T: Tagged>: A last in-first out structure without insertion or deletion other than the 'top'.
• Vec<T: Tagged>: A first-in, first-out structure without insertion other than tail and deletion other than head and tail.
• Hashmap<K: Hash,T: Tagged>: A map of keys with a hash function associated to values of arbitrary type.
• Tree<T: Tagged>: A binary tree of values.

Hashing

General hashing of types required the implementation of certain hash alogorithms that can be assumed as present and identical. We propose:

• FNV1a
• CRC32/64
• MD5
• SHA2

OS Abstraction

Many frameworks need elementary items from the underlying operating system. To support the individual demands of frameworks the standard library implementations in Rust and C++ offer neither a sufficient, nor a compatible set of APIs. Hence for fundamental resources we propose an operating system abstraction layer (OSAL) to be available to all frameworks in the S-Core stack.

Memory

Memory abstraction specifically targets at the allocation and deallocation of memory. While the allocation of local process memory is sufficiently abstracted through malloc/free, new/delete and Box<T>, Rc<T> and Arc<T>, respectively this does not hold for shared memory provision.

The OSAL shall provide means to allocate and deallocated named shared memory segments. The allocation shall be able to provide access attributes for read and write to enable mixed criticallity safety scenarios.

Runtime

For runtime implementations we require extended access to computing and synchronization resources beyond the capabilities of standard libraries.

CPU architecture

The OS abstraction shall be able to provide CPU architecture attributes such as

• Number of CPU cores
• Information on cores (performance, efficiency, etc.)
• Endianness of data values. We propose to expect "little endian" to be defined as standard.

The OS abstraction should be able to group cores non-exclusively into core-groups that allow clustering of cores to be used in thread-bindings.

Threads

The OS abstraction shall provide an API to access threads in the current process context. The following attributes shall be assignable to and readable from a thread:

• A name
• A priority
• A core affinity (and core-group affinity)

The following attributes shall be assignable to a thread upon creation:

• A thread function with (captured) arguments passed for the parameters of the thread function.
• A result type

The abstraction shall provide means to access the current thread.

The abstraction shall provide means to spawn new threads.

The abstraction shall provide means to join a thread, blocking the current thread until the thread to join terminated. Join shall provide the result of the thread procedure or an appropriate error in case the join failed.

The abstraction shall provide means to check on the current state of the thread, namely if the thread is still running or has finished. "Finished" means the thread can join without blocking.

As there is no common function in operating systems to kill a thread from the outside it is expected to cooperatively terminate threads by signaling termination from the outside.

Synchronization

Synchronizing threads is usually provided through standard library functions. We expect the use of synchronization primitives to be covered by the standard library, as long as these primitives operate within the local process context. These are:

• Condition Variables: synchronization elements to encapsulate OS events or signals, allowing the current thread to wait on them with and without timeout, and allowing other objects to issue a notification (notify_one, notify_all) to waiting threads.
• Mutexes: Mutually exclusive resource protection structures that allow the resource to be locked for exclusive access by the current thread. Usual operations:
  • lock: unconditional lock, wait until available
  • lock_timeout: unconditional lock, wait until available with timeout
  • try_lock: test the lock and acquire if possible, otherwise return with negative indication

Synchronization mechanism of standard libraries do not span process boundaries. For runtime orchestration this is required.
The OS abstraction shall provide means to create and connect to named events. These events shall have the following operations:

• wait: wait for the event to occur, block the current thread until it does
• wait_timeout: wait for the event to occur with a timeout, return when occurrence happened or timeout expired. Report which happened.
• notify_all: trigger the event and notify all waiting threads in all processes.

Time

Clocks

The OS abstraction shall provide unified access to time through clocks. A clock is an entity that provides steadily increasing timepoints through an operation now(). The difference between two timepoints we call a duration.

We assume the use of Timepoints and Duration as defined by the standard libraries.

A clock shall provide the following information:

• frequency: The frequency with which the clock increments timepoints
• start: The timepoint at which the clock started

Furthermore, a clock shall provide an operation sleep_until(timepoint) that performs an accurate interruption of thread progress until the timepoint indicated is reached by the clock. For timepoints in the past the function shall return immediately.

There shall be a high-resolution clock that is implemented on the CPU directly.

There shall be a time-synchronized clock with a global timebase. This is not necessarily an OS function but requires additional time synchronization frameworks. The OS abstraction shall provide means for such frameworks to provide a global clock through the OS abstraction.

Time

Apart from specific clocks the system time shall be provided through the means of the standard libraries.

Storage