From nobody Mon Feb 9 08:57:20 2026 Delivered-To: importer@patchew.org Received-SPF: pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) client-ip=192.237.175.120; envelope-from=xen-devel-bounces@lists.xenproject.org; helo=lists.xenproject.org; Authentication-Results: mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) smtp.mailfrom=xen-devel-bounces@lists.xenproject.org; dmarc=pass(p=reject dis=none) header.from=citrix.com ARC-Seal: i=1; a=rsa-sha256; t=1636653531; cv=none; d=zohomail.com; s=zohoarc; b=InEjklftbsK2dueD1OAMxR1U07K/n/ZVengaYaR0iKkVOcgbsP0xXNpYe+za0mCG59bnrMlS6dj8CMSPitLGk9Cm+84j4qh/ZriwE3WxWD7P1NUhk6JkM3wCaclJ+uwvz29zPoO2CKQRLo7ZPmlZxOEbblTqurG/X7ortB3lzT8= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1636653531; h=Content-Type:Content-Transfer-Encoding:Cc:Date:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Help:List-Unsubscribe:MIME-Version:Message-ID:References:Sender:Subject:To; bh=fprq8xIAksNErW/09yRBY5UoepxCeoe+Z+1OSXzzRbY=; b=MCYgzzRlhjxFqQunhWrEyK0YNA1uXr17pbJ2kEdeyhmvDCq616AnZb6HJu6pBOoM8ybDRo6kJ1Iy+HbEytVb9uy9a7pFqLTz/Otu5xnpKzavgt9+dSQIsvuiC8g24upGLEhqq8dML4hFd9X6Api6UdtKt0S4wtnDmHIJhh266vA= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) smtp.mailfrom=xen-devel-bounces@lists.xenproject.org; dmarc=pass header.from= (p=reject dis=none) Return-Path: Received: from lists.xenproject.org (lists.xenproject.org [192.237.175.120]) by mx.zohomail.com with SMTPS id 1636653531583490.6846607501923; Thu, 11 Nov 2021 09:58:51 -0800 (PST) Received: from list by lists.xenproject.org with outflank-mailman.224830.388351 (Exim 4.92) (envelope-from ) id 1mlEKw-00061Z-Iy; Thu, 11 Nov 2021 17:58:10 +0000 Received: by outflank-mailman (output) from mailman id 224830.388351; Thu, 11 Nov 2021 17:58:10 +0000 Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1mlEKw-00061S-Fs; Thu, 11 Nov 2021 17:58:10 +0000 Received: by outflank-mailman (input) for mailman id 224830; Thu, 11 Nov 2021 17:58:09 +0000 Received: from se1-gles-sth1-in.inumbo.com ([159.253.27.254] helo=se1-gles-sth1.inumbo.com) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1mlEKv-0005kR-6q for xen-devel@lists.xenproject.org; Thu, 11 Nov 2021 17:58:09 +0000 Received: from esa3.hc3370-68.iphmx.com (esa3.hc3370-68.iphmx.com [216.71.145.155]) by se1-gles-sth1.inumbo.com (Halon) with ESMTPS id ecce4348-4318-11ec-9787-a32c541c8605; Thu, 11 Nov 2021 18:58:07 +0100 (CET) X-Outflank-Mailman: Message body and most headers restored to incoming version 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" X-Inumbo-ID: ecce4348-4318-11ec-9787-a32c541c8605 DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=citrix.com; s=securemail; t=1636653487; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version:content-transfer-encoding; bh=wZjOooR7h3617EbhfqFJc1ylcvpSG2QwEC0bQQSIklo=; b=H184UounUCpDqJbBWjVnZhwg7Cvd38MeHcehF4gQ+47ZLLD6VjGUK3Sj D0AHlE3HdzGRMQkPClVTugIMJpx+MEmx6JNC2sezIwwQD0Ylu4WRQLQe4 gAXAowJg32tscjROYZCPwlm0spjevpmdpl1Qrz/Hrx77E1KNedrF0DL3S I=; Authentication-Results: esa3.hc3370-68.iphmx.com; dkim=none (message not signed) header.i=none IronPort-SDR: DJMeo/F80T5kkf/alFsTsShab5w4ojag5j96fmWJRUuoVF0nOYRG6bTFv4REPTw7nzPOjDXJiG yo7lOH9d8DMQKSC1S2swjdAqYyGN+1cquh91CSrXsHqqPeJD/IBAy2VFMxznZXwsKeSfBee/Gx 97L+CpZS3oPCDaoBiYteVp1W5hJ8/162HQyOW/qWGv9yBicwosirfnX+tyRtUC3z+P/rZFgpFL nr+BTBW6OgTjFxpaKndUUAvArOIO3uugmo9D2z/yLV0XRpwpIbKV4QvLqcQmscoExA7kzottqF DzZ8F8VwbrxKU67Iyw6JpB5r X-SBRS: 5.1 X-MesageID: 57653926 X-Ironport-Server: esa3.hc3370-68.iphmx.com X-Remote-IP: 162.221.156.83 X-Policy: $RELAYED IronPort-Data: A9a23:C4ryNqKjPLpZJsZwFE+RcpIlxSXFcZb7ZxGr2PjKsXjdYENS12MEy jcdXz2GPKuCamqhKI92PNvk90wCvZfTnNVnGwBlqX01Q3x08seUXt7xwmUcns+xwm8vaGo9s q3yv/GZdJhcokcxIn5BC5C5xZVG/fjgqoHUVaiUZUideSc+EH140Es6wrZg6mJVqYPR7z2l6 IuaT/L3YDdJ6xYsWo7Dw/vewP/HlK2aVAIw5jTSV9gS1LPtvyB94KYkDbOwNxPFrrx8RYZWc QphIIaRpQs19z91Yj+sfy2SnkciGtY+NiDW4pZatjTLbrGvaUXe345iXMfwZ3u7hB2Cz/Iq4 /pQv6erTAd1b4ucmboUVydHRnQW0a1uoNcrIFC6uM2XiUbHb2Ht07NlC0Re0Y8wo7gtRzsUr LpBdW5LPkvra+GemdpXTsFFgMg5IdatF4QYonx6lhnSDOo8QICFSKLPjTNd9Gpv2J0VTKyAD yYfQWs1cxLGXRIfAHIeVLt92/qzj0LvKiIN/Tp5ooJoujOOnWSdyoPFMsfRe9GMbdVYmACfv G2u11r+BhYWJdmO0w2v+3inhvLMtS7jUYdUH7q9ntZgjUeP3GUVBFsTXEGivPiiokekXpRUL El80jUqhbg/8gqsVNaVdw21pjuIswARX/JUEvYm80edx6zM+QGbC2MYCDlbZ7QOluU7WDgr3 V+hhM7yCHpkt7j9YWmG6r6eoDe2OC4UBWwPfykJSU0C+daLnW0opkuRFJA5Svfz14CrX2Grq 9yXkMQgr75Dr5Ug+LixxkvCg279gMjIEAcx2BqCCwpJ8ThFTIKiYoWp733S4vBBMJuVQzG9g ZQUpySNxLtQVM/QzURhVM1IRej0vKjdbFUwlHY2R8F5nwlB7UJPamy5DNtWAE5yevgJdjbyC KM4kVMAvcQDVJdGgEIeXm5QNyjI5fS/fTgGfqqNBjarXnSXXFbWlM2JTRTAt10BaGB2zckC1 W6zKK5A90oyB6V91yaRTOwAy7ItzS1W7TqNHs6mkUX4gefBOyH9pVI53L2mN7FRAESs+lW9z jqiH5HSl0U3vBPWPkE7DrL/3XhVdCNmVPgaWuRcd/KZIxoOJY3SI6S5/F/VQKQ8x/49vr6Rp hmVAxYEoHKi1SyvAVjbMRhLNeKwNauTWFpmZETAy37zgCN9CWtuhY9CH6YKkU4PqLY+kKUqF qZdIK1twJ1nE1z6xtjUVrGlxKQKSfhhrVjm0/ONbGdtcph+aRbO/9O4LALj+DNXVni8tNcko q3m3QTeGMJRSwNnBcfQSfSu01Lu4iRNxLMsBxPFcotJZUHh0Il2MCit3PU5FN4BdEfYzTyA2 gfIXRpB/bvRo5U4+cXijLyfq9v7CPN3G0dXRjGJ7bu/OSTA0HCkxItMDLSBcTzHDTum86S+f +RFifr7NaRfzlpNtoN9FZdtzL4/uISz9+MLkFw8ESySPVqxC75mLn2X5uV1t/VAlu1DpA+7e kOT4d0Ga7+HD9zoTQwKLw0/Y+XdifxNwmvO7e44KVnR7TNs+ObVSl1bOhSBhXAPLLZxN495k +4ttNRPtl66gxsudN2HkjpV5yKHKXlZC/crsZQTAYnKjAs3yw4dPcyAW3GuuJzfOc9RNkQKI yOPgPuQjrtR8UPObn4vGCWfxuFan5kP5EhHwVJqy45lQTYZaivbBCFszAk= IronPort-HdrOrdr: A9a23:m1QOnau0xHHIRx4Mt+A+cgtu7skDTtV00zEX/kB9WHVpmszxra 6TdZMgpGbJYVcqKRcdcL+7WJVoLUmxyXcx2/h1AV7AZniAhILLFvAA0WKK+VSJcEeSygce79 YFT0EXMqyJMbEQt6fHCWeDfOrIuOP3kpyVuQ== X-IronPort-AV: E=Sophos;i="5.87,226,1631592000"; d="scan'208";a="57653926" From: Andrew Cooper To: Xen-devel CC: Andrew Cooper , Jan Beulich , =?UTF-8?q?Roger=20Pau=20Monn=C3=A9?= , Wei Liu , Stefano Stabellini , Julien Grall , Volodymyr Babchuk , Bertrand Marquis Subject: [PATCH 3/5] xen/sort: Switch to an extern inline implementation Date: Thu, 11 Nov 2021 17:57:38 +0000 Message-ID: <20211111175740.23480-4-andrew.cooper3@citrix.com> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20211111175740.23480-1-andrew.cooper3@citrix.com> References: <20211111175740.23480-1-andrew.cooper3@citrix.com> MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable X-ZohoMail-DKIM: pass (identity @citrix.com) X-ZM-MESSAGEID: 1636653532512100004 There are exactly 3 callers of sort() in the hypervisor. Both arm callers pass in NULL for the swap function. While this might seem like an attractive option at first, it causes generic_swap() to be used whi= ch forced a byte-wise copy. Provide real swap functions which the compiler can optimise sensibly. Furthermore, use of function pointers in tight loops like that can be very = bad for performance. Implement sort() as extern inline, so the optimiser can judge whether to inline things or not. On x86, the diffstat shows how much of a better job the compiler can do when it is able to see the cmp/swap implementations. $ ../scripts/bloat-o-meter xen-syms-before xen-syms-after add/remove: 0/5 grow/shrink: 1/1 up/down: 505/-735 (-230) Function old new delta sort_exception_table 31 536 +505 u32_swap 9 - -9 generic_swap 34 - -34 cmp_ex 36 - -36 swap_ex 41 - -41 sort_exception_tables 90 38 -52 sort 563 - -563 Signed-off-by: Andrew Cooper Reviewed-by: Jan Beulich --- CC: Jan Beulich CC: Roger Pau Monn=C3=A9 CC: Wei Liu CC: Stefano Stabellini CC: Julien Grall CC: Volodymyr Babchuk CC: Bertrand Marquis --- xen/arch/arm/bootfdt.c | 9 +++++- xen/arch/arm/io.c | 9 +++++- xen/include/xen/sort.h | 55 +++++++++++++++++++++++++++++++++- xen/lib/sort.c | 80 ++--------------------------------------------= ---- 4 files changed, 72 insertions(+), 81 deletions(-) diff --git a/xen/arch/arm/bootfdt.c b/xen/arch/arm/bootfdt.c index afaa0e249b71..e318ef960386 100644 --- a/xen/arch/arm/bootfdt.c +++ b/xen/arch/arm/bootfdt.c @@ -448,6 +448,13 @@ static int __init cmp_memory_node(const void *key, con= st void *elem) return 0; } =20 +static void __init swap_memory_node(void *_a, void *_b, size_t size) +{ + struct membank *a =3D _a, *b =3D _b; + + SWAP(*a, *b); +} + /** * boot_fdt_info - initialize bootinfo from a DTB * @fdt: flattened device tree binary @@ -472,7 +479,7 @@ size_t __init boot_fdt_info(const void *fdt, paddr_t pa= ddr) * the banks sorted in ascending order. So sort them through. */ sort(bootinfo.mem.bank, bootinfo.mem.nr_banks, sizeof(struct membank), - cmp_memory_node, NULL); + cmp_memory_node, swap_memory_node); =20 early_print_info(); =20 diff --git a/xen/arch/arm/io.c b/xen/arch/arm/io.c index 729287e37c59..1a066f9ae502 100644 --- a/xen/arch/arm/io.c +++ b/xen/arch/arm/io.c @@ -80,6 +80,13 @@ static int cmp_mmio_handler(const void *key, const void = *elem) return 0; } =20 +static void swap_mmio_handler(void *_a, void *_b, size_t size) +{ + struct mmio_handler *a =3D _a, *b =3D _b; + + SWAP(*a, *b); +} + static const struct mmio_handler *find_mmio_handler(struct domain *d, paddr_t gpa) { @@ -170,7 +177,7 @@ void register_mmio_handler(struct domain *d, =20 /* Sort mmio handlers in ascending order based on base address */ sort(vmmio->handlers, vmmio->num_entries, sizeof(struct mmio_handler), - cmp_mmio_handler, NULL); + cmp_mmio_handler, swap_mmio_handler); =20 write_unlock(&vmmio->lock); } diff --git a/xen/include/xen/sort.h b/xen/include/xen/sort.h index a403652948e7..01479ea44606 100644 --- a/xen/include/xen/sort.h +++ b/xen/include/xen/sort.h @@ -3,8 +3,61 @@ =20 #include =20 +/* + * sort - sort an array of elements + * @base: pointer to data to sort + * @num: number of elements + * @size: size of each element + * @cmp: pointer to comparison function + * @swap: pointer to swap function or NULL + * + * This function does a heapsort on the given array. You may provide a + * swap function optimized to your element type. + * + * Sorting time is O(n log n) both on average and worst-case. While + * qsort is about 20% faster on average, it suffers from exploitable + * O(n*n) worst-case behavior and extra memory requirements that make + * it less suitable for kernel use. + */ +#ifndef SORT_IMPLEMENTATION +extern gnu_inline +#endif void sort(void *base, size_t num, size_t size, int (*cmp)(const void *, const void *), - void (*swap)(void *, void *, size_t)); + void (*swap)(void *, void *, size_t)) +{ + /* pre-scale counters for performance */ + size_t i =3D (num / 2) * size, n =3D num * size, c, r; + + /* heapify */ + while ( i > 0 ) + { + for ( r =3D i -=3D size; r * 2 + size < n; r =3D c ) + { + c =3D r * 2 + size; + if ( (c < n - size) && (cmp(base + c, base + c + size) < 0) ) + c +=3D size; + if ( cmp(base + r, base + c) >=3D 0 ) + break; + swap(base + r, base + c, size); + } + } + + /* sort */ + for ( i =3D n; i > 0; ) + { + i -=3D size; + swap(base, base + i, size); + for ( r =3D 0; r * 2 + size < i; r =3D c ) + { + c =3D r * 2 + size; + if ( (c < i - size) && (cmp(base + c, base + c + size) < 0) ) + c +=3D size; + if ( cmp(base + r, base + c) >=3D 0 ) + break; + swap(base + r, base + c, size); + } + } +} =20 #endif /* __XEN_SORT_H__ */ diff --git a/xen/lib/sort.c b/xen/lib/sort.c index 35ce0d7abdec..b7e78cc0e8d2 100644 --- a/xen/lib/sort.c +++ b/xen/lib/sort.c @@ -4,81 +4,5 @@ * Jan 23 2005 Matt Mackall */ =20 -#include - -static void u32_swap(void *a, void *b, size_t size) -{ - uint32_t t =3D *(uint32_t *)a; - - *(uint32_t *)a =3D *(uint32_t *)b; - *(uint32_t *)b =3D t; -} - -static void generic_swap(void *a, void *b, size_t size) -{ - char t; - - do { - t =3D *(char *)a; - *(char *)a++ =3D *(char *)b; - *(char *)b++ =3D t; - } while ( --size > 0 ); -} - -/* - * sort - sort an array of elements - * @base: pointer to data to sort - * @num: number of elements - * @size: size of each element - * @cmp: pointer to comparison function - * @swap: pointer to swap function or NULL - * - * This function does a heapsort on the given array. You may provide a - * swap function optimized to your element type. - * - * Sorting time is O(n log n) both on average and worst-case. While - * qsort is about 20% faster on average, it suffers from exploitable - * O(n*n) worst-case behavior and extra memory requirements that make - * it less suitable for kernel use. - */ - -void sort(void *base, size_t num, size_t size, - int (*cmp)(const void *, const void *), - void (*swap)(void *, void *, size_t size)) -{ - /* pre-scale counters for performance */ - size_t i =3D (num / 2) * size, n =3D num * size, c, r; - - if ( !swap ) - swap =3D (size =3D=3D 4 ? u32_swap : generic_swap); - - /* heapify */ - while ( i > 0 ) - { - for ( r =3D i -=3D size; r * 2 + size < n; r =3D c ) - { - c =3D r * 2 + size; - if ( (c < n - size) && (cmp(base + c, base + c + size) < 0) ) - c +=3D size; - if ( cmp(base + r, base + c) >=3D 0 ) - break; - swap(base + r, base + c, size); - } - } - - /* sort */ - for ( i =3D n; i > 0; ) - { - i -=3D size; - swap(base, base + i, size); - for ( r =3D 0; r * 2 + size < i; r =3D c ) - { - c =3D r * 2 + size; - if ( (c < i - size) && (cmp(base + c, base + c + size) < 0) ) - c +=3D size; - if ( cmp(base + r, base + c) >=3D 0 ) - break; - swap(base + r, base + c, size); - } - } -} +#define SORT_IMPLEMENTATION +#include --=20 2.11.0