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 #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