Block and Fragment Bitmaps

The allocation status of blocks and fragments is determined by a bitmap. In fact, there are two bitmaps for every block in UFS because there is a fragment bitmap and a block bitmap. You will notice that these bitmaps are opposite from what we typically find. These bitmaps are "free bitmaps" and are set to 1 when the object is unallocated and set to 0 when it is allocated.

We will first examine the fragment bitmap. Each cylinder group has a fragment bitmap located inside its group descriptor. The bitmap's byte offset is given in the group descriptor, and its size can be determined based on the number of fragments in the group. To find the bit for a specific fragment, we determine its address relative to the start of the cylinder group by subtracting the address of the first fragment in the group. If a fragment is the fiftieth in a group, its allocation status is given in the fiftieth bit, which is the second bit in byte 6.

In the UFS1 file system that we previously dissected, the group descriptor was located in block 24, and the fragment bitmap had an offset of 504 bytes. We view that with dcat and supply the 8 to show all eight fragments in the block:

# dcat -f openbsd openbsd.dd 24 8 | xxd

[REMOVED]

0000496: 0000 0000 0000 0000 0000 0000 0000 0000 ................

0000512: 0000 0000 0000 0000 0000 0000 0000 0000 ................

0000528: 0000 0000 0000 0000 0000 f0fe 0000 0000 ................

0000544: 0000 0000 ffff ffff 00ff 0000 0000 0000 ................

0000560: 0000 0000 0000 0000 0000 0000 0000 0000 ................

0000576: 0000 0000 0000 0000 0000 0000 0000 0000 ................

[REMOVED]

Byte 504 is the first byte in the fragment bitmap, and we see that it is 0, which means that the first eight fragments are allocated. We do not see any free fragments until byte 538, which is byte 34 in the bitmap. The four upper bits of the byte are set to 1, which means that fragments that are 276 to 279 are available. Because this is the first group, this is also their actual address; otherwise, we would have to add the starting address of the group. Notice that these four unallocated fragments do not represent a full block because each block has eight fragments in it. In this case, the first four fragments of a block are allocated and the final four are not.

Bytes 548 to 551 show a span of 32 consecutive fragments that are not allocated. Byte 548 corresponds to byte 44 of the bitmap, so the first bit is for fragment 352.

The fragment bitmap is not efficient for allocating blocks or large groups of consecutive blocks, so the block bitmap also exists. This bitmap duplicates the information that can be found in the fragment bitmap, but it uses 1 bit for each block. Because each bit corresponds to a block, we need to address the blocks differently. Therefore, we assign each block a consecutive address. For example, if we have eight fragments per block, instead of having block 0, 8, 16, 24, and so on, we would have block 0, 1, 2, 3, and so on. To calculate the block address, simply divide the fragment-based address by the number of fragments per block. If the corresponding bit is set to 1, the block is available.

In our UFS1 system, we saw that the block bitmap was located at offset 1,540 within the group descriptor:

# dcat -f openbsd openbsd.dd 24 8 | xxd

[REMOVED]

0001536: 0100 0000 0000 0000 00f0 0200 0000 0000 ................

0001552: 0000 0000 0000 0000 0000 0000 c0ff ffff ................

0001568: ffff ffff ffff ffff ffff ffff ffff ffff ................

[REMOVED]

We see that byte 1,540 is 0, and we do not see any bits set until byte 1,545, which has the upper four bits set. This is byte 5 in the bitmap, which means that its bits correspond to relative blocks 40 to 47, and the bits for relative blocks 44 to 47 are set to 1. If we convert these addresses to their fragment address, we get fragments 352 to 383, which we saw in the fragment bitmap as a collection of free consecutive fragments.