--- title: "SafeCode Consulting - Atomic-Powered Functions from Two Tiny Primitives" description: "Two wrapped instructions can build atomic exchange, compare-and-replace and add, plus counters and semaphores. What the load-and-reserve pair makes possible." url: "https://safecodetech.com/insights/articles/design-3-lil2-atomic-powered-functions.html?tmpl=component" date: "2026-10-06T20:47:52-04:00" language: "en-US" --- ## Breadcrumbs [Home](https://safecodetech.com/) > Insights > [Articles](https://safecodetech.com/insights/articles.html) > Atomic-Powered Functions from Two Tiny Primitives ## Atomic-Powered Functions from Two Tiny Primitives Details By Max Hinkley Max Hinkley October 06, 2026 ##### *Part 2 of 3 in the Locks-in-Layers series* The previous article in this series, [Some Assembly Required: Filling an RTOS Gap](https://safecodetech.com/insights/articles/insights/articles/design-2-lil1-some-assembly-required) , introduced the problem of creating spinlocks and ended with two inline functions, providing C language access to assembly language concepts, `load_and_reserve` and `store_if_reserved`. Together they can be used to make almost any simple operation behave as though it were atomic. This installment looks at what can be built directly on them, and at the synchronization concepts that depend on those operations, including the spinlock. With the exception of implementing the two wrappers mentioned above, the algorithms coded here should be portable to any MPU that supports these concepts. ### The Versatility The `load_and_reserve` and `store_if_reserved` pair enable creation of some very useful higher-level abstractions: - **Ticket locks**: Each arriving task atomically takes a ticket number and then waits until a "now serving" counter reaches it. That gives first-come, first-served ordering and removes starvation, which a plain spinlock can't promise. - **Sequence locks**: A writer bumps a counter before and after updating small data such as a timestamp or a counter. Readers take no lock, read the counter before and after, and retry if it changed or was odd. This suits data that is read often and written rarely. - **Reader-writer and event flags**: A word whose bits mean different things can be updated atomically, including set-bit, clear-bit and "claim the bit if it was clear." These are not uncommon in RTOS code. - **Lock-free stacks and free lists**: A Treiber stack is a single linked list updated with a retry loop on the top pointer. It is the simplest non-trivial lock-free structure. A free list or fixed buffer pool built this way lets an ISR and a task allocate without a lock. - **Queues**: Lock-free multi-producer queues use the same compare-and-retry pattern. - **Counters with rules**: Saturating counters, atomic minimum and maximum, and a high-water mark are all one retry loop with a test inside. That test is the creative part, because the loop can apply any short rule. All of these are possible, but they generally rest on tiny building blocks. ### The Repeating Pattern In our case, every operation built on the primitive pair has the same skeleton. Load the current value and reserve it, compute the new value, attempt the conditional store, and start over if the store reports failure. A failed store means the reservation was broken, so something modified the region between the load and the store, and the computed result was based on stale data. `do {` `old = load_and_reserve( location );` `new = f( old ); /* any simple computation */` `} while ( !store_if_reserved( location, new ) );` The loop is the price of not having a truly atomic instruction. The computation between the two calls should be as short as you can make it, because a longer window gives other code more opportunity to break the reservation. The short window makes the unbounded structure of the loop a non-issue. On some architectures, unrelated memory accesses between the pair can also cause the store to fail, and the exact rules vary by processor, so the documentation for your target deserves a careful read. Here is a small collection of operations using the pair that can be used as building blocks for bigger things: `/**` `* This can be used to non-destructively cancel a reservation held` `* by another process, forcing it to retry it's operation.` `* @param res [IN] The data location` `* @return the value of res.` `*/` `value_t load_and_unreserve( volatile reserved_t* res ) {` `value_t v;` `do {` `v = load_and_reserve( res );` `} while ( !store_if_reserved( res, v ) );` `return v;` `}` `/**` `* Replace the value of res with val, and return its original value.` `* @param res [IN/OUT] The data location` `* @param val [IN] The value to be conditionally written.` `* @return the value of res before it was overwritten.` `*/` `value_t exchange( volatile reserved_t* res, const value_t val ) {` `value_t v;` `do {` `v = load_and_reserve( res );` `} while ( !store_if_reserved( res, val ) );` `return v;` `}` `/**` `* Replace the value of res with val, only if *res matches the value of cmp.` `* @param res [IN/OUT] The data location` `* @param cmp [IN] The value to compared with the current content.` `* @param val [IN] The value to be conditionally written.` `* @param act [OUT] The actual value of res at exit.` `* @return true iff *res contained cmp, and val was written; otherwise false.` `*/``bool replace_if_match( volatile reserved_t* res, const value_t cmp, const value_t val, value_t* act ) {` `value_t v;` `do {` `v = load_and_reserve( res );` `if ( v != cmp ) {` `*act = v;` `return false;` `}` `} while ( !store_if_reserved( res, val ) );` `*act = val;` `return true;` `}` `/**` `* Replace the value of res with val, only if res originally contains zero.` `* @param res [IN/OUT] The data location` `* @param val [IN] The value to be conditionally written.` `* @return true iff *res contained 0, and val was written; otherwise false.` `*/` `bool replace_if_zero( reserved_t* res, const value_t val ) {` `value_t act;` `return replace_if_match( res, (value_t)0, val, &act );` `}` `/**` `* Add delta to *res and return the previous value. This is similar to a post-increment.` `* @res [IN/OUT] the location containing the value to be updated.` `* @delta [IN] the value to be added to *res` `* @return the original (pre-addition) value of *res` `*/` `value_t atomic_add( volatile reserved_t* res, value_t delta ) {` `value_t old;` `do {` `old = load_and_reserve( res );` `} while ( !store_if_reserved( res, old + delta ) );` `return old;` `}` Of this group, Compare-and-swap (replace_if_match, above) is the most versatile, and the one most lock-free algorithms are expressed in. Locks, counters, and linked structures can all be built from it. On a processor with a reservation pair, it is one more retry loop with a test inserted, and it returns early, without storing, when the value does not match. ### Counters, Semaphores, and Shared Structures Fetch-and-add covers the simple cases directly. Event counters, statistics gathering, and reference counts are all a single call, with no lock involved. A counting semaphore is nearly as simple, since its core is a counter that must never go below zero: `/* Non-blocking take: returns true if a unit was available. */` `bool semaphore_try_take( volatile reserved_t* count ) {` `value_t n;` `do {` `n = load_and_reserve( count );` `if ( n == 0 ) {` `return false;` `}` `} while ( !store_if_reserved( count, n - 1 ) );` `return true;` `}` `void semaphore_give( volatile reserved_t* count ) {` `atomic_add( count, 1 );` `}` This is an incomplete example of a non-blocking semaphore. It lacks initialization and an upper limit on give. Shared data structures are also possible. A linked stack can be pushed and popped without a lock. The push reads the head pointer, links the new node to it, and conditionally stores the new node's address as the head. Thread-safe add and remove operations on containers reduce to the same pattern. A simple (non-atomic) compare-and-swap has one well-known weakness here, called the ABA problem. The comparison checks only that the value is unchanged. If another task removed a node and later put the same node back, the head pointer looks untouched even though the list changed underneath. This weakness can be overcome using the reserved store pair described in the previous installment, since a reservation breaks on any write to its region, whether or not the value ends up the same. Of course, for some problems, the simple compare-and-swap is a perfectly appropriate solution. These problems are not common to every kind of programming. Some languages and platforms provide the mechanisms already. Multiprocessing and multi-threaded applications on real-time operating systems are where these techniques come into their own. Part 3, [Locks in Layers: Different Strokes](https://safecodetech.com/insights/articles/insights/articles/design-4-lil3-locks-in-layers), walks through the four layers I built on these primitives, from the derived atomics up to a keyed lock, and explains why each one exists.