Extending the OrderedSimpleTaskRunner unit tests to show ordering issues.

Extending the OrderedSimpleTaskRunner unit tests to show ordering issues.

The OrderedSimpelTaskRunner doesn't understand Now() at all, hence tasks which
are posted with delays can end up executing in weird orders. This effect is
most notable when using PostTask inside a task!

BUG=

[mithro-old, 2014-07-16 14:11:06]

Hi guys,

I was trying to understand how my change to add Now support to
OrderingSimpleTestRunner was breaking things. I eventually tracked down the
issue to the weirdness which is expressed in these unit tests.

The fundamental issue is that if delayed tasks are scheduled inside a task then
you get task order inversion happening.

The re-entrant behaviour was a bit unintuitive (and can also lead to task order
inversion) as the output depends on if tasks have been previously posted.

I think, even if this type of behaviour would be allowable on a normal
TaskRunner is leads to some very unexpected results when trying to do testing.

Tim

[Sami, 2014-07-16 14:36:54]

Looks like TestSimpleTaskRunner just uses 0 as the posting time, which would
explain this. Shall we fix that instead?

https://code.google.com/p/chromium/codesearch#chromium/src/base/test/test_sim...

https://codereview.chromium.org/396063011/diff/1/cc/test/ordered_simple_task_...
File cc/test/ordered_simple_task_runner_unittest.cc (right):

https://codereview.chromium.org/396063011/diff/1/cc/test/ordered_simple_task_...
cc/test/ordered_simple_task_runner_unittest.cc:15:
task_runner_->RunPendingTasks();             \
nit: indent by two more?

[mithro-old, 2014-07-17 03:31:27]

On 2014/07/16 14:36:54, Sami wrote:
> Looks like TestSimpleTaskRunner just uses 0 as the posting time, which would
> explain this. Shall we fix that instead?

That doesn't actually help. Even if posting time was non-zero, RunPendingTasks
will still end up running events which were already scheduled before events
which are scheduled inside RunPendingTasks despite the delay.

I think this points to a number of questions;
 * Should RunPendingTasks handle "instant" tasks differently from "delayed"
tasks?
 * Should RunPendingTasks handle tasks which are already pending at call time
differently from tasks which are scheduled during a RunPendingTask call?

My thoughts are;
 * We want to provide proper ordering of the tasks. Tasks which would occur
earlier on the system normally should occur earlier on this task runner.

 * We should handle instant tasks exactly as delayed tasks with a delay of zero.
This is how the TaskRunner interface is described in the comments in
base/task_runner.h 

 * We should only run tasks which were pending when the RunPendingTask call was
made (if you want to keep running tasks, you can use RunUntilIdle instead). This
allows us to be very exact in knowing what is about to happen. It does have the
side effect that if a new task is scheduled to run *before* an already scheduled
pending task we need to exit RunPendingTasks before completing everything.

If these are acceptable then the versions of EXPECT_EQ I proposed are the
correct behaviour.

Tim

[Sami, 2014-07-17 11:31:35]

On 2014/07/17 03:31:27, mithro(OO till 11 Aug) wrote:
> On 2014/07/16 14:36:54, Sami wrote:
> > Looks like TestSimpleTaskRunner just uses 0 as the posting time, which would
> > explain this. Shall we fix that instead?
> 
> That doesn't actually help. Even if posting time was non-zero, RunPendingTasks
> will still end up running events which were already scheduled before events
> which are scheduled inside RunPendingTasks despite the delay.

Oh I see, is that because of the we make a copy of the pending tasks for
re-entrancy? The contract for OrderedSimpleTaskRunner says "This runs pending
tasks based on task's post_time + delay.", which you've demonstrated to be
false. I still think we should make that class do what it says :)
 
> I think this points to a number of questions;
>  * Should RunPendingTasks handle "instant" tasks differently from "delayed"
> tasks?
>  * Should RunPendingTasks handle tasks which are already pending at call time
> differently from tasks which are scheduled during a RunPendingTask call?

There's also this comment about that:

// We should not execute a delayed task sooner than some of the queued tasks
// which don't have a delay even though it is queued early.

so it seems like instant tasks are special. I hope our code isn't relying on
that though.
 
> My thoughts are;
>  * We want to provide proper ordering of the tasks. Tasks which would occur
> earlier on the system normally should occur earlier on this task runner.
> 
>  * We should handle instant tasks exactly as delayed tasks with a delay of
zero.
> This is how the TaskRunner interface is described in the comments in
> base/task_runner.h 

Right, it might be argued that OrderedSimpleTaskRunner is too simple if it
breaks that contract.
 
>  * We should only run tasks which were pending when the RunPendingTask call
was
> made (if you want to keep running tasks, you can use RunUntilIdle instead).
This
> allows us to be very exact in knowing what is about to happen. It does have
the
> side effect that if a new task is scheduled to run *before* an already
scheduled
> pending task we need to exit RunPendingTasks before completing everything.

I think we should do what TaskRunner does. I *think* it's supposed to do what
you said, but I'm not sure.
 
> If these are acceptable then the versions of EXPECT_EQ I proposed are the
> correct behaviour.
> 
> Tim

[brianderson, 2014-07-18 00:23:16]

Thanks for writing all these tests. I agree with all of the expectations
regarding correct behavior in the comments of each test.

https://codereview.chromium.org/396063011/diff/1/cc/test/ordered_simple_task_...
File cc/test/ordered_simple_task_runner_unittest.cc (right):

https://codereview.chromium.org/396063011/diff/1/cc/test/ordered_simple_task_...
cc/test/ordered_simple_task_runner_unittest.cc:47: void
PostTaskWhichPostsDelayedTask(int task_num,
PostDelayedTaskWhichPostsDelayedTask?

https://codereview.chromium.org/396063011/diff/1/cc/test/ordered_simple_task_...
cc/test/ordered_simple_task_runner_unittest.cc:80: PostTask(-task_num, delay);
Using -task_num is a simple trick to figure out if the task is the second posted
task. It's a little unintuitive at first, but since this is test-only I'm fine
with that.

[mithro-old, 2014-07-18 00:28:04]

Should we try and fix OrderedSimpleTaskRunner without Now functionality? Or
should we just land that change which also makes these tests behave as
expected?


On 18 July 2014 10:23, <brianderson@chromium.org> wrote:

> Thanks for writing all these tests. I agree with all of the expectations
> regarding correct behavior in the comments of each test.
>
>
>
> https://codereview.chromium.org/396063011/diff/1/cc/test/
> ordered_simple_task_runner_unittest.cc
> File cc/test/ordered_simple_task_runner_unittest.cc (right):
>
> https://codereview.chromium.org/396063011/diff/1/cc/test/
> ordered_simple_task_runner_unittest.cc#newcode47
> cc/test/ordered_simple_task_runner_unittest.cc:47: void
> PostTaskWhichPostsDelayedTask(int task_num,
> PostDelayedTaskWhichPostsDelayedTask?
>
> https://codereview.chromium.org/396063011/diff/1/cc/test/
> ordered_simple_task_runner_unittest.cc#newcode80
> cc/test/ordered_simple_task_runner_unittest.cc:80: PostTask(-task_num,
> delay);
> Using -task_num is a simple trick to figure out if the task is the
> second posted task. It's a little unintuitive at first, but since this
> is test-only I'm fine with that.
>
> https://codereview.chromium.org/396063011/
>

To unsubscribe from this group and stop receiving emails from it, send an email
to chromium-reviews+unsubscribe@chromium.org.

[brianderson, 2014-07-18 00:31:52]

On 2014/07/18 00:28:04, mithro(OO till 11 Aug) wrote:
> Should we try and fix OrderedSimpleTaskRunner without Now functionality? Or
> should we just land that change which also makes these tests behave as
> expected?
> 

If it's not too much trouble, please split them up; but I'm fine either way.
They are pretty closely related.

> 
> On 18 July 2014 10:23, <mailto:brianderson@chromium.org> wrote:
> 
> > Thanks for writing all these tests. I agree with all of the expectations
> > regarding correct behavior in the comments of each test.
> >
> >
> >
> > https://codereview.chromium.org/396063011/diff/1/cc/test/
> > ordered_simple_task_runner_unittest.cc
> > File cc/test/ordered_simple_task_runner_unittest.cc (right):
> >
> > https://codereview.chromium.org/396063011/diff/1/cc/test/
> > ordered_simple_task_runner_unittest.cc#newcode47
> > cc/test/ordered_simple_task_runner_unittest.cc:47: void
> > PostTaskWhichPostsDelayedTask(int task_num,
> > PostDelayedTaskWhichPostsDelayedTask?
> >
> > https://codereview.chromium.org/396063011/diff/1/cc/test/
> > ordered_simple_task_runner_unittest.cc#newcode80
> > cc/test/ordered_simple_task_runner_unittest.cc:80: PostTask(-task_num,
> > delay);
> > Using -task_num is a simple trick to figure out if the task is the
> > second posted task. It's a little unintuitive at first, but since this
> > is test-only I'm fine with that.
> >
> > https://codereview.chromium.org/396063011/
> >
> 
> To unsubscribe from this group and stop receiving emails from it, send an
email
> to mailto:chromium-reviews+unsubscribe@chromium.org.

[mithro-old, 2014-07-18 00:46:35]

I'll give it a go. Sami, do you agree with Brian that the system should
operate as the way my commented expectations show? I have a real world
example that I can show if anyone wants.

Tim


On 18 July 2014 10:31, <brianderson@chromium.org> wrote:

> On 2014/07/18 00:28:04, mithro(OO till 11 Aug) wrote:
>
>> Should we try and fix OrderedSimpleTaskRunner without Now functionality?
>> Or
>> should we just land that change which also makes these tests behave as
>> expected?
>>
>
>
> If it's not too much trouble, please split them up; but I'm fine either
> way.
> They are pretty closely related.
>
>
>
>  On 18 July 2014 10:23, <mailto:brianderson@chromium.org> wrote:
>>
>
>  > Thanks for writing all these tests. I agree with all of the expectations
>> > regarding correct behavior in the comments of each test.
>> >
>> >
>> >
>> > https://codereview.chromium.org/396063011/diff/1/cc/test/
>> > ordered_simple_task_runner_unittest.cc
>> > File cc/test/ordered_simple_task_runner_unittest.cc (right):
>> >
>> > https://codereview.chromium.org/396063011/diff/1/cc/test/
>> > ordered_simple_task_runner_unittest.cc#newcode47
>> > cc/test/ordered_simple_task_runner_unittest.cc:47: void
>> > PostTaskWhichPostsDelayedTask(int task_num,
>> > PostDelayedTaskWhichPostsDelayedTask?
>> >
>> > https://codereview.chromium.org/396063011/diff/1/cc/test/
>> > ordered_simple_task_runner_unittest.cc#newcode80
>> > cc/test/ordered_simple_task_runner_unittest.cc:80: PostTask(-task_num,
>> > delay);
>> > Using -task_num is a simple trick to figure out if the task is the
>> > second posted task. It's a little unintuitive at first, but since this
>> > is test-only I'm fine with that.
>> >
>> > https://codereview.chromium.org/396063011/
>> >
>>
>
>  To unsubscribe from this group and stop receiving emails from it, send an
>>
> email
>
>> to mailto:chromium-reviews+unsubscribe@chromium.org.
>>
>
>
>
> https://codereview.chromium.org/396063011/
>

To unsubscribe from this group and stop receiving emails from it, send an email
to chromium-reviews+unsubscribe@chromium.org.

[Sami, 2014-07-18 16:35:27]

On 2014/07/18 00:46:35, mithro(OO till 11 Aug) wrote:
> I'll give it a go. Sami, do you agree with Brian that the system should
> operate as the way my commented expectations show? I have a real world
> example that I can show if anyone wants.

Your expectations seem reasonable, but could you check that they match the
constraints here:

https://code.google.com/p/chromium/codesearch#chromium/src/base/sequenced_tas...

If they do, then I'm all for it :)

[mithro-old, 2014-08-14 06:02:19]

On 2014/07/18 16:35:27, Sami wrote:
> On 2014/07/18 00:46:35, mithro(OO till 11 Aug) wrote:
> > I'll give it a go. Sami, do you agree with Brian that the system should
> > operate as the way my commented expectations show? I have a real world
> > example that I can show if anyone wants.
> 
> Your expectations seem reasonable, but could you check that they match the
> constraints here:
> 
>
https://code.google.com/p/chromium/codesearch#chromium/src/base/sequenced_tas...
> 
> If they do, then I'm all for it :)

Copying the constraints that Sami linked above;

// A SequencedTaskRunner is a subclass of TaskRunner that provides
// additional guarantees on the order that tasks are started, as well
// as guarantees on when tasks are in sequence, i.e. one task finishes
// before the other one starts.
//
// Summary
// -------
// Non-nested tasks with the same delay will run one by one in FIFO
// order.
//
// Detailed guarantees
// -------------------
//
// SequencedTaskRunner also adds additional methods for posting
// non-nestable tasks.  In general, an implementation of TaskRunner
// may expose task-running methods which are themselves callable from
// within tasks.  A non-nestable task is one that is guaranteed to not
// be run from within an already-running task.  Conversely, a nestable
// task (the default) is a task that can be run from within an
// already-running task.
//
// The guarantees of SequencedTaskRunner are as follows:
//
//   - Given two tasks T2 and T1, T2 will start after T1 starts if:
//
//       * T2 is posted after T1; and
//       * T2 has equal or higher delay than T1; and
//       * T2 is non-nestable or T1 is nestable.
//
//   - If T2 will start after T1 starts by the above guarantee, then
//     T2 will start after T1 finishes and is destroyed if:
//
//       * T2 is non-nestable, or
//       * T1 doesn't call any task-running methods.
//
//   - If T2 will start after T1 finishes by the above guarantee, then
//     all memory changes in T1 and T1's destruction will be visible
//     to T2.
//
//   - If T2 runs nested within T1 via a call to the task-running
//     method M, then all memory changes in T1 up to the call to M
//     will be visible to T2, and all memory changes in T2 will be
//     visible to T1 from the return from M.
//
// Note that SequencedTaskRunner does not guarantee that tasks are run
// on a single dedicated thread, although the above guarantees provide
// most (but not all) of the same guarantees.  If you do need to
// guarantee that tasks are run on a single dedicated thread, see
// SingleThreadTaskRunner (in single_thread_task_runner.h).
//
// Some corollaries to the above guarantees, assuming the tasks in
// question don't call any task-running methods:
//
//   - Tasks posted via PostTask are run in FIFO order.
//
//   - Tasks posted via PostNonNestableTask are run in FIFO order.
//
//   - Tasks posted with the same delay and the same nestable state
//     are run in FIFO order.
//
//   - A list of tasks with the same nestable state posted in order of
//     non-decreasing delay is run in FIFO order.
//
//   - A list of tasks posted in order of non-decreasing delay with at
//     most a single change in nestable state from nestable to
//     non-nestable is run in FIFO order. (This is equivalent to the
//     statement of the first guarantee above.)
//
// Some theoretical implementations of SequencedTaskRunner:
//
//   - A SequencedTaskRunner that wraps a regular TaskRunner but makes
//     sure that only one task at a time is posted to the TaskRunner,
//     with appropriate memory barriers in between tasks.
//
//   - A SequencedTaskRunner that, for each task, spawns a joinable
//     thread to run that task and immediately quit, and then
//     immediately joins that thread.
//
//   - A SequencedTaskRunner that stores the list of posted tasks and
//     has a method Run() that runs each runnable task in FIFO order
//     that can be called from any thread, but only if another
//     (non-nested) Run() call isn't already happening.

[brianderson, 2014-08-21 21:29:23]

Do you intend to roll this patch into https://codereview.chromium.org/387493002?

[mithro-old, 2014-08-25 05:31:02]

On 2014/08/21 at 21:29:23, brianderson wrote:
> Do you intend to roll this patch into
https://codereview.chromium.org/387493002?

This patch was extracted out of https://codereview.chromium.org/387493002 in the
first place. I'm not planning on landing this. Closing.