Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
From:   "Liam R. Howlett" <Liam.Howlett@oracle.com>
To:     Andrew Morton <akpm@linux-foundation.org>
Cc:     maple-tree@lists.infradead.org, linux-mm@kvack.org,
        linux-kernel@vger.kernel.org,
        "Paul E . McKenney" <paulmck@kernel.org>,
        Suren Baghdasaryan <surenb@google.com>,
        Matthew Wilcox <willy@infradead.org>,
        "Liam R. Howlett" <Liam.Howlett@oracle.com>
Subject: [PATCH 0/6] maple_tree: Change replacement strategy
Date:   Fri,  4 Aug 2023 12:59:45 -0400
Message-Id: <20230804165951.2661157-1-Liam.Howlett@oracle.com>
Content-Transfer-Encoding: 8bit
Content-Type: text/plain
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?JaCcmV9o+THzNz+ntnKaNuzcMuSEqJUNoL/PQyQwb5QUpBEGLyMSUZ3AJDrS?=
 =?us-ascii?Q?trvOahIo+JSCBckX1kJAAd/BftS+M3MXbXhd/yKAG8v1u0OEOMF2iIEUQlhL?=
 =?us-ascii?Q?PMaiIKgbfFBBFCIEOj5/mHGmfGVdus7Tv7cl/vXguHEs7Cen9GhoMGBSoJgg?=
 =?us-ascii?Q?djZqephAhoXrD9weBlpLFFhjRGeC2eS8DHNTtCONueNaOIVNz1r5TocGq1qO?=
 =?us-ascii?Q?1BtjJXvVe+p46UiC1pZ53+M+qShDq87Lit7xi9hbP57BF6yfvfMdQ2umtr0L?=
 =?us-ascii?Q?nPfF/OOtv09SgwYNMBtXh4E4hSKRQSxcGw212HstNzFdA4mwWmXdldQoehKU?=
 =?us-ascii?Q?60nQwdmUThgR5kI9cYBRcFY5sHndUqfYDEdlYEGLuSBrC1GWujwYlYuh8Cbi?=
 =?us-ascii?Q?B2fziN2OBg/YcailHehHHFnb3w0lLObJVKRlp3x5wW5TWYhBrpHS+5ZFhHLH?=
 =?us-ascii?Q?aMXy/1/K8WNuAVEA7n5qMy1X7ZftF3c/Fa58yyJYdScafXvLIadRT9zR7AbU?=
 =?us-ascii?Q?O9e2QhmLcVLPYZgWcwGOJ+WwBDjlSelpmsYclTwQG8IPrwwlqjps4D1qBNL/?=
 =?us-ascii?Q?rtrxkvhbczENYESZCePFW88eosJRw/lqH9HU1+Wg9ci1T2QthuhXA6WSao84?=
 =?us-ascii?Q?dIXP1uLrUBhUPy3Id9PB4/lUssCk94Juqg/+4D2He4RHVIgW+GI2asr73TCW?=
 =?us-ascii?Q?pySwhC9I+ygWJOHdBieKIhzCleX4LO8cYAvsHTCFMDW7VTT5GdV3ARUcfdSx?=
 =?us-ascii?Q?RCPlTvaBCL8z8f7snCHgvoLcbow9CsYILQBEFcAIWvR1i6bZHfG7s900ApQC?=
 =?us-ascii?Q?VVZF15yEy67ZnXZ61vyf/fl0n9wR/ZBBP0um5roItxWt8jAOgk+rW74rx/Bu?=
 =?us-ascii?Q?o8XoiU6CJCCD3UYooQoILbLhZgrXJAuJf+td7zgF5xY6Km6CxGtcjj+lsj90?=
 =?us-ascii?Q?cUxXdGDbK0jDEj6YJrS3i5u34bFuj50PA015ANbDc7+sQ0RkbH670Yq3YfdX?=
 =?us-ascii?Q?6nWZOvA/7+n8y9CBppDWI6hh45RRFvwjGbMS/3T/QTkZKAwy5sTYMwmZm4E+?=
 =?us-ascii?Q?8KUxSjQ1++o9dB45vF/o/7i7BMreT2fsQyHK4uWTXENX1gcfZUanwtslyjd0?=
 =?us-ascii?Q?8+3QWVoMC+zl3SBlb+mI2KnDZZojTzTITP21cA2rGbKgtdAyjg5avcNi/VuX?=
 =?us-ascii?Q?YWNYgLZglk5moKIET9jy5wysLx2xggygyByAS7hDteveEcgPT9qOoa5QFK6P?=
 =?us-ascii?Q?g4EryKh6ESOjBWc8i1ttaMYAmEUrVbYRLcDFWfC3eracEfGrz7tu7AsyJUaZ?=
 =?us-ascii?Q?Ld+q5wQCAs70iqPat7Cx+jW3gGCIVTracs6Rv5iT1SSsEpLBsrmEXLMqrIDS?=
 =?us-ascii?Q?4u/QzaUM5i0BMtl0qyK07YiQsjfvXsAiJGbtjAjFcbr0GvOCg1HT2BGw97Cj?=
 =?us-ascii?Q?T2KUWb216//f7FbpcOo+pJzW+Vqiu4mw9QMg+X5SVRj8KM60B2oHhVodZE5t?=
 =?us-ascii?Q?xjifuJueJHabLlh8fg6Hnh2ffpfK7ftQn7bagnBEra9PBj9ANw1ktO5QTDO9?=
 =?us-ascii?Q?xDDfLVwHAVMIYDHHXhNsgPz3ao/eXgu4rhJuKpux8fmvSUZPiG1u0oNGRy3N?=
 =?us-ascii?Q?xg=3D=3D?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: =?us-ascii?Q?IrfxQCi8Ca6PCj+g1yES4SPfvyMPLdA+n2Btz6jIARDjTY44t3/2b0Gsg4oG?=
 =?us-ascii?Q?1TUbwp0DjiTd+k9XoNk25rz+UXPD0h5n018j9yOewHHx1y2kS2ktMSH9iHxN?=
 =?us-ascii?Q?TPPQ+yatZTWvyGAfwJEele7DXIu2g5hrrp/ui7B1XsV/ZTt4v4Nbzcbg/Ffh?=
 =?us-ascii?Q?8BTgguKdFUnGSEtQi+fha7eGRWuU/HKZ/Mk+djdbBc+g2iyiv5pMGgD7+g/a?=
 =?us-ascii?Q?i9BwHhCvqSuggwgT1+GrwDdzoOXgQcTC/w/f4u+lU+R54TK/o+qc9U+ZQk/C?=
 =?us-ascii?Q?dfl7UDaLwY1l2U0RAxdV6QXumZPaK6gAVI5tT0LqOJB2V/Jsp4ljL3cUhXep?=
 =?us-ascii?Q?6mwNAkzT1MmmeyQrU7oywtbLsAkDyw7w+B9m47D/cMBasDpKkEpJHj1n9VfD?=
 =?us-ascii?Q?0JOHDZJRnhliufW7+q6C4NcFxkA2V1o2MmNxLshq2iwyaQAcC72wG0vWCNvK?=
 =?us-ascii?Q?f22ygL3/93X0ikUeQQLdicyMQz6BE6njcUvNx3LNeUSrCL1Q4QTFhSZS9eYc?=
 =?us-ascii?Q?UeU1il/bPN2cuTeMdnEqxcXmK1caZAI3Qe1HMUj5vWB+UocYZFm8QifB6Clq?=
 =?us-ascii?Q?tEGC1XUpzC4lABVMqrZl621LZM+Ivtd9xvb/31QH/DyEQYnkKlRV+oa5stoy?=
 =?us-ascii?Q?CMrc5FHZhdcCc4j8/uo1n5VWOAM0ICYpuN91M7dU8DYvjymTHF2+2m+nXxqz?=
 =?us-ascii?Q?91457dRBNoop4Xagti9Xn6HORD45YoaOLJO8B6m0rqtBJRDh5mqSNT5FQQm+?=
 =?us-ascii?Q?B4a+h60rNPdbKpvJ/69XTpTKXaUHL2O1pirgMz4iwWjPM9E6b7TKLqeM2mxT?=
 =?us-ascii?Q?gk3MDQHQn6gNL5AWjm1Wk55MVuW3NGVJ+qNxOonr+oQ2Zc4PXmGHla24yEtu?=
 =?us-ascii?Q?yZ7UXh5WcZzbuBwB1j+XNrMRjbGhTPwdnXDy6RiBjnrP1/iUDPbZ3aVrhkt4?=
 =?us-ascii?Q?vUxwBfdOmY4X1Y7TqF9BNLYvxLRJJ9MXpCKBZtMfjxM=3D?=
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 26ad192b-fcb6-41fa-21d1-08db950c43ea
X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 04 Aug 2023 17:00:11.6020
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: 4e2c6054-71cb-48f1-bd6c-3a9705aca71b
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: kUDiJqTXq7p3htrgXC68BSWtSiMit6lI4oJlXtm3v9VR8YPrKI1vI2rjMDqd5xduWejea0A1bkdwse6q2/5rAg==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: PH0PR10MB4469
X-Proofpoint-Virus-Version: vendor=baseguard
 engine=ICAP:2.0.267,Aquarius:18.0.957,Hydra:6.0.591,FMLib:17.11.176.26
 definitions=2023-08-04_16,2023-08-03_01,2023-05-22_02
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 malwarescore=0 bulkscore=0 phishscore=0
 mlxscore=0 spamscore=0 adultscore=0 suspectscore=0 mlxlogscore=999
 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2306200000
 definitions=main-2308040151
X-Proofpoint-ORIG-GUID: RyiOzTUOroQO_GksT8kJsV_lbK1LpXN3
X-Proofpoint-GUID: RyiOzTUOroQO_GksT8kJsV_lbK1LpXN3
X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED,
        DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_BLOCKED,
        RCVD_IN_MSPIKE_H5,RCVD_IN_MSPIKE_WL,SPF_HELO_NONE,SPF_NONE
        autolearn=ham autolearn_force=no version=3.4.6
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on
        lindbergh.monkeyblade.net
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

The maple tree marks nodes dead as soon as they are going to be
replaced.  This could be problematic when used in the RCU context since
the writer may be starved of CPU time by the readers.  This patch set
addresses the issue by switching the data replacement strategy to one
that will only mark data as dead once the new data is available.

This series changes the ordering of the node replacement so that the new
data is live before the old data is marked 'dead'.  When readers hit
'dead' nodes, they will restart from the top of the tree and end up in
the new data.

In more complex scenarios, the replacement strategy means a subtree is
built and graphed into the tree leaving some nodes to point to the old
parent.  The view of tasks into the old data will either remain with the
old data, or see the new data once the old data is marked 'dead'.

Iterators will see the 'dead' node and restart on their own and switch
to the new data.  There is no risk of the reader seeing old data in
these cases.

The 'dead' subtree of data is then fully marked dead, but reused nodes
will still point to the dead nodes until the parent pointer is updated.
Walking up to a 'dead' node will cause a re-walk from the top of the
tree and enter the new data area where old data is not reachable.

Once the parent pointers are fully up to date in the active data, the
'dead' subtree is iterated to collect entirely 'dead' subtrees, and dead
nodes (nodes that partially contained reused data).

Liam R. Howlett (6):
  maple_tree: Add hex output to maple_arange64 dump
  maple_tree: Reorder replacement of nodes to avoid live lock
  maple_tree: introduce mas_put_in_tree()
  maple_tree: Introduce mas_tree_parent() definition
  maple_tree: Change mas_adopt_children() parent usage
  maple_tree: Replace data before marking dead in split and spanning
    store

 lib/maple_tree.c | 607 +++++++++++++++++++----------------------------
 1 file changed, 240 insertions(+), 367 deletions(-)

-- 
2.39.2