Monthly Archives: November 2008

Cluster Map

Posted on November 26, 2008 | 1 Comment

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.

→ 1 Comment

Posted in NTFS, VHD, Windows Vista, Windows XP

Tagged , ,

Blue Ocean Strategy

Posted on November 19, 2008 | 2 Comments

Blue Ocean Strategy is a book written by W. Chan Kim and Renée Mauborgne.  Unlike some of the previous business books written about, this one was selected by me.  There were a few different conversations about it at work which led me to believe that it was worth learning about.  Having read it over the last few weeks, I know feel fairly well informed about the strategy and what makes it different from existing methods.

The most basic idea is that instead of competing in an existing market (“ocean”), why not create a new market to work with.  By redefining the market space, the company can be the first to provide products and services.  However, it is not just about creating something different.  It is also about creating value innovation for the customers.  This means that the product or service needs to fit a strategy canvas that keeps both the company and the customer happy.  True value comes from stopping certain activities while growing new ones.  The different strategies can be plotted against an X-Y axis and compared to other companies.  The overall difference is that the company with the blue ocean strategy is going to look a lot lower in certain strategies but much higher than others.

The tricky part is figuring out what needs to be readjusted. The book spends much time explaining how to target the strategy canvas.  As an example,  Southwest Airlines created a blue ocean by dropping traditional airline features like meals, lounges, seating choices, and hubs.  It instead focused on friendly service, speed, and frequent point to point departure.  This shift in focus reduced their cost base while increasing their demand based on what customers wanted most.  Instead of raising prices, Southwest instead found the most appropriate price for the customer while still guaranteeing a profit.  The assigning of price and costs is very important for the success of the business.  Setting the price too high hurts demand while also encouraging competition.  Setting the price too low with little or no profits guarantees that the business will not survive.

I was most skeptical about the idea related to keeping the ocean blue.  Nothing would be stopping a newcomer from entering the market later on.  However, this is where the blue ocean strategy shines.  Not only are you the first to enter that market, but if you set the price correctly from the start, you will discourage any other companies from doing the same.  Existing companies will not want to change their strategy canvases to match.  It is very hard to stop doing things that everyone expects is going to continue even if it does not make sense.

There is no easy way to do justice to all the things said.  Perhaps there will be more posts about Blue Ocean Strategy in the future like what was done for “Good To Great”.

→ 2 Comments

Posted in Book Analysis

Tagged

Blocks Versus Files

Posted on November 12, 2008 | Leave a comment

This topic presents an interesting problem.  A disk is made up of sectors which are arranged as clusters by the file system.  Both NTFS and FAT use a cluster model to clump together sectors into bigger chunks.  The cluster model has been around since the original DOS and still runs strong today.  The boot sector of the volume contains how many sectors of a certain size belong to one cluster.  On my Vista system the clusters are 4K (8 sectors of 512 bytes each).  This can vary for USB Flash Drives and smaller hard drives.  My flash drive reports a cluster size of 32K (64 sectors/cluster).  All of this is fine but then the question becomes why should I care?

The answer becomes more relevant when virtualization comes into the picture.  For a VM, the disk is virtual and is actually a file within another file system (most of the time).  Microsoft and Citrix use the VHD format for the VM files.  The VHD specification is public knowledge since Microsoft has documented as of a couple of years ago.  Given that there is a VHD file, everything needed by the operating system is there.  However, it becomes very difficult to manage this information from the outside.  Yes, there are ways to mount VHD drives within a native operating system, but this process is not necessarily easy to automate.  Well, at least not for everyone.

Then a new factor enters the equation.  Since the outside tools cannot see inside the VHD to understand what Windows is actually using, it becomes very difficult to do any kind of analysis or consolidation.  Microsoft does have a solution for compressing a VHD with Virtual PC 2007.  Unfortunately, there are many steps and it involves executing code both inside and outside the VM.  Wouldn’t it be nice if this could be managed completely from the outside?  Wouldn’t it be nice if every cluster (block) was paired with a file?

This sounds difficult and overall the problem is very tough.  The benefits however would be huge.  Basically any file operation performed on the inside could potentially be performed on the outside.  This would include things like defragmentation and shrinking the VHD to get rid of the blank chunks.  It could also include peering into the VHD to see what is there and even the hope of doing updates.

Other possible ventures would include merging virtual disks and even creating virtual disks out of multiple virtual disks.  It is possible to focus on the files instead of the blocks, it would much more possible to have base and delta disks which would both be allowed to change but yet form a cohesive volume to the user.  It is good to dream.

The sources of information look promising.  Microsoft has published APIs related to defragmenting disks which can locate a file on disk.  The API also allow for cluster relocation.  Beyond this, there are projects for Linux to understand NTFS.  Those teams have done much to discover the structure of NTFS and have included this knowledge in their programs and their documentation.  With these kind of guidelines, with patience, NTFS starts to open up and new things become possible.

There is a bit of vagueness about going on here.  It is still too early to talk about in detail.  However, it does seem that specific tasks are within reach which did not look so possible before.  Combining the knowledge of VHD with NTFS to form new tools looks incredibly attractive.

→ Leave a comment

Posted in Citrix Ideas, Citrix Tools, Microsoft, Research, Tools, VHD

Tagged , ,