POWER MANAGEMENT - INTRODUCTION

Power management is a extensive topic, some basic elements need to understood be we go deeper.

In Linux if we click on shutdown 4 options will be provided

1. Shutdown
2. Standby
3. Suspend
4. Hibernate

Standby mode: LCD and display back light are turned off, CPU clock speed is reduced. Power saving will be less but latency will be less. Here latency refers to the time taken to resume.

Suspend mode: Suspend to RAM, CPU in sleep state which means power is turned off in most of the devices and parts of CPU. But DRAM puts itself in self refresh mode to preserve the machine state. CPU will be wake up from sleep state by some preprogrammed event.

Hibernate: Suspend to disk, is like powering down a system by retaining its state into disk, active pages in RAM will be moved to disk (persistent storage), power to RAM is also turned off. Hibernate needs a swap partition or swap file space to swap the RAM contents. Latency will be more.

KERNEL THREAD SYNCHRONIZATION WITH SEMAPHORE

// Kernel thread synchronization with semaphore
// Theory:
//Two threads can be synchornized by semaphore, blocked threads are pushed //into semaphore queue

#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/init.h>
#include <linux/kthread.h>
#include <linux/sched.h>
#include <linux/semaphore.h>
#include <linux/delay.h>

MODULE_LICENSE("Dual BSD/GPL");


struct kthr_data
{
    const char *name; //kthread name
    struct semaphore *sem1;
    struct semaphore *sem2;
};

static struct kthr_data dking, dqueen;
static struct semaphore kingsem, queensem;
static struct task_struct *tking, *tqueen;

/* our case:
   down dking sem1 decrements to make it (1->0)zero and runs the thread tking unlocked to locked state //king works
   up dking sem2 increments to make it (0->1) unlock because sem2 waitlist is still empty
   down dqueen sem1 decrements to make it (1->0)zero and runs the thread tking unlocked to locked state //queen works
   up dqueen sem2 increments to make it (0->1) unlock

*/
int kthread_function(void *data)
{
    struct kthr_data *pdata = (struct kthr_data*)data;
    while(1)
    {
        //down operation decrements the counter, if the count is 0 then down operation over the semaphore
        //1. blocks the calling kernel thread
        //2. Insert it into task structure to the queue of the semaphore
        //3. schedule another task
        down_interruptible(pdata->sem1); //uninterruptible sleep in sem->wait list when sem1 is zero
        printk("%s\n", pdata->name);
        mdelay(499);
        msleep(1);
        up(pdata->sem2);
        //if the semaphore wait queue is not empty then it pick a task and make it runnable else increment the counter
        //if sem->wait list is empty increment sem->count and leave if sem->count is 0 remove the first waiter structure from the sem queue
        if(kthread_should_stop())
            break;
    }
    return 0;
}

struct task_struct *ts;

static int __init kthr_init(void)
{
    printk("kthread init called");
    //semaphore is an object consists of a counter and a queue of waiting tasks

    sema_init(&kingsem, 1); //unlocked state
    sema_init(&queensem, 0); //locked state
    dking.name = "king";
    dqueen.name = "queen";
    dking.sem1 = &kingsem;
    dking.sem2 = &queensem;
    dqueen.sem1 = &queensem;
    dqueen.sem2 = &kingsem;

    tking = kthread_run(kthread_function, &dking, "king");
    tqueen = kthread_run(kthread_function, &dqueen, "queen");
    return 0;
}

void __exit kthr_exit(void)
{
    printk("tking_stop called");
    kthread_stop(tking);
    printk("tqueen_stop called");
    kthread_stop(tqueen);
}

module_init(kthr_init);
module_exit(kthr_exit);

//output:
//king queen king queen ....

//why we synchronize to know this just comment down and up lines and see there //will not be any ordered synchronized print statements
 

LINUX KERNEL THREAD SYNCHRONIZATION WITH WAITQUEUE

// Kernel thread synchronization with wait queue

/*

This code post is useful to learn the synchronization behavior of kernel thread with respect to synchronization 

Theory: 

Threads synchronization is based on event, 2 threads use completion event for synchronization and unblock the other thread

Blocked thread waiting for an event waits in a wait queue. when it receives the event it is eligible by the scheduler to run

Task in blocked state will expect some condition to be true (non zero)

wait queues in linux are defined by wait queue header which is a list_head node (Double linked list node) linked to wait_queue_t nodes which holds a function pointer to the task

wait_event_interruptible puts the task into waitqueue

wake_up_interruptible wakes the task on wakeup event

Code Explanation:

Initialization creates 2 instances of kernel thread (tone, tzero)with same kernel function (kthread function)

The kernel threads tone and tzero should alternatively display their names one and zero

Thread parameter structure is assocaited with each thread instance kthread_data

Thread parameters are

1. name

2. wait queue to synchronize the two threads

3. condition variable used with the wait queue

4. Pointer to other thread's parameter

kthread_function?

conditionally block on a wait queue using wait_event_interruptible

output the name

wait for the event in wait_queue

unblock the other thread using wake_up_interruptible

tone is the first thread with condition variable to true (1 - non-zero)

tzero thread with condition variable initialized to false (0 - zero)

*/

 

#include <linux/module.h>

#include <linux/kernel.h>

#include <linux/init.h>

#include <linux/kthread.h>

#include <linux/sched.h>

#include <linux/delay.h>

MODULE_LICENSE("Dual BSD/GPL");

struct kthr_data {

const char *name;

//wq<--wqh-->wq

wait_queue_head_t thrdwq; // kernel thread waits on this queue //wait_queue_head_t is the list head other nodes are wait_queue_t //nodes which holds the task (function pointer)

int condition;

struct kthr_data *datalink;

};

static struct kthr_data done, dzero;

int kthread_function(void* data)

{

struct kthr_data *pdata = (struct kthr_data*)data; // this data depends on the kernel thread running "one"/"zero"

while(1)

{

printk("wait(%s)", pdata->name);

wait_event_interruptible(pdata->thrdwq, pdata->condition);

pdata->condition = 0;

printk("%s\n",pdata->name);

mdelay(500);

msleep(1);

pdata->datalink->condition = 1;

printk("wakeup (%s)\n", pdata->name);

wake_up_interruptible(&pdata->datalink->thrdwq);//wake up the //task waiting in queue

if(kthread_should_stop())

break;

}

return 0;

}

struct task_struct *tone, *tzero;

int __init kthread_init(void)

{

printk("\nkthread init");

init_waitqueue_head(&done.thrdwq);

init_waitqueue_head(&dzero.thrdwq);

done.condition = 1;

dzero.condition = 0;

done.name = "one";

dzero.name = "zero";

done.datalink = &dzero;

dzero.datalink = &done;

tone = kthread_run(kthread_function, &done, "one");

tzero = kthread_run(kthread_function, &dzero, "zero");

return 0;

}

void __exit kthread_exit(void)

{

printk("\nkernel exit thread");

kthread_stop(tone);

kthread_stop(tzero);

}

module_init(kthread_init);

module_exit(kthread_exit);

//output: one zero one zero ...

 

 

MESSAGE SIGNALED INTERRUPT

Hope you might have read my previous article "Interrupt journey  from hardware to software"

Due to increasing pressure on chipset and processor packages to reduce pin count, the need for interrupt pins is expected to diminish over time.Devices, due to pin constraints, may implement messages to increase performance. 

PCI Express endpoints uses INTx emulation (in-band messages) instead of IRQ pin assertion. Using INTx emulation requires interruptsharing among devices connected to the same node (PCI bridge) while MSI is unique (non-shared) and does not require BIOS configuration support. As a result, the PCI Express technology requires MSI support for better interrupt performance.

INTERRUPT DELIVERY MECHANISM

Legacy PCI Interrupt Delivery

   

This mechanism supports devices that must use PCI-Compatible interrupt signaling (i.e., INTA#, INTB#, INTC#, and INTD#) defined for the PCI bus. Legacy functions use one of the interrupt lines to signal an interrupt. An INTx# signal is asserted to request interrupt service and deasserted when the interrupt service accesses a device-specific register, thereby indicating the interrupt is being serviced.

Native PCI Express Interrupt Delivery 

Native PCI Express device use message signaled interrupt. A Message Signaled Interrupt is not a PCI express message instead it is a simple memory write transaction. This write is distinguished from normal write by target address which is reserved for MSI interrupt delivery.

           PCI Express and Legacy Interrupt Delivery

Message Signaled Interrupts (MSIs) are delivered to the Root Complex via memory write transactions. The MSI Capability register provides all the information that the device requires to signal MSIs. This register is set up by configuration software (PCI bus driver) and includes the following information:

• Target memory address
• Data Value to be written to the specified address location
• The number of messages that can be encoded into the data

         MSI Capability Register

MSI Configuration Process

The following list specifies the steps taken by software (PCI bus driver) to configure MSI interrupts for a PCI Express device.

1. At startup time, the configuration software scans the PCI bus(es) (referred to as bus enumeration) and discovers devices (i.e., it performs configuration reads for valid Vendor IDs). On discovering a PCI express function, the configuration software reads the Capabilities List Pointer to obtain the location of the first Capability register within the chain of registers.

2. The software then searches the capability register sets until it discovers the MSI Capability register set (Capability ID of 05h).

3. Software assigns a dword-aligned memory address to the device's Message Address register. This is the destination address of the memory write used when delivering an interrupt request.

4. Software checks the Multiple Message Capable field in the device's Message Control register to determine how many event-specific messages the device would like assigned to it.

5. The software then allocates a number of messages equal to or less than what the device requested. At a minimum, one message will be allocated to the device.

6. The software writes the base message data pattern into the device's Message Data register.

7. Finally, the software sets the MSI Enable bit in the device's Message Control register, thereby enabling it to generate interrupts using MSI memory writes.

Memory Write Transaction (MSI):

When the device must generate an interrupt request, it writes the Message Data register contents to the memory address specified in its Message Address register. Header fields need to filled.

MSI-x is a extension to MSI which supports additional vectors per function.

Reference: PCI Express System Architecture

open source IDE at its best with gdb debugger suport

http://www.codeblocks.org/

Check the above link's download section to get free IDE for your environment

Features

Highlights: Open Source! GPLv3, no hidden costs. Cross-platform. Runs on Linux, Mac, Windows (uses wxWidgets). Written in C++. No interpreted languages or proprietary libs needed. Extensible through plugins Compiler: Multiple compiler support: GCC (MingW / GNU GCC) MSVC++ Digital Mars Borland C++ 5.5 Open Watcom ...and more Very fast custom build system (no makefiles needed) Support for parallel builds (utilizing your CPU's extra cores) Multi-target projects Workspaces to combine multiple projects Inter-project dependencies inside workspace Imports MSVC projects and workspaces (NOTE: assembly code not supported yet) Imports Dev-C++ projects Debugger: Interfaces GNU GDB Also supports MS CDB (not fully featured) Full breakpoints support: Code breakpoints Data breakpoints (read, write and read/write) Breakpoint conditions (break only when an expression is true) Breakpoint ignore counts (break only after certain number of hits) Display local function symbols and arguments User-defined watches (support for watching user-defined types through scripting) Call stack Disassembly Custom memory dump Switch between threads View CPU registers Interface: Syntax highlighting, customizable and extensible Code folding for C++ and XML files. Tabbed interface Code completion Class Browser Smart indent One-key swap between .h and .c/.cpp files Open files list for quick switching between files (optional) External customizable "Tools" To-do list management with different users And many more features provided through plugins!

tit bits - SWAPPING ADJACENT BITS

If   X = 1100 1010 

Result will be "1100 0101"

Left->Right

1 swapped with adjacent 1
0 swapped with adjacent 0
0 swapped with adjacent 1
0 swapped with adjacent 1

How to do:

1. Create an even bit pattern and an odd bit pattern "0xAA", "0x55"

2. Perform bitwise AND with x and even pattern(xeven) and odd pattern (xodd)

i.e 0x 1100 1010 & 0x 1010 1010,   0x 1100 1010 & 0x 0101 0101

3. Right shift xeven by 1,  xevenshift = xeven>>1

4. Left shift xodd by 1, xoddshift = xodd <<1

5. Perform bitwise OR between xevenshift and xoddshift

Result = xevenshift | xoddshift

INTERRUPT JOURNEY FROM HARDWARE TO SOFTWARE - 1

Interrupt is a very vast topic. This post is about How Interrupt is generated from Peripheral and routed to the processor. Exactly till we get an IRQ number.

INTERRUPT: 

    An event external to the currently executing process that causes a change in the normal flow of instruction execution, usually generated by hardware devices external to the CPU sometimes by software.

We will deal software interrupts and exceptions in a separate post.

Hardware interrupts are asynchronous in nature.

How it is asynchronous ? 

Interrupt will not wait for nay other CPU routine to complete. It can be raised even in the middle of CPU execution.

Interrupt Vs Polling

Polling is a technique used by CPU to check for events in the peripheral device in a periodic manner.

Pros:

Efficient if interrupts arrive frequently.

Cons:

Takes precious CPU time even when there is no request from external device.

Each hardware interrupt has an interrupt level, trigger, and interrupt priority.

The following sections describe various interrupt components:

Interrupt Level

The interrupt level defines the source of the interrupt and is often referred to as the interrupt source. There are basically two types of interrupt levels: system and bus. The bus interrupts are generated by the devices on the buses (such as PCI, ISA, VDEVICE, and PCI-E). Examples of system interrupts are the timer and Environmental and Power Off Warning (EPOW).

Interrupt Trigger

There are two types of trigger mechanisms, level-triggered interrupts and edge-triggered interrupts.

Level-Triggered: A level-triggered interrupt module always generates an interrupt whenever the level of the interrupt source is asserted.

A device sends a signal (Setting this line to active), and keeps it at that state until the interrupt is serviced.
Typically, the processor samples the interrupt input at predefined times during each bus cycle
Pro:Level-triggered interrupt is favored by some because it is easy to share the interrupt Request line without losing the interrupts, when multiple shared devices interrupt at the same time. Upon detecting assertion of the interrupt line, the CPU must search through the devices sharing the interrupt Request line until one who triggered the interrupt is detected.
Con: As long as any device on the line has an outstanding request for service the line remains asserted, so it is not possible to detect a change in the status of any other device.

• 
  

An edge-triggered interrupt is an interrupt signalled by a level transition on the interrupt line, either a falling edge (high to low) or a rising edge (low to high). A device, wishing to signal an interrupt, drives a pulse onto the line and then releases the line to its inactive state.
Hybrid.

Some systems use a hybrid of level-triggered and edge-triggered signalling. The hardware not only looks for an edge, but it also verifies that the interrupt signal stays active for a certain period of time.

A common use of a hybrid interrupt is for the NMI (non-maskable interrupt) input.

A message-signaled interrupt does not use a physical interrupt line. Instead, a device signals its request for service by sending a short message over some communications medium, typically a computer bus. The message might be of a type reserved for interrupts, or it might be of some pre-existing type such as a memory write. This is been used by PCI Express devices.

To generate an interrupt request PCI Express device initiates a memory write transaction targeting north bridge (APIC Interrupt controller). The data written is a unique interrupt vector associated with device generating the interrupt.

Interrupt controller interrupts the CPU through North bridge and the vector is delivered to the CPU.

We will have a separate post on MSI.

doorbell interrupt is often used to describe a mechanism whereby a software system can signal or notify a computer hardware device that there is some work to be done. Typically, the software system will place data in some well known and mutually agreed upon memory location(s), and "ring the doorbell" by writing to a different memory location.

Interrupt Priorities

The interrupt priority defines which of a set of pending interrupts is serviced first.

INTERRUPT STATES

Inactive An interrupt that is not active or pending.
Pending An interrupt from a source to the PIC that is recognized as asserted in hardware or generated by software and is waiting to be serviced by a target processor.
Active An interrupt from a source to the PIC that has been acknowledged by a processor, and is being serviced but has not completed.
Active and pending A processor is servicing the interrupt and the PIC has a pending interrupt from the 
same source.

 

 programmable interrupt controller (PIC) is a device that is used to combine several sources of interrupt onto one or more CPU lines, while allowing priority levels to be assigned to its interrupt outputs. 

INTERRUPT CONTROLLER INTERNALS

Delivering the interrupt from Interrupt controller to processor completes with Interrupt acknowledgement sequence. As a result Processor will be getting the IRQ number.

1. Eight interrupt lines IR0-IR7 are connected to the interrupt request register (IRR). The IRR is eight bits wide, where every bit corresponds to one of the lines IR0-IR7. The device requiring service signals the PIC via one of the eight pins IR0-IR7 setting it to a high level. The 8259A then sets the corresponding bit in the IRR.
2. At the same time, the PIC activates its output INT line to inform the processor about the interrupt request. The INT line is directly connected to the INTR input of the processor. This starts an interrupt acknowledge sequence.
3. The CPU receives the INT signal, finishes the currently executing instruction and outputs a first interrupt acknowledge (INTA) pulse if the IE flag is set (that is, if the interrupts are not masked at the CPU).
4. Upon receival of the first INTA pulse from the CPU the highest priority in the IRR register is cleared and the corresponding bit in the in-service register (ISR) register is set.There is no PIC activity on the data bus in this cycle.
5. The processor initiates a second INTA pulse and thus causes the 8259A to put an 8-bit number onto the data bus. This 8 bit number is the IRQ number. The CPU reads this number as the number of the interrupt handler to call, through IDT-Interrupt Descriptor Table, which is then fetched and executed.
6. In the Automatic End Of Interrupt (AEOI) Mode the ISR bit is reset at the end of the second INTA pulse. Otherwise, the CPU must issue an End of Interrupt (EOI) to the 8259A PIC when executing the interrupt handler to clear the ISR bit manually.

The above procedure will give you a clear picture on how Interrupt is routed from Peripheral device to the Processor.

***More to be posted on Interrupt descriptor Table and how OS handles it.