From mboxrd@z Thu Jan 1 00:00:00 1970 Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=intel.com header.i=@intel.com header.b="glYuk8RX" Received: from mgamail.intel.com (mgamail.intel.com [192.198.163.7]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 8A384A7; Mon, 4 Dec 2023 05:07:44 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=intel.com; i=@intel.com; q=dns/txt; s=Intel; t=1701695265; x=1733231265; h=date:from:to:cc:subject:message-id:references: mime-version:in-reply-to; bh=UpKiTiLV03HLrMK8OyY7m+bGEMtR9L95NOiQzYClrhU=; b=glYuk8RXPb0XnOqDmmVCjrF7jpJ9zshznGYsBwZnW6Lp6N9UB3wcJAfW RcyKoR3vcNfNkawEw6PplM/CnnVsbAPCOO3ye8XRT4rN3XSwOLz9sb1hU 7C+6cD/D1sePV5R/GegF2Oygln5+FP4LpN8LETCbSj5emh7LU/EmbTFtR dAUdaO++oeIOhU9+SvMmDwUTY7pfPCIkRyf2unXDWTJ2pYQAWOK2AA2Mv 93RpGe0s7/IwqU+loGPDWvrNJMvLWXNCZjdCDCe8Q32LqxnYlkjlPcodB VrGEtbgUe6WUs5DZVI6UwsLf1e6rvg4sOZtvRq/3Q28morjoDvQUepAYu w==; X-IronPort-AV: E=McAfee;i="6600,9927,10913"; a="15275177" X-IronPort-AV: E=Sophos;i="6.04,249,1695711600"; d="scan'208";a="15275177" Received: from orsmga007.jf.intel.com ([10.7.209.58]) by fmvoesa101.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 04 Dec 2023 05:07:37 -0800 X-ExtLoop1: 1 X-IronPort-AV: E=McAfee;i="6600,9927,10913"; a="763935696" X-IronPort-AV: E=Sophos;i="6.04,249,1695711600"; d="scan'208";a="763935696" Received: from smile.fi.intel.com ([10.237.72.54]) by orsmga007.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 04 Dec 2023 05:07:13 -0800 Received: from andy by smile.fi.intel.com with local (Exim 4.97) (envelope-from ) id 1rA8fA-00000001kqj-2oCl; Mon, 04 Dec 2023 15:07:04 +0200 Date: Mon, 4 Dec 2023 15:07:04 +0200 From: Andy Shevchenko To: Yury Norov Cc: linux-kernel@vger.kernel.org, "David S. Miller" , "H. Peter Anvin" , "James E.J. Bottomley" , "K. Y. Srinivasan" , "Md. Haris Iqbal" , Akinobu Mita , Andrew Morton , Bjorn Andersson , Borislav Petkov , Chaitanya Kulkarni , Christian Brauner , Damien Le Moal , Dave Hansen , David Disseldorp , Edward Cree , Eric Dumazet , Fenghua Yu , Geert Uytterhoeven , Greg Kroah-Hartman , Gregory Greenman , Hans Verkuil , Hans de Goede , Hugh Dickins , Ingo Molnar , Jakub Kicinski , Jaroslav Kysela , Jason Gunthorpe , Jens Axboe , Jiri Pirko , Jiri Slaby , Kalle Valo , Karsten Graul , Karsten Keil , Kees Cook , Leon Romanovsky , Mark Rutland , Martin Habets , Mauro Carvalho Chehab , Michael Ellerman , Michal Simek , Nicholas Piggin , Oliver Neukum , Paolo Abeni , Paolo Bonzini , Peter Zijlstra , Ping-Ke Shih , Rich Felker , Rob Herring , Robin Murphy , Sean Christopherson , Shuai Xue , Stanislaw Gruszka , Steven Rostedt , Thomas Bogendoerfer , Thomas Gleixner , Valentin Schneider , Vitaly Kuznetsov , Wenjia Zhang , Will Deacon , Yoshinori Sato , 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, Jan Kara , Mirsad Todorovac , Matthew Wilcox , Rasmus Villemoes , Maxim Kuvyrkov , Alexey Klimov , Bart Van Assche , Sergey Shtylyov Subject: Re: [PATCH v2 00/35] bitops: add atomic find_bit() operations Message-ID: References: <20231203192422.539300-1-yury.norov@gmail.com> Precedence: bulk X-Mailing-List: dmaengine@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20231203192422.539300-1-yury.norov@gmail.com> Organization: Intel Finland Oy - BIC 0357606-4 - Westendinkatu 7, 02160 Espoo 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 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 Received: from lists.ozlabs.org (lists.ozlabs.org [112.213.38.117]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.lore.kernel.org (Postfix) with ESMTPS id 1AFBAC4167B for ; Mon, 4 Dec 2023 21:46:07 +0000 (UTC) Authentication-Results: lists.ozlabs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=intel.com header.i=@intel.com header.a=rsa-sha256 header.s=Intel header.b=Xmx/3+GC; dkim-atps=neutral Received: from boromir.ozlabs.org (localhost [IPv6:::1]) by lists.ozlabs.org (Postfix) with ESMTP id 4Skcg15Wj8z3cZt for ; Tue, 5 Dec 2023 08:46:05 +1100 (AEDT) Authentication-Results: lists.ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=intel.com header.i=@intel.com header.a=rsa-sha256 header.s=Intel header.b=Xmx/3+GC; dkim-atps=neutral Authentication-Results: lists.ozlabs.org; spf=none (no SPF record) smtp.mailfrom=linux.intel.com (client-ip=192.198.163.7; helo=mgamail.intel.com; envelope-from=andriy.shevchenko@linux.intel.com; receiver=lists.ozlabs.org) Received: from mgamail.intel.com (mgamail.intel.com [192.198.163.7]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by lists.ozlabs.org (Postfix) with ESMTPS id 4SkP915PW3z2xmC for ; Tue, 5 Dec 2023 00:07:47 +1100 (AEDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=intel.com; i=@intel.com; q=dns/txt; s=Intel; t=1701695270; x=1733231270; h=date:from:to:cc:subject:message-id:references: mime-version:in-reply-to; bh=UpKiTiLV03HLrMK8OyY7m+bGEMtR9L95NOiQzYClrhU=; b=Xmx/3+GCOY5eOvmw/Dh2Iyn7m2UWaobrzyYF6SqjHCtI8TdM8ShtUg17 06gAHvgov6EvaFeFBk+vXU9xD27sZTnu15g8KC13cGsh9HNgtXIRLiRTV 7xq7COElS5atRXEjAEwY3tCeSXyzNQduqzphDk2REfdAeQPDzkA8ANtEC fxopGNLXOoevcE093WqgBceJtzQNAJOaRgH2lAmPQlhjOYsPzd7T0XO89 JjixuEJ62c7zCp41BUPwA859+wly4p3cNlw4nd9t65J6e/MACtj4d8C6b QPpuewCuY+AnXnso9f/K5PgZr7TduXgJ855de29UTrtnwgTpKg3lUz3rW A==; X-IronPort-AV: E=McAfee;i="6600,9927,10913"; a="15275174" X-IronPort-AV: E=Sophos;i="6.04,249,1695711600"; d="scan'208";a="15275174" Received: from orsmga007.jf.intel.com ([10.7.209.58]) by fmvoesa101.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 04 Dec 2023 05:07:37 -0800 X-ExtLoop1: 1 X-IronPort-AV: E=McAfee;i="6600,9927,10913"; a="763935696" X-IronPort-AV: E=Sophos;i="6.04,249,1695711600"; d="scan'208";a="763935696" Received: from smile.fi.intel.com ([10.237.72.54]) by orsmga007.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 04 Dec 2023 05:07:13 -0800 Received: from andy by smile.fi.intel.com with local (Exim 4.97) (envelope-from ) id 1rA8fA-00000001kqj-2oCl; Mon, 04 Dec 2023 15:07:04 +0200 Date: Mon, 4 Dec 2023 15:07:04 +0200 From: Andy Shevchenko To: Yury Norov Subject: Re: [PATCH v2 00/35] bitops: add atomic find_bit() operations Message-ID: References: <20231203192422.539300-1-yury.norov@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20231203192422.539300-1-yury.norov@gmail.com> Organization: Intel Finland Oy - BIC 0357606-4 - Westendinkatu 7, 02160 Espoo X-Mailman-Approved-At: Tue, 05 Dec 2023 08:44:31 +1100 X-BeenThere: linuxppc-dev@lists.ozlabs.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Linux on PowerPC Developers Mail List List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: linux-sh@vger.kernel.org, Jaroslav Kysela , Hans Verkuil , "Md. Haris Iqbal" , "K. Y. Srinivasan" , Bart Van Assche , Geert Uytterhoeven , Jiri Pirko , Christian Brauner , Nicholas Piggin , Alexey Klimov , Sergey Shtylyov , Thomas Gleixner , Karsten Keil , Greg Kroah-Hartman , linux-usb@vger.kernel.org, linux-wireless@vger.kernel.org, linux-kernel@vger.kernel.org, GR-QLogic-Storage-Upstream@marvell.com, Andrew Morton , Mark Rutland , alsa-devel@alsa-project.org, Dave Hansen , Eric Dumazet , Gregory Greenman , linux-s390@vger.kernel.org, Valentin Schneider , Leon Romanovsky , Will Deacon , mpi3mr-linuxdrv.pdl@broadcom.com, Hugh Dickins , iommu@lists.linux.dev, Martin Habets , linux-media@vger.kernel.org, Stanislaw Gruszka , linux-arm-msm@vger.kernel.org, Wenjia Zhang , linux-m68k@lists.linux-m68k.org, linux-arm-kernel@lists.infradead.org, Sean Christopherson , Oliver Neukum , Mirsad Todorovac , linux-pci@vger.kernel.org, Rasmus Villemoes , linux-hyperv@vger.kernel.org, Matthew Wilcox , Jiri Slaby , Rob Herring , linux-rdma@vger.kernel.org, Damien Le Moal , ath10k@lists.infradead.org, David Disseldorp , Paolo Abeni , Fenghua Yu , Kees Cook , "James E.J. Bot tomley" , Akinobu Mita , Steven Rostedt , Borislav Petkov , Mauro Carvalho Chehab , Thomas Bogendoerfer , Edward Cree , Shuai Xue , netdev@vger.kernel.org, "David S. Miller" , Rich Felker , Jan Kara , kvm@vger.kernel.org, Peter Zijlstra , "H. Peter Anvin" , sparclinux@vger.kernel.org, Ping-Ke Shih , linux-scsi@vger.kernel.org, linux-net-drivers@amd.com, x86@kernel.org, Jason Gunthorpe , Ingo Molnar , linux-serial@vger.kernel.org, Jakub Kicinski , Chaitanya Kulkarni , Kalle Valo , linux-block@vger.kernel.org, Hans de Goede , linux-sound@vger.kernel.org, Maxim Kuvyrkov , Jen s Axboe , Michal Simek , Yoshinori Sato , Robin Murphy , Bjorn Andersson , linux-mips@vger.kernel.org, linux-bluetooth@vger.kernel.org, dmaengine@vger.kernel.org, Paolo Bonzini , Vitaly Kuznetsov , linuxppc-dev@lists.ozlabs.org, Karsten Graul Errors-To: linuxppc-dev-bounces+linuxppc-dev=archiver.kernel.org@lists.ozlabs.org Sender: "Linuxppc-dev" 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