Showing posts with label systems. Show all posts
Showing posts with label systems. Show all posts

Saturday, February 4, 2012

Top and Bottom Halves

Source


10.4. Top and Bottom Halves

One of the main problems with interrupt handling is how to perform lengthy tasks
within a handlerOften a substantial amount of work must be done in response to
 a device interrupt, but interrupt handlers need to finish up quickly and not keep
interrupts blocked for long. These two needs (work and speed) conflict with each
other, leaving the driver writer in a bit of a bind. Linux (along with many other
systems) resolves this problem by splitting the interrupt handler into two halves.
The so-called top half is the routine that actually responds to the interrupt—the
one you register with request_irq. The bottom half is a routine that is scheduled
by the top half to be executed later, at a safer time. The big difference between the
top-half handler and the bottom half is that all interrupts are enabled during
execution of the bottom half—that's why it runs at a safer time. In the typical
scenario, the top half saves device data to a device-specific buffer, schedules its
bottom half, and exits: this operation is very fast. The bottom half then performs
whatever other work is required, such as awakening processes, starting up another
I/O operation, and so on. This setup permits the top half to service a new interrupt
while the bottom half is still working.
Almost every serious interrupt handler is split this way. For instance, when a
network interface reports the arrival of a new packet, the handler just retrieves
the data and pushes it up to the protocol layer; actual processing of the packet
is performed in a bottom half.
The Linux kernel has two different mechanisms that may be used to implement
bottom-half processing, both of which were introduced in Chapter 7. Tasklets are
often the preferred mechanism for bottom-half processing; they are very fast, but
all tasklet code must be atomic. The alternative to tasklets is workqueues, which
may have a higher latency but that are allowed to sleep.
The following discussion works, once again, with the short driver. When loaded with
a module option, short can be told to do interrupt processing in a top/bottom-half
mode with either a tasklet or workqueue handler. In this case, the top half executes
 quickly; it simply remembers the current time and schedules the bottom half
 processing. The bottom half is then charged with encoding this time and awakening
 any user processes that may be waiting for data.

10.4.1. Tasklets

Remember that tasklets are a special function that may be scheduled to run, in 
software interrupt context, at a system-determined safe time. They may be 
scheduled to run multiple times, but tasklet scheduling is not cumulative; the 
tasklet runs only once, even if it is requested repeatedly before it is launched.
 No tasklet ever runs in parallel with itself, since they run only once, but tasklets
 can run in parallel with other tasklets on SMP systems. Thus, if your driver has
 multiple tasklets, they must employ some sort of locking to avoid conflicting 
with each other.
Tasklets are also guaranteed to run on the same CPU as the function that first
schedules them. Therefore, an interrupt handler can be secure that a tasklet does
not begin executing before the handler has completed. However, another interrupt
can certainly be delivered while the tasklet is running, so locking between the
tasklet and the interrupt handler may still be required.
Tasklets must be declared with the DECLARE_TASKLET macro:
DECLARE_TASKLET(name, function, data);

name is the name to be given to the tasklet, function is the function that is called to
execute the tasklet (it takes one unsigned long argument and returns void), and
data is an unsigned long value to be passed to the tasklet function.
The short driver declares its tasklet as follows:
void short_do_tasklet(unsigned long);
DECLARE_TASKLET(short_tasklet, short_do_tasklet, 0);

The function tasklet_schedule is used to schedule a tasklet for running. 
If short is loaded with tasklet=1, it installs a different interrupt handler that 
saves data and schedules the tasklet as follows:
irqreturn_t short_tl_interrupt(int irq, void *dev_id, struct pt_regs *regs)
{
/* cast to stop 'volatile' warning */
do_gettimeofday((struct timeval *) tv_head);
short_incr_tv(&tv_head);
    tasklet_schedule(&short_tasklet);
    short_wq_count++; /* record that an interrupt arrived */
    return IRQ_HANDLED;
}

The actual tasklet routine, short_do_tasklet, will be executed shortly
(so to speak) at the system's convenience. As mentioned earlier, this routine
performs the bulk of the work of handling the interrupt; it looks like this:
void short_do_tasklet (unsigned long unused)
{
    int savecount = short_wq_count, written;
    short_wq_count = 0; /* we have already been removed from the queue */
    /*
     * The bottom half reads the tv array, filled by the top half,
     * and prints it to the circular text buffer, which is then consumed
     * by reading processes
     */

    /* First write the number of interrupts that occurred before this bh */
    written = sprintf((char *)short_head,"bh after %6i\n",savecount);
    short_incr_bp(&short_head, written);

    /*
     * Then, write the time values. Write exactly 16 bytes at a time,
     * so it aligns with PAGE_SIZE
     */

    do {
        written = sprintf((char *)short_head,"%08u.%06u\n",
                (int)(tv_tail->tv_sec % 100000000),
                (int)(tv_tail->tv_usec));
        short_incr_bp(&short_head, written);
        short_incr_tv(&tv_tail);
    } while (tv_tail != tv_head);

    wake_up_interruptible(&short_queue); /* awake any reading process */
}

Among other things, this tasklet makes a note of how many interrupts have
arrived since it was last called. A device such as short can generate a great
 many interrupts in a brief period, so it is not uncommon for several to arrive
before the bottom half is executed. Drivers must always be prepared for this
 possibility and must be able to determine how much work there is to perform 
from the information left by the top half.

10.4.2. Workqueues

Recall that workqueues invoke a function at some future time in the context
of a special worker process. Since the workqueue function runs in process
context, it can sleep if need be. You cannot, however, copy data into user
space from a workqueue, unless you use the advanced techniques we
demonstrate in Chapter 15; the worker process does not have access to any
other process's address space.
The short driver, if loaded with the wq option set to a nonzero value, uses a
workqueue for its bottom-half processing. It uses the system default workqueue,
so there is no special setup code required; if your driver has special latency
requirements (or might sleep for a long time in the workqueue function), you
may want to create your own, dedicated workqueue. We do need awork_struct
structure, which is declared and initialized with the following:
static struct work_struct short_wq;

    /* this line is in short_init(  ) */
    INIT_WORK(&short_wq, (void (*)(void *)) short_do_tasklet, NULL);

Our worker function is short_do_tasklet, which we have already seen in
the previous section.
When working with a workqueue, short establishes yet another interrupt
handler that looks like this:
irqreturn_t short_wq_interrupt(int irq, void *dev_id, struct pt_regs *regs)
{
    /* Grab the current time information. */
    do_gettimeofday((struct timeval *) tv_head);
    short_incr_tv(&tv_head);

    /* Queue the bh. Don't worry about multiple enqueueing */
    schedule_work(&short_wq);

    short_wq_count++; /* record that an interrupt arrived */
    return IRQ_HANDLED;
}

As you can see, the interrupt handler looks very much like the tasklet
version, with the exception that it calls schedule_work to arrange the
bottom-half processing.

    Monday, November 7, 2011

    How does gdb work ? part 1

    Source : http://www.alexonlinux.com/

    How debugger works

    Introduction

    In this article, I’d like to tell you how real debugger works. What happens under the hood and why it happens. We’ll even write our own small debugger and see it in action.

    I will talk about Linux, although same principles apply to other operating systems. Also, we’ll talk about x86 architecture. This is because it is the most common architecture today. On the other hand, even if you’re working with other architecture, you will find this article useful because, again, same principles work everywhere.

    Kernel support

    Actual debugging requires operating system kernel support and here’s why. Think about it. We’re living in a world where one process reading memory belonging to another process is a serious security vulnerability. Yet, when debugging a program, we would like to access a memory that is part of debugged process’s (debuggie) memory space, from debugger process. It is a bit of a problem, isn’t it? We could, of course, try somehow to use same memory space for both debugger and debuggie, but then what if debuggie itself creates processes. This really complicates things.

    Debugger support has to be part of the operating system kernel. Kernel able to read and write memory that belongs to each and every process in the system. Furthermore, as long as process is not running, kernel can see value of its registers and debugger have to be able to know values of the debuggie registers. Otherwise it won’t be able to tell you where the debuggie has stopped (when we pressed CTRL-C in gdb for instance).

    As we spoke about where debugger support starts we already mentioned several of the features that we need in order to have debugging support in operating system. We don’t want just any process to be able to debug other processes. Someone has to monitor debuggers and debuggies. Hence the debugger has to tell the kernel that it is going to debug certain process and kernel has to either permit or deny this request. Therefore, we need an ability to tell the kernel that certain process is a debugger and it is about to debug other process. Also we need an ability to query and set values from debuggie’s memory space. And we need an ability to query and set values of the debuggie’s registers, when it stops.

    And operating system lets us to do all this. Each operating system does it in it’s manner of course. Linux provides single system call named ptrace() (defined in sys/ptrace.h), which allows to do all these operations and much more.

    ptrace()

    ptrace() accepts four arguments. First is one of the values from enum __ptrace_requestthat defined in sys/ptrace.h. This argument specifies what operation we would like to do, whether it is reading debuggie registers or altering values in its memory. Second argument specifies pid of the debuggie process. It’s not very obvious, but single process can debug several other processes. Thus we have to tell exactly what process we’re referring. Last two arguments are optional arguments for the call.

    Starting to debugBACK TO TOC

    One of the first things debuggers do to start debugging certain process is attaching to it or running it. There is a ptrace() operation for each one of these cases.

    First called PTRACE_TRACEME, tells the kernel that calling process wants its parent to debug itself. I.e. me calling ptrace( PTRACE_TRACEME ) means I want my dad to debug me. This comes handy when you want debugger process to spawn the debuggie. In this case you do fork() creating a new process, then ptrace( PTRACE_TRACEME ) and then you call exec() or execve().

    Second operation called PTRACE_ATTACH. It tells the kernel that calling process should become debugging parent of the process being called. Debugging parent means debugger and a parent process.

    Debugger-debuggie synchronizationBACK TO TOC

    Alright. Now we told operating system that we are going to debug certain process. Operating system made it our child process. Good. This is a great time for us to have the debuggie stopped and us doing preparations before we actually start to debug. We may want to, for instance, analyze executable that we run and place a breakpoints before we actually start debugging. So, how do we stop the debuggie and let debugger do its thing?

    Operating system does that for us using signals. Actually, operating system notifies us, the debugger, about all kinds of events that occur in debuggie and it does all that with signals. This includes the “debuggie is ready to shoot” signal. In particular, if we attach to existing process it receives SIGSTOP and we receive SIGCHLD once it actually stops. If we spawn a new process and it did ptrace( PTRACE_TRACEME ) it will receive SIGTRAP signal once it attempts to exec() or execve(). We will be notified with SIGCHLD about this, of course.

    A new debugger was bornBACK TO TOC

    Now lets see code that actually demonstrates that. Complete listing can be found here.

    The debuggie does the following…

    01.
    02.
    03.
    04 if (ptrace( PTRACE_TRACEME, 0, NULL, NULL ))
    05 {
    06 perror( "ptrace" );
    07 return;
    08 }
    09
    10 execve( "/bin/ls", argv, envp );
    11.
    12.
    13.

    Note the ptrace( PTRACE_TRACEME ) followed by execve(). This is what real debuggers do to spawn the process that going to be debugged. As you know, execve() replaces current executable image and memory of the current process with the executable and memory space belonging to program that being execve()‘d. Once kernel finishes this operation, it sends SIGTRAP to calling process and SIGCHLD to the debugger. The debugger receives appropriate notifications via signals and via wait() that returns. Here is the debugger’s code.

    01.
    02.
    03.
    04 do {
    05 child = wait( &status );
    06 printf( "Debugger exited wait()\n" );
    07 if (WIFSTOPPED( status ))
    08 {
    09 printf( "Child has stopped due to signal %d\n",
    10 WSTOPSIG( status ) );
    11 }
    12 if (WIFSIGNALED( status ))
    13 {
    14 printf( "Child %ld received signal %d\n",
    15 (long)child,
    16 WTERMSIG(status) );
    17 }
    18 } while (!WIFEXITED( status ));
    19.
    20.
    21.

    Compiling and running listing1.c produces following output:

    1In debuggie process 14095
    2In debugger process 14094
    3Process 14094 received signal 17
    4Debugger exited wait()
    5Child has stopped due to signal 5

    Here we can clearly see that debugger indeed receives a signal and gets notified via wait(). If we want to place a breakpoint before we start to debug the process, this is our chance. Lets talk about how we can do something like that.