Lib

Purpose

lib/ is the kernel's library directory: data-structure implementations (list, rbtree, xarray, idr, radix-tree, maple_tree, bitmap), string and number helpers (string.c, vsprintf.c, sort.c), CRC and hash routines, simple compression, integer-math helpers, and a number of specialized utilities used across the tree.

It is small relative to other top-level dirs (~12 MB) but extremely heavily depended on.

Notable contents

Area	Files
Data structures	lib/list_debug.c, lib/rbtree.c, lib/maple_tree.c, lib/xarray.c, lib/radix-tree.c, lib/idr.c, lib/iov_iter.c, lib/llist.c, lib/btree.c, lib/plist.c
Strings & format	lib/string.c, lib/vsprintf.c, lib/string_helpers.c, lib/parser.c
Bitmaps	lib/bitmap.c, lib/cpumask.c, lib/find_bit.c
Compression	lib/zstd/, lib/lz4/, lib/lzo/, lib/xz/, lib/decompress_*.c
Hash & checksum	lib/crc32.c, lib/crc16.c, lib/crc-t10dif.c, lib/jhash.c (in include/linux/), lib/siphash.c
Math	lib/div64.c, lib/gcd.c, lib/sort.c, lib/glob.c
Allocators	lib/genalloc.c, lib/percpu_counter.c
Refcount	lib/refcount.c
Tests	lib/test_*.c, lib/kunit/
Networking helpers	lib/argv_split.c, lib/zlib_inflate/, lib/zlib_deflate/

The directory is flat and has no real hierarchy; ls lib/ is the best directory.

Key abstractions you'll see across the tree

• struct list_head — doubly-linked list. Defined in include/linux/list.h. Probably the most-used data structure in the kernel.
• struct rb_node, struct rb_root — red-black tree.
• struct maple_tree — modern tree used by mm to track VMAs (replaced rb-tree).
• struct xarray — wide-key associative array (replaced radix_tree).
• struct idr — int → ptr mapping.
• refcount_t — saturating reference counter.
• struct iov_iter — generic iterator over user/kernel iovecs / pages / bvecs / xarray. The unifying abstraction for I/O.
• struct cpumask — bitmap of CPUs.

Integration points

Almost everything depends on lib/. Specifically:

• mm/ uses xarray (page cache), maple_tree (VMAs), iov_iter, percpu_counter.
• fs/ uses xarray, hashtable, list_lru, inode_lru.
• net/ uses jhash/siphash, list, bitmap.
• drivers/ rely on dozens of these primitives.

Tests

lib/test_*.c and lib/kunit/ contain self-tests for these primitives. They run under KUnit or as boot-time module init.

Entry points for modification

• A new general-purpose data structure: rare. The bar is high; existing maintainers (Andrew Morton et al.) want to know why nothing existing fits.
• A bug fix or perf improvement to an existing data structure: send to whoever last touched the file (./scripts/get_maintainer.pl).
• A new test: drop a lib/test_<x>.c and add a Kconfig entry.

Related pages

• Memory management — heavy lib user.
• Filesystems — xarray, lists.
• Kernel core — refcount, list helpers.