From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751168AbdFANCF (ORCPT ); Thu, 1 Jun 2017 09:02:05 -0400 Received: from mx1.redhat.com ([209.132.183.28]:60820 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750952AbdFANCD (ORCPT ); Thu, 1 Jun 2017 09:02:03 -0400 DMARC-Filter: OpenDMARC Filter v1.3.2 mx1.redhat.com 4B9B87AE8C Authentication-Results: ext-mx01.extmail.prod.ext.phx2.redhat.com; dmarc=none (p=none dis=none) header.from=redhat.com Authentication-Results: ext-mx01.extmail.prod.ext.phx2.redhat.com; spf=pass smtp.mailfrom=jpoimboe@redhat.com DKIM-Filter: OpenDKIM Filter v2.11.0 mx1.redhat.com 4B9B87AE8C Date: Thu, 1 Jun 2017 08:02:01 -0500 From: Josh Poimboeuf To: Jiri Slaby Cc: Peter Zijlstra , x86@kernel.org, linux-kernel@vger.kernel.org, live-patching@vger.kernel.org, Linus Torvalds , Andy Lutomirski , Ingo Molnar , "H. Peter Anvin" Subject: Re: [RFC PATCH 10/10] x86/unwind: add undwarf unwinder Message-ID: <20170601130201.uuijo6h6irna23ri@treble> References: <89552d4047e5aed843f7b6a54277f9af62da6a82.1496293620.git.jpoimboe@redhat.com> <20170601110539.helelmmngwaba7fa@hirez.programming.kicks-ass.net> <20170601122651.g6xtofvyy3mbo7lq@treble> <66294b55-46c1-e339-52df-da9639227e78@suse.cz> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline In-Reply-To: <66294b55-46c1-e339-52df-da9639227e78@suse.cz> User-Agent: Mutt/1.6.0.1 (2016-04-01) X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.5.16 (mx1.redhat.com [10.5.110.25]); Thu, 01 Jun 2017 13:02:03 +0000 (UTC) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Thu, Jun 01, 2017 at 02:47:48PM +0200, Jiri Slaby wrote: > 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. Actually, I think bsearch would work with the latest version of the data structure. It now has a len field, so we can do a self-contained compare. -- Josh