Skip to content

Commit

Permalink
Rewrite recursive guard and wire it up.
Browse files Browse the repository at this point in the history
The old recursion guard (ported from MRI years ago) had a number
of flaws:

* It forced an object ID for every object encountered.
* It created transient objects for every recursive stack.
* It was not using identity hashing (#3887).
* It used a RubyHash internally, which has much more overhead than
  a typical JDK Map.

The new implementation largely follows the pattern of the original
but fixes all the above items. It passes all untagged specs.

See also #3884, which started this whole thing.
headius committed May 18, 2016
1 parent 455fce1 commit dc7c489
Showing 6 changed files with 175 additions and 55 deletions.
63 changes: 63 additions & 0 deletions core/src/main/java/org/jruby/Ruby.java
Original file line number Diff line number Diff line change
@@ -4437,6 +4437,69 @@ private IRubyObject execRecursiveInternal(RecursiveFunction func, IRubyObject ob
}
}

ThreadLocal<Map<String, Map<IRubyObject, IRubyObject>>> symMap = new ThreadLocal<>();

public IRubyObject safeRecurse(RecursiveFunction func, IRubyObject obj, String name, boolean outer) {
Map<IRubyObject, IRubyObject> guards = safeRecurseGetGuards(name);

boolean outermost = outer && !guards.containsKey(recursiveKey);

// check guards
if (guards.containsKey(obj)) {
if (outer && !outermost) {
throw new RecursiveError(guards);
}
return func.call(obj, true);
} else {
if (outermost) {
return safeRecurseOutermost(func, obj, guards);
} else {
return safeRecurseInner(func, obj, guards);
}
}
}

private IRubyObject safeRecurseOutermost(RecursiveFunction func, IRubyObject obj, Map<IRubyObject, IRubyObject> guards) {
boolean recursed = false;
guards.put(recursiveKey, recursiveKey);

try {
return safeRecurseInner(func, obj, guards);
} catch (RecursiveError re) {
if (re.tag != guards) {
throw re;
}
recursed = true;
guards.remove(recursiveKey);
return func.call(obj, true);
} finally {
if (!recursed) guards.remove(recursiveKey);
}
}

private Map<IRubyObject, IRubyObject> safeRecurseGetGuards(String name) {
Map<String, Map<IRubyObject, IRubyObject>> symToGuards = symMap.get();
if (symToGuards == null) {
symToGuards = new HashMap<>();
symMap.set(symToGuards);
}

Map<IRubyObject, IRubyObject> guards = symToGuards.get(name);
if (guards == null) {
guards = new IdentityHashMap<>();
symToGuards.put(name, guards);
} return guards;
}

private IRubyObject safeRecurseInner(RecursiveFunction func, IRubyObject obj, Map<IRubyObject, IRubyObject> guards) {
try {
guards.put(obj, obj);
return func.call(obj, false);
} finally {
guards.remove(obj);
}
}

/**
* Perform a recursive walk on the given object using the given function.
*
55 changes: 25 additions & 30 deletions core/src/main/java/org/jruby/RubyArray.java
Original file line number Diff line number Diff line change
@@ -76,9 +76,10 @@

import static org.jruby.RubyEnumerator.enumeratorize;
import static org.jruby.RubyEnumerator.enumeratorizeWithSize;
import static org.jruby.runtime.Helpers.hashEnd;
import static org.jruby.runtime.Helpers.invokedynamic;
import static org.jruby.runtime.Helpers.murmurCombine;
import static org.jruby.runtime.Visibility.PRIVATE;
import static org.jruby.runtime.invokedynamic.MethodNames.HASH;
import static org.jruby.runtime.invokedynamic.MethodNames.OP_CMP;
import static org.jruby.RubyEnumerator.SizeFn;

@@ -676,25 +677,23 @@ public RubyFixnum hash19(ThreadContext context) {
*
*/
@JRubyMethod(name = "hash")
public RubyFixnum hash(final ThreadContext context) {
return (RubyFixnum) context.runtime.execRecursiveOuter(new Ruby.RecursiveFunction() {
public IRubyObject call(IRubyObject obj, boolean recur) {
final Ruby runtime = context.runtime;
int begin = RubyArray.this.begin;
long h = realLength;
h ^= System.identityHashCode(RubyArray.class);
if (recur) {
h ^= h * 31 + RubyNumeric.num2long(invokedynamic(context, runtime.getArray(), HASH));
} else {
for (int i = begin; i < begin + realLength; i++) {
h = (h << 1) | (h < 0 ? 1 : 0);
final IRubyObject value = safeArrayRef(runtime, values, i);
h ^= h * 31 + RubyNumeric.num2long(invokedynamic(context, value, HASH));
}
}
return runtime.newFixnum(h);
}
}, RubyArray.this);
public RubyFixnum hash(ThreadContext context) {
Ruby runtime = context.runtime;

int begin = RubyArray.this.begin;
long h = Helpers.hashStart(runtime, realLength);

h = Helpers.murmurCombine(h, System.identityHashCode(RubyArray.class));

for (int i = begin; i < begin + realLength; i++) {
IRubyObject value = safeArrayRef(runtime, values, i);
RubyFixnum n = Helpers.safeHash(context, value);
h = murmurCombine(h, n.getLongValue());
}

h = hashEnd(h);

return runtime.newFixnum(h);
}

/** rb_ary_store
@@ -1765,15 +1764,15 @@ private void recursiveJoin(final ThreadContext context, final IRubyObject outVal

if (ary == this) throw runtime.newArgumentError("recursive array join");

runtime.execRecursive(new Ruby.RecursiveFunction() {
runtime.safeRecurse(new Ruby.RecursiveFunction() {
public IRubyObject call(IRubyObject obj, boolean recur) {
if (recur) throw runtime.newArgumentError("recursive array join");

RubyArray recAry = ((RubyArray) ary);
recAry.joinAny(context, outValue, sep, recAry.begin, result);

return runtime.getNil();
}}, outValue);
}}, outValue, "join", true);
}

/** rb_ary_join
@@ -1799,15 +1798,11 @@ public IRubyObject join19(final ThreadContext context, IRubyObject sep) {
IRubyObject tmp = val.checkStringType19();
if (tmp.isNil() || tmp != val) {
len += ((begin + realLength) - i) * 10;
final RubyString result = (RubyString) RubyString.newStringLight(runtime, len, USASCIIEncoding.INSTANCE).infectBy(this);
final RubyString sepStringFinal = sepString;
final int iFinal = i;
RubyString result = (RubyString) RubyString.newStringLight(runtime, len, USASCIIEncoding.INSTANCE).infectBy(this);
RubyString sepStringFinal = sepString;
int iFinal = i;

return runtime.recursiveListOperation(new Callable<IRubyObject>() {
public IRubyObject call() {
return joinAny(context, RubyArray.this, sepStringFinal, iFinal, joinStrings(sepStringFinal, iFinal, result));
}
});
return joinAny(context, RubyArray.this, sepStringFinal, iFinal, joinStrings(sepStringFinal, iFinal, result));
}

len += ((RubyString) tmp).getByteList().length();
26 changes: 10 additions & 16 deletions core/src/main/java/org/jruby/RubyHash.java
Original file line number Diff line number Diff line change
@@ -1241,24 +1241,18 @@ public IRubyObject op_ge(ThreadContext context, IRubyObject other) {
@JRubyMethod(name = "hash")
public RubyFixnum hash() {
final Ruby runtime = getRuntime();
if (size == 0) return RubyFixnum.zero(runtime);
final ThreadContext context = runtime.getCurrentContext();
return (RubyFixnum) runtime.execRecursiveOuter(new Ruby.RecursiveFunction() {
@Override
public IRubyObject call(IRubyObject obj, boolean recur) {
if (recur) {
return invokedynamic(context, runtime.getHash(), HASH).convertToInteger();
final long[] hval = {Helpers.hashStart(runtime, size())};
if (size > 0) {
iteratorVisitAll(new Visitor() {
@Override
public void visit(IRubyObject key, IRubyObject value) {
hval[0] += Helpers.safeHash(context, key).convertToInteger().getLongValue()
^ Helpers.safeHash(context, value).convertToInteger().getLongValue();
}
final long[] h = new long[]{1};
visitAll(new Visitor() {
@Override
public void visit(IRubyObject key, IRubyObject value) {
h[0] += invokedynamic(context, key, HASH).convertToInteger().getLongValue() ^ invokedynamic(context, value, HASH).convertToInteger().getLongValue();
}
});
return runtime.newFixnum(h[0]);
}
}, this);
});
}
return runtime.newFixnum(hval[0]);
}

@Deprecated
12 changes: 4 additions & 8 deletions core/src/main/java/org/jruby/RubyStruct.java
Original file line number Diff line number Diff line change
@@ -586,15 +586,11 @@ public RubyString inspect(final ThreadContext context) {
final Ruby runtime = context.runtime;
final RubyStruct struct = this;
// recursion guard
return runtime.recursiveListOperation(new Callable<RubyString>() {
public RubyString call() {
return (RubyString) runtime.execRecursive(new Ruby.RecursiveFunction() {
public IRubyObject call(IRubyObject obj, boolean recur) {
return inspectStruct(context, recur);
}
}, struct);
return (RubyString) runtime.safeRecurse(new Ruby.RecursiveFunction() {
public IRubyObject call(IRubyObject obj, boolean recur) {
return inspectStruct(context, recur);
}
});
}, struct, "inspect", false);
}

@JRubyMethod(name = {"to_a", "values"})
72 changes: 72 additions & 0 deletions core/src/main/java/org/jruby/runtime/Helpers.java
Original file line number Diff line number Diff line change
@@ -34,6 +34,7 @@
import org.jruby.runtime.invokedynamic.MethodNames;
import org.jruby.util.ByteList;
import org.jruby.util.DefinedMessage;
import org.jruby.util.MurmurHash;
import org.jruby.util.TypeConverter;

import java.util.ArrayList;
@@ -48,7 +49,9 @@
import org.jcodings.specific.UTF8Encoding;
import org.jcodings.unicode.UnicodeEncoding;

import static org.jruby.runtime.Helpers.invokedynamic;
import static org.jruby.runtime.invokedynamic.MethodNames.EQL;
import static org.jruby.runtime.invokedynamic.MethodNames.HASH;
import static org.jruby.runtime.invokedynamic.MethodNames.OP_EQUAL;
import static org.jruby.util.CodegenUtils.sig;
import static org.jruby.util.StringSupport.EMPTY_STRING_ARRAY;
@@ -2714,6 +2717,75 @@ public static boolean isRequiredKeywordArgumentValueNode(Node asgnNode) {
return asgnNode.childNodes().get(0) instanceof RequiredKeywordArgumentValueNode;
}

// MRI: rb_hash_start
public static long hashStart(Ruby runtime, long value) {
long hash = value +
(runtime.isSiphashEnabled() ?
runtime.getHashSeedK1() :
runtime.getHashSeedK0());
return hash;
}

public static long hashEnd(long value) {
value = murmur_step(value, 10);
value = murmur_step(value, 17);
return value;
}

// MRI: rb_hash
public static RubyFixnum safeHash(final ThreadContext context, IRubyObject obj) {
final Ruby runtime = context.runtime;
IRubyObject hval = runtime.safeRecurse(new Ruby.RecursiveFunction() {
public IRubyObject call(IRubyObject obj, boolean recur) {
if (recur) return RubyFixnum.zero(runtime);
return invokedynamic(context, obj, HASH);
}
}, obj, "hash", true);

while (!(hval instanceof RubyFixnum)) {
if (hval instanceof RubyBignum) {
// This is different from MRI because we don't have rb_integer_pack
return ((RubyBignum) hval).hash();
}
hval = hval.convertToInteger();
}

return (RubyFixnum) hval;
}

public static long murmurCombine(long h, long i)
{
long v = 0;
h += i;
v = murmur1(v + h);
v = murmur1(v + (h >>> 4*8));
return v;
}

public static long murmur(long h, long k, int r)
{
long m = MurmurHash.MURMUR2_MAGIC;
h += k;
h *= m;
h ^= h >> r;
return h;
}

public static long murmur_finish(long h)
{
h = murmur(h, 0, 10);
h = murmur(h, 0, 17);
return h;
}

public static long murmur_step(long h, long k) {
return murmur((h), (k), 16);
}

public static long murmur1(long h) {
return murmur_step(h, 16);
}

@Deprecated
public static String encodeParameterList(List<String[]> args) {
if (args.size() == 0) return "NONE";
2 changes: 1 addition & 1 deletion core/src/main/java/org/jruby/util/MurmurHash.java
Original file line number Diff line number Diff line change
@@ -15,7 +15,7 @@ public class MurmurHash {

// 'm' and 'r' are mixing constants generated offline.
// They're not really 'magic', they just happen to work well.
private static final int MURMUR2_MAGIC = 0x5bd1e995;
public static final int MURMUR2_MAGIC = 0x5bd1e995;
// CRuby 1.9 uses 16 but original C++ implementation uses 24 with above Magic.
private static final int MURMUR2_R = 24;

0 comments on commit dc7c489

Please sign in to comment.