Index: share/man/man9/bitset.9
===================================================================
--- share/man/man9/bitset.9
+++ share/man/man9/bitset.9
@@ -42,9 +42,14 @@
 .Nm BIT_SETOF ,
 .Nm BIT_EMPTY ,
 .Nm BIT_ISFULLSET ,
+.Nm BIT_FFC ,
+.Nm BIT_FFC_AT ,
 .Nm BIT_FFS ,
 .Nm BIT_FFS_AT ,
+.Nm BIT_FLC ,
+.Nm BIT_FLC_AT ,
 .Nm BIT_FLS ,
+.Nm BIT_FLS_AT ,
 .Nm BIT_FOREACH_ISSET ,
 .Nm BIT_FOREACH_ISCLR ,
 .Nm BIT_COUNT ,
@@ -89,11 +94,21 @@
 .Ft bool
 .Fn BIT_ISFULLSET "const SETSIZE" "struct STRUCTNAME *bitset"
 .Ft long
+.Fn BIT_FFC "const SETSIZE" "struct STRUCTNAME *bitset"
+.Ft long
+.Fn BIT_FFC_AT "const SETSIZE" "struct STRUCTNAME *bitset" "long start"
+.Ft long
 .Fn BIT_FFS "const SETSIZE" "struct STRUCTNAME *bitset"
 .Ft long
 .Fn BIT_FFS_AT "const SETSIZE" "struct STRUCTNAME *bitset" "long start"
 .Ft long
+.Fn BIT_FLC "const SETSIZE" "struct STRUCTNAME *bitset"
+.Ft long
+.Fn BIT_FLC_AT "const SETSIZE" "struct STRUCTNAME *bitset" "long start"
+.Ft long
 .Fn BIT_FLS "const SETSIZE" "struct STRUCTNAME *bitset"
+.Ft long
+.Fn BIT_FLS_AT "const SETSIZE" "struct STRUCTNAME *bitset" "long start"
 .Fo BIT_FOREACH_ISSET
 .Fa "const SETSIZE"
 .Fa "size_t bit"
@@ -256,6 +271,16 @@
 performs multiple individually atomic operations.)
 .Pp
 The
+.Fn BIT_ISSET
+macro returns
+.Dv true
+if the bit
+.Fa bit
+in the bitset pointed to by
+.Fa bitset
+is set.
+.Pp
+The
 .Fn BIT_SET
 macro sets bit
 .Fa bit
@@ -305,6 +330,35 @@
 is full (all bits set).
 .Pp
 The
+.Fn BIT_FFC
+macro returns the 1-index of the first (lowest) clear bit in
+.Fa bitset ,
+or zero if
+.Fa bitset
+is full.
+Like with
+.Xr ffs 3 ,
+to use the non-zero result of
+.Fn BIT_FFC
+as a
+.Fa bit
+index parameter to any other
+.Nm
+macro, you must subtract one from the result.
+.Pp
+The
+.Fn BIT_FFC_AT
+macro returns the 1-index of the first (lowest) clear bit in
+.Fa bitset ,
+which is greater than the given 0-indexed
+.Fa start ,
+or zero if no bits in
+.Fa bitset
+greater than
+.Fa start
+are clear.
+.Pp
+The
 .Fn BIT_FFS
 macro returns the 1-index of the first (lowest) set bit in
 .Fa bitset ,
@@ -325,7 +379,7 @@
 .Fn BIT_FFS_AT
 macro returns the 1-index of the first (lowest) set bit in
 .Fa bitset ,
-which is greater than the given 1-indexed
+which is greater than the given 0-indexed
 .Fa start ,
 or zero if no bits in
 .Fa bitset
@@ -334,6 +388,35 @@
 are set.
 .Pp
 The
+.Fn BIT_FLC
+macro returns the 1-index of the last (highest) clear bit in
+.Fa bitset ,
+or zero if
+.Fa bitset
+is full.
+Like with
+.Xr fls 3 ,
+to use the non-zero result of
+.Fn BIT_FLC
+as a
+.Fa bit
+index parameter to any other
+.Nm
+macro, you must subtract one from the result.
+.Pp
+The
+.Fn BIT_FLC_AT
+macro returns the 1-index of the last (highest) clear bit in
+.Fa bitset ,
+which is greater than the given 0-indexed
+.Fa start ,
+or zero if no bits in
+.Fa bitset
+greater than
+.Fa start
+are clear.
+.Pp
+The
 .Fn BIT_FLS
 macro returns the 1-index of the last (highest) set bit in
 .Fa bitset ,
@@ -351,6 +434,18 @@
 macro, you must subtract one from the result.
 .Pp
 The
+.Fn BIT_FLS_AT
+macro returns the 1-index of the last (highest) set bit in
+.Fa bitset ,
+which is greater than the given 0-indexed
+.Fa start ,
+or zero if no bits in
+.Fa bitset
+greater than
+.Fa start
+are set.
+.Pp
+The
 .Fn BIT_FOREACH_ISSET
 macro can be used to iterate over all set bits in
 .Fa bitset .
Index: sys/sys/bitset.h
===================================================================
--- sys/sys/bitset.h
+++ sys/sys/bitset.h
@@ -222,45 +222,67 @@
 } while (0)
 
 /*
- * Note that `start` and the returned value from __BIT_FFS_AT are
- * 1-based bit indices.
+ * Note the returned value from __BIT_FFV_AT is a 1-based bit index.
  */
-#define	__BIT_FFS_AT(_s, p, start) __extension__ ({			\
+#define	__BIT_FFV_AT(_s, p, start, flip) __extension__ ({		\
 	__size_t __i;							\
 	long __bit, __mask;						\
 									\
-	__mask = ~0UL << ((start) % _BITSET_BITS);			\
 	__bit = 0;							\
-	for (__i = __bitset_word((_s), (start));			\
-	    __i < __bitset_words((_s));					\
-	    __i++) {							\
-		if (((p)->__bits[__i] & __mask) != 0) {			\
-			__bit = ffsl((p)->__bits[__i] & __mask);	\
+	if ((start) < (_s)) {						\
+		__i = __bitset_word((_s), (start));			\
+		__mask = ~0UL << ((start) % _BITSET_BITS);		\
+		__mask &= (flip) ^ (p)->__bits[__i];			\
+		while (__mask == 0 && ++__i < __bitset_words((_s)))	\
+			__mask = (flip) ^ (p)->__bits[__i];		\
+		if (__mask != 0 && (_s) % _BITSET_BITS != 0 &&		\
+		    __i == __bitset_words((_s)) - 1)			\
+			__mask = ~0UL >> (-(_s) & (_BITSET_BITS - 1));	\
+		if (__mask != 0) {					\
+			__bit = ffsl(__mask);				\
 			__bit += __i * _BITSET_BITS;			\
-			break;						\
 		}							\
-		__mask = ~0UL;						\
 	}								\
 	__bit;								\
 })
 
+#define __BIT_FFC_AT(_s, p, start) __BIT_FFV_AT(_s, p, start, ~0UL)
+#define	__BIT_FFC(_s, p) __BIT_FFC_AT((_s), (p), 0)
+
+#define __BIT_FFS_AT(_s, p, start) __BIT_FFV_AT(_s, p, start, 0UL)
 #define	__BIT_FFS(_s, p) __BIT_FFS_AT((_s), (p), 0)
 
-#define	__BIT_FLS(_s, p) __extension__ ({			       	\
+/*
+ * Note the returned value from __BIT_FLV_AT is a 1-based bit index.
+ */
+#define	__BIT_FLV_AT(_s, p, start, flip) __extension__ ({		\
 	__size_t __i;							\
-	long __bit;							\
+	long __bit, __mask;						\
 									\
 	__bit = 0;							\
-	for (__i = __bitset_words((_s)); __i > 0; __i--) {		\
-		if ((p)->__bits[__i - 1] != 0) {			\
-			__bit = flsl((p)->__bits[__i - 1]);		\
-			__bit += (__i - 1) * _BITSET_BITS;		\
-			break;						\
+	__i = __bitset_words((_s));					\
+	if ((start) < (_s)) {						\
+		__mask = ~0UL >> (-(_s) & (_BITSET_BITS - 1));		\
+		__mask &= (flip) ^ (p)->__bits[--__i];			\
+		while (__mask == 0 && __bitset_word((_s), (start)) < __i)\
+			__mask = (flip) ^ (p)->__bits[--__i];		\
+		if (__mask != 0 && (start) % _BITSET_BITS != 0 &&	\
+		    __bitset_word((_s), (start)) == __i)		\
+			__mask &= ~0UL << ((start) % _BITSET_BITS);	\
+		if (__mask != 0) {					\
+			__bit = flsl(__mask);				\
+			__bit += __i * _BITSET_BITS;			\
 		}							\
 	}								\
 	__bit;								\
 })
 
+#define	__BIT_FLC_AT(_s, p, start) __BIT_FLV_AT((_s), (p), start, ~0UL)
+#define	__BIT_FLC(_s, p) __BIT_FLC_AT((_s), (p), 0)
+
+#define	__BIT_FLS_AT(_s, p, start) __BIT_FLV_AT((_s), (p), start, 0UL)
+#define	__BIT_FLS(_s, p) __BIT_FLS_AT((_s), (p), 0)
+
 #define	__BIT_COUNT(_s, p) __extension__ ({				\
 	__size_t __i;							\
 	long __count;							\
@@ -324,10 +346,15 @@
 #define	BIT_COPY_STORE_REL(_s, f, t)		__BIT_COPY_STORE_REL(_s, f, t)
 #define	BIT_COUNT(_s, p)			__BIT_COUNT(_s, p)
 #define	BIT_EMPTY(_s, p)			__BIT_EMPTY(_s, p)
+#define	BIT_FFC(_s, p)				__BIT_FFC(_s, p)
+#define	BIT_FFC_AT(_s, p, start)		__BIT_FFC_AT(_s, p, start)
 #define	BIT_FFS(_s, p)				__BIT_FFS(_s, p)
 #define	BIT_FFS_AT(_s, p, start)		__BIT_FFS_AT(_s, p, start)
 #define	BIT_FILL(_s, p)				__BIT_FILL(_s, p)
+#define	BIT_FLC(_s, p)				__BIT_FLC(_s, p)
+#define	BIT_FLC_AT(_s, p, start)		__BIT_FLC_AT(_s, p, start)
 #define	BIT_FLS(_s, p)				__BIT_FLS(_s, p)
+#define	BIT_FLS_AT(_s, p, start)		__BIT_FLS_AT(_s, p, start)
 #define BIT_FOREACH(_s, i, p, op)		__BIT_FOREACH(_s, i, p, op)
 #define	BIT_FOREACH_ADVANCE(_s, i, p, op)	__BIT_FOREACH_ADVANCE(_s, i, p, op)
 #define	BIT_FOREACH_ISCLR(_s, i, p)		__BIT_FOREACH_ISCLR(_s, i, p)
Index: tests/sys/sys/bitset_test.c
===================================================================
--- tests/sys/sys/bitset_test.c
+++ tests/sys/sys/bitset_test.c
@@ -83,8 +83,106 @@
 #undef _BIT_FOREACH_COUNT
 }
 
+ATF_TC_WITHOUT_HEAD(bit_ffs);
+ATF_TC_BODY(bit_ffs, tc)
+{
+	struct bs256 bsrand;
+	int i, j;
+
+	BIT_ZERO(256, &bsrand);
+	for (i = 0; i < 256; i++)
+		if (random() % 2 != 0)
+			BIT_SET(256, i, &bsrand);
+
+	/*
+	 * Try to verify that BIT_FFS_AT is correct
+	 * for all start values.
+	 */
+	for (i = 0; i < 256; i++) {
+		j = BIT_FFS_AT(256, &bsrand, i);
+		ATF_REQUIRE_MSG(i < j && j <= 256 || j == 0,
+		    "out of range ffs value %d not in [%d, 256]", j, i);
+		if (j != 0) {
+			j--;
+			ATF_REQUIRE_MSG(BIT_ISSET(256, j, &bsrand),
+			    "ffs[%d, 256] incorrect 0 ffs value %d", i, j);
+		} else
+			j = 256;
+		while (--j >= i)
+			ATF_REQUIRE_MSG(!BIT_ISSET(256, j, &bsrand),
+			    "ffs[%d, 256] incorrect 1 ffs value %d", i, j);
+	}
+
+	/*
+	 * Try to verify that BIT_FFS is correct
+	 * for all size values.
+	 */
+	for (i = 1; i <= 256; i++) {
+		j = BIT_FFS(i, &bsrand);
+		ATF_REQUIRE_MSG(0 <= j && j <= i,
+		    "out of range ffs value %d not in [0, %d]", j, i);
+		if (j != 0) {
+			j--;
+			ATF_REQUIRE_MSG(BIT_ISSET(256, j, &bsrand),
+			    "ffs[0, %d] incorrect 0 ffs value %d", i, j);
+		} else
+			j = i;
+		while (--j >= i)
+			ATF_REQUIRE_MSG(!BIT_ISSET(256, j, &bsrand),
+			    "ffs[0, %d] incorrect 1 ffs value %d", i, j);
+	}
+}
+
+ATF_TC_WITHOUT_HEAD(bit_fls);
+ATF_TC_BODY(bit_fls, tc)
+{
+	struct bs256 bsrand;
+	int i, j;
+
+	BIT_ZERO(256, &bsrand);
+	for (i = 0; i < 256; i++)
+		if (random() % 2 != 0)
+			BIT_SET(256, i, &bsrand);
+
+	/*
+	 * Try to verify that BIT_FLS_AT is correct
+	 * for all start values.
+	 */
+	for (i = 0; i < 256; i++) {
+		j = BIT_FLS_AT(256, &bsrand, i);
+		ATF_REQUIRE_MSG(i < j && j <= 256 || j == 0,
+		    "out of range fls value %d not in [%d, 256]", j, i);
+		if (j != 0) {
+			ATF_REQUIRE_MSG(BIT_ISSET(256, j - 1, &bsrand),
+			    "fls[%d, 256] incorrect 0 fls value %d", i, j - 1);
+		}
+		while (j++ < 256)
+			ATF_REQUIRE_MSG(!BIT_ISSET(256, j - 1, &bsrand),
+			    "fls[%d, 256] incorrect 1 fls value %d", i, j - 1);
+	}
+
+	/*
+	 * Try to verify that BIT_FLS is correct
+	 * for all size values.
+	 */
+	for (i = 1; i <= 256; i++) {
+		j = BIT_FLS(i, &bsrand);
+		ATF_REQUIRE_MSG(0 <= j && j <= i,
+		    "out of range fls value %d not in [0, %d]", j, i);
+		if (j != 0) {
+			ATF_REQUIRE_MSG(BIT_ISSET(256, j - 1, &bsrand),
+			    "fls[0, %d] incorrect 0 fls value %d", i, j - 1);
+		}
+		while (j++ < i)
+			ATF_REQUIRE_MSG(!BIT_ISSET(256, j - 1, &bsrand),
+			    "fls[0, %d] incorrect 1 fls value %d", i, j - 1);
+	}
+}
+
 ATF_TP_ADD_TCS(tp)
 {
 	ATF_TP_ADD_TC(tp, bit_foreach);
+	ATF_TP_ADD_TC(tp, bit_ffs);
+	ATF_TP_ADD_TC(tp, bit_fls);
 	return (atf_no_error());
 }