1 /*
2 * ReactOS Cancel-Safe Queue library
3 * Copyright (c) 2004, Vizzini (vizzini@plasmic.com)
4 * Licensed under the GNU GPL for the ReactOS project
5 *
6 * This file implements the ReactOS CSQ library. For background and overview
7 * information on these routines, read csq.h. For the authoritative reference
8 * to using these routines, see the current DDK (IoCsqXXX and CsqXxx callbacks).
9 *
10 * There are a couple of subtle races that this library is designed to avoid.
11 * Please read the code (particularly IoCsqInsertIrpEx and IoCsqRemoveIrp) for
12 * some details.
13 *
14 * In general, we try here to avoid the race between these queue/dequeue
15 * interfaces and our own cancel routine. This library supplies a cancel
16 * routine that is used in all IRPs that are queued to it. The major race
17 * conditions surround the proper handling of in-between cases, such as in-progress
18 * queue and de-queue operations.
19 *
20 * When you're thinking about these operations, keep in mind that three or four
21 * processors can have queue and dequeue operations in progress simultaneously,
22 * and a user thread may cancel any IRP at any time. Also, these operations don't
23 * all happen at DISPATCH_LEVEL all of the time, so thread switching on a single
24 * processor can create races too.
25 */
26
27 #include <ntdef.h>
28 #undef DECLSPEC_IMPORT
29 #define DECLSPEC_IMPORT
30 #include <ntifs.h>
31
32
33 /*!
34 * @brief Cancel routine that is installed on any IRP that this library manages
35 *
36 * @param DeviceObject
37 * @param Irp
38 *
39 * @note
40 * - We assume that Irp->Tail.Overlay.DriverContext[3] has either a IO_CSQ
41 * or an IO_CSQ_IRP_CONTEXT in it, but we have to figure out which it is
42 * - By the time this routine executes, the I/O Manager has already cleared
43 * the cancel routine pointer in the IRP, so it will only be canceled once
44 * - Because of this, we're guaranteed that Irp is valid the whole time
45 * - Don't forget to release the cancel spinlock ASAP --> #1 hot lock in the
46 * system
47 * - May be called at high IRQL
48 */
_Function_class_(DRIVER_CANCEL)49 _Function_class_(DRIVER_CANCEL)
50 static
51 VOID
52 NTAPI
53 IopCsqCancelRoutine(
54 _Inout_ PDEVICE_OBJECT DeviceObject,
55 _Inout_ _IRQL_uses_cancel_ PIRP Irp)
56 {
57 PIO_CSQ Csq;
58 KIRQL Irql;
59
60 /* First things first: */
61 IoReleaseCancelSpinLock(Irp->CancelIrql);
62
63 /* We could either get a context or just a csq */
64 Csq = (PIO_CSQ)Irp->Tail.Overlay.DriverContext[3];
65
66 if(Csq->Type == IO_TYPE_CSQ_IRP_CONTEXT)
67 {
68 PIO_CSQ_IRP_CONTEXT Context = (PIO_CSQ_IRP_CONTEXT)Csq;
69 Csq = Context->Csq;
70
71 /* clean up context while we're here */
72 Context->Irp = NULL;
73 }
74
75 /* Now that we have our CSQ, complete the IRP */
76 Csq->CsqAcquireLock(Csq, &Irql);
77 Csq->CsqRemoveIrp(Csq, Irp);
78 Csq->CsqReleaseLock(Csq, Irql);
79
80 Csq->CsqCompleteCanceledIrp(Csq, Irp);
81 }
82
83
84 /*!
85 * @brief Set up a CSQ struct to initialize the queue
86 *
87 * @param Csq - Caller-allocated non-paged space for our IO_CSQ to be initialized
88 * @param CsqInsertIrp - Insert routine
89 * @param CsqRemoveIrp - Remove routine
90 * @param CsqPeekNextIrp - Routine to paeek at the next IRP in queue
91 * @param CsqAcquireLock - Acquire the queue's lock
92 * @param CsqReleaseLock - Release the queue's lock
93 * @param CsqCompleteCanceledIrp - Routine to complete IRPs when they are canceled
94 *
95 * @return
96 * - STATUS_SUCCESS in all cases
97 *
98 * @note
99 * - Csq must be non-paged, as the queue is manipulated with a held spinlock
100 */
101 NTSTATUS
102 NTAPI
IoCsqInitialize(_Out_ PIO_CSQ Csq,_In_ PIO_CSQ_INSERT_IRP CsqInsertIrp,_In_ PIO_CSQ_REMOVE_IRP CsqRemoveIrp,_In_ PIO_CSQ_PEEK_NEXT_IRP CsqPeekNextIrp,_In_ PIO_CSQ_ACQUIRE_LOCK CsqAcquireLock,_In_ PIO_CSQ_RELEASE_LOCK CsqReleaseLock,_In_ PIO_CSQ_COMPLETE_CANCELED_IRP CsqCompleteCanceledIrp)103 IoCsqInitialize(
104 _Out_ PIO_CSQ Csq,
105 _In_ PIO_CSQ_INSERT_IRP CsqInsertIrp,
106 _In_ PIO_CSQ_REMOVE_IRP CsqRemoveIrp,
107 _In_ PIO_CSQ_PEEK_NEXT_IRP CsqPeekNextIrp,
108 _In_ PIO_CSQ_ACQUIRE_LOCK CsqAcquireLock,
109 _In_ PIO_CSQ_RELEASE_LOCK CsqReleaseLock,
110 _In_ PIO_CSQ_COMPLETE_CANCELED_IRP CsqCompleteCanceledIrp)
111 {
112 Csq->Type = IO_TYPE_CSQ;
113 Csq->CsqInsertIrp = CsqInsertIrp;
114 Csq->CsqRemoveIrp = CsqRemoveIrp;
115 Csq->CsqPeekNextIrp = CsqPeekNextIrp;
116 Csq->CsqAcquireLock = CsqAcquireLock;
117 Csq->CsqReleaseLock = CsqReleaseLock;
118 Csq->CsqCompleteCanceledIrp = CsqCompleteCanceledIrp;
119 Csq->ReservePointer = NULL;
120
121 return STATUS_SUCCESS;
122 }
123
124
125 /*!
126 * @brief Set up a CSQ struct to initialize the queue (extended version)
127 *
128 * @param Csq - Caller-allocated non-paged space for our IO_CSQ to be initialized
129 * @param CsqInsertIrpEx - Extended insert routine
130 * @param CsqRemoveIrp - Remove routine
131 * @param CsqPeekNextIrp - Routine to paeek at the next IRP in queue
132 * @param CsqAcquireLock - Acquire the queue's lock
133 * @param CsqReleaseLock - Release the queue's lock
134 * @param CsqCompleteCanceledIrp - Routine to complete IRPs when they are canceled
135 *
136 * @return
137 * - STATUS_SUCCESS in all cases
138 * @note
139 * - Csq must be non-paged, as the queue is manipulated with a held spinlock
140 */
141 NTSTATUS
142 NTAPI
IoCsqInitializeEx(_Out_ PIO_CSQ Csq,_In_ PIO_CSQ_INSERT_IRP_EX CsqInsertIrpEx,_In_ PIO_CSQ_REMOVE_IRP CsqRemoveIrp,_In_ PIO_CSQ_PEEK_NEXT_IRP CsqPeekNextIrp,_In_ PIO_CSQ_ACQUIRE_LOCK CsqAcquireLock,_In_ PIO_CSQ_RELEASE_LOCK CsqReleaseLock,_In_ PIO_CSQ_COMPLETE_CANCELED_IRP CsqCompleteCanceledIrp)143 IoCsqInitializeEx(
144 _Out_ PIO_CSQ Csq,
145 _In_ PIO_CSQ_INSERT_IRP_EX CsqInsertIrpEx,
146 _In_ PIO_CSQ_REMOVE_IRP CsqRemoveIrp,
147 _In_ PIO_CSQ_PEEK_NEXT_IRP CsqPeekNextIrp,
148 _In_ PIO_CSQ_ACQUIRE_LOCK CsqAcquireLock,
149 _In_ PIO_CSQ_RELEASE_LOCK CsqReleaseLock,
150 _In_ PIO_CSQ_COMPLETE_CANCELED_IRP CsqCompleteCanceledIrp)
151 {
152 Csq->Type = IO_TYPE_CSQ_EX;
153 Csq->CsqInsertIrp = (PIO_CSQ_INSERT_IRP)CsqInsertIrpEx;
154 Csq->CsqRemoveIrp = CsqRemoveIrp;
155 Csq->CsqPeekNextIrp = CsqPeekNextIrp;
156 Csq->CsqAcquireLock = CsqAcquireLock;
157 Csq->CsqReleaseLock = CsqReleaseLock;
158 Csq->CsqCompleteCanceledIrp = CsqCompleteCanceledIrp;
159 Csq->ReservePointer = NULL;
160
161 return STATUS_SUCCESS;
162 }
163
164
165 /*!
166 * @brief Insert an IRP into the CSQ
167 *
168 * @param Csq - Pointer to the initialized CSQ
169 * @param Irp - Pointer to the IRP to queue
170 * @param Context - Context record to track the IRP while queued
171 *
172 * @return
173 * - Just passes through to IoCsqInsertIrpEx, with no InsertContext
174 */
175 VOID
176 NTAPI
IoCsqInsertIrp(_Inout_ PIO_CSQ Csq,_Inout_ PIRP Irp,_Out_opt_ PIO_CSQ_IRP_CONTEXT Context)177 IoCsqInsertIrp(
178 _Inout_ PIO_CSQ Csq,
179 _Inout_ PIRP Irp,
180 _Out_opt_ PIO_CSQ_IRP_CONTEXT Context)
181 {
182 IoCsqInsertIrpEx(Csq, Irp, Context, 0);
183 }
184
185
186 /*!
187 * @brief Insert an IRP into the CSQ, with additional tracking context
188 *
189 * @param Csq - Pointer to the initialized CSQ
190 * @param Irp - Pointer to the IRP to queue
191 * @param Context - Context record to track the IRP while queued
192 * @param InsertContext - additional data that is passed through to CsqInsertIrpEx
193 *
194 * @note
195 * - Passes the additional context through to the driver-supplied callback,
196 * which can be used with more sophistocated queues
197 * - Marks the IRP pending in all cases
198 * - Guaranteed to not queue a canceled IRP
199 * - This is complicated logic, and is patterend after the Microsoft library.
200 * I'm sure I have gotten the details wrong on a fine point or two, but
201 * basically this works with the MS-supplied samples.
202 */
203 NTSTATUS
204 NTAPI
IoCsqInsertIrpEx(_Inout_ PIO_CSQ Csq,_Inout_ PIRP Irp,_Out_opt_ PIO_CSQ_IRP_CONTEXT Context,_In_opt_ PVOID InsertContext)205 IoCsqInsertIrpEx(
206 _Inout_ PIO_CSQ Csq,
207 _Inout_ PIRP Irp,
208 _Out_opt_ PIO_CSQ_IRP_CONTEXT Context,
209 _In_opt_ PVOID InsertContext)
210 {
211 NTSTATUS Retval = STATUS_SUCCESS;
212 KIRQL Irql;
213
214 Csq->CsqAcquireLock(Csq, &Irql);
215
216 do
217 {
218 /* mark all irps pending -- says so in the cancel sample */
219 IoMarkIrpPending(Irp);
220
221 /* set up the context if we have one */
222 if(Context)
223 {
224 Context->Type = IO_TYPE_CSQ_IRP_CONTEXT;
225 Context->Irp = Irp;
226 Context->Csq = Csq;
227 Irp->Tail.Overlay.DriverContext[3] = Context;
228 }
229 else
230 Irp->Tail.Overlay.DriverContext[3] = Csq;
231
232 /*
233 * NOTE! This is very sensitive to order. If you set the cancel routine
234 * *before* you queue the IRP, our cancel routine will get called back for
235 * an IRP that isn't in its queue.
236 *
237 * There are three possibilities:
238 * 1) We get an IRP, we queue it, and it is valid the whole way
239 * 2) We get an IRP, and the IO manager cancels it before we're done here
240 * 3) We get an IRP, queue it, and the IO manager cancels it.
241 *
242 * #2 is is a booger.
243 *
244 * When the IO manger receives a request to cancel an IRP, it sets the cancel
245 * bit in the IRP's control byte to TRUE. Then, it looks to see if a cancel
246 * routine is set. If it isn't, the IO manager just returns to the caller.
247 * If there *is* a routine, it gets called.
248 *
249 * If we test for cancel first and then set the cancel routine, there is a spot
250 * between test and set that the IO manager can cancel us without our knowledge,
251 * so we miss a cancel request. That is bad.
252 *
253 * If we set a routine first and then test for cancel, we race with our completion
254 * routine: We set the routine, the IO Manager sets cancel, we test cancel and find
255 * it is TRUE. Meanwhile the IO manager has called our cancel routine already, so
256 * we can't complete the IRP because it'll rip it out from under the cancel routine.
257 *
258 * The IO manager does us a favor though: it nulls out the cancel routine in the IRP
259 * before calling it. Therefore, if we test to see if the cancel routine is NULL
260 * (after we have just set it), that means our own cancel routine is already working
261 * on the IRP, and we can just return quietly. Otherwise, we have to de-queue the
262 * IRP and cancel it ourselves.
263 *
264 * We have to go through all of this mess because this API guarantees that we will
265 * never return having left a canceled IRP in the queue.
266 */
267
268 /* Step 1: Queue the IRP */
269 if(Csq->Type == IO_TYPE_CSQ)
270 Csq->CsqInsertIrp(Csq, Irp);
271 else
272 {
273 PIO_CSQ_INSERT_IRP_EX pCsqInsertIrpEx = (PIO_CSQ_INSERT_IRP_EX)Csq->CsqInsertIrp;
274 Retval = pCsqInsertIrpEx(Csq, Irp, InsertContext);
275 if(Retval != STATUS_SUCCESS)
276 break;
277 }
278
279 /* Step 2: Set our cancel routine */
280 (void)IoSetCancelRoutine(Irp, IopCsqCancelRoutine);
281
282 /* Step 3: Deal with an IRP that is already canceled */
283 if(!Irp->Cancel)
284 break;
285
286 /*
287 * Since we're canceled, see if our cancel routine is already running
288 * If this is NULL, the IO Manager has already called our cancel routine
289 */
290 if(!IoSetCancelRoutine(Irp, NULL))
291 break;
292
293
294 Irp->Tail.Overlay.DriverContext[3] = 0;
295
296 /* OK, looks like we have to de-queue and complete this ourselves */
297 Csq->CsqRemoveIrp(Csq, Irp);
298 Csq->CsqCompleteCanceledIrp(Csq, Irp);
299
300 if(Context)
301 Context->Irp = NULL;
302 }
303 while(0);
304
305 Csq->CsqReleaseLock(Csq, Irql);
306
307 return Retval;
308 }
309
310
311 /*!
312 * @brief Remove anb IRP from the queue
313 *
314 * @param Csq - Queue to remove the IRP from
315 * @param Context - Context record containing the IRP to be dequeued
316 *
317 * @return
318 * - Pointer to an IRP if we found it
319 *
320 * @note
321 * - Don't forget that we can be canceled any time up to the point
322 * where we unset our cancel routine
323 */
324 PIRP
325 NTAPI
IoCsqRemoveIrp(_Inout_ PIO_CSQ Csq,_Inout_ PIO_CSQ_IRP_CONTEXT Context)326 IoCsqRemoveIrp(
327 _Inout_ PIO_CSQ Csq,
328 _Inout_ PIO_CSQ_IRP_CONTEXT Context)
329 {
330 KIRQL Irql;
331 PIRP Irp = NULL;
332
333 Csq->CsqAcquireLock(Csq, &Irql);
334
335 do
336 {
337 /* It's possible that this IRP could have been canceled */
338 Irp = Context->Irp;
339
340 if(!Irp)
341 break;
342
343 ASSERT(Context->Csq == Csq);
344
345 /* Unset the cancel routine and see if it has already been canceled */
346 if(!IoSetCancelRoutine(Irp, NULL))
347 {
348 /*
349 * already gone, return NULL --> NOTE that we cannot touch this IRP *or* the context,
350 * since the context is being simultaneously twiddled by the cancel routine
351 */
352 Irp = NULL;
353 break;
354 }
355
356 ASSERT(Context == Irp->Tail.Overlay.DriverContext[3]);
357
358 /* This IRP is valid and is ours. Dequeue it, fix it up, and return */
359 Csq->CsqRemoveIrp(Csq, Irp);
360
361 Context = (PIO_CSQ_IRP_CONTEXT)InterlockedExchangePointer(&Irp->Tail.Overlay.DriverContext[3], NULL);
362
363 if (Context && Context->Type == IO_TYPE_CSQ_IRP_CONTEXT)
364 {
365 Context->Irp = NULL;
366
367 ASSERT(Context->Csq == Csq);
368 }
369
370 Irp->Tail.Overlay.DriverContext[3] = 0;
371 }
372 while(0);
373
374 Csq->CsqReleaseLock(Csq, Irql);
375
376 return Irp;
377 }
378
379 /*!
380 * @brief IoCsqRemoveNextIrp - Removes the next IRP from the queue
381 *
382 * @param Csq - Queue to remove the IRP from
383 * @param PeekContext - Identifier of the IRP to be removed
384 *
385 * @return
386 * Pointer to the IRP that was removed, or NULL if one
387 * could not be found
388 *
389 * @note
390 * - This function is sensitive to yet another race condition.
391 * The basic idea is that we have to return the first IRP that
392 * we get that matches the PeekContext >that is not already canceled<.
393 * Therefore, we have to do a trick similar to the one done in Insert
394 * above.
395 */
396 PIRP
397 NTAPI
IoCsqRemoveNextIrp(_Inout_ PIO_CSQ Csq,_In_opt_ PVOID PeekContext)398 IoCsqRemoveNextIrp(
399 _Inout_ PIO_CSQ Csq,
400 _In_opt_ PVOID PeekContext)
401 {
402 KIRQL Irql;
403 PIRP Irp = NULL;
404 PIO_CSQ_IRP_CONTEXT Context;
405
406 Csq->CsqAcquireLock(Csq, &Irql);
407
408 while((Irp = Csq->CsqPeekNextIrp(Csq, Irp, PeekContext)))
409 {
410 /*
411 * If the cancel routine is gone, we're already canceled,
412 * and are spinning on the queue lock in our own cancel
413 * routine. Move on to the next candidate. It'll get
414 * removed by the cance routine.
415 */
416 if(!IoSetCancelRoutine(Irp, NULL))
417 continue;
418
419 Csq->CsqRemoveIrp(Csq, Irp);
420
421 /* Unset the context stuff and return */
422 Context = (PIO_CSQ_IRP_CONTEXT)InterlockedExchangePointer(&Irp->Tail.Overlay.DriverContext[3], NULL);
423
424 if (Context && Context->Type == IO_TYPE_CSQ_IRP_CONTEXT)
425 {
426 Context->Irp = NULL;
427
428 ASSERT(Context->Csq == Csq);
429 }
430
431 Irp->Tail.Overlay.DriverContext[3] = 0;
432
433 break;
434 }
435
436 Csq->CsqReleaseLock(Csq, Irql);
437
438 return Irp;
439 }
440
441