From nobody Mon Nov 01 13:23:09 2021 X-Original-To: dev-commits-src-all@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 0C27A18287AA; Mon, 1 Nov 2021 13:23:10 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4HjYcs3TBnz4Wdr; Mon, 1 Nov 2021 13:23:09 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 34E9612364; Mon, 1 Nov 2021 13:23:09 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.16.1/8.16.1) with ESMTP id 1A1DN9jt018970; Mon, 1 Nov 2021 13:23:09 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 1A1DN9nT018969; Mon, 1 Nov 2021 13:23:09 GMT (envelope-from git) Date: Mon, 1 Nov 2021 13:23:09 GMT Message-Id: <202111011323.1A1DN9nT018969@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-branches@FreeBSD.org From: Mark Johnston Subject: git: 2788bb20cc05 - stable/13 - bitset(9): Introduce BIT_FOREACH_ISSET and BIT_FOREACH_ISCLR List-Id: Commit messages for all branches of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-all List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-all@freebsd.org X-BeenThere: dev-commits-src-all@freebsd.org MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: markj X-Git-Repository: src X-Git-Refname: refs/heads/stable/13 X-Git-Reftype: branch X-Git-Commit: 2788bb20cc05f581a57b4f50e5c63f9c70e04208 Auto-Submitted: auto-generated X-ThisMailContainsUnwantedMimeParts: N The branch stable/13 has been updated by markj: URL: https://cgit.FreeBSD.org/src/commit/?id=2788bb20cc05f581a57b4f50e5c63f9c70e04208 commit 2788bb20cc05f581a57b4f50e5c63f9c70e04208 Author: Mark Johnston AuthorDate: 2021-09-21 15:32:23 +0000 Commit: Mark Johnston CommitDate: 2021-11-01 13:20:11 +0000 bitset(9): Introduce BIT_FOREACH_ISSET and BIT_FOREACH_ISCLR These allow one to non-destructively iterate over the set or clear bits in a bitset. The motivation is that we have several code fragments which iterate over a CPU set like this: while ((cpu = CPU_FFS(&cpus)) != 0) { cpu--; CPU_CLR(cpu, &cpus); ; } This is slow since CPU_FFS begins the search at the beginning of the bitset each time. On amd64 and arm64, CPU sets have size 256, so there are four limbs in the bitset and we do a lot of unnecessary scanning. A second problem is that this is destructive, so code which needs to preserve the original set has to make a copy. In particular, we have quite a few functions which take a cpuset_t parameter by value, meaning that each call has to copy the 32 byte cpuset_t. The new macros address both problems. Reviewed by: cem, kib Sponsored by: The FreeBSD Foundation (cherry picked from commit dfd3bde5775ecf88851d5dffd6a8ed6076b53566) --- share/man/man9/Makefile | 2 ++ share/man/man9/bitset.9 | 34 ++++++++++++++++++++++++++++++++-- sys/sys/bitset.h | 10 ++++++++++ 3 files changed, 44 insertions(+), 2 deletions(-) diff --git a/share/man/man9/Makefile b/share/man/man9/Makefile index c180742bdb4b..8793eb6b7278 100644 --- a/share/man/man9/Makefile +++ b/share/man/man9/Makefile @@ -616,6 +616,8 @@ MLINKS+=bitset.9 BITSET_DEFINE.9 \ bitset.9 BIT_FFS.9 \ bitset.9 BIT_FFS_AT.9 \ bitset.9 BIT_FLS.9 \ + bitset.9 BIT_FOREACH_ISSET.9 \ + bitset.9 BIT_FOREACH_ISCLR.9 \ bitset.9 BIT_COUNT.9 \ bitset.9 BIT_SUBSET.9 \ bitset.9 BIT_OVERLAP.9 \ diff --git a/share/man/man9/bitset.9 b/share/man/man9/bitset.9 index 1e080f515788..5788f09f2465 100644 --- a/share/man/man9/bitset.9 +++ b/share/man/man9/bitset.9 @@ -24,7 +24,7 @@ .\" .\" $FreeBSD$ .\" -.Dd December 31, 2020 +.Dd September 20, 2021 .Dt BITSET 9 .Os .Sh NAME @@ -45,6 +45,8 @@ .Nm BIT_FFS , .Nm BIT_FFS_AT , .Nm BIT_FLS , +.Nm BIT_FOREACH_ISSET , +.Nm BIT_FOREACH_ISCLR , .Nm BIT_COUNT , .Nm BIT_SUBSET , .Nm BIT_OVERLAP , @@ -92,9 +94,18 @@ .Fn BIT_FFS_AT "const SETSIZE" "struct STRUCTNAME *bitset" "long start" .Ft long .Fn BIT_FLS "const SETSIZE" "struct STRUCTNAME *bitset" +.Fo BIT_FOREACH_ISSET +.Fa "const SETSIZE" +.Fa "size_t bit" +.Fa "const struct STRUCTNAME *bitset" +.Fc +.Fo BIT_FOREACH_ISCLR +.Fa "const SETSIZE" +.Fa "size_t bit" +.Fa "const struct STRUCTNAME *bitset" +.Fc .Ft long .Fn BIT_COUNT "const SETSIZE" "struct STRUCTNAME *bitset" -.\" .Ft bool .Fo BIT_SUBSET .Fa "const SETSIZE" "struct STRUCTNAME *haystack" "struct STRUCTNAME *needle" @@ -329,6 +340,25 @@ index parameter to any other macro, you must subtract one from the result. .Pp The +.Fn BIT_FOREACH_ISSET +macro can be used to iterate over all set bits in +.Fa bitset . +The index variable +.Fa bit +must have been declared with type +.Ft int , +and upon each iteration +.Fa bit +is set to the index of successive set bits. +The value of +.Fa bit +after the loop terminates is undefined. +Similarly, +.Fn BIT_FOREACH_ISCLR +iterates over all clear bits in +.Fa bitset . +.Pp +The .Fn BIT_COUNT macro returns the total number of set bits in .Fa bitset . diff --git a/sys/sys/bitset.h b/sys/sys/bitset.h index 2b5df78a8193..ab6eaf85b8df 100644 --- a/sys/sys/bitset.h +++ b/sys/sys/bitset.h @@ -271,6 +271,16 @@ __count; \ }) +/* Non-destructively loop over all set or clear bits in the set. */ +#define _BIT_FOREACH(_s, i, p, op) \ + for (__size_t __i = 0; __i < __bitset_words(_s); __i++) \ + for (long __j = op((p)->__bits[__i]), __b = ffsl(__j); \ + (i = (__b - 1) + __i * _BITSET_BITS), __j != 0; \ + __j &= ~(1l << i), __b = ffsl(__j)) + +#define BIT_FOREACH_ISSET(_s, i, p) _BIT_FOREACH(_s, i, p, ) +#define BIT_FOREACH_ISCLR(_s, i, p) _BIT_FOREACH(_s, i, p, ~) + #define BITSET_T_INITIALIZER(x) \ { .__bits = { x } }