How to parallelise Symbian programs without changing the code

October 23rd, 2008

The Smartphone Show this year seemed to have a lot of emphasis on different types of ‘runtime’ which can be used on Symbian phones. In this instance a ‘runtime’ seems to mean any programming environment: be it native Symbian C++, Java, Flash, Python or even AJAX stuff in the browser.

There was also a lot of emphasis on multi-processing, since it seems pretty clear that SMP is going to be the best way to save power on phones in the future. (Two slow processors use less power than one fast one).

Symbian OS provides all the usual techniques for multi-processing: threads, semaphores, and mutexes. Yet we all know these make programming difficult. So here are some miscellaneous thoughts on other things which could be done.

A declarative run-time

I tend to think that, as we get to a world with dozens or hundreds of cores on the desktop, we programmers are going to have to give up on issuing specific sequences of instructions, and instead just describe the desired relationships between our variables. The runtime then figures out how to calculate this based on the available hardware resources.

Such a scheme requires these relationships to be described in a functional or declarative programming language like Haskell. Maybe we need a Haskell runtime for Symbian OS?

I can imagine that working quite well to calculate the screen image of a game, for example. But interfacing with the rest of the system would probably need to be done using traditional programming techniques.

Software transactional memory

STM is an alternative to locks. In short, you just go ahead and make your writes to memory, and if they conflict with somebody else’s writes, the system will roll them back.

Ideally we need a paging system which somehow makes copies of pages automatically for each thread, and only merges them together upon a commit.

Parallelising active objects

Most Symbian OS programmes are specified as a series of active objects, which define how the thread responds to certain incoming events. A parallelised active scheduler could simply distribute the active objects across multiple threads in order that they can run in parallel on multiple cores. But, there would need to be restrictions: it’s always been assumed that active objects run one-at-a-time, and hence there’s no need for locking of data structures. Either all active objects would need to use locks whenever accessing potentially shared data structures, or each object would need to be annotated to give rules about which ones the scheduler could run simultaneously.

Still, the fact that Symbian programmes do have this semi-declarative way of saying what code to run in response to which stimulus does give them an advantage over other operating systems where event loops can be structured in myriad ways. It does open the door to thinking about parallelising programs automatically.

In practice, I think it’s probably hopeless. Except…

Paralellising active objects + software transactional memory

If you imagine each active object as a single transaction in STM, then each one can run independently, operating on its own copy of the data. When the active object has completed, if no other active object has operated on the same data, then its changes are committed. Otherwise, they’re reverted and the active object is run again.

Then, the restrictions needed get much less: just making sure each active object doesn’t do any input/output operations (otherwise it can’t be reverted). (Non-blocking operations can simply be postponed until the transaction is committed).

So, all we need to do, is find a way to annotate the behaviour of active objects like that; implement a paging scheme and APIs for STM, and write an active scheduler which can distribute active objects across threads… and suddenly we have a way of parallelising all existing Symbian programmes.

Ha ha ha. Of course there are millions of complications. But it’s interesting to muse.

Stray event scanner 1.0.19 released

August 21st, 2008

There’s an updated version of the Stray Event Scanner tool available from the download page. Release notes can also be found there; mostly they’re to do with improvements to the command-line version of the tool.

Results of Stray Event Scanner evaluation at a customer site

August 19th, 2008

As I mentioned, about a week ago I visited a customer site to find out if our Stray Event Scanner tool actually did the trick, on their codebase. That customer has kindly said I can post some results here.

Results were mixed!

Proportion of this customer’s codebase scanned 5% (estimate).
False positives reported by the tool 47
Of which are things I might be able to fix 37
are intrinsic limitations 8
are already fixed in a later development version of the tool 2
Interestingly, 35 of these false-positives were in one smallish area of code. It seems that some Symbian OS code conforms to the norms expected by the tool, whilst some code really gets is unnecessarily overexcited. All the rest of the code we scanned only produced 12 false-positives.
Real bugs found by the tool 14
Of which tool was precise about the problem 6
tool was wrong, or vague, about the specific problem but did identify the right bit of faulty code 8
Actual bugs filed in this customer’s defect-tracking system 10 (because the other four were duplicates)

Conclusions. Good things first…

  • As expected, the tool found plenty of bugs. Nearly all of these bugs were real problems which could cause E32USER-CBase 46 panics under some circumstances, which are awful to diagnose.
  • In fact one of them was a duplicate of an existing E32USER-CBase 46 bug, which they’d been searching for for some time, but had been unable to find. Result!
  • The tool broadly worked as planned. There were no hopeless incompatibilities with their source code.
  • With the exception of that one component, there were far fewer false-positives than I realised.

Bad things…

  • There were lots of false-positives in that one component. Many of these will be impossible to remove using the current analysis method.
  • In some cases the tool was not very accurate about specifying exactly what was wrong with the code. It would identify the right area of code, but a lot of examination and thought was required to identify whether there really was a problem there. Again, there’s not much that can be done about this: stray event problems are intrinsically complicated and somebody technically experienced will be required to analyse the results.

Next steps…

  • See how many of those false-positives I can remove easily
  • Fix a few other minor bugs that cropped up
  • Decide whether the tool is ready to leave the beta stage!

DTrace is very good

August 18th, 2008

One of the things which would make Macrobug’s life much easier is if Symbian OS had DTrace or an equivalent. DTrace is a dynamic tracing framework which allows arbitrary APIs and function calls to be instrumented at run-time without any changes to any code. That way, the Macrobug tools would be able to hook in and monitor what’s happening inside the device without any changes to the kernel or application binaries.

Such days are probably some way away, but I can look forward to it!

Meanwhile, just as an example of how great DTrace is on a real system, I’ve just used it to diagnose a problem with my Mac. Macs include a backup mechanism known as Time Machine. This does incremental backups, in my case onto a RAIDed NAS server sitting elsewhere in my house (which in turn has parts of it rsync’ed to an off-site backup regularly).

Time Machine backs up automatically every hour in the background, and keeps as many incremental backups as it can fit onto the backup disk. There’s therefore an incentive for the backups to be smallish, as then your history will go back further. I found that most Macs seem to back up about 1-3 MB every hour, whereas mine always backed up 105-110MB. What was this mysterious file which was changing every hour that seemed to be 105MB big?

To diagnose this, I used Apple’s whizzy DTrace front-end, known as Instruments, to attach to the “backupd” process which does the time machine backups. I used some preset DTrace probes which can instrument the APIs used to read and write files, thus giving me lists of all the reads and writes, including their sizes, filenames, and even call stacks. And there’s even a nice UI to look at the results:

Instruments UI

The mysterious 105MB file turned out to be the article database for my RSS reader. It appears that they store all the articles in one file (messages.db) instead of many small ones. So, each time it refreshes (more than once per hour) the file changes, and Time Machine chooses to back it up.

So, the solution is simple – check whether there’s a fixed version of Vienna, or move to a new RSS reader, or tell Time Machine to ignore this file.

As for Symbian, perhaps there will be something like DTrace one day! I can’t wait!

PIPS on Motorola Z8

August 15th, 2008

PIPS is Symbian’s newish POSIX API layer. On the whole it’s pretty good; the APIs work well, although there is not much support for “related issues” such as building using GNU autoconf, link-by-name, and interfacing with other Symbian code.

However, PIPS 1.3 doesn’t work on Motorola phones. This means a customer of mine can’t release their software for Motorola devices, and the same will apply to many others I’m sure.

So, for the record, here’s Motorola’s explanation:

“We found that PIPS 1.3 is not supported with Motorola Z8 devices as no manufacturing capabilities are supported with Z8 in order to install PIPS 1.3 Software applications.We no longer intend to support with Z8.”

“However we are evaluating to support with our future UIQ devices for PIPS 1.3 Software application installation. Hopefully we will support.”

That’s nice, then!

(In all fairness, contrary to what Motorola Developer Support say above, I’ve been told from other sources that this is a temporary situation, and PIPS should work again on all Motorola phones – including the Z8 – in due course.)

Carbide.c++ and Qt

August 13th, 2008

The Carbide.c++ team has released the first Milestone release of Carbide.c++ 2.0.

There are two interesting things about this release.

The first is that an indexer bug has been fixed to work with templated types. Symbian OS descriptors are usually templated types, and so this is a big deal. It means a lot of features now work with Symbian APIs which previously didn’t – such as the call hierarchy, F3 to open definition, etc.

Just like in previous Carbide.c++ versions, when Carbide can’t understand your code, the code is shown in grey. The difference is that in previous Carbide builds it was probably a Carbide bug, whereas now it’s 99% likely to be a bug in your code. Several times now I’ve thought to myself, “oh, that code looks fine, Carbide must be imagining it” and sure enough, the indexer is right, I’ve messed something up.

For those reasons alone I wholeheartedly recommend joining the Carbide.c++ 2.0 beta and using the new version.

The second thing is the presence of a new perspective in Carbide.c++ – a Qt perspective. A few months ago, you might have noticed Nokia bought Trolltech, the makers of Qt. At the time there was speculation about what Nokia would do. Would they port Qt on top of S60? Would they replace S60? Would they start to make Linux/QT phones?

Well, the first answers are beginning to appear in this version of Carbide.c++. For example, the Qt perspective has editors for Qt actions, properties, objects, slots and widgets. That seems a lot to me, and although these views appear to belong to a com.trolltech.qtcppdesigner package and therefore aren’t produced by the Carbide.c++ team, it looks like a lot of the effort in Carbide.c++ 2.0 has gone into Qt work as well as Symbian work. I may be wrong!

Also, the Qt perspective doesn’t show the Symbian Project Navigator view. There’s nothing in that view which is specific to Symbian UIs – it’s all about the Symbian build system. That suggests to me that whatever Qt stuff is going to be happening in Carbide.c++ 2.0, it will not involve the Symbian build system, which in turn means it’s based on Linux (or something) rather than Symbian.

Again, I may be wrong, but that’s my prediction. It looks to me like Carbide.c++ is going to turn into a dual-purpose tool: Qt/Linux as well as S60/Symbian, rather than Qt-on-Symbian. It will be interesting to find out if I’m completely off the mark.

(Incidentally, this leads onto another vague interest of mine – getting the cross-platform make system cmake to generate Symbian OS MMP and bld.inf files. I vaguely plan to investigate that one day, but haven’t yet. I believe that KDE uses cmake, which suggests it’s popular in the Qt world. If there is any crossover, perhaps that’s been done somewhere already.)

New release of stray event scanner tool: 1.0.18

August 10th, 2008

This clears up a few bugs, displays the conditions more nicely, and makes things quicker. Use Carbide’s built-in software update to fetch the new version.

Off to demonstrate tomorrow…

August 10th, 2008

A customer has given me a contract to deploy my tools on their codebase, to see whether they come up with useful results. After that, maybe they’ll talk about licencing the tool… very exciting! But of course I’ve failed to fix all the things I had wanted to fix in the time leading up to this demonstration, so I know it won’t meet their criteria, quite. Sugar!

Tough bugs

July 15th, 2008

I’m still working on fixing the remaining known problems in Macrobug’s Stray Event Scanner.

I don’t intend to try to make it perfect – because, when understanding code, there’s always an exponential effort required to understand the rarest features. For example, the tool will never support the C goto keyword where it skips backwards up a function. (The tool already supports forward gotos!)

But, I do want to enhance support for a few more things. For example, if code Leaves, it currently considers what happens when the code either leaves or it doesn’t. That’s usually correct, apart from when functions are used which are always guaranteed to leave (for example, User::Leave). Then the tool should only consider the code path which occurs if the function does leave, and any errors after that should not be reported (until of course the leave is trapped). Unfortunately, this is tricker than it sounds given the tool’s current architecture.

In short, I think I’ve fixed most of the easy bugs and I’m now facing the exponential curve of tricky obscure things to fix! Let’s see how far up that curve I get before giving up and rolling back down again. I want to make the tool output as good as possible, but it’s already much better than having no means to detect these problems.

Stray Event Scanner Launched

July 9th, 2008

Macrobug is proud to present its first product for actual sale: the Stray Event Scanner. This is a source code analysis tool which does one thing, and does it well: it finds the causes of the dreaded Stray Event panic. Why are they dreaded? Well, by the time the crash has happened, the reason is lost in the mists of time, so there’s no way to diagnose them except to read reams of source code and spot the mistake.

The Macrobug Stray Event Scanner does that for you. It uses GCCXML to build your source code, and then analyses the results to ensure that each any every time you make a request, you are somehow getting ready for the reply to be received.

Problem marker from Stray Event Scanner

And yes, the problem messages are so descriptive they don’t even fit on this website.

Download the demonstration version now, or buy the real one!