OSRLogo
OSRLogoOSRLogoOSRLogo x Subscribe to The NT Insider
OSRLogo
x

Everything Windows Driver Development

x
x
x
GoToHomePage xLoginx
 
 

    Sat, 17 Nov 2018     118021 members

   Login
   Join


 
 
Contents
  Online Dump Analyzer
OSR Dev Blog
The NT Insider
Downloads
ListServer / Forum
  Express Links
  · The NT Insider Digital Edition - May-June 2016 Now Available!
  · Windows 8.1 Update: VS Express Now Supported
  · HCK Client install on Windows N versions
  · There's a WDFSTRING?
  · When CAN You Call WdfIoQueueP...ously

Kernel Mode Basics: An Introduction to Bitmaps

A standard Windows data structure that many developers find helpful is the bitmap. A bitmap is a structure which allows you to quickly find the set or clear bits in a buffer. This is quite helpful if you have a fixed structure of entries and you want to quickly find which entries are free, for example. File Systems typically use bitmaps in order to keep track of which sectors on the volume are free or in use.

This article will describe bitmaps, how they are used, and the Windows RTL_BITMAP structure and helper functions that allow you to easily create and manipulate them.

Bitmaps

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;

The structure is initialized via a call to RtlInitializeBitMap, where you specify the address of the RTL_BITMAP structure, the address of the buffer that is the bitmap, and the number of bits in the bitmap. The prototype for the function is show below:

VOID RtlInitializeBitMap(IN PRTL_BITMAP Bm,In PULONG BitMapBuffer,
                                               IN ULONG SizeOfBitMap);

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.

Setting and clearing bits in a RTL_BITMAP

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);

So, our call would specify our bitmap, the number to find would be 2 (indicating the number of contiguous clear bits to find), and our hint index would be 0, indicating that we want to start our search from the beginning of the bitmap. Upon completion, this routine would return the zero-based starting bit index for a found clear bit range that matches our requested size, or it will return 0xFFFFFFFF if one cannot be found. In our case, if we started with an array as shown in Figure 1 the return from this call would be 1.

So, you've seen how to set and clear bits in the array. "Is that all?" you ask. Wait! There's more (sounds like some infomercial I've heard recently)! Windows provides a few functions that provide information on the state of the bitmap. Some of these are described in the following section.

Informational Functions

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

Windows offers a variety of data structures and associated routines that provide kernel developers with ready-made solutions to their data structure needs. RTL_BITMAPs are one of those provided data structures.

User Comments
Rate this article and give us feedback. Do you find anything missing? Share your opinion with the community!
Post Your Comment

"Excellent Gem"
This a very good article to gain an insight in to bitmaps.

Rating:
04-Nov-09, Rupesh Prasad


Post Your Comments.
Print this article.
Email this article.
bottom nav links