Concurrency issue when comparing MediaType#parameters

[thboileau]

Encountered Deadlock in the org.restlet.data.MediaType class while comparing the parameters:
https://github.com/restlet/restlet-framework-java/blob/2.3/modules/org.restlet/src/org/restlet/data/MediaType.java#L965

Noticed that two threads where comparing the two same media types but in distinct order. The deadlock is caused by the fact that WrapperList relies on the Vector class and that each thread locks one list of parameters and wait for the other when comparing it.

[thboileau]

We think that one fix is to replace the Vector class by CopyOnWriteArrayList. By doing so, the read and write won't be concurrent.
One drawback is that read don't wait for current writes. It can cause troubles in cases where the list is updated and read frequently.

In order to have the impacts in mind.
Some classes already use the WrapperList with CopyOnWriteArrayList class:

• list of client and server connectors
• list of routes (routers and virtual hosts)
• list of services (applications and components)

=> These cases are not impacted.

Some classes leverages the WrapperList with Vector class for some of their attributes:

• EncodeRepresentation.encodings
• Variant.encodings
• Variant.languages

=> We think that these cases are moderately risky

Two classes inherits from WrapperList and require more attention:

• Form
• Series

Here are the places where the Series class is leveraged (only the code module and the html extension used in APISpark have bee studied):

• org.restlet.Response cookieSettings attribute of type Series<CookieSetting>
• org.restlet.engine.header.PreferenceReader parsing of Accept header Series<<Parameter>
• org.restlet.engine.header.ContentTypeReader parsing of Content-type header Series<Parameter>
• org.restlet.engine.RestletHelper parameters of a helper Series<Parameter>
• org.restlet.engine.adapter.Call request and response headers Series<Header>
• org.restlet.Context parameters attribute of type Series<Parameter>
• org.restlet.Message request and response headers Series<Header>
• org.restlet.security.Realm.java parameters attribute of type Series<Parameter>
• org.restlet.data.Preference parameters attribute of type Series<Parameter>
• org.restlet.data.ChallengeMessage parameters attribute of type Series<Parameter>
• org.restlet.data.Disposition parameters attribute of type Series<Parameter>
• org.restlet.data.MediaType parameters attribute of type Series<Parameter>
• org.restlet.Request.java cookies attribute of type Series<Cookie>
• org.restlet.ext.html.FormDataSet entries attribute of type Series<FormData>
• org.restlet.ext.html.internal.FormReader parsing of multi part entity Series<FormData>

We don't think that in these cases, the list are updated and read frequently.

[thboileau]

Hello @Tembrel , I wonder if you have any piece of advice.
Do you think we should have a closer look of the impacts? Do you think replacing Vector class by CopyOnWriteArrayList is a good thing?
Aside from this topic, I think I will take care also of this ticket #1175.

[Tembrel]

@thboileau - I don't fully understand this comment:

One drawback is that read don't wait for current writes. It can cause troubles in cases where the list is updated and read frequently.

Are you worried about performance or correctness here? I'll respond to both possibilities.

Performance

It's true that CopyOnWriteArrayList performs best in write-seldom-read-often settings, because each write allocates and copies a new array. But I don't think this becomes a performance issue unless you're dealing with large arrays under frequent modification, and the uses that Thierry mentions are all likely to be fairly small.

But if stress testing reveals problems with CopyOnWriteArrayList, then I'd recommend that WrapperList be rewritten to manage synchronization itself, perhaps with ReadWriteLock on an ArrayList.

Correctness

The fact that, in CopyOnWriteArrayList, writes don't block readers means that consecutive reads can see different states of the list. But this is potentially a problem already with WrapperList, since it doesn't provide any mechanism to do multiple reads atomically.

But I'd argue that it's not good practice to rely on the state of a WrapperList not changing between reads, and that any code that absolutely must do this should use toArray to get an unshared snapshot of the state.

[Tembrel]

For a quick fix to the deadlock problem, though, consider this change to WrapperList#equals:

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }

        if (o instanceof List) {
            List<?> that = (List<?>) o;
            return Arrays.equals(this.toArray(), that.toArray());
        }

        return false;
    }
}

You could get really fancy trying to order the calls to avoid deadlock, but since you in general don't know the implementation of the delegate, it wouldn't protect against all possibilities. This simple solution is probably best, even with the expense of allocating and copying arrays.

[thboileau]

Hello @Tembrel
many thanks for your answer
@jlouvel what do you think of Tim's proposal?

[jlouvel]

@Tembrel Thanks a lot for the great insights. I like the equals() solution.
@thboileau I think we should go with this solution first.

[thboileau]

The fix is now part of the 2.3 branch, and will be shipped with the 2.3.8 version.