Re: [TRIVIAL] Re: UP went into unexpected trashing

Re: [TRIVIAL] Re: UP went into unexpected trashing

[Petr Vandrovec]

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
                                                vandrove@vc.cvut.cz
                                                

Re: [TRIVIAL] Re: UP went into unexpected trashing

[Dipankar Sarma]

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;
 }
 
 /**

Re: [TRIVIAL] Re: UP went into unexpected trashing

[Linus Torvalds]

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

Re: [TRIVIAL] Re: UP went into unexpected trashing

[Rusty Russell]

In message <Pine.LNX.4.44.0211081206140.4471-100000@penguin.transmeta.com> 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)
 {

Re: [TRIVIAL] Re: UP went into unexpected trashing

[Linus Torvalds]

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

Re: [TRIVIAL] Re: UP went into unexpected trashing

[Rusty Russell]

In message <Pine.LNX.4.44.0211082038580.1609-100000@home.transmeta.com> 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.

[TRIVIAL] Re: UP went into unexpected trashing

[Rusty Trivial Russell]

[ 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:  dipankar@in.ibm.com

  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  <dipankar@in.ibm.com> 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: dipankar@in.ibm.com: Re: [long]2.5.44-mm3 UP went into unexpected trashing