Module Name: src
Committed By: riastradh
Date: Mon Aug 27 14:46:23 UTC 2018
Modified Files:
src/sys/external/bsd/common/include/linux: bitops.h
Log Message:
Give find_first/next_set/zero_bit a chance to work.
Self-review comments on the draft thrown together in a hurry two
weeks ago:
- I bet I screwed up for_each_set_bit or something.
- There might be several bits wrong in this __find_next_bit routine!
- for_each_set_bit is busted.
- Maybe I should test this stuff before I commit it.
- Hey, cool, buffer overflow here.
- What was I thinking.
- how did this even
- Was I drunk? I'm never drunk.
- I don't even drink.
- It wasn't even that late at night...
To generate a diff of this commit:
cvs rdiff -u -r1.7 -r1.8 src/sys/external/bsd/common/include/linux/bitops.h
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/sys/external/bsd/common/include/linux/bitops.h
diff -u src/sys/external/bsd/common/include/linux/bitops.h:1.7 src/sys/external/bsd/common/include/linux/bitops.h:1.8
--- src/sys/external/bsd/common/include/linux/bitops.h:1.7 Mon Aug 27 13:54:37 2018
+++ src/sys/external/bsd/common/include/linux/bitops.h Mon Aug 27 14:46:23 2018
@@ -1,4 +1,4 @@
-/* $NetBSD: bitops.h,v 1.7 2018/08/27 13:54:37 riastradh Exp $ */
+/* $NetBSD: bitops.h,v 1.8 2018/08/27 14:46:23 riastradh Exp $ */
/*-
* Copyright (c) 2013 The NetBSD Foundation, Inc.
@@ -188,7 +188,8 @@ __find_next_bit(const unsigned long *ptr
{
const size_t bpl = (CHAR_BIT * sizeof(*ptr));
const unsigned long *p = ptr + startbit/bpl;
- unsigned long result = rounddown(startbit, bpl);
+ size_t n = howmany(nbits, bpl);
+ unsigned long result;
uint64_t word;
/*
@@ -200,35 +201,42 @@ __find_next_bit(const unsigned long *ptr
/* Do we need to examine a partial starting word? */
if (startbit % bpl) {
- /* Are any of the first startbit%bpl bits zero? */
- if ((*p ^ toggle) & ~(~0UL << (startbit % bpl))) {
- /* Toggle the bits and convert to 64 bits. */
- word = *p ^ toggle;
-
- /* Clear the low startbit%bpl bits. */
- word &= ~(~0UL << (startbit % bpl));
-
- /* Find the first set bit in this word. */
- result += ffs64(word);
-
- /* Clamp down to at most nbits. */
- return MIN(result, nbits);
- }
+ /* Toggle the bits and convert to 64 bits for ffs64. */
+ word = *p ^ toggle;
+
+ /* Clear the low startbit%bpl bits. */
+ word &= (~0UL << (startbit % bpl));
+
+ /* Are any of these bits set now? */
+ if (word)
+ goto out;
+
+ /* Move past it. */
+ p++;
+ n--;
}
- /* Find the first word matching word. */
- for (; bpl < nbits; p++, result += bpl) {
- if (*p ^ toggle)
- break;
+ /* Find the first word with any bits set. */
+ for (; n --> 0; p++) {
+ /* Toggle the bits and convert to 64 bits for ffs64. */
+ word = *p ^ toggle;
+
+ /* Are any of these bits set now? */
+ if (word)
+ goto out;
}
- /* Toggle the bits and convert to 64 bits for ffs64. */
- word = *p ^ toggle;
+ /* Nada. */
+ return nbits;
+
+out:
+ /* Count how many words we've skipped. */
+ result = bpl*(p - ptr);
- /* Find the first set bit in this word. */
- result += ffs64(word);
+ /* Find the first set bit in this word, zero-based. */
+ result += ffs64(word) - 1;
- /* Clamp down to at most nbits. */
+ /* We may have overshot, so clamp down to at most nbits. */
return MIN(result, nbits);
}
