commit 2302d74cf76225326c4a5cba08957f1868b75386
author Scott Haseley <shaseley@chromium.org> Fri Dec 03 23:19:23 2021
committer Chromium LUCI CQ <chromium-scoped@luci-project-accounts.iam.gserviceaccount.com> Fri Dec 03 23:19:23 2021
tree 437be34e12d2284aa837d92cb6370028706f3462
parent 8c49996aab9832898a52c867b79d63afbe326ece

SequenceManager: Introduce TaskOrder as on ordering on ready tasks

This CL fixes an ordering issue where ready delayed tasks with the same
priority might not be ordered by delayed run time across tasks queues.
This could happen as a result how we assign EnqueueOrders during
wake-ups. We previously fixed this by sorting ready delayed tasks by
delayed run time across task queues prior to assigning their
EnqueueOrder (crrev.com/c/3213629), but reverted the change due TaskOrder
performance overhead. This CL attempts to achieve the same result more
efficiently.

To achieve the desired ordering for delayed tasks, this CL introduces a
new abstraction, TaskOrder, which replaces EnqueueOrder as the key in
in WorkQueueSets. TaskOrder is a 3-tuple of (enqueue order, delayed run
time, and sequence number (posting order)), which can be obtained from
a task via `task.task_order()`. TaskOrder has the following properties:

 1. task1.enqueue_order() < task2.enqueue_order() =>
    task1.task_order() < task2.task_order().

 2. If task1.enqueue_order() == task2.enqueue_order(), then
    task1.task_order() < task2.task_order() iff task1 < task2 (i.e.
    by comparing delayed_run_time and sequence_num in the same way
    we do for PendingTasks).

All ready delayed tasks enqueued during a wake-up are assigned the same
EnqueueOrder, so ordering between then is decided by their delayed run
times and sequence numbers.

This CL also changes fences to use TaskOrder instead of EnqueueOrder.
For delayed fences activated during wake-ups, we previously would use a
unique enqueue order within the range of enqueue orders assigned to
ready delayed tasks during a wake-up. But since all such tasks now use
the same enqueue order, this is no longer possible. Instead, we use the
TaskOrder corresponding to first delayed task past the delayed fence.
We also create a Fence subclass of TaskOrder with functionality for
blocking fences to separate it from TaskOrder.

This also adds unit tests for TaskOrder as well as new test cases for
WorkQueueSets and WorkQueue.

Bug: 1249857
Change-Id: I1a0d57e3bbf75c7d371d67509710bcd19d7df306
Reviewed-on: https://chromium-review.googlesource.com/c/chromium/src/+/3290327
Commit-Queue: Scott Haseley <shaseley@chromium.org>
Reviewed-by: Alexander Timin <altimin@chromium.org>
Reviewed-by: Etienne Pierre-Doray <etiennep@chromium.org>
Cr-Commit-Position: refs/heads/main@{#948220}