On Wed, May 21, 2014 at 6:26 AM, Naoya Horiguchi <n-horiguchi@xxxxxxxxxxxxx> wrote: > It's useful if we can run only over a specific index range of radix trees, > which this patch does. This patch changes only radix_tree_for_each_slot() > and radix_tree_for_each_tagged(), because we need it only for them for now. NAK, I don't see how this is usefull. Main users don't need this. Barely used argument don't makes complicated macro easier. radix_tree_next_slot() is perfomance-critical. I'm not sure that compiler can throw out your checks if the end is -1, since it stored in structure which is passed into function. Just write something like this where needed. radix_tree_for_each_slot(..) { if (iter.index > end) goto out; <...> if (iter.index == end) goto out; } out: Probably this migh be hidden in a macro as well. There is simple way to abort iterating: set next_index to zero and break inner loop. > > ChangeLog: > - rebased onto v3.15-rc5, which has e a few new caller of radix_tree_for_each_slot(), > so apply this change them too. > > Signed-off-by: Naoya Horiguchi <n-horiguchi@xxxxxxxxxxxxx> > --- > drivers/gpu/drm/qxl/qxl_ttm.c | 2 +- > include/linux/radix-tree.h | 27 ++++++++++++++++++++------- > kernel/irq/irqdomain.c | 2 +- > lib/radix-tree.c | 8 ++++---- > mm/filemap.c | 8 ++++---- > 5 files changed, 30 insertions(+), 17 deletions(-) > > diff --git v3.15-rc5.orig/drivers/gpu/drm/qxl/qxl_ttm.c v3.15-rc5/drivers/gpu/drm/qxl/qxl_ttm.c > index d52c27527b9a..d807e66fe308 100644 > --- v3.15-rc5.orig/drivers/gpu/drm/qxl/qxl_ttm.c > +++ v3.15-rc5/drivers/gpu/drm/qxl/qxl_ttm.c > @@ -398,7 +398,7 @@ static int qxl_sync_obj_wait(void *sync_obj, > struct radix_tree_iter iter; > int release_id; > > - radix_tree_for_each_slot(slot, &qfence->tree, &iter, 0) { > + radix_tree_for_each_slot(slot, &qfence->tree, &iter, 0, ~0UL) { > struct qxl_release *release; > > release_id = iter.index; > diff --git v3.15-rc5.orig/include/linux/radix-tree.h v3.15-rc5/include/linux/radix-tree.h > index 33170dbd9db4..88258c34371f 100644 > --- v3.15-rc5.orig/include/linux/radix-tree.h > +++ v3.15-rc5/include/linux/radix-tree.h > @@ -312,6 +312,7 @@ static inline void radix_tree_preload_end(void) > * @index: index of current slot > * @next_index: next-to-last index for this chunk > * @tags: bit-mask for tag-iterating > + * @end_index: last index to be scanned > * > * This radix tree iterator works in terms of "chunks" of slots. A chunk is a > * subinterval of slots contained within one radix tree leaf node. It is > @@ -324,6 +325,7 @@ struct radix_tree_iter { > unsigned long index; > unsigned long next_index; > unsigned long tags; > + unsigned long end_index; > }; > > #define RADIX_TREE_ITER_TAG_MASK 0x00FF /* tag index in lower byte */ > @@ -335,10 +337,12 @@ struct radix_tree_iter { > * > * @iter: pointer to iterator state > * @start: iteration starting index > + * @end: iteration ending index > * Returns: NULL > */ > static __always_inline void ** > -radix_tree_iter_init(struct radix_tree_iter *iter, unsigned long start) > +radix_tree_iter_init(struct radix_tree_iter *iter, unsigned long start, > + unsigned long end) > { > /* > * Leave iter->tags uninitialized. radix_tree_next_chunk() will fill it > @@ -350,6 +354,7 @@ radix_tree_iter_init(struct radix_tree_iter *iter, unsigned long start) > */ > iter->index = 0; > iter->next_index = start; > + iter->end_index = end; > return NULL; > } > > @@ -399,6 +404,8 @@ radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags) > iter->tags >>= 1; > if (likely(iter->tags & 1ul)) { > iter->index++; > + if (iter->index > iter->end_index) > + return NULL; > return slot + 1; > } > if (!(flags & RADIX_TREE_ITER_CONTIG) && likely(iter->tags)) { > @@ -406,6 +413,8 @@ radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags) > > iter->tags >>= offset; > iter->index += offset + 1; > + if (iter->index > iter->end_index) > + return NULL; > return slot + offset + 1; > } > } else { > @@ -414,6 +423,8 @@ radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags) > while (size--) { > slot++; > iter->index++; > + if (iter->index > iter->end_index) > + return NULL; > if (likely(*slot)) > return slot; > if (flags & RADIX_TREE_ITER_CONTIG) { > @@ -438,7 +449,7 @@ radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags) > * Locks can be released and reacquired between iterations. > */ > #define radix_tree_for_each_chunk(slot, root, iter, start, flags) \ > - for (slot = radix_tree_iter_init(iter, start) ; \ > + for (slot = radix_tree_iter_init(iter, start, ~0UL) ; \ > (slot = radix_tree_next_chunk(root, iter, flags)) ;) > > /** > @@ -461,11 +472,12 @@ radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags) > * @root: the struct radix_tree_root pointer > * @iter: the struct radix_tree_iter pointer > * @start: iteration starting index > + * @end: iteration ending index > * > * @slot points to radix tree slot, @iter->index contains its index. > */ > -#define radix_tree_for_each_slot(slot, root, iter, start) \ > - for (slot = radix_tree_iter_init(iter, start) ; \ > +#define radix_tree_for_each_slot(slot, root, iter, start, end) \ > + for (slot = radix_tree_iter_init(iter, start, end) ; \ > slot || (slot = radix_tree_next_chunk(root, iter, 0)) ; \ > slot = radix_tree_next_slot(slot, iter, 0)) > > @@ -480,7 +492,7 @@ radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags) > * @slot points to radix tree slot, @iter->index contains its index. > */ > #define radix_tree_for_each_contig(slot, root, iter, start) \ > - for (slot = radix_tree_iter_init(iter, start) ; \ > + for (slot = radix_tree_iter_init(iter, start, ~0UL) ; \ > slot || (slot = radix_tree_next_chunk(root, iter, \ > RADIX_TREE_ITER_CONTIG)) ; \ > slot = radix_tree_next_slot(slot, iter, \ > @@ -493,12 +505,13 @@ radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags) > * @root: the struct radix_tree_root pointer > * @iter: the struct radix_tree_iter pointer > * @start: iteration starting index > + * @end: iteration ending index > * @tag: tag index > * > * @slot points to radix tree slot, @iter->index contains its index. > */ > -#define radix_tree_for_each_tagged(slot, root, iter, start, tag) \ > - for (slot = radix_tree_iter_init(iter, start) ; \ > +#define radix_tree_for_each_tagged(slot, root, iter, start, end, tag) \ > + for (slot = radix_tree_iter_init(iter, start, end) ; \ > slot || (slot = radix_tree_next_chunk(root, iter, \ > RADIX_TREE_ITER_TAGGED | tag)) ; \ > slot = radix_tree_next_slot(slot, iter, \ > diff --git v3.15-rc5.orig/kernel/irq/irqdomain.c v3.15-rc5/kernel/irq/irqdomain.c > index f14033700c25..55fc49b412e1 100644 > --- v3.15-rc5.orig/kernel/irq/irqdomain.c > +++ v3.15-rc5/kernel/irq/irqdomain.c > @@ -571,7 +571,7 @@ static int virq_debug_show(struct seq_file *m, void *private) > mutex_lock(&irq_domain_mutex); > list_for_each_entry(domain, &irq_domain_list, link) { > int count = 0; > - radix_tree_for_each_slot(slot, &domain->revmap_tree, &iter, 0) > + radix_tree_for_each_slot(slot, &domain->revmap_tree, &iter, 0, ~0UL) > count++; > seq_printf(m, "%c%-16s %6u %10u %10u %s\n", > domain == irq_default_domain ? '*' : ' ', domain->name, > diff --git v3.15-rc5.orig/lib/radix-tree.c v3.15-rc5/lib/radix-tree.c > index 9599aa72d7a0..531fba8a81db 100644 > --- v3.15-rc5.orig/lib/radix-tree.c > +++ v3.15-rc5/lib/radix-tree.c > @@ -1007,7 +1007,7 @@ radix_tree_gang_lookup(struct radix_tree_root *root, void **results, > if (unlikely(!max_items)) > return 0; > > - radix_tree_for_each_slot(slot, root, &iter, first_index) { > + radix_tree_for_each_slot(slot, root, &iter, first_index, ~0UL) { > results[ret] = indirect_to_ptr(rcu_dereference_raw(*slot)); > if (!results[ret]) > continue; > @@ -1049,7 +1049,7 @@ radix_tree_gang_lookup_slot(struct radix_tree_root *root, > if (unlikely(!max_items)) > return 0; > > - radix_tree_for_each_slot(slot, root, &iter, first_index) { > + radix_tree_for_each_slot(slot, root, &iter, first_index, ~0UL) { > results[ret] = slot; > if (indices) > indices[ret] = iter.index; > @@ -1086,7 +1086,7 @@ radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results, > if (unlikely(!max_items)) > return 0; > > - radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) { > + radix_tree_for_each_tagged(slot, root, &iter, first_index, ~0UL, tag) { > results[ret] = indirect_to_ptr(rcu_dereference_raw(*slot)); > if (!results[ret]) > continue; > @@ -1123,7 +1123,7 @@ radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results, > if (unlikely(!max_items)) > return 0; > > - radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) { > + radix_tree_for_each_tagged(slot, root, &iter, first_index, ~0UL, tag) { > results[ret] = slot; > if (++ret == max_items) > break; > diff --git v3.15-rc5.orig/mm/filemap.c v3.15-rc5/mm/filemap.c > index 000a220e2a41..d684e4cffe96 100644 > --- v3.15-rc5.orig/mm/filemap.c > +++ v3.15-rc5/mm/filemap.c > @@ -1118,7 +1118,7 @@ unsigned find_get_entries(struct address_space *mapping, > > rcu_read_lock(); > restart: > - radix_tree_for_each_slot(slot, &mapping->page_tree, &iter, start) { > + radix_tree_for_each_slot(slot, &mapping->page_tree, &iter, start, ~0UL) { > struct page *page; > repeat: > page = radix_tree_deref_slot(slot); > @@ -1180,7 +1180,7 @@ unsigned find_get_pages(struct address_space *mapping, pgoff_t start, > > rcu_read_lock(); > restart: > - radix_tree_for_each_slot(slot, &mapping->page_tree, &iter, start) { > + radix_tree_for_each_slot(slot, &mapping->page_tree, &iter, start, ~0UL) { > struct page *page; > repeat: > page = radix_tree_deref_slot(slot); > @@ -1324,7 +1324,7 @@ unsigned find_get_pages_tag(struct address_space *mapping, pgoff_t *index, > rcu_read_lock(); > restart: > radix_tree_for_each_tagged(slot, &mapping->page_tree, > - &iter, *index, tag) { > + &iter, *index, ~0UL, tag) { > struct page *page; > repeat: > page = radix_tree_deref_slot(slot); > @@ -2023,7 +2023,7 @@ void filemap_map_pages(struct vm_area_struct *vma, struct vm_fault *vmf) > pte_t *pte; > > rcu_read_lock(); > - radix_tree_for_each_slot(slot, &mapping->page_tree, &iter, vmf->pgoff) { > + radix_tree_for_each_slot(slot, &mapping->page_tree, &iter, vmf->pgoff, ~0UL) { > if (iter.index > vmf->max_pgoff) > break; > repeat: > -- > 1.9.0 > -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@xxxxxxxxx. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"dont@xxxxxxxxx"> email@xxxxxxxxx </a>