The Logical Structure, Organization, and Management of Hard Disk Drives
…ÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕª
∫ ∫
∫ The Logical Structure, Organization, ∫
∫ and Management of Hard Disk Drives ∫
∫ ∫
∫ by ∫
∫ Steve Gibson ∫
∫ GIBSON RESEARCH CORPORATION ∫
∫ ∫
∫ Portions of this text originally appeared in Steve's ∫
∫ InfoWorld Magazine TechTalk Column. ∫
∫ ∫
»ÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕÕº
As our operating systems and application software have continued to grow in size, their memory requirements have increased steadily. A vital memory in our system is hard disk storage.
Bound within the hard disk's structure lie the answers to questions like: What is a low level format? What does FDISK do? What is a hard disk partition and why does DOS limit us to 32 megabytes in a partition? What does it mean to have "lost cluster chains" or "cross-linked files?" What does it mean to have our disks "defragmented?" Let's explore MS-DOS and PC-DOS hard disk organization to answer these questions and others.
The first stage in preparing any hard disk for operation is known as low level formatting. Low level formatting takes any hard disk from its virgin "fresh from the factory" state and prepares it for operation with a particular hard disk controller and computer system.
Low level formatting divides each circular track into equal size SECTORS by placing SECTOR ID HEADERS at uniform positions around each track. The start of a sector ID is marked with a special magnetic pattern which cannot be generated by normal recorded data. This ADDRESS MARK allows the beginning of each sector to be uniquely discriminated from all recorded data.
The sector ID information, which immediately follows the address mark contains each sector's Cylinder, Head, and Sector number which is completely unique for each sector on the disk. When the hard disk controller is late reading or writing to these disk sectors, it compares the sector's pre-recorded cylinder number to make sure that the heads haven't "mis-stepped" and that they're flying over the proper cylinder. It then compares the head number to verify that unreliable cabling is not causing an improper head to be selected and waits for the proper sector to start by comparing the pre-recorded sector number as it passes by with the sector number for which it is searching.
Since many hard disk surfaces are not flawless, low level formatting programs include a means for entering the hard disk drive's defect list. The defect list specifies tracks (by cylinder and head number) that the manufacturer's sensitive drive certification equipment found to stray from the normal which indicates some form of physical flaw that might prevent data from being reliably written and read. The list of such defects is typically printed and attached to the outside of the drive.
When these tracks are entered into the low level formatter, the defective tracks receive a special code in their sector ID headers which indicates that the track has been flagged as bad and cannot be used for any data storage. Later, as we shall see, high level formatting moves this defective track information into the system's File Allocation Table (FAT) to prevent the operating system from allocating files within these defective regions.
When the low level format has been established, we have a completely empty drive, devoid of stored information, which can accept and retrieve data with the specification of any valid cylinder, head, and sector number.
There's an important issue about the low level formatting of a hard disk which is frequently overlooked, but which can be quite important to appreciate. Since the hard disk controller works in intimate concert with its hard disk drive to transfer the data within its numbered sectors to and from the computer's memory, the exact details of the address mark, sector ID header, and rotational sector timing can be completely arbitrary for any controller and drive. Since these details are initially established when the drive receives its low level formatting, they are forever hence agreed upon by both the hard disk drive and the controller. But more importantly, there's absolutely no reason to assume that the relatively arbitrary low level formatting specifics used by any particular hard disk controller would be compatible with any other model of hard disk controller.
In practice this means that differing makes or models of hard disk controllers are completely unable to read, write, or interpret the formatted information created by any other make or model of controller. Consequently, whenever it is necessary or desirable to exchange hard disk controllers, a complete backup of the hard disk's data, while attached to the initial controller, MUST BE followed by creating a new low level format with the new controller on the drive before any of the backed-up information can be restored to the drive with the new controller.
So we've given our drives a low level format, since we see that it is this process which first establishes "communication" between a hard disk and its controller by creating 512-byte "sectors" where none existed before. Now lets take up the next phase of hard disk structuring: The hard disk PARTITION.
The notion of hard disk (or "fixed disk" as IBM calls them) partitions was created to allow a hard disk based computer system to contain and "boot up" several completely different operating systems. Partitioning divides a single physical hard disk into multiple LOGICAL partitions.
A birthday cake is divided into multiple pieces by slicing it radially whereas a hard disk's divisions are circular. For example, a drive's first partition might extend from cylinder zero through 299 with the second partition beginning on cylinder 300 and extending through 599. This circular partitioning is far more efficient since it minimizes the disk head travel when moving within a single partition.
The partitions on a drive, even if there's only one, are managed by a special sector called the PARTITION TABLE which is located at the very beginning of every hard disk. It defines the starting and ending locations for each of the disk's partitions and specifies which of the partitions is to gain control of the system during system boot up. When the hard disk drive is booted a tiny program at the beginning of the partition table locates the partition which is flagged as being the "bootable partition" in the table and executes the program located in the first sector, the "boot sector," of that partition. This boot sector loads the balance of the partition's operating system then transfers control to it.
Each partition on a hard disk is blind to the existence of any other. By universal agreement, the operation of software inside a partition is completely contained within the bounds of the partition. Adherence to this agreement prevents multiple operating systems from colliding and allows strange environments to cohabitate on a single hard disk.
The sectors within a partition are numbered sequentially starting at zero and extending to the end of the partition. In kind with DOS's original belief that 640K of RAM would be more than we'd EVER need, there was a time in the not-so-distant past when a ten megabyte hard disk was an unheard of luxury and was considered huge. How could any single person ever fill up 10 megabytes? No way.
Consequently DOS was designed to access sectors within its hard disk partition with a single sixteen-bit quantity. One "word" was set aside for the specification of partition sectors. As many of you know, a single sixteen-bit binary word can represent values from 0 through 65,535. So this limited a partition's total sector count to 65,536. Since hard disk sectors are 512 bytes long, a partition could contain 33,554,432 bytes. When you remember that binary megabytes are really 1,048,576 bytes each, that's exactly 32 megabytes.
This is the origin of DOS's infamous 32 megabyte barrier. Today of course we have affordable drives with capacities well exceeding DOS's 32 megabyte limit. The industry has invented three solutions to this partition size dilemma.
The first solution invented to the partition size problem utilizes DOS's inherent extendibility with external device drivers. Programs such as OnTrack's DISK MANAGER, Storage Dimensions' SPEEDSTOR, and Golden Bow's VFEATURE DELUXE utilize a clever trick to circumvent the 32 megabyte DOS limit: They trick DOS into believing that sectors are larger than 512 bytes! By interposing themselves between DOS and the hard disk, these partitioning device drivers lead DOS to believe that individual sectors are much larger than they really are. Then when DOS asks for one "logical" 4k-byte sector they hand DOS eight 512-byte physical sectors. This transforms the 65,536 sector count limit into a single partition containing more than 268 megabytes!
The second solution was introduced by IBM's PC-DOS 3.3 operating system with its ability to allow DOS to have simultaneous access to multiple logical partitions on a single drive. With DOS 3.3, the standard FDISK command can establish any number of 32- megabyte or smaller partitions on a drive. While this doesn't create a single unified huge partition, it also doesn't require any external resident device drivers.
The final solution has recently been introduced by Compaq Computer with their introduction of DOS 3.31. Being big enough to get away with sacrificing some software compatiblity, Compaq has redefined the way DOS numbers its partition sectors thereby removing the limitation at its source.
So now our hard disks have a low level format, with "addressability" to the disk's individual physical sectors established. We have also defined and established partitions on our drive, which gives DOS a sub-range of the hard disk within which to build its filing system. Now let's examine the structure of MS-/PC-DOS filing systems. The following discussion also applies to DOS diskettes which aren't partitioned but otherwise have an identical structure.
Let's begin by looking at the problem that DOS's filing system solves: Its task is to allow us, through the vehicle of DOS application programs, to create named collections of bytes of data, called files, and to help with their management by providing directories of these named files.
The directory entry for any DOS file contains the file's name and extension, the date and time when the file was last written and closed, an assortment of Yes/No "attributes" which indicate whether the file has been modified since last backup, whether it can be written to, whether it's even visible in the directory, etc. The directory entry for the file also contains the address of the start of the file.
We already know that hard disks are divided into numbered sectors 512 bytes in length. Since most of the files DOS manages are much larger than a single sector, disk space is allocated in "clumps" of sectors called clusters. Various versions of DOS utilize clusters of 4, 8 or 16 sectors each, or 2048, 4096, or 8192 bytes in length.
When a hard disk is completely empty, its clusters of sectors are all available for storing file data. As files are created and deleted on the hard disk, a bookkeeping system is needed which keeps track of which clusters are in use by which existing files, and which clusters are still available for allocation to new or growing files. This is the vital role played by the File Allocation Table. The "FAT," as it's frequently called, is the table DOS uses to manage the allocation of space on the hard disk.
As we know, the hard disk is arranged as a long stream of sectors. After being clumped together into clusters, it can be viewed as a long stream of clusters. Now picture a table consisting of a long stream of entries, with one entry in the table for each cluster on the disk. The first FAT table entry corresponds to the first hard disk cluster, and the last FAT entry corresponds to the last hard disk cluster.
Now imagine that DOS needs to create a new text or spreadsheet file for us. It must first find a free cluster on the hard disk, so it searches through the File Allocation Table looking for an empty FAT table entry, which corresponds to an empty hard disk cluster. When DOS finds the empty table entry it memorizes its number, then places a special "end of chain" marker in the FAT entry to show that this cluster has been allocated and is no longer free for use. DOS then goes out to the sectors which comprise this cluster and writes the file's new data there.
This is all great until the file grows longer than a single cluster of sectors. DOS now needs to allocate a second cluster for this file. So it once again searches through the File Allocation Table for a free cluster. When found, it again places the special "end of chain" marker in this cluster and memorizes its number.
Now things begin to get interesting... and just a little bit tricky. Since files might be really long, consisting of thousands of individually allocated clusters, there's no way for DOS to memorize all of the clusters used by each file. So DOS uses each File Allocation Table entry to store the number of the file's next cluster!
Following along with our example, after finding and allocating the second cluster for the growing file, DOS goes back to the first cluster's FAT entry where it had placed that first "end of chain" marker and replaces it with the number of the file's second cluster. If a third cluster were then needed, its FAT entry would be marked "not available" by placing the special "end of chain" marker in it, then this third cluster number would be placed into the second cluster's FAT entry. Get it?
This creates a "chain" of clusters with each cluster entry pointing to the next one, and the last one containing a special "end of chain" entry which signals that the end of the file's allocation chain has been reached.
Finally, when the file is "closed," an entry is created in a DOS directory which names the file and contains the number of the file's first cluster. Then, using that first cluster's FAT entry, the entire allocation "chain" can be "traversed" to find the clusters which contain the file's data.
So now let's do a bit of review....
The allocation of file space within a DOS partition is recorded and maintained within DOS's File Allocation Tables (FATs). The FATs make up a map of the utilization of space on any floppy or hard disk with one entry in the FAT for each allocatable cluster of sectors. Each entry in the FAT can indicate one of four possible conditions for the clusters of sectors it represents: It can be unused and available for allocation, unused and marked as bad to prevent its use, in use and pointing to the next cluster of the file, or in use as the last cluster of a file.
If each entry in the FAT points to the next, who points to the first entry? This is the role of the file's directory entry. It contains the name of the file, the file's exact length, the time and date of the file's last modification, file attribute flags, and the identity of file's first cluster. In a sense, a file's directory entry forms the head of the file's allocation chain with each link thereafter pointing to the next link in the chain.
This system, while quite workable and efficient, does have its dangers. These dangers center around the fact that the FAT contains the ONLY record of disk space utilization and a stubborn failure to correctly read a single sector of the FAT could render hundreds of files unrecoverable. This danger explains the popularity of several utility programs which create a back-up copy of the File Allocation Table and Root Directory with each system boot-up. They provide some hope of recovery from the cataclysmic loss of the FAT's data.
The original designers of DOS were aware of the importance of the FAT and do provide a duplicate copy immediately following the first, but its physical proximity to the original renders it little better than none, and DOS has long been notorious for failing to intelligently utilize this extra copy of FAT information even in the event of a primary FAT failure. (DOS 3.3 seems to be much smarter in this regard.)
Important as FAT reliability is, it's not generally the prime source of DOS file corruption, since even with perfect data retrieval, it's still possible to scramble DOS's files like crazy. The primary cause of DOS file system troubles are user error, program bugs, and "glitches." The advent of TSR "rule breaking" resident multitasking-style software has further complicated the scene.
When a new file is created or "opened," information about it is maintained inside DOS. The file's name, status, and first cluster are all held in internal tables. Then, as the file grows, free clusters are "checked out" of the File Allocation Table and allocated to the file's chain of clusters.
Now here's the crucial fact which causes so much trouble: No matter how big the newly created file becomes, a directory entry for the file is ONLY created when the file is finally and properly CLOSED. Until then the file exists only as a chain of allocated clusters filled with the file's data. If anything occurs to prevent the error-free closing of this file we have a real problem because the file's data is occupying a chain of "checked out" disk clusters, but there is no anchoring directory entry to point to the first cluster in the chain!
A chain of clusters without an anchoring directory entry is called a "lost chain." It exists, it contains data, but there's no record of the file's name, exact size, or purpose.
Lost cluster chains are frequently created when programs abort abnormally, when TSR's crash the system suddenly, when the computer user forgets to write a TSR's files out to disk before shutting the system down, or when a task in a multi-tasking system is not terminated. (It's easy to forget that a file was left open in a suspended background task.) Additionally, any damage to DOS's root directory or subdirectories can "liberate" chains of lost clusters.
DOS provides the CHKDSK (pronounced Check Disk) command to help its users keep an eye on just these sorts of problems. CHKDSK provides a comprehensive verification of DOS's filing system integrity and provides a means for straightening things out. When the CHKDSK command is given, the parentage of all cluster chains is checked, allocation chains are "followed" to be sure they don't cross over other chains (creating cross-linked files), and several other system integrity checks are performed.
In the case of lost chains, CHKDSK will offer to convert these into files by anchoring them to the root directory. Then any suitable text editor can be used to open these new files for the sake of identifying them and moving them back to where they belong.
Unfortunately the structure of DOS filing systems lacks the fundamental redundancy required to provide simple and error-free recovery from many forms of damage. Even the tools and techniques available from third party suppliers can't surmount these problems. The best bet is to understand DOS's weak spots, make certain that all opened files are closed successfully, perform a weekly CHKDSK command to collect accumulating file fragment "debris" and back up your hard disks regularly.
"Disk Optimizers" which promise to increase the throughput and performance of old and well used hard disk drives number among the most popular of the general use hard disk utilities.
We've seen how DOS's file allocation system operates. Files are composed of clusters which in turn are composed of sectors. And while the group of sectors which comprise a cluster are by definition contiguous, the cluster linking scheme which DOS employs allows a file's clusters to be scattered across the disk's surface. Since the file's directory entry specifies the file's first cluster, and each succeeding cluster entry in the file allocation table specifies the next one, the file's contents could be literally anywhere on the disk. The term "file fragmentation" refers to the condition where a file's clusters are not consecutively numbered. Let's first examine how a disk's files might become fragmented.
When a file is deleted from a disk, its directory entry is flagged as unused and each cluster which the file occupied is flagged in the system's FAT as being free for use. If the surrounding clusters are still in use by other files, this
creates a "hole" of free space in the disk.
Now suppose that a new file is copied from a floppy disk onto the hard disk. As DOS reads the new file's data from the floppy, it must allocate space for this file on the hard disk. So each time another cluster of sectors is needed, DOS searches through the file allocation table to find the next available cluster. In our example, DOS would discover the clusters which had been freed by the first file we deleted and allocate them for use by the new file. Then, when all of the clusters in the free space hole had been used, DOS would be forced to continue its search deeper into the drive. When space was found further in, the file's contents would be partially stored near the beginning of the disk and partially nearer to the end. The file would then consist of at least two fragments.
During the normal course of daily computer usage, many files are being constantly created, copied, extended, deleted, and replaced. When a wordprocessor creates an automatic backup file, the original file is typically renamed to identify it as a backup file and a new file is created. Every new file creation is an opportunity for fragmentation. The files which are being modified most often are most subject to extensive fragmentation since any search by DOS for a free file cluster is almost guaranteed to produce a new discontinuity. With continued use, it's typical for much of the disk's file data to become haphazardly scattered across the surface of the disk drive.
But since DOS's cluster allocation scheme was specifically designed to manage such scattering, what's the problem? Any time the drive's head moves, two things occur: Time is consumed, and the drive experiences some mechanical wear and tear. If a file's data is scattered across the surface of the disk, the drive's head is forced to move a large distance many times to read a single file. If the file is a database whose records are being accessed at random, this excessive head motion can degrade the overall system performance tremendously and induce many other wear-related disk drive problems.
The extra time wasted in cluster fragment chasing is directly proportional to the drive's average head access time. The prior generation of 65 to 80 millisecond stepping motor drives lose far more performance to fragmentation than the latest sub-28 millisecond drives.
Disk optimizers like SoftLogic Solutions' DISK OPTIMIZER, Norton's SPEEDDISK, Central Point's COMPRESS, and Golden Bow's VOPT operate by physically rearranging the allocation of files on the disk. They relocate file cluster fragments while simultaneously updating the system's File Allocation Tables to reflect the new cluster locations. When finished, every file on the disk consists of a single contiguous run of consecutively numbered clusters. Once the disk drive's head has been positioned to the beginning of the file, the entire file can be read or randomly accessed with an absolute minimum of head motion. Besides improving the system's overall performance, file defragmentation minimizes the mechanical wear and tear placed upon the drive's hardware. If some disaster should befall your system's Root Directory or File Allocation Table, contiguous files are also much easier to find and recover than files with severe fragmentation.
Since file fragmentation is a continually occurring fact of living with DOS, periodic defragmentation, like hard disk backup, should become part of every serious DOS user's regimen.
- The End -
Copyright (c) 1989 by Steven M. Gibson
Laguna Hills, CA 92653
**ALL RIGHTS RESERVED **
