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>

drm_mm_debug_table will print the memory manager state
in table allowing to give a snapshot of the manager at
given point in time. Usefull for debugging.
Signed-off-by: NJerome Glisse <jglisse@redhat.com>
Signed-off-by: NDave Airlie <airlied@redhat.com>

These are required for changes to TTM.
Signed-off-by: NJerome Glisse <jglisse@redhat.com>
Signed-off-by: NDave Airlie <airlied@redhat.com>

Free and used were reversed.
Signed-off-by: NDave Airlie <airlied@redhat.com>

unused_nodes modification needs to be protected by unused_lock spinlock.
Here is an example of an usage where there is no such protection without
this patch.

  Process 1: 1-drm_mm_pre_get(this function modify unused_nodes list)
             2-spin_lock(spinlock protecting mm struct)
             3-drm_mm_put_block(this function might modify unused_nodes
               list but doesn't protect modification with unused_lock)
             4-spin_unlock(spinlock protecting mm struct)
  Process2:  1-drm_mm_pre_get(this function modify unused_nodes list)
At this point Process1 & Process2 might both be doing modification to
unused_nodes list. This patch add unused_lock protection into
drm_mm_put_block to avoid such issue.
Signed-off-by: NJerome Glisse <jglisse@redhat.com>
Signed-off-by: NDave Airlie <airlied@redhat.com>

This adds code to the drm_mm to talk to debugfs, and adds
support to radeon to add the VRAM and GTT mm lists to debugfs.

I tested with spinlock debugging and it doesn't give out.
Signed-off-by: NDave Airlie <airlied@redhat.com>

also for the atomic path by using a common code-path.
Signed-off-by: NThomas Hellstrom <thellstrom@vmware.com>
Signed-off-by: NDave Airlie <airlied@redhat.com>

If the block needs an alignment but otherwise fits exactly into the tail,
then the split-off block from the start would remain marked as non-free.
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Acked-by: NThomas Hellstrom <thellstrom@vmware.com>
Signed-off-by: NDave Airlie <airlied@redhat.com>

this is a TTM preparation patch, it rearranges the mm and
add operations needed to do mm operations in atomic context.
Signed-off-by: NThomas Hellstrom <thellstrom@vmware.com>
Signed-off-by: NDave Airlie <airlied@redhat.com>

Add mode setting support to the DRM layer.

This is a fairly big chunk of work that allows DRM drivers to provide
full output control and configuration capabilities to userspace.  It was
motivated by several factors:
  - the fb layer's APIs aren't suited for anything but simple
    configurations
  - coordination between the fb layer, DRM layer, and various userspace
    drivers is poor to non-existent (radeonfb excepted)
  - user level mode setting drivers makes displaying panic & oops
    messages more difficult
  - suspend/resume of graphics state is possible in many more
    configurations with kernel level support

This commit just adds the core DRM part of the mode setting APIs.
Driver specific commits using these new structure and APIs will follow.

Co-authors: Jesse Barnes <jbarnes@virtuousgeek.org>, Jakob Bornecrantz <jakob@tungstengraphics.com>
Contributors: Alan Hourihane <alanh@tungstengraphics.com>, Maarten Maathuis <madman2003@gmail.com>
Signed-off-by: NJesse Barnes <jbarnes@virtuousgeek.org>
Signed-off-by: NEric Anholt <eric@anholt.net>
Signed-off-by: NDave Airlie <airlied@redhat.com>

GEM allows the creation of persistent buffer objects accessible by the
graphics device through new ioctls for managing execution of commands on the
device.  The userland API is almost entirely driver-specific to ensure that
any driver building on this model can easily map the interface to individual
driver requirements.

GEM is used by the 2d driver for managing its internal state allocations and
will be used for pixmap storage to reduce memory consumption and enable
zero-copy GLX_EXT_texture_from_pixmap, and in the 3d driver is used to enable
GL_EXT_framebuffer_object and GL_ARB_pixel_buffer_object.
Signed-off-by: NEric Anholt <eric@anholt.net>
Signed-off-by: NDave Airlie <airlied@redhat.com>

With the coming of kernel based modesetting and the memory manager stuff,
the everything in one directory approach was getting very ugly and
starting to be unmanageable.

This restructures the drm along the lines of other kernel components.

It creates a drivers/gpu/drm directory and moves the hw drivers into
subdirectores. It moves the includes into an include/drm, and
sets up the unifdef for the userspace headers we should be exporting.
Signed-off-by: NDave Airlie <airlied@redhat.com>

Signed-off-by: NDave Airlie <airlied@linux.ie>

* Convert files to UTF-8.

  * Also correct some people's names
    (one example is Eißfeldt, which was found in a source file.
    Given that the author used an ß at all in a source file
    indicates that the real name has in fact a 'ß' and not an 'ss',
    which is commonly used as a substitute for 'ß' when limited to
    7bit.)

  * Correct town names (Goettingen -> Göttingen)

  * Update Eberhard Mönkeberg's address (http://lkml.org/lkml/2007/1/8/313)
Signed-off-by: NJan Engelhardt <jengelh@gmx.de>
Signed-off-by: NAdrian Bunk <bunk@kernel.org>

Signed-off-by: NDave Airlie <airlied@linux.ie>

This patch removes two unused exports.
Signed-off-by: NAdrian Bunk <bunk@stusta.de>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NDave Airlie <airlied@linux.ie>

Remove the memory manager parameter from the put_block function, as this
makes the client code a lot cleaner. Prepare buffer manager for lock and
unlock calls.
Fix buggy aligned allocations.
Remove the stupid root_node field from the core memory manager.
Support multi-page buffer offset alignments
Add improved alignment functionality to the core memory manager.
This makes an allocated block actually align itself and returns any
wasted space to the manager.
Signed-off-by: NDave Airlie <airlied@linux.ie>

Thanks to Andrew Morton for pointing these out, I've fixed a few his patch
missed.
Signed-off-by: NAndrew Morton <akpm@osdl.org>
Signed-off-by: NDave Airlie <airlied@linux.ie>

This adds the DRM hashtable and simple memory manager implementations from
Tungsten Graphics, this is NOT the new memory manager, this is a replacement
for the SIS and VIA memory managers.
Signed-off-by: NDave Airlie <airlied@linux.ie>