209499 - convert PL_str* impls to use ANSI C equivalents

Status: RESOLVED FIXED

(NSPR :: NSPR, defect)

Description

[Aaron Lehmann]

NSPR includes many string functions that are redundant: PL_strlen, PL_strcat,
...{cpy,ncpy,ncat,strpbrk}, etc. are all implementations of functions provided
by the C standard. There are many advantages to using the standard functions.
Not only do C libraries often provide assembly-optimized versions, but some
compilers are able to inline optimised standard string functions when they
decide that it is appropriate.

I am replacing uses of the functions provided by the C standard with the
standard versions. If this is an unwanted change, please mark this bug INVALID.
Functions where NSPR is necessary for portability, such as the PL_strdup and
PL_str[n]case{cmp,str} family, are preserved. I am also changing calls to
PL_strfree() into normal free() calls, since that's all PL_strfree() does. This
is because I don't expect PL_str* code to change its memory allocation scheme,
seeing that it already seems somewhat deprecated. Anyway, it's easy for me to
undo the removals of PL_strfree calls if that's what the reviewer wants.

The nsCRT::str* functions that take const char* arguments are also a target, but
I haven't gotten to those yet.

Comment 1

[Aaron Lehmann]

Attachment: First stab

This does the conversion in the following subdirs: netwerk layout caps content
directory dom editor ipc js xpinstall

More to come if people like this.

Comment 2

[Christian :Biesinger (don't email me, ping me on IRC)]

>I am also changing calls to
>PL_strfree() into normal free() calls, since that's all PL_strfree() does. This
>is because I don't expect PL_str* code to change its memory allocation scheme,

I don't think that you should make assumptions about NSPR's memory allocator.

Comment 3

[timeless]

Comment on attachment 125712 [details] [diff] [review]
First stab

indeed PL_strfree is *not* equivalent to free. it's explictly for PL_strdup, if
you're replacing the PL_strdup then you can (must) change the PL_strfree at the
same time. otherwise please leave it alone.

Comment 4

[Aaron Lehmann]

Attachment: v2

Fair enough.

Comment 5

[[e-mail]]

Index: netwerk/protocol/http/src/nsHttpTransaction.cpp
===================================================================
-            char *p = PL_strchr(PL_strchr(buf.get(), ' ')+1, ' ');
+            char *p = strchr(PL_strchr(buf.get(), ' ')+1, ' ');

looks like you missed one there.

Comment 6

[[e-mail]]

This won't work in all cases - you can't blindly replace PL_str* functions with
ANSI C equivalents, because the PL_str* family is nullsafe. ANSI C string
functions are not. We probably rely on this behavior in many cases.

The PL_str* implementations are definitely slower than the ANSI C ones, so it
would be nice to do something here; perhaps we could redefine the PL_str*
functions to be nullsafe wrappers around ANSI counterparts? Then, consumers that
don't need nullsafety could be converted later, but that's a laborious task
since each occurrence needs to be checked by hand.

Comment 7

[Darin Fisher]

what dwitte said.  instead of trying to manually replace all PL_strlen with
strlen, let's try to change the implementation of PL_strlen instead ;)

i'm not sure that NSPR will want to change the definitions of these functions
since they are designed to work with really ancient operating systems that often
don't follow ANSI C in very subtle ways.  cc'ing wtc for his input.  it seems
like it should be safe to make PL_strlen a macro on platforms that have a good
strlen.  e.g., strlen is a single CPU instruction on ix86.

same applies to other string routines (like PL_strchr in particular).

Comment 8

[Wan-Teh Chang]

The PL_str functions must remain functions for binary
compatibility.  We can change their implementations to
call the corresponding str functions.  Then the only
optimization you lose is the inlining of the str functions.

Comment 9

[[e-mail]]

Do we know of any platforms where the ANSI functions are broken or inconsistent?
Or should we just forge ahead and do this for all platforms?

Which functions must remain with their NSPR implementation (Aaron mentioned
PL_strdup and PL_str[n]case{cmp,str}, where did this list come from)?

Once these are answered, I guess we just need someone to do the typing. ;)

Comment 10

[Wan-Teh Chang]

It is safe to do this for all platforms.

The functions that must remain with their NSPR implementation
are those that are not in the Standard C Library.

Comment 11

[timeless]

You probably confused strdup w/ strndup. strndup, strcasecmp, and strcasestr aren't part of the standard.

Comment 12

[Aaron Lehmann]

The manpage for strdup I have here says:

CONFORMING TO
       SVID 3, BSD 4.3.  strndup(), strdupa(), and strndupa() are  GNU  exten-
       sions.

Notice no ISO conformance. But it's dated 1993...

Comment 13

[Wan-Teh Chang]

We should assume that only the str* functions listed
in The C Programming Language, 2nd Ed., are
universally available at present.  strdup is not one
of them.

Comment 14

[[e-mail]]

according to an ANSI C reference i found, the following functions are provided:

strlen
strcpy
strncpy
strcat
strncat
strcmp
strncmp
strchr
strrchr
memcpy
memmove
memcmp
memchr
memset

if this list is incorrect for our purposes, please correct me. ;)

Comment 15

[[e-mail]]

add the following to the above list:

strspn
strcspn
strpbrk
strstr
strtok

Comment 16

[Darin Fisher]

dwitte: avoid ANSI C strtok... nsCRT::strtok is better ;)

Comment 17

[[e-mail]]

i definitely will be, since ANSI C strtok isn't threadsafe at all :)

so i've got a first-cut patch for nspr to convert pretty much everything i can
over to ANSI C... coming right up!

Comment 18

[Christian :Biesinger (don't email me, ping me on IRC)]

aren't nspr PR_str* functions null-safe, contrary to ANSI C ones?

Comment 19

[[e-mail]]

Attachment: first-cut nspr patch

so this changes most of the nspr string functions to use libc... pretty much
first-cut at this point, to see what wtc and other folk think.

it keeps binary and API compatibility untouched. i've measured a 3.1%
improvement in Txul with this patch (linux gtk2, gcc 3.3.2). i'm unable to
measure Tp at this point.

Comment 20

[[e-mail]]

Comment on attachment 135490 [details] [diff] [review]
first-cut nspr patch

wtc, what do you think? :)

Comment 21

[[e-mail]]

oh, one note, about the comment

/* error checking in case we have a 64-bit platform -- make sure we dont
 * have ultra long strings that overflow a int32
 */

in strlen.c. the reason i removed the assertion here is that it doesn't seem to
be implemented consistently in any of the other PL_str* functions that deal with
int32's in an unsafe fashion - so, i chose to be consistent and drop it
altogether, rather than making a mess of the string functions. comments on this
approach are welcome.

Comment 22

[[e-mail]]

Attachment: second-cut nspr patch

err, ignore that... nspr's handling of int32 overflows was perfectly correct.

this patch fixes up that part for 64-bit platforms, by using PRSize rather than
PRUint32 when dealing with ANSI C functions.

Comment 23

[[e-mail]]

Nit: if you're going to keep nspr's wacky if ((char *)0 == tests, you should do
so for your ?: tests too. Also, some || return consistency would be nice.

Comment 24

[Darin Fisher]

Comment on attachment 135491 [details] [diff] [review]
second-cut nspr patch

some review comments (from me hoping to help this patch along)...

>Index: nsprpub/lib/libc/src/strcat.c

> PL_strncat(char *dest, const char *src, PRUint32 max)
...
>+    char *end = strchr(dest, '\0');
>+    (void)strncpy(end, src, (PRSize)max);

nit: s/PRSize/size_t/ ??

i know this shouldn't matter, but isn't size_t likewise part of ANSI-C?
this nit applies throughout the patch...


> PL_strcatn(char *dest, PRUint32 max, const char *src)
> {
>+    if( ((char *)0 == dest) || ((const char *)0 == src) )
>+        return dest;
> 
>+    PRSize dl = strlen(dest);
>+    PRSize n = (PRSize)max - (dl + 1);
>+    if( n > 0 )
>+    {
>+        char *end = dest + dl;
>+        (void)strncat(end, src, n);
>+    }

this looks fishy to me.  suppose:

  dest -> "xyz"
  max  -> 5
  src  -> "abc"

the expected result is: "xyza" (null terminated)

with this code:

  dl  -> 3
  n   -> 5 - 3 - 1 -> 1
  end -> dest + 3 -> "" (pointing at the null terminator)

strncat would basically copy one byte from src to end and that's it.
i believe the result would not be null terminated because strncat
does not guarantee null termination.  in fact, it only null terminates
if the selected range of src data ends with a null terminator.

i recommend keeping the existing code that calls PL_strncpyz.


>Index: nsprpub/lib/libc/src/strchr.c

> PR_IMPLEMENT(char *)
> PL_strnchr(const char *s, char c, PRUint32 n)
> {
>+    if( ((const char *)0 == s) ) return (char *)0;
> 
>+    const char *end = (const char *)memchr(s, '\0', (PRSize)n);
> 
>+    return (char *)memchr(s, c, end ? end - s + 1 : (PRSize)n);
> }

this might be clearer:

    /* do not search beyond a null terminator if one exists */
    const char *end = (const char *) memchr(s, '\0', (size_t)n);
    if (end)
	n = end - s + 1;
    return (char *)memchr(s, c, (size_t)n);


>Index: nsprpub/lib/libc/src/strcpy.c

> PL_strncpy(char *dest, const char *src, PRUint32 max)
...
>-#ifdef JLRU
>-    while( --max )
>-        *++dest = '\0';
>-#endif /* JLRU */

what's up with this ifdef?  do we need to preserve it?	wtc?


> PL_strncpyz(char *dest, const char *src, PRUint32 max)
...
>+    if( ((char *)0 == dest) || ((const char *)0 == src) ) return (char *)0;

nit: elsewhere you have put the return statement on a new line -- be consistent
;)
i think the return on the same line is the prevailing style fwiw.


>Index: nsprpub/lib/libc/src/strdup.c

> PL_strdup(const char *s)
> {
>     char *rv;
> 
>     if( (const char *)0 == s )
>+    {
>+        rv = (char *)malloc(1);
>+
>+        if( (char *)0 != rv )
>+            *rv = '\0';
>+    }
>     else
>+    {
>+        rv = (char *)malloc(strlen(s) + 1);
>+
>+        if( (char *)0 != rv )
>+            (void)strcpy(rv, s);

it would be more efficient to not compute strlen twice.  like this:

   size_t n = strlen(s) + 1;

   rv = (char *)malloc(n);

   if( (char *)0 != rv )
       (void)memcpy(rv, s, n);


> PL_strndup(const char *s, PRUint32 max)

i think the old code for this function might have been better.	it
is certainly more compact.  i'm not sure what benefit is to be had
by reimplementing this function.

Comment 25

[[e-mail]]

thanks for the comments darin! re the stylistic mess... yeah, i should tidy it
up a bit more. partly i couldn't be bothered until wtc says what style he'd
prefer (that goes for size_t as well) :)

>with this code:
>
>  dl  -> 3
>  n   -> 5 - 3 - 1 -> 1
>  end -> dest + 3 -> "" (pointing at the null terminator)
>
>strncat would basically copy one byte from src to end and that's it.
>i believe the result would not be null terminated because strncat
>does not guarantee null termination.  in fact, it only null terminates
>if the selected range of src data ends with a null terminator.

hmm, are you sure? my reference for strncat says that it copies up to n chars
(where n is the 3rd arg), and _then_ nullterminates. maybe you're confusing it
with strncpy, which behaves how you describe?

so it would copy one byte from src to end, and then nullterminate as expected.
http://www.mkssoftware.com/docs/man3/strncat.3.asp

>it would be more efficient to not compute strlen twice.

yup, just a late-night goof. Neil pointed that out and i've made the change
locally :)

>i think the old code for this function might have been better.

sure... i just felt like inlining as much as possible, since codesize isn't
important for these tiny functions. i can change it back.

>this might be clearer:

agreed :)

Comment 26

[Darin Fisher]

here's the MAN page entry:

       The  strcat()  function appends the src string to the dest string over-
       writing the ‘\0’ character at the end of dest, and then adds  a  termi-
       nating  ‘\0’  character.   The  strings  may  not overlap, and the dest
       string must have enough space for the result.
 
       The strncat() function is similar, except that only the first n charac-
       ters of src are appended to dest.

so, yeah... hmm... it isn't exactly clear.  does "similar" mean similar in that
it also null terminates?  maybe there is a better reference for strncat somewhere?

Comment 27

[Wan-Teh Chang]

Comment on attachment 135491 [details] [diff] [review]
second-cut nspr patch

I reviewed this patch last weekend.  I didn't finish it.

This patch must be reviewed with extreme care.	It is very
easy to introduce off-by-one errors when working on character
strings.

Some of the changes are obviously correct (for example, those
that handle null pointer arguments and then simply call the
libc equivalents) and can be checked in first.

Comment 28

[Markus Hübner]

Can we check in some of that?

Comment 29

[[e-mail]]

wtc, any chance you can take a look at this patch sometime? (or if you'd rather
some of the changes wait for further review/testing, could you indicate what
you'd be happy with?)

thanks!

Comment 30

[Wan-Teh Chang]

Comment on attachment 135491 [details] [diff] [review]
second-cut nspr patch

Dan,

Sorry about the delay.	I reviewed this patch
before but forgot to write my comments here.

One reason for the delay is that some of the
changes in this patch have a high risk of
introducing off-by-one bugs.  The strategy
I have in mind is to check in the other
low-risk changes first.

Comment 31

[Wan-Teh Chang]

Attachment: safest changes (PL_strxxx checks for null pointers and then calls strxxx)

These are the safest changes in dwitte's "second-cut nspr patch".
I will check these in first.

I only made some minor changes:
1. I changed PRSize to size_t.
2. In PL_strstr, I restored the checks for empty strings because
   if 'little' is an empty string, PL_strstr returns (char *)0
   whereas strstr returns 'big'.
3. The change for PL_strlen can't declare 'l' in the middle of
   the function (this is C code).

Comment 32

[Wan-Teh Chang]

Comment on attachment 146924 [details] [diff] [review]
safest changes (PL_strxxx checks for null pointers and then calls strxxx)

Dan, please at least review my change to your
patch for PL_strstr.

Comment 33

[Wan-Teh Chang]

Attachment: safest changes (PL_strxxx checks for null pointers and then calls strxxx)

I removed the patch for PL_strncpy from this set
because I noticed a subtle difference between
PL_strncpy and strncpy in the padding of null bytes
if the 'src' string has less than 'max' chars.
(See the code in PL_strncpy ifdef'd with JLRU.)

Comment 34

[Wan-Teh Chang]

Attachment: remaining changes

Comment 35

[Bernard Alleysson]

Comment on attachment 146930 [details] [diff] [review]
remaining changes

after bug 94580, while you're touching strdup.c, you could replace

+    {
+	 rv = (char *)malloc(strlen(s) + 1);
+
+	 if( (char *)0 != rv )
+	     (void)strcpy(rv, s);
+    }

by

+    {
+	 size_t l;
+
+	 l = strlen(s) + 1;
+	 rv = (char *)malloc(l);
+	 if( (char *)0 != rv )
+	     (void)memcpy(rv, s, l);
+    }

Comment 36

[[e-mail]]

Comment on attachment 146929 [details] [diff] [review]
safest changes (PL_strxxx checks for null pointers and then calls strxxx)

looks like a good start, thanks wtc!

r=dwitte

Comment 37

[Darin Fisher]

Comment on attachment 146929 [details] [diff] [review]
safest changes (PL_strxxx checks for null pointers and then calls strxxx)

We should ensure that we are compiling with -O2 under GCC (in release builds)
to ensure that the inline assembly code for many of these functions is used.

NOTE: if compiled with -Os, then none of these will be expanded to inline
assembly.  the result might not be so good due to the function call overhead
(extra jumps through PLT on ELF, for example).

Comment 38

[[e-mail]]

back when i wrote this patch, i tested using #define __USE_STRING_INLINES... it
didn't seem to make any difference in perf (Txul), compared to non-inline (see
comment 19). (aside: it's also possible to achieve inlining with -Os, by
#undef'ing __OPTIMIZE_SIZE__, in the .c files of interest.)

the probable reason for this is that, for glibc on linux (my test platform), the
inline versions of the string functions (where they exist) are _not_ the same as
the non-inline versions that get used normally. they are more compact for
codesize reasons, which generally means they're slower, and they're only
provided for one arch iirc... so, the inline versions will always be written in
a compact i386 asm, whereas the noninline ones might be a faster i486/i686 asm.

unfortunate that glibc still worries about consumer codesize even when you
specify to use inlines... it'd be nice if it gave the consumer that choice. ;)

Comment 39

[Wan-Teh Chang]

Attachment: wtc's second patch

I've reviewed all the remaining changes.  Here
are the changes that I think are okay.	The only
substantial changes are in strdup.c (which I rewrote
to handle a null pointer as an empty string and to
use memcpy to copy strings) and strstr.c.

I will explain next why the other changes are not
accepted.

Comment 40

[Wan-Teh Chang]

Attachment: remaining changes

Comments on the remaining changes.

1. The patches for PL_strncat, PL_strncpy, and
PL_strncpyz are wrong.

PL_strncat, PL_strncpy: PL_strncpy and strncpy are
not interchangeable because strncpy always stores
'max' characters in the 'dest' buffer while
PL_strncpy terminates after copying the null
character.

PL_strncpyz: this statement is wrong:
    dest[--max] = '\0';
because the 'dest' buffer is not guaranteed to
be 'max' character long.

2. The patch for PL_strcatn may be okay.  Are
you sure the new code is faster than the old
code?

3. As for the other changes, it is not obvious
that the new code is faster than the old code.

I am not sure that

    r = (const char *)memchr(s, '\0', (PRSize)max);

is faster than

    for( r = s; max && *r; r++, max-- )
	;

or

    r = strchr(s, '\0');

is faster than

    for( r = s; *r; r++ )
	;

My gut feeling is that we won't get perceivable
application performance gain with these changes.
The effort to review these changes and to prove
that the new code is faster than the old code
may not be worthwhile.

Comment 41

[Wan-Teh Chang]

Comment on attachment 147481 [details] [diff] [review]
remaining changes

I also want to comment on the patch for
PL_strnchr.  I am not sure if the new code
(two memchr calls) is faster than the old
code (a single for loop).

Comment 42

[Wan-Teh Chang]

I've checked in the patches "safest changes" and
"wtc's second patch" on the NSPR tip (NSPR 4.6)
and NSPRPUB_PRE_4_2_CLIENT_BRANCH (Mozilla 1.8
alpha).

I've obtained Dan Witte's agreement that we do
not check in the remaining changes.

I'd like to thank Dan for contributing a high-quality
patch.  I am impressed that he followed the coding
style of the original author exactly.