ntoskrnl/ke/devqueue.c

   1 /*
   2  * PROJECT:         ReactOS Kernel
   3  * LICENSE:         GPL - See COPYING in the top level directory
   4  * FILE:            ntoskrnl/ke/devqueue.c
   5  * PURPOSE:         Implement device queues
   6  * PROGRAMMERS:     Alex Ionescu (alex.ionescu@reactos.org)
   7  */
   8
   9 /* INCLUDES ******************************************************************/
  10
  11 #include <ntoskrnl.h>
  12 #define NDEBUG
  13 #include <debug.h>
  14
  15 /* FUNCTIONS *****************************************************************/
  16
  17 /*
  18  * @implemented
  19  */
  20 VOID
  21 NTAPI
  22 KeInitializeDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue)
  23 {
  24     /* Initialize the Header */
  25     DeviceQueue->Type = DeviceQueueObject;
  26     DeviceQueue->Size = sizeof(KDEVICE_QUEUE);
  27
  28     /* Initialize the Listhead and Spinlock */
  29     InitializeListHead(&DeviceQueue->DeviceListHead);
  30     KeInitializeSpinLock(&DeviceQueue->Lock);
  31
  32     /* Set it as busy */
  33     DeviceQueue->Busy=FALSE;
  34 }
  35
  36 /*
  37  * @implemented
  38  */
  39 BOOLEAN
  40 NTAPI
  41 KeInsertDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue,
  42                     IN PKDEVICE_QUEUE_ENTRY DeviceQueueEntry)
  43 {
  44     KLOCK_QUEUE_HANDLE DeviceLock;
  45     BOOLEAN Inserted;
  46     ASSERT_DEVICE_QUEUE(DeviceQueue);
  47
  48     DPRINT("KeInsertDeviceQueue() DevQueue %p, Entry %p\n", DeviceQueue, DeviceQueueEntry);
  49
  50     /* Lock the queue */
  51     KiAcquireDeviceQueueLock(DeviceQueue, &DeviceLock);
  52
  53     /* Check if it's not busy */
  54     if (!DeviceQueue->Busy)
  55     {
  56         /* Set it as busy */
  57         Inserted = FALSE;
  58         DeviceQueue->Busy = TRUE;
  59     }
  60     else
  61     {
  62         /* Insert it into the list */
  63         Inserted = TRUE;
  64         InsertTailList(&DeviceQueue->DeviceListHead,
  65                        &DeviceQueueEntry->DeviceListEntry);
  66     }
  67
  68     /* Sert the Insert state into the entry */
  69     DeviceQueueEntry->Inserted = Inserted;
  70
  71     /* Release the lock */
  72     KiReleaseDeviceQueueLock(&DeviceLock);
  73
  74     /* Return the state */
  75     return Inserted;
  76 }
  77
  78 /*
  79  * @implemented
  80  */
  81 BOOLEAN
  82 NTAPI
  83 KeInsertByKeyDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue,
  84                          IN PKDEVICE_QUEUE_ENTRY DeviceQueueEntry,
  85                          IN ULONG SortKey)
  86 {
  87     KLOCK_QUEUE_HANDLE DeviceLock;
  88     BOOLEAN Inserted;
  89     PLIST_ENTRY NextEntry;
  90     PKDEVICE_QUEUE_ENTRY LastEntry;
  91     ASSERT_DEVICE_QUEUE(DeviceQueue);
  92
  93     DPRINT("KeInsertByKeyDeviceQueue() DevQueue %p, Entry %p, SortKey 0x%x\n", DeviceQueue, DeviceQueueEntry, SortKey);
  94
  95     /* Lock the queue */
  96     KiAcquireDeviceQueueLock(DeviceQueue, &DeviceLock);
  97
  98     /* Set the Sort Key */
  99     DeviceQueueEntry->SortKey = SortKey;
 100
 101     /* Check if it's not busy */
 102     if (!DeviceQueue->Busy)
 103     {
 104         /* Set it as busy */
 105         Inserted = FALSE;
 106         DeviceQueue->Busy = TRUE;
 107     }
 108     else
 109     {
 110         /* Make sure the list isn't empty */
 111         NextEntry = &DeviceQueue->DeviceListHead;
 112         if (!IsListEmpty(NextEntry))
 113         {
 114             /* Get the last entry */
 115             LastEntry = CONTAINING_RECORD(NextEntry->Blink,
 116                                           KDEVICE_QUEUE_ENTRY,
 117                                           DeviceListEntry);
 118
 119             /* Check if our sort key is lower */
 120             if (SortKey < LastEntry->SortKey)
 121             {
 122                 /* Loop each sort key */
 123                 do
 124                 {
 125                     /* Get the next entry */
 126                     NextEntry = NextEntry->Flink;
 127                     LastEntry = CONTAINING_RECORD(NextEntry,
 128                                                   KDEVICE_QUEUE_ENTRY,
 129                                                   DeviceListEntry);
 130
 131                     /* Keep looping until we find a place to insert */
 132                 } while (SortKey >= LastEntry->SortKey);
 133             }
 134         }
 135
 136         /* Now insert us */
 137         InsertTailList(NextEntry, &DeviceQueueEntry->DeviceListEntry);
 138         Inserted = TRUE;
 139     }
 140
 141     /* Release the lock */
 142     KiReleaseDeviceQueueLock(&DeviceLock);
 143
 144     /* Return the state */
 145     return Inserted;
 146 }
 147
 148 /*
 149  * @implemented
 150  */
 151 PKDEVICE_QUEUE_ENTRY
 152 NTAPI
 153 KeRemoveDeviceQueue(IN PKDEVICE_QUEUE   DeviceQueue)
 154 {
 155     PLIST_ENTRY ListEntry;
 156     PKDEVICE_QUEUE_ENTRY ReturnEntry;
 157     KLOCK_QUEUE_HANDLE DeviceLock;
 158     ASSERT_DEVICE_QUEUE(DeviceQueue);
 159
 160     DPRINT("KeRemoveDeviceQueue() DevQueue %p\n", DeviceQueue);
 161
 162     /* Lock the queue */
 163     KiAcquireDeviceQueueLock(DeviceQueue, &DeviceLock);
 164     ASSERT(DeviceQueue->Busy);
 165
 166     /* Check if this is an empty queue */
 167     if (IsListEmpty(&DeviceQueue->DeviceListHead))
 168     {
 169         /* Set it to idle and return nothing*/
 170         DeviceQueue->Busy = FALSE;
 171         ReturnEntry = NULL;
 172     }
 173     else
 174     {
 175         /* Remove the Entry from the List */
 176         ListEntry = RemoveHeadList(&DeviceQueue->DeviceListHead);
 177         ReturnEntry = CONTAINING_RECORD(ListEntry,
 178                                         KDEVICE_QUEUE_ENTRY,
 179                                         DeviceListEntry);
 180
 181         /* Set it as non-inserted */
 182         ReturnEntry->Inserted = FALSE;
 183     }
 184
 185     /* Release the lock */
 186     KiReleaseDeviceQueueLock(&DeviceLock);
 187
 188     /* Return the entry */
 189     return ReturnEntry;
 190 }
 191
 192 /*
 193  * @implemented
 194  */
 195 PKDEVICE_QUEUE_ENTRY
 196 NTAPI
 197 KeRemoveByKeyDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue,
 198                          IN ULONG SortKey)
 199 {
 200     PLIST_ENTRY NextEntry;
 201     PKDEVICE_QUEUE_ENTRY ReturnEntry;
 202     KLOCK_QUEUE_HANDLE DeviceLock;
 203     ASSERT_DEVICE_QUEUE(DeviceQueue);
 204
 205     DPRINT("KeRemoveByKeyDeviceQueue() DevQueue %p, SortKey 0x%x\n", DeviceQueue, SortKey);
 206
 207     /* Lock the queue */
 208     KiAcquireDeviceQueueLock(DeviceQueue, &DeviceLock);
 209     ASSERT(DeviceQueue->Busy);
 210
 211     /* Check if this is an empty queue */
 212     if (IsListEmpty(&DeviceQueue->DeviceListHead))
 213     {
 214         /* Set it to idle and return nothing*/
 215         DeviceQueue->Busy = FALSE;
 216         ReturnEntry = NULL;
 217     }
 218     else
 219     {
 220         /* If SortKey is greater than the last key, then return the first entry right away */
 221         NextEntry = &DeviceQueue->DeviceListHead;
 222         ReturnEntry = CONTAINING_RECORD(NextEntry->Blink,
 223                                         KDEVICE_QUEUE_ENTRY,
 224                                         DeviceListEntry);
 225
 226         /* Check if we can just get the first entry */
 227         if (ReturnEntry->SortKey <= SortKey)
 228         {
 229             /* Get the first entry */
 230             ReturnEntry = CONTAINING_RECORD(NextEntry->Flink,
 231                                             KDEVICE_QUEUE_ENTRY,
 232                                             DeviceListEntry);
 233         }
 234         else
 235         {
 236             /* Loop the list */
 237             NextEntry = DeviceQueue->DeviceListHead.Flink;
 238             while (TRUE)
 239             {
 240                 /* Make sure we don't go beyond the end of the queue */
 241                 ASSERT(NextEntry != &DeviceQueue->DeviceListHead);
 242
 243                 /* Get the next entry and check if the key is low enough */
 244                 ReturnEntry = CONTAINING_RECORD(NextEntry,
 245                                                 KDEVICE_QUEUE_ENTRY,
 246                                                 DeviceListEntry);
 247                 if (SortKey <= ReturnEntry->SortKey) break;
 248
 249                 /* Try the next one */
 250                 NextEntry = NextEntry->Flink;
 251             }
 252         }
 253
 254         /* We have an entry, remove it now */
 255         RemoveEntryList(&ReturnEntry->DeviceListEntry);
 256
 257         /* Set it as non-inserted */
 258         ReturnEntry->Inserted = FALSE;
 259     }
 260
 261     /* Release the lock */
 262     KiReleaseDeviceQueueLock(&DeviceLock);
 263
 264     /* Return the entry */
 265     return ReturnEntry;
 266 }
 267
 268 /*
 269  * @implemented
 270  */
 271 PKDEVICE_QUEUE_ENTRY
 272 NTAPI
 273 KeRemoveByKeyDeviceQueueIfBusy(IN PKDEVICE_QUEUE DeviceQueue,
 274                                IN ULONG SortKey)
 275 {
 276     PLIST_ENTRY NextEntry;
 277     PKDEVICE_QUEUE_ENTRY ReturnEntry;
 278     KLOCK_QUEUE_HANDLE DeviceLock;
 279     ASSERT_DEVICE_QUEUE(DeviceQueue);
 280
 281     DPRINT("KeRemoveByKeyDeviceQueueIfBusy() DevQueue %p, SortKey 0x%x\n", DeviceQueue, SortKey);
 282
 283     /* Lock the queue */
 284     KiAcquireDeviceQueueLock(DeviceQueue, &DeviceLock);
 285
 286     /* Check if this is an empty or idle queue */
 287     if (!(DeviceQueue->Busy) || (IsListEmpty(&DeviceQueue->DeviceListHead)))
 288     {
 289         /* Set it to idle and return nothing*/
 290         DeviceQueue->Busy = FALSE;
 291         ReturnEntry = NULL;
 292     }
 293     else
 294     {
 295         /* If SortKey is greater than the last key, then return the first entry right away */
 296         NextEntry = &DeviceQueue->DeviceListHead;
 297         ReturnEntry = CONTAINING_RECORD(NextEntry->Blink,
 298                                         KDEVICE_QUEUE_ENTRY,
 299                                         DeviceListEntry);
 300
 301         /* Check if we can just get the first entry */
 302         if (ReturnEntry->SortKey <= SortKey)
 303         {
 304             /* Get the first entry */
 305             ReturnEntry = CONTAINING_RECORD(NextEntry->Flink,
 306                                             KDEVICE_QUEUE_ENTRY,
 307                                             DeviceListEntry);
 308         }
 309         else
 310         {
 311             /* Loop the list */
 312             NextEntry = DeviceQueue->DeviceListHead.Flink;
 313             while (TRUE)
 314             {
 315                 /* Make sure we don't go beyond the end of the queue */
 316                 ASSERT(NextEntry != &DeviceQueue->DeviceListHead);
 317
 318                 /* Get the next entry and check if the key is low enough */
 319                 ReturnEntry = CONTAINING_RECORD(NextEntry,
 320                                                 KDEVICE_QUEUE_ENTRY,
 321                                                 DeviceListEntry);
 322                 if (SortKey <= ReturnEntry->SortKey) break;
 323
 324                 /* Try the next one */
 325                 NextEntry = NextEntry->Flink;
 326             }
 327         }
 328
 329         /* We have an entry, remove it now */
 330         RemoveEntryList(&ReturnEntry->DeviceListEntry);
 331
 332         /* Set it as non-inserted */
 333         ReturnEntry->Inserted = FALSE;
 334     }
 335
 336     /* Release the lock */
 337     KiReleaseDeviceQueueLock(&DeviceLock);
 338
 339     /* Return the entry */
 340     return ReturnEntry;
 341 }
 342
 343 /*
 344  * @implemented
 345  */
 346 BOOLEAN
 347 NTAPI
 348 KeRemoveEntryDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue,
 349                          IN PKDEVICE_QUEUE_ENTRY DeviceQueueEntry)
 350 {
 351     BOOLEAN OldState;
 352     KLOCK_QUEUE_HANDLE DeviceLock;
 353     ASSERT_DEVICE_QUEUE(DeviceQueue);
 354
 355     DPRINT("KeRemoveEntryDeviceQueue() DevQueue %p, Entry %p\n", DeviceQueue, DeviceQueueEntry);
 356
 357     /* Lock the queue */
 358     KiAcquireDeviceQueueLock(DeviceQueue, &DeviceLock);
 359     ASSERT(DeviceQueue->Busy);
 360
 361     /* Check the insertion state */
 362     OldState = DeviceQueueEntry->Inserted;
 363     if (OldState)
 364     {
 365         /* Remove it */
 366         DeviceQueueEntry->Inserted = FALSE;
 367         RemoveEntryList(&DeviceQueueEntry->DeviceListEntry);
 368     }
 369
 370     /* Unlock and return old state */
 371     KiReleaseDeviceQueueLock(&DeviceLock);
 372     return OldState;
 373 }