Sunday, April 01, 2012

Memory management, reference counting, and ownership in the Mozilla codebase

Memory management is always an issue in large C++ programs. In small programs with a single programmer, manual memory management is fine (and fast). But in large programs, it is doomed to failure. Garbage collection is the usual solution, and, usually, a good one. But it has disadvantages, namely pauses and slow down, which is not acceptable in system software, such as a web browser (frankly, I would have thought you could do this cleverly and sneak garbage collection in when the browser is quiescent, which happens quite often. But, as browsers are used more and more as software platforms, this becomes less and less practical).

In Mozilla, we use reference counting for memory management. This is a compromise between safety, complexity, and speed. It is fast and there are no pauses, not as fast as manual memory management, but close enough. It is safer than manual memory management, but leaks can still be a problem. And it is much less complex than manual memory management, but an order of magnitude more complex than garbage collected 'fire and forget'.

C++ operator overloading allows for semi-transparent use of reference counting, but logically, you have to keep in mind that objects are reference counted. Transparency doesn't really work. Key to the way reference counting in Firefox works is the idea of object ownership. Object ownership is a subject close to my heart because lots of my research has been around ownership types, which statically enforce the ownership hierarchy which is implicit in the Mozilla system.

OK, now for some details, we'll get back to speculation later...

A reference counted pointer uses the nsRefPtr class, so for a pointer to an object of class C, you would use nsRefPtr. nsRefPtrs are quite clever, they do the bulk of the ref counting goodness, when you copy one the reference count goes up, and when one goes out of scope, the ref count goes down. nsRefPtrs are used to represent owning references, for example, a Layer object owners it's mask layer, so has a field with type nsRefPtr (well, there is no MaskLayer class, but you get the idea). Raw pointers are used for non-owning references, for example, if the mask layer keeps a reference to it's owner, then it would have a field of type Layer*. This is important because it means you can have reference cycles, but indicate which are counted (owning) references and which aren't so the aggregate will still get destroyed when it ought to. We also need ownership transfer, and this is done using already_AddRefed. These are temporary references, where, conceptually, the reference count is not incremented, but the refered to object is kept alive. Or, equivalently, a reference where the reference count is not increased by copying. Note that, when we copy the reference into an nsRefPtr, then the count is increased. So if we have a nsRefPtr field and it is the only reference to an object, then the ref count is one. A geter which returns an already_AddRefed reference to the field does not increase this count, but when we store that reference in another nsRefPtr, the count is bumped to two. However, if we store the reference in a raw pointer, the reference count stays at one. Ownership transfer happens by calling the forget() method on an nsRefPtr, this decrements the ref count and returns an already_AddRefed to the object. Note that if the ref count drops to 0, then the object will not be destroyed until the already_AddRefed also goes out of scope (which is why you should often use nsRefPtrs locally, even if it is just a temporary reference).

There are also getter_AddRefs references for use as 'out' parameters, and dont_AddRef references, which I have no idea about, but I won't go into them here.

So, in summary, we use a fairly sophisticated reference counting scheme which has at its core the concept of object ownership. For this kind of programming, could ownership types help? Well first, you'd actually have to motivate people to get over the extra syntactic overhead of ownership types, and for that you would probably need more benefit than improving reference counting. On the other hand, you only need a pretty lightweight system to help with reference counting. If you could statically enforce an ownership hierarchy, then, together with the system described above, you could be sure to avoid reference cycles and thus many memory leaks. This would be great. I would also hope that you could use the types to simplify the reference counting system, possibly making it more transparent, certainly reducing the number of reference types. But the challenge is that the implicit ownership described above is very unlike most ownership types systems, it is dynamic, supports multiple ownership and lightweight ownership transfer. So this is a non-trivial problem.

So, here is a challenge to language research people - can you come up with an ownership type system that simplifies this style of coding and reduces memory leaks without too much syntactic overhead? This is a great project because there is a huge corpus of real-world code that is constantly expanding and is all ready cross referenced (MXR, DXR) and is all open source, and lots of friendly people have experience applying all kinds of tools to it (unfortunately it will take some Google-fu to track down all the various blog posts about various things, but hey). The Rust language has some concepts for improving pointers, but I hope that we could do better with ownership types. There is real motivation within Mozilla to start using Rust to rework much of the project, so if you are quick, there is opportunity for any research to see real-world use. Anyone keen?

Footnote: if you are interested in finding out more about nsRefPtr look at the nsComPtr docs, they are almost identical, but nsComPtrs are used for XUL objects. The documentation doesn't seem to have been updated to reflect the widespread use of nsRefPtr.

1 comment:

  1. Anyone keen?

    Keen? yes. Have the time? that's a sadder story...

    ReplyDelete