So what is a bitmap? Obviously it is not (just) a graphic! In Windows a bitmap is a set of one or more continuous unsigned longwords, in which each bit in the set represents some state to the implementer. In File Systems, bitmaps are commonly used to represent the sectors (or clusters) on a volume that are free or in use. In other types of drivers, bitmaps might be used to indicate, for example, which entries in a fixed length table are free or in use.

Let's look at a simple example of bitmap use. Assume that we are implementing a file system that supports a disk with 32 clusters on it. Our volume bitmap would look like the bitmap in the figure below once our File System is formatted.

Figure 1

Notice that two bits are set in this example bitmap: bits 0 and 31. In this simple file system implementation, the file system sets these bits to indicate that clusters 0 and 31 are in use. The remaining bits are clear, indicating all the other clusters are free.

If the file system is asked to create a file on the volume, it will need to quickly determine where to put the information on disk. A simple way to determine this is by scanning the bitmap looking for the first unset bit or bits in the bitmap. Since an unset bit indicates a free cluster on the disk, scanning the bitmap for an unset bit is a fast and efficient way to search for free space. Pretty simple.

RTL_BITMAP

While implementing you own bitmap would be pretty simple, Windows provides support for bitmaps via the RTL_BITMAP structure as defined below (from the WDK):

typedef struct _RTL_BITMAP {
    ULONG SizeOfBitMap;                     // Number of bits in bit map
    PULONG Buffer;                          // Pointer to the bit map itself
} RTL_BITMAP;
typedef RTL_BITMAP *PRTL_BITMAP;

You should note a few things about the RTL_BITMAPs:

• Consider what IRQLs at which you will be accessing the bitmap. If the IRQL will always be less than IRQL DISPATCH_LEVEL then you are free to put the structures, RTL_BITMAP structure and bitmap buffer, in paged memory. If, however, you access the bitmap at IRQL DISPATCH_LEVEL or higher, then both the RTL_BITMAP structure and the bitmap buffer are going to have to reside in non-paged memory. A simple thought, but one that is sometimes overlooked.
• No synchronization is provided by the RTL_BITMAP routines. Therefore if two threads of execution could attempt to access the bitmap structure simultaneously, it is your responsibility to synchronize them appropriately.

In addtion, Windows provides a lot of routines to use a bitmap and we'll discuss them in the following sections.

If you use a bitmap, you'll need a way to set and clear bits in that bitmap. To that end Windows provides two routines that allow you to set bits and two routines that allow you to clear bits. Those routines are listed below:

• RtlSetBits - which allows you to set one or more bits in a given range of a bitmap
• RtlSetAllBits - which allows you to set all the bits in a bitmap
• RtlClearBits - which allows you to clear one or more bits in a given range of a bitmap
• RtlClearAllBits - which allows you to clear all the bits in a bitmap

Let us see an example of how to use one of these functions. Assume that we are once again writing the simple file system driver mentioned earlier and shown in the figure. Our file system driver needs to reserve two clusters for a new file. How do we set them? Well doing that is simple! We call RtlSetBits which has the following prototype:

VOID RtlSetBits(IN PRTL_BITMAP Bm,IN ULONG StartingIndex,IN ULONG NumberToSet);

Thus our call would specify our bitmap, a starting index of 0 so that we start at the beginning of the bitmap, and the number of bits to set would be two. Upon completion, our bitmap would be illustrated in the figure below.

Figure 2

Your next question might be how to find a contiguous range of clear bits. Luckily, Windows has provided an array of functions to provide that functionally.

Finding set or clear bits in a RTL_BITMAP

As mentioned in the previous section, you need to have a way to find a range of bits in the bitmap that meet a search criteria of either being set or cleared. Windows provides you with a vast array of functions to do that. The routines are:

• RtlFindClearBits - which tries to find a clear bit range of the requested size, starting from a specified index position
• RtlFindClearBitsAndSet - which tries to find and set a clear bit range of the requested size, starting from a specified index position
• RtlFindClearRuns - which finds the specified number of runs of clear bits, starting from a specified index position
• RtlFindFirstRunClear - which finds the first contiguous range of clear bits, starting from a specified index position
• RtlFindLastBackwardRunClear - which finds the preceding clear run of bits, starting from a specified index position
• RtlFindLongestRunClear - which finds the largest contiguous range of clear bits, starting from a specified index position
• RtlFindNextForwardRunClear - which finds the next clear run of bits, starting from a specified index position
• RtlFindSetBits - which finds a range of set bits of the requested size, starting from a specified index position
• RtlFindSetBitsAndClear - which finds a range of set bits of the requested size and clears the bits, when located, starting from a specified index position

Let's see an example of one of these functions. Again, let's continue with our simple file system driver example. In this case, before we called RtlSetBits in the previous section, we first wanted to determine whether or not we had sufficient free space on the volume to hold the two cluster file. In other words, we want to find two consecutive bits in the bitmap that are clear. To do that we would call RtlFindClearBits, this has the following signature:

ULONG RtlFindClearBits(IN PRTL_BITMAP Bm,IN ULONG NumberToFind,IN ULONG HintIndex);

Windows offers a few informational functions that might be useful to you in using bitmaps:

• RtlNumberOfClearBits - returns the number of clear bits in the bitmap
• RtlNumberOfSetBits - returns the number of bits set in the bitmap
• RtlCheckBit - determines whether a specified bit is set or cleared
• RtlAreBitsSet - determines whether a given range of bits are set
• RtlAreBitsClear - determines whether a given range of bits are clear

As you can see these functions can be quite useful. Calling RtlNumberOfClearBits would tell our simple file system driver how much free space was available, while RtlNumberOfSetBits would tell the file system driver how much space was used.

Summary