Yesterday I decided to diff the export tables of some core Win32 DLLs to see what’s changed between Windows 8.1 and the Windows 10 technical preview. There weren’t many changes, but the ones that were there are quite exciting IMHO. While researching these new APIs, I also stumbled across some others that were added during the Windows 8 timeframe that we should be considering as well.

Volatile Ranges

While my diff showed these APIs as new exports for Windows 10, the MSDN docs claim that these APIs are actually new for the Windows 8.1 Update. Using the OfferVirtualMemory and ReclaimVirtualMemory functions, we can now specify ranges of virtual memory that are safe to discarded under memory pressure. Later on, should we request that access be restored to that memory, the kernel will either return that virtual memory to us unmodified, or advise us that the associated pages have been discarded.

A couple of years ago we had an intern on the Perf Team who was working on bringing this capability to Linux. I am pleasantly surprised that this is now offered on Windows.

madvise(MADV_WILLNEED) for Win32

For the longest time we have been hacking around the absence of a madvise-like API on Win32. On Linux we will do a madvise(MADV_WILLNEED) on memory-mapped files when we want the kernel to read ahead. On Win32, we were opening the backing file and then doing a series of sequential reads through the file to force the kernel to cache the file data. As of Windows 8, we can now call PrefetchVirtualMemory for a similar effect.

Operation Recorder: An API for SuperFetch

The OperationStart and OperationEnd APIs are intended to record access patterns during a file I/O operation. SuperFetch will then create prefetch files for the operation, enabling prefetch capabilities above and beyond the use case of initial process startup.

Memory Pressure Notifications

This API is not actually new, but I couldn’t find any invocations of it in the Mozilla codebase. CreateMemoryResourceNotification allocates a kernel handle that becomes signalled when physical memory is running low. Gecko already has facilities for handling memory pressure events on other platforms, so we should probably add this to the Win32 port.

I could apologize for the clickbaity title, but I won’t. I have no shame.

Today I want to talk about some code that we imported from Chromium some time ago. I replaced it in Mozilla’s codebase a few months back in bug 1072752:

261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277

    // A WM_* message is available.
    // If a parent child relationship exists between windows across threads
    // then their thread inputs are implicitly attached.
    // This causes the MsgWaitForMultipleObjectsEx API to return indicating
    // that messages are ready for processing (Specifically, mouse messages
    // intended for the child window may appear if the child window has
    // capture).
    // The subsequent PeekMessages call may fail to return any messages thus
    // causing us to enter a tight loop at times.
    // The WaitMessage call below is a workaround to give the child window
    // some time to process its input messages.
    MSG msg = {0};
    DWORD queue_status = GetQueueStatus(QS_MOUSE);
    if (HIWORD(queue_status) & QS_MOUSE &&
        !PeekMessage(&msg, NULL, WM_MOUSEFIRST, WM_MOUSELAST, PM_NOREMOVE)) {
      WaitMessage();
    }

This code is wrong. Very wrong.

Let us start with the calls to GetQueueStatus and PeekMessage. Those APIs mark any messages already in the thread’s message queue as having been seen, such that they are no longer considered “new.” Even though those function calls do not remove messages from the queue, any messages that were in the queue at this point are considered to be “old.”

The logic in this code snippet is essentially saying, “if the queue contains mouse messages that do not belong to this thread, then they must belong to an attached thread.” The code then calls WaitMessage in an effort to give the other thread(s) a chance to process their mouse messages. This is where the code goes off the rails.

The documentation for WaitMessage states the following:

Note that WaitMessage does not return if there is unread input in the message queue after the thread has called a function to check the queue. This is because functions such as PeekMessage, GetMessage, GetQueueStatus, WaitMessage, MsgWaitForMultipleObjects, and MsgWaitForMultipleObjectsEx check the queue and then change the state information for the queue so that the input is no longer considered new. A subsequent call to WaitMessage will not return until new input of the specified type arrives. The existing unread input (received prior to the last time the thread checked the queue) is ignored.

WaitMessage will only return if there is a new (as opposed to any) message in the queue for the calling thread. Any messages for the calling thread that were already in there at the time of the GetQueueStatus and PeekMessage calls are no longer new, so they are ignored.

There might very well be a message at the head of that queue that should be processed by the current thread. Instead it is ignored while we wait for other threads. Here is the crux of the problem: we’re waiting on other threads whose input queues are attached to our own! That other thread can’t process its messages because our thread has messages in front of its messages; on the other hand, our thread has blocked itself!

The only way to break this deadlock is for new messages to be added to the queue. That is a big reason why we’re seeing things like bug 1105386: Moving the mouse adds new messages to the queue, making WaitMessage unblock.

I’ve already eliminated this code in Mozilla’s codebase, but the challenge is going to be getting rid of this code in third-party binaries that attach their own windows to Firefox’s windows.

I’ve previously blogged indirectly about attached input queues, but today I want to address the issue directly. What once was a nuisance in the realm of plugin hangs has grown into a more serious problem in the land of OMTC and e10s.

As a brief recap for those who are not very familiar with this problem: imagine two windows, each on their own separate threads, forming a parent-child relationship with each other. When this situation arises, Windows implicitly attaches together and synchronizes their input queues, putting each thread at the mercy of the other attached threads’ ability to pump messages. If one thread does something bad in its message pump, any other threads that are attached to it are likely to be affected as well.

One of the biggest annoyances when it comes to knowledge about which threads are affected, is that we are essentially flying blind. There is no way to query Windows for information about attached input queues. This is unfortunate, as it would be really nice to obtain some specific knowledge to allow us to analyze the state of Firefox threads’ input queues so that we can mitigate the problem.

I had previously been working on a personal side project to make this possible, but in light of recent developments (and a tweet from bsmedberg), I decided to bring this investigation under the umbrella of my full-time job. I’m pleased to announce that I’ve finished the first cut of a utility that I call the Input Queue Visualizer, or iqvis.

iqvis consists of two components, one of which is a kernel-mode driver. This driver exposes input queue attachment data to user mode. The iqvis user-mode executable is the client that queries the driver and outputs the results. In the next section I’m going to discuss the inner workings of iqvis. Following that, I’ll discuss the results of running iqvis on an instance of Firefox.

Input Queue Visualizer Internals

First of all, let’s start off with this caveat: Nearly everything that this driver does involves undocumented APIs and data structures. Because of this, iqvis does some things that you should never do in production software.

One of the big consequences of using undocumented information is that iqvis requires pointers to very specific locations in kernel memory to accomplish things. These pointers will change every time that Windows is updated. To mitigate this, I kind of cheated: it turns out that debugging symbols exist for all of the locations that iqvis needs to access! I wrote the iqvis client to invoke the dbghelp engine to extract the pointers that I need from Windows symbols and send those values as the input to the DeviceIoControl call that triggers the data collection. Passing pointers from user mode to be accessed in kernel mode is a very dangerous thing to do (and again, I would never do it in production software), but it is damn convenient for iqvis!

Another issue is that these undocumented details change between Windows versions. The initial version of iqvis works on 64-bit Windows 8.1, but different code is required for other major releases, such as Windows 7. The iqvis driver theoretically will work on Windows 7 but I need to make a few bug fixes for that case.

So, getting those details out of the way, we can address the crux of the problem: we need to query input queue attachment information from win32k.sys, which is the driver that implements USER and GDI system calls on Windows NT systems.

In particular, the window manager maintains a linked list that describes thread attachment info as a triple that points to the “from” thread, the “to” thread, and a count. The count is necessary because the same two threads may be attached to each other multiple times. The iqvis driver walks this linked list in a thread-safe way to obtain the attachment data, and then copies it to the output buffer for the DeviceIoControl request.

Since iqvis involves a device driver, and since I have not digitally signed that device driver, one can’t just run iqvis and call it a day. This program won’t work unless the computer was either booted with kernel debugging enabled, or it was booted with driver signing temporarily disabled.

Running iqvis against Firefox

Today I ran iqvis using today’s Nightly 39 as well as the lastest release of Flash. I also tried it with Flash Protected Mode both disabled and enabled. (Note that these examples used an older version of iqvis that outputs thread IDs in hexadecimal. The current version uses decimal for its output.)

Protected Mode Disabled

FromTID ToTID Count
ac8 df4 1

Looking up the thread IDs:

• df4 is the Firefox main thread;
• ac8 is the plugin-container main thread.

I think that the output from this case is pretty much what I was expecting to see. The protected mode case, however, is more interesting.

Protected Mode Enabled

FromTID ToTID Count
f8c dbc 1
794 f8c 3

Looking up the thread IDs:

• dbc is the Firefox main thread;
• f8c is the plugin-container main thread;
• 794 is the Flash sandbox main thread.

Notice how Flash is attached to plugin-container, which is then attached to Firefox. Notice that transitively the Flash sandbox is effectively attached to Firefox, confirming previous hypotheses that I’ve discussed with colleagues in the past.

Also notice how the Flash sandbox attachment to plugin-container has a count of 3!

In Conclusion

In my opinion, my Input Queue Visualizer has already yielded some very interesting data. Hopefully this will help us to troubleshoot our issues in the future. Oh, and the code is up on GitHub! It’s poorly documented at the moment, but just remember to only try running it on 64-bit Windows 8.1 for the time being!