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

[Abel Wu <wuyun.abel@bytedance.com>]

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