Basic.lookup hangs about hashtables

[gregorycollins]

A reproduction test case would help. It's always possible that there's a hard-to-trigger bug there, which would make it hard to reproduce, but without a consistently failing test case it's hard to do anything about it.

[tmcdonell]

I don't seem to be able to add attachments, so here is my test code inline. There is an attempt to shrink the test case pulled directly from my application to something shorter and more manageable; note that this relies on using timeout, which is unable to interrupt FFI code, but you can verify that the shorter sequence hangs in both the standard and portable configurations.

Does this bug also trigger on your machine?

module Main where

import Prelude
import Control.Monad
import Test.QuickCheck.Arbitrary
import System.IO
import System.Timeout

import qualified Data.HashTable.IO              as Hash

type HashTable key val = Hash.BasicHashTable key val

data Action = Lookup Int
            | Insert Int
            | Delete Int
            deriving Show


main :: IO ()
main = do
  res <- test [complete]
  putStrLn $ case res of
    Nothing -> "All tests passed... (?)"
    Just as -> unlines $ [ ""
                         , "minimal sequence length: " ++ show (length as)
                         , show as
                         ]
  where
    -- timeout is measured in microseconds
    --
    wait = 1 * sec
    sec  = 1000000

    -- Run a sequence of actions. If the sequence completes, return Nothing,
    -- otherwise attempt to shrink the failing test case and return the smallest
    -- set of commands that trigger the bug.
    --
    test []     = return Nothing
    test (a:as) = do
      tbl <- Hash.new
      res <- timeout wait $ foldM_ (\t k -> apply t k >> return t) tbl a
      case res of
           Just _  -> test as   -- sequence ok; continue
           Nothing -> do        -- this triggered the bug
             putChar '.' >> hFlush stdout
             res' <- test (shrinkList shrinkNothing a)
             case res' of
                  Nothing -> return (Just a)    -- all smaller sequences are ok
                  Just a' -> return (Just a')

    apply :: HashTable Int () -> Action -> IO ()
    apply tbl (Lookup key) = void $ Hash.lookup tbl key
    apply tbl (Insert key) = Hash.insert tbl key ()
    apply tbl (Delete key) = Hash.delete tbl key



-- A minimal test case. We use timeout above to cancel operations that have
-- gotten stuck in a loop, but this relies on asynchronous exceptions. This is
-- useless when calling into FFI code, but we can run the shrinking when running
-- in portable mode (pure Haskell only) and verify that the bug is still hit
-- using the equivalent C functions.
--
minimal :: [Action]
minimal =
  [ Insert 28
  , Insert 27
  , Insert 30
  , Insert 31
  , Insert 32
  , Insert 33
  , Insert 34
  , Insert 29
  , Insert 36
  , Insert 37
  , Delete 34
  , Delete 29
  , Insert 38
  , Insert 39
  , Insert 40
  , Insert 35
  , Delete 39
  , Insert 42
  , Insert 43
  , Delete 40
  , Delete 35
  , Insert 44
  , Insert 45
  , Insert 41
  , Insert 48
  , Insert 47
  , Insert 50
  , Insert 51
  , Insert 52
  , Insert 49
  , Insert 54
  , Insert 53
  , Insert 56
  , Insert 55
  , Insert 58
  , Insert 57
  , Insert 60
  , Insert 59
  , Delete 60
  , Insert 62
  , Insert 61
  , Insert 63
  , Insert 46
  , Lookup 66
  ]

-- The complete failing test case, pulled directly from the application
--
complete :: [Action]
complete =
  [ Lookup 17
  , Insert 17
  , Lookup 16
  , Insert 16
  , Lookup 16
  , Lookup 17
  , Lookup 15
  , Insert 15
  , Lookup 15
  , Lookup 16
  , Lookup 15
  , Delete 16
  , Delete 15
  , Lookup 17
  , Lookup 20
  , Insert 20
  , Lookup 20
  , Lookup 17
  , Lookup 21
  , Insert 21
  , Lookup 21
  , Lookup 20
  , Lookup 21
  , Lookup 17
  , Lookup 22
  , Insert 22
  , Lookup 22
  , Lookup 17
  , Lookup 23
  , Insert 23
  , Lookup 23
  , Lookup 22
  , Lookup 23
  , Delete 20
  , Delete 21
  , Lookup 17
  , Lookup 24
  , Insert 24
  , Lookup 24
  , Lookup 17
  , Lookup 25
  , Insert 25
  , Lookup 25
  , Lookup 24
  , Lookup 25
  , Lookup 17
  , Lookup 19
  , Insert 19
  , Lookup 19
  , Lookup 17
  , Lookup 18
  , Insert 18
  , Lookup 18
  , Lookup 19
  , Lookup 18
  , Delete 22
  , Delete 23
  , Delete 24
  , Delete 25
  , Lookup 17
  , Lookup 28
  , Insert 28
  , Lookup 28
  , Lookup 17
  , Lookup 27
  , Insert 27
  , Lookup 27
  , Lookup 28
  , Lookup 27
  , Delete 19
  , Delete 18
  , Lookup 17
  , Lookup 30
  , Insert 30
  , Lookup 30
  , Lookup 17
  , Lookup 31
  , Insert 31
  , Lookup 31
  , Lookup 30
  , Lookup 31
  , Delete 28
  , Delete 27
  , Delete 30
  , Lookup 17
  , Lookup 32
  , Insert 32
  , Lookup 32
  , Lookup 17
  , Lookup 33
  , Insert 33
  , Lookup 33
  , Lookup 32
  , Lookup 33
  , Lookup 17
  , Lookup 34
  , Insert 34
  , Lookup 34
  , Lookup 17
  , Lookup 29
  , Insert 29
  , Lookup 29
  , Lookup 34
  , Lookup 29
  , Delete 31
  , Delete 32
  , Delete 33
  , Lookup 17
  , Lookup 36
  , Insert 36
  , Lookup 36
  , Lookup 17
  , Lookup 37
  , Insert 37
  , Lookup 37
  , Lookup 36
  , Lookup 37
  , Delete 34
  , Delete 29
  , Lookup 17
  , Lookup 38
  , Insert 38
  , Lookup 38
  , Lookup 17
  , Lookup 39
  , Insert 39
  , Lookup 39
  , Lookup 38
  , Lookup 39
  , Lookup 17
  , Lookup 40
  , Insert 40
  , Lookup 40
  , Lookup 17
  , Lookup 35
  , Insert 35
  , Lookup 35
  , Lookup 40
  , Lookup 35
  , Delete 37
  , Delete 36
  , Delete 38
  , Delete 39
  , Lookup 17
  , Lookup 42
  , Insert 42
  , Lookup 42
  , Lookup 17
  , Lookup 43
  , Insert 43
  , Lookup 43
  , Lookup 42
  , Lookup 43
  , Delete 40
  , Delete 35
  , Lookup 17
  , Lookup 44
  , Insert 44
  , Lookup 44
  , Lookup 17
  , Lookup 45
  , Insert 45
  , Lookup 45
  , Lookup 44
  , Lookup 45
  , Lookup 17
  , Lookup 41
  , Insert 41
  , Lookup 41
  , Lookup 17
  , Lookup 26
  , Insert 26
  , Lookup 26
  , Lookup 41
  , Lookup 26
  , Delete 42
  , Delete 43
  , Delete 44
  , Delete 45
  , Lookup 17
  , Lookup 48
  , Insert 48
  , Lookup 48
  , Lookup 17
  , Lookup 47
  , Insert 47
  , Lookup 47
  , Lookup 48
  , Lookup 47
  , Lookup 17
  , Lookup 50
  , Insert 50
  , Lookup 50
  , Lookup 17
  , Lookup 51
  , Insert 51
  , Lookup 51
  , Lookup 50
  , Lookup 51
  , Delete 41
  , Delete 26
  , Lookup 17
  , Lookup 52
  , Insert 52
  , Lookup 52
  , Lookup 17
  , Lookup 49
  , Insert 49
  , Lookup 49
  , Lookup 52
  , Lookup 49
  , Delete 48
  , Delete 47
  , Delete 50
  , Delete 51
  , Lookup 17
  , Lookup 54
  , Insert 54
  , Lookup 54
  , Lookup 17
  , Lookup 53
  , Insert 53
  , Lookup 53
  , Lookup 54
  , Lookup 53
  , Delete 52
  , Lookup 17
  , Lookup 56
  , Insert 56
  , Lookup 56
  , Lookup 17
  , Lookup 55
  , Insert 55
  , Lookup 55
  , Lookup 56
  , Lookup 55
  , Lookup 17
  , Lookup 58
  , Insert 58
  , Lookup 58
  , Lookup 17
  , Lookup 57
  , Insert 57
  , Lookup 57
  , Lookup 58
  , Lookup 57
  , Lookup 17
  , Lookup 60
  , Insert 60
  , Lookup 60
  , Lookup 17
  , Lookup 59
  , Insert 59
  , Lookup 59
  , Lookup 60
  , Lookup 59
  , Delete 60
  , Lookup 17
  , Lookup 62
  , Insert 62
  , Lookup 62
  , Lookup 17
  , Lookup 61
  , Insert 61
  , Lookup 61
  , Lookup 62
  , Lookup 61
  , Lookup 17
  , Lookup 63
  , Insert 63
  , Lookup 63
  , Lookup 17
  , Lookup 46
  , Insert 46
  , Lookup 46
  , Lookup 63
  , Lookup 46
  , Delete 62
  , Delete 61
  , Delete 63
  , Lookup 17
  , Lookup 66
  ]

[gregorycollins]

Thanks so much for the test case!

I've isolated the problem, and it's really stupid of me -- what's happening here is that the cache line search loops forever if the table doesn't have any empty markers in it. This can happen after the right sequence of inserts and deletes. I need to rewrite the search routines to quit after traversing the entire array.

[gregorycollins]

Hi Trevor,

Could you please test the fix before I release a new version of the package?

[tmcdonell]

Another test case, this one related to forwardSearch64_3(). Seems to get (*p == x3) on the first pass; the function exits then is called again with the same parameters. Repeat.

testData =
  [ Insert 65
  , Insert 66
  , Insert 67
  , Insert 74
  , Insert 75
  , Insert 76
  , Insert 77
  , Insert 79
  , Insert 80
  , Insert 81
  , Insert 82
  , Insert 83
  , Insert 84
  , Delete 81
  , Delete 82
  , Insert 85
  , Insert 86
  , Insert 87
  , Insert 88
  , Insert 89
  , Insert 90
  , Insert 78
  , Insert 93
  , Insert 94
  , Insert 95
  , Insert 96
  , Insert 97
  , Insert 92
  , Delete 93
  , Delete 94
  , Delete 95
  , Delete 96
  , Insert 99
  , Insert 100
  , Insert 101
  , Insert 102
  , Insert 103
  , Insert 104
  , Insert 98
  , Insert 91
  , Insert 108
  , Insert 109
  , Insert 110
  , Insert 111
  ]

[tmcdonell]

edit: forwardSearch64_3 gets the same array pointer, and it is the start value which loops between [1,end].

[gregorycollins]

Hey Trevor,

The HEAD version with your latest test case doesn't fail for me. I'm checking in a new test, could you confirm?

[tmcdonell]

It does, but you have to check the result of timeout, c.f. #3.

[gregorycollins]

OK -- phew -- I think the deletion logic has also been corrected here. It also necessitated a bunch of extra logic to force a rehash of the table when it gets cluttered up with deleted entries (because otherwise probes turn O(n)).

Could you please confirm?

[tmcdonell]

Great! Everything seems to be working, no problems encountered so far. Thanks!

[gregorycollins]

1.0.1.0 released, thanks so much for the testing!