ReactOS 0.4.15-dev-5669-g09dde2c
devqueue.c
Go to the documentation of this file.
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 */
20VOID
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 */
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,
66 }
67
68 /* Set 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 */
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 */
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,
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,
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 */
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 */
152NTAPI
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,
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 */
196NTAPI
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,
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,
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,
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 */
272NTAPI
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,
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,
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,
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 */
347NTAPI
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 */
368 }
369
370 /* Unlock and return old state */
371 KiReleaseDeviceQueueLock(&DeviceLock);
372 return OldState;
373}
unsigned char BOOLEAN
PKDEVICE_QUEUE_ENTRY NTAPI KeRemoveDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue)
Definition: devqueue.c:153
BOOLEAN NTAPI KeInsertByKeyDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue, IN PKDEVICE_QUEUE_ENTRY DeviceQueueEntry, IN ULONG SortKey)
Definition: devqueue.c:83
PKDEVICE_QUEUE_ENTRY NTAPI KeRemoveByKeyDeviceQueueIfBusy(IN PKDEVICE_QUEUE DeviceQueue, IN ULONG SortKey)
Definition: devqueue.c:273
BOOLEAN NTAPI KeInsertDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue, IN PKDEVICE_QUEUE_ENTRY DeviceQueueEntry)
Definition: devqueue.c:41
VOID NTAPI KeInitializeDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue)
Definition: devqueue.c:22
PKDEVICE_QUEUE_ENTRY NTAPI KeRemoveByKeyDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue, IN ULONG SortKey)
Definition: devqueue.c:197
BOOLEAN NTAPI KeRemoveEntryDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue, IN PKDEVICE_QUEUE_ENTRY DeviceQueueEntry)
Definition: devqueue.c:348
#define NULL
Definition: types.h:112
#define TRUE
Definition: types.h:120
#define FALSE
Definition: types.h:117
#define RemoveEntryList(Entry)
Definition: env_spec_w32.h:986
#define InsertTailList(ListHead, Entry)
#define IsListEmpty(ListHead)
Definition: env_spec_w32.h:954
#define RemoveHeadList(ListHead)
Definition: env_spec_w32.h:964
#define InitializeListHead(ListHead)
Definition: env_spec_w32.h:944
#define KeInitializeSpinLock(sl)
Definition: env_spec_w32.h:604
FORCEINLINE VOID KiAcquireDeviceQueueLock(IN PKDEVICE_QUEUE DeviceQueue, IN PKLOCK_QUEUE_HANDLE DeviceLock)
Definition: ke_x.h:676
FORCEINLINE VOID KiReleaseDeviceQueueLock(IN PKLOCK_QUEUE_HANDLE DeviceLock)
Definition: ke_x.h:696
#define ASSERT(a)
Definition: mode.c:44
@ DeviceQueueObject
Definition: ketypes.h:459
#define DPRINT
Definition: sndvol32.h:71
Definition: ketypes.h:566
LIST_ENTRY DeviceListEntry
Definition: ketypes.h:567
ULONG SortKey
Definition: ketypes.h:568
BOOLEAN Inserted
Definition: ketypes.h:569
Definition: typedefs.h:120
struct _LIST_ENTRY * Blink
Definition: typedefs.h:122
struct _LIST_ENTRY * Flink
Definition: typedefs.h:121
#define NTAPI
Definition: typedefs.h:36
#define IN
Definition: typedefs.h:39
#define CONTAINING_RECORD(address, type, field)
Definition: typedefs.h:260
uint32_t ULONG
Definition: typedefs.h:59
_Inout_ PKDEVICE_QUEUE_ENTRY _In_ ULONG SortKey
Definition: kefuncs.h:342
_Inout_ PKDEVICE_QUEUE_ENTRY DeviceQueueEntry
Definition: kefuncs.h:341
#define ASSERT_DEVICE_QUEUE(Object)
struct _KDEVICE_QUEUE KDEVICE_QUEUE