From: Tvrtko Ursulin <tvrtko.ursulin@linux.intel.com>
To: Chris Wilson <chris@chris-wilson.co.uk>, intel-gfx@lists.freedesktop.org
Cc: thomas.hellstrom@intel.com
Subject: Re: [Intel-gfx] [PATCH 20/41] drm/i915: Replace priolist rbtree with a skiplist
Date: Thu, 28 Jan 2021 16:42:44 +0000 [thread overview]
Message-ID: <f4f42b32-d536-6f2f-0118-be7fedcd94db@linux.intel.com> (raw)
In-Reply-To: <161185117340.2943.10174190803342821813@build.alporthouse.com>
On 28/01/2021 16:26, Chris Wilson wrote:
> Quoting Tvrtko Ursulin (2021-01-28 15:56:19)
>> On 25/01/2021 14:01, Chris Wilson wrote:
>>> diff --git a/drivers/gpu/drm/i915/i915_priolist_types.h b/drivers/gpu/drm/i915/i915_priolist_types.h
>>> index bc2fa84f98a8..1200c3df6a4a 100644
>>> --- a/drivers/gpu/drm/i915/i915_priolist_types.h
>>> +++ b/drivers/gpu/drm/i915/i915_priolist_types.h
>>> @@ -38,10 +38,36 @@ enum {
>>> #define I915_PRIORITY_UNPREEMPTABLE INT_MAX
>>> #define I915_PRIORITY_BARRIER (I915_PRIORITY_UNPREEMPTABLE - 1)
>>>
>>> +#ifdef CONFIG_64BIT
>>> +#define I915_PRIOLIST_HEIGHT 12
>>> +#else
>>> +#define I915_PRIOLIST_HEIGHT 11
>>> +#endif
>>
>> I did not get this. On one hand I could think pointers are larger on
>> 64-bit so go for fewer levels, if size was a concern. But on the other
>> hand 32-bit is less important these days, definitely much less as a
>> performance platform. So going for less memory use => worse performance
>> on a less important platform, which typically could be more memory
>> constrained? Not sure I see it as that important either way to be
>> distinctive but a comment would satisfy me.
>
> Just aligned to the cacheline. The struct is 128B on 64b and 64B on 32b.
> On 64B, we will scale to around 16 million requests in flight and 4
> million on 32b. Which should be enough.
>
> If we shrunk 64b to a 64B node, we would only scale to 256 requests
> which limit we definitely will exceed.
Ok thanks, pouring it into a comment is implied.
>
>>> struct i915_priolist {
>>> struct list_head requests;
>>
>> What would be on this list? Request can only be on one at a time, so I
>> was thinking these nodes would have pointers to list of that priority,
>> rather than lists themselves. Assuming there can be multiple nodes of
>> the same priority in the 2d hierarcy. Possibly I don't understand the
>> layout.
>
> A request is only on one list (queue, active, hold). But we may still
> have more than one request at the same deadline, though that will likely
> be limited to priority-inheritance and timeslice deferrals.
>
> Since we would need pointer to the request, we could only reclaim a
> single pointer here, which is not enough to warrant reducing the overall
> node size. And while there is at least one user of request->sched.link,
> the list maintenance will still be incurred. Using request->sched.link
> remains a convenient interface.
Lost you.
Is the data structure like this and I will limit to priorities for
simplicity:
Level1: [-1]------------->[1]
Level0: [-1]---->[0]----->[1]
[SENTINEL]
Each of the boxes is struct i915_priolist?
Sentinel contains pointers to first i915_priolist for each level. Or
maybe it could contain just a single pointer to highest level (most
sparse) list.
And then each box is i915_priolist, single linked to next, in order.
But it should also have a single pointer for down, or up (or both)? I
don't understand why you have up to "max levels" pointers in each.
And each box should then contain a pointer to a list of requests. I
cannot each have it's own list since there are duplicates.
But obviously I am understanding something way wrong.
>
>>
>>> - struct rb_node node;
>>> int priority;
>>> +
>>> + int level;
>>> + struct i915_priolist *next[I915_PRIOLIST_HEIGHT];
>>
>> Does every node need maximum height or you could allocated depending on
>> current height?
>
> Every slab allocation here is a power of 2, so there are only a few
> different options that are worthwhile (on 64b the only other choice is
> [4], unless you want to go larger to [28]). It did not feel like enough
> benefit to justify the extra code.
>
>>> -static void assert_priolists(struct i915_sched_engine * const se)
>>> -{
>>> - struct rb_node *rb;
>>> - long last_prio;
>>> -
>>> - if (!IS_ENABLED(CONFIG_DRM_I915_DEBUG_GEM))
>>> - return;
>>> -
>>> - GEM_BUG_ON(rb_first_cached(&se->queue) !=
>>> - rb_first(&se->queue.rb_root));
>>> -
>>> - last_prio = INT_MAX;
>>> - for (rb = rb_first_cached(&se->queue); rb; rb = rb_next(rb)) {
>>> - const struct i915_priolist *p = to_priolist(rb);
>>> -
>>> - GEM_BUG_ON(p->priority > last_prio);
>>> - last_prio = p->priority;
>>> - }
>>> + root->prng = next_pseudo_random32(root->prng);
>>> + return __ffs(root->prng) / 2;
>>
>> Where is the relationship to I915_PRIOLIST_HEIGHT? Feels root->prng %
>> I915_PRIOLIST_HEIGHT would be more obvious here unless I am terribly
>> mistaken. Or at least put a comment saying why the hack.
>
> HEIGHT is the maximum possible for our struct. skiplists only want to
> increment the height of the tree one step at a time. So we choose a level
> with decreasing probability, and then limit that to the maximum height of
> the current tree + 1, clamped to HEIGHT.
>
> You might notice that unlike traditional skiplists, this uses a
That's optimistic, that I would notice that. I'll stick to the basics
for now. :)
Regards,
Tvrtko
> probability of 0.25 for each additional level. A neat trick discovered by
> Con Kolivas (I haven't found it mentioned elsewhere) as the cost of the
> extra level (using P=.5) is the same as the extra chain length with
> P=.25. So you can scale to higher number of requests by packing more
> requests into each level.
>
> So that is split between randomly choosing a level and then working out
> the height of the node.
>
>>> static struct list_head *
>>> lookup_priolist(struct intel_engine_cs *engine, int prio)
>>> {
>>> + struct i915_priolist *update[I915_PRIOLIST_HEIGHT];
>>> struct i915_sched_engine * const se = &engine->active;
>>> - struct i915_priolist *p;
>>> - struct rb_node **parent, *rb;
>>> - bool first = true;
>>> -
>>> - lockdep_assert_held(&engine->active.lock);
>>> - assert_priolists(se);
>>> + struct i915_priolist_root *root = &se->queue;
>>> + struct i915_priolist *pl, *tmp;
>>> + int lvl;
>>>
>>> + lockdep_assert_held(&se->lock);
>>> if (unlikely(se->no_priolist))
>>> prio = I915_PRIORITY_NORMAL;
>>>
>>> + for_each_priolist(pl, root) { /* recycle any empty elements before us */
>>> + if (pl->priority >= prio || !list_empty(&pl->requests))
>>> + break;
>>> +
>>> + i915_priolist_advance(root, pl);
>>> + }
>>> +
>>> find_priolist:
>>> - /* most positive priority is scheduled first, equal priorities fifo */
>>> - rb = NULL;
>>> - parent = &se->queue.rb_root.rb_node;
>>> - while (*parent) {
>>> - rb = *parent;
>>> - p = to_priolist(rb);
>>> - if (prio > p->priority) {
>>> - parent = &rb->rb_left;
>>> - } else if (prio < p->priority) {
>>> - parent = &rb->rb_right;
>>> - first = false;
>>> - } else {
>>> - return &p->requests;
>>> - }
>>> + pl = &root->sentinel;
>>> + lvl = pl->level;
>>> + while (lvl >= 0) {
>>> + while (tmp = pl->next[lvl], tmp->priority >= prio)
>>> + pl = tmp;
>>> + if (pl->priority == prio)
>>> + goto out;
>>> + update[lvl--] = pl;
>>> }
>>>
>>> if (prio == I915_PRIORITY_NORMAL) {
>>> - p = &se->default_priolist;
>>> + pl = &se->default_priolist;
>>> + } else if (!pl_empty(&root->sentinel.requests)) {
>>> + pl = pl_pop(&root->sentinel.requests);
>>> } else {
>>> - p = kmem_cache_alloc(global.slab_priorities, GFP_ATOMIC);
>>> + pl = kmem_cache_alloc(global.slab_priorities, GFP_ATOMIC);
>>> /* Convert an allocation failure to a priority bump */
>>> - if (unlikely(!p)) {
>>> + if (unlikely(!pl)) {
>>> prio = I915_PRIORITY_NORMAL; /* recurses just once */
>>>
>>> - /* To maintain ordering with all rendering, after an
>>> + /*
>>> + * To maintain ordering with all rendering, after an
>>> * allocation failure we have to disable all scheduling.
>>> * Requests will then be executed in fifo, and schedule
>>> * will ensure that dependencies are emitted in fifo.
>>> @@ -260,18 +304,103 @@ lookup_priolist(struct intel_engine_cs *engine, int prio)
>>> }
>>> }
>>>
>>> - p->priority = prio;
>>> - INIT_LIST_HEAD(&p->requests);
>>> + pl->priority = prio;
>>> + INIT_LIST_HEAD(&pl->requests);
>>>
>>> - rb_link_node(&p->node, rb, parent);
>>> - rb_insert_color_cached(&p->node, &se->queue, first);
>>> + lvl = random_level(root);
>>> + if (lvl > root->sentinel.level) {
>>> + if (root->sentinel.level < I915_PRIOLIST_HEIGHT - 1) {
>>> + lvl = ++root->sentinel.level;
>>
>> root->sentinel.level is maximum currently populated height? So if
>> random_level said insert at 4 but there are currently only 2 levels,
>> height will grow by one only?
>
> Yes. The idea is keep the number of next[] as small as possible for the
> number of nodes in the tree. (Since the height of the tree is the
> constant overhead in list traversal.)
>
>>> + update[lvl] = &root->sentinel;
>>> + } else {
>>> + lvl = I915_PRIOLIST_HEIGHT - 1;
>>
>> But if maximum level already has been reached then this branch does not
>> set anything to update[],
>
> at the next level.
>
>> relying on the while loop earlier in the
>> function has populated it? How should I think of the update array?
>
> The update[] is the array of nodes just before the position we need to
> insert. So update[] needs only be the height of the tree at that time,
> and if we decide to grow the tree, update[height] will be the root node,
> as we will be the first in that level.
> -Chris
>
_______________________________________________
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/intel-gfx
next prev parent reply other threads:[~2021-01-28 16:42 UTC|newest]
Thread overview: 90+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-01-25 14:00 [Intel-gfx] [PATCH 01/41] drm/i915/selftests: Check for engine-reset errors in the middle of workarounds Chris Wilson
2021-01-25 14:00 ` [Intel-gfx] [PATCH 02/41] drm/i915/gt: Move the defer_request waiter active assertion Chris Wilson
2021-01-25 14:53 ` Tvrtko Ursulin
2021-01-25 14:00 ` [Intel-gfx] [PATCH 03/41] drm/i915: Replace engine->schedule() with a known request operation Chris Wilson
2021-01-25 15:14 ` Tvrtko Ursulin
2021-01-25 14:00 ` [Intel-gfx] [PATCH 04/41] drm/i915: Teach the i915_dependency to use a double-lock Chris Wilson
2021-01-25 15:34 ` Tvrtko Ursulin
2021-01-25 21:37 ` Chris Wilson
2021-01-26 9:40 ` Tvrtko Ursulin
2021-01-25 14:01 ` [Intel-gfx] [PATCH 05/41] drm/i915: Restructure priority inheritance Chris Wilson
2021-01-26 11:12 ` Tvrtko Ursulin
2021-01-26 11:30 ` Chris Wilson
2021-01-26 11:40 ` Tvrtko Ursulin
2021-01-26 11:55 ` Chris Wilson
2021-01-26 13:15 ` Tvrtko Ursulin
2021-01-26 13:24 ` Chris Wilson
2021-01-26 13:45 ` Chris Wilson
2021-01-25 14:01 ` [Intel-gfx] [PATCH 06/41] drm/i915/selftests: Measure set-priority duration Chris Wilson
2021-01-25 14:01 ` [Intel-gfx] [PATCH 07/41] drm/i915/selftests: Exercise priority inheritance around an engine loop Chris Wilson
2021-01-25 14:01 ` [Intel-gfx] [PATCH 08/41] drm/i915: Improve DFS for priority inheritance Chris Wilson
2021-01-26 16:22 ` Tvrtko Ursulin
2021-01-26 16:26 ` Chris Wilson
2021-01-26 16:42 ` Tvrtko Ursulin
2021-01-26 16:51 ` Tvrtko Ursulin
2021-01-26 16:51 ` Chris Wilson
2021-01-25 14:01 ` [Intel-gfx] [PATCH 09/41] drm/i915/selftests: Exercise relative mmio paths to non-privileged registers Chris Wilson
2021-01-25 14:01 ` [Intel-gfx] [PATCH 10/41] drm/i915/selftests: Exercise cross-process context isolation Chris Wilson
2021-01-25 14:01 ` [Intel-gfx] [PATCH 11/41] drm/i915: Extract request submission from execlists Chris Wilson
2021-01-26 16:28 ` Tvrtko Ursulin
2021-01-25 14:01 ` [Intel-gfx] [PATCH 12/41] drm/i915: Extract request rewinding " Chris Wilson
2021-01-25 14:01 ` [Intel-gfx] [PATCH 13/41] drm/i915: Extract request suspension from the execlists Chris Wilson
2021-01-25 14:01 ` [Intel-gfx] [PATCH 14/41] drm/i915: Extract the ability to defer and rerun a request later Chris Wilson
2021-01-25 14:01 ` [Intel-gfx] [PATCH 15/41] drm/i915: Fix the iterative dfs for defering requests Chris Wilson
2021-01-25 14:01 ` [Intel-gfx] [PATCH 16/41] drm/i915: Move common active lists from engine to i915_scheduler Chris Wilson
2021-01-25 14:01 ` [Intel-gfx] [PATCH 17/41] drm/i915: Move scheduler queue Chris Wilson
2021-01-25 14:01 ` [Intel-gfx] [PATCH 18/41] drm/i915: Move tasklet from execlists to sched Chris Wilson
2021-01-27 14:10 ` Tvrtko Ursulin
2021-01-27 14:24 ` Chris Wilson
2021-01-25 14:01 ` [Intel-gfx] [PATCH 19/41] drm/i915/gt: Show scheduler queues when dumping state Chris Wilson
2021-01-27 14:13 ` Tvrtko Ursulin
2021-01-27 14:35 ` Chris Wilson
2021-01-27 14:50 ` Tvrtko Ursulin
2021-01-27 14:55 ` Chris Wilson
2021-01-25 14:01 ` [Intel-gfx] [PATCH 20/41] drm/i915: Replace priolist rbtree with a skiplist Chris Wilson
2021-01-27 15:10 ` Tvrtko Ursulin
2021-01-27 15:33 ` Chris Wilson
2021-01-27 15:44 ` Chris Wilson
2021-01-27 15:58 ` Tvrtko Ursulin
2021-01-28 9:50 ` Chris Wilson
2021-01-28 15:56 ` Tvrtko Ursulin
2021-01-28 16:26 ` Chris Wilson
2021-01-28 16:42 ` Tvrtko Ursulin [this message]
2021-01-28 22:20 ` Chris Wilson
2021-01-28 22:44 ` Chris Wilson
2021-01-29 9:24 ` Tvrtko Ursulin
2021-01-29 9:37 ` Tvrtko Ursulin
2021-01-29 10:26 ` Chris Wilson
2021-01-28 22:56 ` Matthew Brost
2021-01-29 10:30 ` Chris Wilson
2021-01-29 17:01 ` Matthew Brost
2021-01-29 10:22 ` Tvrtko Ursulin
2021-01-25 14:01 ` [Intel-gfx] [PATCH 21/41] drm/i915: Wrap cmpxchg64 with try_cmpxchg64() helper Chris Wilson
2021-01-27 15:28 ` Tvrtko Ursulin
2021-01-25 14:01 ` [Intel-gfx] [PATCH 22/41] drm/i915: Fair low-latency scheduling Chris Wilson
2021-01-28 11:35 ` Tvrtko Ursulin
2021-01-28 12:32 ` Chris Wilson
2021-01-25 14:01 ` [Intel-gfx] [PATCH 23/41] drm/i915/gt: Specify a deadline for the heartbeat Chris Wilson
2021-01-25 14:01 ` [Intel-gfx] [PATCH 24/41] drm/i915: Extend the priority boosting for the display with a deadline Chris Wilson
2021-01-25 14:01 ` [Intel-gfx] [PATCH 25/41] drm/i915/gt: Support virtual engine queues Chris Wilson
2021-01-25 14:01 ` [Intel-gfx] [PATCH 26/41] drm/i915: Move saturated workload detection back to the context Chris Wilson
2021-01-25 14:01 ` [Intel-gfx] [PATCH 27/41] drm/i915: Bump default timeslicing quantum to 5ms Chris Wilson
2021-01-25 14:01 ` [Intel-gfx] [PATCH 28/41] drm/i915/gt: Wrap intel_timeline.has_initial_breadcrumb Chris Wilson
2021-01-25 14:01 ` [Intel-gfx] [PATCH 29/41] drm/i915/gt: Track timeline GGTT offset separately from subpage offset Chris Wilson
2021-01-25 14:01 ` [Intel-gfx] [PATCH 30/41] drm/i915/gt: Add timeline "mode" Chris Wilson
2021-01-25 14:01 ` [Intel-gfx] [PATCH 31/41] drm/i915/gt: Use indices for writing into relative timelines Chris Wilson
2021-01-25 14:01 ` [Intel-gfx] [PATCH 32/41] drm/i915/selftests: Exercise relative timeline modes Chris Wilson
2021-01-25 14:01 ` [Intel-gfx] [PATCH 33/41] drm/i915/gt: Use ppHWSP for unshared non-semaphore related timelines Chris Wilson
2021-01-25 14:01 ` [Intel-gfx] [PATCH 34/41] Restore "drm/i915: drop engine_pin/unpin_breadcrumbs_irq" Chris Wilson
2021-01-25 14:01 ` [Intel-gfx] [PATCH 35/41] drm/i915/gt: Couple tasklet scheduling for all CS interrupts Chris Wilson
2021-01-25 14:01 ` [Intel-gfx] [PATCH 36/41] drm/i915/gt: Support creation of 'internal' rings Chris Wilson
2021-01-25 14:01 ` [Intel-gfx] [PATCH 37/41] drm/i915/gt: Use client timeline address for seqno writes Chris Wilson
2021-01-25 14:01 ` [Intel-gfx] [PATCH 38/41] drm/i915/gt: Infrastructure for ring scheduling Chris Wilson
2021-01-25 14:01 ` [Intel-gfx] [PATCH 39/41] drm/i915/gt: Implement ring scheduler for gen4-7 Chris Wilson
2021-01-25 14:01 ` [Intel-gfx] [PATCH 40/41] drm/i915/gt: Enable ring scheduling for gen5-7 Chris Wilson
2021-01-25 14:01 ` [Intel-gfx] [PATCH 41/41] drm/i915: Support secure dispatch on gen6/gen7 Chris Wilson
2021-01-25 14:40 ` [Intel-gfx] [PATCH 01/41] drm/i915/selftests: Check for engine-reset errors in the middle of workarounds Tvrtko Ursulin
2021-01-25 17:08 ` [Intel-gfx] ✗ Fi.CI.CHECKPATCH: warning for series starting with [01/41] " Patchwork
2021-01-25 17:10 ` [Intel-gfx] ✗ Fi.CI.SPARSE: " Patchwork
2021-01-25 17:38 ` [Intel-gfx] ✓ Fi.CI.BAT: success " Patchwork
2021-01-25 22:45 ` [Intel-gfx] ✗ Fi.CI.IGT: failure " Patchwork
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=f4f42b32-d536-6f2f-0118-be7fedcd94db@linux.intel.com \
--to=tvrtko.ursulin@linux.intel.com \
--cc=chris@chris-wilson.co.uk \
--cc=intel-gfx@lists.freedesktop.org \
--cc=thomas.hellstrom@intel.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).