Friday, February 11, 2022

Layers II

In "Layers", I wrote about one way to think about the architecture of Diminuto ("tiny"), my open-source library of C functions that I find useful for the kinds of systems programming tasks I am frequently called upon to perform, either by my clients or for my own projects. That article considered the layers of Diminuto in a conceptual fashion: documentation, types, logging, errors, assertions, unit tests, wrappers, models, and functional tests. In this article, I'll be taking a more functional approach, writing about the library in terms of projects (repositories), themes (broad capabilities within a project), and features (individual APIs that support those capabilities). The themes, and the features within each theme, are roughly in order from lowest layer to highest (higher layers depend on lower layers).

Disclaimer: The purpose of both this article and the earlier "Layers" is mostly to document the architecture of the library, largely doing so for my own use. Whether you find it useful or even interesting may depend on whether you do the kinds of low-level things I get paid to do, in C or similar systems programming languages, especially in the Linux/GNU/POSIX milieu. If your daily-driver programming language is something like JavaScript or Python (both of which I've also used), most of this kind of stuff will already have been provided in some language-specific package.

In all cases, the features I name correspond to C header files of the same name; for example, the feature diminuto_time corresponds to the header file diminuto_time.h in a standard directory in which the public Diminuto APIs are defined. (There are also private Diminuto APIs that are shared amongst the features themselves.)

All of the features described here have unit tests, some have functional tests (some of which require purpose-built hardware test fixtures), and many are used in command line utilities, that not only test the features, but serve as demonstrations on how the features may be used. Other projects of mine, some of which are mentioned below, are built on top of Diminuto, and are also good examples of how to leverage the library.

These are just a subset of the Diminuto features. I've omitted some of the more obscure ones.

Theme: Types

Most of the Diminuto header files define their own types that are used by that particular feature. But some types are so ubiquitous that their definitions are unified into a single header file. This is especially true for types that may be used to pass function arguments between features, or for types that would otherwise result in circular feature dependencies.

Features:

diminuto_types includes the C library and system header files that define frequently used types like int64_t and size_t. It also defines widely-used Diminuto-specific types like diminuto_ticks_t (more on ticks later) and diminuto_ipv4_t.

Theme: Macros

This theme includes features that define macros that do useful things in the spirit of the standard C sizeof operator. These get used a lot.

Features:

diminuto_countof defines a macro that returns the dimension of a one-dimensional array (not its size).

diminuto_widthof defines a trivial macro the returns the bit-width of a type.

diminuto_typeof defines a common macro to infer the type of a variable. It should work with either GNU or ISO compliant C compilers.

diminuto_offsetof defines a macro that computes the byte-offset of a specified field from the beginning of the structure in which it resides.

diminuto_containerof defines a macro that computes the memory address of a container given the structure describing the container and a pointer to a field inside the structure.

diminuto_memberof defines a macro that creates a reference to a specified field in a structure without having a pointer to a structure of that type. It is typically used in conjunction with the sizeof operator.

diminuto_minmaxof defines macros that compute the minimum or maximum possible values of a type, automatically taking into account whether or not the type is signed, for integer types that use two-complement encoding.

diminuto_cxxcapidiminuto_begin, and diminuto_end define macros that simplify the integration of C and C++ code bases. ("cxxcapi" may be pronounced "sexy API".)

diminuto_new and diminuto_delete (added 2023-03) dynamically allocate and free objects of a caller-specified type, and invoke caller-defined constructor and destructor functions.

Theme: Data Structures

Features:

diminuto_list implements a circular doubly-linked list object. I have found this data structure to be remarkable flexible and useful.

diminuto_tree implements a self-balancing red-black tree. I based this implementation on code in the U-Boot boot loader, which was authored by the same person who wrote the red-black tree implementation used internally by the Linux kernel. (I don't know which one came first, the U-Boot or the Linux kernel implementation. My code looks nothing like either of those, and all bugs are strictly my own).

diminuto_store implements a keyword-value store using a diminuto_tree.

Theme: Time

One of my complaints about the various Linux/GNU and POSIX library function calls that deal with time is that the units are all different: seconds, microseconds, nanoseconds, etc. And all of the functions use structures, which makes it challenging to use them in computation. Diminuto instead defines a standard unit called a tick that is a sixty-four bit wide integer. There is an unsigned version, diminuto_tick_t, and a signed version, diminuto_stick_t (which is totally okay to pronounce as "stick"). All of the time-related Diminuto features use one of these two types in which to store durations, timeouts, and the time of day. The current resolution of the Diminuto tick is one nanosecond.

Features:

diminuto_frequency provides functions that return the resolution of the Diminuto tick in units of Hertz. All of the other Diminuto features in this theme also define functions that return the maximum resolution of their underlying Linux or POSIX implementation in units of Hertz. This provides applications guidance as to what time-related values are useful.

diminuto_time provides functions to return the time of day in ticks since the POSIX Epoch, the elapsed time of a monotonically increasing clock that is not subject to NTP or CLI adjustments, the CPU time for the calling process, the CPU time for the calling thread, and the value of a logical clock that simply returns a monotonically increasing counter value. With the exception of the logical clock, all functions return values in units of ticks.

diminuto_delay provides a function to delay the calling thread until at least the specified number of ticks have elapsed. There is both an interruptible (by a POSIX signal) and an uninterruptible version. It also defines a function that forces the calling thread to context switch, and another to block the thread until any unblocked signal arrives. (There is also a signal theme that we will discuss shortly.)

diminuto_timer provides functions that use real-time POSIX timers to create and manage timers of both the one-shot and the periodic variety. It also defines functions on top of these that mimic the old setitimer(2) semantics, but with monotonic POSIX timers that (unlike the old mechanism) are not subject to variation due to NTP or CLI time adjustments.

Theme: Utilities

This theme includes features that don't quite fit in anywhere else, but these features are used in many of the higher layers.

Features:

diminuto_log defines macros and provides functions that implement a multi-level logging mechanism that automatically determines whether to write messages to the system log (syslog(3)) if the caller is a daemon, or to standard error (stderr(3)) if it is not. It also includes a way to import what log levels are enabled and disabled from an environmental variable. (As you might expect, this gets used everywhere.)

diminuto_unittest defines macros for a simple unit-test framework. (This gets used in almost all of the Diminuto unit tests, except for a few which predate it.)

diminuto_dump provides functions to write a formatted multi-line hexadecimal dump of application data to a FILE stream like stderr(3).

diminuto_phex provides functions to write application data to a FILE stream like stderr(3), while turning unprintable characters into standard C-style escape sequences. (The name is short for "print hex" and may be pronounced "fex".)

diminuto_escape provides functions to expand single unprintable characters in a buffer into C-style escape sequences, and to collapse C-style escape sequences in a buffer into single characters.

diminuto_fibonacci provides functions to generate Fibonacci numbers. (Yeah, I know this sounds crazy; but Fibonacci numbers lend themselves well to problems in backoff-and-retry error recovery, and progressively larger dynamic resource allocation.)

Theme: State Machines

There is really only one complicated state machine in Diminuto, but it's a useful one.

Features:

diminuto_framer is a state machine that implements a framing mechanism for arbitrary binary octets over sequential data streams. Such streams can be over serial ports (actual serial hardware or USB serial adaptors), TCP stream sockets, or what have you. A frame contains a header with a sixteen-bit length (65535 maximum payload size) and sixteen-bit sequence number (65536 window size), a Fletcher-16 checksum that protects the header, and a Kermit-16 (a.k.a. CRC-CCITT) cyclic redundancy check that protects the payload. The Framer uses a byte-stuffing mechanism borrowed from the High-level Data Link Control (HDLC) protocol. The Framer feature offers a multilevel API that gives the application a lot of discretion about how it wants to approach input and output of its serial data. (Added 2023-05-01.)

Theme: Signals

Signals are a kind of software interrupt widely used in UNIX/Linux/POSIX systems software. There are all kinds of signals, but only a few of the most commonly used are directly supported by features in Diminuto. The API for handling each signal is mostly the same for each feature, except where noted. (I tend to add support for additional signals in Diminuto organically, i.e. when I need them.)

Features:

diminuto_alarm supports the SIGALRM signal: a timer has elapsed.

diminuto_hangup supports the SIGHUP signal: the controlling terminal has disconnected.

diminuto_interrupter supports the SIGINT signal: the user has typed control-C on the controlling terminal.

diminuto_reaper supports the SIGCHLD signal: a child of the receiving process has terminated. Left to its own devices, this feature will also reap the child: collect its final exit state so that the kernel can reclaim its resources.

diminuto_terminator supports the SIGTERM signal: the receiving process has encountered a condition that would otherwise terminate it.

diminuto_uninterruptiblesection defines a set of bracketing C macros - typically a begin macro and an end macro - that can be used to temporarily block or delay the reception of a specified signal. They are used to protect a kind of critical section. (We'll see this same pattern later in other themes and features.)

Theme: Interprocess Communication

Features:

diminuto_ipc provides socket-related functions that are common across all addressing and protocol flavors. Many of the functions in this feature are applicable whether the application knows what kind of socket it is applying them to.

diminuto_ipc4, diminuto_ipc6, and diminuto_ipcl provide functions that simplify establishing socket connections with remote end points, using IPv4, IPv6, or Local (a.k.a. UNIX domain) addressing, respectively. The orientation of the connections may be streams (TCP), datagrams (UDP), or - in the case of Local sockets - sequenced packets (SCTP). This last orientation, sequenced packets, can be used to transfer open file descriptors across process boundaries, and there is a unit test that does exactly that. (Sadly, SCTP, a protocol developed to connect SS7 telephone switches in the PSTN, which combines the reliability of streams with the fixed message boundaries of datagrams, and which is directly supported by the Linux/GNU OS, is not supported by most internet routing hardware, which is why it is only supported in Diminuto for Local sockets.)

diminuto_mux and diminuto_poll provide mechanisms to multiplex file descriptor (including socket) I/O. Both provide the capability to either block indefinitely or to timeout; in the latter case, the timeout duration is specified in (you guessed it) ticks.

diminuto_scattergather provides an (admittedly overly complicated) interface to handle vector I/O.

Theme: Processes

Features:

diminuto_core provides a function that enables an application to produce a core dump if it terminates unexpectedly, and also a function to cause it to terminate expectedly with a core dump if it is enabled.

diminuto_daemon provides functions for the caller to turn itself into a daemon (which does not inherit its parent's file descriptors), or a service (which does inherit its parent's file descriptors), or to run a shell command as a separate process, in the background, detached from the caller.

diminuto_module provides functions to implement a simplified interface to the system dynamic linker. This allows an application to dynamically load and invoke separately compiled functions at run-time. (I totally swiped this idea from the Asterisk open-source PBX.)

Theme: Threads

These Diminuto features are wrappers around the use of pthreads(7) functions. They aren't just conveniences; they implement a specific model of using POSIX threads that I've found broadly useful in other projects.

Features:

diminuto_mutex provides functions to support the use of mutexes for mutual exclusion.

diminuto_condition provides functions to support the use of condition variables.

diminuto_thread provides functions that support the creation, management, and termination of POSIX threads.

diminuto_criticalsection defines a set of bracketing C macros that use a caller-provided mutex to protect a critical section.

diminuto_readerwriter implements a first-in first-out readers-writers synchronization lock.

Theme: File System

Features:

diminuto_fs provides functions to interrogate an object in the file system for its type; to canonicalize a file system path name (e.g. resolve all soft links); to progressively make all the sub-components in a directory path; and to recursively walk the file system, applying a caller-provided function to each object encountered.

diminuto_lock provides a kind of atomic locking capability using a file in the file system. This technique is widely used by daemons.

diminuto_observation provides a mechanism to atomically update a file in the file system such that other processes will never see an intermediate state in the contents of the file. I have used this in other projects to support headless operation of long-running processes.

Theme: Real-Time

This theme addresses issues in the real-time behavior of a system, including traffic shaping (controlling the rate at which events are generated) and traffic policing (controlling the rate at which events are accepted).

Features:

diminuto_throttle implements a mechanism that shapes or polices real-time events using a traffic contract enforced using the Generic Cell Rate Algorithm (GCRA). The traffic contract is specified using an interarrival increment (in the literature, referred to as i), a total threshold or limit (l), an expected interarrival time (x), and an actual interarrival time (x1). All the parameters are specified in ticks.

diminuto_shaper implements a more complex traffic contract enforced using two diminuto_throttle objects, one to control the peak rate with a specified jitter tolerance, and one to control the sustained rate with a specified maximum burst size.

Theme: Close to Bare Metal, Safeties Off

This theme collects the features that interact more directly with hardware, or with the kernel in ways that may require that the calling application have root privileges.

Features:

diminuto_serial provides a simple set of functions to configure a serial port.

diminuto_cue provides a simple function to debounce a digital signal. (I didn't invent this algorithm, and I admire the person that did.)

diminuto_pin provides functions to control and interrogate General Purpose I/O (GPIO) pins through the standard /sys kernel interface. GPIO pins are manipulated via FILE streams, and hence ultimately use file descriptors, which allows them to be multiplexed, and read via interrupts on the leading or trailing edge of a digital signal.

diminuto_i2c provides convenience functions for communicating with other devices over an I2C bus. (This is one of several features that I test using a breadboard with a purpose-built test fixture.)

diminuto_coherentsection defines a set of bracketing C macros. The begin macro implements a read memory barrier with acquire semantics, and the end macro implements a write memory barrier with release semantics. (It bothers me that I have no real way to test this.)

diminuto_memory provides functions to interrogate the kernel for details about the memory sub-system, like the virtual page size, and the Level 1 cache line size.

diminuto_map provides functions for privileged applications to map physical memory addresses (for example, of memory-mapped hardware devices) to virtual memory addressed, and to release such mappings. (I confess I don't test this very often.)

diminuto_modulator implements a Pulse Width Modulation (PWM) generator using diminuto_timer and diminuto_pin. No guarantees as to its precision and accuracy, since it is running in user space. (I've used this successfully for LED brightness control.)

diminuto_controller implements a Proportional/Integral/Differential (PID) controller, although again no guarantees as to its precision and accuracy, since it is running in user space. (I have used this successfully to implement a feed back loop between a light sensor and an LED, and between an A/D voltage sensor and a D/A voltage output.)

Theme: Command Line Tools

Here is a partial list of Diminuto command line utilities, built using the library, that can be run interactively or from a shell script. (These are indispensable tools in my day-to-day development, testing, and reverse engineering toolbox; they alone might justify use of the library.)

Features:

coreable enables core dumps for the specified command.

dump displays its input in a formatted hexadecimal dump.

endpoint converts an endpoint name consisting of a printable IPv4 or IPv6 address, host name, domain name, or local path name, and a printable port number or service name, into a binary IPv4 or IPv6 address or canonical path name (with all the soft links resolved), and binary port number.

internettool verifies internet connectivity.

log logs messages taken from the command line and/or standard input.

observe watches for an observation file and indicates when it arrives.

phex displays its input in a printable form, changing unprintable characters into C-style escape sequences.

pinchange executes a command when a GPIO pin changes state.

pintool manipulates GPIO pins.

pps (pulse per second) uses pintool to multiplex on a 1PPS GPIO pin.

renametool atomically renames files or swaps files in the same file system.

serialtool manipulates serial ports.

shaper shapes traffic in a shell pipeline.

Other Projects

Briefly I'll mention some of my other projects that make use of Diminuto. This is only a partial list. I'll abbreviate the names of the features just for readability.

Hazer is my project for all things GPS, or more broadly GNSS, and even for some IMU work. Hazer uses Critical Section, IPC4, IPC6, List, Dump, Escape, Lock, Observation, Thread, Tree, many of the Signal handlers, Log, and others. The applications gpstool and rtktool in Hazer especially depend on Diminuto.

Assay is my project that uses the GNU Bison and Flex tools (formerly YACC and Lex in other versions of UNIX) to implement a parser for parameter files, or what are generically referred to by Microsoft and others as parmfiles, containing keyword=value pairs. Assay uses Container Of, Dump, Escape, Tree, and other features not mentioned here. (Be forewarned that everyone has their own idea of what the syntax of a parameter file should be. Assay is no different.)

Codex was my excuse to learn how to use OpenSSL. Codex uses Critical Section, Tree, Delay, IPC4, IPC6, and Log.

Placer was my way of relearning how to use SQLite after being away from it for years. Placer uses Log, Phex, and Fibonacci.

In addition, Diminuto, or portions of it, has shipped in several products I helped my clients develop.

Thursday, February 03, 2022

Revisiting the First-Come First-Served Reader-Writer Solution

In "First-Come First-Served Readers and Writers in C using Monitors", I wrote about my solution to the classic Readers-Writers concurrency problem, in C using POSIX threads. My solution maintained the multiple-reader/single-writer invariants, but enforced access to the shared resource (whatever it was) in strict time order: readers could access the shared resource concurrently providing a writer had not requested accesses ahead of them. While POSIX threads provides its own Readers-Writers lock solution - see pthread_rwlock_rdlock(3) and pthread_rwlock_wrlock(3) - strict time ordering is not necessarily guaranteed.

My diminuto_readerwriter code, part of my Diminuto C-based systems programming library that I've been maintaining and expanding since 2008, worked fine for what I needed at the time. But it had one flaw that prayed on my mind: it required that the application provide an array that the algorithm could use in which to store state. This wasn't a big deal, except that sizing the array was sometimes not straightforward. And it just seemed awkward. Since I was thinking of using the Reader Writer code for another purpose, I finally decided to fix that.

I replaced the array - what the API referred to as the ring buffer - with a diminuto_list (or just List), a doubly-linked-list structure provided by the library, for what the API now refers to as the wait list. The root of the List was part of the structure that defined the diminuto_readerwriter (or just Reader Writer) lock object. Each thread now has a List node that is automatically dynamically allocated on first use and stored in the thread's thread-local storage (see pthread_key_create(3)), and is automatically freed when the thread exits. No matter how many Reader Writer locks you use, you only needed one List node per thread, because a thread can only block on one Reader Writer lock at a time.

This worked out really well. All of the storage management of the wait list was completely under the hood and handled automatically. The application didn't have to worry about sizing anything. And the wait list offered some additional useful capabilities.

It greatly simplified the implementation of timeouts, where a thread could get an error return from its Reader Writer request if it could not be serviced within a specified time interval. This was especially useful in some niche applications in which a timeout of zero is used to poll for resource availability.

It also made it easier to implement priority, or expedited, requests, in which the blocking thread is pushed onto the front of the wait list instead of queued at its end. This allows applications to, for example, give a specific writer priority over readers and other writers. This is useful for real-time events, like the loss of a socket connection, to cancel pending transactions and possibly take corrective action ahead of waiting readers and writers.

But what I really liked about this refactoring of my Reader Writer solution is that it reminded me of how much I like using Diminuto's implementation of Lists. Because it's an implementation that doesn't use null pointers.

A Diminuto List node consists of four pointer fields: next, prev, root (all of which point to a node) and data (a generic void pointer). (As usual, you can click on an image to see a larger version.)

diminuto_list_t

The next and prev field are obvious: they are the pointers that actually implement the doubly-linked-List. One of the advantages of a doubly-linked-list is that a node can be removed from a List by starting with just a pointer to the node; no other information is necessary to link the prev node with the next node and making the List whole again. Similarly, you can insert a new node into a List using just a pointer to the new node and a pointer a node that is already on the List; the new node can be easily added before or after the existing node.

The root field points to the root of the list; this allows the application to identify what List any node is on. When a new node is inserted onto a List, it automatically inherits the root of the node that is already on the list.

Here's the interesting part: when a node is initialized, its next, prev, and root pointers are all set to point to itself. No null pointers (except perhaps for the data pointer; we'll get to that in a bit). All List nodes start out life as a List of one node, serving as their own root.

InitializedNode

The root of the list - the node that is used to represent the List itself - starts out life like this: with its root pointer pointing to itself. As new nodes are queued to the end of the List or pushed onto the front of the List, they inherit the root pointer of the root node. Traverse the list in either direction and you come back to the root node. You know it is the root node, because its root pointer points to itself. You know if a List is empty if the next and prev pointers of the root node point to itself. This also makes is trivial to access the head or the tail of a List.

Thus, the Diminuto List isn't just a doubly-linked-list, it is a circular-doubly-linked-list. 

FiveNodes

There is a simple iterative mechanism in the List API to re-root a list so that some other node represents the List. This works because there is no difference between the root node and any other node on the List. 

Except - maybe - the data pointer.

The data pointer is for whatever the application wants to use it for. None of the List implementation implicitly reads or modifies the data field of a node. The List node initialization function doesn't touch the data pointer. Typical applications using a Diminuto List use the data pointer to contain application data (or a pointer to such), or a pointer to the structure in which the List node structure itself is embedded.

The Reader Writer object uses the latter technique: it has embedded in it a List node structure used as the root of the wait list, and the data pointer in that single List node is set to point to the Reader Writer object itself. This allows any thread on the wait list to trivially access the Reader Writer object on which it is waiting by [1] accessing the pointer to its own List node in its thread-local storage, [2] going through the root pointer of that node to the root node, and finally [3] going through the data pointer of the root node.

Meanwhile, the data pointer in every individual thread's List node in its thread-local storage is used to store an enumerated value (not a pointer) used by the algorithm to indicate the state of the thread in regards to the Reader Writer object: waiting reader, waiting writer, pending reader, pending writer, running, etc.

The replacement of the ring buffer with the wait list in the Reader Writer object was straightforward. I wish I had been brave enough to use that approach when I first implemented it. I wrote Diminuto List in C, but I don't see any reason why it couldn't be written in any other language that has pointer references.