The Atomic Operations Catalog: Building Thread-Safe Programs Without Locks

When building concurrent programs, the traditional approach involves mutexes and read/write locks to prevent race conditions. However, UNIX-like operating systems offer a rich set of atomic operations that can eliminate much of this complexity. These operations allow the kernel to handle synchronization, reducing CPU overhead and potential bugs in your code.

Pathname Operations: The Foundation of Atomic File Management

Working with pathnames atomically is crucial for reliable file operations, especially when deploying new code or managing shared resources.

The mv -T Command: Atomic Symlink Updates

The mv -T <oldsymlink> <newsymlink> command atomically changes the target of <newsymlink> to point to the directory referenced by <oldsymlink>. This is particularly valuable during code deployments where you need to switch between different versions of your application without downtime.

Both operands must be symlinks for this to work. The operation ultimately calls rename(2), which can atomically replace <newsymlink>. However, be aware that this doesn't work on Mac OS X, where mv(1) doesn't call rename(2).

Link Operations for File Locking

The link(oldpath, newpath) system call creates a new hard link called newpath pointing to the same inode as oldpath, increasing the link count by one. This operation fails with EEXIST if newpath already exists, making it an excellent mechanism for locking files among threads or processes that agree on the newpath name.

I prefer this technique for whole-file locking because the lock is visible to ls(1), making it easier to debug and monitor.

Symbolic Links for Directory Locking

The symlink(oldpath, newpath) operation works similarly to link(2) but creates a symbolic link at a new inode rather than a hard link to the same inode. This is particularly useful because symbolic links can point to directories, which hard links cannot.

This provides the same locking mechanism as link(2) but works for directories too. However, be cautious of "dangling" symbolic links whose target inode has been removed—open(2) will fail with ENOENT in such cases.

Rename for Interprocess Locking

The rename(oldpath, newpath) operation can change a pathname atomically, provided both paths are on the same filesystem. It fails with ENOENT if oldpath doesn't exist, enabling interprocess locking similar to the link(2) technique.

I find this approach more natural when the files in question will be unlinked later, as it provides a cleaner workflow for temporary files.

File Creation with O_EXCL

The open(pathname, O_CREAT | O_EXCL, 0644) operation creates and opens a new file, failing with EEXIST if the pathname already exists. This is useful for deciding which process should handle a task—whoever successfully creates the file gets the job.

Don't forget to set the mode in the third argument (0644 in this example) to ensure proper file permissions.

Directory Creation for Locking

The mkdir(dirname, 0755) operation creates a new directory but fails with EEXIST if dirname already exists. This provides for directories the same mechanism that link(2) and open(2) with O_EXCL provide for files.

File Descriptor Operations: Fine-Grained Control

When you need more granular control over file access, operations on file descriptors provide powerful synchronization mechanisms.

File Locking with fcntl

The fcntl(fd, F_GETLK, &lock), fcntl(fd, F_SETLK, &lock), and fcntl(fd, F_SETLKW, &lock) operations allow cooperating processes to lock regions of a file to serialize their access. The lock parameter is of type struct flock and describes the type of lock and the region being locked.

F_SETLKW is particularly useful as it blocks the calling process until the lock is acquired, providing a simple way to implement blocking locks without complex synchronization primitives.

Note that there is a "mandatory locking" mode, but Linux's implementation is unreliable due to a race condition, so advisory locking is generally preferred.

Lease-Based Notifications

The fcntl(fd, F_GETLEASE) and fcntl(fd, F_SETLEASE, lease) operations ask the kernel to notify the calling process with SIGIO when another process opens or truncates the file referred to by fd. When that signal arrives, the lease needs to be removed by calling fcntl(fd, F_SETLEASE, F_UNLCK).

fcntl(fd, F_NOTIFY, arg) is similar but doesn't block other processes, so it isn't useful for synchronization—it's better suited for monitoring file changes.

Memory-Mapped File Sharing

The mmap(0, length, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0) operation returns a pointer from which a file's contents can be read and written by normal memory operations. By making frequent use of msync(addr, length, MS_INVALIDATE), data written in this manner can be shared between processes that both map the same file.

This provides an efficient way to share data between processes without explicit copying or complex synchronization mechanisms.

Virtual Memory Operations: Lock-Free Algorithms

For the most demanding synchronization scenarios, virtual memory operations provide the building blocks for lock-free algorithms.

GCC Atomic Builtins

The __sync_fetch_and_add, __sync_add_and_fetch, __sync_val_compare_and_swap, and related operations provide a full memory barrier, ensuring "no memory operand will be moved across the operation, either forward or backward." These operations are the basis for most (if not all) lock-free algorithms.

These builtins are essential for implementing high-performance concurrent data structures and algorithms that avoid the overhead and potential deadlocks of traditional locking mechanisms.

Practical Considerations and Caveats

While these atomic operations are powerful tools, there are several important considerations to keep in mind:

Filesystem Dependencies: Many of these operations work best on local filesystems. Using them on NFS mounts can lead to unexpected behavior because multiple kernels are involved, and the kernel can't handle all the locking for you.

Resource Limits: Inodes are a finite resource—this particular machine has 1,245,184 inodes. Be mindful of inode usage, especially when creating many temporary files or symbolic links.

Platform Differences: Some operations behave differently across platforms. For example, the mv -T command doesn't work as expected on Mac OS X because its mv(1) doesn't call rename(2).

Race Conditions: Even with atomic operations, race conditions can still occur if you're not careful. Always consider the entire sequence of operations and whether intermediate states could cause problems.

The Philosophy: Let the Kernel Do the Work

The underlying philosophy here is to let the kernel handle as much work as possible. At my most pessimistic, I trust kernel developers more than I trust myself. More practically, it's stupid to spend CPU time locking around an operation that's already atomic.

By leveraging these atomic operations, you can build thread-safe and multi-process-safe programs without the complexity of mutexes or read/write locks, resulting in simpler, more reliable, and often more performant code.

Have you discovered other atomic operations or have suggestions for improving this catalog? The author welcomes feedback at [email protected] or @rcrowley on Twitter.