Linux Kernel Architecture

Chapter 16: Page and Buffer Cache

❑ radix_tree_deleteremoves a tree element selected by means of its integer key. A pointer to the

deleted object is returned if deletion was successful.

❑ radix_tree_tag_getchecks if a tag is present on a radix tree node. If the tag is set, the function

returns1;otherwise,0.

❑ radix_tree_tag_cleardeletes a tag in a radix tree node. The change is propagated upward in

the tree; that is, if all elements on one level have no tags, then the bit is also removed in the next

higher level, and so on. The address of the tagged item is returned upon success.

These functions are implemented largely by shifting numbers as described in Appendix C.

To ensure that radix trees are manipulated very quickly, the kernel uses a separate slab cache that holds

instances ofradix_tree_nodefor rapid allocation.

Caution: The slab cache stores only the data structures needed to create the tree.

This has nothing to do with the memory used for the cached pages, which is

allocated and managed independently.

Each radix tree also has a per-CPU pool of pre-allocated node elements to further speed the insertion

of new elements into the tree.radix_tree_preloadis a container that ensures that at least one element

resides in this cache. The function is always invoked before an individual element is added to the radix

tree usingradix_tree_insert(this is ignored in the following sections).^4

Locking

Radix trees do not provide any form of protection against concurrent access in general. As usual in the

kernel, it is the responsibility of each subsystem that deploys radix trees to care for correction locking

or any other synchronization primitive, as discussed in Chapter 5. However, an exception is made for

several important read functions. This includesradix_tree_lookupto perform a lookup operation,

radix_tree_tag_getto obtain a tag on a radix tree node, andradix_tree_taggedto test whether any

items in the tree are tagged.

The first two functions can be called without subsystem-specific locking if they are embraced by

rcu_read_lock()...rcu_read_unlock(), while the third function does not require any lock at all.

rcu_headprovides the required connection between radix tree nodes and the RCU implementation.

Notice that<radix-tree.h>contains more advice on how to implement proper synchronization for

radix trees, so I will not discuss the problem in more detail here.

16.3.3 Operations on Address Spaces

Address spaces connect backing stores with memory segments. Not only data structures but also func-

tions are needed to perform the transfer operations between the two. Because address spaces can be

used in various combinations, the requisite functions are not defined statically but must be determined

according to the particular mapping with the help of a special structure that holds function pointers to

the appropriate implementation.

(^4) To be more accurate, the insert operations are embedded between radix_tree_preload()...andradixtree
preload_end(). The use of per-CPU variables means that kernel preemption (see Chapter 2) must be disabled and then
enabled again upon completion of the operation. This is currently the only task ofradix_tree_preload_end.