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