kenshou-check (empty) → 0.1.0.0
raw patch · 37 files changed
+3321/−0 lines, 37 filesdep +aesondep +asyncdep +base
Dependencies added: aeson, async, base, bytestring, containers, directory, filepath, hedgehog, hspec, hspec-hedgehog, kenshou-check, kenshou-core, network, process, scientific, splitmix, stm, temporary, text, time, unix
Files
- CHANGELOG.md +13/−0
- LICENSE +28/−0
- fixture/Main.hs +6/−0
- kenshou-check.cabal +132/−0
- src/Kenshou/Check/Fact.hs +128/−0
- src/Kenshou/Check/Fault.hs +112/−0
- src/Kenshou/Check/Fault/Cell.hs +31/−0
- src/Kenshou/Check/Fault/Network.hs +215/−0
- src/Kenshou/Check/Fault/Postgres.hs +169/−0
- src/Kenshou/Check/Fault/Time.hs +36/−0
- src/Kenshou/Check/Fault/Wake.hs +35/−0
- src/Kenshou/Check/Invariant.hs +262/−0
- src/Kenshou/Check/Invariant/Checkpoint.hs +3/−0
- src/Kenshou/Check/Invariant/Duplicates.hs +3/−0
- src/Kenshou/Check/Invariant/Effects.hs +3/−0
- src/Kenshou/Check/Invariant/Gapless.hs +3/−0
- src/Kenshou/Check/Invariant/NoLoss.hs +3/−0
- src/Kenshou/Check/Invariant/Order.hs +3/−0
- src/Kenshou/Check/Invariant/Ownership.hs +3/−0
- src/Kenshou/Check/Invariant/Quiescence.hs +3/−0
- src/Kenshou/Check/Ledger.hs +198/−0
- src/Kenshou/Check/Ledger/Read.hs +111/−0
- src/Kenshou/Check/Ledger/Sort.hs +132/−0
- src/Kenshou/Check/Model.hs +87/−0
- src/Kenshou/Check/Model/Linearizability.hs +148/−0
- src/Kenshou/Check/Oracle.hs +108/−0
- src/Kenshou/Check/Process.hs +373/−0
- src/Kenshou/Check/Scenario.hs +77/−0
- src/Kenshou/Check/Selftest.hs +160/−0
- src/Kenshou/Check/Selftest/BackendKill.hs +109/−0
- src/Kenshou/Check/Selftest/KillRestart.hs +125/−0
- src/Kenshou/Check/Selftest/ModelReplay.hs +79/−0
- src/Kenshou/Check/Selftest/ProxyPartition.hs +80/−0
- src/Kenshou/Check/Verdict.hs +120/−0
- src/Kenshou/Check/Window.hs +52/−0
- test/Main.hs +170/−0
- test/golden/verdict.json +1/−0
+ CHANGELOG.md view
@@ -0,0 +1,13 @@+# Changelog++## 0.1.0.0 - 2026-10-28++### New Features++- First public release of the correctness toolkit: fact ledgers, invariants, fault injection, process supervision, and linearizability checking.+- Oracles are registered on bundles by name and turned into typed queries with `fromSpec`; `registeredOracle` looks them up.++### Other Changes++- Extracted from `mori://shinzui/keiro-runtime-kenshou` at commit `a1648293443ad88ff1695ed800ff44c99993574e`, with its package and module names unchanged.+- The layer-specific oracle modules stay with the suites that own them.
+ LICENSE view
@@ -0,0 +1,28 @@+BSD 3-Clause License++Copyright (c) 2026, Nadeem Bitar++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++1. Redistributions of source code must retain the above copyright notice, this+ list of conditions and the following disclaimer.++2. Redistributions in binary form must reproduce the above copyright notice,+ this list of conditions and the following disclaimer in the documentation+ and/or other materials provided with the distribution.++3. Neither the name of the copyright holder nor the names of its contributors+ may be used to endorse or promote products derived from this software without+ specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"+AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE+IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE+DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR+ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES+(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;+LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON+ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ fixture/Main.hs view
@@ -0,0 +1,6 @@+module Main (main) where++import Control.Concurrent (threadDelay)++main :: IO ()+main = threadDelay maxBound
+ kenshou-check.cabal view
@@ -0,0 +1,132 @@+cabal-version: 3.0+name: kenshou-check+version: 0.1.0.0+synopsis: Correctness and fault-injection toolkit for Kenshou scenarios+description: Bounded evidence ledgers, invariant verdicts, process supervision, fault injection, and model checking.+license: BSD-3-Clause+license-file: LICENSE+author: Nadeem Bitar+maintainer: nadeem@gmail.com+homepage: https://github.com/shinzui/kenshou+bug-reports: https://github.com/shinzui/kenshou/issues+category: Testing+build-type: Simple+extra-doc-files: CHANGELOG.md+tested-with: ghc >=9.12 && <9.13+extra-source-files:+ test/golden/verdict.json++common warnings+ ghc-options:+ -Wall+ -Wcompat+ -Widentities+ -Wincomplete-record-updates+ -Wincomplete-uni-patterns+ -Wpartial-fields+ -Wredundant-constraints++ default-language: GHC2024+ default-extensions:+ BlockArguments+ DuplicateRecordFields+ ImportQualifiedPost+ NoFieldSelectors+ OverloadedLabels+ OverloadedRecordDot+ OverloadedStrings++library+ import: warnings+ hs-source-dirs: src+ exposed-modules:+ Kenshou.Check.Fact+ Kenshou.Check.Fault+ Kenshou.Check.Fault.Cell+ Kenshou.Check.Fault.Network+ Kenshou.Check.Fault.Postgres+ Kenshou.Check.Fault.Time+ Kenshou.Check.Fault.Wake+ Kenshou.Check.Invariant+ Kenshou.Check.Invariant.Checkpoint+ Kenshou.Check.Invariant.Duplicates+ Kenshou.Check.Invariant.Effects+ Kenshou.Check.Invariant.Gapless+ Kenshou.Check.Invariant.NoLoss+ Kenshou.Check.Invariant.Order+ Kenshou.Check.Invariant.Ownership+ Kenshou.Check.Invariant.Quiescence+ Kenshou.Check.Ledger+ Kenshou.Check.Ledger.Read+ Kenshou.Check.Ledger.Sort+ Kenshou.Check.Model+ Kenshou.Check.Model.Linearizability+ Kenshou.Check.Oracle+ Kenshou.Check.Process+ Kenshou.Check.Scenario+ Kenshou.Check.Selftest+ Kenshou.Check.Selftest.BackendKill+ Kenshou.Check.Selftest.KillRestart+ Kenshou.Check.Selftest.ModelReplay+ Kenshou.Check.Selftest.ProxyPartition+ Kenshou.Check.Verdict+ Kenshou.Check.Window++ build-depends:+ aeson >=2.2 && <2.3,+ async >=2.2 && <2.3,+ base >=4.21 && <4.22,+ bytestring >=0.12 && <0.13,+ containers >=0.7 && <0.8,+ directory >=1.3 && <1.4,+ filepath >=1.5 && <1.6,+ hedgehog >=1.7 && <1.8,+ kenshou-core ^>=0.1.0.0,+ network >=3.2 && <3.3,+ process >=1.6 && <1.7,+ scientific >=0.3 && <0.4,+ splitmix >=0.1 && <0.2,+ stm >=2.5 && <2.6,+ text >=2.1 && <2.2,+ time >=1.14 && <1.15,+ unix >=2.8 && <2.9,++test-suite kenshou-check-test+ import: warnings+ type: exitcode-stdio-1.0+ hs-source-dirs: test+ main-is: Main.hs+ build-tool-depends: kenshou-check:kenshou-check-fixture-worker+ ghc-options:+ -threaded+ -rtsopts+ -with-rtsopts=-N+ -with-rtsopts=-T++ build-depends:+ aeson,+ base >=4.21 && <4.22,+ bytestring,+ containers,+ directory >=1.3 && <1.4,+ filepath,+ hedgehog >=1.4 && <1.8,+ hspec >=2.11 && <2.12,+ hspec-hedgehog >=0.0 && <0.4,+ kenshou-check,+ kenshou-core ^>=0.1.0.0,+ temporary,+ text,+ time >=1.14 && <1.15,++executable kenshou-check-fixture-worker+ import: warnings+ hs-source-dirs: fixture+ main-is: Main.hs+ ghc-options: -threaded+ build-depends:+ base >=4.21 && <4.22++source-repository head+ type: git+ location: https://github.com/shinzui/kenshou.git
+ src/Kenshou/Check/Fact.hs view
@@ -0,0 +1,128 @@+module Kenshou.Check.Fact+ ( FactKind (..),+ ProcId (..),+ Fact (..),+ factKindText,+ parseFactKind,+ renderProcId,+ parseProcId,+ )+where++import Data.Aeson+import Data.Aeson.KeyMap (KeyMap)+import Data.Int (Int64)+import Data.Text (Text)+import Data.Text qualified as Text+import Data.Word (Word64)++data FactKind+ = Intent+ | Produced+ | Observed+ | Effect+ | Terminal+ | Acquired+ | Acted+ | Released+ | Checkpoint+ | DisturbanceStart+ | DisturbanceEnd+ | Mark+ deriving stock (Eq, Ord, Show, Enum, Bounded)++data ProcId = ProcId+ { role :: !Text,+ index :: !Int,+ incarnation :: !Int+ }+ deriving stock (Eq, Ord, Show)++data Fact = Fact+ { kind :: !FactKind,+ key :: !Text,+ seq :: !Int64,+ id :: !Text,+ scope :: !Text,+ proc :: !ProcId,+ n :: !Word64,+ mono :: !Word64,+ wall :: !Int64,+ attrs :: !(KeyMap Value)+ }+ deriving stock (Eq, Show)++factKindText :: FactKind -> Text+factKindText Intent = "intent"+factKindText Produced = "produced"+factKindText Observed = "observed"+factKindText Effect = "effect"+factKindText Terminal = "terminal"+factKindText Acquired = "acquired"+factKindText Acted = "acted"+factKindText Released = "released"+factKindText Checkpoint = "checkpoint"+factKindText DisturbanceStart = "disturbance-start"+factKindText DisturbanceEnd = "disturbance-end"+factKindText Mark = "mark"++parseFactKind :: Text -> Maybe FactKind+parseFactKind value = lookup value [(factKindText item, item) | item <- [minBound .. maxBound]]++renderProcId :: ProcId -> Text+renderProcId value = value.role <> "/" <> Text.pack (show value.index) <> "." <> Text.pack (show value.incarnation)++parseProcId :: Text -> Either Text ProcId+parseProcId value = case Text.breakOnEnd "/" value of+ (roleWithSlash, suffix)+ | not (Text.null roleWithSlash),+ (indexText, incarnationTextWithDot) <- Text.breakOn "." suffix,+ Just index <- readText indexText,+ Just incarnation <- readText (Text.drop 1 incarnationTextWithDot),+ not (Text.null incarnationTextWithDot) ->+ Right (ProcId (Text.dropEnd 1 roleWithSlash) index incarnation)+ _ -> Left "process id must be <role>/<index>.<incarnation>"+ where+ readText input = case reads (Text.unpack input) of [(parsed, "")] -> Just parsed; _ -> Nothing++instance ToJSON FactKind where toJSON = String . factKindText++instance FromJSON FactKind where+ parseJSON = withText "FactKind" (maybe (fail "unknown fact kind") pure . parseFactKind)++instance ToJSON ProcId where toJSON = String . renderProcId++instance FromJSON ProcId where+ parseJSON = withText "ProcId" (either (fail . Text.unpack) pure . parseProcId)++instance ToJSON Fact where+ toJSON fact =+ object+ [ "schema" .= ("kenshou.ledger-fact/v1" :: Text),+ "kind" .= fact.kind,+ "key" .= fact.key,+ "seq" .= fact.seq,+ "id" .= fact.id,+ "scope" .= fact.scope,+ "proc" .= fact.proc,+ "n" .= fact.n,+ "mono" .= fact.mono,+ "wall" .= fact.wall,+ "attrs" .= Object fact.attrs+ ]++instance FromJSON Fact where+ parseJSON = withObject "Fact" \value -> do+ schema <- value .: "schema"+ if schema /= ("kenshou.ledger-fact/v1" :: Text) then fail "unsupported ledger fact schema" else pure ()+ Fact+ <$> value .: "kind"+ <*> value .: "key"+ <*> value .: "seq"+ <*> value .: "id"+ <*> value .: "scope"+ <*> value .: "proc"+ <*> value .: "n"+ <*> value .: "mono"+ <*> value .: "wall"+ <*> (value .: "attrs" >>= withObject "attrs" pure)
+ src/Kenshou/Check/Fault.hs view
@@ -0,0 +1,112 @@+module Kenshou.Check.Fault+ ( Duration (..),+ milliseconds,+ seconds,+ Availability (..),+ FaultHandle (..),+ Fault (..),+ Schedule,+ at,+ every,+ during,+ onMark,+ holding,+ withSchedule,+ )+where++import Control.Concurrent (threadDelay)+import Control.Concurrent.Async+import Control.Concurrent.MVar+import Control.Exception (Exception, bracket, bracketOnError, throwIO)+import Control.Monad (forM_)+import Data.Aeson (Value)+import Data.Text (Text)+import Kenshou.Check.Fact (FactKind (..))+import Kenshou.Check.Ledger (recordDurable)+import Kenshou.Check.Process (Child, awaitMark)+import Kenshou.Check.Scenario+import Kenshou.Core.Phase (PhaseName)++newtype Duration = Duration {micros :: Int}+ deriving stock (Eq, Ord, Show)++milliseconds :: Int -> Duration+milliseconds value = Duration (value * 1000)++seconds :: Int -> Duration+seconds value = Duration (value * 1000000)++data Availability = Available | Unavailable Text deriving stock (Eq, Show)++data FaultHandle = FaultHandle+ { heal :: IO (),+ details :: Value+ }++data Fault = Fault+ { name :: Text,+ target :: Text,+ availability :: IO Availability,+ inject :: IO FaultHandle+ }++data Scheduled = Scheduled+ { delay :: !Duration,+ waitForMark :: !(Maybe (Child, Text)),+ fault :: !Fault+ }++newtype Schedule = Schedule [Scheduled]++instance Semigroup Schedule where Schedule left <> Schedule right = Schedule (left <> right)++instance Monoid Schedule where mempty = Schedule []++newtype FaultInjectionFailed = FaultInjectionFailed Text deriving stock (Eq, Show)++instance Exception FaultInjectionFailed++at :: Duration -> Fault -> Schedule+at delay fault = Schedule [Scheduled delay Nothing fault]++every :: Duration -> Fault -> Schedule+every = at++during :: PhaseName -> Schedule -> Schedule+during _ = id++onMark :: Child -> Text -> Fault -> Schedule+onMark child mark fault = Schedule [Scheduled (Duration 0) (Just (child, mark)) fault]++holding :: Duration -> Fault -> Fault+holding duration fault =+ fault+ { inject = do+ bracketOnError fault.inject (.heal) \handle -> do+ threadDelay duration.micros+ handle.heal+ pure handle {heal = pure ()}+ }++withSchedule :: CheckEnv -> Schedule -> IO value -> IO value+withSchedule environment (Schedule scheduled) action = bracket start stop (const action)+ where+ start = do+ active <- newMVar []+ workers <- traverse (async . runOne active) scheduled+ pure (workers, active)+ stop (workers, active) = do+ mapM_ cancel workers+ readMVar active >>= mapM_ (.heal)+ runOne active item = do+ forM_ item.waitForMark \(child, mark) -> awaitMark child mark 600000+ threadDelay item.delay.micros+ availability <- item.fault.availability+ case availability of+ Unavailable reason -> throwIO (FaultInjectionFailed (item.fault.name <> ": " <> reason))+ Available -> do+ recordDurable environment.ledger DisturbanceStart item.fault.target 0 item.fault.name mempty+ handle <- item.fault.inject+ modifyMVar_ active (pure . (handle :))+ recordDurable environment.ledger DisturbanceEnd item.fault.target 0 item.fault.name mempty
+ src/Kenshou/Check/Fault/Cell.hs view
@@ -0,0 +1,31 @@+module Kenshou.Check.Fault.Cell (cellFault) where++import Data.Aeson (Value, encode, object, (.=))+import Data.ByteString.Lazy.Char8 qualified as LazyByteString+import Data.Text (Text)+import Data.Text qualified as Text+import Kenshou.Check.Fault+import System.Environment (lookupEnv)+import System.Exit (ExitCode (..))+import System.Process (readProcessWithExitCode)++cellFault :: Text -> Value -> Fault+cellFault name parameters =+ Fault+ { name = "cell-" <> name,+ target = "cell",+ availability = maybe (Unavailable "KENSHOU_CELL_FAULT_HOOK is unset") (const Available) <$> lookupEnv "KENSHOU_CELL_FAULT_HOOK",+ inject = do+ hook <- lookupEnv "KENSHOU_CELL_FAULT_HOOK" >>= maybe (ioError (userError "KENSHOU_CELL_FAULT_HOOK is unset")) pure+ (code, token, err) <- readProcessWithExitCode hook ["inject", Text.unpack name, LazyByteString.unpack (encode parameters)] ""+ case code of+ ExitFailure _ -> ioError (userError err)+ ExitSuccess -> do+ let cleanToken = Text.strip (Text.pack token)+ pure (FaultHandle (healHook hook cleanToken) (object ["fault" .= name, "token" .= cleanToken]))+ }++healHook :: FilePath -> Text -> IO ()+healHook hook token = do+ (code, _, err) <- readProcessWithExitCode hook ["heal", Text.unpack token] ""+ case code of ExitSuccess -> pure (); ExitFailure _ -> ioError (userError err)
+ src/Kenshou/Check/Fault/Network.hs view
@@ -0,0 +1,215 @@+module Kenshou.Check.Fault.Network+ ( TcpProxy,+ QueryBarrier,+ ProxyMode (..),+ withTcpProxy,+ proxyPort,+ setProxyMode,+ armQueryBarrier,+ armResponseBarrier,+ queryBarrierReached,+ releaseQueryBarrier,+ releaseResponseBarrier,+ resetConnections,+ proxyFault,+ proxiedConnectionString,+ )+where++import Control.Concurrent (threadDelay)+import Control.Concurrent.Async+import Control.Concurrent.MVar+import Control.Concurrent.STM+import Control.Exception (SomeException, bracket, bracketOnError, catch, finally)+import Control.Monad (forever, unless, void, when)+import Data.Aeson (object, (.=))+import Data.ByteString qualified as ByteString+import Data.Text (Text)+import Data.Text qualified as Text+import Kenshou.Check.Fault+import Kenshou.Core.Env.Postgres (PostgresEnv (..))+import Network.Socket+import Network.Socket.ByteString qualified as Socket++data ProxyMode = Forward | Latency Int | Throttle Int | Stall | Blackhole | RefuseNew+ deriving stock (Eq, Show)++data TcpProxy = TcpProxy+ { listening :: !Socket,+ port :: !PortNumber,+ mode :: !(TVar ProxyMode),+ queryBarrier :: !(TVar (Maybe QueryBarrier)),+ responseBarrier :: !(TVar (Maybe QueryBarrier)),+ connections :: !(MVar [Socket]),+ acceptor :: !(Async ())+ }++data QueryBarrier = QueryBarrier+ { needle :: !ByteString.ByteString,+ reached :: !(MVar ()),+ resume :: !(MVar ()),+ armed :: !(TVar Bool)+ }++withTcpProxy :: IO (HostName, PortNumber) -> (TcpProxy -> IO value) -> IO value+withTcpProxy upstream = bracket (startProxy upstream) stopProxy++proxyPort :: TcpProxy -> PortNumber+proxyPort = (.port)++setProxyMode :: TcpProxy -> ProxyMode -> IO ()+setProxyMode proxy mode = atomically (writeTVar proxy.mode mode)++-- | Hold the first downstream SQL request containing the supplied bytes before+-- forwarding it to PostgreSQL. The caller can change database state after+-- 'queryBarrierReached' and then release the exact request boundary.+armQueryBarrier :: TcpProxy -> ByteString.ByteString -> IO QueryBarrier+armQueryBarrier proxy = armBarrier proxy.queryBarrier++-- | Hold the first upstream response containing the supplied bytes before+-- forwarding it to the client. Useful for stopping an adapter after PostgreSQL+-- has read a row but before the adapter receives that row.+armResponseBarrier :: TcpProxy -> ByteString.ByteString -> IO QueryBarrier+armResponseBarrier proxy = armBarrier proxy.responseBarrier++armBarrier :: TVar (Maybe QueryBarrier) -> ByteString.ByteString -> IO QueryBarrier+armBarrier barrierSlot needle = do+ reached <- newEmptyMVar+ resume <- newEmptyMVar+ armed <- newTVarIO True+ let barrier = QueryBarrier needle reached resume armed+ atomically (writeTVar barrierSlot (Just barrier))+ pure barrier++queryBarrierReached :: QueryBarrier -> IO ()+queryBarrierReached = readMVar . (.reached)++releaseQueryBarrier :: TcpProxy -> QueryBarrier -> IO ()+releaseQueryBarrier proxy = releaseBarrier proxy.queryBarrier++releaseResponseBarrier :: TcpProxy -> QueryBarrier -> IO ()+releaseResponseBarrier proxy = releaseBarrier proxy.responseBarrier++releaseBarrier :: TVar (Maybe QueryBarrier) -> QueryBarrier -> IO ()+releaseBarrier barrierSlot barrier = do+ atomically (writeTVar barrierSlot Nothing)+ void (tryPutMVar barrier.resume ())++resetConnections :: TcpProxy -> IO Int+resetConnections proxy = modifyMVar proxy.connections \connections -> do+ mapM_ reset connections+ pure ([], length connections)+ where+ reset socket = (setSocketOption socket Linger 0 >> close socket) `catch` ignore++proxyFault :: TcpProxy -> ProxyMode -> Fault+proxyFault proxy mode =+ Fault+ { name = "tcp-" <> modeName mode,+ target = "tcp-proxy",+ availability = pure Available,+ inject = do+ previous <- readTVarIO proxy.mode+ setProxyMode proxy mode+ pure (FaultHandle (setProxyMode proxy previous) (object ["mode" .= modeName mode]))+ }++proxiedConnectionString :: PostgresEnv -> TcpProxy -> Text+proxiedConnectionString postgres proxy = postgres.connectionString <> " host=127.0.0.1 port=" <> Text.pack (show (fromIntegral proxy.port :: Int))++startProxy :: IO (HostName, PortNumber) -> IO TcpProxy+startProxy upstream = do+ listening <- socket AF_INET Stream defaultProtocol+ setSocketOption listening ReuseAddr 1+ bind listening (SockAddrInet 0 (tupleToHostAddress (127, 0, 0, 1)))+ listen listening 128+ port <- socketPort listening+ mode <- newTVarIO Forward+ queryBarrier <- newTVarIO Nothing+ responseBarrier <- newTVarIO Nothing+ connections <- newMVar []+ acceptor <- async (acceptLoop upstream listening mode queryBarrier responseBarrier connections)+ pure (TcpProxy listening port mode queryBarrier responseBarrier connections acceptor)++stopProxy :: TcpProxy -> IO ()+stopProxy proxy = do+ cancel proxy.acceptor+ close proxy.listening `catch` ignore+ void (resetConnections proxy)++acceptLoop :: IO (HostName, PortNumber) -> Socket -> TVar ProxyMode -> TVar (Maybe QueryBarrier) -> TVar (Maybe QueryBarrier) -> MVar [Socket] -> IO ()+acceptLoop upstream listening mode queryBarrier responseBarrier connections = forever do+ (downstream, _) <- accept listening+ current <- readTVarIO mode+ if current == RefuseNew+ then close downstream+ else void . async $ do+ (host, port) <- upstream+ upstreamSocket <- connectTo host port+ modifyMVar_ connections (pure . (downstream :) . (upstreamSocket :))+ race_ (pump mode queryBarrier downstream upstreamSocket) (pump mode responseBarrier upstreamSocket downstream) `finally` do+ close downstream `catch` ignore+ close upstreamSocket `catch` ignore++connectTo host port = do+ addresses <- getAddrInfo (Just defaultHints {addrSocketType = Stream}) (Just host) (Just (show (fromIntegral port :: Int)))+ case addresses of+ [] -> ioError (userError "proxy upstream did not resolve")+ address : _ -> bracketOnError (socket (addrFamily address) Stream defaultProtocol) close \socket -> connect socket (addrAddress address) >> pure socket++pump :: TVar ProxyMode -> TVar (Maybe QueryBarrier) -> Socket -> Socket -> IO ()+pump mode barrier source destination = go ByteString.empty+ where+ go carry = do+ chunk <- Socket.recv source 32768+ unless (ByteString.null chunk) do+ nextCarry <- pauseOnQuery barrier carry chunk+ awaitMode mode chunk+ current <- readTVarIO mode+ case current of+ Blackhole -> pure ()+ RefuseNew -> Socket.sendAll destination chunk+ _ -> Socket.sendAll destination chunk+ go nextCarry++pauseOnQuery :: TVar (Maybe QueryBarrier) -> ByteString.ByteString -> ByteString.ByteString -> IO ByteString.ByteString+pauseOnQuery currentBarrier carry chunk =+ readTVarIO currentBarrier >>= \case+ Nothing -> pure ByteString.empty+ Just barrier -> do+ let combined = carry <> chunk+ keep = max 0 (ByteString.length barrier.needle - 1)+ nextCarry = ByteString.drop (max 0 (ByteString.length combined - keep)) combined+ when (barrier.needle `ByteString.isInfixOf` combined) do+ claimed <- atomically do+ pending <- readTVar barrier.armed+ when pending (writeTVar barrier.armed False)+ pure pending+ when claimed do+ putMVar barrier.reached ()+ takeMVar barrier.resume+ pure nextCarry++awaitMode mode chunk =+ readTVarIO mode >>= \case+ Forward -> pure ()+ Latency millis -> do+ threadDelay (millis * 1000)+ atomically do+ current <- readTVar mode+ check (current /= Stall)+ Throttle bytesPerSecond -> threadDelay (max 1 (ByteString.length chunk * 1000000 `div` max 1 bytesPerSecond))+ Stall -> atomically do current <- readTVar mode; check (current /= Stall)+ Blackhole -> pure ()+ RefuseNew -> pure ()++modeName :: ProxyMode -> Text+modeName Forward = "forward"+modeName (Latency _) = "latency"+modeName (Throttle _) = "throttle"+modeName Stall = "stall"+modeName Blackhole = "blackhole"+modeName RefuseNew = "refuse-new"++ignore :: SomeException -> IO ()+ignore _ = pure ()
+ src/Kenshou/Check/Fault/Postgres.hs view
@@ -0,0 +1,169 @@+module Kenshou.Check.Fault.Postgres+ ( Backend (..),+ BackendSelector (..),+ LockTarget (..),+ CrashMode (..),+ listBackends,+ terminateBackends,+ terminateOneBackend,+ holdLock,+ hogConnections,+ withApplicationName,+ withStatementTimeout,+ crashPostmaster,+ )+where++import Control.Concurrent (threadDelay)+import Control.Monad (replicateM)+import Data.Aeson (object, (.=))+import Data.Int (Int32, Int64)+import Data.Text (Text)+import Data.Text qualified as Text+import Kenshou.Check.Fault+import Kenshou.Check.Process (ProcessSpec (..))+import Kenshou.Core.Env.Postgres+import System.Exit (ExitCode (..))+import System.Posix.Signals (sigKILL, signalProcess)+import System.Process++data Backend = Backend+ { pid :: !Int32,+ applicationName :: !Text,+ state :: !Text,+ waitEventType :: !(Maybe Text),+ waitEvent :: !(Maybe Text),+ query :: !Text+ }+ deriving stock (Eq, Show)++data BackendSelector = ByApplicationName Text | ByQueryPattern Text | ByPid Int32 | AllOtherBackends+ deriving stock (Eq, Show)++data LockTarget = TableLock Text Text | RowLock Text Text | AdvisoryLock Int64+ deriving stock (Eq, Show)++data CrashMode = ImmediateShutdown | FastShutdown | KillPostmaster+ deriving stock (Eq, Show)++listBackends :: PostgresEnv -> IO [Backend]+listBackends postgres = do+ output <- psql postgres "SELECT pid, coalesce(application_name,''), coalesce(state,''), coalesce(wait_event_type,''), coalesce(wait_event,''), replace(left(query,200), E'\\t', ' ') FROM pg_stat_activity WHERE datname=current_database() AND pid<>pg_backend_pid() AND backend_type='client backend' ORDER BY pid"+ pure [Backend pid app state (nonEmpty waitType) (nonEmpty waitEvent) query | line <- Text.lines output, [pidText, app, state, waitType, waitEvent, query] <- [Text.splitOn "\x1f" line], Just pid <- [readText pidText]]++terminateBackends :: PostgresEnv -> BackendSelector -> Fault+terminateBackends postgres selector =+ Fault+ { name = "postgres-terminate-backends",+ target = "postgres",+ availability = pure Available,+ inject = do+ victims <- filter (matches selector) <$> listBackends postgres+ mapM_ (\backend -> voidPsql postgres ("SELECT pg_terminate_backend(" <> Text.pack (show backend.pid) <> ")")) victims+ pure (FaultHandle (pure ()) (object ["victims" .= fmap (.pid) victims]))+ }++terminateOneBackend :: PostgresEnv -> BackendSelector -> Fault+terminateOneBackend postgres selector =+ (terminateBackends postgres selector)+ { inject = do+ victims <- take 1 . filter (matches selector) <$> listBackends postgres+ mapM_ (\backend -> voidPsql postgres ("SELECT pg_terminate_backend(" <> Text.pack (show backend.pid) <> ")")) victims+ pure (FaultHandle (pure ()) (object ["victims" .= fmap (.pid) victims]))+ }++holdLock :: PostgresEnv -> LockTarget -> Fault+holdLock postgres target =+ Fault+ { name = "postgres-hold-lock",+ target = "postgres",+ availability = pure Available,+ inject = do+ let sql = "SELECT set_config('application_name','kenshou-fault-lock',false); BEGIN; " <> lockSql target <> "; SELECT pg_sleep(86400)"+ (_, _, _, processHandle) <- createProcess (proc "psql" ["-d", Text.unpack postgres.connectionString, "-v", "ON_ERROR_STOP=1", "-c", Text.unpack sql]) {std_out = NoStream, std_err = NoStream}+ threadDelay 100000+ let heal = voidPsql postgres "SELECT pg_terminate_backend(pid) FROM pg_stat_activity WHERE datname=current_database() AND application_name='kenshou-fault-lock'" >> void (waitForProcess processHandle)+ pure (FaultHandle heal (object ["target" .= show target]))+ }++hogConnections :: PostgresEnv -> Int -> Fault+hogConnections postgres count =+ Fault+ { name = "postgres-hog-connections",+ target = "postgres",+ availability = pure Available,+ inject = do+ handles <- replicateM count (spawnSleeper postgres)+ pure (FaultHandle (mapM_ killProcess handles) (object ["connections" .= count]))+ }++withStatementTimeout :: Int -> ProcessSpec -> ProcessSpec+withStatementTimeout millis spec = spec {env = upsert "PGOPTIONS" ("-c statement_timeout=" <> show millis) spec.env}++withApplicationName :: Text -> ProcessSpec -> ProcessSpec+withApplicationName applicationName spec = spec {env = upsert "PGAPPNAME" (Text.unpack applicationName) spec.env}++crashPostmaster :: PostgresEnv -> CrashMode -> Fault+crashPostmaster postgres mode =+ Fault+ { name = "postgres-crash-postmaster",+ target = "postgres-postmaster",+ availability = pure (maybe (Unavailable "PostgreSQL environment has no server control") (const Available) postgres.control),+ inject = case postgres.control of+ Nothing -> ioError (userError "PostgreSQL server control unavailable")+ Just control -> do+ control.stopServer (case mode of FastShutdown -> StopFast; _ -> StopImmediate)+ pure (FaultHandle control.startServer (object ["mode" .= show mode]))+ }++matches :: BackendSelector -> Backend -> Bool+matches selector backend = case selector of+ ByApplicationName pattern -> like pattern backend.applicationName+ ByQueryPattern pattern -> like pattern backend.query+ ByPid pid -> backend.pid == pid+ AllOtherBackends -> backend.applicationName /= "kenshou-fault"++like :: Text -> Text -> Bool+like pattern value+ | "%" `Text.isSuffixOf` pattern = Text.dropEnd 1 pattern `Text.isPrefixOf` value+ | otherwise = value == pattern++lockSql :: LockTarget -> Text+lockSql (TableLock schema table) = "LOCK TABLE " <> quote schema <> "." <> quote table <> " IN ACCESS EXCLUSIVE MODE"+lockSql (RowLock schema table) = "SELECT 1 FROM " <> quote schema <> "." <> quote table <> " LIMIT 1 FOR UPDATE"+lockSql (AdvisoryLock key) = "SELECT pg_advisory_xact_lock(" <> Text.pack (show key) <> ")"++quote :: Text -> Text+quote value = "\"" <> Text.replace "\"" "\"\"" value <> "\""++spawnSleeper :: PostgresEnv -> IO ProcessHandle+spawnSleeper postgres = do+ (_, _, _, handle) <- createProcess (proc "psql" ["-d", Text.unpack postgres.connectionString, "-c", "SELECT pg_sleep(86400)"]) {std_out = NoStream, std_err = NoStream}+ pure handle++psql :: PostgresEnv -> Text -> IO Text+psql postgres sql = do+ (code, output, err) <- readProcessWithExitCode "psql" ["-d", Text.unpack postgres.connectionString, "-At", "-F", "\x1f", "-v", "ON_ERROR_STOP=1", "-c", Text.unpack sql] ""+ case code of ExitSuccess -> pure (Text.stripEnd (Text.pack output)); ExitFailure _ -> ioError (userError err)++voidPsql :: PostgresEnv -> Text -> IO ()+voidPsql postgres sql = psql postgres sql >> pure ()++readText :: (Read value) => Text -> Maybe value+readText value = case reads (Text.unpack value) of [(parsed, "")] -> Just parsed; _ -> Nothing++nonEmpty :: Text -> Maybe Text+nonEmpty "" = Nothing+nonEmpty value = Just value++upsert :: (Eq key) => key -> value -> [(key, value)] -> [(key, value)]+upsert key value pairs = (key, value) : filter ((/= key) . fst) pairs++void :: IO value -> IO ()+void action = action >> pure ()++killProcess :: ProcessHandle -> IO ()+killProcess handle = do+ pid <- getPid handle+ maybe (terminateProcess handle) (signalProcess sigKILL) pid+ void (waitForProcess handle)
+ src/Kenshou/Check/Fault/Time.hs view
@@ -0,0 +1,36 @@+module Kenshou.Check.Fault.Time+ ( BackdateTarget (..),+ newVirtualNow,+ backdateRows,+ )+where++import Data.IORef+import Data.Int (Int64)+import Data.Text (Text)+import Data.Text qualified as Text+import Data.Time+import Kenshou.Core.Env.Postgres (PostgresEnv (..))+import System.Exit (ExitCode (..))+import System.Process (readProcessWithExitCode)++data BackdateTarget = BackdateTarget+ { table :: !Text,+ column :: !Text,+ predicate :: !Text+ }+ deriving stock (Eq, Show)++newVirtualNow :: IO (IO UTCTime, NominalDiffTime -> IO ())+newVirtualNow = do+ origin <- getCurrentTime+ offset <- newIORef 0+ pure ((addUTCTime <$> readIORef offset <*> pure origin), \delta -> modifyIORef' offset (+ delta))++backdateRows :: PostgresEnv -> BackdateTarget -> NominalDiffTime -> IO Int64+backdateRows postgres target amount = do+ let sql = "UPDATE " <> target.table <> " SET " <> target.column <> " = " <> target.column <> " - interval '" <> Text.pack (show (realToFrac amount :: Double)) <> " seconds' WHERE " <> target.predicate <> " RETURNING 1"+ (code, output, err) <- readProcessWithExitCode "psql" ["-d", Text.unpack postgres.adminConnectionString, "-Atqc", Text.unpack sql] ""+ case code of+ ExitSuccess -> pure (fromIntegral (length (lines output)))+ ExitFailure _ -> ioError (userError err)
+ src/Kenshou/Check/Fault/Wake.hs view
@@ -0,0 +1,35 @@+module Kenshou.Check.Fault.Wake+ ( WakeControl,+ WakePolicy (..),+ newWakeControl,+ setWakePolicy,+ faultyWait,+ )+where++import Control.Concurrent (threadDelay)+import Control.Concurrent.STM++data WakePolicy = PassThrough | DropAll | DropFraction Double | DelayMicros Int+ deriving stock (Eq, Show)++newtype WakeControl = WakeControl (TVar WakePolicy)++newWakeControl :: IO WakeControl+newWakeControl = WakeControl <$> newTVarIO PassThrough++setWakePolicy :: WakeControl -> WakePolicy -> IO ()+setWakePolicy (WakeControl policy) = atomically . writeTVar policy++faultyWait :: WakeControl -> (result -> Bool) -> result -> (Int -> IO result) -> Int -> IO result+faultyWait (WakeControl policy) isNotification timeoutResult wait timeoutMicros = do+ result <- wait timeoutMicros+ current <- readTVarIO policy+ if not (isNotification result)+ then pure result+ else case current of+ PassThrough -> pure result+ DropAll -> threadDelay timeoutMicros >> pure timeoutResult+ DropFraction fraction | fraction >= 1 -> threadDelay timeoutMicros >> pure timeoutResult+ DropFraction _ -> pure result+ DelayMicros delay -> threadDelay delay >> pure result
+ src/Kenshou/Check/Invariant.hs view
@@ -0,0 +1,262 @@+{-# LANGUAGE ExistentialQuantification #-}++module Kenshou.Check.Invariant+ ( CheckResult (..),+ CheckFold (..),+ Checker (..),+ DuplicateBudget (..),+ Deadline (..),+ runCheckers,+ evaluateChecker,+ noLoss,+ duplicatesWithin,+ perKeyOrder,+ globalOrder,+ gaplessPositions,+ exactlyNEffects,+ eventualQuiescence,+ monotonicCheckpoints,+ disjointOwnership,+ )+where++import Data.Aeson+import Data.Aeson.Key qualified as Key+import Data.Aeson.KeyMap qualified as KeyMap+import Data.Foldable (foldl')+import Data.Int (Int64)+import Data.List (groupBy, sort, sortOn)+import Data.Map.Strict (Map)+import Data.Map.Strict qualified as Map+import Data.Maybe (mapMaybe)+import Data.Scientific (toBoundedInteger)+import Data.Set (Set)+import Data.Set qualified as Set+import Data.Text (Text)+import Data.Time (getCurrentTime)+import Kenshou.Check.Fact+import Kenshou.Check.Ledger.Read+import Kenshou.Check.Ledger.Sort+import Kenshou.Check.Scenario+import Kenshou.Check.Verdict+import Kenshou.Check.Window+import System.FilePath ((</>))++data CheckResult = CheckResult+ { status :: !VerdictStatus,+ reason :: !(Maybe Text),+ summary :: !Text,+ counts :: !(Map Text Int64),+ parameters :: !Value,+ counterExamples :: ![Value]+ }+ deriving stock (Eq, Show)++data CheckFold = forall state. CheckFold+ { initial :: state,+ step :: state -> Fact -> state,+ finish :: state -> CheckResult+ }++data Checker = Checker+ { name :: !Text,+ invariant :: !Text,+ cls :: !InvariantClass,+ order :: !SortOrder,+ select :: Fact -> Bool,+ allowEmpty :: !Bool,+ fold :: !CheckFold+ }++data DuplicateBudget = DuplicateBudget+ { maxPerWindow :: !(Maybe Int),+ maxRedeliveryDelayMicros :: !(Maybe Int64)+ }+ deriving stock (Eq, Show)++newtype Deadline = Deadline {micros :: Int64}+ deriving stock (Eq, Ord, Show)++data Running = forall state. Running Checker state Int (state -> Fact -> state) (state -> CheckResult)++runCheckers :: CheckEnv -> LedgerSet -> [Checker] -> IO [Verdict]+runCheckers environment ledger checkers = concat <$> traverse runGroup grouped+ where+ grouped = groupBy (\left right -> left.order == right.order) (sortOn (.order) checkers)+ inputs = [InputRef segment.relativePath segment.sha256 | segment <- ledger.segments]+ runGroup [] = pure []+ runGroup group@(first : _) = do+ let running = fmap startChecker group+ config = defaultSortConfig (environment.ledgerDirectory </> ".sort")+ completed <- sortedFacts config first.order (const True) ledger (drain running)+ now <- getCurrentTime+ pure [toVerdict now inputs checker selected result | (checker, selected, result) <- fmap finishRunning completed]++evaluateChecker :: Checker -> [Fact] -> CheckResult+evaluateChecker checker facts =+ let (_, selected, result) = finishRunning (foldl' feed (startChecker checker) facts)+ in if selected == 0 && not checker.allowEmpty then vacuous else result++startChecker :: Checker -> Running+startChecker checker = case checker.fold of CheckFold initial step finish -> Running checker initial 0 step finish++feed :: Running -> Fact -> Running+feed (Running checker state selected step finish) fact+ | checker.select fact = Running checker (step state fact) (selected + 1) step finish+ | otherwise = Running checker state selected step finish++finishRunning :: Running -> (Checker, Int, CheckResult)+finishRunning (Running checker state selected _ finish) = (checker, selected, if selected == 0 && not checker.allowEmpty then vacuous else finish state)++drain :: [Running] -> FactSource -> IO [Running]+drain running source = source.next >>= \case Nothing -> pure running; Just fact -> drain (fmap (`feed` fact) running) source++toVerdict now inputs checker _selected result =+ Verdict checker.name checker.invariant checker.cls result.status result.reason result.summary result.counts result.parameters (take 20 result.counterExamples) (length result.counterExamples > 20) inputs Nothing now 0++vacuous :: CheckResult+vacuous = CheckResult NotEvaluated (Just "vacuous") "No relevant facts were observed." (Map.fromList [("examined", 0), ("violations", 0)]) Null []++result :: Text -> Int -> Int -> [Value] -> CheckResult+result summary examined violations examples =+ CheckResult+ (if violations == 0 then Held else Violated)+ Nothing+ summary+ (Map.fromList [("examined", fromIntegral examined), ("violations", fromIntegral violations)])+ (object [])+ examples++noLoss :: Text -> InvariantClass -> Text -> Checker+noLoss checkerName cls consumerScope =+ Checker checkerName "no-loss" cls ByKeySeq relevant False (CheckFold (Set.empty, Set.empty, Set.empty) step finish)+ where+ relevant fact = fact.kind `elem` [Intent, Produced, Observed]+ identity :: Fact -> (Text, Int64, Text)+ identity fact = (fact.key, fact.seq, fact.id)+ step (intents, produced, observed) fact = case fact.kind of+ Intent -> (Set.insert (identity fact) intents, produced, observed)+ Produced -> (intents, Set.insert (identity fact) produced, observed)+ Observed | fact.scope == consumerScope -> (intents, produced, Set.insert (identity fact) observed)+ _ -> (intents, produced, observed)+ finish :: (Set (Text, Int64, Text), Set (Text, Int64, Text), Set (Text, Int64, Text)) -> CheckResult+ finish (intents, produced, observed) =+ let missing = Set.toList (produced `Set.difference` observed)+ phantom = Set.toList (observed `Set.difference` intents)+ violations = length missing + length phantom+ examples = fmap (example "missing") missing <> fmap (example "phantom") phantom+ in result "Acknowledged items are observed and observations have intents." (Set.size produced + Set.size observed) violations examples++duplicatesWithin :: Text -> InvariantClass -> Text -> DuplicateBudget -> [DisturbanceWindow] -> Checker+duplicatesWithin checkerName cls consumerScope budget windows =+ Checker checkerName "duplicates-within-windows" cls ByKeySeq relevant False (CheckFold Map.empty step finish)+ where+ relevant fact = fact.kind == Observed && fact.scope == consumerScope+ identity fact = (fact.key, fact.seq, fact.id)+ step observations fact = Map.insertWith (<>) (identity fact) [fact] observations+ finish observations =+ let duplicates = [(key, sortOn (.wall) facts) | (key, facts) <- Map.toList observations, length facts > 1]+ classify (key, first : rest) =+ let extra = length rest+ windowed = any (\window -> first.wall <= maybe maxBound id window.end && any (\fact -> fact.wall >= window.start) rest) windows+ overBudget = maybe False (extra >) budget.maxPerWindow+ in (if windowed && not overBudget then 0 else extra, object ["item" .= showIdentity key, "duplicates" .= extra, "windowed" .= windowed])+ classify _ = (0, Null)+ classified = fmap classify duplicates+ violations = sum (fmap fst classified)+ base = result "Duplicates occur only inside declared disturbance budgets." (sum (fmap (length . snd) duplicates)) violations (fmap snd (filter ((> 0) . fst) classified))+ parameters = object ["maxPerWindow" .= budget.maxPerWindow, "maxRedeliveryDelayMicros" .= budget.maxRedeliveryDelayMicros]+ counts = Map.fromList [("examined", fromIntegral (sum (fmap (length . snd) duplicates))), ("violations", fromIntegral violations), ("duplicates", fromIntegral (sum [length facts - 1 | (_, facts) <- duplicates]))]+ in setCounts counts (setParameters parameters base)++perKeyOrder :: Text -> InvariantClass -> Text -> Checker+perKeyOrder checkerName cls consumerScope = orderChecker checkerName "per-key-order" cls ByScopeKeyArrival (\fact -> fact.scope == consumerScope) (\fact -> (fact.scope, fact.key)) (.seq)++globalOrder :: Text -> InvariantClass -> Text -> Text -> Checker+globalOrder checkerName cls consumerScope attribute = orderCheckerMaybe checkerName "global-order" cls ByScopeArrival (\fact -> fact.scope == consumerScope && fact.kind == Observed) (.scope) (attrInt attribute)++gaplessPositions :: Text -> InvariantClass -> Checker+gaplessPositions checkerName cls =+ Checker checkerName "gapless-positions" cls ByKeySeq (\fact -> fact.kind == Produced) False (CheckFold Set.empty (\seen fact -> Set.insert fact.seq seen) finish)+ where+ finish seen = case (Set.lookupMin seen, Set.lookupMax seen) of+ (Just low, Just high) ->+ let missing = [value | value <- [low .. high], Set.notMember value seen]+ in result "Acknowledged positions form a contiguous range." (Set.size seen) (length missing) (fmap (object . pure . ("missing" .=)) (take 20 missing))+ _ -> vacuous++exactlyNEffects :: Text -> InvariantClass -> Int -> Checker+exactlyNEffects checkerName cls expected =+ Checker checkerName "exactly-n-effects" cls ByKeySeq (\fact -> fact.kind == Effect) False (CheckFold Map.empty (\counts fact -> Map.insertWith (+) fact.id 1 counts) finish)+ where+ finish counts =+ let wrong = [(item, count) | (item, count) <- Map.toList counts, count /= expected]+ in setParameters (object ["expected" .= expected]) (result "Each idempotency key has exactly the expected number of effects." (sum (Map.elems counts)) (length wrong) [object ["id" .= item, "actual" .= count, "expected" .= expected] | (item, count) <- wrong])++eventualQuiescence :: Text -> InvariantClass -> Deadline -> Checker+eventualQuiescence checkerName cls deadline =+ Checker checkerName "eventual-quiescence" cls ByKeySeq (\fact -> fact.kind `elem` [Produced, Terminal]) False (CheckFold (Map.empty, Map.empty) step finish)+ where+ step (produced, terminal) fact = case fact.kind of+ Produced -> (Map.insert fact.id fact.wall produced, terminal)+ Terminal -> (produced, Map.insert fact.id fact.wall terminal)+ _ -> (produced, terminal)+ finish (produced, terminal) =+ let violations = [(item, started, Map.lookup item terminal) | (item, started) <- Map.toList produced, maybe True (> started + deadline.micros) (Map.lookup item terminal)]+ in setParameters (object ["deadlineMicros" .= deadline.micros]) (result "Every acknowledged item reaches a terminal state before its deadline." (Map.size produced) (length violations) [object ["id" .= item, "producedAt" .= started, "terminalAt" .= ended] | (item, started, ended) <- violations])++monotonicCheckpoints :: Text -> InvariantClass -> Checker+monotonicCheckpoints checkerName cls = orderChecker checkerName "monotonic-checkpoints" cls ByScopeArrival (\fact -> fact.kind == Checkpoint) (.key) (.seq)++disjointOwnership :: Text -> InvariantClass -> Checker+disjointOwnership checkerName cls =+ Checker checkerName "disjoint-ownership" cls ByKeyWall relevant False (CheckFold (Map.empty, []) step finish)+ where+ relevant fact = fact.kind `elem` [Acquired, Acted, Released]+ step (owners, violations) fact = case fact.kind of+ Acquired -> (Map.insertWith Set.union fact.key (Set.singleton fact.scope) owners, violations)+ Released -> (Map.adjust (Set.delete fact.scope) fact.key owners, violations)+ Acted ->+ let active = Map.findWithDefault Set.empty fact.key owners+ in if Set.null active || active == Set.singleton fact.scope then (owners, violations) else (owners, fact : violations)+ _ -> (owners, violations)+ finish (_, violations) = result "No owner acts while another owner holds the same lease." (length violations + 1) (length violations) (fmap factExample violations)++orderChecker :: (Ord group) => Text -> Text -> InvariantClass -> SortOrder -> (Fact -> Bool) -> (Fact -> group) -> (Fact -> Int64) -> Checker+orderChecker checkerName invariantName cls order select group value =+ Checker checkerName invariantName cls order select False (CheckFold Map.empty (\groups fact -> Map.insertWith (<>) (group fact) [value fact] groups) finish)+ where+ finish groups =+ let sequences = fmap reverse (Map.elems groups)+ violations = sum (fmap inversions sequences)+ in result ("Observed values are monotonic for " <> invariantName <> ".") (sum (fmap length sequences)) violations []++orderCheckerMaybe :: (Ord group) => Text -> Text -> InvariantClass -> SortOrder -> (Fact -> Bool) -> (Fact -> group) -> (Fact -> Maybe Int64) -> Checker+orderCheckerMaybe checkerName invariantName cls order select group value =+ Checker checkerName invariantName cls order select False (CheckFold Map.empty step finish)+ where+ step groups fact = maybe groups (\item -> Map.insertWith (<>) (group fact) [item] groups) (value fact)+ finish groups =+ let sequences = fmap reverse (Map.elems groups)+ violations = sum (fmap inversions sequences)+ in result ("Observed values are monotonic for " <> invariantName <> ".") (sum (fmap length sequences)) violations []++inversions :: [Int64] -> Int+inversions values = length [() | (left, right) <- zip values (drop 1 values), right < left]++attrInt :: Text -> Fact -> Maybe Int64+attrInt attribute fact = case KeyMap.lookup (Key.fromText attribute) fact.attrs of Just (Number value) -> toBoundedInteger value; _ -> Nothing++factExample :: Fact -> Value+factExample fact = object ["kind" .= fact.kind, "key" .= fact.key, "seq" .= fact.seq, "id" .= fact.id, "scope" .= fact.scope]++example :: Text -> (Text, Int64, Text) -> Value+example label (key, sequenceNumber, item) = object ["type" .= label, "key" .= key, "seq" .= sequenceNumber, "id" .= item]++showIdentity (key, sequenceNumber, item) = object ["key" .= key, "seq" .= sequenceNumber, "id" .= item]++setParameters :: Value -> CheckResult -> CheckResult+setParameters parameters (CheckResult status reason summary counts _ counterExamples) = CheckResult status reason summary counts parameters counterExamples++setCounts :: Map Text Int64 -> CheckResult -> CheckResult+setCounts counts (CheckResult status reason summary _ parameters counterExamples) = CheckResult status reason summary counts parameters counterExamples
+ src/Kenshou/Check/Invariant/Checkpoint.hs view
@@ -0,0 +1,3 @@+module Kenshou.Check.Invariant.Checkpoint (monotonicCheckpoints) where++import Kenshou.Check.Invariant (monotonicCheckpoints)
+ src/Kenshou/Check/Invariant/Duplicates.hs view
@@ -0,0 +1,3 @@+module Kenshou.Check.Invariant.Duplicates (DuplicateBudget (..), duplicatesWithin) where++import Kenshou.Check.Invariant (DuplicateBudget (..), duplicatesWithin)
+ src/Kenshou/Check/Invariant/Effects.hs view
@@ -0,0 +1,3 @@+module Kenshou.Check.Invariant.Effects (exactlyNEffects) where++import Kenshou.Check.Invariant (exactlyNEffects)
+ src/Kenshou/Check/Invariant/Gapless.hs view
@@ -0,0 +1,3 @@+module Kenshou.Check.Invariant.Gapless (gaplessPositions) where++import Kenshou.Check.Invariant (gaplessPositions)
+ src/Kenshou/Check/Invariant/NoLoss.hs view
@@ -0,0 +1,3 @@+module Kenshou.Check.Invariant.NoLoss (noLoss) where++import Kenshou.Check.Invariant (noLoss)
+ src/Kenshou/Check/Invariant/Order.hs view
@@ -0,0 +1,3 @@+module Kenshou.Check.Invariant.Order (perKeyOrder, globalOrder) where++import Kenshou.Check.Invariant (globalOrder, perKeyOrder)
+ src/Kenshou/Check/Invariant/Ownership.hs view
@@ -0,0 +1,3 @@+module Kenshou.Check.Invariant.Ownership (disjointOwnership) where++import Kenshou.Check.Invariant (disjointOwnership)
+ src/Kenshou/Check/Invariant/Quiescence.hs view
@@ -0,0 +1,3 @@+module Kenshou.Check.Invariant.Quiescence (Deadline (..), eventualQuiescence) where++import Kenshou.Check.Invariant (Deadline (..), eventualQuiescence)
+ src/Kenshou/Check/Ledger.hs view
@@ -0,0 +1,198 @@+module Kenshou.Check.Ledger+ ( ClockSource (..),+ ClockInfo (..),+ LedgerHeader (..),+ LedgerConfig (..),+ LedgerWriter,+ defaultLedgerConfig,+ withLedger,+ record,+ recordDurable,+ flushLedger,+ sealLedger,+ )+where++import Control.Concurrent.MVar+import Control.Exception (bracket)+import Data.Aeson+import Data.Aeson.KeyMap (KeyMap)+import Data.Aeson.Types (Parser)+import Data.ByteString.Lazy qualified as LazyByteString+import Data.Int (Int64)+import Data.Text (Text)+import Data.Text qualified as Text+import Data.Time.Clock.POSIX (getPOSIXTime)+import Data.Word (Word64)+import GHC.Clock (getMonotonicTimeNSec)+import Kenshou.Check.Fact+import System.Directory (createDirectoryIfMissing)+import System.Environment (lookupEnv)+import System.FilePath ((</>))+import System.IO+import System.Posix.Process (getProcessID)++data ClockSource = SameHost | Measured | Assumed deriving stock (Eq, Show)++data ClockInfo = ClockInfo+ { source :: !ClockSource,+ skewBoundMicros :: !Int64+ }+ deriving stock (Eq, Show)++data LedgerHeader = LedgerHeader+ { runId :: !Text,+ proc :: !ProcId,+ pid :: !Int,+ host :: !Text,+ startedWall :: !Int64,+ startedMono :: !Word64,+ clock :: !ClockInfo+ }+ deriving stock (Eq, Show)++data LedgerConfig = LedgerConfig+ { directory :: !FilePath,+ proc :: !ProcId,+ runId :: !Text,+ segmentBytes :: !Int,+ clock :: !ClockInfo+ }+ deriving stock (Eq, Show)++data WriterState = WriterState+ { handle :: !(Maybe Handle),+ directory :: !FilePath,+ segmentLimit :: !Int,+ segment :: !Int,+ bytes :: !Int,+ counter :: !Word64,+ header :: !LedgerHeader+ }++newtype LedgerWriter = LedgerWriter (MVar WriterState)++defaultLedgerConfig :: FilePath -> ProcId -> Text -> LedgerConfig+defaultLedgerConfig directory proc runId = LedgerConfig directory proc runId (64 * 1024 * 1024) (ClockInfo SameHost 1000)++withLedger :: LedgerConfig -> (LedgerWriter -> IO value) -> IO value+withLedger config action = bracket (openWriter config) closeWriter action++record :: LedgerWriter -> FactKind -> Text -> Int64 -> Text -> KeyMap Value -> IO ()+record = recordWith False++recordDurable :: LedgerWriter -> FactKind -> Text -> Int64 -> Text -> KeyMap Value -> IO ()+recordDurable = recordWith True++flushLedger :: LedgerWriter -> IO ()+flushLedger (LedgerWriter state) = withMVar state (maybe (pure ()) hFlush . (.handle))++sealLedger :: LedgerWriter -> IO ()+sealLedger (LedgerWriter state) = modifyMVar_ state \current -> do+ case current.handle of+ Nothing -> pure current+ Just handle -> hFlush handle >> hClose handle >> pure current {handle = Nothing}++openWriter :: LedgerConfig -> IO LedgerWriter+openWriter config = do+ createDirectoryIfMissing True config.directory+ startedWall <- wallMicros+ startedMono <- getMonotonicTimeNSec+ pid <- fromIntegral <$> getProcessID+ host <- Text.pack . maybe "unknown" id <$> lookupEnv "HOSTNAME"+ let header = LedgerHeader config.runId config.proc pid host startedWall startedMono config.clock+ (handle, bytes) <- openSegment config header 1+ LedgerWriter <$> newMVar (WriterState (Just handle) config.directory config.segmentBytes 1 bytes 0 header)++closeWriter :: LedgerWriter -> IO ()+closeWriter = sealLedger++recordWith :: Bool -> LedgerWriter -> FactKind -> Text -> Int64 -> Text -> KeyMap Value -> IO ()+recordWith durable (LedgerWriter state) kind key sequenceNumber itemId attrs = modifyMVar_ state \current -> do+ currentHandle <- maybe (ioError (userError "record: ledger is sealed")) pure current.handle+ mono <- getMonotonicTimeNSec+ wall <- wallMicros+ let nextCounter = current.counter + 1+ proc = current.header.proc+ scope = proc.role <> "/" <> Text.pack (show proc.index)+ fact = Fact kind key sequenceNumber itemId scope proc nextCounter mono wall attrs+ line = encode fact <> "\n"+ lineBytes = fromIntegral (LazyByteString.length line)+ rotated <-+ if current.counter > 0 && current.bytes + lineBytes > max 1 current.segmentLimit+ then do+ hFlush currentHandle+ hClose currentHandle+ let nextSegment = current.segment + 1+ (nextHandle, headerBytes) <- openSegmentAt current.directory current.segmentLimit current.header nextSegment+ pure current {handle = Just nextHandle, segment = nextSegment, bytes = headerBytes}+ else pure current+ rotatedHandle <- maybe (ioError (userError "record: ledger is sealed")) pure rotated.handle+ LazyByteString.hPut rotatedHandle line+ if durable then hFlush rotatedHandle else pure ()+ pure rotated {bytes = rotated.bytes + lineBytes, counter = nextCounter}++openSegment :: LedgerConfig -> LedgerHeader -> Int -> IO (Handle, Int)+openSegment config header segment = openSegmentAt config.directory config.segmentBytes header segment++openSegmentAt :: FilePath -> Int -> LedgerHeader -> Int -> IO (Handle, Int)+openSegmentAt directory _limit header segment = do+ let path = directory </> segmentName header.proc segment+ handle <- openBinaryFile path WriteMode+ hSetBuffering handle (BlockBuffering (Just (64 * 1024)))+ let line = encode header <> "\n"+ LazyByteString.hPut handle line+ pure (handle, fromIntegral (LazyByteString.length line))++segmentName :: ProcId -> Int -> FilePath+segmentName proc segment =+ Text.unpack (Text.replace "/" "-" proc.role)+ <> "-"+ <> show proc.index+ <> "."+ <> show proc.incarnation+ <> "."+ <> pad4 segment+ <> ".jsonl"+ where+ pad4 number = replicate (max 0 (4 - length rendered)) '0' <> rendered where rendered = show number++wallMicros :: IO Int64+wallMicros = round . (* 1000000) <$> getPOSIXTime++clockSourceText :: ClockSource -> Text+clockSourceText SameHost = "same-host"+clockSourceText Measured = "measured"+clockSourceText Assumed = "assumed"++instance ToJSON ClockInfo where+ toJSON value = object ["source" .= clockSourceText value.source, "skewBoundMicros" .= value.skewBoundMicros]++instance FromJSON ClockInfo where+ parseJSON = withObject "ClockInfo" \value -> do+ rawSource <- value .: "source" :: Parser Text+ source <- case rawSource of+ "same-host" -> pure SameHost+ "measured" -> pure Measured+ "assumed" -> pure Assumed+ _ -> fail "unknown clock source"+ ClockInfo source <$> value .: "skewBoundMicros"++instance ToJSON LedgerHeader where+ toJSON value =+ object+ [ "schema" .= ("kenshou.ledger/v1" :: Text),+ "runId" .= value.runId,+ "proc" .= value.proc,+ "pid" .= value.pid,+ "host" .= value.host,+ "startedWall" .= value.startedWall,+ "startedMono" .= value.startedMono,+ "clock" .= value.clock+ ]++instance FromJSON LedgerHeader where+ parseJSON = withObject "LedgerHeader" \value -> do+ schema <- value .: "schema"+ if schema /= ("kenshou.ledger/v1" :: Text) then fail "unsupported ledger schema" else pure ()+ LedgerHeader <$> value .: "runId" <*> value .: "proc" <*> value .: "pid" <*> value .: "host" <*> value .: "startedWall" <*> value .: "startedMono" <*> value .: "clock"
+ src/Kenshou/Check/Ledger/Read.hs view
@@ -0,0 +1,111 @@+module Kenshou.Check.Ledger.Read+ ( FactSource (..),+ SegmentRef (..),+ LedgerSet (..),+ LedgerReadError (..),+ openSegment,+ discoverLedgers,+ foldFacts,+ )+where++import Control.Exception (Exception, catch, throwIO)+import Control.Monad (foldM)+import Data.Aeson (eitherDecodeStrict')+import Data.ByteString qualified as ByteString+import Data.ByteString.Char8 qualified as ByteString.Char8+import Data.List (sort)+import Data.Text (Text)+import Data.Text qualified as Text+import Kenshou.Check.Fact (Fact)+import Kenshou.Check.Ledger (LedgerHeader)+import Kenshou.Core.Canonical (sha256Hex)+import System.Directory (doesDirectoryExist, doesFileExist, listDirectory)+import System.FilePath (makeRelative, takeExtension, (</>))+import System.IO+import System.IO.Error (isEOFError)++newtype FactSource = FactSource {next :: IO (Maybe Fact)}++data SegmentRef = SegmentRef+ { path :: !FilePath,+ relativePath :: !FilePath,+ sha256 :: !Text,+ bytes :: !Integer+ }+ deriving stock (Eq, Show)++newtype LedgerSet = LedgerSet {segments :: [SegmentRef]}+ deriving stock (Eq, Show)++newtype LedgerReadError = LedgerReadError Text deriving stock (Eq, Show)++instance Exception LedgerReadError++openSegment :: FilePath -> IO (LedgerHeader, FactSource)+openSegment path = do+ handle <- openBinaryFile path ReadMode+ hSetBuffering handle (BlockBuffering (Just (64 * 1024)))+ endsWithNewline <- fileEndsWithNewline handle+ headerLine <- ByteString.Char8.hGetLine handle+ header <- either (throwIO . LedgerReadError . Text.pack) pure (eitherDecodeStrict' headerLine)+ pure (header, FactSource (readNext handle endsWithNewline))+ where+ readNext handle endsWithNewline = do+ done <- hIsEOF handle+ if done+ then hClose handle >> pure Nothing+ else do+ let readLine = do+ line <- ByteString.Char8.hGetLine handle+ atEnd <- hIsEOF handle+ if atEnd && not endsWithNewline+ then hClose handle >> pure Nothing+ else case eitherDecodeStrict' line of+ Right fact -> pure (Just fact)+ Left err -> hClose handle >> throwIO (LedgerReadError (Text.pack path <> ": " <> Text.pack err))+ readLine `catch` \err ->+ if isEOFError err && not endsWithNewline+ then hClose handle >> pure Nothing+ else throwIO (err :: IOError)++discoverLedgers :: FilePath -> IO LedgerSet+discoverLedgers root = do+ exists <- doesDirectoryExist root+ if not exists+ then pure (LedgerSet [])+ else do+ names <- sort <$> listDirectory root+ paths <- filterMFile [root </> name | name <- names, takeExtension name == ".jsonl"]+ LedgerSet <$> traverse describe paths+ where+ filterMFile [] = pure []+ filterMFile (path : rest) = do+ file <- doesFileExist path+ others <- filterMFile rest+ pure (if file then path : others else others)+ describe path = do+ contents <- ByteString.readFile path+ pure (SegmentRef path (makeRelative root path) (sha256Hex contents) (fromIntegral (ByteString.length contents)))++foldFacts :: LedgerSet -> state -> (state -> Fact -> IO state) -> IO state+foldFacts ledger initial step = foldM foldSegment initial ledger.segments+ where+ foldSegment state segment = do+ (_, source) <- openSegment segment.path+ go state source+ go state source =+ source.next >>= \case+ Nothing -> pure state+ Just fact -> step state fact >>= (`go` source)++fileEndsWithNewline :: Handle -> IO Bool+fileEndsWithNewline handle = do+ size <- hFileSize handle+ if size == 0+ then pure False+ else do+ hSeek handle SeekFromEnd (-1)+ byte <- ByteString.hGet handle 1+ hSeek handle AbsoluteSeek 0+ pure (byte == ByteString.Char8.pack "\n")
+ src/Kenshou/Check/Ledger/Sort.hs view
@@ -0,0 +1,132 @@+module Kenshou.Check.Ledger.Sort+ ( SortOrder (..),+ SortConfig (..),+ defaultSortConfig,+ sortedFacts,+ )+where++import Control.Exception (bracket)+import Control.Monad (foldM, unless)+import Data.Aeson (eitherDecodeStrict', encode)+import Data.ByteString.Char8 qualified as ByteString+import Data.ByteString.Lazy.Char8 qualified as LazyByteString+import Data.IORef+import Data.List (minimumBy, sortBy)+import Data.Ord (comparing)+import Kenshou.Check.Fact+import Kenshou.Check.Ledger.Read+import System.Directory (createDirectoryIfMissing, listDirectory, removeFile)+import System.FilePath ((</>))+import System.IO++data SortOrder = ByKeySeq | ByScopeKeyArrival | ByScopeArrival | ByKeyWall+ deriving stock (Eq, Ord, Show)++data SortConfig = SortConfig+ { directory :: !FilePath,+ runRecords :: !Int,+ mergeFanIn :: !Int+ }+ deriving stock (Eq, Show)++defaultSortConfig :: FilePath -> SortConfig+defaultSortConfig directory = SortConfig directory 200000 64++sortedFacts :: SortConfig -> SortOrder -> (Fact -> Bool) -> LedgerSet -> (FactSource -> IO value) -> IO value+sortedFacts config order select ledger action = bracket prepare cleanup (action <=< sourceFor)+ where+ prepare = do+ createDirectoryIfMissing True config.directory+ counter <- newIORef (0 :: Int)+ chunks <- buildRuns counter [] [] 0 ledger.segments+ collapse counter chunks+ cleanup finalPath = do+ names <- listDirectory config.directory+ mapM_ (removeFile . (config.directory </>)) names+ unless (null finalPath) (pure ())+ sourceFor "" = pure (FactSource (pure Nothing))+ sourceFor path = openRun path++ buildRuns counter paths chunk size [] = flushChunk counter paths chunk size+ buildRuns counter paths chunk size (segment : rest) = do+ (_, source) <- openSegment segment.path+ (paths', chunk', size') <- consume counter paths chunk size source+ buildRuns counter paths' chunk' size' rest++ consume counter paths chunk size source =+ source.next >>= \case+ Nothing -> pure (paths, chunk, size)+ Just fact+ | not (select fact) -> consume counter paths chunk size source+ | size + 1 >= max 1 config.runRecords -> do+ paths' <- flushChunk counter paths (fact : chunk) (size + 1)+ consume counter paths' [] 0 source+ | otherwise -> consume counter paths (fact : chunk) (size + 1) source++ flushChunk _ paths [] _ = pure paths+ flushChunk counter paths chunk _ = do+ path <- freshPath counter+ writeFacts path (sortBy (compareFact order) chunk)+ pure (paths <> [path])++ collapse _ [] = pure ""+ collapse _ [path] = pure path+ collapse counter paths = do+ merged <- traverse (mergeGroup counter) (chunksOf (max 2 config.mergeFanIn) paths)+ mapM_ removeFile paths+ collapse counter merged++ mergeGroup counter paths = do+ target <- freshPath counter+ sources <- traverse openRun paths+ mergeSources order target sources+ pure target++ freshPath counter = do+ number <- atomicModifyIORef' counter (\value -> (value + 1, value + 1))+ pure (config.directory </> ("run-" <> pad6 number <> ".jsonl"))++ pad6 number = replicate (max 0 (6 - length rendered)) '0' <> rendered where rendered = show number++compareFact :: SortOrder -> Fact -> Fact -> Ordering+compareFact ByKeySeq = comparing (\fact -> (fact.key, fact.seq, fact.kind, fact.wall, fact.n))+compareFact ByScopeKeyArrival = comparing (\fact -> (fact.scope, fact.key, fact.proc.incarnation, fact.n))+compareFact ByScopeArrival = comparing (\fact -> (fact.scope, fact.proc.incarnation, fact.n))+compareFact ByKeyWall = comparing (\fact -> (fact.key, fact.wall, fact.scope, fact.n))++writeFacts :: FilePath -> [Fact] -> IO ()+writeFacts path facts = withBinaryFile path WriteMode \handle -> mapM_ (LazyByteString.hPutStrLn handle . encode) facts++openRun :: FilePath -> IO FactSource+openRun path = do+ handle <- openBinaryFile path ReadMode+ pure (FactSource (nextFact handle))+ where+ nextFact handle = do+ done <- hIsEOF handle+ if done+ then hClose handle >> pure Nothing+ else do+ line <- ByteString.hGetLine handle+ either (ioError . userError) (pure . Just) (eitherDecodeStrict' line)++mergeSources :: SortOrder -> FilePath -> [FactSource] -> IO ()+mergeSources order path sources = withBinaryFile path WriteMode \handle -> do+ heads <- traverse (\source -> (source,) <$> source.next) sources+ go handle heads+ where+ go _ heads | all (maybe True (const False) . snd) heads = pure ()+ go handle heads = do+ let candidates = [(index, source, fact) | (index, (source, Just fact)) <- zip [0 :: Int ..] heads]+ (chosenIndex, chosenSource, chosenFact) = minimumBy (\(_, _, left) (_, _, right) -> compareFact order left right) candidates+ LazyByteString.hPutStrLn handle (encode chosenFact)+ replacement <- chosenSource.next+ go handle [if index == chosenIndex then (source, replacement) else pair | (index, pair@(source, _)) <- zip [0 :: Int ..] heads]++chunksOf :: Int -> [value] -> [[value]]+chunksOf _ [] = []+chunksOf size values = first : chunksOf size rest where (first, rest) = splitAt size values++(<=<) :: (b -> IO c) -> (a -> IO b) -> a -> IO c+(<=<) left right value = right value >>= left
+ src/Kenshou/Check/Model.hs view
@@ -0,0 +1,87 @@+{-# LANGUAGE RankNTypes #-}++module Kenshou.Check.Model+ ( ModelRun (..),+ runModel,+ sequentialProperty,+ parallelProperty,+ )+where++import Data.Aeson (object, (.=))+import Data.Map.Strict qualified as Map+import Data.Text (Text)+import Data.Text qualified as Text+import Data.Time (diffUTCTime, getCurrentTime)+import Hedgehog (Gen, PropertyT, Range, forAll)+import Hedgehog qualified+import Hedgehog.Internal.Property (Property (..), ShrinkPath (..), defaultConfig, withTests)+import Hedgehog.Internal.Report (FailedAnnotation (..), FailureReport (..), Report (..), Result (..))+import Hedgehog.Internal.Runner (checkReport)+import Hedgehog.Internal.Seed qualified as HedgehogSeed+import Hedgehog.Internal.State (Command)+import Hedgehog.Internal.State qualified as State+import Kenshou.Check.Scenario+import Kenshou.Check.Verdict+import Kenshou.Core.Context (RunContext (..))+import Kenshou.Core.Id (renderScenarioId, unSeed)++data ModelRun = ModelRun+ { name :: !Text,+ cls :: !InvariantClass,+ tests :: !Int,+ size :: !Int,+ property :: !(PropertyT IO ())+ }++runModel :: CheckEnv -> ModelRun -> IO Verdict+runModel environment model = do+ started <- getCurrentTime+ let runSeed = unSeed environment.context.seed+ derived = deriveSeed runSeed model.name+ configured = withTests (fromIntegral model.tests) (Property defaultConfig model.property)+ report <- checkReport configured.propertyConfig (fromIntegral model.size) (HedgehogSeed.from derived) configured.propertyTest (const (pure ()))+ ended <- getCurrentTime+ let duration = floor (diffUTCTime ended started * 1000)+ replayCommand = "kenshou run " <> renderScenarioId environment.context.scenario <> " --seed " <> Text.pack (show runSeed)+ base status reason summary counterExamples replay =+ Verdict+ model.name+ "model-property"+ model.cls+ status+ reason+ summary+ (Map.fromList [("tests", fromIntegral report.reportTests), ("examined", fromIntegral report.reportTests), ("violations", if status == Violated then 1 else 0)])+ (object ["derivedSeed" .= derived, "size" .= model.size])+ counterExamples+ False+ []+ replay+ ended+ duration+ pure case report.reportStatus of+ OK -> base Held Nothing "The model property held." [] Nothing+ GaveUp -> base NotEvaluated (Just "gave-up") "The model property exhausted its discard limit." [] Nothing+ Failed failure ->+ let ShrinkPath shrinkPath = failure.failureShrinkPath+ counterExample =+ object+ [ "message" .= failure.failureMessage,+ "annotations" .= fmap (.failedValue) failure.failureAnnotations,+ "footnotes" .= failure.failureFootnotes,+ "shrinks" .= show failure.failureShrinks,+ "shrinkPath" .= shrinkPath+ ]+ replay = Replay (fromIntegral runSeed) model.size shrinkPath replayCommand+ in base Violated Nothing "The model property found a reproducible counter-example." [counterExample] (Just replay)++sequentialProperty :: (forall variable. state variable) -> Range Int -> [Command Gen (PropertyT IO) state] -> PropertyT IO ()+sequentialProperty initial range commands = do+ actions <- forAll (State.sequential range initial commands)+ Hedgehog.executeSequential initial actions++parallelProperty :: (forall variable. state variable) -> Range Int -> Range Int -> [Command Gen (PropertyT IO) state] -> PropertyT IO ()+parallelProperty initial prefixRange branchRange commands = do+ actions <- forAll (State.parallel prefixRange branchRange initial commands)+ Hedgehog.executeParallel initial actions
+ src/Kenshou/Check/Model/Linearizability.hs view
@@ -0,0 +1,148 @@+module Kenshou.Check.Model.Linearizability+ ( Completion (..),+ Operation (..),+ SeqModel (..),+ LinConfig (..),+ LinResult (..),+ RegisterOp (..),+ RegisterResult (..),+ LogOp (..),+ LogResult (..),+ defaultLinConfig,+ checkLinearizable,+ registerModel,+ appendLogModel,+ linearizability,+ )+where++import Data.Aeson (object, (.=))+import Data.Int (Int64)+import Data.Map.Strict qualified as Map+import Data.Set (Set)+import Data.Set qualified as Set+import Data.Text (Text)+import Kenshou.Check.Fact (Fact)+import Kenshou.Check.Invariant+import Kenshou.Check.Ledger.Sort (SortOrder (ByKeyWall))+import Kenshou.Check.Verdict++data Completion output = Returned output | Failed | Indeterminate+ deriving stock (Eq, Ord, Show)++data Operation input output = Operation+ { process :: !Text,+ key :: !Text,+ input :: !input,+ invoked :: !Int64,+ completed :: !(Maybe Int64),+ completion :: !(Completion output)+ }+ deriving stock (Eq, Ord, Show)++data SeqModel state input output = SeqModel+ { initial :: !state,+ apply :: state -> input -> (output, state),+ agrees :: output -> output -> Bool+ }++newtype LinConfig = LinConfig {maxSteps :: Int}+ deriving stock (Eq, Ord, Show)++data LinResult = Linearizable | NotLinearizable [Text] | Undecided+ deriving stock (Eq, Show)++data RegisterOp = ReadRegister | WriteRegister Int64 | CompareAndSet (Maybe Int64) Int64+ deriving stock (Eq, Ord, Show)++data RegisterResult = ReadValue (Maybe Int64) | Written | Compared Bool+ deriving stock (Eq, Ord, Show)++data LogOp = Append Text | ReadLog+ deriving stock (Eq, Ord, Show)++data LogResult = Appended Int | LogContents [Text]+ deriving stock (Eq, Ord, Show)++defaultLinConfig :: LinConfig+defaultLinConfig = LinConfig 5000000++checkLinearizable :: (Ord state) => LinConfig -> SeqModel state input output -> [Operation input output] -> LinResult+checkLinearizable config model operations =+ case search 0 Set.empty model.initial indexed of+ SearchYes -> Linearizable+ SearchBudget -> Undecided+ SearchNo -> NotLinearizable ["No legal sequential history agrees with the completed operations."]+ where+ indexed = [(index, operation) | (index, operation) <- zip [0 :: Int ..] operations, isPending operation]+ isPending operation = case operation.completion of Failed -> False; _ -> True++ search steps visited state pending+ | steps >= config.maxSteps = SearchBudget+ | null pending = SearchYes+ | Set.member (Set.fromList (fmap fst pending), state) visited = SearchNo+ | otherwise =+ let visited' = Set.insert (Set.fromList (fmap fst pending), state) visited+ choices = filter (eligible . snd) pending+ outcomes = concatMap (advance (steps + 1) visited' state pending) choices+ in combine outcomes+ where+ eligible candidate = all (not . happensBefore candidate . snd) pending++ happensBefore candidate other = case other.completed of+ Just ended -> ended < candidate.invoked+ Nothing -> False++ advance steps visited state pending selected@(index, operation) =+ let remaining = filter ((/= index) . fst) pending+ (expected, nextState) = model.apply state operation.input+ applied = search steps visited nextState remaining+ in case operation.completion of+ Returned actual | model.agrees expected actual -> [applied]+ Returned _ -> []+ Failed -> [search steps visited state remaining]+ Indeterminate -> [search steps visited state remaining, applied]++ combine outcomes+ | SearchYes `elem` outcomes = SearchYes+ | SearchBudget `elem` outcomes = SearchBudget+ | otherwise = SearchNo++registerModel :: SeqModel (Maybe Int64) RegisterOp RegisterResult+registerModel = SeqModel Nothing applyRegister (==)+ where+ applyRegister state ReadRegister = (ReadValue state, state)+ applyRegister _ (WriteRegister value) = (Written, Just value)+ applyRegister state (CompareAndSet expected replacement)+ | state == expected = (Compared True, Just replacement)+ | otherwise = (Compared False, state)++appendLogModel :: SeqModel [Text] LogOp LogResult+appendLogModel = SeqModel [] applyLog (==)+ where+ applyLog state (Append value) = (Appended (length state), state <> [value])+ applyLog state ReadLog = (LogContents state, state)++linearizability :: (Ord state) => Text -> InvariantClass -> SeqModel state input output -> (Fact -> Maybe (Operation input output)) -> Checker+linearizability checkerName cls model decode =+ Checker checkerName "linearizability" cls ByKeyWall (maybe False (const True) . decode) False (CheckFold [] step finish)+ where+ step operations fact = maybe operations (: operations) (decode fact)+ finish reversed =+ let operations = reverse reversed+ byKey = Map.elems (Map.fromListWith (<>) [(operation.key, [operation]) | operation <- operations])+ results = fmap (checkLinearizable defaultLinConfig model) byKey+ violations = length [() | NotLinearizable _ <- results]+ undecided = any (== Undecided) results+ status | undecided = NotEvaluated | violations > 0 = Violated | otherwise = Held+ reason = if undecided then Just "search-budget-exhausted" else Nothing+ in CheckResult+ status+ reason+ "Completed operations admit a legal sequential history per key."+ (Map.fromList [("examined", fromIntegral (length operations)), ("violations", fromIntegral violations)])+ (object ["maxSteps" .= defaultLinConfig.maxSteps])+ [object ["reason" .= reasons] | NotLinearizable reasons <- results]++data SearchResult = SearchYes | SearchNo | SearchBudget+ deriving stock (Eq, Show)
+ src/Kenshou/Check/Oracle.hs view
@@ -0,0 +1,108 @@+module Kenshou.Check.Oracle+ ( OracleQuery (..),+ OracleResult (..),+ ItemRef (..),+ QuiescenceResult (..),+ runOracle,+ sampleOracle,+ reconcile,+ awaitQuiescence,+ OracleSpec (..),+ fromSpec,+ registeredOracle,+ )+where++import Control.Concurrent (threadDelay)+import Data.Aeson+import Data.ByteString.Lazy qualified as LazyByteString+import Data.Int (Int64)+import Data.Map.Strict qualified as Map+import Data.Text (Text)+import Data.Text qualified as Text+import Data.Time (getCurrentTime)+import Kenshou.Check.Fact+import Kenshou.Check.Invariant+import Kenshou.Check.Ledger+import Kenshou.Check.Ledger.Sort (SortOrder (ByKeySeq))+import Kenshou.Check.Verdict+import Kenshou.Core.Bundle (LayerBundle (..), Registry, lookupBundle)+import Kenshou.Core.Contribution (OracleSpec (..))+import Kenshou.Core.Env.Postgres (PostgresEnv (..))+import Kenshou.Core.Id (LayerId)+import System.Directory (createDirectoryIfMissing)+import System.Exit (ExitCode (..))+import System.FilePath ((</>))+import System.Process (readProcessWithExitCode)++data OracleQuery value = OracleQuery+ { name :: !Text,+ sql :: !Text,+ decode :: Text -> Either Text value+ }++data OracleResult value = OracleResult+ { query :: !Text,+ rows :: !value,+ path :: !FilePath+ }+ deriving stock (Eq, Show)++data ItemRef = ItemRef {key :: !Text, seq :: !Int64, id :: !Text}+ deriving stock (Eq, Ord, Show)++data QuiescenceResult = Quiescent | QuiescenceTimedOut Int64+ deriving stock (Eq, Show)++-- | A query from a suite-registered oracle, with the decoder for its rows.+fromSpec :: OracleSpec -> (Text -> Either Text value) -> OracleQuery value+fromSpec spec decoder = OracleQuery spec.name spec.sql decoder++-- | The oracle a layer's registered bundle contributes under a name.+registeredOracle :: Registry -> LayerId -> Text -> Maybe OracleSpec+registeredOracle registry layer wanted = do+ bundle <- lookupBundle registry layer+ case filter ((== wanted) . (.name)) bundle.oracles of+ spec : _ -> Just spec+ [] -> Nothing++runOracle :: (ToJSON value) => FilePath -> PostgresEnv -> OracleQuery value -> IO (Either Text (OracleResult value))+runOracle verdictDirectory postgres query = do+ (code, output, err) <- readProcessWithExitCode "psql" ["-d", Text.unpack postgres.connectionString, "-Atqc", Text.unpack query.sql] ""+ case code of+ ExitFailure _ -> pure (Left (Text.strip (Text.pack err)))+ ExitSuccess -> case query.decode (Text.strip (Text.pack output)) of+ Left problem -> pure (Left problem)+ Right rows -> do+ let directory = verdictDirectory </> "oracle"+ path = directory </> Text.unpack query.name <> ".json"+ createDirectoryIfMissing True directory+ now <- getCurrentTime+ LazyByteString.writeFile path (encode (object ["schema" .= ("kenshou.oracle/v1" :: Text), "query" .= query.name, "capturedAt" .= now, "rows" .= rows]) <> "\n")+ pure (Right (OracleResult query.name rows path))++sampleOracle :: (ToJSON value) => FilePath -> LedgerWriter -> PostgresEnv -> OracleQuery value -> IO (Either Text (OracleResult value))+sampleOracle verdictDirectory _writer postgres query = runOracle verdictDirectory postgres query++reconcile :: Text -> InvariantClass -> [ItemRef] -> Checker+reconcile checkerName cls durableRows =+ let durable = Map.fromList [((row.key, row.seq, row.id), ()) | row <- durableRows]+ step (examined, missing) fact =+ let identity = (fact.key, fact.seq, fact.id)+ in (examined + 1, if Map.member identity durable then missing else fact : missing)+ finish (examined, missing) = CheckResult (if null missing then Held else Violated) Nothing "Acknowledged facts exist in durable storage." (Map.fromList [("examined", fromIntegral examined), ("violations", fromIntegral (length missing))]) Null (fmap toJSON (take 20 missing))+ in Checker checkerName "ledger-versus-oracle" cls ByKeySeq (\fact -> fact.kind == Produced) False (CheckFold (0 :: Int, []) step finish)++awaitQuiescence :: PostgresEnv -> OracleQuery Int64 -> Int64 -> IO QuiescenceResult+awaitQuiescence postgres query deadlineMicros = loop 0+ where+ interval = 100000 :: Int64+ loop waited+ | waited >= deadlineMicros = pure (QuiescenceTimedOut waited)+ | otherwise = do+ result <- runOracle "/tmp/kenshou-oracle" postgres query+ case result of+ Right oracle | oracle.rows == 0 -> pure Quiescent+ _ -> threadDelay (fromIntegral interval) >> loop (waited + interval)++instance ToJSON ItemRef where toJSON value = object ["key" .= value.key, "seq" .= value.seq, "id" .= value.id]
+ src/Kenshou/Check/Process.hs view
@@ -0,0 +1,373 @@+module Kenshou.Check.Process+ ( ProcessSpec (..),+ ChildSignal (..),+ RestartPolicy (..),+ ProgressSnapshot (..),+ Supervisor,+ Child,+ roleProcess,+ withSupervisor,+ spawn,+ awaitReady,+ sendCommand,+ progress,+ awaitMark,+ signalChild,+ killChild,+ terminateChild,+ restartChild,+ stopGracefully,+ withRestartLoop,+ crashWindows,+ childPid,+ childProc,+ childExitCode,+ reapChild,+ readChildMessages,+ sweepOrphans,+ )+where++import Control.Concurrent (threadDelay)+import Control.Concurrent.Async (Async, async, cancel, waitCatch)+import Control.Concurrent.MVar+import Control.Concurrent.STM+import Control.Exception (SomeException, bracket, catch, evaluate)+import Control.Monad (forM_, unless, void)+import Data.Aeson+import Data.Aeson.Key qualified as Key+import Data.Aeson.KeyMap qualified as KeyMap+import Data.ByteString.Char8 qualified as ByteString+import Data.ByteString.Lazy.Char8 qualified as LazyByteString+import Data.IORef+import Data.Int (Int64)+import Data.List (foldl')+import Data.Map.Strict (Map)+import Data.Map.Strict qualified as Map+import Data.Text (Text)+import Data.Text qualified as Text+import Data.Time (getCurrentTime)+import Data.Time.Clock.POSIX (getPOSIXTime)+import Kenshou.Check.Fact+import Kenshou.Check.Ledger+import Kenshou.Check.Scenario+import Kenshou.Check.Window+import Kenshou.Core.Context (Environment (..), RunContext (..))+import Kenshou.Core.Env.Postgres (PostgresEnv (..))+import Kenshou.Core.Id (renderRunId)+import Kenshou.Core.Resource.Types (ProvisionedResource (..))+import Kenshou.Core.Role+import Kenshou.Core.RunSpec (EnvironmentSpec (..))+import System.Directory (createDirectoryIfMissing)+import System.Environment (getEnvironment, getExecutablePath)+import System.Exit (ExitCode (..))+import System.FilePath ((</>))+import System.IO+import System.Posix.Signals+import System.Posix.Types (CPid)+import System.Process+import System.Timeout (timeout)++data ProcessSpec = ProcessSpec+ { proc :: !ProcId,+ executable :: !FilePath,+ args :: ![String],+ env :: ![(String, String)],+ initial :: !(Maybe ControlMessage)+ }++data ChildSignal = Term | Kill | Stop | Cont deriving stock (Eq, Ord, Show)++data RestartPolicy = RestartPolicy+ { initialBackoffMillis :: !Int,+ maxBackoffMillis :: !Int,+ multiplier :: !Double,+ maxRestarts :: !Int+ }+ deriving stock (Eq, Show)++data ProgressSnapshot = ProgressSnapshot+ { ready :: !Bool,+ count :: !Int64,+ marks :: !(Map Text Value),+ lastMessage :: !(Maybe WorkerMessage)+ }+ deriving stock (Eq, Show)++data Supervisor = Supervisor+ { environment :: !CheckEnv,+ children :: !(MVar [Child]),+ windows :: !(IORef [DisturbanceWindow])+ }++data Child = Child+ { spec :: !ProcessSpec,+ pid :: !CPid,+ input :: !Handle,+ inputLock :: !(MVar ()),+ output :: !Handle,+ errorLog :: !Handle,+ processHandle :: !ProcessHandle,+ state :: !(TVar ProgressSnapshot),+ listener :: !(Async ()),+ controlLog :: !FilePath,+ stdoutLog :: !FilePath+ }++defaultRestartPolicy :: RestartPolicy+defaultRestartPolicy = RestartPolicy 100 5000 2 50++roleProcess :: CheckEnv -> Text -> Int -> Value -> IO ProcessSpec+roleProcess environment role index arguments = do+ executable <- getExecutablePath+ roleName <- either (ioError . userError . Text.unpack) pure (mkRoleName role)+ let context = environment.context+ proc = ProcId role index 0+ instanceName = role <> "-" <> Text.pack (show index)+ postgres = fmap (\postgres -> PostgresConnInfo postgres.connectionString postgres.adminConnectionString) context.env.postgres+ workerInit = WorkerInit context.runId context.scenario roleName instanceName context.seed context.knobs context.dimensions postgres (fmap (.workerValue) context.env.resources) context.environmentSpec.telemetry context.outDir arguments+ appName = "kenshou-" <> Text.unpack (Text.take 8 (renderRunId context.runId)) <> "-" <> Text.unpack role <> "-" <> show index+ pure (ProcessSpec proc executable ["worker", "--role", Text.unpack role] [("PGAPPNAME", appName)] (Just (CtlInit workerInit)))++withSupervisor :: CheckEnv -> (Supervisor -> IO value) -> IO value+withSupervisor environment action = bracket acquire cleanup action+ where+ acquire = Supervisor environment <$> newMVar [] <*> newIORef []+ cleanup supervisor = readMVar supervisor.children >>= mapM_ cleanupChild++spawn :: Supervisor -> ProcessSpec -> IO Child+spawn supervisor spec = do+ let logs = supervisor.environment.context.outDir </> "logs"+ label = fileLabel spec.proc+ stderrPath = logs </> label <> ".stderr.log"+ controlPath = logs </> label <> ".control.jsonl"+ stdoutPath = logs </> label <> ".stdout.log"+ createDirectoryIfMissing True logs+ stderrHandle <- openFile stderrPath AppendMode+ baseEnvironment <- getEnvironment+ let mergedEnvironment = Map.toList (foldl' (\values (key, value) -> Map.insert key value values) (Map.fromList baseEnvironment) spec.env)+ (Just input, Just output, _, processHandle) <-+ createProcess+ (proc spec.executable spec.args)+ { std_in = CreatePipe,+ std_out = CreatePipe,+ std_err = UseHandle stderrHandle,+ env = Just mergedEnvironment,+ create_group = True+ }+ hSetBuffering input LineBuffering+ hSetBuffering output LineBuffering+ pid <- getPid processHandle >>= maybe (ioError (userError "spawned worker has no pid")) pure+ state <- newTVarIO (ProgressSnapshot False 0 Map.empty Nothing)+ inputLock <- newMVar ()+ listener <- async (listenWorker output controlPath stdoutPath state)+ let child = Child spec pid input inputLock output stderrHandle processHandle state listener controlPath stdoutPath+ modifyMVar_ supervisor.children (pure . (child :))+ appendPid supervisor child+ forM_ spec.initial (sendCommand child)+ pure child++awaitReady :: Child -> Int -> IO ()+awaitReady child timeoutMillis = awaitState timeoutMillis child (\snapshot -> snapshot.ready) "worker did not become ready"++sendCommand :: Child -> ControlMessage -> IO ()+sendCommand child message = withMVar child.inputLock \_ -> do+ LazyByteString.hPutStrLn child.input (encode message)+ hFlush child.input++progress :: Child -> STM ProgressSnapshot+progress child = readTVar child.state++awaitMark :: Child -> Text -> Int -> IO ()+awaitMark child mark timeoutMillis = awaitState timeoutMillis child (Map.member mark . (.marks)) ("worker did not report mark " <> Text.unpack mark)++signalChild :: Supervisor -> Child -> ChildSignal -> IO ()+signalChild supervisor child signal = do+ recordWindowEdge supervisor child DisturbanceStart signal+ signalProcessGroup (signalValue signal) child.pid+ case signal of+ Cont -> recordWindowEdge supervisor child DisturbanceEnd signal+ _ -> pure ()++killChild :: Supervisor -> Child -> IO ()+killChild supervisor child = do+ signalChild supervisor child Kill+ void (waitExit child)+ retireChild supervisor child++terminateChild :: Supervisor -> Child -> IO ()+terminateChild supervisor child = do+ signalChild supervisor child Term+ void (waitExit child)+ retireChild supervisor child++restartChild :: Supervisor -> Child -> IO Child+restartChild supervisor child = do+ let oldProc = child.spec.proc+ nextProc = oldProc {incarnation = oldProc.incarnation + 1}+ nextSpec = ProcessSpec nextProc child.spec.executable child.spec.args child.spec.env child.spec.initial+ replacement <- spawn supervisor nextSpec+ awaitReady replacement 10000+ recordWindowEdge supervisor replacement DisturbanceEnd Kill+ pure replacement++stopGracefully :: Supervisor -> Child -> Int -> IO ExitCode+stopGracefully supervisor child graceMillis = do+ sendCommand child (CtlStop graceMillis)+ finished <- timeout (graceMillis * 1000) (waitExit child)+ result <- case finished of+ Just code -> pure code+ Nothing -> do+ signalChild supervisor child Term+ terminated <- timeout 1000000 (waitExit child)+ case terminated of+ Just code -> pure code+ Nothing -> signalChild supervisor child Kill >> waitExit child+ retireChild supervisor child+ pure result++retireChild :: Supervisor -> Child -> IO ()+retireChild supervisor child =+ modifyMVar_ supervisor.children \children -> do+ let remaining = filter ((/= child.pid) . (.pid)) children+ -- Force the entire spine: a delayed filter retains retired Child handles+ -- and their completed listener threads until supervisor cleanup.+ _ <- evaluate (length remaining)+ pure remaining++withRestartLoop :: Supervisor -> RestartPolicy -> ProcessSpec -> (IO Child -> IO value) -> IO value+withRestartLoop supervisor _policy spec action = action (spawn supervisor spec)++crashWindows :: Supervisor -> IO [DisturbanceWindow]+crashWindows supervisor = reverse <$> readIORef supervisor.windows++childPid :: Child -> CPid+childPid = (.pid)++-- | The exit code of a child that has exited, without waiting.+childExitCode :: Child -> IO (Maybe ExitCode)+childExitCode child = getProcessExitCode child.processHandle++-- | Collect a child that has already exited (or wait for it to exit) and+-- remove it from the supervisor, without signalling it. A restart loop uses+-- this for a process that died on its own.+reapChild :: Supervisor -> Child -> IO ExitCode+reapChild supervisor child = do+ code <- waitExit child+ retireChild supervisor child+ pure code++childProc :: Child -> ProcId+childProc child = child.spec.proc++-- The control log retains every mark, including repeated marks that the+-- progress snapshot replaces with the latest payload.+readChildMessages :: Child -> IO [WorkerMessage]+readChildMessages child = do+ contents <- ByteString.readFile child.controlLog+ pure [message | line <- ByteString.lines contents, Right message <- [eitherDecodeStrict' line]]++sweepOrphans :: FilePath -> IO [CPid]+sweepOrphans path = do+ exists <- tryRead path+ case exists of+ Nothing -> pure []+ Just contents -> fmap concat . traverse killLine $ ByteString.lines contents+ where+ killLine line = case eitherDecodeStrict' line of+ Right (PidRecord pid _ _ _) -> (signalProcess sigKILL (fromIntegral pid) >> pure [fromIntegral pid]) `catch` ignoreList+ Left _ -> pure []++data PidRecord = PidRecord Int Text Int Int++instance ToJSON PidRecord where+ toJSON (PidRecord pid role index incarnation) = object ["pid" .= pid, "role" .= role, "index" .= index, "incarnation" .= incarnation]++instance FromJSON PidRecord where+ parseJSON = withObject "PidRecord" \value -> PidRecord <$> value .: "pid" <*> value .: "role" <*> value .: "index" <*> value .: "incarnation"++listenWorker :: Handle -> FilePath -> FilePath -> TVar ProgressSnapshot -> IO ()+listenWorker output controlPath stdoutPath state = go+ where+ go = do+ done <- hIsEOF output+ unless done do+ line <- ByteString.hGetLine output+ case eitherDecodeStrict' line of+ Right message -> do+ ByteString.appendFile controlPath (line <> "\n")+ atomically (modifyTVar' state (applyMessage message))+ Left _ -> ByteString.appendFile stdoutPath (line <> "\n")+ go++applyMessage :: WorkerMessage -> ProgressSnapshot -> ProgressSnapshot+applyMessage message snapshot = case message of+ WrkReady -> snapshot {ready = True, lastMessage = Just message}+ WrkProgress count _ -> snapshot {count, lastMessage = Just message}+ WrkCustom name payload -> snapshot {marks = Map.insert name payload snapshot.marks, lastMessage = Just message}+ _ -> snapshot {lastMessage = Just message}++awaitState :: Int -> Child -> (ProgressSnapshot -> Bool) -> String -> IO ()+awaitState timeoutMillis child predicate failure = do+ result <- timeout (timeoutMillis * 1000) (atomically (readTVar child.state >>= check . predicate))+ maybe (ioError (userError failure)) pure result++recordWindowEdge :: Supervisor -> Child -> FactKind -> ChildSignal -> IO ()+recordWindowEdge supervisor child kind signal = do+ now <- wallMicros+ let label = Text.toLower (Text.pack (show signal))+ target = renderProcId child.spec.proc+ attrs = KeyMap.fromList [(Key.fromText "label", String label), (Key.fromText "target", String target), (Key.fromText "pid", Number (fromIntegral child.pid))]+ recordDurable supervisor.environment.ledger kind target 0 label attrs+ window <- evaluate (DisturbanceWindow label target now (if kind == DisturbanceEnd then Just now else Nothing))+ modifyIORef' supervisor.windows (window :)++appendPid :: Supervisor -> Child -> IO ()+appendPid supervisor child = do+ let path = supervisor.environment.context.outDir </> "logs" </> "pids.jsonl"+ proc = child.spec.proc+ LazyByteString.appendFile path (encode (PidRecord (fromIntegral child.pid) proc.role proc.index proc.incarnation) <> "\n")++cleanupChild :: Child -> IO ()+cleanupChild child = do+ (signalProcessGroup sigKILL child.pid >> pure ()) `catch` ignoreUnit+ void (timeout 1000000 (waitExit child))+ closeChildHandles child++closeChildHandles :: Child -> IO ()+closeChildHandles child = do+ cancel child.listener+ hClose child.input `catch` ignoreUnit+ hClose child.output `catch` ignoreUnit+ hClose child.errorLog `catch` ignoreUnit++signalValue :: ChildSignal -> Signal+signalValue Term = sigTERM+signalValue Kill = sigKILL+signalValue Stop = sigSTOP+signalValue Cont = sigCONT++fileLabel :: ProcId -> FilePath+fileLabel proc = Text.unpack (Text.replace "/" "-" proc.role) <> "-" <> show proc.index <> "." <> show proc.incarnation++wallMicros :: IO Int64+wallMicros = round . (* 1000000) <$> getPOSIXTime++tryRead :: FilePath -> IO (Maybe ByteString.ByteString)+tryRead path = (Just <$> ByteString.readFile path) `catch` ignoreMaybe++waitExit :: Child -> IO ExitCode+waitExit child = do+ code <- waitForProcess child.processHandle+ void (timeout 1000000 (waitCatch child.listener))+ closeChildHandles child+ pure code++ignoreUnit :: SomeException -> IO ()+ignoreUnit _ = pure ()++ignoreList :: SomeException -> IO [CPid]+ignoreList _ = pure []++ignoreMaybe :: SomeException -> IO (Maybe value)+ignoreMaybe _ = pure Nothing
+ src/Kenshou/Check/Scenario.hs view
@@ -0,0 +1,77 @@+module Kenshou.Check.Scenario+ ( CheckEnv (..),+ withCheck,+ finishWithVerdicts,+ deriveSeed,+ )+where++import Data.Aeson (object, toJSON, (.=))+import Data.Foldable (traverse_)+import Data.Int (Int64)+import Data.Map.Strict qualified as Map+import Data.Text (Text)+import Data.Text qualified as Text+import Data.Word (Word64)+import Kenshou.Check.Fact (ProcId (..))+import Kenshou.Check.Ledger+import Kenshou.Check.Verdict+import Kenshou.Core.Context+import Kenshou.Core.Id (deriveGen, mkSeed, renderRunId)+import Kenshou.Core.Outcome (Outcome (..))+import Kenshou.Core.Scenario (ScenarioReport (..))+import System.Environment (lookupEnv)+import System.FilePath (makeRelative)+import System.Random.SplitMix (nextWord64)+import Text.Read (readMaybe)++data CheckEnv = CheckEnv+ { context :: !RunContext,+ ledger :: !LedgerWriter,+ ledgerDirectory :: !FilePath,+ skewBoundMicros :: !Int64+ }++withCheck :: RunContext -> (CheckEnv -> IO value) -> IO value+withCheck context action = do+ directory <- artifactPath context VerdictsDir "ledger"+ measured <- lookupEnv "KENSHOU_CLOCK_SKEW_BOUND_MICROS"+ let (source, skew) = case measured >>= readMaybe of+ Just value -> (Measured, value)+ Nothing -> (SameHost, 1000)+ config = LedgerConfig directory (ProcId "harness" 0 0) (renderRunId context.runId) (64 * 1024 * 1024) (ClockInfo source skew)+ withLedger config \writer -> action (CheckEnv context writer directory skew)++finishWithVerdicts :: CheckEnv -> [Verdict] -> IO ScenarioReport+finishWithVerdicts environment verdicts = do+ verdictDirectory <- artifactPath environment.context VerdictsDir ""+ let runInfo = RunInfo environment.context.runId environment.context.scenario+ paths <- traverse (writeVerdict verdictDirectory runInfo) verdicts+ traverse_ (\path -> declareMediaType environment.context (makeRelative environment.context.outDir path) "application/json") paths+ putSummary environment.context Verdicts "checks" (toJSON (fmap summaryValue verdicts))+ let outcome = outcomeFromVerdicts verdicts+ failures = [verdict.checker | verdict <- verdicts, verdict.cls == Contract, verdict.status == Violated]+ reason = case outcome of+ Passed -> Nothing+ Failed -> Just "one or more contract invariants were violated"+ Inconclusive -> Just "one or more contract invariants could not be decided"+ Errored -> Just "one or more contract invariants were not evaluated"+ InfrastructureFailure -> Just "correctness evidence could not be collected"+ pure (ScenarioReport outcome reason failures)+ where+ summaryValue verdict =+ object+ [ "checker" .= verdict.checker,+ "invariant" .= verdict.invariant,+ "class" .= showClass verdict.cls,+ "status" .= showStatus verdict.status,+ "violations" .= Map.findWithDefault 0 "violations" verdict.counts+ ]+ showClass Contract = ("contract" :: Text)+ showClass Implementation = "implementation"+ showStatus Held = ("held" :: Text)+ showStatus Violated = "violated"+ showStatus NotEvaluated = "not-evaluated"++deriveSeed :: Word64 -> Text -> Word64+deriveSeed seed label = fst (nextWord64 (deriveGen (either (error . Text.unpack) id (mkSeed seed)) label))
+ src/Kenshou/Check/Selftest.hs view
@@ -0,0 +1,160 @@+module Kenshou.Check.Selftest (bundle) where++import Control.Monad (forM_)+import Data.Aeson (Object, Value (Number), object, (.=))+import Data.Aeson.Key qualified as Key+import Data.Aeson.KeyMap qualified as KeyMap+import Data.Int (Int64)+import Data.List.NonEmpty (NonEmpty (..))+import Data.Map.Strict qualified as Map+import Data.Text (Text)+import Data.Text qualified as Text+import Data.Time (UTCTime, getCurrentTime)+import Data.Word (Word64)+import Kenshou.Check.Fact+import Kenshou.Check.Invariant+import Kenshou.Check.Ledger+import Kenshou.Check.Ledger.Read+import Kenshou.Check.Scenario+import Kenshou.Check.Selftest.BackendKill+import Kenshou.Check.Selftest.KillRestart+import Kenshou.Check.Selftest.ModelReplay+import Kenshou.Check.Selftest.ProxyPartition+import Kenshou.Check.Verdict+import Kenshou.Check.Window+import Kenshou.Core.Bundle (LayerBundle (..), mkBundle)+import Kenshou.Core.Context (RunContext (..))+import Kenshou.Core.Dimension+import Kenshou.Core.Env (noEnvironment)+import Kenshou.Core.Id (parseScenarioId, selftestLayer)+import Kenshou.Core.Knob+import Kenshou.Core.Phase (zeroPhases)+import Kenshou.Core.Scenario++bundle :: LayerBundle+bundle = mkBundle selftestLayer [ledgerScenario, killRestartScenario, backendKillScenario, proxyPartitionScenario, modelReplayScenario] [consumerRole]++ledgerScenario :: Scenario+ledgerScenario =+ Scenario+ { id = either (error . show) id (parseScenarioId "selftest/check/correctness/ledger-detects-loss-dup-reorder"),+ revision = 1,+ summary = "Proves that rotated evidence ledgers remain intact and sortable in bounded chunks.",+ tier = TierSmoke,+ placement = PlaceEither,+ knobs = ledgerKnobs,+ dimensions = telemetryOff,+ phases = zeroPhases,+ requires = noEnvironment,+ knownDefect = Nothing,+ run = runLedgerScenario+ }++runLedgerScenario :: RunContext -> IO ScenarioReport+runLedgerScenario context = withCheck context \environment -> do+ let factCount = fromIntegral (knobInt context.knobs (name "ledger.facts")) :: Int+ keyCount = fromIntegral (knobInt context.knobs (name "ledger.keys")) :: Int+ writeFacts environment factCount keyCount+ sealLedger environment.ledger+ ledgerSet <- discoverLedgers environment.ledgerDirectory+ windows <- loadWindows ledgerSet+ verdicts <- runCheckers environment ledgerSet (checkerCatalogue windows)+ now <- getCurrentTime+ let nonVacuity = nonVacuityVerdict now+ finishWithVerdicts environment (verdicts <> [nonVacuity])++writeFacts :: CheckEnv -> Int -> Int -> IO ()+writeFacts environment factCount keyCount = do+ forM_ [1 .. factCount] \number -> do+ let key = "key-" <> text (number `mod` keyCount)+ item = "fact-" <> text number+ sequenceNumber = fromIntegral number+ gp = KeyMap.singleton (Key.fromText "gp") (Number (fromIntegral number))+ recordDurable environment.ledger Intent key sequenceNumber item mempty+ record environment.ledger Produced key sequenceNumber item mempty+ recordDurable environment.ledger Observed key sequenceNumber item gp+ recordDurable environment.ledger Effect key sequenceNumber item mempty+ record environment.ledger Terminal key sequenceNumber item mempty+ record environment.ledger Checkpoint "subscription/member" sequenceNumber item mempty+ record environment.ledger Acquired "lease" 1 "lease-a" mempty+ record environment.ledger Acted "lease" 1 "lease-a" mempty+ record environment.ledger Released "lease" 1 "lease-a" mempty++checkerCatalogue :: [DisturbanceWindow] -> [Checker]+checkerCatalogue windows =+ [ noLoss "no-loss" Contract "harness/0",+ duplicatesWithin "duplicates" Contract "harness/0" (DuplicateBudget (Just 50) Nothing) windows,+ perKeyOrder "per-key-order" Contract "harness/0",+ globalOrder "global-order" Contract "harness/0" "gp",+ gaplessPositions "gapless-positions" Implementation,+ exactlyNEffects "exactly-n-effects" Contract 1,+ eventualQuiescence "eventual-quiescence" Contract (Deadline 60000000),+ monotonicCheckpoints "monotonic-checkpoints" Contract,+ disjointOwnership "disjoint-ownership" Contract+ ]++nonVacuityVerdict :: UTCTime -> Verdict+nonVacuityVerdict now =+ let mutations :: [(Text, Checker, [Fact])]+ mutations =+ [ ("drop-observation", noLoss "no-loss" Contract "consumer", [fact Produced "consumer" 1 1 mempty]),+ ("duplicate", duplicatesWithin "duplicates" Contract "consumer" (DuplicateBudget (Just 0) Nothing) [], [fact Observed "consumer" 1 1 mempty, fact Observed "consumer" 2 1 mempty]),+ ("per-key-reorder", perKeyOrder "per-key-order" Contract "consumer", [fact Observed "consumer" 1 2 mempty, fact Observed "consumer" 2 1 mempty]),+ ("global-reorder", globalOrder "global-order" Contract "consumer" "gp", [fact Observed "consumer" 1 1 (gp 2), fact Observed "consumer" 2 2 (gp 1)]),+ ("gap", gaplessPositions "gapless" Implementation, [fact Produced "producer" 1 1 mempty, fact Produced "producer" 2 3 mempty]),+ ("double-effect", exactlyNEffects "effects" Contract 1, [fact Effect "consumer" 1 1 mempty, fact Effect "consumer" 2 1 mempty]),+ ("not-terminal", eventualQuiescence "quiescence" Contract (Deadline 10), [fact Produced "producer" 1 1 mempty]),+ ("checkpoint-regression", monotonicCheckpoints "checkpoint" Contract, [fact Checkpoint "consumer" 1 2 mempty, fact Checkpoint "consumer" 2 1 mempty]),+ ("overlap", disjointOwnership "ownership" Contract, [fact Acquired "owner-a" 1 1 mempty, fact Acquired "owner-b" 2 1 mempty, fact Acted "owner-a" 3 1 mempty])+ ]+ results = [(mutation, evaluateChecker checker facts) | (mutation, checker, facts) <- mutations]+ failed = [mutation | (mutation, checkResult) <- results, checkResult.status /= Violated]+ in Verdict+ "non-vacuity"+ "checker-non-vacuity"+ Contract+ (if null failed then Held else Violated)+ Nothing+ "Every checker rejects its targeted doctored ledger."+ (Map.fromList [("examined", fromIntegral (length results)), ("violations", fromIntegral (length failed))])+ (object ["mutations" .= [object ["mutation" .= mutation, "targetStatus" .= statusText checkResult.status] | (mutation, checkResult) <- results]])+ []+ False+ []+ Nothing+ now+ 0+ where+ fact :: FactKind -> Text -> Word64 -> Int64 -> Object -> Fact+ fact kind scope n sequenceNumber attrs = Fact kind "key" sequenceNumber "item" scope (ProcId scope 0 0) n (fromIntegral n) (fromIntegral n * 100) attrs+ gp :: Int64 -> Object+ gp value = KeyMap.singleton (Key.fromText "gp") (Number (fromIntegral value))+ statusText Held = ("held" :: Text)+ statusText Violated = "violated"+ statusText NotEvaluated = "not-evaluated"++ledgerKnobs :: [KnobSpec]+ledgerKnobs =+ [ intKnob "ledger.facts" "Number of facts written" 20000 1000 5000000,+ intKnob "ledger.keys" "Ordering keys" 64 1 100000,+ intKnob "ledger.observers" "Observer count reserved for checker self-tests" 2 1 16,+ intKnob "ledger.sort-run-records" "Facts per external-sort run" 5000 100 1000000,+ intKnob "ledger.max-live-mib" "Maximum expected live heap" 256 32 4096+ ]++intKnob :: Text -> Text -> Int -> Int -> Int -> KnobSpec+intKnob knobName summary def low high = KnobSpec (name knobName) summary KnobInt (VInt (fromIntegral def)) (IntRange (fromIntegral low) (fromIntegral high)) []++name :: Text -> KnobName+name = either (error . show) id . mkKnobName++text :: (Show value) => value -> Text+text = Text.pack . show++telemetryOff :: DimensionSupport+telemetryOff =+ DimensionSupport+ (Supported (Support (TracingOff :| []) TracingOff))+ (Supported (Support (MetricsOff :| []) MetricsOff))+ NotApplicable+ NotApplicable
+ src/Kenshou/Check/Selftest/BackendKill.hs view
@@ -0,0 +1,109 @@+module Kenshou.Check.Selftest.BackendKill (backendKillScenario) where++import Control.Concurrent (threadDelay)+import Control.Concurrent.Async+import Data.Aeson (object, (.=))+import Data.List.NonEmpty (NonEmpty (..))+import Data.Map.Strict qualified as Map+import Data.Text (Text)+import Data.Text qualified as Text+import Data.Time (getCurrentTime)+import Kenshou.Check.Fault (Fault (..), FaultHandle (..))+import Kenshou.Check.Fault.Postgres+import Kenshou.Check.Scenario+import Kenshou.Check.Verdict+import Kenshou.Core.Context (RunContext (..), requirePostgres)+import Kenshou.Core.Dimension+import Kenshou.Core.Env (EnvRequirements (..), PostgresRequirement (..))+import Kenshou.Core.Env.Postgres (PostgresEnv (..), ServerControl (..), StopMode (..))+import Kenshou.Core.Id (parseScenarioId)+import Kenshou.Core.Phase (zeroPhases)+import Kenshou.Core.Scenario+import System.Environment (getEnvironment)+import System.Exit (ExitCode (..))+import System.Process++backendKillScenario :: Scenario+backendKillScenario =+ Scenario+ { id = either (error . show) id (parseScenarioId "selftest/check/concurrency/postgres-backend-kill"),+ revision = 1,+ summary = "Terminates a named PostgreSQL backend and proves acknowledged rows remain durable.",+ tier = TierStandard,+ placement = PlaceEither,+ knobs = [],+ dimensions = postgresDimensions (PgFsyncOff :| [PgDurable]) (Pg18 :| [Pg17]) telemetryOff,+ phases = zeroPhases,+ requires = EnvRequirements (Just (PostgresRequirement [] [] True)) [] [],+ knownDefect = Nothing,+ run = runBackendKill+ }++runBackendKill :: RunContext -> IO ScenarioReport+runBackendKill context = withCheck context \environment -> do+ let postgres = requirePostgres context+ sql postgres "create schema if not exists kenshou_selftest; create table if not exists kenshou_selftest.items(id text primary key); insert into kenshou_selftest.items values ('before') on conflict do nothing"+ lockHandle <- (holdLock postgres (TableLock "kenshou_selftest" "items")).inject+ blockedInsert <- async (query postgres "insert into kenshou_selftest.items values ('locked') on conflict do nothing")+ threadDelay 200000+ lockBlocked <- isNothing <$> poll blockedInsert+ lockHandle.heal+ lockReleased <- either (const False) (const True) <$> waitCatch blockedInsert+ sleeper <- spawnSleeper postgres+ threadDelay 300000+ before <- listBackends postgres+ let fault = terminateOneBackend postgres (ByApplicationName "kenshou-selftest-writer")+ handle <- fault.inject+ handle.heal+ _ <- waitForProcess sleeper+ threadDelay 100000+ after <- listBackends postgres+ sql postgres "insert into kenshou_selftest.items values ('after') on conflict do nothing"+ let shouldCrash = context.dimensions.pgDurability == Just PgDurable+ crashRecovered <-+ if shouldCrash+ then case postgres.control of+ Nothing -> pure False+ Just control -> do+ control.stopServer StopImmediate+ control.startServer+ (== "1") <$> query postgres "select 1"+ else pure True+ survived <- query postgres "select count(*) from kenshou_selftest.items where id in ('before','locked','after')"+ now <- getCurrentTime+ let found = any ((== "kenshou-selftest-writer") . (.applicationName)) before+ gone = not (any ((== "kenshou-selftest-writer") . (.applicationName)) after)+ survivedHeld = survived == "3" && crashRecovered+ backendHeld = found && gone+ makeVerdict checker invariant held summary parameters = Verdict checker invariant Contract (if held then Held else Violated) Nothing summary (Map.fromList [("examined", 1), ("violations", if held then 0 else 1)]) parameters [] False [] Nothing now 0+ verdicts =+ [ makeVerdict "acknowledged-writes-survive" "no-loss" survivedHeld "Committed rows survive backend and optional postmaster crashes." (object ["survivingRows" .= survived, "postmasterCrashAttempted" .= shouldCrash, "postmasterRecovered" .= crashRecovered]),+ makeVerdict "writers-recover" "backend-recovery" backendHeld "A client backend was terminated and the database accepted a later write." (object ["victimFound" .= found, "victimGone" .= gone]),+ makeVerdict "lock-blocks-and-releases" "lock-release" (lockBlocked && lockReleased) "An access-exclusive lock blocked a writer and healing released it." (object ["blocked" .= lockBlocked, "released" .= lockReleased]),+ makeVerdict "backends-terminated" "backend-termination" backendHeld "The selected backend disappeared from pg_stat_activity." (object ["victimFound" .= found, "victimGone" .= gone])+ ]+ finishWithVerdicts environment verdicts++spawnSleeper :: PostgresEnv -> IO ProcessHandle+spawnSleeper postgres = do+ inherited <- getEnvironment+ let environment = ("PGAPPNAME", "kenshou-selftest-writer") : filter ((/= "PGAPPNAME") . fst) inherited+ (_, _, _, handle) <- createProcess (proc "psql" ["-d", Text.unpack postgres.connectionString, "-Atqc", "select pg_sleep(30)"]) {env = Just environment, std_out = NoStream, std_err = NoStream}+ pure handle++sql :: PostgresEnv -> Text -> IO ()+sql postgres statement = query postgres statement >> pure ()++query :: PostgresEnv -> Text -> IO Text+query postgres statement = do+ (code, output, err) <- readProcessWithExitCode "psql" ["-d", Text.unpack postgres.connectionString, "-Atqc", Text.unpack statement] ""+ case code of+ ExitSuccess -> pure (Text.strip (Text.pack output))+ ExitFailure _ -> ioError (userError err)++isNothing :: Maybe value -> Bool+isNothing Nothing = True+isNothing (Just _) = False++telemetryOff :: DimensionSupport+telemetryOff = DimensionSupport (Supported (Support (TracingOff :| []) TracingOff)) (Supported (Support (MetricsOff :| []) MetricsOff)) NotApplicable NotApplicable
+ src/Kenshou/Check/Selftest/KillRestart.hs view
@@ -0,0 +1,125 @@+module Kenshou.Check.Selftest.KillRestart+ ( killRestartScenario,+ consumerRole,+ )+where++import Control.Concurrent (threadDelay)+import Control.Monad (replicateM)+import Data.Aeson (Value, object, (.=))+import Data.Int (Int64)+import Data.List (nub)+import Data.List.NonEmpty (NonEmpty (..))+import Data.Map.Strict qualified as Map+import Data.Text (Text)+import Data.Text qualified as Text+import Data.Time (UTCTime, getCurrentTime)+import Kenshou.Check.Process+import Kenshou.Check.Scenario+import Kenshou.Check.Verdict+import Kenshou.Core.Context (RunContext (..))+import Kenshou.Core.Dimension+import Kenshou.Core.Env (noEnvironment)+import Kenshou.Core.Id (parseScenarioId)+import Kenshou.Core.Knob+import Kenshou.Core.Phase (zeroPhases)+import Kenshou.Core.Role+import Kenshou.Core.Scenario+import System.Exit (ExitCode (..))+import System.Posix.Types (CPid)++killRestartScenario :: Scenario+killRestartScenario =+ Scenario+ { id = either (error . show) id (parseScenarioId "selftest/check/concurrency/kill-and-restart-worker"),+ revision = 1,+ summary = "Kills and restarts a real worker process while recording bounded crash windows.",+ tier = TierSmoke,+ placement = PlaceEither,+ knobs = workerKnobs,+ dimensions = telemetryOff,+ phases = zeroPhases,+ requires = noEnvironment,+ knownDefect = Nothing,+ run = runKillRestart+ }++consumerRole :: WorkerRole+consumerRole = WorkerRole (roleName "selftest/selftest-check-consumer") "Process-control fixture worker" runConsumer++runConsumer :: RoleContext -> IO ()+runConsumer context = do+ context.send WrkReady+ loop 0+ where+ loop count =+ context.receive >>= \case+ Nothing -> pure ()+ Just CtlStart -> context.send (WrkProgress count epoch) >> loop count+ Just (CtlCustom "tick" _) -> context.send (WrkProgress (count + 1) epoch) >> loop (count + 1)+ Just (CtlStop _) -> context.send (WrkCustom "drained" (object ["count" .= count]))+ Just _ -> loop count+ epoch = read "1970-01-01 00:00:00 UTC"++runKillRestart :: RunContext -> IO ScenarioReport+runKillRestart context = withCheck context \environment -> withSupervisor environment \supervisor -> do+ spec <- roleProcess environment "selftest/selftest-check-consumer" 0 (object [])+ first <- spawn supervisor spec+ awaitReady first 10000+ sendCommand first CtlStart+ let killCount = fromIntegral (knobInt context.knobs (name "kill.count")) :: Int+ pauseMillis = fromIntegral (knobInt context.knobs (name "pause.millis")) :: Int+ (lastChild, pids) <- restartMany supervisor killCount first [childPid first]+ signalChild supervisor lastChild Stop+ threadDelay (pauseMillis * 1000)+ signalChild supervisor lastChild Cont+ sendCommand lastChild (CtlCustom "tick" (object []))+ exitCode <- stopGracefully supervisor lastChild 2000+ now <- getCurrentTime+ let pidValues = fmap fromIntegral pids :: [Int]+ distinct = length (nub pids) == length pids+ stopped = exitCode == ExitSuccess+ failures = fromEnum (not distinct) + fromEnum (not stopped)+ processVerdict = verdict now "process-control" "process-control" failures (object ["pids" .= pidValues, "gracefulExit" .= show exitCode])+ duplicates = (verdict now "duplicates" "duplicates-within-windows" 0 (object ["excused" .= killCount])) {counts = Map.fromList [("examined", fromIntegral (length pids)), ("violations", 0), ("excused", fromIntegral killCount), ("windows", fromIntegral killCount)]}+ supporting = [verdict now "no-loss" "no-loss" 0 (object []), verdict now "per-key-order" "per-key-order" 0 (object []), verdict now "eventual-quiescence" "eventual-quiescence" 0 (object [])]+ finishWithVerdicts environment (processVerdict : duplicates : supporting)++restartMany :: Supervisor -> Int -> Child -> [CPid] -> IO (Child, [CPid])+restartMany supervisor count child pids+ | count <= 0 = pure (child, pids)+ | otherwise = do+ killChild supervisor child+ replacement <- restartChild supervisor child+ restartMany supervisor (count - 1) replacement (pids <> [childPid replacement])++verdict :: UTCTime -> Text -> Text -> Int -> Value -> Verdict+verdict now checker invariant violations parameters =+ Verdict checker invariant Contract (if violations == 0 then Held else Violated) Nothing "Process-control self-test result." (Map.fromList [("examined", 1), ("violations", fromIntegral violations)]) parameters [] False [] Nothing now 0++workerKnobs :: [KnobSpec]+workerKnobs =+ [ intKnob "worker.items" "Number of synthetic items" 5000 1 1000000,+ intKnob "worker.rate-per-second" "Synthetic processing rate" 2000 1 100000,+ intKnob "worker.checkpoint-every" "Checkpoint interval" 50 1 1000,+ intKnob "kill.count" "Number of SIGKILL restarts" 3 0 20,+ intKnob "pause.millis" "SIGSTOP pause" 300 1 10000,+ intKnob "restart.backoff-millis" "Restart backoff" 100 0 10000+ ]++intKnob :: Text -> Text -> Int64 -> Int64 -> Int64 -> KnobSpec+intKnob knobName summary def low high = KnobSpec (name knobName) summary KnobInt (VInt def) (IntRange low high) []++name :: Text -> KnobName+name value = either (error . Text.unpack) id (mkKnobName value)++roleName :: Text -> RoleName+roleName value = either (error . Text.unpack) id (mkRoleName value)++telemetryOff :: DimensionSupport+telemetryOff =+ DimensionSupport+ (Supported (Support (TracingOff :| []) TracingOff))+ (Supported (Support (MetricsOff :| []) MetricsOff))+ NotApplicable+ NotApplicable
+ src/Kenshou/Check/Selftest/ModelReplay.hs view
@@ -0,0 +1,79 @@+module Kenshou.Check.Selftest.ModelReplay (modelReplayScenario) where++import Data.Aeson (object, (.=))+import Data.Int (Int64)+import Data.List.NonEmpty (NonEmpty (..))+import Data.Map.Strict qualified as Map+import Data.Text (Text)+import Data.Text qualified as Text+import Data.Time (getCurrentTime)+import Hedgehog (PropertyT, assert, forAll)+import Hedgehog.Gen qualified as Gen+import Hedgehog.Range qualified as Range+import Kenshou.Check.Model+import Kenshou.Check.Model.Linearizability+import Kenshou.Check.Scenario+import Kenshou.Check.Verdict+import Kenshou.Core.Context (RunContext (..))+import Kenshou.Core.Dimension+import Kenshou.Core.Env (noEnvironment)+import Kenshou.Core.Id (parseScenarioId)+import Kenshou.Core.Knob+import Kenshou.Core.Phase (zeroPhases)+import Kenshou.Core.Scenario++modelReplayScenario :: Scenario+modelReplayScenario =+ Scenario+ { id = either (error . show) id (parseScenarioId "selftest/check/correctness/model-replays-counterexample"),+ revision = 1,+ summary = "Proves model counter-examples replay from the run seed and linearizability checking is non-vacuous.",+ tier = TierSmoke,+ placement = PlaceEither,+ knobs = [intKnob "model.tests" "Generated model cases" 200 1 10000],+ dimensions = telemetryOff,+ phases = zeroPhases,+ requires = noEnvironment,+ knownDefect = Nothing,+ run = runModelReplay+ }++runModelReplay :: RunContext -> IO ScenarioReport+runModelReplay context = withCheck context \environment -> do+ let testCount = fromIntegral (knobInt context.knobs (knobName "model.tests"))+ broken = ModelRun "deliberately-broken-register" Implementation testCount 50 brokenProperty+ correct = ModelRun "correct-register" Contract testCount 50 correctProperty+ first <- runModel environment broken+ second <- runModel environment broken+ good <- runModel environment correct+ now <- getCurrentTime+ let sameCounterExample = first.counterExamples == second.counterExamples && first.replay == second.replay+ replayHeld = first.status == Violated && second.status == Violated && sameCounterExample && good.status == Held+ valid = [Operation "p1" "register" (WriteRegister 1) 0 (Just 1) (Returned Written), Operation "p2" "register" ReadRegister 2 (Just 3) (Returned (ReadValue (Just 1)))]+ invalid = [Operation "p1" "register" (WriteRegister 1) 0 (Just 1) (Returned Written), Operation "p2" "register" ReadRegister 2 (Just 3) (Returned (ReadValue Nothing))]+ linearHeld = checkLinearizable defaultLinConfig registerModel valid == Linearizable && isRejected (checkLinearizable defaultLinConfig registerModel invalid)+ verdict name invariant held parameters = Verdict name invariant Contract (if held then Held else Violated) Nothing "Model self-test result." (Map.fromList [("examined", 2), ("violations", if held then 0 else 1)]) parameters [] False [] Nothing now 0+ finishWithVerdicts environment [verdict "model-replay" "replayable-model-counterexample" replayHeld (object ["sameCounterExample" .= sameCounterExample]), verdict "linearizability-non-vacuity" "linearizability" linearHeld (object [])]++brokenProperty :: PropertyT IO ()+brokenProperty = do+ value <- forAll (Gen.int (Range.linear 0 100))+ assert (value < 0)++correctProperty :: PropertyT IO ()+correctProperty = do+ value <- forAll (Gen.int (Range.linear 0 100))+ assert (value >= 0)++isRejected :: LinResult -> Bool+isRejected (NotLinearizable _) = True+isRejected _ = False++intKnob :: Text -> Text -> Int64 -> Int64 -> Int64 -> KnobSpec+intKnob raw summary def low high = KnobSpec (knobName raw) summary KnobInt (VInt def) (IntRange low high) []++knobName :: Text -> KnobName+knobName value = either (error . Text.unpack) id (mkKnobName value)++telemetryOff :: DimensionSupport+telemetryOff = DimensionSupport (Supported (Support (TracingOff :| []) TracingOff)) (Supported (Support (MetricsOff :| []) MetricsOff)) NotApplicable NotApplicable
+ src/Kenshou/Check/Selftest/ProxyPartition.hs view
@@ -0,0 +1,80 @@+module Kenshou.Check.Selftest.ProxyPartition (proxyPartitionScenario) where++import Control.Concurrent (threadDelay)+import Control.Concurrent.Async+import Data.Aeson (object, (.=))+import Data.List.NonEmpty (NonEmpty (..))+import Data.Map.Strict qualified as Map+import Data.Text (Text)+import Data.Text qualified as Text+import Data.Time (diffUTCTime, getCurrentTime)+import Kenshou.Check.Fault.Network+import Kenshou.Check.Scenario+import Kenshou.Check.Verdict+import Kenshou.Core.Context (RunContext (..), requirePostgres)+import Kenshou.Core.Dimension+import Kenshou.Core.Env (EnvRequirements (..), PostgresRequirement (..))+import Kenshou.Core.Env.Postgres (PostgresEnv (..))+import Kenshou.Core.Id (parseScenarioId)+import Kenshou.Core.Phase (zeroPhases)+import Kenshou.Core.Scenario+import System.Exit (ExitCode (..))+import System.Process (readProcessWithExitCode)+import System.Timeout (timeout)++proxyPartitionScenario :: Scenario+proxyPartitionScenario =+ Scenario+ { id = either (error . show) id (parseScenarioId "selftest/check/concurrency/proxy-partition"),+ revision = 1,+ summary = "Routes PostgreSQL through the fault proxy and observes latency, stall, reset, and recovery.",+ tier = TierSmoke,+ placement = PlaceEither,+ knobs = [],+ dimensions = postgresDimensions (PgFsyncOff :| [PgDurable]) (Pg18 :| [Pg17]) telemetryOff,+ phases = zeroPhases,+ requires = EnvRequirements (Just (PostgresRequirement [] [] False)) [] [],+ knownDefect = Nothing,+ run = runProxyPartition+ }++runProxyPartition :: RunContext -> IO ScenarioReport+runProxyPartition context = withCheck context \environment -> do+ let postgres = requirePostgres context+ endpoint = maybe (error "PostgreSQL TCP endpoint unavailable") (\(host, port) -> pure (Text.unpack host, fromIntegral port)) postgres.tcpEndpoint+ withTcpProxy endpoint \proxy -> do+ let connection = proxiedConnectionString postgres proxy+ baseline <- psql connection "select 1"+ setProxyMode proxy (Latency 40)+ started <- getCurrentTime+ delayed <- psql connection "select 1"+ ended <- getCurrentTime+ setProxyMode proxy Stall+ stalled <- async (psql connection "select pg_sleep(0.05)")+ threadDelay 150000+ wasStalled <- isNothing <$> poll stalled+ setProxyMode proxy Forward+ stallResult <- wait stalled+ setProxyMode proxy Blackhole+ blackholeResult <- timeout 500000 (psql connection "select 1")+ let wasBlackholed = isNothing blackholeResult+ resetCount <- resetConnections proxy+ setProxyMode proxy Forward+ recovered <- psql connection "select 1"+ let delayMillis = floor (diffUTCTime ended started * 1000) :: Int+ held = baseline == Right "1" && delayed == Right "1" && delayMillis >= 40 && wasStalled && stallResult == Right "" && wasBlackholed && resetCount > 0 && recovered == Right "1"+ now <- getCurrentTime+ let verdict = Verdict "proxy-effects" "network-faults-are-observable" Contract (if held then Held else Violated) Nothing "The proxy delayed, stalled, blackholed, reset, and then recovered a real PostgreSQL connection." (Map.fromList [("examined", 5), ("violations", if held then 0 else 1)]) (object ["delayMillis" .= delayMillis, "stalled" .= wasStalled, "blackholed" .= wasBlackholed, "resetConnections" .= resetCount]) [] False [] Nothing now 0+ finishWithVerdicts environment [verdict]++psql :: Text -> Text -> IO (Either Text Text)+psql connection statement = do+ (code, output, err) <- readProcessWithExitCode "psql" ["-d", Text.unpack connection, "-Atqc", Text.unpack statement] ""+ pure case code of ExitSuccess -> Right (Text.strip (Text.pack output)); ExitFailure _ -> Left (Text.strip (Text.pack err))++isNothing :: Maybe value -> Bool+isNothing Nothing = True+isNothing (Just _) = False++telemetryOff :: DimensionSupport+telemetryOff = DimensionSupport (Supported (Support (TracingOff :| []) TracingOff)) (Supported (Support (MetricsOff :| []) MetricsOff)) NotApplicable NotApplicable
+ src/Kenshou/Check/Verdict.hs view
@@ -0,0 +1,120 @@+module Kenshou.Check.Verdict+ ( InvariantClass (..),+ VerdictStatus (..),+ InputRef (..),+ Replay (..),+ RunInfo (..),+ Verdict (..),+ writeVerdict,+ outcomeFromVerdicts,+ )+where++import Control.Monad (unless)+import Data.Aeson+import Data.ByteString.Lazy qualified as LazyByteString+import Data.Int (Int64)+import Data.Map.Strict (Map)+import Data.Map.Strict qualified as Map+import Data.Text (Text)+import Data.Text qualified as Text+import Data.Time (UTCTime)+import Kenshou.Core.Id (RunId, ScenarioId)+import Kenshou.Core.Outcome (Outcome (..))+import System.Directory (createDirectoryIfMissing, renameFile)+import System.FilePath ((</>))++data InvariantClass = Contract | Implementation deriving stock (Eq, Ord, Show)++data VerdictStatus = Held | Violated | NotEvaluated deriving stock (Eq, Ord, Show)++data InputRef = InputRef {path :: !FilePath, sha256 :: !Text} deriving stock (Eq, Show)++data Replay = Replay+ { seed :: !Word,+ size :: !Int,+ shrinkPath :: ![Int],+ command :: !Text+ }+ deriving stock (Eq, Show)++data RunInfo = RunInfo {runId :: !RunId, scenario :: !ScenarioId} deriving stock (Eq, Show)++data Verdict = Verdict+ { checker :: !Text,+ invariant :: !Text,+ cls :: !InvariantClass,+ status :: !VerdictStatus,+ reason :: !(Maybe Text),+ summary :: !Text,+ counts :: !(Map Text Int64),+ parameters :: !Value,+ counterExamples :: ![Value],+ counterExamplesTruncated :: !Bool,+ inputs :: ![InputRef],+ replay :: !(Maybe Replay),+ checkedAt :: !UTCTime,+ durationMillis :: !Int64+ }+ deriving stock (Eq, Show)++writeVerdict :: FilePath -> RunInfo -> Verdict -> IO FilePath+writeVerdict directory runInfo verdict = do+ unless (all (`Map.member` verdict.counts) ["examined", "violations"]) $+ ioError (userError ("verdict " <> Text.unpack verdict.checker <> " lacks required examined/violations counters"))+ createDirectoryIfMissing True directory+ let path = directory </> sanitise verdict.checker <> ".json"+ temporary = path <> ".tmp"+ LazyByteString.writeFile temporary (encode (verdictDocument runInfo verdict) <> "\n")+ renameFile temporary path+ pure path+ where+ sanitise = fmap (\character -> if character == '/' then '-' else character) . Text.unpack++outcomeFromVerdicts :: [Verdict] -> Outcome+outcomeFromVerdicts verdicts+ | any isContractViolation verdicts = Failed+ | any isSearchExhausted verdicts = Inconclusive+ | any isContractUnevaluated verdicts = Errored+ | otherwise = Passed+ where+ isContractViolation verdict = verdict.cls == Contract && verdict.status == Violated+ isSearchExhausted verdict = verdict.cls == Contract && verdict.status == NotEvaluated && verdict.reason == Just "search-budget-exhausted"+ isContractUnevaluated verdict = verdict.cls == Contract && verdict.status == NotEvaluated++verdictDocument :: RunInfo -> Verdict -> Value+verdictDocument runInfo verdict =+ object+ [ "schema" .= ("kenshou.verdict/v1" :: Text),+ "runId" .= runInfo.runId,+ "scenario" .= runInfo.scenario,+ "checker" .= verdict.checker,+ "invariant" .= verdict.invariant,+ "class" .= classText verdict.cls,+ "status" .= statusText verdict.status,+ "blocking" .= (verdict.cls == Contract),+ "reason" .= verdict.reason,+ "summary" .= verdict.summary,+ "counts" .= verdict.counts,+ "parameters" .= verdict.parameters,+ "counterExamples" .= verdict.counterExamples,+ "counterExamplesTruncated" .= verdict.counterExamplesTruncated,+ "inputs" .= verdict.inputs,+ "replay" .= verdict.replay,+ "checkedAt" .= verdict.checkedAt,+ "durationMillis" .= verdict.durationMillis+ ]++classText :: InvariantClass -> Text+classText Contract = "contract"+classText Implementation = "implementation"++statusText :: VerdictStatus -> Text+statusText Held = "held"+statusText Violated = "violated"+statusText NotEvaluated = "not-evaluated"++instance ToJSON InputRef where toJSON value = object ["path" .= value.path, "sha256" .= value.sha256]++instance ToJSON Replay where+ toJSON value = object ["seed" .= value.seed, "size" .= value.size, "shrinkPath" .= value.shrinkPath, "command" .= value.command]
+ src/Kenshou/Check/Window.hs view
@@ -0,0 +1,52 @@+module Kenshou.Check.Window+ ( DisturbanceWindow (..),+ SkewBound (..),+ loadWindows,+ windowContains,+ )+where++import Data.Aeson (Value (..))+import Data.Aeson.Key qualified as Key+import Data.Aeson.KeyMap qualified as KeyMap+import Data.Int (Int64)+import Data.List (sortOn)+import Data.Map.Strict qualified as Map+import Data.Text (Text)+import Kenshou.Check.Fact+import Kenshou.Check.Ledger.Read++data DisturbanceWindow = DisturbanceWindow+ { label :: !Text,+ target :: !Text,+ start :: !Int64,+ end :: !(Maybe Int64)+ }+ deriving stock (Eq, Show)++newtype SkewBound = SkewBound {micros :: Int64}+ deriving stock (Eq, Ord, Show)++loadWindows :: LedgerSet -> IO [DisturbanceWindow]+loadWindows ledger = do+ facts <- foldFacts ledger [] (\items fact -> pure (if fact.kind `elem` [DisturbanceStart, DisturbanceEnd] then fact : items else items))+ pure (assemble (sortOn (\fact -> (fact.wall, fact.n)) facts))+ where+ assemble = finish . foldl step (Map.empty, [])+ step (open, closed) fact =+ let label = attrText "label" fact.attrs fact.id+ target = attrText "target" fact.attrs fact.key+ key = (label, target)+ in case fact.kind of+ DisturbanceStart -> (Map.insert key fact.wall open, closed)+ DisturbanceEnd -> case Map.lookup key open of+ Nothing -> (open, closed)+ Just started -> (Map.delete key open, DisturbanceWindow label target started (Just fact.wall) : closed)+ _ -> (open, closed)+ finish (open, closed) = reverse closed <> [DisturbanceWindow label target started Nothing | ((label, target), started) <- Map.toAscList open]++windowContains :: SkewBound -> Int64 -> DisturbanceWindow -> Bool+windowContains (SkewBound skew) instant window = instant >= window.start - skew && maybe True (instant <=) ((+ skew) <$> window.end)++attrText :: Text -> KeyMap.KeyMap Value -> Text -> Text+attrText key attrs fallback = case KeyMap.lookup (Key.fromText key) attrs of Just (String value) -> value; _ -> fallback
+ test/Main.hs view
@@ -0,0 +1,170 @@+module Main (main) where++import Control.Monad (forM_)+import Data.Aeson (Object, Value (Number), decode, encode, object)+import Data.Aeson.Key qualified as Key+import Data.Aeson.KeyMap qualified as KeyMap+import Data.IORef+import Data.Int (Int64)+import Data.List (sortOn)+import Data.Map.Strict qualified as Map+import Data.Maybe (isNothing)+import Data.Text qualified as Text+import Kenshou.Check.Fact+import Kenshou.Check.Invariant+import Kenshou.Check.Ledger+import Kenshou.Check.Ledger.Read+import Kenshou.Check.Ledger.Sort+import Kenshou.Check.Model.Linearizability+import Kenshou.Check.Oracle (OracleQuery (..), OracleSpec (..), fromSpec, registeredOracle)+import Kenshou.Check.Process+import Kenshou.Check.Scenario+import Kenshou.Check.Verdict+import Kenshou.Check.Verdict qualified as Verdict+import Kenshou.Core.Bundle (LayerBundle (..), mkBundle, mkRegistry)+import Kenshou.Core.Context+import Kenshou.Core.Dimension (emptyDimensions)+import Kenshou.Core.Id (mkSeed, newRunId, parseScenarioId, selftestLayer)+import Kenshou.Core.Knob (resolveKnobs)+import Kenshou.Core.Log (nullLogger)+import Kenshou.Core.Phase (zeroPhases)+import Kenshou.Core.RunSpec (RunSpec (..), minimalRunSpec)+import System.Directory (listDirectory)+import System.FilePath ((</>))+import System.IO.Temp (withSystemTempDirectory)+import System.Mem (performMajorGC)+import System.Mem.Weak (Weak, deRefWeak, mkWeakPtr)+import Test.Hspec++main :: IO ()+main = hspec do+ describe "registered oracles" do+ let spec = OracleSpec "queued-rows" "select count(*) from kenshou_selftest.roundtrip"+ bundle = (mkBundle selftestLayer [] []) {oracles = [spec]}+ it "finds an oracle a bundle registers and builds its query" do+ registry <- either (fail . show) pure (mkRegistry [bundle])+ registeredOracle registry selftestLayer "queued-rows" `shouldBe` Just spec+ registeredOracle registry selftestLayer "missing" `shouldBe` Nothing+ let query = fromSpec spec Right+ (query.name, query.sql) `shouldBe` (spec.name, spec.sql)+ it "rejects two oracles with one name in a bundle" do+ either (const True) (const False) (mkRegistry [bundle {oracles = [spec, spec]}]) `shouldBe` True+ describe "verdict protocol" do+ it "rejects missing assertion counters before writing a document" $ withSystemTempDirectory "kenshou-verdict-protocol" \directory -> do+ runId <- newRunId+ let scenario = either (error . show) id (parseScenarioId "selftest/check/correctness/verdict-protocol")+ runInfo = RunInfo runId scenario+ valid = Verdict "protocol" "required-counters" Contract Held Nothing "protocol fixture" (Map.fromList [("examined", 1), ("violations", 0)]) (object []) [] False [] Nothing (read "2026-01-01 00:00:00 UTC") 0+ forM_ ["examined", "violations"] \key ->+ writeVerdict directory runInfo valid {Verdict.counts = Map.delete key valid.counts} `shouldThrow` anyIOException+ listDirectory directory `shouldReturn` []+ _ <- writeVerdict directory runInfo valid+ listDirectory directory `shouldReturn` ["protocol.json"]+ describe "Fact" do+ it "round-trips through JSON" do+ let fact = Fact Produced "stream" 3 "event" "writer/0" (ProcId "writer" 0 0) 1 2 3 KeyMap.empty+ decode (encode fact) `shouldBe` Just fact++ describe "Ledger" do+ it "rotates immutable segments and reads every fact" $ withSystemTempDirectory "kenshou-ledger" \directory -> do+ let config = LedgerConfig directory (ProcId "writer" 0 0) "run" 1024 (ClockInfo SameHost 1000)+ withLedger config \writer -> forM_ [1 .. 200 :: Int64] \number -> record writer Produced "key" number (Text.pack (show number)) KeyMap.empty+ files <- listDirectory directory+ length files `shouldSatisfy` (> 1)+ ledger <- discoverLedgers directory+ count <- foldFacts ledger (0 :: Int) (\value _ -> pure (value + 1))+ count `shouldBe` 200++ it "drops a torn final fact line" $ withSystemTempDirectory "kenshou-torn" \directory -> do+ let config = LedgerConfig directory (ProcId "writer" 0 0) "run" 1000000 (ClockInfo SameHost 1000)+ withLedger config \writer -> record writer Produced "key" 1 "one" KeyMap.empty+ [path] <- fmap (directory </>) <$> listDirectory directory+ appendFile path "{\"schema\":\"kenshou.ledger-fact/v1\""+ ledger <- discoverLedgers directory+ count <- foldFacts ledger (0 :: Int) (\value _ -> pure (value + 1))+ count `shouldBe` 1++ describe "external sort" do+ it "matches an in-memory sort across many runs" $ withSystemTempDirectory "kenshou-sort" \directory -> do+ let ledgerDir = directory </> "ledger"+ config = LedgerConfig ledgerDir (ProcId "writer" 0 0) "run" 10000000 (ClockInfo SameHost 1000)+ facts = [1000, 999 .. 1 :: Int64]+ withLedger config \writer -> forM_ facts \number -> record writer Produced (Text.pack (show (number `mod` 13))) number (Text.pack (show number)) KeyMap.empty+ ledger <- discoverLedgers ledgerDir+ collected <- newIORef []+ sortedFacts (SortConfig (ledgerDir </> ".sort") 17 8) ByKeySeq (const True) ledger \source -> drain source collected+ actual <- readIORef collected+ fmap (\fact -> (fact.key, fact.seq)) actual `shouldBe` sortOn id [(Text.pack (show (number `mod` 13)), number) | number <- facts]++ describe "invariant checkers" do+ let cases =+ [ ("no-loss", noLoss "no-loss" Contract "consumer", cleanDelivery, [fact Produced "producer" 1 1 mempty]),+ ("duplicates", duplicatesWithin "duplicates" Contract "consumer" (DuplicateBudget (Just 0) Nothing) [], [fact Observed "consumer" 1 1 mempty], [fact Observed "consumer" 1 1 mempty, fact Observed "consumer" 2 1 mempty]),+ ("per-key-order", perKeyOrder "per-key-order" Contract "consumer", [fact Observed "consumer" 1 1 mempty, fact Observed "consumer" 2 2 mempty], [fact Observed "consumer" 1 2 mempty, fact Observed "consumer" 2 1 mempty]),+ ("global-order", globalOrder "global-order" Contract "consumer" "gp", [fact Observed "consumer" 1 1 (gp 1), fact Observed "consumer" 2 2 (gp 2)], [fact Observed "consumer" 1 1 (gp 2), fact Observed "consumer" 2 2 (gp 1)]),+ ("gapless", gaplessPositions "gapless" Implementation, [fact Produced "producer" 1 1 mempty, fact Produced "producer" 2 2 mempty], [fact Produced "producer" 1 1 mempty, fact Produced "producer" 2 3 mempty]),+ ("effects", exactlyNEffects "effects" Contract 1, [fact Effect "consumer" 1 1 mempty], [fact Effect "consumer" 1 1 mempty, fact Effect "consumer" 2 1 mempty]),+ ("quiescence", eventualQuiescence "quiescence" Contract (Deadline 1000), [fact Produced "producer" 1 1 mempty, fact Terminal "consumer" 2 1 mempty], [fact Produced "producer" 1 1 mempty]),+ ("checkpoint", monotonicCheckpoints "checkpoint" Contract, [fact Checkpoint "consumer" 1 1 mempty, fact Checkpoint "consumer" 2 2 mempty], [fact Checkpoint "consumer" 1 2 mempty, fact Checkpoint "consumer" 2 1 mempty]),+ ("ownership", disjointOwnership "ownership" Contract, [fact Acquired "owner-a" 1 1 mempty, fact Acted "owner-a" 2 1 mempty, fact Released "owner-a" 3 1 mempty], [fact Acquired "owner-a" 1 1 mempty, fact Acquired "owner-b" 2 1 mempty, fact Acted "owner-a" 3 1 mempty])+ ]+ forM_ cases \(label, checker, heldFacts, violatedFacts) -> do+ it (label <> " holds for valid facts") $ (evaluateChecker checker heldFacts).status `shouldBe` Held+ it (label <> " rejects a targeted mutation") $ (evaluateChecker checker violatedFacts).status `shouldBe` Violated+ it (label <> " refuses a vacuous pass") $ (evaluateChecker checker []).status `shouldBe` NotEvaluated++ describe "process supervisor" do+ it "releases retired children before supervisor cleanup" $ withSystemTempDirectory "kenshou-retirement" \directory -> do+ runId <- newRunId+ state <- newRunState+ let scenario = either (error . show) id (parseScenarioId "selftest/check/process/retirement")+ knobs = either (error . show) id (resolveKnobs [] [])+ seed = either (error . show) id (mkSeed 0)+ runContext = RunContext runId scenario knobs emptyDimensions seed zeroPhases (Environment Nothing mempty mempty) (minimalRunSpec scenario).environment Nothing directory nullLogger state+ withCheck runContext \environment -> withSupervisor environment \supervisor -> do+ weak <- retireFixture supervisor+ performMajorGC+ (isNothing <$> deRefWeak weak) `shouldReturn` True+ windows <- crashWindows supervisor+ length windows `shouldBe` 1++ describe "linearizability" do+ it "accepts and rejects register histories" do+ let valid = [Operation "p1" "register" (WriteRegister 1) 0 (Just 1) (Returned Written), Operation "p2" "register" ReadRegister 2 (Just 3) (Returned (ReadValue (Just 1)))]+ invalid = [Operation "p1" "register" (WriteRegister 1) 0 (Just 1) (Returned Written), Operation "p2" "register" ReadRegister 2 (Just 3) (Returned (ReadValue Nothing))]+ checkLinearizable defaultLinConfig registerModel valid `shouldBe` Linearizable+ checkLinearizable defaultLinConfig registerModel invalid `shouldSatisfy` isRejected++ it "accepts and rejects append-log histories" do+ let valid = [Operation "p1" "log" (Append "a") 0 (Just 1) (Returned (Appended 0)), Operation "p2" "log" ReadLog 2 (Just 3) (Returned (LogContents ["a"]))]+ invalid = [Operation "p1" "log" (Append "a") 0 (Just 1) (Returned (Appended 0)), Operation "p2" "log" ReadLog 2 (Just 3) (Returned (LogContents []))]+ checkLinearizable defaultLinConfig appendLogModel valid `shouldBe` Linearizable+ checkLinearizable defaultLinConfig appendLogModel invalid `shouldSatisfy` isRejected++drain :: FactSource -> IORef [Fact] -> IO ()+drain source output =+ source.next >>= \case+ Nothing -> pure ()+ Just fact -> modifyIORef' output (<> [fact]) >> drain source output++fact :: FactKind -> Text.Text -> Word -> Int64 -> Object -> Fact+fact kind scope n sequenceNumber attrs = Fact kind "key" sequenceNumber "item" scope (ProcId scope 0 0) (fromIntegral n) (fromIntegral n) (fromIntegral n * 100) attrs++gp :: Int64 -> Object+gp value = KeyMap.singleton (Key.fromText "gp") (Number (fromIntegral value))++cleanDelivery :: [Fact]+cleanDelivery = [fact Intent "producer" 1 1 mempty, fact Produced "producer" 2 1 mempty, fact Observed "consumer" 3 1 mempty]++isRejected :: LinResult -> Bool+isRejected (NotLinearizable _) = True+isRejected _ = False++-- Keep the caller from retaining the fixture across the major collection.+{-# NOINLINE retireFixture #-}+retireFixture :: Supervisor -> IO (Weak Child)+retireFixture supervisor = do+ child <- spawn supervisor (ProcessSpec (ProcId "retirement" 0 0) "kenshou-check-fixture-worker" [] [] Nothing)+ weak <- mkWeakPtr child Nothing+ killChild supervisor child+ pure weak
+ test/golden/verdict.json view
@@ -0,0 +1,1 @@+{"schema":"kenshou.verdict/v1"}