64-bit horse that can count
The article is devoted to the peculiarities of the behavior of the Visual C ++ compiler when generating 64-bit code and the potential errors associated with it.
The phenomenon of “Clever Hans,” Mr. Von Osten's horse, was described in 1911 [1]. Clever Hans was famous for being able to read and solve math problems, tapping the answer with his front hoof. Of course, there were many skeptics. Therefore, the ability of Hans was tested by a commission of experts, which found that the horse demonstrates them without the help of Mr. von Osten. But how could such a thing exist - human! - level of intelligence in a simple horse? The psychologist O. Pfangst carried out a series of experiments with extreme thoroughness, as a result of which he discovered that Hans received subtle, unintentional clues from those who asked him questions. For example, after Hans was asked about something, people fixed their eyes on his front hoof, with which the horse “answered”. But as soon as Hans hit the hoof the necessary number of times, the questioners raised their eyes or head a little bit in anticipation of the completion of his answer. And the horse, which was trained to notice and use these almost imperceptible movements for the observers, perceived them as signals to stop their actions. From the outside it always looked like the right answer to a question.
That was such a wonderful horse, who considered and solved puzzles, although he did not know how to do it. 64-bit programs have become digital horses of the beginning of the 21st century, many of which also cannot be counted, although they successfully pretend. Consider this phenomenon in more detail.
')
I am the author and co-author of a number of articles devoted to the problems of developing 64-bit applications. Articles can be found on our website: http://www.viva64.com/en/articles/64-bit-development . In these articles, I try to use the term “potential error” or “hidden error”, and not just “error” [ 2 , 3 , 4 ].
I explain this by saying that the same code can be considered both correct and incorrect, depending on its purpose. A simple example is the use of an int variable for indexing elements of an array. If using this variable, we refer to an array of graphical windows, then everything is correct. There is no need, and it will not work with billions of windows. But indexing using a variable of type int to array elements in 64-bit math programs or databases may well be a problem when the number of elements goes out of the range 0..INT_MAX.
But there is one more, much more subtle reason for calling errors “potential”. The fact is, whether an error manifests itself or not depends not only on the input data, but also on the mood of the optimizer of the compiler. I have bypassed this topic for a long time, since most of these errors manifest themselves well in the debug-version, and are “potential” only in the release-versions. However, not every program compiled as debug can be debugged on large amounts of data. There is a situation when the debug-version is tested only on the most simple data sets. And load testing and end-user testing on real data is performed on release versions, where errors can be temporarily hidden. Therefore, I decided to share the knowledge that is. I hope I can convince you that when transferring a program to another platform, it is dangerous to rely only on the execution stage checks (unit tests, dynamic analysis, manual testing). You will say all this to promote the Viva64 tool. Yes, for this, but still listen to the scary stories that I will now tell you. I love to tell them.
- Why do you have two identical JMPs in your code in a row?
- What if the first does not work.
I first encountered the features of optimizing the Visual C ++ 2005 compiler when preparing the PortSample program. This is a project that is included in the Viva64 distribution kit and is intended to demonstrate all the errors diagnosed by the Viva64 analyzer. Examples that are contained in this project should work correctly in 32-bit mode and lead to errors in the 64-bit version. In the debug version, everything worked fine, but there were difficulties with the release version. The code that in the 64-bit mode was supposed to hang or crash worked successfully! The reason turned out to be optimization. The solution was the additional redundant complication of the example code and the placement of the volatile keywords, which you can observe in the PortSample project.
The same applies to Visual C ++ 2008. The code will of course be somewhat different, but all that will be written in this article can be attributed to both Visual C ++ 2005 and Visual C ++ 2008. And later in the article the differences will not be made.
If it seems to you that this is only good, if some errors do not manifest themselves, then rather drive this thought. The code with similar errors becomes extremely unstable. And the slightest code change, not directly related to the error, can lead to a change in behavior. Just in case, I emphasize that it is not the compiler that is to blame for this, but hidden code defects. Further, some phantom errors will be shown that disappear and appear in release versions with the slightest code changes and which can be hunted for a long time.
The chapter will be long and boring, so I'll start with a joke, which is its summary:
Ilya Muromets walked through the forest and came out into a clearing where the Serpent Gorynych sat. Ilya Muromets ran up to the Serpent Gorynych and cut a single head to him. And Snake Gorynych, instead of this head, has grown two. Ilya cut two heads, grew 4. Cut 4, grew 8 ... And so it went for an hour, two, three ... And then Ilya of Murom cut down Snake Gorynych 32768 heads and Snake Gorynych died, for he was 16-bit.
As in the joke, problems are rooted in type overflow, which may or may not occur depending on which code the compiler generates when optimization is enabled. Consider the first example of code that works in release mode, although it should not:
This code correctly fills the entire array with values, even if the array size is much larger than INT_MAX. Theoretically, this is impossible, since the variable index is of type int. After a while due to overflow, access to the elements by a negative index must occur. However, optimization leads to the generation of the following code:
As you can see, 64-bit registers are used and no overflow occurs. But we will make a very small correction of the code:
We assume that this is how the code looks more beautiful. Agree that it is functionally the same. But the result will be significant - the program will crash. Consider the code generated by the compiler:
The very overflow occurs, which should have been in the previous example. The register value r8d = 0x80000000 is expanded into rcx as 0xffffffff80000000. And as a result - writing outside the array.
Consider another optimization example and how easy it is to spoil everything. Example:
Assembly Code:
The compiler decided to use the 64-bit rdx register to store the variable index. As a result, the code can correctly handle arrays larger than UINT_MAX.
But the world is fragile. It is enough to complicate the code a little and it will become incorrect:
The use of the expression “index + = volatileVar;” instead of index ++ leads to the fact that 32-bit registers begin to take part in the code, due to which overflows occur:
Finally, I will give an interesting, but a great example. Unfortunately, I could not cut it to save the necessary behavior. It is precisely with this that such errors are dangerous, since it is impossible to predict what the simplest change in code leads to.
This code cannot correctly fill an array consisting of 50,000 * 50,000 elements. It is impossible for the reason that when calculating "int result = x + y * width;" an overflow should occur.
Thanks to the miracle, the array is still correctly filled in the release version. The UnsafeCalcIndex function is embedded inside the loop, 64-bit registers are used:
All this happened because the UnsafeCalcIndex function is simple and can be easily integrated. If you make it a little harder or the compiler thinks that you should not embed it, an error will occur that will manifest itself on large amounts of data.
Let's slightly modify (complicate) the UnsafeCalcIndex function. Please note that the function logic has not changed at all:
The result is a program crash when the array is exceeded:
I think you are already bored. I apologize. I just wanted to show how easily a 64-bit program can become inoperative after you make the most innocuous edits or compile it with another version of the compiler.
A program is a sequence of error handling.
(c) Unknown author
I suppose that many already existing 64-bit applications or those that will soon be transferred to 64-bit systems may unexpectedly start to present more and more unpleasant surprises. They can be identified a large number of defects with an increase in the amount of input data that was not available for processing on 32-bit systems. Hidden defects may unexpectedly manifest themselves in the course of further upgrading the program code or when changing the version of libraries or the compiler.
As in the history of the horse, the first impression can be deceptive. And the fact that your program has successfully started processing a large amount of data can only seem to you. There needs to be a much more thorough check that can accurately show whether your 64-bit horse really believes or not.
To be sure that the 64-bit program is correct, the most minimal step would be to use at all stages of testing not only the release, but also the debug version. Note that this is a necessary, but not sufficient condition. If the tests do not use data sets that, for example, do not use a large amount of RAM, the error may not manifest itself in the release and in the debug-version [ 5 ]. Extension of unit tests, expansion of data sets for load and manual testing are necessary. It is necessary to force the algorithms to process new combinations of data that are available only on 64-bit systems [ 6 ].
An alternative way to diagnose 64-bit errors is to use static analysis tools. It is much more radical and reliable than guessing whether enough tests have been added or not. It is convenient because it does not require the use of a debug version to grind gigabytes of data.
The point of the method is to perform a full analysis of the project once at program transfer and view all diagnostic messages about suspicious places in the code. People are scared away by a list of thousands and tens of thousands of warnings. But the total time immediately spent on their analysis will be an order of magnitude less than the correction over the years of the most diverse bug reports that have arisen from nowhere. These will be the phantoms described earlier. In addition, when you start working with the list of warnings, it will quickly become clear that most of them can be filtered out and analysis work will not be as much as it seems. In the future, you will only need to use static analysis, only for newly created code, which does not take much time.
From the toolkit for searching 64-bit phantoms, I will certainly offer the tool we are developing - Viva64 . By the way, this tool will soon be included in PVS-Studio, which will integrate all our static analysis tools.
To be more objective and I have been criticized less with this article as an advertisement, I will mention some other tools. It should be called Gimpel PC-Lint and Parasoft C ++ Test . They also implement rules for checking 64-bit errors, although in this they have less diagnostic capabilities than the highly specialized tool Viva64 [ 7 ]. There is also Abraxas CodeCheck , the new version of which (14.5) also provides diagnostic functions for 64-bit errors, but I do not have more detailed information.
I will be glad if the article will help you to more easily master new platforms, knowing what hidden problems may arise. Thanks for attention.
Introduction
The phenomenon of “Clever Hans,” Mr. Von Osten's horse, was described in 1911 [1]. Clever Hans was famous for being able to read and solve math problems, tapping the answer with his front hoof. Of course, there were many skeptics. Therefore, the ability of Hans was tested by a commission of experts, which found that the horse demonstrates them without the help of Mr. von Osten. But how could such a thing exist - human! - level of intelligence in a simple horse? The psychologist O. Pfangst carried out a series of experiments with extreme thoroughness, as a result of which he discovered that Hans received subtle, unintentional clues from those who asked him questions. For example, after Hans was asked about something, people fixed their eyes on his front hoof, with which the horse “answered”. But as soon as Hans hit the hoof the necessary number of times, the questioners raised their eyes or head a little bit in anticipation of the completion of his answer. And the horse, which was trained to notice and use these almost imperceptible movements for the observers, perceived them as signals to stop their actions. From the outside it always looked like the right answer to a question.
That was such a wonderful horse, who considered and solved puzzles, although he did not know how to do it. 64-bit programs have become digital horses of the beginning of the 21st century, many of which also cannot be counted, although they successfully pretend. Consider this phenomenon in more detail.
')
1. Potential errors
I am the author and co-author of a number of articles devoted to the problems of developing 64-bit applications. Articles can be found on our website: http://www.viva64.com/en/articles/64-bit-development . In these articles, I try to use the term “potential error” or “hidden error”, and not just “error” [ 2 , 3 , 4 ].
I explain this by saying that the same code can be considered both correct and incorrect, depending on its purpose. A simple example is the use of an int variable for indexing elements of an array. If using this variable, we refer to an array of graphical windows, then everything is correct. There is no need, and it will not work with billions of windows. But indexing using a variable of type int to array elements in 64-bit math programs or databases may well be a problem when the number of elements goes out of the range 0..INT_MAX.
But there is one more, much more subtle reason for calling errors “potential”. The fact is, whether an error manifests itself or not depends not only on the input data, but also on the mood of the optimizer of the compiler. I have bypassed this topic for a long time, since most of these errors manifest themselves well in the debug-version, and are “potential” only in the release-versions. However, not every program compiled as debug can be debugged on large amounts of data. There is a situation when the debug-version is tested only on the most simple data sets. And load testing and end-user testing on real data is performed on release versions, where errors can be temporarily hidden. Therefore, I decided to share the knowledge that is. I hope I can convince you that when transferring a program to another platform, it is dangerous to rely only on the execution stage checks (unit tests, dynamic analysis, manual testing). You will say all this to promote the Viva64 tool. Yes, for this, but still listen to the scary stories that I will now tell you. I love to tell them.
2. How it all began
- Why do you have two identical JMPs in your code in a row?
- What if the first does not work.
I first encountered the features of optimizing the Visual C ++ 2005 compiler when preparing the PortSample program. This is a project that is included in the Viva64 distribution kit and is intended to demonstrate all the errors diagnosed by the Viva64 analyzer. Examples that are contained in this project should work correctly in 32-bit mode and lead to errors in the 64-bit version. In the debug version, everything worked fine, but there were difficulties with the release version. The code that in the 64-bit mode was supposed to hang or crash worked successfully! The reason turned out to be optimization. The solution was the additional redundant complication of the example code and the placement of the volatile keywords, which you can observe in the PortSample project.
The same applies to Visual C ++ 2008. The code will of course be somewhat different, but all that will be written in this article can be attributed to both Visual C ++ 2005 and Visual C ++ 2008. And later in the article the differences will not be made.
If it seems to you that this is only good, if some errors do not manifest themselves, then rather drive this thought. The code with similar errors becomes extremely unstable. And the slightest code change, not directly related to the error, can lead to a change in behavior. Just in case, I emphasize that it is not the compiler that is to blame for this, but hidden code defects. Further, some phantom errors will be shown that disappear and appear in release versions with the slightest code changes and which can be hunted for a long time.
3. Phantoms
The chapter will be long and boring, so I'll start with a joke, which is its summary:
Ilya Muromets walked through the forest and came out into a clearing where the Serpent Gorynych sat. Ilya Muromets ran up to the Serpent Gorynych and cut a single head to him. And Snake Gorynych, instead of this head, has grown two. Ilya cut two heads, grew 4. Cut 4, grew 8 ... And so it went for an hour, two, three ... And then Ilya of Murom cut down Snake Gorynych 32768 heads and Snake Gorynych died, for he was 16-bit.
As in the joke, problems are rooted in type overflow, which may or may not occur depending on which code the compiler generates when optimization is enabled. Consider the first example of code that works in release mode, although it should not:
int index = 0; size_t arraySize = ...; for (size_t i = 0; i! = arraySize; i ++) array [index ++] = BYTE (i); |
0000000140001040 mov byte ptr [rcx + rax], cl 0000000140001043 add rcx, 1 0000000140001047 cmp rcx, rbx 000000014000104A jne wmain + 40h (140001040h) |
int index = 0;
for (size_t i = 0; i! = arraySize; i ++)
{
array [index] = BYTE (index);
++ index;
}
|
0000000140001040 movsxd rcx, r8d 0000000140001043 mov byte ptr [rcx + rbx], r8b 0000000140001047 add r8d, 1 000000014000104B sub rax, 1 000000014000104F jne wmain + 40h (140001040h) |
Consider another optimization example and how easy it is to spoil everything. Example:
unsigned index = 0;
for (size_t i = 0; i! = arraySize; ++ i) {
array [index ++] = 1;
if (array [i]! = 1) {
printf ("Error \ n");
break;
}
}
|
0000000140001040 mov byte ptr [rdx], 1 0000000140001043 add rdx, 1 0000000140001047 cmp byte ptr [rcx + rax], 1 000000014000104B jne wmain + 58h (140001058h) 000000014000104D add rcx, 1 0000000140001051 cmp rcx, rdi 0000000140001054 jne wmain + 40h (140001040h) |
But the world is fragile. It is enough to complicate the code a little and it will become incorrect:
volatile unsigned volatileVar = 1;
...
unsigned index = 0;
for (size_t i = 0; i! = arraySize; ++ i) {
array [index] = 1;
index + = volatileVar;
if (array [i]! = 1) {
printf ("Error \ n");
break;
}
}
|
0000000140001040 mov ecx, r8d 0000000140001043 add r8d, dword ptr [volatileVar (140003020h)] 000000014000104A mov byte ptr [rcx + rax], 1 000000014000104E cmp byte ptr [rdx + rax], 1 0000000140001052 jne wmain + 5Fh (14000105Fh) 0000000140001054 add rdx, 1 0000000140001058 cmp rdx, rdi 000000014000105B jne wmain + 40h (140001040h) |
ptrdiff_t UnsafeCalcIndex (int x, int y, int width) {
int result = x + y * width;
return result;
} |
...
int domainWidth = 50000;
int domainHeght = 50000;
for (int x = 0; x! = domainWidth; ++ x)
for (int y = 0; y! = domainHeght; ++ y)
array [UnsafeCalcIndex (x, y, domainWidth)] = 1;
|
Thanks to the miracle, the array is still correctly filled in the release version. The UnsafeCalcIndex function is embedded inside the loop, 64-bit registers are used:
0000000140001052 test rsi, rsi 0000000140001055 je wmain + 6Ch (14000106Ch) 0000000140001057 lea rcx, [r9 + rax] 000000014000105B mov rdx, rsi 000000014000105E xchg ax, ax 0000000140001060 mov byte ptr [rcx], 1 0000000140001063 add rcx, rbx 0000000140001066 sub rdx, 1 000000014000106A jne wmain + 60h (140001060h) 000000014000106C add r9.1 0000000140001070 cmp r9, rbx 0000000140001073 jne wmain + 52h (140001052h) |
Let's slightly modify (complicate) the UnsafeCalcIndex function. Please note that the function logic has not changed at all:
ptrdiff_t UnsafeCalcIndex (int x, int y, int width) {
int result = 0;
if (width! = 0)
result = y * width;
return result + x;
}
|
0000000140001050 test esi, esi 0000000140001052 je wmain + 7Ah (14000107Ah) 0000000140001054 mov r8d, ecx 0000000140001057 mov r9d, esi 000000014000105A xchg ax, ax 000000014000105D xchg ax, ax 0000000140001060 mov eax, ecx 0000000140001062 test ebx, ebx 0000000140001064 cmovne eax, r8d 0000000140001068 add r8d, ebx 000000014000106B cdqe 000000014000106D add rax, rdx 0000000140001070 sub r9,1 0000000140001074 mov byte ptr [rax + rdi], 1 0000000140001078 jne wmain + 60h (140001060h) 000000014000107A add rdx, 1 000000014000107E cmp rdx, r12 0000000140001081 jne wmain + 50h (140001050h) |
4. Diagnose potential errors
A program is a sequence of error handling.
(c) Unknown author
I suppose that many already existing 64-bit applications or those that will soon be transferred to 64-bit systems may unexpectedly start to present more and more unpleasant surprises. They can be identified a large number of defects with an increase in the amount of input data that was not available for processing on 32-bit systems. Hidden defects may unexpectedly manifest themselves in the course of further upgrading the program code or when changing the version of libraries or the compiler.
As in the history of the horse, the first impression can be deceptive. And the fact that your program has successfully started processing a large amount of data can only seem to you. There needs to be a much more thorough check that can accurately show whether your 64-bit horse really believes or not.
To be sure that the 64-bit program is correct, the most minimal step would be to use at all stages of testing not only the release, but also the debug version. Note that this is a necessary, but not sufficient condition. If the tests do not use data sets that, for example, do not use a large amount of RAM, the error may not manifest itself in the release and in the debug-version [ 5 ]. Extension of unit tests, expansion of data sets for load and manual testing are necessary. It is necessary to force the algorithms to process new combinations of data that are available only on 64-bit systems [ 6 ].
An alternative way to diagnose 64-bit errors is to use static analysis tools. It is much more radical and reliable than guessing whether enough tests have been added or not. It is convenient because it does not require the use of a debug version to grind gigabytes of data.
The point of the method is to perform a full analysis of the project once at program transfer and view all diagnostic messages about suspicious places in the code. People are scared away by a list of thousands and tens of thousands of warnings. But the total time immediately spent on their analysis will be an order of magnitude less than the correction over the years of the most diverse bug reports that have arisen from nowhere. These will be the phantoms described earlier. In addition, when you start working with the list of warnings, it will quickly become clear that most of them can be filtered out and analysis work will not be as much as it seems. In the future, you will only need to use static analysis, only for newly created code, which does not take much time.
From the toolkit for searching 64-bit phantoms, I will certainly offer the tool we are developing - Viva64 . By the way, this tool will soon be included in PVS-Studio, which will integrate all our static analysis tools.
To be more objective and I have been criticized less with this article as an advertisement, I will mention some other tools. It should be called Gimpel PC-Lint and Parasoft C ++ Test . They also implement rules for checking 64-bit errors, although in this they have less diagnostic capabilities than the highly specialized tool Viva64 [ 7 ]. There is also Abraxas CodeCheck , the new version of which (14.5) also provides diagnostic functions for 64-bit errors, but I do not have more detailed information.
Conclusion
I will be glad if the article will help you to more easily master new platforms, knowing what hidden problems may arise. Thanks for attention.
Bibliographic list
- Roger R. Hawk. 40 studies that rocked the psychology. 4th int. ed. SPb .: Prime-Eurosnak, 2006, ISBN: 5-93878-237-6.
- Andrey Karpov. 64 bits, / Wp64, Visual Studio 2008, Viva64 and everything, everything, everything ... http://www.viva64.com/art-1-2-253695945.html
- Andrey Karpov, Evgeny Ryzhkov. Static code analysis for verification of 64-bit applications. http://www.viva64.com/art-1-1-1630333432.html
- Andrey Karpov. 7 steps to transfer the program to a 64-bit system. http://www.viva64.com/art-1-1-1148261225.html
- Andrey Karpov, Evgeny Ryzhkov. 20 issues of porting C ++ code on a 64-bit platform. http://www.viva64.com/art-1-1-1958348565.html
- Andrey Karpov, Evgeny Ryzhkov. Search traps in C / C ++ code when porting applications for the 64-bit version of Windows. http://www.viva64.com/art-1-1-329725213.html
- Andrey Karpov. Comparison of the diagnostic capabilities of analyzers when checking 64-bit code. http://www.viva64.com/art-1-1-1441719613.html
Source: https://habr.com/ru/post/81222/
All Articles