Memory Management Part #2Filed Under: Articles, Weekly Tuesday Dose of goodness

Hi all,

Today I shall continue our discussion on memory management. However, today’s topic will be of a higher-level outlook with a lower-level understanding.

How so?

Read on…

In my last post I was talking about memory management based on new/delete and so on. The whole scheme here faces at least 3 problems:

1) Garbage collection
2) Strength of pointer checks
3) Pointer ownership

Let’s briefly talk about these problems and I’ll present a logical solution to all these 3 problems later.

Garbage Collection

In this context, we’ll be talking strictly about collecting memory that has been orphanated only. Some might mention that GC does more than just memory reclamation. Agreed, but let’s just focus on this for now.

What’s GC? Basically those who have learn Java and .NET will know that their respective VMs automatically help them delete the memory that they don’t really need. How? Simply by setting a “pointer” or “reference” to null.

Just a side note here, C++ pointers are totally different from Java pointers as well as .NET references. Some people might say, Java don’t have pointers. That’s wrong! If there’re no pointers, then why is there a NullPointerException then?

In short, I don’t have to explicit delete an object in Java or .NET in order to free up my memory; the VM does it for me.

In C++, obviously, by default, in its purest state, there is no such thing as a C++ built-in garbage collector. Therefore, we have 2 things that help resolve this problem:
1) Destructor
2) delete or delete[] keyword

But is that enough?

Strength of pointer checks

Next, even if we deploy our destructors and use the delete keyword as well as have a very nice contract with no loopholes to seal off as many memory errors as possible, we still face an inherent problem.

That is - when we perform checks on pointers, can the diagnosis be trustworthy?

Some may think, yeah why not? I can just do the following checks,

this,

if(!ptr)
return false;

or this,

if(ptr == 0xDEADBEEF || ptr == 0xFEEEFEEE)
return false;

The answer is - NO, these checks are barely enough to do the job!

Why not? First of all, by checking a pointer for ! or not only checks if a pointer is null or not. It doesn’t cater for dangling or wild pointers. So what are these types of pointers?

Dangling pointers are pointers pointing to an address that has already been freed prior.

Wild pointers are pointers that were not initialized when declared.

Guess what? These pointers point to a non-zero memory address, therefore making this check insufficient to guard against other types of pointers.

Next,

if(ptr == 0xDEADBEEF || ptr == 0xFEEEFEEE)
return false;

Does this help? Well… some compilers are kind enough to assign pointers to certain known addresses for wild pointers. That alone doesn’t guard against dangling pointers… and it certainly won’t work for Release mode. Unless you have a strong desire to make your program debug only (which has tons of dependency problems with VS2005 onwards), you might as well do away with these validations.

Pointer ownership

Lastly, let’s talk abt pointer ownership. This is a problem with all languages, not just with C++. Reason being that pointer ownership also refers to object ownership. Why? If you just consider the high level design, there’s also an obvious ownership problem for logical objects as well.

How so? In VM environments, it’s difficult, if not impossible to control when your objects’ memory are freed.  Yes, one might argue that the garbage collector can be called explicitly to clean up objects with zero reference count. But that alone isn’t object ownership.

What do we mean by object ownership? That is the ability to introduce master-slave mechanism into pointers. Which means, when the master decides to terminate itself, all other slave pointers will report a null pointer. A typical scenario would be a missile guidance algorithm with both owner and target pointers.  A stricter scenario would be a device-to-engine problem. For example, a game engine switching rendering APIs from OpenGL to Direct3D. A simple reference counting pointer algorithm is simply not enough to handle this scenario.

Solutions

Ok enough of the problems, let’s now talk about the range of solutions available to resolve problems in C++. I must apologise to the Java and .NET guys since it won’t apply to you guys.

1) auto_ptr<T>

Auto pointer is available in standard C++ library. What it does is simply transfering the ownership of a pointer to and fro a function. This means, if you pass in a pointer into a function and did not pass out, a few things will happen:

1) The object gets deleted in the function
2) The other auto pointers outside will return a null when checked against

This pointer container solves the following problems:
1) Careless memory leaks by scope
2) Somewhat semi-automatic cleanup of memory when function goes out of scope
3) Null validation is now effective

It also introduces or has inherent problems:
1) Pointer objects cannot be shared since it’s scope based
2) Possible dual-memory management (ie, 1 naked pointer, 1 pointer container, container deletes the pointer, leaving the naked pointer dangling)

2) boost::shared_ptr<T> and StridesLib’s cSmartPtr<T> (old)

I’m sure we’re all familiar with the boost library which might be integrated into the next iteration of C++ standards. Its shared_ptr<T> has the ability to resolve most of the memory leak problems. The key concept behind these 2 pointer containers is also known as reference counting.

See link: http://www.stridesdev.org/forum/viewtopic.php?t=7 to understand how it works in detail.

Basically, imagine the object in the heap is a meeting room. The people that comes into the meeting room are pointer containers pointing to the meeting room. The first person switches on the light, it also symbolizes that an instance of a meeting room is instantiated.

Next, more people come in, filling up the room, so we have a count. There’s like 10 persons in the meeting room right now.

Now, imbue everyone with the same responsibility; that is, the last person to leave the meeting room switches off the lights. Therefore, the last pointer container to be set to NULL will decrement its reference count to zero, at the same time, giving the pointer container the permission to delete the heap object altogether.

This pointer container solves the following problems:

1) All memory leaks related to new/delete only. (delete[] requires shared_array<T>)
- It doesn’t apply to COM objects directly - if your destructor did not release them, you’re going to leak them anyway.
2) Null validation is now effective
3) Objects can be shared

It also introduces or has inherent problems:
1) Possible dual-memory management (ie, 1 naked pointer, 1 pointer container, container deletes the pointer, leaving the naked pointer dangling)
2) Possible dual-container memory management (ie, 1 naked pointer shared by 2 separate pointer containers, each having reference count as 1, when set to null, one gets deleted while the other gets a dangling pointer with a reference count of 1 still. Guess what happens when the 2nd container goes out of scope?)
3) Shared pointer or cSmartPtr<T> (free download version) doesn’t have master-slave mechanism. Therefore, no doubt it’s shared, it still faces problems with device-to-engine problem.

3) StridesLib 1.0 cSmartPtr<T> (v2)

This implementation of cSmartPtr<T> is only available in Strides ADK and Strides Game Engine 1.0.

In v2, the very same reference counting pointer has evolved and now contains the master-slave mechanism which is essential to many parts of the game engine as well as game application.

With it, the pointer container can ensure that memory is cleaned up in the same process that created the object, preventing access violations due to overstepping the border.

It also ensures that no pointer is left dangling even if the master object has declared termination.

This pointer container solves the following problems:

1) All memory leaks related to new/delete only. (delete[] requires shared_array<T>)
- It doesn’t apply to COM objects directly - if your destructor did not release them, you’re going to leak them anyway.
2) Null validation is now effective
3) Objects can be shared
4) Master-slave mechanisms allow precise removal of objects without redudant memory usage
5) Allows individual DLL to delete their own objects within their own processes. This is not possible with shared_ptr<T> or cSmartPtr<T> (old) unless there’s a specific call in the game engine, demanding everybody to set their affected pointers to null. (A very crude way if you ask me)

It also introduces or has inherent problems:
1) Possible dual-memory management (ie, 1 naked pointer, 1 pointer container, container deletes the pointer, leaving the naked pointer dangling)
2) Possible dual-container memory management (as described above)
3) Not recommended for very tiny objects for example, Vectors with 4 floats.

4) cSmartPtr<T> (v3 commerical edition)

We’ll not talk abt v3 in this post. But in short, in this version, there’s virtually very little problems remaining.

Here’re the problems it solved on top of the other solutions:
1) Dual container management issue
2) Synchronization between threads, sensitive data protected during per read and per write
3) Master pointer can now “switch” pointers (replace operation)

Existing issues:
1) Possible dual-memory management (ie, 1 naked pointer, 1 pointer container, container deletes the pointer, leaving the naked pointer dangling) - This can’t be helped since we don’t override the operator new.
2) Possible performance issues as features become larger.

Hope it has been a nice ride for all who has read this article.

In my next post, I’ll introduce cSmartPtr<T> v3 commercial edition for sales! End to all standard memory leaks!

Signing off,
Jeremy

Tags: pointers smart container reference counting