linux-mm.kvack.org archive mirror
 help / color / mirror / Atom feed
* [PATCH -next 00/11] lib/interval-tree: move to half closed intervals
@ 2019-10-03 20:18 Davidlohr Bueso
  2019-10-03 20:18 ` [PATCH 01/11] mm: introduce vma_interval_tree_foreach_stab() Davidlohr Bueso
                   ` (12 more replies)
  0 siblings, 13 replies; 38+ messages in thread
From: Davidlohr Bueso @ 2019-10-03 20:18 UTC (permalink / raw)
  To: akpm; +Cc: walken, peterz, linux-kernel, linux-mm, dri-devel, linux-rdma, dave

Hi,

It has been discussed[1,2] that almost all users of interval trees would better
be served if the intervals were actually not [a,b], but instead [a, b). This
series attempts to convert all callers by way of transitioning from using
"interval_tree_generic.h" to "interval_tree_gen.h". Once all users are converted,
we remove the former.

Patch 1: adds a call that will make patch 8 easier to review by introducing stab
         queries for the vma interval tree.

Patch 2: adds the new interval_tree_gen.h which is the same as the old one but
         uses [a,b) intervals.

Patch 3-9: converts, in baby steps (as much as possible), each interval tree to
	   the new [a,b) one. It is done this way also to maintain bisectability.
	   Most conversions are pretty straightforward, however, there are some
	   creative ways in which some callers use the interval 'end' when going
	   through intersecting ranges within a tree. Ie: patch 3, 6 and 9.

Patch 10: deletes the interval_tree_generic.h header; there are no longer any users.

Patch 11: finally simplifies x86 pat tree to use the new interval tree machinery.

This has been lightly tested, and certainly not on driver paths that do non
trivial conversions. Also needs more eyeballs as conversions can be easily
missed (even when I've tried mitigating this by renaming the endpoint from 'last'
to 'end' in each corresponding structure).

Because this touches a lot of drivers, I'm Cc'ing the whole thing to a couple of
relevant lists (mm, dri, rdma); sorry if you consider this spam.

Applies on top of today's linux-next tree. Please consider for v5.5.

Thanks!

[1] https://lore.kernel.org/lkml/CANN689HVDJXKEwB80yPAVwvRwnV4HfiucQVAho=dupKM_iKozw@mail.gmail.com/
[2] https://lore.kernel.org/patchwork/patch/1114629/

Davidlohr Bueso (11):
  mm: introduce vma_interval_tree_foreach_stab()
  lib/interval-tree: add an equivalent tree with [a,b) intervals
  drm/amdgpu: convert amdgpu_vm_it to half closed intervals
  drm: convert drm_mm_interval_tree to half closed intervals
  IB/hfi1: convert __mmu_int_rb to half closed intervals
  IB,usnic: convert usnic_uiom_interval_tree to half closed intervals
  vhost: convert vhost_umem_interval_tree to half closed intervals
  mm: convert vma_interval_tree to half closed intervals
  lib/interval-tree: convert interval_tree to half closed intervals
  lib: drop interval_tree_generic.h
  x86/mm, pat: convert pat tree to generic interval tree

 arch/arm/mm/fault-armv.c                           |   2 +-
 arch/arm/mm/flush.c                                |   2 +-
 arch/nios2/mm/cacheflush.c                         |   2 +-
 arch/parisc/kernel/cache.c                         |   2 +-
 arch/x86/mm/pat.c                                  |  22 +--
 arch/x86/mm/pat_rbtree.c                           | 151 +++++----------------
 drivers/gpu/drm/amd/amdgpu/amdgpu_cs.c             |   2 +-
 drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c             |  12 +-
 drivers/gpu/drm/amd/amdgpu/amdgpu_object.h         |   2 +-
 drivers/gpu/drm/amd/amdgpu/amdgpu_trace.h          |  18 +--
 drivers/gpu/drm/amd/amdgpu/amdgpu_uvd.c            |   2 +-
 drivers/gpu/drm/amd/amdgpu/amdgpu_vce.c            |   3 +-
 drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c             |  47 ++++---
 drivers/gpu/drm/drm_mm.c                           |   8 +-
 drivers/gpu/drm/i915/gem/i915_gem_userptr.c        |   5 +-
 .../gpu/drm/i915/gem/selftests/i915_gem_context.c  |   2 +-
 drivers/gpu/drm/radeon/radeon_mn.c                 |  11 +-
 drivers/gpu/drm/radeon/radeon_trace.h              |   2 +-
 drivers/gpu/drm/radeon/radeon_vm.c                 |  26 ++--
 drivers/gpu/drm/selftests/test-drm_mm.c            |   2 +-
 drivers/infiniband/core/umem_odp.c                 |  21 +--
 drivers/infiniband/hw/hfi1/mmu_rb.c                |  15 +-
 drivers/infiniband/hw/usnic/usnic_uiom.c           |   8 +-
 .../infiniband/hw/usnic/usnic_uiom_interval_tree.c |  26 ++--
 .../infiniband/hw/usnic/usnic_uiom_interval_tree.h |   2 +-
 drivers/iommu/virtio-iommu.c                       |   6 +-
 drivers/vhost/vhost.c                              |  19 ++-
 drivers/vhost/vhost.h                              |   4 +-
 fs/dax.c                                           |   2 +-
 include/drm/drm_mm.h                               |   6 +-
 include/linux/interval_tree.h                      |   2 +-
 ...interval_tree_generic.h => interval_tree_gen.h} |  72 +++++-----
 include/linux/mm.h                                 |   6 +
 include/rdma/ib_umem_odp.h                         |   4 +-
 kernel/events/uprobes.c                            |   2 +-
 lib/interval_tree.c                                |   6 +-
 mm/hugetlb.c                                       |   4 +-
 mm/interval_tree.c                                 |   4 +-
 mm/khugepaged.c                                    |   2 +-
 mm/memory-failure.c                                |   6 +-
 mm/memory.c                                        |   2 +-
 mm/nommu.c                                         |   2 +-
 mm/rmap.c                                          |   6 +-
 43 files changed, 217 insertions(+), 333 deletions(-)
 rename include/linux/{interval_tree_generic.h => interval_tree_gen.h} (72%)

-- 
2.16.4



^ permalink raw reply	[flat|nested] 38+ messages in thread

end of thread, other threads:[~2019-10-21 23:25 UTC | newest]

Thread overview: 38+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-10-03 20:18 [PATCH -next 00/11] lib/interval-tree: move to half closed intervals Davidlohr Bueso
2019-10-03 20:18 ` [PATCH 01/11] mm: introduce vma_interval_tree_foreach_stab() Davidlohr Bueso
2019-10-03 20:18 ` [PATCH 02/11] lib/interval-tree: add an equivalent tree with [a,b) intervals Davidlohr Bueso
2019-10-04 11:02   ` Michel Lespinasse
2019-10-03 20:18 ` [PATCH 03/11] drm/amdgpu: convert amdgpu_vm_it to half closed intervals Davidlohr Bueso
2019-10-04  6:54   ` Koenig, Christian
2019-10-04 11:36     ` Michel Lespinasse
2019-10-04 12:39       ` Christian König
2019-10-03 20:18 ` [PATCH 04/11] drm: convert drm_mm_interval_tree " Davidlohr Bueso
2019-10-03 20:18 ` [PATCH 05/11] IB/hfi1: convert __mmu_int_rb " Davidlohr Bueso
2019-10-04 11:50   ` Michel Lespinasse
2019-10-04 19:41     ` Davidlohr Bueso
2019-10-03 20:18 ` [PATCH 06/11] IB,usnic: convert usnic_uiom_interval_tree " Davidlohr Bueso
2019-10-03 20:18 ` [PATCH 07/11] vhost: convert vhost_umem_interval_tree " Davidlohr Bueso
2019-10-04 12:10   ` Michel Lespinasse
2019-10-04 19:44     ` Davidlohr Bueso
2019-10-10  5:49   ` Jason Wang
2019-10-03 20:18 ` [PATCH 08/11] mm: convert vma_interval_tree " Davidlohr Bueso
2019-10-03 20:41   ` Matthew Wilcox
2019-10-04 12:30   ` Michel Lespinasse
2019-10-03 20:18 ` [PATCH 09/11] lib/interval-tree: convert interval_tree " Davidlohr Bueso
2019-10-03 22:50   ` kbuild test robot
2019-10-04  6:57   ` Koenig, Christian
2019-10-04  7:20     ` Koenig, Christian
2019-10-08 16:59       ` Davidlohr Bueso
2019-10-03 20:18 ` [PATCH 10/11] lib: drop interval_tree_generic.h Davidlohr Bueso
2019-10-03 20:18 ` [PATCH 11/11] x86/mm, pat: convert pat tree to generic interval tree Davidlohr Bueso
2019-10-07 15:33   ` Ingo Molnar
2019-10-21 23:24     ` Davidlohr Bueso
2019-10-03 20:32 ` [PATCH -next 00/11] lib/interval-tree: move to half closed intervals Matthew Wilcox
2019-10-03 21:10   ` Davidlohr Bueso
2019-10-04 12:43   ` Michel Lespinasse
2019-10-04  0:26 ` Jason Gunthorpe
2019-10-04  2:48   ` Davidlohr Bueso
2019-10-04 13:15   ` Michel Lespinasse
2019-10-04 16:03     ` Matthew Wilcox
2019-10-04 19:35       ` Davidlohr Bueso
2019-10-04 17:45     ` Jason Gunthorpe

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).