From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-14.2 required=3.0 tests=BAYES_00,DKIMWL_WL_HIGH, DKIM_SIGNED,DKIM_VALID,INCLUDES_CR_TRAILER,INCLUDES_PATCH,MAILING_LIST_MULTI, SPF_HELO_NONE,SPF_PASS,URIBL_BLOCKED autolearn=unavailable autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id B5D22C433E0 for ; Wed, 24 Mar 2021 12:25:51 +0000 (UTC) Received: from desiato.infradead.org (desiato.infradead.org [90.155.92.199]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id 2F13361A0A for ; Wed, 24 Mar 2021 12:25:51 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 2F13361A0A Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=kernel.org Authentication-Results: mail.kernel.org; spf=none smtp.mailfrom=linux-riscv-bounces+linux-riscv=archiver.kernel.org@lists.infradead.org DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=desiato.20200630; h=Sender:Content-Transfer-Encoding :Content-Type:List-Subscribe:List-Help:List-Post:List-Archive: List-Unsubscribe:List-Id:Cc:To:Subject:Message-ID:Date:From:In-Reply-To: References:MIME-Version:Reply-To:Content-ID:Content-Description:Resent-Date: Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:List-Owner; bh=HN//Pe3p/ljzp4TasPxgeWrV+wKUVVO8zaxJCHprjlI=; b=cTTm3jzSYvP2lziX95QgLPozJ B51nbShm1jLFT12mjMm7NhieHdH/509PB5YAjNJOoi/U1ZIiWBrG5V+smvcZ8p6uPUMTzM1ldDm3p aODP6KKAT9CdsCB6bgWuLa3fZ2lmcZnGlxSUYzMrS8/45Z8SdoNFajktc2Ex8kUgQTXYEcp2Lbq3L rwFqFw8Oeres32FVNgYgDuKXkdMx6aU8L+t5ZuQ1O/56mYqFzbVSwxY6yDZx6i2RjpXm30+yqKdj9 HXqOj8Aj+O0E7DkHPaAMFZOG2bo3keYZlCQtSkwV12ixy/SNdHwVpU/eh98zNZi1SnDR49fa7Y3DW fBRHqVcrg==; Received: from localhost ([::1] helo=desiato.infradead.org) by desiato.infradead.org with esmtp (Exim 4.94 #2 (Red Hat Linux)) id 1lP2Zz-00H4cj-9R; Wed, 24 Mar 2021 12:25:43 +0000 Received: from mail.kernel.org ([198.145.29.99]) by desiato.infradead.org with esmtps (Exim 4.94 #2 (Red Hat Linux)) id 1lP2Z9-00H43x-3f for linux-riscv@lists.infradead.org; Wed, 24 Mar 2021 12:24:55 +0000 Received: by mail.kernel.org (Postfix) with ESMTPSA id 3A18A61A0C for ; Wed, 24 Mar 2021 12:24:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1616588688; bh=BXm3zkQ5Yjf6l+F8X1T+BW05dzKb+rl9rVFAsGKCTFA=; h=References:In-Reply-To:From:Date:Subject:To:Cc:From; b=QdaYQcKcth121k/VXNlsXTvdxZYWbwhTp8vVog49HmChmpdvW9xiKLNxzoxTPF5rw kzollqGyldN5oC1Gb0wWA4J7Aljydph9xQUzwCrLn7gBUx0EcmlJHBY5r3Y/d1FXLo AXkAFiqmlli0XfneVfameVehoEDOtWpZR6CCM5ceqWSmTiHu/X4N5bvl1ALAsc4vdb insAonEzCM3bU1IAlXWf51vgHRxMFFgqeHplKNucz7dYMhG51qEf61mcFt/SP6coX/ lj6jY8OBYvRj00liXjcfWPT4x0qwWzqwqjhxk/KnFiUYNzgKeYq0UGrdtvFFBnUHhs ZtlpLBPl/7Ntw== Received: by mail-lf1-f42.google.com with SMTP id 75so31620044lfa.2 for ; Wed, 24 Mar 2021 05:24:48 -0700 (PDT) X-Gm-Message-State: AOAM5339Ezf4IbYIG7J1EbFmd0+UAQsi5qAYo+qLrLcc+9T6JAO4dLAv pMLlornMxLn3F4ae8XAfsW4UTF8Ryf0IVPb+9FA= X-Google-Smtp-Source: ABdhPJyTJ8ZaRt6/6JYG7WfQyVzBpd3bfpGGAi4niZdbAIm61S+hgiy1MrIJy6dpzABw2yhhZWXDg/kWvcvQ2HRBaik= X-Received: by 2002:a05:6512:3d1c:: with SMTP id d28mr1742491lfv.41.1616588686431; Wed, 24 Mar 2021 05:24:46 -0700 (PDT) MIME-Version: 1.0 References: <1616580892-80815-1-git-send-email-guoren@kernel.org> In-Reply-To: From: Guo Ren Date: Wed, 24 Mar 2021 20:24:34 +0800 X-Gmail-Original-Message-ID: Message-ID: Subject: Re: [PATCH] riscv: locks: introduce ticket-based spinlock implementation To: Vitaly Wool Cc: linux-riscv , LKML , Guo Ren , Catalin Marinas , Will Deacon , Peter Zijlstra , Palmer Dabbelt , Anup Patel , Arnd Bergmann X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20210324_122452_192556_171DCF27 X-CRM114-Status: GOOD ( 24.51 ) X-BeenThere: linux-riscv@lists.infradead.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Sender: "linux-riscv" Errors-To: linux-riscv-bounces+linux-riscv=archiver.kernel.org@lists.infradead.org On Wed, Mar 24, 2021 at 7:16 PM Vitaly Wool wrote: > > > > On Wed, Mar 24, 2021, 11:16 AM wrote: >> >> From: Guo Ren >> >> This patch introduces a ticket lock implementation for riscv, along the >> same lines as the implementation for arch/arm & arch/csky. > > > Could you please provide a rationale for this? Like, what is wrong with the current implementation. Ticket based spinlock's principle is here: https://lwn.net/Articles/267968/ Current implementation will cause cache line bouncing when many harts are acquiring the same spinlock. I'm seeking a solution, maybe not fitting the current RISC-V base ISA. I'll add more comments in the next version of patch. > > Thanks in advance, > > Best regards, > Vitaly >> >> >> Signed-off-by: Guo Ren >> Cc: Catalin Marinas >> Cc: Will Deacon >> Cc: Peter Zijlstra >> Cc: Palmer Dabbelt >> Cc: Anup Patel >> Cc: Arnd Bergmann >> --- >> arch/riscv/Kconfig | 1 + >> arch/riscv/include/asm/Kbuild | 1 + >> arch/riscv/include/asm/spinlock.h | 158 ++++++++++++-------------------- >> arch/riscv/include/asm/spinlock_types.h | 19 ++-- >> 4 files changed, 74 insertions(+), 105 deletions(-) >> >> diff --git a/arch/riscv/Kconfig b/arch/riscv/Kconfig >> index 87d7b52..7c56a20 100644 >> --- a/arch/riscv/Kconfig >> +++ b/arch/riscv/Kconfig >> @@ -30,6 +30,7 @@ config RISCV >> select ARCH_HAS_STRICT_KERNEL_RWX if MMU >> select ARCH_OPTIONAL_KERNEL_RWX if ARCH_HAS_STRICT_KERNEL_RWX >> select ARCH_OPTIONAL_KERNEL_RWX_DEFAULT >> + select ARCH_USE_QUEUED_RWLOCKS >> select ARCH_WANT_DEFAULT_TOPDOWN_MMAP_LAYOUT if MMU >> select ARCH_WANT_FRAME_POINTERS >> select ARCH_WANT_HUGE_PMD_SHARE if 64BIT >> diff --git a/arch/riscv/include/asm/Kbuild b/arch/riscv/include/asm/Kbuild >> index 445ccc9..e57ef80 100644 >> --- a/arch/riscv/include/asm/Kbuild >> +++ b/arch/riscv/include/asm/Kbuild >> @@ -3,5 +3,6 @@ generic-y += early_ioremap.h >> generic-y += extable.h >> generic-y += flat.h >> generic-y += kvm_para.h >> +generic-y += qrwlock.h >> generic-y += user.h >> generic-y += vmlinux.lds.h >> diff --git a/arch/riscv/include/asm/spinlock.h b/arch/riscv/include/asm/spinlock.h >> index f4f7fa1..2c81764 100644 >> --- a/arch/riscv/include/asm/spinlock.h >> +++ b/arch/riscv/include/asm/spinlock.h >> @@ -7,129 +7,91 @@ >> #ifndef _ASM_RISCV_SPINLOCK_H >> #define _ASM_RISCV_SPINLOCK_H >> >> -#include >> -#include >> -#include >> - >> /* >> - * Simple spin lock operations. These provide no fairness guarantees. >> + * Ticket-based spin-locking. >> */ >> +static inline void arch_spin_lock(arch_spinlock_t *lock) >> +{ >> + arch_spinlock_t lockval; >> + u32 tmp; >> + >> + asm volatile ( >> + "1: lr.w %0, %2 \n" >> + " mv %1, %0 \n" >> + " addw %0, %0, %3 \n" >> + " sc.w %0, %0, %2 \n" >> + " bnez %0, 1b \n" >> + : "=&r" (tmp), "=&r" (lockval), "+A" (lock->lock) >> + : "r" (1 << TICKET_NEXT) >> + : "memory"); >> >> -/* FIXME: Replace this with a ticket lock, like MIPS. */ >> - >> -#define arch_spin_is_locked(x) (READ_ONCE((x)->lock) != 0) >> + while (lockval.tickets.next != lockval.tickets.owner) { >> + /* >> + * FIXME - we need wfi/wfe here to prevent: >> + * - cache line bouncing >> + * - saving cpu pipeline in multi-harts-per-core >> + * processor >> + */ >> + lockval.tickets.owner = READ_ONCE(lock->tickets.owner); >> + } >> >> -static inline void arch_spin_unlock(arch_spinlock_t *lock) >> -{ >> - smp_store_release(&lock->lock, 0); >> + __atomic_acquire_fence(); >> } >> >> static inline int arch_spin_trylock(arch_spinlock_t *lock) >> { >> - int tmp = 1, busy; >> - >> - __asm__ __volatile__ ( >> - " amoswap.w %0, %2, %1\n" >> - RISCV_ACQUIRE_BARRIER >> - : "=r" (busy), "+A" (lock->lock) >> - : "r" (tmp) >> + u32 tmp, contended, res; >> + >> + do { >> + asm volatile ( >> + " lr.w %0, %3 \n" >> + " srliw %1, %0, %5 \n" >> + " slliw %2, %0, %5 \n" >> + " or %1, %2, %1 \n" >> + " li %2, 0 \n" >> + " sub %1, %1, %0 \n" >> + " bnez %1, 1f \n" >> + " addw %0, %0, %4 \n" >> + " sc.w %2, %0, %3 \n" >> + "1: \n" >> + : "=&r" (tmp), "=&r" (contended), "=&r" (res), >> + "+A" (lock->lock) >> + : "r" (1 << TICKET_NEXT), "I" (TICKET_NEXT) >> : "memory"); >> + } while (res); >> >> - return !busy; >> -} >> - >> -static inline void arch_spin_lock(arch_spinlock_t *lock) >> -{ >> - while (1) { >> - if (arch_spin_is_locked(lock)) >> - continue; >> - >> - if (arch_spin_trylock(lock)) >> - break; >> + if (!contended) { >> + __atomic_acquire_fence(); >> + return 1; >> + } else { >> + return 0; >> } >> } >> >> -/***********************************************************/ >> - >> -static inline void arch_read_lock(arch_rwlock_t *lock) >> +static inline void arch_spin_unlock(arch_spinlock_t *lock) >> { >> - int tmp; >> - >> - __asm__ __volatile__( >> - "1: lr.w %1, %0\n" >> - " bltz %1, 1b\n" >> - " addi %1, %1, 1\n" >> - " sc.w %1, %1, %0\n" >> - " bnez %1, 1b\n" >> - RISCV_ACQUIRE_BARRIER >> - : "+A" (lock->lock), "=&r" (tmp) >> - :: "memory"); >> + smp_store_release(&lock->tickets.owner, lock->tickets.owner + 1); >> + /* FIXME - we need ipi/sev here to notify above */ >> } >> >> -static inline void arch_write_lock(arch_rwlock_t *lock) >> +static inline int arch_spin_value_unlocked(arch_spinlock_t lock) >> { >> - int tmp; >> - >> - __asm__ __volatile__( >> - "1: lr.w %1, %0\n" >> - " bnez %1, 1b\n" >> - " li %1, -1\n" >> - " sc.w %1, %1, %0\n" >> - " bnez %1, 1b\n" >> - RISCV_ACQUIRE_BARRIER >> - : "+A" (lock->lock), "=&r" (tmp) >> - :: "memory"); >> + return lock.tickets.owner == lock.tickets.next; >> } >> >> -static inline int arch_read_trylock(arch_rwlock_t *lock) >> +static inline int arch_spin_is_locked(arch_spinlock_t *lock) >> { >> - int busy; >> - >> - __asm__ __volatile__( >> - "1: lr.w %1, %0\n" >> - " bltz %1, 1f\n" >> - " addi %1, %1, 1\n" >> - " sc.w %1, %1, %0\n" >> - " bnez %1, 1b\n" >> - RISCV_ACQUIRE_BARRIER >> - "1:\n" >> - : "+A" (lock->lock), "=&r" (busy) >> - :: "memory"); >> - >> - return !busy; >> + return !arch_spin_value_unlocked(READ_ONCE(*lock)); >> } >> >> -static inline int arch_write_trylock(arch_rwlock_t *lock) >> +static inline int arch_spin_is_contended(arch_spinlock_t *lock) >> { >> - int busy; >> - >> - __asm__ __volatile__( >> - "1: lr.w %1, %0\n" >> - " bnez %1, 1f\n" >> - " li %1, -1\n" >> - " sc.w %1, %1, %0\n" >> - " bnez %1, 1b\n" >> - RISCV_ACQUIRE_BARRIER >> - "1:\n" >> - : "+A" (lock->lock), "=&r" (busy) >> - :: "memory"); >> + struct __raw_tickets tickets = READ_ONCE(lock->tickets); >> >> - return !busy; >> + return (tickets.next - tickets.owner) > 1; >> } >> +#define arch_spin_is_contended arch_spin_is_contended >> >> -static inline void arch_read_unlock(arch_rwlock_t *lock) >> -{ >> - __asm__ __volatile__( >> - RISCV_RELEASE_BARRIER >> - " amoadd.w x0, %1, %0\n" >> - : "+A" (lock->lock) >> - : "r" (-1) >> - : "memory"); >> -} >> - >> -static inline void arch_write_unlock(arch_rwlock_t *lock) >> -{ >> - smp_store_release(&lock->lock, 0); >> -} >> +#include >> >> #endif /* _ASM_RISCV_SPINLOCK_H */ >> diff --git a/arch/riscv/include/asm/spinlock_types.h b/arch/riscv/include/asm/spinlock_types.h >> index f398e76..d7b38bf 100644 >> --- a/arch/riscv/include/asm/spinlock_types.h >> +++ b/arch/riscv/include/asm/spinlock_types.h >> @@ -10,16 +10,21 @@ >> # error "please don't include this file directly" >> #endif >> >> +#define TICKET_NEXT 16 >> + >> typedef struct { >> - volatile unsigned int lock; >> + union { >> + u32 lock; >> + struct __raw_tickets { >> + /* little endian */ >> + u16 owner; >> + u16 next; >> + } tickets; >> + }; >> } arch_spinlock_t; >> >> -#define __ARCH_SPIN_LOCK_UNLOCKED { 0 } >> - >> -typedef struct { >> - volatile unsigned int lock; >> -} arch_rwlock_t; >> +#define __ARCH_SPIN_LOCK_UNLOCKED { { 0 } } >> >> -#define __ARCH_RW_LOCK_UNLOCKED { 0 } >> +#include >> >> #endif /* _ASM_RISCV_SPINLOCK_TYPES_H */ >> -- >> 2.7.4 >> >> >> _______________________________________________ >> linux-riscv mailing list >> linux-riscv@lists.infradead.org >> http://lists.infradead.org/mailman/listinfo/linux-riscv -- Best Regards Guo Ren ML: https://lore.kernel.org/linux-csky/ _______________________________________________ linux-riscv mailing list linux-riscv@lists.infradead.org http://lists.infradead.org/mailman/listinfo/linux-riscv