strcpycat2012-01-08
This is a look at the various means in C to copy strings, and their safety and performance implications. What is surprising is that all of the available implementations, even the venerable *BSD strl functions have serious issues.
To preface, I am only going to cover null-terminated strings, because that is what the libc runtime, which is the foundation that every language ultimately reaches down to in the end, is built around.
I will also cover a new proposed alternative to address the problems I've mentioned at the end of this article.
Note: to be clear, when I speak of O(n^2) overhead, I am referring to multiple successive calls to these functions: not a single call. Such situations are common in lexical analysis.
char* strcpy(char *target, const char *source);
char* strcat(char *target, const char *source);
Ah, the venerable libc standard functions. They're fast, but have the very obvious problem that you can easily overflow your target buffer if the source buffer is larger.
This has been done to death, so let's move on to the safer variants.
char* strncpy(char *target, const char *source, unsigned length);
char* strncat(char *target, const char *source, unsigned length);
These were initially created for handling UNIX filenames long ago. They were meant to be used on relatively small buffer sizes.
Nowadays, they are often proposed as safer variants. These functions take the size of your target string, but they still have a few problems.
strncpy
The first is a performance problem. If the target string is longer than the source string, it will continue to be padded with zeroes. For a relatively large target buffer, this can present an O(n^2) overhead for string building, if it were to be called multiple times.
The second is a safety problem. If the target is shorter than the source string, it is not null-terminated. Attempting to pass this unterminated string around can easily lead to out-of-bounds memory accesses.
The third problem is one of convenience versus safety: the length is not the actual size of the object, but rather the number of characters accessible in it. Although this is convenient for literal integers, it makes passing sizeof target when you have char target[] write one byte out of bounds.
strncat
Seemingly belonging to a different family entirely, strncat operates very differently. Unlike strncpy, it does not fill remaining bytes with null values, and it also will always add a final null terminator to the target string, even if that means writing one byte past the size you passed the function.
signed strlcpy(char *target, const char *source, unsigned length);
signed strlcat(char *target, const char *source, unsigned length);
The OpenBSD project, unsatisfied with the performance issues of the strn functions, created the strl functions with their own performance issues.
On the plus side, it correctly uses length to denote the actual size of the entire string object in memory. It also always ensures that the target string is null-terminated, so long as length > 0.
However, it suffers from feature-creep. The return values in this case are
not the output strings, but instead some rather non-sensical values.
(Note: I am sure they serve a legitimate purpose, just not a commonly used one.)
For strlcpy(), the return value is equal to strlen(source). For strlcat(), the return value is equal to strlen(source) + min(length, strlen(target)). To directly quote the OpenBSD documentation, "While this may seem somewhat confusing, it was done to make truncation detection simple." Er, somewhat?
I suppose it can be useful to know if you did not copy the entire buffer, but knowing exactly how many bytes remain is not entirely useful. An alternate usage of this would be to skip strlcat() for another strlcpy(), but the syntax is odious, to say the least:
signed n = strlcpy(target, source1, sizeof target); signed o = strlcpy(target + n, source2, sizeof target - n); signed p = strlcpy(target + n + o, source3, sizeof target - n - o); ...
I fully acknowledge the benefits of bypassing strlcat()'s need to compute the target string length in preventing O(n^2) overhead; but the cpy/cat functions really weren't meant for this sort of optimization. A large volume of string concatenations deserves its own specialized function that can write to the target and length parameters as it goes along (eg unsigned* or unsigned&.)
What's worse, is that this frivilous, rarely-used feature creates a rather significant performance bottleneck.
When tokenizing an input string, say XML or CSV data, one has to copy chunks of data from the source to the target, but the source is not actually null-terminated in this instance. The strlcpy() function would be great for this purpose, except you run into the problem that it runs over the entire length of your source string to calculate its length for the return parameter.
So if you have a 20MB file with one million evenly-sized tokens, the first 500,000 tokens will run over ~15MB of data per call to strlcpy(). So once again, you are stuck with O(n^2) performance.
Now, arguably, the length parameter is supposed to be the actual size of the target — I understand that. However, it's an artificial limitation that cripples an otherwise very useful and common feature; in exchange for a not-so-common one.
Worse, this performance penalty also affects legitimate uses. Say you have a 20MB source string, and you wish to read the first few bytes to determine something about it. The strlcpy() will traverse the entire source string anyway, even though your target string is only a few bytes long.
Further, by not being able to clamp the source length properly, you must ensure the source string is properly null-terminated or this function could also access out-of-bounds memory.
The best way to think of the strl family is to consider the l to stand for len; because you get an extra mandatory strlen() for every call.
errno_t strcpy_s(char *target, unsigned length, const char *source);
errno_t strcat_s(char *target, unsigned length, const char *source);
These are ridiculous Microsoft contraptions. Overlapping source and target strings lead to undefined behavior. Implying that a straight memcpy() is used internally, which means there is no way to limit the read length of the source string. In that instance, if the source is smaller than your length parameter, it will read out-of-bounds on the copy.
The return type is also wasted on nonsensical codes.
void* memcpy(void *target, const void *source, unsigned length);
Okay, this one's not technically a string copy function. But to stave off potential questions ... yes, one could use memcpy() to perform the tokenization I discussed in the strlcpy() function. However, this is also unsafe: it will not stop copying from source after a null-terminator is found.
So at this point, we are doing pretty bad. Every single function has the potential to access out-of-bounds memory. We need a solution, so I propose the following:
Replacement Proposal : strmcpy(), strmcat()
The core concept is defined in strmcpy() and strmcat(). The functions are three lines or less; but don't let the size fool you, they are quite powerful.
//return = strlen(target)
unsigned strmcpy(char *target, const char *source, unsigned length) {
const char *origin = target;
if(length) { while(*source && --length) *target++ = *source++; *target = 0; }
return target - origin;
}
//return = strlen(target)
unsigned strmcat(char *target, const char *source, unsigned length) {
const char *origin = target;
while(*target && length) target++, length--;
return (target - origin) + strmcpy(target, source, length);
}
Like the strl family, strm's length parameter includes the null-terminator. This allows usage of sizeof target, as well as zero-byte lengths which will not write to the target.
Unlike the strl family, we return the length of the target string instead. This still allows us to easily detect incomplete copies, as you will see below. This also avoids any potential for O(n^2) complexity.
We also stop transferring when the source string is terminated. Further, using the length parameter as the source size (or target size, or both) is fully supported.
Here is how we can use the length argument:
strmcpy(target, source, sizeof target); //transfer as much of source as possible strmcpy(target, source, 6); //copy up to 5-bytes + null-terminator to target strmcpy(target, source, min(sizeof target, 6)); //same as above, but also bound-limit target
And here is how we can perform multiple appends in O(n) time:
unsigned p = 0; p += strmcpy(target + p, source1, sizeof(target) - p); p += strmcpy(target + p, source2, sizeof(target) - p); p += strmcpy(target + p, source3, sizeof(target) - p);
If target already contains data, we only have to use strmcat() once:
unsigned p = strmcat(target, source1, sizeof(target)); p += strmcpy(target + p, source2, sizeof(target) - p); p += strmcpy(target + p, source3, sizeof(target) - p);
Helper Functions
We can easily detect overflow with these simple wrappers:
//return = true when all of source was copied
bool strccpy(char *target, const char *source, unsigned length) {
return !source[strmcpy(target, source, length)];
}
//return = true when all of source was copied
bool strccat(char *target, const char *source, unsigned length) {
while(*target && length) target++, length--;
return !source[strmcpy(target, source, length)];
}
Usage example:
while(strccat(target, source, length)); //keep appending source until target is exhausted if(!strccpy(target, source, length)) handle_incomplete_copy();
We can also reduce the red-tape necessary for multiple successive appends:
//return = reserved for future use
void strpcpy(char *&target, const char *source, unsigned &length) {
unsigned offset = strmcpy(target, source, length);
target += offset, length -= offset;
}
This can be used like so:
char *p = target; unsigned length = sizeof target; strpcpy(target, source1, length); strpcpy(target, source2, length); strpcpy(target, source3, length);