Narrowing the data. Continued fight against overflow
It all started with a stupid mistake. In the text of the program instead of the operator x=20; where x – an integer variable with a sign and size in bytes, accidentally written x=200;
And the compiler, as they say, without batting an eye, formed a command to write to a variable x constants 0C8Hwhich actually corresponded to the operator x=-56; It turned out that over the long years of operation of this compiler no dog no user (including ourselves) has ever written such blunders and therefore the error in the compiler went unnoticed. And the data narrowing teams were to blame.
In fact, of course, there are no narrowing commands in x86. This is how I call them by analogy with the existing extension commands.
But before discussing these virtual commands, I would like to digress a bit and pay attention to the type of error that occurred. Of course, the compiler test system was not up to par, since testing missed such an obvious lapse. However, not everything is as simple as we would like. For myself, I divide compiler errors into two categories and, using the example of real errors, I will show what is meant.
One of the first category errors in the compiler was that it could not generate code for a function that returned a pointer when that pointer was the result of the addr function built into the language.
Those. this is how you could write:
p=addr(x); return(p);And this is how we got a compilation error:
return(addr(x))The error occurred due to the fact that this particular combination was missed in the list of parsing branches. Adding it and fixing the error took just a couple of minutes.
A second category error in the compiler was found in indexed labels. The language allows you to write labels with indices in the text, for example, m(1): m(2): and so on. and jump to them with the goto m(i) operator. We used such a mechanism, for example, to write complex finite automata, but that’s not the point. It turned out that if several labels with the same index were accidentally placed in the text, the compiler takes the address of only the last one.
It would seem, well, what categories can such bugs have? Bad testing, that’s all. However, in the first case, the compiler gave an error for the correct fragment, and in the second case, it did not report an error in the wrong fragment. In my opinion, this is the fundamental difference.
In the first case, a system of tests can be created that will pass at least once for each branch of the compiler. Having a formal description of the language, such a system can even be created automatically. And the number of tests in this system will be finite. And all errors of the first category (in theory) will be detected. So for the first error, there really was bad testing.
In the second case, the number of possible errors in the text is potentially unlimited. How is it with the Strugatskys on Monday, which begins on Saturday? The knowledge of infinity requires infinite time? Therefore, work do not work (or in this case, test do not test) – everything is one. All errors of the second category will still not be revealed.
In fact, the infinite number of possible errors in the program text is not at all a reason to refuse tests containing known errors to check whether the compiler responds to them. But a kind of missing compiler error in the statement x=200; It is connected precisely with the complexity of inventing specially erroneous tests and with the complexity of their formalization.
Thus, for a long time, these errors were not detected, since, again, no dog not a single user suggested such fragments of programs to the compiler, and in tests no one thought of writing this on purpose.
Let’s return to the topic of the article. In my previous note, I mentioned that the compiler uses only 90 x86-64 instructions in its work, excluding instructions FPU.
At the same time, some of these 90 are not commands at all, but convenient abstractions for the compiler, like labels or pseudo-commands func, which is needed only to detect the exit from the function without calculating the result. And among these pseudo-commands there are data narrowing commands, as I call them. They are inside the compiler and are named accordingly. cwb and cdw by analogy with real extension commands cbw and cwd.
Since most readers are not very familiar with the x86 instruction system, I will give a little help.
Ever since the 8086 processor, two operand expansion instructions have been provided cbw and cwdwhich are, in fact, just a preparation for the division of integers, which always requires a pair of registers for the dividend al:ah or ax:dx. That’s why cbw fills the register Ah case sign ala cwd – sign ax/eax fills the register dx/edx. With the development of x86, convenient operand expansion instructions appeared, no longer for division, but simply for manipulating objects of different sizes, and the instruction movx expands a signed operand, and the instruction movzx – fills the rest of the larger object with zeros.
For example, the command movsx ebx,al converts case ebxso that the low byte ebx (i.e. register bl) becomes equal to case aland the remaining three bytes ebx will be filled with zeros or ones depending on the sign bit al.
The compiler has a handling of the generalized assignment/transfer operation. If it has integer type operands, then they can be 1, 2, 4, or 8 bytes in size. Thus, in this operation, there can be 16 different combinations of the sizes of the two operands in total. Four options (equality of sizes) do not require additional actions, which is nice. In other cases, either six types of operand expansion or six types of operand “narrowing” are required, which leads to the generation of yet virtual expansion or narrowing instructions.
Virtual expansion commands eventually spawn real expansion commands movzx or movsx, for example code movsx ebx,al. But the reverse action, i.e. narrowing in the form of a command movsx al,ebx is not created, since there is no such command in x86, normal transfers are used instead, for example, in the form of a command mov al,bl.
If you do not bother with some very exotic cases of objects that occupy a non-integer number of bytes, then such a system of expansion-narrowing works fine. But there is a nuance. If, by definition, there cannot be an overflow when expanding an integer operand, then when narrowing the operand, it can.
Compiler error while parsing statement x=200; was not so much that he decided to put the low byte of the constant in the variable x, how much is that he did not check, but whether such a signed constant “climbs” into a variable. And in this case, the compiler would have to be informed about the overflow, and this is easy to do, since the constants are known at the compilation stage, and they can be immediately checked for a valid range.
The situation is more complicated with checks during program execution. First of all, how do you quickly check for overflow? Yes, just like in the lower grades they are forced to check division by multiplication, i.e. reverse action. So here, the “narrowed” operand must again be expanded to the size of the original and compared with the original. If they are equal, such a narrowing is legitimate, otherwise the same overflow occurs.
For example, suppose in the program it is required to assign an integer signed variable y byte-sized value of an integer signed variable x 4 bytes in size.
Without overflow control, the compiler generates simple transfers:
mov al,x
mov y,alWith overflow control, commands are generated:
mov eax,x ;достаем содержимое переменной x
push rax ;помещаем ее в стек
movsx eax,al ;расширяем младший байт
cmp eax,[rsp] ;получилось исходное значение ?
pop rax ;очищаем стек
jz m ;все в порядке, x помещается в y
into ;иначе сигнал переполнения
m: mov y,al ;пересылка в yof course x86-64 doesn’t have my favorite command intowhich checks the overflow flag (and this flag is not set here), but the generation of an overflow signal can also be implemented using the forbidden command handler intobecause with a “forbidden command” exception, it is easy to determine from the context (that is, from the code of the above check) that this is a case of exactly an integer overflow when narrowing the data.
For all cases of checking the narrowing, this piece of code will be the same, except for the form of one command movx or sometimes movzxwhich is used for unsigned narrowing.
Although there is no explicit unsigned integer type in the subset of the language we are using, implicitly such a type still arises. For example, the language has a built-in function asciiwhich returns the ASCII character given by its ordinal (so ascii(140) will return the character “M”). Therefore, if the parameter of such a function is a variable of two or more bytes, when narrowing, it is necessary to take into account the allowable range of 0-255, and not -128+127. In this case, instead of movx and applied movzx.
After introducing such additional overflow checks into the compiler when narrowing, even old and long-running software suddenly began to show errors. For example, in one of the programs, when extracting a substring from a string, the initial position was specified as length(s)-2, where length(s) is the current length of the string. However, the case of an empty string still arose, and then the initial position turned into invalid -2. Naturally, the language has control over the correctness of substring positions (with the exception StringRange). But due to narrowing command without overflow check invalid -2 with a flick of the wrist turned into a valid 254 and the existing substring check passed. True, then the empty string was still discarded and there were no consequences, which is why, in fact, this error was not noticed. But you can’t expect it to always be like this.
Additional checks increased the size of the code and slowed down the work, but they increased the reliability of the programs. I consider such a payment for reliability to be quite justified, besides, narrowing the data in programs is still not required as often as expanding it. Of course it’s a pity that in x86 there are no type narrowing commands mov al,ebxwhich would simply perform a register transfer bl in albut at the same time they would also set the overflow flag if the register ebx “does not fit” in al. Such commands would be very helpful in compiling compact and fast code with overflow checks.
If, nevertheless, in some case it is required to simply pass part of the larger operand to the smaller one without checking, then this can be implemented in various ways besides simply disabling checks in the compiler. For example, PL/1 has the ability to “stack” one variable onto another in memory:
declare x fixed(31), y fixed(7) defined(x); // x и y имеют один адрес в памятиwith such an overlay, the operator y=x; not even needed, in a variable y and so will always be the low byte of the value x. There are no narrowing commands, and therefore no overflow checks. The compiler only checks that the smaller object always overlays the larger object, and not vice versa, since memory is allocated for only one object. But such cheating of the compiler is still a rare case. More often in transfers, overflow control is natural and necessary.
For many years I have been using a language that has very little “undefined behavior”. Even 55 years ago, the language standard unambiguously defined a set of exceptional situations like SubScriptRange (index out of bounds), StringRange (out of line position) and others, including, of course, and fixed overflow (integer overflow). This approach makes the behavior of programs predictable and greatly facilitates debugging and maintenance of the software. And now, additional checks have finally been covered from overflow errors, an unclosed, as it turned out, “side gate” in the compiler in the form of data narrowing commands.
And this is much better than, as in some languages, errors and algorithms and programmers associated with overflow, just sweep under the rug with the inscription “undefined behavior”.
