From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mx0b-0031df01.pphosted.com (mx0b-0031df01.pphosted.com [205.220.180.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 C330A36F916 for ; Thu, 25 Jun 2026 21:28:19 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=205.220.180.131 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1782422901; cv=none; b=BXWMGXxGSg2F/ab7g0LmOfM84ln1fQoFExXq165Xsz9VzTrmEnF7Za7F0Qg4sAGdtYqWSnm6ukvuPiqSrZ/xruVI2kEP+MRU3cs7+4N33MBxTy3fraNa0NhQqgmVYluhwDVdyDy5dn1y5lOHYvImjEElRiFQYWp+418Yjb8cYWA= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1782422901; c=relaxed/simple; bh=GQsO8VeAgC/KNNaZnoHfmtwfirlK1mVAUqOScNygEgc=; h=Message-ID:Date:MIME-Version:Subject:To:Cc:References:From: In-Reply-To:Content-Type; b=YBO725XQEdcOqIMv+ts/TjkLn2lbe5To5fw+WCgN9YG3Rd0hFEQwr8EkUDW04MmHzpLJGk5zV8Q6CqoRnPyEGYGAxbl4mxfbv8Vm7F5dGQED2NRVwHKud4StEP3F74gUOGHEPL+FYC9wDDzkfsauEz9SWRkLiRjsSCi/5L5dqcg= 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=bhsprzAC; dkim=pass (2048-bit key) header.d=oss.qualcomm.com header.i=@oss.qualcomm.com header.b=imIaCD8g; arc=none smtp.client-ip=205.220.180.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="bhsprzAC"; dkim=pass (2048-bit key) header.d=oss.qualcomm.com header.i=@oss.qualcomm.com header.b="imIaCD8g" Received: from pps.filterd (m0279869.ppops.net [127.0.0.1]) by mx0a-0031df01.pphosted.com (8.18.1.11/8.18.1.11) with ESMTP id 65PJkPlt3387954 for ; Thu, 25 Jun 2026 21:28:18 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= QS7UHeLZQ8FUPa0FNvzQZRUxB4HFWhnIDFIBp7tIS6w=; b=bhsprzACOGqjhen2 Nt0Y5lU8ib3eUGl3WmeWVM07S3w1G8hoBh7Y8fPitS0YnTc0muQRKdkKq1BXYeDN ZmFG8f4rtiZ7RuSDvVBMw8iIlbF1S37lqzaUCrcwYPdKAHq5W7j1KhgiQ00wERwM tDlGXG91vHqjZk5bsDPLOgCEROI7TLmCpZE+ujqzl8tgHzvTv5o6R8pbvc95Gl6j czOU/9bOCDde4vuD/yxKzWVT87G/ML0UcBgGzvvN2i4Suad8HOj786YyuDcmNthZ cKYisTflEGgBPVROWcQmWVnqWnWUY+76GkPUb63dfqinaESZoUrUP/qtxHn5J4pW T/Zkuw== Received: from mail-dy1-f198.google.com (mail-dy1-f198.google.com [74.125.82.198]) by mx0a-0031df01.pphosted.com (PPS) with ESMTPS id 4f1askr9a0-1 (version=TLSv1.3 cipher=TLS_AES_128_GCM_SHA256 bits=128 verify=NOT) for ; Thu, 25 Jun 2026 21:28:18 +0000 (GMT) Received: by mail-dy1-f198.google.com with SMTP id 5a478bee46e88-30c13bb8ca9so515708eec.0 for ; Thu, 25 Jun 2026 14:28:18 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oss.qualcomm.com; s=google; t=1782422898; x=1783027698; 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=QS7UHeLZQ8FUPa0FNvzQZRUxB4HFWhnIDFIBp7tIS6w=; b=imIaCD8gD2FrVrjLGiDFefr0poKSQH3AyPfQjjEZA0aYP/De8IE2SrKlXjhUQAw+uf KxooAGU8PZtepzPzEnmeaRC/ALNvF5E9NeFHsQNSCNY6Q6n61WspIXAYcC9/i0Nk2lce 9UWPTmq74OwXRzSIkoh0irCaS941MsyI2XOeZoKTAvF7P2F3b+D9vlDQXN3N4AedqxJj eBHsElmenc09n4LQxFFRplQVd79AcbTHWLWnh816fK3MsTZqvoFCrqcLhtP9vJgF7AtH OIh4wYIw66aCjzlLn6cUsYnYAzeYvLQH7TfWMGs78vSARnobSZCZU4F7snTx5peHaVOF xNgA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1782422898; x=1783027698; 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=QS7UHeLZQ8FUPa0FNvzQZRUxB4HFWhnIDFIBp7tIS6w=; b=DYGgLNSkeg9a83b4t1o5U94lCgLgvnG3smRzetm/7C04sc5CjdAKl8bkJIYmFObUu8 KAMx9ftDMm8o4V2Ti69zX1ZEp9+xqT9CE8LbEvC0bQPdW3N0REy2nPAYaY4M/0eHgRlx jbp+tg0r7IZZ05cZBo06IWSJ/PUe0YW2obPISS5C1tHfUksMVYogkuti89IqKCc8lX4z bjeztEDsSlq1dUKMuEDxHhqRr6RDRDUvjg3MP0V4MIc+zjctdM8iqpzoXufdIUTQZdD5 Jg4qu9YXAmxz65H4aEZEGiCog9Y4IQ+wH0i7rjoLAbKhLtk09UYQfoMkwCRYY0eaXT2C OZrQ== X-Forwarded-Encrypted: i=1; AHgh+RrQmGPhWDUX4yhfuCQnoJizLa9KYM2qwY6t8+6k3w6bxGM1N+DYEq5w2AVJtItO2ub1nbgrYa/wNm7ZNY8=@vger.kernel.org X-Gm-Message-State: AOJu0Yy3nP8njdS19zNssn07EbhdRHMlONADKVzRSEYj+XsNYYIhf62G ACvtpEhtMTy+SOrLHOneFWZKFpdj2oaYIkslwR9sRMLIo+4S92lRJWkwiUVzMJlimikJea32b84 a7y9irc+3/47cetYv4jmtBE1CwWb0hOCwSyAXSoN7+KEEoi8yOdVrE0xtN93PmI5p6fE= X-Gm-Gg: AfdE7cmzJx7DYPCrnTnfxJeDBkJrTg0RgfHpDoXWSsjurl+FEHQnthSASFzLU5zVcXB yJmNdTTelHOtUjAlZWAwe2XOqgeSGEX6U3sRz/kcrxF3nVBtf6EwVmqtwVJPgkchJRkKToOjamd elH92pmgXrXJZB/8nXfSVkdf65VlCIeOjk1Fm6ITLB10pYxkAju25bothv8os75JieyysfMnd8K 7S+rdD/cEkWjUoluHgy4/UYqYGOIH6qp1YdEZR26dL/1PiESv0N6LKRXtI6wQW1tacM8Jtm9RX+ 4sYBb5vc2vGV/E34eOg/cKDzgV+Q7HnDYgbzsGbw+d6kcVW12JYGuDBXcUplf9XPFmojSORntXT Z2rQ38Q0nG11+g+Kp399oxYI9FMmezZuuoTYZKceh X-Received: by 2002:a05:7300:d021:b0:30c:536e:3a8a with SMTP id 5a478bee46e88-30c84b7208amr3993365eec.6.1782422897598; Thu, 25 Jun 2026 14:28:17 -0700 (PDT) X-Received: by 2002:a05:7300:d021:b0:30c:536e:3a8a with SMTP id 5a478bee46e88-30c84b7208amr3993332eec.6.1782422897093; Thu, 25 Jun 2026 14:28:17 -0700 (PDT) Received: from [192.168.1.4] ([122.177.247.87]) by smtp.gmail.com with ESMTPSA id 5a478bee46e88-30c7c4ca21fsm12718751eec.6.2026.06.25.14.28.08 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 25 Jun 2026 14:28:16 -0700 (PDT) Message-ID: <5285b561-d610-43d7-af76-ba5da19e70ff@oss.qualcomm.com> Date: Fri, 26 Jun 2026 02:58:06 +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; format=flowed Content-Transfer-Encoding: 7bit X-Proofpoint-Spam-Info: AW1haW4tMjYwNjI1MDE4NiBTYWx0ZWRfXxiCSACSfoXXk sf2ZASbcVV3k6S18K9PopyQums9V8jEGo1taff4soO9OrLKlRGxEuXvfqmMMPG9m2LZ2X37ARPG Hq8XwNVDYsYprHS32l5ww86vUgvNmwk= X-Proofpoint-Spam-Details-Enc: AW1haW4tMjYwNjI1MDE4NiBTYWx0ZWRfX3BKECesUaI9J r4L3H7KsQniTX+3nvUtWbP1rStD1ZEtxYCo1q3FalSlMwAjvcwNWCXN50e2ME0F9CW6htX/Ir7R BE88YvsnOqosD5rXH9+7TiIwjWHhedOM+FXiX0S0lYLwpah3InYBQByV1IHqrkLk6L3RLsBsSy8 N5HIVD047q3iQiqg/ttcyw4rPHO2L/5DSzvhwmyAWXxK3iNm3XBlCaFSwX9x6ndPFclMT5O0+Xd ufVPG+A+K0DX6PcebeFzi5ojNgmJFkeY1GS7OSzBD0vTk4w6lwpCO0QQvNgjxbUVx3cDdP/kUkO xYCzmdcid2Gs8kVZwVAeoV/dNvNPp4o1brucqXW+QekKhGJI79vLDgVhFShGstYnFB0AU2TcL5E p4jY5eYztktoCp9AFuekKLurSRQPU+XnLhCr9v2VFo1kQB8Y+Uu05wMsuO+fatwKbF0gUVXCdM1 D6KSurdZBhSK8/8rnaA== X-Proofpoint-GUID: FUQp_WubfzODvA7_kxhwGI0biQPgQdoK X-Proofpoint-ORIG-GUID: FUQp_WubfzODvA7_kxhwGI0biQPgQdoK X-Authority-Analysis: v=2.4 cv=AMxnnMPh c=1 sm=1 tr=0 ts=6a3d9d72 cx=c_pps a=wEP8DlPgTf/vqF+yE6f9lg==:117 a=/mmxY0Z96yNuczEkiZ583g==:17 a=IkcTkHD0fZMA:10 a=FelO9ux0wxsA:10 a=s4-Qcg_JpJYA:10 a=VkNPw1HP01LnGYTKEx00:22 a=u7WPNUs3qKkmUXheDGA7:22 a=_glEPmIy2e8OvE2BGh3C:22 a=QrJ9IbtdTVaOtOl6jMIA:9 a=QEXdDO2ut3YA:10 a=bBxd6f-gb0O0v-kibOvt:22 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-25_02,2026-06-24_01,2025-10-01_01 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 suspectscore=0 adultscore=0 impostorscore=0 priorityscore=1501 phishscore=0 malwarescore=0 lowpriorityscore=0 clxscore=1015 spamscore=0 bulkscore=0 classifier=typeunknown authscore=0 authtc= authcc= route=outbound adjust=0 reason=mlx scancount=1 engine=8.22.0-2606150000 definitions=main-2606250186 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.