73  * Therefore KSM uses two data structures - the stable and the unstable tree.
75  * The stable tree holds pointers to all the merged pages (ksm pages), sorted
78  * and therefore this tree is called the stable tree.
80  * The stable tree node includes information required for reverse
84  * KSM maintains two types of nodes in the stable tree:
95  * In addition to the stable tree, KSM uses a second data structure called the
113  * 4) KSM never flushes the stable tree, which means that even if it were to
115  *    it is secured in the stable tree.  (When we scan a new page, we first
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.
149  * struct ksm_stable_node - node of the stable rbtree
150  * @node: rb node of this ksm page in the stable tree
158  * @nid: NUMA node id of stable tree in which linked (may not match kpfn)
162 		struct rb_node node;	/* when node of stable tree */
191  * @anon_vma: pointer to anon_vma for this mm,address, when in stable tree
197  * @head: pointer to stable_node heading this list in the stable tree
205 		struct anon_vma *anon_vma;	/* when stable */
217 		struct {		/* when listed from stable tree */
226 #define STABLE_FLAG	0x200	/* is listed from the stable tree */
228 /* The stable and unstable tree heads */
234 /* Recently migrated nodes of stable tree, pending proper placement */
258 /* The number of nodes in the stable tree */
279 /* Maximum number of page slots sharing a stable node */
708 	 * than we're counting as nodes in the stable tree; but ksm_do_scan  in break_ksm()
802  * stable and unstable pages from all nodes with roots in index 0. Otherwise,
803  * every node has its own stable and unstable tree.
825 		 * Put the stable node chain in the first dimension of  in alloc_stable_node_chain()
826 		 * the stable tree and at the same time remove the old  in alloc_stable_node_chain()
827 		 * stable node.  in alloc_stable_node_chain()
832 		 * Move the old stable node to the second dimension  in alloc_stable_node_chain()
900  * get_ksm_page: checks if the page indicated by the stable node
904  * remove the stale node from the stable tree and return NULL.
905  * But beware, the stable node's page might be being migrated.
911  * "keyhole reference": access to the ksm page from the stable node peeps
913  * pointing back to this stable node.  This relies on freeing a PageAnon
994  * Removing rmap_item from stable or unstable tree.
995  * This function will clean the information from the stable/unstable tree.
1058  * Though it's very tempting to unmerge rmap_items from stable tree rather
1060  * that - an rmap_item is assigned to the stable tree after inserting ksm
1129 		 * The stable node did not yet appear stale to get_ksm_page(),  in remove_stable_node()
1255 	/* Clean up stable nodes, but don't worry if some are still busy */  in unmerge_and_remove_all_rmap_items()
1488 	 * We need the page lock to read a stable PageSwapCache in  in try_to_merge_one_page()
1556 	/* Unstable nid is in union with stable anon_vma: remove first */  in try_to_merge_with_ksm_page()
1644 		 * stable nodes during lookup.  in stable_node_dup()
1707 			 * otherwise left as a stable pointer, the  in stable_node_dup()
1809  * stable_tree_search - search for page inside the stable tree
1811  * This function checks if there is a page inside the stable tree
1814  * This function returns the stable tree node of identical content if found,
1856 		 * stable rbtree and stable_node will be equal to  in stable_tree_search()
1910 				 * into a stable node dup. If the mapcount is  in stable_tree_search()
1983 	 * from the case there was no chain in the stable  in stable_tree_search()
2034 	 * from the case there was no chain in the stable  in stable_tree_search()
2061  * stable_tree_insert - insert stable tree node pointing to new ksm page
2062  * into the stable tree.
2064  * This function returns the stable tree node just allocated on success,
2255  * rmap_items hanging off a given node of the stable tree, all sharing
2293  * cmp_and_merge_page - first see if page can be merged into the stable tree;
2296  * both transferred to the stable tree.
2332 	/* We first start with searching the page inside the stable tree */  in cmp_and_merge_page()
2349 			 * add its rmap_item to the stable tree.  in cmp_and_merge_page()
2425 			 * node in the stable tree and add both rmap_items.  in cmp_and_merge_page()
2438 			 * If we fail to insert the page into the stable tree,  in cmp_and_merge_page()
2440 			 * to a ksm page left outside the stable tree,  in cmp_and_merge_page()
3111 	 * to that page's node of the stable tree.  in rmap_walk_ksm()
3139 			/* Ignore the stable/unstable/sqnr flags */  in rmap_walk_ksm()
3333 		 * it is unsafe for them to touch the stable tree at this time.  in ksm_memory_callback()
3517 			 * Allocate stable and unstable together:  in merge_across_nodes_store()
3528 				/* Stable tree is empty but not the unstable */  in merge_across_nodes_store()