On May 11, 2012, at 8:00 PM, Adam Heath wrote:
> On 05/11/2012 12:30 PM, Jacopo Cappellato wrote:
>>
>> On May 11, 2012, at 6:34 PM, Adam Heath wrote:
>>
>>> There is no difference. The act of map.get() can be doing a *lot* of
>>> separate, individual steps. Without any kind of
>>> happens-before/happens-after on map.get(), the protected put/get in
>>> the lock could interleave with the unprotected get.
>>
>> Ok, if you don't want to admit that there is no DCL in my code I will give
>> up; what you describe next is a clearly totally different topic.
>
> I won't admit that, because there IS a DCL in the code you added in
> the original commit.
>
> if (!initialized) {
> lock {
> if (!initialized) {
> initialize();
> }
> }
> }
>
This is not what I implemented; I already explained it in my other emails,
please read them carefully.I have to go now but if you can't find the answers
from my others email let me know and I will add details during the week end
(now I have to go).
> That is DCL to. It doesn't matter if initialized is a simple read of
> a variable, a null check, or something more complex(map.get). They
> are all the same *pattern*.
>
> What is at issue, is that the code running before the lock can be
> interleaved with the code run inside the lock. This is because the
> code outside the lock has no barrier, no guard, no kind of
> happens-relationship at all with the code inside the lock. All the
> lock helps protect is 2 threads trying to run the internal block. But
> that external block can run at any time.
There is no need to explain to me why DCL is bad.
>
>> But even if a totally different topic I think it is an interesting one
>> because the UtilCache get/put/putIfAbsent methods are used a lot and if they
>> are not thread safe this would be a problem. A problem for my code, your
>> code and a lot of code in OFBiz.
>
> The UtilCache objects *are* thread-safe. You will not get any
> internal corruption inside UtilCache. That is all that can be guaranteed.
>
> What isn't thread safe, is that calling code may end up having
> multiple instances for the same key, unless calling code is written
> correctly.
And so if these methods are thread safe all your comments below don't apply to
the code I wrote:
>> Saying again. 2 threads could be running. One wants "foo", the other
>> wants "bar". The first sees no value for "foo", starts generating the
>> result, then calls map.put("foo", result). When map.put is running,
>> it's doing a lot of separate, individual steps.
>>
>> Now, the second thread comes around, and calls map.get("bar"). The
>> first thread is still running inside the put. The second thread is
>> not in the synchronized block, so it went straight into map.get. And
>> now you have 2 threads both running code inside that map that has no
>> happens-before/happens-after guarantees, so now things blow up.
>
> The changes I did to remove synchronized from most places in UtilCache
> were correct, it reduced contention. Each method on UtilCache still
> has correct happens-before/happens-since, both before and after
> removing synchronized.
>
And in fact I greatly appreciate the work you did at that time.
> Any such issues in calling code were always there previously; it's
> just that because of synchronized, it slowed down threads enough so
> that you wouldn't see bad code as often. Remove the contention,
> things happen quicker, and so do any bugs.
>
> Why do you think java 1.1 introduced HashMap, to replace Hashtable?
> Hashtable used to have synchronized on get/put, but in reality, that
> did *nothing* to protect calling code that had *separate* calls to
> get/put/containsKey/whatever. It is the *external* code that needed
> the lock, not the Hashtable.
>
> Also, an unprotected map.entrySet().iterator() can have corruption if
> other threads are mutating the structure of the map. In those case,
> external synchronization needs to happen between the iteration, *and*
> the get/put/remove. If you read the ConcurrentMap(and friends) code,
> you'll find references to the iterators failing
> fast(ConcurrentModificationException), or not failing at all(you'll
> get a read-only snapshot of something that may not reflect the current
> values of the Collection).
Yeah, I know all of these things: "Java Concurrency In Practice" is actually
quite enlightening on these topics.
Regards,
Jacopo
>
>> I didn't look too closely at the implementation of the two methods but it
>> seems that they are actually handling the shared status in a thread safe way
>> (even if they are not atomic), so I do not see a risk for reading objects in
>> a stale/invalid status; but you actually did, if I am not wrong, the
>> implementation of these method and you may know better than I.
>
> I have seen a map.get/null-check/put DCL as given in your code cause
> threads to enter into never-ending loops, as they call .toString(),
> which calls .iterator(), which, because of unprotected manipulation,
> the hash-bucket links internal to the map become circular.
>
> The first time(it's happened multiple times), I had no clue. But
> then, I added a -XX parameter to allow me to attach to the java
> process. The next time, I dumped the entire memory(that was huge, as
> these bugs happen more often during OOM). I then used IBM's
> HeapAnaylzer(nice little swing app to memory dumps, better than jhat)
> to see that the hashbucket links were circular.
>
>> By the way, all the issues that you are mentioning are actually all present
>> in the fix that you suggested at the beginning of this thread:
>>
>> Class scriptClass = parsedScripts.get(script);
>> if (scriptClass == null) {
>> scriptClass = genClass();
>> parsedScripts.putIfAbsent(script, scriptClass);
>> scriptClass = parsedScripts.get(script);
>> }
>
> parsedScripts is a UtilCache; the methods on that object have
> happens-before/happens-after guarantees, due to internally using
> ConcurrentMap. Deep inside ConcurrentMap, you'll find variables
> marked volatile, and/or work-stealing/work-completing patterns, that
> also again have happens-before/happens-after.
>
> The only issue in the above code, as I have already mentioned, is that
> some other background thread may call remove(script) inbetween
> putIfAbsent() and the following get(). And the solution for that is
> to change the if to a while.
>
>> while my initial code was safer (because it was wrapping get and put calls
>> into synchronized blocks). But if the UtilCache method put/get/putIfAbsent
>> are not thread safe, now it makes me nervous to call them within
>> synchronized blocks because in them there are also synchronized blocks (risk
>> for deadlocks). The best way to fix this would be to make the methods thread
>> safe (if they are not already as it seems they are).
>
> Nope, your code still had the same removal problem.
>
>>> Yet another thread might explicitly *remove* the key between the
>>> putIfAsent and following get; so the above really needs to be done in
>>> a loop. With UtilCache, an item may be removed *at any time* when
>>> soft-references are used, or when a TTL expires. Even in such a short
>>> timeframe as the 2 lines above. Just because those 2 lines are right
>>> next to each other, doesn't mean that the process execution context
>>> will stay running this particular thread.
>>
>> This is a good point and probably the only real issue of your initial code
>> (and in the latest version of my code, the one without synchronized blocks);
>> I would suggest the following fix:
>>
>> Class scriptClass = parsedScripts.get(script);
>> if (scriptClass == null) {
>> scriptClass = genClass();
>> Class cachedScriptClass = null;
>> do {
>> parsedScripts.putIfAbsent(script, scriptClass);
>> cachedScriptClass = parsedScripts.get(script);
>> } while(cachedScriptClass != null);
>> scriptClass = cachedScriptClass;
>> }
>>
>> But of course here I am assuming that UtilCache put/get/putIfAbsent are
>> thread safe.
>
> They are, just without doing synchronized.
>
>> What do you think?
>>
>> Jacopo
>>
>
