# The Linux Kernel/Multitasking

* multitasking
* threads or tasks
* synchronization
* Scheduler
* interrupts core
* CPU specific
Linux kernel is a preemptive multitasking operating system. As a multitasking OS, it allows multiple processes to share processors (CPUs) and other system resources. Each CPU executes a single task at a time. However, multitasking allows each processor to switch between tasks that are being executed without having to wait for each task to finish. For that, the kernel can, at any time, temporarily interrupt a task being carried out by the processor, and replace it by another task that can be new or a previously suspended one. The operation involving the swapping of the running task is called context switch.

## Threads or tasks

In Linux kernel "thread" and "task" are almost synonyms.
💾 History: Till 2.6.39, kernel mode has only one thread protected by big kernel lock.
⚲ API
    linux/sched.h$_{inc}$ - the main scheduler API
       task_struct$_{id}$
    arch/x86/include/asm/current.h$_{src}$
       current$_{id}$ and get_current$_{id}$ return current task_struct$_{id}$
    uapi/linux/taskstats.h$_{inc}$ per-task statistics
    linux/thread_info.h$_{inc}$
       current_thread_info$_{id}$ returns thread_info$_{id}$
    linux/sched/task.h$_{inc}$ - interface between the scheduler and various task lifetime (fork/exit) functionality
    linux/kthread.h$_{inc}$ - simple interface for creating and stopping kernel threads without mess.
       kthread_run$_{id}$ creates and wakes a thread
       kthread_create$_{id}$
⚙️ Internals
    kthread_run$_{id}$ ↯ hierarchy:
    kernel/kthread.c$_{src}$
       kthreadd$_{id}$ – parent kernel thread and the creator of all other kernel threads. Dequeues kthread_create_info$_{id}$ from kthread_create_list$_{id}$.
          create_kthread$_{id}$
             kernel_thread$_{id}$
             kthread$_{id}$ – invokes threadfn$_{id}$
       __kthread_create_on_node$_{id}$ – equeues kthread_create_info$_{id}$ into kthread_create_list$_{id}$
    kernel/fork.c$_{src}$
       kernel_thread$_{id}$
          kernel_clone$_{id}$

## Scheduler

The scheduler is the part of the operating system that decides which process runs at a certain point in time. It usually has the ability to pause a running process, move it to the back of the running queue and start a new process.
Active processes are placed in an array called a run queue, or runqueue - rq$_{id}$. The run queue may contain priority values for each process, which will be used by the scheduler to determine which process to run next. To ensure each program has a fair share of resources, each one is run for some time period (quantum) before it is paused and placed back into the run queue. When a program is stopped to let another run, the program with the highest priority in the run queue is then allowed to execute. Processes are also removed from the run queue when they ask to sleep, are waiting on a resource to become available, or have been terminated.
Linux uses the Completely Fair Scheduler (CFS), the first implementation of a fair queuing process scheduler widely used in a general-purpose operating system. CFS uses a well-studied, classic scheduling algorithm called "fair queuing" originally invented for packet networks. The CFS scheduler has a scheduling complexity of O(log N), where N is the number of tasks in the runqueue. Choosing a task can be done in constant time, but reinserting a task after it has run requires O(log N) operations, because the run queue is implemented as a red–black tree.
In contrast to the previous O(1) scheduler, the CFS scheduler implementation is not based on run queues. Instead, a red-black tree implements a "timeline" of future task execution. Additionally, the scheduler uses nanosecond granularity accounting, the atomic units by which an individual process' share of the CPU was allocated (thus making redundant the previous notion of timeslices). This precise knowledge also means that no specific heuristics are required to determine the interactivity of a process, for example.
Like the old O(1) scheduler, CFS uses a concept called "sleeper fairness", which considers sleeping or waiting tasks equivalent to those on the runqueue. This means that interactive tasks which spend most of their time waiting for user input or other events get a comparable share of CPU time when they need it.
The data structure used for the scheduling algorithm is a red-black tree in which the nodes are scheduler specific structures, entitled sched_entity$_{id}$. These are derived from the general task_struct process descriptor, with added scheduler elements. These nodes are indexed by processor execution time in nanoseconds. A maximum execution time is also calculated for each process. This time is based upon the idea that an "ideal processor" would equally share processing power amongst all processes. Thus, the maximum execution time is the time the process has been waiting to run, divided by the total number of processes, or in other words, the maximum execution time is the time the process would have expected to run on an "ideal processor".
When the scheduler is invoked to run a new processes, the operation of the scheduler is as follows:
* The left most node of the scheduling tree is chosen (as it will have the lowest spent execution time), and sent for execution.
* If the process simply completes execution, it is removed from the system and scheduling tree.
* If the process reaches its maximum execution time or is otherwise stopped (voluntarily or via interrupt) it is reinserted into the scheduling tree based on its new spent execution time.
* The new left-most node will then be selected from the tree, repeating the iteration.
If the process spends a lot of its time sleeping, then its spent time value is low and it automatically gets the priority boost when it finally needs it. Hence such tasks do not get less processor time than the tasks that are constantly running.
An alternative to CFS is the Brain Fuck Scheduler (BFS) created by Con Kolivas. The objective of BFS, compared to other schedulers, is to provide a scheduler with a simpler algorithm, that does not require adjustment of heuristics or tuning parameters to tailor performance to a specific type of computation workload.
Con Kolivas also maintains another alternative to CFS, the MuQSS scheduler.
The Linux kernel contains different scheduler classes (or policies). The Completely Fair Scheduler used nowadays by default is SCHED_NORMAL$_{id}$ scheduler class aka SCHED_OTHER. The kernel also contains two additional classes SCHED_BATCH$_{id}$ and SCHED_IDLE$_{id}$, and another two real-time scheduling classes named SCHED_FIFO$_{id}$ (realtime first-in-first-out) and SCHED_RR$_{id}$ (realtime round-robin), with a third realtime scheduling policy known as SCHED_DEADLINE$_{id}$ that implements the earliest deadline first algorithm (EDF) added later. Any realtime scheduler class takes precedence over any of the "normal" —i.e. non realtime— classes. The scheduler class is selected and configured through the man 2 sched_setscheduler ↪ do_sched_setscheduler$_{id}$ system call.
Properly balancing latency, throughput, and fairness in schedulers is an open problem.
⚲ API
    man 1 renice – priority of running processes
    man 1 nice – run a program with modified scheduling priority
    man 1 chrt – manipulate the real-time attributes of a process
       man 2 sched_getattr ↪ sys_sched_getattr$_{id}$ – get scheduling policy and attributes
    linux/sched.h$_{inc}$ – the main scheduler API
       schedule$_{id}$
    man 2 getpriority, man 2 setpriority
    man 2 sched_setscheduler, man 2 sched_getscheduler
⚙️ Internals
    sched_init$_{id}$ is called from start_kernel$_{id}$
    __schedule$_{id}$ is the main scheduler function.
    runqueues$_{id}$, this_rq$_{id}$
    kernel/sched$_{src}$
    kernel/sched/core.c$_{src}$
    kernel/sched/fair.c$_{src}$ implements SCHED_NORMAL$_{id}$, SCHED_BATCH$_{id}$, SCHED_IDLE$_{id}$
    sched_setscheduler$_{id}$, sched_getscheduler$_{id}$
    task_struct$_{id}$::rt_priority$_{id}$ and other members with less unique identifiers
🛠️ Utilities
    man 1 pidstat]
    man 1 pcp-pidstat
    man 1 perf-sched
    Understanding Scheduling Behavior with SchedViz
📖 References
    man 7 sched
    Scheduling$_{doc}$
    Delaying and scheduling routines$_{doc}$
    CFS
       Completely Fair Scheduler$_{doc}$
       CFS Bandwidth Control$_{doc}$
       Tuning the task scheduler
       stop using CPU limits on Kubernetes
    Completely fair scheduler LWN
    Deadline Task Scheduler$_{doc}$
    sched$_{ltp}$
    sched_setparam$_{ltp}$
    sched_getscheduler$_{ltp}$
    sched_setscheduler$_{ltp}$
📚 Further reading about the scheduler
    Scheduler tracing
    bcc/ebpf CPU and scheduler tools

### Preemption

Preemption refers to the ability of the system to interrupt a running task to switch to another task. This is essential for ensuring that high-priority tasks receive the necessary CPU time and for improving the system's responsiveness. In Linux, preemption models define how and when the kernel can preempt tasks. Different models offer varying trade-offs between system responsiveness and throughput.
📖 References
    kernel/Kconfig.preempt$_{src}$
       CONFIG_PREEMPT_NONE$_{id}$ – no forced preemption for servers
       CONFIG_PREEMPT_VOLUNTARY$_{id}$ – voluntary preemption for desktops
       CONFIG_PREEMPT$_{id}$ – preemptible except for critical sections for low-latency desktops
       CONFIG_PREEMPT_RT$_{id}$ – real-time preemption for highly responsive applications
       CONFIG_PREEMPT_DYNAMIC$_{id}$, see /sys/kernel/debug/sched/preempt

### Wait queues

A wait queue in the kernel is a data structure that allows one or more processes to wait (sleep) until something of interest happens. They are used throughout the kernel to wait for available memory, I/O completion, message arrival, and many other things. In the early days of Linux, a wait queue was a simple list of waiting processes, but various scalability problems (including the thundering herd problem) have led to the addition of a fair amount of complexity since then.
⚲ API
linux/wait.h$_{inc}$
wait_queue_head$_{id}$ consists of double linked list of wait_queue_entry$_{id}$ and a spinlock.
Waiting for simple events:
    Use one of two methods for wait_queue_head$_{id}$ initialization:
       init_waitqueue_head$_{id}$ initializes wait_queue_head$_{id}$ in function context
       DECLARE_WAIT_QUEUE_HEAD$_{id}$ - actually defines wait_queue_head$_{id}$ in global context
    Wait alternatives:
       wait_event_interruptible$_{id}$ - preferable wait
       wait_event_interruptible_timeout$_{id}$
       wait_event$_{id}$ - uninterruptible wait. Can cause deadlock ⚠
    wake_up$_{id}$ etc
👁 For example usage see references to unique suspend_queue$_{id}$.
Explicit use of add_wait_queue instead of simple wait_event for complex cases:
    DECLARE_WAITQUEUE$_{id}$ actually defines wait_queue_entry with default_wake_function$_{id}$
    add_wait_queue$_{id}$ inserts process in the first position of a wait queue
    remove_wait_queue$_{id}$
⚙️ Internals
    ___wait_event$_{id}$
    __add_wait_queue$_{id}$
    __wake_up_common$_{id}$, try_to_wake_up$_{id}$
    kernel/sched/wait.c$_{src}$
📖 References
    Wait queues and Wake events$_{doc}$
    Handling wait queues

### Real-time
#### RT preemption

The Linux Foundation's Real-Time Linux (RTL) collaborative project is focused on improving the real-time capabilities of Linux and advancing the adoption of real-time Linux in various industries, including aerospace, automotive, robotics, and telecommunications.
Parameter CONFIG_PREEMPT_RT$_{id}$ enables real-time preemption.

#### RT scheduling policies

Scheduling policies for RT:
    SCHED_FIFO$_{id}$, SCHED_RR$_{id}$
       implemented in kernel/sched/rt.c$_{src}$
    SCHED_DEADLINE
       implemented in kernel/sched/deadline.c$_{src}$
API:
    man 1 chrt – manipulate the real-time attributes of a process
    man 2 sched_rr_get_interval – get the SCHED_RR interval for the named process
    man 2 sched_setscheduler, sched_getscheduler – set and get scheduling policy/parameters
    man 2 sched_get_priority_min, sched_get_priority_max – get static priority range

#### Testing RT capabilities

The testing process for Real-Time Linux typically involves several key aspects. First and foremost, it is crucial to verify the accuracy and stability of the system's timekeeping mechanisms. Precise time management is fundamental to real-time applications, and any inaccuracies can lead to timing errors and compromise the system's real-time capabilities.
Another essential aspect of testing is evaluating the system's scheduling algorithms. Real-Time Linux employs advanced scheduling policies to prioritize critical tasks and ensure their timely execution. Testing the scheduler involves assessing its ability to allocate resources efficiently, handle task prioritization correctly, and prevent resource contention or priority inversion scenarios.
Furthermore, latency measurement is a critical part of Real-Time Linux testing. Latency refers to the time delay between the occurrence of an event and the system's response to it. In real-time applications, minimizing latency is crucial to achieving timely and predictable behavior. Testing latency involves measuring the time it takes for the system to respond to various stimuli and identifying any sources of delay or unpredictability.
Additionally, stress testing plays a significant role in assessing the system's robustness under heavy workloads. It involves subjecting the Real-Time Linux system to high levels of concurrent activities, intense computational loads, and input/output operations to evaluate its performance, responsiveness, and stability. Stress testing helps identify potential bottlenecks, resource limitations, or issues that might degrade the real-time behavior of the system.
    RTLA – The realtime Linux analysis tool:
       rtla timerlat$_{doc}$ – CLI for the kernel's timerlat tracer$_{doc}$
       rtla osnoise$_{doc}$ – CLI for the kernel's osnoise tracer$_{doc}$.
          Kernel function run_osnoise$_{id}$ measures time with function trace_clock_local$_{id}$ in loop.
       rtla hwnoise$_{doc}$ – CLI for the osnoise tracer$_{doc}$ with interrupts disabled
          Implementation: tools/tracing/rtla$_{src}$ and kernel/trace/trace_osnoise.c$_{src}$
       Linux scheduling latency debug and analysis
    RT-Tests, source
       cyclictest
    some RT-Tests man pages:
       cyclictest – measures man 2 clock_nanosleep or man 2 nanosleep delay
       hwlatdetect – CLI for /sys/kernel/tracing/hwlat_detector$_{doc}$ / kernel/trace/trace_hwlat.c$_{src}$. Kernel function kthread_fn$_{id}$ measures time delays with function trace_clock_local$_{id}$ in loop.
       oslat – measures delay with RDTSC in busy loop
       hackbench – scheduler benchmark/stress test
    RT Tracing Tools with eBPF
    realtime$_{ltp}$
Further reading about real-time Linux:
    linux/spinlock_rt.h$_{inc}$ used via linux/spinlock_types.h$_{inc}$
    linux/rtmutex.h$_{inc}$ used via linux/mutex_types.h$_{inc}$
    linux/rwbase_rt.h$_{inc}$ used via linux/rwlock_types.h$_{inc}$
    Introduction to Real-Time Linux: Unleashing Deterministic Computing
    Power Management and Scheduling in the Linux Kernel (OSPM)
    the Real-Time Linux wiki
       CPU partitioning and isolation
    Realtime@LWN
    linux-stable-rt.git
    linux-rt-devel.git
    Realtime kernel patchset, Arch Linux
    https://www.kernel.org/pub/linux/kernel/projects/rt/ - RT patches for upstream kernel
    High Precision Event Timer (HPET)
    Demystifying the Real-Time Linux Scheduling Latency
    Real-time kernel tuning in RHEL 9
    Linux subsystems related to real-time
       Linux kernel scheduling and preemption
       Interrupts
       Deferred works
       Non-maskable interrupt handler (NMI)
       System management interrupt (SMI)
       man 7 sched
    latency @ LKML
    PREEMPT_RT @ LKML
    QA about PREEMP_RT, LPC'23, State of the onion, pdf
💾 Historical
The PREEMPT_RT patch has been partially merged into the mainline Linux kernel, starting from version 5.15.

## Synchronization

Thread synchronization is defined as a mechanism which ensures that two or more concurrent processes or threads do not simultaneously execute some particular program segment known as mutual exclusion (mutex). When one thread starts executing the critical section (serialized segment of the program) the other thread should wait until the first thread finishes. If proper synchronization techniques are not applied, it may cause a race condition where, the values of variables may be unpredictable and vary depending on the timings of context switches of the processes or threads.

### User space synchronization
#### POSIX Timers

⚲ APIs
    man 2 timer_create – creates a POSIX timer
    man 2 timer_settime – starts or modifies a timer
    man 2 timer_gettime – retrieves the remaining time of a timer
    man 2 timer_delete – deletes a POSIX timer
    man 2 clock_nanosleep – suspends execution for a specified time
⚙️ Internals
    linux/posix-timers.h$_{inc}$
    kernel/posix-timers.c$_{src}$
    kernel/time/itimer.c$_{src}$
    kernel/time/posix-timers.c$_{src}$
    kernel/time/posix-cpu-timers.c$_{src}$
       posix_cpu_timer_set$_{id}$ – function setting up CPU timers

#### Futex

A man 2 futex ↪ do_futex$_{id}$ (short for "fast userspace mutex") is a kernel system call that programmers can use to implement basic locking, or as a building block for higher-level locking abstractions such as semaphores and POSIX mutexes or condition variables.
A futex consists of a kernelspace wait queue that is attached to an aligned integer in userspace. Multiple processes or threads operate on the integer entirely in userspace (using atomic operations to avoid interfering with one another), and only resort to relatively expensive system calls to request operations on the wait queue (for example to wake up waiting processes, or to put the current process on the wait queue). A properly programmed futex-based lock will not use system calls except when the lock is contended; since most operations do not require arbitration between processes, this will not happen in most cases.
The basic operations of futexes are based on only two central operations futex_wait$_{id}$ and futex_wake$_{id}$ though implementation has a more operations for more specialized cases.
    WAIT (addr, val) checks if the value stored at the address addr is val, and if it is puts the current thread to sleep.
    WAKE (addr, val) wakes up val number of threads waiting on the address addr.
⚲ API
    uapi/linux/futex.h$_{inc}$
    linux/futex.h$_{inc}$
⚙️ Internals: kernel/futex.c$_{src}$
📖 References
    Futex
    man 7 futex
    Futex API reference$_{doc}$
    futex$_{ltp}$

#### File locking

⚲ API: man 2 flock

#### Semaphore

💾 History: Semaphore is part of System V IPC man 7 sysvipc
⚲ API
    man 2 semget
    man 2 semctl
    man 2 semget
⚙️ Internals: ipc/sem.c$_{src}$

### Kernel space synchronization

For kernel mode synchronization Linux provides three categories of locking primitives: sleeping, per CPU local locks and spinning locks.

#### Read-Copy-Update

Common mechanism to solve the readers–writers problem is the read-copy-update (RCU) algorithm. Read-copy-update implements a kind of mutual exclusion that is wait-free (non-blocking) for readers, allowing extremely low overhead. However, RCU updates can be expensive, as they must leave the old versions of the data structure in place to accommodate pre-existing readers.
💾 History: RCU was added to Linux in October 2002. Since then, there are thousandths uses of the RCU API within the kernel including the networking protocol stacks and the memory-management system. The implementation of RCU in version 2.6 of the Linux kernel is among the better-known RCU implementations.
⚲ The core API in linux/rcupdate.h$_{inc}$ is quite small:
    rcu_read_lock$_{id}$ marks an RCU-protected data structure so that it won't be reclaimed for the full duration of that critical section.
    rcu_read_unlock$_{id}$ is used by a reader to inform the reclaimer that the reader is exiting an RCU read-side critical section. Note that RCU read-side critical sections may be nested and/or overlapping.
    synchronize_rcu$_{id}$ blocks until all pre-existing RCU read-side critical sections on all CPUs have completed. Note that synchronize_rcu will not necessarily wait for any subsequent RCU read-side critical sections to complete.
For example, consider the following sequence of events:
| | CPU 0 | CPU 1 | CPU 2 |
| 1. | rcu_read_lock | | |
| 2. | | enters synchronize_rcu | |
| 3. | | | rcu_read_lock |
| 4. | rcu_read_unlock | | |
| 5. | | exits synchronize_rcu | |
| 6. | | | rcu_read_unlock |
    Since synchronize_rcu is the API that must figure out when readers are done, its implementation is key to RCU. For RCU to be useful in all but the most read-intensive situations, synchronize_rcu's overhead must also be quite small.
    Alternatively, instead of blocking, synchronize_rcu may register a callback to be invoked after all ongoing RCU read-side critical sections have completed. This callback variant is called call_rcu$_{id}$ in the Linux kernel.
    rcu_assign_pointer$_{id}$ - The updater uses this function to assign a new value to an RCU-protected pointer, in order to safely communicate the change in value from the updater to the reader. This function returns the new value, and also executes any memory barrier instructions required for a given CPU architecture. Perhaps more importantly, it serves to document which pointers are protected by RCU.
    rcu_dereference$_{id}$ - The reader uses this function to fetch an RCU-protected pointer, which returns a value that may then be safely dereferenced. It also executes any directives required by the compiler or the CPU, for example, a volatile cast for gcc, a memory_order_consume load for C/C++11 or the memory-barrier instruction required by the old DEC Alpha CPU. The value returned by rcu_dereference is valid only within the enclosing RCU read-side critical section. As with rcu_assign_pointer, an important function of rcu_dereference is to document which pointers are protected by RCU.
The RCU infrastructure observes the time sequence of rcu_read_lock, rcu_read_unlock, synchronize_rcu, and call_rcu invocations in order to determine when (1) synchronize_rcu invocations may return to their callers and (2) call_rcu callbacks may be invoked. Efficient implementations of the RCU infrastructure make heavy use of batching in order to amortize their overhead over many uses of the corresponding APIs.
⚲ API
    rcu_nocbs – no-callback CPUs
⚙️ Internals
    kernel/rcu$_{src}$
📖 References
    Avoiding Locks: Read Copy Update$_{doc}$
    RCU concepts$_{doc}$
    RCU initialization

#### Sleeping locks
##### Mutexes

⚲ API
    linux/mutex.h$_{inc}$
    linux/completion.h$_{inc}$
    mutex$_{id}$ has owner and usage constrains, more easy to debug then semaphore
       rt_mutex$_{id}$ blocking mutual exclusion locks with priority inheritance (PI) support
       ww_mutex$_{id}$ Wound/Wait mutexes: blocking mutual exclusion locks with deadlock avoidance
    rw_semaphore$_{id}$ readers–writer semaphores
    percpu_rw_semaphore$_{id}$
    completion$_{id}$ - use completion for synchronization task with ISR and task or two tasks.
       wait_for_completion$_{id}$
       complete$_{id}$
💾 Historical
    semaphore$_{id}$ - use mutex instead semaphore if possible
    linux/semaphore.h$_{inc}$
    linux/rwsem.h$_{inc}$
📖 References
    Completions - “wait for completion” barrier APIs$_{doc}$
    Mutex API reference$_{doc}$
    LWN: completion events

#### per CPU local lock

    local_lock$_{id}$, preempt_disable$_{id}$
    local_lock_irqsave$_{id}$, local_irq_save$_{id}$
    etc
On normal preemptible kernel local_lock calls preempt_disable$_{id}$. On RT preemptible kernel local_lock calls migrate_disable$_{id}$ and spin_lock$_{id}$. Any changes applied to spinlock_t also apply to local_lock.
⚲ API
    linux/local_lock.h$_{inc}$
📖 References
    local_lock$_{doc}$
    PREEMPT_RT caveats: spinlock_t, rwlock_t, migrate_disable and local_lock$_{doc}$
    Proper locking under a preemptive kernel$_{doc}$
    Local locks in the kernel
💾 History: Prior to kernel version 2.6, Linux disabled interrupt to implement short critical sections. Since version 2.6 and later, Linux is fully preemptive.

#### Spinning locks
##### Spinlocks

a spinlock is a lock which causes a thread trying to acquire it to simply wait in a loop ("spin") while repeatedly checking if the lock is available. Since the thread remains active but is not performing a useful task, the use of such a lock is a kind of busy waiting. Once acquired, spinlocks will usually be held until they are explicitly released, although in some implementations they may be automatically released if the thread being waited on (that which holds the lock) blocks, or "goes to sleep".
Spinlocks are commonly used inside kernels because they are efficient if threads are likely to be blocked for only short periods. However, spinlocks become wasteful if held for longer durations, as they may prevent other threads from running and require rescheduling. 👁 For example kobj_kset_join$_{id}$ uses spinlock to protect assess to the linked list.
Enabling and disabling of kernel preemption replaced spinlocks on uniprocessor systems (disabled CONFIG_SMP$_{id}$). Most spinning locks becoming sleeping locks in the CONFIG_PREEMPT_RT$_{id}$ kernels.
📖 References
    spinlock_t$_{id}$
    raw_spinlock_t$_{id}$
    bit_spin_lock$_{id}$
    Introduction to spinlocks
    Queued spinlocks

##### Seqlocks

A seqlock (short for "sequential lock") is a special locking mechanism used in Linux for supporting fast writes of shared variables between two parallel operating system routines. It is a special solution to the readers–writers problem when the number of writers is small.
It is a reader-writer consistent mechanism which avoids the problem of writer starvation. A seqlock_t$_{id}$ consists of storage for saving a sequence counter seqcount_t$_{id}$/seqcount_spinlock_t in addition to a lock. The lock is to support synchronization between two writers and the counter is for indicating consistency in readers. In addition to updating the shared data, the writer increments the sequence counter, both after acquiring the lock and before releasing the lock. Readers read the sequence counter before and after reading the shared data. If the sequence counter is odd on either occasion, a writer had taken the lock while the data was being read and it may have changed. If the sequence counters are different, a writer has changed the data while it was being read. In either case readers simply retry (using a loop) until they read the same even sequence counter before and after.
💾 History: The semantics stabilized as of version 2.5.59, and they are present in the 2.6.x stable kernel series. The seqlocks were developed by Stephen Hemminger and originally called frlocks, based on earlier work by Andrea Arcangeli. The first implementation was in the x86-64 time code where it was needed to synchronize with user space where it was not possible to use a real lock.
⚲ API
    seqlock_t$_{id}$
       DEFINE_SEQLOCK$_{id}$, seqlock_init$_{id}$, read_seqlock_excl$_{id}$, write_seqlock$_{id}$
    seqcount_t$_{id}$
       seqcount_init$_{id}$, read_seqcount_begin$_{id}$, read_seqcount_retry$_{id}$, write_seqcount_begin$_{id}$, write_seqcount_end$_{id}$
    linux/seqlock.h$_{inc}$
👁 Example: mount_lock$_{id}$, defined in fs/namespace.c$_{src}$
📖 References
    Sequence counters and sequential locks$_{doc}$
    SeqLock

#### Spinning or sleeping locks

    normalon preempt RT spinlock_t,raw_spinlock_trt_mutex_base, rt_spin_lock, sleeping rwlock_tspinningsleeping local_lockpreempt_disablemigrate_disable, rt_spin_lock, sleeping

#### Low level

The compiler might optimize away or reorder writes to variables leading to unexpected behavior when variables are accessed concurrently by multiple threads.
⚲ API
    asm-generic/rwonce.h$_{inc}$ – prevent the compiler from merging or refetching reads or writes.
    linux/compiler.h$_{inc}$
       barrier$_{id}$ – prevents the compiler from reordering instructions around the barrier
    asm-generic/barrier.h$_{inc}$ – generic barrier definitions
    arch/x86/include/asm/barrier.h$_{src}$ – force strict CPU ordering
       mb$_{id}$ – ensures that all memory operations before the barrier are completed before any memory operations after the barrier are started
⚙️ Internals
    Atomics$_{doc}$
       asm-generic/atomic.h$_{inc}$
       linux/atomic/atomic-instrumented.h$_{inc}$
          atomic_dec_and_test$_{id}$ ...
📚 Further reading
    volatile – prevents the compiler from optimizations
    Memory barrier – enforces an ordering constraint on memory operations
⚙️ Locking internals
    linux/lockdep.h$_{inc}$ – runtime locking correctness validator
    linux/debug_locks.h$_{inc}$
    lib/locking-selftest.c$_{src}$
    kernel/locking$_{src}$
    timer_list$_{id}$ wait_queue_head_t$_{id}$
       kernel/locking/locktorture.c$_{src}$ – module-based torture test facility for locking
📖 Locking references
    locking$_{doc}$
       Lock types and their rules$_{doc}$
          😴 sleeping locks$_{doc}$
             mutex$_{id}$, rt_mutex$_{id}$, semaphore$_{id}$, rw_semaphore$_{id}$, ww_mutex$_{id}$, percpu_rw_semaphore$_{id}$
             on preempt RT: local_lock, spinlock_t, rwlock_t
          😵‍💫 spinning locks$_{doc}$:
             raw_spinlock_t, bit spinlocks
             on non preempt RT: spinlock_t, rwlock_t
    Unreliable Guide To Locking$_{doc}$
    Synchronization primitives

### Time

⚲ UAPI
    uapi/linux/time.h$_{inc}$
       timespec$_{id}$ – nanosecond resolution
       timeval$_{id}$ – microsecond resolution
       timezone$_{id}$
    uapi/linux/time_types.h$_{inc}$
       __kernel_timespec$_{id}$ – nanosecond resolution, used in syscalls
⚲ API
    linux/sched/clock.h$_{inc}$
       sched_clock$_{id}$
    linux/time.h$_{inc}$
       tm$_{id}$
       get_timespec64$_{id}$
    linux/ktime.h$_{inc}$
       ktime_t$_{id}$ – nanosecond scalar representation for kernel time values
       ktime_sub$_{id}$
    linux/timekeeping.h$_{inc}$
       ktime_get$_{id}$, ktime_get_ns$_{id}$
       ktime_get_real$_{id}$
    linux/time64.h$_{inc}$
       timespec64$_{id}$
       time64_t$_{id}$
       ns_to_timespec64$_{id}$
       timespec64_sub$_{id}$
       ktime_to_timespec64$_{id}$
    uapi/linux/rtc.h$_{inc}$
    linux/jiffies.h$_{inc}$
⚙️ Internals
    kernel/time$_{src}$
📖 References
    ktime accessors$_{doc}$
    Clock sources, Clock events, sched_clock and delay timers$_{doc}$
    Time and timer routines$_{doc}$
    Year 2038 problem

## Interrupts

An interrupt is a signal to the processor emitted by hardware or software indicating an event that needs immediate attention. An interrupt alerts the processor to a high-priority condition requiring the interruption of the current code the processor is executing. The processor responds by suspending its current activities, saving its state, and executing a function called an interrupt handler (or an interrupt service routine, ISR) to deal with the event. This interruption is temporary, and, after the interrupt handler finishes, the processor resumes normal activities.
There are two types of interrupts: hardware interrupts and software interrupts. Hardware interrupts are used by devices to communicate that they require attention from the operating system. For example, pressing a key on the keyboard or moving the mouse triggers hardware interrupts that cause the processor to read the keystroke or mouse position. Unlike the software type, hardware interrupts are asynchronous and can occur in the middle of instruction execution, requiring additional care in programming. The act of initiating a hardware interrupt is referred to as an interrupt request - IRQ (⚙️ do_IRQ$_{id}$).
A software interrupt is caused either by an exceptional condition in the processor itself, or a special instruction in the instruction set which causes an interrupt when it is executed. The former is often called a trap (⚙️ do_trap$_{id}$) or exception and is used for errors or events occurring during program execution that are exceptional enough that they cannot be handled within the program itself. For example, if the processor's arithmetic logic unit is commanded to divide a number by zero, this impossible demand will cause a divide-by-zero exception (⚙️ X86_TRAP_DE$_{id}$), perhaps causing the computer to abandon the calculation or display an error message. Software interrupt instructions function similarly to subroutine calls and are used for a variety of purposes, such as to request services from low-level system software such as device drivers. For example, computers often use software interrupt instructions to communicate with the disk controller to request data be read or written to the disk.
Each interrupt has its own interrupt handler. The number of hardware interrupts is limited by the number of interrupt request (IRQ) lines to the processor, but there may be hundreds of different software interrupts.
⚲ API
    /proc/interrupts
    man 1 irqtop – utility to display kernel interrupt information
    irqbalance – distribute hardware interrupts across processors on a multiprocessor system
    There are many ways to request ISR, two of them
    devm_request_threaded_irq$_{id}$ – preferable function to allocate an interrupt line for a managed device with a threaded ISR
    request_irq$_{id}$, free_irq$_{id}$ – old and common functions to add and remove a handler for an interrupt line
    linux/interrupt.h$_{inc}$ – main interrupt support header
       irqaction$_{id}$ – contains handler functions
    linux/irq.h$_{inc}$
       irq_data$_{id}$
    include/linux/irqflags.h$_{inc}$
       irqs_disabled$_{id}$
       local_irq_save$_{id}$ ...
       local_irq_disable$_{id}$ ...
    linux/irqdesc.h$_{inc}$
       irq_desc$_{id}$
    linux/irqdomain.h$_{inc}$
       irq_domain$_{id}$ – hardware interrupt number translation object
       irq_domain_get_irq_data$_{id}$
    linux/msi.h$_{inc}$ – Message Signaled Interrupts
       msi_desc$_{id}$
    Structure of structures:
       irq_desc$_{id}$ is container of
          irq_data$_{id}$
             irq – interrupt number
          irq_common_data$_{id}$
          list of irqaction$_{id}$
⚙️ Internals
    kernel/irq/settings.h$_{src}$
    kernel/irq$_{src}$
       kernel/irq/internals.h$_{src}$
    ls /sys/kernel/debug/irq/domains/
       x86_vector_domain$_{id}$, x86_vector_domain_ops$_{id}$
    irq_chip$_{id}$
    load_idt$_{id}$ – load Interrupt Descriptor Table
📖 References
    IRQs$_{doc}$
       The irq_domain interrupt number mapping library$_{doc}$
    Linux generic IRQ handling$_{doc}$
    Message Signaled Interrupts: The MSI Driver Guide$_{doc}$
    Lock types and their rules$_{doc}$
    Hard IRQ Context$_{doc}$
    Interrupts
👁 Examples
    dummy_irq_chip$_{id}$ – dummy interrupt chip implementation
    lib/locking-selftest.c$_{src}$

### IRQ affinity

⚲ API
    /proc/irq/default_smp_affinity
    /proc/irq/*/smp_affinity and /proc/irq/*/smp_affinity_list
Common types and functions:
    struct irq_affinity$_{id}$ – description for automatic irq affinity assignments, see devm_platform_get_irqs_affinity$_{id}$
    struct irq_affinity_desc$_{id}$ – interrupt affinity descriptor, see irq_update_affinity_desc$_{id}$, irq_create_affinity_masks$_{id}$
    irq_set_affinity$_{id}$
    irq_get_affinity_mask$_{id}$
    irq_can_set_affinity$_{id}$
    irq_set_affinity_hint$_{id}$
    irqd_affinity_is_managed$_{id}$
    irq_data_get_affinity_mask$_{id}$
    irq_data_get_effective_affinity_mask$_{id}$
    irq_data_update_effective_affinity$_{id}$
    irq_set_affinity_notifier$_{id}$
    irq_affinity_notify$_{id}$
    irq_chip_set_affinity_parent$_{id}$
    irq_set_vcpu_affinity$_{id}$
🛠️ Utilities
    irqbalance – distributes hardware interrupts across CPUs
📖 References
    SMP IRQ affinity$_{doc}$
    IRQ affinity, LF
    managed_irq kernel parameter, @LKML
    irqaffinity kernel parameter, @LKML

### Non-maskable interrupts

⚲ API
    linux/nmi.h$_{inc}$
       in_nmi$_{id}$
       touch_nmi_watchdog$_{id}$
    trace/events/nmi.h$_{inc}$
    arch/x86/include/asm/nmi.h$_{src}$
       register_nmi_handler$_{id}$
       unregister_nmi_handler$_{id}$
⚙️ Internals
    arch/x86/kernel/nmi.c$_{src}$
    arch/x86/kernel/nmi_selftest.c$_{src}$
📖 References
    NMI Trace Events$_{doc}$
📚 Further reading
    Non-maskable interrupt handler (NMI)
📚 Further reading about interrupts
    IDT – Interrupt descriptor table
    Tickless (Full dynticks) reduces timer interrupts overhead, CONFIG_NO_HZ_FULL$_{id}$
    LGDT/LIDT – Load Global/Interrupt Descriptor Table Register asm instruction

## Deferred works
### Scheduler context
#### kthread work

This framework simplifies the use of kernel kthreads. A kthread_work$_{id}$ item can be queued with kthread_queue_work$_{id}$ and flushed using kthread_flush_work$_{id}$. All queued kthread_work items are processed by a dedicated kernel thread executing the kthread_worker_fn$_{id}$ function.
⚲ API
    kthread_work$_{id}$ – contains kthread_work_func_t$_{id}$ to execute
       kthread_init_work$_{id}$
       kthread_flush_work$_{id}$
    kthread_worker$_{id}$ – links a kthread_work and a task
       kthread_run_worker$_{id}$ – creates and wakes a kthread worker
          kthread_create_worker$_{id}$
          kthread_flush_worker$_{id}$
       kthread_destroy_worker$_{id}$
    kthread_queue_work$_{id}$ – queues a kthread_work on a kthread_worker
⚙️ Internals
    __kthread_create_worker_on_node$_{id}$
    kthread_worker_fn$_{id}$ – executes work's function
👁 Example usages
    watchdog_kworker$_{id}$, pwq_release_worker$_{id}$, pump_messages$_{id}$

#### Threaded IRQ

⚲ API devm_request_threaded_irq$_{id}$, request_threaded_irq$_{id}$ ISR should return IRQ_WAKE_THREAD to run thread function
⚙️ Internals
    setup_irq_thread$_{id}$, irq_thread$_{id}$
    kernel/irq/manage.c$_{src}$
📖 References
    request_threaded_irq$_{doc}$

#### Work and workqueue

Generic async execution with shared worker pool.
⚲ API
    PF_WQ_WORKER$_{id}$ – workqueue worker process flag
    linux/workqueue.h$_{inc}$, linux/workqueue_types.h$_{inc}$
    work_struct$_{id}$, INIT_WORK$_{id}$, schedule_work$_{id}$,
    delayed_work$_{id}$, INIT_DELAYED_WORK$_{id}$, schedule_delayed_work$_{id}$, cancel_delayed_work_sync$_{id}$
    workqueue_struct$_{id}$
       alloc_workqueue$_{id}$
       destroy_workqueue$_{id}$
    queue_work$_{id}$ – queues work on a workqueue
    show_all_workqueues$_{id}$
       show_one_workqueue$_{id}$
    system_power_efficient_wq$_{id}$ ...
👁 Example usage samples/ftrace/sample-trace-array.c$_{src}$
⚙️ Internals
    kernel/workqueue.c$_{src}$
       workqueue_init$_{id}$
          create_worker$_{id}$
             worker_thread$_{id}$
                process_one_work$_{id}$
       format_worker_id$_{id}$ – names kworker kthreads
       pool_workqueue$_{id}$
          worker_pool$_{id}$
📖 References
    Concurrency Managed Workqueue$_{doc}$

### Interrupt context

    linux/irq_work.h$_{inc}$ – framework for enqueueing and running callbacks from hardirq context
       samples/trace_printk/trace-printk.c$_{src}$

#### Timers
##### softirq timer

This timer is a softirq for periodical tasks with jiffies resolution
⚲ API
    linux/timer.h$_{inc}$
    timer_list$_{id}$, DEFINE_TIMER$_{id}$, timer_setup$_{id}$
    mod_timer$_{id}$ — sets expiration time in jiffies.
    del_timer$_{id}$
⚙️ Internals
    kernel/time/timer.c$_{src}$
       timer_bases$_{id}$
👁 Examples
    input_enable_softrepeat$_{id}$ and input_start_autorepeat$_{id}$
📚 References
    Time and timer routines$_{doc}$
       mod_timer_pending ... $_{doc}$

##### High-resolution timer

⚲ API
    /proc/timer_list
    /proc/sys/kernel/timer_migration
    linux/hrtimer_defs.h$_{inc}$
    linux/hrtimer.h$_{inc}$
    hrtimer$_{id}$, hrtimer.function — callback
    hrtimer_init$_{id}$
    hrtimer_setup$_{id}$
    hrtimer_start$_{id}$ — starts a timer with nanosecond resolution
    hrtimer_cancel$_{id}$
👁 Examples alarm_init$_{id}$, watchdog_enable$_{id}$
⚙️ Internals
    CONFIG_HIGH_RES_TIMERS$_{id}$
    kernel/time/tick-internal.h$_{src}$
       hrtimer_bases$_{id}$
    kernel/time/hrtimer.c$_{src}$
    kernel/time/itimer.c$_{src}$
    kernel/time/timer_list.c$_{src}$
📚 HR timers references
    High-resolution timers$_{doc}$
    hrtimers - subsystem for high-resolution kernel timers$_{doc}$
    high resolution timers and dynamic ticks design notes$_{doc}$
📚 Timers references
    Timers$_{doc}$
    Better CPU selection for timer expiration

#### Tasklet

tasklet is a softirq, for time critical operations
⚲ API is deprecated in favor of threaded IRQs: devm_request_threaded_irq$_{id}$
    tasklet_struct$_{id}$, tasklet_init$_{id}$, tasklet_schedule$_{id}$
⚙️ Internals: tasklet_action_common$_{id}$ HI_SOFTIRQ, TASKLET_SOFTIRQ

#### Softirq

softirq is internal system facility and should not be used directly. Use tasklet or threaded IRQs
⚲ API
    linux/interrupt.h$_{inc}$
    cat /proc/softirqs
    open_softirq$_{id}$ registers softirq_action$_{id}$
⚙️ Internals
    kernel/softirq.c$_{src}$
📖 References
    Introduction to deferred interrupts (Softirq, Tasklets and Workqueues)
    Timers and time management
    Deferred work, linux-kernel-labs
    Chapter 7. Time, Delays, and Deferred Work

## CPU specific

🖱️ GUI
    tuna – program for tuning running processes
⚲ API
    cat /proc/cpuinfo
    /sys/devices/system/cpu/
    /sys/devices/system/node/
    /sys/cpu/
    /sys/fs/cgroup/cpu/
    grep -i cpu /proc/self/status
    rdmsr – tool for reading CPU machine specific registers (MSR)
    man 1 lscpu – display information about the CPU architecture
    linux/arch_topology.h$_{inc}$ – arch specific cpu topology information
    linux/cpu.h$_{inc}$ – generic cpu definition
    linux/cpu_cooling.h$_{inc}$
    linux/cpu_pm.h$_{inc}$
    linux/cpufeature.h$_{inc}$
    linux/peci-cpu.h$_{inc}$
    linux/sched/cputime.h$_{inc}$ – cputime accounting APIs
⚙️ Internals
    drivers/base/cpu.c$_{src}$
       cpu_dev_init$_{id}$

### Cache

    linux/cacheflush.h$_{inc}$
       arch/x86/include/asm/cacheflush.h$_{src}$: clflush_cache_range$_{id}$
    linux/cache.h$_{inc}$
       arch/x86/include/asm/cache.h$_{src}$
⚙️ Internals
    arch/x86/mm/pat/set_memory.c$_{src}$
    arch/x86/kernel/cpu/mtrr/$_{src}$
📚 Further reading
    MTTR – Memory type range register
    CPU cache

### SMP

This chapter is about multiprocessing and muti-core aspects of Linux kernel.
Key concepts and features of Linux SMP include:
* Symmetry: In an SMP system, all processors are considered the same without hardware hierarchy in contradiction to use of coprocessors.
* Load balancing: The Linux kernel employs load balancing mechanisms to distribute tasks evenly among available CPU cores. This prevents any one core from becoming overwhelmed while others remain underutilized.
* Parallelism: SMP enables parallel processing, where multiple threads or processes can execute simultaneously on different CPU cores. This can significantly improve the execution speed of applications that are designed to take advantage of multiple threads.
* Thread scheduling: The Linux kernel scheduler is responsible for determining which threads or processes run on which CPU cores and for how long. It aims to optimize performance by minimizing contention and maximizing CPU utilization.
* Shared memory: In an SMP system, all CPU cores typically share the same physical memory space. This allows processes and threads running on different cores to communicate and share data more efficiently.
* NUMA – Non-Uniform Memory Access: In larger SMP systems, memory access times might not be uniform due to the physical arrangement of memory banks and processors. Linux has mechanisms to handle NUMA architectures efficiently, allowing processes to be scheduled on CPUs closer to their associated memory.
* Cache coherency: SMP systems require mechanisms to ensure that all CPU cores have consistent views of memory. Cache coherency protocols ensure that changes made to shared memory locations are correctly propagated to all cores.
* Scalability: SMP systems can be scaled up to include more CPU cores, enhancing the overall computing power of the system. However, as the number of cores increases, challenges related to memory access, contention, and communication between cores may arise.
* Kernel and user space: Linux applications running in user space can take advantage of SMP without needing to be aware of the underlying hardware details. The kernel handles the management of CPU cores and resource allocation.
⚲ API
    ps -PLe – lists threads with processor that the thread last executed on (the third column PSR).
    man 2 getcpu – determine CPU and NUMA node on which the calling thread is running
    man 8 chcpu – configure CPUs
    man 3 CPU_SET – macros for manipulating CPU sets
    linux/smp.h$_{inc}$
    linux/cpu.h$_{inc}$
    linux/group_cpus.h$_{inc}$: group_cpus_evenly$_{id}$ – groups all CPUs evenly per NUMA/CPU locality
    asm-generic/percpu.h$_{inc}$
    linux/percpu-defs.h$_{inc}$ – basic definitions for percpu areas
       this_cpu_ptr$_{id}$
    linux/percpu.h$_{inc}$
    linux/percpu-refcount.h$_{inc}$
    linux/percpu-rwsem.h$_{inc}$
    linux/preempt.h$_{inc}$
       migrate_disable$_{id}$, migrate_enable$_{id}$
    /sys/bus/cpu
    per CPU local_lock
    arch/x86/include/asm/topology.h$_{src}$
⚙️ Internals
    boot_cpu_init$_{id}$ activates the first CPU
    smp_prepare_cpus$_{id}$ initializes rest CPUs during boot
    cpu_number$_{id}$
    CONFIG_SMP$_{id}$
       CONFIG_NUMA$_{id}$
    trace/events/percpu.h$_{inc}$
    IPI – Inter-processor interrupt
       trace/events/ipi.h$_{inc}$
       kernel/irq/ipi.c$_{src}$
       ipi_send_single$_{id}$, ipi_send_mask$_{id}$ ...
       drivers/base/cpu.c$_{src}$ – CPU driver model subsystem support
       kernel/cpu.c$_{src}$
    smpboot
       linux/smpboot.h$_{inc}$
       kernel/smpboot.c$_{src}$
       arch/x86/kernel/smpboot.c$_{src}$
    lib/group_cpus.c$_{src}$
🛠️ Utilities
    irqbalance – distributes hardware interrupts across CPUs
    man 8 numactl – controls NUMA policy for processes or shared memory
📖 References
    Per-CPU Data$_{doc}$
    How CPU topology info is exported via sysfs$_{doc}$
📚 Further reading
    Functionalities of the scheduler TuneD plugin
    tuned-adm – command line tool for switching between different tuning profiles

#### CPU affinity

Affinity refers to assigning a process or thread to specific CPU cores. This helps control which CPUs execute tasks, potentially improving performance by reducing data movement between cores. It can be managed using system calls or commands. Affinity can be represented as CPU bitmask: cpumask_t$_{id}$ or CPU affinity list: cpulist_parse$_{id}$.
⚲ API
    man 1 taskset – set or retrieve a process's CPU affinity
    grep Cpus_allowed /proc/self/status
    man 2 sched_setaffinity man 2 sched_getaffinity – set and get a thread's CPU affinity mask
       ↪ sched_setaffinity$_{id}$
    set_cpus_allowed_ptr$_{id}$ – common kernel function to change a task's affinity mask
    linux/cpu_rmap.h$_{inc}$ – CPU affinity reverse-map support
    linux/cpumask_types.h$_{inc}$
       struct cpumask, cpumask_t$_{id}$ – CPUs bitmap, can be very big
       cpumask_var_t$_{id}$ – type for local cpumask variable, see alloc_cpumask_var$_{id}$, free_cpumask_var$_{id}$.
    linux/cpumask.h$_{inc}$ – Cpumasks provide a bitmap suitable for representing the set of CPU's in a system, one bit position per CPU number
       for_each_possible_cpu$_{id}$
       num_online_cpus$_{id}$
       cpumask_set_cpu$_{id}$
       cpumask_test_cpu$_{id}$
       for_each_cpu$_{id}$
⚙️ Internals
    cpus_mask$_{id}$ – affinity of task_struct$_{id}$
    cpus_allowed$_{id}$ – affinity of cpuset$_{id}$
📚 Further reading
    Processor affinity
    Affinity mask

#### CPU hotplug

CPU hotplugging in Linux refers to the ability to dynamically add or remove CPUs from the system without needing a reboot. This feature is crucial in environments requiring high availability and resource flexibility, such as data centers, virtualized systems, and systems that use power management aggressively.
🗝️ Acronyms
    BP – Bootstrap Processor
    AP – Application Processor
⚲ API
    /sys/devices/system/cpu/cpu*/online
    /sys/devices/system/cpu/cpu*/hotplug/
    linux/cpu.h$_{inc}$
       add_cpu$_{id}$ ...
    linux/cpuhotplug.h$_{inc}$
       cpuhp_state$_{id}$ – CPU hotplug states
       cpuhp_setup_state$_{id}$ ... – setups hotplug state callbacks
          cpuhp_setup_state_multi$_{id}$
          cpuhp_setup_state_nocalls$_{id}$
    linux/cpuhplock.h$_{inc}$ – CPU hotplug locking
       cpus_read_lock$_{id}$ ...
       remove_cpu$_{id}$ ...
⚙️ Internals
    kernel/cpu.c$_{src}$
       cpuhp_state$_{id}$ – from CPUHP_OFFLINE to CPUHP_AP_ACTIVE and CPUHP_ONLINE.
       cpuhp_hp_states$_{id}$
       boot_cpu_hotplug_init$_{id}$
       cpuhp_threads_init$_{id}$
       ... cpuhp_invoke_callback_range$_{id}$ ...
    kernel/irq/cpuhotplug.c$_{src}$
    drivers/base/cpu.c$_{src}$ – CPU subsystem support
       cpu_dev_init$_{id}$
          ... cpu_subsys_online$_{id}$
👁️ Examples
    torture_onoff$_{id}$
    tools/testing/selftests/sched_ext/hotplug.c$_{src}$
📖 References
    CPU hotplug in the Kernel$_{doc}$
📚 Further reading
    CONFIG_CPU_HOTPLUG_STATE_CONTROL$_{id}$ – enables the ability to write incremental steps between "offline" and "online" states to the CPU's sysfs target file, allowing for more granular control of state transitions.
       target_store$_{id}$: cpu_up$_{id}$/cpu_down$_{id}$
    cpuhotplug @LKML

#### CPU isolation

CPU isolation ensures that specific tasks run on dedicated CPUs, reducing contention and latency.
Housekeeping CPUs refer to the CPUs that are reserved for various system tasks. See hk_type$_{id}$.
Isolated CPUs are dedicated to real-time applications, such as DPDK.
⚲ API
    /sys/devices/system/cpu/isolated
    /sys/devices/system/cpu/nohz_full
    /sys/fs/cgroup/cpuset.cpus.isolated
    /sys/fs/cgroup/.../cpuset.cpus.partition
    linux/sched/isolation.h$_{inc}$
       hk_type$_{id}$ – housekeeping type
       housekeeping_cpumask$_{id}$
       cpu_is_isolated$_{id}$
    linux/cpuset.h$_{inc}$ – cpuset interface
       cpuset_cpu_is_isolated$_{id}$
    man 7 cpuset – confine processes to processor and memory node subsets
⚙️ Internals
    CONFIG_CPU_ISOLATION$_{id}$
       kernel/sched/isolation.c$_{src}$
          isolated_cpus$_{id}$
    CONFIG_CPUSETS$_{id}$
       kernel/cgroup/cpuset.c$_{src}$
          cpuset_init$_{id}$
          cpuset_init_smp$_{id}$
          partition_xcpus_newstate$_{id}$
📖 References
    CPU lists in command-line parameters$_{doc}$
       nohz_full clears housekeeping.cpumasks$_{id}$ for tick, wq, timer, rcu, misc, and kthread in housekeeping_nohz_full_setup$_{id}$
       isolcpus clears housekeeping.cpumasks$_{id}$ for domain (by default), tick, and managed_irq in housekeeping_isolcpus_setup$_{id}$
    CPUSETS of cgroup v2$_{doc}$
    CPUSETS of cgroup v1$_{doc}$
📚 Further reading
    CPU Isolation state of the art, LPC'23
    CPU Isolation
    isolcpus @LKML
    housekeeping @LKML
    Explicitly Reserved CPU List, Kubernetes Documentation
    CPU Partitioning
    Scheduler Domains$_{doc}$ – the Scheduler balances CPUs (scheduling groups) within a sched domain
    nohz_full @LKML

### Memory barriers

Memory barriers (MB) are synchronization mechanisms used to ensure proper ordering of memory operations in a SMP environment. They play a crucial role in maintaining the consistency and correctness of data shared among different CPU cores or processors. MBs prevent unexpected and potentially harmful reordering of memory access instructions by the compiler or CPU, which can lead to data corruption and race conditions in a concurrent software system.
⚲ API
    man 2 membarrier
    asm-generic/barrier.h$_{inc}$
       mb$_{id}$, rmb$_{id}$, wmb$_{id}$
       smp_mb$_{id}$, smp_rmb$_{id}$, smp_wmb$_{id}$
⚙️ Internals
    arch/x86/include/asm/barrier.h$_{src}$
    kernel/sched/membarrier.c$_{src}$
📖 References
    Memory barriers$_{doc}$

### States

C-states and P-states are features in modern CPUs designed to improve energy efficiency.
C-states, aka cpuidle, Processor states:
    C0 – the operating state.
    C1 (aka Halt) – the processor is not executing instructions, but can return to an executing state instantaneously.
    C2 (aka Stop-Clock) – the processor maintains all software-visible state, but may take longer to wake up.
    C3 (aka Sleep) – takes longer to wake up.
P-states, aka cpufreq, Performance states:
    P0 – maximum power and frequency
    Pn – less power and frequency
⚲ API
    idle=
    Working-State Power Management$_{doc}$
       intel_pstate=
    cpufreq.default_governor=
    /dev/cpu_dma_latency – see set_cpu_dma_latency$_{id}$
    C-states interfaces:
       /sys/devices/system/cpu/cpuidle/
       /sys/devices/system/cpu/cpu*/cpuidle/
       linux/cpuidle.h$_{inc}$ – a generic framework for CPU idle power management
       intel_idle CPU Idle Time Management Driver$_{doc}$
    P-states interfaces:
       /sys/devices/system/cpu/cpufreq/
       /sys/devices/system/cpu/cpu*/cpufreq/
       /sys/devices/system/cpu/intel_pstate/
       linux/cpufreq.h$_{inc}$
       Kernel Command Line Options for intel_pstate$_{doc}$
       linux/sched/cpufreq.h$_{inc}$ – interface between cpufreq drivers and the scheduler
    linux/pm_qos.h$_{inc}$
⚙️ Internals
    drivers/cpuidle$_{src}$ – C-states implementation
    drivers/cpufreq$_{src}$ – P-states implementation
       intel_pstate$_{id}$
       acpi_cpufreq_driver$_{id}$
    kernel/sched/cpufreq_schedutil.c$_{src}$ – implementation of cpufreq.default_governor=schedutil
    kernel/power/qos.c$_{src}$
       cpu_latency_qos_miscdev$_{id}$ – implementation of /dev/cpu_dma_latency
📖 References
    Working-State Power Management$_{doc}$
       CPU Idle Time Management$_{doc}$
       CPU Performance Scaling$_{doc}$
    PM Quality Of Service Interface$_{doc}$
    Device Frequency Scaling$_{doc}$
    CPUFreq Governor
    CPUFreq - CPU frequency and voltage scaling$_{doc}$
📚 Further reading
    cpufreq$_{ltp}$
    cpupower
    How to use cpufrequtils
       cpufreq-info
       cpufreq-set

### Architectures

Linux CPU architectures refer to the different types of central processing units (CPUs) that are compatible with the Linux operating system. Linux is designed to run on a wide range of CPU architectures, which allows it to be utilized on various devices, from smartphones to servers and supercomputers. Each architecture has its own unique features, advantages, and design considerations.
Architectures are classified by family (e.g. x86, ARM), word or long int size (e.g. CONFIG_32BIT$_{id}$, CONFIG_64BIT$_{id}$).
Some functions with different implementations for different CPU architectures:
    do_boot_cpu$_{id}$ > start_secondary$_{id}$ > cpu_init$_{id}$
    setup_arch$_{id}$, start_thread$_{id}$, get_current$_{id}$, current$_{id}$
⚲ API
    BITS_PER_LONG$_{id}$, __BITS_PER_LONG$_{id}$,
⚙️ Arch internals
    arch$_{src}$
       x86
          CONFIG_X86$_{id}$
          arch/x86$_{src}$
          drivers/platform/x86$_{src}$
          https://lwn.net/Kernel/Index/#Architectures-x86
       ARM
          CONFIG_ARM$_{id}$
          arch/arm$_{src}$, ARM Architecture$_{doc}$
          https://lwn.net/Kernel/Index/#Architectures-ARM
          arch/arm64$_{src}$, ARM64 Architecture$_{doc}$
    architecture-specific initialization
📖 References
    CPU Architectures$_{doc}$
       x86-specific$_{doc}$
          x86_64 Support$_{doc}$
📚 Further reading about multitasking, scheduling and CPU
    bcc/ebpf CPU and scheduler tools
* 1 2 Malte Skarupke. "Measuring Mutexes, Spinlocks and how Bad the Linux Scheduler Really is".