ReadWriteLock - Should We Remove?

[Robert Liao]

I was going through base::internal::IncomingTaskQueue and was surprised to see that a ReadWriteLock had made it into base.

For Windows, SRWLocks in shared mode have non-trivial performance implications as more state has to be checked on acquisition. This slows down the shared acquisition and is reproable with a tight loop test:

SRWLOCK srwlock = SRWLOCK_INIT;
constexpr size_t rounds = 10000000;   

DWORD start = timeGetTime();
for (size_t i = 0; i < rounds; ++i) {
  AcquireSRWLockExclusive(&srwlock);
  ReleaseSRWLockExclusive(&srwlock);
}
DWORD end = timeGetTime();
DWORD startshared = timeGetTime();
for (size_t i = 0; i < rounds; ++i) {
  AcquireSRWLockShared(&srwlock);
  ReleaseSRWLockShared(&srwlock);
}
DWORD endshared = timeGetTime();

printf("Exclusive: %d ms\n", end - start);
printf("Shared: %d ms\n", endshared - startshared); 

5 different runs:

 >Sandbox.exe
Exclusive: 138 ms
Shared: 163 ms
>Sandbox.exe
Exclusive: 139 ms
Shared: 163 ms
>Sandbox.exe
Exclusive: 139 ms
Shared: 163 ms
>Sandbox.exe
Exclusive: 138 ms
Shared: 163 ms
>Sandbox.exe
Exclusive: 139 ms
Shared: 162 ms

I only see two uses of ReadWriteLock in Chromium and I'm inclined to remove this lock due to this gotcha on Windows as well as extremely limited use.

Any objections?

[Brett Wilson]

If we have a solution for these two call sites that it clear and we think is at least as good, I agree we should remove it.

2 uses over >1 year doesn't seem to justify its existence, even without platform-specific issues.

Brett

--
--
Chromium Developers mailing list: chromi...@chromium.org
View archives, change email options, or unsubscribe:
http://groups.google.com/a/chromium.org/group/chromium-dev
---
You received this message because you are subscribed to the Google Groups "Chromium-dev" group.
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/chromium-dev/CAK7A45VgB4Gaph648aQQP2b7qw3E%2BuDRB%2BC%2BhzoLX29M-w0%3D-Q%40mail.gmail.com.

[Robert Liao]

From what I can tell, these uses can just use a regular lock (or existing locks) as the Write Lock is acquired only for the purpose of synchronizing shutdown in both the TaskService and IncomingTaskQueue.

[Antoine Labour]

On Thu, Aug 24, 2017 at 2:39 PM, Robert Liao <rob...@chromium.org> wrote:

From what I can tell, these uses can just use a regular lock (or existing locks) as the Write Lock is acquired only for the purpose of synchronizing shutdown in both the TaskService and IncomingTaskQueue.

The RWLock was introduced by https://codereview.chromium.org/1991623002, it sounds like it has very legitimate scalability uses. Beware of blindly replacing by a dumb lock... (see also Chesterton's Fence).

Thanks,

Antoine

 

To unsubscribe from this group and stop receiving emails from it, send an email to chromium-dev+unsubscribe@chromium.org.

To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/chromium-dev/CAK7A45U7o7OKzruZkQ0icb_6aL4opj%2BQQ7XX9XM8mbXX3-izNA%40mail.gmail.com.

[Robert Liao]

For IncomingTaskQueue and MIDI TaskService, the reason why I'm less sympathetic is because it only requests the exclusive lock at shutdown.

I do agree that a Lock+CV is probably more appropriate here to allow the concurrent reads while guarding against the single write.

[bruce...@chromium.org]

Actually... I recently requested that we *add* a use of that lock. We recently hit a pretty nasty bug (crbug.com/754213) where we ended up with multiple threads all trying to acquire the PartitionAlloc spin lock. It was a classic priority inversion issue with the net result that Chrome consumed all CPU time and made zero progress. The bug was made more serious by the fact that two of the threads were real-time priority audio threads, and the machines only having two cores. Nasty. Although, the context switch graphs from the ETW trace looked pretty amazing.

As long as PartitionAlloc uses a spin lock we can't use it from high priority threads (or low priority threads) and we risk temporary priority inversions even with normal priority threads, especially on machines with low core counts.

My understanding is that there are technical reasons why a critical section (my usual first choice) is incompatible with PartitionAlloc - hence the desire for the ReadWriteLock.

If we had to get rid of one lock I'd recommend getting rid of the spin lock.

That said, I don't know much about ReadWriteLocks.

[Robert Liao]

What's the access pattern in PartitionAlloc that necessitates the use of a ReadWriteLock that can't be substituted with a Lock+CV pair?

To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/chromium-dev/23206110-ec04-4341-828a-efd55bd2ae32%40chromium.org.

[Bruce Dawson]

My understanding is that PartitionAlloc only has space for a pointer-sized lock.

[Robert Liao]

It seems PartitionAlloc's problems are caused by spinning. If they used base::Lock/SRWLock directly, wouldn't that also address the issue?

[Bruce Dawson]

> If they used base::Lock/SRWLock directly, wouldn't that also address the issue?

Yes, but my understanding is that base::Lock is incompatible with PartitionAlloc (requires initialization/destruction, isn't pointer sized) and SRWLock is the one that you were suggesting removing, wasn't it?

BTW, crbug.com/758695 is the bug requesting that we switch to a non spin-lock for PartitionAlloc.

[Robert Liao]

We're keeping base::Lock (which on Windows uses SRWLock underneath with AcquireSRWLockExclusive and ReleaseSRWLockExclusive).

 

ReadWriteLock just exposes an additional AcquireSRWLockShared and ReleaseSRWLockShared, which we likely don't really need in base.

[Bruce Dawson]

Ah - understood. I thought that base::Lock was a critical section - that explains the misunderstanding.

[Robert Liao]

Yep. base::Lock used to use CRITICAL_SECTION on Windows until

https://chromium.googlesource.com/chromium/src/+/7a8a904bfdf23bb8cacba471718bc09a0d9a3175

SRWLock is what we use now. If there is a strict requirement for the lock to be pointer sized, the base locking APIs are not guaranteed to be pointer sized.

For POSIX, base::Lock uses pthread_mutex_t and base::subtle::ReadWriteLock uses pthread_rwlock_t, both of which are structures often with multiple members that generally exceed a pointer size.

As a result, if pointer-size is a strict requirement for PartitionAlloc, both base::Lock and base::subtle::ReadWriteLock can't provide that guarantee today without some memory indirection.

[Antoine Labour]

On Fri, Aug 25, 2017 at 2:16 PM, Robert Liao <rob...@chromium.org> wrote:

We're keeping base::Lock (which on Windows uses SRWLock underneath with AcquireSRWLockExclusive and ReleaseSRWLockExclusive).

 

ReadWriteLock just exposes an additional AcquireSRWLockShared and ReleaseSRWLockShared, which we likely don't really need in base.

TBH I'm not sure what you're proposing or what the rationale is exactly. ReadWriteLock is a well understood primitive with clear semantics, and implemented in typical platform APIs (e.g. pthread, win32, linux kernel, you name it).

So a ReadWriteLock is slightly (20%) more costly than a pure Lock in the non-contended use case - that's kind of expected. That's the tradeoff for scalability in the contended use case. Some code uses that primitive, probably for good reason (or are you arguing that it's not?).

It sounds like you're advocating replacing the ReadWriteLock by some other code in the places that use it, but I'm not clear about the suggested replacement - it sounds like it would be more expensive (2 lock/unlocks in the shared case, but maybe I misunderstood). So.... why?

Antoine

[Robert Liao]

The proposal is to remove base::subtle::ReadWriteLock, introduced just over a year ago with only two users in that timespan, both of which could have used something else. Both cases also deal with the write mode only at shutdown of the component

There are two main motivations for the removal:

1. Only two components (now one, and soon zero) have used this lock since the lock's introduction over a year ago, which runs afoul of the wide applicability requirement for base.
   
2. Using this lock correctly can be non-trivial and the lock has perf implications on Windows at least. It's rightfully in base::subtle. 

After going through a migration for TaskService, the code's intention is now more obvious

  base::AutoLock tasks_in_flight_auto_lock(tasks_in_flight_lock_);
  while (tasks_in_flight_ > 0)
    no_tasks_in_flight_cv_.Wait();

  return true;

vs.

  base::subtle::AutoWriteLock task_lock(task_lock_);
  return true;

Given that we will soon have no more users and base::Lock is generally good enough for most use cases, removing base::subtle::ReadWriteLock seemed reasonable.

[Antoine Labour]

On Fri, Aug 25, 2017 at 3:02 PM, Robert Liao <rob...@chromium.org> wrote:

The proposal is to remove base::subtle::ReadWriteLock, introduced just over a year ago with only two users in that timespan, both of which could have used something else. Both cases also deal with the write mode only at shutdown of the component

There are two main motivations for the removal:

1. Only two components (now one, and soon zero) have used this lock since the lock's introduction over a year ago, which runs afoul of the wide applicability requirement for base.
   

This argument is a bit meaningless for things that are used directly by base/ . I suppose it could be moved to base::internal, which wouldn't bother me. Or it could be merged into its user(s) but that makes testing harder.

1. Using this lock correctly can be non-trivial and the lock has perf implications on Windows at least. It's rightfully in base::subtle. 

I guess I still don't understand this "perf implication" bit. Isn't the replacement worse?

After going through a migration for TaskService, the code's intention is now more obvious

Maybe more obvious, but less scalable. Maybe it doesn't matter for MIDI's TaskService patterns - I don't have an opinion there.

However making PostTask block for upwards of 80ms because of contention is unacceptable. So we'll still need some equivalent of RWLock, and if we reimplement it using pure locks (or lock + cv) instead of the existing platform primitive it'll be slower (and that's for every single PostTask for every single message loop). So why would we want to do that?

Antoine

[Robert Liao]

I guess I still don't understand this "perf implication" bit. Isn't the replacement worse?

The perf implication is for widespread use of ReadWriteLock.

If we were to apply ReadWriteLock religiously by using the read lock in areas that are read only and writes in areas that write, the code is demonstrably slower than just using exclusive access as most code in Chromium isn't generally multiple-reader single-writer. Again, this does depend on the access pattern.

Maybe more obvious, but less scalable.

This solution is sufficient for the MIDI case, and incidentally was a solution they were going to use before they were hunting around and found ReadWriteLock. 

However making PostTask block for upwards of 80ms because of contention is unacceptable. So we'll still need some equivalent of RWLock, and if we reimplement it using pure locks (or lock + cv) instead of the existing platform primitive it'll be slower (and that's for every single PostTask for every single message loop). So why would we want to do that?

The 80ms waking up the MessageLoop is going to dominate any singular call/double call to lock+cv or ReadWriteLock. Instead, what IncomingTaskQueue here wants is to know when its safe to set message_loop_ to null, which is not unlike the TaskService usage can be accomplished similarly by only setting the value if there are no pending tasks in flight. A ReadWriteLock is not required for that.

If the MessageLoop wakeup is fast, the serialization of the all the calls through IncomingTaskQueue::PostPendingTask will start to dominate, which means you would have been better off using a single lock.

[pal...@chromium.org]

On Thursday, August 24, 2017 at 6:10:12 PM UTC-7, bruce...@chromium.org wrote:

Actually... I recently requested that we *add* a use of that lock. We recently hit a pretty nasty bug (crbug.com/754213) where we ended up with multiple threads all trying to acquire the PartitionAlloc spin lock. It was a classic priority inversion issue with the net result that Chrome consumed all CPU time and made zero progress. The bug was made more serious by the fact that two of the threads were real-time priority audio threads, and the machines only having two cores. Nasty. Although, the context switch graphs from the ETW trace looked pretty amazing.

I'm working on this problem now.

But, for the record, I'd like to note again :) that a thread can't really claim to be "real-time" and also do dynamic memory allocation. That's just not a thing. I'll try to make Partition Alloc resilient against such callers. But the root of the problem is, IMO, with setting non-real-time-capable threads as real-time priority.

[Robert Liao]

This work is now complete and ReadWriteLock is no longer in the codebase.

For IncomingTaskQueue, there is now one fewer lock acquisition for most platforms compared to the ReadWriteLock solution.

For Android, the number of required acquisitions is the same and the serialization points also remain the same.

--

--
Chromium Developers mailing list: chromi...@chromium.org
View archives, change email options, or unsubscribe:
http://groups.google.com/a/chromium.org/group/chromium-dev
---
You received this message because you are subscribed to the Google Groups "Chromium-dev" group.

To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/chromium-dev/ed6524f0-9cf8-44bd-a7f6-b294dfef7502%40chromium.org.