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 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 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 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 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 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 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 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