Re: git-diff-tree rename detection bug

Linus Torvalds writes:

It works, but it does end up complaining about things like 

	==23756== Invalid read of size 4
	==23756==    at 0x25A38990: strlen (in /lib/libc-2.3.5.so)
	..
	==23756==  Address 0x25B86754 is 3 bytes after a block of size 17 alloc'd

which seems to be just strlen prefetching the next word or something like 
that. 

The strlen() in glibc for ppc is unbearably clever hand-coded
assembly, which loads up 8 bytes at a time (once it has the address
8-byte aligned), and does various ANDs and ORs and ADDs and
conditional branches.  If some of the 8 bytes aren't defined, it will
in many cases branch one way or the other based on the undefined
bytes, but end up computing the same result on either branch.

Valgrind is right in that strlen is loading up some bytes that are
past the end of a malloc'd block.  In fact those bytes don't end up
affecting the result, and in fact the load couldn't cause a segfault,
but it's not surprising that Valgrind can't see that, since the value
of the extra bytes can actually affect whether a conditional branch is
taken or not, but we end up with the same result either way.

Valgrind sets LD_PRELOAD so that you get a simple Valgrind-supplied
set of string functions, including strlen, from vgpreload_memcheck.so
rather than the fancy glibc ones.  However, that doesn't seem to catch
the calls to strlen from inside glibc - the call from vfprintf is a
direct branch rather than going through the PLT, for instance.

I could add a suppression to suppress all errors in strlen, but that
would mean you would miss real errors, where the string is not
null-terminated within the malloc'd block, and strlen runs off the
end.

I wish I had a good answer for this problem, but I don't.  Maybe we
need a debugging version of glibc that doesn't use the fancy
bit-fiddling algorithms in the string functions.

(Just for interest: here are the comments from strlen.S:

   1) Given a word 'x', we can test to see if it contains any 0 bytes
      by subtracting 0x01010101, and seeing if any of the high bits of each
      byte changed from 0 to 1. This works because the least significant
      0 byte must have had no incoming carry (otherwise it's not the least
      significant), so it is 0x00 - 0x01 == 0xff. For all other
      byte values, either they have the high bit set initially, or when
      1 is subtracted you get a value in the range 0x00-0x7f, none of which
      have their high bit set. The expression here is
      (x + 0xfefefeff) & ~(x | 0x7f7f7f7f), which gives 0x00000000 when
      there were no 0x00 bytes in the word.

   2) Given a word 'x', we can test to see _which_ byte was zero by
      calculating ~(((x & 0x7f7f7f7f) + 0x7f7f7f7f) | x | 0x7f7f7f7f).
      This produces 0x80 in each byte that was zero, and 0x00 in all
      the other bytes. The '| 0x7f7f7f7f' clears the low 7 bits in each
      byte, and the '| x' part ensures that bytes with the high bit set
      produce 0x00. The addition will carry into the high bit of each byte
      iff that byte had one of its low 7 bits set. We can then just see
      which was the most significant bit set and divide by 8 to find how
      many to add to the index.
      This is from the book 'The PowerPC Compiler Writer's Guide',
      by Steve Hoxey, Faraydon Karim, Bill Hay and Hank Warren.
)

Paul.