EXOTIC SILICON
“A faster way to find nothing - strchrnul()!”
Adding a new string function to libc
Missing strchrnul() on your OpenBSD system?
Tired of cumbersome workarounds using strcspn()?
Solution: add strchrnul() to libc!
INTRODUCTION
What is strchrnul(), anyway?
The libc functions strchr() and strcspn() are the most obvious to use when searching for a particular character in a string, depending on whether the calling code can most easily use a pointer to the character location, (strchr()), or a simple byte offset, (strcspn()).
However, in some cases when a pointer to a string is desired, (even if that string is of zero-length), the fact that strchr() returns a discrete NULL pointer when the searched-for character is not found is less than convenient.
Other systems often implement strchrnul(), a similar function to strchr(), but which returns a pointer to the terminating NUL if the searched-for character is not present in the string.
DOWNLOADS AND CHEAT SHEET
Immediate gratification without learning the technicalities!
JUST WANT THE CODE?
If you're not interested in the technical discussion, then follow this cheat sheet to get our pre-prepared patchset up and running:
First, download the patchset to a convenient directory using this download link.
The patchset is signed with our signify key, which should be placed in /etc/signify/ if you don't already have it installed.
Finally, apply the patchset, install an updated header file, compile and install libc, and update the manual page database:
# cd /usr/src/
# signify -Vep /etc/signify/exoticsilicon.pub -x $DOWNLOAD_DIR/strchrnul_patchset_7.8.sig -m - | patch -p0
# cp -p include/string.h /usr/include/
# cd lib/libc
# make clean
# make obj
# make
# make install
# makewhatis
Now you're ready to use strchrnul() in userland programs!
Also included in the archive are an updated manual page for strchr() and some regression tests.
ALTERNATIVES TO STRCHRNUL()
Workarounds using strcspn(), strchr(), and strlen()
Without a native implementation of strchrnul(), there are various ways to get the same result.
The most simple is by using strcspn() together with some pointer arithmetic:
strchrnul(bar, 'X')
With strchrnul()
bar + strcspn(bar, 'X')
Without strchrnul()
Another alternative is to use strchr(), then test for NULL and in that case add the length of the string to reach the terminating NUL:
strchrnul(bar, 'X')
With strchrnul()
foo = strchr(bar, 'X');
if (foo == NULL)
foo = bar + strlen(bar);
Without strchrnul()
POTENTIAL PITFALLS
Reasons not to use these simple workarounds
Unfortunately, not only are the approaches described above somewhat error prone, they are also not usually very efficient.
The first workaround using strcspn() is conceptually simple, and we might naively assume that the performance of strcspn() would be similar to that of strchr().
In fact, it's not. This is hardly surprising, since the second argument to strcspn() is another string, rather than a single value.
If we discard strcspn() as an almost drop-in replacement for strchrnul(), due to strcspn() not being particularly good for performance, the other obvious workaround is the combination of strchr() and strlen().
This apparently more complicated approach has more potential, especially if the length of the string is already known and we can avoid the call to strlen().
But in reality, the 'C' implementation of strchr() on OpenBSD is still a simple byte by byte comparison.
Potential performance compared with a native 'C' implementation of strchrnul() is further constrained by the very difference between the two functions. Whereas strchrnul() returns the same value, (a pointer to the current search position in the string), regardless of whether it finds the requested character or the NUL terminator, strchr() has two separate conditionals to evaluate, with a different result being returned for each one.
Knowing all this, we can presume that even an unoptimised 'C' implementation of strchrnul() will likely slightly outperform either of the two alternative approaches already mentioned.
ASSEMBLER OPTIMISATIONS
Possible performance gains
Provision is made within libc to optionally implement a subset of the functions directly in assembly.
This is architecture dependent, and typically the functions in question are implemented as both 'C' versions, (which can be used on any architecture), and native assembly versions for one or more specific architectures.
Native assembly versions are usually expected to be faster than the 'C' implementation, (sometimes considerably faster).
As of OpenBSD 7.8-release:
However, simply implementing the same byte by byte comparison logic that the 'C' version uses directly in assembly won't necessarily provide a significant speed increase.
The only architecture for which the logic of the assembler version differs significantly to that in the 'C' version is amd64.
Indeed, on amd64, the strchr() and strlen() functions are considerably faster than they would be without native hand optimisation.
It's most likely that the combination of strchr() + strlen() on amd64 would outperform an unoptimised 'C' implementation of strchrnul() such at the one presented in this article.
But of course, strchrnul() could also be implemented in hand optimised assembler at a later date, thereby regaining a performance advantage.
Interestingly, build system references to strcspn() are included in the architecture specific libc makefiles rather than in the relevant machine independent makefile, despite this function only being implemented in 'C'.
Presumably at some point implementing one or more assembly versions was considered, but as of the latest release all architectures still use the 'C' version.
IMPLEMENTING STRCHRNUL()
The real solution
An actual basic implementation of strchrnul() in C is trivial:
char * strchrnul(const char * p, int c) {
for ( ; ; p++)
if (*p == (char)c || *p == 0)
return ((char *)p);
}
The code simply checks each byte in sequence until it finds either the specified character or the NUL terminator, 0x00.
More advanced and potentially much faster techniques exist, but for an initial implementation and testing within userland programs, the code above is more than adequate.
ADDING THE NEW FUNCTION TO LIBC
Step by step!
Actually adding the new function to libc involves several steps.
First, we put the code we saw above in a new file, src/lib/libc/string/strchrnul.c.
Critically, we also need to make two additions to it:
#include <string.h>
char * strchrnul(const char * p, int c) {
for ( ; ; p++)
if (*p == (char)c || *p == 0)
return ((char *)p);
}
DEF_STRONG(strchrnul);
Next, we need to add the function prototype to src/lib/include/string.h:
char * strchrnul(const char *, int)
Note that this line should be added within #if __BSD_VISIBLE until such time as strchrnul() is included in a specific published standard recognised by OpenBSD.
The modified version of this file should also be installed in /usr/include/:
# cp /usr/src/include/string.h /usr/include/
Back in the libc source, we need to update another header file, this time src/lib/libc/hidden/string.h:
PROTO_NORMAL(strchrnul);
Next, add strchrnul.c to the makefile in src/lib/libc/string/Makefile.inc.
SRCS += strchrnul.c
Top tip!
Writing your own functions with architecture specific code
If you intend to write different versions of a function for different architectures, (typically assembler versions), then don't add a reference to the source file in this makefile.
Instead, add a reference to the relevant architecture specific source file in every one of the architecture specific makefiles, which are found in src/lib/libc/arch/*/Makefile.inc.
For architectures that do not have an assembler implementation of your function:
You will generally have a reference to function_name.c, which is a common file shared between all such architectures, and stored in src/lib/libc/string/, (assuming that it's a string function).
For architectures that do have an assembler implementation of your function:
You will generally have a reference to function_name.S, which exists as a unique file for each such architecture, and is stored in src/lib/libc/arch/*/string/, (again, assuming that it's a string function).
Finally, we add strchrnul() to the symbol list in src/lib/libc/Symbols.list:
strchrnul
At this point, we're done modifying the libc code.
COMPILING LIBC
... and installing it!
Compiling and installing libc is straightforward:
# cd /usr/src/lib/libc
# make clean
# make obj
# make
# make install
If you're using our patchset, note that it includes an update to the manual page.
Since the manual page for strchrnul() is just a link to a modified version of the strchr() manual page, you'll need to run 'makewhatis' to ensure that the link is made between the two:
# makewhatis
The recompiled libc, including strchrnul(), is now ready for use!
Top tip!
Regression tests
Whenever a new function is added to libc, it's good practice to create a set of regression tests that exercises it in various ways. This helps to ensure that any future changes don't unexpectedly break the functionality.
Our patchset includes a basic set of regression tests for the newly added strchrnul() function.
SUMMARY AND FUTURE ENHANCEMENTS
A resume of what we've seen today, and ideas for the future
Today we've seen how to add a new string function to libc.
This implementation of strchrnul() is intended as a proof of concept and an opportunity to test use of the function in userland code. As such it is optimised for code clarity rather than performance.
Nevertheless, real-world performance is improved over the common strcspn() with pointer arithmetic approach.