Changeset 18903 in josm for trunk/src


Ignore:
Timestamp:
2023-11-22T15:38:23+01:00 (12 months ago)
Author:
taylor.smock
Message:

Fix #23309: NPE in GeoPropertyIndex$GPLevel.getBounded when called by Territories.getRegionalTaginfoUrls

Territories.getRegionalTaginfoUrls uses Collection.parallelStream
which could cause the following race conditions:

  • children is reinitialized after the null check, potentially causing an NPE due to a different null check becoming false after it was checked. Solution: either synchronize the creation of children or have a local variable.
  • Two threads could generate a child and then generate children of children, creating a split tree hierarchy, only one of which would be kept. Solution: synchronize the creation of the child nodes

For both of the new synchronized methods, we could use a safe double-lock
idiom if there ends up being performance issues. This probably won't be the case.
Profiling JOSM start to end with Mesa County, CO (+ validations) did not show
that the modified methods were "hot".

This additionally fixes some lint issues and converts some package-private
methods to use ILatLon instead of LatLon.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/org/openstreetmap/josm/tools/GeoPropertyIndex.java

    r17465 r18903  
    22package org.openstreetmap.josm.tools;
    33
     4import java.util.Collection;
     5
     6import org.openstreetmap.josm.data.coor.ILatLon;
    47import org.openstreetmap.josm.data.coor.LatLon;
    58import org.openstreetmap.josm.data.osm.BBox;
    … …  
    710/**
    811 * Fast index to look up properties of the earth surface.
    9  *
     12 * <p>
    1013 * It is expected that there is a relatively slow method to look up the property
    1114 * for a certain coordinate and that there are larger areas with a uniform
    1215 * property.
    13  *
     16 * <p>
    1417 * This index tries to find rectangles with uniform property and caches them.
    1518 * Rectangles are subdivided, if there are different properties within.
    … …  
    8083            if (isInside(ll))
    8184                return getBounded(ll);
    82             if (DEBUG) System.err.print("up["+level+"]");
     85            if (DEBUG) Logging.trace("up[{0}]", level);
    8386            return parent != null ? parent.get(ll) : null;
    8487        }
    8588
    8689        private T getBounded(LatLon ll) {
    87             if (DEBUG) System.err.print("GPLevel["+level+"]"+bbox+" ");
     90            if (DEBUG) Logging.trace("GPLevel[{0}]{1}", level, bbox);
    8891            if (!isInside(ll)) {
    8992                throw new AssertionError("Point "+ll+" should be inside "+bbox);
    9093            }
    9194            if (val != null) {
    92                 if (DEBUG) System.err.println(" hit! "+val);
     95                if (DEBUG) Logging.trace("GPLevel[{0}]{1} hit! {2}", level, bbox, val);
    9396                owner.lastLevelUsed = this;
    9497                return val;
    9598            }
    9699            if (level >= owner.maxLevel) {
    97                 if (DEBUG) System.err.println(" max level reached !");
     100                if (DEBUG) Logging.trace("GPLevel[{0}]{1} max level reached !", level, bbox);
    98101                return owner.geoProp.get(ll);
    99102            }
    100103
    101             if (children == null) {
    102                 @SuppressWarnings("unchecked")
    103                 GPLevel<T>[] tmp = new GPLevel[4];
    104                 this.children = tmp;
    105             }
     104            GPLevel<T>[] currentChildren = this.getChildren();
    106105
    107106            LatLon center = bbox.getCenter();
    108107            for (int idx = 0; idx < 4; idx++) {
    109108                BBox testBBox = null;
    110                 if (children[idx] != null)
    111                     testBBox = children[idx].bbox;
     109                if (currentChildren[idx] != null)
     110                    testBBox = currentChildren[idx].bbox;
    112111
    113112                if (testBBox == null) {
    114                     double lon1, lat1;
    115                     switch (idx) {
    116                         case 0:
    117                             lon1 = bbox.getTopLeftLon();
    118                             lat1 = bbox.getBottomRightLat();
    119                             break;
    120                         case 1:
    121                             lon1 = bbox.getTopLeftLon();
    122                             lat1 = bbox.getTopLeftLat();
    123                             break;
    124                         case 2:
    125                             lon1 = bbox.getBottomRightLon();
    126                             lat1 = bbox.getBottomRightLat();
    127                             break;
    128                         case 3:
    129                             lon1 = bbox.getBottomRightLon();
    130                             lat1 = bbox.getTopLeftLat();
    131                             break;
    132                         default:
    133                             throw new AssertionError();
    134                     }
    135                     testBBox = new BBox(lon1, lat1, center.lon(), center.lat());
     113                    testBBox = generateTestBBox(idx, center.lon(), center.lat());
    136114                }
    137115                if (isInside(testBBox, ll)) {
    138                     if (children[idx] == null) {
    139                         if (DEBUG) System.err.println(" - new with idx "+idx);
    140                         children[idx] = new GPLevel<>(level + 1, testBBox, this, owner);
    141                     }
    142                     return children[idx].getBounded(ll);
     116                    generateChild(currentChildren, testBBox, idx);
     117                    return currentChildren[idx].getBounded(ll);
    143118                }
    144119            }
    145120            throw new AssertionError("Point "+ll+" should be inside one of the children of "+bbox);
     121        }
     122
     123        /**
     124         * Generate the bbox for the specified index in the {@link #getChildren()} array
     125         * @param idx The index in the {@link #getChildren()} array
     126         * @param lon2 The longitude of the center of the previous level
     127         * @param lat2 The latitude of the center of the previous level
     128         * @return The test bbox for the specified index in the {@link #getChildren()} array
     129         */
     130        private BBox generateTestBBox(int idx, double lon2, double lat2) {
     131            double lon1;
     132            double lat1;
     133            switch (idx) {
     134                case 0:
     135                    lon1 = bbox.getTopLeftLon();
     136                    lat1 = bbox.getBottomRightLat();
     137                    break;
     138                case 1:
     139                    lon1 = bbox.getTopLeftLon();
     140                    lat1 = bbox.getTopLeftLat();
     141                    break;
     142                case 2:
     143                    lon1 = bbox.getBottomRightLon();
     144                    lat1 = bbox.getBottomRightLat();
     145                    break;
     146                case 3:
     147                    lon1 = bbox.getBottomRightLon();
     148                    lat1 = bbox.getTopLeftLat();
     149                    break;
     150                default:
     151                    throw new AssertionError();
     152            }
     153            return new BBox(lon1, lat1, lon2, lat2);
     154        }
     155
     156        /**
     157         * Safely generate the child in a multi-threaded environment
     158         * @param currentChildren The children array to check
     159         * @param testBBox The current bbox (will be used to create the new {@link GPLevel})
     160         * @param idx The index in the child array
     161         */
     162        private synchronized void generateChild(GPLevel<T>[] currentChildren, BBox testBBox, int idx) {
     163            if (currentChildren[idx] == null) {
     164                if (DEBUG) Logging.trace("GPLevel[{0}]{1} - new with idx {2}", level, bbox, idx);
     165                currentChildren[idx] = new GPLevel<>(level + 1, testBBox, this, owner);
     166            }
     167        }
     168
     169        /**
     170         * Get the children array safely in a multi-threaded environment.
     171         * If this ends up being a performance issue, look up the "immutable" double-checked locking idiom.
     172         * Just be certain you have a good test when checking the performance differences.
     173         * See #23309/#23036. The issue there is that {@link Territories#getRegionalTaginfoUrls(LatLon)}
     174         * uses a {@link Collection#parallelStream}.
     175         * @return The children array (sw, nw, se, ne)
     176         */
     177        private synchronized GPLevel<T>[] getChildren() {
     178            GPLevel<T>[] currentChildren = this.children;
     179            if (currentChildren == null) {
     180                @SuppressWarnings("unchecked")
     181                GPLevel<T>[] tmp = new GPLevel[4];
     182                currentChildren = tmp;
     183                this.children = currentChildren;
     184            }
     185            return currentChildren;
    146186        }
    147187
    … …  
    153193         * @return true, if it is inside of the box
    154194         */
    155         boolean isInside(LatLon ll) {
     195        boolean isInside(ILatLon ll) {
    156196            return isInside(bbox, ll);
    157197        }
    … …  
    165205         * @return true, if it is inside of the box
    166206         */
    167         boolean isInside(BBox bbox, LatLon ll) {
     207        boolean isInside(BBox bbox, ILatLon ll) {
    168208            return bbox.getTopLeftLon() <= ll.lon() &&
    169209                    (ll.lon() < bbox.getBottomRightLon() || (ll.lon() == 180.0 && bbox.getBottomRightLon() == 180.0)) &&
Note: See TracChangeset for help on using the changeset viewer.