From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mx0a-0031df01.pphosted.com (mx0a-0031df01.pphosted.com [205.220.168.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id D7C863A9872 for ; Fri, 26 Jun 2026 09:43:51 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=205.220.168.131 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1782467033; cv=none; b=EToNH5xChP8g8n/UIlrpvNPCM/ho232fI83BbKuu/Eu3HE2LayTNj/8FFev0mHOQ8W25kcAK9+sFeJEjGRYanshZ6vFfB41DVb/+si4hvUfhE+3+wic1ZrR0yGFaWNo9oa7kIJHHDBgK5K+8jOMf7uNfXjcAJFTwTlIUbGBFmjg= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1782467033; c=relaxed/simple; bh=Fl+FGgsJdZgdbefiY6HOupOALouXoshrGXiJQrVWStU=; h=Message-ID:Date:MIME-Version:Subject:To:Cc:References:From: In-Reply-To:Content-Type; b=dAfJdv3QyfI9zTG7gjX3RVQdEQHX4MkDRLjNoYKzQ7YkdUS/2cEqSzDxNToKSE9lBexL2dV/Iyy1Xa4GDFMXGt5SUrfoETKwK3uBjnR/x6UrO8BMbcHWQWTYUdnlEURLcZeOPpICASRy7VnbUKRkY9eNGzcT9Zh1+0l6bIP4Dk8= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=oss.qualcomm.com; spf=pass smtp.mailfrom=oss.qualcomm.com; dkim=pass (2048-bit key) header.d=qualcomm.com header.i=@qualcomm.com header.b=AJVYM1sO; dkim=pass (2048-bit key) header.d=oss.qualcomm.com header.i=@oss.qualcomm.com header.b=AQCdIxH1; arc=none smtp.client-ip=205.220.168.131 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=oss.qualcomm.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=oss.qualcomm.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=qualcomm.com header.i=@qualcomm.com header.b="AJVYM1sO"; dkim=pass (2048-bit key) header.d=oss.qualcomm.com header.i=@oss.qualcomm.com header.b="AQCdIxH1" Received: from pps.filterd (m0279862.ppops.net [127.0.0.1]) by mx0a-0031df01.pphosted.com (8.18.1.11/8.18.1.11) with ESMTP id 65Q6VM1x4193020 for ; Fri, 26 Jun 2026 09:43:51 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=qualcomm.com; h= cc:content-transfer-encoding:content-type:date:from:in-reply-to :message-id:mime-version:references:subject:to; s=qcppdkim1; bh= DJR0sgePn08C5LSYaXjJKVn++m0V1zKkluMfeBu+TGw=; b=AJVYM1sOs7RyYHBz RCmf50nu5Av0PyOCRuE3+YF1ALmXhNJpKOHhk3GrnZl8rtk+HUPukr00+bZcaWJp r58fhRFeLRxl5n1H0LNu7MBjZxlAvZI1Uq0uv+VRGfxct1fkX8fH64cvDYDV2BmR 6Eu57I2ufQo6rUOikWj9q/pJCaPrXICsXGhf4yZc/VOoFNkKZwnsh5zZMNt8Qju5 SCIbPA/ucYdMWJ9fcqOWPPCsT8M7sAEKp7H1EsyikkVyf5xHq3sSJpotN6sI9rif G3F2Ur6YqUqP/tVjYYXK57JlPNIT28bk1beZxc1cu0WkOtuW1C9l8gRGQt0aEtpp fkj1eg== Received: from mail-pf1-f197.google.com (mail-pf1-f197.google.com [209.85.210.197]) by mx0a-0031df01.pphosted.com (PPS) with ESMTPS id 4f1fgdsuc6-1 (version=TLSv1.3 cipher=TLS_AES_128_GCM_SHA256 bits=128 verify=NOT) for ; Fri, 26 Jun 2026 09:43:51 +0000 (GMT) Received: by mail-pf1-f197.google.com with SMTP id d2e1a72fcca58-845bbdc86ebso1065146b3a.0 for ; Fri, 26 Jun 2026 02:43:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oss.qualcomm.com; s=google; t=1782467030; x=1783071830; darn=vger.kernel.org; h=content-transfer-encoding:in-reply-to:from:references:cc:to :content-language:subject:user-agent:mime-version:date:message-id :from:to:cc:subject:date:message-id:reply-to; bh=DJR0sgePn08C5LSYaXjJKVn++m0V1zKkluMfeBu+TGw=; b=AQCdIxH1h+wCMeOPaOy02fF9EMIpTyeISVY+M7OEM+n3fJrDKnUCnnGQWSLSF7q6Td pOHH0VnB4re8361H/gb3kX+aOOWYqerwAQGHBsHTpbtIgnxPjAi385yKtxZdy9RD1EAy 3qREP9WgSPzSNGK0hdz4I4yHP1RdteHjuFZejeXUDGRcIfLaUkCTYw5E+q3UWBAFf4xG nRG4OxrOkRuUflw4uanKlU0LtU0YZiVX5S/fZnB2qGyDIDt2sQQEpckKE9iji5OJIJ+s tjjlNFl1mzwbrfqomAq9Bxk6CcxTKmj+vW2rjJ52aCpVxrPVH2wr6RvkovSeR9G5ihBl Z48A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1782467030; x=1783071830; h=content-transfer-encoding:in-reply-to:from:references:cc:to :content-language:subject:user-agent:mime-version:date:message-id :x-gm-gg:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=DJR0sgePn08C5LSYaXjJKVn++m0V1zKkluMfeBu+TGw=; b=ofCIuF9fvjMv/k7Q4+ba7CmjEoh+OyPPWk2MxyyjOSIXYnOEdQy19G7Ey6W+oN7tzz VRtFgao8vzwPvhOsN3hV3r3FYZAw1LzK7MqjA2+uvK8pdIAwY20Mgc+JoYN/CJFGTwxp nj5PyvV2U5sp0MTI34Cyksn75E6E8XwlyxcLxM9pD/CYLkRQAUad0XUv1XT9u2useNpr JHypRuYJeRi8pmjGzYbIM+C6RFOjKd9poQi48PG+7vUWiBXXoWI8PEj9wHwSN6jyvag3 4jh84bTWESgaq2diGao7UJz0Kz0aW3k7EXjMd/FSlV8l6FH13j186FaeQoFO+SEUU/Qn sMew== X-Forwarded-Encrypted: i=1; AHgh+RrD3zoc+DGmn5qGelE6QxC9LdfDIQUVED8V9++ieXuoQbC7b0zS6ls5zAJe/yKzWRT3wITYKBbY4Fyn3fU=@vger.kernel.org X-Gm-Message-State: AOJu0YwWbkZQ4gW6bz5kfPZE5nl4M3renKUE/5U6mApbWhF50GJE1hiJ 8OFK65lEMcLtKYJa+z+GlE7mzMc46h5RXLZOubf9/01GM82e+38myobjTDA3jrDqhVGYXL2Xn/n maSaY3k407Dp8h3h+losG7XjmStbiEfPdloGnmb6JNDlijH1YDXyD+QCKxB9OfDlYr58= X-Gm-Gg: AfdE7clmNGSEtizbwuz+n9sBQ3jV0aTCAFpw0FkOU1JkDu/uu4KzZ4SGf0j+mRxuliw VLFuo12Zurp9GtMeoFmaP3Ke3+HyKNyxpbcjK7y2Qw+2Fhxfhse8AoVtB+PqovLjt5HSOc+vgL8 YhzgMlKa0KPuR8S1LPx1eNpnOwHJK1prFnewk7i+qzNGDJAGZG62mOjm4WLU4VXwPuqMxrvxVd+ jqwtdoqQYRYOnHyCl35Zey3IU+P2Ha1+f0ZbdFtEpG3IU7wtChDptYYTNGhLmf7Bib4Ht4x7TJN wkXGquX/ILD/t4hEm5yU1ZWnLRQMa7Wb/gcYGO5NyMrCFwltG+4uOBmHyLWPGkiOnBFsnN6V/Jl 5wLeeiTrKyCWR/2GLMcnQWXBohp2lx9JziJN1lJYT X-Received: by 2002:a05:6a00:181e:b0:845:c6c3:5e7c with SMTP id d2e1a72fcca58-845c6c36675mr2099905b3a.6.1782467030101; Fri, 26 Jun 2026 02:43:50 -0700 (PDT) X-Received: by 2002:a05:6a00:181e:b0:845:c6c3:5e7c with SMTP id d2e1a72fcca58-845c6c36675mr2099876b3a.6.1782467029665; Fri, 26 Jun 2026 02:43:49 -0700 (PDT) Received: from [10.218.25.225] ([202.46.22.19]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-845c5d248b4sm1123098b3a.37.2026.06.26.02.43.41 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 26 Jun 2026 02:43:49 -0700 (PDT) Message-ID: Date: Fri, 26 Jun 2026 15:13:40 +0530 Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Subject: Re: [PATCH RFC 00/12] mm/vmalloc: migrate vmap_area indexing from rb-tree to maple-tree Content-Language: en-US To: Matthew Wilcox Cc: Andrew Morton , Uladzislau Rezki , "Liam R. Howlett" , Alice Ryhl , Andrew Ballance , linux-arm-msm@vger.kernel.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Lorenzo Stoakes , Pranjal Shrivastava , Will Deacon , Suzuki K Poulose , Neil Armstrong , Mostafa Saleh , Balbir Singh , Suren Baghdasaryan , Marco Elver , Dmitry Vyukov , Alexander Potapenko , Shuah Khan , Dev Jain , Brendan Jackman , Puranjay Mohan , Santosh Shukla , Wyes Karny , Sudeep Holla References: <20260613-vmalloc_maple-v1-0-0aa740bb944b@oss.qualcomm.com> From: Pranjal Arya In-Reply-To: Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit X-Authority-Analysis: v=2.4 cv=API5kwXb c=1 sm=1 tr=0 ts=6a3e49d7 cx=c_pps a=rEQLjTOiSrHUhVqRoksmgQ==:117 a=fChuTYTh2wq5r3m49p7fHw==:17 a=IkcTkHD0fZMA:10 a=FelO9ux0wxsA:10 a=s4-Qcg_JpJYA:10 a=VkNPw1HP01LnGYTKEx00:22 a=u7WPNUs3qKkmUXheDGA7:22 a=_K5XuSEh1TEqbUxoQ0s3:22 a=QrJ9IbtdTVaOtOl6jMIA:9 a=QEXdDO2ut3YA:10 a=2VI0MkxyNR6bbpdq8BZq:22 X-Proofpoint-Spam-Details-Enc: AW1haW4tMjYwNjI2MDA3OCBTYWx0ZWRfX2KYQX/CjKyhC 366H3JbDX/OoaGoKCjIXsSa2CeITRqGzBO3GJLp2jfK7iWAaLLaV57KQn45xWR4FSr1fp2NCzng P7Obm1RKTo7MCa/jFKg/0sE17U9z2tuOM6uh0/PWcfkYEiFfysIGQHSYqaq5gQV54+ZFpk154+A XIkMQLUXnSLOQRKiJfpk3EoXe71VHloQ+v92ah2IP4k+GJzFUgz4nXYS1lU/et7dNX9c7IhwQYl X92hVBOiy/dtul5nt0//RXID5JYJ5LYa5CknIeV2H48ra/E5oY0vpOIvD7FWpIW+8RYDoPsl4xa 711FggtZi2LLANHS6mEIVbEXFrSbjUdITI7Die2WC84WoY7vvw0Bse3O5fyO9GqI6+qUxUN70ay xIKJuo8A4wcMcCduSivfnciLeRcIG95W+x8YYOBn2jcbG+XScMKfKrx2/wdrM7FJ/ozPeZfTnzq PatwaJ52ezz7T+Bntdw== X-Proofpoint-ORIG-GUID: 1mmElzuDig0kGGSORYwxzN4Z4DDy_fGF X-Proofpoint-GUID: 1mmElzuDig0kGGSORYwxzN4Z4DDy_fGF X-Proofpoint-Spam-Info: AW1haW4tMjYwNjI2MDA3OCBTYWx0ZWRfX4h1L+rS+f/aO 27IiA3v/3N49QSWaEfSR71/kJDtKLDsaPu2Pm5Q3JfzMO4Wwlz2wFw5mLKSIpvraxgq8r1sgfGH CxP+ency3koRnaa2uSGOL/mRX3Mj51c= X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.293,Aquarius:18.0.1143,Hydra:6.1.125,FMLib:17.12.100.49 definitions=2026-06-26_02,2026-06-24_01,2025-10-01_01 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 suspectscore=0 clxscore=1015 bulkscore=0 impostorscore=0 lowpriorityscore=0 priorityscore=1501 adultscore=0 malwarescore=0 phishscore=0 spamscore=0 classifier=typeunknown authscore=0 authtc= authcc= route=outbound adjust=0 reason=mlx scancount=1 engine=8.22.0-2606150000 definitions=main-2606260078 On 6/14/2026 4:45 AM, Matthew Wilcox wrote: > On Sat, Jun 13, 2026 at 10:49:42PM +0530, Pranjal Arya wrote: >> vmalloc's free/busy/lazy area tracking is one of the last remaining >> augmented-rb_tree consumers in the core mm allocators. The rest of >> mm/ has been gradually consolidating range-keyed indexing around >> maple_tree (notably the per-process VMA tree in mm/mmap.c), and >> the underlying reason is a structural mismatch between rb_tree and >> range tracking: > > First, and most importantly, I love this. The maple tree is undoubtedly > the right data structure to use for this purpose. > > What I don't understand is why you maintain a separate "free" tree. > It should not be necessary any more, but maybe you tried removing it > already and found a performance problem? Thank you Matthew, that is very encouraging to hear :). The maple tree's native range primitives and built in RCU support do make it a much cleaner fit for vmalloc than the augmented rb tree was. You are right, and I'm going to remove free tree next patch. Allocation will use occupied maple tree which will walk the gap space of the occupied index directly. The concern that motivated keeping the separate index in the RFC was lock contention separation. Uladzislau had originally structured things so that the alloc path could touch the free tree while unrelated readers could access the occupied tree without blocking each other. Your follow up explanation of how the maple tree's RCU contract makes a separate free index unnecessary is the key insight with MT_FLAGS_USE_RCU set on the occupied tree and call rcu deferred vmap_area free, the same contention reduction is achievable without maintaining a second index. BR, Pranjal