This is an automated email from the ASF dual-hosted git repository.
madhan pushed a commit to branch ranger-2.6
in repository https://gitbox.apache.org/repos/asf/ranger.git
The following commit(s) were added to refs/heads/ranger-2.6 by this push:
new a94b31758 RANGER-4893: enhanced trie to support custom handling of
matches
a94b31758 is described below
commit a94b31758eb9d1401aeff30fec9db14e3ee863a8
Author: Madhan Neethiraj <[email protected]>
AuthorDate: Wed Aug 7 21:02:15 2024 -0700
RANGER-4893: enhanced trie to support custom handling of matches
(cherry picked from commit cbc70f69416507c747f74e98c7c7021d083b292e)
---
.../plugin/policyengine/RangerResourceTrie.java | 290 +++++++++++----------
.../util/RangerResourceEvaluatorsRetriever.java | 129 ++++-----
2 files changed, 203 insertions(+), 216 deletions(-)
diff --git
a/agents-common/src/main/java/org/apache/ranger/plugin/policyengine/RangerResourceTrie.java
b/agents-common/src/main/java/org/apache/ranger/plugin/policyengine/RangerResourceTrie.java
index 773a02609..abfc8f0aa 100644
---
a/agents-common/src/main/java/org/apache/ranger/plugin/policyengine/RangerResourceTrie.java
+++
b/agents-common/src/main/java/org/apache/ranger/plugin/policyengine/RangerResourceTrie.java
@@ -37,7 +37,6 @@ import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import java.util.ArrayList;
-import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
@@ -190,29 +189,32 @@ public class RangerResourceTrie<T extends
RangerResourceEvaluator> {
}
}
- public Set<T> getInheritedEvaluators() {
- return inheritedEvaluators;
- }
-
public Set<T> getEvaluatorsForResource(Object resource) {
return getEvaluatorsForResource(resource,
ResourceElementMatchingScope.SELF);
}
- @SuppressWarnings("unchecked")
public Set<T> getEvaluatorsForResource(Object resource,
ResourceElementMatchingScope scope) {
- if (resource instanceof String) {
- return getEvaluatorsForResource((String) resource, scope);
- } else if (resource instanceof Collection) {
- Collection<String> resources = (Collection<String>) resource;
+ EvalCollector<T> ret = new EvalCollector<>();
- if (CollectionUtils.isEmpty(resources)) { // treat empty
collection same as empty-string
- return getEvaluatorsForResource("", scope);
- } else {
- return getEvaluatorsForResources(resources, scope);
- }
- }
+ traverse(resource, scope, ret);
+
+ return ret.getResult();
+ }
+
+ public Set<T> getEvaluatorsForResource(Object resource,
ResourceElementMatchingScope scope, Set<T> filter) {
+ EvalSubsetCollector<T> ret = new EvalSubsetCollector<>(filter);
- return null;
+ traverse(resource, scope, ret);
+
+ return ret.getResult();
+ }
+
+ public int getEvaluatorsCountForResource(Object resource,
ResourceElementMatchingScope scope) {
+ EvalCountCollector<T> ret = new EvalCountCollector<>();
+
+ traverse(resource, scope, ret);
+
+ return ret.getResult();
}
public void add(RangerPolicyResource resource, T evaluator) {
@@ -594,19 +596,38 @@ public class RangerResourceTrie<T extends
RangerResourceEvaluator> {
int prefixLen = getNonWildcardPrefixLength(str);
return (prefixLen < str.length()) ? str.substring(0, prefixLen) : str;
+
}
+ public void traverse(Object resource, ResourceElementMatchingScope scope,
TraverseMatchHandler<T> handler) {
+ if (resource instanceof String) {
+ traverse((String) resource, scope, handler);
+ } else if (resource instanceof Collection) {
+ Collection<String> resources = (Collection<String>) resource;
+ if (CollectionUtils.isEmpty(resources)) { // treat empty
collection same as empty-string
+ traverse("", scope, handler);
+ } else {
+ traverse(resources, scope, handler);
+ }
+ }
+ }
- private Set<T> getEvaluatorsForResource(String resource,
ResourceElementMatchingScope scope) {
+ public void traverse(Collection<String> resources,
ResourceElementMatchingScope scope, TraverseMatchHandler<T> handler) {
+ for (String resource : resources) {
+ traverse(resource, scope, handler);
+ }
+ }
+
+ public void traverse(String resource, ResourceElementMatchingScope scope,
TraverseMatchHandler<T> handler) {
if(LOG.isDebugEnabled()) {
- LOG.debug("==> RangerResourceTrie.getEvaluatorsForResource(" +
resource + ", " + scope + ")");
+ LOG.debug("==> RangerResourceTrie.traverse(" + resource + ", " +
scope + ")");
}
RangerPerfTracer perf = null;
if(RangerPerfTracer.isPerfTraceEnabled(PERF_TRIE_OP_LOG)) {
- perf = RangerPerfTracer.getPerfTracer(PERF_TRIE_OP_LOG,
"RangerResourceTrie.getEvaluatorsForResource(resource=" + resource + ")");
+ perf = RangerPerfTracer.getPerfTracer(PERF_TRIE_OP_LOG,
"RangerResourceTrie.traverse(resource=" + resource + ")");
}
TrieNode<T> curr = root;
@@ -615,14 +636,14 @@ public class RangerResourceTrie<T extends
RangerResourceEvaluator> {
final int len = resource.length();
int i = 0;
- Set<T> accumulatedEvaluators = new HashSet<>();
+ handler.process(inheritedEvaluators);
while (i < len) {
if (!isOptimizedForSpace) {
curr.setupIfNeeded(parent);
} else {
- if (curr.getWildcardEvaluators() != null) {
- accumulatedEvaluators.addAll(curr.getWildcardEvaluators());
+ if (handler.process(curr.getWildcardEvaluators())) {
+ break;
}
}
@@ -646,39 +667,30 @@ public class RangerResourceTrie<T extends
RangerResourceEvaluator> {
if (!isOptimizedForSpace) {
curr.setupIfNeeded(parent);
} else {
- if (curr.getWildcardEvaluators() != null) {
- accumulatedEvaluators.addAll(curr.getWildcardEvaluators());
- }
+ handler.process(curr.getWildcardEvaluators());
}
boolean isSelfMatch = (i == len);
- Set<T> ret;
if (!isOptimizedForSpace) {
- ret = isSelfMatch ? curr.getEvaluators() :
curr.getWildcardEvaluators();
+ handler.process(isSelfMatch ? curr.getEvaluators() :
curr.getWildcardEvaluators());
} else {
if (isSelfMatch) {
- if (curr.getEvaluators() != null) {
- accumulatedEvaluators.addAll(curr.getEvaluators());
- }
+ handler.process(curr.getEvaluators());
}
- ret = accumulatedEvaluators;
}
- final boolean includeChildEvaluators = scope ==
ResourceElementMatchingScope.SELF_OR_CHILD || scope ==
ResourceElementMatchingScope.SELF_OR_PREFIX;
- final Set<T> childEvaluators = includeChildEvaluators ? new
HashSet<>() : null;
-
if (scope == ResourceElementMatchingScope.SELF_OR_CHILD) {
final boolean resourceEndsWithSep =
resource.charAt(resource.length() - 1) == separatorChar;
if (isSelfMatch) { // resource == path(curr)
if (resourceEndsWithSep) { // ex: resource=/tmp/
- curr.getChildren().values().stream().forEach(c ->
c.collectChildEvaluators(separatorChar, 0, childEvaluators));
+ curr.getChildren().values().forEach(c ->
c.collectChildEvaluators(separatorChar, 0, handler));
} else { // ex: resource=/tmp
curr = curr.getChild(separatorChar);
if (curr != null) {
- curr.collectChildEvaluators(separatorChar, 1,
childEvaluators);
+ curr.collectChildEvaluators(separatorChar, 1, handler);
}
}
} else if (child != null) { // resource != path(child) ex:
(resource=/tmp, path(child)=/tmp/test.txt or path(child)=/tmpdir)
@@ -687,31 +699,21 @@ public class RangerResourceTrie<T extends
RangerResourceEvaluator> {
if (isPrefixMatch) {
if (resourceEndsWithSep) { // ex: resource=/tmp/
- child.collectChildEvaluators(separatorChar,
remainingLen, childEvaluators);
+ child.collectChildEvaluators(separatorChar,
remainingLen, handler);
} else if (child.getStr().charAt(remainingLen) ==
separatorChar) { // ex: resource=/tmp
- child.collectChildEvaluators(separatorChar,
remainingLen + 1, childEvaluators);
+ child.collectChildEvaluators(separatorChar,
remainingLen + 1, handler);
}
}
}
} else if (scope == ResourceElementMatchingScope.SELF_OR_PREFIX) {
- curr.collectChildEvaluators(resource, i, childEvaluators);
- }
-
- if (CollectionUtils.isNotEmpty(childEvaluators)) {
- if (CollectionUtils.isNotEmpty(ret)) {
- childEvaluators.addAll(ret);
- }
-
- ret = childEvaluators;
+ curr.collectChildEvaluators(resource, i, handler);
}
RangerPerfTracer.logAlways(perf);
if(LOG.isDebugEnabled()) {
- LOG.debug("<== RangerResourceTrie.getEvaluatorsForResource(" +
resource + ", " + scope + "): evaluators=" + (ret == null ? null :
Arrays.deepToString(ret.toArray())));
+ LOG.debug("<== RangerResourceTrie.traverse(" + resource + ", " +
scope + "): evaluators=" + handler);
}
-
- return ret;
}
private TrieNode<T> getNodeForResource(String resource) {
@@ -757,53 +759,6 @@ public class RangerResourceTrie<T extends
RangerResourceEvaluator> {
return curr;
}
- private Set<T> getEvaluatorsForResources(Collection<String> resources,
ResourceElementMatchingScope scope) {
- if(LOG.isDebugEnabled()) {
- LOG.debug("==> RangerResourceTrie.getEvaluatorsForResources(" +
resources + ")");
- }
-
- Set<T> ret = null;
- Map<Long, T> evaluatorsMap = null;
-
- for (String resource : resources) {
- Set<T> resourceEvaluators = getEvaluatorsForResource(resource,
scope);
-
- if (CollectionUtils.isEmpty(resourceEvaluators)) {
- continue;
- }
-
- if (evaluatorsMap == null) {
- if (ret == null) { // first resource: don't create map yet
- ret = resourceEvaluators;
- } else if (ret != resourceEvaluators) { // if evaluator list
is same as earlier resources, retain the list, else create a map
- evaluatorsMap = new HashMap<>();
-
- for (T evaluator : ret) {
- evaluatorsMap.put(evaluator.getId(), evaluator);
- }
-
- ret = null;
- }
- }
-
- if (evaluatorsMap != null) {
- for (T evaluator : resourceEvaluators) {
- evaluatorsMap.put(evaluator.getId(), evaluator);
- }
- }
- }
-
- if (ret == null && evaluatorsMap != null) {
- ret = new HashSet<>(evaluatorsMap.values());
- }
-
- if(LOG.isDebugEnabled()) {
- LOG.debug("<== RangerResourceTrie.getEvaluatorsForResources(" +
resources + "): evaluatorCount=" + (ret == null ? 0 : ret.size()));
- }
-
- return ret;
- }
-
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
@@ -1229,7 +1184,7 @@ public class RangerResourceTrie<T extends
RangerResourceEvaluator> {
}
}
- void collectChildEvaluators(Character sep, int startIdx, Set<U>
childEvaluators) {
+ void collectChildEvaluators(Character sep, int startIdx,
TraverseMatchHandler<U> handler) {
if (!isOptimizedForSpace) {
setupIfNeeded(getParent());
}
@@ -1238,30 +1193,24 @@ public class RangerResourceTrie<T extends
RangerResourceEvaluator> {
if (sepPos == -1) { // ex: startIdx=5, path(str)=/tmp/test, path(a
child) could be: /tmp/test.txt, /tmp/test/, /tmp/test/a, /tmp/test/a/b
if (isOptimizedForSpace) {
- if (this.wildcardEvaluators != null) {
- childEvaluators.addAll(this.wildcardEvaluators);
- }
- }
- if (this.evaluators != null) {
- childEvaluators.addAll(this.evaluators);
+ handler.process(this.wildcardEvaluators);
}
- children.values().stream().forEach(c ->
c.collectChildEvaluators(sep, 0, childEvaluators));
+ handler.process(this.evaluators);
+
+ children.values().forEach(c -> c.collectChildEvaluators(sep,
0, handler));
} else if (sepPos == (str.length() - 1)) { // ex: str=/tmp/test/,
startIdx=5
if (isOptimizedForSpace) {
- if (this.wildcardEvaluators != null) {
- childEvaluators.addAll(this.wildcardEvaluators);
- }
- }
- if (this.evaluators != null) {
- childEvaluators.addAll(this.evaluators);
+ handler.process(this.wildcardEvaluators);
}
+
+ handler.process(this.evaluators);
}
}
- void collectChildEvaluators(String resource, int startIndex, Set<U>
childEvaluators) {
+ void collectChildEvaluators(String resource, int startIndex,
TraverseMatchHandler<U> handler) {
if (startIndex == resource.length()) {
- collectChildEvaluators(childEvaluators);
+ collectChildEvaluators(handler);
} else if (startIndex < resource.length()) {
Character startChar = getLookupChar(resource, startIndex);
TrieNode<U> childNode = children.get(startChar);
@@ -1275,25 +1224,20 @@ public class RangerResourceTrie<T extends
RangerResourceEvaluator> {
int lenToMatch = Math.min(resource.length() - startIndex,
childStr.length());
if (resource.regionMatches(optIgnoreCase, startIndex,
childStr, 0, lenToMatch)) {
- if (childNode.wildcardEvaluators != null) {
-
childEvaluators.addAll(childNode.wildcardEvaluators);
- }
-
- if (childNode.evaluators != null) {
- childEvaluators.addAll(childNode.evaluators);
- }
+ handler.process(childNode.wildcardEvaluators);
+ handler.process(childNode.evaluators);
if (resource.length() == (startIndex + lenToMatch)) {
- childNode.collectChildEvaluators(childEvaluators);
+ childNode.collectChildEvaluators(handler);
} else {
- childNode.children.values().stream().forEach(c ->
c.collectChildEvaluators(resource, startIndex + childStr.length(),
childEvaluators));
+ childNode.children.values().forEach(c ->
c.collectChildEvaluators(resource, startIndex + childStr.length(), handler));
}
}
}
}
}
- private void collectChildEvaluators(Set<U> childEvaluators) {
+ private void collectChildEvaluators(TraverseMatchHandler<U>
childEvaluators) {
Stack<TrieNode<U>> nodes = new Stack<>();
nodes.addAll(children.values());
@@ -1305,13 +1249,8 @@ public class RangerResourceTrie<T extends
RangerResourceEvaluator> {
childNode.setupIfNeeded(childNode.getParent());
}
- if (childNode.wildcardEvaluators != null) {
- childEvaluators.addAll(childNode.wildcardEvaluators);
- }
-
- if (childNode.evaluators != null) {
- childEvaluators.addAll(childNode.evaluators);
- }
+ childEvaluators.process(childNode.wildcardEvaluators);
+ childEvaluators.process(childNode.evaluators);
nodes.addAll(childNode.children.values());
}
@@ -1381,4 +1320,93 @@ public class RangerResourceTrie<T extends
RangerResourceEvaluator> {
}
}
}
+
+ public interface TraverseMatchHandler<T> {
+ // return: true - stop traverse, processing is complete
+ // false - continue traverse, processing is not complete yet
+ boolean process(Set<T> evaluators);
+ }
+
+ public static class EvalCollector<T> implements TraverseMatchHandler<T> {
+ private Set<T> result;
+ private boolean isOwnedResult = false;
+
+ public EvalCollector() {
+ this.result = null;
+ }
+
+ public Set<T> getResult() {
+ return result;
+ }
+
+ @Override
+ public boolean process(Set<T> evaluators) {
+ if (evaluators != null && !evaluators.isEmpty()) {
+ if (result == null) {
+ result = evaluators;
+ } else {
+ if (!isOwnedResult) {
+ result = new HashSet<>(result);
+
+ isOwnedResult = true;
+ }
+
+ result.addAll(evaluators);
+ }
+ }
+
+ return false; // continue traverse
+ }
+ }
+
+ public static class EvalSubsetCollector<T> implements
TraverseMatchHandler<T> {
+ private final Set<T> filter;
+ private Set<T> result;
+
+ public EvalSubsetCollector(Set<T> filter) {
+ this.filter = filter == null ? Collections.emptySet() : filter;
+ this.result = null;
+ }
+
+ public Set<T> getResult() {
+ return result;
+ }
+
+ @Override
+ public boolean process(Set<T> evaluators) {
+ if (evaluators != null && !evaluators.isEmpty()) {
+ if (result == null) {
+ result = new HashSet<>();
+ }
+
+ intersect(filter, evaluators, result);
+ }
+
+ return result != null && (filter.size() == result.size()); // stop
traverse once the result includes all entries in the filter
+ }
+
+ private static <T> void intersect(Set<T> a, Set<T> b, Set<T> result) {
+ Set<T> smaller = a.size() < b.size() ? a : b;
+ Set<T> larger = smaller == a ? b : a;
+
+ smaller.forEach(item -> { if (larger.contains(item))
result.add(item); });
+ }
+ }
+
+ public static class EvalCountCollector<T> implements
TraverseMatchHandler<T> {
+ private int result = 0;
+
+ public int getResult() {
+ return result;
+ }
+
+ @Override
+ public boolean process(Set<T> evaluators) {
+ if (evaluators != null) {
+ result += evaluators.size();
+ }
+
+ return false; // continue traverse
+ }
+ }
}
diff --git
a/agents-common/src/main/java/org/apache/ranger/plugin/util/RangerResourceEvaluatorsRetriever.java
b/agents-common/src/main/java/org/apache/ranger/plugin/util/RangerResourceEvaluatorsRetriever.java
index 2ba8135b1..69cb4417d 100644
---
a/agents-common/src/main/java/org/apache/ranger/plugin/util/RangerResourceEvaluatorsRetriever.java
+++
b/agents-common/src/main/java/org/apache/ranger/plugin/util/RangerResourceEvaluatorsRetriever.java
@@ -27,11 +27,8 @@ import
org.apache.ranger.plugin.policyresourcematcher.RangerResourceEvaluator;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
-import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
-import java.util.HashSet;
-import java.util.List;
import java.util.Map;
import java.util.Set;
@@ -53,63 +50,63 @@ public class RangerResourceEvaluatorsRetriever {
}
if (MapUtils.isNotEmpty(resourceTrie) &&
MapUtils.isNotEmpty(resource)) {
- Set<String> resourceKeys = resource.keySet();
+ Set<String> resourceKeys = resource.keySet();
+ String resourceWithMinEvals = null;
- List<Evaluators<T>> sortedEvaluators = new
ArrayList<>(resourceKeys.size());
+ if (resourceKeys.size() > 1) {
+ int minEvalCount = 0; // initial value doesn't matter, as the
count for the first resource will be assigned later, in line #70
- for (String resourceDefName : resourceKeys) {
- RangerResourceTrie<T> trie = resourceTrie.get(resourceDefName);
+ for (String resourceDefName : resourceKeys) {
+ RangerResourceTrie<T> trie =
resourceTrie.get(resourceDefName);
- if (trie == null) {
- continue;
- }
+ if (trie == null) {
+ continue;
+ }
- Object resourceValues = resource.get(resourceDefName);
+ Object resourceValues = resource.get(resourceDefName);
- Set<T> inheritedMatchers = trie.getInheritedEvaluators();
- Set<T> matchersForResource =
trie.getEvaluatorsForResource(resourceValues, scopes.get(resourceDefName));
+ int evalCount =
trie.getEvaluatorsCountForResource(resourceValues, scopes.get(resourceDefName));
- if (LOG.isDebugEnabled()) {
- LOG.debug("ResourceDefName:[" + resourceDefName + "],
values:[" + resourceValues + "], resource-matchers:[" + matchersForResource +
"], inherited-matchers:[" + inheritedMatchers + "]");
+ if (resourceWithMinEvals == null || (evalCount <
minEvalCount)) {
+ resourceWithMinEvals = resourceDefName;
+ minEvalCount = evalCount;
+ }
}
- if (CollectionUtils.isEmpty(inheritedMatchers) &&
CollectionUtils.isEmpty(matchersForResource)) {
- sortedEvaluators.clear();
- break;
+ } else if (resourceKeys.size() == 1) { // skip
getEvaluatorsCountForResource() when there is only one resource
+ String resourceKey =
resourceKeys.iterator().next();
+ RangerResourceTrie<T> trie =
resourceTrie.get(resourceKey);
+
+ if (trie != null) {
+ resourceWithMinEvals = resourceKey;
}
- sortedEvaluators.add(new Evaluators<>(inheritedMatchers,
matchersForResource));
}
- if (CollectionUtils.isNotEmpty(sortedEvaluators)) {
- Collections.sort(sortedEvaluators);
+ if (resourceWithMinEvals != null) {
+ RangerResourceTrie<T> trie =
resourceTrie.get(resourceWithMinEvals);
- ret = sortedEvaluators.remove(0).getMatchers();
+ ret =
trie.getEvaluatorsForResource(resource.get(resourceWithMinEvals),
scopes.get(resourceWithMinEvals));
- for (Evaluators<T> evaluators : sortedEvaluators) {
- if (CollectionUtils.isEmpty(evaluators.inheritedMatchers))
{
- ret.retainAll(evaluators.resourceMatchers);
- } else if
(CollectionUtils.isEmpty(evaluators.resourceMatchers)) {
- ret.retainAll(evaluators.inheritedMatchers);
- } else {
- Set<T> smaller = evaluators.getSmaller();
- Set<T> bigger = evaluators.getBigger();
-
- Set<T> tmp = new HashSet<>(ret.size());
-
- if (ret.size() < smaller.size()) {
-
ret.stream().filter(smaller::contains).forEach(tmp::add);
-
ret.stream().filter(bigger::contains).forEach(tmp::add);
- } else {
-
smaller.stream().filter(ret::contains).forEach(tmp::add);
- if (ret.size() < bigger.size()) {
-
ret.stream().filter(bigger::contains).forEach(tmp::add);
- } else {
-
bigger.stream().filter(ret::contains).forEach(tmp::add);
- }
- }
- ret = tmp;
+ for (String resourceDefName : resourceKeys) {
+ if (resourceWithMinEvals.equals(resourceDefName)) {
+ continue;
+ }
+
+ trie = resourceTrie.get(resourceDefName);
+
+ if (trie == null) {
+ continue;
}
- if (ret.isEmpty()) {
+
+ Set<T> evaluators =
trie.getEvaluatorsForResource(resource.get(resourceDefName),
scopes.get(resourceDefName), ret);
+
+ if (CollectionUtils.isEmpty(evaluators)) {
+ ret = Collections.emptySet();
+
break;
+ } else {
+ if (evaluators.size() < ret.size()) {
+ ret = evaluators;
+ }
}
}
}
@@ -118,45 +115,7 @@ public class RangerResourceEvaluatorsRetriever {
if (LOG.isDebugEnabled()) {
LOG.debug("<== RangerResourceEvaluatorsRetriever.getEvaluators(" +
resource + ") : evaluator:[" + ret + "]");
}
- return ret;
- }
-
- static class Evaluators<T> implements Comparable<Evaluators<T>> {
- private final Set<T> inheritedMatchers;
- private final Set<T> resourceMatchers;
- private final Set<T> smaller;
- private final Set<T> bigger;
- private final int size;
-
- Evaluators(Set<T> inherited, Set<T> matched) {
- inheritedMatchers = inherited == null ? Collections.emptySet() :
inherited;
- resourceMatchers = matched == null ? Collections.emptySet() :
matched;
- size = inheritedMatchers.size() +
resourceMatchers.size();
- smaller = inheritedMatchers.size() <
resourceMatchers.size() ? inheritedMatchers : resourceMatchers;
- bigger = smaller == inheritedMatchers ?
resourceMatchers : inheritedMatchers;
- }
-
- // Should be called at most once
- Set<T> getMatchers() {
- Set<T> ret = new HashSet<>(size);
-
- ret.addAll(inheritedMatchers);
- ret.addAll(resourceMatchers);
-
- return ret;
- }
-
- Set<T> getSmaller() {
- return smaller;
- }
- Set<T> getBigger() {
- return bigger;
- }
-
- @Override
- public int compareTo(Evaluators<T> other) {
- return Integer.compare(size, other.size);
- }
+ return ret;
}
}
