From dev-return-38642-apmail-harmony-dev-archive=harmony.apache.org@harmony.apache.org Sat Dec 12 15:53:38 2009 Return-Path: Delivered-To: apmail-harmony-dev-archive@www.apache.org Received: (qmail 58876 invoked from network); 12 Dec 2009 15:53:38 -0000 Received: from hermes.apache.org (HELO mail.apache.org) (140.211.11.3) by minotaur.apache.org with SMTP; 12 Dec 2009 15:53:38 -0000 Received: (qmail 16128 invoked by uid 500); 12 Dec 2009 15:53:38 -0000 Delivered-To: apmail-harmony-dev-archive@harmony.apache.org Received: (qmail 16047 invoked by uid 500); 12 Dec 2009 15:53:38 -0000 Mailing-List: contact dev-help@harmony.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@harmony.apache.org Delivered-To: mailing list dev@harmony.apache.org Received: (qmail 16034 invoked by uid 99); 12 Dec 2009 15:53:38 -0000 Received: from athena.apache.org (HELO athena.apache.org) (140.211.11.136) by apache.org (qpsmtpd/0.29) with ESMTP; Sat, 12 Dec 2009 15:53:38 +0000 X-ASF-Spam-Status: No, hits=-6.1 required=5.0 tests=AWL,BAYES_00,HTML_MESSAGE,RCVD_IN_DNSWL_MED X-Spam-Check-By: apache.org Received-SPF: pass (athena.apache.org: domain of vsm@google.com designates 216.239.33.17 as permitted sender) Received: from [216.239.33.17] (HELO smtp-out.google.com) (216.239.33.17) by apache.org (qpsmtpd/0.29) with ESMTP; Sat, 12 Dec 2009 15:53:35 +0000 Received: from spaceape24.eur.corp.google.com (spaceape24.eur.corp.google.com [172.28.16.76]) by smtp-out.google.com with ESMTP id nBCFrDQm032407 for ; Sat, 12 Dec 2009 15:53:13 GMT DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=google.com; s=beta; t=1260633193; bh=4d8k5YBTja9FbhqR0SXVgq/oQfI=; h=MIME-Version:In-Reply-To:References:Date:Message-ID:Subject:From: To:Content-Type; b=jOgf8dpaOwtS6kpl9hEu7eT9qO8ks3MOdA6kroTrGBDbv9OsHylpPcQvY2S3YUr1Q ZtX2+MrsU98JFFJrOLEHQ== DomainKey-Signature: a=rsa-sha1; s=beta; d=google.com; c=nofws; q=dns; h=mime-version:in-reply-to:references:date:message-id:subject:from:to: content-type:x-system-of-record; b=WueC0t/GSWxP0qlv8y6A/YdzcRhyUGv3P9JRpmOHwOXJtOqW20K/YM3X7jrMHcWBU P2501KRKtxugExXeYyS0g== Received: from pzk41 (pzk41.prod.google.com [10.243.19.169]) by spaceape24.eur.corp.google.com with ESMTP id nBCFrAM4018200 for ; Sat, 12 Dec 2009 07:53:11 -0800 Received: by pzk41 with SMTP id 41so1271452pzk.0 for ; Sat, 12 Dec 2009 07:53:10 -0800 (PST) MIME-Version: 1.0 Received: by 10.141.130.16 with SMTP id h16mr1806141rvn.38.1260633190118; Sat, 12 Dec 2009 07:53:10 -0800 (PST) In-Reply-To: <25aac9fc0912120734n23cc3392k2c46f81674a1d679@mail.gmail.com> References: <981540465.1260477018418.JavaMail.jira@brutus> <4B21BE3A.4030202@gmail.com> <6554f93c0912102009n45e4981btfc072f0c6feacca7@mail.gmail.com> <4B221ABA.4040809@gmail.com> <87638doa25.fsf@gmail.com> <4B226D80.4040309@gmail.com> <3b3f27c60912112000h7c52613ajbbc9692150a3a44e@mail.gmail.com> <25aac9fc0912120734n23cc3392k2c46f81674a1d679@mail.gmail.com> Date: Sat, 12 Dec 2009 07:53:10 -0800 Message-ID: <6554f93c0912120753h784f1c21qd4d14c732faa7425@mail.gmail.com> Subject: Re: [jira] Created: (HARMONY-6404) possible data-reordering in some hashCode-methods (e.g. String or URL) From: Vijay Menon To: dev@harmony.apache.org Content-Type: multipart/alternative; boundary=0003255630527d37d9047a8a0938 X-System-Of-Record: true --0003255630527d37d9047a8a0938 Content-Type: text/plain; charset=ISO-8859-1 On Sat, Dec 12, 2009 at 7:34 AM, sebb wrote: > On 12/12/2009, Nathan Beyer wrote: > > On Fri, Dec 11, 2009 at 10:04 AM, Tim Ellison > wrote: > > > On 11/Dec/2009 14:32, Egor Pasko wrote: > > >> On the 0x684 day of Apache Harmony Tim Ellison wrote: > > >>> On 11/Dec/2009 04:09, Vijay Menon wrote: > > >>>> Perhaps I'm missing some context, but I don't see any problem. I > don't > > >>>> believe that this: > > >>>> > > >>>> if (hashCode == 0) { > > >>>> // calculate hash > > >>>> hashCode = hash; > > >>>> } > > >>>> return hashCode; > > >>>> > > >>>> can ever return 0 (assuming hash is non-zero), regardless of memory > fences. > > >>>> The JMM won't allow visible reordering in a single threaded > program. > > >>> I agree. In the multi-threaded case there can be a data race on the > > >>> hashCode, with the effect that the same hashCode value is > unnecessarily, > > >>> but harmlessly, recalculated. > > >> > > >> Vijay, Tim, you are not 100% correct here. > > >> > > >> 1. there should be an extra restriction that the part "calculate > hash" > > >> does not touch the hashCode field. Without that restriction more > > >> trivial races can happen as discussed in LANG-481. > > >> > > >> So we should assume this code: > > >> > > >> if (this.hashCode == 0) { > > >> int hash; > > >> if (this.hashCode == 0) { > > >> // Calculate using 'hash' only, not this.hashCode. > > >> this.hashCode = hash; > > >> } > > >> return this.hashCode; > > >> } > > > > > > Yes, I guess I figured that was assumed :-) > > > > > > Of course, there are lots of things you could put into the > > > "// Calculate..." section that would be unsafe. We should stick with > > > showing the non-abbreviated implementation to avoid ambiguity: > > > > > > public int hashCode() { > > > if (hashCode == 0) { > > > if (count == 0) { > > > return 0; > > > } > > > int hash = 0; > > > for (int i = offset; i < count + offset; i++) { > > > hash = value[i] + ((hash << 5) - hash); > > > } > > > hashCode = hash; > > > } > > > return hashCode; > > > } > > > > > > > > > I think I understand the concern, after some additional reading. The > > issue seems to be that 'hashCode' is read twice and the field is not > > protected by any memory barriers (synchronized, volatile, etc). As > > such, it would be okay for the second read to be done using a cached > > value, which means that both reads could return 0 in the same thread > > of execution. Another way to look at it is that the write to > > 'hashCode' may or may not affect subsequent reads of 'hashCode'. This > > is how I understand it. > > > > Will that happen in practice? I have no idea. It does seem possible. > > The Java MM guarantees that a single thread behaves as if the code is > processed sequentially. > So if the thread writes non-zero to this.hashCode it cannot then > return zero for the value of this.hashCode if no other threads > intervene. The thread cannot ignore updates to values it has itself > cached! > > If another thread writes to this.hashCode concurrently, then this > thread may or may not see the value stored by that thread. In this > case, it's not a problem, as another thread can only write a fixed > value. So the worst that can happen is that this.hashCode is written > more than once, and the current thread may fetch the value written by > another thread. But this is the same value it wrote anyway. > In a multithreaded setting, this code *can* break and return 0 if hashCode is read twice. This is not just a performance optimization - it is a correctness issue. The compiler / runtime / hardware is allowed to reorder read operations. The following racy execution is allowable under the JMM: 1. Thread 1 reads 0 from hashCode and stores 0 into a local (t1). 2. Thread 2 write 42 into hashCode. 3. Thread 1 reads 42 from hashCode and stores 42 into a local (t2). 4. Thread 1 compares t2 (42) with 0 and does not execute the if clause. 5. Thread 1 returns t1 (0). - Vijay > > > In any case, it does seem a pinch more efficient to only do one read > > of hashCode ... switch up the code to be something like this. > > Agreed. > > > public int hashCode() { > > final int hash = hashCode; > > if (hash == 0) { > > > > if (count == 0) { > > return 0; > > } > > > > for (int i = offset; i < count + offset; i++) { > > hash = value[i] + ((hash << 5) - hash); > > } > > hashCode = hash; > > } > > > > return hash; > > } > > > > Thoughts? > > > > > > >> where 'this.*' is always a memory reference while 'hash' is a thread > private var. > > >> > > >> 2. DRLVM JIT indeed does not privatize field access to threads. It > > >> always loads fields from memory in original order. Hence this > > >> potential bug does not affect DRLVM .. now. But potentially it can > > >> start optimizing things this way because current behavior prevents > > >> a bunch of high level optimizations. > > >> > > >> 3. Jeremy Manson, being an expert in Java Memory Model claims [1] > that > > >> such reordering is allowed theoretically. I.e. like this: > > >> > > >> int hash = this.hashCode; > > >> if (this.hashCode == 0) { > > >> hash = this.hashCode = // calculate hash > > >> } > > >> return hash; > > >> > > >> This is a correct single-threaded code. What happened here is a > > >> lengthy thread privatization of this.hashCode (again, does not happen > > >> in DRLVM). That is incorrect in multithreaded environment and needs > > >> extra synchronization/volatile/etc. > > >> > > >> 4. I do not know why a JIT would want to do that, i.e. two sequential > > >> reads from the same memory location. Sounds like a bit synthetic > example. > > > > > > ...at which point a bunch of code probably would go wrong! So > hopefully > > > it remains only a theoretical possibility. > > > > > > Regards, > > > Tim > > > > > >> [1] > http://jeremymanson.blogspot.com/2008/12/benign-data-races-in-java.html > > >> > > > > > > --0003255630527d37d9047a8a0938--