Old Dog, New Tricks

In their article "File Descriptor Transfer over Unix Domain Sockets" in their blog CopyConstruct, distributed systems engineer Cindy Sridharan references an article by Facebook engineers and others that appeared in the proceedings of a virtual ACM conference: "Zero Downtime Release: Disruption-free Load Balancing of a Multi-Billion User Website" [Usama Naseer et al., SIGCOMM '20, 2020-08-10]. It's a real eye opener. I thought I was pretty conversant with the socket interface available in Linux, having been doing that kind of interprocess/interprocessor communication since my 4.2 BSD days on a VAX-11/750. Apparently I have some catching up to do.

Sridharan's article points out that you can transfer open sockets from one process to another, running on the same computer, via a UNIX domain socket, in the address family AF_UNIX (a.k.a. AF_LOCAL). UNIX domain sockets (or what I typically refer to as "local sockets") only work between endpoints on the same computer. Instead of using an IP address and port number, the rendezvous between endpoints is identified using a unique name in the file system namespace. Local sockets are have been around for eons, but I was not aware of this use for them.

What this is not is a child process inheriting a file descriptor from a parent process. This is sending a message over a local socket from one process to another that effectively results in a dup(2) system call on the receiving end for one or more file descriptors from the sending end that are specified in the message. The system calls involved are sendmsg(2) and recvmsg(2).

ssize_t sendmsg(int sockfd, const struct msghdr *msg, int flags);

ssize_t recvmsg(int sockfd, struct msghdr *msg, int flags);

Even the socket type was a new one on me: SOCK_SEQPACKET, which exchanges a message having fixed boundaries like a datagram, but which has guaranteed delivery like a TCP socket.

int listensocket = socket(AF_UNIX, SOCK_SEQPACKET, 0);

I had used sendmsg and recvmsg with struct msghdr before, to send and receive vector I/O using datagrams. You can find examples of this in my test program unittest-ipc-scattergather.c that I described in a previous article "Scatter/Gather".

But struct msghdr has additional fields that can be used to transmit additional ancillary information (the term used in the manual page). This includes control messages like SCM_RIGHTS, which enables the transfer of open file descriptors across process boundaries. (You still have to transmit at least one byte of conventional data, even if it is ignored by the far end; the control message tags along.)

You can find the test program described here at unittest-ipc-ancillary.c. In that program, there is one "main" process, one "workload" process, and four "instance" processes. 

The workload process manages a pool of sixty-four client threads. Each active client thread is trying to connect to the same listen socket identified by an IP address and port number. When the connection is established, the client writes one or more requests, and for each request reads a response from the server on the far end. Then the client closes the connected socket, returns itself to the thread pool, and ends. The workload process continuously waits for a client thread to appear in pool; it removes it from the pool and starts it.

Each instance process uses sendmsg to send a message to the main process over a local socket asking for the listen socket. The listen socket is a conventional socket identified by an IP address and port number, and has pending client threads waiting for their connection to be accepted. The main process receives the request using recvmsg and replies using sendmsg with its open listen socket to one instance process at a time until that process exits and its status is waited for by the main process. Then the connection request of the next instance process is accepted, and it is sent the same open listen socket.

Each instance process manages a dispatcher thread. The dispatcher thread continuously accepts connection requests on the listen socket from client threads, and assigns each new stream socket to one of eight server threads that it has started from a thread pool. When the client thread closes its end of the socket, the server thread returns itself to the thread pool and ends. During a single activation, a server thread services a sequence of requests from a single client.

The main process that drives the test gives each of the eight instance process ten seconds to service as many clients as it can before it is signaled by the main process to exit.

Here is a code snippet lifted from that test program for the sending side. diminuto_ipcl_packet_send() is the function in my Diminuto library that calls sendmsg.

struct iovec vector[1];

struct msghdr message;

union { struct cmsghdr alignment; char data[CMSG_SPACE(sizeof(int))]; } control;

struct cmsghdr * cp;

char dummy[1] = { '\0' };

 

vector[0].iov_base = dummy;

vector[0].iov_len = sizeof(dummy);

message.msg_iov = vector;

message.msg_iovlen = countof(vector);

message.msg_control = &control;

message.msg_controllen = sizeof(control);

cp = CMSG_FIRSTHDR(&message);

cp->cmsg_level = SOL_SOCKET;

cp->cmsg_type = SCM_RIGHTS;

cp->cmsg_len = CMSG_LEN(sizeof(listensocket));

memcpy(CMSG_DATA(cp), &listensocket, sizeof(listensocket));

ASSERT(diminuto_ipcl_packet_send(activationsocket, &message) == sizeof(dummy));

Here is a code snippet from the receiving side. Similarly, diminuto_ipcl_packet_receive() calls recvmsg. Note that the value returned by both sendmsg and recvmsg is the length of the dummy payload, not the length of struct msghdr or struct cmsghdr.

char dummy[1];

struct iovec vector[1];

struct msghdr message;

union { struct cmsghdr alignment; char data[CMSG_SPACE(sizeof(int))]; } control;

struct cmsghdr * cp;

ssize_t length;

int listensocket = -1;

 

vector[0].iov_base = dummy;

vector[0].iov_len = sizeof(dummy);

message.msg_iov = vector;

message.msg_iovlen = countof(vector);

message.msg_control = &control;

message.msg_controllen = sizeof(control);

ASSERT((length = diminuto_ipcl_packet_receive(activationsocket, &message)) == sizeof(dummy));

for (cp = CMSG_FIRSTHDR(&message); 

     cp != (struct cmsghdr *)0; 

     cp = CMSG_NXTHDR(&message, cp)) {

  if (cp->cmsg_level != SOL_SOCKET) { continue; }

  if (cp->cmsg_type != SCM_RIGHTS) { continue; }

  if (cp->cmsg_len != CMSG_LEN(sizeof(listensocket))) { continue; }

  memcpy(&listensocket, CMSG_DATA(cp), sizeof(listensocket)); break; 

}

The test program is constructed such that the listen socket being passed to each instance process doesn't even exist when the instance processes are forked. The only way the listen socket could be known to the instance processes is via the control message mechanism.

This is a remarkable capability. I own Cindy Sridharan a debt of gratitude for bringing it to my attention.

Addendum (2020-12-15)

Fazal Majid was kind enough to pass along the fact that this capability has been around for a long time, and cited a classic reference that I have on my bookshelf just a couple of feet away.

W. Richard Stevens, Stephen A. Rago, Advanced Programming in the UNIX Environment, 2nd ed., Addison-Wesley, 2005

It took me a few minutes to find it: 17.4.2, "Passing File Descriptors over UNIX Domain Sockets", pp. 606-614. I'm embarrassed to admit I missed this. In my defense, the book is 927 pages long. A big thank you to Mr. Majid for pointing this out.

Addendum (2020-12-16)

The SOCK_SEQPACKET socket type looks pretty interesting, doesn't it? It has the reliability of SOCK_STREAM with the fixed message boundaries of SOCK_DGRAM. Why don't we see it used more? Because underneath the hood it uses neither the Transmission Control Protocol (TCP) used for streams, nor the User Datagram Protocol (UDP) used for datagrams, the two transport-layer protocols on which most of the Internet is based. Instead, it uses the Stream Control Transmission Protocol (SCTP) developed for Signaling System 7 (SS7), the telecommunications protocol stack used to set up and tear down telephone calls in the Public Switched Telephone Network (PSTN). SCTP is defined in RFC 4960. SCTP isn't as widely deployed in the Internet at large as its peers in the transport layer. I'm not confident SCTP packets would make it through all firewalls. And it's not that hard to parse out fixed size messages from TCP streams. Diminuto provides an API to create a sequential packet socket only for the UNIX domain (local) address type, where it might be useful for inter-process communication on the same computer.

Scatter/Gather

The Linux kernel has a variety of I/O system calls that can be used to write data to and read from a file, device, or network. Which system call you use depends in part on how you want to treat the data, for example as as an unformatted (to the kernel anyway) stream of bytes, or as a fixed length datagram. Recently I was reminded of the readv(2) and writev(2) system calls, which read and write vectors of data which reside in non-contiguous areas in memory.

(Click on any image to see a larger version. Or any version of all, since Blogger doesn't alway play well with Flickr.)

These calls take, not a pointer to a buffer and a length in bytes, as is typical of other I/O system calls, but a pointer to an array known as an I/O vector (not to be confused with an interrupt vector), and a count of the number of positions in the array. (The readv and writev system calls are for streams; there are similar system calls, recvmsg(2) and sendmsg(2), that you can use for datagrams.)

Every array position in the I/O vector is an iovec structure. Each iovec structure contains a pair of fields: a pointer to the data to be written or a buffer into which data will be read, and the length in bytes of the data to be read or written.

I take it from the comments in the header file that readv and writev were originally adapted from the Berkeley Software Distribution (BSD), a UNIX variant I cut my teeth on decades ago on a DEC VAX-11/750. But it was later, at the National Center for Atmospheric Research in Boulder Colorado, where I was introduced to vector I/O, which was used to read and write ginormous lists of floating point numbers used in the specialized vector supercomputers at that national lab. Those high performance machines could do many identical floating point operations in parallel on those data vectors, multiplying and dividing dozens of numbers together all at once. I'm told vector I/O also has its place in high performance graphics hardware.

But my interest in vector I/O comes from the many years I've spend working in protocol stacks for technologies, like Asynchronous Transfer Mode (ATM) and cellular base stations, in the telecommunications industry.

Vector I/O

Supposing you want to transmit a packet whose wire format - what it looks like as it is transmitted over the network, not necessarily what it looks like in memory - looks like this. (This is a pretty simple example compared to typical network protocols.)

The wire format has five fields: a four-byte IPv4 address, a two-byte port number, an eight-byte payload length (which would be overkill for sure), a variable length payload, and finally a two-byte (sixteen-bit) checksum.

These fields may not be in a contiguous location in memory in the protocol stack. In fact, because of memory alignment requirements for the different fields, it may be impossible for them to be contiguous without copying each field byte by byte into a buffer as character data. Furthermore, the way protocol stacks are designed, these fields are probably not managed by the same software layers. By way of a trivial example, when creating an outgoing packet: one layer dealing with the application and business logic generates the payload; another layer responsible for packaging the payload and insuring it arrives intact adds the length field to the beginning and the checksum to the end; and a third layer whose duty is to route the data to the recipient adds the address and port number to the beginning.

One way I've seen this handled in production software is to do a lot of data copying and recopying. That tends to be expensive in terms of time and memory usage. Another way (which I thought was pretty clever, I wish I'd thought of it) was to use double-ended buffers: a single buffer was passed through the layers, the application put its payload more or less in the middle of the buffer, and each successive layer prepended and appended fields to either end. This still involves a lot of data copying from application variables into a contiguous buffer. I wondered if I/O vectors could be yet another approach to solving this problem.

You may have read or heard about zero-copy I/O. This is not that. Vector I/O is a way to eliminate copying in the application from variables to a buffer. Zero-copy I/O is a way to eliminate copying between user space where the application runs and kernel space where the device driver runs. For example: the application makes a zero-copy system call to write a buffer out to a device, file, or network. Instead of making a copy of all the application data from user space to kernel space and then releasing the application buffer, the kernel instead takes ownership of the application buffer, and later asynchronously notifies the application that the I/O is complete. The application can't mess with its own buffer until this notification arrives. It's possible to use both vector I/O and zero-copy I/O to avoid both types of copying (although my test program doesn't do that).

The application using writev instead populates an iovec array with pointers to, and the lengths of, each data field. When the data is ready to be written onto the wire (file, device, or network), the writev system call steps through the array and writes each field one by one in order. (The Linux implementation makes sure this operation is atomic, so a writev running in one process or thread can't intermingle fields with another concurrent writev.)

For our example packet above, the iovec array would look like this.

Vector reads work similarly: the application using readv prepares an iovec array containing empty buffers and their lengths into which data will be read.

That's why this technique is sometimes referred to as scatter/gather: data read serially off the wire is scattered into separate memory locations instead of into a single contiguous buffer; data written to the wire is gathered from separate memory locations and serially written onto the wire.

I wanted to try out the various vector I/O system calls in Linux, so I wrote a little program to do just that. But I didn't want to do anything as prosaic just using iovec arrays. That would be too simple. I decided instead to try out an idea I've had for a long time: using a linked list to pass the data through the various software layers of a simulated protocol stack. And not any linked list, but the doubly-linked diminuto_list_t data structure I implemented in my Diminuto C systems programming library many years ago.

Lists

The Diminuto List implements a doubly-linked list - a linked list in which each node has a pointer to the next item on the list, as with a singly-linked list, and a pointer to the previous item on the list.

(You can find the source code for the Diminuto List implementation on GitHub at diminuto_list.h and diminuto_list.c.)

Singly- and doubly-linked lists are familiar to anyone who has taken Data Structures 101. Doubly-linked lists have an advantage over singly-linked lists in that a node can be removed or inserted anywhere on the list. Diminuto Lists (or just Lists, with a capital L, for brevity) have a few other features besides the next and previous links.

Each node on a List also has a link to the root of the list. This means that given any node on a List, you can find out what List it's on without traversing the List back to the root. So you can do things like trivially prepend or append a new node onto the same List as another node.

Diminuto Lists don't use null pointers, except for the data payload pointer, or as a returned value to indicate a specific condition. Lists are circular doubly-linked lists. The previous pointer on the node at the head of the List points back to the root note; the next pointer on the node at the tail of the List also points back to the root node. You know a node is at the head of the list because its previous pointer and its root pointer are the same. Similarly, a node is at the tail of the list because its next pointer and its root pointer are the same. When you insert a new node onto a List, that node inherits the root pointer from the node after which it was inserted.

Every Diminuto List node has a void * pointer that can point to a data payload. You can use this field by allocating nodes and payloads separately, and have each node point to its corresponding payload, whatever that is. Or you can embed an diminuto_list_t node structure as a field in the payload structure itself, and either ignore the data pointer, or use it to point to the beginning of the payload. You can have multiple node structures in a payload structure, so that the payload can exist on multiple Lists simultaneously; each node's payload pointer can point to the beginning of the containing structure; this eliminates the need to know which node structure you are using in a payload structure in order to compute the address of the beginning of the payload structure.

The root of a Diminuto List is just another node. You know it's the root node because its own root pointer is pointing to itself. Your application may choose to use the payload pointer in the root node for something, or just ignore it.

When a List node is newly initialized it looks like this.

The node's next pointer, its previous pointer, and its root pointer are all pointing to itself. It is in effect the root of an empty List. Whether it remains a root node depends on whether another node is inserted onto it (then it is), or it is inserted onto another List (then it isn't).

As you insert nodes, the next and previous pointers in the inserted node and the adjacent nodes, as well as the root pointer in the inserted node, are all adjusted appropriately. Similar when you remove a node. Because a List is circular, there are no special cases about inserting, removing, appending, or prepending, a node on a List. And you can splice an entire List into another List; the root pointers in the spliced List will all be rerooted to point to the root of the List onto which it is being spliced. You can cut out a sub-List from an existing List, and reroot that new List to a new root node.

If you have a Diminuto List with five nodes plus the sixth root node, it looks like this. (I abbreviated the root node pointers so as to not make the diagram too tangled.)

I don't use Diminuto Lists for everything: the overhead of the four pointers is overkill for applications where one suffices. But they have proven remarkable flexible. So it seemed like a good idea for this experiment.

Gather

The idea here is that different layers in the protocol stack incrementally build a packet by putting the value of each field to be transmitted into a payload buffer associated with a List node, then prepend or append (or even insert or replace) that node onto a List that will eventually represent the entire packet. When the packet is completely built, the application hands off the root node to a function which walks the entire List to build an I/O vector, and then passes the vector to a system call to put on the wire. 

(You can find the source code for this test program on GitHub at unittest-ipc-scattergather.c.)

The highest layer of the stack puts a node whose data payload pointer points to a buffer containing the data to be transmitted. In my test program, these buffers are allocated from a pool (as are the List nodes, from a different pool), and each buffer has a length field at its beginning. The start of the data field of a buffer from the pool is eight-byte aligned, so that its address can be cast to be a pointer of an application variable or structure; that pointer can be used via indirect addressing without copying values. In my test program, the root node is referred to as a record, and the nodes with payload buffers are called segments.

The record is, of course, initially empty. Once the payload segment is put on the record, the record looks like this.

The next layer of the stack prepends a segment at the beginning of the record that contains the length of the data to be transmitted in an eight-byte field. (The length is just taken from the length field in the payload segment's data buffer). It appends a segment to the end of the record that contains a two-byte Fletcher-16 checksum field that it computed from the payload data. The record now looks like this.

The record gets passed to another layer that prepends two segments to the beginning of the record: one containing a four-byte IPv4 address, and another containing two-byte port number.

The record gets passed to a final layer that interrogates the address and port segments of the record to get the destination to which the record is to be sent. It then passes the record along with this information to a function which vectorizes the record: the function just walks the List from front to back, interrogating each segment for a pointer to the beginning of its data buffer and the value in that buffer's length field. It shoves each of these pairs of data into successive positions in the I/O vector. (This is the same figure as seen above.)

It then calls the appropriate system call, writev(2) for streams or sendmsg(2) for datagrams, which puts the resulting serialized packet on the wire. (This is also the same figure as above.)

This completes the gather portion of the I/O. (With the appropriate abstraction and packaging into supporting functions, this was all a lot easier to code than it sounds.)

Scatter

The scatter portion of the I/O is almost the same operation, but done in reverse. But there is a complication: the payload portion of the packet is variable length, so the application has no way of knowing ahead of time what how large a data buffer to assign to the segment the represents that payload field, or what length to put in the I/O vector for the system call.

For datagram sockets, I solved this problem by having four segments, for four fields - address, port, length, and payload - instead of five. The last segment has a data buffer that is large enough to contain the largest possible payload and the two-byte checksum. The datagram receiver in the test program has to extract the checksum from the end of the payload buffer once the length is known. Because, like all good software developers, I'm a little OCD, I added the checksum as another segment which I appended to the record, and adjusted the length field in the payload data buffer by two bytes.

This solution doesn't work for stream sockets, because if there is a second packet behind the one we are receiving, the beginning of that packet would be read into the larger payload buffer past the data of the prior packet. I solved this problem by doing two vector I/O operations: the first reads the address, port, and length; once the length is known, the second reads the payload and the checksum. This solution isn't possible for datagram sockets, since datagrams are transmitted and received as a single unit.

Or you can ditch the entire vector I/O scheme on the receiving end completely. As my test program illustrates, the sender can transmit the packet using vector I/O, but the receiver can receive the packet using any appropriate scheme it wants. My test program implements a variety of ways of doing this for both stream and datagram sockets.

Remarks

I wrote the unittest-ipc-scattergather.c test program as a sort of audition for adding this kind of capability to the mainstream Diminuto library. I'm not convinced that it has broad enough applicability to make that worthwhile. But I rest easier knowing that I have a usable List-vector I/O scheme with a working example in my hip pocket.

Update (2021-03-19)

Today I made the scatter/gather capability a mainstream Diminuto feature. The function and type names have been changed to reflect the canonical Diminuto style. The feature now supports both IPv4 and IPv6 sockets. Additional unit tests have been added. The unit tests are now part of the sanity test suite for Diminuto. All sanity tests pass.

Is the Virtuous Cycle really that virtuous?

In October 2020 I wrote a longish article titled Layers about the layered implementation that emerged organically from the fifteen years (so far) of work I put into my Diminuto systems programming library that is the underlying platform for much of my C-based work. After thinking more about the "virtuous cycle" I described in that article - where feedback from actual use of Diminuto lead to its evolution and expansion and then subsequent use in even more projects (including some shipping products) - I added an afterword. Upon even more reflection, the afterword got longer and longer. Eventually I decided it merited its own short blog article. This is it.

I wonder from time to time whether I'm the only person still working in C. Then I see the TIOBE Index where C is the #1 most used programming language. I find this remarkable, since my years of PDP-11 experience eons ago lead me to still think of C as a kind of structured PDP-11 assembler language.

C places around fifth in other surveys, which seems about right to me. Although I find Rust challenging to work in, I couldn't criticize anyone for using it for systems-level work. And maybe using Go instead of Java for application work. And I like Python too for non-performance-sensitive high level work.

One of the things I find really mysterious is that organizations who work in C, GNU, and Linux don't seem to put any effort into making C easier, simpler, more reliable, and more productive to use. That's exactly what using Diminuto does for me. I'm not trying to talk C shops into using Diminuto. But but I am arguing that they should do something like what I do with Diminuto. And they could do a lot worse than looking carefully at the layered implementation approach I talk about in this article.

I believe this is another case of the cognitive bias towards prioritizing the short term over the long term. Putting code that is likely to be commonly useful in other projects into a reusable library, along with unit tests, is a pattern that has worked very well for me. But in organizations larger than my tiny one-person company, it requires that the folks managing the project and holding the purse strings see the long term value in that. For most project managers there is no long term. And certainly nothing worth spending resources - schedule and budget - outside of their immediate project and silo.

It also requires enough experience to know what is likely to be more generally useful in the long term; I haven't always gotten that right myself. And once you have a library that is used in multiple projects, changes and maintenance on that library requires more diligence and incurs a higher price, since it affects multiple code bases. An API change that breaks legacy code requires careful consideration indeed to balance the cost of breakage against the cost of technical debt.

Line managers and developers are typically not incentivized to think long term. Agile processes do not encourage this either. I find it hard to argue against this. It's easy to get side-tracked and take your eye off of the immediate goal. Long term thinking is the job of senior architects and upper management. And as I like to say: if you don't survive in the short term, there is no long term. It's just that in my tiny corporation, I'm both the line developer and the senior architect. I have to pay attention to the tiny details and the big picture.

Balancing short term and long term needs is a hard problem.