When we evict from the GTT to make room for an object, the hole we create is put onto the MRU stack inside the drm_mm range manager. On the next search pass, we can speed up a PIN_HIGH allocation by referencing that stack for the new hole.

v2: Pull together the 3 identical implements (ahem, a couple were outdated) into a common routine for allocating a node and evicting as necessary.

Signed-off-by: Chris Wilson chris@chris-wilson.co.uk Reviewed-by: Joonas Lahtinen joonas.lahtinen@linux.intel.com --- drivers/gpu/drm/i915/gvt/aperture_gm.c | 33 +++++----------- drivers/gpu/drm/i915/i915_gem_gtt.c | 72 ++++++++++++++++++++++++---------- drivers/gpu/drm/i915/i915_gem_gtt.h | 5 +++ drivers/gpu/drm/i915/i915_vma.c | 40 ++----------------- 4 files changed, 70 insertions(+), 80 deletions(-)

diff --git a/drivers/gpu/drm/i915/gvt/aperture_gm.c b/drivers/gpu/drm/i915/gvt/aperture_gm.c index 7d33b607bc89..1bb7a5b80d47 100644 --- a/drivers/gpu/drm/i915/gvt/aperture_gm.c +++ b/drivers/gpu/drm/i915/gvt/aperture_gm.c @@ -48,47 +48,34 @@ static int alloc_gm(struct intel_vgpu *vgpu, bool high_gm) { struct intel_gvt *gvt = vgpu->gvt; struct drm_i915_private *dev_priv = gvt->dev_priv; - u32 alloc_flag, search_flag; + unsigned int flags; u64 start, end, size; struct drm_mm_node *node; - int retried = 0; int ret;

if (high_gm) { - search_flag = DRM_MM_SEARCH_BELOW; - alloc_flag = DRM_MM_CREATE_TOP; node = &vgpu->gm.high_gm_node; size = vgpu_hidden_sz(vgpu); start = gvt_hidden_gmadr_base(gvt); end = gvt_hidden_gmadr_end(gvt); + flags = PIN_HIGH; } else { - search_flag = DRM_MM_SEARCH_DEFAULT; - alloc_flag = DRM_MM_CREATE_DEFAULT; node = &vgpu->gm.low_gm_node; size = vgpu_aperture_sz(vgpu); start = gvt_aperture_gmadr_base(gvt); end = gvt_aperture_gmadr_end(gvt); + flags = PIN_MAPPABLE; }

mutex_lock(&dev_priv->drm.struct_mutex); -search_again: - ret = drm_mm_insert_node_in_range_generic(&dev_priv->ggtt.base.mm, - node, size, 4096, - I915_COLOR_UNEVICTABLE, - start, end, search_flag, - alloc_flag); - if (ret) { - ret = i915_gem_evict_something(&dev_priv->ggtt.base, - size, 4096, - I915_COLOR_UNEVICTABLE, - start, end, 0); - if (ret == 0 && ++retried < 3) - goto search_again; - - gvt_err("fail to alloc %s gm space from host, retried %d\n", - high_gm ? "high" : "low", retried); - } + ret = i915_gem_gtt_insert(&dev_priv->ggtt.base, node, + size, 4096, I915_COLOR_UNEVICTABLE, + start, end, flags); mutex_unlock(&dev_priv->drm.struct_mutex); + if (ret) + gvt_err("fail to alloc %s gm space from host\n", + high_gm ? "high" : "low"); + return ret; }

diff --git a/drivers/gpu/drm/i915/i915_gem_gtt.c b/drivers/gpu/drm/i915/i915_gem_gtt.c index 6af9311f72f5..c8f1675852a7 100644 --- a/drivers/gpu/drm/i915/i915_gem_gtt.c +++ b/drivers/gpu/drm/i915/i915_gem_gtt.c @@ -2044,7 +2044,6 @@ static int gen6_ppgtt_allocate_page_directories(struct i915_hw_ppgtt *ppgtt) struct i915_address_space *vm = &ppgtt->base; struct drm_i915_private *dev_priv = ppgtt->base.i915; struct i915_ggtt *ggtt = &dev_priv->ggtt; - bool retried = false; int ret;

/* PPGTT PDEs reside in the GGTT and consists of 512 entries. The @@ -2057,29 +2056,14 @@ static int gen6_ppgtt_allocate_page_directories(struct i915_hw_ppgtt *ppgtt) if (ret) return ret;

-alloc: - ret = drm_mm_insert_node_in_range_generic(&ggtt->base.mm, &ppgtt->node, - GEN6_PD_SIZE, GEN6_PD_ALIGN, - I915_COLOR_UNEVICTABLE, - 0, ggtt->base.total, - DRM_MM_TOPDOWN); - if (ret == -ENOSPC && !retried) { - ret = i915_gem_evict_something(&ggtt->base, - GEN6_PD_SIZE, GEN6_PD_ALIGN, - I915_COLOR_UNEVICTABLE, - 0, ggtt->base.total, - 0); - if (ret) - goto err_out; - - retried = true; - goto alloc; - } - + ret = i915_gem_gtt_insert(&ggtt->base, &ppgtt->node, + GEN6_PD_SIZE, GEN6_PD_ALIGN, + I915_COLOR_UNEVICTABLE, + 0, ggtt->base.total, + PIN_HIGH); if (ret) goto err_out;

- if (ppgtt->node.start < ggtt->mappable_end) DRM_DEBUG("Forced to use aperture for PDEs\n");

@@ -3553,3 +3537,49 @@ i915_get_ggtt_vma_pages(struct i915_vma *vma) return ret; }

+int i915_gem_gtt_insert(struct i915_address_space *vm, + struct drm_mm_node *node, + u64 size, u64 alignment, unsigned long color, + u64 start, u64 end, unsigned int flags) +{ + u32 search_flag, alloc_flag; + int err; + + lockdep_assert_held(&vm->i915->drm.struct_mutex); + + if (flags & PIN_HIGH) { + search_flag = DRM_MM_SEARCH_BELOW; + alloc_flag = DRM_MM_CREATE_TOP; + } else { + search_flag = DRM_MM_SEARCH_DEFAULT; + alloc_flag = DRM_MM_CREATE_DEFAULT; + } + + /* We only allocate in PAGE_SIZE/GTT_PAGE_SIZE (4096) chunks, + * so we know that we always have a minimum alignment of 4096. + * The drm_mm range manager is optimised to return results + * with zero alignment, so where possible use the optimal + * path. + */ + GEM_BUG_ON(size & 4095); + if (alignment <= 4096) + alignment = 0; + + err = drm_mm_insert_node_in_range_generic(&vm->mm, node, + size, alignment, color, + start, end, + search_flag, alloc_flag); + if (err != -ENOSPC) + return err; + + err = i915_gem_evict_something(vm, size, alignment, color, + start, end, flags); + if (err) + return err; + + search_flag = DRM_MM_SEARCH_DEFAULT; + return drm_mm_insert_node_in_range_generic(&vm->mm, node, + size, alignment, color, + start, end, + search_flag, alloc_flag); +} diff --git a/drivers/gpu/drm/i915/i915_gem_gtt.h b/drivers/gpu/drm/i915/i915_gem_gtt.h index 0055b8567a43..4c7bef07e38a 100644 --- a/drivers/gpu/drm/i915/i915_gem_gtt.h +++ b/drivers/gpu/drm/i915/i915_gem_gtt.h @@ -528,6 +528,11 @@ int __must_check i915_gem_gtt_prepare_pages(struct drm_i915_gem_object *obj, void i915_gem_gtt_finish_pages(struct drm_i915_gem_object *obj, struct sg_table *pages);

+int i915_gem_gtt_insert(struct i915_address_space *vm, + struct drm_mm_node *node, + u64 size, u64 alignment, unsigned long color, + u64 start, u64 end, unsigned int flags); + /* Flags used by pin/bind&friends. */ #define PIN_NONBLOCK BIT(0) #define PIN_MAPPABLE BIT(1) diff --git a/drivers/gpu/drm/i915/i915_vma.c b/drivers/gpu/drm/i915/i915_vma.c index fd75d5704287..608008d2d999 100644 --- a/drivers/gpu/drm/i915/i915_vma.c +++ b/drivers/gpu/drm/i915/i915_vma.c @@ -415,43 +415,11 @@ i915_vma_insert(struct i915_vma *vma, u64 size, u64 alignment, u64 flags) goto err_unpin; } } else { - u32 search_flag, alloc_flag; - - if (flags & PIN_HIGH) { - search_flag = DRM_MM_SEARCH_BELOW; - alloc_flag = DRM_MM_CREATE_TOP; - } else { - search_flag = DRM_MM_SEARCH_DEFAULT; - alloc_flag = DRM_MM_CREATE_DEFAULT; - } - - /* We only allocate in PAGE_SIZE/GTT_PAGE_SIZE (4096) chunks, - * so we know that we always have a minimum alignment of 4096. - * The drm_mm range manager is optimised to return results - * with zero alignment, so where possible use the optimal - * path. - */ - if (alignment <= 4096) - alignment = 0; - -search_free: - ret = drm_mm_insert_node_in_range_generic(&vma->vm->mm, - &vma->node, - size, alignment, - obj->cache_level, - start, end, - search_flag, - alloc_flag); - if (ret) { - ret = i915_gem_evict_something(vma->vm, size, alignment, - obj->cache_level, - start, end, - flags); - if (ret == 0) - goto search_free; - + ret = i915_gem_gtt_insert(vma->vm, &vma->node, + size, alignment, obj->cache_level, + start, end, flags); + if (ret) goto err_unpin; - }

GEM_BUG_ON(vma->node.start < start); GEM_BUG_ON(vma->node.start + vma->node.size > end);

Fairly commonly we want to inspect the node list on the struct drm_mm, which is buried within an embedded node. Bring it to the surface with a bit of syntatic sugar.

Note this was intended to be split from commit ad579002c8ec ("drm: Add drm_mm_for_each_node_safe()") before being applied, but my timing sucks.

Signed-off-by: Chris Wilson chris@chris-wilson.co.uk Reviewed-by: Joonas Lahtinen joonas.lahtinen@linux.intel.com Cc: Daniel Vetter daniel.vetter@ffwll.ch --- drivers/gpu/drm/drm_mm.c | 8 ++++---- include/drm/drm_mm.h | 18 +++++++++++++++--- 2 files changed, 19 insertions(+), 7 deletions(-)

diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c index 7573661302a4..4257c86cc305 100644 --- a/drivers/gpu/drm/drm_mm.c +++ b/drivers/gpu/drm/drm_mm.c @@ -138,7 +138,7 @@ static void show_leaks(struct drm_mm *mm) if (!buf) return;

- list_for_each_entry(node, __drm_mm_nodes(mm), node_list) { + list_for_each_entry(node, drm_mm_nodes(mm), node_list) { struct stack_trace trace = { .entries = entries, .max_entries = STACKDEPTH @@ -320,7 +320,7 @@ int drm_mm_reserve_node(struct drm_mm *mm, struct drm_mm_node *node) if (hole->start < end) return -ENOSPC; } else { - hole = list_entry(__drm_mm_nodes(mm), typeof(*hole), node_list); + hole = list_entry(drm_mm_nodes(mm), typeof(*hole), node_list); }

hole = list_last_entry(&hole->node_list, typeof(*hole), node_list); @@ -883,7 +883,7 @@ EXPORT_SYMBOL(drm_mm_scan_remove_block); */ bool drm_mm_clean(const struct drm_mm *mm) { - const struct list_head *head = __drm_mm_nodes(mm); + const struct list_head *head = drm_mm_nodes(mm);

return (head->next->next == head); } @@ -929,7 +929,7 @@ EXPORT_SYMBOL(drm_mm_init); */ void drm_mm_takedown(struct drm_mm *mm) { - if (WARN(!list_empty(__drm_mm_nodes(mm)), + if (WARN(!list_empty(drm_mm_nodes(mm)), "Memory manager not clean during takedown.\n")) show_leaks(mm);

diff --git a/include/drm/drm_mm.h b/include/drm/drm_mm.h index 5c7f15875b6a..f6a68ed5ecaf 100644 --- a/include/drm/drm_mm.h +++ b/include/drm/drm_mm.h @@ -180,7 +180,19 @@ static inline u64 drm_mm_hole_node_end(const struct drm_mm_node *hole_node) return __drm_mm_hole_node_end(hole_node); }

-#define __drm_mm_nodes(mm) (&(mm)->head_node.node_list) +/** + * drm_mm_nodes - list of nodes under the drm_mm range manager + * @mm: the struct drm_mm range manger + * + * As the drm_mm range manager hides its node_list deep with its + * structure, extracting it looks painful and repetitive. This is + * not expected to be used outside of the drm_mm_for_each_node() + * macros and similar internal functions. + * + * Returns: + * The node list, may be empty. + */ +#define drm_mm_nodes(mm) (&(mm)->head_node.node_list)

/** * drm_mm_for_each_node - iterator to walk over all allocated nodes @@ -191,7 +203,7 @@ static inline u64 drm_mm_hole_node_end(const struct drm_mm_node *hole_node) * with list_for_each, so not save against removal of elements. */ #define drm_mm_for_each_node(entry, mm) \ - list_for_each_entry(entry, __drm_mm_nodes(mm), node_list) + list_for_each_entry(entry, drm_mm_nodes(mm), node_list)

/** * drm_mm_for_each_node_safe - iterator to walk over all allocated nodes @@ -203,7 +215,7 @@ static inline u64 drm_mm_hole_node_end(const struct drm_mm_node *hole_node) * with list_for_each_safe, so save against removal of elements. */ #define drm_mm_for_each_node_safe(entry, next, mm) \ - list_for_each_entry_safe(entry, next, __drm_mm_nodes(mm), node_list) + list_for_each_entry_safe(entry, next, drm_mm_nodes(mm), node_list)

#define __drm_mm_for_each_hole(entry, mm, hole_start, hole_end, backwards) \ for (entry = list_entry((backwards) ? (mm)->hole_stack.prev : (mm)->hole_stack.next, struct drm_mm_node, hole_stack); \

Prime numbers are interesting for testing components that use multiplies and divides, such as testing DRM's struct drm_mm alignment computations.

v2: Move to lib/, add selftest v3: Fix initial constants (exclude 0/1 from being primes) v4: More RCU markup to keep 0day/sparse happy v5: Fix RCU unwind on module exit, add to kselftests v6: Tidy computation of bitmap size v7: for_each_prime_number_from() v8: Compose small-primes using BIT() for easier verification v9: Move rcu dance entirely into callers.

Signed-off-by: Chris Wilson chris@chris-wilson.co.uk Cc: Lukas Wunner lukas@wunner.de --- include/linux/prime_numbers.h | 37 ++++ lib/Kconfig | 7 + lib/Makefile | 2 + lib/prime_numbers.c | 304 +++++++++++++++++++++++++++ tools/testing/selftests/lib/prime_numbers.sh | 15 ++ 5 files changed, 365 insertions(+) create mode 100644 include/linux/prime_numbers.h create mode 100644 lib/prime_numbers.c create mode 100755 tools/testing/selftests/lib/prime_numbers.sh

diff --git a/include/linux/prime_numbers.h b/include/linux/prime_numbers.h new file mode 100644 index 000000000000..14ec4f567342 --- /dev/null +++ b/include/linux/prime_numbers.h @@ -0,0 +1,37 @@ +#ifndef __LINUX_PRIME_NUMBERS_H +#define __LINUX_PRIME_NUMBERS_H + +#include <linux/types.h> + +bool is_prime_number(unsigned long x); +unsigned long next_prime_number(unsigned long x); + +/** + * for_each_prime_number - iterate over each prime upto a value + * @prime: the current prime number in this iteration + * @max: the upper limit + * + * Starting from the first prime number 2 iterate over each prime number up to + * the @max value. On each iteration, @prime is set to the current prime number. + * @max should be less than ULONG_MAX to ensure termination. To begin with + * @prime set to 1 on the first iteration use for_each_prime_number_from() + * instead. + */ +#define for_each_prime_number(prime, max) \ + for_each_prime_number_from((prime), 2, (max)) + +/** + * for_each_prime_number_from - iterate over each prime upto a value + * @prime: the current prime number in this iteration + * @from: the initial value + * @max: the upper limit + * + * Starting from @from iterate over each successive prime number up to the + * @max value. On each iteration, @prime is set to the current prime number. + * @max should be less than ULONG_MAX, and @from less than @max, to ensure + * termination. + */ +#define for_each_prime_number_from(prime, from, max) \ + for (prime = (from); prime <= (max); prime = next_prime_number(prime)) + +#endif /* !__LINUX_PRIME_NUMBERS_H */ diff --git a/lib/Kconfig b/lib/Kconfig index 260a80e313b9..1788a1f50d28 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -550,4 +550,11 @@ config STACKDEPOT config SBITMAP bool

+config PRIME_NUMBERS + tristate "Prime number generator" + default n + help + Provides a helper module to generate prime numbers. Useful for writing + test code, especially when checking multiplication and divison. + endmenu diff --git a/lib/Makefile b/lib/Makefile index 50144a3aeebd..c664143fd917 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -197,6 +197,8 @@ obj-$(CONFIG_ASN1) += asn1_decoder.o

obj-$(CONFIG_FONT_SUPPORT) += fonts/

+obj-$(CONFIG_PRIME_NUMBERS) += prime_numbers.o + hostprogs-y := gen_crc32table clean-files := crc32table.h

diff --git a/lib/prime_numbers.c b/lib/prime_numbers.c new file mode 100644 index 000000000000..1e4dcbf99619 --- /dev/null +++ b/lib/prime_numbers.c @@ -0,0 +1,304 @@ +#define pr_fmt(fmt) "prime numbers: " fmt "\n" + +#include <linux/module.h> +#include <linux/mutex.h> +#include <linux/prime_numbers.h> +#include <linux/slab.h> + +#define bitmap_size(nbits) (BITS_TO_LONGS(nbits) * sizeof(unsigned long)) + +struct primes { + struct rcu_head rcu; + unsigned long last, sz; + unsigned long primes[]; +}; + +#if BITS_PER_LONG == 64 +static const struct primes small_primes = { + .last = 61, + .sz = 64, + .primes = { + BIT(2) | + BIT(3) | + BIT(5) | + BIT(7) | + BIT(11) | + BIT(13) | + BIT(17) | + BIT(19) | + BIT(23) | + BIT(29) | + BIT(31) | + BIT(37) | + BIT(41) | + BIT(43) | + BIT(47) | + BIT(53) | + BIT(59) | + BIT(61) + } +}; +#elif BITS_PER_LONG == 32 +static const struct primes small_primes = { + .last = 31, + .sz = 32, + .primes = { + BIT(2) | + BIT(3) | + BIT(5) | + BIT(7) | + BIT(11) | + BIT(13) | + BIT(17) | + BIT(19) | + BIT(23) | + BIT(29) | + BIT(31) + } +}; +#else +#error "unhandled BITS_PER_LONG" +#endif + +static DEFINE_MUTEX(lock); +static const struct primes __rcu *primes = RCU_INITIALIZER(&small_primes); + +static unsigned long selftest_max; + +static bool slow_is_prime_number(unsigned long x) +{ + unsigned long y = int_sqrt(x); + + while (y > 1) { + if ((x % y) == 0) + break; + y--; + } + + return y == 1; +} + +static unsigned long slow_next_prime_number(unsigned long x) +{ + while (x < ULONG_MAX && !slow_is_prime_number(++x)) + ; + + return x; +} + +static unsigned long clear_multiples(unsigned long x, + unsigned long *p, + unsigned long start, + unsigned long end) +{ + unsigned long m; + + m = 2 * x; + if (m < start) + m = roundup(start, x); + + while (m < end) { + __clear_bit(m, p); + m += x; + } + + return x; +} + +static bool expand_to_next_prime(unsigned long x) +{ + const struct primes *p; + struct primes *new; + unsigned long sz, y; + + /* Betrand's Theorem states: + * For all n > 1, there exists a prime p: n < p <= 2*n. + */ + sz = 2 * x + 1; + if (sz < x) + return false; + + sz = round_up(sz, BITS_PER_LONG); + new = kmalloc(sizeof(*new) + bitmap_size(sz), GFP_KERNEL); + if (!new) + return false; + + mutex_lock(&lock); + p = rcu_dereference_protected(primes, lockdep_is_held(&lock)); + if (x < p->last) { + kfree(new); + goto unlock; + } + + /* Where memory permits, track the primes using the + * Sieve of Eratosthenes. The sieve is to remove all multiples of known + * primes from the set, what remains in the set is therefore prime. + */ + bitmap_fill(new->primes, sz); + bitmap_copy(new->primes, p->primes, p->sz); + for (y = 2UL; y < sz; y = find_next_bit(new->primes, sz, y + 1)) + new->last = clear_multiples(y, new->primes, p->sz, sz); + new->sz = sz; + + BUG_ON(new->last <= x); + + rcu_assign_pointer(primes, new); + if (p != &small_primes) + kfree_rcu((struct primes *)p, rcu); + +unlock: + mutex_unlock(&lock); + return true; +} + +/** + * next_prime_number - return the next prime number + * @x: the starting point for searching to test + * + * A prime number is an integer greater than 1 that is only divisible by + * itself and 1. The set of prime numbers is computed using the Sieve of + * Eratoshenes (on finding a prime, all multiples of that prime are removed + * from the set) enabling a fast lookup of the next prime number larger than + * @x. If the sieve fails (memory limitation), the search falls back to using + * slow trial-divison, up to the value of ULONG_MAX (which is reported as the + * final prime as a sentinel). + * + * Returns: the next prime number larger than @x + */ +unsigned long next_prime_number(unsigned long x) +{ + const struct primes *p; + + rcu_read_lock(); + p = rcu_dereference(primes); + while (x >= p->last) { + rcu_read_unlock(); + + if (!expand_to_next_prime(x)) + return slow_next_prime_number(x); + + rcu_read_lock(); + p = rcu_dereference(primes); + } + x = find_next_bit(p->primes, p->last, x + 1); + rcu_read_unlock(); + + return x; +} +EXPORT_SYMBOL(next_prime_number); + +/** + * is_prime_number - test whether the given number is prime + * @x: the number to test + * + * A prime number is an integer greater than 1 that is only divisible by + * itself and 1. Internally a cache of prime numbers is kept (to speed up + * searching for sequential primes, see next_prime_number()), but if the number + * falls outside of that cache, its primality is tested using trial-divison. + * + * Returns: true if @x is prime, false for composite numbers. + */ +bool is_prime_number(unsigned long x) +{ + const struct primes *p; + bool result; + + rcu_read_lock(); + p = rcu_dereference(primes); + while (x >= p->sz) { + rcu_read_unlock(); + + if (!expand_to_next_prime(x)) + return slow_is_prime_number(x); + + rcu_read_lock(); + p = rcu_dereference(primes); + } + result = test_bit(x, p->primes); + rcu_read_unlock(); + + return result; +} +EXPORT_SYMBOL(is_prime_number); + +static void dump_primes(void) +{ + const struct primes *p; + char *buf; + + buf = kmalloc(PAGE_SIZE, GFP_KERNEL); + + rcu_read_lock(); + p = rcu_dereference(primes); + + if (buf) + bitmap_print_to_pagebuf(true, buf, p->primes, p->sz); + pr_info("primes.{last=%lu, .sz=%lu, .primes[]=...x%lx} = %s", + p->last, p->sz, p->primes[BITS_TO_LONGS(p->sz) - 1], buf); + + rcu_read_unlock(); + + kfree(buf); +} + +static int selftest(unsigned long max) +{ + unsigned long x, last; + + if (!max) + return 0; + + for (last = 0, x = 2; x < max; x++) { + bool slow = slow_is_prime_number(x); + bool fast = is_prime_number(x); + + if (slow != fast) { + pr_err("inconsistent result for is-prime(%lu): slow=%s, fast=%s!", + x, slow ? "yes" : "no", fast ? "yes" : "no"); + goto err; + } + + if (!slow) + continue; + + if (next_prime_number(last) != x) { + pr_err("incorrect result for next-prime(%lu): expected %lu, got %lu", + last, x, next_prime_number(last)); + goto err; + } + last = x; + } + + pr_info("selftest(%lu) passed, last prime was %lu", x, last); + return 0; + +err: + dump_primes(); + return -EINVAL; +} + +static int __init primes_init(void) +{ + return selftest(selftest_max); +} + +static void __exit primes_exit(void) +{ + const struct primes *p; + + mutex_lock(&lock); + p = rcu_dereference_protected(primes, lockdep_is_held(&lock)); + if (p != &small_primes) { + rcu_assign_pointer(primes, &small_primes); + kfree_rcu((struct primes *)p, rcu); + } + mutex_unlock(&lock); +} + +module_init(primes_init); +module_exit(primes_exit); + +module_param_named(selftest, selftest_max, ulong, 0400); + +MODULE_AUTHOR("Intel Corporation"); +MODULE_LICENSE("GPL"); diff --git a/tools/testing/selftests/lib/prime_numbers.sh b/tools/testing/selftests/lib/prime_numbers.sh new file mode 100755 index 000000000000..da4cbcd766f5 --- /dev/null +++ b/tools/testing/selftests/lib/prime_numbers.sh @@ -0,0 +1,15 @@ +#!/bin/sh +# Checks fast/slow prime_number generation for inconsistencies + +if ! /sbin/modprobe -q -r prime_numbers; then + echo "prime_numbers: [SKIP]" + exit 77 +fi + +if /sbin/modprobe -q prime_numbers selftest=65536; then + /sbin/modprobe -q -r prime_numbers + echo "prime_numbers: ok" +else + echo "prime_numbers: [FAIL]" + exit 1 +fi

Simple test to just exercise calling the debug dumper on the drm_mm.

Signed-off-by: Chris Wilson chris@chris-wilson.co.uk Reviewed-by: Joonas Lahtinen joonas.lahtinen@linux.intel.com --- drivers/gpu/drm/selftests/drm_mm_selftests.h | 1 + drivers/gpu/drm/selftests/test-drm_mm.c | 35 ++++++++++++++++++++++++++++ 2 files changed, 36 insertions(+)

diff --git a/drivers/gpu/drm/selftests/drm_mm_selftests.h b/drivers/gpu/drm/selftests/drm_mm_selftests.h index 844dd29db540..0265f09e92fa 100644 --- a/drivers/gpu/drm/selftests/drm_mm_selftests.h +++ b/drivers/gpu/drm/selftests/drm_mm_selftests.h @@ -7,3 +7,4 @@ */ selftest(sanitycheck, igt_sanitycheck) /* keep first (selfcheck for igt) */ selftest(init, igt_init) +selftest(debug, igt_debug) diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c index 87ad147670da..434320061d9e 100644 --- a/drivers/gpu/drm/selftests/test-drm_mm.c +++ b/drivers/gpu/drm/selftests/test-drm_mm.c @@ -141,6 +141,41 @@ static int igt_init(void *ignored) return ret; }

+static int igt_debug(void *ignored) +{ + struct drm_mm mm; + struct drm_mm_node nodes[2]; + int ret; + + /* Create a small drm_mm with a couple of nodes and a few holes, and + * check that the debug iterator doesn't explode over a trivial drm_mm. + */ + + drm_mm_init(&mm, 0, 4096); + + memset(nodes, 0, sizeof(nodes)); + nodes[0].start = 512; + nodes[0].size = 1024; + ret = drm_mm_reserve_node(&mm, &nodes[0]); + if (ret) { + pr_err("failed to reserve node[0] {start=%lld, size=%lld)\n", + nodes[0].start, nodes[0].size); + return ret; + } + + nodes[1].size = 1024; + nodes[1].start = 4096 - 512 - nodes[1].size; + ret = drm_mm_reserve_node(&mm, &nodes[1]); + if (ret) { + pr_err("failed to reserve node[1] {start=%lld, size=%lld)\n", + nodes[1].start, nodes[1].size); + return ret; + } + + drm_mm_debug_table(&mm, __func__); + return 0; +} + #include "drm_selftest.c"

static int __init test_drm_mm_init(void)

Exercise drm_mm_insert_node(), check that we can't overfill a range and that the lists are correct after reserving/removing.

v2: Extract helpers for the repeated tests v3: Iterate over all allocation flags

Signed-off-by: Chris Wilson chris@chris-wilson.co.uk Reviewed-by: Joonas Lahtinen joonas.lahtinen@linux.intel.com --- drivers/gpu/drm/selftests/drm_mm_selftests.h | 1 + drivers/gpu/drm/selftests/test-drm_mm.c | 234 +++++++++++++++++++++++++++ 2 files changed, 235 insertions(+)

diff --git a/drivers/gpu/drm/selftests/drm_mm_selftests.h b/drivers/gpu/drm/selftests/drm_mm_selftests.h index 693d85677e7f..727c6d7255e0 100644 --- a/drivers/gpu/drm/selftests/drm_mm_selftests.h +++ b/drivers/gpu/drm/selftests/drm_mm_selftests.h @@ -9,3 +9,4 @@ selftest(sanitycheck, igt_sanitycheck) /* keep first (selfcheck for igt) */ selftest(init, igt_init) selftest(debug, igt_debug) selftest(reserve, igt_reserve) +selftest(insert, igt_insert) diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c index 789a810d66aa..feb5985abdc2 100644 --- a/drivers/gpu/drm/selftests/test-drm_mm.c +++ b/drivers/gpu/drm/selftests/test-drm_mm.c @@ -21,6 +21,23 @@ static unsigned int random_seed; static unsigned int max_iterations = 8192; static unsigned int max_prime = 128;

+enum { + DEFAULT, + TOPDOWN, + BEST, +}; + +static const struct insert_mode { + const char *name; + unsigned int search_flags; + unsigned int create_flags; +} insert_modes[] = { + [DEFAULT] = { "default", DRM_MM_SEARCH_DEFAULT, DRM_MM_CREATE_DEFAULT }, + [TOPDOWN] = { "top-down", DRM_MM_SEARCH_BELOW, DRM_MM_CREATE_TOP }, + [BEST] = { "best", DRM_MM_SEARCH_BEST, DRM_MM_CREATE_DEFAULT }, + {} +}; + static int igt_sanitycheck(void *ignored) { pr_info("%s - ok!\n", __func__); @@ -131,6 +148,48 @@ static bool assert_continuous(const struct drm_mm *mm, u64 size) return true; }

+static u64 misalignment(struct drm_mm_node *node, u64 alignment) +{ + u64 rem; + + if (!alignment) + return 0; + + div64_u64_rem(node->start, alignment, &rem); + return rem; +} + +static bool assert_node(struct drm_mm_node *node, struct drm_mm *mm, + u64 size, u64 alignment, unsigned long color) +{ + bool ok = true; + + if (!drm_mm_node_allocated(node) || node->mm != mm) { + pr_err("node not allocated\n"); + ok = false; + } + + if (node->size != size) { + pr_err("node has wrong size, found %llu, expected %llu\n", + node->size, size); + ok = false; + } + + if (misalignment(node, alignment)) { + pr_err("node is misalinged, start %llx rem %llu, expected alignment %llu\n", + node->start, misalignment(node, alignment), alignment); + ok = false; + } + + if (node->color != color) { + pr_err("node has wrong color, found %lu, expected %lu\n", + node->color, color); + ok = false; + } + + return ok; +} + static int igt_init(void *ignored) { const unsigned int size = 4096; @@ -451,6 +510,181 @@ static int igt_reserve(void *ignored) return 0; }

+static bool expect_insert(struct drm_mm *mm, struct drm_mm_node *node, + u64 size, u64 alignment, unsigned long color, + const struct insert_mode *mode) +{ + int err; + + err = drm_mm_insert_node_generic(mm, node, + size, alignment, color, + mode->search_flags, + mode->create_flags); + if (err) { + pr_err("insert (size=%llu, alignment=%llu, color=%lu, mode=%s) failed with err=%d\n", + size, alignment, color, mode->name, err); + return false; + } + + if (!assert_node(node, mm, size, alignment, color)) { + drm_mm_remove_node(node); + return false; + } + + return true; +} + +static bool expect_insert_fail(struct drm_mm *mm, u64 size) +{ + struct drm_mm_node tmp = {}; + int err; + + err = drm_mm_insert_node(mm, &tmp, size, 0, DRM_MM_SEARCH_DEFAULT); + if (likely(err == -ENOSPC)) + return true; + + if (!err) { + pr_err("impossible insert succeeded, node %llu + %llu\n", + tmp.start, tmp.size); + drm_mm_remove_node(&tmp); + } else { + pr_err("impossible insert failed with wrong error %d [expected %d], size %llu\n", + err, -ENOSPC, size); + } + return false; +} + +static int __igt_insert(unsigned int count, u64 size) +{ + DRM_RND_STATE(prng, random_seed); + const struct insert_mode *mode; + struct drm_mm mm; + struct drm_mm_node *nodes, *node, *next; + unsigned int *order, n, m, o = 0; + int ret; + + /* Fill a range with lots of nodes, check it doesn't fail too early */ + + DRM_MM_BUG_ON(!count); + DRM_MM_BUG_ON(!size); + + ret = -ENOMEM; + nodes = vzalloc(count * sizeof(*nodes)); + if (!nodes) + goto err; + + order = drm_random_order(count, &prng); + if (!order) + goto err_nodes; + + ret = -EINVAL; + drm_mm_init(&mm, 0, count * size); + + for (mode = insert_modes; mode->name; mode++) { + for (n = 0; n < count; n++) { + if (!expect_insert(&mm, &nodes[n], size, 0, n, mode)) { + pr_err("%s insert failed, size %llu step %d\n", + mode->name, size, n); + goto out; + } + } + + /* After random insertion the nodes should be in order */ + if (!assert_continuous(&mm, size)) + goto out; + + /* Repeated use should then fail */ + if (!expect_insert_fail(&mm, size)) + goto out; + + /* Remove one and reinsert, as the only hole it should refill itself */ + for (n = 0; n < count; n++) { + u64 addr = nodes[n].start; + + drm_mm_remove_node(&nodes[n]); + if (!expect_insert(&mm, &nodes[n], size, 0, n, mode)) { + pr_err("%s reinsert failed, size %llu step %d\n", + mode->name, size, n); + goto out; + } + + if (nodes[n].start != addr) { + pr_err("%s reinsert node moved, step %d, expected %llx, found %llx\n", + mode->name, n, addr, nodes[n].start); + goto out; + } + + if (!assert_continuous(&mm, size)) + goto out; + } + + /* Remove several, reinsert, check full */ + for_each_prime_number(n, min(max_prime, count)) { + for (m = 0; m < n; m++) { + node = &nodes[order[(o + m) % count]]; + drm_mm_remove_node(node); + } + + for (m = 0; m < n; m++) { + node = &nodes[order[(o + m) % count]]; + if (!expect_insert(&mm, node, size, 0, n, mode)) { + pr_err("%s multiple reinsert failed, size %llu step %d\n", + mode->name, size, n); + goto out; + } + } + + o += n; + + if (!assert_continuous(&mm, size)) + goto out; + + if (!expect_insert_fail(&mm, size)) + goto out; + } + + drm_mm_for_each_node_safe(node, next, &mm) + drm_mm_remove_node(node); + DRM_MM_BUG_ON(!drm_mm_clean(&mm)); + } + + ret = 0; +out: + drm_mm_for_each_node_safe(node, next, &mm) + drm_mm_remove_node(node); + drm_mm_takedown(&mm); + kfree(order); +err_nodes: + vfree(nodes); +err: + return ret; +} + +static int igt_insert(void *ignored) +{ + const unsigned int count = min_t(unsigned int, BIT(10), max_iterations); + unsigned int n; + int ret; + + for_each_prime_number_from(n, 1, 54) { + u64 size = BIT_ULL(n); + + ret = __igt_insert(count, size - 1); + if (ret) + return ret; + + ret = __igt_insert(count, size); + if (ret) + return ret; + + ret = __igt_insert(count, size + 1); + if (ret) + return ret; + } + + return 0; +} + #include "drm_selftest.c"

static int __init test_drm_mm_init(void)

Exercise drm_mm_insert_node_in_range(), check that we only allocate from the specified range.

v2: Use all allocation flags v3: Don't pass in invalid ranges - these will be asserted later.

Signed-off-by: Chris Wilson chris@chris-wilson.co.uk Reviewed-by: Joonas Lahtinen joonas.lahtinen@linux.intel.com --- drivers/gpu/drm/selftests/drm_mm_selftests.h | 1 + drivers/gpu/drm/selftests/test-drm_mm.c | 269 +++++++++++++++++++++++++++ 2 files changed, 270 insertions(+)

diff --git a/drivers/gpu/drm/selftests/drm_mm_selftests.h b/drivers/gpu/drm/selftests/drm_mm_selftests.h index dca726baa65d..92b2c1cb10fa 100644 --- a/drivers/gpu/drm/selftests/drm_mm_selftests.h +++ b/drivers/gpu/drm/selftests/drm_mm_selftests.h @@ -11,3 +11,4 @@ selftest(debug, igt_debug) selftest(reserve, igt_reserve) selftest(insert, igt_insert) selftest(replace, igt_replace) +selftest(insert_range, igt_insert_range) diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c index 7914428c9862..afc9274d8086 100644 --- a/drivers/gpu/drm/selftests/test-drm_mm.c +++ b/drivers/gpu/drm/selftests/test-drm_mm.c @@ -738,6 +738,275 @@ static int igt_replace(void *ignored) return 0; }

+static bool expect_insert_in_range(struct drm_mm *mm, struct drm_mm_node *node, + u64 size, u64 alignment, unsigned long color, + u64 range_start, u64 range_end, + const struct insert_mode *mode) +{ + int err; + + err = drm_mm_insert_node_in_range_generic(mm, node, + size, alignment, color, + range_start, range_end, + mode->search_flags, + mode->create_flags); + if (err) { + pr_err("insert (size=%llu, alignment=%llu, color=%lu, mode=%s) nto range [%llx, %llx] failed with err=%d\n", + size, alignment, color, mode->name, + range_start, range_end, err); + return false; + } + + if (!assert_node(node, mm, size, alignment, color)) { + drm_mm_remove_node(node); + return false; + } + + return true; +} + +static bool expect_insert_in_range_fail(struct drm_mm *mm, + u64 size, + u64 range_start, + u64 range_end) +{ + struct drm_mm_node tmp = {}; + int err; + + err = drm_mm_insert_node_in_range_generic(mm, &tmp, + size, 0, 0, + range_start, range_end, + DRM_MM_SEARCH_DEFAULT, + DRM_MM_CREATE_DEFAULT); + if (likely(err == -ENOSPC)) + return true; + + if (!err) { + pr_err("impossible insert succeeded, node %llx + %llu, range [%llx, %llx]\n", + tmp.start, tmp.size, range_start, range_end); + drm_mm_remove_node(&tmp); + } else { + pr_err("impossible insert failed with wrong error %d [expected %d], size %llu, range [%llx, %llx]\n", + err, -ENOSPC, size, range_start, range_end); + } + + return false; +} + +static bool assert_contiguous_in_range(struct drm_mm *mm, + u64 size, + u64 start, + u64 end) +{ + struct drm_mm_node *node; + unsigned int n; + + if (!expect_insert_in_range_fail(mm, size, start, end)) + return false; + + n = div64_u64(start + size - 1, size); + drm_mm_for_each_node(node, mm) { + if (node->start < start || node->start + node->size > end) { + pr_err("node %d out of range, address [%llx + %llu], range [%llx, %llx]\n", + n, node->start, node->start + node->size, start, end); + return false; + } + + if (node->start != n * size) { + pr_err("node %d out of order, expected start %llx, found %llx\n", + n, n * size, node->start); + return false; + } + + if (node->size != size) { + pr_err("node %d has wrong size, expected size %llx, found %llx\n", + n, size, node->size); + return false; + } + + if (node->hole_follows && drm_mm_hole_node_end(node) < end) { + pr_err("node %d is followed by a hole!\n", n); + return false; + } + + n++; + } + + drm_mm_for_each_node_in_range(node, mm, 0, start) { + if (node) { + pr_err("node before start: node=%llx+%llu, start=%llx\n", + node->start, node->size, start); + return false; + } + } + + drm_mm_for_each_node_in_range(node, mm, end, U64_MAX) { + if (node) { + pr_err("node after end: node=%llx+%llu, end=%llx\n", + node->start, node->size, end); + return false; + } + } + + return true; +} + +static int __igt_insert_range(unsigned int count, u64 size, u64 start, u64 end) +{ + const struct insert_mode *mode; + struct drm_mm mm; + struct drm_mm_node *nodes, *node, *next; + unsigned int n, start_n, end_n; + int ret; + + DRM_MM_BUG_ON(!count); + DRM_MM_BUG_ON(!size); + DRM_MM_BUG_ON(end <= start); + + /* Very similar to __igt_insert(), but now instead of populating the + * full range of the drm_mm, we try to fill a small portion of it. + */ + + ret = -ENOMEM; + nodes = vzalloc(count * sizeof(*nodes)); + if (!nodes) + goto err; + + ret = -EINVAL; + drm_mm_init(&mm, 0, count * size); + + start_n = div64_u64(start + size - 1, size); + end_n = div64_u64(end - size, size); + + for (mode = insert_modes; mode->name; mode++) { + for (n = start_n; n <= end_n; n++) { + if (!expect_insert_in_range(&mm, &nodes[n], + size, size, n, + start, end, mode)) { + pr_err("%s insert failed, size %llu, step %d [%d, %d], range [%llx, %llx]\n", + mode->name, size, n, + start_n, end_n, + start, end); + goto out; + } + } + + if (!assert_contiguous_in_range(&mm, size, start, end)) { + pr_err("%s: range [%llx, %llx] not full after initialisation, size=%llu\n", + mode->name, start, end, size); + goto out; + } + + /* Remove one and reinsert, it should refill itself */ + for (n = start_n; n <= end_n; n++) { + u64 addr = nodes[n].start; + + drm_mm_remove_node(&nodes[n]); + if (!expect_insert_in_range(&mm, &nodes[n], + size, size, n, + start, end, mode)) { + pr_err("%s reinsert failed, step %d\n", mode->name, n); + goto out; + } + + if (nodes[n].start != addr) { + pr_err("%s reinsert node moved, step %d, expected %llx, found %llx\n", + mode->name, n, addr, nodes[n].start); + goto out; + } + } + + if (!assert_contiguous_in_range(&mm, size, start, end)) { + pr_err("%s: range [%llx, %llx] not full after reinsertion, size=%llu\n", + mode->name, start, end, size); + goto out; + } + + drm_mm_for_each_node_safe(node, next, &mm) + drm_mm_remove_node(node); + DRM_MM_BUG_ON(!drm_mm_clean(&mm)); + } + + ret = 0; +out: + drm_mm_for_each_node_safe(node, next, &mm) + drm_mm_remove_node(node); + drm_mm_takedown(&mm); + vfree(nodes); +err: + return ret; +} + +static int insert_outside_range(void) +{ + struct drm_mm mm; + const unsigned int start = 1024; + const unsigned int end = 2048; + const unsigned int size = end - start; + + drm_mm_init(&mm, start, size); + + if (!expect_insert_in_range_fail(&mm, 1, 0, start)) + return -EINVAL; + + if (!expect_insert_in_range_fail(&mm, size, + start - size/2, start + (size+1)/2)) + return -EINVAL; + + if (!expect_insert_in_range_fail(&mm, size, + end - (size+1)/2, end + size/2)) + return -EINVAL; + + if (!expect_insert_in_range_fail(&mm, 1, end, end + size)) + return -EINVAL; + + drm_mm_takedown(&mm); + return 0; +} + +static int igt_insert_range(void *ignored) +{ + const unsigned int count = min_t(unsigned int, BIT(13), max_iterations); + unsigned int n; + int ret; + + /* Check that requests outside the bounds of drm_mm are rejected. */ + ret = insert_outside_range(); + if (ret) + return ret; + + for_each_prime_number_from(n, 1, 50) { + const u64 size = BIT_ULL(n); + const u64 max = count * size; + + ret = __igt_insert_range(count, size, 0, max); + if (ret) + return ret; + + ret = __igt_insert_range(count, size, 1, max); + if (ret) + return ret; + + ret = __igt_insert_range(count, size, 0, max - 1); + if (ret) + return ret; + + ret = __igt_insert_range(count, size, 0, max/2); + if (ret) + return ret; + + ret = __igt_insert_range(count, size, max/2, max); + if (ret) + return ret; + + ret = __igt_insert_range(count, size, max/4+1, 3*max/4-1); + if (ret) + return ret; + } + + return 0; +} + #include "drm_selftest.c"

static int __init test_drm_mm_init(void)

Check that we add arbitrary blocks to the eviction scanner in order to find the first minimal hole that matches our request.

v2: Refactor out some common eviction code for later

Signed-off-by: Chris Wilson chris@chris-wilson.co.uk Reviewed-by: Joonas Lahtinen joonas.lahtinen@linux.intel.com --- drivers/gpu/drm/selftests/drm_mm_selftests.h | 1 + drivers/gpu/drm/selftests/test-drm_mm.c | 337 +++++++++++++++++++++++++++ 2 files changed, 338 insertions(+)

diff --git a/drivers/gpu/drm/selftests/drm_mm_selftests.h b/drivers/gpu/drm/selftests/drm_mm_selftests.h index a7a3763f8b20..a31b4458c7eb 100644 --- a/drivers/gpu/drm/selftests/drm_mm_selftests.h +++ b/drivers/gpu/drm/selftests/drm_mm_selftests.h @@ -15,3 +15,4 @@ selftest(insert_range, igt_insert_range) selftest(align, igt_align) selftest(align32, igt_align32) selftest(align64, igt_align64) +selftest(evict, igt_evict) diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c index 53ba268e07d9..065e2c72845b 100644 --- a/drivers/gpu/drm/selftests/test-drm_mm.c +++ b/drivers/gpu/drm/selftests/test-drm_mm.c @@ -36,6 +36,10 @@ static const struct insert_mode { [TOPDOWN] = { "top-down", DRM_MM_SEARCH_BELOW, DRM_MM_CREATE_TOP }, [BEST] = { "best", DRM_MM_SEARCH_BEST, DRM_MM_CREATE_DEFAULT }, {} +}, evict_modes[] = { + { "default", DRM_MM_SEARCH_DEFAULT, DRM_MM_CREATE_DEFAULT }, + { "top-down", DRM_MM_SEARCH_BELOW, DRM_MM_CREATE_TOP }, + {} };

static int igt_sanitycheck(void *ignored) @@ -1110,6 +1114,339 @@ static int igt_align64(void *ignored) return igt_align_pot(64); }

+static void show_scan(const struct drm_mm *scan) +{ + pr_info("scan: hit [%llx, %llx], size=%lld, align=%d, color=%ld\n", + scan->scan_hit_start, scan->scan_hit_end, + scan->scan_size, scan->scan_alignment, scan->scan_color); +} + +static void show_holes(const struct drm_mm *mm, int count) +{ + u64 hole_start, hole_end; + struct drm_mm_node *hole; + + drm_mm_for_each_hole(hole, mm, hole_start, hole_end) { + struct drm_mm_node *next = list_next_entry(hole, node_list); + const char *node1 = NULL, *node2 = NULL; + + if (hole->allocated) + node1 = kasprintf(GFP_KERNEL, + "[%llx + %lld, color=%ld], ", + hole->start, hole->size, hole->color); + + if (next->allocated) + node2 = kasprintf(GFP_KERNEL, + ", [%llx + %lld, color=%ld]", + next->start, next->size, next->color); + + pr_info("%sHole [%llx - %llx, size %lld]%s\n", + node1, + hole_start, hole_end, hole_end - hole_start, + node2); + + kfree(node2); + kfree(node1); + + if (!--count) + break; + } +} + +struct evict_node { + struct drm_mm_node node; + struct list_head link; +}; + +static bool evict_nodes(struct drm_mm *mm, + struct evict_node *nodes, + unsigned int *order, + unsigned int count, + struct list_head *evict_list) +{ + struct evict_node *e, *en; + unsigned int i; + + for (i = 0; i < count; i++) { + e = &nodes[order ? order[i] : i]; + list_add(&e->link, evict_list); + if (drm_mm_scan_add_block(&e->node)) + break; + } + list_for_each_entry_safe(e, en, evict_list, link) { + if (!drm_mm_scan_remove_block(&e->node)) + list_del(&e->link); + } + if (list_empty(evict_list)) { + pr_err("Failed to find eviction: size=%lld [avail=%d], align=%d (color=%lu)\n", + mm->scan_size, count, + mm->scan_alignment, + mm->scan_color); + return false; + } + + list_for_each_entry(e, evict_list, link) + drm_mm_remove_node(&e->node); + + return true; +} + +static bool evict_nothing(struct drm_mm *mm, + unsigned int total_size, + struct evict_node *nodes) +{ + LIST_HEAD(evict_list); + struct evict_node *e; + struct drm_mm_node *node; + unsigned int n; + + drm_mm_init_scan(mm, 1, 0, 0); + for (n = 0; n < total_size; n++) { + e = &nodes[n]; + list_add(&e->link, &evict_list); + drm_mm_scan_add_block(&e->node); + } + list_for_each_entry(e, &evict_list, link) + drm_mm_scan_remove_block(&e->node); + + for (n = 0; n < total_size; n++) { + e = &nodes[n]; + + if (!drm_mm_node_allocated(&e->node)) { + pr_err("node[%d] no longer allocated!\n", n); + return false; + } + + e->link.next = NULL; + } + + drm_mm_for_each_node(node, mm) { + e = container_of(node, typeof(*e), node); + e->link.next = &e->link; + } + + for (n = 0; n < total_size; n++) { + e = &nodes[n]; + + if (!e->link.next) { + pr_err("node[%d] no longer connected!\n", n); + return false; + } + } + + return assert_continuous(mm, nodes[0].node.size); +} + +static bool evict_everything(struct drm_mm *mm, + unsigned int total_size, + struct evict_node *nodes) +{ + LIST_HEAD(evict_list); + struct evict_node *e; + unsigned int n; + int err; + + drm_mm_init_scan(mm, total_size, 0, 0); + for (n = 0; n < total_size; n++) { + e = &nodes[n]; + list_add(&e->link, &evict_list); + drm_mm_scan_add_block(&e->node); + } + list_for_each_entry(e, &evict_list, link) { + if (!drm_mm_scan_remove_block(&e->node)) { + pr_err("Node %lld not marked for eviction!\n", + e->node.start); + list_del(&e->link); + } + } + + list_for_each_entry(e, &evict_list, link) + drm_mm_remove_node(&e->node); + + if (!assert_one_hole(mm, 0, total_size)) + return false; + + list_for_each_entry(e, &evict_list, link) { + err = drm_mm_reserve_node(mm, &e->node); + if (err) { + pr_err("Failed to reinsert node after eviction: start=%llx\n", + e->node.start); + return false; + } + } + + return assert_continuous(mm, nodes[0].node.size); +} + +static int evict_something(struct drm_mm *mm, + struct evict_node *nodes, + unsigned int *order, + unsigned int count, + unsigned int size, + unsigned int alignment, + const struct insert_mode *mode) +{ + LIST_HEAD(evict_list); + struct evict_node *e; + struct drm_mm_node tmp; + int err; + + drm_mm_init_scan(mm, size, alignment, 0); + if (!evict_nodes(mm, + nodes, order, count, + &evict_list)) + return -EINVAL; + + memset(&tmp, 0, sizeof(tmp)); + err = drm_mm_insert_node_generic(mm, &tmp, size, alignment, 0, + mode->search_flags, + mode->create_flags); + if (err) { + pr_err("Failed to insert into eviction hole: size=%d, align=%d\n", + size, alignment); + show_scan(mm); + show_holes(mm, 3); + return err; + } + + if (!assert_node(&tmp, mm, size, alignment, 0) || tmp.hole_follows) { + pr_err("Inserted did not fill the eviction hole: size=%lld [%d], align=%d [rem=%lld], start=%llx, hole-follows?=%d\n", + tmp.size, size, + alignment, misalignment(&tmp, alignment), + tmp.start, tmp.hole_follows); + err = -EINVAL; + } + + drm_mm_remove_node(&tmp); + if (err) + return err; + + list_for_each_entry(e, &evict_list, link) { + err = drm_mm_reserve_node(mm, &e->node); + if (err) { + pr_err("Failed to reinsert node after eviction: start=%llx\n", + e->node.start); + return err; + } + } + + if (!assert_continuous(mm, nodes[0].node.size)) { + pr_err("range is no longer continuous\n"); + return -EINVAL; + } + + return 0; +} + +static int igt_evict(void *ignored) +{ + DRM_RND_STATE(prng, random_seed); + const unsigned int size = 8192; + const struct insert_mode *mode; + struct drm_mm mm; + struct evict_node *nodes; + struct drm_mm_node *node, *next; + unsigned int *order, n; + int ret, err; + + /* Here we populate a full drm_mm and then try and insert a new node + * by evicting other nodes in a random order. The drm_mm_scan should + * pick the first matching hole it finds from the random list. We + * repeat that for different allocation strategies, alignments and + * sizes to try and stress the hole finder. + */ + + ret = -ENOMEM; + nodes = vzalloc(size * sizeof(*nodes)); + if (!nodes) + goto err; + + order = drm_random_order(size, &prng); + if (!order) + goto err_nodes; + + ret = -EINVAL; + drm_mm_init(&mm, 0, size); + for (n = 0; n < size; n++) { + err = drm_mm_insert_node(&mm, &nodes[n].node, 1, 0, + DRM_MM_SEARCH_DEFAULT); + if (err) { + pr_err("insert failed, step %d\n", n); + ret = err; + goto out; + } + } + + /* First check that using the scanner doesn't break the mm */ + if (!evict_nothing(&mm, size, nodes)) { + pr_err("evict_nothing() failed\n"); + goto out; + } + if (!evict_everything(&mm, size, nodes)) { + pr_err("evict_everything() failed\n"); + goto out; + } + + for (mode = evict_modes; mode->name; mode++) { + for (n = 1; n <= size; n <<= 1) { + drm_random_reorder(order, size, &prng); + err = evict_something(&mm, + nodes, order, size, + n, 1, + mode); + if (err) { + pr_err("%s evict_something(size=%u) failed\n", + mode->name, n); + ret = err; + goto out; + } + } + + for (n = 1; n < size; n <<= 1) { + drm_random_reorder(order, size, &prng); + err = evict_something(&mm, + nodes, order, size, + size/2, n, + mode); + if (err) { + pr_err("%s evict_something(size=%u, alignment=%u) failed\n", + mode->name, size/2, n); + ret = err; + goto out; + } + } + + for_each_prime_number_from(n, 1, min(size, max_prime)) { + unsigned int nsize = (size - n + 1) / 2; + + DRM_MM_BUG_ON(!nsize); + + drm_random_reorder(order, size, &prng); + err = evict_something(&mm, + nodes, order, size, + nsize, n, + mode); + if (err) { + pr_err("%s evict_something(size=%u, alignment=%u) failed\n", + mode->name, nsize, n); + ret = err; + goto out; + } + } + } + + ret = 0; +out: + drm_mm_for_each_node_safe(node, next, &mm) + drm_mm_remove_node(node); + drm_mm_takedown(&mm); + kfree(order); +err_nodes: + vfree(nodes); +err: + return ret; +} + #include "drm_selftest.c"

static int __init test_drm_mm_init(void)

Check that if we request top-down allocation from drm_mm_insert_node() we receive the next available hole from the top.

v2: Flip sign on conditional assert.

Signed-off-by: Chris Wilson chris@chris-wilson.co.uk Reviewed-by: Joonas Lahtinen joonas.lahtinen@linux.intel.com --- drivers/gpu/drm/selftests/drm_mm_selftests.h | 1 + drivers/gpu/drm/selftests/test-drm_mm.c | 119 +++++++++++++++++++++++++++ 2 files changed, 120 insertions(+)

diff --git a/drivers/gpu/drm/selftests/drm_mm_selftests.h b/drivers/gpu/drm/selftests/drm_mm_selftests.h index 965aca65c160..cd508e3d6538 100644 --- a/drivers/gpu/drm/selftests/drm_mm_selftests.h +++ b/drivers/gpu/drm/selftests/drm_mm_selftests.h @@ -17,3 +17,4 @@ selftest(align32, igt_align32) selftest(align64, igt_align64) selftest(evict, igt_evict) selftest(evict_range, igt_evict_range) +selftest(topdown, igt_topdown) diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c index d49115186967..d3d4e4f39042 100644 --- a/drivers/gpu/drm/selftests/test-drm_mm.c +++ b/drivers/gpu/drm/selftests/test-drm_mm.c @@ -1552,6 +1552,125 @@ static int igt_evict_range(void *ignored) return ret; }

+static unsigned int node_index(const struct drm_mm_node *node) +{ + return div64_u64(node->start, node->size); +} + +static int igt_topdown(void *ignored) +{ + const struct insert_mode *topdown = &insert_modes[TOPDOWN]; + DRM_RND_STATE(prng, random_seed); + const unsigned int count = 8192; + unsigned int size; + unsigned long *bitmap = NULL; + struct drm_mm mm; + struct drm_mm_node *nodes, *node, *next; + unsigned int *order, n, m, o = 0; + int ret; + + /* When allocating top-down, we expect to be returned a node + * from a suitable hole at the top of the drm_mm. We check that + * the returned node does match the highest available slot. + */ + + ret = -ENOMEM; + nodes = vzalloc(count * sizeof(*nodes)); + if (!nodes) + goto err; + + bitmap = kzalloc(count / BITS_PER_LONG * sizeof(unsigned long), + GFP_TEMPORARY); + if (!bitmap) + goto err_nodes; + + order = drm_random_order(count, &prng); + if (!order) + goto err_bitmap; + + ret = -EINVAL; + for (size = 1; size <= 64; size <<= 1) { + drm_mm_init(&mm, 0, size*count); + for (n = 0; n < count; n++) { + if (!expect_insert(&mm, &nodes[n], + size, 0, n, + topdown)) { + pr_err("insert failed, size %u step %d\n", size, n); + goto out; + } + + if (nodes[n].hole_follows) { + pr_err("hole after topdown insert %d, start=%llx\n, size=%u", + n, nodes[n].start, size); + goto out; + } + + if (!assert_one_hole(&mm, 0, size*(count - n - 1))) + goto out; + } + + if (!assert_continuous(&mm, size)) + goto out; + + drm_random_reorder(order, count, &prng); + for_each_prime_number_from(n, 1, min(count, max_prime)) { + for (m = 0; m < n; m++) { + node = &nodes[order[(o + m) % count]]; + drm_mm_remove_node(node); + __set_bit(node_index(node), bitmap); + } + + for (m = 0; m < n; m++) { + unsigned int last; + + node = &nodes[order[(o + m) % count]]; + if (!expect_insert(&mm, node, + size, 0, 0, + topdown)) { + pr_err("insert failed, step %d/%d\n", m, n); + goto out; + } + + if (node->hole_follows) { + pr_err("hole after topdown insert %d/%d, start=%llx\n", + m, n, node->start); + goto out; + } + + last = find_last_bit(bitmap, count); + if (node_index(node) != last) { + pr_err("node %d/%d, size %d, not inserted into upmost hole, expected %d, found %d\n", + m, n, size, last, node_index(node)); + goto out; + } + + __clear_bit(last, bitmap); + } + + DRM_MM_BUG_ON(find_first_bit(bitmap, count) != count); + + o += n; + } + + drm_mm_for_each_node_safe(node, next, &mm) + drm_mm_remove_node(node); + DRM_MM_BUG_ON(!drm_mm_clean(&mm)); + } + + ret = 0; +out: + drm_mm_for_each_node_safe(node, next, &mm) + drm_mm_remove_node(node); + drm_mm_takedown(&mm); + kfree(order); +err_bitmap: + kfree(bitmap); +err_nodes: + vfree(nodes); +err: + return ret; +} + #include "drm_selftest.c"

static int __init test_drm_mm_init(void)

Check that after applying the driver's color adjustment, eviction scanning finds a suitable hole.

Signed-off-by: Chris Wilson chris@chris-wilson.co.uk Reviewed-by: Joonas Lahtinen joonas.lahtinen@linux.intel.com --- drivers/gpu/drm/selftests/drm_mm_selftests.h | 1 + drivers/gpu/drm/selftests/test-drm_mm.c | 156 +++++++++++++++++++++++++++ 2 files changed, 157 insertions(+)

diff --git a/drivers/gpu/drm/selftests/drm_mm_selftests.h b/drivers/gpu/drm/selftests/drm_mm_selftests.h index ff44f39a1826..0a3a7e32e5f7 100644 --- a/drivers/gpu/drm/selftests/drm_mm_selftests.h +++ b/drivers/gpu/drm/selftests/drm_mm_selftests.h @@ -19,3 +19,4 @@ selftest(evict, igt_evict) selftest(evict_range, igt_evict_range) selftest(topdown, igt_topdown) selftest(color, igt_color) +selftest(color_evict, igt_color_evict) diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c index 24841d3994dc..6584e4ce96af 100644 --- a/drivers/gpu/drm/selftests/test-drm_mm.c +++ b/drivers/gpu/drm/selftests/test-drm_mm.c @@ -1854,6 +1854,162 @@ static int igt_color(void *ignored) return ret; }

+static int evict_color(struct drm_mm *mm, + struct evict_node *nodes, + unsigned int *order, + unsigned int count, + unsigned int size, + unsigned int alignment, + unsigned long color, + const struct insert_mode *mode) +{ + LIST_HEAD(evict_list); + struct evict_node *e; + struct drm_mm_node tmp; + int err; + + drm_mm_init_scan(mm, size, alignment, color); + if (!evict_nodes(mm, + nodes, order, count, + &evict_list)) + return -EINVAL; + + memset(&tmp, 0, sizeof(tmp)); + err = drm_mm_insert_node_generic(mm, &tmp, size, alignment, color, + mode->search_flags, + mode->create_flags); + if (err) { + pr_err("Failed to insert into eviction hole: size=%d, align=%d, color=%lu, err=%d\n", + size, alignment, color, err); + show_scan(mm); + show_holes(mm, 3); + return err; + } + + if (colors_abutt(&tmp)) + err = -EINVAL; + + if (!assert_node(&tmp, mm, size, alignment, color)) { + pr_err("Inserted did not fit the eviction hole: size=%lld [%d], align=%d [rem=%lld], start=%llx\n", + tmp.size, size, + alignment, misalignment(&tmp, alignment), tmp.start); + err = -EINVAL; + } + + drm_mm_remove_node(&tmp); + if (err) + return err; + + list_for_each_entry(e, &evict_list, link) { + err = drm_mm_reserve_node(mm, &e->node); + if (err) { + pr_err("Failed to reinsert node after eviction: start=%llx\n", + e->node.start); + return err; + } + } + + return 0; +} + +static int igt_color_evict(void *ignored) +{ + DRM_RND_STATE(prng, random_seed); + const unsigned int total_size = min(8192u, max_iterations); + const struct insert_mode *mode; + unsigned long color = 0; + struct drm_mm mm; + struct evict_node *nodes; + struct drm_mm_node *node, *next; + unsigned int *order, n; + int ret, err; + + /* Check that the drm_mm_scan also honours color adjustment when + * choosing its victims to create a hole. Our color_adjust does not + * allow two nodes to be placed together without an intervening hole + * enlarging the set of victims that must be evicted. + */ + + ret = -ENOMEM; + nodes = vzalloc(total_size * sizeof(*nodes)); + if (!nodes) + goto err; + + order = drm_random_order(total_size, &prng); + if (!order) + goto err_nodes; + + ret = -EINVAL; + drm_mm_init(&mm, 0, 2*total_size - 1); + mm.color_adjust = separate_adjacent_colors; + for (n = 0; n < total_size; n++) { + if (!expect_insert(&mm, &nodes[n].node, + 1, 0, color++, + &insert_modes[0])) { + pr_err("insert failed, step %d\n", n); + goto out; + } + } + + for (mode = evict_modes; mode->name; mode++) { + for (n = 1; n <= total_size; n <<= 1) { + drm_random_reorder(order, total_size, &prng); + err = evict_color(&mm, + nodes, order, total_size, + n, 1, color++, + mode); + if (err) { + pr_err("%s evict_color(size=%u) failed\n", + mode->name, n); + goto out; + } + } + + for (n = 1; n < total_size; n <<= 1) { + drm_random_reorder(order, total_size, &prng); + err = evict_color(&mm, + nodes, order, total_size, + total_size/2, n, color++, + mode); + if (err) { + pr_err("%s evict_color(size=%u, alignment=%u) failed\n", + mode->name, total_size/2, n); + goto out; + } + } + + for_each_prime_number_from(n, 1, min(total_size, max_prime)) { + unsigned int nsize = (total_size - n + 1) / 2; + + DRM_MM_BUG_ON(!nsize); + + drm_random_reorder(order, total_size, &prng); + err = evict_color(&mm, + nodes, order, total_size, + nsize, n, color++, + mode); + if (err) { + pr_err("%s evict_color(size=%u, alignment=%u) failed\n", + mode->name, nsize, n); + goto out; + } + } + } + + ret = 0; +out: + if (ret) + drm_mm_debug_table(&mm, __func__); + drm_mm_for_each_node_safe(node, next, &mm) + drm_mm_remove_node(node); + drm_mm_takedown(&mm); + kfree(order); +err_nodes: + vfree(nodes); +err: + return ret; +} + #include "drm_selftest.c"

static int __init test_drm_mm_init(void)

Build the struct drm_mm selftests so that we can trivially run them within our CI.

"Enable debug, become developer." - Joonas Lahtinen

Signed-off-by: Chris Wilson chris@chris-wilson.co.uk Reviewed-by: Joonas Lahtinen joonas.lahtinen@linux.intel.com --- drivers/gpu/drm/i915/Kconfig.debug | 1 + 1 file changed, 1 insertion(+)

diff --git a/drivers/gpu/drm/i915/Kconfig.debug b/drivers/gpu/drm/i915/Kconfig.debug index 597648c7a645..598551dbf62c 100644 --- a/drivers/gpu/drm/i915/Kconfig.debug +++ b/drivers/gpu/drm/i915/Kconfig.debug @@ -24,6 +24,7 @@ config DRM_I915_DEBUG select X86_MSR # used by igt/pm_rpm select DRM_VGEM # used by igt/prime_vgem (dmabuf interop checks) select DRM_DEBUG_MM if DRM=y + select DRM_DEBUG_MM_SELFTEST select DRM_I915_SW_FENCE_DEBUG_OBJECTS default n help

In places (e.g. i915.ko), the alignment is exported to userspace as u64 and there now exists hardware for which we can indeed utilize a u64 alignment. As such, we need to keep 64bit integers throughout when handling alignment.

Testcase: igt/drm_mm/align64 Testcase: igt/gem_exec_alignment Signed-off-by: Chris Wilson chris@chris-wilson.co.uk Cc: Joonas Lahtinen joonas.lahtinen@linux.intel.com Cc: Christian König christian.koenig@amd.com Reviewed-by: Christian König christian.koenig@amd.com --- drivers/gpu/drm/drm_mm.c | 37 +++++++++++++++------------------ drivers/gpu/drm/selftests/test-drm_mm.c | 4 ++-- include/drm/drm_mm.h | 16 +++++++------- 3 files changed, 27 insertions(+), 30 deletions(-)

diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c index 9756542abe4c..fd2667052c73 100644 --- a/drivers/gpu/drm/drm_mm.c +++ b/drivers/gpu/drm/drm_mm.c @@ -93,12 +93,12 @@

static struct drm_mm_node *drm_mm_search_free_generic(const struct drm_mm *mm, u64 size, - unsigned alignment, + u64 alignment, unsigned long color, enum drm_mm_search_flags flags); static struct drm_mm_node *drm_mm_search_free_in_range_generic(const struct drm_mm *mm, u64 size, - unsigned alignment, + u64 alignment, unsigned long color, u64 start, u64 end, @@ -227,7 +227,7 @@ static void drm_mm_interval_tree_add_node(struct drm_mm_node *hole_node,

static void drm_mm_insert_helper(struct drm_mm_node *hole_node, struct drm_mm_node *node, - u64 size, unsigned alignment, + u64 size, u64 alignment, unsigned long color, enum drm_mm_allocator_flags flags) { @@ -246,10 +246,9 @@ static void drm_mm_insert_helper(struct drm_mm_node *hole_node, adj_start = adj_end - size;

if (alignment) { - u64 tmp = adj_start; - unsigned rem; + u64 rem;

- rem = do_div(tmp, alignment); + div64_u64_rem(adj_start, alignment, &rem); if (rem) { if (flags & DRM_MM_CREATE_TOP) adj_start -= rem; @@ -376,7 +375,7 @@ EXPORT_SYMBOL(drm_mm_reserve_node); * 0 on success, -ENOSPC if there's no suitable hole. */ int drm_mm_insert_node_generic(struct drm_mm *mm, struct drm_mm_node *node, - u64 size, unsigned alignment, + u64 size, u64 alignment, unsigned long color, enum drm_mm_search_flags sflags, enum drm_mm_allocator_flags aflags) @@ -398,7 +397,7 @@ EXPORT_SYMBOL(drm_mm_insert_node_generic);

static void drm_mm_insert_helper_range(struct drm_mm_node *hole_node, struct drm_mm_node *node, - u64 size, unsigned alignment, + u64 size, u64 alignment, unsigned long color, u64 start, u64 end, enum drm_mm_allocator_flags flags) @@ -423,10 +422,9 @@ static void drm_mm_insert_helper_range(struct drm_mm_node *hole_node, adj_start = adj_end - size;

if (alignment) { - u64 tmp = adj_start; - unsigned rem; + u64 rem;

- rem = do_div(tmp, alignment); + div64_u64_rem(adj_start, alignment, &rem); if (rem) { if (flags & DRM_MM_CREATE_TOP) adj_start -= rem; @@ -482,7 +480,7 @@ static void drm_mm_insert_helper_range(struct drm_mm_node *hole_node, * 0 on success, -ENOSPC if there's no suitable hole. */ int drm_mm_insert_node_in_range_generic(struct drm_mm *mm, struct drm_mm_node *node, - u64 size, unsigned alignment, + u64 size, u64 alignment, unsigned long color, u64 start, u64 end, enum drm_mm_search_flags sflags, @@ -548,16 +546,15 @@ void drm_mm_remove_node(struct drm_mm_node *node) } EXPORT_SYMBOL(drm_mm_remove_node);

-static int check_free_hole(u64 start, u64 end, u64 size, unsigned alignment) +static int check_free_hole(u64 start, u64 end, u64 size, u64 alignment) { if (end - start < size) return 0;

if (alignment) { - u64 tmp = start; - unsigned rem; + u64 rem;

- rem = do_div(tmp, alignment); + div64_u64_rem(start, alignment, &rem); if (rem) start += alignment - rem; } @@ -567,7 +564,7 @@ static int check_free_hole(u64 start, u64 end, u64 size, unsigned alignment)

static struct drm_mm_node *drm_mm_search_free_generic(const struct drm_mm *mm, u64 size, - unsigned alignment, + u64 alignment, unsigned long color, enum drm_mm_search_flags flags) { @@ -609,7 +606,7 @@ static struct drm_mm_node *drm_mm_search_free_generic(const struct drm_mm *mm,

static struct drm_mm_node *drm_mm_search_free_in_range_generic(const struct drm_mm *mm, u64 size, - unsigned alignment, + u64 alignment, unsigned long color, u64 start, u64 end, @@ -729,7 +726,7 @@ EXPORT_SYMBOL(drm_mm_replace_node); */ void drm_mm_init_scan(struct drm_mm *mm, u64 size, - unsigned alignment, + u64 alignment, unsigned long color) { mm->scan_color = color; @@ -762,7 +759,7 @@ EXPORT_SYMBOL(drm_mm_init_scan); */ void drm_mm_init_scan_with_range(struct drm_mm *mm, u64 size, - unsigned alignment, + u64 alignment, unsigned long color, u64 start, u64 end) diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c index fb8f7056225b..e2ed9efb361c 100644 --- a/drivers/gpu/drm/selftests/test-drm_mm.c +++ b/drivers/gpu/drm/selftests/test-drm_mm.c @@ -1116,7 +1116,7 @@ static int igt_align64(void *ignored)

static void show_scan(const struct drm_mm *scan) { - pr_info("scan: hit [%llx, %llx], size=%lld, align=%d, color=%ld\n", + pr_info("scan: hit [%llx, %llx], size=%lld, align=%lld, color=%ld\n", scan->scan_hit_start, scan->scan_hit_end, scan->scan_size, scan->scan_alignment, scan->scan_color); } @@ -1178,7 +1178,7 @@ static bool evict_nodes(struct drm_mm *mm, list_del(&e->link); } if (list_empty(evict_list)) { - pr_err("Failed to find eviction: size=%lld [avail=%d], align=%d (color=%lu)\n", + pr_err("Failed to find eviction: size=%lld [avail=%d], align=%lld (color=%lu)\n", mm->scan_size, count, mm->scan_alignment, mm->scan_color); diff --git a/include/drm/drm_mm.h b/include/drm/drm_mm.h index 525543019896..0ce8c3678c11 100644 --- a/include/drm/drm_mm.h +++ b/include/drm/drm_mm.h @@ -98,12 +98,12 @@ struct drm_mm { struct rb_root interval_tree;

unsigned int scan_check_range : 1; - unsigned scan_alignment; + unsigned int scanned_blocks; unsigned long scan_color; + u64 scan_alignment; u64 scan_size; u64 scan_hit_start; u64 scan_hit_end; - unsigned scanned_blocks; u64 scan_start; u64 scan_end; struct drm_mm_node *prev_scanned_node; @@ -261,7 +261,7 @@ int drm_mm_reserve_node(struct drm_mm *mm, struct drm_mm_node *node); int drm_mm_insert_node_generic(struct drm_mm *mm, struct drm_mm_node *node, u64 size, - unsigned alignment, + u64 alignment, unsigned long color, enum drm_mm_search_flags sflags, enum drm_mm_allocator_flags aflags); @@ -284,7 +284,7 @@ int drm_mm_insert_node_generic(struct drm_mm *mm, static inline int drm_mm_insert_node(struct drm_mm *mm, struct drm_mm_node *node, u64 size, - unsigned alignment, + u64 alignment, enum drm_mm_search_flags flags) { return drm_mm_insert_node_generic(mm, node, size, alignment, 0, flags, @@ -294,7 +294,7 @@ static inline int drm_mm_insert_node(struct drm_mm *mm, int drm_mm_insert_node_in_range_generic(struct drm_mm *mm, struct drm_mm_node *node, u64 size, - unsigned alignment, + u64 alignment, unsigned long color, u64 start, u64 end, @@ -321,7 +321,7 @@ int drm_mm_insert_node_in_range_generic(struct drm_mm *mm, static inline int drm_mm_insert_node_in_range(struct drm_mm *mm, struct drm_mm_node *node, u64 size, - unsigned alignment, + u64 alignment, u64 start, u64 end, enum drm_mm_search_flags flags) @@ -361,11 +361,11 @@ __drm_mm_interval_first(const struct drm_mm *mm, u64 start, u64 last);

void drm_mm_init_scan(struct drm_mm *mm, u64 size, - unsigned alignment, + u64 alignment, unsigned long color); void drm_mm_init_scan_with_range(struct drm_mm *mm, u64 size, - unsigned alignment, + u64 alignment, unsigned long color, u64 start, u64 end);

Protect ourselves from a caller passing in node.start + node.size that will overflow and trick us into reserving that node.

Signed-off-by: Chris Wilson chris@chris-wilson.co.uk Reviewed-by: Joonas Lahtinen joonas.lahtinen@linux.intel.com --- drivers/gpu/drm/drm_mm.c | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-)

diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c index 767cfd05c628..370cb8ee91c9 100644 --- a/drivers/gpu/drm/drm_mm.c +++ b/drivers/gpu/drm/drm_mm.c @@ -308,10 +308,9 @@ int drm_mm_reserve_node(struct drm_mm *mm, struct drm_mm_node *node) u64 hole_start, hole_end; u64 adj_start, adj_end;

- if (WARN_ON(node->size == 0)) - return -EINVAL; - end = node->start + node->size; + if (unlikely(end <= node->start)) + return -ENOSPC;

/* Find the relevant hole to add our node to */ hole = drm_mm_interval_tree_iter_first(&mm->interval_tree,

A simple assert to ensure that we don't overflow start + size when initialising the drm_mm, or its scanner.

In future, we may want to switch to tracking the value of ranges (rather than size) so that we can cover the full u64, for example like resource tracking.

Signed-off-by: Chris Wilson chris@chris-wilson.co.uk Reviewed-by: Joonas Lahtinen joonas.lahtinen@linux.intel.com --- drivers/gpu/drm/drm_mm.c | 7 +++++++ 1 file changed, 7 insertions(+)

diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c index e0419cf09bbb..b80305484124 100644 --- a/drivers/gpu/drm/drm_mm.c +++ b/drivers/gpu/drm/drm_mm.c @@ -729,6 +729,8 @@ void drm_mm_init_scan(struct drm_mm *mm, u64 alignment, unsigned long color) { + DRM_MM_BUG_ON(!size); + mm->scan_color = color; mm->scan_alignment = alignment; mm->scan_size = size; @@ -764,6 +766,9 @@ void drm_mm_init_scan_with_range(struct drm_mm *mm, u64 start, u64 end) { + DRM_MM_BUG_ON(start >= end); + DRM_MM_BUG_ON(!size || size > end - start); + mm->scan_color = color; mm->scan_alignment = alignment; mm->scan_size = size; @@ -882,6 +887,8 @@ EXPORT_SYMBOL(drm_mm_scan_remove_block); */ void drm_mm_init(struct drm_mm *mm, u64 start, u64 size) { + DRM_MM_BUG_ON(start + size <= start); + INIT_LIST_HEAD(&mm->hole_stack); mm->scanned_blocks = 0;

The scan state occupies a large proportion of the struct drm_mm and is rarely used and only contains temporary state. That makes it suitable to moving to its struct and onto the stack of the callers.

Signed-off-by: Chris Wilson chris@chris-wilson.co.uk Reviewed-by: Joonas Lahtinen joonas.lahtinen@linux.intel.com --- drivers/gpu/drm/drm_mm.c | 124 ++++++++++++++++++-------------- drivers/gpu/drm/etnaviv/etnaviv_mmu.c | 7 +- drivers/gpu/drm/i915/i915_gem_evict.c | 19 +++-- drivers/gpu/drm/selftests/test-drm_mm.c | 45 ++++++------ include/drm/drm_mm.h | 43 +++++++---- 5 files changed, 138 insertions(+), 100 deletions(-)

diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c index b80305484124..21bd2e13738b 100644 --- a/drivers/gpu/drm/drm_mm.c +++ b/drivers/gpu/drm/drm_mm.c @@ -574,7 +574,7 @@ static struct drm_mm_node *drm_mm_search_free_generic(const struct drm_mm *mm, u64 adj_end; u64 best_size;

- DRM_MM_BUG_ON(mm->scanned_blocks); + DRM_MM_BUG_ON(mm->scan_active);

best = NULL; best_size = ~0UL; @@ -618,7 +618,7 @@ static struct drm_mm_node *drm_mm_search_free_in_range_generic(const struct drm_ u64 adj_end; u64 best_size;

- DRM_MM_BUG_ON(mm->scanned_blocks); + DRM_MM_BUG_ON(mm->scan_active);

best = NULL; best_size = ~0UL; @@ -693,7 +693,7 @@ EXPORT_SYMBOL(drm_mm_replace_node); * * The DRM range allocator supports this use-case through the scanning * interfaces. First a scan operation needs to be initialized with - * drm_mm_init_scan() or drm_mm_init_scan_with_range(). The driver adds + * drm_mm_scan_init() or drm_mm_scan_init_with_range(). The driver adds * objects to the roaster (probably by walking an LRU list, but this can be * freely implemented) until a suitable hole is found or there's no further * evictable object. @@ -710,7 +710,8 @@ EXPORT_SYMBOL(drm_mm_replace_node); */

/** - * drm_mm_init_scan - initialize lru scanning + * drm_mm_scan_init - initialize lru scanning + * @scan: scan state * @mm: drm_mm to scan * @size: size of the allocation * @alignment: alignment of the allocation @@ -724,26 +725,33 @@ EXPORT_SYMBOL(drm_mm_replace_node); * As long as the scan list is non-empty, no other operations than * adding/removing nodes to/from the scan list are allowed. */ -void drm_mm_init_scan(struct drm_mm *mm, +void drm_mm_scan_init(struct drm_mm_scan *scan, + struct drm_mm *mm, u64 size, u64 alignment, unsigned long color) { DRM_MM_BUG_ON(!size); + DRM_MM_BUG_ON(mm->scan_active);

- mm->scan_color = color; - mm->scan_alignment = alignment; - mm->scan_size = size; - mm->scanned_blocks = 0; - mm->scan_hit_start = 0; - mm->scan_hit_end = 0; - mm->scan_check_range = 0; - mm->prev_scanned_node = NULL; + scan->mm = mm; + + scan->color = color; + scan->alignment = alignment; + scan->size = size; + + scan->check_range = 0; + + scan->hit_start = U64_MAX; + scan->hit_end = 0; + + scan->prev_scanned_node = NULL; } -EXPORT_SYMBOL(drm_mm_init_scan); +EXPORT_SYMBOL(drm_mm_scan_init);

/** - * drm_mm_init_scan - initialize range-restricted lru scanning + * drm_mm_scan_init_with_range - initialize range-restricted lru scanning + * @scan: scan state * @mm: drm_mm to scan * @size: size of the allocation * @alignment: alignment of the allocation @@ -759,7 +767,8 @@ EXPORT_SYMBOL(drm_mm_init_scan); * As long as the scan list is non-empty, no other operations than * adding/removing nodes to/from the scan list are allowed. */ -void drm_mm_init_scan_with_range(struct drm_mm *mm, +void drm_mm_scan_init_with_range(struct drm_mm_scan *scan, + struct drm_mm *mm, u64 size, u64 alignment, unsigned long color, @@ -768,19 +777,25 @@ void drm_mm_init_scan_with_range(struct drm_mm *mm, { DRM_MM_BUG_ON(start >= end); DRM_MM_BUG_ON(!size || size > end - start); + DRM_MM_BUG_ON(mm->scan_active); + + scan->mm = mm; + + scan->color = color; + scan->alignment = alignment; + scan->size = size; + + DRM_MM_BUG_ON(end <= start); + scan->range_start = start; + scan->range_end = end; + scan->check_range = 1;

- mm->scan_color = color; - mm->scan_alignment = alignment; - mm->scan_size = size; - mm->scanned_blocks = 0; - mm->scan_hit_start = 0; - mm->scan_hit_end = 0; - mm->scan_start = start; - mm->scan_end = end; - mm->scan_check_range = 1; - mm->prev_scanned_node = NULL; + scan->hit_start = U64_MAX; + scan->hit_end = 0; + + scan->prev_scanned_node = NULL; } -EXPORT_SYMBOL(drm_mm_init_scan_with_range); +EXPORT_SYMBOL(drm_mm_scan_init_with_range);

/** * drm_mm_scan_add_block - add a node to the scan list @@ -792,46 +807,46 @@ EXPORT_SYMBOL(drm_mm_init_scan_with_range); * Returns: * True if a hole has been found, false otherwise. */ -bool drm_mm_scan_add_block(struct drm_mm_node *node) +bool drm_mm_scan_add_block(struct drm_mm_scan *scan, + struct drm_mm_node *node) { - struct drm_mm *mm = node->mm; + struct drm_mm *mm = scan->mm; struct drm_mm_node *prev_node; u64 hole_start, hole_end; u64 adj_start, adj_end;

- mm->scanned_blocks++; - + DRM_MM_BUG_ON(node->mm != mm); + DRM_MM_BUG_ON(!node->allocated); DRM_MM_BUG_ON(node->scanned_block); node->scanned_block = 1; + mm->scan_active++;

- prev_node = list_entry(node->node_list.prev, struct drm_mm_node, - node_list); + prev_node = list_prev_entry(node, node_list);

node->scanned_preceeds_hole = prev_node->hole_follows; prev_node->hole_follows = 1; list_del(&node->node_list); node->node_list.prev = &prev_node->node_list; - node->node_list.next = &mm->prev_scanned_node->node_list; - mm->prev_scanned_node = node; + node->node_list.next = &scan->prev_scanned_node->node_list; + scan->prev_scanned_node = node;

adj_start = hole_start = drm_mm_hole_node_start(prev_node); adj_end = hole_end = drm_mm_hole_node_end(prev_node);

- if (mm->scan_check_range) { - if (adj_start < mm->scan_start) - adj_start = mm->scan_start; - if (adj_end > mm->scan_end) - adj_end = mm->scan_end; + if (scan->check_range) { + if (adj_start < scan->range_start) + adj_start = scan->range_start; + if (adj_end > scan->range_end) + adj_end = scan->range_end; }

if (mm->color_adjust) - mm->color_adjust(prev_node, mm->scan_color, - &adj_start, &adj_end); + mm->color_adjust(prev_node, scan->color, &adj_start, &adj_end);

if (check_free_hole(adj_start, adj_end, - mm->scan_size, mm->scan_alignment)) { - mm->scan_hit_start = hole_start; - mm->scan_hit_end = hole_end; + scan->size, scan->alignment)) { + scan->hit_start = hole_start; + scan->hit_end = hole_end; return true; }

@@ -856,24 +871,25 @@ EXPORT_SYMBOL(drm_mm_scan_add_block); * True if this block should be evicted, false otherwise. Will always * return false when no hole has been found. */ -bool drm_mm_scan_remove_block(struct drm_mm_node *node) +bool drm_mm_scan_remove_block(struct drm_mm_scan *scan, + struct drm_mm_node *node) { - struct drm_mm *mm = node->mm; struct drm_mm_node *prev_node;

- mm->scanned_blocks--; - + DRM_MM_BUG_ON(node->mm != scan->mm); DRM_MM_BUG_ON(!node->scanned_block); node->scanned_block = 0;

- prev_node = list_entry(node->node_list.prev, struct drm_mm_node, - node_list); + DRM_MM_BUG_ON(!node->mm->scan_active); + node->mm->scan_active--; + + prev_node = list_prev_entry(node, node_list);

prev_node->hole_follows = node->scanned_preceeds_hole; list_add(&node->node_list, &prev_node->node_list);

- return (drm_mm_hole_node_end(node) > mm->scan_hit_start && - node->start < mm->scan_hit_end); + return (drm_mm_hole_node_end(node) > scan->hit_start && + node->start < scan->hit_end); } EXPORT_SYMBOL(drm_mm_scan_remove_block);

@@ -890,7 +906,7 @@ void drm_mm_init(struct drm_mm *mm, u64 start, u64 size) DRM_MM_BUG_ON(start + size <= start);

INIT_LIST_HEAD(&mm->hole_stack); - mm->scanned_blocks = 0; + mm->scan_active = 0;

/* Clever trick to avoid a special case in the free hole tracking. */ INIT_LIST_HEAD(&mm->head_node.node_list); diff --git a/drivers/gpu/drm/etnaviv/etnaviv_mmu.c b/drivers/gpu/drm/etnaviv/etnaviv_mmu.c index 169ac96e8f08..fe1e886dcabb 100644 --- a/drivers/gpu/drm/etnaviv/etnaviv_mmu.c +++ b/drivers/gpu/drm/etnaviv/etnaviv_mmu.c @@ -113,6 +113,7 @@ static int etnaviv_iommu_find_iova(struct etnaviv_iommu *mmu,

while (1) { struct etnaviv_vram_mapping *m, *n; + struct drm_mm_scan scan; struct list_head list; bool found;

@@ -134,7 +135,7 @@ static int etnaviv_iommu_find_iova(struct etnaviv_iommu *mmu, }

/* Try to retire some entries */ - drm_mm_init_scan(&mmu->mm, size, 0, 0); + drm_mm_scan_init(&scan, &mmu->mm, size, 0, 0);

found = 0; INIT_LIST_HEAD(&list); @@ -151,7 +152,7 @@ static int etnaviv_iommu_find_iova(struct etnaviv_iommu *mmu, continue;

list_add(&free->scan_node, &list); - if (drm_mm_scan_add_block(&free->vram_node)) { + if (drm_mm_scan_add_block(&scan, &free->vram_node)) { found = true; break; } @@ -171,7 +172,7 @@ static int etnaviv_iommu_find_iova(struct etnaviv_iommu *mmu, * can leave the block pinned. */ list_for_each_entry_safe(m, n, &list, scan_node) - if (!drm_mm_scan_remove_block(&m->vram_node)) + if (!drm_mm_scan_remove_block(&scan, &m->vram_node)) list_del_init(&m->scan_node);

/* diff --git a/drivers/gpu/drm/i915/i915_gem_evict.c b/drivers/gpu/drm/i915/i915_gem_evict.c index 6457fd0c33a8..6db0d73c0aa7 100644 --- a/drivers/gpu/drm/i915/i915_gem_evict.c +++ b/drivers/gpu/drm/i915/i915_gem_evict.c @@ -51,7 +51,10 @@ static bool ggtt_is_idle(struct drm_i915_private *dev_priv) }

static bool -mark_free(struct i915_vma *vma, unsigned int flags, struct list_head *unwind) +mark_free(struct drm_mm_scan *scan, + struct i915_vma *vma, + unsigned int flags, + struct list_head *unwind) { if (i915_vma_is_pinned(vma)) return false; @@ -63,7 +66,7 @@ mark_free(struct i915_vma *vma, unsigned int flags, struct list_head *unwind) return false;

list_add(&vma->exec_list, unwind); - return drm_mm_scan_add_block(&vma->node); + return drm_mm_scan_add_block(scan, &vma->node); }

/** @@ -97,6 +100,7 @@ i915_gem_evict_something(struct i915_address_space *vm, unsigned flags) { struct drm_i915_private *dev_priv = vm->i915; + struct drm_mm_scan scan; struct list_head eviction_list; struct list_head *phases[] = { &vm->inactive_list, @@ -123,11 +127,12 @@ i915_gem_evict_something(struct i915_address_space *vm, * object on the TAIL. */ if (start != 0 || end != vm->total) { - drm_mm_init_scan_with_range(&vm->mm, min_size, + drm_mm_scan_init_with_range(&scan, &vm->mm, min_size, alignment, cache_level, start, end); } else - drm_mm_init_scan(&vm->mm, min_size, alignment, cache_level); + drm_mm_scan_init(&scan, &vm->mm, min_size, + alignment, cache_level);

/* Retire before we search the active list. Although we have * reasonable accuracy in our retirement lists, we may have @@ -144,13 +149,13 @@ i915_gem_evict_something(struct i915_address_space *vm, phase = phases; do { list_for_each_entry(vma, *phase, vm_link) - if (mark_free(vma, flags, &eviction_list)) + if (mark_free(&scan, vma, flags, &eviction_list)) goto found; } while (*++phase);

/* Nothing found, clean up and bail out! */ list_for_each_entry_safe(vma, next, &eviction_list, exec_list) { - ret = drm_mm_scan_remove_block(&vma->node); + ret = drm_mm_scan_remove_block(&scan, &vma->node); BUG_ON(ret);

INIT_LIST_HEAD(&vma->exec_list); @@ -199,7 +204,7 @@ i915_gem_evict_something(struct i915_address_space *vm, * of any of our objects, thus corrupting the list). */ list_for_each_entry_safe(vma, next, &eviction_list, exec_list) { - if (drm_mm_scan_remove_block(&vma->node)) + if (drm_mm_scan_remove_block(&scan, &vma->node)) __i915_vma_pin(vma); else list_del_init(&vma->exec_list); diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c index e2ed9efb361c..997f2bc93b9b 100644 --- a/drivers/gpu/drm/selftests/test-drm_mm.c +++ b/drivers/gpu/drm/selftests/test-drm_mm.c @@ -1114,11 +1114,11 @@ static int igt_align64(void *ignored) return igt_align_pot(64); }

-static void show_scan(const struct drm_mm *scan) +static void show_scan(const struct drm_mm_scan *scan) { pr_info("scan: hit [%llx, %llx], size=%lld, align=%lld, color=%ld\n", - scan->scan_hit_start, scan->scan_hit_end, - scan->scan_size, scan->scan_alignment, scan->scan_color); + scan->hit_start, scan->hit_end, + scan->size, scan->alignment, scan->color); }

static void show_holes(const struct drm_mm *mm, int count) @@ -1158,7 +1158,7 @@ struct evict_node { struct list_head link; };

-static bool evict_nodes(struct drm_mm *mm, +static bool evict_nodes(struct drm_mm_scan *scan, struct evict_node *nodes, unsigned int *order, unsigned int count, @@ -1170,18 +1170,16 @@ static bool evict_nodes(struct drm_mm *mm, for (i = 0; i < count; i++) { e = &nodes[order ? order[i] : i]; list_add(&e->link, evict_list); - if (drm_mm_scan_add_block(&e->node)) + if (drm_mm_scan_add_block(scan, &e->node)) break; } list_for_each_entry_safe(e, en, evict_list, link) { - if (!drm_mm_scan_remove_block(&e->node)) + if (!drm_mm_scan_remove_block(scan, &e->node)) list_del(&e->link); } if (list_empty(evict_list)) { pr_err("Failed to find eviction: size=%lld [avail=%d], align=%lld (color=%lu)\n", - mm->scan_size, count, - mm->scan_alignment, - mm->scan_color); + scan->size, count, scan->alignment, scan->color); return false; }

@@ -1195,19 +1193,20 @@ static bool evict_nothing(struct drm_mm *mm, unsigned int total_size, struct evict_node *nodes) { + struct drm_mm_scan scan; LIST_HEAD(evict_list); struct evict_node *e; struct drm_mm_node *node; unsigned int n;

- drm_mm_init_scan(mm, 1, 0, 0); + drm_mm_scan_init(&scan, mm, 1, 0, 0); for (n = 0; n < total_size; n++) { e = &nodes[n]; list_add(&e->link, &evict_list); - drm_mm_scan_add_block(&e->node); + drm_mm_scan_add_block(&scan, &e->node); } list_for_each_entry(e, &evict_list, link) - drm_mm_scan_remove_block(&e->node); + drm_mm_scan_remove_block(&scan, &e->node);

for (n = 0; n < total_size; n++) { e = &nodes[n]; @@ -1241,19 +1240,21 @@ static bool evict_everything(struct drm_mm *mm, unsigned int total_size, struct evict_node *nodes) { + struct drm_mm_scan scan; LIST_HEAD(evict_list); struct evict_node *e; unsigned int n; int err;

- drm_mm_init_scan(mm, total_size, 0, 0); + drm_mm_scan_init(&scan, mm, total_size, 0, 0); for (n = 0; n < total_size; n++) { e = &nodes[n]; list_add(&e->link, &evict_list); - drm_mm_scan_add_block(&e->node); + if (drm_mm_scan_add_block(&scan, &e->node)) + break; } list_for_each_entry(e, &evict_list, link) { - if (!drm_mm_scan_remove_block(&e->node)) { + if (!drm_mm_scan_remove_block(&scan, &e->node)) { pr_err("Node %lld not marked for eviction!\n", e->node.start); list_del(&e->link); @@ -1287,15 +1288,16 @@ static int evict_something(struct drm_mm *mm, unsigned int alignment, const struct insert_mode *mode) { + struct drm_mm_scan scan; LIST_HEAD(evict_list); struct evict_node *e; struct drm_mm_node tmp; int err;

- drm_mm_init_scan_with_range(mm, + drm_mm_scan_init_with_range(&scan, mm, size, alignment, 0, range_start, range_end); - if (!evict_nodes(mm, + if (!evict_nodes(&scan, nodes, order, count, &evict_list)) return -EINVAL; @@ -1307,7 +1309,7 @@ static int evict_something(struct drm_mm *mm, if (err) { pr_err("Failed to insert into eviction hole: size=%d, align=%d\n", size, alignment); - show_scan(mm); + show_scan(&scan); show_holes(mm, 3); return err; } @@ -1864,15 +1866,16 @@ static int evict_color(struct drm_mm *mm, unsigned long color, const struct insert_mode *mode) { + struct drm_mm_scan scan; LIST_HEAD(evict_list); struct evict_node *e; struct drm_mm_node tmp; int err;

- drm_mm_init_scan_with_range(mm, + drm_mm_scan_init_with_range(&scan, mm, size, alignment, color, range_start, range_end); - if (!evict_nodes(mm, + if (!evict_nodes(&scan, nodes, order, count, &evict_list)) return -EINVAL; @@ -1884,7 +1887,7 @@ static int evict_color(struct drm_mm *mm, if (err) { pr_err("Failed to insert into eviction hole: size=%d, align=%d, color=%lu, err=%d\n", size, alignment, color, err); - show_scan(mm); + show_scan(&scan); show_holes(mm, 3); return err; } diff --git a/include/drm/drm_mm.h b/include/drm/drm_mm.h index 72e0c0ddf8d0..fcad718c5fb4 100644 --- a/include/drm/drm_mm.h +++ b/include/drm/drm_mm.h @@ -98,20 +98,29 @@ struct drm_mm { /* 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 int scanned_blocks; - unsigned long scan_color; - u64 scan_alignment; - u64 scan_size; - u64 scan_hit_start; - u64 scan_hit_end; - u64 scan_start; - u64 scan_end; - struct drm_mm_node *prev_scanned_node; - void (*color_adjust)(const struct drm_mm_node *node, unsigned long color, u64 *start, u64 *end); + + unsigned long scan_active; +}; + +struct drm_mm_scan { + struct drm_mm *mm; + + u64 size; + u64 alignment; + + u64 range_start; + u64 range_end; + + u64 hit_start; + u64 hit_end; + + struct drm_mm_node *prev_scanned_node; + + unsigned long color; + bool check_range : 1; };

/** @@ -378,18 +387,22 @@ __drm_mm_interval_first(const struct drm_mm *mm, u64 start, u64 last); node__ && node__->start < (end__); \ node__ = list_next_entry(node__, node_list))

-void drm_mm_init_scan(struct drm_mm *mm, +void drm_mm_scan_init(struct drm_mm_scan *scan, + struct drm_mm *mm, u64 size, u64 alignment, unsigned long color); -void drm_mm_init_scan_with_range(struct drm_mm *mm, +void drm_mm_scan_init_with_range(struct drm_mm_scan *scan, + struct drm_mm *mm, u64 size, u64 alignment, unsigned long color, u64 start, u64 end); -bool drm_mm_scan_add_block(struct drm_mm_node *node); -bool drm_mm_scan_remove_block(struct drm_mm_node *node); +bool drm_mm_scan_add_block(struct drm_mm_scan *scan, + struct drm_mm_node *node); +bool drm_mm_scan_remove_block(struct drm_mm_scan *scan, + struct drm_mm_node *node);

void drm_mm_debug_table(const struct drm_mm *mm, const char *prefix); #ifdef CONFIG_DEBUG_FS

Acknowledging that we were building up the hole was more useful to me when reading the code, than knowing the relationship between this node and the previous node.

Signed-off-by: Chris Wilson chris@chris-wilson.co.uk Reviewed-by: Joonas Lahtinen joonas.lahtinen@linux.intel.com --- drivers/gpu/drm/drm_mm.c | 16 ++++++++-------- 1 file changed, 8 insertions(+), 8 deletions(-)

diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c index 21bd2e13738b..459f10ca5714 100644 --- a/drivers/gpu/drm/drm_mm.c +++ b/drivers/gpu/drm/drm_mm.c @@ -811,7 +811,7 @@ bool drm_mm_scan_add_block(struct drm_mm_scan *scan, struct drm_mm_node *node) { struct drm_mm *mm = scan->mm; - struct drm_mm_node *prev_node; + struct drm_mm_node *hole; u64 hole_start, hole_end; u64 adj_start, adj_end;

@@ -821,17 +821,17 @@ bool drm_mm_scan_add_block(struct drm_mm_scan *scan, node->scanned_block = 1; mm->scan_active++;

- prev_node = list_prev_entry(node, node_list); + hole = list_prev_entry(node, node_list);

- node->scanned_preceeds_hole = prev_node->hole_follows; - prev_node->hole_follows = 1; + node->scanned_preceeds_hole = hole->hole_follows; + hole->hole_follows = 1; list_del(&node->node_list); - node->node_list.prev = &prev_node->node_list; + node->node_list.prev = &hole->node_list; node->node_list.next = &scan->prev_scanned_node->node_list; scan->prev_scanned_node = node;

- adj_start = hole_start = drm_mm_hole_node_start(prev_node); - adj_end = hole_end = drm_mm_hole_node_end(prev_node); + adj_start = hole_start = drm_mm_hole_node_start(hole); + adj_end = hole_end = drm_mm_hole_node_end(hole);

if (scan->check_range) { if (adj_start < scan->range_start) @@ -841,7 +841,7 @@ bool drm_mm_scan_add_block(struct drm_mm_scan *scan, }

if (mm->color_adjust) - mm->color_adjust(prev_node, scan->color, &adj_start, &adj_end); + mm->color_adjust(hole, scan->color, &adj_start, &adj_end);

if (check_free_hole(adj_start, adj_end, scan->size, scan->alignment)) {

The range restriction should be applied after the color adjustment, or else we may inadvertently apply the color adjustment to the restricted hole (and not against its neighbours).

Signed-off-by: Chris Wilson chris@chris-wilson.co.uk Reviewed-by: Joonas Lahtinen joonas.lahtinen@linux.intel.com --- drivers/gpu/drm/drm_mm.c | 15 +++++++++------ 1 file changed, 9 insertions(+), 6 deletions(-)

diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c index c68f79149b9a..1b5613bcb35e 100644 --- a/drivers/gpu/drm/drm_mm.c +++ b/drivers/gpu/drm/drm_mm.c @@ -772,6 +772,7 @@ bool drm_mm_scan_add_block(struct drm_mm_scan *scan, struct drm_mm *mm = scan->mm; struct drm_mm_node *hole; u64 hole_start, hole_end; + u64 col_start, col_end; u64 adj_start, adj_end;

DRM_MM_BUG_ON(node->mm != mm); @@ -789,14 +790,16 @@ bool drm_mm_scan_add_block(struct drm_mm_scan *scan, node->node_list.next = &scan->prev_scanned_node->node_list; scan->prev_scanned_node = node;

- hole_start = drm_mm_hole_node_start(hole); - hole_end = drm_mm_hole_node_end(hole); - - adj_start = max(hole_start, scan->range_start); - adj_end = min(hole_end, scan->range_end); + hole_start = __drm_mm_hole_node_start(hole); + hole_end = __drm_mm_hole_node_end(hole);

+ col_start = hole_start; + col_end = hole_end; if (mm->color_adjust) - mm->color_adjust(hole, scan->color, &adj_start, &adj_end); + mm->color_adjust(hole, scan->color, &col_start, &col_end); + + adj_start = max(col_start, scan->range_start); + adj_end = min(col_end, scan->range_end);

if (check_free_hole(adj_start, adj_end, scan->size, scan->alignment)) {

For power-of-two alignments, we can avoid the 64bit divide and do a simple bitwise add instead.

v2: s/alignment_mask/remainder_mask/

Signed-off-by: Chris Wilson chris@chris-wilson.co.uk Reviewed-by: Joonas Lahtinen joonas.lahtinen@linux.intel.com --- drivers/gpu/drm/drm_mm.c | 9 ++++++++- include/drm/drm_mm.h | 1 + 2 files changed, 9 insertions(+), 1 deletion(-)

diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c index 189ab84c5a59..0441d84fba74 100644 --- a/drivers/gpu/drm/drm_mm.c +++ b/drivers/gpu/drm/drm_mm.c @@ -742,8 +742,12 @@ void drm_mm_scan_init_with_range(struct drm_mm_scan *scan,

scan->mm = mm;

+ if (alignment <= 1) + alignment = 0; + scan->color = color; scan->alignment = alignment; + scan->remainder_mask = is_power_of_2(alignment) ? alignment - 1 : 0; scan->size = size; scan->flags = flags;

@@ -811,7 +815,10 @@ bool drm_mm_scan_add_block(struct drm_mm_scan *scan, if (scan->alignment) { u64 rem;

- div64_u64_rem(adj_start, scan->alignment, &rem); + if (likely(scan->remainder_mask)) + rem = adj_start & scan->remainder_mask; + else + div64_u64_rem(adj_start, scan->alignment, &rem); if (rem) { adj_start -= rem; if (scan->flags != DRM_MM_CREATE_TOP) diff --git a/include/drm/drm_mm.h b/include/drm/drm_mm.h index 606336fc229a..d6701d56ea74 100644 --- a/include/drm/drm_mm.h +++ b/include/drm/drm_mm.h @@ -110,6 +110,7 @@ struct drm_mm_scan {

u64 size; u64 alignment; + u64 remainder_mask;

u64 range_start; u64 range_end;

Using mm->color_adjust makes the eviction scanner much tricker since we don't know the actual neighbours of the target hole until after it is created (after scanning is complete). To work out whether we need to evict the neighbours because they impact upon the hole, we have to then check the hole afterwards - requiring an extra step in the user of the eviction scanner when they apply color_adjust.

v2: Massage kerneldoc.

Signed-off-by: Chris Wilson chris@chris-wilson.co.uk Reviewed-by: Joonas Lahtinen joonas.lahtinen@linux.intel.com --- drivers/gpu/drm/drm_mm.c | 76 ++++++++++++++++++++++----------- drivers/gpu/drm/i915/i915_gem_evict.c | 7 +++ drivers/gpu/drm/selftests/test-drm_mm.c | 20 ++++++++- include/drm/drm_mm.h | 1 + 4 files changed, 77 insertions(+), 27 deletions(-)

diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c index ccca8dafb7fc..b59978fe4c6e 100644 --- a/drivers/gpu/drm/drm_mm.c +++ b/drivers/gpu/drm/drm_mm.c @@ -692,19 +692,21 @@ EXPORT_SYMBOL(drm_mm_replace_node); * The DRM range allocator supports this use-case through the scanning * interfaces. First a scan operation needs to be initialized with * drm_mm_scan_init() or drm_mm_scan_init_with_range(). The driver adds - * objects to the roaster (probably by walking an LRU list, but this can be - * freely implemented) until a suitable hole is found or there's no further - * evictable object. + * objects to the roster (probably by walking an LRU list, but this can be + * freely implemented) (using drm_mm_scan_add_block()) until a suitable hole + * is found or there are no further evictable objects. * * The driver must walk through all objects again in exactly the reverse * order to restore the allocator state. Note that while the allocator is used * in the scan mode no other operation is allowed. * - * Finally the driver evicts all objects selected in the scan. Adding and - * removing an object is O(1), and since freeing a node is also O(1) the overall - * complexity is O(scanned_objects). So like the free stack which needs to be - * walked before a scan operation even begins this is linear in the number of - * objects. It doesn't seem to hurt badly. + * Finally the driver evicts all objects selected (drm_mm_scan_remove_block() + * reported true) in the scan, and any overlapping nodes after color adjustment + * (drm_mm_scan_evict_color()). Adding and removing an object is O(1), and + * since freeing a node is also O(1) the overall complexity is + * O(scanned_objects). So like the free stack which needs to be walked before a + * scan operation even begins this is linear in the number of objects. It + * doesn't seem to hurt too badly. */

/** @@ -829,23 +831,8 @@ bool drm_mm_scan_add_block(struct drm_mm_scan *scan, } }

- if (mm->color_adjust) { - /* If allocations need adjusting due to neighbouring colours, - * we do not have enough information to decide if we need - * to evict nodes on either side of [adj_start, adj_end]. - * What almost works is - * hit_start = adj_start + (hole_start - col_start); - * hit_end = adj_start + scan->size + (hole_end - col_end); - * but because the decision is only made on the final hole, - * we may underestimate the required adjustments for an - * interior allocation. - */ - scan->hit_start = hole_start; - scan->hit_end = hole_end; - } else { - scan->hit_start = adj_start; - scan->hit_end = adj_start + scan->size; - } + scan->hit_start = adj_start; + scan->hit_end = adj_start + scan->size;

DRM_MM_BUG_ON(scan->hit_start >= scan->hit_end); DRM_MM_BUG_ON(scan->hit_start < hole_start); @@ -903,6 +890,45 @@ bool drm_mm_scan_remove_block(struct drm_mm_scan *scan, EXPORT_SYMBOL(drm_mm_scan_remove_block);

/** + * drm_mm_scan_color_evict - evict overlapping nodes on either side of hole + * @scan: drm_mm scan with target hole + * + * After completing an eviction scan and removing the selected nodes, we may + * need to remove a few more nodes from either side of the target hole if + * mm.color_adjust is being used. + * + * Returns: + * A node to evict, or NULL if there are no overlapping nodes. + */ +struct drm_mm_node *drm_mm_scan_color_evict(struct drm_mm_scan *scan) +{ + struct drm_mm *mm = scan->mm; + struct drm_mm_node *hole; + u64 hole_start, hole_end; + + DRM_MM_BUG_ON(list_empty(&mm->hole_stack)); + + if (!mm->color_adjust) + return NULL; + + hole = list_first_entry(&mm->hole_stack, typeof(*hole), hole_stack); + hole_start = __drm_mm_hole_node_start(hole); + hole_end = __drm_mm_hole_node_end(hole); + + DRM_MM_BUG_ON(hole_start > scan->hit_start); + DRM_MM_BUG_ON(hole_end < scan->hit_end); + + mm->color_adjust(hole, scan->color, &hole_start, &hole_end); + if (hole_start > scan->hit_start) + return hole; + if (hole_end < scan->hit_end) + return list_next_entry(hole, node_list); + + return NULL; +} +EXPORT_SYMBOL(drm_mm_scan_color_evict); + +/** * drm_mm_init - initialize a drm-mm allocator * @mm: the drm_mm structure to initialize * @start: start of the range managed by @mm diff --git a/drivers/gpu/drm/i915/i915_gem_evict.c b/drivers/gpu/drm/i915/i915_gem_evict.c index 2741498cdf2b..50129ec1caab 100644 --- a/drivers/gpu/drm/i915/i915_gem_evict.c +++ b/drivers/gpu/drm/i915/i915_gem_evict.c @@ -108,6 +108,7 @@ i915_gem_evict_something(struct i915_address_space *vm, NULL, }, **phase; struct i915_vma *vma, *next; + struct drm_mm_node *node; int ret;

lockdep_assert_held(&vm->i915->drm.struct_mutex); @@ -218,6 +219,12 @@ i915_gem_evict_something(struct i915_address_space *vm, if (ret == 0) ret = i915_vma_unbind(vma); } + + while (ret == 0 && (node = drm_mm_scan_color_evict(&scan))) { + vma = container_of(node, struct i915_vma, node); + ret = i915_vma_unbind(vma); + } + return ret; }

diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c index 1bbfc24342c5..f609e4f1eeaf 100644 --- a/drivers/gpu/drm/selftests/test-drm_mm.c +++ b/drivers/gpu/drm/selftests/test-drm_mm.c @@ -1162,6 +1162,7 @@ static bool evict_nodes(struct drm_mm_scan *scan, struct evict_node *nodes, unsigned int *order, unsigned int count, + bool use_color, struct list_head *evict_list) { struct evict_node *e, *en; @@ -1186,6 +1187,21 @@ static bool evict_nodes(struct drm_mm_scan *scan, list_for_each_entry(e, evict_list, link) drm_mm_remove_node(&e->node);

+ if (use_color) { + struct drm_mm_node *node; + + while ((node = drm_mm_scan_color_evict(scan))) { + e = container_of(node, typeof(*e), node); + drm_mm_remove_node(&e->node); + list_add(&e->link, evict_list); + } + } else { + if (drm_mm_scan_color_evict(scan)) { + pr_err("drm_mm_scan_color_evict unexpectedly reported overlapping nodes!\n"); + return false; + } + } + return true; }

@@ -1299,7 +1315,7 @@ static int evict_something(struct drm_mm *mm, range_start, range_end, mode->create_flags); if (!evict_nodes(&scan, - nodes, order, count, + nodes, order, count, false, &evict_list)) return -EINVAL;

@@ -1878,7 +1894,7 @@ static int evict_color(struct drm_mm *mm, range_start, range_end, mode->create_flags); if (!evict_nodes(&scan, - nodes, order, count, + nodes, order, count, true, &evict_list)) return -EINVAL;

diff --git a/include/drm/drm_mm.h b/include/drm/drm_mm.h index ff120b7d0f85..aed93cbc4bde 100644 --- a/include/drm/drm_mm.h +++ b/include/drm/drm_mm.h @@ -422,6 +422,7 @@ bool drm_mm_scan_add_block(struct drm_mm_scan *scan, struct drm_mm_node *node); bool drm_mm_scan_remove_block(struct drm_mm_scan *scan, struct drm_mm_node *node); +struct drm_mm_node *drm_mm_scan_color_evict(struct drm_mm_scan *scan);

void drm_mm_debug_table(const struct drm_mm *mm, const char *prefix); #ifdef CONFIG_DEBUG_FS

mm->color_adjust() compares the hole with its neighbouring nodes. They only abutt before we restrict the hole, so we have to apply color_adjust before we apply the range restriction.

Signed-off-by: Chris Wilson chris@chris-wilson.co.uk Reviewed-by: Joonas Lahtinen joonas.lahtinen@linux.intel.com --- drivers/gpu/drm/drm_mm.c | 16 ++++++---------- 1 file changed, 6 insertions(+), 10 deletions(-)

diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c index c0024719f32b..e279ac7c7aaf 100644 --- a/drivers/gpu/drm/drm_mm.c +++ b/drivers/gpu/drm/drm_mm.c @@ -410,14 +410,12 @@ static void drm_mm_insert_helper_range(struct drm_mm_node *hole_node,

DRM_MM_BUG_ON(!drm_mm_hole_follows(hole_node) || node->allocated);

- if (adj_start < start) - adj_start = start; - if (adj_end > end) - adj_end = end; - if (mm->color_adjust) mm->color_adjust(hole_node, color, &adj_start, &adj_end);

+ adj_start = max(adj_start, start); + adj_end = min(adj_end, end); + if (flags & DRM_MM_CREATE_TOP) adj_start = adj_end - size;

@@ -625,17 +623,15 @@ static struct drm_mm_node *drm_mm_search_free_in_range_generic(const struct drm_ flags & DRM_MM_SEARCH_BELOW) { u64 hole_size = adj_end - adj_start;

- if (adj_start < start) - adj_start = start; - if (adj_end > end) - adj_end = end; - if (mm->color_adjust) { mm->color_adjust(entry, color, &adj_start, &adj_end); if (adj_end <= adj_start) continue; }

+ adj_start = max(adj_start, start); + adj_end = min(adj_end, end); + if (!check_free_hole(adj_start, adj_end, size, alignment)) continue;

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!

Signed-off-by: Chris Wilson chris@chris-wilson.co.uk Reviewed-by: Joonas Lahtinen joonas.lahtinen@linux.intel.com --- drivers/gpu/drm/amd/amdgpu/amdgpu_gtt_mgr.c | 16 +- drivers/gpu/drm/amd/amdgpu/amdgpu_vram_mgr.c | 20 +- drivers/gpu/drm/armada/armada_gem.c | 4 +- drivers/gpu/drm/drm_mm.c | 511 +++++++++++++++------------ drivers/gpu/drm/drm_vma_manager.c | 3 +- drivers/gpu/drm/etnaviv/etnaviv_mmu.c | 8 +- drivers/gpu/drm/i915/i915_gem.c | 10 +- drivers/gpu/drm/i915/i915_gem_evict.c | 9 +- drivers/gpu/drm/i915/i915_gem_execbuffer.c | 5 +- drivers/gpu/drm/i915/i915_gem_gtt.c | 39 +- drivers/gpu/drm/i915/i915_gem_stolen.c | 6 +- drivers/gpu/drm/msm/msm_gem.c | 3 +- drivers/gpu/drm/msm/msm_gem_vma.c | 3 +- drivers/gpu/drm/selftests/test-drm_mm.c | 58 ++- drivers/gpu/drm/sis/sis_mm.c | 6 +- drivers/gpu/drm/tegra/gem.c | 4 +- drivers/gpu/drm/ttm/ttm_bo_manager.c | 18 +- drivers/gpu/drm/vc4/vc4_crtc.c | 2 +- drivers/gpu/drm/vc4/vc4_hvs.c | 3 +- drivers/gpu/drm/vc4/vc4_plane.c | 6 +- drivers/gpu/drm/via/via_mm.c | 4 +- drivers/gpu/drm/vmwgfx/vmwgfx_cmdbuf.c | 10 +- include/drm/drm_mm.h | 135 +++---- 23 files changed, 434 insertions(+), 449 deletions(-)

diff --git a/drivers/gpu/drm/amd/amdgpu/amdgpu_gtt_mgr.c b/drivers/gpu/drm/amd/amdgpu/amdgpu_gtt_mgr.c index 00f46b0e076d..d841fcb2e709 100644 --- a/drivers/gpu/drm/amd/amdgpu/amdgpu_gtt_mgr.c +++ b/drivers/gpu/drm/amd/amdgpu/amdgpu_gtt_mgr.c @@ -97,8 +97,7 @@ int amdgpu_gtt_mgr_alloc(struct ttm_mem_type_manager *man, { struct amdgpu_gtt_mgr *mgr = man->priv; struct drm_mm_node *node = mem->mm_node; - enum drm_mm_search_flags sflags = DRM_MM_SEARCH_BEST; - enum drm_mm_allocator_flags aflags = DRM_MM_CREATE_DEFAULT; + enum drm_mm_insert_mode mode; unsigned long fpfn, lpfn; int r;

@@ -115,15 +114,14 @@ int amdgpu_gtt_mgr_alloc(struct ttm_mem_type_manager *man, else lpfn = man->size;

- if (place && place->flags & TTM_PL_FLAG_TOPDOWN) { - sflags = DRM_MM_SEARCH_BELOW; - aflags = DRM_MM_CREATE_TOP; - } + mode = DRM_MM_INSERT_BEST; + if (place && place->mode & TTM_PL_FLAG_TOPDOWN) + mode = DRM_MM_INSERT_HIGH;

spin_lock(&mgr->lock); - r = drm_mm_insert_node_in_range_generic(&mgr->mm, node, mem->num_pages, - mem->page_alignment, 0, - fpfn, lpfn, sflags, aflags); + r = drm_mm_insert_node_in_range(&mgr->mm, node, + mem->num_pages, mem->page_alignment, 0, + fpfn, lpfn, mode); spin_unlock(&mgr->lock);

if (!r) { diff --git a/drivers/gpu/drm/amd/amdgpu/amdgpu_vram_mgr.c b/drivers/gpu/drm/amd/amdgpu/amdgpu_vram_mgr.c index d710226a0fff..5f106ad815ce 100644 --- a/drivers/gpu/drm/amd/amdgpu/amdgpu_vram_mgr.c +++ b/drivers/gpu/drm/amd/amdgpu/amdgpu_vram_mgr.c @@ -97,8 +97,7 @@ static int amdgpu_vram_mgr_new(struct ttm_mem_type_manager *man, struct amdgpu_vram_mgr *mgr = man->priv; struct drm_mm *mm = &mgr->mm; struct drm_mm_node *nodes; - enum drm_mm_search_flags sflags = DRM_MM_SEARCH_DEFAULT; - enum drm_mm_allocator_flags aflags = DRM_MM_CREATE_DEFAULT; + enum drm_mm_insert_mode mode; unsigned long lpfn, num_nodes, pages_per_node, pages_left; unsigned i; int r; @@ -121,10 +120,9 @@ static int amdgpu_vram_mgr_new(struct ttm_mem_type_manager *man, if (!nodes) return -ENOMEM;

- if (place->flags & TTM_PL_FLAG_TOPDOWN) { - sflags = DRM_MM_SEARCH_BELOW; - aflags = DRM_MM_CREATE_TOP; - } + mode = DRM_MM_INSERT_BEST; + if (place->flags & TTM_PL_FLAG_TOPDOWN) + mode = DRM_MM_INSERT_HIGH;

pages_left = mem->num_pages;

@@ -135,13 +133,11 @@ static int amdgpu_vram_mgr_new(struct ttm_mem_type_manager *man,

if (pages == pages_per_node) alignment = pages_per_node; - else - sflags |= DRM_MM_SEARCH_BEST;

- r = drm_mm_insert_node_in_range_generic(mm, &nodes[i], pages, - alignment, 0, - place->fpfn, lpfn, - sflags, aflags); + r = drm_mm_insert_node_in_range(mm, &nodes[i], + pages, alignment, 0, + place->fpfn, lpfn, + mode); if (unlikely(r)) goto error;

diff --git a/drivers/gpu/drm/armada/armada_gem.c b/drivers/gpu/drm/armada/armada_gem.c index 768087ddb046..65b029bc84b5 100644 --- a/drivers/gpu/drm/armada/armada_gem.c +++ b/drivers/gpu/drm/armada/armada_gem.c @@ -149,8 +149,8 @@ armada_gem_linear_back(struct drm_device *dev, struct armada_gem_object *obj) return -ENOSPC;

mutex_lock(&priv->linear_lock); - ret = drm_mm_insert_node(&priv->linear, node, size, align, - DRM_MM_SEARCH_DEFAULT); + ret = drm_mm_insert_node_generic(&priv->linear, node, + size, align, 0, 0); mutex_unlock(&priv->linear_lock); if (ret) { kfree(node); diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c index 58a7e3bbe130..960c9cd7dc23 100644 --- a/drivers/gpu/drm/drm_mm.c +++ b/drivers/gpu/drm/drm_mm.c @@ -92,14 +92,6 @@ * some basic allocator dumpers for debugging. */

-static struct drm_mm_node *drm_mm_search_free_in_range_generic(const struct drm_mm *mm, - u64 size, - u64 alignment, - unsigned long color, - u64 start, - u64 end, - enum drm_mm_search_flags flags); - #ifdef CONFIG_DRM_DEBUG_MM #include <linux/stackdepot.h>

@@ -221,69 +213,47 @@ static void drm_mm_interval_tree_add_node(struct drm_mm_node *hole_node, &drm_mm_interval_tree_augment); }

-static void drm_mm_insert_helper(struct drm_mm_node *hole_node, - struct drm_mm_node *node, - u64 size, u64 alignment, - unsigned long color, - u64 range_start, u64 range_end, - enum drm_mm_allocator_flags flags) +#define RB_INSERT(root, member, expr) do { \ + struct rb_node **link = &root.rb_node, *rb = NULL; \ + u64 x = expr(node); \ + while (*link) { \ + rb = *link; \ + if (x < expr(rb_entry(rb, struct drm_mm_node, member))) \ + link = &rb->rb_left; \ + else \ + link = &rb->rb_right; \ + } \ + rb_link_node(&node->member, rb, link); \ + rb_insert_color(&node->member, &root); \ +} while (0) + +#define HOLE_SIZE(NODE) ((NODE)->hole_size) +#define HOLE_ADDR(NODE) (__drm_mm_hole_node_start(NODE)) + +static void add_hole(struct drm_mm_node *node) { - struct drm_mm *mm = hole_node->mm; - u64 hole_start = drm_mm_hole_node_start(hole_node); - u64 hole_end = drm_mm_hole_node_end(hole_node); - u64 adj_start = hole_start; - u64 adj_end = hole_end; - - DRM_MM_BUG_ON(!drm_mm_hole_follows(hole_node) || node->allocated); - - if (mm->color_adjust) - mm->color_adjust(hole_node, color, &adj_start, &adj_end); - - adj_start = max(adj_start, range_start); - adj_end = min(adj_end, range_end); - - if (flags & DRM_MM_CREATE_TOP) - adj_start = adj_end - size; - - if (alignment) { - u64 rem; - - div64_u64_rem(adj_start, alignment, &rem); - if (rem) { - if (flags & DRM_MM_CREATE_TOP) - adj_start -= rem; - else - adj_start += alignment - rem; - } - } - - if (adj_start == hole_start) { - hole_node->hole_follows = 0; - list_del(&hole_node->hole_stack); - } + struct drm_mm *mm = node->mm;

- node->start = adj_start; - node->size = size; - node->mm = mm; - node->color = color; - node->allocated = 1; + node->hole_size = + __drm_mm_hole_node_end(node) - __drm_mm_hole_node_start(node); + DRM_MM_BUG_ON(!drm_mm_hole_follows(node));

- list_add(&node->node_list, &hole_node->node_list); + RB_INSERT(mm->holes_size, rb_hole_size, HOLE_SIZE); + RB_INSERT(mm->holes_addr, rb_hole_addr, HOLE_ADDR);

- drm_mm_interval_tree_add_node(hole_node, node); + list_add(&node->hole_stack, &mm->hole_stack); +}

- DRM_MM_BUG_ON(node->start < range_start); - DRM_MM_BUG_ON(node->start < adj_start); - DRM_MM_BUG_ON(node->start + node->size > adj_end); - DRM_MM_BUG_ON(node->start + node->size > range_end); +static void rm_hole(struct drm_mm_node *node) +{ + DRM_MM_BUG_ON(!drm_mm_hole_follows(node));

- node->hole_follows = 0; - if (__drm_mm_hole_node_start(node) < hole_end) { - list_add(&node->hole_stack, &mm->hole_stack); - node->hole_follows = 1; - } + list_del(&node->hole_stack); + rb_erase(&node->rb_hole_size, &node->mm->holes_size); + rb_erase(&node->rb_hole_addr, &node->mm->holes_addr); + node->hole_size = 0;

- save_stack(node); + DRM_MM_BUG_ON(drm_mm_hole_follows(node)); }

/** @@ -313,7 +283,7 @@ int drm_mm_reserve_node(struct drm_mm *mm, struct drm_mm_node *node)

/* Find the relevant hole to add our node to */ hole = drm_mm_interval_tree_iter_first(&mm->interval_tree, - node->start, ~(u64)0); + node->start, U64_MAX); if (hole) { if (hole->start < end) return -ENOSPC; @@ -321,12 +291,12 @@ int drm_mm_reserve_node(struct drm_mm *mm, struct drm_mm_node *node) hole = list_entry(drm_mm_nodes(mm), typeof(*hole), node_list); }

- hole = list_last_entry(&hole->node_list, typeof(*hole), node_list); + hole = list_prev_entry(hole, node_list); if (!drm_mm_hole_follows(hole)) return -ENOSPC;

adj_start = hole_start = __drm_mm_hole_node_start(hole); - adj_end = hole_end = __drm_mm_hole_node_end(hole); + adj_end = hole_end = hole_start + hole->hole_size;

if (mm->color_adjust) mm->color_adjust(hole, node->color, &adj_start, &adj_end); @@ -335,31 +305,128 @@ int drm_mm_reserve_node(struct drm_mm *mm, struct drm_mm_node *node) return -ENOSPC;

node->mm = mm; - node->allocated = 1;

list_add(&node->node_list, &hole->node_list); - drm_mm_interval_tree_add_node(hole, node); + node->allocated = true; + node->hole_size = 0; + + rm_hole(hole); + if (node->start > hole_start) + add_hole(hole); + if (end < hole_end) + add_hole(node); + + save_stack(node); + return 0; +} +EXPORT_SYMBOL(drm_mm_reserve_node); + +static inline struct drm_mm_node *rb_hole_size_to_node(struct rb_node *rb) +{ + return rb_entry_safe(rb, struct drm_mm_node, rb_hole_size); +} + +static inline struct drm_mm_node *rb_hole_addr_to_node(struct rb_node *rb) +{ + return rb_entry_safe(rb, struct drm_mm_node, rb_hole_addr); +}

- if (node->start == hole_start) { - hole->hole_follows = 0; - list_del(&hole->hole_stack); +static inline u64 rb_hole_size(struct rb_node *rb) +{ + return rb_entry(rb, struct drm_mm_node, rb_hole_size)->hole_size; +} + +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; + + while (*link) { + struct rb_node *rb = *link; + if (size <= rb_hole_size(rb)) { + link = &rb->rb_left; + best = rb; + } else { + link = &rb->rb_right; + } }

- node->hole_follows = 0; - if (end != hole_end) { - list_add(&node->hole_stack, &mm->hole_stack); - node->hole_follows = 1; + return rb_hole_size_to_node(best); +} + +static struct drm_mm_node *find_hole(struct drm_mm *mm, u64 addr) +{ + struct drm_mm_node *node = NULL; + struct rb_node **link = &mm->holes_addr.rb_node; + + while (*link) { + u64 hole_start; + + node = rb_hole_addr_to_node(*link); + hole_start = __drm_mm_hole_node_start(node); + + if (addr < hole_start) + link = &node->rb_hole_addr.rb_left; + else if (addr > hole_start + node->hole_size) + link = &node->rb_hole_addr.rb_right; + else + break; }

- save_stack(node); + return node; +}

- return 0; +static struct drm_mm_node * +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: + return best_hole(mm, size); + + case DRM_MM_INSERT_LOW: + return find_hole(mm, start); + + case DRM_MM_INSERT_HIGH: + return find_hole(mm, end); + + case DRM_MM_INSERT_EVICT: + return list_first_entry_or_null(&mm->hole_stack, + struct drm_mm_node, + hole_stack); + } +} + +static struct drm_mm_node * +next_hole(struct drm_mm *mm, + struct drm_mm_node *node, + enum drm_mm_insert_mode mode) +{ + switch (mode) { + default: + case DRM_MM_INSERT_BEST: + return rb_hole_size_to_node(rb_next(&node->rb_hole_size)); + + case DRM_MM_INSERT_LOW: + return rb_hole_addr_to_node(rb_next(&node->rb_hole_addr)); + + case DRM_MM_INSERT_HIGH: + return rb_hole_addr_to_node(rb_prev(&node->rb_hole_addr)); + + case DRM_MM_INSERT_EVICT: + node = list_next_entry(node, hole_stack); + return &node->hole_stack == &mm->hole_stack ? NULL : node; + } } -EXPORT_SYMBOL(drm_mm_reserve_node);

/** - * drm_mm_insert_node_in_range_generic - ranged search for space and insert @node + * drm_mm_insert_node_in_range - ranged search for space and insert @node * @mm: drm_mm to allocate from * @node: preallocate node to insert * @size: size of the allocation @@ -367,38 +434,104 @@ EXPORT_SYMBOL(drm_mm_reserve_node); * @color: opaque tag value to use for this node * @start: start of the allowed range for this node * @end: end of the allowed range for this node - * @sflags: flags to fine-tune the allocation search - * @aflags: flags to fine-tune the allocation behavior + * @mode: fine-tune the allocation search and placement * * The preallocated node must be cleared to 0. * * Returns: * 0 on success, -ENOSPC if there's no suitable hole. */ -int drm_mm_insert_node_in_range_generic(struct drm_mm *mm, struct drm_mm_node *node, - u64 size, u64 alignment, - unsigned long color, - u64 start, u64 end, - enum drm_mm_search_flags sflags, - enum drm_mm_allocator_flags aflags) +int drm_mm_insert_node_in_range(struct drm_mm * const mm, + struct drm_mm_node * const node, + u64 size, u64 alignment, + unsigned long color, + u64 range_start, u64 range_end, + enum drm_mm_insert_mode mode) { - struct drm_mm_node *hole_node; + struct drm_mm_node *hole; + u64 remainder_mask;

- if (WARN_ON(size == 0)) - return -EINVAL; + DRM_MM_BUG_ON(range_start >= range_end);

- hole_node = drm_mm_search_free_in_range_generic(mm, - size, alignment, color, - start, end, sflags); - if (!hole_node) + if (unlikely(size == 0 || range_end - range_start < size)) return -ENOSPC;

- drm_mm_insert_helper(hole_node, node, - size, alignment, color, - start, end, aflags); - return 0; + if (alignment <= 1) + alignment = 0; + + 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)) { + u64 hole_start = __drm_mm_hole_node_start(hole); + u64 hole_end = hole_start + hole->hole_size; + u64 adj_start, adj_end; + u64 col_start, col_end; + + if (mode == DRM_MM_INSERT_LOW && hole_start >= range_end) + break; + + if (mode == DRM_MM_INSERT_HIGH && hole_end <= range_start) + break; + + col_start = hole_start; + col_end = hole_end; + if (mm->color_adjust) + mm->color_adjust(hole, color, &col_start, &col_end); + + adj_start = max(col_start, range_start); + adj_end = min(col_end, range_end); + + if (adj_end <= adj_start || adj_end - adj_start < size) + continue; + + if (mode == DRM_MM_INSERT_HIGH) + adj_start = adj_end - size; + + if (alignment) { + u64 rem; + + if (likely(remainder_mask)) + rem = adj_start & remainder_mask; + else + div64_u64_rem(adj_start, alignment, &rem); + if (rem) { + adj_start -= rem; + if (mode != DRM_MM_INSERT_HIGH) + adj_start += alignment; + + if (adj_start < max(col_start, range_start) || + min(col_end, range_end) - adj_start < size) + continue; + + if (adj_end <= adj_start || + adj_end - adj_start < size) + continue; + } + } + + node->mm = mm; + node->size = size; + node->start = adj_start; + node->color = color; + node->hole_size = 0; + + list_add(&node->node_list, &hole->node_list); + drm_mm_interval_tree_add_node(hole, node); + node->allocated = true; + + rm_hole(hole); + if (adj_start > hole_start) + add_hole(hole); + if (adj_start + size < hole_end) + add_hole(node); + + save_stack(node); + return 0; + } + + return -ENOSPC; } -EXPORT_SYMBOL(drm_mm_insert_node_in_range_generic); +EXPORT_SYMBOL(drm_mm_insert_node_in_range);

/** * drm_mm_remove_node - Remove a memory node from the allocator. @@ -416,92 +549,20 @@ void drm_mm_remove_node(struct drm_mm_node *node) DRM_MM_BUG_ON(!node->allocated); DRM_MM_BUG_ON(node->scanned_block);

- prev_node = - list_entry(node->node_list.prev, struct drm_mm_node, node_list); - - if (drm_mm_hole_follows(node)) { - DRM_MM_BUG_ON(__drm_mm_hole_node_start(node) == - __drm_mm_hole_node_end(node)); - list_del(&node->hole_stack); - } else { - DRM_MM_BUG_ON(__drm_mm_hole_node_start(node) != - __drm_mm_hole_node_end(node)); - } + prev_node = list_prev_entry(node, node_list);

- if (!drm_mm_hole_follows(prev_node)) { - prev_node->hole_follows = 1; - list_add(&prev_node->hole_stack, &mm->hole_stack); - } else - list_move(&prev_node->hole_stack, &mm->hole_stack); + if (drm_mm_hole_follows(node)) + rm_hole(node);

drm_mm_interval_tree_remove(node, &mm->interval_tree); list_del(&node->node_list); - node->allocated = 0; -} -EXPORT_SYMBOL(drm_mm_remove_node); - -static int check_free_hole(u64 start, u64 end, u64 size, u64 alignment) -{ - if (end - start < size) - return 0; - - if (alignment) { - u64 rem; - - div64_u64_rem(start, alignment, &rem); - if (rem) - start += alignment - rem; - } - - return end >= start + size; -} - -static struct drm_mm_node *drm_mm_search_free_in_range_generic(const struct drm_mm *mm, - u64 size, - u64 alignment, - unsigned long color, - u64 start, - u64 end, - enum drm_mm_search_flags flags) -{ - struct drm_mm_node *entry; - struct drm_mm_node *best; - u64 adj_start; - u64 adj_end; - u64 best_size; - - DRM_MM_BUG_ON(mm->scan_active); - - best = NULL; - best_size = ~0UL; - - __drm_mm_for_each_hole(entry, mm, adj_start, adj_end, - flags & DRM_MM_SEARCH_BELOW) { - u64 hole_size = adj_end - adj_start; - - if (mm->color_adjust) { - mm->color_adjust(entry, color, &adj_start, &adj_end); - if (adj_end <= adj_start) - continue; - } - - adj_start = max(adj_start, start); - adj_end = min(adj_end, end); - - if (!check_free_hole(adj_start, adj_end, size, alignment)) - continue; - - if (!(flags & DRM_MM_SEARCH_BEST)) - return entry; - - if (hole_size < best_size) { - best = entry; - best_size = hole_size; - } - } + node->allocated = false;

- return best; + if (drm_mm_hole_follows(prev_node)) + rm_hole(prev_node); + add_hole(prev_node); } +EXPORT_SYMBOL(drm_mm_remove_node);

/** * drm_mm_replace_node - move an allocation from @old to @new @@ -516,18 +577,23 @@ void drm_mm_replace_node(struct drm_mm_node *old, struct drm_mm_node *new) { DRM_MM_BUG_ON(!old->allocated);

+ *new = *old; + list_replace(&old->node_list, &new->node_list); - list_replace(&old->hole_stack, &new->hole_stack); rb_replace_node(&old->rb, &new->rb, &old->mm->interval_tree); - new->hole_follows = old->hole_follows; - new->mm = old->mm; - new->start = old->start; - new->size = old->size; - new->color = old->color; - new->__subtree_last = old->__subtree_last; - - old->allocated = 0; - new->allocated = 1; + + 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, + &old->mm->holes_size); + rb_replace_node(&old->rb_hole_addr, + &new->rb_hole_addr, + &old->mm->holes_addr); + } + + old->allocated = false; + new->allocated = true; } EXPORT_SYMBOL(drm_mm_replace_node);

@@ -570,7 +636,7 @@ EXPORT_SYMBOL(drm_mm_replace_node); * @color: opaque tag value to use for the allocation * @start: start of the allowed range for the allocation * @end: end of the allowed range for the allocation - * @flags: flags to specify how the allocation will be performed afterwards + * @mode: fine-tune the allocation search and placement * * This simply sets up the scanning routines with the parameters for the desired * hole. @@ -586,7 +652,7 @@ void drm_mm_scan_init_with_range(struct drm_mm_scan *scan, unsigned long color, u64 start, u64 end, - unsigned int flags) + enum drm_mm_insert_mode mode) { DRM_MM_BUG_ON(start >= end); DRM_MM_BUG_ON(!size || size > end - start); @@ -601,7 +667,7 @@ void drm_mm_scan_init_with_range(struct drm_mm_scan *scan, scan->alignment = alignment; scan->remainder_mask = is_power_of_2(alignment) ? alignment - 1 : 0; scan->size = size; - scan->flags = flags; + scan->mode = mode;

DRM_MM_BUG_ON(end <= start); scan->range_start = start; @@ -659,7 +725,7 @@ bool drm_mm_scan_add_block(struct drm_mm_scan *scan, if (adj_end <= adj_start || adj_end - adj_start < scan->size) return false;

- if (scan->flags == DRM_MM_CREATE_TOP) + if (scan->mode == DRM_MM_INSERT_HIGH) adj_start = adj_end - scan->size;

if (scan->alignment) { @@ -671,7 +737,7 @@ bool drm_mm_scan_add_block(struct drm_mm_scan *scan, div64_u64_rem(adj_start, scan->alignment, &rem); if (rem) { adj_start -= rem; - if (scan->flags != DRM_MM_CREATE_TOP) + if (scan->mode != DRM_MM_INSERT_HIGH) adj_start += scan->alignment; if (adj_start < max(col_start, scan->range_start) || min(col_end, scan->range_end) - adj_start < scan->size) @@ -765,7 +831,7 @@ struct drm_mm_node *drm_mm_scan_color_evict(struct drm_mm_scan *scan)

hole = list_first_entry(&mm->hole_stack, typeof(*hole), hole_stack); hole_start = __drm_mm_hole_node_start(hole); - hole_end = __drm_mm_hole_node_end(hole); + hole_end = hole_start + hole->hole_size;

DRM_MM_BUG_ON(hole_start > scan->hit_start); DRM_MM_BUG_ON(hole_end < scan->hit_end); @@ -792,21 +858,22 @@ void drm_mm_init(struct drm_mm *mm, u64 start, u64 size) { DRM_MM_BUG_ON(start + size <= start);

+ mm->color_adjust = NULL; + INIT_LIST_HEAD(&mm->hole_stack); - mm->scan_active = 0; + mm->interval_tree = RB_ROOT; + mm->holes_size = RB_ROOT; + mm->holes_addr = RB_ROOT;

/* Clever trick to avoid a special case in the free hole tracking. */ INIT_LIST_HEAD(&mm->head_node.node_list); - mm->head_node.allocated = 0; - mm->head_node.hole_follows = 1; + mm->head_node.allocated = false; mm->head_node.mm = mm; mm->head_node.start = start + size; - mm->head_node.size = start - mm->head_node.start; - list_add_tail(&mm->head_node.hole_stack, &mm->hole_stack); - - mm->interval_tree = RB_ROOT; + mm->head_node.size = -size; + add_hole(&mm->head_node);

- mm->color_adjust = NULL; + mm->scan_active = 0; } EXPORT_SYMBOL(drm_mm_init);

@@ -828,18 +895,16 @@ EXPORT_SYMBOL(drm_mm_takedown); static u64 drm_mm_debug_hole(const struct drm_mm_node *entry, const char *prefix) { - u64 hole_start, hole_end, hole_size; - - if (entry->hole_follows) { - hole_start = drm_mm_hole_node_start(entry); - hole_end = drm_mm_hole_node_end(entry); - hole_size = hole_end - hole_start; - pr_debug("%s %#llx-%#llx: %llu: free\n", prefix, hole_start, - hole_end, hole_size); - return hole_size; + u64 start, size; + + size = entry->hole_size; + if (size) { + start = drm_mm_hole_node_start(entry); + pr_debug("%s %#llx-%#llx: %llu: free\n", + prefix, start, start + size, size); }

- return 0; + return size; }

/** @@ -870,18 +935,16 @@ EXPORT_SYMBOL(drm_mm_debug_table); #if defined(CONFIG_DEBUG_FS) static u64 drm_mm_dump_hole(struct seq_file *m, const struct drm_mm_node *entry) { - u64 hole_start, hole_end, hole_size; - - if (entry->hole_follows) { - hole_start = drm_mm_hole_node_start(entry); - hole_end = drm_mm_hole_node_end(entry); - hole_size = hole_end - hole_start; - seq_printf(m, "%#018llx-%#018llx: %llu: free\n", hole_start, - hole_end, hole_size); - return hole_size; + u64 start, size; + + size = entry->hole_size; + if (size) { + start = drm_mm_hole_node_start(entry); + seq_printf(m, "%#018llx-%#018llx: %llu: free\n", + start, start + size, size); }

- return 0; + return size; }

/** diff --git a/drivers/gpu/drm/drm_vma_manager.c b/drivers/gpu/drm/drm_vma_manager.c index 20cc33d1bfc1..d9100b565198 100644 --- a/drivers/gpu/drm/drm_vma_manager.c +++ b/drivers/gpu/drm/drm_vma_manager.c @@ -212,8 +212,7 @@ int drm_vma_offset_add(struct drm_vma_offset_manager *mgr, goto out_unlock; }

- ret = drm_mm_insert_node(&mgr->vm_addr_space_mm, &node->vm_node, - pages, 0, DRM_MM_SEARCH_DEFAULT); + ret = drm_mm_insert_node(&mgr->vm_addr_space_mm, &node->vm_node, pages); if (ret) goto out_unlock;

diff --git a/drivers/gpu/drm/etnaviv/etnaviv_mmu.c b/drivers/gpu/drm/etnaviv/etnaviv_mmu.c index 2dae3169ce48..69ab98c143dc 100644 --- a/drivers/gpu/drm/etnaviv/etnaviv_mmu.c +++ b/drivers/gpu/drm/etnaviv/etnaviv_mmu.c @@ -107,6 +107,7 @@ static int etnaviv_iommu_find_iova(struct etnaviv_iommu *mmu, struct drm_mm_node *node, size_t size) { struct etnaviv_vram_mapping *free = NULL; + enum drm_mm_insert_mode mode = DRM_MM_INSERT_LOW; int ret;

lockdep_assert_held(&mmu->lock); @@ -118,8 +119,9 @@ static int etnaviv_iommu_find_iova(struct etnaviv_iommu *mmu, bool found;

ret = drm_mm_insert_node_in_range(&mmu->mm, node, - size, 0, mmu->last_iova, ~0UL, - DRM_MM_SEARCH_DEFAULT); + size, 0, 0, + mmu->last_iova, U64_MAX, + mode);

if (ret != -ENOSPC) break; @@ -187,6 +189,8 @@ static int etnaviv_iommu_find_iova(struct etnaviv_iommu *mmu, list_del_init(&m->scan_node); }

+ mode = DRM_MM_INSERT_EVICT; + /* * We removed enough mappings so that the new allocation will * succeed. Ensure that the MMU will be flushed before the diff --git a/drivers/gpu/drm/i915/i915_gem.c b/drivers/gpu/drm/i915/i915_gem.c index 5275f6248ce3..cc4e0224968f 100644 --- a/drivers/gpu/drm/i915/i915_gem.c +++ b/drivers/gpu/drm/i915/i915_gem.c @@ -69,12 +69,10 @@ insert_mappable_node(struct i915_ggtt *ggtt, struct drm_mm_node *node, u32 size) { memset(node, 0, sizeof(*node)); - return drm_mm_insert_node_in_range_generic(&ggtt->base.mm, node, - size, 0, - I915_COLOR_UNEVICTABLE, - 0, ggtt->mappable_end, - DRM_MM_SEARCH_DEFAULT, - DRM_MM_CREATE_DEFAULT); + return drm_mm_insert_node_in_range(&ggtt->base.mm, node, + size, 0, I915_COLOR_UNEVICTABLE, + 0, ggtt->mappable_end, + DRM_MM_INSERT_LOW); }

static void diff --git a/drivers/gpu/drm/i915/i915_gem_evict.c b/drivers/gpu/drm/i915/i915_gem_evict.c index 50129ec1caab..f92f63e8749a 100644 --- a/drivers/gpu/drm/i915/i915_gem_evict.c +++ b/drivers/gpu/drm/i915/i915_gem_evict.c @@ -109,6 +109,7 @@ i915_gem_evict_something(struct i915_address_space *vm, }, **phase; struct i915_vma *vma, *next; struct drm_mm_node *node; + enum drm_mm_insert_mode mode; int ret;

lockdep_assert_held(&vm->i915->drm.struct_mutex); @@ -127,10 +128,14 @@ i915_gem_evict_something(struct i915_address_space *vm, * On each list, the oldest objects lie at the HEAD with the freshest * object on the TAIL. */ + mode = DRM_MM_INSERT_BEST; + if (flags & PIN_HIGH) + mode = DRM_MM_INSERT_HIGH; + if (flags & PIN_MAPPABLE) + mode = DRM_MM_INSERT_LOW; drm_mm_scan_init_with_range(&scan, &vm->mm, min_size, alignment, cache_level, - start, end, - flags & PIN_HIGH ? DRM_MM_CREATE_TOP : 0); + start, end, mode);

/* Retire before we search the active list. Although we have * reasonable accuracy in our retirement lists, we may have diff --git a/drivers/gpu/drm/i915/i915_gem_execbuffer.c b/drivers/gpu/drm/i915/i915_gem_execbuffer.c index c64438f8171c..3e435caf7221 100644 --- a/drivers/gpu/drm/i915/i915_gem_execbuffer.c +++ b/drivers/gpu/drm/i915/i915_gem_execbuffer.c @@ -436,12 +436,11 @@ static void *reloc_iomap(struct drm_i915_gem_object *obj, PIN_MAPPABLE | PIN_NONBLOCK); if (IS_ERR(vma)) { memset(&cache->node, 0, sizeof(cache->node)); - ret = drm_mm_insert_node_in_range_generic + ret = drm_mm_insert_node_in_range (&ggtt->base.mm, &cache->node, 4096, 0, I915_COLOR_UNEVICTABLE, 0, ggtt->mappable_end, - DRM_MM_SEARCH_DEFAULT, - DRM_MM_CREATE_DEFAULT); + DRM_MM_INSERT_LOW); if (ret) /* no inactive aperture space, use cpu reloc */ return NULL; } else { diff --git a/drivers/gpu/drm/i915/i915_gem_gtt.c b/drivers/gpu/drm/i915/i915_gem_gtt.c index c8f1675852a7..939b862bfcfa 100644 --- a/drivers/gpu/drm/i915/i915_gem_gtt.c +++ b/drivers/gpu/drm/i915/i915_gem_gtt.c @@ -2722,12 +2722,10 @@ int i915_gem_init_ggtt(struct drm_i915_private *dev_priv) return ret;

/* Reserve a mappable slot for our lockless error capture */ - ret = drm_mm_insert_node_in_range_generic(&ggtt->base.mm, - &ggtt->error_capture, - 4096, 0, - I915_COLOR_UNEVICTABLE, - 0, ggtt->mappable_end, - 0, 0); + ret = drm_mm_insert_node_in_range(&ggtt->base.mm, &ggtt->error_capture, + 4096, 0, I915_COLOR_UNEVICTABLE, + 0, ggtt->mappable_end, + DRM_MM_INSERT_LOW); if (ret) return ret;

@@ -3542,18 +3540,16 @@ int i915_gem_gtt_insert(struct i915_address_space *vm, u64 size, u64 alignment, unsigned long color, u64 start, u64 end, unsigned int flags) { - u32 search_flag, alloc_flag; + enum drm_mm_insert_mode mode; int err;

lockdep_assert_held(&vm->i915->drm.struct_mutex);

- if (flags & PIN_HIGH) { - search_flag = DRM_MM_SEARCH_BELOW; - alloc_flag = DRM_MM_CREATE_TOP; - } else { - search_flag = DRM_MM_SEARCH_DEFAULT; - alloc_flag = DRM_MM_CREATE_DEFAULT; - } + mode = DRM_MM_INSERT_BEST; + if (flags & PIN_HIGH) + mode = DRM_MM_INSERT_HIGH; + if (flags & PIN_MAPPABLE) + mode = DRM_MM_INSERT_LOW;

/* We only allocate in PAGE_SIZE/GTT_PAGE_SIZE (4096) chunks, * so we know that we always have a minimum alignment of 4096. @@ -3565,10 +3561,9 @@ int i915_gem_gtt_insert(struct i915_address_space *vm, if (alignment <= 4096) alignment = 0;

- err = drm_mm_insert_node_in_range_generic(&vm->mm, node, - size, alignment, color, - start, end, - search_flag, alloc_flag); + err = drm_mm_insert_node_in_range(&vm->mm, node, + size, alignment, color, + start, end, mode); if (err != -ENOSPC) return err;

@@ -3577,9 +3572,7 @@ int i915_gem_gtt_insert(struct i915_address_space *vm, if (err) return err;

- search_flag = DRM_MM_SEARCH_DEFAULT; - return drm_mm_insert_node_in_range_generic(&vm->mm, node, - size, alignment, color, - start, end, - search_flag, alloc_flag); + return drm_mm_insert_node_in_range(&vm->mm, node, + size, alignment, color, + start, end, DRM_MM_INSERT_EVICT); } diff --git a/drivers/gpu/drm/i915/i915_gem_stolen.c b/drivers/gpu/drm/i915/i915_gem_stolen.c index f1a80bfa9919..f6d507faf83b 100644 --- a/drivers/gpu/drm/i915/i915_gem_stolen.c +++ b/drivers/gpu/drm/i915/i915_gem_stolen.c @@ -55,9 +55,9 @@ int i915_gem_stolen_insert_node_in_range(struct drm_i915_private *dev_priv, return -ENODEV;

mutex_lock(&dev_priv->mm.stolen_lock); - ret = drm_mm_insert_node_in_range(&dev_priv->mm.stolen, node, size, - alignment, start, end, - DRM_MM_SEARCH_DEFAULT); + ret = drm_mm_insert_node_in_range(&dev_priv->mm.stolen, node, + size, alignment, 0, + start, end, DRM_MM_INSERT_BEST); mutex_unlock(&dev_priv->mm.stolen_lock);

return ret; diff --git a/drivers/gpu/drm/msm/msm_gem.c b/drivers/gpu/drm/msm/msm_gem.c index cd06cfd94687..412669062cb7 100644 --- a/drivers/gpu/drm/msm/msm_gem.c +++ b/drivers/gpu/drm/msm/msm_gem.c @@ -54,8 +54,7 @@ static struct page **get_pages_vram(struct drm_gem_object *obj, if (!p) return ERR_PTR(-ENOMEM);

- ret = drm_mm_insert_node(&priv->vram.mm, msm_obj->vram_node, - npages, 0, DRM_MM_SEARCH_DEFAULT); + ret = drm_mm_insert_node(&priv->vram.mm, msm_obj->vram_node, npages); if (ret) { drm_free_large(p); return ERR_PTR(ret); diff --git a/drivers/gpu/drm/msm/msm_gem_vma.c b/drivers/gpu/drm/msm/msm_gem_vma.c index a311d26ccb21..b654eca7636a 100644 --- a/drivers/gpu/drm/msm/msm_gem_vma.c +++ b/drivers/gpu/drm/msm/msm_gem_vma.c @@ -45,8 +45,7 @@ msm_gem_map_vma(struct msm_gem_address_space *aspace, if (WARN_ON(drm_mm_node_allocated(&vma->node))) return 0;

- ret = drm_mm_insert_node(&aspace->mm, &vma->node, npages, - 0, DRM_MM_SEARCH_DEFAULT); + ret = drm_mm_insert_node(&aspace->mm, &vma->node, npages); if (ret) return ret;

diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c index 2ce92f4dcfc7..a07c04a6c4b9 100644 --- a/drivers/gpu/drm/selftests/test-drm_mm.c +++ b/drivers/gpu/drm/selftests/test-drm_mm.c @@ -22,23 +22,24 @@ static unsigned int max_iterations = 8192; static unsigned int max_prime = 128;

enum { - DEFAULT, - TOPDOWN, BEST, + BOTTOMUP, + TOPDOWN, + EVICT, };

static const struct insert_mode { const char *name; - unsigned int search_flags; - unsigned int create_flags; + enum drm_mm_insert_mode mode; } insert_modes[] = { - [DEFAULT] = { "default", DRM_MM_SEARCH_DEFAULT, DRM_MM_CREATE_DEFAULT }, - [TOPDOWN] = { "top-down", DRM_MM_SEARCH_BELOW, DRM_MM_CREATE_TOP }, - [BEST] = { "best", DRM_MM_SEARCH_BEST, DRM_MM_CREATE_DEFAULT }, + [BEST] = { "best", DRM_MM_INSERT_BEST }, + [BOTTOMUP] = { "bottom-up", DRM_MM_INSERT_LOW }, + [TOPDOWN] = { "top-down", DRM_MM_INSERT_HIGH }, + [EVICT] = { "evict", DRM_MM_INSERT_EVICT }, {} }, evict_modes[] = { - { "default", DRM_MM_SEARCH_DEFAULT, DRM_MM_CREATE_DEFAULT }, - { "top-down", DRM_MM_SEARCH_BELOW, DRM_MM_CREATE_TOP }, + { "bottom-up", DRM_MM_INSERT_LOW }, + { "top-down", DRM_MM_INSERT_HIGH }, {} };

@@ -522,8 +523,7 @@ static bool expect_insert(struct drm_mm *mm, struct drm_mm_node *node,

err = drm_mm_insert_node_generic(mm, node, size, alignment, color, - mode->search_flags, - mode->create_flags); + mode->mode); if (err) { pr_err("insert (size=%llu, alignment=%llu, color=%lu, mode=%s) failed with err=%d\n", size, alignment, color, mode->name, err); @@ -543,7 +543,7 @@ static bool expect_insert_fail(struct drm_mm *mm, u64 size) struct drm_mm_node tmp = {}; int err;

- err = drm_mm_insert_node(mm, &tmp, size, 0, DRM_MM_SEARCH_DEFAULT); + err = drm_mm_insert_node(mm, &tmp, size); if (likely(err == -ENOSPC)) return true;

@@ -749,11 +749,10 @@ static bool expect_insert_in_range(struct drm_mm *mm, struct drm_mm_node *node, { int err;

- err = drm_mm_insert_node_in_range_generic(mm, node, - size, alignment, color, - range_start, range_end, - mode->search_flags, - mode->create_flags); + err = drm_mm_insert_node_in_range(mm, node, + size, alignment, color, + range_start, range_end, + mode->mode); if (err) { pr_err("insert (size=%llu, alignment=%llu, color=%lu, mode=%s) nto range [%llx, %llx] failed with err=%d\n", size, alignment, color, mode->name, @@ -777,11 +776,10 @@ static bool expect_insert_in_range_fail(struct drm_mm *mm, struct drm_mm_node tmp = {}; int err;

- err = drm_mm_insert_node_in_range_generic(mm, &tmp, - size, 0, 0, - range_start, range_end, - DRM_MM_SEARCH_DEFAULT, - DRM_MM_CREATE_DEFAULT); + err = drm_mm_insert_node_in_range(mm, &tmp, + size, 0, 0, + range_start, range_end, + 0); if (likely(err == -ENOSPC)) return true;

@@ -1314,7 +1312,7 @@ static int evict_something(struct drm_mm *mm, drm_mm_scan_init_with_range(&scan, mm, size, alignment, 0, range_start, range_end, - mode->create_flags); + mode->mode); if (!evict_nodes(&scan, nodes, order, count, false, &evict_list)) @@ -1322,8 +1320,7 @@ static int evict_something(struct drm_mm *mm,

memset(&tmp, 0, sizeof(tmp)); err = drm_mm_insert_node_generic(mm, &tmp, size, alignment, 0, - mode->search_flags, - mode->create_flags); + DRM_MM_INSERT_EVICT); if (err) { pr_err("Failed to insert into eviction hole: size=%d, align=%d\n", size, alignment); @@ -1398,8 +1395,7 @@ static int igt_evict(void *ignored) ret = -EINVAL; drm_mm_init(&mm, 0, size); for (n = 0; n < size; n++) { - err = drm_mm_insert_node(&mm, &nodes[n].node, 1, 0, - DRM_MM_SEARCH_DEFAULT); + err = drm_mm_insert_node(&mm, &nodes[n].node, 1); if (err) { pr_err("insert failed, step %d\n", n); ret = err; @@ -1507,8 +1503,7 @@ static int igt_evict_range(void *ignored) ret = -EINVAL; drm_mm_init(&mm, 0, size); for (n = 0; n < size; n++) { - err = drm_mm_insert_node(&mm, &nodes[n].node, 1, 0, - DRM_MM_SEARCH_DEFAULT); + err = drm_mm_insert_node(&mm, &nodes[n].node, 1); if (err) { pr_err("insert failed, step %d\n", n); ret = err; @@ -1894,7 +1889,7 @@ static int evict_color(struct drm_mm *mm, drm_mm_scan_init_with_range(&scan, mm, size, alignment, color, range_start, range_end, - mode->create_flags); + mode->mode); if (!evict_nodes(&scan, nodes, order, count, true, &evict_list)) @@ -1902,8 +1897,7 @@ static int evict_color(struct drm_mm *mm,

memset(&tmp, 0, sizeof(tmp)); err = drm_mm_insert_node_generic(mm, &tmp, size, alignment, color, - mode->search_flags, - mode->create_flags); + DRM_MM_INSERT_EVICT); if (err) { pr_err("Failed to insert into eviction hole: size=%d, align=%d, color=%lu, err=%d\n", size, alignment, color, err); diff --git a/drivers/gpu/drm/sis/sis_mm.c b/drivers/gpu/drm/sis/sis_mm.c index 03defda77766..1622db24cd39 100644 --- a/drivers/gpu/drm/sis/sis_mm.c +++ b/drivers/gpu/drm/sis/sis_mm.c @@ -109,8 +109,7 @@ static int sis_drm_alloc(struct drm_device *dev, struct drm_file *file, if (pool == AGP_TYPE) { retval = drm_mm_insert_node(&dev_priv->agp_mm, &item->mm_node, - mem->size, 0, - DRM_MM_SEARCH_DEFAULT); + mem->size); offset = item->mm_node.start; } else { #if defined(CONFIG_FB_SIS) || defined(CONFIG_FB_SIS_MODULE) @@ -122,8 +121,7 @@ static int sis_drm_alloc(struct drm_device *dev, struct drm_file *file, #else retval = drm_mm_insert_node(&dev_priv->vram_mm, &item->mm_node, - mem->size, 0, - DRM_MM_SEARCH_DEFAULT); + mem->size); offset = item->mm_node.start; #endif } diff --git a/drivers/gpu/drm/tegra/gem.c b/drivers/gpu/drm/tegra/gem.c index c08e5279eeac..a6051d6c6de6 100644 --- a/drivers/gpu/drm/tegra/gem.c +++ b/drivers/gpu/drm/tegra/gem.c @@ -128,8 +128,8 @@ static int tegra_bo_iommu_map(struct tegra_drm *tegra, struct tegra_bo *bo) if (!bo->mm) return -ENOMEM;

- err = drm_mm_insert_node_generic(&tegra->mm, bo->mm, bo->gem.size, - PAGE_SIZE, 0, 0, 0); + err = drm_mm_insert_node_generic(&tegra->mm, + bo->mm, bo->gem.size, PAGE_SIZE, 0, 0); if (err < 0) { dev_err(tegra->drm->dev, "out of I/O virtual memory: %zd\n", err); diff --git a/drivers/gpu/drm/ttm/ttm_bo_manager.c b/drivers/gpu/drm/ttm/ttm_bo_manager.c index aea6a01500e1..493fe6b33353 100644 --- a/drivers/gpu/drm/ttm/ttm_bo_manager.c +++ b/drivers/gpu/drm/ttm/ttm_bo_manager.c @@ -54,9 +54,8 @@ static int ttm_bo_man_get_node(struct ttm_mem_type_manager *man, { struct ttm_range_manager *rman = (struct ttm_range_manager *) man->priv; struct drm_mm *mm = &rman->mm; - struct drm_mm_node *node = NULL; - enum drm_mm_search_flags sflags = DRM_MM_SEARCH_BEST; - enum drm_mm_allocator_flags aflags = DRM_MM_CREATE_DEFAULT; + struct drm_mm_node *node; + enum drm_mm_insert_mode mode; unsigned long lpfn; int ret;

@@ -68,16 +67,15 @@ static int ttm_bo_man_get_node(struct ttm_mem_type_manager *man, if (!node) return -ENOMEM;

- if (place->flags & TTM_PL_FLAG_TOPDOWN) { - sflags = DRM_MM_SEARCH_BELOW; - aflags = DRM_MM_CREATE_TOP; - } + mode = DRM_MM_INSERT_BEST; + if (place->flags & TTM_PL_FLAG_TOPDOWN) + mode = DRM_MM_INSERT_HIGH;

spin_lock(&rman->lock); - ret = drm_mm_insert_node_in_range_generic(mm, node, mem->num_pages, + ret = drm_mm_insert_node_in_range(mm, node, + mem->num_pages, mem->page_alignment, 0, - place->fpfn, lpfn, - sflags, aflags); + place->fpfn, lpfn, mode); spin_unlock(&rman->lock);

if (unlikely(ret)) { diff --git a/drivers/gpu/drm/vc4/vc4_crtc.c b/drivers/gpu/drm/vc4/vc4_crtc.c index a0fd3e66bc4b..baacdf62c83e 100644 --- a/drivers/gpu/drm/vc4/vc4_crtc.c +++ b/drivers/gpu/drm/vc4/vc4_crtc.c @@ -589,7 +589,7 @@ static int vc4_crtc_atomic_check(struct drm_crtc *crtc,

spin_lock_irqsave(&vc4->hvs->mm_lock, flags); ret = drm_mm_insert_node(&vc4->hvs->dlist_mm, &vc4_state->mm, - dlist_count, 1, 0); + dlist_count); spin_unlock_irqrestore(&vc4->hvs->mm_lock, flags); if (ret) return ret; diff --git a/drivers/gpu/drm/vc4/vc4_hvs.c b/drivers/gpu/drm/vc4/vc4_hvs.c index 6fbab1c82cb1..4aba0fa56289 100644 --- a/drivers/gpu/drm/vc4/vc4_hvs.c +++ b/drivers/gpu/drm/vc4/vc4_hvs.c @@ -141,8 +141,7 @@ static int vc4_hvs_upload_linear_kernel(struct vc4_hvs *hvs, int ret, i; u32 __iomem *dst_kernel;

- ret = drm_mm_insert_node(&hvs->dlist_mm, space, VC4_KERNEL_DWORDS, 1, - 0); + ret = drm_mm_insert_node(&hvs->dlist_mm, space, VC4_KERNEL_DWORDS); if (ret) { DRM_ERROR("Failed to allocate space for filter kernel: %d\n", ret); diff --git a/drivers/gpu/drm/vc4/vc4_plane.c b/drivers/gpu/drm/vc4/vc4_plane.c index 110d1518f5d5..c1f06897136b 100644 --- a/drivers/gpu/drm/vc4/vc4_plane.c +++ b/drivers/gpu/drm/vc4/vc4_plane.c @@ -514,9 +514,9 @@ static int vc4_plane_mode_set(struct drm_plane *plane, if (lbm_size) { if (!vc4_state->lbm.allocated) { spin_lock_irqsave(&vc4->hvs->mm_lock, irqflags); - ret = drm_mm_insert_node(&vc4->hvs->lbm_mm, - &vc4_state->lbm, - lbm_size, 32, 0); + ret = drm_mm_insert_node_generic(&vc4->hvs->lbm_mm, + &vc4_state->lbm, + lbm_size, 32, 0, 0); spin_unlock_irqrestore(&vc4->hvs->mm_lock, irqflags); } else { WARN_ON_ONCE(lbm_size != vc4_state->lbm.size); diff --git a/drivers/gpu/drm/via/via_mm.c b/drivers/gpu/drm/via/via_mm.c index a04ef1c992d9..4217d66a5cc6 100644 --- a/drivers/gpu/drm/via/via_mm.c +++ b/drivers/gpu/drm/via/via_mm.c @@ -140,11 +140,11 @@ int via_mem_alloc(struct drm_device *dev, void *data, if (mem->type == VIA_MEM_AGP) retval = drm_mm_insert_node(&dev_priv->agp_mm, &item->mm_node, - tmpSize, 0, DRM_MM_SEARCH_DEFAULT); + tmpSize); else retval = drm_mm_insert_node(&dev_priv->vram_mm, &item->mm_node, - tmpSize, 0, DRM_MM_SEARCH_DEFAULT); + tmpSize); if (retval) goto fail_alloc;

diff --git a/drivers/gpu/drm/vmwgfx/vmwgfx_cmdbuf.c b/drivers/gpu/drm/vmwgfx/vmwgfx_cmdbuf.c index aa04fb0159a7..77cb7c627e09 100644 --- a/drivers/gpu/drm/vmwgfx/vmwgfx_cmdbuf.c +++ b/drivers/gpu/drm/vmwgfx/vmwgfx_cmdbuf.c @@ -673,16 +673,10 @@ static bool vmw_cmdbuf_try_alloc(struct vmw_cmdbuf_man *man,

memset(info->node, 0, sizeof(*info->node)); spin_lock_bh(&man->lock); - ret = drm_mm_insert_node_generic(&man->mm, info->node, info->page_size, - 0, 0, - DRM_MM_SEARCH_DEFAULT, - DRM_MM_CREATE_DEFAULT); + ret = drm_mm_insert_node(&man->mm, info->node, info->page_size); if (ret) { vmw_cmdbuf_man_process(man); - ret = drm_mm_insert_node_generic(&man->mm, info->node, - info->page_size, 0, 0, - DRM_MM_SEARCH_DEFAULT, - DRM_MM_CREATE_DEFAULT); + ret = drm_mm_insert_node(&man->mm, info->node, info->page_size); }

spin_unlock_bh(&man->lock); diff --git a/include/drm/drm_mm.h b/include/drm/drm_mm.h index 92ec5759caae..6558cd08d7c9 100644 --- a/include/drm/drm_mm.h +++ b/include/drm/drm_mm.h @@ -55,32 +55,27 @@ #define DRM_MM_BUG_ON(expr) BUILD_BUG_ON_INVALID(expr) #endif

-enum drm_mm_search_flags { - DRM_MM_SEARCH_DEFAULT = 0, - DRM_MM_SEARCH_BEST = 1 << 0, - DRM_MM_SEARCH_BELOW = 1 << 1, +enum drm_mm_insert_mode { + DRM_MM_INSERT_BEST = 0, + DRM_MM_INSERT_LOW, + DRM_MM_INSERT_HIGH, + DRM_MM_INSERT_EVICT, };

-enum drm_mm_allocator_flags { - DRM_MM_CREATE_DEFAULT = 0, - DRM_MM_CREATE_TOP = 1 << 0, -}; - -#define DRM_MM_BOTTOMUP DRM_MM_SEARCH_DEFAULT, DRM_MM_CREATE_DEFAULT -#define DRM_MM_TOPDOWN DRM_MM_SEARCH_BELOW, DRM_MM_CREATE_TOP - struct drm_mm_node { + struct drm_mm *mm; struct list_head node_list; struct list_head hole_stack; struct rb_node rb; - unsigned hole_follows : 1; - unsigned allocated : 1; - bool scanned_block : 1; - unsigned long color; + struct rb_node rb_hole_size; + struct rb_node rb_hole_addr; u64 start; u64 size; u64 __subtree_last; - struct drm_mm *mm; + u64 hole_size; + unsigned long color; + bool allocated : 1; + bool scanned_block : 1; #ifdef CONFIG_DRM_DEBUG_MM depot_stack_handle_t stack; #endif @@ -94,6 +89,8 @@ struct drm_mm { struct drm_mm_node head_node; /* Keep an interval_tree for fast lookup of drm_mm_nodes by address. */ struct rb_root interval_tree; + struct rb_root holes_size; + struct rb_root holes_addr;

void (*color_adjust)(const struct drm_mm_node *node, unsigned long color, @@ -116,7 +113,7 @@ struct drm_mm_scan { u64 hit_end;

unsigned long color; - unsigned int flags; + enum drm_mm_insert_mode mode; };

/** @@ -168,7 +165,7 @@ static inline bool drm_mm_initialized(const struct drm_mm *mm) */ static inline bool drm_mm_hole_follows(const struct drm_mm_node *node) { - return node->hole_follows; + return node->hole_size; }

static inline u64 __drm_mm_hole_node_start(const struct drm_mm_node *hole_node) @@ -251,14 +248,6 @@ static inline u64 drm_mm_hole_node_end(const struct drm_mm_node *hole_node) #define drm_mm_for_each_node_safe(entry, next, mm) \ list_for_each_entry_safe(entry, next, drm_mm_nodes(mm), node_list)

-#define __drm_mm_for_each_hole(entry, mm, hole_start, hole_end, backwards) \ - for (entry = list_entry((backwards) ? (mm)->hole_stack.prev : (mm)->hole_stack.next, struct drm_mm_node, hole_stack); \ - &entry->hole_stack != &(mm)->hole_stack ? \ - hole_start = drm_mm_hole_node_start(entry), \ - hole_end = drm_mm_hole_node_end(entry), \ - 1 : 0; \ - entry = list_entry((backwards) ? entry->hole_stack.prev : entry->hole_stack.next, struct drm_mm_node, hole_stack)) - /** * drm_mm_for_each_hole - iterator to walk over all holes * @entry: drm_mm_node used internally to track progress @@ -274,57 +263,27 @@ static inline u64 drm_mm_hole_node_end(const struct drm_mm_node *hole_node) * Implementation Note: * We need to inline list_for_each_entry in order to be able to set hole_start * and hole_end on each iteration while keeping the macro sane. - * - * The __drm_mm_for_each_hole version is similar, but with added support for - * going backwards. */ -#define drm_mm_for_each_hole(entry, mm, hole_start, hole_end) \ - __drm_mm_for_each_hole(entry, mm, hole_start, hole_end, 0) +#define drm_mm_for_each_hole(pos, mm, hole_start, hole_end) \ + for (pos = list_first_entry(&(mm)->hole_stack, \ + typeof(*pos), hole_stack); \ + &pos->hole_stack != &(mm)->hole_stack ? \ + hole_start = drm_mm_hole_node_start(pos), \ + hole_end = hole_start + pos->hole_size : 0; \ + pos = list_next_entry(pos, hole_stack))

/* * Basic range manager support (drm_mm.c) */ int drm_mm_reserve_node(struct drm_mm *mm, struct drm_mm_node *node); -int drm_mm_insert_node_in_range_generic(struct drm_mm *mm, - struct drm_mm_node *node, - u64 size, - u64 alignment, - unsigned long color, - u64 start, - u64 end, - enum drm_mm_search_flags sflags, - enum drm_mm_allocator_flags aflags); - -/** - * drm_mm_insert_node_in_range - ranged search for space and insert @node - * @mm: drm_mm to allocate from - * @node: preallocate node to insert - * @size: size of the allocation - * @alignment: alignment of the allocation - * @start: start of the allowed range for this node - * @end: end of the allowed range for this node - * @flags: flags to fine-tune the allocation - * - * This is a simplified version of drm_mm_insert_node_in_range_generic() with - * @color set to 0. - * - * The preallocated node must be cleared to 0. - * - * Returns: - * 0 on success, -ENOSPC if there's no suitable hole. - */ -static inline int drm_mm_insert_node_in_range(struct drm_mm *mm, - struct drm_mm_node *node, - u64 size, - u64 alignment, - u64 start, - u64 end, - enum drm_mm_search_flags flags) -{ - return drm_mm_insert_node_in_range_generic(mm, node, size, alignment, - 0, start, end, flags, - DRM_MM_CREATE_DEFAULT); -} +int drm_mm_insert_node_in_range(struct drm_mm *mm, + struct drm_mm_node *node, + u64 size, + u64 alignment, + unsigned long color, + u64 start, + u64 end, + enum drm_mm_insert_mode mode);

/** * drm_mm_insert_node_generic - search for space and insert @node @@ -333,8 +292,7 @@ static inline int drm_mm_insert_node_in_range(struct drm_mm *mm, * @size: size of the allocation * @alignment: alignment of the allocation * @color: opaque tag value to use for this node - * @sflags: flags to fine-tune the allocation search - * @aflags: flags to fine-tune the allocation behavior + * @mode: fine-tune the allocation search and placement * * The preallocated node must be cleared to 0. * @@ -345,13 +303,11 @@ static inline int drm_mm_insert_node_generic(struct drm_mm *mm, struct drm_mm_node *node, u64 size, u64 alignment, unsigned long color, - enum drm_mm_search_flags sflags, - enum drm_mm_allocator_flags aflags) + enum drm_mm_insert_mode mode) { - return drm_mm_insert_node_in_range_generic(mm, node, - size, alignment, 0, - 0, U64_MAX, - sflags, aflags); + return drm_mm_insert_node_in_range(mm, node, + size, alignment, color, + 0, U64_MAX, mode); }

/** @@ -359,8 +315,6 @@ drm_mm_insert_node_generic(struct drm_mm *mm, struct drm_mm_node *node, * @mm: drm_mm to allocate from * @node: preallocate node to insert * @size: size of the allocation - * @alignment: alignment of the allocation - * @flags: flags to fine-tune the allocation * * This is a simplified version of drm_mm_insert_node_generic() with @color set * to 0. @@ -372,13 +326,9 @@ drm_mm_insert_node_generic(struct drm_mm *mm, struct drm_mm_node *node, */ static inline int drm_mm_insert_node(struct drm_mm *mm, struct drm_mm_node *node, - u64 size, - u64 alignment, - enum drm_mm_search_flags flags) + u64 size) { - return drm_mm_insert_node_generic(mm, node, - size, alignment, 0, - flags, DRM_MM_CREATE_DEFAULT); + return drm_mm_insert_node_generic(mm, node, size, 0, 0, 0); }

void drm_mm_remove_node(struct drm_mm_node *node); @@ -425,7 +375,7 @@ void drm_mm_scan_init_with_range(struct drm_mm_scan *scan, struct drm_mm *mm, u64 size, u64 alignment, unsigned long color, u64 start, u64 end, - unsigned int flags); + enum drm_mm_insert_mode mode);

/** * drm_mm_scan_init - initialize lru scanning @@ -434,7 +384,7 @@ void drm_mm_scan_init_with_range(struct drm_mm_scan *scan, * @size: size of the allocation * @alignment: alignment of the allocation * @color: opaque tag value to use for the allocation - * @flags: flags to specify how the allocation will be performed afterwards + * @mode: fine-tune the allocation search and placement * * This simply sets up the scanning routines with the parameters for the desired * hole. @@ -448,12 +398,11 @@ static inline void drm_mm_scan_init(struct drm_mm_scan *scan, u64 size, u64 alignment, unsigned long color, - unsigned int flags) + enum drm_mm_insert_mode mode) { drm_mm_scan_init_with_range(scan, mm, size, alignment, color, - 0, U64_MAX, - flags); + 0, U64_MAX, mode); }

bool drm_mm_scan_add_block(struct drm_mm_scan *scan,