Category Archives: NTFS

VHD versus NTFS alignment

This topic is guaranteed to bore most people.  Or, maybe I am wrong.  Are you the kind of person that loves to defrag your disk?  Are you always looking for new ways of speeding up your machine?  Are knobs and buttons something you love to tweak?  How about that registry cleaner?

No, I am not saying those things are bad.  Some people have the patience for this while others do not.  Usually the people that fiddle with the settings are eventually rewarded.  At the very least they can proclaim that they understand what the settings are really doing.

Thanks to a reader (thanks John!) I was made aware of the offset problem within VHDs.  Well, let me rephrase that.  I knew about it but I did not know its official name or that people had solved it.

John pointed me to this blog post about the offset problem.  There are already tools out there from NetApp to solve the issue but basically you need to be a NetApp customer in order to get access (at least for the tools that actually fix your images).  In truth, the problem affects most virtualisation users.

So, this is the part where the problem is dissected and understood.  Virtual disks still follow rules left over from physical disks.  Specifically, they have a “geometry” setting that indicates things like sectors per track.  Here is an example from my tool named vhddump of one the test VHDs laying around.

Geometry             3F10BA9E
Cylinders            9EBA
Heads                10
Sectors/Track        3F

This information is a field inside the VHD header.  The geometry value splits into the next three values based on interpreting the bytes.  Since VHDs are big endian (big bytes first instead the typical little endian on Windows).  vhddump is reporting the field backwards since it had not been important to preserve the byte order.

Anyways, you can see that our virtual disk has 3F sectors per track.  This translates to 63 sectors in decimal.  The geometry reported (also known as CHS) affects the alignment of partitions.  The rule with older versions of Windows is that the boot partition starts after the first track.  This is the output for the same VHD with vhddump:

Index(0) 80 01 01 00 07 FE FF FF 3F 00 00 00 B5 98 70 02
Index(0) BootFlag(80) Type(07) SectorStart(0000003F) SectorLength(027098B5)
Index(0) CHSStart(010100) CHSEnd(FEFFFF)
Start CHS  Head(01) Sector(01) Cylinder(0000)
End   CHS  Head(FE) Sector(3F) Cylinder(03FF)

Volume Count         1
Volume Index         0
FirstVolumeSector    3F

The master boot record starts at the first sector of the virtual disk.  This dump is from a Windows XP image.  The first sector of the first volume/partition is at 0x3f.

Why is this a problem?

Well the most obvious problem is that the sector 0x3f does not align with VHD blocks or even NTFS clusters.  Since it is an ‘odd’ sector, it is guaranteed never to align with anything inside the VHD.

This problem was first seen when exploring the clusters inside the VHD.  Instead of being neatly aligned with the VHD blocks, it was possible to have a cluster that spanned two blocks.  Even the sector bitmap showing the written clusters did not align on byte boundaries for a cluster.  Not only did it make it harder to correspond information, it was more wasteful to do more work for something that should have been aligned in the first place.

This kind of offset problem would show as a performance problem over time.  It is always more efficient to have alignment.

If people really understood this problem, they would probably insist that the partitions were aligned.  A simple example is a cluster that spans two blocks.  Not only is it a read/write hit to access two blocks, but it also potentially wastes space with the second block if there is nothing else there.

If clusters are aligned with VHD blocks, it is much easier to correlate the file data.  It makes sense that the disk should be aligned not with pretend physical settings but rather the VHD format itself.  Even though it is counter-intuitive, it might make sense to have the first partition start at a 2MB boundary.  Some space would be wasted before and after a given partition but the partition would be guaranteed to be isolated from the MBR area and the other partitions.

John had asked for a tool to fix this.  Unfortunately I do not have time right now to solve it.  There are other areas which are currently more important.  However, it would be fun to write such a tool.

Cluster Map

Defragmentation on Windows XP

 

One aspect of volume management is knowing which clusters are free and which ones are used.  This is typically something managed solely by the operating system but it is sometimes possible to get a glimpse of how things align.  Microsoft published a few interfaces a few years ago that were once considered undocumented.  The set of API targets being able to defrag a disk.  The cluster map is gathered using FSCTL_GET_VOLUME_BITMAP.  A cluster is the most basic unit of the file system.  It is defined by what is specified in the boot sector of the volume.  Windows apparently always uses a sector size of 512 bytes with the option of different cluster sizes (multiples of the sectors).  The two fields in the boot sector are “sectors per cluster” and “sector size”.  The boot sector has this information at offset 0x0B for “sector size” (WORD) and offset 0xD for “sectors per cluster” (BYTE).

The cluster size typically corresponds to the size of the disk.  The larger the disk, the larger the cluster size.  My main 250GB drive has a cluster size of 4K.  Originally the drives were small enough to have the sector size and cluster size match (512 bytes).

Back to FSCTL_GET_VOLUME_BITMAP.  When the information is successfully returned from the IOCTL, it reveals the cluster pattern for the volume.  The structure returned is VOLUME_BITMAP_BUFFER which is effectively a bitmap of used/free clusters.  Each byte in this “Buffer” corresponds 8 clusters.  The lowest bit represents the first cluster of that byte.  Just today I figured that if you had 64 bytes of bitmap data, it would correspond to 2MB of data with 4K clusters.  

The actual output of the bytes shows an idea of where the used and free space is concentrated.  As expected, most of the early parts of the disk are used while the last parts are usually free.  There is also hints of fragmentation since there is gaps between sections of data which probably used to be files.

It is actually possible to gather free/used cluster counts from the bitmap by throwing the data through a counter that changes the byte patterns to actual count pairs.  I wrote a program that scanned the whole bitmap using each nibble to match against pre-programmed arrays.  So, put in 0xF and get back 4 used 0 free.  Put in 0×6 and get 2 used and 2 free.  You get the idea.  Originally I had thought of doing it against the byte but was not looking forward to entering the 256 combinations.

I keep on thinking of defrag programs from the past (like Norton) that show the cluster map (from a high level view) and moving files around.  Now it seems fairly simplistic given the amount of clusters involved.  It also seems a bit risky given the temporary nature of the free/used bitmap.

The point there is that the amount of free/used clusters is always changing based on system activity.  A snapshot using the IOCTL is just a picture in time and does not guarantee that things are still the same.  Even Microsoft recommend to assume that you might not get the free clusters you want for a defrag operation so you better be prepared to try again.

The actual information lives inside NTFS in a metadata file called $Bitmap.  It is MFT record number 6 (reserved and for all time the same).  $Bitmap cannot be directly read from any Windows program since it is only intended for the file system.  Obviously Microsoft does not want anyone to change this file.  It would play major havoc on Windows most likely.  

The cluster map in $Bitmap is in theory the basis of what is returned from the IOCTL.  However, based on not being able to do both at exactly the same instant means that they could vary.  The exception to this would be if you could freeze Windows somehow.

Speaking of freezing Windows, the only way to do this successfully is to access the information when nothing is changing.  The easiest way is to access the volume when it is not booted from.  As long as no running program is changing the non-boot drive, it should be possible to get an accurate snapshot that will stay good over time.

Coming from a VHD angle, you could mount the VHD and then use the IOCTL.  Or, you could spend a lot of time understanding the NTFS format along with the VHD format to go get the $Bitmap file yourself.  Difficult, but entirely possible.

Having come to the end of this post, it seems that this topic might be a bit tangential to what most of you might be interested in.  Let’s assume that it is really meant for the tinkerers out there that like to know where the disk space is really being used.  Please expect a few more words about this area in the coming weeks.