entry.c

Go to the documentation of this file.

/*
 * PROJECT:     ReactOS Arbitration Library
 * LICENSE:     MIT (https://spdx.org/licenses/MIT)
 * PURPOSE:     Entry allocation pipeline
 * COPYRIGHT:   Copyright 2026 Justin Miller <justin.miller@reactos.org>
 */
 
/* INCLUDES *******************************************************************/
 
#include <ntifs.h>
#include <ndk/rtlfuncs.h>
#include "arbiter.h"
 
#define NDEBUG
#include <debug.h>
 
/* Bound the search */
#define ARBITER_ALLOCATE_DEADLINE  (10ULL * 1000 * 1000)   /* 1 second */
#define ARBITER_ALLOCATE_HARD_DEADLINE  (10ULL * 1000 * 1000 * 10)   /* 10 seconds */
 
CODE_SEG("PAGE")
NTSTATUS
NTAPI
ArbiterLibPreprocessEntry(
    _In_ PARBITER_INSTANCE Arbiter,
    _Inout_ PARBITER_ALLOCATION_STATE ArbState)
{
    PAGED_CODE();
 
    UNREFERENCED_PARAMETER(Arbiter);
    UNREFERENCED_PARAMETER(ArbState);
    return STATUS_SUCCESS;
}
 
CODE_SEG("PAGE")
NTSTATUS
NTAPI
ArbiterLibSortArbitrationList(
    _Inout_ PLIST_ENTRY ArbitrationList)
{
    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;
}
 
CODE_SEG("PAGE")
static
VOID
ArbpFreeAllocationWorkSpaces(
    _Inout_ PARBITER_ALLOCATION_STATE ArbState)
{
    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;
        }
    }
}
 
CODE_SEG("PAGE")
static
VOID
ArbpReportConflictingRanges(
    _In_ PARBITER_INSTANCE Arbiter,
    _In_ ULONGLONG Minimum,
    _In_ ULONGLONG Maximum)
{
    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);
    }
}
 
CODE_SEG("PAGE")
NTSTATUS
NTAPI
ArbiterLibAllocateEntry(
    _In_ PARBITER_INSTANCE Arbiter,
    _Inout_ PARBITER_ALLOCATION_STATE ArbState)
{
    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;
}