Changeset 2440 in josm

Timestamp:

2009-11-12T19:37:33+01:00 (14 years ago)

Author:

hansendc

Message:

Fixes races reported in trac #3909

This introduces locking to QuadBuckets. This introduces
a QuadBucket-wide lock called 'split_lock'. It protects
a wee bit more than just splits, but splits are its
primary target.

It is used in the iterator to ensure that we do not
encounter temporary dead-ends during tree walks.

File:

• trunk/src/org/openstreetmap/josm/data/osm/QuadBuckets.java (modified) (11 diffs)

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

@@ -18 +18 @@
     public static boolean debug = false;
     static boolean consistency_testing = false;
+    /*
+     * Functions prefixed with __ need locking before
+     * being called.
+     */
+    private Object split_lock = new Object();
 
     static void abort(String s)
@@ -263 +268 @@
             return index;
         }
-        void split()
+        /*
+         * There is a race between this and qb.nextContentNode().
+         * If nextContentNode() runs into this bucket, it may
+         * attempt to null out 'children' because it thinks this
+         * is a dead end.
+         */
+        void __split()
         {
             if (debug) {
@@ -283 +294 @@
                 int new_index = get_index(o, level);
                 if (new_index == -1) {
-                    this.add_content(o);
+                    this.__add_content(o);
                     //out("adding content to branch: " + this);
                     continue;
@@ -297 +308 @@
             }
         }
-        boolean add_content(T o)
+        void split() {
+            synchronized(split_lock) {
+                __split();
+            }
+        }
+        boolean __add_content(T o)
         {
             boolean ret = false;
+            // The split_lock will keep two concurrent
+            // calls from overwriting content
             if (content == null) {
                 content = new ArrayList<T>();
@@ -309 +327 @@
             return ret;
         }
-        void add_to_leaf(T o)
-        {
-            add_content(o);
+        void __add_to_leaf(T o)
+        {
+            __add_content(o);
             if (content.size() > MAX_OBJECTS_PER_LEVEL) {
                 if (debug) {
@@ -447 +465 @@
             return next;
         }
+        QBLevel firstChild()
+        {
+            QBLevel ret = null;
+            for (QBLevel child : this.children) {
+                if (child == null)
+                    continue;
+                ret = child;
+                break;
+            }
+            return ret;
+        }
         QBLevel nextContentNode()
         {
@@ -455 +484 @@
             if (next == null)
                 return null;
-            // Walk back down the tree
-            // and find the first leaf
+            // Walk back down the tree and find the first leaf
             while (!next.isLeaf()) {
+                QBLevel child;
                 if (next.hasContent() && next != this) {
                     break;
                 }
+                child = next.firstChild();
                 if (debug) {
                     out("["+next.level+"] next node ("+next+") is a branch (content: "+next.hasContent()+"), moving down...");
                 }
-                boolean progress = false;
-                for (QBLevel child : next.children) {
-                    if (child == null) {
-                        continue;
-                    }
-                    next = child;
-                    progress = true;
-                    break;
-                }
-                if (!progress) {
-                    // this should out it as not being a branch
-                    next.children = null;
-                    break;
-                }
-            }
-            // This means that there are no leaves or branches
-            // with content as children.  We must continue to
-            // search siblings.
-            if (next == this)
-                return nextSibling().nextContentNode();
+                if (child == null)
+                    abort("branch node had no children");
+                next = child;
+            }
             return next;
         }
@@ -561 +575 @@
                 }
             }
-            if (isLeaf()) {
-                add_to_leaf(n);
-            } else {
-                add_to_branch(n);
+            synchronized (split_lock) {
+                if (isLeaf()) {
+                    __add_to_leaf(n);
+                } else {
+                    __add_to_branch(n);
+                }
             }
             return true;
         }
-        QBLevel add_to_branch(T n)
+        QBLevel __add_to_branch(T n)
         {
             int index = get_index(n, level);
@@ -575 +591 @@
                     out("unable to get index for " + n + "at level: " + level + ", adding content to branch: " + this);
                 }
-                this.add_content(n);
+                this.__add_content(n);
                 return this;
             }
@@ -815 +831 @@
         // bounding box.  Just stash it in the root node.
         if (!n.isUsable()) {
-            ret = root.add_content(n);
+            synchronized (split_lock) {
+                ret = root.__add_content(n);
+            }
         } else {
             ret = root.add(n);
@@ -967 +985 @@
                 return null;
             QBLevel orig = q;
-            QBLevel next = q.nextContentNode();
+            QBLevel next;
+            synchronized (split_lock) {
+                next = q.nextContentNode();
+            }
             //if (consistency_testing && (orig == next))
             if (orig == next) {