diff options
| author | Chris Wilson <chris@chris-wilson.co.uk> | 2016-08-03 16:04:09 +0100 |
|---|---|---|
| committer | Daniel Vetter <daniel.vetter@ffwll.ch> | 2016-08-08 10:05:16 +0200 |
| commit | 202b52b7fbf70858609ec20829c7d69a13ffa351 (patch) | |
| tree | 5d4d2383e745fdd75fffeb053974eacfbe4ccdc7 /include/drm/drm_mm.h | |
| parent | 1d776851a6949abd85ba305514612fed16ff2459 (diff) | |
drm: Track drm_mm nodes with an interval tree
In addition to the last-in/first-out stack for accessing drm_mm nodes,
we occasionally and in the future often want to find a drm_mm_node by an
address. To do so efficiently we need to track the nodes in an interval
tree - lookups for a particular address will then be O(lg(N)), where N
is the number of nodes in the range manager as opposed to O(N).
Insertion however gains an extra O(lg(N)) step for all nodes
irrespective of whether the interval tree is in use. For future i915
patches, eliminating the linear walk is a significant improvement.
v2: Use generic interval-tree template for u64 and faster insertion.
Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
Cc: David Herrmann <dh.herrmann@gmail.com>
Cc: dri-devel@lists.freedesktop.org
Reviewed-by: David Herrmann <dh.herrmann@gmail.com>
Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/1470236651-678-1-git-send-email-chris@chris-wilson.co.uk
Diffstat (limited to 'include/drm/drm_mm.h')
| -rw-r--r-- | include/drm/drm_mm.h | 12 |
1 files changed, 12 insertions, 0 deletions
diff --git a/include/drm/drm_mm.h b/include/drm/drm_mm.h index fc65118e5077..205ddcf6d55d 100644 --- a/include/drm/drm_mm.h +++ b/include/drm/drm_mm.h @@ -37,6 +37,7 @@ * Generic range manager structs */ #include <linux/bug.h> +#include <linux/rbtree.h> #include <linux/kernel.h> #include <linux/list.h> #include <linux/spinlock.h> @@ -61,6 +62,7 @@ enum drm_mm_allocator_flags { struct drm_mm_node { struct list_head node_list; struct list_head hole_stack; + struct rb_node rb; unsigned hole_follows : 1; unsigned scanned_block : 1; unsigned scanned_prev_free : 1; @@ -70,6 +72,7 @@ struct drm_mm_node { unsigned long color; u64 start; u64 size; + u64 __subtree_last; struct drm_mm *mm; }; @@ -79,6 +82,9 @@ struct drm_mm { /* 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; + /* Keep an interval_tree for fast lookup of drm_mm_nodes by address. */ + struct rb_root interval_tree; + unsigned int scan_check_range : 1; unsigned scan_alignment; unsigned long scan_color; @@ -295,6 +301,12 @@ void drm_mm_init(struct drm_mm *mm, void drm_mm_takedown(struct drm_mm *mm); bool drm_mm_clean(struct drm_mm *mm); +struct drm_mm_node * +drm_mm_interval_first(struct drm_mm *mm, u64 start, u64 last); + +struct drm_mm_node * +drm_mm_interval_next(struct drm_mm_node *node, u64 start, u64 last); + void drm_mm_init_scan(struct drm_mm *mm, u64 size, unsigned alignment, |