reactos/ntoskrnl/ke/kqueue.c

   1 /*
   2  * COPYRIGHT:       See COPYING in the top level directory
   3  * PURPOSE:         ReactOS kernel
   4  * FILE:            ntoskrnl/ke/kqueue.c
   5  * PURPOSE:         Implement device queues
   6  *
   7  * PROGRAMMERS:     Alex Ionescu (alex@relsoft.net) - Several optimizations and implement
   8  *                                                    usage of Inserted flag + reformat and
   9  *                                                    add debug output.
  10  *                  David Welch (welch@mcmail.com)
  11  */
  12
  13 /* INCLUDES ****************************************************************/
  14
  15 #include <ntoskrnl.h>
  16 #define NDEBUG
  17 #include <internal/debug.h>
  18
  19 /* FUNCTIONS *****************************************************************/
  20
  21 /*
  22  * @implemented
  23  *
  24  * FUNCTION: Intializes a device queue
  25  * ARGUMENTS:
  26  *       DeviceQueue = Device queue to initialize
  27  */
  28 VOID
  29 STDCALL
  30 KeInitializeDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue)
  31 {
  32
  33     /* Initialize the Header */
  34     DeviceQueue->Type = DeviceQueueObject;
  35     DeviceQueue->Size = sizeof(KDEVICE_QUEUE);
  36
  37     /* Initialize the Listhead and Spinlock */
  38     InitializeListHead(&DeviceQueue->DeviceListHead);
  39     KeInitializeSpinLock(&DeviceQueue->Lock);
  40
  41     /* Set it as busy */
  42     DeviceQueue->Busy=FALSE;
  43 }
  44
  45 /*
  46  * @implemented
  47  *
  48  * FUNCTION: Inserts an entry in a device queue
  49  * ARGUMENTS:
  50  *        DeviceQueue = Queue to insert the entry in
  51  *        DeviceQueueEntry = Entry to insert
  52  * RETURNS: False is the device queue wasn't busy
  53  *          True otherwise
  54  */
  55 BOOLEAN
  56 STDCALL
  57 KeInsertDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue,
  58                     IN PKDEVICE_QUEUE_ENTRY DeviceQueueEntry)
  59 {
  60     BOOLEAN Inserted;
  61
  62     DPRINT("KeInsertDeviceQueue(DeviceQueue %x)\n", DeviceQueue);
  63     ASSERT(KeGetCurrentIrql() == DISPATCH_LEVEL);
  64
  65     /* Lock the Queue */
  66     KeAcquireSpinLockAtDpcLevel(&DeviceQueue->Lock);
  67
  68     if (!DeviceQueue->Busy) {
  69
  70         /* Set it as busy */
  71         Inserted = FALSE;
  72         DeviceQueue->Busy = TRUE;
  73
  74     } else {
  75
  76         /* Insert it into the list */
  77         Inserted = TRUE;
  78         InsertTailList(&DeviceQueue->DeviceListHead,
  79                        &DeviceQueueEntry->DeviceListEntry);
  80
  81
  82     }
  83
  84     /* Sert the Insert state into the entry */
  85     DeviceQueueEntry->Inserted = Inserted;
  86
  87     /* Release lock and return */
  88     KeReleaseSpinLockFromDpcLevel(&DeviceQueue->Lock);
  89     return Inserted;
  90 }
  91
  92 /*
  93  * @implemented
  94  */
  95 BOOLEAN
  96 STDCALL
  97 KeInsertByKeyDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue,
  98                          IN PKDEVICE_QUEUE_ENTRY DeviceQueueEntry,
  99                          IN ULONG SortKey)
 100 {
 101     BOOLEAN Inserted;
 102
 103     DPRINT("KeInsertByKeyDeviceQueue(DeviceQueue %x)\n", DeviceQueue);
 104     ASSERT(KeGetCurrentIrql() == DISPATCH_LEVEL);
 105
 106     /* Acquire the Lock */
 107     KeAcquireSpinLockAtDpcLevel(&DeviceQueue->Lock);
 108
 109     /* Set the Sort Key */
 110     DeviceQueueEntry->SortKey=SortKey;
 111
 112     if (!DeviceQueue->Busy) {
 113
 114         DeviceQueue->Busy=TRUE;
 115         Inserted = FALSE;
 116
 117     } else {
 118
 119         /* Insert new entry after the last entry with SortKey less or equal to passed-in SortKey */
 120         InsertAscendingListFIFO(&DeviceQueue->DeviceListHead,
 121                                 KDEVICE_QUEUE_ENTRY,
 122                                 DeviceListEntry,
 123                                 DeviceQueueEntry,
 124                                 SortKey);
 125         Inserted = TRUE;
 126     }
 127
 128     /* Reset the Inserted State */
 129     DeviceQueueEntry->Inserted = Inserted;
 130
 131     /* Release Lock and Return */
 132     KeReleaseSpinLockFromDpcLevel(&DeviceQueue->Lock);
 133     return Inserted;
 134 }
 135
 136 /*
 137  * @implemented
 138  *
 139  * FUNCTION: Removes an entry from a device queue
 140  * ARGUMENTS:
 141  *        DeviceQueue = Queue to remove the entry
 142  * RETURNS: The removed entry
 143  */
 144 PKDEVICE_QUEUE_ENTRY
 145 STDCALL
 146 KeRemoveDeviceQueue(IN PKDEVICE_QUEUE   DeviceQueue)
 147 {
 148     PLIST_ENTRY ListEntry;
 149     PKDEVICE_QUEUE_ENTRY ReturnEntry;
 150
 151     DPRINT("KeRemoveDeviceQueue(DeviceQueue %x)\n", DeviceQueue);
 152     ASSERT(KeGetCurrentIrql() == DISPATCH_LEVEL);
 153
 154     /* Acquire the Lock */
 155     KeAcquireSpinLockAtDpcLevel(&DeviceQueue->Lock);
 156     ASSERT(DeviceQueue->Busy);
 157
 158     /* An attempt to remove an entry from an empty (and busy) queue sets the queue idle */
 159     if (IsListEmpty(&DeviceQueue->DeviceListHead)) {
 160         DeviceQueue->Busy = FALSE;
 161         ReturnEntry = NULL;
 162
 163    } else {
 164
 165         /* Remove the Entry from the List */
 166         ListEntry = RemoveHeadList(&DeviceQueue->DeviceListHead);
 167         ReturnEntry = CONTAINING_RECORD(ListEntry,
 168                                         KDEVICE_QUEUE_ENTRY,
 169                                         DeviceListEntry);
 170
 171         /* Set it as non-inserted */
 172         ReturnEntry->Inserted = FALSE;
 173     }
 174
 175     /* Release lock and Return */
 176     KeReleaseSpinLockFromDpcLevel(&DeviceQueue->Lock);
 177     return ReturnEntry;
 178 }
 179
 180 /*
 181  * @implemented
 182  */
 183 PKDEVICE_QUEUE_ENTRY
 184 STDCALL
 185 KeRemoveByKeyDeviceQueue (IN PKDEVICE_QUEUE DeviceQueue,
 186                           IN ULONG SortKey)
 187 {
 188     PLIST_ENTRY ListEntry;
 189     PKDEVICE_QUEUE_ENTRY ReturnEntry;
 190
 191     DPRINT("KeRemoveByKeyDeviceQueue(DeviceQueue %x)\n", DeviceQueue);
 192     ASSERT(KeGetCurrentIrql() == DISPATCH_LEVEL);
 193
 194     /* Acquire the Lock */
 195     KeAcquireSpinLockAtDpcLevel(&DeviceQueue->Lock);
 196     ASSERT(DeviceQueue->Busy);
 197
 198     /* An attempt to remove an entry from an empty (and busy) queue sets the queue idle */
 199     if (IsListEmpty(&DeviceQueue->DeviceListHead)) {
 200
 201         DeviceQueue->Busy = FALSE;
 202         ReturnEntry = NULL;
 203
 204    } else {
 205
 206         /* Find entry with SortKey greater than or equal to the passed-in SortKey */
 207         ListEntry = DeviceQueue->DeviceListHead.Flink;
 208         while (ListEntry != &DeviceQueue->DeviceListHead) {
 209
 210             /* Get Entry */
 211             ReturnEntry = CONTAINING_RECORD(ListEntry,
 212                                             KDEVICE_QUEUE_ENTRY,
 213                                             DeviceListEntry);
 214
 215             /* Check if keys match */
 216             if (ReturnEntry->SortKey >= SortKey) break;
 217
 218             /* Move to next item */
 219             ListEntry = ListEntry->Flink;
 220         }
 221
 222         /* Check if we found something */
 223         if (ListEntry == &DeviceQueue->DeviceListHead) {
 224
 225             /*  Not found, return the first entry */
 226             ListEntry = RemoveHeadList(&DeviceQueue->DeviceListHead);
 227             ReturnEntry = CONTAINING_RECORD(ListEntry,
 228                                             KDEVICE_QUEUE_ENTRY,
 229                                             DeviceListEntry);
 230         } else {
 231
 232             /* We found it, so just remove it */
 233             RemoveEntryList(&ReturnEntry->DeviceListEntry);
 234         }
 235
 236         /* Set it as non-inserted */
 237         ReturnEntry->Inserted = FALSE;
 238     }
 239
 240     /* Release lock and Return */
 241     KeReleaseSpinLockFromDpcLevel(&DeviceQueue->Lock);
 242     return ReturnEntry;
 243 }
 244
 245 /*
 246  * @implemented
 247  */
 248 BOOLEAN STDCALL
 249 KeRemoveEntryDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue,
 250                          IN PKDEVICE_QUEUE_ENTRY DeviceQueueEntry)
 251 {
 252     KIRQL OldIrql;
 253     BOOLEAN OldState;
 254
 255     DPRINT("KeRemoveEntryDeviceQueue(DeviceQueue %x)\n", DeviceQueue);
 256     ASSERT(KeGetCurrentIrql() <= DISPATCH_LEVEL);
 257
 258     /* Acquire the Lock */
 259     KeAcquireSpinLock(&DeviceQueue->Lock, &OldIrql);
 260
 261     /* Check/Set Old State */
 262     if ((OldState = DeviceQueueEntry->Inserted)) {
 263
 264         /* Remove it */
 265         DeviceQueueEntry->Inserted = FALSE;
 266         RemoveEntryList(&DeviceQueueEntry->DeviceListEntry);
 267     }
 268
 269     /* Unlock and return old state */
 270     KeReleaseSpinLock(&DeviceQueue->Lock, OldIrql);
 271     return OldState;
 272 }