fix typo for drm

v1->v2:
respin with the change "iff ==> implies that"
Signed-off-by: NCai Huoqing <caihuoqing@baidu.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Link: https://patchwork.freedesktop.org/patch/msgid/20210730132729.376-1-caihuoqing@baidu.com

Skipping just one branch of the tree is not the most
effective approach.

Instead use a macro to define the traversal functions and
sort out both branch sides.

This improves the performance of the unit tests by
a factor of more than 4.
Signed-off-by: NChristian König <christian.koenig@amd.com>
Reviewed-by: NNirmoy Das <nirmoy.das@amd.com>
Link: https://patchwork.freedesktop.org/patch/370298/

Abort early if there isn't enough space to allocate from a subtree.
Signed-off-by: NChristian König <christian.koenig@amd.com>
Acked-by: NNirmoy Das <nirmoy.das@amd.com>
Link: https://patchwork.freedesktop.org/patch/370297/

Just some code cleanup.
Signed-off-by: NChristian König <christian.koenig@amd.com>
Reviewed-by: NNirmoy Das <nirmoy.das@amd.com>
Link: https://patchwork.freedesktop.org/patch/370296/

When the current entry is rejected as candidate for the search
it does not mean that we can abort the subtree search.

It is perfectly possible that only the alignment, but not the
size is the reason for the rejection.
Signed-off-by: NChristian König <christian.koenig@amd.com>
Reviewed-by: NNirmoy Das <nirmoy.das@amd.com>
Link: https://patchwork.freedesktop.org/patch/369394/

Fixes: 0cdea445 ("drm/mm: optimize rb_hole_addr rbtree search")
Signed-off-by: NNirmoy Das <nirmoy.das@amd.com>
Reported-by: NChristian König <christian.koenig@amd.com>
Reviewed-by: NChristian König <christian.koenig@amd.com>
Signed-off-by: NChristian König <christian.koenig@amd.com>
Link: https://patchwork.freedesktop.org/patch/367726/

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: Nkbuild test robot <lkp@intel.com>
v4:
Fix commit message.
Signed-off-by: NNirmoy Das <nirmoy.das@amd.com>
Reviewed-by: NChris Wilson <chris@chris-wilson.co.uk>
Acked-by: NChristian König <christian.koenig@amd.com>
Link: https://patchwork.freedesktop.org/patch/364341/Signed-off-by: NChristian König <christian.koenig@amd.com>

This reverts commit 7be1b9b8.

The drm_mm is supposed to work in atomic context, so calling schedule()
or in this case cond_resched() is illegal.
Signed-off-by: NChristian König <christian.koenig@amd.com>
Acked-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Link: https://patchwork.freedesktop.org/patch/359278/

This reverts commit 7be1b9b8.

The drm_mm is supposed to work in atomic context, so calling schedule()
or in this case cond_resched() is illegal.
Signed-off-by: NChristian König <christian.koenig@amd.com>
Acked-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Link: https://patchwork.freedesktop.org/patch/359278/

In Pete Goodliffe words, "You can improve a system by adding new code. You
can also improve a system by removing code" - In this case, commit
"202b52b7" added new code to initialize end of the node. So, there
is no need for duplicated initialization, and this patch simply removes it.
Signed-off-by: NAkeem G Abodunrin <akeem.g.abodunrin@intel.com>
Cc: Chris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: NChris Wilson <chris@chris-wilson.co.uk>
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Link: https://patchwork.freedesktop.org/patch/msgid/20200309151156.25040-1-akeem.g.abodunrin@intel.com

We try hard to select a suitable hole in the drm_mm first time. But if
that is unsuccessful, we then have to look at neighbouring nodes, and
this requires traversing the rbtree. Walking the rbtree can be slow
(much slower than a linear list for deep trees), and if the drm_mm has
been purposefully fragmented our search can be trapped for a long, long
time. For non-preemptible kernels, we need to break up long CPU bound
sections by manually checking for cond_resched(); similarly we should
also bail out if we have been told to terminate. (In an ideal world, we
would break for any signal, but we need to trade off having to perform
the search again after ERESTARTSYS, which again may form a trap of
making no forward progress.)
Reported-by: NZbigniew Kempczyński <zbigniew.kempczynski@intel.com>
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Cc: Zbigniew Kempczyński <zbigniew.kempczynski@intel.com>
Cc: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Reviewed-by: NAndi Shyti <andi.shyti@intel.com>
Link: https://patchwork.freedesktop.org/patch/msgid/20200207151720.2812125-1-chris@chris-wilson.co.uk

A few callers need to serialise the destruction of their drm_mm_node and
ensure it is removed from the drm_mm before freeing. However, to be
completely sure that any access from another thread is complete before
we free the struct, we require the RELEASE semantics of
clear_bit_unlock().

This allows the conditional locking such as

Thread A			Thread B
  mutex_lock(mm_lock);		  if (drm_mm_node_allocated(node)) {
  drm_mm_node_remove(node);	    mutex_lock(mm_lock);
  mutex_unlock(mm_lock);	    if (drm_mm_node_allocated(node))
				      drm_mm_node_remove(node);
				    mutex_unlock(mm_lock);
				  }
				  kfree(node);

to serialise correctly without any lingering accesses from A to the
freed node. Allocation / insertion of the node is assumed never to race
with removal or eviction scanning.
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: NTvrtko Ursulin <tvrtko.ursulin@intel.com>
Link: https://patchwork.freedesktop.org/patch/msgid/20191003210100.22250-5-chris@chris-wilson.co.uk

A straightforward conversion of assignment and checking of the boolean
state flags (allocated, scanned) into non-atomic bitops. The caller
remains responsible for all locking around the drm_mm and its nodes.
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: NTvrtko Ursulin <tvrtko.ursulin@intel.com>
Link: https://patchwork.freedesktop.org/patch/msgid/20191003210100.22250-4-chris@chris-wilson.co.uk

In preparation for rearranging the booleans into a flags field, ensure
all the current users are using the inline helpers and not directly
accessing the members.
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: NTvrtko Ursulin <tvrtko.ursulin@intel.com>
Link: https://patchwork.freedesktop.org/patch/msgid/20191003210100.22250-3-chris@chris-wilson.co.uk

We gracefully handle the caller specifying a zero range, so don't force
them to special case that condition if it naturally falls out of their
setup. What we don't check is if the end < start, so keep that as an
assert for an illegal call.
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Cc: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Cc: Daniele Ceraolo Spurio <daniele.ceraolospurio@intel.com>
Cc: Daniel Vetter <daniel.vetter@ffwll.ch>
Reviewed-by: NDaniele Ceraolo Spurio <daniele.ceraolospurio@intel.com>
Link: https://patchwork.freedesktop.org/patch/msgid/20190626094330.3556-1-chris@chris-wilson.co.uk

The use of the drmP.h header file is deprecated.
Remove use from all files in drm/*
so people do not look there and follow a bad example.

Build tested allyesconfig,allmodconfig on x86, arm etc.
Including alpha that is as always more challenging than
the rest.
Signed-off-by: NSam Ravnborg <sam@ravnborg.org>
Acked-by: NDaniel Vetter <daniel@ffwll.ch>
Cc: Maarten Lankhorst <maarten.lankhorst@linux.intel.com>
Cc: Maxime Ripard <maxime.ripard@bootlin.com>
Cc: Sean Paul <sean@poorly.run>
Cc: David Airlie <airlied@linux.ie>
Link: https://patchwork.freedesktop.org/patch/msgid/20190526173535.32701-8-sam@ravnborg.org

Replace the indirection through struct stack_trace by using the storage
array based interfaces.

The original code in all printing functions is really wrong. It allocates a
storage array on stack which is unused because depot_fetch_stack() does not
store anything in it. It overwrites the entries pointer in the stack_trace
struct so it points to the depot storage.
Signed-off-by: NThomas Gleixner <tglx@linutronix.de>
Reviewed-by: NJosh Poimboeuf <jpoimboe@redhat.com>
Acked-by: NDaniel Vetter <daniel@ffwll.ch>
Cc: Andy Lutomirski <luto@kernel.org>
Cc: intel-gfx@lists.freedesktop.org
Cc: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Cc: Maarten Lankhorst <maarten.lankhorst@linux.intel.com>
Cc: dri-devel@lists.freedesktop.org
Cc: David Airlie <airlied@linux.ie>
Cc: Jani Nikula <jani.nikula@linux.intel.com>
Cc: Rodrigo Vivi <rodrigo.vivi@intel.com>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Alexander Potapenko <glider@google.com>
Cc: Alexey Dobriyan <adobriyan@gmail.com>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Christoph Lameter <cl@linux.com>
Cc: Pekka Enberg <penberg@kernel.org>
Cc: linux-mm@kvack.org
Cc: David Rientjes <rientjes@google.com>
Cc: Catalin Marinas <catalin.marinas@arm.com>
Cc: Dmitry Vyukov <dvyukov@google.com>
Cc: Andrey Ryabinin <aryabinin@virtuozzo.com>
Cc: kasan-dev@googlegroups.com
Cc: Mike Rapoport <rppt@linux.vnet.ibm.com>
Cc: Akinobu Mita <akinobu.mita@gmail.com>
Cc: Christoph Hellwig <hch@lst.de>
Cc: iommu@lists.linux-foundation.org
Cc: Robin Murphy <robin.murphy@arm.com>
Cc: Marek Szyprowski <m.szyprowski@samsung.com>
Cc: Johannes Thumshirn <jthumshirn@suse.de>
Cc: David Sterba <dsterba@suse.com>
Cc: Chris Mason <clm@fb.com>
Cc: Josef Bacik <josef@toxicpanda.com>
Cc: linux-btrfs@vger.kernel.org
Cc: dm-devel@redhat.com
Cc: Mike Snitzer <snitzer@redhat.com>
Cc: Alasdair Kergon <agk@redhat.com>
Cc: Tom Zanussi <tom.zanussi@linux.intel.com>
Cc: Miroslav Benes <mbenes@suse.cz>
Cc: linux-arch@vger.kernel.org
Link: https://lkml.kernel.org/r/20190425094802.622094226@linutronix.de

No architecture terminates the stack trace with ULONG_MAX anymore. Remove
the cruft.
Signed-off-by: NThomas Gleixner <tglx@linutronix.de>
Acked-by: NPeter Zijlstra (Intel) <peterz@infradead.org>
Cc: Josh Poimboeuf <jpoimboe@redhat.com>
Cc: Andy Lutomirski <luto@kernel.org>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Alexander Potapenko <glider@google.com>
Cc: intel-gfx@lists.freedesktop.org
Cc: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Cc: Maarten Lankhorst <maarten.lankhorst@linux.intel.com>
Cc: dri-devel@lists.freedesktop.org
Cc: David Airlie <airlied@linux.ie>
Cc: Jani Nikula <jani.nikula@linux.intel.com>
Cc: Daniel Vetter <daniel@ffwll.ch>
Cc: Rodrigo Vivi <rodrigo.vivi@intel.com>
Link: https://lkml.kernel.org/r/20190410103644.945059666@linutronix.de

Most of these are just cases where code comments used contractions
(it's, who's) where they actually mean to use a possessive pronoun (its,
whose) or vice-versa.
Signed-off-by: NMatt Roper <matthew.d.roper@intel.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Link: https://patchwork.freedesktop.org/patch/msgid/20190202012326.20096-1-matthew.d.roper@intel.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: NChris Wilson <chris@chris-wilson.co.uk>
Cc: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Reviewed-by: NJoonas 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: NChris Wilson <chris@chris-wilson.co.uk>
Cc: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Reviewed-by: NJoonas Lahtinen <joonas.lahtinen@linux.intel.com>
Link: https://patchwork.freedesktop.org/patch/msgid/20180521082131.13744-1-chris@chris-wilson.co.uk

When we descend the tree to find our slot, if we step to the right, we
are no longer the leftmost node.

Fixes: f808c13f ("lib/interval_tree: fast overlap detection")
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Cc: Davidlohr Bueso <dbueso@suse.de>
Cc: Jérôme Glisse <jglisse@redhat.com>
Cc: Christian König <christian.koenig@amd.com>
Reviewed-by: NJoonas Lahtinen <joonas.lahtinen@linux.intel.com>
Acked-by: Christian König <christian.koenig@amd.com> for now.
Link: https://patchwork.freedesktop.org/patch/msgid/20180220093738.1461-1-chris@chris-wilson.co.uk

During eviction, the driver may free more than one hole in the drm_mm
due to the side-effects in evicting the scanned nodes. However,
drm_mm_scan_color_evict() expects that the scan result is the first
available hole (in the mru freed hole_stack list):

  kernel BUG at drivers/gpu/drm/drm_mm.c:844!
  invalid opcode: 0000 [#1] PREEMPT SMP KASAN PTI
  Dumping ftrace buffer:
     (ftrace buffer empty)
  Modules linked in: i915 snd_hda_codec_analog snd_hda_codec_generic coretemp snd_hda_intel snd_hda_codec snd_hwdep snd_hda_core lpc_ich snd_pcm e1000e mei_me prime_numbers mei
  CPU: 1 PID: 1490 Comm: gem_userptr_bli Tainted: G     U           4.16.0-rc1-g740f57c54ecf-kasan_6+ #1
  Hardware name: Dell Inc. OptiPlex 755                 /0PU052, BIOS A08 02/19/2008
  RIP: 0010:drm_mm_scan_color_evict+0x2b8/0x3d0
  RSP: 0018:ffff880057a573f8 EFLAGS: 00010287
  RAX: ffff8800611f5980 RBX: ffff880057a575d0 RCX: dffffc0000000000
  RDX: 00000000029d5000 RSI: 1ffff1000af4aec1 RDI: ffff8800611f5a10
  RBP: ffff88005ab884d0 R08: ffff880057a57600 R09: 000000000afff000
  R10: 1ffff1000b5710b5 R11: 0000000000001000 R12: 1ffff1000af4ae82
  R13: ffff8800611f59b0 R14: ffff8800611f5980 R15: ffff880057a57608
  FS:  00007f2de0c2e8c0(0000) GS:ffff88006ac40000(0000) knlGS:0000000000000000
  CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
  CR2: 00007f2ddde1e000 CR3: 00000000609b2000 CR4: 00000000000006e0
  Call Trace:
   ? drm_mm_scan_remove_block+0x330/0x330
   ? drm_mm_scan_remove_block+0x151/0x330
   i915_gem_evict_something+0x711/0xbd0 [i915]
   ? igt_evict_contexts+0x50/0x50 [i915]
   ? nop_clear_range+0x10/0x10 [i915]
   ? igt_evict_something+0x90/0x90 [i915]
   ? i915_gem_gtt_reserve+0x1a1/0x320 [i915]
   i915_gem_gtt_insert+0x237/0x400 [i915]
   __i915_vma_do_pin+0xc25/0x1a20 [i915]
   eb_lookup_vmas+0x1c63/0x3790 [i915]
   ? i915_gem_check_execbuffer+0x250/0x250 [i915]
   ? trace_hardirqs_on_caller+0x33f/0x590
   ? _raw_spin_unlock_irqrestore+0x39/0x60
   ? __pm_runtime_resume+0x7d/0xf0
   i915_gem_do_execbuffer+0x86a/0x2ff0 [i915]
   ? __kmalloc+0x132/0x340
   ? i915_gem_execbuffer2_ioctl+0x10f/0x760 [i915]
   ? drm_ioctl_kernel+0x12e/0x1c0
   ? drm_ioctl+0x662/0x980
   ? eb_relocate_slow+0xa90/0xa90 [i915]
   ? i915_gem_execbuffer2_ioctl+0x10f/0x760 [i915]
   ? __might_fault+0xea/0x1a0
   i915_gem_execbuffer2_ioctl+0x3cc/0x760 [i915]
   ? i915_gem_execbuffer_ioctl+0xba0/0xba0 [i915]
   ? lock_acquire+0x3c0/0x3c0
   ? i915_gem_execbuffer_ioctl+0xba0/0xba0 [i915]
   drm_ioctl_kernel+0x12e/0x1c0
   drm_ioctl+0x662/0x980
   ? i915_gem_execbuffer_ioctl+0xba0/0xba0 [i915]
   ? drm_getstats+0x20/0x20
   ? debug_check_no_obj_freed+0x2a6/0x8c0
   do_vfs_ioctl+0x170/0xe70
   ? ioctl_preallocate+0x170/0x170
   ? task_work_run+0xbe/0x160
   ? lock_acquire+0x3c0/0x3c0
   ? trace_hardirqs_on_caller+0x33f/0x590
   ? _raw_spin_unlock_irq+0x2f/0x50
   SyS_ioctl+0x36/0x70
   ? do_vfs_ioctl+0xe70/0xe70
   do_syscall_64+0x18c/0x5d0
   entry_SYSCALL_64_after_hwframe+0x26/0x9b
  RIP: 0033:0x7f2ddf13b587
  RSP: 002b:00007fff15c4f9d8 EFLAGS: 00000246 ORIG_RAX: 0000000000000010
  RAX: ffffffffffffffda RBX: 0000000000000003 RCX: 00007f2ddf13b587
  RDX: 00007fff15c4fa20 RSI: 0000000040406469 RDI: 0000000000000003
  RBP: 00007fff15c4fa20 R08: 0000000000000000 R09: 00007f2ddf3fe120
  R10: 0000000000000073 R11: 0000000000000246 R12: 0000000040406469
  R13: 0000000000000003 R14: 00007fff15c4fa20 R15: 00000000000000c7
  Code: 00 00 00 4a c7 44 22 08 00 00 00 00 42 c7 44 22 10 00 00 00 00 48 81 c4 b8 00 00 00 5b 5d 41 5c 41 5d 41 5e 41 5f c3 0f 0b 0f 0b <0f> 0b 31 c0 eb c0 4c 89 ef e8 9a 09 41 ff e9 1e fe ff ff 4c 89
  RIP: drm_mm_scan_color_evict+0x2b8/0x3d0 RSP: ffff880057a573f8

We can trivially relax this assumption by searching the hole_stack for
the scan result and warn instead if the driver called us without any
result.

Fixes: 3fa489da ("drm: Apply tight eviction scanning to color_adjust")
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Cc: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Cc: <stable@vger.kernel.org> # v4.11+
Reviewed-by: NJoonas Lahtinen <joonas.lahtinen@linux.intel.com>
Reviewed-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Link: https://patchwork.freedesktop.org/patch/msgid/20180219113543.8010-1-chris@chris-wilson.co.uk

Add a variant of rbtree_replace_node() that maintains the leftmost cache
of struct rbtree_root_cached when replacing nodes within the rbtree.

As drm_mm is the only rb_replace_node() being used on an interval tree,
the mistake looks fairly self-contained.  Furthermore the only user of
drm_mm_replace_node() is its testsuite...

Testcase: igt/drm_mm/replace

Link: http://lkml.kernel.org/r/20171122100729.3742-1-chris@chris-wilson.co.uk
Link: https://patchwork.freedesktop.org/patch/msgid/20171109212435.9265-1-chris@chris-wilson.co.uk
Fixes: f808c13f ("lib/interval_tree: fast overlap detection")
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: NJoonas Lahtinen <joonas.lahtinen@linux.intel.com>
Acked-by: NDavidlohr Bueso <dbueso@suse.de>
Cc: Jérôme Glisse <jglisse@redhat.com>
Cc: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Cc: Daniel Vetter <daniel.vetter@ffwll.ch>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>

Minor spelling fix for 'monster' and replace 'on' with 'own' in
comments.
Signed-off-by: NLiviu Dudau <Liviu.Dudau@arm.com>
Reviewed-by: NAlex Deucher <alexander.deucher@amd.com>
Signed-off-by: NGustavo Padovan <gustavo.padovan@collabora.com>
Link: https://patchwork.freedesktop.org/patch/msgid/20171101140436.2743-1-Liviu.Dudau@arm.com

Allow interval trees to quickly check for overlaps to avoid unnecesary
tree lookups in interval_tree_iter_first().

As of this patch, all interval tree flavors will require using a
'rb_root_cached' such that we can have the leftmost node easily
available.  While most users will make use of this feature, those with
special functions (in addition to the generic insert, delete, search
calls) will avoid using the cached option as they can do funky things
with insertions -- for example, vma_interval_tree_insert_after().

[jglisse@redhat.com: fix deadlock from typo vm_lock_anon_vma()]
  Link: http://lkml.kernel.org/r/20170808225719.20723-1-jglisse@redhat.com
Link: http://lkml.kernel.org/r/20170719014603.19029-12-dave@stgolabs.netSigned-off-by: NDavidlohr Bueso <dbueso@suse.de>
Signed-off-by: NJérôme Glisse <jglisse@redhat.com>
Acked-by: NChristian König <christian.koenig@amd.com>
Acked-by: NPeter Zijlstra (Intel) <peterz@infradead.org>
Acked-by: NDoug Ledford <dledford@redhat.com>
Acked-by: NMichael S. Tsirkin <mst@redhat.com>
Cc: David Airlie <airlied@linux.ie>
Cc: Jason Wang <jasowang@redhat.com>
Cc: Christian Benvenuti <benve@cisco.com>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>

As we require valid start/end parameters, we can replace the initial
potential NULL with a pointer to the drm_mm.head_node and so reduce the
test on every iteration from a NULL + address comparison to just an
address comparison.

add/remove: 0/0 grow/shrink: 0/1 up/down: 0/-26 (-26)
function                                     old     new   delta
i915_gem_evict_for_node                      719     693     -26

(No other users outside of the test harness.)
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Cc: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Reviewed-by: NJoonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20170204111913.12416-1-chris@chris-wilson.co.uk

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: NChris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: NJoonas Lahtinen <joonas.lahtinen@linux.intel.com>
Cc: Alex Deucher <alexander.deucher@amd.com>
Cc: "Christian König" <christian.koenig@amd.com>
Cc: David Airlie <airlied@linux.ie>
Cc: Russell King <rmk+kernel@armlinux.org.uk>
Cc: Daniel Vetter <daniel.vetter@intel.com>
Cc: Jani Nikula <jani.nikula@linux.intel.com>
Cc: Sean Paul <seanpaul@chromium.org>
Cc: Lucas Stach <l.stach@pengutronix.de>
Cc: Christian Gmeiner <christian.gmeiner@gmail.com>
Cc: Rob Clark <robdclark@gmail.com>
Cc: Thierry Reding <thierry.reding@gmail.com>
Cc: Stephen Warren <swarren@wwwdotorg.org>
Cc: Alexandre Courbot <gnurou@gmail.com>
Cc: Eric Anholt <eric@anholt.net>
Cc: Sinclair Yeh <syeh@vmware.com>
Cc: Thomas Hellstrom <thellstrom@vmware.com>
Reviewed-by: NAlex Deucher <alexander.deucher@amd.com>
Reviewed-by: Sinclair Yeh <syeh@vmware.com> # vmwgfx
Reviewed-by: Lucas Stach <l.stach@pengutronix.de> #etnaviv
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20170202210438.28702-1-chris@chris-wilson.co.uk

I just learned that &struct_name.member_name works and looks pretty
even. It doesn't (yet) link to the member directly though, which would
be really good for big structures or vfunc tables (where the
per-member kerneldoc tends to be long).

Also some minor drive-by polish where it makes sense, I read a lot
of docs ...

Cc: Jani Nikula <jani.nikula@linux.intel.com>
Cc: Chris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: NGustavo Padovan <gustavo.padovan@collabora.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@intel.com>
Link: http://patchwork.freedesktop.org/patch/msgid/20170125062657.19270-5-daniel.vetter@ffwll.ch

Added some boilerplate for the structs, documented members where they
are relevant and plenty of markup for hyperlinks all over. And a few
small wording polish.

Note that the intro needs some more love after the DRM_MM_INSERT_*
patch from Chris has landed.

v2: Spelling fixes (Chris).

v3: Use &struct foo instead of &foo structure (Chris).

Cc: Chris Wilson <chris@chris-wilson.co.uk>
Cc: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Reviewed-by: NDavid Herrmann <dh.herrmann@gmail.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@intel.com>
Link: http://patchwork.freedesktop.org/patch/msgid/1483044517-5770-3-git-send-email-daniel.vetter@ffwll.ch

Including all drivers. I thought about keeping small compat functions
to avoid having to change all drivers. But I really like the
drm_printer idea, so figured spreading it more widely is a good thing.

v2: Review from Chris:
- Natural argument order and better name for drm_mm_print.
- show_mm() macro in the selftest.

Cc: Rob Clark <robdclark@gmail.com>
Cc: Russell King <rmk+kernel@armlinux.org.uk>
Cc: Alex Deucher <alexander.deucher@amd.com>
Cc: Christian König <christian.koenig@amd.com>
Cc: Lucas Stach <l.stach@pengutronix.de>
Cc: Tomi Valkeinen <tomi.valkeinen@ti.com>
Cc: Thierry Reding <thierry.reding@gmail.com>
Cc: Jyri Sarha <jsarha@ti.com>
Reviewed-by: NChris Wilson <chris@chris-wilson.co.uk>
Signed-off-by: NDaniel Vetter <daniel.vetter@intel.com>
Link: http://patchwork.freedesktop.org/patch/msgid/1483009764-8281-1-git-send-email-daniel.vetter@ffwll.ch

A couple of parameters slipped through the kerneldoc net.
Reported-by: Nkbuild test robot <fengguang.wu@intel.com>
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Cc: Daniel Vetter <daniel.vetter@ffwll.ch>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161228105120.14500-1-chris@chris-wilson.co.uk

Drivers need to take care. Motivated by a discussion between Mark and
Rob on dri-devel.

Cc: Mark yao <mark.yao@rock-chips.com>
Cc: Rob Clark <robdclark@gmail.com>
Reviewed-by: NChris Wilson <chris@chris-wilson.co.uk>
[danvet: s/alloc|freeing/modifications/ per Chris' suggestion.]
Signed-off-by: NDaniel Vetter <daniel.vetter@intel.com>
Link: http://patchwork.freedesktop.org/patch/msgid/1482833457-29592-1-git-send-email-daniel.vetter@ffwll.ch

Remove a superfluous helper as drm_mm_insert_node is equivalent to
insert_node_in_range with a range of [0, U64_MAX].
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: NJoonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-37-chris@chris-wilson.co.uk

mm->color_adjust() compares the hole with its neighbouring nodes. They
only abutt before we restrict the hole, so we have to apply color_adjust
before we apply the range restriction.
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: NJoonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-36-chris@chris-wilson.co.uk

Insulate users from changes to the internal hole tracking within
struct drm_mm_node by using an accessor for hole_follows.
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: NJoonas Lahtinen <joonas.lahtinen@linux.intel.com>
[danvet: resolve conflicts in i915_vma.c]
Signed-off-by: NDaniel 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: NChris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: NJoonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-34-chris@chris-wilson.co.uk

Since we mandate a strict reverse-order of drm_mm_scan_remove_block()
after drm_mm_scan_add_block() we can further simplify the list
manipulations when generating the temporary scan-hole.

v2: Highlight the games being played with the lists to track the scan
holes without allocation.
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: NJoonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-33-chris@chris-wilson.co.uk

For power-of-two alignments, we can avoid the 64bit divide and do a
simple bitwise add instead.

v2: s/alignment_mask/remainder_mask/
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: NJoonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-32-chris@chris-wilson.co.uk

Compute the minimal required hole during scan and only evict those nodes
that overlap. This enables us to reduce the number of nodes we need to
evict to the bare minimum.
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: NJoonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-31-chris@chris-wilson.co.uk