/*
- * 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>
/*
* @implemented
+ *
+ * FUNCTION: Intializes a device queue
+ * ARGUMENTS:
+ * DeviceQueue = Device queue to initialize
*/
-BOOLEAN STDCALL
-KeInsertByKeyDeviceQueue (
- IN PKDEVICE_QUEUE DeviceQueue,
- IN PKDEVICE_QUEUE_ENTRY DeviceQueueEntry,
- IN ULONG SortKey)
+VOID
+STDCALL
+KeInitializeDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue)
{
- PLIST_ENTRY current;
- PKDEVICE_QUEUE_ENTRY entry;
-
- DPRINT("KeInsertByKeyDeviceQueue()\n");
- assert(KeGetCurrentIrql() == DISPATCH_LEVEL);
-
- DeviceQueueEntry->SortKey=SortKey;
- KeAcquireSpinLockAtDpcLevel(&DeviceQueue->Lock);
-
- if (!DeviceQueue->Busy)
- {
- DeviceQueue->Busy=TRUE;
- KeReleaseSpinLockFromDpcLevel(&DeviceQueue->Lock);
- return(FALSE);
- }
-
- /*
- Insert new entry after the last entry with SortKey less or equal to passed-in SortKey.
- NOTE: walking list in reverse order.
- */
- current=DeviceQueue->DeviceListHead.Blink;
- while (current!=(&DeviceQueue->DeviceListHead))
- {
- entry = CONTAINING_RECORD(current,KDEVICE_QUEUE_ENTRY,DeviceListEntry);
- if (entry->SortKey <= SortKey)
- {
- /* insert new entry after current entry */
- InsertTailList(current, &DeviceQueueEntry->DeviceListEntry);
- KeReleaseSpinLockFromDpcLevel(&DeviceQueue->Lock);
- return(TRUE);
- }
- current = current->Blink;
- }
-
- InsertHeadList(&DeviceQueue->DeviceListHead,&DeviceQueueEntry->DeviceListEntry);
-
- KeReleaseSpinLockFromDpcLevel(&DeviceQueue->Lock);
- return(TRUE);
+ /* 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;
}
/*
* @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
*/
-PKDEVICE_QUEUE_ENTRY
+BOOLEAN
STDCALL
-KeRemoveByKeyDeviceQueue (
- IN PKDEVICE_QUEUE DeviceQueue,
- IN ULONG SortKey
- )
+KeInsertDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue,
+ IN PKDEVICE_QUEUE_ENTRY DeviceQueueEntry)
{
- PLIST_ENTRY current;
- PKDEVICE_QUEUE_ENTRY entry;
+ BOOLEAN Inserted;
+
+ DPRINT("KeInsertDeviceQueue(DeviceQueue %x)\n", DeviceQueue);
+ ASSERT(KeGetCurrentIrql() == DISPATCH_LEVEL);
+
+ /* Lock the Queue */
+ KeAcquireSpinLockAtDpcLevel(&DeviceQueue->Lock);
- assert(KeGetCurrentIrql() == DISPATCH_LEVEL);
- assert(DeviceQueue!=NULL);
- assert(DeviceQueue->Busy);
+ if (!DeviceQueue->Busy) {
+
+ /* Set it as busy */
+ Inserted = FALSE;
+ DeviceQueue->Busy = TRUE;
+
+ } else {
+
+ /* Insert it into the list */
+ Inserted = TRUE;
+ InsertTailList(&DeviceQueue->DeviceListHead,
+ &DeviceQueueEntry->DeviceListEntry);
+
+
+ }
- KeAcquireSpinLockAtDpcLevel(&DeviceQueue->Lock);
+ /* Sert the Insert state into the entry */
+ DeviceQueueEntry->Inserted = Inserted;
- /* an attempt to remove an entry from an empty (and busy) queue sets the queue to idle */
- if (IsListEmpty(&DeviceQueue->DeviceListHead))
- {
- DeviceQueue->Busy = FALSE;
+ /* Release lock and return */
KeReleaseSpinLockFromDpcLevel(&DeviceQueue->Lock);
- return NULL;
- }
-
- /* find entry with SortKey greater than or equal to the passed-in SortKey */
- current = DeviceQueue->DeviceListHead.Flink;
- while (current != &DeviceQueue->DeviceListHead)
- {
- entry = CONTAINING_RECORD(current,KDEVICE_QUEUE_ENTRY,DeviceListEntry);
- if (entry->SortKey >= SortKey)
- {
- RemoveEntryList(current);
- KeReleaseSpinLockFromDpcLevel(&DeviceQueue->Lock);
- return entry;
- }
- current = current->Flink;
- }
-
- /* if we didn't find a match, return the first entry */
- current = RemoveHeadList(&DeviceQueue->DeviceListHead);
- KeReleaseSpinLockFromDpcLevel(&DeviceQueue->Lock);
-
- return CONTAINING_RECORD(current,KDEVICE_QUEUE_ENTRY,DeviceListEntry);
+ return Inserted;
}
/*
* @implemented
*/
-PKDEVICE_QUEUE_ENTRY
+BOOLEAN
STDCALL
-KeRemoveDeviceQueue (
- IN PKDEVICE_QUEUE DeviceQueue)
+KeInsertByKeyDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue,
+ IN PKDEVICE_QUEUE_ENTRY DeviceQueueEntry,
+ IN ULONG SortKey)
+{
+ 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;
+
+ 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;
+ }
+
+ /* Reset the Inserted State */
+ DeviceQueueEntry->Inserted = Inserted;
+
+ /* Release Lock and Return */
+ KeReleaseSpinLockFromDpcLevel(&DeviceQueue->Lock);
+ return Inserted;
+}
+
/*
+ * @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)
{
- PLIST_ENTRY list_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(KeGetCurrentIrql() == DISPATCH_LEVEL);
- assert(DeviceQueue!=NULL);
- assert(DeviceQueue->Busy);
+ /* Acquire the Lock */
+ KeAcquireSpinLockAtDpcLevel(&DeviceQueue->Lock);
+ ASSERT(DeviceQueue->Busy);
- KeAcquireSpinLockAtDpcLevel(&DeviceQueue->Lock);
+ /* 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;
- /* an attempt to remove an entry from an empty (and busy) queue sets the queue idle */
- if (IsListEmpty(&DeviceQueue->DeviceListHead))
- {
- DeviceQueue->Busy = FALSE;
- KeReleaseSpinLockFromDpcLevel(&DeviceQueue->Lock);
- return NULL;
- }
+ } else {
- list_entry = RemoveHeadList(&DeviceQueue->DeviceListHead);
- KeReleaseSpinLockFromDpcLevel(&DeviceQueue->Lock);
-
- return CONTAINING_RECORD(list_entry,KDEVICE_QUEUE_ENTRY,DeviceListEntry);
-}
+ /* 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;
+ }
-/*
- * @implemented
- */
-VOID
-STDCALL
-KeInitializeDeviceQueue (
- IN PKDEVICE_QUEUE DeviceQueue
- )
-/*
- * FUNCTION: Intializes a device queue
- * ARGUMENTS:
- * DeviceQueue = Device queue to initialize
- */
-{
- assert(DeviceQueue!=NULL);
- InitializeListHead(&DeviceQueue->DeviceListHead);
- DeviceQueue->Busy=FALSE;
- KeInitializeSpinLock(&DeviceQueue->Lock);
+ /* Release lock and Return */
+ KeReleaseSpinLockFromDpcLevel(&DeviceQueue->Lock);
+ return ReturnEntry;
}
/*
* @implemented
*/
-BOOLEAN
+PKDEVICE_QUEUE_ENTRY
STDCALL
-KeInsertDeviceQueue (
- IN PKDEVICE_QUEUE DeviceQueue,
- IN 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
- */
+KeRemoveByKeyDeviceQueue (IN PKDEVICE_QUEUE DeviceQueue,
+ IN ULONG SortKey)
{
- assert(KeGetCurrentIrql() == DISPATCH_LEVEL);
-
- KeAcquireSpinLockAtDpcLevel(&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;
- if (!DeviceQueue->Busy)
- {
- DeviceQueue->Busy=TRUE;
- KeReleaseSpinLockFromDpcLevel(&DeviceQueue->Lock);
- return(FALSE);
- }
+ } else {
- DeviceQueueEntry->SortKey=0;
- InsertTailList(&DeviceQueue->DeviceListHead, &DeviceQueueEntry->DeviceListEntry);
+ /* 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;
+ }
- KeReleaseSpinLockFromDpcLevel(&DeviceQueue->Lock);
- return(TRUE);
+ /* Release lock and Return */
+ KeReleaseSpinLockFromDpcLevel(&DeviceQueue->Lock);
+ return ReturnEntry;
}
-
/*
* @implemented
*/
BOOLEAN STDCALL
-KeRemoveEntryDeviceQueue(
- IN PKDEVICE_QUEUE DeviceQueue,
- IN PKDEVICE_QUEUE_ENTRY DeviceQueueEntry)
+KeRemoveEntryDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue,
+ IN PKDEVICE_QUEUE_ENTRY DeviceQueueEntry)
{
- PLIST_ENTRY current;
- KIRQL oldIrql;
- PKDEVICE_QUEUE_ENTRY entry;
-
- assert(KeGetCurrentIrql() <= DISPATCH_LEVEL);
+ KIRQL OldIrql;
+ BOOLEAN OldState;
+
+ DPRINT("KeRemoveEntryDeviceQueue(DeviceQueue %x)\n", DeviceQueue);
+ ASSERT(KeGetCurrentIrql() <= DISPATCH_LEVEL);
- KeAcquireSpinLock(&DeviceQueue->Lock, &oldIrql);
-
- current = DeviceQueue->DeviceListHead.Flink;
- while (current != &DeviceQueue->DeviceListHead)
- {
- entry = CONTAINING_RECORD(current, KDEVICE_QUEUE_ENTRY, DeviceListEntry);
- if (DeviceQueueEntry == entry)
- {
- RemoveEntryList(current);
- KeReleaseSpinLock(&DeviceQueue->Lock, oldIrql);
- /* entry was in the queue (but not anymore) */
- return TRUE;
+ /* Acquire the Lock */
+ KeAcquireSpinLock(&DeviceQueue->Lock, &OldIrql);
+
+ /* Check/Set Old State */
+ if ((OldState = DeviceQueueEntry->Inserted)) {
+
+ /* Remove it */
+ DeviceQueueEntry->Inserted = FALSE;
+ RemoveEntryList(&DeviceQueueEntry->DeviceListEntry);
}
- current = current->Flink;
- }
-
- KeReleaseSpinLock(&DeviceQueue->Lock, oldIrql);
- /* entry wasn't in the queue */
- return FALSE;
+ /* Unlock and return old state */
+ KeReleaseSpinLock(&DeviceQueue->Lock, OldIrql);
+ return OldState;
}
projects / reactos.git / blobdiff