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

Larry McVoy lm at mcvoy.com
Wed Nov 13 10:24:35 AEST 2019

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.


More information about the TUHS mailing list