Category Archives: Uncategorized

Iterator Invalidation

You might be fooled into thinking by using std::vector and avoiding bare arrays created with new T[] that you’ll be avoiding all possible old-fashioned pointer-misuse bugs from the C era for that variable, for instance, null pointer dereferences, out of bounds access, memory corruption, etc. Not so – if you keep iterators  and references around to elements of a vector and then do anything to change its size, the standard says that those iterators and references may be invalidated by that operation(*). More importantly, you don’t get a warning about this and static analysis tools like cppcheck might not detect it in all cases (for instance, collection is modified by a function further down the call stack).

At least for operations like push_back which only affect the end of a group of iterators – there’s a simple trick you can do to save and restore a group of iterators after such an operation.

namespace detail
{
    /* Main implementation of KeepIteratorsAlive -
     * counts down through all the iterators through
     * a recursive call until we get to N = 0, at which
     * point call the function in question */
    template <typename Function,
              typename Collection,
              typename IteratorTuple,
              size_t   N>
    struct PreserveIterator
    {
        IteratorTuple
        operator () (Function      const &function,
                     Collection          &collection,
                     IteratorTuple const &tuple)
        {
            /* We need to call std::begin twice as the value of it
             * may change after we've called our iterator-modifying
             * function */
            auto distance = std::distance (std::begin (collection),
                                           std::get <N - 1> (tuple));
            auto result (PreserveIterator <Function,
                                           Collection,
                                           IteratorTuple,
                                           N - 1> () (function,
                                                      collection,
                                                      tuple));
            std::get <N - 1> (result) = std::begin (collection) +
                                        distance;
            return result;
        }
    };

    /* Specialisation for N == 0, at this point
     * we call the function and return an empty tuple
     * to fill up with the correct iterators again */
    template <typename Function,
              typename Collection,
              typename IteratorTuple>
    struct PreserveIterator <Function, Collection, IteratorTuple, 0>
    {
        IteratorTuple
        operator () (Function      const &function,
                     Collection          &collection,
                     IteratorTuple const &tuple)
        {
            function ();
            return IteratorTuple ();
        }
    };
}

template <typename Function,
          typename Collection,
          typename IteratorTuple>
IteratorTuple
KeepIteratorsAlive (Function      const &function,
                    Collection          &collection,
                    IteratorTuple const &tuple)
{
    typedef Function F;
    typedef Collection C;
    typedef IteratorTuple T;
    constexpr size_t const S = std::tuple_size <IteratorTuple>::value;

    return detail::PreserveIterator <F, C, T, S> () (function,
                                                     collection,
                                                     tuple);
}

You can use it like

std::vector <MyType> vector;
vector.push_back (MyType ());
auto it = vector.begin ();
std::tie (it) = KeepIteratorsAlive ([&vector]() {
                    vector.push_back (MyType ());
                },
                vector,
                std::make_tuple (it));

As for reference and pointer stability – this is more difficult. You can either wrap the object type in std::unique_ptr (and take a reference to it) or std::shared_ptr (and make a copy of the std::shared_ptr), which means you’ll pay the cost of another allocation and indirection costs on access, or you can assign each object a unique identifier by which you can use to look it up in the std::vector later.

If you want to avoid messing around with iterators, additional allocation or identifiers and in general iterator, reference and pointer stability is more important than performance then you can use boost::stable_vector

The main difference between the two is that boost::stable_vector is not contiguous, so if you have a lot of internal fragmentation (for instance, in these tests, 2 random erases for every three insertions) it can be a lot slower than std::vector. If array access performance is more important than insert/delete, then iterator adjustment and identifier tracking above can be used.

[smspillaz@平和猫とケーキ build (work)] $ ./src/benchmark 2000
2000 of boost::stable_vector (cold)
 0.000143s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
2000 of boost::stable_vector (warm)
 0.000111s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
2000 of std::vector (cold)
 0.000048s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
2000 of std::vector (warm)
 0.000040s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
2000 of std::list (cold)
 0.000104s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
2000 of std::list (warm)
 0.000069s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)

(*) Detailed by Louis Feng here.

Happenings

Bom dia!

University has all finished up this year. I’m really happy with the grades I’ve managed to achieve this semester – two of the highest grades I’ve ever achieved in law units. Bombed one exam, but still managed to do okay in the unit overall. Somehow managed a High Distinction for a Communications unit I thought I did awfully in. The mysteries of scaling.

I’ve been a little absent from lots of communities lately, so people might be wondering what I’m up to.

Well – I’m currently living here in Brazil for two months, involved with an organisation which I think is going to be a real gamechanger. I can’t say who they are or exactly what they’re doing – but they’ve got a very, very, very big goal and a very talented and enthusiastic team to bring that vision about.

I hope to get back (and report back) on what I’ve been doing with polysquare over this year as well. Unfortunately, it hasn’t been much due to the pure amount of study load I’ve had recently.

Tchau!

Server Grabs and getting stuck in _XReply

Here’s a quick reference to anyone in the future who ever gets stuck debugging some external library being stuck in _XReply

#0 _XReply

#1 ???

#2 some_library_do_thing

# 3 my_app_do_thing

Check if your app is using server grabs (XGrabServer, XUngrabServer).

Some third party libraries open up new X Server connections in the same process as yours. They shouldn’t do this, but they do anyways (graphics drivers are notorious culprits for this).

If you are holding a server grab and then call into a third party library which makes a synchronous call on its own X connection you will get a deadlock. This is because of how server grabs work – they prevent all connections from reading or writing any data until your connection has released the server grab.

When using server grabs (please don’t unless you really need atomic semantics around a series of X calls), always try to limit them to the closest possible subset of protocol requests you actually need atomic semantics around. Don’t just wrap some entire function in a server grab. Especially not if you plan to be calling callbacks which you don’t control or calling into libraries that are subject to change.

Also remember that XUngrabServer is not a synchronous operation – you will need to call XSync after using it in order to completely release the grab for other connections.

Coffee Party

I was glad to see Mark take leadership today and post an apology for the “tea party” comment. Thought leaders make mistakes and comments they later regret, as have I and plenty of others. While it is always important to hold leaders to account, it is also important to recognise when they have taken steps to address criticism directed towards them. I don’t have too much more to add, but I wholeheartedly agree with the final thoughts on that post, which I’ll leave here.

For the record, technical critique of open source software is part of what makes open source software so good. It is welcome and appreciated very much at Canonical; getting reviews and feedback and suggestions for improvement from smart people who care is part of why we enjoy writing open source software. There isn’t anything in what I said to suggest that I don’t welcome such technical feedback, but some assumed I was rejecting all feedback including technical commentary. [...]

I was talking about criticism of software which does not centre on the software itself, but rather on some combination of the motivations of the people who wrote it, or the particular free  software license under which it is published, or the policies of the company, or the nationality of the company behind it. Unless critique is focused on improving the software in question it is pretty much a waste of the time of the people who are trying to improve the software in question. That waste of time is what I had in mind with the comment; nevertheless, it was a thoughtless use of an irrelevant label.

[emphasis mine]

I’ll add a quick thought in here: Much of the hysteria and partisan criticism which is levelled at Ubuntu these days is objectively false and we as a community have a duty to examine the state of public debate to ensure that we are not distracted from what we each individually want to achieve.  This does not excuse the fact that there will always be difficulty in creating a product identity from a culture that is free-form in nature, but we should always recognise that individual actors in the ecosystem have the right to use their resources as they see fit to contribute in a way that may only benefit themselves, so long as those contributions do not pose a real practical harm to other actors within the community.

On another note, I make no apology to the real “Tea Party”.

Of Tea Parties and Armchairs

I was a little taken aback today by Mark’s “tea party” comment on the Trusty Tahr release announcement today. To try and put it in as much context as possible:

Mir is really important work. When lots of competitors attack a project on purely political grounds, you have to wonder what THEIR agenda is. At least we know now who belongs to the Open Source Tea Party ;)  And to put all the hue and cry into context: Mir is relevant for approximately 1% of all developers, just those who think about shell development. Every app developer will consume Mir through their toolkit. By contrast, those same outraged individuals have NIH’d just about every important piece of the stack they can get their hands on… most notably SystemD, which is hugely invasive and hardly justified. What closely to see how competitors to Canonical torture the English language in their efforts to justify how those toolkits should support Windows but not Mir. But we’ll get it done, and it will be amazing.

I can tell you what the agenda of the Mir team is: speed, quality, reliability, efficiency. That’s it. From what I’ve seen on the smartphone, Mir is going to be a huge leap forward for gaming performance, battery life and next-generation display capabilities. So thank you for the many contributions we had to Mir, and to everyone who is testing it in more challenging environments than the smartphone. I’m enjoying it on my laptop and loving the gaming benchmarks for native Mir. So to that team, and the broader community who are helping test and refine Mir, thank you.

I was a little disappointed that this comment came out, since I really thought that the inevitable controversy that comes with any major direction-setting decision had come and gone. It was quite clear that it was aimed more broadly at Red Hat and Intel with the reference to systemd, which is unfortunate, because while there was a recent controversy surrounding Intel, I don’t think they are really the “tea party” that Mark wants to refer to.

For my non-Western or at least non-U.S based readers, the “tea party” is a far-right, decentralized and loosely associated political group that exists within the Republican party. They are (arguably) backed by some large and anonymous vested interests and have only performed the function of skewing debate about, and obstructing the implementation of some socially and economically “liberal” policies such as the Patient Protection and Affordable Care Act. Their actions are largely the reason why the non-essential administrative services associated with the normal running of government went unfunded for the past two weeks and why we almost had the United States default on its foreign debt on Thursday. The “Tea Party” uses its small political power to its maximum extent in order to manufacture crisis after crisis in order to destabilize a democratically elected government and house.

It is no surprise then that calling a group of people within a community a “tea party” is a very deliberate attempt to categorize them as a group of people whose sole purpose is to destabilize, and no doubt insulting to that group of people.

There is a tea party, but just not who you expect

I think Mark did pick up on something though, which is that a tea party does exist. I’m not going to name them or imply who they are, because they are a disparate group of loosely-affiliated people, so it would be a rather pointless exercise.

One thing I think Mark got confused in his comments was the difference between those who are heavily involved in the development of open source software projects on one hand and their vocal proponents (or opponents) on the other. I tend to find that these groups are usually mutually exclusive and it is only on limited occasions that you’ll find some overlap between the two. The reality is that the vast majority of us are far too busy working on our projects, whether that be Wayland, Weston, Mutter, KWin, Mir or something else to really care all that much about coming out on top of a political crisis with words. And we know all too well that its very difficult to change taken direction with words alone.

The “tea party” does exist though. It exists in a loosely-associated group of people I like to call “armchair free software developers”. These people feel a kind of emotional closeness to the community and to particular projects but are not involved in the day to day development of those projects, either because they don’t feel that have the skills required to do so, don’t want to make the effort to do so, or simply don’t have time (because they are busy with other and probably more important things). In order to resolve this relevant inability to contribute, they create political debate and drum up support and opposition to things as an ostensible “contribution” in order to maintain their self-deception about their closeness to a community or project.

Now in jest I say – the irony in Mark’s statements is that he’s just fulfilled this exact criterion of being an “armchair free software developer”, and the irony in my statements is that I’ve also fulfilled this exact criterion of being such an armchair developer. Mark can’t be involved with the day to day running of these projects because he’s too busy trying to run a venture with a lot of external influences. I can’t be involved with the day to day running of these projects because I’m too busy with my Law degree.

If you watch the logs of the #wayland or #ubuntu-mir IRC channels on freenode or their respective mailing lists, you’ll notice that its very rarely that anybody there makes political commentary on, or let alone even talks about, the other project. It is also very rare that they talk about Windows’ Desktop Window Manager, or OS X’ Quartz Extreme, or Android’s SurfaceFlinger, or any other “competing” project. Usually whenever that happens it is some new person trying to start an argument and they usually get ignored.

On the other hand, if you watch the Phoronix forums, Reddit or various blog posts and their comments, lots of people who have hardly anything to do with these projects seem to have a lot to say about them as well as the constant capacity to talk about them. The political commentary is typically quite shallow, makes reference to blog posts published months ago and is usually just spreading misinformation and hearsay. It does appear to make up the vast majority of the debate.

At this point, you might be asking what my credibility is on this. After all, this is just a blog post. I’ll be the first to say that I’m not involved in the day to day running of either project. After all – I have more pressing things to do with my time. I speak here as a developer who has been somewhat involved with both projects. I’ve made (very limited) contributions to both Mir and Weston, wrote the client code to support both display servers for a large media center project. I helped to write the backend for an important graphical toolkit for one of the display servers. More importantly, I speak as a person who is a personal friend of developers from both projects. Which leads me nicely on to the next section.

Why do “tea parties” and “armchair developers” matter?

One fallacy is to equate a project’s proponents and opponents with its developers. Another fallacy is to assume that because somebody does not contribute to discussion and debate, then they are not engaged or affected by its contents. There’s a really depressing feeling that comes with scrolling through comment after comment about your project, the fruit of your hard labor by the politically insatiable minds of Reddit or one of Mark’s blog posts about your “hidden agenda”.

Seeing hateful comment after hateful comment about compiz in an attempt to “contribute” to the debate by comparing it with other similar projects is what made me effectively give up on it and move on to other completely different projects in the middle of this year. In fact, I almost did so at the end of 2011 and didn’t because I was being paid to work on it. Why put all your effort into maintaining something when people constantly rag on about how its “garbage” or “tainted” or “CLA riddled” or “a corporation’s hidden agenda” or … you get the picture. The positive comments sprinkled here and there in a sea of partisan criticism manifesting itself as “contribution to the debate” only made my imposter syndrome worse. Those who manage the affairs of Intel, Red Hat and Canonical should take particular note of this. You are demotivating your employees by engaging in constant crisis and debate.

Every project that is somehow involved in all of this each has its own unique and important merits. Both Wayland and Mir have substantially innovated in the protocol space, development methodology and flexibility of display servers. They are both good things. Let their developers create and refine the fruits of their labor and don’t punish them with partisan criticism and never-ending political debate and crisis.