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