lock-free hashtable error

[uchida]

On rare occasions, gethash returns nil dispite the existence of the entry.

toor@toor-VirtualBox:~/src/lisp$ ~/ccl/lx86cl -n
Welcome to Clozure Common Lisp Version 1.8-r15286M  (LinuxX8632)!
? (load "lock-free-hash-table-test.lisp")

#<EXTERNAL-PROCESS (/bin/echo)[9149] (RUNNING) #x1839788E> 
#<EXTERNAL-PROCESS (/bin/echo)[9152] (RUNNING) #x1835FF26> 
#<EXTERNAL-PROCESS (/bin/echo)[9154] (RUNNING) #x1841F11E> 
...
#<EXTERNAL-PROCESS (/bin/echo)[15259] (RUNNING) #x1D41E8E6> 
#<EXTERNAL-PROCESS (/bin/echo)[15261] (RUNNING) #x1D4D0536> 
#<EXTERNAL-PROCESS (/bin/echo)[15264] (RUNNING) #x1D74E746> 
> Error: value NIL is not of the expected type NUMBER.
> While executing: CCL::+-2, in process listener(1).
> Type :POP to abort, :R for a list of available restarts.
> Type :? for other options.
1 > 

[uchida]

Reproducible in dx86cl, dx86cl64, lx86cl and lx86cl64.

[gb]

Also reproducible on ARM, which is a bit surprising.

[uchida]

Another test program. In this, the error is now reproducible on wx86cl.exe(Win XP Pro 32bit.) On Darwin, it typically takes less than 10 seconds to reproduce the error even without the #'clrhash-thread.

[uchida]

(932 . 89)
(932 . 90)
(932 . 91)
(932 . 92)
(932 . 93)
(932 . 94)
> Error: value NIL is not of the expected type NUMBER.
> While executing: CCL::+-2, in process listener(1).
> Type :GO to continue, :POP to abort, :R for a list of available restarts.
> If continued: Skip loading "lock-free-hash-table-test-2.lisp"
> Type :? for other options.
1 > (lisp-implementation-version)
"Version 1.8-r15286M  (WindowsX8632)"
1 >

[uchida]

This is an even shorter version to reproduce a lock-free related error on dx86cl, lx86cl, wx86cl.exe.

(34 . 50)
(34 . 51)
(34 . 52)
(34 . 53)
(34 . 54)
(34 . 55)
> Error: Stack overflow on value stack.
> While executing: CCL::LOCK-FREE-REHASH, in process listener(1).
> Type :GO to continue, :POP to abort, :R for a list of available restarts.
> If continued: Delete one of the entries.
> Type :? for other options.
1 > (lisp-implementation-version)
"Version 1.8-r15286M  (WindowsX8632)"
1 >

[uchida]

I managed to remove the run-program.

[uchida]

All the test cases above run to completion without error by preventing GC in other threads while executing ccl::set-hash-key-conditional, and a small change in ccl::%lock-free-rehash-in-place.

To build, put all the attached files and ccl-1.8-darwinx86.tar.gz on the same directory and,

$ ./build.sh

To run the tests,

$ ./run.sh

[gb]

(In [15444]) Because of pc_luser_xp()'s expectations/constraints, don't modify %temp0 in .SPset_hash_key_conditional. (This is similar to r15433, and doesn't fix ticket:993 either, but may have caused another problem.)

[gb]

The comment in r15444 said that ticket:993 was NOT fixed by that change.

[gb]

(In [15447]) Register usage in x8632 version of .SPstore_node_conditional. (See ticket:993, which has exposed this and similar problems but isn't primarily attributable to them.)

[uchida]

On x8664, it takes typically less than 10 seconds to reproduce the error by increasing the chance of GC between set-hash-key-conditional and set-hash-value-conditional in lock-free-puthash.

uchita-akiko-no-macbook-2:lispbox-0.7 uchidamasako$ ./ccl/dx86cl64 -n
Welcome to Clozure Common Lisp Version 1.8-r15286M  (DarwinX8664)!
? (advise ccl::store-gvector-conditional
	(ccl:process-allow-schedule)
	:when :before)
#<Compiled-function (CCL::ADVISED 'CCL::STORE-GVECTOR-CONDITIONAL) (Non-Global)  #x3020006F657F>
? (load "lock-free-hash-table-test.lisp")

#<EXTERNAL-PROCESS (/bin/echo)[43660] (RUNNING) #x30200072CC6D> 
#<EXTERNAL-PROCESS (/bin/echo)[43661] (RUNNING) #x30200072B3CD> 
#<EXTERNAL-PROCESS (/bin/echo)[43662] (RUNNING) #x3020006B774D> 
#<EXTERNAL-PROCESS (/bin/echo)[43663] (EXITED : 0) #x3020009FF60D> 
#<EXTERNAL-PROCESS (/bin/echo)[43664] (RUNNING) #x302000C1F62D> 
...
#<EXTERNAL-PROCESS (/bin/echo)[43749] (EXITED : 0) #x302004A2090D> 
#<EXTERNAL-PROCESS (/bin/echo)[43750] (RUNNING) #x302004BA090D> 
> Error: value NIL is not of the expected type NUMBER.
> While executing: CCL::+-2, in process listener(1).
> Type :POP to abort, :R for a list of available restarts.
> Type :? for other options.
1 > 

[uchida]

My guess is that between set-hash-key-conditional and set-hash-value-conditional in lock-free-puthash, the partially inserted entry is in DELETED1 state. If GC happens between set-hash-key-conditional and set-hash-value-conditional and remhash or clrhash has set nhash.vector.deleted-count to 1 since the last GC, mark_root (in x86-gc.c) deletes the partially inserted entry.

[uchida]

Trying to encode the partially inserted state by reversing the order of update in hash entry like l0-hash.lisp.2.diff. I'm not sure if I am right.

[uchida]

Here is an even simpler test program to reproduce the error.

[rme]

r15504 in the trunk should fix this.

[uchida]

Thanks! Unfortunately, lock-free-hash-table-test-3.lisp is showing another problem other than this. It seems that l0-hash.lisp.diff attached above seems to reduce the likelihood of this error.

uchita-akiko-no-macbook-2:lispbox-0.7 uchidamasako$ ./ccl-trunk/ccl/dx86cl64 -n
Welcome to Clozure Common Lisp Version 1.9-dev-r15508  (DarwinX8664)!
? (load "lock-free-hash-table-test-3.lisp")

(0 . 0) 
(0 . 1) 
(0 . 2) 
(0 . 3) 
(0 . 4) 
(0 . 5) 
...
(575 . 35) 
(575 . 36) 
(575 . 37) 
(575 . 38) 
(575 . 39) 
(575 . 40) 
(575 . 41) 
> Error: Stack overflow on value stack.
> While executing: CCL::LOCK-FREE-REHASH, in process listener(1).
> Type :GO to continue, :POP to abort, :R for a list of available restarts.
> If continued: Delete one of the entries.
> Type :? for other options.
1 > 

[gz]

See also ticket:717.

[gz]

(In [15525]) In lock-free-puthash handle a new key getting relocated just before it's added to the table. Fix %lock-free-rehash-in-place to set both key and value in a free slot. This fixes ticket:993.