From patchwork Thu Mar 30 00:10:24 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Mark Brown X-Patchwork-Id: 13193316 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 kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id ED27DC77B6D for ; Thu, 30 Mar 2023 00:10:39 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id BB8F36B0075; Wed, 29 Mar 2023 20:10:38 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id B41ED6B0078; Wed, 29 Mar 2023 20:10:38 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 9B9D26B007B; Wed, 29 Mar 2023 20:10:38 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0013.hostedemail.com [216.40.44.13]) by kanga.kvack.org (Postfix) with ESMTP id 8DFAC6B0075 for ; Wed, 29 Mar 2023 20:10:38 -0400 (EDT) Received: from smtpin29.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id 683B61C6532 for ; Thu, 30 Mar 2023 00:10:38 +0000 (UTC) X-FDA: 80623633356.29.F287AD3 Received: from dfw.source.kernel.org (dfw.source.kernel.org [139.178.84.217]) by imf29.hostedemail.com (Postfix) with ESMTP id 8ED97120003 for ; Thu, 30 Mar 2023 00:10:36 +0000 (UTC) Authentication-Results: imf29.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=lckIHN5g; spf=pass (imf29.hostedemail.com: domain of broonie@kernel.org designates 139.178.84.217 as permitted sender) smtp.mailfrom=broonie@kernel.org; dmarc=pass (policy=none) header.from=kernel.org ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1680135036; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=7kKtttYyjbEbpqUYhX+QcKsKPbey+lrJhBEhw+qAoO8=; b=v0DCgABUFzyGn4kEOdA2aEuLQZpn5Y5RcLV+XWnWKMCm3USu1FQubkG8JZSZZdv1Ef5q3m wIHF7vBh+DhW/cKjukZMirybLJBegT8T2uwaz3pE/nc4QTbT6MOsyuKFqToGTHPL0WR+2S 0FWNVDZI8JyYxDmSU0Yr593861RNGaQ= ARC-Authentication-Results: i=1; imf29.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=lckIHN5g; spf=pass (imf29.hostedemail.com: domain of broonie@kernel.org designates 139.178.84.217 as permitted sender) smtp.mailfrom=broonie@kernel.org; dmarc=pass (policy=none) header.from=kernel.org ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1680135036; a=rsa-sha256; cv=none; b=2XpKpXdvAhzUunACPMcp7xtdbk80RNJUN0pKBqEyrK9jleM8hH68iLdF4TNkFmDVLyDO5o ujDboTT4uC12t+V+VXdLrOs9lmXmHLal8Vo2c2frHfb7/52V4jQLt0lsUvY9zY9IBRYGQR hMKES5qimRt52D6od5DIloZYF1pnnN4= Received: from smtp.kernel.org (relay.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dfw.source.kernel.org (Postfix) with ESMTPS id BF22361E9D; Thu, 30 Mar 2023 00:10:35 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 2894AC4339B; Thu, 30 Mar 2023 00:10:33 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1680135035; bh=6o6WJNDaMCZWNhX5s/+/7rfMlV2XHzvRy7uHRedlHjw=; h=From:Date:Subject:References:In-Reply-To:To:Cc:From; b=lckIHN5gJtb8I6eyKBBEOzTc84GkMDD2rBNYDVpq7yX/uA8Ov75QZVLh7vPrMvFYp rLAepCV7ax13zz8XYTPfLPnu69hLbKGH1LS6l0OEEDxMCDJvXPqQl+wj3TR7ubPBj2 FzBJXv/fiWzQE2g+dykVMvYU727pbXq5zi+OM0Sr1pVt5PkvJlICNd/FaDzdeV6hoO FQjnjDBgFLBoB7CeZ17BoHh2E+vhG5zexjM7jINllHiI52BEErAkcVo/J3VUkGhEHt CmDy/lrzR55jIjT4nl9KLs/ScC62mJjvLCtjkNsaAYIAMORpmrFV87mHFrbyk/8Nf8 AN7fm69o3Vyxw== From: Mark Brown Date: Thu, 30 Mar 2023 01:10:24 +0100 Subject: [PATCH v3 2/2] regmap: Add maple tree based register cache MIME-Version: 1.0 Message-Id: <20230325-regcache-maple-v3-2-23e271f93dc7@kernel.org> References: <20230325-regcache-maple-v3-0-23e271f93dc7@kernel.org> In-Reply-To: <20230325-regcache-maple-v3-0-23e271f93dc7@kernel.org> To: "Liam R. Howlett" Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, Mark Brown X-Mailer: b4 0.13-dev-2eb1a X-Developer-Signature: v=1; a=openpgp-sha256; l=10710; i=broonie@kernel.org; h=from:subject:message-id; bh=6o6WJNDaMCZWNhX5s/+/7rfMlV2XHzvRy7uHRedlHjw=; b=owEBbQGS/pANAwAKASTWi3JdVIfQAcsmYgBkJNN0YhF6T8H6UbcT48gje2cpvib0Ny9h0srpTtpE 4KXLaQiJATMEAAEKAB0WIQSt5miqZ1cYtZ/in+ok1otyXVSH0AUCZCTTdAAKCRAk1otyXVSH0DlyB/ 9cmdPXXH0YlC434hrW6oLg0d63akoXmUUM4TmjlZD2G5xuPD9k7KkP8SYfuddAAC8jEvx9aekhAem/ Pu70kXZk4d6ArBAev+Z1gMPwWZRSgNsakWV3fOkHoj81XnVsl/vqb6Z8lsfeT+dWjD6v0JK3qR7jb8 VCIlXT+2cYpsDajC/RuUw3m0EwxjL5kbGOjT5qQVMqmeRDrQnMQ9fquUGu31Gd1U1Z4KoW4PHhyLyC Ui13TiBJDYeuW2eBLnO2srpaLiAfnATwG9R77i+xVhvXZ/i4LotD1pgB3X7NOJd/1gwylIHT+YC5Hc EJyeMZllEV0TPxXHPKPYUbxeRJn/5f X-Developer-Key: i=broonie@kernel.org; a=openpgp; fpr=3F2568AAC26998F9E813A1C5C3F436CA30F5D8EB X-Rspamd-Server: rspam07 X-Rspamd-Queue-Id: 8ED97120003 X-Rspam-User: X-Stat-Signature: i13n69d8mumxpzho57eo64ho9t3pdq61 X-HE-Tag: 1680135036-322446 X-HE-Meta: U2FsdGVkX1/yL5qKIwwzE4vwqTvKg2FJQ0T9Gm2U2IJ39e5ftgJWIpA3VavyD8YoIS1LvjdWW8QWdKYebIK1wvIBXwmHe1uFC4OPKOEkmKe+WuucHtrz97thn8g4nZdACVrz5+DON0PJuxKRQDknPhh3hblWeD7B2+C463vLnzPhD/1aa9j2G9WUsWPTwawKsua78uU3JH2myp/7pB+Umsv3X0AXuuSNhgN+fET7hG4pN86uPLKaNbtMXdHm8YDSoyCzs5gyj4EYyUfHsvg3JtH2TMFLalBzBitmX2e+yJZZo82fTdzXlEHqPfxpkLMEX8TT29mMEuNGLipucnCvaMS3jsEznJMR7+JhmrQK1CIAfog4+HQTCXxGhvMP2LZnZ3ct5Lr568IvviveHBEJmoNCfR72+8kbMIe0N0NNcgOMugIqo4hQsIIRrYCtBlXC08z3oy3GHkvjUcUibDIVIfDHFrsl0dfr+vfkCcCcy47i+92Jia4HNdcBjQEDHF2bkVvxVul+Jl01S0ZU+lTzsp4wkPqItS1EvA7vHLXJicuFA/S1AwqjFd5qkDNYDbng5Va3acg89qpiqsnnJqOJwZAm/tSPYprAqWhmEoNcA5rODltTxQXQDcn7Oh2HTZWamwIY5ayuZrYnD6k6YpN35mRiidj5WXKPMN7x+5PbKhRFwetFWTgkHFtq8+lyTBhOfWuBpPpFrzzJ/iG9IP9Xbfpk0I6cgt7+NXKFCgHaCnChEUwoDyk9xwdyVHOW5FiiTYGLJOwLTlzv3Fj5gmrxXIhqQowyGEOeEbW2iGTewpW1bF4H7v8IUoMSxMlfqKP5h+nDsH+6EmFb+LdOTsWlJdqHOJ7JWa+mcdS9212n9etcCim4HCkkolJbH1vADD0/Mn6efObY+YWpPhS6kJLmKk4/16e+kLbstR0XhoHn2h8iAeMNxdfzUsChsWOPOYCZ4ZFs/Nvvu+DAW4dzXfY cZS0oqbA WdwiyHuVk3OPlV9b4DujcrU7dPPsKXJQ7hoZDsdO98f5csTUk1nIt7qwhJnp1MyuTcdxinjy4sRbsi6+BPtiiT4avjq/JaMNyKxV5SAjuXW4ed0viljKZzZxULKcov6/p1spbw8CPuj347ZXoMzy2m2x58TujRyuostMY2YQr1zWkHJds3IE4/ThGNfpZyEhi2u89Y5iK6OwKBr7IAVd+huT7j5B0nLoY5i+3p/wUGbBO4d4QRGhoGHmmZ+y4Bs5pdIpnFH017AyWRrLujRZhgfHNx00XdyOmdumgc3gd/SdtQq7ku8xqxP65MJARjRsfz1E8yDSL5DY1ce/7c8eUOO93342wFkk+ZoNzBRHt4JcUpmuTIDRqnaQJCnb8EzExWbhPa5gq9I/jz6c= X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: The current state of the art for sparse register maps is the rbtree cache. This works well for most applications but isn't always ideal for sparser register maps since the rbtree can get deep, requiring a lot of walking. Fortunately the kernel has a data structure intended to address this very problem, the maple tree. Provide an initial implementation of a register cache based on the maple tree to start taking advantage of it. The entries stored in the maple tree are arrays of register values, with the maple tree keys holding the register addresses. We store data in host native format rather than device native format as we do for rbtree, this will be a benefit for devices where we don't marshal data within regmap and simplifies the code but will result in additional CPU overhead when syncing the cache on devices where we do marshal data in regmap. This should work well for a lot of devices, though there's some additional areas that could be looked at such as caching the last accessed entry like we do for rbtree and trying to minimise the maple tree level locking. We should also use bulk writes rather than single register writes when resyncing the cache where possible, even if we don't store in device native format. Very small register maps may continue to to better with rbtree longer term. Signed-off-by: Mark Brown --- drivers/base/regmap/Makefile | 2 +- drivers/base/regmap/internal.h | 1 + drivers/base/regmap/regcache-maple.c | 278 +++++++++++++++++++++++++++++++++++ drivers/base/regmap/regcache.c | 1 + drivers/base/regmap/regmap-kunit.c | 3 + include/linux/regmap.h | 1 + 6 files changed, 285 insertions(+), 1 deletion(-) diff --git a/drivers/base/regmap/Makefile b/drivers/base/regmap/Makefile index 4cb73468a197..f6c6cb017200 100644 --- a/drivers/base/regmap/Makefile +++ b/drivers/base/regmap/Makefile @@ -3,7 +3,7 @@ CFLAGS_regmap.o := -I$(src) obj-$(CONFIG_REGMAP) += regmap.o regcache.o -obj-$(CONFIG_REGMAP) += regcache-rbtree.o regcache-flat.o +obj-$(CONFIG_REGMAP) += regcache-rbtree.o regcache-flat.o regcache-maple.o obj-$(CONFIG_DEBUG_FS) += regmap-debugfs.o obj-$(CONFIG_REGMAP_KUNIT) += regmap-kunit.o obj-$(CONFIG_REGMAP_AC97) += regmap-ac97.o diff --git a/drivers/base/regmap/internal.h b/drivers/base/regmap/internal.h index 7b9ef43bcea6..6361df6f553a 100644 --- a/drivers/base/regmap/internal.h +++ b/drivers/base/regmap/internal.h @@ -282,6 +282,7 @@ enum regmap_endian regmap_get_val_endian(struct device *dev, const struct regmap_config *config); extern struct regcache_ops regcache_rbtree_ops; +extern struct regcache_ops regcache_maple_ops; extern struct regcache_ops regcache_flat_ops; static inline const char *regmap_name(const struct regmap *map) diff --git a/drivers/base/regmap/regcache-maple.c b/drivers/base/regmap/regcache-maple.c new file mode 100644 index 000000000000..497cc708d277 --- /dev/null +++ b/drivers/base/regmap/regcache-maple.c @@ -0,0 +1,278 @@ +// SPDX-License-Identifier: GPL-2.0 +// +// Register cache access API - maple tree based cache +// +// Copyright 2023 Arm, Ltd +// +// Author: Mark Brown + +#include +#include +#include +#include + +#include "internal.h" + +static int regcache_maple_read(struct regmap *map, + unsigned int reg, unsigned int *value) +{ + struct maple_tree *mt = map->cache; + MA_STATE(mas, mt, reg, reg); + unsigned long *entry; + + rcu_read_lock(); + + entry = mas_find(&mas, reg); + if (!entry) { + rcu_read_unlock(); + return -ENOENT; + } + + *value = entry[reg - mas.index]; + + rcu_read_unlock(); + + return 0; +} + +static int regcache_maple_write(struct regmap *map, unsigned int reg, + unsigned int val) +{ + struct maple_tree *mt = map->cache; + MA_STATE(mas, mt, reg, reg); + unsigned long *entry, *upper, *lower; + unsigned long index, last; + size_t lower_sz, upper_sz; + int ret; + + rcu_read_lock(); + + entry = mas_find(&mas, reg); + if (entry) { + entry[reg - mas.index] = val; + rcu_read_unlock(); + return 0; + } + + /* Any adjacent entries to extend/merge? */ + mas_set_range(&mas, reg - 1, reg + 1); + index = reg; + last = reg; + + lower = mas_find(&mas, reg - 1); + if (lower) { + index = mas.index; + lower_sz = (mas.last - mas.index + 1) * sizeof(unsigned long); + } + + upper = mas_find(&mas, reg + 1); + if (upper) { + last = mas.last; + upper_sz = (mas.last - mas.index + 1) * sizeof(unsigned long); + } + + rcu_read_unlock(); + + entry = kmalloc((last - index + 1) * sizeof(unsigned long), + GFP_KERNEL); + if (!entry) + return -ENOMEM; + + if (lower) + memcpy(entry, lower, lower_sz); + entry[reg - index] = val; + if (upper) + memcpy(&entry[reg - index + 1], upper, upper_sz); + + /* + * This is safe because the regmap lock means the Maple lock + * is redundant, but we need to take it due to lockdep asserts + * in the maple tree code. + */ + mas_lock(&mas); + + mas_set_range(&mas, index, last); + ret = mas_store_gfp(&mas, entry, GFP_KERNEL); + + mas_unlock(&mas); + + if (ret == 0) { + kfree(lower); + kfree(upper); + } + + return ret; +} + +static int regcache_maple_drop(struct regmap *map, unsigned int min, + unsigned int max) +{ + struct maple_tree *mt = map->cache; + MA_STATE(mas, mt, min, max); + unsigned long *entry, *lower, *upper; + unsigned long lower_index, lower_last; + unsigned long upper_index, upper_last; + int ret; + + lower = NULL; + upper = NULL; + + mas_lock(&mas); + + mas_for_each(&mas, entry, max) { + /* + * This is safe because the regmap lock means the + * Maple lock is redundant, but we need to take it due + * to lockdep asserts in the maple tree code. + */ + mas_unlock(&mas); + + /* Do we need to save any of this entry? */ + if (mas.index < min) { + lower_index = mas.index; + lower_last = min -1; + + lower = kmemdup(entry, ((min - mas.index) * + sizeof(unsigned long)), + GFP_KERNEL); + if (!lower) { + ret = -ENOMEM; + goto out; + } + } + + if (mas.last > max) { + upper_index = max + 1; + upper_last = mas.last; + + upper = kmemdup(&entry[max + 1], + ((mas.last - max) * + sizeof(unsigned long)), + GFP_KERNEL); + if (!upper) { + ret = -ENOMEM; + goto out; + } + } + + kfree(entry); + mas_lock(&mas); + mas_erase(&mas); + + /* Insert new nodes with the saved data */ + if (lower) { + mas_set_range(&mas, lower_index, lower_last); + ret = mas_store_gfp(&mas, lower, GFP_KERNEL); + if (ret != 0) + goto out; + lower = NULL; + } + + if (upper) { + mas_set_range(&mas, upper_index, upper_last); + ret = mas_store_gfp(&mas, upper, GFP_KERNEL); + if (ret != 0) + goto out; + upper = NULL; + } + } + +out: + mas_unlock(&mas); + kfree(lower); + kfree(upper); + + return ret; +} + +static int regcache_maple_sync(struct regmap *map, unsigned int min, + unsigned int max) +{ + struct maple_tree *mt = map->cache; + unsigned long *entry; + MA_STATE(mas, mt, min, max); + unsigned long lmin = min; + unsigned long lmax = max; + unsigned int r; + int ret; + + map->cache_bypass = true; + + rcu_read_lock(); + + mas_for_each(&mas, entry, max) { + for (r = max(mas.index, lmin); r <= min(mas.last, lmax); r++) { + ret = regcache_sync_val(map, r, entry[r - mas.index]); + if (ret != 0) + goto out; + } + } + +out: + rcu_read_unlock(); + + map->cache_bypass = false; + + return ret; +} + +static int regcache_maple_exit(struct regmap *map) +{ + struct maple_tree *mt = map->cache; + MA_STATE(mas, mt, 0, UINT_MAX); + unsigned int *entry;; + + /* if we've already been called then just return */ + if (!mt) + return 0; + + mas_lock(&mas); + mas_for_each(&mas, entry, UINT_MAX) + kfree(entry); + __mt_destroy(mt); + mas_unlock(&mas); + + kfree(mt); + map->cache = NULL; + + return 0; +} + +static int regcache_maple_init(struct regmap *map) +{ + struct maple_tree *mt; + int i; + int ret; + + mt = kmalloc(sizeof(*mt), GFP_KERNEL); + if (!mt) + return -ENOMEM; + map->cache = mt; + + mt_init(mt); + + for (i = 0; i < map->num_reg_defaults; i++) { + ret = regcache_maple_write(map, + map->reg_defaults[i].reg, + map->reg_defaults[i].def); + if (ret) + goto err; + } + + return 0; + +err: + regcache_maple_exit(map); + return ret; +} + +struct regcache_ops regcache_maple_ops = { + .type = REGCACHE_MAPLE, + .name = "maple", + .init = regcache_maple_init, + .exit = regcache_maple_exit, + .read = regcache_maple_read, + .write = regcache_maple_write, + .drop = regcache_maple_drop, + .sync = regcache_maple_sync, +}; diff --git a/drivers/base/regmap/regcache.c b/drivers/base/regmap/regcache.c index e5d6b535c002..0b47721089e6 100644 --- a/drivers/base/regmap/regcache.c +++ b/drivers/base/regmap/regcache.c @@ -17,6 +17,7 @@ static const struct regcache_ops *cache_types[] = { ®cache_rbtree_ops, + ®cache_maple_ops, ®cache_flat_ops, }; diff --git a/drivers/base/regmap/regmap-kunit.c b/drivers/base/regmap/regmap-kunit.c index 6f2bfa4650fe..3486bf9e28b8 100644 --- a/drivers/base/regmap/regmap-kunit.c +++ b/drivers/base/regmap/regmap-kunit.c @@ -29,6 +29,7 @@ static const struct regcache_types regcache_types_list[] = { { REGCACHE_NONE, "none" }, { REGCACHE_FLAT, "flat" }, { REGCACHE_RBTREE, "rbtree" }, + { REGCACHE_MAPLE, "maple" }, }; KUNIT_ARRAY_PARAM(regcache_types, regcache_types_list, case_to_desc); @@ -36,12 +37,14 @@ KUNIT_ARRAY_PARAM(regcache_types, regcache_types_list, case_to_desc); static const struct regcache_types real_cache_types_list[] = { { REGCACHE_FLAT, "flat" }, { REGCACHE_RBTREE, "rbtree" }, + { REGCACHE_MAPLE, "maple" }, }; KUNIT_ARRAY_PARAM(real_cache_types, real_cache_types_list, case_to_desc); static const struct regcache_types sparse_cache_types_list[] = { { REGCACHE_RBTREE, "rbtree" }, + { REGCACHE_MAPLE, "maple" }, }; KUNIT_ARRAY_PARAM(sparse_cache_types, sparse_cache_types_list, case_to_desc); diff --git a/include/linux/regmap.h b/include/linux/regmap.h index 24fc4a9ed1f9..11b360da199d 100644 --- a/include/linux/regmap.h +++ b/include/linux/regmap.h @@ -51,6 +51,7 @@ enum regcache_type { REGCACHE_NONE, REGCACHE_RBTREE, REGCACHE_FLAT, + REGCACHE_MAPLE, }; /**