[ find_first_bit on x86 returns 32 even if you said to stop at (say) 5
bits. Uncovered by the larger cpu mask patch. ]
From: [email protected]
Well, my earlier find_first_bit() implementation was completely bogus.
My sanity has now returned and I coded this patch below that fixes
find_find_bit() to return "size" if all bits are zero. I have tested it
extensively in userspace and it boots 2.5.44-mm5 which crashed with the earlier
version of the bitops_fix patch. I have coded the assembly routine
as optimal as I could think of and without introducing any new
branches or memory loads.
Along with this patch, I applied the larger_cpu_mask patch to -mm5
and sanity tested both UP and SMP kernels for dcache leaks in a 4CPU P3 box.
An ls -lR and subsequent unmounting of that filesystems showed that
the dentries were correctly getting returned the dcache slab and
that indicates that the larger_cpu_mask patch no longer breaks RCU.
I will do some more testing with this combination later with
rcu_stats applied on this tree (just to be sure), but so far it looks good.
Thanks
--
Dipankar Sarma <[email protected]> http://lse.sourceforge.net
Linux Technology Center, IBM Software Lab, Bangalore, India.
bitops_fix.patch
-----------------
--- trivial-2.5-bk/include/asm-i386/bitops.h.orig 2002-11-08 18:47:20.000000000 +1100
+++ trivial-2.5-bk/include/asm-i386/bitops.h 2002-11-08 18:47:20.000000000 +1100
@@ -311,12 +311,13 @@
"repe; scasl\n\t"
"jz 1f\n\t"
"leal -4(%%edi),%%edi\n\t"
- "bsfl (%%edi),%%eax\n"
- "1:\tsubl %%ebx,%%edi\n\t"
+ "bsfl (%%edi),%%edx\n"
+ "subl %%ebx,%%edi\n\t"
"shll $3,%%edi\n\t"
- "addl %%edi,%%eax"
+ "addl %%edi,%%edx\n\t"
+ "1:\tmovl %%edx,%%eax\n\t"
:"=a" (res), "=&c" (d0), "=&D" (d1)
- :"1" ((size + 31) >> 5), "2" (addr), "b" (addr));
+ :"1" ((size + 31) >> 5), "2" (addr), "b" (addr), "d" (size));
return res;
}
--
Don't blame me: the Monkey is driving
File: [email protected]: Re: [long]2.5.44-mm3 UP went into unexpected trashing
On 8 Nov 02 at 19:33, Rusty Trivial Russell wrote:
> --- trivial-2.5-bk/include/asm-i386/bitops.h.orig 2002-11-08 18:47:20.000000000 +1100
> +++ trivial-2.5-bk/include/asm-i386/bitops.h 2002-11-08 18:47:20.000000000 +1100
> @@ -311,12 +311,13 @@
> "repe; scasl\n\t"
> "jz 1f\n\t"
> "leal -4(%%edi),%%edi\n\t"
> - "bsfl (%%edi),%%eax\n"
> - "1:\tsubl %%ebx,%%edi\n\t"
> + "bsfl (%%edi),%%edx\n"
> + "subl %%ebx,%%edi\n\t"
> "shll $3,%%edi\n\t"
> - "addl %%edi,%%eax"
> + "addl %%edi,%%edx\n\t"
> + "1:\tmovl %%edx,%%eax\n\t"
> :"=a" (res), "=&c" (d0), "=&D" (d1)
> - :"1" ((size + 31) >> 5), "2" (addr), "b" (addr));
> + :"1" ((size + 31) >> 5), "2" (addr), "b" (addr), "d" (size));
> return res;
EDX is modified, should not you list "=d" as output, with new variable (d2)?
Or better, drop last line of assembly code, and say that (res) is in
"d", and list "a" as clobbered or dummy output register.
And BTW, if you'll do
unsigned long b = 0x8000;
find_first_bit(&b, 1);
return value will be 15 even with patched function. So either more
fixing is needed, or code which calls find_first_bit() with value which
is not multiple of 32 should take special care that last dword does
not contain set bits after last interesting bit.
So maybe callers should just treat any return value >= size as "not found",
leaving older smaller code in place.
Best regards,
Petr Vandrovec
[email protected]
On Fri, Nov 08, 2002 at 04:40:13PM +0100, Petr Vandrovec wrote:
> On 8 Nov 02 at 19:33, Rusty Trivial Russell wrote:
>
> So maybe callers should just treat any return value >= size as "not found",
> leaving older smaller code in place.
Or add a check in there. I can't figure out a way to avoid the extra
conditional branch anyway :)
Thanks
Dipankar
diff -urN linux-2.5.46-base/include/asm-i386/bitops.h linux-2.5.46-misc/include/asm-i386/bitops.h
--- linux-2.5.46-base/include/asm-i386/bitops.h Sat Sep 28 03:20:22 2002
+++ linux-2.5.46-misc/include/asm-i386/bitops.h Sat Nov 9 01:08:56 2002
@@ -317,7 +317,7 @@
"addl %%edi,%%eax"
:"=a" (res), "=&c" (d0), "=&D" (d1)
:"1" ((size + 31) >> 5), "2" (addr), "b" (addr));
- return res;
+ return (size > res) ? res : size;
}
/**
On Sat, 9 Nov 2002, Dipankar Sarma wrote:
>
> Or add a check in there. I can't figure out a way to avoid the extra
> conditional branch anyway :)
I'd actually rather change the calling convention, and say that the only
valid test is for testing the return value "being in range".
And it's not strictly even a calling convention _change_ - it's always
been that way. See the original user, ie the minix filesystem:
if ((j = minix_find_first_zero_bit(bh->b_data, 8192)) < 8192) {
...
and it's really a documentation fix/update to just tell people about this.
Linus
In message <[email protected]> you
write:
>
> On Sat, 9 Nov 2002, Dipankar Sarma wrote:
> >
> > Or add a check in there. I can't figure out a way to avoid the extra
> > conditional branch anyway :)
>
> I'd actually rather change the calling convention, and say that the only
> valid test is for testing the return value "being in range".
At least gcc 3.0 doesn't do the optimization for you, unfortunately 8(
So I agree, although I'd prefer the stricter definition.
Rusty.
PS. Previous documentation was written by a bad monkey, so I've fixed
it to actually say something useful, too.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.
diff -urpN --exclude TAGS -X /home/rusty/devel/kernel/kernel-patches/current-dontdiff --minimal linux-2.5-bk/include/asm-i386/bitops.h working-2.5-bk-find_first_bit/include/asm-i386/bitops.h
--- linux-2.5-bk/include/asm-i386/bitops.h 2002-11-09 13:33:20.000000000 +1100
+++ working-2.5-bk-find_first_bit/include/asm-i386/bitops.h 2002-11-09 14:12:32.000000000 +1100
@@ -263,10 +263,10 @@ static __inline__ int variable_test_bit(
/**
* find_first_zero_bit - find the first zero bit in a memory region
* @addr: The address to start the search at
- * @size: The maximum size to search
+ * @size: The maximum size to search (may be rounded up by BITS_PER_LONG)
*
- * Returns the bit-number of the first zero bit, not the number of the byte
- * containing a bit.
+ * Returns the bit-number of the first zero bit (not the number of the byte
+ * containing the bit) or a value >= size if none found.
*/
static __inline__ int find_first_zero_bit(unsigned long * addr, unsigned size)
{
@@ -295,10 +295,10 @@ static __inline__ int find_first_zero_bi
/**
* find_first_bit - find the first set bit in a memory region
* @addr: The address to start the search at
- * @size: The maximum size to search
+ * @size: The maximum size to search (may be rounded up by BITS_PER_LONG)
*
- * Returns the bit-number of the first set bit, not the number of the byte
- * containing a bit.
+ * Returns the bit-number of the first set bit (not the number of the byte
+ * containing the bit) or a value >= size if none found.
*/
static __inline__ int find_first_bit(unsigned long * addr, unsigned size)
{
@@ -321,10 +321,14 @@ static __inline__ int find_first_bit(uns
}
/**
- * find_next_zero_bit - find the first zero bit in a memory region
+ * find_next_zero_bit - find the next zero bit in a memory region
* @addr: The address to base the search on
* @offset: The bitnumber to start searching at
- * @size: The maximum size to search
+ * @size: The maximum size to search (may be rounded up by BITS_PER_LONG)
+ *
+ * Returns the bit-number of the first zero bit >= offset (not the
+ * number of the byte containing the bit), or a value >= size if none
+ * found.
*/
static __inline__ int find_next_zero_bit(unsigned long * addr, int size, int offset)
{
@@ -354,10 +358,14 @@ static __inline__ int find_next_zero_bit
}
/**
- * find_next_bit - find the first set bit in a memory region
+ * find_next_bit - find the next set bit in a memory region
* @addr: The address to base the search on
* @offset: The bitnumber to start searching at
- * @size: The maximum size to search
+ * @size: The maximum size to search (may be rounded up by BITS_PER_LONG)
+ *
+ * Returns the bit-number of the first bit set >= offset (not the
+ * number of the byte containing the bit) or a value >= size if none
+ * found.
*/
static __inline__ int find_next_bit(unsigned long *addr, int size, int offset)
{
On Sat, 9 Nov 2002, Rusty Russell wrote:
> - * Returns the bit-number of the first zero bit, not the number of the byte
> - * containing a bit.
> + * Returns the bit-number of the first zero bit (not the number of the byte
> + * containing the bit) or a value >= size if none found.
Ok.
However, what was the original codepath that doesn't follow this and was
the cause of the headache (ie the "unexpected trashing"?) Let's fix that
user of the functions too, not just the documentation..
Linus
In message <[email protected]> you wri
te:
>
> On Sat, 9 Nov 2002, Rusty Russell wrote:
> > + * containing the bit) or a value >= size if none found.
>
> However, what was the original codepath that doesn't follow this and was
> the cause of the headache (ie the "unexpected trashing"?)
It was the "cpu masks become an unsigned long array" patch, which was
in Andrew Morton's mm tree, but you never took.
> Let's fix that user of the functions too, not just the documentation..
You're not adopting the Viro doctine are you? "On each new issue,
begin by assuming your peers are idiots". 8)
It's not becoming,
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.