1 /*++
2 
3 Copyright (c) Microsoft Corporation.  All rights reserved.
4 
5 Module Name:
6 
7     FxTransactionedList.cpp
8 
9 Abstract:
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 
15 Author:
16 
17 
18 
19 Environment:
20 
21     Both kernel and user mode
22 
23 Revision History:
24 
25 --*/
26 
27 #include "fxsupportpch.hpp"
28 
29 FxTransactionedList::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 
41 FxTransactionedList::~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 
116 VOID
117 FxTransactionedList::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 
128 VOID
129 FxTransactionedList::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 
156 VOID
157 FxTransactionedList::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 
208 VOID
209 FxTransactionedList::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 
237 BOOLEAN
238 FxTransactionedList::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_
262 NTSTATUS
263 FxTransactionedList::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 
303 VOID
304 FxTransactionedList::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 
355 Done:
356     ReleaseLock(FxDriverGlobals, irql);
357 
358     if (removed && m_DeleteOnRemove) {
359         pEntry->GetTransactionedObject()->DeleteObject();
360     }
361 }
362 
363 VOID
364 FxTransactionedList::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 
381 BOOLEAN
382 FxTransactionedList::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_
431 FxTransactionedEntry*
432 FxTransactionedList::GetNextEntry(
433     __in_opt FxTransactionedEntry* Entry
434     )
435 /*++
436 
437 Routine Description:
438     Gets the next entry.  Assumes the caller has called LockedForEnum
439 
440 Arguments:
441     Entry the current entry in the iteratation, NULL for the first
442 
443 Return 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_
457 FxTransactionedEntry*
458 FxTransactionedList::GetNextEntryLocked(
459     __in_opt FxTransactionedEntry* Entry
460     )
461 /*++
462 
463 Routine Description:
464     Returns the next entry.  Assumes that the caller has the list locked through
465     a call to AcquireLock() or through LockForEnum()
466 
467 Arguments:
468     Entry the current entry in the iteratation, NULL for the first
469 
470 Return 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 
502 FxSpinLockTransactionedList::FxSpinLockTransactionedList() :
503     FxTransactionedList()
504 {
505 }
506 
507 __drv_raisesIRQL(DISPATCH_LEVEL)
508 __drv_maxIRQL(DISPATCH_LEVEL)
509 VOID
510 FxSpinLockTransactionedList::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)
520 VOID
521 FxSpinLockTransactionedList::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_)
531 VOID
532 FxWaitLockTransactionedList::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_)
542 VOID
543 FxWaitLockTransactionedList::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 
553