Data structures and algorithms in the Linux kernel
Summary
A curated overview shows where the Linux kernel uses trees, hash lists, heaps, compression and scheduling algorithms in practice. The kernel provides generic list and tree helpers. CFS uses a red-black tree.
Ideas
- Red-black trees manage ordered dynamic sets.
- Hash tables speed up key access in several subsystems.
- Bitmaps store dense sets with little overhead.
- Schedulers combine data structures with time-critical selection rules.
Insights
- Production code shows edge cases that textbook implementations leave out.
- Data structures are chosen according to load profile and kernel constraints.
- General algorithms get domain-specific synchronisation and memory management.
Facts
- The kernel sources contain several compression algorithms.
Recommendations
- Read the callers together with the data structure implementation.
- Check locking and lifetime rules before making changes.
References
Links to the original source and the Web Archive open in a new tab.