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

[Chris Wilson]

Quoting Tvrtko Ursulin (2021-02-08 15:23:17)
> 
> On 08/02/2021 10:52, Chris Wilson wrote:
> >   static struct list_head *
> >   lookup_priolist(struct i915_sched *se, int prio)
> >   {
> > -     struct i915_priolist *p;
> > -     struct rb_node **parent, *rb;
> > -     bool first = true;
> > +     struct i915_priolist *update[I915_PRIOLIST_HEIGHT];
> > +     struct i915_priolist_root *const root = &se->queue;
> > +     struct i915_priolist *pl, *tmp;
> > +     int lvl;
> >   
> >       lockdep_assert_held(&se->lock);
> > -     assert_priolists(se);
> > -
> >       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;
> 
> This less part of the less-or-equal condition keeps confusing me as a 
> break criteria. If premise is cleaning up, why break on first smaller 
> prio? Would the idea be to prune all empty lists up to, not including, 
> the lookup prio?

Just parcelling up the work. If we tidy up all the unused nodes before
us, we insert ourselves at the head of the tree, and all the cheap
checks to see if this is the first request, or to find the first
request are happy.

It's not expected to find anything unused with the tweaks to tidy up
empty elements as we move between i915_priolist.requests, but it seems
sensible to keep as then it should be just checking the first
i915_priolist and breaking out.

> > -void __i915_priolist_free(struct i915_priolist *p)
> > +static void __remove_priolist(struct i915_sched *se, struct list_head *plist)
> >   {
> > -     kmem_cache_free(global.slab_priorities, p);
> > +     struct i915_priolist_root *root = &se->queue;
> > +     struct i915_priolist *pl, *tmp;
> > +     struct i915_priolist *old =
> > +             container_of(plist, struct i915_priolist, requests);
> > +     int prio = old->priority;
> > +     int lvl;
> > +
> > +     lockdep_assert_held(&se->lock);
> > +     GEM_BUG_ON(!list_empty(plist));
> > +
> > +     pl = &root->sentinel;
> > +     lvl = pl->level;
> > +     GEM_BUG_ON(lvl < 0);
> > +
> > +     if (prio != I915_PRIORITY_NORMAL)
> > +             pl_push(old, &pl->requests);
> > +
> > +     do {
> > +             while (tmp = pl->next[lvl], tmp->priority > prio)
> > +                     pl = tmp;
> > +             if (lvl <= old->level) {
> > +                     pl->next[lvl] = old->next[lvl];
> > +                     if (pl == &root->sentinel && old->next[lvl] == pl) {
> > +                             GEM_BUG_ON(pl->level != lvl);
> > +                             pl->level--;
> > +                     }
> > +             }
> > +     } while (--lvl >= 0);
> > +     GEM_BUG_ON(tmp != old);
> > +}

> > +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));
> > +     GEM_BUG_ON(pl == s);
> > +
> > +     /* Keep pl->next[0] valid for for_each_priolist iteration */
> > +     if (pl->priority != I915_PRIORITY_NORMAL)
> > +             pl_push(pl, &s->requests);
> > +
> > +     lvl = pl->level;
> > +     GEM_BUG_ON(lvl < 0);
> > +     do {
> > +             s->next[lvl] = pl->next[lvl];
> > +             if (pl->next[lvl] == s) {
> > +                     GEM_BUG_ON(s->level != lvl);
> > +                     s->level--;
> > +             }
> > +     } while (--lvl >= 0);
> > +
> > +     return pl->next[0];
> >   }
> 
> If both __i915_sched_dequeue_next and __remove_priolist are removing an 
> empty list from the hieararchy, why can't they shared some code?

The __remove_priolist does the general search and remove, whereas
dequeue_next is trying to keep O(1) remove-from-head. dequeue_next is
meant to be called many, many more times than __remove_priolist.
-Chris