From: Peter Oskolkov <posk@google.com>
To: Thierry Delisle <tdelisle@uwaterloo.ca>
Cc: posk@posk.io, avagin@google.com, bsegall@google.com,
jannh@google.com, jnewsome@torproject.org,
joel@joelfernandes.org, linux-api@vger.kernel.org,
linux-kernel@vger.kernel.org, mingo@redhat.com,
peterz@infradead.org, pjt@google.com, tglx@linutronix.de,
Peter Buhr <pabuhr@uwaterloo.ca>
Subject: Re: [RFC PATCH 4/4 v0.3] sched/umcg: RFC: implement UMCG syscalls
Date: Mon, 19 Jul 2021 10:29:59 -0700 [thread overview]
Message-ID: <CAPNVh5cmhFEWr4bmODkDDFhV=mHLcO0DZJ432GEL=OitzPP80g@mail.gmail.com> (raw)
In-Reply-To: <2c971806-b8f6-50b9-491f-e1ede4a33579@uwaterloo.ca>
On Mon, Jul 19, 2021 at 9:07 AM Thierry Delisle <tdelisle@uwaterloo.ca> wrote:
>
> > /**
> > * @idle_servers_ptr: a single-linked list pointing to the list
> > * of idle servers. Can be NULL.
> > *
> > * Readable/writable by both the kernel and the userspace: the
> > * userspace adds items to the list, the kernel removes them.
> > *
> > * This is a single-linked list (stack): head->next->next->next->NULL.
> > * "next" nodes are idle_servers_ptr fields in struct umcg_task.
> > *
> > * Example:
> > *
> > * a running worker idle server 1 idle server 2
> > *
> > * struct umct_task: struct umcg_task: struct umcg_task:
> > * state state state
> > * api_version api_version api_version
> > * ... ... ...
> > * idle_servers_ptr --> head --> idle_servers_ptr -->
> idle_servers_ptr --> NULL
> > * ... ... ...
> > *
> > *
> > * Due to the way struct umcg_task is aligned, idle_servers_ptr
> > * is aligned at 8 byte boundary, and so has its first byte as zero
> > * when it holds a valid pointer.
> > *
> > * When pulling idle servers from the list, the kernel marks nodes as
> > * "deleted" by ORing the node value (the pointer) with 1UL atomically.
> > * If a node is "deleted" (i.e. its value AND 1UL is not zero),
> > * the kernel proceeds to the next node.
> > *
> > * The kernel checks at most [nr_cpu_ids * 2] first nodes in the list.
> > *
> > * It is NOT considered an error if the kernel cannot find an idle
> > * server.
> > *
> > * The userspace is responsible for cleanup/gc (i.e. for actually
> > * removing nodes marked as "deleted" from the list).
> > */
> > uint64_t idle_servers_ptr; /* r/w */
>
> I don't understand the reason for using this ad-hoc scheme, over using a
> simple
> eventfd to do the job. As I understand it, the goal here is to let
> servers that
> cannot find workers to run, block instead of spinning. Isn't that
> exactly what
> the eventfd interface is for?
Latency/efficiency: on worker wakeup an idle server can be picked from
the list and context-switched into synchronously, on the same CPU.
Using FDs and select/poll/epoll will add extra layers of abstractions;
synchronous context-switches (not yet fully implemented in UMCG) will
most likely be impossible. This patchset seems much more efficient and
lightweight than whatever can be built on top of FDs.
>
> Have you considered an idle_fd field, the kernel writes 1 to the fd when a
> worker is appended to the idle_workers_ptr? Servers that don't find work can
> read the fd or alternatively use select/poll/epoll. Multiple workers are
> expected to share fds, either a single global fd, one fd per server, or any
> other combination the scheduler may fancy.
>
next prev parent reply other threads:[~2021-07-19 18:27 UTC|newest]
Thread overview: 14+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-07-16 18:47 [RFC PATCH 0/4 v0.3] sched/UMCG Peter Oskolkov
2021-07-16 18:47 ` [RFC PATCH 1/4 v0.3] sched: add WF_CURRENT_CPU and externise ttwu Peter Oskolkov
2021-07-16 18:47 ` [RFC PATCH 2/4 v0.3] sched/umcg: RFC: add userspace atomic helpers Peter Oskolkov
2021-07-16 18:47 ` [RFC PATCH 3/4 v0.3] sched/umcg: RFC: add userspace sll helpers Peter Oskolkov
2021-07-17 0:58 ` Thierry Delisle
2021-07-16 18:47 ` [RFC PATCH 4/4 v0.3] sched/umcg: RFC: implement UMCG syscalls Peter Oskolkov
2021-07-19 16:07 ` Thierry Delisle
2021-07-19 17:29 ` Peter Oskolkov [this message]
2021-07-19 18:13 ` Thierry Delisle
2021-07-19 19:46 ` Peter Oskolkov
2021-07-21 19:55 ` Thierry Delisle
2021-07-21 23:44 ` Peter Oskolkov
2021-07-23 19:06 ` Thierry Delisle
2021-07-26 16:44 ` Peter Oskolkov
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAPNVh5cmhFEWr4bmODkDDFhV=mHLcO0DZJ432GEL=OitzPP80g@mail.gmail.com' \
--to=posk@google.com \
--cc=avagin@google.com \
--cc=bsegall@google.com \
--cc=jannh@google.com \
--cc=jnewsome@torproject.org \
--cc=joel@joelfernandes.org \
--cc=linux-api@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=mingo@redhat.com \
--cc=pabuhr@uwaterloo.ca \
--cc=peterz@infradead.org \
--cc=pjt@google.com \
--cc=posk@posk.io \
--cc=tdelisle@uwaterloo.ca \
--cc=tglx@linutronix.de \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).