Repository migrated to git

The EduMIPS64 source code repository, hosted at svn.edumips.org, has been converted to git.

So far, the repository contents have been migrated to git using the method described in Pro Git, and the resulting git repository has been pushed to Google Code and Github.

The next step is to create a git repository on edumips.org and configure Trac and Apache in order to let them serve the git repository. Most probably, the SVN repository will be removed.

EDIT: the github repository is now the main one. There will be no repository hosted on edumips.org.

Finding bugs via bisection

In the last version of EduMIPS64, we introduced a nasty bug that caused the simulator to stop working under Mac OS X Snow Leopard. Now we will not delve into the usual sayings about Java being "write once, debug everywhere", but instead we will show you how we actually identified the commit that introduced the bug.

The bug was discovered during the development of version 0.5.3, and the problem is that we don't have access to Mac OS X machines for testing, so usually we develop under Linux and sometimes we test also under Windows. So when one of the users reported the bug for version 0.5.3-rc2 we had no idea of which commit could have introduced the bug.

The stack trace wasn't helpful, just a StackOverflowError with lots of nested AWT/Swing calls, there was no pointer to the EduMIPS64 source code.

So when last week we could use a Snow Leopard machine to find and fix the bug, we had the problem to first identify the incriminated commit. The SVN revision of 0.5.2 is 436, while the last revision was 623. So there are 187 commits to check.. how to do it (possibly avoiding brute force)?

Enter bisection.

Bisection is a technique similar to binary search. You have a good version (rev. 436) and a bad version (rev. 623). What you do is to move at revision (good + bad) / 2, check if it is working or not, mark it as good or bad and repeat the process until the distance between good and bad is 1. This means that you have identified the change that made your good program a bad program.

You will recognize a familiar pattern here: you are always halving the distance to the objective. This means that you will be able to identify the culprit in log₂(good - bad). In our case, log₂(623-436) = 10 (rounding up the result). This means that in at most 10 update/compile/test cycles we will find our bug, provided that we can easily and without hesitation say if each version is good or bad. And in our case a bad version means that the simulator is totally hung up, so it is easy.


So, we started from (623 + 436) / 2 = 530, and this is the path that we followed: 530 (good, ↑), 576 (bad ↓), 553 (bad ↓), 541 (bad ↓), 535 (bad ↓), 532 (good ↑), 534 (bad ↓), 533 (bad ↓). So the commit that introduced the bug is 533. We "simply" had to figure out what is the bug.


Turns out that commit 533 is a bad commit in itself, because packs several changes at a time (introduction of a singleton, changes to the buildfile and to the logging system setup). So we spent half an hour with the singleton only to find out that the problem was that the JVM of Snow Leopard didn't appreciate that we tried to get the root logger by calling Logger.getLogger() with an empty string as a parameter (as shown in the official docs, even if we couldn't find this document for version 6). Using another logger instead of the root logger solved the problem.


By the way, if we used git (and we will migrate to it shortly), we could have used the wonderful command git bisect.


So, lessons learned:

• use bisection to find a commit that introduced a bug, if you can easily tell if a commit contains or not the bug;
• try to limit what you change in a commit, so that later it is easy to find what's wrong in that commit;
• use git because it helps you in doing both those things. :)

Enjoy!

Web site and SVN down

Unfortunately, slicehost is down right now, and all our services are hosted on a slicehost VPS.

This means that both the web site and SVN are down right now. I hope there is no big data loss, as I don't have a backup copy of the wiki and would need to rely on the Google cache to rebuild the pages.

UPDATE: Slicehost was down only for 6 hours (http://status.slicehost.com/2011/8/11/stl-a-issues-3), and there was no data loss. Time to plan backups!

Status update on 0.5.3

The version 0.5.3 of EduMIPS64 is almost ready. Thanks to the students of the Computer Architecture course at the University of Catania I was able to find and fix some bugs (see the temporary ChangeLog).

I also cleaned up the configuration of Trac on edumips.org and started using its ticket tracking features. Here is reported the project roadmap (with no due dates) and here are all the tickets (including closed ones), grouped by milestone.

I moved two tickets that need more time to 0.5.4, so for releasing 0.5.3 only two bugs need to be addressed. The problem is that one of them is related to the Mac OS X platform, and I don't have a Mac to work on it. People have been reproducing it on different versions of Mac OS X, and it is obviously a regression because version 0.5.2 shows no issues.

I hope that I'll get my hands on a Mac OS X in the near future and try to debug this issue. If you have one, please contact me.

In the next week, I won't have any time for the project, but I hope to start working on it on July.

Profiling performance issues

After some recent changes to the logging code and to the help system, I noticed that the startup of the simulator and its normal operations were considerably slower than the older version. After a bit of search by trial-and-error, I told to myself that I had to use a more scientific method and try to profile the application with a profiler.

So I started searching for a profiler for Java, and I found the YourKit Java Profiler, and it seemed to be what I was searching for. I briefly tried it and, thanks to the "HotSpot" feature, I immediately found a bottleneck (formatting the log messages even when they are discarded), so I asked them if they would provide free licenses for open source developers; i then discovered that YourKit is kindly supporting open source projects with free licenses of its full-featured Java Profiler.

Yourkit profilers are produced by YourKit, LLc: they produce both a Java and a .NET profiler. Of course I only briefly tried the Java profiler, and I can tell you that it was really easy to spot that obvious bottleneck. I'm going to spend some time to profile EduMIPS64 and remove the most prominent bottlenecks.

Fixing the help system

Currently, the EduMIPS64 user documentation is in bad shape. There are two different sources of documentation:

• The PDF manual, built from LaTeX files;
• The in-application help, made by (.. drum roll ..) text files. 

Both help sources are available in English and Italian. But this diversity means that there are two (actually, four) different places to update; moreover, the in-application help is really not adequate and a bit too simple.

Some time ago, we tried porting the help system to JavaHelp, but we didn't finish the porting and had some trouble in properly converting LaTeX to HTML. Moreover, JavaHelp seems to be dead.

So I asked a question on Stack Overflow, and I got two answers:

• convert LaTeX to ePub and embed an open source ePub viewer;
• use RTF in a JTextPane

To summarize, our requirements for the help system are the following:

• single source, multiple outputs (PDF, in-application help);
• in-application viewer
• optional search in the in-application help
• optional navigation pane in the in-application help

I have been playing a bit with the Sphinx documentation system, and I got two good PDF and single-html outputs, but then the problem was to display HTML in the application. The JEditorPane widget has some basic support for HTML and CSS, but it is way too basic. I'd had to heavily customize the output of Sphinx and I don't want to spend much time on it. Further, Using a basic viewer I'd drop the two optional requirements (search and navigation), or I'd have to code it- boring.

So we are going to try the LaTeX -> epub road, hoping that it works out nicely. In our idea, the new help system should be the only new feature in EduMIPS64 0.5.3.

EDIT: We settled with converting the documentation to reStructured Text and using Sphinx to output both the PDF and a multi-page HTML document, using the epub HTML theme; this HTML docs were then processed with jHelpDev to build a help set for JavaHelp, that even if it is not actively developed, seems to work well - maybe it is a bit slow but works. So probably 0.5.3 will have in-app help based on JavaHelp and with the same contents of the PDF manual.

Improving testability

There are a lot of features that can be integrated or implemented, but we feel that the first thing to do is to create a test suite, in order to be fairly confident that when we change something we do not break anything! After all, people use EduMIPS64 during their exams, and I don't want that someone gets a bad grade (and consequently tries to kill me) because of bad code.

A CPU simulator can be tested in many ways. The main decision we have to make is whether we should do black-box testing (overall functionality) or white-box testing (Java classes, individual or in small sets). So we looked at other CPU simulators in order to see how they solved this problem.

We've been looking at WinMIPS64, WinDLX and DLXView, but found no answer to our questions.

But when we turned to the SPIM MIPS32 Simulator, we found a very rich test suite. It is not surprising, as its author, James Larus, is very smart and wrote a really good presentation on Why write real software in Academia? (suggested reading for people in academia who happen to write software). The simulator is also featured in Appendix A of Hennessy & Patterson's "Computer Architecture: A quantitative approach", a reference book in the field, so it is definitely a good reference and inspiration source.

The Tests directory of SPIM contains 8 assembly test files that, together, amount to ~8500 lines of testing code. It is assembly code, so it is black-box testing.

We can try to reuse some of them, skipping some features (like FPU) and writing some new tests, as we implement a superset of their instruction set, even if the computation model is a bit different (we don't have memory/mapped IO, control registers and other few things).

There is a problem, however: EduMIPS64 is meant to be run as a desktop interactive application, and cannot be run in a CLI and in batch mode.

So we are trying to remove the few dependencies that the core of the simulator has with respect to the User Interface, that are poor design choices, and write a very small CLI frontend for the core, so that the CPU features can be tested without running the UI.

After that, we will try to port some testing code from SPIM to EduMIPS64, adding our own tests.

We will then be ready to integrate and add features to the simulator, knowing that we have a safety net that will catch most of the errors and will allow us to write code without breaking the core features in any (obvious) way.

State of the EduMIPS64 code base

In 2006, a small group of undergraduate students at the University of Catania was taking a course in Computer Architecture; they were not satisfied by existing MIPS64 simulators, so they decided to design and write their own simulator. They called it EduMIPS64 (web site: www.edumips.org), and it was initially conceived as an improved Java clone of WinMIPS64.

Most of the development happened between April and October 2006. Then, development slowed down a bit because the main functionalities were working and the simulator had been adopted as the official tool for Computer Architecture courses at the University of Catania.

There have been a moderate but constant activity through all 2007 and then, finally, in 2008 development came to an halt. The simulator was more mature, but many things still need improvement. Some important features, like FPU support and branch delay slot, have been developed but not released because the code needed to be polished, documented and tested.

This blog post wants to take a snapshot of the current state of the EduMIPS64 code base, in order to facilitate future development efforts.

The current stable version
The last version of EduMIPS64, 0.5.2, was released on 17th April of 2008, and like version 0.5.1 it is mainly a bug-fix release. Version 0.5 was the last major version, i.e. a version that introduced new features (namely, MIPS32 instructions and a few other things).

It can be considered quite stable, as the simulator is routinely used at least at the University of Catania for Computer Architecture exams, and no bugs were reported in the last 3 years.

The trunk
The trunk contains an implementation of the FPU, with a complete FP instruction set, visual representation of FP-related sections of the pipeline.
Moreover, it contains a (non-working) attempt to add in the help a conversion to HTML of the PDF manual.

The branches

• delayslot: contains an implementation of the Branch delay slot;
• editor: contains a (very) basic prototype of a built-in editor;
• new_parser:  a re-engineered parser written to replace the default one, that is difficult to mantain. It was developed as a student project for a Compilers course;
• cache: a re-engineered parser written to replace the one written during the development 
• 0.5: branch where development of the 0.5 series should go

Of these branches, delayslot, new_parser and cache are the ones that most likely will be included in future stable releases.

A note on testability

One of the problems of the EduMIPS64 code base is the lack of automated testing. When we developed it, we were mostly concerned with making it work, and as students it was an ambitious project. We worked day and night and fixed issues when they were raised, either by developers or by users, but we did not fully understand some basic concepts like unit testing, separation of intents, modularity etc..

Future development work needs to be addressed to a suite of unit tests that will work as a safety net for regressions as the development goes on.

Future development

There are many features that are almost ready but have been never released to the public, like the FPU or the branch delay slot.

It is likely that a new version of EduMIPS64, 0.5.3, will be released shortly. It will include some bug fixes and the ability to enable the branch delay slot, in order to get some user feedbacks on it.

After this, probably a 0.9 version with FPU will be released, and this version will also need to be heavily tested by users before a 1.0 stable version will be released.