Load-Linked and Store-Conditional

We've seen how compare-and-swap (CAS) can be a powerful tool for implementing lock-free data structures. But it's not the only game in town. Some architectures, including MIPS (which your OS/161 system uses), provide an alternative pair of instructions: load-linked (LL) and store-conditional (SC).

How LL/SC Works

The load-linked and store-conditional instructions work together:

1. load-linked loads a value from memory and marks the memory location as “monitored”.
   • Think of it like there is a spy-camera on the memory location, watching to see if anyone else messes with it.
2. store-conditional attempts to store a value to the monitored location. It succeeds only if the location hasn't been modified since load-linked ran.

Here's some pseudocode to illustrate:

int
load_linked(int *ptr) {
        MEMORY_WATCHER_TRACK(*ptr);
        return *ptr;
}

bool store_conditional(int *ptr, int new_value) {
        switch (MEMORY_WATCHER_STATUS(*ptr)) {
            case MW_MODIFIED:
                return false;
            case MW_SORRY_I_LOST_TRACK:
                return false;
            case MW_UNCHANGED:
                *ptr = new_value;
                return true;
        }
}

(Remember, each of these functions is pseudocode for a single hardware instruction.)

Implementing Compare-and-Swap with LL/SC

You can implement CAS using LL/SC. Here's how you might do it:

bool compare_and_swap(int *ptr, int expected, int new_value) {
    int current = load_linked(ptr);
    if (current == expected) {
        return store_conditional(ptr, new_value);
    }
    return false;
}

The A–B–A Problem

Let's go back and look at the code we used for our lock-free stack. Although it seems to work, it actually has an insidious bug, due to the highlighted line:

// Helper function to pop an item from the stack
int
pop_item(void)
{
        while (1) {
                struct stack_node *popped_node = atomic_load(&stack_head);
                if (popped_node == NULL) {
                        return NO_DATA; // Stack is empty
                }

                struct stack_node *new_head = popped_node->next;
                if (atomic_compare_exchange_weak(&stack_head, &popped_node,
                                                 new_head)) {
                        int value = popped_node->data;
                        free(popped_node);
                        return value;
                }
                // If CAS failed, another thread modified the stack, so we try
                // again
        }
}

In that line, we think we have the right value for new_head. But let's consider this sequence of events:

• We read popped_node from stack_head; let's suppose it's at memory address 0x1234.
• We read popped_node->next, and it's at memory address 0x5678.
• Then, another thread runs. It
  • Pops a node from the stack, throwing away the node at 0x1234.
  • Pops another node from the stack, throwing away the node at 0x5678, leaving a new stack head of 0x9abc.
  • Pushes a new node onto the stack, where its next pointer is 0x9abc as it should be, but alas, the memory allocator chose to put our new node at location 0x1234 as that location isn't being used.
• Our thread continues. It does the compare-and-swap, looking to see if 0x1234 is still the head of the stack. It succeeds, replacing the stack head with 0x5678, a deleted node.

Practical Considerations

While LL/SC is theoretically more powerful than CAS, there are some practical limitations.

1. Hardware Limitations: Many implementations of LL/SC have restrictions. For example, some prohibit any function calls or interrupts between the LL and SC instructions. But that's not really a huge limitation in practice, given that the alternative is a single CAS instruction.
2. Limited Availability: Not all processors support LL/SC. x86 processors, which are very common, use CAS instead. (On the other hand, ARM, RISC-V, and PowerPC do support LL/SC, as does MIPS, which is what OS/161 is based on.)
3. C/C++ Support: Standard C and C++ don't provide direct support for LL/SC operations, which makes it less convenient to use LL/SC in portable code.

That said, LL/SC is superior to CAS, and it's good to use when practical.

LL/SC in OS/161

OS/161 runs on a simulated MIPS32 processor which does support LL/SC, and if you go spelunking in the OS/161 source code, you'll find them used. For example, in kern/arch/mips/include/spinlock.h, you'll see

/*
 * Test-and-set a spinlock_data_t. Use the LL/SC instructions to
 * make it atomic.
 *
 * LL (load linked) loads a machine word from memory, and marks the
 * address. SC (store conditional) stores a machine word to memory,
 * but succeeds only if the address is marked from a previous LL on
 * the same processor. Stores from other processors clear that mark,
 * as do traps on the current processor. Note that there may be no
 * other memory accesses (besides instruction fetches) between the LL
 * and the SC or the behavior is *undefined*. You can only use LL/SC
 * to atomically update one machine word.
 */
SPINLOCK_INLINE
spinlock_data_t
spinlock_data_testandset(volatile spinlock_data_t *sd)
{
        spinlock_data_t x;
        spinlock_data_t y;

        /*
         * Test-and-set using LL/SC.
         *
         * Load the existing value into X, and use Y to store 1.
         * After the SC, Y contains 1 if the store succeeded,
         * 0 if it failed.
         *
         * On failure, return 1 to pretend that the spinlock
         * was already held.
         */

        y = 1;
        __asm volatile(
                ".set push;"            /* save assembler mode */
                ".set mips32;"          /* allow MIPS32 instructions */
                ".set volatile;"        /* avoid unwanted optimization */
                "ll %0, 0(%2);"         /*   x = *sd */
                "sc %1, 0(%2);"         /*   *sd = y; y = success? */
                ".set pop"              /* restore assembler mode */
                : "=&r" (x), "+r" (y) : "r" (sd));
        if (y == 0) {
                return 1;
        }
        return x;
}

Takeaways

• Load-Linked and Store-Conditional (LL/SC) is an alternative to Compare-and-Swap (CAS) for implementing atomic operations.
• LL/SC can avoid some issues that CAS can run into, such as the A–B–A problem.
• While theoretically more powerful, LL/SC has practical limitations that make it less commonly used than CAS in general-purpose code.
• When writing C code, the differences between LL/SC and CAS are often abstracted away, allowing us to focus on the higher-level algorithm rather than the specific hardware instructions.
• In OS/161, where sys161 simulates a MIPS32 processor, LL/SC is the native atomic operation.

(When logged in, completion status appears here.)