Archive | Linux kernel Preemption IDT Faults Traps Interrupts RSS feed for this section

Before the world of Linux Kernel Preemptions: a cooperative world

By on January 30, 2012 in Linux Kernel Memory Management, Linux kernel Preemption IDT Faults Traps Interrupts, Processor Throughputs, Uncategorized

Kernel preemption tries to ensure fair usage of limited CPU resources. One way to understand kernel preemption is to explore its opposite. i.e. the way it WAS before the 2.6 linux kernel (which is preemptive). Well, the way it WAS .. was a cooperative world: A Process that got the CPU resources was expected to play nine-nine, and let cooperatively hand over the cpu (i.e. at EXIT system call), or the kernel could also, when it switched to user-mode, decide to schedule a new process. Processes were expected to be graceful in letting others use CPU resources.

Processes had to deal with many issues to try to ensure this model “worked”, however in additional to some hard problems created , there are some architectural features that just plumb stall out CPU resources and ensure suboptimal CPU resource usage regardless of whatever processes could have done about it. In other words, Processes do not have visibility into the underlying mechanisms of the operating system / kernel itself.

Linux Kernel preemption ensures what I consider to be somewhat fair (aka somewhat arbitrary) reallocation of CPU resources between more processes with “all the knowledge under the sun” on the underlying “goings on”. As an example, if the Kernel KNOWs the system is taking interrupts at HZ rate (see blog below), then why not try to prioritize between existing processes, and give others a chance to run ? If the Kernel KNOWS a process is to stall on a resource that may take some time to come available…why not put the process to “sleep” and “wake” someone fortunate process up ?

Well.. there are many reasons to NOT do that also (if processes are Real-time processes for example). Or to prevent “lockouts” etc etc

In the end, it boils down to a tradeoff between latency for the lucky few, .vs. throughput for the very many. And all shades in between, with considerations galore: A few of which are listed below->

Explicit and Implicit “Blocking”, Critical Code Section Synchronizations, Network and Block Device Processing Latencies and Throughputs, Interrupt Latencies, “Deferred Processing”, Safety in Preemptability (preventing lockouts because we have preempted tasks that should not have been), and there denials of preemptions / recursive depths of denials, relationships to interrups and recursive relationships to the above, system-programming architectural considerations and requirements (Scheduler Priorities, Classes etc), SMP / Cross Processor considerations, memory management, x86 Architectural considerations in Interrupt Latencies  etc etc

Again, all this is probably a good review for our past students. We explain these specific x86 features, Linux Kernel concepts and more in detail in my classes ( Advanced Linux Kernel Programming @UCSC-Extension), and also in other classes that I teach independently. Please take note, and take advantage also, of upcoming training sessions. As always, Feedback, Questions and Comments are appreciated and will be responded to.

Comments { 0 }

Linux Kernel Preemptions in the “Interrupt Context”: The x86 Interrupt Descriptor Table IDT

By on January 28, 2012 in Linux kernel Preemption IDT Faults Traps Interrupts

The term Interrupt / IRQ context in the kernel needs to be considered in the context of X86, and the low-level INTERRUPT and FAULT / TRAP handlers. INTERRUPTS are asynchronous events, FAULTS and TRAPS are programmatically generated events (i.e. can be “pegged” to a specific instruction) .

The purpose of this blog is to create an unambiguous delineation between Faults, Traps and Interrupts (COC Change-Of-Control events) . And then  create a lead-in into a future discussion on the implications to the kernel.

The actual entry into the fault handler is based on the Interrupt Number INT# (14 for Page Fault)… so for Page Fault, the index 14 will be used to index into the Interrupt Descriptor Table (IDT), a “gate descriptor is fetched (which has the Offset / EIP of the IRQ Handler). The Gate points to a “target descriptor”, which will have a Segment Selector , which will be used to fetch a Segment Descriptor per the normal mechanisms described in an older blog below the BASE and the OFFSET get added, and we have the Linear Address of the IRQ Handler…..where control will transfer when a COC events occurs.

In the case of an INTERRUPT (not a FAULT or a TRAP), the INT# is returned from the interrupting device, an INT# it was given at the time of device initialization (we will definitely blog on this later) at the time of request_irq, and the process hardware uses that INT# to vector through the IDT Gizmo.

All COCs “push” the  the following x86 state onto the stack: CS (Code Segment Selector.. see Blog below), EIP (Program Counter) and EFLAGS. However,  in the case of an Interrupt, we really dont know which CS:EIP will be pushed onto the stack, it will be the determined by the hardware as to when the INTR pin is raised inside the processor, and which “Instruction Boundary” that INTR is raised.

In the case of the FAULT (for example a Page Fault), the CS:EIP pushed onto the Stack will belong to the Instruction generating the Page Fault (which could be based on the Instruction fetch, Or an Operand Fetch).

In the case of a TRAP, the CS:EIP belongs to the Instruction following the instruction that generated the trap for operands, and to the Instruction itself when the TRAP is generated on an Instruction Fetch.

Now, the entry into the Kernel for all these events, INTERRUPTS, FAULTS, TRAPS etc etc happen through the same IDT, so the Linux Kernel calls them all IRQ events. The entry point into the “C” part of the Kernel (past the Low-Level interrupt drivers in entry_32.S) when preemption may be needed is unified for all these events, and  is preempt_schedule_irq.

However, the state  with which the Linux kernel will enter preempt_schedule_irq will be different based on whether the entry is in the INTERRUPT context or not. For discussion later.  Regardless, an entry into this routine is grounds for a “Preemption”.  Remember, these Preemptions are caused by IRQs.

We will  discuss “non-IRQ” Kernel-induced preemptions later also.

All this is probably a good review for our students. We explain these specific x86 features, Linux Kernel concepts and more in detail in my classes ( Advanced Linux Kernel Programming @UCSC-Extension), and also in other classes that I teach independently. Please take note, and take advantage also, of upcoming training sessions. As always, Feedback, Questions and Comments are appreciated and will be responded to. Cheers  Carlos !

 

Comments { 0 }