[src/trunk]: src/sys/external/bsd/common/include/linux Give find_first/next_s...

[riastradh <riastradh%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/5185f5ac6cff
branches:  trunk
changeset: 835392:5185f5ac6cff
user:      riastradh <riastradh%NetBSD.org@localhost>
date:      Mon Aug 27 14:46:23 2018 +0000

description:
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...

diffstat:

 sys/external/bsd/common/include/linux/bitops.h |  54 ++++++++++++++-----------
 1 files changed, 31 insertions(+), 23 deletions(-)

diffs (83 lines):

diff -r 5476279f5a6a -r 5185f5ac6cff sys/external/bsd/common/include/linux/bitops.h
--- a/sys/external/bsd/common/include/linux/bitops.h    Mon Aug 27 14:46:10 2018 +0000
+++ b/sys/external/bsd/common/include/linux/bitops.h    Mon Aug 27 14:46:23 2018 +0000
@@ -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 @@
 {
        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 @@
 
        /* 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;
+               /* Toggle the bits and convert to 64 bits for ffs64.  */
+               word = *p ^ toggle;
+
+               /* Clear the low startbit%bpl bits.  */
+               word &= (~0UL << (startbit % bpl));
 
-                       /* Clear the low startbit%bpl bits.  */
-                       word &= ~(~0UL << (startbit % bpl));
+               /* Are any of these bits set now?  */
+               if (word)
+                       goto out;
 
-                       /* Find the first set bit in this word. */
-                       result += ffs64(word);
-
-                       /* Clamp down to at most nbits.  */
-                       return MIN(result, nbits);
-               }
+               /* 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;
 
-       /* Find the first set bit in this word.  */
-       result += ffs64(word);
+out:
+       /* Count how many words we've skipped.  */
+       result = bpl*(p - ptr);
 
-       /* Clamp down to at most nbits.  */
+       /* Find the first set bit in this word, zero-based.  */
+       result += ffs64(word) - 1;
+
+       /* We may have overshot, so clamp down to at most nbits.  */
        return MIN(result, nbits);
 }