Quoting Tvrtko Ursulin (2021-01-28 16:42:44)
>
> 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:
> >>> 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?
Although each level is circular.
1: SENTINEL -> [-1] --------> [1] -> SENTINEL
0: SENTINEL -> [-1] -> [0] -> [1] -> SENTINEL
Ah. I think I see the cause of confusion here. Each column, not each
box, is a i915_priolist.
So the skiplist is really a set of [HEIGHT] singly linked lists, with
each list containing a sorted subset of the whole. And each descending
level includes every member from the level above, until we reach a
linked list of all i915_priolist in [0].
[skip, hopefully I caught the central point]
SENTINEL[2] is a list of all i915_priolist of level >= 2
SENTINEL[1] is a list of all i915_priolist of level >= 1
SENTINEL[0] is a list of all i915_priolist.
As we randomly assign i915_priolist.level, SENTINEL[1] should have half
the elements of SENTINEL[0], and SENTINEL[2] should have half again the
elements of SENTINEL[1] (hence its ability to do a binary/lgN search for
a key, each level is a bisection of the last).
-Chris
_______________________________________________
Intel-gfx mailing list
Intel-gfx@xxxxxxxxxxxxxxxxxxxxx
https://lists.freedesktop.org/mailman/listinfo/intel-gfx
