linux-kernel - Re: Re: [PATCH] sched/fair: fix pick_eevdf to always find the correct se

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <99cabaee-df77-4da4-9521-3877a507ba48@bytedance.com>
Date:   Thu, 12 Oct 2023 18:04:17 +0800
From:   Abel Wu <wuyun.abel@...edance.com>
To:     Peter Zijlstra <peterz@...radead.org>
Cc:     Benjamin Segall <bsegall@...gle.com>, mingo@...nel.org,
        vincent.guittot@...aro.org, linux-kernel@...r.kernel.org,
        juri.lelli@...hat.com, dietmar.eggemann@....com,
        rostedt@...dmis.org, mgorman@...e.de, bristot@...hat.com,
        corbet@....net, qyousef@...alina.io, chris.hyser@...cle.com,
        patrick.bellasi@...bug.net, pjt@...gle.com, pavel@....cz,
        qperret@...gle.com, tim.c.chen@...ux.intel.com, joshdon@...gle.com,
        timj@....org, kprateek.nayak@....com, yu.c.chen@...el.com,
        youssefesmat@...omium.org, joel@...lfernandes.org, efault@....de,
        tglx@...utronix.de
Subject: Re: Re: [PATCH] sched/fair: fix pick_eevdf to always find the correct
 se

On 10/11/23 9:14 PM, Peter Zijlstra Wrote:
> On Wed, Oct 11, 2023 at 08:12:09PM +0800, Abel Wu wrote:
> 
> As the paper explains, you get two walks, one down the eligibility path,
> and then one down the heap. I think the current code structure
> represents that fairly well.

Yes, it does. I just wonder if the 2-step search is necessary, since
they obey the same rule of heap search:

   1) node->min_deadline > node->left->min_deadline
	1.1) BUG

   2) node->min_deadline = node->left->min_deadline
	2.1) go left if tiebreak on vruntime

   3) node->min_deadline < node->left->min_deadline
	3.1) return @node if it has min deadline, or
	3.2) go right

which gives:

	while (node) {
		if ((left = node->left)) {
			/* 1.1 */
			BUG_ON(left->min < node->min);

			/* 2.1 */
			if (left->min == node->min) {
				node = left;
				continue;
			}
		}

		/* 3.1 */
		if (node->deadline == node->min)
			return node;

		/* 3.2 */
		node = node->right;
	}

The above returns the entity with ealiest deadline (and with smallest
vruntime if have same deadline). Then comes with eligibility:

   0) it helps pruning the tree since the right subtree of a
      non-eligible node can't contain any eligible node.

   3.2.1) record left as a fallback iff the eligibility check
          is active, and saving the best one is enough since
          none of them contain non-eligible node, IOW the one
          with min deadline in the left tree must be eligible.

   4) the eligibility check ends immediately once go left from
      an eligible node, including switch to the fallback which
      is essentially is the 'left' of an eligible node.

   5) fallback to the candidate (if exists) if failed to find
      an eligible entity with earliest deadline.

which makes:

	candidate = NULL;
	need_check = true;

	while (node) {
		/* 0 */
		if (need_check && !eligible(node)) {
			node = node->left;
			goto next;
		}

		if ((left = node->left)) {
			/* 1.1 */
			BUG_ON(left->min < node->min);

			/* 2.1 */
			if (left->min == node->min) {
				node = left;
				/* 4 */
				need_check = false;
				continue;
			}

			/* 3.2.1 */
			if (need_check)
				candidate = better(candidate, left);
		}

		/* 3.1 */
		if (node->deadline == node->min)
			return node;

		/* 3.2 */
		node = node->right;
	next:
		/* 5 */
		if (!node && candidate) {
			node = candidate;
			need_check = false; /* 4 */
			candidate = NULL;
		}
	}

The search ends with a 'best' entity on the tree, comparing it with
curr which is out of tree makes things a whole.

But it's absolutely fine to me to honor the 2-step search given by
the paper if you think that is already clear enough :)

Best,
	Abel