All unused buffer heads are collected in a simply linked list, whose first element is addressed by the unused_list variable. Each buffer head stores the address of the next list element in the b_next_free field. The current number of elements in the list is stored in the nr_unused_buffer_heads variable. The unused_list_lock spin lock protects the list against concurrent accesses in multiprocessor systems.

The list of unused buffer heads acts as a primary memory cache for the buffer head objects, while the bh_cachep slab allocator cache is a secondary memory cache. When a buffer head is no longer needed, it is inserted into the list of unused buffer heads. Buffer heads are released to the slab allocator (a preliminary step to letting the kernel free the memory associated with them altogether) only when the number of list elements exceeds MAX_UNUSED_BUFFERS (usually 100 elements). In other words, a buffer head in this list is considered an allocated object by the slab allocator and an unused data structure by the buffer cache.

A subset of NR_RESERVED (usually 80) elements in the list is reserved for page I/O operations. This is done to prevent nasty deadlocks caused by the lack of free buffer heads. As we shall see in Chapter 16, if free memory is scarce, the kernel can try to free a page frame by swapping out some page to disk. To do this, it requires at least one additional buffer head to perform the page I/O file operation. If the swapping algorithm fails to get a buffer head, it simply keeps waiting and lets writes to files proceed to free up buffers, since at least NR_RESERVED buffer heads are going to be released as soon as the ongoing file operations terminate.

The get_unused_buffer_head( ) function is invoked to get a new buffer head. It essentially performs the following operations:

The put_unused_buffer_head( ) function performs the reverse operation, releasing a buffer head. It inserts the object in the list of unused buffer heads if that list has fewer than MAX_UNUSED_BUFFERS elements; otherwise, it releases the object to the slab allocator by invoking kmem_cache_free( ) on the buffer head.

When a buffer belongs to the buffer cache, the flags of the corresponding buffer head describe its current status (see Section 13.4.4). For instance, when a block not present in the cache must be read from disk, a new buffer is allocated and the BH_Uptodate flag of the buffer head is cleared because the buffer’s contents are meaningless. While filling the buffer by reading from disk, the BH_Lock flag is set to protect the buffer from being reclaimed. If the read operation terminates successfully, the BH_Uptodate flag is set and the BH_Lock flag is cleared. If the block must be written to disk, the buffer content is modified and the BH_Dirty flag is set; the flag is cleared only after the buffer is successfully written to disk.

Any buffer head associated with a used buffer is contained in a doubly linked list, implemented by means of the b_next_free and b_prev_free fields. There are three different lists, identified by an index defined as a macro (BUF_CLEAN, BUF_LOCKED, and BUF_DIRTY). We’ll define these lists in a moment.

The three lists are introduced to speed up the functions that flush dirty buffers to disk (see Section 14.2.4 later in this chapter). For reasons of efficiency, a buffer head is not moved right away from one list to another when it changes status; this makes the following description a bit murky.

For any buffer head associated with a used buffer, the b_list field of the buffer head stores the index of the list containing the buffer. The lru_list array^[99] stores the address of the first element in each list, the nr_buffers_type array stores the number of elements in each list, and the size_buffers_type array stores the total capacity of the buffers in each list (in byte). The lru_list_lock spin lock protects these arrays from concurrent accesses in multiprocessor systems.

The mark_buffer_dirty( ) and mark_buffer_clean( ) functions set and clear, respectively, the BH_Dirty flag of a buffer head. To keep the number of dirty buffers in the system bounded, mark_buffer_dirty( ) invokes the balance_dirty( ) function (see the later section Section 14.2.4). Both functions also invoke the refile_buffer( ) function, which moves the buffer head into the proper list according to the value of the BH_Dirty and BH_Lock flags.

Beside the BUF_DIRTY list, the kernel manages two doubly linked lists of dirty buffers for every inode object. They are used whenever the kernel must flush all dirty buffers of a given file — for instance, when servicing the fsync( ) or fdatasync( ) service calls (see Section 14.2.4.3 later in this chapter).

The first of the two lists includes buffers containing the file’s control data (like the disk inode itself), while the other list includes buffers containing the file’s data. The heads of these lists are stored in the i_dirty_buffers and i_dirty_data_buffers fields of the inode object, respectively. The b_inode_buffers field of any buffer head stores the pointers to the next and previous elements of these lists. Both of them are protected by the lru_list_lock spin lock just mentioned. The buffer_insert_inode_queue( ) and buffer_insert_inode_data_queue( ) functions are used, respectively, to insert a buffer head in the i_dirty_buffers and i_dirty_data_buffers lists. The remove_inode_queue( ) function removes a buffer head from the list that includes it.

The addresses of the buffer heads belonging to the buffer cache are inserted into a hash table. Given a device identifier and a block number, the kernel can use the hash table to quickly derive the address of the corresponding buffer head, if one exists. The hash table noticeably improves kernel performance because checks on buffer heads are frequent. Before starting a block I/O operation, the kernel must check whether the required block is already in the buffer cache; in this situation, the hash table lets the kernel avoid a lengthy sequential scan of the lists of cached buffers.

The hash table is stored in the hash_table array, which is allocated during system initialization and whose size depends on the amount of RAM installed on the system. For example, for systems having 128 MB of RAM, hash_table is stored in 4 page frames and includes 4,096 buffer head pointers. As usual, entries that cause a collision are chained in doubly linked lists implemented by means of the b_next and b_pprev fields of each buffer head. The hash_table_lock read/write spin lock protects the hash table data structures from concurrent accesses in multiprocessor systems.

The get_hash_table( ) function retrieves a buffer head from the hash table. The buffer head to be located is identified by three parameters: the device number, the block number, and the size of the corresponding data block. The function hashes the values of the device number and the block number, and looks into the hash table to find the first element in the collision list; then it checks the b_dev, b_blocknr, and b_size fields of each element in the list and returns the address of the requested buffer head. If the buffer head is not in the cache, the function returns NULL.

The b_count field of the buffer head is a usage counter for the corresponding buffer. The counter is incremented right before each operation on the buffer and decremented right after. It acts mainly as a safety lock, since the kernel never destroys a buffer (or its contents) as long as it has a non-null usage counter. Instead, the cached buffers are examined either periodically or when the free memory becomes scarce, and only those buffers that have null counters may be destroyed (see Chapter 16). In other words, a buffer with a null usage counter may belong to the buffer cache, but it cannot be determined how long the buffer will stay in the cache.

When a kernel control path wishes to access a buffer, it should increment the usage counter first. This task is performed by the getblk( ) function, which is usually invoked to locate the buffer, so that the increment need not be done explicitly by higher-level functions. When a kernel control path stops accessing a buffer, it may invoke either brelse( ) or bforget( ) to decrement the corresponding usage counter.The difference between these two functions is that bforget( ) also marks the buffer as clean, thus forcing the kernel to forget any change in the buffer that has yet to be written on disk.

The kernel allocates a new buffer page when it discovers that the buffer cache does not include data for a given block. In this case, the kernel invokes the grow_buffers( ) function, passing to it three parameters that identify the block:

The function essentially performs the following actions:

The bdflush kernel thread (also called kflushd ) is created during system initialization. It executes the bdflush( ) function, which selects some dirty buffers and forces an update of the corresponding blocks on the physical block devices.

Some system parameters control the behavior of bdflush; they are stored in the b_un field of the bdf_prm table and are accessible either by means of the /proc/sys/vm/bdflush file or by invoking the bdflush( ) system call. Each parameter has a default standard value, although it may vary within a minimum and a maximum value stored in the bdflush_min and bdflush_max tables, respectively. The parameters are listed in Table 14-4.^[101]

The most typical cases that cause the kernel thread to be woken up are:

To wake up bdflush, the kernel invokes the wakeup_bdflush( ) function, which simply executes:

wake_up_interruptible(&bdflush_wait);

to wake up the process suspended in the bdflush_wait task queue. There is just one process in this wait queue, namely bdflush itself.

The core of the bdflush( ) function is the following endless loop:

for (;;) {  
    if (emergency_sync_scheduled) /* Only if the kernel has been compiled */
        do_emergency_sync( );      /*   with Magic SysRq Key support       */
    spin_lock(&lru_list_lock);
    if (!write_some_buffers(0) || balance_dirty_state( ) < 0) {
        wait_for_some_buffers(0);
        interruptible_sleep_on(&bdflush_wait);
    } 
}

If the Linux kernel has been compiled with the Magic SysRq Key option, bdflush( ) checks whether the user has requested an emergency sync. If so, the function invokes do_emergency_sync( ) to execute fsync_dev( ) on all existing block devices, flushing all dirty buffers (see the later section Section 14.2.4.3).

Next, the function acquires the lru_list_lock spin lock, and invokes the write_some_buffers( ) function, which tries to activate block I/O write operations for up to 32 unlocked dirty buffers. Once the write operations have been activated, write_some_buffers( ) releases the lru_list_lock spin lock and returns 0 if less than 32 unlocked dirty buffers have been found; it returns a negative value otherwise.

If write_some_buffers( ) didn’t find 32 buffers to flush, or the number of dirty or locked buffers falls below the percentage threshold given by the bdflush’s parameter nfract, the bdflush kernel thread goes to sleep. To do this, it first invokes the wait_for_some_buffers( ) function so that it sleeps until all I/O data transfers of the buffers in the BUF_LOCKED list terminate. During this time interval, the kernel thread is not woken up even if the kernel executes the wakeup_bdflush( ) function. Once data transfers terminate, the bdflush( ) function invokes interruptible_sleep_on( ) on the bdflush_wait wait queue to sleep until the next wakeup_bdflush( ) invocation.

Since the bdflush kernel thread is usually activated only when there are too many dirty buffers or when more buffers are needed and available memory is scarce, some dirty buffers might stay in RAM for an arbitrarily long time before being flushed to disk. The kupdate kernel thread is thus introduced to flush the older dirty buffers.^[102]

As shown in Table 14-4, age_buffer is a time-out parameter that specifies the time for buffers to age before kupdate writes them to disk (usually 30 seconds), while the interval field of the bdf_prm table stores the delay in ticks between two activations of the kupdate kernel thread (usually five seconds). If this field is null, the kernel thread is normally stopped, and is activated only when it receives a SIGCONT signal.

When the kernel modifies the contents of some buffer, it sets the b_flushtime field of the corresponding buffer head to the time (in jiffies) when it should later be flushed to disk. The kupdate kernel thread selects only the dirty buffers whose b_flushtime field is smaller than the current value of jiffies.

The kupdate kernel thread runs the kupdate( ) function; it keeps executing the following endless loop:

for (;;) {
    wait_for_some_buffers(0);
    if (bdf_prm.b_un.interval) {
        tsk->state = TASK_INTERRUPTIBLE;
        schedule_timeout(bdf_prm.b_un.interval);
    } else {
            tsk->state = TASK_STOPPED; 
            schedule( ); /* wait for SIGCONT */
    }
    sync_old_buffers( );
}

First of all, the kernel thread suspends itself until the I/O data transfers have been completed for all buffers in the BUF_LOCKED list. Then, if bdf.prm.b_un.interval interval is not null, the thread goes to sleep for the specified amount of ticks (see Section 6.6.2); otherwise, the thread stops itself until a SIGCONT signal is received (see Section 10.1).

The core of the kupdate( ) function consists of the sync_old_buffers( ) function. The operations to be performed are very simple for standard filesystems used with Unix; all the function has to do is write dirty buffers to disk. However, some nonnative filesystems introduce complexities because they store their superblock or inode information in complicated ways. sync_old_buffers( ) executes the following steps:

Three different system calls are available to user applications to flush dirty buffers to disk:

The core of the sync( ) system call is the fsync_dev( ) function, which performs the following actions:

The fsync( ) system call forces the kernel to write to disk all dirty buffers that belong to the file specified by the fd file descriptor parameter (including the buffer containing its inode, if necessary). The system service routine derives the address of the file object and then invokes the fsync method. Usually, this method simply invokes the fsync_inode_buffers( ) function, which scans the two lists of dirty buffers of the inode object (see the earlier section Section 14.2.1.3), and invokes ll_rw_block( ) on each element present in the lists. The function then suspends the calling process until all dirty buffers of the file have been written to disk by invoking wait_on_buffer( ) on each locked buffer. Moreover, the service routine of the fsync( ) system call flushes the dirty pages that belong to the memory mapping of the file, if any (see Section 15.2.5).

The fdatasync( ) system call is very similar to fsync( ), but writes to disk only the buffers that contain the file’s data, not those that contain inode information. Since Linux 2.4 does not have a specific file method for fdatasync( ), this system call uses the fsync method and is thus identical to fsync( ).