logo.gif (6996 bytes)
Bitmap

Up
Block header
Root
AdminSpaceContainer
Bitmap
ObjectContainer
HashTable
BNodeContainer

The fsBitmap structure is used for Bitmap blocks.  A bitmap block is used to keep track of which space is in use and which isn't for a particular area of a disk.   All bitmap blocks together keep track of the free space for an entire disk.   The location of the first bitmap block is known and all other bitmap blocks are stored in order after the first one.

Field Type Description
bheader struct fsBlockHeader Standard block header.
bitmap ULONG An array of ULONG's.  These hold the actual information on which blocks are in use and which aren't.
struct fsBitmap {
    struct fsBlockHeader bheader;
    ULONG bitmap[0];
};

Each bit in a bitmap block (except for the block header) represents a single block.   If the bit is set than the block is free, and if the bit is clear then it is full.   The first ULONG in the bitmap area of the first bitmap block represents blocks 0 through 31 on the disk.  Bit 31 of this ULONG is block 0, 30 is block 1, and so on.   Bit 0 of the first ULONG represents block 31.

Below is a table to clarify how bitmaps work even further.  The first column is the bitmap block number, the second column is the number of the ULONG in the bitmap array.   The third column is the bit number in this ULONG, and the last column is the block which this specific bit, in this specific bitmap block represents.

We'll assume here that a bitmap block has room for 120 ULONG's (meaning there is room for storing 32 * 120 bits).

Bitmap block ULONG number Bit number Block represented
1 (first) 0 31 0
1 0 30 1
... ... ... ...
1 0 1 30
1 0 0 31
1 1 31 32
... ... ... ...
1 2 31 64
1 2 30 65
... ... ... ...
1 119 0 3839
2 0 31 3840
2 0 30 3841
... ... ... ...

The last bitmap block doesn't need to be completely used.  The unused bits (which belong to blocks which donot exist) all have to be clear, to indicate that these blocks are in use.


All rights reserved.
For comments, problems or questions regarding this page contact John Hendrikx.
Last updated: 17 oktober 1998.