A venerable technique for allocating file space for files on disk is to maintain a bit map with a bit for each disk block that records whether that block is currently allocated. When a data block is allocated its bit is turned on and its address is carried off to live in some index block which is itself a disk block associated with the file to which the data block belongs. Index blocks hold disk addresses to data blocks and other index blocks.

The bit map must survive on disk since RAM is volatile and the bit map may be large. The bit map may be rebuilt from reading index blocks but this is expensive. The bit map is itself divided into disk blocks and several will be cached in RAM any time that the system is running. Any particular portion of the bit map spends most of its life on disk.

Most files have a fleeting existence and come and go never having been written to disk. This makes temporary files vastly more efficient than if they actually lived on disk. Concomitantly with this, all disk blocks are written out lazily, mainly when RAM is tight or perhaps when there is idle disk writing capacity. Disk addresses are allocated to data blocks in such transient files as they are created in RAM even when they are never written on disk.

When a system boots without a valid RAM state, it reintroduces itself to files that survived the loss of RAM. It starts at some root block and follows disk addresses therein to other disk blocks. If there was an orderly shutdown then the bit map on disk will faithfully represent what disk blocks are allocated; in particular any block reachable from the root block by following disk addresses therein, have its bit map value = 1. If the system crashes it is possible that the bit map on disk is stale and marks a block as free when it is in fact allocated in light of index blocks that were written out. (Other inconsistencies are avoided by some technique such as insuring that block X is written to disk before block Y whenever Y holds the disk address of X.)

Upon orderly shutdown the system writes something to disk to indicates that the bit map on disk is valid. The opposite indication is written (promptly) on disk when new blocks are allocated. It is this indication that tells the system whether to a file check must be performed. The file check starts from the root index block and finds and reads all index blocks to rebuild the bit map. This takes minutes. An alternative that I have not seen used, is to divide the bit map into many regions and keep an up-to-date indication on the disk of which of these regions are valid on disk. The disk bit map would then be valid by region. Bit map regions in use at the time of the crash (whose disk state are stale) are taken permanently out of play until a full disk check is performed.

One crude way of doing this is to immediately write all ones to the portion of the bit map on disk when that portion is read from the disk for allocation. If the system crashes then it remains true that allocated disk blocks all have their bit set. The main penalty of this scheme is that the system has no good estimate of how much storage is unused yet marked allocated in the bit map.

An advantage of this scheme is that the file check can proceed concurrently with normal system service.