+/**
+* @name AllocateIndexNode
+* @implemented
+*
+* Allocates a new index record in an index allocation.
+*
+* @param DeviceExt
+* Pointer to the target DEVICE_EXTENSION describing the volume the node will be created on.
+*
+* @param FileRecord
+* Pointer to a copy of the file record containing the index.
+*
+* @param IndexBufferSize
+* Size of an index record for this index, in bytes. Commonly defined as 4096.
+*
+* @param IndexAllocationCtx
+* Pointer to an NTFS_ATTR_CONTEXT describing the index allocation attribute the node will be assigned to.
+*
+* @param IndexAllocationOffset
+* Offset of the index allocation attribute relative to the file record.
+*
+* @param NewVCN
+* Pointer to a ULONGLONG which will receive the VCN of the newly-assigned index record
+*
+* @returns
+* STATUS_SUCCESS in case of success.
+* STATUS_NOT_IMPLEMENTED if there's no $I30 bitmap attribute in the file record.
+*
+* @remarks
+* AllocateIndexNode() doesn't write any data to the index record it creates. Called by UpdateIndexNode().
+* Don't call PrintAllVCNs() or NtfsDumpFileRecord() after calling AllocateIndexNode() before UpdateIndexNode() finishes.
+*/
+NTSTATUS
+AllocateIndexNode(PDEVICE_EXTENSION DeviceExt,
+ PFILE_RECORD_HEADER FileRecord,
+ ULONG IndexBufferSize,
+ PNTFS_ATTR_CONTEXT IndexAllocationCtx,
+ ULONG IndexAllocationOffset,
+ PULONGLONG NewVCN)
+{
+ NTSTATUS Status;
+ PNTFS_ATTR_CONTEXT BitmapCtx;
+ ULONGLONG IndexAllocationLength, BitmapLength;
+ ULONG BitmapOffset;
+ ULONGLONG NextNodeNumber;
+ PCHAR *BitmapMem;
+ ULONG *BitmapPtr;
+ RTL_BITMAP Bitmap;
+ ULONG BytesWritten;
+ ULONG BytesNeeded;
+ LARGE_INTEGER DataSize;
+
+ DPRINT1("AllocateIndexNode(%p, %p, %lu, %p, %lu, %p) called.\n", DeviceExt,
+ FileRecord,
+ IndexBufferSize,
+ IndexAllocationCtx,
+ IndexAllocationOffset,
+ NewVCN);
+
+ // Get the length of the attribute allocation
+ IndexAllocationLength = AttributeDataLength(IndexAllocationCtx->pRecord);
+
+ // Find the bitmap attribute for the index
+ Status = FindAttribute(DeviceExt,
+ FileRecord,
+ AttributeBitmap,
+ L"$I30",
+ 4,
+ &BitmapCtx,
+ &BitmapOffset);
+ if (!NT_SUCCESS(Status))
+ {
+ DPRINT1("FIXME: Need to add bitmap attribute!\n");
+ return STATUS_NOT_IMPLEMENTED;
+ }
+
+ // Get the length of the bitmap attribute
+ BitmapLength = AttributeDataLength(BitmapCtx->pRecord);
+
+ NextNodeNumber = IndexAllocationLength / DeviceExt->NtfsInfo.BytesPerIndexRecord;
+
+ // TODO: Find unused allocation in bitmap and use that space first
+
+ // Add another bit to bitmap
+
+ // See how many bytes we need to store the amount of bits we'll have
+ BytesNeeded = NextNodeNumber / 8;
+ if (NextNodeNumber % 8 != 0)
+ BytesNeeded++;
+
+ // Windows seems to allocate the bitmap in 8-byte chunks to keep any bytes from being wasted on padding
+ ALIGN_UP(BytesNeeded, ATTR_RECORD_ALIGNMENT);
+
+ // Do we need to enlarge the bitmap?
+ if (BytesNeeded > BitmapLength)
+ {
+ // TODO: handle synchronization issues that could occur from changing the directory's file record
+ // Change bitmap size
+ DataSize.QuadPart = BytesNeeded;
+ Status = SetResidentAttributeDataLength(DeviceExt,
+ BitmapCtx,
+ BitmapOffset,
+ FileRecord,
+ &DataSize);
+ if (!NT_SUCCESS(Status))
+ {
+ DPRINT1("ERROR: Failed to set length of bitmap attribute!\n");
+ ReleaseAttributeContext(BitmapCtx);
+ return Status;
+ }
+ }
+
+ // Enlarge Index Allocation attribute
+ DataSize.QuadPart = IndexAllocationLength + IndexBufferSize;
+ Status = SetNonResidentAttributeDataLength(DeviceExt,
+ IndexAllocationCtx,
+ IndexAllocationOffset,
+ FileRecord,
+ &DataSize);
+ if (!NT_SUCCESS(Status))
+ {
+ DPRINT1("ERROR: Failed to set length of index allocation!\n");
+ ReleaseAttributeContext(BitmapCtx);
+ return Status;
+ }
+
+ // Update file record on disk
+ Status = UpdateFileRecord(DeviceExt, IndexAllocationCtx->FileMFTIndex, FileRecord);
+ if (!NT_SUCCESS(Status))
+ {
+ DPRINT1("ERROR: Failed to update file record!\n");
+ ReleaseAttributeContext(BitmapCtx);
+ return Status;
+ }
+
+ // Allocate memory for the bitmap. RtlInitializeBitmap() wants a pointer that's ULONG-aligned
+ BitmapMem = ExAllocatePoolWithTag(NonPagedPool, BytesNeeded + sizeof(ULONG) - 1, TAG_NTFS);
+ BitmapPtr = (PULONG)ALIGN_UP_BY((ULONG_PTR)BitmapMem, sizeof(ULONG));
+
+ RtlZeroMemory(BitmapPtr, BytesNeeded);
+
+ // Read the existing bitmap data
+ Status = ReadAttribute(DeviceExt, BitmapCtx, 0, (PCHAR)BitmapPtr, BitmapLength);
+
+ // Initialize bitmap
+ RtlInitializeBitMap(&Bitmap, BitmapPtr, BytesNeeded);
+
+ // Set the bit for the new index record
+ RtlSetBits(&Bitmap, NextNodeNumber, 1);
+
+ // Write the new bitmap attribute
+ Status = WriteAttribute(DeviceExt,
+ BitmapCtx,
+ 0,
+ (const PUCHAR)BitmapPtr,
+ BytesNeeded,
+ &BytesWritten,
+ FileRecord);
+ if (!NT_SUCCESS(Status))
+ {
+ DPRINT1("ERROR: Unable to write to $I30 bitmap attribute!\n");
+ }
+
+ // Calculate VCN of new node number
+ *NewVCN = NextNodeNumber * (IndexBufferSize / DeviceExt->NtfsInfo.BytesPerCluster);
+
+ ExFreePoolWithTag(BitmapMem, TAG_NTFS);
+ ReleaseAttributeContext(BitmapCtx);
+
+ return Status;
+}
+
+/**
+* @name CreateDummyKey
+* @implemented
+*
+* Creates the final B_TREE_KEY for a B_TREE_FILENAME_NODE. Also creates the associated index entry.
+*
+* @param HasChildNode
+* BOOLEAN to indicate if this key will have a LesserChild.
+*
+* @return
+* The newly-created key.
+*/
+PB_TREE_KEY
+CreateDummyKey(BOOLEAN HasChildNode)
+{
+ PINDEX_ENTRY_ATTRIBUTE NewIndexEntry;
+ PB_TREE_KEY NewDummyKey;
+
+ // Calculate max size of a dummy key
+ ULONG EntrySize = ALIGN_UP_BY(FIELD_OFFSET(INDEX_ENTRY_ATTRIBUTE, FileName), 8);
+ EntrySize += sizeof(ULONGLONG); // for VCN
+
+ // Create the index entry for the key
+ NewIndexEntry = ExAllocatePoolWithTag(NonPagedPool, EntrySize, TAG_NTFS);
+ if (!NewIndexEntry)
+ {
+ DPRINT1("Couldn't allocate memory for dummy key index entry!\n");
+ return NULL;
+ }
+
+ RtlZeroMemory(NewIndexEntry, EntrySize);
+
+ if (HasChildNode)
+ {
+ NewIndexEntry->Flags = NTFS_INDEX_ENTRY_NODE | NTFS_INDEX_ENTRY_END;
+ }
+ else
+ {
+ NewIndexEntry->Flags = NTFS_INDEX_ENTRY_END;
+ EntrySize -= sizeof(ULONGLONG); // no VCN
+ }
+
+ NewIndexEntry->Length = EntrySize;
+
+ // Create the key
+ NewDummyKey = ExAllocatePoolWithTag(NonPagedPool, sizeof(B_TREE_KEY), TAG_NTFS);
+ if (!NewDummyKey)
+ {
+ DPRINT1("Unable to allocate dummy key!\n");
+ ExFreePoolWithTag(NewIndexEntry, TAG_NTFS);
+ return NULL;
+ }
+ RtlZeroMemory(NewDummyKey, sizeof(B_TREE_KEY));
+
+ NewDummyKey->IndexEntry = NewIndexEntry;
+
+ return NewDummyKey;
+}
+