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 F0D80C76196 for ; Sat, 25 Mar 2023 21:53:49 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id F25DF900003; Sat, 25 Mar 2023 17:53:48 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id ED5DB900002; Sat, 25 Mar 2023 17:53:48 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id DC480900003; Sat, 25 Mar 2023 17:53:48 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0010.hostedemail.com [216.40.44.10]) by kanga.kvack.org (Postfix) with ESMTP id CE7D0900002 for ; Sat, 25 Mar 2023 17:53:48 -0400 (EDT) Received: from smtpin09.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay03.hostedemail.com (Postfix) with ESMTP id 7B653A0309 for ; Sat, 25 Mar 2023 21:53:48 +0000 (UTC) X-FDA: 80608773336.09.D6DB1F6 Received: from ams.source.kernel.org (ams.source.kernel.org [145.40.68.75]) by imf23.hostedemail.com (Postfix) with ESMTP id 91E4E14000B for ; Sat, 25 Mar 2023 21:53:46 +0000 (UTC) Authentication-Results: imf23.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=FR531Owi; spf=pass (imf23.hostedemail.com: domain of broonie@kernel.org designates 145.40.68.75 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=1679781226; 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=cLZm3rl65fgdQjBh8/okbL1ZsSIkKOCeG2OSxrEZtPA=; b=jUsNMOztupalsWh09Kjs2SBtLHjGi670wGTll6Zwxx4moGCOhetb0WmrxzRVQDZu6joo8G dZZKL9zbyngmDnjj94m0shMzCFs81DYn0CCVLSj3tj2ogupS6e7qU7sqiJRG4brxVOtQIj lDngPpiosqZf2SGuSD/rHcWmit6xf8Y= ARC-Authentication-Results: i=1; imf23.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=FR531Owi; spf=pass (imf23.hostedemail.com: domain of broonie@kernel.org designates 145.40.68.75 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=1679781226; a=rsa-sha256; cv=none; b=JapUA4ICrghLpTWTeTb9lXjvTX507NEs8pTER5AP2q6O3i9lLRdb68nNXjO6X7IpjVbSi5 Wf2norF4ZTNMp4wqBqvsRSXZ9AZL5qyPxP1sYNbEk5p3jevd832BaoxXVCUNljpeVSl4Xy kcPvBpw/9e/qKuJzQmGyVvjbJRK4sTc= 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 CDD0CB80A29; Sat, 25 Mar 2023 21:53:44 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 8B70AC433D2; Sat, 25 Mar 2023 21:53:42 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1679781223; bh=V1h8146cmoRln4hPMtI/jWca1lcxyl3oHSMWyVsYMEw=; h=From:Subject:Date:To:Cc:From; b=FR531OwiRabFDRE5hjpL+VbgmFve701nosU0dPxAAHsDUsG0pcYm4/GLPzP+sLO+d GA1+eEMMZGF9QpaYIQmTGtq53IFUSbma0ZjzwImgDszZPTIWw2jpOYOWiXkKUHQOWO KPSNlf5X2dTIGcqHTnZYAx3IVnU+AwtX3K9MpFYqSGggbQ2QesuhqinkkEaRX5SahV ITNg2HAsZsgYHAY5JPS+zfTkuOVpmzZKzvM/Y4YQWzoDsjZvkpqHUo9WQh+Cfgab92 bOtX+Vo7Z7GM/6uM2w2Ib5N3E4q/YW9X3d8Sk1AWN/AxgE1j8DwX7JUdlq8bV1lx2z Vxw3B/knAgxzg== From: Mark Brown Subject: [PATCH 0/2] regmap: Add basic maple tree register cache Date: Sat, 25 Mar 2023 21:52:57 +0000 Message-Id: <20230325-regcache-maple-v1-0-1c76916359fb@kernel.org> MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit X-B4-Tracking: v=1; b=H4sIADltH2QC/x2NwQrCMBAFf6Xs2UCaWBV/RXrYrq/NoqZlAyqU/ rupxxkYZqUCUxS6NisZ3lp0zhXaQ0OSOE9weq9MwYfoY+icYRKWBPfi5QkXT0ecu0sroxeq0cA FbjDOkvbsM9tj14th1O//c+u37Qdm1kghdwAAAA== 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=2382; i=broonie@kernel.org; h=from:subject:message-id; bh=V1h8146cmoRln4hPMtI/jWca1lcxyl3oHSMWyVsYMEw=; b=owEBbQGS/pANAwAKASTWi3JdVIfQAcsmYgBkH21jKBq4A6rXdP4NSuSGsCl/C4mZFqou8XpoNRbf +ChIV26JATMEAAEKAB0WIQSt5miqZ1cYtZ/in+ok1otyXVSH0AUCZB9tYwAKCRAk1otyXVSH0OSIB/ 9eRVDZm51+9jLcBMCKiKSoKt7LUPGSQgjL2ghAziWItq1sUXirx3OXxPSnLcSHoSquEbwVlrMSkmCz IM+bZwpOiVhXJ7Vms7BUfziK15wJf4PIf4r+ObH1RbRIDpXMlIM0jhR1ZtZCIki+T4XV8aPO4p8e6s 63uZVGHYOTqT+Y4OTfivzvZRdti8eOJFklNfFbtR/zYdoXZ6t9lK6FkiY3vHt8OvMYHaUNvtVyMTgW pxONWmiXOlqrRnB8gFb3xAAjfbMLS9r/zmApSyXe/OeuJ+fJ9XHev+/6TF4EWR6wFLZCm6AJ3WAx/p lFeJiufqLh9otps0se13LZtNswgOeD X-Developer-Key: i=broonie@kernel.org; a=openpgp; fpr=3F2568AAC26998F9E813A1C5C3F436CA30F5D8EB X-Rspamd-Queue-Id: 91E4E14000B X-Stat-Signature: ciokx8imysdj9k6modurfczsztuebsrj X-Rspam-User: X-Rspamd-Server: rspam08 X-HE-Tag: 1679781226-507983 X-HE-Meta: U2FsdGVkX18FVpVU8EH7VlOxEJpArB1vHHwDCgOZC6Pl3qWfj54KBHi9FGcAFF+BEfKjC4E5G8sXp7Ms2cRrPLH/blc6sfVCNQc/zPJtdVnq02qXikkkcR+G7BWkMmJCcT7++/wQEuZdkS+WAroGZiGGJEXCmXHBZKhco+jCdF6g6SRB0DPPMVwpEqaZoHssBNnYSVfluEBBlzS9Pd0IzKFHSlyeQ/LiqhvsdV6c2E/tgd35BDiFXhyRwJqGWEHnFF7eX71yVlTOPfcZX0HyGe7JOMkAVRTF42MWlW6SGtbjN9vfyguG3BCGtnLfacwrzvmeWV5csTz6VTjrS9Y4kb9u/PUDYaXOhBD82cdXCkkMGryzpDQ0XyS+P0J1mU1RpjNsvMtF9xgk5976/s8nne4xzWw7pzeeId+FrCJO+aRl1Io9ZzH4UpM9S5RAztEUJhp67lqD+iKhziiqpsdoQhLDuScqUK/X3gi0qKybAgDBOxLUjZZU2bBo3fcRJ1wFI3bnoTo2U/VpOZakFMq6A1ksa+WPh+V2cORCNG7aknS667zA1wNj3r+GuiY263OEbg3JDMS5/GNwTABH6NTT1pp74m89fMudg3Zjqa3hyQFgqBiTvPRiqHPC9gL3LLptJz+p/SmrPGF39RRl+7NjihnwLGp1lAqmo58wm8tVrYA4l2hWE4fLh4dRw3x8uMZgy4CALhTNBdbZUT+zvB3AG1YyUGLs5/Z+xfqK7JHYMt9mWLjBo480/z4iA9UP7Sj8/GcQDWTBSwtxqLggweZIQIF+4Q9nG2lE8l9ODKAzSwaNAR0WRbSp3hqcVdwVvxV6na5119LGmAnk341RJ5GnvNj5/3kbj/iJyN5O250lzmOggdrklUECpJc6Az5yyEyYG+cVMTwiVwMp/WiVZTGcewlvn3Ob0TV/WBICQmo/21OjP6G3E+zI6YLT6biGx8nNKaeznFk6eHUbJMs3n06 afX4Brmj sNOYqWUAjGDAE/67Bn0o1Hk8PKR14SZZEguwNwY3hVRgkUWMLfxHs9B3QFgtpHP+q8gdiymQ19Zwi5iNc9Rwlr6l7sN7eG+qPWBs0oJ7GVY4BJZfwi9P34GG8Je44YK7tja9vRF+V29lxGCnKjxlmwGTZpYD5wgidO25fvaVTZO5pQTDWe+irv6MI/0MKtrKbGe9qdkV3yTF2Xh4= 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. This series depends on a number of patches sent previously and separately, including KUnit support and some core fixes and features. 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 | 154 +++++++++++++++++++++++++++++++++++ drivers/base/regmap/regcache.c | 41 ++++++---- drivers/base/regmap/regmap-kunit.c | 3 + include/linux/regmap.h | 1 + 6 files changed, 188 insertions(+), 15 deletions(-) --- base-commit: c20bc1c03695287bd19922a32052f2bc7d4a462d change-id: 20230325-regcache-maple-364e7581cf0c Best regards, -- Mark Brown