You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
1359 lines
40 KiB
1359 lines
40 KiB
/*++
|
|
|
|
Copyright (c) Microsoft Corporation. All rights reserved.
|
|
|
|
Module Name:
|
|
|
|
pnprlist.c
|
|
|
|
Abstract:
|
|
|
|
This module contains routines to manipulate relations list. Relation lists
|
|
are used by Plug and Play during the processing of device removal and
|
|
ejection.
|
|
|
|
These routines are all pageable and can't be called at raised IRQL or with
|
|
a spinlock held.
|
|
|
|
Author:
|
|
|
|
Robert Nelson (robertn) Apr, 1998.
|
|
|
|
Revision History:
|
|
|
|
--*/
|
|
|
|
#include "pnpmgrp.h"
|
|
#pragma hdrstop
|
|
|
|
#ifdef POOL_TAGGING
|
|
#undef ExAllocatePool
|
|
#define ExAllocatePool(a,b) ExAllocatePoolWithTag(a,b,'lrpP')
|
|
#endif
|
|
|
|
#ifdef ALLOC_PRAGMA
|
|
#pragma alloc_text(PAGE, IopAddRelationToList)
|
|
#pragma alloc_text(PAGE, IopAllocateRelationList)
|
|
#pragma alloc_text(PAGE, IopCompressRelationList)
|
|
#pragma alloc_text(PAGE, IopEnumerateRelations)
|
|
#pragma alloc_text(PAGE, IopFreeRelationList)
|
|
#pragma alloc_text(PAGE, IopGetRelationsCount)
|
|
#pragma alloc_text(PAGE, IopGetRelationsTaggedCount)
|
|
#pragma alloc_text(PAGE, IopIsRelationInList)
|
|
#pragma alloc_text(PAGE, IopMergeRelationLists)
|
|
#pragma alloc_text(PAGE, IopRemoveIndirectRelationsFromList)
|
|
#pragma alloc_text(PAGE, IopRemoveRelationFromList)
|
|
#pragma alloc_text(PAGE, IopSetAllRelationsTags)
|
|
#pragma alloc_text(PAGE, IopSetRelationsTag)
|
|
#endif
|
|
|
|
#define RELATION_FLAGS 0x00000003
|
|
|
|
#define RELATION_FLAG_TAGGED 0x00000001
|
|
#define RELATION_FLAG_DESCENDANT 0x00000002
|
|
|
|
NTSTATUS
|
|
IopAddRelationToList(
|
|
IN PRELATION_LIST List,
|
|
IN PDEVICE_OBJECT DeviceObject,
|
|
IN BOOLEAN DirectDescendant,
|
|
IN BOOLEAN Tagged
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
Adds an element to a relation list.
|
|
|
|
If this is the first DeviceObject of a particular level then a new
|
|
RELATION_LIST_ENTRY will be allocated.
|
|
|
|
This routine should only be called on an uncompressed relation list,
|
|
otherwise it is likely that STATUS_INVALID_PARAMETER will be returned.
|
|
|
|
Arguments:
|
|
|
|
List Relation list to which the DeviceObject is added.
|
|
|
|
DeviceObject DeviceObject to be added to List. It must be a
|
|
PhysicalDeviceObject (PDO).
|
|
|
|
DirectDescendant Indicates whether DeviceObject is a direct descendant of
|
|
the original target device of this remove.
|
|
|
|
Tagged Indicates whether DeviceObject should be tagged in List.
|
|
|
|
Return Value:
|
|
|
|
STATUS_SUCCESS
|
|
|
|
The DeviceObject was added successfully.
|
|
|
|
STATUS_OBJECT_NAME_COLLISION
|
|
|
|
The DeviceObject already exists in the relation list.
|
|
|
|
STATUS_INSUFFICIENT_RESOURCES
|
|
|
|
There isn't enough PagedPool available to allocate a new
|
|
RELATION_LIST_ENTRY.
|
|
|
|
STATUS_INVALID_PARAMETER
|
|
|
|
The level of the DEVICE_NODE associated with DeviceObject is less than
|
|
FirstLevel or greater than the MaxLevel.
|
|
|
|
STATUS_NO_SUCH_DEVICE
|
|
|
|
DeviceObject is not a PhysicalDeviceObject (PDO), it doesn't have a
|
|
DEVICE_NODE associated with it.
|
|
|
|
--*/
|
|
|
|
{
|
|
PDEVICE_NODE deviceNode;
|
|
PRELATION_LIST_ENTRY entry;
|
|
ULONG level;
|
|
ULONG index;
|
|
ULONG flags;
|
|
|
|
PAGED_CODE();
|
|
|
|
flags = 0;
|
|
|
|
if (Tagged) {
|
|
Tagged = 1;
|
|
flags |= RELATION_FLAG_TAGGED;
|
|
}
|
|
|
|
if (DirectDescendant) {
|
|
flags |= RELATION_FLAG_DESCENDANT;
|
|
}
|
|
|
|
if ((deviceNode = DeviceObject->DeviceObjectExtension->DeviceNode) != NULL) {
|
|
level = deviceNode->Level;
|
|
|
|
//
|
|
// Since this routine is called with the DeviceNode Tree locked and
|
|
// List is initially allocated with enough entries to hold the deepest
|
|
// DEVICE_NODE this ASSERT should never fire. If it does then either
|
|
// the tree is changing or we were given a compressed list.
|
|
//
|
|
ASSERT(List->FirstLevel <= level && level <= List->MaxLevel);
|
|
|
|
if (List->FirstLevel <= level && level <= List->MaxLevel) {
|
|
|
|
if ((entry = List->Entries[ level - List->FirstLevel ]) == NULL) {
|
|
|
|
//
|
|
// This is the first DeviceObject of its level, allocate a new
|
|
// RELATION_LIST_ENTRY.
|
|
//
|
|
entry = ExAllocatePool( PagedPool,
|
|
sizeof(RELATION_LIST_ENTRY) +
|
|
IopNumberDeviceNodes * sizeof(PDEVICE_OBJECT));
|
|
|
|
if (entry == NULL) {
|
|
return STATUS_INSUFFICIENT_RESOURCES;
|
|
}
|
|
|
|
//
|
|
// We always allocate enough Devices to hold the whole tree as
|
|
// a simplification. Since each entry is a PDEVICE_OBJECT and
|
|
// there is generally under 50 devices on a machine this means
|
|
// under 1K for each entry. The excess space will be freed when
|
|
// the list is compressed.
|
|
//
|
|
entry->Count = 0;
|
|
entry->MaxCount = IopNumberDeviceNodes;
|
|
|
|
List->Entries[ level - List->FirstLevel ] = entry;
|
|
}
|
|
|
|
//
|
|
// There should always be room for a DeviceObject since the Entry is
|
|
// initially dimensioned large enough to hold all the DEVICE_NODES
|
|
// in the system.
|
|
//
|
|
ASSERT(entry->Count < entry->MaxCount);
|
|
|
|
if (entry->Count < entry->MaxCount) {
|
|
//
|
|
// Search the list to see if DeviceObject has already been
|
|
// added.
|
|
//
|
|
for (index = 0; index < entry->Count; index++) {
|
|
if (((ULONG_PTR)entry->Devices[ index ] & ~RELATION_FLAGS) == (ULONG_PTR)DeviceObject) {
|
|
|
|
//
|
|
// DeviceObject already exists in the list. However
|
|
// the Direct Descendant flag may differ. We will
|
|
// override it if DirectDescendant is TRUE. This could
|
|
// happen if we merged two relation lists.
|
|
|
|
if (DirectDescendant) {
|
|
entry->Devices[ index ] = (PDEVICE_OBJECT)((ULONG_PTR)entry->Devices[ index ] | RELATION_FLAG_DESCENDANT);
|
|
}
|
|
|
|
return STATUS_OBJECT_NAME_COLLISION;
|
|
}
|
|
}
|
|
} else {
|
|
//
|
|
// There isn't room in the Entry for another DEVICE_OBJECT, the
|
|
// list has probably already been compressed.
|
|
//
|
|
return STATUS_INVALID_PARAMETER;
|
|
}
|
|
|
|
//
|
|
// Take out a reference on DeviceObject, we will release it when we
|
|
// free the list or remove the DeviceObject from the list.
|
|
//
|
|
ObReferenceObject( DeviceObject );
|
|
IopDbgPrint((IOP_LOADUNLOAD_INFO_LEVEL,
|
|
"%wZ added as a relation %s\n",
|
|
&deviceNode->InstancePath,
|
|
(DirectDescendant)? "(direct descendant)" : ""));
|
|
|
|
entry->Devices[ index ] = (PDEVICE_OBJECT)((ULONG_PTR)DeviceObject | flags);
|
|
entry->Count++;
|
|
|
|
List->Count++;
|
|
List->TagCount += Tagged;
|
|
|
|
return STATUS_SUCCESS;
|
|
} else {
|
|
//
|
|
// There isn't an Entry available for the level of this
|
|
// DEVICE_OBJECT, the list has probably already been compressed.
|
|
//
|
|
|
|
return STATUS_INVALID_PARAMETER;
|
|
}
|
|
} else {
|
|
//
|
|
// DeviceObject is not a PhysicalDeviceObject (PDO).
|
|
//
|
|
return STATUS_NO_SUCH_DEVICE;
|
|
}
|
|
}
|
|
|
|
PRELATION_LIST
|
|
IopAllocateRelationList(
|
|
IN PLUGPLAY_DEVICE_DELETE_TYPE OperationCode
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
Allocate a new Relations List. The list is initially sized large enough to
|
|
hold the deepest DEVICE_NODE encountered since the system started.
|
|
|
|
Arguments:
|
|
|
|
OperationCode - Type of operation the relation list is being allocated for.
|
|
|
|
Return Value:
|
|
|
|
Newly allocated list if enough PagedPool is available, otherwise NULL.
|
|
|
|
--*/
|
|
|
|
{
|
|
PRELATION_LIST list;
|
|
ULONG maxLevel;
|
|
ULONG listSize;
|
|
|
|
PAGED_CODE();
|
|
|
|
//
|
|
// Level number of the deepest DEVICE_NODE allocated since the system
|
|
// started.
|
|
//
|
|
maxLevel = IopMaxDeviceNodeLevel;
|
|
listSize = sizeof(RELATION_LIST) + maxLevel * sizeof(PRELATION_LIST_ENTRY);
|
|
|
|
list = (PRELATION_LIST) PiAllocateCriticalMemory(
|
|
OperationCode,
|
|
PagedPool,
|
|
listSize,
|
|
'rcpP'
|
|
);
|
|
|
|
if (list != NULL) {
|
|
|
|
RtlZeroMemory(list, listSize);
|
|
// list->FirstLevel = 0;
|
|
// list->Count = 0;
|
|
// list->Tagged = 0;
|
|
list->MaxLevel = maxLevel;
|
|
}
|
|
|
|
return list;
|
|
}
|
|
|
|
NTSTATUS
|
|
IopCompressRelationList(
|
|
IN OUT PRELATION_LIST *List
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
Compresses the relation list by reallocating the list and all the entries so
|
|
that they a just large enough to hold their current contents.
|
|
|
|
Once a list has been compressed IopAddRelationToList and
|
|
IopMergeRelationLists targetting this list are both likely to fail.
|
|
|
|
Arguments:
|
|
|
|
List Relation List to compress.
|
|
|
|
Return Value:
|
|
|
|
STATUS_SUCCESS
|
|
|
|
The list was compressed. Although this routine does allocate memory and
|
|
the allocation can fail, the routine itself will never fail. Since the
|
|
memory we are allocating is always smaller then the memory it is
|
|
replacing we just keep the old memory if the allocation fails.
|
|
|
|
--*/
|
|
|
|
{
|
|
PRELATION_LIST oldList, newList;
|
|
PRELATION_LIST_ENTRY oldEntry, newEntry;
|
|
ULONG lowestLevel;
|
|
ULONG highestLevel;
|
|
ULONG index;
|
|
|
|
PAGED_CODE();
|
|
|
|
oldList = *List;
|
|
|
|
//
|
|
// Initialize lowestLevel and highestLevel with illegal values chosen so
|
|
// that the first real entry will override them.
|
|
//
|
|
lowestLevel = oldList->MaxLevel;
|
|
highestLevel = oldList->FirstLevel;
|
|
|
|
//
|
|
// Loop through the list looking for allocated entries.
|
|
//
|
|
for (index = 0; index <= (oldList->MaxLevel - oldList->FirstLevel); index++) {
|
|
|
|
if ((oldEntry = oldList->Entries[ index ]) != NULL) {
|
|
//
|
|
// This entry is allocated, update lowestLevel and highestLevel if
|
|
// necessary.
|
|
//
|
|
if (lowestLevel > index) {
|
|
lowestLevel = index;
|
|
}
|
|
|
|
if (highestLevel < index) {
|
|
highestLevel = index;
|
|
}
|
|
|
|
if (oldEntry->Count < oldEntry->MaxCount) {
|
|
|
|
//
|
|
// This entry is only partially full. Allocate a new entry
|
|
// which is just the right size to hold the current number of
|
|
// PDEVICE_OBJECTs.
|
|
//
|
|
newEntry = ExAllocatePool( PagedPool,
|
|
sizeof(RELATION_LIST_ENTRY) +
|
|
(oldEntry->Count - 1) * sizeof(PDEVICE_OBJECT));
|
|
|
|
if (newEntry != NULL) {
|
|
|
|
//
|
|
// Initialize Count and MaxCount to the number of
|
|
// PDEVICE_OBJECTs in the old entry.
|
|
//
|
|
newEntry->Count = oldEntry->Count;
|
|
newEntry->MaxCount = oldEntry->Count;
|
|
|
|
//
|
|
// Copy the PDEVICE_OBJECTs from the old entry to the new
|
|
// one.
|
|
//
|
|
RtlCopyMemory( newEntry->Devices,
|
|
oldEntry->Devices,
|
|
oldEntry->Count * sizeof(PDEVICE_OBJECT));
|
|
|
|
//
|
|
// Free the old entry and store the new entry in the list.
|
|
//
|
|
ExFreePool( oldEntry );
|
|
|
|
oldList->Entries[ index ] = newEntry;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
//
|
|
// Assert that the old list isn't empty.
|
|
//
|
|
ASSERT(lowestLevel <= highestLevel);
|
|
|
|
if (lowestLevel > highestLevel) {
|
|
//
|
|
// The list is empty - we shouldn't get asked to compress an empty list
|
|
// but lets do it anyways.
|
|
//
|
|
lowestLevel = 0;
|
|
highestLevel = 0;
|
|
}
|
|
|
|
//
|
|
// Check if the old list had unused entries at the beginning or the end of
|
|
// the Entries array.
|
|
//
|
|
if (lowestLevel != oldList->FirstLevel || highestLevel != oldList->MaxLevel) {
|
|
|
|
//
|
|
// Allocate a new List with just enough Entries to hold those between
|
|
// FirstLevel and MaxLevel inclusive.
|
|
//
|
|
newList = ExAllocatePool( PagedPool,
|
|
sizeof(RELATION_LIST) +
|
|
(highestLevel - lowestLevel) * sizeof(PRELATION_LIST_ENTRY));
|
|
|
|
if (newList != NULL) {
|
|
//
|
|
// Copy the old list to the new list and return it to the caller.
|
|
//
|
|
newList->Count = oldList->Count;
|
|
newList->TagCount = oldList->TagCount;
|
|
newList->FirstLevel = lowestLevel;
|
|
newList->MaxLevel = highestLevel;
|
|
|
|
RtlCopyMemory( newList->Entries,
|
|
&oldList->Entries[ lowestLevel ],
|
|
(highestLevel - lowestLevel + 1) * sizeof(PRELATION_LIST_ENTRY));
|
|
|
|
ExFreePool( oldList );
|
|
|
|
*List = newList;
|
|
}
|
|
}
|
|
|
|
return STATUS_SUCCESS;
|
|
}
|
|
|
|
BOOLEAN
|
|
IopEnumerateRelations(
|
|
IN PRELATION_LIST List,
|
|
IN OUT PULONG Marker,
|
|
OUT PDEVICE_OBJECT *DeviceObject,
|
|
OUT BOOLEAN *DirectDescendant OPTIONAL,
|
|
OUT BOOLEAN *Tagged OPTIONAL,
|
|
IN BOOLEAN Reverse
|
|
)
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
Enumerates the relations in a list.
|
|
|
|
Arguments:
|
|
|
|
List Relation list to be enumerated.
|
|
|
|
Marker Cookie used to maintain current place in the list. It
|
|
must be initialized to 0 the first time
|
|
IopEnumerateRelations is called.
|
|
|
|
DeviceObject Returned Relation.
|
|
|
|
DirectDescendant If specified then it is set if the relation is a direct
|
|
descendant of the original target device of this remove.
|
|
|
|
Tagged If specified then it is set if the relation is tagged
|
|
otherwise it is cleared.
|
|
|
|
Reverse Direction of traversal, TRUE means from deepest to
|
|
closest to the root, FALSE means from the root down.
|
|
|
|
If Reverse changes on a subsequent call then the
|
|
previously enumerated relation is skipped. For example,
|
|
given the sequence A, B, C, D, E. If
|
|
IopEnumerateRelations is called thrice with Reverse set
|
|
to FALSE and then called repeatedly with Reverse set to
|
|
TRUE until it returns FALSE, the sequence would be: A,
|
|
B, C, B, A.
|
|
|
|
Once the end has been reached it is not possible to
|
|
change directions.
|
|
|
|
Return Value:
|
|
|
|
TRUE - DeviceObject and optionally Tagged have been set to the next
|
|
relation.
|
|
|
|
FALSE - There are no more relations.
|
|
|
|
--*/
|
|
{
|
|
PRELATION_LIST_ENTRY entry;
|
|
LONG levelIndex;
|
|
ULONG entryIndex;
|
|
|
|
PAGED_CODE();
|
|
|
|
//
|
|
// The basic assumptions of our use of Marker is that there will never be
|
|
// more than 16M DeviceNodes at any one level and that the tree will never
|
|
// be more than 127 deep.
|
|
//
|
|
// The format of Marker is
|
|
// Bit 31 = Valid (used to distinguish the initial call
|
|
// Bit 30-24 = Current index into entries
|
|
// Bit 23-0 = Current index into devices, 0xFFFFFF means last
|
|
//
|
|
if (*Marker == ~0U) {
|
|
//
|
|
// We've reached the end.
|
|
//
|
|
return FALSE;
|
|
}
|
|
|
|
if (*Marker == 0) {
|
|
//
|
|
// This is the initial call to IopEnumerateRelations
|
|
//
|
|
if (Reverse) {
|
|
//
|
|
// Initialize levelIndex to the last element of Entries
|
|
//
|
|
levelIndex = List->MaxLevel - List->FirstLevel;
|
|
} else {
|
|
//
|
|
// Initialize levelIndex to the first element of Entries
|
|
//
|
|
levelIndex = 0;
|
|
}
|
|
//
|
|
// Initialize entryIndex to unknown element of Devices. If we are going
|
|
// in reverse then this will appear to be beyond the last element and
|
|
// we'll adjust it the last one. If we are going forward then this will
|
|
// appear to be just prior to the first element so when we increment it,
|
|
// it will become zero.
|
|
//
|
|
entryIndex = ~0U;
|
|
} else {
|
|
//
|
|
// Bit 31 is our valid bit, used to distinguish level 0, device 0 from
|
|
// the first time call.
|
|
//
|
|
ASSERT(*Marker & ((ULONG)1 << 31));
|
|
//
|
|
// Current level stored in bits 30-24.
|
|
//
|
|
levelIndex = (*Marker >> 24) & 0x7F;
|
|
//
|
|
// Current device stored in bits 23-0.
|
|
//
|
|
entryIndex = *Marker & 0x00FFFFFF;
|
|
}
|
|
|
|
if (Reverse) {
|
|
//
|
|
// We are traversing the list bottom up, from the deepest device towards
|
|
// the root.
|
|
//
|
|
for ( ; levelIndex >= 0; levelIndex--) {
|
|
|
|
//
|
|
// Since the Entries array can be sparse find the next allocated
|
|
// Entry.
|
|
//
|
|
if ((entry = List->Entries[ levelIndex ]) != NULL) {
|
|
|
|
if (entryIndex > entry->Count) {
|
|
//
|
|
// entryIndex (the current one) is greater than Count, this
|
|
// will be the case where it is 0xFFFFFF, in other words
|
|
// unspecified. Adjust it so that it is one past the last
|
|
// one in this Entry.
|
|
//
|
|
entryIndex = entry->Count;
|
|
}
|
|
|
|
if (entryIndex > 0) {
|
|
|
|
//
|
|
// The current entry is beyond the first entry so the next
|
|
// entry (which is the one we are looking for is immediately
|
|
// prior, adjust entryIndex.
|
|
//
|
|
entryIndex--;
|
|
|
|
//
|
|
// Get the device object and remove the tag.
|
|
//
|
|
*DeviceObject = (PDEVICE_OBJECT)((ULONG_PTR)entry->Devices[ entryIndex ] & ~RELATION_FLAGS);
|
|
|
|
if (Tagged != NULL) {
|
|
//
|
|
// The caller is interested in the tag value.
|
|
//
|
|
*Tagged = (BOOLEAN)((ULONG_PTR)entry->Devices[ entryIndex ] & RELATION_FLAG_TAGGED);
|
|
}
|
|
|
|
if (DirectDescendant != NULL) {
|
|
//
|
|
// The caller is interested in the DirectDescendant value.
|
|
//
|
|
*DirectDescendant = (BOOLEAN)((ULONG_PTR)entry->Devices[ entryIndex ] & RELATION_FLAG_DESCENDANT);
|
|
}
|
|
|
|
//
|
|
// Update the marker (info for current device)
|
|
//
|
|
*Marker = ((ULONG)1 << 31) | (levelIndex << 24) | (entryIndex & 0x00FFFFFF);
|
|
|
|
return TRUE;
|
|
}
|
|
}
|
|
|
|
//
|
|
// The current device object has been deleted or the current
|
|
// device object is the first one in this Entry.
|
|
// We need to continue to search backwards through the other
|
|
// Entries.
|
|
//
|
|
entryIndex = ~0U;
|
|
}
|
|
} else {
|
|
for ( ; levelIndex <= (LONG)(List->MaxLevel - List->FirstLevel); levelIndex++) {
|
|
|
|
//
|
|
// Since the Entries array can be sparse find the next allocated
|
|
// Entry.
|
|
//
|
|
if ((entry = List->Entries[ levelIndex ]) != NULL) {
|
|
|
|
//
|
|
// entryIndex is the index of the current device or 0xFFFFFFFF
|
|
// if this is the first time we have been called or the current
|
|
// current device is the last one in its Entry. Increment the
|
|
// index to point to the next device.
|
|
//
|
|
entryIndex++;
|
|
|
|
if (entryIndex < entry->Count) {
|
|
|
|
//
|
|
// The next device is within this entry.
|
|
//
|
|
//
|
|
// Get the device object and remove the tag.
|
|
//
|
|
*DeviceObject = (PDEVICE_OBJECT)((ULONG_PTR)entry->Devices[ entryIndex ] & ~RELATION_FLAGS);
|
|
|
|
if (Tagged != NULL) {
|
|
//
|
|
// The caller is interested in the tag value.
|
|
//
|
|
*Tagged = (BOOLEAN)((ULONG_PTR)entry->Devices[ entryIndex ] & RELATION_FLAG_TAGGED);
|
|
}
|
|
|
|
if (DirectDescendant != NULL) {
|
|
//
|
|
// The caller is interested in the DirectDescendant value.
|
|
//
|
|
*DirectDescendant = (BOOLEAN)((ULONG_PTR)entry->Devices[ entryIndex ] & RELATION_FLAG_DESCENDANT);
|
|
}
|
|
|
|
//
|
|
// Update the marker (info for current device)
|
|
//
|
|
*Marker = ((ULONG)1 << 31) | (levelIndex << 24) | (entryIndex & 0x00FFFFFF);
|
|
|
|
return TRUE;
|
|
}
|
|
}
|
|
|
|
//
|
|
// The current device has been removed or we have processed the
|
|
// last device in the current entry.
|
|
// Set entryIndex so that it is just before the first device in
|
|
// the next entry. Continue the search looking for the next
|
|
// allocated Entry.
|
|
//
|
|
entryIndex = ~0U;
|
|
}
|
|
}
|
|
|
|
//
|
|
// We are at the end of the list
|
|
//
|
|
*Marker = ~0U;
|
|
*DeviceObject = NULL;
|
|
|
|
if (Tagged != NULL) {
|
|
*Tagged = FALSE;
|
|
}
|
|
|
|
if (DirectDescendant != NULL) {
|
|
*DirectDescendant = FALSE;
|
|
}
|
|
|
|
return FALSE;
|
|
}
|
|
|
|
VOID
|
|
IopFreeRelationList(
|
|
IN PRELATION_LIST List
|
|
)
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
Free a relation list allocated by IopAllocateRelationList.
|
|
|
|
Arguments:
|
|
|
|
List The list to be freed.
|
|
|
|
Return Value:
|
|
|
|
NONE.
|
|
|
|
--*/
|
|
{
|
|
PRELATION_LIST_ENTRY entry;
|
|
ULONG levelIndex;
|
|
ULONG entryIndex;
|
|
|
|
PAGED_CODE();
|
|
|
|
//
|
|
// Search the list looking for allocated Entries.
|
|
//
|
|
for (levelIndex = 0; levelIndex <= (List->MaxLevel - List->FirstLevel); levelIndex++) {
|
|
|
|
if ((entry = List->Entries[ levelIndex ]) != NULL) {
|
|
//
|
|
// This entry has been allocated.
|
|
//
|
|
for (entryIndex = 0; entryIndex < entry->Count; entryIndex++) {
|
|
//
|
|
// Dereference all the Devices in the entry.
|
|
//
|
|
ObDereferenceObject((PDEVICE_OBJECT)((ULONG_PTR)entry->Devices[ entryIndex ] & ~RELATION_FLAGS));
|
|
}
|
|
//
|
|
// Free the Entry.
|
|
//
|
|
ExFreePool( entry );
|
|
}
|
|
}
|
|
|
|
//
|
|
// Free the list. It isn't necessary to dereference the DeviceObject that
|
|
// was the original target that caused the list to be created. This
|
|
// DeviceObject is also in one of the Entries and its reference is taken
|
|
// and released there.
|
|
//
|
|
ExFreePool( List );
|
|
}
|
|
|
|
ULONG
|
|
IopGetRelationsCount(
|
|
PRELATION_LIST List
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
Returns the total number of relations (Device Objects) in all the entries.
|
|
|
|
Arguments:
|
|
|
|
List Relation List.
|
|
|
|
Return Value:
|
|
|
|
Count of relations (Device Objects).
|
|
|
|
--*/
|
|
|
|
{
|
|
PAGED_CODE();
|
|
|
|
return List->Count;
|
|
}
|
|
|
|
ULONG
|
|
IopGetRelationsTaggedCount(
|
|
PRELATION_LIST List
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
Returns the total number of relations (Device Objects) in all the entries
|
|
which are tagged.
|
|
|
|
Arguments:
|
|
|
|
List Relation List.
|
|
|
|
Return Value:
|
|
|
|
Count of tagged relations (Device Objects).
|
|
|
|
--*/
|
|
|
|
{
|
|
PAGED_CODE();
|
|
|
|
return List->TagCount;
|
|
}
|
|
|
|
BOOLEAN
|
|
IopIsRelationInList(
|
|
PRELATION_LIST List,
|
|
PDEVICE_OBJECT DeviceObject
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
Checks if a relation (Device Object) exists in the specified relation list.
|
|
|
|
Arguments:
|
|
|
|
List Relation list to check.
|
|
|
|
DeviceObject Relation to be checked.
|
|
|
|
|
|
Return Value:
|
|
|
|
TRUE
|
|
|
|
Relation exists.
|
|
|
|
FALSE
|
|
|
|
Relation is not in the list.
|
|
|
|
--*/
|
|
|
|
{
|
|
PDEVICE_NODE deviceNode;
|
|
PRELATION_LIST_ENTRY entry;
|
|
ULONG level;
|
|
ULONG index;
|
|
|
|
PAGED_CODE();
|
|
|
|
if ((deviceNode = DeviceObject->DeviceObjectExtension->DeviceNode) != NULL) {
|
|
//
|
|
// The device object is a PDO.
|
|
//
|
|
level = deviceNode->Level;
|
|
|
|
if (List->FirstLevel <= level && level <= List->MaxLevel) {
|
|
//
|
|
// The level is within the range of levels stored in this list.
|
|
//
|
|
if ((entry = List->Entries[ level - List->FirstLevel ]) != NULL) {
|
|
//
|
|
// There is an Entry for this level.
|
|
//
|
|
for (index = 0; index < entry->Count; index++) {
|
|
//
|
|
// For each Device in the entry, compare it to the given
|
|
// DeviceObject
|
|
if (((ULONG_PTR)entry->Devices[ index ] & ~RELATION_FLAGS) == (ULONG_PTR)DeviceObject) {
|
|
//
|
|
// It matches
|
|
//
|
|
return TRUE;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
//
|
|
// It wasn't a PDO
|
|
// or the level wasn't in the range of levels in this list
|
|
// or there are no DeviceObjects at the same level in this list
|
|
// or the DeviceObject isn't in the Entry for its level in this list
|
|
//
|
|
return FALSE;
|
|
}
|
|
|
|
NTSTATUS
|
|
IopMergeRelationLists(
|
|
IN OUT PRELATION_LIST TargetList,
|
|
IN PRELATION_LIST SourceList,
|
|
IN BOOLEAN Tagged
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
Merges two relation lists by copying all the relations from the source list
|
|
to the target list. Source list remains unchanged.
|
|
|
|
Arguments:
|
|
|
|
TargetList List to which the relations from Sourcelist are added.
|
|
|
|
SourceList List of relations to be added to TargetList.
|
|
|
|
Tagged TRUE if relations from SourceList should be tagged when added to
|
|
TargetList. If FALSE then relations added from SourceList are
|
|
untagged.
|
|
|
|
Return Value:
|
|
|
|
STATUS_SUCCESS
|
|
|
|
All the relations in SourceList were added to TargetList successfully.
|
|
|
|
STATUS_OBJECT_NAME_COLLISION
|
|
|
|
One of the relations in SourceList already exists in TargetList. This
|
|
is a fatal error and TargetList may already have some of the relations
|
|
from SourceList added. This could be dealt with more gracefully if
|
|
necessary but the current callers of IopMergeRelationLists avoid this
|
|
situation.
|
|
|
|
STATUS_INSUFFICIENT_RESOURCES
|
|
|
|
There isn't enough PagedPool available to allocate a new
|
|
RELATION_LIST_ENTRY.
|
|
|
|
STATUS_INVALID_PARAMETER
|
|
|
|
The level of one of the relations in SourceList is less than FirstLevel
|
|
or greater than the MaxLevel. This is a fatal error and TargetList may
|
|
already have some of the relations from SourceList added. The only way
|
|
this could happen is if the tree lock isn't held or if TargetList has
|
|
been compressed by IopCompressRelationList. Both situations would be
|
|
bugs in the caller.
|
|
|
|
STATUS_NO_SUCH_DEVICE
|
|
|
|
One of the relations in SourceList is not a PhysicalDeviceObject (PDO),
|
|
it doesn't have a DEVICE_NODE associated with it. This is a fatal error
|
|
and TargetList may already have some of the relations from SourceList
|
|
added. This should never happen since it was a PDO when it was added to
|
|
SourceList.
|
|
|
|
|
|
--*/
|
|
|
|
{
|
|
PRELATION_LIST_ENTRY entry;
|
|
LONG levelIndex;
|
|
LONG entryIndex;
|
|
LONG change;
|
|
LONG maxIndex;
|
|
NTSTATUS status;
|
|
NTSTATUS finalStatus;
|
|
|
|
PAGED_CODE();
|
|
|
|
finalStatus = STATUS_SUCCESS;
|
|
change = 1;
|
|
levelIndex = 0;
|
|
maxIndex = SourceList->MaxLevel - SourceList->FirstLevel;
|
|
for ( ; ; ) {
|
|
//
|
|
// Stop at maxIndex if moving forward or at 0 otherwise.
|
|
//
|
|
if ( (change == 1 && levelIndex > maxIndex) ||
|
|
(change == -1 && levelIndex < 0)) {
|
|
break;
|
|
}
|
|
entry = SourceList->Entries[levelIndex];
|
|
if (entry) {
|
|
entryIndex = (change == 1)? 0 : entry->Count - 1;
|
|
for ( ; ; ) {
|
|
if (change == 1) {
|
|
//
|
|
// Stop if we added all DOs in this entry.
|
|
//
|
|
if (entryIndex >= (LONG)entry->Count) {
|
|
break;
|
|
}
|
|
//
|
|
// For each Device in the Entry, add it to the target List.
|
|
//
|
|
status = IopAddRelationToList( TargetList,
|
|
(PDEVICE_OBJECT)((ULONG_PTR)entry->Devices[entryIndex] & ~RELATION_FLAGS),
|
|
FALSE,
|
|
Tagged);
|
|
if (!NT_SUCCESS(status)) {
|
|
//
|
|
// We need to undo the damage on failure by unwinding and removing DOs we added..
|
|
//
|
|
finalStatus = status;
|
|
change = -1;
|
|
}
|
|
} else {
|
|
//
|
|
// Stop at 0 if we are unwinding.
|
|
//
|
|
if (entryIndex < 0) {
|
|
break;
|
|
}
|
|
status = IopRemoveRelationFromList( TargetList,
|
|
(PDEVICE_OBJECT)((ULONG_PTR)entry->Devices[entryIndex] & ~RELATION_FLAGS));
|
|
ASSERT(NT_SUCCESS(status));
|
|
}
|
|
entryIndex += change;
|
|
}
|
|
}
|
|
levelIndex += change;
|
|
}
|
|
|
|
return finalStatus;
|
|
}
|
|
|
|
NTSTATUS
|
|
IopRemoveIndirectRelationsFromList(
|
|
IN PRELATION_LIST List
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
Removes all the relations without the DirectDescendant flag from a relation
|
|
list.
|
|
|
|
Arguments:
|
|
|
|
List List from which to remove the relations.
|
|
|
|
|
|
Return Value:
|
|
|
|
STATUS_SUCCESS
|
|
|
|
The relations were removed successfully.
|
|
|
|
--*/
|
|
|
|
{
|
|
PDEVICE_OBJECT deviceObject;
|
|
PRELATION_LIST_ENTRY entry;
|
|
ULONG level;
|
|
LONG index;
|
|
|
|
PAGED_CODE();
|
|
|
|
//
|
|
// For each Entry in the list.
|
|
//
|
|
for (level = List->FirstLevel; level <= List->MaxLevel; level++) {
|
|
|
|
//
|
|
// If the entry is allocated.
|
|
//
|
|
if ((entry = List->Entries[ level - List->FirstLevel ]) != NULL) {
|
|
|
|
//
|
|
// For each Device in the list.
|
|
//
|
|
for (index = entry->Count - 1; index >= 0; index--) {
|
|
if (!((ULONG_PTR)entry->Devices[ index ] & RELATION_FLAG_DESCENDANT)) {
|
|
|
|
deviceObject = (PDEVICE_OBJECT)((ULONG_PTR)entry->Devices[ index ] & ~RELATION_FLAGS);
|
|
|
|
ObDereferenceObject( deviceObject );
|
|
|
|
if ((ULONG_PTR)entry->Devices[ index ] & RELATION_FLAG_TAGGED) {
|
|
List->TagCount--;
|
|
}
|
|
|
|
if (index < ((LONG)entry->Count - 1)) {
|
|
|
|
RtlMoveMemory( &entry->Devices[ index ],
|
|
&entry->Devices[ index + 1 ],
|
|
(entry->Count - index - 1) * sizeof(PDEVICE_OBJECT));
|
|
}
|
|
|
|
if (--entry->Count == 0) {
|
|
List->Entries[ level - List->FirstLevel ] = NULL;
|
|
ExFreePool(entry);
|
|
}
|
|
|
|
List->Count--;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return STATUS_SUCCESS;
|
|
}
|
|
|
|
NTSTATUS
|
|
IopRemoveRelationFromList(
|
|
PRELATION_LIST List,
|
|
PDEVICE_OBJECT DeviceObject
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
Removes a relation from a relation list.
|
|
|
|
Arguments:
|
|
|
|
List List from which to remove the relation.
|
|
|
|
DeviceObject Relation to remove.
|
|
|
|
Return Value:
|
|
|
|
STATUS_SUCCESS
|
|
|
|
The relation was removed successfully.
|
|
|
|
STATUS_NO_SUCH_DEVICE
|
|
|
|
The relation doesn't exist in the list.
|
|
|
|
--*/
|
|
|
|
{
|
|
PDEVICE_NODE deviceNode;
|
|
PRELATION_LIST_ENTRY entry;
|
|
ULONG level;
|
|
LONG index;
|
|
|
|
PAGED_CODE();
|
|
|
|
if ((deviceNode = DeviceObject->DeviceObjectExtension->DeviceNode) != NULL) {
|
|
level = deviceNode->Level;
|
|
|
|
ASSERT(List->FirstLevel <= level && level <= List->MaxLevel);
|
|
|
|
if (List->FirstLevel <= level && level <= List->MaxLevel) {
|
|
if ((entry = List->Entries[ level - List->FirstLevel ]) != NULL) {
|
|
for (index = entry->Count - 1; index >= 0; index--) {
|
|
if (((ULONG_PTR)entry->Devices[ index ] & ~RELATION_FLAGS) == (ULONG_PTR)DeviceObject) {
|
|
|
|
ObDereferenceObject( DeviceObject );
|
|
|
|
if (((ULONG_PTR)entry->Devices[ index ] & RELATION_FLAG_TAGGED) != 0) {
|
|
List->TagCount--;
|
|
}
|
|
if (index < ((LONG)entry->Count - 1)) {
|
|
|
|
RtlMoveMemory( &entry->Devices[ index ],
|
|
&entry->Devices[ index + 1 ],
|
|
(entry->Count - index - 1) * sizeof(PDEVICE_OBJECT));
|
|
}
|
|
|
|
if (--entry->Count == 0) {
|
|
List->Entries[ level - List->FirstLevel ] = NULL;
|
|
ExFreePool(entry);
|
|
}
|
|
|
|
List->Count--;
|
|
|
|
return STATUS_SUCCESS;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return STATUS_NO_SUCH_DEVICE;
|
|
}
|
|
|
|
VOID
|
|
IopSetAllRelationsTags(
|
|
PRELATION_LIST List,
|
|
BOOLEAN Tagged
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
Tags or untags all the relations in a relations list.
|
|
|
|
Arguments:
|
|
|
|
List Relation list containing relations to be tagged or untagged.
|
|
|
|
Tagged TRUE if the relations should be tagged, FALSE if they are to be
|
|
untagged.
|
|
|
|
Return Value:
|
|
|
|
NONE
|
|
|
|
--*/
|
|
|
|
{
|
|
PRELATION_LIST_ENTRY entry;
|
|
ULONG level;
|
|
ULONG index;
|
|
|
|
PAGED_CODE();
|
|
|
|
//
|
|
// For each Entry in the list.
|
|
//
|
|
for (level = List->FirstLevel; level <= List->MaxLevel; level++) {
|
|
|
|
//
|
|
// If the entry is allocated.
|
|
//
|
|
if ((entry = List->Entries[ level - List->FirstLevel ]) != NULL) {
|
|
|
|
//
|
|
// For each Device in the list.
|
|
//
|
|
for (index = 0; index < entry->Count; index++) {
|
|
|
|
//
|
|
// Set or clear the tag based on the argument Tagged.
|
|
//
|
|
if (Tagged) {
|
|
entry->Devices[ index ] = (PDEVICE_OBJECT)((ULONG_PTR)entry->Devices[ index ] | RELATION_FLAG_TAGGED);
|
|
} else {
|
|
entry->Devices[ index ] = (PDEVICE_OBJECT)((ULONG_PTR)entry->Devices[ index ] & ~RELATION_FLAG_TAGGED);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
//
|
|
// If we are setting the tags then update the TagCount to the number of
|
|
// relations in the list. Otherwise reset it to zero.
|
|
//
|
|
List->TagCount = Tagged ? List->Count : 0;
|
|
}
|
|
|
|
NTSTATUS
|
|
IopSetRelationsTag(
|
|
IN PRELATION_LIST List,
|
|
IN PDEVICE_OBJECT DeviceObject,
|
|
IN BOOLEAN Tagged
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
Sets or clears a tag on a specified relation in a relations list. This
|
|
routine is also used by some callers to determine if a relation exists in
|
|
a list and if so to set the tag.
|
|
|
|
Arguments:
|
|
|
|
List List containing relation to be tagged or untagged.
|
|
|
|
DeviceObject Relation to be tagged or untagged.
|
|
|
|
Tagged TRUE if relation is to be tagged, FALSE if it is to be
|
|
untagged.
|
|
|
|
Return Value:
|
|
|
|
STATUS_SUCCESS
|
|
|
|
The relation was tagged successfully.
|
|
|
|
STATUS_NO_SUCH_DEVICE
|
|
|
|
The relation doesn't exist in the list.
|
|
|
|
--*/
|
|
|
|
{
|
|
PDEVICE_NODE deviceNode;
|
|
PRELATION_LIST_ENTRY entry;
|
|
ULONG level;
|
|
LONG index;
|
|
|
|
PAGED_CODE();
|
|
|
|
if ((deviceNode = DeviceObject->DeviceObjectExtension->DeviceNode) != NULL) {
|
|
//
|
|
// DeviceObject is a PhysicalDeviceObject (PDO), get its level.
|
|
//
|
|
level = deviceNode->Level;
|
|
|
|
if (List->FirstLevel <= level && level <= List->MaxLevel) {
|
|
//
|
|
// The level is within the range of levels in this List.
|
|
//
|
|
if ((entry = List->Entries[ level - List->FirstLevel ]) != NULL) {
|
|
//
|
|
// The Entry for this level is allocated. Search each device
|
|
// in the Entry looking for a match.
|
|
//
|
|
for (index = entry->Count - 1; index >= 0; index--) {
|
|
|
|
if (((ULONG_PTR)entry->Devices[ index ] & ~RELATION_FLAGS) == (ULONG_PTR)DeviceObject) {
|
|
|
|
//
|
|
// We found a match
|
|
//
|
|
if ((ULONG_PTR)entry->Devices[ index ] & RELATION_FLAG_TAGGED) {
|
|
//
|
|
// The relation is already tagged so to simplify the
|
|
// logic below decrement the TagCount. We'll
|
|
// increment it later if the caller still wants it
|
|
// to be tagged.
|
|
//
|
|
List->TagCount--;
|
|
}
|
|
|
|
if (Tagged) {
|
|
//
|
|
// Set the tag and increment the number of tagged
|
|
// relations.
|
|
//
|
|
entry->Devices[ index ] = (PDEVICE_OBJECT)((ULONG_PTR)entry->Devices[ index ] | RELATION_FLAG_TAGGED);
|
|
List->TagCount++;
|
|
} else {
|
|
//
|
|
// Clear the tag.
|
|
//
|
|
entry->Devices[ index ] = (PDEVICE_OBJECT)((ULONG_PTR)entry->Devices[ index ] & ~RELATION_FLAG_TAGGED);
|
|
}
|
|
|
|
return STATUS_SUCCESS;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
//
|
|
// It wasn't a PDO
|
|
// or the level wasn't in the range of levels in this list
|
|
// or there are no DeviceObjects at the same level in this list
|
|
// or the DeviceObject isn't in the Entry for its level in this list
|
|
//
|
|
return STATUS_NO_SUCH_DEVICE;
|
|
}
|
|
|