Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > linux.kernel > #1319875 > unrolled thread
| Started by | Matthew Wilcox <matthew.r.wilcox@intel.com> |
|---|---|
| First post | 2016-01-27 22:20 +0100 |
| Last post | 2016-02-03 07:30 +0100 |
| Articles | 9 — 4 participants |
Back to article view | Back to linux.kernel
[PATCH 0/5] Fix races & improve the radix tree iterator patterns Matthew Wilcox <matthew.r.wilcox@intel.com> - 2016-01-27 22:20 +0100
[PATCH 1/5] radix-tree: Fix race in gang lookup Matthew Wilcox <matthew.r.wilcox@intel.com> - 2016-01-27 22:20 +0100
Re: [PATCH 1/5] radix-tree: Fix race in gang lookup Konstantin Khlebnikov <koct9i@gmail.com> - 2016-02-03 22:40 +0100
Re: [PATCH 1/5] radix-tree: Fix race in gang lookup Konstantin Khlebnikov <koct9i@gmail.com> - 2016-02-04 09:50 +0100
[PATCH 4/5] mm: Use radix_tree_iter_retry() Matthew Wilcox <matthew.r.wilcox@intel.com> - 2016-01-27 22:20 +0100
Re: [PATCH 4/5] mm: Use radix_tree_iter_retry() Vlastimil Babka <vbabka@suse.cz> - 2016-01-29 15:50 +0100
Re: [PATCH 4/5] mm: Use radix_tree_iter_retry() Matthew Wilcox <willy@linux.intel.com> - 2016-01-29 16:00 +0100
Re: [PATCH 0/5] Fix races & improve the radix tree iterator patterns Konstantin Khlebnikov <koct9i@gmail.com> - 2016-01-28 08:20 +0100
Re: [PATCH 0/5] Fix races & improve the radix tree iterator patterns Konstantin Khlebnikov <koct9i@gmail.com> - 2016-02-03 07:30 +0100
| From | Matthew Wilcox <matthew.r.wilcox@intel.com> |
|---|---|
| Date | 2016-01-27 22:20 +0100 |
| Subject | [PATCH 0/5] Fix races & improve the radix tree iterator patterns |
| Message-ID | <qVFFo-1hk-29@gated-at.bofh.it> |
From: Matthew Wilcox <willy@linux.intel.com> The first two patches here are bugfixes, and I would like to see them make their way into stable ASAP since they can lead to data corruption (very low probabilty). The last three patches do not qualify as bugfixes. They simply improve the standard pattern used to do radix tree iterations by removing the 'goto restart' part. Partially this is because this is an ugly & confusing goto, and partially because with multi-order entries in the tree, it'll be more likely that we'll see an indirect_ptr bit, and it's more efficient to kep going from the point of the iteration we're currently in than restart from the beginning each time. Matthew Wilcox (5): radix-tree: Fix race in gang lookup hwspinlock: Fix race between radix tree insertion and lookup btrfs: Use radix_tree_iter_retry() mm: Use radix_tree_iter_retry() radix-tree,shmem: Introduce radix_tree_iter_next() drivers/hwspinlock/hwspinlock_core.c | 4 +++ fs/btrfs/tests/btrfs-tests.c | 3 +- include/linux/radix-tree.h | 31 +++++++++++++++++++++ lib/radix-tree.c | 12 ++++++-- mm/filemap.c | 53 ++++++++++++------------------------ mm/shmem.c | 30 ++++++++++---------- 6 files changed, 78 insertions(+), 55 deletions(-) -- 2.7.0.rc3
[toc] | [next] | [standalone]
| From | Matthew Wilcox <matthew.r.wilcox@intel.com> |
|---|---|
| Date | 2016-01-27 22:20 +0100 |
| Subject | [PATCH 1/5] radix-tree: Fix race in gang lookup |
| Message-ID | <qVFFr-1hk-73@gated-at.bofh.it> |
| In reply to | #1319875 |
From: Matthew Wilcox <willy@linux.intel.com>
If the indirect_ptr bit is set on a slot, that indicates we need to
redo the lookup. Introduce a new function radix_tree_iter_retry()
which forces the loop to retry the lookup by setting 'slot' to NULL and
turning the iterator back to point at the problematic entry.
This is a pretty rare problem to hit at the moment; the lookup has to
race with a grow of the radix tree from a height of 0. The consequences
of hitting this race are that gang lookup could return a pointer to a
radix_tree_node instead of a pointer to whatever the user had inserted
in the tree.
Fixes: cebbd29e1c2f ("radix-tree: rewrite gang lookup using iterator")
Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
Cc: stable@vger.kernel.org
---
include/linux/radix-tree.h | 16 ++++++++++++++++
lib/radix-tree.c | 12 ++++++++++--
2 files changed, 26 insertions(+), 2 deletions(-)
diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index f9a3da5bf892..db0ed595749b 100644
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -387,6 +387,22 @@ void **radix_tree_next_chunk(struct radix_tree_root *root,
struct radix_tree_iter *iter, unsigned flags);
/**
+ * radix_tree_iter_retry - retry this chunk of the iteration
+ * @iter: iterator state
+ *
+ * If we iterate over a tree protected only by the RCU lock, a race
+ * against deletion or creation may result in seeing a slot for which
+ * radix_tree_deref_retry() returns true. If so, call this function
+ * and continue the iteration.
+ */
+static inline __must_check
+void **radix_tree_iter_retry(struct radix_tree_iter *iter)
+{
+ iter->next_index = iter->index;
+ return NULL;
+}
+
+/**
* radix_tree_chunk_size - get current chunk size
*
* @iter: pointer to radix tree iterator
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index a25f635dcc56..65422ac17114 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -1105,9 +1105,13 @@ radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
return 0;
radix_tree_for_each_slot(slot, root, &iter, first_index) {
- results[ret] = indirect_to_ptr(rcu_dereference_raw(*slot));
+ results[ret] = rcu_dereference_raw(*slot);
if (!results[ret])
continue;
+ if (radix_tree_is_indirect_ptr(results[ret])) {
+ slot = radix_tree_iter_retry(&iter);
+ continue;
+ }
if (++ret == max_items)
break;
}
@@ -1184,9 +1188,13 @@ radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
return 0;
radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) {
- results[ret] = indirect_to_ptr(rcu_dereference_raw(*slot));
+ results[ret] = rcu_dereference_raw(*slot);
if (!results[ret])
continue;
+ if (radix_tree_is_indirect_ptr(results[ret])) {
+ slot = radix_tree_iter_retry(&iter);
+ continue;
+ }
if (++ret == max_items)
break;
}
--
2.7.0.rc3
[toc] | [prev] | [next] | [standalone]
| From | Konstantin Khlebnikov <koct9i@gmail.com> |
|---|---|
| Date | 2016-02-03 22:40 +0100 |
| Subject | Re: [PATCH 1/5] radix-tree: Fix race in gang lookup |
| Message-ID | <qYdjz-7nl-1@gated-at.bofh.it> |
| In reply to | #1319881 |
On Thu, Jan 28, 2016 at 12:17 AM, Matthew Wilcox
<matthew.r.wilcox@intel.com> wrote:
> From: Matthew Wilcox <willy@linux.intel.com>
>
> If the indirect_ptr bit is set on a slot, that indicates we need to
> redo the lookup. Introduce a new function radix_tree_iter_retry()
> which forces the loop to retry the lookup by setting 'slot' to NULL and
> turning the iterator back to point at the problematic entry.
>
> This is a pretty rare problem to hit at the moment; the lookup has to
> race with a grow of the radix tree from a height of 0. The consequences
> of hitting this race are that gang lookup could return a pointer to a
> radix_tree_node instead of a pointer to whatever the user had inserted
> in the tree.
>
> Fixes: cebbd29e1c2f ("radix-tree: rewrite gang lookup using iterator")
> Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
> Cc: stable@vger.kernel.org
> ---
> include/linux/radix-tree.h | 16 ++++++++++++++++
> lib/radix-tree.c | 12 ++++++++++--
> 2 files changed, 26 insertions(+), 2 deletions(-)
>
> diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
> index f9a3da5bf892..db0ed595749b 100644
> --- a/include/linux/radix-tree.h
> +++ b/include/linux/radix-tree.h
> @@ -387,6 +387,22 @@ void **radix_tree_next_chunk(struct radix_tree_root *root,
> struct radix_tree_iter *iter, unsigned flags);
>
> /**
> + * radix_tree_iter_retry - retry this chunk of the iteration
> + * @iter: iterator state
> + *
> + * If we iterate over a tree protected only by the RCU lock, a race
> + * against deletion or creation may result in seeing a slot for which
> + * radix_tree_deref_retry() returns true. If so, call this function
> + * and continue the iteration.
> + */
> +static inline __must_check
> +void **radix_tree_iter_retry(struct radix_tree_iter *iter)
> +{
> + iter->next_index = iter->index;
> + return NULL;
> +}
> +
> +/**
> * radix_tree_chunk_size - get current chunk size
> *
> * @iter: pointer to radix tree iterator
> diff --git a/lib/radix-tree.c b/lib/radix-tree.c
> index a25f635dcc56..65422ac17114 100644
> --- a/lib/radix-tree.c
> +++ b/lib/radix-tree.c
> @@ -1105,9 +1105,13 @@ radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
> return 0;
>
> radix_tree_for_each_slot(slot, root, &iter, first_index) {
> - results[ret] = indirect_to_ptr(rcu_dereference_raw(*slot));
> + results[ret] = rcu_dereference_raw(*slot);
> if (!results[ret])
> continue;
> + if (radix_tree_is_indirect_ptr(results[ret])) {
> + slot = radix_tree_iter_retry(&iter);
> + continue;
> + }
> if (++ret == max_items)
> break;
> }
Looks like your fix doesn't work.
After radix_tree_iter_retry: radix_tree_for_each_slot will call
radix_tree_next_slot which isn't safe to call for NULL slot.
#define radix_tree_for_each_slot(slot, root, iter, start) \
for (slot = radix_tree_iter_init(iter, start) ; \
slot || (slot = radix_tree_next_chunk(root, iter, 0)) ; \
slot = radix_tree_next_slot(slot, iter, 0))
tagged iterator works becase restart happens only at root - tags
filled with single bit.
quick (untested) fix for that
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -457,9 +457,9 @@ radix_tree_next_slot(void **slot, struct
radix_tree_iter *iter, unsigned flags)
return slot + offset + 1;
}
} else {
- unsigned size = radix_tree_chunk_size(iter) - 1;
+ int size = radix_tree_chunk_size(iter) - 1;
- while (size--) {
+ while (size-- > 0) {
slot++;
iter->index++;
if (likely(*slot))
> @@ -1184,9 +1188,13 @@ radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
> return 0;
>
> radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) {
> - results[ret] = indirect_to_ptr(rcu_dereference_raw(*slot));
> + results[ret] = rcu_dereference_raw(*slot);
> if (!results[ret])
> continue;
> + if (radix_tree_is_indirect_ptr(results[ret])) {
> + slot = radix_tree_iter_retry(&iter);
> + continue;
> + }
> if (++ret == max_items)
> break;
> }
> --
> 2.7.0.rc3
>
> --
> 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>
[toc] | [prev] | [next] | [standalone]
| From | Konstantin Khlebnikov <koct9i@gmail.com> |
|---|---|
| Date | 2016-02-04 09:50 +0100 |
| Subject | Re: [PATCH 1/5] radix-tree: Fix race in gang lookup |
| Message-ID | <qYnLX-6cC-13@gated-at.bofh.it> |
| In reply to | #1325980 |
[Multipart message — attachments visible in raw view] — view raw
On Thu, Feb 4, 2016 at 12:37 AM, Konstantin Khlebnikov <koct9i@gmail.com> wrote:
> On Thu, Jan 28, 2016 at 12:17 AM, Matthew Wilcox
> <matthew.r.wilcox@intel.com> wrote:
>> From: Matthew Wilcox <willy@linux.intel.com>
>>
>> If the indirect_ptr bit is set on a slot, that indicates we need to
>> redo the lookup. Introduce a new function radix_tree_iter_retry()
>> which forces the loop to retry the lookup by setting 'slot' to NULL and
>> turning the iterator back to point at the problematic entry.
>>
>> This is a pretty rare problem to hit at the moment; the lookup has to
>> race with a grow of the radix tree from a height of 0. The consequences
>> of hitting this race are that gang lookup could return a pointer to a
>> radix_tree_node instead of a pointer to whatever the user had inserted
>> in the tree.
>>
>> Fixes: cebbd29e1c2f ("radix-tree: rewrite gang lookup using iterator")
>> Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
>> Cc: stable@vger.kernel.org
>> ---
>> include/linux/radix-tree.h | 16 ++++++++++++++++
>> lib/radix-tree.c | 12 ++++++++++--
>> 2 files changed, 26 insertions(+), 2 deletions(-)
>>
>> diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
>> index f9a3da5bf892..db0ed595749b 100644
>> --- a/include/linux/radix-tree.h
>> +++ b/include/linux/radix-tree.h
>> @@ -387,6 +387,22 @@ void **radix_tree_next_chunk(struct radix_tree_root *root,
>> struct radix_tree_iter *iter, unsigned flags);
>>
>> /**
>> + * radix_tree_iter_retry - retry this chunk of the iteration
>> + * @iter: iterator state
>> + *
>> + * If we iterate over a tree protected only by the RCU lock, a race
>> + * against deletion or creation may result in seeing a slot for which
>> + * radix_tree_deref_retry() returns true. If so, call this function
>> + * and continue the iteration.
>> + */
>> +static inline __must_check
>> +void **radix_tree_iter_retry(struct radix_tree_iter *iter)
>> +{
>> + iter->next_index = iter->index;
>> + return NULL;
>> +}
>> +
>> +/**
>> * radix_tree_chunk_size - get current chunk size
>> *
>> * @iter: pointer to radix tree iterator
>> diff --git a/lib/radix-tree.c b/lib/radix-tree.c
>> index a25f635dcc56..65422ac17114 100644
>> --- a/lib/radix-tree.c
>> +++ b/lib/radix-tree.c
>> @@ -1105,9 +1105,13 @@ radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
>> return 0;
>>
>> radix_tree_for_each_slot(slot, root, &iter, first_index) {
>> - results[ret] = indirect_to_ptr(rcu_dereference_raw(*slot));
>> + results[ret] = rcu_dereference_raw(*slot);
>> if (!results[ret])
>> continue;
>> + if (radix_tree_is_indirect_ptr(results[ret])) {
>> + slot = radix_tree_iter_retry(&iter);
>> + continue;
>> + }
>> if (++ret == max_items)
>> break;
>> }
>
> Looks like your fix doesn't work.
>
> After radix_tree_iter_retry: radix_tree_for_each_slot will call
> radix_tree_next_slot which isn't safe to call for NULL slot.
>
> #define radix_tree_for_each_slot(slot, root, iter, start) \
> for (slot = radix_tree_iter_init(iter, start) ; \
> slot || (slot = radix_tree_next_chunk(root, iter, 0)) ; \
> slot = radix_tree_next_slot(slot, iter, 0))
>
> tagged iterator works becase restart happens only at root - tags
> filled with single bit.
>
> quick (untested) fix for that
>
> --- a/include/linux/radix-tree.h
> +++ b/include/linux/radix-tree.h
> @@ -457,9 +457,9 @@ radix_tree_next_slot(void **slot, struct
> radix_tree_iter *iter, unsigned flags)
> return slot + offset + 1;
> }
> } else {
> - unsigned size = radix_tree_chunk_size(iter) - 1;
> + int size = radix_tree_chunk_size(iter) - 1;
>
> - while (size--) {
> + while (size-- > 0) {
> slot++;
> iter->index++;
> if (likely(*slot))
>
>
Yep. Kernel crashes. Test in attachment.
fix: https://lkml.kernel.org/r/145457528789.31321.4441662473067711123.stgit@zurg
>> @@ -1184,9 +1188,13 @@ radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
>> return 0;
>>
>> radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) {
>> - results[ret] = indirect_to_ptr(rcu_dereference_raw(*slot));
>> + results[ret] = rcu_dereference_raw(*slot);
>> if (!results[ret])
>> continue;
>> + if (radix_tree_is_indirect_ptr(results[ret])) {
>> + slot = radix_tree_iter_retry(&iter);
>> + continue;
>> + }
>> if (++ret == max_items)
>> break;
>> }
>> --
>> 2.7.0.rc3
>>
>> --
>> 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>
[toc] | [prev] | [next] | [standalone]
| From | Matthew Wilcox <matthew.r.wilcox@intel.com> |
|---|---|
| Date | 2016-01-27 22:20 +0100 |
| Subject | [PATCH 4/5] mm: Use radix_tree_iter_retry() |
| Message-ID | <qVFFr-1hk-77@gated-at.bofh.it> |
| In reply to | #1319875 |
From: Matthew Wilcox <willy@linux.intel.com>
Instead of a 'goto restart', we can now use radix_tree_iter_retry()
to restart from our current position. This will make a difference
when there are more ways to happen across an indirect pointer. And it
eliminates some confusing gotos.
Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
---
mm/filemap.c | 53 +++++++++++++++++------------------------------------
mm/shmem.c | 18 ++++++++++++------
2 files changed, 29 insertions(+), 42 deletions(-)
diff --git a/mm/filemap.c b/mm/filemap.c
index 7705dac561ba..e0c4b905fe1c 100644
--- a/mm/filemap.c
+++ b/mm/filemap.c
@@ -1245,7 +1245,6 @@ unsigned find_get_entries(struct address_space *mapping,
return 0;
rcu_read_lock();
-restart:
radix_tree_for_each_slot(slot, &mapping->page_tree, &iter, start) {
struct page *page;
repeat:
@@ -1253,8 +1252,10 @@ repeat:
if (unlikely(!page))
continue;
if (radix_tree_exception(page)) {
- if (radix_tree_deref_retry(page))
- goto restart;
+ if (radix_tree_deref_retry(page)) {
+ slot = radix_tree_iter_retry(&iter);
+ continue;
+ }
/*
* A shadow entry of a recently evicted page, a swap
* entry from shmem/tmpfs or a DAX entry. Return it
@@ -1307,7 +1308,6 @@ unsigned find_get_pages(struct address_space *mapping, pgoff_t start,
return 0;
rcu_read_lock();
-restart:
radix_tree_for_each_slot(slot, &mapping->page_tree, &iter, start) {
struct page *page;
repeat:
@@ -1317,13 +1317,8 @@ repeat:
if (radix_tree_exception(page)) {
if (radix_tree_deref_retry(page)) {
- /*
- * Transient condition which can only trigger
- * when entry at index 0 moves out of or back
- * to root: none yet gotten, safe to restart.
- */
- WARN_ON(iter.index);
- goto restart;
+ slot = radix_tree_iter_retry(&iter);
+ continue;
}
/*
* A shadow entry of a recently evicted page,
@@ -1374,7 +1369,6 @@ unsigned find_get_pages_contig(struct address_space *mapping, pgoff_t index,
return 0;
rcu_read_lock();
-restart:
radix_tree_for_each_contig(slot, &mapping->page_tree, &iter, index) {
struct page *page;
repeat:
@@ -1385,12 +1379,8 @@ repeat:
if (radix_tree_exception(page)) {
if (radix_tree_deref_retry(page)) {
- /*
- * Transient condition which can only trigger
- * when entry at index 0 moves out of or back
- * to root: none yet gotten, safe to restart.
- */
- goto restart;
+ slot = radix_tree_iter_retry(&iter);
+ continue;
}
/*
* A shadow entry of a recently evicted page,
@@ -1450,7 +1440,6 @@ unsigned find_get_pages_tag(struct address_space *mapping, pgoff_t *index,
return 0;
rcu_read_lock();
-restart:
radix_tree_for_each_tagged(slot, &mapping->page_tree,
&iter, *index, tag) {
struct page *page;
@@ -1461,12 +1450,8 @@ repeat:
if (radix_tree_exception(page)) {
if (radix_tree_deref_retry(page)) {
- /*
- * Transient condition which can only trigger
- * when entry at index 0 moves out of or back
- * to root: none yet gotten, safe to restart.
- */
- goto restart;
+ slot = radix_tree_iter_retry(&iter);
+ continue;
}
/*
* A shadow entry of a recently evicted page.
@@ -1529,7 +1514,6 @@ unsigned find_get_entries_tag(struct address_space *mapping, pgoff_t start,
return 0;
rcu_read_lock();
-restart:
radix_tree_for_each_tagged(slot, &mapping->page_tree,
&iter, start, tag) {
struct page *page;
@@ -1539,12 +1523,8 @@ repeat:
continue;
if (radix_tree_exception(page)) {
if (radix_tree_deref_retry(page)) {
- /*
- * Transient condition which can only trigger
- * when entry at index 0 moves out of or back
- * to root: none yet gotten, safe to restart.
- */
- goto restart;
+ slot = radix_tree_iter_retry(&iter);
+ continue;
}
/*
@@ -2151,10 +2131,11 @@ repeat:
if (unlikely(!page))
goto next;
if (radix_tree_exception(page)) {
- if (radix_tree_deref_retry(page))
- break;
- else
- goto next;
+ if (radix_tree_deref_retry(page)) {
+ slot = radix_tree_iter_retry(&iter);
+ continue;
+ }
+ goto next;
}
if (!page_cache_get_speculative(page))
diff --git a/mm/shmem.c b/mm/shmem.c
index fa2ceb2d2655..6ec14b70d82d 100644
--- a/mm/shmem.c
+++ b/mm/shmem.c
@@ -388,8 +388,10 @@ restart:
* don't need to reset the counter, nor do we risk infinite
* restarts.
*/
- if (radix_tree_deref_retry(page))
- goto restart;
+ if (radix_tree_deref_retry(page)) {
+ slot = radix_tree_iter_retry(&iter);
+ continue;
+ }
if (radix_tree_exceptional_entry(page))
swapped++;
@@ -1952,8 +1954,10 @@ restart:
radix_tree_for_each_slot(slot, &mapping->page_tree, &iter, start) {
page = radix_tree_deref_slot(slot);
if (!page || radix_tree_exception(page)) {
- if (radix_tree_deref_retry(page))
- goto restart;
+ if (radix_tree_deref_retry(page)) {
+ slot = radix_tree_iter_retry(&iter);
+ continue;
+ }
} else if (page_count(page) - page_mapcount(page) > 1) {
spin_lock_irq(&mapping->tree_lock);
radix_tree_tag_set(&mapping->page_tree, iter.index,
@@ -2007,8 +2011,10 @@ restart:
page = radix_tree_deref_slot(slot);
if (radix_tree_exception(page)) {
- if (radix_tree_deref_retry(page))
- goto restart;
+ if (radix_tree_deref_retry(page)) {
+ slot = radix_tree_iter_retry(&iter);
+ continue;
+ }
page = NULL;
}
--
2.7.0.rc3
[toc] | [prev] | [next] | [standalone]
| From | Vlastimil Babka <vbabka@suse.cz> |
|---|---|
| Date | 2016-01-29 15:50 +0100 |
| Subject | Re: [PATCH 4/5] mm: Use radix_tree_iter_retry() |
| Message-ID | <qWix5-4ym-25@gated-at.bofh.it> |
| In reply to | #1319883 |
On 01/27/2016 10:17 PM, Matthew Wilcox wrote:
> From: Matthew Wilcox <willy@linux.intel.com>
>
> Instead of a 'goto restart', we can now use radix_tree_iter_retry()
> to restart from our current position. This will make a difference
> when there are more ways to happen across an indirect pointer. And it
> eliminates some confusing gotos.
>
> Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
[...]
> diff --git a/mm/shmem.c b/mm/shmem.c
> index fa2ceb2d2655..6ec14b70d82d 100644
> --- a/mm/shmem.c
> +++ b/mm/shmem.c
> @@ -388,8 +388,10 @@ restart:
> * don't need to reset the counter, nor do we risk infinite
> * restarts.
> */
> - if (radix_tree_deref_retry(page))
> - goto restart;
> + if (radix_tree_deref_retry(page)) {
> + slot = radix_tree_iter_retry(&iter);
> + continue;
> + }
>
> if (radix_tree_exceptional_entry(page))
> swapped++;
This should be applied on top. There are no restarts anymore.
----8<----
From 3b0bdd370b57fb6d83b213e140cd1fb0e8962af8 Mon Sep 17 00:00:00 2001
From: Vlastimil Babka <vbabka@suse.cz>
Date: Fri, 29 Jan 2016 15:41:31 +0100
Subject: [PATCH] mm: Use radix_tree_iter_retry()-fix
Remove now-obsolete-and-misleading comment.
Signed-off-by: Vlastimil Babka <vbabka@suse.cz>
---
mm/shmem.c | 5 -----
1 file changed, 5 deletions(-)
diff --git a/mm/shmem.c b/mm/shmem.c
index 8f89abd4eaee..4d758938340c 100644
--- a/mm/shmem.c
+++ b/mm/shmem.c
@@ -382,11 +382,6 @@ unsigned long shmem_partial_swap_usage(struct address_space *mapping,
page = radix_tree_deref_slot(slot);
- /*
- * This should only be possible to happen at index 0, so we
- * don't need to reset the counter, nor do we risk infinite
- * restarts.
- */
if (radix_tree_deref_retry(page)) {
slot = radix_tree_iter_retry(&iter);
continue;
--
2.7.0
[toc] | [prev] | [next] | [standalone]
| From | Matthew Wilcox <willy@linux.intel.com> |
|---|---|
| Date | 2016-01-29 16:00 +0100 |
| Subject | Re: [PATCH 4/5] mm: Use radix_tree_iter_retry() |
| Message-ID | <qWiGK-4DM-9@gated-at.bofh.it> |
| In reply to | #1321804 |
On Fri, Jan 29, 2016 at 03:45:59PM +0100, Vlastimil Babka wrote:
> This should be applied on top. There are no restarts anymore.
Quite right. Sorry I missed the comment.
Acked-by: Matthwe Wilcox <willy@linux.intel.com>
> ----8<----
> >From 3b0bdd370b57fb6d83b213e140cd1fb0e8962af8 Mon Sep 17 00:00:00 2001
> From: Vlastimil Babka <vbabka@suse.cz>
> Date: Fri, 29 Jan 2016 15:41:31 +0100
> Subject: [PATCH] mm: Use radix_tree_iter_retry()-fix
>
> Remove now-obsolete-and-misleading comment.
>
> Signed-off-by: Vlastimil Babka <vbabka@suse.cz>
> ---
> mm/shmem.c | 5 -----
> 1 file changed, 5 deletions(-)
>
> diff --git a/mm/shmem.c b/mm/shmem.c
> index 8f89abd4eaee..4d758938340c 100644
> --- a/mm/shmem.c
> +++ b/mm/shmem.c
> @@ -382,11 +382,6 @@ unsigned long shmem_partial_swap_usage(struct address_space *mapping,
>
> page = radix_tree_deref_slot(slot);
>
> - /*
> - * This should only be possible to happen at index 0, so we
> - * don't need to reset the counter, nor do we risk infinite
> - * restarts.
> - */
> if (radix_tree_deref_retry(page)) {
> slot = radix_tree_iter_retry(&iter);
> continue;
> --
> 2.7.0
>
>
[toc] | [prev] | [next] | [standalone]
| From | Konstantin Khlebnikov <koct9i@gmail.com> |
|---|---|
| Date | 2016-01-28 08:20 +0100 |
| Message-ID | <qVP22-8nH-7@gated-at.bofh.it> |
| In reply to | #1319875 |
On Thu, Jan 28, 2016 at 12:17 AM, Matthew Wilcox <matthew.r.wilcox@intel.com> wrote: > From: Matthew Wilcox <willy@linux.intel.com> > > The first two patches here are bugfixes, and I would like to see them > make their way into stable ASAP since they can lead to data corruption > (very low probabilty). > > The last three patches do not qualify as bugfixes. They simply improve > the standard pattern used to do radix tree iterations by removing the > 'goto restart' part. Partially this is because this is an ugly & > confusing goto, and partially because with multi-order entries in the > tree, it'll be more likely that we'll see an indirect_ptr bit, and > it's more efficient to kep going from the point of the iteration we're > currently in than restart from the beginning each time. Ack whole set. I think we should go deeper in hide dereference/retry inside iterator. Something like radix_tree_for_each_data(data, slot, root, iter, start). I'll prepare patch for that. > > Matthew Wilcox (5): > radix-tree: Fix race in gang lookup > hwspinlock: Fix race between radix tree insertion and lookup > btrfs: Use radix_tree_iter_retry() > mm: Use radix_tree_iter_retry() > radix-tree,shmem: Introduce radix_tree_iter_next() > > drivers/hwspinlock/hwspinlock_core.c | 4 +++ > fs/btrfs/tests/btrfs-tests.c | 3 +- > include/linux/radix-tree.h | 31 +++++++++++++++++++++ > lib/radix-tree.c | 12 ++++++-- > mm/filemap.c | 53 ++++++++++++------------------------ > mm/shmem.c | 30 ++++++++++---------- > 6 files changed, 78 insertions(+), 55 deletions(-) > > -- > 2.7.0.rc3 > > -- > 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>
[toc] | [prev] | [next] | [standalone]
| From | Konstantin Khlebnikov <koct9i@gmail.com> |
|---|---|
| Date | 2016-02-03 07:30 +0100 |
| Message-ID | <qXZ6W-6G0-27@gated-at.bofh.it> |
| In reply to | #1320356 |
On Thu, Jan 28, 2016 at 10:17 AM, Konstantin Khlebnikov <koct9i@gmail.com> wrote: > On Thu, Jan 28, 2016 at 12:17 AM, Matthew Wilcox > <matthew.r.wilcox@intel.com> wrote: >> From: Matthew Wilcox <willy@linux.intel.com> >> >> The first two patches here are bugfixes, and I would like to see them >> make their way into stable ASAP since they can lead to data corruption >> (very low probabilty). >> >> The last three patches do not qualify as bugfixes. They simply improve >> the standard pattern used to do radix tree iterations by removing the >> 'goto restart' part. Partially this is because this is an ugly & >> confusing goto, and partially because with multi-order entries in the >> tree, it'll be more likely that we'll see an indirect_ptr bit, and >> it's more efficient to kep going from the point of the iteration we're >> currently in than restart from the beginning each time. > > Ack whole set. > > I think we should go deeper in hide dereference/retry inside iterator. > Something like radix_tree_for_each_data(data, slot, root, iter, start). > I'll prepare patch for that. After second thought: there'ra not so many users for new sugar. This scheme with radix_tree_deref_retry - radix_tree_iter_retry complicated but fine. > >> >> Matthew Wilcox (5): >> radix-tree: Fix race in gang lookup >> hwspinlock: Fix race between radix tree insertion and lookup >> btrfs: Use radix_tree_iter_retry() >> mm: Use radix_tree_iter_retry() >> radix-tree,shmem: Introduce radix_tree_iter_next() >> >> drivers/hwspinlock/hwspinlock_core.c | 4 +++ >> fs/btrfs/tests/btrfs-tests.c | 3 +- >> include/linux/radix-tree.h | 31 +++++++++++++++++++++ >> lib/radix-tree.c | 12 ++++++-- >> mm/filemap.c | 53 ++++++++++++------------------------ >> mm/shmem.c | 30 ++++++++++---------- >> 6 files changed, 78 insertions(+), 55 deletions(-) >> >> -- >> 2.7.0.rc3 >> >> -- >> 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>
[toc] | [prev] | [standalone]
Back to top | Article view | linux.kernel
csiph-web