4 ms·

> For example, "Do not use fixed size buffers". It's all very fine, but 1) it can be exploited as well if someone managed to fudge the size you are going to all

> For example, "Do not use fixed size buffers". It's all very fine, but 1) it can be exploited as well if someone managed to fudge the size you are going to allocate Fuzzing really underscored just how terrible "dynamically sized buffers" are to me as well. Even if your logic is perfectly correct (e.g. no possibility of buffer overflows), something as simple as deserializing a length-prefixed array needs a quota or cap. It's not enough to handle malloc failing: Someone will successfully allocate 1.9GB via your 32-bit deserialization code, spreading the actual allocation failures across the rest of your codebase - including all 3rd party and system libraries - most of which almost certainly have at least one oversight in OOM condition error handling, invoking all kinds of potentially exploitable undefined behavior.

userbinator 10y ago
I prefer attempting to find an O(1)-space algorithm over dynamic allocation, which I suppose means using fixed-size buffers anyway. In my experience it is surprising how many programmers will --- regardless of language --- tend to settle for O(n)-space or higher algorithms when just a little more thought would produce a simpler O(1). Line numbering is a common example of this.
- renox 10y ago
  Could you explain your point about line numbering?
  - MaulingMonkey 10y ago
    Take, for example, displaying the context source code for an error when you know the file and lineNo of the error. A naive approach would be to read the entire file into an array and then to output the lines [lineNo-context..lineNo+context], possibly with line numbers prefixed. This is O(N) memory with regards to the size of the file being processed. A 8GB source file will crash your program when built for 32-bit. Another approach is to read and discard until you've discarded lineNo-context '\n' characters, then copy chunks from your source directly to the output until you've read another 2*context+1 characters. This is O(1) memory (strictly speaking, you could do it byte-by-byte with an integer counter or two - practically you might have a fixed size buffer to read/write faster) and would allow you to handle even 1TB files sanely. To be fair, I'm often guilty of the naive approach myself :)

userbinator 10y ago

I prefer attempting to find an O(1)-space algorithm over dynamic allocation, which I suppose means using fixed-size buffers anyway. In my experience it is surprising how many programmers will --- regardless of language --- tend to settle for O(n)-space or higher algorithms when just a little more thought would produce a simpler O(1). Line numbering is a common example of this.

renox 10y ago
Could you explain your point about line numbering?
- MaulingMonkey 10y ago
  Take, for example, displaying the context source code for an error when you know the file and lineNo of the error. A naive approach would be to read the entire file into an array and then to output the lines [lineNo-context..lineNo+context], possibly with line numbers prefixed. This is O(N) memory with regards to the size of the file being processed. A 8GB source file will crash your program when built for 32-bit. Another approach is to read and discard until you've discarded lineNo-context '\n' characters, then copy chunks from your source directly to the output until you've read another 2*context+1 characters. This is O(1) memory (strictly speaking, you could do it byte-by-byte with an integer counter or two - practically you might have a fixed size buffer to read/write faster) and would allow you to handle even 1TB files sanely. To be fair, I'm often guilty of the naive approach myself :)