412 static inline void free_stable_node(struct ksm_stable_node *stable_node)  in free_stable_node()  argument
414 	VM_BUG_ON(stable_node->rmap_hlist_len &&  in free_stable_node()
415 		  !is_stable_node_chain(stable_node));  in free_stable_node()
416 	kmem_cache_free(stable_node_cache, stable_node);  in free_stable_node()
668 static void remove_node_from_stable_tree(struct ksm_stable_node *stable_node)  in remove_node_from_stable_tree()  argument
673 	BUG_ON(stable_node->rmap_hlist_len < 0);  in remove_node_from_stable_tree()
675 	hlist_for_each_entry(rmap_item, &stable_node->hlist, hlist) {  in remove_node_from_stable_tree()
678 			trace_ksm_remove_rmap_item(stable_node->kpfn, rmap_item, rmap_item->mm);  in remove_node_from_stable_tree()
685 		VM_BUG_ON(stable_node->rmap_hlist_len <= 0);  in remove_node_from_stable_tree()
686 		stable_node->rmap_hlist_len--;  in remove_node_from_stable_tree()
702 	trace_ksm_remove_ksm_page(stable_node->kpfn);  in remove_node_from_stable_tree()
703 	if (stable_node->head == &migrate_nodes)  in remove_node_from_stable_tree()
704 		list_del(&stable_node->list);  in remove_node_from_stable_tree()
706 		stable_node_dup_del(stable_node);  in remove_node_from_stable_tree()
707 	free_stable_node(stable_node);  in remove_node_from_stable_tree()
735 static struct page *get_ksm_page(struct ksm_stable_node *stable_node,  in get_ksm_page()  argument
742 	expected_mapping = (void *)((unsigned long)stable_node |  in get_ksm_page()
745 	kpfn = READ_ONCE(stable_node->kpfn); /* Address dependency. */  in get_ksm_page()
804 	if (READ_ONCE(stable_node->kpfn) != kpfn)  in get_ksm_page()
806 	remove_node_from_stable_tree(stable_node);  in get_ksm_page()
817 		struct ksm_stable_node *stable_node;  in remove_rmap_item_from_tree()  local
820 		stable_node = rmap_item->head;  in remove_rmap_item_from_tree()
821 		page = get_ksm_page(stable_node, GET_KSM_PAGE_LOCK);  in remove_rmap_item_from_tree()
829 		if (!hlist_empty(&stable_node->hlist))  in remove_rmap_item_from_tree()
836 		VM_BUG_ON(stable_node->rmap_hlist_len <= 0);  in remove_rmap_item_from_tree()
837 		stable_node->rmap_hlist_len--;  in remove_rmap_item_from_tree()
915 					struct ksm_stable_node *stable_node)  in set_page_stable_node()  argument
918 	page->mapping = (void *)((unsigned long)stable_node | PAGE_MAPPING_KSM);  in set_page_stable_node()
925 static int remove_stable_node(struct ksm_stable_node *stable_node)  in remove_stable_node()  argument
930 	page = get_ksm_page(stable_node, GET_KSM_PAGE_LOCK);  in remove_stable_node()
954 		remove_node_from_stable_tree(stable_node);  in remove_stable_node()
963 static int remove_stable_node_chain(struct ksm_stable_node *stable_node,  in remove_stable_node_chain()  argument
969 	if (!is_stable_node_chain(stable_node)) {  in remove_stable_node_chain()
970 		VM_BUG_ON(is_stable_node_dup(stable_node));  in remove_stable_node_chain()
971 		if (remove_stable_node(stable_node))  in remove_stable_node_chain()
978 				  &stable_node->hlist, hlist_dup) {  in remove_stable_node_chain()
983 	BUG_ON(!hlist_empty(&stable_node->hlist));  in remove_stable_node_chain()
984 	free_stable_node_chain(stable_node, root);  in remove_stable_node_chain()
990 	struct ksm_stable_node *stable_node, *next;  in remove_all_stable_nodes()  local
996 			stable_node = rb_entry(root_stable_tree[nid].rb_node,  in remove_all_stable_nodes()
998 			if (remove_stable_node_chain(stable_node,  in remove_all_stable_nodes()
1006 	list_for_each_entry_safe(stable_node, next, &migrate_nodes, list) {  in remove_all_stable_nodes()
1007 		if (remove_stable_node(stable_node))  in remove_all_stable_nodes()
1415 bool __is_page_sharing_candidate(struct ksm_stable_node *stable_node, int offset)  in __is_page_sharing_candidate()  argument
1417 	VM_BUG_ON(stable_node->rmap_hlist_len < 0);  in __is_page_sharing_candidate()
1424 	return stable_node->rmap_hlist_len &&  in __is_page_sharing_candidate()
1425 		stable_node->rmap_hlist_len + offset < ksm_max_page_sharing;  in __is_page_sharing_candidate()
1429 bool is_page_sharing_candidate(struct ksm_stable_node *stable_node)  in is_page_sharing_candidate()  argument
1431 	return __is_page_sharing_candidate(stable_node, 0);  in is_page_sharing_candidate()
1439 	struct ksm_stable_node *dup, *found = NULL, *stable_node = *_stable_node;  in stable_node_dup()  local
1446 	    time_before(jiffies, stable_node->chain_prune_time +  in stable_node_dup()
1451 		stable_node->chain_prune_time = jiffies;  in stable_node_dup()
1454 				  &stable_node->hlist, hlist_dup) {  in stable_node_dup()
1502 			BUG_ON(stable_node->hlist.first->next);  in stable_node_dup()
1508 			rb_replace_node(&stable_node->node, &found->node,  in stable_node_dup()
1510 			free_stable_node(stable_node);  in stable_node_dup()
1525 			stable_node = NULL;  in stable_node_dup()
1526 		} else if (stable_node->hlist.first != &found->hlist_dup &&  in stable_node_dup()
1545 				       &stable_node->hlist);  in stable_node_dup()
1553 static struct ksm_stable_node *stable_node_dup_any(struct ksm_stable_node *stable_node,  in stable_node_dup_any()  argument
1556 	if (!is_stable_node_chain(stable_node))  in stable_node_dup_any()
1557 		return stable_node;  in stable_node_dup_any()
1558 	if (hlist_empty(&stable_node->hlist)) {  in stable_node_dup_any()
1559 		free_stable_node_chain(stable_node, root);  in stable_node_dup_any()
1562 	return hlist_entry(stable_node->hlist.first,  in stable_node_dup_any()
1563 			   typeof(*stable_node), hlist_dup);  in stable_node_dup_any()
1585 	struct ksm_stable_node *stable_node = *_stable_node;  in __stable_node_chain()  local
1586 	if (!is_stable_node_chain(stable_node)) {  in __stable_node_chain()
1587 		if (is_page_sharing_candidate(stable_node)) {  in __stable_node_chain()
1588 			*_stable_node_dup = stable_node;  in __stable_node_chain()
1589 			return get_ksm_page(stable_node, GET_KSM_PAGE_NOLOCK);  in __stable_node_chain()
1637 	struct ksm_stable_node *stable_node, *stable_node_dup, *stable_node_any;  in stable_tree_search()  local
1658 		stable_node = rb_entry(*new, struct ksm_stable_node, node);  in stable_tree_search()
1660 		tree_page = chain_prune(&stable_node_dup, &stable_node,	root);  in stable_tree_search()
1679 			stable_node_any = stable_node_dup_any(stable_node,  in stable_tree_search()
1801 	if (stable_node_dup == stable_node) {  in stable_tree_search()
1821 		VM_BUG_ON(!is_stable_node_chain(stable_node));  in stable_tree_search()
1827 			stable_node_chain_add_dup(page_node, stable_node);  in stable_tree_search()
1852 	if (stable_node_dup == stable_node) {  in stable_tree_search()
1855 		stable_node = alloc_stable_node_chain(stable_node_dup,  in stable_tree_search()
1857 		if (!stable_node)  in stable_tree_search()
1870 	stable_node_chain_add_dup(page_node, stable_node);  in stable_tree_search()
1888 	struct ksm_stable_node *stable_node, *stable_node_dup, *stable_node_any;  in stable_tree_insert()  local
1903 		stable_node = rb_entry(*new, struct ksm_stable_node, node);  in stable_tree_insert()
1905 		tree_page = chain(&stable_node_dup, stable_node, root);  in stable_tree_insert()
1912 			stable_node_any = stable_node_dup_any(stable_node,  in stable_tree_insert()
1971 		if (!is_stable_node_chain(stable_node)) {  in stable_tree_insert()
1972 			struct ksm_stable_node *orig = stable_node;  in stable_tree_insert()
1974 			stable_node = alloc_stable_node_chain(orig, root);  in stable_tree_insert()
1975 			if (!stable_node) {  in stable_tree_insert()
1980 		stable_node_chain_add_dup(stable_node_dup, stable_node);  in stable_tree_insert()
2073 			       struct ksm_stable_node *stable_node,  in stable_tree_append()  argument
2086 	BUG_ON(stable_node->rmap_hlist_len < 0);  in stable_tree_append()
2088 	stable_node->rmap_hlist_len++;  in stable_tree_append()
2091 		WARN_ON_ONCE(stable_node->rmap_hlist_len >  in stable_tree_append()
2094 	rmap_item->head = stable_node;  in stable_tree_append()
2096 	hlist_add_head(&rmap_item->hlist, &stable_node->hlist);  in stable_tree_append()
2120 	struct ksm_stable_node *stable_node;  in cmp_and_merge_page()  local
2126 	stable_node = page_stable_node(page);  in cmp_and_merge_page()
2127 	if (stable_node) {  in cmp_and_merge_page()
2128 		if (stable_node->head != &migrate_nodes &&  in cmp_and_merge_page()
2129 		    get_kpfn_nid(READ_ONCE(stable_node->kpfn)) !=  in cmp_and_merge_page()
2130 		    NUMA(stable_node->nid)) {  in cmp_and_merge_page()
2131 			stable_node_dup_del(stable_node);  in cmp_and_merge_page()
2132 			stable_node->head = &migrate_nodes;  in cmp_and_merge_page()
2133 			list_add(&stable_node->list, stable_node->head);  in cmp_and_merge_page()
2135 		if (stable_node->head != &migrate_nodes &&  in cmp_and_merge_page()
2136 		    rmap_item->head == stable_node)  in cmp_and_merge_page()
2142 		if (!is_page_sharing_candidate(stable_node))  in cmp_and_merge_page()
2148 	if (kpage == page && rmap_item->head == stable_node) {  in cmp_and_merge_page()
2242 			stable_node = stable_tree_insert(kpage);  in cmp_and_merge_page()
2243 			if (stable_node) {  in cmp_and_merge_page()
2244 				stable_tree_append(tree_rmap_item, stable_node,  in cmp_and_merge_page()
2246 				stable_tree_append(rmap_item, stable_node,  in cmp_and_merge_page()
2257 			if (!stable_node) {  in cmp_and_merge_page()
2344 			struct ksm_stable_node *stable_node, *next;  in scan_get_next_rmap_item()  local
2347 			list_for_each_entry_safe(stable_node, next,  in scan_get_next_rmap_item()
2349 				page = get_ksm_page(stable_node,  in scan_get_next_rmap_item()
2840 	struct ksm_stable_node *stable_node;  in rmap_walk_ksm()  local
2852 	stable_node = folio_stable_node(folio);  in rmap_walk_ksm()
2853 	if (!stable_node)  in rmap_walk_ksm()
2856 	hlist_for_each_entry(rmap_item, &stable_node->hlist, hlist) {  in rmap_walk_ksm()
2915 	struct ksm_stable_node *stable_node;  in collect_procs_ksm()  local
2921 	stable_node = folio_stable_node(folio);  in collect_procs_ksm()
2922 	if (!stable_node)  in collect_procs_ksm()
2924 	hlist_for_each_entry(rmap_item, &stable_node->hlist, hlist) {  in collect_procs_ksm()
2956 	struct ksm_stable_node *stable_node;  in folio_migrate_ksm()  local
2962 	stable_node = folio_stable_node(folio);  in folio_migrate_ksm()
2963 	if (stable_node) {  in folio_migrate_ksm()
2964 		VM_BUG_ON_FOLIO(stable_node->kpfn != folio_pfn(folio), folio);  in folio_migrate_ksm()
2965 		stable_node->kpfn = folio_pfn(newfolio);  in folio_migrate_ksm()
2989 static bool stable_node_dup_remove_range(struct ksm_stable_node *stable_node,  in stable_node_dup_remove_range()  argument
2993 	if (stable_node->kpfn >= start_pfn &&  in stable_node_dup_remove_range()
2994 	    stable_node->kpfn < end_pfn) {  in stable_node_dup_remove_range()
2999 		remove_node_from_stable_tree(stable_node);  in stable_node_dup_remove_range()
3005 static bool stable_node_chain_remove_range(struct ksm_stable_node *stable_node,  in stable_node_chain_remove_range()  argument
3013 	if (!is_stable_node_chain(stable_node)) {  in stable_node_chain_remove_range()
3014 		VM_BUG_ON(is_stable_node_dup(stable_node));  in stable_node_chain_remove_range()
3015 		return stable_node_dup_remove_range(stable_node, start_pfn,  in stable_node_chain_remove_range()
3020 				  &stable_node->hlist, hlist_dup) {  in stable_node_chain_remove_range()
3024 	if (hlist_empty(&stable_node->hlist)) {  in stable_node_chain_remove_range()
3025 		free_stable_node_chain(stable_node, root);  in stable_node_chain_remove_range()
3034 	struct ksm_stable_node *stable_node, *next;  in ksm_check_stable_tree()  local
3041 			stable_node = rb_entry(node, struct ksm_stable_node, node);  in ksm_check_stable_tree()
3042 			if (stable_node_chain_remove_range(stable_node,  in ksm_check_stable_tree()
3052 	list_for_each_entry_safe(stable_node, next, &migrate_nodes, list) {  in ksm_check_stable_tree()
3053 		if (stable_node->kpfn >= start_pfn &&  in ksm_check_stable_tree()
3054 		    stable_node->kpfn < end_pfn)  in ksm_check_stable_tree()
3055 			remove_node_from_stable_tree(stable_node);  in ksm_check_stable_tree()