= Solution
Use a <block allocation bitmap>, one <bit> per allocatable <disk block number>, or a <free-block list>. Allocation removes a free block from the free representation; deallocation inserts it. Reserved <file system> structures, including the <inode table> and the free-space representation itself, must never be offered as free <file data blocks>. Free <inodes> can be tracked separately by an <inode allocation bitmap>.
A <file data block> becomes reusable when the <file system> has removed its ownership from the <file>. This happens, for example, when truncation discards that portion of the <file>, or when the <file> is finally destroyed. Destruction requires both removal of its last <hard link> and release of its last live reference: <unlinking an open file> must not reclaim blocks still needed through an <open file description>. A <memory-mapped file>, if supported, also requires its references to be accounted for. The <indirect block pointers>' own blocks are reclaimed when they are no longer needed.
There are two relevant notions of accessibility. Pathname-accessible <files> are those reached from the root through valid <directory entries>, subject to permissions; their allocated blocks are found through their <inodes>. Already-open <files> can additionally remain accessible through <file descriptors> even after their last names disappear. Allocated <file system> structures and blocks pinned by an operation must also be excluded from allocation. A <block allocation bitmap> must therefore describe actual allocation, rather than merely the blocks of currently named regular <files>.
One processor can still run several processes and be interrupted. Updating ownership and the free-space representation must therefore be serialized with respect to competing operations, for example through an appropriate kernel critical section. Persistence across a crash additionally requires <file-system crash consistency>, such as ordered updates or <file-system journaling>.
$$
\boxed{\text{last name removed}\ \not\Rightarrow\ \text{open-file blocks immediately free}.}
$$
Back to article page
