From patchwork Fri Oct 23 10:19:08 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Beulich X-Patchwork-Id: 11852705 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id CD80B157C for ; Fri, 23 Oct 2020 10:19:58 +0000 (UTC) Received: from lists.xenproject.org (lists.xenproject.org [192.237.175.120]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id 911C820936 for ; Fri, 23 Oct 2020 10:19:58 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (1024-bit key) header.d=suse.com header.i=@suse.com header.b="NWq48x/R" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 911C820936 Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=suse.com Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=xen-devel-bounces@lists.xenproject.org Received: from list by lists.xenproject.org with outflank-mailman.10849.28979 (Exim 4.92) (envelope-from ) id 1kVuA9-0001Mj-Jy; Fri, 23 Oct 2020 10:19:09 +0000 X-Outflank-Mailman: Message body and most headers restored to incoming version Received: by outflank-mailman (output) from mailman id 10849.28979; Fri, 23 Oct 2020 10:19:09 +0000 X-BeenThere: xen-devel@lists.xenproject.org List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xenproject.org Precedence: list Sender: "Xen-devel" Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1kVuA9-0001Mc-G7; Fri, 23 Oct 2020 10:19:09 +0000 Received: by outflank-mailman (input) for mailman id 10849; Fri, 23 Oct 2020 10:19:07 +0000 Received: from us1-rack-iad1.inumbo.com ([172.99.69.81]) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1kVuA7-0001ML-Ne for xen-devel@lists.xenproject.org; Fri, 23 Oct 2020 10:19:07 +0000 Received: from mx2.suse.de (unknown [195.135.220.15]) by us1-rack-iad1.inumbo.com (Halon) with ESMTPS id 1014aeee-1e22-4d37-a6d0-95a688ff8cf7; Fri, 23 Oct 2020 10:19:06 +0000 (UTC) Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id D9A7CAD04; Fri, 23 Oct 2020 10:19:05 +0000 (UTC) Received: from us1-rack-iad1.inumbo.com ([172.99.69.81]) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1kVuA7-0001ML-Ne for xen-devel@lists.xenproject.org; Fri, 23 Oct 2020 10:19:07 +0000 X-Inumbo-ID: 1014aeee-1e22-4d37-a6d0-95a688ff8cf7 Received: from mx2.suse.de (unknown [195.135.220.15]) by us1-rack-iad1.inumbo.com (Halon) with ESMTPS id 1014aeee-1e22-4d37-a6d0-95a688ff8cf7; Fri, 23 Oct 2020 10:19:06 +0000 (UTC) X-Virus-Scanned: by amavisd-new at test-mx.suse.de DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.com; s=susede1; t=1603448346; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=7kZoCIqv4yQVugUvj1z6blQttzij9hYwlGKaJUnpBgI=; b=NWq48x/RySaomVo5kON84Ox76WEKa0qzw91tc1UM95npyomVIUXhXGr6U4Zw6tXnaQW+cC YT/aTY8Y+LTxeq0LmQWSwK5wgFsNRKBaV4rtGU78eL9ByJgrmvKl2D8bT/2TETc2Rn1MW3 X8JK1d/OE9HanmEibBWABAUXQJIUEQM= Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id D9A7CAD04; Fri, 23 Oct 2020 10:19:05 +0000 (UTC) Subject: [PATCH v2 7/8] lib: move bsearch code From: Jan Beulich To: "xen-devel@lists.xenproject.org" Cc: Andrew Cooper , George Dunlap , Ian Jackson , Julien Grall , Wei Liu , Stefano Stabellini References: Message-ID: <87a20884-5a76-a664-dcc9-bd4becee40b3@suse.com> Date: Fri, 23 Oct 2020 12:19:08 +0200 User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:68.0) Gecko/20100101 Thunderbird/68.12.1 MIME-Version: 1.0 In-Reply-To: Content-Language: en-US Convert this code to an inline function (backed by an instance in an archive in case the compiler decides against inlining), which results in not having it in x86 final binaries. This saves a little bit of dead code. Signed-off-by: Jan Beulich Reviewed-by: Bertrand Marquis --- v2: Make the function an extern inline in its header. --- xen/common/Makefile | 1 - xen/common/bsearch.c | 51 -------------------------------------- xen/include/xen/compiler.h | 1 + xen/include/xen/lib.h | 42 ++++++++++++++++++++++++++++++- xen/lib/Makefile | 1 + xen/lib/bsearch.c | 13 ++++++++++ 6 files changed, 56 insertions(+), 53 deletions(-) delete mode 100644 xen/common/bsearch.c create mode 100644 xen/lib/bsearch.c diff --git a/xen/common/Makefile b/xen/common/Makefile index 7bb779f780a1..d8519a2cc163 100644 --- a/xen/common/Makefile +++ b/xen/common/Makefile @@ -1,6 +1,5 @@ obj-$(CONFIG_ARGO) += argo.o obj-y += bitmap.o -obj-y += bsearch.o obj-$(CONFIG_HYPFS_CONFIG) += config_data.o obj-$(CONFIG_CORE_PARKING) += core_parking.o obj-y += cpu.o diff --git a/xen/common/bsearch.c b/xen/common/bsearch.c deleted file mode 100644 index 7090930aab5c..000000000000 --- a/xen/common/bsearch.c +++ /dev/null @@ -1,51 +0,0 @@ -/* - * A generic implementation of binary search for the Linux kernel - * - * Copyright (C) 2008-2009 Ksplice, Inc. - * Author: Tim Abbott - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License as - * published by the Free Software Foundation; version 2. - */ - -#include - -/* - * bsearch - binary search an array of elements - * @key: pointer to item being searched for - * @base: pointer to first element to search - * @num: number of elements - * @size: size of each element - * @cmp: pointer to comparison function - * - * This function does a binary search on the given array. The - * contents of the array should already be in ascending sorted order - * under the provided comparison function. - * - * Note that the key need not have the same type as the elements in - * the array, e.g. key could be a string and the comparison function - * could compare the string with the struct's name field. However, if - * the key and elements in the array are of the same type, you can use - * the same comparison function for both sort() and bsearch(). - */ -void *bsearch(const void *key, const void *base, size_t num, size_t size, - int (*cmp)(const void *key, const void *elt)) -{ - size_t start = 0, end = num; - int result; - - while (start < end) { - size_t mid = start + (end - start) / 2; - - result = cmp(key, base + mid * size); - if (result < 0) - end = mid; - else if (result > 0) - start = mid + 1; - else - return (void *)base + mid * size; - } - - return NULL; -} diff --git a/xen/include/xen/compiler.h b/xen/include/xen/compiler.h index c0e0ee9f27be..2b7acdf3b188 100644 --- a/xen/include/xen/compiler.h +++ b/xen/include/xen/compiler.h @@ -12,6 +12,7 @@ #define inline __inline__ #define always_inline __inline__ __attribute__ ((__always_inline__)) +#define gnu_inline __inline__ __attribute__ ((__gnu_inline__)) #define noinline __attribute__((__noinline__)) #define noreturn __attribute__((__noreturn__)) diff --git a/xen/include/xen/lib.h b/xen/include/xen/lib.h index 076bcfb67dbb..940d23755661 100644 --- a/xen/include/xen/lib.h +++ b/xen/include/xen/lib.h @@ -192,8 +192,48 @@ void dump_execstate(struct cpu_user_regs *); void init_constructors(void); +/* + * bsearch - binary search an array of elements + * @key: pointer to item being searched for + * @base: pointer to first element to search + * @num: number of elements + * @size: size of each element + * @cmp: pointer to comparison function + * + * This function does a binary search on the given array. The + * contents of the array should already be in ascending sorted order + * under the provided comparison function. + * + * Note that the key need not have the same type as the elements in + * the array, e.g. key could be a string and the comparison function + * could compare the string with the struct's name field. However, if + * the key and elements in the array are of the same type, you can use + * the same comparison function for both sort() and bsearch(). + */ +#ifndef BSEARCH_IMPLEMENTATION +extern gnu_inline +#endif void *bsearch(const void *key, const void *base, size_t num, size_t size, - int (*cmp)(const void *key, const void *elt)); + int (*cmp)(const void *key, const void *elt)) +{ + size_t start = 0, end = num; + int result; + + while ( start < end ) + { + size_t mid = start + (end - start) / 2; + + result = cmp(key, base + mid * size); + if ( result < 0 ) + end = mid; + else if ( result > 0 ) + start = mid + 1; + else + return (void *)base + mid * size; + } + + return NULL; +} #endif /* __ASSEMBLY__ */ diff --git a/xen/lib/Makefile b/xen/lib/Makefile index b469d2dff7b8..122eeb3d327b 100644 --- a/xen/lib/Makefile +++ b/xen/lib/Makefile @@ -1,6 +1,7 @@ obj-y += ctors.o obj-$(CONFIG_X86) += x86/ +lib-y += bsearch.o lib-y += ctype.o lib-y += list-sort.o lib-y += parse-size.o diff --git a/xen/lib/bsearch.c b/xen/lib/bsearch.c new file mode 100644 index 000000000000..149f7feafd1f --- /dev/null +++ b/xen/lib/bsearch.c @@ -0,0 +1,13 @@ +/* + * A generic implementation of binary search for the Linux kernel + * + * Copyright (C) 2008-2009 Ksplice, Inc. + * Author: Tim Abbott + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License as + * published by the Free Software Foundation; version 2. + */ + +#define BSEARCH_IMPLEMENTATION +#include