From: Yury Norov <yury.norov@gmail•com>
To: Jan Kara <jack@suse•cz>
Cc: linux-sh@vger•kernel.org, Jaroslav Kysela <perex@perex•cz>,
Hans Verkuil <hverkuil@xs4all•nl>,
"Md. Haris Iqbal" <haris.iqbal@ionos•com>,
"K. Y. Srinivasan" <kys@microsoft•com>,
Bart Van Assche <bvanassche@acm•org>,
Geert Uytterhoeven <geert@linux-m68k•org>,
Jiri Pirko <jiri@resnulli•us>,
Christian Brauner <brauner@kernel•org>,
Nicholas Piggin <npiggin@gmail•com>,
Alexey Klimov <klimov.linux@gmail•com>,
Sergey Shtylyov <s.shtylyov@omp•ru>,
Thomas Gleixner <tglx@linutronix•de>,
Karsten Keil <isdn@linux-pingi•de>,
Greg Kroah-Hartman <gregkh@linuxfoundation•org>,
linux-usb@vger•kernel.org, linux-wireless@vger•kernel.org,
linux-kernel@vger•kernel.org,
GR-QLogic-Storage-Upstream@marvell•com,
Andrew Morton <akpm@linux-foundation•org>,
Mark Rutland <mark.rutland@arm•com>,
alsa-devel@alsa-project•org,
Dave Hansen <dave.hansen@linux•intel.com>,
Eric Dumazet <edumazet@google•com>,
Gregory Greenman <gregory.greenman@intel•com>,
linux-s390@vger•kernel.org,
Valentin Schneider <vschneid@redhat .com>,
Leon Romanovsky <leon@kernel•org>, Will Deacon <will@kernel•org>,
mpi3mr-linuxdrv.pdl@broadcom•com, Hugh Dickins <hughd@google•com>,
iommu@lists•linux.dev, Martin Habets <habetsm.xilinx@gmail•com>,
linux-media@vger•kernel.org, Stanislaw Gruszka <stf_xl@wp•pl>,
linux-arm-msm@vger•kernel.org,
Wenjia Zhang <wenjia@linux•ibm.com>,
linux-m68k@lists•linux-m68k.org,
linux-arm-kernel@lists•infradead.org,
Sean Christopherson <seanjc@google•com>,
Oliver Neukum <oneukum@suse•com>,
Mirsad Todorovac <mirsad.todorovac@alu•unizg.hr>,
linux-pci@vger•kernel.org,
Rasmus Villemoes <linux@rasmusvillemoes•dk>,
linux-hyperv@vger•kernel.org,
Matthew Wilcox <willy@infradead•org>,
Jiri Slaby <jirislaby@kernel•org>, Rob Herring <robh@kernel•org>,
linux-rdma@vger•kernel.org,
Damien Le Moal <damien.lemoal@opensource•wdc.com>,
ath10k@lists•infradead.org, David Disseldorp <ddiss@suse•de>,
Paolo Abeni <pabeni@redhat•com>,
Fenghua Yu <fenghua.yu@intel•com>,
Kees Cook <keescook@chromium•org>,
"James E.J. Bot tomley" <jejb@linux•ibm.com>,
Akinobu Mita <akinobu.mita@gmail•com>,
Steven Rostedt <rostedt@goodmis•org>,
Borislav Petkov <bp@alien8•de>,
Mauro Carvalho Chehab <mchehab@kernel•org>,
Thomas Bogendoerfer <tsbogend@alpha•franken.de>,
Edward Cree <ecree.xilinx@gmail•com>,
Shuai Xue <xueshuai@linux•alibaba.com>,
netdev@vger•kernel.org, "David S. Miller" <davem@davemloft•net>,
Rich Felker <dalias@libc•org>,
kvm@vger•kernel.org, Peter Zijlstra <peterz@infradead•org>,
"H. Peter Anvin" <hpa@zytor•com>,
sparclinux@vger•kernel.org, Ping-Ke Shih <pkshih@realtek•com>,
linux-scsi@vger•kernel.org, linux-net-drivers@amd•com,
x86@kernel•org, Jason Gunthorpe <jgg@ziepe•ca>,
Ingo Molnar <mingo@redhat•com>,
linux-serial@vger•kernel.org, Jakub Kicinski <kuba@kernel•org>,
Chaitanya Kulkarni <kch@nvidia•com>,
Kalle Valo <kvalo@kernel•org>,
linux-block@vger•kernel.org, Hans de Goede <hdegoede@redhat•com>,
linux-sound@vger•kernel.org,
Andy Shevchenko <andriy.shevchenko@linux•intel.com>,
Maxim Kuvyrkov <max im.kuvyrkov@linaro•org>,
Jens Axboe <axboe@kernel•dk>, Michal Simek <monstr@monstr•eu>,
Yoshinori Sato <ysato@users•sourceforge.jp>,
Robin Murphy <robin.murphy@arm•com>,
Bjorn Andersson <andersson@kernel•org>,
linux-mips@vger•kernel.org, linux-bluetooth@vger•kernel.org,
dmaengine@vger•kernel.org, Paolo Bonzini <pbonzini@redhat•com>,
Vitaly Kuznetsov <vkuznets@redhat•com>,
linuxppc-dev@lists•ozlabs.org,
Karsten Graul <kgraul@linux•ibm.com>
Subject: Re: [PATCH v2 00/35] bitops: add atomic find_bit() operations
Date: Tue, 5 Dec 2023 21:22:59 -0800 [thread overview]
Message-ID: <ZXAFM2VZugdhM3oE@yury-ThinkPad> (raw)
In-Reply-To: <20231204185101.ddmkvsr2xxsmoh2u@quack3>
On Mon, Dec 04, 2023 at 07:51:01PM +0100, Jan Kara wrote:
> Hello Yury!
>
> On Sun 03-12-23 11:23:47, Yury Norov wrote:
> > Add helpers around test_and_{set,clear}_bit() that allow to search for
> > clear or set bits and flip them atomically.
> >
> > The target patterns may look like this:
> >
> > for (idx = 0; idx < nbits; idx++)
> > if (test_and_clear_bit(idx, bitmap))
> > do_something(idx);
> >
> > Or like this:
> >
> > do {
> > bit = find_first_bit(bitmap, nbits);
> > if (bit >= nbits)
> > return nbits;
> > } while (!test_and_clear_bit(bit, bitmap));
> > return bit;
> >
> > In both cases, the opencoded loop may be converted to a single function
> > or iterator call. Correspondingly:
> >
> > for_each_test_and_clear_bit(idx, bitmap, nbits)
> > do_something(idx);
> >
> > Or:
> > return find_and_clear_bit(bitmap, nbits);
>
> These are fine cleanups but they actually don't address the case that has
> triggered all these changes - namely the xarray use of find_next_bit() in
> xas_find_chunk().
>
> ...
> > This series is a result of discussion [1]. All find_bit() functions imply
> > exclusive access to the bitmaps. However, KCSAN reports quite a number
> > of warnings related to find_bit() API. Some of them are not pointing
> > to real bugs because in many situations people intentionally allow
> > concurrent bitmap operations.
> >
> > If so, find_bit() can be annotated such that KCSAN will ignore it:
> >
> > bit = data_race(find_first_bit(bitmap, nbits));
>
> No, this is not a correct thing to do. If concurrent bitmap changes can
> happen, find_first_bit() as it is currently implemented isn't ever a safe
> choice because it can call __ffs(0) which is dangerous as you properly note
> above. I proposed adding READ_ONCE() into find_first_bit() / find_next_bit()
> implementation to fix this issue but you disliked that. So other option we
> have is adding find_first_bit() and find_next_bit() variants that take
> volatile 'addr' and we have to use these in code like xas_find_chunk()
> which cannot be converted to your new helpers.
Here is some examples when concurrent operations with plain find_bit()
are acceptable:
- two threads running find_*_bit(): safe wrt ffs(0) and returns correct
value, because underlying bitmap is unchanged;
- find_next_bit() in parallel with set or clear_bit(), when modifying
a bit prior to the start bit to search: safe and correct;
- find_first_bit() in parallel with set_bit(): safe, but may return wrong
bit number;
- find_first_zero_bit() in parallel with clear_bit(): same as above.
In last 2 cases find_bit() may not return a correct bit number, but
it may be OK if caller requires any (not exactly first) set or clear
bit, correspondingly.
In such cases, KCSAN may be safely silenced.
> > This series addresses the other important case where people really need
> > atomic find ops. As the following patches show, the resulting code
> > looks safer and more verbose comparing to opencoded loops followed by
> > atomic bit flips.
> >
> > In [1] Mirsad reported 2% slowdown in a single-thread search test when
> > switching find_bit() function to treat bitmaps as volatile arrays. On
> > the other hand, kernel robot in the same thread reported +3.7% to the
> > performance of will-it-scale.per_thread_ops test.
>
> It was actually me who reported the regression here [2] but whatever :)
>
> [2] https://lore.kernel.org/all/20231011150252.32737-1-jack@suse.cz
My apologize.
> > Assuming that our compilers are sane and generate better code against
> > properly annotated data, the above discrepancy doesn't look weird. When
> > running on non-volatile bitmaps, plain find_bit() outperforms atomic
> > find_and_bit(), and vice-versa.
> >
> > So, all users of find_bit() API, where heavy concurrency is expected,
> > are encouraged to switch to atomic find_and_bit() as appropriate.
>
> Well, all users where any concurrency can happen should switch. Otherwise
> they are prone to the (admittedly mostly theoretical) data race issue.
>
> Honza
> --
> Jan Kara <jack@suse•com>
> SUSE Labs, CR
next prev parent reply other threads:[~2023-12-06 5:37 UTC|newest]
Thread overview: 8+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-12-03 19:23 [PATCH v2 00/35] bitops: add atomic find_bit() operations Yury Norov
2023-12-03 19:23 ` [PATCH v2 01/35] lib/find: add atomic find_bit() primitives Yury Norov
2023-12-03 19:32 ` [PATCH v2 02/35] lib/find: add test for atomic find_bit() ops Yury Norov
2023-12-03 19:32 ` [PATCH v2 18/35] powerpc: use atomic find_bit() API where appropriate Yury Norov
2023-12-04 13:07 ` [PATCH v2 00/35] bitops: add atomic find_bit() operations Andy Shevchenko
2023-12-04 18:51 ` Jan Kara
2023-12-06 5:22 ` Yury Norov [this message]
2023-12-07 9:10 ` Jan Kara
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=ZXAFM2VZugdhM3oE@yury-ThinkPad \
--to=yury.norov@gmail$(echo .)com \
--cc=GR-QLogic-Storage-Upstream@marvell$(echo .)com \
--cc=akinobu.mita@gmail$(echo .)com \
--cc=akpm@linux-foundation$(echo .)org \
--cc=alsa-devel@alsa-project$(echo .)org \
--cc=andriy.shevchenko@linux$(echo .)intel.com \
--cc=ath10k@lists$(echo .)infradead.org \
--cc=bp@alien8$(echo .)de \
--cc=brauner@kernel$(echo .)org \
--cc=bvanassche@acm$(echo .)org \
--cc=dalias@libc$(echo .)org \
--cc=damien.lemoal@opensource$(echo .)wdc.com \
--cc=dave.hansen@linux$(echo .)intel.com \
--cc=davem@davemloft$(echo .)net \
--cc=ddiss@suse$(echo .)de \
--cc=ecree.xilinx@gmail$(echo .)com \
--cc=edumazet@google$(echo .)com \
--cc=fenghua.yu@intel$(echo .)com \
--cc=geert@linux-m68k$(echo .)org \
--cc=gregkh@linuxfoundation$(echo .)org \
--cc=gregory.greenman@intel$(echo .)com \
--cc=habetsm.xilinx@gmail$(echo .)com \
--cc=haris.iqbal@ionos$(echo .)com \
--cc=hdegoede@redhat$(echo .)com \
--cc=hpa@zytor$(echo .)com \
--cc=hughd@google$(echo .)com \
--cc=hverkuil@xs4all$(echo .)nl \
--cc=iommu@lists$(echo .)linux.dev \
--cc=isdn@linux-pingi$(echo .)de \
--cc=jack@suse$(echo .)cz \
--cc=jejb@linux$(echo .)ibm.com \
--cc=jgg@ziepe$(echo .)ca \
--cc=jiri@resnulli$(echo .)us \
--cc=jirislaby@kernel$(echo .)org \
--cc=kch@nvidia$(echo .)com \
--cc=keescook@chromium$(echo .)org \
--cc=klimov.linux@gmail$(echo .)com \
--cc=kuba@kernel$(echo .)org \
--cc=kvalo@kernel$(echo .)org \
--cc=kvm@vger$(echo .)kernel.org \
--cc=kys@microsoft$(echo .)com \
--cc=leon@kernel$(echo .)org \
--cc=linux-arm-kernel@lists$(echo .)infradead.org \
--cc=linux-arm-msm@vger$(echo .)kernel.org \
--cc=linux-block@vger$(echo .)kernel.org \
--cc=linux-hyperv@vger$(echo .)kernel.org \
--cc=linux-kernel@vger$(echo .)kernel.org \
--cc=linux-m68k@lists$(echo .)linux-m68k.org \
--cc=linux-media@vger$(echo .)kernel.org \
--cc=linux-net-drivers@amd$(echo .)com \
--cc=linux-pci@vger$(echo .)kernel.org \
--cc=linux-rdma@vger$(echo .)kernel.org \
--cc=linux-s390@vger$(echo .)kernel.org \
--cc=linux-scsi@vger$(echo .)kernel.org \
--cc=linux-serial@vger$(echo .)kernel.org \
--cc=linux-sh@vger$(echo .)kernel.org \
--cc=linux-sound@vger$(echo .)kernel.org \
--cc=linux-usb@vger$(echo .)kernel.org \
--cc=linux-wireless@vger$(echo .)kernel.org \
--cc=linux@rasmusvillemoes$(echo .)dk \
--cc=mark.rutland@arm$(echo .)com \
--cc=mchehab@kernel$(echo .)org \
--cc=mingo@redhat$(echo .)com \
--cc=mirsad.todorovac@alu$(echo .)unizg.hr \
--cc=mpi3mr-linuxdrv.pdl@broadcom$(echo .)com \
--cc=netdev@vger$(echo .)kernel.org \
--cc=npiggin@gmail$(echo .)com \
--cc=oneukum@suse$(echo .)com \
--cc=pabeni@redhat$(echo .)com \
--cc=perex@perex$(echo .)cz \
--cc=peterz@infradead$(echo .)org \
--cc=pkshih@realtek$(echo .)com \
--cc=robh@kernel$(echo .)org \
--cc=rostedt@goodmis$(echo .)org \
--cc=s.shtylyov@omp$(echo .)ru \
--cc=seanjc@google$(echo .)com \
--cc=sparclinux@vger$(echo .)kernel.org \
--cc=stf_xl@wp$(echo .)pl \
--cc=tglx@linutronix$(echo .)de \
--cc=tsbogend@alpha$(echo .)franken.de \
--cc=vschneid@redhat$(echo .)com \
--cc=wenjia@linux$(echo .)ibm.com \
--cc=will@kernel$(echo .)org \
--cc=willy@infradead$(echo .)org \
--cc=x86@kernel$(echo .)org \
--cc=xueshuai@linux$(echo .)alibaba.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox