Repository: incubator-ranger Updated Branches: refs/heads/ranger-0.5 141018c5e -> ed4b8985d
RANGER-1161: Policy evaluation optimization: trie updated for evaluator-lists to be shared amongst nodes Project: http://git-wip-us.apache.org/repos/asf/incubator-ranger/repo Commit: http://git-wip-us.apache.org/repos/asf/incubator-ranger/commit/ed4b8985 Tree: http://git-wip-us.apache.org/repos/asf/incubator-ranger/tree/ed4b8985 Diff: http://git-wip-us.apache.org/repos/asf/incubator-ranger/diff/ed4b8985 Branch: refs/heads/ranger-0.5 Commit: ed4b8985d2ef73d8ddde237c047329a5bd2cb520 Parents: 141018c Author: Madhan Neethiraj <[email protected]> Authored: Fri Aug 26 22:34:31 2016 -0700 Committer: Madhan Neethiraj <[email protected]> Committed: Fri Aug 26 22:52:01 2016 -0700 ---------------------------------------------------------------------- .../policyengine/RangerPolicyRepository.java | 2 +- .../RangerAbstractPolicyEvaluator.java | 30 ++- .../policyevaluator/RangerPolicyEvaluator.java | 3 +- .../RangerPolicyResourceEvaluator.java | 36 +++ .../ranger/plugin/util/RangerResourceTrie.java | 257 ++++++++++++------- 5 files changed, 224 insertions(+), 104 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/incubator-ranger/blob/ed4b8985/agents-common/src/main/java/org/apache/ranger/plugin/policyengine/RangerPolicyRepository.java ---------------------------------------------------------------------- diff --git a/agents-common/src/main/java/org/apache/ranger/plugin/policyengine/RangerPolicyRepository.java b/agents-common/src/main/java/org/apache/ranger/plugin/policyengine/RangerPolicyRepository.java index 5de4583..539d580 100644 --- a/agents-common/src/main/java/org/apache/ranger/plugin/policyengine/RangerPolicyRepository.java +++ b/agents-common/src/main/java/org/apache/ranger/plugin/policyengine/RangerPolicyRepository.java @@ -282,7 +282,7 @@ public class RangerPolicyRepository { continue; } - List<RangerPolicyEvaluator> resourceEvaluators = trie.getPoliciesForResource(resource.getValue(resourceName)); + List<RangerPolicyEvaluator> resourceEvaluators = trie.getEvaluatorsForResource(resource.getValue(resourceName)); if(CollectionUtils.isEmpty(resourceEvaluators)) { // no policies for this resource, bail out ret = null; http://git-wip-us.apache.org/repos/asf/incubator-ranger/blob/ed4b8985/agents-common/src/main/java/org/apache/ranger/plugin/policyevaluator/RangerAbstractPolicyEvaluator.java ---------------------------------------------------------------------- diff --git a/agents-common/src/main/java/org/apache/ranger/plugin/policyevaluator/RangerAbstractPolicyEvaluator.java b/agents-common/src/main/java/org/apache/ranger/plugin/policyevaluator/RangerAbstractPolicyEvaluator.java index 14a003b..f3c2de6 100644 --- a/agents-common/src/main/java/org/apache/ranger/plugin/policyevaluator/RangerAbstractPolicyEvaluator.java +++ b/agents-common/src/main/java/org/apache/ranger/plugin/policyevaluator/RangerAbstractPolicyEvaluator.java @@ -28,6 +28,10 @@ import org.apache.ranger.plugin.model.RangerPolicy; import org.apache.ranger.plugin.model.RangerServiceDef; import org.apache.ranger.plugin.policyengine.RangerPolicyEngineOptions; import org.apache.ranger.plugin.policyengine.RangerAccessRequest; +import org.apache.ranger.plugin.policyresourcematcher.RangerPolicyResourceEvaluator; + + +import java.util.Map; public abstract class RangerAbstractPolicyEvaluator implements RangerPolicyEvaluator { @@ -53,6 +57,16 @@ public abstract class RangerAbstractPolicyEvaluator implements RangerPolicyEvalu } @Override + public long getId() { + return policy != null ? policy.getId() :-1; + } + + @Override + public Map<String, RangerPolicy.RangerPolicyResource> getPolicyResource() { + return policy !=null ? policy.getResources() : null; + } + + @Override public RangerPolicy getPolicy() { return policy; } @@ -73,15 +87,23 @@ public abstract class RangerAbstractPolicyEvaluator implements RangerPolicyEvalu } @Override - public int compareTo(RangerPolicyEvaluator other) { + public int compareTo(RangerPolicyResourceEvaluator obj) { if(LOG.isDebugEnabled()) { LOG.debug("==> RangerAbstractPolicyEvaluator.compareTo()"); } - int result = Integer.compare(this.getEvalOrder(), other.getEvalOrder()); + int result; + + if(obj instanceof RangerPolicyEvaluator) { + RangerPolicyEvaluator other = (RangerPolicyEvaluator)obj; + + result = Integer.compare(this.getEvalOrder(), other.getEvalOrder()); - if (result == 0) { - result = Integer.compare(getCustomConditionsCount(), other.getCustomConditionsCount()); + if (result == 0) { + result = Integer.compare(getCustomConditionsCount(), other.getCustomConditionsCount()); + } + } else { + result = Long.compare(getId(), obj.getId()); } if(LOG.isDebugEnabled()) { http://git-wip-us.apache.org/repos/asf/incubator-ranger/blob/ed4b8985/agents-common/src/main/java/org/apache/ranger/plugin/policyevaluator/RangerPolicyEvaluator.java ---------------------------------------------------------------------- diff --git a/agents-common/src/main/java/org/apache/ranger/plugin/policyevaluator/RangerPolicyEvaluator.java b/agents-common/src/main/java/org/apache/ranger/plugin/policyevaluator/RangerPolicyEvaluator.java index cd66dd6..4dafec5 100644 --- a/agents-common/src/main/java/org/apache/ranger/plugin/policyevaluator/RangerPolicyEvaluator.java +++ b/agents-common/src/main/java/org/apache/ranger/plugin/policyevaluator/RangerPolicyEvaluator.java @@ -31,11 +31,12 @@ import org.apache.ranger.plugin.policyengine.RangerAccessResult; import org.apache.ranger.plugin.policyengine.RangerAccessResource; import org.apache.ranger.plugin.policyengine.RangerPolicyEngineOptions; import org.apache.ranger.plugin.policyengine.RangerResourceAccessInfo; +import org.apache.ranger.plugin.policyresourcematcher.RangerPolicyResourceEvaluator; import org.apache.ranger.plugin.policyresourcematcher.RangerPolicyResourceMatcher; import org.apache.ranger.plugin.resourcematcher.RangerResourceMatcher; -public interface RangerPolicyEvaluator extends Comparable<RangerPolicyEvaluator> { +public interface RangerPolicyEvaluator extends RangerPolicyResourceEvaluator { public static final String EVALUATOR_TYPE_AUTO = "auto"; public static final String EVALUATOR_TYPE_OPTIMIZED = "optimized"; public static final String EVALUATOR_TYPE_CACHED = "cached"; http://git-wip-us.apache.org/repos/asf/incubator-ranger/blob/ed4b8985/agents-common/src/main/java/org/apache/ranger/plugin/policyresourcematcher/RangerPolicyResourceEvaluator.java ---------------------------------------------------------------------- diff --git a/agents-common/src/main/java/org/apache/ranger/plugin/policyresourcematcher/RangerPolicyResourceEvaluator.java b/agents-common/src/main/java/org/apache/ranger/plugin/policyresourcematcher/RangerPolicyResourceEvaluator.java new file mode 100644 index 0000000..799e8b3 --- /dev/null +++ b/agents-common/src/main/java/org/apache/ranger/plugin/policyresourcematcher/RangerPolicyResourceEvaluator.java @@ -0,0 +1,36 @@ +/* + * 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.ranger.plugin.policyresourcematcher; + + +import org.apache.ranger.plugin.model.RangerPolicy; +import org.apache.ranger.plugin.resourcematcher.RangerResourceMatcher; + +import java.util.Map; + +public interface RangerPolicyResourceEvaluator extends Comparable<RangerPolicyResourceEvaluator> { + long getId(); + + RangerPolicyResourceMatcher getPolicyResourceMatcher(); + + Map<String, RangerPolicy.RangerPolicyResource> getPolicyResource(); + + RangerResourceMatcher getResourceMatcher(String resourceName); +} http://git-wip-us.apache.org/repos/asf/incubator-ranger/blob/ed4b8985/agents-common/src/main/java/org/apache/ranger/plugin/util/RangerResourceTrie.java ---------------------------------------------------------------------- diff --git a/agents-common/src/main/java/org/apache/ranger/plugin/util/RangerResourceTrie.java b/agents-common/src/main/java/org/apache/ranger/plugin/util/RangerResourceTrie.java index 809c07e..2ca9bd6 100644 --- a/agents-common/src/main/java/org/apache/ranger/plugin/util/RangerResourceTrie.java +++ b/agents-common/src/main/java/org/apache/ranger/plugin/util/RangerResourceTrie.java @@ -23,10 +23,9 @@ package org.apache.ranger.plugin.util; import org.apache.commons.collections.CollectionUtils; import org.apache.commons.logging.Log; import org.apache.commons.logging.LogFactory; -import org.apache.ranger.plugin.model.RangerPolicy; import org.apache.ranger.plugin.model.RangerPolicy.RangerPolicyResource; import org.apache.ranger.plugin.model.RangerServiceDef; -import org.apache.ranger.plugin.policyevaluator.RangerPolicyEvaluator; +import org.apache.ranger.plugin.policyresourcematcher.RangerPolicyResourceEvaluator; import org.apache.ranger.plugin.resourcematcher.RangerAbstractResourceMatcher; import org.apache.ranger.plugin.resourcematcher.RangerResourceMatcher; @@ -37,7 +36,7 @@ import java.util.List; import java.util.Map; -public class RangerResourceTrie { +public class RangerResourceTrie<T extends RangerPolicyResourceEvaluator> { private static final Log LOG = LogFactory.getLog(RangerResourceTrie.class); private static final String DEFAULT_WILDCARD_CHARS = "*?"; @@ -48,7 +47,7 @@ public class RangerResourceTrie { private final String wildcardChars; private final TrieNode root; - public RangerResourceTrie(RangerServiceDef.RangerResourceDef resourceDef, List<RangerPolicyEvaluator> evaluators) { + public RangerResourceTrie(RangerServiceDef.RangerResourceDef resourceDef, List<T> evaluators) { if(LOG.isDebugEnabled()) { LOG.debug("==> RangerResourceTrie(" + resourceDef.getName() + ", evaluatorCount=" + evaluators.size() + ")"); } @@ -63,9 +62,8 @@ public class RangerResourceTrie { this.wildcardChars = optWildcard ? DEFAULT_WILDCARD_CHARS : ""; this.root = new TrieNode(Character.valueOf((char)0)); - for(RangerPolicyEvaluator evaluator : evaluators) { - RangerPolicy policy = evaluator.getPolicy(); - Map<String, RangerPolicyResource> policyResources = policy != null ? policy.getResources() : null; + for(T evaluator : evaluators) { + Map<String, RangerPolicyResource> policyResources = evaluator.getPolicyResource(); RangerPolicyResource policyResource = policyResources != null ? policyResources.get(resourceName) : null; if(policyResource == null) { @@ -73,21 +71,25 @@ public class RangerResourceTrie { } if(policyResource.getIsExcludes()) { - root.addWildcardPolicy(evaluator); + root.addWildcardEvaluator(evaluator); } else { RangerResourceMatcher resourceMatcher = evaluator.getResourceMatcher(resourceName); if(resourceMatcher != null && resourceMatcher.isMatchAny()) { - root.addWildcardPolicy(evaluator); + root.addWildcardEvaluator(evaluator); } else { - for (String resource : policyResource.getValues()) { - insert(resource, policyResource.getIsRecursive(), evaluator); + if(CollectionUtils.isNotEmpty(policyResource.getValues())) { + for (String resource : policyResource.getValues()) { + insert(resource, policyResource.getIsRecursive(), evaluator); + } } } } } - root.postSetup(); + root.postSetup(null); + + LOG.info(toString()); if(LOG.isDebugEnabled()) { LOG.debug("<== RangerResourceTrie(" + resourceDef.getName() + ", evaluatorCount=" + evaluators.size() + "): " + toString()); @@ -98,12 +100,12 @@ public class RangerResourceTrie { return resourceName; } - public List<RangerPolicyEvaluator> getPoliciesForResource(String resource) { + public List<T> getEvaluatorsForResource(String resource) { if(LOG.isDebugEnabled()) { - LOG.debug("==> RangerResourceTrie.getPoliciesForResource(" + resource + ")"); + LOG.debug("==> RangerResourceTrie.getEvaluatorsForResource(" + resource + ")"); } - List<RangerPolicyEvaluator> ret = null; + List<T> ret = null; TrieNode curr = root; @@ -113,8 +115,8 @@ public class RangerResourceTrie { TrieNode child = curr.getChild(ch); if(child == null) { - ret = curr.getWildcardPolicies(); - curr = null; // so that curr.getPolicies() will not be called below + ret = curr.getWildcardEvaluators(); + curr = null; // so that curr.getEvaluators() will not be called below break; } @@ -123,41 +125,46 @@ public class RangerResourceTrie { if(ret == null) { if(curr != null) { - ret = curr.getPolicies(); + ret = curr.getEvaluators(); } } if(LOG.isDebugEnabled()) { - LOG.debug("<== RangerResourceTrie.getPoliciesForResource(" + resource + "): evaluatorCount=" + (ret == null ? 0 : ret.size())); + LOG.debug("<== RangerResourceTrie.getEvaluatorsForResource(" + resource + "): evaluatorCount=" + (ret == null ? 0 : ret.size())); } return ret; } - public int getNodeCount() { - return root.getNodeCount(); + public TrieData getTrieData() { + TrieData ret = new TrieData(); + + root.populateTrieData(ret); + ret.maxDepth = getMaxDepth(); + + return ret; } public int getMaxDepth() { return root.getMaxDepth(); } - public void reorderPolicyEvaluators() { - root.reorderPolicyEvaluators(); + public void reorderEvaluators() { + root.reorderEvaluators(null); } - private Character getLookupChar(char ch) { - return optIgnoreCase ? Character.valueOf(Character.toLowerCase(ch)) : Character.valueOf(ch); + private final Character getLookupChar(char ch) { + if(optIgnoreCase) { + ch = Character.toLowerCase(ch); + } + + return Character.valueOf(ch); } - private void insert(String resource, boolean isRecursive, RangerPolicyEvaluator evaluator) { + private void insert(String resource, boolean isRecursive, T evaluator) { TrieNode curr = root; boolean isWildcard = false; - if(optIgnoreCase) { - resource = resource.toLowerCase(); - } - final int len = resource.length(); for(int i = 0; i < len; i++) { Character ch = getLookupChar(resource.charAt(i)); @@ -173,9 +180,9 @@ public class RangerResourceTrie { } if(isWildcard || isRecursive) { - curr.addWildcardPolicy(evaluator); + curr.addWildcardEvaluator(evaluator); } else { - curr.addPolicy(evaluator); + curr.addEvaluator(evaluator); } } @@ -183,20 +190,38 @@ public class RangerResourceTrie { public String toString() { StringBuilder sb = new StringBuilder(); - sb.append("nodeCount=").append(getNodeCount()); - sb.append("; maxDepth=").append(getMaxDepth()); - sb.append(Character.LINE_SEPARATOR); - root.toString("", sb); + TrieData trieData = getTrieData(); + + sb.append("resourceName=").append(resourceName); + sb.append("; optIgnoreCase=").append(optIgnoreCase); + sb.append("; optWildcard=").append(optWildcard); + sb.append("; wildcardChars=").append(wildcardChars); + sb.append("; nodeCount=").append(trieData.nodeCount); + sb.append("; maxDepth=").append(trieData.maxDepth); + sb.append("; evaluatorListCount=").append(trieData.evaluatorListCount); + sb.append("; wildcardEvaluatorListCount=").append(trieData.wildcardEvaluatorListCount); + sb.append("; evaluatorListRefCount=").append(trieData.evaluatorListRefCount); + sb.append("; wildcardEvaluatorListRefCount=").append(trieData.wildcardEvaluatorListRefCount); return sb.toString(); } + + public class TrieData { + int nodeCount = 0; + int maxDepth = 0; + int evaluatorListCount = 0; + int wildcardEvaluatorListCount = 0; + int evaluatorListRefCount = 0; + int wildcardEvaluatorListRefCount = 0; + } } -class TrieNode { - private final Character c; - private Map<Character, TrieNode> children = null; - private List<RangerPolicyEvaluator> policies = null; - private List<RangerPolicyEvaluator> wildcardPolicies = null; +class TrieNode<T extends RangerPolicyResourceEvaluator> { + private final Character c; + private Map<Character, TrieNode> children = null; + private List<T> evaluators = null; + private List<T> wildcardEvaluators = null; + private boolean isSharingParentWildcardEvaluators = false; TrieNode(Character c) { this.c = c; @@ -210,12 +235,12 @@ class TrieNode { return children; } - List<RangerPolicyEvaluator> getPolicies() { - return policies; + List<T> getEvaluators() { + return evaluators; } - List<RangerPolicyEvaluator> getWildcardPolicies() { - return wildcardPolicies; + List<T> getWildcardEvaluators() { + return wildcardEvaluators; } TrieNode getChild(Character c) { @@ -224,18 +249,32 @@ class TrieNode { return ret; } - int getNodeCount() { - int ret = 1; + void populateTrieData(RangerResourceTrie.TrieData trieData) { + trieData.nodeCount++; + + if(wildcardEvaluators != null) { + if(isSharingParentWildcardEvaluators) { + trieData.wildcardEvaluatorListRefCount++; + } else { + trieData.wildcardEvaluatorListCount++; + } + } + + if(evaluators != null) { + if(evaluators == wildcardEvaluators) { + trieData.evaluatorListRefCount++; + } else { + trieData.evaluatorListCount++; + } + } if(children != null) { for(Map.Entry<Character, TrieNode> entry : children.entrySet()) { TrieNode child = entry.getValue(); - ret += child.getNodeCount(); + child.populateTrieData(trieData); } } - - return ret; } int getMaxDepth() { @@ -271,69 +310,91 @@ class TrieNode { return child; } - void addPolicy(RangerPolicyEvaluator evaluator) { - if(policies == null) { - policies = new ArrayList<RangerPolicyEvaluator>(); + void addEvaluator(T evaluator) { + if(evaluators == null) { + evaluators = new ArrayList<T>(); } - if(!policies.contains(evaluator)) { - policies.add(evaluator); + if(!evaluators.contains(evaluator)) { + evaluators.add(evaluator); } } - void addPolicies(List<RangerPolicyEvaluator> evaluators) { - if(CollectionUtils.isNotEmpty(evaluators)) { - for(RangerPolicyEvaluator evaluator : evaluators) { - addPolicy(evaluator); - } + void addWildcardEvaluator(T evaluator) { + if(wildcardEvaluators == null) { + wildcardEvaluators = new ArrayList<T>(); + } + + if(!wildcardEvaluators.contains(evaluator)) { + wildcardEvaluators.add(evaluator); } } - void addWildcardPolicy(RangerPolicyEvaluator evaluator) { - if(wildcardPolicies == null) { - wildcardPolicies = new ArrayList<RangerPolicyEvaluator>(); + void postSetup(List<T> parentWildcardEvaluators) { + // finalize wildcard-evaluators list by including parent's wildcard evaluators + if(parentWildcardEvaluators != null) { + if(CollectionUtils.isEmpty(this.wildcardEvaluators)) { + this.wildcardEvaluators = parentWildcardEvaluators; + } else { + for (T evaluator : parentWildcardEvaluators) { + addWildcardEvaluator(evaluator); + } + } } + this.isSharingParentWildcardEvaluators = wildcardEvaluators == parentWildcardEvaluators; - if(!wildcardPolicies.contains(evaluator)) { - wildcardPolicies.add(evaluator); + // finalize evaluators list by including wildcard evaluators + if(wildcardEvaluators != null) { + if(CollectionUtils.isEmpty(this.evaluators)) { + this.evaluators = wildcardEvaluators; + } else { + for (T evaluator : wildcardEvaluators) { + addEvaluator(evaluator); + } + } } - } - void addWildcardPolicies(List<RangerPolicyEvaluator> evaluators) { - if(CollectionUtils.isNotEmpty(evaluators)) { - for(RangerPolicyEvaluator evaluator : evaluators) { - addWildcardPolicy(evaluator); + if(!isSharingParentWildcardEvaluators && CollectionUtils.isNotEmpty(wildcardEvaluators)) { + Collections.sort(wildcardEvaluators); + } + + if(evaluators != wildcardEvaluators && CollectionUtils.isNotEmpty(evaluators)) { + Collections.sort(evaluators); + } + + if(children != null) { + for(Map.Entry<Character, TrieNode> entry : children.entrySet()) { + TrieNode child = entry.getValue(); + + child.postSetup(wildcardEvaluators); } } } - void postSetup() { - addPolicies(wildcardPolicies); + void reorderEvaluators(List<T> parentWildcardEvaluators) { + boolean isEvaluatorsSameAsWildcardEvaluators = evaluators == wildcardEvaluators; - if(wildcardPolicies != null) { - Collections.sort(wildcardPolicies); + if(isSharingParentWildcardEvaluators) { + wildcardEvaluators = parentWildcardEvaluators; + } else { + wildcardEvaluators = getSortedCopy(wildcardEvaluators); } - if(policies != null) { - Collections.sort(policies); + if(isEvaluatorsSameAsWildcardEvaluators) { + evaluators = wildcardEvaluators; + } else { + evaluators = getSortedCopy(evaluators); } if(children != null) { for(Map.Entry<Character, TrieNode> entry : children.entrySet()) { TrieNode child = entry.getValue(); - child.addWildcardPolicies(wildcardPolicies); - - child.postSetup(); + child.reorderEvaluators(wildcardEvaluators); } } } - void reorderPolicyEvaluators() { - wildcardPolicies = getSortedCopy(wildcardPolicies); - policies = getSortedCopy(policies); - } - public void toString(String prefix, StringBuilder sb) { String nodeValue = prefix; @@ -343,18 +404,18 @@ class TrieNode { sb.append("nodeValue=").append(nodeValue); sb.append("; childCount=").append(children == null ? 0 : children.size()); - sb.append("; policies=[ "); - if(policies != null) { - for(RangerPolicyEvaluator evaluator : policies) { - sb.append(evaluator.getPolicy().getId()).append(" "); + sb.append("; evaluators=[ "); + if(evaluators != null) { + for(T evaluator : evaluators) { + sb.append(evaluator.getId()).append(" "); } } sb.append("]"); - sb.append("; wildcardPolicies=[ "); - if(wildcardPolicies != null) { - for(RangerPolicyEvaluator evaluator : wildcardPolicies) { - sb.append(evaluator.getPolicy().getId()).append(" "); + sb.append("; wildcardEvaluators=[ "); + if(wildcardEvaluators != null) { + for(T evaluator : wildcardEvaluators) { + sb.append(evaluator.getId()).append(" "); } } sb.append("]"); @@ -370,16 +431,16 @@ class TrieNode { } public void clear() { - children = null; - policies = null; - wildcardPolicies = null; + children = null; + evaluators = null; + wildcardEvaluators = null; } - private List<RangerPolicyEvaluator> getSortedCopy(List<RangerPolicyEvaluator> evaluators) { - final List<RangerPolicyEvaluator> ret; + private List<T> getSortedCopy(List<T> evaluators) { + final List<T> ret; if(CollectionUtils.isNotEmpty(evaluators)) { - ret = new ArrayList<RangerPolicyEvaluator>(wildcardPolicies); + ret = new ArrayList<T>(evaluators); Collections.sort(ret); } else {
