* [RFC] [PATCH 0/1] ksm: fix use after free with merge_across_nodes = 0
@ 2017-05-12 19:38 Andrea Arcangeli
2017-05-12 19:38 ` [PATCH 1/1] " Andrea Arcangeli
2017-05-12 20:37 ` [RFC] [PATCH 0/1] " Andrew Morton
0 siblings, 2 replies; 4+ messages in thread
From: Andrea Arcangeli @ 2017-05-12 19:38 UTC (permalink / raw)
To: Andrew Morton, linux-mm
Cc: Evgheni Dereveanchin, Andrey Ryabinin, Petr Holasek,
Hugh Dickins, Arjan van de Ven, Davidlohr Bueso, Gavin Guo,
Jay Vosburgh, Mel Gorman
Hello,
The KSMscale patch in -mm (not yet upstream) is fundamental for
enterprise use and in turn it's included in -mm, RHEL, CentoOS and
Ubuntu and it'd be great if it could be merged upstream (especially
after solving this problem with merge_across_nodes = 0 ...).
https://marc.info/?l=linux-mm&m=149265809928003&w=2
http://kernel.ubuntu.com/~gavinguo/sf00131845/numa-131845.svg
http://kernel.ubuntu.com/~gavinguo/sf00131845/virtual_appliances_loading.png
A few weeks ago I got a report that with merge_across_nodes set to 0
KSM would eventually crash with an user after free (I assumed it was
an use after free because the kindly provided crashdump showed a
corrupted stable_node). Everything was again rock solid after setting
merge_across_nodes back to 1.
merge_across_nodes set to 0 is a tuning performance optimization
for NUMA that creates a different copy of KSM pages for each NUMA node
with a KSM stable_tree for each node (instead of sharing the same
equal memory across the whole system with a single stable_tree).
I couldn't reproduce this bug so far but there's a definitive use
after free in the merge_across_nodes = 0 path, so it would help if who
can reproduce already can give this a spin (untested... or better
tested but only in a NUMA balancing environment that never reproduced the use
after free in the first place so it's inconclusive).
In production I recommend to leave the merge_across_nodes default
value set to 1 if running with the KSMscale patch applied for the time
being, until this is confirmed fixed.
Again this fix should be considered untested so it should be run in testing
environment only.
Thanks,
Andrea
Andrea Arcangeli (1):
ksm: fix use after free with merge_across_nodes = 0
mm/ksm.c | 66 +++++++++++++++++++++++++++++++++++++++++++++++++++++-----------
1 file changed, 55 insertions(+), 11 deletions(-)
--
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>
^ permalink raw reply [flat|nested] 4+ messages in thread
* [PATCH 1/1] ksm: fix use after free with merge_across_nodes = 0
2017-05-12 19:38 [RFC] [PATCH 0/1] ksm: fix use after free with merge_across_nodes = 0 Andrea Arcangeli
@ 2017-05-12 19:38 ` Andrea Arcangeli
2017-05-15 16:14 ` Andrey Ryabinin
2017-05-12 20:37 ` [RFC] [PATCH 0/1] " Andrew Morton
1 sibling, 1 reply; 4+ messages in thread
From: Andrea Arcangeli @ 2017-05-12 19:38 UTC (permalink / raw)
To: Andrew Morton, linux-mm
Cc: Evgheni Dereveanchin, Andrey Ryabinin, Petr Holasek,
Hugh Dickins, Arjan van de Ven, Davidlohr Bueso, Gavin Guo,
Jay Vosburgh, Mel Gorman
If merge_across_nodes was manually set to 0 (not the default value) by
the admin or a tuned profile on NUMA systems triggering cross-NODE
page migrations, a stable_node use after free could materialize.
If the chain is collapsed stable_node would point to the old chain
that was already freed. stable_node_dup would be the stable_node dup
now converted to a regular stable_node and indexed in the rbtree in
replacement of the freed stable_node chain (not anymore a dup).
This special case where the chain is collapsed in the NUMA replacement
path, is now detected by setting stable_node to NULL by the
chain_prune callee if it decides to collapse the chain. This tells the
NUMA replacement code that even if stable_node and stable_node_dup are
different, this is not a chain if stable_node is NULL, as the
stable_node_dup was converted to a regular stable_node and the chain
was collapsed.
It is generally safer for the callee to force the caller stable_node
to NULL the moment it become stale so any other mistake like this
would result in an instant Oops easier to debug than an use after free.
Otherwise the replace logic would act like if stable_node was a valid
chain, when in fact it was freed. Notably
stable_node_chain_add_dup(page_node, stable_node) would run on a
stable stable_node.
Andrey Ryabinin found the source of the use after free in
chain_prune().
Reported-by: Andrey Ryabinin <aryabinin@virtuozzo.com>
Reported-by: Evgheni Dereveanchin <ederevea@redhat.com>
Signed-off-by: Andrea Arcangeli <aarcange@redhat.com>
---
mm/ksm.c | 66 +++++++++++++++++++++++++++++++++++++++++++++++++++++-----------
1 file changed, 55 insertions(+), 11 deletions(-)
diff --git a/mm/ksm.c b/mm/ksm.c
index 44a1b2a..b53fd58 100644
--- a/mm/ksm.c
+++ b/mm/ksm.c
@@ -338,6 +338,7 @@ static inline void stable_node_chain_add_dup(struct stable_node *dup,
static inline void __stable_node_dup_del(struct stable_node *dup)
{
+ VM_BUG_ON(!is_stable_node_dup(dup));
hlist_del(&dup->hlist_dup);
ksm_stable_node_dups--;
}
@@ -1315,12 +1316,12 @@ 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,
+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 stable_node *dup, *found = NULL, *stable_node = *_stable_node;
struct hlist_node *hlist_safe;
struct page *_tree_page;
int nr = 0;
@@ -1393,6 +1394,15 @@ static struct stable_node *stable_node_dup(struct stable_node *stable_node,
free_stable_node(stable_node);
ksm_stable_node_chains--;
ksm_stable_node_dups--;
+ /*
+ * NOTE: the caller depends on the
+ * *_stable_node to become NULL if the chain
+ * was collapsed. Enforce that if anything
+ * uses a stale (freed) stable_node chain a
+ * visible crash will materialize (instead of
+ * an use after free).
+ */
+ *_stable_node = stable_node = NULL;
} else if (__is_page_sharing_candidate(found, 1)) {
/*
* Refile our candidate at the head
@@ -1422,11 +1432,12 @@ static struct stable_node *stable_node_dup_any(struct stable_node *stable_node,
typeof(*stable_node), hlist_dup);
}
-static struct stable_node *__stable_node_chain(struct stable_node *stable_node,
+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)
{
+ struct stable_node *stable_node = *_stable_node;
if (!is_stable_node_chain(stable_node)) {
if (is_page_sharing_candidate(stable_node)) {
*tree_page = get_ksm_page(stable_node, false);
@@ -1434,11 +1445,11 @@ static struct stable_node *__stable_node_chain(struct stable_node *stable_node,
}
return NULL;
}
- return stable_node_dup(stable_node, tree_page, root,
+ 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,
+static __always_inline struct stable_node *chain_prune(struct stable_node **s_n,
struct page **t_p,
struct rb_root *root)
{
@@ -1449,7 +1460,7 @@ 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);
+ return __stable_node_chain(&s_n, t_p, root, false);
}
/*
@@ -1490,7 +1501,15 @@ static struct page *stable_tree_search(struct page *page)
cond_resched();
stable_node = rb_entry(*new, struct stable_node, node);
stable_node_any = NULL;
- stable_node_dup = chain_prune(stable_node, &tree_page, root);
+ stable_node_dup = chain_prune(&stable_node, &tree_page, root);
+ /*
+ * NOTE: stable_node may have been freed by
+ * chain_prune() if the returned stable_node_dup is
+ * not NULL. stable_node_dup may have been inserted in
+ * the rbtree instead as a regular stable_node (in
+ * order to collapse the stable_node chain if a single
+ * stable_node dup was found in it).
+ */
if (!stable_node_dup) {
/*
* Either all stable_node dups were full in
@@ -1605,20 +1624,33 @@ static struct page *stable_tree_search(struct page *page)
return NULL;
replace:
- if (stable_node_dup == stable_node) {
+ /*
+ * If stable_node was a chain and chain_prune collapsed it,
+ * stable_node will be NULL here. In that case the
+ * stable_node_dup is the regular stable_node that has
+ * replaced the chain. If stable_node is not NULL and equal to
+ * stable_node_dup there was no chain and stable_node_dup is
+ * the regular stable_node in the stable rbtree. Otherwise
+ * stable_node is the chain and stable_node_dup is the dup to
+ * replace.
+ */
+ if (!stable_node || stable_node_dup == stable_node) {
+ VM_BUG_ON(is_stable_node_chain(stable_node_dup));
+ VM_BUG_ON(is_stable_node_dup(stable_node_dup));
/* 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,
+ rb_replace_node(&stable_node_dup->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);
+ rb_erase(&stable_node_dup->node, root);
page = NULL;
}
} else {
@@ -1645,7 +1677,17 @@ static struct page *stable_tree_search(struct page *page)
/* 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) {
+ /*
+ * If stable_node was a chain and chain_prune collapsed it,
+ * stable_node will be NULL here. In that case the
+ * stable_node_dup is the regular stable_node that has
+ * replaced the chain. If stable_node is not NULL and equal to
+ * stable_node_dup there was no chain and stable_node_dup is
+ * the regular stable_node in the stable rbtree.
+ */
+ if (!stable_node || stable_node_dup == stable_node) {
+ VM_BUG_ON(is_stable_node_chain(stable_node_dup));
+ VM_BUG_ON(is_stable_node_dup(stable_node_dup));
/* chain is missing so create it */
stable_node = alloc_stable_node_chain(stable_node_dup,
root);
@@ -1658,6 +1700,8 @@ static struct page *stable_tree_search(struct page *page)
* of the current nid for this page
* content.
*/
+ VM_BUG_ON(!is_stable_node_chain(stable_node));
+ VM_BUG_ON(!is_stable_node_dup(stable_node_dup));
VM_BUG_ON(page_node->head != &migrate_nodes);
list_del(&page_node->list);
DO_NUMA(page_node->nid = nid);
--
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>
^ permalink raw reply related [flat|nested] 4+ messages in thread
* Re: [RFC] [PATCH 0/1] ksm: fix use after free with merge_across_nodes = 0
2017-05-12 19:38 [RFC] [PATCH 0/1] ksm: fix use after free with merge_across_nodes = 0 Andrea Arcangeli
2017-05-12 19:38 ` [PATCH 1/1] " Andrea Arcangeli
@ 2017-05-12 20:37 ` Andrew Morton
1 sibling, 0 replies; 4+ messages in thread
From: Andrew Morton @ 2017-05-12 20:37 UTC (permalink / raw)
To: Andrea Arcangeli
Cc: linux-mm, Evgheni Dereveanchin, Andrey Ryabinin, Petr Holasek,
Hugh Dickins, Arjan van de Ven, Davidlohr Bueso, Gavin Guo,
Jay Vosburgh, Mel Gorman
On Fri, 12 May 2017 21:38:04 +0200 Andrea Arcangeli <aarcange@redhat.com> wrote:
> The KSMscale patch in -mm (not yet upstream) is fundamental for
> enterprise use and in turn it's included in -mm, RHEL, CentoOS and
> Ubuntu and it'd be great if it could be merged upstream (especially
> after solving this problem with merge_across_nodes = 0 ...).
In April 2016 I folded two fixes against
ksm-introduce-ksm_max_page_sharing-per-page-deduplication-limit.patch
into that patch and disabled the patch from -mm. I think/assume
because it was causing crashes. The patch then got forgotten about.
I have resurrected it (below) and merged this patch after it.
From: Andrea Arcangeli <aarcange@redhat.com>
Subject: ksm: introduce ksm_max_page_sharing per page deduplication limit
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.
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.
[akpm@linux-foundation.org: fix non-NUMA build]
Signed-off-by: Andrea Arcangeli <aarcange@redhat.com>
Tested-by: Petr Holasek <pholasek@redhat.com>
Cc: Hugh Dickins <hughd@google.com>
Cc: Davidlohr Bueso <dave@stgolabs.net>
Cc: Arjan van de Ven <arjan@linux.intel.com>
Cc: Evgheni Dereveanchin <ederevea@redhat.com>
Cc: Andrey Ryabinin <aryabinin@virtuozzo.com>
Cc: Gavin Guo <gavin.guo@canonical.com>
Cc: Jay Vosburgh <jay.vosburgh@canonical.com>
Cc: Mel Gorman <mgorman@techsingularity.net>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---
Documentation/vm/ksm.txt | 63 +++
mm/ksm.c | 733 +++++++++++++++++++++++++++++++++----
2 files changed, 730 insertions(+), 66 deletions(-)
diff -puN Documentation/vm/ksm.txt~ksm-introduce-ksm_max_page_sharing-per-page-deduplication-limit Documentation/vm/ksm.txt
--- a/Documentation/vm/ksm.txt~ksm-introduce-ksm_max_page_sharing-per-page-deduplication-limit
+++ a/Documentation/vm/ksm.txt
@@ -98,6 +98,50 @@ use_zero_pages - specifies whether emp
it is only effective for pages merged after the change.
Default: 0 (normal KSM behaviour as in earlier releases)
+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
@@ -106,10 +150,29 @@ pages_unshared - how many pages unique
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 -puN mm/ksm.c~ksm-introduce-ksm_max_page_sharing-per-page-deduplication-limit mm/ksm.c
--- a/mm/ksm.c~ksm-introduce-ksm_max_page_sharing-per-page-deduplication-limit
+++ a/mm/ksm.c
@@ -128,9 +128,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 {
@@ -138,11 +141,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
@@ -192,6 +208,7 @@ static struct rb_root *root_unstable_tre
/* 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);
@@ -219,6 +236,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;
@@ -287,6 +316,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;
@@ -317,6 +384,8 @@ static inline struct stable_node *alloc_
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);
}
@@ -498,25 +567,82 @@ static inline int get_kpfn_nid(unsigned
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;
+#if defined (CONFIG_DEBUG_VM) && defined(CONFIG_NUMA)
+ 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.
+ */
+#if GCC_VERSION >= 40903 /* only recent gcc can handle it */
+ BUILD_BUG_ON(STABLE_NODE_DUP_HEAD <= &migrate_nodes);
+ BUILD_BUG_ON(STABLE_NODE_DUP_HEAD >= &migrate_nodes + 1);
+#endif
+
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);
}
@@ -635,6 +761,8 @@ static void remove_rmap_item_from_tree(s
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;
@@ -743,6 +871,31 @@ static int remove_stable_node(struct sta
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, *next;
@@ -753,7 +906,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 */
}
@@ -1139,6 +1293,163 @@ static struct page *try_to_merge_two_pag
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
*
@@ -1154,7 +1465,7 @@ static struct page *stable_tree_search(s
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);
@@ -1176,7 +1487,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,
@@ -1199,6 +1535,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
@@ -1206,23 +1570,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;
}
}
@@ -1233,22 +1595,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;
}
/*
@@ -1265,7 +1677,8 @@ static struct stable_node *stable_tree_i
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);
@@ -1280,7 +1693,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,
@@ -1303,27 +1741,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;
}
/*
@@ -1413,8 +1861,27 @@ struct rmap_item *unstable_tree_search_i
* 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);
@@ -1442,19 +1909,26 @@ static void cmp_and_merge_page(struct pa
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 */
@@ -1474,7 +1948,8 @@ static void cmp_and_merge_page(struct pa
* 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);
@@ -1524,8 +1999,10 @@ static void cmp_and_merge_page(struct pa
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);
@@ -2029,6 +2506,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)
{
@@ -2040,15 +2559,12 @@ static void ksm_check_stable_tree(unsign
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();
}
@@ -2294,6 +2810,47 @@ static ssize_t use_zero_pages_store(stru
}
KSM_ATTR(use_zero_pages);
+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)
{
@@ -2332,6 +2889,46 @@ static ssize_t pages_volatile_show(struc
}
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)
{
@@ -2351,6 +2948,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,
&use_zero_pages_attr.attr,
NULL,
};
_
--
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>
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH 1/1] ksm: fix use after free with merge_across_nodes = 0
2017-05-12 19:38 ` [PATCH 1/1] " Andrea Arcangeli
@ 2017-05-15 16:14 ` Andrey Ryabinin
0 siblings, 0 replies; 4+ messages in thread
From: Andrey Ryabinin @ 2017-05-15 16:14 UTC (permalink / raw)
To: Andrea Arcangeli, Andrew Morton, linux-mm
Cc: Evgheni Dereveanchin, Petr Holasek, Hugh Dickins,
Arjan van de Ven, Davidlohr Bueso, Gavin Guo, Jay Vosburgh,
Mel Gorman
On 05/12/2017 10:38 PM, Andrea Arcangeli wrote:
> If merge_across_nodes was manually set to 0 (not the default value) by
> the admin or a tuned profile on NUMA systems triggering cross-NODE
> page migrations, a stable_node use after free could materialize.
>
> If the chain is collapsed stable_node would point to the old chain
> that was already freed. stable_node_dup would be the stable_node dup
> now converted to a regular stable_node and indexed in the rbtree in
> replacement of the freed stable_node chain (not anymore a dup).
>
> This special case where the chain is collapsed in the NUMA replacement
> path, is now detected by setting stable_node to NULL by the
> chain_prune callee if it decides to collapse the chain. This tells the
> NUMA replacement code that even if stable_node and stable_node_dup are
> different, this is not a chain if stable_node is NULL, as the
> stable_node_dup was converted to a regular stable_node and the chain
> was collapsed.
>
> It is generally safer for the callee to force the caller stable_node
> to NULL the moment it become stale so any other mistake like this
> would result in an instant Oops easier to debug than an use after free.
>
> Otherwise the replace logic would act like if stable_node was a valid
> chain, when in fact it was freed. Notably
> stable_node_chain_add_dup(page_node, stable_node) would run on a
> stable stable_node.
>
> Andrey Ryabinin found the source of the use after free in
> chain_prune().
>
> Reported-by: Andrey Ryabinin <aryabinin@virtuozzo.com>
> Reported-by: Evgheni Dereveanchin <ederevea@redhat.com>
> Signed-off-by: Andrea Arcangeli <aarcange@redhat.com>
> ---
Works for me,
Tested-by: Andrey Ryabinin <aryabinin@virtuozzo.com>
Bellow is reproducer which causes crash in ksm in several minutes without this fix.
$ cat ksm_test.c
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <sys/mman.h>
#include <stdlib.h>
#include <unistd.h>
#include <stdio.h>
#include <numaif.h>
#include <sys/types.h>
#include <sys/wait.h>
#define NR_NODES 4
#define MAP_SIZE 4096
#define NR_THREADS 1024
pid_t pids[NR_THREADS];
int merge_and_migrate(void)
{
void *p;
unsigned long rnd;
unsigned long old_node, new_node;
pid_t p_pid, pid;
int j;
p = mmap(NULL, MAP_SIZE, PROT_READ|PROT_WRITE,
MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
if (p == MAP_FAILED)
perror("mmap"), exit(1);
memset(p, 0xff, MAP_SIZE);
if (madvise(p, MAP_SIZE, MADV_MERGEABLE))
perror("madvise"), exit(1);
while (1) {
sleep(0);
rnd = rand() % 2;
switch (rnd) {
case 0: {
rnd = rand() % 128;
memset(p, rnd, MAP_SIZE);
break;
}
case 1: {
j = rand()%NR_NODES;
old_node = 1 << j;
new_node = 1<<((j+1)%NR_NODES);
migrate_pages(0, NR_NODES, &old_node, &new_node);
break;
}
}
}
return 0;
}
int main(void)
{
int i,ret,j;
pid_t pid;
int wstatus;
unsigned long old_node, new_node;
for (i = 0; i < NR_THREADS; i++) {
pid = fork();
if (pid < 0) {
perror("fork");
return 1;
}
if (pid) {
pids[i] = pid;
continue;
} else
merge_and_migrate();
}
while (1) {
pid = waitpid(-1, &wstatus, WNOHANG);
if (pid < 0) {
perror("waitpid failed");
return 1;
}
if (pid) {
for (i = 0; i< NR_THREADS; i++) {
if (pids[i] == pid) {
pid = fork();
if (pid < 0) {
perror("fork in while");
return 1;
}
if (pid) {
pids[i] = pid;
break;
} else
merge_and_migrate();
}
}
continue; /*while(1)*/
}
i = rand()%NR_THREADS;
kill(pids[i], SIGKILL);
}
return 0;
}
$ cat run_ksm.sh
#!/bin/bash
gcc -lnuma -O2 ksm_test.c -o ksm_test
echo 1 > /sys/kernel/mm/ksm/run
echo 0 > /sys/kernel/mm/ksm/merge_across_nodes
echo 2 > /sys/kernel/mm/ksm/max_page_sharing
echo 0 > /sys/kernel/mm/ksm/stable_node_chains_prune_millisecs
./ksm_test
$ ./run_ksm.sh
[ 203.251200] ==================================================================
[ 203.251679] BUG: KASAN: use-after-free in stable_tree_search+0x1450/0x16f0
[ 203.252229] Read of size 4 at addr ffff880037e9d938 by task ksmd/170
[ 203.252800]
[ 203.252957] CPU: 2 PID: 170 Comm: ksmd Not tainted 4.12.0-rc1-next-20170515+ #639
[ 203.253627] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS rel-1.10.2-0-g5f4c7b1-prebuilt.qemu-project.org 04/01/2014
[ 203.254670] Call Trace:
[ 203.254907] dump_stack+0x67/0x98
[ 203.255222] print_address_description+0x7c/0x290
[ 203.255652] ? stable_tree_search+0x1450/0x16f0
[ 203.256073] kasan_report+0x26e/0x350
[ 203.256418] __asan_report_load4_noabort+0x19/0x20
[ 203.256852] stable_tree_search+0x1450/0x16f0
[ 203.257262] ? __stable_node_chain+0x8a0/0x8a0
[ 203.257668] ? follow_page_mask+0x5f9/0xd80
[ 203.258060] ksm_scan_thread+0xb47/0x2790
[ 203.258438] ? stable_tree_search+0x16f0/0x16f0
[ 203.258858] ? __schedule+0x904/0x1ad0
[ 203.259214] ? clkdev_alloc+0xd0/0xd0
[ 203.259553] ? wake_atomic_t_function+0x2a0/0x2a0
[ 203.259985] ? trace_hardirqs_on+0xd/0x10
[ 203.260361] kthread+0x2d6/0x3d0
[ 203.260658] ? stable_tree_search+0x16f0/0x16f0
[ 203.261073] ? kthread_create_on_node+0xb0/0xb0
[ 203.261485] ret_from_fork+0x2e/0x40
[ 203.261819]
[ 203.261936] Allocated by task 170:
[ 203.262251] save_stack_trace+0x1b/0x20
[ 203.262601] kasan_kmalloc+0xee/0x180
[ 203.262938] kasan_slab_alloc+0x12/0x20
[ 203.263290] kmem_cache_alloc+0x129/0x2d0
[ 203.263654] alloc_stable_node_chain+0x29/0x310
[ 203.264072] ksm_scan_thread+0x2048/0x2790
[ 203.264444] kthread+0x2d6/0x3d0
[ 203.264744] ret_from_fork+0x2e/0x40
[ 203.265075]
[ 203.265220] Freed by task 170:
[ 203.265503] save_stack_trace+0x1b/0x20
[ 203.265852] kasan_slab_free+0xad/0x180
[ 203.266208] kmem_cache_free+0xc7/0x300
[ 203.266558] __stable_node_chain+0x68a/0x8a0
[ 203.266948] stable_tree_search+0x18e/0x16f0
[ 203.267339] ksm_scan_thread+0xb47/0x2790
[ 203.267655] kthread+0x2d6/0x3d0
[ 203.267910] ret_from_fork+0x2e/0x40
--
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>
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2017-05-15 16:12 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-05-12 19:38 [RFC] [PATCH 0/1] ksm: fix use after free with merge_across_nodes = 0 Andrea Arcangeli
2017-05-12 19:38 ` [PATCH 1/1] " Andrea Arcangeli
2017-05-15 16:14 ` Andrey Ryabinin
2017-05-12 20:37 ` [RFC] [PATCH 0/1] " Andrew Morton
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.