"Richard L. Hamilton" <[email protected]> wrote:
> memchr() probably shouldn't be going too far either; even though
> it doesn't explicitly have the same restriction, neither does it have
> permission to look past the length bytes starting at the pointer.
>
> The C of memchr is ok. As far as I understand them, I think the
> assembler versions are also being careful not to look past the area
> they're supposed to check. At least, I think the x86 versions are;
> the SPARC versions are a little too creative for me to follow without
> taking a lot of time and aspirin.
The usual fast implemtation of memchr() is based on
masking longs this way:
/*
* The magic mask is a long word where all carry bits a clear.
* This are bits 8, 16, 24 ...
* In addition, the top bit is not set (e.g bit 31 or 63). The magic
* mask will look this way:
*
* bits: 01111110 11111110 ... 11111110 11111111
* bytes: AAAAAAAA BBBBBBBB ... CCCCCCCC DDDDDDDD
*
* If we add anything to this magic number, no carry bit will change if
* it is the first carry bit left to a 0 byte. Adding anything != 0
* to the magic number will just turn the carry bit left to the byte
* but does not propagate any further.
*/
and then to find a long that might match. Such a implementation overshoots
access to the data in most cases and memchr() _is_ permitted to overshoot...
> I did some tests to check for looking past the end. They aren't perfect,
> because they
> require that the area in which it may be ok to look _ends_ at a page boundary
> (so the next page can have no permissions such that accessing it would
> cause an obvious memory violation). So they don't cover the case where the
> area to be searched ends other than on word boundaries. (But they work fine
> with cases where it doesn't start on a word alignment.)
A while ago, I fixed a bug in the Solaris kernel where a 100% correct (but
different from mkisofs) fs formatter created a filesystem with Rock Ridge
extensions. The problem with Rock Ridge filenames is that they are not null
terminated and the Rock Ridge standard permits the filename to be the last
entry in the Rock Ridge knapsack at the end of the ISO-9660 directory entry.
What happened in our specific case was that the last valid character in the
Rock Ridge file name was exactly the last byte in a physical page. As the
strncat() implementation in the Solaris kernel ignores POSIX rules and
overshoots by one with accessing the source memory, we ended up in kernel
panic from accessing a non-existent page....... fortunately we had a kernel
crash dump.
Such problems can only be detected and fixed correctly if the person who works
on the problem knows how to debug kernel crash dumps and at the same time
correctly understands the low level structures of the filesystem. These people
are rare and BTW: the initial analysis from the Sun people who first debugged
the crash dump was wrong as they missed the needed knowledge on the filesystem
structure.
As you see, it is unpredicatble what an incorrect implementation may finally
cause as result.
Jörg
--
EMail:[email protected] (home) Jörg Schilling D-13353 Berlin
[email protected] (uni)
[email protected] (work) Blog:
http://schily.blogspot.com/
URL: http://cdrecord.berlios.de/private/ ftp://ftp.berlios.de/pub/schily
_______________________________________________
opensolaris-code mailing list
[email protected]
http://mail.opensolaris.org/mailman/listinfo/opensolaris-code
