How to detect overflow of 32-bit variable in long cycles in a 64-bit program
One of the problems faced by developers of 64-bit applications is the overflow of 32-bit variables in very long cycles. The PVS-Studio code analyzer (Viva64 diagnostic kit) does a good job with this task. There are a number of questions on StackOverflow.com on variable overflow in cycles. But since my answers may be considered purely advertising, and not as useful information, I decided to describe the possibilities of PVS-Studio in the article.
A typical construction of the C / C ++ language is a loop. When porting programs to the 64-bit architecture, the cycles unexpectedly become a weak point, since when developing the code, it was rare for anyone to think in advance what would happen if the program had to perform billions of iterations.
In our articles we call such situations 64-bit errors. In fact, these are just mistakes. But their peculiarity is that they only manifest themselves in the 64-bit program. In a 32-bit program, such long cycles simply do not occur, and it is impossible to create an array, with the number of elements greater than INT_MAX .
So the problem. In a 64-bit program, an overflow of integer 32-bit types occurs. We are talking about such types as int , unsigned , long (if it is Win64 ). It is necessary to somehow identify all such dangerous places. This can be done by the PVS-Studio analyzer, which we will talk about.
')
Consider various options for overflow of variables associated with long cycles.
The first situation. Described on the StackOverflow website here: " How can elusive 64-bit portability issues be detected? ". There is a code like the following:
The program handles very long lines. In a 32-bit program, the string length cannot exceed INT_MAX . Therefore, no error can occur. Yes, the program cannot process any large amounts of data, but this is not an error, but a limitation of the capabilities of the 32-bit architecture.
In a 64-bit program, the length of the string may already be longer than INT_MAX and, accordingly, the variable n may overflow. This will lead to undefined program behavior. Do not think that overflow will simply turn the number 2147483647 into -2147483648. It is precisely indefinite behavior and it is impossible to predict the consequences. For those who do not believe that overflow of the sign variable leads to unexpected changes in the program, I suggest to get acquainted with my article " Undefined behavior closer than you think ."
So, we need to find out that the variable n can overflow. There is nothing easier. Run PVS-Studio and get a warning:
V127 An overflow of 32-bit 'n' variable is possible inside a cycle which utilizes a memsize-type loop counter. mfcapplication2dlg.cpp 190
If you change the type of the variable n to size_t , then the error, and accordingly the analyzer message, will disappear.
It also provides another example of code that needs to be revealed:
Run PVS-Studio and again get the warning V127:
V127 An overflow of 32-bit i 'variable is possible inside a long cycle which utilizes a memsize-type loop counter. mfcapplication2dlg.cpp 201
The topic on StackOverflow also raises the question of what to do if the codebase is huge and how to find all such errors.
As you can see, these errors can be detected with the help of the PVS-Studio static code analyzer. And this is the only way to cope with a large project. It should also be noted that PVS-Studio provides a convenient interface for working with a large number of diagnostic messages. You can interactively filter messages, mark them as false and so on. However, the description of the capabilities of PVS-Studio is beyond the scope of this note. For those who are interested in the instrument, I suggest to get acquainted with the following materials:
I also note that we have the experience of porting a large project to 9 million lines of code on a 64-bit platform. And PVS-Studio showed itself perfectly in the work on this project.
Let's move on to the next topic on StackOverflow: " Can Klocwork (or other tools) be aware of types, typedefs and # define directives? ".
As I understand it, a person set for himself the task of finding a suitable tool for finding all cycles organized with the help of 32-bit cycle counters. Those. in other words, where int is used .
This task is somewhat different from the previous one. But such cycles really should be looked for. After all, using the variable int it is impossible to process huge arrays and so on.
A man came up to the solution of the problem wrong. This is not his fault. He simply does not know about the existence of PVS-Studio. Now you will understand why I say that.
So he plans to look for:
It's horrible. We'll have to see an incredible number of cycles, in order to understand whether they can lead to an error or not. This is a great job and you can hardly do it without losing attention. Most likely to be missed many dangerous places.
To edit all cycles in a row, replacing int , for example, with intptr_t is also a bad option. This is a lot of work and code changes.
PVS-Studio analyzer can help. He will not find the above cycle. Because it is not necessary to look for him. There is simply no room for error. The loop performs 10 iterations. And no overflow in it can not be. So there is nothing for the programmer to waste time on this piece of code.
But the analyzer will indicate the following cycles:
The analyzer will immediately issue 2 warnings. The first warns that in the expression the 32-bit type is compared with the memsize-type :
V104 Implicit conversion of the i 'm to memsize type in an arithmetic expression: i <v.size () mfcapplication2dlg.cpp 210
Indeed, the type of the variable i is not suitable for organizing long cycles.
The second warning says that it’s strange to use a 32-bit variable as an index. If the array is large, then the code is incorrect.
V108 Incorrect index type: v [not a memsize-type]. Use memsize type instead. mfcapplication2dlg.cpp 211
The correct code should look like this:
The code has become long and ugly, so there is a temptation to use the auto keyword, but this cannot be done - the code modified in this way is incorrect again:
Since the constant 0 is of type int , the variable i will also be of type int . And we went back to where we started. By the way, once we are talking about new features of the C ++ standard, I suggest taking a look at the article " C ++ 11 and 64-bit errors ."
I think you can compromise and write not perfect, but the correct code:
Note. Of course, it would be even more correct to use iterators or the fill () algorithm. But we are talking about looking for overflow of 32-bit variables in old programs. Therefore, I do not consider such options for correcting the code. This is a completely different topic.
I want to emphasize that the analyzer is smart enough and is trying not to disturb the programmer for nothing. For example, it will not issue a warning if it sees that a small array is being processed:
Conclusion
PVS-Studio analyzer is the leader in searching for 64-bit errors. Initially, it was created to help programmers in porting their programs to 64-bit systems. At that time, it was also called Viva64. This is only later, it turned into a general-purpose analyzer, but the existing 64-bit diagnostics have not disappeared anywhere and are also ready to help you.
Download the demo version here .
Read more about the development of 64-bit programs .
A typical construction of the C / C ++ language is a loop. When porting programs to the 64-bit architecture, the cycles unexpectedly become a weak point, since when developing the code, it was rare for anyone to think in advance what would happen if the program had to perform billions of iterations.
In our articles we call such situations 64-bit errors. In fact, these are just mistakes. But their peculiarity is that they only manifest themselves in the 64-bit program. In a 32-bit program, such long cycles simply do not occur, and it is impossible to create an array, with the number of elements greater than INT_MAX .
So the problem. In a 64-bit program, an overflow of integer 32-bit types occurs. We are talking about such types as int , unsigned , long (if it is Win64 ). It is necessary to somehow identify all such dangerous places. This can be done by the PVS-Studio analyzer, which we will talk about.
')
Consider various options for overflow of variables associated with long cycles.
The first situation. Described on the StackOverflow website here: " How can elusive 64-bit portability issues be detected? ". There is a code like the following:
int n; size_t pos, npos; /* ... initialization ... */ while((pos = find(ch, start)) != npos) { /* ... advance start position ... */ n++; // this will overflow if the loop iterates too many times } The program handles very long lines. In a 32-bit program, the string length cannot exceed INT_MAX . Therefore, no error can occur. Yes, the program cannot process any large amounts of data, but this is not an error, but a limitation of the capabilities of the 32-bit architecture.
In a 64-bit program, the length of the string may already be longer than INT_MAX and, accordingly, the variable n may overflow. This will lead to undefined program behavior. Do not think that overflow will simply turn the number 2147483647 into -2147483648. It is precisely indefinite behavior and it is impossible to predict the consequences. For those who do not believe that overflow of the sign variable leads to unexpected changes in the program, I suggest to get acquainted with my article " Undefined behavior closer than you think ."
So, we need to find out that the variable n can overflow. There is nothing easier. Run PVS-Studio and get a warning:
V127 An overflow of 32-bit 'n' variable is possible inside a cycle which utilizes a memsize-type loop counter. mfcapplication2dlg.cpp 190
If you change the type of the variable n to size_t , then the error, and accordingly the analyzer message, will disappear.
It also provides another example of code that needs to be revealed:
int i = 0; for (iter = c.begin(); iter != c.end(); iter++, i++) { /* ... */ }
Run PVS-Studio and again get the warning V127:
V127 An overflow of 32-bit i 'variable is possible inside a long cycle which utilizes a memsize-type loop counter. mfcapplication2dlg.cpp 201
The topic on StackOverflow also raises the question of what to do if the codebase is huge and how to find all such errors.
As you can see, these errors can be detected with the help of the PVS-Studio static code analyzer. And this is the only way to cope with a large project. It should also be noted that PVS-Studio provides a convenient interface for working with a large number of diagnostic messages. You can interactively filter messages, mark them as false and so on. However, the description of the capabilities of PVS-Studio is beyond the scope of this note. For those who are interested in the instrument, I suggest to get acquainted with the following materials:
- PVS-Studio article for Visual C ++ .
- Article Practice of using the PVS-Studio analyzer .
- Documentation
I also note that we have the experience of porting a large project to 9 million lines of code on a 64-bit platform. And PVS-Studio showed itself perfectly in the work on this project.
Let's move on to the next topic on StackOverflow: " Can Klocwork (or other tools) be aware of types, typedefs and # define directives? ".
As I understand it, a person set for himself the task of finding a suitable tool for finding all cycles organized with the help of 32-bit cycle counters. Those. in other words, where int is used .
This task is somewhat different from the previous one. But such cycles really should be looked for. After all, using the variable int it is impossible to process huge arrays and so on.
A man came up to the solution of the problem wrong. This is not his fault. He simply does not know about the existence of PVS-Studio. Now you will understand why I say that.
So he plans to look for:
for (int i = 0; i < 10; i++) // ...
It's horrible. We'll have to see an incredible number of cycles, in order to understand whether they can lead to an error or not. This is a great job and you can hardly do it without losing attention. Most likely to be missed many dangerous places.
To edit all cycles in a row, replacing int , for example, with intptr_t is also a bad option. This is a lot of work and code changes.
PVS-Studio analyzer can help. He will not find the above cycle. Because it is not necessary to look for him. There is simply no room for error. The loop performs 10 iterations. And no overflow in it can not be. So there is nothing for the programmer to waste time on this piece of code.
But the analyzer will indicate the following cycles:
void Foo(std::vector<float> &v) { for (int i = 0; i < v.size(); i++) v[i] = 1.0; }
The analyzer will immediately issue 2 warnings. The first warns that in the expression the 32-bit type is compared with the memsize-type :
V104 Implicit conversion of the i 'm to memsize type in an arithmetic expression: i <v.size () mfcapplication2dlg.cpp 210
Indeed, the type of the variable i is not suitable for organizing long cycles.
The second warning says that it’s strange to use a 32-bit variable as an index. If the array is large, then the code is incorrect.
V108 Incorrect index type: v [not a memsize-type]. Use memsize type instead. mfcapplication2dlg.cpp 211
The correct code should look like this:
void Foo(std::vector<float> &v) { for (std::vector<float>::size_type i = 0; i < v.size(); i++) v[i] = 1.0; }
The code has become long and ugly, so there is a temptation to use the auto keyword, but this cannot be done - the code modified in this way is incorrect again:
for (auto i = 0; i < v.size(); i++) v[i] = 1.0;
Since the constant 0 is of type int , the variable i will also be of type int . And we went back to where we started. By the way, once we are talking about new features of the C ++ standard, I suggest taking a look at the article " C ++ 11 and 64-bit errors ."
I think you can compromise and write not perfect, but the correct code:
for (size_t i = 0; i < v.size(); i++) v[i] = 1.0;
Note. Of course, it would be even more correct to use iterators or the fill () algorithm. But we are talking about looking for overflow of 32-bit variables in old programs. Therefore, I do not consider such options for correcting the code. This is a completely different topic.
I want to emphasize that the analyzer is smart enough and is trying not to disturb the programmer for nothing. For example, it will not issue a warning if it sees that a small array is being processed:
void Foo(int n) { float A[100]; for (int i = 0; i < n; i++) A[i] = 1.0; }
Conclusion
PVS-Studio analyzer is the leader in searching for 64-bit errors. Initially, it was created to help programmers in porting their programs to 64-bit systems. At that time, it was also called Viva64. This is only later, it turned into a general-purpose analyzer, but the existing 64-bit diagnostics have not disappeared anywhere and are also ready to help you.
Download the demo version here .
Read more about the development of 64-bit programs .
Source: https://habr.com/ru/post/279841/
All Articles