Free space bitmap
Encyclopedia
Free space bitmaps are one method used to track allocated sector
s by some file system
s. While the most simplistic design is highly inefficient, advanced or hybrid implementations of free space bitmaps are used by some modern file systems.
s. In this example, a zero would indicate a free sector, while a one indicates a sector in use. Each sector would be of fixed size. For explanatory purposes, we will use a 4 GiB
hard drive with 4096 byte
sectors, and assume the bitmap itself is stored elsewhere. The example disk would require 1,048,576 bits, one for each sector, or 128 KiB
. Increasing the size of the drive will proportionately increase the size of the bitmap, while multiplying the sector size will produce a proportionate reduction.
When the operating system
(OS) needs to write a file, it will scan the bitmap until it finds enough free locations to fit the file. If a 12 KiB file were stored on the example drive, three zero bits would be found, changed to ones, and the data would be written across the three sectors represented by those bits. If the file were subsequently truncated down to 8 KiB, the final sector's bit would be set back to zero, indicating that it is again available for use.
This approach drastically reduces the cost of finding free space, but it doesn't help with the process of freeing space. If the combined size of the summary array and bitmap is greater than can readily be stored in memory and a large number of files with scattered sectors are freed, an enormous amount of disk access is necessary to find all the sectors, decrement the summary counter and flip the bits back to zero. This greatly reduces the benefits of the bitmap, as it is no longer performing its function of summarizing the free space rapidly without reading from the disk.
Disk sector
In computer disk storage, a sector is a subdivision of a track on a magnetic disk or optical disc. Each sector stores a fixed amount of user data. Traditional formatting of these storage media provides space for 512 bytes or 2048 bytes of user-accessible data per sector...
s by some file system
File system
A file system is a means to organize data expected to be retained after a program terminates by providing procedures to store, retrieve and update data, as well as manage the available space on the device which contain it. A file system organizes data in an efficient manner and is tuned to the...
s. While the most simplistic design is highly inefficient, advanced or hybrid implementations of free space bitmaps are used by some modern file systems.
Example
The simplest form of free space bitmap is a bit array, i.e. a block of bitBit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
s. In this example, a zero would indicate a free sector, while a one indicates a sector in use. Each sector would be of fixed size. For explanatory purposes, we will use a 4 GiB
Gibibyte
The gibibyte is a standards-based binary multiple of the byte, a unit of digital information storage. The gibibyte unit symbol is GiB....
hard drive with 4096 byte
Byte
The byte is a unit of digital information in computing and telecommunications that most commonly consists of eight bits. Historically, a byte was the number of bits used to encode a single character of text in a computer and for this reason it is the basic addressable element in many computer...
sectors, and assume the bitmap itself is stored elsewhere. The example disk would require 1,048,576 bits, one for each sector, or 128 KiB
Kibibyte
The kibibyte is a multiple of the unit byte for quantities of digital information. The binary prefix kibi means 1024; therefore, 1 kibibyte is . The unit symbol for the kibibyte is KiB. The unit was established by the International Electrotechnical Commission in 1999 and has been accepted for use...
. Increasing the size of the drive will proportionately increase the size of the bitmap, while multiplying the sector size will produce a proportionate reduction.
When the operating system
Operating system
An operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system...
(OS) needs to write a file, it will scan the bitmap until it finds enough free locations to fit the file. If a 12 KiB file were stored on the example drive, three zero bits would be found, changed to ones, and the data would be written across the three sectors represented by those bits. If the file were subsequently truncated down to 8 KiB, the final sector's bit would be set back to zero, indicating that it is again available for use.
Advantages
- Simple: Each bit directly corresponds to a sector
- Fast random access allocation check: Checking if a sector is free is as simple as checking the corresponding bit
- Fast deletion: Data need not be overwritten on delete, flipping the corresponding bit is sufficient
- Fixed cost: Both an advantage and disadvantage. Other techniques to store free space information have a variable amount of overhead depending on the number and size of the free space extents. Bitmaps can never do as well as other techniques in their respective ideal circumstances, but don't suffer pathological cases either. Since the bitmap never grows, shrinks or moves, fewer lookups are required to find the desired information
- Low storage overhead as a percentage of the drive size: Even with relatively small sector sizes, the storage space required for the bitmap is small. A 2 TiBTebibyteThe tebibyte is a standards-based binary multiple of the byte, a unit of digital information storage. The tebibyte unit symbol is TiB....
drive could be fully represented with a mere 64 MiBMebibyteThe mebibyte is a multiple of the unit byte for digital information. The binary prefix mebi means 220, therefore 1 mebibyte is . The unit symbol for the mebibyte is MiB. The unit was established by the International Electrotechnical Commission in 2000 and has been accepted for use by all major...
bitmap.
Disadvantages
- Wasteful on larger disks: The simplistic design starts wasting large amounts of space (in an absolute sense) for extremely large volumes
- Poor scalability: While the size remains negligible as a percentage of the disk size, finding free space becomes slower as the disk fills. If the bitmap is larger than available memoryRandom-access memoryRandom access memory is a form of computer data storage. Today, it takes the form of integrated circuits that allow stored data to be accessed in any order with a worst case performance of constant time. Strictly speaking, modern types of DRAM are therefore not random access, as data is read in...
, performance drops precipitously on all operations - FragmentationFile system fragmentationIn computing, file system fragmentation, sometimes called file system aging, is the inability of a file system to lay out related data sequentially , an inherent phenomenon in storage-backed file systems that allow in-place modification of their contents. It is a special case of data fragmentation...
: If free sectors are taken as they are found, drives with frequent file creation and deletion will rapidly become fragmented. If the search attempts to find contiguous blocks, finding free space becomes much slower for even moderately full disks.
Advanced techniques
As the drive size grows, the amount of time needed to scan for free space can become unreasonable. To address this, real world implementations of free space bitmaps will find ways to centralize information on free space. One approach is to split the bitmap into many chunks. A separate array then stores the number of free sectors in each chunk, so chunks with insufficient space can be easily skipped over, and the total amount of free space is easier to compute. Finding free space now entails searching the summary array first, then searching the associated bitmap chunk for the exact sectors available.This approach drastically reduces the cost of finding free space, but it doesn't help with the process of freeing space. If the combined size of the summary array and bitmap is greater than can readily be stored in memory and a large number of files with scattered sectors are freed, an enormous amount of disk access is necessary to find all the sectors, decrement the summary counter and flip the bits back to zero. This greatly reduces the benefits of the bitmap, as it is no longer performing its function of summarizing the free space rapidly without reading from the disk.
See also
- High Performance File System (HPFS)
- exFATExFATexFAT is a proprietary, patent-pending file system designed especially for USB flash drives. Developed by Microsoft, it is supported in Windows XP and Windows Server 2003 with update KB955704, Windows Embedded CE 6.0, Windows Vista with Service Pack 1, Windows Server 2008, Windows 7, Windows...
- Bitmap indexBitmap IndexA bitmap index is a special kind of database index that uses bitmaps.Bitmap indexes have traditionally been considered to work well for data such as gender, which has a small number of distinct values, for example male and female, but many occurrences of those values. This would happen if, for...
- A means of indexing databases that frequently overlaps with efficient free space bitmap designs - B-treeB-treeIn computer science, a B-tree is a tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree is a generalization of a binary search tree in that a node can have more than two children...
- An alternate means of tracking free space by storing a sorted set of free space extents