From e611b132f9b8abe35b362e5870b74bce94a1e58e Mon Sep 17 00:00:00 2001 From: Adam Date: Sat, 16 May 2020 20:51:50 -0700 Subject: initial commit --- private/ntos/cntfs/views/heap.c | 506 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 506 insertions(+) create mode 100644 private/ntos/cntfs/views/heap.c (limited to 'private/ntos/cntfs/views/heap.c') diff --git a/private/ntos/cntfs/views/heap.c b/private/ntos/cntfs/views/heap.c new file mode 100644 index 000000000..170650e5f --- /dev/null +++ b/private/ntos/cntfs/views/heap.c @@ -0,0 +1,506 @@ +/*++ + +Copyright (c) 1989-1997 Microsoft Corporation + +Module Name: + + heap.c + +Abstract: + + This module contains the code to manipulate the value heap. + + +--*/ + +#include // needs propset.h and ntfsprop.h + +#define Dbg DEBUG_TRACE_PROP_FSCTL + +// +// Global illegal value +// + +PROPID IllegalId = PID_ILLEGAL; + + +ULONG +FindStringInHeap( + IN PPROPERTY_CONTEXT Context, + IN PCOUNTED_STRING Name + ) + +/*++ + +Routine Description: + + This routines looks up a property by name in the property set heap. + +Arguments: + + Context - Context of heap to scan + + Name - UNICODE string property to search for + +Return Value: + + Offset to property value. If name is not found, 0 is returned + +--*/ + +{ + PPROPERTY_HEAP_ENTRY HeapEntry = FIRST_HEAP_ENTRY( Context->HeapHeader ); + UNICODE_STRING First, Second; + + First.Buffer = COUNTED_STRING_TEXT( Name ); + First.Length = Second.Length = COUNTED_STRING_LENGTH( Name ); + + // + // While there are more heap records + // + + while (!IS_LAST_HEAP_ENTRY( Context->HeapHeader, HeapEntry )) { + + // + // if a name doesn't have the same length, skip it + // + + if (HeapEntry->PropertyNameLength != Name->Length) { + + NOTHING; + + // + // Same length, test for case-insignificant match + // + + } else { + Second.Buffer = &HeapEntry->PropertyName[0]; + + if (RtlCompareUnicodeString( &First, &Second, TRUE ) == 0) { + + // + // return pointer to name + // + + DebugTrace( 0, Dbg, ("FindStringInHeap %.*ws %x\n", + COUNTED_STRING_LENGTH( Name ) / sizeof( WCHAR ), + COUNTED_STRING_TEXT( Name ), + HeapOffset( Context, HeapEntry )) ); + + return HeapOffset( Context, HeapEntry ); + } + } + + // + // advance to next heap record + // + + HeapEntry = NEXT_HEAP_ENTRY( HeapEntry ); + } + + // + // return not-found + // + + DebugTrace( 0, Dbg, ("FindStringInHeap %.*ws not found\n", + COUNTED_STRING_LENGTH( Name ) / sizeof( WCHAR ), + COUNTED_STRING_TEXT( Name )) ); + + return 0; +} + + +// +// Local support routine +// + +PPROPERTY_HEAP_ENTRY GrowHeap ( + IN PPROPERTY_CONTEXT Context, + IN ULONG Length + ) + +/*++ + +Routine Description: + + This routines grows the heap to accommodate a value of a particular length. + There is no guarantee about any "extra space" present. + +Arguments: + + Context - context of property set + + Length - minimum growth needed + + +Return Value: + + Pointer to new free item at end of heap + +--*/ + +{ + PPROPERTY_HEAP_ENTRY HeapEntry; + + // + // Determine true growth. For now, we allocate 2X the size of the property + // up to a max of 1K. After that, we just allocate the requested size + // + + if (Length <= 512) { + Length = max( 2 * Length, Length + PROPERTY_HEAP_ENTRY_SIZE( 10, 8 )); + } + + // + // Resize stream to account for new growth + // + + + DebugTrace( 0, Dbg, ("Growing heap to length %x\n", Length + NtOfsQueryLength( Context->Attribute ))); + + NtOfsSetLength ( + Context->IrpContext, + Context->Attribute, + Length + NtOfsQueryLength( Context->Attribute )); + + // + // Set up new header for new growth, Id and Length. + // + + HeapEntry = (PPROPERTY_HEAP_ENTRY) Add2Ptr( Context->HeapHeader, Context->HeapHeader->PropertyHeapLength ); + + LogFileFullFailCheck( Context->IrpContext ); + NtOfsPutData( Context->IrpContext, + Context->Attribute, + ContextOffset( Context, &HeapEntry->PropertyId ), + sizeof( PROPID ), + &IllegalId ); + + LogFileFullFailCheck( Context->IrpContext ); + NtOfsPutData( Context->IrpContext, + Context->Attribute, + ContextOffset( Context, &HeapEntry->PropertyValueLength ), + sizeof( Length ), + &Length ); + + // + // Resize heap + // + + Length+= Context->HeapHeader->PropertyHeapLength; + + LogFileFullFailCheck( Context->IrpContext ); + NtOfsPutData( Context->IrpContext, + Context->Attribute, + ContextOffset( Context, &Context->HeapHeader->PropertyHeapLength ), + sizeof( Length ), + &Length ); + + return HeapEntry; +} + +VOID +SetValueInHeap( + IN PPROPERTY_CONTEXT Context, + IN PPROPERTY_HEAP_ENTRY HeapEntry, + IN PROPID Id, + IN USHORT NameLength, + IN PWCHAR Name, + IN ULONG ValueLength, + IN SERIALIZEDPROPERTYVALUE *Value + ) + +/*++ + +Routine Description: + + This routines sets a specific value in the heap. + +Arguments: + + Context - context of property set + + HeapEntry - pointer to header that will be modified + + Id - PROPID to set + + NameLength - length of name in BYTES + + Name - pointer to name, may be NULL + + ValueLength - count of bytes in value + + Value - Serialized property value + +Return Value: + + None. + +--*/ + +{ + PROPASSERT( Id != PID_ILLEGAL ); + + // + // Set PropertyId + // + + LogFileFullFailCheck( Context->IrpContext ); + NtOfsPutData( Context->IrpContext, + Context->Attribute, + ContextOffset( Context, &HeapEntry->PropertyId ), + sizeof( PROPID ), + &Id ); + + // + // Set name length + // + + LogFileFullFailCheck( Context->IrpContext ); + NtOfsPutData( Context->IrpContext, + Context->Attribute, + ContextOffset( Context, &HeapEntry->PropertyNameLength ), + sizeof( USHORT ), + &NameLength ); + + // + // Set name if present + // + + if (Name != NULL) { + LogFileFullFailCheck( Context->IrpContext ); + NtOfsPutData( Context->IrpContext, + Context->Attribute, + ContextOffset( Context, &HeapEntry->PropertyName[0] ), + NameLength, + Name ); + } + + // + // Set property value + // + + LogFileFullFailCheck( Context->IrpContext ); + NtOfsPutData( Context->IrpContext, + Context->Attribute, + ContextOffset( Context, PROPERTY_HEAP_ENTRY_VALUE( HeapEntry )), + ValueLength, + Value ); + +} + + +ULONG +AddValueToHeap( + IN PPROPERTY_CONTEXT Context, + IN PROPID Id, + IN ULONG Length, + IN USHORT NameLength, + IN PWCHAR Name OPTIONAL, + IN ULONG ValueLength, + IN SERIALIZEDPROPERTYVALUE *Value + ) + +/*++ + +Routine Description: + + This routines adds a value to the heap. We walk the heap looking for a free + header (PID_ILLEGAL) whose size is sufficient to contain the name and value. + If one is not found, the heap and attribute are grown. + +Arguments: + + Context - context of property set + + Id - PROPID to add + + Length - length of entire propery value (including name) in bytes + + NameLength - length of name in BYTES + + Name - pointer to name, may be NULL + + ValueLength - count of bytes in value + + Value - Serialized property value + +Return Value: + + Offset to property value stored in heap + +--*/ + +{ + PPROPERTY_HEAP_ENTRY HeapEntry = FIRST_HEAP_ENTRY( Context->HeapHeader ); + + PROPASSERT( Id != PID_ILLEGAL ); + + DebugTrace( +1, Dbg, ("AddValueToHeap(%x '%.*ws' %x len %x)\n", + Id, NameLength / sizeof( WCHAR ), Name, Value, ValueLength) ); + DebugTrace( 0, Dbg, ("property value length is %x\n", Length) ); + + // + // Walk through the heap until we reach the end or until we have + // a free block that contains enough room for this property. We also + // will break out if the block we find has enough room for the property + // and can be split to allow for a property that has 5 chars of name + // and 8 bytes of serialized value. + // + + while (TRUE) { + // + // If this is not a valid header, break + // + + if (IS_LAST_HEAP_ENTRY( Context->HeapHeader, HeapEntry )) { + break; + } + + // + // if this is a free header + // + + if (HeapEntry->PropertyId == PID_ILLEGAL) { + + // + // If the value length matches exactly, break + // + + if (HeapEntry->PropertyValueLength == Length) { + break; + } + + // + // If the value length allows for an extra value, break + // + + if (HeapEntry->PropertyValueLength >= + Length + PROPERTY_HEAP_ENTRY_SIZE( 10, 8 )) { + break; + } + } + + // + // Go to next block + // + + HeapEntry = NEXT_HEAP_ENTRY( HeapEntry ); + } + + // + // If we are at the end of the heap, then we must grow the heap. In this case + // we grow the heap by a large block and set thing up as if we had found + // a free block of the right size. We then fall into the normal reuse-free- + // block code. + // + + if (IS_LAST_HEAP_ENTRY( Context->HeapHeader, HeapEntry )) { + HeapEntry = GrowHeap( Context, Length ); + } + + // + // HeapEntry points to a free heap block that is large enough to contain + // the new length, possibly splitting. First, split if necessary. + // + + if (HeapEntry->PropertyValueLength != Length) { + PPROPERTY_HEAP_ENTRY SecondHeader; + ULONG SecondLength = HeapEntry->PropertyValueLength - Length; + + PROPASSERT( Length + PROPERTY_HEAP_ENTRY_SIZE( 10, 8 ) <= HeapEntry->PropertyValueLength); + + // + // Get address of second block header + // + + SecondHeader = (PPROPERTY_HEAP_ENTRY) Add2Ptr( HeapEntry, Length ); + + // + // set up second block header: length and propid + // + + LogFileFullFailCheck( Context->IrpContext ); + NtOfsPutData( Context->IrpContext, + Context->Attribute, + ContextOffset( Context, &SecondHeader->PropertyId ), + sizeof( PROPID ), + &IllegalId ); + + LogFileFullFailCheck( Context->IrpContext ); + NtOfsPutData( Context->IrpContext, + Context->Attribute, + ContextOffset( Context, &SecondHeader->PropertyValueLength ), + sizeof( SecondLength ), + &SecondLength ); + + + // + // set up value header length to reflect split + // + + LogFileFullFailCheck( Context->IrpContext ); + NtOfsPutData( Context->IrpContext, + Context->Attribute, + ContextOffset( Context, &HeapEntry->PropertyValueLength ), + sizeof( Length ), + &Length ); + + } + + // + // HeapEntry points at a free block with exactly the right amount of space + // for this name/value + // + + PROPASSERT( Length == HeapEntry->PropertyValueLength ); + + SetValueInHeap( Context, HeapEntry, Id, NameLength, Name, ValueLength, Value ); + + DebugTrace( -1, Dbg, ("value offset is at %x\n", + HeapOffset( Context, HeapEntry )) ); + + return HeapOffset( Context, HeapEntry ); +} + + +VOID +DeleteFromHeap( + IN PPROPERTY_CONTEXT Context, + IN PPROPERTY_HEAP_ENTRY HeapEntry + ) + +/*++ + +Routine Description: + + This routines deletes a value from the heap. The present implementation + marks the header as being for PID_ILLEGAL. + +Arguments: + + Context - Property set context + + HeapEntry - entry to be deleted + +Return Value: + + Nothing + +--*/ + +{ + DebugTrace( 0, Dbg, ("DeleteFromHeap at %x\n", HeapEntry) ); + + // + // Delete by setting the value to be PID_ILLEGAL + // + + LogFileFullFailCheck( Context->IrpContext ); + NtOfsPutData( Context->IrpContext, + Context->Attribute, + ContextOffset( Context, &HeapEntry->PropertyId), + sizeof( IllegalId ), + &IllegalId ); +} + -- cgit v1.2.3