  Modern multi-socket architectures exhibit non-uniform memory access (NUMA)
behavior, where access by a core to data cached locally on a socket is much
faster than access to data cached on a remote socket. Prior work offers several
efficient NUMA-aware locks that exploit this behavior by keeping the lock
ownership on the same socket, thus reducing remote cache misses and
inter-socket communication. Virtually all those locks, however, are
hierarchical in their nature, thus requiring space proportional to the number
of sockets. The increased memory cost renders NUMA-aware locks unsuitable for
systems that are conscious to space requirements of their synchronization
constructs, with the Linux kernel being the chief example.
  In this work, we present a compact NUMA-aware lock that requires only one
word of memory, regardless of the number of sockets in the underlying machine.
The new lock is a variant of an efficient (NUMA-oblivious) MCS lock, and
inherits its performant features, such as local spinning and a single atomic
instruction in the acquisition path. Unlike MCS, the new lock organizes waiting
threads in two queues, one composed of threads running on the same socket as
the current lock holder, and another composed of threads running on a different
socket(s).
  We integrated the new lock in the Linux kernel's qspinlock, one of the major
synchronization constructs in the kernel. Our evaluation using both user-space
and kernel benchmarks shows that the new lock has a single-thread performance
of MCS, but significantly outperforms the latter under contention, achieving a
similar level of performance when compared to other, state-of-the-art
NUMA-aware locks that require substantially more space.
