packages feed

haskoin-store-1.16.0: test/Haskoin/Store/Web/CongestionSpec.hs

{-# LANGUAGE OverloadedRecordDot #-}

-- | The controller of the limit on long requests, alone, and the probes of
-- the scheduler's delay that it follows.
module Haskoin.Store.Web.CongestionSpec (spec) where

import Control.Concurrent (getNumCapabilities, threadDelay)
import Control.Concurrent.Async (withAsyncOn)
import Control.Exception (evaluate)
import Control.Monad (forever, unless, when)
import Data.IORef (newIORef, readIORef, writeIORef)
import Data.IntMap.Strict qualified as IntMap
import GHC.Stats (getRTSStatsEnabled)
import Haskoin.Store.Web.Congestion
import System.Mem (performMajorGC)
import Test.Hspec
import Test.Hspec.QuickCheck (prop)
import Test.QuickCheck

spec :: Spec
spec = do
  describe "the controller of the limit" $ do
    prop "keeps the limit between the floor and the ceiling" $
      forAll settings $ \c -> forAll (start c) $ \w ->
        forAll (listOf (observation c)) $ \os ->
          all (\x -> c.floor <= x.limit && x.limit <= c.ceiling) (steps c w os)

    prop "comes down to the floor while the delay stays over the target" $
      forAll settings $ \c -> forAll (start c) $ \w ->
        forAll (vectorOf 64 (congested c)) $ \os ->
          let ms = map (.limit) (steps c w os)
           in last ms == c.floor && and (zipWith (>=) ms (drop 1 ms))

    prop "cuts at most once a round trip" $
      forAll settings $ \c -> forAll (start c) $ \w -> forAll (chooseInt (0, 5000000)) $ \rtt ->
        forAll (listOf (congested c)) $ \os ->
          let os' = [o {roundTrip = rtt} | o <- os]
              ws = drop 1 (steps c w os')
              -- microseconds since the last cut, before each step
              since = scanl (\t (o, x) -> if x.sinceCut == 0 then 0 else t + o.elapsed) w.sinceCut (zip os' ws)
           in and [t + o.elapsed >= rtt | (t, o, x) <- zip3 since os' ws, x.sinceCut == 0]

    prop "never grows while it is not saturated, or while the cores are busy" $
      forAll settings $ \c -> forAll (start c) $ \w ->
        forAll (listOf (observation c)) $ \os -> forAll (chooseInt (90, 200)) $ \busy ->
          let idle = map (.limit) (steps c w [o {saturated = False} | o <- os])
              full = map (.limit) (steps c w [o {used = busy} | o <- os])
           in and (zipWith (>=) idle (drop 1 idle)) && and (zipWith (>=) full (drop 1 full))

    prop "never cuts while the cores have room" $
      forAll settings $ \c -> forAll (start c) $ \w ->
        forAll (listOf (congested c)) $ \os -> forAll (chooseInt (0, 89)) $ \idle ->
          let ms = map (.limit) (steps c w [o {used = idle} | o <- os])
           in and (zipWith (<=) ms (drop 1 ms))

    prop "is free to rise only while the cores have room, under the ceiling" $
      forAll settings $ \c -> forAll (start c) $ \w -> forAll (observation c) $ \o ->
        rising c o w == (o.used < 90 && w.limit < c.ceiling)

    prop "grows back to the level of the last cut, then past it to the ceiling" $
      forAll settings $ \c -> forAll (chooseInt (c.floor, c.ceiling)) $ \n ->
        let w = (window c) {limit = n, level = fromIntegral n, peak = fromIntegral n}
            cut = control c (Observation (c.target + 1) 95 True 0 500000) w
            climb = steps c cut (replicate 400 (calm c))
            -- seconds on the curve at each step
            times = [0.5 * fromIntegral i :: Double | i <- [0 :: Int ..]]
            early = [x.limit | (x, t) <- zip climb times, t < cut.knee]
            past = [x.limit | (x, t) <- zip climb times, t >= cut.knee + 0.5]
         in all (<= n) early
              && all (>= n) (take 1 past)
              && last (map (.limit) climb) == c.ceiling
              && and (zipWith (<=) (map (.limit) climb) (drop 1 (map (.limit) climb)))

    prop "never moves a fixed limit" $
      forAll settings $ \c0 -> forAll (listOf (observation c0)) $ \os ->
        let c = c0 {ceiling = c0.floor}
         in all ((== c.floor) . (.limit)) (steps c (window c) os)

  describe "the percentile" $ do
    it "is the value at its rank" $ do
      percentile 90 [1 .. 100] `shouldBe` 90
      percentile 90 [100, 99 .. 1] `shouldBe` 90
      percentile 90 [7] `shouldBe` 7
      percentile 50 [1, 2, 3, 4] `shouldBe` 2
    it "is zero for no values" $
      percentile 90 [] `shouldBe` 0
    it "counts each value for its weight, when weighted" $ do
      weighted 90 [(x, 1) | x <- [1 .. 100]] `shouldBe` 90
      -- thirty wakes on time on an idle capability, and one of a busy
      -- capability, 500 µs late, which covers more time than all of them
      weighted 90 ((500, 510) : replicate 30 (1, 10)) `shouldBe` 500
      percentile 90 (500 : replicate 30 1) `shouldBe` 1
      weighted 90 [] `shouldBe` 0

  describe "the probes of the scheduler's delay" $ do
    -- the target is 25 ms; the thresholds leave a factor of two either way
    it "stay well under the target on idle capabilities" $
      withProbes $ \ps -> do
        _ <- lateness ps
        threadDelay 1000000
        d <- lateness ps
        d `shouldSatisfy` (< 12500)

    it "rise well over the target with four busy threads on each capability" $ do
      caps <- getNumCapabilities
      fourOn [0 .. caps - 1] $ withProbes $ \ps -> do
        _ <- lateness ps
        threadDelay 1000000
        d <- lateness ps
        d `shouldSatisfy` (> 50000)

    it "rise well over the target with four busy threads on one capability" $
      fourOn [0] $
        withProbes $ \ps -> do
          _ <- lateness ps
          threadDelay 1000000
          d <- lateness ps
          d `shouldSatisfy` (> 50000)

    it "take the pauses of the collector out of the scheduler's delay" $ do
      counted <- getRTSStatsEnabled
      unless counted $ pendingWith "GHC keeps no statistics without +RTS -T"
      -- a map of a million entries, copied by every major collection,
      -- which nothing else runs between
      held <- evaluate (IntMap.fromList [(i, i) | i <- [1 .. 1_000_000 :: Int]])
      withProbes $ \ps -> do
        _ <- delays ps
        before <- delays ps
        let collect n = when (n > (0 :: Int)) (performMajorGC >> collect (n - 1))
        collect 20
        d <- delays ps
        IntMap.size held `shouldBe` 1_000_000
        d.collected `shouldSatisfy` (> before.collected)
        d.raw `shouldSatisfy` (> 5000)
        d.scheduling `shouldSatisfy` (< d.raw `div` 2)
  where
    steps c = scanl (flip (control c))

-- | Run an action with four threads that compute on each of these
-- capabilities.
fourOn :: [Int] -> IO a -> IO a
fourOn caps act = foldr (\i k -> busy i (busy i (busy i (busy i k)))) act caps
  where
    busy i k = withAsyncOn i spin (const k)

-- | A thread that computes, and allocates, so that GHC can take its core
-- from it at the end of its timeslice.
spin :: IO ()
spin = do
  r <- newIORef (0 :: Int)
  forever $ readIORef r >>= \x -> writeIORef r $! x + 1

-- | Settings of the controller.
settings :: Gen Control
settings = do
  lo <- chooseInt (1, 64)
  hi <- chooseInt (lo, 1024)
  target <- chooseInt (1, 100000)
  return Control {floor = lo, ceiling = hi, target = target}

-- | A window that some steps led to from the start.
start :: Control -> Gen Window
start c = foldl (flip (control c)) (window c) <$> listOf (observation c)

-- | Anything that a step may see.
observation :: Control -> Gen Observation
observation c =
  Observation
    <$> chooseInt (0, 2 * c.target)
    <*> chooseInt (0, 150)
    <*> arbitrary
    <*> chooseInt (0, 2000000)
    <*> chooseInt (0, 1000000)

-- | A step with a delay over the target and the cores busy, a round trip
-- after the last cut.
congested :: Control -> Gen Observation
congested c =
  Observation
    <$> chooseInt (c.target + 1, 4 * c.target)
    <*> chooseInt (90, 150)
    <*> arbitrary
    <*> pure 0
    <*> chooseInt (1, 1000000)

-- | A step of half a second with a delay under the target, every slot
-- taken, and cores with room.
calm :: Control -> Observation
calm c = Observation (c.target - 1) 50 True 0 500000