From patchwork Tue Feb 14 13:38:13 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Paul Liu X-Patchwork-Id: 653462 Delivered-To: patch@linaro.org Received: by 2002:adf:f90f:0:0:0:0:0 with SMTP id b15csp3038032wrr; Tue, 14 Feb 2023 05:38:46 -0800 (PST) X-Google-Smtp-Source: AK7set/GYpSvW1Z4pevSp3ToK7CqJ0wLmAFk74/+lOQT+NOF60mHv+K9GrR5Q/nvGO7hKgXyhTKf X-Received: by 2002:a05:6870:d38a:b0:163:bd7f:bc27 with SMTP id k10-20020a056870d38a00b00163bd7fbc27mr1236501oag.6.1676381926698; Tue, 14 Feb 2023 05:38:46 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1676381926; cv=none; d=google.com; s=arc-20160816; b=n1l59qrNfOG8T1kx0lHMkzAq1iQa4H+JAMhT6Mnk05M/IacgTSeBnw//pRslDjHMgR WTVXzs8NLA6R0Re57qG3zAUnU90pVAPgveJdOfhD635a9y9oieJQIIQ4UWv91JJFxvDO b7xuKZhP1YhK13MeoXhcFMIUQUG8z5GjsNwowmser0UB18wq7FcUjqCadmE9pSBjcPp2 n/djmf0ApdThwg+/Tr0u1NmQs7BNkZXHc6KQ430YuLviCOu2vW5RYw6UlTlqaNA6YxHv T2YCoqejqY3geG3Ohl4jimt40L19PkABkX2jFvFQv6WNjaGTgnUBFq0LitDcnyo9G+oa mTiA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:content-transfer-encoding :mime-version:references:in-reply-to:message-id:date:subject:cc:to :from:dkim-signature; bh=FhLepc2FNecPvpeSsLH6uZ0VrrKtY3S5wQ6stB/IAEE=; b=QWL7AXA6gCEHW9AaqYM+EjGu1c6dSofNDkoMIJeTh1awXL9UYDkdhgkvp0mXmbeI1E Y31Gj4dtzz1GzkiC742bzraaUYr9Q9cavNIrgjNPsoHy0lmwEYoh8uKyli+tE8ApUEh0 qxBmu1ADQaH+DK483a2tfnB8T/3X0FL/R9f/U+Y37jA8jiqhPFXSF2syqOgitRjYHo3h jdpdGheC7t4aCvnijB4lm4GbfMcJ8B1TnFLOO24pedlNYAKKEY7VnO3jGjTDrZEdtDVq eDQQv+FYD7sO4PrDPzz5d+I/NskAeY18Upuxew/sUDsVAoCy0scQrcPSFIeDGHBpnv4K PJmQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=EPPyiV8C; spf=pass (google.com: domain of u-boot-bounces@lists.denx.de designates 85.214.62.61 as permitted sender) smtp.mailfrom=u-boot-bounces@lists.denx.de; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from phobos.denx.de (phobos.denx.de. [85.214.62.61]) by mx.google.com with ESMTPS id l20-20020a056870f15400b00169e620d71fsi8519939oac.187.2023.02.14.05.38.46 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 14 Feb 2023 05:38:46 -0800 (PST) Received-SPF: pass (google.com: domain of u-boot-bounces@lists.denx.de designates 85.214.62.61 as permitted sender) client-ip=85.214.62.61; Authentication-Results: mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=EPPyiV8C; spf=pass (google.com: domain of u-boot-bounces@lists.denx.de designates 85.214.62.61 as permitted sender) smtp.mailfrom=u-boot-bounces@lists.denx.de; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Received: from h2850616.stratoserver.net (localhost [IPv6:::1]) by phobos.denx.de (Postfix) with ESMTP id 8D3E58591B; Tue, 14 Feb 2023 14:38:35 +0100 (CET) Authentication-Results: phobos.denx.de; dmarc=pass (p=none dis=none) header.from=linaro.org Authentication-Results: phobos.denx.de; spf=pass smtp.mailfrom=u-boot-bounces@lists.denx.de Authentication-Results: phobos.denx.de; dkim=pass (2048-bit key; unprotected) header.d=linaro.org header.i=@linaro.org header.b="EPPyiV8C"; dkim-atps=neutral Received: by phobos.denx.de (Postfix, from userid 109) id 0001E8592D; Tue, 14 Feb 2023 14:38:26 +0100 (CET) X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on phobos.denx.de X-Spam-Level: X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.2 Received: from mail-pj1-x102b.google.com (mail-pj1-x102b.google.com [IPv6:2607:f8b0:4864:20::102b]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits)) (No client certificate requested) by phobos.denx.de (Postfix) with ESMTPS id 4026785905 for ; Tue, 14 Feb 2023 14:38:23 +0100 (CET) Authentication-Results: phobos.denx.de; dmarc=pass (p=none dis=none) header.from=linaro.org Authentication-Results: phobos.denx.de; spf=pass smtp.mailfrom=paul.liu@linaro.org Received: by mail-pj1-x102b.google.com with SMTP id w14-20020a17090a5e0e00b00233d3b9650eso7921905pjf.4 for ; Tue, 14 Feb 2023 05:38:23 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=FhLepc2FNecPvpeSsLH6uZ0VrrKtY3S5wQ6stB/IAEE=; b=EPPyiV8CHILLAPM3435GRRI/7OQuiirsDbNX8R3dTKB0WWj/JjJPMWUo1BBU16G+4O a7ypFPf02ZC8q759iBbaAgwCkzzAiD0LpoZA7q02N32nAz9F9hUS3XtCQVrz5FUjFPH1 sl/ZPyXQz4onvEqQkiEehtt//9dqvLTend85qhUq9scn08voFSCm7pQnuVdA1hIQSBKD UM/xb3P4b5oaQhDF/M6MSw1VxET1OdoBekf+n0qeAm6N6TwIgvnbp79WNPCVy0UpAb5m D2FEq/UCf9kexPohQOcDDZipmSWopzeaz5ByR+0CU1HIznKCL7QMIN2QDzOMWNvDJhDg /X4g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=FhLepc2FNecPvpeSsLH6uZ0VrrKtY3S5wQ6stB/IAEE=; b=f0f/SJCfgKjbpwjHhtm7iVzLP0/+ugVID/kRZwDXkbY8ejw0CYFpxwKYXtUP6uaWJt uNl9McHXiHVGgaArnzwlUI6ADjRysdtHXXKDufoaZ1mXE1VUK6FBRqsv3CFrxQOeT1xz llgKj6gHpWCsATaV2yIVGOPKLfTjaoI2aM2XupAVYE5Rt7omLnIvU7wG2nK9ti5CPmqf RkpDaHdEi2yEJvRD5J9C/QGz9iMolFosxyBe7usQDR7FnDpfeOTIHavuVAVl0jGSR0Yk sTr3SmiYxqxOncfke1S3/wIjEU8bKynUYbjoC93C67V/8cO90qxxM4bShsttjJa5+Mb3 RBdQ== X-Gm-Message-State: AO0yUKX0E5aaudOQIhMIKW0TOKT3v0/mf41eJH54sXm1x9d1Fy3n5feO +Gmq/3+CBnTA9uR0J8gGEIbCAnXeT1UYTFDs X-Received: by 2002:a17:90b:4a06:b0:231:24c1:8028 with SMTP id kk6-20020a17090b4a0600b0023124c18028mr2410276pjb.29.1676381901499; Tue, 14 Feb 2023 05:38:21 -0800 (PST) Received: from localhost ([111.184.129.17]) by smtp.gmail.com with ESMTPSA id 23-20020a17090a005700b00233d6547000sm4911652pjb.54.2023.02.14.05.38.20 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 14 Feb 2023 05:38:21 -0800 (PST) From: "Ying-Chun Liu (PaulLiu)" To: u-boot@lists.denx.de Cc: Marc Zyngier , =?utf-8?q?Pierre-Cl=C3=A9ment_Tosi?= , Ying-Chun Liu , Tom Rini Subject: [PATCH 1/2] arm64: Reduce add_map() complexity Date: Tue, 14 Feb 2023 21:38:13 +0800 Message-Id: <20230214133814.4173549-2-paul.liu@linaro.org> X-Mailer: git-send-email 2.39.1 In-Reply-To: <20230214133814.4173549-1-paul.liu@linaro.org> References: <20230214133814.4173549-1-paul.liu@linaro.org> MIME-Version: 1.0 X-BeenThere: u-boot@lists.denx.de X-Mailman-Version: 2.1.39 Precedence: list List-Id: U-Boot discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: u-boot-bounces@lists.denx.de Sender: "U-Boot" X-Virus-Scanned: clamav-milter 0.103.6 at phobos.denx.de X-Virus-Status: Clean From: Marc Zyngier In the add_map() function, for each level it populates, it iterates from the root of the PT tree, making it ineficient if a mapping needs to occur past level 1. Instead, replace it with a recursive (and much simpler) algorithm that keeps the complexity as low as possible. With this, mapping 512GB at level 2 goes from several seconds down to not measurable on an A55 machine. We keep the block mappings at level 1 for now though. Signed-off-by: Marc Zyngier Signed-off-by: Pierre-Clément Tosi [ Paul: pick from the Android tree. Fixup Pierre's commit. Rebase to the upstream ] Signed-off-by: Ying-Chun Liu (PaulLiu) Cc: Tom Rini Link: https://android.googlesource.com/platform/external/u-boot/+/96ad729cf4cab53bdff8222bb3eb256f38b5c3a6 Link: https://android.googlesource.com/platform/external/u-boot/+/6be9330601d81545c7c941e3609f35bf68a09059 --- arch/arm/cpu/armv8/cache_v8.c | 94 +++++++++++++++++------------------ 1 file changed, 46 insertions(+), 48 deletions(-) diff --git a/arch/arm/cpu/armv8/cache_v8.c b/arch/arm/cpu/armv8/cache_v8.c index f333ad8889..876344e1b4 100644 --- a/arch/arm/cpu/armv8/cache_v8.c +++ b/arch/arm/cpu/armv8/cache_v8.c @@ -299,61 +299,59 @@ static void split_block(u64 *pte, int level) set_pte_table(pte, new_table); } -/* Add one mm_region map entry to the page tables */ -static void add_map(struct mm_region *map) +static void map_range(u64 virt, u64 phys, u64 size, int level, + u64 *table, u64 attrs) { - u64 *pte; - u64 virt = map->virt; - u64 phys = map->phys; - u64 size = map->size; - u64 attrs = map->attrs | PTE_TYPE_BLOCK | PTE_BLOCK_AF; - u64 blocksize; - int level; - u64 *new_table; + u64 map_size = BIT_ULL(level2shift(level)); + int i, idx; - while (size) { - pte = find_pte(virt, 0); - if (pte && (pte_type(pte) == PTE_TYPE_FAULT)) { - debug("Creating table for virt 0x%llx\n", virt); - new_table = create_table(); - set_pte_table(pte, new_table); - } + idx = (virt >> level2shift(level)) & (MAX_PTE_ENTRIES - 1); + for (i = idx; size; i++) { + u64 next_size, *next_table; - for (level = 1; level < 4; level++) { - pte = find_pte(virt, level); - if (!pte) - panic("pte not found\n"); - - blocksize = 1ULL << level2shift(level); - debug("Checking if pte fits for virt=%llx size=%llx blocksize=%llx\n", - virt, size, blocksize); - if (size >= blocksize && !(virt & (blocksize - 1))) { - /* Page fits, create block PTE */ - debug("Setting PTE %p to block virt=%llx\n", - pte, virt); - if (level == 3) - *pte = phys | attrs | PTE_TYPE_PAGE; - else - *pte = phys | attrs; - virt += blocksize; - phys += blocksize; - size -= blocksize; - break; - } else if (pte_type(pte) == PTE_TYPE_FAULT) { - /* Page doesn't fit, create subpages */ - debug("Creating subtable for virt 0x%llx blksize=%llx\n", - virt, blocksize); - new_table = create_table(); - set_pte_table(pte, new_table); - } else if (pte_type(pte) == PTE_TYPE_BLOCK) { - debug("Split block into subtable for virt 0x%llx blksize=0x%llx\n", - virt, blocksize); - split_block(pte, level); - } + if (level >= 1 && + size >= map_size && !(virt & (map_size - 1))) { + if (level == 3) + table[i] = phys | attrs | PTE_TYPE_PAGE; + else + table[i] = phys | attrs; + + virt += map_size; + phys += map_size; + size -= map_size; + + continue; } + + /* Going one level down */ + if (pte_type(&table[i]) == PTE_TYPE_FAULT) + set_pte_table(&table[i], create_table()); + + next_table = (u64 *)(table[i] & GENMASK_ULL(47, PAGE_SHIFT)); + next_size = min(map_size - (virt & (map_size - 1)), size); + + map_range(virt, phys, next_size, level + 1, next_table, attrs); + + virt += next_size; + phys += next_size; + size -= next_size; } } +static void add_map(struct mm_region *map) +{ + u64 attrs = map->attrs | PTE_TYPE_BLOCK | PTE_BLOCK_AF; + u64 va_bits; + int level = 0; + + get_tcr(NULL, &va_bits); + if (va_bits < 39) + level = 1; + + map_range(map->virt, map->phys, map->size, level, + (u64 *)gd->arch.tlb_addr, attrs); +} + enum pte_type { PTE_INVAL, PTE_BLOCK, From patchwork Tue Feb 14 13:38:14 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Paul Liu X-Patchwork-Id: 653463 Delivered-To: patch@linaro.org Received: by 2002:adf:f90f:0:0:0:0:0 with SMTP id b15csp3038402wrr; Tue, 14 Feb 2023 05:39:36 -0800 (PST) X-Google-Smtp-Source: AK7set+R+EG576bRVSqdUsfQSxy7tOVEWyo5rPkvE2+QcrvSW+SQRRLky+0vUJYP7oSojqVC6iZb X-Received: by 2002:a05:6870:1ce:b0:16d:ec20:3931 with SMTP id n14-20020a05687001ce00b0016dec203931mr1144337oad.17.1676381976764; Tue, 14 Feb 2023 05:39:36 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1676381976; cv=none; d=google.com; s=arc-20160816; b=qexH+0NuDWh8lkpKc9J+sXNBKPzygSuzMGpnhyOxy7afnBKKHyIVo3cabv6KrX+cXm l6iN6pcoum7ky9Qwt84vc+DSd7k8+s7Dkw8UfjoWpZXQbBj5Apkf4/LDgPof0zXENXeV DYI7fWYfRfmgnre+a0nBMSiYETTZhqp6QrZ0QApiToruawFNFS3uIEILdGEr+IR0LVkL NH7r/C8y5Wd70h7Mjkfll+NmaoZ6NQARMZ76IgosPMKfEKRy4eSpl+DGfvruWcMAqhLm JtfgR3a0zvBcBbTP7lpJjAlvEsbjNwUluRTXXh1fhP/MYCnQxlFC1hPkn/fmgYMDkR5w ID2A== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:content-transfer-encoding :mime-version:references:in-reply-to:message-id:date:subject:cc:to :from:dkim-signature; bh=dEvdCjJfS19pWWjNuik3CWDaKRXa+ULc1LVJsvaQjwM=; b=BHbr+cd7QT/hkA/bqcbWoko8nQpeYDeZOcH3xLUbGET3XEMBqeIO3YFXEiRVh3v1V8 0iId6w5+FDPI5MFfDi8DBHBLXoKGhIrMF9zruY4ZOI9KV76KPerYCjwyy4vhfbaS+D+Y oA68xtyNwyJiqLXdSc/ai9GyY4UwP3S36/GK7rzICWdSveD2YiDb4ttNmUnGlYsj6pEL lol4Bfsf0OtKw+zU/uvuO3V4YHKVKkroTw3omBA4yvePdwLzmpXcY8ElyMNiUn6AQfiQ WwBosnuJ+W7wJiX+P1w+bWrrxRlikjaWeSNiowwXAmyZNN/vj7RaUUPj4qe7Uh34K1cE j0ew== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=QdIA6XaD; spf=pass (google.com: domain of u-boot-bounces@lists.denx.de designates 85.214.62.61 as permitted sender) smtp.mailfrom=u-boot-bounces@lists.denx.de; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from phobos.denx.de (phobos.denx.de. [85.214.62.61]) by mx.google.com with ESMTPS id b14-20020a056870b24e00b0016e078d937fsi6184307oam.332.2023.02.14.05.39.35 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 14 Feb 2023 05:39:36 -0800 (PST) Received-SPF: pass (google.com: domain of u-boot-bounces@lists.denx.de designates 85.214.62.61 as permitted sender) client-ip=85.214.62.61; Authentication-Results: mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=QdIA6XaD; spf=pass (google.com: domain of u-boot-bounces@lists.denx.de designates 85.214.62.61 as permitted sender) smtp.mailfrom=u-boot-bounces@lists.denx.de; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Received: from h2850616.stratoserver.net (localhost [IPv6:::1]) by phobos.denx.de (Postfix) with ESMTP id 02C288593A; Tue, 14 Feb 2023 14:38:41 +0100 (CET) Authentication-Results: phobos.denx.de; dmarc=pass (p=none dis=none) header.from=linaro.org Authentication-Results: phobos.denx.de; spf=pass smtp.mailfrom=u-boot-bounces@lists.denx.de Authentication-Results: phobos.denx.de; dkim=pass (2048-bit key; unprotected) header.d=linaro.org header.i=@linaro.org header.b="QdIA6XaD"; dkim-atps=neutral Received: by phobos.denx.de (Postfix, from userid 109) id 7D11C8591B; Tue, 14 Feb 2023 14:38:28 +0100 (CET) X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on phobos.denx.de X-Spam-Level: X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.2 Received: from mail-pj1-x1032.google.com (mail-pj1-x1032.google.com [IPv6:2607:f8b0:4864:20::1032]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits)) (No client certificate requested) by phobos.denx.de (Postfix) with ESMTPS id 0B08D854EF for ; Tue, 14 Feb 2023 14:38:25 +0100 (CET) Authentication-Results: phobos.denx.de; dmarc=pass (p=none dis=none) header.from=linaro.org Authentication-Results: phobos.denx.de; spf=pass smtp.mailfrom=paul.liu@linaro.org Received: by mail-pj1-x1032.google.com with SMTP id d13-20020a17090ad3cd00b0023127b2d602so15474547pjw.2 for ; Tue, 14 Feb 2023 05:38:24 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=dEvdCjJfS19pWWjNuik3CWDaKRXa+ULc1LVJsvaQjwM=; b=QdIA6XaDWk6a1z+VbPvCV+WJ0HB8lC4TQ52owuAwD/8mJ211AzhUcQ8/W/nm2EDLXD b8OgYstduVRBgck6NAajpkPj3TuWfNGyzvNkot8u5CV3Upzg2SSS+7vxevg3BWzcnZ5d BhzezPI92jNHDnX2gna7SKjZjYKk6tk0VYNb3QZqmuNqgCnonIjIufQ9HAnyBL6M7kbn HVe3JViD+A+JrWgNAUxZXRvdVrieoUvDBTMqqdhd42jmN/6Gbyok+pk2gfHSsOykWh3s wZ5ze0DcZJ/hh5JMlWgoQgIj75zygp0M+1jKTm0gcXyZZ4m+yQoYls6dznNOUK45ch3I 8Lrw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=dEvdCjJfS19pWWjNuik3CWDaKRXa+ULc1LVJsvaQjwM=; b=miO4JovC5Y3KVQNZeu3W7D8zgOYikalruWk1L20yOXZWdcQPb17C0BMiIPcS2ZeFzG 3+4AFRzVFQXvwZCKd4nAEJ7fU0EHKmxm6E5HsHqF/cQG1aB4QRwvmuMPdfRrvmZ0+1g3 5XoWcMhZEWPGLr3Uuv60ZPpZruqLtHtPxb8Akmg5DBUqargbT3G8vowJ35Tymqn8+h06 Pl9AQ8+dju9Wod5VXXRS9a7wObp6KgotCRDtyTU1RBRmXc4/RhYBGgmLvhplQm+oPtmY ve0FoMEK7ub/o7wBXb0f/b2SH9v9LzKRoWE/wvjYJzkC/shSwe/T/4251KNna7bM30+h Modg== X-Gm-Message-State: AO0yUKWEyODeT1bNy957Jfpbagi/+ht4EdnTpQSxDDounEeXi/u+VpVz HGAdEjUG8HIDaFlSSG73uzbpYxNCBKDprghA X-Received: by 2002:a17:903:18e:b0:19a:b7c0:f097 with SMTP id z14-20020a170903018e00b0019ab7c0f097mr2160010plg.57.1676381903223; Tue, 14 Feb 2023 05:38:23 -0800 (PST) Received: from localhost ([111.184.129.17]) by smtp.gmail.com with ESMTPSA id jh9-20020a170903328900b0018b025d9a40sm6471579plb.256.2023.02.14.05.38.22 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 14 Feb 2023 05:38:22 -0800 (PST) From: "Ying-Chun Liu (PaulLiu)" To: u-boot@lists.denx.de Cc: Marc Zyngier , =?utf-8?q?Pierre-Cl=C3=A9ment_Tosi?= , Ying-Chun Liu , Tom Rini Subject: [PATCH 2/2] arm64: Reduce PT size estimation complexity Date: Tue, 14 Feb 2023 21:38:14 +0800 Message-Id: <20230214133814.4173549-3-paul.liu@linaro.org> X-Mailer: git-send-email 2.39.1 In-Reply-To: <20230214133814.4173549-1-paul.liu@linaro.org> References: <20230214133814.4173549-1-paul.liu@linaro.org> MIME-Version: 1.0 X-BeenThere: u-boot@lists.denx.de X-Mailman-Version: 2.1.39 Precedence: list List-Id: U-Boot discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: u-boot-bounces@lists.denx.de Sender: "U-Boot" X-Virus-Scanned: clamav-milter 0.103.6 at phobos.denx.de X-Virus-Status: Clean From: Marc Zyngier count_required_pts()'s complexity is high if mappings are not using the largest possible block size (due to some other requirement such as tracking dirty pages, for example). Let's switch to a method that follows the pattern established with the add_map() helper, and make it almost instantaneous instead of taking a large amount of time if 2MB mappings are in use instead of 1GB. Signed-off-by: Marc Zyngier Signed-off-by: Pierre-Clément Tosi [ Paul: pick from the Android tree. Fixup Pierre's commit. Rebase to the upstream ] Signed-off-by: Ying-Chun Liu (PaulLiu) Cc: Tom Rini Link: https://android.googlesource.com/platform/external/u-boot/+/5d756d147e31a1cdaaa261a50e526404ca5968f5 Link: https://android.googlesource.com/platform/external/u-boot/+/6be9330601d81545c7c941e3609f35bf68a09059 --- arch/arm/cpu/armv8/cache_v8.c | 109 +++++++++++----------------------- 1 file changed, 34 insertions(+), 75 deletions(-) diff --git a/arch/arm/cpu/armv8/cache_v8.c b/arch/arm/cpu/armv8/cache_v8.c index 876344e1b4..697334086f 100644 --- a/arch/arm/cpu/armv8/cache_v8.c +++ b/arch/arm/cpu/armv8/cache_v8.c @@ -352,98 +352,57 @@ static void add_map(struct mm_region *map) (u64 *)gd->arch.tlb_addr, attrs); } -enum pte_type { - PTE_INVAL, - PTE_BLOCK, - PTE_LEVEL, -}; - -/* - * This is a recursively called function to count the number of - * page tables we need to cover a particular PTE range. If you - * call this with level = -1 you basically get the full 48 bit - * coverage. - */ -static int count_required_pts(u64 addr, int level, u64 maxaddr) +static void count_range(u64 virt, u64 size, int level, int *cntp) { - int levelshift = level2shift(level); - u64 levelsize = 1ULL << levelshift; - u64 levelmask = levelsize - 1; - u64 levelend = addr + levelsize; - int r = 0; - int i; - enum pte_type pte_type = PTE_INVAL; + u64 map_size = BIT_ULL(level2shift(level)); + int i, idx; - for (i = 0; mem_map[i].size || mem_map[i].attrs; i++) { - struct mm_region *map = &mem_map[i]; - u64 start = map->virt; - u64 end = start + map->size; + idx = (virt >> level2shift(level)) & (MAX_PTE_ENTRIES - 1); + for (i = idx; size; i++) { + u64 next_size; - /* Check if the PTE would overlap with the map */ - if (max(addr, start) <= min(levelend, end)) { - start = max(addr, start); - end = min(levelend, end); + if (level >= 1 && + size >= map_size && !(virt & (map_size - 1))) { + virt += map_size; + size -= map_size; - /* We need a sub-pt for this level */ - if ((start & levelmask) || (end & levelmask)) { - pte_type = PTE_LEVEL; - break; - } + continue; + } - /* Lv0 can not do block PTEs, so do levels here too */ - if (level <= 0) { - pte_type = PTE_LEVEL; - break; - } + /* Going one level down */ + (*cntp)++; + next_size = min(map_size - (virt & (map_size - 1)), size); - /* PTE is active, but fits into a block */ - pte_type = PTE_BLOCK; - } - } + count_range(virt, next_size, level + 1, cntp); - /* - * Block PTEs at this level are already covered by the parent page - * table, so we only need to count sub page tables. - */ - if (pte_type == PTE_LEVEL) { - int sublevel = level + 1; - u64 sublevelsize = 1ULL << level2shift(sublevel); - - /* Account for the new sub page table ... */ - r = 1; - - /* ... and for all child page tables that one might have */ - for (i = 0; i < MAX_PTE_ENTRIES; i++) { - r += count_required_pts(addr, sublevel, maxaddr); - addr += sublevelsize; - - if (addr >= maxaddr) { - /* - * We reached the end of address space, no need - * to look any further. - */ - break; - } - } + virt += next_size; + size -= next_size; } - - return r; } -/* Returns the estimated required size of all page tables */ -__weak u64 get_page_table_size(void) +static int count_ranges(void) { - u64 one_pt = MAX_PTE_ENTRIES * sizeof(u64); - u64 size = 0; + int i, count = 0, level = 0; u64 va_bits; - int start_level = 0; get_tcr(NULL, &va_bits); if (va_bits < 39) - start_level = 1; + level = 1; + + for (i = 0; mem_map[i].size || mem_map[i].attrs; i++) + count_range(mem_map[i].virt, mem_map[i].size, level, &count); + + return count; +} + +/* Returns the estimated required size of all page tables */ +__weak u64 get_page_table_size(void) +{ + u64 one_pt = MAX_PTE_ENTRIES * sizeof(u64); + u64 size; /* Account for all page tables we would need to cover our memory map */ - size = one_pt * count_required_pts(0, start_level - 1, 1ULL << va_bits); + size = one_pt * count_ranges(); /* * We need to duplicate our page table once to have an emergency pt to