This is the mail archive of the mailing list for the newlib project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: bug in optimised strstr

Eric Blake wrote:
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?

Don't bother Sam....

 max_suffix = SIZE_MAX;
 j = 0;
 k = p = 1;
 while (j + k < needle_len)
     a = CANON_ELEMENT (needle[j + k]);
     b = CANON_ELEMENT (needle[max_suffix + k]);

it is the line b=....

It cannot be correct as you are trying to reference SIZE_MAX + 1 the first time through the loop.

-- Jeff J.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]