Re: [PATCH 09/31] drm/i915: Replace priolist rbtree with a skiplist

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 




On 08/02/2021 12:46, Chris Wilson wrote:
Quoting Tvrtko Ursulin (2021-02-08 12:29:14)

On 08/02/2021 10:52, Chris Wilson wrote:
+static void remove_from_priolist(struct i915_sched *se,
+                              struct i915_request *rq,
+                              struct list_head *list,
+                              bool tail)
+{
+     struct list_head *prev = rq->sched.link.prev;

This depends on rq being at the head of it's list?

Not depends. We are testing if the list is singular, that is by removing
this request from the i915_priolist.requests that list becomes empty,
and so the i915_priolist can be removed from the skiplist.

Ah so obvious now, thanks.


+
+     GEM_BUG_ON(!i915_request_in_priority_queue(rq));
+
+     __list_del_entry(&rq->sched.link);
+     if (tail)
+             list_add_tail(&rq->sched.link, list);
+     else
+             list_add(&rq->sched.link, list);

So it is more move than remove(_from_priolist) ?

Yes, we can quite happily just keep the list_move(), except we then end
up with lots of empty levels. At first I thought the walk through those
(during dequeue) would be cheaper than removing. The max lock holdtime
strongly favours the removal as we move requests around (which will
happen in dribs-and-drabs) over doing a bulk remove at dequeue.

Give it a name to reflect it is a move like move_to_priolist?


+     /* If we just removed the last element in the old plist, delete it */
+     if (list_empty(prev))
+             __remove_priolist(se, prev);
+}
+
+struct i915_priolist *__i915_sched_dequeue_next(struct i915_sched *se)
+{
+     struct i915_priolist * const s = &se->queue.sentinel;
+     struct i915_priolist *pl = s->next[0];
+     int lvl;
+
+     GEM_BUG_ON(!list_empty(&pl->requests));

Lost as to why pl->requests has to be empty at this point. Considering:

+#define i915_sched_dequeue(se, pl, rq, rn) \
+       for ((pl) = (se)->queue.sentinel.next[0]; \
+            (pl) != &(se)->queue.sentinel; \
+            (pl) = __i915_sched_dequeue_next(se)) \
+               priolist_for_each_request_safe(rq, rn, pl)
+

I also don't understand what it would de-queue. Whole priolist woth of
requests at a time? But it can't be empty to dequeue something. And who
puts any unconsumed requests back on somewhere in this case.

It's a double for-loop. I think the flattening of the logic is worth it.

During dequeue, we always move the very first request onto the next list
(i.e. i915_sched.active). Then when we have finished with all the
requests in one priority level, we move onto the next i915_priolist
(calling __i915_sched_dequeue_next).

So in __i915_sched_dequeue_next, we are always dealing with an empty
i915_priolist and want to advance the start of the skiplist to the next.

Ah yes, __i915_sched_dequeue_next is only if there isn't a "goto done" from within the inner loop (priolist_for_each_request_safe). Well it's a bit fragile if someone does a break one day. But I guess bug on will be hit then so it's okay.

Right, I have some more questions for which I'll start a new sub-thread.

Regards,

Tvrtko


I was thinking that in order to hide the double for-loop, we could
handle the non-empty i915_priolist case causing it to break out of the
outer loop. So we could get rid of the goto done.
-Chris

_______________________________________________
Intel-gfx mailing list
Intel-gfx@xxxxxxxxxxxxxxxxxxxxx
https://lists.freedesktop.org/mailman/listinfo/intel-gfx



[Index of Archives]     [AMD Graphics]     [Linux USB Devel]     [Linux Audio Users]     [Yosemite News]     [Linux Kernel]     [Linux SCSI]

  Powered by Linux