From 2f7e87692e0441abf27a9714991edd136e87363a Mon Sep 17 00:00:00 2001 From: Chris Wilson Date: Mon, 21 May 2018 09:21:28 +0100 Subject: drm/mm: Reject over-sized allocation requests early As we keep an rbtree of available holes sorted by their size, we can very easily determine if there is any hole large enough that might satisfy the allocation request. This helps when dealing with a highly fragmented address space and a request for a search by address. To cache the largest size, we convert into the cached rbtree variant which tracks the leftmost node for us. However, currently we sorted into ascending size order so the leftmost node is the smallest, and so to make it the largest hole we need to invert our sorting. Signed-off-by: Chris Wilson Cc: Joonas Lahtinen Reviewed-by: Joonas Lahtinen Link: https://patchwork.freedesktop.org/patch/msgid/20180521082131.13744-1-chris@chris-wilson.co.uk --- drivers/gpu/drm/drm_mm.c | 82 +++++++++++++++++++++++++++++++++--------------- 1 file changed, 57 insertions(+), 25 deletions(-) (limited to 'drivers/gpu/drm/drm_mm.c') diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c index 3166026a1874..7b4ad05fe1c0 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 @@ -457,6 +486,9 @@ int drm_mm_insert_node_in_range(struct drm_mm * const mm, 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; @@ -587,9 +619,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 +917,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. */ -- cgit From 83bc4ec37210b17bd611a58968b2ce0e9cc7f251 Mon Sep 17 00:00:00 2001 From: Chris Wilson Date: Mon, 21 May 2018 09:21:29 +0100 Subject: drm/mm: Add a search-by-address variant to only inspect a single hole Searching for an available hole by address is slow, as there no guarantee that a hole will be available and so we must walk over all nodes in the rbtree before we determine the search was futile. In many cases, the caller doesn't strictly care for the highest available hole and was just opportunistically laying out the address space in a preferred order. In such cases, the caller can accept any address and would rather do so then do a slow walk. To be able to mix search strategies, the caller wants to tell the drm_mm how long to spend on the search. Without a good guide for what should be the best split, start with a request to try once at most. That is return the top-most (or lowest) hole if it fulfils the alignment and size requirements. v2: Documentation, by why of example (selftests) and kerneldoc. Signed-off-by: Chris Wilson Cc: Joonas Lahtinen Reviewed-by: Joonas Lahtinen Link: https://patchwork.freedesktop.org/patch/msgid/20180521082131.13744-2-chris@chris-wilson.co.uk --- drivers/gpu/drm/drm_mm.c | 9 +++- drivers/gpu/drm/selftests/drm_mm_selftests.h | 2 + drivers/gpu/drm/selftests/test-drm_mm.c | 71 ++++++++++++++++++++++++++++ include/drm/drm_mm.h | 32 +++++++++++++ 4 files changed, 112 insertions(+), 2 deletions(-) (limited to 'drivers/gpu/drm/drm_mm.c') diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c index 7b4ad05fe1c0..3cc5fbd78ee2 100644 --- a/drivers/gpu/drm/drm_mm.c +++ b/drivers/gpu/drm/drm_mm.c @@ -480,6 +480,7 @@ 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); @@ -492,9 +493,13 @@ int drm_mm_insert_node_in_range(struct drm_mm * const mm, 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; diff --git a/drivers/gpu/drm/selftests/drm_mm_selftests.h b/drivers/gpu/drm/selftests/drm_mm_selftests.h index 54acc117550c..6b943ea1c57d 100644 --- a/drivers/gpu/drm/selftests/drm_mm_selftests.h +++ b/drivers/gpu/drm/selftests/drm_mm_selftests.h @@ -19,7 +19,9 @@ selftest(align64, igt_align64) selftest(evict, igt_evict) selftest(evict_range, igt_evict_range) selftest(bottomup, igt_bottomup) +selftest(lowest, igt_lowest) selftest(topdown, igt_topdown) +selftest(highest, igt_highest) selftest(color, igt_color) selftest(color_evict, igt_color_evict) selftest(color_evict_range, igt_color_evict_range) diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c index 7cc935d7b7aa..f69d8da222b0 100644 --- a/drivers/gpu/drm/selftests/test-drm_mm.c +++ b/drivers/gpu/drm/selftests/test-drm_mm.c @@ -1825,6 +1825,77 @@ err: return ret; } +static int __igt_once(unsigned int mode) +{ + struct drm_mm mm; + struct drm_mm_node rsvd_lo, rsvd_hi, node; + int err; + + drm_mm_init(&mm, 0, 7); + + memset(&rsvd_lo, 0, sizeof(rsvd_lo)); + rsvd_lo.start = 1; + rsvd_lo.size = 1; + err = drm_mm_reserve_node(&mm, &rsvd_lo); + if (err) { + pr_err("Could not reserve low node\n"); + goto err; + } + + memset(&rsvd_hi, 0, sizeof(rsvd_hi)); + rsvd_hi.start = 5; + rsvd_hi.size = 1; + err = drm_mm_reserve_node(&mm, &rsvd_hi); + if (err) { + pr_err("Could not reserve low node\n"); + goto err_lo; + } + + if (!drm_mm_hole_follows(&rsvd_lo) || !drm_mm_hole_follows(&rsvd_hi)) { + pr_err("Expected a hole after lo and high nodes!\n"); + err = -EINVAL; + goto err_hi; + } + + memset(&node, 0, sizeof(node)); + err = drm_mm_insert_node_generic(&mm, &node, + 2, 0, 0, + mode | DRM_MM_INSERT_ONCE); + if (!err) { + pr_err("Unexpectedly inserted the node into the wrong hole: node.start=%llx\n", + node.start); + err = -EINVAL; + goto err_node; + } + + err = drm_mm_insert_node_generic(&mm, &node, 2, 0, 0, mode); + if (err) { + pr_err("Could not insert the node into the available hole!\n"); + err = -EINVAL; + goto err_hi; + } + +err_node: + drm_mm_remove_node(&node); +err_hi: + drm_mm_remove_node(&rsvd_hi); +err_lo: + drm_mm_remove_node(&rsvd_lo); +err: + drm_mm_takedown(&mm); + return err; +} + +static int igt_lowest(void *ignored) +{ + return __igt_once(DRM_MM_INSERT_LOW); +} + +static int igt_highest(void *ignored) +{ + return __igt_once(DRM_MM_INSERT_HIGH); +} + static void separate_adjacent_colors(const struct drm_mm_node *node, unsigned long color, u64 *start, diff --git a/include/drm/drm_mm.h b/include/drm/drm_mm.h index e3aa3bfd4860..2c3bbb43c7d1 100644 --- a/include/drm/drm_mm.h +++ b/include/drm/drm_mm.h @@ -109,6 +109,38 @@ enum drm_mm_insert_mode { * Allocates the node from the bottom of the found hole. */ DRM_MM_INSERT_EVICT, + + /** + * @DRM_MM_INSERT_ONCE: + * + * Only check the first hole for suitablity and report -ENOSPC + * immediately otherwise, rather than check every hole until a + * suitable one is found. Can only be used in conjunction with another + * search method such as DRM_MM_INSERT_HIGH or DRM_MM_INSERT_LOW. + */ + DRM_MM_INSERT_ONCE = BIT(31), + + /** + * @DRM_MM_INSERT_HIGHEST: + * + * Only check the highest hole (the hole with the largest address) and + * insert the node at the top of the hole or report -ENOSPC if + * unsuitable. + * + * Does not search all holes. + */ + DRM_MM_INSERT_HIGHEST = DRM_MM_INSERT_HIGH | DRM_MM_INSERT_ONCE, + + /** + * @DRM_MM_INSERT_LOWEST: + * + * Only check the lowest hole (the hole with the smallest address) and + * insert the node at the bottom of the hole or report -ENOSPC if + * unsuitable. + * + * Does not search all holes. + */ + DRM_MM_INSERT_LOWEST = DRM_MM_INSERT_LOW | DRM_MM_INSERT_ONCE, }; /** -- cgit