In computer systems, a problem which arises very often is as follows. A city has M blocks, numbered 0 to M-1. Each block has N houses, numbered 0 to N-1. Each house has a unique block address, denoted by (block, house), where 0 < = block < M, 0 < = house < N. An alien from outer space may be unfamiliar with the block addressing scheme on Earth and prefers to address the houses linearly as 0,1,..N-1,N, N + 1 …….. , etc. Given a block address BA = (block, house), how to convert it to a linear address LA, and vice versa? If everything counts from 0, the conversion is very simple.
Linear_address LA = N*block + house;
Block_address BA = (LA / N, LA % N);
Note that the conversion is valid only if everything counts from 0. If some of the items do not count from 0, they can not be used in the conversion formula directly. The reader may try to figure out how to handle such cases in general. For ease of reference, we shall refer to the conversion method as the Mailman’s algorithm. The following shows applications of the Mailman’s algorithm.
1. Test-Set-Clear Bits in C
(1) Test, Set and Clear bits in C: In standard C programs, the smallest addressable unit is a char or byte. It is often necessary to manipulate bits in a bitmap, which is a sequence of bits. Consider char buf [1024], which has 1024 bytes, denoted by buf[i], i = 0, 1,… ., 1023. It also has 8192 bits numbered 0,1,2,__ 8191. Given a bit number BIT, e.g. 1234, which byte i contains the bit, and which bit j is it in that byte? Solution:
i = BIT / 8; j = BIT % 8; // 8 = number of bits in a byte.
This allows us to combine the Mailman’ s algorithm with bit masking to do the following bit operations in C.
.TST a bit for 1 or 0 : if (buf[i] & (1 << j))
.SET a bit to 1 : buf[i] |= (1 << j);
.CLR a bit to 0 : buf[i] &= ~(1 << j);
It is noted that some C compilers allow specifying bits in a structure, as in.
The structure defines var. as an unsigned 32-bit integer with individual bits or ranges of bits. Then, var.bitO = 0; assigns 1 to bit 0, and var.bit123 = 5; assigns 101 to bits 1 to 3, etc. However, the generated code still relies on the Mailman’s algorithm and bit masking to access the individual bits. The Mailman’s algorithm allows us to manipulate bits in a bitmap directly without defining complex C structures.
2. Convert INODE Number to INODE on Disk
(2) In an EXT2 file system, each file has a unique INODE structure. On the file system disk, inodes begin in the inode_table Each disk block contains
INODES_PER_BLOCK = BLOCK_SIZE/sizeof(INODE)
inodes. Each inode has a unique inode number, ino = 1, 2, ………. , counted linearly from 1. Given an ino, e.g. 1234, determine which disk block contains the inode and which inode is it in that block? We need to know the disk block number because read/write a real disk is by blocks. Solution:
block = (ino – 1) / INODES_PER_BLOCK + inode_table;
inode = (ino – 1) % INODES_PER_BLOCK;
Similarly, converting double and triple indirect logical block numbers to physical block numbers in an EXT2 file system also depends on the Mailman’s algorithm.
(3) Convert linear disk block number to CHS = (cylinder, head, sector) format: Floppy disk and old hard disk use CHS addressing but file systems always use linear block addressing. The algorithm can be used to convert a disk block number to CHS when calling BIOS INT13.
Source: Wang K.C. (2018), Systems Programming in Unix/Linux, Springer; 1st ed. 2018 edition.