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;
MIME-Version: 1.0
References: <20210908184905.163787-1-posk@google.com> <20210908184905.163787-3-posk@google.com>
 <CAG48ez2LyLNkH4iVbeKJUuH=oh57WECkKYCW+G9mtheoh7Fsvg@mail.gmail.com>
 <CAPNVh5eaW7r_Nv-wHEyxQiFkXngmONwPyZSFvtTEhk3TxJ+iMA@mail.gmail.com>
 <CAG48ez0mgCXpXnqAUsa0TcFBPjrid-74Gj=xG8HZqj2n+OPoKw@mail.gmail.com>
 <d656e605-4f89-4ea2-8baf-f7786f0630d9@www.fastmail.com> <YUDlzxLjNsW+oYGC@hirez.programming.kicks-ass.net>
 <f6fdecfe-963d-4669-ae05-1d7192467a19@www.fastmail.com> <YUIUWs9pIfHh51lP@hirez.programming.kicks-ass.net>
In-Reply-To: <YUIUWs9pIfHh51lP@hirez.programming.kicks-ass.net>
From:   Andy Lutomirski <luto@kernel.org>
Date:   Wed, 15 Sep 2021 09:50:41 -0700
Message-ID: <CALCETrUnnHN0dyx02ewuRu=_TZ+cD=HaEzNs34ADNbWps1tTBw@mail.gmail.com>
Subject: Re: [PATCH 2/4 v0.5] sched/umcg: RFC: add userspace atomic helpers
To:     Peter Zijlstra <peterz@infradead.org>
Cc:     Andy Lutomirski <luto@kernel.org>, Jann Horn <jannh@google.com>,
        Peter Oskolkov <posk@google.com>,
        Peter Oskolkov <posk@posk.io>, Ingo Molnar <mingo@redhat.com>,
        Thomas Gleixner <tglx@linutronix.de>,
        Linux Kernel Mailing List <linux-kernel@vger.kernel.org>,
        Linux API <linux-api@vger.kernel.org>,
        Paul Turner <pjt@google.com>, Ben Segall <bsegall@google.com>,
        Andrei Vagin <avagin@google.com>,
        Thierry Delisle <tdelisle@uwaterloo.ca>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Precedence: bulk

On Wed, Sep 15, 2021 at 8:45 AM Peter Zijlstra <peterz@infradead.org> wrote=
:
>
> On Tue, Sep 14, 2021 at 11:40:01AM -0700, Andy Lutomirski wrote:
> >
> >
> > On Tue, Sep 14, 2021, at 11:11 AM, Peter Zijlstra wrote:
> > > On Tue, Sep 14, 2021 at 09:52:08AM -0700, Andy Lutomirski wrote:
> > > > With a custom mapping, you don=E2=80=99t need to pin pages at all, =
I think.
> > > > As long as you can reconstruct the contents of the shared page and
> > > > you=E2=80=99re willing to do some slightly careful synchronization,=
 you can
> > > > detect that the page is missing when you try to update it and skip =
the
> > > > update. The vm_ops->fault handler can repopulate the page the next
> > > > time it=E2=80=99s accessed.
> > >
> > > The point is that the moment we know we need to do this user-poke, is
> > > schedule(), which could be called while holding mmap_sem (it being a
> > > preemptable lock). Which means we cannot go and do faults.
> >
> > That=E2=80=99s fine. The page would be in one or two states: present an=
d
> > writable by kernel or completely gone. If its present, the scheduler
> > writes it. If it=E2=80=99s gone, the scheduler skips the write and the =
next
> > fault fills it in.
>
> That's non-deterministic, and as such not suitable.

What's the precise problem?  The code would be roughly:

if (try_pin_the_page) {
  write it;
  unpin;
} else {
  do nothing -- .fault will fill in the correct contents.
}

The time this takes is nondeterministic, but it's bounded and short.

>
> > > > All that being said, I feel like I=E2=80=99m missing something. The=
 point of
> > > > this is to send what the old M:N folks called =E2=80=9Cscheduler ac=
tivations=E2=80=9D,
> > > > right?  Wouldn=E2=80=99t it be more efficient to explicitly wake so=
mething
> > > > blockable/pollable and write the message into a more efficient data
> > > > structure?  Polling one page per task from userspace seems like it
> > > > will have inherently high latency due to the polling interval and w=
ill
> > > > also have very poor locality.  Or am I missing something?
> > >
> > > The idea was to link the user structures together in a (single) linke=
d
> > > list. The server structure gets a list of all the blocked tasks. This
> > > avoids having to a full N iteration (like Java, they're talking stupi=
d
> > > number of N).
> > >
> > > Polling should not happen, once we run out of runnable tasks, the ser=
ver
> > > task gets ran again and it can instantly pick up all the blocked
> > > notifications.
> > >
> >
> > How does the server task know when to read the linked list?  And
> > what=E2=80=99s wrong with a ring buffer or a syscall?
>
> Same problem, ring-buffer has the case where it's full and events get
> dropped, at which point you've completely lost state. If it is at all
> possible to recover from that, doing so is non-deterministic.
>
> I really want this stuff to work for realtime workloads too.

A ring buffer would have a bounded size -- one word (of whatever size)
per user thread.