code review request: 7118809: rcache deadlock

[Valerie (Yu-Ching) Peng]

Ok, I have no other comments.
Thanks,
Valerie

On 01/12/12 20:57, Weijun Wang wrote:
> Hi Valerie
>
> Here are the updated webrevs:
>
>  for 8: http://cr.openjdk.java.net/~weijun/7118809/webrev.01/
>  for 7u4: http://cr.openjdk.java.net/~weijun/7118809/7u4/webrev.00/
>
> I've added a function test. If CacheTable does not add the 
> ReplayCache, the test would fail. No real regression test for this 
> particular bug because of noreg-hard.
>
> Thanks
> Max
>
>
> On 01/13/2012 09:58 AM, Valerie (Yu-Ching) Peng wrote:
>>
>> Ok.
>> Thanks,
>> Valerie
>>
>> On 01/12/12 17:46, Weijun Wang wrote:
>>> How about this? We remove the empty ReplayCache in JDK 8 but keep it
>>> in 7u4 (I want to backport it). I just feel there is a hidden monster
>>> somewhere.
>>>
>>> Thanks
>>> Max
>>>
>>> On 01/13/2012 07:20 AM, Valerie (Yu-Ching) Peng wrote:
>>>>
>>>> Secret use?
>>>> As far as I can see, the CacheTable.put(...) method handles the case
>>>> where an ReplayCache object isn't found and I can't think of any 
>>>> secret
>>>> use for this.
>>>> It looks to me that cleaning this up is only an internal impl of
>>>> CacheTable class and should not affect its behavior.
>>>> Removing an empty Cache seems more correct than leaving it there.
>>>> Thanks,
>>>> Valerie
>>>>
>>>> On 01/11/12 22:11, Weijun Wang wrote:
>>>>>> In addition, I think the CacheTable.put(...) method should check if
>>>>>> the
>>>>>> ReplayCache object is empty and if yes, do the removal itself.
>>>>>> So, the cleanup of empty ReplayCache object is still done, except 
>>>>>> it's
>>>>>> now in CacheTable class instead of ReplayCache class which leads to
>>>>>> the
>>>>>> deadlock.
>>>>>
>>>>> That was my original plan. But I have no idea why in CacheTable
>>>>> there is
>>>>>
>>>>> // re-insert the entry, since rc.put could have removed the entry
>>>>>
>>>>> Does it really have a secret use?
>>>>>
>>>>>>
>>>>>> Lastly, not really relevant to your changes here, but the code in 
>>>>>> both
>>>>>> classes doesn't seem too efficient and some even looks not quite
>>>>>> correct.
>>>>>> For example, the impl of ReplayCache.put(...) method first goes
>>>>>> through
>>>>>> the LinkList and insert authenticator timestamp in descending order
>>>>>> and
>>>>>> then going through it again removing the expired timestamps.
>>>>>> Wouldn't it
>>>>>> be better to revert the order or doing both together, i.e. check for
>>>>>> expiration and find the indexing while going through the list once?
>>>>>
>>>>> Maybe.
>>>>>
>>>>> Thanks
>>>>> Max
>>>>>
>>>>>>
>>>>>> Thanks,
>>>>>> Valerie
>>>>>>
>>>>>> On 01/09/12 21:41, Weijun Wang wrote:
>>>>>>> Hi Valerie
>>>>>>>
>>>>>>> Please review my fix:
>>>>>>>
>>>>>>> http://cr.openjdk.java.net/~weijun/7118809/webrev.00/
>>>>>>>
>>>>>>> Basically, CacheTable.put() operates on ReplayCache inside it, and
>>>>>>> ReplayCache.put() operates on CacheTable containing it, and both
>>>>>>> methods are synchronized and using thread-safe Hashtable.
>>>>>>>
>>>>>>> My solution is to move the "table.remove(principal)" line in
>>>>>>> ReplayCache.put() outside the method. I search thru JDK and
>>>>>>> CacheTable.put() is the only place the method is called:
>>>>>>>
>>>>>>> public synchronized void put(String principal, AuthTime time, long
>>>>>>> currTime) {
>>>>>>> ReplayCache rc = super.get(principal);
>>>>>>> if (rc == null) {
>>>>>>> if (DEBUG) {
>>>>>>> System.out.println("replay cache for " + principal + "
>>>>>>> is null.");
>>>>>>> }
>>>>>>> rc = new ReplayCache(principal, this);
>>>>>>> rc.put(time, currTime);
>>>>>>> super.put(principal, rc);
>>>>>>> }
>>>>>>> else {
>>>>>>> rc.put(time, currTime);
>>>>>>> // re-insert the entry, since rc.put could have removed
>>>>>>> the entry
>>>>>>> super.put(principal, rc);
>>>>>>> if (DEBUG) {
>>>>>>> System.out.println("replay cache found.");
>>>>>>> }
>>>>>>> }
>>>>>>> }
>>>>>>>
>>>>>>> Curiously, you can see after each call, the ReplayCache object is
>>>>>>> added back into the CacheTable. Therefore, the remove action is
>>>>>>> useless.
>>>>>>>
>>>>>>> Maybe the most correct way is to remove a ReplayCache from a
>>>>>>> CacheTable if it's empty, but that re-insert line was added in a
>>>>>>> security fix some years ago which I cannot decipher.
>>>>>>>
>>>>>>> So my fix simply removes the "remove" call in ReplayCache.
>>>>>>>
>>>>>>> No regression test, hard to reproduce failure.
>>>>>>>
>>>>>>> Thanks
>>>>>>> Max
>>>>>>>
>>>>>>> -------- Original Message --------
>>>>>>> *Change Request ID*: 7118809
>>>>>>> *Synopsis*: rcache deadlock
>>>>>>>
>>>>>>> === *Description*
>>>>>>> ============================================================
>>>>>>> A DESCRIPTION OF THE PROBLEM :
>>>>>>> The program as below:
>>>>>>> --------------------------------------------------
>>>>>>> import sun.security.krb5.internal.rcache.*;
>>>>>>> import sun.security.krb5.internal.*;
>>>>>>> import java.util.*;
>>>>>>>
>>>>>>> public class KTest2 {
>>>>>>> public static void main(String [] a) throws Exception{
>>>>>>> final CacheTable ct = new CacheTable();
>>>>>>> final long time = System.currentTimeMillis();
>>>>>>> ct.put("TheOnlyOne", new AuthTime( time -
>>>>>>> Krb5.DEFAULT_ALLOWABLE_CLOCKSKEW * 1000L, 0), time);
>>>>>>> final ReplayCache rc = (ReplayCache) ct.get("TheOnlyOne");
>>>>>>> new Thread() {
>>>>>>> public void run() {
>>>>>>> rc.put(new AuthTime( time - Krb5.DEFAULT_ALLOWABLE_CLOCKSKEW *
>>>>>>> 1000L, 0), time + 300*1000);
>>>>>>> }
>>>>>>> }.start();
>>>>>>> ct.put("TheOnlyOne", new AuthTime( time -
>>>>>>> Krb5.DEFAULT_ALLOWABLE_CLOCKSKEW * 1000L, 0), time);
>>>>>>> }
>>>>>>> }
>>>>>>> --------------------------------------------------
>>>>>>> When compiles as in: javac KTest2.java
>>>>>>> and executed as in: java KTest2
>>>>>>> can deadlock the hosting JVM as is reproduced by the stack-trace
>>>>>>> dump,
>>>>>>> below:
>>>>>>> -------------------------------------------------
>>>>>>> Found one Java-level deadlock:
>>>>>>> =============================
>>>>>>> "Thread-0":
>>>>>>> waiting to lock monitor 0x0921d720 (object 0xa5621b80, a
>>>>>>> sun.security.krb5.internal.rcache.CacheTable),
>>>>>>> which is held by "main"
>>>>>>> "main":
>>>>>>> waiting to lock monitor 0x0921caa0 (object 0xa5622fb8, a
>>>>>>> sun.security.krb5.internal.rcache.ReplayCache),
>>>>>>> which is held by "Thread-0"
>>>>>>>
>>>>>>> Java stack information for the threads listed above:
>>>>>>> ===================================================
>>>>>>> "Thread-0":
>>>>>>> at java.util.Hashtable.remove(Hashtable.java:435)
>>>>>>> - waiting to lock<0xa5621b80> (a
>>>>>>> sun.security.krb5.internal.rcache.CacheTable)
>>>>>>> at
>>>>>>> sun.security.krb5.internal.rcache.ReplayCache.put(ReplayCache.java:123) 
>>>>>>>
>>>>>>>
>>>>>>> - locked<0xa5622fb8> (a
>>>>>>> sun.security.krb5.internal.rcache.ReplayCache)
>>>>>>> at KTest2$1.run(KTest2.java:13)
>>>>>>> "main":
>>>>>>> at
>>>>>>> sun.security.krb5.internal.rcache.ReplayCache.put(ReplayCache.java:62) 
>>>>>>>
>>>>>>>
>>>>>>> - waiting to lock<0xa5622fb8> (a
>>>>>>> sun.security.krb5.internal.rcache.ReplayCache)
>>>>>>> at
>>>>>>> sun.security.krb5.internal.rcache.CacheTable.put(CacheTable.java:59) 
>>>>>>>
>>>>>>> - locked<0xa5621b80> (a
>>>>>>> sun.security.krb5.internal.rcache.CacheTable)
>>>>>>> at KTest2.main(KTest2.java:16)
>>>>>>>
>>>>>>> Found 1 deadlock.
>>>>>>> ...
>>>>>>>
>>>>>>
>>>>
>>>>
>>