range.c

Go to the documentation of this file.

/*
 * PROJECT:     ReactOS Arbitration Library
 * LICENSE:     MIT (https://spdx.org/licenses/MIT)
 * PURPOSE:     Allocation range search core
 * 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>
 
/* RANGE WALKER ***************************************************************/
 
#define ARBITER_RESERVED_PASS_DONE  0xFFFFFFFF
 
CODE_SEG("PAGE")
BOOLEAN
NTAPI
ArbiterLibOverrideConflict(
    _In_ PARBITER_INSTANCE Arbiter,
    _Inout_ PARBITER_ALLOCATION_STATE ArbState)
{
    RTL_RANGE_LIST_ITERATOR Iterator;
    PRTL_RANGE Range;
    BOOLEAN SelfConflictOnly = FALSE;
 
    PAGED_CODE();
 
    /*
     * Only a fixed requirement may reclaim its window. Anything else still
     * has other placements to try, and letting it overlap would hide
     * real conflicts.
     */
    if (ArbState->CurrentAlternative == NULL ||
        !(ArbState->CurrentAlternative->Flags & ARBITER_ALTERNATIVE_FLAG_FIXED))
    {
        return FALSE;
    }
 
    if (ArbState->Entry == NULL || ArbState->Entry->PhysicalDeviceObject == NULL)
        return FALSE;
 
    if (!NT_SUCCESS(RtlGetFirstRange(Arbiter->PossibleAllocation, &Iterator, &Range)))
        return FALSE;
 
    while (Range != NULL)
    {
        /* A range that overlaps the window and is not made available. */
        if (Range->Start <= ArbState->CurrentMaximum &&
            Range->End >= ArbState->CurrentMinimum &&
            !(Range->Attributes & ArbState->RangeAvailableAttributes))
        {
            if ((PDEVICE_OBJECT)Range->Owner != ArbState->Entry->PhysicalDeviceObject)
                return FALSE;
 
            SelfConflictOnly = TRUE;
            ArbState->Start = ArbState->CurrentMinimum;
            ArbState->End = ArbState->CurrentMaximum;
        }
 
        if (!NT_SUCCESS(RtlGetNextRange(&Iterator, &Range, TRUE)))
            break;
    }
 
    return SelfConflictOnly;
}
 
CODE_SEG("PAGE")
static
VOID
ArbpWritePriority(
    _In_ PARBITER_INSTANCE Arbiter,
    _Inout_ PARBITER_ALTERNATIVE Alternative)
{
    PARBITER_ORDERING Ordering;
    PARBITER_ORDERING End;
    INT32 Priority = Alternative->Priority;
    BOOLEAN Preferred;
    ULONG Index;
 
    PAGED_CODE();
 
    if (Priority == ARBITER_PRIORITY_EXHAUSTED)
        return;
 
    if (Priority == ARBITER_PRIORITY_RESERVED ||
        Priority == ARBITER_PRIORITY_PREFERRED_RESERVED)
    {
        /* Stay in the reserved pass until its final whole-window try is spent. */
        if (Alternative->Reserved[0] == ARBITER_RESERVED_PASS_DONE)
            Alternative->Priority = ARBITER_PRIORITY_EXHAUSTED;
        return;
    }
 
    Preferred = (Alternative->Descriptor->Option & IO_RESOURCE_PREFERRED) != 0;
 
    if (Priority == ARBITER_PRIORITY_NULL)
    {
        Ordering = Arbiter->OrderingList.Orderings;
    }
    else
    {
        /* A fixed alternative fits in exactly one place; it gets a single shot. */
        if (Alternative->Flags & ARBITER_ALTERNATIVE_FLAG_FIXED)
        {
            Alternative->Priority = ARBITER_PRIORITY_EXHAUSTED;
            return;
        }
 
        Index = (Priority < 0) ? (ULONG)(-(Priority + 1)) : (ULONG)(Priority - 1);
        if (Index >= Arbiter->OrderingList.Count)
        {
            Alternative->Reserved[0] = 0;
            Alternative->Priority = Preferred ? ARBITER_PRIORITY_PREFERRED_RESERVED
                                              : ARBITER_PRIORITY_RESERVED;
            return;
        }
        Ordering = &Arbiter->OrderingList.Orderings[Index + 1];
    }
 
    End = &Arbiter->OrderingList.Orderings[Arbiter->OrderingList.Count];
    for (; Ordering < End; ++Ordering)
    {
        UINT64 Start, RangeEnd;
 
        if (Ordering->Start > Alternative->Maximum ||
            Alternative->Minimum > Ordering->End)
        {
            continue;  /* No intersection with this alternative's window */
        }
 
        Start = max(Alternative->Minimum, Ordering->Start);
        RangeEnd = min(Alternative->Maximum, Ordering->End);
 
        if ((RangeEnd - Start + 1) >= Alternative->Length)
        {
            INT32 NewPriority = (INT32)(Ordering - Arbiter->OrderingList.Orderings) + 1;
            Alternative->Priority = Preferred ? -NewPriority : NewPriority;
            return;
        }
    }
 
    Alternative->Reserved[0] = 0;
    Alternative->Priority = Preferred ? ARBITER_PRIORITY_PREFERRED_RESERVED
                                      : ARBITER_PRIORITY_RESERVED;
}
 
CODE_SEG("PAGE")
static
BOOLEAN
ArbpIsRootEnumerated(
    _In_ PDEVICE_OBJECT DeviceObject)
{
    WCHAR Buffer[16];
    UNICODE_STRING Name;
    const UNICODE_STRING Root = RTL_CONSTANT_STRING(L"ROOT");
    ULONG Length = 0;
 
    PAGED_CODE();
 
    if (DeviceObject == NULL)
        return FALSE;
 
    if (!NT_SUCCESS(IoGetDeviceProperty(DeviceObject, DevicePropertyEnumeratorName,
                                        sizeof(Buffer), Buffer, &Length)))
    {
        return FALSE;
    }
 
    RtlInitUnicodeString(&Name, Buffer);
    return RtlEqualUnicodeString(&Root, &Name, TRUE);
}
 
CODE_SEG("PAGE")
static
BOOLEAN
ArbpSharesDriverStack(
    _In_ PDEVICE_OBJECT DeviceA,
    _In_ PDEVICE_OBJECT DeviceB)
{
    PDEVICE_OBJECT A, B;
 
    PAGED_CODE();
 
    for (A = DeviceA->AttachedDevice; A != NULL; A = A->AttachedDevice)
    {
        for (B = DeviceB->AttachedDevice; B != NULL; B = B->AttachedDevice)
        {
            if (A->DriverObject == B->DriverObject)
                return TRUE;
        }
    }
 
    return FALSE;
}
 
CODE_SEG("PAGE")
static
BOOLEAN
ArbpShareDriverExclusive(
    _In_ PARBITER_INSTANCE Arbiter,
    _Inout_ PARBITER_ALLOCATION_STATE ArbState)
{
    PARBITER_LIST_ENTRY Entry = ArbState->Entry;
    PDEVICE_OBJECT Requester;
    RTL_RANGE_LIST_ITERATOR Iterator;
    PRTL_RANGE Range;
    BOOLEAN RequesterIsRoot;
 
    PAGED_CODE();
 
    if (Entry == NULL || Entry->PhysicalDeviceObject == NULL ||
        ArbState->CurrentAlternative == NULL)
    {
        return FALSE;
    }
 
    Requester = Entry->PhysicalDeviceObject;
    RequesterIsRoot = ArbpIsRootEnumerated(Requester);
 
    if (!NT_SUCCESS(RtlGetFirstRange(Arbiter->PossibleAllocation, &Iterator, &Range)))
        return FALSE;
 
    while (Range != NULL)
    {
        /*
         * Candidate: overlaps the requested window, is not already made available
         * by attribute, and either the request or the range is driver-exclusive.
         */
        if (Range->Start <= ArbState->CurrentMaximum &&
            Range->End >= ArbState->CurrentMinimum &&
            !(Range->Attributes & ArbState->RangeAvailableAttributes) &&
            (ArbState->CurrentAlternative->Descriptor->ShareDisposition == CmResourceShareDriverExclusive ||
             (Range->Attributes & ARBITER_RANGE_SHARED_DRIVER)) &&
            Range->Owner != NULL)
        {
            PDEVICE_OBJECT Owner = (PDEVICE_OBJECT)Range->Owner;
            BOOLEAN Share = FALSE;
 
            /* Two root-enumerated devices may share; else only a shared driver. */
            if (RequesterIsRoot && ArbpIsRootEnumerated(Owner))
                Share = TRUE;
            else if (ArbpSharesDriverStack(Requester, Owner))
                Share = TRUE;
 
            if (Share)
            {
                ArbState->Start = ArbState->CurrentMinimum;
                ArbState->End = ArbState->CurrentMaximum;
                if (ArbState->CurrentAlternative->Descriptor->ShareDisposition ==
                    CmResourceShareDriverExclusive)
                {
                    ArbState->RangeAttributes |= ARBITER_RANGE_SHARED_DRIVER;
                }
                return TRUE;
            }
        }
 
        if (!NT_SUCCESS(RtlGetNextRange(&Iterator, &Range, TRUE)))
            break;
    }
 
    return FALSE;
}
 
CODE_SEG("PAGE")
static
BOOLEAN
ArbpReuseOwnedInterrupt(
    _In_ PARBITER_INSTANCE Arbiter,
    _Inout_ PARBITER_ALLOCATION_STATE ArbState)
{
    PARBITER_LIST_ENTRY Entry = ArbState->Entry;
    PARBITER_ALTERNATIVE Alternative = ArbState->CurrentAlternative;
    RTL_RANGE_LIST_ITERATOR Iterator;
    PRTL_RANGE Range;
 
    PAGED_CODE();
 
    if (Arbiter->ResourceType != CmResourceTypeInterrupt)
        return FALSE;
 
    if (Entry == NULL || Entry->PhysicalDeviceObject == NULL || Alternative == NULL)
        return FALSE;
 
    if (!NT_SUCCESS(RtlGetFirstRange(Arbiter->Allocation, &Iterator, &Range)))
        return FALSE;
 
    while (Range != NULL)
    {
        if ((PDEVICE_OBJECT)Range->Owner == Entry->PhysicalDeviceObject &&
            Range->Start >= ArbState->CurrentMinimum &&
            Range->Start <= ArbState->CurrentMaximum &&
            Range->End <= ArbState->CurrentMaximum &&
            (Range->End - Range->Start + 1) >= Alternative->Length)
        {
            ArbState->Start = Range->Start;
            ArbState->End = Range->Start + Alternative->Length - 1;
            return TRUE;
        }
 
        if (!NT_SUCCESS(RtlGetNextRange(&Iterator, &Range, TRUE)))
            break;
    }
 
    return FALSE;
}
 
CODE_SEG("PAGE")
static
BOOLEAN
ArbpTakeReservedWindow(
    _In_ PARBITER_INSTANCE Arbiter,
    _Inout_ PARBITER_ALTERNATIVE Alternative,
    _Out_ PUINT64 Minimum,
    _Out_ PUINT64 Maximum)
{
    ULONG Index;
 
    PAGED_CODE();
 
    if (Alternative->Reserved[0] == ARBITER_RESERVED_PASS_DONE)
        return FALSE;
 
    for (Index = Alternative->Reserved[0];
         Index < Arbiter->ReservedList.Count;
         ++Index)
    {
        PARBITER_ORDERING Window = &Arbiter->ReservedList.Orderings[Index];
        UINT64 Lo, Hi;
 
        if (Window->Start > Alternative->Maximum ||
            Alternative->Minimum > Window->End)
        {
            continue;  /* No intersection with this alternative's window */
        }
 
        Lo = max(Alternative->Minimum, Window->Start);
        Hi = min(Alternative->Maximum, Window->End);
        if ((Hi - Lo + 1) < Alternative->Length)
            continue;
 
        Alternative->Reserved[0] = Index + 1;
        *Minimum = Lo;
        *Maximum = Hi;
        return TRUE;
    }
 
    /*
     * Reserved windows exhausted. A final whole-window pass follows
     * turns on FIXED, and either answer is wrong for the other case.
     *
     * A flexible alternative must not get one: [Minimum, Maximum] ignores both
     * the ordering and the reserved list, re-granting the ranges the reserved
     * pass had just punched out. A bridge's [0, 0xFFFFFFFF] memory window
     * searched against an empty pool resolves to 0, placing the window on top
     * of RAM.
     *
     * A fixed alternative must get one: it has a single possible placement, so
     * the whole window is that candidate. Withholding it goes straight to
     * EXHAUSTED without ever calling FindSuitableRange, so neither the
     * boot-allocated availability mask nor OverrideConflict can grant the
     * device its own firmware configuration. That is fatal whenever no
     * ordering window spans the requirement, as the root port list's does not
     * below 0x100.
     */
    Alternative->Reserved[0] = ARBITER_RESERVED_PASS_DONE;
 
    if (Alternative->Flags & ARBITER_ALTERNATIVE_FLAG_FIXED)
    {
        *Minimum = Alternative->Minimum;
        *Maximum = Alternative->Maximum;
        return TRUE;
    }
 
    return FALSE;
}
 
CODE_SEG("PAGE")
BOOLEAN
NTAPI
ArbiterLibGetNextAllocationRange(
    _In_ PARBITER_INSTANCE Arbiter,
    _Inout_ PARBITER_ALLOCATION_STATE ArbState)
{
    PARBITER_ALTERNATIVE Alternative;
    PARBITER_ALTERNATIVE Lowest;
    UINT64 Minimum, Maximum;
 
    PAGED_CODE();
 
    if (ArbState->AlternativeCount == 0)
        return FALSE;
 
    for (;;)
    {
        /* Advance the alternative we last worked on, or seed all on first entry. */
        if (ArbState->CurrentAlternative != NULL)
        {
            ArbpWritePriority(Arbiter, ArbState->CurrentAlternative);
        }
        else
        {
            for (Alternative = ArbState->Alternatives;
                 Alternative < &ArbState->Alternatives[ArbState->AlternativeCount];
                 ++Alternative)
            {
                Alternative->Priority = ARBITER_PRIORITY_NULL;
                ArbpWritePriority(Arbiter, Alternative);
            }
        }
 
        /* Pick the best (lowest-priority) alternative. */
        Lowest = ArbState->Alternatives;
        for (Alternative = ArbState->Alternatives + 1;
             Alternative < &ArbState->Alternatives[ArbState->AlternativeCount];
             ++Alternative)
        {
            if (Alternative->Priority < Lowest->Priority)
                Lowest = Alternative;
        }
 
        if (Lowest->Priority == ARBITER_PRIORITY_EXHAUSTED)
            return FALSE;
 
        if (Lowest->Priority == ARBITER_PRIORITY_RESERVED ||
            Lowest->Priority == ARBITER_PRIORITY_PREFERRED_RESERVED)
        {
            /*
             * Last-resort pass: the reserved windows in turn, then the whole
             * requirement window (see ArbpTakeReservedWindow).
             */
            if (!ArbpTakeReservedWindow(Arbiter, Lowest, &Minimum, &Maximum))
            {
                /*
                 * CurrentAlternative must be set before looping. While it is
                 * still NULL, the top of the loop re-seeds every alternative's
                 * priority back to ARBITER_PRIORITY_NULL, which would discard
                 * the EXHAUSTED just recorded and spin forever.
                 */
                Lowest->Priority = ARBITER_PRIORITY_EXHAUSTED;
                ArbState->CurrentAlternative = Lowest;
                continue;
            }
        }
        else
        {
            PARBITER_ORDERING Ordering;
            ULONG Index = (Lowest->Priority < 0) ? (ULONG)(-(Lowest->Priority + 1))
                                                 : (ULONG)(Lowest->Priority - 1);
            if (Index >= Arbiter->OrderingList.Count)
            {
                Lowest->Priority = ARBITER_PRIORITY_EXHAUSTED;
                ArbState->CurrentAlternative = Lowest;
                continue;
            }
            Ordering = &Arbiter->OrderingList.Orderings[Index];
            Minimum = max(Lowest->Minimum, Ordering->Start);
            Maximum = min(Lowest->Maximum, Ordering->End);
        }
 
        /*
         * Trim the window so an aligned allocation of the required length is
         * possible; skip the window entirely if it cannot hold one.
         */
        if (Lowest->Length != 0)
        {
            UINT64 Alignment = Lowest->Alignment ? Lowest->Alignment : 1;
            UINT64 LengthMinusOne = Lowest->Length - 1;
            UINT64 AlignedMax;
 
            Minimum += Alignment - 1;
            Minimum -= Minimum % Alignment;
 
            if (Minimum > Maximum || LengthMinusOne > Maximum - Minimum)
            {
                ArbState->CurrentAlternative = Lowest;  /* consume this priority */
                continue;
            }
 
            AlignedMax = Maximum - LengthMinusOne;
            AlignedMax -= AlignedMax % Alignment;
            if (AlignedMax < Minimum)
            {
                ArbState->CurrentAlternative = Lowest;  /* no aligned start fits */
                continue;
            }
            Maximum = AlignedMax + LengthMinusOne;
        }
        else
        {
            Minimum = Lowest->Minimum;
            Maximum = Lowest->Maximum;
        }
 
        if (Minimum != ArbState->CurrentMinimum ||
            Maximum != ArbState->CurrentMaximum ||
            ArbState->CurrentAlternative != Lowest)
        {
            ArbState->CurrentMinimum = Minimum;
            ArbState->CurrentMaximum = Maximum;
            ArbState->CurrentAlternative = Lowest;
            return TRUE;
        }
 
        ArbState->CurrentAlternative = Lowest;
    }
}
 
CODE_SEG("PAGE")
BOOLEAN
NTAPI
ArbiterLibFindSuitableRange(
    _In_ PARBITER_INSTANCE Arbiter,
    _Inout_ PARBITER_ALLOCATION_STATE ArbState)
{
    PARBITER_ALTERNATIVE Alternative = ArbState->CurrentAlternative;
    ULONG Flags = 0;
    NTSTATUS Status;
 
    PAGED_CODE();
 
    if (Alternative == NULL)
        return FALSE;
 
    if (ArbState->CurrentMinimum > ArbState->CurrentMaximum)
        return FALSE;
 
    if (Alternative->Length == 0)
    {
        ArbState->Start = ArbState->CurrentMinimum;
        ArbState->End = ArbState->CurrentMinimum;
        return TRUE;
    }
 
    /*
     * Interrupt retention: give the device back its firmware-routed vector rather
     * than letting the top-down search pick an untranslatable one
     */
    if (ArbpReuseOwnedInterrupt(Arbiter, ArbState))
        return TRUE;
 
    /* Legacy requests consider preallocated (boot) ranges available. */
    if (ArbState->Entry != NULL &&
        (ArbState->Entry->RequestSource == ArbiterRequestLegacyReported ||
         ArbState->Entry->RequestSource == ArbiterRequestLegacyAssigned))
    {
        ArbState->RangeAvailableAttributes |= ARBITER_RANGE_BOOT_ALLOCATED;
    }
 
    if (ArbState->Flags & ARBITER_STATE_FLAG_NULL_CONFLICT_OK)
        Flags |= RTL_RANGE_LIST_NULL_CONFLICT_OK;
    if (Alternative->Flags & ARBITER_ALTERNATIVE_FLAG_SHARED)
        Flags |= RTL_RANGE_LIST_SHARED_OK;
    if (Alternative->Flags & ARBITER_ALTERNATIVE_FLAG_INACCESSIBLE_OK)
        ArbState->RangeAvailableAttributes |= ARBITER_RANGE_INACCESSIBLE;
 
    Status = RtlFindRange(Arbiter->PossibleAllocation,
                          ArbState->CurrentMinimum,
                          ArbState->CurrentMaximum,
                          Alternative->Length,
                          max(Alternative->Alignment, 1),
                          Flags,
                          ArbState->RangeAvailableAttributes,
                          Arbiter->ConflictCallbackContext,
                          Arbiter->ConflictCallback,
                          &ArbState->Start);
    if (!NT_SUCCESS(Status))
    {
        /*
         * The window is occupied.  A CmResourceShareDriverExclusive requirement
         * can still succeed by sharing the conflicting range with the same driver
         * or another root-enumerated device
         *
         * This matters a lot because HAL reverses quite a bit and marks it this.
         * This mechanism is how Windows "internally allows this".
         */
        if (ArbpShareDriverExclusive(Arbiter, ArbState))
            return TRUE;
        if (Arbiter->OverrideConflict != NULL &&
            Arbiter->OverrideConflict(Arbiter, ArbState))
        {
            return TRUE;
        }
 
        /*
         * A window that only fails because it runs into the MMCONFIG region
         * points at the firmware's MCFG table rather than at any device.
         */
        if (ArbiterLibIsConflictWithMmConfigRange(ArbState->CurrentMinimum,
                                                  ArbState->CurrentMaximum))
        {
            ArbState->Flags |= ARBITER_STATE_FLAG_MCFG_CONFLICT;
        }
 
        return FALSE;
    }
 
    ArbState->End = ArbState->Start + Alternative->Length - 1;
    return TRUE;
}
 
CODE_SEG("PAGE")
VOID
NTAPI
ArbiterLibAddAllocation(
    _In_ PARBITER_INSTANCE Arbiter,
    _Inout_ PARBITER_ALLOCATION_STATE ArbState)
{
    ULONG Flags = RTL_RANGE_LIST_ADD_IF_CONFLICT;
 
    PAGED_CODE();
 
    if (ArbState->CurrentAlternative != NULL &&
        (ArbState->CurrentAlternative->Flags & ARBITER_ALTERNATIVE_FLAG_SHARED))
    {
        Flags |= RTL_RANGE_LIST_ADD_SHARED;
    }
 
    RtlAddRange(Arbiter->PossibleAllocation,
                ArbState->Start,
                ArbState->End,
                ArbState->RangeAttributes,
                Flags,
                NULL,
                ArbState->Entry ? ArbState->Entry->PhysicalDeviceObject : NULL);
}
 
CODE_SEG("PAGE")
VOID
NTAPI
ArbiterLibBacktrackAllocation(
    _In_ PARBITER_INSTANCE Arbiter,
    _Inout_ PARBITER_ALLOCATION_STATE ArbState)
{
    PAGED_CODE();
 
    RtlDeleteRange(Arbiter->PossibleAllocation,
                   ArbState->Start,
                   ArbState->End,
                   ArbState->Entry ? ArbState->Entry->PhysicalDeviceObject : NULL);
}