Getting the Tools

You can download the source code for binutils and gcc and build the tool chain yourself. This can often be very tricky and takes many separate stages (consider the problem of creating a compiler without first having a compiler). There are a number of scripts that greatly simplify the generation of the tool chain. At the time of writing, the crosstool-NG is a good option if you just require a tool chain. It cross-builds the tool chain for all architectures supported by GCC. The ct-ng menuconfig line is where you select the target CPU architecture. Below is a Mercurial source code control command to get the source from the source repository system.

>hg clone http://crosstool-ng.org/hg/crosstool-ng

>./configure --prefix=/some/place>make

>make install

>export PATH="${PATH}:/some/place/bin"

>cd /your/development/directory

>ct-ng help

>ct-ng menuconfig

>ct-ng build

There are four key attributes of the target tool chain that must be selected:

The output of the build process is placed in your home directory in an x-tools folder. Each tool chain that you select is placed in a configuration specific folder. For example, a generic IA-32 tool chain is placed in the ~/x-tool/i386-unknown-elf/ folder, and a generic ARM tool chain is placed in ~/x-tools/arm-unknown-eabi folder. In addition to the target architectures, the target application binary interface must also be selected for the tool chain to use. The ABI defines all semantics associated with the construction of binary objects, libraries, interfunction calling mechanisms, calls to operating system services, register usage, and the like.

There are two versions of ABIs in use on IA-32 systems, a 32-bit and a 64-bit version. The 32-bit version of standard can be found at http://www.sco.com/developers/devspecs/abi386-4.pdf and the 64-bit version http://www.x86-64.org/documentation/abi.pdf.

The default ARM tool chain application binary interface is the Embedded Application Binary Interface (EABI). It defines the conventions for files, data types, register mapping, stack frame and parameter passing rules. The EABI is commonly used on ARM and PowerPC CPUs. The ARM EABI specification can be found at http://www.arm.com.

The primary object format is defined by the Tool Interface Standard – Executable and Linking Format (ELF) (http://refspecs.freestandards.org/elf/elf.pdf.) The standard is composed of books that define the generic ELF format, along with extensions of processor architectures and target operating systems.

In some cases, there is no target operating system specified or used; this is in effect a generic target. Most tool chains support a non-OS-specific processor-specific target option. This is sometimes known as bare metal.

Tools Overview

The tools used/required in embedded systems go beyond the traditional compiler and linker. There are a number of cross-development tools generated that are part of the GCC family, as shown in Table 8.1. A review follows of the capabilities of each tool and what each is used for.

Table 8.1. Cross-Tool Chain Programs.

The most commonly used programs for an embedded developer are set in boldface in the table, namely, ar, as, gcc, ld, and objdump.

Once you have acquired the appropriate tools, make sure you set the path to them and archive a copy when you release your software.

Kernel Build

Building the Linux kernel from source is a relatively straightforward process. You must first download the entire source tree for the Linux kernel. The kernel source tree consists of all the source code for the kernel and device drivers for all supported processor architectures. The original kernel was developed to support 32-bit IA-32-based systems (starting with the 80386). At this point it supports all Intel architectures from the 80486, Intel Atom, Intel Core™ family, and Intel Xeon™—in both 32-bit and 64-bit modes. The kernel itself is remarkably portable, and at the time of writing the kernel source tree supports the following systems in additional to the IA-32-based platforms: Alpha^™, AXP^™, Sun Spark^™, Motorola 68000^™, PowerPC, ARM, Hitachi SuperH^™, IBM S/390/ MIPS, HP PA-RISC^™, AMD IA-32-64^™, ASOC CRIS^™, Renesas M32R^™, Atmel AVR32^™, Renesas H8/300^™, NEC V850^™, Tensilca Xtensa^™, and Analog Device Blackfin^™ architectures.

In addition to specifying the processor architecture that the kernel supports, specific platforms or boards are also supported in the source tree. In general, the vast majority of IA-32-based platforms are supported by default (primarily due to the platform level consistency of all IA-32 platforms). The IA-32 processor-specific source is primarily found in linux-2.6.38.4/arch/IA-32. For non-IA-32 architecture, the source tree usually contains a directory entry for the SOC along with board-specific variants. For example, the XScale IPX400 BSP code is primarily located in the linux-2.6.38.4/arch/arm/mach-ixp4xx/.

Another key directory in the kernel tree is the linux-2.6.38.4/drivers tree. This portion of the source tree provides device drivers. Depending the architecture, the drivers required to support an SOC device may be in the driver tree area or within the platform directories. Figure 8.2 shows a selection of the kernel source tree most likely to be updated for platform or processor changes.

FIGURE 8.2 Sample Directories in the Kernel Tree.

Kernel Options

There is a wide range of kernel configuration items that can be selected prior to the build phase. The build system is controlled by the contents of a .config file in the root directory of the kernel tree. The configuration file itself can be generated by issuing the make menuconfig command. The configuration items can be selected using the menus presented.

Figure 8.3 shows the initial screen for the make menuconfig. If you simply select exit, the command will generate the default kernel configuration. There are other graphics variants that you can use to configure the kernel make xconfig and make gconfig, which just use different graphics tools kits for the menu structure.

FIGURE 8.3 Screenshot of make menuconfig Command.

The default .config file can also be created by issuing the make defconfig command.

There is truly a very large number of configuration items; the default .config currently has over 5000 entries. You should not directly edit the .config file; you should use the configuration tools to make such modifications, because the configuration tool ensures that any dependent configuration items are also configured appropriately. Making direct modifications to the .config file may result in a configuration that fails to build or even crashes at runtime.

There are three types of options generated in the configuration (.config) file.

Changing a configuration option is as simple as selecting the required option in the configuration tool prior to building the kernel.

The design pattern for configuring the behavior of the system in a static manner by setting compile time variables in a configuration file is a common one. Kernel or driver code must use the resultant #defines to alter the behavior of the kernel at compile time. There are also runtime controls that may change the behavior of the system. In the case of ARM BSPs, for each ARM platform there are platform-specific definitions that are generated from definitions in the file linux/arch/arm/tools/mach-type. For example, on an XScale Intel IXP435 BSP the following run/configuration values are created:

The bzimage file consists of a compressed kernel and startup code that is used to decompress the kernel image. The map file is created for the compressed kernel image when it is decompressed into memory (shown in Figure 8.4). A map file is a list of addresses and an associated program symbols. The Linux kernel map file is system.map.

FIGURE 8.4 Linux Compressed Images.

If you have ever booted a Linux kernel, especially on an embedded system, you may have seen a series of dots on the screen (“....”). This is the decompression phase of the boot sequence.

There are two reasons to compress the kernel image (and initial RAM file system). The first reason is to save on the storage requirements for the kernel. In embedded systems the kernel is usually stored on a flash device (although general mass storage is also an option). The second reason to use compression is boot speed; a compressed kernel requires less I/O to get it off the storage device into memory, and the decompression carried out by the CPU runs quickly. The time taken to read and decompress a compressed image is less than the time to read a larger uncompressed image.

There are also options in many embedded systems to keep the image uncompressed and run the kernel from flash without first copying to memory. This is known as execute in place (XIP). XIP saves overall RAM as the kernel remains on flash; however, since the flash image is not compressed, it requires additional flash space. The performance of such systems is often lower than non XIP based systems as read access times to flash memory are typically slower than those of DRAM.

Root File System Build

The root file system is the file system you will see if you launch a shell or login to a Linux-based system (host or target) and then change directory to the root via the command

cd /

The file system layout in most cases will follow the layout defined by the Filesystem Hierarchy Standard (FHS). The FHS is standardized as part of the Linux Standard Base (LSB) (http://refspecs.linuxfoundation.org/fhs.shtm). If a distribution indicates that it is compliant with an LSB version, then the file system layout will also follow the specified FHS. In many embedded systems, the FHS is not followed exactly, as the root file system is trimmed significantly.

Creating a root file system for a full distribution is a very challenging task. The distribution could contain thousands of packages, all of which must be selected to ensure that all of the dependences and versions are correctly aligned. If your embedded system requires a significant number of packages and capabilities such as a window manager, graphics frameworks, and so on, you should start from an existing distribution. Meego, Yocto Linux, or Open Embedded would be good starting points for a sophisticated multimedia embedded platform. There are, of course, a number of commercially supported embedded distributions that are available, such as MontaVista Linux and Wind River Linux, all such distributions provide tools to build the root file system and manage the contents of the root file system (with an aim to tune the contents of the file system).

The FHS based file system follows the directory layout below:

In embedded systems it is best to combine the root file system directly with the kernel image. This allows the system to boot quickly, and given that it is linked with the kernel, it can provide capabilities such as loadable kernel modules before a traditional file system is available. In many embedded cases, this is the only file system that is required and no further file system need be mounted.

In this configuration selected below the initial root file system is compressed and integrated into the kernel. The file system is decompressed and mounted as a RAM disk during kernel initialization. Having the kernel and file system in one image has advantages in managing/deploying the images for the embedded system. However, if the file system must be updated, the kernel must also be rebuilt and upgraded.

The Linux kernel has a built-in option to build a file system for inclusion into the kernel. The option is known as “Initial RAM File system and RAM disk.” The option takes a configuration file that describes the file system as shown in Figure 8.5.

FIGURE 8.5 Kernel Configuration for an Initial RAM File System.

The initial RAM disk is available very early on in the boot sequence and is described in kernel/ documentation/early-userspace/README. The kernel build takes an argument to a configuration file. The configuration file is a list of entries that create the underlying file system. The following is a list of commands that are used to define the layout of the initial ram disk.

While building the initial root file system into the kernel image has advantages, in many cases the system must mount a larger file system from a mass storage device. The kernel must include the file system driver applicable to the file system format used on the mass storage device. In order to switch the root file system from the RAM disk mounted during boot to the other mass storage based root file system we must perform a pivot root. This mounts a new root file system.

int

pivot_root(const char ∗new_root, const char ∗put_old);

Once the initial RAM disk root file system is up, the kernel executes /init as its first process. The init execute may be a binary or script. If the busybox init is used, it will search for scripts at defined locations and execute them. If required, this script should perform the root pivot.

The standard desktop system (for example, Ubuntu) also uses an initial RAM file system. The boot loader in the system (such as grub2) takes augments to the kernel and initial RAM file system to load. If you look in the root directory you will find a vmlinux and initd.img file (these are actually links to the files in /boot directory or partition.). When the vmlinumx and initd images are loaded by the boot loader, the boot loader must support the file system, on which these files are stored. This can often be problematic in some embedded systems, as the boot loader (for example, Das UBOOT) needs to support the file system used; this entails duplicate development of file system support in the boot loader and the kernel. As mentioned above, it is beneficial to link the kernel and initial root file system into a single image; this image can be stored in a simple file system, which is easily supported by the boot loader. The more sophisticated file systems such as EXT3 are supported by the kernel, this alleviates the need to develop separate code to support file system for the boot loader and kernel. It can also be difficult to reuse kernel code in a boot loader, they are often released under different licence models which precludes the reuse of kernel code in the boot loader.

You can use a platform emulator (on your host machine) such as QEMU to load the kernel and initial RAM disk. For example, take a copy of the kernel and initrd file into a local directory, then issue the command

>qemu –kenrel vmlinux –initrd initrd.img

The kernel will boot up and load the file system. It will then probably fail because there is no root file system/hard drive assigned to the qemu.

Busybox

No discussion of embedded Linux can take place without also mentioning Busybox. The most widely used shell commands in an embedded system are provided by Busybox (http://www.busybox.net/):

Busybox combines tiny versions of many common UNIX utilities into a single small executable. It provides replacements for most of the utilities you usually find in GNU fileutils, shellutils, etc. The utilities in Busybox generally have fewer options than their full-featured GNU cousins; however, the options that are included provide the expected functionality and behave very much like their GNU counterparts. Busybox provides a fairly complete environment for any small or embedded system.

The Busybox is a single statically linked executable. Each Busybox command is created by creating a link to the Busybox executable. When the command executes, the first argument passed to program is the name of the executable. When busy box executes, the name of the executable is passed as the first argument to the executable, and as a result the Busybox image can select the appropriate behavior to provide.

There is significant space saving by using one executable to provide multiple shell commands. Each executable has a fixed overhead that would be replicated to every command. In this case, it is over 600KBytes per executable if statically linked, and 7KBytes per command if the executable were dynamically linked. A static linked file means that all of the required code is placed into the binary— that’s all the startup code and library functions used—whereas a dynamically linked executable only has the application code (with some minimal startup code). The library code is loaded on demand as needed from shared libraries.

C Library

One of the key libraries in any system is the standard C library, often known simply as libc. The standard C library provides functions that are available to all C programs (and some other language bindings use the library). The library provides implementations of functions such as input/output (printf, open) and string handling functions (strlen). The international C Standard (C99) is maintained by the ISO under the ISO/IEC 9899:1999 standard.

There are many implementations of the standard C library to choose from, especially for embedded systems. The most commonly used implementation is that provided by the GNU C Library. This is a comprehensive implementation that provides all the functions defined in the standard. In fact, it complies with ISO C99, POSIX.1c, POSIX.1j, POSIX.1d, Unix98, and Single Unix Specification standards.

Given that GLIBC is so comprehensive, it can be considered too large for use in an embedded system. As a result, there are a number of lighter variants available. These variants usually remove some features not generally required by most applications. In some cases applications will need to be modified to use these embedded variants of the C library due to missing capabilities, but every effort is made to reduce the impact of such changes.

The Embedded GLIBC is a variant of the GLIBC. It is defined for use on embedded systems. It has a reduced footprint (to that of GLIBC) and provides the capability to configure individual components within the library. This is a good choice for larger embedded systems where most C library functions are required. EGLIBC strives to be both source and binary compatible with GLIBC.

Another popular C library is uClibc (μClibc). It is much smaller than the GLIBC and most functions are supported. In many cases just recompilation is required, so it is source code compatible but not necessarily binary compatible.

The core operating system within Android^™ is a Linux variant. Google choose to use the Bionic C library. The library is a derivative of the original BSD standard C library. The library is not as fully featured as GLIBC. The objective in using Bionic was stated as

License: Google stated they wish to keep GPL licensed code out of the user space; Bionic uses BSD license. Size: The goal was to create a much library smaller than GLIBC, approx. ½ size of GLIBC; and speed: Allowing speed optimizations, e.g., a fast threading API (from http://www.youtube.com (17:50), Google I/O 2008 – Anatomy and Physiology of an Android).

The Bionic library is not compatible with GLIBC. All Android native code must be recompiled against Bionic. Native code will need to be updated if porting from a traditional Linux system where it uses GLIBC features which are not available in Bionic.

Boot Sequence

The Linux boot sequence is substantially more involved than that of a simple RTOS boot sequence. In the case of an RTOS it is not unusual to link the application and the kernel and even boot loader into a single monolithic image. The linking process binds both (or all three) components together. In fact, this configuration is a common one used in the deployments of the VxWorks operating system; the image contains the code required to boot up, decompress the kernel, and call an application entry point, which then starts all of the threads that are required for the application.

In the case of Linux, the system consists of four distinct capabilities that are sometimes merged, but not usually for IA-32 systems:

The following is the sequence of events on an IA-32 embedded boot flow.

The init program or script is the first user space program that will be executed. The process id given to this process is 1, as can be seen by the following command:

$ ps -ef

UID  PID PPID C STIME TTY TIME   CMD

root 1   0  0 May14 ?  00:00:01 /sbin/init

The init could execute traditional bring-up scripts (as you may be familiar with in a desktop distribution, such as /etc/init.d files), or it could be an application binary that you create to run just one special dedicated application—the choice is yours as an embedded developer. Having said that, it is really convenient for debug and development if you can start a login console (using the normal init scripts).

While developing a system it can be very convenient to mount a network file system during boot. In this case the RAM disk would mount an NFS remote partition and then perform the root pivot. The hosting system simply exports a directory on the host, which becomes the root file system on the target. This allows you to build and update applications on the target root file system very easily. You don’t have to perform any special download to the target; updates to the NFS mounted directory on the host are immediately available on the target device.

Debugging Applications

Debugging applications is relatively straightforward. There are a number of user space debuggers available. The GNU debugger, GDB (http://www.gnu.org/software/gdb/), is still ubiquitous. GDB provides native and cross-platform debug capabilities (between host and target). GDB can be a little tricky to get used to at first, but there are many GUI wrappers to improve its usability. There are some very powerful features in GDB such as reverse debugging—this is where you can run your program backwards to help find a bug—and it is also effective for debugging multithread applications. Examples of such GUI wrappers are DDD and the KDE GDB – kdbg. There are also full-fledged IDEs such as KDevelop and Eclipse-based development environments that you can use. The Eclipse platform is very extensible and supports development in source languages (C, C++, Java etc.) languages. The C/C++ development environment is known as the Eclipse C/C++ Development tool. Figure 8.6 shows a snapshot of the eclipse C/C++ debugger. The example shows multiple threads within the application, disassembly of the code, the source code, and an console output.

FIGURE 8.6 Eclipse Debugger.

One advantage of using Linux on your embedded target platform is that you can start to develop and debug your application on a host-based Linux system such as on a Linux desktop. In this case, you can use any of the native development and debug tools mentioned above. Once you have completed debugging on the host, you can then migrate your application to the target. If the embedded target system is high performance and provides a display, then you can continue to use a host debugger on the target, but in many cases this is not available. So you must debug the target from the host platform - this is known as cross-debugging. The debugger runs on the host system and communicates with the target either via a direct connection to the processor via JTAG/BDM (background debug mode, or over a communications port such as Ethernet or a serial port (see Figure 8.7).

FIGURE 8.7 Cross-Target Debugging.

The target must provide a target debugger agent. In the case of hardware-based JTAG debuggers (see Chapter 17), this agent is provided by the hardware debugger. In software-only-based target debug scenarios, the target debug agent runs on the target CPU.

Kernel Debugging

The most common way of debugging a kernel is to insert strategically placed printk() messages in the kernel and device driver modules. The printk function is an implementation of printf that can be used in the kernel. printk messages are directed to the kernel debug buffer (circular) and the messages are also displayed on the console port. The Linux command dmesg can be used to dump the contents of the kernel debug buffer.

If the kernel crashes, you will be presented with a kernel oops. This is a detailed traceback of the kernel stack; it often provides sufficient information to identify why the kernel crashed, but it can take a significant level of experience to do so. Some systems can be set up to create a core dump file for the entire system (using Kdump). A core dump file contains a complete snapshot of system memory, and all relevant processor state such as register contents. The core dump file can be loaded into gdb and the system memory can be examined in detail. This can make it easier to debug a system crash, but in many embedded systems there is not sufficient local storage to save the core dump file, and relying on a mechanism (eg network stack) to send a core dump file to another system during a crash can be challenging.

Using a debugger to perform host kernel debugging brings about its own challenges. You cannot actively debug on the kernel that you are running on. Specifically, you can’t modify data structures, call functions in the kernel, or use breakpoints. You can inspect the system at great length, and that can often be enough to find the issue. In order to debug any kernel you must edit the kernel configuration to compile the kernel with debugging information (turn on CONFIG_DEBUG_INFO). If you want to inspect the kernel for the host platform you are running on you can issue the gdb command >gdb vmlinux /proc/kcore (on the system you want to debug). This will connect gdb to the currently executing system. The symbols for the kernel are loaded from the vmlinux file (stored in the /boot folder). The /proc/kcore is a special driver used to communicate with the kernel debug agent from the user space gdb application.

Cross-target kernel debugging is likely to be one of the most advanced embedded debugging techniques you will have to master. The core debugger runs on your host development system. The target will require a debug agent to communicate with the debugger on the host system. In many embedded systems you will use some form of hardware probe (via JTAG or BDM). This works well at the start of a system development but is often not practical when you are getting close to releasing the system (production hardware often removes the hardware connectors needed to connect to the hardware probe to save costs). Once the system is stable enough to provide a robust data connection via Ethernet, serial ports, or even USB, a good option is to switch to a software-based target debug agent. Support for remote kernel debugging was introduced (merged) into the 2.6.35 version of the Linux kernel (prior to that it was available as a patch to the kernel). This allows for kernel target debugging.

Another powerful way to debug the kernel is to use a software emulator. An emulator consists of both a CPU emulator and a platform/board level emulation capability. The open source QEMU emulator is a very powerful platform-level emulator. It supports a wide range of CPU architectures along with a number of emulated boards. You can start up the emulator with a debug connection from GBD to a target kernel debug agent running in the kernel, which itself is running in QEMU. In this configuration you can perform kernel level debug of the kernel executing within the QEMU emulator. The only downside is that you are not able to easily debug your target hardware drivers. Having said that, if the hardware being developed is new also, it can be very useful to develop a model of the new hardware in a software environment. You could do this by looking at how devices are emulated in QEMU and create your own device model. Special modeling languages exist such as System-C, these languages can be used to develop functional simulation models. These models can be developed in advance of the actual hardware development, and can be used to develop software while the silicon/hardware is still under development. This can often accelerate the time to market by allowing you to have the software ready when the hardware/SOC is ready. Full platform-level modeling/emulation environments are also commercially available, such as Wind River Simics and Synopsis Innovator.

Character Driver Model

This section provides an overview of the different aspects of a character-based device driver, discusses the user space interface provided by the driver, and the data path from submission of data by the user space application down to an underlying device.

PCI Device Drivers

The current IA-32-based drivers present the vast majority of hardware as PCI devices. The device may be internal in an SOC or on a board via physical PCIe links, but in all cases they are presented via the logical PCIe discovery model. The kernel identifies all hardware on the system and associates it automatically with the appropriate driver. The kernel uses a combination of PCI Vendor Code and Device ID or Class ID to associate the correct driver with an associated device automatically.

Each kernel module supporting a PCIe device indicates which devices are supported by the device driver. It does so by initializing a pci_device_id table and declaring the structure to the kernel loader using the MODULE_DEVICE_TABLE() macro. A sample from an Intel Gigabit Ethernet driver – e1000_main.c is shown below.

static DEFINE_PCI_DEVICE_TABLE(e1000_pci_tbl)

 = {

   PCI_DEVICE(0x8086, 0x1000),

   PCI_DEVICE(0x8086, 0x1000),

  {0,}

 };

MODULE_DEVICE_TABLE(pci, e1000_pci_tbl);

In the initiation function you must register the drive handling functions. This is similar to the procedure shown for the simple character device.

static struct pci_driver e1000_driver = {

 .name   = e1000_driver_name,

 .id_table = e1000_pci_tbl,

 .probe  = e1000_probe,

 .remove  = __devexit_p(e1000_remove),

#ifdef CONFIG_PM

 /∗ Power Managment Hooks ∗/

 .suspend  = e1000_suspend,

 .resume   = e1000_resume,

#endif

 .shutdown  = e1000_shutdown,

 .err_handler = &e1000_err_handler

};

pci_register_driver(&e1000_driver);

The probe function is particular to the PCI discovery process. The driver probe function is called with a pointer to the PCI device structure. This provides all the required information for the driver to identify the individual instance of a PCI device being initialized (for instance, there could be many NIC interfaces in the system):

static int __devinit

  e1000_probe(struct pci_dev ∗pdev,

        const struct pci_device_id ∗ent)

The probe, shutdown, and power manage handlers do not expose any specific capability of the PCI device. It could be a video capture card or a network interface, and these functions would be very similar in behavior. The following are the general steps required during this phase:

These steps ensure that resources are allocated and the device is set up ready to be used.

Interrupt Handling

Almost all device interactions require that the device driver operate with device interrupts. Interrupts are used to indicate that a change has occurred in the device. The driver is expected to service the hardware interrupt in a timely fashion.

The operating system provides a specific mechanism to allocate and assign a callback function to device interrupts. In IA-32-based systems, many hardware devices are presented as PCIe devices (both on the SOC and external). For such devices, three different types of interrupts support mechanisms in the hardware and are supported by the kernel. They are:

The driver should enable MSI/MSIx for a device by calling pci_enable_msi() or pci_enable_msix(). This allocates CPU interrupt vectors and writes the vector data into a PCI device. The interrupt vectors allocated to the device are returned by the call. If the call fails, then the driver should revert to a legacy interrupt support and bind a single interrupt callback function to the legacy interrupt vector. For MSI/MSIx vectors, you should not assume that you obtained all the vectors that the device is capable of generating; the operating system may allocate fewer vectors (perhaps only 1) to a device if vectors are scarce (255 vectors in all). This is not very likely in an embedded system, but you must ensure that your driver handles such cases gracefully.

MSI/MSIx-based systems also follow different ordering semantics for transactions from the device (to devices which use legacy wired interrupts). When a device which uses MSI/MSIx interrupts writes to system memory and then generates an interrupt, the system memory is guaranteed to be up to date when the processor reads the data based on the arrival of the interrupt. The driver is not required to perform a device read to ensure memory consistency.

Once the system allocates the vectors, the driver can assign the vectors to callback routines.

request_irq(IRQ Number,

           callback function handler,

           irq_flags,

           name, /∗ show in statistics ∗/

           data); 

When an interrupt fires on the device, the callback function handler is called with an interrupt vector and a void∗ data pointer. The data pointer is usually set to a device driver stricture that contains all the required device instance/specific information (including a pointer to the PCI device structure for the device.). The interrupts statistics can be seen in the /proc/interrupts pseudo file system.

The handler runs in interrupt context. In most systems, there are significant limitations to the operating system functions that can be called from interrupt context. The in_interrupt() call returns true if the calling function is in the interrupt context, this call can be used to check the calling context and ensure the function does not call inappropriate services given the calling context.

The amount of work performed in the interrupt handler should be kept to a minimum; specifically, only perform the time-critical aspect of servicing the device. At a minimum, the interrupt handler runs with the current interrupt level disabled, so running too much code may affect the performance of other critical interrupt handling, specifically it can add to the jitter associated with processing other key interrupts.

All other work related to the device should be deferred in an alternative non-interrupt context. Operating systems provide a specific mechanism to defer work to a kernel task context to perform the remainder of the work. In Linux these are kernel bottom halves/tasklets, while on VxWorks you can transfer work to any system task.

User Space

The most well-known mechanism for requesting memory from user space is to call malloc(). This is a C library function that returns a user space pointer to the allocated memory. The pointer contains a virtual address, and the MMU system within the CPU translates access to this virtual address to an underlying physical memory location(s). The memory is contiguous as far as the user space application is concerned, however the allocation may have come from multiple physically discontinuous memory pages. The MMU tables are appropriately configured to ensure the contiguous virtual address mappings.

An important attribute to this memory is that it is subject to paging to disk if the system becomes oversubscribed (in terms of memory requests). You should note that paging is generally turned off in embedded systems due to file system wear (particularly for flash devices) and nondeterministic performance. The user space memory library often makes requests to the underlying kernel for memory.

Access to User Space memory from the Kernel

When a user space application makes a system call such as write() to a device, a transition from user space to kernel space occurs. The appropriate device driver write function is called (as in the case of our character driver above). The write function will be working on behalf of the calling user space process and as a result is said to be running in its process context. While in process context, the memory of the calling process and kernel mappings are accessible (provided no paging has occurred). In this context both the user space process and kernel virtual address ranges are available, as a result the virtual address assigned to the kernel and those assigned to processes must be unique. In a 32-bit Linux system, processes are assigned virtual addresses that range from zero to 3 GBytes, and the kernel uses virtual addresses that ranges from 3 GB through 4 GB. The Linux system calls copy_from_user() and copy_to_user() are provided to copy data between the user space pages and the kernel pages.

Kernel Allocation

The kernel manages all memory in physical page units. Each processor has a defined page size (4 K on IA-32). The kernel tracks every page in the system with page structure defined in linux/include/linux/mm_types.h.

The following key attributes are maintained for each physical page in the system:

Information on the current page statistics can be found using the command >cat /proc/meminfo.

The kernel supports a number of different logical zones for memory allocation. The zones address ranges are processor architecture specific. The first is ZONE_DMA; when an allocation request ZONE_DMA is requested it provides pages that are guaranteed to be accessible by any DMA agent in the system. In some cases devices with DMA capability are not all capable of accessing all addresses in the system. This is set to <16 MB in IA-32 systems to cover old ISA bus devices and is rarely used at this point. ZONE_DMA2 is a zone that is supported on IA-32 systems. It is used for devices that can only access 32-bit address space but with more than 4 GB of memory populated (x64).

ZONE_NORMAL is the normal memory zone used. If used with a device, the device must be able to access all system memory (for a 32-bit device system, all 4 GB must be accessible from the device). Memory obtained from this zone has a valid virtual address that can be used to dereference the physical memory at any time. Most allocations use this zone. It’s important to note that there is a fixed offset between the virtual address and physical address allocated from the normal zone. This is very important; in many cases device drivers convert from virtual addresses to physical (and then bus address) addresses when interacting with a device. It is important for the cost of such translations to be low, and having a fixed arithmetic offset between the two addresses achieves a very efficient translation at runtime. The function virt_to_phy() performs such a translation.

ZONE_HIGH_MEM is assigned to pages that are high in physical memory (above 900 MB). As mentioned earlier, the kernel occupies virtual address ranges from 3 GB through 4 GB. That is, it is allocated 1 GB of virtual address. Therefore, it cannot have all physical addresses mapped. In this case you can still allocate the pages, but there is no permanent virtual mapping to the physical page. These pages must be mapped if you need to read/write the memory from the kernel at run time. However these memory regions are accessible from devices via DMA without creating a kernel virtual address mapping.

Page Allocation

A number of low-level functions can be used to request memory from a particular zone. The allocations return memory that is both page-aligned and with page granularity. The lowest level page allocation function is

struct page ∗alloc_pages(unsigned int gfp_mask,

                        unsigned int order)

This function allocates 2 << order contiguous pages from the kernel. The function returns a page structure. The flags include the ZONE and other elements described later. The virtual address mapped to the page (for DMA_ZONE and DMA_NORMAL) can be obtained from the returned page structure by calling page_address(). As the physical pages must be contiguous (not the case for user space malloced memory). It is often difficult to obtain large contiguous memory regions from the kernel, especially the longer the system is up and running. In most cases you should request your large contiguous memory requests during startup to improve the likelihood of success, however in general it is better to assume you cannot guarantee large physically contiguous memory allocations. As a general rule of thumb, a 64-kB block is considered a large contiguous section to request. When large contiguous memory regions are needed, you can make a call to alloc_bootmem() during system startup. This has a much higher probability of succeeding, and it is used when very large buffers are needed (several megabytes).

In many cases, device drivers make use of linked lists of pages to describe incoming and outgoing data. These are arranged as linked lists of pages; each page is contiguous but the list does not need to be made up from contiguous pages. These lists are referred to as scatter gather lists. Corresponding to the DMA engines, a device should support a descriptor mechanism whereby a logical contiguous data block can be characterized by a list of physical pointers.

The kmalloc() Function

The kernel provides a function very similar to the user space counterpart malloc(). The page allocation routines above may be very inefficient if small allocations (below one page) are required. The kernel maintains a SLAB of buffers and can efficiently provide subpage or page size allocation.

Void ∗ptr;

ptr = kmalloc(1024,GFP_KERNEL);

..

kfree(ptr);

The kmalloc function returns at least the number of bytes requested, but they are not necessarily page aligned (often important for devices). The second argument is the gfp_mask flag. The flags are defined in linux/include/linux/gfp.h and slab.h. The mask can be broken down into two separate modifiers.

Luckily, the kernel provides a number of predefined definitions that you can use without the need to understand the lower-level details, as shown in Table 8.2.

Table 8.2. Flag Types (Subset).

The majority of uses of kmalloc simply use the GFP_KERNEL flag.

PCI Memory Allocation and Mapping

The PCI subsystem provides a number of memory allocation routines that should be used when allocating memory, which is shared between the processor and a device. There are a wide range of system combinations supported by Linux, 32-bit/64-bit CPU, 32-bit/64-bit PCI, different processor endianness, PCI bus address translation in controllers, memory coherence (between CPU and devices)—all of which lead to challenges in creating platform device drivers for PCI devices that may be used in any system. The expectation of a device driver that has been upstreamed and hosted at kernel.org is that it will operate on any supported architecture if a PCI bus is supported.

A device driver may allocate memory for use as a shared communication area between the processor and device. The device driver must have a virtual address mapping for this memory in order to write to the memory. The device must also be informed of the address in a configuration register. The address written to in the device must be the address the device puts in the PCI transactions and is called the bus address. The driver must have the physical and bus address that corresponds to the virtual address used by the driver. On older kernels this translation was achieved by calling virt_to_bus() and bus_to_virt(). However, these have been superseded by the PCI DMA interface and should not be used.

The DMA API provides allocation for two different use cases, known as consistent and streaming. Consistent mapping should be used for memory that must be guaranteed to be accessible from the device at all times. It is typically allocated and mapped during initialization. The device and CPU can access the memory concurrently. The software is not expected to perform any cache flush (for non-cache coherent architectures) for this memory space. When the CPU writes to this space, it is immediately visible to the device. There are some processor architectures where you need place a write barrier in the instruction pipeline to ensure such consistency. This can be achieved by using the write memory barrier call wmb(). The IA-32 processors are strongly ordered and do not require the wmb(). Processors such as Itanium® are weakly ordered and do require such barriers.

The call to allocate a consistent area of memory uses the following function:

dma_addr_t dma_handle;

cpu_addr =

dma_alloc_coherent(dev, size, &dma_handle, gfp);

The function returns a CPU virtual address that can be directly used by the driver to read from and write to the memory. It also returns a dma_handle. The DMA address is the appropriate bus address that can be written to the device.

The DMA Streaming API provides a mechanism to obtain bus addresses for data. The data could be allocated from the NORMAL or HIGHMEM zones. The functions used are called dma_map_single(), dma_map_page(), and dma_map_sg().

dma_addr_t dma_handle;

dma_handle = dma_map_single(dev, addr, size, direction);

The function returns the bus address for the virtual address provided. The function also performs any architecture-required cache coherence updates. You should consider the data to be “owned” by the device after a map call is made. The reciprocal dma_unmap_single(), dma_unmap_page, dma_unmap_sg() functions should be called once the driver is aware that the device no longer needs access to the mapped page. For example, it may be known that the device interrupts the process to indicate that the packet has been transmitted. The calls take a direction parameter to indicate whether the buffer is going to be written to or read from the device, or both.

Atomic Operations

An atomic operation is an operation that runs without being interrupted. Operations on atomic integers are easy to use.

atomic_t atomic_var;

atomic_set(&atomic_var, 10); / set to 10

atomic_add(5,&atomic_var); // add 5 to the variable

atomic_inc(&atomic_var); // increment by 1.

Atomic intrinsics usually use processor atomic instructions, such as the IA-32 instruction TSL (test set and lock) or Locked CMPXCHG (locked compare and exchange), which are used to build up these underling atomic operations. These instructions can be costly and often serialize the processor’s pipeline.

Atomic operations are often used to update counters, although the use of atomics for simple counters should be avoided where possible (create per CPU/context counter values).

Spinlock

In many cases, a sequence of code needs to run that must be executed in one execution context at any given time. No other context can enter the synchronized area of code until the previous context leaves the synchronized area. A simple example of such a case is to update a linked list where head/tail pointer updates must be carried out atomically.

To facilitate such serialization, the Linux kernel provides spinlocks. A spinlock can only be held/owned by one execution context (thread). If the lock has not yet been acquired, then the first thread to request it obtains the lock (with little overhead). If an execution context attempts to acquire the lock but it has already been acquired, then the calling context will simply spin in a loop until the other context releases the lock. Spinlocks are very fast and efficient in terms of acquisition cost, but the CPU running the busy loop is wasting CPU time until the contended execution context is de-scheduled (in a single-processor system).

spinlock_t link_lock = SPIN_LOCK_UNLOCKED;

spin_lock(&link_lock);

…

spin_unlock(&link_lock)

Obviously, you have to be careful to ensure that you do not create a deadlock scenario, for example, by using spinlocks between an interrupt and kernel thread. To facilitate the use of spinlocks between interrupt and kernel execution context you can use spin_lock_irqsave() and spin_unlock_irqrestore().

Depending on the use case, the use of a generic spinlock may block threads that in reality do not need to be. The most common use case is the single writer, multiple reader design pattern. In this case the kernel provides a lock that does not block multiple readers until a thread wishes to perform an update/write. The read_lock() and write_lock() functions provide such capabilities.

Semaphore

A semaphore is a lock, but it may sleep the context that attempts to obtain a contented lock. Instead of running a busy loop waiting for the lock, the thread is placed in a not-ready state and de-scheduled. Semaphores should only be used where the expected wait time is long; spinlocks should be used in short wait use cases.

The semaphores implemented in the Linux kernel are known as counting semaphores, and the count can be specified. In many cases the count is specified as one, which makes the semaphore a binary semaphore or mutex. There is an API added for mutexes given that they are so common.

static DECLARE_MUTEX(link_mutex);

// attempt to get the semaphore

if ( down_ interruptible(&link_mutex))

{

  /∗ only case were we don't get the mutex is due to

    reception of a signal.∗/

…handle signal ..

}

/∗ Critical section ∗/

…

/∗ release the mutex ∗/

up(&link_mutex);

Given that semaphores and mutexes may cause the calling context to switch, they thus cannot be used from an interrupt context.