Original bug ID: 1994
Reporter: administrator
Status: closed (set by @xavierleroy on 2006-06-17T09:56:17Z)
Resolution: won't fix
Priority: normal
Severity: minor
Category: ~DO NOT USE (was: OCaml general)

Bug description

Full_Name: Nuutti Kotivuori
Version: 3.07+7 (2003-12-17)
OS: Debian GNU/Linux
Submission from: aka.pp.htv.fi (213.243.183.115)

I stumbled on a rather nasty condition in Hashtbl that will cause a
stack overflow with a bit bigger than normal data amounts.

A snippet that demonstrates this:
,----
| let tbl = Hashtbl.create 10 in
| for i = 0 to 100000 do
| Hashtbl.add tbl 1 "test"
| done;;
`----

The bug is as follows - hash table resizing has a recursive function
called to migrate a single bucket to the new table and it is not tail
recursive.

Here's the bit of code:
,----[ hashtbl.ml ]
| let resize hashfun tbl =
| let odata = tbl.data in
| let osize = Array.length odata in
| let nsize = min (2 * osize + 1) Sys.max_array_length in
| if nsize <> osize then begin
| let ndata = Array.create nsize Empty in
| let rec insert_bucket = function
| Empty -> ()
| | Cons(key, data, rest) ->
| insert_bucket rest; (* preserve original order of elements *)
| let nidx = (hashfun key) mod nsize in
| ndata.(nidx) <- Cons(key, data, ndata.(nidx)) in
| for i = 0 to osize - 1 do
| insert_bucket odata.(i)
| done;
| tbl.data <- ndata;
| end
`----

In here, insert_bucket obviously isn't tail recursive.

So what it means is that if even a rather meager amount of values
happens to get stuffed in the same hash bucket, it will cause a
stack overflow.

I ran into this while using some of the standard bits in OCaml that
internally used a Hashtbl - so this ended up as a real and actual
problem.

-- Naked