Userspace can severely fragment rb_hole_addr rbtree by manipulating
alignment while allocating buffers. Fragmented rb_hole_addr rbtree
would result in large delays while allocating buffer object for a
userspace application. It takes long time to find suitable hole
because if we fail to find a suitable hole in the first attempt
then we look for neighbouring nodes using rb_prev()/rb_next().
Traversing rbtree using rb_prev()/rb_next() can take really long
time if the tree is fragmented.
This patch improves searches in fragmented rb_hole_addr rbtree by
modifying it to an augmented rbtree which will store an extra field
in drm_mm_node, subtree_max_hole. Each drm_mm_node now stores maximum
hole size for its subtree in drm_mm_node->subtree_max_hole. Using
drm_mm_node->subtree_max_hole, it is possible to eliminate a complete
subtree if that subtree is unable to serve a request hence reducing
number of rb_prev()/rb_next() used.
With this patch applied, 1 million bo allocs on amdgpu took ~8 sec,
compared to 50k bo allocs which took 28 sec without it.
partial test code:
int test_fragmentation(void)
{
int i = 0;
uint32_t minor_version;
uint32_t major_version;
struct amdgpu_bo_alloc_request request = {};
amdgpu_bo_handle vram_handle[MAX_ALLOC] = {};
amdgpu_device_handle device_handle;
request.alloc_size = 4096;
request.phys_alignment = 8192;
request.preferred_heap = AMDGPU_GEM_DOMAIN_VRAM;
int fd = open("/dev/dri/card0", O_RDWR | O_CLOEXEC);
amdgpu_device_initialize(fd, &major_version, &minor_version,
&device_handle);
for (i = 0; i < MAX_ALLOC; i++) {
amdgpu_bo_alloc(device_handle, &request, &vram_handle[i]);
}
for (i = 0; i < MAX_ALLOC; i++)
amdgpu_bo_free(vram_handle[i]);
return 0;
}
v2:
Use RB_DECLARE_CALLBACKS_MAX to maintain subtree_max_hole
v3:
insert_hole_addr() should be static a function
fix return value of next_hole_high_addr()/next_hole_low_addr()
Reported-by: kbuild test robot <lkp@intel.com>
v4:
Fix commit message.
Signed-off-by: Nirmoy Das <nirmoy.das@amd.com>
Reviewed-by: Chris Wilson <chris@chris-wilson.co.uk>
Acked-by: Christian König <christian.koenig@amd.com>
Link: https://patchwork.freedesktop.org/patch/364341/
Signed-off-by: Christian König <christian.koenig@amd.com>
Searching for an available hole by address is slow, as there no
guarantee that a hole will be available and so we must walk over all
nodes in the rbtree before we determine the search was futile. In many
cases, the caller doesn't strictly care for the highest available hole
and was just opportunistically laying out the address space in a
preferred order. In such cases, the caller can accept any address and
would rather do so then do a slow walk.
To be able to mix search strategies, the caller wants to tell the drm_mm
how long to spend on the search. Without a good guide for what should be
the best split, start with a request to try once at most. That is return
the top-most (or lowest) hole if it fulfils the alignment and size
requirements.
v2: Documentation, by why of example (selftests) and kerneldoc.
Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
Cc: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Reviewed-by: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Link: https://patchwork.freedesktop.org/patch/msgid/20180521082131.13744-2-chris@chris-wilson.co.uk
As we keep an rbtree of available holes sorted by their size, we can
very easily determine if there is any hole large enough that might
satisfy the allocation request. This helps when dealing with a highly
fragmented address space and a request for a search by address.
To cache the largest size, we convert into the cached rbtree variant
which tracks the leftmost node for us. However, currently we sorted into
ascending size order so the leftmost node is the smallest, and so to
make it the largest hole we need to invert our sorting.
Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
Cc: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Reviewed-by: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Link: https://patchwork.freedesktop.org/patch/msgid/20180521082131.13744-1-chris@chris-wilson.co.uk
First slice of drm-misc-next for 4.12:
Core/subsystem-wide:
- link status core patch from Manasi, for signalling link train fail
to userspace. I also had the i915 patch in here, but that had a
small buglet in our CI, so reverted.
- more debugfs_remove removal from Noralf, almost there now (Noralf
said he'll try to follow up with the stragglers).
- drm todo moved into kerneldoc, for better visibility (see
Documentation/gpu/todo.rst), lots of starter tasks in there.
- devm_ of helpers + use it in sti (from Ben Gaignard, acked by Rob
Herring)
- extended framebuffer fbdev support (for fbdev flipping), and vblank
wait ioctl fbdev support (Maxime Ripard)
- misc small things all over, as usual
- add vblank callbacks to drm_crtc_funcs, plus make lots of good use
of this to simplify drivers (Shawn Guo)
- new atomic iterator macros to unconfuse old vs. new state
Small drivers:
- vc4 improvements from Eric
- vc4 kerneldocs (Eric)!
- tons of improvements for dw-mipi-dsi in rockchip from John Keeping
and Chris Zhong.
- MAINTAINERS entries for drivers managed in drm-misc. It's not yet
official, still an experiment, but definitely not complete fail and
better to avoid confusion. We kinda screwed that up with drm-misc a
bit when we started committers last year.
- qxl atomic conversion (Gabriel Krisman)
- bunch of virtual driver polish (qxl, virgl, ...)
- misc tiny patches all over
This is the first time we've done the same merge-window blackout for
drm-misc as we've done for drm-intel for ages, hence why we have a
_lot_ of stuff queued already. But it's still only half of drm-intel
(room to grow!), and the drivers in drm-misc experiment seems to work
at least insofar as that you also get lots of driver updates here
alredy.
* tag 'drm-misc-next-2017-03-06' of git://anongit.freedesktop.org/git/drm-misc: (141 commits)
drm/vc4: Fix OOPSes from trying to cache a partially constructed BO.
drm/vc4: Fulfill user BO creation requests from the kernel BO cache.
Revert "drm/i915: Implement Link Rate fallback on Link training failure"
drm/fb-helper: implement ioctl FBIO_WAITFORVSYNC
drm: Update drm_fbdev_cma_init documentation
drm/rockchip/dsi: add dw-mipi power domain support
drm/rockchip/dsi: fix insufficient bandwidth of some panel
dt-bindings: add power domain node for dw-mipi-rockchip
drm/rockchip/dsi: remove mode_valid function
drm/rockchip/dsi: dw-mipi: correct the coding style
drm/rockchip/dsi: dw-mipi: support RK3399 mipi dsi
dt-bindings: add rk3399 support for dw-mipi-rockchip
drm/rockchip: dw-mipi-dsi: add reset control
drm/rockchip: dw-mipi-dsi: support non-burst modes
drm/rockchip: dw-mipi-dsi: defer probe if panel is not loaded
drm/rockchip: vop: test for P{H,V}SYNC
drm/rockchip: dw-mipi-dsi: use positive check for N{H, V}SYNC
drm/rockchip: dw-mipi-dsi: use specific poll helper
drm/rockchip: dw-mipi-dsi: improve PLL configuration
drm/rockchip: dw-mipi-dsi: properly configure PHY timing
...
Insulate users from changes to the internal hole tracking within
struct drm_mm_node by using an accessor for hole_follows.
Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
[danvet: resolve conflicts in i915_vma.c]
Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
Using mm->color_adjust makes the eviction scanner much tricker since we
don't know the actual neighbours of the target hole until after it is
created (after scanning is complete). To work out whether we need to
evict the neighbours because they impact upon the hole, we have to then
check the hole afterwards - requiring an extra step in the user of the
eviction scanner when they apply color_adjust.
v2: Massage kerneldoc.
Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-34-chris@chris-wilson.co.uk
The scan state occupies a large proportion of the struct drm_mm and is
rarely used and only contains temporary state. That makes it suitable to
moving to its struct and onto the stack of the callers.
Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
[danvet: Fix up etnaviv to compile, was missing a BUG_ON.]
Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
Jani Nikula
Rodrigo Vivi
Andy ShevchenkoandThomas Zimmermann
Wang QingandDaniel Vetter
Nirmoy DasandChristian König
Chris Wilson
Liviu DudauandGustavo Padovan
Davidlohr BuesoandLinus Torvalds
Dave Airlie
Ingo Molnar