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
KeInitializeDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue)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
KeInsertDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue,IN PKDEVICE_QUEUE_ENTRY DeviceQueueEntry)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 /* 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 */
81 BOOLEAN
82 NTAPI
KeInsertByKeyDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue,IN PKDEVICE_QUEUE_ENTRY DeviceQueueEntry,IN ULONG SortKey)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
KeRemoveDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue)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
KeRemoveByKeyDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue,IN ULONG SortKey)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
KeRemoveByKeyDeviceQueueIfBusy(IN PKDEVICE_QUEUE DeviceQueue,IN ULONG SortKey)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
KeRemoveEntryDeviceQueue(IN PKDEVICE_QUEUE DeviceQueue,IN PKDEVICE_QUEUE_ENTRY DeviceQueueEntry)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 }
374