Re: bug in optimised strstr

[Eric Blake <ebb9 at byu dot net>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

According to Sam Clegg on 10/2/2008 2:41 AM:
> I think there is bug in the current strstr implementation.  I initially
> found this in the codesourcery distribution and have recently reproduced
> it using newlib form CVS on both arm and x86 platforms.  Here is the
> repro case:
> 
>     const char* s1 = "GL_OES_byte_coordinates GL_OES_compressed_paletted_texture GL_OES_fixed_point GL_OES_point_size_array GL_OES_point_sprite GL_OES_read_format GL_OES_single_precision GL_IMG_texture_compression_pvrtc GL_IMG_texture_env_enhanced_fixed_function GL_ARB_texture_env_combine GL_ARB_texture_env_dot3 GL_IMG_user_clip_planes GL_OES_matrix_get GL_IMG_vertex_program GL_EXT_multi_draw_arrays GL_OES_matrix_palette GL_OES_draw_texture ";
>     const char* s2 = "GL_IMG_texture_compression_pvrtc";
>     const char* res = strstr(s1, s2);  // crash in critical_factorization

Thanks for the test case.  I wrote that implementation of strstr earlier
this year, and it is in use in both newlib and m4 1.4.11 (among other
places).  I could not quickly confirm the crash using m4 1.4.11 (I got the
expected answer of s1+165), but I'll continue looking into the matter
(perhaps there is a subtle bug in newlib not present in m4's version).

> 
> This bug seems to have been in newlib for a long time.

Do you have a stack trace?  If so, which line of critical_factorization is
crashing?  That implementation was only submitted around Jan or Feb of
this year; did the previous implementation crash?  If the crash is truly
in critical_factorization, then you should see it for almost any s1 that
is longer than s2 (critical_factorization only operates on s2).  Is the
bug also present in memmem or strcasestr, which also use
critical_factorization?

>  It can be worked
> around by compiling with -Os and thereby disabling the strstr
> optimisations.

Yes, that is a valid workaround; it trades worst-case O(n+m) speed and
large (but still O(1)) space, for worst-case O(n*m) speed and much smaller
O(1) space, bypassing critical_factorization altogether.

- --
Don't work too hard, make some time for fun as well!

Eric Blake             ebb9@byu.net
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Public key at home.comcast.net/~ericblake/eblake.gpg
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkjkv2MACgkQ84KuGfSFAYDt5QCg2MJXeIx3AjIchsx27+rXqHfR
/CwAnjmAdaGrTyRkdf5hPggpY2xFzjuD
=nTT+
-----END PGP SIGNATURE-----