linux-5.10/mm/ksm.c

64  * Therefore KSM uses two data structures - the stable and the unstable tree.
87  * unstable tree: this tree holds pointers to pages which have been found to
88  * be "unchanged for a period of time".  The unstable tree sorts these pages
90  * upon the unstable tree to work correctly - the unstable tree is liable to
91  * be corrupted as its contents are modified, and so it is called unstable.
95  * 1) The unstable tree is flushed every time KSM completes scanning all
97  * 2) KSM will only insert into the unstable tree, pages whose hash value
99  * 3) The unstable tree is a RedBlack Tree - so its balancing is based on the
105  *    take 10 attempts to find a page in the unstable tree, once it is found,
107  *    compare it against the stable tree, and then against the unstable tree.)
110  * stable trees and multiple unstable trees: one of each for each NUMA node.
132  * @seqnr: count of completed full scans (needed when removing unstable node)
187  * @nid: NUMA node id of unstable tree in which linked (may not match page)
191  * @node: rb node of this rmap_item in the unstable tree
200 		int nid;		/* when node of unstable tree */
205 	unsigned int oldchecksum;	/* when unstable */
207 		struct rb_node node;	/* when node of unstable tree */
215 #define SEQNR_MASK	0x0ff	/* low bits of unstable tree seqnr */
216 #define UNSTABLE_FLAG	0x100	/* is a node of the unstable tree */
221 /* The stable and unstable tree heads */
251 /* The number of nodes in the unstable tree */
583  * stable and unstable pages from all nodes with roots in index 0. Otherwise,
584  * every node has its own stable and unstable tree.
771  * Removing rmap_item from stable or unstable tree.
772  * This function will clean the information from the stable/unstable tree.
1293 	/* Unstable nid is in union with stable anon_vma: remove first */  in try_to_merge_with_ksm_page()
1662 				 * in the unstable tree to create a  in stable_tree_search()
1911  * else insert rmap_item into the unstable tree.
1913  * This function searches for a page in the unstable tree identical to the
1915  * tree, we insert rmap_item as a new object into the unstable tree.
1969 			 * it will be flushed out and put in the right unstable  in unstable_tree_search_insert()
2030  * be inserted into the unstable tree, or merged with a page already there and
2098 	 * don't want to insert it in the unstable tree, and we don't want  in cmp_and_merge_page()
2636 			/* Ignore the stable/unstable/sqnr flags */  in rmap_walk_ksm()
2959 			 * Allocate stable and unstable together:  in merge_across_nodes_store()
2970 				/* Stable tree is empty but not the unstable */  in merge_across_nodes_store()