Synchronism x Performance

February 28th, 2007 - Fernando Roberto

No wonder that my last posts brought issues related to linked lists and performance. In recent weeks, I had been hired by a security company to take a look at one of their File System filters, in order to reduce the delay caused by them. In this post, I will talk about synchronism and CPU contention.

I think it should not be new to many here that a linked list, or any other resource, when shared among multiple threads, should implement some access synchronism control thus, avoiding a thread to read invalid data as a result of a change made by another thread at same time.

But I don’t have two processors, synchronism for what?

It is true that computers with only one processor run only one thread at any given moment. So we never have two threads being executed at the same time. But it is important to remember that threads are executed in small slices of time determined by the scheduler, considering each thread quantum size and its priority. There are ways of avoiding that a thread be interrupted by the Windows scheduler, but at normal temperature and pressure conditions, we do not know when a thread is interrupted giving its place to another thread be executed.

There are several synchronization mechanisms that we can use, but in this post, I will comment specifically about those I’ve been involved in these weeks. But besides these ones, I have to talk about the most exotic I’ve seen in years of experience, which for me was nicknamed “Mutex, pero no Mutcho.” This was a derived class from VMutex of VToolsD. The class enter() method insanely tried to acquire a mutex few thousand times in a loop. If after these thousands of interactions the mutex has not been acquired, then the thread gave up and accessed the shared resource anyway. Do you think the system was having some trouble of Dead Lock? Anyway, it was nice to fix this years ago. There are things we only believe when we see them.

As I have mentioned in another post, File System Filter is a layer placed over drivers like FastFAT, NTFS, CDFS, Network Redirectors and any other drivers that implement a file system interface. That is, all operations related to files, including File Mapping access, pass through File System filters.

If you’re not only interested to know about File System filters, but interested in working with File Systems itself, then you have an obligation to read the Windows NT File System Internals by Rajeev Nagar. This book is the single known reference that is comprehensive enough on this subject. First published in 1997 by O’Reilly, this book is still a mandatory tool for development relative to File Systems even for Windows Vista. Its publication was interrupted a few years ago, and during that time, I saw this book being sold for more than U$ 200.00 for a single used copy on Amazon. Today OSR holds the book copyrights and it is currently working on an updated edition, which should bring issues such as Shadow Copy, Transactional NTFS, Filter Manager, Mini Redirectors and force volume dismount. However this is a job that will take some time, then in 2005, the original version was reprinted to meet this need, while the new edition has been made.

The filter I have worked on maintains several lists to be consulted on each intercepted access. The mechanism used to synchronize access to these lists was the Spin Lock. An obvious choice, but inadequate for this scenario, where the activity is too intense. The list group that is used on IRP_MJ_READ routine is also used at IRP_MJ_WRITE routine and other events. The result is CPU contention. That is, when a thread gets a Spin Lock to do a query on the list, all other threads that need to consult the same list have to sit and wait until the Spin Lock is released (even in cases that we have more than one processor). Knowing that these lists are not small. Can you imagine how slow it was?

Just as world hunger, cervix cancer, the prostate examination and other ills that affect mankind, something should be done about this. Therefore, in a relentless struggle against the evil forces was created the ERESOURCE. (Angelic chants and a dry ice mist is dissipated into the ground)

Using ERESOURCE

ERESOURCE is the most appropriate and native way used to synchronize access to structures that are part of a file system, such as FCB (File Control Block), which besides other information, keeps the current file size. With ERESOURCE, multiple threads can access the same linked list at the same time for reading. Assuming that none of the threads would change the data list, then all accesses could be performed simultaneously. In contrast, if necessary, a thread can gain exclusive access to the list in order to make a change.

To use ERESOURSE, you must declare a ERESOURCE variable, which must reside in non-paged memory and 8 bytes aligned, and initialize it using ExInitializeResourceLite() function. For shared access (read only) to the list, you must use ExAcquireResourceSharedLite() function. This function checks for a thread with exclusive access to controlled resource. If so, the function may, depending on a parameter, return failure or wait until the resource to be released. To have exclusive access, use ExAcquireResourceExclusiveLite() function, which analogously checks for threads with shared access to the resource, and optionally, waits until all threads with shared access before releasing the resource for exclusive access. Finally, to release the access granted, either exclusive or shared, use the ExReleaseResourceLite() function.

An interesting point to notice is that the Kernel APC delivery must be disabled for the threads that acquire ERESOURCE. I do not know the real reason for this need, but at least it prevents the thread holding the resource from being terminated by another thread, knowing that the TerminateThread() is implemented via Kernel APC. Thus, the most common way to use these functions is as shown below.

    //-f--> Get shared access (read only).
    KeEnterCriticalRegion();
    ExAcquireResourceSharedLite(&m_Resource, TRUE);
 
    //-f--> Query the protected values.
 
    //-f--> Release the resource.
    ExReleaseResourceLite(&m_Resource);
    KeLeaveCriticalRegion();

One downside is that most of the functions that deal with ERESOURCE, unlike Spin Locks, should be called with IRQL < DISPATCH_LEVEL. Thus, perhaps some tricks are necessary when handling IRPs and their CompletionsRoutines to deal with this.

After those modifications, the system has gained a lot of performance on the tests I did. The gain will be even greater as we have more operations in parallel, and of course, on computers with more than one processor.

And everybody has lived happily ever after…

Leave a Reply