Messages in this thread | | | Date | Thu, 12 Oct 2023 18:04:17 +0800 | Subject | Re: Re: [PATCH] sched/fair: fix pick_eevdf to always find the correct se | From | Abel Wu <> |
| |
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
| |