Master Linux Kernel Sync with struct completion

The struct completion in the Linux kernel is a synchronization mechanism used to signal the completion of an asynchronous event. It allows one or more threads to wait for a specific event to occur, and another thread to notify them when the event is done. Below is a detailed explanation of its structure, purpose, and usage:

1. Structure Definition

The struct completion is defined as:

struct completion {
    unsigned int done;        // Counter indicating completion status
    wait_queue_head_t wait;   // Wait queue for blocking processes
};        

Key Fields:

• done:

A counter that tracks whether the completion event has occurred.

Initialized to 0 (event not completed). When complete() is called, done is incremented.

If done > 0, waiting processes are allowed to proceed.

• wait:

A wait queue that holds processes (tasks) that are blocked waiting for the completion event.

When a process calls wait_for_completion(), it is added to this queue and enters an asleep state until the event is signaled.

2. Purpose and Use Cases

The struct completion is used to:

• Synchronize asynchronous operations (e.g., I/O, DMA, or hardware interrupts).
• Signal completion of an event to waiting processes.
• Avoid busy waiting, ensuring processes only wake up when the event is ready.

Common Scenarios:

• Device Drivers: Waiting for hardware operations to complete (e.g., SPI transfers, disk I/O).
• Multi-threaded Kernels: Coordinating between kernel threads (e.g., one thread performs a task while others wait).
• Interrupt Handling: Notifying a waiting process that an interrupt has occurred.

3. Key Operations

Initialization:

• Static Initialization:

DECLARE_COMPLETION(my_completion); // Macro to declare and initialize        

• Dynamic Initialization:

struct completion my_completion; 
init_completion(&my_completion); // Explicitly initialize 'done' to 0        

Waiting for Completion:

• Basic Wait:

wait_for_completion(&my_completion); // Blocks until 'done' > 0        

Variants:

• wait_for_completion_timeout(): Waits with a timeout.
• wait_for_completion_interruptible(): Allows the wait to be interrupted by signals.
• wait_for_completion_killable(): Allows interruption by fatal signals (e.g., SIGKILL).

Signaling Completion:

• Single Wakeup:

complete(&my_completion); // Increments 'done' and wakes one waiting process        

• All Wakeups:

complete_all(&my_completion); // Wakes all waiting processes (since Linux 2.5)        

4. How It Works

• Initialization:

The done counter is set to 0, and the wait queue is initialized to empty.

• Waiting:

A process calls wait_for_completion(), which:Checks if done > 0. If yes, proceeds.

Otherwise, adds itself to the wait queue and blocks (sleeps).

• Signaling:

Another thread (e.g., an interrupt handler or worker thread) calls complete() or complete_all(), which:

Increments done.

Wakes up waiting processes (one or all, depending on the function).

• Resuming Execution:

Woken processes check done and proceed if the event is complete.

5. Key Features

• Order-Independent Operation:

A process can call wait_for_completion() before the event is signaled. The complete() call will still wake it up.

If complete() is called before any process starts waiting, the next wait_for_completion() will proceed immediately.

• Reusability:

After complete(), the done counter remains non-zero. Subsequent calls to wait_for_completion() will not block unless init_completion() is called again to reset it.

To reuse the completion, you must reinitialize it with init_completion().

• Safety:

Prevents race conditions by managing the done counter and wait queue atomically.

6. Example Usage

#include <linux/completion.h>

struct completion my_completion;

// Thread A (e.g., worker thread):
void worker_thread(void) {
    // Perform some task...
    do_work();
    
    // Signal completion to waiting threads
    complete(&my_completion);
}

// Thread B (e.g., main thread):
void main_thread(void) {
    init_completion(&my_completion);
    
    // Start the worker thread...
    start_worker_thread();
    
    // Wait for the worker to finish
    wait_for_completion(&my_completion);
    
    // Proceed after completion
    printk("Worker thread has finished!");
}
        

7. Comparison with Other Synchronization Mechanisms

8. Common Pitfalls

1. Forgetting to Initialize:Failing to call init_completion() or DECLARE_COMPLETION() leads to undefined behavior.
2. Reusing Without Reinitialization:After complete(), wait_for_completion() will not block again unless init_completion() is called.
3. Deadlocks:Avoid waiting for a completion in an interrupt context (which cannot sleep).

Conclusion

The struct completion is a lightweight, efficient mechanism for asynchronous event synchronization in the Linux kernel. By combining a counter (done) and a wait queue (wait), it allows processes to wait for specific events and ensures orderly execution without busy waiting. It is widely used in device drivers, kernel threads, and interrupt handlers to manage dependencies between asynchronous operations.

More for UEFI background readers:

UEFI don't have sleep, so it blocks the current execution flow until an event is signaled.

// Create an event  
EFI_STATUS CreateEvent(  
  IN UINT32                   Type,       // Event type (e.g., timer, I/O)  
  IN UINT32                   NotifyTpl,  // Task priority level  
  IN EFI_EVENT_NOTIFY        NotifyFunction, // Optional callback  
  IN VOID                    *NotifyContext,  
  OUT EFI_EVENT              *Event  
);  

// Wait for one or more events to trigger  
EFI_STATUS WaitForEvent(  
  IN UINTN                   NumberOfEvents,  
  IN EFI_EVENT              *EventList,  
  OUT UINTN                 *Index  
);  

// Signal (trigger) an event  
EFI_STATUS SignalEvent(  
  IN EFI_EVENT              Event  
);