Free-space bitmaps are one method used to track allocated
sectors
Sector may refer to:
Places
* Sector, West Virginia, U.S.
Geometry
* Circular sector, the portion of a disc enclosed by two radii and a circular arc
* Hyperbolic sector, a region enclosed by two radii and a hyperbolic arc
* Spherical sector, a p ...
by some
file system
In computing, file system or filesystem (often abbreviated to fs) is a method and data structure that the operating system uses to control how data is stored and retrieved. Without a file system, data placed in a storage medium would be one larg ...
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
A bit array (also known as bitmask, bit map, bit set, bit string, or bit vector) is an array data structure that compactly stores bits. It can be used to implement a simple set data structure. A bit array is effective at exploiting bit-level p ...
, i.e. a block of
bit
The bit is the most basic unit of information in computing and digital communications. The name is a portmanteau of binary digit. The bit represents a logical state with one of two possible values. These values are most commonly represente ...
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
The byte is a unit of digital information that most commonly consists of eight bits. Historically, the byte was the number of bits used to encode a single character of text in a computer and for this reason it is the smallest addressable unit ...
hard drive
A hard disk drive (HDD), hard disk, hard drive, or fixed disk is an electro-mechanical data storage device that stores and retrieves digital data using magnetic storage with one or more rigid rapidly rotating platters coated with magnet ...
with 4096-
byte
The byte is a unit of digital information that most commonly consists of eight bits. Historically, the byte was the number of bits used to encode a single character of text in a computer and for this reason it is the smallest addressable unit ...
sectors and assume that the bitmap itself is stored elsewhere. The example disk would require 1,048,576 bits, one for each sector, or 1
MiB. 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
An operating system (OS) is system software that manages computer hardware, software resources, and provides common services for computer programs.
Time-sharing operating systems schedule tasks for efficient use of the system and may also in ...
(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 whether 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 fraction of the drive size: Even with relatively small sector sizes, the storage space required for the bitmap is small. A 2
TB drive could be fully represented with a mere 64
MB bitmap (for 4096-
byte
The byte is a unit of digital information that most commonly consists of eight bits. Historically, the byte was the number of bits used to encode a single character of text in a computer and for this reason it is the smallest addressable unit ...
sectors).
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 fraction of the disk size, finding free space becomes slower as the disk fills. If the bitmap is larger than available
memory
Memory is the faculty of the mind by which data or information is encoded, stored, and retrieved when needed. It is the retention of information over time for the purpose of influencing future action. If past events could not be remembered, ...
, performance drops precipitously on all operations.
*
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. Fragmented data also slows down reading speeds on mechanical hard drives due to seeking
latency of the magnetic head, though this is not an issue on
flash memory
Flash memory is an electronic non-volatile computer memory storage medium that can be electrically erased and reprogrammed. The two main types of flash memory, NOR flash and NAND flash, are named for the NOR and NAND logic gates. Both us ...
.
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
*
Block availability map In computer file systems, a block availability map (BAM) is a data structure used to track block size (data storage and transmission), disk blocks that are considered free (available for new data). It is used along with a directory (file systems), ...
*
High Performance File System
HPFS (High Performance File System) is a file system created specifically for the OS/2 operating system to improve upon the limitations of the FAT file system. It was written by Gordon Letwin and others at Microsoft and added to OS/2 version 1 ...
(HPFS)
*
exFAT
exFAT (Extensible File Allocation Table) is a file system introduced by Microsoft in 2006 and optimized for flash memory such as USB flash drives and SD cards. exFAT was proprietary until 28 August 2019, when Microsoft published its specificati ...
*
Bitmap index a means of indexing databases that frequently overlaps with efficient free-space bitmap designs
*
B-tree
In computer science, a B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree generalizes the binary search tree, allowing for n ...
an alternate means of tracking free space by storing a sorted set of free-space extents
References
{{reflist
Bit data structures
Computer file systems