Thursday, 8 May 2014

Factory functions and their return types

Suppose we need to write a factory function that constructs a runtime polymorphic object. For the purposes of this post, let's say we want to construct a concrete shape object -- a rectangle, triangle, or an ellipse. Here are our basic declarations:

struct shape {
    virtual ~shape() {}

struct ellipse : shape {
    ellipse(int rad_a, int rad_b) {}

struct triangle : shape {
    triangle(int base, int height) {}

struct rectangle : shape {
    rectangle(int width, int height) {}

Basic stuff. Now for the factory function:

enum class shape_type { ellipse, triangle, rectangle };

struct rect {
    int w, h;

??? make_shape(shape_type type, rect bounds);

What should make_shape return. A pointer to shape, of course, but which kind. Should it be a raw pointer or a smart pointer like std::unique_ptr and std::shared_ptr. C++11 heavily advocates against raw pointers and I completely agree. That leaves us with a unique_ptr or a shared_ptr. I believe that in vast majority of situations there's a single owner of an object so that begs for returning unique_ptr. At least few other people are of the same opinion: here and here.

The argument goes that a shared_ptr can be constructed from a unique_ptr&& so this will also work just fine for the less common shared ownership cases:

std::shared_ptr<shape> s = make_shape(shape_type::ellipse, { 3, 5 });

While that is certainly true, there is a performance problem with this. C++11 encourages us to use std::make_shared<T> to construct shared ownership objects. Most std::make_shared implementations use a single dynamic memory allocation for both the object and the pointer control block (that stores the ref count). Not only does that save on overhead of calling 'new' twice, it also improves the cache locality by keeping the two close.

That benefit is clearly lost with conversion from unique_ptr to shared_ptr. I would therefore argue that factory functions should come in two flavors: a unique and a shared kind:

std::unique_ptr<shape> make_unique_shape(shape_type type, rect bounds);
std::shared_ptr<shape> make_shared_shape(shape_type type, rect bounds);

We now have two functions that do almost identical work. To avoid code duplication, we should factor out common behavior, right? Right but it turns out to be trickier than I expected. What we want is a helper function that is parameterized on make_shared or make_unique (or similar till will have it in C++14). The solution I came up with uses good old tag dispatching.

First, declare the tags but have them also know their associated smart pointer type:

struct shared_ownership {
    template <typename T> using ptr_t = std::shared_ptr<T>;

struct unique_ownership {
    template <typename T> using ptr_t = std::unique_ptr<T>;

Next, we add two overloads to do the actual construction:

template <typename T, typename... Args>
std::unique_ptr<T> make_with_ownership(unique_ownership, Args... args) {
    // until we have make_unique in C+14
    return std::unique_ptr<T>(new T(std::forward<Args>(args)...));

template <typename T, typename... Args>
std::shared_ptr<T> make_with_ownership(shared_ownership, Args... args) {
    return std::make_shared<T>(std::forward<Args>(args)...);

Finally, we can put it all together to create a generic make_shape along with make_unique_shape and make_shared_shape:

template <typename OwnTag>
typename OwnTag::template ptr_t<shape> make_shape(shape_type type, rect bounds, OwnTag owntag) {
    switch( type ) {
        case shape_type::ellipse:
            return make_with_ownership<ellipse>(owntag, bounds.w / 2, bounds.h / 2);

        case shape_type::triangle:
            return make_with_ownership<triangle>(owntag, bounds.w, bounds.h);

        case shape_type::rectangle:
            return make_with_ownership<rectangle>(owntag, bounds.w, bounds.h);

inline std::unique_ptr<shape> make_unique_shape(shape_type type, rect bounds) {
    return make_shape(type, bounds, unique_ownership());

inline std::shared_ptr<shape> make_shared_shape(shape_type type, rect bounds) {
    return make_shape(type, bounds, shared_ownership());

If you look at the return type of make_shape, it should make you cringe with disgust. Yeah, no bonus points for elegant syntax here. I also dislike the verbose name make_with_ownership. Nevertheless, I believe having a generic function for both unique and shared construction is extremely valuable. I would love to hear proposals for a better implementation and suggestions for a more concise name.

As always, the code is available on GitHub.

Sunday, 23 March 2014

forkfs: making any directory into a throw away directory

I recently needed to work on two git branches simultaneously. My particular use case required me to make small changes to both branches, rebuild and run. These were temporary changes that I was going to blow away at the end. One approach could have been to have two clones of the repo but that would have required me to rebuild my project from scratch for the second working copy (it was boost which is large). Having run into the same predicament before, I decided to create a script to "fork" a directory.

The script, called forkfs, works as follows. Suppose you are in your bash session in directory foo:
~/foo$ ls

You then execute forkfs which launches a new bash session and changes your prompt to remind you that you are forked:
~/foo$ sudo ~/bin/forkfs
(forkfs) ~/foo$ ls

So far it looks like nothing has changed but if we start making changes to the contents of foo, they'll only be visible in our forked session:
(forkfs) ~/foo$ touch baz
(forkfs) ~/foo$ ls
bar baz

Open up another bash session and do an ls there:
~/foo$ ls

When you exit out of your forkfs session, all your changes will be lost! You can also make multiple forks of the same directory, just not a fork of a fork. The forkfs script is available on GitHub.

Words Of Caution

Be careful where your fork begins. If you're using it for multiple git branches like I was, be sure to fork at the repository directory -- same place that houses the .git directory. Otherwise git will be confused outside of forked session.

Under The Hood

The script makes use of two technologies that are also used by Docker: aufs and mount namespaces. Aufs is a union filesystem which takes multiple source directories and combines them into a single destination directory. For example, one can mount /home/johndoe such that it's a union of /home/john and /home/doe directories. When you make changes in /home/johndoe, aufs uses a preconfigured policy to figure out which underlying directory gets the changes. One such policy allows forkfs to create Copy-On-Write functionality. When forkfs is forking ~/foo:

1. It creates an empty temporary directory, e.g. /tmp/tmp.Gb33ro1lrU
2. It mounts ~/foo (marked as readonly) + /tmp/tmp.Gb33ro1lrU (marked as read-write) into ~/foo:
mount -t aufs -o br=/tmp/tmp.Gb33ro1lrU=rw:~/foo=ro none ~/foo

Since ~/foo was marked as read only, all the writes go to the temporary directory, achieving copy-on-write.

Notice that the aufs was mounted over ~/foo. An unfortunate consequence of this is that the original ~/foo is no longer accessible. Moreover, it will not be possible to create other forks of ~/foo. This is where mount namespaces come to the rescue.

Mount namespaces allow a process to inherit all of the parent's mounts but have any further mounts not be visible by its parent. Linux actually has other namespaces of which a process can get a private copy: IPC, network, host/domain names, PIDs. Linux containers (LXC) makes use of these to provide light-weight virtualization.

unshare is a handy command to get a process running with a private namespace. forkfs uses "unshare -m bash" to get a bash running with a private mount namespace. It then executes aufs mount without having the rest of the system seeing the fork.

Future Work

If I have time, I'd like to add ability to create named forks and then be able to come back to them (like Python's virtualenv).


Special thanks goes to Vlad Didenko for helping me out with bash nuances.

Friday, 3 January 2014

LastPark: my first iPhone app gone wrong

I decided to venture out into the unknown -- iOS development. My first app -- LastPark -- saves the last location where the car was parked. I was solely trying to scratch a personal itch as I often forget on what street or what end of the parking lot I parked at. There are plenty of apps out there that allow you to mark the location of the vehicle but that requires remembering to do that before you're lost! Then there are Bluetooth LE devices that you can purchase and install in your car. When you shut your engine the device turns off and the app loses connectivity to it, causing it to save the location. $99 Automatic will also provide a slew of other features while the $25 Find My Car Smarter is very basic.

However my car already has the Bluetooth built in and moreover connects to my iPhone every time I get in to provide me with hands free calling. Why, I thought, would I need to buy another Bluetooth device when I got all the parts already installed. This is when I decided to write LastPark. (Technically I had to spend $99 to join the Apple Developer Program -- the same price as the fancy Automatic).

Unfortunately getting access to plain old Bluetooth (not the new Low Energy one) is not exactly easy in iOS. It seems like the only way was to use a private framework (undocumented). The upside is that a few people have already gone this route and there's even a demo project on GitHub that I used as a starting point. The downside is that Apple does not allow apps that use private frameworks in the AppStore. Not a biggie for me as I was developing it for my own use.

What killed this app was the inability to run it in the background. After some time in the background state the app gets suspended and doesn't get woken up for Bluetooth notifications. I tried specifying various background mode preferences in the plist but to no avail. I realize that Apple tries to improve the battery life by limiting the amount of work the apps can do in the background. However I believe it should be more liberal in allowing apps to register for notifications of ambient activities. These registrations probably take just a few bytes in some table inside a daemon (that's running anyway) and don't take much resources.

I've released what I got on GitHub. Any comments on how to get this to work as desired would be greatly appreciated.