4 ms·
So why insist on this NUL termination business? I expected this to be necessary in C libraries due to legacy code but the kernel can always do whatever it wants
by matheusmoreira 4y ago
So why insist on this NUL termination business? I expected this to be necessary in C libraries due to legacy code but the kernel can always do whatever it wants internally.
struct bytes { size_t size; unsigned char *pointer; };
Seems simple enough... A little structure like that has always been useful in my projects.
I find myself agreeing with the glibc maintainer in the extended discussion linked from the article:
https://lwn.net/Articles/612244/ https://lwn.net/Articles/612244/
> Correct string handling means that you always know how long your strings are and therefore you can you memcpy (instead of strcpy).
I think he's absolutely right. The str* functions are just worse versions of the mem* functions.
- _8j50 4y agoCan you imagine the conversion effort?
- XorNot 4y agoI can imagine it's not been analysed so we're all assuming it's just "impossible". Sometimes you just need to do the boring work so it's done. The Linux kernel is one of the most important pieces of software on the planet - limiting it's performance and safety due to C's string handling legacy is madness.
- _8j50 4y agoHave you read the article? Linus' resistance to auto-conversion means one or a few people can't do it, every maintainer has to do a project involving many orgs and thousands of people over several years. It is not impossible, it takes time but it is doable, the question is is this the best way to solve the underlying issue (and what exactly is that?) ? Assuming of course the NUL replacement is backwards compatible in some way, if not then I say focus on migrating to Rust instead.
- JdeBP 4y agoM. Torvalds never expressed an objection to auto-conversion. Xe expressed an objection to mass conversion, with patches that mass change function calls with little scrutiny and even less actual regression testing of all of the affected code paths. Because xyr past experience was that that was what happened in practice, and stuff broke as a consequence.
- pwdisswordfish9 4y agoWho is M. Torvalds? I am not aware of anyone with first initial M. named Torvalds that is relevant to this discussion and would require such bizarre pronouns to be applied to them.
- quickthrower2 4y agoThe M is believe is a gender neutral title. And ze a gender neutral pronoun.
- duskwuff 4y ago> So why insist on this NUL termination business? It's inherent to the language. Writing "string" gives you a NUL-terminated string; converting that to another format takes effort. Interestingly, some Mac OS compilers would let you write "\pABC" to get a structure containing the bytes {3, 'A', 'B', 'C'}. (The "p" stands for Pascal.)
- matheusmoreira 4y ago> It's inherent to the language. Writing "string" gives you a NUL-terminated string; converting that to another format takes effort. Couldn't we just leave the NUL byte in there and pretend it doesn't exist? const char *literal = "string literal with NUL byte"; struct bytes text; text.size = strlen(literal); // strlen doesn't count the NUL terminator text.pointer = literal; // I know I discarded the const qualifier up there, but it's just to illustrate Then a copy(text, other) function would conveniently ignore the entire NUL issue. The copy would not even have the terminating NUL. > Interestingly, some Mac OS compilers would let you write "\pABC" to get a structure containing the bytes {3, 'A', 'B', 'C'}. (The "p" stands for Pascal.) Pascal strings are nice but their sizes are too limited. Same idea as my structure above but with a uint8_t for length instead of uint64_t = size_t.
- Phelinofist 4y agoHow would that work with untrusted strings? As I understood TFA strlen() is an issue if the string is not null terminated
- matheusmoreira 4y agoThat's correct. Using strlen on anything but C string literals is just asking for bugs. The thing is untrusted strings don't come from C itself, they come from I/O. The kernel has perfectly reasonable I/O interfaces. ssize_t bytes_read = read(file_descriptor, buffer, size); ssize_t bytes_written = write(file_descriptor, buffer, size); You always know the length. Well... At least you would always know the length if the standard C library didn't abstract that perfectly good interface away behind stdio just so it could do buffering and return NUL-terminated strings. It's just like errno. The kernel simply returns a negated error constant on failure. The C standard library takes that sane interface and turns it into a thread local global variable.
- zzo38computer 4y ago> I think he's absolutely right. The str* functions are just worse versions of the mem* functions. I think they aren't "worse versions of the mem* functions"; they are different functions. The "str" functions deal with null-terminated data, "mem" functions deal with data of a specified length, and "strn" deals with whichever is shorter. Some "str" functions do not have "mem" variants (and vice-versa). For example, there is no "memdup" function.
- matheusmoreira 4y ago> they are different functions. The "str" functions deal with null-terminated data Well, yes. I say they're worse because the only reason they exist is to deal with this NUL terminator nonsense. The str* functions all reduce to the mem* functions after the string length is computed. To me it's like this: str_function = mem_function(string, strlen(string) + 1) There is no need for these functions to exist if we get rid of this NUL terminator business. > Some "str" functions do not have "mem" variants (and vice-versa). For example, there is no "memdup" function. There could easily be. For example, strdup is essentially strcpy(malloc(strlen(string) + 1), string). A memdup function would be even more efficient because the length is already known: memcpy(malloc(length), source, length).
- JdeBP 4y agoThere could easily be so much more than that. In the early 1990s, there was a popular shareware string library for C in circulation that added a whole raft of extra strXXX() functions, such as strrtrim() and strend(), to a C runtime library. All of these were useful. Indeed, they were fundamental in some other languages, e.g. some dialects of BASIC with their various string functions like MID$ and RIGHT$. But the standard C library never gained them. The strXXX() set in the C standard library is, rather, in large part an ad hoc set of useful wrappers around stuff that could be done with assembly language idioms, like REPNE SCASB on x86 instruction sets, that had grown up by 1987. The functions weren't intended to be reducible to memXXX(). They were intended to be reducible to assembly language, or even to compiler intrinsics. The sad part is that the context here is kernel code, in particular Linux kernel code, where human-readable text interfaces (as opposed to machine-parseable interfaces) are the norm. Whitespace-terminated or LF-terminated strings are the norm, in things like procfs for example, and it is a double irony that the C standard library addresses NUL termination more readily than it does those, and even then provides only an ad hoc collection of NUL-terminated string functions with long-since well-known glaring holes unsuitable for kernel code. Getting rid of the problem in the way that you suggest would necessitate redesigning a lot of kernel APIs to not be human-readable text that operates in terms of variable length strings terminated by special character values with no explicit length counters. No more redirecting the output of the "echo" command to /proc/something . This is exceedingly unlikely to happen.
- MarkSweep 4y agobstring [1] is one example of library implementing this sort of higher-level string library. I've used it in some embedded projects. The Linux kernel has data structure libraries for things like linked lists and maps. Does it really not have a higher-level string abstraction? [1] http://bstring.sourceforge.net/ http://bstring.sourceforge.net/
- zzo38computer 4y agoI think that structure will be helpful, and you can also easily pass substrings. (With null-terminated strings, you can easy cut off some characters from the beginning of the string, but not from the end. Passing both the length and the pointer together allows to easily do both, as well as allowing passing strings containing null characters.) I think that this is better than Pascal strings, due to being able to make substrings like this. (Also the structure can be passed by value (without a pointer to the structure), which also allow to easily use in other function, e.g. to convert a null-terminated string or Pascal string into this structure, without allocating additional memory.)
- nicoburns 4y agoIt boggles my mind that the C standard hasn’t officially added support for this. It seems like such a small change that would dramatically improve the quality of C code.
- nine_k 4y agoThey were afraid of the C++ situation where there are 3-4 different string implementations in every large project.
- pjmlp 4y agoHence why something like SDS should be part of the standard.
- jstimpfle 4y agoNul termination is not only in C but also in some file formats. It has some advantages - apart from modest space savings for short strings, it means that you can read a string from some given location to the end - without any out of band data (length) that necessarily has to be stored in a different, agreed on location. This is a very valuable property. I'm not saying don't use length fields, I'm saying use nul terminators where possible and use length fields where needed. And, they are not mutually exclusive. And C doesn't need a standardized length delineated string structure in my opinion. Nul terminators serve the job fine for most Standard APIs (which take only short strings), and can receive length fields as separate function parameters where required.
- snickerbockers 4y agohes wrong, correct string handling means processing the string serially one char at a time. carrying a size_t along with your strings like that is a waste of a perfectly good gpr.
- noobermin 4y agoA waste of 8 bytes?
- snickerbockers 4y agoWell technically that's implementation-defined, but yes.
- Thiez 4y ago7, since keeping track of the length allows you to skip storing the trailing 0.
- drran 4y agoIf we define `String` type as `{size_t len, size_t offset, char *data}`, then we can store up to 23 bytes directly in the struct, if we will sacrifice 1 bit of `len` field to indicate that.
- adgjlsfhk1 4y agothis was true in the 1980s, but now if you want speed, you want to use vectorized instructions, so you want to do as much work as possible 32 bytes at a time for large strings. if you don't store a length, your string processing will be an order of magnitude slower.
- cmroanirgo 4y agoIt definitely gets a bit murky when dealing with mbcs, when you want characters spanning multiple bytes rather than individual bytes. I understand the topic is strXxx() funcs which are ascii only, but it does need to be said that size!=len for wide and multi char sets.
- matheusmoreira 4y agoYeah, that's an important observation especially in today's unicode world. It just strengthens my point that these "string" functions are really just bytes/memory functions in disguise. Honestly "string" is a very harmful word that we've all grown used to. As an abstraction it sits somewhere between raw bytes and properly encoded text with proper unicode functions such as those provided by ICU. Python 3 finally forced people to start thinking about this stuff and nobody liked it.
- mort96 4y agoThe str functions aren't ASCII-only, they work perfectly fine with multi-byte strings such as UTF-8-encoded strings. The "length" just isn't the number of "characters", but the definition of a "character" itself is murky and bytes are what what you're usually interested in anyways.
- johannes1234321 4y ago> and bytes are what what you're usually interested in anyways. Bytes are relevant when I have to allocate memory otherwise some definition of "character" is often more relevant. Even if I trim text to fit in a buffer I don't want to trim inside a "character" but get the most number of fitting "characters" Now "characters" are of course complicated as grapheme clusters are what is useful the most for human interaction ... but those are quite out of scope for a "simple" string library ...
- ndesaulniers 4y agoOne thought, most targets are not built as -ffreestanding and while the kernel doesn't link against a libc, it does provide most symbols with the same semantics. This allows the compiler to perform libcall optimizations. For example, calls to printf can be transformed into calls to puts under certain conditions. The compiler can check + find those, even after optimizations. There are many of these tricks for the str* functions that assume NUL terminated C strings. Though perhaps if the mem* functions were used to implement a fat strings implementation, many of those might still apply. Point being; the compiler can help when your strings representation is first class by the language spec. The compiler can also help with FORTIFY; it can insert compile time length checks in certain cases that can make code safer. This avoids treewide rewrites which are relatively painful to do for the Linux kernel due to its development model, but not impossible. That's another barrier to a new string representation and a library of routines for these. That said, strscpy is not part of the language spec, so I'm guessing unless it's implemented in terms of language defined functions, it gets neither libcall optimizations nor fortified.
- morelisp 4y agoSo, if you want to do struct bytes { size_t size; unsigned char *data; }; now you've got two allocations (or at least two separate memory regions, or at least a pointer wasted assuming it's constant) per dynamically-allocated thing. On the other hand, if you take a more direct mirror of a Pascal string: struct bytes { size_t size; unsigned char data[]; }; You're back to one memory span but can't reslice it. And of course the worst codebase is when someone uses the first one because they want to keep slicing and someone else uses the second one because they need to save memory / indirections. To support both you end up writing functions that take a separate size and data pointer, and... well, then what's the point?
- masklinn 4y ago> now you've got two allocations (or at least two separate memory regions, or at least a pointer wasted assuming it's constant) per dynamically-allocated thing. Having a size_t on the stack is hardly an issue, it's what every low-level modern language does. It's fast, convenient, and pretty efficient. It also doesn't require deref'ing to get the length, which is a pretty common use case (e.g. checking if a string is empty, or too big, or something along those lines).
- morelisp 4y agoThat approach only works if the string isn't being mutated in a way which could change its size, though. Otherwise you need to make sure it has a lexical lifetime (and be very careful with it), or if that's not possible pay the double alloc cost. I would be also worried about any difficulties separating the length and data causes for prefetching/cache lines though. The second form is also more amenable to SSO; I'm not sure how often that would come up in the kernel but it's saved me a decent chunk of memory in at least one past project. (Still today I'm sometimes frustated by Go `string` porting from Java `String`, like great now I don't have to pay a boxing overhead but if it's often absent/empty my base size is now 2x what it would otherwise be...)
- alcover 4y ago> then what's the point? There's no point. Moreover, passing the length separately is annoying and error-prone. You can have both your models in a single type. That's what my buffer lib achieves : SSO + slicing. https://github.com/alcover/buffet https://github.com/alcover/buffet
- deleted 4y ago[deleted]
- throw0101a 4y ago> I think he's absolutely right. The str* functions are just worse versions of the mem* functions. Per Todd C. Miller (creator of strlcpy and maintainer of sudo) and Theo de Raadt (OpenBSD) in these 1999 (PostScript) slides, the simplest implementation of strlcpy() uses (can use) memcpy(): size_t strlcpy(char *dst, const char *src, size_t siz) { size_t n; size_t slen = strlen(src); if (siz) { if ((n = MIN(slen, siz - 1))) memcpy(dst, src, n); dst[n] = ’\0’; } return(slen); } * https://www.openbsd.org/papers/strlcpy-slides.ps https://www.openbsd.org/papers/strlcpy-slides.ps The current OpenBSD is currently different: * https://github.com/openbsd/src/blob/master/lib/libc/string/strlcpy.c https://github.com/openbsd/src/blob/master/lib/libc/string/s... * https://cvsweb.openbsd.org/src/lib/libc/string/strlcpy.c https://cvsweb.openbsd.org/src/lib/libc/string/strlcpy.c One problem with memcpy() is that it returns (void *), so there is no way to know if you've truncated things. From the USENIX paper on strlcpy(): > The strlcpy() and strlcat() functions return the total length of the string they tried to create. For strlcpy() that is simply the length of the source; for strlcat() that means the length of the destination (before concatenation) plus the length of the source. To check for truncation, the programmer need only verify that the return value is less than the size parameter. Thus, if truncation has occurred, the number of bytes needed to store the entire string is now known and the programmer may allocate more space and re-copy the strings if he or she wishes. * https://www.usenix.org/legacy/events/usenix99/full_papers/millert/millert.pdf https://www.usenix.org/legacy/events/usenix99/full_papers/mi...
- grandinj 4y agothe git codebase internally does this, has quite a nice library of C functions to work on them
- Ygg2 4y agoInteresting enough, null terminated strings have faster Simd primitives for null terminated strings. https://stackoverflow.com/questions/20935769/sse42-sttni-pcmpestrm-is-twice-slower-than-pcmpistrm-is-it-true https://stackoverflow.com/questions/20935769/sse42-sttni-pcm...