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

[Chris Wilson]

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:
> >>> 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.

/*
 * i915_priolist forms a skiplist. The skiplist is built in layers,
 * starting at the base [0] is a singly linked list of all i915_priolist.
 * Each higher layer contains a fraction of the i915_priolist from the
 * previous layer:
 *
 * S[0] 0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF S
 * E[1] >1>3>5>7>9>B>D>F>1>3>5>7>9>B>D>F>1>3>5>7>9>B>D>F>1>3>5>7>9>B>D>F E
 * N[2] -->3-->7-->B-->F-->3-->7-->B-->F-->3-->7-->B-->F-->3-->7-->B-->F N
 * T[3] ------->7----->F-------7------>F------>7------>F------>7------>F T
 * I[4] -------------->F-------------->F-------------->F-------------->F I
 * N[5] ------------------------------>F------------------------------>F N
 * E[6] ------------------------------>F-------------------------------> E
 * L[7] ---------------------------------------------------------------> L
 *
 * To iterate through all active i915_priolist, we only need to follow
 * the chain in i915_priolist.next[0] (see for_each_priolist).
 *
 * To quickly find a specific key (or insert point), we can perform a binary
 * search by starting at the highest level and following the linked list
 * at that level until we either find the node, or have gone passed the key.
 * Then we descend a level, and start walking the list again starting from
 * the current position, until eventually we find our key, or we run out of
 * levels.
 */
-Chris