[RFC] strrstr function in libbb failes on some corner cases

Denys Vlasenko vda.linux at googlemail.com
Mon Jun 16 04:33:35 UTC 2008


On Sunday 15 June 2008 23:06, Tito wrote:
> Hi,
> while inspecting the last changes in busybox code I hit some issues in
> libbb/strrstr.c. The strrtstr function fails on some corner cases of a little
> test program I wrote (and bombs out on NULL pointers):
> 
> char* strrstr(const char *haystack, const char *needle)
> {
> 	char *tmp = strrchr(haystack, *needle);
> 	if (tmp == NULL || strcmp(tmp, needle) != 0)
> 		return NULL;
> 	return tmp;
> }
> 
> 
> ./test
> 'baaabaaab'  vs. 'aaa'       : FAILED
> 'baaabaaaab' vs. 'aaa'       : FAILED
> 'baaabaab'   vs. 'aaa'       : FAILED
> 'aaa'        vs. 'aaa'       : FAILED
> 'aaa'        vs. 'a'         : PASSED
> 'aaa'        vs. 'bbb'       : PASSED
> 'a'          vs. 'aaa'       : PASSED
> 'aaa'        vs. ''          : FAILED
> ''           vs. 'aaa'       : PASSED
> ''           vs. ''          : FAILED
> Segmentation fault
> 
> I've tried to write a more robust variant:
> 
> /*
>  * The strrstr() function finds the last occurrence of the nul terminated
>  * substring needle in the nul terminated string haystack. The terminating
>  * nul characters  or NULL pointers are  not compared.
>  */

Why is it important to work with NULLs?
E.g. strlen would SEGV on NULL.

Mine version is:

char* strrstr(const char *haystack, const char *needle)
{
        char *r = NULL;

        if (!needle[0])
                return r;
        while (1) {
                char *p = strstr(haystack, needle);
                if (!p)
                        return r;
                r = p;
                haystack = p + 1;
        }
}

# ./a.out
'baaabaaab'  vs. 'aaa'       : PASSED
'baaabaaaab' vs. 'aaa'       : PASSED
'baaabaab'   vs. 'aaa'       : PASSED
'aaa'        vs. 'aaa'       : PASSED
'aaa'        vs. 'a'         : PASSED
'aaa'        vs. 'bbb'       : PASSED
'a'          vs. 'aaa'       : PASSED
'aaa'        vs. ''          : PASSED
''           vs. 'aaa'       : PASSED
''           vs. ''          : PASSED
(cases with NULLs are not tested)

Comparing with current busybox:

function                                             old     new   delta
strrstr                                               53      42     -11

BTW, is it normal:

        ret |= !(n = (strrstr("aaa", "") == NULL));
        printf("'aaa'        vs. ''          : %s\n", n ? "PASSED" : "FAILED");
        ret |= !(n = (strrstr("", "") == NULL));
        printf("''           vs. ''          : %s\n", n ? "PASSED" : "FAILED");

"" needle definitely CAN be found in (any) haystack. Why we return NULL?!
--
vda



More information about the busybox mailing list