2018-09-22

Gigabit Ethernet Everywhere

What's the purpose ?

Every developer even remotely interested in performance regularly needs multiple physical machines to test the effects of various optimizations. I'm no exception to this, on my desk lie a number of fanless Atom and ARM boards serving as load generators and web servers when I need to validate certain points regarding HAProxy.

The problem is that you don't always have enough network connectivity on the wall. A simple solution consists in buying some external 5-port switches but at some places you then don't have enough power plugs, and having to deal with extra cables and devices at all time for a test once in a while is not always cool.

Additionally when you have to visit customers for some consulting it's commonly problematic not to be able to plug anywhere or directly behind a test machine.

Nowadays there are interesting solutions like this very inexpensive 5 port Gigabit Ethernet switch which I paid less than $13 shipping included. But this one also requires an external power supply.

Very simple solution

One will note that the description mentions a 5V power supply. Thus it can very likely be powered over USB. I bought one and used a USB cable adapter to verify that it worked fine once connected to USB. And indeed, it did.

Thus I opened it, de-soldered the power plug, replaced it with a micro-USB female connector, and that was all. Now I can carry this device in my computer bag every day and if I need to connect it, I can pick whatever micro-USB cable available and connect it to my PC or any other power source.

It would be nice if such low-power switches would ship with micro-USB by default. They would cost even less to produce, and would not need to be shipped with a power adapter.

The modification steps are shown below :

1) open the device by removing the top cover and extract the PCB :

2) desolder the jack plug :


3) prepare a micro-USB connector. This one comes already soldered on a board, I just had to re-cut the PCB a little bit to adapt it to the format of the original jack plug :


4) solder the micro-USB PCB, place a piece of foam on top of it to plug the hole, and put the top cover back. You're done :


That's something very easy to do, which saves you from having to carry an adapter or even a special cable everywhere. I wish the manufacturer will think about it for future versions.

Other thoughts

It's visible on the top right that there's room for an eeprom containing the switch config. The config format is documented in the switch's datasheet. This device is based on a Mediatek MT7530DU. I didn't go into details yet but very commonly this allows to enable VLANs and maybe even port mirroring. For some use cases it can be useful to have a tagged port communicating with each other port via a distinct VLAN. This allows for instance to very easily extend a laptop's interface to 4 ports for routing, firewalling or load-balancing tests. If the device supports port mirroring, it could be even better, supporting being inserted on existing cables and capture the traffic for network troubleshooting purposes.

2018-02-25

USB-based watchdog for ATX power supply

Introduction

Sometimes when developing on low-level stuff like a kernel, you face situations which completely freeze your system. While it's not that much of a problem on a development board, it's more annoying when it happens on a regular PC and you have to move off your chair to power cycle the beast, or worse, wait till you're home when developing remotely.

Usually this doesn't happen because your hardware is supposed to come with a hardware watchdog timer that will reboot the board if hung. But some boards don't have one, or sometimes it doesn't work well or you simply don't have the driver on your experimental kernel.

This article explains how it is possible to implement a watchdog for an ATX power supply, that is controlled over USB. It supports both being controlled by the target device itself (like any regular watchdog timer), or by another machine which will be able to power cycle the tested one.

Background

First, it seems useful to remind how a watchdog timer works. It is a hardware counter that counts down from a configured value, and which triggers the system's reset once the counter reaches zero. The main system periodically refreshes this counter so that as long as the system runs, the counter cannot reach zero (e.g. it sets it to 10 seconds every second). If the system hangs, it stops refreshing the timer and once the period is over, the reset line is triggered and the system reboots.

Second, it happens that some embedded boards do not easily expose certain connectors like the reset pin. At this point it becomes a bit harder to implement a hardware watchdog timer. But there is a solution : ATX power supplies are expected to drive the PWR_OK signal up once the voltage is correct, and drive it down when it's out of specs. More precisely, they connect it to a pull-up resistor, and actively drive it down when the voltage is not within specs. The motherboard is supposed to watch this signal and hold its reset line until this signal is up. This is very convenient because it means we can connect to this signal without even cutting any wire, and drive it low to force the board to reset itself.

So we have our reset input :-)

Locating the PWR_OK signal

This signal is on the grey wire connected to ping 8 of the ATX connector (either 20 or 24 pin) as shown below. In case of doubt, please use your favorite search engine to look for ATX pinout. But be careful, the pinout is often shown from the pin side (front view) and not from the wire side (rear view) :

Controlling the signal

We will need a timer and one solution to communicate with the host and/or with another host. Initially I thought about using a serial port but they are not always available nowadays. Then I thought about using the PS/2 connector and periodically sending commands via the keyboard controller, but some boards do not have such connector. Nowadays almost all boards do have plenty of USB ports however. So it looks like implementing a USB slave device is a good idea, which will make it easy to unplug and connect to another machine if desired.

The difficulty with USB is to find a suitable chip. But not only this is no longer a problem thanks to the V-USB stack but it ends up possibly be the cheapest solution one can think of. This stack is available for very affordable micro-controllers like Atmel (now Microchip)'s ATTiny85. which can be purchased already soldered on a board with all required external components for around $1.50 to $2.00 depending on the board and form factor. Models sold as "Digistump Digispark", "Adafruit Trinket" as well as various so called "ATTINY85 development/programmer board" equipped with a micro-USB connector are all suitable. Two such devices have been successfully used to date :


One point to keep in mind is that the PWR_OK pin can be very sensitive on the motherboard. The ATX specification says that a power supply is required to drain at least 200 µA (i.e. 5V through a 25k resistor), and a motherboard must consider any voltage lower than 2.4V as low. This means that simply connecting a 10k resistor between this signal and the ground may be enough to drive it low with some power supplies. As long as the module is always connected, it's not a problem. But if the module is to be left disconnected, hanging out of the machine, then it will drain the signal through the power lines and will drive it low, preventing the machine from powering up. One pin on the ATTiny85 doesn't cause this : PB5. It's shared with the RESET signal and supports a high voltage, so it doesn't contain any pull-up nor clamp diode. The tests confirmed that indeed, when the module is not connected, only this pin doesn't prevent the board from powering up.

There are 3 solutions to this problem :
  1. use the PB5 pin as the output to control PWR_OK. I'm not happy with doing this as it won't be possible to reprogram the device anymore without providing a high voltage to the chip.
  2. permanently connect the +5V to the device by connecting it to the power supply's +5V line. I'm not fond of this method either, as taking the +5V outside of a machine isn't always safe if there aren't efficient protections (e.g. wires getting accidently pulled off could easily burn if shorted). On some boards this may also require disconnecting the +5V from the micro-USB connector to avoid leaking the current into the USB host.
  3. adding a transistor to only let the current flow when the board is powered. This sounds like the best solution, an only requires one external component.
The boards above all include a LED connected to PB1. We'll use it to indicate when the PWR_OK signal is asserted by the module and to help debugging. It's always convenient to be able to test a driver without having to power down the machine to confirm it works! On such boards, PB3 and PB4 are used for the USB connection. PB5 is shared with the RESET, which only leaves PB0 and PB2 available. Thus we'll use PB0 here to control the PWR_OK signal.

Additionally, in order to protect the device against cheap power supplies which would directly connect PWR_OK to the +5V output, we'll put a series resistor to protect the transistor and the micro-controller against a short-circuit. The micro-controller is supposed to be able to drain and sink 40 mA per output pin. By using 180 ohm, we'll limit the output current to 27 mA in the worst case (just enough to lit a LED), which allows to safely control a wide range of power supplies.

Circuit design

The circuit is pretty simple. A BS170 MOSFET is connected between +5V and PB0, so that the output is only connected when PB0 is low. This MOSFET contains a reverse diode, which allows us to also monitor the output and report it to the USB host. The MOSFET may be replaced with an NPN transistor like a 2N3904 or a BC547, a resistor, and a diode if the voltage monitoring function is desired. Both solutions have been built, tested, and confirmed to work :



The code takes care of disabling the output and the pull-up when the output is not asserted, so that no current even flows through the diode. The finalized boards look like this (before putting them into transparent heat shrink tube) :




Communicating with the chip

The V-USB mentionned above provides USB connectivity. This is fine for HID devices, but these devices require a driver on the host (well, it's not totally exact as they can send keyboard keystrokes but there's no trivial way to send data without a driver or an application). Another solution consists in emulating a modem using the CDC ACM mode. This is exactly what the AVR-CDC code does. It's important however to keep in mind that CDC ACM over a low-speed device is out of spec but general operating systems tend to support it, which is what we're exploiting here.

The AVR-CDC code comes with an example application consisting in a USB-to-RS232 interface realized entirely in software. It's a good starting point for what we need, so the RS232 code was removed and the USB code was modified to instead simply manage a watchdog. The modified code is available here with the pre-compiled firmware in hex format.

The protocol is very simple : the device presents itself as a serial port on the host, and receives some short commands. The following commands are supported :
  • '0'       : disables the watchdog
  • '1'..'8'  : schedules a reset after 2^N-1 seconds (1..255)
  • 'OFF'     : power off
  • 'ON'      : power on
  • 'RST'     : triggers a reset immediately
  • 'L0'/'L1' : turns the LED off/on (to test communication without resetting)
  • '?'       : retrieves current state on 2 bytes. First byte indicates the level of the pin, which is set as an input when not off, allowing to check a power supply's status. '0' indicates it's off (or forced off), '1' indicates it's on (or disconnected). The second byte indicates the remaining amount of seconds before reset.
All unknown characters reset the parser, so CR, LF, spaces etc will not cause any trouble.

All commands which manipulate the timer or the output ('0'..'8', 'ON', 'OFF', 'RST') automatically disable any pending timer. The device takes a great care not to influence the output during boot, and doesn't automatically start. This way it's possible to leave it connected inside a machine and to turn it on by software. It may also be used as a self-reset function by writing 'RST' to the device.

Testing the module

The tests were conducted on an ATX motherboard with an ATX power supply. The module was connected to a netbook PC. The module was forced off and on, then it was verified that the device didn't reset as long as the timer kept being refreshed, and then that stopping the loop (Ctrl-C) was enough to cause the board to restart. The status and the timer were also read before, during and after a reset :


The whole test setup :


The motherboard tested here (Asus P5E3 WS Pro) seems to only sample the PWR_OK signal on the falling edge for a short time, and decides to start anyway after a few seconds. It will prevent from controlling the power from outside. It's not dramatic, it still allows to remotely reset the board, which is the most important.

It is likely that some users may want to enable the timer at boot time. It's easy to do in the code anyway. A change could consist in checking pin PB2 to decide whether or not to automatically start the timer at boot. A variation could consist in replacing the output resistor with a relay connected to +5V or +12V, inserted between the mains and the power supply, or between an external power block's output and the board to control. The system is simple and versatile enough for many variations, possibly not even requiring any code update.

For motherboards featuring an internal USB connector, the Digispark board may be the best, as it includes the USB male connector, so it can directly be plugged into the internal connector without any cable. For internal connections, only the PWR_OK wire is needed.

For remote control, it's preferable to place the module outside of the machine with only the two long wires connected to the ATX power connector. These ones do not represent any particular risk. In case of shortage or connection to the ground, the board will simply be forced off.

Some tests should be conducted to determine whether or not it would make more sense to drive the PS_ON# signal instead. This one is driven low by the board to turn the power supply on. The problem is that some boards wire it to the ground to keep it constantly low. However it would be possible to implement the inverted signal on pin PB2 and decide depending on the motherboard whether to use PWR_OK or PS_ON#.

Downloads and links

2018-02-16

Progressive Locks : fast, upgradable read/write locks


Context

A few years after I created the Elastic Binary Trees (ebtree), I started to get some feedback from users who needed to use them in multi-threaded environments, asking if an MT-safe version was available. By then, nothing was available, and all I could suggest them was to place some locks around all the tree manipulation code. While this generally works well, it was sub-optimal because these trees feature some really nice properties that are partially impaired if surrounded by frequent, heavy locks. Thus it required some extra thinking, leading to a first minimal solution emerging in 2012 and having improved since.

Common use cases

It looks like the most common use cases of ebtrees are :
  • data caches (like the LRU cache example from ebtree that ended up in HAProxy as well)
  • log parsing / analysis (i.e.: count number of occurrences of a number of criteria and their relation with other criteria)
  • data conversion (like in HAProxy's maps, mostly used for IP-based Geolocation)
These use cases share a few important properties :
  • the trees are mostly read from, and seldom updated (typically less than 2-3% updates)
  • these operations are performed as a very small part of something more complex, and often a single high-level operation will require multiple tree accesses. Thus these operations need to remain extremely fast.
  • the workloads involving these operations tend to be heavy and to benefit from multi-threading
At first glance, some R/W locks would perfectly fit this purpose. But R/W locks tend to be slow because they involve two atomic operations when taking the lock for reading and when dropping it. This means performing 4 atomic operations per tree lookup. This can end up being slower than the tree lookup itself in certain cases. Often taking the lock for writing is faster but that's the case we're the least interested in here. And I got the confirmation by some users that due to low concurrency on their tree, they preferred to use a faster spinlock around the tree operations, even if that implied not doing any parallelism at all.

For other users requiring parallelism and some insertions (caches, log processing), R/W locks limit the scalability to the ratio of time spent writing vs the time spent doing something else not requiring access to the tree. Indeed, the write lock being exclusive, each time there is a write operation, the tree is not usable and all readers have to wait.

Observing how the time is spent in ebtrees

Ebtrees present an average lookup and insertion time of O(log(N)) where N is the number of entries in the tree. In practice this is not totally exact for small trees, because an ebtree is a modified radix tree, so the number of visited nodes during a lookup or an insertion in fact corresponds to the number of common prefixes along the chain to the requested node, which can be as high as the number of bits in the data element. The tree descent is done by comparing some bit fields with the data found at each location and deciding to go left or right based on this. The final operation (returning the data found, or inserting/deleting a node) is very fast as it's only a matter of manipulating 4 pointers in the worst case. The sequence below shows how a node "3" would be added to a tree already containing nodes 1, 2, 4, and 5 :

   

On a core i7-6700K running at 4.4 GHz, a lookup in a tree containing 1 million nodes over a depth of 20 levels takes 40 ns when all the traversed nodes are hot in the L1 cache, and up to 600 ns when looking up non-existing random values causing mostly cache misses. This fixes a limit to 1.67 million lookups per second in the worst case (e.g. cache being intentionally attacked).

This ratio is interesting because it shows that for some use cases, a thread would possibly want to benefit from the fast lookup of common keys (e.g. 40ns to look up the source IP address of a packet belonging to a recent communication), without being too much disturbed by another thread having to insert some random values locking the tree for 600 ns.

For a workload consisting in 1% writes in the worst case conditions above, a single core would spend 87% of its time in reads, and 13% in writes, for a total of 22 million lookups per second. This means that even if all reads could be parallelized on an infinite number of cores, the maximum performance that could be achieved would be around 160 million lookups per second, or less than 8 times the capacity of a single core.

Below is a graphical representation of how the time would be spent between fast reads and slow writes on this worst-case workload, on a single core machine, then on a 8-core machine, showing that the 8-core machine would be only 4 times faster than the single-core one, spending 48% of its total CPU resources waiting while the write lock is held. The 100 operations are performed every 1095 ns, bringing 91 million operations per second.


Note that this problem is not specific to trees in fact. It also affects other structures such as hash tables, to certain extents. Hash tables are made of linked lists attached to an array of list heads. Most of the time, elements are not ordered, so additions are performed to the head (or tail) of the list and it is possible to lock a list head (or the whole hash table depending on requirements) during a simple insertion. But there is a special case which concerns uniqueness : if you want to insert an element and ensure it is unique (like a cache usually does), you need to atomically look it up then insert the new one, and the same problem happens, except that this time the worst lookup time can be O(N) :


Designing a solution

Since most of the time is spent looking up a position in the storage structure (tree, list, etc), and this lookup by itself doesn't result in modifying the structure, it seems pointless to prevent other readers from accessing the structure. In an ideal case, we would like to have the ability to "upgrade" the lock from Read to Write only after the lookup. This cannot be done without some constraints since if it were universally possible, it would mean that all readers could be upgraded to writer some of which would be stuck at certain positions while a writer is currently modifying these same locations.

But most of the time we know that we're performing a lookup planning for a write operation. So we could have an intermediary lock state that does not exclude readers, and which at the same time is guaranteed to be atomically upgradable to a write lock once all readers are gone.

This is exactly what the initial design of the Progressive Locks (plock) does. The new intermediary lock state is called "S" for "seek" as it is only used while seeking over the storage area and without performing any modification. Just like for W locks, a single S lock may be held at a time, but while the W and R locks are exclusive, the S and R locks are compatible.

In the worst case above, is we consider that among the 600ns it takes to insert a key into the tree, 595ns are used for the lookup and 5ns are used to update the pointers, it becomes obvious that the whole tree is locked only for 5ns every 600ns, so 595ns out of the 600ns are usable for read operations that happen in parallel. Thus the sequence becomes the following one :
  1. a slow writer starts to seek through the whole tree using the S lock, taking 595ns
  2. in parallel, other threads continue their read operations. During the same time frame, each thread may initiate 15 read operations of 40ns
  3. once the writer finds the location where it wants to insert its new node, it upgrades its S lock to W.
  4. other threads stop initiating read operations and complete existing ones
  5. the writer waits for all readers to be gone. In the worst case it takes the time it takes for a full read operation, hence 40ns max (20ns avg)
  6. after 635ns max, the writer is alone and can modify the tree
  7. after 640ns max, the write operation is completed, the lock is removed and readers can enter again.
With 8 total cores, all cores can stay busy handling a 99% read ratio and 1% write ratio, since during the 595-635ns the S lock is held by one core, 7 cores can process 105 read operations of 40ns each.

The writer will wait between 0 and 40ns to get exclusive access, thus 20ns on average. As a result, this will bring one write every 620ns and all read requests in parallel. This means that 100 operations are performed every 620ns, bringing a throughput of 161 million operations per second, or 77% faster than when using an R/W lock as above :


Initial implementation

It appeared critical that a single atomic operation could be used to take a lock, so as not to repeat the performance problem of classical R/W locks. Given that the number of readers needs to be known all the time, the lock needs to be large enough to store a number as large as the maximum number of readers, in addition to other information like the other lock states, into a single word-sized memory area guaranteeing the possibility of atomic accesses.

Usually locks are implemented using a compare-and-swap operation (e.g. CMPXCHG on x86), which allows to check for contention before performing an operation. But while using compare-and-swap is convenient when dealing with a few distinct values, it's not convenient at all when dealing with an integer which can vary very quickly depending on the number of readers, because it would require many failed attempts and could even never succeed for some users.

On x86 systems, we have a very convenient XADD instruction. This is an example of fetch-and-add operation : it atomically reads a value from a memory location, adds it to a register, and stores the result back to memory, while returning the original value into the register.

Using XADD definitely helps counting readers, but it is subject to overflows, and doesn't appear very convenient to count write requesters. While we do know that we'll never have many write requesters at once, a safe design mandates to be able to let all threads compete in parallel in this situation.

Thus the idea emerged of splitting an integer into 3 parts :
  • one to count the readers
  • one to count the demands for S locks
  • one to count the demands for W locks
By splitting a 64-bit integer into 3 equal parts, it becomes possible to assign 21 bits per part, hence support up to 2097151 threads without ever causing an overflow. On 32-bit systems, this would only support 1023 threads without overflowing. This limit on 32-bit systems would definitely make the solution unsuitable to some existing software, so some improvements were needed.

As mentionned, the W locks need to be exclusive to all other locks. The S locks need to be exclusive to S and W locks. The R locks need to be exclusive to W locks. This means that it is possible to overflow certain values into the other ones without a risk :

  • if the R bits overflow into the S bits, since S locks are stricter than R locks, the guarantees offered to readers are preserved
  • if the S bits overflow into the W bits, since W locks are stricter than S, the guarantees offered to S users are preserved
But we need to protect W against overflowing or to assign it enough bits.

So in practice the limit is really dictated by the number of bits to represent W. And in order to get optimal performance, and avoid forcing readers to wait, it seems important to have the same number of bits for R. In theory, a single bit is needed for S. But given that concurrent accesses on S would result in occasional appearance of W, this would occasionally make some readers wait while not needed. Thus the choice was made to use two bits for S, supporting up to 3 concurrent seek attempts without perturbing readers, which leaves enough time for these seekers to step back.

This provides the following distribution :
  • on 32-bit platforms :
    • 14 bits for W
    • 2 bits for S
    • 14 bits for R
  • on 64-bit platforms :
    • 30 bits for W
    • 2 bits for S
    • 30 bits for R
The astute reader will have noted that this results in 30 bits for 32-bit platforms and 62 bits on 64-bit platforms. This leaves us with 2 extra bits used for any application purpose, particularly the ebtree configuration bits (unicity etc) :


The initial naive encoding showed that certain combinations correspond to non-existing cases in practices and that a more advanced encoding could help store one extra state.

Indeed, the progress made on ebtrees makes it apparent that certain O(1) operations like the removal of a node might one day be implemented as atomic operations, without requiring any locking. But how is this related to a lock implementation then ? Porting an application or a design from locked to lock-free is never a straightforward operation and can sometimes span over several years making small progress at each attempt. Being able to use a special lock state to mention that it is compatible only with itself and exclusive to all other ones can be very convenient during the time it takes to transform the application.

So a new "A" (for "atomic") state was introduced and all the encoding of the states based on the bits above was redefined to be a bit more complex but still fast and safe, as described below.

Current implementation

The 5 known states of Progressive Locks are now :
  • U (unlocked) : nobody claims the lock
  • R (read-locked) : some users are reading the shared resource
  • S (seek-locked) : reading is still OK but nobody else may seek nor write
  • W (write-locked) : exclusive access for writing
  • A (atomic-locked) : some users are performing safe atomic operations which are potentially not compatible with the ones covered by R/S/W.
The U, R and W state are the common states for classical R/W locks. The S state is an intermediary step between R and W, which still allows readers to enter, but rejects other W and S requests and guarantees a quick upgrade to (as well as return from) the W state. The S lock also makes it possible to implement some "lockless" operations following a "single-writer multiple-readers" model where a single careful writer can perform changes without preventing readers from accessing the data. The A state is for atomic operations mainly consisting in ordered writes, that can be performed in parallel but must not be mixed with R, S nor W.

The S lock cannot be taken if another S or W lock is already held. But once the S lock is held, the owner is automatically granted the right to upgrade it to W without checking for other writers. And it can take and release the W lock multiple times atomically if needed. It must only wait for last readers to
leave.

The A lock supports concurrent write accesses and is used when certain atomic operations can be performed on a structure which also supports non-atomic operations. It is exclusive with the other locks. It is weaker than the S/W locks (S being a promise of "upgradability"), and will wait for any readers to leave before proceeding.

The lock compatibility matrix now looks like below. Compatible locks are immediately obtained. Incompatible locks simply result in the requester to wait for the incompatible ones to leave :



Many transitions are possible between these states for a given thread, as represented on the transition graph below :


Some additional state transitions may be attempted but are not guaranteed to succeed. This is the case when holding a Read lock and trying to turn it into another lock which is limited to a single instance : another thread might attempt to perform exactly the same transition and by definition this can not work for both of them. Moreover, the one succeeding will wait for readers to quit, so the one failing will also have to drop its Read lock in this case before trying again. Nevertheless, the plock API provides an easy access to these uncommon features.


The transitions to W and A are performed in two phases :
  1. request the lock
  2. wait for previous incompatible users to leave
Claiming the Read lock is performed by first checking if nobody holds the W lock. The rationale behind this is to ensure that a thread holding the Write lock and waiting for readers to quit doesn't have to wait for too long seeing new readers come.
The locks are implemented using cumulable bit fields representing from the
lowest to the highest bits :
  • R: the number of readers (read, seek, write)
  • S: the number of seek requests
  • W: the number of write requests
Each regular lock (R, S, W) counts as a reader. Since all of them may operate
on a concurrent read, the maximum number of concurrent threads supported is dictated by the number of bits used to encode the readers.

Since the writers are totally exclusive to any other activity, they require the same number of bits in order to accept the worst possibly imaginable scenario where all threads would request a write lock at the exact same instant so the number of bits used to represent writers is the same as the number used to represent the number of readers.

The number of seek requests remains on a low bit count and this number is placed just below the write bit count so that if it overflows, it temporarily overflows into the write bits and appears as requesting an exclusive write access. This allows the number of seek bits to remain very low, 1 technically, but 2 to avoid needless lock/unlock sequences during common conflicts.

In terms of representation, we now have this :
  • R lock is made of the R bits
  • S lock is made of S+R bits
  • W lock is made of W+S+R bits
  • A lock is made of W bits only
Due to W being made of W+S+R, and S overflowing into W, each time a W lock is directly taken, both W and S bits are added resulting in the W field growing faster than the number of write requests. Indeed, with two bits for S below W, the W:S word is increased by 0b101 = 5 while W represents 1/4 of the W:S word, so each writer consumes 5/4 of a position. But given that 5 doesn't divide any power-of-two quantity, we're guaranteed to always keep at least one non-null bit in the W part of the word for any supported number of writers, and given that the W lock is stronger than the S lock, other access types are protected.

Having only the W bits set in W:S could be confused with the A lock except that the A lock doesn't hold the R bits and is exclusive with regular locks so this situation is unambiguous as well.

In practice, it is useful to understand all states that can be observed in the lock, including the transient ones shown below. "N" means "anything greater than zero". "M" means "greater than 1 (many)". "X" means "anything including zero" :


The lock can be upgraded and downgraded between various states at the demand of the requester :
  • U⇔A : pl_take_a() / pl_drop_a()   (adds/subs W)
  • U⇔R : pl_take_r() / pl_drop_r()   (adds/subs R)
  • U⇔S : pl_take_s() / pl_drop_s()   (adds/subs S+R)
  • U⇔W : pl_take_w() / pl_drop_w()   (adds/subs W+S+R)
  • S⇔W : pl_stow()   / pl_wtos()     (adds/subs W)
  • S⇒R : pl_stor()                   (subs S)
  • W⇒R : pl_wtor()                   (subs W+S)
This is where the XADD instruction really shines : it is possible to take or upgrade any lock using a single atomic instruction by carefully setting the constant value. And while doing this, the current value is retrieved so that the requester can check whether or not it is causing a conflict and has to rollback the change. Dropping, downgrading a lock, or cancelling a failed attempt to take a lock simply requires an atomic subtract.

In case of conflict, the requester has to periodically observe the lock's status by reading it, and trying again once the lock's status appears to be compatible with the request. It is very important not to try to take the lock again without reading first because of the way CPU caches work : each write attempt to a shared memory location (here the lock) will broadcast a request to all other caches to flush their pending changes and to invalidate the cache line. If the lock is located close to a memory location being modified under this lock's protection, repeated write attempts to the lock will significantly slow down the progress of the other thread holding the lock since the cache line will have to bounce back and forth between competing threads.

Instead, by only reading the lock, the other caches will still have to flush their pending changes but not to invalidate the cache line. This way it will still make progress, albeit not as fast as what it could do without this.

In order to improve the situation, Progressive locks implement an exponential backoff : each failed attempt causes the failing thread to wait twice as long as the previous time before trying again. This well known method used in locks and in network protocols comes with three immediate benefits :
  1. it limits the disturbance caused to the thread holding the lock
  2. it avoids cache storms when using many concurrent threads
  3. it provides a much better fairness to all threads by increasing the randomness of their attempts
When a thread is silently waiting, it uses some CPU-specific instructions like the PAUSE instruction on x86 processors, which stops execution for a few cycles and leaves the CPU pipelines available to the other thread of the same CPU core, thus further speeding up processing on simultaneous multi-threaded environments.

Performance measurements

A new locking mechanism couldn't work without some performance benchmarks. One such utility implementing a simple LRU cache using a hash table is provided with the software package, under the name lrubench. This utility looks up and inserts random values into a cache if they are not present yet. It allows to set the number of concurrent threads, the cache size (number of keys kept before eviction), the key space to control the cache hit ratio, the cost of a cache miss (number of loops to perform on a simple operation mimicking a real, more expensive operation like a regex call), and the locking strategy.

For each locking strategy, the principle is the same :
  1. perform a lookup of the value in the cache
  2. if the value is present, use it
  3. otherwise perform the expensive operation
  4. insert the result of this expensive operation into the cache, only if it was not added in the mean time by another thread, otherwise replace this older entry with the new one
  5. in case of insertion, remove possible excess elements from the cache to keep it to the desired size
Eight locking strategies are supported :
  1. pthread spinlock : the first lookup is protected using pthread_spinlock(). During the insertion, the lookup, the possible removal, and the insertion are atomically performed using pthread_spinlock(). No parallel operation is possible on the cache.
  2. pthread rwlock : the first lookup is protected using pthread_rwlock_rdlock(). During the insertion, the lookup, the possible removal, and the insertion are atomically performed using pthread_rwlock_wrlock(). Initial lookups may be processed in parallel but not the second ones.
  3. plock W lock : the first lookup is protected using a W lock. During the insertion, the lookup, the possible removal, and the insertion are atomically performed using a W lock. No parallel operation is possible on the cache. This is comparable to the pthread spinlock strategy.
  4. plock S lock : the first lookup is protected using an S lock. During the insertion, the lookup, the possible removal, and the insertion are atomically performed using an S lock. No parallel operation is possible on the cache. This is comparable to the plock W lock above but is slightly faster because the S lock doesn't have to check for readers. It is the closest plock alternative to the pthread spinlock.
  5. plock R+W lock : the first lookup is protected using a R lock. During the insertion, the lookup, the possible removal, and the insertion are atomically performed using a W lock. Initial lookups may be processed in parallel but not the second ones. This is comparable to the pthread rwlock strategy, but is much faster due to the single atomic operation.
  6. plock R+S>W lock : the first lookup is protected using a R lock. During the insertion, the lookup is performed using an S lock, then the possible removal, and the insertion are atomically performed by upgrading the S lock to a W lock. Initial lookups may be processed in parallel as well as in parallel to the second ones. Only one second lookup may be performed at a time, and initial lookups are only blocked during the short write period at the end.
  7. plock R+R>S>W lock : the first lookup is protected using a R lock. During the insertion, the lookup is performed using an R lock, then the possible removal, and the insertion are atomically performed by upgrading trying to upgrade the R lock to an S lock, or performing the operation again using an S lock in case of conflict. Then the S lock is upgraded to aa W lock to complete the operation. Initial lookups may be processed in parallel as well as in parallel to the second ones. The second lookups may be performed in parallel as well, unless a write access is already claimed, forcing a second lookup to be done.
  8. plock R+R>W lock : the first lookup is protected using a R lock. During the insertion, the lookup is performed using an R lock, then the possible removal, and the insertion are atomically performed by upgrading trying to upgrade the R lock to a W lock, or performing the operation again using a W lock in case of conflict. Initial lookups may be processed in parallel as well as in parallel to the second ones. The second lookups may be performed in parallel as well, unless a write access is already claimed, forcing a second lookup to be done.
The utility has been run on a 12-core Xeon E5-2680v3 at 2.5 GHz with HyperThreading enabled.

The graphs below represent the number of cache lookup operations per second achieved using these different locks, for 6 different cache hit ratios (50%, 80%, 90%, 95%, 98%, 99%), for 3 different cache miss costs (30, 100, 300 snprintf() loops), and with a varying number of threads. The left part of the graph uses only one thread per CPU core (no HyperThreading involved), and the right part of the graph uses two threads per CPU core (HyperThreading).

Low miss cost (30 loops)

(click on the graphs to zoom)

Medium miss cost (100 loops)

(click on the graphs to zoom)

High miss cost (300 loops)

(click on the graphs to zoom)

It is obviously not a surprise that the difference between locking mechanisms fades away when the miss cost increases and the hit ratio diminishes since more time is proportionally spent computing a value than competing for a lock. But the difference at high hit ratios for large numbers of threads is stunning : at 24 threads, the plock can be respectively 5.5 and 8 times faster than R/W locks and spinlocks! And even at low hit ratios and high miss cost, the plocks are never below the pthread locks and become better past 8-10 threads.

The more time the lookup takes, the wider the gap between the different mechanisms, since in the case of spinlocks or R/W locks, exclusive access is required during the insertion, making even a single thread doing an occasional insert stop all other threads from using the cache. This is not the case with plocks, except in the R+R>W mode upon failure to upgrade due to two threads trying to concurrently insert an entry. This is what causes the R+R>W mechanism to converge to the R+W mechanism when the thread count increases.

It looks like the upgrade attempts from the R lock are pointless on this workload, because there is rarely a contention between two insertions. It starts to be slightly beneficial only when dealing with important lookup times and cache miss ratios. But in this case one of the threads has to retry the operation, which is not much different from being serialized around an S lock.

At low hit ratios (50%), the spinlocks are cheaper than R/W locks (less operations, balance around 80% and 10 threads), and the plock S and W variants are slightly faster than the spinlocks and converge towards them with more threads. One explanation might be the use of exponential back-off in plock that makes it behave slightly better for a comparable workload. But at even only 80% cache hit ratio (hence 20% miss), all strict locks behave similarly and the benefit of the upgradable locks becomes obvious.

It is also visible on graphs with high hit ratios that the spinlock performance degrades as the number of threads increases. One could think that this would indicate that the spinlocks do not use an exponential back-off to avoid polluting the bus and caches, but the curve is perfectly merged with the plock-S and plock-W curves, and plock does use exponential back-off. In fact the reason here is different. It's simply that plock-S and plock-W start with an aggressive locked XADD operation, and that the spinlocks use a locked CMPXCHG operation. Both operations unconditionally issue a bus write cycle, even the CMPXCHG! This is explained in the Intel Software Developer's manual in the CMPXCHG instruction description : "To simplify the interface to the processor’s bus, the destination operand receives a write cycle without regard to the result of the comparison. The destination operand is written back if the comparison fails; otherwise, the source operand is written into the destination. (The processor never produces a locked read without also producing a locked write.)". These write operations have a negative effect on the other CPU's caches, forcing invalidations, which explains why the performance slowly degrades.

For plock, an attempt was made to read before writing, but this results in a small performance loss for most common cases which isn't worth the change. In the end this preliminary read is only performed before taking the R lock, because in general this lock is taken before a long operation so a double read is easily amortized, and because not doing it increases the time it takes for a W lock holder to see the last reader quit.

Integrating Progressive locks into a program

The plock Git tree can be consulted and cloned from here. The code was made to have the least possible dependencies. It only consists in an include file bringing all the code as macros, and a second include file providing the atomic operations. The choice of macros was made so that the calls may automatically be used on 32- and 64- bit locks. 32-bit platforms may only use 32-bit locks, but 64-bit platforms may use both. For most use cases, it's likely that even a 64-bit platform will not need more than 16383 threads and may prefer to save space by using only 32-bit locks.

A program only needs to do this to use plocks :

#include <plock.h>

From this point, adding a lock to a structure simply requires an integer, long or even a pointer :

struct cache {
     struct list head;
     int plock;
};

A lock value of zero describes and unlocked state, which is easy to initialize since any structure allocated with calloc() starts with an initialized lock.

Appending an entry without requiring any lookup would consist in simply taking the W lock around the cache access :

struct cache_node *__cache_append(struct cache *, const char*);
void cache_insert(struct cache *cache, const char *str)
{
    struct cache_node *node;

    pl_take_w(&cache->plock);
    node = __cache_append(cache, str);
    pl_drop_w(&cache->plock);
}

Then reading from the cache would basically consist in taking the R lock before operating :

struct cache_node *__cache_find(const struct cache *, const char*);

int cache_find(struct cache *cache, const char *str)  {
    const struct cache_node *node;
    int ret;

    pl_take_r(&cache->plock);
    node = __cache_find(cache, str);
    ret = node ? node->value : -1;
    pl_drop_r(&cache->plock);
    return ret;
}

Deleting an entry from the cache would consist in taking the S lock during the lookup and upgrading it to a W lock for the final operation :

struct cache_node *__cache_find(const struct cache *, const char*);
void __cache_free(struct cache *, struct cache_node *);

void cache_delete(struct cache *cache, const char *str)  {
    struct cache_node *node;

    pl_take_s(&cache->plock);
    node = __cache_find(cache, str);
    if (!node) {
       pl_drop_s(&cache->plock);
       return;
    }
    pl_stow(&cache->plock);
    __cache_free(cache, node);
    pl_drop_w(&cache->plock);
}

Inserting an entry only if it doesn't already exist can be done in multiple ways (typically taking the S lock for a lookup and upgrading it if no node is found). One interesting way when the risk of collision is low and the insertion rate is high (eg: log indexing) consists in using a read lock and to attempt an upgrade to W, or falling back to an S lock in case of failure. This way many threads may insert in parallel and their atomicity checks will be parallelized yet will guarantee atomicity :

struct cache_node *__cache_find(const struct cache *, const char*);
struct cache_node *__cache_append(struct cache *, const char*);

void cache_insert_unique(struct cache *cache, const char *str)
{
    struct cache_node *node;

    pl_take_r(&cache->plock);
    node = __cache_find(cache, str);
    if (node) {
        pl_drop_r(&cache->plock);
        return;
    }
    if (!pl_try_rtow) {
        /* upgrade conflict, must drop R and try again */
        pl_drop_r(&cache->plock);
        pl_take_s(&cache->plock);
        node = __cache_find(cache, str);
        if (node) {
           pl_drop_s(&cache->plock);
           return;
        }
        pl_stow(&cache->plock);
    }
    /* here W is held */
    node = __cache_append(cache, str);
    pl_drop_w(&cache->plock);
}

The lrubench.c  test program provided with plock gives a good illustration of how the locks can be used using various strategies compared to spinlocks and standard RW locks.

Extra work

Some cleanup work remains to be done on the locks, particularly on the atomic operations which confusingly are prefixed with "pl_". Some of them will move to a distinct low-level library. This is not important since users should normally not use these functions directly.

It seems useless to implement progressive locks on 16-bit values (would support at most 127 threads, or 63 if keeping the 2 application bits). But maybe some environments could make good use of them by reusing holes in existing structures.

I made a few attempts at using the same mechanism to implement tickets to grant an even better fairness to many threads, but didn't find a way to guarantee uniqueness of ticket numbers without performing multiple atomic operations.

It would seem that sort of an atomic "test-and-add" operation would be beneficial here to avoid taking the lock then rolling it back in case of conflict. It would be a mix of a test-and-set and an addition replacing the XADD so that the addition is only performed if certain bits are not set (typically S and W bits). While no such instruction exists for now, a few different options should probably be considered :
  • HLE (Hardware Lock Elision), which is a new mechanism introduced with Intel's TSX extensions. The idea is to define a code section where locks are ignored and the operation is attempted directly into the L1 cache. If it succeeds, we've saved some bus locks. If it fails, it is attempted again with the real locks. It seems that it could be used for the read+XADD at least when taking an R lock, and avoid having to grab the bus lock at this point. Some experimentation is required. What's nice is that code written like this is backwards compatible with older processors.
  • RTM (Restricted Transactional Memory) is a more complex mechanism allowing to know if a sequence of operations has a chance to succeed lockless or requires locking. In case of failure the operation will be attempted again. It matches very closely the R->S and R->M opportunistic upgrades that we have in the example above. This could also be used to insert or delete a node in the tree after a lockless lookup.

Annex A: detailed locking rules

The rights and expectations these locks impose to their users are the following :

  • unlocked (U) :
    • nobody may perform visible modifications to the protected area at all
    • anybody can read the protected area at their own risk
    • anybody may immediately turn the lock to any other state
  • read-locked (R) :
    • requester must wait for writers to leave before being granted the lock
    • owner may read any location from the protected structure without any requirement for ordering
    • others may read any location from the protected structure without any requirement for ordering
    • others may also be granted an R lock
    • one other user may also be granted an S lock
    • one other may take a W lock but will first have to wait for all readers to leave before proceeding with writes
  • seek-locked (S) :
    • requester must wait for writers and seekers to leave before being granted the lock
    • owner may read any location from the protected structure without any requirement for ordering
    • others may read any location from the protected structure without any requirement for ordering
    • others may also be granted an R lock
    • owner may upgrade the lock to a W lock at any instant without prior notification
    • owner must wait for readers to leave after the lock is upgraded before performing any write
    • owner may release the lock without performing an upgrade
    • owner may also downgrade the S lock to an R lock
  • write-locked (W) :
    • requester must wait for writers and seekers to leave before being granted the lock (this is guaranteed when upgrading from S)
    • others may not try to grab any lock once this lock is held
    • the lock is granted once all other users have left
    • owner may perform any modification to the protected structure
    • others may not access the protected structure at all
    • owner may downgrade the lock to an S lock
    • owner may downgrade the lock to an R lock
  • atomic (A) :
    • requester must wait for writers and seekers to leave before being granted the lock, but doesn't exclude other write-atomic users
    • the lock is granted once all other users have left
    • owner is not guaranteed to be alone since other users may hold the A lock in parallel and perform modifications at the same time ; observations and retries might be necessary to complete certain operations
    • owner may only carefully apply modifications to the protected structure using atomic operations and memory barriers in a way that is compatible with its own usage
    • others may only carefully apply modifications to the protected structure using atomic operations and memory barriers in a way that is compatible with others' usage
    • the protections involved with this type of lock are 100% application specific. Most commonly this will be used to reinitialize some elements, release a series of pointers using atomic operations and all compatible functions will use this lock instead of any of the 3 above.