What is RCU (Read-copy-update) from Wikipedia http://en.wikipedia.org/wiki/Read-copy-update:

In computer operating systems, read-copy-update (RCU) is a synchronization mechanism implementing a kind of mutual exclusion that can sometimes be used as an alternative to a readers-writer lock. It allows extremely low overhead, wait-free reads. However, RCU updates can be expensive, as they must leave the old versions of the data structure in place to accommodate pre-existing readers. These old versions are reclaimed after all pre-existing readers finish their accesses.

Linux Kernel RCU API:

  • rcu_read_lock() – Marks an RCU-protected data structure so that it won't be reclaimed for the full duration of that critical section.
  • rcu_read_unlock() – Used by a reader to inform the reclaimer that the reader is exiting an RCU read-side critical section. Note that RCU read-side critical sections may be nested and/or overlapping.

For example for radix tree (mm/readahead.c):

 * Count contiguously cached pages from @offset-1 to @offset-@max,
 * this count is a conservative estimation of
 *     - length of the sequential read sequence, or
 *     - thrashing threshold in memory tight systems
static pgoff_t count_history_pages(struct address_space *mapping,  
                   struct file_ra_state *ra,
                   pgoff_t offset, unsigned long max)
    pgoff_t head;

    head = radix_tree_prev_hole(&mapping->page_tree, offset - 1, max);

    return offset - 1 - head;