From patchwork Thu Nov 14 17:05:19 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sidhartha Kumar X-Patchwork-Id: 13875505 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 361D1D637D4 for ; Thu, 14 Nov 2024 17:06:15 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id A96156B0093; Thu, 14 Nov 2024 12:06:14 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id A1DC96B009E; Thu, 14 Nov 2024 12:06:14 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 898366B00A3; Thu, 14 Nov 2024 12:06:14 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by kanga.kvack.org (Postfix) with ESMTP id 6802D6B0093 for ; Thu, 14 Nov 2024 12:06:14 -0500 (EST) Received: from smtpin05.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay05.hostedemail.com (Postfix) with ESMTP id 07C0C4133D for ; Thu, 14 Nov 2024 17:06:14 +0000 (UTC) X-FDA: 82785327618.05.A7FC1D7 Received: from mx0b-00069f02.pphosted.com (mx0b-00069f02.pphosted.com [205.220.177.32]) by imf12.hostedemail.com (Postfix) with ESMTP id 4DA31400FD for ; Thu, 14 Nov 2024 17:05:10 +0000 (UTC) Authentication-Results: imf12.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=FuybvMBm; spf=pass (imf12.hostedemail.com: domain of sidhartha.kumar@oracle.com designates 205.220.177.32 as permitted sender) smtp.mailfrom=sidhartha.kumar@oracle.com; dmarc=pass (policy=reject) header.from=oracle.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1731603755; 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-transfer-encoding:content-transfer-encoding: in-reply-to:references:dkim-signature; bh=FFFolayj59SPa6a5ry3K7EO1JG669hS35arha73WQKk=; b=uZX8eg28NBB9klciWbzRIWLhin4xIJi91VmIMRNSZbYLSPzQGjUGhHuwsRzmLabzWD4JBn NHKINB/pGmvfXJ3n9TFDkziyYR/IBsXd4blJbiHXtuqwVO9YMGk7uMCOzfr/OlHt3AcQ3R +CBeDL1n1RNy18Mv9RKFjt1vDyIijHQ= ARC-Authentication-Results: i=1; imf12.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=FuybvMBm; spf=pass (imf12.hostedemail.com: domain of sidhartha.kumar@oracle.com designates 205.220.177.32 as permitted sender) smtp.mailfrom=sidhartha.kumar@oracle.com; dmarc=pass (policy=reject) header.from=oracle.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1731603755; a=rsa-sha256; cv=none; b=uRjncrepXJfUig+L1eyBTPNWuUXwGsOxX5Yo2BfSOv+/e2e4uGBgkdeY4tWrTapCKT0DoK 30x7w99MsIxVh+89DASgz0m/g+cpKYk5KdIGbemUkDKjMA2DvKgCLWd5reuX4gPsbgBC72 xd7dtC9d1/Mt8GlVf4ADRsVpFtQWQEk= Received: from pps.filterd (m0246632.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.18.1.2/8.18.1.2) with ESMTP id 4AEDHSw8025082; Thu, 14 Nov 2024 17:05:28 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=cc :content-transfer-encoding:date:from:message-id:mime-version :subject:to; s=corp-2023-11-20; bh=FFFolayj59SPa6a5ry3K7EO1JG669 hS35arha73WQKk=; b=FuybvMBmpFPq00BscZSPyuGk9NUKocxQwJoY+Hw4FAjIP b/rdZcQGCeqQAFlnY3kjWeRrtGse3jbZ5Sm7Mebv+y7EQIA497Cx4vQDfTupp5bj eEND/wtll4rTqI6w2XKb69hfg6N9bbDSFnaUnvOmM164xvGMK8Xo+A8LshcoOnzS VMr3vrKOnU7dGCEulF3q7YxzcfqzkttTTr+u1XWdDJAh9GlOYpitEtYad7H4UpaQ QidTRx4bwSA2aLApYKVV7GVLATKid0FjLmukHk1MGJXtEH4zhLS+/GGxPwKApOYx KBqJyJSPEZU9zd1hc1KBbGyd0IarolvXK8uf2w5lQ== Received: from phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta03.appoci.oracle.com [138.1.37.129]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 42t0heskys-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 14 Nov 2024 17:05:28 +0000 (GMT) Received: from pps.filterd (phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (8.18.1.2/8.18.1.2) with ESMTP id 4AEH3ROU022745; Thu, 14 Nov 2024 17:05:27 GMT Received: from pps.reinject (localhost [127.0.0.1]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (PPS) with ESMTPS id 42vuw1jy6k-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 14 Nov 2024 17:05:27 +0000 Received: from phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 4AEH5QmH032739; Thu, 14 Nov 2024 17:05:26 GMT Received: from sidkumar-mac.us.oracle.com (dhcp-10-39-201-66.vpn.oracle.com [10.39.201.66]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (PPS) with ESMTP id 42vuw1jy5w-1; Thu, 14 Nov 2024 17:05:26 +0000 From: Sidhartha Kumar To: linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org Cc: linux-mm@kvack.org, akpm@linux-foundation.org, liam.howlett@oracle.com, Sidhartha Kumar Subject: [PATCH 0/5] Track node vacancy to reduce worst case allocation counts Date: Thu, 14 Nov 2024 12:05:19 -0500 Message-ID: <20241114170524.64391-1-sidhartha.kumar@oracle.com> X-Mailer: git-send-email 2.46.0 MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.293,Aquarius:18.0.1057,Hydra:6.0.680,FMLib:17.12.62.30 definitions=2024-11-14_05,2024-11-13_01,2024-09-30_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 bulkscore=0 mlxscore=0 spamscore=0 adultscore=0 phishscore=0 malwarescore=0 mlxlogscore=999 suspectscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2409260000 definitions=main-2411140134 X-Proofpoint-ORIG-GUID: MtKCEM8yZv4wXPA5BALxi4JO3Ct--jlZ X-Proofpoint-GUID: MtKCEM8yZv4wXPA5BALxi4JO3Ct--jlZ X-Rspamd-Server: rspam09 X-Rspamd-Queue-Id: 4DA31400FD X-Stat-Signature: zo8bueo3q6obzg8d9f7st4mskeuc9ubo X-Rspam-User: X-HE-Tag: 1731603910-644206 X-HE-Meta: U2FsdGVkX18Jo6dlAY3ICkAPZUQNzEJpmNymZLeE7W3D56DTi72hpDsyOhUfBrFazEVG7QP7yeAjiAaG02kJ3RqzTboGFCBQxxGuy4HmWjstq0wCkPpFDbQKdh8RG6gv2OumVgszKE67qQEQPt+IJln80jwjVOcH0InIWA2pjP+OcUcLYMzUcmYI+n/lMtORShGFv5yM1OrR+TcxzI52obJk5TqzzbbMEf++77VFNM88VspqQ/jYxgUEEyAc2+ddNVHD9RZhWD5tzy7XWhI/kKqqMUQoCu/ohMeXiw8gzS4Dr7ai13QHCSgkd54KRyOTpPGMPprTwYieY5dRhg2vouKdBOEEd0NjJu6unn4eh0FeG+Ic8+kfAT+J9IGw1/lj3S/bR5mPuWPUPdZWO1DWqfKty5X/9QSjNQgYPIMOoCkh78c2jqeZml7rPfbH258z3aKDQraaXUWtBHulGy2YHQqYrsord3LKRWnNEb2VUis1vd+T6Pzf8tnuGvstaiUz8iAxaOGR+bV/k/r85wo2Ik0ZCzoMU/0vxhISHjv4Q5SMR5AoF7bLwP1912i72TwvL2XgtcbFuWl3onUka5He0SSzL1cte9/1fPGwBfSQsoBy2YXStOfyEBbZLfw6YafE+9ROBrOwwrataaa7dIaGN+dvCylNNFG8pvwiCZaAcxfq5Ys0f1Ng/CsfE7/OUvz6BlJa5d5+fkbkclPec4XOdgnohladZVgKyApY15B+ZyjcguF+UjfQxpEeJu6VsiEvtsqrO6DyRcb9cAIZM5eBN/iGbHWNU4LN00fLjTMxjYHLqADjGRPrbhzhv0gErShD0r0isoBU4HWe2AeGq7efB3udGW+QTuDbfnMUSil24tH33/0Zi+S5rPR6ENyEtcYssTVBHbp1nS0O+WTmZzdp8mTQWfEblmPK2vUPp484oTqvELARbProDmCPJkymXvBo1crtH1HoYu1ASo9nCIZ 7lax4/a1 iK8ug9Gptudx/db1fiKz5pPT9pevFm9235pJr8JlaOPee56PSaFAXIpsOcTW78gU1zsdk4X6I6WMNf9F1CM3ADe/fwLjcnF9J4QFpLcYHzr/jwklvQleqTNEHTgrGPSl3NNsgwV5U4mCKJTuXr9gFYLfDSft8Aw/uzHKdpBAsdDerh4o+DvZNdsmnbVJxwsYMT5Dc1Pet2u6ddMs= X-Bogosity: Ham, tests=bogofilter, spamicity=0.016425, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: ================ overview ======================== Currently, the maple tree preallocates the worst case number of nodes for given store type by taking into account the whole height of the tree. This comes from a worst case scenario of every node in the tree being full and having to propagate node allocation upwards until we reach the root of the tree. This can be optimized if there are vacancies in nodes that are at a lower depth than the root node. This series implements tracking the level at which there is a vacant node so we only need to allocate until this level is reached, rather than always using the full height of the tree. The ma_wr_state struct is modified to add a field which keeps track of the vacant height and is updated during walks of the tree. This value is then read in mas_prealloc_calc() when we decide how many nodes to allocate. For rebalancing stores, we also need to track the lowest height at which a node has 1 more entry than the minimum sufficient number of entries. This is because rebalancing can cause a parent node to become insufficient which results in further node allocations. In this case, we need to use the sufficient height as the worst case rather than the vacant height. patch 1-2: preparatory patches patch 3: implement vacant height tracking + update the tests patch 4: support vacant height tracking for rebalacning writes patch 5: implement sufficient height tracking ================ results ========================= Bpftrace was used to profile the allocation path for requesting new maple nodes while running the ./mmap1_processes test from mmtests. The two paths for allocation are requests for a single node and the bulk allocation path. The histogram represents the number of calls to these paths and a shows the distribution of the number of nodes requested for the bulk allocation path. mm-unstable 11/13/24 @bulk_alloc_req: [2, 4) 10 |@@@@@@@@@@@@@ | [4, 8) 38 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@| [8, 16) 19 |@@@@@@@@@@@@@@@@@@@@@@@@@@ | mm-unstable 11/13/24 + this series @bulk_alloc_req: [2, 4) 9 |@@@@@@@@@@ | [4, 8) 43 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@| [8, 16) 15 |@@@@@@@@@@@@@@@@@@ | We can see the worst case bulk allocations of [8,16) nodes are reduced after this series. Sidhartha Kumar (5): maple_tree: convert mas_prealloc_calc() to take in a maple write state maple_tree: use height and depth consistently maple_tree: use vacant nodes to reduce worst case allocations maple_tree: break on convergence in mas_spanning_rebalance() maple_tree: add sufficient height include/linux/maple_tree.h | 4 + lib/maple_tree.c | 89 +++++++++++++--------- tools/testing/radix-tree/maple.c | 125 +++++++++++++++++++++++++++++-- 3 files changed, 176 insertions(+), 42 deletions(-)