/*++

Copyright (c) Microsoft Corporation.  All rights reserved.

Module Name:

    FxTransactionedList.cpp

Abstract:

    This module implements a simple transactioned list which allows the caller
    to lock the list and then iterate over it without worrying about deletes
    and adds.

Author:



Environment:

    Both kernel and user mode

Revision History:

--*/

#include "fxsupportpch.hpp"

FxTransactionedList::FxTransactionedList()
{
    m_ListLockedRecursionCount = 0;
    m_DeleteOnRemove = FALSE;
    m_Deleting = FALSE;
    m_Retries = 0;
    m_DeletingDoneEvent = NULL;

    InitializeListHead(&m_ListHead);
    InitializeListHead(&m_TransactionHead);
}

FxTransactionedList::~FxTransactionedList()
{
    FxTransactionedEntry* pEntry;
    PLIST_ENTRY ple;

    //
    // If m_DeleteOnRemove is FALSE, there is no need to iterate over any of the
    // lists to free anything.
    //
    if (m_DeleteOnRemove == FALSE) {
        ASSERT(IsListEmpty(&m_ListHead));
        ASSERT(IsListEmpty(&m_TransactionHead));
        return;
    }

    ASSERT(m_ListLockedRecursionCount == 0);

    while (!IsListEmpty(&m_ListHead)) {
        ple = RemoveHeadList(&m_ListHead);
        InitializeListHead(ple);

        pEntry = FxTransactionedEntry::_FromEntry(ple);

        switch (pEntry->m_Transaction) {
        case FxTransactionActionNothing:
            //
            // Nothing to do, no pending transaction
            //
            break;

        case FxTransactionActionAdd:
            //
            // Should not have an add transaction and be on the main list at the
            // same time!
            //
            ASSERT(FALSE);
            break;

        case FxTransactionActionRemove:
            //
            // Make sure it is not on the transaction list
            //
            RemoveEntryList(&pEntry->m_TransactionLink);
            InitializeListHead(&pEntry->m_TransactionLink);

            //
            // When inserted as a remove transaction, we add this reference in
            // RemoveLocked
            //
            pEntry->GetTransactionedObject()->RELEASE(pEntry);
            break;

        }

        pEntry->GetTransactionedObject()->DeleteObject();
    }

    while (!IsListEmpty(&m_TransactionHead)) {
        ple = RemoveHeadList(&m_TransactionHead);
        InitializeListHead(ple);

        pEntry = CONTAINING_RECORD(ple, FxTransactionedEntry, m_TransactionLink);

        //
        // We yanked out all of the removes in the previous loop
        //
        ASSERT(pEntry->m_Transaction == FxTransactionActionAdd);

        //
        // Delete the object since this list owns it.
        //
        pEntry->GetTransactionedObject()->DeleteObject();
    }
}

VOID
FxTransactionedList::LockForEnum(
    __in PFX_DRIVER_GLOBALS FxDriverGlobals
    )
{
    KIRQL irql;

    AcquireLock(FxDriverGlobals, &irql);
    m_ListLockedRecursionCount++;
    ReleaseLock(FxDriverGlobals, irql);
}

VOID
FxTransactionedList::UnlockFromEnum(
    __in PFX_DRIVER_GLOBALS FxDriverGlobals
    )
{
    LIST_ENTRY releaseHead;
    KIRQL irql;
    MxEvent* event;

    InitializeListHead(&releaseHead);
    event = NULL;
    AcquireLock(FxDriverGlobals, &irql);
    m_ListLockedRecursionCount--;
    ProcessTransactionList(&releaseHead);

    if (m_ListLockedRecursionCount == 0 && m_Deleting) {
        event = m_DeletingDoneEvent;
        m_DeletingDoneEvent = NULL;
    }
    ReleaseLock(FxDriverGlobals, irql);

    ProcessObjectsToRelease(&releaseHead);

    if (event != NULL) {
        event->Set();
    }
}

VOID
FxTransactionedList::ProcessTransactionList(
    __in PLIST_ENTRY ReleaseHead
    )
{
    LIST_ENTRY *ple;
    FxTransactionedEntry* pEntry;

    //
    // If there are other iterators, do not process transactions until they are
    // done.
    //
    if (m_ListLockedRecursionCount != 0) {
        return;
    }

    while (!IsListEmpty(&m_TransactionHead)) {
        ple = RemoveHeadList(&m_TransactionHead);
        InitializeListHead(ple);

        pEntry = CONTAINING_RECORD(ple, FxTransactionedEntry, m_TransactionLink);

        ASSERT(pEntry->m_Transaction != FxTransactionActionNothing);

        if (pEntry->m_Transaction == FxTransactionActionAdd) {
            //
            // Add to the main list
            //
            InsertTailList(&m_ListHead, &pEntry->m_ListLink);

            //
            // Virtual notification of addition
            //
            EntryAdded(pEntry);
        }
        else if (pEntry->m_Transaction == FxTransactionActionRemove) {
            //
            // Remove it from the main list and move it to a free list
            //
            RemoveEntryList(&pEntry->m_ListLink);
            InsertTailList(ReleaseHead, &pEntry->m_TransactionLink);

            //
            // Virtual notification of removal
            //
            EntryRemoved(pEntry);
        }

        pEntry->m_Transaction = FxTransactionActionNothing;
    }
}

VOID
FxTransactionedList::ProcessObjectsToRelease(
    __in PLIST_ENTRY ReleaseHead
    )
{
    LIST_ENTRY *ple;
    FxTransactionedEntry* pEntry;

    while (!IsListEmpty(ReleaseHead)) {
        ple = RemoveHeadList(ReleaseHead);
        InitializeListHead(ple);

        pEntry = CONTAINING_RECORD(ple, FxTransactionedEntry, m_TransactionLink);

        //
        // We always release our reference we took when we post the change
        // to the list
        //
        pEntry->GetTransactionedObject()->RELEASE(pEntry);

        //
        // 2ndary release if the list is set to do this
        //
        if (m_DeleteOnRemove) {
            pEntry->GetTransactionedObject()->DeleteObject();
        }
    }
}

BOOLEAN
FxTransactionedList::Deleting(
    __in PFX_DRIVER_GLOBALS FxDriverGlobals,
    __in_opt MxEvent* DeleteDoneEvent
    )
{
    KIRQL irql;
    BOOLEAN result;

    result = TRUE;

    AcquireLock(FxDriverGlobals, &irql);
    m_Deleting = TRUE;

    if (m_ListLockedRecursionCount != 0) {
        m_DeletingDoneEvent = DeleteDoneEvent;
        result = FALSE;
    }

    ReleaseLock(FxDriverGlobals, irql);

    return result;
}

_Must_inspect_result_
NTSTATUS
FxTransactionedList::Add(
    __in PFX_DRIVER_GLOBALS FxDriverGlobals,
    __in FxTransactionedEntry* Entry
    )
{
    NTSTATUS status;
    KIRQL irql;

    AcquireLock(FxDriverGlobals, &irql);

    if (m_Deleting) {
        status = STATUS_INVALID_DEVICE_STATE;
    }
    else {
        status = ProcessAdd(Entry);
    }

    if (NT_SUCCESS(status)) {
        if (m_ListLockedRecursionCount == 0) {
            //
            // We can insert the entry now, do so
            //
            InsertTailList(&m_ListHead, &Entry->m_ListLink);

            EntryAdded(Entry);
        }
        else {
            //
            // List is locked, queue a transaction
            //
            Entry->m_Transaction = FxTransactionActionAdd;
            InsertTailList(&m_TransactionHead, &Entry->m_TransactionLink);
        }
    }

    ReleaseLock(FxDriverGlobals, irql);

    return status;
}

VOID
FxTransactionedList::SearchForAndRemove(
    __in PFX_DRIVER_GLOBALS FxDriverGlobals,
    __in PVOID EntryData
    )
{
    KIRQL irql;
    FxTransactionedEntry* pEntry;
    PLIST_ENTRY ple;
    BOOLEAN removed;

    removed = FALSE;

    AcquireLock(FxDriverGlobals, &irql);

    for (ple = m_TransactionHead.Flink;
         ple != &m_TransactionHead;
         ple = ple->Flink) {

        pEntry = CONTAINING_RECORD(ple, FxTransactionedEntry, m_TransactionLink);

        if (Compare(pEntry, EntryData)) {
            if (pEntry->GetTransactionAction() == FxTransactionActionAdd) {
                RemoveEntryList(&pEntry->m_TransactionLink);
                InitializeListHead(&pEntry->m_TransactionLink);

                removed = TRUE;
            }
            else {
                //
                // Already being removed, just return
                //
                ASSERT(pEntry->GetTransactionAction() ==
                                                    FxTransactionActionRemove);
            }

            goto Done;
        }
    }

    //
    // Walk the committed list
    //
    pEntry = NULL;

    while ((pEntry = GetNextEntryLocked(pEntry)) != NULL) {
        if (Compare(pEntry, EntryData)) {
            removed = RemoveLocked(pEntry);
            break;
        }
    }

Done:
    ReleaseLock(FxDriverGlobals, irql);

    if (removed && m_DeleteOnRemove) {
        pEntry->GetTransactionedObject()->DeleteObject();
    }
}

VOID
FxTransactionedList::Remove(
    __in PFX_DRIVER_GLOBALS FxDriverGlobals,
    __in FxTransactionedEntry* Entry
    )
{
    BOOLEAN removed;
    KIRQL irql;

    AcquireLock(FxDriverGlobals, &irql);
    removed = RemoveLocked(Entry);
    ReleaseLock(FxDriverGlobals,irql);

    if (removed && m_DeleteOnRemove) {
        Entry->GetTransactionedObject()->DeleteObject();
    }
}

BOOLEAN
FxTransactionedList::RemoveLocked(
    __in FxTransactionedEntry* Entry
    )
{
    BOOLEAN removed;

    removed = FALSE;

    if (Entry->m_Transaction == FxTransactionActionAdd) {
        //
        // Not yet added to the list proper, remove it from the transaction list
        //
        removed = TRUE;
        RemoveEntryList(&Entry->m_TransactionLink);
        InitializeListHead(&Entry->m_TransactionLink);

        Entry->m_Transaction = FxTransactionActionNothing;
    }
    else {
        ASSERT(!IsListEmpty(&Entry->m_ListLink));

        if (m_ListLockedRecursionCount == 0) {
            //
            // List is not locked, remove it now
            //
            RemoveEntryList(&Entry->m_ListLink);
            InitializeListHead(&Entry->m_ListLink);

            //
            // Virtual notification
            //
            EntryRemoved(Entry);

            removed = TRUE;
        }
        else {
            //
            // List is locked for enumeration, queue a transaction
            //
            Entry->m_Transaction = FxTransactionActionRemove;
            InsertTailList(&m_TransactionHead, &Entry->m_TransactionLink);
            Entry->GetTransactionedObject()->ADDREF(Entry);
        }
    }

    return removed;
}

_Must_inspect_result_
FxTransactionedEntry*
FxTransactionedList::GetNextEntry(
    __in_opt FxTransactionedEntry* Entry
    )
/*++

Routine Description:
    Gets the next entry.  Assumes the caller has called LockedForEnum

Arguments:
    Entry the current entry in the iteratation, NULL for the first

Return Value:
    next entry in the iteration, NULL if there are no more entries

  --*/
{
    //
    // The caller should have locked the list for enumeration
    //
    ASSERT(m_ListLockedRecursionCount > 0 || m_Deleting);

    return GetNextEntryLocked(Entry);
}

_Must_inspect_result_
FxTransactionedEntry*
FxTransactionedList::GetNextEntryLocked(
    __in_opt FxTransactionedEntry* Entry
    )
/*++

Routine Description:
    Returns the next entry.  Assumes that the caller has the list locked through
    a call to AcquireLock() or through LockForEnum()

Arguments:
    Entry the current entry in the iteratation, NULL for the first

Return Value:
    next entry in the iteration, NULL if there are no more entries

  --*/
{
    PLIST_ENTRY ple;

    if (Entry == NULL) {
        ple = m_ListHead.Flink;
    }
    else {
        ple = Entry->m_ListLink.Flink;
    }

    //
    // Find the next entry which does not have a pending transaction on it
    //
    for ( ; ple != &m_ListHead; ple = ple->Flink) {
        FxTransactionedEntry* pNext;

        pNext = FxTransactionedEntry::_FromEntry(ple);
        if (pNext->m_Transaction == FxTransactionActionNothing) {
            return pNext;
        }
    }

    //
    // Reached the end of the list
    //
    return NULL;
}

FxSpinLockTransactionedList::FxSpinLockTransactionedList() :
    FxTransactionedList()
{
}

__drv_raisesIRQL(DISPATCH_LEVEL)
__drv_maxIRQL(DISPATCH_LEVEL)
VOID
FxSpinLockTransactionedList::AcquireLock(
    __in PFX_DRIVER_GLOBALS FxDriverGlobals,
    __out PKIRQL Irql
    )
{
    UNREFERENCED_PARAMETER(FxDriverGlobals);
    m_ListLock.Acquire(Irql);
}

__drv_requiresIRQL(DISPATCH_LEVEL)
VOID
FxSpinLockTransactionedList::ReleaseLock(
    __in PFX_DRIVER_GLOBALS FxDriverGlobals,
    __in __drv_restoresIRQL KIRQL Irql
    )
{
    UNREFERENCED_PARAMETER(FxDriverGlobals);
    m_ListLock.Release(Irql);
}

_Acquires_lock_(_Global_critical_region_)
VOID
FxWaitLockTransactionedList::AcquireLock(
    __in  PFX_DRIVER_GLOBALS FxDriverGlobals,
    __out PKIRQL Irql
    )
{
    UNREFERENCED_PARAMETER(Irql);
    m_StateChangeListLock.AcquireLock(FxDriverGlobals);
}

_Releases_lock_(_Global_critical_region_)
VOID
FxWaitLockTransactionedList::ReleaseLock(
    __in PFX_DRIVER_GLOBALS FxDriverGlobals,
    __in KIRQL Irql
    )
{
    UNREFERENCED_PARAMETER(Irql);
    m_StateChangeListLock.ReleaseLock(FxDriverGlobals);
}