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 86E97C4167B for ; Wed, 28 Dec 2022 17:10:34 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id D22238E0002; Wed, 28 Dec 2022 12:10:33 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id CD28A8E0001; Wed, 28 Dec 2022 12:10:33 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id BC11F8E0002; Wed, 28 Dec 2022 12:10:33 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0014.hostedemail.com [216.40.44.14]) by kanga.kvack.org (Postfix) with ESMTP id AB25A8E0001 for ; Wed, 28 Dec 2022 12:10:33 -0500 (EST) Received: from smtpin22.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 5625480D4A for ; Wed, 28 Dec 2022 17:10:33 +0000 (UTC) X-FDA: 80292353946.22.7704562 Received: from mail-yw1-f179.google.com (mail-yw1-f179.google.com [209.85.128.179]) by imf25.hostedemail.com (Postfix) with ESMTP id BEE7CA000D for ; Wed, 28 Dec 2022 17:10:31 +0000 (UTC) Authentication-Results: imf25.hostedemail.com; dkim=pass header.d=google.com header.s=20210112 header.b=UkbVoEG8; spf=pass (imf25.hostedemail.com: domain of surenb@google.com designates 209.85.128.179 as permitted sender) smtp.mailfrom=surenb@google.com; dmarc=pass (policy=reject) header.from=google.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1672247431; 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: in-reply-to:in-reply-to:references:references:dkim-signature; bh=oYsqnZ8FJ65xaJlOCHcTfd528vZbbXtntY5OMB92i10=; b=hFnGnYs7dzPgYOUg5qEbOtOSUM6KLPSSwU333pIuNok/1svZxUx14fXG4on1V4ff+t/L1V 0SxJX5wC8XyP0mjJt1plhTgjovM7soK5dc78xeHsw1ew90F6ft06dTSD2noUlxVT0Vrkz4 rCYe8Ti1Q6h0uXk8v89hTUQV1keoWCA= ARC-Authentication-Results: i=1; imf25.hostedemail.com; dkim=pass header.d=google.com header.s=20210112 header.b=UkbVoEG8; spf=pass (imf25.hostedemail.com: domain of surenb@google.com designates 209.85.128.179 as permitted sender) smtp.mailfrom=surenb@google.com; dmarc=pass (policy=reject) header.from=google.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1672247431; a=rsa-sha256; cv=none; b=uT8c5VYXC4pNgSVfbD8U9NC/p+HuSYfnz1qLQMyvC0A2ZnIt3tTiVGBL+CNQO9ZFasMsWO Xn6UJ1AGjoeFg/QjOimNN29bnJJyPYQN8nc5HVkLr9L7vEw/fQI/vVoqdb15AlalmISmL0 NOxcxZkLhpPrkfK+469mIgrzLyPZJf8= Received: by mail-yw1-f179.google.com with SMTP id 00721157ae682-45c11d1bfc8so229449977b3.9 for ; Wed, 28 Dec 2022 09:10:31 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=oYsqnZ8FJ65xaJlOCHcTfd528vZbbXtntY5OMB92i10=; b=UkbVoEG8EXDv03CU0ZLBkw9xvwi0gUbu6WtMl0/cSzlfr+HMnEoXWh9otr4CKs9Z5c atkhIsOItvBZKXOFzukIjmG6UfPDzKOLfYFLaFznsoXUsFpLdrbpXxDYygAfihpc+4Dq Ndu6c8nz2L5bcq+UhdEY+T8o4G/wAD8HnBjKmkx86AIZCsfCjrPcCMuorp/pP9jghs8k XixkENiqi6u9SIG3RFGPBKdIfgdy8FDxBbGKAY+OgI8e4BYXGrt6cB6+DRjFBvUnLTyK BHtSjt7JzK2d1dYz6w21gB7Tf4P6hL5jo5wrTZbG3/rnZSAnEpXX55QM6cxuRKlg9QGs 3MtQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=oYsqnZ8FJ65xaJlOCHcTfd528vZbbXtntY5OMB92i10=; b=bkcIVCJGfEEuCVNXXVb2ld/T0Rm6s2MZGwaFCWPsX32xH+Rv0HLAT9m7ojPcVqaiOF x72wvpdDpq7+LagF57oGduk0ziizU+wr+R+7moG79CWDksCJKNVmvdX4NO4/twQY5FZs cUptSYnQvx9R+1wJ3vfK57h2PPTEkGDRUPpqLDumjgvMMxxTVFenrGfNjUthEmPfQCss +T09jVyIpaikMM1MSjOINwtw3ffOBXnEMK64uQJR89f/qaQPChk+MKgXx3EBUrUlUlqo XNaS6NQauXZZ0K2gdILwjvYqDAZXJXH5EYsj/lKHQwWW9qxABq7vFgSUMj2c93eiDHKm MtiA== X-Gm-Message-State: AFqh2kppb36zC/kenJKMS390AKnX1DTNdcUD2pwQ0osGyHbNIcecJnFa 6INm8gSFAWgjulH4CYBHXca79nK/M/g5i/jWNV2dPW68/AY+U+9N X-Google-Smtp-Source: AMrXdXs/YzI0oXArYeCy16hKt7OLDtsFcLJcGXyrSW1Mncb+52cj9t7LwjbFR8qZe929ZW6axi9srVWhK3wRT1TIZek= X-Received: by 2002:a0d:d611:0:b0:479:b6a1:d9a4 with SMTP id y17-20020a0dd611000000b00479b6a1d9a4mr1119032ywd.263.1672247430626; Wed, 28 Dec 2022 09:10:30 -0800 (PST) MIME-Version: 1.0 References: In-Reply-To: From: Suren Baghdasaryan Date: Wed, 28 Dec 2022 09:10:20 -0800 Message-ID: Subject: Re: [QUESTION] about the maple tree and current status of mmap_lock scalability To: Hyeonggon Yoo <42.hyeyoo@gmail.com> Cc: linux-mm@kvack.org, liam.howlett@oracle.com, willy@infradead.org, ldufour@linux.ibm.com, michel@lespinasse.org, vbabka@suse.cz, linux-kernel@vger.kernel.org Content-Type: text/plain; charset="UTF-8" X-Stat-Signature: khjir3q771ki7rfukeduqxfhwt1ak8bh X-Rspam-User: X-Rspamd-Queue-Id: BEE7CA000D X-Rspamd-Server: rspam06 X-HE-Tag: 1672247431-316733 X-HE-Meta: U2FsdGVkX19gwa1lhtbu9N3TnLMjvTXM0s/6aJnYGCTquU8lj3+Mb4qdLwtpOQA9lh1jFkbuFPguHano1q5nN+9ogvFsJy4HQgFHTf4vVWKirecb3wks8wuRI1XmdZhZ2K//VN0ntHs8sOdthB4XayDBW5hICd9b3nAJ/KXA2YUPtd3pPn6fI7pwg/hq0vRxPVyTTOihdugfJM3/BozJ15joppcm9Y+egbGPj0pDn9k42z1LzO4IYnjU0fKSF6hAQuLvX7gUoHSNWEvLgSLEv47K1a+ASxC7zqGodOfX7qbCyL/AKCQK+5WhvURvu5GagHqiW2cFg03ifplALiZEDXAnVf6rZnvhoibE108HyJgvx0jp2fisCc/ETw+sNlwl1IckKwq70TSMfULOH8VboKo3c7R8GJDKIMHDYu2rLsn8FQXlQJQuYdWpT9LaFw3i3jbaeML2WJ6bbllyAzvjFb+ZXxbTZbizsVlF65jqRzbysvQhz/og1NWzfpz/nUDfWpIPCAjh/zHXFzXKnlI5M6tWsshUQh0eAVMRGNgtxWS30DhCwHjCFWZqZnIJbe9N6/Wa5QZ8n2JKZmQ72YCDrdFiwa/n6TF93oT5Q3xdhaSJZjcbgqweJuDqDwa+UI4fPr7egI+b+B0ezGk1TC9hMvxg1xn8uPvA8p61ZDlh9KYF5ZH8ugwC0aIAutC+kY106uNP1KfOsvUe33RAuYIqNchaXUlfE1z2g6/P8ei/8Hm05EmBZAoJvoQ/5pI8He0a8FoNlF2qYMGN8GE85Bfqsz0mqx8O/z6o3BN8aLEuCsJ5MyQknucsBSDAusXSJ61qz0eRswYcqw3vshznI8ws+KV5Dfh+aErQC04hkcsZkj9fTfEWmFBOeRZVanFS/U5pb46vfEQYB6+qYoWF3EPQx+X6Xji0G/k9YHPgpV6juTKw3IWqT6mjO90SYnxBDXxG6KHrLKR8ebUux9AqwYH t1/3feSO thuBHm/7DMdqFhpOxWDdeDi9itpc5ed3KxZx5k390/fepUTyQ0MDzhYgIY2baLzko+G1YqXVvnOc+BPwbAYW0ri/c+Eq/cTMqMHp05Bq7fRgGOpaONsrmzS4PvdWW0b6w+a+4 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: Hi Hyeonggon, On Wed, Dec 28, 2022 at 4:49 AM Hyeonggon Yoo <42.hyeyoo@gmail.com> wrote: > > Hello mm folks, > > I have a few questions about the current status of mmap_lock scalability. > > ============================================================= > What is currently causing the kernel to use mmap_lock to protect the maple tree? > ============================================================= > > I understand that the long-term goal is to remove the need for mmap_lock in readers > while traversing the maple tree, using techniques such as RCU or SPF. > What is the biggest obstacle preventing this from being achieved at this time? Maple tree has an RCU mode which does not need mmap_lock for traversal. Liam and I were testing it recently and Liam fixed a number of issues to enable it. It seems stable now and the fixes are incorporated into the "per-vma locks" patchset which I prepared in this branch: https://github.com/surenbaghdasaryan/linux/tree/per_vma_lock. I haven't posted this patchset upstream yet but it's pretty much ready to go. I'm planning to post it in early January. Thanks, Suren. > > ================================================== > How does the maple tree provide RCU-safe manipulation of VMAs? > ================================================== > > Is it similar to the approach suggested in the RCUVM paper (replacing the original > root node with a new root node that shares most of its nodes and deferring > the freeing of stale nodes using RCU)? > > I'm having difficulty understanding the design of the maple tree in this regard. > > [RCUVM paper] https://pdos.csail.mit.edu/papers/rcuvm:asplos12.pdf > > Thank you for your time. > > --- > Hyeonggon