Thursday, April 19, 2018

Frames of Reference II

I'm taking an weekly adult education class at University of Denver on the science and nature of time. Me, an adult, if you can imagine it, but perhaps not so surprising a topic for a guy that has his own cesium atomic clock and several Swiss mechanical wristwatches. The instructor, a semi-retired astronomer that worked on the Hubble space telescope, had us do an interesting experiment the other evening.

Take off your shoe and mindfully touch your big toe with your index finger. The sensations you experience are traveling along three different paths:
  1. the light reaches your eyes, then the visual cue travels a very short distance to your brain through your nervous system;
  2. the sensation of your finger touching your toe travels through your nervous system, up your arm to your spinal cord, then a short distance to your brain;
  3. the sensation of your toe touching your finger travels a relatively long distance up your leg, up your spinal cord, to your brain.
Did you perceive any difference in those three sensations? Most people say they sense them simultaneously.

Here's the thing: there is about a 80 millisecond difference in delay between the latency from your eyes and the latency from your toe, with your finger falling in between. 80ms is nearly a tenth of a second. That's easily perceptible by the human brain; we recognize 1/10s delay routinely when listening to music. I own a mechanical watch - a vintage Eterna-Matic 36000 - that audibly ticks at 10Hz or 10 times a second.

Eterna Matic 36000 Fast Beat ca. 1968

But this difference in latency isn't apparent when we do this little experiment. Why not? There are some shenanigans going on in our brain regarding the processing of those sensations and it affects our perception of time.

Googling for this topic reveals all sorts of interesting research, the most common result being "hearing is faster than seeing", in part because of the processing involved. A lot of the research is done to determine how fast is fast enough to seem "instantaneous" and is motivated by response time studies. In the more recent decades, the computer gaming industry has been doing this kind of research.

But I was struck at the eerie similarities between this vagary of human perception and the how design and implementation decisions could affect latencies and therefore the ordering of events in real-time systems that I wrote about in this blog in Frames of Reference just a month earlier.

Wednesday, April 18, 2018


I just recently discovered that Linux kernels from about version 3.15 or so implement a system call called renameat2. (That's pronounced "rename at 2" not "rena meat 2" BTW.) This is a useful thing to know, because a close reading of the renameat2(2) manual page reveals it eliminates two related thorny problems that I haven't found any other way to solve.

I also discovered that despite what the output of the man renameat2 command might imply about the C function prototype, recent versions of the glibc library, at least the one on my Ubuntu 16.04 "xenial" development system, don't provide a function wrapper for the system call. Fortunately, it turns out that you can easily roll your own, something I have never had to do before.

Here is the implementation of the equivalent C function.

(N.B. In these code snippets I've eliminated all the error checking for clarity. In my production code, I am avidly paranoid about checking all error returns. I encourage you to do the same. All of these code snippets are from actual running examples. Since Blogger seems incapable of consistently displaying my code snippets correctly across all browsers - they all look correct in the Blogger editor - these snippets can be found on GitHub.)

#include <stdio.h>
#include <fcntl.h>
#define _GNU_SOURCE
#include <unistd.h>
#include <sys/syscall.h>

int renameat2(int olddirfd, const char * oldpath, int newdirfd, const char * newpath, unsigned int flags) {
 return syscall(SYS_renameat2, olddirfd, oldpath, newdirfd, newpath, flags);

A careful application of the strace command on some unit tests reveals nothing but goodness in the result.

Problem One

Accidents happen. Mistakes are made. No matter how carefully you write your boot-time start-up scripts, or your interactive restart scripts, for system daemons, sooner or later your product is going to try to start the same daemon twice. This will happen in the development lab, or during quality assurance testing, if no where else. Wackiness may ensue.

A common idiom used to prevent this is for a daemon to initially create a lock file with a unique name like /run/lock/mydaemonname.lck in such a way that if the file already exists, the file creation fails, and the daemon exits assuming that prior version of itself is already running. This lock file is deleted when the daemon exits, and the entire /run/lock directory is cleaned up when the system reboots.

Ensuring that the lock file does not already exist can be easily done by using the combination of the O_CREAT | O_EXCL | O_WRONLY flags on on the open(2) system call; the system call will fail if the file already exists, and the check for it existing, and the subsequent creation of the file, is atomic. There is no way another process running concurrently on the system can see an intermediate result. The Linux kernel and its file system implementation guarantees that the file either exists, or it doesn't exist; there is no possible race condition.

This pattern gets ugly when the daemon wants to implement another commonly used idiom: writing its own process identifier, typically as text, into the lock file. This is really useful, because it allows other applications to verify that the daemon that created the lock file is still running, and to subsequently communicate with it, for example by sending it a signal. The ugliness happens because if the daemon atomically creates the file using open(2), then writes its PID into the file, applications can easily see an intermediate state: an empty lock file, or worse, a lock file with only a partially written PID that may look legitimate, because writing the PID to the lock file isn't necessarily atomic.

What the daemon would like to do is create a unique temporary file, perhaps using mkstemp(3), write its PID into that file, then atomically rename(2) the temporary file to the name of the lock file using the same exclusivity semantics as provided by open(2). We want the lock file to have exactly two visible states:
  • the lock file does not exist;
  • the lock file exists and contains a valid process identifier.
Unfortunately, while the rename(2) system call can be atomic, providing the source and destination files are in the same file system (so that no copying needs to be done),  it does not provide the same optional exclusivity flags as open(2). But that's exactly what renameat2(2) provides with its RENAME_NOREPLACE flag. And even better, renameat2(2) also checks that the source and destination file names are in the same file system, keeping you from shooting yourself in the foot.

Here is the implementation of the lock function.

int my_lock(const char * file)
    static const char SUFFIX[] = "-lock-XXXXXX";
    pid_t pid = getpid();
    char * path = (char *)malloc(strlen(file) + sizeof(SUFFIX));
    strcpy(path, file);
    strcat(path, SUFFIX);
    int fd = mkstemp(path);
    FILE * fp = fdopen(fd, "w");
    fprintf(fp, "%d\n", pid);
    int rc = renameat2(AT_FDCWD, path, AT_FDCWD, file, RENAME_NOREPLACE);
    if (rc < 0) { unlink(path); }
    return rc;

Problem Two

Another common idiom is for a parent process to atomically create an empty lock file, fork(2) off a child process, the child process daemonifies itself, then it writes its PID into the lock file. In this approach, the lock file has three states instead of two:
  • the lock file does not exist,
  • the lock file exists but is empty,
  • the lock file exists and contains a valid PID.
We want the lock file creation to be atomic as before, and we want the transition from empty to containing a PID to be atomic as well, with no intermediate states visible. The parent can wait for some time out period, then check the lock file for the PID. This not only gives the parent a PID through which it and other applications can signal the child, but also informs the parent that the child has started successfully.

The initial atomic creation of the lock file can be done as described previously using open(2) with the appropriate flags. As a subsequent step, the child process creates a temporary file containing its PID, and, providing the temporary file and the lock file are in the same file system, renameat2(2) can be used with its RENAME_EXCHANGE flag to atomically swap the temporary file and the lock file. renameat2(2) does all the heavy lifting for us by not only atomically swapping the two files, but also by guaranteeing that the two files are in the same file system, and insuring that the lock file already exists.

Here is the implementation of the pre-lock function called by the parent process that atomically exclusively creates the lock file, and the post-lock function called by the child that populates the lock file with the child's PID. (The implementation of the functions to delete the lock file, and to read the PID from the lock file, are left as an exercise for the reader.)

int my_prelock(const char * file)
    int fd = open(file, O_CREAT | O_EXCL | O_WRONLY, 0600);
    if (fd < 0) { return -1; }
    return 0;

int my_postlock(const char * file)
    static const char SUFFIX[] = "-post-XXXXXX";
    pid_t pid = getpid();
    char * path = (char *)malloc(strlen(file) + sizeof(SUFFIX));
    strcpy(path, file);
    strcat(path, SUFFIX);
    int fd = mkstemp(path);
    FILE * fp = fdopen(fd, "w");
    fprintf(fp, "%d\n", pid);
    int rc = renameat2(AT_FDCWD, path, AT_FDCWD, file, RENAME_EXCHANGE);
    return rc;

Note that once the swap is successful, the post-lock function deletes the temporary file, which will now be empty.


I recently worked on a embedded product development project in which the underlying Linux distribution chosen by the team supported systemd(1), the system and service manager. systemd replaces the bulk of the boot-time init infrastructure, daemon start-up scripts, and even the cron daemon. As you might imagine, its introduction is somewhat controversial in the Linux mainstream, especially given that the traditional UNIX architectural philosophy is to resist centralized management.

But I - who have been doing embedded Linux development since the Linux 2.4 kernel - was a little surprised to find I liked systemd. If your projects supports systemd, you will find that it provides other mechanisms to manage the daemons you might be called upon to write. You should use those mechanisms.

My computer scientist friends will have appreciated that the renameat2 system call implements a kind of semaphore or mutex, or at least a kind of atomic swap that can be used to implement such capabilities, in the file system. That means there are probably lots of other things it can be used for.

Linux (and other UNIX variants) provide other synchronization and mutual-exclusion mechanisms through which something like this could be implemented. But this approach just uses the file system. It requires only a small amount of cooperation between the applications that make use of it. It's simple and straight forward.

Important Safety Tips

renameat2(2) requires support from the underlying file system. Not all file systems may implement it. Some, especially network file systems, may never be able to implement it, because of their semantics.

At least on Ubuntu 16.04 "xenial", the synthetic processor implemented by valgrind(1) doesn't provide the renameat2 system call. This means you can't test applications using that call for memory leaks. This makes me nervous.

Final Remarks

I like renameat2(2) because I haven't found any other way to reliably and simply implement what it provides. In fact, renameat2(2) is so uniquely useful, I suspect that systemd(1) uses the renameat2 system call under the hood to perform its own service management. (Update: I just checked the systemd repository on GitHub and this is indeed the case.)

I came to use renameat2(2) in the implementation of the diminuto_lock.c feature, and in the renametool utility, in my Diminuto C-based systems programming library. Diminuto is a collection of useful C functions and utilities I have written that has found its way into a number of shipping products, not to mention in many of my internal projects.

Tuesday, April 10, 2018

Follow by Email

My old friend, occasional colleague, and one time flat mate Paul Moorman suggested I add the Follow by Email gadget to my blog. I have done so. Entering your email address on the form near the bottom of the web version of this blog subscribes you to a Feedburner feed. When I post a new article you'll get an email notification. No update, no email. You can, of course, also follow this blog via your favorite RSS reader; I'm using Feedly these days. Finally, I finally activated the option to redirect all links to this blog to a secure HTTPS connection, something I should have done long ago. Thanks, Paul!

Wednesday, March 14, 2018

Frames of Reference

Lightning strikes the houses at either end of your street. As your neighbor at one end relates it, lightning struck his end of the street first, then the other end. Your other neighbor who lives at the other end says just the opposite: lightning struck his end first, then the other end. You live in the middle, and you saw it strike both ends simultaneously. Who's right?

You all are. That's what Einstein was getting at in the Special Theory of Relativity: when all observers are at rest with respect to the world around them, there is no preferred frame of reference. None of you are more correct than the other. Under no circumstances can information travel faster than the speed of light. So our perception of the order of events that occur in the world around us depends upon our position within the world and the speed at which we are traveling. There is no right answer. Or at least, none that is any more right than another.

As anthro-astronomer Anthony Aveni points out in his book Empires of Time [University Press of Colorado, 2002], on timekeeping across cultures and throughout history, even if you were unfortunate enough to have your eyeball pressed right up against the place on the roof where the bolt of lightning struck, there is still a non-zero latency for the light to reach your eyeball, to be converted into nerve impulses, for those impulses to travel to your brain, for them to be interpreted by your conscious mind, and for your mind to order you mouth to say "HOLY CRAP!" Any sense of simultaneity is completely subjective.

And so it is with the real-time systems we build. I've worked on all sorts of stuff over my long career: ATM-based optical networking for internationally distributed telecommunication systems; GSM and CDMA cellular base stations; Iridium satellite communication systems for business aircraft; Zigbee wireless sensor networks; RS-485 connected industrial lighting control systems, to name just a few. Plus a lot of the more typical Ethernet, WiFi, and LTE communications systems designed to tie together a variety of computers. These systems all suffer from the same lack of preferred reference frames that we do.

Each of these systems can be thought of as state machines that receive stimuli from many different sources and through many different channels. Vastly complex state machines for sure. But ultimately we can consider of their entire memory as one gigantic number - a Gödel number - perhaps billions of bits in length, each unique value encoding a specific state. Each real-time stimulus causes this enormous number to change, transitioning the state machine to a new state. Because there is a finite amount of memory in the system, there is a finite (albeit really really big) number of unique states that the system can assume.

The stimuli to this state machine may arrive via a variety of mechanisms. Network messages from other nodes might arrive via Ethernet, WiFi, and cellular networks. Sensor values might be read via various hardware schemes like SPI, I2C, GPIO, ADC, UART, each of which has its own bandwidth, and more importantly, latency. The hardware latency for each of these technologies varies widely. Some, like the analog/digital convertor, have hardware latency quite long relative to other devices. Plus all the software processing latency on top of it for whatever protocol stack is used.

In addition to all of these stimuli that are the results of events occurring in the outside world, stimuli generated internally are arriving all the time as well. Peruse any network standard and you'll find a slew of timers defined, that are set when certain conditions are met, cancelled if others are met, and when they fire, they inject their own stimuli into the state machine.

Once received, each stimulus has to be serialized - placed in some discrete order of events relative to all of the other stimuli - to be injected into the state machine so that the system acts deterministically.

If two companies develop competing products to solve the same problem, they will likely make different hardware design choices and write different software. Their products will implement different hardware and software paths, even if they use the same networks and sensors. The real-time stimuli that gets injected into their state machines will, at least occasionally, be serialized in a different order. Their systems will transition to different states. Because of that, they may make different decisions, based their own unique but different perception of reality. Which system is right?

Maybe they are all right. Even when the system responds in a way we think is incorrect, we may still be basing that assessment on our own perception of what happened in the real-world, which may or may not be any more or less correct than what the hardware and software system perceived. We may believe that our own reference frame is the preferred one, but both we and our cyber counterparts are subject to the same laws of Special Relativity as applied to biological and silicon systems.

I think about this a lot when I read articles on driverless vehicles. Vehicle automation doesn't have to be perfect. It just has to be better than the human behind the wheel. Or the joy stick. That may be a low bar to hurdle. There are still likely to be cases where the vehicle automation system makes a decision different from the one we would have made ourselves. That doesn't make it wrong. But it might be hard to understand why it did what it did without a lot of forensic log analysis.

My own Subaru WRX has an EyeSight automation system that includes features like collision avoidance, lane assist, and adaptive cruise control. EyeSight gets concerned when I drive through the car wash. It sometimes loses track of the road completely in heavy rain or snow. But for the most part, it works remarkably well. I don't depend on it.

Just this past weekend, Mrs. Overclock and I celebrated our thirty-fourth wedding anniversary in Las Vegas, a short plane ride from our home near Denver. We witnessed the eight-passenger driverless shuttle, part of a pilot program, cruising around the downtown area near Fremont Street. We saw it hesitate while pulling away from a stop because of oncoming traffic. Its full load of passengers weren't screaming in terror.

We also saw an empty and unmanned Las Vegas monorail train blow through a station where we were waiting to the sound of a very loud bang and a big shower of sparks. This resulted in someone with a walkie talkie walking the track, and eventually an announcement of a service disruption with no estimated time of repair. On the cab ride - plan B - we noticed another train stuck at a earlier station waiting for service to resume.

The Denver-area light/commuter rail was due to be extended to our neighborhood nearly a year and a half ago. The rail line is complete, and all the stations ready with their brightly lit platforms and scrolling electronic signs. But the developers can't get the positive train control to work as required by federal regulations; the automated crossing gates apparently stay down about twenty seconds too long. Sounds minor, but this defect - which has to be a lot more complex than it sounds or it would have been solved long ago - has cost millions of dollars, not to mention keeping Mrs. Overclock and me from taking the train from the station at the end of this line, which is within walking distance from our suburban home, to downtown Denver for the theatre and concerts we regularly attend, or even to the Denver International Airport by changing lines downtown.

Do any of these automated systems suffer from a disparity in reference frames with their users? Dunno. But in the future when I work on product development projects with a lot of real-time components (which for me, is pretty much all of them), I'm going to be pondering even more the implications of our hardware and software design decisions, how they impact how the system responds to events in our real-world, and how I'm going to troubleshoot the system when it inevitably makes a decision that its user finds inexplicable.

Wednesday, January 10, 2018

Windows Update on Windows 7 after December 3rd 2017

Tried to run Windows Update on a Windows 7 system after December 3rd and got an error message that it can't check for updates because the service isn't running? Yep, me too. If you search for this, you'll find we're not alone; probably millions of folks got caught by a botched timestamp buried in a file on a compressed archive deep in the Windows file system.

What the web suggests and what worked for me: set your system clock back to before the expiration date (I used December 1st), run Windows Update (it downloads updates that include a fix for this), let it restart your system, then maybe try running it again (because more updates showed up for me and I had to restart again), and then you can change the date back to today. Windows Update works afterwards.

Why Windows 7? Some proprietary embedded tools I must use from time to time - mostly for talking to hardware devices - haven't made the jump yet to Windows 10, or even Windows 8. Also, it doesn't suck.