From patchwork Tue Apr 6 01:53:54 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: 1462573 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=pY98JYlT; 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 4FDrDX6ZP1z9sRR for ; Tue, 6 Apr 2021 11:54:20 +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:References:In-Reply-To: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:List-Owner; bh=y44V7p4OkLxffwbLyle0Hb5Vc9PqWMElMy6S/QEcMxQ=; b=pY98JYlTCJAS8bfoiiJ66Y681 qlkjbdyQKfpixs4mAl/0l+K2Nxg8PjBCpxJ0ViJUVDA5hr9qtNPiJZFN+ZkhUKFCYZLgn8LL2iqGf DSrrZmrkCQoHlR6MTbqL1WMvntkobbYQ1RtSUDx61GJRCxH3znFHxCnSE5rLGcO3vbzBrrJwJA2Pc t/Nf+PMW//Tc2shLx6MOFR1KowUDDt/L7L+0nWHxbzmypMzvb/n8cF/WwH+SicGL7EgLxIXmqoxi0 cwnE6fI+rHQUJoIPYOulckE3XpxX5T3a5hNQdC/iBfOojSTGuL4S9FPolbcJoTEtxsdaj+3jqZkK7 4WuAKKreA==; Received: from localhost ([::1] helo=desiato.infradead.org) by desiato.infradead.org with esmtp (Exim 4.94 #2 (Red Hat Linux)) id 1lTav1-001Crf-UV; Tue, 06 Apr 2021 01:54:16 +0000 Received: from mail-ej1-f47.google.com ([209.85.218.47]) by desiato.infradead.org with esmtps (Exim 4.94 #2 (Red Hat Linux)) id 1lTaum-001Cmb-M4 for opensbi@lists.infradead.org; Tue, 06 Apr 2021 01:54:04 +0000 Received: by mail-ej1-f47.google.com with SMTP id a7so19394561ejs.3 for ; Mon, 05 Apr 2021 18:54:00 -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:in-reply-to :references:mime-version:content-transfer-encoding; bh=lwKvaFsqcKbJ7z8sLW0eAVB74J+moQWKh4oty+sS7ro=; b=S7MT/ZzSB0h3Y8ucXgpnaFbHf3KKULfT5IJk1ePwLoQZ/AHOVrTg6wS6OI/VJgCJw2 A0I+6QpYc/vbVnNXGi5MqhJMGxHwnoPpBeTv1tv5OjSW1qG1yjowj8r12/c3/moR+TSK /2MSp4sozajC0JErpEkGfQ6WNkVh7rY6l7bsmMPLDfzpC5GQly10J7JrZF90l2qAimtq bwmUlKrKSZpbAx8Iz+2nFfZIN9oN5QzBJQAOFq++tFvhXSjSSZfe5rwNwv8SABLYkGX8 j7HqhSYaFraJwGADI1aMvQioW5v/xzZFviysJky66TXrnlbUWXDpjq73z88nimYXRSft NDDQ== X-Gm-Message-State: AOAM530JzvdqNGqcPB3gI6QqeVErR5Jw8bLM3yIuqfCAOZzQjM+8dRqE cNm7198MAy+rYKtQrVmyECsL67pQ7BE4dc1J X-Google-Smtp-Source: ABdhPJxqhw5NpZoYf4Y54oMy0J2jnZpgYp0SnSBuQrvEoru01y2JoRN2x43A1fLOnjtBZM0iO+CTTA== X-Received: by 2002:a17:906:8470:: with SMTP id hx16mr18752929ejc.153.1617674039941; Mon, 05 Apr 2021 18:53:59 -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 q18sm7846996edw.56.2021.04.05.18.53.59 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 05 Apr 2021 18:53:59 -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 v3 3/3] spinlocks: Replace test-and-set locks by ticket locks Date: Tue, 6 Apr 2021 03:53:54 +0200 Message-Id: <20210406015354.332780-4-cmuellner@linux.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20210406015354.332780-1-cmuellner@linux.com> References: <20210406015354.332780-1-cmuellner@linux.com> MIME-Version: 1.0 X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20210406_025401_548070_59FD829B X-CRM114-Status: GOOD ( 14.15 ) 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: Replace the test-and-set spinlock implementation with ticket locks in order to get fairness (in form of FIFO order). 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. This allows that the [...] 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.218.47 listed in list.dnswl.org] -0.0 RCVD_IN_MSPIKE_H2 RBL: Average reputation (+2) [209.85.218.47 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 Replace the test-and-set spinlock implementation with ticket locks in order to get fairness (in form of FIFO order). 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. This allows that the code works for both, RV32 and RV64. Signed-off-by: Christoph Muellner Reviewed-by: Anup Patel Reviewed-by: Xiang W --- include/sbi/riscv_locks.h | 33 ++++++++++++------- lib/sbi/riscv_locks.c | 67 +++++++++++++++++++++++++++++---------- 2 files changed, 72 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..7e607b0 100644 --- a/lib/sbi/riscv_locks.c +++ b/lib/sbi/riscv_locks.c @@ -2,44 +2,77 @@ * 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. */ + " amoadd.w.aqrl %0, %4, %3\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" + + /* If not, then 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); } +