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.

No comments: