Overview(9)

✨ OVERVIEW ✨

okay so welcome to Overview(9) 💖 this is from the Kernel API Manual and it's lowkey just a lil notes page — a few notes about the KSM scanning process, so that the data structures below make sense to you bestie. no cap, read this first or the structs will look like gibberish 🫶

---

so. KSM has a whole problem: scanning everything all the time is way too much. to reduce that excessive scanning, KSM sorts the memory pages by their contents into a data structure that holds pointers to the pages' locations. iconic behavior honestly ✨

but here's the ✨plot twist✨ — the contents of the pages may change at any moment 😭 so KSM cannot just insert the pages into a normal sorted tree and expect it to find anything. like, that tree would be lying to it. so instead KSM uses two data structures: the stable tree and the unstable tree. two besties, two jobs 💅

🌸 the stable tree

the stable tree holds pointers to all the merged pages (ksm pages), sorted by their contents. and because each such page is write-protected, searching on this tree is fully assured to be working (except when pages are unmapped) — and that's why this tree is called the stable tree. she's stable, she's secure, she's not going anywhere 👑

the stable tree node includes information required for reverse mapping from a KSM page to virtual addresses that map this page.

and to avoid large latencies of the rmap walks on KSM pages, KSM maintains two types of nodes in the stable tree:

• the regular nodes that keep the reverse mapping structures in a linked list
• the "chains" that link nodes ("dups") that represent the same write protected memory content, but each "dup" corresponds to a different KSM page copy of that content

internally, the regular nodes, "dups" and "chains" are all represented using the same struct ksm_stable_node structure. one struct, three looks, main character energy fr fr 🦋

🌀 the unstable tree

in addition to the stable tree, KSM uses a second data structure called the unstable tree — this tree holds pointers to pages which have been found to be "unchanged for a period of time". the unstable tree sorts these pages by their contents, but since they are not write-protected, KSM cannot rely upon the unstable tree to work correctly 😬 the unstable tree is liable to be corrupted as its contents are modified, and so it is called unstable. she's going through something, okay 💀

---

🎀 how KSM solves this problem

KSM solves this problem by several techniques:

1. The unstable tree is flushed every time KSM completes scanning all memory areas, and then the tree is rebuilt again from the beginning.
2. KSM will only insert into the unstable tree, pages whose hash value has not changed since the previous scan of all memory areas.
3. The unstable tree is a RedBlack Tree — so its balancing is based on the colors of the nodes and not on their contents, assuring that even when the tree gets "corrupted" it won't get out of balance, so scanning time remains the same (also, searching and inserting nodes in an rbtree uses the same algorithm, so we have no overhead when we flush and rebuild). not her being immune to drama 🔥
4. KSM never flushes the stable tree, which means that even if it were to take 10 attempts to find a page in the unstable tree, once it is found, it is secured in the stable tree. (When we scan a new page, we first compare it against the stable tree, and then against the unstable tree.)

💜 and if the merge_across_nodes tunable is unset, then KSM maintains multiple stable trees and multiple unstable trees: one of each for each NUMA node. so many trees. a whole forest bestie 🌈

---

👑 SEE ALSO 👑

go read these, they're literally the rest of the lore 🧚 no skimming:

• Kernel file ./mm/ksm.c struct ksm_mm_slot(9), ksm_scan(9), ksm_stable_node(9), ksm_rmap_item(9), advisor_ctx(9), replace_page(9), ksm_do_scan(9), ksm_vma_flags(9), ksm_enable_merge_any(9), ksm_disable_merge_any(9)

---

anyway that's the page 🎀 this came to you from ./mm, dated October 2026, and it's Overview(9) in the Kernel API Manual — mwah, go read ksm.c now, i'm obsessed with you for making it this far 💅💖✨