Top and Bottom halves in Interrupts in kernel

For most UNIX systems, Linux included, device drivers typically divide the work of processing interrupts into two parts or halves. The first part, the top half, is the familiar interrupt handler, which the kernel invokes in response to an interrupt signal from the hardware device. Unfortunately, the interrupt handler is true to its name: it interrupts whatever code is executing when the hardware device issues the interrupt. That is, interrupt handlers (top halves) run asynchronously with respect to the currently executing code. Because interrupt handlers interrupt already executing code (whether it is other kernel code, a user-space process or even another interrupt handler), it is important that they run as quickly as possible.

Worse, some interrupt handlers (known in Linux as fast interrupt handlers) run with all interrupts on the local processor disabled. This is done to ensure that the interrupt handler runs without interruption, as quickly as possible. More so, all interrupt handlers run with their current interrupt line disabled on all processors. This ensures that two interrupt handlers for the same interrupt line do not run concurrently. It also prevents device driver writers from having to handle recursive interrupts, which complicate programming. If interrupts are disabled, however, other interrupt handlers cannot run. Interrupt latency (how long it takes the kernel to respond to a hardware device's interrupt request) is a key factor in the performance of the system. Again, the speed of interrupt handlers is crucial.

To facilitate small and fast interrupt handlers, the second part or bottom half of interrupt handling is used to defer as much of the work as possible away from the top half and until a later time. The bottom half runs with all interrupts enabled. Therefore, a running bottom half does not prevent other interrupts from running and does not contribute adversely to interrupt latency.

Nearly every device driver employs bottom halves in one form or another. The device driver uses the top half (the interrupt handler) to respond to the hardware and perform any requisite time-sensitive operations, such as resetting a device register or copying data from the device into main memory. The interrupt handler then marks the bottom half, instructing the kernel to run it as soon as possible, and exits.

In most cases, then, the real work takes place in the bottom half. At a later point—often as soon as the interrupt handler returns—the kernel executes the bottom half. Then the bottom half runs, performing all of the remaining work not carried out by the interrupt handler. The actual division of work between the top and bottom halves is a decision made by the device driver's author. Generally, device driver authors attempt to defer as much work as possible to the bottom half.

Confusingly, Linux offers many mechanisms for implementing bottom halves. Currently, the 2.6 kernel provides softirqs, tasklets and work queues as available types of bottom halves. In previous kernels, other forms of bottom halves were available; they included BHs and task queues. This article deals with the new work queue interface only, which was introduced during the 2.5 development series to replace the ailing keventd part of the task queue interface.

Read more »

NAND and NOR Flash Memory Differences

NOR and NAND technologies dominate today's nonvolatile flash memory market. NORflash, first introduced by Intel in 1988, revolutionized the market formerly dominated by EPROM- and EEPROM-based devices.

The introduction of Toshiba's NAND flash architecture in 1989, addressed the need for lower cost per bit, higher-performance, and disk-like memory with a consistent interface for easy upgrade.

A feature of NOR is eXecute In Place (XIP), which allows an application to be run directly from flash instead of reading the application code into system RAM. NOR delivers high read performance and is most cost effective in lower capacities--1 to 4 Mbytes--but suffers from extremely low write-and-erase performance.

NAND architecture competes by offering extremely high cell densities that translate to high storage capacity, combined with fast write and erase rates. The difficulty using NAND revolves around the need for flash management and special requirements for system interface.

Performance

Flash memory is nonvolatile memory that can be erased and reprogrammed in units of memory called blocks. A write operation in any flash device can only be performed on an empty/erased unit, so in most cases an erase operation must precede the write operation. The erase operation is fairly straightforward for NAND devices, whereas NOR technology mandates that all bytes in the target block be written with zeros before they can be erased.

Since the size of an erase block in NOR ranges from 64 to 128 Kbytes, such a write/erase operation can take up to 5 s. By contrast, using erase blocks 8 to 32 Kbytes in size, NAND performs the identical operation in a maximum of 4 ms.

The erase block-size difference further increases the performance gap between NOR and NAND, as statistically more erase operations must be performed in NOR-based units per any given set of write operations (especially when updating small files). Therefore, when selecting a local storage solution, designers need to weigh the following factors:

• NOR reads slightly faster than NAND.

• NAND writes significantly faster than NOR.

• NAND erases much faster than NOR--4 ms vs. 5 s, respectively.

• Most writes require a preceding erase operation.

• NAND has smaller erase units, so fewer erases are needed.

Capacities and cost

The cell size of NAND flash is almost half the size of a NOR cell. In combination with a simpler production process, NAND architecture can be offered with higher capacity for a given die size, resulting in a lower price tag.

NOR flash dominates the market in memory capacity ranging between 1 and 16 Mbytes, while NAND flash is used in capacity ranges between 8 to 128 Mbytes. This again stresses the roles of NOR devices as a code-storage media and NAND devices as ideal for data storage--NAND has its strongest market presence in the memory card market (CompactFlash, Secure Digital, PC Cards, and MMC).

Reliability and endurance

One of the main considerations of working with flash media is its reliability. Flash is the preferred storage solution for systems in need of extended MTBF. Comparison of reliabilities between NOR and NAND architectures breaks down into three main factors--life span (endurance), bit flipping, and bad-block handling.

Life span (endurance)

The maximum allowed number of erase cycles per erase block in a NAND device is one million cycles, compared with 100,000 cycles for a NOR device. In addition to the 10-to-1 block-erase-cycle advantage of NAND memory devices, the typical NAND block size itself is about 8 times smaller than that of a NOR device--eachNAND memory block will be erased fewer times over a given period of time.

Bit flipping

All flash architectures today suffer from a phenomenon known as "bit flipping."On some occasions (rare, yet more common in NAND than in NOR), a bit either gets reversed or is reported reversed.

One bit change may seem insignificant, but this minor glitch may hang the system altogether if it corrupts a critical file. When the problem is just one of reporting, repeating the read operation may solve it.

However, if the bit has actually been changed, an error detection/error correction (EDC/ECC) algorithm must be applied. Problems associated with bit flipping are more common with NAND devices than NOR and all NAND vendors now recommend using an EDC/ECC algorithm with their devices.

This problem is not as critical when using NAND to store multimedia information. However, when used as a local storage device storing the operatingsystem, configuration files, or other sensitive information, an EDC/ECC system must be implemented to ensure reliability.

Bad-block handling

NAND devices are shipped with bad blocks randomly scattered within them. An early attempt to ship NAND devices free of bad blocks was found not to be economically practical due to the very high price tag caused by low-production yield rates.

NAND devices require an initial scanning of the media for bad blocks, which aremapped as unusable. Failing to perform this process in a reliable way results in high-failure rates in the finished device.

Ease of use

Using a NOR-based flash is a straightforward process. It is connected like other memory devices, and code can be run directly from it.

NAND, however, is complicated with its requirement for an I/O interface. Accessing rules for NAND interfaces may differ depending on the NAND vendor.

A driver must be written and used for performing any operation on a NAND device. Writing information to a NAND device is a particularly tricky issue, since the designer must not write to a bad block--meaning that virtual mapping must be implemented on NAND devices at all times.

Software support

When discussing software support, two levels of support are distinguished: basic for read/write/erase operations and high level software for disk emulation and flash management algorithms--including performance optimization.

Running code from NOR devices requires no special software support. Doing the same thing in NAND requires a driver, usually referred to as a memorytechnology driver (MTD). Both NAND and NOR require MTDs for write and erase operations.

Working with NOR does not require much more than MTDs. Higher-level software is available for NOR devices from many vendors, including M-Systems' TrueFFS drivers--used by vendors such as Wind River Systems, Microsoft, QNX Software Systems, Symbian, and Intel.

The drivers also implemented in the company's DiskOnChip products provide both disk emulation and NAND flash management, including bit-error correction, bad-block handling, and wear leveling.

NOR-NAND comparison

PARAMETER	NOR	NAND
Capacity	1 to 16 Mbytes	8 to 128 Mbytes
XIP (code execution)	Yes	No
Performance Erase Write Read	Very Slow (5 s) Slow Fast	Fast (3 ms) Fast Fast
Strengths	Addressable to every byte	More than 10% higher life expectancy
Erase cycle range	10,000 to 100,000	100,000 to1,000,000
Interface	SRAM-like, memory mapped	Accessed in bursts of 512 bytes; I/O mapped
Access method	Random	Sequential
Price	High	Very low

Read more »

Interview questions on c part-8

8.1: What's wrong with this code?
char c;
while((c = getchar()) != EOF) ...

A: For one thing, the variable to hold getchar's return value must be an int. getchar() can return all possible character values, as well as EOF. By passing getchar's return value through a char, either a normal character might be misinterpreted as EOF, or the EOF might be altered (particularly if type char is unsigned) and so never seen.

8.2: Why does the code
while(!feof(infp)) {
fgets(buf, MAXLINE, infp);
fputs(buf, outfp);
}
copy the last line twice?

A: In C, EOF is only indicated *after* an input routine has tried to read, and has reached end-of-file. (In other words, C's I/O is not like Pascal's.) Usually, you should just check the return value of the input routine (fgets() in this case); often, you don't need to use feof() at all.

8.3: My program's prompts and intermediate output don't always show up
on the screen, especially when I pipe the output through another program.

A: It's best to use an explicit fflush(stdout) whenever output should definitely be visible. Several mechanisms attempt to perform the fflush() for you, at the "right time," but they tend to apply only when stdout is an interactive terminal.

8.4: How can I print a '%' character in a printf format string? I tried \%, but it didn't work.

A: Simply double the percent sign: %% . \% can't work, because the backslash \ is the *compiler's* escape character, while here our problem is that the % is printf's escape character.

8.5: Someone told me it was wrong to use %lf with printf(). How can
printf() use %f for type double, if scanf() requires %lf?

A: It's true that printf's %f specifier works with both float and double arguments. Due to the "default argument promotions" (which apply in variable-length argument lists such as printf's, whether or not prototypes are in scope), values of type float are promoted to double, and printf() therefore sees only doubles.

8.6: How can I print numbers with commas separating the thousands?
What about currency formatted numbers?

A: The routines in begin to provide some support for these operations, but there is no standard routine for doing either task. (The only thing printf() does in response to a custom locale setting is to change its decimal-point character.)

8.7: Why doesn't the call scanf("%d", i) work?

A: The arguments you pass to scanf() must always be pointers. To fix the fragment above, change it to scanf("%d", &i) .

8.8: Why doesn't this code:
double d;
scanf("%f", &d);
work?

A: Unlike printf(), scanf() uses %lf for values of type double, and %f for float.

8.9: How can I specify a variable width in a scanf() format string?

A: You can't; an asterisk in a scanf() format string means to suppress assignment. You may be able to use ANSI stringizing and string concatenation to accomplish about the same thing, or to construct a scanf format string on-the-fly.

8.10: When I read numbers from the keyboard with scanf "%d\n", it seems
to hang until I type one extra line of input.

A: Perhaps surprisingly, \n in a scanf format string does *not* mean to expect a newline, but rather to read and discard characters as long as each is a whitespace character.

8.11: I'm reading a number with scanf %d and then a string with gets(), but the compiler seems to be skipping the call to gets()!

A: scanf %d won't consume a trailing newline. If the input number is immediately followed by a newline, that newline will immediately satisfy the gets().As a general rule, you shouldn't try to interlace calls to scanf() with calls to gets() (or any other input routines); scanf's peculiar treatment of newlines almost always leads to trouble. Either use scanf() to read everything or nothing.

8.12: I figured I could use scanf() more safely if I checked its return value
to make sure that the user typed the numeric values I expect, but
sometimes it seems to go into an infinite loop.

A: When scanf() is attempting to convert numbers, any non-numeric characters it encounters terminate the conversion *and are left on the input stream*. Therefore, unless some other steps are taken, unexpected non-numeric input "jams" scanf() again and again: scanf() never gets past the bad character(s) to encounter later, valid data. If the user types a character like `x' in response to a numeric scanf format such as %d or %f, code that simply re-prompts and retries the same scanf() call will immediately reencounter the same `x'.

8.13: Why does everyone say not to use scanf()? What should I use
instead?

A: scanf() has a number of problems -- %s format has the same problem that gets() has -- it's hard to guarantee that the receiving buffer won't overflow. More generally, scanf() is designed for relatively structured, formatted input (its name is in fact derived from "scan formatted"). If you pay attention, it will tell you whether it succeeded or failed, but it can tell you only approximately where it failed, and not at all how or why. It's nearly impossible to do decent error recovery with scanf(); usually it's far easier to read entire lines (with fgets() or the like), then interpret them, either using sscanf() or some other techniques. (Routines like strtol(), strtok(), and atoi() are often useful; If you do use sscanf(), don't forget to check the return value to make sure that the expected number of items were found.

8.14: How can I tell how much destination buffer space I'll need for an
arbitrary sprintf call? How can I avoid overflowing the destination buffer
with sprintf()?

A: There are not (yet) any good answers to either of these excellent questions, and this represents perhaps the biggest deficiency in the traditional stdio library. When the format string being used with sprintf() is known and relatively simple, you can usually predict a buffer size in an ad-hoc way. If the format consists of one or two %s's, you can count the fixed characters in the format string yourself (or let sizeof count them for you) and add in the result of calling strlen() on the string(s) to be inserted. You can conservatively estimate the size that %d will expand to with code like:
#include // here stdio.h
char buf[(sizeof(int) * CHAR_BIT + 2) / 3 + 1 + 1];
sprintf(buf, "%d", n);
(This code computes the number of characters required for a base- 8 representation of a number; a base-10 expansion is guaranteed to take as much room or less.) When the format string is more complicated, or is not even known until run time, predicting the buffer size becomes as difficult as reimplementing sprintf(), and correspondingly error-prone (and inadvisable). A last-ditch technique which is sometimes suggested is to use fprintf() to print the same text to a bit bucket or temporary file, and then to look at fprintf's return value or the size of the file.If there's any chance that the buffer might not be big enough, you won't want to call sprintf() without some guarantee that the buffer will not overflow and overwrite some other part of memory. Several stdio's (including GNU and 4.4bsd) provide the obvious snprintf() function, which can be used like this:
snprintf(buf, bufsize, "You typed \"%s\"", answer);
and we can hope that a future revision of the ANSI/ISO C Standard will include this function.

8.15: Why does everyone say not to use gets()?

A: Unlike fgets(), gets() cannot be told the size of the buffer it's to read into, so it cannot be prevented from overflowing that buffer. As a general rule, always use fgets(). For a code fragment illustrating the replacement of gets() with fgets().

8.16: Why does errno contain ENOTTY after a call to printf()?

A: Many implementations of the stdio package adjust their behavior slightly if stdout is a terminal. To make the determination, these implementations perform some operation which happens to fail (with ENOTTY) if stdout is not a terminal. Although the output operation goes on to complete successfully, errno still contains ENOTTY. (Note that it is only meaningful for a program to inspect the contents of errno after an error has been reported.)

8.17: What's the difference between fgetpos/fsetpos and ftell/fseek? What
are fgetpos() and fsetpos() good for?

A: fgetpos() and fsetpos() use a special typedef, fpos_t, for representing offsets (positions) in a file. The type behind this typedef, if chosen appropriately, can represent arbitrarily large offsets, allowing fgetpos() and fsetpos() to be used with arbitrarily huge files. ftell() and fseek(), on the other hand, use long int, and are therefore limited to offsets which can be represented in a long int.

8.18: How can I flush pending input so that a user's typeahead isn't read at the next prompt? Will fflush(stdin) work?

A: fflush() is defined only for output streams. Since its definition of "flush" is to complete the writing of buffered characters (not to discard them), discarding unread input would not be an analogous meaning for fflush on input streams. There is no standard way to discard unread characters from a stdio input stream, nor would such a way be sufficient unread characters can also accumulate in other, OS-level input buffers.

8.19: I'm trying to update a file in place, by using fopen mode "r+", reading a certain string, and writing back a modified string, but it's not working.

A: Be sure to call fseek before you write, both to seek back to the beginning of the string you're trying to overwrite, and because an fseek or fflush is always required between reading and writing in the read/write "+" modes. Also, remember that you can only overwrite characters with the same number of replacement characters;

8.20: Once I've used freopen(), how can I get the original stdout (or stdin)back?

A: There isn't a good way. If you need to switch back, the best solution is not to have used freopen() in the first place. Try using your own explicit output (or input) stream variable, which you can reassign at will, while leaving the original stdout (or stdin) undisturbed.

8.21: How can I read a binary data file properly? I'm occasionally seeing
0x0a and 0x0d values getting garbled, and it seems to hit EOF prematurely
if the data contains the value 0x1a.

A: When you're reading a binary data file, you should specify "rb" mode when calling fopen(), to make sure that text file translations do not occur. Similarly, when writing binary data files, use "wb". Note that the text/binary distinction is made when you open the file: once a file is open, it doesn't matter which I/O calls you use on it.

Read more »