From: Konstantin Khlebnikov <koct9i@gmail.com>
To: Matthew Wilcox <mawilcox@linuxonhyperv.com>
Cc: Linux Kernel Mailing List <linux-kernel@vger.kernel.org>,
Andrew Morton <akpm@linux-foundation.org>,
Ross Zwisler <ross.zwisler@linux.intel.com>,
linux-fsdevel <linux-fsdevel@vger.kernel.org>,
Matthew Wilcox <mawilcox@microsoft.com>,
"linux-mm@kvack.org" <linux-mm@kvack.org>,
"Kirill A . Shutemov" <kirill.shutemov@linux.intel.com>
Subject: Re: [PATCH 20/29] radix tree: Improve multiorder iterators
Date: Fri, 18 Nov 2016 14:47:35 +0300 [thread overview]
Message-ID: <CALYGNiN++jFZZwvShjD4PDV=cZczVOs+K-ib-ZL=M+v2XU_aYQ@mail.gmail.com> (raw)
In-Reply-To: <1479341856-30320-59-git-send-email-mawilcox@linuxonhyperv.com>
On Thu, Nov 17, 2016 at 3:17 AM, Matthew Wilcox
<mawilcox@linuxonhyperv.com> wrote:
> From: Matthew Wilcox <mawilcox@microsoft.com>
This code still looks overengineered for me.
>
> This fixes several interlinked problems with the iterators in the
> presence of multiorder entries.
>
> 1. radix_tree_iter_next() would only advance by one slot, which would
> result in the iterators returning the same entry more than once if there
> were sibling entries.
Is this a problem? Do we have users who cannot evalate length of entry
by looking into it head?
>
> 2. radix_tree_next_slot() could return an internal pointer instead of
> a user pointer if a tagged multiorder entry was immediately followed by
> an entry of lower order.
>
> 3. radix_tree_next_slot() expanded to a lot more code than it used to
> when multiorder support was compiled in. And I wasn't comfortable with
> entry_to_node() being in a header file.
>
> Fixing radix_tree_iter_next() for the presence of sibling entries
> necessarily involves examining the contents of the radix tree, so we now
> need to pass 'slot' to radix_tree_iter_next(), and we need to change the
> calling convention so it is called *before* dropping the lock which
> protects the tree. Fortunately, unconverted code won't compile.
>
> radix_tree_next_slot() becomes closer to how it looked before multiorder
> support was introduced. It only checks to see if the next entry in the
> chunk is a sibling entry or a pointer to a node; this should be rare
> enough that handling this case out of line is not a performance impact
> (and such impact is amortised by the fact that the entry we just
> processed was a multiorder entry). Also, radix_tree_next_slot() used
> to force a new chunk lookup for untagged entries, which is more
> expensive than the out of line sibling entry
>
> Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
> ---
> fs/btrfs/tests/btrfs-tests.c | 2 +-
> include/linux/radix-tree.h | 63 ++++++++------------
> lib/radix-tree.c | 94 ++++++++++++++++++++++++++++++
> mm/khugepaged.c | 2 +-
> mm/shmem.c | 6 +-
> tools/testing/radix-tree/iteration_check.c | 4 +-
> tools/testing/radix-tree/multiorder.c | 12 ++++
> tools/testing/radix-tree/regression3.c | 6 +-
> tools/testing/radix-tree/test.h | 1 +
> 9 files changed, 142 insertions(+), 48 deletions(-)
>
> diff --git a/fs/btrfs/tests/btrfs-tests.c b/fs/btrfs/tests/btrfs-tests.c
> index 73076a0..6d3457a 100644
> --- a/fs/btrfs/tests/btrfs-tests.c
> +++ b/fs/btrfs/tests/btrfs-tests.c
> @@ -162,7 +162,7 @@ void btrfs_free_dummy_fs_info(struct btrfs_fs_info *fs_info)
> slot = radix_tree_iter_retry(&iter);
> continue;
> }
> - slot = radix_tree_iter_next(&iter);
> + slot = radix_tree_iter_next(slot, &iter);
> spin_unlock(&fs_info->buffer_lock);
> free_extent_buffer_stale(eb);
> spin_lock(&fs_info->buffer_lock);
> diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
> index 66fb8c0..36c6175 100644
> --- a/include/linux/radix-tree.h
> +++ b/include/linux/radix-tree.h
> @@ -424,15 +424,10 @@ __radix_tree_iter_add(struct radix_tree_iter *iter, unsigned long slots)
> *
> * If the iterator needs to release then reacquire a lock, the chunk may
> * have been invalidated by an insertion or deletion. Call this function
> - * to continue the iteration from the next index.
> + * before releasing the lock to continue the iteration from the next index.
> */
> -static inline __must_check
> -void **radix_tree_iter_next(struct radix_tree_iter *iter)
> -{
> - iter->next_index = __radix_tree_iter_add(iter, 1);
> - iter->tags = 0;
> - return NULL;
> -}
> +void **__must_check radix_tree_iter_next(void **slot,
> + struct radix_tree_iter *iter);
>
> /**
> * radix_tree_chunk_size - get current chunk size
> @@ -446,10 +441,17 @@ radix_tree_chunk_size(struct radix_tree_iter *iter)
> return (iter->next_index - iter->index) >> iter_shift(iter);
> }
>
> -static inline struct radix_tree_node *entry_to_node(void *ptr)
> +#ifdef CONFIG_RADIX_TREE_MULTIORDER
> +void ** __radix_tree_next_slot(void **slot, struct radix_tree_iter *iter,
> + unsigned flags);
> +#else
> +/* Can't happen without sibling entries, but the compiler can't tell that */
> +static inline void ** __radix_tree_next_slot(void **slot,
> + struct radix_tree_iter *iter, unsigned flags)
> {
> - return (void *)((unsigned long)ptr & ~RADIX_TREE_INTERNAL_NODE);
> + return slot;
> }
> +#endif
>
> /**
> * radix_tree_next_slot - find next slot in chunk
> @@ -474,51 +476,31 @@ static __always_inline void **
> radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags)
> {
> if (flags & RADIX_TREE_ITER_TAGGED) {
> - void *canon = slot;
> -
> iter->tags >>= 1;
> if (unlikely(!iter->tags))
> return NULL;
> - while (IS_ENABLED(CONFIG_RADIX_TREE_MULTIORDER) &&
> - radix_tree_is_internal_node(slot[1])) {
> - if (entry_to_node(slot[1]) == canon) {
> - iter->tags >>= 1;
> - iter->index = __radix_tree_iter_add(iter, 1);
> - slot++;
> - continue;
> - }
> - iter->next_index = __radix_tree_iter_add(iter, 1);
> - return NULL;
> - }
> if (likely(iter->tags & 1ul)) {
> iter->index = __radix_tree_iter_add(iter, 1);
> - return slot + 1;
> + slot++;
> + goto found;
> }
> if (!(flags & RADIX_TREE_ITER_CONTIG)) {
> unsigned offset = __ffs(iter->tags);
>
> - iter->tags >>= offset;
> - iter->index = __radix_tree_iter_add(iter, offset + 1);
> - return slot + offset + 1;
> + iter->tags >>= offset++;
> + iter->index = __radix_tree_iter_add(iter, offset);
> + slot += offset;
> + goto found;
> }
> } else {
> long count = radix_tree_chunk_size(iter);
> - void *canon = slot;
>
> while (--count > 0) {
> slot++;
> iter->index = __radix_tree_iter_add(iter, 1);
>
> - if (IS_ENABLED(CONFIG_RADIX_TREE_MULTIORDER) &&
> - radix_tree_is_internal_node(*slot)) {
> - if (entry_to_node(*slot) == canon)
> - continue;
> - iter->next_index = iter->index;
> - break;
> - }
> -
> if (likely(*slot))
> - return slot;
> + goto found;
> if (flags & RADIX_TREE_ITER_CONTIG) {
> /* forbid switching to the next chunk */
> iter->next_index = 0;
> @@ -527,6 +509,11 @@ radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags)
> }
> }
> return NULL;
> +
> + found:
> + if (unlikely(radix_tree_is_internal_node(*slot)))
> + return __radix_tree_next_slot(slot, iter, flags);
> + return slot;
> }
>
> /**
> @@ -577,6 +564,6 @@ radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags)
> slot || (slot = radix_tree_next_chunk(root, iter, \
> RADIX_TREE_ITER_TAGGED | tag)) ; \
> slot = radix_tree_next_slot(slot, iter, \
> - RADIX_TREE_ITER_TAGGED))
> + RADIX_TREE_ITER_TAGGED | tag))
>
> #endif /* _LINUX_RADIX_TREE_H */
> diff --git a/lib/radix-tree.c b/lib/radix-tree.c
> index 09c5f1d..27b53ef 100644
> --- a/lib/radix-tree.c
> +++ b/lib/radix-tree.c
> @@ -69,6 +69,11 @@ struct radix_tree_preload {
> };
> static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, };
>
> +static inline struct radix_tree_node *entry_to_node(void *ptr)
> +{
> + return (void *)((unsigned long)ptr & ~RADIX_TREE_INTERNAL_NODE);
> +}
> +
> static inline void *node_to_entry(void *ptr)
> {
> return (void *)((unsigned long)ptr | RADIX_TREE_INTERNAL_NODE);
> @@ -1138,6 +1143,95 @@ static inline void __set_iter_shift(struct radix_tree_iter *iter,
> #endif
> }
>
> +static void ** __radix_tree_iter_next(struct radix_tree_node **nodep,
> + void **slot, struct radix_tree_iter *iter)
> +{
> + void *sib = node_to_entry(slot - 1);
> +
> + while (iter->index < iter->next_index) {
> + *nodep = rcu_dereference_raw(*slot);
> + if (*nodep && *nodep != sib)
> + return slot;
> + slot++;
> + iter->index = __radix_tree_iter_add(iter, 1);
> + iter->tags >>= 1;
> + }
> +
> + *nodep = NULL;
> + return NULL;
> +}
> +
> +#ifdef CONFIG_RADIX_TREE_MULTIORDER
> +void ** __radix_tree_next_slot(void **slot, struct radix_tree_iter *iter,
> + unsigned flags)
> +{
> + unsigned tag = flags & RADIX_TREE_ITER_TAG_MASK;
> + struct radix_tree_node *node = rcu_dereference_raw(*slot);
> +
> + slot = __radix_tree_iter_next(&node, slot, iter);
> +
> + while (radix_tree_is_internal_node(node)) {
> + unsigned offset;
> +
> + if (node == RADIX_TREE_RETRY)
> + return slot;
> + node = entry_to_node(node);
> +
> + if (flags & RADIX_TREE_ITER_TAGGED) {
> + unsigned tag_long, tag_bit;
> + offset = radix_tree_find_next_bit(node, tag, 0);
> + if (offset == RADIX_TREE_MAP_SIZE)
> + return NULL;
> + slot = &node->slots[offset];
> +
> + tag_long = offset / BITS_PER_LONG;
> + tag_bit = offset % BITS_PER_LONG;
> + iter->tags = node->tags[tag][tag_long] >> tag_bit;
> + BUG_ON(iter->tags >= (RADIX_TREE_MAP_SIZE * 2));
> + node = rcu_dereference_raw(*slot);
> + } else {
> + offset = 0;
> + slot = &node->slots[0];
> + for (;;) {
> + node = rcu_dereference_raw(*slot);
> + if (node)
> + break;
> + slot++;
> + offset++;
> + if (offset == RADIX_TREE_MAP_SIZE)
> + return NULL;
> + }
> + }
> + if ((flags & RADIX_TREE_ITER_CONTIG) && (offset > 0))
> + goto none;
> + iter->shift -= RADIX_TREE_MAP_SHIFT;
> + iter->index = __radix_tree_iter_add(iter, offset);
> + iter->next_index = (iter->index | shift_maxindex(iter->shift)) +
> + 1;
> + }
> +
> + return slot;
> + none:
> + iter->next_index = 0;
> + return NULL;
> +}
> +EXPORT_SYMBOL(__radix_tree_next_slot);
> +#endif
> +
> +void **radix_tree_iter_next(void **slot, struct radix_tree_iter *iter)
> +{
> + struct radix_tree_node *node;
> +
> + slot++;
> + iter->index = __radix_tree_iter_add(iter, 1);
> + node = rcu_dereference_raw(*slot);
> + __radix_tree_iter_next(&node, slot, iter);
> + iter->next_index = iter->index;
> + iter->tags = 0;
> + return NULL;
> +}
> +EXPORT_SYMBOL(radix_tree_iter_next);
> +
> /**
> * radix_tree_next_chunk - find next chunk of slots for iteration
> *
> diff --git a/mm/khugepaged.c b/mm/khugepaged.c
> index 728d779..46155d1 100644
> --- a/mm/khugepaged.c
> +++ b/mm/khugepaged.c
> @@ -1614,8 +1614,8 @@ static void khugepaged_scan_shmem(struct mm_struct *mm,
> present++;
>
> if (need_resched()) {
> + slot = radix_tree_iter_next(slot, &iter);
> cond_resched_rcu();
> - slot = radix_tree_iter_next(&iter);
> }
> }
> rcu_read_unlock();
> diff --git a/mm/shmem.c b/mm/shmem.c
> index 166ebf5..0b3fe33 100644
> --- a/mm/shmem.c
> +++ b/mm/shmem.c
> @@ -658,8 +658,8 @@ unsigned long shmem_partial_swap_usage(struct address_space *mapping,
> swapped++;
>
> if (need_resched()) {
> + slot = radix_tree_iter_next(slot, &iter);
> cond_resched_rcu();
> - slot = radix_tree_iter_next(&iter);
> }
> }
>
> @@ -2434,8 +2434,8 @@ static void shmem_tag_pins(struct address_space *mapping)
> }
>
> if (need_resched()) {
> + slot = radix_tree_iter_next(slot, &iter);
> cond_resched_rcu();
> - slot = radix_tree_iter_next(&iter);
> }
> }
> rcu_read_unlock();
> @@ -2504,8 +2504,8 @@ static int shmem_wait_for_pins(struct address_space *mapping)
> spin_unlock_irq(&mapping->tree_lock);
> continue_resched:
> if (need_resched()) {
> + slot = radix_tree_iter_next(slot, &iter);
> cond_resched_rcu();
> - slot = radix_tree_iter_next(&iter);
> }
> }
> rcu_read_unlock();
> diff --git a/tools/testing/radix-tree/iteration_check.c b/tools/testing/radix-tree/iteration_check.c
> index df71cb8..6eca4c2 100644
> --- a/tools/testing/radix-tree/iteration_check.c
> +++ b/tools/testing/radix-tree/iteration_check.c
> @@ -79,7 +79,7 @@ static void *tagged_iteration_fn(void *arg)
> }
>
> if (rand_r(&seeds[0]) % 50 == 0) {
> - slot = radix_tree_iter_next(&iter);
> + slot = radix_tree_iter_next(slot, &iter);
> rcu_read_unlock();
> rcu_barrier();
> rcu_read_lock();
> @@ -127,7 +127,7 @@ static void *untagged_iteration_fn(void *arg)
> }
>
> if (rand_r(&seeds[1]) % 50 == 0) {
> - slot = radix_tree_iter_next(&iter);
> + slot = radix_tree_iter_next(slot, &iter);
> rcu_read_unlock();
> rcu_barrier();
> rcu_read_lock();
> diff --git a/tools/testing/radix-tree/multiorder.c b/tools/testing/radix-tree/multiorder.c
> index 25e0463..588209a 100644
> --- a/tools/testing/radix-tree/multiorder.c
> +++ b/tools/testing/radix-tree/multiorder.c
> @@ -232,10 +232,14 @@ void multiorder_iteration(void)
> int height = order[i] / RADIX_TREE_MAP_SHIFT;
> int shift = height * RADIX_TREE_MAP_SHIFT;
> int mask = (1 << order[i]) - 1;
> + struct item *item = *slot;
>
> assert(iter.index >= (index[i] &~ mask));
> assert(iter.index <= (index[i] | mask));
> assert(iter.shift == shift);
> + assert(!radix_tree_is_internal_node(item));
> + assert(item->index >= (index[i] &~ mask));
> + assert(item->index <= (index[i] | mask));
> i++;
> }
> }
> @@ -279,12 +283,16 @@ void multiorder_tagged_iteration(void)
> }
>
> radix_tree_for_each_tagged(slot, &tree, &iter, j, 1) {
> + struct item *item = *slot;
> for (k = i; index[k] < tag_index[i]; k++)
> ;
> mask = (1 << order[k]) - 1;
>
> assert(iter.index >= (tag_index[i] &~ mask));
> assert(iter.index <= (tag_index[i] | mask));
> + assert(!radix_tree_is_internal_node(item));
> + assert(item->index >= (tag_index[i] &~ mask));
> + assert(item->index <= (tag_index[i] | mask));
> i++;
> }
> }
> @@ -303,12 +311,16 @@ void multiorder_tagged_iteration(void)
> }
>
> radix_tree_for_each_tagged(slot, &tree, &iter, j, 2) {
> + struct item *item = *slot;
> for (k = i; index[k] < tag_index[i]; k++)
> ;
> mask = (1 << order[k]) - 1;
>
> assert(iter.index >= (tag_index[i] &~ mask));
> assert(iter.index <= (tag_index[i] | mask));
> + assert(!radix_tree_is_internal_node(item));
> + assert(item->index >= (tag_index[i] &~ mask));
> + assert(item->index <= (tag_index[i] | mask));
> i++;
> }
> }
> diff --git a/tools/testing/radix-tree/regression3.c b/tools/testing/radix-tree/regression3.c
> index 1f06ed7..4d28eeb 100644
> --- a/tools/testing/radix-tree/regression3.c
> +++ b/tools/testing/radix-tree/regression3.c
> @@ -88,7 +88,7 @@ void regression3_test(void)
> printf("slot %ld %p\n", iter.index, *slot);
> if (!iter.index) {
> printf("next at %ld\n", iter.index);
> - slot = radix_tree_iter_next(&iter);
> + slot = radix_tree_iter_next(slot, &iter);
> }
> }
>
> @@ -96,7 +96,7 @@ void regression3_test(void)
> printf("contig %ld %p\n", iter.index, *slot);
> if (!iter.index) {
> printf("next at %ld\n", iter.index);
> - slot = radix_tree_iter_next(&iter);
> + slot = radix_tree_iter_next(slot, &iter);
> }
> }
>
> @@ -106,7 +106,7 @@ void regression3_test(void)
> printf("tagged %ld %p\n", iter.index, *slot);
> if (!iter.index) {
> printf("next at %ld\n", iter.index);
> - slot = radix_tree_iter_next(&iter);
> + slot = radix_tree_iter_next(slot, &iter);
> }
> }
>
> diff --git a/tools/testing/radix-tree/test.h b/tools/testing/radix-tree/test.h
> index 33d2b6b..b678f13 100644
> --- a/tools/testing/radix-tree/test.h
> +++ b/tools/testing/radix-tree/test.h
> @@ -43,6 +43,7 @@ void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag);
> extern int nr_allocated;
>
> /* Normally private parts of lib/radix-tree.c */
> +struct radix_tree_node *entry_to_node(void *ptr);
> void radix_tree_dump(struct radix_tree_root *root);
> int root_tag_get(struct radix_tree_root *root, unsigned int tag);
> unsigned long node_maxindex(struct radix_tree_node *);
> --
> 2.10.2
>
> --
> 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>
WARNING: multiple messages have this Message-ID (diff)
From: Konstantin Khlebnikov <koct9i@gmail.com>
To: Matthew Wilcox <mawilcox@linuxonhyperv.com>
Cc: Linux Kernel Mailing List <linux-kernel@vger.kernel.org>,
Andrew Morton <akpm@linux-foundation.org>,
Ross Zwisler <ross.zwisler@linux.intel.com>,
linux-fsdevel <linux-fsdevel@vger.kernel.org>,
Matthew Wilcox <mawilcox@microsoft.com>,
"linux-mm@kvack.org" <linux-mm@kvack.org>,
"Kirill A . Shutemov" <kirill.shutemov@linux.intel.com>
Subject: Re: [PATCH 20/29] radix tree: Improve multiorder iterators
Date: Fri, 18 Nov 2016 14:47:35 +0300 [thread overview]
Message-ID: <CALYGNiN++jFZZwvShjD4PDV=cZczVOs+K-ib-ZL=M+v2XU_aYQ@mail.gmail.com> (raw)
In-Reply-To: <1479341856-30320-59-git-send-email-mawilcox@linuxonhyperv.com>
On Thu, Nov 17, 2016 at 3:17 AM, Matthew Wilcox
<mawilcox@linuxonhyperv.com> wrote:
> From: Matthew Wilcox <mawilcox@microsoft.com>
This code still looks overengineered for me.
>
> This fixes several interlinked problems with the iterators in the
> presence of multiorder entries.
>
> 1. radix_tree_iter_next() would only advance by one slot, which would
> result in the iterators returning the same entry more than once if there
> were sibling entries.
Is this a problem? Do we have users who cannot evalate length of entry
by looking into it head?
>
> 2. radix_tree_next_slot() could return an internal pointer instead of
> a user pointer if a tagged multiorder entry was immediately followed by
> an entry of lower order.
>
> 3. radix_tree_next_slot() expanded to a lot more code than it used to
> when multiorder support was compiled in. And I wasn't comfortable with
> entry_to_node() being in a header file.
>
> Fixing radix_tree_iter_next() for the presence of sibling entries
> necessarily involves examining the contents of the radix tree, so we now
> need to pass 'slot' to radix_tree_iter_next(), and we need to change the
> calling convention so it is called *before* dropping the lock which
> protects the tree. Fortunately, unconverted code won't compile.
>
> radix_tree_next_slot() becomes closer to how it looked before multiorder
> support was introduced. It only checks to see if the next entry in the
> chunk is a sibling entry or a pointer to a node; this should be rare
> enough that handling this case out of line is not a performance impact
> (and such impact is amortised by the fact that the entry we just
> processed was a multiorder entry). Also, radix_tree_next_slot() used
> to force a new chunk lookup for untagged entries, which is more
> expensive than the out of line sibling entry
>
> Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
> ---
> fs/btrfs/tests/btrfs-tests.c | 2 +-
> include/linux/radix-tree.h | 63 ++++++++------------
> lib/radix-tree.c | 94 ++++++++++++++++++++++++++++++
> mm/khugepaged.c | 2 +-
> mm/shmem.c | 6 +-
> tools/testing/radix-tree/iteration_check.c | 4 +-
> tools/testing/radix-tree/multiorder.c | 12 ++++
> tools/testing/radix-tree/regression3.c | 6 +-
> tools/testing/radix-tree/test.h | 1 +
> 9 files changed, 142 insertions(+), 48 deletions(-)
>
> diff --git a/fs/btrfs/tests/btrfs-tests.c b/fs/btrfs/tests/btrfs-tests.c
> index 73076a0..6d3457a 100644
> --- a/fs/btrfs/tests/btrfs-tests.c
> +++ b/fs/btrfs/tests/btrfs-tests.c
> @@ -162,7 +162,7 @@ void btrfs_free_dummy_fs_info(struct btrfs_fs_info *fs_info)
> slot = radix_tree_iter_retry(&iter);
> continue;
> }
> - slot = radix_tree_iter_next(&iter);
> + slot = radix_tree_iter_next(slot, &iter);
> spin_unlock(&fs_info->buffer_lock);
> free_extent_buffer_stale(eb);
> spin_lock(&fs_info->buffer_lock);
> diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
> index 66fb8c0..36c6175 100644
> --- a/include/linux/radix-tree.h
> +++ b/include/linux/radix-tree.h
> @@ -424,15 +424,10 @@ __radix_tree_iter_add(struct radix_tree_iter *iter, unsigned long slots)
> *
> * If the iterator needs to release then reacquire a lock, the chunk may
> * have been invalidated by an insertion or deletion. Call this function
> - * to continue the iteration from the next index.
> + * before releasing the lock to continue the iteration from the next index.
> */
> -static inline __must_check
> -void **radix_tree_iter_next(struct radix_tree_iter *iter)
> -{
> - iter->next_index = __radix_tree_iter_add(iter, 1);
> - iter->tags = 0;
> - return NULL;
> -}
> +void **__must_check radix_tree_iter_next(void **slot,
> + struct radix_tree_iter *iter);
>
> /**
> * radix_tree_chunk_size - get current chunk size
> @@ -446,10 +441,17 @@ radix_tree_chunk_size(struct radix_tree_iter *iter)
> return (iter->next_index - iter->index) >> iter_shift(iter);
> }
>
> -static inline struct radix_tree_node *entry_to_node(void *ptr)
> +#ifdef CONFIG_RADIX_TREE_MULTIORDER
> +void ** __radix_tree_next_slot(void **slot, struct radix_tree_iter *iter,
> + unsigned flags);
> +#else
> +/* Can't happen without sibling entries, but the compiler can't tell that */
> +static inline void ** __radix_tree_next_slot(void **slot,
> + struct radix_tree_iter *iter, unsigned flags)
> {
> - return (void *)((unsigned long)ptr & ~RADIX_TREE_INTERNAL_NODE);
> + return slot;
> }
> +#endif
>
> /**
> * radix_tree_next_slot - find next slot in chunk
> @@ -474,51 +476,31 @@ static __always_inline void **
> radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags)
> {
> if (flags & RADIX_TREE_ITER_TAGGED) {
> - void *canon = slot;
> -
> iter->tags >>= 1;
> if (unlikely(!iter->tags))
> return NULL;
> - while (IS_ENABLED(CONFIG_RADIX_TREE_MULTIORDER) &&
> - radix_tree_is_internal_node(slot[1])) {
> - if (entry_to_node(slot[1]) == canon) {
> - iter->tags >>= 1;
> - iter->index = __radix_tree_iter_add(iter, 1);
> - slot++;
> - continue;
> - }
> - iter->next_index = __radix_tree_iter_add(iter, 1);
> - return NULL;
> - }
> if (likely(iter->tags & 1ul)) {
> iter->index = __radix_tree_iter_add(iter, 1);
> - return slot + 1;
> + slot++;
> + goto found;
> }
> if (!(flags & RADIX_TREE_ITER_CONTIG)) {
> unsigned offset = __ffs(iter->tags);
>
> - iter->tags >>= offset;
> - iter->index = __radix_tree_iter_add(iter, offset + 1);
> - return slot + offset + 1;
> + iter->tags >>= offset++;
> + iter->index = __radix_tree_iter_add(iter, offset);
> + slot += offset;
> + goto found;
> }
> } else {
> long count = radix_tree_chunk_size(iter);
> - void *canon = slot;
>
> while (--count > 0) {
> slot++;
> iter->index = __radix_tree_iter_add(iter, 1);
>
> - if (IS_ENABLED(CONFIG_RADIX_TREE_MULTIORDER) &&
> - radix_tree_is_internal_node(*slot)) {
> - if (entry_to_node(*slot) == canon)
> - continue;
> - iter->next_index = iter->index;
> - break;
> - }
> -
> if (likely(*slot))
> - return slot;
> + goto found;
> if (flags & RADIX_TREE_ITER_CONTIG) {
> /* forbid switching to the next chunk */
> iter->next_index = 0;
> @@ -527,6 +509,11 @@ radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags)
> }
> }
> return NULL;
> +
> + found:
> + if (unlikely(radix_tree_is_internal_node(*slot)))
> + return __radix_tree_next_slot(slot, iter, flags);
> + return slot;
> }
>
> /**
> @@ -577,6 +564,6 @@ radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags)
> slot || (slot = radix_tree_next_chunk(root, iter, \
> RADIX_TREE_ITER_TAGGED | tag)) ; \
> slot = radix_tree_next_slot(slot, iter, \
> - RADIX_TREE_ITER_TAGGED))
> + RADIX_TREE_ITER_TAGGED | tag))
>
> #endif /* _LINUX_RADIX_TREE_H */
> diff --git a/lib/radix-tree.c b/lib/radix-tree.c
> index 09c5f1d..27b53ef 100644
> --- a/lib/radix-tree.c
> +++ b/lib/radix-tree.c
> @@ -69,6 +69,11 @@ struct radix_tree_preload {
> };
> static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, };
>
> +static inline struct radix_tree_node *entry_to_node(void *ptr)
> +{
> + return (void *)((unsigned long)ptr & ~RADIX_TREE_INTERNAL_NODE);
> +}
> +
> static inline void *node_to_entry(void *ptr)
> {
> return (void *)((unsigned long)ptr | RADIX_TREE_INTERNAL_NODE);
> @@ -1138,6 +1143,95 @@ static inline void __set_iter_shift(struct radix_tree_iter *iter,
> #endif
> }
>
> +static void ** __radix_tree_iter_next(struct radix_tree_node **nodep,
> + void **slot, struct radix_tree_iter *iter)
> +{
> + void *sib = node_to_entry(slot - 1);
> +
> + while (iter->index < iter->next_index) {
> + *nodep = rcu_dereference_raw(*slot);
> + if (*nodep && *nodep != sib)
> + return slot;
> + slot++;
> + iter->index = __radix_tree_iter_add(iter, 1);
> + iter->tags >>= 1;
> + }
> +
> + *nodep = NULL;
> + return NULL;
> +}
> +
> +#ifdef CONFIG_RADIX_TREE_MULTIORDER
> +void ** __radix_tree_next_slot(void **slot, struct radix_tree_iter *iter,
> + unsigned flags)
> +{
> + unsigned tag = flags & RADIX_TREE_ITER_TAG_MASK;
> + struct radix_tree_node *node = rcu_dereference_raw(*slot);
> +
> + slot = __radix_tree_iter_next(&node, slot, iter);
> +
> + while (radix_tree_is_internal_node(node)) {
> + unsigned offset;
> +
> + if (node == RADIX_TREE_RETRY)
> + return slot;
> + node = entry_to_node(node);
> +
> + if (flags & RADIX_TREE_ITER_TAGGED) {
> + unsigned tag_long, tag_bit;
> + offset = radix_tree_find_next_bit(node, tag, 0);
> + if (offset == RADIX_TREE_MAP_SIZE)
> + return NULL;
> + slot = &node->slots[offset];
> +
> + tag_long = offset / BITS_PER_LONG;
> + tag_bit = offset % BITS_PER_LONG;
> + iter->tags = node->tags[tag][tag_long] >> tag_bit;
> + BUG_ON(iter->tags >= (RADIX_TREE_MAP_SIZE * 2));
> + node = rcu_dereference_raw(*slot);
> + } else {
> + offset = 0;
> + slot = &node->slots[0];
> + for (;;) {
> + node = rcu_dereference_raw(*slot);
> + if (node)
> + break;
> + slot++;
> + offset++;
> + if (offset == RADIX_TREE_MAP_SIZE)
> + return NULL;
> + }
> + }
> + if ((flags & RADIX_TREE_ITER_CONTIG) && (offset > 0))
> + goto none;
> + iter->shift -= RADIX_TREE_MAP_SHIFT;
> + iter->index = __radix_tree_iter_add(iter, offset);
> + iter->next_index = (iter->index | shift_maxindex(iter->shift)) +
> + 1;
> + }
> +
> + return slot;
> + none:
> + iter->next_index = 0;
> + return NULL;
> +}
> +EXPORT_SYMBOL(__radix_tree_next_slot);
> +#endif
> +
> +void **radix_tree_iter_next(void **slot, struct radix_tree_iter *iter)
> +{
> + struct radix_tree_node *node;
> +
> + slot++;
> + iter->index = __radix_tree_iter_add(iter, 1);
> + node = rcu_dereference_raw(*slot);
> + __radix_tree_iter_next(&node, slot, iter);
> + iter->next_index = iter->index;
> + iter->tags = 0;
> + return NULL;
> +}
> +EXPORT_SYMBOL(radix_tree_iter_next);
> +
> /**
> * radix_tree_next_chunk - find next chunk of slots for iteration
> *
> diff --git a/mm/khugepaged.c b/mm/khugepaged.c
> index 728d779..46155d1 100644
> --- a/mm/khugepaged.c
> +++ b/mm/khugepaged.c
> @@ -1614,8 +1614,8 @@ static void khugepaged_scan_shmem(struct mm_struct *mm,
> present++;
>
> if (need_resched()) {
> + slot = radix_tree_iter_next(slot, &iter);
> cond_resched_rcu();
> - slot = radix_tree_iter_next(&iter);
> }
> }
> rcu_read_unlock();
> diff --git a/mm/shmem.c b/mm/shmem.c
> index 166ebf5..0b3fe33 100644
> --- a/mm/shmem.c
> +++ b/mm/shmem.c
> @@ -658,8 +658,8 @@ unsigned long shmem_partial_swap_usage(struct address_space *mapping,
> swapped++;
>
> if (need_resched()) {
> + slot = radix_tree_iter_next(slot, &iter);
> cond_resched_rcu();
> - slot = radix_tree_iter_next(&iter);
> }
> }
>
> @@ -2434,8 +2434,8 @@ static void shmem_tag_pins(struct address_space *mapping)
> }
>
> if (need_resched()) {
> + slot = radix_tree_iter_next(slot, &iter);
> cond_resched_rcu();
> - slot = radix_tree_iter_next(&iter);
> }
> }
> rcu_read_unlock();
> @@ -2504,8 +2504,8 @@ static int shmem_wait_for_pins(struct address_space *mapping)
> spin_unlock_irq(&mapping->tree_lock);
> continue_resched:
> if (need_resched()) {
> + slot = radix_tree_iter_next(slot, &iter);
> cond_resched_rcu();
> - slot = radix_tree_iter_next(&iter);
> }
> }
> rcu_read_unlock();
> diff --git a/tools/testing/radix-tree/iteration_check.c b/tools/testing/radix-tree/iteration_check.c
> index df71cb8..6eca4c2 100644
> --- a/tools/testing/radix-tree/iteration_check.c
> +++ b/tools/testing/radix-tree/iteration_check.c
> @@ -79,7 +79,7 @@ static void *tagged_iteration_fn(void *arg)
> }
>
> if (rand_r(&seeds[0]) % 50 == 0) {
> - slot = radix_tree_iter_next(&iter);
> + slot = radix_tree_iter_next(slot, &iter);
> rcu_read_unlock();
> rcu_barrier();
> rcu_read_lock();
> @@ -127,7 +127,7 @@ static void *untagged_iteration_fn(void *arg)
> }
>
> if (rand_r(&seeds[1]) % 50 == 0) {
> - slot = radix_tree_iter_next(&iter);
> + slot = radix_tree_iter_next(slot, &iter);
> rcu_read_unlock();
> rcu_barrier();
> rcu_read_lock();
> diff --git a/tools/testing/radix-tree/multiorder.c b/tools/testing/radix-tree/multiorder.c
> index 25e0463..588209a 100644
> --- a/tools/testing/radix-tree/multiorder.c
> +++ b/tools/testing/radix-tree/multiorder.c
> @@ -232,10 +232,14 @@ void multiorder_iteration(void)
> int height = order[i] / RADIX_TREE_MAP_SHIFT;
> int shift = height * RADIX_TREE_MAP_SHIFT;
> int mask = (1 << order[i]) - 1;
> + struct item *item = *slot;
>
> assert(iter.index >= (index[i] &~ mask));
> assert(iter.index <= (index[i] | mask));
> assert(iter.shift == shift);
> + assert(!radix_tree_is_internal_node(item));
> + assert(item->index >= (index[i] &~ mask));
> + assert(item->index <= (index[i] | mask));
> i++;
> }
> }
> @@ -279,12 +283,16 @@ void multiorder_tagged_iteration(void)
> }
>
> radix_tree_for_each_tagged(slot, &tree, &iter, j, 1) {
> + struct item *item = *slot;
> for (k = i; index[k] < tag_index[i]; k++)
> ;
> mask = (1 << order[k]) - 1;
>
> assert(iter.index >= (tag_index[i] &~ mask));
> assert(iter.index <= (tag_index[i] | mask));
> + assert(!radix_tree_is_internal_node(item));
> + assert(item->index >= (tag_index[i] &~ mask));
> + assert(item->index <= (tag_index[i] | mask));
> i++;
> }
> }
> @@ -303,12 +311,16 @@ void multiorder_tagged_iteration(void)
> }
>
> radix_tree_for_each_tagged(slot, &tree, &iter, j, 2) {
> + struct item *item = *slot;
> for (k = i; index[k] < tag_index[i]; k++)
> ;
> mask = (1 << order[k]) - 1;
>
> assert(iter.index >= (tag_index[i] &~ mask));
> assert(iter.index <= (tag_index[i] | mask));
> + assert(!radix_tree_is_internal_node(item));
> + assert(item->index >= (tag_index[i] &~ mask));
> + assert(item->index <= (tag_index[i] | mask));
> i++;
> }
> }
> diff --git a/tools/testing/radix-tree/regression3.c b/tools/testing/radix-tree/regression3.c
> index 1f06ed7..4d28eeb 100644
> --- a/tools/testing/radix-tree/regression3.c
> +++ b/tools/testing/radix-tree/regression3.c
> @@ -88,7 +88,7 @@ void regression3_test(void)
> printf("slot %ld %p\n", iter.index, *slot);
> if (!iter.index) {
> printf("next at %ld\n", iter.index);
> - slot = radix_tree_iter_next(&iter);
> + slot = radix_tree_iter_next(slot, &iter);
> }
> }
>
> @@ -96,7 +96,7 @@ void regression3_test(void)
> printf("contig %ld %p\n", iter.index, *slot);
> if (!iter.index) {
> printf("next at %ld\n", iter.index);
> - slot = radix_tree_iter_next(&iter);
> + slot = radix_tree_iter_next(slot, &iter);
> }
> }
>
> @@ -106,7 +106,7 @@ void regression3_test(void)
> printf("tagged %ld %p\n", iter.index, *slot);
> if (!iter.index) {
> printf("next at %ld\n", iter.index);
> - slot = radix_tree_iter_next(&iter);
> + slot = radix_tree_iter_next(slot, &iter);
> }
> }
>
> diff --git a/tools/testing/radix-tree/test.h b/tools/testing/radix-tree/test.h
> index 33d2b6b..b678f13 100644
> --- a/tools/testing/radix-tree/test.h
> +++ b/tools/testing/radix-tree/test.h
> @@ -43,6 +43,7 @@ void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag);
> extern int nr_allocated;
>
> /* Normally private parts of lib/radix-tree.c */
> +struct radix_tree_node *entry_to_node(void *ptr);
> void radix_tree_dump(struct radix_tree_root *root);
> int root_tag_get(struct radix_tree_root *root, unsigned int tag);
> unsigned long node_maxindex(struct radix_tree_node *);
> --
> 2.10.2
>
> --
> 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>
--
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>
next prev parent reply other threads:[~2016-11-18 11:47 UTC|newest]
Thread overview: 152+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-11-17 0:16 [PATCH 00/29] Improve radix tree for 4.10 Matthew Wilcox
2016-11-17 0:16 ` Matthew Wilcox
2016-11-17 0:16 ` [PATCH 01/29] tools: Add WARN_ON_ONCE Matthew Wilcox
2016-11-17 0:16 ` Matthew Wilcox
2016-11-17 0:16 ` [PATCH 02/29] radix tree test suite: Allow GFP_ATOMIC allocations to fail Matthew Wilcox
2016-11-17 0:16 ` Matthew Wilcox
2016-11-17 0:16 ` [PATCH 03/29] radix tree test suite: Track preempt_count Matthew Wilcox
2016-11-17 0:16 ` Matthew Wilcox
2016-11-17 0:16 ` [PATCH 04/29] radix tree test suite: Free preallocated nodes Matthew Wilcox
2016-11-17 0:16 ` Matthew Wilcox
2016-11-17 0:16 ` [PATCH 05/29] radix tree test suite: Make runs more reproducible Matthew Wilcox
2016-11-17 0:16 ` Matthew Wilcox
2016-11-17 0:16 ` [PATCH 06/28] Add benchmark Matthew Wilcox
2016-11-17 0:16 ` [PATCH 06/29] radix tree test suite: benchmark for iterator Matthew Wilcox
2016-11-17 0:16 ` Matthew Wilcox
2016-11-17 0:16 ` [PATCH 07/29] radix tree test suite: Use rcu_barrier Matthew Wilcox
2016-11-17 0:16 ` Matthew Wilcox
2016-11-17 0:16 ` [PATCH 07/28] test suite: Switch to rcu_barrier from sleep Matthew Wilcox
2016-11-17 0:16 ` [PATCH 08/29] tools: Add more bitmap functions Matthew Wilcox
2016-11-17 0:16 ` Matthew Wilcox
2016-11-17 0:16 ` [PATCH 09/29] radix tree test suite: Use common find-bit code Matthew Wilcox
2016-11-17 0:16 ` Matthew Wilcox
2016-11-17 0:16 ` [PATCH 10/29] radix-tree: Add radix_tree_join Matthew Wilcox
2016-11-17 0:16 ` Matthew Wilcox
2016-11-17 0:16 ` [PATCH 11/29] radix-tree: Add radix_tree_split Matthew Wilcox
2016-11-17 0:16 ` Matthew Wilcox
2016-11-17 0:16 ` [PATCH 12/29] radix-tree: Add radix_tree_split_preload() Matthew Wilcox
2016-11-17 0:16 ` Matthew Wilcox
2016-11-17 0:16 ` [PATCH 13/29] radix-tree: Fix typo Matthew Wilcox
2016-11-17 0:16 ` Matthew Wilcox
2016-11-17 0:16 ` [PATCH 14/29] radix-tree: Move rcu_head into a union with private_list Matthew Wilcox
2016-11-17 0:16 ` Matthew Wilcox
2016-11-17 0:16 ` [PATCH 15/29] radix-tree: Create node_tag_set() Matthew Wilcox
2016-11-17 0:16 ` Matthew Wilcox
2016-11-17 0:16 ` [PATCH 16/29] radix-tree: Make radix_tree_find_next_bit more useful Matthew Wilcox
2016-11-17 0:16 ` Matthew Wilcox
2016-11-17 0:16 ` [PATCH 17/29] radix-tree: Improve dump output Matthew Wilcox
2016-11-17 0:16 ` Matthew Wilcox
2016-11-17 0:16 ` [PATCH 18/29] btrfs: Fix race in btrfs_free_dummy_fs_info() Matthew Wilcox
2016-11-17 0:16 ` Matthew Wilcox
2016-11-17 0:16 ` [PATCH 19/29] radix tree test suite: iteration test misuses RCU Matthew Wilcox
2016-11-17 0:16 ` Matthew Wilcox
2016-11-17 0:16 ` [PATCH 20/29] radix tree: Improve multiorder iterators Matthew Wilcox
2016-11-17 0:16 ` Matthew Wilcox
2016-11-17 0:16 ` [PATCH 21/29] radix-tree: Delete radix_tree_locate_item() Matthew Wilcox
2016-11-17 0:16 ` Matthew Wilcox
2016-11-17 0:16 ` [PATCH 22/29] radix-tree: Delete radix_tree_range_tag_if_tagged() Matthew Wilcox
2016-11-17 0:16 ` Matthew Wilcox
2016-11-17 0:16 ` [PATCH 23/29] idr: Add ida_is_empty Matthew Wilcox
2016-11-17 0:16 ` Matthew Wilcox
2016-11-18 11:56 ` Konstantin Khlebnikov
2016-11-18 11:56 ` Konstantin Khlebnikov
2016-11-17 0:16 ` [PATCH 24/29] tpm: Use idr_find(), not idr_find_slowpath() Matthew Wilcox
2016-11-17 0:16 ` Matthew Wilcox
2016-11-17 0:16 ` [PATCH 25/28] idr: Reduce the number of bits per level from 8 to 6 Matthew Wilcox
2016-11-17 0:16 ` [PATCH 25/29] rxrpc: Abstract away knowledge of IDR internals Matthew Wilcox
2016-11-17 0:16 ` Matthew Wilcox
2016-11-17 0:16 ` [PATCH 26/29] idr: Reduce the number of bits per level from 8 to 6 Matthew Wilcox
2016-11-17 0:16 ` Matthew Wilcox
2016-11-17 0:16 ` [PATCH 26/28] radix tree test suite: Add some more functionality Matthew Wilcox
2016-11-17 0:16 ` [PATCH 27/28] radix-tree: Create all_tag_set Matthew Wilcox
2016-11-17 0:16 ` [PATCH 27/29] radix tree test suite: Add some more functionality Matthew Wilcox
2016-11-17 0:16 ` Matthew Wilcox
2016-11-17 0:16 ` [PATCH 28/28] Reimplement IDR and IDA using the radix tree Matthew Wilcox
2016-11-17 0:16 ` [PATCH 28/29] radix-tree: Create all_tag_set Matthew Wilcox
2016-11-17 0:16 ` Matthew Wilcox
2016-11-17 0:17 ` [PATCH 29/29] Reimplement IDR and IDA using the radix tree Matthew Wilcox
2016-11-17 0:17 ` Matthew Wilcox
2016-11-17 0:17 ` [PATCH 00/29] Improve radix tree for 4.10 Matthew Wilcox
2016-11-17 0:17 ` Matthew Wilcox
2016-11-17 19:38 ` Matthew Wilcox
2016-11-17 19:38 ` Matthew Wilcox
2016-11-17 22:17 ` Ross Zwisler
2016-11-17 22:17 ` Ross Zwisler
2016-11-18 4:24 ` Matthew Wilcox
2016-11-18 4:24 ` Matthew Wilcox
2016-11-17 0:17 ` [PATCH 01/29] tools: Add WARN_ON_ONCE Matthew Wilcox
2016-11-17 0:17 ` Matthew Wilcox
2016-11-17 0:17 ` [PATCH 02/29] radix tree test suite: Allow GFP_ATOMIC allocations to fail Matthew Wilcox
2016-11-17 0:17 ` Matthew Wilcox
2016-11-17 0:17 ` [PATCH 03/29] radix tree test suite: Track preempt_count Matthew Wilcox
2016-11-17 0:17 ` Matthew Wilcox
2016-11-17 0:17 ` [PATCH 04/29] radix tree test suite: Free preallocated nodes Matthew Wilcox
2016-11-17 0:17 ` Matthew Wilcox
2016-11-17 0:17 ` [PATCH 05/29] radix tree test suite: Make runs more reproducible Matthew Wilcox
2016-11-17 0:17 ` Matthew Wilcox
2016-11-17 0:17 ` [PATCH 06/28] Add benchmark Matthew Wilcox
2016-11-17 0:17 ` [PATCH 06/29] radix tree test suite: benchmark for iterator Matthew Wilcox
2016-11-17 0:17 ` Matthew Wilcox
2016-11-17 0:17 ` [PATCH 07/29] radix tree test suite: Use rcu_barrier Matthew Wilcox
2016-11-17 0:17 ` Matthew Wilcox
2016-11-17 0:17 ` [PATCH 07/28] test suite: Switch to rcu_barrier from sleep Matthew Wilcox
2016-11-17 0:17 ` [PATCH 08/29] tools: Add more bitmap functions Matthew Wilcox
2016-11-17 0:17 ` Matthew Wilcox
2016-11-17 0:17 ` [PATCH 09/29] radix tree test suite: Use common find-bit code Matthew Wilcox
2016-11-17 0:17 ` Matthew Wilcox
2016-11-17 0:17 ` [PATCH 10/29] radix-tree: Add radix_tree_join Matthew Wilcox
2016-11-17 0:17 ` Matthew Wilcox
2016-11-17 0:17 ` [PATCH 11/29] radix-tree: Add radix_tree_split Matthew Wilcox
2016-11-17 0:17 ` Matthew Wilcox
2016-11-17 0:17 ` [PATCH 12/29] radix-tree: Add radix_tree_split_preload() Matthew Wilcox
2016-11-17 0:17 ` Matthew Wilcox
2016-11-17 0:17 ` [PATCH 13/29] radix-tree: Fix typo Matthew Wilcox
2016-11-17 0:17 ` Matthew Wilcox
2016-11-17 0:17 ` [PATCH 14/29] radix-tree: Move rcu_head into a union with private_list Matthew Wilcox
2016-11-17 0:17 ` Matthew Wilcox
2016-11-17 0:17 ` [PATCH 15/29] radix-tree: Create node_tag_set() Matthew Wilcox
2016-11-17 0:17 ` Matthew Wilcox
2016-11-17 0:17 ` [PATCH 16/29] radix-tree: Make radix_tree_find_next_bit more useful Matthew Wilcox
2016-11-17 0:17 ` Matthew Wilcox
2016-11-17 0:17 ` [PATCH 17/29] radix-tree: Improve dump output Matthew Wilcox
2016-11-17 0:17 ` Matthew Wilcox
2016-11-17 0:17 ` [PATCH 18/29] btrfs: Fix race in btrfs_free_dummy_fs_info() Matthew Wilcox
2016-11-17 0:17 ` Matthew Wilcox
2016-11-17 0:17 ` [PATCH 19/29] radix tree test suite: iteration test misuses RCU Matthew Wilcox
2016-11-17 0:17 ` Matthew Wilcox
2016-11-17 0:17 ` [PATCH 20/29] radix tree: Improve multiorder iterators Matthew Wilcox
2016-11-17 0:17 ` Matthew Wilcox
2016-11-18 11:47 ` Konstantin Khlebnikov [this message]
2016-11-18 11:47 ` Konstantin Khlebnikov
2016-11-18 16:31 ` Matthew Wilcox
2016-11-18 16:31 ` Matthew Wilcox
2016-11-18 17:56 ` Konstantin Khlebnikov
2016-11-18 17:56 ` Konstantin Khlebnikov
2016-11-18 20:23 ` Matthew Wilcox
2016-11-17 0:17 ` [PATCH 21/29] radix-tree: Delete radix_tree_locate_item() Matthew Wilcox
2016-11-17 0:17 ` Matthew Wilcox
2016-11-18 11:50 ` Konstantin Khlebnikov
2016-11-18 11:50 ` Konstantin Khlebnikov
2016-11-18 16:34 ` Matthew Wilcox
2016-11-17 0:17 ` [PATCH 22/29] radix-tree: Delete radix_tree_range_tag_if_tagged() Matthew Wilcox
2016-11-17 0:17 ` Matthew Wilcox
2016-11-17 0:17 ` [PATCH 23/29] idr: Add ida_is_empty Matthew Wilcox
2016-11-17 0:17 ` Matthew Wilcox
2016-11-17 0:17 ` [PATCH 24/29] tpm: Use idr_find(), not idr_find_slowpath() Matthew Wilcox
2016-11-17 0:17 ` Matthew Wilcox
2016-11-17 0:17 ` [PATCH 25/28] idr: Reduce the number of bits per level from 8 to 6 Matthew Wilcox
2016-11-17 0:17 ` [PATCH 25/29] rxrpc: Abstract away knowledge of IDR internals Matthew Wilcox
2016-11-17 0:17 ` Matthew Wilcox
2016-11-17 0:17 ` [PATCH 26/29] idr: Reduce the number of bits per level from 8 to 6 Matthew Wilcox
2016-11-17 0:17 ` Matthew Wilcox
2016-11-17 0:17 ` [PATCH 26/28] radix tree test suite: Add some more functionality Matthew Wilcox
2016-11-17 0:17 ` [PATCH 27/28] radix-tree: Create all_tag_set Matthew Wilcox
2016-11-17 0:17 ` [PATCH 27/29] radix tree test suite: Add some more functionality Matthew Wilcox
2016-11-17 0:17 ` Matthew Wilcox
2016-11-17 0:17 ` [PATCH 28/28] Reimplement IDR and IDA using the radix tree Matthew Wilcox
2016-11-18 11:52 ` Konstantin Khlebnikov
2016-11-18 13:43 ` Matthew Wilcox
2016-11-17 0:17 ` [PATCH 28/29] radix-tree: Create all_tag_set Matthew Wilcox
2016-11-17 0:17 ` Matthew Wilcox
2016-11-17 0:17 ` [PATCH 29/29] Reimplement IDR and IDA using the radix tree Matthew Wilcox
2016-11-17 0:17 ` Matthew Wilcox
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CALYGNiN++jFZZwvShjD4PDV=cZczVOs+K-ib-ZL=M+v2XU_aYQ@mail.gmail.com' \
--to=koct9i@gmail.com \
--cc=akpm@linux-foundation.org \
--cc=kirill.shutemov@linux.intel.com \
--cc=linux-fsdevel@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-mm@kvack.org \
--cc=mawilcox@linuxonhyperv.com \
--cc=mawilcox@microsoft.com \
--cc=ross.zwisler@linux.intel.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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.