August 2014

Reference Counting, Finalization and Resurrection

I've been enamoured of reference counting since devouring Smalltalk-80: The Language and its Implementation in 1987, and actively using it since reading Coplien's Advanced C++ in 1993.

For compatibility with the Object Pascal memory model, which ameliorated the lack of physical memory management, C++ on the Mac generally used handle-based heap objects. This had serious structural issues because they just weren't firmly located in memory.

Ultimately regular pointer-based heap objects won out even on Mac and reference counting became usable. I encapsulated the necessary activities in the smart pointer ZRef and the object base class ZCounted, which stabilized in the late 1990s after some struggles with the advent of preemptive multithreading.


All of which is to justify why I haven't simply embraced the C++11 standard library's smart_ptr — by implementing reference counting for myself I think I stumbled over every possible mistake, but also found a really useful mechanism I haven't encountered elsewhere. In the literature reference counting is considered to have two fundamental problems — reference cycles and object resurrection. In my experience a cycle (ultimately) indicates a broken data model.

However, inadvertent resurrection is a significant problem.


The issue is that we may want to take additional action when an entity's count transitions from one to zero, but if that action itself needs to treat the entity as counted, then the count will necessarily increment from zero, must ultimately transition down again, and we're into recursive execution of finalization.

Another situation is when we don't want simply to release the entity when it's no longer in general circulation, but want to change its treatment, perhaps by placing it in a cache. So we actually still have a physical reference to the entity, but managed with some different mechanism. This kind of changeover is very susceptible to thread issues. We could acquire a lock every time we manipulate any reference count, but that utterly kills performance and creates a pervasive and non-obvious source of deadlocks.


The solution is in the statement — we know to take action when the reference count changes from one to zero. What if we don't change the count in that case? Remember we're tracking the number of extant physical references. Seeing the one to zero transition tells us there's no other reference to the object than the one in our hands at that moment. So any further reference originates from the one we're considering finalizing. Rather than the typical atomic-decrement-and-test, releasing a reference uses a get, test and CAS sequence. The finalization code is now free to pass the entity to other code and no (legal) operation can again take the count from one to zero. Ultimately execution returns to the finalization. If the count has returned to (or remained) one, then we release the entity, otherwise do a simple atomic decrement and exit.

February 2014

WireOver - Fast, Free, Secure File Sending

WireOver is a Mac, Windows and Linux application for sending and receiving files. It's easy to use and very low friction, requiring only entry of an email address and click on a received web link to set up. Receiving an unsolicited send is even easier, as acting on the receipt of the notifying email naturally associates that email with the recipient.

Transfers (by subscribers) use perfect forward secrecy, and can be entirely asynchronous, so sender and receiver need never be online at the same time. Of course if they are, then transmission goes as fast as the physical network allows.

We built the backend and client mainly in Python, supporting Mac and Windows back to 10.5 and XP respectively. For Linux we support 32 and 64 bit Ubuntu 12 and later.

Much of my focus has been on keeping OS variations from impacting the main body of the code. To that end, we're using wxWidgets to abstract the GUI, and I've implemented such native code as needed to interface with unwrapped aspects of the OS and third-party libraries. In some cases the fluent Python bindings to OS facilities just aren't fast enough, and native code is used there also.

June 2013

Glass Ceiling

Glass Ceiling is the ultimate female revenge fantasy. In Glass Ceiling, our hero Moxie fights her way up the corporate ladder—literally. By battling fresh men, backstabbing co-workers, asinine accountants, bad bosses and other office stereotypes.

Graphic and game design by Wendy Carmical, project management and game design by Maura Sparks.

It's written in C++ using OpenGL, and thus is completely portable between iOS, Android and OSX.

March 2012

SPARKvue Augmented Reality

Working with Sally Ride Science and PASCO I extended the desktop version of SPARKvue to support augmented reality views of the experimental setup.

In this enhanced version of SPARKvue sensors are tagged with fiduciary markers. The video from a camera pointed at the experimental setup is shown beneath normal UI elements, and measurements from sensors are drawn into the video as it runs.

November 2011

MOTOACTV HTTP Proxy

The MOTOACTV communicates with servers to share and manage its user's fitness information. The device is very small and interacting with a complex network configuration UI is not viable. So, when tethered, it communicates through an HTTP proxy I wrote that runs on the user's desktop machine.

This is not my first full HTTP proxy; that was the desktop component of iMobimac Modem. In this case there were a couple of requirements that made things interesting.

Generally a proxy is a long-running system service, and it builds and evolves knowledge of what outbound paths and upstream proxies are available and usable. This proxy launches when the device connects, and shuts down when it quits, so any knowledge it can acquire is likely to be stale.

The approach I took was to try everything at once -- initiate connections on every combination of network interface, proxy name and resolved IP address, and use whichever wins the race. Thereafter it starts with the last thing that worked, and only scatterguns after a timeout. Interestingly this makes regular desktop browsing more responsive too, but it's pretty abusive to the network infrastructure and is only safe for idempotent GETs.

The other interesting feature was handling Proxy Auto Config (PAC) files. These are chunks of javascript that take a desired host name and return the name/address of the proxy that should handle the request. I'd never come across one in the wild, but they're very common in corporate networks where there's free rein inside the firewall, but all external access is via proxies. The system facilities on OS X are sufficient that the task can be handled by calling CFNetworkExecuteProxyAutoConfigurationURL. Windows on the other hand can almost do the job. The WinHTTP library can handle a PAC specified with a network URL, but not with a local file. So when we see that the PAC is a local file we fabricate an HTTP URL referencing a port we're handling, and any request on that port returns the content of the PAC file.

May 2011

Wellness!

As a new parent, especially once the children started at school, I was amazed at the number of prescriptions for minor ailments that we'd have to manage at once. Hence the iOS application Wellness!, developed in collaboration with IRMAcreative.

Project Archives