Cuckoo loses data when inserting 65th element via mutate

[infinity0]

edit: see next comment for a much better and more minimal reproduction:

[infinity0]

Here's a much smaller example:

module Main where

import Control.Monad (forM_)
import Control.Monad.ST
import Data.Char

import qualified Data.HashTable.ST.Cuckoo as Cuckoo
import qualified Data.Set        as Set

main :: IO ()
main = do
  let orig = [0..64] :: [Int]
  let orig' = Set.fromList orig
  print $ length orig'
  final <- do
    temp <- stToIO Cuckoo.new
    --works fine:
    --forM_ orig $ \k -> stToIO $ Cuckoo.insert temp k ()
    forM_ orig $ \k -> stToIO $ Cuckoo.mutate temp k (const (Just (), ()))
    stToIO $ Cuckoo.foldM (fmap pure <$> flip (:)) [] temp
  let final' = Set.fromList $ fmap fst final
  print $ length final'
  putStrLn "diff:"
  print $ Set.difference orig' final'
  print $ Set.difference final' orig'

The problem is with Cuckoo.mutate and occurs when inserting the 65th element, presumably this causes a table resize which plays badly with mutate. insert is fine however.

[infinity0]

If you change 0..64 to 0..200000 even more data is lost:

200001
199984
diff:
fromList [48,205,384,783,1090,1118,2717,2799,3955,4668,7586,7785,11840,13313,17764,48620,130513]
fromList []

[infinity0]

@vbsd you wrote that function, can you take a look?

This bug only happens if the hashtable has 64 elements and you insert a new one using mutate, which isn't covered by the current testMutate - I'd suggest a new test that inserts 200000 elements using mutate and then deletes them all. That would cover a wider range of behaviours.

[vbsd]

@infinity0 I’m afraid there’s no way I can get to a computer until the next Monday or so. I’ll try to have a look then.

[infinity0]

@vbsd any update?

[infinity0]

@gregorycollins @vbsd ping :)

[fizbin]

Just slammed headfirst into this, and lost several hours not believing what my code was telling me.

Any update?

[erikd]

I am a co-maintainer. I will look at this on the weekend.

[erikd]

This is a modified version of the test which:

• Compares the Set extracted from the HashTable with the equivalent Set.
• Uses Cuckoo.insert for the first 64 elements and validates it against the equivalent Set.
• Inserts a 65th element using Cuckoo.mutate and validating against the equvalent Set.

It is this last operation which fails.

import           Control.Monad (unless)
import           Control.Monad.ST (stToIO)

import           Data.HashTable.ST.Cuckoo (HashTable)
import qualified Data.HashTable.ST.Cuckoo as Cuckoo
import           Data.Set (Set)
import qualified Data.Set as Set

import           GHC.Prim (RealWorld)

import           System.Exit (exitFailure)

type HT = HashTable RealWorld Int ()

main :: IO ()
main =
  simpleTest =<< stToIO Cuckoo.new


simpleTest :: HT -> IO ()
simpleTest ht = do
  let orig = [0..63]
  let intSet = Set.fromList orig
  htSet <- insertCuckoo ht orig
  let diff = Set.difference intSet htSet
  unless (Set.null diff) $ do
    print $ diff
    exitFailure

  let intSet2 = Set.insert 64 intSet
  htSet2 <- mutateInsertCuckoo ht [64]
  let diff2 = Set.difference intSet2 htSet2
  unless (Set.null diff2) $ do
    print $ diff2
    exitFailure
  putStrLn "pass"

insertCuckoo :: HT -> [Int] -> IO (Set Int)
insertCuckoo ht xs = do
  mapM_ (\k -> stToIO $ Cuckoo.insert ht k ()) xs
  extractAsSet ht

mutateInsertCuckoo :: HT -> [Int] -> IO (Set Int)
mutateInsertCuckoo ht xs = do
  mapM_ (\k -> stToIO $ Cuckoo.mutate ht k (const (Just (), ()))) xs
  extractAsSet ht

extractAsSet :: HT -> IO (Set Int)
extractAsSet ht =
  Set.fromList . fmap fst <$> stToIO (Cuckoo.foldM (fmap pure <$> flip (:)) [] ht)

[erikd]

If I add another test function like this:

secondTest :: Int -> IO ()
secondTest k = do
  ht <- stToIO Cuckoo.new
  let orig = [0..63]
  let intSet = Set.fromList orig
  htSet <- insertCuckoo ht orig
  let diff = Set.difference intSet htSet
  unless (Set.null diff) $ do
    print $ diff
    exitFailure

  let intSet2 = Set.insert k intSet
  htSet2 <- mutateInsertCuckoo ht [k]
  print $ Set.difference intSet2 htSet

and run it as mapM_ secondTest [ 64 .. 100 ] the Set difference is always fromList [48] or
fromList [49].

[infinity0]

@fizbin FWIW we worked around this by switching to Data.HashMap from unordered-containers. @ninegua ran some benchmarks and at least for our use-case this is even faster than hashtables, so we kept it.

I did try to look into fixing this myself but couldn't understand the code quickly enough.

[erikd]

I have some clues.

The Cuckoo.new is implemented as Cockoo. newSizedReal 2 >>= newRef and if I bump that number from 2 to 3 then the tests above pass. However, I strongly suspect that it will then fail when inserting a higher numbered element.

The problem occurs in the cuckooOrFail. If that fails (maxAttempts == 0) then no value is inserted. Now to figure out why this works correctly for insert but not for mutate.

[erikd]

Spent a little more time on this. mutate' calls cuckooOrFail which fails returning Just (k, v) so that mutate' then calls grow which then calls updateOrFail which calls delete' which returns an index at which it would be safe to write the new value.

[erikd]

Haven't had a chance to get back to this. I narrowed the problem down, but got bogged down trying to figure out what was going on. I may not get back to looking at this further. If anyone is interested in pursuing this they should contact me and I can push my debug branch and document the debugging I have done a bit better.

[infinity0]

This is still not fixed. Could someone at least push a hackage update adding some big warnings to the package documentation? It looks like several people have lots hours of debugging over this, myself included, and I'd guess more people that haven't commented. There exists a good fast alternative - Data.HashMap from unordered-containers.

[sjakobi]

There exists a good fast alternative - Data.HashMap from unordered-containers.

FWIW, unordered-containers has its own issues – performance issues, mind you, AFAIK no correctness issues. In my current understanding, default Hashable instances are prone to produce collisions, and HashMaps don't handle these very well. See e.g. haskell-unordered-containers/unordered-containers#121.

[infinity0]

I am not sure about the use-case context of these performance issues you mention. If I remember right, we tested it for an internal company use-case last year, and it was actually faster than this package. Though our use-case was a network-IO-bound program with a few thousand entries max in this map, as opposed to a CPU-bound program using lots of memory.

[sjakobi]

That's good to hear! I think the main concern with using HashMap is that with some Hashable instances, it's easy to produce a lot of collisions which then lead to linear insertion performance. I don't currently have a good understanding which instances are problematic. haskell-unordered-containers/unordered-containers#8 indicates an issue with String for example, but it's also a very old report, so things may have changed in the meantime.

[sjakobi]

Ah, I finally found hashable's "security advisory":

http://hackage.haskell.org/package/hashable-1.3.0.0/docs/Data-Hashable.html#g:1

Apologies for all the noise. I'll stop now! :)

[infinity0]

Ah right. That's a general thing common to all hashtables in any language. The other tickets you linked seemed to be talking about different issues, though?

I never actually thought about this in the context of pure Haskell, but since unordered-containers is pure, to support a protection against this type of attack, the container constructor would have to take in an additional key parameter for seeding the hash function with, which could be generated via IO. For convenience, there could be a default seed in a top-level binding that is generated from runtime entropy via unsafePerformIO, but IMO the API should retain the possibility for the user to pass an explicit seed of their choice. (Should we file a ticket there for this?)

For hashtables the seed can just be generated in ST, the other new* functions are already in ST.

[sjakobi]

@infinity0 I've brought this up in haskell-unordered-containers/unordered-containers#265. You're welcome to chime in! :)

[gregorycollins]

I don't think the mutate function was implemented correctly when the hash table has to grow. I think I can provide a fix.

[erikd]

@gregorycollins Nice! Would you like me to make a release?

[gregorycollins]

I pushed two already (1.2.4.0 to fix the bug and 1.2.4.1 just now to fix some bad deps that got in -- sloppy Greg no cookie)

[fizbin]

I have to say, that fix makes me highly suspicious of everything else that was changed in 196fa53

[gregorycollins]

You're not wrong and clearly we didn't review it carefully enough -- or insist on a high enough test coverage at the time. Should we just take it out of the API until we have time to fix it?