Skip to content
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

proposal: sync.RWMutex: upgradable/downgradable locking #44049

Closed
zx2c4 opened this issue Feb 1, 2021 · 8 comments
Closed

proposal: sync.RWMutex: upgradable/downgradable locking #44049

zx2c4 opened this issue Feb 1, 2021 · 8 comments

Comments

@zx2c4
Copy link
Contributor

zx2c4 commented Feb 1, 2021

This issue is to gauge interest in adding RWMutex.UpgradeToExcusive(), RWMutex.TryUpgradeToExclusive(), and RWMutex.DowngradeToRead().

Consider this function:

func connectToService(serviceName string) (*connectedService, error) {
	// First check if we have a cached service.
	cachedServicesMu.RLock()
	service, ok := cachedServices[serviceName]
	if ok {
		cachedServicesMu.RUnlock()
		return service, nil
	}
	cachedServicesMu.RUnlock()

	// <--- Potential race happens here.

	cachedServicesMu.Lock()
	defer cachedServicesMu.Unlock()

	// Check again now that we're holding the exclusive lock.
	service, ok := cachedServices[serviceName]
	if ok {
		cachedServicesMu.RUnlock()
		return service, nil
	}
	
	// Not cached, so make the expensive connection.
	service, err := doSomeConnectionDance(serviceName)
	if err != nil {
		return nil, err
	}
	
	// Cache it for later.
	cachedServices[serviceName] = service

	return service, nil
}

This first checks a cache map using a read lock and then later upgrades it to a write lock. But there's a race during the upgrade, so it has to recheck mid-way through. Here's an improvement:

func connectToService(serviceName string) (*connectedService, error) {
	// First check if we have a cached service.
	cachedServicesMu.RLock()
	for {
		service, ok := cachedServices[serviceName]
		if ok {
			cachedServicesMu.RUnlock()
			return service, nil
		}
		if cachedServicesMu.TryUpgradeToExclusive() { // <-- New API!
			break
		}
	}
	defer cachedServicesMu.Unlock()

	// Not cached, so make the expensive connection.
	service, err := doSomeConnectionDance(serviceName)
	if err != nil {
		return nil, err
	}
	
	// Cache it for later.
	cachedServices[serviceName] = service

	return service, nil
}

The cachedServicesMu.TryUpgradeToExclusive() line changes the lock from a read-lock to an exclusive-lock, without giving up the lock entirely in the middle. It blocks until it gets exclusive use, and returns true, or until the next waiting exclusive user returns its lock, in which case it returns false and doesn't upgrade.

Is this functionality that's sufficiently interesting to others? Or is it too niche? Is it conceivably implementable using existing code or would it require changes that are too invasive?

CC @prattmic @CAFxX

@gopherbot gopherbot added this to the Proposal milestone Feb 1, 2021
@randall77
Copy link
Contributor

Looks like a dup of #4026 .
Anything new here?

@prattmic
Copy link
Member

prattmic commented Feb 1, 2021

There have also been discussions about this on #4026, #23513, and #38891.

And importantly note #4026 (comment): UpgradeToExclusive can't unconditionally succeed, as it could deadlock.

@zx2c4
Copy link
Contributor Author

zx2c4 commented Feb 1, 2021

Ahhh looks like this has been suggested before, most recently in June, and @rsc declined based on no clear consensus. I'm fine closing this if that opinion prevails. Perhaps the Try variant in this proposal makes it slightly different, but perhaps not.

@prattmic
Copy link
Member

prattmic commented Feb 1, 2021

The cachedServicesMu.TryUpgradeToExclusive() line changes the lock from a read-lock to an exclusive-lock, without giving up the lock entirely in the middle. It blocks until it gets exclusive use, and returns true, or until the next waiting exclusive user returns its lock, in which case it returns false and doesn't upgrade.

I'm not sure I understand how this is supposed to work, could you explain more? It seems like "until the next waiting exclusive user returns its lock" will never occur. We are holding a read lock, so waiting writers can't ever unblock until we release the read lock, which never occurs. Is the intention that TryUpgradeToExclusive does that internally? i.e., if TryUpgradeToExclusive returns false we are in a new read-locked region and any previous values (e.g., service) are invalidated? I think that would work, but IMO it is quite subtle and error-prone.

@zx2c4
Copy link
Contributor Author

zx2c4 commented Feb 1, 2021

The idea for TryUpgradeToExclusive would be:

  • If nobody else has called TryUpgradeToExclusive, then it takes an exclusive lock whenever the last read lock is dropped (or whenever all the readers are parked on their own calls to TryUpgradeToExclusive).
  • If somebody else has already called TryUpgradeToExclusive, then it blocks until the first caller of TryUpgradeToExclusive obtains and subsequently drops the exclusive lock, and then returns with the read lock taken.

Consider that in the context of the snippet:

func connectToService(serviceName string) (*connectedService, error) {
	// First check if we have a cached service.
	cachedServicesMu.RLock()
	for {
		service, ok := cachedServices[serviceName]
		if ok {
			cachedServicesMu.RUnlock()
			return service, nil
		}
		if cachedServicesMu.TryUpgradeToExclusive() { // <-- New API!
			break
		}
	}
	defer cachedServicesMu.Unlock()

	// Not cached, so make the expensive connection.
	service, err := doSomeConnectionDance(serviceName)
	if err != nil {
		return nil, err
	}
	
	// Cache it for later.
	cachedServices[serviceName] = service

	return service, nil
}

We break out of that loop if we succeeded in getting the exclusive lock first. Otherwise we know somebody else got it first, but they're now done with it, so it's a good time for us to unblock and do another loop iteration with the read lock still held.

@AndrewGMorgan
Copy link
Contributor

What is wrong with this pattern (no loop, just unroll once)?:

	cachedServicesMu.RLock()
	service, ok := cachedServices[serviceName]
	cachedServicesMu.RUnlock()
        if !ok {
                // confirm with a more expensive lock
	        cachedServicesMu.Lock()
	        defer cachedServicesMu.Unlock()
	        service, ok = cachedServices[serviceName]
        }
        if ok {
                return service, nil
        }
	// Not cached, so make the expensive connection.
	service, err := doSomeConnectionDance(serviceName)
	if err != nil {
		return nil, err
	}
	
	// Cache it for later.
	cachedServices[serviceName] = service

	return service, nil

@ianlancetaylor ianlancetaylor added this to Incoming in Proposals (old) Feb 17, 2021
@rsc
Copy link
Contributor

rsc commented Feb 17, 2021

Closing as a duplicate of #38891.
The fundamental problem is that we have no evidence that adding this API would make any real programs faster.

@rsc rsc moved this from Incoming to Declined in Proposals (old) Feb 17, 2021
@rsc
Copy link
Contributor

rsc commented Feb 17, 2021

No change in consensus, so declined.
— rsc for the proposal review group

Edit: Oops, I need to fix the bot's handling of duplicate issues. Sorry for the confusing message!

@rsc rsc closed this as completed Feb 17, 2021
@golang golang locked and limited conversation to collaborators Feb 17, 2022
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
No open projects
Development

No branches or pull requests

7 participants
@zx2c4 @rsc @prattmic @randall77 @gopherbot @AndrewGMorgan and others