[Chicken-users] Crash in SRFI-69 eq?-hash

[Thomas Chust]

Hello,

while trying to port some code from CHICKEN 4 to CHICKEN 5 I have just
spent several hours tracking down a crash to a call of
hash-table-ref/default for a table which happened to use eq? as the
comparison function and was loaded with various types of objects as
keys.

Then I realized that eq?-hash simply cannot be called on certain types
of objects:

$ chicken-status
[...]
srfi-69 ....................................................... version: 0.2
[...]

$ csi
CHICKEN
(c) 2008-2018, The CHICKEN Team
(c) 2000-2007, Felix L. Winkelmann
Version 5.0.0rc1 (prerelease) (rev 9d480412)
linux-unix-gnu-x86-64 [ 64bit dload ptables ]

#;1> (import srfi-69)
; loading /opt/chicken/lib/chicken/9/srfi-69.import.so ...
; loading /opt/chicken/lib/chicken/9/srfi-69.so ...
#;2> (eq?-hash 2/3)
[panic] out of memory - heap has reached its maximum size - execution terminated

Apart from fractions, complex numbers also seem to trigger the crash
reliably.

Since I don't see any obvious reason why hashing by object identity
should be impossible for certain values, I consider this a serious
bug :-/

Ciao,
Thomas

[Chris Vine]

On Sun, 19 Aug 2018 03:40:26 +0200

Post by Thomas Chust
Hello,
while trying to port some code from CHICKEN 4 to CHICKEN 5 I have just
spent several hours tracking down a crash to a call of
hash-table-ref/default for a table which happened to use eq? as the
comparison function and was loaded with various types of objects as
keys.
Then I realized that eq?-hash simply cannot be called on certain types
$ chicken-status
[...]
srfi-69 ....................................................... version: 0.2
[...]
$ csi
CHICKEN
(c) 2008-2018, The CHICKEN Team
(c) 2000-2007, Felix L. Winkelmann
Version 5.0.0rc1 (prerelease) (rev 9d480412)
linux-unix-gnu-x86-64 [ 64bit dload ptables ]
#;1> (import srfi-69)
; loading /opt/chicken/lib/chicken/9/srfi-69.import.so ...
; loading /opt/chicken/lib/chicken/9/srfi-69.so ...
#;2> (eq?-hash 2/3)
[panic] out of memory - heap has reached its maximum size - execution terminated
Apart from fractions, complex numbers also seem to trigger the crash
reliably.
Since I don't see any obvious reason why hashing by object identity
should be impossible for certain values, I consider this a serious
bug :-/

It probably shouldn't crash, but since '(eq? 2 2)' is allowed to evaluate
to #f, depending on the implementation, does it matter that much? (Maybe
crashing is better than a hash function silently failing to produce a
workable hash.)

[Thomas Chust]

Post by Chris Vine
On Sun, 19 Aug 2018 03:40:26 +0200

Post by Thomas Chust
[...]
Then I realized that eq?-hash simply cannot be called on certain types
[...]
$ csi
CHICKEN
(c) 2008-2018, The CHICKEN Team
(c) 2000-2007, Felix L. Winkelmann
Version 5.0.0rc1 (prerelease) (rev 9d480412)
linux-unix-gnu-x86-64 [ 64bit dload ptables ]
#;1> (import srfi-69)
; loading /opt/chicken/lib/chicken/9/srfi-69.import.so ...
; loading /opt/chicken/lib/chicken/9/srfi-69.so ...
#;2> (eq?-hash 2/3)
[panic] out of memory - heap has reached its maximum size - execution terminated
[...]

It probably shouldn't crash, but since '(eq? 2 2)' is allowed to evaluate
to #f, depending on the implementation, does it matter that much? (Maybe
crashing is better than a hash function silently failing to produce a
workable hash.)
[...]

Hello,

this matters a lot: For one I have an application where it is crucial
to be able to identify if the exact same object is passed more than
once into certain functions and to be able to detect cyclic data
structures – eq? and eq?-hash are supposed to be applicable to
precisely that situation.

Secondly, and maybe even more importantly, the implementation of
eq?-hash in the srfi-69 egg seems to be based on that for eqv?-hash and
equal?-hash in the case of non-immediate data objects:

$ csi -R srfi-69 -p '(eqv?-hash 2/3)'
[panic] out of memory - heap has reached its maximum size - execution
terminated
[...]
$ csi -R srfi-69 -p '(equal?-hash 2+3i)'
[panic] out of memory - heap has reached its maximum size - execution
terminated
[...]

In other words, none of the hash functions offered by the srfi-69 egg
are usable at all!

And lastly, a hash function that goes with a certain equality predicate
should always be applicable to the entire domain of the equality
predicate to be of any practical value.

Ciao,
Thomas

[k***@upyum.com]

Post by Thomas Chust
this matters a lot: For one I have an application where it is crucial
to be able to identify if the exact same object is passed more than
once into certain functions and to be able to detect cyclic data
structures – eq? and eq?-hash are supposed to be applicable to
precisely that situation.

Please calm down, it is indeed a bug and it will be fixed. :)

I checked the code and, for number types, only fixnums and flonums are
explicitely handled, other numeric types trigger an incorrect recursion.

It seems we forgot to add support for the new numeric types to srfi-69
when we introduced them.

[Thomas Chust]

Post by k***@upyum.com
[...]
I checked the code and, for number types, only fixnums and flonums are
explicitely handled, other numeric types trigger an incorrect recursion.
It seems we forgot to add support for the new numeric types to srfi-69
when we introduced them.
[...]

Hello,

thanks for taking the time to look into this!

Your explanation makes a lot of sense, I also suspected the newly added
numeric tower support in core may have broken some low-level
type-specific logic. I just didn't understand enough of the magic
around ##sys#object->uid, for which I couldn't immediately find any
definition in the CHICKEN source, to get a firm grasp of how the
default hash functions in srfi-69 work at all.

For the moment being I have implemented a hackish workaround using

(define %eq?-hash
(foreign-lambda* int ([scheme-object v] [int bound])
"C_return((((intptr_t) v) >> C_FIXNUM_SHIFT) % bound);"))

which is probably terribly incorrect in case the garbage collector
moves objects around, but memory load seems low enough and table
lifetimes short enough in my use case for this to work momentarily %-]

Ciao,
Thomas

[k***@upyum.com]

Hey! :)

This has been fixed in SRFI-69 0.3, hope it works fine for you now!

[Thomas Chust]

Post by k***@upyum.com
[...]
This has been fixed in SRFI-69 0.3, hope it works fine for you now!
[...]

Hello,

thanks a lot, it works like a charm and allowed me to release a new
version of the protocol buffers egg :-)

Ciao,
Thomas