/*
- * COPYRIGHT: See COPYING in the top level directory
- * PURPOSE: ReactOS kernel
- * FILE: ntoskrnl/ke/kqueue.c
- * PURPOSE: Implement device queues
- * PROGRAMMER: David Welch (welch@mcmail.com)
- * REVISION HISTORY:
- * 08/07/98: Created
+ * COPYRIGHT: See COPYING in the top level directory
+ * PURPOSE: ReactOS kernel
+ * FILE: ntoskrnl/ke/kqueue.c
+ * PURPOSE: Implement device queues
+ *
+ * PROGRAMMERS: Alex Ionescu (alex@relsoft.net) - Several optimizations and implement
+ * usage of Inserted flag + reformat and
+ * add debug output.
+ * David Welch (welch@mcmail.com)
*/
/* INCLUDES ****************************************************************/
-#include <ddk/ntddk.h>
-
+#include <ntoskrnl.h>
#define NDEBUG
#include <internal/debug.h>
/* FUNCTIONS *****************************************************************/
-VOID
-InsertBeforeEntryInList(PLIST_ENTRY Head, PLIST_ENTRY After, PLIST_ENTRY Entry)
+/*
+ * @implemented
+ *
+ * FUNCTION: Intializes a device queue
+ * ARGUMENTS:
+ * DeviceQueue = Device queue to initialize
+ */
+VOID
+STDCALL
+KeInitializeDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue)
{
- InsertHeadList(After, Entry);
+
+ /* Initialize the Header */
+ DeviceQueue->Type = DeviceQueueObject;
+ DeviceQueue->Size = sizeof(KDEVICE_QUEUE);
+
+ /* Initialize the Listhead and Spinlock */
+ InitializeListHead(&DeviceQueue->DeviceListHead);
+ KeInitializeSpinLock(&DeviceQueue->Lock);
+
+ /* Set it as busy */
+ DeviceQueue->Busy=FALSE;
}
-BOOLEAN STDCALL
-KeInsertByKeyDeviceQueue (PKDEVICE_QUEUE DeviceQueue,
- PKDEVICE_QUEUE_ENTRY DeviceQueueEntry,
- ULONG SortKey)
+/*
+ * @implemented
+ *
+ * FUNCTION: Inserts an entry in a device queue
+ * ARGUMENTS:
+ * DeviceQueue = Queue to insert the entry in
+ * DeviceQueueEntry = Entry to insert
+ * RETURNS: False is the device queue wasn't busy
+ * True otherwise
+ */
+BOOLEAN
+STDCALL
+KeInsertDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue,
+ IN PKDEVICE_QUEUE_ENTRY DeviceQueueEntry)
{
- KIRQL oldlvl;
- PLIST_ENTRY current;
- PKDEVICE_QUEUE_ENTRY entry;
-
- DPRINT("KeInsertByKeyDeviceQueue()\n");
+ BOOLEAN Inserted;
+
+ DPRINT("KeInsertDeviceQueue(DeviceQueue %x)\n", DeviceQueue);
+ ASSERT(KeGetCurrentIrql() == DISPATCH_LEVEL);
+
+ /* Lock the Queue */
+ KeAcquireSpinLockAtDpcLevel(&DeviceQueue->Lock);
- DeviceQueueEntry->Key=SortKey;
+ if (!DeviceQueue->Busy) {
+
+ /* Set it as busy */
+ Inserted = FALSE;
+ DeviceQueue->Busy = TRUE;
+
+ } else {
- KeAcquireSpinLock(&DeviceQueue->Lock,&oldlvl);
+ /* Insert it into the list */
+ Inserted = TRUE;
+ InsertTailList(&DeviceQueue->DeviceListHead,
+ &DeviceQueueEntry->DeviceListEntry);
+
+
+ }
- if (!DeviceQueue->Busy)
- {
- DeviceQueue->Busy=TRUE;
- KeReleaseSpinLock(&DeviceQueue->Lock,oldlvl);
- return(FALSE);
- }
-
- current=DeviceQueue->ListHead.Flink;
- while (current!=(&DeviceQueue->ListHead))
- {
- entry = CONTAINING_RECORD(current,KDEVICE_QUEUE_ENTRY,Entry);
- if (entry->Key < SortKey)
- {
- InsertBeforeEntryInList(&DeviceQueue->ListHead,
- &DeviceQueueEntry->Entry,
- current);
- KeReleaseSpinLock(&DeviceQueue->Lock,oldlvl);
- return(TRUE);
- }
- current = current->Flink;
- }
- InsertTailList(&DeviceQueue->ListHead,&DeviceQueueEntry->Entry);
+ /* Sert the Insert state into the entry */
+ DeviceQueueEntry->Inserted = Inserted;
- KeReleaseSpinLock(&DeviceQueue->Lock,oldlvl);
- return(TRUE);
+ /* Release lock and return */
+ KeReleaseSpinLockFromDpcLevel(&DeviceQueue->Lock);
+ return Inserted;
}
-PKDEVICE_QUEUE_ENTRY
+/*
+ * @implemented
+ */
+BOOLEAN
STDCALL
-KeRemoveByKeyDeviceQueue (
- PKDEVICE_QUEUE DeviceQueue,
- ULONG SortKey
- )
+KeInsertByKeyDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue,
+ IN PKDEVICE_QUEUE_ENTRY DeviceQueueEntry,
+ IN ULONG SortKey)
{
- KIRQL oldlvl;
- PLIST_ENTRY current;
- PKDEVICE_QUEUE_ENTRY entry;
-
- assert_irql(DISPATCH_LEVEL);
- assert(DeviceQueue!=NULL);
- assert(DeviceQueue->Busy);
+ BOOLEAN Inserted;
+
+ DPRINT("KeInsertByKeyDeviceQueue(DeviceQueue %x)\n", DeviceQueue);
+ ASSERT(KeGetCurrentIrql() == DISPATCH_LEVEL);
+
+ /* Acquire the Lock */
+ KeAcquireSpinLockAtDpcLevel(&DeviceQueue->Lock);
+
+ /* Set the Sort Key */
+ DeviceQueueEntry->SortKey=SortKey;
- KeAcquireSpinLock(&DeviceQueue->Lock,&oldlvl);
+ if (!DeviceQueue->Busy) {
+
+ DeviceQueue->Busy=TRUE;
+ Inserted = FALSE;
+
+ } else {
+
+ /* Insert new entry after the last entry with SortKey less or equal to passed-in SortKey */
+ InsertAscendingListFIFO(&DeviceQueue->DeviceListHead,
+ KDEVICE_QUEUE_ENTRY,
+ DeviceListEntry,
+ DeviceQueueEntry,
+ SortKey);
+ Inserted = TRUE;
+ }
- current = DeviceQueue->ListHead.Flink;
- while (current != &DeviceQueue->ListHead)
- {
- entry = CONTAINING_RECORD(current,KDEVICE_QUEUE_ENTRY,Entry);
- if (entry->Key < SortKey ||
- current->Flink == &DeviceQueue->ListHead)
- {
- RemoveEntryList(current);
- KeReleaseSpinLock(&DeviceQueue->Lock,oldlvl);
- return(entry);
- }
- current = current->Flink;
- }
- DeviceQueue->Busy = FALSE;
- KeReleaseSpinLock(&DeviceQueue->Lock, oldlvl);
- return(NULL);
+ /* Reset the Inserted State */
+ DeviceQueueEntry->Inserted = Inserted;
+
+ /* Release Lock and Return */
+ KeReleaseSpinLockFromDpcLevel(&DeviceQueue->Lock);
+ return Inserted;
}
-PKDEVICE_QUEUE_ENTRY
-STDCALL
-KeRemoveDeviceQueue (
- PKDEVICE_QUEUE DeviceQueue
- )
/*
+ * @implemented
+ *
* FUNCTION: Removes an entry from a device queue
* ARGUMENTS:
* DeviceQueue = Queue to remove the entry
* RETURNS: The removed entry
*/
+PKDEVICE_QUEUE_ENTRY
+STDCALL
+KeRemoveDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue)
{
- KIRQL oldlvl;
- PLIST_ENTRY list_entry;
- PKDEVICE_QUEUE_ENTRY entry;
+ PLIST_ENTRY ListEntry;
+ PKDEVICE_QUEUE_ENTRY ReturnEntry;
- DPRINT("KeRemoveDeviceQueue(DeviceQueue %x)\n",DeviceQueue);
+ DPRINT("KeRemoveDeviceQueue(DeviceQueue %x)\n", DeviceQueue);
+ ASSERT(KeGetCurrentIrql() == DISPATCH_LEVEL);
- assert_irql(DISPATCH_LEVEL);
- assert(DeviceQueue!=NULL);
- assert(DeviceQueue->Busy);
+ /* Acquire the Lock */
+ KeAcquireSpinLockAtDpcLevel(&DeviceQueue->Lock);
+ ASSERT(DeviceQueue->Busy);
- KeAcquireSpinLock(&DeviceQueue->Lock,&oldlvl);
+ /* An attempt to remove an entry from an empty (and busy) queue sets the queue idle */
+ if (IsListEmpty(&DeviceQueue->DeviceListHead)) {
+ DeviceQueue->Busy = FALSE;
+ ReturnEntry = NULL;
- list_entry = RemoveHeadList(&DeviceQueue->ListHead);
- if (list_entry==(&DeviceQueue->ListHead))
- {
- DeviceQueue->Busy=FALSE;
- KeReleaseSpinLock(&DeviceQueue->Lock,oldlvl);
- return(NULL);
- }
- KeReleaseSpinLock(&DeviceQueue->Lock,oldlvl);
+ } else {
- entry = CONTAINING_RECORD(list_entry,KDEVICE_QUEUE_ENTRY,Entry);
- return(entry);
+ /* Remove the Entry from the List */
+ ListEntry = RemoveHeadList(&DeviceQueue->DeviceListHead);
+ ReturnEntry = CONTAINING_RECORD(ListEntry,
+ KDEVICE_QUEUE_ENTRY,
+ DeviceListEntry);
+
+ /* Set it as non-inserted */
+ ReturnEntry->Inserted = FALSE;
+ }
+
+ /* Release lock and Return */
+ KeReleaseSpinLockFromDpcLevel(&DeviceQueue->Lock);
+ return ReturnEntry;
}
-VOID
-STDCALL
-KeInitializeDeviceQueue (
- PKDEVICE_QUEUE DeviceQueue
- )
/*
- * FUNCTION: Intializes a device queue
- * ARGUMENTS:
- * DeviceQueue = Device queue to initialize
+ * @implemented
*/
+PKDEVICE_QUEUE_ENTRY
+STDCALL
+KeRemoveByKeyDeviceQueue (IN PKDEVICE_QUEUE DeviceQueue,
+ IN ULONG SortKey)
{
- assert(DeviceQueue!=NULL);
- InitializeListHead(&DeviceQueue->ListHead);
- DeviceQueue->Busy=FALSE;
- KeInitializeSpinLock(&DeviceQueue->Lock);
+ PLIST_ENTRY ListEntry;
+ PKDEVICE_QUEUE_ENTRY ReturnEntry;
+
+ DPRINT("KeRemoveByKeyDeviceQueue(DeviceQueue %x)\n", DeviceQueue);
+ ASSERT(KeGetCurrentIrql() == DISPATCH_LEVEL);
+
+ /* Acquire the Lock */
+ KeAcquireSpinLockAtDpcLevel(&DeviceQueue->Lock);
+ ASSERT(DeviceQueue->Busy);
+
+ /* An attempt to remove an entry from an empty (and busy) queue sets the queue idle */
+ if (IsListEmpty(&DeviceQueue->DeviceListHead)) {
+
+ DeviceQueue->Busy = FALSE;
+ ReturnEntry = NULL;
+
+ } else {
+
+ /* Find entry with SortKey greater than or equal to the passed-in SortKey */
+ ListEntry = DeviceQueue->DeviceListHead.Flink;
+ while (ListEntry != &DeviceQueue->DeviceListHead) {
+
+ /* Get Entry */
+ ReturnEntry = CONTAINING_RECORD(ListEntry,
+ KDEVICE_QUEUE_ENTRY,
+ DeviceListEntry);
+
+ /* Check if keys match */
+ if (ReturnEntry->SortKey >= SortKey) break;
+
+ /* Move to next item */
+ ListEntry = ListEntry->Flink;
+ }
+
+ /* Check if we found something */
+ if (ListEntry == &DeviceQueue->DeviceListHead) {
+
+ /* Not found, return the first entry */
+ ListEntry = RemoveHeadList(&DeviceQueue->DeviceListHead);
+ ReturnEntry = CONTAINING_RECORD(ListEntry,
+ KDEVICE_QUEUE_ENTRY,
+ DeviceListEntry);
+ } else {
+
+ /* We found it, so just remove it */
+ RemoveEntryList(&ReturnEntry->DeviceListEntry);
+ }
+
+ /* Set it as non-inserted */
+ ReturnEntry->Inserted = FALSE;
+ }
+
+ /* Release lock and Return */
+ KeReleaseSpinLockFromDpcLevel(&DeviceQueue->Lock);
+ return ReturnEntry;
}
-BOOLEAN
-STDCALL
-KeInsertDeviceQueue (
- PKDEVICE_QUEUE DeviceQueue,
- PKDEVICE_QUEUE_ENTRY DeviceQueueEntry
- )
/*
- * FUNCTION: Inserts an entry in a device queue
- * ARGUMENTS:
- * DeviceQueue = Queue to insert the entry in
- * DeviceQueueEntry = Entry to insert
- * RETURNS: False is the device queue wasn't busy
- * True otherwise
+ * @implemented
*/
+BOOLEAN STDCALL
+KeRemoveEntryDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue,
+ IN PKDEVICE_QUEUE_ENTRY DeviceQueueEntry)
{
- KIRQL oldlvl;
-
- KeAcquireSpinLock(&DeviceQueue->Lock,&oldlvl);
-
- if (!DeviceQueue->Busy)
- {
- DeviceQueue->Busy=TRUE;
- KeReleaseSpinLock(&DeviceQueue->Lock,oldlvl);
- return(FALSE);
- }
-
- InsertTailList(&DeviceQueue->ListHead,
- &DeviceQueueEntry->Entry);
- DeviceQueueEntry->Key=0;
-
- KeReleaseSpinLock(&DeviceQueue->Lock,oldlvl);
- return(TRUE);
+ KIRQL OldIrql;
+ BOOLEAN OldState;
+
+ DPRINT("KeRemoveEntryDeviceQueue(DeviceQueue %x)\n", DeviceQueue);
+ ASSERT(KeGetCurrentIrql() <= DISPATCH_LEVEL);
+
+ /* Acquire the Lock */
+ KeAcquireSpinLock(&DeviceQueue->Lock, &OldIrql);
+
+ /* Check/Set Old State */
+ if ((OldState = DeviceQueueEntry->Inserted)) {
+
+ /* Remove it */
+ DeviceQueueEntry->Inserted = FALSE;
+ RemoveEntryList(&DeviceQueueEntry->DeviceListEntry);
+ }
+
+ /* Unlock and return old state */
+ KeReleaseSpinLock(&DeviceQueue->Lock, OldIrql);
+ return OldState;
}
projects / reactos.git / blobdiff