drm: mm: track free areas implicitly

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: Daniel Vetter <daniel.vetter@ffwll.ch>
Signed-off-by: Dave Airlie <airlied@redhat.com>

1 files changed, 12 insertions, 9 deletions

diff --git a/include/drm/drm_mm.h b/include/drm/drm_mm.h
index 0d791462f7b2..34fa36f2de70 100644
--- a/include/drm/drm_mm.h
+++ b/include/drm/drm_mm.h
@@ -42,23 +42,24 @@
 #endif
 
 struct drm_mm_node {
-        struct list_head free_stack;
         struct list_head node_list;
-        unsigned free : 1;
+        struct list_head hole_stack;
+        unsigned hole_follows : 1;
         unsigned scanned_block : 1;
         unsigned scanned_prev_free : 1;
         unsigned scanned_next_free : 1;
+        unsigned scanned_preceeds_hole : 1;
         unsigned long start;
         unsigned long size;
         struct drm_mm *mm;
 };
 
 struct drm_mm {
-        /* List of free memory blocks, most recently freed ordered. */
-        struct list_head free_stack;
-        /* List of all memory nodes, ordered according to the (increasing) start
-         * address of the memory node. */
-        struct list_head node_list;
+        /* List of all memory nodes that immediatly preceed a free hole. */
+        struct list_head hole_stack;
+        /* head_node.node_list is the list of all memory nodes, ordered
+         * according to the (increasing) start address of the memory node. */
+        struct drm_mm_node head_node;
         struct list_head unused_nodes;
         int num_unused;
         spinlock_t unused_lock;
@@ -74,9 +75,11 @@ struct drm_mm {
 
 static inline bool drm_mm_initialized(struct drm_mm *mm)
 {
-        return mm->free_stack.next;
+        return mm->hole_stack.next;
 }
-
+#define drm_mm_for_each_node(entry, mm) list_for_each_entry(entry, \
+                                                &(mm)->head_node.node_list, \
+                                                node_list);
 /*
  * Basic range manager support (drm_mm.c)
  */