The drm_mm debugfs output is difficult to read as two different formats
are used for the addresses:

0x00000080000000-0x0000008000b000: 45056: used
0x8000b000-0x80016000: 45056: free
0x00000080016000-0x0000008001b000: 20480: used
0x8001b000-0x817a1000: 24666112: free
0x000000817a1000-0x000000817a8000: 28672: used
0x000000817a8000-0x00000081ba8000: 4194304: used

Fix this by using %#018llx for all addresses, thus making the output:

0x0000000080000000-0x000000008000b000: 45056: used
0x000000008000b000-0x0000000080016000: 45056: free
0x0000000080016000-0x000000008001b000: 20480: used
0x000000008001b000-0x00000000817a1000: 24666112: free
0x00000000817a1000-0x00000000817a8000: 28672: used
0x00000000817a8000-0x0000000081ba8000: 4194304: used
Signed-off-by: NRussell King <rmk+kernel@arm.linux.org.uk>
Reviewed-by: NAlex Deucher <alexander.deucher@amd.com>
Signed-off-by: NDave Airlie <airlied@redhat.com>

bad argument if(tmp)... in check_free_hole

fix oops: kernel BUG at drivers/gpu/drm/drm_mm.c:305!

[airlied: excellent, this was my task for today].
Signed-off-by: NKrzysztof Kolasa <kkolasa@winsoft.pl>
Reviewed-by: NChris wilson <chris@chris-wilson.co.uk>
Signed-off-by: NDave Airlie <airlied@redhat.com>

The current implementation is limited by the number of addresses that
fit into an unsigned long. This causes problems on 32-bit Tegra where
unsigned long is 32-bit but drm_mm is used to manage an IOVA space of
4 GiB. Given the 32-bit limitation, the range is limited to 4 GiB - 1
(or 4 GiB - 4 KiB for page granularity).

This commit changes the start and size of the range to be an unsigned
64-bit integer, thus allowing much larger ranges to be supported.

[airlied: fix i915 warnings and coloring callback]
Signed-off-by: NThierry Reding <treding@nvidia.com>
Reviewed-by: NAlex Deucher <alexander.deucher@amd.com>
Reviewed-by: NChris Wilson <chris@chris-wilson.co.uk>
Signed-off-by: NDave Airlie <airlied@redhat.com>

fixupo

Jesse's BIOS fb reconstruction code actually relies on the -ENOSPC
return value to detect overlapping framebuffers (which the bios uses
always when lighting up more than one screen). All this fanciness
happens in intel_alloc_plane_obj in intel_display.c.

Since no one else uses this we can safely remove the WARN without
repercussions.
Reported-by: NBen Widawsky <benjamin.widawsky@intel.com>
Tested-by: NBen Widawsky <ben@bwidawsk.net>
Cc: Jesse Barnes <jbarnes@virtuousgeek.org>
Cc: Dave Airlie <airlied@redhat.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Acked-by: NDave Airlie <airlied@redhat.com>
Signed-off-by: NJani Nikula <jani.nikula@intel.com>

entry->size is the size of the node, not the size of the hole after it.
So the code would actually find the hole which can satisfy the
constraints and which is preceded by the smallest node, not the smallest
hole satisfying the constraints.
Reported-by: N"Huang, FrankR" <FrankR.Huang@amd.com>
Signed-off-by: NMichel Dänzer <michel.daenzer@amd.com>
Signed-off-by: NDave Airlie <airlied@redhat.com>

Clients like i915 need to segregate cache domains within the GTT which
can lead to small amounts of fragmentation. By allocating the uncached
buffers from the bottom and the cacheable buffers from the top, we can
reduce the amount of wasted space and also optimize allocation of the
mappable portion of the GTT to only those buffers that require CPU
access through the GTT.

For other drivers, allocating small bos from one end and large ones
from the other helps improve the quality of fragmentation.

Based on drm_mm work by Chris Wilson.

v3: Changed to use a TTM placement flag
v2: Updated kerneldoc

Cc: Chris Wilson <chris@chris-wilson.co.uk>
Cc: Ben Widawsky <ben@bwidawsk.net>
Cc: Christian König <deathsimple@vodafone.de>
Signed-off-by: NLauri Kasanen <cand@gmx.com>
Signed-off-by: NDavid Airlie <airlied@redhat.com>

While at it do a tiny bit of interface cleanup and convert boolean
return values to bool. With this patch all exported functions and inline
helpers which are part of the drm_mm public interface are documented.

Also drop superflous extern function modifiers since most of drm_mm.h
doesn't use them - more consistent that way.
Reviewed-by: NAlex Deucher <alexander.deucher@amd.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>

kerneldoc polish will follow in the next patch.

Hopefully documenting the lru scan support a bit better spurs someone
to give this a shot in the ttm eviction code. At least in i915 it
helped quite a lot with memory thrashing on platforms where eviction
was (we've fixed that too meanwhile) fairly expensive.
Reviewed-by: NAlex Deucher <alexander.deucher@amd.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>

This was missed in

commit c700c67b
Author: David Herrmann <dh.herrmann@gmail.com>
Date:   Sat Jul 27 13:39:28 2013 +0200

    drm/mm: remove unused API

Cc: David Herrmann <dh.herrmann@gmail.com>
Reviewed-by: NAlex Deucher <alexander.deucher@amd.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>

The conditional is usually a recoverable driver bug, and so WARNing, and
preventing the drm_mm code from doing potential damage (BUG) is
desirable.

This issue was hit and fixed twice while developing the i915 multiple
address space code. The first fix is the patch just before this, and is
hit on an not frequently occuring error path. Another was fixed during
patch iteration, so it's hard to see from the patch:

commit c6cfb325
Author: Ben Widawsky <ben@bwidawsk.net>
Date:   Fri Jul 5 14:41:06 2013 -0700

    drm/i915: Embed drm_mm_node in i915 gem obj

From the intel-gfx mailing list, we discussed this:
References: <20130705191235.GA3057@bwidawsk.net>

Cc: Dave Airlie <airlied@redhat.com>
CC: <dri-devel@lists.freedesktop.org>
Acked-by: NChris Wilson <chris@chris-wilson.co.uk>
Signed-off-by: NBen Widawsky <ben@bwidawsk.net>
Acked-by: NDave Airlie <airlied@redhat.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>

We used to pre-allocate drm_mm nodes and save them in a linked list for
later usage so we always have spare ones in atomic contexts. However, this
is really racy if multiple threads are in an atomic context at the same
time and we don't have enough spare nodes. Moreover, all remaining users
run in user-context and just lock drm_mm with a spinlock. So we can easily
preallocate the node, take the spinlock and insert the node.

This may have worked well with BKL in place, however, with today's
infrastructure it really doesn't make any sense. Besides, most users can
easily embed drm_mm_node into their objects so no allocation is needed at
all.

Thus, remove the old pre-alloc API and all the helpers that it provides.
Drivers have already been converted and we should not use the old API for
new code, anymore.
Signed-off-by: NDavid Herrmann <dh.herrmann@gmail.com>
Acked-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Signed-off-by: NDave Airlie <airlied@redhat.com>

Add a "best_match" flag similar to the drm_mm_search_*() helpers so we
can convert TTM to use them in follow up patches. We can also inline the
non-generic helpers and move them into the header to allow compile-time
optimizations.

To make calls to drm_mm_{search,insert}_node() more readable, this
converts the boolean argument to a flagset. There are pending patches that
add additional flags for top-down allocators and more.

v2:
 - use flag parameter instead of boolean "best_match"
 - convert *_search_free() helpers to also use flags argument
Signed-off-by: NDavid Herrmann <dh.herrmann@gmail.com>
Reviewed-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Signed-off-by: NDave Airlie <airlied@redhat.com>

With the previous patch we no longer actually create a node, we simply
find the correct hole and occupy it. This very well could have been
squashed with the last patch, but since I already had David's review, I
figured it's easiest to keep it distinct.

Also update the users in i915. Conveniently this is the only user of the
interface.

CC: David Airlie <airlied@linux.ie>
CC: <dri-devel@lists.freedesktop.org>
Signed-off-by: NBen Widawsky <ben@bwidawsk.net>
Acked-by: NDavid Airlie <airlied@linux.ie>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>

For an upcoming patch where we introduce the i915 VMA, it's ideal to
have the drm_mm_node as part of the VMA struct (ie. it's pre-allocated).
Part of the conversion to VMAs is to kill off obj->gtt_space. Doing this
will break a bunch of code, but amongst them are 2 callers of
drm_mm_create_block(), both related to stolen memory.

It also allows us to embed the drm_mm_node into the object currently
which provides a nice transition over to the new code.

v2: Reordered to do before ripping out obj->gtt_offset.
Some minor cleanups made available because of reordering.

v3: s/continue/break on failed stolen node allocation (David)
Set obj->gtt_space on failed node allocation (David)
Only unref stolen (fix double free) on failed create_stolen (David)
Free node, and NULL it in failed create_stolen (David)
Add back accidentally removed newline (David)

CC: <dri-devel@lists.freedesktop.org>
Reviewed-by: NDavid Herrmann <dh.herrmann@gmail.com>
Signed-off-by: NBen Widawsky <ben@bwidawsk.net>
Acked-by: NDavid Airlie <airlied@linux.ie>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>

The usual drm driver has tons of different drm_mm memory managers so the drm
error message in dmesg is pretty useless. WARN instead so that we have the full
backtrace.
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Reviewed-by: NBen Widawsky <ben@bwidawsk.net>
Signed-off-by: NDave Airlie <airlied@redhat.com>

In

commit 3a359f0b
Author: Daniel Vetter <daniel.vetter@ffwll.ch>
Date:   Sat Apr 20 12:08:11 2013 +0200

    drm/mm: fix dump table BUG

I've failed to fix both instances of the regression introduced in

commit 9e8944ab
Author: Chris Wilson <chris@chris-wilson.co.uk>
Date:   Thu Nov 15 11:32:17 2012 +0000

   drm: Introduce an iterator over holes in the drm_mm range manager

Patch this up in the same way by extracting the hole debug logic
into it's own function, since that'll also clarify the logic a bit.

Cc: Chris Wilson <chris@chris-wilson.co.uk>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Signed-off-by: NDave Airlie <airlied@redhat.com>

There is no reason to return "int" as this function never fails.
Furthermore, several drivers (ast, sis) already depend on this.
Signed-off-by: NDavid Herrmann <dh.herrmann@gmail.com>
Reviewed-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Signed-off-by: NDave Airlie <airlied@redhat.com>

In

commit 9e8944ab
Author: Chris Wilson <chris@chris-wilson.co.uk>
Date:   Thu Nov 15 11:32:17 2012 +0000

    drm: Introduce an iterator over holes in the drm_mm range manager

helpers and iterators for hole handling have been introduced with some
debug BUG_ONs sprinkled over. Unfortunately this broke the mm dumper
which unconditionally tried to compute the size of the very first
hole.

While at it unify the code a bit with the hole dumping in the loop.

v2: Extract a hole dump helper.
Reported-by: NChristopher Harvey <charvey@matrox.com>
Cc: Christopher Harvey <charvey@matrox.com>
Cc: Dave Airlie <airlied@redhat.com>
Cc: Chris Wilson <chris@chris-wilson.co.uk>
Cc: stable@vger.kernel.org
Acked-by: NDave Airlie <airlied@redhat.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>

Avoid clobbering adjacent blocks if they happen to expire earlier and
amalgamate together to form the requested hole.

In passing this fixes a regression from
commit ea7b1dd4
Author: Daniel Vetter <daniel.vetter@ffwll.ch>
Date:   Fri Feb 18 17:59:12 2011 +0100

    drm: mm: track free areas implicitly

which swaps the end address for size (with a potential overflow) and
effectively causes the eviction code to clobber almost all earlier
buffers above the evictee.

v2: Check the original hole not the adjusted as the coloring may confuse
us when later searching for the overlapping nodes. Also make sure that
we do apply the range restriction and color adjustment in the same
order for both scanning, searching and insertion.

v3: Send the version that was actually tested.

Note that this seems to be ducttape of decent quality ot paper over
some of our unbind related gpu hangs reported since 3.7. It is not
fully effective though, and certainly doesn't fix the underlying bug.
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Cc: Daniel Vetter <daniel.vetter@ffwll.ch>
[danvet: Added note plus bugzilla link and tested-by.]
Cc: stable@vger.kernel.org
Bugzilla: https://bugs.freedesktop.org/show_bug.cgi?id=55984Tested-by: NNorbert Preining <preining@logic.at>
Acked-by: Dave Airlie <airlied@gmail.com
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>

Required by i915 in order to avoid the allocation in the middle of
manipulating the drm_mm lists.

Use a pair of stubs to preserve the existing EXPORT_SYMBOLs for
backporting; to be removed later.

Cc: Dave Airlie <airlied@redhat.com>
Cc: dri-devel@lists.freedesktop.org
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: NJani Nikula <jani.nikula@intel.com>
[danvet: bikeshedded-away the atomic parameter, it's not yet used
anywhere.]
Acked-by: NDave Airlie <airlied@gmail.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>

This will be used i915 in forthcoming patches in order to measure the
largest contiguous chunk of memory available for enabling chipset
features.

v2: Try to make the macro marginally safer and more readable by not
depending upon the drm_mm_hole_node_end() being non-zero. Note that we
need to open code list_for_each() in order to update the hole_start,
hole_end variable on each iteration and keep the macro sane.

v3: Tidy up few BUG_ONs that fell foul of adding additional tests to
drm_mm_hole_node_start().
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Cc: Dave Airlie <airlied@redhat.com>
Acked-by: NDave Airlie <airlied@redhat.com>
Cc: dri-devel@lists.freedesktop.org
Reviewed-by: NBen Widawsky <ben@bwidawsk.net>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>

To be used later by i915 to preallocate exact blocks of space from the
range manager.
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Cc: Dave Airlie <airlied@redhat.com>
Acked-by: NDave Airlie <airlied@redhat.com>
Cc: dri-devel@lists.freedesktop.org
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>

Convert #include "..." to #include <path/...> in drivers/gpu/.
Signed-off-by: NDavid Howells <dhowells@redhat.com>
Acked-by: NDave Airlie <airlied@redhat.com>
Acked-by: NArnd Bergmann <arnd@arndb.de>
Acked-by: NThomas Gleixner <tglx@linutronix.de>
Acked-by: NPaul E. McKenney <paulmck@linux.vnet.ibm.com>
Acked-by: NDave Jones <davej@redhat.com>

In order to support snoopable memory on non-LLC architectures (so that
we can bind vgem objects into the i915 GATT for example), we have to
avoid the prefetcher on the GPU from crossing memory domains and so
prevent allocation of a snoopable PTE immediately following an uncached
PTE. To do that, we need to extend the range allocator with support for
tracking and segregating different node colours.

This will be used by i915 to segregate memory domains within the GTT.

v2: Now with more drm_mm helpers and less driver interference.
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Cc: Dave Airlie <airlied@redhat.com
Cc: Benjamin Herrenschmidt <benh@kernel.crashing.org>
Cc: Ben Skeggs <bskeggs@redhat.com>
Cc: Jerome Glisse <jglisse@redhat.com>
Cc: Alex Deucher <alexander.deucher@amd.com>
Reviewed-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Signed-off-by: NDave Airlie <airlied@gmail.com>

They need this to get all the EXPORT_SYMBOL variants and THIS_MODULE
Signed-off-by: NPaul Gortmaker <paul.gortmaker@windriver.com>

The looping helper didn't do anything due to a superficial
semicolon. Furthermore one of the two dump functions suffered
from copy&paste fail.

While staring at the code I've also noticed that the replace
helper (currently unused) is a bit broken.
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Signed-off-by: NDave Airlie <airlied@redhat.com>

Fixes generated by 'codespell' and manually reviewed.
Signed-off-by: NLucas De Marchi <lucas.demarchi@profusion.mobi>

With the switch to implicit free space accounting one pointer
got unused when scanning. Use it to create a single-linked list
to ensure correct unwinding of the scan state.
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Signed-off-by: NDave Airlie <airlied@redhat.com>

The old api has a two-step process: First search for a suitable
free hole, then allocate from that specific hole. No user used
this to do anything clever. So drop it for the embeddable variant
of the drm_mm api (the old one retains this ability, for the time
being).

With struct drm_mm_node embedded, we cannot track allocations
anymore by checking for a NULL pointer. So keep track of this
and add a small helper drm_mm_node_allocated.

Also add a function to move allocations between different struct
drm_mm_node.

v2: Implement suggestions by Chris Wilson.
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Signed-off-by: NDave Airlie <airlied@redhat.com>

Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Signed-off-by: NDave Airlie <airlied@redhat.com>

The idea is to track free holes implicitly by marking the allocation
immediatly preceeding a hole.

To avoid an ugly corner case add a dummy head_node to struct drm_mm
to track the hole that spans to complete allocation area when the
memory manager is empty.

To guarantee that there's always a preceeding/following node (that might
be marked as hole_follows == 1), move the mm->node_list list_head to the
head_node.

The main allocator and fair-lru scan code actually becomes simpler.
Only the debug code slightly suffers because free areas are no longer
explicit.

Also add drm_mm_for_each_node (which will be much more useful when
struct drm_mm_node is embeddable).
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Signed-off-by: NDave Airlie <airlied@redhat.com>

Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>

With the code cleanup in

7a6b2896 is the first bad commit
commit 7a6b2896
Author: Daniel Vetter <daniel.vetter@ffwll.ch>
Date:   Fri Jul 2 15:02:15 2010 +0100

    drm_mm: extract check_free_mm_node

I've botched up the range-restriction checks. The result is usually
an X server dying with SIGBUS in libpixman (software fallback rendering).
Change the code to adjust the start and end for range restricted
allocations. IMHO this even makes the code a bit clearer.

Fixes regression bug: https://bugs.freedesktop.org/show_bug.cgi?id=29738Reported-by-Tested-by: NTill MAtthiesen <entropy@everymail.net>
Acked-by: NAlex Deucher <alexdeucher@gmail.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Signed-off-by: NDave Airlie <airlied@redhat.com>

These helper functions can be used to efficiently scan lru list
for eviction. Eviction becomes a three stage process:
1. Scanning through the lru list until a suitable hole has been found.
2. Scan backwards to restore drm_mm consistency and find out which
   objects fall into the hole.
3. Evict the objects that fall into the hole.

These helper functions don't allocate any memory (at the price of
not allowing any other concurrent operations). Hence this can also be
used for ttm (which does lru scanning under a spinlock).

Evicting objects in this fashion should be more fair than the current
approach by i915 (scan the lru for a object large enough to contain
the new object). It's also more efficient than the current approach used
by ttm (uncoditionally evict objects from the lru until there's enough
free space).
Signed-Off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Acked-by: NThomas Hellstrom <thellstrom@vmwgfx.com>
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Signed-off-by: NDave Airlie <airlied@redhat.com>

There are already two copies of this logic. And the new scanning
stuff will add some more. So extract it into a small helper
function.
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Acked-by: NThomas Hellstrom <thellstrom@vmwgfx.com>
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Signed-off-by: NDave Airlie <airlied@redhat.com>

Yeah, I've kinda noticed that fl_entry is the free stack. Still
give it (and the memory node list ml_entry) decent names.
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Acked-by: NThomas Hellstrom <thellstrom@vmwgfx.com>
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Signed-off-by: NDave Airlie <airlied@redhat.com>

Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Acked-by: NThomas Hellstrom <thellstrom@vmwgfx.com>
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Signed-off-by: NDave Airlie <airlied@redhat.com>

Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Acked-by: NThomas Hellstrom <thellstrom@vmwgfx.com>
Signed-off-by: NDave Airlie <airlied@redhat.com>

When searching for free space in a range, the function could return a node extending outside of the given range.
Signed-off-by: NThomas Hellstrom <thellstrom@vmware.com>
Signed-off-by: NDave Airlie <airlied@redhat.com>

This is from bug 25728.

[airlied: I'm just forwarding the patch for review, Thomas, ickle?]
Acked-by: NJerome Glisse <jglisse@redhat.com>
Acked-by: NThomas Hellstrom <thellstrom@vmware.com>
Signed-off-by: NDave Airlie <airlied@redhat.com>