4 ms·
I feel like this statement does not reflect an understanding of the problem. Machines do not have arbitrary-precision integers. If you need to take X units of
by asveikau 13y ago
I feel like this statement does not reflect an understanding of the problem.
Machines do not have arbitrary-precision integers. If you need to take X units of Y bytes, and your integers are 32 bits, and X is big enough so that X * Y will not fit in 32 bits... Then this problem has to exist somewhere - the machine will have to truncate the product into a 32 bit entity, the bit pattern of which is a legitimate quantity in its own right. The allocator doesn't and can't know whether you really meant "the lower 32 bits of X * Y" or "the product of X and Y", because the former is a totally valid input.
You could very well make the same mistake in a higher level language since AFAIK most of them don't have arbitrary precision integers by default: create an array of a size based on an expression with an integer overflow. The difference is that it will blow up in a "safer" manner when you index beyond the end of the array. You could argue that this is the real benefit of the higher level language and perhaps you're right, but somebody at some layer of the system must implement that check; the machine does not have it as an inherent feature.
- betterunix 13y ago"Machines do not have arbitrary-precision integers" Nor do they typically have multidimensional arrays. The reason we use compilers and high-level languages is so that we can think in terms of an abstract machine that is easier to work with. Languages exist for the benefit of programmers, and the less mental effort programmers have to spend on nonsense (like remembering that arithmetic is done modulo 2^32 -- or is it 2^64, or 2^29 [yes, really], etc.?) the better able they are to create useful programs. "the machine will have to truncate the product into a 32 bit entity, the bit pattern of which is a legitimate quantity in its own right" Right, and that is why the compiler should translate "x * y" into an arbitrary-precision multiplication -- because programmers assume that "int" refers to "integers," which do not get truncated when they are multiplied. The only reason a compiler should not do such a thing is when it can deduce bounds on the operands that ensure no truncation will occur. Languages that use arbitrary precision arithmetic by default are better and make programmers more productive. "You could very well make the same mistake in a higher level language since AFAIK most of them don't have arbitrary precision integers by default" Yeah, but integer overflows can be and should be reported as errors in languages that do not support arbitrary precision arithmetic. It is very unusual for an overflow to be the desired behavior of a program, and more often than not, overflows are bugs. There was an attack on an electronic voting machine (shown in Hacking Democracy) that exploited an integer overflow -- had the software simply entered an error state, the attack would have been stopped regardless. "You could argue that this is the real benefit of the higher level language and perhaps you're right" Yes, that is basically the point I was making. Let's ignore the part about arbitrary precision arithmetic, and simply assume that overflows will go unreported. Why should it be possible to read or write arbitrary locations in memory as a result? If you try to access an array index that is out of bounds, an exception should be thrown. If the compiler can guarantee that you'll never be out of bounds, i.e. that the exception would never be thrown, it can remove the bounds check as an optimization -- but only when there is such a guarantee. "somebody at some layer of the system must implement that check" That is why we have compilers: they can insert checks for us, automatically, everywhere the checks are needed. It is not different from having your compiler ensure that all functions use the same argument passing convention. Again, this is why we use compilers -- compilers are better at doing mundane, tedious tasks like setting up stack frames or checking array boundaries. Programmers tend to make mistakes with these things, and those mistakes usually lead to disastrous problems later on.
- asveikau 13y ago> Why should it be possible to read or write arbitrary locations in memory as a result? Because that is the point of an allocator. Your favorite language cannot have allocators in the same sense that C can. Instead of going on a crusade against the language, why not simply accept that some problem domains have to care about that? In this discussion I am not here griping about my favorite criticisms of various higher level languages (some examples: lots of code out there that assumes memory allocation is free, data structures with lots of gratuitous pointers [oops sorry, "object references"!] that slow down access, over-reliance on exceptions i.e. thousands of gotos that cross stack frames) because I admit that these languages are good for certain problem sets.
- betterunix 13y agoThe issue is not with the allocator; the issue is with the ability to read or write beyond the bounds of an array. The fact that arrays are represented with pointers only worsens the problem. Even for low-level code, it never makes sense to step out of array bounds. Worse, though, is the fact that most C code is high-level, with no particular need or benefit from pointer acrobatics, and exposed to potentially malicious inputs. A common refrain in these discussions is that C is good for some problem domains, and high level languages are good for others. The problem is that C is not being used only for one domain or some set of domains; it is being used everywhere. Web browsers and web servers are written in C. Email clients are written in C. Instant messaging programs. It is hard to see how my email program benefits from pointer acrobatics, unchecked array access, or a pile of undefined behavior -- so why was it written in C? You could say this is my main issue. I can just assume that C is good in some domain, even if I never come across it; what I cannot understand is why high-level software is being written in a language that bogs programmers down with low-level concerns. Even implementing a small core in C, and the rest in a high-level language (e.g. Emacs) makes more sense than what we see today.
- asveikau 13y ago> The issue is not with the allocator; the issue is with the ability to read or write beyond the bounds of an array. ... Even for low-level code, it never makes sense to step out of array bounds. You must understand that from the low level perspective, the array and its bounds do not exist. This is an abstraction. An allocator needs to chop up and slice a larger block of memory and give different segments to different callers. You cannot do this if something is enforcing bounds. What you can do is build higher level abstractions that track bounds and do runtime checks at every access. In C there is nothing to stop you from doing that as a library. In C++, some STL implementations even have bounds checking as a compile time option. But the languages don't force you into paying that cost.
- dragonwriter 13y ago> Machines do not have arbitrary-precision integers. Machines don't have concepts like "integers" at all. They have concrete functions that produce defined outputs with defined inputs, which can be interpreted as fixed size integers, components of arbitrary precision integers, or specifications of glyphs, or numerous other things. But none of those interpretations are inherent in the machine.
- asveikau 13y agoBy integer I mean machine word. Those do exist. I suppose we can get philosophical and say that there is no such thing as a machine word, that when you operate on the memory using different instructions, or jump into the memory, or whatever, this "machine word" becomes something else... But IMO this is a pointless exercise. The fixed-size machine word is a reality in the machines we're talking about. (How that gets translated into a higher level language like C will vary from machine to machine, compiler to compiler, but the analogy still stands and I do not believe it is meaningful to argue such points unless engaged in purposeful misinterpretation.)