6 files changed, 280 insertions, 28 deletions

diff --git a/drivers/gpu/drm/i915/i915_drv.h b/drivers/gpu/drm/i915/i915_drv.h
index 8a181b455197..6a051381f535 100644
--- a/drivers/gpu/drm/i915/i915_drv.h
+++ b/drivers/gpu/drm/i915/i915_drv.h
@@ -1978,6 +1978,10 @@ struct drm_i915_private {
                 struct i915_gt_timelines {
                         struct mutex mutex; /* protects list, tainted by GPU */
                         struct list_head list;
+
+                        /* Pack multiple timelines' seqnos into the same page */
+                        spinlock_t hwsp_lock;
+                        struct list_head hwsp_free_list;
                 } timelines;
 
                 struct list_head active_rings;
diff --git a/drivers/gpu/drm/i915/i915_timeline.c b/drivers/gpu/drm/i915/i915_timeline.c
index 8d5792311a8f..add8fc33cf6e 100644
--- a/drivers/gpu/drm/i915/i915_timeline.c
+++ b/drivers/gpu/drm/i915/i915_timeline.c
@@ -9,6 +9,18 @@
 #include "i915_timeline.h"
 #include "i915_syncmap.h"
 
+struct i915_timeline_hwsp {
+        struct i915_vma *vma;
+        struct list_head free_link;
+        u64 free_bitmap;
+};
+
+static inline struct i915_timeline_hwsp *
+i915_timeline_hwsp(const struct i915_timeline *tl)
+{
+        return tl->hwsp_ggtt->private;
+}
+
 static struct i915_vma *__hwsp_alloc(struct drm_i915_private *i915)
 {
         struct drm_i915_gem_object *obj;
@@ -27,28 +39,89 @@ static struct i915_vma *__hwsp_alloc(struct drm_i915_private *i915)
         return vma;
 }
 
-static int hwsp_alloc(struct i915_timeline *timeline)
+static struct i915_vma *
+hwsp_alloc(struct i915_timeline *timeline, unsigned int *cacheline)
 {
-        struct i915_vma *vma;
+        struct drm_i915_private *i915 = timeline->i915;
+        struct i915_gt_timelines *gt = &i915->gt.timelines;
+        struct i915_timeline_hwsp *hwsp;
 
-        vma = __hwsp_alloc(timeline->i915);
-        if (IS_ERR(vma))
-                return PTR_ERR(vma);
+        BUILD_BUG_ON(BITS_PER_TYPE(u64) * CACHELINE_BYTES > PAGE_SIZE);
 
-        timeline->hwsp_ggtt = vma;
-        timeline->hwsp_offset = 0;
+        spin_lock(&gt->hwsp_lock);
 
-        return 0;
+        /* hwsp_free_list only contains HWSP that have available cachelines */
+        hwsp = list_first_entry_or_null(&gt->hwsp_free_list,
+                                        typeof(*hwsp), free_link);
+        if (!hwsp) {
+                struct i915_vma *vma;
+
+                spin_unlock(&gt->hwsp_lock);
+
+                hwsp = kmalloc(sizeof(*hwsp), GFP_KERNEL);
+                if (!hwsp)
+                        return ERR_PTR(-ENOMEM);
+
+                vma = __hwsp_alloc(i915);
+                if (IS_ERR(vma)) {
+                        kfree(hwsp);
+                        return vma;
+                }
+
+                vma->private = hwsp;
+                hwsp->vma = vma;
+                hwsp->free_bitmap = ~0ull;
+
+                spin_lock(&gt->hwsp_lock);
+                list_add(&hwsp->free_link, &gt->hwsp_free_list);
+        }
+
+        GEM_BUG_ON(!hwsp->free_bitmap);
+        *cacheline = __ffs64(hwsp->free_bitmap);
+        hwsp->free_bitmap &= ~BIT_ULL(*cacheline);
+        if (!hwsp->free_bitmap)
+                list_del(&hwsp->free_link);
+
+        spin_unlock(&gt->hwsp_lock);
+
+        GEM_BUG_ON(hwsp->vma->private != hwsp);
+        return hwsp->vma;
+}
+
+static void hwsp_free(struct i915_timeline *timeline)
+{
+        struct i915_gt_timelines *gt = &timeline->i915->gt.timelines;
+        struct i915_timeline_hwsp *hwsp;
+
+        hwsp = i915_timeline_hwsp(timeline);
+        if (!hwsp) /* leave global HWSP alone! */
+                return;
+
+        spin_lock(&gt->hwsp_lock);
+
+        /* As a cacheline becomes available, publish the HWSP on the freelist */
+        if (!hwsp->free_bitmap)
+                list_add_tail(&hwsp->free_link, &gt->hwsp_free_list);
+
+        hwsp->free_bitmap |= BIT_ULL(timeline->hwsp_offset / CACHELINE_BYTES);
+
+        /* And if no one is left using it, give the page back to the system */
+        if (hwsp->free_bitmap == ~0ull) {
+                i915_vma_put(hwsp->vma);
+                list_del(&hwsp->free_link);
+                kfree(hwsp);
+        }
+
+        spin_unlock(&gt->hwsp_lock);
 }
 
 int i915_timeline_init(struct drm_i915_private *i915,
                        struct i915_timeline *timeline,
                        const char *name,
-                       struct i915_vma *global_hwsp)
+                       struct i915_vma *hwsp)
 {
         struct i915_gt_timelines *gt = &i915->gt.timelines;
         void *vaddr;
-        int err;
 
         /*
          * Ideally we want a set of engines on a single leaf as we expect
@@ -64,18 +137,22 @@ int i915_timeline_init(struct drm_i915_private *i915,
         timeline->name = name;
         timeline->pin_count = 0;
 
-        if (global_hwsp) {
-                timeline->hwsp_ggtt = i915_vma_get(global_hwsp);
-                timeline->hwsp_offset = I915_GEM_HWS_SEQNO_ADDR;
-        } else {
-                err = hwsp_alloc(timeline);
-                if (err)
-                        return err;
+        timeline->hwsp_offset = I915_GEM_HWS_SEQNO_ADDR;
+        if (!hwsp) {
+                unsigned int cacheline;
+
+                hwsp = hwsp_alloc(timeline, &cacheline);
+                if (IS_ERR(hwsp))
+                        return PTR_ERR(hwsp);
+
+                timeline->hwsp_offset = cacheline * CACHELINE_BYTES;
         }
+        timeline->hwsp_ggtt = i915_vma_get(hwsp);
 
-        vaddr = i915_gem_object_pin_map(timeline->hwsp_ggtt->obj, I915_MAP_WB);
+        vaddr = i915_gem_object_pin_map(hwsp->obj, I915_MAP_WB);
         if (IS_ERR(vaddr)) {
-                i915_vma_put(timeline->hwsp_ggtt);
+                hwsp_free(timeline);
+                i915_vma_put(hwsp);
                 return PTR_ERR(vaddr);
         }
 
@@ -105,6 +182,9 @@ void i915_timelines_init(struct drm_i915_private *i915)
         mutex_init(&gt->mutex);
         INIT_LIST_HEAD(&gt->list);
 
+        spin_lock_init(&gt->hwsp_lock);
+        INIT_LIST_HEAD(&gt->hwsp_free_list);
+
         /* via i915_gem_wait_for_idle() */
         i915_gem_shrinker_taints_mutex(i915, &gt->mutex);
 }
@@ -144,12 +224,13 @@ void i915_timeline_fini(struct i915_timeline *timeline)
         GEM_BUG_ON(timeline->pin_count);
         GEM_BUG_ON(!list_empty(&timeline->requests));
 
-        i915_syncmap_free(&timeline->sync);
-
         mutex_lock(&gt->mutex);
         list_del(&timeline->link);
         mutex_unlock(&gt->mutex);
 
+        i915_syncmap_free(&timeline->sync);
+        hwsp_free(timeline);
+
         i915_gem_object_unpin_map(timeline->hwsp_ggtt->obj);
         i915_vma_put(timeline->hwsp_ggtt);
 }
@@ -226,6 +307,7 @@ void i915_timelines_fini(struct drm_i915_private *i915)
         struct i915_gt_timelines *gt = &i915->gt.timelines;
 
         GEM_BUG_ON(!list_empty(&gt->list));
+        GEM_BUG_ON(!list_empty(&gt->hwsp_free_list));
 
         mutex_destroy(&gt->mutex);
 }
diff --git a/drivers/gpu/drm/i915/i915_timeline.h b/drivers/gpu/drm/i915/i915_timeline.h
index 0c3739d53d79..ab736e2e5707 100644
--- a/drivers/gpu/drm/i915/i915_timeline.h
+++ b/drivers/gpu/drm/i915/i915_timeline.h
@@ -33,6 +33,7 @@
 #include "i915_utils.h"
 
 struct i915_vma;
+struct i915_timeline_hwsp;
 
 struct i915_timeline {
         u64 fence_context;
diff --git a/drivers/gpu/drm/i915/selftests/i915_random.c b/drivers/gpu/drm/i915/selftests/i915_random.c
index 1f415ce47018..716a3f19f030 100644
--- a/drivers/gpu/drm/i915/selftests/i915_random.c
+++ b/drivers/gpu/drm/i915/selftests/i915_random.c
@@ -41,18 +41,37 @@ u64 i915_prandom_u64_state(struct rnd_state *rnd)
         return x;
 }
 
-void i915_random_reorder(unsigned int *order, unsigned int count,
-                         struct rnd_state *state)
+void i915_prandom_shuffle(void *arr, size_t elsz, size_t count,
+                          struct rnd_state *state)
 {
-        unsigned int i, j;
+        char stack[128];
+
+        if (WARN_ON(elsz > sizeof(stack) || count > U32_MAX))
+                return;
+
+        if (!elsz || !count)
+                return;
+
+        /* Fisher-Yates shuffle courtesy of Knuth */
+        while (--count) {
+                size_t swp;
+
+                swp = i915_prandom_u32_max_state(count + 1, state);
+                if (swp == count)
+                        continue;
 
-        for (i = 0; i < count; i++) {
-                BUILD_BUG_ON(sizeof(unsigned int) > sizeof(u32));
-                j = i915_prandom_u32_max_state(count, state);
-                swap(order[i], order[j]);
+                memcpy(stack, arr + count * elsz, elsz);
+                memcpy(arr + count * elsz, arr + swp * elsz, elsz);
+                memcpy(arr + swp * elsz, stack, elsz);
         }
 }
 
+void i915_random_reorder(unsigned int *order, unsigned int count,
+                         struct rnd_state *state)
+{
+        i915_prandom_shuffle(order, sizeof(*order), count, state);
+}
+
 unsigned int *i915_random_order(unsigned int count, struct rnd_state *state)
 {
         unsigned int *order, i;
diff --git a/drivers/gpu/drm/i915/selftests/i915_random.h b/drivers/gpu/drm/i915/selftests/i915_random.h
index 7dffedc501ca..8e1ff9c105b6 100644
--- a/drivers/gpu/drm/i915/selftests/i915_random.h
+++ b/drivers/gpu/drm/i915/selftests/i915_random.h
@@ -54,4 +54,7 @@ void i915_random_reorder(unsigned int *order,
                          unsigned int count,
                          struct rnd_state *state);
 
+void i915_prandom_shuffle(void *arr, size_t elsz, size_t count,
+                          struct rnd_state *state);
+
 #endif /* !__I915_SELFTESTS_RANDOM_H__ */
diff --git a/drivers/gpu/drm/i915/selftests/i915_timeline.c b/drivers/gpu/drm/i915/selftests/i915_timeline.c
index 1585b614510d..c34340f074cf 100644
--- a/drivers/gpu/drm/i915/selftests/i915_timeline.c
+++ b/drivers/gpu/drm/i915/selftests/i915_timeline.c
@@ -4,6 +4,8 @@
  * Copyright © 2017-2018 Intel Corporation
  */
 
+#include <linux/prime_numbers.h>
+
 #include "../i915_selftest.h"
 #include "i915_random.h"
 
@@ -11,6 +13,146 @@
 #include "mock_gem_device.h"
 #include "mock_timeline.h"
 
+static struct page *hwsp_page(struct i915_timeline *tl)
+{
+        struct drm_i915_gem_object *obj = tl->hwsp_ggtt->obj;
+
+        GEM_BUG_ON(!i915_gem_object_has_pinned_pages(obj));
+        return sg_page(obj->mm.pages->sgl);
+}
+
+static unsigned long hwsp_cacheline(struct i915_timeline *tl)
+{
+        unsigned long address = (unsigned long)page_address(hwsp_page(tl));
+
+        return (address + tl->hwsp_offset) / CACHELINE_BYTES;
+}
+
+#define CACHELINES_PER_PAGE (PAGE_SIZE / CACHELINE_BYTES)
+
+struct mock_hwsp_freelist {
+        struct drm_i915_private *i915;
+        struct radix_tree_root cachelines;
+        struct i915_timeline **history;
+        unsigned long count, max;
+        struct rnd_state prng;
+};
+
+enum {
+        SHUFFLE = BIT(0),
+};
+
+static void __mock_hwsp_record(struct mock_hwsp_freelist *state,
+                               unsigned int idx,
+                               struct i915_timeline *tl)
+{
+        tl = xchg(&state->history[idx], tl);
+        if (tl) {
+                radix_tree_delete(&state->cachelines, hwsp_cacheline(tl));
+                i915_timeline_put(tl);
+        }
+}
+
+static int __mock_hwsp_timeline(struct mock_hwsp_freelist *state,
+                                unsigned int count,
+                                unsigned int flags)
+{
+        struct i915_timeline *tl;
+        unsigned int idx;
+
+        while (count--) {
+                unsigned long cacheline;
+                int err;
+
+                tl = i915_timeline_create(state->i915, "mock", NULL);
+                if (IS_ERR(tl))
+                        return PTR_ERR(tl);
+
+                cacheline = hwsp_cacheline(tl);
+                err = radix_tree_insert(&state->cachelines, cacheline, tl);
+                if (err) {
+                        if (err == -EEXIST) {
+                                pr_err("HWSP cacheline %lu already used; duplicate allocation!\n",
+                                       cacheline);
+                        }
+                        i915_timeline_put(tl);
+                        return err;
+                }
+
+                idx = state->count++ % state->max;
+                __mock_hwsp_record(state, idx, tl);
+        }
+
+        if (flags & SHUFFLE)
+                i915_prandom_shuffle(state->history,
+                                     sizeof(*state->history),
+                                     min(state->count, state->max),
+                                     &state->prng);
+
+        count = i915_prandom_u32_max_state(min(state->count, state->max),
+                                           &state->prng);
+        while (count--) {
+                idx = --state->count % state->max;
+                __mock_hwsp_record(state, idx, NULL);
+        }
+
+        return 0;
+}
+
+static int mock_hwsp_freelist(void *arg)
+{
+        struct mock_hwsp_freelist state;
+        const struct {
+                const char *name;
+                unsigned int flags;
+        } phases[] = {
+                { "linear", 0 },
+                { "shuffled", SHUFFLE },
+                { },
+        }, *p;
+        unsigned int na;
+        int err = 0;
+
+        INIT_RADIX_TREE(&state.cachelines, GFP_KERNEL);
+        state.prng = I915_RND_STATE_INITIALIZER(i915_selftest.random_seed);
+
+        state.i915 = mock_gem_device();
+        if (!state.i915)
+                return -ENOMEM;
+
+        /*
+         * Create a bunch of timelines and check that their HWSP do not overlap.
+         * Free some, and try again.
+         */
+
+        state.max = PAGE_SIZE / sizeof(*state.history);
+        state.count = 0;
+        state.history = kcalloc(state.max, sizeof(*state.history), GFP_KERNEL);
+        if (!state.history) {
+                err = -ENOMEM;
+                goto err_put;
+        }
+
+        mutex_lock(&state.i915->drm.struct_mutex);
+        for (p = phases; p->name; p++) {
+                pr_debug("%s(%s)\n", __func__, p->name);
+                for_each_prime_number_from(na, 1, 2 * CACHELINES_PER_PAGE) {
+                        err = __mock_hwsp_timeline(&state, na, p->flags);
+                        if (err)
+                                goto out;
+                }
+        }
+
+out:
+        for (na = 0; na < state.max; na++)
+                __mock_hwsp_record(&state, na, NULL);
+        mutex_unlock(&state.i915->drm.struct_mutex);
+        kfree(state.history);
+err_put:
+        drm_dev_put(&state.i915->drm);
+        return err;
+}
+
 struct __igt_sync {
         const char *name;
         u32 seqno;
@@ -260,6 +402,7 @@ static int bench_sync(void *arg)
 int i915_timeline_mock_selftests(void)
 {
         static const struct i915_subtest tests[] = {
+                SUBTEST(mock_hwsp_freelist),
                 SUBTEST(igt_sync),
                 SUBTEST(bench_sync),
         };