Hacker News Reader

Comment by marvy | Hacker News Reader

what's your better idea? (hint: this has to work in assembly language.)

Strings and arrays begin with one pointer-sized word that indicates the size of the string/array, thus making all the various mutant versions of functions that work with them unnecessary. And eliminate the requirement to specify length separately when passing as a function argument. And make bounds-checking trivial. And almost entirely eliminate buffer overflows.

This would naturally want malloc to know the type and count, eg: char[] x = malloc(char[], 100). That means no opportunity to screw it up (let the compiler turn that into the sizeof math to pass to the actual allocator).

If bounds checking is a performance bottleneck you could turn it off with compiler flags; that's not a valid argument against it.

But hey... all the various buffer overflows, RCEs, and various exploits are totally worth the minor performance gains /sarcasm.

I don't think you appreciate the zeitgeist. People were building complex systems: compilers, operating systems, databases, numerical simulations, and worse in machines with less memory than an Arduino. Adding a byte to every string was widely viewed as madness.

Yes, of course. The only problem is that now my iPhone is more performant than top supercomputer was then, but this ugly hack with strings is still there, alive and kicking.

And even then — one byte of memory could be nothing compared to CPU overhead. Or maybe not — RAM was insanely expensive these days.

But you're comparing apples and pears. This 'ugly hack' is - for obvious reasons - not what 90% of software on your iPhone is actually using to manipulate strings. Instead, the ugly hack known as NSString tidily wraps the char buffer, its byte-length, possibly an offset - most application developers never deal with null-terminated strings!

So in other words, I don't really understand why you are arguing for replacing a standard - one that works well for its purposes, mind you - with another when this has in fact already happened. And even less I understand why you are trying to frame a good and sound engineering decision as somehow a mistake?

Indeed. Its like mainframes didn't have 2-digit years because the programmers were stupid or lazy, they did what they could with what they had.

Funny, because outside AT&T people were able to do it, like those crazy Burroughs company in 1961.

If the strings is under 255 characters, using Pascal strings have the same cost. You keep "wasting" a single byte for null character or an counter. Null terminated strings becomes more space efficient when you need to store longer strings.

This has more far reaching consequences. You can't create pointers to strings, or you have to restrict them to only point at the head of strings. You would still have overruns, but the focus would be on overwriting the length field at the start of the string instead of overwriting the null at the end, or maybe overwriting the length on the next string. This is a seismic change to just about everything string related in C, the days of people iterating over characters with a pointer would be over.

Just think about how something like strsep (strtok to you older folks) would work in a system like this.

Remember, this was all written before computer networking, let alone internetworking. The level of defensiveness required to write network-facing code wasn't realised at the time.

The prevailing view of how to do things was based on tape (magnetic or paper). In that context, it's really inconvenient to know how long your tape is before you write it and really convenient to just keep reading it until you hit a marker or the hardware says "sorry, end of tape". See also the "end of file" character, ctrl-D.

Judging history in hindsight is uncharitable.

Ignoring history is even worse.

Burroughs B5000 in 1961, with memory safe systems programming in an Algol dialect.

https://en.wikipedia.org/wiki/Burroughs_large_systems

Similar examples can be provided for systems older or of similar age to PDP-11.

"An ordinary unprivileged user with sufficient knowledge of the system needs only the ability to be able to modify machine-code in order to penetrate the system completely."

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.162...

Security was hard then and continues to be hard now. It would also be nice to have a cost comparison between the various alternatives.

You should take on account that PDP-11 was pretty limited. You can't afford "wasting" memory on counters (for strings bigger that 255 chars) on an computer that handled few MiB at best, when you can use the null character trick, plus being efficient on these machine. Also, I think that not was motivation to make it secure on something that was initially a pet project on a unused machine.

PDP-11 was certainly more powerful than the Burroughs machines, being one decade newer.

P-Strings (Pascal) do exactly this. The original ones limited it to 255 (instead of using the pointer size), but others used more. One of the nice things about using Pascal for programming back In The Day.

The article says it doesn't know where ZTSs came into Unix, but I thought I read somewhere, many moons ago, that it was a pretty simple choice: prefixed strings used one more byte of memory than a prefixed string for a string longer than 255 characters, and on the systems at the time, that mattered a lot.

I thought the limited 255 byte strings were a nuisance in Turbo Pascal. It was one of the many reasons switching to C/C++ felt like getting out of jail.

A bit smarter is to combine the length field with the metadata stored already by malloc. Malloc (generally) knows the size of the allocation, probably not the exact size, but the size rounded up to 8 or 16 bytes. For example with glibc you call malloc_usable_size(ptr) (a non-standard function of course).

You can encode the byte length of the string minus the rounded up size (known by malloc) using the same trick that OCaml uses: https://rwmj.wordpress.com/2009/08/05/ocaml-internals-part-2... Using this trick you can get the byte length of the string from the base pointer in O(1). Such strings can also contain \0 characters.

Thus you don't need to store the string length explicitly as a separate field, and you can even make string pointers within the string work, and it's backwards compatible with legacy functions that expect a null-terminated string (albeit it won't work if you pass a string containing \0 to one of those legacy functions, but that is to be expected).

I wrote more about this topic: https://news.ycombinator.com/item?id=10866416

I think I read something like this in a header file for a GNU licensed compiler at some point.

The String object was a character array (presumably terminated by a NULL) which was prefixed by a size_t (it may have been assumed that String inherited another precursor class).

Still, I do like the idea of working within a bounded set. This sounds much more like a language feature where you could work within an array of known size. Though most of the time when I care about easy String handling I'm better off writing it in a higher level language.

make str_t an opaque type. First char is always length.

1. If string is 0-15 chars long, str_t is a small string, aka char[16]. First byte is length, payload starts in 2nd byte, tail is always zeroed. Empty string is all zeros always.

2. If string is 16-248, str_t is a half string. The whole payload exist in a single contiguous buffer. First bytes is length. A pointer to the rest of the payload exist within the remaining 15 bytes, starting at the first alligned address. This way you can cast half string as small string when passing as value without knowing the size at compile time (and stil recover the rest of the payload). Gap between the length and the pointer is reserved and always zeroed.

3. For lengths 249 and higher. Each value 249-255 is not the lenght, but an encoded way to represent one or more styles of bigger strings. Not need to hold the payload in a single contiguous buffer. Remaining 15 bytes will hold a pointer to the data structure in the same fashion as half string. Reserved bytes are used to represent length if possible. If not, length is required to exist at a fixed position in the first buffer accesible when dereferencing the pointer.

Wow, that sounds nightmarish. Three different ways to store the string, pointers to buffers everywhere, and because it is so complex your string library needs to account for all possibilities because there's no way anybody is going to want to manually twiddle with those strings.

If you get it right and hide all of the complexity from the user then it's not quite as bad, although undoubtedly confusing the first few times someone inspects it in their debugger.

YEs, you are right... it is very complex. But it is consistent enought that the compiler can do it all in the background.

If you think that it is a bad idea to do:

   str_t* string = (str_t*)malloc(string_length);

then half of the goal is been achieved right there.

The other half is to have this nailed down in the language definition in sufficient detail so that implementations do not differ widely and you can poke inside it with assembly when you have to.

I used to work for a company that whose C++ string class worked like this, although not quite as intricate. Had a separate mode for statically compiled strings too. It was pretty nice, although I didn't agree with every style choice. Makes some branchy code though.

In Visual Studio debugger you can write scripts to pretty-print string variables in the "watch" window, I would guess other good debuggers can do this too.

String operations are intrinsically complex by nature. At least they are now in this age that you cannot assume the encoding is always ASCII.

The goodness of this approach is that if you just need to pass around the string, a shallow copy of the first 16 byte block is enough. It might or might not contain the whole of the array, but if you need to know, it means you need to go through all the corner cases, no strcat(small_buffer, unsanitized_user_input), thank you very much!

Are there any other types in C that allocate space on the heap? Is that even possible in C? Not C++; there we have std::string, which is much as you describe above.

Reply on news.ycombinator.com