Changeset 9267 in josm for trunk/src/org

Timestamp:

2016-01-02T19:15:51+01:00 (9 years ago)

Author:

simon04

Message:

fix #12272 - Fix access to the AbstractPrimitive#keys (patch by michael2402)

Location:

trunk/src/org/openstreetmap/josm/data/osm

Files:

• AbstractPrimitive.java (modified) (8 diffs)
• OsmPrimitive.java (modified) (4 diffs)

trunk/src/org/openstreetmap/josm/data/osm/AbstractPrimitive.java

@@ -482 +482 @@
      ------------*/
 
-    // Note that all methods that read keys first make local copy of keys array reference. This is to ensure thread safety - reading
-    // doesn't have to be locked so it's possible that keys array will be modified. But all write methods make copy of keys array so
-    // the array itself will be never modified - only reference will be changed
-
     /**
      * The key/value list for this primitive.
-     */
-    protected String[] keys;
+     * <p>
+     * Note that the keys field is synchronized using RCU.
+     * Writes to it are not synchronized by this object, the writers have to synchronize writes themselves.
+     * <p>
+     * In short this means that you should not rely on this variable being the same value when read again and your should always
+     * copy it on writes.
+     * <p>
+     * Further reading:
+     * <ul>
+     * <li>{@link java.util.concurrent.CopyOnWriteArrayList}</li>
+     * <li> <a href="http://stackoverflow.com/questions/2950871/how-can-copyonwritearraylist-be-thread-safe">
+     *     http://stackoverflow.com/questions/2950871/how-can-copyonwritearraylist-be-thread-safe</a></li>
+     * <li> <a href="https://en.wikipedia.org/wiki/Read-copy-update">
+     *     https://en.wikipedia.org/wiki/Read-copy-update</a> (mind that we have a Garbage collector,
+     *     {@code rcu_assign_pointer} and {@code rcu_dereference} are ensured by the {@code volatile} keyword)</li>
+     * </ul>
+     */
+    protected volatile String[] keys;
 
     /**
@@ -531 +543 @@
      * Old key/value pairs are removed.
      * If <code>keys</code> is null, clears existing key/value pairs.
+     * <p>
+     * Note that this method, like all methods that modify keys, is not synchronized and may lead to data corruption when being used
+     * from multiple threads.
      *
      * @param keys the key/value pairs to set. If null, removes all existing key/value pairs.
@@ -555 +570 @@
      * Set the given value to the given key. If key is null, does nothing. If value is null,
      * removes the key and behaves like {@link #remove(String)}.
+     * <p>
+     * Note that this method, like all methods that modify keys, is not synchronized and may lead to data corruption when being used
+     * from multiple threads.
      *
      * @param key  The key, for which the value is to be set. Can be null or empty, does nothing in this case.
@@ -572 +590 @@
             keysChangedImpl(originalKeys);
         } else {
-            for (int i = 0; i < keys.length; i += 2) {
-                if (keys[i].equals(key)) {
-                    // This modifies the keys array but it doesn't make it invalidate for any time so its ok (see note no top)
-                    keys[i+1] = value;
-                    keysChangedImpl(originalKeys);
-                    return;
-                }
+            int keyIndex = indexOfKey(keys, key);
+            int tagArrayLength = keys.length;
+            if (keyIndex < 0) {
+                keyIndex = tagArrayLength;
+                tagArrayLength += 2;
             }
-            String[] newKeys = Arrays.copyOf(keys, keys.length + 2);
-            newKeys[keys.length] = key;
-            newKeys[keys.length + 1] = value;
+
+            // Do not try to optimize this array creation if the key already exists.
+            // We would need to convert the keys array to be an AtomicReferenceArray
+            // Or we would at least need a volatile write after the array was modified to
+            // ensure that changes are visible by other threads.
+            String[] newKeys = Arrays.copyOf(keys, tagArrayLength);
+            newKeys[keyIndex] = key;
+            newKeys[keyIndex + 1] = value;
             keys = newKeys;
             keysChangedImpl(originalKeys);
@@ -589 +610 @@
 
     /**
+     * Scans a key/value array for a given key.
+     * @param keys The key array. It is not modified. It may be null to indicate an emtpy array.
+     * @param key The key to search for.
+     * @return The position of that key in the keys array - which is always a multiple of 2 - or -1 if it was not found.
+     */
+    private static int indexOfKey(String[] keys, String key) {
+        if (keys == null) {
+            return -1;
+        }
+        for (int i = 0; i < keys.length; i += 2) {
+            if (keys[i].equals(key)) {
+                return i;
+            }
+        }
+        return -1;
+    }
+
+    /**
      * Remove the given key from the list
+     * <p>
+     * Note that this method, like all methods that modify keys, is not synchronized and may lead to data corruption when being used
+     * from multiple threads.
      *
      * @param key  the key to be removed. Ignored, if key is null.
@@ -618 +660 @@
     /**
      * Removes all keys from this primitive.
+     * <p>
+     * Note that this method, like all methods that modify keys, is not synchronized and may lead to data corruption when being used
+     * from multiple threads.
      */
     @Override
@@ -681 +726 @@
 
     public final int getNumKeys() {
+        String[] keys = this.keys;
         return keys == null ? 0 : keys.length / 2;
     }
@@ -719 +765 @@
      */
     public boolean hasKey(String key) {
-        String[] keys = this.keys;
-        if (key == null) return false;
-        if (keys == null) return false;
-        for (int i = 0; i < keys.length; i += 2) {
-            if (keys[i].equals(key)) return true;
-        }
-        return false;
+        return key != null && indexOfKey(keys, key) >= 0;
     }
 

trunk/src/org/openstreetmap/josm/data/osm/OsmPrimitive.java

@@ -776 +776 @@
     /**
      * Returns {@link #getKeys()} for which {@code key} does not fulfill {@link #isUninterestingKey}.
-     * @return list of interesting tags
+     * @return A map of interesting tags
      */
     public Map<String, String> getInterestingTags() {
@@ -833 +833 @@
 
     private void updateTagged() {
-        if (keys != null) {
-            for (String key: keySet()) {
-                // 'area' is not really uninteresting (putting it in that list may have unpredictable side effects)
-                // but it's clearly not enough to consider an object as tagged (see #9261)
-                if (!isUninterestingKey(key) && !"area".equals(key)) {
-                    updateFlagsNoLock(FLAG_TAGGED, true);
-                    return;
-                }
+        for (String key: keySet()) {
+            // 'area' is not really uninteresting (putting it in that list may have unpredictable side effects)
+            // but it's clearly not enough to consider an object as tagged (see #9261)
+            if (!isUninterestingKey(key) && !"area".equals(key)) {
+                updateFlagsNoLock(FLAG_TAGGED, true);
+                return;
             }
         }
@@ -847 +845 @@
 
     private void updateAnnotated() {
-        if (keys != null) {
-            for (String key: keySet()) {
-                if (getWorkInProgressKeys().contains(key)) {
-                    updateFlagsNoLock(FLAG_ANNOTATED, true);
-                    return;
-                }
+        for (String key: keySet()) {
+            if (getWorkInProgressKeys().contains(key)) {
+                updateFlagsNoLock(FLAG_ANNOTATED, true);
+                return;
             }
         }
@@ -1188 +1184 @@
      */
     public boolean hasSameInterestingTags(OsmPrimitive other) {
-        // We cannot directly use Arrays.equals(keys, other.keys) as keys is not ordered by key
-        // but we can at least check if both arrays are null or of the same size before creating
-        // and comparing the key maps (costly operation, see #7159)
         return (keys == null && other.keys == null)
-                || (keys != null && other.keys != null && keys.length == other.keys.length
-                        && (keys.length == 0 || getInterestingTags().equals(other.getInterestingTags())));
+                || getInterestingTags().equals(other.getInterestingTags());
     }