Issue #3391 - Add detached initialization class

src/plugin/DetachedInitialization.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/>.
+ */
+
+#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()
+  {
+    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_