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