From patchwork Wed Jun 26 17:48:14 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Xiang W X-Patchwork-Id: 1952741 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (2048-bit key; secure) header.d=lists.infradead.org header.i=@lists.infradead.org header.a=rsa-sha256 header.s=bombadil.20210309 header.b=BmUaU2NG; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=126.com header.i=@126.com header.a=rsa-sha256 header.s=s110527 header.b=TEg3/bRr; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=none (no SPF record) smtp.mailfrom=lists.infradead.org (client-ip=2607:7c80:54:3::133; helo=bombadil.infradead.org; envelope-from=opensbi-bounces+incoming=patchwork.ozlabs.org@lists.infradead.org; receiver=patchwork.ozlabs.org) Received: from bombadil.infradead.org (bombadil.infradead.org [IPv6:2607:7c80:54:3::133]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4W8Tjb2yj3z20Z9 for ; Thu, 27 Jun 2024 03:49:38 +1000 (AEST) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20210309; h=Sender: Content-Transfer-Encoding:Content-Type:List-Subscribe:List-Help:List-Post: List-Archive:List-Unsubscribe:List-Id:MIME-Version:References:In-Reply-To: Message-ID:Date:Subject:Cc:To:From:Reply-To:Content-ID:Content-Description: Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID: List-Owner; bh=spJvnQiWBib5YvHTf9rDklxr9qMEKFfHiBOBbfG/aA0=; b=BmUaU2NG86T6pd NvAmw2H0fL3BzRitPxHwvKARcgzXmSxYEicDq87EZohKm7iosGMu65Hx4nCBcRI9lBoES4orVTm5p v7QxUq9OT8xbrQarphJH2DE9Z3PWTSb3pqJOLB8u0Qtjyz5D2CtVsWFM2y5K7TmhSDF+zIk+tMGDp PwwCZj7S3HZWAOm4AZSuSo5lXhwULLH/HC6M/YT72y+PWIF14B/uxPZ8bxBFrlCveOXVVFrG7JEzd 7bbO0CSvKea+KVmnkYimLBayxJelgzhzKTmcQOEZ8QhUy65HMjr+Z8iFfj0Glx4oQwpJDsbcrbGXa +99xeltPZ/PXQyxpXFDw==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.97.1 #2 (Red Hat Linux)) id 1sMWlo-00000007oYf-0eBw; Wed, 26 Jun 2024 17:49:24 +0000 Received: from m16.mail.126.com ([220.197.31.9]) by bombadil.infradead.org with esmtp (Exim 4.97.1 #2 (Red Hat Linux)) id 1sMWlh-00000007oWv-1hSV for opensbi@lists.infradead.org; Wed, 26 Jun 2024 17:49:22 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=126.com; s=s110527; h=From:Subject:Date:Message-ID:MIME-Version; bh=gWy0f am+hy9G1CAek+fuWWgszDw9/vbaDEH2K7OcsAY=; b=TEg3/bRr3NTmeEcKVel7w mvgPzmz2luWrUDEfgEcU7pJ6ZFK2DWMAVj0BL4IH4T+8exAE2JXYstOgRCUDV3U/ JxjU2C7iX90QrXbVlh4RIlMu4ppcN0rNPQ6Z0gsdO6dbWsy+gyzo8eiegt2Y26DB rZVzshJD1w5kSXlhG7fauk= Received: from T490.lan (unknown [112.83.183.192]) by gzga-smtp-mta-g0-1 (Coremail) with SMTP id _____wD3Hz5iVHxmnCGXAA--.57783S5; Thu, 27 Jun 2024 01:48:20 +0800 (CST) From: Xiang W To: opensbi@lists.infradead.org Cc: Xiang W , anup@brainfault.org Subject: [PATCH 3/3] lib: sbi: Improve memory region merging Date: Thu, 27 Jun 2024 01:48:14 +0800 Message-ID: <20240626174816.2837278-4-wxjstz@126.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20240626174816.2837278-1-wxjstz@126.com> References: <20240626174816.2837278-1-wxjstz@126.com> MIME-Version: 1.0 X-CM-TRANSID: _____wD3Hz5iVHxmnCGXAA--.57783S5 X-Coremail-Antispam: 1Uf129KBjvJXoW3Xw4fCw4rCryfXFyUWw1UGFg_yoW3Gry8pa 15KF9rKr4Iqr4jqws7Ga1UX390yr1IyF4a939rAw18A3WxJr9xCFWrZw1jvF1YvFyxXa1j 9Fy5WrsrCrsxtaDanT9S1TB71UUUUU7qnTZGkaVYY2UrUUUUjbIjqfuFe4nvWSU5nxnvy2 9KBjDUYxBIdaVFxhVjvjDU0xZFpf9x0zRQzVbUUUUU= X-Originating-IP: [112.83.183.192] X-CM-SenderInfo: pz0m23b26rjloofrz/1tbi5BQKOmVLaGIakgAAss X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20240626_104919_419054_C367651A X-CRM114-Status: GOOD ( 18.90 ) X-Spam-Score: -0.2 (/) X-Spam-Report: Spam detection software, running on the system "bombadil.infradead.org", has NOT identified this incoming email as spam. The original message has been attached to this so you can view it or label similar future email. If you have any questions, see the administrator of that system for details. Content preview: The previous merging method can only merge blocks of the same order. The current merging method can merge blocks of different orders. The tor type of pmp can be used to save pmp configuration register [...] Content analysis details: (-0.2 points, 5.0 required) pts rule name description ---- ---------------------- -------------------------------------------------- -0.0 RCVD_IN_DNSWL_NONE RBL: Sender listed at https://www.dnswl.org/, no trust [220.197.31.9 listed in list.dnswl.org] -0.0 SPF_PASS SPF: sender matches SPF record 0.0 SPF_HELO_NONE SPF: HELO does not publish an SPF Record -0.1 DKIM_VALID Message has at least one valid DKIM or DK signature -0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from author's domain -0.1 DKIM_VALID_EF Message has a valid DKIM or DK signature from envelope-from domain 0.1 DKIM_SIGNED Message has a DKIM or DK signature, not necessarily valid 0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider [wxjstz(at)126.com] X-BeenThere: opensbi@lists.infradead.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: "opensbi" Errors-To: opensbi-bounces+incoming=patchwork.ozlabs.org@lists.infradead.org The previous merging method can only merge blocks of the same order. The current merging method can merge blocks of different orders. The tor type of pmp can be used to save pmp configuration registers. Signed-off-by: Xiang W --- lib/sbi/sbi_domain.c | 254 +++++++++++++++++++++++++++++-------------- 1 file changed, 172 insertions(+), 82 deletions(-) diff --git a/lib/sbi/sbi_domain.c b/lib/sbi/sbi_domain.c index 9a9fce1..4d8d995 100644 --- a/lib/sbi/sbi_domain.c +++ b/lib/sbi/sbi_domain.c @@ -279,17 +279,175 @@ static void swap_region(struct sbi_domain_memregion* reg1, sbi_memcpy(reg2, &treg, sizeof(treg)); } -static void clear_region(struct sbi_domain_memregion* reg) +static bool merge_find_near(struct sbi_domain *dom, + unsigned long flags, + unsigned long *start, + unsigned long *end, + unsigned long *bmap) { - sbi_memset(reg, 0x0, sizeof(*reg)); + bool found, ret = false; + int i; + unsigned long s, e, s1, e1; + struct sbi_domain_memregion *reg; + s = *start; + e = *end; + do { + found = false; + i = 0; + sbi_domain_for_each_memregion(dom, reg) { + i++; + if (__test_bit(i- 1, bmap)) + continue; + if (flags != reg->flags) + continue; + s1 = memregion_start(reg); + e1 = memregion_end(reg); + if (e1 < s - 1 || s1 > e + 1) + continue; + found = true; + __set_bit(i - 1, bmap); + s = MIN(s, s1); + e = MAX(e, e1); + } + ret = ret || found; + } while (found); + *start = s; + *end = e; + + return ret; } -static int sanitize_domain(struct sbi_domain *dom) +static void merge_del_helper(struct sbi_domain *dom, + unsigned long *regions_count, unsigned long *bmap) +{ + int i, s = 0, count = *regions_count; + for (i = count - 1; i >= 0; i--) { + if (!__test_bit(i, bmap)) + s += sizeof(struct sbi_domain_memregion); + else { + sbi_memmove(dom->regions + i, dom->regions + i + 1, s); + count--; + } + } + + dom->regions[count].order = 0; + *regions_count = count; +} + +static bool merge_add_helper(struct sbi_domain *dom, + unsigned long *regions_count, + unsigned long *bmap, unsigned long start, + unsigned long end, unsigned long flags) { - u32 i, j, count; - bool is_covered; + int cnt = 0; + unsigned long pos, order, size, s; + end = end + 1; + size = end - start; + if (sbi_popcount(size) > 2) { + merge_del_helper(dom, regions_count, bmap); + + dom->regions[*regions_count].base = start; + dom->regions[*regions_count].size = size; + dom->regions[*regions_count].order = 1; + dom->regions[*regions_count].flags = flags; + (*regions_count)++; + dom->regions[*regions_count].order = 0; + return true; + } + + + pos = start; + while (pos < end) { + s = end - pos; + order = sbi_ffs(pos); + if (BIT(order) > s) + order = sbi_fls(s); + pos = pos + BIT(order); + cnt++; + } + if (cnt >= sbi_popcount(*bmap)) + return false; + + merge_del_helper(dom, regions_count, bmap); + + pos = start; + while (pos < end) { + s = end - pos; + order = sbi_ffs(pos); + if (BIT(order) > s) + order = sbi_fls(s); + dom->regions[*regions_count].base = pos; + dom->regions[*regions_count].size = 0; + dom->regions[*regions_count].order = order; + dom->regions[*regions_count].flags = flags; + (*regions_count)++; + pos = pos + BIT(order); + } + dom->regions[*regions_count].order = 0; + + return true; +} + +static int merge_region(struct sbi_domain *dom) +{ + int i, j; + bool found; + unsigned long bmap, start, end, regions_count; struct sbi_domain_memregion *reg, *reg1; + /* Count memory regions */ + regions_count = root_memregs_count; + if (dom != &root) { + regions_count = 0; + sbi_domain_for_each_memregion(dom, reg) + regions_count++; + } + + /* + * bmap is used to record near regions that may be merged. The number of + * regions cannot exceed the number of bits in bmap. + */ + if (regions_count > BITS_PER_LONG) + return SBI_EINVAL; + + i = 0; + while(i < regions_count) { + reg = dom->regions + i; + bmap = 1UL << i; + start = memregion_start(reg); + end = memregion_end(reg); + found = merge_find_near(dom, reg->flags, &start, &end, &bmap); + if (found) { + if (merge_add_helper(dom, ®ions_count, &bmap, + start, end, reg->flags)) + continue; + } + i++; + } + + /* Sort the memory regions */ + for (i = 0; i < (regions_count - 1); i++) { + reg = &dom->regions[i]; + for (j = i + 1; j < regions_count; j++) { + reg1 = &dom->regions[j]; + + if (!is_region_before(reg1, reg)) + continue; + + swap_region(reg, reg1); + } + } + + if (dom == &root) + root_memregs_count = regions_count; + return SBI_OK; +} + +static int sanitize_domain(struct sbi_domain *dom) +{ + u32 i; + struct sbi_domain_memregion *reg; + /* Check possible HARTs */ if (!dom->possible_harts) { sbi_printf("%s: %s possible HART mask is NULL\n", @@ -321,11 +479,6 @@ static int sanitize_domain(struct sbi_domain *dom) } } - /* Count memory regions */ - count = 0; - sbi_domain_for_each_memregion(dom, reg) - count++; - /* Check presence of firmware regions */ if (!dom->fw_region_inited) { sbi_printf("%s: %s does not have firmware region\n", @@ -333,43 +486,7 @@ static int sanitize_domain(struct sbi_domain *dom) return SBI_EINVAL; } - /* Sort the memory regions */ - for (i = 0; i < (count - 1); i++) { - reg = &dom->regions[i]; - for (j = i + 1; j < count; j++) { - reg1 = &dom->regions[j]; - - if (!is_region_before(reg1, reg)) - continue; - - swap_region(reg, reg1); - } - } - - /* Remove covered regions */ - while(i < (count - 1)) { - is_covered = false; - reg = &dom->regions[i]; - - for (j = i + 1; j < count; j++) { - reg1 = &dom->regions[j]; - - if (is_region_compatible(reg, reg1)) { - is_covered = true; - break; - } - } - - /* find a region is superset of reg, remove reg */ - if (is_covered) { - for (j = i; j < (count - 1); j++) - swap_region(&dom->regions[j], - &dom->regions[j + 1]); - clear_region(&dom->regions[count - 1]); - count--; - } else - i++; - } + merge_region(dom); /* * We don't need to check boot HART id of domain because if boot @@ -605,8 +722,7 @@ int sbi_domain_register(struct sbi_domain *dom, int sbi_domain_root_add_memregion(const struct sbi_domain_memregion *reg) { int rc; - bool reg_merged; - struct sbi_domain_memregion *nreg, *nreg1, *nreg2; + struct sbi_domain_memregion *nreg; /* Sanity checks */ if (!reg || domain_finalized || !root.regions || @@ -625,39 +741,13 @@ int sbi_domain_root_add_memregion(const struct sbi_domain_memregion *reg) root_memregs_count++; root.regions[root_memregs_count].order = 0; - /* Sort and optimize root regions */ - do { - /* Sanitize the root domain so that memregions are sorted */ - rc = sanitize_domain(&root); - if (rc) { - sbi_printf("%s: sanity checks failed for" - " %s (error %d)\n", __func__, - root.name, rc); - return rc; - } - - /* Merge consecutive memregions with same order and flags */ - reg_merged = false; - sbi_domain_for_each_memregion(&root, nreg) { - nreg1 = nreg + 1; - if (!nreg1->order) - continue; - - if (!(nreg->base & (BIT(nreg->order + 1) - 1)) && - (nreg->base + BIT(nreg->order)) == nreg1->base && - nreg->order == nreg1->order && - nreg->flags == nreg1->flags) { - nreg->order++; - while (nreg1->order) { - nreg2 = nreg1 + 1; - sbi_memcpy(nreg1, nreg2, sizeof(*nreg1)); - nreg1++; - } - reg_merged = true; - root_memregs_count--; - } - } - } while (reg_merged); + rc = sanitize_domain(&root); + if (rc) { + sbi_printf("%s: sanity checks failed for" + " %s (error %d)\n", __func__, + root.name, rc); + return rc; + } return 0; }