summaryrefslogtreecommitdiff
path: root/drivers/gpu/drm/drm_mm.c
diff options
context:
space:
mode:
Diffstat (limited to 'drivers/gpu/drm/drm_mm.c')
-rw-r--r--drivers/gpu/drm/drm_mm.c91
1 files changed, 64 insertions, 27 deletions
diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c
index 3166026a1874..3cc5fbd78ee2 100644
--- a/drivers/gpu/drm/drm_mm.c
+++ b/drivers/gpu/drm/drm_mm.c
@@ -239,6 +239,32 @@ static void drm_mm_interval_tree_add_node(struct drm_mm_node *hole_node,
#define HOLE_SIZE(NODE) ((NODE)->hole_size)
#define HOLE_ADDR(NODE) (__drm_mm_hole_node_start(NODE))
+static u64 rb_to_hole_size(struct rb_node *rb)
+{
+ return rb_entry(rb, struct drm_mm_node, rb_hole_size)->hole_size;
+}
+
+static void insert_hole_size(struct rb_root_cached *root,
+ struct drm_mm_node *node)
+{
+ struct rb_node **link = &root->rb_root.rb_node, *rb = NULL;
+ u64 x = node->hole_size;
+ bool first = true;
+
+ while (*link) {
+ rb = *link;
+ if (x > rb_to_hole_size(rb)) {
+ link = &rb->rb_left;
+ } else {
+ link = &rb->rb_right;
+ first = false;
+ }
+ }
+
+ rb_link_node(&node->rb_hole_size, rb, link);
+ rb_insert_color_cached(&node->rb_hole_size, root, first);
+}
+
static void add_hole(struct drm_mm_node *node)
{
struct drm_mm *mm = node->mm;
@@ -247,7 +273,7 @@ static void add_hole(struct drm_mm_node *node)
__drm_mm_hole_node_end(node) - __drm_mm_hole_node_start(node);
DRM_MM_BUG_ON(!drm_mm_hole_follows(node));
- RB_INSERT(mm->holes_size, rb_hole_size, HOLE_SIZE);
+ insert_hole_size(&mm->holes_size, node);
RB_INSERT(mm->holes_addr, rb_hole_addr, HOLE_ADDR);
list_add(&node->hole_stack, &mm->hole_stack);
@@ -258,7 +284,7 @@ static void rm_hole(struct drm_mm_node *node)
DRM_MM_BUG_ON(!drm_mm_hole_follows(node));
list_del(&node->hole_stack);
- rb_erase(&node->rb_hole_size, &node->mm->holes_size);
+ rb_erase_cached(&node->rb_hole_size, &node->mm->holes_size);
rb_erase(&node->rb_hole_addr, &node->mm->holes_addr);
node->hole_size = 0;
@@ -282,38 +308,39 @@ static inline u64 rb_hole_size(struct rb_node *rb)
static struct drm_mm_node *best_hole(struct drm_mm *mm, u64 size)
{
- struct rb_node *best = NULL;
- struct rb_node **link = &mm->holes_size.rb_node;
+ struct rb_node *rb = mm->holes_size.rb_root.rb_node;
+ struct drm_mm_node *best = NULL;
- while (*link) {
- struct rb_node *rb = *link;
+ do {
+ struct drm_mm_node *node =
+ rb_entry(rb, struct drm_mm_node, rb_hole_size);
- if (size <= rb_hole_size(rb)) {
- link = &rb->rb_left;
- best = rb;
+ if (size <= node->hole_size) {
+ best = node;
+ rb = rb->rb_right;
} else {
- link = &rb->rb_right;
+ rb = rb->rb_left;
}
- }
+ } while (rb);
- return rb_hole_size_to_node(best);
+ return best;
}
static struct drm_mm_node *find_hole(struct drm_mm *mm, u64 addr)
{
+ struct rb_node *rb = mm->holes_addr.rb_node;
struct drm_mm_node *node = NULL;
- struct rb_node **link = &mm->holes_addr.rb_node;
- while (*link) {
+ while (rb) {
u64 hole_start;
- node = rb_hole_addr_to_node(*link);
+ node = rb_hole_addr_to_node(rb);
hole_start = __drm_mm_hole_node_start(node);
if (addr < hole_start)
- link = &node->rb_hole_addr.rb_left;
+ rb = node->rb_hole_addr.rb_left;
else if (addr > hole_start + node->hole_size)
- link = &node->rb_hole_addr.rb_right;
+ rb = node->rb_hole_addr.rb_right;
else
break;
}
@@ -326,9 +353,6 @@ first_hole(struct drm_mm *mm,
u64 start, u64 end, u64 size,
enum drm_mm_insert_mode mode)
{
- if (RB_EMPTY_ROOT(&mm->holes_size))
- return NULL;
-
switch (mode) {
default:
case DRM_MM_INSERT_BEST:
@@ -355,7 +379,7 @@ next_hole(struct drm_mm *mm,
switch (mode) {
default:
case DRM_MM_INSERT_BEST:
- return rb_hole_size_to_node(rb_next(&node->rb_hole_size));
+ return rb_hole_size_to_node(rb_prev(&node->rb_hole_size));
case DRM_MM_INSERT_LOW:
return rb_hole_addr_to_node(rb_next(&node->rb_hole_addr));
@@ -426,6 +450,11 @@ int drm_mm_reserve_node(struct drm_mm *mm, struct drm_mm_node *node)
}
EXPORT_SYMBOL(drm_mm_reserve_node);
+static u64 rb_to_hole_size_or_zero(struct rb_node *rb)
+{
+ return rb ? rb_to_hole_size(rb) : 0;
+}
+
/**
* drm_mm_insert_node_in_range - ranged search for space and insert @node
* @mm: drm_mm to allocate from
@@ -451,18 +480,26 @@ int drm_mm_insert_node_in_range(struct drm_mm * const mm,
{
struct drm_mm_node *hole;
u64 remainder_mask;
+ bool once;
DRM_MM_BUG_ON(range_start >= range_end);
if (unlikely(size == 0 || range_end - range_start < size))
return -ENOSPC;
+ if (rb_to_hole_size_or_zero(rb_first_cached(&mm->holes_size)) < size)
+ return -ENOSPC;
+
if (alignment <= 1)
alignment = 0;
+ once = mode & DRM_MM_INSERT_ONCE;
+ mode &= ~DRM_MM_INSERT_ONCE;
+
remainder_mask = is_power_of_2(alignment) ? alignment - 1 : 0;
- for (hole = first_hole(mm, range_start, range_end, size, mode); hole;
- hole = next_hole(mm, hole, mode)) {
+ for (hole = first_hole(mm, range_start, range_end, size, mode);
+ hole;
+ hole = once ? NULL : next_hole(mm, hole, mode)) {
u64 hole_start = __drm_mm_hole_node_start(hole);
u64 hole_end = hole_start + hole->hole_size;
u64 adj_start, adj_end;
@@ -587,9 +624,9 @@ void drm_mm_replace_node(struct drm_mm_node *old, struct drm_mm_node *new)
if (drm_mm_hole_follows(old)) {
list_replace(&old->hole_stack, &new->hole_stack);
- rb_replace_node(&old->rb_hole_size,
- &new->rb_hole_size,
- &mm->holes_size);
+ rb_replace_node_cached(&old->rb_hole_size,
+ &new->rb_hole_size,
+ &mm->holes_size);
rb_replace_node(&old->rb_hole_addr,
&new->rb_hole_addr,
&mm->holes_addr);
@@ -885,7 +922,7 @@ void drm_mm_init(struct drm_mm *mm, u64 start, u64 size)
INIT_LIST_HEAD(&mm->hole_stack);
mm->interval_tree = RB_ROOT_CACHED;
- mm->holes_size = RB_ROOT;
+ mm->holes_size = RB_ROOT_CACHED;
mm->holes_addr = RB_ROOT;
/* Clever trick to avoid a special case in the free hole tracking. */
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-12 15:23:40 +0000