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=-2.7 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS, URIBL_BLOCKED autolearn=no 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 6F4E6C433B4 for ; Tue, 13 Apr 2021 10:25:18 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 5137061029 for ; Tue, 13 Apr 2021 10:25:18 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S244130AbhDMKZd (ORCPT ); Tue, 13 Apr 2021 06:25:33 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33446 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S243397AbhDMKZc (ORCPT ); Tue, 13 Apr 2021 06:25:32 -0400 Received: from mail-vs1-xe2e.google.com (mail-vs1-xe2e.google.com [IPv6:2607:f8b0:4864:20::e2e]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id C4077C061574 for ; Tue, 13 Apr 2021 03:25:12 -0700 (PDT) Received: by mail-vs1-xe2e.google.com with SMTP id 2so8254332vsh.4 for ; Tue, 13 Apr 2021 03:25:12 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc:content-transfer-encoding; bh=0lVf0nl5+qZIZ/jwfGQvy92YMy+Bwdb1xbccBw3TFn4=; b=OQucTICyR/tvEMXOZVjDg+CuM65o1aglrPM1pxZwsPXp1hq20Ab1ovqvtWIGG24X+0 fa8WvN4zl0fWpYqVcXRaQSaRvwZP28mJyVG6tjv6u/oqP5CDONyT4OoUbgqf7iVrzPss ZXxDcWSEUkdupAb3uez+3j+IAeZXETzsvlf+0nUM4oQk0RG+7GpkEYm2AiTNMWqQHwe7 oV079OC27O+PVqHKUUuni8LlJiYch4KoCaksdtWX8vWfpHUeoHDdCWyJp3223DAbe1Y+ dhuO3xPCWjkggaeGDmyiXboig1YavxvI5GAsv5rrBt5qJR/R6TvavU6R5RFR7hDYmqD+ NAGw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=0lVf0nl5+qZIZ/jwfGQvy92YMy+Bwdb1xbccBw3TFn4=; b=cvmc4fHwBxKySZP263pThNIu8yxUuKVHW6sO1kof6oR+gCbj2Opqb3SVphFTY6jbmE E+PEBy52P+Cqk5JzDTPR6RVlkFoFeGEoDKa0Pwz317KabejpxTYWHPRuUqLdQK7eKxrn b/Sjwisle547VaEfBgJ+49v2xfHo+hLW+ODWSZbqc5ojUnH88Ba3LCN4cndjeoOXh0nR 5i8NQanU4FvbHDLIRcpPNT170l9a9abgGXP06rIL9qRde3U20QJu5uHfJB+yyHV+v4Ba S7Dj1myibhS9wou2Hm1y9YrfCf3JZN15iQG/H43C+AEemwwmz6pddrZe1oqL8KVZu2Kb ECZw== X-Gm-Message-State: AOAM530CjHEl2vq/3YkytO5I5b/JhIZVt5Qv4lC7mcoy5grNxW2K/TGS uEphGwPMH7BipzjINCUAm+iwfFOqttEeWd9Ha78= X-Google-Smtp-Source: ABdhPJxnF09LZHIgut/aICnbMhcpqGlRpleSNRviOgql/+Uc9Wy5Lxs0pjY/bNLdVZZrBYZ78aDIZG9tURDVo9wKp1s= X-Received: by 2002:a67:e40b:: with SMTP id d11mr6143063vsf.23.1618309511657; Tue, 13 Apr 2021 03:25:11 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: =?UTF-8?Q?Christoph_M=C3=BCllner?= Date: Tue, 13 Apr 2021 12:25:00 +0200 Message-ID: Subject: Re: [PATCH] riscv: locks: introduce ticket-based spinlock implementation To: Peter Zijlstra Cc: Palmer Dabbelt , Anup Patel , Guo Ren , linux-riscv , Linux Kernel Mailing List , Guo Ren , catalin.marinas@arm.com, will.deacon@arm.com, Arnd Bergmann Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Tue, Apr 13, 2021 at 11:37 AM Peter Zijlstra wrot= e: > > On Tue, Apr 13, 2021 at 11:22:40AM +0200, Christoph M=C3=BCllner wrote: > > > > For ticket locks you really only needs atomic_fetch_add() and > > > smp_store_release() and an architectural guarantees that the > > > atomic_fetch_add() has fwd progress under contention and that a sub-w= ord > > > store (through smp_store_release()) will fail the SC. > > > > > > Then you can do something like: > > > > > > void lock(atomic_t *lock) > > > { > > > u32 val =3D atomic_fetch_add(1<<16, lock); /* SC, gives us RC= sc */ > > > u16 ticket =3D val >> 16; > > > > > > for (;;) { > > > if (ticket =3D=3D (u16)val) > > > break; > > > cpu_relax(); > > > val =3D atomic_read_acquire(lock); > > > } > > > } > > > > > > void unlock(atomic_t *lock) > > > { > > > u16 *ptr =3D (u16 *)lock + (!!__BIG_ENDIAN__); > > > u32 val =3D atomic_read(lock); > > > > > > smp_store_release(ptr, (u16)val + 1); > > > } > > > > > > That's _almost_ as simple as a test-and-set :-) It isn't quite optima= l > > > on x86 for not being allowed to use a memop on unlock, since its bein= g > > > forced into a load-store because of all the volatile, but whatever. > > > > What about trylock()? > > I.e. one could implement trylock() without a loop, by letting > > trylock() fail if the SC fails. > > That looks safe on first view, but nobody does this right now. > > Generic code has to use cmpxchg(), and then you get something like this: > > bool trylock(atomic_t *lock) > { > u32 old =3D atomic_read(lock); > > if ((old >> 16) !=3D (old & 0xffff)) > return false; > > return atomic_try_cmpxchg(lock, &old, old + (1<<16)); /* SC, for = RCsc */ > } This approach requires two loads (atomic_read() and cmpxchg()), which is not required. Detecting this pattern and optimizing it in a compiler is quite unlikely. A bit less generic solution would be to wrap the LL/SC (would be mandatory in this case) instructions and do something like this: uint32_t __smp_load_acquire_reserved(void*); int __smp_store_release_conditional(void*, uint32_t); typedef union { uint32_t v32; struct { uint16_t owner; uint16_t next; }; } arch_spinlock_t; int trylock(arch_spinlock_t *lock) { arch_spinlock_t l; int success; do { l.v32 =3D __smp_load_acquire_reserved(lock); if (l.owner !=3D l.next) return 0; l.next++; success =3D __smp_store_release_conditional(lock, l.v32); } while (!success); return success; } But here we can't tell the compiler to optimize the code between LL and SC.= .. > > That will try and do the full LL/SC loop, because it wants to complete > the cmpxchg, but in generic code we have no other option. > > (Is this what C11's weak cmpxchg is for?)