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

[Oleksandr, 2016/02/05 07:36:05]

Nit: 2016

[Eric, 2016/02/08 17:34:07]

Done.

+ *
+ * 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
+ *
+ * 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;
+  typedef std::lock_guard<std::mutex> LockGuardType;
+
+  inline bool AlreadyInitialized() const // noexcept
+  {
+    // Memory fence ensures load starts after any other load or store
+    return isInitializationComplete.load(std::memory_order_acquire);
+  }
+
+  inline bool AlreadyStartedInitializer() const // noexcept
+  {
+    return hasInitializerStarted.load(std::memory_order_acquire);
+  }
+
+  /**
+   * Main function for thread
+   */
+  void ThreadMain()
+  {
+    try
+    {
+      F();
+    }
+    catch (std::exception&)
+    {
+      // Assert initializer threw an exception
+      initializerException = std::current_exception();
+    }
+    /*
+     * Synchronize with reading the completion status in EnsureInitialized().
+     * Serialize return from SpawnInitializer() and this function.
+     */
+    LockGuardType lg(mutex);
+    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
+      /*
+       * 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
+    }
+  }
+
+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.
+     */
+    if (!AlreadyStartedInitializer())
+    {
+      return;
+    }
+    // Wait for initializer to complete
+    EnsureInitialized();
+  }
+
+  /**
+   * 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
+   */
+  void SpawnInitializer()

[Oleksandr, 2016/02/01 02:47:09]

The double checked locking is really convoluted here. Why not just do something
like?

std::once_flag flag;
ThreadMain()
{
  ...
  std::call_once(flag, F);
  cv.notify_all();
}

void SpawnInitializer()
{
  ...
  std::thread th([this]() -> void { ThreadMain(); });
  th.detach();
}

And I would also still use the 

[Eric, 2016/02/03 14:19:01]

[...]
'std::call_once' has different behavior than might be obvious, and it leads to
behavior that does not work as well here.

The main problem is that using 'call_once()' has exception behavior that's
inappropriate for what we need. If you spawn multiple threads and the active
execution thread throws, this function then converts one of the passive threads
into the active execution thread and tries again. In other words, the function
should not be named 'call_once()' but 'call_until_first_return()'. There are
uses where that's appropriate behavior, but this isn't one of them.

Another problem is that using 'call_once()' you have to create one thread per
call to 'SpawnInitializer()'. The present approach only ever creates a single
thread over all instances.

[Oleksandr, 2016/02/05 07:36:05]

I am not convinced converting passive threads into active ones isn't what we
want though. As it is now, re-throwing the exception in EnsureInitialized is
counter intuitive, IMHO. In fact I think we could be better off if we eat the
possible exceptions in the initialization function instead and assume it can not
throw. 
With the usage that this class will have I don't think it will be any
performance hit at all. On the flip side would be a better
readability/maintainability though.

[Eric, 2016/02/08 17:34:07]

There's no other place to throw it. You can't throw it from 'SpawnInitializer()'
since that function returns before the initializer thread even starts. What's
going on here is something like a deferred constructor exception. When
'EnsureInitialized()' throws, it's telling you that it's not initialized and is
never going to be. 
You can never assume that a function call will not throw (even if declared
'noexcept'), because there are a handful of exceptions, such as 'bad_alloc',
that are implicit in the language.

Besides, you can get what you want in the present code just fine. Just use an
initializer function that doesn't throw. That's exactly what I did in
https://codereview.adblockplus.org/29332665/ (which, I must point out, has
_still_ received no comments). 
Threads are reasonably heavy system resources. (Not as much as a process, but
still ...) It's foolish code that spawns a thread just to check some flags and
then terminates, particularly when we've already got code (the present review)
that does that completely generically already.
Because the semantics are different (hard vs. soft errors), this concern isn't
relevant. We need it to behave correctly.

[Eric, 2016/02/08 17:34:07]

It's not what we want, at least not now.

The difference in semantics is that between handling hard errors and soft
errors. If you have hard errors, you don't want to retry. And if your apparatus
does retry, you may need new code in the initialization function not to actually
retry, since some hard errors don't like being tried again.

On the other hand, if you have soft errors, you may want to retry, but you need
to be able to distinguish that the error is hard vs. soft and not combine the
two. We have no capacity to make that distinction yet. We haven't even done a
proper analysis of what error might be soft vs. hard, although the one I've
looked that replace static initialization look all/mostly like hard errors. In
addition, when you want to handle soft errors, you need to have class semantics
to allow an object to exist in a "temporarily not working" state. We don't have
any capacity at present for that either.

The semantics of this present class are for hard errors. This makes everything
easier and we can make incremental progress. If we want to support soft errors
at the outset, it's a lot more code change.

+  {
+    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);
+        /*
+         * 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(); });
+        // 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
+        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));
+      }
+    }
+  }
+
+  /**
+   * 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()
+  {
+    EnsureInitializedNoexcept();
+    if (initializerException)
+    {
+      std::rethrow_exception(initializerException);
+    }
+  }
+};
+
+#endif // _DETACHED_INITIALIZATION_H_