Block availability map

In computer file systems, a block availability map (BAM) ^{[1] [2] [3] [4] [5]} is a data structure used to track disk blocks that are considered free (available for new data). It is used along with a directory to manage files on a disk (originally only a floppy disk, and later also a hard disk).

In terms of Commodore DOS (CBM DOS) compatible disk drives, the BAM was a data structure stored in a reserved area of the disk (its size and location varied based on the physical characteristics of the disk). For each track, the BAM consisted of a bitmap of available blocks and (usually) a count of the available blocks. The count was held in a single byte, as all formats had 256 or fewer blocks per track. The count byte was simply the sum of all 1-bits in the bitmap of bytes for the current track.

The following table illustrates the layout of Commodore 1541 BAM. The table would be larger for higher-capacity disks (described below).

	Total byte	Bitmap byte 1	Bitmap byte 2	Bitmap byte 3
Track 1	blocks available	Blocks 0-7	Blocks 8-15	Blocks 16-23
Track 2	blocks available	Blocks 0-7	Blocks 8-15	Blocks 16-23
...	...	...	...	...
Track 35	blocks available	Blocks 0-7	Blocks 8-15	Blocks 16-23

The bitmap was contained in 3 bytes for Commodore 1541 format (single-sided) disks because it had 17 to 20 sectors per track (note 3 bytes can hold at least 20 bits). ^[6] Similarly, the Commodore 1571 used 3 bytes for the bitmap of each track, but the BAM was twice the size because there were twice as many tracks when formatted as double-sided. ^[7] In contrast, the Commodore 1581 disk drive used 5 bytes for the bitmap because the disk format had 40 blocks per track (note 5 bytes can hold 40 bits). ^[8]

In the bitmap of any format, a 1 bit indicated the block was available (free), while a 0 bit indicated the block was not available (used), and the bitmap data was stored low-byte first. So the first byte held a map for blocks 0 to 7, the second byte held a map for blocks 8 to 15, and so on. Within a byte, the bitmap was ordered low-bit first. For example, the first byte would represent block 0 with the least significant bit and block 7 with the most significant bit.

Storage devices by Creative Micro Designs, intended for use with CBM computers, also used a Block Availability Map which served the same purpose. However, these devices (FD-2000, FD-4000, and CMD-HD) did not include a count byte, and the bits in each byte were reversed (high-bit first). Although the bits were reversed (compared to CBM formats), the bytes were still stored in the same order (low-byte first). ^[9]

	Bitmap byte 1	Bitmap byte 2	...	Bitmap byte 32
Track 1	Blocks 0-7	Blocks 8-15	...	Blocks 248-255
Track 2	Blocks 0-7	Blocks 8-15	...	Blocks 248-255
...	...	...	...	...

See also

• File Allocation Table (FAT)
• Design of the FAT file system
• Free space bitmap

References

1. Englisch, Lothar (1984). The Anatomy of the 1541 Disk Drive. Grand Rapids, MI: Abacus Software. p.  89. ISBN   0-916439-01-1.
2. 1541 User's Guide. Commodore Business Machines. 1982. p. 9.
3. 1571 User's Guide. Commodore Business Machines. 1985. p. 23.
4. 1581 User's Guide. Commodore Business Machines. 1987. p. 34.
5. FD Series User's Manual. Creative Micro Designs. 1992. p. 108.
6. 1541 User's Guide. Commodore Business Machines. 1982. p. 65.
7. 1571 User's Guide. Commodore Business Machines. 1985. pp. 108–109.
8. 1581 User's Guide. Commodore Business Machines. 1987. pp. 119–120.
9. FD Series User's Manual. Creative Micro Designs. 1992. pp. 112–114.