Repository: tahoe-lafs/zfec (language: python)

Issue:
Using multithreading, sometimes the results are wrong
The [tahoe-chk](https://whetstone.private.storage/privatestorage/tahoe-chk/) test suite exercises the Haskell bindings for encoding and decoding.  _Sometimes_ the test suite fails as a result of getting garbage from the ZFEC encoder.  This manifests as CHK shares being miscomputed and is visible as CHK capabilities with the wrong fingerprints.

Apparently sometimes the encoder output contains extra copies of the primary shares instead of generated secondary shares.

The tahoe-chk test suite failures look like this:

```
❯ while cabal run tests -- --num-threads 4 --pattern 'chkCap'; do :; done                                              
Up to date                                                                                                                                                                        
CHK                                                                                                                                                                               
  Vectors                                                                                                                                                                         
    chkCap                                                                                                                                                                        
      URI:CHK:rl4bzmselnuezmapjlzssnqg2e:p7kvin2fnemochuxsmh6ot75qpbfhrscbxi5i74bhqdhzcy6i5eq:1:3:56:         FAIL (0.02s)
        test/SpecCHK.hs:367:                                                                                                                                                      
        yes                                                                                                                                                                       
        expected: Right URI:CHK:rl4b...:p7kv...:1:3:56                                                                                                                            
         but got: Right URI:CHK:rl4b...:kb2z...:1:3:56                                                                                                                            
        Use -p '/chkCap/&&/URI:CHK:rl4bzmselnuezmapjlzssnqg2e:p7kvin2fnemochuxsmh6ot75qpbfhrscbxi5i74bhqdhzcy6i5eq:1:3:56/' to rerun this test only.        
...
```

The behavior is non-deterministic.  It seems that generally either all of the tests beneath `chkCap` pass or fail together.  Threading options seem to make a difference to the result.  I don't think I've ever observed a failure with only one test runner thread.



Discussion / hints:

Fix patch:
diff --git a/.circleci/config.yml b/.circleci/config.yml
index 1cb8322e..730d8377 100644
--- a/.circleci/config.yml
+++ b/.circleci/config.yml
@@ -43,7 +43,7 @@ jobs:
 
       - run:
           name: "Nix Build"
-          no_output_timeout: "30m"
+          no_output_timeout: "90m"
           command: |
             nix build --print-build-logs
 
diff --git a/fec.cabal b/fec.cabal
index ae50f1bc..e3ceed39 100644
--- a/fec.cabal
+++ b/fec.cabal
@@ -1,6 +1,6 @@
 cabal-version:      3.0
 name:               fec
-version:            0.1.1
+version:            0.2.0
 license:            GPL-2.0-or-later
 license-file:       README.rst
 author:             Adam Langley <agl@imperialviolet.org>
@@ -31,6 +31,7 @@ library
   build-depends:
     , base
     , bytestring  >=0.9
+    , extra
 
   exposed-modules:    Codec.FEC
   default-extensions: ForeignFunctionInterface
diff --git a/haskell/Codec/FEC.hs b/haskell/Codec/FEC.hs
index 9cbbf21c..a769fc06 100644
--- a/haskell/Codec/FEC.hs
+++ b/haskell/Codec/FEC.hs
@@ -18,6 +18,7 @@
 -}
 module Codec.FEC (
     FECParams (paramK, paramN),
+    initialize,
     fec,
     encode,
     decode,
@@ -29,6 +30,8 @@ module Codec.FEC (
     deFEC,
 ) where
 
+import Control.Concurrent.Extra (Lock, newLock, withLock)
+import Control.Exception (Exception, throwIO)
 import Data.Bits (xor)
 import qualified Data.ByteString as B
 import qualified Data.ByteString.Unsafe as BU
@@ -42,7 +45,7 @@ import Foreign.ForeignPtr (
  )
 import Foreign.Marshal.Alloc (allocaBytes)
 import Foreign.Marshal.Array (advancePtr, withArray)
-import Foreign.Ptr (FunPtr, Ptr, castPtr)
+import Foreign.Ptr (FunPtr, Ptr, castPtr, nullPtr)
 import Foreign.Storable (poke, sizeOf)
 import System.IO (IOMode (..), withFile)
 import System.IO.Unsafe (unsafePerformIO)
@@ -57,6 +60,8 @@ data FECParams = FECParams
 instance Show FECParams where
     show (FECParams _ k n) = "FEC (" ++ show k ++ ", " ++ show n ++ ")"
 
+foreign import ccall unsafe "fec_init"
+    _init :: IO ()
 foreign import ccall unsafe "fec_new"
     _new ::
         -- | k
@@ -101,6 +106,24 @@ isValidConfig k n
     | n > 255 = False
     | otherwise = True
 
+{- | The underlying library signaled that it has not been properly initialized
+ yet.  Use @initialize@ to initialize it.
+-}
+data Uninitialized = Uninitialized deriving (Ord, Eq, Show)
+
+instance Exception Uninitialized
+
+-- A lock to ensure at most one thread attempts to initialize the underlying
+-- library at a time.  Multiple initializations are harmless but concurrent
+-- initializations are disallowed.
+_initializationLock :: Lock
+{-# NOINLINE _initializationLock #-}
+_initializationLock = unsafePerformIO newLock
+
+-- | Initialize the library.  This must be done before other APIs can succeed.
+initialize :: IO ()
+initialize = withLock _initializationLock _init
+
 -- | Return a FEC with the given parameters.
 fec ::
     -- | the number of primary blocks
@@ -115,8 +138,13 @@ fec k n =
             unsafePerformIO
                 ( do
                     cfec' <- _new (fromIntegral k) (fromIntegral n)
-                    params <- newForeignPtr _free cfec'
-                    return $ FECParams params k n
+                    -- new will return null if the library hasn't been
+                    -- initialized.
+                    if cfec' == nullPtr
+                        then throwIO Uninitialized
+                        else do
+                            params <- newForeignPtr _free cfec'
+                            return $ FECParams params k n
                 )
 
 -- | Create a C array of unsigned from an input array
diff --git a/zfec/_fecmodule.c b/zfec/_fecmodule.c
index 72f250a6..381bff5f 100644
--- a/zfec/_fecmodule.c
+++ b/zfec/_fecmodule.c
@@ -673,6 +673,8 @@ init_fec(void) {
     py_fec_error = PyErr_NewException("_fec.Error", NULL, NULL);
     PyDict_SetItemString(module_dict, "Error", py_fec_error);
 
+    fec_init();
+
 #if PY_MAJOR_VERSION >= 3
     return module;
 #endif
diff --git a/zfec/fec.c b/zfec/fec.c
index cc77a93b..310a038b 100644
--- a/zfec/fec.c
+++ b/zfec/fec.c
@@ -393,12 +393,23 @@ _invert_vdm (gf* src, unsigned k) {
     return;
 }
 
+/* There are few (if any) ordering guarantees that apply to reads and writes
+ * of this static int across threads.  This is the reason for some of the
+ * tight requirements for how `fec_init` is called.  If we could use a mutex
+ * or a C11 atomic here we might be able to provide more flexibility to
+ * callers.  It's tricky to do that while remaining compatible with all of
+ * macOS/Linux/Windows and CPython's MSVC requirements and not switching to
+ * C++ (or something even more different).
+ */
 static int fec_initialized = 0;
-static void
-init_fec (void) {
-    generate_gf();
-    _init_mul_table();
-    fec_initialized = 1;
+
+void
+fec_init (void) {
+    if (fec_initialized == 0) {
+        generate_gf();
+        _init_mul_table();
+        fec_initialized = 1;
+    }
 }
 
 /*
@@ -428,8 +439,9 @@ fec_new(unsigned short k, unsigned short n) {
     assert(n <= 256);
     assert(k <= n);
 
-    if (fec_initialized == 0)
-        init_fec ();
+    if (fec_initialized == 0) {
+        return NULL;
+    }
 
     retval = (fec_t *) malloc (sizeof (fec_t));
     retval->k = k;
diff --git a/zfec/fec.h b/zfec/fec.h
index 249fe666..aaa42578 100644
--- a/zfec/fec.h
+++ b/zfec/fec.h
@@ -20,6 +20,18 @@ typedef struct {
 #define restrict
 #endif
 
+/** Initialize the fec library.
+ *
+ * Call this:
+ *
+ *  - at least once
+ *  - from at most one thread at a time
+ *  - before calling any other APIs from the library
+ *  - before creating any other threads that will use APIs from the library
+ *
+ */
+void fec_init(void);
+
 /**
  * param k the number of blocks required to reconstruct
  * param m the total number of blocks created


Test patch:
diff --git a/haskell/test/FECTest.hs b/haskell/test/FECTest.hs
index 042f3771..1d5e9099 100644
--- a/haskell/test/FECTest.hs
+++ b/haskell/test/FECTest.hs
@@ -6,17 +6,16 @@ import Test.Hspec (describe, hspec, it, parallel)
 
 import qualified Codec.FEC as FEC
 import qualified Data.ByteString as B
-import Data.Int ()
+import qualified Data.ByteString.Lazy as BL
 import Data.List (sortOn)
-import Data.Serializer ()
 import Data.Word (Word16, Word8)
-
 import System.Random (Random (randoms), mkStdGen)
 import Test.QuickCheck (
     Arbitrary (arbitrary),
     Property,
     Testable (property),
     choose,
+    conjoin,
     once,
     withMaxSuccess,
     (===),
@@ -24,6 +23,8 @@ import Test.QuickCheck (
 import Test.QuickCheck.Monadic (assert, monadicIO, run)
 
 -- Imported for the orphan Arbitrary ByteString instance.
+
+import Control.Monad (replicateM_)
 import Test.QuickCheck.Instances.ByteString ()
 
 -- | Valid ZFEC parameters.
@@ -103,9 +104,36 @@ prop_deFEC (Params req tot) testdata =
     allShares = FEC.enFEC req tot testdata
     minimalShares = take req allShares
 
+prop_primary_copies :: Params -> BL.ByteString -> Property
+prop_primary_copies (Params _ tot) primary = property $ do
+    conjoin $ (BL.toStrict primary ===) <$> secondary
+  where
+    fec = FEC.fec 1 tot
+    secondary = FEC.encode fec [BL.toStrict primary]
+
 main :: IO ()
-main = hspec $
-    parallel $ do
+main = do
+    -- Be sure to do the required zfec initialization first.
+    FEC.initialize
+    hspec . parallel $ do
+        describe "encode" $ do
+            -- This test originally caught a bug in multi-threaded
+            -- initialization of the C library.  Since it is in the
+            -- initialization codepath, it cannot catch the bug if it runs
+            -- after initialization has happened.  So we put it first in the
+            -- suite and hope that nothing manages to get in before this.
+            --
+            -- Since the bug has to do with multi-threaded use, we also make a
+            -- lot of copies of this property so hspec can run them in parallel
+            -- (QuickCheck will not do anything in parallel inside a single
+            -- property).
+            --
+            -- Still, there's non-determinism and the behavior is only revealed
+            -- by this property sometimes.
+            replicateM_ 20 $
+                it "returns copies of the primary block for all 1 of N encodings" $
+                    withMaxSuccess 5 prop_primary_copies
+
         describe "secureCombine" $ do
             -- secureDivide is insanely slow and memory hungry for large inputs,
             -- like QuickCheck will find with it as currently defined.  Just pass
@@ -115,8 +143,11 @@ main = hspec $
             it "is the inverse of secureDivide n" $ once $ prop_divide 1024 65 3
 
         describe "deFEC" $ do
-            it "is the inverse of enFEC" (withMaxSuccess 2000 prop_deFEC)
-
-        describe "decode" $ do
-            it "is (nearly) the inverse of encode" (withMaxSuccess 2000 prop_decode)
-            it "works with required=255" $ property $ prop_decode (Params 255 255)
+            replicateM_ 10 $
+                it "is the inverse of enFEC" $
+                    property prop_deFEC
+
+        describe "decode" $
+            replicateM_ 10 $ do
+                it "is (nearly) the inverse of encode" $ property $ prop_decode
+                it "works with required=255" $ property $ prop_decode (Params 255 255)