[Intel-gfx] [PATCH v3 08/14] drm/i915/scheduler: Execute requests in order of priorities

[Chris Wilson]

On Mon, Nov 14, 2016 at 11:48:32AM +0000, Tvrtko Ursulin wrote:
> 
> On 14/11/2016 11:41, Chris Wilson wrote:
> >On Mon, Nov 14, 2016 at 11:15:52AM +0000, Tvrtko Ursulin wrote:
> >>On 14/11/2016 08:56, Chris Wilson wrote:
> >>>+static void execlists_schedule(struct drm_i915_gem_request *request, int prio)
> >>>+{
> >>>+	struct intel_engine_cs *engine = NULL;
> >>>+	struct i915_dependency *dep, *p;
> >>>+	struct i915_dependency stack;
> >>>+	LIST_HEAD(dfs);
> >>>+
> >>>+	if (prio <= READ_ONCE(request->priotree.priority))
> >>>+		return;
> >>>+
> >>>+	/* Need BKL in order to use the temporary link inside i915_dependency */
> >>>+	lockdep_assert_held(&request->i915->drm.struct_mutex);
> >>>+
> >>>+	stack.signaler = &request->priotree;
> >>>+	list_add(&stack.dfs_link, &dfs);
> >>>+
> >>>+	/* Recursively bump all dependent priorities to match the new request */
> >>
> >>Missed last time round that the comment needs updating.
> >
> >It still is a recursive design though, just flat. That one word was
> >saving a paragraph :|
> >
> >I think the easiest way to describe what the code is doing here is to
> >show the recursive version in the comment and then hope for inspiration
> >in describing how that maps onto the search list.
> 
> I can see that angle yes. Maybe the just add a second sentence
> saying something like "To avoid having recursive code to do this
> recursive update we build a flat list of dependencies in a depth
> first search manner."?

        /* Recursively bump all dependent priorities to match the new request.
         *
         * A naive approach would be to use recursion:
         * static void update_priorities(struct i915_priotree *pt, prio) {
         *      list_for_each_entry(dep, &pt->signalers_list, signal_link )
         *              update_priorities(dep->signal, prio)
         *      insert_request(pt);
         * }
         * but that may have unlimited recursion depth and so runs a very
         * real risk of overunning the kernel stack. Instead, we build
         * a flat list of all dependencies starting with the current request.
         * As we walk the list of dependencies, we add all of its dependencies
         * to the end of the list (this may include an already visited
         * request) and continue to walk onwards onto the new dependencies. The
         * end result is a topological list of requests in reverse order, the
         * last element in the list is the request we must execute first.
         */

-- 
Chris Wilson, Intel Open Source Technology Centre