From: Yury Norov <yury.norov@gmail.com>
To: linux-kernel@vger.kernel.org,
"David S. Miller" <davem@davemloft.net>,
"H. Peter Anvin" <hpa@zytor.com>,
"James E.J. Bottomley" <jejb@linux.ibm.com>,
"K. Y. Srinivasan" <kys@microsoft.com>,
"Md. Haris Iqbal" <haris.iqbal@ionos.com>,
Akinobu Mita <akinobu.mita@gmail.com>,
Andrew Morton <akpm@linux-foundation.org>,
Bjorn Andersson <andersson@kernel.org>,
Borislav Petkov <bp@alien8.de>,
Chaitanya Kulkarni <kch@nvidia.com>,
Christian Brauner <brauner@kernel.org>,
Damien Le Moal <damien.lemoal@opensource.wdc.com>,
Dave Hansen <dave.hansen@linux.intel.com>,
David Disseldorp <ddiss@suse.de>,
Edward Cree <ecree.xilinx@gmail.com>,
Eric Dumazet <edumazet@google.com>,
Fenghua Yu <fenghua.yu@intel.com>,
Geert Uytterhoeven <geert@linux-m68k.org>,
Greg Kroah-Hartman <gregkh@linuxfoundation.org>,
Gregory Greenman <gregory.greenman@intel.com>,
Hans Verkuil <hverkuil@xs4all.nl>,
Hans de Goede <hdegoede@redhat.com>,
Hugh Dickins <hughd@google.com>, Ingo Molnar <mingo@redhat.com>,
Jakub Kicinski <kuba@kernel.org>,
Jaroslav Kysela <perex@perex.cz>, Jason Gunthorpe <jgg@ziepe.ca>,
Jens Axboe <axboe@kernel.dk>, Jiri Pirko <jiri@resnulli.us>,
Jiri Slaby <jirislaby@kernel.org>, Kalle Valo <kvalo@kernel.org>,
Karsten Graul <kgraul@linux.ibm.com>,
Karsten Keil <isdn@linux-pingi.de>,
Kees Cook <keescook@chromium.org>,
Leon Romanovsky <leon@kernel.org>,
Mark Rutland <mark.rutland@arm.com>,
Martin Habets <habetsm.xilinx@gmail.com>,
Mauro Carvalho Chehab <mchehab@kernel.org>,
Michael Ellerman <mpe@ellerman.id.au>,
Michal Simek <monstr@monstr.eu>,
Nicholas Piggin <npiggin@gmail.com>,
Oliver Neukum <oneukum@suse.com>, Paolo Abeni <pabeni@redhat.com>,
Paolo Bonzini <pbonzini@redhat.com>,
Peter Zijlstra <peterz@infradead.org>,
Ping-Ke Shih <pkshih@realtek.com>, Rich Felker <dalias@libc.org>,
Rob Herring <robh@kernel.org>,
Robin Murphy <robin.murphy@arm.com>,
Sean Christopherson <seanjc@google.com>,
Shuai Xue <xueshuai@linux.alibaba.com>,
Stanislaw Gruszka <stf_xl@wp.pl>,
Steven Rostedt <rostedt@goodmis.org>,
Thomas Bogendoerfer <tsbogend@alpha.franken.de>,
Thomas Gleixner <tglx@linutronix.de>,
Valentin Schneider <vschneid@redhat.com>,
Vitaly Kuznetsov <vkuznets@redhat.com>,
Wenjia Zhang <wenjia@linux.ibm.com>,
Will Deacon <will@kernel.org>,
Yoshinori Sato <ysato@users.sourceforge.jp>,
GR-QLogic-Storage-Upstream@marvell.com,
alsa-devel@alsa-project.org, ath10k@lists.infradead.org,
dmaengine@vger.kernel.org, iommu@lists.linux.dev,
kvm@vger.kernel.org, linux-arm-kernel@lists.infradead.org,
linux-arm-msm@vger.kernel.org, linux-block@vger.kernel.org,
linux-bluetooth@vger.kernel.org, linux-hyperv@vger.kernel.org,
linux-m68k@lists.linux-m68k.org, linux-media@vger.kernel.org,
linux-mips@vger.kernel.org, linux-net-drivers@amd.com,
linux-pci@vger.kernel.org, linux-rdma@vger.kernel.org,
linux-s390@vger.kernel.org, linux-scsi@vger.kernel.org,
linux-serial@vger.kernel.org, linux-sh@vger.kernel.org,
linux-sound@vger.kernel.org, linux-usb@vger.kernel.org,
linux-wireless@vger.kernel.org, linuxppc-dev@lists.ozlabs.org,
mpi3mr-linuxdrv.pdl@broadcom.com, netdev@vger.kernel.org,
sparclinux@vger.kernel.org, x86@kernel.org
Cc: Jan Kara <jack@suse.cz>,
Mirsad Todorovac <mirsad.todorovac@alu.unizg.hr>,
Matthew Wilcox <willy@infradead.org>,
Rasmus Villemoes <linux@rasmusvillemoes.dk>,
Andy Shevchenko <andriy.shevchenko@linux.intel.com>,
Maxim Kuvyrkov <maxim.kuvyrkov@linaro.org>,
Alexey Klimov <klimov.linux@gmail.com>,
Bart Van Assche <bvanassche@acm.org>,
Sergey Shtylyov <s.shtylyov@omp.ru>
Subject: Re: [PATCH v3 00/35] bitops: add atomic find_bit() operations
Date: Sat, 16 Dec 2023 13:48:18 -0800 [thread overview]
Message-ID: <ZX4bIisLzpW8c4WM@yury-ThinkPad> (raw)
In-Reply-To: <20231212022749.625238-1-yury.norov@gmail.com>
On Mon, Dec 11, 2023 at 06:27:14PM -0800, 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);
>
> Obviously, the less routine code people have to write themself, the
> less probability to make a mistake.
>
> Those are not only handy helpers but also resolve a non-trivial
> issue of using non-atomic find_bit() together with atomic
> test_and_{set,clear)_bit().
>
> The trick is that find_bit() implies that the bitmap is a regular
> non-volatile piece of memory, and compiler is allowed to use such
> optimization techniques like re-fetching memory instead of caching it.
>
> For example, find_first_bit() is implemented like this:
>
> for (idx = 0; idx * BITS_PER_LONG < sz; idx++) {
> val = addr[idx];
> if (val) {
> sz = min(idx * BITS_PER_LONG + __ffs(val), sz);
> break;
> }
> }
>
> On register-memory architectures, like x86, compiler may decide to
> access memory twice - first time to compare against 0, and second time
> to fetch its value to pass it to __ffs().
>
> When running find_first_bit() on volatile memory, the memory may get
> changed in-between, and for instance, it may lead to passing 0 to
> __ffs(), which is undefined. This is a potentially dangerous call.
>
> find_and_clear_bit() as a wrapper around test_and_clear_bit()
> naturally treats underlying bitmap as a volatile memory and prevents
> compiler from such optimizations.
>
> Now that KCSAN is catching exactly this type of situations and warns on
> undercover memory modifications. We can use it to reveal improper usage
> of find_bit(), and convert it to atomic find_and_*_bit() as appropriate.
>
> In some cases concurrent operations with plain find_bit() are acceptable.
> For example:
>
> - 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 the first) set or clear
> bit, correspondingly.
>
> In such cases, KCSAN may be safely silenced with data_race(). But in most
> cases where KCSAN detects concurrency people should carefully review their
> code and likely protect critical sections or switch to atomic
> find_and_bit(), as appropriate.
>
> The 1st patch of the series adds the following atomic primitives:
>
> find_and_set_bit(addr, nbits);
> find_and_set_next_bit(addr, nbits, start);
> ...
>
> Here find_and_{set,clear} part refers to the corresponding
> test_and_{set,clear}_bit function. Suffixes like _wrap or _lock
> derive their semantics from corresponding find() or test() functions.
>
> For brevity, the naming omits the fact that we search for zero bit in
> find_and_set, and correspondingly search for set bit in find_and_clear
> functions.
>
> The patch also adds iterators with atomic semantics, like
> for_each_test_and_set_bit(). Here, the naming rule is to simply prefix
> corresponding atomic operation with 'for_each'.
>
> In [1] Jan 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.
>
> 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.
>
> The 1st patch of this series adds atomic find_and_bit() API, 2nd adds
> a basic test for new API, and all the following patches spread it over
> the kernel.
>
> They can be applied separately from each other on per-subsystems basis,
> or I can pull them in bitmap tree, as appropriate.
>
> [1] https://lore.kernel.org/lkml/634f5fdf-e236-42cf-be8d-48a581c21660@alu.unizg.hr/T/#m3e7341eb3571753f3acf8fe166f3fb5b2c12e615
Thank you all for reviews and comments. Now moving the series to
bitmap-for-next for testing.
Thanks,
Yury
prev parent reply other threads:[~2023-12-16 21:48 UTC|newest]
Thread overview: 6+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-12-12 2:27 [PATCH v3 00/35] bitops: add atomic find_bit() operations Yury Norov
2023-12-12 2:27 ` [PATCH v3 01/35] lib/find: add atomic find_bit() primitives Yury Norov
2023-12-12 2:27 ` [PATCH v3 02/35] lib/find: add test for atomic find_bit() ops Yury Norov
2023-12-12 2:27 ` [PATCH v3 11/35] ath10k: optimize ath10k_snoc_napi_poll() Yury Norov
2023-12-12 2:27 ` [PATCH v3 12/35] wifi: rtw88: optimize the driver by using atomic iterator Yury Norov
2023-12-16 21:48 ` Yury Norov [this message]
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=ZX4bIisLzpW8c4WM@yury-ThinkPad \
--to=yury.norov@gmail.com \
--cc=GR-QLogic-Storage-Upstream@marvell.com \
--cc=akinobu.mita@gmail.com \
--cc=akpm@linux-foundation.org \
--cc=alsa-devel@alsa-project.org \
--cc=andersson@kernel.org \
--cc=andriy.shevchenko@linux.intel.com \
--cc=ath10k@lists.infradead.org \
--cc=axboe@kernel.dk \
--cc=bp@alien8.de \
--cc=brauner@kernel.org \
--cc=bvanassche@acm.org \
--cc=dalias@libc.org \
--cc=damien.lemoal@opensource.wdc.com \
--cc=dave.hansen@linux.intel.com \
--cc=davem@davemloft.net \
--cc=ddiss@suse.de \
--cc=dmaengine@vger.kernel.org \
--cc=ecree.xilinx@gmail.com \
--cc=edumazet@google.com \
--cc=fenghua.yu@intel.com \
--cc=geert@linux-m68k.org \
--cc=gregkh@linuxfoundation.org \
--cc=gregory.greenman@intel.com \
--cc=habetsm.xilinx@gmail.com \
--cc=haris.iqbal@ionos.com \
--cc=hdegoede@redhat.com \
--cc=hpa@zytor.com \
--cc=hughd@google.com \
--cc=hverkuil@xs4all.nl \
--cc=iommu@lists.linux.dev \
--cc=isdn@linux-pingi.de \
--cc=jack@suse.cz \
--cc=jejb@linux.ibm.com \
--cc=jgg@ziepe.ca \
--cc=jiri@resnulli.us \
--cc=jirislaby@kernel.org \
--cc=kch@nvidia.com \
--cc=keescook@chromium.org \
--cc=kgraul@linux.ibm.com \
--cc=klimov.linux@gmail.com \
--cc=kuba@kernel.org \
--cc=kvalo@kernel.org \
--cc=kvm@vger.kernel.org \
--cc=kys@microsoft.com \
--cc=leon@kernel.org \
--cc=linux-arm-kernel@lists.infradead.org \
--cc=linux-arm-msm@vger.kernel.org \
--cc=linux-block@vger.kernel.org \
--cc=linux-bluetooth@vger.kernel.org \
--cc=linux-hyperv@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-m68k@lists.linux-m68k.org \
--cc=linux-media@vger.kernel.org \
--cc=linux-mips@vger.kernel.org \
--cc=linux-net-drivers@amd.com \
--cc=linux-pci@vger.kernel.org \
--cc=linux-rdma@vger.kernel.org \
--cc=linux-s390@vger.kernel.org \
--cc=linux-scsi@vger.kernel.org \
--cc=linux-serial@vger.kernel.org \
--cc=linux-sh@vger.kernel.org \
--cc=linux-sound@vger.kernel.org \
--cc=linux-usb@vger.kernel.org \
--cc=linux-wireless@vger.kernel.org \
--cc=linux@rasmusvillemoes.dk \
--cc=linuxppc-dev@lists.ozlabs.org \
--cc=mark.rutland@arm.com \
--cc=maxim.kuvyrkov@linaro.org \
--cc=mchehab@kernel.org \
--cc=mingo@redhat.com \
--cc=mirsad.todorovac@alu.unizg.hr \
--cc=monstr@monstr.eu \
--cc=mpe@ellerman.id.au \
--cc=mpi3mr-linuxdrv.pdl@broadcom.com \
--cc=netdev@vger.kernel.org \
--cc=npiggin@gmail.com \
--cc=oneukum@suse.com \
--cc=pabeni@redhat.com \
--cc=pbonzini@redhat.com \
--cc=perex@perex.cz \
--cc=peterz@infradead.org \
--cc=pkshih@realtek.com \
--cc=robh@kernel.org \
--cc=robin.murphy@arm.com \
--cc=rostedt@goodmis.org \
--cc=s.shtylyov@omp.ru \
--cc=seanjc@google.com \
--cc=sparclinux@vger.kernel.org \
--cc=stf_xl@wp.pl \
--cc=tglx@linutronix.de \
--cc=tsbogend@alpha.franken.de \
--cc=vkuznets@redhat.com \
--cc=vschneid@redhat.com \
--cc=wenjia@linux.ibm.com \
--cc=will@kernel.org \
--cc=willy@infradead.org \
--cc=x86@kernel.org \
--cc=xueshuai@linux.alibaba.com \
--cc=ysato@users.sourceforge.jp \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
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;
as well as URLs for NNTP newsgroup(s).