Skip to contentSkip to conversation

Problem with find_first_bit function and kin

DISCUSSION Alex Dubov 2 participants 4 messages Aug 16, 2008 – Aug 18, 2008

lore
Share & tools
lore

Alex Dubov

author
#0 lore raw

It's well may be that I'm just missing something obvious.

It seems to me that find_first_bit/find_next_bit functions return their offsets "base 1" - first set bit is "1" and last is "bitmap size". This means that if only the last bit in the bitmap is set, the returned value will be indistinguishable from no bits set situation. Moreover, bit manipulation functions appear to use "base 0" bit addresses, adding to the inconvenience.

Is this a desired behavior? And, if yes, how is one supposed to deal with last bit of the bitmap?

#1 lore raw
Quoted 10 lines · Alex Dubov

It's well may be that I'm just missing something obvious.

It seems to me that find_first_bit/find_next_bit functions return their offsets "base 1" - first set bit is "1" and last is "bitmap size". This means that if only the last bit in the bitmap is set, the returned value will be indistinguishable from no bits set situation. Moreover, bit manipulation functions appear to use "base 0" bit addresses, adding to the
inconvenience.

Quoted 2 lines

Is this a desired behavior? And, if yes, how is one supposed to deal with last bit of the bitmap?

Hi Alex,

If this is the behaviour you observe, it's a bug. How did you find out?

The intended behaviour is that the bits are enumerated in "base 0" style. If only the last bit in the bitmap is set it should return bitmapsize-1 and if no bit is set it should return bitmapsize. Some architecture-specific code gets the last detail wrong, they return a value that is slightly larger than the bitmap size in some cases.

Greetings,
Alexander

Signature · 5 lines
  Alexander van Heukelum
  [email protected]

-- 
http://www.fastmail.fm - A no graphics, no pop-ups email service
author
#2 lore raw
Quoted 45 lines · Alexander van Heukelum

From: Alexander van Heukelum <[email protected]>
Subject: Re: Problem with find_first_bit function and kin
To: [email protected], "Linux kernel mailing list" <[email protected]>
Date: Sunday, August 17, 2008, 4:58 AM

Quoted 1 line · Alex Dubov

It's well may be that I'm just missing

something obvious.

Quoted 2 lines

It seems to me that find_first_bit/find_next_bit

functions return their

Quoted 1 line

offsets "base 1" - first set bit is

"1" and last is "bitmap size". This

Quoted 1 line

means that if only the last bit in the bitmap is set,

the returned value

Quoted 1 line

will be indistinguishable from no bits set situation.

Moreover, bit

Quoted 1 line

manipulation functions appear to use "base

0" bit addresses, adding to

Quoted 4 lines

the
inconvenience.

Is this a desired behavior? And, if yes, how is one

supposed to deal with

Quoted 1 line

last bit of the bitmap?

Hi Alex,

If this is the behaviour you observe, it's a bug. How did you
find out?

The intended behaviour is that the bits are enumerated in "base 0"
style. If only the last bit in the bitmap is set it should return
bitmapsize-1 and if no bit is set it should return bitmapsize.
Some architecture-specific code gets the last detail wrong, they
return a value that is slightly larger than the bitmap size in
some cases.

Quoted 3 lines

Greetings,
Alexander

I was compiling some stuff out-of-the tree and got "ffs" linked in instead of "__ffs", which caused all this weird behavior (on 64b platform). Sorry for the noise.

But then, why "ffs" behaves differently from "__ffs" and whats the reason they both exist?

#3 lore raw
Quoted 51 lines · Alex Dubov
Quoted 45 lines · Alexander van Heukelum

From: Alexander van Heukelum <[email protected]>
Subject: Re: Problem with find_first_bit function and kin
To: [email protected], "Linux kernel mailing list" <[email protected]>
Date: Sunday, August 17, 2008, 4:58 AM

Quoted 1 line · Alex Dubov

It's well may be that I'm just missing

something obvious.

Quoted 2 lines

It seems to me that find_first_bit/find_next_bit

functions return their

Quoted 1 line

offsets "base 1" - first set bit is

"1" and last is "bitmap size". This

Quoted 1 line

means that if only the last bit in the bitmap is set,

the returned value

Quoted 1 line

will be indistinguishable from no bits set situation.

Moreover, bit

Quoted 1 line

manipulation functions appear to use "base

0" bit addresses, adding to

Quoted 4 lines

the
inconvenience.

Is this a desired behavior? And, if yes, how is one

supposed to deal with

Quoted 1 line

last bit of the bitmap?

Hi Alex,

If this is the behaviour you observe, it's a bug. How did you
find out?

The intended behaviour is that the bits are enumerated in "base 0"
style. If only the last bit in the bitmap is set it should return
bitmapsize-1 and if no bit is set it should return bitmapsize.
Some architecture-specific code gets the last detail wrong, they
return a value that is slightly larger than the bitmap size in
some cases.

Quoted 3 lines

Greetings,
Alexander

Quoted 6 lines

I was compiling some stuff out-of-the tree and got "ffs" linked in instead of "__ffs", which caused all this weird behavior (on 64b platform). Sorry for the noise.

But then, why "ffs" behaves differently from "__ffs" and whats the reason they both exist?

The difference is that __ffs does base-0 indexing on a long type and ffs does base-1 indexing on a regular int type. Also, __ffs(0) is undefined, while ffs(0) returns 0. ffs is the odd one out in the kernel, but its behaviour is set in stone, because gcc may replace any call to ffs with its own (usually inlined) version, which behaves as described.

Greetings,
Alexander

Signature · 5 lines
  Alexander van Heukelum
  [email protected]

-- 
http://www.fastmail.fm - Email service worth paying for. Try it for free