Wednesday 11 May 2016

Grisou RIP

Grisou at his most felinely handsome. He always looked a bit of a rogue.
Our beloved Grisou is no longer with us. He went for his evening stroll around 7 on Sunday evening, and didn't come back. The following evening we heard that he'd been hit by a car on a busy road a long way from the house, far further than we ever thought he roamed, where we found his poor dead body.

Grisou's first day at our house
He was just barely a year old. By an awful coincidence, he was almost exactly the same age as Missy's brother Hercule was when he was also killed by a car, three years ago - thirteen months and a few days. He'd been with us less than a year, we were looking forward to celebrating the anniversary of his arrival on 21st May. That will never happen.

Poor Grisou. Poor, poor Grisou. He was a cat with an incredible character. His morning and evening strolls took him round our whole neighbourhood - and much further than we ever thought. Everyone knew him, he was a regular visitor to every garden.

But let's start at the beginning. After Hercule died, it seemed a good idea to get a second cat to keep Missy company. Whether cats need or want company is a big unknown, though she seemed very happy to be with Grisou once they got used to each other.

A good idea, but we worried how Missy would react at first. She is a very timid cat - unlike Grisou, probably no more than a couple of our neighbours even know she exists. As a result, it took us two years to act on the idea.

Isabelle saw a litter of kittens in the window of our local vet's office. Four were black, and two were grey. We went and held them, tiny tiny kittens that fit in the palm of my hand. We chose Grisou, rather than the other grey one, because even at just a few weeks old he seemed to have more character. He was tiny, about 800 grams (1.5 pounds), and liked to stand on my shoulder. For the first few days he hadn't quite mastered his hind legs, when he jumped he would land on his forepaws then not know what to do with the rest, landing in a tangled heap. He soon figured that out though.

The introduction to Missy was very tricky and painful. We kept Grisou in our spare bedroom, but he was desperate to escape - it was a challenge to open the door without him zooming down the corridor into the rest of the house. Missy knew he was there and would sniff at the door, miaowing. Our house has an enclosed atrium, open to the sky but not to the outside world. We would put Grisou in there and let Missy see him. Even though he was just a tiny kitten, she was frightened of him. She would stare at him for a minute or two, then retreat to the garden with her ears flattened.

Why Grisou? It's a French word, though nothing to do with cats - it means "firedamp" (methane) - but "gris" means grey. And it rhymes with "bizou", meaning kiss. He was a uniform medium grey all over, from his nose to his tail, with just very faint bands on his tail. His actual nose was a different shade of grey, which seemed to change all the time. He was beautiful.

Missy became more and more reluctant to enter the house at all until finally one morning I realised she hadn't even been inside to eat. I rushed to put her food outside and she ate with enthusiasm. She continued to eat outside for about three months. Very gradually she started to come back indoors, and to allow Grisou to get closer to her. He was full of enthusiasm and would chase after her, until eventually she would jump onto the fence leaving Grisou on the ground puzzled, thinking "How on earth did she do that?"

Eventually they settled down to a sort of clawed truce. They would play fight and hiss (well, Missy hissed) and chase each other around the garden or the house, but they never hurt each other (though Grisou would often have a bit of Missy's long fur stuck in his teeth). Then they'd settle down and snooze close enough to touch each other.

As soon as Grisou was big enough to go out, he started roaming the whole neighbourhood. He was a true "people's cat". We were shocked when, chatting with a group of our neighbours, we discovered they all knew him as a friend, a regular visitor to their gardens. We often saw him crossing our street, or just sitting at the side of the road - fortunately it's a very quiet street and nobody drives fast. One day we caught him teasing a dog who has a rather poor history with cats - an extremely bad idea, even though the dog was soundly tied to a tree. That was when I said, "It'll be a miracle if he lives to his first birthday." Well, he did, but only just, and not to his first anniversary with us.

Late last summer, we started keeping them both indoors at night. Partly this was just for my own sleep and sanity, since if I woke up in the night and one cat wasn't there I wouldn't be able to sleep. And also there were coyotes in the area, attacking and eating pet cats. It worked very well all through the winter. Both cats would be indoors by 8pm or so, we'd close the catflap, and have the security of knowing they were safe with us. They didn't seem to mind.

As the days got longer in spring, though, it got harder, and Grisou often wouldn't come home until bedtime. We knew he was touring the neighbourhood, though we had no idea how far we went. The furthest I ever saw him was half way to the main road - about 300 feet from the house. I really hoped that was the furthest he went - little did I know.

Whenever we travelled, we had a friend come by twice a day to feed Grisou and Missy and give them a cuddle. At first we wanted them to be indoors the whole time. We left the cat flap in its "entrance only" position, in case one got out by mistake. Then we had reports that they were both in the garden. We didn't know how until our friend saw Grisou lay on his back under the door, stick a claw into the plastic frame and pull it open inwards, then squirm out from underneath. We realised it was hopeless, so when we were away they had the freedom to come and go as they pleased.

We were away for a couple of weeks in March and April. After we got back, Grisou was out until the small hours a couple of times. He was quite a creature of habit. He would snooze indoors or close to the house all day, usually on his favourite footstool in our living room (where now there is nothing but a desperately sad cat-free space). Around 5 he'd start grooming, by 6 he'd be outside, and around 7 he'd disappear for the rest of the evening. Usually he came back before bedtime for a snack, and we'd close the cat flap. Then one morning recently we found that he'd figured out how to open it! He'd moved the heavy carton from in front of it then, most surprising, moved the stiff plastic catch that held it shut, opened it and escaped. I caught him trying to do the same thing late one night, after he'd popped in for a quick snack, so I put some heavy furniture in front of it. He was furious and spent the next hour complaining loudly. He almost never miaowed, only when he was cross. The following night, he simply didn't come in at all until about 3am.

Usually, he eventually accepted being shut in, and then he would settle down for an initial nap at the very back of a closet in our bedroom, almost completely invisible. At some point in the small hours he and Missy would have a ritual exchange of views, and then he'd settle down in his second night snoozing spot, on a cushion under some furniture by a window. He'd stay there often until 10am or later. Then he'd go out for his morning stroll, until 12 or so when he'd settle on the footstool for his daytime snooze again.

Sometimes he'd have a snooze at the top of the cat tree we got when Missy and Hercule were kittens. He'd leap to the top, his six kilos (13 pounds) very nearly toppling the whole thing, then curl up in the small space there. He never quite fitted, there was always a paw dangling out and his tail.

A few days before his birthday we had some sushi and gave him some of the tuna. He loved it. So his birthday treat was some sashimi-grade tuna from the Japanese supermarket. He loved that even more. His normal daily diet was dry cat food, with an evening treat of tinned tuna, and a morning treat of wet cat food. Missy too, though as far as we can tell she mostly only eats the dry food.

Some books say you should give your cats separate feeding places. So we did, we set up one in each of two bathrooms. The theory - our theory - was that one was for Missy and the other for Grisou. But they didn't take that seriously. For the last few days he was alive, they both ate "chez Missy la chatte", cleaning it out every night, while Grisou's place remained untouched.

Missy and Grisou in their respective snoozing places
A few days ago I came home early from work. It was so nice sitting in the garden in the evening sunshine with two cats, sometimes sitting quietly, sometimes chasing each other crazily around the garden, from one end to the other and back again. On Saturday afternoon I sat in my armchair, Grisou snoozing on the footstool and Missy on her favourite dining chair, both within reach. It was soporific, I wrote "There are few things less inducing to getting on and doing things than sitting between two snoozing cats". Perhaps I shouldn't have tempted fate.

Last Sunday, Isabelle returned from a trip to Europe. Both cats were waiting for her when we returned from the airport. Grisou seemed really happy to see her, demanding a cuddle and following her round the garden. Then in the evening he went off for his usual tour. The last time I saw him - alive - I remember he was licking delicately between the toes of his hind paws. He was so beautiful, so supremely feline.

He didn't come home before bedtime. I woke up at four, still no Grisou. I didn't get back to sleep. At 6 I looked everywhere for him, driving round all the local small streets. At lunchtime we put flyers in nearly 100 letterboxes, including places we thought were far outside his range. We still hoped, of course, that he'd show up - maybe after being shut in somewhere, or maybe deciding to get food and shelter in one of his many adoptive homes. We were sure of one thing - we'd looked everywhere and not seen a body by the road.

But were wrong. In the evening I got a text in response to the flyer, from someone who had found him dead in the main road. She'd called the police who had moved his body to the median where we hadn't seen it. So we walked down there, and there was his poor dead body, intact. You could almost believe he was just sleeping. But he wasn't. He was dead. And that is final. We carried his poor body home, to touch him one last time.

We used to speak French with him. When he showed up we'd say "il y un Grisou" (there's a Grisou) or "on a un Grisou" (we've got a Grisou). And I still say it to myself. But now it's not true, and it never will be, never again. And my keyboard is wet with tears.

The last ever photo of Grisou, the day before he died

Tuesday 3 May 2016

The Importance of Virtual Destructors

Our system had a memory leak. It wasn't huge, but network software (unlike phones or laptops) has to run for months or years without failure, so it was unacceptable. Unlike most complex software in C and C++, we are not plagued by memory leaks, so this was a bad surprise. We make extensive use of smart pointers (though not the horrible shared_pointer class, which is an ugly accident waiting to happen) and the RAII paradigm. As a result, objects get deleted when they should, whether they are short-term temporaries or long-term configuration information. Yet, we were leaking memory.

The fix, once we tracked it down, turned out to be the addition of a one-line function with an empty body:

virtual ~query_helper_iterator_base() { };

How can an empty function fix a complex memory leak? Read on...

Our system (STM) keeps track of several very large collections, of potentially millions of objects: network applications, hosts, users, network routes and several others. It provides a SQL-like Rest API that can be used to retrieve them based on complex filters and other criteria. For example, you can say "find the top 20 applications ordered by traffic rate, and tell me their current traffic rate and flow count".

Our web-based GUI maintains several charts, which it updates periodically every few seconds via the Rest API. Many users can run their own copy of the GUI, so these complex queries can be seen several times per second. The problem is that they require the whole collection to be scanned, and every entry to be inspected. As you may imagine, this is very expensive in CPU cycles and memory bandwidth, and we found it was a performance problem for our larger installations.

All of these collections are scanned in the background every few seconds, to maintain performance information. It doesn't seem hard, as we scan the whole collection and have them in L1 cache, to preload a cache for common queries such as the one above. Hence we came to write the query_helper collection of classes. Thus armed, we can say to a collection "do you have a cache which matches this query?". For example, we keep a cache of the top 1000 applications by traffic rate. When the GUI asks for the current top 20, we simply look at the cache and pick the top 20 from it - much easier than scanning a million applications.

Different caches have different implementations, depending on the nature of the query they are designed to support. For example, some use a simple STL vector, while others, which are explicitly ordered, use an STL set. This implementation detail needs to be hidden from the internal user, who merely knows that they have been given a cache that matches their query. This is, of course, an obvious application of virtual functions and pure base classes. The user sees a query_helper object, whose implementation is hidden behind them. So far, so straightforward.

The problem comes when we consider the iterators for these collections. The normal usage is a range-based for loop, which has to create a concrete iterator over the collection:

query_helper *qh = collection->find_matching_helper(rest_query);
if (qh) {
    for (object *obj : qh) {
        ...

The type of the iterator must be known, in detail, at compile time, yet the full type of the collection varies dynamically at runtime. How can this be made to work?

The solution is to use a second level of iterator, to which the base class iterator simply contains a pointer. That can in turn use virtual functions to implement an iterator in terms of the specific implementation of the actual query_helper object. The outer iterator simply delegates every function to the corresponding virtual function of the inner iterator. The only complication is that creating an iterator requires a dynamic memory allocation, but in the overall scheme of the Rest API implementation this is small stuff.

By now you're probably wondering what this has to do with our memory leak. I need to explain another implementation detail. The caches are rebuilt from scratch at every scan of the collection. But what happens if someone is using one when this happens? How can we know when it is safe to delete the old cache? The answer is that our cache uses our generic intrusive reference count mechanism. The object contains a reference count, and the same "mixin" class (called reference_countee) that provides it also provides a class-specific smart pointer that manipulates the counter, deleting the object when the count falls to zero.

So all we have to do is include said smart pointer in the iterator object, and it will protect the old cache from being deleted until the iterator is deleted. No possibility of dangling references, and all taken care of by C++'s constructor and destructor system. Nothing can go wrong...

Except (as you've guessed) something did go wrong. In fact, any cache that got used during its brief lifetime was never getting deleted. Reading the code, everything should have worked. The outer iterator (for the query_helper base class) has a destructor, which in turn deletes the inner iterator it points to The inner iterator's destructor destructs the smart pointer, which in the process decrements the reference count and, if this was the last user, deletes the object. That mechanism - the same identical C++ source code - is used in dozens of places in the code, and it works.

This, finally, is where the empty one line function comes in. C++, because of its heritage in C, doesn't assume that a function is virtual. Unless it's explicitly declared to be, the compiler assumes it can safely generate a static call to the member function of the actual class pointed to, rather than incurring he extra cost of using a function pointer. The base class of the inner iterator has no content, so the automatically-generated destructor does nothing.

So... when the outer iterator was deleted, its destructor was called. That correctly called the destructor for its contained inner iterator (thanks to std::auto_ptr... don't get me started on why the new unique_ptr is a terrible idea). But, instead of calling the proper destructor for the derived class, which would decrement the reference count and hence allow the old cache to finally be deleted, it was just calling the trivial destructor for the base class.

It's not the code in our one-line function that matters, it's simply the fact that it exists and (most important) is declared virtual. That tells the compiler that instead of generating a static call, it must look in the object's virtual function table (vtable) to find the corresponding function in the derived class.

C++11 purists will say, correctly, that there is another way this should be caught. If we define a function whose sole purpose is to override a virtual function in a base class, it should be given the 'override' qualifier. This would have generated a compiler error since the base class didn't in fact have such a function to override. We consider our wrists duly slapped, and will redouble our efforts to ensure that such functions are duly qualified.

This is pretty hard to understand, so at risk of making it even harder, here are some code snippets to illustrate what is going on. (It's not quite right yet - it's very hard to get the blog system to handle angle brackets).

/************************************************************************
 * First the base type for the INNER iterator - the one that MUST have
 * the critical virtual destructor. All its member functions, like
 * operator++ shown below, are pure virtual, and there are no member
 * variables.
 ************************************************************************/

class subtype_iterator_base : public std::forward_iterator_tag
{
public:
    // virtual ~subtype_iterator_base() { }; // the vital virtual destructor!
    virtual subtype_iterator_base &operator++() = 0;
    ....
};

/************************************************************************
 * Now the base query_helper class. This is the only class seen by the
 * users of this function - they are never aware of any of its derived
 * classes.
 ************************************************************************/

class query_helper
{
    ....    
/************************************************************************
 * Now the OUTER iterator of the base class. It contains only one member
 * variable, an auto_ptr to the base INNER iterator which actually does the 
 * work. All its member functions simply delegate to the corresponding
 * virtual member function of the inner iterator.
 ************************************************************************/

    class iterator : public std::forward_iterator_tag
    {
    private:
        auto_ptr my_sub_iter;
    public:
        iterator &operator++() { my_sub_iter->operator++(); return *this; };
        ....
    };
    ....
};

/************************************************************************
 * Finally, a specific derived class of the query_helper class, in this
 * implemented (somehow) using an STL set. It defines an iterator class,
 * derived from subtype_iterator_base, which in turn has a smart
 * reference-counting pointer to the query_helper it is using.
 * 
 * Note the inheritance from reference_countee (using CRTP), which provides
 * both the intrusive reference count and the ::pointer smart pointer
 * class. 
 ************************************************************************/

template<class OBJECT_CLASS, class COLLECTION_CLASS>
class query_helper_xxx : public query_helper,
                         public reference_countee<query_helper_xxx>
{
private:
    std::set<OBJECT_CLASS*> my_items;
public:
    class my_iterator_t : public subtype_iterator_base
    {
    private:
        typename std::set<OBJECT_CLASS>::iterator my_iterator;
        typename query_helper_xxx<OBJECT_CLASS,COLLECTION_CLASS> ::pointer 
            my_qh;
    public:
        C *operator*() const override { return *this->my_iter; };
        ....
    };
    ....
};

Monday 2 May 2016

Flying the London Helicopter Routes

To small planes the whole of London, from Docklands in the east to beyond Heathrow in the west, is a no-go area. With Heathrow's airspace, and London City's, and restrictions over the centre of London, almost everything inside the M25, except for fringes to the north and south, is closed.

Helicopters, though, are a different story. Because of their ability to land engine-out in a very small space and without risking damage on the ground, they are permitted on a small number of carefully planned routes that provide an out along their entire length - mostly in open spaces, except for central London where it is the river. These routes allow you to fly all along the Thames, from Chiswick to Greenwich, as well as directly overhead Heathrow airport. Considering how protective the UK is, it is astonishing - but true - that you can fly over Heathrow in the tiniest of single-engine helicopters, the Robinson 22. But you can - there are even videos on Youtube.

I'd wanted to do this for a long time, and finally a trip to England provided the opportunity. I booked a Monday morning flight with EBG Helicopters at Redhill Aerodrome (EGKR), in one of their Robinson 44s, so my son could come along too. I'd previously flown there in their Guimbal Cabri G2 (G-ETWO - geddit?). That was a very interesting introduction to a new (to me) type, but we didn't go very far from the field.

I'd prepared for the flight by studying the helicopter route chart, available from Pooley's, and reading what I could find on the web, e.g. this. From the south, the most interesting routes are H9, which runs dead straight from the A3 to just south of Heathrow at Bedfont, and then north to the A40 at Northolt. That is followed by a stretch of H10, along the A40 then turning right onto the North Circular Road (A406) to the river. There is a lot of IFR - I Follow Roads (or Rivers) - involved in this. H10 joins up with H4 (via a short stretch of H3), snaking along above the Thames from Kew through the centre of London to the Isle of Dogs. South and east of there, you can do what you want, relatively speaking anyway. H7 provides an alternative route north from Redhill straight into H4 if you don't want to fly over Heathrow.

Over the weekend, the forecast was not good, and I was afraid I'd have to cancel. But the morning dawned with blue skies. It clouded over by the time of our flight but never worse than 2500 overcast, plenty for this trip.

The first challenge is finding the aerodrome. Redhill has to be the hardest to find in the whole world, despite being only a couple of miles from Gatwick and sandwiched in the corner of the M25 and the M23. I'd been there before so had a rough idea, but was still very grateful for the data roaming package on my phone as I followed a succession of single-track country lanes and narrow roads through housing estates.

Once you find it, Redhill is a very interesting place. It's home to many of London's helicopters, including the Surrey Police, an air ambulance, Sky's ENG ship, and a good selection of expensive-looking executive machines. It also has a couple of grass runways but I've never seen a fixed-wing operation there - I think the runways must be waterlogged a lot of the time.

Briefing for the flight was simple enough - no flight plan or other permission is required. A quick call to Heathrow's ATC confirmed that they were taking H9 transitions, and then we jumped into G-PAMY to start our adventure: me, my son Joe, and my instructor for the day. It would be crazy to try a flight like this for the first time without someone who has done it plenty of times before. I asked him to take care of the radio calls since there are plenty of unfamiliar visual reporting points, and I'm not 100% comfortable with the differences between UK and US radio practice.

After takeoff our first call, crossing the M25, was to Heathrow Special. This sounds an odd name, to me anyway. All non-airline flights in Heathrow's airspace are done under Special VFR (SVFR), which is essentially VFR flight under IFR-like control. I did this once before flying from White Waltham to Stapleford, though I never got anywhere close to the airport. Heathrow Special is a dedicated frequency for such flights. They cleared us as far as the Bedfont holding point, at "approved altitude".  Every segment has an approved maximum altitude on the chart, sometimes changing every couple of miles, and you are expected to have this information to hand.


Close to Bedfont we were handed off to Heathrow Tower - a first for me and, unless I do this again one day, the only time. They were very friendly and helpful, despite handling the two busiest runways in the world as well as a pesky helicopter. There had been some concern about how long we'd have to hold, one of the guys at Redhill mentioned holding for 20 minutes and then again for 15 minutes between the runways. We had plenty of fuel and the view is excellent, so it wouldn't have been a problem, but it didn't happen. We were instructed to wait for one landing aircraft, which we did hovering at 1000 feet just south of the 27L runway numbers. Joe got several excellent shots of the arriving Air Canada 767. Once it was on the ground we were cleared to proceed across both runways, having hovered for less than a minute. The view was absolutely spectacular, along the whole length of Heathrow. I'm using to flying past San Francisco, and have even landed at LAX, but this was really extraordinary. There was a long line of departing aircraft, with a BA Airbus 380 at the tail. In fact I counted 5 A380s on the ground - a significant proportion of the entire fleet.

Once north of the airport, we went back to talking to Heathrow Special as we admired the collection of bizjets at Northolt - no evidence there that it is still owned and operated by the RAF. Soon we reached the Thames at Kew. The river is surprisingly twisty and quite hard to follow accurately, even though I slowed down to 60 knots - partly for manoeuvrability but mainly to enjoy the view. And the view was fabulous. With Battersea heliport below to our right we could see right across London, with Chelsea and the Royal Albert Hall off to our left. (At home we joke that Albert is plane spotting from his memorial, writing down the tail numbers of the airliners on long final into Heathrow in his royal notebook - this was probably the first time he logged G-PAMY).


Further on we got a very special treat - our timing coincided exactly with the Changing of the Guard at Buckingham Palace, giving us a spectacle of the Household Cavalry as well as the massed tourists in front of the palace. From the same location we also got an excellent view of the Houses of Parliament, Big Ben, Westminster Abbey and then Whitehall and Downing Street. I once had the good fortune to attend a meeting inside No 10 (the Cabinet Room, no less, though the occasion was much less exotic), but I'd certainly never seen it from this angle.

By now we were talking to City Airport tower, and they had us hold just short of Tower Bridge. We had a tailwind so hovering wasn't a great idea - instead we made a tight turn over the river and returned to Westminster Bridge, giving us a magnificent second showing of central London. Sadly we only got one turn around the hold, before City cleared us to proceed overhead Tower Bridge, following the twists of the river until the exit point of H4 at the southern tip of the Isle of Dogs.

From here it was a simple straight flight back over Croydon to Redhill, with a glimpse along the way of the remains of Croydon Airport, London's main airport before the War. All that's left is the terminal, a pre-war airliner in front of it, and about 200 feet of the runway.

Back at Redhill I demonstrated an autorotation to Joe - the common belief is that helicopters drop out of the sky if the engine fails, but in fact a power-off landing in a helicopter is much safer than in a plane since you only need a very small space to touch down. The aircraft descends quickly, but under complete control, and at about 40 feet above the ground you flare to slow down and stop the descent, then drop gently to the ground, cushioning the final drop with the remaining energy in the rotor.

From there it was a short hover in a challenging crosswind back to EBG's base, and we said goodbye to G-PAMY. Though not to Redhill, since we stayed for lunch at the excellent airfield cafe. The food is very good, but the best part is the toilets - or rather the walk to get there, which takes you around three sides of a hangar filled with unusual and vintage aircraft, including the only remaining specimen of the 1932 Spartan Arrow.

It was a wonderful trip, so good in fact that I'm awfully tempted to do it again when I'm in England again! There are lots more pictures from the trip here.