packages feed

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 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"}