Queuing IO Requests | Programming the Microsoft Windows Driver Model

Queuing I/O Requests

Sometimes your driver receives an IRP that it can t handle right away. Rather than reject the IRP by causing it to fail with an error status, your dispatch routine places the IRP on a queue. In another part of your driver, you provide logic that removes one IRP from the queue and passes it to a StartIo routine.

Microsoft Queuing Routines

Apart from this sidebar, I m omitting discussion of the functions IoStartPacket and IoStartNextPacket, which have been part of Windows NT since the beginning. These functions implement a queuing model that s inappropriate for WDM drivers. In that model, a device is in one of three states: idle, busy with an empty queue, or busy with a nonempty queue. If you call IoStartPacket at a time when the device is idle, it unconditionally sends the IRP to your StartIo routine. Unfortunately, many times a WDM driver needs to queue an IRP even though the device is idle. These functions also rely heavily on a global spin lock whose overuse has created a serious performance bottleneck.

Just in case you happen to be working on an old driver that uses these obsolete routines, however, here s how they work. A dispatch routine would queue an IRP like this:

NTSTATUS DispatchSomething(PDEVICE_OBJECT fdo, PIRP Irp) { IoMarkIrpPending(Irp); IoStartPacket(fdo, Irp, NULL, CancelRoutine); return STATUS_PENDING; }

Your driver would have a single StartIo routine. Your DriverEntry routine would set the DriverStartIo field of the driver object to point to this routine. If your StartIo routine completes IRPs, you would also call IoSetStart IoAttributes (in Windows XP or later) to help prevent excessive recursion into StartIo. IoStartPacket and IoStartNextPacket call StartIo to process one IRP at a time. In other words, StartIo is the place where the I/O manager serializes access to your hardware.

A DPC routine (see the later discussion of how DPC routines work) would complete the previous IRP and start the next one using this code:

VOID DpcForIsr(PKDPC junk, PDEVICE_OBJECT fdo, PIRP Irp, PVOID morejunk) { IoCompleteRequest(Irp, STATUS_NO_INCREMENT); IoStartNextPacket(fdo, TRUE); }

To provide for canceling a queued IRP, you would need to write a cancel routine. Illustrating that and the cancel logic in StartIo is beyond the scope of this book.

In addition, you can rely on the CurrentIrp field of a DEVICE_OBJECT to always contain NULL or the address of the IRP most recently sent (by IoStartPacket or IoStartNextPacket) to your StartIo routine.

Queuing an IRP is conceptually very simple. You can provide a list anchor in your device extension, which you initialize in your AddDevice function:

typedef struct _DEVICE_EXTENSION {  LIST_ENTRY IrpQueue; BOOLEAN DeviceBusy; } DEVICE_EXTENSION, *PDEVICE_EXTENSION; NTSTATUS AddDevice(...) {  InitializeListHead(&pdx->IrpQueue);  }

Then you can write two naive routines for queuing and dequeuing IRPs:

VOID NaiveStartPacket(PDEVICE_EXTENSION pdx, PIRP Irp) { if (pdx->DeviceBusy) InsertTailList(&pdx->IrpQueue, &Irp->Tail.Overlay.ListEntry); else { pdx->DeviceBusy = TRUE; StartIo(pdx->DeviceObject, Irp); } } VOID NaiveStartNextPacket(PDEVICE_EXTENSION pdx, PIRP Irp) { if (IsListEmpty(&pdx->IrpQueue)) pdx->DeviceBusy = FALSE; else { PLIST_ENTRY foo = RemoveHeadList(&pdx->IrpQueue); PIRP Irp = CONTAINING_RECORD(foo, IRP, Tail.Overlay.ListEntry); StartIo(pdx->DeviceObject, Irp); } }

Then your dispatch routine calls NaiveStartPacket, and your DPC routine calls NaiveStartNextPacket in the manner discussed earlier in connection with the standard model.

There are many problems with this scheme, which is why I called it naive. The most basic problem is that your DPC routine and multiple instances of your dispatch routine could all be simultaneously active on different CPUs. They would likely conflict in trying to access the queue and the busy flag. You could address that problem by creating a spin lock and using it to guard against the obvious races, as follows:

typedef struct _DEVICE_EXTENSION {  LIST_ENTRY IrpQueue; KSPIN_LOCK IrpQueueLock; BOOLEAN DeviceBusy; } DEVICE_EXTENSION, *PDEVICE_EXTENSION; NTSTATUS AddDevice(...) {  InitializeListHead(&pdx->IrpQueue); KeInitializeSpinLock(&pdx->IrpQueueLock);   } VOID LessNaiveStartPacket(PDEVICE_EXTENSION pdx, PIRP Irp) { KIRQL oldirql; KeAcquireSpinLock(&pdx->IrpQueueLock, &oldirql); if (pdx->DeviceBusy) { InsertTailList(&pdx->IrpQueue, &Irp->Tail.Overlay.ListEntry; KeReleaseSpinLock(&pdx->IrpQueueLock, oldirql); } else { pdx->DeviceBusy = TRUE; KeReleaseSpinLock(&pdx->IrpQueueLock, DISPATCH_LEVEL); StartIo(pdx->DeviceObject, Irp); KeLowerIrql(oldirql); } } VOID LessNaiveStartNextPacket(PDEVICE_EXTENSION pdx, PIRP Irp) { KIRQL oldirql; KeAcquireSpinLock(&pdx->IrpQueueLock, &oldirql); if (IsListEmpty(&pdx->IrpQueue) { pdx->DeviceBusy = FALSE; KeReleaseSpinLock(&pdx->IrpQueueLock, oldirql); else { PLIST_ENTRY foo = RemoveHeadList(&pdx->IrpQueue); KeReleaseSpinLock(&pdx->IrpQueueLock, DISPATCH_LEVEL); PIRP Irp = CONTAINING_RECORD(foo, IRP, Tail.Overlay.ListEntry); StartIo(pdx->DeviceObject, Irp); KeLowerIrql(oldirql); } }

Incidentally, we always want to call StartIo at a single IRQL. Because DPC routines are among the callers of LessNaiveStartNextPacket, and they run at DISPATCH_LEVEL, we pick DISPATCH_LEVEL. That means we want to stay at DISPATCH_LEVEL when we release the spin lock.

(You did remember that these two queue management routines need to be in nonpaged memory because they run at DISPATCH_LEVEL, right?)

These queueing routines are actually almost OK, but they have one more defect and a shortcoming. The shortcoming is that we need a way to stall a queue for the duration of certain PnP and Power states. IRPs accumulate in a stalled queue until someone unstalls the queue, whereupon the queue manager can resume sending IRPs to a StartIo routine. The defect in the less naive set of routines is that someone could decide to cancel an IRP at essentially any time. IRP cancellation complicates IRP queuing logic so much that I ve devoted the next major section to discussing it. Before we get to that, though, let me explain how to use the queuing routines that I crafted to deal with all the problems.

Using the DEVQUEUE Object

To solve a variety of IRP queuing problems, I created a package of subroutines for managing a queue object that I call a DEVQUEUE. I ll show you first the basic usage of a DEVQUEUE. Later in this chapter, I ll explain how the major DEVQUEUE service routines work. I ll discuss in later chapters how your PnP and power management code interacts with the DEVQUEUE object or objects you define.

You define a DEVQUEUE object for each queue of requests you ll manage in the driver. For example, if your device manages reads and writes in a single queue, you define one DEVQUEUE:

typedef struct _DEVICE_EXTENSION {  DEVQUEUE dqReadWrite;  } DEVICE_EXTENSION, *PDEVICE_EXTENSION;

On the CD Code for the DEVQUEUE is part of GENERIC.SYS. In addition, if you use my WDMWIZ to create a skeleton driver and don t ask for GENERIC.SYS support, your skeleton project will include the files DEVQUEUE.CPP and DEVQUEUE.H, which fully implement exactly the same object. I don t recommend trying to type this code from the book because the code from the companion content will contain even more features than I can describe in the book. I also recommend checking my Web site (www.oneysoft.com) for updates and corrections.

Figure 5-8 illustrates the IRP processing logic for a typical driver using DEVQUEUE objects. Each DEVQUEUE has its own StartIo routine, which you specify when you initialize the object in AddDevice:

NTSTATUS AddDevice(...) {  PDEVICE_EXTENSION pdx = ...; InitializeQueue(&pdx->dqReadWrite, StartIo);  }

figure 5-8 irp flow with a devqueue and a startio routine.

Figure 5-8. IRP flow with a DEVQUEUE and a StartIo routine.

You can specify a common dispatch function for both IRP_MJ_READ and IRP_MJ_WRITE:

NTSTATUS DriverEntry(PDRIVER_OBJECT DriverObject, PUNICODE_STRING RegistryPath) {  DriverObject->MajorFunction[IRP_MJ_READ] = DispatchReadWrite; DriverObject->MajorFunction[IRP_MJ_WRITE] = DispatchReadWrite;  } #pragma PAGEDCODE NTSTATUS DispatchReadWrite(PDEVICE_OBJECT fdo, PIRP Irp) { PAGED_CODE(); PDEVICE_EXTENSION pdx = (PDEVICE_EXTENSION) fdo->DeviceExtension; IoMarkIrpPending(Irp); StartPacket(&pdx->dqReadWrite, fdo, Irp, CancelRoutine); return STATUS_PENDING; } #pragma LOCKEDCODE VOID CancelRoutine(PDEVICE_OBJECT fdo, PIRP Irp) { PDEVICE_EXTENSION pdx = (PDEVICE_EXTENSION) fdo->DeviceExtension; CancelRequest(&pdx->dqReadWrite, Irp); }

Note that the cancel argument to StartPacket is not optional: you must supply a cancel routine, but you can see how simple that routine will be.

If you complete IRPs in a DPC routine, you ll also call StartNextPacket:

VOID DpcForIsr(PKPDC junk1, PDEVICE_OBJECT fdo, PIRP junk2, PDEVICE_EXTENSION pdx) {  StartNextPacket(&pdx->dqReadWrite, fdo); }

If you complete IRPs in your StartIo routine, schedule a DPC to make the call to StartNextPacket in order to avoid excessive recursion. For example:

typedef struct _DEVICE_EXTENSION {  KDPC StartNextDpc; } DEVICE_EXTENSION, *PDEVICE_EXTENSION; NTSTATUS AddDevice(...) {  KeInitializeDpc(&pdx->StartNextDpc, (PKDEFERRED_ROUTINE) StartNextDpcRoutine, pdx);  } VOID StartIo(...) {  IoCompleteRequest(...); KeInsertQueueDpc(&pdx->StartNextDpc, NULL, NULL); } VOID StartNextDpcRoutine(PKDPC junk1, PDEVICE_EXTENSION pdx, PVOID junk2, PVOID junk3) { StartNextPacket(&pdx->dqReadWrite, pdx->DeviceObject); }

In this example, StartIo calls IoCompleteRequest to complete the IRP it has just handled. Calling StartNextPacket directly might lead to a recursive call to StartIo. After enough recursive calls, we ll run out of stack. To avoid the potential stack overflow, we queue the StartNextDpc DPC object and return. Because StartIo runs at DISPATCH_LEVEL, it won t be possible for the DPC routine to be called before StartIo returns. Therefore, StartNextDpcRoutine can call StartNext Packet without worrying about recursion.

NOTE
If you were using the Microsoft queue routines IoStartPacket and IoStartNextPacket, you d have a single StartIo routine. Your DriverEntry routine would set the DriverStartIo pointer in the driver object to the address of this routine. To avoid the recursion problem discussed in the text in Windows XP or later, you could call IoSetStartIoAttributes.

Using Cancel-Safe Queues

Some drivers work better if they operate with a separate I/O thread. Such a thread wakes up each time there is an IRP to be processed, processes IRPs until a queue is empty, and then goes back to sleep. I ll discuss the details of how such a thread routine works in Chapter 14, but this is the appropriate time to talk about how you can queue IRPs in such a driver. See Figure 5-9.

A DEVQUEUE isn t appropriate for this situation because the DEVQUEUE wants to call a StartIo routine to process IRPs. When you have a separate I/O thread, you want to be responsible in that thread for fetching IRPs. Microsoft provides a set of routines for cancel-safe queue operations that provide most of the functionality you need. These routines don t work automatically with your PnP and Power logic, but I predict it won t be hard to add such support. The Cancel sample in the DDK shows how to work with a cancel-safe queue in exactly this situation, but I ll go over the mechanics here as well.

figure 5-9 irp flow with an i/o thread.

Figure 5-9. IRP flow with an I/O thread.

NOTE
In their original incarnation, the cancel-safe queue functions weren t appropriate when you wanted to use a StartIo routine for actual I/O because they didn t provide a way to set a CurrentIrp pointer and do a queue operation inside one invocation of the queue lock. They were modified while I was wrirting this book to support StartIo usage, but we didn t have time to include an explanation of how to use the new features. I commend you, therefore, to the DDK documentation.

Note also that the cancel-safe queue functions were first described in an XP release of the DDK. They are implemented in a static library, however, and are therefore available for use on all prior platforms.

Initialization for Cancel-Safe Queue

To take advantage of the cancel-safe queue functions, first declare six helper functions (see Table 5-5) that the I/O Manager can call to perform operations on your queue. Declare an instance of the IO_CSQ structure in your device extension structure. Also declare an anchor for your IRP queue and whichever synchronization object you want to use. You initialize these objects in your AddDevice function. For example:

typedef struct _DEVICE_EXTENSION {  IO_CSQ IrpQueue; LIST_ENTRY IrpQueueAnchor; KSPIN_LOCK IrpQueueLock;  } DEVICE_EXTENSION, *PDEVICE_EXTENSION; NTSTATUS AddDevice(PDRIVER_OBJECT DriverObject, PDEVICE_OBJECT pdo) {  KeInitializeSpinLock(&pdx->IrpQueueLock); InitializeListHead(&pdx->IrpQueueAnchor); IoCsqInitialize(&pdx->IrpQueue, InsertIrp, RemoveIrp, PeekNextIrp, AcquireLock, ReleaseLock, CompleteCanceledIrp);  }

Table 5-5. Cancel-Safe Queue Callback Routines
Callback Routine	Purpose
AcquireLock	Acquire lock on the queue
CompleteCanceledIrp	Complete an IRP that has been cancelled
InsertIrp	Insert IRP into queue
PeekNextIrp	Retrieve pointer to next IRP in queue without removing it
ReleaseLock	Release queue lock
RemoveIrp	Remove IRP from queue

Using the Queue

You queue an IRP in a dispatch routine like this:

NTSTATUS DispatchSomething(PDEVICE_OBJECT fdo, PIRP Irp) { PDEVICE_EXTENSION pdx = (PDEVICE_EXTENSION) fdo->DeviceExtension; IoCsqInsertIrp(&pdx->IrpQueue, Irp, NULL); return STATUS_PENDING; }

It s unnecessary and incorrect to call IoMarkIrpPending yourself because IoCsqInsertIrp does so automatically. As is true with other queuing schemes, the IRP might be complete by the time IoCsqInsertIrp returns, so don t touch the pointer afterwards.

To remove an IRP from the queue (say, in your I/O thread), use this code:

PIRP Irp = IoCsqRemoveNextIrp(&pdx->IrpQueue, PeekContext);

I ll describe the PeekContext argument a bit further on. Note that the return value is NULL if no IRPs on are on the queue. The IRP you get back hasn t been cancelled, and any future call to IoCancelIrp is guaranteed to do nothing more than set the Cancel flag in the IRP.

You ll also want to provide a dispatch routine for IRP_MJ_CLEANUP that will interact with the queue. I ll show you code for that purpose a bit later in this chapter.

Cancel-Safe Queue Callback Routines

The I/O Manager calls your cancel-safe queue callback routines with the address of the queue object as one of the arguments. To recover the address of your device extension structure, use the CONTAINING_RECORD macro:

#define GET_DEVICE_EXTENSION(csq) \ CONTAINING_RECORD(csq, DEVICE_EXTENSION, IrpQueue)

You supply callback routines for acquiring and releasing the lock you ve decided to use for your queue. For example, if you had settled on using a spin lock, you d write these two routines:

VOID AcquireLock(PIO_CSQ csq, PKIRQL Irql) { PDEVICE_EXTENSION pdx = GET_DEVICE_EXTENSION(csq); KeAcquireSpinLock(&pdx->IrpQueueLock, Irql); } VOID ReleaseLock(PIO_CSQ csq, KIRQL Irql) { PDEVICE_EXTENSION pdx = GET_DEVICE_EXTENSION(csq); KeReleaseSpinLock(&pdx->IrpQueueLock, Irql); }

You don t have to use a spin lock for synchronization, though. You can use a mutex, a fast mutex, or any other object that suits your fancy.

When you call IoCsqInsertIrp, the I/O Manager locks your queue by calling your AcquireLock routine and then calls your InsertIrp routine:

VOID InsertIrp(PIO_CSQ csq, PIRP Irp) { PDEVICE_EXTENSION pdx = GET_DEVICE_EXTENSION(csq); InsertTailList(&pdx->IrpQueueAnchor, &Irp->Tail.Overlay.ListEntry); }

When you call IoCsqRemoveNextIrp, the I/O Manager locks your queue and calls your PeekNextIrp and RemoveIrp functions:

PIRP PeekNextIrp(PIO_CSQ csq, PIRP Irp, PVOID PeekContext) { PDEVICE_EXTENSION pdx = GET_DEVICE_EXTENSION(csq); PLIST_ENTRY next = Irp ? Irp->Tail.Overlay.ListEntry.Flink : pdx->IrpQueueAnchor.Flink; while (next != &pdx->IrpQueueAnchor) { PIRP NextIrp = CONTAINING_RECORD(next, IRP, Tail.Overlay.ListEntry); if (PeekContext && <NextIrp matches PeekContext>) return NextIrp; if (!PeekContext) return NextIrp; next = next->Flink; } return NULL; } VOID RemoveIrp(PIO_CSQ csq, PIRP Irp) { RemoveEntryList(&Irp->Tail.Overlay.ListEntry); }

The parameters to PeekNextIrp require a bit of explanation. Irp, if not NULL, is the predecessor of the first IRP you should look at. If Irp is NULL, you should look at the IRP at the front of the list. PeekContext is an arbitrary parameter that you can use for any purpose you want as a way for the caller of IoCsqRemoveNextIrp to communicate with PeekNextIrp. A common convention is to use this argument to point to a FILE_OBJECT that s the current subject of an IRP_MJ_CLEANUP. I wrote this function so that a NULL value for PeekContext means, Return the next IRP, period. A non-NULL value means, Return the next value that matches PeekContext. You define what it means to match the peek context.

The sixth and last callback function is this one, which the I/O Manager calls when an IRP needs to be cancelled:

VOID CompleteCanceledIrp(PIO_CSQ csq, PIRP Irp) { PDEVICE_EXTENSION pdx = GET_DEVICE_EXTENSION(csq); Irp->IoStatus.Status = STATUS_CANCELLED; Irp->IoStatus.Information = 0; IoCompleteRequest(Irp, IO_NO_INCREMENT); }

That is, all you do is complete the IRP with STATUS_CANCELLED.

To reiterate, the advantage you gain by using the cancel-safe queue functions is that you don t need to write a cancel routine, and you don t need to include any code in your driver (apart from the CompleteCanceledIrp function, that is) that relates to cancelling queued IRPs. The I/O Manager installs its own cancel routine, and it promises never to deliver a cancelled IRP back from IoCsqRemoveNextIrp.

Parking an IRP on a Cancel-Safe Queue

The preceding sections described how you can use a cancel-safe queue to serialize I/O processing in a kernel thread. Another way to use the cancel-safe queue functions is for parking IRPs while you process them. The idea is that you would place the IRP into the queue when you first received it. Then, when it comes time to complete the IRP, you remove that specific IRP from the queue. You re not using the queue as a real queue in this scenario, because you don t pay any attention to the order of the IRPs in the queue.

To park an IRP, define a persistent context structure for use by the cancel-safe queue package. You need one such structure for each separate IRP that you plan to park. Suppose, for example, that your driver processes red requests and blue requests (fanciful names to avoid the baggage that real examples sometimes bring along with them).

typedef struct _DEVICE_EXTENSION {  IO_CSQ_IRP_CONTEXT RedContext; IO_CSQ_IRP_CONTEXT BlueContext; } DEVICE_EXTENSION, *PDEVICE_EXTENSION;

When you receive a red IRP, you specify the context structure in your call to IoCsqInsertIrp:

IoCsqInsertIrp(&pdx->IrpQueue, RedIrp, &pdx->RedContext);

How to park a blue IRP should be pretty obvious.

When you later decide you want to complete a parked IRP, you write code like this:

PIRP RedIrp = IoCsqRemoveIrp(&pdx->IrpQueue, &pdx->RedContext); if (RedIrp) { RedIrp->IoStatus.Status = STATUS_XXX; RedIrp->IoStatus.Information = YYY; IoCompleteRequest(RedIrp, IO_NO_INCREMENT); }

IoCsqRemoveIrp will return NULL if the IRP associated with the context structure has already been cancelled.

Bear in mind the following caveats when using this mechanism:

It s up to you to make sure that you haven t previously parked an IRP using a particular context structure. IoCsqInsertIrp is a VOID function and therefore has no way to tell you when you violate this rule.
You mustn t touch an I/O buffer associated with a parked IRP because the IRP can be cancelled (and the I/O buffer released!) at any time while it s parked. You should remove the IRP from the queue before trying to use a buffer.