Message-ID: <ZW3O-P_98eubKxMU@smile.fi.intel.com>
Date:   Mon, 4 Dec 2023 15:07:04 +0200
From:   Andy Shevchenko <andriy.shevchenko@...ux.intel.com>
To:     Yury Norov <yury.norov@...il.com>
Cc:     linux-kernel@...r.kernel.org,
        "David S. Miller" <davem@...emloft.net>,
        "H. Peter Anvin" <hpa@...or.com>,
        "James E.J. Bottomley" <jejb@...ux.ibm.com>,
        "K. Y. Srinivasan" <kys@...rosoft.com>,
        "Md. Haris Iqbal" <haris.iqbal@...os.com>,
        Akinobu Mita <akinobu.mita@...il.com>,
        Andrew Morton <akpm@...ux-foundation.org>,
        Bjorn Andersson <andersson@...nel.org>,
        Borislav Petkov <bp@...en8.de>,
        Chaitanya Kulkarni <kch@...dia.com>,
        Christian Brauner <brauner@...nel.org>,
        Damien Le Moal <damien.lemoal@...nsource.wdc.com>,
        Dave Hansen <dave.hansen@...ux.intel.com>,
        David Disseldorp <ddiss@...e.de>,
        Edward Cree <ecree.xilinx@...il.com>,
        Eric Dumazet <edumazet@...gle.com>,
        Fenghua Yu <fenghua.yu@...el.com>,
        Geert Uytterhoeven <geert@...ux-m68k.org>,
        Greg Kroah-Hartman <gregkh@...uxfoundation.org>,
        Gregory Greenman <gregory.greenman@...el.com>,
        Hans Verkuil <hverkuil@...all.nl>,
        Hans de Goede <hdegoede@...hat.com>,
        Hugh Dickins <hughd@...gle.com>,
        Ingo Molnar <mingo@...hat.com>,
        Jakub Kicinski <kuba@...nel.org>,
        Jaroslav Kysela <perex@...ex.cz>,
        Jason Gunthorpe <jgg@...pe.ca>, Jens Axboe <axboe@...nel.dk>,
        Jiri Pirko <jiri@...nulli.us>,
        Jiri Slaby <jirislaby@...nel.org>,
        Kalle Valo <kvalo@...nel.org>,
        Karsten Graul <kgraul@...ux.ibm.com>,
        Karsten Keil <isdn@...ux-pingi.de>,
        Kees Cook <keescook@...omium.org>,
        Leon Romanovsky <leon@...nel.org>,
        Mark Rutland <mark.rutland@....com>,
        Martin Habets <habetsm.xilinx@...il.com>,
        Mauro Carvalho Chehab <mchehab@...nel.org>,
        Michael Ellerman <mpe@...erman.id.au>,
        Michal Simek <monstr@...str.eu>,
        Nicholas Piggin <npiggin@...il.com>,
        Oliver Neukum <oneukum@...e.com>,
        Paolo Abeni <pabeni@...hat.com>,
        Paolo Bonzini <pbonzini@...hat.com>,
        Peter Zijlstra <peterz@...radead.org>,
        Ping-Ke Shih <pkshih@...ltek.com>,
        Rich Felker <dalias@...c.org>, Rob Herring <robh@...nel.org>,
        Robin Murphy <robin.murphy@....com>,
        Sean Christopherson <seanjc@...gle.com>,
        Shuai Xue <xueshuai@...ux.alibaba.com>,
        Stanislaw Gruszka <stf_xl@...pl>,
        Steven Rostedt <rostedt@...dmis.org>,
        Thomas Bogendoerfer <tsbogend@...ha.franken.de>,
        Thomas Gleixner <tglx@...utronix.de>,
        Valentin Schneider <vschneid@...hat.com>,
        Vitaly Kuznetsov <vkuznets@...hat.com>,
        Wenjia Zhang <wenjia@...ux.ibm.com>,
        Will Deacon <will@...nel.org>,
        Yoshinori Sato <ysato@...rs.sourceforge.jp>,
        GR-QLogic-Storage-Upstream@...vell.com,
        alsa-devel@...a-project.org, ath10k@...ts.infradead.org,
        dmaengine@...r.kernel.org, iommu@...ts.linux.dev,
        kvm@...r.kernel.org, linux-arm-kernel@...ts.infradead.org,
        linux-arm-msm@...r.kernel.org, linux-block@...r.kernel.org,
        linux-bluetooth@...r.kernel.org, linux-hyperv@...r.kernel.org,
        linux-m68k@...ts.linux-m68k.org, linux-media@...r.kernel.org,
        linux-mips@...r.kernel.org, linux-net-drivers@....com,
        linux-pci@...r.kernel.org, linux-rdma@...r.kernel.org,
        linux-s390@...r.kernel.org, linux-scsi@...r.kernel.org,
        linux-serial@...r.kernel.org, linux-sh@...r.kernel.org,
        linux-sound@...r.kernel.org, linux-usb@...r.kernel.org,
        linux-wireless@...r.kernel.org, linuxppc-dev@...ts.ozlabs.org,
        mpi3mr-linuxdrv.pdl@...adcom.com, netdev@...r.kernel.org,
        sparclinux@...r.kernel.org, x86@...nel.org,
        Jan Kara <jack@...e.cz>,
        Mirsad Todorovac <mirsad.todorovac@....unizg.hr>,
        Matthew Wilcox <willy@...radead.org>,
        Rasmus Villemoes <linux@...musvillemoes.dk>,
        Maxim Kuvyrkov <maxim.kuvyrkov@...aro.org>,
        Alexey Klimov <klimov.linux@...il.com>,
        Bart Van Assche <bvanassche@....org>,
        Sergey Shtylyov <s.shtylyov@....ru>
Subject: Re: [PATCH v2 00/35] bitops: add atomic find_bit() operations

On Sun, Dec 03, 2023 at 11:23:47AM -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.
> 
> 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'.
> 
> 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));
> 
> 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.
> 
> 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.

...

In some cases the better improvements can be achieved by switching
the (very) old code to utilise IDA framework.

-- 
With Best Regards,
Andy Shevchenko

Powered by blists - more mailing lists