Synchronization issues with Template

[thboileau]

Initial ticket : http://restlet.tigris.org/issues/show_bug.cgi?id=881

[thboileau]

initial ticket lost, no more details, let's close this ticket.

[Tembrel]

FWIW, here's what @jlouvel wrote about this (to the "code" listserv) back in September 2009:

Hi guys,

Ivan Gorgiev came across a subtle multi-threading issue as described here:

“Synchronization issues with Template”

It appears that the “double-check locking” pattern that we use in many places in Restlet code doesn’t work reliably in some environments (AMD-64 in his case).

He further points to this web page which worries me:
“The "Double-Checked Locking is Broken" Declaration”

I’d like to get the opinion of concurrency experts in this list to see if we better synchronize all those lazy creation methods instead?

I had been looking at the codebase at that time and had made some comments about concurrency issues in general (probably on #213, contents now lost), but I hadn't noticed a problem like this. I promised to take a look at Template.java back then and, it seems, never did.

I looked just now, and while the concurrency properties aren't explicitly documented, I don't think there's a problem with double-checked locking. The only DCL cases I can find look totally fine (and should work on all Java 6+ platforms):

restlet-framework-java/modules/org.restlet/src/main/java/org/restlet/routing/Template.java

Lines 577 to 589 in 0af3e48

	private List<String> getRegexVariables() {
	// Lazy initialization with double-check.
	List<String> rv = this.regexVariables;
	if (rv == null) {
	synchronized (this) {
	rv = this.regexVariables;
	if (rv == null) {
	this.regexVariables = rv = new CopyOnWriteArrayList<String>();
	}
	}
	}
	return rv;
	}

(Similarly with getRegexPattern.)

I don't know what Ivan Gorgiev meant about not working under AMD-64, and since the original contents of this issue are lost, probably never will.

However, I do see a problem in the parse method:

restlet-framework-java/modules/org.restlet/src/main/java/org/restlet/routing/Template.java

Lines 751 to 752 in 0af3e48

	for (int i = 0; i < getRegexVariables().size(); i++) {
	attributeName = getRegexVariables().get(i);

These repeated calls to getRegexVariables are not done with the synchronization lock held, so it's possible for regexVariables list to be modified during the loop, causing unpredictable parsing behavior, or even an ArrayIndexOutOfBoundsException. This could have been avoided by saving the value returned by getRegexVariables once and using for the whole loop, which is guaranteed to be safe; that was the whole point of using CopyOnWriteArrayList.

(There's an additional problem that getRegexPattern depends on getRegexVariables, so a real fix would involve saving the values of getRegexPattern and getRegexVariables with the lock held first, then releasing the lock and proceeding normally.)

I'm reopening this, but you might prefer to close again and open a new issue, since it's slightly different from the original issue.

[Tembrel]

Corrected comment (original comment below)

The sketch below is broken. The simplest and best fix to parse (and the one I should have mentioned right away) is to wrap the whole try-block with synchronized (this) (or just make the method synchronized).

Additionally:

• As with parse, the format and getVariableNames methods should also be guarded with a synchronized keyword or block. (Any loops over mutable collections, in general, need to be so guarded.)
• The setPattern method should be synchronized.
• Change synchronized (this.variables) to synchronized (this) in setVariables, so that all concurrent access/modification is guarded by the same object. Otherwise a concurrent call to setVariables during parse (or format) could break things.
• My original comment about removing the synchronized keyword from getVariables is still valid.
• My later comment about making regexVariables final is still valid.

Note that even with these changes, the fact that the class publishes access to its mutable collections (getRegexVariables, getVariables), however safely, means that users can't reliably use those collections themselves without synchronizing on the Template instance. (A separate thread could modify entries in variables, for example, during parsing or formatting.) This is unlikely to cause problems in practice, but it's still an undocumented concurrency "policy".

The heart of the problem is that Template is mutable in the first place. As with many of the types in Restlet, it probably should have been designed as an immutable type from the start, using method names like withXXX instead of setXXX to produce new (immutable) instances, but that's by now water under the bridge. I'll try to address this in a comment to (currently closed) issue #213.

Sorry to have muddied the waters so much.

Original comment

Sketch of potential fix:

try {
    Matcher matcher;
    List<String> regexVariables;
    synchronized (this) {
        // Atomically retrieve pattern and variables
        matcher = getRegexPattern().matcher(formattedString);
        regexVariables = getRegexVariables();
    }

    boolean matched = ((getMatchingMode() == MODE_EQUALS) && matcher
            .matches())
            || ((getMatchingMode() == MODE_STARTS_WITH) && matcher
                    .lookingAt());

    if (matched) {
        // Update the number of matched characters
        result = matcher.end();

        // Update the attributes with the variables value
        String attributeName = null;
        String attributeValue = null;

        for (int i = 0; i < regexVariables.size(); i++) {
            attributeName = regexVariables.get(i);
            attributeValue = matcher.group(i + 1);
            Variable var = variables.get(attributeName);

            if ((var != null) && var.isDecodingOnParse()) {
                attributeValue = Reference.decode(attributeValue);
            }

            if (loggable) {
                getLogger().fine(
                        "Template variable \"" + attributeName
                                + "\" matched with value \""
                                + attributeValue + "\"");
            }

            variables.put(attributeName, attributeValue);
        }
    }
...

Also, there is no need for the getVariables method to be synchronized, as it just returns a final variable.

[Tembrel]

Also, even though the double-checked locking is correct here, I see no compelling reason to initialize regexVariables lazily. It would be simpler to make it a final field and initialize it as:

    private final List<String> regexVariables = new CopyOnWriteArrayList<>();

One less volatile field to think about.