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 CDE1EC74A5B for ; Thu, 30 Mar 2023 00:10:37 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 4B2B76B0072; Wed, 29 Mar 2023 20:10:37 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 462E86B0074; Wed, 29 Mar 2023 20:10:37 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 32A236B0075; Wed, 29 Mar 2023 20:10:37 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0015.hostedemail.com [216.40.44.15]) by kanga.kvack.org (Postfix) with ESMTP id 2257C6B0072 for ; Wed, 29 Mar 2023 20:10:37 -0400 (EDT) Received: from smtpin04.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay08.hostedemail.com (Postfix) with ESMTP id E60791401AD for ; Thu, 30 Mar 2023 00:10:36 +0000 (UTC) X-FDA: 80623633272.04.A1EB3A8 Received: from ams.source.kernel.org (ams.source.kernel.org [145.40.68.75]) by imf06.hostedemail.com (Postfix) with ESMTP id 08019180007 for ; Thu, 30 Mar 2023 00:10:34 +0000 (UTC) Authentication-Results: imf06.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=bsquifgR; dmarc=pass (policy=none) header.from=kernel.org; spf=pass (imf06.hostedemail.com: domain of broonie@kernel.org designates 145.40.68.75 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=1680135035; 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: references:dkim-signature; bh=lsZ2l0/QNB/prrsM5YGsD/Vo+9SMfpTbxujm4teifpc=; b=BjCyNz4RW5uCMtey2vdg5pto/eOhUxJ4gACLwHrSwCjYhull+9qH8aFsk+4FGMwYd9KIBj B230m5Z1GD+MRKUily52nMXj9pJUjkK8YslQGOGO2TCSP479RILWmmMdEKSvSybO4kFdiK 8Rd3jyV7oBTkQCqz883GFqNIhzKryNM= ARC-Authentication-Results: i=1; imf06.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=bsquifgR; dmarc=pass (policy=none) header.from=kernel.org; spf=pass (imf06.hostedemail.com: domain of broonie@kernel.org designates 145.40.68.75 as permitted sender) smtp.mailfrom=broonie@kernel.org ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1680135035; a=rsa-sha256; cv=none; b=PGh+flhPGqkAZxcohcJy5UbbilATnaJNCT4+v1ATfzUn6x1CbpAJQ/Qi0l78QNT5+6isoy zP1jN1jRvOE//zF0ydhH4iRNoL9eOyksLZ/F/dXPTpE2z2+j+O2/lV0jciephKEEiNtOKL 4r/aIro7eD+u3sX27ydOKcw6+bXvC7U= 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 10D46B8254C; Thu, 30 Mar 2023 00:10:33 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 43325C433D2; Thu, 30 Mar 2023 00:10:30 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1680135031; bh=6OPjRtreFodTiugCaVKFhgY12JIHQ2V9CaXtnSdw8Rc=; h=From:Subject:Date:To:Cc:From; b=bsquifgRZ0k+oUcruQ1HwsXXh0uScmGwCV57uNW4GD9j9daZ8IGrmoZxgqUSg8k96 yYLV+l2+a96YOMPovoxp2sNfgxiODTIRBvWSQ3Fq4GvzZllLsSTF2dDQ5EiRb+4LYe PprUTdEi1cW6j/28b89OwJzve31fTxHsrDFElHOsSopfXl706Od9qGp3ontZKOorbf YwO+KKYNOZ6dLT/gQ2tSRBx3bkM6ARbmSTlD2BW6x/Ush+Nkv13ScJ+tMUJ2uqwoU4 rY1luC3XWjZZR1iN4ectqUa/62Xhjt28wjqo7+JzSsBCZrlFabI2xrtRBLcFeGv8m1 Z5iZm0K56TFiQ== From: Mark Brown Subject: [PATCH v3 0/2] regmap: Add basic maple tree register cache Date: Thu, 30 Mar 2023 01:10:22 +0100 Message-Id: <20230325-regcache-maple-v3-0-23e271f93dc7@kernel.org> MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit X-B4-Tracking: v=1; b=H4sIAG7TJGQC/32Nyw6CMBBFf4V0bU0fAuLK/zAu2mGgDdqSqUEN4 d8t7Fzo8tzk3DOzhOQxsVMxM8LJJx9DBr0rGDgTeuS+zcyUUFpoVXLCHgw45Hcz3pDr6oB1eZT QCWBZsiYht2QCuFV7RhrWeSTs/GvrXK6ZnU+PSO8tO8l1/VmYJBdcQl01stJl09nzgBTwto/Us /VrUv99lf26aVowViNY+eUvy/IBY0jyYwQBAAA= 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=2788; i=broonie@kernel.org; h=from:subject:message-id; bh=6OPjRtreFodTiugCaVKFhgY12JIHQ2V9CaXtnSdw8Rc=; b=owEBbQGS/pANAwAKASTWi3JdVIfQAcsmYgBkJNNzzr+9LxrwDPG5XfGItP6QTjQ/mBYELIWGvCbc s2743/CJATMEAAEKAB0WIQSt5miqZ1cYtZ/in+ok1otyXVSH0AUCZCTTcwAKCRAk1otyXVSH0GGqB/ 4wtxI82fzlEQJF/rlWcRT3jvziNKNPRD5sm5oN4TKPAp4PZWcleeTsucGk7IU/9wBNQGjLGMWu3ti/ lq48jW1Bij0L06A0gxzaRJPu5aMs5my5J2MN4yFus2S0iB3otdV4kMo22WzBVx3RfCy9VEOjismb/1 ibPtZPZ/OqVaWpGCNlH4WIhaCG9+/xxIelNQWmjy+3hO2wh5oq9fjyWRTok4bmFI+t+RRm6wtkaMY0 69eB7wD798JCBXgjBVgszoBvxUE3mkbqnKXdHNde7aXA3vv7dKHIf/oWLssXtWeV2RkfUYUQJ9lyYK f/mY+skqc8qtF7L2O2bu5wbJU/6d1K X-Developer-Key: i=broonie@kernel.org; a=openpgp; fpr=3F2568AAC26998F9E813A1C5C3F436CA30F5D8EB X-Rspam-User: X-Rspamd-Server: rspam02 X-Rspamd-Queue-Id: 08019180007 X-Stat-Signature: kpuixb8szhdf3owbr69ir9qz5kpt1u9f X-HE-Tag: 1680135034-757008 X-HE-Meta: U2FsdGVkX1+JpjeBIyiW4cBiTam6GRW+nCZOKq1LDY5FRnMgAmsnA+DSEHJp3g6jjUvh4cCRsg08TnPei7kkLMgi0RPERpmpev4OIV7LtHsm/b9fV9AxPso+2gPZypgsu/YoLqokRYCyqwt0Ccrv4ewIgV2LBW1UAgC5pbd3vUXbiPUkCI1QzSPc9cmqcprlAf/ZqExT2w6DMv4XOUHnq0dcwoN00czEmUythyeHjqSUOKW1/X1PH7UGy+h4uGyCezIwxz17GX3FzNeVycQQXwxFvjBxOA1Lmk4U8KamjODa/nDwJGBcEvkzUQwjsFA9wRwatuenCdUFntW3FNT6Tm0C6SYZsQYLvpmrEGUoDNEE98wYC5m/TGZbdaAemyCucmaD3lkMZ67aO/Tc2M1jAPCGciVIUGislJQ0rLLlExnv6rdDzltk//wB1ydZNs8mWyK41h7rxHJS4MOPWTKKSlgBOBy83K+ILGnjetLnvtkXZGHeWqQZeaATgZtaACRbvEh/N5LFGICgSd5IWjWH6bnjpCw7kAqi4zcaeQiYjlMcz+jCtnIrdWKR9dJ/DLx7V65w4lFZRYmdtVHNHAF0gt/G4MgrYk+756E/PXOW1iyhRe8p9dRpvYB6UKACEqKqt6xNZTQBZhgGMQWh5s2ImnHEkjUBf8b9W3r0tVyx+yjOxL8iGsFb7dMRrzgMtjVMKl/fETqgvqMdaitvFZs9AWDhi1MiQlI1Wy5NnW29NXWM3fYlykhbEQLIk65jNGqBoxv7X5pqlVtGQi+p7K2puW/TJR0dXnS8uxsN4APzCtdcM8+aOgbrqWz9o4KoIJcC7HnP0p3z7CQ3AT/2f1G5QUrO19qes42kLA92kjLEKuuX2vYrv6Hxnap+IbYhIPylENbRXPGqmfhN2RdGLd8VfMzxgWaZ03VCEkDXIm3JlrVjfo3UngGUzxs+kMlr20KFJbDoDEzB9PK8YmdAS8A NcLBIjtr tIklR7tl5R7AivAkGfJS8g4Vyw8+fEvBZpB8oupk2wuBL6hP2GbfwnIXyJQFzbQFlCJzyXprYYMl1+YN6mgeEC6VMsu9sruFCnApRmE29eYrVNA4UABUwauTGZq3uI8yyiACOcW8SI8CqTnBTXKT2PyZl8mJln4uqo0z9YTXHQKbdHYosUfq8l3xZMcoPi/CRamDHP1NZjGT7dm4= 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 syncing the cache where possible, even if we don't store in device native format, and there is room for improvement in how we load register defaults into the cache. Very small register maps may continue to to better with rbtree longer term, though the difference should become marginal especially in the context of the cost of register I/O. Changes in v3: - Rework locking so we don't allocate with the Maple lock. - Link to v2: https://lore.kernel.org/r/20230325-regcache-maple-v2-0-799dcab3ecb1@kernel.org Changes in v2: - Rework to store multiple values per maple tree node with coalescing, bringing us much closer to the state of the art with rbtree. - Add locking required for maple tree usage. - Use more efficent code suggested by Liam to free the register map. - Link to v1: https://lore.kernel.org/r/20230325-regcache-maple-v1-0-1c76916359fb@kernel.org Signed-off-by: Mark Brown --- Mark Brown (2): regmap: Factor out single value register syncing regmap: Add maple tree based register cache drivers/base/regmap/Makefile | 2 +- drivers/base/regmap/internal.h | 2 + drivers/base/regmap/regcache-maple.c | 278 +++++++++++++++++++++++++++++++++++ drivers/base/regmap/regcache.c | 41 ++++-- drivers/base/regmap/regmap-kunit.c | 3 + include/linux/regmap.h | 1 + 6 files changed, 312 insertions(+), 15 deletions(-) --- base-commit: c20bc1c03695287bd19922a32052f2bc7d4a462d change-id: 20230325-regcache-maple-364e7581cf0c Best regards, -- Mark Brown