Address Types

Thus far, we have talked about virtual and physical addresses, but a number of the details have been glossed over. The Linux system deals with several types of addresses, each with its own semantics. Unfortunately, the kernel code is not always very clear on exactly which type of address is being used in each situation, so the programmer must be careful.

The following is a list of address types used in Linux. Figure 13-1 shows how these address types relate to physical memory.

Different kernel functions require different types of addresses. It would be nice if there were different C types defined so that the required address type were explicit, but we have no such luck. In this chapter, we will be clear on which types of addresses are used where.

High and Low Memory

Recent developments have eliminated the limitations on memory, and 32-bit systems can now work with well over 4 GB of system memory (assuming, of course, that the processor itself can address that much memory). The limitation on how much memory can be directly mapped with logical addresses remains, however. Only the lowest portion of memory (up to 1 or 2 GB, depending on the hardware and the kernel configuration) has logical addresses; the rest (high memory) does not. High memory can require 64-bit physical addresses, and the kernel must set up explicit virtual address mappings to manipulate it. Thus, many kernel functions are limited to low memory only; high memory tends to be reserved for user-space process pages.

The term "high memory" can be confusing to some, especially since it has other meanings in the PC world. So, to make things clear, we'll define the terms here:

Low memory

Memory for which logical addresses exist in kernel space. On almost every system you will likely encounter, all memory is low memory.

High memory

Memory for which logical addresses do not exist, because the system contains more physical memory than can be addressed with 32 bits.

On i386 systems, the boundary between low and high memory is usually set at just under 1 GB. This boundary is not related in any way to the old 640 KB limit found on the original PC. It is, instead, a limit set by the kernel itself as it splits the 32-bit address space between kernel and user space.

We will point out high-memory limitations as we come to them in this chapter.

The Memory Map and struct page

There is much more information within struct page, but it is part of the deeper black magic of memory management and is not of concern to driver writers.

Some functions and macros are defined for translating between struct page pointers and virtual addresses:

Page Tables

Note that Linux uses a three-level system even on hardware that only supports two levels of page tables or hardware that uses a different way to map virtual addresses to physical ones. The use of three levels in a processor-independent implementation allows Linux to support both two-level and three-level processors without clobbering the code with a lot of #ifdef statements. This kind of conservative coding doesn't lead to additional overhead when the kernel runs on two-level processors, because the compiler actually optimizes out the unused level.

It is time to take a look at the data structures used to implement the paging system. The following list summarizes the implementation of the three levels in Linux, and Figure 13-2 depicts them.

The kernel doesn't need to worry about doing page-table lookups during normal program execution, because they are done by the hardware. Nonetheless, the kernel must arrange things so that the hardware can do its work. It must build the page tables and look them up whenever the processor reports a page fault, that is, whenever the page associated with a virtual address needed by the processor is not present in memory. Device drivers, too, must be able to build page tables and handle faults when implementing mmap.

Virtual Memory Areas

The memory areas of a process can be seen by looking in /proc/pid/maps(where pid, of course, is replaced by a process ID). /proc/self is a special case of /proc/pid, because it always refers to the current process. As an example, here are a couple of memory maps, to which we have added short comments after a sharp sign:

morgana.root# cat /proc/1/maps   # look at init
08048000-0804e000 r-xp 00000000 08:01 51297      /sbin/init  # text
0804e000-08050000 rw-p 00005000 08:01 51297      /sbin/init  # data
08050000-08054000 rwxp 00000000 00:00 0          # zero-mapped bss
40000000-40013000 r-xp 00000000 08:01 39003      /lib/ld-2.1.3.so # text
40013000-40014000 rw-p 00012000 08:01 39003      /lib/ld-2.1.3.so # data
40014000-40015000 rw-p 00000000 00:00 0          # bss for ld.so
4001b000-40108000 r-xp 00000000 08:01 39006      /lib/libc-2.1.3.so # text
40108000-4010c000 rw-p 000ec000 08:01 39006      /lib/libc-2.1.3.so # data
4010c000-40110000 rw-p 00000000 00:00 0          # bss for libc.so
bfffe000-c0000000 rwxp fffff000 00:00 0          # zero-mapped stack

morgana.root# rsh wolf head /proc/self/maps  #### alpha-axp: static ecoff
000000011fffe000-0000000120000000 rwxp 0000000000000000 00:00 0     # stack
0000000120000000-0000000120014000 r-xp 0000000000000000 08:03 2844  # text
0000000140000000-0000000140002000 rwxp 0000000000014000 08:03 2844  # data
0000000140002000-0000000140008000 rwxp 0000000000000000 00:00 0     # bss

The fields in each line are as follows:

start-end perm offset major:minor inode image.

Each field in /proc/*/maps (except the image name) corresponds to a field in struct vm_area_struct, and is described in the following list.

start

end

The beginning and ending virtual addresses for this memory area.

perm

A bit mask with the memory area's read, write, and execute permissions. This field describes what the process is allowed to do with pages belonging to the area. The last character in the field is either p for "private'' or s for "shared.''

offset

Where the memory area begins in the file that it is mapped to. An offset of zero, of course, means that the first page of the memory area corresponds to the first page of the file.

major

minor

The major and minor numbers of the device holding the file that has been mapped. Confusingly, for device mappings, the major and minor numbers refer to the disk partition holding the device special file that was opened by the user, and not the device itself.

inode

The inode number of the mapped file.

image

The name of the file (usually an executable image) that has been mapped.

A definitive example of mmap usage can be seen by looking at a subset of the virtual memory areas for the X Window System server:

cat /proc/731/maps
08048000-08327000 r-xp 00000000 08:01 55505    /usr/X11R6/bin/XF86_SVGA
08327000-08369000 rw-p 002de000 08:01 55505    /usr/X11R6/bin/XF86_SVGA
40015000-40019000 rw-s fe2fc000 08:01 10778    /dev/mem
40131000-40141000 rw-s 000a0000 08:01 10778    /dev/mem
40141000-40941000 rw-s f4000000 08:01 10778    /dev/mem
     ...

The full list of the X server's VMAs is lengthy, but most of the entries are not of interest here. We do see, however, three separate mappings of /dev/mem, which give some insight into how the X server works with the video card. The first mapping shows a 16 KB region mapped at fe2fc000. This address is far above the highest RAM address on the system; it is, instead, a region of memory on a PCI peripheral (the video card). It will be a control region for that card. The middle mapping is at a0000, which is the standard location for video RAM in the 640 KB ISA hole. The last /dev/memmapping is a rather larger one at f4000000 and is the video memory itself. These regions can also be seen in /proc/iomem:

000a0000-000bffff : Video RAM area
f4000000-f4ffffff : Matrox Graphics, Inc. MGA G200 AGP
fe2fc000-fe2fffff : Matrox Graphics, Inc. MGA G200 AGP

Mapping a device means associating a range of user-space addresses to device memory. Whenever the program reads or writes in the assigned address range, it is actually accessing the device. In the X server example, using mmap allows quick and easy access to the video card's memory. For a performance-critical application like this, direct access makes a large difference.

These limits are not a big constraint for drivers, because the program accessing the device is device dependent anyway. It needs to know how to make sense of the memory region being mapped, so the PAGE_SIZE alignment is not a problem. A bigger constraint exists when ISA devices are used on some non-x86 platforms, because their hardware view of ISA may not be contiguous. For example, some Alpha computers see ISA memory as a scattered set of 8-bit, 16-bit, or 32-bit items, with no direct mapping. In such cases, you can't use mmap at all. The inability to perform direct mapping of ISA addresses to Alpha addresses is due to the incompatible data transfer specifications of the two systems. Whereas early Alpha processors could issue only 32-bit and 64-bit memory accesses, ISA can do only 8-bit and 16-bit transfers, and there's no way to transparently map one protocol onto the other.

The system call is declared as follows (as described in the mmap(2) manual page):

mmap (caddr_t addr, size_t len, int prot, int flags, int fd, 
off_t offset)

On the other hand, the file operation is declared as

int (*mmap) (struct file *filp, struct vm_area_struct *vma);

The filp argument in the method is the same as that introduced in Chapter 3, "Char Drivers", while vma contains the information about the virtual address range that is used to access the device. Much of the work has thus been done by the kernel; to implement mmap, the driver only has to build suitable page tables for the address range and, if necessary, replace vma->vm_ops with a new set of operations.

There are two ways of building the page tables: doing it all at once with a function called remap_page_range, or doing it a page at a time via the nopage VMA method. Both methods have their advantages. We'll start with the "all at once'' approach, which is simpler. From there we will start adding the complications needed for a real-world implementation.

Using remap_page_range

int remap_page_range(unsigned long virt_add, unsigned long phys_add,
                     unsigned long size, pgprot_t prot);

The value returned by the function is the usual 0 or a negative error code. Let's look at the exact meaning of the function's arguments:

virt_add

The user virtual address where remapping should begin. The function builds page tables for the virtual address range between virt_add and virt_add+size.

phys_add

The physical address to which the virtual address should be mapped. The function affects physical addresses from phys_add to phys_add+size.

size

The dimension, in bytes, of the area being remapped.

prot

The "protection'' requested for the new VMA. The driver can (and should) use the value found in vma->vm_page_prot.

A Simple Implementation

If your driver needs to do a simple, linear mapping of device memory into a user address space, remap_page_range is almost all you really need to do the job. The following code comes from drivers/char/mem.c and shows how this task is performed in a typical module called simple (Simple Implementation Mapping Pages with Little Enthusiasm):

 #include <linux/mm.h>

 int simple_mmap(struct file *filp, struct vm_area_struct *vma)
 {
     unsigned long offset = vma->vm_pgoff << PAGE_SHIFT;
    
     if (offset >= _&thinsp;_pa(high_memory) || (filp->f_flags & O_SYNC))
         vma->vm_flags |= VM_IO;
     vma->vm_flags |= VM_RESERVED;

     if (remap_page_range(vma->vm_start, offset, 
            vma->vm_end-vma->vm_start, vma->vm_page_prot))
         return -EAGAIN;
     return 0;
 }

Adding VMA Operations

We'll use these methods to increment the module usage count whenever the VMA is opened, and to decrement it when it's closed. In modern kernels, this work is not strictly necessary; the kernel will not call the driver's release method as long as a VMA remains open, so the usage count will not drop to zero until all references to the VMA are closed. The 2.0 kernel, however, did not perform this tracking, so portable code will still want to be able to maintain the usage count.

So, we will override the default vma->vm_ops with operations that keep track of the usage count. The code is quite simple -- a complete mmap implementation for a modularized /dev/mem looks like the following:

 
void simple_vma_open(struct vm_area_struct *vma)
{ MOD_INC_USE_COUNT; }

void simple_vma_close(struct vm_area_struct *vma)
{ MOD_DEC_USE_COUNT; }

static struct vm_operations_struct simple_remap_vm_ops = {
    open:  simple_vma_open,
    close: simple_vma_close,
};

int simple_remap_mmap(struct file *filp, struct vm_area_struct *vma)
{
    unsigned long offset = VMA_OFFSET(vma);

    if (offset >= __pa(high_memory) || (filp->f_flags & O_SYNC))
        vma->vm_flags |= VM_IO;
    vma->vm_flags |= VM_RESERVED;

    if (remap_page_range(vma->vm_start, offset, vma->vm_end-vma->vm_start,
                vma->vm_page_prot))
        return -EAGAIN;

    vma->vm_ops = &simple_remap_vm_ops;
    simple_vma_open(vma);
    return 0;
}

This code relies on the fact that the kernel initializes to NULL the vm_ops field in the newly created area before calling f_op->mmap. The code just shown checks the current value of the pointer as a safety measure, should something change in future kernels.

Mapping Memory with nopage

The nopage method, remember, has the following prototype:

 struct page (*nopage)(struct vm_area_struct *vma, 
                     unsigned long address, int write_access);

 get_page(struct page *pageptr);

This step is necessary to keep the reference counts correct on the mapped pages. The kernel maintains this count for every page; when the count goes to zero, the kernel knows that the page may be placed on the free list. When a VMA is unmapped, the kernel will decrement the usage count for every page in the area. If your driver does not increment the count when adding a page to the area, the usage count will become zero prematurely and the integrity of the system will be compromised.

The Linux implementation of mremap doesn't notify the driver of changes in the mapped area. Actually, it does notify the driver if the size of the area is reduced via the unmap method, but no callback is issued if the area increases in size.

The basic idea behind notifying the driver of a reduction is that the driver (or the filesystem mapping a regular file to memory) needs to know when a region is unmapped in order to take the proper action, such as flushing pages to disk. Growth of the mapped region, on the other hand, isn't really meaningful for the driver until the program invoking mremap accesses the new virtual addresses. In real life, it's quite common to map regions that are never used (unused sections of program code, for example). The Linux kernel, therefore, doesn't notify the driver if the mapped region grows, because the nopage method will take care of pages one at a time as they are actually accessed.

In other words, the driver isn't notified when a mapping grows because nopage will do it later, without having to use memory before it is actually needed. This optimization is mostly aimed at regular files, whose mapping uses real RAM.

The nopage method, therefore, must be implemented if you want to support the mremap system call. But once you have nopage, you can choose to use it extensively, with some limitations (described later). This method is shown in the next code fragment. In this implementation of mmap, the device method only replaces vma->vm_ops. The nopagemethod takes care of "remapping'' one page at a time and returning the address of its struct page structure. Because we are just implementing a window onto physical memory here, the remapping step is simple -- we need only locate and return a pointer to the struct page for the desired address.

An implementation of /dev/mem using nopage looks like the following:

 
struct page *simple_vma_nopage(struct vm_area_struct *vma,
                unsigned long address, int write_access)
{
    struct page *pageptr;
    unsigned long physaddr = address - vma->vm_start + VMA_OFFSET(vma);
    pageptr = virt_to_page(__va(physaddr));
    get_page(pageptr);
    return pageptr;
}

int simple_nopage_mmap(struct file *filp, struct vm_area_struct *vma)
{
    unsigned long offset = VMA_OFFSET(vma);

    if (offset >= __pa(high_memory) || (filp->f_flags & O_SYNC))
        vma->vm_flags |= VM_IO;
    vma->vm_flags |= VM_RESERVED;

    vma->vm_ops = &simple_nopage_vm_ops;
    simple_vma_open(vma);
    return 0;
}

If the nopage method is left NULL, kernel code that handles page faults maps the zero page to the faulting virtual address. The zero page is a copy-on-write page that reads as zero and that is used, for example, to map the BSS segment. Therefore, if a process extends a mapped region by calling mremap, and the driver hasn't implemented nopage, it will end up with zero pages instead of a segmentation fault.

The nopage method normally returns a pointer to a struct page. If, for some reason, a normal page cannot be returned (e.g., the requested address is beyond the device's memory region), NOPAGE_SIGBUS can be returned to signal the error. nopage can also return NOPAGE_OOM to indicate failures caused by resource limitations.

Remapping Specific I/O Regions

unsigned long off = vma->vm_pgoff << PAGE_SHIFT;
unsigned long physical = simple_region_start + off;
unsigned long vsize = vma->vm_end - vma->vm_start;
unsigned long psize = simple_region_size - off;

if (vsize > psize)
    return -EINVAL; /*  spans too high */
remap_page_range(vma_>vm_start, physical, vsize, vma->vm_page_prot);

In addition to calculating the offsets, this code introduces a check that reports an error when the program tries to map more memory than is available in the I/O region of the target device. In this code, psize is the physical I/O size that is left after the offset has been specified, and vsize is the requested size of virtual memory; the function refuses to map addresses that extend beyond the allowed memory range.

The simplest way to prevent extension of the mapping is to implement a simple nopage method that always causes a bus signal to be sent to the faulting process. Such a method would look like this:

struct page *simple_nopage(struct vm_area_struct *vma,
                           unsigned long address, int write_access);
{ return NOPAGE_SIGBUS; /* send a SIGBUS */}

Remapping RAM

Therefore, remap_page_range won't allow you to remap conventional addresses -- which include the ones you obtain by calling get_free_page. Instead, it will map in the zero page. Nonetheless, the function does everything that most hardware drivers need it to, because it can remap high PCI buffers and ISA memory.

morgana.root# ./mapper /dev/mem 0x10000 0x1000 | od -Ax -t x1
mapped "/dev/mem" from 65536 to 69632
000000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
*
001000

The inability of remap_page_range to deal with RAM suggests that a device like scullpcan't easily implement mmap, because its device memory is conventional RAM, not I/O memory. Fortunately, a relatively easy workaround is available to any driver that needs to map RAM into user space; it uses the nopage method that we have seen earlier.

Remapping RAM with the nopage method

scullp is the page oriented char device. Because it is page oriented, it can implement mmap on its memory. The code implementing memory mapping uses some of the concepts introduced earlier in "Memory Management in Linux".

Code that is intended to map RAM according to the rules just outlined needs to implement open, close, and nopage; it also needs to access the memory map to adjust the page usage counts.

This implementation of scullp_mmap is very short, because it relies on the nopage function to do all the interesting work:

 
int scullp_mmap(struct file *filp, struct vm_area_struct *vma)
{
    struct inode *inode = INODE_FROM_F(filp);

    /* refuse to map if order is not 0 */
    if (scullp_devices[MINOR(inode->i_rdev)].order)
        return -ENODEV;

    /* don't do anything here: "nopage" will fill the holes */
    vma->vm_ops = &scullp_vm_ops;
    vma->vm_flags |= VM_RESERVED;
    vma->vm_private_data = scullp_devices + MINOR(inode->i_rdev);
    scullp_vma_open(vma);
    return 0;
}

The purpose of the leading conditional is to avoid mapping devices whose allocation order is not 0. scullp's operations are stored in the vm_ops field, and a pointer to the device structure is stashed in the vm_private_data field. At the end, vm_ops->open is called to update the usage count for the module and the count of active mappings for the device.

open and close simply keep track of these counts and are defined as follows:

 
void scullp_vma_open(struct vm_area_struct *vma)
{
    ScullP_Dev *dev = scullp_vma_to_dev(vma);

    dev->vmas++;
    MOD_INC_USE_COUNT;
}

void scullp_vma_close(struct vm_area_struct *vma)
{
    ScullP_Dev *dev = scullp_vma_to_dev(vma);

    dev->vmas--;
    MOD_DEC_USE_COUNT;
}

Most of the work is then performed by nopage. In the scullp implementation, the address parameter to nopage is used to calculate an offset into the device; the offset is then used to look up the correct page in the scullpmemory tree.

 
struct page *scullp_vma_nopage(struct vm_area_struct *vma,
                                unsigned long address, int write)
{
    unsigned long offset;
    ScullP_Dev *ptr, *dev = scullp_vma_to_dev(vma);
    struct page *page = NOPAGE_SIGBUS;
    void *pageptr = NULL; /* default to "missing" */

    down(&dev->sem);
    offset = (address - vma->vm_start) + VMA_OFFSET(vma);
    if (offset >= dev->size) goto out; /* out of range */

    /*
     * Now retrieve the scullp device from the list, then the page.
     * If the device has holes, the process receives a SIGBUS when
     * accessing the hole.
     */
    offset >>= PAGE_SHIFT; /* offset is a number of pages */
    for (ptr = dev; ptr && offset >= dev->qset;) {
        ptr = ptr->next;
        offset -= dev->qset;
    }
    if (ptr && ptr->data) pageptr = ptr->data[offset];
    if (!pageptr) goto out; /* hole or end-of-file */
    page = virt_to_page(pageptr);
    
    /* got it, now increment the count */
    get_page(page);
out:
    up(&dev->sem);
    return page;
}

scullp uses memory obtained with get_free_pages. That memory is addressed using logical addresses, so all scullp_nopage has to do to get a struct page pointer is to call virt_to_page.

morgana% ls -l /dev > /dev/scullp
morgana% ./mapper /dev/scullp 0 140
mapped "/dev/scullp" from 0 to 140
total 77
-rwxr-xr-x    1 root     root        26689 Mar  2  2000 MAKEDEV
crw-rw-rw-    1 root     root      14,  14 Aug 10 20:55 admmidi0
morgana% ./mapper /dev/scullp 8192 200
mapped "/dev/scullp" from 8192 to 8392
0
crw --  --  -- -    1 root     root     113,   1 Mar 26  1999 cum1
crw --  --  -- -    1 root     root     113,   2 Mar 26  1999 cum2
crw --  --  -- -    1 root     root     113,   3 Mar 26  1999 cum3

Remapping Virtual Addresses

Most of the scullv implementation is like the one we've just seen for scullp, except that there is no need to check the order parameter that controls memory allocation. The reason for this is that vmalloc allocates its pages one at a time, because single-page allocations are far more likely to succeed than multipage allocations. Therefore, the allocation order problem doesn't apply to vmalloced space.

 
pgd_t *pgd; pmd_t *pmd; pte_t *pte;
unsigned long lpage;

/*
 * After scullv lookup, "page" is now the address of the page
 * needed by the current process. Since it's a vmalloc address,
 * first retrieve the unsigned long value to be looked up
 * in page tables.
 */
lpage = VMALLOC_VMADDR(pageptr);
spin_lock(&init_mm.page_table_lock);
pgd = pgd_offset(&init_mm, lpage);
pmd = pmd_offset(pgd, lpage);
pte = pte_offset(pmd, lpage);
page = pte_page(*pte);
spin_unlock(&init_mm.page_table_lock);
    
/* got it, now increment the count */
get_page(page);
out:
up(&dev->sem);
return page;

The kiobuf Structure

The key to the kiobuf interface is the maplist array. Functions that operate on pages stored in a kiobuf deal directly with the page structures -- all of the virtual memory system overhead has been moved out of the way. This implementation allows drivers to function independent of the complexities of memory management, and in general simplifies life greatly.

void kiobuf_init(struct kiobuf *iobuf);

int alloc_kiovec(int nr, struct kiobuf **iovec);

void free_kiovec(int nr, struct kiobuf **);

int lock_kiovec(int nr, struct kiobuf *iovec[], int wait);
int unlock_kiovec(int nr, struct kiobuf *iovec[]);

Locking a kiovec in this manner is unnecessary, however, for most applications of kiobufs seen in device drivers.

Mapping User-Space Buffers and Raw I/O

The Linux kernel has traditionally not provided a raw interface, for a number of reasons. As the system gains in popularity, however, more applications that expect to be able to do raw I/O (such as large database management systems) are being ported. So the 2.3 development series finally added raw I/O; the driving force behind the kiobuf interface was the need to provide this capability.

It is worth noting that in Linux systems, there is no need for block drivers to provide this sort of interface. The raw device, in drivers/char/raw.c, provides this capability in an elegant, general way for all block devices. The block drivers need not even know they are doing raw I/O. The raw I/O code in sbull is essentially a simplification of the raw device code for demonstration purposes.

Raw I/O to a block device must always be sector aligned, and its length must be a multiple of the sector size. Other kinds of devices, such as tape drives, may not have the same constraints. sbullr behaves like a block device and enforces the alignment and length requirements. To that end, it defines a few symbols:

 
#  define SBULLR_SECTOR 512  /* insist on this */
#  define SBULLR_SECTOR_MASK (SBULLR_SECTOR - 1)
#  define SBULLR_SECTOR_SHIFT 9

The sbullr raw device will be registered only if the hard-sector size is equal to SBULLR_SECTOR. There is no real reason why a larger hard-sector size could not be supported, but it would complicate the sample code unnecessarily.

The sbullr implementation adds little to the existing sbull code. In particular, the open and close methods from sbull are used without modification. Since sbullr is a char device, however, it needs read and writemethods. Both are defined to use a single transfer function as follows:

 
ssize_t sbullr_read(struct file *filp, char *buf, size_t size, 
                    loff_t *off)
{
    Sbull_Dev *dev = sbull_devices + 
                    MINOR(filp->f_dentry->d_inode->i_rdev);
    return sbullr_transfer(dev, buf, size, off, READ);
}

ssize_t sbullr_write(struct file *filp, const char *buf, size_t size,
                loff_t *off)
{
    Sbull_Dev *dev = sbull_devices + 
                    MINOR(filp->f_dentry->d_inode->i_rdev);
    return sbullr_transfer(dev, (char *) buf, size, off, WRITE);
}

The sbullr_transfer function handles all of the setup and teardown work, while passing off the actual transfer of data to yet another function. It is written as follows:

 
static int sbullr_transfer (Sbull_Dev *dev, char *buf, size_t count,
                loff_t *offset, int rw)
{
    struct kiobuf *iobuf;       
    int result;
    
    /* Only block alignment and size allowed */
    if ((*offset & SBULLR_SECTOR_MASK) || (count & SBULLR_SECTOR_MASK))
        return -EINVAL;
    if ((unsigned long) buf & SBULLR_SECTOR_MASK)
        return -EINVAL;

    /* Allocate an I/O vector */
    result = alloc_kiovec(1, &iobuf);
    if (result)
        return result;

    /* Map the user I/O buffer and do the I/O. */
    result = map_user_kiobuf(rw, iobuf, (unsigned long) buf, count);
    if (result) {
        free_kiovec(1, &iobuf);
        return result;
    }
    spin_lock(&dev->lock);
    result = sbullr_rw_iovec(dev, iobuf, rw, 
                    *offset >> SBULLR_SECTOR_SHIFT,
                    count >> SBULLR_SECTOR_SHIFT);
    spin_unlock(&dev->lock);

    /* Clean up and return. */
    unmap_kiobuf(iobuf);
    free_kiovec(1, &iobuf);
    if (result > 0)
        *offset += result << SBULLR_SECTOR_SHIFT;
    return result << SBULLR_SECTOR_SHIFT;
}

int map_user_kiobuf(int rw, struct kiobuf *iobuf, 
                    unsigned long address, size_t len);

The result of this call, if all goes well, is that the buffer at the given (user virtual) address with length len is mapped into the given iobuf. This operation can sleep, since it is possible that part of the user buffer will need to be faulted into memory.

So far, we have seen how to prepare a kiobuf for I/O, but not how to actually perform that I/O. The last step involves going through each page in the kiobuf and doing the required transfers; in sbullr, this task is handled by sbullr_rw_iovec. Essentially, this function passes through each page, breaks it up into sector-sized pieces, and passes them to sbull_transfer via a fake request structure:

 
static int sbullr_rw_iovec(Sbull_Dev *dev, struct kiobuf *iobuf, int rw,
                int sector, int nsectors)
{
    struct request fakereq;
    struct page *page;
    int offset = iobuf->offset, ndone = 0, pageno, result;

    /* Perform I/O on each sector */
    fakereq.sector = sector;
    fakereq.current_nr_sectors = 1;
    fakereq.cmd = rw;
    
    for (pageno = 0; pageno < iobuf->nr_pages; pageno++) {
        page = iobuf->maplist[pageno];
        while (ndone < nsectors) {
            /* Fake up a request structure for the operation */
            fakereq.buffer = (void *) (kmap(page) + offset);
            result = sbull_transfer(dev, &fakereq);
	    kunmap(page);
            if (result == 0)
                return ndone;
            /* Move on to the next one */
            ndone++;
            fakereq.sector++;
            offset += SBULLR_SECTOR;
            if (offset >= PAGE_SIZE) {
                offset = 0;
                break;
            }
        }
    }
    return ndone;
}

Some quick tests copying data show that a copy to or from an sbullr device takes roughly two-thirds the system time as the same copy to the block sbull device. The savings is gained by avoiding the extra copy through the buffer cache. Note that if the same data is read several times over, that savings will evaporate -- especially for a real hardware device. Raw device access is often not the best approach, but for some applications it can be a major improvement.

To exploit the DMA capabilities of its hardware, the device driver needs to be able to correctly set up the DMA transfer and synchronize with the hardware. Unfortunately, because of its hardware nature, DMA is very system dependent. Each architecture has its own techniques to manage DMA transfers, and the programming interface is different for each. The kernel can't offer a unified interface, either, because a driver can't abstract too much from the underlying hardware mechanisms. Some steps have been made in that direction, however, in recent kernels.

This chapter concentrates mainly on the PCI bus, since it is currently the most popular peripheral bus available. Many of the concepts are more widely applicable, though. We also touch on how some other buses, such as ISA and SBus, handle DMA.

Overview of a DMA Data Transfer

Before introducing the programming details, let's review how a DMA transfer takes place, considering only input transfers to simplify the discussion.

Data transfer can be triggered in two ways: either the software asks for data (via a function such as read) or the hardware asynchronously pushes data to the system.

In the first case, the steps involved can be summarized as follows:

1. When a process calls read, the driver method allocates a DMA buffer and instructs the hardware to transfer its data. The process is put to sleep.

2. The hardware writes data to the DMA buffer and raises an interrupt when it's done.

3. The interrupt handler gets the input data, acknowledges the interrupt, and awakens the process, which is now able to read data.

1. The hardware raises an interrupt to announce that new data has arrived.

2. The interrupt handler allocates a buffer and tells the hardware where to transfer its data.

3. The peripheral device writes the data to the buffer and raises another interrupt when it's done.

4. The handler dispatches the new data, wakes any relevant process, and takes care of housekeeping.

The processing steps in all of these cases emphasize that efficient DMA handling relies on interrupt reporting. While it is possible to implement DMA with a polling driver, it wouldn't make sense, because a polling driver would waste the performance benefits that DMA offers over the easier processor-driven I/O.

Another relevant item introduced here is the DMA buffer. To exploit direct memory access, the device driver must be able to allocate one or more special buffers, suited to DMA. Note that many drivers allocate their buffers at initialization time and use them until shutdown -- the word allocate in the previous lists therefore means "get hold of a previously allocated buffer.''

Allocating the DMA Buffer

The main problem with the DMA buffer is that when it is bigger than one page, it must occupy contiguous pages in physical memory because the device transfers data using the ISA or PCI system bus, both of which carry physical addresses. It's interesting to note that this constraint doesn't apply to the SBus (see "SBus" in Chapter 15, "Overview of Peripheral Buses"), which uses virtual addresses on the peripheral bus. Some architectures can also use virtual addresses on the PCI bus, but a portable driver cannot count on that capability.

Although DMA buffers can be allocated either at system boot or at runtime, modules can only allocate their buffers at runtime. Chapter 7, "Getting Hold of Memory" introduced these techniques: "Boot-Time Allocation" talked about allocation at system boot, while "The Real Story of kmalloc" and "get_free_page and Friends" described allocation at runtime. Driver writers must take care to allocate the right kind of memory when it will be used for DMA operations -- not all memory zones are suitable. In particular, high memory will not work for DMA on most systems -- the peripherals simply cannot work with addresses that high.

Most devices on modern buses can handle 32-bit addresses, meaning that normal memory allocations will work just fine for them. Some PCI devices, however, fail to implement the full PCI standard and cannot work with 32-bit addresses. And ISA devices, of course, are limited to 16-bit addresses only.

Do-it-yourself allocation

When the kernel cannot return the requested amount of memory, or when you need more than 128 KB (a common requirement for PCI frame grabbers, for example), an alternative to returning -ENOMEM is to allocate memory at boot time or reserve the top of physical RAM for your buffer. We described allocation at boot time in "Boot-Time Allocation" in Chapter 7, "Getting Hold of Memory", but it is not available to modules. Reserving the top of RAM is accomplished by passing a mem= argument to the kernel at boot time. For example, if you have 32 MB, the argument mem=31M keeps the kernel from using the top megabyte. Your module could later use the following code to gain access to such memory:

dmabuf = ioremap( 0x1F00000 /* 31M */, 0x100000 /* 1M */); 

Actually, there is another way to allocate DMA space: perform aggressive allocation until you are able to get enough consecutive pages to make a buffer. We strongly discourage this allocation technique if there's any other way to achieve your goal. Aggressive allocation results in high machine load, and possibly in a system lockup if your aggressiveness isn't correctly tuned. On the other hand, sometimes there is no other way available.

In practice, the code invokes kmalloc(GFP_ATOMIC) until the call fails; it then waits until the kernel frees some pages, and then allocates everything once again. If you keep an eye on the pool of allocated pages, sooner or later you'll find that your DMA buffer of consecutive pages has appeared; at this point you can release every page but the selected buffer. This kind of behavior is rather risky, though, because it may lead to a deadlock. We suggest using a kernel timer to release every page in case allocation doesn't succeed before a timeout expires.

Bus Addresses

As a matter of fact, the situation is slightly more complicated than that. DMA-based hardware uses bus, rather than physical, addresses. Although ISA and PCI addresses are simply physical addresses on the PC, this is not true for every platform. Sometimes the interface bus is connected through bridge circuitry that maps I/O addresses to different physical addresses. Some systems even have a page-mapping scheme that can make arbitrary pages appear contiguous to the peripheral bus.

unsigned long virt_to_bus(volatile void * address);
void * bus_to_virt(unsigned long address);

DMA on the PCI Bus

Dealing with difficult hardware

int pci_dma_supported(struct pci_dev *pdev, dma_addr_t mask);

Here, mask is a simple bit mask describing which address bits the device can successfully use. If the return value is nonzero, DMA is possible, and your driver should set the dma_mask field in the PCI device structure to the mask value. For a device that can only handle 16-bit addresses, you might use a call like this:

if (pci_dma_supported (pdev, 0xffff))
    pdev->dma_mask = 0xffff;
else {
    card->use_dma = 0;   /* We'll have to live without DMA */
    printk (KERN_WARN, "mydev: DMA not supported\n");
}

int pci_set_dma_mask(struct pci_dev *pdev, dma_addr_t mask);

If DMA can be supported with the given mask, this function returns 0 and sets the dma_mask field; otherwise, -EIO is returned.

For devices that can handle 32-bit addresses, there is no need to call pci_dma_supported.

DMA mappings

The PCI code distinguishes between two types of DMA mappings, depending on how long the DMA buffer is expected to stay around:

The two mapping types must be manipulated in different ways; it's time to look at the details.

Setting up consistent DMA mappings

void *pci_alloc_consistent(struct pci_dev *pdev, size_t size,
                           dma_addr_t *bus_addr);

This function handles both the allocation and the mapping of the buffer. The first two arguments are our PCI device structure and the size of the needed buffer. The function returns the result of the DMA mapping in two places. The return value is a kernel virtual address for the buffer, which may be used by the driver; the associated bus address, instead, is returned in bus_addr. Allocation is handled in this function so that the buffer will be placed in a location that works with DMA; usually the memory is just allocated with get_free_pages (but note that the size is in bytes, rather than an order value).

Most architectures that support PCI perform the allocation at the GFP_ATOMIC priority, and thus do not sleep. The ARM port, however, is an exception to this rule.

void pci_free_consistent(struct pci_dev *pdev, size_t size,
                         void *cpu_addr, dma_handle_t bus_addr);

Note that this function requires that both the CPU address and the bus address be provided.

Setting up streaming DMA mappings

When setting up a streaming mapping, you must tell the kernel in which direction the data will be moving. Some symbols have been defined for this purpose:

For a number of reasons that we will touch on shortly, it is important to pick the right value for the direction of a streaming DMA mapping. It may be tempting to just pick PCI_DMA_BIDIRECTIONAL at all times, but on some architectures there will be a performance penalty to pay for that choice.

dma_addr_t pci_map_single(struct pci_dev *pdev, void *buffer,
                          size_t size, int direction);

The return value is the bus address that you can pass to the device, or NULL if something goes wrong.

void pci_unmap_single(struct pci_dev *pdev, dma_addr_t bus_addr,
                      size_t size, int direction);

Here, the size and direction arguments must match those used to map the buffer.

There are some important rules that apply to streaming DMA mappings:

• The buffer must be used only for a transfer that matches the direction value given when it was mapped.

• Once a buffer has been mapped, it belongs to the device, not the processor. Until the buffer has been unmapped, the driver should not touch its contents in any way. Only after pci_unmap_single has been called is it safe for the driver to access the contents of the buffer (with one exception that we'll see shortly). Among other things, this rule implies that a buffer being written to a device cannot be mapped until it contains all the data to write.

• The buffer must not be unmapped while DMA is still active, or serious system instability is guaranteed.

You may be wondering why the driver can no longer work with a buffer once it has been mapped. There are actually two reasons why this rule makes sense. First, when a buffer is mapped for DMA, the kernel must ensure that all of the data in that buffer has actually been written to memory. It is likely that some data will remain in the processor's cache, and must be explicitly flushed. Data written to the buffer by the processor after the flush may not be visible to the device.

Incidentally, bounce buffers are one reason why it is important to get the direction right. PCI_DMA_BIDIRECTIONAL bounce buffers are copied before and after the operation, which is often an unnecessary waste of CPU cycles.

void pci_sync_single(struct pci_dev *pdev, dma_handle_t bus_addr,
                     size_t size, int direction);

Scatter-gather mappings

Finally, if a bounce buffer must be used, it makes sense to coalesce the entire list into a single buffer (since it is being copied anyway).

char *address;

The address of a buffer used in the scatter/gather operation

unsigned int length;

The length of that buffer

int pci_map_sg(struct pci_dev *pdev, struct scatterlist *list,
               int nents, int direction);

The return value will be the number of DMA buffers to transfer; it may be less than nents, the number of scatterlist entries passed in.

Your driver should transfer each buffer returned by pci_map_sg. The bus address and length of each buffer will be stored in the struct scatterlist entries, but their location in the structure varies from one architecture to the next. Two macros have been defined to make it possible to write portable code:

Again, remember that the address and length of the buffers to transfer may be different from what was passed in to pci_map_sg.

void pci_unmap_sg(struct pci_dev *pdev, struct scatterlist *list,
                  int nents, int direction);

Note that nents must be the number of entries that you originally passed to pci_map_sg, and not the number of DMA buffers that function returned to you.

void pci_dma_sync_sg(struct pci_dev *pdev, struct scatterlist *sg,
                     int nents, int direction);

How different architectures support PCI DMA

The differences listed will not be problems for most driver writers, as long as the interface guidelines are followed.

A simple PCI DMA example

int dad_transfer(struct dad_dev *dev, int write, void *buffer, 
                 size_t count)
{
    dma_addr_t bus_addr;
    unsigned long flags;

    /* Map the buffer for DMA */
    dev->dma_dir = (write ? PCI_DMA_TODEVICE : PCI_DMA_FROMDEVICE);
    dev->dma_size = count;
    bus_addr = pci_map_single(dev->pci_dev, buffer, count, 
                              dev->dma_dir);
    dev->dma_addr = bus_addr;

    /* Set up the device */
    writeb(dev->registers.command, DAD_CMD_DISABLEDMA);
    writeb(dev->registers.command, write ? DAD_CMD_WR : DAD_CMD_RD);
    writel(dev->registers.addr, cpu_to_le32(bus_addr));
    writel(dev->registers.len, cpu_to_le32(count));

    /* Start the operation */
    writeb(dev->registers.command, DAD_CMD_ENABLEDMA);
    return 0;
}

This function maps the buffer to be transferred and starts the device operation. The other half of the job must be done in the interrupt service routine, which would look something like this:

void dad_interrupt(int irq, void *dev_id, struct pt_regs *regs)
{
    struct dad_dev *dev = (struct dad_dev *) dev_id;

    /* Make sure it's really our device interrupting */

    /* Unmap the DMA buffer */
    pci_unmap_single(dev->pci_dev, dev->dma_addr, dev->dma_size,
		         dev->dma_dir);

    /* Only now is it safe to access the buffer, copy to user, etc. */
    ...
}

Obviously a great deal of detail has been left out of this example, including whatever steps may be required to prevent attempts to start multiple simultaneous DMA operations.

A quick look at SBus

DMA for ISA Devices

As far as native DMA is concerned, there are three entities involved in a DMA data transfer on the ISA bus:

The channels are numbered from 0 to 7; channel 4 is not available to ISA peripherals because it is used internally to cascade the slave controller onto the master. The available channels are thus 0 to 3 on the slave (the 8-bit channels) and 5 to 7 on the master (the 16-bit channels). The size of any DMA transfer, as stored in the controller, is a 16-bit number representing the number of bus cycles. The maximum transfer size is therefore 64 KB for the slave controller and 128 KB for the master.

Because the DMA controller is a system-wide resource, the kernel helps deal with it. It uses a DMA registry to provide a request-and-free mechanism for the DMA channels and a set of functions to configure channel information in the DMA controller.

Registering DMA usage

int request_dma(unsigned int channel, const char *name); 
void free_dma(unsigned int channel);

The channel argument is a number between 0 and 7 or, more precisely, a positive number less than MAX_DMA_CHANNELS. On the PC, MAX_DMA_CHANNELS is defined as 8, to match the hardware. The name argument is a string identifying the device. The specified name appears in the file /proc/dma, which can be read by user programs.

The return value from request_dma is 0 for success and -EINVAL or -EBUSY if there was an error. The former means that the requested channel is out of range, and the latter means that another device is holding the channel.

We also suggest that you request the DMA channel after you've requested the interrupt line and that you release it before the interrupt. This is the conventional order for requesting the two resources; following the convention avoids possible deadlocks. Note that every device using DMA needs an IRQ line as well; otherwise, it couldn't signal the completion of data transfer.

In a typical case, the code for open looks like the following, which refers to our hypothetical dad module. The dad device as shown uses a fast interrupt handler without support for shared IRQ lines.

int dad_open (struct inode *inode, struct file *filp)
{
    struct dad_device *my_device; 

    /* ... */
    if ( (error = request_irq(my_device.irq, dad_interrupt,
                              SA_INTERRUPT, "dad", NULL)) )
        return error; /* or implement blocking open */

    if ( (error = request_dma(my_device.dma, "dad")) ) {
        free_irq(my_device.irq, NULL);
        return error; /* or implement blocking open */
    }
    /* ... */
    return 0;
}

The close implementation that matches the open just shown looks like this:

void dad_close (struct inode *inode, struct file *filp)
{
    struct dad_device *my_device;

    /* ... */
    free_dma(my_device.dma);
    free_irq(my_device.irq, NULL);
    /* ... */
}

As far as /proc/dma is concerned, here's how the file looks on a system with the sound card installed:

merlino% cat /proc/dma
 1: Sound Blaster8
 4: cascade

Talking to the DMA controller

The spinlock should be held when using the functions described next. It should not be held during the actual I/O, however. A driver should never sleep when holding a spinlock.

The information that must be loaded into the controller is made up of three items: the RAM address, the number of atomic items that must be transferred (in bytes or words), and the direction of the transfer. To this end, the following functions are exported by <asm/dma.h>:

In addition to these functions, there are a number of housekeeping facilities that must be used when dealing with DMA devices:

Using these functions, a driver can implement a function like the following to prepare for a DMA transfer:

int dad_dma_prepare(int channel, int mode, unsigned int buf,
                    unsigned int count)
{
    unsigned long flags;

    flags = claim_dma_lock();
    disable_dma(channel);
    clear_dma_ff(channel);
    set_dma_mode(channel, mode);
    set_dma_addr(channel, virt_to_bus(buf));
    set_dma_count(channel, count);
    enable_dma(channel);
    release_dma_lock(flags);

    return 0;
}

A function like the next one, then, is used to check for successful completion of DMA:

int dad_dma_isdone(int channel)
{
    int residue;
    unsigned long flags = claim_dma_lock ();
    residue = get_dma_residue(channel);
    release_dma_lock(flags);
    return (residue == 0);
}

As we have seen, the 2.4 kernel makes extensive use of pointers to struct page to refer to specific pages in memory. This structure has been present in Linux for a long time, but it was not previously used to refer to the pages themselves; instead, the kernel used logical addresses.

 
#ifdef MAP_NR
#define virt_to_page(page) (mem_map + MAP_NR(page))
#endif

 
#ifndef get_page
#  define get_page(p) atomic_inc(&(p)->count)
#endif

There have also been changes to the the various vm_ops methods stored in the VMA:

Because nopage used to return unsigned long, its job was to return the logical address of the page of interest, rather than its mem_map entry.

In the 2.0 kernel, the init_mm structure was not exported to modules. Thus, a module that wished to access init_mm had to dig through the task table to find it (as part of the init process). When running on a 2.0 kernel, scullp finds init_mm with this bit of code:

 
static struct mm_struct *init_mm_ptr;
#define init_mm (*init_mm_ptr) /* to avoid ifdefs later */

static void retrieve_init_mm_ptr(void)
{
    struct task_struct *p;

    for (p = current ; (p = p->next_task) != current ; )
        if (p->pid == 0)
            break;

    init_mm_ptr = p->mm;
}

Another thing the 2.0 kernel did not have was maintenance of the module's usage count in the presence of memory-mapped areas. Drivers that implement mmap under 2.0 need to provide open and close VMA operations to adjust the usage count themselves. The sample source modules that implement mmap provide these operations.

int (*mmap)(struct inode *inode, struct file *filp, 
            struct vm_area_struct *vma);

Changes to DMA

For those who need to write portable PCI drivers, sysdep.h in the sample code includes a simple implementation of the 2.4 DMA interface that may be used on older kernels.

The ISA interface, on the other hand, is almost unchanged since Linux 2.0. ISA is an old architecture, after all, and there have not been a whole lot of changes to keep up with. The only addition was the DMA spinlock in 2.2; prior to that kernel, there was no need to protect against conflicting access to the DMA controller. Versions of these functions have been defined in sysdep.h; they disable and restore interrupts, but perform no other function.