Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18;
Content-Type: text/plain;
        charset=us-ascii
Mime-Version: 1.0 (Mac OS X Mail 13.4 \(3608.120.23.2.4\))
Subject: Re: [PATCH] userfaultfd: prevent non-cooperative events vs
 mcopy_atomic races
From:   Nadav Amit <nadav.amit@gmail.com>
In-Reply-To: <20201208083434.GA1164013@linux.ibm.com>
Date:   Tue, 8 Dec 2020 00:57:30 -0800
Cc:     Mike Rapoport <rppt@linux.vnet.ibm.com>,
        Andrew Morton <akpm@linux-foundation.org>,
        linux-mm <linux-mm@kvack.org>,
        lkml <linux-kernel@vger.kernel.org>,
        Andrea Arcangeli <aarcange@redhat.com>,
        Mike Kravetz <mike.kravetz@oracle.com>,
        Pavel Emelyanov <xemul@virtuozzo.com>,
        Andrei Vagin <avagin@virtuozzo.com>
Content-Transfer-Encoding: quoted-printable
Message-Id: <83A6D439-F732-4112-BD1F-00195EBFCE4C@gmail.com>
References: <1527061324-19949-1-git-send-email-rppt@linux.vnet.ibm.com>
 <31DA12CC-E9CC-497D-A2EE-B83549D95CE8@gmail.com>
 <20201206093703.GY123287@linux.ibm.com>
 <5921BA80-F263-4F8D-B7E6-316CEB602B51@gmail.com>
 <20201208083434.GA1164013@linux.ibm.com>
To:     Mike Rapoport <rppt@linux.ibm.com>
Precedence: bulk

> On Dec 8, 2020, at 12:34 AM, Mike Rapoport <rppt@linux.ibm.com> wrote:
>=20
> On Sun, Dec 06, 2020 at 08:31:39PM -0800, Nadav Amit wrote:
>> Whenever I run into a non-standard and non-trivial synchronization =
algorithm
>> in the kernel (and elsewhere), I become very confused and concerned. =
I
>> raised my question since I wanted to modify the code and could not =
figure
>> out how to properly do so. Based on your input that the monitor is =
expected
>> to know the child mappings according to userfaultfd events, I now =
think that
>> the kernel does not provide this ability and the locking scheme is =
broken.
>>=20
>> Here are some scenarios that I think are broken - please correct me =
if I am
>> wrong:
>>=20
>> * Scenario 1: MADV_DONTNEED racing with userfaultfd page-faults
>>=20
>> userfaultfd_remove() only holds the mmap_lock for read, so these =
events
>> cannot be ordered with userfaultfd page-faults.
>>=20
>> * Scenario 2: MADV_DONTNEED racing with fork()
>>=20
>> As userfaultfd_remove() releases mmap_lock after the user =
notification and
>> before the actual unmapping, concurrent fork() might happen before or =
after
>> the actual unmapping in MADV_DONTNEED and the user therefore has no =
way of
>> knowing whether the actual unmapping took place before or after the =
fork().
>>=20
>> * Scenario 3: Concurrent MADV_DONTNEED can cause userfaultfd_remove() =
to
>> clear mmap_changing cleared before all the notifications are =
completed.
>>=20
>> As mmap_lock is only taken for read, the first thread the completed
>> userfaultfd_remove() would clear the indication that was set by the =
other
>> one.
>>=20
>> * Scenario 4: Fork starts and ends between copying of two pages.
>>=20
>> As mmap_lock might be released during ioctl_copy() (inside
>> __mcopy_atomic()), some pages might be mapped in the child and others =
not:
>>=20
>>=20
>> CPU0				CPU1
>> ----				----
>> ioctl_copy():
>> __mcopy_atomic()
>>  mmap_read_lock()
>>  !mmap_changing [ok]
>>  mfill_atomic_pte() =3D=3D 0 [page0 copied]
>>  mfill_atomic_pte() =3D=3D -ENOENT [page1 will be retried]
>>  mmap_read_unlock()
>>  goto retry
>>=20
>> 				fork():
>> 				 dup_userfaultfd()
>> 				 -> mmap_changing=3Dtrue
>> 				 userfaultfd_event_wait_completion()
>> 				 -> mmap_changing=3Dfalse
>>=20
>>  mmap_read_lock()
>>  !mmap_changing [ok]
>>  mfill_atomic_pte() =3D=3D 0 [page1 copied]
>>  mmap_read_unlock()
>>=20
>> return: 2 pages were mapped, while the first is present in the child =
and
>> the second one is non-present.
>>=20
>> Bottom-line: it seems to me that mmap_changing should be a counter =
(not
>> boolean) that is protected by mmap_lock. This counter should be kept
>> elevated throughout the entire operation (in regard to =
MADV_DONTNEED).
>> Perhaps mmap_lock does not have to be taken to decrease the counter, =
but
>> then an smp_wmb() would be needed before the counter is decreased.
>>=20
>> Let me know whether I am completely off or missing something.
>=20
> I tried to remember what's going on there and wrap my head around your
> examples. I'm not sure if userspace cannot workaround some of those, =
but
> I can't say I can propose it right now.
>=20
> There is for sure userspace is helpless in Scenario 4, but I think it =
is
> very unlikely that fork() will be fast enough to grab and release
> mmap_lock while uffd_copy() waits for CPU to retry.
>=20
> I agree that a making mmap_changing a counter would be more robust
> anyway.

Thanks for confirming my suspicion.

On a second thought, I think that a sequence lock would be required. I =
will
work on a patch to resolve it in the next RFC of the related patch =
series I
am working on.

As for the race window size, as there are lock optimizations to prevent
writers' starvation, I do not think the last scenario is completely
far-fetched.

Thanks again,
Nadav=