Issue #3391 - Add detached initialization class

src/plugin/DetachedInitialization.h

+/*
+ * This file is part of Adblock Plus <https://adblockplus.org/>,
+ * Copyright (C) 2006-2015 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/>.
+ */
+
+#ifndef _DETACHED_INITIALIZATION_H_
+#define _DETACHED_INITIALIZATION_H_
+
+#include <atomic>
+#include <thread>
+#include <mutex>
+#include <chrono>
+#include <condition_variable>
+
+/**
+ * A detached initializer for static class members

[sergei, 2016/01/29 10:04:21]

It would be much better to pull the changes of this file from the following
review into this review
https://codereview.adblockplus.org/29334397/diff/29334398/src/plugin/Detached...

[Eric, 2016/01/29 15:33:10]

No need.

[sergei, 2016/02/09 17:38:14]

Currently it's very inconvenient to review the code in two places. Why do you
want us to review and to commit a temporary implementation which is already
different? It should be in one commit.

+ *
+ * Detached initializers use a separate thread to avoid delays at instantiation.
+ * Variables statically initialized in a DLL cannot, however, contain threads.
+ * Thus such initialization must occur in the constructor at the earliest.
+ *
+ * This kind of initialization acts shares much in common with a singleton.
+ * Rather than constructing a singleton, instead we execute an initialization function.
+ * The multiprocessing and synchronization issues, however, are essentially identical.
+ *
+ * The designated usage of this class:
+ * 1) Define a static class member 'x' of this type with an initializer function.
+ * 2) Call 'x.SpawnInitializer()' in the constructors to run the initializer.
+ * 3) Call 'x.EnsureInitialized()' before relying upon any of the side effects of the initializer.
+ *
+ * The implementation acts much like a multithreaded singleton initialization using a double-checked lock.
+ * See https://en.wikipedia.org/wiki/Double-checked_locking and http://preshing.com/20130922/acquire-and-release-fences/
+ * The flag members of this class enable fast-return paths, that is, a return without obtaining a mutex lock.
+ *
+ * \tparam F
+ *   The initializer function
+ *
+ * \par Serialization Guarantees
+ * The visible effect of these function returns are serialized: 
+ *   - SpawnInitializer() before ThreadMain()
+ *   - ThreadMain() before EnsureInitialized()
+ *   - If ThreadMain() started, ThreadMain() before destructor
+ */
+template<void (&F)()>
+class DetachedInitializer
+{
+  // "protected" declaration allows white-box subclass for testing
+protected:
+  /**
+   * Set to true after initializer thread successfully constructed; remains true thereafter.
+   */
+  std::atomic<bool> hasInitializerStarted;
+
+  /**
+   * Set to true after initializer function completes; remains true thereafter.
+   */
+  std::atomic<bool> isInitializationComplete;
+
+  /**
+   * Synchronizes order of setting flags and completion of member functions
+   *
+   * Protects separate changes to state flags
+   *   - In SpawnInitializer(), only one initializer runs
+   *   - In ThreadMain() and EnsureInitialized(), initializer completes and waiters notified
+   * Protects mutual changes to state flags
+   *   - Serialize setting flags true: hasInitializerStarted always before isInitializationComplete
+   */
+  std::mutex mutex;
+
+  /**
+   * Synchronizes end of initialization with waiting for intialization to finish.
+   */
+  std::condition_variable cv;
+
+  /**
+   * If not null, an exception thrown by the initializer function
+   * Thrown in EnsureInitialized() if present.
+   */
+  std::exception_ptr initializerException;
+
+  typedef std::unique_lock<std::mutex> UniqueLockType;

[sergei, 2016/01/29 10:04:22]

I think we don't need "Type" suffix.

[Eric, 2016/01/29 15:33:10]

It's the C++ library convention, modified for our capitalization style.

[sergei, 2016/02/09 17:38:15]

Acknowledged.

+  typedef std::lock_guard<std::mutex> LockGuardType;

[sergei, 2016/01/29 10:04:22]

UniqueLockType is used only once, LockGuardType is used twice, why do we need a
typedef for them?

[Eric, 2016/01/29 15:33:11]

They're present because the code at the point of use is clearer with them.

[sergei, 2016/02/09 17:38:14]

That's very subjective, OK, let's leave them.

+
+  inline bool AlreadyInitialized() // noexcept

[sergei, 2016/01/29 10:04:22]

It seems this method should be `const`.

[Eric, 2016/01/29 15:33:10]

Done.

+  {
+    // Memory fence ensures load starts after any other load or store
+    return isInitializationComplete.load(std::memory_order_acquire);

[sergei, 2016/01/29 10:04:22]

Do we really need to be so specific and not use a default memory order value
everywhere in this class? It rather attracts the attention and causes questions
than simplifies the understanding (readability).
Thus we don't need these methods.

[Eric, 2016/01/29 15:33:11]

Memory fences are absolutely critical for correct behavior.

I'm not going to try to teach you _why_ that is. If you don't understand why
they're necessary, then start with the two URL's in the class documentation
comment above, and keep reading. Keep reading until you understand why they're
here.
It _should_ attract attention. The code is incorrect without these fences.
Here's how I read this statement: "I don't understand it, therefore it shouldn't
be here." I do hope you appreciate why I have zero respect for this statement.

[sergei, 2016/02/09 17:38:14]

That's clear that they are critical, why do we need to use not a default value
(`std::memory_order_seq_cst`)?
That sounds quite offensive, taking into account comments from some other code
reviews, I can only recommend you to behave professional in conversations, read
the documentation and carefully check the everything before you write an answer
and don't demonstrate the lack of experience. Try to read something about ethics
in code review.
I'm not proposing to not use these fences, they are still used with default
value for memory order. There is a negligible overheard and much better
maintainability.
Why do think that I don't understand it? Just in case, when I ask the question
"why" or "what" it also means that I'm kindly giving you an opportunity to
recognize the trouble by yourself and don't want to be so rude as you above by
saying "Keep reading until you understand".
I think that your position in return to generate something, the code and not
succinct lengthy answers in codereviews, is not productive, by doing it you are
wasting at least my and Oleksandr's time, please respect the colleagues.

+  }
+
+  inline bool AlreadyStartedInitializer() // noexcept

[sergei, 2016/01/29 10:04:20]

It seems this method should be `const`.

[Eric, 2016/01/29 15:33:11]

Done.

+  {
+    return hasInitializerStarted.load(std::memory_order_acquire);
+  }
+
+  /**
+   * Main function for thread
+   */
+  void ThreadMain()
+  {
+    try
+    {
+      F();
+    }
+    catch (std::exception& e)

[sergei, 2016/01/29 10:04:21]

Compiler generates warning `e` is not used.

[sergei, 2016/01/29 10:04:23]

Why is it not const reference?

[Eric, 2016/01/29 15:33:10]

Done.

It's fixed in the subsequent patch set, incidentally, but since I need to post a
new patch set, I can do it here.

[sergei, 2016/02/09 17:38:14]

I see that in
https://codereview.adblockplus.org/29334397/diff/29335525/src/plugin/Detached...
it's replaced by ellipsis, that's one of the examples that it would be better to
pull the changes into the current codereview.

+    {
+      // Assert initializer threw an exception

[sergei, 2016/01/29 10:04:22]

This comment is not needed

[sergei, 2016/02/09 17:38:15]

ignored?

+      initializerException = std::current_exception();
+    }
+    /*
+     * Synchronize with reading the completion status in EnsureInitialized().
+     * Serialize return from SpawnInitializer() and this function.
+     */
+    LockGuardType lg(mutex);

[sergei, 2016/01/29 10:04:20]

it would be easier to read if name it `lock` not `lg`.

[Eric, 2016/01/29 15:33:11]

Its name doesn't matter, since it's a sentry object and only instantiated. Might
as well call it 'x'.

+    isInitializationComplete.store(true, std::memory_order_release);
+    cv.notify_all();
+  }
+
+  /**
+   * "noexcept" version of EnsureInitialized() used to implement both it and the destructor
+   */
+  void EnsureInitializedNoexcept() // noexcept
+  {
+    try
+    {
+      if (AlreadyInitialized())
+      {
+        return; // fast-return path
+      }
+      UniqueLockType ul(mutex); // won't throw because this class uses only scoped locks

[sergei, 2016/01/29 10:04:23]

it would be easier to read if name it `lock` not `ul`.

+      /*
+       * We must always check initialization status under lock.
+       * The loop protects against spurious wake-up calls.
+       */
+      while (!AlreadyInitialized())
+      {
+        cv.wait(ul); // won't throw because mutex is locked
+      }
+    }
+    catch (...)
+    {
+      // Should not reach

[sergei, 2016/01/29 10:04:21]

It would be better to put `assert(false && "Should not reach")` here.

[Eric, 2016/01/29 15:33:11]

That would be unnecessary code bloat.

There's a proof in the code comments about why the code will not throw. It
relies upon guarantees made by the standard library. The try-block is only there
so we can get a noexcept declaration to compile correctly.

If C++ were more sophisticated, we could show noexcept behavior inside
non-comment code. But we can't.

[sergei, 2016/02/09 17:38:15]

It's not more than the comment, however it helps to find it out when it happens.

+    }
+  }
+
+public:
+  DetachedInitializer()
+    : hasInitializerStarted(false), isInitializationComplete(false)
+  {}
+
+  /**
+   * \par Precondition
+   *   - No external aliases to this instance exist except for the one in the initializer thread
+   *
+   * \par Postcondition
+   *   - Ensures that initializer thread is not running before return.
+   */
+  ~DetachedInitializer()
+  {
+    /*
+     * We don't need to acquire a lock here.
+     * By precondition at most the initializer thread is running, and it doesn't touch this flag.

[sergei, 2016/01/29 10:04:23]

We don't need this comment.

[Eric, 2016/01/29 15:33:10]

We do.

+     */
+    if (!AlreadyStartedInitializer())
+    {
+      return;
+    }
+    // Wait for initializer to complete
+    EnsureInitialized();
+  }

[sergei, 2016/01/29 10:04:21]

We should wait in the destructor for the finishing of the thread, otherwise we
can get the case when the object instance has been already destroyed but the
variables from the scope of ThreadMain are not destroyed yet but they use in
their destructor object instance members (in particular `lg` uses `mutex`).

[Eric, 2016/01/29 15:33:10]

Sergei, we _are_ waiting for the destructor to finish. That's what calling
EnsureInitialized() does. 

[sergei, 2016/02/09 17:38:14]

Right, overlooked.
However, I would to still wait for the finishing of the thread for the sake of a
good order because `this` is captured by the closure of thread function, it has
no side-effect here but it attracts an attention.
In addition, it's always safer to know when the thread has finished and we can
do it here without a significant overhead.

+
+  /**
+   * Start an initialization thread if not already initialized and no initialization thread exists.
+   *
+   * \par Postcondition
+   * - if returns, AlreadyStartedInitializer is true
+   * - if throws, AlreadyStartedInitializer is false

[sergei, 2016/01/29 10:04:21]

Why is it false and what happens in EnsureInitialized called from the destructor
then?

[Eric, 2016/01/29 15:33:11]

Trace the code. The only times this function can throw is when
'AlreadyStartedInitializer' is false. Analyzing this isn't as simple as
identifying statements that _might_ throw. Most such statements cannot actually
throw because their preconditions for not throwing are satisfied.

For the record, the only statement that can throw is the thread constructor.

[sergei, 2016/02/09 17:38:13]

Acknowledged.

+   */
+  void SpawnInitializer()
+  {
+    if (AlreadyInitialized() || AlreadyStartedInitializer())
+    {
+      return; // fast-return path
+    }
+    // Assert we have neither completed nor started an initialization thread
+    /*
+     * Try to obtain a lock, giving us permission to start the initialization thread.
+     * try_lock() is not reliable, that is, it can sometimes fail to lock when the mutex is unlocked.
+     * It is, however, guaranteed to succeed eventually.
+     */
+    while (true)
+    {
+      if (mutex.try_lock())
+      {
+        // Assert mutex is locked
+        LockGuardType lg(mutex, std::adopt_lock);

[sergei, 2016/01/29 10:04:22]

Why not just use `std::lock_guard<std::mutex> lock(mutex)` without try_lock and
the infinite cycle with sleep?

[Eric, 2016/01/29 15:33:10]

Because that would be incorrect code.

There's a race condition if you do it in the way you suggest. I know, because
that's what I had originally.

[sergei, 2016/02/09 17:38:15]

What is the race condition here? If there is a real race condition then it
should be reflected in the comment, right now the comment is not useful.

+        /*
+         * Refresh our knowledge of whether the initializer has started, this time under lock.
+         */
+        if (AlreadyStartedInitializer())
+        {
+          return;
+        }
+        /*
+         * This thread constructor is the only statement that can throw in this function.
+         * If it does throw, the initialization-started flag won't be set.
+         * An exception here is thus a soft error, since a future invocation might succeed.
+         */
+        std::thread th([this]() -> void { ThreadMain(); });

[sergei, 2016/01/29 10:04:20]

Can it be written down as `[this]{ ThreadMain(); }`?

+        // Memory fence ensures store ends before any other load or store
+        hasInitializerStarted.store(true, std::memory_order_release);
+        th.detach(); // Won't throw because the thread is both valid and joinable

[sergei, 2016/01/29 10:04:22]

We should not do that, see comment for the destructor.

[Eric, 2016/01/29 15:33:10]

Calling 'detach()' here is the whole point of detached initialization. What's
not clear here? If we don't call 'detach()' here, we get a completely different
class.

[sergei, 2016/02/09 17:38:13]

If the thread is a member of the class then initialization won't block the
caller. Detaching a thread usually results in some race conditions and less
maintainable code.

+        return;
+      }
+      else
+      {
+        // Assert mutex is not locked
+        if (AlreadyStartedInitializer())
+        {
+          return; // Some other thread might have started the thread in the interim
+        }
+        // One microsecond is usually enough for a mutex to fully reset
+        std::this_thread::sleep_for(std::chrono::microseconds(1));

[sergei, 2016/01/29 10:04:23]

std::this_thread::yield() would be better.
FYI: according to my experience the precision of Sleep on MS Windows (NT) is
about 20 msec (milli not micro), it also means that usually it could not sleep
less than ~20msec, so it would be better to remove the comment.

[Eric, 2016/01/29 15:33:11]

Calling 'sleep()' is more conservative.

This statement only gets executed in the case of a spurious 'try_lock()'
failure. That's already rare on any architecture. I read some commentary online
that the VS version of this never has spurious failures. The upshot is that this
statement is executed seldom-to-never. Hence the performance of this statement
is not critical. I've picked the statement that has more conservative behavior.

[sergei, 2016/02/09 17:38:12]

std::this_thread::yield() is more descriptive, so we need neither comments nor
questionable sleep.

+      }
+    }
+  }
+
+  /**
+   * Ensure that initialization has completed, blocking if necessary until it is.
+   *
+   * SpawnInitializer() must have returned prior to calling this function.
+   * If not, the function will block indefinitely.
+   *
+   * \throw exception
+   *   if the initializer threw an exception, it's rethrown here
+   */
+  void EnsureInitialized()

[sergei, 2016/01/29 10:04:21]

If you require to call firstly SpawnInitializer() then add an `assert` or throw
an exception.

[sergei, 2016/01/29 10:04:21]

It would be better to name it WaitForInitCompletion. "EnsureInitialized" implies
that SpawnInitializer() will be called if it's not called yet.

[Eric, 2016/01/29 15:33:11]

As I've said so many times before, this is a not a general purpose library
class. We do not need to hold the hands of potential users.

We have two uses of this class in the code base. I'm sure we can get it right.

If this requirement were undocumented, we would have a problem. But it's
adequately documented. Therefore, all I can say is "please don't shoot yourself
in the foot by not reading".

[Eric, 2016/01/29 15:33:11]

Renaming suggestion rejected. The current name reflects what you can rely on
("what it does"). The name you suggest is how it works.

[sergei, 2016/02/09 17:38:12]

It does not ensure that something is initialized if nobody called
`SpawnInitializer`, so it does not do what is said in the name.

[sergei, 2016/02/09 17:38:13]

If it's used merely two times then it might be not a time to generalize it.
It's good that it's commented but having the check in addition in the code does
not hurt.

+  {
+    EnsureInitializedNoexcept();
+    if (initializerException)
+    {
+      std::rethrow_exception(initializerException);
+    }
+  }
+};
+
+#endif // _DETACHED_INITIALIZATION_H_