How The Race Was Lost

I’ve been told by a reader of this modest little web log that I have shirked my duties by not getting this post up before midnight (my time, which is GMT-6). Because of this oversight on my part, I have failed to make my minimum one post per day. My heartfelt apologies to all three of you who read this blog at this point; I’ll try to never let it happen again. 🙂

I promised you yesterday that I’d describe some of the Hell of the Cancel Race. In fact, I hope you never have to care about this stuff because you”ve taken my advice and used CSQs in your driver. With that said, the idea basically goes like this.

Say you are a driver that needs to keep a hold of IRPs as they come in. For some reason or other, you are either unable or unwilling to complete the IRPs in their original thread contexts (i.e. synchronously). Therefore, you need a place to stash them before you return to the caller (with STATUS_PENDING). Say you use a trivial linked list to queue up these IRPs for later processing (using the Tail.Overlay.ListEntry generously supplied by Microsoft). For one reason or another, your driver needs to wait a “long” time before it will finally get around to servicing these queued IRPs, so they stay queued for a while. What will happen if someoone above you decides he’s tired of waiting for you? He will, of course, cancel his request.

To cancel his request, the originator of the IRP will call IoCancelIrp(). This, in turn, causes the IO manager to look inside the IRP for a CancelRoutine (look up Cancel in the DDK for details). If this routine is present, the IO manager will do some bookkeeping and call the routine. That routine is the way a driver finds out that someone above it wants to cancel that IRP. This driver would then presumably dequeue the IRP from the list and complete it (STATUS_CANCELLED) up the chain.

The problem arises because of the fact that your cancel routine can be called at essentially any time after it is set on the IRP (via IoSetCancelRoutine()). It will want to manipulate the same linked list that your dispatch routines are using to queue and dequeue IRPs normally. Furthermore, there are races with the IO manager between the calling of IoSetCancelRoutine() and enqueuing the IRP, and between dequeuing the IRP and calling IoSetCancelRoutine() to clear the cancel routine. Remember, multiple processors can be manipulating the queue simultaneously, so you could have 3 or 4 enqueue/dequeue operations going on at a time, and a couple of cancellations pending.

One detailed example: Suppose you receive an IRP that you decide to queue. If you set the cancel routine first, the IO manager might call the routine before you queue the IRP. Then your cancel routine gets called and tries to de-queue an IRP that isn’t on the queue at all. On the other hand, If you queue the IRP first and then set the cancel routine, your dequeuing thread might dequeue the IRP and complete it before you get a chance to set the cancel routine. You then set a cancel routine, and the IO manager savagely rips your IRP out from under ou while you’re processing it. Have fun running down that crash!

You can manage the situation appropriately with locks, but organizing your use of those locks in such a way that you won’t race is exactly what is so difficult about this problem. The proper solution winds up requiring an interlocked pointer exchange with the CancelRoutine pointer in the IRP, and determining if it was previously NULL (which signals that the IO manager has called the CancelRoutine already). You also have to properly handle the BOOLEAN Cancelled flag in the IRP, which has its own semantics.

Instead of all of that work, why not just call IoAcquireCancelSpinLock() and IoReleaseCancelSpinLock()? Well, a couple of reasons. First, even *that* locking mechanism can be used incorrectly, leading to another tricky race. But even more than that, the cancel lock is a system-wide resource – it is the #1 hot lock in the entire OS. Think about it – the cancel lock has to be acquired by the IO manager every time an IRP is cancelled, at least for a little while (i.e. until the cancel routine calls IoReleaseCancelSpinLock()). Contention for this lock can become a serious bottleneck in your driver’s performance. Much better to wait on a driver-owned lock, or even better, an in-stack queued spinlock (more on that another day).

This is really just a start; the only way to really wrap your brain around the cancel races is to try and code cancel logic yourself. Read the DDK docs on all of these functions mentioned here, as well as the general sections on IRP queuing and cancellation. There are other resources on the Internet as well (google for “cancel-safe queues”). Finally, once again, Walter Oney has an excellent IRP cancellation chapter in his WDM book, and (IIRC) even provides source to his queuing logic.

Next up: an example of CSQ usage.

Happy hacking!

Leave a Reply

Your email address will not be published. Required fields are marked *