Re: [RFC PATCH 10/10] x86/unwind: add undwarf unwinder

[Jiri Slaby]

On 06/01/2017, 02:26 PM, Josh Poimboeuf wrote:
> On Thu, Jun 01, 2017 at 01:05:39PM +0200, Peter Zijlstra wrote:
>> On Thu, Jun 01, 2017 at 12:44:16AM -0500, Josh Poimboeuf wrote:
>>
>>> +static struct undwarf *__undwarf_lookup(struct undwarf *undwarf,
>>> +					unsigned int num, unsigned long ip)
>>> +{
>>> +	struct undwarf *first = undwarf;
>>> +	struct undwarf *last = undwarf + num - 1;
>>> +	struct undwarf *mid;
>>> +	unsigned long u_ip;
>>> +
>>> +	while (first <= last) {
>>> +		mid = first + ((last - first) / 2);
>>> +		u_ip = undwarf_ip(mid);
>>> +
>>> +		if (ip >= u_ip) {
>>> +			if (ip < u_ip + mid->len)
>>> +				return mid;
>>> +			first = mid + 1;
>>> +		} else
>>> +			last = mid - 1;
>>> +	}
>>> +
>>> +	return NULL;
>>> +}
>>
>> That's a bog standard binary search thing, don't we have a helper for
>> that someplace?
> 
> I wasn't able to find one...

There is bsearch, but that doesn't support searching for a value in
between of 2 keys. I.e. what we typically have is these keys:
  some_function1 at 0x1000
  some_function2 at 0x2000
and we look for IP which can be e.g. 0x1010. The bsearch's cmp function
currently has no option to say, yes, the last one you asked me was the
right one, this one is after it already.

thanks,
-- 
js
suse labs