155 struct stable_node {  struct
209 			struct stable_node *head;
312 	stable_node_cache = KSM_KMEM_CACHE(stable_node, 0);  in ksm_slab_init()
338 static __always_inline bool is_stable_node_chain(struct stable_node *chain)  in is_stable_node_chain()
343 static __always_inline bool is_stable_node_dup(struct stable_node *dup)  in is_stable_node_dup()
348 static inline void stable_node_chain_add_dup(struct stable_node *dup,  in stable_node_chain_add_dup()
349 					     struct stable_node *chain)  in stable_node_chain_add_dup()
358 static inline void __stable_node_dup_del(struct stable_node *dup)  in __stable_node_dup_del()
365 static inline void stable_node_dup_del(struct stable_node *dup)  in stable_node_dup_del()
395 static inline struct stable_node *alloc_stable_node(void)  in alloc_stable_node()
405 static inline void free_stable_node(struct stable_node *stable_node)  in free_stable_node()  argument
407 	VM_BUG_ON(stable_node->rmap_hlist_len &&  in free_stable_node()
408 		  !is_stable_node_chain(stable_node));  in free_stable_node()
409 	kmem_cache_free(stable_node_cache, stable_node);  in free_stable_node()
590 static struct stable_node *alloc_stable_node_chain(struct stable_node *dup,  in alloc_stable_node_chain()
593 	struct stable_node *chain = alloc_stable_node();  in alloc_stable_node_chain()
623 static inline void free_stable_node_chain(struct stable_node *chain,  in free_stable_node_chain()
631 static void remove_node_from_stable_tree(struct stable_node *stable_node)  in remove_node_from_stable_tree()  argument
636 	BUG_ON(stable_node->rmap_hlist_len < 0);  in remove_node_from_stable_tree()
638 	hlist_for_each_entry(rmap_item, &stable_node->hlist, hlist) {  in remove_node_from_stable_tree()
643 		VM_BUG_ON(stable_node->rmap_hlist_len <= 0);  in remove_node_from_stable_tree()
644 		stable_node->rmap_hlist_len--;  in remove_node_from_stable_tree()
662 	if (stable_node->head == &migrate_nodes)  in remove_node_from_stable_tree()
663 		list_del(&stable_node->list);  in remove_node_from_stable_tree()
665 		stable_node_dup_del(stable_node);  in remove_node_from_stable_tree()
666 	free_stable_node(stable_node);  in remove_node_from_stable_tree()
694 static struct page *get_ksm_page(struct stable_node *stable_node,  in get_ksm_page()  argument
701 	expected_mapping = (void *)((unsigned long)stable_node |  in get_ksm_page()
704 	kpfn = READ_ONCE(stable_node->kpfn); /* Address dependency. */  in get_ksm_page()
763 	if (READ_ONCE(stable_node->kpfn) != kpfn)  in get_ksm_page()
765 	remove_node_from_stable_tree(stable_node);  in get_ksm_page()
776 		struct stable_node *stable_node;  in remove_rmap_item_from_tree()  local
779 		stable_node = rmap_item->head;  in remove_rmap_item_from_tree()
780 		page = get_ksm_page(stable_node, GET_KSM_PAGE_LOCK);  in remove_rmap_item_from_tree()
788 		if (!hlist_empty(&stable_node->hlist))  in remove_rmap_item_from_tree()
792 		VM_BUG_ON(stable_node->rmap_hlist_len <= 0);  in remove_rmap_item_from_tree()
793 		stable_node->rmap_hlist_len--;  in remove_rmap_item_from_tree()
860 static inline struct stable_node *page_stable_node(struct page *page)  in page_stable_node()
866 					struct stable_node *stable_node)  in set_page_stable_node()  argument
868 	page->mapping = (void *)((unsigned long)stable_node | PAGE_MAPPING_KSM);  in set_page_stable_node()
875 static int remove_stable_node(struct stable_node *stable_node)  in remove_stable_node()  argument
880 	page = get_ksm_page(stable_node, GET_KSM_PAGE_LOCK);  in remove_stable_node()
904 		remove_node_from_stable_tree(stable_node);  in remove_stable_node()
913 static int remove_stable_node_chain(struct stable_node *stable_node,  in remove_stable_node_chain()  argument
916 	struct stable_node *dup;  in remove_stable_node_chain()
919 	if (!is_stable_node_chain(stable_node)) {  in remove_stable_node_chain()
920 		VM_BUG_ON(is_stable_node_dup(stable_node));  in remove_stable_node_chain()
921 		if (remove_stable_node(stable_node))  in remove_stable_node_chain()
928 				  &stable_node->hlist, hlist_dup) {  in remove_stable_node_chain()
933 	BUG_ON(!hlist_empty(&stable_node->hlist));  in remove_stable_node_chain()
934 	free_stable_node_chain(stable_node, root);  in remove_stable_node_chain()
940 	struct stable_node *stable_node, *next;  in remove_all_stable_nodes()  local
946 			stable_node = rb_entry(root_stable_tree[nid].rb_node,  in remove_all_stable_nodes()
947 						struct stable_node, node);  in remove_all_stable_nodes()
948 			if (remove_stable_node_chain(stable_node,  in remove_all_stable_nodes()
956 	list_for_each_entry_safe(stable_node, next, &migrate_nodes, list) {  in remove_all_stable_nodes()
957 		if (remove_stable_node(stable_node))  in remove_all_stable_nodes()
1335 bool __is_page_sharing_candidate(struct stable_node *stable_node, int offset)  in __is_page_sharing_candidate()  argument
1337 	VM_BUG_ON(stable_node->rmap_hlist_len < 0);  in __is_page_sharing_candidate()
1344 	return stable_node->rmap_hlist_len &&  in __is_page_sharing_candidate()
1345 		stable_node->rmap_hlist_len + offset < ksm_max_page_sharing;  in __is_page_sharing_candidate()
1349 bool is_page_sharing_candidate(struct stable_node *stable_node)  in is_page_sharing_candidate()  argument
1351 	return __is_page_sharing_candidate(stable_node, 0);  in is_page_sharing_candidate()
1354 static struct page *stable_node_dup(struct stable_node **_stable_node_dup,  in stable_node_dup()
1355 				    struct stable_node **_stable_node,  in stable_node_dup()
1359 	struct stable_node *dup, *found = NULL, *stable_node = *_stable_node;  in stable_node_dup()  local
1366 	    time_before(jiffies, stable_node->chain_prune_time +  in stable_node_dup()
1371 		stable_node->chain_prune_time = jiffies;  in stable_node_dup()
1374 				  &stable_node->hlist, hlist_dup) {  in stable_node_dup()
1422 			BUG_ON(stable_node->hlist.first->next);  in stable_node_dup()
1428 			rb_replace_node(&stable_node->node, &found->node,  in stable_node_dup()
1430 			free_stable_node(stable_node);  in stable_node_dup()
1445 			stable_node = NULL;  in stable_node_dup()
1446 		} else if (stable_node->hlist.first != &found->hlist_dup &&  in stable_node_dup()
1465 				       &stable_node->hlist);  in stable_node_dup()
1473 static struct stable_node *stable_node_dup_any(struct stable_node *stable_node,  in stable_node_dup_any()  argument
1476 	if (!is_stable_node_chain(stable_node))  in stable_node_dup_any()
1477 		return stable_node;  in stable_node_dup_any()
1478 	if (hlist_empty(&stable_node->hlist)) {  in stable_node_dup_any()
1479 		free_stable_node_chain(stable_node, root);  in stable_node_dup_any()
1482 	return hlist_entry(stable_node->hlist.first,  in stable_node_dup_any()
1483 			   typeof(*stable_node), hlist_dup);  in stable_node_dup_any()
1500 static struct page *__stable_node_chain(struct stable_node **_stable_node_dup,  in __stable_node_chain()
1501 					struct stable_node **_stable_node,  in __stable_node_chain()
1505 	struct stable_node *stable_node = *_stable_node;  in __stable_node_chain()  local
1506 	if (!is_stable_node_chain(stable_node)) {  in __stable_node_chain()
1507 		if (is_page_sharing_candidate(stable_node)) {  in __stable_node_chain()
1508 			*_stable_node_dup = stable_node;  in __stable_node_chain()
1509 			return get_ksm_page(stable_node, GET_KSM_PAGE_NOLOCK);  in __stable_node_chain()
1522 static __always_inline struct page *chain_prune(struct stable_node **s_n_d,  in chain_prune()
1523 						struct stable_node **s_n,  in chain_prune()
1529 static __always_inline struct page *chain(struct stable_node **s_n_d,  in chain()
1530 					  struct stable_node *s_n,  in chain()
1533 	struct stable_node *old_stable_node = s_n;  in chain()
1557 	struct stable_node *stable_node, *stable_node_dup, *stable_node_any;  in stable_tree_search()  local
1558 	struct stable_node *page_node;  in stable_tree_search()
1578 		stable_node = rb_entry(*new, struct stable_node, node);  in stable_tree_search()
1580 		tree_page = chain_prune(&stable_node_dup, &stable_node,	root);  in stable_tree_search()
1599 			stable_node_any = stable_node_dup_any(stable_node,  in stable_tree_search()
1721 	if (stable_node_dup == stable_node) {  in stable_tree_search()
1741 		VM_BUG_ON(!is_stable_node_chain(stable_node));  in stable_tree_search()
1747 			stable_node_chain_add_dup(page_node, stable_node);  in stable_tree_search()
1772 	if (stable_node_dup == stable_node) {  in stable_tree_search()
1776 		stable_node = alloc_stable_node_chain(stable_node_dup,  in stable_tree_search()
1778 		if (!stable_node)  in stable_tree_search()
1787 	VM_BUG_ON(!is_stable_node_chain(stable_node));  in stable_tree_search()
1792 	stable_node_chain_add_dup(page_node, stable_node);  in stable_tree_search()
1803 static struct stable_node *stable_tree_insert(struct page *kpage)  in stable_tree_insert()
1810 	struct stable_node *stable_node, *stable_node_dup, *stable_node_any;  in stable_tree_insert()  local
1825 		stable_node = rb_entry(*new, struct stable_node, node);  in stable_tree_insert()
1827 		tree_page = chain(&stable_node_dup, stable_node, root);  in stable_tree_insert()
1834 			stable_node_any = stable_node_dup_any(stable_node,  in stable_tree_insert()
1893 		if (!is_stable_node_chain(stable_node)) {  in stable_tree_insert()
1894 			struct stable_node *orig = stable_node;  in stable_tree_insert()
1896 			stable_node = alloc_stable_node_chain(orig, root);  in stable_tree_insert()
1897 			if (!stable_node) {  in stable_tree_insert()
1902 		stable_node_chain_add_dup(stable_node_dup, stable_node);  in stable_tree_insert()
1995 			       struct stable_node *stable_node,  in stable_tree_append()  argument
2008 	BUG_ON(stable_node->rmap_hlist_len < 0);  in stable_tree_append()
2010 	stable_node->rmap_hlist_len++;  in stable_tree_append()
2013 		WARN_ON_ONCE(stable_node->rmap_hlist_len >  in stable_tree_append()
2016 	rmap_item->head = stable_node;  in stable_tree_append()
2018 	hlist_add_head(&rmap_item->hlist, &stable_node->hlist);  in stable_tree_append()
2040 	struct stable_node *stable_node;  in cmp_and_merge_page()  local
2046 	stable_node = page_stable_node(page);  in cmp_and_merge_page()
2047 	if (stable_node) {  in cmp_and_merge_page()
2048 		if (stable_node->head != &migrate_nodes &&  in cmp_and_merge_page()
2049 		    get_kpfn_nid(READ_ONCE(stable_node->kpfn)) !=  in cmp_and_merge_page()
2050 		    NUMA(stable_node->nid)) {  in cmp_and_merge_page()
2051 			stable_node_dup_del(stable_node);  in cmp_and_merge_page()
2052 			stable_node->head = &migrate_nodes;  in cmp_and_merge_page()
2053 			list_add(&stable_node->list, stable_node->head);  in cmp_and_merge_page()
2055 		if (stable_node->head != &migrate_nodes &&  in cmp_and_merge_page()
2056 		    rmap_item->head == stable_node)  in cmp_and_merge_page()
2062 		if (!is_page_sharing_candidate(stable_node))  in cmp_and_merge_page()
2068 	if (kpage == page && rmap_item->head == stable_node) {  in cmp_and_merge_page()
2151 			stable_node = stable_tree_insert(kpage);  in cmp_and_merge_page()
2152 			if (stable_node) {  in cmp_and_merge_page()
2153 				stable_tree_append(tree_rmap_item, stable_node,  in cmp_and_merge_page()
2155 				stable_tree_append(rmap_item, stable_node,  in cmp_and_merge_page()
2166 			if (!stable_node) {  in cmp_and_merge_page()
2248 			struct stable_node *stable_node, *next;  in scan_get_next_rmap_item()  local
2251 			list_for_each_entry_safe(stable_node, next,  in scan_get_next_rmap_item()
2253 				page = get_ksm_page(stable_node,  in scan_get_next_rmap_item()
2592 	struct stable_node *stable_node;  in rmap_walk_ksm()  local
2604 	stable_node = page_stable_node(page);  in rmap_walk_ksm()
2605 	if (!stable_node)  in rmap_walk_ksm()
2608 	hlist_for_each_entry(rmap_item, &stable_node->hlist, hlist) {  in rmap_walk_ksm()
2682 	struct stable_node *stable_node;  in ksm_migrate_page()  local
2688 	stable_node = page_stable_node(newpage);  in ksm_migrate_page()
2689 	if (stable_node) {  in ksm_migrate_page()
2690 		VM_BUG_ON_PAGE(stable_node->kpfn != page_to_pfn(oldpage), oldpage);  in ksm_migrate_page()
2691 		stable_node->kpfn = page_to_pfn(newpage);  in ksm_migrate_page()
2715 static bool stable_node_dup_remove_range(struct stable_node *stable_node,  in stable_node_dup_remove_range()  argument
2719 	if (stable_node->kpfn >= start_pfn &&  in stable_node_dup_remove_range()
2720 	    stable_node->kpfn < end_pfn) {  in stable_node_dup_remove_range()
2725 		remove_node_from_stable_tree(stable_node);  in stable_node_dup_remove_range()
2731 static bool stable_node_chain_remove_range(struct stable_node *stable_node,  in stable_node_chain_remove_range()  argument
2736 	struct stable_node *dup;  in stable_node_chain_remove_range()
2739 	if (!is_stable_node_chain(stable_node)) {  in stable_node_chain_remove_range()
2740 		VM_BUG_ON(is_stable_node_dup(stable_node));  in stable_node_chain_remove_range()
2741 		return stable_node_dup_remove_range(stable_node, start_pfn,  in stable_node_chain_remove_range()
2746 				  &stable_node->hlist, hlist_dup) {  in stable_node_chain_remove_range()
2750 	if (hlist_empty(&stable_node->hlist)) {  in stable_node_chain_remove_range()
2751 		free_stable_node_chain(stable_node, root);  in stable_node_chain_remove_range()
2760 	struct stable_node *stable_node, *next;  in ksm_check_stable_tree()  local
2767 			stable_node = rb_entry(node, struct stable_node, node);  in ksm_check_stable_tree()
2768 			if (stable_node_chain_remove_range(stable_node,  in ksm_check_stable_tree()
2778 	list_for_each_entry_safe(stable_node, next, &migrate_nodes, list) {  in ksm_check_stable_tree()
2779 		if (stable_node->kpfn >= start_pfn &&  in ksm_check_stable_tree()
2780 		    stable_node->kpfn < end_pfn)  in ksm_check_stable_tree()
2781 			remove_node_from_stable_tree(stable_node);  in ksm_check_stable_tree()