Categories: Valgrind

Quick Introduction to Valgrind

For my Computer Aided Geometric Design course, a simple program called CPLOT is used for some of the project work. Its documentation is on the course website. After my initial draft of my project 1 implementation crashed, I was inspired to try out Valgrind on CPLOT (even though I was able to find the bugs using my debugger). All that’s needed to install Valgrind on Ubuntu is sudo apt-get install valgrind. The CPLOT code supplied needed a minor change in order to compile, so I changed

#include <string.h>;

into

#include <string.h>;

and all was well with the world again. The updated CPLOT code is available in my public repo. Line 1 below compiles the code. The Valgrind Quick Start Guide recommends using the -g flag to produce debugging information so that Memcheck’s error messages include exact line numbers.

g++ -g -o cplot.out cplot.cpp
valgrind --leak-check=yes ./cplot.out eg1.dat eg1.eps

The eg1.dat file I used is the one on page 3 of the CPLOT documentation. Below is the output from valgrind:

==1594== Memcheck, a memory error detector
==1594== Copyright (C) 2002-2010, and GNU GPL'd, by Julian Seward et al.
==1594== Using Valgrind-3.6.1 and LibVEX; rerun with -h for copyright info
==1594== Command: ./cplot.out eg1.dat eg1.eps
==1594==
In initps: eg1.eps
File processed successfully!
==1594==
==1594== HEAP SUMMARY:
==1594==     in use at exit: 120 bytes in 6 blocks
==1594==   total heap usage: 8 allocs, 2 frees, 824 bytes allocated
==1594==
==1594== 120 (8 direct, 112 indirect) bytes in 1 blocks are definitely lost in loss record 3 of 3
==1594==    at 0x402641D: operator new(unsigned int) (vg_replace_malloc.c:255)
==1594==    by 0x8049224: readCurve() (cplot.cpp:182)
==1594==    by 0x8048D89: main (cplot.cpp:127)
==1594==
==1594== LEAK SUMMARY:
==1594==    definitely lost: 8 bytes in 1 blocks
==1594==    indirectly lost: 112 bytes in 5 blocks
==1594==      possibly lost: 0 bytes in 0 blocks
==1594==    still reachable: 0 bytes in 0 blocks
==1594==         suppressed: 0 bytes in 0 blocks
==1594==
==1594== For counts of detected and suppressed errors, rerun with: -v
==1594== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 17 from 6)

This program can be improved by changing the return statements in the body of the main for(;;) loop into break statements. By so doing, all the cleanup code can be placed after that loop, just before the program exits. This also prevents the duplication of the cleanup code. The code after the for(;;) loop then becomes:

    // Deallocate all allocated memory
    for (int i=0; i < NCURVES; i++) {
        delete curves[i];
    }

    // Close the file resources
    fclose(in);
    fclose(ps);
    return 0;

The Curve class destructor then becomes:

Curve::~Curve() {
    for (int j=0; j <= degree; j++)
        delete points[j];

    delete [] points;
};

Running Valgrind on the updated program then gives the following output.

==6539== Memcheck, a memory error detector
==6539== Copyright (C) 2002-2010, and GNU GPL'd, by Julian Seward et al.
==6539== Using Valgrind-3.6.1 and LibVEX; rerun with -h for copyright info
==6539== Command: ./cplot.out eg1.dat eg1.eps
==6539==
In initps: eg1.eps
File processed successfully!
==6539==
==6539== HEAP SUMMARY:
==6539==     in use at exit: 0 bytes in 0 blocks
==6539==   total heap usage: 8 allocs, 8 frees, 824 bytes allocated
==6539==
==6539== All heap blocks were freed -- no leaks are possible
==6539==
==6539== For counts of detected and suppressed errors, rerun with: -v
==6539== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 17 from 6)

There was another bug in the program since it could attempt to plot control polygons for uninitialized curves because of a missing else. I pushed the trivial fix to that. The program also crashed if the input file specified did not exist because fscanf would try to use a NULL parameter. The fix is a simple NULL check.


Modelling the Infamous Dining Philosophers

A sample implementation of the dining philosophers problem is provided in the JPF core source code. The solution I gave to this problem was to use the following locking scheme: if a thread has an even id i, then it should lock fork i first and then fork (i + 1) % N. If its id i is odd, then it should lock fork (i + 1) % N first and then lock fork i. Replacing

new Philosopher(forks[i], forks[(i + 1) % N]);

with

Fork leftFork, rightFork;
if (i % 2 == 0) {
    leftFork = forks[i];
    rightFork = forks[(i + 1) % N];
} else {
    leftFork = forks[(i + 1) % N];
    rightFork = forks[i];
}
new Philosopher(leftFork, rightFork);

Should do the trick. DiningPhil.jpf can then be launched to verify the absence of deadlock with this new locking scheme.


Categories: JPF

Copying Image Files to Build Folder in Eclipse

Part of my Google Summer of Code project this summer involved building a visualization tool to help examine trace files used by JPF Guided Test and a related under-approximation scheduler. The visualization tool is in the Guided Test repository. I was using Eclipse to manage the project. Everything built correctly but the program didn’t work because the icons were not in the build folder as expected. A quick hint from stackoverflow was that the solution is to use Ant.

<target name="-pre-jar" description="Copy Images">
  <property name="images.dir" value="build/main/edu/byu/cs/guided/search/visualize/graphics" />

  <copy todir="${images.dir}">
    <fileset dir="./src/main/edu/byu/cs/guided/search/visualize/graphics" />
  </copy>
  <echo level="info" message="Visualization icons was copied."/>
</target>

The key is to use the “-pre-jar” target in the build.xml file to copy the files into the right spot. This change was part of the visualization check-in into the repository. Some documentation on Ant targets is available in the Apache Ant User Manual. This StackOverflow entry on adding resource files to a jar file with Ant has some useful hints as well.


Categories: Eclipse

Attaching Java Source Files to an Eclipse JRE

As per this ubuntu thread, the solution is:

  1. Window > Preferences > Java > Installed JREs.
  2. Double click on the JRE for which you want to attach source code.
  3. Under “JRE System Libraries”, select rt.jar.
  4. Click on the “Source Attachment…” button.
  5. Supply a path to the source zip file, e.g. C:/Program Files/Java/jdk1.6.0_23/src.zip

That zip file was already on my system (since the JDK was installed) but some projects were using the JRE rather than the JDK. Therefore, I needed to specify the JDK source zip file for the JREs as well.


Building Racket in Linux

The Racket website has documentation on how to clone the PLT repository.

git clone git://git.racket-lang.org/plt.git

Next, the src/README file has all the gory details on how to build Racket. The procedure is rather straightforward for Linux:

mkdir build
cd build
../configure
make
make install

I’m yet to figure out how to successfully build racket in Visual C++ (2008 Professional), so that’s the next item on my list.

Update (03/11/11): Actually rather straightforward for Visual C++ as well, run vsvars32.bat to ensure that devenv and other commands are in the path:

cd plt\src\worksp\
"C:\Program Files (x86)\Microsoft Visual Studio 9.0\Common7\Tools\vsvars32.bat"
build

I got the hint from this thread.


Implementing canvas putImageData’s optional arguments

Bug 498826 is about the HTML canvas putImageData method. It did not implement the optional arguments specified in the WHATWG spec. These optional arguments specify the dirty rectangle for the image data transfer (specifically, these arguments are the coordinates of the top left corner and the dimensions of the dirty rectangle, any of which are allowed to be negative). A quick glance at the description of the algorithm for handling of the optional arguments may not reveal the overall intent of the algorithm. Some of its key aspects are:

  1. Adjusting the dimensions of the rectangle to be positive by shifting the top left corner if necessary (step 2).
  2. Ensuring the top left corner of the dirty rectangle is in the first quadrant (step 3) which effectively eliminates all negative arguments.
  3. Clipping the dirty rectangle to ensure its lower right corner does not extend beyond the bounds of the incoming imagedata’s dimensions (step 4).
  4. Verifying that the newly adjusted dirty rectangle has positive dimensions (step 5), and if so, using the region bounded by the dirty rectangle on the incoming imagedata object as the source for the operation.

The patch is rather straightforward (although admittedly, it was not as straightforward to create on my part). If there are enough arguments to specify a dirty rectangle, then the JS_ValueToECMAInt32 function is used to convert the JavaScript values into integers. The CheckedInt32 and the gfxRect classes do most of the heavy lifting in the patch, and then only the dirty rectangle is redrawn.


Remove unused nsCookieService::SetCookieString argument

Bug 520914 is the only Bugzilla item I got to look at this month – since it required the least amount of time :). All that needed to be done was to remove the aPrompt argument currently in nsICookieService’s SetCookieString method. The locations in need of change were easily located with a simple MXR search.


Practical Example of Artificial Intelligence Principles

While digging around in Bugzilla (as is now my usual daily custom), I came across Bug 580468 – JM: Tune Trace JIT Heuristics. It was interesting following the discussion since it was a perfect illustration of the principles being taught in CS470. Therefore, I wrote up this brief summary of the bug discussion to reinforce to myself how practical these issues are: Practical AI.


Make location.host and location.hostname return “” for host-less URIs

In the rather straightforward bug 562433, Firefox’s location.host and location.hostname need to return the empty string for host-less URIs instead of throwing an exception. What ends up wasting my time with such 1-minute fixes is figuring out the right test location and the right command to run the test. At least documenting this should save a few minutes next time:

TEST_PATH=dom/tests/mochitest/bugs/test_bug562433.html make -C /c/mozilla/obj mochitest-plain

See the Mochitest automated testing framework documentation for details.


Excel Macro to Merge First Two Cells of Each Column

Once in a while you may run into an Excel spreadsheet in which the first two rows have been used for column labels as a way to wrap text. Cleaning this up involves the straightforward task of merging the first two cells of each column. This rather tedious task is thankfully easily automated with an Excel VBA macro. See the code samples below:

Sample 1:

Sub MergeFirstTwoCellsInEachColumn()
    ' Bound the range selection as Ctrl+End would.
    ' See http://www.ozgrid.com/forum/showthread.php?t=17070
    Dim lastCol As Integer
    Dim row1LastCol As Integer
    Dim row2LastCol As Integer

    row1LastCol = Range("A1").currentRegion.End(xlToRight).Column
    row2LastCol = Range("B1").currentRegion.End(xlToRight).Column

    lastCol = WorksheetFunction.Max(row1LastCol, row2LastCol)

    ' Select the first two rows
    Rows("1:2").Select

    ' Merge the first two cells of each column
    For i = 1 To lastCol
        Dim columnCells

        columnCells = Selection.Columns(i).Cells

        Dim finalColumnText

        ' Concatenate contents of cells in rows 1 and 2 in this column
        ' separating them with a space
        finalColumnText = Trim(columnCells(1, 1) & " " & columnCells(2, 1))

        ' Clear both cells and store the new value in the first cell
        Selection.Columns(i).Value = ""
        Selection.Columns(i).Cells(1, 1) = finalColumnText

        ' Merge the cells
        Selection.Columns(i).Merge
    Next i
End Sub

One side effect of this code is that it merges cells in the columns up to the end of the range that would be selected if you pressed Ctrl + End. The columns to the right of this range are not merged, in effect leaving two rows in the spreadsheet for the headings. Enter Sample 2:

Sub MergeFirstTwoCellsInEachColumn2()
    ' Select the first two rows
    ' Bound the range selection as Ctrl+End would.
    ' See http://www.ozgrid.com/forum/showthread.php?t=17070
    Dim lastCol As Integer
    Dim row1LastCol As Integer
    Dim row2LastCol As Integer

    row1LastCol = Range("A1").currentRegion.End(xlToRight).Column
    row2LastCol = Range("B1").currentRegion.End(xlToRight).Column

    lastCol = WorksheetFunction.Max(row1LastCol, row2LastCol)

    ' Select the first two rows
    Rows("1:2").Select

    ' Combine the contents of the first two cells of each column
    For i = 1 To lastCol
        Dim columnCells
        Dim finalColumnText

        columnCells = Selection.Columns(i).Cells

        ' Concatenate contents of cells in rows 1 and 2 in this column
        ' separating them with a space
        finalColumnText = Trim(columnCells(1, 1) & " " & columnCells(2, 1))

        ' Store the new value in the first cell
        Selection.Columns(i).Cells(1, 1) = finalColumnText
    Next i

    ' Delete row 2
    Rows("2").Delete
End Sub

In MergeFirstTwoCellsInEachColumn2, the new column headings are simply written to the top cell and when this has been done for all columns, row two is deleted. This is perhaps the more elegant solution for most spreadsheets. A few comments on the code:

row1LastCol = Range("A1").currentRegion.End(xlToRight).Column

This line determines the last non-blank column in row 1. The currentRegion property of the Range object returns a “range bounded by any combination of blank rows and blank columns”. When called on the Range(“A1”) object, it effectively selects the same region as Ctrl + End. It’s then straightforward to inspect the End property and get the corresponding Column.

lastCol = WorksheetFunction.Max(row1LastCol, row2LastCol)

lastCol is the greater of the last columns in the first two rows (needed in case both rows don’t have the same column number as the last column). This lastCol value is important because without it, Excel will chew lots of CPU running the macro on all the columns beyond those spanned by the input data.