From patchwork Mon Apr 5 14:47:27 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Christoph_M=C3=BCllner?= X-Patchwork-Id: 1462432 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=none (no SPF record) smtp.mailfrom=lists.infradead.org (client-ip=2001:8b0:10b:1:d65d:64ff:fe57:4e05; helo=desiato.infradead.org; envelope-from=opensbi-bounces+incoming=patchwork.ozlabs.org@lists.infradead.org; receiver=) Authentication-Results: ozlabs.org; dkim=pass (2048-bit key; secure) header.d=lists.infradead.org header.i=@lists.infradead.org header.a=rsa-sha256 header.s=desiato.20200630 header.b=hKK31kgW; dkim-atps=neutral Received: from desiato.infradead.org (desiato.infradead.org [IPv6:2001:8b0:10b:1:d65d:64ff:fe57:4e05]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4FDYRN0DRCz9sRf for ; Tue, 6 Apr 2021 00:47:44 +1000 (AEST) 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:MIME-Version:Message-Id:Date:Subject:Cc:To:From: Reply-To:Content-ID:Content-Description:Resent-Date:Resent-From:Resent-Sender :Resent-To:Resent-Cc:Resent-Message-ID:In-Reply-To:References:List-Owner; bh=sQL9RcViZfST92U3UFA+nqzmKSy/8jH145+DHPjmbDw=; b=hKK31kgWEliJm9VQlbdLmMssv4 lhFCMdS/5xvpJlt4CBmNbCimDgdnlWPU6gJngMhlwd40O6Loj0aUjZDgESJWREDc+yHode0/Wq61O bX1z/tnQT0apYVDAoUlAdaWRbMSIO7rG8ixPCKpMUtplMyxfxktgE+4p2y4ijWIFfnpOyuJqdcqPL h2eE5L4/Lo6V03Y2s/uvRXSO34Ae4xZ+cv9Zafh/bc1LzqiC9qylYqVVvOUqwAXZIzjgukHVGvHIh RUziVyCzUsJf/TqzwC+0BmisQHdtNCp6QqzUPFk+fxXSuQdEJJMrK0I+NTEFDLObAFPYpoCuGWOjE 9nGBr5eA==; Received: from localhost ([::1] helo=desiato.infradead.org) by desiato.infradead.org with esmtp (Exim 4.94 #2 (Red Hat Linux)) id 1lTQVs-00HQgZ-01; Mon, 05 Apr 2021 14:47:36 +0000 Received: from mail-ed1-f51.google.com ([209.85.208.51]) by desiato.infradead.org with esmtps (Exim 4.94 #2 (Red Hat Linux)) id 1lTQVo-00HQg9-Ki for opensbi@lists.infradead.org; Mon, 05 Apr 2021 14:47:34 +0000 Received: by mail-ed1-f51.google.com with SMTP id z1so12827859edb.8 for ; Mon, 05 Apr 2021 07:47:31 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:mime-version :content-transfer-encoding; bh=JMSU3Pe/XyU/j9Uy2Ho+bm1vyIyw3l4hcJDgOLZc1a4=; b=MmfrDL026L59OHjV33bTSPcTB/m2i8x6FfoBtEu6qk2iF/y874/Sg3U9uGAwbyykvW D8CTsah0NaLwLn1oiBwRFLKNG5vyqMiYaAmMhDjhOiUihCyXoFTs7nd8rMwGIrXjFpHr K/f24EVZ7xuHZbWSL22/PftexN2SvsAJB/GktfMozOlgy7+67rZF/3nwGaFCqIbmlwb3 Qf7XOzz4FhcBVqd/wGYOtvo59xi4xdf916AetcAnKEbWUKlt7RGQp/QX6jgx+9oP86Hj BpecIyOIrNOh7THedKcFUpU6Z89glxciz2p8Uf6Nrhdged2af/PpzBL7+iWaiyPbM+AI 5j2Q== X-Gm-Message-State: AOAM532vatvdm6bMCisR7yeS+dnDT8igd8X9q2Q7+zyhNHvUMdbZv5y7 qr1F50EQqmo1JZStIFVljXkweq3QyPlV0W6o X-Google-Smtp-Source: ABdhPJyNvMiz+f08+bj5AH72FnO+cH/3jZMUda6ydCM8k5YZeqX5yzaW+5CCJsKa7v7FPbTcHXrvCw== X-Received: by 2002:aa7:d687:: with SMTP id d7mr31248441edr.118.1617634050805; Mon, 05 Apr 2021 07:47:30 -0700 (PDT) Received: from t14s.fritz.box (62-178-178-158.cable.dynamic.surfer.at. [62.178.178.158]) by smtp.gmail.com with ESMTPSA id w1sm3154461edt.89.2021.04.05.07.47.30 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 05 Apr 2021 07:47:30 -0700 (PDT) From: Christoph Muellner To: opensbi@lists.infradead.org, anup.patel@wdc.com, Guo Ren , Xiang W , Jessica Clarke Cc: Christoph Muellner Subject: [PATCH v2] spinlocks: Replace test-and-set locks by ticket locks Date: Mon, 5 Apr 2021 16:47:27 +0200 Message-Id: <20210405144727.89369-1-cmuellner@linux.com> X-Mailer: git-send-email 2.30.2 MIME-Version: 1.0 X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20210405_154732_754579_F972451E X-CRM114-Status: GOOD ( 17.46 ) X-Spam-Score: 0.7 (/) X-Spam-Report: Spam detection software, running on the system "desiato.infradead.org", has NOT identified this incoming email as spam. The original message has been attached to this so you can view it or label similar future email. If you have any questions, see the administrator of that system for details. Content preview: Test-and-set locks don't provide fairness and are non-deterministic (w.r.t. the prediction of the future holder of a lock). This can be a performance problem in case of lock contention. Let's change the implementation to use ticket locks, which guarantee a fair locking order (FIFO ordering). Content analysis details: (0.7 points, 5.0 required) pts rule name description ---- ---------------------- -------------------------------------------------- -0.0 RCVD_IN_DNSWL_NONE RBL: Sender listed at https://www.dnswl.org/, no trust [209.85.208.51 listed in list.dnswl.org] -0.0 RCVD_IN_MSPIKE_H2 RBL: Average reputation (+2) [209.85.208.51 listed in wl.mailspike.net] 0.0 SPF_HELO_NONE SPF: HELO does not publish an SPF Record 0.2 HEADER_FROM_DIFFERENT_DOMAINS From and EnvelopeFrom 2nd level mail domains are different 0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider [christophm30[at]gmail.com] -0.0 SPF_PASS SPF: sender matches SPF record 0.2 FREEMAIL_ENVFROM_END_DIGIT Envelope-from freemail username ends in digit [christophm30[at]gmail.com] 0.2 FREEMAIL_FORGED_FROMDOMAIN 2nd level domains in From and EnvelopeFrom freemail headers are different X-BeenThere: opensbi@lists.infradead.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: "opensbi" Errors-To: opensbi-bounces+incoming=patchwork.ozlabs.org@lists.infradead.org Test-and-set locks don't provide fairness and are non-deterministic (w.r.t. the prediction of the future holder of a lock). This can be a performance problem in case of lock contention. Let's change the implementation to use ticket locks, which guarantee a fair locking order (FIFO ordering). Ticket locks have two counters 'owner' and 'next'. The counter 'owner' holds the ticket number of the current lock owner. The counter 'next' holds the latest free ticket number. The lock is free if both counters are equal. To acquire the lock, the 'next' counter is atomically incremented to obtain a new ticket. The counter 'owner' is then polled until it becomes equal to the new ticket. To release a lock, one atomically increments the 'owner' counter. The implementation uses a 32-bit wide struct, which consists of two 16-bit counters (owner and next). This is inspired by similar spinlock implementations on other architectures. Note, that RISC-V lacks sub-word atomics, therefore we need to circumvent this limitation with additional instructions. This implementation aims to reduce the instructions between the LR/SC pairs to minimize the chances of failing SCs. The cost of this approach is, that we spill more registers than necessary. This patch has been tested on RV64 and RV32 against self-written unit tests (to ensure the 16-bit overflow is correct) and against the Linux kernel (by exchanging the kernel's spinlock implementation with the one from this patch). Signed-off-by: Christoph Muellner --- include/sbi/riscv_locks.h | 33 ++++++++++++------ lib/sbi/riscv_locks.c | 70 +++++++++++++++++++++++++++++---------- 2 files changed, 75 insertions(+), 28 deletions(-) diff --git a/include/sbi/riscv_locks.h b/include/sbi/riscv_locks.h index faa9676..492935f 100644 --- a/include/sbi/riscv_locks.h +++ b/include/sbi/riscv_locks.h @@ -2,26 +2,37 @@ * SPDX-License-Identifier: BSD-2-Clause * * Copyright (c) 2019 Western Digital Corporation or its affiliates. - * - * Authors: - * Anup Patel + * Copyright (c) 2021 Christoph Müllner */ #ifndef __RISCV_LOCKS_H__ #define __RISCV_LOCKS_H__ +#include + +#define TICKET_SHIFT 16 + typedef struct { - volatile long lock; -} spinlock_t; +#if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ + u16 next; + u16 owner; +#else + u16 owner; + u16 next; +#endif +} __aligned(4) spinlock_t; + +#define __SPIN_LOCK_UNLOCKED \ + (spinlock_t) { 0, 0 } -#define __RISCV_SPIN_UNLOCKED 0 +#define SPIN_LOCK_INIT(x) \ + x = __SPIN_LOCK_UNLOCKED -#define SPIN_LOCK_INIT(x) (x).lock = __RISCV_SPIN_UNLOCKED +#define SPIN_LOCK_INITIALIZER \ + __SPIN_LOCK_UNLOCKED -#define SPIN_LOCK_INITIALIZER \ - { \ - .lock = __RISCV_SPIN_UNLOCKED, \ - } +#define DEFINE_SPIN_LOCK(x) \ + spinlock_t SPIN_LOCK_INIT(x) int spin_lock_check(spinlock_t *lock); diff --git a/lib/sbi/riscv_locks.c b/lib/sbi/riscv_locks.c index 4d1d9c0..04ee18a 100644 --- a/lib/sbi/riscv_locks.c +++ b/lib/sbi/riscv_locks.c @@ -2,44 +2,80 @@ * SPDX-License-Identifier: BSD-2-Clause * * Copyright (c) 2019 Western Digital Corporation or its affiliates. - * - * Authors: - * Anup Patel + * Copyright (c) 2021 Christoph Müllner */ #include #include -int spin_lock_check(spinlock_t *lock) +static inline int spin_lock_unlocked(spinlock_t lock) { - return (lock->lock == __RISCV_SPIN_UNLOCKED) ? 0 : 1; + return lock.owner == lock.next; +} + +bool spin_lock_check(spinlock_t *lock) +{ + RISCV_FENCE(r, rw); + return !spin_lock_unlocked(*lock); } int spin_trylock(spinlock_t *lock) { - int tmp = 1, busy; + unsigned long inc = 1u << TICKET_SHIFT; + unsigned long mask = 0xffffu << TICKET_SHIFT; + u32 l0, tmp1, tmp2; __asm__ __volatile__( - " amoswap.w %0, %2, %1\n" RISCV_ACQUIRE_BARRIER - : "=r"(busy), "+A"(lock->lock) - : "r"(tmp) + /* Get the current lock counters. */ + "1: lr.w.aq %0, %3\n" + " slli %2, %0, %6\n" + " and %2, %2, %5\n" + " and %1, %0, %5\n" + /* Is the lock free right now? */ + " bne %1, %2, 2f\n" + " add %0, %0, %4\n" + /* Acquire the lock. */ + " sc.w.rl %0, %0, %3\n" + " bnez %0, 1b\n" + "2:" + : "=&r"(l0), "=&r"(tmp1), "=&r"(tmp2), "+A"(*lock) + : "r"(inc), "r"(mask), "I"(TICKET_SHIFT) : "memory"); - return !busy; + return !l0; } void spin_lock(spinlock_t *lock) { - while (1) { - if (spin_lock_check(lock)) - continue; + unsigned long inc = 1u << TICKET_SHIFT; + unsigned long mask = 0xffffu; + u32 l0, tmp1, tmp2; - if (spin_trylock(lock)) - break; - } + __asm__ __volatile__( + /* Atomically increment the next ticket. */ + "0: lr.w.aq %0, %3\n" + " add %1, %0, %4\n" + " sc.w.rl %2, %1, %3\n" + " bnez %2, 0b\n" + + /* Did we get the lock? */ + " srli %1, %0, %6\n" + " and %1, %1, %5\n" + "1: and %2, %0, %5\n" + " beq %1, %2, 2f\n" + + /* No, let's spin on the lock. */ + " lw %0, %3\n" + RISCV_ACQUIRE_BARRIER + " j 1b\n" + "2:" + : "=&r"(l0), "=&r"(tmp1), "=&r"(tmp2), "+A"(*lock) + : "r"(inc), "r"(mask), "I"(TICKET_SHIFT) + : "memory"); } void spin_unlock(spinlock_t *lock) { - __smp_store_release(&lock->lock, __RISCV_SPIN_UNLOCKED); + __smp_store_release(&lock->owner, lock->owner + 1); } +