[TUHS] buffer overflow (Re: Happy birthday Morris worm

[Larry McVoy]

On Tue, Nov 12, 2019 at 11:41:51PM +0100, Robert Clausecker wrote:
> Oh please no.  One of the things we've hopefully all learned from Pascal
> is that length-prefixed strings suck because you can't perform anything
> useful without copying the entire string.  Rob Pike and friends showed
> how to get strings and vectors right in the Go language where you have a
> builtin slice type which is essentially a structure
> 
>     struct slice(type) {
>             type *data;
>             size_t len, cap;
>     };
> 
> where data points to a buffer, len is the length of meaningful data in
> that buffer and cap is the total buffer size.  

We did something similar in BitKeeper but we added a spicy little twist.
We encoded len and cap in one word by making cap increase in powers of
2 only (which means you need log(n) bits for cap).  So it was a data
structure that scaled both up and down.

We used it everywhere in BitKeeper, it was super handy.

http://repos.bkbits.net/bk/dev/src/libc/utils/lines.c?PAGE=anno&REV=56cf7e34BTkDFx47E54DPNG51B2uCA