linux-kernel - [PATCH -next v2 0/8] rbtree: Cache leftmost node internally

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Date:   Thu,  8 Jun 2017 11:03:21 -0700
From:   Davidlohr Bueso <dave@...olabs.net>
To:     mingo@...nel.org, peterz@...radead.org, akpm@...ux-foundation.org
Cc:     jack@...e.cz, kirill.shutemov@...ux.intel.com,
        ldufour@...ux.vnet.ibm.com, mhocko@...e.com,
        mgorman@...hsingularity.net, dave@...olabs.net,
        linux-kernel@...r.kernel.org
Subject: [PATCH -next v2 0/8] rbtree: Cache leftmost node internally

Changes from v1 (https://marc.info/?l=linux-kernel&m=149611025616685):

- No longer rfc.
- Removed bogus semimcolon in rb_first_cached()
- Updated missing interval tree user drivers/infiniband/hw/hfi1/
- Removed redundant @cached arg in when erasing a node.
- Added more patches that make use of rb_first_cached(), which I
  thought might be worth it: procfs and epoll.
- Cc more people for patch 5, which touches drivers such as infiniband
and gpu. The rest of the changes are pretty covered with the current
Cc'ed maintainers and mm folks.

Hi,

Here's a proposal for extending rbtrees to internally cache the leftmost
node such that we can have fast overlap check optimization for all interval
tree users[1]. 

Patch 1: Layout the rb machinery.

Patches 2,3, 4:  Make use of the internal leftmost node in scheduler and
rt mutexes.

Patch 5: Implements fast overlap checks for interval trees.

Patch 6: rocket science.

Patches 7,8: New patches that convert to O(1) rb_first_cached().

The series has survived booting, kernel builds and pistress workloads.

Applies on top of 4.12-rc4 (next).

Thanks!

Davidlohr Bueso (8):
  rbtree: Cache leftmost node internally
  sched/fair: Replace cfs_rq->rb_leftmost
  sched/deadline: Replace earliest dl and rq leftmost caching
  locking/rtmutex: Replace top-waiter and pi_waiters leftmost caching
  lib/interval_tree: Fast overlap detection
  lib/interval-tree: Correct comment wrt generic flavor
  procfs: Use faster rb_first_cached()
  fs/epoll: Use faster rb_first_cached()

 drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c             |  8 ++--
 drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c             |  7 +--
 drivers/gpu/drm/amd/amdgpu/amdgpu_vm.h             |  2 +-
 drivers/gpu/drm/drm_mm.c                           | 10 ++---
 drivers/gpu/drm/drm_vma_manager.c                  |  2 +-
 drivers/gpu/drm/i915/i915_gem_userptr.c            |  6 +--
 drivers/gpu/drm/radeon/radeon.h                    |  2 +-
 drivers/gpu/drm/radeon/radeon_mn.c                 |  8 ++--
 drivers/gpu/drm/radeon/radeon_vm.c                 |  7 +--
 drivers/infiniband/core/umem_rbtree.c              |  4 +-
 drivers/infiniband/core/uverbs_cmd.c               |  2 +-
 drivers/infiniband/hw/hfi1/mmu_rb.c                | 10 ++---
 drivers/infiniband/hw/usnic/usnic_uiom.c           |  6 +--
 drivers/infiniband/hw/usnic/usnic_uiom.h           |  2 +-
 .../infiniband/hw/usnic/usnic_uiom_interval_tree.c | 15 ++++---
 .../infiniband/hw/usnic/usnic_uiom_interval_tree.h | 12 +++---
 drivers/vhost/vhost.c                              |  2 +-
 drivers/vhost/vhost.h                              |  2 +-
 fs/eventpoll.c                                     | 30 +++++++------
 fs/hugetlbfs/inode.c                               |  6 +--
 fs/inode.c                                         |  2 +-
 fs/proc/generic.c                                  | 26 +++++------
 fs/proc/internal.h                                 |  2 +-
 fs/proc/proc_net.c                                 |  2 +-
 fs/proc/root.c                                     |  2 +-
 include/drm/drm_mm.h                               |  2 +-
 include/linux/fs.h                                 |  4 +-
 include/linux/init_task.h                          |  5 +--
 include/linux/interval_tree.h                      |  8 ++--
 include/linux/interval_tree_generic.h              | 48 ++++++++++++++++-----
 include/linux/mm.h                                 | 17 ++++----
 include/linux/rbtree.h                             | 11 +++++
 include/linux/rbtree_augmented.h                   | 33 ++++++++++++--
 include/linux/rmap.h                               |  4 +-
 include/linux/rtmutex.h                            |  9 ++--
 include/linux/sched.h                              |  3 +-
 include/rdma/ib_umem_odp.h                         | 11 +++--
 include/rdma/ib_verbs.h                            |  2 +-
 kernel/fork.c                                      |  3 +-
 kernel/locking/rtmutex-debug.c                     |  2 +-
 kernel/locking/rtmutex.c                           | 36 ++++++----------
 kernel/locking/rtmutex_common.h                    | 10 ++---
 kernel/sched/deadline.c                            | 50 ++++++++--------------
 kernel/sched/debug.c                               |  2 +-
 kernel/sched/fair.c                                | 35 +++++----------
 kernel/sched/sched.h                               |  9 ++--
 lib/interval_tree_test.c                           |  4 +-
 lib/rbtree.c                                       | 34 ++++++++++++---
 mm/interval_tree.c                                 | 10 ++---
 mm/memory.c                                        |  4 +-
 mm/mmap.c                                          | 10 ++---
 mm/rmap.c                                          |  4 +-
 52 files changed, 303 insertions(+), 244 deletions(-)

-- 
2.12.0