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 kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 4CE92C6FD1C for ; Sat, 25 Mar 2023 21:53:51 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 6268C900004; Sat, 25 Mar 2023 17:53:50 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 5AFA4900002; Sat, 25 Mar 2023 17:53:50 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 44F3F900004; Sat, 25 Mar 2023 17:53:50 -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 3884B900002 for ; Sat, 25 Mar 2023 17:53:50 -0400 (EDT) Received: from smtpin01.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id D514D80305 for ; Sat, 25 Mar 2023 21:53:49 +0000 (UTC) X-FDA: 80608773378.01.03E8628 Received: from dfw.source.kernel.org (dfw.source.kernel.org [139.178.84.217]) by imf03.hostedemail.com (Postfix) with ESMTP id 11FAC20010 for ; Sat, 25 Mar 2023 21:53:47 +0000 (UTC) Authentication-Results: imf03.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=joWShSYs; dmarc=pass (policy=none) header.from=kernel.org; spf=pass (imf03.hostedemail.com: domain of broonie@kernel.org designates 139.178.84.217 as permitted sender) smtp.mailfrom=broonie@kernel.org ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1679781228; 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=5vSS2kl4pfXKCA2M+EiCBivqfGWKskPxLgF/ApXT2V4=; b=n3QP+29oIODOW+gdnHas2Wh7MKE2lMJHdNeUOZwuNg2uPjekvbCpS10o5F5455+Us5l/oz D8mlnOEOMzLuS9hWZyrUpcO8aIz4qLPU3rFT5p9VHxjGXDVrIO/XxfD3mJKxwFG/37e365 1tiQNkbh1WvjdgaJaQlhZv4vCA2Hvco= ARC-Authentication-Results: i=1; imf03.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=joWShSYs; dmarc=pass (policy=none) header.from=kernel.org; spf=pass (imf03.hostedemail.com: domain of broonie@kernel.org designates 139.178.84.217 as permitted sender) smtp.mailfrom=broonie@kernel.org ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1679781228; a=rsa-sha256; cv=none; b=0NaCwYweGa51DBLitt5Gw8bT/CkA3YP+/fhljXUBz8tsXv6fONo6pC5b/orAHCEaY1Dqcn XGVG10QzFbrbp6x4W1FDdPXfgtElR/XgLfSL5oqVr2APFG8qNOKvkmn4a4Gcntl2tOcqIm 6WWEVFc6es3ic6XXZFj5oOKmhjgjzZU= 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 E284C60C7F; Sat, 25 Mar 2023 21:53:46 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 69AEFC433EF; Sat, 25 Mar 2023 21:53:45 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1679781226; bh=q/ZvsHZA/zVTwNk2IyUTWYt6K7dSG3s3+2BXFFIMbwM=; h=From:Date:Subject:References:In-Reply-To:To:Cc:From; b=joWShSYsC2qo/RI1UApgbOXmT79KGvcJQ0TF5W1ZjOVSfRiGcIykqy5HHNJlmrf07 JAANONJ73xFwtf2b5BWbSLj0KXQ/U6lX5ZB7Q/gqGWiOhA8WVuVQjZF08cjreWK/NB NPen08cyImpSEMAvo/8lRLejew3l1O8uq5nfmY2roFFx4HNyJexdyny7nlejdJofJd xEo18rEkK6epgTzWmMfiQ66HbsTULHR4JMzIxS7Xsey6S733sEaZ07tzf0NXVkeXyG 6WwPp7HsgCtdhDLof96MNDV13CZ7WB6xptib9715tOSAepVZVPKrEbscjeD5IukpDF NPaxq1CJvmXsA== From: Mark Brown Date: Sat, 25 Mar 2023 21:52:59 +0000 Subject: [PATCH 2/2] regmap: Add maple tree based register cache MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit Message-Id: <20230325-regcache-maple-v1-2-1c76916359fb@kernel.org> References: <20230325-regcache-maple-v1-0-1c76916359fb@kernel.org> In-Reply-To: <20230325-regcache-maple-v1-0-1c76916359fb@kernel.org> To: "Liam R. Howlett" Cc: linux-mm@kvack.org, Mark Brown X-Mailer: b4 0.13-dev-2eb1a X-Developer-Signature: v=1; a=openpgp-sha256; l=8142; i=broonie@kernel.org; h=from:subject:message-id; bh=q/ZvsHZA/zVTwNk2IyUTWYt6K7dSG3s3+2BXFFIMbwM=; b=owEBbQGS/pANAwAKASTWi3JdVIfQAcsmYgBkH21lbmFVaGfVF0UDDzZZAxQSpQN1JQxbbWQXcrus 4jDzb92JATMEAAEKAB0WIQSt5miqZ1cYtZ/in+ok1otyXVSH0AUCZB9tZQAKCRAk1otyXVSH0NvpB/ 9luVvAdfHHxw51kG7knKme5M0B/Ax0fLknaNNkzjgFHvIgcmnAmiuc+OSqMMRMm9ayzuAmSwmysYgI t5zweRchrKNSRA+HWgxmoGtbJx/kQu0A6S1R5NUUw4FdS7AVrp0Mgl9nDX4O5c41DrhZIBeXFWrxp0 GHNL39GtbXKDXmQ4A2DoPJZ/dUFSTTrg4MMLT2enwfjPehjkySPI1PjNKcxphqQeZI3a3aUURfGd/x TRQwJS0b544CtYhVaSI7GSqECMbw80CsLx7mKE8ohJaOsDKtVYa6DFFpYBZQfCxGmPKOWBIbsq3zcb lbmJoHin8Jwj1xRNGaULdmn7vi7hi/ X-Developer-Key: i=broonie@kernel.org; a=openpgp; fpr=3F2568AAC26998F9E813A1C5C3F436CA30F5D8EB X-Rspam-User: X-Rspamd-Server: rspam02 X-Rspamd-Queue-Id: 11FAC20010 X-Stat-Signature: 9emygz4xzq89yez3m8jyjygaehgfhfng X-HE-Tag: 1679781227-689609 X-HE-Meta: U2FsdGVkX19MJThi+MauK53MX1atsy6Lwn/nYlGbxcP/1RoeUA/9XxfzcvycJ5GKUnH4U3UDDj9PXDkhSxRLWszQC4a7g3ntaGQOH1hd+bscPC+J8pAw1ySFk8FCBqbjo3t759Tu/MuHUMuD58rqunVwe4vIKdpgjcqCWKj5/WcuSMrZLdpukpZpcKayLDfBRqy8p+5TCxYZqBoWBMqF2Xg9mFf90ll0s9SvjlnfZmi70nyPfF8/cTO4DEVykon5QfI1okJVQs8gUDpX+GLBIjyLS3+Fkff+JqMpIl/ZGAWm1QIzWd4dFLKjmr9tGR5ZM8WNT2o4kh8p5V3NWEWGzzSTEjxdOH5ui9qT1Kcsg4GAbvUiRW4N+HQqSPoDDnfmJwkFli+tf15QHhi3aWs83DyT3wLPNSdmiu4dXDoFdFYgPBogYI/LDJz9XhZmap9nY74MvFUYIHvy7+FT8YbJ7SEVhNCVb8oMmZ5VyZqmw6CJlgwhIMNULp5f75EqOy93sgt4iNFRCOqyeaO3WRbHRRa4G3MzH6y912nYxn11sviMRpb1Dqa0GW0/HO1mw9q6F740OePLoI8H0q8k551p7x4JXeZE3/ICGMtOteKkv73hsl97ybXk7UZoGhxv3To6IqFA1sUv5eFY+VXtClLMh8I4KgL2vi9gwQkaWfUp8CGb+NAfwbStzi+k2UeKHnIseQOQ/4NOpJO+c1w8mifUlm2nGzb1Qe4sf1f5Oh/Scfhkmz2RdLuFCM5dAA7mUPZrGGInmZsPJfe83AXH+6iMq3ujvreCbHelGEo4GJykqTL39mnIpFP57+xbaEqJt/VceRh8Ab/a/uONjnOLGHW0y37Wr2R0/UFqpnfLPLQq8o8EQfbSbSthuElvz6bH0nWDHt9c6nHgT3lOlS8xre/+NZUEtC0g+uyYX69MFmeFV3Z5U4sEeBSUr9eYguuGfGbquxzPld9pDcxjlKfUMYk WqmzkD0n 6GO6P0KFrxJBV+EFcApxwNsjgw0yUsTDRbdf+WvHK0xPoN71D/N+xHFqWfKiYiDdkeqQ5dgLyccwhojpVNCLgqo8TEmo4womGqojQ7ShRxuUPkCF7VrLZLlakJXOkdbe39BnCSKrDg/stGgvCgTdWS4QVsyeg1XjWqR4zQiE2ncZkndiAeG+B7HNlJLCw0tuHyuzY3xFp88lhJ8a8MAEuMLFhD2uhBoVSQCKye4AnOUdFdcChxlARpWM4NLoM+z5S4ItWYWHPlo78zdHbDJNMUh7/zZFZA/Qp1LaO6dhw5wnheuGuGUzb60iKoxc1Km3+xCQ4oAi5OWnY68+lF22nRQ5k2+cCVoSBual7+fXtxrkpUgwpa879dGJqjui5SXCWn2AgeCTZLPcvb7mkdQ9C3zya8naI1z7a7NS5+SHs+n3KEWBNj50Kh6N0ZQ== 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. This initial implementation is very simplistic and doesn't take full advantage of the capabilities of the maple tree, we simply store each register as a single value within the tree. Since maple tree values are pointers and iteration doesn't naturally give us the key we allocate a small structure for each register, effectively adding another layer to the tree. We also 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 until we are able to store more than one register in a node there's no reason to have preformatted data even where we do marshal. This works well enough to get started and should already work well for some devices but there is a great deal of room for improvement, as well as storing blocks rather than just individual registers we don't need the locking that the maple tree does and are likely to benefit from caching the last accessed entry. 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 | 154 +++++++++++++++++++++++++++++++++++ drivers/base/regmap/regcache.c | 1 + drivers/base/regmap/regmap-kunit.c | 3 + include/linux/regmap.h | 1 + 6 files changed, 161 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..a18966aed27e --- /dev/null +++ b/drivers/base/regmap/regcache-maple.c @@ -0,0 +1,154 @@ +// 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" + +struct cache_entry { + unsigned int reg; + unsigned int val; +}; + +static int regcache_maple_read(struct regmap *map, + unsigned int reg, unsigned int *value) +{ + struct maple_tree *mt = map->cache; + struct cache_entry *entry; + + entry = mtree_load(mt, reg); + if (!entry) + return -ENOENT; + + *value = entry->val; + + 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); + struct cache_entry *entry; + int ret; + + entry = mas_find(&mas, reg); + if (entry) { + entry->val = val; + return 0; + } + + entry = kmalloc(sizeof(*entry), GFP_KERNEL); + if (!entry) + return -ENOMEM; + + entry->reg = reg; + entry->val = val; + + ret = mtree_store(mt, reg, entry, GFP_KERNEL); + if (ret != 0) + kfree(entry); + + 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); + struct cache_entry *entry; + + for (entry = mas_find(&mas, min); entry; entry = mas_next(&mas, max)) { + kfree(entry); + mas_erase(&mas); + } + + return 0; +} + +static int regcache_maple_sync(struct regmap *map, unsigned int min, + unsigned int max) +{ + struct maple_tree *mt = map->cache; + struct cache_entry *entry; + MA_STATE(mas, mt, min, max); + int ret; + + map->cache_bypass = true; + + for (entry = mas_find(&mas, min); entry; entry = mas_next(&mas, max)) { + ret = regcache_sync_val(map, entry->reg, entry->val); + if (ret != 0) + goto out; + } + +out: + map->cache_bypass = false; + + return ret; +} + +static int regcache_maple_exit(struct regmap *map) +{ + struct maple_tree *mt = map->cache; + + /* if we've already been called then just return */ + if (!mt) + return 0; + + regcache_maple_drop(map, 0, UINT_MAX); + + 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, }; /** -- 2.34.1