From mboxrd@z Thu Jan 1 00:00:00 1970 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 phobos.denx.de (phobos.denx.de [85.214.62.61]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.lore.kernel.org (Postfix) with ESMTPS id 59C05C64ED6 for ; Tue, 14 Feb 2023 13:39:34 +0000 (UTC) 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) 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-Google-Smtp-Source: AK7set/oHJsyJO2eVYrcdYhbefmP6V7se3Nucy3nmUloEyMQhLi5uRkYEu1FHYGD+Kmw+lm8jQX4gw== 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=20Tosi?= , 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 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit 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 -- 2.39.1