1# LK Kernel Blocking Primitives 2 3## Overview 4 5The LK kernel provides a comprehensive set of synchronization primitives for coordinating access to shared resources and enabling communication between threads. These primitives are built on top of the wait queue system and provide different semantics for various synchronization patterns. 6 7## Core Architecture 8 9### Wait Queues Foundation 10 11All blocking primitives in LK are built upon wait queues (`wait_queue_t`), which provide the fundamental blocking and wakeup mechanisms: 12 13- **Thread blocking**: Threads can be placed on wait queues and blocked until signaled 14- **Timeout support**: All wait operations support optional timeouts 15- **Wake semantics**: Support for waking one thread or all threads 16- **Priority preservation**: Threads maintain their priority when blocked and resumed 17 18### Locking Requirements 19 20All synchronization primitives require the global thread lock (`thread_lock`) to be held when manipulating their internal state. This ensures atomic operations and prevents race conditions during state transitions. 21 22## Synchronization Primitives 23 24### 1. Mutexes 25 26Mutexes provide exclusive access to shared resources with ownership semantics. 27 28#### Structure 29 30```c 31typedef struct mutex { 32 uint32_t magic; // Magic number for validation 33 int count; // Contention counter 34 thread_t *holder; // Currently owning thread 35 wait_queue_t wait; // Wait queue for blocked threads 36} mutex_t; 37``` 38 39#### Key Properties 40 41- **Ownership**: Only the thread that acquired the mutex can release it 42- **Non-recursive**: A thread cannot acquire the same mutex multiple times 43- **Thread context only**: Cannot be used from interrupt context 44- **Priority inheritance**: Implicit through wait queue mechanism 45 46#### API 47 48```c 49void mutex_init(mutex_t *m); 50void mutex_destroy(mutex_t *m); 51status_t mutex_acquire(mutex_t *m); // Infinite timeout 52status_t mutex_acquire_timeout(mutex_t *m, lk_time_t timeout); 53status_t mutex_release(mutex_t *m); 54bool is_mutex_held(const mutex_t *m); // Check ownership 55``` 56 57#### Usage Example 58 59```c 60mutex_t resource_lock = MUTEX_INITIAL_VALUE(resource_lock); 61 62void protected_function(void) { 63 status_t result = mutex_acquire(&resource_lock); 64 if (result == NO_ERROR) { 65 // Critical section - exclusive access to resource 66 access_shared_resource(); 67 mutex_release(&resource_lock); 68 } 69} 70``` 71 72#### C++ Wrapper 73 74```cpp 75class Mutex { 76public: 77 status_t acquire(lk_time_t timeout = INFINITE_TIME); 78 status_t release(); 79 bool is_held(); 80}; 81 82class AutoLock { 83public: 84 explicit AutoLock(mutex_t *mutex); // RAII lock acquisition 85 ~AutoLock(); // Automatic release 86 void release(); // Early release 87}; 88``` 89 90### 2. Semaphores 91 92Semaphores control access to a finite number of resources using a counter mechanism. 93 94#### Structure 95 96```c 97typedef struct semaphore { 98 int magic; // Magic number for validation 99 int count; // Available resource count 100 wait_queue_t wait; // Wait queue for blocked threads 101} semaphore_t; 102``` 103 104#### Key Properties 105 106- **Resource counting**: Tracks available resource instances 107- **No ownership**: Any thread can post/wait on a semaphore 108- **Thread context only**: Cannot be used from interrupt context 109- **FIFO ordering**: Waiting threads are woken in FIFO order 110 111#### API 112 113```c 114void sem_init(semaphore_t *sem, unsigned int value); 115void sem_destroy(semaphore_t *sem); 116status_t sem_wait(semaphore_t *sem); // Infinite timeout 117status_t sem_timedwait(semaphore_t *sem, lk_time_t timeout); 118status_t sem_trywait(semaphore_t *sem); // Non-blocking 119int sem_post(semaphore_t *sem, bool resched); // Signal availability 120``` 121 122#### Usage Example 123 124```c 125semaphore_t resource_pool; 126 127void init_resource_pool(void) { 128 sem_init(&resource_pool, 5); // 5 available resources 129} 130 131void use_resource(void) { 132 if (sem_wait(&resource_pool) == NO_ERROR) { 133 // Use one resource 134 use_shared_resource(); 135 sem_post(&resource_pool, true); // Return resource 136 } 137} 138``` 139 140#### Semaphore Semantics 141 142- **Positive count**: Resources available, wait operations succeed immediately 143- **Zero count**: No resources available, threads block on wait operations 144- **Negative count**: Represents number of waiting threads 145 146### 3. Events 147 148Events provide signaling mechanisms for thread coordination and notification. 149 150#### Structure 151 152```c 153typedef struct event { 154 int magic; // Magic number for validation 155 bool signaled; // Current signal state 156 uint flags; // Behavior flags 157 wait_queue_t wait; // Wait queue for blocked threads 158} event_t; 159``` 160 161#### Event Flags 162 163- **EVENT_FLAG_AUTOUNSIGNAL**: Automatically clear signal after waking one thread 164- **Default (no flags)**: Remain signaled until manually cleared 165 166#### Key Properties 167 168- **State-based**: Maintains signaled/unsignaled state 169- **Flexible semantics**: Support for one-shot and persistent signaling 170- **Interrupt safe**: Can be signaled from interrupt context (with resched=false) 171- **No ownership**: Any thread can signal or wait 172 173#### API 174 175```c 176void event_init(event_t *e, bool initial, uint flags); 177void event_destroy(event_t *e); 178status_t event_wait(event_t *e); // Infinite timeout 179status_t event_wait_timeout(event_t *e, lk_time_t timeout); 180status_t event_signal(event_t *e, bool reschedule); 181status_t event_unsignal(event_t *e); 182bool event_initialized(event_t *e); 183``` 184 185#### Usage Examples 186 187#### One-shot Event (Auto-unsignal) 188 189```c 190event_t completion_event; 191 192void init_completion(void) { 193 event_init(&completion_event, false, EVENT_FLAG_AUTOUNSIGNAL); 194} 195 196void wait_for_completion(void) { 197 event_wait(&completion_event); // Blocks until signaled 198} 199 200void signal_completion(void) { 201 event_signal(&completion_event, true); // Wake one waiter 202} 203``` 204 205#### Persistent Event 206 207```c 208event_t ready_event; 209 210void init_ready_state(void) { 211 event_init(&ready_event, false, 0); // No auto-unsignal 212} 213 214void wait_until_ready(void) { 215 event_wait(&ready_event); // All waiters proceed when signaled 216} 217 218void set_ready(void) { 219 event_signal(&ready_event, true); // Wake all waiters 220} 221 222void clear_ready(void) { 223 event_unsignal(&ready_event); // Manual clear 224} 225``` 226 227### 4. Ports 228 229Ports provide message-passing communication channels between threads with buffering. 230 231#### Structure 232 233```c 234typedef struct { 235 char value[PORT_PACKET_LEN]; // Packet payload 236} port_packet_t; 237 238typedef struct { 239 void *ctx; // Associated context 240 port_packet_t packet; // Message data 241} port_result_t; 242``` 243 244#### Port Types 245 246- **Write Port**: Sending side of a communication channel 247- **Read Port**: Receiving side of a communication channel 248- **Port Group**: Collection of read ports for multiplexed waiting 249 250#### Port Modes 251 252```c 253typedef enum { 254 PORT_MODE_BROADCAST, // Multiple readers can connect 255 PORT_MODE_UNICAST, // Single reader connection 256 PORT_MODE_BIG_BUFFER // Larger internal buffer 257} port_mode_t; 258``` 259 260#### Key Properties 261 262- **Named channels**: Ports are identified by name strings 263- **Buffered communication**: Internal buffering prevents blocking on send 264- **Flexible topology**: Broadcast and unicast communication patterns 265- **Context passing**: Associate arbitrary context with messages 266 267#### API 268 269```c 270void port_init(void); 271status_t port_create(const char *name, port_mode_t mode, port_t *port); 272status_t port_destroy(port_t port); 273status_t port_open(const char *name, void *ctx, port_t *port); 274status_t port_close(port_t port); 275status_t port_write(port_t port, const port_packet_t *pk, size_t count); 276status_t port_read(port_t port, port_result_t *result); 277status_t port_read_timeout(port_t port, port_result_t *result, lk_time_t timeout); 278 279// Port groups for multiplexed reading 280status_t port_group_create(port_t *group); 281status_t port_group_add(port_t group, port_t port); 282status_t port_group_remove(port_t group, port_t port); 283status_t port_group_read(port_t group, port_result_t *result); 284status_t port_group_read_timeout(port_t group, port_result_t *result, lk_time_t timeout); 285``` 286 287#### Usage Example 288 289```c 290// Producer thread 291void producer_thread(void *arg) { 292 port_t write_port; 293 port_create("data_channel", PORT_MODE_BROADCAST, &write_port); 294 295 port_packet_t packet; 296 // Fill packet with data 297 fill_packet_data(&packet); 298 299 port_write(write_port, &packet, 1); 300 port_destroy(write_port); 301} 302 303// Consumer thread 304void consumer_thread(void *arg) { 305 port_t read_port; 306 port_open("data_channel", NULL, &read_port); 307 308 port_result_t result; 309 if (port_read_timeout(read_port, &result, 1000) == NO_ERROR) { 310 // Process received data 311 process_packet_data(&result.packet); 312 } 313 314 port_close(read_port); 315} 316``` 317 318### 5. Spinlocks 319 320Spinlocks provide lightweight mutual exclusion for short critical sections. 321 322#### Structure 323 324Architecture-specific spinlock implementation with common interface: 325 326```c 327typedef arch_spin_lock_t spin_lock_t; 328typedef arch_spin_lock_saved_state_t spin_lock_saved_state_t; 329``` 330 331#### Key Properties 332 333- **Non-blocking**: Busy-wait instead of sleeping 334- **Interrupt safe**: Can be used from interrupt context 335- **Short critical sections**: Designed for brief atomic operations 336- **No recursion**: Cannot be acquired recursively 337- **Priority inversion risk**: Can cause priority inversion 338 339#### API 340 341```c 342void spin_lock_init(spin_lock_t *lock); 343void spin_lock(spin_lock_t *lock); // Assumes interrupts disabled 344int spin_trylock(spin_lock_t *lock); // Non-blocking attempt 345void spin_unlock(spin_lock_t *lock); 346bool spin_lock_held(spin_lock_t *lock); 347 348// IRQ-safe variants 349void spin_lock_irqsave(spin_lock_t *lock, spin_lock_saved_state_t *state); 350void spin_unlock_irqrestore(spin_lock_t *lock, spin_lock_saved_state_t state); 351``` 352 353#### Usage Example 354 355```c 356spin_lock_t hardware_lock = SPIN_LOCK_INITIAL_VALUE; 357 358void access_hardware_register(void) { 359 spin_lock_saved_state_t state; 360 spin_lock_irqsave(&hardware_lock, &state); 361 362 // Brief critical section 363 write_hardware_register(value); 364 365 spin_unlock_irqrestore(&hardware_lock, state); 366} 367``` 368 369#### C++ Wrapper 370 371```cpp 372class SpinLock { 373public: 374 void lock(); 375 int trylock(); 376 void unlock(); 377 bool is_held(); 378 void lock_irqsave(spin_lock_saved_state_t *state); 379 void unlock_irqrestore(spin_lock_saved_state_t state); 380}; 381 382class AutoSpinLock { 383public: 384 explicit AutoSpinLock(spin_lock_t *lock); // RAII with IRQ save 385 ~AutoSpinLock(); 386 void release(); 387}; 388 389class AutoSpinLockNoIrqSave { 390public: 391 explicit AutoSpinLockNoIrqSave(spin_lock_t *lock); // RAII without IRQ save 392 ~AutoSpinLockNoIrqSave(); 393 void release(); 394}; 395``` 396 397## Advanced Topics 398 399### Wait Queues 400 401The foundation primitive underlying all blocking synchronization: 402 403#### API 404 405```c 406void wait_queue_init(wait_queue_t *wait); 407void wait_queue_destroy(wait_queue_t *wait, bool reschedule); 408status_t wait_queue_block(wait_queue_t *wait, lk_time_t timeout); 409int wait_queue_wake_one(wait_queue_t *wait, bool reschedule, status_t error); 410int wait_queue_wake_all(wait_queue_t *wait, bool reschedule, status_t error); 411status_t thread_unblock_from_wait_queue(thread_t *t, status_t error); 412``` 413 414#### Timeout Handling 415 416- **INFINITE_TIME**: Block indefinitely until signaled 417- **0**: Return immediately with ERR_TIMED_OUT if would block 418- **Positive values**: Block for specified milliseconds, return ERR_TIMED_OUT on expiration 419 420### Priority Inheritance 421 422While not explicitly implemented, the LK synchronization primitives provide implicit priority inheritance through the wait queue mechanism: 423 424- **FIFO ordering**: Threads are generally woken in the order they were blocked 425- **Priority-based scheduling**: High-priority threads are scheduled immediately when unblocked 426- **Head insertion**: Newly unblocked threads are inserted at the head of their priority run queue 427 428### Error Handling 429 430#### Common Error Codes 431 432- **NO_ERROR**: Operation successful 433- **ERR_TIMED_OUT**: Operation timed out 434- **ERR_NOT_READY**: Resource not available (try operations) 435- **ERR_INVALID_ARGS**: Invalid parameters 436- **ERR_OBJECT_DESTROYED**: Primitive was destroyed while waiting 437- **ERR_NOT_ENOUGH_BUFFER**: Insufficient buffer space (ports) 438- **ERR_THREAD_DETACHED**: Thread was detached (join operations) 439 440#### Panic Conditions 441 442Debug builds include assertions that will panic on: 443 444- **Double acquisition**: Attempting to acquire a mutex already owned 445- **Invalid release**: Releasing a mutex not owned by current thread 446- **Magic number corruption**: Corrupted primitive structures 447- **Invalid state transitions**: Inconsistent internal state 448 449### SMP Considerations 450 451#### CPU Wakeup 452 453When threads are unblocked, the scheduler automatically handles CPU wakeup: 454 455- **Pinned threads**: Wake the specific CPU where the thread is pinned 456- **Unpinned threads**: Wake all CPUs except the local one 457- **Load balancing**: Distribution across available CPUs 458 459#### Memory Ordering 460 461- **Architecture barriers**: Spinlocks include appropriate memory barriers 462- **Cache coherency**: Hardware ensures cache coherence for shared data 463- **Atomic operations**: Underlying atomic primitives ensure consistency 464 465## Best Practices 466 467### Choosing the Right Primitive 468 4691. **Mutexes**: For exclusive access to shared resources with ownership 4702. **Semaphores**: For counting resources or limiting concurrency 4713. **Events**: For signaling and notification between threads 4724. **Ports**: For message passing and producer-consumer patterns 4735. **Spinlocks**: For very short critical sections or interrupt contexts 474 475### Performance Considerations 476 477#### Mutex vs Spinlock Trade-offs 478 479**Use Mutexes when:** 480 481- Critical sections may be long 482- Thread context is available 483- Resource contention is possible 484- Priority inheritance is needed 485 486**Use Spinlocks when:** 487 488- Critical sections are very short (< 100 cycles) 489- Interrupt context or high-priority threads 490- Low contention expected 491- Immediate response required 492 493#### Avoiding Priority Inversion 494 495- **Keep critical sections short**: Minimize time holding locks 496- **Consistent lock ordering**: Prevent deadlock with multiple locks 497- **Avoid nested locking**: Reduce complexity and deadlock risk 498- **Use appropriate primitives**: Match primitive to use case 499 500### Common Patterns 501 502#### Producer-Consumer 503 504```c 505// Using semaphores 506semaphore_t empty_slots, full_slots; 507mutex_t buffer_lock; 508 509void producer(void) { 510 sem_wait(&empty_slots); // Wait for space 511 mutex_acquire(&buffer_lock); // Protect buffer 512 add_to_buffer(data); 513 mutex_release(&buffer_lock); 514 sem_post(&full_slots, true); // Signal data available 515} 516 517void consumer(void) { 518 sem_wait(&full_slots); // Wait for data 519 mutex_acquire(&buffer_lock); // Protect buffer 520 data = remove_from_buffer(); 521 mutex_release(&buffer_lock); 522 sem_post(&empty_slots, true); // Signal space available 523} 524``` 525 526#### Event Notification 527 528```c 529// Using events for completion notification 530event_t work_complete; 531 532void worker_thread(void) { 533 // Perform work 534 do_work(); 535 536 // Signal completion 537 event_signal(&work_complete, true); 538} 539 540void coordinator_thread(void) { 541 // Start work 542 start_work(); 543 544 // Wait for completion 545 event_wait(&work_complete); 546 547 // Process results 548 process_results(); 549} 550``` 551 552#### Resource Pool Management 553 554```c 555// Using semaphores for resource pool 556semaphore_t resource_pool; 557mutex_t pool_lock; 558resource_t *resources[MAX_RESOURCES]; 559 560void init_pool(void) { 561 sem_init(&resource_pool, MAX_RESOURCES); 562 mutex_init(&pool_lock); 563 // Initialize resource array 564} 565 566resource_t *acquire_resource(void) { 567 if (sem_wait(&resource_pool) == NO_ERROR) { 568 mutex_acquire(&pool_lock); 569 resource_t *res = find_free_resource(); 570 mark_resource_used(res); 571 mutex_release(&pool_lock); 572 return res; 573 } 574 return NULL; 575} 576 577void release_resource(resource_t *res) { 578 mutex_acquire(&pool_lock); 579 mark_resource_free(res); 580 mutex_release(&pool_lock); 581 sem_post(&resource_pool, true); 582} 583``` 584 585## Integration with Threading System 586 587### Lock Context Requirements 588 589All blocking primitives (except spinlocks) require: 590 591- **Thread context**: Cannot be used from interrupt handlers 592- **Interrupts enabled**: Should not be called with interrupts disabled 593- **No spinlocks held**: Deadlock risk if thread spinlocks are held 594 595### Scheduler Integration 596 597- **Automatic blocking**: Primitives automatically use `thread_block()` 598- **Priority preservation**: Blocked threads maintain their priority 599- **Fair scheduling**: FIFO ordering within priority levels 600- **Efficient wakeup**: Minimal overhead for thread state transitions 601 602### Memory Management 603 604- **Static initialization**: All primitives support compile-time initialization 605- **Dynamic allocation**: Runtime initialization for dynamically allocated primitives 606- **Cleanup requirements**: Proper destruction prevents resource leaks 607- **Magic number validation**: Debug builds validate primitive integrity 608 609This comprehensive set of blocking primitives provides the foundation for safe, efficient multi-threaded programming in the LK kernel, supporting everything from simple mutual exclusion to complex communication patterns. 610