Re: [PATCH 1/1] ksm: introduce ksm_max_page_sharing per page deduplication limit

[Petr Holasek <pholasek@redhat.com>]

On Tue, 10 Nov 2015, Andrea Arcangeli <aarcange@redhat.com> wrote:
> Without a max deduplication limit for each KSM page, the list of the
> rmap_items associated to each stable_node can grow infinitely
> large.
> 
> During the rmap walk each entry can take up to ~10usec to process
> because of IPIs for the TLB flushing (both for the primary MMU and the
> secondary MMUs with the MMU notifier). With only 16GB of address space
> shared in the same KSM page, that would amount to dozens of seconds of
> kernel runtime.
> 
> A ~256 max deduplication factor will reduce the latencies of the rmap
> walks on KSM pages to order of a few msec. Just doing the
> cond_resched() during the rmap walks is not enough, the list size must
> have a limit too, otherwise the caller could get blocked in (schedule
> friendly) kernel computations for seconds, unexpectedly.
> 
> There's room for optimization to significantly reduce the IPI delivery
> cost during the page_referenced(), but at least for page_migration in
> the KSM case (used by hard NUMA bindings, compaction and NUMA
> balancing) it may be inevitable to send lots of IPIs if each
> rmap_item->mm is active on a different CPU and there are lots of
> CPUs. Even if we ignore the IPI delivery cost, we've still to walk the
> whole KSM rmap list, so we can't allow millions or billions (ulimited)
> number of entries in the KSM stable_node rmap_item lists.
> 
> The limit is enforced efficiently by adding a second dimension to the
> stable rbtree. So there are three types of stable_nodes: the regular
> ones (identical as before, living in the first flat dimension of the
> stable rbtree), the "chains" and the "dups".
> 
> Every "chain" and all "dups" linked into a "chain" enforce the
> invariant that they represent the same write protected memory content,
> even if each "dup" will be pointed by a different KSM page copy of
> that content. This way the stable rbtree lookup computational
> complexity is unaffected if compared to an unlimited
> max_sharing_limit. It is still enforced that there cannot be KSM page
> content duplicates in the stable rbtree itself.
> 
> Adding the second dimension to the stable rbtree only after the
> max_page_sharing limit hits, provides for a zero memory footprint
> increase on 64bit archs. The memory overhead of the per-KSM page
> stable_tree and per virtual mapping rmap_item is unchanged. Only after
> the max_page_sharing limit hits, we need to allocate a stable_tree
> "chain" and rb_replace() the "regular" stable_node with the newly
> allocated stable_node "chain". After that we simply add the "regular"
> stable_node to the chain as a stable_node "dup" by linking hlist_dup
> in the stable_node_chain->hlist. This way the "regular" (flat)
> stable_node is converted to a stable_node "dup" living in the second
> dimension of the stable rbtree.
> 
> During stable rbtree lookups the stable_node "chain" is identified as
> stable_node->rmap_hlist_len == STABLE_NODE_CHAIN (aka
> is_stable_node_chain()).
> 
> When dropping stable_nodes, the stable_node "dup" is identified as
> stable_node->head == STABLE_NODE_DUP_HEAD (aka is_stable_node_dup()).
> 
> The STABLE_NODE_DUP_HEAD must be an unique valid pointer never used
> elsewhere in any stable_node->head/node to avoid a clashes with the
> stable_node->node.rb_parent_color pointer, and different from
> &migrate_nodes. So the second field of &migrate_nodes is picked and
> verified as always safe with a BUILD_BUG_ON in case the list_head
> implementation changes in the future.
> 
> The STABLE_NODE_DUP is picked as a random negative value in
> stable_node->rmap_hlist_len. rmap_hlist_len cannot become negative
> when it's a "regular" stable_node or a stable_node "dup".
> 
> The stable_node_chain->nid is irrelevant. The stable_node_chain->kpfn
> is aliased in a union with a time field used to rate limit the
> stable_node_chain->hlist prunes.
> 
> The garbage collection of the stable_node_chain happens lazily during
> stable rbtree lookups (as for all other kind of stable_nodes), or
> while disabling KSM with "echo 2 >/sys/kernel/mm/ksm/run" while
> collecting the entire stable rbtree.

Hi Andrea,

I've been running stress tests against this patchset for a couple of hours
and everything was ok. However, I've allocated ~1TB of memory and got
following lockup during disabling KSM with 'echo 2 > /sys/kernel/mm/ksm/run':

[13201.060601] INFO: task ksmd:351 blocked for more than 120 seconds.
[13201.066812]       Not tainted 4.4.0-rc4+ #5
[13201.070996] "echo 0 > /proc/sys/kernel/hung_task_timeout_secs" disables
this message.
[13201.078830] ksmd            D ffff883f65eb7dc8     0   351      2
0x00000000
[13201.085903]  ffff883f65eb7dc8 ffff887f66e26400 ffff883f65d5e400
ffff883f65eb8000
[13201.093343]  ffffffff81a65144 ffff883f65d5e400 00000000ffffffff
ffffffff81a65148
[13201.100792]  ffff883f65eb7de0 ffffffff816907e5 ffffffff81a65140
ffff883f65eb7df0
[13201.108242] Call Trace:
[13201.110708]  [<ffffffff816907e5>] schedule+0x35/0x80
[13201.115676]  [<ffffffff81690ace>] schedule_preempt_disabled+0xe/0x10
[13201.122044]  [<ffffffff81692524>] __mutex_lock_slowpath+0xb4/0x130
[13201.128237]  [<ffffffff816925bf>] mutex_lock+0x1f/0x2f
[13201.133395]  [<ffffffff811debd2>] ksm_scan_thread+0x62/0x1f0
[13201.139068]  [<ffffffff810c8ac0>] ? wait_woken+0x80/0x80
[13201.144391]  [<ffffffff811deb70>] ? ksm_do_scan+0x1140/0x1140
[13201.150164]  [<ffffffff810a4378>] kthread+0xd8/0xf0
[13201.155056]  [<ffffffff810a42a0>] ? kthread_park+0x60/0x60
[13201.160551]  [<ffffffff8169460f>] ret_from_fork+0x3f/0x70
[13201.165961]  [<ffffffff810a42a0>] ? kthread_park+0x60/0x60

It seems this is not connected with the new code, but it would be nice to
also make unmerge_and_remove_all_rmap_items() more scheduler friendly.

thanks,
Petr

> 
> While the "regular" stable_nodes and the stable_node "dups" must wait
> for their underlying tree_page to be freed before they can be freed
> themselves, the stable_node "chains" can be freed immediately if the
> stable_node->hlist turns empty. This is because the "chains" are never
> pointed by any page->mapping and they're effectively stable rbtree KSM
> self contained metadata.
> 
> Signed-off-by: Andrea Arcangeli <aarcange@redhat.com>
> ---
>  Documentation/vm/ksm.txt |  63 ++++
>  mm/ksm.c                 | 731 ++++++++++++++++++++++++++++++++++++++++++-----
>  2 files changed, 728 insertions(+), 66 deletions(-)
> 
> diff --git a/Documentation/vm/ksm.txt b/Documentation/vm/ksm.txt
> index f34a8ee..a7ef759 100644
> --- a/Documentation/vm/ksm.txt
> +++ b/Documentation/vm/ksm.txt
> @@ -80,6 +80,50 @@ run              - set 0 to stop ksmd from running but keep merged pages,
>                     Default: 0 (must be changed to 1 to activate KSM,
>                                 except if CONFIG_SYSFS is disabled)
>  
> +max_page_sharing - Maximum sharing allowed for each KSM page. This
> +                   enforces a deduplication limit to avoid the virtual
> +                   memory rmap lists to grow too large. The minimum
> +                   value is 2 as a newly created KSM page will have at
> +                   least two sharers. The rmap walk has O(N)
> +                   complexity where N is the number of rmap_items
> +                   (i.e. virtual mappings) that are sharing the page,
> +                   which is in turn capped by max_page_sharing. So
> +                   this effectively spread the the linear O(N)
> +                   computational complexity from rmap walk context
> +                   over different KSM pages. The ksmd walk over the
> +                   stable_node "chains" is also O(N), but N is the
> +                   number of stable_node "dups", not the number of
> +                   rmap_items, so it has not a significant impact on
> +                   ksmd performance. In practice the best stable_node
> +                   "dup" candidate will be kept and found at the head
> +                   of the "dups" list. The higher this value the
> +                   faster KSM will merge the memory (because there
> +                   will be fewer stable_node dups queued into the
> +                   stable_node chain->hlist to check for pruning) and
> +                   the higher the deduplication factor will be, but
> +                   the slowest the worst case rmap walk could be for
> +                   any given KSM page. Slowing down the rmap_walk
> +                   means there will be higher latency for certain
> +                   virtual memory operations happening during
> +                   swapping, compaction, NUMA balancing and page
> +                   migration, in turn decreasing responsiveness for
> +                   the caller of those virtual memory operations. The
> +                   scheduler latency of other tasks not involved with
> +                   the VM operations doing the rmap walk is not
> +                   affected by this parameter as the rmap walks are
> +                   always schedule friendly themselves.
> +
> +stable_node_chains_prune_millisecs - How frequently to walk the whole
> +                   list of stable_node "dups" linked in the
> +                   stable_node "chains" in order to prune stale
> +                   stable_nodes. Smaller milllisecs values will free
> +                   up the KSM metadata with lower latency, but they
> +                   will make ksmd use more CPU during the scan. This
> +                   only applies to the stable_node chains so it's a
> +                   noop if not a single KSM page hit the
> +                   max_page_sharing yet (there would be no stable_node
> +                   chains in such case).
> +
>  The effectiveness of KSM and MADV_MERGEABLE is shown in /sys/kernel/mm/ksm/:
>  
>  pages_shared     - how many shared pages are being used
> @@ -88,10 +132,29 @@ pages_unshared   - how many pages unique but repeatedly checked for merging
>  pages_volatile   - how many pages changing too fast to be placed in a tree
>  full_scans       - how many times all mergeable areas have been scanned
>  
> +stable_node_chains - number of stable node chains allocated, this is
> +		     effectively the number of KSM pages that hit the
> +		     max_page_sharing limit
> +stable_node_dups   - number of stable node dups queued into the
> +		     stable_node chains
> +
>  A high ratio of pages_sharing to pages_shared indicates good sharing, but
>  a high ratio of pages_unshared to pages_sharing indicates wasted effort.
>  pages_volatile embraces several different kinds of activity, but a high
>  proportion there would also indicate poor use of madvise MADV_MERGEABLE.
>  
> +The maximum possible page_sharing/page_shared ratio is limited by the
> +max_page_sharing tunable. To increase the ratio max_page_sharing must
> +be increased accordingly.
> +
> +The stable_node_dups/stable_node_chains ratio is also affected by the
> +max_page_sharing tunable, and an high ratio may indicate fragmentation
> +in the stable_node dups, which could be solved by introducing
> +fragmentation algorithms in ksmd which would refile rmap_items from
> +one stable_node dup to another stable_node dup, in order to freeup
> +stable_node "dups" with few rmap_items in them, but that may increase
> +the ksmd CPU usage and possibly slowdown the readonly computations on
> +the KSM pages of the applications.
> +
>  Izik Eidus,
>  Hugh Dickins, 17 Nov 2009
> diff --git a/mm/ksm.c b/mm/ksm.c
> index b5cd647..fd0bf51 100644
> --- a/mm/ksm.c
> +++ b/mm/ksm.c
> @@ -126,9 +126,12 @@ struct ksm_scan {
>   * struct stable_node - node of the stable rbtree
>   * @node: rb node of this ksm page in the stable tree
>   * @head: (overlaying parent) &migrate_nodes indicates temporarily on that list
> + * @hlist_dup: linked into the stable_node->hlist with a stable_node chain
>   * @list: linked into migrate_nodes, pending placement in the proper node tree
>   * @hlist: hlist head of rmap_items using this ksm page
>   * @kpfn: page frame number of this ksm page (perhaps temporarily on wrong nid)
> + * @chain_prune_time: time of the last full garbage collection
> + * @rmap_hlist_len: number of rmap_item entries in hlist or STABLE_NODE_CHAIN
>   * @nid: NUMA node id of stable tree in which linked (may not match kpfn)
>   */
>  struct stable_node {
> @@ -136,11 +139,24 @@ struct stable_node {
>  		struct rb_node node;	/* when node of stable tree */
>  		struct {		/* when listed for migration */
>  			struct list_head *head;
> -			struct list_head list;
> +			struct {
> +				struct hlist_node hlist_dup;
> +				struct list_head list;
> +			};
>  		};
>  	};
>  	struct hlist_head hlist;
> -	unsigned long kpfn;
> +	union {
> +		unsigned long kpfn;
> +		unsigned long chain_prune_time;
> +	};
> +	/*
> +	 * STABLE_NODE_CHAIN can be any negative number in
> +	 * rmap_hlist_len negative range, but better not -1 to be able
> +	 * to reliably detect underflows.
> +	 */
> +#define STABLE_NODE_CHAIN -1024
> +	int rmap_hlist_len;
>  #ifdef CONFIG_NUMA
>  	int nid;
>  #endif
> @@ -190,6 +206,7 @@ static struct rb_root *root_unstable_tree = one_unstable_tree;
>  
>  /* Recently migrated nodes of stable tree, pending proper placement */
>  static LIST_HEAD(migrate_nodes);
> +#define STABLE_NODE_DUP_HEAD ((struct list_head *)&migrate_nodes.prev)
>  
>  #define MM_SLOTS_HASH_BITS 10
>  static DEFINE_HASHTABLE(mm_slots_hash, MM_SLOTS_HASH_BITS);
> @@ -217,6 +234,18 @@ static unsigned long ksm_pages_unshared;
>  /* The number of rmap_items in use: to calculate pages_volatile */
>  static unsigned long ksm_rmap_items;
>  
> +/* The number of stable_node chains */
> +static unsigned long ksm_stable_node_chains;
> +
> +/* The number of stable_node dups linked to the stable_node chains */
> +static unsigned long ksm_stable_node_dups;
> +
> +/* Delay in pruning stale stable_node_dups in the stable_node_chains */
> +static int ksm_stable_node_chains_prune_millisecs = 2000;
> +
> +/* Maximum number of page slots sharing a stable node */
> +static int ksm_max_page_sharing = 256;
> +
>  /* Number of pages ksmd should scan in one batch */
>  static unsigned int ksm_thread_pages_to_scan = 100;
>  
> @@ -279,6 +308,44 @@ static void __init ksm_slab_free(void)
>  	mm_slot_cache = NULL;
>  }
>  
> +static __always_inline bool is_stable_node_chain(struct stable_node *chain)
> +{
> +	return chain->rmap_hlist_len == STABLE_NODE_CHAIN;
> +}
> +
> +static __always_inline bool is_stable_node_dup(struct stable_node *dup)
> +{
> +	return dup->head == STABLE_NODE_DUP_HEAD;
> +}
> +
> +static inline void stable_node_chain_add_dup(struct stable_node *dup,
> +					     struct stable_node *chain)
> +{
> +	VM_BUG_ON(is_stable_node_dup(dup));
> +	dup->head = STABLE_NODE_DUP_HEAD;
> +	VM_BUG_ON(!is_stable_node_chain(chain));
> +	hlist_add_head(&dup->hlist_dup, &chain->hlist);
> +	ksm_stable_node_dups++;
> +}
> +
> +static inline void __stable_node_dup_del(struct stable_node *dup)
> +{
> +	hlist_del(&dup->hlist_dup);
> +	ksm_stable_node_dups--;
> +}
> +
> +static inline void stable_node_dup_del(struct stable_node *dup)
> +{
> +	VM_BUG_ON(is_stable_node_chain(dup));
> +	if (is_stable_node_dup(dup))
> +		__stable_node_dup_del(dup);
> +	else
> +		rb_erase(&dup->node, root_stable_tree + NUMA(dup->nid));
> +#ifdef CONFIG_DEBUG_VM
> +	dup->head = NULL;
> +#endif
> +}
> +
>  static inline struct rmap_item *alloc_rmap_item(void)
>  {
>  	struct rmap_item *rmap_item;
> @@ -303,6 +370,8 @@ static inline struct stable_node *alloc_stable_node(void)
>  
>  static inline void free_stable_node(struct stable_node *stable_node)
>  {
> +	VM_BUG_ON(stable_node->rmap_hlist_len &&
> +		  !is_stable_node_chain(stable_node));
>  	kmem_cache_free(stable_node_cache, stable_node);
>  }
>  
> @@ -493,25 +562,80 @@ static inline int get_kpfn_nid(unsigned long kpfn)
>  	return ksm_merge_across_nodes ? 0 : NUMA(pfn_to_nid(kpfn));
>  }
>  
> +static struct stable_node *alloc_stable_node_chain(struct stable_node *dup,
> +						   struct rb_root *root)
> +{
> +	struct stable_node *chain = alloc_stable_node();
> +	VM_BUG_ON(is_stable_node_chain(dup));
> +	if (likely(chain)) {
> +		INIT_HLIST_HEAD(&chain->hlist);
> +		chain->chain_prune_time = jiffies;
> +		chain->rmap_hlist_len = STABLE_NODE_CHAIN;
> +#ifdef CONFIG_DEBUG_VM
> +		chain->nid = -1; /* debug */
> +#endif
> +		ksm_stable_node_chains++;
> +
> +		/*
> +		 * Put the stable node chain in the first dimension of
> +		 * the stable tree and at the same time remove the old
> +		 * stable node.
> +		 */
> +		rb_replace_node(&dup->node, &chain->node, root);
> +
> +		/*
> +		 * Move the old stable node to the second dimension
> +		 * queued in the hlist_dup. The invariant is that all
> +		 * dup stable_nodes in the chain->hlist point to pages
> +		 * that are wrprotected and have the exact same
> +		 * content.
> +		 */
> +		stable_node_chain_add_dup(dup, chain);
> +	}
> +	return chain;
> +}
> +
> +static inline void free_stable_node_chain(struct stable_node *chain,
> +					  struct rb_root *root)
> +{
> +	rb_erase(&chain->node, root);
> +	free_stable_node(chain);
> +	ksm_stable_node_chains--;
> +}
> +
>  static void remove_node_from_stable_tree(struct stable_node *stable_node)
>  {
>  	struct rmap_item *rmap_item;
>  
> +	/* check it's not STABLE_NODE_CHAIN or negative */
> +	BUG_ON(stable_node->rmap_hlist_len < 0);
> +
>  	hlist_for_each_entry(rmap_item, &stable_node->hlist, hlist) {
>  		if (rmap_item->hlist.next)
>  			ksm_pages_sharing--;
>  		else
>  			ksm_pages_shared--;
> +		VM_BUG_ON(stable_node->rmap_hlist_len <= 0);
> +		stable_node->rmap_hlist_len--;
>  		put_anon_vma(rmap_item->anon_vma);
>  		rmap_item->address &= PAGE_MASK;
>  		cond_resched();
>  	}
>  
> +	/*
> +	 * We need the second aligned pointer of the migrate_nodes
> +	 * list_head to stay clear from the rb_parent_color union
> +	 * (aligned and different than any node) and also different
> +	 * from &migrate_nodes. This will verify that future list.h changes
> +	 * don't break STABLE_NODE_DUP_HEAD.
> +	 */
> +	BUILD_BUG_ON(STABLE_NODE_DUP_HEAD <= &migrate_nodes);
> +	BUILD_BUG_ON(STABLE_NODE_DUP_HEAD >= &migrate_nodes + 1);
> +
>  	if (stable_node->head == &migrate_nodes)
>  		list_del(&stable_node->list);
>  	else
> -		rb_erase(&stable_node->node,
> -			 root_stable_tree + NUMA(stable_node->nid));
> +		stable_node_dup_del(stable_node);
>  	free_stable_node(stable_node);
>  }
>  
> @@ -630,6 +754,8 @@ static void remove_rmap_item_from_tree(struct rmap_item *rmap_item)
>  			ksm_pages_sharing--;
>  		else
>  			ksm_pages_shared--;
> +		VM_BUG_ON(stable_node->rmap_hlist_len <= 0);
> +		stable_node->rmap_hlist_len--;
>  
>  		put_anon_vma(rmap_item->anon_vma);
>  		rmap_item->address &= PAGE_MASK;
> @@ -738,6 +864,31 @@ static int remove_stable_node(struct stable_node *stable_node)
>  	return err;
>  }
>  
> +static int remove_stable_node_chain(struct stable_node *stable_node,
> +				    struct rb_root *root)
> +{
> +	struct stable_node *dup;
> +	struct hlist_node *hlist_safe;
> +
> +	if (!is_stable_node_chain(stable_node)) {
> +		VM_BUG_ON(is_stable_node_dup(stable_node));
> +		if (remove_stable_node(stable_node))
> +			return true;
> +		else
> +			return false;
> +	}
> +
> +	hlist_for_each_entry_safe(dup, hlist_safe,
> +				  &stable_node->hlist, hlist_dup) {
> +		VM_BUG_ON(!is_stable_node_dup(dup));
> +		if (remove_stable_node(dup))
> +			return true;
> +	}
> +	BUG_ON(!hlist_empty(&stable_node->hlist));
> +	free_stable_node_chain(stable_node, root);
> +	return false;
> +}
> +
>  static int remove_all_stable_nodes(void)
>  {
>  	struct stable_node *stable_node;
> @@ -749,7 +900,8 @@ static int remove_all_stable_nodes(void)
>  		while (root_stable_tree[nid].rb_node) {
>  			stable_node = rb_entry(root_stable_tree[nid].rb_node,
>  						struct stable_node, node);
> -			if (remove_stable_node(stable_node)) {
> +			if (remove_stable_node_chain(stable_node,
> +						     root_stable_tree + nid)) {
>  				err = -EBUSY;
>  				break;	/* proceed to next nid */
>  			}
> @@ -1136,6 +1288,163 @@ static struct page *try_to_merge_two_pages(struct rmap_item *rmap_item,
>  	return err ? NULL : page;
>  }
>  
> +static __always_inline
> +bool __is_page_sharing_candidate(struct stable_node *stable_node, int offset)
> +{
> +	VM_BUG_ON(stable_node->rmap_hlist_len < 0);
> +	/*
> +	 * Check that at least one mapping still exists, otherwise
> +	 * there's no much point to merge and share with this
> +	 * stable_node, as the underlying tree_page of the other
> +	 * sharer is going to be freed soon.
> +	 */
> +	return stable_node->rmap_hlist_len &&
> +		stable_node->rmap_hlist_len + offset < ksm_max_page_sharing;
> +}
> +
> +static __always_inline
> +bool is_page_sharing_candidate(struct stable_node *stable_node)
> +{
> +	return __is_page_sharing_candidate(stable_node, 0);
> +}
> +
> +static struct stable_node *stable_node_dup(struct stable_node *stable_node,
> +					   struct page **tree_page,
> +					   struct rb_root *root,
> +					   bool prune_stale_stable_nodes)
> +{
> +	struct stable_node *dup, *found = NULL;
> +	struct hlist_node *hlist_safe;
> +	struct page *_tree_page;
> +	int nr = 0;
> +	int found_rmap_hlist_len;
> +
> +	if (!prune_stale_stable_nodes ||
> +	    time_before(jiffies, stable_node->chain_prune_time +
> +			msecs_to_jiffies(
> +				ksm_stable_node_chains_prune_millisecs)))
> +		prune_stale_stable_nodes = false;
> +	else
> +		stable_node->chain_prune_time = jiffies;
> +
> +	hlist_for_each_entry_safe(dup, hlist_safe,
> +				  &stable_node->hlist, hlist_dup) {
> +		cond_resched();
> +		/*
> +		 * We must walk all stable_node_dup to prune the stale
> +		 * stable nodes during lookup.
> +		 *
> +		 * get_ksm_page can drop the nodes from the
> +		 * stable_node->hlist if they point to freed pages
> +		 * (that's why we do a _safe walk). The "dup"
> +		 * stable_node parameter itself will be freed from
> +		 * under us if it returns NULL.
> +		 */
> +		_tree_page = get_ksm_page(dup, false);
> +		if (!_tree_page)
> +			continue;
> +		nr += 1;
> +		if (is_page_sharing_candidate(dup)) {
> +			if (!found ||
> +			    dup->rmap_hlist_len > found_rmap_hlist_len) {
> +				if (found)
> +					put_page(*tree_page);
> +				found = dup;
> +				found_rmap_hlist_len = found->rmap_hlist_len;
> +				*tree_page = _tree_page;
> +
> +				if (!prune_stale_stable_nodes)
> +					break;
> +				/* skip put_page */
> +				continue;
> +			}
> +		}
> +		put_page(_tree_page);
> +	}
> +
> +	/*
> +	 * nr is relevant only if prune_stale_stable_nodes is true,
> +	 * otherwise we may break the loop at nr == 1 even if there
> +	 * are multiple entries.
> +	 */
> +	if (prune_stale_stable_nodes && found) {
> +		if (nr == 1) {
> +			/*
> +			 * If there's not just one entry it would
> +			 * corrupt memory, better BUG_ON. In KSM
> +			 * context with no lock held it's not even
> +			 * fatal.
> +			 */
> +			BUG_ON(stable_node->hlist.first->next);
> +
> +			/*
> +			 * There's just one entry and it is below the
> +			 * deduplication limit so drop the chain.
> +			 */
> +			rb_replace_node(&stable_node->node, &found->node,
> +					root);
> +			free_stable_node(stable_node);
> +			ksm_stable_node_chains--;
> +			ksm_stable_node_dups--;
> +		} else if (__is_page_sharing_candidate(found, 1)) {
> +			/*
> +			 * Refile our candidate at the head
> +			 * after the prune if our candidate
> +			 * can accept one more future sharing
> +			 * in addition to the one underway.
> +			 */
> +			hlist_del(&found->hlist_dup);
> +			hlist_add_head(&found->hlist_dup,
> +				       &stable_node->hlist);
> +		}
> +	}
> +
> +	return found;
> +}
> +
> +static struct stable_node *stable_node_dup_any(struct stable_node *stable_node,
> +					       struct rb_root *root)
> +{
> +	if (!is_stable_node_chain(stable_node))
> +		return stable_node;
> +	if (hlist_empty(&stable_node->hlist)) {
> +		free_stable_node_chain(stable_node, root);
> +		return NULL;
> +	}
> +	return hlist_entry(stable_node->hlist.first,
> +			   typeof(*stable_node), hlist_dup);
> +}
> +
> +static struct stable_node *__stable_node_chain(struct stable_node *stable_node,
> +					       struct page **tree_page,
> +					       struct rb_root *root,
> +					       bool prune_stale_stable_nodes)
> +{
> +	if (!is_stable_node_chain(stable_node)) {
> +		if (is_page_sharing_candidate(stable_node)) {
> +			*tree_page = get_ksm_page(stable_node, false);
> +			return stable_node;
> +		}
> +		return NULL;
> +	}
> +	return stable_node_dup(stable_node, tree_page, root,
> +			       prune_stale_stable_nodes);
> +}
> +
> +static __always_inline struct stable_node *chain_prune(struct stable_node *s_n,
> +						       struct page **t_p,
> +						       struct rb_root *root)
> +{
> +	return __stable_node_chain(s_n, t_p, root, true);
> +}
> +
> +static __always_inline struct stable_node *chain(struct stable_node *s_n,
> +						 struct page **t_p,
> +						 struct rb_root *root)
> +{
> +	return __stable_node_chain(s_n, t_p, root, false);
> +}
> +
>  /*
>   * stable_tree_search - search for page inside the stable tree
>   *
> @@ -1151,7 +1460,7 @@ static struct page *stable_tree_search(struct page *page)
>  	struct rb_root *root;
>  	struct rb_node **new;
>  	struct rb_node *parent;
> -	struct stable_node *stable_node;
> +	struct stable_node *stable_node, *stable_node_dup, *stable_node_any;
>  	struct stable_node *page_node;
>  
>  	page_node = page_stable_node(page);
> @@ -1173,7 +1482,32 @@ again:
>  
>  		cond_resched();
>  		stable_node = rb_entry(*new, struct stable_node, node);
> -		tree_page = get_ksm_page(stable_node, false);
> +		stable_node_any = NULL;
> +		stable_node_dup = chain_prune(stable_node, &tree_page, root);
> +		if (!stable_node_dup) {
> +			/*
> +			 * Either all stable_node dups were full in
> +			 * this stable_node chain, or this chain was
> +			 * empty and should be rb_erased.
> +			 */
> +			stable_node_any = stable_node_dup_any(stable_node,
> +							      root);
> +			if (!stable_node_any) {
> +				/* rb_erase just run */
> +				goto again;
> +			}
> +			/*
> +			 * Take any of the stable_node dups page of
> +			 * this stable_node chain to let the tree walk
> +			 * continue. All KSM pages belonging to the
> +			 * stable_node dups in a stable_node chain
> +			 * have the same content and they're
> +			 * wrprotected at all times. Any will work
> +			 * fine to continue the walk.
> +			 */
> +			tree_page = get_ksm_page(stable_node_any, false);
> +		}
> +		VM_BUG_ON(!stable_node_dup ^ !!stable_node_any);
>  		if (!tree_page) {
>  			/*
>  			 * If we walked over a stale stable_node,
> @@ -1196,6 +1530,34 @@ again:
>  		else if (ret > 0)
>  			new = &parent->rb_right;
>  		else {
> +			if (page_node) {
> +				VM_BUG_ON(page_node->head != &migrate_nodes);
> +				/*
> +				 * Test if the migrated page should be merged
> +				 * into a stable node dup. If the mapcount is
> +				 * 1 we can migrate it with another KSM page
> +				 * without adding it to the chain.
> +				 */
> +				if (page_mapcount(page) > 1)
> +					goto chain_append;
> +			}
> +
> +			if (!stable_node_dup) {
> +				/*
> +				 * If the stable_node is a chain and
> +				 * we got a payload match in memcmp
> +				 * but we cannot merge the scanned
> +				 * page in any of the existing
> +				 * stable_node dups because they're
> +				 * all full, we need to wait the
> +				 * scanned page to find itself a match
> +				 * in the unstable tree to create a
> +				 * brand new KSM page to add later to
> +				 * the dups of this stable_node.
> +				 */
> +				return NULL;
> +			}
> +
>  			/*
>  			 * Lock and unlock the stable_node's page (which
>  			 * might already have been migrated) so that page
> @@ -1203,23 +1565,21 @@ again:
>  			 * It would be more elegant to return stable_node
>  			 * than kpage, but that involves more changes.
>  			 */
> -			tree_page = get_ksm_page(stable_node, true);
> -			if (tree_page) {
> -				unlock_page(tree_page);
> -				if (get_kpfn_nid(stable_node->kpfn) !=
> -						NUMA(stable_node->nid)) {
> -					put_page(tree_page);
> -					goto replace;
> -				}
> -				return tree_page;
> -			}
> -			/*
> -			 * There is now a place for page_node, but the tree may
> -			 * have been rebalanced, so re-evaluate parent and new.
> -			 */
> -			if (page_node)
> +			tree_page = get_ksm_page(stable_node_dup, true);
> +			if (unlikely(!tree_page))
> +				/*
> +				 * The tree may have been rebalanced,
> +				 * so re-evaluate parent and new.
> +				 */
>  				goto again;
> -			return NULL;
> +			unlock_page(tree_page);
> +
> +			if (get_kpfn_nid(stable_node_dup->kpfn) !=
> +			    NUMA(stable_node_dup->nid)) {
> +				put_page(tree_page);
> +				goto replace;
> +			}
> +			return tree_page;
>  		}
>  	}
>  
> @@ -1230,22 +1590,72 @@ again:
>  	DO_NUMA(page_node->nid = nid);
>  	rb_link_node(&page_node->node, parent, new);
>  	rb_insert_color(&page_node->node, root);
> -	get_page(page);
> -	return page;
> +out:
> +	if (is_page_sharing_candidate(page_node)) {
> +		get_page(page);
> +		return page;
> +	} else
> +		return NULL;
>  
>  replace:
> -	if (page_node) {
> -		list_del(&page_node->list);
> -		DO_NUMA(page_node->nid = nid);
> -		rb_replace_node(&stable_node->node, &page_node->node, root);
> -		get_page(page);
> +	if (stable_node_dup == stable_node) {
> +		/* there is no chain */
> +		if (page_node) {
> +			VM_BUG_ON(page_node->head != &migrate_nodes);
> +			list_del(&page_node->list);
> +			DO_NUMA(page_node->nid = nid);
> +			rb_replace_node(&stable_node->node, &page_node->node,
> +					root);
> +			if (is_page_sharing_candidate(page_node))
> +				get_page(page);
> +			else
> +				page = NULL;
> +		} else {
> +			rb_erase(&stable_node->node, root);
> +			page = NULL;
> +		}
>  	} else {
> -		rb_erase(&stable_node->node, root);
> -		page = NULL;
> +		VM_BUG_ON(!is_stable_node_chain(stable_node));
> +		__stable_node_dup_del(stable_node_dup);
> +		if (page_node) {
> +			VM_BUG_ON(page_node->head != &migrate_nodes);
> +			list_del(&page_node->list);
> +			DO_NUMA(page_node->nid = nid);
> +			stable_node_chain_add_dup(page_node, stable_node);
> +			if (is_page_sharing_candidate(page_node))
> +				get_page(page);
> +			else
> +				page = NULL;
> +		} else {
> +			page = NULL;
> +		}
>  	}
> -	stable_node->head = &migrate_nodes;
> -	list_add(&stable_node->list, stable_node->head);
> +	stable_node_dup->head = &migrate_nodes;
> +	list_add(&stable_node_dup->list, stable_node_dup->head);
>  	return page;
> +
> +chain_append:
> +	/* stable_node_dup could be null if it reached the limit */
> +	if (!stable_node_dup)
> +		stable_node_dup = stable_node_any;
> +	if (stable_node_dup == stable_node) {
> +		/* chain is missing so create it */
> +		stable_node = alloc_stable_node_chain(stable_node_dup,
> +						      root);
> +		if (!stable_node)
> +			return NULL;
> +	}
> +	/*
> +	 * Add this stable_node dup that was
> +	 * migrated to the stable_node chain
> +	 * of the current nid for this page
> +	 * content.
> +	 */
> +	VM_BUG_ON(page_node->head != &migrate_nodes);
> +	list_del(&page_node->list);
> +	DO_NUMA(page_node->nid = nid);
> +	stable_node_chain_add_dup(page_node, stable_node);
> +	goto out;
>  }
>  
>  /*
> @@ -1262,7 +1672,8 @@ static struct stable_node *stable_tree_insert(struct page *kpage)
>  	struct rb_root *root;
>  	struct rb_node **new;
>  	struct rb_node *parent;
> -	struct stable_node *stable_node;
> +	struct stable_node *stable_node, *stable_node_dup, *stable_node_any;
> +	bool need_chain = false;
>  
>  	kpfn = page_to_pfn(kpage);
>  	nid = get_kpfn_nid(kpfn);
> @@ -1277,7 +1688,32 @@ again:
>  
>  		cond_resched();
>  		stable_node = rb_entry(*new, struct stable_node, node);
> -		tree_page = get_ksm_page(stable_node, false);
> +		stable_node_any = NULL;
> +		stable_node_dup = chain(stable_node, &tree_page, root);
> +		if (!stable_node_dup) {
> +			/*
> +			 * Either all stable_node dups were full in
> +			 * this stable_node chain, or this chain was
> +			 * empty and should be rb_erased.
> +			 */
> +			stable_node_any = stable_node_dup_any(stable_node,
> +							      root);
> +			if (!stable_node_any) {
> +				/* rb_erase just run */
> +				goto again;
> +			}
> +			/*
> +			 * Take any of the stable_node dups page of
> +			 * this stable_node chain to let the tree walk
> +			 * continue. All KSM pages belonging to the
> +			 * stable_node dups in a stable_node chain
> +			 * have the same content and they're
> +			 * wrprotected at all times. Any will work
> +			 * fine to continue the walk.
> +			 */
> +			tree_page = get_ksm_page(stable_node_any, false);
> +		}
> +		VM_BUG_ON(!stable_node_dup ^ !!stable_node_any);
>  		if (!tree_page) {
>  			/*
>  			 * If we walked over a stale stable_node,
> @@ -1300,27 +1736,37 @@ again:
>  		else if (ret > 0)
>  			new = &parent->rb_right;
>  		else {
> -			/*
> -			 * It is not a bug that stable_tree_search() didn't
> -			 * find this node: because at that time our page was
> -			 * not yet write-protected, so may have changed since.
> -			 */
> -			return NULL;
> +			need_chain = true;
> +			break;
>  		}
>  	}
>  
> -	stable_node = alloc_stable_node();
> -	if (!stable_node)
> +	stable_node_dup = alloc_stable_node();
> +	if (!stable_node_dup)
>  		return NULL;
>  
> -	INIT_HLIST_HEAD(&stable_node->hlist);
> -	stable_node->kpfn = kpfn;
> -	set_page_stable_node(kpage, stable_node);
> -	DO_NUMA(stable_node->nid = nid);
> -	rb_link_node(&stable_node->node, parent, new);
> -	rb_insert_color(&stable_node->node, root);
> +	INIT_HLIST_HEAD(&stable_node_dup->hlist);
> +	stable_node_dup->kpfn = kpfn;
> +	set_page_stable_node(kpage, stable_node_dup);
> +	stable_node_dup->rmap_hlist_len = 0;
> +	DO_NUMA(stable_node_dup->nid = nid);
> +	if (!need_chain) {
> +		rb_link_node(&stable_node_dup->node, parent, new);
> +		rb_insert_color(&stable_node_dup->node, root);
> +	} else {
> +		if (!is_stable_node_chain(stable_node)) {
> +			struct stable_node *orig = stable_node;
> +			/* chain is missing so create it */
> +			stable_node = alloc_stable_node_chain(orig, root);
> +			if (!stable_node) {
> +				free_stable_node(stable_node_dup);
> +				return NULL;
> +			}
> +		}
> +		stable_node_chain_add_dup(stable_node_dup, stable_node);
> +	}
>  
> -	return stable_node;
> +	return stable_node_dup;
>  }
>  
>  /*
> @@ -1410,8 +1856,27 @@ struct rmap_item *unstable_tree_search_insert(struct rmap_item *rmap_item,
>   * the same ksm page.
>   */
>  static void stable_tree_append(struct rmap_item *rmap_item,
> -			       struct stable_node *stable_node)
> +			       struct stable_node *stable_node,
> +			       bool max_page_sharing_bypass)
>  {
> +	/*
> +	 * rmap won't find this mapping if we don't insert the
> +	 * rmap_item in the right stable_node
> +	 * duplicate. page_migration could break later if rmap breaks,
> +	 * so we can as well crash here. We really need to check for
> +	 * rmap_hlist_len == STABLE_NODE_CHAIN, but we can as well check
> +	 * for other negative values as an undeflow if detected here
> +	 * for the first time (and not when decreasing rmap_hlist_len)
> +	 * would be sign of memory corruption in the stable_node.
> +	 */
> +	BUG_ON(stable_node->rmap_hlist_len < 0);
> +
> +	stable_node->rmap_hlist_len++;
> +	if (!max_page_sharing_bypass)
> +		/* possibly non fatal but unexpected overflow, only warn */
> +		WARN_ON_ONCE(stable_node->rmap_hlist_len >
> +			     ksm_max_page_sharing);
> +
>  	rmap_item->head = stable_node;
>  	rmap_item->address |= STABLE_FLAG;
>  	hlist_add_head(&rmap_item->hlist, &stable_node->hlist);
> @@ -1439,19 +1904,26 @@ static void cmp_and_merge_page(struct page *page, struct rmap_item *rmap_item)
>  	struct page *kpage;
>  	unsigned int checksum;
>  	int err;
> +	bool max_page_sharing_bypass = false;
>  
>  	stable_node = page_stable_node(page);
>  	if (stable_node) {
>  		if (stable_node->head != &migrate_nodes &&
> -		    get_kpfn_nid(stable_node->kpfn) != NUMA(stable_node->nid)) {
> -			rb_erase(&stable_node->node,
> -				 root_stable_tree + NUMA(stable_node->nid));
> +		    get_kpfn_nid(READ_ONCE(stable_node->kpfn)) !=
> +		    NUMA(stable_node->nid)) {
> +			stable_node_dup_del(stable_node);
>  			stable_node->head = &migrate_nodes;
>  			list_add(&stable_node->list, stable_node->head);
>  		}
>  		if (stable_node->head != &migrate_nodes &&
>  		    rmap_item->head == stable_node)
>  			return;
> +		/*
> +		 * If it's a KSM fork, allow it to go over the sharing limit
> +		 * without warnings.
> +		 */
> +		if (!is_page_sharing_candidate(stable_node))
> +			max_page_sharing_bypass = true;
>  	}
>  
>  	/* We first start with searching the page inside the stable tree */
> @@ -1471,7 +1943,8 @@ static void cmp_and_merge_page(struct page *page, struct rmap_item *rmap_item)
>  			 * add its rmap_item to the stable tree.
>  			 */
>  			lock_page(kpage);
> -			stable_tree_append(rmap_item, page_stable_node(kpage));
> +			stable_tree_append(rmap_item, page_stable_node(kpage),
> +					   max_page_sharing_bypass);
>  			unlock_page(kpage);
>  		}
>  		put_page(kpage);
> @@ -1504,8 +1977,10 @@ static void cmp_and_merge_page(struct page *page, struct rmap_item *rmap_item)
>  			lock_page(kpage);
>  			stable_node = stable_tree_insert(kpage);
>  			if (stable_node) {
> -				stable_tree_append(tree_rmap_item, stable_node);
> -				stable_tree_append(rmap_item, stable_node);
> +				stable_tree_append(tree_rmap_item, stable_node,
> +						   false);
> +				stable_tree_append(rmap_item, stable_node,
> +						   false);
>  			}
>  			unlock_page(kpage);
>  
> @@ -2009,6 +2484,48 @@ static void wait_while_offlining(void)
>  	}
>  }
>  
> +static bool stable_node_dup_remove_range(struct stable_node *stable_node,
> +					 unsigned long start_pfn,
> +					 unsigned long end_pfn)
> +{
> +	if (stable_node->kpfn >= start_pfn &&
> +	    stable_node->kpfn < end_pfn) {
> +		/*
> +		 * Don't get_ksm_page, page has already gone:
> +		 * which is why we keep kpfn instead of page*
> +		 */
> +		remove_node_from_stable_tree(stable_node);
> +		return true;
> +	}
> +	return false;
> +}
> +
> +static bool stable_node_chain_remove_range(struct stable_node *stable_node,
> +					   unsigned long start_pfn,
> +					   unsigned long end_pfn,
> +					   struct rb_root *root)
> +{
> +	struct stable_node *dup;
> +	struct hlist_node *hlist_safe;
> +
> +	if (!is_stable_node_chain(stable_node)) {
> +		VM_BUG_ON(is_stable_node_dup(stable_node));
> +		return stable_node_dup_remove_range(stable_node, start_pfn,
> +						    end_pfn);
> +	}
> +
> +	hlist_for_each_entry_safe(dup, hlist_safe,
> +				  &stable_node->hlist, hlist_dup) {
> +		VM_BUG_ON(!is_stable_node_dup(dup));
> +		stable_node_dup_remove_range(dup, start_pfn, end_pfn);
> +	}
> +	if (hlist_empty(&stable_node->hlist)) {
> +		free_stable_node_chain(stable_node, root);
> +		return true; /* notify caller that tree was rebalanced */
> +	} else
> +		return false;
> +}
> +
>  static void ksm_check_stable_tree(unsigned long start_pfn,
>  				  unsigned long end_pfn)
>  {
> @@ -2021,15 +2538,12 @@ static void ksm_check_stable_tree(unsigned long start_pfn,
>  		node = rb_first(root_stable_tree + nid);
>  		while (node) {
>  			stable_node = rb_entry(node, struct stable_node, node);
> -			if (stable_node->kpfn >= start_pfn &&
> -			    stable_node->kpfn < end_pfn) {
> -				/*
> -				 * Don't get_ksm_page, page has already gone:
> -				 * which is why we keep kpfn instead of page*
> -				 */
> -				remove_node_from_stable_tree(stable_node);
> +			if (stable_node_chain_remove_range(stable_node,
> +							   start_pfn, end_pfn,
> +							   root_stable_tree +
> +							   nid))
>  				node = rb_first(root_stable_tree + nid);
> -			} else
> +			else
>  				node = rb_next(node);
>  			cond_resched();
>  		}
> @@ -2254,6 +2768,47 @@ static ssize_t merge_across_nodes_store(struct kobject *kobj,
>  KSM_ATTR(merge_across_nodes);
>  #endif
>  
> +static ssize_t max_page_sharing_show(struct kobject *kobj,
> +				     struct kobj_attribute *attr, char *buf)
> +{
> +	return sprintf(buf, "%u\n", ksm_max_page_sharing);
> +}
> +
> +static ssize_t max_page_sharing_store(struct kobject *kobj,
> +				      struct kobj_attribute *attr,
> +				      const char *buf, size_t count)
> +{
> +	int err;
> +	int knob;
> +
> +	err = kstrtoint(buf, 10, &knob);
> +	if (err)
> +		return err;
> +	/*
> +	 * When a KSM page is created it is shared by 2 mappings. This
> +	 * being a signed comparison, it implicitly verifies it's not
> +	 * negative.
> +	 */
> +	if (knob < 2)
> +		return -EINVAL;
> +
> +	if (READ_ONCE(ksm_max_page_sharing) == knob)
> +		return count;
> +
> +	mutex_lock(&ksm_thread_mutex);
> +	wait_while_offlining();
> +	if (ksm_max_page_sharing != knob) {
> +		if (ksm_pages_shared || remove_all_stable_nodes())
> +			err = -EBUSY;
> +		else
> +			ksm_max_page_sharing = knob;
> +	}
> +	mutex_unlock(&ksm_thread_mutex);
> +
> +	return err ? err : count;
> +}
> +KSM_ATTR(max_page_sharing);
> +
>  static ssize_t pages_shared_show(struct kobject *kobj,
>  				 struct kobj_attribute *attr, char *buf)
>  {
> @@ -2292,6 +2847,46 @@ static ssize_t pages_volatile_show(struct kobject *kobj,
>  }
>  KSM_ATTR_RO(pages_volatile);
>  
> +static ssize_t stable_node_dups_show(struct kobject *kobj,
> +				     struct kobj_attribute *attr, char *buf)
> +{
> +	return sprintf(buf, "%lu\n", ksm_stable_node_dups);
> +}
> +KSM_ATTR_RO(stable_node_dups);
> +
> +static ssize_t stable_node_chains_show(struct kobject *kobj,
> +				       struct kobj_attribute *attr, char *buf)
> +{
> +	return sprintf(buf, "%lu\n", ksm_stable_node_chains);
> +}
> +KSM_ATTR_RO(stable_node_chains);
> +
> +static ssize_t
> +stable_node_chains_prune_millisecs_show(struct kobject *kobj,
> +					struct kobj_attribute *attr,
> +					char *buf)
> +{
> +	return sprintf(buf, "%u\n", ksm_stable_node_chains_prune_millisecs);
> +}
> +
> +static ssize_t
> +stable_node_chains_prune_millisecs_store(struct kobject *kobj,
> +					 struct kobj_attribute *attr,
> +					 const char *buf, size_t count)
> +{
> +	unsigned long msecs;
> +	int err;
> +
> +	err = kstrtoul(buf, 10, &msecs);
> +	if (err || msecs > UINT_MAX)
> +		return -EINVAL;
> +
> +	ksm_stable_node_chains_prune_millisecs = msecs;
> +
> +	return count;
> +}
> +KSM_ATTR(stable_node_chains_prune_millisecs);
> +
>  static ssize_t full_scans_show(struct kobject *kobj,
>  			       struct kobj_attribute *attr, char *buf)
>  {
> @@ -2311,6 +2906,10 @@ static struct attribute *ksm_attrs[] = {
>  #ifdef CONFIG_NUMA
>  	&merge_across_nodes_attr.attr,
>  #endif
> +	&max_page_sharing_attr.attr,
> +	&stable_node_chains_attr.attr,
> +	&stable_node_dups_attr.attr,
> +	&stable_node_chains_prune_millisecs_attr.attr,
>  	NULL,
>  };
>  

-- 
Petr Holasek
pholasek@redhat.com

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>