The DikuSTM library

For my Mas­ters The­sis at Uni­ver­sity, I designed and devel­oped a Trans­ac­tional Mem­ory¹ library in C++. I named it DikuSTM, after the Com­puter Sci­ence depart­ment where I stud­ied, which is semi-formally nick­named DIKU. At the end of the project, in the spring 2010, I had a basi­cally func­tional pro­to­type, although the imple­men­ta­tion of some parts was sub­op­ti­mal, and I later dis­cov­ered a few bugs and race con­di­tions. This old ver­sion of the library, along with my Mas­ters The­sis itself, is avail­able here.

After­wards, of course, I took a long break from the project. But a few months ago, I decided to resume work on the project in my (some­what lim­ited) spare time, and while a few areas can still be improved, and the doc­u­men­ta­tion is nearly nonex­is­tent, the library is actu­ally near­ing a use­ful state.

On this page, I intend to track the sta­tus of the library, as well as what­ever doc­u­men­ta­tion and infor­ma­tion I have written.

A rea­son­ably up-to-date snap­shot of the code can be found here. Or you can pull it from the bzr repos­i­tory here

While no detailed and up-to-date doc­u­men­ta­tion exists yet, I have writ­ten the fol­low­ing short guide to illus­trate the basic usage of the library, and hope­fully allow any­one who’s inter­ested to take the library for a test drive.

10-minute Whirl­wind Tour

Trans­ac­tional Mem­ory can be imple­mented in a vari­ety of dif­fer­ent ways, each with their advan­tages and dis­ad­van­tages. But at its core is the notion that a block of code can be anno­tated to behave as a trans­ac­tion. Just like their data­base equiv­a­lents, a STM trans­ac­tion guar­an­tees that what­ever occurs within it hap­pens Atom­i­cally and in Iso­la­tion, while keep­ing the appli­ca­tion state Con­sis­tent at all times. (In the data­base world, Dura­bil­ity is guar­an­teed as well, and the four prop­er­ties are known as the ACID prop­er­ties, but as STM oper­ates in mem­ory, it is inher­ently volatile, and dura­bil­ity is both impos­si­ble to achieve, and unnec­es­sary — the rest of the appli­ca­tion state is lost on a crash any­way, so pre­serv­ing the state of in-memory trans­ac­tions would be use­less, even if it was possible.

When a trans­ac­tion ends, it is attempted com­mit­ted, at which point, the sys­tem ver­i­fies the con­sis­tency of the data touched by the trans­ac­tion, and if every­thing is con­sis­tent, the trans­ac­tion is allowed to com­mit, atom­i­cally mak­ing all its changes vis­i­ble to the rest of the sys­tem. If an incon­sis­tency is detected, typ­i­cally because another trans­ac­tion has com­mit­ted a mod­i­fi­ca­tion to an object read by the cur­rently com­mit­ting trans­ac­tion, that trans­ac­tion has to be aborted and rolled back, so that none of its changes are vis­i­ble. The trans­ac­tion then implic­itly retries, start­ing over and per­form­ing all its mod­i­fi­ca­tions again, before try­ing to com­mit once more.

A con­se­quence of this exe­cu­tion model is that the body of a trans­ac­tion may be eval­u­ated more than once — and so, side effects and I/O in par­tic­u­lar is, in the gen­eral case, for­bid­den within a trans­ac­tion. Side effects are per­mis­si­ble if they can be rolled back along with the trans­ac­tion, but I/O, such as writ­ing to stan­dard out­put would lead to sur­pris­ing results if done within a trans­ac­tion that is forced to roll back and retry.

Under the hood, these trans­ac­tions can be imple­mented using tra­di­tional syn­chro­niza­tion mech­a­nisms, and by copy­ing data into a pri­vate buffer accessed only by a spe­cific trans­ac­tion. A trans­ac­tion appears to exe­cute in iso­la­tion if it can cre­ate pri­vate copies of any shared data it mod­i­fies — regard­less of what the rest of the sys­tem may be doing, these pri­vate copies will stay untouched, and so the trans­ac­tion can pro­ceed as if it were alone on the sys­tem. Atom­ic­ity can be achieved by defin­ing a suit­able lock­ing pro­to­col, which allows trans­ac­tions to lock shared objects while cre­at­ing the afore­men­tioned pri­vate copy, and later on, when the trans­ac­tion com­mits and applies its changes to the global appli­ca­tion state. And con­sis­tency can be ensured by tag­ging every shared object with a ver­sion num­ber or a time­stamp, so that for any given trans­ac­tion, we can record the time­stamp at which it starts, and through­out the transaction’s life­time, ver­ify that objects accessed by it have not been mod­i­fied by other objects since the trans­ac­tion started.

That’s the ele­va­tor pitch describ­ing the fun­da­men­tal idea behind Soft­ware Trans­ac­tional Mem­ory, and a few hints at how such a library might work under the hood. Of course, there are many dif­fer­ent imple­men­ta­tion strate­gies, but the above should be good enough to give a high level under­stand­ing of what is going on in a STM library.

Using the DikuSTM Library

The sim­plest way to exper­i­ment with my library is to treat it as a header-only library. A few .cpp files do exist in my code, and are used if the pre­proces­sor sym­bol STM_HEADER_ONLY is not defined. This is cur­rently defined in file config.hpp, along with a num­ber of other set­tings and macros. In short, the library can be used as-is sim­ply by #include’ing the appro­pri­ate header, stm.hpp, located in the root of the down­loaded archive. The Boost.Thread library is used inter­nally in the library, and so it may be nec­es­sary to link to this library as well. The inter­nals of the library are located in the stm direc­tory. If you go look­ing at the tests located in the other direc­to­ries, be warned that they have accu­mu­lated over the last 18 months, since I started work on the project, and so, they’re ugly, incon­sis­tent and even use two dif­fer­ent test frame­works. The old ones use Boost.Tests, and the new ones use the excel­lent, and highly rec­om­mended, Catch library.

Now, get­ting back to the inter­est­ing part, the library itself, a sim­ple STM Hello World could look like this:

#include <stm.hpp>
#include <iostream>

std::string my_transaction(stm::transaction& tx) {
  return "Hello world";
}

int main() {
    std::cout << stm::atomic<std::string>(my_transaction);
}

Of course, this exam­ple runs in a sin­gle thread, and as such, we have no need for trans­ac­tional mem­ory what­so­ever. But it illus­trates the basic oper­a­tion of defin­ing a trans­ac­tion and invok­ing it atomically.

This sim­ple (and point­less) snip­pet high­lights a few inter­est­ing fea­tures of the library:

• trans­ac­tions are defined as func­tions or func­tors — stm::atomic accepts any “function-like” object, whether it is a plain func­tion pointer as in the exam­ple above, or a func­tion object, or, in C++0x, a lambda expression.
• stm::atomic is where the magic hap­pens. It exe­cutes the func­tion passed to it as a trans­ac­tion, atom­i­cally, con­sis­tently and in iso­la­tion. It is cur­rently nec­es­sary to spec­ify the return type as a tem­plate para­me­ter (call­ing stm::atomic() with no tem­plate para­me­ters implies that the trans­ac­tion returns void. In C++0x, the return type could be deduced auto­mat­i­cally through the magic of decltype, but the library does not yet take advan­tage of that feature.)
• the trans­ac­tion takes a ref­er­ence to an object of type stm::transaction as its sole para­me­ter (and so, in order to pass para­me­ters to the trans­ac­tion, the trans­ac­tion must be defined as a func­tor or func­tion object, so that the user-defined para­me­ters can be passed to its con­struc­tor). The stm::transaction object acts as the inter­face for com­mu­ni­ca­tion with the STM library. If the user wishes to abort the trans­ac­tion, for exam­ple, the stm::transaction object con­tains a mem­ber func­tion abort().
• for the com­mon case, the library just does the right thing. We didn’t need to call an explicit commit() func­tion — the trans­ac­tion is implic­itly com­mit­ted when con­trol leaves the scope of the trans­ac­tion func­tion. Val­i­da­tion is also taken care of for us. Dur­ing com­mit, incon­sis­ten­cies are auto­mat­i­cally detected, the trans­ac­tion is rolled back and retried, and so, no error han­dling is nec­es­sary on the user’s part. In this case, it means that we can sim­ply exe­cute the trans­ac­tion through stm::atomic, and stream the result to std::cout, with­out hav­ing to worry about “what hap­pens in the case of a con­flict, and if the trans­ac­tion fails to com­mit”. The user can sim­ply assume that the trans­ac­tion will com­mit suc­cess­fully, and return the desired value. It may inter­nally require a few tries to com­mit suc­cess­fully, but the user of the library does not see this, or need to write code to han­dle it.

This was a rather point­less exam­ple, how­ever. We cre­ated a trans­ac­tion, but we had no threads, and no shared data. So, let us add some shared data.

In the “ideal” imple­men­ta­tion of trans­ac­tional mem­ory, every­thing hap­pens inside a trans­ac­tion, and all data is mod­i­fied trans­ac­tion­ally. How­ever, such an imple­men­ta­tion would be impos­si­ble to imple­ment effi­ciently in C++ (and would be hard to inte­grate into exist­ing code), and so only objects wrapped in a spe­cial stm::shared tem­plate wrap­per are treated “trans­ac­tion­ally”; mod­i­fi­ca­tions to such objects occur in iso­la­tion, and are com­mit­ted atomically.

So, here is a sim­ple exam­ple which accesses and mod­i­fies some shared data:

#include <stm.hpp>
#include <iostream>

stm::shared<std::string> greeting("Hello");

struct combine_string {
    void operator()(stm::transaction& tx) {
        std::string& str = greeting.open_rw(tx);
        mystr += " World";
    }
};

std::string get_string(stm::transaction& tx) {
    return greeting.open_r(tx);
}

int main() {
    stm::atomic(combine_string());
    std::cout << stm::atomic<std::string>(get_string);
}

Again, hope­fully fairly sim­ple code. And a cou­ple of observations:

• in order to access a shared object, we need to open it, essen­tially reg­is­ter­ing with the STM sys­tem that the spec­i­fied trans­ac­tion is now access­ing the object. Objects can be opened in “read-only” mode with open_r, which returns a const ref­er­ence, or in “read-write” mode with open_rw, return­ing a reference.
• once opened, we get a plain ref­er­ence to the inter­nal type, and can deal with the object stored within the shared wrap­per com­pletely as we would expect to. We also see that the API is non-intrusive, so that exist­ing types can be used as-is.
• access to an opened object is auto­mat­i­cally “closed” again once the trans­ac­tion ter­mi­nates. No explicit close() call is nec­es­sary (or possible).
• in order to open an object, we have to pass in our stm::transaction ref­er­ence. This acts as a “key”, indi­cat­ing that yes, we are work­ing inside a trans­ac­tion, and so it is safe to open the object. Open­ing a shared object out­side a trans­ac­tion would be dan­ger­ous, and by requir­ing a ref­er­ence to the cur­rent trans­ac­tion, we pre­vent the user from acci­den­tally attempt­ing to do this.

We still have only a sin­gle thread, so once again, the exam­ple is some­what point­less. But if we had had more than one thread, then they could all have opened the greeting string within their respec­tive trans­ac­tions, and every trans­ac­tion would be guar­an­teed to see a con­sis­tent and valid value. The “inter­me­di­ate” invalid state while the string was being appended to occurred in iso­la­tion within the mod­i­fy­ing trans­ac­tion, so that other trans­ac­tions will only see the ini­tial or the final value, regard­less of when the trans­ac­tion attempts to open the object.

But let’s do some­thing real­is­tic now. Let’s add a sec­ond thread (I’m going to use the Boost.Thread API, but any thread­ing API will work — the library makes no assump­tions about how the thread was created):

#include <stm.hpp>
#include <iostream>
#include <boost/thread.hpp>

stm::shared<std::string> greeting("Hello");
stm::shared<bool> has_name(false);

struct add_name_tx {
    add_name_tx(const std::string& name) : name(name) {}

    void operator()(stm::transaction& tx) {
        if (has_name.open_rw(tx)) {
            clear_name();
        }
        bool& b = has_name.open_rw(tx);
        b = true;
        std::string& str = greeting.open_rw(tx);
        mystr += " " + name;
    }

private:
    std::string name;
};

struct add_name {
    add_name(const std::string& name) : name(name) {}
    void operator()() {
        stm::atomic(add_name_tx(name));
    }
private:
    std::string name;
};

void clear_name_tx(stm::transaction& tx) {
    greeting.open_rw(tx) = false;
    greeting.open_rw(tx) = "Hello";
}
void clear_name() {
    stm::atomic(clear_name_tx);
}

std::string print_name_tx() {
    return greeting.open_r() + (has_name.open_r()) ? ". You seem like a nice person." : ". Who are you again?";
}
void print_name() {
    std::cout << stm::atomic<std::string>(print_name_tx);
}
int main() {
    boost::thread_group group;
    group.create_thread(add_name("Jesper"));
    group.create_thread(clear_name));
    group.create_thread(print_greeting);

    group.join_all();
}

A bit more com­plex, but hope­fully it still makes sense.We cre­ate three threads; one which appends a name to the greet­ing string (clear­ing the exist­ing name if one existed), another which clears the name, and one which prints the greet­ing string, along with a small extra mes­sage depend­ing on whether or not a name has been added to the string. We also have two shared objects now, which must be updated atom­i­cally. When a name is appended to the greet­ings string, the value of has_name must be true, and vice versa. Our pro­gram logic relies on these objects being in sync at all times. And with tra­di­tional lock-based code, this would have been quite brit­tle. It’d be easy enough to add the nec­es­sary locks to ensure that as the code is today, these val­ues are always updated together. But every future exten­sion to the pro­gram would have had to keep this in mind as well. It’d be up to the devel­oper to remem­ber to “never access one of these two val­ues out­side of a crit­i­cal section”.

But with trans­ac­tions, it just works. We want to add a name to the string? Just open a trans­ac­tion in which both are mod­i­fied. The mod­i­fi­ca­tion depends on the cur­rent value of has_name? Well, just open it and check its value. It is guar­an­teed to stay con­sis­tent through­out the trans­ac­tion. And if we try to append a name, and one already exists? Why, we invoke the clear-name func­tion which, itself, also launches a trans­ac­tion. That’s no prob­lem. With locks this would have forced us to con­sider whether our locks are reen­trant, whether we’re intro­duc­ing any dead­locks, and so on. But we can com­pose trans­ac­tions just fine. And I can’t sim­ply for­get myself and try to access one or both shared objects out­side a trans­ac­tion. Because if I don’t have a stm::transaction ref­er­ence to pass to the open func­tion, I can’t get to the object stored within the shared wrap­per. With this code I can’t tell you which mes­sage is printed out, as it depends on the pre­cise tim­ing of the three threads and I do noth­ing to sequence or syn­chro­nize the threads in any par­tic­u­lar order, but I can guar­an­tee that what­ever is printed will be valid, and it will be either the mes­sage in which a name is spec­i­fied, or the mes­sage with­out a name. There are no dead­locks or race con­di­tions, at least not of the dan­ger­ous kind. I don’t know what the program’s out­put will be pre­cisely, but I know that it will be one of two mes­sages, both of which are con­sid­ered valid. The pro­gram does depend on the pre­cise order­ing of the threads, but its state is guar­an­teed to be con­sis­tent and valid at all times.

Of course, this exam­ple is still quite lim­ited. It allows us to stop wor­ry­ing about atom­ic­ity and thread-safety, but most pro­grams will also need some way to order and syn­chro­nize code, so that they can ensure that a spe­cific oper­a­tion on thread A only ever hap­pens once another oper­a­tion has been com­pleted on threads B, C or D. You can use con­ven­tional lock-based prim­i­tives for this if you like, but the STM library also pro­vides a few tools you may use. A few other fea­tures should also be men­tioned: like the abil­ity to return a con­sis­tent snap­shot of mul­ti­ple shared objects from a sin­gle trans­ac­tion, or the abil­ity to man­u­ally abort trans­ac­tions, or allow the sys­tem to fall back to attempt­ing a dif­fer­ent trans­ac­tion if the first one fails to com­mit. How­ever, these will be described some other time.

Hope­fully this quick tour of the most basic usage of my library has given you a rea­son­able idea of “what it’s all about”. Feel free to poke around at the code, and try using my library. But be aware that it is still not quite production-quality. The code needs to be cleaned up, a few aspects need to be opti­mized, the file orga­ni­za­tion is a mess, and the doc­u­men­ta­tion is… well, if you’ve got this far, you’ve seen all the doc­u­men­ta­tion that cur­rently exists. But to the best of my knowl­edge, the library works.

Blog posts

While I wrote my Mas­ters The­sis, I occa­sion­ally blogged about the sta­tus of the project. These posts can be found in the fol­low­ing list:
The­sis, yay!
Soft­ware Trans­ac­tional Mem­ory
Being func­tional in an imper­a­tive lan­guage
Using My STM Library
Hous­ton, we have a (per­for­mance) prob­lem
Empty state­ment of intent