Tk Source Code

View Ticket
Login
Ticket UUID: f1a3ca09d2981cdfe0a4a8060acab26ff24559e4
Title: Memory leak generic/tkTextBTree.c
Type: Bug Version: 8.6.6
Submitter: edhume3 Created on: 2017-08-09 00:49:41
Subsystem: 18. [text] Assigned To: fvogel
Priority: 5 Medium Severity: Important
Status: Closed Last Modified: 2017-08-24 19:23:39
Resolution: Fixed Closed By: fvogel
    Closed on: 2017-08-24 19:23:39
Description:
The implementation of the Text widget has memory leaks which are very evident when compiling with -DTCL_MEM_DEBUG and printing lots of output to the windows console, and yes, deleting all text in the console between memory active snapshots.  The leaks are from allocations for Btree nodes that contain child allocations (numPixels) that are not freed when the node is freed.  The following patches fix the leak which has existed for a long time (at least Tcl 8.5.16).  The ckfree( ) call added at around line 4281 has been proven to be necessary. The other ckfree() calls may not be necessary but they provide consistent and comprehensive deallocations whenever a BTree node is freed.
RCS file: /usr/cvsroot/tk8.6/generic/tkTextBTree.c,v
retrieving revision 1.2
retrieving revision 1.4
diff -c -4 -r1.2 -r1.4
*** tkTextBTree.c       25 Jul 2017 18:34:34 -0000      1.2
--- tkTextBTree.c       2 Aug 2017 15:04:01 -0000       1.4
***************
*** 798,806 ****
        nodePtr->numPixels[overwriteWithLast] =
                nodePtr->numPixels[treePtr->pixelReferences-1];
      }
      if (treePtr->pixelReferences == 1) {
!       nodePtr->numPixels = NULL;
      } else {
        nodePtr->numPixels = ckrealloc(nodePtr->numPixels,
                sizeof(int) * (treePtr->pixelReferences - 1));
      }
--- 798,807 ----
        nodePtr->numPixels[overwriteWithLast] =
                nodePtr->numPixels[treePtr->pixelReferences-1];
      }
      if (treePtr->pixelReferences == 1) {
!         ckfree(nodePtr->numPixels);
!           nodePtr->numPixels = NULL;
      } else {
        nodePtr->numPixels = ckrealloc(nodePtr->numPixels,
                sizeof(int) * (treePtr->pixelReferences - 1));
      }
***************
*** 1438,1445 ****
--- 1439,1448 ----
                    }
                    prevNodePtr->nextPtr = curNodePtr->nextPtr;
                }
                parentPtr->numChildren--;
+         DeleteSummaries(curNodePtr->summaryPtr);
+         ckfree(curNodePtr->numPixels);
                ckfree(curNodePtr);
                curNodePtr = parentPtr;
            }
            curNodePtr = curLinePtr->parentPtr;
***************
*** 4184,4191 ****
--- 4187,4195 ----
                if ((nodePtr->numChildren == 1) && (nodePtr->level > 0)) {
                    treePtr->rootPtr = nodePtr->children.nodePtr;
                    treePtr->rootPtr->parentPtr = NULL;
                    DeleteSummaries(nodePtr->summaryPtr);
+             ckfree(nodePtr->numPixels);
                    ckfree(nodePtr);
                }
                return;
            }
***************
*** 4273,4280 ****
--- 4277,4285 ----
                RecomputeNodeCounts(treePtr, nodePtr);
                nodePtr->nextPtr = otherPtr->nextPtr;
                nodePtr->parentPtr->numChildren--;
                DeleteSummaries(otherPtr->summaryPtr);
+         ckfree(otherPtr->numPixels);
                ckfree(otherPtr);
                continue;
            }
User Comments: fvogel added on 2017-08-24 19:23:39:
Merged to core-8-6-branch and trunk. Thanks again!

fvogel added on 2017-08-22 18:10:34:

Sorry, not sure why I stated my last (completely wrong) comment.

valgrind does show memleak plugging.

To convince yourself, just compare the two outputs (with and without the fix) in attachments: "valgrind_check_core-8-6-branch.txt" and "valgrind_check_bugfix_branch.txt"

The script run was simply:

    pack [text .t]
    .t insert end [string repeat "Test text\n" 1000]
    .t delete 1.0 end

Efficiency of the fix is demonstrated.


fvogel added on 2017-08-22 17:39:40:
valgrind does not show any leak, with (in the bugfix branch) or without (in core-8-6-branch) the proposed fix, for the test script I proposed below two comments ago.

I don't know what to conclude.

fvogel added on 2017-08-22 15:35:11:

More digging:

Your patch proposes to plug memory leaks, some of which were already fixed in the codebase. In fact, you propose to add codelines that are supposed to plug memleaks at only two new places in the code. This is commit [6c705c9b5d] I made:

Modified generic/tkTextBTree.c from [6ebb49bd61] to [0101cc0f47]. 
   795    795        */
   796    796   
   797    797       if (overwriteWithLast != -1) {
   798    798   	nodePtr->numPixels[overwriteWithLast] =
   799    799   		nodePtr->numPixels[treePtr->pixelReferences-1];
   800    800       }
   801    801       if (treePtr->pixelReferences == 1) {
          802  +	ckfree(nodePtr->numPixels);
   802    803   	nodePtr->numPixels = NULL;
   803    804       } else {
   804    805   	nodePtr->numPixels = ckrealloc(nodePtr->numPixels,
   805    806   		sizeof(int) * (treePtr->pixelReferences - 1));
   806    807       }
   807    808       if (nodePtr->level != 0) {
   808    809   	nodePtr = nodePtr->children.nodePtr;
................................................................................
  1435   1436   		    Node *prevNodePtr = parentPtr->children.nodePtr;
  1436   1437   		    while (prevNodePtr->nextPtr != curNodePtr) {
  1437   1438   			prevNodePtr = prevNodePtr->nextPtr;
  1438   1439   		    }
  1439   1440   		    prevNodePtr->nextPtr = curNodePtr->nextPtr;
  1440   1441   		}
  1441   1442   		parentPtr->numChildren--;
         1443  +		DeleteSummaries(curNodePtr->summaryPtr);
  1442   1444   		ckfree(curNodePtr->numPixels);
  1443   1445   		ckfree(curNodePtr);
  1444   1446   		curNodePtr = parentPtr;
  1445   1447   	    }
  1446   1448   	    curNodePtr = curLinePtr->parentPtr;
  1447   1449   	    continue;
  1448   1450   	}

Among these two places:

- The first place I did not manage to exercise. This codepath is simply never run by the test suite of Tk.

- The second place is exercised by the short script I provided in my previous comment. This script should therefore show a memory leak. But this script fails at demonstrating this. What I can still do is to run this test script under valgrind and look at what valgrind spits.


fvogel added on 2017-08-22 07:38:13:

I'm still trying to show the efficiency of your proposed fix. So I wrote a script that should leak, in order to demonstrate the leak before your fix, and check that it no longer happens with the fix. I came out with the following:

package require Tk
pack [text .t]
for {set i 1} {$i < 10000} {incr i} {
    .t insert end [string repeat "Test text\n" 1000]
    .t delete 1.0 end
}

This script could not show any memory leak on the current core-8-6-branch (that is: before the fix you propose). However, in core-8-5-branch, where the previously found leak [28a3c366e6] was plugged, this script easily shows huge leaks.

It should be possible to to come up with a script demonstrating the leaks that you're proposing to plug, don't you think so?


fvogel added on 2017-08-10 18:51:03:
OK, I get the idea, thanks.

I tried to produce an output before and after your fix proposal, to check that the fix is effective, but...

- had to install unix-like tools (I picked unixutils, is that correct?)

- what test file are you running? (i.e. what is the value of 'testname'?). For instance it can't just be a .test file from tk/tests since these files most of the time can't just be sourced (example with 'text.test': it ends up with "invalid command name "cleanupTests"").
 
- from what directory are you running proc memtest? (is it tk/tests?)

- I could not find dmh_wish code (but I have found its man page)

All in all, quite some burden to make this leak detection system half work. I guess all this is perfectly tailored to your habits and local systems, but it's less than ideally generic.

I'm inclined to just trust you without checking the efficiency of the fix.

edhume3 added on 2017-08-10 03:36:49:
Here is how to detect memory leaks.  

For the Text widget, we want to compile the Windows version and use the Console window which is implemented as a Text widget.

Compile Tcl and Tk and all packages to be tested with TCL_MEM_DEBUG=1. When using makefile.vc you add STATS=memdbg as in:

nmake -f makefile.vc release SYMBOLS=1 MACHINE=AMD64 INSTALLDIR="\usr\local" EHDEFINES="-DFD_SETSIZE=256" STATS=memdbg

The procedure below is used to run a test multiple times, even thousands of times, and capture memory snapshots before and after.  
To test the Text widget, the test file should print to the console, perhaps by setting tcltest::verbose.

proc memtest {testname {reps1 20} {reps2 300}} {
    set f ${testname}.test
    time {source $f} $reps1
    console eval {.console delete 0.0 end}
    memory active m0
    time {source $f} $reps2
    console eval {.console delete 0.0 end}
    memory active m2
    exec memcmp.bat m0 m2 &
    }

The memcmp.bat program uses Unix-like utilities, cut, sort, and diff to compare 
the memory snapshots:

hume@zip:~/src86/tests86/tcllib> cat memcmp.bat
start dmh_wish -tclargs "proc start args {} ; proc goto args {}; set f1 %1 ; set f2 %2 ; source memcmp.bat"
goto EndOfTcl
#

foreach file [list $f1 $f2] {
    exec cut -b31- $file >${file}.c
    exec sort ${file}.c /O ${file}.s
    }

catch {exec diff ${f1}.s ${f2}.s >diff.txt}

exec gvim.exe diff.txt &

exit

# \
:endOfTcl

If you ran the test 7000 times, you look to see if you have a multiple of 7000 
new allocations in the diff.txt file.  The lines of the diff.txt show where the 
source file and line where the allocations occurred.  You will ordinarily have a 
few lines different from the history buffer etc. 

Sorry I do not have an example output.  The testing verified that the change 
around line 4191 fixed a leak.  Upon study of the source file, I saw there were 
other places where Btree nodes were freed without the complete set of 
deallocations.  So I added them, knowing it is not a problem to call ckfree() 
against a null pointer, and knowing that the possibly allocated structure members 
are initialized to null or set to null after the child allocations are freed.

fvogel added on 2017-08-09 20:30:12:

Thanks for your report!

Part of your proposed changes were already present in the bleeding edge of the source code. I have committed the remaining fixes in branch bug-f1a3ca09d2, could you please check that this is OK?

The test suite is still happy with the proposed fixes.

For the records: you are talking about very obvious leaks, could you be more explicit about how you demonstrate existence of these leaks?

Thanks!


Attachments: