[PATCH v4 1/2] drm: Improve drm_mm search (and fix topdown allocation) with rbtrees

[Lucas Stach]

Am Donnerstag, den 02.02.2017, 11:44 +0000 schrieb Chris Wilson:
> The drm_mm range manager claimed to support top-down insertion, but it
> was neither searching for the top-most hole that could fit the
> allocation request nor fitting the request to the hole correctly.
> 
> In order to search the range efficiently, we create a secondary index
> for the holes using either their size or their address. This index
> allows us to find the smallest hole or the hole at the bottom or top of
> the range efficiently, whilst keeping the hole stack to rapidly service
> evictions.
> 
> v2: Search for holes both high and low. Rename flags to mode.
> v3: Discover rb_entry_safe() and use it!
> v4: Kerneldoc for enum drm_mm_insert_mode.
> 
> Signed-off-by: Chris Wilson <chris at chris-wilson.co.uk>
> Reviewed-by: Joonas Lahtinen <joonas.lahtinen at linux.intel.com>
> Cc: Alex Deucher <alexander.deucher at amd.com>
> Cc: "Christian König" <christian.koenig at amd.com>
> Cc: David Airlie <airlied at linux.ie>
> Cc: Russell King <rmk+kernel at armlinux.org.uk>
> Cc: Daniel Vetter <daniel.vetter at intel.com>
> Cc: Jani Nikula <jani.nikula at linux.intel.com>
> Cc: Sean Paul <seanpaul at chromium.org>
> Cc: Lucas Stach <l.stach at pengutronix.de>
> Cc: Christian Gmeiner <christian.gmeiner at gmail.com>
> Cc: Rob Clark <robdclark at gmail.com>
> Cc: Thierry Reding <thierry.reding at gmail.com>
> Cc: Stephen Warren <swarren at wwwdotorg.org>
> Cc: Alexandre Courbot <gnurou at gmail.com>
> Cc: Eric Anholt <eric at anholt.net>
> Cc: Sinclair Yeh <syeh at vmware.com>
> Cc: Thomas Hellstrom <thellstrom at vmware.com>
> ---
>  drivers/gpu/drm/amd/amdgpu/amdgpu_gtt_mgr.c  |  16 +-
>  drivers/gpu/drm/amd/amdgpu/amdgpu_vram_mgr.c |  20 +-
>  drivers/gpu/drm/armada/armada_gem.c          |   4 +-
>  drivers/gpu/drm/drm_mm.c                     | 488 +++++++++++++++------------
>  drivers/gpu/drm/drm_vma_manager.c            |   3 +-
>  drivers/gpu/drm/etnaviv/etnaviv_mmu.c        |  16 +-
>  drivers/gpu/drm/i915/i915_gem.c              |  10 +-
>  drivers/gpu/drm/i915/i915_gem_evict.c        |   9 +-
>  drivers/gpu/drm/i915/i915_gem_execbuffer.c   |   5 +-
>  drivers/gpu/drm/i915/i915_gem_gtt.c          |  39 +--
>  drivers/gpu/drm/i915/i915_gem_stolen.c       |   6 +-
>  drivers/gpu/drm/msm/msm_gem.c                |   3 +-
>  drivers/gpu/drm/msm/msm_gem_vma.c            |   3 +-
>  drivers/gpu/drm/selftests/test-drm_mm.c      |  58 ++--
>  drivers/gpu/drm/sis/sis_mm.c                 |   6 +-
>  drivers/gpu/drm/tegra/gem.c                  |   4 +-
>  drivers/gpu/drm/ttm/ttm_bo_manager.c         |  18 +-
>  drivers/gpu/drm/vc4/vc4_crtc.c               |   2 +-
>  drivers/gpu/drm/vc4/vc4_hvs.c                |   3 +-
>  drivers/gpu/drm/vc4/vc4_plane.c              |   6 +-
>  drivers/gpu/drm/via/via_mm.c                 |   4 +-
>  drivers/gpu/drm/vmwgfx/vmwgfx_cmdbuf.c       |  10 +-
>  include/drm/drm_mm.h                         | 184 +++++-----
>  23 files changed, 470 insertions(+), 447 deletions(-)
[...]
>  
> diff --git a/drivers/gpu/drm/etnaviv/etnaviv_mmu.c b/drivers/gpu/drm/etnaviv/etnaviv_mmu.c
> index f503af462dad..004456534e48 100644
> --- a/drivers/gpu/drm/etnaviv/etnaviv_mmu.c
> +++ b/drivers/gpu/drm/etnaviv/etnaviv_mmu.c
> @@ -107,6 +107,7 @@ static int etnaviv_iommu_find_iova(struct etnaviv_iommu *mmu,
>  				   struct drm_mm_node *node, size_t size)
>  {
>  	struct etnaviv_vram_mapping *free = NULL;
> +	enum drm_mm_insert_mode mode = DRM_MM_INSERT_LOW;
>  	int ret;
>  
>  	lockdep_assert_held(&mmu->lock);
> @@ -117,15 +118,10 @@ static int etnaviv_iommu_find_iova(struct etnaviv_iommu *mmu,
>  		struct list_head list;
>  		bool found;
>  
> -		/*
> -		 * XXX: The DRM_MM_SEARCH_BELOW is really a hack to trick
> -		 * drm_mm into giving out a low IOVA after address space
> -		 * rollover. This needs a proper fix.
> -		 */
>  		ret = drm_mm_insert_node_in_range(&mmu->mm, node,
> -			size, 0, mmu->last_iova, ~0UL,
> -			mmu->last_iova ? DRM_MM_SEARCH_DEFAULT : DRM_MM_SEARCH_BELOW);
> -
> +						  size, 0, 0,
> +						  mmu->last_iova, U64_MAX,
> +						  mode);
>  		if (ret != -ENOSPC)
>  			break;
>  
> @@ -140,7 +136,7 @@ static int etnaviv_iommu_find_iova(struct etnaviv_iommu *mmu,
>  		}
>  
>  		/* Try to retire some entries */
> -		drm_mm_scan_init(&scan, &mmu->mm, size, 0, 0, 0);
> +		drm_mm_scan_init(&scan, &mmu->mm, size, 0, 0, mode);
>  
>  		found = 0;
>  		INIT_LIST_HEAD(&list);
> @@ -192,6 +188,8 @@ static int etnaviv_iommu_find_iova(struct etnaviv_iommu *mmu,
>  			list_del_init(&m->scan_node);
>  		}
>  
> +		mode = DRM_MM_INSERT_EVICT;
> +
>  		/*
>  		 * We removed enough mappings so that the new allocation will
>  		 * succeed.  Ensure that the MMU will be flushed before the

This needs a rebase on the etnaviv for 4.11 pull, that removes the hack
mentioned in the comment above. Otherwise the code change looks fine.

Regards,
Lucas