Lambda the Ultimate

Try these bugs on for size.

Countering buffer overflows
"In nearly all computer languages, both old and new, trying to overflow a buffer is normally detected and prevented automatically by the language itself (say, by raising an exception or adding more space to the buffer as needed). But there are two languages where this is not true: C and C++...
An alternative is to use another programming language, since almost all of today's other languages protect against buffer overflows. But using another language doesn't eliminate all problems. Many languages depend on C libraries, and many have mechanisms that turn off the protections (trading off safety for speed). "

The virtual ring buffer (aka circular buffer) is common as salt in well-designed communications work. DSP chips have them in microcode. They seem strangely absent from modern languages, VMs, and CLRs.

don't higher level parts of the system deal with the problems that a ring buffer addresses in different ways? i'm sure they're great for buffering a stream of data when you're worried about speed and memory use, but in higher level - further up the comms stack - programming you're more worried about different things. infinte lists and streams are better abstractions (and are supported widely) for some applications where you might use a ring buffer (and you don't need to decide on the amount of memory you want ahead of time). and you can simply stop reading and let lower levels do the buffering.

maybe i'm biassed - i once wrote one of these things mainly because i didn't understand enough about either system-level buffering or the underlying comms protocol. it became famous (within the company) as a source of bugs (i just wasn't that used to messing around with pointers and memory - another way of saying i was using the wrong tool for the job). eventually we deleted it. the program worked just as well without (com.intertrader.io.GreedyInputStream RIP :o)

They are mildly tricky to write, but that is another argument to put them in the language or runtime support. I argue that they belong in the CPU instruction set.

Ring buffers can undergird higher abstractions, just like linear buffers. Just like linear buffers, they can grow and shrink, clone and resize, or allocate afresh. The ring nature can hide behind spillway techniques, creating an interface identical to linear buffers. The important difference remaining is that overflow problems are contained.

Translate the remark "let lower levels do the buffering" into "let Microsoft DLLs written in C/C++ do the buffering" and the point crystallizes. C/C++ offers no intrinsic overflow protection. That is why these bugs keep cropping up.

(Some overflow bugs are stack-related and those, ring buffers won't help.)

To me that just sounds like an argument to put them in a library.

The important difference remaining is that overflow problems are contained.

You can contain overflows with a linear buffer as well, for example by a dynamic check or automatically resizing. What is the advantage of a ring buffer?

BTW, perhaps I don't understand what you mean by ring buffer; if it doesn't automatically resize itself, and it fills up, does it overwrite the first element, or what?

To me that just sounds like an argument to put them in a library.

Right, a runtime lib. Wherever it may live, the point is to have one group write it once, and correctly. Dealing as it does with low-level byte shuffling, these things seem unsuitable for high-level (let alone garbage-collected) languages. Better that ring buffers be part of the C implementation of a language, another data type like "string."

You can contain overflows with a linear buffer as well...

Then why can't Microsoft manage it? Campuses full of C/C++ programmers and QA teams leave Microsoft issuing almost weekly patches for buffer bugs. This kind of discipline should be part of the language. With enough discipline, any one of us could become Mr. Universe; not many have it though!

Think of a ring buffer as a linear buffer with a perpetual watchdog sniffer to detect end-of-buffer conditions. The discipline moves from the programmer to the automated ring buffer.

BTW, perhaps I don't understand what you mean by ring buffer; if it doesn't automatically resize itself, and it fills up, does it overwrite the first element, or what?

Under normal operation by the time the buffer fills (wraps), the first element has long since been processed and become stale, so it can be overwritten. Internal pointers track the head and tail of live data within the buffer.

One sizes a ring buffer heuristically or empirically to match a given problem (like any buffer). A ring buffer is more likely to stay put and avoid memory management operations during time-critical communications loops.

The "spillway" is an end appendage which always mirrors a portion of the front, so that the buffer's interface to external code is everywhere linear. Callers can ignore the ring effect. If the caller's data happens to live at the wrap point, the spillway presents him with a nice linear interface. Now if your CPU happens to sport circular pointers, then you don't even need a spillway.

Ultimately an overflow condition (bytes of live data > bytes of ring memory) is like any other out-of-memory condition and would be handled by an exception mechanism.

mark's looking at this state of affairs as: circular buffers are safer than linear ones in practice. frank's seeing: both are equally safe/dangerous under the same conditions.

i guess it comes down to the "macho" c culture which values performance above everything. the language and style of programming that have evolved from that conspire to make code so unsafe. it can be fixed by changing the language or by changing the culture and libraries (together - or people simply won't use the libraries).

a circular buffer is safer because it is more complicated...

No. It is safer because the safety checks are automatic.

mark's looking at this state of affairs as: circular buffers are safer than linear ones in practice.

Yes, but more to the point, language support is in order.

frank's seeing: both are equally safe/dangerous under the same conditions.

Frank is just asking questions.

i guess it comes down to the "macho" c culture which values performance above everything.

No. I argue for language support because programmers should not be mucking about with this stuff. The language should do it for them.

the language and style of programming that have evolved from that conspire to make code so unsafe.

We are on the same page then: a "high-level language" is a Good Thing.

Circular buffers are terribly useful in communications work. Communications subroutines are a major nexus of Microsoft (and probably Linux) overflow bugs.

Note also CCured which has dealt with massive projects.