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 B073CC46CA2 for ; Sat, 16 Dec 2023 22:58:24 +0000 (UTC) Authentication-Results: lists.ozlabs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20230601 header.b=VxLZ854V; dkim-atps=neutral Received: from boromir.ozlabs.org (localhost [IPv6:::1]) by lists.ozlabs.org (Postfix) with ESMTP id 4St1hv1drCz3cPW for ; Sun, 17 Dec 2023 09:58:23 +1100 (AEDT) Authentication-Results: lists.ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20230601 header.b=VxLZ854V; dkim-atps=neutral Authentication-Results: lists.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gmail.com (client-ip=2607:f8b0:4864:20::236; helo=mail-oi1-x236.google.com; envelope-from=yury.norov@gmail.com; receiver=lists.ozlabs.org) Received: from mail-oi1-x236.google.com (mail-oi1-x236.google.com [IPv6:2607:f8b0:4864:20::236]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by lists.ozlabs.org (Postfix) with ESMTPS id 4St08C1g3kz30YS for ; Sun, 17 Dec 2023 08:48:25 +1100 (AEDT) Received: by mail-oi1-x236.google.com with SMTP id 5614622812f47-3b9db318839so1431973b6e.3 for ; Sat, 16 Dec 2023 13:48:25 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1702763300; x=1703368100; darn=lists.ozlabs.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=NUQpZPD/c05+/8BhIN1J/cQeLxUmIOzSz7QCay9VzCE=; b=VxLZ854VcbG/gmyiOQ+BAMrSEkbv3X7slQR6+8yx2twZ1RAv5127FTfk9C1maJoI4u RRYN3phbyQo6RycRHy61SI1f4fbmswbH43Kq0q+6M6ffbJhwOfNpeOCPl00T0C7n3npT Pq7Q/ILSZGwATXkVWCtlB5MACjIXJaT8VU9RNK5fjz+qv5SgiazAccsiNS5IAZkKEbLr 8wBKJA+s+AHHAaSvcaKSRGLX31ydXBHSPd8/hjH/Bn1i1Z/6dHzobM8abroNmfqQHMIo ARGFOqBI3VtqCWstznUql4y/MZNOOcInATJpxdmRkSwYmAlil1WJJ6dcFaxoHVc/nYyw yeMQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1702763300; x=1703368100; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=NUQpZPD/c05+/8BhIN1J/cQeLxUmIOzSz7QCay9VzCE=; b=BSte5LangE4OQBrElu/7nbtE7lmp5lUFeqQ7JQHBtv525dwwx1dw1EVMz/wpfI+Opg nAcB8+qTU5ssvGaO2U3uYKGK9D19JkrHjuejSue9H6UTGtPkz3LtwXs87PSGq66tfmqA VPFMfqTxXCssp1REqtvMQWFKPADsRC2i1K+kUdo1EI9jMZ9b3LOevMnEyjITMsLIr+d7 Gj2jfEOin2eWq7vtrXgGVQHEcuBjem3CFxdoOuLZB0BzzaHRzUCaGu1gvoHePZrYx9c8 XLquk6D1VTVnNwIVSVL9hBicQsCEAtMDoiOPEDhpJqGwLxZHfBO10hcvmEennTIhqNt0 633A== X-Gm-Message-State: AOJu0YwCLF9XCIV+lxH+43Xgu0pM9E1aFgFx9T47APc10SFmQb3VHmEg pFFxjQB8ckYIyS7L93VT5Aw= X-Google-Smtp-Source: AGHT+IFAZquuH097Av+/ztaIvHAct5BHBdf+5D2NTKxYyfNfNcV2HR26lQ0bCSd6CXKBysIoEd8l8w== X-Received: by 2002:a05:6808:1819:b0:3b8:b063:6658 with SMTP id bh25-20020a056808181900b003b8b0636658mr13429212oib.79.1702763299744; Sat, 16 Dec 2023 13:48:19 -0800 (PST) Received: from localhost ([2601:344:8301:57f0:4a5e:2f67:f6d1:4a98]) by smtp.gmail.com with ESMTPSA id l6-20020a25bcc6000000b00dbd22a3eb4fsm60955ybm.51.2023.12.16.13.48.18 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 16 Dec 2023 13:48:19 -0800 (PST) Date: Sat, 16 Dec 2023 13:48:18 -0800 From: Yury Norov To: 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 Subject: Re: [PATCH v3 00/35] bitops: add atomic find_bit() operations Message-ID: References: <20231212022749.625238-1-yury.norov@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20231212022749.625238-1-yury.norov@gmail.com> X-Mailman-Approved-At: Sun, 17 Dec 2023 09:57: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: Sergey Shtylyov , Jan Kara , Bart Van Assche , Rasmus Villemoes , Matthew Wilcox , Alexey Klimov , Mirsad Todorovac , Andy Shevchenko , Maxim Kuvyrkov Errors-To: linuxppc-dev-bounces+linuxppc-dev=archiver.kernel.org@lists.ozlabs.org Sender: "Linuxppc-dev" 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