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 writing. It is used along with a directory to manage files on a disk.
In terms of Commodore Business Machines (CBM) compatible Disk Drives, the BAM was a data structure in the disk header whose size and location varied based on the physical characteristics of the disk. The BAM consisted of a bitmap of available blocks and (usually) a count of the available blocks for each track. 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 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 24 bits)[6]. Similarly, the Commodore 1571 used 3 bytes for the bitmap of each track, but the BAM was about 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 (logical) 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 for writing (free), 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 represented 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 Availibility 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 stored in reverse 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
References
- ^ Englisch, Lothar (1984). The Anatomy of the 1541 Disk Drive. Grand Rapids, MI: Abacus Software. p. 89. ISBN 0-916439-01-1.
- ^ 1541 User's Guide. Commodore Business Machines. 1982. p. 9.
- ^ 1571 User's Guide. Commodore Business Machines. 1985. p. 23.
- ^ 1581 User's Guide. Commodore Business Machines. 1987. p. 34.
- ^ FD Series User's Manual. Creative Micro Designs. 1992. p. 108.
- ^ 1541 User's Guide. Commodore Business Machines. 1982. p. 65.
- ^ 1571 User's Guide. Commodore Business Machines. 1985. p. 108-109.
- ^ 1581 User's Guide. Commodore Business Machines. 1987. p. 119-120.
- ^ FD Series User's Manual. Creative Micro Designs. 1992. p. 112-114.