New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Locking Problem with Lazy Striped ReadWriteLocks #2477

Closed
dobermai opened this Issue May 12, 2016 · 12 comments

Comments

Projects
None yet
8 participants
@dobermai

dobermai commented May 12, 2016

We're seeing a behaviour of a Striped.lazyReadWriteLock that seem to break the documented behaviour that for the same key the same lock will be returned. Is there something obvious we're missing or misunderstood about the lazy Striped Locks? When using eager Locks, everything works as expected.

The following test reproduces the behaviour.

public class MyTest {

    private final Striped<ReadWriteLock> stripedLock = Striped.lazyWeakReadWriteLock(64);
    private final AtomicBoolean writeLocked = new AtomicBoolean(false);
    private final Set<String> someSet = new HashSet<>();
    private final Random random = new Random();

    private final String key = "anyKey";

    @Test
    public void test() throws Exception {
        final ExecutorService executorService = Executors.newCachedThreadPool();
        final AtomicBoolean testFailed = new AtomicBoolean(false);

        for (int i = 0; i < 1000000; i++) {
            someSet.add("" + i);
        }

        for (int i = 0; i < 10; i++) {

            executorService.submit(new Runnable() {
                @Override
                public void run() {
                    try {
                        while (!testFailed.get()) {
                            if (random.nextBoolean()) {
                                writeLockedMethod();
                            } else {
                                readLockedMethod();
                            }
                        }
                    } catch (AssertionError e) {
                        e.printStackTrace();
                        testFailed.set(true);
                    }
                }
            });
        }

        while (!testFailed.get()) {
            Thread.sleep(1000);
        }
        fail();
    }

    private void readLockedMethod() {
        final Lock readLock = stripedLock.get(key).readLock();
        readLock.lock();
        assertFalse(writeLocked.get());
        try {
            someSet.contains("" + random.nextInt(1000000)); //Just do something.
        } finally {
            readLock.unlock();
        }
    }

    private void writeLockedMethod() {
        final Lock writeLock = stripedLock.get(key).writeLock();
        writeLock.lock();
        //Since the atomic boolean is set inside the write lock, for the same key, this should never be true.
        assertFalse(Thread.currentThread().getName(),writeLocked.get());
        writeLocked.getAndSet(true);
        try {
            someSet.contains("" + random.nextInt(1000000)); //Just do something.
        } finally {
            writeLocked.getAndSet(false);
            writeLock.unlock();
        }
    }
}
@navkast

This comment has been minimized.

Show comment
Hide comment
@navkast

navkast Jan 9, 2017

This is something I'm seeing as well.

navkast commented Jan 9, 2017

This is something I'm seeing as well.

@FoKas90

This comment has been minimized.

Show comment
Hide comment
@FoKas90

FoKas90 Oct 16, 2017

I had same problem with .lazyWeakReadWriteLock(int) in 20.0 version

FoKas90 commented Oct 16, 2017

I had same problem with .lazyWeakReadWriteLock(int) in 20.0 version

@lowasser

This comment has been minimized.

Show comment
Hide comment
@lowasser

lowasser Oct 16, 2017

Contributor

As surprising as this behavior is, I think it's...technically...spec-compliant. Took me a couple minutes to figure it out. That doesn't mean it's not unacceptably surprising, or fixable, though.

The issue isn't the laziness, it's the weak part. The lock is weakly referenced by the Striped; it says so in the "weak" part of the method name.

The issue is that those two methods of yours don't hold on to the ReadWriteLock itself. They hold on to the read lock and to the write lock. Separately. And those don't hold references back to the ReadWriteLock. So the ReadWriteLock is eligible for garbage collection in the middle of the method, and a new one gets generated the next time someone asks for it, and since it's not the same lock they interoperate at the same time.

That said: that's an artifact of the Java implementation of ReentrantReadWriteLock, that the read and write locks don't actually hold references back to the shared lock object they came from. And it makes lazyWeakReadWriteLock almost useless. So I think the proper thing to do is, in fact, to return not a ReentrantReadWriteLock but a thin wrapper that makes sure the read and write locks hold references to the ReadWriteLock they came from.

Contributor

lowasser commented Oct 16, 2017

As surprising as this behavior is, I think it's...technically...spec-compliant. Took me a couple minutes to figure it out. That doesn't mean it's not unacceptably surprising, or fixable, though.

The issue isn't the laziness, it's the weak part. The lock is weakly referenced by the Striped; it says so in the "weak" part of the method name.

The issue is that those two methods of yours don't hold on to the ReadWriteLock itself. They hold on to the read lock and to the write lock. Separately. And those don't hold references back to the ReadWriteLock. So the ReadWriteLock is eligible for garbage collection in the middle of the method, and a new one gets generated the next time someone asks for it, and since it's not the same lock they interoperate at the same time.

That said: that's an artifact of the Java implementation of ReentrantReadWriteLock, that the read and write locks don't actually hold references back to the shared lock object they came from. And it makes lazyWeakReadWriteLock almost useless. So I think the proper thing to do is, in fact, to return not a ReentrantReadWriteLock but a thin wrapper that makes sure the read and write locks hold references to the ReadWriteLock they came from.

@cpovirk

This comment has been minimized.

Show comment
Hide comment
@cpovirk
Member

cpovirk commented Oct 16, 2017

@cpovirk cpovirk closed this Oct 16, 2017

@cpovirk cpovirk added this to the NEXT milestone Oct 16, 2017

@cpovirk cpovirk added status=fixed and removed status=triaged labels Oct 16, 2017

@Maaartinus

This comment has been minimized.

Show comment
Hide comment
@Maaartinus

Maaartinus Oct 16, 2017

@cpovirk

Would you consider to make the WeakSafeReadWriteLock public? I use a similar thing to Striped#lazyWeakReadWriteLock, just without the striping.

Shouldn't this be fixed in the JDK? Just removing the static modifier of the nested classes would do. We could argue that the nested locks need no reference to the enclosing class, but this issue shows it's actually needed.

I had an idea of simply extending all three involved locks and overriding the readLock and writeLock getters, making the original locks unused. Your fix is cleaner, but it's more than ten times longer. It might perform worse because CHA for Condition and overridden methods deeper in the call hierarchy tree. Just guessing.

Maaartinus commented Oct 16, 2017

@cpovirk

Would you consider to make the WeakSafeReadWriteLock public? I use a similar thing to Striped#lazyWeakReadWriteLock, just without the striping.

Shouldn't this be fixed in the JDK? Just removing the static modifier of the nested classes would do. We could argue that the nested locks need no reference to the enclosing class, but this issue shows it's actually needed.

I had an idea of simply extending all three involved locks and overriding the readLock and writeLock getters, making the original locks unused. Your fix is cleaner, but it's more than ten times longer. It might perform worse because CHA for Condition and overridden methods deeper in the call hierarchy tree. Just guessing.

@cpovirk

This comment has been minimized.

Show comment
Hide comment
@cpovirk

cpovirk Oct 16, 2017

Member

RE: public: We've gotten requests before for "Striped but without the striping" (internal issue 4197198). It's probably worth another look, given the bug found here. The hard part is probably the API. Ideally it would fit closely with the API for Striped, but it's not actually striping, so the name doesn't make sense, nor does the extremely rarely used getAt(int index) method (which we might replace with lockAll and unlockAll if not for those non-lock and read-write-lock use cases...) or the related method size(). Maybe the right approach would have been a LockMap class with stripedReadWriteLock, perObjectReadWriteLock, etc., with some of those returning a StripedLockMap subclass with the index/size-based methods. That might work, but I'm not sure when it will reach the top of our priority list :( But it still seems more likely than just exposing the lock, given that the lock is fairly straightforward to write yourself.

RE: fixing in JDK: That sounds like a good idea to me. Are you interested in reporting on http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest? If not, I can do it -- probably not immediately but well before I do the API thing, at least :)

RE: extending: I suppose I can imagine some hit to performance from the extra types (and/or indirection). My guess is that it won't matter much in comparison with the overhead that people expect when using especially a read/write lock. Also, I'm not sure we have that option for Condition, since newCondition in ReentrantReadWriteLock requires access to the private sync field, so we either do all Forwarding* types or else we mix subclasses and forwarding (which is not really "wrong" but a little weird).

Member

cpovirk commented Oct 16, 2017

RE: public: We've gotten requests before for "Striped but without the striping" (internal issue 4197198). It's probably worth another look, given the bug found here. The hard part is probably the API. Ideally it would fit closely with the API for Striped, but it's not actually striping, so the name doesn't make sense, nor does the extremely rarely used getAt(int index) method (which we might replace with lockAll and unlockAll if not for those non-lock and read-write-lock use cases...) or the related method size(). Maybe the right approach would have been a LockMap class with stripedReadWriteLock, perObjectReadWriteLock, etc., with some of those returning a StripedLockMap subclass with the index/size-based methods. That might work, but I'm not sure when it will reach the top of our priority list :( But it still seems more likely than just exposing the lock, given that the lock is fairly straightforward to write yourself.

RE: fixing in JDK: That sounds like a good idea to me. Are you interested in reporting on http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest? If not, I can do it -- probably not immediately but well before I do the API thing, at least :)

RE: extending: I suppose I can imagine some hit to performance from the extra types (and/or indirection). My guess is that it won't matter much in comparison with the overhead that people expect when using especially a read/write lock. Also, I'm not sure we have that option for Condition, since newCondition in ReentrantReadWriteLock requires access to the private sync field, so we either do all Forwarding* types or else we mix subclasses and forwarding (which is not really "wrong" but a little weird).

@lowasser

This comment has been minimized.

Show comment
Hide comment
@lowasser

lowasser Oct 16, 2017

Contributor

I'm not necessarily inclined to support the fix in the JDK, actually? Like..."must work when used via weak references" is not generally a thing that implementations specify or are written for. I'm not sure ReentrantReadWriteLock is any more special than the many other APIs that may or may not work when used via weak references.

Also, FWIW, I tend to consider ~all JDK classes that are not explicitly abstract to be implicitly final, and extending them to be a dangerous practice.

Contributor

lowasser commented Oct 16, 2017

I'm not necessarily inclined to support the fix in the JDK, actually? Like..."must work when used via weak references" is not generally a thing that implementations specify or are written for. I'm not sure ReentrantReadWriteLock is any more special than the many other APIs that may or may not work when used via weak references.

Also, FWIW, I tend to consider ~all JDK classes that are not explicitly abstract to be implicitly final, and extending them to be a dangerous practice.

@cpovirk

This comment has been minimized.

Show comment
Hide comment
@cpovirk

cpovirk Oct 16, 2017

Member

Yeah, it's a weird case that the JDK might not be interested in handling. I think it's worth asking them, but I could understand if they were to say no.

I also agree in general about extension, but I am willing to occasionally make exceptions for java.util.concurrent classes, which seem to be designed at least a little more for extension, in only so that people can save a little indirection by using inheritance. And classes like ReadLock have docs like "Constructor for use by subclasses," which is also encouraging. Nevertheless, I do think that composition is nicer here; I just consider inheritance to be a little safer than usual, if still hairy.

Member

cpovirk commented Oct 16, 2017

Yeah, it's a weird case that the JDK might not be interested in handling. I think it's worth asking them, but I could understand if they were to say no.

I also agree in general about extension, but I am willing to occasionally make exceptions for java.util.concurrent classes, which seem to be designed at least a little more for extension, in only so that people can save a little indirection by using inheritance. And classes like ReadLock have docs like "Constructor for use by subclasses," which is also encouraging. Nevertheless, I do think that composition is nicer here; I just consider inheritance to be a little safer than usual, if still hairy.

@Maaartinus

This comment has been minimized.

Show comment
Hide comment
@Maaartinus

Maaartinus Oct 17, 2017

perObjectReadWriteLock

That's it.

fixing in JDK

Posted.

in comparison with the overhead that people expect when using especially a read/write lock

In a lucky case, there's hardly anything besides a single CAS in nonfairTryAcquire, but agreed.

I'm not sure we have that option for Condition

I wasn't that far at the time of posting... I'm afraid, we're not. This makes inheritance only half as usable (and the mixing would be weird), so let's forget it.

I'm not necessarily inclined to support the fix in the JDK

@lowasser Agreed, I'm not sure either. But the cost is tiny, so I posted it for them to evaluate.

if ReentrantReadWriteLock is any more special than the many other APIs

In a sense it is, as there are the three classes where each just exposes different aspects of a single sync (whose identity matters), so keeping them all alive for the same time sounds good. I can't recall any similar case.

Maaartinus commented Oct 17, 2017

perObjectReadWriteLock

That's it.

fixing in JDK

Posted.

in comparison with the overhead that people expect when using especially a read/write lock

In a lucky case, there's hardly anything besides a single CAS in nonfairTryAcquire, but agreed.

I'm not sure we have that option for Condition

I wasn't that far at the time of posting... I'm afraid, we're not. This makes inheritance only half as usable (and the mixing would be weird), so let's forget it.

I'm not necessarily inclined to support the fix in the JDK

@lowasser Agreed, I'm not sure either. But the cost is tiny, so I posted it for them to evaluate.

if ReentrantReadWriteLock is any more special than the many other APIs

In a sense it is, as there are the three classes where each just exposes different aspects of a single sync (whose identity matters), so keeping them all alive for the same time sounds good. I can't recall any similar case.

@cpovirk

This comment has been minimized.

Show comment
Hide comment
@cpovirk

cpovirk Oct 17, 2017

Member

Posted.

If I recall correctly, I had to join the list before I could post. I'm not seeing your post, so that would explain it.

Member

cpovirk commented Oct 17, 2017

Posted.

If I recall correctly, I had to join the list before I could post. I'm not seeing your post, so that would explain it.

@Maaartinus

This comment has been minimized.

Show comment
Hide comment
@Maaartinus

Maaartinus Oct 17, 2017

Posted.

If I recall correctly, I had to join the list before I could post. I'm not seeing your post, so that would explain it.

Thanks! I thought, I was a member already. Too many mailing lists. ;) Now, it worked.

Maaartinus commented Oct 17, 2017

Posted.

If I recall correctly, I had to join the list before I could post. I'm not seeing your post, so that would explain it.

Thanks! I thought, I was a member already. Too many mailing lists. ;) Now, it worked.

@efge

This comment has been minimized.

Show comment
Hide comment

@netdpb netdpb modified the milestones: NEXT, 23.3 Oct 26, 2017

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment