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