Author: asanso
Date: Mon Dec 22 12:39:40 2014
New Revision: 1647303
URL: http://svn.apache.org/r1647303
Log:
SLING-4216 - Limit the number of vanityPath MapEntry
Added:
sling/trunk/bundles/resourceresolver/src/main/java/org/apache/sling/resourceresolver/impl/mapping/BloomFilterUtils.java
sling/trunk/bundles/resourceresolver/src/test/java/org/apache/sling/resourceresolver/impl/mapping/BloomFilterUtilsTest.java
Modified:
sling/trunk/bundles/resourceresolver/src/main/java/org/apache/sling/resourceresolver/impl/CommonResourceResolverFactoryImpl.java
sling/trunk/bundles/resourceresolver/src/main/java/org/apache/sling/resourceresolver/impl/ResourceResolverFactoryActivator.java
sling/trunk/bundles/resourceresolver/src/main/java/org/apache/sling/resourceresolver/impl/mapping/MapConfigurationProvider.java
sling/trunk/bundles/resourceresolver/src/main/java/org/apache/sling/resourceresolver/impl/mapping/MapEntries.java
sling/trunk/bundles/resourceresolver/src/test/java/org/apache/sling/resourceresolver/impl/mapping/MapEntriesTest.java
Modified:
sling/trunk/bundles/resourceresolver/src/main/java/org/apache/sling/resourceresolver/impl/CommonResourceResolverFactoryImpl.java
URL:
http://svn.apache.org/viewvc/sling/trunk/bundles/resourceresolver/src/main/java/org/apache/sling/resourceresolver/impl/CommonResourceResolverFactoryImpl.java?rev=1647303&r1=1647302&r2=1647303&view=diff
==============================================================================
---
sling/trunk/bundles/resourceresolver/src/main/java/org/apache/sling/resourceresolver/impl/CommonResourceResolverFactoryImpl.java
(original)
+++
sling/trunk/bundles/resourceresolver/src/main/java/org/apache/sling/resourceresolver/impl/CommonResourceResolverFactoryImpl.java
Mon Dec 22 12:39:40 2014
@@ -241,6 +241,14 @@ public class CommonResourceResolverFacto
public boolean isVanityPathEnabled() {
return this.activator.isVanityPathEnabled();
}
+
+ public long getMaxCachedVanityPathEntries() {
+ return this.activator.getMaxCachedVanityPathEntries();
+ }
+
+ public int getVanityBloomFilterMaxBytes() {
+ return this.activator.getVanityBloomFilterMaxBytes();
+ }
public boolean isOptimizeAliasResolutionEnabled() {
return this.activator.isOptimizeAliasResolutionEnabled();
Modified:
sling/trunk/bundles/resourceresolver/src/main/java/org/apache/sling/resourceresolver/impl/ResourceResolverFactoryActivator.java
URL:
http://svn.apache.org/viewvc/sling/trunk/bundles/resourceresolver/src/main/java/org/apache/sling/resourceresolver/impl/ResourceResolverFactoryActivator.java?rev=1647303&r1=1647302&r2=1647303&view=diff
==============================================================================
---
sling/trunk/bundles/resourceresolver/src/main/java/org/apache/sling/resourceresolver/impl/ResourceResolverFactoryActivator.java
(original)
+++
sling/trunk/bundles/resourceresolver/src/main/java/org/apache/sling/resourceresolver/impl/ResourceResolverFactoryActivator.java
Mon Dec 22 12:39:40 2014
@@ -184,7 +184,21 @@ public class ResourceResolverFactoryActi
description = "This flag controls whether all resources with a
sling:vanityPath property " +
"are processed and added to the mappoing table.")
private static final String PROP_ENABLE_VANITY_PATH =
"resource.resolver.enable.vanitypath";
-
+
+ private static final long DEFAULT_MAX_CACHED_VANITY_PATHS = -1;
+ @Property(longValue = DEFAULT_MAX_CACHED_VANITY_PATHS,
+ label = "Maximum number of cached vanity path entries",
+ description = "The maximum number of cached vanity path entries.
" +
+ "Default is -1 (no limit)")
+ private static final String PROP_MAX_CACHED_VANITY_PATHS =
"resource.resolver.max.vanityPath.entries";
+
+ private static final int DEFAULT_VANITY_BLOOM_FILTER_MAX_BYTES = 1024000;
+ @Property(longValue = DEFAULT_VANITY_BLOOM_FILTER_MAX_BYTES,
+ label = "Maximum number of vanity bloom filter bytes",
+ description = "The maximum number of vanity bloom filter bytes.
" +
+ "Changing this value is subject to vanity bloom
filter rebuild")
+ private static final String PROP_VANITY_BLOOM_FILTER_MAX_BYTES =
"resource.resolver.vanity.bloom.filter.max.bytes";
+
private static final boolean DEFAULT_ENABLE_OPTIMIZE_ALIAS_RESOLUTION =
true;
@Property(boolValue = DEFAULT_ENABLE_OPTIMIZE_ALIAS_RESOLUTION ,
label = "Optimize alias resolution",
@@ -260,6 +274,12 @@ public class ResourceResolverFactoryActi
/** alias resource resolution optimization enabled? */
private boolean enableOptimizeAliasResolution =
DEFAULT_ENABLE_OPTIMIZE_ALIAS_RESOLUTION;
+ /** max number of cache vanity path entries */
+ private long maxCachedVanityPathEntries = DEFAULT_MAX_CACHED_VANITY_PATHS;
+
+ /** Maximum number of vanity bloom filter bytes */
+ private int vanityBloomFilterMaxBytes =
DEFAULT_VANITY_BLOOM_FILTER_MAX_BYTES;
+
/** vanity paths will have precedence over existing /etc/map mapping? */
private boolean vanityPathPrecedence = DEFAULT_VANITY_PATH_PRECEDENCE;
@@ -347,6 +367,14 @@ public class ResourceResolverFactoryActi
public boolean hasVanityPathPrecedence() {
return this.vanityPathPrecedence;
}
+
+ public long getMaxCachedVanityPathEntries() {
+ return this.maxCachedVanityPathEntries;
+ }
+
+ public int getVanityBloomFilterMaxBytes() {
+ return this.vanityBloomFilterMaxBytes;
+ }
// ---------- SCR Integration ---------------------------------------------
@@ -449,7 +477,9 @@ public class ResourceResolverFactoryActi
}
this.enableOptimizeAliasResolution =
PropertiesUtil.toBoolean(properties.get(PROP_ENABLE_OPTIMIZE_ALIAS_RESOLUTION),
DEFAULT_ENABLE_OPTIMIZE_ALIAS_RESOLUTION);
-
+ this.maxCachedVanityPathEntries =
PropertiesUtil.toLong(properties.get(PROP_MAX_CACHED_VANITY_PATHS),
DEFAULT_MAX_CACHED_VANITY_PATHS);
+ this.vanityBloomFilterMaxBytes =
PropertiesUtil.toInteger(properties.get(PROP_VANITY_BLOOM_FILTER_MAX_BYTES),
DEFAULT_VANITY_BLOOM_FILTER_MAX_BYTES);
+
this.vanityPathPrecedence =
PropertiesUtil.toBoolean(properties.get(PROP_VANITY_PATH_PRECEDENCE),
DEFAULT_VANITY_PATH_PRECEDENCE);
final BundleContext bc = componentContext.getBundleContext();
Added:
sling/trunk/bundles/resourceresolver/src/main/java/org/apache/sling/resourceresolver/impl/mapping/BloomFilterUtils.java
URL:
http://svn.apache.org/viewvc/sling/trunk/bundles/resourceresolver/src/main/java/org/apache/sling/resourceresolver/impl/mapping/BloomFilterUtils.java?rev=1647303&view=auto
==============================================================================
---
sling/trunk/bundles/resourceresolver/src/main/java/org/apache/sling/resourceresolver/impl/mapping/BloomFilterUtils.java
(added)
+++
sling/trunk/bundles/resourceresolver/src/main/java/org/apache/sling/resourceresolver/impl/mapping/BloomFilterUtils.java
Mon Dec 22 12:39:40 2014
@@ -0,0 +1,115 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.sling.resourceresolver.impl.mapping;
+
+/**
+ * Bloom filter utilities.
+ */
+public class BloomFilterUtils {
+
+ /**
+ * The multiply and shift constants for the supplemental hash function.
+ */
+ private static final int MUL = 2153, SHIFT = 19;
+
+ /**
+ * The number of bits needed per stored element.
+ * Using the formula m = - (n * ln(p)) / (ln(2)^2) as described in
+ * http://en.wikipedia.org/wiki/Bloom_filter
+ * (simplified, as we used a fixed K: 2).
+ */
+ private static final double BIT_FACTOR = -Math.log(0.02) /
Math.pow(Math.log(2), 2);
+
+ /**
+ * Create a bloom filter array for the given number of elements.
+ *
+ * @param elementCount the number of entries
+ * @param maxBytes the maximum number of bytes
+ * @return the empty bloom filter
+ */
+ public static byte[] createFilter(int elementCount, int maxBytes) {
+ int bits = (int) (elementCount * BIT_FACTOR) + 7;
+ return new byte[Math.min(maxBytes, bits / 8)];
+ }
+
+ /**
+ * Add the key.
+ *
+ * @param bloom the bloom filter
+ * @param key the key
+ */
+ public static void add(byte[] bloom, Object key) {
+ int len = bloom.length;
+ if (len > 0) {
+ int h1 = hash(key.hashCode()), h2 = hash(h1);
+ bloom[(h1 >>> 3) % len] |= 1 << (h1 & 7);
+ bloom[(h2 >>> 3) % len] |= 1 << (h2 & 7);
+ }
+ }
+
+ /**
+ * Remove the key.
+ *
+ * @param bloom the bloom filter
+ * @param key the key
+ */
+ public static void remove(byte[] bloom, Object key){
+ throw new UnsupportedOperationException();
+ }
+
+ /**
+ * Check whether the given key is probably in the set. This method never
+ * returns false if the key is in the set, but possibly returns true even
if
+ * it isn't.
+ *
+ * @param bloom the bloom filter
+ * @param key the key
+ * @return true if the given key is probably in the set
+ */
+ public static boolean probablyContains(byte[] bloom, Object key) {
+ int len = bloom.length;
+ if (len == 0) {
+ return true;
+ }
+ int h1 = hash(key.hashCode());
+ long x = bloom[(h1 >>> 3) % len] & (1 << (h1 & 7));
+ if (x != 0) {
+ int h2 = hash(h1);
+ x = bloom[(h2 >>> 3) % len] & (1 << (h2 & 7));
+ }
+ return x != 0;
+ }
+
+ /**
+ * Get the hash value for the given key. The returned hash value is
+ * stretched so that it should work well even for relatively bad hashCode
+ * implementations.
+ *
+ * @param key the key
+ * @return the hash value
+ */
+ private static int hash(int key) {
+ int hash = key;
+ // a supplemental secondary hash function
+ // to protect against hash codes that don't differ much
+ hash = ((hash >>> 16) ^ hash) * 0x45d9f3b;
+ hash = ((hash >>> 16) ^ hash) * 0x45d9f3b;
+ hash = (hash >>> 16) ^ hash;
+ return hash;
+ }
+
+}
Modified:
sling/trunk/bundles/resourceresolver/src/main/java/org/apache/sling/resourceresolver/impl/mapping/MapConfigurationProvider.java
URL:
http://svn.apache.org/viewvc/sling/trunk/bundles/resourceresolver/src/main/java/org/apache/sling/resourceresolver/impl/mapping/MapConfigurationProvider.java?rev=1647303&r1=1647302&r2=1647303&view=diff
==============================================================================
---
sling/trunk/bundles/resourceresolver/src/main/java/org/apache/sling/resourceresolver/impl/mapping/MapConfigurationProvider.java
(original)
+++
sling/trunk/bundles/resourceresolver/src/main/java/org/apache/sling/resourceresolver/impl/mapping/MapConfigurationProvider.java
Mon Dec 22 12:39:40 2014
@@ -39,6 +39,10 @@ public interface MapConfigurationProvide
int getDefaultVanityPathRedirectStatus();
boolean isVanityPathEnabled();
+
+ long getMaxCachedVanityPathEntries();
+
+ int getVanityBloomFilterMaxBytes();
boolean isOptimizeAliasResolutionEnabled();
Modified:
sling/trunk/bundles/resourceresolver/src/main/java/org/apache/sling/resourceresolver/impl/mapping/MapEntries.java
URL:
http://svn.apache.org/viewvc/sling/trunk/bundles/resourceresolver/src/main/java/org/apache/sling/resourceresolver/impl/mapping/MapEntries.java?rev=1647303&r1=1647302&r2=1647303&view=diff
==============================================================================
---
sling/trunk/bundles/resourceresolver/src/main/java/org/apache/sling/resourceresolver/impl/mapping/MapEntries.java
(original)
+++
sling/trunk/bundles/resourceresolver/src/main/java/org/apache/sling/resourceresolver/impl/mapping/MapEntries.java
Mon Dec 22 12:39:40 2014
@@ -18,6 +18,11 @@
*/
package org.apache.sling.resourceresolver.impl.mapping;
+import java.io.DataInputStream;
+import java.io.File;
+import java.io.FileInputStream;
+import java.io.FileOutputStream;
+import java.io.IOException;
import java.net.MalformedURLException;
import java.net.URL;
import java.util.ArrayList;
@@ -30,6 +35,8 @@ import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
+import java.util.Timer;
+import java.util.TimerTask;
import java.util.Map.Entry;
import java.util.NoSuchElementException;
import java.util.SortedMap;
@@ -37,10 +44,9 @@ import java.util.TreeMap;
import java.util.TreeSet;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.TimeUnit;
+import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.locks.ReentrantLock;
-
import javax.servlet.http.HttpServletResponse;
-
import org.apache.sling.api.SlingConstants;
import org.apache.sling.api.resource.LoginException;
import org.apache.sling.api.resource.Resource;
@@ -75,6 +81,10 @@ public class MapEntries implements Event
public static final String PROP_VANITY_PATH = "sling:vanityPath";
public static final String PROP_VANITY_ORDER = "sling:vanityOrder";
+
+ private static final String VANITY_BLOOM_FILTER_NAME =
"vanityBloomFilter.txt";
+
+ private static final int VANITY_BLOOM_FILTER_MAX_ENTRIES = 10000000;
/** Key for the global list. */
private static final String GLOBAL_LIST_KEY = "*";
@@ -111,12 +121,26 @@ public class MapEntries implements Event
private final ReentrantLock initializing = new ReentrantLock();
private final boolean enabledVanityPaths;
+
+ private final long maxCachedVanityPathEntries;
+
+ private final int vanityBloomFilterMaxBytes;
private final boolean enableOptimizeAliasResolution;
private final boolean vanityPathPrecedence;
private final List<VanityPathConfig> vanityPathConfig;
+
+ private final AtomicLong vanityCounter;
+
+ private final File vanityBloomFilterFile;
+
+ private byte[] vanityBloomFilter;
+
+ private Timer timer;
+
+ private boolean updateBloomFilterFile = false;
@SuppressWarnings("unchecked")
private MapEntries() {
@@ -131,18 +155,24 @@ public class MapEntries implements Event
this.registration = null;
this.eventAdmin = null;
this.enabledVanityPaths = true;
+ this.maxCachedVanityPathEntries = -1;
+ this.vanityBloomFilterMaxBytes = 0;
this.enableOptimizeAliasResolution = true;
this.vanityPathConfig = null;
this.vanityPathPrecedence = false;
+ this.vanityCounter = new AtomicLong(0);
+ this.vanityBloomFilterFile = null;
}
@SuppressWarnings("unchecked")
public MapEntries(final MapConfigurationProvider factory, final
BundleContext bundleContext, final EventAdmin eventAdmin)
- throws LoginException {
+ throws LoginException, IOException {
this.resolver = factory.getAdministrativeResourceResolver(null);
this.factory = factory;
this.mapRoot = factory.getMapRoot();
this.enabledVanityPaths = factory.isVanityPathEnabled();
+ this.maxCachedVanityPathEntries =
factory.getMaxCachedVanityPathEntries();
+ this.vanityBloomFilterMaxBytes =
factory.getVanityBloomFilterMaxBytes();
this.vanityPathConfig = factory.getVanityPathConfig();
this.enableOptimizeAliasResolution =
factory.isOptimizeAliasResolutionEnabled();
this.vanityPathPrecedence = factory.hasVanityPathPrecedence();
@@ -161,6 +191,10 @@ public class MapEntries implements Event
props.put(Constants.SERVICE_DESCRIPTION, "Map Entries Observation");
props.put(Constants.SERVICE_VENDOR, "The Apache Software Foundation");
this.registration =
bundleContext.registerService(EventHandler.class.getName(), this, props);
+
+ this.vanityCounter = new AtomicLong(0);
+ this.vanityBloomFilterFile =
bundleContext.getDataFile(VANITY_BLOOM_FILTER_NAME);
+ initializeVanityPaths();
}
/**
@@ -179,8 +213,6 @@ public class MapEntries implements Event
}
final Map<String, List<MapEntry>> newResolveMapsMap = new
ConcurrentHashMap<String, List<MapEntry>>();
-
- final Map<String,List<String>> vanityTargets =
(this.enabledVanityPaths ? this.loadVanityPaths(resolver, newResolveMapsMap) :
Collections.<String,List <String>>emptyMap());
//optimization made in SLING-2521
if (enableOptimizeAliasResolution){
@@ -188,7 +220,6 @@ public class MapEntries implements Event
this.aliasMap = aliasMap;
}
- this.vanityTargets = vanityTargets;
this.resolveMapsMap = newResolveMapsMap;
doUpdateConfiguration();
@@ -204,6 +235,58 @@ public class MapEntries implements Event
}
}
+
+ /**
+ * Actual vanity paths initializer. Guards itself against concurrent use by
+ * using a ReentrantLock. Does nothing if the resource resolver has already
+ * been null-ed.
+ *
+ * @throws IOException
+ */
+ protected void initializeVanityPaths() throws IOException {
+ this.initializing.lock();
+ try {
+ if (this.enabledVanityPaths) {
+
+ if (vanityBloomFilterFile == null) {
+ throw new RuntimeException(
+ "This platform does not have file system support");
+ }
+ boolean createVanityBloomFilter = false;
+ if (!vanityBloomFilterFile.exists()) {
+ log.debug("creating bloom filter file {}",
+ vanityBloomFilterFile.getAbsolutePath());
+ vanityBloomFilter = createVanityBloomFilter();
+ persistBloomFilter();
+ createVanityBloomFilter = true;
+ } else {
+ // initialize bloom filter from disk
+ vanityBloomFilter = new byte[(int) vanityBloomFilterFile
+ .length()];
+ DataInputStream dis = new DataInputStream(
+ new FileInputStream(vanityBloomFilterFile));
+ try {
+ dis.readFully(vanityBloomFilter);
+ } finally {
+ dis.close();
+ }
+ }
+
+ // task for persisting the bloom filter every minute (if
changes
+ // exist)
+ timer = new Timer();
+ timer.schedule(new BloomFilterTask(), 60 * 1000);
+
+ final Map<String, List<String>> vanityTargets = this
+ .loadVanityPaths(resolver, resolveMapsMap,
+ createVanityBloomFilter);
+ this.vanityTargets = vanityTargets;
+ }
+ } finally {
+ this.initializing.unlock();
+ }
+
+ }
private boolean doNodeAdded(String path, boolean refreshed) {
this.initializing.lock();
@@ -363,7 +446,15 @@ public class MapEntries implements Event
private void doAddVanity(String path) {
Resource resource = resolver.getResource(path);
- loadVanityPath(resource, resolveMapsMap, vanityTargets);
+ if (maxCachedVanityPathEntries < vanityCounter.longValue()) {
+ // fill up the cache and the bloom filter
+ loadVanityPath(resource, resolveMapsMap, vanityTargets, true,
true);
+ vanityCounter.incrementAndGet();
+ } else {
+ // fill up the bloom filter
+ loadVanityPath(resource, resolveMapsMap, vanityTargets, false,
true);
+ }
+ updateBloomFilterFile = true;
}
private void doUpdateVanity(String path) {
@@ -392,6 +483,9 @@ public class MapEntries implements Event
}
}
vanityTargets.remove(actualContentPath);
+ if (vanityCounter.longValue() > 0) {
+ vanityCounter.decrementAndGet();
+ }
}
private void doUpdateVanityOrder(String path, boolean deletion) {
@@ -518,6 +612,12 @@ public class MapEntries implements Event
* Cleans up this class.
*/
public void dispose() {
+ try {
+ persistBloomFilter();
+ } catch (IOException e) {
+ log.error("Error while saving bloom filter to disk", e);
+ }
+
if (this.registration != null) {
this.registration.unregister();
this.registration = null;
@@ -601,6 +701,23 @@ public class MapEntries implements Event
public Map<String, String> getAliasMap(final String parentPath) {
return aliasMap.get(parentPath);
}
+
+ /**
+ * get the MapEnty containing all the nodes having a specific vanityPath
+ */
+ private List<MapEntry> getMapEntryList(String vanityPath){
+ List<MapEntry> mapEntries = null;
+
+ if (BloomFilterUtils.probablyContains(vanityBloomFilter, vanityPath)) {
+ mapEntries = this.resolveMapsMap.get(vanityPath);
+ if (mapEntries == null) {
+ Map<String, List<MapEntry>> mapEntry =
getVanityPaths(vanityPath);
+ mapEntries = mapEntry.get(vanityPath);
+ }
+ }
+
+ return mapEntries;
+ }
// ---------- EventListener interface
@@ -679,6 +796,76 @@ public class MapEntries implements Event
// ---------- internal
+ private byte[] createVanityBloomFilter() throws IOException {
+ byte bloomFilter[] = null;
+ if (vanityBloomFilter == null) {
+ bloomFilter =
BloomFilterUtils.createFilter(VANITY_BLOOM_FILTER_MAX_ENTRIES,
this.vanityBloomFilterMaxBytes);
+ }
+ return bloomFilter;
+ }
+
+ private void persistBloomFilter() throws IOException {
+ if (vanityBloomFilterFile != null && vanityBloomFilter != null) {
+ FileOutputStream out = new FileOutputStream(vanityBloomFilterFile);
+ try {
+ out.write(this.vanityBloomFilter);
+ } finally {
+ out.close();
+ }
+ }
+ }
+
+ private boolean isAllVanityPathEntriesCached() {
+ return maxCachedVanityPathEntries == -1;
+ }
+
+ /**
+ * Escapes illegal XPath search characters at the end of a string.
+ * <p>
+ * Example:<br>
+ * A search string like 'test?' will run into a ParseException documented
in
+ * http://issues.apache.org/jira/browse/JCR-1248
+ *
+ * @param s
+ * the string to encode
+ * @return the escaped string
+ */
+ private static String escapeIllegalXpathSearchChars(String s) {
+ StringBuilder sb = new StringBuilder();
+ if (s != null && s.length() > 1) {
+ sb.append(s.substring(0, (s.length() - 1)));
+ char c = s.charAt(s.length() - 1);
+ // NOTE: keep this in sync with _ESCAPED_CHAR below!
+ if (c == '!' || c == '(' || c == ':' || c == '^' || c == '['
+ || c == ']' || c == '{' || c == '}' || c == '?') {
+ sb.append('\\');
+ }
+ sb.append(c);
+ }
+ return sb.toString();
+ }
+
+ /**
+ * get the vanity paths Search for all nodes having a specific vanityPath
+ */
+ private Map<String, List<MapEntry>> getVanityPaths(String vanityPath) {
+
+ final Map<String, List<MapEntry>> entryMap = new HashMap<String,
List<MapEntry>>();
+ final Map <String, List<String>> targetPaths = new HashMap <String,
List<String>>();
+
+ // sling:VanityPath (uppercase V) is the mixin name
+ // sling:vanityPath (lowercase) is the property name
+ final String queryString = "SELECT sling:vanityPath, sling:redirect,
sling:redirectStatus FROM sling:VanityPath WHERE sling:vanityPath ="
+ +
"'"+escapeIllegalXpathSearchChars(vanityPath).replaceAll("'", "''")+"' OR
sling:vanityPath ="+
"'"+escapeIllegalXpathSearchChars(vanityPath.substring(1)).replaceAll("'",
"''")+"' ORDER BY sling:vanityOrder DESC";
+ final Iterator<Resource> i = resolver.findResources(queryString,
"sql");
+
+ while (i.hasNext()) {
+ final Resource resource = i.next();
+ loadVanityPath(resource, entryMap, targetPaths, true, false);
+ }
+ return entryMap;
+ }
+
private boolean isValidVanityPath(Resource resource){
// ignore system tree
if (resource.getPath().startsWith(JCR_SYSTEM_PREFIX)) {
@@ -907,25 +1094,36 @@ public class MapEntries implements Event
* Load vanity paths Search for all nodes inheriting the sling:VanityPath
* mixin
*/
- private Map <String, List<String>> loadVanityPaths(final ResourceResolver
resolver, final Map<String, List<MapEntry>> entryMap) {
+ private Map <String, List<String>> loadVanityPaths(final ResourceResolver
resolver, final Map<String, List<MapEntry>> entryMap, boolean
createVanityBloomFilter) {
// sling:VanityPath (uppercase V) is the mixin name
// sling:vanityPath (lowercase) is the property name
final Map <String, List<String>> targetPaths = new ConcurrentHashMap
<String, List<String>>();
final String queryString = "SELECT sling:vanityPath, sling:redirect,
sling:redirectStatus FROM sling:VanityPath WHERE sling:vanityPath IS NOT NULL";
final Iterator<Resource> i = resolver.findResources(queryString,
"sql");
- while (i.hasNext()) {
+ while (i.hasNext() && (createVanityBloomFilter ||
maxCachedVanityPathEntries < vanityCounter.longValue())) {
final Resource resource = i.next();
- loadVanityPath(resource, entryMap, targetPaths);
+ if (maxCachedVanityPathEntries < vanityCounter.longValue()) {
+ // fill up the cache and the bloom filter
+ loadVanityPath(resource, entryMap, targetPaths, true,
+ createVanityBloomFilter);
+ vanityCounter.incrementAndGet();
+ } else {
+ // fill up the bloom filter
+ loadVanityPath(resource, entryMap, targetPaths, false,
+ createVanityBloomFilter);
+ }
+
}
+
return targetPaths;
}
/**
* Load vanity path given a resource
*/
- private void loadVanityPath(final Resource resource, final Map<String,
List<MapEntry>> entryMap, final Map <String, List<String>> targetPaths) {
+ private void loadVanityPath(final Resource resource, final Map<String,
List<MapEntry>> entryMap, final Map <String, List<String>> targetPaths, boolean
addToCache, boolean newVanity) {
if (!isValidVanityPath(resource)) {
return;
@@ -967,25 +1165,36 @@ public class MapEntries implements Event
final String checkPath = result[1];
boolean addedEntry;
- if (redirectName.indexOf('.') > -1) {
- // 1. entry with exact match
- this.addEntry(entryMap, checkPath, getMapEntry(url + "$",
status, false, vanityOrder, redirect));
+ if (addToCache) {
+ if (redirectName.indexOf('.') > -1) {
+ // 1. entry with exact match
+ this.addEntry(entryMap, checkPath, getMapEntry(url +
"$", status, false, vanityOrder, redirect));
- final int idx = redirectName.lastIndexOf('.');
- final String extension = redirectName.substring(idx + 1);
+ final int idx = redirectName.lastIndexOf('.');
+ final String extension = redirectName.substring(idx +
1);
- // 2. entry with extension
- addedEntry = this.addEntry(entryMap, checkPath,
getMapEntry(url + "\\." + extension, status, false, vanityOrder, redirect));
- } else {
- // 1. entry with exact match
- this.addEntry(entryMap, checkPath, getMapEntry(url + "$",
status, false, vanityOrder, redirect + ".html"));
+ // 2. entry with extension
+ addedEntry = this.addEntry(entryMap, checkPath,
getMapEntry(url + "\\." + extension, status, false, vanityOrder, redirect));
+ } else {
+ // 1. entry with exact match
+ this.addEntry(entryMap, checkPath, getMapEntry(url +
"$", status, false, vanityOrder, redirect + ".html"));
- // 2. entry with match supporting selectors and extension
- addedEntry = this.addEntry(entryMap, checkPath,
getMapEntry(url + "(\\..*)", status, false, vanityOrder, redirect + "$1"));
- }
- if (addedEntry) {
- // 3. keep the path to return
- this.updateTargetPaths(targetPaths, redirect, checkPath);
+ // 2. entry with match supporting selectors and
extension
+ addedEntry = this.addEntry(entryMap, checkPath,
getMapEntry(url + "(\\..*)", status, false, vanityOrder, redirect + "$1"));
+ }
+ if (addedEntry) {
+ // 3. keep the path to return
+ this.updateTargetPaths(targetPaths, redirect,
checkPath);
+ if (newVanity) {
+ // update bloom filter
+ BloomFilterUtils.add(vanityBloomFilter, checkPath);
+ }
+ }
+ } else {
+ if (newVanity) {
+ // update bloom filter
+ BloomFilterUtils.add(vanityBloomFilter, checkPath);
+ }
}
}
}
@@ -1174,7 +1383,7 @@ public class MapEntries implements Event
return filter.toString();
}
- private static final class MapEntryIterator implements Iterator<MapEntry> {
+ private final class MapEntryIterator implements Iterator<MapEntry> {
private final Map<String, List<MapEntry>> resolveMapsMap;
@@ -1239,7 +1448,13 @@ public class MapEntries implements Event
if (lastDotPos != -1) {
key = key.substring(0, lastDotPos);
}
- final List<MapEntry> special =
this.resolveMapsMap.get(key);
+
+ final List<MapEntry> special;
+ if (MapEntries.this.isAllVanityPathEntriesCached()) {
+ special = this.resolveMapsMap.get(key);
+ } else {
+ special = MapEntries.this.getMapEntryList(key)
+; }
if (special != null) {
specialIterator = special.iterator();
}
@@ -1306,5 +1521,20 @@ public class MapEntries implements Event
}
return mapEntry;
}
+
+ final class BloomFilterTask extends TimerTask {
+ @Override
+ public void run() {
+ try {
+ if (updateBloomFilterFile) {
+ persistBloomFilter();
+ updateBloomFilterFile = false;
+ }
+ } catch (IOException e) {
+ throw new RuntimeException(
+ "Error while saving bloom filter to disk", e);
+ }
+ }
+ }
}
Added:
sling/trunk/bundles/resourceresolver/src/test/java/org/apache/sling/resourceresolver/impl/mapping/BloomFilterUtilsTest.java
URL:
http://svn.apache.org/viewvc/sling/trunk/bundles/resourceresolver/src/test/java/org/apache/sling/resourceresolver/impl/mapping/BloomFilterUtilsTest.java?rev=1647303&view=auto
==============================================================================
---
sling/trunk/bundles/resourceresolver/src/test/java/org/apache/sling/resourceresolver/impl/mapping/BloomFilterUtilsTest.java
(added)
+++
sling/trunk/bundles/resourceresolver/src/test/java/org/apache/sling/resourceresolver/impl/mapping/BloomFilterUtilsTest.java
Mon Dec 22 12:39:40 2014
@@ -0,0 +1,206 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.sling.resourceresolver.impl.mapping;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+import java.math.BigInteger;
+import java.util.HashSet;
+import java.util.Random;
+import org.junit.Test;
+
+/**
+ * Test the bloom filter utility class.
+ */
+public class BloomFilterUtilsTest {
+
+ /**
+ * Program to calculate the best shift and multiply constants.
+ */
+ public static void main(String... args) {
+ Random random = new Random(1);
+ HashSet<String> inSet = new HashSet<String>();
+ while (inSet.size() < 100) {
+ inSet.add(randomString(random));
+ }
+ Object[] in = inSet.toArray();
+ HashSet<String> notSet = new HashSet<String>();
+ while (notSet.size() < 10000) {
+ String k = randomString(random);
+ if (!inSet.contains(k)) {
+ notSet.add(k);
+ }
+ }
+ Object[] not = notSet.toArray();
+ int best = Integer.MAX_VALUE;
+ for (int mul = 1; mul < 100000; mul += 2) {
+ if (!BigInteger.valueOf(mul).isProbablePrime(10)) {
+ continue;
+ }
+ for (int shift = 0; shift < 32; shift++) {
+ byte[] bloom = BloomFilterUtils.createFilter(100, 64);
+ for (Object k : in) {
+ int h1 = hash(k.hashCode(), mul, shift), h2 = hash(h1,
mul, shift);
+ add(bloom, h1, h2);
+ }
+ int falsePositives = 0;
+ for (Object k : not) {
+ int h1 = hash(k.hashCode(), mul, shift), h2 = hash(h1,
mul, shift);
+ if (probablyContains(bloom, h1, h2)) {
+ falsePositives++;
+ // short false positives are bad
+ if (k.toString().length() < 4) {
+ falsePositives += 5;
+ }
+ if (falsePositives > best) {
+ break;
+ }
+ }
+ }
+ if (falsePositives < best) {
+ best = falsePositives;
+ System.out.println("mul: " + mul + " shift: "
+ + shift + " falsePositives: " + best);
+ }
+ }
+ }
+ }
+
+ private static String randomString(Random r) {
+ if (r.nextInt(5) == 0) {
+ return randomName(r);
+ }
+ int length = 1 + Math.abs((int) r.nextGaussian() * 5);
+ if (r.nextBoolean()) {
+ length += r.nextInt(10);
+ }
+ char[] chars = new char[length];
+ for (int i = 0; i < length; i++) {
+ chars[i] = randomChar(r);
+ }
+ return new String(chars);
+ }
+
+ private static char randomChar(Random r) {
+ switch (r.nextInt(101) / 100) {
+ case 0:
+ case 1:
+ // 20% ascii
+ return (char) (32 + r.nextInt(127 - 32));
+ case 2:
+ case 3:
+ case 4:
+ case 5:
+ // 40% a-z
+ return (char) ('a' + r.nextInt('z' - 'a'));
+ case 6:
+ // 10% A-Z
+ return (char) ('A' + r.nextInt('Z' - 'A'));
+ case 7:
+ case 8:
+ // 20% 0-9
+ return (char) ('0' + r.nextInt('9' - '0'));
+ case 9:
+ // 10% aeiou
+ return "aeiou".charAt(r.nextInt("aeiou".length()));
+ }
+ // 1% unicode
+ return (char) r.nextInt(65535);
+ }
+
+ private static String randomName(Random r) {
+ int i = r.nextInt(1000);
+ // like TPC-C lastName, but lowercase
+ String[] n = {
+ "bar", "ought", "able", "pri", "pres", "ese", "anti",
+ "cally", "ation", "eing" };
+ StringBuilder buff = new StringBuilder();
+ buff.append(n[i / 100]);
+ buff.append(n[(i / 10) % 10]);
+ buff.append(n[i % 10]);
+ return buff.toString();
+ }
+
+
+ private static int hash(int oldHash, int mul, int shift) {
+ return oldHash ^ ((oldHash * mul) >> shift);
+ }
+
+ private static void add(byte[] bloom, int h1, int h2) {
+ int len = bloom.length;
+ if (len > 0) {
+ bloom[(h1 >>> 3) % len] |= 1 << (h1 & 7);
+ bloom[(h2 >>> 3) % len] |= 1 << (h2 & 7);
+ }
+ }
+
+ private static boolean probablyContains(byte[] bloom, int h1, int h2) {
+ int len = bloom.length;
+ if (len == 0) {
+ return true;
+ }
+ int x = bloom[(h1 >>> 3) % len] & (1 << (h1 & 7));
+ if (x != 0) {
+ x = bloom[(h2 >>> 3) % len] & (1 << (h2 & 7));
+ }
+ return x != 0;
+ }
+
+ @Test
+ public void size() {
+ byte[] bloom = BloomFilterUtils.createFilter(100, 64);
+ assertEquals(64, bloom.length);
+ bloom = BloomFilterUtils.createFilter(10, 64);
+ assertEquals(11, bloom.length);
+ bloom = BloomFilterUtils.createFilter(0, 64);
+ assertEquals(0, bloom.length);
+ bloom = BloomFilterUtils.createFilter(1, 64);
+ assertEquals(1, bloom.length);
+ }
+
+ @Test
+ public void probability() {
+ byte[] bloom = BloomFilterUtils.createFilter(20, 64);
+ System.out.println(bloom.length);
+ Random random = new Random(1);
+ random.setSeed(1);
+ for (int i = 0; i < 20; i++) {
+ BloomFilterUtils.add(bloom, random.nextInt());
+ }
+ random.setSeed(1);
+ for (int i = 0; i < 20; i++) {
+ assertTrue(BloomFilterUtils.probablyContains(bloom,
random.nextInt()));
+ }
+ int falsePositives = 0;
+ for (int i = 20; i < 100000; i++) {
+ if (BloomFilterUtils.probablyContains(bloom, random.nextInt())) {
+ falsePositives++;
+ }
+ }
+ assertEquals(4594, falsePositives);
+ }
+ @Test
+ public void negativeHashCode() {
+ BloomFilterUtils.add(new byte[0], new Object() {
+ @Override
+ public int hashCode() {
+ return -1;
+ }
+ });
+ }
+
+}
Modified:
sling/trunk/bundles/resourceresolver/src/test/java/org/apache/sling/resourceresolver/impl/mapping/MapEntriesTest.java
URL:
http://svn.apache.org/viewvc/sling/trunk/bundles/resourceresolver/src/test/java/org/apache/sling/resourceresolver/impl/mapping/MapEntriesTest.java?rev=1647303&r1=1647302&r2=1647303&view=diff
==============================================================================
---
sling/trunk/bundles/resourceresolver/src/test/java/org/apache/sling/resourceresolver/impl/mapping/MapEntriesTest.java
(original)
+++
sling/trunk/bundles/resourceresolver/src/test/java/org/apache/sling/resourceresolver/impl/mapping/MapEntriesTest.java
Mon Dec 22 12:39:40 2014
@@ -26,6 +26,8 @@ import static org.mockito.Matchers.eq;
import static org.mockito.Mockito.mock;
import static org.mockito.Mockito.when;
+import java.io.File;
+import java.io.IOException;
import java.lang.reflect.Field;
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
@@ -87,6 +89,8 @@ public class MapEntriesTest {
configs.add(new VanityPathConfig("/vanityPathOnJcrContent", false));
Collections.sort(configs);
+
+
when(bundleContext.getDataFile("vanityBloomFilter.txt")).thenReturn(new
File("vanityBloomFilter.txt"));
when(resourceResolverFactory.getAdministrativeResourceResolver(null)).thenReturn(resourceResolver);
when(resourceResolverFactory.isVanityPathEnabled()).thenReturn(true);
when(resourceResolverFactory.getVanityPathConfig()).thenReturn(configs);
@@ -98,6 +102,11 @@ public class MapEntriesTest {
Field field0 = MapEntries.class.getDeclaredField("mapRoot");
field0.setAccessible(true);
field0.set(mapEntries, MapEntries.DEFAULT_MAP_ROOT);
+
+ Field field1 =
MapEntries.class.getDeclaredField("maxCachedVanityPathEntries");
+ field1.setAccessible(true);
+ field1.set(mapEntries, -1);
+
}
@Test
@@ -224,6 +233,7 @@ public class MapEntriesTest {
});
mapEntries.doInit();
+ mapEntries.initializeVanityPaths();
List<MapEntry> entries = mapEntries.getResolveMaps();
assertEquals(8, entries.size());
@@ -267,7 +277,7 @@ public class MapEntriesTest {
}
@Test
- public void test_vanity_path_registration_include_exclude() {
+ public void test_vanity_path_registration_include_exclude() throws
IOException {
final String[] validPaths = {"/libs/somewhere", "/libs/a/b", "/foo/a",
"/baa/a"};
final String[] invalidPaths = {"/libs/denied/a", "/libs/denied/b/c",
"/nowhere"};
@@ -292,6 +302,7 @@ public class MapEntriesTest {
});
mapEntries.doInit();
+ mapEntries.initializeVanityPaths();
List<MapEntry> entries = mapEntries.getResolveMaps();
// each valid resource results in 2 entries
