From: Peter Zijlstra <peterz@infradead.org> To: Guo Ren <guoren@kernel.org> Cc: linux-riscv <linux-riscv@lists.infradead.org>, Linux Kernel Mailing List <linux-kernel@vger.kernel.org>, linux-csky@vger.kernel.org, linux-arch <linux-arch@vger.kernel.org>, Guo Ren <guoren@linux.alibaba.com>, Will Deacon <will@kernel.org>, Ingo Molnar <mingo@redhat.com>, Waiman Long <longman@redhat.com>, Arnd Bergmann <arnd@arndb.de>, Anup Patel <anup@brainfault.org> Subject: Re: [PATCH v4 3/4] locking/qspinlock: Add ARCH_USE_QUEUED_SPINLOCKS_XCHG32 Date: Tue, 30 Mar 2021 18:08:40 +0200 [thread overview] Message-ID: <YGNNCEAMSWbBU+hd@hirez.programming.kicks-ass.net> (raw) In-Reply-To: <CAJF2gTRncV1+GT7nBpYkvfpyaG57o9ecaHBjoR6gEQAkG2ELrg@mail.gmail.com> On Tue, Mar 30, 2021 at 11:13:55AM +0800, Guo Ren wrote: > On Mon, Mar 29, 2021 at 8:50 PM Peter Zijlstra <peterz@infradead.org> wrote: > > > > On Mon, Mar 29, 2021 at 08:01:41PM +0800, Guo Ren wrote: > > > u32 a = 0x55aa66bb; > > > u16 *ptr = &a; > > > > > > CPU0 CPU1 > > > ========= ========= > > > xchg16(ptr, new) while(1) > > > WRITE_ONCE(*(ptr + 1), x); > > > > > > When we use lr.w/sc.w implement xchg16, it'll cause CPU0 deadlock. > > > > Then I think your LL/SC is broken. > > > > That also means you really don't want to build super complex locking > > primitives on top, because that live-lock will percolate through. > Do you mean the below implementation has live-lock risk? > +static __always_inline u32 xchg_tail(struct qspinlock *lock, u32 tail) > +{ > + u32 old, new, val = atomic_read(&lock->val); > + > + for (;;) { > + new = (val & _Q_LOCKED_PENDING_MASK) | tail; > + old = atomic_cmpxchg(&lock->val, val, new); > + if (old == val) > + break; > + > + val = old; > + } > + return old; > +} That entirely depends on the architecture (and cmpxchg() impementation). There are a number of cases: * architecture has cmpxchg() instruction (x86, s390, sparc, etc.). - architecture provides fwd progress (x86) - architecture requires backoff for progress (sparc) * architecture does not have cmpxchg, and implements it using LL/SC. and here things get *really* interesting, because while an architecture can have LL/SC fwd progress, that does not translate into cmpxchg() also having the same guarantees and all bets are off. The real bummer is that C can do cmpxchg(), but there is no way it can do LL/SC. And even if we'd teach C how to do LL/SC, it couldn't be generic because architectures lacking it can't emulate it using cmpxchg() (there's a fun class of bugs there). So while the above code might be the best we can do in generic code, it's really up to the architecture to make it work.
WARNING: multiple messages have this Message-ID (diff)
From: Peter Zijlstra <peterz@infradead.org> To: Guo Ren <guoren@kernel.org> Cc: linux-riscv <linux-riscv@lists.infradead.org>, Linux Kernel Mailing List <linux-kernel@vger.kernel.org>, linux-csky@vger.kernel.org, linux-arch <linux-arch@vger.kernel.org>, Guo Ren <guoren@linux.alibaba.com>, Will Deacon <will@kernel.org>, Ingo Molnar <mingo@redhat.com>, Waiman Long <longman@redhat.com>, Arnd Bergmann <arnd@arndb.de>, Anup Patel <anup@brainfault.org> Subject: Re: [PATCH v4 3/4] locking/qspinlock: Add ARCH_USE_QUEUED_SPINLOCKS_XCHG32 Date: Tue, 30 Mar 2021 18:08:40 +0200 [thread overview] Message-ID: <YGNNCEAMSWbBU+hd@hirez.programming.kicks-ass.net> (raw) In-Reply-To: <CAJF2gTRncV1+GT7nBpYkvfpyaG57o9ecaHBjoR6gEQAkG2ELrg@mail.gmail.com> On Tue, Mar 30, 2021 at 11:13:55AM +0800, Guo Ren wrote: > On Mon, Mar 29, 2021 at 8:50 PM Peter Zijlstra <peterz@infradead.org> wrote: > > > > On Mon, Mar 29, 2021 at 08:01:41PM +0800, Guo Ren wrote: > > > u32 a = 0x55aa66bb; > > > u16 *ptr = &a; > > > > > > CPU0 CPU1 > > > ========= ========= > > > xchg16(ptr, new) while(1) > > > WRITE_ONCE(*(ptr + 1), x); > > > > > > When we use lr.w/sc.w implement xchg16, it'll cause CPU0 deadlock. > > > > Then I think your LL/SC is broken. > > > > That also means you really don't want to build super complex locking > > primitives on top, because that live-lock will percolate through. > Do you mean the below implementation has live-lock risk? > +static __always_inline u32 xchg_tail(struct qspinlock *lock, u32 tail) > +{ > + u32 old, new, val = atomic_read(&lock->val); > + > + for (;;) { > + new = (val & _Q_LOCKED_PENDING_MASK) | tail; > + old = atomic_cmpxchg(&lock->val, val, new); > + if (old == val) > + break; > + > + val = old; > + } > + return old; > +} That entirely depends on the architecture (and cmpxchg() impementation). There are a number of cases: * architecture has cmpxchg() instruction (x86, s390, sparc, etc.). - architecture provides fwd progress (x86) - architecture requires backoff for progress (sparc) * architecture does not have cmpxchg, and implements it using LL/SC. and here things get *really* interesting, because while an architecture can have LL/SC fwd progress, that does not translate into cmpxchg() also having the same guarantees and all bets are off. The real bummer is that C can do cmpxchg(), but there is no way it can do LL/SC. And even if we'd teach C how to do LL/SC, it couldn't be generic because architectures lacking it can't emulate it using cmpxchg() (there's a fun class of bugs there). So while the above code might be the best we can do in generic code, it's really up to the architecture to make it work. _______________________________________________ linux-riscv mailing list linux-riscv@lists.infradead.org http://lists.infradead.org/mailman/listinfo/linux-riscv
next prev parent reply other threads:[~2021-03-30 16:09 UTC|newest] Thread overview: 126+ messages / expand[flat|nested] mbox.gz Atom feed top 2021-03-27 18:06 [PATCH v4 0/4] riscv: Add qspinlock/qrwlock guoren 2021-03-27 18:06 ` guoren 2021-03-27 18:06 ` [PATCH v4 1/4] riscv: cmpxchg.h: Cleanup unused code guoren 2021-03-27 18:06 ` guoren 2021-03-27 18:06 ` [PATCH v4 2/4] riscv: cmpxchg.h: Merge macros guoren 2021-03-27 18:06 ` guoren 2021-03-27 21:25 ` Arnd Bergmann 2021-03-27 21:25 ` Arnd Bergmann 2021-03-28 1:50 ` Guo Ren 2021-03-28 1:50 ` Guo Ren 2021-03-27 18:06 ` [PATCH v4 3/4] locking/qspinlock: Add ARCH_USE_QUEUED_SPINLOCKS_XCHG32 guoren 2021-03-27 18:06 ` guoren 2021-03-27 18:43 ` Waiman Long 2021-03-27 18:43 ` Waiman Long 2021-03-28 1:48 ` Guo Ren 2021-03-28 1:48 ` Guo Ren 2021-03-29 7:50 ` Peter Zijlstra 2021-03-29 7:50 ` Peter Zijlstra 2021-03-29 9:41 ` Arnd Bergmann 2021-03-29 9:41 ` Arnd Bergmann 2021-03-29 11:16 ` Peter Zijlstra 2021-03-29 11:16 ` Peter Zijlstra 2021-03-29 11:29 ` Peter Zijlstra 2021-03-29 11:29 ` Peter Zijlstra 2021-03-29 12:52 ` Guo Ren 2021-03-29 12:52 ` Guo Ren 2021-03-29 13:56 ` Arnd Bergmann 2021-03-29 13:56 ` Arnd Bergmann 2021-03-30 2:26 ` Guo Ren 2021-03-30 2:26 ` Guo Ren 2021-03-30 5:51 ` Anup Patel 2021-03-30 5:51 ` Anup Patel 2021-03-30 6:26 ` Guo Ren 2021-03-30 6:26 ` Guo Ren 2021-03-30 7:11 ` Arnd Bergmann 2021-03-30 7:11 ` Arnd Bergmann 2021-03-31 4:18 ` Guo Ren 2021-03-31 4:18 ` Guo Ren 2021-03-31 5:33 ` Paul Campbell 2021-03-31 5:33 ` Paul Campbell 2021-04-05 16:12 ` Guo Ren 2021-04-05 16:12 ` Guo Ren 2021-03-31 6:44 ` Guo Ren 2021-03-31 6:44 ` Guo Ren 2021-03-31 7:12 ` Arnd Bergmann 2021-03-31 7:12 ` Arnd Bergmann 2021-03-29 11:19 ` Guo Ren 2021-03-29 11:19 ` Guo Ren 2021-03-29 11:26 ` Peter Zijlstra 2021-03-29 11:26 ` Peter Zijlstra 2021-03-29 12:01 ` Guo Ren 2021-03-29 12:01 ` Guo Ren 2021-03-29 12:49 ` Peter Zijlstra 2021-03-29 12:49 ` Peter Zijlstra 2021-03-30 3:13 ` Guo Ren 2021-03-30 3:13 ` Guo Ren 2021-03-30 4:54 ` Anup Patel 2021-03-30 4:54 ` Anup Patel 2021-03-30 6:27 ` Guo Ren 2021-03-30 6:27 ` Guo Ren 2021-03-30 8:31 ` David Laight 2021-03-30 8:31 ` David Laight 2021-03-30 14:09 ` Waiman Long 2021-03-30 14:09 ` Waiman Long 2021-03-31 14:47 ` Guo Ren 2021-03-31 14:47 ` Guo Ren 2021-04-05 16:45 ` Guo Ren 2021-04-05 16:45 ` Guo Ren 2021-03-30 16:08 ` Peter Zijlstra [this message] 2021-03-30 16:08 ` Peter Zijlstra 2021-03-30 22:35 ` Stafford Horne 2021-03-30 22:35 ` Stafford Horne 2021-03-31 7:23 ` Arnd Bergmann 2021-03-31 7:23 ` Arnd Bergmann 2021-03-31 12:31 ` Stafford Horne 2021-03-31 12:31 ` Stafford Horne 2021-03-31 15:10 ` Guo Ren 2021-03-31 15:10 ` Guo Ren 2021-04-06 8:51 ` Stafford Horne 2021-04-06 8:51 ` Stafford Horne 2021-04-06 3:50 ` Guo Ren 2021-04-06 3:50 ` Guo Ren 2021-04-06 8:56 ` Stafford Horne 2021-04-06 8:56 ` Stafford Horne 2021-04-07 8:42 ` Arnd Bergmann 2021-04-07 8:42 ` Arnd Bergmann 2021-04-07 11:36 ` Peter Zijlstra 2021-04-07 11:36 ` Peter Zijlstra 2021-04-07 11:57 ` Arnd Bergmann 2021-04-07 11:57 ` Arnd Bergmann 2021-04-07 12:02 ` Peter Zijlstra 2021-04-07 12:02 ` Peter Zijlstra 2021-04-05 16:40 ` Guo Ren 2021-04-05 16:40 ` Guo Ren 2021-03-31 15:22 ` Guo Ren 2021-03-31 15:22 ` Guo Ren 2021-04-06 7:15 ` Peter Zijlstra 2021-04-06 7:15 ` Peter Zijlstra 2021-04-07 9:42 ` Christoph Hellwig 2021-04-07 9:42 ` Christoph Hellwig 2021-04-07 14:29 ` Christoph Müllner 2021-04-07 14:29 ` Christoph Müllner 2021-04-07 14:34 ` Christoph Hellwig 2021-04-07 14:34 ` Christoph Hellwig 2021-04-07 15:51 ` Peter Zijlstra 2021-04-07 15:51 ` Peter Zijlstra 2021-04-07 16:44 ` Peter Zijlstra 2021-04-07 16:44 ` Peter Zijlstra 2021-04-07 15:52 ` Peter Zijlstra 2021-04-07 15:52 ` Peter Zijlstra 2021-04-07 16:54 ` Peter Zijlstra 2021-04-07 16:54 ` Peter Zijlstra 2021-04-07 16:00 ` Peter Zijlstra 2021-04-07 16:00 ` Peter Zijlstra 2021-04-07 19:50 ` Christoph Müllner 2021-04-07 19:50 ` Christoph Müllner 2021-04-06 17:24 ` Boqun Feng 2021-04-06 17:24 ` Boqun Feng 2021-04-07 9:26 ` Peter Zijlstra 2021-04-07 9:26 ` Peter Zijlstra 2021-03-29 12:13 ` Anup Patel 2021-03-29 12:13 ` Anup Patel 2021-03-29 12:54 ` Peter Zijlstra 2021-03-29 12:54 ` Peter Zijlstra 2021-03-27 18:06 ` [PATCH v4 4/4] riscv: Convert custom spinlock/rwlock to generic qspinlock/qrwlock guoren 2021-03-27 18:06 ` guoren
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=YGNNCEAMSWbBU+hd@hirez.programming.kicks-ass.net \ --to=peterz@infradead.org \ --cc=anup@brainfault.org \ --cc=arnd@arndb.de \ --cc=guoren@kernel.org \ --cc=guoren@linux.alibaba.com \ --cc=linux-arch@vger.kernel.org \ --cc=linux-csky@vger.kernel.org \ --cc=linux-kernel@vger.kernel.org \ --cc=linux-riscv@lists.infradead.org \ --cc=longman@redhat.com \ --cc=mingo@redhat.com \ --cc=will@kernel.org \ /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: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.