📊
linux-insides
  • README
  • Summary
    • Booting
      • From bootloader to kernel
      • First steps in the kernel setup code
      • Video mode initialization and transition to protected mode
      • Transition to 64-bit mode
      • Kernel decompression
      • Kernel load address randomization
    • Initialization
      • First steps in the kernel
      • Early interrupts handler
      • Last preparations before the kernel entry point
      • Kernel entry point
      • Continue architecture-specific boot-time initializations
      • Architecture-specific initializations, again...
      • End of the architecture-specific initializations, almost...
      • Scheduler initialization
      • RCU initialization
      • End of initialization
    • Interrupts
      • Introduction
      • Start to dive into interrupts
      • Interrupt handlers
      • Initialization of non-early interrupt gates
      • Implementation of some exception handlers
      • Handling Non-Maskable interrupts
      • Dive into external hardware interrupts
      • Initialization of external hardware interrupts structures
      • Softirq, Tasklets and Workqueues
      • Last part
    • System calls
      • Introduction to system calls
      • How the Linux kernel handles a system call
      • vsyscall and vDSO
      • How the Linux kernel runs a program
      • Implementation of the open system call
      • Limits on resources in Linux
    • Timers and time management
      • Introduction
      • Clocksource framework
      • The tick broadcast framework and dyntick
      • Introduction to timers
      • Clockevents framework
      • x86 related clock sources
      • Time related system calls
    • Synchronization primitives
      • Introduction to spinlocks
      • Queued spinlocks
      • Semaphores
      • Mutex
      • Reader/Writer semaphores
      • SeqLock
      • RCU
      • Lockdep
    • Memory management
      • Memblock
      • Fixmaps and ioremap
      • kmemcheck
    • Cgroups
      • Introduction to Control Groups
    • SMP
    • Concepts
      • Per-CPU variables
      • Cpumasks
      • The initcall mechanism
      • Notification Chains
    • Data Structures in the Linux Kernel
      • Doubly linked list
      • Radix tree
      • Bit arrays
    • Theory
      • Paging
      • Elf64
      • Inline assembly
      • CPUID
      • MSR
    • Initial ram disk
    • Misc
      • Linux kernel development
      • How the kernel is compiled
      • Linkers
      • Program startup process in userspace
      • Write and Submit your first Linux kernel Patch
      • Data types in the kernel
    • KernelStructures
      • IDT
    • Useful links
    • Contributors
Powered by GitBook
On this page
  • Radix tree
  • Linux kernel radix tree API
  • Links

Was this helpful?

  1. Summary
  2. Data Structures in the Linux Kernel

Radix tree

PreviousDoubly linked listNextBit arrays

Last updated 2 years ago

Was this helpful?

Radix tree

As you already know Linux kernel provides many different libraries and functions which implement different data structures and algorithms. In this part we will consider one of these data structures - . There are two files which are related to radix tree implementation and API in the linux kernel:

Lets talk about what a radix tree is. Radix tree is a compressed trie where a is a data structure which implements an interface of an associative array and allows to store values as key-value. The keys are usually strings, but any data type can be used. A trie is different from an n-tree because of its nodes. Nodes of a trie do not store keys; instead, a node of a trie stores single character labels. The key which is related to a given node is derived by traversing from the root of the tree to this node. For example:

               +-----------+
               |           |
               |    " "    |
               |           |
        +------+-----------+------+
        |                         |
        |                         |
   +----v------+            +-----v-----+
   |           |            |           |
   |    g      |            |     c     |
   |           |            |           |
   +-----------+            +-----------+
        |                         |
        |                         |
   +----v------+            +-----v-----+
   |           |            |           |
   |    o      |            |     a     |
   |           |            |           |
   +-----------+            +-----------+
                                  |
                                  |
                            +-----v-----+
                            |           |
                            |     t     |
                            |           |
                            +-----------+

So in this example, we can see the trie with keys, go and cat. The compressed trie or radix tree differs from trie in that all intermediates nodes which have only one child are removed.

struct radix_tree_root {
         unsigned int            height;
         gfp_t                   gfp_mask;
         struct radix_tree_node  __rcu *rnode;
};

This structure presents the root of a radix tree and contains three fields:

  • height - height of the tree;

  • gfp_mask - tells how memory allocations will be performed;

  • rnode - pointer to the child node.

The first field we will discuss is gfp_mask:

Low-level kernel memory allocation functions take a set of flags as - gfp_mask, which describes how that allocation is to be performed. These GFP_ flags which control the allocation process can have following values: (GFP_NOIO flag) means allocation can block but must not initiate disk I/O; (__GFP_HIGHMEM flag) means either ZONE_HIGHMEM or ZONE_NORMAL memory can be used; (GFP_ATOMIC flag) means the allocation is high-priority and must not sleep, etc.

  • GFP_NOIO - allocation can block but must not initiate disk I/O;

  • __GFP_HIGHMEM - either ZONE_HIGHMEM or ZONE_NORMAL can be used;

  • GFP_ATOMIC - allocation process is high-priority and must not sleep;

etc.

The next field is rnode:

struct radix_tree_node {
        unsigned int    path;
        unsigned int    count;
        union {
                struct {
                        struct radix_tree_node *parent;
                        void *private_data;
                };
                struct rcu_head rcu_head;
        };
        /* For tree user */
        struct list_head private_list;
        void __rcu      *slots[RADIX_TREE_MAP_SIZE];
        unsigned long   tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
};

This structure contains information about the offset in a parent and height from the bottom, count of the child nodes and fields for accessing and freeing a node. This fields are described below:

  • path - offset in parent & height from the bottom;

  • count - count of the child nodes;

  • parent - pointer to the parent node;

  • private_data - used by the user of a tree;

  • rcu_head - used for freeing a node;

  • private_list - used by the user of a tree;

The two last fields of the radix_tree_node - tags and slots are important and interesting. Every node can contains a set of slots which are store pointers to the data. Empty slots in the Linux kernel radix tree implementation store NULL. Radix trees in the linux kernel also supports tags which are associated with the tags fields in the radix_tree_node structure. Tags allow individual bits to be set on records which are stored in the radix tree.

Now that we know about radix tree structure, it is time to look on its API.

Linux kernel radix tree API

We start from the data structure initialization. There are two ways to initialize a new radix tree. The first is to use RADIX_TREE macro:

RADIX_TREE(name, gfp_mask);

As you can see we pass the name parameter, so with the RADIX_TREE macro we can define and initialize radix tree with the given name. Implementation of the RADIX_TREE is easy:

#define RADIX_TREE(name, mask) \
         struct radix_tree_root name = RADIX_TREE_INIT(mask)

#define RADIX_TREE_INIT(mask)   { \
        .height = 0,              \
        .gfp_mask = (mask),       \
        .rnode = NULL,            \
}

At the beginning of the RADIX_TREE macro we define instance of the radix_tree_root structure with the given name and call RADIX_TREE_INIT macro with the given mask. The RADIX_TREE_INIT macro just initializes radix_tree_root structure with the default values and the given mask.

The second way is to define radix_tree_root structure by hand and pass it with mask to the INIT_RADIX_TREE macro:

struct radix_tree_root my_radix_tree;
INIT_RADIX_TREE(my_tree, gfp_mask_for_my_radix_tree);

where:

#define INIT_RADIX_TREE(root, mask)  \
do {                                 \
        (root)->height = 0;          \
        (root)->gfp_mask = (mask);   \
        (root)->rnode = NULL;        \
} while (0)

makes the same initialization with default values as it does RADIX_TREE_INIT macro.

The next are two functions for inserting and deleting records to/from a radix tree:

  • radix_tree_insert;

  • radix_tree_delete;

The first radix_tree_insert function takes three parameters:

  • root of a radix tree;

  • index key;

  • data to insert;

The radix_tree_delete function takes the same set of parameters as the radix_tree_insert, but without data.

Searching through a radix tree is implemented in three ways:

  • radix_tree_lookup;

  • radix_tree_gang_lookup;

  • radix_tree_lookup_slot.

The first radix_tree_lookup function takes two parameters:

  • root of a radix tree;

  • index key;

This function tries to find the given key in the tree and return the record associated with this key. The second radix_tree_gang_lookup function have the following signature

unsigned int radix_tree_gang_lookup(struct radix_tree_root *root,
                                    void **results,
                                    unsigned long first_index,
                                    unsigned int max_items);

and returns number of records, sorted by the keys, starting from the first index. Number of the returned records will not be greater than max_items value.

And the last radix_tree_lookup_slot function will return the slot which will contain the data.

Links

Radix tree in Linux kernel is the data structure which maps values to integer keys. It is represented by the following structures from the file :

Radix tree
include/linux/radix-tree.h
lib/radix-tree.c
trie
include/linux/radix-tree.h
Radix tree
Trie