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