From nobody Thu May 2 12:32:15 2024 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id A73A1C74A5B for ; Sun, 26 Mar 2023 13:43:59 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231985AbjCZNm7 (ORCPT ); Sun, 26 Mar 2023 09:42:59 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:44578 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230123AbjCZNmy (ORCPT ); Sun, 26 Mar 2023 09:42:54 -0400 Received: from ams.source.kernel.org (ams.source.kernel.org [145.40.68.75]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 08F2972AB for ; Sun, 26 Mar 2023 06:42:52 -0700 (PDT) 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 ams.source.kernel.org (Postfix) with ESMTPS id 77C71B80C9A for ; Sun, 26 Mar 2023 13:42:51 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 204DAC433EF; Sun, 26 Mar 2023 13:42:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1679838170; bh=QomJxmHFHEg1D6+6n5cFYGToSzAqlNRqVQNvQ76f0pE=; h=From:Date:Subject:References:In-Reply-To:To:Cc:From; b=D+Sdrs9yVNlYys8gz9LIFR7W4UwRT+pPt3M02zS9/T+iCIerY74bm8BnJUZMpW6Dr Yq7VqJxfT9nl6FtBQOyk0DwJPA52+pFxjolIczpOY9RjS6QiN0DpH1sZrgrlV82OEF o4SsjTvLE2wTkvLcZgjeAuUunNVVfwqEyt8vcioPmvsOqQO9FL2ripJC5xmR+inIg5 EiGIPxusQ3NE0QkoQPs5oFkZU2W2leY8nOuHMyGtQvzuy6X5PUfGu7Dp1uaBjLv35Q h9aiQE+nflrTMIQyTDhbKP4z+rB9kK8R0gGSr5bnITr5XGqakndMt0+NLPGLLBNXVA /a2rE7aqpy6iw== From: Mark Brown Date: Sun, 26 Mar 2023 14:42:38 +0100 Subject: [PATCH v2 1/2] regmap: Factor out single value register syncing MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Message-Id: <20230325-regcache-maple-v2-1-799dcab3ecb1@kernel.org> References: <20230325-regcache-maple-v2-0-799dcab3ecb1@kernel.org> In-Reply-To: <20230325-regcache-maple-v2-0-799dcab3ecb1@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=2689; i=broonie@kernel.org; h=from:subject:message-id; bh=QomJxmHFHEg1D6+6n5cFYGToSzAqlNRqVQNvQ76f0pE=; b=owEBbQGS/pANAwAKASTWi3JdVIfQAcsmYgBkIEvVZtvtk5LqHIofZVwrdWpYutCKKSOUZgBYKqpc rZvCqXeJATMEAAEKAB0WIQSt5miqZ1cYtZ/in+ok1otyXVSH0AUCZCBL1QAKCRAk1otyXVSH0JtzB/ 41ddUryS62ss/+QHOKfK7Xwje0qB/PpTxcabZVNL1tuNehf+GnsMC140hRMR4qPvIhd2A4wUkjU2w8 71Z79RH2pLxYRQ03bxjuzCqvekrO9OyDTQ1gPYmbKXxRjzJuiq472TOi463b7zEPaL5mGLhxNJBgCK z/BxAH6ZKlycr8NKjizwFOyhe4NECoox5D95yXQGX4tJGCd9xdl9CzOzHrv4j+30hIo5o+Na5EcXKf T0aUw8rrakl0Ebgq4LhPbjwptRydT+3rA8cTgbb3U66bcazSwHJ2Gj/mjcCf5bBNRS+YxVipTLu5R5 7vJUq6LQ+DY6njuNWXadFM2Q1YL9kQ X-Developer-Key: i=broonie@kernel.org; a=openpgp; fpr=3F2568AAC26998F9E813A1C5C3F436CA30F5D8EB Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org In order to support sparse caches that don't store data in raw format factor out the parts of the raw block sync implementation that deal with writing a single register via _regmap_write(). Signed-off-by: Mark Brown --- drivers/base/regmap/internal.h | 1 + drivers/base/regmap/regcache.c | 40 ++++++++++++++++++++++++++------------= -- 2 files changed, 27 insertions(+), 14 deletions(-) diff --git a/drivers/base/regmap/internal.h b/drivers/base/regmap/internal.h index 10aca7119d33..7b9ef43bcea6 100644 --- a/drivers/base/regmap/internal.h +++ b/drivers/base/regmap/internal.h @@ -270,6 +270,7 @@ unsigned int regcache_get_val(struct regmap *map, const= void *base, bool regcache_set_val(struct regmap *map, void *base, unsigned int idx, unsigned int val); int regcache_lookup_reg(struct regmap *map, unsigned int reg); +int regcache_sync_val(struct regmap *map, unsigned int reg, unsigned int v= al); =20 int _regmap_raw_write(struct regmap *map, unsigned int reg, const void *val, size_t val_len, bool noinc); diff --git a/drivers/base/regmap/regcache.c b/drivers/base/regmap/regcache.c index d4877099e990..e5d6b535c002 100644 --- a/drivers/base/regmap/regcache.c +++ b/drivers/base/regmap/regcache.c @@ -669,6 +669,30 @@ static bool regcache_reg_present(unsigned long *cache_= present, unsigned int idx) return test_bit(idx, cache_present); } =20 +int regcache_sync_val(struct regmap *map, unsigned int reg, unsigned int v= al) +{ + int ret; + + if (!regcache_reg_needs_sync(map, reg, val)) + return 0; + + map->cache_bypass =3D true; + + ret =3D _regmap_write(map, reg, val); + + map->cache_bypass =3D false; + + if (ret !=3D 0) { + dev_err(map->dev, "Unable to sync register %#x. %d\n", + reg, ret); + return ret; + } + dev_dbg(map->dev, "Synced register %#x, value %#x\n", + reg, val); + + return 0; +} + static int regcache_sync_block_single(struct regmap *map, void *block, unsigned long *cache_present, unsigned int block_base, @@ -685,21 +709,9 @@ static int regcache_sync_block_single(struct regmap *m= ap, void *block, continue; =20 val =3D regcache_get_val(map, block, i); - if (!regcache_reg_needs_sync(map, regtmp, val)) - continue; - - map->cache_bypass =3D true; - - ret =3D _regmap_write(map, regtmp, val); - - map->cache_bypass =3D false; - if (ret !=3D 0) { - dev_err(map->dev, "Unable to sync register %#x. %d\n", - regtmp, ret); + ret =3D regcache_sync_val(map, regtmp, val); + if (ret !=3D 0) return ret; - } - dev_dbg(map->dev, "Synced register %#x, value %#x\n", - regtmp, val); } =20 return 0; --=20 2.34.1 From nobody Thu May 2 12:32:15 2024 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id CB216C6FD1C for ; Sun, 26 Mar 2023 13:43:59 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232009AbjCZNnC (ORCPT ); Sun, 26 Mar 2023 09:43:02 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:44588 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230380AbjCZNmz (ORCPT ); Sun, 26 Mar 2023 09:42:55 -0400 Received: from ams.source.kernel.org (ams.source.kernel.org [145.40.68.75]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 58A3072B3 for ; Sun, 26 Mar 2023 06:42:54 -0700 (PDT) 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 ams.source.kernel.org (Postfix) with ESMTPS id D314DB80C9F for ; Sun, 26 Mar 2023 13:42:52 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 9F279C4339C; Sun, 26 Mar 2023 13:42:50 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1679838171; bh=JzRb0vPHK81K/w4HAdgArDg0c/30xVRY6Pqby/OShLs=; h=From:Date:Subject:References:In-Reply-To:To:Cc:From; b=g8IUwSZ6bkMob6B3d/HMxNHUtG8U3oUP7KRKSCm2xcxPNHeKC/G0/QehtWeewUNjP WNKs9riKHOHbiFWsArm5e0Mm0VFR8z+ttMKi0VPVhutCdhSUhoMJ7/B1HqGCqFP2Hq I/J22Z4u83tlatZhRf19Dm/ZRh38AES6GhQClM4PFpbL1r5EquXHdSZkUfzMMQD9hb Mx1c7BXhnKKgPd//YcvEJF6SgVO/wkT4ZRfSGdBiKcmVklAXnaMv3WGTkjPcuDfdKd 8i0/jPXBC9EG4i5wqaKU3wZAkmhwA192EkUbWJuviPzgaUZ/rICgKjvWXf4JAcol/7 MCuDPQPePRG5A== From: Mark Brown Date: Sun, 26 Mar 2023 14:42:39 +0100 Subject: [PATCH v2 2/2] regmap: Add maple tree based register cache MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Message-Id: <20230325-regcache-maple-v2-2-799dcab3ecb1@kernel.org> References: <20230325-regcache-maple-v2-0-799dcab3ecb1@kernel.org> In-Reply-To: <20230325-regcache-maple-v2-0-799dcab3ecb1@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=10316; i=broonie@kernel.org; h=from:subject:message-id; bh=JzRb0vPHK81K/w4HAdgArDg0c/30xVRY6Pqby/OShLs=; b=owEBbQGS/pANAwAKASTWi3JdVIfQAcsmYgBkIEvWCIaO8pCOMK7FgEyK4AhwWiv319Os5BvuxXSA 1W2k8ZiJATMEAAEKAB0WIQSt5miqZ1cYtZ/in+ok1otyXVSH0AUCZCBL1gAKCRAk1otyXVSH0DJ0B/ 9xxYMJd5jzIzsT97q33UMDe3CnRNuyje2xgCMylVlaRNlMx89ugDcXqQ8iHRozuqFYwP6IAIr8w/Ji 6To0RjkVUVa+FNTs/eCeQfRGMY90GtdRUnL4mZSdx8TkLVyXsolntXLrzX4TIYy3DZBw0XRdfLAykJ LucelvxACMk/q4cUM9Ai+VEcY6OPN6hjxFIkKE+Htv95RhmRaw2Ok3fkbLCnmPQEuwM5gL32n0rv1a HArp1rYqpHoDkmvsC+VBgTqk06qVD7TNbFbV5LWp6Rbw9iacdVKwjNHFu//obOSZoorEBNCGZ30dc2 xsCMQn2ealvTU9rZTLgey5TxuKFjma X-Developer-Key: i=broonie@kernel.org; a=openpgp; fpr=3F2568AAC26998F9E813A1C5C3F436CA30F5D8EB Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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 | 265 +++++++++++++++++++++++++++++++= ++++ drivers/base/regmap/regcache.c | 1 + drivers/base/regmap/regmap-kunit.c | 3 + include/linux/regmap.h | 1 + 6 files changed, 272 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 :=3D -I$(src) =20 obj-$(CONFIG_REGMAP) +=3D regmap.o regcache.o -obj-$(CONFIG_REGMAP) +=3D regcache-rbtree.o regcache-flat.o +obj-$(CONFIG_REGMAP) +=3D regcache-rbtree.o regcache-flat.o regcache-maple= .o obj-$(CONFIG_DEBUG_FS) +=3D regmap-debugfs.o obj-$(CONFIG_REGMAP_KUNIT) +=3D regmap-kunit.o obj-$(CONFIG_REGMAP_AC97) +=3D 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); =20 extern struct regcache_ops regcache_rbtree_ops; +extern struct regcache_ops regcache_maple_ops; extern struct regcache_ops regcache_flat_ops; =20 static inline const char *regmap_name(const struct regmap *map) diff --git a/drivers/base/regmap/regcache-maple.c b/drivers/base/regmap/reg= cache-maple.c new file mode 100644 index 000000000000..07d446b49801 --- /dev/null +++ b/drivers/base/regmap/regcache-maple.c @@ -0,0 +1,265 @@ +// 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 =3D map->cache; + MA_STATE(mas, mt, reg, reg); + unsigned long *entry; + + rcu_read_lock(); + + entry =3D mas_find(&mas, reg); + if (!entry) { + mas_unlock(&mas); + return -ENOENT; + } + + *value =3D 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 =3D 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; + + mas_lock(&mas); + + entry =3D mas_find(&mas, reg); + if (entry) { + entry[reg - mas.index] =3D val; + ret =3D 0; + goto out; + } + + /* Any adjacent entries to extend/merge? */ + mas_set_range(&mas, reg - 1, reg + 1); + index =3D reg; + last =3D reg; + + lower =3D mas_find(&mas, reg - 1); + if (lower) { + index =3D mas.index; + lower_sz =3D (mas.last - mas.index + 1) * sizeof(unsigned long); + } + + upper =3D mas_find(&mas, reg + 1); + if (upper) { + last =3D mas.last; + upper_sz =3D (mas.last - mas.index + 1) * sizeof(unsigned long); + } + + entry =3D kmalloc((last - index + 1) * sizeof(unsigned long), + GFP_KERNEL); + if (!entry) { + ret =3D -ENOMEM; + goto out; + } + + if (lower) + memcpy(entry, lower, lower_sz); + entry[reg - index] =3D val; + if (upper) + memcpy(&entry[reg - index + 1], upper, upper_sz); + + mas_set_range(&mas, index, last); + + ret =3D mas_store_gfp(&mas, entry, GFP_KERNEL); + if (ret =3D=3D 0) { + kfree(lower); + kfree(upper); + } + +out: + mas_unlock(&mas); + + return ret; +} + +static int regcache_maple_drop(struct regmap *map, unsigned int min, + unsigned int max) +{ + struct maple_tree *mt =3D 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 =3D NULL; + upper =3D NULL; + + mas_lock(&mas); + + mas_for_each(&mas, entry, max) { + /* Do we need to save any of this entry? */ + if (mas.index < min) { + lower_index =3D mas.index; + lower_last =3D min -1; + + lower =3D kmemdup(entry, ((min - mas.index) * + sizeof(unsigned long)), + GFP_KERNEL); + if (!lower) { + ret =3D -ENOMEM; + goto out; + } + } + + if (mas.last > max) { + upper_index =3D max + 1; + upper_last =3D mas.last; + + upper =3D kmemdup(&entry[max + 1], + ((mas.last - max) * + sizeof(unsigned long)), + GFP_KERNEL); + if (!upper) { + ret =3D -ENOMEM; + goto out; + } + } + + /* Delete the current entry */ + mas_erase(&mas); + kfree(entry); + + /* Insert new nodes with the saved data */ + if (lower) { + mas_set_range(&mas, lower_index, lower_last); + ret =3D mas_store_gfp(&mas, lower, GFP_KERNEL); + if (ret !=3D 0) + goto out; + lower =3D NULL; + } + + if (upper) { + mas_set_range(&mas, upper_index, upper_last); + ret =3D mas_store_gfp(&mas, upper, GFP_KERNEL); + if (ret !=3D 0) + goto out; + upper =3D 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 =3D map->cache; + unsigned long *entry; + MA_STATE(mas, mt, min, max); + unsigned long lmin =3D min; + unsigned long lmax =3D max; + unsigned int r; + int ret; + + map->cache_bypass =3D true; + + rcu_read_lock(); + + mas_for_each(&mas, entry, max) { + for (r =3D max(mas.index, lmin); r <=3D min(mas.last, lmax); r++) { + ret =3D regcache_sync_val(map, r, entry[r - mas.index]); + if (ret !=3D 0) + goto out; + } + } + +out: + rcu_read_unlock(); + + map->cache_bypass =3D false; + + return ret; +} + +static int regcache_maple_exit(struct regmap *map) +{ + struct maple_tree *mt =3D 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 =3D NULL; + + return 0; +} + +static int regcache_maple_init(struct regmap *map) +{ + struct maple_tree *mt; + int i; + int ret; + + mt =3D kmalloc(sizeof(*mt), GFP_KERNEL); + if (!mt) + return -ENOMEM; + map->cache =3D mt; + + mt_init(mt); + + for (i =3D 0; i < map->num_reg_defaults; i++) { + ret =3D 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 =3D { + .type =3D REGCACHE_MAPLE, + .name =3D "maple", + .init =3D regcache_maple_init, + .exit =3D regcache_maple_exit, + .read =3D regcache_maple_read, + .write =3D regcache_maple_write, + .drop =3D regcache_maple_drop, + .sync =3D 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 @@ =20 static const struct regcache_ops *cache_types[] =3D { ®cache_rbtree_ops, + ®cache_maple_ops, ®cache_flat_ops, }; =20 diff --git a/drivers/base/regmap/regmap-kunit.c b/drivers/base/regmap/regma= p-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[] = =3D { { REGCACHE_NONE, "none" }, { REGCACHE_FLAT, "flat" }, { REGCACHE_RBTREE, "rbtree" }, + { REGCACHE_MAPLE, "maple" }, }; =20 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[] =3D { { REGCACHE_FLAT, "flat" }, { REGCACHE_RBTREE, "rbtree" }, + { REGCACHE_MAPLE, "maple" }, }; =20 KUNIT_ARRAY_PARAM(real_cache_types, real_cache_types_list, case_to_desc); =20 static const struct regcache_types sparse_cache_types_list[] =3D { { REGCACHE_RBTREE, "rbtree" }, + { REGCACHE_MAPLE, "maple" }, }; =20 KUNIT_ARRAY_PARAM(sparse_cache_types, sparse_cache_types_list, case_to_des= c); 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, }; =20 /** --=20 2.34.1