linux-6.12.1/mm/ksm.c

73  * Therefore KSM uses two data structures - the stable and the unstable tree.
96  * unstable tree: this tree holds pointers to pages which have been found to
97  * be "unchanged for a period of time".  The unstable tree sorts these pages
99  * upon the unstable tree to work correctly - the unstable tree is liable to
100  * be corrupted as its contents are modified, and so it is called unstable.
104  * 1) The unstable tree is flushed every time KSM completes scanning all
106  * 2) KSM will only insert into the unstable tree, pages whose hash value
108  * 3) The unstable tree is a RedBlack Tree - so its balancing is based on the
114  *    take 10 attempts to find a page in the unstable tree, once it is found,
116  *    compare it against the stable tree, and then against the unstable tree.)
119  * stable trees and multiple unstable trees: one of each for each NUMA node.
137  * @seqnr: count of completed full scans (needed when removing unstable node)
192  * @nid: NUMA node id of unstable tree in which linked (may not match page)
196  * @node: rb node of this rmap_item in the unstable tree
207 		int nid;		/* when node of unstable tree */
212 	unsigned int oldchecksum;	/* when unstable */
216 		struct rb_node node;	/* when node of unstable tree */
224 #define SEQNR_MASK	0x0ff	/* low bits of unstable tree seqnr */
225 #define UNSTABLE_FLAG	0x100	/* is a node of the unstable tree */
228 /* The stable and unstable tree heads */
264 /* The number of nodes in the unstable tree */
769  * stable and unstable pages from all nodes with roots in index 0. Otherwise,
770  * every node has its own stable and unstable tree.
962  * Removing rmap_item from stable or unstable tree.
963  * This function will clean the information from the stable/unstable tree.
1562 	/* Unstable nid is in union with stable anon_vma: remove first */  in try_to_merge_with_ksm_page()
1869 				 * in the unstable tree to create a  in stable_tree_search()
2088  * else insert rmap_item into the unstable tree.
2090  * This function searches for a page in the unstable tree identical to the
2092  * tree, we insert rmap_item as a new object into the unstable tree.
2146 			 * it will be flushed out and put in the right unstable  in unstable_tree_search_insert()
2209  * be inserted into the unstable tree, or merged with a page already there and
2249 		 * don't want to insert it in the unstable tree, and we don't want  in cmp_and_merge_page()
3034 			/* Ignore the stable/unstable/sqnr flags */  in rmap_walk_ksm()
3411 			 * Allocate stable and unstable together:  in merge_across_nodes_store()
3422 				/* Stable tree is empty but not the unstable */  in merge_across_nodes_store()