huwcampbell.com
Reactos
1/*++
2
3Copyright (c) Microsoft Corporation. All rights reserved.
4
5Module Name:
6
7 FxTransactionedList.cpp
8
9Abstract:
10
11 This module implements a simple transactioned list which allows the caller
12 to lock the list and then iterate over it without worrying about deletes
13 and adds.
14
15Author:
16
17
18
19Environment:
20
21 Both kernel and user mode
22
23Revision History:
24
25--*/
26
27#include "fxsupportpch.hpp"
28
29FxTransactionedList::FxTransactionedList()
30{
31 m_ListLockedRecursionCount = 0;
32 m_DeleteOnRemove = FALSE;
33 m_Deleting = FALSE;
34 m_Retries = 0;
35 m_DeletingDoneEvent = NULL;
36
37 InitializeListHead(&m_ListHead);
38 InitializeListHead(&m_TransactionHead);
39}
40
41FxTransactionedList::~FxTransactionedList()
42{
43 FxTransactionedEntry* pEntry;
44 PLIST_ENTRY ple;
45
46 //
47 // If m_DeleteOnRemove is FALSE, there is no need to iterate over any of the
48 // lists to free anything.
49 //
50 if (m_DeleteOnRemove == FALSE) {
51 ASSERT(IsListEmpty(&m_ListHead));
52 ASSERT(IsListEmpty(&m_TransactionHead));
53 return;
54 }
55
56 ASSERT(m_ListLockedRecursionCount == 0);
57
58 while (!IsListEmpty(&m_ListHead)) {
59 ple = RemoveHeadList(&m_ListHead);
60 InitializeListHead(ple);
61
62 pEntry = FxTransactionedEntry::_FromEntry(ple);
63
64 switch (pEntry->m_Transaction) {
65 case FxTransactionActionNothing:
66 //
67 // Nothing to do, no pending transaction
68 //
69 break;
70
71 case FxTransactionActionAdd:
72 //
73 // Should not have an add transaction and be on the main list at the
74 // same time!
75 //
76 ASSERT(FALSE);
77 break;
78
79 case FxTransactionActionRemove:
80 //
81 // Make sure it is not on the transaction list
82 //
83 RemoveEntryList(&pEntry->m_TransactionLink);
84 InitializeListHead(&pEntry->m_TransactionLink);
85
86 //
87 // When inserted as a remove transaction, we add this reference in
88 // RemoveLocked
89 //
90 pEntry->GetTransactionedObject()->RELEASE(pEntry);
91 break;
92
93 }
94
95 pEntry->GetTransactionedObject()->DeleteObject();
96 }
97
98 while (!IsListEmpty(&m_TransactionHead)) {
99 ple = RemoveHeadList(&m_TransactionHead);
100 InitializeListHead(ple);
101
102 pEntry = CONTAINING_RECORD(ple, FxTransactionedEntry, m_TransactionLink);
103
104 //
105 // We yanked out all of the removes in the previous loop
106 //
107 ASSERT(pEntry->m_Transaction == FxTransactionActionAdd);
108
109 //
110 // Delete the object since this list owns it.
111 //
112 pEntry->GetTransactionedObject()->DeleteObject();
113 }
114}
115
116VOID
117FxTransactionedList::LockForEnum(
118 __in PFX_DRIVER_GLOBALS FxDriverGlobals
119 )
120{
121 KIRQL irql;
122
123 AcquireLock(FxDriverGlobals, &irql);
124 m_ListLockedRecursionCount++;
125 ReleaseLock(FxDriverGlobals, irql);
126}
127
128VOID
129FxTransactionedList::UnlockFromEnum(
130 __in PFX_DRIVER_GLOBALS FxDriverGlobals
131 )
132{
133 LIST_ENTRY releaseHead;
134 KIRQL irql;
135 MxEvent* event;
136
137 InitializeListHead(&releaseHead);
138 event = NULL;
139 AcquireLock(FxDriverGlobals, &irql);
140 m_ListLockedRecursionCount--;
141 ProcessTransactionList(&releaseHead);
142
143 if (m_ListLockedRecursionCount == 0 && m_Deleting) {
144 event = m_DeletingDoneEvent;
145 m_DeletingDoneEvent = NULL;
146 }
147 ReleaseLock(FxDriverGlobals, irql);
148
149 ProcessObjectsToRelease(&releaseHead);
150
151 if (event != NULL) {
152 event->Set();
153 }
154}
155
156VOID
157FxTransactionedList::ProcessTransactionList(
158 __in PLIST_ENTRY ReleaseHead
159 )
160{
161 LIST_ENTRY *ple;
162 FxTransactionedEntry* pEntry;
163
164 //
165 // If there are other iterators, do not process transactions until they are
166 // done.
167 //
168 if (m_ListLockedRecursionCount != 0) {
169 return;
170 }
171
172 while (!IsListEmpty(&m_TransactionHead)) {
173 ple = RemoveHeadList(&m_TransactionHead);
174 InitializeListHead(ple);
175
176 pEntry = CONTAINING_RECORD(ple, FxTransactionedEntry, m_TransactionLink);
177
178 ASSERT(pEntry->m_Transaction != FxTransactionActionNothing);
179
180 if (pEntry->m_Transaction == FxTransactionActionAdd) {
181 //
182 // Add to the main list
183 //
184 InsertTailList(&m_ListHead, &pEntry->m_ListLink);
185
186 //
187 // Virtual notification of addition
188 //
189 EntryAdded(pEntry);
190 }
191 else if (pEntry->m_Transaction == FxTransactionActionRemove) {
192 //
193 // Remove it from the main list and move it to a free list
194 //
195 RemoveEntryList(&pEntry->m_ListLink);
196 InsertTailList(ReleaseHead, &pEntry->m_TransactionLink);
197
198 //
199 // Virtual notification of removal
200 //
201 EntryRemoved(pEntry);
202 }
203
204 pEntry->m_Transaction = FxTransactionActionNothing;
205 }
206}
207
208VOID
209FxTransactionedList::ProcessObjectsToRelease(
210 __in PLIST_ENTRY ReleaseHead
211 )
212{
213 LIST_ENTRY *ple;
214 FxTransactionedEntry* pEntry;
215
216 while (!IsListEmpty(ReleaseHead)) {
217 ple = RemoveHeadList(ReleaseHead);
218 InitializeListHead(ple);
219
220 pEntry = CONTAINING_RECORD(ple, FxTransactionedEntry, m_TransactionLink);
221
222 //
223 // We always release our reference we took when we post the change
224 // to the list
225 //
226 pEntry->GetTransactionedObject()->RELEASE(pEntry);
227
228 //
229 // 2ndary release if the list is set to do this
230 //
231 if (m_DeleteOnRemove) {
232 pEntry->GetTransactionedObject()->DeleteObject();
233 }
234 }
235}
236
237BOOLEAN
238FxTransactionedList::Deleting(
239 __in PFX_DRIVER_GLOBALS FxDriverGlobals,
240 __in_opt MxEvent* DeleteDoneEvent
241 )
242{
243 KIRQL irql;
244 BOOLEAN result;
245
246 result = TRUE;
247
248 AcquireLock(FxDriverGlobals, &irql);
249 m_Deleting = TRUE;
250
251 if (m_ListLockedRecursionCount != 0) {
252 m_DeletingDoneEvent = DeleteDoneEvent;
253 result = FALSE;
254 }
255
256 ReleaseLock(FxDriverGlobals, irql);
257
258 return result;
259}
260
261_Must_inspect_result_
262NTSTATUS
263FxTransactionedList::Add(
264 __in PFX_DRIVER_GLOBALS FxDriverGlobals,
265 __in FxTransactionedEntry* Entry
266 )
267{
268 NTSTATUS status;
269 KIRQL irql;
270
271 AcquireLock(FxDriverGlobals, &irql);
272
273 if (m_Deleting) {
274 status = STATUS_INVALID_DEVICE_STATE;
275 }
276 else {
277 status = ProcessAdd(Entry);
278 }
279
280 if (NT_SUCCESS(status)) {
281 if (m_ListLockedRecursionCount == 0) {
282 //
283 // We can insert the entry now, do so
284 //
285 InsertTailList(&m_ListHead, &Entry->m_ListLink);
286
287 EntryAdded(Entry);
288 }
289 else {
290 //
291 // List is locked, queue a transaction
292 //
293 Entry->m_Transaction = FxTransactionActionAdd;
294 InsertTailList(&m_TransactionHead, &Entry->m_TransactionLink);
295 }
296 }
297
298 ReleaseLock(FxDriverGlobals, irql);
299
300 return status;
301}
302
303VOID
304FxTransactionedList::SearchForAndRemove(
305 __in PFX_DRIVER_GLOBALS FxDriverGlobals,
306 __in PVOID EntryData
307 )
308{
309 KIRQL irql;
310 FxTransactionedEntry* pEntry;
311 PLIST_ENTRY ple;
312 BOOLEAN removed;
313
314 removed = FALSE;
315
316 AcquireLock(FxDriverGlobals, &irql);
317
318 for (ple = m_TransactionHead.Flink;
319 ple != &m_TransactionHead;
320 ple = ple->Flink) {
321
322 pEntry = CONTAINING_RECORD(ple, FxTransactionedEntry, m_TransactionLink);
323
324 if (Compare(pEntry, EntryData)) {
325 if (pEntry->GetTransactionAction() == FxTransactionActionAdd) {
326 RemoveEntryList(&pEntry->m_TransactionLink);
327 InitializeListHead(&pEntry->m_TransactionLink);
328
329 removed = TRUE;
330 }
331 else {
332 //
333 // Already being removed, just return
334 //
335 ASSERT(pEntry->GetTransactionAction() ==
336 FxTransactionActionRemove);
337 }
338
339 goto Done;
340 }
341 }
342
343 //
344 // Walk the committed list
345 //
346 pEntry = NULL;
347
348 while ((pEntry = GetNextEntryLocked(pEntry)) != NULL) {
349 if (Compare(pEntry, EntryData)) {
350 removed = RemoveLocked(pEntry);
351 break;
352 }
353 }
354
355Done:
356 ReleaseLock(FxDriverGlobals, irql);
357
358 if (removed && m_DeleteOnRemove) {
359 pEntry->GetTransactionedObject()->DeleteObject();
360 }
361}
362
363VOID
364FxTransactionedList::Remove(
365 __in PFX_DRIVER_GLOBALS FxDriverGlobals,
366 __in FxTransactionedEntry* Entry
367 )
368{
369 BOOLEAN removed;
370 KIRQL irql;
371
372 AcquireLock(FxDriverGlobals, &irql);
373 removed = RemoveLocked(Entry);
374 ReleaseLock(FxDriverGlobals,irql);
375
376 if (removed && m_DeleteOnRemove) {
377 Entry->GetTransactionedObject()->DeleteObject();
378 }
379}
380
381BOOLEAN
382FxTransactionedList::RemoveLocked(
383 __in FxTransactionedEntry* Entry
384 )
385{
386 BOOLEAN removed;
387
388 removed = FALSE;
389
390 if (Entry->m_Transaction == FxTransactionActionAdd) {
391 //
392 // Not yet added to the list proper, remove it from the transaction list
393 //
394 removed = TRUE;
395 RemoveEntryList(&Entry->m_TransactionLink);
396 InitializeListHead(&Entry->m_TransactionLink);
397
398 Entry->m_Transaction = FxTransactionActionNothing;
399 }
400 else {
401 ASSERT(!IsListEmpty(&Entry->m_ListLink));
402
403 if (m_ListLockedRecursionCount == 0) {
404 //
405 // List is not locked, remove it now
406 //
407 RemoveEntryList(&Entry->m_ListLink);
408 InitializeListHead(&Entry->m_ListLink);
409
410 //
411 // Virtual notification
412 //
413 EntryRemoved(Entry);
414
415 removed = TRUE;
416 }
417 else {
418 //
419 // List is locked for enumeration, queue a transaction
420 //
421 Entry->m_Transaction = FxTransactionActionRemove;
422 InsertTailList(&m_TransactionHead, &Entry->m_TransactionLink);
423 Entry->GetTransactionedObject()->ADDREF(Entry);
424 }
425 }
426
427 return removed;
428}
429
430_Must_inspect_result_
431FxTransactionedEntry*
432FxTransactionedList::GetNextEntry(
433 __in_opt FxTransactionedEntry* Entry
434 )
435/*++
436
437Routine Description:
438 Gets the next entry. Assumes the caller has called LockedForEnum
439
440Arguments:
441 Entry the current entry in the iteratation, NULL for the first
442
443Return Value:
444 next entry in the iteration, NULL if there are no more entries
445
446 --*/
447{
448 //
449 // The caller should have locked the list for enumeration
450 //
451 ASSERT(m_ListLockedRecursionCount > 0 || m_Deleting);
452
453 return GetNextEntryLocked(Entry);
454}
455
456_Must_inspect_result_
457FxTransactionedEntry*
458FxTransactionedList::GetNextEntryLocked(
459 __in_opt FxTransactionedEntry* Entry
460 )
461/*++
462
463Routine Description:
464 Returns the next entry. Assumes that the caller has the list locked through
465 a call to AcquireLock() or through LockForEnum()
466
467Arguments:
468 Entry the current entry in the iteratation, NULL for the first
469
470Return Value:
471 next entry in the iteration, NULL if there are no more entries
472
473 --*/
474{
475 PLIST_ENTRY ple;
476
477 if (Entry == NULL) {
478 ple = m_ListHead.Flink;
479 }
480 else {
481 ple = Entry->m_ListLink.Flink;
482 }
483
484 //
485 // Find the next entry which does not have a pending transaction on it
486 //
487 for ( ; ple != &m_ListHead; ple = ple->Flink) {
488 FxTransactionedEntry* pNext;
489
490 pNext = FxTransactionedEntry::_FromEntry(ple);
491 if (pNext->m_Transaction == FxTransactionActionNothing) {
492 return pNext;
493 }
494 }
495
496 //
497 // Reached the end of the list
498 //
499 return NULL;
500}
501
502FxSpinLockTransactionedList::FxSpinLockTransactionedList() :
503 FxTransactionedList()
504{
505}
506
507__drv_raisesIRQL(DISPATCH_LEVEL)
508__drv_maxIRQL(DISPATCH_LEVEL)
509VOID
510FxSpinLockTransactionedList::AcquireLock(
511 __in PFX_DRIVER_GLOBALS FxDriverGlobals,
512 __out PKIRQL Irql
513 )
514{
515 UNREFERENCED_PARAMETER(FxDriverGlobals);
516 m_ListLock.Acquire(Irql);
517}
518
519__drv_requiresIRQL(DISPATCH_LEVEL)
520VOID
521FxSpinLockTransactionedList::ReleaseLock(
522 __in PFX_DRIVER_GLOBALS FxDriverGlobals,
523 __in __drv_restoresIRQL KIRQL Irql
524 )
525{
526 UNREFERENCED_PARAMETER(FxDriverGlobals);
527 m_ListLock.Release(Irql);
528}
529
530_Acquires_lock_(_Global_critical_region_)
531VOID
532FxWaitLockTransactionedList::AcquireLock(
533 __in PFX_DRIVER_GLOBALS FxDriverGlobals,
534 __out PKIRQL Irql
535 )
536{
537 UNREFERENCED_PARAMETER(Irql);
538 m_StateChangeListLock.AcquireLock(FxDriverGlobals);
539}
540
541_Releases_lock_(_Global_critical_region_)
542VOID
543FxWaitLockTransactionedList::ReleaseLock(
544 __in PFX_DRIVER_GLOBALS FxDriverGlobals,
545 __in KIRQL Irql
546 )
547{
548 UNREFERENCED_PARAMETER(Irql);
549 m_StateChangeListLock.ReleaseLock(FxDriverGlobals);
550}
551
552