drm: Improve drm_mm search (and fix topdown allocation) with rbtrees

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 <[email protected]>
Reviewed-by: Joonas Lahtinen <[email protected]>
Cc: Alex Deucher <[email protected]>
Cc: "Christian König" <[email protected]>
Cc: David Airlie <[email protected]>
Cc: Russell King <[email protected]>
Cc: Daniel Vetter <[email protected]>
Cc: Jani Nikula <[email protected]>
Cc: Sean Paul <[email protected]>
Cc: Lucas Stach <[email protected]>
Cc: Christian Gmeiner <[email protected]>
Cc: Rob Clark <[email protected]>
Cc: Thierry Reding <[email protected]>
Cc: Stephen Warren <[email protected]>
Cc: Alexandre Courbot <[email protected]>
Cc: Eric Anholt <[email protected]>
Cc: Sinclair Yeh <[email protected]>
Cc: Thomas Hellstrom <[email protected]>
Reviewed-by: Alex Deucher <[email protected]>
Reviewed-by: Sinclair Yeh <[email protected]> # vmwgfx
Reviewed-by: Lucas Stach <[email protected]> #etnaviv
Signed-off-by: Daniel Vetter <[email protected]>
Link: http://patchwork.freedesktop.org/patch/msgid/[email protected]

0 files changed, 0 insertions, 0 deletions