entry.c File Reference

#include <ntifs.h>
#include <ndk/rtlfuncs.h>
#include "arbiter.h"
#include <debug.h>

Include dependency graph for entry.c:

Go to the source code of this file.

Macros
#define	NDEBUG
#define	ARBITER_ALLOCATE_DEADLINE   (10ULL * 1000 * 1000) /* 1 second */
#define	ARBITER_ALLOCATE_HARD_DEADLINE   (10ULL * 1000 * 1000 * 10) /* 10 seconds */

Functions
NTSTATUS NTAPI	ArbiterLibPreprocessEntry (_In_ PARBITER_INSTANCE Arbiter, _Inout_ PARBITER_ALLOCATION_STATE ArbState)
	Per-entry hook invoked before each placement attempt. The library default does nothing and succeeds.
NTSTATUS NTAPI	ArbiterLibSortArbitrationList (_Inout_ PLIST_ENTRY ArbitrationList)
	Orders an arbitration list most-constrained first, so fixed requirements are placed before flexible ones can steal their ranges.
static VOID	ArbpFreeAllocationWorkSpaces (_Inout_ PARBITER_ALLOCATION_STATE ArbState)
	Releases the per-entry workspace a PreprocessEntry override allocated, across the whole allocation stack.
static VOID	ArbpReportConflictingRanges (_In_ PARBITER_INSTANCE Arbiter, _In_ ULONGLONG Minimum, _In_ ULONGLONG Maximum)
	Says what an arbiter is already holding across a window.
NTSTATUS NTAPI	ArbiterLibAllocateEntry (_In_ PARBITER_INSTANCE Arbiter, _Inout_ PARBITER_ALLOCATION_STATE ArbState)
	Places the whole stack of entries with backtracking: when an entry cannot be placed, the previous entry's tentative choice is withdrawn and varied, first lower within its window, then via its next window or alternative.

Macro Definition Documentation

ARBITER_ALLOCATE_DEADLINE

#define ARBITER_ALLOCATE_DEADLINE   (10ULL * 1000 * 1000) /* 1 second */

Definition at line 18 of file entry.c.

ARBITER_ALLOCATE_HARD_DEADLINE

#define ARBITER_ALLOCATE_HARD_DEADLINE   (10ULL * 1000 * 1000 * 10) /* 10 seconds */

Definition at line 19 of file entry.c.

NDEBUG

#define NDEBUG

Definition at line 14 of file entry.c.

Function Documentation

ArbiterLibAllocateEntry()

NTSTATUS NTAPI ArbiterLibAllocateEntry	(	_In_ PARBITER_INSTANCE	Arbiter,
		_Inout_ PARBITER_ALLOCATION_STATE	ArbState
	)

Places the whole stack of entries with backtracking: when an entry cannot be placed, the previous entry's tentative choice is withdrawn and varied, first lower within its window, then via its next window or alternative.

Parameters

[in]	Arbiter	The arbiter instance whose walker callbacks (GetNextAllocationRange, FindSuitableRange, AddAllocation, BacktrackAllocation) drive each placement.
[in,out]	ArbState	The first ARBITER_ALLOCATION_STATE of the allocation stack, one per entry in most-constrained-first order, terminated by a state whose Entry is NULL.

Returns

Returns STATUS_SUCCESS once every entry has a placement (the results are packed into each entry's Assignment and Result), STATUS_UNSUCCESSFUL if even the first entry has no solution, or a PreprocessEntry / PackResource failure status.

Definition at line 223 of file entry.c.

{
    PARBITER_ALLOCATION_STATE Current = ArbState;
    BOOLEAN Backtracking = FALSE;
    BOOLEAN McfgConflict = FALSE;
    BOOLEAN DeadlineReported = FALSE;
    ULONGLONG Deadline;
    ULONGLONG HardDeadline;
    NTSTATUS Status;
 
    PAGED_CODE();
 
    Deadline = KeQueryInterruptTime() + ARBITER_ALLOCATE_DEADLINE;
    HardDeadline = KeQueryInterruptTime() + ARBITER_ALLOCATE_HARD_DEADLINE;
 
    while (Current >= ArbState && Current->Entry != NULL)
    {
        BOOLEAN Found = FALSE;
        BOOLEAN RetrySameRange = FALSE;
 
        /*
         * A search that cannot terminate must fail rather than wedge the
         * machine.
         */
        if (KeQueryInterruptTime() > HardDeadline)
        {
            DPRINT1("Arbiter %ws: abandoning allocation at entry %u, the search "
                    "is not terminating\n",
                    Arbiter->Name ? Arbiter->Name : L"(unnamed)",
                    (ULONG)(Current - ArbState));
 
            if (ArbState->Entry != NULL)
                ArbState->Entry->Result = ArbiterResultExternalConflict;
 
            ArbpFreeAllocationWorkSpaces(ArbState);
            return STATUS_UNSUCCESSFUL;
        }
 
        Status = Arbiter->PreprocessEntry(Arbiter, Current);
        if (!NT_SUCCESS(Status))
        {
            ArbpFreeAllocationWorkSpaces(ArbState);
            return Status;
        }
 
        if (Backtracking)
        {
            PARBITER_ALTERNATIVE FailedAlternative = Current->CurrentAlternative;
 
            /*
             * The entry after this one could not be placed. Withdraw this
             * entry's tentative choice and vary it: first lower within the same
             * window, then via the next window / alternative.
             */
            (Current + 1)->CurrentAlternative = NULL;
            Backtracking = FALSE;
 
            if (FailedAlternative == NULL || FailedAlternative->Length == 0)
                goto Backtrack;  /* Nothing to vary here */
 
            Arbiter->BacktrackAllocation(Arbiter, Current);
 
            /*
             * Retrying one placement lower walks the window down an alignment
             * unit at a time, so it has to be bounded, or searching a bridge's
             * multi-gigabyte window will hang the system.
             */
            if (Current->Start > Current->CurrentMinimum &&
                !(FailedAlternative->Flags & ARBITER_ALTERNATIVE_FLAG_FIXED))
            {
                if (KeQueryInterruptTime() <= Deadline)
                {
                    Current->CurrentMaximum = Current->Start - 1;
                    RetrySameRange = TRUE;
                }
                else if (!DeadlineReported)
                {
                    DeadlineReported = TRUE;
                    DPRINT1("Arbiter %ws: allocation deadline expired, giving up "
                            "range refinement\n",
                            Arbiter->Name ? Arbiter->Name : L"(unnamed)");
                }
            }
        }
 
        for (;;)
        {
            if (!RetrySameRange)
            {
                if (!Arbiter->GetNextAllocationRange(Arbiter, Current))
                    break;
            }
            RetrySameRange = FALSE;
 
            if (Arbiter->FindSuitableRange(Arbiter, Current))
            {
                Found = TRUE;
                break;
            }
        }
 
        if (Found)
        {
            if (Current->CurrentAlternative->Length != 0)
                Arbiter->AddAllocation(Arbiter, Current);
            else
                Current->Entry->Result = ArbiterResultNullRequest;
 
            Current++;
            continue;
        }
 
Backtrack:
        if (Current->Flags & ARBITER_STATE_FLAG_MCFG_CONFLICT)
            McfgConflict = TRUE;
 
        if (Current == ArbState)
        {
            /* Even the first entry has no solution. */
            if (Current->Entry != NULL)
                Current->Entry->Result = ArbiterResultExternalConflict;
 
            DPRINT1("Arbiter %ws: nowhere to put 0x%I64x..0x%I64x\n",
                    Arbiter->Name ? Arbiter->Name : L"(unnamed)",
                    Current->CurrentMinimum, Current->CurrentMaximum);
            ArbpReportConflictingRanges(Arbiter,
                                        Current->CurrentMinimum,
                                        Current->CurrentMaximum);
 
            ArbpFreeAllocationWorkSpaces(ArbState);
            return McfgConflict ? STATUS_BAD_MCFG_TABLE : STATUS_UNSUCCESSFUL;
        }
        Backtracking = TRUE;
        Current--;
    }
 
    /* Complete solution found; report it back to the requesters. */
    for (Current = ArbState; Current->Entry != NULL; ++Current)
    {
        Current->Entry->SelectedAlternative = Current->CurrentAlternative->Descriptor;
 
        if (Current->Entry->Assignment != NULL && Arbiter->PackResource != NULL)
        {
            Status = Arbiter->PackResource(Current->CurrentAlternative->Descriptor,
                                           Current->Start,
                                           Current->Entry->Assignment);
            if (!NT_SUCCESS(Status))
            {
                ArbpFreeAllocationWorkSpaces(ArbState);
                return Status;
            }
        }
 
        if (Current->Entry->Result != ArbiterResultNullRequest)
            Current->Entry->Result = ArbiterResultSuccess;
    }
 
    ArbpFreeAllocationWorkSpaces(ArbState);
    return STATUS_SUCCESS;
}

Referenced by ArbiterLibInitializeInstance().

ArbiterLibPreprocessEntry()

NTSTATUS NTAPI ArbiterLibPreprocessEntry	(	_In_ PARBITER_INSTANCE	Arbiter,
		_Inout_ PARBITER_ALLOCATION_STATE	ArbState
	)

Per-entry hook invoked before each placement attempt. The library default does nothing and succeeds.

Parameters

[in]	Arbiter	The arbiter instance placing the entry.
[in,out]	ArbState	The allocation state of the entry about to be placed.

Returns

Returns STATUS_SUCCESS.

Definition at line 38 of file entry.c.

{
    PAGED_CODE();
 
    UNREFERENCED_PARAMETER(Arbiter);
    UNREFERENCED_PARAMETER(ArbState);
    return STATUS_SUCCESS;
}

Referenced by ArbiterLibInitializeInstance().

ArbiterLibSortArbitrationList()

NTSTATUS NTAPI ArbiterLibSortArbitrationList

(

_Inout_ PLIST_ENTRY

ArbitrationList

)

Orders an arbitration list most-constrained first, so fixed requirements are placed before flexible ones can steal their ranges.

Parameters

[in,out]

ArbitrationList

The list of ARBITER_LIST_ENTRY nodes to sort, keyed on the WorkSpace constrainedness score in ascending order. The sort is stable: equally scored entries keep their relative order.

Returns

Returns STATUS_SUCCESS.

Remarks

Without this ordering a wide requirement placed first keeps landing on the one range a later fixed requirement must have, forcing a backtrack for every such collision.

Definition at line 71 of file entry.c.

{
    LIST_ENTRY Sorted;
 
    PAGED_CODE();
 
    InitializeListHead(&Sorted);
 
    while (!IsListEmpty(ArbitrationList))
    {
        PLIST_ENTRY ListEntry = RemoveHeadList(ArbitrationList);
        PARBITER_LIST_ENTRY Entry = CONTAINING_RECORD(ListEntry, ARBITER_LIST_ENTRY, ListEntry);
        PLIST_ENTRY Position;
 
        for (Position = Sorted.Flink; Position != &Sorted; Position = Position->Flink)
        {
            if (CONTAINING_RECORD(Position, ARBITER_LIST_ENTRY, ListEntry)->WorkSpace >
                Entry->WorkSpace)
            {
                break;
            }
        }
 
        InsertTailList(Position, ListEntry);  /* Insert before Position */
    }
 
    /* Return the data back to ArbitrationList! */
    if (!IsListEmpty(&Sorted))
    {
        ArbitrationList->Flink = Sorted.Flink;
        Sorted.Flink->Blink = ArbitrationList;
        ArbitrationList->Blink = Sorted.Blink;
        Sorted.Blink->Flink = ArbitrationList;
    }
 
    return STATUS_SUCCESS;
}

Referenced by ArbpTestAllocation().

ArbpFreeAllocationWorkSpaces()

static VOID ArbpFreeAllocationWorkSpaces ( _Inout_ PARBITER_ALLOCATION_STATE  ArbState )

static

Releases the per-entry workspace a PreprocessEntry override allocated, across the whole allocation stack.

Parameters

[in,out]

ArbState

The first state of the allocation stack.

Definition at line 121 of file entry.c.

{
    PARBITER_ALLOCATION_STATE Current;
 
    PAGED_CODE();
 
    for (Current = ArbState; Current->Entry != NULL; ++Current)
    {
        if (Current->Flags & ARBITER_STATE_FLAG_WORKSPACE)
        {
            ExFreePoolWithTag((PVOID)Current->WorkSpace, TAG_ARBITER);
            Current->WorkSpace = 0;
            Current->Flags &= ~ARBITER_STATE_FLAG_WORKSPACE;
        }
    }
}

Referenced by ArbiterLibAllocateEntry().

ArbpReportConflictingRanges()

static VOID ArbpReportConflictingRanges ( _In_ PARBITER_INSTANCE  Arbiter, _In_ ULONGLONG  Minimum, _In_ ULONGLONG  Maximum  )

static

Says what an arbiter is already holding across a window.

The bare "arbitration failed" a caller reports names the device that could not be placed but not what stopped it, which is the half worth knowing: a fixed requirement can fail either because the window belongs to somebody else or because it was never the arbiter's to give. Both look the same from outside.

Parameters

[in]	Arbiter	The arbiter whose bookkeeping to read.
[in]	Minimum	The bottom of the window that could not be satisfied.
[in]	Maximum	The top of it.

Definition at line 161 of file entry.c.

{
    RTL_RANGE_LIST_ITERATOR Iterator;
    PRTL_RANGE Range;
    BOOLEAN Overlapped = FALSE;
 
    PAGED_CODE();
 
    if (!NT_SUCCESS(RtlGetFirstRange(Arbiter->PossibleAllocation, &Iterator, &Range)))
        return;
 
    while (Range != NULL)
    {
        if ((Range->Start <= Maximum) && (Range->End >= Minimum))
        {
            Overlapped = TRUE;
            DPRINT1("  0x%I64x..0x%I64x held by %p, attributes 0x%x%s\n",
                    Range->Start, Range->End, Range->Owner, Range->Attributes,
                    (Range->Flags & RTL_RANGE_SHARED) ? " (shared)" : "");
        }
 
        if (!NT_SUCCESS(RtlGetNextRange(&Iterator, &Range, TRUE)))
            break;
    }
 
    if (!Overlapped)
    {
        DPRINT1("  nothing holds 0x%I64x..0x%I64x, so it is outside what this "
                "arbiter was given\n",
                Minimum, Maximum);
    }
}

Referenced by ArbiterLibAllocateEntry().