From: Peter Oskolkov <posk@posk.io>
To: Peter Zijlstra <peterz@infradead.org>,
Ingo Molnar <mingo@redhat.com>,
Thomas Gleixner <tglx@linutronix.de>,
linux-kernel@vger.kernel.org, linux-api@vger.kernel.org
Cc: Paul Turner <pjt@google.com>, Ben Segall <bsegall@google.com>,
Peter Oskolkov <posk@google.com>, Peter Oskolkov <posk@posk.io>,
Joel Fernandes <joel@joelfernandes.org>,
Andrei Vagin <avagin@google.com>,
Jim Newsome <jnewsome@torproject.org>,
Jann Horn <jannh@google.com>,
Thierry Delisle <tdelisle@uwaterloo.ca>
Subject: [RFC PATCH 3/4 v0.3] sched/umcg: RFC: add userspace sll helpers
Date: Fri, 16 Jul 2021 11:47:18 -0700 [thread overview]
Message-ID: <20210716184719.269033-4-posk@google.com> (raw)
In-Reply-To: <20210716184719.269033-1-posk@google.com>
The helpers below can work with userspace single-linked lists concurrently
without indefinitely spinning in the kernel. Specifically:
push (add to the head of the list):
step = 0
while (++step < N)
old = *head
*next = old
cmp_xchng(head, &old, next)
pop (remove the first element from the list):
mark the node as deleted by flipping its lowest bit without
actually removing the node from the list:
curr = *head
step = 0
while (curr && ++step < N)
next = *curr
if (next & 1)
curr = next & ~1
continue
if (cmp_xchng(curr, next, next | 1))
return curr
else
curr = next & ~1
It is the userspace's responsibility to actually remove the
nodes marked as deleted from the list.
v0.2->v0.3 changes:
- removed spinning from the kernel (other than capped cmpxchg).
Signed-off-by: Peter Oskolkov <posk@google.com>
---
kernel/sched/umcg.h | 116 ++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 116 insertions(+)
diff --git a/kernel/sched/umcg.h b/kernel/sched/umcg.h
index 288017f5368c..435531d751f2 100644
--- a/kernel/sched/umcg.h
+++ b/kernel/sched/umcg.h
@@ -165,5 +165,121 @@ static inline int cmpxchg_user_64(u64 __user *uaddr, u64 *old, u64 new)
ret; \
})
+/**
+ * umcg_sll_push - push a node onto a single-linked-list (stack) in userspace
+ * @head - a pointer to the head of the stack;
+ * @node - a pointer to the node to push;
+ * @max_tries - the maximum number of attempts to push the node onto the list.
+ *
+ * Push a node onto a single-linked list (stack). The function tries
+ * @max_tries times and returns -EAGAIN if too many concurrent updates, so that
+ * the caller may yield the CPU.
+ *
+ * Return:
+ * 0 - success;
+ * -EFAULT - error;
+ * -EAGAIN - try again.
+ */
+static inline int umcg_sll_push(u64 __user *head, u64 __user *node, int max_tries)
+{
+ int step;
+
+ for (step = 0; step < max_tries; step++) {
+ int ret;
+ u64 first;
+
+ smp_mb(); /* Make the read below clean. */
+ if (get_user(first, head))
+ return -EFAULT;
+
+ if (put_user(first, node))
+ return -EFAULT;
+ smp_mb(); /* Make the write above visible. */
+
+ ret = cmpxchg_user_64(head, &first, (u64)node);
+ if (!ret)
+ return 0;
+
+ if (ret == -EAGAIN) {
+ cpu_relax();
+ continue;
+ }
+
+ if (WARN_ONCE(ret != -EFAULT, "unexpected umcg_cmpxchg result"))
+ return -EFAULT;
+
+ return -EFAULT;
+ }
+
+ return -EAGAIN;
+}
+
+/**
+ * umcg_sll_pop - pop a node from a single-linked-list (stack) in the userspace
+ * @head - a pointer to the head of the stack;
+ * @value - a pointer to where store the popped value;
+ * @max_tries - the maximum number of nodes to try to pop.
+ *
+ * Pop a node from a single-linked list (stack). Internally, popped nodes
+ * are marked as such, and not actually removed from the list, to avoid
+ * the ABA problem. It is the responsibility of the userspace to do GC.
+ *
+ * As an additional protection, the function checks only the first
+ * @max_tries nodes.
+ *
+ * Note: on success, @value should be cast to (u64 __user *) if not zero.
+ *
+ * Return:
+ * 0 - success;
+ * -EFAULT - error;
+ * -EAGAIN - try again.
+ */
+static inline int umcg_sll_pop(u64 __user *head, u64 *value, int max_tries)
+{
+ int step;
+ u64 curr;
+
+ smp_mb(); /* Make the read below clean. */
+ if (get_user(curr, head))
+ return -EFAULT;
+
+ for (step = 0; step < max_tries; step++) {
+ int ret;
+ u64 next;
+
+ if (!curr) {
+ *value = 0UL;
+ return 0;
+ }
+
+ if (curr & 1UL)
+ return -EFAULT; /* Should not happen. */
+
+ smp_mb(); /* Make the read below clean. */
+ if (get_user(next, (u64 __user *)curr))
+ return -EFAULT;
+
+ if (next & 1UL) { /* curr is deleted */
+ curr = next & ~1UL;
+ continue;
+ }
+
+ ret = cmpxchg_user_64((u64 __user *)curr, &next, next | 1UL);
+ if (!ret) {
+ *value = curr;
+ return 0;
+ }
+ if (ret == -EAGAIN) {
+ curr = next & ~1UL;
+ cpu_relax();
+ continue;
+ }
+
+ if (ret)
+ return -EFAULT;
+ }
+
+ return -EAGAIN;
+}
#endif /* CONFIG_X86_64 */
#endif /* _KERNEL_SCHED_UMCG_H */
--
2.25.1
next prev parent reply other threads:[~2021-07-16 18:47 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 ` Peter Oskolkov [this message]
2021-07-17 0:58 ` [RFC PATCH 3/4 v0.3] sched/umcg: RFC: add userspace sll helpers 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
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=20210716184719.269033-4-posk@google.com \
--to=posk@posk.io \
--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=peterz@infradead.org \
--cc=pjt@google.com \
--cc=posk@google.com \
--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).