2 * COPYRIGHT: See COPYING in the top level directory
3 * PURPOSE: ReactOS kernel
4 * FILE: ntoskrnl/ke/kqueue.c
5 * PURPOSE: Implement device queues
7 * PROGRAMMERS: Alex Ionescu (alex@relsoft.net) - Several optimizations and implement
8 * usage of Inserted flag + reformat and
10 * David Welch (welch@mcmail.com)
13 /* INCLUDES ****************************************************************/
17 #include <internal/debug.h>
19 /* FUNCTIONS *****************************************************************/
24 * FUNCTION: Intializes a device queue
26 * DeviceQueue = Device queue to initialize
30 KeInitializeDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue
)
33 /* Initialize the Header */
34 DeviceQueue
->Type
= DeviceQueueObject
;
35 DeviceQueue
->Size
= sizeof(KDEVICE_QUEUE
);
37 /* Initialize the Listhead and Spinlock */
38 InitializeListHead(&DeviceQueue
->DeviceListHead
);
39 KeInitializeSpinLock(&DeviceQueue
->Lock
);
42 DeviceQueue
->Busy
=FALSE
;
48 * FUNCTION: Inserts an entry in a device queue
50 * DeviceQueue = Queue to insert the entry in
51 * DeviceQueueEntry = Entry to insert
52 * RETURNS: False is the device queue wasn't busy
57 KeInsertDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue
,
58 IN PKDEVICE_QUEUE_ENTRY DeviceQueueEntry
)
62 DPRINT("KeInsertDeviceQueue(DeviceQueue %x)\n", DeviceQueue
);
63 ASSERT(KeGetCurrentIrql() == DISPATCH_LEVEL
);
66 KeAcquireSpinLockAtDpcLevel(&DeviceQueue
->Lock
);
68 if (!DeviceQueue
->Busy
) {
72 DeviceQueue
->Busy
= TRUE
;
76 /* Insert it into the list */
78 InsertTailList(&DeviceQueue
->DeviceListHead
,
79 &DeviceQueueEntry
->DeviceListEntry
);
84 /* Sert the Insert state into the entry */
85 DeviceQueueEntry
->Inserted
= Inserted
;
87 /* Release lock and return */
88 KeReleaseSpinLockFromDpcLevel(&DeviceQueue
->Lock
);
97 KeInsertByKeyDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue
,
98 IN PKDEVICE_QUEUE_ENTRY DeviceQueueEntry
,
103 DPRINT("KeInsertByKeyDeviceQueue(DeviceQueue %x)\n", DeviceQueue
);
104 ASSERT(KeGetCurrentIrql() == DISPATCH_LEVEL
);
106 /* Acquire the Lock */
107 KeAcquireSpinLockAtDpcLevel(&DeviceQueue
->Lock
);
109 /* Set the Sort Key */
110 DeviceQueueEntry
->SortKey
=SortKey
;
112 if (!DeviceQueue
->Busy
) {
114 DeviceQueue
->Busy
=TRUE
;
119 /* Insert new entry after the last entry with SortKey less or equal to passed-in SortKey */
120 InsertAscendingListFIFO(&DeviceQueue
->DeviceListHead
,
128 /* Reset the Inserted State */
129 DeviceQueueEntry
->Inserted
= Inserted
;
131 /* Release Lock and Return */
132 KeReleaseSpinLockFromDpcLevel(&DeviceQueue
->Lock
);
139 * FUNCTION: Removes an entry from a device queue
141 * DeviceQueue = Queue to remove the entry
142 * RETURNS: The removed entry
146 KeRemoveDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue
)
148 PLIST_ENTRY ListEntry
;
149 PKDEVICE_QUEUE_ENTRY ReturnEntry
;
151 DPRINT("KeRemoveDeviceQueue(DeviceQueue %x)\n", DeviceQueue
);
152 ASSERT(KeGetCurrentIrql() == DISPATCH_LEVEL
);
154 /* Acquire the Lock */
155 KeAcquireSpinLockAtDpcLevel(&DeviceQueue
->Lock
);
156 ASSERT(DeviceQueue
->Busy
);
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
;
165 /* Remove the Entry from the List */
166 ListEntry
= RemoveHeadList(&DeviceQueue
->DeviceListHead
);
167 ReturnEntry
= CONTAINING_RECORD(ListEntry
,
171 /* Set it as non-inserted */
172 ReturnEntry
->Inserted
= FALSE
;
175 /* Release lock and Return */
176 KeReleaseSpinLockFromDpcLevel(&DeviceQueue
->Lock
);
185 KeRemoveByKeyDeviceQueue (IN PKDEVICE_QUEUE DeviceQueue
,
188 PLIST_ENTRY ListEntry
;
189 PKDEVICE_QUEUE_ENTRY ReturnEntry
;
191 DPRINT("KeRemoveByKeyDeviceQueue(DeviceQueue %x)\n", DeviceQueue
);
192 ASSERT(KeGetCurrentIrql() == DISPATCH_LEVEL
);
194 /* Acquire the Lock */
195 KeAcquireSpinLockAtDpcLevel(&DeviceQueue
->Lock
);
196 ASSERT(DeviceQueue
->Busy
);
198 /* An attempt to remove an entry from an empty (and busy) queue sets the queue idle */
199 if (IsListEmpty(&DeviceQueue
->DeviceListHead
)) {
201 DeviceQueue
->Busy
= FALSE
;
206 /* Find entry with SortKey greater than or equal to the passed-in SortKey */
207 LIST_FOR_EACH(ReturnEntry
, &DeviceQueue
->DeviceListHead
, KDEVICE_QUEUE_ENTRY
, DeviceListEntry
)
209 /* Check if keys match */
210 if (ReturnEntry
->SortKey
>= SortKey
) {
211 /* We found it, so just remove it */
212 RemoveEntryList(&ReturnEntry
->DeviceListEntry
);
217 /* Check if we found something */
220 /* Not found, return the first entry */
221 ListEntry
= RemoveHeadList(&DeviceQueue
->DeviceListHead
);
222 ReturnEntry
= CONTAINING_RECORD(ListEntry
,
227 /* Set it as non-inserted */
228 ReturnEntry
->Inserted
= FALSE
;
231 /* Release lock and Return */
232 KeReleaseSpinLockFromDpcLevel(&DeviceQueue
->Lock
);
241 KeRemoveByKeyDeviceQueueIfBusy(IN PKDEVICE_QUEUE DeviceQueue
,
252 KeRemoveEntryDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue
,
253 IN PKDEVICE_QUEUE_ENTRY DeviceQueueEntry
)
258 DPRINT("KeRemoveEntryDeviceQueue(DeviceQueue %x)\n", DeviceQueue
);
259 ASSERT(KeGetCurrentIrql() <= DISPATCH_LEVEL
);
261 /* Acquire the Lock */
262 KeAcquireSpinLock(&DeviceQueue
->Lock
, &OldIrql
);
264 /* Check/Set Old State */
265 if ((OldState
= DeviceQueueEntry
->Inserted
)) {
268 DeviceQueueEntry
->Inserted
= FALSE
;
269 RemoveEntryList(&DeviceQueueEntry
->DeviceListEntry
);
272 /* Unlock and return old state */
273 KeReleaseSpinLock(&DeviceQueue
->Lock
, OldIrql
);