From patchwork Tue Jul 5 12:47:04 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Jan Beulich X-Patchwork-Id: 12906552 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org 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 smtp.lore.kernel.org (Postfix) with ESMTPS id 64680C43334 for ; Tue, 5 Jul 2022 12:48:17 +0000 (UTC) Received: from list by lists.xenproject.org with outflank-mailman.361160.590507 (Exim 4.92) (envelope-from ) id 1o8hyG-0004rI-7h; Tue, 05 Jul 2022 12:48:04 +0000 X-Outflank-Mailman: Message body and most headers restored to incoming version Received: by outflank-mailman (output) from mailman id 361160.590507; Tue, 05 Jul 2022 12:48:04 +0000 Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1o8hyG-0004rB-4g; Tue, 05 Jul 2022 12:48:04 +0000 Received: by outflank-mailman (input) for mailman id 361160; Tue, 05 Jul 2022 12:48:02 +0000 Received: from se1-gles-flk1-in.inumbo.com ([94.247.172.50] helo=se1-gles-flk1.inumbo.com) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1o8hyE-0004qq-9c for xen-devel@lists.xenproject.org; Tue, 05 Jul 2022 12:48:02 +0000 Received: from EUR04-HE1-obe.outbound.protection.outlook.com (mail-eopbgr70041.outbound.protection.outlook.com [40.107.7.41]) by se1-gles-flk1.inumbo.com (Halon) with ESMTPS id b3f9e874-fc60-11ec-a8e4-439420d8e422; Tue, 05 Jul 2022 14:48:01 +0200 (CEST) Received: from VE1PR04MB6560.eurprd04.prod.outlook.com (2603:10a6:803:122::25) by AM5PR04MB3089.eurprd04.prod.outlook.com (2603:10a6:206:b::28) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5353.22; Tue, 5 Jul 2022 12:47:05 +0000 Received: from VE1PR04MB6560.eurprd04.prod.outlook.com ([fe80::dfa:a64a:432f:e26b]) by VE1PR04MB6560.eurprd04.prod.outlook.com ([fe80::dfa:a64a:432f:e26b%7]) with mapi id 15.20.5395.021; Tue, 5 Jul 2022 12:47:05 +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" X-Inumbo-ID: b3f9e874-fc60-11ec-a8e4-439420d8e422 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=IifTTQEATJ5rsOs+0MYWRNiVeYOl4HmRLv/0qT4Q1/S7hNiCjoOTbtXdaxOAEtRqxx8f5CXdV1E4Z4QcrI356jNZ/BWyBVfYvqelaj+K6GYoeAdE0ANeHfUtmsL6gRVE0p41sAW3FOAPWUkDxBETeFaAtIn87TNoEznJ+zEdyMbiqJQiPV9Z4c4T4g7raW3n0QtgGojmXaW9OOlYjgmd5/NgnNREqjZJYlmxwsNVZXw80eYWsg7/WdrO3b44mQAkK33aYHzIiOxPiAu+acFZTgg6eMOn2fFCGqrjbQq2eHuER5pH0pvRoYDgU0B6Quwsvgbl79rCDrIOl5vNrqce4g== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=nzH6EFMW+e3+Xs7xettJZg30tav9rjlAdUzEqGTjlFU=; b=eNuEDpnJGvKgefB/KMfXzNBxiCUJB5nU/VNiWl+aHiG5xI+WxDOtlJbg+9zOdw6xU6nsjS5xuYnCVxf50oVlSMbJqjGJiSQDUChwjcTEteWZ+hu6fWLqUKrww5vgS9yggj1Jyj40XndtoxgnFARiUECqD6BbI2d5XelcZ0OtuZpVg7A6yc1boX70L58LBfOebaix1w2mu4xzHx4Bwdh6nHiqgrPQXnN+iQLdx6cRz4b9fVAlRFohrBTyastvOAiYofnXE0Vsz/6G7gTsT0G35sJ1/hmC6Sq7iuGBr03lUKE7wQLfjpNK7pw0LGEiFHloOv1UEFjdH8gSNF7RvxV41w== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=suse.com; dmarc=pass action=none header.from=suse.com; dkim=pass header.d=suse.com; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=nzH6EFMW+e3+Xs7xettJZg30tav9rjlAdUzEqGTjlFU=; b=vZrmrFR22i1aPqYekL2ea2xnPgR619OXDSqa6tUwtORrSK6F/h9v2zLzmGevDHSs7Sf9TmRfWAyzosXSqY1tSA5z3hfobEoLXi3+L5VHyDOufS+0E4IKEj3NBy+DQAomK8qRA5Iv+ITd3cxCMNXxEoeFas6aj5ud9r7jYoQ6w/tDj8ndREyafbRXV04X1Q/u4H9SgAcoekVJRlm4YNSfBQZ/S+nmK1cFUy7b3ea1WfaZuww+Y0C7x+/Aa26iC9pwh58t4E4fuVh2mxy1pM659z+eiGXwmsrNTOKdsUOkLHW8qum5VRS94tgwLmbEv7GI7F3zg09F6C3nGf/WB7jHBg== Authentication-Results: dkim=none (message not signed) header.d=none;dmarc=none action=none header.from=suse.com; Message-ID: <1ff53db0-088e-ec08-b757-b03639c09432@suse.com> Date: Tue, 5 Jul 2022 14:47:04 +0200 User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101 Thunderbird/91.11.0 Subject: [PATCH v7 07/14] x86: introduce helper for recording degree of contiguity in page tables Content-Language: en-US From: Jan Beulich To: "xen-devel@lists.xenproject.org" Cc: Andrew Cooper , Paul Durrant , =?utf-8?q?Roger_Pau_Monn=C3=A9?= References: <4c9d4b32-d4db-3a4f-fe92-6022e63c3f82@suse.com> In-Reply-To: <4c9d4b32-d4db-3a4f-fe92-6022e63c3f82@suse.com> X-ClientProxiedBy: FR0P281CA0102.DEUP281.PROD.OUTLOOK.COM (2603:10a6:d10:a9::18) To VE1PR04MB6560.eurprd04.prod.outlook.com (2603:10a6:803:122::25) MIME-Version: 1.0 X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: f4e76a39-2084-4ed2-6ff9-08da5e84771b X-MS-TrafficTypeDiagnostic: AM5PR04MB3089:EE_ X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: KHX2nzvOmr4qFPnYicQka8unMweegtMNmAcJzW2JQRf4PSnFPmvUIrzPD/cyuolqQCn89da4Cjai+6/GaPpt8MbH3mwlZsyrErAgc0zH0N8ELDpGIHNuvuL6Sci5E3CzpEEMgy4/XVRj+dTMZEyqoGAZh7K9wettedRRHfTs/qvJssmkMDbm7Yj7HadSLcU5rfqTQN/T/WTceeUTjKJREqPQbwNW4od5JHrvP4xkvZQRPdy4auDjNv4bYF4NVvNRW+xr6EYPTG9fV48jL3oLyJQT6lxACLw0REaCO3PqLGQlUCjIpR+bUVx841AK0ONCq6Sj+OtyhBD9cJFnWreu+IsBa8zgQHCvgTdh6f9CCmYTVdWcbclPJDWlgndjoAQZDu2VrlLLt/GJ65sGTTh1t7owJPN/0uwWYMmR8vGsvP0Ji1HQEA7Gdn5sjp6rqTG0SPy/KPT5R4KvFd6VtffZiuygA3wcoIoELV5Y+KjKUVoeVwIFMGm+8QhjFLWX6x+wKlMaSDPAG8BRzu3LZiGtjhvbxKRJASyWDhBmT1CTgOmOb0fsNFIrPp1lfBHZNcyCf1AzrFUBv319o2rTolGsqGJvZBLeBwYvBnAOviYooIn5D3eHpLkPey7x2FIAI2lX1ut3gHBzA6NqmlPmAfF06CQmh+SbdKeUK6BGA3qVXEAypLHKsXjVpg75tzPBeMQNAhvQDhHEqTMBVvnPCQwuc72DzGDx5NJQuWt18n6Cm7cHgF7RoYwrJvvZ8Fsps/C5W/pMiq1nMtE3gOTEg2Fiv2oezf8kNTZ8ACs7INk97K5gRQN0WOhSMuIsbzAgQzsDA1Ge3Ulyqacw9EUlAAqW/TjsUIqEH0zfTcTEBP+D4FE= X-Forefront-Antispam-Report: CIP:255.255.255.255;CTRY:;LANG:en;SCL:1;SRV:;IPV:NLI;SFV:NSPM;H:VE1PR04MB6560.eurprd04.prod.outlook.com;PTR:;CAT:NONE;SFS:(13230016)(366004)(396003)(39860400002)(376002)(136003)(346002)(478600001)(8936002)(5660300002)(6486002)(86362001)(31696002)(2906002)(6916009)(54906003)(316002)(41300700001)(2616005)(66476007)(66556008)(66946007)(186003)(83380400001)(6506007)(31686004)(38100700002)(36756003)(4326008)(8676002)(26005)(6512007)(45980500001)(43740500002);DIR:OUT;SFP:1101; X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-MessageData-0: =?utf-8?q?JvYodMl2o/JoFMmlaV7Y1q3BIDQR?= =?utf-8?q?Ba60yJUR/gCDzoFBPl8Er5HyEmmJ/a+FQI4TNvdWrYPqNIZcYbIkiEx31mRS7zYeR?= =?utf-8?q?RF5bcAyyQ2Dp5dWPonNVBakC+5nfyRofVhz0VILPia7B4YOhSej98okyGvMOX9fPV?= =?utf-8?q?1eayYKN4TEfa66C1rcyB/hRLzbHho0FzvBKnoXeWx3hsIAAx3eLBaJu3OYc8jzNAi?= =?utf-8?q?TupaT/Qn2v1nDBrITx+gjsJDkPG30BwZty/srXN25Capndb+NpWkce5maFC2S4v7D?= =?utf-8?q?Rl2emU86k1fTS4/qEKMyvEWM2+QHNtlZm3CY5181qXFLC4CsXV0KM0d1taOjA59Km?= =?utf-8?q?LHWxv2eGYDfwBxGQ70xaKQ/P31HLzUI5jbV+g021spS9iiuVZHjwbj8LMbJbzgT7n?= =?utf-8?q?AmMn7jgu8KtmB7GU/LAtqkKpuAEYp6Eh8G+LmpteSnWxFwNZFMkhAAizrd7MV/wH6?= =?utf-8?q?tYLwngOjiyrFsxv1PEaTPCkRc1HTKz/9bkIXfF9EA6KUCQzo8m9t9h7z4ITYWZFuS?= =?utf-8?q?1p+/4/ol7vkSHXaoxhkNMEHDtLYWBB+sBH1Va+sS2r0k7C94C+CrkAKX/zw34ZCv1?= =?utf-8?q?tUZWr8IM+1IZWz/ZdKmu0lQYb0+lTE6u3qBIcKYJnHT05XYLwHhX1mgsD17Zlw5J8?= =?utf-8?q?9MLYlof9He1mtZi7KbmnBjtQmK1m5Ro9DPyS6wcADgVi8Pn456lvz+hcfCleJfZKf?= =?utf-8?q?VjVejqCaWS+fLd3M/H0EXsEp5kDl2MNvxdcBDjngtKqfy9GsfVXDMTMo7ZCdhoiZs?= =?utf-8?q?2o+81b5KUheAM6KCgOOZl+3wI1poH4gEBOzZzbpGxt1Q9UjwK9sDRM2guQSVVXH8N?= =?utf-8?q?1mi8uQ7TRsDXlLMEgMcMt1aQzbxmdTqs4OHwlskHQqSkBwAoCqvWPiLte8pPoxF5v?= =?utf-8?q?rysOT48EEsV54+b0VKNACw65rHP0bfrEXy2sHwviwd0lbENuEEY+xM72hZG5QicDS?= =?utf-8?q?nxqFnchdzgvdluBh3rxmqzLqPyKLg36qfipTj/VmuS/z4zOVP8t0HmXYMA86N0Nfa?= =?utf-8?q?ccF4sp1IPHYvAyZPkY5bHegKl8PIT4pswJuW0IIVbZiGVCVBK1VoHon6tnBEgx4aT?= =?utf-8?q?07iAaGbr07wIXX+dqI75we0sMHDwsGb+XJuPZjFEY5bslfgBeKeyvuJ0cnGz6kacf?= =?utf-8?q?tViSJPEmQEmx7RaByHShG+wNOdO8Ib/JygvQtkFH9nVNBPPHcIf1PzspUotzNXR8M?= =?utf-8?q?Vu8LQaTpREjC1stZMjudoA+awCJbBrZzEVqE4zy4UXKXw3Um6GEv+dJJQL7RaVCub?= =?utf-8?q?Bd6SueNLttBwO4r5kIGFmvcd1t6WE1hv7ZhOX1RIj6SFpn65fLbC6xcJ06/2Ooae/?= =?utf-8?q?t+fPSxoOSKvsKVUZBMvDaRnHI4hrvkZao48pVDCWkAFLpAEPxr/giVsHesnaLVDoO?= =?utf-8?q?twOnMl0rwHubrPCAZ5zCNbvWweAcAhs5BTQGGFch5c7t26OGD37LJP5M0Pi0kXq2x?= =?utf-8?q?FR1iNQJNEt0QJaheU16iWSCiqq9HnVPykavw6eLW6RacruHydExXwpmLAXj/2vIJc?= =?utf-8?q?zfiESL3XTyU1?= X-OriginatorOrg: suse.com X-MS-Exchange-CrossTenant-Network-Message-Id: f4e76a39-2084-4ed2-6ff9-08da5e84771b X-MS-Exchange-CrossTenant-AuthSource: VE1PR04MB6560.eurprd04.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-OriginalArrivalTime: 05 Jul 2022 12:47:05.4733 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-CrossTenant-Id: f7a17af6-1c5c-4a36-aa8b-f5be247aa4ba X-MS-Exchange-CrossTenant-MailboxType: HOSTED X-MS-Exchange-CrossTenant-UserPrincipalName: 6E6aurzClZBOFWPGA7ImmFoHM3ea5vP1JrKR/Exhzt3El9FL9kHTqJorPmT0LOf/WCUMXKTmurzr5NYFOKbg+w== X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM5PR04MB3089 This is a re-usable helper (kind of a template) which gets introduced without users so that the individual subsequent patches introducing such users can get committed independently of one another. See the comment at the top of the new file. To demonstrate the effect, if a page table had just 16 entries, this would be the set of markers for a page table with fully contiguous mappings: index 0 1 2 3 4 5 6 7 8 9 A B C D E F marker 4 0 1 0 2 0 1 0 3 0 1 0 2 0 1 0 "Contiguous" here means not only present entries with successively increasing MFNs, each one suitably aligned for its slot, but also a respective number of all non-present entries. Signed-off-by: Jan Beulich Reviewed-by: Roger Pau Monné Reviewed-by: Paul Durrant --- v5: Bail early from step 1 if possible. Arrange for consumers who are just after CONTIG_{LEVEL_SHIFT,NR}. Extend comment. v3: Rename function and header. Introduce IS_CONTIG(). v2: New. --- /dev/null +++ b/xen/arch/x86/include/asm/pt-contig-markers.h @@ -0,0 +1,110 @@ +#ifndef __ASM_X86_PT_CONTIG_MARKERS_H +#define __ASM_X86_PT_CONTIG_MARKERS_H + +/* + * Short of having function templates in C, the function defined below is + * intended to be used by multiple parties interested in recording the + * degree of contiguity in mappings by a single page table. + * + * Scheme: Every entry records the order of contiguous successive entries, + * up to the maximum order covered by that entry (which is the number of + * clear low bits in its index, with entry 0 being the exception using + * the base-2 logarithm of the number of entries in a single page table). + * While a few entries need touching upon update, knowing whether the + * table is fully contiguous (and can hence be replaced by a higher level + * leaf entry) is then possible by simply looking at entry 0's marker. + * + * Prereqs: + * - CONTIG_MASK needs to be #define-d, to a value having at least 4 + * contiguous bits (ignored by hardware), before including this file (or + * else only CONTIG_LEVEL_SHIFT and CONTIG_NR will become available), + * - page tables to be passed to the helper need to be initialized with + * correct markers, + * - not-present entries need to be entirely clear except for the marker. + */ + +/* This is the same for all anticipated users, so doesn't need passing in. */ +#define CONTIG_LEVEL_SHIFT 9 +#define CONTIG_NR (1 << CONTIG_LEVEL_SHIFT) + +#ifdef CONTIG_MASK + +#include +#include +#include + +#define GET_MARKER(e) MASK_EXTR(e, CONTIG_MASK) +#define SET_MARKER(e, m) \ + ((void)((e) = ((e) & ~CONTIG_MASK) | MASK_INSR(m, CONTIG_MASK))) + +#define IS_CONTIG(kind, pt, i, idx, shift, b) \ + ((kind) == PTE_kind_leaf \ + ? (((pt)[i] ^ (pt)[idx]) & ~CONTIG_MASK) == (1ULL << ((b) + (shift))) \ + : !((pt)[i] & ~CONTIG_MASK)) + +enum PTE_kind { + PTE_kind_null, + PTE_kind_leaf, + PTE_kind_table, +}; + +static bool pt_update_contig_markers(uint64_t *pt, unsigned int idx, + unsigned int level, enum PTE_kind kind) +{ + unsigned int b, i = idx; + unsigned int shift = (level - 1) * CONTIG_LEVEL_SHIFT + PAGE_SHIFT; + + ASSERT(idx < CONTIG_NR); + ASSERT(!(pt[idx] & CONTIG_MASK)); + + /* Step 1: Reduce markers in lower numbered entries. */ + while ( i ) + { + b = find_first_set_bit(i); + i &= ~(1U << b); + if ( GET_MARKER(pt[i]) <= b ) + break; + SET_MARKER(pt[i], b); + } + + /* An intermediate table is never contiguous with anything. */ + if ( kind == PTE_kind_table ) + return false; + + /* + * Present entries need in-sync index and address to be a candidate + * for being contiguous: What we're after is whether ultimately the + * intermediate table can be replaced by a superpage. + */ + if ( kind != PTE_kind_null && + idx != ((pt[idx] >> shift) & (CONTIG_NR - 1)) ) + return false; + + /* Step 2: Check higher numbered entries for contiguity. */ + for ( b = 0; b < CONTIG_LEVEL_SHIFT && !(idx & (1U << b)); ++b ) + { + i = idx | (1U << b); + if ( !IS_CONTIG(kind, pt, i, idx, shift, b) || GET_MARKER(pt[i]) != b ) + break; + } + + /* Step 3: Update markers in this and lower numbered entries. */ + for ( ; SET_MARKER(pt[idx], b), b < CONTIG_LEVEL_SHIFT; ++b ) + { + i = idx ^ (1U << b); + if ( !IS_CONTIG(kind, pt, i, idx, shift, b) || GET_MARKER(pt[i]) != b ) + break; + idx &= ~(1U << b); + } + + return b == CONTIG_LEVEL_SHIFT; +} + +#undef IS_CONTIG +#undef SET_MARKER +#undef GET_MARKER +#undef CONTIG_MASK + +#endif /* CONTIG_MASK */ + +#endif /* __ASM_X86_PT_CONTIG_MARKERS_H */