Additional Memory Issues

Some memory errors were reported when performing memory testing on the current source.  Checking previous commits back to the last tag reported the same memory errors, which was strange because the previous commits successfully passed the memory tests.  The memory errors were reported in libglib2.0.

I remembered that there was just an update for this library within the past week, which explained why these memory errors were previously not reported.  There must be some interaction between the Qt library and the new version of this library.  These errors were added to the error suppression file so that they will no longer be reported.  These extra errors will not affect the memory tests if the update for this library is not applied.

[commit 7ccd9ac05f]

Old Translator Issues With Token Caching

While debugging the new PRINT translate routine, I realized that the old translator routines were never tested with new token caching and error reporting code, because when they were, crashes and errors occurred.  Two small problems were found and were corrected.

The first issue occurred when an error is detected and the error token was not the current token obtained from the parser (meaning the error token had already been added to the output and cannot be deleted).  The old translator routine obtained a new token and copied the error token into it before calling the set error token routine, which called the output list set error routine and then deleted the token.  When the token was copied into the new token obtained, the index of the original token was copied over the new token's index confusing the used token handling.  This was corrected by calling the output list set error routine directly (which only grabs the column and length of the error token) so no temporary token is needed.

The second issue occurred when there was a REMARK operator (') at the beginning of a line.  The Null token put on the bottom of the hold stack was not removed.  This was detected as a token leak and the detection code reported and deleted the token.  Unfortunately, the translator still had the token on the hold stack.  This did not cause a problem until the next command with an error was processed.  When an error occurs, the the hold stack is empty and its tokens are deleted.  When it got to the deleted Null token, the index was garbage (because the memory for the token had been reused) and a segmentation fault occurred.

The REMARK operator token handler was modified to pop and delete the Null token from the hold stack if currently in command mode.  If not in command mode, then another part of the translator correctly handled the the Null token.  Curiously for this situation, the EOL token at the end of the line is never obtained and processed.  Therefore, this fix is a hack, but since the old translator routines will be abandoned, there is no reason for a correct fix.

One last minor issue was that when token leaks or extra deletes were reported, if the token was a Null or End-of-line token, a blank token was output with just an index.  The "NULL" and "EOL" strings were added to the debug name entry in the table to identify these blank tokens.

[commit cf93288fcb]

Extra Token Delete Detection

The other type of token allocation error that can occur is when a token that has already been deleted is deleted again.  This is a less common problem, but can still could occur none the less.  Extra token delete detection was also previously implemented, but removed.  The original implementation contained a list of tokens deleted extra times.  A copy of the token was appended to the list.

This time around, the text of the token (by using the text access function) along with its index (as part of the string) is saved in a list of strings of deleted tokens.  When it comes to to report these errors, each string in the list is output.  In the reimplemented delete operation function, before the token is marked a unused in the used token vector (its pointer set to null), if the token is already marked as unused, its index and text is appended to the deleted list instead and the token is not pushed onto the free token stack (it is already there).

A new private DeletedList class was  implemented inside the Token class.  The destructor is called automatically upon termination of the application and any extra token deletes are reported. This class also contains a report errors function that does the work of outputting the deleted list to the standard error output stream and clears the list afterward.  The destructor calls this function.

Again, a separate function was implemented so that it can be called at the end of each line translated in test mode and extra token deletes for that specific line are reported with the line.  For non-test (GUI) mode, any extra token deletes are reported when the application terminates.

Token (Memory) Leak Detection

While implementing the token caching, I thought it would be extremely helpful to put back some token leak detection, a common time consuming problem seen during debugging of the new translator routines.  Leak detection was previously implemented, but removed during the Qt transition.  According to the post on October 28, 2012, this was due to obscure compiler errors.  Since valgrind was being used for memory leak detection by then, this code was removed.  The log for this commit did not provide any additional clues to the issues other than to say Qt does not interface well to self implemented new and delete operators (?).

The original token leak detection consisted of a static list of used tokens and each token contained a pointer into this list.  This was easy to implemented with how the original List class was designed, but the QList class had no easy equivalent (using an iterator did not work).  I suspect this partly caused the problem, which may also have had something to do with the way members are initialized by the constructor when a new instance is created and having a Qt member complicated things.  Anyway, a new easier method of keep track of used tokens was implemented this time around that did not cause any problems.

A plain integer index member was added to the Token class.  Every token allocated gets a unique index number, which the token will have through the life of the application.  The index values assigned start at zero and each additional token allocated gets the next index value.  This index is used to index into a QVector of token pointers.

When a new token is allocated, the index is set to the size of this used token vector, and then the token is appended to the vector.  In other words, the index points to its corresponding element in this vector.  When a token pointer is popped from the free token stack, the element corresponding to the token is set to the token pointer.  When a token is deleted, the element corresponding to the token is set to a null pointer to indicate the token is not currently used (it is in the free token stack).

A token pointer was used for this vector instead of a simple boolean flag (for indicating a token was used), so that when it came time to see if there are any tokens used that have not been freed (the element in the vector contains a non-null token pointer), the token pointer can be used to print information about the token (type, code, string, etc.).

A new private UsedVector class was implemented inside the Token class, similar to the FreeStack private class.  The destructor is called automatically upon termination of the application and any token leaks are reported and the tokens deleted so that valgrind does not also report memory leaks.  This class also contains a report errors function that does the work of scanning the vector and reporting any token leak errors found to the standard error output stream and deletes the tokens.  The destructor calls this function.

A separate function was implemented so that it can be called at the end of each line translated in test mode and token leaks for that specific line are reported with the line.  This does not interfere with the test scripts since the errors are output to the standard error stream, which is not captured in the output that gets compared with the expected results files.  Once a test is seen to contain errors, it can be rerun from the command line to the standard output to see which test statements caused the errors.  Having the errors output with the test lines saves debugging time in having to identify which test statement caused the error.

For non-test (GUI) mode, any token leaks are reported when the application terminates, though if not run from the command line, these errors will not be seen.  This should not be an issue because any token leaks should have been eliminated by this time.

Token Caching (With Error Checking)

The PRINT translation will involve many token deletes for unneeded tokens (like semicolons) but also many new tokens (to hold the specific data type print codes).  More on the redesign PRINT translation in an upcoming post, but it is desirable to reuse tokens as much as possible instead of repeatedly using the free memory heap, which can get fragmented with many allocations and deletions requiring time consuming garbage collection.  Other commands (like INPUT) will also require this reuse capability.

Instead of some type of token saving code in each command translation routine as needed, a global method of caching tokens was implemented.  This was accomplished by reimplementing the new and delete operators of the Token class.  For the delete operator, instead of simply freeing the memory of the token, the pointer to the token is saved on a free token stack.  For the new operator, if the free token stack is not empty, a pointer to a token is popped from this stack, otherwise a new token is allocated using the global new operator.

The free token stack was implemented as a private class based on the QStack class containing a reimplemented destructor function, which deletes all the tokens on the free stack.  The destructor is called when the free stack goes out of scope, which occurs when the application terminates.

During the implementation and debugging of LET statements, one area that was time consuming was tracking down memory leak errors, mostly related to tokens.  (Other leaks were easy to identify and correct.)  First the test statement causing the problem had to be identified (time consuming), then the debugger had to be run to identify what was in the token that was not deleted so that the problem could be corrected (also time consuming).  Missed through all of this was the token leak detection that was removed a while ago due to issues with the Qt libraries during the Qt transition.

A new token leak detection scheme was implemented along with detection of tokens that are deleted more than once.  More details of these schemes in following posts.  Any token leaks and extra token deletes are reported after each translator test line is translated.  This will save the time to identify which statement caused errors.  The text of the token is output for each error along with its index (will be detailed in the next post).  Any token errors are also reported at application termination for non-test mode.

[commit 5fa1780cda]

Memory Testing / Minor Memory Leak

Since all of the tests are now working with the new translator (excluding the commands not yet implemented), it seemed appropriate to change the memtestn script to run all of the tests.  After changing this script, two memory leaks were discovered in translator tests #7 (Errors) and #9 (Semicolon Errors).  The memory leak determined to be occurring with sub-string assignment statements that contained an error.

The memory leak occurred because an RPN item was allocated for the sub-string assignment token, which is not appended immediately to the RPN output list.  The RPN item is left on the done stack, which the LET translate routine pops and pushes it's token to the LET stack and then deletes the RPN item.  However, if the next token that should be a comma or equal token is not or a parser error occurred, then this does not occur.  The error clean up code assumes that all RPN items on the done stack have been added to the RPN output list, so only the items in the output list are deleted.

This problem was corrected by slightly rearranging the code in the LET translate routine where if there is an error with the comma or equal token, and the top of the done stack contains a sub-string assignment token (that has not been added to the RPN output list), then the done item on top of the done stack is popped and deleted, which deletes the RPN item and its token(s).  With this change, all of the tests with the new translator have no memory errors.

[commit 229af22a78]

New Translator – Memory Leaks

Several of the error conditions caused a memory leak because the token at which the error occurred was not deleted.  The error token can't just be deleted because it may be in the RPN output list.  Tokens in the output list will be deleted when the list is clears when an error is detected.  A method was needed to determine when an error token should be deleted.

This was accomplished by added a new UnUsed sub-code.  At the locations where an error detected, the routine setting the error needs to set this sub-code if the token has not been added to the output list.  This sub-code was set in two places, one in the get operand routine when there is a command or operator token, and the other in the translate routine that called the get expression routine when the terminating token is not the end-of-line token.

One other problem that caused a uninitialized variable used error from valgrind was also in the translate routine when the terminating token is checked for the end-of-line token.  The check also needed to test if the token has a table entry before checking the token for the end-of-line code (non-table entry tokens don't have a code).

[commit a9b45327d6]

Qt Application – Memory Errors

A simply program was created that containing a single main() function with a QApplication instance, a single shot timer to force the program to quit and a call to the Qt event processing executive.  This simply program also had the same memory issues, so this is some sort of issue with Qt, and probably explains why the External Errors are disabled by default in the Analyzer.

The valgrind utility has an option to disable (suppress) errors from being reported.  The ‑‑gen‑suppressions=all option can be used to generate a list of errors to suppress.  These error suppressions (extracted from the output - between the sets of braces) were put into the ibcp.supp file in the test sub-directory.  The memory test script was modified with the ‑‑suppression=$dir/ibcp.supp option where $dir is set to the test sub-directory in the source directory within the script.

This error suppression file can also be added to the Analyzer in QtCreator by going to Options... in the Tools menu and going to the Analyzer options page.  In the Memory Analysis Options section, the Add... button is used to select the ibcp.supp file.  (Note: this is only for running on Linux.)

The commented static linking commands in the CMake file were removed.  Since the executable is now going to require two Qt library files, there is no longer any reason to link the MinGW libraries required by the executable statically.  All the required dynamic link libraries will be included in future releases of the binary zip file for Windows.  If I read the licensing correctly, this is permitted if the libraries were not built from custom source.

[commit  af6faac469]

String to Number Conversions

As the modified Parser code was being tested, a weird memory issues was reported by valgrind.  The problems occurred with the toInt() and toDouble() functions of QString.  The problem was duplicated with a very simple program:

#include <QString>
int main(void) {
    qDebug("%d", QString("123").toInt();
}

The same issue occurs if the program above is changed to double with toDouble().  No reason for this error could be found.  However, when this program is turned into a Qt console application, the error no long occurred.  But this same thing applied to the ibcp program did not eliminate the error.  Click Continue... for how to build and run this program from the command line to demonstrate the memory issue (requires Linux with Qt and valgrind installed).

No solution was found for this problem.  When the program was changed from QString to QByteArray, which also contains these same two functions, no memory issue was reported.  Therefore, as a temporary solution, the string to convert is converted to a QByteArray.  A QByteArray was declared and the QString to convert was appended to it.

Third Translator Memory Issue

The memory issue reported for translator test 7 was the same message as test 6 except on a different line, which was another if statement.  Again through the process of elimination, the statement causing the error was identified to be MID$(A$ B, which is expected to produce an expected comma error at the B token.

After briefly studying this if statement, the problem was identified and is similar to the previous problem.  This if statement, in the process binary operator routine, was checking if the token (within a sub-string assignment) was not a comma.  Again, it should not have been checking the token code before checking that the code was valid (since not all token types have a code).  The B token is an identifier with no parentheses token type and code is not used.

The if statement was corrected by adding a check if the token has a table entry (and therefore a valid code) and it is not a comma.  Now all the memory issues were resolved.  I also now understand what the Conditional jump or move depends on unintialised values(s) error is indicating.  Apparently, the Analyzer (valgrind) is checking for more than just memory leaks, it is also checking when a variable is being accessed, but it hasn't been initialized, which was the case for these two if statements.

Rechecking all the tests, all the memory issues were resolved.  However, upon running the regression tests, translator test 7 was now failing.  The problem occurred with the statement above, which was now reporting an expected operator or comma error, which was wrong because with a sub-string assignments, an operator is not allowed after the string variable identifier.

The if statement was modified so that either the token does not have a table entry or the token is not a comma.  All tests now pass.  To simplify (and automate) this memory testing, a new memtest script was created, but only for Linux as it requires the valgrind program.  This new script is based on the regtest script and also checks the regression test results along with checking for memory issues.  Now back to replacing the List class with the QList class...

[commit 1d427d7d98] [commit da0014b34d]

Second Translator Memory Issue

While the first memory issue was a simple memory leak, the second issue was much more difficult to resolve.  The issue on translator test 6 was reported as a Conditional jump or move depends on unintialised values(s).  Clicking on this showed the source line and another message reporting Uninitialised value was created by a heap allocation.  The line for this message was in the token new function where the memory for the token is allocated.  Curious that the token allocation checks were not reporting any token leaks.

Through the process of elimination, the statement (out of 42) causing the error was identified to be PRINT A(TAB(10)).  Looking at the line indicated by the first message (an if statement) did not make it clear what the issue was.  So the code was stepped through with the debugger to identify the problem, which was caused by an incorrect check for the item on top of the hold stack, which happen to be the line reported with a problem.

This if statement checks if a print-only function is found in an expression, which should be reported as an error since these functions are only valid in a PRINT command.  The check is for either the current command is not a PRINT command or the token on top of the hold stack is not the null token (any other token indicates the print-only function is in a parentheses, array or function - an error).

The problem was with the null token check as it was only checking if the code of the token was not the null code.  However, not every token type has a valid code, specifically, constants, identifiers (with and without parentheses), and user defined functions (preceded by FN with and without parentheses).  This check was replaced with a call to a new token function that checks to see if the token is a null token, which first checks if the token has a table entry (and therefore a code) and then checks the code.

This corrected the problem with translator test 6.  All the expression and translator tests were rechecked with the Analyzer.  Translator test 7 was still reporting a memory issue.

First Translator Memory Leak

The first memory leak, which occurred on every expression and translator test, was easy to identify and correct as the Analyzer pointed directly to the problem.  The memory issue was reported in the translator start() function with the RPN (reverse polish notation) list allocated there.

For expression test 1, 13 blocks were reported lost, which exactly coincided with the number of test expressions.  This made it obvious that the memory allocated for the RPN list object was not being released.  In the translate input routine, after the resulting tokens in the RPN list were output, the memory allocated for each token was released.  However, the RPN list object itself was not released.

After the correction, all the expression and translator tests were rechecked with the Analyzer.  Translator tests 6 and 7 were still reporting memory issues.

Finding Memory Leaks (Linux)

QtCreator can be used to find memory leaks using the Analyze mode.  This requires the valgrind program, which can be installed via the valgrind package on Ubuntu based distros.  Unfortunately it looks like this program has not been ported to Windows (MinGW), so Windows developers are out of luck (at least when using MinGW with the Qt SDK).

In order to use valgrind, the program to check must be compiled with debugging information.  To do this with CMake under QtCreator, in the Run CMake dialog, the Arguments line needs to be set to ‑DCMAKE_BUILD_TYPE=Debug.  This is a nuisance because it needs to be done every time CMake is run the first time and there appears to be no way to automate this inside QtCreator.  So an alternate scheme was devised using CMake (will be described in the next post).

Once Analyze mode is selected (by the icon on the side panel or Ctrl+6), the Analyzer panel will appear.  In this panel, the mode needs to be changed from QML Profiler to Valgrind Memory Analyzer.  The program is started using the start (play) icon (left side of Analyzer panel toolbar).  Once the program ends, any memory issues will be reported.

After using the Analyzer to learn about list element deallocation, I thought it might be a good idea to check the ibcp program for any memory issues.  There is already an implementation to detect token memory leaks accomplished by overloading the new and delete operators for the Token structure, but there are many other memory allocation operations in the program.

So this process was started for each parser, expression and translator test.  For each, the run arguments were set (Projects page, Run Settings) and the Analyzer was run.  This were no memory issues on the parser tests, however, some problems were found on the translator tests, which will be discussed in following posts.

List Class Replacement (Begin)

The List class was the first implemented for this project, so it is fitting that it will be the first to be replaced with the transition to Qt.  Qt's list class is named QList.  The functionality is not much different then the home grown List class, though most of the member functions have different names.

The approach being used was to first replace all cases of List with QList and then search for each List class member function name and replace it with QList's version.  In some cases, the code needs to be written a bit since the QList functionality is slightly different.  For example, while QList also has a first() function, it must not be called if the list is empty (must check if it is empty first), while the List class first() function allows for an empty list (returning a null pointer).

The first complication came in how to deallocate items in the QList.  The question was, does this happen automatically when leaving scope, is deleted or via QList's clear() member function.  Neither was the case where the list is a list of pointers to allocated elements.  Each element needs to be deleted (same as the case with the List class).

A small test program was written to evaluate and confirm this behavior.  As part of this evaluation,  a method to detect memory leaks was employed that is kind of built into QtCreator (at least on Linux).  This lead to quite a few detours, which will be the subject of the posts that follow...

Translator – Correcting More Token Leaks

There were a few more token leaks that needed to corrected, one with the first and last operand changes and rest with the PRINT command. Details of the rest of the token leaks found and corrected are after the continue. All tokens leaks have now been corrected, time to handle array assignments...

Translator – Correcting Token Leaks

The crash on Translator test 12 was caused because the token leaks were only being output after a successful translation but not when an error was reported. After a number of errors, the token leaks built up and when they were finally output, their information didn't line up with the current input line causing a crash when accessing outside of a buffer. Once that problem was fixed, the token memory leaks were fixed one by one.

For one of the leaks, an incorrect fix was applied causing multiple token deletes. For some reason these tokens were not output. A segmentation fault occurred when attempting to debug this problem before it even got to the output code when it was attempting to delete the string in the token a second time. Setting the string pointer to NULL didn't help – apparently the memory was already being used for something else.

Apparently gdb (under NetBeans) catches these segmentation faults where the program running by itself does not. In any case, at least the code was at least detecting the extra delete condition.  Details of the memory leaks found and corrected so far after the continue. A common theme is that the token leaks occur when something is popped from the stack and not put anywhere because any tokens in any of the stacks, the pending parentheses token or the output list get deleted by the Translator's cleanup routine.

Token Leaks – Implementation

To implement token leak detection, a token pointer list was added to the Token class as a static member and a token list element pointer was added as a regular member.  The new and delete operators were overloaded in the Token class to be able to maintain this token list.

The overloaded new operator function first allocates an array of bytes for the size argument, which is type cast to a Token pointer. The token pointer is appended to the static token pointer list and the element pointer returned from the list append function is put into the element pointer member of the token. The value of the token pointer is returned.

The overloaded delete operator function type casts the void pointer to a token pointer. If the element pointer is NULL, then this token has already been deleted. Otherwise the element pointer in the token is used to remove the token pointer from the token pointer list. The element pointer of the token is set to NULL to indicate that it has been deleted (to detect multiple deletes of the same token). The memory used by the token is then deleted.

This additional error that can occur when a token being deleted more than once. To also catch these errors, when a token is being deleted, if its element pointer is NULL, then a copy of the token will be added to a new delete list, which will be a list of tokens. A copy of the token needs to be made because the memory has already been deleted and could be reused by another allocation. It's also possible that the memory may have already been reused and the token copy will be garbage, but at least it will be known there is an extra delete somewhere.

Finally, the test code was modified to output any tokens that have not been deleted once the RPN output list has been output and cleaned up (all of its tokens deleted). The tokens in the delete list are also output. Once the code was working and running, many token leaks were found (in six of the Translator tests), and Translator test 12 (more error tests) was crashing. Time to fix some problems...

Token Leaks – Initial Design Thoughts

When considering a design to keep track of tokens created, there needed to be an easy way to remove the token once it has been deleted. Tokens left in the list would be memory leaks. The first idea was a simple linked list where each element consisted of a previous link, a next link, a pointer to the token and some type of identifier of where in the code that the Token was allocated. A pointer to the list element would be added to the Token class.

When a token is created, it would be added to the list and a pointer to the list element would be put into the token.  When a token is deleted, it would use the element pointer to delete the item from the list. For tokens still in the list at the end, the identifier would indicate where the token was created, though the contents of the token itself would probably be sufficient in determining why it was not deleted.

At first, a special token list class was considered. It would only need a pointer to the first element in the list. Some code on how this would work (adding and deleted elements) was sketched out.  But wait, there was already a List class, and then it was realized that the List class doesn't need a master element to keep track of the first and last elements in the list. Only a pointer to the first (or last) element is needed...