Re: [Qemu-devel] [PATCH 1/7] bt-sdp: fix broken uuids power-of-2 calculation

[Eric Blake]

On 03/17/2015 05:56 AM, Stefan Hajnoczi wrote:
> The binary search in sdp_uuid_match() only works when the number of
> elements to search is a power of two.
> 
>   lo = record->uuid;
>   hi = record->uuids;
>   while (hi >>= 1)
>       if (lo[hi] <= val)
>           lo += hi;
> 
>   return *lo == val;
> 
> I noticed that the record->uuids calculation in
> sdp_service_record_build() was suspect:
> 
>   record->uuids = 1 << ffs(record->uuids - 1);
> 
> Unlike most ffs(val) - 1 users, the expression is ffs(val - 1)!

Indeed, quite likely to be quite wrong.

> 
> Actually ffs() is the wrong function to use for power-of-2.  Use
> pow2ceil() to achieve the correct effect.  Now the record->uuid[] array
> is sized correctly and the binary search in sdp_uuid_match() should
> work.
> 
> I'm not sure how to run/test this code.

Me neither.  But I can still analyze the code for sanity.  Counts as a
bug fix, so I'd put this in 2.3, even if the rest of the series is
deferred to 2.4 as being a style cleanup rather than bug fix.

> 
> Cc: Andrzej Zaborowski <address@hidden>
> Signed-off-by: Stefan Hajnoczi <address@hidden>
> ---
>  hw/bt/sdp.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)

Reviewed-by: Eric Blake <address@hidden>

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org

signature.asc
Description: OpenPGP digital signature