From patchwork Mon Feb 1 09:26:12 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: vijayak@caviumnetworks.com X-Patchwork-Id: 8177341 Return-Path: X-Original-To: patchwork-xen-devel@patchwork.kernel.org Delivered-To: patchwork-parsemail@patchwork2.web.kernel.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.136]) by patchwork2.web.kernel.org (Postfix) with ESMTP id 023FABEEE5 for ; Mon, 1 Feb 2016 09:33:24 +0000 (UTC) Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id 052272041D for ; Mon, 1 Feb 2016 09:33:23 +0000 (UTC) Received: from lists.xen.org (lists.xenproject.org [50.57.142.19]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id E5FA42041A for ; Mon, 1 Feb 2016 09:33:21 +0000 (UTC) Received: from localhost ([127.0.0.1] helo=lists.xen.org) by lists.xen.org with esmtp (Exim 4.72) (envelope-from ) id 1aQAoQ-0006og-DY; Mon, 01 Feb 2016 09:30:22 +0000 Received: from mail6.bemta5.messagelabs.com ([195.245.231.135]) by lists.xen.org with esmtp (Exim 4.72) (envelope-from ) id 1aQAm6-0006eC-IK for xen-devel@lists.xen.org; Mon, 01 Feb 2016 09:27:58 +0000 Received: from [85.158.139.211] by server-10.bemta-5.messagelabs.com id F6/02-17090-D152FA65; Mon, 01 Feb 2016 09:27:57 +0000 X-Env-Sender: Vijaya.Kumar@caviumnetworks.com X-Msg-Ref: server-11.tower-206.messagelabs.com!1454318876!19414136!1 X-Originating-IP: [157.56.110.60] X-SpamReason: No, hits=0.0 required=7.0 tests= X-StarScan-Received: X-StarScan-Version: 7.35.1; banners=-,-,- X-VirusChecked: Checked Received: (qmail 39106 invoked from network); 1 Feb 2016 09:27:56 -0000 Received: from mail-bn1on0060.outbound.protection.outlook.com (HELO na01-bn1-obe.outbound.protection.outlook.com) (157.56.110.60) by server-11.tower-206.messagelabs.com with AES256-SHA256 encrypted SMTP; 1 Feb 2016 09:27:56 -0000 Received: from cavium-Vostro-2520.caveonetworks.com (111.93.218.67) by BN3PR0701MB1688.namprd07.prod.outlook.com (10.163.39.154) with Microsoft SMTP Server (TLS) id 15.1.396.15; Mon, 1 Feb 2016 09:27:44 +0000 From: To: , , , , , Date: Mon, 1 Feb 2016 14:56:12 +0530 Message-ID: <1454318798-31913-3-git-send-email-vijayak@caviumnetworks.com> X-Mailer: git-send-email 1.7.9.5 In-Reply-To: <1454318798-31913-1-git-send-email-vijayak@caviumnetworks.com> References: <1454318798-31913-1-git-send-email-vijayak@caviumnetworks.com> MIME-Version: 1.0 X-Originating-IP: [111.93.218.67] X-ClientProxiedBy: BM1PR01CA0026.INDPRD01.PROD.OUTLOOK.COM (25.163.198.161) To BN3PR0701MB1688.namprd07.prod.outlook.com (25.163.39.154) X-Microsoft-Exchange-Diagnostics: 1; BN3PR0701MB1688; 2:R42W/ivmE4Y+Zi0CvCxcWBTn3AUC0OiHipjDT/AMrlRbfE7YavUQvMU44ewclPjuY6t5jj4DoTDa9VFMWwBZBgpBicZeVp8Eh2lTba/qqdL/GhHRdPIFRzmuHVnD/4ZnZ2r6UWdpygi69oB4FrKE0A==; 3:LWLvCGAwkEnLeR49s5mOOrVBnC+u5Y2fgU9U32wMcxDPYWNrPZOEutvupOjI9evaxuecD8b6zOSHcBih9loCd70bmgaVkJYcOyjFYMV05Qfao+N29UedXhsr3AVCb21G; 25:Lv8bY3ThdFEIq/c58uuo3SE09EBgTnlHSz1vudsoG/HNOonhXnthCTznqFJWYNb+/WuDyyPLArHrT8QrHIdHxIOZzhZs/6E2ieWetnsSOsNAHY+A+NwyH9bReoNW18cCF/gnlFpgJQIJNzeBYBObQRSHRu9D7BRaLAA2JZu1Vau9CQA8WbV2ArLuQV5CU+nTDHuaXdkdXDOKj83xQtHWQTd4K5AlvXWvEBcuZ7YvMdYso1dLK6SmQvYfuTtTC6Od X-Microsoft-Antispam: UriScan:;BCL:0;PCL:0;RULEID:;SRVR:BN3PR0701MB1688; X-MS-Office365-Filtering-Correlation-Id: 41b95e91-01b8-41ca-7313-08d32ae9f6eb X-Microsoft-Exchange-Diagnostics: 1; BN3PR0701MB1688; 20:ZOQq+8QroEsC5kWklrUafrAC4mDrMWULohOtW5AOVQcTNG4AfhLdMl8JH6TWrEr0BTaNZ9C8OP/ODL+fQb2ZM4hqor8ouXWozdBTgaiKBh0F3WrEUChs792KxEHeg5mMJk1tDbGjJHQgQxJUrlFELn9UHdulAj692A5XAVOUudS4cAoXbU3aaLm94Rd4gSN13OC3nfGfpzhdNOjRQiIzVrLmsi2eR+Gvn6+D3w3YaBylAbuHkcmB/TKHHw8Fov1WWK/YJK4f72OYis0BG9zRc+Pws3lNvYmzRxaftKTo+4WAULzgISl6WIK8c1z+/ZFMIB3nQsQTTSgCY1AEhqyY6BK83fzYubLBjkq7qo72FkqC9Myi6WtxSrh6X4zb3LNM+I7PVXQ0IpVz23HNbN9Q1/l+uvzEf0fFhug0jJN0iRd5yupdSy0IvACL3PRsPpNbt45tzRcB/nPWBpn14lQ4jV8OePMDDggXbuRoDgqpKg7bZ+rbvKPsLs7qUVYKK6cSwnR4gYpZTqlDJ09R7/wg/f7kHCAGcDPErrPPwHaSiYoQUWzJOOlTzYaWiyMzwKY7ErQgNukqsMMrbbbPe+xYErH17wFD1PQukHBrzhOPGvc= X-Microsoft-Antispam-PRVS: X-Exchange-Antispam-Report-Test: UriScan:; X-Exchange-Antispam-Report-CFA-Test: BCL:0; PCL:0; RULEID:(601004)(2401047)(5005006)(8121501046)(3002001)(10201501046); SRVR:BN3PR0701MB1688; BCL:0; PCL:0; RULEID:; SRVR:BN3PR0701MB1688; X-Microsoft-Exchange-Diagnostics: 1; BN3PR0701MB1688; 4:PjJvPitsuy6V9WR6/b86emIl0EnIbAuXXhqYAU3Klo7GaKDqjGXzLOch9rwfgJPViHEWW9Q1MgHPDYm40i3fpheMOwUwrTIR2ti+iOcf3XePt61VBkhM5tVBVu+I0/JLsKhlCA9fRNcen2jVL2okd5U51F8fIJeiH2KFIy52PS/y+MT2peOn7wyGf5yMcdx5HM41rE+fL+rFpR/9kIkGpEQH3C6MOgatQSVkQZV0D3nltRuK3ymDMwEx0bukYz8zbA8ugc5dwkB0xUVTcyg7aw6tN1u05cjZpQV/UdCRmMBdZSPewmZJe6jO1EVm+QTYcTKi3c5n5WR4pM802wXoiTufRSLfu/0ERiBdwgQNORu6GQVbpsOgwnmjAwau8JJp X-Forefront-PRVS: 0839D067E7 X-Forefront-Antispam-Report: SFV:NSPM; SFS:(10009020)(6009001)(3846002)(5009440100003)(586003)(1096002)(76176999)(50986999)(36756003)(189998001)(92566002)(5004730100002)(2950100001)(229853001)(50226001)(87976001)(86152002)(2201001)(5001960100002)(77096005)(53416004)(48376002)(19580395003)(19580405001)(5003940100001)(5001770100001)(42186005)(33646002)(66066001)(47776003)(2906002)(2876002)(4326007)(122386002)(3470700001)(5008740100001)(50466002)(40100003)(7099028)(7059030)(2004002)(2101003); DIR:OUT; SFP:1101; SCL:1; SRVR:BN3PR0701MB1688; H:cavium-Vostro-2520.caveonetworks.com; FPR:; SPF:None; MLV:sfv; LANG:en; X-Microsoft-Exchange-Diagnostics: =?us-ascii?Q?1; BN3PR0701MB1688; 23:dUHbdZvZRG/sVcvnVu6hKUcAmyy6Y7R1257wBX5?= =?us-ascii?Q?w+7EZgBwAe4+GYF9l3QTXkuGiNdvRZABmC9pOV3HAxpuPZzyJ4HUR455ZciR?= =?us-ascii?Q?R81Omb1gc/PIWCKTextP/2/azuNRb5j1odrYQObWKoGeXy0g4pmdy+MS2lRv?= =?us-ascii?Q?FqaB4M7cJfwN1imj+Up8hc1SlUvuH08UgeIf4vDJ7u2gMZOwPQ8aubKb6S0X?= =?us-ascii?Q?1IDbMG2BF2tQUBna4oW+27ia9gNbf/gEpnTCUUYOOWwsgpxUr8n6bBx6cXNn?= =?us-ascii?Q?hLUGmYCQ1LEzqHnSFiV+FX3pVC3sqgfuBj13d67qSaDJIRFF8dYM7ACRi/zi?= =?us-ascii?Q?qvyEBndm+2Di1wu3FgWDSn/ns/4YwQqRyJzQAyfZjWlGLzOvPB0IUdbYI8Y4?= =?us-ascii?Q?WfzehY3W4xjr9PeISUV7SfPMBrliZrZ9Rp9SAEuRr+5gXRGUWgsOogtk9Ghz?= =?us-ascii?Q?Pzfdy3dK8oSIHEsBb7GdifZx5G+D0JpVcOjuHy6QfhWQcwmdPVCLOv1P7oJQ?= =?us-ascii?Q?f4sY0NJNVZzu3h6ov3ArgWv/XfXl7k716eSgq/s949JQSG5VZmHcKWhFPht9?= =?us-ascii?Q?h6FLR/o+mYsP2Mnv0fP9YFQhWGYePM5PrbbKPLZly+AJZpsXC9y8JMFJfr3P?= =?us-ascii?Q?KezRvDxqXvh+wC5FQqiaOjL7TEHeTYRBE0yZJPI43piH/QHJ8ZSE6d8k0izK?= =?us-ascii?Q?YjinACzAJ44GQW8y1qfPm11vykk6NVXNEF9w6GQfRbN2clvOZTVqSvQGbQfd?= =?us-ascii?Q?0Z9ZTwyfwcOrb3js4nJb4EY5srhO/862DS0jZOZyDCCsELdIpR2NXEbStuTs?= =?us-ascii?Q?unE3iSoellMZV7aTxbvMgSpJTcruZNAvVYCJ9RuUgkMz9+Clfsn3+mRrbrsh?= =?us-ascii?Q?NNjr7O2pw30sqMeLfdLH3nTDLbaNkEXaE3hIhKevKWehXbBWfHc/3pvR0HCg?= =?us-ascii?Q?HYsp3d0h09V6dEUQD6SO7GkHMqIrSjp4B5Jwntxkv6O+g3+3bW3dDjzrn3of?= =?us-ascii?Q?VRvCJksa/0ExwpczvrNT1OoUQ867RH9XDWCJ2o9M4QP9tjkP5P+lo4KtfFuj?= =?us-ascii?Q?YzS+D7iI35HRd2aQRbOaif7Audi1q/DNTy2kssjieXi0MgLM2zw=3D=3D?= X-Microsoft-Exchange-Diagnostics: 1; BN3PR0701MB1688; 5:QVW/BYQ3Cj1EoxoQ6598SaeOSDHRlumxKRZsKTPNa2RZ24WVglmtjNN7qon3YiE2g6LT3Ex4opLny0Ct9DU/2lGdEL0ixTA4JrZKHK3gRVh8a1NtuAA/+tkUPn6VOdUn6/+PodUQRz+Lmt9YrQVYdw==; 24:ZrAQ2tR9OfmVJu4b36rx/j9qNomqDMFymqj92kL/YsZ+Hm3ciLTuPsuf+hIQD6WHYp9+m3bIduarK9TnKCOt5BeZjgTc0Ec25NbTQyMNupc= SpamDiagnosticOutput: 1:23 SpamDiagnosticMetadata: NSPM X-OriginatorOrg: caviumnetworks.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 01 Feb 2016 09:27:44.9049 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-Transport-CrossTenantHeadersStamped: BN3PR0701MB1688 X-Mailman-Approved-At: Mon, 01 Feb 2016 09:30:20 +0000 Cc: Keir Fraser , Ian Campbell , vijay.kilari@gmail.com, Prasun.Kapoor@caviumnetworks.com, manish.jaggi@caviumnetworks.com, Ian Jackson , Jan Beulich , Vijaya Kumar K Subject: [Xen-devel] [PATCH v8 02/28] xen: Add log2 functionality X-BeenThere: xen-devel@lists.xen.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: xen-devel-bounces@lists.xen.org Errors-To: xen-devel-bounces@lists.xen.org X-Spam-Status: No, score=-4.2 required=5.0 tests=BAD_ENC_HEADER,BAYES_00, RCVD_IN_DNSWL_MED, UNPARSEABLE_RELAY autolearn=unavailable version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on mail.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Vijaya Kumar K log2 helper apis are ported from linux from commit 13c07b0286d340275f2d97adf085cecda37ede37 (linux/log2.h: Fix rounddown_pow_of_two(1)) Changes made for xen are: - Only required functionality is retained - Replace fls_long with flsl Signed-off-by: Vijaya Kumar K Acked-by: Jan Beulich CC: Ian Campbell CC: Ian Jackson CC: Jan Beulich CC: Keir Fraser CC: Tim Deegan --- v4: - Only retained required functionality - Replaced fls_long with flsl - Removed fls_long implementation in bitops.h in v3 version --- xen/include/xen/log2.h | 167 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 167 insertions(+) diff --git a/xen/include/xen/log2.h b/xen/include/xen/log2.h new file mode 100644 index 0000000..86bd861 --- /dev/null +++ b/xen/include/xen/log2.h @@ -0,0 +1,167 @@ +/* + * Copyright (C) 2006 Red Hat, Inc. All Rights Reserved. + * Written by David Howells (dhowells@redhat.com) + * + * 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; either version + * 2 of the License, or (at your option) any later version. + */ + +#ifndef _XEN_LOG2_H +#define _XEN_LOG2_H + +#include +#include + +/* + * deal with unrepresentable constant logarithms + */ +extern __attribute__((const)) +int ____ilog2_NaN(void); + +/* + * non-constant log of base 2 calculators + * - the arch may override these in asm/bitops.h if they can be implemented + * more efficiently than using fls() and fls64() + * - the arch is not required to handle n==0 if implementing the fallback + */ +static inline __attribute__((const)) +int __ilog2_u32(u32 n) +{ + return fls(n) - 1; +} + +static inline __attribute__((const)) +int __ilog2_u64(u64 n) +{ + return flsl(n) - 1; +} + +/* + * round up to nearest power of two + */ +static inline __attribute__((const)) +unsigned long __roundup_pow_of_two(unsigned long n) +{ + return 1UL << flsl(n - 1); +} + +/** + * ilog2 - log of base 2 of 32-bit or a 64-bit unsigned value + * @n - parameter + * + * constant-capable log of base 2 calculation + * - this can be used to initialise global variables from constant data, hence + * the massive ternary operator construction + * + * selects the appropriately-sized optimised version depending on sizeof(n) + */ +#define ilog2(n) \ +( \ + __builtin_constant_p(n) ? ( \ + (n) < 1 ? ____ilog2_NaN() : \ + (n) & (1ULL << 63) ? 63 : \ + (n) & (1ULL << 62) ? 62 : \ + (n) & (1ULL << 61) ? 61 : \ + (n) & (1ULL << 60) ? 60 : \ + (n) & (1ULL << 59) ? 59 : \ + (n) & (1ULL << 58) ? 58 : \ + (n) & (1ULL << 57) ? 57 : \ + (n) & (1ULL << 56) ? 56 : \ + (n) & (1ULL << 55) ? 55 : \ + (n) & (1ULL << 54) ? 54 : \ + (n) & (1ULL << 53) ? 53 : \ + (n) & (1ULL << 52) ? 52 : \ + (n) & (1ULL << 51) ? 51 : \ + (n) & (1ULL << 50) ? 50 : \ + (n) & (1ULL << 49) ? 49 : \ + (n) & (1ULL << 48) ? 48 : \ + (n) & (1ULL << 47) ? 47 : \ + (n) & (1ULL << 46) ? 46 : \ + (n) & (1ULL << 45) ? 45 : \ + (n) & (1ULL << 44) ? 44 : \ + (n) & (1ULL << 43) ? 43 : \ + (n) & (1ULL << 42) ? 42 : \ + (n) & (1ULL << 41) ? 41 : \ + (n) & (1ULL << 40) ? 40 : \ + (n) & (1ULL << 39) ? 39 : \ + (n) & (1ULL << 38) ? 38 : \ + (n) & (1ULL << 37) ? 37 : \ + (n) & (1ULL << 36) ? 36 : \ + (n) & (1ULL << 35) ? 35 : \ + (n) & (1ULL << 34) ? 34 : \ + (n) & (1ULL << 33) ? 33 : \ + (n) & (1ULL << 32) ? 32 : \ + (n) & (1ULL << 31) ? 31 : \ + (n) & (1ULL << 30) ? 30 : \ + (n) & (1ULL << 29) ? 29 : \ + (n) & (1ULL << 28) ? 28 : \ + (n) & (1ULL << 27) ? 27 : \ + (n) & (1ULL << 26) ? 26 : \ + (n) & (1ULL << 25) ? 25 : \ + (n) & (1ULL << 24) ? 24 : \ + (n) & (1ULL << 23) ? 23 : \ + (n) & (1ULL << 22) ? 22 : \ + (n) & (1ULL << 21) ? 21 : \ + (n) & (1ULL << 20) ? 20 : \ + (n) & (1ULL << 19) ? 19 : \ + (n) & (1ULL << 18) ? 18 : \ + (n) & (1ULL << 17) ? 17 : \ + (n) & (1ULL << 16) ? 16 : \ + (n) & (1ULL << 15) ? 15 : \ + (n) & (1ULL << 14) ? 14 : \ + (n) & (1ULL << 13) ? 13 : \ + (n) & (1ULL << 12) ? 12 : \ + (n) & (1ULL << 11) ? 11 : \ + (n) & (1ULL << 10) ? 10 : \ + (n) & (1ULL << 9) ? 9 : \ + (n) & (1ULL << 8) ? 8 : \ + (n) & (1ULL << 7) ? 7 : \ + (n) & (1ULL << 6) ? 6 : \ + (n) & (1ULL << 5) ? 5 : \ + (n) & (1ULL << 4) ? 4 : \ + (n) & (1ULL << 3) ? 3 : \ + (n) & (1ULL << 2) ? 2 : \ + (n) & (1ULL << 1) ? 1 : \ + (n) & (1ULL << 0) ? 0 : \ + ____ilog2_NaN() \ + ) : \ + (sizeof(n) <= 4) ? \ + __ilog2_u32(n) : \ + __ilog2_u64(n) \ + ) + +/** + * roundup_pow_of_two - round the given value up to nearest power of two + * @n - parameter + * + * round the given value up to the nearest power of two + * - the result is undefined when n == 0 + * - this can be used to initialise global variables from constant data + */ +#define roundup_pow_of_two(n) \ +( \ + __builtin_constant_p(n) ? ( \ + (n == 1) ? 1 : \ + (1UL << (ilog2((n) - 1) + 1)) \ + ) : \ + __roundup_pow_of_two(n) \ + ) + +/** + * order_base_2 - calculate the (rounded up) base 2 order of the argument + * @n: parameter + * + * The first few values calculated by this routine: + * ob2(0) = 0 + * ob2(1) = 0 + * ob2(2) = 1 + * ob2(3) = 2 + * ob2(4) = 2 + * ob2(5) = 3 + * ... and so on. + */ + +#define order_base_2(n) ilog2(roundup_pow_of_two(n)) +#endif /* _XEN_LOG2_H */