Bug 572594

Summary: Race condition in B+ tree implementation
Product: [Fedora] Fedora Reporter: Karel Klíč <kklic>
Component: tokyocabinetAssignee: Deji Akingunola <dakingun>
Status: CLOSED ERRATA QA Contact: Fedora Extras Quality Assurance <extras-qa>
Severity: medium Docs Contact:
Priority: low    
Version: 12CC: dakingun, kklic, masahase, mtasaka, rvokal
Target Milestone: ---   
Target Release: ---   
Hardware: All   
OS: Linux   
Whiteboard:
Fixed In Version: tokyocabinet-1.4.33-2.fc12 Doc Type: Bug Fix
Doc Text:
Story Points: ---
Clone Of: Environment:
Last Closed: 2010-03-23 02:08:32 UTC Type: ---
Regression: --- Mount Type: ---
Documentation: --- CRM:
Verified Versions: Category: ---
oVirt Team: --- RHEL 7.3 requirements from Atomic Host:
Cloudforms Team: --- Target Upstream Version:
Embargoed:
Attachments:
Description Flags
Proposed fix
none
Testing program that sometimes fails none

Description Karel Klíč 2010-03-11 16:24:50 UTC 
Created attachment 399381 [details]
Proposed fix

Description of problem:
One of the multi-threading tests in tokyocabinet fails when building on IBM S/390 machine. S390 is not Fedora architecture, but I believe x86 might be affected too (for example just on some machines, or by upgrading the gcc compiler). The upstream acknowledged the bug, and the next Tokyo Cabinet release will contain the fix.

The test that fails:
./tcbmttest typical -rr 1000 casket 5 50000 5 5

The race condition in  the B+ tree implementation. It's caused by the compiler
optimizing out some clever code in tcbdb.c:

uint64_t hlid = bdb->hleaf;
if(hlid < 1 || !(leaf = tcbdbgethistleaf(bdb, kbuf, ksiz, hlid)))...

is transformed into

if (bdb->hleaf < 1 || !(leaf = tcbdbgethistleaf(bdb, kbuf, ksiz,
bdb->hleaf)))...

tcbdbgethistleaf(..., id) is run with id = 0, because bdb->hleaf is changed
to 0 by another thread AFTER checking "bdb->hleaf < 1"

How reproducible:
Sometimes. See https://bugzilla.redhat.com/show_bug.cgi?id=571767 for the testing program.

Affected versions:
The newest released version 1.4.42, and all older versions
Comment 1 Deji Akingunola 2010-03-11 16:45:19 UTC 
(In reply to comment #0)
> Created an attachment (id=399381) [details]
> Proposed fix
> 
...
> 
> The test that fails:
> ./tcbmttest typical -rr 1000 casket 5 50000 5 5
> 
> The race condition in  the B+ tree implementation. It's caused by the compiler
> optimizing out some clever code in tcbdb.c:
> 
Thanks for the report and the attached fix. However, I wonder why this is not reported (to gcc) as a gcc bug?
Comment 2 Karel Klíč 2010-03-11 16:56:10 UTC 
It's a valid optimization, when the variable is not marked as volatile. The compiler assumes that no other thread changes the value, because such a situation is usually prevented by mutexes. Tokyo Cabinet does not use mutex here probably because it would cause large performance hit.
Comment 3 Mamoru TASAKA 2010-03-11 17:00:34 UTC 
(In reply to comment #0)

> How reproducible:
> Sometimes. See https://bugzilla.redhat.com/show_bug.cgi?id=571767 for the
> testing program.

You are not authorized to access bug #571767 :(
Comment 4 Mamoru TASAKA 2010-03-11 17:08:00 UTC 
2010-01-26  Mikio Hirabayashi  <hirarin>
        * tcutil.c (tcmapout): a useless condition was fixed.
        * tchdb.h, tcbdb.h: some members have volatile flag now.
        - Release: 1.4.43
Comment 5 Fedora Update System 2010-03-11 18:57:35 UTC 
tokyocabinet-1.4.33-2.fc12 has been submitted as an update for Fedora 12.
http://admin.fedoraproject.org/updates/tokyocabinet-1.4.33-2.fc12
Comment 6 Fedora Update System 2010-03-11 18:57:39 UTC 
tokyocabinet-1.4.43-1.fc13 has been submitted as an update for Fedora 13.
http://admin.fedoraproject.org/updates/tokyocabinet-1.4.43-1.fc13
Comment 7 Fedora Update System 2010-03-11 18:57:44 UTC 
tokyocabinet-1.4.33-1.fc11 has been submitted as an update for Fedora 11.
http://admin.fedoraproject.org/updates/tokyocabinet-1.4.33-1.fc11
Comment 8 Karel Klíč 2010-03-11 19:02:36 UTC 
Created attachment 399418 [details]
Testing program that sometimes fails
Comment 9 Fedora Update System 2010-03-13 02:23:04 UTC 
tokyocabinet-1.4.33-1.fc11 has been pushed to the Fedora 11 testing repository.  If problems still persist, please make note of it in this bug report.
 If you want to test the update, you can install it with 
 su -c 'yum --enablerepo=updates-testing update tokyocabinet'.  You can provide feedback for this update here: http://admin.fedoraproject.org/updates/tokyocabinet-1.4.33-1.fc11
Comment 10 Fedora Update System 2010-03-13 02:25:14 UTC 
tokyocabinet-1.4.33-2.fc12 has been pushed to the Fedora 12 testing repository.  If problems still persist, please make note of it in this bug report.
 If you want to test the update, you can install it with 
 su -c 'yum --enablerepo=updates-testing update tokyocabinet'.  You can provide feedback for this update here: http://admin.fedoraproject.org/updates/tokyocabinet-1.4.33-2.fc12
Comment 11 Fedora Update System 2010-03-13 02:25:35 UTC 
tokyocabinet-1.4.43-1.fc13 has been pushed to the Fedora 13 testing repository.  If problems still persist, please make note of it in this bug report.
 If you want to test the update, you can install it with 
 su -c 'yum --enablerepo=updates-testing update tokyocabinet'.  You can provide feedback for this update here: http://admin.fedoraproject.org/updates/tokyocabinet-1.4.43-1.fc13
Comment 12 Fedora Update System 2010-03-23 02:08:27 UTC 
tokyocabinet-1.4.33-1.fc11 has been pushed to the Fedora 11 stable repository.  If problems still persist, please make note of it in this bug report.
Comment 13 Fedora Update System 2010-03-23 02:10:36 UTC 
tokyocabinet-1.4.43-1.fc13 has been pushed to the Fedora 13 stable repository.  If problems still persist, please make note of it in this bug report.
Comment 14 Fedora Update System 2010-03-23 02:14:15 UTC 
tokyocabinet-1.4.33-2.fc12 has been pushed to the Fedora 12 stable repository.  If problems still persist, please make note of it in this bug report.