From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751253AbdFAMrx (ORCPT ); Thu, 1 Jun 2017 08:47:53 -0400 Received: from mail-wm0-f47.google.com ([74.125.82.47]:36700 "EHLO mail-wm0-f47.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751078AbdFAMrw (ORCPT ); Thu, 1 Jun 2017 08:47:52 -0400 Subject: Re: [RFC PATCH 10/10] x86/unwind: add undwarf unwinder To: Josh Poimboeuf , Peter Zijlstra Cc: x86@kernel.org, linux-kernel@vger.kernel.org, live-patching@vger.kernel.org, Linus Torvalds , Andy Lutomirski , Ingo Molnar , "H. Peter Anvin" References: <89552d4047e5aed843f7b6a54277f9af62da6a82.1496293620.git.jpoimboe@redhat.com> <20170601110539.helelmmngwaba7fa@hirez.programming.kicks-ass.net> <20170601122651.g6xtofvyy3mbo7lq@treble> From: Jiri Slaby Message-ID: <66294b55-46c1-e339-52df-da9639227e78@suse.cz> Date: Thu, 1 Jun 2017 14:47:48 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.1.1 MIME-Version: 1.0 In-Reply-To: <20170601122651.g6xtofvyy3mbo7lq@treble> Content-Type: text/plain; charset=utf-8 Content-Language: en-GB Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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