How defragmentation tools work with NT 4.0
Welcome to the first installment of my regular column that explores the "guts" of Windows NT. I
plan to cover topics ranging from high-level issues such as the architecture of NT to low-level issues such as details
of algorithms NT employs. If you have a particular NT internals topic you'd like to see this column demystify, please
drop me an email.
This month's topic is NT's disk defragmentation support. Disk defragmentation products are hot sellers, and many
people want to know how these products work. After defining disk defragmentation, I'll provide a synopsis of the history
of NT defragmentation products, and describe the support Microsoft added to NT 4.0's file systems specifically for use
by defragmentation tools.
Disk Defragmentation
NT's file systems allocate the disk sectors of logical drives (e.g., C, D) in units known as clusters. When
you create a file on a drive, the file system assigns clusters of storage for the file's data. As time passes and you
expand and shrink the file and create and delete other files, both the free clusters on the drive and the clusters
assigned to the files become fragmented (i.e., non-contiguous).
For example, suppose you create a Word document and the file system assigns six clusters to hold the document's
contents. Later, you add a few pages to the document, and the file grows by six more clusters. If another file or
directory uses the clusters that immediately follow the document's original clusters, the file system assigns the
document's new file clusters from somewhere else on the drive--your file now consists of at least two fragments. Figure 1A, shows a simplified diagram of a fragmented file; Figure 1B depicts a defragmented file.
Fragmentation can negatively affect performance. When the disk head reads contiguous data, the level of throughput
is high. When the system reads a fragmented disk file, the disk head must move from fragment to fragment. On a disk with
many fragmented files, moving the disk head across fragments can consume significant time.
Disk defragmenters are products that aim to optimize system performance by reorganizing a drive's clusters
to make file clusters contiguous, and in some cases, to make the free clusters contiguous. Defragmenters use heuristic
algorithms that implement a fragment-shifting strategy to defragment the drive's files as quickly as possible.
The History of Disk Defragmenting on NT
In April 1995, Executive Software released the first defragmenter for NT: Diskeeper for NT 3.5 with Service Pack 1
(SP1) or Service Pack 2 (SP2). The company announced an update for NT 3.51 in July of the same year.
Because Microsoft did not design NT 3.5x's native file systems, FAT and NTFS, with disk defragmenting in mind, FAT
and NTFS have no support for moving clusters around a disk. Executive Software purchased an NT source license from
Microsoft to modify NT and the FAT and NTFS drivers to support disk defragmenting. As a result, Executive Software
shipped its custom version of NT with Diskeeper for NT 3.51.
But as Diskeeper users upgraded NT 3.51 with SPs, they experienced problems. Installing an SP overwrote some of
Diskeeper's files and left others alone, causing incompatibility problems for upgraded systems--and technical support
problems for Microsoft and Executive Software.
As development of NT 4.0 began in 1995, Microsoft invited a Diskeeper developer to Redmond, Washington, to
participate in the design and implementation of NT 4.0's defragmentation support. Basing Diskeeper on NT's built-in
support let Executive Software avoid shipping custom versions of NT and meant Microsoft's technical support didn't have
to troubleshoot non-standard versions of NT. One month before NT 4.0's public release, Executive Software offered a
trial version of Diskeeper 2.0--the version for NT 4.0--on its Web site. (For Jonathan J. Chau's review of Diskeeper
2.0, see Lab Reports, "Diskeeper 2.0," April 1997.) Symantec has since entered the NT disk defragmenting
market with its Norton Utilities Speed Disk, which also uses the NT 4.0 defragmentation support.
NT 4.0 Support for Disk Defragmenting
The defragmentation support introduced in NT 4.0's file systems consists of five commands: GetVolumeBitmap,
GetRetrievalPointers, and MoveFile (common to both FAT and NTFS), and GetVolumeData and ReadMFTRecord (specific to only
NTFS). Microsoft doesn't document these commands or officially acknowledge that they exist.
GetVolumeBitmap. The GetVolumeBitmap command obtains a map of the free and allocated clusters of a
logical drive. NT file systems maintain an array of bits that track the drive's clusters. An "on" bit signals
an allocated cluster; an "off" bit signals a free cluster.