So I have a bitmap, of 2048 bits.
I ask for a clear bit at HintIndex 2047 (last 0-based inex to be a bit
in the bitmap, which is SET in my case) - but RtlFindClearBits gives
me index 1???
Am I missing something here? SHould I be looking at memory corruption,
or is RtlFindClear bits supposed to return index 1 in such a case?
i just put together some usermode code can you adapt it to reproduce the issue i seem to get correct results
#include <windows.h>
#include <stdio.h>
typedef struct _RTL_BITMAP
{
ULONG SizeOfBitMap;
PULONG Buffer;
} RTL_BITMAP,*PRTL_BITMAP;
VOID ( WINAPI *RtlInitializeBitMap ) ( PRTL_BITMAP, PULONG, ULONG );
ULONG ( WINAPI *RtlFindClearBits ) ( PRTL_BITMAP, ULONG, ULONG );
VOID ( WINAPI *RtlClearAllBits ) ( PRTL_BITMAP );
VOID ( WINAPI *RtlSetBits ) ( PRTL_BITMAP, ULONG,ULONG);
int main (void) {
HMODULE hMod = LoadLibrary("ntdll.dll");
if(!hMod)
{
printf("cannot load ntdll\n");
exit(-1);
}
*( FARPROC *)&RtlInitializeBitMap = GetProcAddress(hMod , "RtlInitializeBitMap" );
*( FARPROC *)&RtlFindClearBits = GetProcAddress(hMod , "RtlFindClearBits" );
*( FARPROC *)&RtlClearAllBits = GetProcAddress(hMod , "RtlClearAllBits" );
*( FARPROC *)&RtlSetBits = GetProcAddress(hMod , "RtlSetBits" );
if( RtlInitializeBitMap == NULL || RtlFindClearBits == NULL ||
RtlClearAllBits == NULL || RtlSetBits == NULL )
{
printf("GetProc failed\n");
exit(-1);
}
printf("ntdll loaded at %p\n" , hMod);
printf("RtlInitBMap is at %p\n", RtlInitializeBitMap);
printf("RtlFindClearBits is at %p\n", RtlFindClearBits);
printf("RtlSetBits is at %p\n", RtlSetBits);
RTL_BITMAP mybmap;
ULONG bmapbuff[2048];
ULONG fcbret = 0;
RtlInitializeBitMap(&mybmap,bmapbuff,2048);
RtlClearAllBits(&mybmap);
fcbret= RtlFindClearBits(&mybmap,1,2047); //2047
printf("fcbret = %u\n" , fcbret);
fcbret = RtlFindClearBits(&mybmap,3,2047); // 0 only 1 clear bit
printf("fcbret = %u\n" , fcbret);
fcbret = RtlFindClearBits(&mybmap,5,2047); // 0 only one clear bit
printf("fcbret = %u\n" , fcbret);
RtlSetBits(&mybmap,2040,3);
fcbret= RtlFindClearBits(&mybmap,1,2047); // 2047
printf("fcbret = %u\n" , fcbret);
fcbret = RtlFindClearBits(&mybmap,3,2040); // 2043 ,44, 45 are clear
printf("fcbret = %u\n" , fcbret);
fcbret = RtlFindClearBits(&mybmap,6,2040); // 0
printf("fcbret = %u\n" , fcbret);
fcbret = RtlFindClearBits(&mybmap,1741,300); // 0 2041 is set
printf("fcbret = %u\n" , fcbret);
}
results seem to be what i think it should be in comments
:\>rtlbitmap.exe
ntdll loaded at 77370000
RtlInitBMap is at 773D5871
RtlFindClearBits is at 773D5DFF
RtlSetBits is at 773D5D0C
fcbret = 2047
fcbret = 0
fcbret = 0
fcbret = 2047
fcbret = 2043
fcbret = 0
fcbret = 0
:>
Which OS is that? I am testing on W7 x86.
I found an article from NT Insider which indicates that this 9my results…) is what it used to work like, prior to Win2K, but then changed. The article is old, so it does not speak of later OSes.
But this is nuts 
I changed your code to include the following two lines, after the RtlClearAllBits:
RtlSetBits(&mybmap, 2047, 1);
RtlSetBits(&mybmap, 0, 1);
and changed the first RtlFindClearBits to:
fcbret= RtlFindClearBits(&mybmap,1,2046); //2047
and the output:
ntdll loaded at 77CE0000
RtlInitBMap is at 77D140C3
RtlFindClearBits is at 77D20FB5
RtlSetBits is at 77D210BC
fcbret = 2046
fcbret = 1
fcbret = 1
fcbret = 1
fcbret = 2043
fcbret = 1
fcbret = 1
indicates that the API does indeed wrap around
I changed the code to RtlFindFirstRunClear insteaad.
it is mentioned in the docs that this function Searches the Whole Bitmap for a run of required size but it starts Searching from the GivenHintIndex
quoted from doc
For a successful call, the returned bit position is not necessarily equivalent to the given HintIndex. If necessary, RtlFindClearBits searches the whole bitmap to locate a clear bit range of the requested size. However, it starts searching for the requested range from HintIndex, so callers can find such a range more quickly when they can supply appropriate hints about where to start looking.
you have probably Initilaized 2048 in RtlBitMapInitialize so it wraps around and returns 1
if you initialize say 2060 bits then you would get 2048 as result for all except the last one which will wrap around
changed code
RtlInitializeBitMap(&mybmap,bmapbuff,2060);
RtlClearAllBits(&mybmap);
RtlSetBits(&mybmap, 2047, 1);
RtlSetBits(&mybmap, 0, 1);
fcbret= RtlFindClearBits(&mybmap,1,2046); //2047
printf("fcbret = %u\n" , fcbret);
fcbret = RtlFindClearBits(&mybmap,3,2047); // 0 only 1 clear bit
printf("fcbret = %u\n" , fcbret);
fcbret = RtlFindClearBits(&mybmap,5,2047); // 0 only one clear bit
printf("fcbret = %u\n" , fcbret);
RtlSetBits(&mybmap,2040,3);
fcbret= RtlFindClearBits(&mybmap,1,2047); // 2047
printf("fcbret = %u\n" , fcbret);
fcbret = RtlFindClearBits(&mybmap,3,2040); // 2043 ,44, 45 are clear
printf("fcbret = %u\n" , fcbret);
fcbret = RtlFindClearBits(&mybmap,6,2040); // 0
printf("fcbret = %u\n" , fcbret);
fcbret = RtlFindClearBits(&mybmap,1741,300); // 0 2041 is set
printf("fcbret = %u\n" , fcbret);
results
:\>rtlbitmap.exe
ntdll loaded at 77370000
RtlInitBMap is at 773D5871
RtlFindClearBits is at 773D5DFF
RtlSetBits is at 773D5D0C
fcbret = 2046
fcbret = 2048
fcbret = 2048
fcbret = 2048
fcbret = 2043
fcbret = 2048
fcbret = 1
the 1 is because you have set 1 bit at index 0
if you change the second set to say
RtlSetBits(&mybmap, 6, 3);
the last findclear will wrap around and return you the index 9
: >rtlbitmap.exe
ntdll loaded at 77370000
RtlInitBMap is at 773D5871
RtlFindClearBits is at 773D5DFF
RtlSetBits is at 773D5D0C
fcbret = 2046
fcbret = 2048
fcbret = 2048
fcbret = 2048
fcbret = 2043
fcbret = 2048
fcbret = 9
is RtlFindClear bits supposed to return index 1 in such a case?
Not to be stupid, but what is it that you’re expecting? If bit 0 is clear, I would think you get back zero. Is that your point? It’s skipping index 0?
Also, just as a side notes: there’s a bug in Win7, where RtlInitializeBitmap is located in paged code. All the other functions are fine… just the initialization function. We ran into this is a major project a while back, where Win7 support was required.
Peter
I am expecting that it not wrap around, i.e. if I specify HintIndex,
that the returned index cannot be lower than HintIndex. I did not
expect it would search the bitmap, and go back to bit 0 if it did not
find clear bits.
It searches HintIndex BitapSize and then 0 to HintIndex - 1 in other
words. I expected it would search HintIndex to BitmapSize only.
The NT Insider article indicated that the behavior changed between NT4
and Win2K, but it changed to what I expected it would do.
So, I am changing the code to use RtlFindNextForwardRunClear.
Thanks for mentioning that, Windows 7 is still the most important OS
for us, by far.
Dejan.
Not to be stupid, but what is it that you’re expecting? If bit 0 is clear,
I would think you get back zero. Is that your point? It’s skipping index
0?Also, just as a side notes: there’s a bug in Win7, where
RtlInitializeBitmap is located in paged code. All the other functions are
fine… just the initialization function. We ran into this is a major
project a while back, where Win7 support was required.
I am expecting that it not wrap around
Ah! It definitely wraps around. A feature on which I have routinely relied.
Funny, you mentioning these routines now. Friday I was writing code to use them. Super handy, and surprisingly efficient.
Peter
I checked these:
http://www.osronline.com/article.cfm?article=523
(funny enough, mentioning that all the Find functions “Start at a
specified position”)
but more importantly:
http://www.osronline.com/article.cfm?id=36
" Well, it turns out using these functions can be just hard enough –
hard enough to break your code that is. It seems that the
implementation of these functions changed between NT V4 and Win2K.
Prior to Win2K, our use of these functions indicated that if you
passed in a “hint index” that was past the bit range for which you
were searching, the functions would return to the beginning of the
bitmap and start searching from the beginning of the bitmap. That is,
the “hint index” was used as a guess; if the guess turned out to be
wrong, and pointed beyond the only range in the bitmap that would
satisfy your request, the function searched from beginning of the
bitmap and returned a matching range. This does not appear to be the
case in the Win2K implementation of this function, even though the
documentation seems to indicate that this is the way the function
works.
In Win2K, our experience with these functions has been that if the
only matching range in the bitmap appears before the “hint index”, the
functions no long return to search the bitmap from the beginning, and
the functions now return 0xFFFFFFFF (to indicate that a suitable range
in the bitmap was not found).
"
so the wrap around happened on NT4 - but NOT on Windows 2K. I expected
the change to flow into Windows 7/10
I ran a bug on the docs to make sure this was mentioned.
Yeah, the kernel has an amazing choice of some basic structure
manipulation APIs that are both handy and efficient. Things that some
user mode compilers didn’t get until recently (I recently found that
C++11 did not officially have a RW lock! Something I used in 1995/6
already in a driver)
> I am expecting that it not wrap around
Ah! It definitely wraps around. A feature on which I have routinely
relied.Funny, you mentioning these routines now. Friday I was writing code to use
them. Super handy, and surprisingly efficient.
Am I supposed to get e-mails for my own posts, BTW?
On 3/11/19, Dejan_Maksimovic
wrote:
> OSR http://osr.vanillacommunities.com/
> Dejan_Maksimovic commented on RtlFindClearBits issue
>
> I checked these:
> http://www.osronline.com/article.cfm?article=523
> (funny enough, mentioning that all the Find functions “Start at a
> specified position”)
> but more importantly:
> http://www.osronline.com/article.cfm?id=36
> " Well, it turns out using these functions can be just hard enough –
> hard enough to break your code that is. It seems that the
> implementation of these functions changed between NT V4 and Win2K.
> Prior to Win2K, our use of these functions indicated that if you
> passed in a “hint index” that was past the bit range for which you
> were searching, the functions would return to the beginning of the
> bitmap and start searching from the beginning of the bitmap. That is,
> the “hint index” was used as a guess; if the guess turned out to be
> wrong, and pointed beyond the only range in the bitmap that would
> satisfy your request, the function searched from beginning of the
> bitmap and returned a matching range. This does not appear to be the
> case in the Win2K implementation of this function, even though the
> documentation seems to indicate that this is the way the function
> works.
>
> In Win2K, our experience with these functions has been that if the
> only matching range in the bitmap appears before the “hint index”, the
> functions no long return to search the bitmap from the beginning, and
> the functions now return 0xFFFFFFFF (to indicate that a suitable range
> in the bitmap was not found).
> "
>
> so the wrap around happened on NT4 - but NOT on Windows 2K. I expected
> the change to flow into Windows 7/10
>
> I ran a bug on the docs to make sure this was mentioned.
>
>
> Yeah, the kernel has an amazing choice of some basic structure
> manipulation APIs that are both handy and efficient. Things that some
> user mode compilers didn’t get until recently (I recently found that
> C++11 did not officially have a RW lock! Something I used in 1995/6
> already in a driver)
>
>>> I am expecting that it not wrap around
>>
>> Ah! It definitely wraps around. A feature on which I have routinely
>> relied.
>>
>> Funny, you mentioning these routines now. Friday I was writing code to
>> use
>> them. Super handy, and surprisingly efficient.
>
> –
> Reply to this email directly or follow the link below to check it out:
> http://osr.vanillacommunities.com/discussion/comment/292935#Comment_292935
>
> Check it out:
> http://osr.vanillacommunities.com/discussion/comment/292935#Comment_292935
>
Am I supposed to get e-mails for my own posts, BTW?
Nope. We’re told it’s a “feature” of the new platform.
Peter
Funnier still than the synchronicity of our both using these functions in the same week, is the fact that I wrote the article about “bug or planned change” that you pointed to and quoted. I don’t remember it at all. But I’m definitely the author. Nobody else here would throw a disparaging reference to President Reagan into an article. It was, what… only 20 years ago?
Peter
Good thing I do not believe in magic, or I’d be very scared now 
Funnier still than the synchronicity of our both using these functions in
the same week, is the fact that I wrote the article about “bug or planned
change” that you pointed to and quoted. I don’t remember it at all. But
I’m definitely the author. Nobody else here would throw a disparaging
reference to President Reagan into an article. It was, what… only 20
years ago?