[Bug 54979] New: Futexes which protect memory allocation congest, causing 100x performance degradation
https://bugs.winehq.org/show_bug.cgi?id=54979 Bug ID: 54979 Summary: Futexes which protect memory allocation congest, causing 100x performance degradation Product: Wine Version: 8.0.1 Hardware: x86-64 OS: Linux Status: UNCONFIRMED Severity: normal Priority: P2 Component: ntdll Assignee: wine-bugs(a)winehq.org Reporter: nagle(a)animats.com Distribution: --- Created attachment 74518 --> https://bugs.winehq.org/attachment.cgi?id=74518 Debugger output with multiple threads stuck in spinlocks. SUMMARY Under the wrong circumstances, a program doing many memory allocations from multiple threads can experience more than 100x performance degradation. I'm seeing this in my own Rust program, which has 16 sometimes-compute-bound threads on a 12 CPU machine. This works fine on Microsoft Windows and when compiled for Linux. Under Wine, it can be over 100x slower. Multiple threads are banging on a spinlock at _InterlockedCompareExchange [Z:\usr\src\packages\BUILD\include\winnt.h:6630] in ntdll spin_lock [Z:\usr\src\packages\BUILD\dlls\ntdll\sync.c:937] in ntdll This is the spin lock around the queue for pausing threads. DISCUSSION This looks like futex congestion. That's a known kind of problem, but doesn't seem to have been seen in Wine before. It may be that some programs just run really slow under Wine, and nobody knows why. The code in NTDLL is clearly intended to handle the fast case without doing an OS-level lock. Under light load, that's O(1). But under heavy load, with multiple threads pounding on spinlocks, each spinlock waits longer, and there are multiple threads, so it becomes O(N^2). Which means huge slowdowns. See discussion at https://forum.winehq.org/viewtopic.php?t=37688 which has snippets of the code that's causing the problem. I can copy all that info over here if necessary. Let me know. -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=54979 Zeb Figura <z.figura12(a)gmail.com> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |z.figura12(a)gmail.com --- Comment #1 from Zeb Figura <z.figura12(a)gmail.com> --- I haven't been able to find a way to avoid the spinlock for RtlWaitOnAddress. That primitive needs to be fair *and* support timeouts *and* as fast as possible, and I haven't been able to find a faster way than user-space spinlocks. However, we can probably avoid RtlWaitOnAddress for critical sections. -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=54979 --- Comment #2 from John Nagle <nagle(a)animats.com> --- I don't see an easy way to eliminate that innermost spinlock, either. It's not a long lock. The slowest thing inside is searching a linear list of waiting threads, which ought to take maybe a microsecond. So it may be that the outer loops are asking for that lock too often. There are three nested locks here, two futexes and a hard spinlock. The one that looks most suspicious is the middle one at wait_semaphore. That loop repeatedly calls RtlWaitOnAddress, which is probably why control is usually in the innermost spinlock on a debugger break. If wait_semaphore didn't do that, the problem might go away. The outermost lock has if (crit->LockCount > 0) break; /* more than one waiter, don't bother spinning */ so it's protected against this kind of problem. If that lock starts to build up a backlog, the thread blocks rather than spinning. But wait_semaphore doesn't have similar protection. Thanks for looking at this. -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=54979 --- Comment #3 from Zeb Figura <z.figura12(a)gmail.com> --- (In reply to Zeb Figura from comment #1)
However, we can probably avoid RtlWaitOnAddress for critical sections.
This is harder than I thought. I thought it would be relatively easy to implement a lock-free wait queue on the stacks of the waiting threads, but after thinking it through I don't think it's actually possible at all. In theory we could try supplying hints as to which thread to wake (say, with a bounded ring buffer). The problem with this is that we only have a pointer's worth of space to work with, and we can't allocate more because we underly the heap implementation. (In reply to John Nagle from comment #2)
There are three nested locks here, two futexes and a hard spinlock. The one that looks most suspicious is the middle one at wait_semaphore. That loop repeatedly calls RtlWaitOnAddress, which is probably why control is usually in the innermost spinlock on a debugger break. If wait_semaphore didn't do that, the problem might go away.
I don't think this is suspicious. We use RtlWakeAddressSingle(), and win32 futexes are fair, so in theory a given waiting thread should only actually be woken once. At worst I think it can have one stale buffered wakeup from a previous alert. -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=54979 mqudsi <mqudsi(a)neosmart.net> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |mqudsi(a)neosmart.net -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=54979 --- Comment #4 from John Nagle <nagle(a)animats.com> --- Any progress on this? What usually sets this off is growing an array. That calls realloc, and attempts to grow the buffer in place. If that's not possible due to a lack of free space after the buffer, the realloc code allocates a new buffer, copies the data, and releases the old buffer. The bottleneck seems to be at the point where the old buffer is released. That's somewhat unexpected. A test case might involve a large number of compute-bound threads, all growing arrays slowly. -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=54979 --- Comment #5 from Zeb Figura <z.figura12(a)gmail.com> --- (In reply to John Nagle from comment #4)
Any progress on this?
No, I don't have any ideas for optimizing critical sections or Win32 futexes. -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=54979 --- Comment #6 from John Nagle <nagle(a)animats.com> --- Hm. Real Windows does not seem to have this problem. What does Microsoft do? -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=54979 --- Comment #7 from Zeb Figura <z.figura12(a)gmail.com> --- (In reply to John Nagle from comment #6)
Hm. Real Windows does not seem to have this problem. What does Microsoft do?
I don't know. Unfortunately I don't think it'll be easy to find out; note that because of copyright we can't go poking around in Windows internals. -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=54979 --- Comment #8 from John Nagle <nagle(a)animats.com> --- Any progress on this? You're not likely to get as good a bug report from anyone else. If this happens in some game, they won't have source code. I do, and was able to see the problem in GDB. There's probably some "My Game Hangs" bug report that's really this problem, but can't be diagnosed. -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=54979 --- Comment #9 from Zeb Figura <z.figura12(a)gmail.com> --- (In reply to John Nagle from comment #8)
Any progress on this?
You're not likely to get as good a bug report from anyone else. If this happens in some game, they won't have source code. I do, and was able to see the problem in GDB. There's probably some "My Game Hangs" bug report that's really this problem, but can't be diagnosed.
I understand, I'm thankful for providing a clear bug report. The thing is, this bug is not going to be fixed until someone has an idea for how to write a fast user-space wait queue that doesn't allocate and whose "head" can fit in a pointer. -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=54979 --- Comment #10 from John Nagle <nagle(a)animats.com> --- Right. You're three deep in futexes at that point, and I think they're interacting badly. I think it's the one in the middle that's part of the problem. But I'm not sure. GDB gives me a snapshot of the state but not the dynamics that got us there. Maybe if the middle spinlock had a quick quit to a hard block... -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=54979 --- Comment #11 from Zeb Figura <z.figura12(a)gmail.com> --- (In reply to John Nagle from comment #10)
Maybe if the middle spinlock had a quick quit to a hard block...
Sorry, what do you mean by "the middle spinlock"? I guess you probably mean futex_queue.lock, since it's the only spinlock. We can't block there, because we have no fast way to wake up a waiter. [And frankly, even if we could block, I worry about the performance implications.] -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=54979 --- Comment #12 from John Nagle <nagle(a)animats.com> --- There is an outer level of spinlock. See summary here: https://forum.winehq.org/viewtopic.php?t=37688 As far as I can tell, this is not fine-grained locking. It's just one big lock for the whole heap. That should be a short spinlock, which, if it times out, causes a kernel-level lock and block. The bottleneck is that when you realloc a buffer, the old one may have to be recopied, and the heap is locked up during that period. -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=54979 --- Comment #13 from Zeb Figura <z.figura12(a)gmail.com> --- (In reply to John Nagle from comment #12)
There is an outer level of spinlock.
See summary here: https://forum.winehq.org/viewtopic.php?t=37688
Ah. That's not really a spinlock, though. The CS is a hybrid lock, but not a true spinlock, and we don't use the spin count for the heap anyway, so it's not even a hybrid lock.
As far as I can tell, this is not fine-grained locking. It's just one big lock for the whole heap.
That's true, if making heap locking more fine-grained would be enough then that's an alternate solution. I don't really have the time/interest to implement that myself, though.
That should be a short spinlock, which, if it times out, causes a kernel-level lock and block.
It is. In fact, it's not even the spinlock; we just block immediately. The problem is that in order to block we need to spin-lock the internal wait queue. There are other ways to do a kernel wait, but they come with a significant performance cost. -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=54979 --- Comment #14 from John Nagle <nagle(a)animats.com> --- Also reported as a Rend3 bug: https://github.com/BVE-Reborn/rend3/issues/570 -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=54979 --- Comment #15 from Zeb Figura <z.figura12(a)gmail.com> --- (In reply to John Nagle from comment #14)
Also reported as a Rend3 bug: https://github.com/BVE-Reborn/rend3/issues/570
That seems to be a different bug? -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=54979 --- Comment #16 from John Nagle <nagle(a)animats.com> --- Wrong bug. Sorry. -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=54979 Jinoh Kang <jinoh.kang.kr(a)gmail.com> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |jinoh.kang.kr(a)gmail.com --- Comment #17 from Jinoh Kang <jinoh.kang.kr(a)gmail.com> --- It would be helpful to discover the specific allocation pattern we should optimize for. Also, the heap lock is never held if the LFH path is taken. Apparently we're not doing LFH here, so we might want to figure out what prevents us from doing LFH, and if Windows also has a problem here. -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
http://bugs.winehq.org/show_bug.cgi?id=54979 --- Comment #18 from John Nagle <nagle(a)animats.com> --- Just upgraded to Ubuntu 24.04 LTS with wine-9.0 (Ubuntu 9.0~repack-4build3) Bug still seems to be present. It's very funny to watch. I can bring up an entire multi-threaded metaverse client, 3D graphics and all. But each character echo takes two seconds. -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
http://bugs.winehq.org/show_bug.cgi?id=54979 marc_aurel@me.com changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |marc_aurel@me.com --- Comment #19 from marc_aurel@me.com --- Created attachment 80774 --> http://bugs.winehq.org/attachment.cgi?id=80774 Futex congestion improvements Does anything in the following patch help? The adaptive spinlock should improve the multiple threads banging against the same lock scenario (and the lock holder probably being preempted). Also there are some improvements there to avoid collisions on the futex queue, although that will not help with the singular heap CS here, but maybe the slowdown observed in the metaverse client does get better with that... -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
http://bugs.winehq.org/show_bug.cgi?id=54979 --- Comment #20 from John Nagle <nagle@animats.com> --- Working well in Wine 11.0 stable / Ubuntu 24.04 LTS. Thank you very much for fixing this. Now I can test under Wine again. -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
participants (2)
-
WineHQ Bugzilla -
WineHQ Bugzilla