able/windows-nt
1
0
Fork 0
Code Issues Pull requests Projects Releases Wiki Activity
windows-nt/Source/XPSP1/NT/base/basedrv/pnpmem/range.c
CryptoAlgo Inc b3cac27891 Add source files
2020-09-26 16:20:57 +08:00

810 lines
18 KiB
C
Raw Permalink Blame History

/*++
Copyright (c) 1999-2000 Microsoft Corporation
Module Name:
range.c
Abstract:
This module implements the range list routines for the Plug and Play Memory
driver.
Author:
Dave Richards (daveri) 16-Aug-1999
Environment:
Kernel mode only.
Revision History:
--*/
#include "pnpmem.h"
PPM_RANGE_LIST_ENTRY
PmAllocateRangeListEntry(
VOID
);
VOID
PmFreeRangeListEntry(
IN PPM_RANGE_LIST_ENTRY RangeListEntry
);
#ifdef ALLOC_PRAGMA
#pragma alloc_text(PAGE, PmAllocateRangeListEntry)
#pragma alloc_text(PAGE, PmInsertRangeInList)
#pragma alloc_text(PAGE, PmFreeRangeListEntry)
#pragma alloc_text(PAGE, PmAllocateRangeList)
#pragma alloc_text(PAGE, PmFreeRangeList)
#pragma alloc_text(PAGE, PmIsRangeListEmpty)
#pragma alloc_text(PAGE, PmDebugDumpRangeList)
#pragma alloc_text(PAGE, PmCopyRangeList)
#pragma alloc_text(PAGE, PmSubtractRangeList)
#pragma alloc_text(PAGE, PmIntersectRangeList)
#pragma alloc_text(PAGE, PmCreateRangeListFromCmResourceList)
#pragma alloc_text(PAGE, PmCreateRangeListFromPhysicalMemoryRanges)
#endif
PPM_RANGE_LIST_ENTRY
PmAllocateRangeListEntry(
VOID
)
/*++
Routine Description:
This function allocates a range list entry from paged pool.
Arguments:
None.
Return Value:
Upon success a pointer to a PM_RANGE_LIST_ENTRY object is returned,
otherwise NULL.
--*/
{
PPM_RANGE_LIST_ENTRY RangeListEntry;
PAGED_CODE();
RangeListEntry = ExAllocatePool(
PagedPool,
sizeof (PM_RANGE_LIST_ENTRY)
);
return RangeListEntry;
}
NTSTATUS
PmInsertRangeInList(
PPM_RANGE_LIST InsertionList,
ULONGLONG Start,
ULONGLONG End
)
{
PPM_RANGE_LIST_ENTRY entry;
entry = PmAllocateRangeListEntry();
if (entry == NULL) {
return STATUS_INSUFFICIENT_RESOURCES;
}
entry->Start = Start;
entry->End = End;
InsertTailList(&InsertionList->List,
&entry->ListEntry);
return STATUS_SUCCESS;
}
VOID
PmFreeRangeListEntry(
IN PPM_RANGE_LIST_ENTRY RangeListEntry
)
/*++
Routine Description:
This function de-allocates a range list entry object.
Arguments:
RangeListEntry - The PM_RANGE_LIST_ENTRY to be de-allocated.
Return Value:
None.
--*/
{
PAGED_CODE();
ASSERT(RangeListEntry != NULL);
ExFreePool(RangeListEntry);
}
PPM_RANGE_LIST
PmAllocateRangeList(
VOID
)
/*++
Routine Description:
This function allocates and initializes a range list from paged pool.
Arguments:
None.
Return Value:
Upon success a pointer to a PM_RANGE_LIST object is returned, otherwise
NULL.
--*/
{
PPM_RANGE_LIST RangeList;
PAGED_CODE();
RangeList = ExAllocatePool(
PagedPool,
sizeof (PM_RANGE_LIST)
);
if (RangeList != NULL) {
InitializeListHead(&RangeList->List);
}
return RangeList;
}
VOID
PmFreeRangeList(
IN PPM_RANGE_LIST RangeList
)
/*++
Routine Description:
This function removes all entries from a range list and de-allocates it.
Arguments:
RangeList - The PM_RANGE_LIST to be de-allocated.
Return Value:
None.
--*/
{
PLIST_ENTRY ListEntry;
PPM_RANGE_LIST_ENTRY RangeListEntry;
PAGED_CODE();
for (ListEntry = RangeList->List.Flink;
ListEntry != &RangeList->List;
ListEntry = RangeList->List.Flink) {
RangeListEntry = CONTAINING_RECORD(
ListEntry,
PM_RANGE_LIST_ENTRY,
ListEntry
);
RemoveEntryList(ListEntry);
PmFreeRangeListEntry(RangeListEntry);
}
ExFreePool(RangeList);
}
BOOLEAN
PmIsRangeListEmpty(
IN PPM_RANGE_LIST RangeList
)
/*++
Routine Description:
This function determines whether the specified range list is empty.
Arguments:
RangeList - The PM_RANGE_LIST.
Return Value:
TRUE if the PM_RANGE_LIST has no PM_RANGE_LIST_ENTRYs, otherwise FALSE.
--*/
{
PAGED_CODE();
return IsListEmpty(&RangeList->List);
}
VOID
PmDebugDumpRangeList(
IN ULONG DebugPrintLevel,
IN PCCHAR DebugMessage,
PPM_RANGE_LIST RangeList
)
{
PLIST_ENTRY listEntry;
PPM_RANGE_LIST_ENTRY rangeListEntry;
PmPrint((DebugPrintLevel, DebugMessage));
if (RangeList == NULL) {
PmPrint((DebugPrintLevel, "\tNULL\n"));
return;
} else if (PmIsRangeListEmpty(RangeList)) {
PmPrint((DebugPrintLevel, "\tEmpty\n"));
return;
} else {
for (listEntry = RangeList->List.Flink;
listEntry != &RangeList->List;
listEntry = listEntry->Flink) {
rangeListEntry = CONTAINING_RECORD(
listEntry,
PM_RANGE_LIST_ENTRY,
ListEntry
);
PmPrint((DebugPrintLevel, "\t0x%I64X - 0x%I64X\n",
rangeListEntry->Start, rangeListEntry->End));
}
}
}
PPM_RANGE_LIST
PmCopyRangeList(
IN PPM_RANGE_LIST SrcRangeList
)
/*++
Routine Description:
This function creates a copy of a PM_RANGE_LIST and its supporting
PM_RANGE_LIST_ENTRY objects.
Arguments:
SrcRangeList - The PM_RANGE_LIST to be copied.
Return Value:
Upon success a pointer to a PM_RANGE_LIST is returned, otherwise NULL.
--*/
{
PPM_RANGE_LIST DstRangeList;
PLIST_ENTRY ListEntry;
PPM_RANGE_LIST_ENTRY SrcRangeListEntry;
PPM_RANGE_LIST_ENTRY DstRangeListEntry;
PAGED_CODE();
DstRangeList = PmAllocateRangeList();
if (DstRangeList != NULL) {
for (ListEntry = SrcRangeList->List.Flink;
ListEntry != &SrcRangeList->List;
ListEntry = ListEntry->Flink) {
SrcRangeListEntry = CONTAINING_RECORD(
ListEntry,
PM_RANGE_LIST_ENTRY,
ListEntry
);
DstRangeListEntry = PmAllocateRangeListEntry();
if (DstRangeListEntry == NULL) {
PmFreeRangeList(DstRangeList);
DstRangeList = NULL;
break;
}
DstRangeListEntry->Start = SrcRangeListEntry->Start;
DstRangeListEntry->End = SrcRangeListEntry->End;
InsertTailList(
&DstRangeList->List,
&DstRangeListEntry->ListEntry
);
}
}
return DstRangeList;
}
PPM_RANGE_LIST
PmSubtractRangeList(
IN PPM_RANGE_LIST MinuendList,
IN PPM_RANGE_LIST SubtrahendList
)
/*++
Routine Description:
This function creates a new range list which represents the set difference
between MinuendList and SubtrahendList.
Arguments:
MinuendList - The minuend range list.
SubtrahendList - The subtrahend range list.
Return Value:
Upon success a pointer to the destination (difference) PM_RANGE_LIST is
returned, otherwise NULL.
--*/
{
PPM_RANGE_LIST DstRangeList;
PLIST_ENTRY DstListEntry;
PPM_RANGE_LIST_ENTRY DstRangeListEntry;
PLIST_ENTRY SrcListEntry;
PPM_RANGE_LIST_ENTRY SrcRangeListEntry;
ULONGLONG Start;
ULONGLONG End;
PLIST_ENTRY ListEntry;
PPM_RANGE_LIST_ENTRY RangeListEntry;
PAGED_CODE();
ASSERT(MinuendList != NULL);
ASSERT(SubtrahendList != NULL);
//
// Make a copy of the minuend.
//
DstRangeList = PmCopyRangeList(MinuendList);
if (DstRangeList != NULL) {
//
// Loop through each range list entry in the minuend.
//
for (DstListEntry = DstRangeList->List.Flink;
DstListEntry != &DstRangeList->List;
DstListEntry = DstListEntry->Flink) {
DstRangeListEntry = CONTAINING_RECORD(
DstListEntry,
PM_RANGE_LIST_ENTRY,
ListEntry
);
//
// Loop through each range list entry in the subtrahend.
//
for (SrcListEntry = SubtrahendList->List.Flink;
SrcListEntry != &SubtrahendList->List;
SrcListEntry = SrcListEntry->Flink) {
SrcRangeListEntry = CONTAINING_RECORD(
SrcListEntry,
PM_RANGE_LIST_ENTRY,
ListEntry
);
//
// Compute the intersection of the minuend and subtrahend
// range list entries.
//
Start = DstRangeListEntry->Start;
if (Start < SrcRangeListEntry->Start) {
Start = SrcRangeListEntry->Start;
};
End = DstRangeListEntry->End;
if (End > SrcRangeListEntry->End) {
End = SrcRangeListEntry->End;
};
if (Start > End) {
continue;
}
//
// There are 4 cases:
//
// 1. The intersection overlaps the minuend range completely.
// 2. The intersection overlaps the start of the minuend
// range.
// 3. The intersection overlaps the end of the minuend range.
// 4. The intersection overlaps the middle of the minuend
// range.
//
if (DstRangeListEntry->Start == Start) {
if (DstRangeListEntry->End == End) {
//
// Case 1: Remove the minuend range list entry.
//
ListEntry = DstListEntry;
DstListEntry = DstListEntry->Blink;
RemoveEntryList(ListEntry);
PmFreeRangeListEntry(DstRangeListEntry);
break;
} else {
//
// Case 2: Increase the minuend's start.
//
DstRangeListEntry->Start = End + 1;
}
} else {
if (DstRangeListEntry->End == End) {
//
// Case 3: Decrease the minend's end.
//
DstRangeListEntry->End = Start - 1;
} else {
//
// Case 4: Divide the range list entry into two
// pieces. The first range list entry's end should
// be just before the intersection start. The
// second range list entry's start should be just
// after the intersection end.
//
RangeListEntry = PmAllocateRangeListEntry();
if (RangeListEntry == NULL) {
PmFreeRangeList(DstRangeList);
return NULL;
}
RangeListEntry->Start = End + 1;
RangeListEntry->End = DstRangeListEntry->End;
//
// BUGBUG Break the list ordering but ensure that
// we'll perform the subtraction against the
// new range list entry as well.
//
InsertHeadList(
&DstRangeListEntry->ListEntry,
&RangeListEntry->ListEntry
);
DstRangeListEntry->End = Start - 1;
}
}
}
}
}
return DstRangeList;
}
PPM_RANGE_LIST
PmIntersectRangeList(
IN PPM_RANGE_LIST SrcRangeList1,
IN PPM_RANGE_LIST SrcRangeList2
)
/*++
Routine Description:
This function creates a new range list which represents the intersection
between SrcRangeList1 and SrcRangeList2.
Arguments:
SrcRangeList1, SrcRangeList - The range lists upon which to compute the
intersection.
Return Value:
Upon success a pointer to the destination (intersection) PM_RANGE_LIST is
returned, otherwise NULL.
--*/
{
PPM_RANGE_LIST DstRangeList;
PLIST_ENTRY SrcListEntry1;
PPM_RANGE_LIST_ENTRY SrcRangeListEntry1;
PLIST_ENTRY SrcListEntry2;
PPM_RANGE_LIST_ENTRY SrcRangeListEntry2;
ULONGLONG Start;
ULONGLONG End;
PPM_RANGE_LIST_ENTRY RangeListEntry;
PAGED_CODE();
ASSERT(SrcRangeList1 != NULL);
ASSERT(SrcRangeList2 != NULL);
DstRangeList = PmAllocateRangeList();
if (DstRangeList != NULL) {
for (SrcListEntry1 = SrcRangeList1->List.Flink;
SrcListEntry1 != &SrcRangeList1->List;
SrcListEntry1 = SrcListEntry1->Flink) {
SrcRangeListEntry1 = CONTAINING_RECORD(
SrcListEntry1,
PM_RANGE_LIST_ENTRY,
ListEntry
);
for (SrcListEntry2 = SrcRangeList2->List.Flink;
SrcListEntry2 != &SrcRangeList2->List;
SrcListEntry2 = SrcListEntry2->Flink) {
SrcRangeListEntry2 = CONTAINING_RECORD(
SrcListEntry2,
PM_RANGE_LIST_ENTRY,
ListEntry
);
Start = SrcRangeListEntry1->Start;
if (Start < SrcRangeListEntry2->Start) {
Start = SrcRangeListEntry2->Start;
};
End = SrcRangeListEntry1->End;
if (End > SrcRangeListEntry2->End) {
End = SrcRangeListEntry2->End;
};
if (Start > End) {
continue;
}
RangeListEntry = PmAllocateRangeListEntry();
if (RangeListEntry == NULL) {
PmFreeRangeList(DstRangeList);
return NULL;
}
RangeListEntry->Start = Start;
RangeListEntry->End = End;
InsertTailList(
&DstRangeList->List,
&RangeListEntry->ListEntry
);
}
}
}
return DstRangeList;
}
PPM_RANGE_LIST
PmCreateRangeListFromCmResourceList(
IN PCM_RESOURCE_LIST CmResourceList
)
/*++
Routine Description:
This function converts a CM_RESOURCE_LIST to a PM_RANGE_LIST. Only
CmResourceTypeMemory descriptors are added to the PM_RANGE_LIST.
Arguments:
CmResourceList - The CM_RESOURCE_LIST to convert.
Return Value:
Upon success a pointer to the converted PM_RANGE_LIST is returned,
otherwise NULL.
--*/
{
PPM_RANGE_LIST RangeList;
PCM_FULL_RESOURCE_DESCRIPTOR FDesc;
ULONG FIndex;
PCM_PARTIAL_RESOURCE_DESCRIPTOR PDesc;
ULONG PIndex;
ULONGLONG Start;
ULONGLONG End;
PPM_RANGE_LIST_ENTRY RangeListEntry;
PAGED_CODE();
RangeList = PmAllocateRangeList();
if (RangeList == NULL) {
return NULL;
}
FDesc = CmResourceList->List;
//
// Note: Any Device-Specific partial descriptor (which could be
// variably sized) is defined to be at the end and thus this code
// is safe.
//
for (FIndex = 0;
FIndex < CmResourceList->Count;
FIndex++) {
PDesc = FDesc->PartialResourceList.PartialDescriptors;
for (PIndex = 0;
PIndex < FDesc->PartialResourceList.Count;
PIndex++, PDesc++) {
//
// ISSUE Fix for ia64 (andy's change), IA32 large memory region
//
if (PDesc->Type == CmResourceTypeMemory) {
Start = PDesc->u.Memory.Start.QuadPart;
End = Start + PDesc->u.Memory.Length - 1;
RangeListEntry = PmAllocateRangeListEntry();
if (RangeListEntry == NULL) {
PmFreeRangeList(RangeList);
return NULL;
}
RangeListEntry->Start = Start;
RangeListEntry->End = End;
InsertTailList(
&RangeList->List,
&RangeListEntry->ListEntry
);
}
}
FDesc = (PCM_FULL_RESOURCE_DESCRIPTOR)PDesc;
}
return RangeList;
}
PPM_RANGE_LIST
PmCreateRangeListFromPhysicalMemoryRanges(
VOID
)
/*++
Routine Description:
This function calls MmGetPhysicalRanges and converts the returned
PHYSICAL_MEMORY_RANGE list to a PM_RANGE_LIST.
Arguments:
None.
Return Value:
Upon success a pointer to the converted PM_RANGE_LIST is returned,
otherwise NULL.
--*/
{
PPM_RANGE_LIST RangeList;
PPHYSICAL_MEMORY_RANGE MemoryRange;
ULONG Index;
ULONGLONG Start;
ULONGLONG End;
PPM_RANGE_LIST_ENTRY RangeListEntry;
PAGED_CODE();
RangeList = PmAllocateRangeList();
if (RangeList != NULL) {
MemoryRange = MmGetPhysicalMemoryRanges();
if (MemoryRange == NULL) {
PmFreeRangeList(RangeList);
RangeList = NULL;
} else {
for (Index = 0;
MemoryRange[Index].NumberOfBytes.QuadPart != 0;
Index++) {
Start = MemoryRange[Index].BaseAddress.QuadPart;
End = Start + (MemoryRange[Index].NumberOfBytes.QuadPart - 1);
RangeListEntry = PmAllocateRangeListEntry();
if (RangeListEntry == NULL) {
PmFreeRangeList(RangeList);
ExFreePool(MemoryRange);
return NULL;
}
RangeListEntry->Start = Start;
RangeListEntry->End = End;
InsertTailList(
&RangeList->List,
&RangeListEntry->ListEntry
);
}
ExFreePool(MemoryRange);
}
}
return RangeList;
}
Reference in a new issue View git blame Copy permalink