JavaMemoryModel: Tiger beta1 ConcurrentHashMap bug?

From: Doron Rajwan (doron@rajwan.org)
Date: Sun Apr 04 2004 - 05:18:05 EDT


Assume the following:

Thread1:
   Object o = new ...
   map.put("x", o);

Thread2:
   Object value = map.get("x");

As I understand, Thread2 must either get() null, or
there is a happens-before edge between the put() in
Thread1 and the get() in Thread2.

To have such happens-before edge, Thread1 must write
to volatile member 'count' ***before*** updating the
'table' member. However, as you can see below, the
update of (an element of) 'table' is done before the
write to 'count'.Thus, it is possible that Thread2
will obtain a partially initialized object.

Although the map itself is fine, the user objects
passing through it are invalid.

Is this true?

thanks,
  Doron.

        V put(K key, int hash, V value, boolean
onlyIfAbsent) {
            lock();
            try {
                int c = count;
                HashEntry[] tab = table;
                int index = hash & (tab.length - 1);
                HashEntry<K,V> first =
(HashEntry<K,V>) tab[index];

                for (HashEntry<K,V> e = first; e !=
null; e = (HashEntry<K,V>) e.next) {
                    if (e.hash == hash &&
key.equals(e.key)) {
                        V oldValue = e.value;
                        if (!onlyIfAbsent)
                            e.value = value;
                        ++modCount;
                        count = c; // write-volatile
                        return oldValue;
                    }
                }

                tab[index] = new HashEntry<K,V>(hash,
key, value, first);
                ++modCount;
                ++c;
                count = c; // write-volatile
                if (c > threshold)
                    setTable(rehash(tab));
                return null;
            } finally {
                unlock();
            }
        }

        V get(Object key, int hash) {
            if (count != 0) { // read-volatile
                HashEntry[] tab = table;
                int index = hash & (tab.length - 1);
                HashEntry<K,V> e = (HashEntry<K,V>)
tab[index];
                while (e != null) {
                    if (e.hash == hash &&
key.equals(e.key))
                        return e.value;
                    e = e.next;
                }
            }
            return null;
        }

=====
Doron Rajwan, mailto:doron@rajwan.org

-------------------------------
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel



This archive was generated by hypermail 2b29 : Thu Oct 13 2005 - 07:01:02 EDT