Re: [RFC PATCH 2/3 v0.2] sched/umcg: RFC: add userspace atomic helpers

[Peter Oskolkov]

On Fri, Jul 9, 2021 at 1:02 AM Peter Zijlstra <peterz@xxxxxxxxxxxxx> wrote:
>
> On Thu, Jul 08, 2021 at 12:46:37PM -0700, Peter Oskolkov wrote:
>
> > +static inline int umcg_atomic_cmpxchg_64(u64 *uval, u64 __user *uaddr,
> > +                                             u64 oldval, u64 newval)
> > +{
> > +     int ret = 0;
> > +
> > +     if (!user_access_begin(uaddr, sizeof(u64)))
> > +             return -EFAULT;
> > +     asm volatile("\n"
> > +             "1:\t" LOCK_PREFIX "cmpxchgq %4, %2\n"
> > +             "2:\n"
> > +             "\t.section .fixup, \"ax\"\n"
> > +             "3:\tmov     %3, %0\n"
> > +             "\tjmp     2b\n"
> > +             "\t.previous\n"
> > +             _ASM_EXTABLE_UA(1b, 3b)
> > +             : "+r" (ret), "=a" (oldval), "+m" (*uaddr)
> > +             : "i" (-EFAULT), "r" (newval), "1" (oldval)
> > +             : "memory"
> > +     );
> > +     user_access_end();
> > +     *uval = oldval;
> > +     return ret;
> > +}
>
> > +static inline int fix_pagefault(unsigned long uaddr, bool write_fault)
> > +{
> > +     struct mm_struct *mm = current->mm;
> > +     int ret;
> > +
> > +     mmap_read_lock(mm);
> > +     ret = fixup_user_fault(mm, uaddr, write_fault ? FAULT_FLAG_WRITE : 0,
> > +                     NULL);
> > +     mmap_read_unlock(mm);
> > +
> > +     return ret < 0 ? ret : 0;
> > +}
>
> > +static inline int umcg_cmpxchg_64_user(u64 __user *uaddr, u64 *prev, u64 val)
> > +{
> > +     while (true) {
> > +             int ret;
> > +             u64 expected = *prev;
> > +
> > +             pagefault_disable();
> > +             ret = umcg_atomic_cmpxchg_64(prev, uaddr, expected, val);
> > +             pagefault_enable();
> > +
> > +             if (!ret)
> > +                     return *prev == expected ? 0 : -EAGAIN;
> > +
> > +             if (WARN_ONCE(ret != -EFAULT, "Unexpected error"))
> > +                     return -EFAULT;
> > +
> > +             ret = fix_pagefault((unsigned long)uaddr, true);
> > +             if (ret)
> > +                     return -EFAULT;
> > +     }
> > +}
> > +
> > +/**
> > + * atomic_stack_push_user - push a node onto the stack
> > + * @head - a pointer to the head of the stack;
> > + * @node - a pointer to the node to push.
> > + *
> > + * Push a node onto a single-linked list (stack). Atomicity/correctness
> > + * is guaranteed by locking the head via settings its first bit (assuming
> > + * the pointer is aligned).
> > + *
> > + * Return: 0 on success, -EFAULT on error.
> > + */
> > +static inline int atomic_stack_push_user(u64 __user *head, u64 __user *node)
> > +{
> > +     while (true) {
> > +             int ret;
> > +             u64 first;
> > +
> > +             smp_mb();  /* Make the read below clean. */
> > +             if (get_user(first, head))
> > +                     return -EFAULT;
> > +
> > +             if (first & 1UL) {
> > +                     cpu_relax();
> > +                     continue;  /* first is being deleted. */
> > +             }
> > +
> > +             if (put_user(first, node))
> > +                     return -EFAULT;
> > +             smp_mb();  /* Make the write above visible. */
> > +
> > +             ret = umcg_cmpxchg_64_user(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;
> > +     }
> > +}
>
>
> This is horrible... Jann is absolutely right, you do not, *ever* do
> userspace spinlocks. What's wrong with the trivial lockless single
> linked list approach?.

I'm not sure how to get around the ABA problem with a lockless single
linked list: https://en.wikipedia.org/wiki/ABA_problem

Our semantics can probably be relied on to prevent ABA from happening
with idle workers (popped/removed by the userspace), but idle servers
can trivially have it:

(initial state): head => Server A => Server B => NULL

task1 :
- read head (get A), read A (get B), {/* delayed */}

tasks 2-3-4:
- pop A, pop B, push A

task 1:
- cmp_xchg(head, A /* old */, B /* new */) - succeeds, now B is in the
list erroneously

>
> On top of that, you really want to avoid all that endless stac/clac
> nonsense and only have that once, at the outer edges of things.
>
> Something like the *completely* untested below (except it needs lots of
> extra gunk to support compilers without asm-goto-output, and more widths
> and ...

I'll try the approach you suggest below once it is clear how to deal
with the ABA issue (and the wake server issue raised in patch 3).

>
>
> #define __try_cmpxchg_user_size(ptr, oldp, new, size, label)            \
> ({                                                                      \
>         _Bool __success;                                                \
>         __chk_user_ptr(ptr);                                            \
>         __typeof__(ptr) _old = (__typeof__(ptr))(oldp);                 \
>         __typeof__(*(ptr)) __old = *_old;                               \
>         __typeof__(*(ptr)) __new = (new);                               \
>         switch (size) {                                                 \
>         case 8:                                                         \
>                 volatile u64 *__ptr = (volatile u64 *)(ptr);            \
>                 asm_volatile_goto("1: " LOCK_PREFIX "cmpxchgq %[new], %[ptr]" \
>                                   CC_SET(z)                             \
>                                   _ASM_EXTABLE_UA(1b, %l[label])        \
>                                   : CC_OUT(x) (__success),              \
>                                     [ptr] "+m" (*__ptr),                \
>                                     [old] "+a" (__old),                 \
>                                   : [new] "r" (__new)                   \
>                                   : "memory"                            \
>                                   : label);                             \
>                 break;                                                  \
>         }                                                               \
>         if (unlikely(!success))                                         \
>                 *_old = __old;                                          \
>         __success;                                                      \
> })
>
> #define unsafe_try_cmpxchg_user(ptr, oldp, new, label)                  \
>         __try_cmpxchg_user_size((ptr), (oldp), (new), sizeof(*(ptr)), label);
>
> int user_llist_add(u64 __user *new, u64 __user *head)
> {
>         u64 first;
>         int ret;
>
>         if (unlikely(!access_ok(new, sizeof(*new)) ||
>                      !access_ok(head, sizeof(*head))))
>                 return -EFAULT;
>
> again:
>         __uaccess_begin_nospec();
>
>         unsafe_get_user(first, head, Efault_head);
>         do {
>                 unsafe_put_user(first, new, Efault_new);
>         } while (!unsafe_try_cmpxchg_user(head, &first, new, Efault_head));
>
>         user_access_end();
>
>         return 0;
>
> Efault_new:
>         user_access_end();
>
>         ret = fixup_fault(new);
>         if (ret < 0)
>                 return ret;
>
>         goto again;
>
> Efault_head:
>         user_access_end();
>
>         ret = fixup_fault(head);
>         if (ret < 0)
>                 return ret;
>
>         goto again;
> }