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