Issue #3595 - Add an actual scheduler; use joined threads for file system

src/Scheduler.h

 /*
  * This file is part of Adblock Plus <https://adblockplus.org/>,
  * Copyright (C) 2006-2016 Eyeo GmbH
  *
  * Adblock Plus is free software: you can redistribute it and/or modify
  * it under the terms of the GNU General Public License version 3 as
  * published by the Free Software Foundation.
  *
  * Adblock Plus is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * GNU General Public License for more details.
  *
  * You should have received a copy of the GNU General Public License
  * along with Adblock Plus.  If not, see <http://www.gnu.org/licenses/>.
  */
 
 #if !defined(ADBLOCKPLUS_SCHEDULER_H)
 #define ADBLOCKPLUS_SCHEDULER_H
 
+#include <condition_variable>
+#include <list>
 #include <memory>
+#include <mutex>
 #include <functional>
+#include <queue>
+#include <thread>
 
 namespace AdblockPlus
 {
   /*
    * Adapter class for heap allocated function objects
    *
    * The legacy behavior of the original threading regime combined task life
    * cycle and execution. Previously, tasks were allocated by the user and 
    * deleted at the end of execution internally. This adapter class allows
    * separation of these concerns. It allows the legacy allocation behavior 
@@ skipping 19 matching lines @@
   };
 
   /*
    * Utility function uses type inference to simplify expressions at point of use.
    */
   template<class T>
   HeapFunction<T> MakeHeapFunction(std::shared_ptr<T> body)
   {
     return HeapFunction<T>(body);
   }
-
-  /*
-   * Scheduler for the execution of tasks.
-   *
-   * The present version is nothing more than a rewrite of the legacy behavior,
-   *   which was to create a new thread for each task.
-   */
-  class Scheduler
-  {
-  public:
-    /*
-     * Execute a task immediately in a thread created for this task only
-     */
-    static void StartImmediatelyInSingleUseThread(std::function<void()> task);
-  };
 }
+
+/*
+ * Execute a task immediately in detached thread that's used only for this task.
+ *
+ * The present version is nothing more than a rewrite of the legacy behavior,
+ *   which was to create a new thread for each task.
+ */
+void StartImmediatelyInSingleUseDetachedThread(std::function<void()> task);
+
+/**
+ * Active object to run arbitrary function objects.
+ *
+ * Operations execute in a thread owned by this instance.
+ * If a user wants to execute an operation in a different thread,

[sergei, 2017/01/20 13:08:14]

We don't need this part "If a user wants to execute an operation in a different
thread ...".

[Eric, 2017/03/30 17:16:59]

Documenting responsibilities is part of what makes documentation good. The line
you want to remove is documenting a responsibility that this class does not
assume.

Responsibility allocation is part of the design, so it's got to be part of the
documentation. For where this started, see
    https://en.wikipedia.org/wiki/Class-responsibility-collaboration_card

[sergei, 2017/04/03 15:35:33]

Sorry, but I have not seen on the provisioned link anything explaining the
reason to have such comment.
If you think that this comment should be then where are comments like
- if a user wants to execute an operation immediately ...
- if a user wants to execute an operation in 5 min ...
- if a user wants to execute an operation in 3 min ...
...
- if a user wants to execute an operation and show a green button
...
?

+ *   they have the responsibility to set up whatever additional
+ *   facilities may be required.
+ */
+class OperationRunner

[sergei, 2017/01/20 13:08:14]

Why not to call it ActiveObject?

[Eric, 2017/03/30 17:16:59]

Because it's not a generic active object. It's tailored for use inside the
scheduler.

[sergei, 2017/04/03 15:35:33]

Maybe it's not a generic active object but it is a simple active object which
can be used as a base for any another active object.

+{
+  /**
+   * Shared mutex for all synchronization
+   */
+  std::mutex m;
+  typedef std::unique_lock<std::mutex> UniqueLockType;
+  /**
+   * Condition variable notified when a operation is added to its queue
+   */
+  std::condition_variable cv;
+  /**
+   * Operation queue for internal communication
+   */
+  std::queue<std::function<void()>> queue;

[sergei, 2017/01/20 13:08:14]

Basically, it's a synchronized queue which has already appeared several times.
So, it would be better to have it as a separate class. However, currently, it's
not important.

[Eric, 2017/03/30 17:16:59]

It's not a separate class because the mutex is used for more than queue
management. You need atomicity between queue operations and notification, for
instance. If you separate them, you get race conditions.

[sergei, 2017/04/03 15:35:33]

Could you please point to that race condition in the example I have posted?

+  /**
+    * The thread for the operation queue
+    */
+  std::thread th;
+  /**
+   * Flag to keep the operation queue running
+   */
+  bool isRunning;
+  /**
+   * Thread main for the operation queue thread.
+   */
+  void ThreadMain();
+
+public:
+  /**
+   * Execution thread starts during construction.
+   */
+  OperationRunner();
+
+  /**
+   * Note: The execution thread must end before the destructor returns.
+   */
+  ~OperationRunner();
+
+  /**
+   * Queue up an operation for execution in the queue's thread.
+   */
+  void Run(std::function<void()> f);
+};
+
+/**
+ * A worker with a single-use-thread.
+ */
+class SingleUseWorker

[sergei, 2017/01/20 13:08:13]

It looks like there was a lot of discussions, finally decided that it's better
if a thread class has no member start/Run/whatever, but here we again introduce
it...

[Eric, 2017/03/30 17:16:59]

It doesn't look from my perspective that there were any discussions at all. When
did these purported discussions happen? Why was I not included?

Besides, this isn't a "thread class". If you want a name for it, it's a "worker
class" and acts as a resource, which I described in my previous message.

[sergei, 2017/04/03 15:35:32]

There were a lot of talks regarding designing a thread class in different C++
communities like boost and Qt and maybe during considering proposals for C++11,
strangely I cannot find any link, but one of main conclusions was that it's a
bad idea to have such method like run or start on a thread class because in this
case one can call it several times on the same object. Therefore there is only
one way to start a thread which is by passing a callable to the constructor or
to a run method accepting callable. Of course there is still plenty ways to use
it a wrong way but, because member methods start have proven themselves on
practice, the recommendation for designers of a thread class was to try another
interface and see whether it helps.
OK, clear, I would propose to introduce that abstraction when it's really
needed.

+{
+  /**
+   * The underlying thread
+   */
+  std::thread th;
+
+public:
+  /**
+   * Constructor does not start thread; that happens in `Run()`.
+   */
+  SingleUseWorker();
+  ~SingleUseWorker();
+  /**
+   * Run a task
+   *
+   * This class may rely on the restriction 
+   *   that the user may call this function at most once.
+   */
+  void Run(std::function<void()> f);
+  /**
+   * Synchronize with point of completion of task
+   *
+   * The present class calls `join()` on the thread,
+   *   but alternates might synchronize in other ways.
+   */
+  void Join();
+};
+
+/**
+ * A simple scheduler.
+ *
+ * The scheduler keeps track of executing threads 
+ *   instead of detaching them and keeping no record of what's executing.
+ * The main goal at this stage is to be able to join all running threads.
+ * Since you can't call `join()` on a thread from within that thread,
+ *   this class contains its a separate thread to be able to make such calls.
+ * This thread runs a generic operation queue 
+ *   that does more than simply join zombie threads.
+ *

[sergei, 2017/03/30 13:14:41]

Could you please move that Scheduler with the functionality described in few
lines above into a separate codereview? We will soon need it for android.

BTW, Scheduler should be even simpler, not a template class and it seems instead
of SingleUseWorker we can directly use std::thread.

[Eric, 2017/03/30 14:20:55]

You might know what you want, but this description is far too short to make
sense of what you are actually asking. I'll also remind you that this review
depended upon a previous one, and your request might involve pulling in code
from the previous one.
No, it should not be simpler. If you want me to do this, the template stays. If
you understood this code better, you'd see that the template is necessary for
the scheduler to work as written.

Hard-coding the particular behaviors of std::thread is a bad idea. std::thread
runs its body upon construction, so if you use that interface, it becomes
impractical to use a thread pool later because the life-cycle of std::thread is
different from what you want with a thread pool. std::thread does not act as a
manageable resource (nor should it), but a proper scheduler needs to be able to
manage its thread resources. Using raw threads diminishes the code that's
already written.

SingleUseWorker above is a wrapper around a raw thread that converts it into a
resource. It's also why it has a Run() method, because it's acting as a resource
and not a raw thread. One of the characteristics of a resource is that it
separates (1) life-cycle, for example, acquire and release from (2) usage, here
running a function body. std::thread does not have that kind of interface, so it
is *necessary* to add it.

----

Furthermore, this review was number 2 of 12 (eventually) in a series that fixed
all the structural problems with threads and engine allocation, completing all
the substantive work for both #3595 and #3593 (they are interrelated, which
isn't obvious). The usage of the Worker template argument is slated for
modification, which is yet another reason not to use raw threads. Right now, the
only usages of a worker resource are `Run()` and `Join()`, but it's slated for a
`Cancel()` method.

In detail, review 9 of 12 (if I'm counting correctly) allows interruption of
timer from SetTimeout. This works by changing the executor for timer bodies to
contain an condition variable. Wake up the condition variable before its timer
fires and you forestall execution of the body. During development that executor
began as a class specific to timers, but the plan is for some of its interface
to migrate into the worker interface so that the scheduler can interrupt and
cancel pending work.

[sergei, 2017/04/03 15:35:33]

So, what are the difficulties to create a codereview only with SchedulerT (I
think the name should be changed) and its dependencies?
Apparently the template is not necessary in my example, so the template is not
necessary.
I think that thread pool should be a completely different class because with the
current approach when a new instance of a worker is created for each task and
with `monitor` the implementation of the thread pool is not going to be simple,
the same for implementation of timers.
BTW, so far there is no need in thread pool, so I would like to ask to not
complicate the code before it's needed.
I consider std::thread also as resource and so far the interface of std::thread
is enough.
That's good but why not to introduce that abstraction in a separate commit?
Smaller commits are always better. What concerns the number of reviews, I don't
think it's an issue because anyway these codereviews should be adapted to
whatever state of master, and I think that the easiest way is to simply pick
small portions with simple functionality and rebase the rest afterwards.
I see the point but for present I would like to don't pull that abstraction. I
doubt that the proposed implementation in
https://codereview.adblockplus.org/29370876/ is the right way we should go now
(because there are more elegant approaches) and maybe later (I think about
clearTimeout).
Cancelling functionality in general has a lot of questions, for instance I would
implement it slightly differently, most likely even on another level, and it
highly depends on requirements. So far, I would propose to create corresponding
issues and discuss it there. For example,
- we will definitely need `clearTimeout` however it's not very important right
now because it's never used.
- `XMLHttpRequest.abort()` is similar to the previous one
- so far, we don't use any cancellable API to work with file system, so no need
for such issue
- an issue with arguments against current cancelling of timers when we are
destroying JsEngine and it would be good to see a reasoned proposal
- cancelling of running file system operations and web requests when JsEngine is
being destroyed. Though I think it should be a part of another issue. I don't
mind to discuss it in https://issues.adblockplus.org/ticket/3595, because the
latter is actually a meta issue for subsequent work, although the description
should be adjusted to its generic title, even more the things mentioned in "What
to change" are already done.

+ * The present version has some limitations and inefficiencies,
+ *   trading them off for ease of incremental implementation.
+ *   - Separate schedulers for each `JsEngine` without any shared facilities.

[sergei, 2017/01/20 13:08:14]

I would remove this string because whether there is a "Separate schedulers for
each `JsEngine`" is not defined yet, it rather looks like an advantage and
scheduler should not be aware about any JsEngine.

[Eric, 2017/03/30 17:16:58]

Since you've not delved into this code the way I have, I'll forgive this
misapprehension. If you want to be able to destroy JsEngine instances, engines
and schedulers must absolutely be aware of each other.

This line documents the particular relationship between the present scheduler
and the present engine.

I don't see any reason as of today why we cannot eventually use a single
scheduler for multiple engine instances. Schedulers generically require their
own thread(s), so it would be better eventually to use a singleton instance, but
we're not there yet. Thus the documentation.

[sergei, 2017/04/03 15:35:33]

I think that scheduler should not be so direct member of JsEngine, I would like
to provide users of libadblockplus with possibility to use their own scheduler
for asynchronous operations. It's useful because, e.g. on MS Windows only one
worker thread is enough to support all our asynchronous operations. It means
changing of interface of injected interfaces like WebRequest and FileSystem to
have asynchronous methods and having a separate instances of scheduler in each
default implementation. All asynchronous operations should be cancelled when the
implementation is destroyed by JsEngine.
So, should JsEngine and scheduler be aware about each other? - No. JsEngine
should take into account that it schedules asynchronous tasks through certain
interfaces and that these tasks either completed or stopped and cleaned after
destroying of a corresponding interface. Neither scheduler nor injected
interfaces should know where they are used.

I can expect here some reaction like, "I have sent XX codereviews, why did you
not tell it earlier/stopped me, where are issues with that, etc". Apparently on
my question https://issues.adblockplus.org/ticket/3595#comment:2 instead of
opinions and following discussion, I have received
https://codereview.adblockplus.org/29367003/ and
https://codereview.adblockplus.org/29367507/ which are actually good but should
be slightly adjusted, so I planned they will be changed during the reviewing
process, and then within a pretty shot time span a bunch of following
codereviews. BTW, there are also good things in them but I would like to pick
them gradually.
I think that before doing such much work it would be better to firstly discuss
it.

+ *   - Working threads are single-use. No provision for a thread pool.

[sergei, 2017/01/20 13:08:13]

That's also questionable.

[Eric, 2017/03/30 17:16:59]

It is absolutely not questionable that this class, as written, uses only
single-use threads and has no provision for a thread pool. Did you not see the
"limitations and inefficiencies" point just three lines above.

Documenting deficiencies is important for code maintenance. It's impractical
and, more significantly, must slower to try to make everything perfect at each
iteration. That practice creates huge friction.

[sergei, 2017/04/03 15:35:33]

Why should it have a thread pool? It's similar to the example in another comment
thread, where is a comment that it does not show a big green button?

+ *   - Tasks are simple function objects. Its possible to hasten termination
+ *       in v8 by calling `TerminateExecution()`, for example,
+ *       but there's no interface for this.
+ *   - No support for delayed execution to support JavaScript `SetTimeout`.
+ */
+template<class Worker>
+class SchedulerT
+{
+  /**
+   * Shared mutex for all synchronization
+   */
+  std::mutex m;

[sergei, 2017/01/20 13:08:14]

it should be rather std::recursive_mutex because if Worker does not run in a a
thread and instead does the everything immediately, thus in the same thread,
there will be an exception.

[Eric, 2017/03/30 17:16:58]

No, it should not be recursive mutex. That would be masking an error. There's no
correct usage scenario where the mutex would ever be called recursively. And for
the record, of all the errors I encountered developing this code, not once did I
ever have the kind of exception you're positing.

Since this is apparently not an obvious point, when you run a task through this
scheduler, the second thing it does (after locking the mutex) is to obtain a new
worker, and that worker is always a separate thread. See the `emplace` statement
in `Run()` below; it invokes the default constructor for `Worker`.

[sergei, 2017/04/03 15:35:33]

Acknowledged.

+  typedef std::unique_lock<std::mutex> UniqueLockType;
+
+  /**
+   * A list containing an entry for each running task.
+   */
+  std::list<Worker> taskList;
+
+  /**
+   * Condition variable notified when a running task is removed from its list
+   */
+  std::condition_variable taskRemoveCv;
+
+  /**
+   * Maintains a separate thread that is able to join completed worker threads.
+   */
+  OperationRunner monitor;
+
+  /**
+   * Execution wrapper for a task.
+   * @param task
+   *   An iterator to the task within the task list.
+   */
+  void WorkerMain(std::function<void()> body, typename std::list<Worker>::iterator task)
+  {
+    body();
+    monitor.Run([this, task]() { JoinAndRemove(task); });
+  }
+
+  /**
+   * Joins a task and then removes it from the task list.
+   * @param task
+   *   An iterator to the task within the task list.
+   *
+   * This is the only function that may remove tasks from the running task list.
+   */
+  void JoinAndRemove(typename std::list<Worker>::iterator task)
+  {
+    task->Join();

[sergei, 2017/04/03 15:35:33]

here is a race condition, it can happen that move-assignment in
SingleUseWorker::Run has not happened yet but body has already finished and
monitor has already reached that point and inside SingleUseWorker::Join it
accessed SingleUseWorker::th which is default constructed yet.

+    {
+      UniqueLockType ul(m);
+      taskList.erase(task);
+    }
+    taskRemoveCv.notify_all();
+  }
+
+public:
+  SchedulerT()
+  {}
+
+  ~SchedulerT()
+  {
+    // `JoinAll()` may be called prior to destruction but, however,
+    //   there is no requirement that it be called beforehand.
+    // We call it in the destructor to ensure all tasks have completed.
+    // If we do not, we risk destruction of a joinable thread,
+    //   which would generate a call to `std::terminate()`.
+    JoinAll();
+  }
+
+  /**
+   * Construct a `Worker` and run a task in it immediately.
+   *
+   * This is the only function that may add tasks to the running task list.
+   */
+  void Run(std::function<void()> body)

[sergei, 2017/01/20 13:08:13]

It would be easier to read if argument "body" is renamed to something like a
"op" (from operation) or "call".

[Eric, 2017/03/30 17:16:58]

I've used "body" consistently for a function that's subject to scheduling and
management.

[sergei, 2017/04/03 15:35:33]

I still think that another name is better here, body of what is used here? Such
words like task, operation, function, callable, executable, runnable fit much
better here than body, IMO.

+  {
+    UniqueLockType ul(m);
+    // Note that the interface to `Worker` uses a constructor and not a factory
+    // Here we construct in place, avoiding both move and copy.
+    auto tt = taskList.emplace(taskList.begin());
+    tt->Run([this, body, tt]() { WorkerMain(body, tt); });

[sergei, 2017/01/20 13:08:13]

I'm not sure that it's a wise decision to assume that Worker runs in some
another thread. In this change it's OK but looking at the final code it seems
very questionable. So, I  would rather have it changed here, in this codereview.
"monitor.Run([this, task]() { JoinAndRemove(task); });" should be rather some
kind of a next function which is executed after worker has finished, which
happens not exactly right after a call of "body". It's clear if consider a case
when we use facilities for asynchronous IO.

[Eric, 2017/03/30 17:16:58]

This is not just an assumption. It's a design principle.

If you don't want a task to be scheduled, don't use the scheduler. If you
schedule it, it runs in some arbitrary thread different that the one it's called
in.

Perhaps you don't recall, but the high-level goal in using asynchrony at all is
to support JavaScript callbacks without re-entering v8. In order to do that, you
*must* restart the call stack from the top, and the only mechanism we have
available for that is a thread. If you were to implement a Worker without a
thread inside somewhere, it would be incorrect in the only usage we have for it.
Apparently you don't understand how it works, so please indicate what you don't
understand so that I can expand upon the documentation.

Ever since this code was working, I've had no problems with dangling threads for
tasks run through this scheduler. The mechanism here is correct, reliable, and
efficient.
That's the way the code works already. `JoinAndRemove` is called within the
monitor thread and not within whatever thread is inside the worker. What does
happen immediately upon completion of the body is enqueuing a `JoinAndRemove`
operation onto the monitor.

Also note that the scheduler takes full responsibility for the entire life cycle
of its tasks. It starts them up initially and detects when they're finished.
Workers have no awareness that they're being used by schedulers, so the
scheduler does not have to present any kind of interface to the worker. This is
far simpler than any alternative where the worker notifies the scheduler that
it's finished.
This mechanism works just fine for asynchronous I/O. I rewrote all of it to use
this mechanism. You say that you've read my code, but if you have, statement
like this lead me believe you did so at best only cursorily or didn't
understand.

[sergei, 2017/04/03 15:35:32]

OK, let's say I want to implement timers using SetTimer from Win API and I'm
allowed to create only one thread for all timers per instance of Scheduler. What
will be the implementation of template class Worker?
JIC, It's merely a theoretical question, I'm not going to use Win API for
timers.
What I really don't understand is the reason you are always repeating that I
didn't understand something. Please stay professional.

+  }
+
+  /**
+   * Block until all running threads have been joined and the task list is empty.
+   *
+   * This class does not take on any responsibility to keep the task list
+   *   from growing while this function executes.
+   * Improper use can result in this function blocking forever; don't do that.
+   */
+  void JoinAll()
+  {
+    // The call to `Worker::Join()` is in another function,
+    //   namely `JoinAndRemove()`, which also removes items from the task list.
+    // Thus all we do here is to wait for the task list to empty.
+    UniqueLockType ul(m);
+    taskRemoveCv.wait(ul, [this]() -> bool { return taskList.empty(); });
+  }
+};
+
 #endif