Spin Time Considerations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# Cache coherence traffic with aggressive TAS spinning
# 4 CPUs spinning on same lock
 
Time  | CPU0 (holder)  | CPU1 (spinner) | CPU2 (spinner) | CPU3 (spinner)
------+----------------+----------------+----------------+----------------
T1    | In critical    | TAS → get excl | (waiting)      | (waiting)
T2    | (working)      | Invalidate all | TAS → get excl | (waiting)
T3    | (working)      | Miss, refetch  | Invalidate all | TAS → get excl
T4    | (working)      | TAS → get excl | Miss, refetch  | Invalidate all
T5    | (working)      | Invalidate all | TAS → get excl | Miss, refetch
...   | (continuous coherence storm, even though holder works unimpeded)
 
# Result: Each TAS iteration takes 50-200 cycles instead of 3-4
# Interconnect bandwidth consumed by spinners, not useful work
# Lock holder's cache also suffers from the storm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

// Spin loop with PAUSE - proper implementation
 
void spin_loop_with_pause(volatile int *flag) {
    while (*flag == 0) {
        // Insert PAUSE hint
        // Each iteration waits ~40 cycles instead of ~1
        // Dramatically reduces cache/interconnect pressure
        #if defined(__x86_64__) || defined(__i386__)
            __asm__ volatile("pause" ::: "memory");
        #elif defined(__aarch64__)
            __asm__ volatile("yield" ::: "memory");
        #elif defined(__riscv)
            __asm__ volatile(".insn i 0x0f, 0, x0, x0, 0x010");  // pause
        #else
            // Generic fallback - compiler barrier at minimum
            __asm__ volatile("" ::: "memory");
        #endif
    }
}
 
// Using __builtin_ia32_pause() on GCC/Clang x86
void spin_loop_builtin(volatile int *flag) {
    while (*flag == 0) {
        __builtin_ia32_pause();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// Constant backoff spinlock
 
#define BACKOFF_ITERATIONS 100
 
void spin_lock_constant_backoff(spinlock_t *lock) {
    while (1) {
        // Check if lock looks free (TTAS)
        if (atomic_load(&lock->locked) == 0) {
            // Try to acquire
            if (atomic_exchange(&lock->locked, 1) == 0) {
                return;  // Got it!
            }
        }
        
        // Failed - back off before retrying
        for (int i = 0; i < BACKOFF_ITERATIONS; i++) {
            __builtin_ia32_pause();
        }
    }
}
 
// Pros: Simple, adds consistent delay
// Cons: Fixed delay is suboptimal for varying contention levels
//       Too short under high contention, too long under low contention

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

// Exponential backoff spinlock
 
#define MIN_BACKOFF 4
#define MAX_BACKOFF 256
 
void spin_lock_exponential_backoff(spinlock_t *lock) {
    int backoff = MIN_BACKOFF;
    
    while (1) {
        // TTAS: spin on read first
        while (atomic_load_explicit(&lock->locked, memory_order_relaxed) != 0) {
            __builtin_ia32_pause();
        }
        
        // Try to acquire
        if (atomic_exchange_explicit(&lock->locked, 1, memory_order_acquire) == 0) {
            return;  // Success!
        }
        
        // Failed - execute backoff delay
        for (int i = 0; i < backoff; i++) {
            __builtin_ia32_pause();
        }
        
        // Double the backoff for next failure
        if (backoff < MAX_BACKOFF) {
            backoff *= 2;
        }
    }
}
 
void spin_unlock(spinlock_t *lock) {
    atomic_store_explicit(&lock->locked, 0, memory_order_release);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

// Randomized exponential backoff
 
#define MIN_BACKOFF 4
#define MAX_BACKOFF 256
 
// Simple pseudo-random number generator (fast, per-thread)
static __thread unsigned int random_state = 12345;
 
unsigned int fast_random(void) {
    random_state = random_state * 1103515245 + 12345;
    return random_state;
}
 
void spin_lock_randomized_backoff(spinlock_t *lock) {
    int limit = MIN_BACKOFF;
    
    while (1) {
        // TTAS spin
        while (atomic_load_explicit(&lock->locked, memory_order_relaxed) != 0) {
            __builtin_ia32_pause();
        }
        
        // Try to acquire
        if (atomic_exchange_explicit(&lock->locked, 1, memory_order_acquire) == 0) {
            return;
        }
        
        // Random backoff in range [0, limit)
        int backoff = fast_random() % limit;
        for (int i = 0; i < backoff; i++) {
            __builtin_ia32_pause();
        }
        
        // Increase limit for next iteration
        if (limit < MAX_BACKOFF) {
            limit *= 2;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

// Proportional backoff based on observed contention
 
struct tracked_spinlock {
    atomic_int locked;
    atomic_int waiters;      // Count of waiting threads
    atomic_int avg_hold_time;// Exponential moving average of hold time
};
 
void spin_lock_proportional(struct tracked_spinlock *lock) {
    // Register as a waiter
    atomic_fetch_add(&lock->waiters, 1);
    
    while (1) {
        if (atomic_load(&lock->locked) == 0) {
            if (atomic_exchange(&lock->locked, 1) == 0) {
                // Got it - unregister as waiter
                atomic_fetch_sub(&lock->waiters, 1);
                return;
            }
        }
        
        // Proportional backoff based on waiters and expected hold time
        int waiters = atomic_load(&lock->waiters);
        int avg_hold = atomic_load(&lock->avg_hold_time);
        
        // Our expected wait ≈ waiters × avg_hold_time
        // Backoff proportional to this
        int backoff = waiters * (avg_hold / 100);  // Tune divisor
        backoff = min(backoff, MAX_BACKOFF);
        backoff = max(backoff, MIN_BACKOFF);
        
        for (int i = 0; i < backoff; i++) {
            __builtin_ia32_pause();
        }
    }
}
 
void spin_unlock_proportional(struct tracked_spinlock *lock, int hold_time) {
    // Update moving average of hold time
    int old_avg = atomic_load(&lock->avg_hold_time);
    int new_avg = (old_avg * 7 + hold_time) / 8;  // 7/8 old, 1/8 new
    atomic_store(&lock->avg_hold_time, new_avg);
    
    atomic_store(&lock->locked, 0);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

// NUMA-aware backoff
 
int get_numa_node(void *addr);  // Get NUMA node of memory address
int my_numa_node(void);         // Get current CPU's NUMA node
 
void spin_lock_numa_aware(spinlock_t *lock) {
    int lock_node = get_numa_node(lock);
    int my_node = my_numa_node();
    
    // Base backoff scales with NUMA distance
    int base_backoff;
    if (lock_node == my_node) {
        base_backoff = 4;    // Local - be aggressive
    } else {
        base_backoff = 64;   // Remote - back off more
        // Remote spinning is expensive and pollutes interconnect
    }
    
    int backoff = base_backoff;
    
    while (1) {
        while (atomic_load_explicit(&lock->locked, memory_order_relaxed) != 0) {
            __builtin_ia32_pause();
        }
        
        if (atomic_exchange_explicit(&lock->locked, 1, memory_order_acquire) == 0) {
            return;
        }
        
        // Backoff with NUMA-adjusted values
        for (int i = 0; i < backoff; i++) {
            __builtin_ia32_pause();
        }
        
        backoff = min(backoff * 2, MAX_BACKOFF);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

// Spin with yield fallback
 
#define SPIN_LIMIT 1000
 
void spin_lock_with_yield(spinlock_t *lock) {
    int spin_count = 0;
    
    while (1) {
        while (atomic_load(&lock->locked) != 0) {
            if (spin_count < SPIN_LIMIT) {
                __builtin_ia32_pause();
                spin_count++;
            } else {
                // Spun enough - let other threads run
                sched_yield();
                spin_count = 0;  // Reset and try again
            }
        }
        
        if (atomic_exchange(&lock->locked, 1) == 0) {
            return;
        }
        
        spin_count = 0;
    }
}
 
// sched_yield() moves this thread to the back of the run queue
// Other runnable threads get a chance to execute
// If the lock holder is on the same CPU, this helps it finish

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

// Adaptive spinlock: spin, then block
 
#define SPIN_THRESHOLD 1000
 
typedef struct {
    atomic_int locked;
    atomic_int waiters;           // Count of blocked waiters
    // Platform-specific: futex, mutex, semaphore, etc.
    blocking_primitive_t waiter;
} adaptive_spinlock_t;
 
void adaptive_lock(adaptive_spinlock_t *lock) {
    int spins = 0;
    
    // Phase 1: Optimistic spinning
    while (spins < SPIN_THRESHOLD) {
        if (atomic_load(&lock->locked) == 0) {
            if (atomic_exchange(&lock->locked, 1) == 0) {
                return;  // Got it without blocking!
            }
        }
        __builtin_ia32_pause();
        spins++;
    }
    
    // Phase 2: Spin exhausted - prepare to block
    atomic_fetch_add(&lock->waiters, 1);
    
    while (1) {
        // One more spin check before blocking
        if (atomic_load(&lock->locked) == 0) {
            if (atomic_exchange(&lock->locked, 1) == 0) {
                atomic_fetch_sub(&lock->waiters, 1);
                return;
            }
        }
        
        // Block until signaled
        block_wait(&lock->waiter);
        
        // Woken up - try again with brief spin
        for (int i = 0; i < 100; i++) {
            if (atomic_load(&lock->locked) == 0) {
                if (atomic_exchange(&lock->locked, 1) == 0) {
                    atomic_fetch_sub(&lock->waiters, 1);
                    return;
                }
            }
            __builtin_ia32_pause();
        }
    }
}
 
void adaptive_unlock(adaptive_spinlock_t *lock) {
    atomic_store(&lock->locked, 0);
    
    // If waiters exist, wake one
    if (atomic_load(&lock->waiters) > 0) {
        wake_one(&lock->waiter);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13

# Thundering herd with 8 threads waiting for lock release
 
Time | CPU0 (holder) | CPU1-7 (spinners)
-----+---------------+------------------------------------------
T1   | unlock()      | All 7 see lock freed (cache invalidation)
T2   | -             | All 7 execute TAS simultaneously
T3   | -             | CPU1 wins (arbitrary), CPU2-7 get old value 1
T4   | -             | CPU2-7 all retry TAS
T5   | -             | Massive coherence traffic burst
T6   | -             | System stutters; unrelated work suffers
 
# The burst of 7 TAS operations + 6 failures + retries
# generates more traffic than the entire hold period

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// Staggered wakeup to reduce thundering herd
 
// Instead of waking all waiters simultaneously,
// wake one at a time with delays
 
void smart_unlock(adaptive_spinlock_t *lock) {
    atomic_store(&lock->locked, 0);
    
    int waiters = atomic_load(&lock->waiters);
    if (waiters > 0) {
        // Wake just ONE waiter
        // That waiter will acquire and wake the next on release
        // Forms implicit serialization
        wake_one(&lock->waiter);
    }
}
 
// For spin-only locks, can't control wakeup order
// But can use ticket locks or MCS locks for inherent ordering

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

// SMT-aware spinning (conceptual)
 
// Get sibling CPU ID for SMT pairing
int get_sibling_cpu(int cpu);
 
void smt_aware_spin(spinlock_t *lock) {
    int my_cpu = get_current_cpu();
    int sibling = get_sibling_cpu(my_cpu);
    
    while (atomic_load(&lock->locked) != 0) {
        int holder_cpu = atomic_load(&lock->holder_cpu);
        
        if (holder_cpu == sibling) {
            // Holder is our sibling hyperthread!
            // Spin briefly - they can make progress with our resources
            for (int i = 0; i < 10; i++) {
                __builtin_ia32_pause();
            }
        } else {
            // Holder is elsewhere - PAUSE (yield to sibling)
            __builtin_ia32_pause();
        }
    }
    
    // Try acquire...
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// ARM spin loop with WFE/SEV
 
void spin_lock_arm(atomic_int *lock) {
    while (1) {
        // Try to acquire
        int expected = 0;
        if (atomic_compare_exchange_strong_explicit(
                lock, &expected, 1,
                memory_order_acquire, memory_order_relaxed)) {
            return;  // Got it
        }
        
        // Wait for event (low power spin)
        __asm__ volatile("wfe" ::: "memory");
    }
}
 
void spin_unlock_arm(atomic_int *lock) {
    atomic_store_explicit(lock, 0, memory_order_release);
    
    // Send event to wake WFE waiters
    __asm__ volatile("sev" ::: "memory");
}