Re: [Qemu-devel] [PATCH 12/15] openpic: IRQ_check: search the queue a word at a time

[Alexander Graf]

On 03.01.2013, at 21:32, Scott Wood wrote:

> On 01/03/2013 02:31:30 PM, Alexander Graf wrote:
>> Am 03.01.2013 um 21:07 schrieb Scott Wood <address@hidden>:
>> > On 01/03/2013 12:53:13 PM, Alexander Graf wrote:
>> >> On 22.12.2012, at 03:15, Scott Wood wrote:
>> >> > Search the queue more efficiently by first looking for a non-zero word,
>> >> > and then using the common bit-searching function to find the bit within
>> >> > the word.  It would be even nicer if bitops_ffsl() could be hooked up
>> >> > to the compiler intrinsic so that bit-searching instructions could be
>> >> > used, but that's another matter.
>> >> >
>> >> > Signed-off-by: Scott Wood <address@hidden>
>> >> What we really want is a bitmap wide ffs() bipops helper function that 
>> >> returns the first set bit in a bitmap and can optimize the hell out of 
>> >> that operation inside of itself. I don't think this belongs to the 
>> >> OpenPIC code.
>> >
>> > Well, we do have find_next_bit() in bitops.c, but it looks comparitively 
>> > complicated in order to be generic and simply return a value rather than 
>> > perform an action on each bit set.  I suspect that the code in this patch 
>> > would be faster, and avoids the need for me to follow all the twists and 
>> > turns of find_next_bit() to figure out whether the undocumented interface 
>> > is actually exactly what I guess it to be (e.g. what does it return when 
>> > no bit is found?).
>> I would just call it bit_ffs and follow the same semantics.
> 
> I'm not sure how that's an answer to what I wrote...

The answer is "man ffs" and it will tell you what semantics the function would 
have. However given that find_next_bit() is defined in Linux, why not use its 
semantics? Can't we just copy Linux code here?

Whether it's faster or not is another question, but I'd like to keep bitops 
internals as internal to bitops as we can. We could even completely hide the 
bitops implementation details behind a private struct definition. But that 
would mean that we'd have to create an indirect memory access for the bitmap 
itself :(.

One advantage of keeping these bits internal would be that we could even add 
more accelerations. We could for example add another bitmap layer on top of the 
bitmap internally, similar to how the MSIs get another bitmap across all 
combined MSI registers in the MPIC. And find_next_bit could use that to speed 
up the lookup for really big bitmaps.


Alex