Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.33 as permitted sender) client-ip=23.128.96.33;
From:   Benjamin Segall <bsegall@google.com>
To:     Peter Zijlstra <peterz@infradead.org>
Cc:     mingo@kernel.org, vincent.guittot@linaro.org,
        linux-kernel@vger.kernel.org, juri.lelli@redhat.com,
        dietmar.eggemann@arm.com, rostedt@goodmis.org, mgorman@suse.de,
        bristot@redhat.com, corbet@lwn.net, qyousef@layalina.io,
        chris.hyser@oracle.com, patrick.bellasi@matbug.net, pjt@google.com,
        pavel@ucw.cz, qperret@google.com, tim.c.chen@linux.intel.com,
        joshdon@google.com, timj@gnu.org, kprateek.nayak@amd.com,
        yu.c.chen@intel.com, youssefesmat@chromium.org,
        joel@joelfernandes.org, efault@gmx.de, tglx@linutronix.de
Subject: Re: [PATCH 05/15] sched/fair: Implement an EEVDF like policy
In-Reply-To: <20230531124603.931005524@infradead.org> (Peter Zijlstra's
        message of "Wed, 31 May 2023 13:58:44 +0200")
References: <20230531115839.089944915@infradead.org>
        <20230531124603.931005524@infradead.org>
User-Agent: Gnus/5.13 (Gnus v5.13)
Date:   Fri, 29 Sep 2023 14:40:31 -0700
Message-ID: <xm265y3sodyo.fsf@google.com>
MIME-Version: 1.0
Content-Type: text/plain
Precedence: bulk

Peter Zijlstra <peterz@infradead.org> writes:

> +
> +/*
> + * Earliest Eligible Virtual Deadline First
> + *
> + * In order to provide latency guarantees for different request sizes
> + * EEVDF selects the best runnable task from two criteria:
> + *
> + *  1) the task must be eligible (must be owed service)
> + *
> + *  2) from those tasks that meet 1), we select the one
> + *     with the earliest virtual deadline.
> + *
> + * We can do this in O(log n) time due to an augmented RB-tree. The
> + * tree keeps the entries sorted on service, but also functions as a
> + * heap based on the deadline by keeping:
> + *
> + *  se->min_deadline = min(se->deadline, se->{left,right}->min_deadline)
> + *
> + * Which allows an EDF like search on (sub)trees.
> + */
> +static struct sched_entity *pick_eevdf(struct cfs_rq *cfs_rq)
> +{
> +	struct rb_node *node = cfs_rq->tasks_timeline.rb_root.rb_node;
> +	struct sched_entity *curr = cfs_rq->curr;
> +	struct sched_entity *best = NULL;
> +
> +	if (curr && (!curr->on_rq || !entity_eligible(cfs_rq, curr)))
> +		curr = NULL;
> +
> +	while (node) {
> +		struct sched_entity *se = __node_2_se(node);
> +
> +		/*
> +		 * If this entity is not eligible, try the left subtree.
> +		 */
> +		if (!entity_eligible(cfs_rq, se)) {
> +			node = node->rb_left;
> +			continue;
> +		}
> +
> +		/*
> +		 * If this entity has an earlier deadline than the previous
> +		 * best, take this one. If it also has the earliest deadline
> +		 * of its subtree, we're done.
> +		 */
> +		if (!best || deadline_gt(deadline, best, se)) {
> +			best = se;
> +			if (best->deadline == best->min_deadline)
> +				break;
> +		}
> +
> +		/*
> +		 * If the earlest deadline in this subtree is in the fully
> +		 * eligible left half of our space, go there.
> +		 */
> +		if (node->rb_left &&
> +		    __node_2_se(node->rb_left)->min_deadline == se->min_deadline) {
> +			node = node->rb_left;
> +			continue;
> +		}
> +
> +		node = node->rb_right;
> +	}

I believe that this can fail to actually find the earliest eligible
deadline, because the earliest deadline (min_deadline) can be in the
right branch, but that se isn't eligible, and the actual target se is in
the left branch. A trivial 3-se example with the nodes represented by
(vruntime, deadline, min_deadline):

   (5,9,7)
 /        \
(4,8,8)  (6,7,7)

AIUI, here the EEVDF pick should be (4,8,8), but pick_eevdf() will
instead pick (5,9,7), because it goes into the right branch and then
fails eligibility.

I'm not sure how much of a problem this is in practice, either in
frequency or severity, but it probably should be mentioned if it's
an intentional tradeoff.


Thinking out loud, I think that it would be sufficient to recheck via something like

for_each_sched_entity(best) {
	check __node_2_se(best->rb_left)->min_deadline, store in actual_best
}

for the best min_deadline, and then go do a heap lookup in actual_best
to find the se matching that min_deadline.

I think this pass could then be combined with our initial descent for
better cache behavior by keeping track of the best rb_left->min_deadline
each time we take a right branch. We still have to look at up to ~2x the
nodes, but I don't think that's avoidable? I'll expand my quick hack I
used to test my simple case into a something of a stress tester and try
some implementations.