A defense of C's null-terminated strings
utcc.utoronto.ca
utcc.utoronto.ca
Strings could be represented as length checked arrays. They could come in two types, short ones, having a length byte at the beginning and are limited to 256 elements, and long ones, having an "int" size marker and corresponding length limits. The type handling could be handled by the compiler, the length() function would always return an int, and the elements addressed by a[i]. Thats it. This would have saved us more than 3 decades of nasty bugs if not security problems.
The Pascal I remember (some version of Turbo Pascal in the early 90s) had strings where you had to declare the length as part of the type. Strings of different length had different types and you could not pass a string of length 30 to a procedure that expected a string of length 31. The way to solve this is to declare that all your strings had the same length and hope that it would be enough. It was horrible and at the time I found the C approach much more reasonable. Of course Pascal improved through the years and the C approach turned out to be a huge security problem.
The first byte tells you the string's length. If the MSB of the first bit is set, the string's first 4 bytes tell you the length of the string. I mean yes its not a horrible system, but there are better systems.
I'll be honest I like Rust's. Just keep the length and the pointer on the stack in a tuple.
Algol and Mesa were two other languages that you could generalize over array size.
For anyone interested in systems programming it is a good eye opener to delve into the system programming languages from 60 and 70's, before C escaped UNIX.
From an information theoretic point of view, making 1 out of 256 values of each byte unusable as the content of the string, is an overhead linear in the size of the string, not constant.
I like to think of bash / sh as just a job control system. It enables you to setup process pipelines. Everything is just processes and files (streams). Variables only serve as programs arguments. Since program arguments are also null terminated, variables containing null bytes just make no sense.
(Of course it gets dirty as soon as you feed the output of a job into a variable, for example. I think that isn't even defined by POSIX for non-text streams).
This is why it surprised me when I realized (without having thought about it) that variables can't contain null bytes. It made my quick id3 tag parsing script a bit trickier to write, since I could no longer just use read(1P).
1/(log2(256)-log2(255))
Assuming 8-bit char, at 1417 chars, zero terminated string overhead is 2 chars.
For 255 characters you lose 9.4 bits which is bigger than the cost of an 8 bit size field.
For 65535 characters you lose 378 bits which is much bigger than the cost of a 16 bit size field.
On the other hand you have only one string type for arbitrarily sized strings and most strings are short.
What would really be needed to be more space efficient for short and long strings is a size field with a variable length encoding. E.g. 1 byte for string lengths up to 64, 2 bytes for string lengths up to 8k, etc.
It's just decoding that requires pipeline busting branches. Well, I guess it's fine if you take branch mispredict for the large string case.
Maybe 1 byte with highest bit zero, 0-127, 2 bytes for 128-32767, etc?
The irony is of course now we have variable length encoding for the string size...
I think just using size_t instead makes more sense than saving a byte or two per string. Memory is cheap, but CPUs aren't getting much faster.
When size is an issue and nothing else prevents it either, just LZ4 (or similar memcpy order of magnitude speed compression) the string.
Yes, "size_t" should be just about right for everybody except the guys who _need_ to program in C/C++ and Assembler due to the hard requirements of their systems. Not very many people but very important systems.
Example: a string with 0 character has a length of 1 (it contains NULL), a 100% overhead. A string with 1 character has a length of 2, a 50% overhead. It gets better with larger strings.
Strings that can't make use of 0 have to be a small constant factor longer to store the same entropy, because each byte can only store log_2 (255) ~ 7.994 bits, instead of log_2 (256) = 8 bits.
Of course, if you are storing printable ascii characters only, that doesn't matter, since you are using far less than 256 possibilities per byte, and so don't care that some of them unused onces are used for in-band signalling (https://en.wikipedia.org/wiki/In-band_signaling).
As vardump points out in another comment, that's equivalent to 1 in 177 bytes.
1) Memory-safe (can't touch memory that you don't own)
2) Opaque (standard library can change the implementation later)
3) Immutable (can be passed around like values)
4) Unicode (no fixed width chars, no default conversion to bytes)
I don't know any good reason to deviate from these rules. Even systems languages would do well to follow them, IMO.
1) Memory-safe costs a lot and gives me little. If I know I'm not going to touch memory incorrectly I should be able to take advantage of that.
2) Knowing the cost of operations is essential to do any kind of performant programming in a reasonable amount of time; e.g. whether `length(x)` is O(N) or O(1). The operations specified is hugely important.
3) When I've got a 300GB log to update, an in-place algorithm will be better for everybody. Microcontrollers don't want to waste space with extra copies either, and a better algorithm wins.
4) I'm not sure having an opinion about Unicode in the language is ideal: You can either store an array of bytes, or you can store an array of code points, or you could store a list of UTF8 "characters", and I see value in all of these interpretations (comparison/copying, rendering, transcoding). I'd prefer flexibility, and the language not switching them around on me behind my back (see #2)
1) Memory buffer errors cost a lot. Kernel panic or a frozen device after overwriting its whole memory. Having some low cost safety would be very much welcome. One of the biggest reasons I'm interested in Rust.
2) Well, I guess you can peek at the implementation, no? Strlen doesn't give you any guarantees either -- different implementations over an order of magnitude in performance.
3) Having a 300GB log to update, what happens when your update process step 2 out of 3 fails? In-place updates are risky on shared or persistent data. And this is a low frequency corner case anyways. Most strings don't need to be mutated. So it's reasonable to default to that.
4) Array of bytes is usually good enough. When it's text, it encoding should just always be UTF-8 except when not practical for some external reason.
I think about programming a lot.
I don't do much programming since my programs usually work correctly the first time, but when I do I write fast web servers and operating systems and text editors and language bindings and compilers and interpreters and compressors/decompressors and image editing tools, backup tools, system administration tools, reverse engineering network protocols, reverse engineering file formats, invoice generation tools, billing and accounting packages, mobile apps, high volume mail servers, mp4 decoders, 1wire (dallas) drivers, ad servers, ad players, web applications like email clients and web stores, windows device drivers, linux device drivers, and other things that I can't remember right now.
I have observed that the bugs I tend to make have more to do with my failing memory (i.e. what I can remember), than overflowing buffers that I allocated. Maybe memory buffer errors happen to other programmers often enough that it's worth worrying about for other people, but I'd argue this says more about those other programmers, and I propose that the techniques I use to avoid making those mistakes are more valuable than memory protection since it clearly allows me to have my cake and eat it too.
I've observed a great deal of performance can be gained by controlling how my structure is laid out in memory, but in order to do that, the compiler needs to trust me.
Maybe.
Some languages are experimenting with algebraic types and what they're doing might be a good-enough middle ground such that they can actually get zero-cost buffer protection, but I haven't played with them much to know for certain. I'm willing to be convinced, but I haven't yet, so I continue to maintain that enforced memory protection is not ideal.
Re 2) I think the original point is that the implementation should be free to change it however (and whenever) they like. That's why they wanted opaque strings, such that you access them from the interface itself.
Re 3) It depends. If it fails, then we've lost however long it takes to scan 300GB (a few minutes), but just because we copied it once from the disk, doesn't mean we need to copy it again and again: That turns minutes into hours. I agree that most strings don't need to be mutated, and that it's reasonable to default to it, however order-of-magnitude performance gains are worth spending a little time thinking about, and they often require mutating-in-place.
Traversing a tree is another good example, and the Schorr-Deutsch-Waite link-inversion algorithm (Knuth, TAOCP vol.1 § 2.3.5) is essential for constrained-memory devices when you need a tree-walker. Sometimes I need to mutate, so I think enforcing immutability is simply not valuable.
I didn't want to invoke any contest, but to remind C is used a lot in those contexts and zero termination seems to be one of the bug magnets. A very common source for security vulnerabilities as well, pretty large portion of them are related to string processing.
> Maybe memory buffer errors happen to other programmers often enough that it's worth worrying about for other people
Yup. Maybe a large part of how I think of this to protect the other people. It's not rare someone messes up on an embedded system and writes a bit somewhere else in memory. Often it won't crash, but the bugs you get take ages to hunt down.
There's just no way around it. I do want to delegate things to other people. Defensive coding tends to catch and prevent a lot of mistakes at that point. Many of them have pretty cowboy attitudes towards details such as parameter validation or error checking. Some of them will need to maintain it in the distant future.
> I've observed a great deal of performance can be gained by controlling how my structure is laid out in memory, but in order to do that, the compiler needs to trust me.
Yeah, performance is often about cache, locality of reference. Pointer chasing and other random access destroys performance. Applying SIMD without penalties requires at least 16 byte alignment. In 2016, 64 byte align is even better. SIMDs are getting pretty wide.
Re 3)...
I still think that 300GB string example is esoteric, even off topic. You're not going to put 300GB string in any standard string abstraction. There are probably a lot of other worries, such as running out of disk space, undetected data corruption on disk (happens pretty often), failure in the middle of the modification process, etc.
> Sometimes I need to mutate, so I think enforcing immutability is simply not valuable.
I don't think anyone wanted to enforce immutability. Just to have it default.
I understand. I think the gross majority of this comes from the C standard library though, and not from the C language.
qmail for example had no buffer overflow problems -- the first security vulnerabilities found 10 years after release wouldn't affect any system that qmail was developed to run on simply because nobody gave their mail server 4GB of ram! Surely the author should have predicted this problem, but it demonstrates methodology can protect against this issue.
KDB takes an interesting approach of reference counting in all operators. Operators can then be optimised for situations where one argument (or both) have a reference-count of exactly one. This means writing C code with KDB's memory management library can make things very simple.
Antirez also has an interesting string library that uses a combination of length+null-termination specifically for the purpose of finding bugs.
> There's just no way around it. I do want to delegate things to other people. Defensive coding tends to catch and prevent a lot of mistakes at that point. Many of them have pretty cowboy attitudes towards details such as parameter validation or error checking. Some of them will need to maintain it in the distant future.
I understand what you're saying, but I think technique can help a lot more than we think: Most of the software engineering industry wants to move to smarter and better tooling, and I'm just proposing we upgrade our brains some too.
I don't have all the answers yet.
> You're not going to put 300GB string in any standard string abstraction.
In KDB this is actually pretty common, but it doesn't have a "standard string abstraction" because while it meaningfully supports byte-arrays that are in the 300GB range, the string-atoms (symbols) which are used similar to strings in python et al, never approach 1MB let alone 300GB.
However in C I just did mmap() and updated the file. It took about 15 minutes to write and debug, and a few minutes to run on the server.
> I don't think anyone wanted to enforce immutability. Just to have it default.
I don't know. I parsed I don't know any good reason to deviate from these rules. as "enforce". I might be wrong, you'd have to ask "cousin_it" what he/she meant at the time. I know at least later they either were convinced, or clarified[1] this position.
However what I meant was that I don't want to enforce those rules because I can think of an exception for each, and they understood that. Sorry I was unclear though.
Wut? Memory safety costs very little and gives you a lot in terms of buffer over flow vuls, remote code execution, use after frees. Running a single in range check costs 1-5 processor cycles which will be branch predicted out of existence.
2) I agree that time and space complexity should be part of the contract.
3) I agree that escape hatches are needed, but they shouldn't be the default. Most code isn't performance sensitive, but all code is bug sensitive.
4) The best internal representation is probably UTF-8, but I don't feel strongly about that. What matters is that the available string operations are specified in terms of Unicode, not bytes.
I grew up in Russia and I remember very well the "fun" of programming with Cyrillic strings in a mixture of Win-1251, KOI8-R, and Unicode. Working with strings as untagged bytes is a disaster everywhere except English speaking countries.
An array of bytes is a storage medium. If you don't need the number of utf-8 characters (and given things like combining characters and invisible spaces, it's rare that's what I actually need) and just need to print and compare, byte-strings are efficient and acceptable. The text remains utf-8 encoded, but `length` is `O(1)` or a simple scan, and `substr` (or similar) are `O(1)`+the cost of allocating.
However if I need to recode things, an array of 32-bit (or 64-bit hah) ints is sometimes better. If the language has a real iterator, UTF-8 might still be okay, but then you are still using a bytestring anyway.
Lastly, if the "string" actually knows its character set, then using things besides UTF-8 might be good because it saves a lot of space. Maybe. I'm not really convinced because the tag for the character set (as you rightly think necessary) takes up space too. Dealing with these kinds of "strings" is really complicated, so I'd agree that anyone who would jump into complexity without some real justification is, as you say, a bozo.
I think a lot of trouble showed up when people thought "string" meant "text", and new programmers learned (in a 7-bit world) how to make programs this way. And then unicode.
I try to be specific and say "array of bytes" (or sometimes "bytestring") if I mean something that's accessed a byte-at-a-time, but since most text is just copied; sent verbatim to the screen, to the HTTP response, etc, I worry about the `O(N)` access and counting algorithms showing up in languages.
Java recently (JEP 254) moved to internal flag for Strings (ISO-8859-1 or UTF16) as most memory was used by strings without any special characters. It was decided that additional complexity was worth it. I guess that getting rid of UTF-16 would be even better as it is the worst Unicode encoding.
You may be that legendary programmer who writes code "without bugs" and everything works correctly on the first run. I don't doubt a handful of "real programmers" like that exist. But most of us make mistakes, and we want the compiler to protect us. Just look at the endless stream of memory-related vulnerabilities at CERT. Nearly all of them could have been prevented in a memory-safe language.
2) That is a non-issue. All serious standard libraries define operation complexity at the Big O granularity. Sometimes they go even further and the spec (especially in C++'s case) gurantees some implementation details.
Anyway, if you're not happy with the proper characteristic of a standard data structure for a certain use, there's nothing preventing you from creating your own data structure with your preferred behavior pattern. You can even use an 'unsafe' override - at least you'd isolate unsafety to a very small and manageable part of the code that way.
3) Again, nothing prevents you from optimizing for special cases. But that are many more programs (e.g. parsers) that deal with short and repetetive strings which can benefit from an implementation that passes them as value-types on the stack (this is essentially which most C++ implementations do).
4. I'm all for a default unicode string type and a separate "raw bytes" type. But the you should either store the string as unicode codepoints (UTF-32) or as UTF-8. UTF-16 is pure evil, since then people tend to assume UTF-16 elements are codepoints and surrogates break spectacularly.
Most of the bugs I create seem to have to do with my limited memory: I forget things when I scroll, or (more often) I misremember things. These bugs are still very embarrassing, but are something I'm working on by scrolling less.
Re 2) I agree it should be a non-issue, but the parent wanted to make the implementation fully opaque which hides operation complexity.
Re 3, 4) Agreed completely. I think these are easier to get with increased flexibility, not with stronger harnesses though.
> I don't know any good reason to deviate from these rules. Even systems languages would do well to follow them, IMO.
Systems-languages are used for things like OS kernels and god knows what where other equally important rules apply:
1. being able to manipulate things directly, in place, without having to allocate additional memory (i.e. creating a new copy)
2. efficiency may be more crucial than type-system guaranteed safety.
Not saying I disagree with your general position, I'm just open to the fact that there's always valid exceptions to any rules.
But, importantly, they don't do it by default as C does.
Not saying it doesn't happen, only that it is rarely needed.
Usually when you can't allocate memory (like IRQ handler), you don't do string processing either.
1) No protection exists there.
2) Abstraction costs too much.
3) Store it in Flash.
4) Be happy your characters may even use the 8th bit.
The main drawback is that most functions have to reassign the pointer back, like in:
sds foo = sdsnew("foo"); // Creates an SDS string
printf("%s\n", foo); // You can print it with printf()
foo = sdscatlen(foo,buffer,10); // Append 10 bytes.
As a stopgap, though, SDS could use GCC's attribute "warn_unused_result" on all of those return values.
So long as all your operations on the string are char-at-a-time, and your first act is to check the char against zero, this works fine.
In fact, so long as you stay in the original UNIX batch processing model, where you're reading bytes from stdin and writing to stdout, the whole program works fine. Inconvenient buffer-size issues are avoided: don't keep intermediate buffers, just write to stdout a char at a time. (Have a look at lex/yacc generated code for this model, for example, with their not-easily-resettable parsers and trouble handling errors other than by calling `exit`).
The problem is not so much "string is not a type" as "buffers for composing strings are not a type".
For security you need not "string first char + length of string" but "string first char + length of allocated region into which it is safe to write", which (unlike the length of the string) cannot be inferred from the string head pointer in any way.
that's pretty harsh, and far-reaching. is it really justified to paint _everything_ with that brush ?
Considering that stubborn programmers are still using strcpy() and its ilk to this very day and the billions of dollars lost every year to cybercrime, then I don't think it's harsh.
>Bstrlib is, by design, impervious to memory size overflow attacks. The reason is it is resiliant to length overflows is that bstring lengths are bounded above by INT_MAX, instead of ~(size_t)0. So length addition overflows cause a wrap around of the integer value making them negative causing balloc() to fail before an erroneous operation can occurr. Attempted conversions of char * strings which may have lengths greater than INT_MAX are detected and the conversion is aborted.
>It is unknown if this property holds on machines that don't represent integers as 2s complement. It is recommended that Bstrlib be carefully auditted by anyone using a system which is not 2s complement based.
(b->slen+1) < 0
b->slen < -1
" D is the first example to have array slices that I can think, of so this might be slightly a-historical."
No, D wasn't the first one.
There were already systems programming languages with proper string types with the same age or older than C.
Usually there was a clear distinction between array of characters and strings, both in any case safer than C's approach.
Most other high-level languages would let you copy the substring even if you don't intend to modify it.
C++, std::string yes. But for example Java, C# and Go (slices) substring doesn't copy data.
edit: I believe String is overused in java land and we should have more CharSequence implementations. https://docs.oracle.com/javase/8/docs/api/java/lang/CharSequ...
If you're stating that C# Substring doesn't copy the string, that is incorrect; .NET always makes a copy: http://stackoverflow.com/questions/6742923/if-strings-are-im...
Like C, any dev that makes language assumptions based on the installed compiler, is bound to get burned.
The implementation changing to be asymptotically worse is not fine.
Also they could have changed the garbage collector to make both cases perform well.
Edit: And the comments you linked have a good point made in them, if you don't assume some bounds on how long a function is going to take, you can't call it ever. substr is not a function that's supposed to be forbidden.
So the thing about advanced compilers in the java world is that they use defined behaviour(results) to do optimisations. And the best optimisations are about not doing work you can avoid. i.e. if you can avoid doing an allocation at all because the (sub)string you just created is only used locally, the object might not be allocated at all (heap|stack) but just registers are reassigned with temporary values needed to calculate the function. So its already common to have O(n) semantics turn into O(1) or even better O(0) ;).
In the java world results are specced, not how you need to get them. (Exceptions to this rule exist).
If you have a real garbage collector of course using the same representation for strings and slices (two pointers or pointer+len) is appropriate.
That allows for elegant constructions in C such as:
while (*p++ = *q++);For example, you would need to ensure that sizeof p is >= sizeof q, or else you will end up with a buffer overflow. This then implies that q has a length and therefore a \0. So you will need to iterate through the string once to find the \0 (which may not be there).
Failure to do this can lead to execution of arbitrary code, which is why null terminated strings are indefensible frankly.
> That allows for elegant constructions in C such as:
> while (*p++ = *q++);
It maps very poorly to modern CPUs as-is, unless the compiler recognizes it as strcpy and replaces it with appropriate code. Luckily most compilers are capable of that. Otherwise loop termination condition causes (most?) compilers not to even try vectorization and an order of magnitude of performance is lost.
Indeed. When I said I read this a long time ago, I meant decades :)