c# - Insert bytes into middle of a file (in windows filesystem) without reading entire file (using File Allocation Table)?

Question

I need a way to insert some file clusters into the middle of a file to insert some data.

Normally, I would just read the entire file and write it back out again with the changes, but the files are multiple gigabytes in size, and it takes 30 minutes just to read the file and write it back out again.

The cluster size doesn't bother me; I can essentially write out zeroes to the end of my inserted clusters, and it will still work in this file format.

How would I use the Windows File API (or some other mechanism) to modify the File Allocation Table of a file, inserting one or more unused clusters at a specified point in the middle of the file?

Answer 1

[EDIT:]

Blah - I'm going to say "this ain't doable, at least not via MFT modification, without a LOT of pain"; first off, the NTFS MFT structures themselves are not 100% "open", so I'm starting to delve into reverse-engineering-territory, which has legal repercussions I'm in no mood to deal with. Also, doing this in .NET is a hyper-tedious process of mapping and marshalling structures based on a lot of guesswork (and don't get me started on the fact that most of the MFT structures are compressed in strange ways). Short story, while I did learn an awful lot about how NTFS "works", I'm no closer to a solution to this problem.

[/EDIT]

Ugh...sooo much Marshalling nonsense....

This struck me as "interesting", therefore I was compelled to poke around at the problem...it's still an "answer-in-progress", but wanted to post up what all I had to assist others in coming up with something. :)

Also, I have a rough sense that this would be FAR easier on FAT32, but given I've only got NTFS to work with...

So - lots of pinvoking and marshalling, so let's start there and work backwards:

As one might guess, the standard .NET File/IO apis aren't going to help you much here - we need device-level access:

[DllImport("kernel32.dll", SetLastError = true, CharSet = CharSet.Auto)]
static extern SafeFileHandle CreateFile(
    string lpFileName,
    [MarshalAs(UnmanagedType.U4)] FileAccess dwDesiredAccess,
    [MarshalAs(UnmanagedType.U4)] FileShare dwShareMode,
    IntPtr lpSecurityAttributes,
    [MarshalAs(UnmanagedType.U4)] FileMode dwCreationDisposition,
    [MarshalAs(UnmanagedType.U4)] FileAttributes dwFlagsAndAttributes,
    IntPtr hTemplateFile);

[DllImport("kernel32.dll", CharSet = CharSet.Auto, SetLastError = true)]
public static extern bool ReadFile(
    SafeFileHandle hFile,      // handle to file
    byte[] pBuffer,        // data buffer, should be fixed
    int NumberOfBytesToRead,  // number of bytes to read
    IntPtr pNumberOfBytesRead,  // number of bytes read, provide NULL here
    ref NativeOverlapped lpOverlapped // should be fixed, if not null
);

[DllImport("Kernel32.dll", SetLastError = true, CharSet = CharSet.Auto)]
public static extern bool SetFilePointerEx(
    SafeFileHandle hFile,
    long liDistanceToMove,
    out long lpNewFilePointer,
    SeekOrigin dwMoveMethod);

We'll use these nasty win32 beasts thusly:

// To the metal, baby!
using (var fileHandle = NativeMethods.CreateFile(
    // Magic "give me the device" syntax
    @"\.c:",
    // MUST explicitly provide both of these, not ReadWrite
    FileAccess.Read | FileAccess.Write,
    // MUST explicitly provide both of these, not ReadWrite
    FileShare.Write | FileShare.Read,
    IntPtr.Zero,
    FileMode.Open,
    FileAttributes.Normal,
    IntPtr.Zero))
{
    if (fileHandle.IsInvalid)
    {
        // Doh!
        throw new Win32Exception();
    }
    else
    {
        // Boot sector ~ 512 bytes long
        byte[] buffer = new byte[512];
        NativeOverlapped overlapped = new NativeOverlapped();
        NativeMethods.ReadFile(fileHandle, buffer, buffer.Length, IntPtr.Zero, ref overlapped);

        // Pin it so we can transmogrify it into a FAT structure
        var handle = GCHandle.Alloc(buffer, GCHandleType.Pinned);
        try
        {
            // note, I've got an NTFS drive, change yours to suit
            var bootSector = (BootSector_NTFS)Marshal.PtrToStructure(
                 handle.AddrOfPinnedObject(), 
                 typeof(BootSector_NTFS));

Whoa, whoa whoa - what the heck is a BootSector_NTFS? It's a byte-mapped struct that fits as close as I can reckon to what the NTFS structure looks like (FAT32 included as well):

[StructLayout(LayoutKind.Sequential, CharSet=CharSet.Ansi, Pack=0)]
public struct JumpBoot
{
    [MarshalAs(UnmanagedType.ByValArray, ArraySubType=UnmanagedType.U1, SizeConst=3)]
    public byte[] BS_jmpBoot;
    [MarshalAs(UnmanagedType.ByValTStr, SizeConst=8)]
    public string BS_OEMName;
}

[StructLayout(LayoutKind.Explicit, CharSet = CharSet.Ansi, Pack = 0, Size = 90)]
public struct BootSector_NTFS
{
    [FieldOffset(0)]
    public JumpBoot JumpBoot;
    [FieldOffset(0xb)]
    public short BytesPerSector;
    [FieldOffset(0xd)]
    public byte SectorsPerCluster;
    [FieldOffset(0xe)]
    public short ReservedSectorCount;
    [FieldOffset(0x10)]
    [MarshalAs(UnmanagedType.ByValArray, SizeConst = 5)]
    public byte[] Reserved0_MUSTBEZEROs;
    [FieldOffset(0x15)]
    public byte BPB_Media;
    [FieldOffset(0x16)]
    public short Reserved1_MUSTBEZERO;
    [FieldOffset(0x18)]
    public short SectorsPerTrack;
    [FieldOffset(0x1A)]
    public short HeadCount;
    [FieldOffset(0x1c)]
    public int HiddenSectorCount;
    [FieldOffset(0x20)]
    public int LargeSectors;
    [FieldOffset(0x24)]
    public int Reserved6;
    [FieldOffset(0x28)]
    public long TotalSectors;
    [FieldOffset(0x30)]
    public long MftClusterNumber;
    [FieldOffset(0x38)]
    public long MftMirrorClusterNumber;
    [FieldOffset(0x40)]
    public byte ClustersPerMftRecord;
    [FieldOffset(0x41)]
    public byte Reserved7;
    [FieldOffset(0x42)]
    public short Reserved8;
    [FieldOffset(0x44)]
    public byte ClustersPerIndexBuffer;
    [FieldOffset(0x45)]
    public byte Reserved9;
    [FieldOffset(0x46)]
    public short ReservedA;
    [FieldOffset(0x48)]
    [MarshalAs(UnmanagedType.ByValArray, SizeConst = 8)]
    public byte[] SerialNumber;
    [FieldOffset(0x50)]
    public int Checksum;
    [FieldOffset(0x54)]
    [MarshalAs(UnmanagedType.ByValArray, SizeConst = 0x1AA)]
    public byte[] BootupCode;
    [FieldOffset(0x1FE)]
    public ushort EndOfSectorMarker;

    public long GetMftAbsoluteIndex(int recordIndex = 0)
    {
        return (BytesPerSector * SectorsPerCluster * MftClusterNumber) + (GetMftEntrySize() * recordIndex);
    }
    public long GetMftEntrySize()
    {
        return (BytesPerSector * SectorsPerCluster * ClustersPerMftRecord);
    }
}


// Note: dont have fat32, so can't verify all these...they *should* work, tho
// refs:
//    http://www.pjrc.com/tech/8051/ide/fat32.html
//    http://msdn.microsoft.com/en-US/windows/hardware/gg463084
[StructLayout(LayoutKind.Explicit, CharSet=CharSet.Auto, Pack=0, Size=90)]
public struct BootSector_FAT32
{
    [FieldOffset(0)]
    public JumpBoot JumpBoot;    
    [FieldOffset(11)]
    public short BPB_BytsPerSec;
    [FieldOffset(13)]
    public byte BPB_SecPerClus;
    [FieldOffset(14)]
    public short BPB_RsvdSecCnt;
    [FieldOffset(16)]
    public byte BPB_NumFATs;
    [FieldOffset(17)]
    public short BPB_RootEntCnt;
    [FieldOffset(19)]
    public short BPB_TotSec16;
    [FieldOffset(21)]
    public byte BPB_Media;
    [FieldOffset(22)]
    public short BPB_FATSz16;
    [FieldOffset(24)]
    public short BPB_SecPerTrk;
    [FieldOffset(26)]
    public short BPB_NumHeads;
    [FieldOffset(28)]
    public int BPB_HiddSec;
    [FieldOffset(32)]
    public int BPB_TotSec32;
    [FieldOffset(36)]
    public FAT32 FAT;
}

[StructLayout(LayoutKind.Sequential)]
public struct FAT32
{
    public int BPB_FATSz32;
    public short BPB_ExtFlags;
    public short BPB_FSVer;
    public int BPB_RootClus;
    public short BPB_FSInfo;
    public short BPB_BkBootSec;
    [MarshalAs(UnmanagedType.ByValArray, SizeConst=12)]
    public byte[] BPB_Reserved;
    public byte BS_DrvNum;
    public byte BS_Reserved1;
    public byte BS_BootSig;
    public int BS_VolID;
    [MarshalAs(UnmanagedType.ByValTStr, SizeConst=11)] 
    public string BS_VolLab;
    [MarshalAs(UnmanagedType.ByValTStr, SizeConst=8)] 
    public string BS_FilSysType;
}

So now we can map a whole mess'o'bytes back to this structure:

// Pin it so we can transmogrify it into a FAT structure
var handle = GCHandle.Alloc(buffer, GCHandleType.Pinned);
    try
    {            
        // note, I've got an NTFS drive, change yours to suit
        var bootSector = (BootSector_NTFS)Marshal.PtrToStructure(
              handle.AddrOfPinnedObject(), 
              typeof(BootSector_NTFS));
        Console.WriteLine(
            "I think that the Master File Table is at absolute position:{0}, sector:{1}", 
            bootSector.GetMftAbsoluteIndex(),
            bootSector.GetMftAbsoluteIndex() / bootSector.BytesPerSector);

Which at this point outputs:

I think that the Master File Table is at 
absolute position:3221225472, sector:6291456

Let's confirm that quick using the OEM support tool nfi.exe:

C:oolsOEMTools
fi>nfi c:
NTFS File Sector Information Utility.
Copyright (C) Microsoft Corporation 1999. All rights reserved.


File 0
Master File Table ($Mft)
    $STANDARD_INFORMATION (resident)
    $FILE_NAME (resident)
    $DATA (nonresident)
        logical sectors 6291456-6487039 (0x600000-0x62fbff)
        logical sectors 366267960-369153591 (0x15d4ce38-0x1600d637)
    $BITMAP (nonresident)
        logical sectors 6291448-6291455 (0x5ffff8-0x5fffff)
        logical sectors 7273984-7274367 (0x6efe00-0x6eff7f)

Cool, looks like we're on the right track...onward!

            // If you've got LinqPad, uncomment this to look at boot sector
            bootSector.Dump();

    Console.WriteLine("Jumping to Master File Table...");
    long lpNewFilePointer;
    if (!NativeMethods.SetFilePointerEx(
            fileHandle, 
            bootSector.GetMftAbsoluteIndex(), 
            out lpNewFilePointer, 
            SeekOrigin.Begin))
    {
        throw new Win32Exception();
    }
    Console.WriteLine("Position now: {0}", lpNewFilePointer);

    // Read in one MFT entry
    byte[] mft_buffer = new byte[bootSector.GetMftEntrySize()];
    Console.WriteLine("Reading $MFT entry...calculated size: 0x{0}",
       bootSector.GetMftEntrySize().ToString("X"));

    var seekIndex = bootSector.GetMftAbsoluteIndex();
    overlapped.OffsetHigh = (int)(seekIndex >> 32);
    overlapped.OffsetLow = (int)seekIndex;
    NativeMethods.ReadFile(
          fileHandle, 
          mft_buffer, 
          mft_buffer.Length, 
          IntPtr.Zero, 
          ref overlapped);
    // Pin it for transmogrification
    var mft_handle = GCHandle.Alloc(mft_buffer, GCHandleType.Pinned);
    try
    {
        var mftRecords = (MFTSystemRecords)Marshal.PtrToStructure(
              mft_handle.AddrOfPinnedObject(), 
              typeof(MFTSystemRecords));
        mftRecords.Dump();
    }
    finally
    {
        // make sure we clean up
        mft_handle.Free();
    }
}
finally
{
    // make sure we clean up
    handle.Free();
}

Argh, more native structures to discuss - so the MFT is arranged such that the first 16 or so entries are "fixed":

[StructLayout(LayoutKind.Sequential)]
public struct MFTSystemRecords
{
    public MFTRecord Mft;
    public MFTRecord MftMirror;
    public MFTRecord LogFile;
    public MFTRecord Volume;
    public MFTRecord AttributeDefs;
    public MFTRecord RootFile;
    public MFTRecord ClusterBitmap;
    public MFTRecord BootSector;
    public MFTRecord BadClusterFile;
    public MFTRecord SecurityFile;
    public MFTRecord UpcaseTable;
    public MFTRecord ExtensionFile;
    [MarshalAs(UnmanagedType.ByValArray, SizeConst = 16)]
    public MFTRecord[] MftReserved;
    public MFTRecord MftFileExt;
}

Where MFTRecord is:

[StructLayout(Layo