[Intel-gfx] [PATCH 09/31] drm/i915: Replace priolist rbtree with a skiplist

[Tvrtko Ursulin]

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
>